Apparatus and method for quadtree based variable block size motion estimation

• US 6,084,908 A
• Filed: 10/23/1996
• Issued: 07/04/2000
• Est. Priority Date: 10/25/1995
• Status: Expired due to Term

• Current Assignee: Sharp Corporation (Hon Hai Precision Industry Co., Ltd.), MediaTek, Inc.
• Original Assignee: Sharp Corporation (Hon Hai Precision Industry Co., Ltd.), Sarnoff Corporation (SRI International, Inc.)
• Inventors: Xiong, Zixiang, Zhang, Ya-Qin, Chiang, Tihao, Lee, Jungwoo
• Primary Examiner(s): Kelley, Chris S.
• Assistant Examiner(s): VO, TUNG T
• Application Number:
  US08/735,869
• Time in Patent Office: 1,350 Days
• Field of Search: 348/405, 348/406, 348/413, 348/415, 348/419, 348/409, 348/420, 348/398, 348/399, 348/416, 382/41, 382/232, 382/246, 382/240, 358/533, 358/454, 375/240
• US Class Current: 375/240.03
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

A method and apparatus for determining an optimal quadtree structure for quadtree-based variable block size (VBS) motion estimation. The method computes the motion vectors for the entire quadtree from the largest block-size to the smallest block-size. Next, the method may optionally select an optimal quantizer scale for each block. The method then compares from "bottom-up" the sum of the distortion from encoding all sub-blocks or sub-nodes (children) as compared to the distortion from encoding the block or node (parent) from which the subnodes are partitioned from. If the sum of the distortion from encoding the children is greater than that of the parent then the node is "merged". Conversely, if the sum of the distortion from encoding the children is less than that of the parent then the node is "split" and the Lagrangian cost for the parent node is set as the sum of the Lagrangian cost of its children. This step is repeated for the all nodes through every level until an optimal quadtree structure is obtained.

Claims

1. Method for determining a tree structure for performing variable block size motion estimation for an image frame, where said tree structure has a plurality of blocks organized in a plurality of levels with a parent-child relationship, said method comprising the steps of:

(a) partitioning the image frame into a plurality of blocks down to a lowest level of the tree structure;

(b) calculating a distortion for encoding each of said plurality of blocks, by selecting a quantizer scale that produces a minimum Lagrangian cost for each of said plurality of blocks;

(c) comparing a sum of said distortions for a set of children blocks with said distortion of a corresponding parent block; and

(d) adjusting a size of said parent block in accordance with a result from said comparing step.

2. The method of claim 1, further comprising the step of:

repeating steps (c) and (d) for all of said blocks up to a highest level of the tree structure.

3. The method of claim 1, wherein said adjusting step (d) comprises the steps of:

merging said children blocks if said sum of said distortions for said children blocks is greater than said distortion of their parent block or splitting said parent block into its children blocks if said sum of said distortions for said children blocks is less than said distortion of their parent block.

4. The method of claim 3, wherein said adjusting step (d) further comprises the step of:

setting said distortion of said parent block to said sum of said distortions for its children blocks if said sum of said distortions for said children blocks is less than said distortion of their parent block.

5. The method of claim 1, wherein said comparing step (c) and adjusting step (d) are conducted using a bottom-up search pattern.

7. The method of claim 1, wherein said quantizer selecting step comprises the steps of:

assigning each of said plurality of blocks a selected set of quantizer scales; and

selecting a quantizer scale from said selected set of quantizer scales that produces a smallest amount of distortion for each block.

8. The method of claim 1, wherein said distortion calculating step (b) comprises the step of:

computing a motion vector for each of said plurality of blocks, wherein said distortion for each block is a result of encoding each block using said motion vector.

9. The method of claim 8, wherein said selected quantizer scale for each of said plurality of blocks is selected to produce a minimum Lagrangian cost for each block.

10. The method of claim 9, wherein said distortion calculating step (b) is subjected to a total bit budget constraint predefined for the image frame.

12. The method of claim 1, wherein said tree structure is a quadtree structure.

6. Method for determining a tree structure for performing variable block size motion estimation for an image frame, where said tree structure has a plurality of blocks organized in a plurality of levels with a parent-child relationship, said method comprising the steps of:

(a) partitioning the image frame into a plurality of blocks down to a lowest level of the tree structure;

(b) calculating a distortion for encoding each of said plurality of blocks, by selecting a quantizer scale that produces a minimum Lagrangian cost for each of said plurality of blocks;

(c) comparing a sum of said distortions for a set of children blocks with said distortion of a corresponding parent block; and

(d) adjusting a size of said parent block in accordance with a result from said comparing step,

wherein said comparing step (c) and adjusting step (d) are conducted using a top-down search pattern, and wherein said distortion calculating step (b) only calculates a distortion for said plurality of blocks that are grown.

11. Method for determining a tree structure for performing variable block size motion estimation for an image frame, where said tree structure has a plurality of blocks organized in a plurality of levels with a parent-child relationship, said method comprising the steps of:

(a) partitioning the image frame into a plurality of blocks down to a lowest level of the tree structure, wherein said plurality of blocks are affine blocks;

(b) calculating a distortion for encoding each of said plurality of blocks by selecting a quantizer scale that produces a minimum Lagrangian cost for each of said plurality of blocks;

(c) comparing a sum of said distortions for a set of children blocks with said distortion of a corresponding parent block; and

(d) adjusting a size of said parent block in accordance with a result from said comparing step.

13. The method of claim 11, wherein the image frame comprises video object planes.

14. Apparatus for encoding an input image which is partitioned in accordance with a tree structure, where said tree structure has a plurality of blocks organized in a plurality of levels with a parent-child relationship, said apparatus comprising:

a variable block motion estimation module for computing a plurality of motion vectors for all of said plurality of blocks for the entire tree structure of the input image to obtain an optimal tree structure;

a motion compensation module, coupled to said variable block motion estimation module, for generating a predicted image using said plurality of motion vectors for said optimal tree structure;

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

a quantization module, coupled to said transform module, for quantizing said plurality of coefficients; and

a rate control module, coupled to said quantization module, for selecting a quantizer scale that produces a minimum Lagrangian cost for each of said plurality of blocks.

15. The apparatus of claim 14, wherein said tree structure is adjusted by comparing a sum of said Lagrangian costs for a set of children blocks with said Lagrangian cost of a corresponding parent block.

16. The apparatus of claim 14, wherein said transform module applies a forward discrete cosine transform.

17. The apparatus of claim 14, wherein said transform module applies a wavelet transform.