US6084908A — Apparatus and method for quadtree based variable …

Claim 1

Independent Claim 130 words

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.

Claim 2

Dependent Claim 130 words

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.

Claim 3

Dependent Claim 29 words

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.

Claim 4

Dependent Claim 65 words

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.

Claim 5

Dependent Claim 51 words

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.

Claim 6

Dependent Claim 21 words

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

Claim 7

Dependent Claim 165 words

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.

Claim 8

Dependent Claim 165 words

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.

Claim 9

Dependent Claim 49 words

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.

Claim 10

Dependent Claim 43 words

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.

Claim 11

Dependent Claim 28 words

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.

Claim 12

Dependent Claim 24 words

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

Claim 13

Dependent Claim 138 words

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.

Claim 14

Dependent Claim 138 words

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.

Claim 15

Dependent Claim 13 words

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

Claim 16

Dependent Claim 13 words

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

Claim 17

Dependent Claim 175 words

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.

Claim 18

Dependent Claim 175 words

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.

Claim 19

Dependent Claim 34 words

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.

Claim 20

Dependent Claim 15 words

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

Claim 21

Dependent Claim 13 words

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

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-07-04	2004-01-03	2004-07-04	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-07-04	2008-01-03	2008-07-04	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-07-04	2012-01-03	2012-07-04	$7700.00	Window Closed / Lapsed

Apparatus and method for quadtree based variable block size motion estimation

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag