Dynamic, locally-adaptive, lossless palettization of color and grayscale images

Abstract

The present invention leverages a lossless pixel palettization scheme to locally compress portions of at least a two-dimensional image. This provides a lossless compression means with a compression ratio comparable with lossy compression means, allowing for efficient data transfers without loss of image information. By utilizing locally-adaptive palettization, two-dimensional pixel information can be exploited to increase compression performance. In one instance of the present invention, a locally-adaptive, lossless palettization scheme is utilized in conjunction with a one-dimensional compression scheme to yield a further increase in compression ratio. This allows for the exploitation of two-dimensional data information along with the further compression of information reduced to one dimension.

1. A system that facilitates data compression, comprising:
 a component that receives an N-dimensional image, where N is any integer from one to infinity; 
 at least one storage element that stores a buffer for recording information; 
 a compression component that utilizes, at least in part, locally-adaptive, lossless palettization to facilitate compression of the N-dimensional image, wherein the locally-adaptive, lossless palettization comprises dividing the N-dimensional image into a plurality of portions each comprising lines formed of a sequence of pixels, each pixel having a color or grayscale, and, for each of the plurality of portions:
 determining whether a sequence of pixel colors or grayscales in any of the lines matches a sequence previously recorded in the buffer, and if so, causing a reference to a location in the buffer at which the previous recordation occurred to be stored in the buffer in association with the sequence, and if not, causing an indication of the sequence of pixel colors or grayscales to be stored in the buffer; and 
 determining whether a color or grayscale of a pixel matches a color or grayscale previously recorded in the buffer, and if so, causing a reference to a location in the buffer at which the previous recordation occurred to be stored in the buffer in association with the pixel, and if not, causing an indication of the pixel color or grayscale to be stored in the buffer. 
 
 
   
   
     2. The system of  claim 1 , the N-dimensional image comprising a two-dimensional image. 
   
   
     3. The system of  claim 1 , the compression component employing the locally-adaptive, lossless palettization when characteristics of image data related to the N-dimensional image are equal to or below a threshold value. 
   
   
     4. The system of  claim 3 , the characteristics of the image data comprising at least one selected from the group consisting of pixel colors and pixel grayscales. 
   
   
     5. The system of  claim 4 , the threshold value comprising a maximum number of at least one selected from the group consisting of pixel colors and pixel grayscales. 
   
   
     6. The system of  claim 1 , the compression component optimizing compression of the N-dimensional image by ordering indices representative of image data and reducing indices bit counts as values of indices decrease. 
   
   
     7. The system of  claim 1 , the compression component further utilizing, subsequent to the locally-adaptive, lossless palettization, a one-dimensional compression technique to further compress the N-dimensional image. 
   
   
     8. The system of  claim 7 , the one-dimensional technique comprising at least one selected from the group consisting of LZ77 compression and LZ78 compression. 
   
   
     9. The system of  claim 1 , wherein the portions comprise macroblocks. 
   
   
     10. The system of  claim 9 , the locally-adaptive, lossless palettization further comprising, at least in part, further splitting the macroblocks to facilitate compression. 
   
   
     11. The system of  claim 1 , wherein the buffer comprises a last recently used (LRU) buffer for indexing image data. 
   
   
     12. The system of  claim 11 , the LRU buffer maintains image data in relative order to facilitate further compression. 
   
   
     13. The system of  claim 1 , the locally-adaptive, lossless palettization comprising dynamic, locally-adaptive, palettization. 
   
   
     14. At least one tangible non-volatile computer readable storage medium having instructions encoded thereon which, when executed, perform a method for facilitating data compression, the method comprising:
 receiving an N-dimensional image, where N is any integer from one to infinity; and 
 utilizing, at least in part, locally-adaptive, lossless palettization to facilitate compression of the N-dimensional image, the locally-adaptive, lossless palettization comprising dividing the N-dimensional image into a plurality of portions each comprising lines formed of a sequence of pixels, each pixel having a color or grayscale, and, for each of the plurality of portions:
 determining whether a sequence of pixel colors or grayscales in any of the lines matches a sequence previously recorded in a buffer, and if so, causing a reference to a location in the buffer at which the previous recordation occurred to be stored in the buffer in association with the sequence, and if not, causing an indication of the sequence of pixel colors or grayscales to be stored in the buffer; and 
 determining whether a color or grayscale of a pixel matches a color or grayscale previously recorded in the buffer, and if so, causing a reference to a location in the buffer at which the previous recordation occurred to be stored in the buffer in association with the pixel, and if not, causing an indication of the pixel color or grayscale to be stored in the buffer. 
 
 
   
   
     15. The at least one tangible computer-readable medium of  claim 14 , the N-dimensional image comprising a two-dimensional image. 
   
   
     16. The at least one tangible computer-readable medium of  claim 14 , wherein the method further comprises, subsequent to the locally-adaptive, lossless palettization:
 compressing an output of the locally-adaptive, lossless palettization utilizing a one-dimensional technique to further reduce redundancies. 
 
   
   
     17. The at least one tangible computer-readable medium of  claim 16 , the one-dimensional technique comprising at least one selected from the group consisting of LZ77 compression and LZ78 compression. 
   
   
     18. The at least one tangible computer-readable medium of  claim 14 , wherein each portion comprises a macroblock, and wherein the method further comprises:
 ordering index values representative of the pixel characteristics from the non-matching macroblock lines in descending order of value; and 
 transmitting the index values, in order, utilizing a reduced set of representation bits derived from, at least in part, a total number of index values for a macroblock, a number of previously transmitted index values, and a value of a last index transmitted. 
 
   
   
     19. The at least one tangible computer-readable medium of  claim 18 , the reduced set of representation bits utilizing a bit count determined by:
   bit count=log 2 ( n+m−k+ 1)  Eq. (4) 
 where n is the value of the last index transmitted, m is the number of previously transmitted index values, and k is the total number of index values for the macroblock.