JPH04248722A - Data coding method - Google Patents

Abstract

PURPOSE:To execute coding of an input data in the data at high speed coding method adopting vector quantization. CONSTITUTION:A code vector included in a code book is divided into M-kinds of categories 302, 303 and a code vector belonging to each of the M kinds of categories is further divided into M(2) kinds of categories. Similarly, the code vector is divided up to the N-th stage. A characteristic vector of each category is used as a centroid vector of the code vector belonging to the category. In the case of coding, according to the tree-structure, retrieval is implemented based on the distance calculation between the input vector and the characteristic vector of each category and the result is coded to an optimum code vector.

Description

[Detailed description of the invention]

0001

[Industrial Application Field] The present invention uses data compression.
It relates to fields such as voice recognition devices, image recognition devices, and digital communications.

0002

[Prior Art] Conventionally, "An Algorithm f
or Vector Quantizer Design
n” (IEEE TRASACTIONS ONCOJ
MMUNICATIONS, VOL. COM-28,
No. 1, JANUARY 1980. by LIN
Data compression of digital signals by vector quantization was known, as described in DE, BUZO and GRAY).

0003

[Problems to be Solved by the Invention] However, in conventional vector quantization, when encoding input data into any of the T code vectors in the codebook, it is difficult to associate the input data with each code vector in the codebook. Since distance calculations are performed T times, encoding takes time, making it difficult to perform recognition processing and data communication in real time. It is an object of the present invention to solve this problem and speed up the calculation time of data compression processing.

0004

[Means for Solving the Problems] The data encoding method of the present invention includes:
Each of the T code vectors is classified as M
(1) dividing into each category of types, and as a second stage classification, dividing each of the M(1) types of categories in the first stage classification into each of M(2) types of categories, respectively; By dividing into M(1)*M(2) types of categories, and in the same way as the classification at each stage described above, as the Nth stage classification, the N-1th stage classification M(1)* M(
2) *...*Divide each category of M(N-1) types into each category of M(N) types,
dividing into *M(2)*...*M(N) categories, setting the value of the number of stages N to 3 or more, and dividing each feature vector of each category into , and when input data is encoded into any of the code vectors in the codebook, as a first search, the input data and M of the first stage are (1) The distance from the feature vector of the type category is the minimum, 1
selecting one of said first stage categories; and
As a search, one second search is performed, in which the distance between the input data and the feature vectors of the M(2) types of categories belonging to the selected first stage category is minimized.
By selecting the category of the stage, and in the same way as each search above, as the Nth search, the input data and the M(N
) selecting one of the N-th stage categories that has a minimum distance from the feature vector of the category of type; Selecting one code vector having a minimum distance to the code vector, and associating the input data with the code of the selected one code vector, and n-th search (n≦
When there is only one code vector belonging to the category of the n-th stage selected in N), the n-th search is regarded as the final search, and the input data is associated with the code of the code vector. shall be.

[0005]

[Example] (Example 1) The data encoding method of the present invention is
An embodiment in which the present invention is applied to a speech recognition device for word recognition will be described with reference to the drawings.

FIG. 1 is a system configuration diagram of a speech recognition device using the data encoding method of the present invention. The voice uttered by the speaker is input through the microphone 1, and the A/D converter 2 converts it into a 16 [KHz], 12-bit digital signal, and the feature extractor 3 converts 20 [ms] into one frame. As such, Hamming window processing and linear prediction analysis are performed for each frame, and 14th-order LPC cepstral coefficients are determined as feature parameters. At this time, the frame shift amount is 10 [ms]. Using the 14th-order feature parameter thus obtained as an input vector, the data compression unit 4 encodes it into one of the code vectors in the codebook 5 using the data encoding method of the present invention. The word recognition unit 5 performs pattern matching on the time series of codes encoded in the data compression unit 4 and standard patterns of X words that have been trained in advance, using the HMM method to recognize words. . At this time, standard patterns of X words are registered in the word dictionary 7.

