US5446806A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Quadtree-structured Walsh transform video/image coding
Assignee: National Semiconductor Corp
•
Filing: 1993-11-15
•
Granted: 1995-08-29
•
Expires: 2013-11-15
Abstract
Abstract Two dimensional data structures are represented by quadtree codes with embedded Walsh transform coefficients. The quadtree code permits both variable block size inherent in quadtrees, and the calculational simplicity of Walsh transform descriptions of nearly uniform blocks of data. Construction of the quadtree is calculationally simple for implementation in a digital system which does a bottom-up determination of the quadtree because Walsh transform coefficients and a measure of the distortion can be recursively calculated using only Walsh transform coefficients from the previous level in the quadtree. Uniform step size quantization, which is optimal for variable length coding and generalized gaussian distributions, permits fast encoding and decoding of quadtree code.
Inventors
- 👤 Xiaonong Ran
- 👤 Micheal Van Scherrenburg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:18
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/10; H04N19/134; H04N19/154; H04N19/90; H04N19/96; H04N19/60
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
209 words
A video coder comprising: a memory; means for creating a quadtree code representing a partition of a two-dimensional array of values stored in the memory, the quadtree code containing embedded Walsh transform coefficients of blocks in the partition, wherein the means for creating the quadtree code comprises: means for generating a quadtree partition of the two-dimensional array, the quadtree partition consisting of blocks from a series of partitions of the two-dimensional array, each partition in the series having a corresponding integer I with N≦I<M and containing 4 I non-intersecting blocks of values from the two-dimensional array, wherein N and M are integers with N<M, and for each integer J with N≦J<M, each block in a partition corresponding to integer J equals a union of four blocks in a partition corresponding to an integer J+1; means for generating a code that indicates which blocks from the series of partitions are in the quadtree partition of the two-dimensional array; and means for generating Walsh transform coefficients for each block in the quadtree partition and embedding the generated Walsh transform coefficients in the code which indicates the quadtree partition; means for guantizing the Walsh transform coefficients embedded in the quadtree code; and means for variable length coding the quantized Walsh transform coefficients.
Claim 2
Dependent Claim
209 words
A video coder comprising: a memory; means for creating a quadtree code representing a partition of a two-dimensional array of values stored in the memory, the quadtree code containing embedded Walsh transform coefficients of blocks in the partition, wherein the means for creating the quadtree code comprises: means for generating a quadtree partition of the two-dimensional array, the quadtree partition consisting of blocks from a series of partitions of the two-dimensional array, each partition in the series having a corresponding integer I with N≦I<M and containing 4 I non-intersecting blocks of values from the two-dimensional array, wherein N and M are integers with N<M, and for each integer J with N≦J<M, each block in a partition corresponding to integer J equals a union of four blocks in a partition corresponding to an integer J+1; means for generating a code that indicates which blocks from the series of partitions are in the quadtree partition of the two-dimensional array; and means for generating Walsh transform coefficients for each block in the quadtree partition and embedding the generated Walsh transform coefficients in the code which indicates the quadtree partition; means for guantizing the Walsh transform coefficients embedded in the quadtree code; and means for variable length coding the quantized Walsh transform coefficients.
Claim 3
Dependent Claim
65 words
The video coder of claim 1, further comprising: a first frame buffer for holding a first pixel map describing a first video image; a second frame buffer for holding a second pixel map describing a second video image; and means for generating and storing in the memory a two-dimensional array of values representing the difference between the first video image and the second video image.
Claim 4
Dependent Claim
75 words
The video coder of claim 2, wherein the means for generating a two-dimensional array comprises: a motion estimation block which determines an average shift between values in the first pixel map and values in the second pixel map; and means for subtracting the first pixel map from the second pixel map, wherein the first pixel map and the second pixel are shifted relative to each other by an amount determine by the motion estimation block.
Claim 5
Dependent Claim
36 words
The video coder of claim 1, wherein the means for quantizing comprises means for dividing Walsh coefficients of a first block in the quadtree partition by a first constant which indicates a uniform quantization steep size.
Claim 6
Dependent Claim
58 words
The video coder of claim 4, wherein the means for quantizing comprises means for dividing Walsh coefficients of a second block in the quadtree partition by a second constant which indicates a second uniform quantization step size wherein the first block contains more values than does the second block, and the first constant differs from the second constant.
Claim 7
Dependent Claim
40 words
The video coder of claim 4, further comprising means for determining a difference between a first Walsh coefficient of the first block and a corresponding Walsh coefficient of a second block and then dividing the difference by the first constant.
Claim 8
Dependent Claim
198 words
A video coder comprising: a memory; a processor which creates a quadtree code representing a partition of a two-dimensional array of values stored in the memory, the quadtree code containing embedded quantized Walsh transform coefficients of blocks in the partition, wherein the processor comprises: means for generating a quadtree partition of the two-dimensional array, the quadtree partition consisting of blocks from a series of partitions of the two-dimensional array, each partition in the series having a corresponding integer I with N≦I≦M and containing 4 I non-intersecting blocks of values from the two-dimensional array, wherein N and M are integers with N<M and for each integer J with N≦J<M, each block in a partition corresponding to integer J equals a union of four blocks in a partition corresponding to an integer J+; means for generating a code which indicates which of the blocks from the series of partitions are in the quadtree partition of the two-dimensional array; and means for generating Walsh transform coefficients for each block in the quadtree partition and embedding the generated Walsh transform coefficients in the code which indicates the quadtree partition; and a source encoder which variable length codes the quantized Walsh transform coefficients.
Claim 9
Dependent Claim
198 words
A video coder comprising: a memory; a processor which creates a quadtree code representing a partition of a two-dimensional array of values stored in the memory, the quadtree code containing embedded quantized Walsh transform coefficients of blocks in the partition, wherein the processor comprises: means for generating a quadtree partition of the two-dimensional array, the quadtree partition consisting of blocks from a series of partitions of the two-dimensional array, each partition in the series having a corresponding integer I with N≦I≦M and containing 4 I non-intersecting blocks of values from the two-dimensional array, wherein N and M are integers with N<M and for each integer J with N≦J<M, each block in a partition corresponding to integer J equals a union of four blocks in a partition corresponding to an integer J+; means for generating a code which indicates which of the blocks from the series of partitions are in the quadtree partition of the two-dimensional array; and means for generating Walsh transform coefficients for each block in the quadtree partition and embedding the generated Walsh transform coefficients in the code which indicates the quadtree partition; and a source encoder which variable length codes the quantized Walsh transform coefficients.
Claim 10
Dependent Claim
43 words
The video coder of claim 7, wherein the processor further comprises means for quantizing Walsh transform coefficients of blocks, wherein all of the quantized Walsh coefficients for a block are quantized using a single predetermined constant which indicates a uniform quantization step size.
Claim 11
Dependent Claim
57 words
The video coder of claim 8, wherein the means for quantizing Walsh transform coefficients quantizes Walsh coefficient of a first block according to the first predetermined constant and quantizes Walsh coefficient of a second block according to a second constant which indicates a second uniform quantization step size, wherein the second constant differs from the first constant.
Claim 12
Dependent Claim
40 words
The video coder of claim 8, further comprising means for determining a difference between a Walsh coefficient of the first block and a corresponding Walsh coefficient of a second block and then quantizing the difference according to the first constant.
Claim 13
Independent Claim
193 words
A method for encoding a video image, comprising the steps of: storing in a memory, a two-dimensional array of values representing pixels of the video image; partitioning the two-dimensional array into a quadtree partition, the quadtree partition consisting of blocks from a series of partitions of the two-dimensional array, each partition in the series having a corresponding integer I with N≦I≦M and containing 4 I non-intersecting blocks of values from the two-dimensional array, wherein N and M are integers with N<M and for each integer J with N≦J<M, each block in a partition corresponding to integer J equals a union of four blocks in a partition corresponding to an integer J+1; generating a code which indicates which of the blocks of the series of partitions are in the quadtree partition of the two-dimensional array; generating Walsh transform coefficients for each block in the quadtree partition; quantizing Walsh transform coefficients of a first block in the quadtree partition by dividing the Walsh transform coefficients of the first block by a first constant that indicates a uniform quantization step size; and embedding the quantized Walsh transform coefficients in the code which indicates the quadtree partition.
Claim 14
Independent Claim
193 words
A method for encoding a video image, comprising the steps of: storing in a memory, a two-dimensional array of values representing pixels of the video image; partitioning the two-dimensional array into a quadtree partition, the quadtree partition consisting of blocks from a series of partitions of the two-dimensional array, each partition in the series having a corresponding integer I with N≦I≦M and containing 4 I non-intersecting blocks of values from the two-dimensional array, wherein N and M are integers with N<M and for each integer J with N≦J<M, each block in a partition corresponding to integer J equals a union of four blocks in a partition corresponding to an integer J+1; generating a code which indicates which of the blocks of the series of partitions are in the quadtree partition of the two-dimensional array; generating Walsh transform coefficients for each block in the quadtree partition; quantizing Walsh transform coefficients of a first block in the quadtree partition by dividing the Walsh transform coefficients of the first block by a first constant that indicates a uniform quantization step size; and embedding the quantized Walsh transform coefficients in the code which indicates the quadtree partition.
Claim 15
Dependent Claim
65 words
The method of claim 11, further comprising the step of quantizing Walsh transform coefficients of a second block in the quadtree partition by dividing the Walsh transform coefficients of the second block by a second constant that indicates a second uniform quantization step size, wherein the first block contains fewer values than does the second block, and the first constant differs from the second constant.
Claim 16
Dependent Claim
56 words
The method of claim 11, further comprising the steps of: determining a difference between a Walsh transform coefficient of the first block and a corresponding Walsh transform coefficient of a second block; quantizing the difference by dividing the difference by the first constant; and embedding the quantized difference in the code which indicates the quadtree partition.
Claim 17
Dependent Claim
41 words
The method of claim 13, further comprising the step of variable length coding the quantized Walsh transform coefficients and the quantized difference before embedding the quantized Walsh transform coefficients and the quantized difference in the code which indicates the quadtree partition.
Claim 18
Dependent Claim
15 words
The method of claim 11, wherein the video image being encoded is a difference frame.
Claim 19
Dependent Claim
53 words
The method of claim 11, wherein the embedding step comprises embedding in the code Walsh transform coefficients for a first block in the quadtree partition, wherein a total number of Walsh transform coefficients embedded in the code, for the first block is fewer than a total number of values in the first block.
References Cited (Backward Citations)
US4831659A
Cited
US5060285A
Cited
US5241395A
Cited
US5293434A
Cited
WO1992022166A1
Cited
US5228098A
Cited
US5295203A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-28 | 1999-02-27 | 1999-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-28 | 2003-02-27 | 2003-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-28 | 2007-02-27 | 2007-08-29 | $7700.00 | Window Closed / Lapsed |