WO2001059934A1

WO2001059934A1 - System and method for image compression using systolic vector quantization

Info

Publication number: WO2001059934A1
Application number: PCT/US2000/010910
Authority: WO
Inventors: George William Dalke
Original assignee: Splash Technology, Inc.
Priority date: 2000-02-11
Filing date: 2000-04-21
Publication date: 2001-08-16
Also published as: EP1262024A1

Abstract

A modified vector quantization compression scheme parses image data into a plurality of cells. A plurality of codebooks are developed in accordance with the nature of the image data, and each cell is associated with one of the plurality of codebooks. The codebooks may have different numbers of coding bits. The image data of each cell is compressed in accordance with the associated codebook. Appropriate sizing of the cells and the associated codebooks provides for overall image compression.

Description

IN THE UNITED STATES PATENT AND TRADEMARK OFFICE

APPLICATION

FOR

UNITED STATES PATENT

FOR

SYSTEM AND METHOD FOR IMAGE COMPRESSION USING SYSTOLIC VECTOR QUANTIZATION

INVENTOR: GEORGE WILLIAM DALKE

SPECIFICATION

Field of the Invention

This application relates generally to data compression methods, and more particularly relates to vector quantization compression methods asnjsed with color printers

BACKGROUND OF THE INVENTION

Vector quantization is used in many applications involving, generally, statistical pattern recognition such as image and voice compression and voice recognition or speech Vector quantization is a data compression method where a set of data points is encoded by a reduced set of reference vectors

In general, a vector quantizer maps k-dimensional vectors in the vector space Rk into a finite set of vectors Y = {yι, i = 0 1 , n-1 } Each vector yi is called a code vector or a codeword and the set of all the codewords is called a codebook Associated with each codeword yi is a nearest neighbor region called Voronoi region and it is defined by V_t =

e R^k : \\x -

-y_J l for ll j ≠

The set of Voronoi regions partition the entire space R^k such that:

N

For example, for a quantity of vectors in two dimensional space arranged in a number of clusters, associated with each cluster of vectors is a representative codeword. Each codeword resides in its own Voronoi region. For a given input vector, the codeword chosen to represent it is the one for that Voronoi region.

A vector quantizer essentially comprises two operations. The first is encoding, while the second is decoding. The encoding process operates on an input vector and outputs the index of the codeword that offers the lowest distortion. "Lowest distortion" is frequently a subjective matter where VQ is involved, since image quality is often a subjective matter determined by each individual viewer. However, in one simplistic approach, the distortion may be found by evaluating the Euclidean distance between the input vector and each codeword in the codebook. Oevcejthe closest codeword is found, the index of that codeword is sent through a channel (the channel could be a computer storage, communications channel, and so on). When the encoder receives the index of the codeword, it replaces the index with the associated codeword. Then, to reconstruct the image or other original data, the decoding process operates in substantially the reverse of the encoding process The decoder receives the index of the codeword, and outputs the codeword. The most common implementation of VQ may be the use of a lookup table for example, if the data is partitioned into a series of vectors of n bits each is to be encoded into an m bit vector, encoding typically consists of an n x m lookup table or other algorithm, while decoding is an m x n lookup table or algorithm The process flow may be further appreciated from Figure 1A, where the source data 100 of n-bit vectors is encoded by an n x m lookup table to yield a series of m-bit vectors Then, to decode, the m-bit vectors are processed by the m x n lookup table to reconstruct the target data of n-bit vectors Stated differently as in Figure 1 B a vector V is encoded by an encoder 150 to yield a code C. The code C is eventually supplied via a channel to a decoder, where the code C is decoded to a vector V. In an implementation of VQ using a look-up table for the decoder, where nc is the number of bit in the code_, and nv is the number of bits in the vector V, the lookup table consists of 2^nc words of nv bits each. In a conventional VQ implementation where explicit loading to the decoder look-up table is part of the communication, the time sequence is "Load table, Code 0, Code 1 , ... Code n-1." Such a prior art arrangement is shown in Figure 1C.

