Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-03-24
2004-08-31
Au, Amelia M. (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
C382S166000
Reexamination Certificate
active
06785425
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to lossless or near lossless image compression.
BACKGROUND OF THE INVENTION
Many techniques, like pre-press imaging and medical imaging, demand very high quality. The images are often very large, say 2048×2048×3 pixels (e.g. in RGB format), thus requiring huge storage spaces and long transfer times. In order to alleviate these problems while keeping up with the “no loss” constraint, lossless compression techniques should be employed. While the compression ratio is rather small (of the order of 2-4), the benefits are quite worth the effort.
Theoretically, the minimal code length may be achieved by first transforming the color planes into three independent planes, decorrelating the planes in order to make them independent, and then compressing each plane optimally. That is why, most of the leading image compression techniques treat the color image (e.g. RGB) by this way, i.e. as three non-related gray-scale images. These include compression algorithms, such as:
BPTC [J. A. Robinson, “Efficient General-Purpose Image Compression with Binary Tree Predictive Coding”, IEEE transactions on Image Processing, vol. 6, no. 4, pp. 601-608, April 1997],
CALIC [X. Wu, N. Memon and K. Sayood, “A Context-Based, Adaptive, Lossless/Nearly-Lossless Coding Scheme for Continuous-Tone Images”, Proposal for the initial ISO/JPEG evaluation, http://www.csd.uwo.ca/faculty/wu/iso.ps, July 1995; and X. Wu et al, “An Algorithmic Study on Lossless Image Compression”, in Proceedings of the 1996 Data Compression Conference (Snowbird, Utah, USA), pp. 150-159, March 1996],
FELICS [P. G. Howard and J. S. Vitter, “Fast and Efficient Lossless Image Compression”, in Proceedings of the 1993 IEEE Data Compression Conference (Snowbird, Utah, USA), pp. 351-360, March 1993],
LOCO-I [M. J. Weinberger, G. Seroussi and G. Sapiro, “LOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithm”, in Proceedings of the 1996 IEEE Data Compression Conference (Snowbird, Utah, USA), pp. 140-149, March 1996], and
SPIHT [A. Said and W. A. Pearlman, “A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees”, IEEE transactions on Circuits and Systems for Video Technology, vol. 6, June 1996].
This approach, however, has not given promising results in practice. Due to its high complexity, these techniques requires high computational power.
Clearly, one can gain benefits in image compressing from exploiting the possible inter-color planes correlation. Therefore, another approach for treating the color image was employed. The main idea of this approach is to encode the current plane by using previous pixels from the same plane and from the other, already encoded, planes. The general concept is follows: first to encode one plane, and then to encode another plane by using the fact that the first plane is known already to the decoder, and finally, to encode the third plane by using the fact that both (first and second) planes are known to the decoder. This approach is implemented in Inter-Band CALIC algorithm, where the first, second and third color planes where the R, G and B planes, respectively (see X.
Wu, W. K. Choi, and N. Memon, “Lossless Interframe Image Compression via Context Modeling”, in Proceedings of the 1998 Data Compression Conference (Snowbird, Utah, USA), pp. 378-387, March 1998). The approach of CALIC offers superior results, however, the method based on the algorithm of CALIC requires very high computational power.
Lossless image compression schemes often consist of two distinct and independent components: modeling and coding. This scheme of the lossless image compression is reflected in the block diagrame of FIG.
1
. The dashed areas
11
in the image icons represent the scanned past data, on which the probability assignment is based, while the black dots
12
represent the pixel currently coded.
The modeling part can be formulated as an inductive inference problem, in which an image is observed pixel by pixel in some pre-defined order (i.e. raster scan). Hence, observing a color image is a simple generalization of a gray-scale image scan, where the pixels of different color planes are interlaced. The term pixel here denotes a monochrome picture element, whereas the term color-pixel denotes a color picture element (consisting of three pixels).
The first step of the modeling is a prediction step in which by knowing the past data X
1
=X
1
, X
2
, . . . . , X
i
, the next pixel's conditional distribution p(X
i+1
|X
i
) is estimated in order to predict a deterministic value for the next pixel X
i+1
. Ideally, the code length contributed by X
i+1
is −log
2
[p(X
i+1
|X
1
)] bits, which averages to the entropy of the probabilistic model. On the next step of the modeling, one performs a determination of the context on which X
i+1
occurs. Indeed, a prediction of the next pixel using a small neighborhood is better performed when conditioned by contexts. If the image is not truly a stationary process, one expects it to be a mixture of different types of processes, which may be classified according to image texture and local smoothness. This is also treated by contexts, which condition the probabilistic behavior of the image. On the last step of the modeling a probabilistic model the prediction residual (the error value), conditioned on the context of X
i+1
, is generated. The prediction residual (error) is obtained from subtraction of the predicted value from the actual value. The errors and probability distribution of the prediction error values are then coded to produce an output.
The coding part of the lossless image compression schemes of the modeled prediction residuals may be done by an arithmetic encoder [see J. Rissanen, “Generalized Kraft Inequality and Arithmetic Coding,” IBM Journal on Recent Developments, vol. 20, no. 3, pp. 198-203, May 1976; and G. G. Langdon, Jr., “An Introduction to Arithmetic Coding,” IBM Journal on Recent Developments, vol. 28, pp. 135-149, 1984], but this means a high complexity algorithm. Huffman coding of the prediction error [see D. A. Huffman, “A Method for the Construction of Minimum Redundancy Codes”, in Proceedings of IRE, vol. 40, pp. 1098-1101, 1952] is much simpler, but it results in lower performance.
A method based on the aforementioned concept of modeling, which overcomes many problems of coding was implemented in U.S. Pat. No. 5,680,129 and in U.S. Pat. No. 5,835,034 by Weinberger, Seroussi and Sapiro. They invented the LOCO-I algorithm forming the basis for the draft standard JPEG-LS of ISO, ISO/ITU ISO/IEC JTC1/SC29 WG1(JPEG/JBIG) for lossless and near-lossless compression of continuous-tone images, Draft International Standard DIS14495-1 (JPEG-LS), 1998. LOCO-I combines the simplicity of Huffman coding with the compression potential of context models. A small number of free statistical parameters is used in LOCO-I to approach the capability of much more complex universal context modeling techniques without the drawbacks of context-dilution. Such a context dilution can occur due to the exponential growth of the number of states with respect to the model's order. Avoiding the dilution is achieved by using a small efficient context space along with the adaptive, symbol-wise, Golomb-Rice code, depending on a single-parameter probability distribution. Another useful feature of LOCO-I is the embedded alphabet extension (run-mode), which further reduces the code redundancy when encoding runs.
However, despite a big step forward in the compressing technique there is still a need in the art to provide an improved method for lossless image compression, especially for color images. Indeed, the most advanced technques such as aforementioned U.S. Pat. Nos. 5,680,129 and 5,835,034 deal mostly with intra-plane approach. Despite the authors of LOCO-I describe the possibility of both intra- and inter-plane correlation for component predictio
Barequet Raz
Barkan Stanley
Feder Meir
Au Amelia M.
Fitch Even Tabin & Flannery
LaRose Colin
Ramot At Tel-Aviv University Ltd.
LandOfFree
Method and system for compression of images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for compression of images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for compression of images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3285666