画像の位置の検索

質問

ある大きな白黒の画像と、その一部である小さな画像（大きな画像から抜き出した画像です）があるんですけども、
その小さな画像が大きな画像のどの位置に当てはまるか、ということを検索しようとした場合、どのようなアルゴリズムを使うのがよいでしょうか？（小さな画像は0、90、180、270、で回転してる場合があります）

回答No.2

liar_adan

>もう少し高速にはならないのかなぁ…。

その画像が、グレースケールなら、バイト列検索に
ボイヤー・ムーア法を使うとか、
2値画像なら、ラビン・カープ法を使うとかすれば
少しは速くなる可能性があります。
一ケタまでは違わないと思うけど…。

これらのアルゴリズムに対しては、さすがに解説できない(スペース的に)ので、
下記の本などを参考にしてください。

参考URL：

http://www.amazon.co.jp/exec/obidos/ASIN/4764902222/,http://www.amazon.co.jp/exec/obidos/ASIN/4764902567/

お礼

扱う画像は2値画像です。
ですので、ラビンカープ法というのを、調べさせてもらおうと思います。

参考書名、どうもです。
（図書館に置いてあったような気がするので、ちょっと読んでみようと思います）

情報ありがとうございました。

回答No.1

liar_adan

私ならこうします。

1)大きな画像を、横方向はバイト列、それを縦方向に配列として並べた「バイト列の配列」としておく。
2)小さな画像も同様。
3)小さな画像を90、180、270回転させた画像も作る。
4)4種類の小さな画像の、上の一ラインだけを取り出す。
5)大きな画像の各ラインから、(4)のラインをサーチする。
6)サーチして一致するところがあれば、その位置で小さな画像全体が一致するか確かめる。違ってたら(5)にもどる。

お礼

回答ありがとうございます。

なるほど、一ラインだけ取り出す…ですか。
先ほど、教えていただいたやり方で、プログラムを組んでみました。
でも、画像が大きくなってくると、結構時間がかかってきてしまいますね。
もう少し高速にはならないのかなぁ…。

とりあえず、ありがとうございました。