いまさら正規相関

　ここ数年、パターンマッチングで作った画像認識でマーク検索を行ってきましたが、 ここへ来て世間では「丸いマーク」が再び出てきました。（うちの周りだけかもしれませんが） 「角」を特徴点とする、うちのマークサーチは、丸いマークにとっても弱く、以前作った無理やり丸の特徴点で何とか対応しておりましたが、認識できないケースも出てきたので、時代に逆行するようですが正規化相関に取り組みます。

正規化相関と呼ばれるモノ

　正規化相関。世間ではそう呼ばれているらしいのですが、まあ力技サーチですよね。言葉からは、何らかの方法で正規化し、つまり、明るさやコントラストの影響を受けないように加工しておいてから、相関関係（似てる度合い）を比べましょうということなんでしょう。
　この仕組みでは画素と画素を比較するために、回転してたり、拡大縮小してたりするパターンは認識できません。部分欠落はうまく作れば実装できるかもしれません。

４重ループ地獄

　ちょっと考えると、恐ろしいコトに気づきます。例えば、カメラで撮影した画像が６４０ドットｘ４８０ドット、探し出したいお手本となる画像（マーク）が５０ドット×５０ドットだったとします。 すると、６４０ｘ４８０の範囲のどこかに、５０ｘ５０ドットの窓を重ねて、「似てる度合い」を計算することになります。すると、内側のループに５０ｘ５０が必要になり、この窓を全位置動かして確認するために、５９０×４３０のループが必要になり、都合４重ループになります。

for (y1 = 0;y1 < 480 - 50;y1++)
	{
	for (x1 = 0;x1 < 640 - 50;x1++)
		{
		dlt = 0;
		for (y2 = 0;y2 < 50;y2++)
			{
			for (x2 = 0;x2 < 50;x2++)
				{
				dlt1 = image[x1+x2][y1+y2] - mark[x2][y2];
				if (dlt1 < 0) dlt1 = -dlt1;
				dlt += dlt1;
				}
			}
		if (min > dlt)
			{
			min = dlt; rx = x1; ry= y1;
			}
		}
	}

　これが、恐ろしい時間がかかる処理であることは簡単にイメージできると思います。 上の例では、430*590*50*50=634,250,000となり、一番内側のループ内は６億３０００万回以上!!実行されることになります。カメラが１３０万画素になったり、２００万画素になったときのことは考えたくないほどの回数です。 まあ、最近のＣＰＵにとっては大した作業ではないのかもしれませんが、ここでは如何に手を抜き、少ない演算回数で目的の答えを出すか考えます。

計算回数を減らす（１）縮小画像

　すぐに思いつくのが、元の画像もマーク画像もデカい。これを小さくして「ある程度」の場所を探してからサーチすれば良いという方法だと思います。画素数を４分の１にすればつまり６４０×４８０の画像を１６０×１２０の画像にしてサーチしても、数ドットｘ数ドットくらいの範囲は特定できるんじゃないかというプランです。
　ただ、マークのほうは予め計算できるのですが、大きい方の画像は、一般的な工業用途だと、画像取り込み直後にパターンマッチングを行うため、この縮小画像を作るというコストがかかってきます。４×４を１ｘ１に縮小するケースなら、割り算が/16になるため、シフトですみますが、準備にある程度のコストがかかってしまうため、今のところ採用していません。今後速度アップを求めるときのためにとっておくことにします。

計算回数を減らす（２）マーク内の価値が高い位置優先

　次に考えたのが、マーク内側のループ回数を減らすことです。上の例では、５０×５０で２５００回ループになってますが、これを５０回くらいに減らせば、６億の総ループ数も９８％ダウンの１２００万回くらいになるなあということです。 マーク内には、エッジになっている特徴的な部分もあれば、隅っこで、コントラストもなく佇んでいるだけのドットも存在します。まあ、エッジのない部分同士を比較することも、平坦な状態が互いに存在するということで無駄ではないのですが、エッジ部分を比較することに比べて価値の低い作業でありましょう。そこで、微分してエッジを計算し、この絶対値の大きい順に上から２％とか場合によってはもっと少ない数だけ比較して相関を調べることにしましょう。
　ついでに、これは（１）の時でも使える方法ですが、一旦、誤差最少の候補が見つかった場合、計算途中でその誤差を超えた場合、トータルで誤差が最少になることはありえないので、計算を打ち切ることができます。これも組み込み検証してみます。