Patent US5867221A successfully refreshed from Google Patents.
US5867221A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for the fractal compression of data using an integrated circuit for discrete cosine transform compression/decompression
Assignee: Mediabin Inc
•
Filing: 1996-03-29
•
Granted: 1999-02-02
•
Expires: 2016-03-29
Abstract
Abstract A system and method for compressing related data sets of a sequence are disclosed. The process compares domain blocks from a current frame buffer to range blocks in a previous frame buffer or vector quantization ("VQ") tables to generate affine map codes. The affine map codes are preferably encoded by an entropy encoder before being transmitted to a remote site for decompression. The cost for the encoded affine map codes are computed and used to determine whether affine map codes for representing smaller blocks should be included in the affine map codes which represent the domain blocks into which the original frame was segmented. The methods are preferably implemented on a commercially available discrete cosine transform ("DCT") processor having a process controller and a data comparator. The results of the affine map code generating process on the DCT processor achieves a more consistent bit rate and image quality than methods operating the DCT processor to generate DCT codes.
Inventors
- 👤 David Pullen
- 👤 Brad Howard
- 👤 Gang Liang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:03
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/90; H04N19/94; H04N19/10; H04N19/102; H04N19/124; H04N19/126; H04N19/134; H04N19/146; H04N19/147; H04N19/154; H04N19/169; H04N19/17; H04N19/176; H04N19/189; H04N19/19; H04N19/50; H04N19/503; H04N19/51; H04N19/53; H04N19/60; H04N19/61; H04N19/96; H04N19/99
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
129 words
A method for compressing related sets of data comprising the steps of: performing a local search to compare a first set of range blocks from a range area in a previous frame buffer to a domain block; performing a checkerboard search to compare a second set of range blocks from a range area in said previous frame buffer to said domain block; determining a first cost of coding a best correspondence between a range block from said first set and said domain block; determining a second cost of coding a best correspondence between a range block from said second set and said domain block; and selecting a set of codes to represent said domain block, said selected set of codes corresponding to said best correspondence having a least cost.
Claim 2
Independent Claim
129 words
A method for compressing related sets of data comprising the steps of: performing a local search to compare a first set of range blocks from a range area in a previous frame buffer to a domain block; performing a checkerboard search to compare a second set of range blocks from a range area in said previous frame buffer to said domain block; determining a first cost of coding a best correspondence between a range block from said first set and said domain block; determining a second cost of coding a best correspondence between a range block from said second set and said domain block; and selecting a set of codes to represent said domain block, said selected set of codes corresponding to said best correspondence having a least cost.
Claim 3
Dependent Claim
22 words
The method of claim 1 wherein said determining step and said selecting steps are performed by a discrete cosine transfer (DCT) processor.
Claim 4
Dependent Claim
47 words
The method of claim 1 further comprising the steps of: performing a no motion search to compare a no-motion range block from said previous frame buffer to said domain block; and determining the no motion cost of coding said domain block with reference to said no-motion block.
Claim 5
Dependent Claim
74 words
The method of claim 1 wherein said domain block is a Y component domain block and further comprising the steps of: determining a best correspondence between a domain block of a second color component in said current frame and a block in a second buffer for said second color component; and selecting a set of affine map codes corresponding to said determined best correspondence for representing said domain block in said second color component.
Claim 6
Dependent Claim
54 words
The method of claim 4 further comprising the steps of: adjusting a motion vector from said set of affine map codes for said domain block of said Y component; and selecting a range block in said second buffer of said second color component to compare with said domain block of said second color component.
Claim 7
Dependent Claim
124 words
The method of claim 1 further comprising the steps of: segmenting said domain block into domain child blocks; determining a best correspondence for said domain child blocks and a block in said previous frame buffer; computing a distortion measurement between each domain child block and a portion of said domain block corresponding to said domain child block; computing a pixel mean difference for each said domain child block; comparing a cost of a set of affine map codes for each pixel mean difference and a cost of a set of affine map codes for said best correspondence for said domain child block; and selecting one of said sets of affine map codes to represent said domain child block that corresponds to said least cost.
Claim 8
Dependent Claim
36 words
The method of claim 6 wherein said cost is a sum of a product of said distortion measurement and a normalization factor and a product of a length of a codeword and a bit rate multiplier.
Claim 9
Dependent Claim
23 words
The method of claim 6 farther including the steps of: interpolating said current frame to a reduced size prior to said determining step.
Claim 10
Dependent Claim
109 words
The method of claim 6 further comprising the steps of: segmenting said domain child block into domain child sub-blocks; computing a distortion measurement between each domain child sub-block and a portion of said domain child block corresponding to said domain child sub-block; computing a pixel mean difference for each said domain child sub-block; comparing a cost of a set of affine map codes for each pixel mean difference and a cost of a set of affine map codes for said best correspondence for said domain child sub-block; and selecting one of said sets of affine map codes to represent said domain child sub-block that corresponds to said least cost.
Claim 11
Dependent Claim
76 words
The method of claim 9 further comprising the steps of: computing a mean pixel value for each said domain child sub-block; adjusting said domain child sub-block by subtracting said mean pixel value from each pixel in each said domain child sub-block; comparing said adjusted domain child sub-block to a plurality of VQ blocks; and selecting affine map codes for said domain child sub-block corresponding to a domain child sub-block/VQ block combination having a smallest distortion measurement.
Claim 12
Dependent Claim
89 words
The method of claim 10 further comprising the steps of: computing a cost for said affine map codes for said domain child sub-block; comparing said cost for said domain child sub-block to said distortion measurement between said domain child block and its corresponding portion of said best correspondence for said domain child block; and including said affine map codes selected for said domain child sub-blocks in said set of affine map codes for representing said domain child block in response to said cost being less than said distortion measurement.
Claim 13
Dependent Claim
43 words
The method of claim 11 further comprising the steps: replacing said set of affine map codes with a do nothing code in response to said cost for said do nothing code being less than said cost for said set of affine map codes.
Claim 14
Dependent Claim
49 words
The method of claim 12 wherein said replacing step is performed for a domain block of a first color component of said current frame; and determining a best correspondence for a next domain block of said first color component without determining a best correspondence for a second color component.
Claim 15
Dependent Claim
115 words
The method of claim of claim 11 further comprising the steps of: computing a sum of costs for said selected affine map codes for one of said domain child blocks and said selected affine map codes for said domain child blocks corresponding to said one of said domain child blocks; comparing said distortion measurement between said one of said domain child block and said corresponding portion of said best correspondence for said domain block and said computed costs; and selecting said affine map codes for said domain child and said domain child subblock to be included in said set of affine map codes in response to said computed cost being less than said distortion measurement.
Claim 16
Dependent Claim
49 words
The method of claim 14 further comprising the steps of: determining all said affine map codes for said domain child sub-blocks are included in said set of affine map codes; and deleting said affine map codes for said domain child block from which said domain child sub-blocks are segmented.
Claim 17
Dependent Claim
48 words
The method of claim 15 further comprising the steps of: determining all said affine map codes for said domain child blocks are included in said set of affine map codes; and deleting said affine map codes for said domain block from which said domain child blocks are segmented.
Claim 18
Dependent Claim
31 words
The method of claim 16 further comprising the steps of: updating a bit rate multiplier in correspondence with a number of bits for codewords representing said set of affine map codes.
Claim 19
Dependent Claim
18 words
The method of claim 17 wherein said bit rate multiplier is restricted to a predefined amount of change.
Claim 20
Dependent Claim
28 words
The method of claim 18 further comprising the steps of: applying a vertical 7 tap filter to said current frame to interpolate said frame to said reduced size.
Claim 21
Independent Claim
201 words
A method for compressing data comprising a luminance/chrominance (YUV) image comprising the steps of: segmenting a luminance (Y) component of a current frame into a plurality of domain blocks; processing a first domain block of said Y component to determine distortion measurements between said first domain block and one of a range block and a vector quantization (VQ) block in a VQ table; determining costs for affine map codes corresponding to domain block/range block combinations and domain block/VQ block combinations; selecting a set of affine map codes to represent said first domain block of said Y component, said selected set corresponding to a least cost; selecting said affine map codes to be a do nothing code in response to a cost for a do nothing code being less than said cost for said set of affine map codes for domain block/range block combinations and domain block/VQ block combinations which represent said domain block; and determining said set of affine map codes for said first domain block of said chrominance components (U and V) to be do nothing codes in response to said set of affine map codes for said first domain block of said Y component being a do nothing code.
Claim 22
Independent Claim
201 words
A method for compressing data comprising a luminance/chrominance (YUV) image comprising the steps of: segmenting a luminance (Y) component of a current frame into a plurality of domain blocks; processing a first domain block of said Y component to determine distortion measurements between said first domain block and one of a range block and a vector quantization (VQ) block in a VQ table; determining costs for affine map codes corresponding to domain block/range block combinations and domain block/VQ block combinations; selecting a set of affine map codes to represent said first domain block of said Y component, said selected set corresponding to a least cost; selecting said affine map codes to be a do nothing code in response to a cost for a do nothing code being less than said cost for said set of affine map codes for domain block/range block combinations and domain block/VQ block combinations which represent said domain block; and determining said set of affine map codes for said first domain block of said chrominance components (U and V) to be do nothing codes in response to said set of affine map codes for said first domain block of said Y component being a do nothing code.
Claim 23
Dependent Claim
121 words
The method of claim 20 further comprising the steps of: processing a next domain block of said Y component to determine a set of affine map codes to represent said next domain block; processing a next domain block of said U and V components to determine a set of affine map codes to represent said next domain block of said U and V components in response to said set of affine map codes for said next domain block for said Y component not being a do nothing code; and continuing to process domain blocks in said Y, U, and V components until a set of affine map codes for all domain blocks of all components of said image have been processed.
Claim 24
Dependent Claim
100 words
The method of claim 21 further comprising the steps of: determining a least distortion measurement between said domain block in said current frame and a plurality of corresponding range blocks in a previous frame; comparing said least distortion measurement to a threshold to determine whether a next level of said domain block is evaluated; selecting said set of affine map codes corresponding to said domain block and range block combination to represent said domain block in response to said least distortion measurement being less than said threshold; and determining a level 0 cost for said set of affine map codes.
Claim 25
Dependent Claim
128 words
The method of claim 22 further comprising the steps of: segmenting said domain block comprising said next level into domain child blocks; determining a best correspondence for said domain child blocks and a block in said previous frame buffer; computing a distortion measurement between each domain child block and a portion of said domain block corresponding to said domain child block; computing a pixel mean difference for each said domain child block; comparing a cost of a set of affine map codes for each pixel mean difference and a cost of a set of affine map codes for said best correspondence for said domain child block; and selecting one of said sets of affine map codes to represent said domain child block that corresponds to said least cost.
Claim 26
Dependent Claim
19 words
The method of claim 23 wherein said next level is comprised of four non-overlapping quadrants of said domain block.
Claim 27
Dependent Claim
34 words
The method of claim 24 further comprising the steps of: comparing said distortion measurement for said domain child block to a threshold to determine whether a second level of said domain block is evaluated.
Claim 28
Dependent Claim
95 words
The method of claim 25 further comprising the steps of: determining a best correspondence between a plurality of domain child sub-blocks comprising said second level of said domain block and a corresponding plurality of range child sub-blocks in said second level, said best correspondence for a domain child sub-block and a range child block corresponding to a lowest distortion measurement; determining affine map codes for each best correspondence of said second level of said domain block; and determining a cost for each set of affine map codes for each best correspondence for said second level.
Claim 29
Dependent Claim
77 words
The method of claim 26 further comprising the steps of: generating additional levels of said domain block; determining best correspondences for blocks in said additional levels of said domain block; selecting affine map codes for each best correspondence for each block in said additional levels; computing a cost for said selected affine map codes; and terminating said level generating step in response to said blocks of a lower level having a size less than said predetermined minimum.
Claim 30
Dependent Claim
82 words
The method of claim 27 comprising the steps of: selecting affine map codes for said best correspondences for said lowest level having a cost less than said distortion measurement for a portion of a previous level block corresponding to said lowest level block; and computing a sum of costs for said selected affine map codes for one of a preceding level block and said selected affine map codes for said lowest level blocks corresponding to said one of said preceding level block.
Claim 31
Dependent Claim
101 words
The method of claim 22 wherein said determining distortion measurement step further comprises the steps of: selecting a set of no motion affine map codes for a domain block/range block combination corresponding to a no motion distortion measurement; selecting a set of local search affine map codes for a domain block/local search range block combination corresponding to a best local search distortion measurement; selecting a set of checkerboard affine map codes for a domain block/checkerboard search range block combination corresponding to a best checkerboard search distortion measurement; selecting one of said sets of affine map codes corresponding to a least cost.
Claim 32
Dependent Claim
59 words
The method of claim 29, wherein said step of selecting said set of no motion affine map codes further comprises the steps of: computing a distortion measurement between said domain block and said range block; selecting a set of affine map codes corresponding to said distortion measurement; and determining a cost for said selected set of affine map codes.
Claim 33
Dependent Claim
173 words
The method of claim 30, wherein said step of selecting said set of local search affine map codes further comprises the steps of: determining a local search range area in said reference frame; selecting a local search range block in said local search range; computing a distortion measurement between said domain block and said local search range block; determining a distortion measurement between said domain block and each local search range block in said local search range area by selecting each local search range block in said local search area and computing said distortion measurement; selecting a set of local search affine map codes for one of said domain block/local search range block combinations corresponding to a least distortion measurement; determining a cost for said selected local search affine map codes; and comparing said cost for said selected set of local search affine map codes to said cost for said set of no motion affine map codes to determine whether said local search affine map codes are used to represent said domain block.
Claim 34
Dependent Claim
163 words
The method of claim 31, said step of selecting said set of checkerboard affine map codes further comprising the steps of: determining a checkerboard range area in said reference frame; selecting a checkerboard range block in said checkerboard range; computing a distortion measurement between said domain block and said checkerboard range block; determining a distortion measurement between said domain block and each checkerboard range block in said checkerboard range area by selecting each checkerboard range block in said checkerboard range area and computing said distortion measurement; selecting a set of checkerboard affine map codes for one of said domain block/checkerboard range block combinations corresponding to a least distortion measurement; determining a cost for said selected set of checkerboard affine map codes; comparing said cost for said selected set of checkerboard affine map codes to said cost for said set of selected no-motion or local search affine map codes to determine whether said checkerboard affine map codes are used to represent said domain block.
Claim 35
Dependent Claim
222 words
The method of claim 32 further comprising the steps of: segmenting said domain block into a plurality of domain child blocks; computing a mean pixel difference for each domain child block; computing a mean pixel distortion measurement for each said domain child block; computing a cost for affine map codes for each mean pixel difference; selecting a range area in said reference frame so that each domain child block has a corresponding range area; measuring a distortion measurement between each domain child block and each range block in said range area corresponding to each said domain block; determining a least distortion measurement for each domain child block and a corresponding cost for a motion vector corresponding to said domain child block/range child block combination having said least distortion measurement; comparing, to determine a least cost, said cost for said affine map codes for each mean pixel difference for each said domain child block to said cost for said motion vector corresponding to said domain child block/range child block combination having said least distortion measurement; and selecting for each domain child block one of said affine map code for said mean pixel difference and said affine map code for said motion vector which corresponds to said least cost so that each domain child block is represented by one of said affine map codes.
Claim 36
Dependent Claim
161 words
The method of claim 33 further comprising the steps of: segmenting said domain child blocks into a plurality of domain child sub-blocks; computing a q parameter for each domain child sub-block; computing a distortion measurement between each said domain child sub-block and each VQ block of a VQ table; determining a least distortion measurement for each domain child sub-block; selecting a VQ identifier and a q parameter corresponding to said block yielding said least distortion measurement; computing a domain child sub-block cost corresponding to said VQ identifier and said q parameter for each said domain child sub-block; comparing said domain child sub-block cost to said distortion measurement for a portion of said domain child block; and selecting said VQ identifier and said q parameter corresponding to said VQ block in said VQ table in response to said domain child sub-block cost being less than said distortion measurement for a portion of said domain child block corresponding to said domain child sub-block.
References Cited (Backward Citations)
US4941193A
Cited
US5105271A
Cited
US5432556A
Cited
US5214504A
Cited
US5477272A
Cited
US5576772A
Cited
WO1995020296A1
Cited
US5457495A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-01 | 2002-08-03 | 2003-02-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-01 | 2006-08-03 | 2007-02-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-01 | 2010-08-03 | 2011-02-02 | $7700.00 | Window Closed / Lapsed |