Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-06-09
2004-07-06
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
Reexamination Certificate
active
06760481
ABSTRACT:
The invention relates generally to the processing of image data. Especially the invention applies to coding and decoding of still image data for compression. One application of the invention is for storage and transmission of image data in a mobile telecommunications system.
Digital images tend to include a large amount of data that should be compressed efficiently to allow their usage in different imaging applications. These applications include storage, which varies from a few images in a digital camera to thousands of images in a library for image archival. Applications also include image transmission, which covers mobile and wireless communications as well as the Internet. Therefore, several compression techniques have been developed to fulfil these applications. The efficiency of a compression technique depends mainly on the application it addresses. For mobile communications systems, a compression technique should consider the low memory capacity of the mobile phone and the limited capacity of the transmission channel.
FIG. 1
illustrates a block diagram of a typical image compression and transfer system
100
. The digitized input image data Y is first mapped to w(Y) by a transfer function,
102
. This may take the form of a transmormation from the spatial domain, where the image is represented by pixel values (e.g. luminance and chrominance) to the spatial frequency domain. Typically after undergoing such a transformation the image data is now expressed as coefficients in the transform domain, e.g. the coefficients of a Discrete Cosine Transform, DCT. Next the coefficients in the transform domain are quantized into determined levels q(w),
104
. The quantized data is further encoded,
106
. At this stage the image data is in a compressed form. This compressed data may be used for storage, and hence the channel
110
could be the connection to the storage disk of the device to hold the image. The compressed data could be used for transmission, and then the channel
110
could be the channel used for mobile or wireless communications or for Internet transmission. In the expansion (receiving) part of the system the signal e(q) is received from the channel and is decoded in the decoder
120
, then inverse quantized
122
and inverse transformed
124
to achieve the resulting image data {overscore (Y)}.
The steps described above form the basic components of codecs used in image compression and decompression. The term codec is the name given to a system or arrangement for image coding which has the ability to both encode and decode image data. Codecs can be rated according to the functionalities they offer and the performance they provide. For example, in a mobile telecommunications environment, a codec is better if it provides:
the highest possible image quality for a given available data transfer rate;
progressivity in quality. This means that during encoding and decoding the quality of the image may be gradually enhanced by increasing the number of bits per pixel used in its representation;
progressivity in resolution. This means that the spatial resolution of the image may be progressively enhanced during encoding and decoding;
low complexity of implementation;
resilience to errors that may occur during transmission.
There are commonly used prior art methods for image compression. The most widely used is the standard released by the International Standards Organization (ISO), the JPEG (Joint Photographic Experts Group). The JPEG image compression standard contains 4 parts. The best known and most commonly used one is the first part, known as the JPEG baseline. In addition to its poor performance when applied at low bit rates this compression system does not offer the above functionalities. To overcome JPEG baseline's shortcomings several solutions have been proposed. A brief description of these methods is given below.
It is prior known to use a so-called Embedded Discrete Cosine Transform solution. In this method the image is transformed by a Discrete Cosine Transform applied to 8 by 8 pixels blocks. The quantization is performed in a successive manner that is embedded in the coding part. Coding is performed using a context based arithmetic coding which makes its complexity in memory and in computations higher. Furthermore, this method is block based and hence at low bit rates it leads to blocking artifacts which require the use of post processing filters. Therefore it is not a preferred solution for mobile communications. Further details about this method can be found in [1].
It is also prior known to use a so-called Wavelet Trellis Coded Quantization. This algorithm consists of four phases: A wavelet transform of the image data, a classification and bit allocation of the bands of the transformed data, the classification being obtained by computing statistics of the data. Based on the classifications, quantization of the transform coefficients is performed in trellis fashion. Trellis quantization is adopted from a technique known as trellis modulation which enables use of twice the number of quantization levels allowed at a certain bit rate with constraints on the transitions between the levels. Later the quantized coefficients are coded in bit planes by a context based arithmetic coder. This solution is very complicated for mobile applications and does not offer high performance at low bit rates. Details about this method can be found in [2].
A further prior art solution is called Multi-Threshold Wavelet Coding. In this method wavelet transformation is applied to the image data. The quantization is performed successively and independently for each band of the transformed data, hence the name multi-threshold. The encoding is then performed using a context based arithmetic coding which makes complexity higher and therefore its use for mobile communications not preferred. Details about this method can be found in [3].
A further prior art solution is called Quad-tree based Entropy Coding. In this method the image data is wavelet transformed, then the coefficients in the transform domain are divided in blocks of 2
n
×2
n
pixels. Each block is then coded by dividing it into four quadrants. Each quadrant is coded again by dividing it into 4 quadrants, and so on till no further division is possible, to form a tree of quadrants, hence the name quadtree. At the first level the number of bits needed to get the maximum coefficient of the block is sent, then for each quadrant the difference between the maximum coefficient of the block and the maximum coefficient of the quadrant is determined. The advantage of this method is that it requires fewer computations and the complexity of the entropy coding is low. However, the problem with this solution is that the algorithm does not provide progressivity in quality or in resolution which, as stated earlier, are important features for mobile applications. Details about this method can be found in [4].
A further prior art solution is the Compact Quadtree Based Subband Image coding scheme. This prior art method for compression of images is described in documehnt [5]. The method uses wavelet transforms, then the quantization is embedded in the encoding. For each quantization level, a quadtree-based method is used to encode the bands. The significance map (the region where coefficients are higher than the quantization level) in the bands is coded by a quad-tree method which uses three symbols for the representation of its nodes:
“X” corresponds to a quadtree block having at least one coefficient coded in the past quantization threshold,
“1” corresponds to a quadtree block where at least one significant coefficient is mixed with an insignificant coefficient in that block and
“0” corresponds to a quadtree block where the whole block is insignificant.
One of the symbols is implicitly obtained from the data, because the existence of a significant coefficient in a region implies considering the whole region significant for the coming bit planes. Therefore, this method implicitly assume
Chebil Fehmi
Lainema Jani
Willner Kai
Couso Jose L.
Nokia Mobile Phones Ltd.
Perman & Green LLP
LandOfFree
Method and system for processing 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 Method and system for processing image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for processing image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3258612