A significant difficulty with VQ is determining the number of codewords necessary to best represent a given set of input vectors. An exhaustive search for the best possible set of codewords in space increases exponentially as the number of codewords increases. As a result, a number of alternative codebook schemes have been developed. Each of these schemes suffers from some limitations. In print images, quantizing artifacts, sometimes referred to as "postenzation," typically occur with many VQ schemes.

For a bilevel, one-bit-per pixel image, a typical compression scheme is to divide the image into cells of 4x4 pixels. The 16 bits for each cell are the input vector. While simple images of, for example, black text on a white background, can be compressed a modest amount, halftone images cannot be compressed in a such a scheme without visible degradation. For a continuous tone, 8-bit/pixel image, the number of bits per cell rapidly becomes overwhelmingly large. For example, the following table shows the rapidity of increase in the number of bits/cell for several cell sizes:

Cell Size Vector Size Encode Table Size

1x1 8 256

2x2 32 4,283, 170,816

4x4 128 huge

The result is that, for useful cell sizes and compression ratios, compromises must be made which have typically resulted in artifacts

Efforts have been made in the prior art to reduce quantizing artifacts through the use of stochastic dithering, structured dithering, or by error diffusion However most continuous tone printers typically use some form of dithering to reduce quantizing artifacts and dithering the data in such a manner can cause interaction which results in moire patterns or other visual effects As a result conventional approaches to overcoming quantizing artifacts with these corrections a^re inadequate for many continuous tone printers There has thus been a long-felt need for a compression scheme compatible with continuous tone images.

SUMMARY OF THE INVENTION The present invention overcomes the limitations of the prior art by dividing the image to be compressed into multiple regions or cells, and then calculating an independent codebook for each region. It has been discovered that independent codebooks may be used with small adjacent regions while at the same time avoiding significant quantizing artifacts. By including the codebooks as part of the file, file size increases with increasing numbers of codebooks. However, codebook size and therefore file size both reduce rapidly with decreasing numbers of code bits. In addition, by using multiple independent codebooks, quantizing artifacts get smaller as cell size gets smaller. As a result, the loss of compression due to multiple codebooks can be more than offset by the increase in compression resulting from using fewer bits. This result occurs for cells small enough to eliminate quantizing artifacts, but large enough to provide a desirable level of compression.

By using the technique for each color plane of a color image, the system and method of the present invention provides an improved compression algorithm for generating color images, for example images suitable for 600 dpi, eight bits/pixel color printers.

The foregoing and other advantages of the present invention may be better appreciated from the following Detailed Description of the Invention, taken in conjunction with the attached Figures as described below

THE FIGURES

Figures 1A-1 C show a prior art implementation of vector quantization encoding and decoding.

Figures 2A-2B show an implementation of an encoder and decoder suitable for use with the present invention

Figure 3 shows in flow diagram form an embodiment of the transfer sequence when the codebook and associated codes are downloaded in accordance with the present invention

DETAILED DESCRIPTION OF THE INVENTION

Referring first to Figure 2A-2B, an implementation of an encodei and decoder system for use with the present invention may be better appreciated. It will be appreciated that Figures 2A-2B are typically implemented within the functionality of a microprocessor-based system where a microprocessor communicates with memory to process instructions stored therein and provides an output determined by the processed instructions and the supplied inputs.

With particular reference to Figure 2A, a vector V is supplied to an encoder function 200, which may, for example, comprises an algorithmic encoder. The encoder function 200 outputs, in a manner described in greater detail hereinafter, a code C together with an associated codebook 215. The codebook 215 is essentially a look-up table that converts the input vector to a compressed format in accordance with the present invention. As with the arrangement shown in Figures 1A-1C, nc is the number of bits in the code, while nv is the number of bits in the vector V. The codebook 215 and associated code C comprise the compressed image information, which may then be supplied to any conventional storage medium or data manipulation process. As will be appreciated from the following discussion, a key aspect of the invention involves the generation of multiple codebooks and associated codes, rather than the single codebook of the prior art. These codebooks and associated codes are then provided as part of the communication

