How does sum of squared difference algorithm work?

Question

I have a two images a and b, where b is a block of image a. I want to find b using block matching. How do I go about it?

Solution 1

It's very simple, in fact the name tells you pretty much everything you need to know - you just calculate the sum of the squared difference value for each pixel.

To calculate the SSD for two images:

ssd = 0
for i = 0 to height - 1
    for j = 0 to width - 1
        diff = A[i][j] - B[i][j]
        ssd += diff * diff

The general idea is that for matching images the SSD will be small. If you're trying to match two images, where one image is translated by some amount, then you would typically do a brute force approach where you calculate the SSD over a range of x, y displacements and then identify the minimum SSD value, which should then correspond to the best alignment offset.

Note that SSD is generally only used due to its simplicity and relatively low computational cost - in general you will get better results using Normalized Cross Correlation.

Solution 2

If you want to find a position of a block b inside an image a, you can save a lot of computing power by building a Gaussian pyramid of both images and start looking at the smallest going up as you find.

The smallest image would give you quick calculations but an estimate result - this estimate result can be later used in the next level of the pyramid to narrow your search area and get a better precision result. You continue like that until you reach level 0 of your pyramid which is you original image.