[最適化]ゼロ正規化相互相関：パターンマッチング

Question

お世話になります。
C++で、パターンマッチングを行っています。
その際、下記のサイトを参考にしたのですが、ZNCCの1パスでの方法ができずに困っています。

参考：
http://imagingsolution.blog107.fc2.com/blog-entry-186.html

この処理の外側には、参照画像を検索していくループがあります。
最適化する前の式はコードへ起こし、マッチングさせることが出来たのですが、
最適化の式をソースコードに変換してから、マッチングする値が、最適化する前の値と違うようになってしまいました。

変更したのは、下記のコード部分で、最適化の式をそのままソースコードにしたつもりです。値が違うのは、私のソースコードへの変換が間違っているのか、そもそも、私の認識違いで最適化した式だけでは、計算が出来ないのかだと考えているのですが、どちらか判断が出来ませんので、ご助言をお願い致します。

CENTER_X : テンプレートのX軸サイズ
CENTER_Y : テンプレートのY軸サイズ
Temp[][] : テンプレート画像
Point[][]: 参照画像

double zucc_1 = 0.0;
double zucc_2 = 0.0;
double zucc_3 = 0.0;
double zucc_4 = 0.0;
double zucc_5 = 0.0;
double zucc_6 = 0.0;
double zucc_7 = 0.0;

for(j=0; j<CENTER_Y; j++)				// パターンマッチ計算.
{
	for(i=0; i<CENTER_X; i++) 
	{
		zucc_1 += Temp[j][i] * Point[j][i];
		zucc_2 += Temp[j][i];
		zucc_3 += Point[j][i];
		zucc_4 += Temp[j][i] * Temp[j][i];
		zucc_5 += Temp[j][i] * Temp[j][i];
		zucc_6 += Point[j][i] * Point[j][i];
		zucc_7 += Point[j][i] * Point[j][i];
	}
}

// 計算
match =  ( (CENTER_Y * CENTER_X * zucc_1) - (zucc_2 * zucc_3) ) / 
	sqrt( ((CENTER_Y * CENTER_X * zucc_4) - (zucc_5)) * ((CENTER_Y * CENTER_X * zucc_6) - zucc_7) );

よろしくお願いいたします。

Comments

[TEC_S]

大変失礼しました。質問の内容について、再度見直し、修正させていただきました。

Answer 1

こんにちは。

まず、参照画像Point[][]はCENTER_X, CENTER_Yより大きな画像ですね？
そして、その画像の中で最もTemplate[][]とマッチする位置を探すことになります。

そのためにはpoint[y][x]を起点とする画像とTemplate[][]を比較するために、各式のPoint[j][i]はPoint[y+j][x+i]となります。
そして、このx, yを参照画像サイズからテンプレート画像サイズを引いたサイズでスキャンし、各々のmatchを計算して最大となるmatchの時のx, yがテンプレートが最もよくマッチした位置となります。

この計算をする時、zucc_nの中にx, yと無関係な値（Point[j][i]を使っていないもの）がありますね。
それらはx, yをスキャンする前に一度計算しておけば再計算しなくて済むということです。

ゼロ平均正規化相互相関には、x, yスキャンも含めたソースが記載されてます。
なぜリンク先が「１パスで済む」と表現しているのかよく分かりませんが、単に言葉の選び方をミスっただけではないでしょうか？ 言いたいことは「計算量を減らせる」だと思います。

Comments

[TEC_S]

記載内容が足りず、ご指摘を受けている質問にも関わらず、ご回答を頂きありがとうございます。（質問内容を一部変更させていただきます。）

仰っている通りで、Point[][]とマッチさせる処理が、記載させて頂いたコードの外側にあります。実際のPoint画像と、テンプレートを比較していき、最大となるものを取得してマッチングさせるのが狙いです。

1パスで済む・・・と表現されているのもあり、式を展開して行けば、Σの2重ループ1回で、計算を行い、後で計算結果を組み合わせることで、ループの回数が激減すると思い、コードを作成しました。

私が自信が無かったのが、式の展開に関してで、最適化する前と、matchの値が違うのは展開の仕方（ソースコードへの変換）がおかしいのか、そもそもやろうとしている事が間違っているのか、判断に困ったためです。

最適化した式の理解としては、あっているのでしょうか？？

[Chironian]

zucc_5とzucc_７が間違っているようです。()の範囲を見間違ってます。
リンク先の式は下記と思います。（私自身も何か見落としている可能性ありますが。）

zucc_5 += Temp[j][i];
zucc_7 += Point[j][i];

　　：

match = ( (CENTER_Y * CENTER_X * zucc_1) - (zucc_2 * zucc_3) ) /
sqrt( ((CENTER_Y * CENTER_X * zucc_4) - (zucc_5*zucc_5)) * ((CENTER_Y * CENTER_X * zucc_6) - (zucc_7*zucc_7)) );

[Chironian]

あ、そうそう、最適化しても4重ループという構造は変わらないですよ。

[TEC_S]

ご返信、ありがとうございます。
ご連絡が遅くなり、申し訳ありません。

4重ループは、この処理の外側の探索のループという事ですね。
承知しました。ありがとうございます。

修正して、ご連絡させて頂きます。

[TEC_S]

ご連絡が遅くなり、申し訳ありません。
ご指摘いただいた点を修正しても、改善しませんでした。

ZNCCにて調べたところ、下記サイトが出てきており、どうやら考え方自体が違っていたのだと、分かりました。4重ループの意味も、自分の勘違いで、やはり1回計算しておかなければ駄目だということで、落ち着きそうです。

http://navi.cs.kumamoto-u.ac.jp/~koutaki/pukiwiki/index.php?%A5%BC%A5%ED%CA%BF%B6%D1%C0%B5%B5%AC%B2%BD%C1%EA%B8%DF%C1%EA%B4%D8

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