As shown in Figure 2B, the output from the encoder function is eventually supplied across a channel 230 to a decoder function 250 which, like the encoder function 200, is typically implemented in a microprocessor-based system which includes an input connected to a processor, a memory associated therewith and connected to one or both, and an output The decoder function 25f -which may be implemented as a lookup table, receives a string of codes C and associated codebooks 215, where the number of bits in the code remains nc, while the number of bits supplied is now nv^*2^nc The output vector V has nv bits However, as will be discussed in greater detail in connection with Figure 3, the sequence by which image data is handled now becomes

Load Table, Code 0, Code 1 , , Code n-1 Load Table, Code 0", Code 1 ', . Code n-1 ' etc

The output of the string of codes C and associated codebooks 215 are a decompressed version of the image data, and may for example, be supplied as an output vector for use in printing or similar processing An important aspect of the present invention is that the codebooks become part of the communication It can thus be seen that the present invention utilizes multiple codebooks and associated codes to provide an efficient compression algorithm suitable for use with color printers and the like from the following the process of establishing multiple codebooks in accordance with the present invention may be better appreciated. In general, the image is divided into a plurality of regions or cells. In keeping with the observation that independent codebooks for small adjacent regions do not cause quantizing artifacts, each of the regions is suitably small. The shape of each cell need not be square, but instead may be any shape.

For an image having a total of N pixels with n pixels per cell, the number of codebooks required is N/n. With such an arrangement, the effect on file size (or, conversely, compression ratio) from using multiple codebooks, with various numbers of code bits and for differing cell sizes, can be better appreciated from Table 1 , below, where an exemplary image of 1 k x 1 k pixels is assumed:

TABLE 1

Thus, it can be appreciated that a compression ratio of 6.4:1 may be achieved for a cell size of 8x8, with one code bit. It will be appreciated that one code bit represents two colors, which permits color printing of a single color plane. By repeating the process for each color plane, reasonable compression is provided It will also be noted, from Table 1 , that for a single color (0 code bits) the arrangement leads to 64^" 1 compression As cell size is reduced, the occurrence of αuantizing artifacts also decreases

Cell sizes less than 16x16 begin to be small enough to very substantially reduce such artifacts, and cell sizes of 8x8 afford substantially no such artifacts Therefore, Table 1 also provides the basis for several important observations

1 Cells small enough to eliminate quantizing artifacts can still be large enough to afford meaningful compression 2. In an implementation using multiple codebooks, each codebook may have a different number of code bits.

3. Unlike Vector Quantization methods using a single codebook, zero bit codes may still be useful where multiple codebooks with a variable number of code bits are used.

4. Compression ratios near 1 may still be useful because the resulting change in data format may enable effective secondary compression that would otherwise not be possible.

The substantial reduction of quantization artifacts is one important aspect of the present compression scheme. As noted previously, as cell size gets smaller, quantizing artifacts are also reduced. In the present invention, it has been discovered that, for sufficiently small cells, the number of code bits can also be significantly reduced without causing such artifacts. The use of multiple codebooks increases file size, but relative file size is reduced rapidly with reductions in the number of code bits. The result is that the loss of compression resulting from multiple code bits is more than offset by the improved compression of using fewer bits. Table 1 shows that cells small enough to very substantially reduce or eliminate quantizing artifacts are still large enough to provide net positive compression.

Reduction of Quantizing Artifacts The substantial reduction or elimination of quantizing artifacts results from two effects The first depends on the slope of the gradient; the second depends on the width of the intensity step. Gradient "size" as used herein means the length from the darkest to the brightest points; for purposes of this discussion, gradients are assumed to be linear in data value- Thus, a 256 level continuous tone printer at 600 dpi resolution has a gradient size of 0 43 inches The relationship between step width, in pixels, and gradient size can be appreciated from Table 2, shown below.

