二枚の画像が似ているかどうかを高速に判定するアルゴリズムを探しています。


通常は画素ごとに差分をとって平均二乗誤差やSN比を計算するのが一般的だと思いますが、これだと2乗計算を画素数分行うため計算量が多くなってしまい、比較する画像が複数ある場合だと計算時間が多大に増えてしまうことが問題になります。そこで画像比較の計算時間を削減できるアルゴリズムを探しています。

例えば、文字列処理では正規表現を用いることで高速に文字列探索が行えると聞いたのですが、画像処理の場合にはこのような強力な手法はあるのでしょうか?

一つ画像にモザイクをかけて比較する画素数を減らして計算時間を削減する手法を行ったのですが、これだと計算時間は削減されるものの比較精度が落ちることが問題でした。あまり精度を落とすことはできません。

私は現在大学生でして、ある自作のソフトウェアを作成している所なのですが、上記の問題のため先に進むのが困難になっています。まだまだ勉強不足なため、ちょっとしたアドバイスから広く回答をいただきたいと思っていますので、どうぞよろしくお願いいたします。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/07/29 23:31:18
  • 終了:2006/07/31 00:07:21

回答(5件)

id:Z9M9Z No.1

Z9M9Z回答回数343ベストアンサー獲得回数112006/07/29 23:39:23

ポイント30pt

普通、精度も速度もほしいときは、ぼかしたものでざっとフィルタリングしてから本番比較、のような2段階法を用います。

位置合わせの問題さえなければ、「ぼかす」のバリエーションとして、「四分木」に代表されるような画像用インデクスを用いるのも一般的と思います。

http://chiyo.sfc.keio.ac.jp/cgsoft/Release/Textbook/expression08...

id:grapalm

どうもありがとうございます。

「四分木」は名前は聞いたことありましたが画像表現にも使えることは知りませんでした。

これは、画像の平坦部分はざっと比較して変化の激しい部分は細かく比較する、といった感じでしょうか。

プログラムで書く場合はどうなるのでしょう。

まず二枚の画像をそれぞれ四分割し、領域ごとにRGBそれぞれの平均値を比較する。その比較誤差がある閾値以上だったら領域をさらに四分割し再帰的に処理を行う。といった流れでしょうか。間違っていたら指摘してもらえると嬉しいです。

一度チャレンジしてみます。参考になります。ありがとうございました。

その他にも何かアルゴリズムがありましたら教えてもらいたいので、よろしくお願いいたします。

2006/07/30 00:31:23
id:jyouseki No.2

jyouseki回答回数5251ベストアンサー獲得回数382006/07/30 00:08:15

ポイント20pt

http://www.oishi.info.waseda.ac.jp/~aguchi/thesis/1g00p084.pdf

このような物体の輪郭を縁取るようなアルゴリズムを用いた方が、モザイクをかけるよりは精度が上がるのではないでしょうか。

id:grapalm

どうもありがとうございます。

これは、画像を「点」で記憶するのではなく「線」で記憶する、ということでしょうか。

僕のCGの知識が皆無なため理解が間違ってるかもしれないのですが、「線」で表現した後に二枚の画像を比較することもできるのでしょうか。

点の比較は単純に差分を取れば可能ですが、線の比較はどうなるんだろう。多項式の係数を比較するのでしょうか。

確かに画像を数式で表現できれば比較回数が減らせそうな気がします。

もう少しこの分野を勉強しないと分からない部分があるので頑張ってみます。理解が間違ってたらすいません。

どうもありがとうございました。

2006/07/30 01:20:10
id:kurukuru-neko No.3

kurukuru-neko回答回数1844ベストアンサー獲得回数1552006/07/30 00:09:09

ポイント30pt

もしカラーで処理しているのであれば、

モノ変更しましょう。

http://www.gsi.go.jp/WNEW/LATEST/USU/sar/matching.htm

画像のパターンマッチングをしたいのかな

と思います。

Yahooなどで 画像 マッチング

等で検索するとたくさん方法が出てきます。

たとえば、ある画像の中に特定の図形を探しだす場合と

顔の写真の類似を探す場合ではまったくアプローチが

必要です。

たとえば顔やモノの輪郭抽出を最初にして

