Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2001-03-16
2001-12-11
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S263000, C382S264000
Reexamination Certificate
active
06330367
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a compressive image encoding and decoding method using edge synthesis and the inverse wavelet transform, and to digital image encoding and decoding devices employing this method.
Compression is essential for efficient storage and transmission of digitized images. Compression methods have been described by the Joint Photographic Experts Group (JPEG) for still images, and the Motion Picture Experts Group (MPEG) for moving images. The JPEG method involves a discrete cosine transform (DCT), followed by quantization and variable-length encoding. The MPEG method involves detecting motion vectors. Both methods require substantial computation, the detection of motion vectors being particularly demanding.
Recently there has been much interest in the wavelet transform as a means of obtaining high compression ratios with relatively modest amounts of computation. This transform employs a family of wavelets related by dilation and translation; that is, the family consists of occurrences of the same basic wavelet at different locations and on different scales. If the scales form a progressively doubling sequence, and if the basic wavelet is zero everywhere except in a limited domain, wavelet transforms and inverse wavelet transforms can be carried out with efficient computational algorithms.
A wavelet transform can be described as a filtering process executed at each wavelet scale. A digitized image, for example, is transformed by filtering with the basic wavelet, then with the basic wave let dilated by a factor of two, then with the basic wavelet dilated by a factor of four, and so on.
One prior-art wavelet encoding scheme employs a complementary pair of wavelets to divide an image into a high-frequency component and a low-frequency component. These components contain information about variations on scales respectively less than and greater than a certain cut-off scale. This process is iterated on the low-frequency component with a doubling of the wavelet scale, obtaining new low-frequency and high-frequency components, then iterated again on the new low-frequency component, and so on. After a certain number of iterations, the components are encoded by an encoding scheme that works from low-toward high-frequency information. This scheme enables accurate image reconstruction, but retains too much high-frequency information to achieve high compression ratios.
Another prior-art wavelet encoding scheme employs a basic wavelet that is the first derivative of a smoothing filter (that is, the first derivative of a low-pass filtering function). This type of wavelet acts as a high-pass filter. High-frequency information is obtained by detecting local peaks (local maxima of absolute values) in the result of the wavelet transform, which correspond to edges in the original image. The size and location of the peak values at a selected scale are encoded, along with a low-frequency image obtained by smoothing at the largest scale of the wavelet transform. Fairly high compression ratios can be obtained in this way.
To reconstruct the original image from the encoded data, this prior-art method employs an algorithm derived from a mathematical procedure involving iterated projections in Hilbert space. Unrder ideal conditions, the projections converge toward a unique set of data that (i) have the required local peak values and (ii) are within the range of the wavelet transform operator. An inverse wavelet transform is thcn carried out on the converged data to obtain the original image.
It has yet to be shown, however, that the projections always converge, or that data satisfying conditions (i) and (ii) are unique. In practice, there is difficulty in knowing when to stop iterating. For some images, it seems that data satisfying (i) and (ii) are not unique, and instead of converging, the iteration wanders endlessly through Hubert space, first approaching the desired image transform, then moving away again.
Still higher compression ratios have been obtained by a fractal compression scheme, but this requires a very large amount of computation in the encoding process.
SUMMARY OF THE INVENTION
It is accordingly an object of the present invention to encode digitized images efficiently, with a high compression ratio but without requiring extensive computation.
Another object of the invention is to encode moving images efficiently.
Still another object is to reconstruct digitized images from encoded information efficiently and reliably.
Yet another object is to reconstruct digitized moving images efficiently and reliably.
The invented method of encoding a digitized image comprises the steps of:
detecting edges in the digitized image;
encoding the position and sharpness of the detected edges to generate edge information;
filtering the digitized image by a low-pass filter to generate a low-frequency image; and
encoding the low-frequency image to generate low-frequency information.
The invented method of reconstructing a digitized image encoded by the invented encoding method comprises the steps of:
generating a horizontal edge image and a vertical edge image from the encoded edge information;
synthesizing a pair of high-frequency images by filtering the horizontal edge image and vertical edge image with an edge synthesis filter;
decoding the encoded low-frequency information to obtain a low-frequency image; and
performing an inverse wavelet transform on the low-frequency image and the high-frequency images.
REFERENCES:
patent: 3035121 (1962-05-01), Schreiber
patent: 4908872 (1990-03-01), Toriu et al.
patent: 5050230 (1991-09-01), Jones et al.
patent: 5124811 (1992-06-01), Ohsawa et al.
patent: 5359674 (1994-10-01), Wal
patent: 5414780 (1995-05-01), Carnahan
patent: 5434808 (1995-07-01), Cohen
patent: 5442459 (1995-08-01), Gahang
patent: 5550936 (1996-08-01), Someya et al.
patent: 93-13624 (1993-07-01), None
patent: 93-20653 (1993-10-01), None
“Compact Image Coding from Edges with Wavelets,” Stephane Mallat et al, ICASSP Proceedings,IEEE, 1991, pp. 2745-2748.
“Characterization of Signals From Multiscale Edges,” S. Mallat et al.,IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 14, No. 7, Jul. 1992, pp. 710-732.
“Edge Modified Vector Quantization For Image Compression,” P. Yu et al.,Discovering A New World Of Communications, Chicago, Jun. 14-18, 1992, vol. 1 of 4, Jun. 1992, Institute of Electrical and Electronics Engineers, pp. 532-536.
“Image Sequence Coding Using Oriented Edges,” G. Guinta et al.,Signal Processing. Image Communication, vol. 2, No. 4, Dec. 1990, pp. 429-440.
“Hierarchical Video Coding Scheme With Scalability And Compatibility,” Tsuyoshi Hanamura et al.,Electronics&Communications In Japan, Part I, Communications, vol. 77, No. 3, Mar. 1994, pp. 25-40.
“Region And Texture Coding Of TV Pictures,” D. Morgan et al., International Conference On Image Processing And Its Applications, Jul. 18, 1989, pp. 536-540.
Eddins et al., A Three-Source Multirate Model for Image Compression, Apr. 1990, pp. 2089-2094, IEEE, ICASSP-90, 5 pages, vol. 2970.
Frank Robert
Johnson Timothy M.
OKI Electric Industry Co., Ltd.
Venable
Wood Allen
LandOfFree
Image encoding and decoding using separate hierarchical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image encoding and decoding using separate hierarchical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image encoding and decoding using separate hierarchical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591182