TABLE 2

Thus, for a constant value of an 8x8 cell, any gradient larger than 3.4 inches will have a quantizing artifact of 1/256. However, for gradients less than 3.41 , no artifacts will be visible since the physical width is only 8/600 inches.

Zero Bit and Variable Bit Encoding Table 1 , above, shows the compression achievable for 0 bits. Normally, a code of zero bits is only useful if the page being compressed has only a single grey level. However, for multiple small cells each having an independent codebook, zero bit codes may be useful to define some of the cells. For zero code bit coding, the optimum codebook is the cell average.

While zero bit coding can be satisfactory for some cells, it will not be satisfactory for other cells in a typical image. In accordance with one aspect of the present invention, the codebook associated with each cell may have a different number of code bits from codebooks associated with other cells. The number of code bits fora given cell would thus be based on the cell data and acceptable compression error. From Table 1 we also see that acceptable compression levels involve the use of 0 or 1 code bits. Thus, an algorithm must be established to select the number of code bits. It has been experimentally established that the relationship between contrast and resolution for 8x8 cells is that a viewer cannot distinguish between 8x8 resolution and 1x8 resolution when the contrast, C, across the cell is less that twenty percent. Thus, one acceptable algorithm, shown in Figure 3, involves dividing the image into a series of small cells at step 300, followed by determining, for each such cell, the maximum pixel value of the cell at step 305 and the minimum pixel value at step 310. At step 315, the difference between the maximum and minimum pixel values for that cell is compared to C If-the difference is less that C, 0 bit coding is selected at step 320, otherwise 1 bit coding is selected at step 325.

Secondary Compression Normally, compression near to or less than one is not useful. However, an additional advantageous aspect of the present invention is the possibility of using such low-level compression as a preprocessor for secondary compression One acceptable secondary compression scheme can include conventional vector quantization with an efficient algorithm for codebook generation An alternative secondary compression scheme is to use transition coding, which may be thought of a a priori vectors and is described below

It has been determined experimentally that application of the first level of compression to most cells results in single transitions - either in the horizontal or vertical direction In this context "single transitions" means that either all rows or all columns have only a single transition from 0 to 1 that is a pattern similar to 0, 0,1 1 The number of leading 0's and trailing 1 's may vary from row to row or column to column, but the pattern is basically the same. Thus, for an 8x8 cell, only 16 possible single or zero transition patterns exist, as shown in Table 3, below.

TABLE 3

Since only 16 patterns are possible, a four bit code can be used to select any one of them. Thus, a single or zero transition eight bit vector can be coded to four bits, or 2:1 compression. Table 4 shows the code size and compression for various sized vectors.

TABLE 4

Thus, for an 8x8 cell, the combined primary compression (from Table 1 ) and secondary compression (from Table 4) is 6 4 x 2 =12 8 In a preferred arrangement, where many of the cells have single transition edges, either horizontal or vertical, and are therefore suitable for secondary compression, a two entry codebook results In such a two entry codebook one of the codes is quantized, together with error diffusion to the second entry

A conventional algorithm for describing the optimum design procedure for a quantizer (encoder) and codebook (decoder) is the Lloyd I algorithm, in which a set of n quantizing intervals, usually linear, are initially established. The Lloyd I algorithm assumes that the probability distribution for the input data is known. The centroid of each interval is calculated, after which the centroids are used to derive a new set of quantizing intervals. Nevertheless, the Lloyd I algorithm is limited with respect to image compression because the optimization is based on minimizing a distortion function, which is based on data statistics. Images, however, are evaluated subjectively by each viewer's eyes, so that optimization of the algorithm for images must also include a vision function. By comparison, the present invention uses a small cell, which essentially provides a more precise knowledge of the statistics of the image. This permits a more direct calculation of the codebooks. For a cell of N data values, the values can be expressed as X = {xi}, where i = 0 N-1 , and where x = (0, ...,255). The average value of X is A, where A = Sum(xi)/N. In accordance with the foregoing notation, the code bits for a zero bit code book and a one bit code book can be directly calculated. The zero bit code vector is straightforward, and is simply the average value, A. The one bit code for a cell is M = {mi}, where i = (0,...,N-1) and mi = (0,1). From Figure 3, it can be appreciated that the elements of M are calculated as follows: mi = 0 if xi < A, else mi = 1 , where A is the average value of X

