p-Stable LSHをC++11でさっくり実装

C++

高次元の特徴量を持ったベクトルの集合に対して，与えられたクエリベクトルに似ているものを探し出すという問題を，近傍探索とかいう．旧来のkd-treeあたりを使った探索ではなく，近似的に近いベクトルを探す近似近傍探索が流行っている（らしい）．近似近傍探索のひとつ，LSHの説明を読んでたら「これ案外簡単に実装できるんじゃね？」と思い至ったので，C++11で書いてみた．

LSHについては以下の説明がとても分かりやすい．
060108 Locality-Sensitive Hashingの実装が一段落 - 飛行船通信 - Seesaa Wiki（ウィキ）
他には以下を実装の参考にした．
lsh p-stable
最近のバイナリハッシングをいくつかJavaで実装してみた - るびゅ備忘録
Locality Sensitive Hashing - (setf yaruki nil) - nlpyutoriグループ
Locality Sensitive Hashing (LSH) Home Page

ちゃんとテストしてないので色々アレかもしれない…

  • 10/3 7:02追記 一時オブジェクトへのポインタを返すという恥ずかしいミスをやらかしていたので修正．
#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>

namespace LSH {
  using namespace std;

  template<class T, int min = 0, int max = numeric_limits<typename T::result_type>::max()>
  typename T::result_type rand() {
    static mt19937 engine;
    static T distribution(min, max);
    return distribution(engine);
  }
	
  // hash cell -> http://www.mit.edu/~andoni/LSH/manual.pdf section 3.5.2
  struct lshHash {
    int h1, h2;
    bool operator ==(lshHash const& lsh) const {
      return h1 == lsh.h1 && h2 == lsh.h2;
    }
  };

  // h(x)
  template<typename T, int d, int r>
  struct H {
  public:
    H() : b(rand<uniform_real_distribution<double>, 0, r>()) {
      for(auto& value : a)
        value = rand<normal_distribution<double>, 0, 1>();
    }

    int operator () (array<T, d> const& x) const {
      return static_cast<int>((inner_product(x.begin(), x.end(), a.begin(), 0) + b) / r);
    }
  private:
    array<T, d> a;
    double b;
  };

  // g(x) = [h1(x),h2(x), ....hk(x)]
  template<typename T, int d, int k, int r>
  struct G {
  public:
    G() {
      for(int i = 0; i < k; i++) {
        r1[i] = rand<uniform_int_distribution<int>>();
        r2[i] = rand<uniform_int_distribution<int>>();
      }
    }
    lshHash operator ()(array<T, d> const& x) const {
      lshHash hash = {};
      array<int, k> a;

      for(int i = 0; i < k; i++)
        a[i] = h[i](x);

      hash.h1 = inner_product(a.begin(), a.end(), r1.begin(), 0);
      hash.h2 = inner_product(a.begin(), a.end() ,r2.begin(), 0);
      return hash;
    }
  private:
    array<H<T, d, r>, k> h;
    array<int, k> r1;
    array<int, k> r2;
  };

  template<typename T, int K, int L, int d, int r>
  class pStable {
  public:
    typedef array<T, d> data_type;

    void add(data_type const& val) {
      data.push_back(data_type(val));
      auto& v = data[data.size() - 1];

      // L個のハッシュテーブルに値を格納
      for(int i = 0; i < L; i++)
        hash_tables[i].insert(make_pair(g[i](v), data.size() - 1));
    }

    unordered_set<const data_type*> query(data_type const& query_data) const{
      unordered_set<const data_type*> result;

      for(int i = 0; i < L; i++){
        auto h = g[i](query_data);
        auto range = hash_tables[i].equal_range(h);

        while(range.first != range.second){
          result.insert(&data[range.first->second]);
          ++range.first;
          if(result.size() >= 2 * L) return result;
        }
      }
      return result;
    }
  private:
    array<G<T, d, K, r>, L> g; // Hash-Familiy
    vector<data_type> data;
    array<unordered_multimap<lshHash, int>, L> hash_tables;
  };
}

namespace std {
  // unordered_map使うための部分特殊化
  template<>
  struct hash<LSH::lshHash> {
    size_t operator()(LSH::lshHash const& h) const{
      return h.h1;
    }
  };
}

