✨Template Matching

Here we deal with template matching using cross-correlation. Assume we have a 2-D template T(x,y) and a subimage I(x,y) in an image.

The cross-correlation r between T and I can be defined as $r=\frac{1}{n}\sum_{x,y}\frac{1}{\sigma_T\sigma_I}(I(x,y)-\mu_I)(T(x,y)-\mu_T)$, where n is the number of pixels in T(x,y) and I(x,y), $\mu_I$is the average of I and $\sigma_I$is standard deviation of I. Thus, we have $|r|\leq1$.

r larger, then the template and a chosen subimage is more similar; r smaller, then the template and a chosen subimage is less similar.

In this code snippet, I implement the template matching algorithm and blank out the part that matches the most in the output image to show the result.

% parameters- 
% image: the large image that we want to find the region that is similar to template
% template: the 2-D template T(x,y)
% width: the width of template
% height: the heigh of template
% returns-
% newmap: the heatmap that shows each pixel's template matching correlation coefficient
% new: the new image that blank out the most correlated region inside image
function [newmap,new]=templateMatch(image,template,width,height)
    newmap=zeros(size(image,1),size(image,2));
    loc_x=-1;
    loc_y=-1;
    % loop through each pixel inside image
    for i=1:size(image,1)-width
        for j=1:size(image,2)-height
            % slice the down-right region from image(i,j) that has 
            % the same width and height as template, then to calculate the correlation
            sliceT=image(i:i+width-1,j:j+height-1);
            sliceI=template;
            miuT=mean(sliceT,'all');
            miuI=mean(sliceI,'all');
            sigmaT=std(sliceT,0,'all');
            sigmaI=std(sliceI,0,'all');
            total=0;
            for a=1:size(sliceT,1)
                for b=1:size(sliceT,2)
                    total=total+(sliceT(a,b)-miuT)*(sliceI(a,b)-miuI)/(sigmaT*sigmaI);
                end
            end
            r=total/(size(sliceT,1)*size(sliceT,2));
            newmap(i,j)=r;
            % find the pixel with maximum matching correlation coefficient
            if r==max(max(newmap))
               loc_x=i;
               loc_y=j;
            end
        end
    end
    newmap(isnan(newmap))=0;
    new=image;
    % blank out the most matched region inside origin image to illustrate the result
    new(loc_x:loc_x+width-1,loc_y:loc_y+height-1)=0;
    return 
end

Results:

up-left: image; up-right: template; down-left: cross correlation result heatmap; down-right: image that blank out the template

As we can see, the brightest pixel in down-left image is the place where we have the highest cross-correlation result (r). We successfully find the name tag UW inside the original image and blank it out.