Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-03-22
2003-10-14
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
Reexamination Certificate
active
06633679
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to image compression methodologies and more particularly, to an apparatus and method for compression of still images
2. Prior Art
Still image compression techniques have been improvised and improved significantly over the past ten years to envelop highly specialized algorithms and mathematical techniques in order to increase the compression ratio of the image. This has been especially the case in recent years as transmission of digital images, particularly color images, over computer networks or telephone lines is highly demanded by consumers. Particularly, transmission of these color images at high speed is desired. In order to increase the speed of transmission for the digitized color image, compression of the image is required. There has been traditionally a trade off between compression and quality however, requiring that the developer of compression techniques and apparatus choose between high compression ratios and therefor increased transmission speeds against the quality of the image once it is decompressed to its initial, or quasi-initial appearance. Inherent in most compression techniques are tradeoffs wherein, particular aspects of the image are sacrificed in order to compress the image to a satisfactory size. These losses of data can include loss of color definition, sharpness of edge lines, or other aspects of image quality. This sacrifice of image quality, particularly for color images, comes at high costs, particularly when the typical compression ratio achieved is less than 20 to 1.
Standard image compression techniques include the following methodology:
In the Digital Conversion of Image step, a CMYK, CMY or Postscript image is scanned and prepared in digital format which most likely includes representing the image in RGB or YUV components. RGB and YUV formatting allows the color image to be broken down into distinct color spectrums or luminance and then compressed based upon those spectrums. After reducing the image to particular color or luminance components, the components may be broken down into blocks of pixels for easy manipulation and analysis.
The next typical step involves generating the matrix transform wherein the image, in its component form, is transformed form one domain to another. This allows the image to be removed from the standard two dimensional image space to the frequency domain thereby causing the coefficients created to be the target of the compression routines and not the color component values themselves. The Discrete Cosine Transform or Fourier Transforms (transforms based upon a linear combinatory of sine and cosine waves with different coefficients) are used to convert the image data to the frequency domain and create the coefficient matrix. These transforms indicate the behavior in the frequency domain of the image as such, they are typically well for homogeneous image areas. The resulting transform coefficients are then compressed by possibly thresholding and also through quantization routines. Quantization may reduce the precision of the coefficients generated in the transform step but allows the actual values to be compressed. This quantization step scales the coefficients by a step size and then rounds off the value to the next integer. Finally, entropy or source encoding is utilized to further compress the quantized data. This encoding step may include run length encoding, Lempel-Ziv-Welch, Huffman, DCPM (differential pulse code modulation) or other well known coding techniques.
More recently, Fourier or DCT transformation matrices have been replaced with more complicated Wavelet transforms. As two types of compression models, lossy coding and lossless coding, have become standard, Wavelet transforms have provided a means to significantly increase compression ratios for the lossless type of compression model. In a lossless type of compression model, the input data, typically intensity data, is converted to codewords which have fewer storage requirements than the data that is coded. In the lossy model, intensity data may be quantized prior to utilization of codewords or transformation. Quantization eliminates those data elements which are not considered relevant to the characteristics of the image. Prior to the quantization step in lossy compression models, transforms are typically utilized to compress the data prior to action upon it by quantization routines.
Wavelet transforms are based on a linear combination of waveforms that are not periodic but display a strong locality, i.e. the local specifics of the image. In wavelet transformations, unlike in a DCT transformation matrix, the image is transformed as a whole, not in modularized pixel blocks. A set of dependent functions are derived from a prototype function each of which have fundamental characteristics for transformation of the data (i.e. scale and transform) such that tradeoffs may be made based upon application specific requirements. These tradeoffs flow from resolution in the time and frequency domain. The dependent functions may be scaled and transformed to meet the requirements of a particular application. Scaling and transformation coefficients are similar to the DCT coefficients. The varying dependent functions allow tradeoffs between the frequency and time resolution. As a result of these wavelet transforms, the high and low frequency portions of the image will be processed independently thus allowing the wavelet functions to act as band pass filters. Each of these filtered signals may then be further separated into various average signals and horizontal, vertical and diagonal features.
Filtering of the image in the horizontal, vertical and diagonal direction may be accomplished to produce separate images through use of high and low filter pass techniques along with an average image signal. Iterative passes may be made to further compress the image thereby producing coefficients for each image which may then be compressed further through encoding or other methods mentioned above. All of these techniques utilize data transform methodology function.
Representation of data using a set of basis functions is well known, with Fourier techniques being perhaps the most familiar. Other transform methods include the fast Fourier transform (FFT), the discrete cosine transform (DCT), and a variety of wavelet transforms. The rationalization for such transform methods is that the basis functions can be encoded by coefficient values and that certain coefficients may be treated as more significant than others based on the information content of the original source data. In doing so, they effectively regard certain coefficient values and correlations of the sort mimicked by the basis functions as more important than any other values or correlations. In essence, transform methods are a means of categorizing the correlations in an image. The limitations of such methods are a result of the unpredictability of the correlations. The variations in luminance and color that characterize an image are often localized and change across the face of the image. As a result, FFT and DCT based methods, such as JPEG, often first segment an image into a number of blocks so that the analysis of correlations can be restricted to a small area of the image. A consequence of this approach is that bothersome discontinuities can occur at the edges of the blocks.
Historical wavelet-based methods avoid this “blocking effect” somewhat by using basis functions that are more localized than sine and cosine functions. However, a problem with these historical wavelet-based methods is that they assume that a particular function is appropriate for an image and that the entire image may be described by the superposition of scaled versions of that function centered at different places within the image. Given the complexity of image data, such a presumption is often unjustified. Consequently, historical wavelet based methods tend to produce textural blurring and noticeable changes in processing and coding quality within and between imag
Couso Jose L.
Middleton & Reutlinger
Salazar John F.
Teletechnologies, Ltd.
LandOfFree
Visually lossless still image compression for CMYK, CMY and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Visually lossless still image compression for CMYK, CMY and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Visually lossless still image compression for CMYK, CMY and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129121