JP2555685B2 - Extended Tree Search Vector Quantization Method - Google Patents

Description

The present invention relates to an extended tree search vector quantization method that improves tree search vector quantization.

(Prior Art) Conventionally, as a high-efficiency coding method that eliminates information theoretical quantization loss due to scalar quantization of an input signal sequence,
Vector quantization is receiving attention. This vector quantization is to search for the vector with the minimum quantization distortion from the output vector group.To apply this to compression of high-speed real-time data such as image signals, introduction of a high-speed algorithm is necessary. is necessary. Vector quantization is division of a multidimensional signal space, and a representative point of the divided space becomes an output vector. Hereinafter, a conventional tree search vector quantization method will be described with reference to the drawings.

FIG. 2 is a diagram showing a binary tree of conventional tree search vector quantization. In the figure, in the first stage, it is divided into two, R ₀ and R ₁ . The representative points of the divisions R ₀ and R ₁ are Is. Next, in the second stage, the two partitions R ₀ and R ₁ are each divided into 2
Divide into four pieces, R ₀₀ , R ₀₁ and R ₁₀ , R ₁₁ . Each representative point Is. Similarly, the N divisions at the nth stage are represented by R _{b (n) 0} .
It consists of R _{b (n) 1} . Each representative point is Becomes Here, b (n) is a binary number representing the history up to the nth stage. That is, the vector to be encoded (hereinafter referred to as the input vector) Distortion with Seeking Then 0, Then proceed to 1. In this way, the process proceeds to the nth stage to obtain the final output vector, and the vector number of this output vector is transmitted.

(Problems to be solved by the invention) However, in the above-mentioned conventional method, since the vector closest to the input vector does not always exist in the lower stage of the vector selected in the node in the middle of the search, 2 ⁿ representative points The representative vector must be found by finding all the distortions between the vector and the input vector. Further, compared with the full-search type vector quantization, there is a problem that the image quality is deteriorated due to the detection loss due to the binary tree and the S / N ratio is lowered by about 1 to 2 dB.

The present invention is intended to solve these problems, and an object of the present invention is to provide an extended tree search vector quantizer capable of improving deterioration of image quality.

(Means for Solving Problems) In order to solve the above problems, the present invention searches for a representative vector having a minimum quantization distortion from an output vector group having a tree structure for an input vector. In the tree search vector quantization method described above, for an arbitrary vector existing in the n-th stage (n is a natural number of 2 or more) that is the final stage, the N-th (N (N
= N−2, n−3, ..., 2,1) The final stage in each case in which the direction opposite to the vector is selected in the Nth stage, assuming that the wrong selection is made in the Nth stage. In the first step of obtaining the distortion between all the vectors existing in the vector and the vector, and the smallest of the obtained distortions is the candidate vector, and the vector existing in the final stage with respect to the input vector and each of the candidates The second step of making the vector having the smallest distortion with respect to the input vector among the vector and the true representative vector.

(Operation) According to the present invention having the above steps, for any vector existing in the n-th stage (n is a natural number of 2 or more), which is the final stage, the vector from the top stage In the Nth stage (N = n−2, n−3, ..., 2,1) of the route leading to, the direction opposite to the vector is selected at the Nth stage. In the case of, the distortion between all the vectors existing in the final stage and the vector is calculated. The smallest one of the obtained distortions is stored as a candidate vector below the final stage vector. If a vector existing at the final stage of the input vector is selected using this extended binary tree, the vector that minimizes the distortion with respect to the input vector is selected from the vector and each candidate vector. Be a representative of

Therefore, the present invention can solve the above problems and provide an extended tree search vector quantization method that can improve the deterioration of image quality.

(Embodiment) An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a diagram showing a binary tree according to an embodiment of the present invention. In the figure, the input vector in the K-dimensional signal space Output vector for Is prepared. Input vector First in the first stage And calculate Then to node 1, If so, move to node 2. The same calculation is performed in the second stage, and the input vector is input in the final stage. Output vector for Conventional tree search vector quantization is used to obtain the above. In this embodiment, a candidate vector is prepared in the final stage. Referring to FIG. 1, the input vector In the binary tree of Fig. 1, If we get the output vector If the selection in node 1 is wrong, Should be chosen. For this reason The smaller one is the candidate vector And Similarly, a candidate when the selection at node 0 is incorrect It is selected in advance and stored under the node 7. Where the input vector When I get to And the distance d = [Σ (x _j −y _nj ) ² ] ^1/2 , Select one output vector with the smallest distance to.

For the sake of simplicity, the above description is for the second to third stages.
Although the explanation has been given with respect to the binary tree, in general, when the binary tree with n stages is used, the binary tree has ²ⁿ representative vectors each having n-1 candidate vectors. For example, if n = 10
When a vector quantizer composed of 1024 output vectors is considered, the vector to be obtained is obtained by performing distance calculation 1024 times in the full search type and 19 times in the method of this embodiment, and the conventional tree is used. Compared to the search vector quantization method,
The S / N ratio improves by about 1 dB.

(Effects of the Invention) As described above, according to the present invention, the candidate vector is arranged at the final stage of the binary tree, so that the number of distance calculation of the output vector from the input vector is reduced and
It is possible to provide an extended tree search vector quantization method that can improve the deterioration of image quality by improving the S / N ratio because the error in the middle stage of the progression tree can be covered.

[Brief description of drawings]

FIG. 1 is a diagram showing a binary tree according to an embodiment of the present invention.
The figure shows a binary evolution of conventional tree search vector quantization.

Front page continued (72) Inventor Kenji Koro 1-7-12 Toranomon, Minato-ku, Tokyo Oki Electric Industry Co., Ltd. (72) Inventor Hirohisa Yamaguchi 2-3-2 Nishi-Shinjuku, Shinjuku-ku, Tokyo Country Tokiga Telegraph and Telephone Corporation (56) References JP 62-145928 (JP, A) JP 61-262378 (JP, A)

Claims (1)

(57) [Claims] 1. A tree search vector quantization method for searching a representative vector having a minimum quantization distortion from an output vector group having a tree structure for an input vector, which is the final stage n (n) Is a natural number greater than or equal to 2), at the Nth (N = n−2, n−3, ..., 2,1) stage in the path from the top stage to the vector, Assuming that the wrong selection is made, the distortion between all the vectors existing in the final stage and the vector in each case where the direction opposite to the direction leading to the vector is selected in the N-th stage and the obtained distortion is obtained. The smallest one is set as the candidate vector, and the vector having the smallest distortion with respect to the input vector is selected as the true representative vector from among the vector existing in the final stage of the input vector and each of the candidate vectors. Expanded tree hunting characterized by Vector quantization method.