Hierarchical variable block size address-vector quantization using inter-block correlation

• US 5,060,285 A
• Filed: 05/19/1989
• Issued: 10/22/1991
• Est. Priority Date: 05/19/1989
• Status: Expired due to Term

• Current Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Original Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Inventors: Dixit, Sudhir S., Feng, Yushu
• Primary Examiner(s): Razavi, Michael
• Application Number:
  US07/354,646
• Time in Patent Office: 886 Days
• Field of Search: 302/56, 302/54, 302/21, 302/50, 302/37, 302/38, 358/452, 358/433, 358/432, 358/429, 358/262.1, 358/261.4, 358/261.3, 358/453, 358/133, 358/448, 358/467, 375/25, 375/26, 381/29, 381/30, 381/34, 381/35
• US Class Current: 382/253
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

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.

Claims

1. 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.

2. 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.

3. The method of claim 1 wherein said maximum size block contains N layers

4. The method of claim 2 wherein said maximum size block contains 2^N-l M×

2^N-l M pixels.

5. 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.

6. The method of claim 1 wherein said first layer code book contains 128 vectors.

7. The method of claim 1 wherein said second layer code book contains 1024 address vectors.

8. The method of claim 1 wherein said second layer code book contains an number of address vectors.

9. The method of claim 1 wherein said third layer code book contains φ

address vectors.

10. The method of claim 1 wherein said third layer code book contains any number of address vectors.