Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1999-03-15
2002-03-19
Mehta, Bhavesh (Department: 2621)
Image analysis
Image compression or coding
Quantization
C375S240220
Reexamination Certificate
active
06360020
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to the vector quantization and inverse vector quantization of a digitized image.
Vector quantization, and the inverse vector quantization connected therewith, is used for coding and compression of digitized images. It is based on the division of the image into two-dimensional image regions, and the determination of a code word that describes the respective image region to be quantized at best approximately, with respect to a predeterminable similarity criterion. Code words are vectors that have previously been stored as a set of standard vectors in what is called a code book. From the code book, vectors are imaged approximately onto vectors that describe the image information of the image region to be quantized. From this procedure, there also results the concept of vector quantization.
In the context of this document, an image region is to be understood as a set of image points of the digital image respectively to be quantized. The image regions can comprise an arbitrary shape and size.
In the following, a quantization vector is designated as a vector that is contained in a code book and that contains as vector components values of image information that are to be quantized. vector. In the following, the index is designated an entry of the code book. With the entry, the respective quantization vector is unambiguously identified. However, it is likewise possible to use the quantization vector itself as an entry of the code book.
Standardly, the entry of the code book is coded and is transmitted to a receiver.
For the reconstruction of the digitized image, after the decoding in a code book also present at the receiver, the received entry is imaged onto the quantization vector, and the quantization vector is used as an item of approximated image information for the reconstruction of the digitized image.
By means of this procedure, the required transmission rate for the transmission of the image information of the digitized image is reduced considerably, since only the index of the code book need respectively be transmitted, and not the entire image vector of the respective image block.
From the prior art document R. F. Chang and W. T. Chen, Image Coding using Variable-Side-Match Finite-State Vector Quantization, IEEE Transactions Image Processing, vol. 2, pp. 104-108, January 1993, it is known in addition to exploit correlations between image blocks, in order in this way to reduce further the required transmission rate. The method specified in the first cited prior art document T. Kim, New Finite State Vector Quantizers for Images, Proceedings of ICASSP, pp. 1180-1183, 1988 is designated as a finite state vector quantization (FSVQ). The respective state of the current input vector is defined by the respective image vector or, respectively, quantization vector immediately previously coded, i.e. quantized. The finite state vector quantization is a class of vector quantizations that use digital memories as described in R. F. Chang and W. T. Chen, Image Coding using Variable-Side-Match Finite-State Vector Quantization, IEEE Transactions Image Processing, vol. 2, pp. 104-108, January 1993.
In the following, an image vector is designated as a vector that respectively describes an image region, and which contains as vector components the image information to be quantized of the respective image region.
Under image information, for example luminance information, a brightness value allocated to the respective image point, chrominance information, a color value allocated to the respective image point, or also for example spectral coefficients, e.g. DCT transformation coefficients (
D
iscrete
C
osine
T
ransformation), are described.
It is known to group a digitized image to be coded into two-dimensional image regions with a rectangular shape T. Kim, New Finite State Vector Quantizers for Images, Proceedings of ICASSP, pp. 1180-1183, 1988. The image points of the image are thereby grouped into what are called image blocks.
Standardly, luminance values and/or chrominance values are allocated to the image points of the image block. The luminance values and/or the chrominance values of the respective image points respectively form, as a component of the image vector, the image vector to be quantized. In the known method, the image vector to be quantized is compared with the set of quantization vectors of the code book, which standardly have been stored previously and were for example stored in a read-only memory (ROM). The quantization vector of the code book is selected that is most similar to the image vector with respect to a predeterminable similarity measure. As a similarity measure, the sum of the quadratic difference of the individual components of the image vector and of the quantization vector is standardly used. If the “best” quantization vector has been determined, an index of the code book is standardly calculated for the identification of the quantization In the first cited prior art document T. Kim, New Finite State Vector Quantizers for Images, Proceedings of ICASSP, pp. 1180-1183, 1988, in addition two methods of finite state vector quantization (FSVQ) are described: what is called side-match vector quantization (SMVQ) and what is called overlap-match vector quantization (OMVQ).
Both methods have the aim of solving the problem of block artefacts that arise during the coding of image blocks.
In the SMVQ, it is presupposed that the distribution of the luminance information of the lines and columns of the image to be quantized can be described with a first-order Markov process, i.e. that the luminance values, allocated to the image points, of adjacent lines and columns are correlated with one another to a high degree. Under this presupposition, image points at the edge of the image blocks of an image block to be coded respectively contain a large part of the image information of previously coded adjacent image blocks. What is known as a state code book is formed, which contains code words that contain edge image points that comprise a high degree of similarity in comparison with edge image points already coded previously. The state code book is used for the selection of the most similar quantization vector of the code book for the respective image block. An advantage of the SMVQ or, respectively, of the FSVQ is that even for the case in which the image vector is not optimally described by the quantization vector, the error that arises is often not excessively visible to an observer of the reconstructed image, due to the correlation of adjacent image blocks.
In the OMVQ method, image blocks to be quantized are formed in that lines or, respectively, columns of adjacent image blocks partially overlap. For the determination of the quantization vector for the respective image block, the same procedure is used as in the FSVQ method or, respectively, in the SMVQ method. In the reconstruction of the image, the respective image block is again brought to its original size by respectively supplementing the overlapping lines or, respectively, columns between the image blocks with a line or, respectively, column of image points of which the average of the brightness values or, respectively, color values is assigned to the overlapping image points.
The known methods comprise some considerable disadvantages. For one, the methods are very complex, which leads to a considerable computing time requirement in the execution of the method by a computer.
In the context of this document, both an electrical data processing and also an arbitrary arrangement with a processor with which digital data can be processed are to be understood as computers.
In addition, the known methods presuppose a first-order Markov process, i.e. a high degree of correlation of adjacent image points of the digitized image. In the method, an additional indication of the state, i.e. an additional indication and taking into account of information of previously coded image blocks, is also required, which leads in turn to an increase in the required transmission rate.
Basic princi
Mehta Bhavesh
Schiff & Hardin & Waite
Siemens Aktiengesellschaft
LandOfFree
Method and arrangement for vector quantization and for... 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 arrangement for vector quantization and for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and arrangement for vector quantization and for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2880724