Motion estimation using a hierarchical search

Abstract

A hierarchial search for moving image encoding determines a motion vector by comparing a target block to sets of blocks selected according to the results of previous comparisons. Typically, each set of blocks includes a central block and four blocks offset on x and y axes. Blocks most similar to the target block provide co-ordinates of a center block in a next stage of the search. The hierarchial search searches regions indicated by previous comparisons to be similar to the target block and thereby reduces the number of comparisons and the search time required to find a motion vector. A motion estimation circuit for the hierarchial search includes: five processing elements which compare the target block to five blocks; a first memory that asserts a target block pixel value to the processing elements; a second memory that asserts five search window pixel values to the processing elements. The processing elements operate in parallel, and an address generator selects the five search window pixel values according to output from the processing elements. The second memory contains three parts. One part is loaded with new data while the processing elements search data from the other two parts. Each part contains nine memory modules, each having an independently addressable data port.