Apparatus and method for employing M-ary pyramids with N-scale tiling

• US 6,560,371 B1
• Filed: 06/29/1998
• Issued: 05/06/2003
• Est. Priority Date: 12/31/1997
• Status: Expired due to Term

• Current Assignee: MediaTek, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Krishnamurthy, Ravi, Song, Xudong, Zhang, Ya-Qin, Chiang, Tihao
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US09/106,707
• Time in Patent Office: 1,772 Days
• Field of Search: 382/232, 382/236, 382/238, 382/239, 382/240, 382/248, 382/250, 348/384, 348/394, 348/395, 348/400, 348/401, 348/402, 348/403, 348/404, 348/407, 348/408, 348/409, 348/410, 348/412, 348/413, 348/414, 348/415, 348/416, 348/417, 348/418, 348/419, 348/420, 348/421, 348/422, 348/430, 348/431
• US Class Current: 382/240
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

An apparatus and a concomitant method for using M-ary pyramid decomposition in combination with N-scale tiling to reduce the computational complexity in determining motion vectors for block-based motion estimation is disclosed.

Claims

1. A method for performing motion estimation for a sequence of images, said method comprising the steps of:

(a) generating an M-ary pyramid having a plurality of levels for each of said images, where each image is divided into a plurality of blocks;

(b) generating a plurality of motion vectors based on a plurality of tiling blocks sizes; and

(c) passing at least one of said motion vectors for each of said blocks to a lower level of said M-ary pyramid.

2. The method of claim 1, wherein said M-ary pyramid generating step (a) generates a binary pyramid for each of said images.

3. The method of claim 1, wherein said M-ary pyramid generating step (a) comprises the steps of:

(a1) generating a mean pyramid for the image; and

(a2) generating said M-ary pyramid from said mean pyramid.

4. The method of claim 3, wherein said M-ary pyramid generating step (a2) comprises the step of quantizing a plurality of differences between children and parent pixels of said mean pyramid.

5. The method of claim 4, wherein said M-ary pyramid is a binary pyramid.

6. The method of claim 5, wherein said binary pyramid is formed in accordance with:

$B^l<br><br>\left(i,j\right)=\{\begin{array}{cc}0& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>X^l<br><br>\left(i,j\right)\ge <br><br>X^{l+1}<br><br>\left(\mathrm{INT}<br><br>\left(\frac{i}{2}\right),\mathrm{INT}<br><br>\left(\frac{j}{2}\right)\right)\\ 1& \mathrm{otherwise}\end{array}$

where l is a level of said M-ary pyramid, and where B¹(i,j) is a value at a location (i,j).

7. The method of claim 1, wherein said motion vectors generating step (b) is performed hierarchically from a highest level of said M-ary pyramid to a lower level of said M-ary pyramid.

8. The method of claim 7, wherein said passing step (c) passes said motion vectors for each of said blocks to a lower level of said M-ary pyramid from a higher level of said M-ary pyramid for all levels above a lowest level of said M-ary pyramid.

9. The method of claim 7, wherein said motion vectors generating step (b) is performed for three tiling block sizes for each of said blocks to produce three motion vectors for each of said blocks.

10. The method of claim 9, wherein said three tiling block sizes are eight pixels by eight pixels, eight pixels by four pixels, and four pixels by eight pixels.

11. The method of claim 9, wherein said passing step (c) comprises the steps of:

(c1) passing said three motion vectors for each of said blocks from a higher level of said M-ary pyramid for all levels above a lowest level of said M-ary pyramid; and

(c2) passing only one of said three motion vectors for each of said blocks from a level immediately above the lowest level to the lowest level of said M-ary pyramid.

12. An apparatus for performing motion estimation for a sequence of images, said apparatus comprises:

an M-ary pyramid generator for generating an M-ary pyramid having a plurality of levels for each of said images, where each image is divided into a plurality of blocks; and

a motion estimation module for performing hierarchical motion estimation on said M-ary pyramid, where motion vectors are generated in accordance with a plurality of tiling block sizes, and where at least one of said motion vectors for each of said blocks is passed to a lower level of said M-ary pyramid.

13. The apparatus of claim 12, wherein said M-ary pyramid is a binary pyramid.

14. The apparatus of claim 12, wherein said M-ary pyramid generator comprises a mean filter to generate a mean pyramid.

15. The apparatus of claim 13, wherein said M-ary pyramid generator comprises a quantizer for generating said binary pyramid in accordance with:

$B^l<br><br>\left(i,j\right)=\{\begin{array}{cc}0& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>X^l<br><br>\left(i,j\right)\ge <br><br>X^{l+1}<br><br>\left(\mathrm{INT}<br><br>\left(\frac{i}{2}\right),\mathrm{INT}<br><br>\left(\frac{j}{2}\right)\right)\\ 1& \mathrm{otherwise}\end{array}$

where l is a level of said M-ary pyramid, and where B¹(i, j) is a value at a location (i, j).

16. The apparatus of claim 12, wherein said motion vectors for each of said blocks are passed to a lower level of said M-ary pyramid from a higher level of said M-ary pyramid for all levels above a lowest level of said M-ary pyramid.

17. The apparatus of claim 12, wherein said three tiling block sizes are eight pixels by eight pixels, eight pixels by four pixels, and four pixels by eight pixels.

18. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform steps on a sequence of images comprising:

(a) generating an M-ary pyramid having a plurality of levels for each of said images, where each image is divided into a plurality of blocks;

(b) generating a plurality of motion vectors based on a plurality of tiling blocks sizes; and

(c) passing at least one of said motion vectors for each of said blocks to a lower level of said M-ary pyramid.

19. The computer-readable medium of claim 18, wherein said M-ary pyramid generating step (a) generates a binary pyramid for each of said images.

20. Apparatus for encoding an image sequence having at least one input frame, said apparatus comprising:

a motion compensator for generating a predicted image of a current input frame, said motion compensator comprising an M-ary pyramid generator for generating an M-ary pyramid having a plurality of levels for said input frame, where said input frame is divided into a plurality of blocks and a motion estimation module for performing hierarchical motion estimation on said M-ary pyramid, where motion vectors are generated in accordance with a plurality of tiling block sizes, and where at least one of said motion vectors for each of said blocks is passed to a lower level of said M-ary pyramid;

a transform module for applying a transformation to a difference signal between the input frame and said predicted image, where said transformation produces a plurality of coefficients;

a quantizer for quantizing said plurality of coefficients with at least one quantizer scale to produce a plurality of quantized coefficients; and

a coder for coding said quantized coefficients into a bitstream.