Step 1: Create a 5x5 search pattern around the centre of the search area,
consisting of the nine coordinates surrounding the centre. Find the minimum BDM of
these coordinates. If the minimum is located at the centre, proceed with step 4.
Otherwise: Go to step 2
Step 2: The search pattern still has the size of 5x5. Depending on the location
of the current minimum BDM, new search coordinates are added to the pattern.
a) If the current minimum BDM is located at the corner of the pattern in step 1),
add 5 additional coordinates located next to the corner.
b) If the minimum BDM is located at the centre of a vertical or horizontal axis
of the search pattern in step 1), add three coordinates to the pattern which are lined up
parallel with that axis.
Search for the new minimum BDM. If its position has not changed after this search, continue
with step 4.
Step 4: Repeat step 2 once and proceed with step 4.
Step 4: The search window size is reduced to 3x3 around the minimum BDM. Search all eight
new coordinates in this pattern for the final minimum BDM.
> |
performs the next comparison |
>> |
performs the next 10 comparisons |
>| |
performs all comparisons |
The grid:
In the lower left you will see a grid. It presents a schematic view of the search area.
Each coordinate represents a block within the area.
A red circle marks position
that are going to be searched.
A yellow dot marks the current optimal position
A green dot marks the current search position
A black cross marks positions that have been searched
How the comparisons of two blocks is done:
In this applet only grey scale-images are used - this means the images have only one color
value per pixel (color images e.g. in RGB format have three).
The algorithm runs through every pixel of the source block and subtracts it from the pixel at
the same position in the block compared to. results are squared and summed up. In the end,
they are normalized,
dist = distance in color space
c(x) = color value of pixel x