How do we computer SSD (Sum of Squared Differences)

Hello!

I am having two images f and g, where g contains a block which is also present in a. How can detect the block in a using SSd? How is SSD computed. Please help!

[Matt J]

What is "a"? You mean present in "f". Are f and g the same size, or is one of them a template of the block you're searching for?

[Emmanuel]

Sorry! my bad..Its actually "f". g contains the template of f and hence g is smaller than f

[nikhil kumar]

Refer to this link http://www.cs.toronto.edu/~guerzhoy/320/lec/patches_filters.pdf

Answer 1

[Matt J]

If g is a template of the block you're searching for, the minimum SSD match is equivalent to the maximum non-normalized correlation match,

correlation=conv2(f,rot90(g,2),'same');
[i,j]=find(correlation=max(correlation(:)));

[Image Analyst]

I'm not sure I follow. Though they may find the same location using different algorithms (subtraction vs. multiplication), the convolution or correlation of an image is not guaranteed to produce a maximum where the template aligns with its counterpart in the larger image. I can make a demo to show that if anyone wants.

[Matt J]

Hmmm. Okay, I think I mis-recalled the derivation, but what if we correct for the norm-squared of the data block,

fEnergy=conv2(f.^2,ones(size(g))/2,'same');
correlation=conv2(f,rot90(g,2),'same');

metric=correlation-fEnergy;

[i,j]=find(metric=max(metric(:)));

[Image Analyst]

Honestly I thought that too until late in grad school my prof told me that it was not the case though it's a common misperception. Kind of like how he showed me that plugging data the equation of a line m*x+b is not a linear transform . Kind of non-intuitive and surprising and not what you always assumed, but once you see it explained you slap your forehead and say "Oh, of course!"

I'm not sure I follow your equations. The first one is basically a blurred version of the square of the image. Then you subtract that from the image convolved with a rotated version of template. I'm not following how that's the same as the sum of squared differences, which honestly I've never heard of or seen, and the only reference to it I see of in Wikipedia on the more common Sum Of Absolute Differences page actually redirects you to something with a totally different name http://en.wikipedia.org/wiki/Squared_deviations

[Matt J]

Let f_ij be the sub-block of f located at coordinate (i,j). We consider blocks the same size as the template g. The SSD search criterion is to find the sub-block f_ij minimizing the squared difference with g

    min_ij  0.5*norm(f_ij(:)-g(:))^2

Expanding the norm gives the equivalent

    min_ij  0.5*norm(f_ij(:))^2 -dot(f_ij(:),g(:)) + 0.5*norm(g(:))^2

The final term is constant and can be ignored. Negating the remaining terms, this is equivalent to the maximization,

     max_ij  dot(f_ij(:),g(:)) - 0.5*norm(f_ij(:))^2

The first term can be computed for all (i,j) and organized as an image by taking the cross-correlation of f with g. The cross-correlation is likewise, the convolution of f with a rotated version of g.

The second term can likewise be obtained as the convolution

   fEnergy=conv2(f.^2,ones(size(g))/2,'same');

All of this is just to say that an SSD search can be broken down into a series of convolutions/correlations... It's of questionable usefulness of course, and would often be outperformed by normalized cross-correlation, except when your template is very accurate.

[Mohammad Al Nagdawi]

conv2 can't find the similarity between multimodal images efficiently. Do you have another similarity metric can deal with the following challenge images?

[Image Analyst]

How are you defining similarity? PSNR? SSIM? MAD? Some other metric?

[Mohammad Al Nagdawi]

In context of image registration, the similarity metric is an indicator that quantifies the degree of closeness between features or intensity values of two images. (Rundo et al. 2016) I expect the highest similarity between these images when the circles completely aligned.

[Image Analyst]

That didn't answer my question. Which similarity metric do you want to use? Did that paper discuss some?

[Mohammad Al Nagdawi]

from the best on my knowledge the state of the art similarity measure unable to find similarity for such images that will lead to correct registration. I tried Mutual information, Jefferey divergence. conv2, RMSE, and PSNR are helpful only for monomodal images. Can you suggest a nonexistent solution I will build and try?

[Image Analyst]

Then you'll have to develop your own. One that preprocesses the images to get something that can be used for registration, like one that finds the outer circle and center, and being robust enough to handle that gradient.

Answer 2

[Image Analyst]

Didn't I answer that in your other question http://www.mathworks.com/matlabcentral/answers/155574#comment_238296

[Emmanuel]

Yeah you did answer! I posted these questions simultaneously and hence the repetition! Thank you