The codebook consists of two values (A1 , and A0), calculated as follows:

N1 = number of elements of M for which mi = 1

NO = number of elements of M for which mi = 0

The decoder algorithm is, similarly:

Output A1 if mi = 1

Output A0 if mi = 0

One difficulty with the foregoing algorithm is that it is subject to noise However, noise immunity can be added to the cell coding by adding hysteresis to the algorithm The hysteresis value d modifies the above algorithm as shown below

The elements of M are calculated as follows mi = 0 if xi < Ai, else mi = 1 , where now, Ai varies as follows Ai = A+d if mι-1 = 0, else Ai = A-d

If preferred for the particular implementation, hysteresis can be applied to only parts of a cell In a presently preferred implementation hysteresis is pp d to either columns or rows of the cell, and the direction of coding is alternated accordingly.

An exemplary strategy for creating codebooks for the 1 bit case is the following:

First, create the codes. This is typically accomplished by cluster analysis, but can also include spatial dithering or hysteresis (for noise suppression and to improve the probability of single transition edges.) A visual function or other criteria, such as preserving highlights, can also be used.

Second, calculate the two codebook values. These are generally the average value of all the pixels assigned to code 0 and the average value of all the pixels assigned to code 1. However, these values can be modified, for example to improve local contrast. A variety of modifications are possible as long as the selected values continue to satisfy the equation n0^*C0 + n1^*C1 = nt^*A, where A is the average pixel value for the cell, nt is the number of pixels in the cell, nO is the number of pixels assigned to code 0 and CO is the codebook entry for code 0, etc Once the codes and codebooks are created, the encoding process of the present invention includes these in the data stream. Then, the decoding process includes the time sequence of Figure 3, showing the transfer sequence when the codebook is downloaded, of loading the first table at step 300; loading, at step 310,

Code 0, Code 1 , and so on up through Code n-1 for that table; processing those codes at step 320; loading the next table at step 330, loading the associated codes at step 340, processing those codes at step 350, and so on as needed at step 360

For an 8x8 pixel case, 64 codes would be loaded after each codebook load

To better understand the present invention, the followϊhg— exemplary embodiment is provided, in which one bit and zero bit systolic vector quantization compression techniques are used The encoding in the present example also includes reduced resolution cells and allows runs of 0 bit VQ cells to be coded efficiently A zero bit cell may be referred to hereinafter as a constant cell

In the present exemplary arrangement, there are eight ways that a cell can be coded The descriptor record for generating a cell consists of data along with one of the following codes Each cell will have a single descriptor with the exception of the RV and RP code which can each generate up to 30 cells with a single descriptor P1 , Paint, full resolution entire cell P2, Paint, half resolution entire cell P4, Paint, quarter resolution entire cell RV, Generate n constant cells n = 1 30 each with the same value

RP Generate n constant cells n = 1 30 each with a different value VQ Vertical SVQ entire cell HQ, Horizontal SVQ, entire cell SQ, Standard SVQ, entire cell

Table 5, below, gives the number of bytes in the descriptor record for each of the 8 cell compression codes with the corresponding compression ratio. (Note that the compression ratios are just for the cells and do not include the overhead of the tile compression codes and the other required structures.) In Table 5, n is the number of tiles encoded in the RV or RB command.

TABLE 5

