Method and apparatus for global-to-local block motion estimation

Claim 3

The method of claim 1 further comprising the steps of: selecting an estimated motion vector from said plurality of estimated motion vectors; positioning, at an initial position defined by said selected estimated motion vector, a full resolution pixel block, from said second image frame, within a full resolution search area within said first image frame; performing, from the initial position, a local search within said full resolution search area using said full resolution pixel block until said full resolution pixel block substantially matches a matching block of pixels in said full resolution search area; and computing a final motion vector representing a distance between a location of said full resolution pixel block within said second image frame and a location of said matching block of pixels within said first image frame.

Claim 4

The method of claim 1 wherein said assigning step is accomplished using a systolic array.

Claim 5

The method of claim 1 wherein said assigning step further comprises the steps of: selecting a reduced resolution block of pixels from said plurality of reduced resolution blocks of pixels; and assigning an estimated motion vector to each of said pre-defined sub-blocks within said selected reduced resolution block of pixels, where said assigned estimated motion vector is selected from either the estimated motion vector computed for said metablock or one of the estimated motion vectors computed for said selected reduced resolution block of pixels.

Claim 6

The method of claim 1 wherein said assigning step further comprises the steps of: selecting a reduced resolution block of pixels from said plurality of reduced resolution blocks of pixels; and assigning an estimated motion vector to each of said pre-defined sub-blocks within said selected reduced resolution block of pixels, where said assigned estimated motion vector is a combination of the estimated motion vector computed for said metablock and one or more of the estimated motion vectors computed for said reduced resolution blocks of pixels.

Claim 7

The method of claim 1 wherein said decimating steps further comprise a step of filtering each of said pixels in said first and second image frames.

Claim 8

The method of claim 1 wherein said first and second image frames are consecutive frames selected from a sequence of image frames.

Claim 9

Apparatus for estimating motion vectors having as an input a first image frame and a second image frame, each containing a plurality of pixels representing an image, said apparatus comprising: a pyramid processor for decimating a search area within said first image frame to produce a reduced resolution search area and for decimating a block of pixels in said second image frame to produce a metablock containing a plurality of reduced resolution blocks of pixels partitioned into pre-defined sub-blocks; global search means, connected to said pyramid processor, for performing a global search within said reduced resolution search area using said metablock until said metablock substantially matches a matching block of pixels in said reduced resolution search area; and means, connected to said global search means, for computing a plurality of estimated motion vectors representing a distance between a location of each of said plurality of reduced resolution blocks within said metablock of said second image frame and a location of said matching block of pixels within said first image frame, where one estimated motion vector is computed for each of said reduced resolution pixel blocks and one estimated motion vector is computed for the metablock; and means, connected to said global search means, for assigning the estimated motion vector of each said reduced resolution pixel blocks to each of said pre-defined sub-blocks within each reduced resolution pixel block.

Claim 10

Apparatus for estimating motion vectors having as an input a first image frame and a second image frame, each containing a plurality of pixels representing an image, said apparatus comprising: a pyramid processor for decimating a search area within said first image frame to produce a reduced resolution search area and for decimating a block of pixels in said second image frame to produce a metablock containing a plurality of reduced resolution blocks of pixels partitioned into pre-defined sub-blocks; global search means, connected to said pyramid processor, for performing a global search within said reduced resolution search area using said metablock until said metablock substantially matches a matching block of pixels in said reduced resolution search area; and means, connected to said global search means, for computing a plurality of estimated motion vectors representing a distance between a location of each of said plurality of reduced resolution blocks within said metablock of said second image frame and a location of said matching block of pixels within said first image frame, where one estimated motion vector is computed for each of said reduced resolution pixel blocks and one estimated motion vector is computed for the metablock; and means, connected to said global search means, for assigning the estimated motion vector of each said reduced resolution pixel blocks to each of said pre-defined sub-blocks within each reduced resolution pixel block.

Claim 11

The apparatus of claim 8 further comprising: means for selecting an estimated motion vector from said plurality of estimated motion vectors; means for positioning, at an initial position defined by said selected estimated motion vector, a full resolution pixel block, from said second image frame, within a full resolution search area within said first image frame; local search means for performing, from the initial position, a local search within said full resolution search area using said full resolution pixel block until said full resolution pixel block substantially matches a matching block of pixels in said full resolution search area; and means for computing a final motion vector representing a distance between a location of said full resolution pixel block within said second image frame and a location of said matching block of pixels within said first image frame.

Claim 12

The apparatus of claim 8 wherein said assigning means is a systolic array.

Claim 13

The apparatus of claim 8 wherein said assigning means further comprises: means for selecting a reduced resolution block of pixels from said plurality of reduced resolution blocks of pixels; and means for assigning an estimated motion vector to each of said pre-defined sub-blocks within said selected reduced resolution block of pixels, where said assigned estimated motion vector is selected from either the estimated motion vector computed for said metablock or one of the estimated motion vectors computed for said selected reduced resolution block of pixels.

Claim 14

The apparatus of claim 8 wherein said assigning means further comprises: means for selecting a reduced resolution block of pixels from said plurality of reduced resolution blocks of pixels; and means for assigning an estimated motion vector to each of said pre-defined sub-blocks within said selected reduced resolution block of pixels, where said assigned estimated motion vector is a combination of the estimated motion vector computed for said metablock and one or more of the estimated motion vectors computed for said reduced resolution blocks of pixels.

Claim 15

The apparatus of claim 8 wherein said pyramid processor further comprises a filter for filtering each of said pixels in said first and second image frames.

Claim 16

The apparatus of claim 8 wherein said first and second image frames are consecutive frames selected from a sequence of image frames.