輪郭の図形の相関関係が高いものを似ていると判定する

方法があると思います。

http://www.brain.kyutech.ac.jp/~morie/Topics/face-recog.html

指紋とか限定されれば以下のような

実装方法を公開している会社もあります。

http://www.dds.co.jp/fv/algorithm.html


id:grapalm

どうもありがとうございます。

この、特徴量を抽出して比較する、というのは参考になります。

ただ、僕の質問の仕方が悪くてすいません。

質問で"二枚の画像が似ているかどうか"と書いたのは、"特定の物体があるかどうか"という意味ではなく、

"輝度や色相など画像全体として似ているかどうか"、という意味です。特に何が写っているかは意識しません。

ある正解画像を用意し、評価画像が正解画像と全く同一(または限りなく同一に近い)かどうかを判定したいのです。

よって色相情報も必要になります。

でも、このマッチングの技術というのは興味があります。

画像の特徴量を比較するとどこまで画像全体として精度が出せるのか。

もう少し勉強してみたいと思います。どうもありがとうございました。

2006/07/30 02:13:02
id:kurukuru-neko No.4

kurukuru-neko回答回数1844ベストアンサー獲得回数1552006/07/30 02:41:39

前の回答誤字脱字多数ありすいません。

実現できれおそらく最高の方法

量子コンピューティング画像認識

http://www.kagawa-u.ac.jp/ccrd/kenkyu/images/hattori/02.pdf

>ある正解画像を用意し、評価画像が正解画像と

図形のずれを無視するなら相関を計算するだけの

ような気がする。

 

 http://www.neurosci.aist.go.jp/~kurita/lecture/statimage/

 http://www.kansai-u.ac.jp/Fc_eng/kyomu/cyllabus/data/160880550.h...

 Yahoo検索 画像 相関係数

id:grapalm

再びどうもありがとうございます。

知らない用語が沢山出てきたので勉強になります。

ただ、自宅のPCで行ってるので量子コンピュータはできません。

統計的画像処理というのが色々研究されてるようなので勉強してみます。

一つ疑問点は、画像の相関を評価する手法は、画素ごとの差分を評価する手法よりも"高速"かつ"精度が良い"かということです。

色々教えていただき道が広がりました。

もう少し勉強してみたいと思います。ありがとうございます。

2006/07/30 23:42:37
id:quintia No.5

quintia回答回数562ベストアンサー獲得回数712006/07/30 23:07:48

ポイント30pt

特徴量や画像類似度の定義に関しては色んな考え方があるわけですが、

http://www.google.co.jp/search?q=site:ac.jp+%E9%A1%9E%E4%BC%BC%E...

こんなgoogleでの検索で色々と見て回れると思います。


その検索結果の中に

http://gemini.mis.ous.ac.jp/Rejume/2005/sim.pdf

こんな論文がありました。

画像を3x3の9分割して、それぞれの領域の「代表色」を特徴量にして検索するものです。

9分割でも検索の上位の結果は、人間からみても十分に似ている画像を選び出してきています。

たった9分割と思われるかもしれませんが、それでも特徴量が9次元のベクトルになります。あまりに分割数を大きくしても今度はいわゆる「次元の呪い」という問題にぶちあたるわけで、1段階目の比較としては十分なのではと思いました。 (1.の回答にある通りまずいったん粗く検索して、得られた上位の画像について本比較をするわけです)


「代表色」の決定だけを考えても、「RGBを使うか、HSVを使うか、HSVを使ってHの重みを大きくとるか」とか、「単純に平均して代表色にするとか、色空間を分割して一番画素数の多い領域を代表色にする」とか、色々ありそうです。

検索対象の画像群が何なのかも加味して考えるべきでしょうし。


余談(次元の呪いの検索結果)↓

http://www.google.co.jp/search?hl=ja&q=%E6%AC%A1%E5%85%83%E3...

id:grapalm

どうもありがとうございます。

画像検索の技術にかなり興味が湧いてきました。

もっと論文なり特許なり読んで色々試してみたいと思います。

積極的な研究対象のようなので面白そうですね。

今回の質問で色々勉強になりました。

これでとにかく先に進めそうです。

回答をしていただいた皆様、どうもありがとうございました。

2006/07/31 00:00:13

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません