Apparatus and method for quadtree based variable block size motion estimation

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.

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.

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.