1. Field of the Invention
This invention relates to a method and apparatus for coding multivalued image data or color image data. More particularly, the invention relates to a coding method and apparatus for coding image information block by block, and subjecting the generated vector data to vector quantization to achieve coding.
2. Description of the Prior Art
Vector quantization has recently become the focus of attention as a method of achieving highly efficient image coding and entails regarding image information in a pixel block as a vector in terms of image block units, and obtaining an optimum reproduction vector for each and every pixel block. However, vector quantization involves certain problems, which will now be set forth.
The arrangement of a coder using conventional vector quantization is illustrated in FIG. 30A. Here the distances between an input vector and reproduction vectors that are contained in a code book stored in a memory 300 are computed by an arithmetic unit 301, the reproduction vector having the shortest distance is selected by a comparator 302 based on the results of the computation, and the code of this vector is delivered as an output.
However, with the arrangement (FIG. 30A) using the arithmetic unit, the higher the number of dimensions of the input vector, the larger the arithmetic circuit and comparator become. This leads to problems in terms of cost and speed.
Tree-search vector quantization is performed in the art in order to solve the problem. Tree-search vector quantization involves a search performed in stage-wise fashion in order to select a reproduction vector from a code book. This is done in the following manner, which serves as one example: First, the entire code book is divided into k groups, each of which usually is composed of vectors whose distances are close to one another. Each group has a representative vector, such as a center-of-gravity vector. Hence, k-number of these vectors are prepared and these are compared with the input vector to decide the group of vectors having the shortest distances relative to the input vector. The group decided is further divided into k groups and similar processing is executed to eventually retrieve the reproduction vector. Thus, with the tree-search vector quantization method, the amount of computation can be reduced since a comparison with the entire code book is not required in order to determine the optimum vector.
Though the amount of computation in the conventional tree-search vector quantization method is thus reduced in comparison with the complete look-up method, a drawback is that an optimum reproduction vector cannot always be obtained to retrieve, in stage-like fashion, a vector exhibiting little distortion. Furthermore, since there is no change in the dimensions of the input vector and the number of bits in each element, an enormous memory capacity is still required. As a result, this approach is not suited to a LUT arrangement.
Another arrangement shown in FIG. 30B is composed of a look-up table (hereinafter referred to as a "LUT"), in which vectors at the shortest distances with respect to input vectors are found in advance and stored in a memory 304. Then, when an input vector is given, the code of the reproduction vector is obtained from the LUT.
Such methods for processing color image are proposed in U.S. patent application Ser. No. 066,119 (filed Jun. 25, 1987), abandoned, U.S. Ser. No. 185,024 (filed Apr. 22, 1988), now U.S. Pat. No. 4,974,071, U.S. Ser. No. 261,276 (filed Oct. 24, 1988), abandoned, U.S. Ser. No. 312,755 (filed Feb. 21, 1989), now U.S. Pat. No. 5,162,923, U.S. Ser. No. 362,014 (filed Jun. 6, 1989), now U.S. Pat. No. 5,089,884, which were assigned to the assignee of the present invention. That is, by dividing color image data into a plurality of blocks in conformity with luminosity and chromaticity to achieve quantization, fairly good coding efficiency is obtained utilizing human visual characteristics with respect to luminosity and chromaticity.
FIG. 17 is a block diagram for describing one example of coding method of color image information proposed by the assignee of this invention. As shown in FIG. 17, a color converter 1 divides input image information R, G, B into respective blocks (each composed of 4.times.4 pixels, by way of example), and each block is converted into luminosity information L* and chromaticity information a*, b* in a uniform color space. Since the brightness information L* is visually sensitive, it is coded faithfully. In other words, the brightness information L* is subjected to an orthogonal transformation by an orthogonal transform unit 2, and the obtained vector having a 16-dimension structure is coded by a vector quantizer 3.
Meanwhile, the items of chromaticity information a*, b* can be further compressed since they are not visually sensitive. That is, the items of chromaticity information a*, b* are further divided into sub-blocks (each consisting of 2.times.2 pixels), the mean values in each sub-block are obtained, and the 8-dimension chromaticity vectors obtained are coded by a vector quantizer 6.
However, with the system employing the LUT (FIG. 30B), the problems related to cost and speed are solved but the following problems arise when the input vector takes on higher dimensions:
(i) In a case where the LUT of a multidimensional vector quantizer is of the complete look-up type, an exorbitant amount of processing time and hardware are required and therefore problems arise in terms of coding efficiency and cost. PA1 (ii) Memory capacity is limited by the size of the elements, and constitution using a ROM or the like is difficult. PA1 (iii) Correlation between vector elements cannot be utilized merely by setting a scalar quantizer in front of the LUT. The result is a decline in efficiency and image quality.
Thus, even with the LUT configuration said to be speedier than the arrangement using the arithmetic unit, problems remain in that there is a decline in processing speed, coding efficiency and image quality depending upon the input signal.
Vector quantization thus requires an operation through which vectors exhibiting minimum quantization distortion may be searched from among a group of predetermined reproduction vectors (i.e., a code book). Consequently, since the amount of computation grows exponentially the higher the dimensions of the vector and the larger the number of reproduction vectors, it is difficult to achieve high speed. In particular, when a vector quantization circuit is composed of hardware and it is attempted to realize complete look-up-type vector quantization using such a circuit, the memory capacity of the LUT must be enormous and therefore such an arrangement is unrealistic. For example, consider a LUT for quantizing one block composed of 4.times.4 pixels, in which each pixel is constituted by eight bits. In such case, the address space of the LUT would be 8 (bits).times.4.times.4=128 (bits). This is not feasible.
On the other hand, when the above-described vector quantization is carried out, the general image (the training image) is sampled and use is made of a code book created by the LBG (Linde, Buzo, Gray) method or the like.
However, when the coding of the chromaticity information is performed solely by vector quantization, the reproduced chromaticity structure tends to become flat and color becomes indistinct especially at the edge portions of characters if use is made of a code book created employing the ordinary training image, which exhibits few color edges. If chromaticity structure information is furnished in order to solve this problem, code length increases.
With regard to the problem, it has also been contemplated to shorten code length by utilizing the interim results of tree search in conventional tree-search quantization. However, besides the fact that an optimum vector cannot always be obtained, code length cannot be increased to improve picture quality.
In addition, in order to select a vector from among a group of predetermined reproduction vectors by training, the length of the word to undergo coding is fixed. Consequently, when it is attempted to change the ratio of compression, since training must be performed anew and the hardware must also be changed, it is difficult to change the ratio of compression.
USPTO Backgrounds
USPTO Backgrounds