How do we computer SSD (Sum of Squared Differences)
Show older comments
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!
Accepted Answer
Matt J
on 20 Sep 2014
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(:)));
10 Comments
Image Analyst
on 20 Sep 2014
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.
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
on 20 Sep 2014
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
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
on 26 Jul 2018
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
on 26 Jul 2018
How are you defining similarity? PSNR? SSIM? MAD? Some other metric?
Mohammad Al Nagdawi
on 28 Jul 2018
Edited: Image Analyst
on 28 Jul 2018
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
on 28 Jul 2018
That didn't answer my question. Which similarity metric do you want to use? Did that paper discuss some?
Mohammad Al Nagdawi
on 29 Jul 2018
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
on 29 Jul 2018
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.
More Answers (1)
Image Analyst
on 20 Sep 2014
0 votes
Didn't I answer that in your other question http://www.mathworks.com/matlabcentral/answers/155574#comment_238296
Categories
Find more on Geometric Transformation and Image Registration in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
