Abstract:
A system and method for compressing and decompressing image data. The system and method reformats the data by interleaving, before it is sent to the compressor. The step of interleaving uses raster scan lines, taking N raster lines at a time and reformatting the data so that the first bit of the first N scan lines form a byte. This is continued for N bits. The data is then sent to a byte/text oriented compressor. After decompressing the data using byte/text oriented decompressors, the data is sent through an inverse binary data reformatter to un-interleave the data and return it to its original binary format.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of Invention 
     This invention is directed to compressing digital data. 
     2. Description of Related Art 
     Data compression is required in data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links to reduce the transmission time or required bandwidth. Similarly, compression is preferred in image storage systems, including digital printers and copiers, where “pages” of a document to be printed are stored temporarily in precollation memory. The amount of media space on which the image data is stored can be substantially reduced with compression. Generally speaking, scanned images, i.e., electronic representations of hard copy documents, are often large, and thus make desirable candidates for compression. 
     SUMMARY OF THE INVENTION 
     Byte oriented compression techniques include ZIP, Compress and LZW. These type of compression techniques rely on finding and encoding similar bytes. When presented with a binary image, which is typically stored as a raster of 1-bit pixels in a binary bit map, or as a raster of pixels, each having one or more bytes, in a byte map, a large context is required to discover the similar bytes on the next few scan lines. 
     This invention provides systems and methods that re-format the original raster image data to improve compression. 
     This invention separately provides systems and methods that take advantage of the vertical correlation that is typically present in a raster image when compressing that raster image. 
     In various exemplary embodiments, the systems and methods of this invention re-format the original raster image data. In various exemplary embodiments, the systems and methods interleave the bits from 8 adjacent raster scan lines. Accordingly, in a bit map raster image the first byte to be compressed includes the first 1-bit pixel of each of the first eight scan lines, the second byte includes the second 1-bit pixel of each of the first eight lines, etc. By re-formatting the raster data in this way, the systems and methods of this invention ensure that much of the vertical correlation of bits in the raster image is captured before the image is compressed using a byte-oriented compression technique. 
     The reordered original image data is then compressed using one of a variety of different types of compression techniques. The data is compressed and transferred to a storage facility or the like. When needed, the original image data can then be decompressed using the corresponding decompression technique re-ordered back into the original format, and sent to an image data sink. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various exemplary embodiments of this invention will be described in detail, with reference to the following figures, wherein: 
         FIG. 1  is a generalized block diagram of one embodiment of a compression and decompression system according to this invention; 
         FIG. 2  is a flowchart outlining one exemplary embodiment of an image compression and decompression method according to this invention; 
         FIG. 3  is a flowchart outlining one exemplary embodiment of a method for reformatting of the original image data of step S 1300 ; 
         FIG. 4  is a flowchart outlining one exemplary embodiment of a method for re-formatting the original image data; and 
         FIG. 5  is a flowchart outlining one exemplary embodiment of a method for inversely reformatting the reformatted data of step S 1700 . 
     
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       FIG. 1  shows one exemplary embodiment of a generalized functional block diagram of a compression and decompression system  100  according to this invention. The compression and decompression system  100  includes an image source  110  that may be any one of a number of different sources, such as a scanner, a digital copier, a facsimile device suitable for generating electronic image data, or a device suitable for storing and/or transmitting the electronic image data, such as a client or server of a network. The electronic image data from the image source  110  is provided to an encoder  400  of the compression and decompression system  100 . 
     The encoder  400  incorporates all the necessary components to process the input image data and compress it. In particular, the encoder  400  includes a binary data reformatter  410  that reformats the original raster image data. The original raster image data, taken from the raster scan order, is interleaved to take advantage of the vertical correlation that is typically present. 
     The reordered original raster image data is then sent to a compressor  420  to be compressed. The compressor  420  can use any one of several byte-oriented data compression technique that can be used to compress the reformatted data These byte-oriented data compression techniques include ZIP, Compress, LZW and any other known or later-developed byte-oriented data compression technique. 
     Once compressed, the image data then is preferably transferred to the channel or storage device  300 . The channel or storage device  300  can be either or both of a channel device for transmitting the compressed image data to the decoder  500  or a storage device for indefinitely storing the compressed image data until there arises a need to decompress the compressed image data. The channel device can be any known structure or apparatus for transmitting the compressed image data from a first apparatus implementing the encoder  400  according to this invention to a physically remote decoder  500  according to this invention. Thus, the channel device can be a public switched telephone network, a local or wide area network, an intranet, the Internet, a wireless transmission channel, any other distributed network, or the like. 
     Similarly, the storage device can be any known structure or apparatus for indefinitely storing compressed image data, such as a RAM, a hard drive and disk, a floppy drive and disk, an optical drive and disk, flash memory or the like. Moreover, the storage device can be physically remote from the encoder  400  and/or the decoder  500 , and reachable over the channel device described above. 
     When the image is to be decompressed, in one exemplary embodiment, the data is then provided to and processed by the decoder  500 . The decoder  500  incorporates all the necessary components to process the compressed data and to restore it to its original format. In particular, the decoder  500  includes a decompressor  530  that receives and decompresses the compressed image data from the channel or storage device  300 , an inverse binary data reformatter  520  to un-interleave the decompressed data back into its original binary format and an output controller  510  that controls the decompressor  530  and the inverse binary data reformatter to form the decompressed image. Though the decoder  500  is shown in  FIG. 1  as physically separate from the encoder  400 , it should be understood that the decoder  500  and the encoder  400  may be different functional and/or structural aspects of a single physical device. 
     The output controller  510  sends the reconstructed image to the output device  200 . It should be understood that the output device  200  can be any device that is capable of outputting or storing the decompressed image data generated according to the invention such as a printer, facsimile device, a display device, a memory, or the like. 
       FIG. 2  is a flowchart outlining one exemplary embodiment of an image compression and decompression method according to this invention. Beginning in step S 1000 , control continues to step S 1100 , where electronic image data is generated from an original image. Then, in step S 1200 , the electronic image data is input from the image source. Control then continues to step S 1300 . 
     It should be appreciated that, while the flowchart of  FIG. 2  shows generating the electronic image data as part of the process, this step is not necessarily needed. That is, while the electronic image data can be generated by scanning an original image, or the like, the electronic image data could have been generated at any time in the past. Moreover, the electronic image data need not have been generated from an original physical image, but could have been an original creation. Accordingly, if electronic image data of the image is already available to the image source, step S 1100  can be skipped, with control continuing directly from step S 1000  to step S 1200 . In step S 1300 , the binary image data is reformatted to form new reformatted image data. Then, in step S 1400 , compressed image data is generated from the reformatted image data using one of many byte-oriented compression techniques. Next, in step S 1500 , the compressed image data is transmitted, and possibly stored before being transmitted, to a device for decompressing the compressed image data. Control then continues to step S 1600 . 
     In step S 1600 , the compressed image data is decompressed using one of many corresponding byte-oriented decompression techniques. Next, in step S 1700 , the decompressed image data is inversely reformatted from its interleaved format back to its original binary image format. Next, in step S 1800 , the binary image data is output to a storage, display or memory device or the like. Then, in step S 1900 , the method ends. 
       FIG. 3  outlines in greater detail one exemplary embodiment reformatting of the image data of step S 1300 . Beginning in step S 1300 , control continues to step S 1310 , where the input data is selected. In step S 1310 , the first or next eight raster lines from the raster scan order are selected. Then, step S 1320 , the input data is reformatted by interleaving the eight bits of the current eight raster lines to form a byte. Next, in step S 1330 , the interleaved data is stored in a reformatted data buffer until all of the reformatted data is ready to be sent to the compressor for compression. Control then continues to step S 1340 . 
     In step S 1340 , a determination is made if there is any more data that needs to be interleaved. If there is data that needs to be interleaved, control jumps back to step S 1310 . If all the data has been interleaved, control continues to step S 1350 . In step S 1350 , the reformatted data or the reformatted data buffer is provided to the compressor for compressing. Thus, in step S 1360 , control returns to step S 1400 . 
       FIG. 4  outlines one exemplary embodiment of detail interleaving of the raster line bits of step S 1320 . Beginning in step S 1320 , control continues to step S 1321 , where the first bit of each of the eight current raster lines is selected. Next, in step S 1322 , a new byte is created out of the selected bits. In particular, the bits selected from the current eight raster lines are grouped together to form a byte. Then, in step S 1323 , a determination is made whether there are any more bits of the eight current raster lines that need to be selected. If there are any more bits to be selected, control jumps back to step S 1321  and the next bit of each of the current eight raster lines are selected. If the last bits in the current eight raster lines have been selected, control continues to step S 1324 , where control returns to step S 1330 . Thus, the data of eight scan lines is interleaved to take advantage of the vertical correlation in the data. 
       FIG. 5  is a flowchart outlining one exemplary embodiment of inverse reformatting the interleaved data of step S 1700 . Beginning in step S 1700 , control continues to step S 1710 , where the first or next decompressed interleaved data bytes is selected. Then, in step S 1720 , the bits from the selected decompressed data bytes inversely interleaved to re-create the original binary raster image data. Next, in step S 1730 , the un-reformatted binary data bits are placed into the appropriate positions within the eight raster lines to which the bits of raster data belong. Control then continues to step S 1740 . 
     Next, in step S 1740 , a determination is made if there is anymore byte data that needs to be inversely interleaved. If there is, control jumps back to step S 1710 , If not, control continues to step S 1750 , where control returns to step S 1800 . 
     In various exemplary embodiments, the encoder  400  is implemented on a programmed general purpose computer. However, the encoder  400  can also be implemented on a special purpose computer, a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA or PAL, or the like. In general, any device, which is capable of implementing step S 1300  of  FIGS. 2 and 3 , can be used to implement the encoder  400 . 
     Similarly, in various exemplary embodiments the decoder  500  is implemented on a programmed general purpose computer. However, the decoder  500  can also be implemented on a special purpose computer, a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA or PAL, or the like. In general, any device, which is capable of implementing step S 1700  of  FIGS. 2 and 5 , can be used to implement the decoder  500 . 
     It should be appreciated that the compression systems and methods of this invention can use any set of byte-oriented compression and decompression techniques. The compression/decompression methods and systems of this invention can be used with any number of systems, including digital printers, digital copiers, scanners, and the like that need to provide compressed or decompressed images. 
     While this invention has been described in conjunction with the exemplary embodiments outlined above, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the exemplary embodiments of the invention may be made without departing from the spirit and scope of the invention.