Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-11-16
2004-03-16
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S248000, C358S426010
Reexamination Certificate
active
06707948
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally concerns digital data compression and decompression, particularly the compression and decompression of digital data representing images, and still more particularly color images.
The present invention particularly concerns the compression and decompression of digital image, and color image, data in the computer and/or color printing, and/or in other transmission(s), of images so that (i) bandwidth between the computer and the printer (or other image recipient) may be conserved, while (ii) decompression of the compressed image is sequential, image side to image side (e.g., image top to image bottom), thus (iii) minimizing the memory requirement for an image data buffer in the printer (or other image recipient).
2. Description of the Prior Art
2.1 The Prior Art of Shapiro, of Pearlman, and of Teng and Neuhoff
The present invention will be seen to concern the compressing of digitized image data, particularly as may represent a color image. The disclosed technique of the invention will be seen to have the properties of (i) being efficient in the (typically different types of) memory (variously) required for each of compressing the image, storing the compressed image and decompressing the compressed image; (ii) permitting the printing of a high quality image, especially such as may be in color; and (iii) supporting a sequential decompression of the compressed image from one side of the image to the other—normally from the top of the image to the bottom. The technique is thus very suitable for applications such as printing images with inkjet or laser printers. Images transmitted in accordance with the present invention need not be printed. They can be, for example, transmitted over networks such as the Internet, displayed on video consoles in cars and on picture phones, and used in video conferencing—the main characteristic being that the images are sequentially decompressed, and are normally sequentially displayed in successive parts as decompression transpires.
In so functioning, the technique of the present invention may first be compared to the prior art apparatus and methods described in four (4) existing U.S. patents of Jerome Shapiro.
U.S. Pat. No. 5,315,670 to Jerome M. Shapiro for DIGITAL DATA COMPRESSION SYSTEM INCLUDING ZEROTREE COEFFICIENT CODING assigned to General Electric Company (Princeton, NJ) concerns a data processing system augmenting compression of non-zero values of significant coefficients by coding entries of a significance map independently of coding the values of significant non-zero coefficients. In the system a dedicated symbol represents a zerotree structure encompassing a related association of insignificant coefficients within the tree structure, thereby compactly representing each tree of insignificant coefficients.
The zerotree symbol represents that neither a root coefficient of the zerotree structure nor any descendant of the root coefficient has a magnitude greater than a given reference level. The zerotree structure is disclosed in the context of a pyramid-type image subband processor together with successive refinement quantization and entropy coding to facilitate data compression.
U.S. Pat. No. 5,321,776 to Shapiro for DATA COMPRESSION SYSTEM INCLUDING SUCCESSIVE APPROXIMATION QUANTIZER also assigned to General Electric Company concerns the same data processing system where the zerotree symbol represents that a coefficient is a root of a zerotree if, at a threshold T, the coefficient, and all of its descendants that have been found to be insignificant at larger thresholds, have magnitudes less than threshold T.
U.S. Pat. No. 5,412,741 to Shapiro for an APPARATUS AND METHOD FOR COMPRESSING INFORMATION assigned to David Sarnoff Research Center, Inc. (Princeton, NJ) concerns an apparatus that achieves high compression efficiency in a computationally efficient manner. A corresponding decoder apparatus, and methods, are also disclosed. The technique uses zerotree coding of wavelet coefficients in a much more efficient manner than previous techniques. The key is the dynamic generation of the list of coefficient indices to be scanned, whereby the dynamically generated list only contains coefficient indices for which a symbol must be encoded. This is claimed to be a dramatic improvement over the prior art in which a static list of coefficient indices is used and each coefficient must be individually checked to see whether (i) a symbol must be encoded, or (ii) it is completely predictable. Additionally, using dynamic list generation, the greater the compression of the signal, the less time it takes to perform the compression. Thus, using dynamic list generation, the computational burden is proportional to the size of the output compressed bit stream instead of being proportional to the size of the input signal or image.
Finally, U.S. Pat. No. 5,563,960 to Shapiro for an APPARATUS AND METHOD FOR EMPHASIZING A SELECTED REGION IN THE COMPRESSED REPRESENTATION OF AN IMAGE also assigned to David Sarnoff Research Center, Inc. concerns certain image analysis applications where it is desirable to compress the image while emphasizing a selected region of the image. The invention is a means for allocating more bits, and thus better quality in the decoded image, to the selected region at the expense of other regions of the image. This allows efficient compression of the image for storage or transmission with those regions deemed to be important preserved at high quality and other regions stored with minimal quality to preserve the context of the image.
The technique of the present invention may also be compared with a published paper of Said and Pearlman. See 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, 6(3):243-250, June 1996.
Finally, the technique of the present invention may be compared with a published paper of Teng and Neuhoff of the University of Michigan [hereinafter “Teng and Neuhoff”] See Chia-Yuan Teng and Dave L. Neuhoff; Quadtree-guided wavelet image coding, Proceedings DCC'96 (Data Compression Conference 1996, Snowbird, Utah, USA, Mar. 31-Apr. 3, 1996.) pp. 406-15.
In the quadtree-guided wavelet compression technique of Teng and Neuhoff only a single level of wavelet decomposition is used; thus it has only 4 subbands. The quantization and encoding of the wavelet coefficients proceeds as follows. The low—low band is divided into blocks of size k by k (typically k is 8 or 16) which are processed in raster scan order. For each block, the lower right corner (called the foot) is predicted from the pixel above the block in the same column, and to the left of the block in the same row. The prediction error is quantized and added to the prediction. Using this foot value, as well as the reconstructed values of neighboring pixels from previously encoded adjacent blocks, the rest of the pixels are predicted using linear interpolation. A quality test then checks how well the interpolation approximates the real pixel values. If the block passes the test, the quantized prediction error for the foot is transmitted using a variable length code. If not, the block is split into four sub blocks (a quadtree subdivision), and the same procedure is repeated for those. Coefficients in the high frequency bands are scalar quantized and run-length encoded in a manner that depends on how many times the corresponding coefficients in the low—low band were subdivided in the quadtree subdivision.
The present invention will be seen to involve the use of (i) a wavelet hybrid-filtering scheme and (ii) a line-by-line wavelet decoding technique. After the invention has been taught, the patents of Shapiro, and the papers of (i) Said and Pearlman, and of (ii) Teng and Neuhoff, will be re-visited in order that the present invention may be contrasted with this prior art.
U.S. Pat. No. 5,710,835 to Bradley for STORAGE AND RETRIEVAL OF LARGE DIGITAL IMAGES—as
Cosman Pamela Caren
Zeger Kenneth Alan
Chen Wenpeng
The Regents of the University of California
LandOfFree
Image compression for memory-constrained decoders 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 compression for memory-constrained decoders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image compression for memory-constrained decoders will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3288826