Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-03-24
2002-01-29
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S239000, C382S238000, C382S248000
Reexamination Certificate
active
06343154
ABSTRACT:
BACKGROUND OF THE INVENTION
Books and magazines often contain pages containing audacious mixtures of color images and text. The present invention relates to a fast and efficient method of coding partially-masked image information of such documents by wavelet coding without wasting bits on the image data that is masked by foreground text.
A simplified block diagram of a wavelet coding system is shown in FIG.
1
. The system includes an encoder
100
and a decoder
200
. The encoder
100
codes input image information according to wavelet compression techniques and outputs coded image data to a channel
300
. The coded image data includes wavelet coefficients representing the image data. The decoder
200
retrieves the coded image data from the channel
300
and decodes-it according to wavelet decompression techniques.
Multi-resolution wavelet decomposition is one of the most efficient schemes for coding color images. These schemes involve several operations: color space transform, image decomposition, coefficient quantization and coefficient coding.
Image information to be coded is represented as a linear combination of locally supported wavelets. An example of wavelet support is shown in FIG.
2
(
a
). Wavelets extend over a predetermined area of image display. For the length of every wavelet such as W
0
, two other wavelets W
1a
and W
1b
extend half of its length. The length of each underlying wavelet W
1a
, W
1b
is itself supported by two other wavelets W
2a
, W
2b
, W
2c
and W
2d
. This support structure may continue until a wavelet represents only a single pixel.
Image data may be coded as a linear combination of the wavelets. Consider the image data of FIG.
2
(
b
). As shown in FIG.
2
(
c
), the image data may be considered as a linear combination of the wavelets of FIG.
2
(
a
). To represent the image data, only the coefficients of the wavelets that represent the image data need by coded. The image data of FIG.
2
(
b
) may be coded as:
W
0
W
1a
W
1b
W
2a
W
2b
W
2c
W
2d
W
3a
W
3b
W
3c
W
3d
W
3e
W
3f
W
3g
W
3h
1
0
1
0
0
1
0
0
5
0
0
0
0
3
0
Because most of the wavelet coefficients are zero, the coefficients themselves may be coded using highly efficient coding methods.
The linear combination of coefficients can be expressed in matrix notation as:
Aw=x (1)
where w is a vector of wavelet coefficients, x is a vector of pixel values, and A is a square matrix whose columns represent the wavelet basis. Matrix A usually describes an orthogonal or nearly orthogonal transformation. When a decoder
200
is given the wavelet coefficient, then it may generate the image data x using the process of Equation. 1. Efficient multi-scale algorithms perform image decomposition (i.e. computing A
−1
x) and image reconstruction (i.e. computing Aw) in time proportional to the number of pixels in the image.
In practice, most image data is smooth. It differs from the exemplary image data of FIG.
2
(
b
) in that the image data generally does not possess abrupt variations in image value. Whereas the image data used in the example of FIG.
2
(
b
) possesses significant energy in the coefficients of shorter wavelets, natural image data does not often possess energy in these coefficients.
The image local smoothness ensures that the distribution of the wavelet coefficients is sharply concentrated around zero. High compression efficiency is achieved using quantization and coding schemes that take advantage of this peaked distribution.
When a unitary source of information, such as a page of a book or magazine, contains both text and image data, the text may be considered as a “mask” that overlays image data beneath the text. Coding of any part of the image data beneath the masking text becomes unnecessary because the text will mask it from being observed. In the case of wavelet encoding. Masked wavelets need not be coded.
When image data is masked, the mask blocks image data thereunder from being observed. Coding errors that are applied to masked image data are unimportant because the masked image data will be replaced with data from the mask. Also, the mask disrupts the smoothness of the image data. It introduces sharp differences in the value of the image data at the boundaries between the image and the foreground text. Coding of the sharp differences would cause significant energy to be placed in the short wavelet coefficients, which would cause coding inefficiencies to arise in coding the image data. Such coding inefficiencies are particularly undesirable because coding errors that occur below the mask will be unnoticed at the decoder where the mask will overlay the erroneous image data. Accordingly, there is a need in the art for a image coder that codes masked image data efficiently.
SUMMARY OF THE INVENTION
The disadvantage of the prior art are alleviated to a great extent by a successive projections algorithm that codes partially-masked image data with a minimum number of wavelet coefficients. According to the successive projections algorithm unmasked image information is coded by wavelet decomposition. For those wavelets whose energy lies substantially below the mask, the wavelet coefficients are canceled. Image reconstruction is performed based on the remaining coefficients. For the image information that lies outside of the mask, the reconstructed image information is replaced with the original image information. The wavelet coding, coefficient cancellation, and image reconstruction repeats until convergence is reached.
The present invention also provides a simple and direct numerical method for coding the image information in a manner that obtains quick convergence. In a first embodiment, quick convergence is obtained by performing masked wavelet encoding in stages, each stage associated with a predetermined wavelet scale. By advancing the stages from finest scale to coarsest scale, coefficients of masked wavelets are identifies early in the coding process. In a second embodiment, quick convergence is obtained by introducing overshoot techniques to the projections of images.
REFERENCES:
patent: 5563960 (1996-10-01), Shapiro
patent: 5764805 (1998-06-01), Martucci et al.
patent: 5822458 (1998-10-01), Silverstein et al.
patent: 5845243 (1998-12-01), Smart et al.
patent: 5896176 (1999-04-01), Das et al.
Bottou, Leon et al.:High Quality Document Image Compression with “DjVu”, Journal of Electronic Imaging, Jul. 1998, vol. 7, No. 3, pp. 417-420.
Santago Pete et al.:New Solution for Frequency and Pixel Domain Coding Using Convex Sets, SPIE, Aug. 1985, Applications of Digital Image Processing VIII, vol. 575, pp. 66-70.
Faryar A. Farid et al.:Transform/Time Coding Domain Using the Method of Projection onto Convex Sets, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, 1985, vol. 1, pp. 351-354.
Antonini, Marc et al.:Image Coding Using Wavelet Transform, IEEE Transactions on Image Processing, Apr. 1992, vol. 1, No. 2, pp. 205-220.
Chen, Homer H. Et al.:A Block Transform Coder for Arbitrarily Shaped Image Segments, IEEE 1994, AT&T Bell Laboratories, Holmdel, NJ, pp. 85-89.
Bottou Leon
Pigeon Steven
AT&T Corp.
Chen Wenpeng
LandOfFree
Compression of partially-masked image data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression of partially-masked image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression of partially-masked image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2861012