In this embodiment, the total number of code vectors in the codebook 5 is 256, which are classified into six levels. In addition, the 256 code vectors in this codebook 5 are obtained by sampling the voices uttered by 20 speakers at 16 [KHz] and 12 bits.
Hamming window processing and linear prediction analysis are performed for each frame, with 0 [ms] as one frame and the shift amount as 10 [ms], and a feature parameter group of hundreds of thousands of frames with 14th LPC cepstral coefficients as feature parameters. , using the LBG algorithm, and the order of each code vector is 14th. This LBG
An algorithm is “AnAlgorithm for
Vector Quantizer Design” (
IEEE TRASACTIONS ON COMMU
NICATIONS, VOL. COM-28, NO. 1
, JANUARY 1980. by LINDE,
This is an algorithm described in BUZO and GRAY).

The six-stage classification of code vectors in codebook 5 will be briefly explained using FIG. Figure 3
In this example, category (0, 1) 301 is a category that includes all 256 code vectors, that is, the codebook itself. This category (0, 1) 301
The 256 code vectors were classified into two categories, category (1, 1), and 30
2, category (1, 2) 302. The feature vectors of categories 302 and 303 are the centroid vectors of code vectors belonging to each category. As the second stage classification, code vectors belonging to the two categories 302 and 303 divided in the first stage classification are
Each category is divided into two categories. Category 3
The categories obtained by dividing the code vector belonging to 02 are:
Categories 304 and 305 are categories, and categories 306 and 307 are obtained by dividing the codebook belonging to category 303. Thus, in the second stage classification, code vectors are divided into four categories. The feature vector of each category is the centroid vector of the code vector belonging to each category, as in the first stage classification. Similarly, in the third stage classification, the code vector is divided into eight categories from category (3, 1) 308 to category (3, 8) 309. In this embodiment, classification is performed in the same way up to six levels. In the sixth stage of classification, the code vector is
Category (6, 1) 310 to Category (6, 64
) is divided into 64 categories up to 311. The four code vectors belonging to category 310 are code vectors 312, 313, 314, and 315, and the feature vector of category 310 is code vector 31.
2, 313, 314, and 315.

The algorithm for this classification will be explained using FIG.

First, symbols will be defined. N is the total number of classification stages, and is set to 6 in this embodiment. Let n be the classification stage name. I is the number of categories in the n-1th stage classification, i
is the category name. Cn(i) is the centroid vector of the newly created category i in the n-th stage classification, that is, the feature vector of the i-category in the n-th stage.

In operation 21, n and I are each initialized to 1. This indicates that the first classification is the first stage classification and that the first number of categories (the number of categories in the 0th stage classification) is one type (the codebook itself).

In loop 22, operations 23 to 27 are calculated I times in order to perform calculations for dividing each code vector belonging to I types of categories into two.

In operation 23, as an initialization for dividing the code vector belonging to the i category in the n-1th stage into two, the two most distant code vectors belonging to the i category in the n-1th stage are The code vector of
Select as the initial values of the two centroid vectors.

In operation 24, the distance between each code vector belonging to the i category of the n-1th stage and the two centroid vectors is calculated, and each code vector is divided into two types so that the distance becomes small. Split into categories.

In operation 25, for each of the two categories classified in operation 24, the centroid vector of the code vector belonging to each category is determined.

In branch 26, for each of the two categories classified in operation 24, it is determined whether the sum of the distances between the centroid vector obtained in operation 25 and the code vector belonging to that category satisfies the convergence condition. It is determined whether to proceed to operation 27 or to recalculate operations 24 and 25. The convergence condition in this embodiment is that when the sum of these distances converges to a certain constant value, convergence is determined, and when convergence occurs, operation 27 is executed.

In operation 27, the two centroid vectors calculated in operation 25 are stored as feature vectors for the (2*i-1) and (2*i) categories of the n-th classification. .

In operation 28, the value of the stage name n is increased by one, and the number of categories of the (n-1)th stage is substituted for I.

At branch 29, if n is less than or equal to N, operation 28 is executed from loop 22, and if n exceeds N, the classification calculation is terminated. In this embodiment, the value of N is 6, so calculations are performed up to the sixth stage of classification, and feature vectors for each category are determined.

A method of encoding an input vector of one frame of input data using the feature vectors of each category obtained through the above calculation will be explained with reference to FIG.

As a first search, one category with a smaller distance between the input vector and the feature vectors C1(1) and C1(2) of the two categories 302 and 303 of the first stage is selected.

