Motion estimation using a hierarchical search

A process for generating a motion vector corresponding to a target block in a current flame of a moving image, the process comprising:

• (a) selecting a step size;
• (b) storing a first component and a second component of an estimated motion vector in a memory, the estimated motion vector identifying a first block in a second frame of the moving image;
• (c) determining a first cost which indicates a difference between the target block and the first block;
• (d) determining second, third, fourth, and fifth costs which indicate differences between the target block and second, third, fourth, and fifth blocks in the second frame, wherein a vector formed by adding the step size to the first component of the estimated motion vector identifies the second block, a vector formed by subtracting the step size from the first component of the estimated motion vector identifies the third block, a vector formed by adding the step size to the second component of the estimated motion vector identifies the fourth block, and a vector formed by subtracting the step size from the second component of the estimated motion vector identifies the fifth block;
• (e) increasing the first component of the estimated motion vector by the step size in response to the second cost being less than the first and third costs;
• (f) reducing the first component of the estimated motion vector by the step size in response to the third cost being less than the first and second costs;
• (g) increasing the second component of the estimated motion vector by the step size the fourth cost being less than the first and fifth costs;
• (h) reducing the second component of the estimated motion vector by the step size in response to the fifth cost being less than the first and fourth costs;
• (i) reducing the step size;
• j) repeating steps (c) through (i) one or more times;
• and
• (k) generating a motion vector which equals the estimated motion vector.

A motion estimation circuit comprising:

• a plurality of processing elements, wherein each processing element converts data signals representing pixel values for first and second blocks into a cost representing a difference between the first and second blocks;
• a first memory operably coupled to simultaneously assert a first data signal to all of the processing elements, the first data signal representing a pixel value from a target block which is stored in the first memory;
• and
• a second memory operably coupled to simultaneously assert second data signals to the processing elements, wherein the second data signals are independent of each other, each second data signal representing a pixel value from a different block in a search window which is stored in the second memory.

A method for generating a motion vector, the method comprising:

• selecting a search center in a two-dimensional array of pixels;
• performing a series of search stages, each search stage comprising:
• searching a first set of blocks of pixels in the two-dimensional array, wherein blocks in the first set are aligned along a first line through the search center;
• identifying a first block which of the blocks in the first set most closely matches a target block;
• searching a second set of blocks of pixels in the two-dimensional array, wherein blocks in the second set are aligned along a second line through the search center;
• identifying a second block which of the blocks in the second set most closely matches the target block;
• and
• changing the search center for a next search stage in the series so that the search center is aligned with the first and second blocks, wherein in response to the first block not being aligned along the second line and the second block not being aligned along the first line, the search center for the next search stage is offset from the first and second lines;
• and
• generating the motion vector from the search center after completing the search stages.

A method for moving image encoding, comprising:

• writing pixel values into a first part of a memory, wherein the pixel values in the first part of the memory represent part of a first search window;
• writing pixel values into a second part of the memory, wherein the pixel values in the second part of the memory represent a part of the first search window which overlaps a first part of a second search window;
• determining a first motion vector for a first target block using the pixel values in the first and second parts of the memory;
• writing pixel values into a third part of the memory, wherein the pixel values in the third part of the memory represent a second part of the second search window and are written to the third part of the memory simultaneously with determining the first motion vector;
• and
• determining a second motion vector for a second target block using pixel values that were written in the second part of the memory before determining the first motion vector and using pixel values that were written in the third part of the memory while determining the first motion vector.

A motion estimation circuit comprising:

• a first memory for storing pixel values of a target block;
• a second memory for storing pixel values of search areas, the second memory having a first, a second, and a third parts, each part having a data port for writing pixel values to that part, wherein two of the three parts of the second memory are required to store pixel values of a search area for the target block;
• a first processing element operably coupled to process pixel values from the first memory and the second memory;
• and
• an address generator which selects pixel values from two of the first, second, and third parts of the second memory to be processed by the first processing element while pixel values of a search area for another block are written to the one of the first, second, and third parts of the second memory not containing the pixel values being selected.

A motion estimation circuit comprising:

• a first memory for storing pixel values of a target block;
• a second memory for storing pixel values of a search area;
• and
• a plurality of processing elements coupled to the first and second memories, wherein:
• the second memory comprises nine modules, each module having a data port for reading pixel values from that module, the data ports being coupled to the processing elements;
• and
• a two-dimensional array of pixel values representing the search area is stored in the nine modules such that:
• each pixels value in a first row of the array is stored in a first, second, or third of the nine modules;
• each pixels value in a second row of the array is stored in a fourth, fifth, or sixth of the nine modules;
• and
• each pixels value in a third row of the array is stored in a seventh, eighth, or ninth of the nine modules.