Image analysis – Image enhancement or restoration – Image filter
Reexamination Certificate
2001-04-13
2004-12-28
Patel, Kanji (Department: 2625)
Image analysis
Image enhancement or restoration
Image filter
C382S103000, C382S240000, C348S169000, C375S240190
Reexamination Certificate
active
06836569
ABSTRACT:
BACKGROUND OF INVENTION
The invention relates generally to a multi-dimensional signal processing method and apparatus, and in particular to a method and apparatus useful for processing multi-dimensional signals, such as two-dimensional images.
The invention is particularly pertinent to the field of image data processing and compression. Image data compression is a process which encodes images for storage or transmission over a communication channel, with fewer bits than what is used by the uncoded image. The goal is to reduce the amount of degradation introduced by such an encoding, for a given data rate. The invention is also relevant for applications to the restoration of signals by removing noises or to matching and classification applications.
In signal processing, efficient procedures often require to compute a stable signal representation which provides precise signal approximations with few non-zero coefficients. Signal compression applications are then implemented with quantization and entropy coding procedures. At high compression rates, it has been shown in S. Mallat and F. Falzon, “Analysis of low bit rate image transform coding,” IEEE Trans. Signal Processing, vol. 46, pp. 1027-1042, 1998, the contents of which are incorporated in reference herein, that the efficiency of a compression algorithm essentially depends upon the ability to construct a precise signal approximation from few non-zero coefficients in the representation. Noise removal algorithms are also efficiently implemented with linear or non-linear diagonal operators over such representations, including thresholding strategies. Other applications such as classification or signal matching can also take advantage of sparse signal representations to reduce the amount of computations in the classification or matching algorithms.
For signal processing, the stability requirement of the signal representation has motivated the use of bases and in particular orthogonal bases. The signal is then represented by its inner products with the different vectors of the orthogonal basis. A sparse representation is obtained by setting to zero the coefficients of smallest amplitude. The Fourier transform which represents signals by their decomposition coefficients in a Fourier basis have mostly dominated signal processing until the 1980's. This basis is indeed particularly efficient to represent smooth signals or stationary signals. During the last twenty years, different signal representations have been constructed, with fast procedures which decompose the signal in a separable basis. Block transforms and in particular block cosine bases have found important applications in image processing. The JPEG still image coding standard is an application which quantizes and Huffman encodes the block cosine coefficients of an image. More recently, separable wavelet bases have been shown to provide a more sparse image representation, which therefore improves the applications. Wavelets compute local image variations at different scales. In particular the JPEG standard is now being replaced by the JPEG-2000 standard which quantizes and encodes the image coefficients in a separable wavelet basis: “JPEG 2000, ISO/IEC 15444-1:2000,” 2000, the contents of which are incorporated in reference herein. Non-linear noise removal applications have been developed by thresholding the wavelet coefficients of noisy signals in D. Donoho and I. Johnstone, “Ideal spatial adaptation via wavelet shrinkage,” Biometrika, vol. 81, pp. 425-455, December 1994, the contents of which are incorporated in reference herein.
To obtain a more sparse representation, foveal procedures gather high resolution data only in the neighborhood of selected points in the image, as described in E. Chang, S. Mallat, and C. Yap, “Wavelet foveation,” Applied and Computational Harmonic Analysis, pp. 312-335, 2000, the contents of which are incorporated in reference herein. This information is equivalent to computing wavelet coefficients only in the neighborhood of specific points as shown in the above reference. This strategy is similar to the behavior of a retina, which provides a high resolution measurements where the fovea is centered and a resolution which decreases when the distance to the fovea center increases. Applications to image compressions have also been developed in the above reference by Chang et al.
The main limitation of bases such as wavelet or block cosine bases, currently used for signal representation, is that these bases do not take advantage of the geometrical regularity of many signal structures. Indeed, these bases are composed of vectors having a support which is not adapted to the elongation of the signal structures such as regular edges. Curvelet bases have recently been introduced in E. Candes and D. Donoho, “Curvelets: A surprisingly effective nonadaptive representation of objects with edges,” tech. rep., Stanford Univ., 1999, the contents of which are incorporated in reference herein, to take partially advantage of the geometrical regularity of the signal, by using elongated vectors along different directions. Yet, this strategy has not been able to improve results currently obtained with a wavelet basis on natural images, because it does not incorporate explicitely the geometrical information.
To incorporate this geometrical regularity, edge oriented representations have been developed in image processing. An edge detector computes an edge map with discretized differential operators and computes some coefficients in order to reconstruct an approximation of the image grey level between edges. In S. Carlsson, “Sketch based coding of gray level images,” IEEE Transaction on Signal Processing, vol. 15, pp. 57-83, July 1988, the contents of which are incorporated in reference herein, an edge detector computes an edge map with discretized derivative operators. For compression applications, chain algorithms are used to represent the chains of edge points with as few bits as possible. The left and right pixel values along the edges are kept and an image is reconstructed from these left and right values with a diffusion process. If all edges were step edges with no noise, this representation would be appropriate but it is rarely the case, and as a result the reconstructed image is not sufficiently close to the original image. An error image is computed and coded with a Laplacian pyramid, but this requires too much bits to be competitive with a procedure such as JPEG-2000.
The above referenced method of Carlsson has been extended in C.-Y. Fu and L. I. Petrich, “Image compression technique.” U.S. Pat. No. 5,615,287, the contents of which are incorporated in reference herein, by keeping weighted average values along the left and right sides of the edges. Although the information is different, there is still little information to characterize the image transition when the edge is not a step edge. Another extension of the method of Carlsson has been proposed in D. Geiger, “Image compression method and apparatus.” U.S. Pat. No. 5,416,855, the contents of which are incorporated in reference herein. An iterative process defines a set of edge pixels and assigns a value to them. A reconstructed image is then obtained from these values with a diffusion process. This representation can contain more accurate information on the image than that of Carlsson but it then requires many pixels to reconstruct the different types of edges and is therefore not sparse enough.
In S. Mallat and S. Zhong, “Characterization of signals from multiscale edges,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 7, pp. 710-732, 1992, the contents of which are incorporated in reference herein, a wavelet edge based image representation is computed, which carries more information than the above referenced method of Carlsson. However, this representation requires a different edge map at each scale of the wavelet transform, which is a handicap to produce a sparse representation. In X. Xue, “Image compression based on low-pass wavelet transform and multi-scale edge c
Le Pennec Erwan
Mallat Stéphane
Baker & Botts LLP
Patel Kanji
LandOfFree
Method and apparatus for processing or compressing... 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 apparatus for processing or compressing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for processing or compressing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3325370