画像一致判定のアルゴリズム

質問

【やりたいこと】
２枚のデジカメなどで撮った画像を自動で合成したいのです。
その２枚は少し(数十ピクセル)左右上下にずれた画像で、最終的にはその２枚を平均化するなどして合成したい。
問題は、その２枚の画像がどの方向に何ピクセルずれているかを求めなければならないのです。
とりあえず１ピクセルずらしながら、差分を合計しその差分が最小となるずれを見つけるようにプログラムしましたが実用的な速度になりません。
【質問したいこと】
２枚の画像のずれを高速に求めるアルゴリズムはありませんでしょうか。
精度はあまり良くなくても構いません。ある程度絞り込めればその付近を１ピクセル調べる方法をとります。

回答No.1

aton · ベストアンサー

「ある程度絞り込めれば」良いのであれば，まず2*2ピクセルとか，3*3ピクセルとか，4*4ピクセルとかの範囲で画像を平均化して，その平均化した画像に対して縦横に2 , 3 , 4ピクセルずつ動かして，差分を計算してみてはどうでしょうか？

平均を計算するのが面倒なら，画像を縦横1/2 or 1/3 or 1/4 に縮小し，その縮小画像に対して1ピクセルずつ調べる方法を適用すれば平均化するのと同じ効果が得られますから，それで大よその位置を絞り込み，次に元のサイズの画像に戻って，さっき求めた位置（座標を元に戻すことをお忘れなく）から同様に1ピクセルずらしを行えば，計算時間が短縮できるのではないでしょうか。

お礼

縦横それぞれ1/nにすれば単純計算で時間は1/n^2になるので、十数倍～数十倍の高速化が期待できるかもしれません。問題なく使えるｎがどこまでかはやってみるしかわかりませんが。
その他のアイデアも待ちたいところですが、質問が一気に下がってしまったようなので、一旦締めます。試してみた後、問題あるようなら改めて質問しますのでその際はよろしくお願いします。
ありがとうございました。