Table 6, below, gives the bit patterns for the cell compression codes. After detecting the code, the offset to the next code is determined implicitly In TableU, x = don't care While the x bits are not used for determining the code, they are used for 6 bit data values.

TABLE 6

Bit Pattern for Compression Byt e Offset to the compression codes Codes Next code xxxxxxOI HQ 7 xxxxxxl O VQ 7 xxxxxxl 1 SQ 1 1

00000000 P1 66

00000100 P2 1 8

00001000 P4 6 00011000 RV, n = 1 3

00010000 RV, n = 2 3

Etc. Etc. Etc.

10010000 RV, n = 30 3

10010100 RB, n = 1 3

10011000 RB, n = 2 3

Etc. Etc. Etc.

11111000 RB, n = 30 3 11111100 unused undefined

P1 data structure and decoding

P1 compression codes consist of a 65-byte descriptorthat is used to generate an 8x8 array of 8 bit pixels. The description of each byte and the names for the bits is given in the following Table 7.

TABLE 7

Byte number in 65 Byte Bit Labels Comment Descriptor

0 00000000 Code for PI

1 P00 First byte of 8x8 byte array etc etc etc __

64 P15, 15 Last byte of 8x8 byte array

The 8x8x8 array is read directly from the 64 data values following the P1 compression code

P2 data structure and decoding

P2 compression codes consist of a 17-byte descriptor that is used to generate an 8x8 array of 8 bit pixels The description of each byte and the names for the bits is given in the following Table 8 TABLE 8

Byte number in 17 Byte Bit Labels Comment Descriptor

0 00000100 Code for P2

1 P0,0 First byte of 4x4 byte array etc etc etc

16 P7.7 Last byte of 4x4 byte array

Replicating each byte of the 4x4 array twice horizontally and twice vertically generates the 8x8x8 array.

P4 data structure and decoding

P4 compression codes consist of a 5-byte descriptor that is used to generate a 2x2 array of 8 bit pixels. The description of each byte and the names for the bits is given in the following Table 9.

TABLE 9

Byte number in 5 Byte Bit Labels Comment Descriptor

0 00001000 Code for P4

1 P0,0 First byte of 2x2 byte array etc etc etc

4 P1 .1 Last byte of 2x2 byte array

Replicating each byte of the 2x2 array four times horizontally and four times vertically generates the 8x8x8 array

RV data structure and decoding

RV compression codes consist of a 2-byte descriptor that is used to generate a number of 8x8x8 constant tiles The description of each byte and the names for the bits is given in the following Table 10 TABLE 10

Byte number in Bit Labels comment 2 Byte Descriptor

0 xxxxxxOO Test xxx to see if this is a RV or RP or unused command. If X=xxxxxχ is greater than 2 and less than 33, then n = x-2 V Constant value for cells

The 8x8x8 constant array with value V is repeated n times.

RP data structure and decoding

RP compression codes consist of a variable length byte descriptor that is used to generate a number of 8x8x8 constant tiles. The description of each byte and the names for the bits is given in the following tables.

Byte number in Bit Labels Comment 2 Byte Descriptor

0 xxxxxxOO Test xxx to see if this is a RV or RP or unused command. If X=xxxxxx is greater than 32 and less than 63, then n = x-32

1 V0 Constant value for cells n Vn-1 Constant value for cells

The 8x8x8 constant array with value is repeated n times

HQ and VQ data structure and decoding

HQ and VQ compression codes consist of a 6-byte descriptor that is used to generate an 8x8 array of 8 bit pixels The description of each byte and the names for the bits is given in the following tables Byte number in 6 Bit Labels Comment

Byte

Descriptor

0 xxxxxxst X = xxxxxx is a 6 bit data value st = 01 for HQ, and st = 10 for VQ

