Search code examples
matlabtemplatesimage-processingtemplate-matching

Matching object outer shape using normalized cross correlation

I am working with normxcorr2 function in Matlab for template matching. However, what I want to do is different from what normxcorr2 does. The built-in normxcorr2 computes cross-correlation taking into account all the pixels in a rectangular template. But I only want certain pixels to participate in the normalized cross correlation process.

For example, I want only the ring-like white region in the following image to be used as a template while correlating. (the black region inside should not be used for computation)

enter image description here

And thus if I correlate the above template with the following image, I am likely to get a normalized value of around 1.0 (considering the outer circles are of same diameter in both images)

enter image description here

I have checked out this solution:- matlab template matching only for 0 (or 1) in matrix but it is not generic.

Can anybody help me with a more general solution in matlab? This can be used to track objects by their outer shapes

EDIT:- This is the entire image for those who want to have a look at it. I want to detect the ball only by the outer circular rim, not the inner details.

enter image description here

Solution

  • Ok, let's give it a try... This solution tries to use existing normxcorr2 implementation and modify it to solve yoru problem.

    The formula for normalized cross correlation is:

    enter image description here

    In this case you want to change the integration boundaries for every window. This is turn affects both standard deviations and the correlation itself. Lets tackle it in several steps:

    Step #1: Get the correlation right

    We can do this by modifying the template image:

    template_fix = template;
mean_template_mask = mean(template(mask == 1));
template_fix(mask == 0) = mean_template_mask;
result = normxcorr2(template_fix, query)

    Notice that by making this change we make the mean value of the template to be equal to the mean value of the template in side the mask. this way all template pixels outside the mask don't contribute to the integration as they are equal to the mean value.

    Step #2: Fix template std

    size_mask = sum(mask(:));
size_template = numel(template);
std_template = std2(template);
std_template_masked = sqrt(sum((template_fix(:) - mean_template_mask).^2)/size_mask);
result = result * (std_template/std_template_masked);

    Step #3: Fix query std

    sum_filt = ones(size(template));
std_query = filter2(query.^2, sum_filt) - filter2(query, sum_filt).^2/size_template;
std_query = sqrt(std_query/size_template);

std_query_mask = filter2(query.^2, mask) - filter2(query, mask).^2/size_mask;    
std_query_mask = sqrt(std_query_mask/size_mask);

result = result .* std_query ./ std_query_mask;

    My Matlab is not responding so I didn't have the chance to test it in practice. Unless I missed some errors it should be mathematically equivalent.

    This solution does some extra convolutions but it doesn't process overlapping pixels more than once.

    If you use the same template image multiple times then you could refactor steps 1 & 2 to run only once for preprocessing. Although both shouldn't be computationally expensive.

    Different approach: Straight forward

    Here is a different, straightforward approach that doesn't use the original normxcorr2 function. This code can be easily optimized for memory usage in expense of readability.

    enter image description here

    enter image description here

    % q for query, t for template and mask for mask
% shape = 'full' or 'same' or 'valid'

t_mask = t .* mask;
n      = numel(mask);
tq_sum = filter2(t_mask,q, shape);

q_sum  = filter2(mask, q, shape);    
q_mean = q_sum/n;
t_sum  = sum(t_mask(:));
t_mean = t_sum/n;

res1 = tq_sum - t_mean*q_sum - t_sum*q_mean + t_mean*q_mean*n;

t_std = sqrt((sum(t_mask(:).^2) - sum(t_mask(:)).^2/n)/n);
q_std = sqrt((filter2(mask, q.^2, shape) - q_sum.^2/n)/n);

res = res1 ./ (n * t_std * q_std)