Method and device for motion estimation

• US 5,953,458 A
• Filed: 11/25/1996
• Issued: 09/14/1999
• Est. Priority Date: 12/06/1995
• Status: Expired due to Fees

• Current Assignee: Thomson Multimedia Incorporated (Vantiva SA)
• Original Assignee: Thomson Multimedia Incorporated (Vantiva SA)
• Inventors: Thomas, Pierre-Xavier, Pirson, Alain
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/758,113
• Time in Patent Office: 1,023 Days
• Field of Search: 382/232, 382/236, 382/248, 382/250, 358/432, 358/433, 348/384, 348/394, 348/395, 348/400-404, 348/407-416, 348/420, 348/421, 348/425, 348/430, 348/431
• US Class Current: 382/236
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/231 using full search

Abstract

The invention relates to a device for blockwise estimation of motion. This device includes on the one hand a matrix array (300) for calculating an error function, the said array including storage elements (S, 406, 407) for plural blocks (a, a'"'"') of current pixels and means (403) for switching between the storage elements corresponding to the various blocks and on the other hand a memory (801) for feeding the said array with pixels of a search window, linked to the said array.

The device according to the invention is characterized in that

the said memory (801) is a random access memory,

the said memory contains a band of the search window corresponding to the entirety of the current blocks stored in the array (300),

the said device including means (812) for read-addressing partial sections of the said band of the memory as a function of the block processed (a, a'"'"') by the said array, the said sections being introduced column by column into the said array.

The invention also relates to a corresponding method and applies especially in the field of digital television.

FIG. 7.

Claims

1. Device for estimation of motion of pixel blocks in search windows, comprising:

a matrix array of means for calculating error function values;

a matrix array of storage elements for storing a plurality of groups of adjacent pixel blocks and connected to said array of means for calculating error function values;

switching means for successively selecting each of said plurality of groups of pixel blocks and for providing pixels of said selected group from said matrix array of storage elements to said matrix array of means for calculating error function values during a calculation pass;

a memory for storing a slice of a composite search window encompassing search windows corresponding to said plurality of groups of adjacent pixel blocks, an output of said memory being connected to said matrix array of means for calculating error function values, wherein said slice is updated in response to error function value calculations performed for said slice; and

means for accessing said memory to provide a partial section of said slice to said matrix array for calculating error functions, said partial section corresponding to a selected group of adjacent pixel blocks wherein

each array of said means for calculating error function values carries out calculations for one slice for one pixel block in one calculation pass.

2. Device according to claim 1, wherein

said composite search window encompasses a search window for each pixel block of said groups of pixel blocks, taken one by one.

3. Device according to claim 1, wherein

said device includes a lines of b matrix arrays connected in series, and said a lines are connected in parallel to said memory.

4. Method for estimation of motion of pixel blocks in search windows in a device comprising a matrix array of storage elements for storing groups of adjacent pixel blocks, switching means for providing pixels of one of said groups to a matrix array of error function value calculation means, and a memory for storing a slice of a composite search window encompassing search windows corresponding to said groups, said method comprising the steps of:

selecting a rectangle of x*a*b adjacent pixel blocks from a current image;

splitting said rectangle into x groups of a*b adjacent pixel blocks;

storing said x groups of blocks in storage elements;

loading into a memory a slice of said composite search window;

successively selecting each one of said groups and providing, through switching means, pixels from said selected group to said error function value calculation means; and

calculating in one pass, using said error function value calculation means, error function values for said selected group and for a section of said slice within said composite search window, wherein said section corresponds to a selected group.

5. Method according to claim 4, wherein

said x groups are horizontally adjacent rectangles of a*b blocks, and

said slice is a horizontal slice.

6. Method according to claim 4, wherein the shape factor of said rectangle of a*b blocks is close to the shape factor of a single block.