1 vvvvvvvv V = wvvvvvv is an 8 bit data value 2 aaaabbbb A = aaaa, B=bbbb, 3 ccccdddd C = cccc, D = dddd 4 eeeeffff E = eeee, F = ffff 5 gggghhhh G ⁼ 99g . H = hhhh

The last four bytes of the data structure are interpreted as 8 four-bit values. Each of these 4 bit values generates an 8x1 pixel code by the following table (if required the codes can be reordered to simplify hardware generation.)

case 4 bit value Pixel codes

0 0000 00000000 1 0001 0000000 2 0010 0000001

3 0011 0000011 4 0100 0000111 5 0101 0001111 6 0110 0011111 7 0111 0111111 8 1000 1111111 9 1001 11111110

10 1010 11111100 1 1 1011 11111000 12 1100 11110000 13 1101 11100000 14 1110 11000000 15 1111 10000000

The 88x1 pixel codes are arranged in rows for HQ and in columns for VQ as shown in the following tables. This creates an 8x8x1 array.

For HQ:

For VQ:

The 8x8x1 array is converted to bytes via a 2x8 LUT with contents X, V This is, if a table value is 0, generate a pixel with value X, else generate a pixel with value V

In general, both V and X should be 8 bit values For the current coding scheme two bit of the first value X, are used for codes reducing X to a 6-bιt value This requires that the compression software assign appropriate values to X and V to avoid quantizing artifacts

SQ data structure and decoding

SQ compression codes consist of a 10-byte descπotoi that is used to generate an 8x8 array of 8 bit pixels. The description of each byte and the names for the bits is given in the following tables.

Byte number in 5 Bit Labels Comment

Byte Descriptor

xxxxxxst X = xxxxxx is a 6 bit data value

St = 0,0 for SQ

1 vvvvvvv V = = vvvvvvvv is an 8 bit data value 2 BO First row of the 8x8x1 array 3 B1 Second row of the 8x8x1 array 4 B2 Etc. 5 B3 Etc. 6 B4 Etc. 7 B5 Etc. 8 B6 Etc. 9 B7 Last row of the 8x8x1 array

The 8 bytes stored in bytes 2 through 9 form an 8x8x1 array. An 8x8x8 array is generated by selecting X when the bit array is 0 and V when it is 1 .

Having fully described a preferred embodiment of the invention and various alternatives, those skilled in the art will recognize given the teachir-rgsjierein, that numerous alternatives and equivalents exist which do not depart from the invention It is therefore intended that the invention not be limited by the foregoing description but only by the appended claims.

_******_*********

Claims

What is claimed is:

1. A data compression process including the steps of dividing an image into a plurality of cells, developing a codebook for each of the plurality of cells, at least some of the codebooks having the same number of coding bits, generating a compressed representation of each cell in accordance with the associated codebook.

2. The data compression process of claim 1 further including the step of repeating the dividing, developing and generating steps for each color plane of a color image.

3. The data compression process of claim 1 wherein the number of coding bits is zero or one

4. The data compression process of claim 3 wherein some of the code books have a different number of coding bits

5. The data compression process of claim 4 wherein the number of coding bits for all of the code books is zero or one

6 The data compression process of claim one further including the step of performing a secondary compression on at least some of the compressed representations

7 A data compression system comprising a data source for supplying image data, a processor for executing commands , a first storage device for supplying a sequence of commands wherein the commands include a command for parsing the image data into a plm ality of cells a command for associating with each cell one of a plurality of c odebooks and a command for compressing the image data of a selected cell in accordance with the associated codebook, and an output for supplying the compressed image data to a channel.

8. A computer program product comprising a computer usable medium having computer readable code embodied therein for causing image data to be divided into a plurality of cells and each such cell processed in accordance with an associated codebook, the computer program product comprising first computer readable program code devices configured to divide image data into a plurality of cells, second computer readable program code devices configured to associate one of a plurality of codebooks with each cell in accordance with a predetermined criteria, and third computer readable program code devices configured to compress the image data of a cell in accordance with the associated codebook.