Patent US5060285A successfully refreshed from Google Patents.
US5060285A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hierarchical variable block size address-vector quantization using inter-block correlation
Assignee: Verizon Laboratories Inc
•
Filing: 1989-05-19
•
Granted: 1991-10-22
•
Expires: 2009-05-19
Abstract
Abstract A vector quantization based image compression technique which exploits inter-block correlation and layered addressing structure to form variable block sizes. Without introducing any quality degradation, when compared to the traditional vector quantization algorithms, the invention described herein significantly increases the compression and reduces the bit rate. The concept of inter-block correlation is utilized to form variable size blocks, which are then coded using a hierarchical coding model. The method is based on starting off from a small basic block which is allowed to grow to a maximum of a preset block size as long as certain conditions are met. The basic idea of growing the block is based on the renormalization group theory in physics. The algorithm utilizes only one pixel code book for the basic block size and several address code books for the layer block sizes to encode an image. S/N ratio in excess of 30 dB at bit rates lower than 0.2 bpp are easily obtained.
Inventors
- 👤 Sudhir S. Dixit
- 👤 Yushu Feng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 18:51
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/90; H04N19/94; H04N19/96; H04N19/60; H04N19/61; H04N19/63
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
525 words
A method of compressing and reconstructing an image by a hierarchial variable block-size address-vector quantization, comprising the steps of: partitioning an image into basic blocks of equal size to form a first layer of blocks, each basic block having the same number of pixels; constructing a first layer pixel vector code book having a plurality of addressable entries, each entry representing a combination of elements which have appeared frequently in individual blocks of previously coded images; combining groups of adjacent basic blocks of said first layer to form a second layer of blocks; constructing an address code book for said second layer blocks having a plurality of addressable entries wherein said entries are addresses of combinations of code vectors in said first layer code book which have the highest probability of occurrence; determining a maximum block size and the number of layers N required to encode a maximum size block; if N≧2. combining groups of adjacent blocks from layer i-l to form a layer i block, where 1<i≦N; constructing an address code book for said ith layer of blocks having a plurality of addressable entries wherein said entries are those combinations of address vectors in said i-l layer code book which have the highest probability of occurrence; storing said code books such that they may be used for both compression and reconstruction of the same images; dividing each newly arriving image into blocks of maximum size; dividing each of said maximum size blocks of said newly arriving image into basic blocks; comparing each of said basic blocks of said maximum size block with said entries in said first layer vector code book to find the best matches of all said basic blocks in said maximum block; scanning said address code book of said second layer to determine if there is an entry representing combinations of addresses of the best matches of adjacent basic blocks in said first layer code book; if all basic blocks of said first layer within the larger block of said second layer can be encoded by a single address in said second layer address code book, combining adjacent blocks of said second layer to form a larger block of a third layer; scanning said address code book of said third layer to determine if there is an entry representing the combination of addresses of second layer blocks of the previous step; if such an entry exists, then repeating the iterative steps of combining the blocks of layer i-l to form a block of layer i; and scanning the address code book of layer i to find a single entry which represents the combination of addresses of blocks of layer i-l in said layer i block; terminating said iterative steps upon occurrence of one of the following events: the maximum block size is reached and encoded; all of the component blocks of a block in layer i cannot be encoded by a single address vector entry in the address code book of layer i; and sending a tree message with block combination information and the code book addresses of the encoded image to a receiver for reconstruction of said image after transmission.
Claim 2
Independent Claim
525 words
A method of compressing and reconstructing an image by a hierarchial variable block-size address-vector quantization, comprising the steps of: partitioning an image into basic blocks of equal size to form a first layer of blocks, each basic block having the same number of pixels; constructing a first layer pixel vector code book having a plurality of addressable entries, each entry representing a combination of elements which have appeared frequently in individual blocks of previously coded images; combining groups of adjacent basic blocks of said first layer to form a second layer of blocks; constructing an address code book for said second layer blocks having a plurality of addressable entries wherein said entries are addresses of combinations of code vectors in said first layer code book which have the highest probability of occurrence; determining a maximum block size and the number of layers N required to encode a maximum size block; if N≧2. combining groups of adjacent blocks from layer i-l to form a layer i block, where 1<i≦N; constructing an address code book for said ith layer of blocks having a plurality of addressable entries wherein said entries are those combinations of address vectors in said i-l layer code book which have the highest probability of occurrence; storing said code books such that they may be used for both compression and reconstruction of the same images; dividing each newly arriving image into blocks of maximum size; dividing each of said maximum size blocks of said newly arriving image into basic blocks; comparing each of said basic blocks of said maximum size block with said entries in said first layer vector code book to find the best matches of all said basic blocks in said maximum block; scanning said address code book of said second layer to determine if there is an entry representing combinations of addresses of the best matches of adjacent basic blocks in said first layer code book; if all basic blocks of said first layer within the larger block of said second layer can be encoded by a single address in said second layer address code book, combining adjacent blocks of said second layer to form a larger block of a third layer; scanning said address code book of said third layer to determine if there is an entry representing the combination of addresses of second layer blocks of the previous step; if such an entry exists, then repeating the iterative steps of combining the blocks of layer i-l to form a block of layer i; and scanning the address code book of layer i to find a single entry which represents the combination of addresses of blocks of layer i-l in said layer i block; terminating said iterative steps upon occurrence of one of the following events: the maximum block size is reached and encoded; all of the component blocks of a block in layer i cannot be encoded by a single address vector entry in the address code book of layer i; and sending a tree message with block combination information and the code book addresses of the encoded image to a receiver for reconstruction of said image after transmission.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein: the size of basic block is M×M pixels; and said basic blocks are recursively combined in groups of four.
Claim 4
Dependent Claim
13 words
The method of claim 1 wherein said maximum size block contains N layers
Claim 5
Dependent Claim
17 words
The method of claim 2 wherein said maximum size block contains 2 N-l M×2 N-l M pixels.
Claim 6
Dependent Claim
30 words
The method of claim 2 wherein each entry in an address code book of layer i, where 2≧i≧N, contains four addresses of vectors in a code book of layer i-l.
Claim 7
Dependent Claim
14 words
The method of claim 1 wherein said first layer code book contains 128 vectors.
Claim 8
Dependent Claim
15 words
The method of claim 1 wherein said second layer code book contains 1024 address vectors.
Claim 9
Dependent Claim
17 words
The method of claim 1 wherein said second layer code book contains an number of address vectors.
Claim 10
Dependent Claim
15 words
The method of claim 1 wherein said third layer code book contains φ address vectors.
Claim 11
Dependent Claim
17 words
The method of claim 1 wherein said third layer code book contains any number of address vectors.
References Cited (Backward Citations)
US4712140A
Cited
US4932066A
Cited
US4831659A
Cited
US4809350A
Cited
US4947447A
Cited
US4922349A
Cited
US4797739A
Cited
US4780761A
Cited
US4791654A
Cited
US4951157A
Cited
US5020120A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-10-21 | 1995-04-22 | 1995-10-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-10-21 | 1999-04-22 | 1999-10-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-10-21 | 2003-04-22 | 2003-10-22 | $7700.00 | Window Closed / Lapsed |