特徴点検出器を作ってライブラリに追加した

前々からアニメ顔類似検索のbag of featuresで使っている特徴点の決め方がイラストにあまり合っていない気がしていたけど、実装がすごく面倒くさそうだったのでやらなかった。しかし、最近SURFに特許があることが発覚して、SURFを使っている意味は特にないなーと思ったので、満足のいくものをつくろう思ったのであった。（ただ特許は気にせずにやる）
ということで、こんなのができた(クリックで拡大)。

結構速いし、スケールの変化、回転、ある程度のゆがみには大体対応できている。対応点の決定は、点の特徴ベクトルが一番近い点と二番目に近い点を取って、ふたつの特徴ベクトルの距離の差を確信度として、確信度が高いもののみマッチングしたことにして表示している。
SIFTやSURFに比べると点多すぎだろ（なぜ渦巻きに…）と思うかもしれないけど、これは僕なりにイラストの特性とかbag of featuresで使うことなどを考えた結果こうなった。
Imager::AnimeFaceで使っているオレオレ画像処理アンド機械学習ライブラリ(nv)に入れたので、次回のバージョン（あれば）にはこれが入っている。
今後はこれを使っていこうと思う。

全体の説明はいろいろ面倒なのでライブラリをきちんと公開するときにドキュメントに書く。
ただ自分に分かる程度には、書いとく。
まず基本的には、SIFTなので、SIFTの実装なんてタイピングにすぎないと言える程度に
物体認識のための局所特徴量SIFTと最近のアプローチ(PDF)
と、あとSIFTのソースコードとStar Detectorのソースコードを読んだ。#bigmouth

スケールを決定するためのフィルタはStar Detectorのアイデア

star integral(造語)を使えば、半径に依存しない計算量で画像を畳み込んだ時のフィルタの出力が計算できる。
star integral(造語)とはこんなの。

二つの正方形を重ねた範囲の積分をintegral imageを使って爆速(O(1))で求める。このフィルタで画像を畳み込んだときの出力値になる。
個人的には、こういう２重円をイメージ。

これを大きいのと小さいのを用意して、符号を変える。

重ねるとStar Detectorが使っているフィルタになる。

これをLoGの代わりに使う。SIFTではLoGの近似としてDoGを使っているので、この部分はかなり違う。

スケールアップを細かく行うのとすべての極値を特徴点の候補とする

SIFTやStar Detectorでは、スケールアップを√2倍づつ行っているけど、√4倍づつ行うようにした。
SIFTはスケール空間の最初（小さいほう）の極値、Star Detectorは最後（大きいほう）の極値で特徴点のスケールを決定しているけど、今回のはすべての極値を候補にするようにした。つまり同じ点が複数のスケールを持つことがある。これは、Bag of Featuresで使うことを考えると、複数あるほうが都合がいいと思ったので。

特徴点の決定は、特定スケールにおいての近傍（特徴点の半径から決定）で最大(または最小）の点とする

Star Detectorでは、5x5のマス内においてスケールをまたがって最大（または最小）の出力点を最終的に特徴点としている。
今回のは、スケールごとに最大/最小をとる。これは同じ点が複数のスケールを持つため。
また固定幅のマスではなく、特徴点の半径に比例する半径の円内で最大/最小を選択する。固定にすると、元画像のスケールによって検出される特徴点の位置が変わるだろうと思ったので。
渦巻状になるのはこのため。

エッジ上の点は削除しない

SIFTやStar Detectorでは、エッジ上の点を判定して削除している。これは、例えば一本の線があるとき、局所特徴的にはどこも同じなのでマッチングできないだろJK問題というのがあるためだと思っているけど、イラストはエッジが多いのと、Bag of featuresでもエッジに近い点を使ったほうがいいと思うので、マッチングのことはあまり考えずに消さないことにした。
点が多いのはこのため。

全体的な話として、矩形ではなく円を使う。画素に直接アクセスせずにスケールの半径から求めたサイズのstar integralの出力値を画素の代わりに使う。

計算量は増えそうだけど、ここには謎のこだわりがある。

ある画素を中心とする勾配強度と方向は、X,Y方向(4点)からではなく、点を中心とした円周上の8点(45°づつ）から求める

X,Y方向ごとの強度を求めると、そこから三角関数で勾配強度と方向が求められるので、SIFTではそれを使っているけれど、これは自然画像のように画素値がなだらかに変化していることを前提としている気がするので（ランダムノイズだと45°回転させたときに使われる画素が全く変わるから問題があるだろうとか）、斜めごとにもとって、それを回転させて、X,Y方向にあわせた後の平均をとったほうがイラストみたいな人工的なエッジだらけの画像にはいいだろうと思ったのでこうした。
この計算方法はオリエンテーションと、記述子（特徴点の特徴ベクトル）に使っている。

オリエンテーションの計算は大体SIFT、方向の決定は単に最大値

SIFTは、矩形内の各画素における勾配強度をガウス関数で重み付けしているので円っぽくはある。これを完全に円で行う。
また勾配方向ヒストグラムは、上に書いた方法で勾配強度算出する。
ヒストグラムは36ビンとした。方向は、単にヒストグラムの最大値の方向とした。これは実験的にこれでよかったからこうしたというだけ。