http://d.hatena.ne.jp/ruby-U/20110215/1297757430 で、画像に変形を加えて局所特徴量の性能を調べたので、次はハッシングの性能を調べる。
類似画像検索の枠組みは
まず、前準備として
- 画像から特徴点を抽出し、それぞれを
bitのバイナリハッシュに変換し、DBに格納しておく。
そして検索は、
- 指定の画像から特徴点を抽出し、
この問い合わせの対象になるバイナリハッシュの数は、例えばなら、ハミング距離0で
個、ハミング距離1以内で
個、ハミング距離2以内で
個、ハミング距離3以内で
個…と増えていく。これが一つの特徴点ごとであることを考えれば、広いハミング半径を問い合わせの対象にすることは、できるなら避けたい。
このような制約から、画像検索の良いパフォーマンスのためには、ハッシングをよくチューニングする必要がある。このための指標として、
- 無関係の画像ペアから抽出した最近傍特徴点
- 近似した画像ペアから抽出した最近傍特徴点
を使うことを考えた。
両者をハッシュ化し、クエリの対象とするハミング距離0、1など、比較的近い位置に、後者のみがうまく入るようにすればいい。
異なる画像同士の特徴点の距離はもっと遠くまで広がっているが、問題設定から最近傍のみに注目している。
実験
- 無関係の画像ペア
- ある画像と、それに変形（5%の拡大）を加えた画像のペア
それぞれから抽出した、特徴点ごとの最近傍点を、前者はDB全体での最近傍のサンプルとして、後者は近似した場合での最近傍のサンプルとして用いた。
以前と同様に、
def min_dist(feature, features): #特徴点featureとfeaturesの中の全てを比較して、最小距離を返す。 #最小値0。
を使って、画像ペアについて、最近傍の特徴点を選び、いくつかのハッシングビット数ごとに、そのユークリッド距離とハミング距離をプロットした。
結果
14 bit
14 bitでは非近似の点がハミング距離0、1に被っていて不適。
20 bit
20 bitもやや被っている。
28 bit
28 bitでは被っていないが、ハミング距離0の近似の点の数が20 bitよりも少ない。
以上
実際のクエリの結果からのフィードバックは必要だが、ハッシングビット数決定の大雑把な見積もり方法としては使えそうだ。
