テンプレートマッチングのコードが重すぎる、MATLAB

Question

前提・実現したいこと

学生です。現在MATLABを用いて、テンプレートマッチングの勉強をしています。
自分なりに計算方法SSDをコードで書いてみたのですが
いざ画像でやろうとすると、重くてコンパイルが終わりません。

発生している問題・エラーメッセージ

エラーなし

該当のソースコード

function [min,zahyou] = patamati(a,b)

sizeA = size(a);   sizeB = size(b);
if(sizeB(1,1)*sizeB(1,2) > sizeA(1,1)*sizeA(1,2))   
    nige = a;   a = b;   b = nige;
end   %入力の順番自由

sizeA = size(a);   sizeB = size(b);
x = 0;   wa = zeros;   min = 256^2 * sizeB(1,1) * sizeB(1,2);   %minの初期値は8bit最大

for k = 0:(sizeA(1,1)-sizeB(1,1))
    for l = 0:(sizeA(1,2)-sizeB(1,2))
        x = x + 1;   wa(x) = 0;
       
        for i = 1:sizeB(1,1)
            for j = 1:sizeB(1,2)
                wa(x) = wa(x) + (a(i+k,j+l) - b(i,j))^2;   %差の二乗を加算
            end
        end
        if(wa(x) < min)
            min = wa(x);   zahyou = [k+1,l+1];   %zahyouはマッチしたときの左上の座標
        end
    end
end
min = min / (sizeB(1,1)*sizeB(1,2));   %1ピクセル当たりの差
end

試したこと

①グレスケ画像（画像は4032×3024、テンプレートは904×383）
②バイナリ画像（サイズは同上）
③4×6のランダムな数値の行列と3×3のテンプレート

結果は③のみ出来ました。バイナリ画像でもできないのはおかしいと思い
質問させていただきました。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

MATLABはインタプリタでコンパイルはしないので、単に実行に時間がかかる意味だと解釈します。

これは、さすがにループの繰り返し回数が多いのではないでしょうか。
画像は4032×3024、テンプレートは904×383でどれくらい計算が繰り返されるかを求めてみます。

まず、テンプレート一つ分の計算は904383=346232、つまりおよそ35万回の計算が行われます。これを(4032-904+1)(302-383+1)=8266818、つまりおよそ800万回繰り返します。つまり、全体でおよそ2.86e+12、つまり3兆回弱の計算が行われることになります。MATLABのforループは遅いので、3兆回も回していたら、何日もかかるでしょう。

基本的にはforループを使わないようにして、行列計算を行うようにします。たとえば、内側のiとjを使ったループは、こんな風に消せます。

for k = 0:(sizeA(1,1)-sizeB(1,1))
    for l = 0:(sizeA(1,2)-sizeB(1,2))
        wa = (a((k+1):(k+sizeB(1,1)), (l+1):(l+sizeB(1,2))) - b) .^ 2;
        wa = sum(wa(:));
        if(wa < min)
            min = wa;   zahyou = [k+1,l+1];   %zahyouはマッチしたときの左上の座標
        end
    end
end

これだけで20から30倍は速くなると思いますが、外側の繰り返しが800万回もあるので、これでも数時間単位で時間がかかると思います。

外側のループの消したかったのですが、うまい方法が思いつきませんでした。計算方法を工夫するところから考えないといけないかもしれません。

Comments

[akaz]

回答ありがとうございます！
確かにうちのPCに3兆回の計算とは、酷なことをさせていました。

なるほど、もっとMATLABの演算方法を確認してみたいと思います。
それから画像サイズももっと小さくしてみます。

仮に画像サイズを1/10にしたとしても実行には数十分ほどかかってしまいそうですが、
テンプレートマッチングというのはそういうものなのでしょうか...

[akaz]

画像サイズ1/5にしただけでも、実行に30秒かからなかったので
とりあえずはこのままやってみようと思います。
改めて、ありがとうございました。