As a second search, one category is selected that has a smaller distance between the input vector and the feature vectors of two categories belonging to the selected first-stage category. Suppose that in the first search, category 303
is selected, in the second search, category 306
, 307, the one category with the smaller distance from the feature vectors C2(3) and C2(4) is selected.

Similarly, the search is performed up to the sixth search, and one category of the classification at the sixth stage is selected.

As a final search, one code vector with the minimum distance between the input vector and the code vector belonging to the selected sixth stage category is selected, and the input vector is converted into the code of the selected code vector. By making the correspondence, encoding of the input vector is completed.

[0025] The average number of codebooks belonging to each category in the sixth stage is four. Therefore, in this example, the number of distance calculations when encoding an input vector is
The distance calculation between the feature vector of each stage category is 2*
6 = 12 times, the distance calculation with the code vector belonging to the category of the 6th stage is performed 4 times on average, and the total average is 18 times. When encoding is performed using the conventional method, distance calculations are performed for all 256 code vectors, so the number of distance calculations is 256. Therefore, using the data encoding method of the present invention, in this embodiment, it is possible to encode data approximately 14 times faster than the conventional method.

[0026] Also, if the code vector belonging to the n-th category selected in the n-th search (n≦N) is 1
If there are only 1, the n-th search is the final search, and the input vector is associated with the code of that code vector.

[0027]

As explained above, by using the data encoding method of the present invention, there is an effect that input data can be encoded at high speed. Suppose the code size is 2.
56, the classification of the data encoding method of the present invention is 6 stages, and the number of categories in the nth stage classification is 2n, the conventional method requires 256 distance calculations during encoding, whereas the conventional method requires 256 distance calculations. , the data encoding method of the present invention has an average of 1
Since it is only necessary to calculate the distance 0 times, the speed is approximately 25 times faster.

[0028] Furthermore, since the coding speed is increased in this way, it is possible to increase the code size and reduce the quantization error that occurs in the coding.

[Brief explanation of the drawing]

FIG. 1 is a system configuration diagram when the data encoding method of the present invention is applied to a speech recognition device.

FIG. 2 is a diagram showing an algorithm for dividing code vectors in the data encoding method of the present invention.

FIG. 3 is a diagram showing classification of code vectors in the data encoding method of the present invention.

[Explanation of symbols]

1. Microphone 2 A/D conversion section 3 Feature extraction section 4 Data compression section 5 Codebook 6 Word recognition section 7. Word dictionary 21 Arithmetic 22 Loop 23 Arithmetic 24 Arithmetic 25 Arithmetic 26 Branch 27 Arithmetic 28 Arithmetic 29 Branch 301 Category 302 Category 303 Category 304 Category 305 Category 306 Category 307 Category 308 Category 309 Category 310 Category 311 Category 312 Code vector 313 Code vector 314 Code vector 315 code vector

Claims (2)

[Claims] Claim 1. A data encoding method comprising: dividing each of T code vectors in a codebook into M(1) types of categories as a first stage classification; and a second stage classification. , M(1
) type categories are respectively divided into M(2) types of categories, and divided into M(1) * M(2) types of categories, and in the same manner as the classification of each stage described above, As the Nth stage classification, M(
1) *M(2)*...*M(N-1) categories are divided into M(N) categories, and M(1)*M(2)*... *Divide into M(N) categories, set the value of the number of stages N to 3 or more, and set each feature vector of each category to the center of gravity of each code vector included in each category. When input data is encoded into one of the code vectors in the codebook, as a first search, the input data and the first stage M
(1) Selecting one of the first-stage categories that has a minimum distance from the feature vector of the category of the type, and as a second search, using the input data and the selected first-stage category. As the Nth search, in the same way as each of the searches described above, select one of the second-stage categories that has a minimum distance from the feature vectors of the M(2) types of categories belonging to the above. selecting one of the N-th stage categories in which the distance between the input data and the feature vectors of the M(N) types of categories belonging to the selected N-1-th stage category is minimum; As a final search, one code vector with the minimum distance between the input data and the code vector belonging to the selected N-th stage category is selected, and the input data is When there is only one code vector belonging to the n-th category selected in the n-th search (n≦N), the n-th search is the final search and the A data encoding method, comprising associating the input data with the code of the code vector. 2. The data encoding method according to claim 1, wherein the code vector in the codebook is a code vector obtained by vector quantizing learning data using an LBG algorithm. Method.