how to perform fast normalized cross correlation

Hello, I am trying to apply normalized cross correlation to compute disparity between two images. What is specific to disparity computation is, I just perform a 1-D search, i.e., for a region in reference image, I just apply crosscorr on the same scanline of the query image. This takes approximately 5-5.5 mins for an image of size 375x450 pixels. I am using Matlab R14 SP3, so I know that the latest version include a built-in function for NCC. The normalization I apply is due to a lecture, which subtracts the mean value of the region and divides the result by the sqrt of sum of squared differences of region elements and the mean value. The code I have written is as below:

function disparity = applyNCC(imgL, imgR, kSize, maxDisparity)
imgL = double(rgb2gray(imgL));
imgR = double(rgb2gray(imgR));

[h, w] = size(imgL);
disparity = zeros(h,w);

halfH = floor(kSize(1)/2);
halfW = floor(kSize(2)/2);

%initialize score array with minimum values
%note that corr score cannot be less than -1
score = -5*ones(1,w);

tic

%for each scanline of left image
for i=1+halfH:h-halfH

    fprintf( 1, 'Processing the %dth scanline of left image...\n', i );

    for j=1+halfW:w-halfW

        template = imgL(i-halfH:i+halfH, j-halfW:j+halfW);

        %normalize the template 
        template_norm = normalize(template);

        %search the best match in the corresponding
        %scanline of the right image
        for k=j:-1:max(1+halfW,j-maxDisparity)
            patch = imgR(i-halfH:i+halfH, k-halfW:k+halfW);

            patch_norm = normalize(patch);

            score(k) = sum(sum(template_norm .* patch_norm));
        end

        [match, idx] = max(score);

        %if it is a consistent match, score=1 for perfect match
        if match > 0.8
            disparity(i,j) = abs(j - idx);
        end

%         disparity(i,j) = abs(j - idx);

        %re-initialize score array
        score = -5*ones(1,w);

    end

end

toc

function y = normalize(x)

d = x - mean2(x);   
v = d.^2;
y = d./sqrt(sum(v(:)));

So what is the best option to make this run fast, it would probably run in seconds with some tricks. Maybe the best way is to compute all normalizations and cross correlations beforehand, and save the results appropriately.. Would you offer any code for this? Best regards..

[Walter Roberson]

Consider using a newer version of MATLAB on a newer (faster) computer.

Answer 1

[Walter Roberson]

if match > 0.8 you make an assignment, but after that if you make the identical assignment unconditionally. Either the code is not correct there or else the conditional assignment can be eliminated.

Answer 2

[academy25]

the conditional assignment is not important here, it can be eliminated totally, and instead I can use disparity(i,j) = abs(j - idx); but the most important is how to apply the template matching without using for loops..