boost嫌いという訳では全然ないんですが，C++11の標準機能だけでもC++03と比べて格段に楽できるという宣伝のつもり．実際に書くのはすごく楽で，唯一unordered_mapを自前のクラスに適用するときに，std::hashの部分特殊化が必要ってことに気づかずに困ったくらい（boostだとhash_value()をグローバルに置いておくだけでADLが効くので，同じノリで書いていた）．reinterpreter_castはどうみても設計が良くないせいなので，どうにかしたい…．(10/3 7:02追記)修正．

int main(void){
  int const d = 10; // 特徴次元
  int const k = 4; // ハッシュコード長
  int const L = 10;// バケット数
  int const r = 2; // Hash Parameter

  typedef std::array<double, d> data_type;

  LSH::pStable<double, k, L, d, r> hash;

  hash.add(data_type{  1,  2,  3,  4,  5,  6,  7,  8,  9, 10});
  hash.add(data_type{100,100,100,100,100,100,100,100,100,100});
  hash.add(data_type{  1,  2,  5,  4,  5,  6,  7,  8,  9, 10});
  hash.add(data_type{  1,  2,  3,  0,  5,  8,  7,  9,  8, 10});
  hash.add(data_type{  2,  1,  2,  4,  5,  6,  7,  8,  9, 10});
  hash.add(data_type{});

  auto result = hash.query(data_type{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

  std::cout << "result:" << std::endl;
  for(auto val : result){
    for(auto v : (*val))
    std::cout << v << ",";
    std::cout << std::endl;
  }
}

出力：

result:
1,2,3,4,5,6,7,8,9,10,
2,1,2,4,5,6,7,8,9,10,
1,2,5,4,5,6,7,8,9,10,

ちなみにC++のLSH実装としてはLSHKITというのがあるらしい．あとは最近のOpenCVにもいつの間にか追加されてる．

名前を知るということ「コンピュータ・ジオメトリ」

読書

最近仕事のほうでは組み込み環境で動かす画像認識のようなものをやっております．はてなインターンに参加したりもしつつ，何だかんだで大学では電気電子を中心にやっていたので，学生の気分で情報科学に入門中．入門中とはいっても業務は待ってくれないので，解くべき問題がトップダウンに与えられ，それに答えるために本を探すことも多い．

で，最近買った本．

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用

  • 作者: M.ドバーグ,M.ファンクリベルド,M.オーバマーズ,O.チョン,Mark De Berg,Mark Overmars,Mark van Kreveld,Otfried Cheong,浅野哲夫
  • 出版社/メーカー: 近代科学社
  • 発売日: 2010/02
  • メディア: 単行本
  • 購入: 4人 クリック: 34回
  • この商品を含むブログ (5件) を見る


この本を取っ掛かりにして，自分が解こうとしていたある問題が，最近傍探索という名前で呼ばれている種の問題に帰着できることを知った．また，その名前でググることで，LSH，Spectral Hashing，AGHのような近似最近傍探索で自分の問題に使えるかもしれない最近の手法にリーチすることができたり，NLPであったりデータベースの探索問題みたいな話題にもつながっていることを知ったりと，一気に視野が開けた．
自分にとって未知の分野の問題を解くとき，「いかに的確な名前を知るか」というのはすごく重要なんだなーというのを改めて感じた一日．
ちなみに本自体も良書で，線分交差判定や移動計画問題，直交領域探索といった問題を取り扱っており，あまり前提知識が無くても（簡単なデータ構造やO記法程度に馴染みがあれば）すんなり読み進められる．

VBAの個人的な嵌りどころ

メモ VBA

必要に迫られてVBA入門中．ちょっと嵌ったところをメモ．間違っていたら誰か指摘してください…

小数→整数への暗黙変換は，最近接偶数に丸められる

小数部が0.5未満のときには切り捨て，ちょうど0.5のときは最も近い偶数に丸められ，それ以外のときには切り上げられる．

Dim i As Ingeger
Dim d As Double

d = 0.5
i = d '0

d = 0.51
i = d '1
 
d = 1.5
i = d '2

d = 1.51
i = d '2

関数の引数はデフォルトで参照渡し

組み込み型だろうと何だろうと，ByValを明示しない限りは参照で渡される．

Sub Test()
    Dim i As Integer
    i = 0
    func1 i  ' i == 1
    func2 i  ' i == 2
    func3 i  ' i == 2
End Sub

' 参照渡し
Private Function func1(i As Integer) As Integer
    i = i + 1
    func1 = i
End Function

' 参照渡し
Private Function func2(ByRef i As Integer) As Integer
    i = i + 1
    func2 = i
End Function

' 値渡し
Private Function func3(ByVal i As Integer) As Integer
    i = i + 1
    func3 = i
End Function

関数呼び出しの引数を括弧でくくるかどうかは，戻り値を使うかどうかで使い分ける

戻り値を捨てる場合は括弧なし，戻り値を使用する場合は括弧有りの書式を使う必要がある．

Sub Test()
    Dim i As Integer
    i = 0
    func1 1, 2       ' OK
    func1(1, 2)      ' Error! 戻り値を使わない場合は括弧を使用しない
    i = func1(1, 2)  ' OK
    i = func1 1, 2   ' Error! 戻り値を使う場合は括弧を使用する
End Sub

Private Function func1(i As Integer, j As Integer) As Integer
    func1 = i + j
End Function

ところが，関数を1引数にすると挙動が変わるように見える．

Sub Test()
    Dim i As Integer
    i = 0
    func1 1       ' OK
    func1(1)      ' OK 2引数の時と違う???
    i = func1(1)  ' OK
    i = func1 1   ' Error! 戻り値を使う場合は括弧を使用する
End Sub

Private Function func1(i As Integer) As Integer
    func1 = i + 3
End Function

この場合の括弧は，実は関数呼び出し側ではなくて引数を修飾したものとして解釈されているらしい．

Dim i As Integer
Dim j As Integer

i = (j) + 3  ' jをコピーした一次オブジェクトと3との和をiに代入
func1(i)     ' iをコピーした一次オブジェクトを，括弧無しの呼び出し構文でfunc1に渡す

ややこしいけど，ここでのfunc1(i)の括弧は，関数ではなくiのほうを修飾したものとして解釈されている．(i)というiのコピーがまず生成され，func1に「括弧無しの書式で」渡っているので，戻り値を評価しなくても当然合法な構文となる．
”括弧を付けると値渡しになる”と解説しているサイトがあったが，結果としてそうなっているだけで，関数呼び出し側にそのような規則があるわけではない．また，”戻り値を評価しない場合には括弧を付けても付けなくても良い”というような解説も見かけたが，1引数のときに見かけ上そうなっているだけで，2引数の場合にはエラーになるのでこれも正しい解釈ではなさそう．
値渡しで引数を渡す - プロシージャ - Excel VBA入門
Office TANAKA - Excel VBA Tips[括弧が必要な場合]

2進数リテラルが欲しいときのまとめ

C

たとえば組み込みで，2進数っぽい文法で数値を扱いたいときがある．ドットマトリクスに顔文字アイコンを表示させるときに

set_icon_data(
    0x0a, //  1 1 
    0x0a, //  1 1 
    0x00, //      
    0x11, // 1   1
    0x0e  //  111
);

みたいにベタ書きなのはあまりにも悲しい．顔文字をコードで直接記述したい！でもC/C++は2進表記を直接サポートしない．じゃあどうするか．

コンパイラの拡張構文を使う

コンパイラによっては"0b00100000"みたいなリテラルで2進数を扱える場合もある．4.3以降のgccでもそう．

set_icon_data(
    0b01010,
    0b01010,
    0b00000,
    0b10001,
    0b01110
);

マクロでbinary literal風事前定義

2進数表記のようなマクロを事前に定義しておく．数が多いなら機械的に生成してあげればOK．

#define b00001 1
#define b00010 2
...

set_icon_data(
    b01010,
    b01010,
    b00000,
    b10001,
    b01110
);

1ビットシフトへの置換

次の手はプリプロセッサに頑張ってもらう方式．定数式なのでコンパイル時に全部計算され，機械語の時点では上と全く一緒になっている．

#define $ (((((0
#define X  <<1|1)
#define _  <<1)

set_icon_data(
    $ _ _ _ _ _,
    $ _ X _ X _,
    $ _ X _ X _,
    $ _ _ _ _ _,
    $ X _ _ _ X,
    $ _ X X X _
);

アイコンっぽくて楽しい感じ．

8進数を介して2進リテラルもどきを生成

8進数で"1011"は2進数で"001 000 001 001"になる．文字列結合演算子##を使って8進数表現にしてから3nビット目をnビット目にマッピングすることで，"1011"から11を得ることができる．これも得られるバイナリは一緒．

#define PP_HEX2BIN(b) ( \
 ((b & 1 <<  0) >>  0) + ((b & 1 <<  3) >>  2) + ((b & 1 <<  6) >>  4) + \
 ((b & 1 <<  9) >>  6) + ((b & 1 << 12) >>  8) + ((b & 1 << 15) >> 10) + \
 ((b & 1 << 18) >> 12) + ((b & 1 << 21) >> 14))

#define B(x) PP_HEX2BIN(0 ## x)

set_icon_data(
    B(01010),
    B(01010),
    B(00000),
    B(10001),
    B(01110)
);

(C++)boostを使う

上と似た機能はboostでも提供されているので，C++なら実装しなくてもよい．こっちは間にスペースが入っていてもOK．

#include <boost/utility/binary.hpp>

#define B(x) BOOST_BINARY(x)

set_icon_data(
    B(01010),
    B(01010),
    B(00000),
    B(10001),
    B(01110)
);

// これでもOK
#define _ 0

set_icon_data(
    B(_ 1 _ 1 _),
    B(_ 1 _ 1 _),
    B(_ _ _ _ _),
    B(1 _ _ _ 1),
    B(_ 1 1 1 _)
);

(C++0x)constexpr

constexprを使ってコンパイル時に評価．演算子を使えると絵としての表現力が上がりますね！
参考：二進数リテラル(嘘) - とくにあぶなくないRiSKのブログ

set_icon_data(
    -+-+-b(),
    -+-+-b(),
    -----b(),
    +---+b(),
    -+++-b()
);

画像のアルファ合成

OpenCV メモ

cvLoadImageは読み込む画像のアルファチャネルを無視するので，画像を重ねあわせるときに不都合．opencv内で何かしらのマスク画像を生成し，そいつを使って重ねあわせる（参考：opencv.jp - OpenCV: コピーと充填（Copying and Filling）サンプルコード -）こともできるけど，ImageMagickのConvertツールを使えばとても簡単．

convert foo.png -channel Alpha -negate -separate foomask.png

後は，cvCopyを呼ぶときにこのマスク画像を使えばOK．

IplImage* target = cvLoadImage("target.png");
IplImage* foo = cvLoadImage("foo.png");
IplImage* foomask = cvLoadImage("foomask.png");

cvCopy(foo, target, foomask);

ちなみに単に画像全体を重み付きで合成するなら，cvAddWeightedでOK．

メンバ関数の戻り値に対応したアニメーションを描画

C++ OpenCV

オブジェクトの状態をOpenCVのウィンドウ上に色々な方法で表示させたい．たとえば，

class Foo {
public:
    int foo() const;
    const std::string& bar() const;
    double buzz() const;
private:
    int foo;
    std::string bar;
    double buzz;
};

こういうクラスが有るときに，「fooの値に連動して画像が回転する」とか，「barやbuzzの戻り値を画面にテキストで表示する」とか，「buzzの戻り値がある閾値以上のときにだけ表示するアイコンが欲しい」みたいな要求を満たしてくれるモノがあると，ロジックとビューを分離できて嬉しいなーと思ったので，車輪の再発明とは思いつつ実装してみた．

ベースクラス

デザインパターンの教科書通りに，まずは文字と画像に共通の基底クラスを用意．IplImageのポインタを渡すと，そこに自身のエレメントを描画するようなインターフェースにしてみる．

#ifndef IELEMENT_H_
#define IELEMENT_H_

class IElement {
public:
	IElement(int x, int y) : x_(x), y_(y){}

	virtual ~IElement(){}

	/**
	 *  渡された画像の上に自身のエレメントを加える
	 */
	virtual void draw(IplImage* image) = 0;

	/**
	 *  エレメントの親要素に対する水平方向相対位置を取得する
	 */
	int x() const { return x_; }

	/**
	 *  エレメントの親要素に対する垂直方向相対位置を取得する
	 */
	int y() const { return y_; }

	/**
	 *  エレメントの親要素に対する相対位置を設定する
	 */
	void setPoint(int x, int y) { x_ = x; y_ = y; }

protected:
	IElement();
	int x_;
	int y_;
};

#endif

文字の表示

ostringstreamで変換可能な型であれば何でも表示させたい，ということで内部にテンプレートクラスを持たせる．

#ifndef TEXT_ELEMENT_H_
#define TEXT_ELEMENT_H_

#include <sstream>
#include <string>
#include <opencv/cv.h>
#include <opencv/highgui.h>

#include "IElement.h"

/**
 *  文字を表示するエレメント。
 */
class TextElement : public IElement {
public:
	TextElement(const std::string& s, int x, int y, 
	    int fontFace = CV_FONT_HERSHEY_SIMPLEX, CvScalar color = CV_RGB(0, 0, 0), int thickness = 1) : IElement(x, y){
		cvInitFont(&font_, fontFace, 1.0, 1.0, 0.0, thickness, 8);
	}

	virtual void draw(IplImage* image){
		cvPutText(image, s_.c_str(), cvPoint(x_, y_), &font_, color_);
	}

protected:
	std::string s_;  //! 表示する文字列
	CvFont font_;    //! フォント
	CvScalar color_; //! 文字色
};

/**
 * 動的に情報を更新して文字を表示するエレメント。
 */
class DynamicTextElement : public TextElement{
	class _Holder {
	public:
		virtual std::string value() = 0;
	};

	template<class T, class Func>
	class _HolderImpl : public _Holder {
	public:
		_HolderImpl(const T& src, Func f) : src_(src), f_(f) {}
		virtual std::string value(){
			std::ostringstream ss;
			ss << (src_.*f_)();
			return ss.str();
		}
	private:
		Func f_;
		const T& src_;
	};

public:
	template<class T, class Func>
	DynamicTextElement(const T& src, Func f, int x, int y, int fontFace, CvScalar color, int thickness = 1)
		: TextElement("", x, y, fontFace, color, thickness){
		holder_ = new _HolderImpl<T, Func>(src, f);
	}

	template<class T, class Func>
	DynamicTextElement(const T& src, Func f, int x, int y) : TextElement("", x, y){
		holder_ = new _HolderImpl<T, Func>(src, f);
	}

	virtual void draw(IplImage* image) {
		s_ = holder_->value();
		TextElement::draw(image);
	}

private:
	_Holder* holder_;
};

#endif

これで，こんな感じにメンバ関数の戻り値をテキスト表示できるようになった．

#include <string>
#include <vector>
#include <opencv/cv.h>
#include <opencv/highgui.h>
#include "TextElement.h"

class Foo {
public:
    int foo() const;
    const std::string& bar() const;
    double buzz() const;
private:
    int foo;
    std::string bar;
    double buzz;
};

// てきとうなウィンドウ描画クラス
class Window {
public:
    void addElement(IElement* element){
        elements_.push_back(element);
    }

    void draw(IplImage* image){
        for(auto it = elements_.begin(); it != elements_.end(); ++it){
            (*it)->draw(image);
        }
    }
private:
    std::vector<IElement*> elements_;
};

int main(void){
    Foo f;
    Window w;

    w.addElement(new DynamicTextElement(f, &Foo::foo, 0, 0));    // Foo::fooの戻り値を(0,0)に表示
    w.addElement(new DynamicTextElement(f, &Foo::bar, 100, 0));  // Foo::barの戻り値を(100,0)に表示
    w.addElement(new DynamicTextElement(f, &Foo::buzz, 200, 0)); // Foo::buzzの戻り値を(200,0)に表示

    IplImage* img = cvCreateImage(cvSize(720, 480), 8, 3);
    cvNamedWindow("foo");

    while(1){
        cvWaitKey(10);
        w.draw(img);
        cvShowImage("foo", img);
    }
}

画像

画像の表示も基本的にアイデアは同じで，クラスの内部に非テンプレートな基底クラスと，テンプレートな派生クラスを持たせておけばＯＫ．リソースの解放や例外処理をぜんぜんケアしていなかったり，冗長で汚らしい感じだけど例えばこんな風に書いてみる．

#ifndef IMAGE_ELEMENT_H_
#define IMAGE_ELEMENT_H_
#include <string>
#include <vector>
#include <opencv/cv.h>
#include <opencv/highgui.h>

#include "IElement.h"
#include "cvHelper.h"

/**
 * 画像を表示する基本エレメント。
 */
class ImageElement : public IElement{
public:
	ImageElement(const std::string& filename, int x = 0, int y = 0)
	    : IElement(x, y), mode_(NORMAL), parent_(NULL), image_(NULL){
		imageOrigin_ = loadImage(filename);
		if(imageOrigin_ != NULL){
			image_ = cvCreateImage(cvSize(imageOrigin_->width, imageOrigin_->height), 8, 3);
			cvCopy(imageOrigin_, image_);
		}
		this->affineMat_ = cvCreateMat(2, 3, CV_32FC1);
	}

	ImageElement(const std::string& filename, ImageElement* parent, int x, int y)
	    : IElement(x, y), mode_(NORMAL), parent_(parent), image_(NULL){
		imageOrigin_ = loadImage(filename);
		if(imageOrigin_ != NULL){
			image_ = cvCreateImage(cvSize(imageOrigin_->width, imageOrigin_->height), 8, 3);
			cvCopy(imageOrigin_, image_);
		}	
		this->affineMat_ = cvCreateMat(2, 3, CV_32FC1);
	}

	~ImageElement(){
		if(image_ != NULL) cvReleaseImage(&image_);
		if(imageOrigin_ != NULL) cvReleaseImage(&imageOrigin_);
		cvReleaseMat(&affineMat_);
	}

	virtual void draw(IplImage* image){
		if(!enable_) return;

		if(parent_ == NULL) setImage(src, image_, x_, y_, mode_);
		else                setImage(src, image_, x_ + parent_->x(), y_ + parent_->y(), mode_);

		for(auto it = child_.begin(); it != child_.end(); ++it) (*it)->draw(src);
	}

	void setMode(DrawingMode mode){ mode_ = mode; }

	void addElement(const std::string& fileName, const std::string& name, int x = 0, int y = 0){
		ImageElement* image = new ImageElement(fileName, name, this, x, y);
		this->child_.push_back(image);
	}

	void addElement(ImageElement* element){
		element->parent_ = this;
		this->child_.push_back(element);
	}

	void rotate(double angle){
		cv2DRotationMatrix(cvPoint2D32f(imageOrigin_->width / 2, imageOrigin_->height / 2), angle, 1, affineMat_);
		cvWarpAffine(imageOrigin_, image_, affineMat_, 9, CV_RGB(255, 255, 255));
	}

	void translate(double dx, double dy){
		CvPoint2D32f before[] = {cvPoint2D32f(0, 0), cvPoint2D32f(0, 1), cvPoint2D32f(1, 0)};
		CvPoint2D32f after[]  = {cvPoint2D32f(dx, dy), cvPoint2D32f(dx, 1 + dy), cvPoint2D32f(1 + dx, dy)};
		cvGetAffineTransform(before, after, affineMat_);
		cvWarpAffine(imageOrigin_, image_, affineMat_, 9, CV_RGB(255, 255, 255));
	}

	void setROI(const CvRect& rect){
		cvSetImageROI(image_, rect);
		cvSetImageROI(imageOrigin_, rect);
	}

	void resetROI(){
		cvResetImageROI(image_);
		cvResetImageROI(imageOrigin_);
	}

protected:
	DrawingMode mode_;
	_IplImage* image_;
	_IplImage* imageOrigin_;
	CvMat* affineMat_;
	std::vector<ImageElement*> child_;
	ImageElement* parent_;
};

/**
 * アニメーションを行う基本エレメント
 */ 
class AnimationElement : public ImageElement{
public:
	AnimationElement(const std::string& animationImage,int x = 0, int y = 0) : ImageElement(animationImage, x, y){}
	virtual void draw(IplImage* image);
protected:
	virtual void drawAnimation() = 0;
};

/**
 * 連続的に動くアニメーションエレメント．具体的な動作はポリシー・クラスで指定する
 */
template<class AnimationPolicy>
class DynamicAnimationElement : public AnimationElement, public AnimationPolicy{
	class _Holder{
	public:
		virtual double getValue() = 0;
	};

	template<class R, class T>
	class _HolderImpl : public _Holder {
	public:
		typedef R (T::*Func)(void) const;
		_HolderImpl(const T& src, Func func, R min, R max) : src_(src), func_(func), min_(min), max_(max){}
		virtual double getValue(){
			R value = (src_.*func_)();
			return 100.0 * (value - min_) / (max_ - min_);
		}
	private:
		const T& src_;
		Func func_;
		R min_;
		R max_;
	};

public:
	template<class R, class T>
	DynamicAnimationElement(const std::string& animationImage, const T& src, R (T::*func)(void) const, R min, R max)
		: AnimationElement(animationImage, 0, 0) {
			holder_ = new _HolderImpl<R, T>(src, func, min, max);
	}

private:
	virtual void drawAnimation(){
		animate(this, holder_->getValue());//このメソッドはAnimationPolicy側に実装されている
	}
	_Holder* holder_;
};

/**
 * メンバ関数の戻り値が条件を満たした場合に画像を表示するエレメント。
 */
class DynamicImageElement : public ImageElement {
	class _Holder {
	public:
		virtual bool check() = 0;
	};
	template<class T, class Func, class Pred, typename Ref>
	class _GenericHolderImpl : public _Holder{
	public:
		_GenericHolderImpl(const T& src, Func f, Pred p, Ref r) : src_(src), f_(f), p_(p), r_(r){}
		virtual bool check(){
			return (*p_)((src_.*f_)(), r_);
		}
	private:
		const T& src_;
		Func f_;
		Pred p_;
		Ref r_;
	};

	template<class T, class Func>
	class _BoolHolderImpl : public _Holder{
	public:
		_BoolHolderImpl(const T& src, Func f) : src_(src), f_(f){}
		virtual bool check(){
			return (src_.*f_)();
		}
	private:
		const T& src_;
		Func f_;
	};

public:
	DynamicImageElement(const std::string& defaultFileName, int x = 0, int y = 0) : ImageElement(defaultFileName, x, y){}

	template<class T, class Func, class Pred, typename Ref>
	void addElementWithFunctor(const std::string& fileName, const T& src, Func f, Pred pred, Ref ref){
		ImageElement* image = new ImageElement(fileName, this, 0, 0);
		addElement(image);
		holder_.push_back(std::make_pair(new _GenericHolderImpl<T, Func, Pred, Ref>(src, f, pred, ref), image));
	}

	template<class T, class Func>
	void addElementWithFunctor(const std::string& fileName, const T& src, Func f){
		ImageElement* image = new ImageElement(fileName, this, 0, 0);
		addElement(image);
		holder_.push_back(std::make_pair(new _BoolHolderImpl<T, Func>(src, f), image));
	}

	virtual void draw(_IplImage* image){
		auto it = holder_.begin();

		while(it != holder_.end()){
			if((*it).first->check()){
				(*it).second->draw(image);
				return;
			}
			++it;
		}
		ImageElement::draw(image);
	}

private:
	std::vector<std::pair<_Holder*, ImageElement*> > holder_;
};

#endif

あとは，アニメーションの具体的な操作を実装するポリシー・クラスをさっくり書けばＯＫ．

#ifndef ANIMATION_POLICY_H_
#define ANIMATION_POLICY_H_

#include "ImageElement.h"

/** 
 *  ステータス値を画像の回転に変換するアニメーションポリシー。
 */
class RotationPolicy {
public:
	RotationPolicy(){}

	/**
	 * アニメーションのパラメータ設定を行う．
	 *
	 * @param amin  ステータス最小時の，画像の回転角度(deg)．
	 * @param amax  ステータス最大時の，画像の回転角度(deg)．
	 */
	void setRotationParam(int amin = 0, int amax = 180){
		amin_ = amin;
		amax_ = amax;
	}

protected:
	void animate(ImageElement* part, double value){
		part->rotate( amin_ + value * (amax_ - amin_) / 100.0);
	}

private:
	int amin_;
	int amax_;
};

/** 
 *  ステータス値を画像の平行移動に変換するアニメーションポリシー。
 */
class TranslationPolicy {
public:
	TranslationPolicy() {}

	/**
	 * アニメーションのパラメータ設定を行う．
	 *
	 * @param min  ステータス最小時の，画像の左上隅座標．
	 * @param max  ステータス最大時の，画像の左上隅座標．
	 */
	void setTranslationParam(CvPoint2D32f min, CvPoint2D32f max){
		xmin_ = min.x;
		ymin_ = min.y;
		xmax_ = max.x;
		ymax_ = max.y;
	}
protected:
	void animate(ImageElement* part, double value){
		double x = value * (xmax_ - xmin_) / 100.0 + (double)xmin_;
		double y = value * (ymax_ - ymin_) / 100.0 + (double)ymin_;
		part->translate(x, y);
	}

private:
	double xmin_;
	double xmax_;
	double ymin_;
	double ymax_;
};

/**
 * ステータス値を画像のROI移動に変換するアニメーションポリシー．
 */
class ROIMovePolicy {
public:
	ROIMovePolicy() {}

	/**
	 * アニメーションのパラメータ設定を行う．
	 *
	 * @param size ROIの矩形サイズ．
	 * @param min  ステータス最小時の，ROIの左上隅座標．
	 * @param max  ステータス最大時の，ROIの左上隅座標．
	 */
	void setROIParam(CvSize size, CvPoint2D32f min, CvPoint2D32f max){
		size_ = size;
		xmin_ = min.x;
		ymin_ = min.y;
		xmax_ = max.x;
		ymax_ = max.y;
	}

protected:
	void animate(ImageElement* part, double value){
		double x = value * (xmax_ - xmin_) / 100.0 + (double)xmin_;
		double y = value * (ymax_ - ymin_) / 100.0 + (double)ymin_;
		part->resetROI();
		part->setROI(cvRect((int)x, (int)y, size_.width, size_.height));
	}

private:
	double xmin_;
	double xmax_;
	double ymin_;
	double ymax_;
	CvSize size_;
};
#endif

あとは適当な画像を用意してやれば，メンバ関数に応じて回ったり消えたりスライドしたりしてくれるはず．

#include <string>
#include <opencv/cv.h>
#include <opencv/highgui.h>

#include "ImageElement.h"

class Foo {
public:
    int foo() const;
    const std::string& bar() const;
    double buzz() const;
    bool isFOO() const;
private:
    int foo;
    std::string bar;
    double buzz;
};

template<typename T>
bool Greater(const T& x, const T& y){
	return x > y;
}

int main(void){
    Foo f;

    // f.foo()の戻り値に応じて，画像を0〜120度の範囲で回転させる
    auto rotation = new DynamicAnimationElement<RotationPolicy>("triangle.png", f, &Foo::foo, 0, 100);
    rotation.setRotationParam(0, 120);

    // f.buzz()の戻り値に応じて，画像を(0,0)から(200,200)まで平行移動させる
    auto translation = new DynamicAnimationElement<TranslationPolicy>("circle.png", f, &Foo::buzz, 0.0, 1.0);
    translation.setTranslationParam(cvPoint2D32f(0, 0), cvPoint2D32f(200, 200));


    auto indicator = new DynamicImageElement("default.png", 0, 0);
    indicator.addElementWithFunctor("1.png", f, &Foo::buzz, Greater<double>, 0.5); // f.buzz()の戻り値が0.5より大きかったら画像を表示
    indicator.addElementWithFunctor("2.png", f, &Foo::isFoo); // f.isFoo()の戻り値がtrueなら画像を表示
    IplImage* img = cvCreateImage(cvSize(720, 480), 8, 3);
    cvNamedWindow("foo");

    while(1){
        cvWaitKey(10);
        rotation.draw(img);
        translation.draw(img);
        indicator.draw(img);
        cvShowImage("foo", img);
    }
}

最近読んでいる本

メモ

地頭の悪さに呻いてるだけでは始まらないので，きちんと地に足の付いた思考展開をするために．GCJ2011のためでもある．

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

  • 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
  • 出版社/メーカー: 近代科学社
  • 発売日: 2007/03
  • メディア: 単行本
  • 購入: 10人 クリック: 169回
  • この商品を含むブログ (48件) を見る
「C++er名乗ってるのにコレもARMも持ってないとか何なの？死ぬの？」という幻聴に釣られて購入．読み物として凄く面白いけど，直近の業務に何の関係も無いので優先度は低め…．
C++の設計と進化

C++の設計と進化

最近のツボ．本質を突いたアルゴリズムとは何か．要所要所でハッとさせられる．自分は回路を触ったり機械設計やったりコード書いたり器用貧乏的に手を広げているけど，この「本質を突く」という点に関して，機械・電気で多少なりとも出来ていることがプログラミングでは全く出来てないなーと痛感．「中身が空洞の球体を，同質量の密な球体とどう見分けるか？」と言われれば「回転させて慣性モーメントを見る（例えば天井から同じ回数捩った同一材料の糸で釣るし，角速度を観察する）」と即答できるけど，「40億個の32ビット整数から欠けている値をO(n)で見つけるには」と言われると全く頭が動かない．良質なインプットをもっと，もっと．
珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造