Step 1: Create a search pattern consisting of 9 coordinates.
These are the centre of the search area (0,0) and the 8 coordinates
with a horizontal and/or vertical distance of 4 pixels to it. Find the
coordinate with the minimum BDM value
Step 2: Halve the search range to to 2. Create a new search pattern
with the eight coordinates surrounding the current best matching coordinate.
Again, find the coordinate with the minimum BDM.
Step 3: Reduce the search range again - this time to 1 pixel. Create a search
pattern existing of the eight coordinates surrounding the current best matching position.
Finally, search for the minimum BDM. This is the coordinate the motion vector will point to.
> |
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