Abstract:
A method compresses a digital continuous tone image of pixels situated on scan lines. The method includes the steps of, for a current pixel to be encoded, said current pixel having an actual pixel value, predicting a predicted pixel value based on pixel values of at least one previously processed pixel from the same image, using a fixed rule, determining a difference parameter based on a difference value of said predicted pixel value and the actual pixel value of said current pixel to be encoded, and inspecting the difference parameter for existence of an uninterrupted series of highest order bits having a value equal to zero, removing at least part of said highest order zero bits, and, if a number of bits within predetermined limits remains, generating a compression code having a predetermined fixed length, said code indicating the number of remaining bits.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This nonprovisional application claims priority under 35 U.S.C. § 119(e) on U.S. Provisional Application No. 60/591,876, filed on Jul. 29, 2004. This nonprovisional application also claims priority under 35 U.S.C. §120 on International Application No. PCT/EP2005/008723, filed on Jul. 26, 2005. The entirety of each of these applications is incorporated herein by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to lossless compression of continuous tone images. More particularly, the invention provides a method of compressing a digital continuous tone image of pixels situated on scan lines, each pixel having a pixel value defined by at least one color channel value, a color channel value having B bits of precision (B&gt;1). It is to be understood that a color channel may also comprise a single black-and-white channel. 
         [0004]    The invention also relates to a computer program product for performing the method when run on a computer and an apparatus, in particular a print controller, in which the method is implemented. 
         [0005]    Finally, the invention relates to a method for decompressing image data that have been compressed with the present invention. 
         [0006]    2. Description of Background Art 
         [0007]    Pages sent to a printer are in general defined in a page description language (PDL). An example of a PDL is PostScript from Adobe Systems Inc. A PDL interpreter that runs on a computer interprets the PDL, resulting in a digital page image for each page to be printed. The page images can be in a form that can be directly passed to a print engine or they can be stored in the form of digital continuous tone images that may be further processed before they are passed to a print engine. The latter approach can be used for example when special image processing is needed, that is not available in the PDL interpreter, e.g. to convert the continuous tone image to a format that can be accepted by the print engine. 
         [0008]    For color printers that use the latter approach, the continuous tone image has to be stored and possibly transmitted to image processing hardware. However the amount of data for a continuous tone image can be very large, e.g. for a 600 dpi continuous tone (8 bits per color channel) CMYK image of A4 size, about 140 Mbytes is needed. This means that it takes a relatively large amount of storage to store the image and that it takes a relatively long amount of time to transport it. A general solution to this problem is to compress the continuous tone image. 
         [0009]    For example,  FIG. 11  shows a schematic of a print controller, also known as a “Raster Image Processor” (RIP) or “color server”. The print controller interprets print jobs (e.g. defined in PostScript), stores the page images on disk and transfers them from there to the printer engine when required. 
         [0010]    The color print controller contains a PDL interpreter  112  that interprets the incoming print job and converts it to uncompressed continuous tone color page images. Directly after generating the page images, they are compressed by the compressor  114  of the present invention. The resulting compressed page images are stored on a harddisk  116  which forms the page store. When the engine needs to print the job, the compressed page images are read from the harddisk and transferred to the engine through a printer interface cable  118  (e.g. Firewire). 
         [0011]      FIG. 12  shows a printer connected to the print controller of  FIG. 11  through the printer interface cable  118 . 
         [0012]    The compressed page images from the print controller are received in a buffer  122 . From there, the compressed image data is passed to the decompressor  124  that converts the compressed page image to an uncompressed image. The uncompressed image is passed through the image processing module  126  to convert it to engine specific bitmaps that are used to drive the printer engine  128 . 
         [0013]    The fact that the image data is compressed directly after the PDL interpreter, saves bandwidth in the transfer of the images to and from the harddisk, allowing a slower disk to be used than would be needed for uncompressed data. It also allows for a smaller disk. Also, the bandwidth needed to transfer the images over the printer interface cable is reduced, so an interface with less available bandwidth can be used. 
         [0014]    Various lossless image compression techniques are available for compression of continuous tone images, for instance JPEG-LS. 
         [0015]    JPEG-LS is based on HP&#39;s LOCO-I algorithm and has been selected by the ISO/ITU-T as a standard for lossless compression of continuous tone images. A description of the algorithm is given in: M. Weinberger, G. Seroussi, G. Saipiro, “LOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithm”, available on www.hpl.hp.com/loco/HPL-98-193R1.pdf 
         [0016]    However, the compression techniques that provide a reasonable amount of compression take considerably more time to compress an image than it takes for the PDL interpreter to generate the same image when executed on the same computer. This implies that if such a compression method would be used to compress the page images, the performance of the printer would drop to unacceptable levels. 
         [0017]    Existing techniques that are fast enough (e.g. simple 1-dimensional run-length compression) do not provide enough compression on average. 
       SUMMARY OF THE INVENTION 
       [0018]    It is an object of the invention to provide a low complexity software solution that can be implemented efficiently on a general purpose processor and that allows lossless compression of PDL generated images, with an execution time that is considerably less than the time it takes a PDL interpreter to generate the image on the same computer. 
         [0019]    This would allow compression to be implemented on the same computer as used to run the PDL interpreter, without additional hardware and without large performance penalties. 
         [0020]    It is a further object of the invention to provide a low complexity compressor having compression factors that are at least as good as state of the art lossless image compression algorithms. 
         [0021]    It is a further object of the invention to allow for a simple hardware implementation of the de-compressor. 
         [0022]    According to the method of the invention, the pixel values are compared to predicted pixel values predicted on the basis of neighboring pixels. Since in many cases pixel values do not change rapidly over position, the difference between actual and predicted pixel values is normally small, and will have several, if not many, leading zero bits. By cutting off the leading zero bits, the data is brought back to less bits, which effectively leads to compression. 
         [0023]    Further advantageous aspects of the invention include steps used to prepare the image data in such way that the resulting differences between actual and predicted pixel values become even smaller, resulting in still better compression. 
         [0024]    The compression is optimized for PDL-generated images, but it may also be advantageously applied to other kinds of digital images, e.g. scanned images. 
         [0025]    Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0026]    The present invention will become more fully understood from the detailed description given hereinbelow and the accompanying drawings which are given by way of illustration only, and thus are not limitative of the present invention, and wherein: 
           [0027]      FIG. 1  illustrates image pixels scaled to a double resolution by a typical PDL interpreter; 
           [0028]      FIG. 2  illustrates an organization of data blocks and code blocks for a scanline as generated according to the invention; 
           [0029]      FIG. 3  illustrates an example of the interpretation of run-length fields in run-length codes according to the invention; 
           [0030]      FIG. 4  illustrates an explanation of PREV and LEFT colors in a scan line of pixels; 
           [0031]      FIG. 5  illustrates examples of predictors; 
           [0032]      FIG. 6  is a flow chart describing the compression method for color values according to a first embodiment of the invention; 
           [0033]      FIGS. 7A and 7B  are a schematic representation of the combination of color channel data in the first embodiment; 
           [0034]      FIG. 8  is a flow chart describing the complete compression method according to a first embodiment of the invention; 
           [0035]      FIG. 9  is a flow chart describing the complete compression method according to a second embodiment of the invention; 
           [0036]      FIG. 10  is a flow chart describing the compression method for gray values according to a second embodiment of the invention; 
           [0037]      FIG. 11  is a schematic of a print controller; and 
           [0038]      FIG. 12  is a schematic of printer. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     General Aspects of the Compression According to the Invention 
       [0039]    The present invention is basically intended for compression of page images generated by a PDL (Page Description Language, such as Postscript) interpreter. Such images have specific characteristics, which are described below. The compression is optimized for these images, but it may also be applied to other kinds of digital images, e.g. scanned images. In the latter case, scanner noise negatively affects the compression ratio, but tests have revealed that a reasonable compression ratio is still attainable. A noise-suppressing pre-processing step would in this case improve the result, since it would increase the opportunities for run length compression, although the compression would then no longer be lossless. 
         [0040]    Further, the compressor according to the present invention has been implemented in software, such that the execution time needed for compressing an image is, on average, considerably smaller than the time it takes to generate the same image by a PDL interpreter on the same computer. This allows the compressor to be implemented on the same computer that runs the PDL interpreter, without requiring additional hardware and without a large performance penalty. 
         [0041]    The compressed format is simple, so as to allow for a simple implementation of the de-compressor in hardware. This implies among others that the amount of memory needed for the decompressor can be limited. 
         [0042]    Also, the compressor has been designed such that it is possible for a hardware-implemented decompressor to produce decompressed pixel data at a fixed rate. This implies that the maximum local expansion of the compressed data must be limited. 
       Image Characteristics of Images to be Compressed 
       [0043]    The images to be compressed are color or black-and-white continuous tone images that are preferably generated by a PDL interpreter. Unless specifically defined otherwise, the term “color” relates to both real color tones and black-and-white gray tints in the following description. PDL-generated images have certain typical characteristics: 
         [0044]    In areas of constant color (e.g. the white background in many pages), there is no noise. This means that for compressing areas of constant color we can use simple mechanisms like run-length encoding for compression. 
         [0045]    For scaling sampled images to the device-resolution, most PDL&#39;s (like PostScript) use nearest neighbor interpolation. Nearest neighbor interpolation gives the device pixels the color of the original pixel that is closest to the device pixel. E.g., as shown in  FIG. 1 , for a 300-dpi image in a PostScript job printed on a 600 dpi device, each original pixel is mapped onto 2 by 2 device pixels. 
         [0046]    A first embodiment of the present invention, which is a compression method intended for colored images, will now be described. 
       Compressed Image Format in the First Embodiment 
       [0047]    The compressed image format consists of a sequence of bytes each containing two 4-bit nibbles. The first nibble in each byte is the high order 4 bits of the byte; the second nibble in each byte is the low order 4 bits of the byte. A nibble is the smallest unit of data in the compressed image format in this first embodiment. The reason for working with nibbles as smallest unit of data rather than with bits is because nibbles can be handled more efficiently on a general-purpose processor than single bits. All numbers that consist of multiple nibbles are represented with the highest order nibble first and the lowest order nibble last. 
         [0048]    The compressed image format is organized as a sequence of information blocks that each describe one scanline, in the order in which the scanlines occur on the page. The reason for choosing a scanline-wise organization (vs. a page-wise organization) is that it allows for processing on a scanline basis without having to store a complete compressed page image. 
         [0049]      FIG. 2  shows an example of the basic form of an information block for a scanline. Each information block consists of a data block immediately followed by a code block. 
         [0050]    The first 4 nibbles in both the data and the code blocks each form a length field that specifies the length of the data/code block in multiples of 8 bytes. This length field is immediately followed by the actual code/data nibbles. Any unused nibble values at the end of a block are set to 0. A data/code block can be at most (2̂−1)*8=524288 bytes long. The length field allows navigation of the compressed data on a scanline basis (fast skipping of scanline data). 
         [0051]    The code blocks contain a sequence of code nibbles that are instructions to the decompressor, specifying the pixels to be generated, starting with the first pixel on the scanline and working towards the last one. 
         [0052]    Some codes in a code block require additional data. This additional data is stored in the data block, in the same order as the corresponding codes appear in the code block for the same scanline. 
       Compression Codes Used in the First Embodiment 
       [0053]    Given the properties of PDL-generated images (larger areas of constant color without noise), a 2-dimensional run length encoding will compress many PDL-generated images well. However pages containing sampled images (e.g. photo&#39;s) generally have many different colors and many pixels have a color that is not equal to their previously processed neighbor pixels so run length encoding will not perform well. Additional codes are necessary for such situations. The present invention provides a method that performs well in both said situations. 
         [0054]    First, a basic 2-dimensional run length compression method with dedicated codes according to the invention will be described. 
       LEFT Code 
       [0055]    We define a code LEFT that indicates that the current pixel has the same color as its left neighbor. We add a run length to this code to indicate that the code should be repeated several times. This is the run length encoding in the first dimension. A code LEFT as the first run on a scanline indicates that the corresponding pixels have the color white. 
       TOP Code 
       [0056]    To make the run-length encoding2-dimensional, we define a code TOP that indicates that the current pixel has the same color as the pixel above. We add a run length to this code to indicate that the code should be repeated several times. This is the run length encoding in the second dimension. A code TOP on the first scanline indicates that the corresponding pixels have the color white. 
         [0057]    Note that this code is very helpful in compressing pages containing sampled images at e.g. half the device resolution. Due to the nearest neighbor interpolation of PostScript/PDF, after scaling to the device resolution, for such an image every second scanline is the same as the scanline above (see  FIG. 1 ). This means that, in this case, every second scanline within such an image can be compressed using a TOP run. 
       NEW Code 
       [0058]    Since we will not be able to use code TOP or LEFT to encode every pixel we will have to add a code that produces a pixel of a new color, which is specified in the compressed data. Code NEW indicates that the current pixel has a color specified as an uncompressed color value in the data block in the order C, M, Y, K, with the high order nibbles first. For each of the four color channels, value 0 corresponds to no ink coverage and value 255 corresponds to full ink coverage. 
         [0059]    In order to reduce the worst-case expansion of the compressed format (to allow a simple hardware decompressor), we add a run length to this code to indicate that the code should be repeated several times. 
       Adding the Run Length 
       [0060]    As mentioned, each of the codes LEFT, TOP and NEW above has a run length added. The distribution of the probabilities of the run length values is roughly negative-exponential. 
         [0061]    A simple way of adding a run length would be to add an extra nibble that specifies the run length. However that would mean that each code would become 2 nibbles long (the first for the code and the second for the run length). It would also mean that there is considerable redundancy in the code since e.g. a code TOP with run length 1 followed by a code TOP of run length 1 would have the same meaning as a code TOP with run length 2. 
         [0062]    In order to prevent these problems we interpret successive occurrences of the same code as one run. In each of the code values for codes LEFT, TOP and NEW, we reserve 1 bit for the run length, to be referred to as L. 
         [0063]    Several successive codes LEFT, TOP or NEW are interpreted together by concatenating the run length bits in each of the codes to form a binary number. An offset value that depends on the number of successive codes is added to the number to form the actual run length value. 
         [0064]    The result is that with a single code nibble we can specify a TOP, LEFT or NEW run of length 1 or 2. With 2 nibbles we can specify a run of length 3, 4, 5 or 6, etc. Table 1 below shows the interpretation of the concatenated run length bits. 
         [0000]    
       
         
               
             
               
               
               
             
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Interpretation of concatenated run length bits 
               
             
          
           
               
                 Nr of 
                   
                   
               
               
                 nibbles 
                 Value of concatenated L bits 
                 Resulting length 
               
               
                   
               
             
          
           
               
                 1 
                 0-1 
                 1-2 
               
               
                 2 
                 00-11 
                 3-6 
               
               
                 3 
                 000-111 
                  7-14 
               
               
                 4 
                 0000-1111 
                 15-30 
               
               
                 5 
                 00000-11111 
                 31-62 
               
               
                 6 
                 000000-111111 
                  63-126 
               
               
                 7 
                 0000000-1111111 
                 127-254 
               
               
                 8 
                 00000000-11111111 
                 255-510 
               
               
                 9 
                 000000000-111111111 
                  511-1022 
               
               
                 10 
                 0000000000-1111111111 
                 1023-2046 
               
               
                 11 
                 00000000000-11111111111 
                 2047-4094 
               
               
                 12 
                 000000000000-111111111111 
                 4095-8190 
               
               
                 13 
                 0000000000000-1111111111111 
                  8191-16382 
               
               
                 14 
                 00000000000000-11111111111111 
                 16383-32766 
               
               
                 15 
                 000000000000000-111111111111111 
                 32767-65534 
               
               
                 16 
                 0000000000000000-111111111111111  
                  65535-131070 
               
               
                   
               
             
          
         
       
     
         [0065]    In  FIG. 3 , an example is shown of how a sequence of NEW, LEFT and TOP codes and their run lengths is interpreted. As an example we decode the hexadecimal string EDCCDDBA. 
         [0066]    Next, non-runlength codes are described that may be used in addition to the TOP, LEFT and NEW codes described above. 
         [0067]    PREV Code 
         [0068]    In order to allow efficient compression of full-resolution binary sampled images on the page, code PREV is added which produces one pixel with the PREV color as defined below. 
         [0069]    Initially for each scanline the PREV color is set to K-black (C=0, M=0, Y=0, K=255). 
         [0070]    Every time the LEFT color changes to a different color, the PREV color is set to the old value of the LEFT color. 
         [0071]      FIG. 4  shows an exemplary scanline of which the first 5 pixels have color yellow, the second 5 pixels have color cyan and the third 5 pixels have color magenta. Then at the first pixel, the PREV color is K-black and the LEFT color is white. At the second up to the 6 th  pixel, the PREV color is white and the left color is yellow. At the 7 th  pixel up to the 11 th  pixel, the PREV color is yellow and the LEFT color is cyan. At the 12 th  up to the 16 th  pixel, the PREV color is cyan and the left color is magenta. 
         [0072]    If the color on a scanline alternates between 2 colors (e.g. black and white) the PREV code can be used to specify the color for every color transition on the scanline. This code produces 1 pixel so no run length is needed. 
       TOPL, TOPR Codes 
       [0073]    Code TOPL specifies that the current pixel has the same color as its neighbor to the northwest. Code TOPR specifies that the current pixel has the same color as its neighbor to the northeast. These codes produce 1 pixel so no run-length is needed. 
         [0074]    Table 2 below shows the codes we have defined up to now. The numbering is arbitrary and reflects the final numbering of the codes. Codes 1 to 7 (“0 0 0 1” to “0 1 1 1”) are still available. 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Codes defined for 2 dimensional run length encoding 
               
             
          
           
               
                   
                 Code 
                 Name 
                 Description 
               
               
                   
                   
               
               
                   
                 0 0 0 0 
                 PREV 
                 Previous color on this scanline, 1 pixel 
               
               
                   
                 1 0 0 0 
                 TOPL 
                 Color of pixel to the north-west, 1 pixel 
               
               
                   
                 1 0 0 1 
                 TOPR 
                 Color of pixel to the north-east, 1 pixel 
               
               
                   
                 1 0 1 L 
                 TOP 
                 Top color (N pixels) 
               
               
                   
                 1 1 0 L 
                 LEFT 
                 Left color (N pixels) 
               
               
                   
                 1 1 1 L 
                 NEW 
                 New color value (N pixels) 
               
               
                   
                   
               
             
          
         
       
     
       Additional Codes for Compressing Color Values 
       [0075]    The codes that have been defined up to now allow for compression of most simple pages. However pages containing sampled images (e.g. photographs) contain many pixels with a color that is not equal to their previously processed neighbor pixels. Therefore, they would be represented using a NEW code, which causes expansion instead of compression. Since successive color values in a sampled image are often similar, there is a possibility for compression of those color values. 
         [0076]    A method according to the present invention for compression of highly correlated color values will now be explained with reference to  FIG. 6 . 
         [0077]    The basic strategy consists of the following steps: 
         [0078]    1. Predict the value based on previous values; 
         [0079]    2. Determine the difference between predicted value and actual value; and 
         [0080]    3. Encode the difference using short codes for commonly occurring (small difference) values and longer ones for less commonly occurring values. 
         [0081]    Various lossless image compression algorithms (like JPEG lossless, JPEG-LS etc.) use a similar strategy. The differences are mostly in the construction of the predictor and in the encoding of the difference values. 
         [0082]    Since each page that will be printed has to go through the compressor, compression time must be low. This implies that we have to use a simple predictor and simple encoding of difference values that can be implemented efficiently on a general-purpose processor. 
         [0083]    Since the gray value of a pixel under consideration is encoded in relation to pixel values in the neighborhood, not only the value of the current pixel is accessed (step S 1  in  FIG. 6 ), but also those of predetermined neighboring pixels that have already been processed before (these pixel values will also be available in the decompressing step). Those neighboring pixel values are used to prepare a predicted pixel value in the prediction step. 
       The Prediction Step (FIG. 6: S 2 ) 
       [0084]    Various ways have been proposed in literature to predict the value of a pixel X, based on previously decoded pixels values north, west and northwest of pixel X. In  FIG. 5 , the predictors used in JPEG lossless are shown. Other algorithms use more complex (non-linear) predictors (e.g. JPEG-LS) or adaptive predictors that are modified while the image is being compressed. 
         [0085]    Since we need a fast algorithm, in the present embodiment we use a simple predictor: the color of the pixel to the left of pixel X (or white if X is the first pixel on the scanline). More advanced predictors may also be chosen. The choice should be made depending on the situation, since generally, such predictors will increase the compression factor, but execution time of the compressor will also increase. 
       The Step of Determining the Color Difference 
       [0086]    Most lossless compression algorithms are defined for gray scale images and the difference is the difference in gray level between predicted value and actual pixel value. In order to compress color images, the algorithm is applied to each color channel separately. A disadvantage of such an approach is that compression is not optimal since the color channels are generally strongly correlated. 
         [0087]    In the encoding method according to the present invention we work with all color channel values together. Basically, in case of CMYK images we will determine 4 color difference values and combine them into one single color difference value. Note that for compression of images with N color channels we would determine N color channel difference values and combine those into a single color difference value. 
         [0088]    At low ink coverage values, the K channel is often 0 for many CMYK printers. In order to make optimal use of this, we have defined 2 modes for specifying color difference values: a CMY mode and a CMYK mode. 
         [0089]    In CMYK mode we determine color differences over all 4 color channels. 
         [0090]    CMY mode can be used when the K channel value does not change. In CMY mode we determine color differences over 3 channels (K is the same as the predicted K value). 
       De-correlation (FIG. 6: S 3 , S 4 ) 
       [0091]    Since the values of the color channels are generally correlated, we will not determine the color difference values of the original channel values but we will first transform these as follows: 
         [0092]    In CMYK mode: 
         [0000]      C1=M 
         [0000]        C 2=( K−M+ 128) mod 256 
         [0000]        C 3=( C−M+ 128) mod 256 
         [0000]        C 4=( Y−M+ 128) mod 256 
         [0093]    In CMY mode: 
         [0000]      C1=M 
         [0000]        C 2=( Y−M+ 128) mod 256 
         [0000]        C 3=( C−M+ 128) mod 256 
         [0094]    This de-correlation step improves compression without a large performance penalty. Other transformations are also possible for de-correlation to the color channels. 
       Determination of Differences 
       [0095]    The de-correlation step S 3  is applied to the predicted color value C*, M*, Y*, K* and delivers de-correlated predicted values C 1 *, C 2 *, C 3 * and C 4 *. Likewise, a de-correlation step S 4  is applied to the actual color value C, M, Y, and K of the pixel to be compressed and delivers de-correlated predicted values C 1 , C 2 , C 3  and C 4 . 
         [0096]    Then, the difference values ΔC 1 , ΔC 2 , ΔC 3  and ΔC 4  are determined between the resulting de-correlated color values. As will be understood, in the CMY mode only three difference values ΔC 1 , ΔC 2  and ΔC 3  are determined. 
       The Step of Encoding the Color Difference 
       [0097]    The goal is to encode the channel differences ΔC 1 , ΔC 2 , ΔC 3  (and ΔC 4 ) of the de-correlated color values into a single combined number ΔC (in CMY mode 24 bits and in CMYK mode 32 bits) that is typically small. This number can then be encoded efficiently by dropping the leading 0 nibbles off the number. 
       Conversion of Difference Values (FIG. 6: S 6 ) 
       [0098]    We start by converting each of the channel difference values ΔC 1 , ΔC 2 , ΔC 3  and ΔC 4  to respective byte values ΔC 1 ′, ΔC 2 ′, ΔC 3 ′ and ΔC 4 ′ that can represent any possible color difference value and that is a small value for a small color difference. 
         [0099]    The difference values per channel can be positive or negative. In order to combine the values into a single color difference value, we map these values onto a positive value, which is small when the absolute value of the difference is small. This can be done by mapping difference values 0, 1, −1, 2, −2, etc. to values 0, 1, 2, 3, 4, 5, etc. in such a way that impossible difference values are skipped. E.g. when the value of the one of the de-correlated predictor channels C 1 *, C 2 *, C 3 * and C 4 * is 2, negative difference values ΔC 1 , ΔC 2 , ΔC 3  and ΔC 4  below −2 and positive difference values above 253 are not mapped since they cannot occur (all color channel values are within the range 0 to 255). 
         [0100]    This mapping can be done using the following formula: 
         [0101]    Let P be the byte value of a color channel of the de-correlated predictor and let A be the byte value of the corresponding color channel of the de-correlated actual color channel. Then the following C-language expression performs the mapping described above: 
         [0000]      (A=P?0:(P&lt;128? 
         [0000]      ( A&gt; 2* P?A :( A&gt;P? 2*( A−P )−1:2*( P−A ))): 
         [0000]      ( A&lt;= 2* P− 255?255− A :( A&gt;P? 2*( A−P )−1:2*( P−A ))))) 
         [0102]    In the actual compressor software these values are pre-calculated and stored in a 256 by 256 byte lookup table. 
         [0103]    Alternatively, a mapping that maps difference values 0, −1, 1, −2, 2 etc. to values 0, 1, 2, 3, 4, 5 etc. may be used. Other similar mappings are also possible, e.g. a mapping based on statistics gathered from actual documents and stored in the 256 by 256 lookup table. 
         [0104]    When it comes to decoding, the decompressor can reverse this transformation as follows. 
         [0105]    Let P be the byte value of a color channel of the de-correlated predictor and let C be the converted color difference value, then the following C-Language function can be used to determine the color channel value of the de-correlated actual color channel value: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 unsigned char color(unsigned char P, unsigned char C) 
               
               
                   
                 {int M0 = (C&amp;1) ?−1:0;  //wiring 
               
               
                   
                 int M7 = (P&amp;128)?−1:0;  //wiring 
               
               
                   
                 int C0 = M0 {circumflex over ( )} (C&gt;&gt;1);   //xor 
               
               
                   
                 int P7 = (M7 {circumflex over ( )} P)&lt;&lt;1;   //xor 
               
               
                   
                 int C7 = M7 {circumflex over ( )} C;   //xor 
               
               
                   
                 int PP = P7 − C;   //adder 
               
               
                   
                 int PC = P − C0;   //adder 
               
               
                   
                 int res = (PP&amp;256) ? C7:PC; //mux 
               
               
                   
                 return res; 
               
               
                   
                 } 
               
               
                   
                   
               
             
          
         
       
     
         [0106]    This function reflects the way the conversion can be implemented in hardware. 
         [0107]    By applying the conversion to the differences (ΔC 1 , ΔC 2 , ΔC 3  and ΔC 4 ) for the color channels, we obtain 3 (in CMY mode) or 4 (in CMYK mode) color difference byte values ΔC 1 ′, ΔC 2 ′, ΔC 3 ′ (and ΔC 4 ′) that specify the color differences and that are typically small 
       Combining Color Channels (FIG. 6: S 7 ) 
       [0108]    In a next step S 7  the converted difference values ΔC 1 ′, ΔC 2 ′, ΔC 3 ′ (and ΔC 4 ′) are combined into a single number ΔC that is typically small. To do this, bits of the separate values are merged, as shown in  FIGS. 7A  (CMYK) and  7 B (CMY). 
         [0109]    As can be seen in  FIG. 7A , in CMYK mode we simply interleave the bits of the 4 color difference values ΔC 1 ′, ΔC 2 ′, ΔC 3 ′ and ΔC 4 ′. In CMY mode ( FIG. 7B ), we do not simply interleave the bits of each difference value. The reason is that the value of the ΔC 1 ′ channel is typically larger than the values of the other channels. The optimal ordering of the bits was determined experimentally for a set of representative test images. In CMYK mode this may also be done as an alternative to the interleaving. 
         [0110]    The result of the merge is a single 24 or 32 bit number ΔC that represents the color difference and that has a small value for small color differences. 
         [0111]    An alternative approach within the scope of the present invention is to use a C-dimensional lookup table with C being the number of color channels. The lookup table is indexed with the C color difference values and each entry in the table contains a unique number such that often occurring color differences have a small value and rarely occurring color differences have a larger value. The table can be filled based on statistics gathered from test images. 
       Encoding the Difference Value (FIG. 6: S 8 /S 9 ) 
       [0112]    The final step is to encode the number ΔC in the compressed format efficiently by removing the high order 0 nibbles from ΔC (S 8 ) and generating codes for the remaining value (S 9 ). In the encoding step S 9  one code nibble is generated and stored in the code block ( FIG. 2 ) and an integer number of related data nibbles are generated and stored in the data block. 
         [0113]    By using 6 code nibble values to represent a color difference ΔC using 1, 2, 3, 4, 5 or 6 extra data nibbles, we can encode the color difference values and achieve compression. If, in CMYK mode, the color difference ΔC cannot be represented using 6 data nibbles then the original code NEW is used to represent the color value uncompressed (using 8 data nibbles for the color value, viz. 2 per color channel). 
         [0114]    The 6 new codes will be called NEW 1  to NEW 6  and will have code value 1 to 6 with NEW 1  having 1 data nibble and NEW 6  having 6 data nibbles to represent the color difference value ΔC. 
         [0115]    The 7 th  free code nibble is used for a new code NEM 6  that does the same as NEW 6  but also switches the mode between CMY and CMYK mode. 
       The Number of Pixels Generated by the New Codes 
       [0116]    Each of the NEW 1  to NEW 6  codes and code NEM 6  could generate 1 pixel per code. However most sampled images on pages have a resolution lower than the device resolution. 
         [0117]    The PostScript interpreter uses nearest neighbor interpolation to scale up the image. This results in several pixels in a row having the exact same value (see  FIG. 1 ). The compressor could use a LEFT code to compress this but it is more efficient if we allow the NEW 1  to NEW 6  and NEM 6  codes to generate a run of N identical pixels. Initially for each image N is set to 1 implicitly. 
         [0118]    This implies that we need to add codes that allow changing N. This will not happen often so we do not need short codes for changing N. 
         [0119]    In order to make this possible we make use of the fact that some of the coded color difference values of the above-defined NEW 1  to NEW 6  codes will not occur. 
         [0000]    First Nibble 0 (code NEWi*): N→1 
         [0120]    Argument values that will never occur are argument values that have a first nibble that is zero (since we stripped leading zero nibbles off the value before encoding it). We use those argument values to change the meaning of nibble code values 2 to 6 as follows: 
         [0121]    If the first nibble of the argument values is zero then codes 2 to 6 will be interpreted as codes NEW 2 * to NEW 6 *. These codes have the same meaning as the codes NEW 2  to NEW 6  except that they always produce only 1 pixel instead of N pixels (current N value), and also set N to 1. 
       Code INC: N→N+1  
       [0122]    Another combination that will never occur is code nibble 1 with a zero argument value, since that implies that the color of the pixel is the same as its neighbor to the west and we used code LEFT to encode that case. We use this combination to define a new code INC that produces 1 pixel with the same color as the left pixel and that increments N by 1. 
       Code NEW 
       [0123]    It will not always be possible for the compressor to use one of the NEW 1 * to NEW 6 * codes to reset N to 1 if the color cannot be expressed with only 6 nibbles. Therefore a code NEW with more than 1 new color values (i.e., L&gt;1) will also set N to 1. 
         [0124]    Table 3 below shows all code nibbles and their interpretation: 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 Summary of the code nibbles and their interpretation 
               
             
          
           
               
                 Code 
                 Name 
                 Data nibbles 
                 Description 
               
               
                   
               
               
                 0 0 0 0 
                 PREV 
                 none 
                 Previous color on scanline, 1 pixel 
               
               
                 0 0 0 1 
                 NEW1 
                 1, non-zero 
                 New color value, run of N pixels 
               
               
                   
                 INC 
                 1, zero 
                 Left color, 1 pixel, N = N + 1 
               
               
                 0 0 1 0 
                 NEW2 
                 2, 1 st  non-zero 
                 New color value, run of N pixels 
               
               
                   
                 NEW2* 
                 2, 1 st  zero 
                 New color value, 1 pixel, N = 1 
               
               
                 0 0 1 1 
                 NEW3 
                 3, 1 st  non-zero 
                 New color value, run of N pixels 
               
               
                   
                 NEW3* 
                 3, 1 st  zero 
                 New color value, 1 pixel, N = 1 
               
               
                 0 1 0 0 
                 NEW4 
                 4, 1 st  non-zero 
                 New color value, run of N pixels 
               
               
                   
                 NEW4* 
                 4, 1 st  zero 
                 New color value, 1 pixel, N = 1 
               
               
                 0 1 0 1 
                 NEW5 
                 5, 1 st  non-zero 
                 New color value, run of N pixels 
               
               
                   
                 NEW5* 
                 5, 1 st  zero 
                 New color value, 1 pixel, N = 1 
               
               
                 0 1 1 0 
                 NEW6 
                 6, 1 st  non-zero 
                 New color value, run of N pixels 
               
               
                   
                 NEW6* 
                 6, 1 st  zero 
                 New color value, 1 pixel, N = 1 
               
               
                 0 1 1 1 
                 NEM6 
                 6 
                 New color value, run of N pixels + 
               
               
                   
                   
                   
                 mode change (CMY &lt;-&gt; CMYK) 
               
               
                 1 0 0 0 
                 TOPL 
                 none 
                 Color of pixel north-west, 1 pixel 
               
               
                 1 0 0 1 
                 TOPR 
                 none 
                 Color of pixel north-east, 1 pixel 
               
               
                 1 0 1 L 
                 TOP 
                 none 
                 Top color. See table 1 for 
               
               
                   
                   
                   
                 interpretation of L bits 
               
               
                 1 1 0 L 
                 LEFT 
                 none 
                 Left color. See table 1 for 
               
               
                   
                   
                   
                 interpretation of L bits 
               
               
                 1 1 1 L 
                 NEW 
                 number of new 
                 New colors. See table 1 for 
               
               
                   
                   
                 colors * 8 
                 interpretation of L bits 
               
               
                   
               
             
          
         
       
     
       Compression Method According to the Invention 
       [0125]    Now that the compressed image format has been defined we will explain the method that an exemplary compressor according to the present invention may use to produce this format. Reference is made to  FIG. 8 . 
       Pixel Processing Order 
       [0126]    The exemplary compressor processes the image scanline by scanline starting at the first scanline of the image and continuing until all scanlines have been processed (steps S 26  to S 29 ). For each scanline the compressor processes all pixel starting at the left-most pixel on the scanline, until all pixels on the scanline have been processed. Upon the start of a new scanline, the PREV and LEFT pixels are set to “white” in an initializing step S 11 . 
       Steps for Each Pixel 
       [0127]    The compressor attempts to compress every next pixel by trying to apply different codes for compressing the pixel in the following fixed order: 
         [0128]    1) The pixel is compared to the TOP color (S 12 ). This is the color of the neighbor pixel to the north or, if the current pixel is on the first scanline, the color white. If a match is found, then the compressor generates a TOP run by generating one or more TOP codes and maximizes the length of this run by adding to this run all following pixels that can be encoded with a TOP run (S 13 ). Then the process restarts at step 1 with the next uncompressed pixel (S 26 , S 27 ). 
         [0129]    2) If the preceding step did not allow encoding the pixel, then the pixel is compared to the LEFT color (S 14 ). This is the color of the neighbor pixel to the west or, if the current pixel is at the start of a scanline, the color white. If a match is found, then the compressor generates a LEFT run by generating one or more LEFT codes and maximizes the length of this run by adding to this run all following pixels that can be encoded with a LEFT run (S 15 ). Then the process restarts at step 1 with the next uncompressed pixel (S 26 , S 27 ). 
         [0130]    3) If the preceding step did not allow encoding the pixel, then the pixel is compared to the PREV color (S 16 ). The value of the PREV color has been explained hereinbefore. If a match is found, then the compressor generates a PREV code (S 17 ). Then the process restarts at step 1 with the next uncompressed pixel (S 26 , S 27 ). 
         [0131]    4) If the preceding step did not allow encoding the pixel, then the pixel is compared to the TOPL color (S 18 ). This is the color of the neighbor pixel to the northwest or, if it doesn&#39;t exist, the color white. If a match is found, then the compressor generates a TOPL code (S 19 ). Then the process restarts at step 1 with the next uncompressed pixel (S 26 , S 27 ). 
         [0132]    5) If the preceding step did not allow encoding the pixel, then the pixel is compared to the TOPR color (S 20 ). This is the color of the neighbor pixel to the northeast or, if it doesn&#39;t exist, the color white. If a match is found, then the compressor generates a TOPR code (S 21 ). Then the process restarts at step 1 with the next uncompressed pixel (S 26 , S 27 ). 
         [0133]    6) If the preceding step did not allow encoding the pixel, then the method for compressing color values described hereinbefore in the “Additional codes for compressing color values” section is applied (S 22 ). If the K channel value is the same as the predicted K channel value then CMY mode is used to compress the color, otherwise CMYK mode is used. It is then checked (S 23 ) if that results in an acceptable NEWi code, that is, a color difference value of 6 nibbles or less with no mode change. If so, then the appropriate one of the NEW 1  to NEW 6  codes is generated together with the color difference nibbles (S 24 ). If that is not the case then a code NEW is generated and the new color value is written uncompressed to the data block (S 25 ). 
         [0134]    If the previous mode was different from the mode used to compress the pixel and if the length of the color difference value is 6 nibbles or less then code NEM 6  is generated together with the color difference nibbles. If the color difference value is longer than 6 nibbles then a code NEW is generated and the new color value is written uncompressed to the data block. These steps are not explicitly shown in  FIG. 8 , but are considered to form part of the steps S 24  and S 25 . 
         [0135]    If the value of N is larger than the number of successive pixels with that color and the color difference value has a length of 5 nibbles or less, then the appropriate one of the NEW 2 * to NEW 6 * codes is generated together with the color difference nibbles preceded by a null nibble. If that is not possible then a code NEW is generated for the current pixel and the next pixel and the color values of the current and next pixels are written uncompressed to the data block. These steps are not explicitly shown in  FIG. 8 , but are considered to form part of the steps S 24  and S 25 . 
         [0136]    Then the process restarts at step S 11  with the next uncompressed pixel (S 26 , S 27 ). 
         [0137]    A code NEW with a run length of at least 2 causes N to be reset to 1. 
         [0138]    In order for the compressor to increment N when appropriate, every time a LEFT run follows a code in the range 1 to 6 (indicating a new color), the compressor stores its state (unless a state was already stored less than 32 pixels ago). From that point on it keeps track of the minimum number M of successive pixels with the identical colors on the scanline. 
         [0139]    If the compressor determines that incrementing N would allow for better compression, then the compressor restores its state to the state it previously stored (thereby discarding any output it generated after storing that state) and N is incremented to the value of M by generating one or more INC codes. Then compression restarts at the point indicated by the stored state. 
       Examples of Possible Simplifications Within the Scope of the Present Invention 
       [0140]    Compression steps 3, 4 and 5 could be done in a different order without significant loss of compression. 
         [0141]    Compression steps 3, 4 and 5 could be left out of the compressor without significant loss of compression for most images. Then the corresponding codes PREV, TOPL and TOPR could be removed from the compressed format. 
         [0142]    Compression steps 1 and 2 can be exchanged without significant change in compression. 
         [0143]    Instead of having a CMYK and a CMY mode, a CMYK mode only would work, albeit with some loss of compression. With one mode, code NEM 6  could be removed from the compressed format. 
         [0144]    N could have been fixed to 1, albeit with some loss of compression. Then the codes INC and NEW 2 * to NEW 5 * could be removed from the compressed format. 
         [0145]    Code NEW has a run length to reduce the maximum expansion of the compressed format. If there would be no requirements for the maximum expansion, a run length would not be needed for code NEW. 
       Decompression Method According to the Invention 
       [0146]    For each successive scanline, starting at the first scanline of the image and proceeding to the last scanline, the de-compressor processes the code nibbles from the code block and takes the corresponding data nibbles from the data block. It assigns the decompressed color values to the successive pixels on that scanline, starting at the left-most pixel. 
         [0147]    Each pixel is assigned a color exactly once.
       When the decompressor encounters a code PREV it assigns the PREV color (of which it keeps track) to the current pixel. The value of the PREV color is explained hereinabove.   When the decompressor encounters one of the code values 1 (hexadecimal 0 0 0 1) to 6 (hexadecimal 0 1 1 0), it checks the value of the next data nibble in the data block.       
 
         [0150]    If the data nibble is non-zero, the code is interpreted as one of the codes NEW 1  to NEW 6 . In that case the de-compressor reconstructs the color value of the next pixel from the color value of the predictor in combination with the difference value store in the data block according to the current mode, by reversing the transformation steps applied by the compressor. This color value is then assigned to N successive pixels starting at the current one. 
         [0151]    The color value of the predictor is the color of the previously decompressed pixel on the scanline, or white if the current pixel is the first on the scanline. 
         [0152]    If the data nibble was zero and the code value was greater than 1, then the code is interpreted as one of the codes NEW 2 * to NEW 6 *. In that case the de-compressor reconstructs the color value from the color value of the predictor in combination with the difference value store in the data block according to the current mode, by reversing the transformation steps applied by the compressor. This color value is then assigned to the current pixel. Additionally the de-compressor sets N to 1. 
         [0153]    If the data nibble was zero and the code value is 1, then the code is interpreted as code INC. In that case the de-compressor assigns the color of the previously decompressed pixel (or the color white if the current pixel is the first on the scanline) to the current pixel. Additionally it increments N by 1.
       When the decompressor encounters a code NEM 6  (code value 0 1 1 1), it switches the current mode and it reconstructs the color value from the color value of the predictor in combination with the difference value store in the data block according to the current mode, by reversing the transformation steps applied by the compressor. This color value is then assigned to N successive pixels starting at the current one.   When the decompressor encounters a code TOPL (code value 1 0 0 0), it copies the color from the previously decompressed neighbor pixel to the northwest and assigns it to the current pixel. If there is no such neighbor pixel it assigns the color white to the current pixel.   When the decompressor encounters a code TOPR (code value 1 0 0 1), it copies the color from the previously decompressed neighbor pixel to the northeast and assigns it to the current pixel. If there is no such neighbor pixel it assigns the color white to the current pixel.   When the decompressor encounters a code TOP (code value 1 0 1 L), it collects all immediately following TOP codes from the code block and determines the run length R using the method described above. Then R pixels, starting from the current pixel are each assigned the color from their neighbor pixel to the north. If the decompressor is decompressing on the first scanline then all R pixels are assigned the color white.   When the decompressor encounters a code LEFT (code value 1 1 0 L), it collects all immediately following LEFT codes from the code block and determines the run length R using the method described above. Then R pixels, starting from the current pixel are assigned the color from their neighbor pixel to the left. If the current pixel is the first pixel on a scanline then all R pixels are assigned the color white.   When the decompressor encounters a code NEW (code value 1 1 1 L), it collects all immediately following NEW codes from the code block and determines the run length R using the method described above. Then the decompressor takes R uncompressed color values from the data block and assigns them to the following R pixels, starting at the current pixel. If the run length R is greater than 1 then the decompressor sets N to 1.       
 
       Evaluation of the Compression Method 
       [0160]    In order to evaluate the performance of the compression method, we used the compressor to compress a range of images and compared the results (compression time and compression factor) with results from compressing the same images with JPEG-LS. We also compared the compression time with the time it took an Adobe PostScript interpreter to generate the pages. 
         [0161]    All tests were done on a 2.4 GHz Pentium 4. The PostScript test files were run on the Adobe PostScript interpreter and the resulting 600 dpi continuous tone CMYK bitmaps were compressed. The size of the bitmaps was A4 (4958 by 7040 pixels) resulting in an uncompressed size of 136345 Kbytes. On the PostScript interpreter, the interpretation of DeviceRGB was set to sRGB and the interpretation of DeviceCMYK was set to Euroscale. A Euroscale output profile was used. 
         [0162]    The PostScript test files used contain complex but realistic page descriptions. A specially constructed PostScript file (chrisA4.ps) has been included which contains an extremely complex page with lots of very fine details (a photo-mosaic page, containing a page-size image consisting of many very small images). This is not a very realistic page but it is used to explore the boundaries of compressibility. 
         [0163]    In order to compare the compression performance of the new compressor with the state of the art in lossless image compression, we compared our results with those produced by JPEG-LS. 
         [0164]    JPEG-LS is based on HP&#39;s LOCO-I algorithm and has been selected by the ISO/ITU-T as a standard for lossless compression of continuous tone images. A description of the algorithm is given in: M. Weinberger, G. Seroussi, G. Saipiro, 
         [0165]    LOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithm”, available on www.hpl.hp.com/loco/HPL-98-193R1.pdf. 
         [0166]    Compared to other lossless continuous tone image compression algorithms (lossless JPEG, CALIC, FELICS), JPEG-LS is relatively simple and fast and it produces better compression. Compression performance for JPEG-LS is slightly better than for JPEG2000 lossless (see Diego Santa Cruz, Touradj Ebrahimi, “An analytical study of JPEG 2000 functionalities”, available on www.jpeg.org/public/wgln1815.pdf). 
         [0167]    We have chosen the JPEG-LS plug-in for Adobe photoshop to test JPEG-LS. It is an efficient implementation that reports the compression time required for the page. It is available on http://www.hpl.hp.com/loco. Note that JPEG-LS has been designed as a generic lossless continuous tone image compression technique, not specifically for the compression of PDL generated continuous tone images. 
         [0168]    The detailed measurement results are presented in Table 4 below. 
         [0000]    
       
         
               
             
               
               
               
               
             
               
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                 Table 4 
               
             
             
               
                   
               
               
                 Measurement results 
               
             
          
           
               
                   
                 PS-RIP 
                 Our compression 
                 JPEG-LS 
               
             
          
           
               
                   
                 Time 
                 Time 
                 Size 
                 Time 
                 Size 
               
               
                 Document 
                 (sec) 
                 (sec) 
                 (kbyte) 
                 (sec) 
                 (kbyte) 
               
               
                   
               
             
          
           
               
                 breakfast.ps 
                 3.51 
                 0.61 
                 17712 
                 11.69 
                 28233 
               
               
                 chqf.ps 
                 1.18 
                 0.19 
                 3711 
                 5.01 
                 6678 
               
               
                 chrisA4.ps 
                 8.79 
                 2.22 
                 80413 
                 17.42 
                 67916 
               
               
                 gatf1.ps 
                 1.69 
                 0.13 
                 1002 
                 4.35 
                 4118 
               
               
                 gatf2.ps 
                 1.34 
                 0.31 
                 6802 
                 6.47 
                 15657 
               
               
                 gatf3.ps 
                 1.09 
                 0.34 
                 7284 
                 6.77 
                 14979 
               
               
                 gatf4.ps 
                 0.94 
                 0.27 
                 6283 
                 6.31 
                 13713 
               
               
                 oilplatform.ps 
                 3.70 
                 0.63 
                 17857 
                 11.05 
                 25637 
               
               
                 model- 
               
               
                 puzzle.ps 
                 6.70 
                 1.44 
                 43832 
                 11.12 
                 35080 
               
               
                 printwork1.ps 
                 1.89 
                 0.11 
                 434 
                 2.82 
                 1870 
               
               
                 printwork2.ps 
                 2.80 
                 0.09 
                 122 
                 4.40 
                 1123 
               
               
                 printwork4.ps 
                 3.27 
                 0.56 
                 17317 
                 7.46 
                 18944 
               
               
                 printwork5.ps 
                 3.59 
                 0.98 
                 31423 
                 10.85 
                 32585 
               
               
                 printwork6.ps 
                 1.97 
                 0.58 
                 19396 
                 8.00 
                 21758 
               
               
                 Average: 
                 3.03 
                 0.60 
                 18113 
                 8.12 
                 20592 
               
               
                   
               
             
          
         
       
     
         [0169]    The first column lists the names of the test pages. The names have no special meaning other than that they happen to be the names under which the documents were stored. The second column shows the execution time of a state of the art Adobe PostScript interpreter for converting the PostScript description of the page into the image to be compressed. The third column shows the execution time of the new compression method and the fourth column shows the resulting amount of compressed data. The fifth column shows the execution time of the JPEG-LS compressor and the sixth column shows the resulting amount of compressed data. The last line of the table shows the averages over all test images. 
         [0170]    The average compression time for the new method is 0.6 seconds, which is about 20% of the execution time of the PostScript interpreter for generating the page. The average compression time of JPEG-LS is 8.12 seconds, which is about 13.5 times slower than the new compression method. It is also clear from these results that JPEG-LS does not fulfill our requirements since it is much too slow in comparison to the PDL interpretation time. 
         [0171]    The amount of compressed data produced by the new compression is on the average less than the amount produced by JPEG-LS. For some very complex pages containing samples images at a resolution equal to the device resolution (“chrisA4.ps” and “model-puzzle.ps”) JPEG-LS produces less compressed data than the new method, but such pages are rare in practice. 
       Implementation in Hardware 
       [0172]    The compressed format has several properties that allow for simple implementation of the decompressor in hardware. 
         [0173]    The maximum local expansion of the format occurs when a NEW code of length 3 is directly followed by a NEW 6  or NEM 6  code. The NEW code takes 2 code nibbles+3*8 data nibbles. The NEW 6  or NEM 6  code takes 1 code nibble+6 data nibbles. This means that in total 33 nibbles are needed in this case to produce 4 CMYK pixel values, so the worst case local expansion is 1/32=3.1%. This means that the speed at which uncompressed data has to be processed is at most 3.1% higher than the rate at which uncompressed pixels are produced. 
         [0174]    The compressed format has been constructed in such a way that each code produces at least one pixel. 
         [0175]    The only special case occurs for the codes LEFT, TOP and NEW, which require successive occurrences of the code to be interpreted as a whole. When the first code nibble for one of these codes has been interpreted, the source of the successive color values is clear:
       for code LEFT: all the same as the left color;   for code TOP: all coming from the pixel above the target pixel; and   for code NEW: all coming from the compressed data stream.       
 
         [0179]    At that point, transfer of the colors to the new pixels can be started and can proceed in parallel with code interpretation. The code interpreter can proceed to combine successive codes until a different code is encountered. Then it knows how many pixels have to be generated. Since the amount of pixels produced by these codes increases faster than the number of nibbles needed to encode this amount, the code interpreter will always be finished determining the amount of pixels before that amount of new color values has been transferred. So the code interpreter can stop the transfer of color values to new pixels after the correct number of pixels have been produced. 
         [0180]    A second embodiment of the present invention, which is a compression method intended for continuous tone black-and-white (grey-value) images, will now be described. 
         [0181]    The mechanisms used in the second embodiment are the same as those of the first embodiment described above, namely: 
         [0182]    The compression is done on a line-per-line basis. For each line the compressed data is organized in 2 parts, the “data block” and the “code block”. 
         [0183]    For each pixel or each set of identical pixels, a code or a series of codes are generated in the code block. For some codes (NEWi codes), additional data are necessary which are stored in the data block. At the end of each scanline, the data block and the code block are put together to generate the compressed data for the current line. 
         [0184]    The second embodiment uses a reduced set of codes and is bit-oriented (as opposed to the nibble-oriented first embodiment). More particularly, codes are always 3 bits long, but the associated parts in the data block have variable length (number of bits). The codes that are used in the second embodiment are defined as follows.
       Code TOP, LEFT, and PREV have the same meaning as in the first embodiment: they encode a run of pixels identical to the pixel to the top, the left or the previous color, respectively.   Code NEW encodes a new color; this code can define a run of identical pixels, although the runlength defining mechanism is different than that of the first embodiment, as will be explained later.   Code NEW 1  to NEW 4  and NEW 3 * and NEW 4 * encode a pixel or a run of identical pixels having a grey value that differs from that of the predicted value (in this example the pixel to the left) by an amount that fits in 1 to 4 bits or 2 or 3 bits, respectively (once converted into a positive integer).       
 
         [0188]    The code words are 3 bits long and can take any of the values listed in Table 5 below. 
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE 5 
               
             
             
               
                   
               
               
                 Summary of the codes 
               
             
          
           
               
                   
                 Code 
                 Name 
               
               
                   
                   
               
               
                   
                 0 0 0 
                 NEW1/PREV 
               
               
                   
                 0 0 1 
                 NEW2/NEW 
               
               
                   
                 0 1 0 
                 NEW3/NEW3* 
               
               
                   
                 0 1 1 
                 NEW4/NEW4*/INC 
               
               
                   
                 1 0 L 
                 LEFT 
               
               
                   
                 1 1 L 
                 TOP 
               
               
                   
                   
               
             
          
         
       
     
         [0189]    The definition of the codes is as follows.
       LEFT and TOP code: there is no associated data part. Several identical codes are interpreted together and the “L” bit is used to encode the number of corresponding pixels, in much the same way as in the first embodiment.   PREV code: no associated data part. It generates a pixel with the current previous color.   NEW 1 /NEW 2 /NEW 3 /NEW 4  codes: when the current pixel to be coded cannot be expressed by a LEFT, TOP, or PREV code, the difference between the color value of the current pixel and the left pixel is computed, and then converted into a positive integer (by the same mechanism as in the first embodiment). If this difference (an 8 bit integer) can fit in 1, 2, 3, or 4 bits after truncation of leading zero bits, a corresponding NEWi code is selected. In addition, an associated data part is formed, that corresponds to the difference and thus is 1, 2, 3, or 4 bits long, respectively. The codes NEW 1  to NEW 4  produce a run of pixels, of which the length (called N) is maintained during the processing of the document.   INC/NEW 3 */NEW 4 * codes: the current run length value N is set to 1 at the beginning and is increased by 1 with an INC code, which code also produces a pixel of the left color. N can be reset to 1 when the value is too high (i.e., when a set of N pixels would not fit the input data): the NEWi* codes are used therefor, as in the original format. The decoder will recognize these codes since a NEWi* code has an associated data part beginning with 0 as the MSB (most significant bit).   NEW code: when a new color value cannot be encoded with one of the previous codes, the NEW code is used. The data part of the NEW code contains the new grey value (8 bits), but may also contain run length information as will be explained below. Finally, a succession of at least two NEW codes resets the value of N to 1, in the same way as in the first embodiment.       
 
         [0195]    The codes are differentiated with their data part: 
       Code 0 0 0: NEW 1 /PREV 
       [0196]    The associated data with this code is 1 bit long. It means that the difference between the current pixel and the one to its left can be expressed with only 1 bit. The case where the data bit is set to 0 is impossible since it would mean no difference between the two pixels. Thus this possibility is used to encode a PREV code. 
       Code 0 0 1: NEW 2 /NEW 
       [0197]    The associated data with this code is 2 bits long. It means that the difference between the current pixel and the one to its left can be expressed with 2 bits. The case where the MSB (most significant bit) of the data part is 0 is used for the NEW code. In that case, the LSB (least significant bit) of the 2 bit long data part is a run-length bit used to group several NEW codes together, in much the same way as the L bit in the LEFT and TOP codes (although in those codes the L bit is situated in the code itself). In case of several NEW codes grouped together, the 2 bits data parts of all NEW codes are grouped and put in the data block and then, all the NEW color values (8 bits each) are put in the data block. 
         [0198]    Note, however, that a code NEW 2  following a NEW code could lead to misinterpretation by the decoder, depending on the NEW color value. Therefore, we prevent a code NEW 2  from following any NEW code. 
       Code 0 1 0: NEW 3 /NEW 3 *  
       [0199]    The associated data part of this code is 3 bits long. This code is used when the difference between the current pixel and the one to its left can be expressed with 3 bits. A NEW 3 * code is a NEW 3  code with a data part having its MSB set to 0. It is used to reset the N value to 1, and encodes a difference with the 2 additional data bits. Since in this embodiment a NEW 2 * code is not available, the NEW 3 * is also used for a difference that can be expressed in 1 bit. 
       Code 0 1 1: NEW 4 /NEW 4 */INC 
       [0200]    The associated data part of this code is 4 bits long. This code is used when the difference between the current pixel and the one to its left can be expressed with 4 bits. A NEW 4 * code is a NEW 4  code with a data part having its MSB set to 0. It is used to reset the N value to 1, and encodes a difference with the 3 additional data bits. An INC code is a NEW 4  code with a data part equal to 0 (all 4 bits). It is used to increment the N value by 1 and generate a pixel with the same color as the pixel to the left. 
       Code 1 0 L: LEFT 
       [0201]    There is no associated data with this code. It is used when the pixel to encode has the same color as the pixel to its left. The “L” bit is a run-length bit that is used to group several LEFT codes together (same mechanism as in the first embodiment) 
       Code 1 1 L: TOP 
       [0202]    There is no associated data with this code. It is used when the pixel to encode has the same color as the pixel to the top. The “L” bit is a run-length bit that is used to group several TOP codes together (same mechanism as in the first embodiment). 
         [0203]      FIG. 9  shows a flow chart of the general encoding process according to the second embodiment of the invention. This process is largely similar to that of the first embodiment as described with reference to  FIG. 8 , although, since less codes are used, some of the steps are missing. A full description of  FIG. 9  is therefore omitted here, since it will be easily understood on the basis of the description of the codes hereinabove. 
         [0204]    The individual steps of the process have been numbered in accordance with the corresponding steps in  FIG. 8 . Reference numbers in  FIG. 9  have been provided with an accent. 
         [0205]      FIG. 10  describes the basic NEWi code forming process according to the second embodiment, as referred to by reference number S 22 ′ in  FIG. 9 . Since this process operates on one color channel only, several steps of the first embodiment are superfluous. Those steps left have been numbered with corresponding reference numbers as in  FIG. 6 , provided with an accent, and are listed below. For a detailed explanation for each step, the reader is referred to the description of  FIG. 6  and the description of the codes of the second embodiment hereinabove. 
         [0206]    The actual value of a pixel under consideration is accessed in step S 1 ′ and a predicted value is determined from neighboring pixels (e.g., the pixel to the left) in step S 2 ′. Then, the difference of the actual and predicted values is determined in step S 5 ′ and this value is converted in step S 6 ′ to a positive integer which is small for small differences and larger for larger differences. The actual conversion may be based on the use of a lookup table (LUT) that may have been filled before with a general or a dedicated conversion data set. 
         [0207]    The resulting difference value is then truncated by cutting off leading zero bits (S 8 ′) and the remaining non-zero bits are encoded in NEWi codes in step S 9 ′, as described hereinabove. 
         [0208]    The present invention, of which two embodiments have been described in detail above, provides a new compression method and format for lossless compression and decompression method for (preferably) PDL-generated continuous tone page image data. 
         [0209]    Compared to a state of the art lossless image compression algorithm like JPEG-LS, the new method is faster on average, as measured for a representative set of test documents. This allows compression to be implemented on the same computer as used to run the PDL interpreter, without additional hardware and without large performance penalties. 
         [0210]    The invention being thus described, it will be obvious that the same may be varied in many ways. Such variations and modifications as would be obvious to one skilled in the art are intended to be included within the scope of the following claims. 
         [0211]    For instance, although the method was optimized for PDL generated images, it can also be used to compress images from other sources. 
         [0212]    Further, the description above focuses on compression of CMYK color images with 8 bits per color channel and 8 bits continuous tone black-and-white images. But anyone skilled in the art will appreciate that it can be modified to compress a multitude of other continuous tone images, such as RGB continuous tone color images, continuous tone color images with more than 4 channels per color value or for images with color channels of a different precision than 8 bits, or other continuous tone single-color (grayscale) images. 
         [0213]    Also, the actual code forms as described in the first embodiment and the second embodiment may be replaced by other, similar codes, and those codes of the first embodiment may also be used in the second one and vice versa. 
         [0214]    The invention being thus described, it will be obvious that the same may be varied in many ways. Such variations are not to be regarded as a departure from the spirit and scope of the invention, and all such modifications as would be obvious to one skilled in the art are intended to be included within the scope of the following claims.