JPH044600B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a pattern matching device used in a pattern recognition system such as speech recognition.

In pattern recognition systems such as voice recognition that are currently being put into practical use, a pattern matching method is used to recognize input patterns by comparing the input patterns with various standard patterns stored in advance. ing. For example, in speech recognition, standard patterns for words to be recognized are stored and used as standard patterns.

In such speech recognition, a problem when using the pattern matching method is that the input speech is arbitrarily expanded or contracted with respect to the time axis each time it is uttered. In other words, even if the same speaker utters the same word, the words cannot be uttered at exactly the same length. Therefore, when matching with a standard pattern, even if the stored standard pattern is that of the speaker who uttered the input voice, since the rate of speech changes arbitrarily, the degree of similarity changes with each utterance, resulting in incorrect recognition. I can't get any results. As a method for matching while matching the time axis deviation between this input pattern and the standard pattern, dynamic programming ( Dynamic Programming ) is used.
rogramming is abbreviated as DP hereafter. ) is widely used.
(See Publication No. 30242). Next, an overview of DP will be explained.

The speech pattern is defined by the feature vector A _i = (a _1i , a _2i ,
a _ni , ... a _oi ) is expressed as A = A ₁ , A ₂ , A ₃ , ..., A _i , ..., A _I ... (1). This feature vector A _i is the audio feature vector of the i-th frame when the audio signal is divided into I sections in the time domain (one section divided at this time is called a frame), and is used as a feature vector. For example, the outputs of a group of n bandpass filters having different center frequencies can be considered. a _ni
is the output of the mth filter among the n bandpass filters of the ith frame of audio. _The input _speech pattern X and _{the standard} speech pattern Y are expressed as _{a time} series _of feature vectors _: , Y _j , …, Y _J …(2).

Here _, in order to find the _similarity between the input pattern ² = _o 〓 (x _iu −y _ju ) ² ...(3). Assuming that there is no expansion _or contraction of the time axes _of the input pattern _n ) ² }/m={ _n 〓 d(m, m)}/m...(4) Here, m indicates a frame number specifying one of n frames for each of the input pattern and the standard pattern. The smaller S is, the higher the degree of similarity is, that is, the patterns (words) are very similar.

As mentioned above, since the voice expands and contracts each time it is uttered, it is not possible to accurately determine the similarity S using equation (4). Therefore, in DP, S is found while aligning the time axes as follows. Figure 1 shows input pattern X and standard pattern Y on the time axis.
Figure 2 shows the process of matching input patterns X,
The standard pattern Y is shown converted into vertical and horizontal coordinates. The arrows indicate the alignment process, showing how the expansion and contraction of the time axis is aligned. When calculating the similarity S while calculating the distance along the route indicated by the arrow, S = {d (1, 1) + d (2, 2) + d (2,
3) +...+d(8,7)}/9...(5) is obtained.

There are various types of pattern matching using DP, but for recognition when the expansion and contraction of the time axis is limited to a certain extent, such as words, DP (hereinafter referred to as DP) is used to Such a DP) is used. The bus selection for this DP is performed as follows.

In other words, the process leading to point E in Figure 3 is as follows:
Three directions of points F, G, and H are allowed;
The cumulative sum of the distance d up to H is D(i, j-1),
Assuming D(i-1, j-1) and D(i-1, j),
The cumulative sum D(i, j) of point E is expressed as equation (6) depending on which of the three directions it comes from. Cumulative sum D(i, j)
Among equations (6), the one whose value is the minimum is selected.

D (i, j-1) + d (i, j) D (i-1, j-1) + W・d (i, j) D (i-1, j) + d (i, j) ...(6 ) However, W indicates the weight of bus selection in the diagonal direction,
Usually it is 2. Also, the elapsed length L until reaching point E
As (i, j), the elapsed length corresponding to the elapsed time selected by equation (6) is selected according to equation (7). Points F, G,
Let the elapsed length up to H be L(i, j-1), L(i-1,
j-1), L(i-1, j), L(i, j-1)+1 L(i-1, j-1)+W L(i-1, j)+1...(7) The initial values D(1, 1) and L(1, 1) are expressed as follows.

D(1,1)=d(1,1) L (1, 1) = 1 ...(8) Furthermore, equation (6) is calculated using the following constraint.

1iI, 1jJ j−γij+γ γ=integer ...(9) γ determines the range of matching by absorbing changes in the time axis of input pattern X and standard pattern Y, that is, the matching width, and as γ increases, , matching can be achieved between the input pattern and the standard pattern, which have large expansion and contraction. However, if γ is too large, the throughput will increase and the matching will be too high. In the case of FIG. 2, l=2γ+1 and γ=±1, indicating that matching can be achieved with l=3. Second
In the figure, the final similarity S is the cumulative sum D(8,
7) and the elapsed length L(8,7), it is obtained as S=D(8,7)/L(8,7)...(10), which corresponds to equation (5).

In this way, in this DP, since it is only necessary to perform matching within the range within the dotted line as shown in FIG. 2, the distance calculation only needs to be performed within the dotted line. Therefore, the amount of processing is small and a large number of standard patterns can be matched.

The problem with this DP is the extraction of input audio. In this DP, the starting end is fixed as shown in equation (8), and the matching width is limited to γ as shown in equation (9). Therefore, if the starting end is cut out incorrectly, the starting point will shift, and it is conceivable that matching will not be possible with the matching width γ. Also, if you make a mistake in cutting out the end, the length of the input voice may exceed the (±γ) allowed by this DP, and the word may be judged as a different word. When performing DP processing in real time, this input audio extraction also needs to be performed in real time. However, various problems arise when extracting input audio in real time.

Next, we will discuss specific problems in real-time DP processing and extraction processing. For example, the power of the input voice is used to extract the input voice, that is, to detect the start and end points. This method takes advantage of the fact that when no voice is being uttered, the power is low (silence), and when the voice is uttered, the power increases.

Now, when determining the end, if there is a consonant sound such as in a stamp (kitsute), the tsu will become a silent section and there is a risk that it will be mistaken for the end (Figure 4A
(near the point). In addition, for words whose endings tend to be devoiced, such as Hamamatsu (HAMAMATSU), it may not be clear whether or not there is a voice signal at the end.
(Between points B and C in Figure). Even if you find a point that seems to be the end of both, you have to look at the situation several hundred milliseconds after that point.
It cannot be determined that that point is the end. In other words, when there is an input voice as shown in FIG. 4, there is a risk that points A and B may be mistaken for the end points, even though the actual end point is point C. Also, in order to determine point C as the terminal point, D
It is necessary to see the state of the input audio up to the point. If point A or point B is mistakenly determined to be the end and the input voice is cut off in the middle, it will be determined that the voice is shorter than the actual input voice. To avoid this, several hundred msec
When determining the end after confirming the silent section of , the end is determined for the first time at point D.
However, when DP processing is performed in real time, the input audio up to point D has already been processed by the DP processing section. In other words, the input voice is processed as having a length up to point D, and is determined to be longer than the actual input voice. In the above-mentioned DP processing, the fluctuation width of the time axis is limited to ±γ (standard pattern time length) in order to reduce the amount of processing, so the end may be mistakenly determined to be point A, B, or D. , the input exceeds this fluctuation range and is rejected.

Therefore, in conventional methods, the input audio is first extracted and stored in memory, and after the extraction is completed, the input audio of the audio section is read out from the memory and matched. .

In order to clarify the problems of this conventional method, first an outline of a conventional example of a recognition processing device for speech, etc. will be explained using FIG. Features of the input voice are extracted by a feature extraction unit 1. The distance calculation unit 2 calculates the distance between the input voice from which features have been extracted and a plurality of standard patterns (words) stored in the standard pattern memory 3 in advance.

The DP processing unit 4 performs matching while aligning the distances from the distance calculation unit 2 on the time axis. The determination unit 5 outputs, as a solution, the standard pattern with the maximum degree of similarity from the degree of similarity with each standard pattern output from the DP processing unit 4. For the above-mentioned reason, the conventional device has a memory 10 for storing one word worth of input speech after the feature extraction section 1, and stores the input speech from the start to the end detected by the speech extraction section 6. Correctly extracted input speech is stored in the memory 10. After the termination is detected, matching processing after distance calculation is performed on the input audio stored in the memory 10.

Conventional equipment cannot perform real-time processing, but the fifth
Real-time processing becomes possible by configuring the memory 10 in the figure so that writing from the feature extraction section 1 and reading from the distance calculation section 2 can be performed simultaneously. In this case, the capacity of the memory 10 is
It is sufficient to be able to store information for several hundred milliseconds from point C to point D in the figure, and the memory capacity can be reduced compared to conventional devices. The apparatus shown in FIG. 5 will be explained below.

The memory 10 inputs the data output from the feature parameter extraction section 1 to the distance calculation section 2 after several hundred milliseconds. Therefore, when the input audio at point D is input to the feature extraction unit 1 and the end is detected by the audio extraction unit 6, the data at point C, which is the actual end, is still stored in the memory 10. It is not input to the distance calculation section 2. The audio cutting unit 6 is
After sending the input audio from the memory 10 to the distance calculation unit 2 up to point C, the end detection signal EE is sent to the DP processing unit 4 at point D, the DP calculation is completed, and the
The DP calculation result is transferred to the judgment unit 5, and the DP calculation result is transferred to the judgment unit 5.
By finding the standard pattern with the maximum similarity based on the calculation results and outputting it as a solution, a device capable of almost real-time processing was realized. However, in the conventional device, the memory 10 becomes a circuit in which reading and writing compete, and the time from point C, which is the actual end, to point D, at which point C can be determined as the actual end, is not constant. Both the control circuit and the control of the audio cutting section 6 become complicated.

SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to solve the above-mentioned problems and provide a pattern matching device used in speech recognition, etc., which can perform real-time processing on input speech. In order to achieve this objective, the present invention performs real-time processing to detect the DP when a termination candidate is detected.
The feature is that the calculation results are sequentially stored in the memory, and when the above termination candidate is detected to be the true termination, the DP calculation result corresponding to the true termination is read out from the memory, and this is used as the true DP calculation result. There is.

The present invention will be described below with reference to Examples.

FIG. 7 shows a block diagram of the speech recognition apparatus according to the present invention, and FIG. 6 shows the matching relationship between the input pattern (horizontal axis) of FIG. 4 and a certain standard pattern (vertical axis).

Points A, B, C, and D in FIG. 6 correspond to time points A, B, C, and D of the input audio in FIG.

In the device shown in FIG. 7, a new memory 7 is added between the DP processing section 4 and the determination section 5 of the conventional device shown in FIG.
will be established. This memory 7 has a capacity equal to the number of words stored in the standard pattern memory 3, that is, the number of recognized words. Furthermore, in addition to the start end detection section 60, the audio extraction section 6 of this device includes an end candidate detection section 61 that detects a point that seems to be the end (end candidate) and transmits this information to the DP processing section 4, and a end point detection section 61 that detects the end, There is an end detection section 62 that conveys this information to the DP processing section 4 and the determination section 5. The start edge detection section 60 generates a start edge signal SS at the start edge of the input pattern, and the termination candidate detection section 61 generates termination candidate signals at points A, B, and C in FIG.
SE is generated, and the termination detector 8 outputs the termination signal EE at point D.
occurs. When the DP processing unit 4 receives the termination candidate signal SE, it writes into the memory 7 the degree of similarity between each standard pattern and the input pattern at that time. Also the termination signal
Processing ends when EE is received. Upon receiving the termination signal EE, the determining section 5 reads out the value in the memory 7 and performs the same determining process as in the case of FIG. 5.

Next, the operation of this device will be explained using FIG. 6. In this device, the feature extraction unit 1
When the start end is first detected based on the feature quantities such as the autocorrelation coefficient and power extracted in step 1, the processing from the distance calculation section 2 onwards is started. As the processing progresses and the voice corresponding to point A is input to the feature extraction unit 1, there is almost no power at point A and there is a possibility that it is the end, so the end candidate detection unit 61 detects this point A as a end candidate and sends it to the DP processing unit. The termination candidate signal SE is sent to 4. Based on this signal SE, the DP processing unit 4 controls whether or not to save the DP matching results up to the point where the termination candidate detection unit 61 detected the termination candidate, that is, the point A, to the memory 7. In the case of Fig. 6, the length of the standard pattern and the length of the input audio up to point A are very different and cannot be settled within the matching width l, so the data saved in memory 7 is not the matching result itself but the rigid one. ect data or data with the lowest degree of similarity. The termination detection unit 62 detects that no voice is input again within several hundred milliseconds after the termination candidate detection unit 61 detects the termination candidate.
In other words, in the circuit that checks the termination when there is no power, between point A and point B, the voice is input again at point B within several hundred milliseconds, so the termination signal EE is not output.

Similarly, at points B and C, the terminal candidate detection unit 61
is determined to be a termination candidate for the above-mentioned reason, and therefore, at points B and C, the termination candidate detection section 61 sends the termination candidate signal SE to the DP processing section 4. Here memory 7
is rewritten with a new matching result every time the matching result is sent from the DP processing unit 4. For example, at point A, the matching result between the input pattern at point A and each standard pattern that has already been written in the memory 7 is the same as the matching result between the input pattern at point B and each standard pattern at point B. Can be rewritten. Similarly, the matching result at point B is rewritten to the matching result at point C at point C. Here, the matching result of point C with respect to the standard pattern in Figure 6 shows that the variation in length of the standard pattern and speech (word) is within the range of -γ to +γ, so the DP processing up to the white circle point takes a certain value as the result. Termination detection section 6
2, no termination signal is output between points B and C because the voice is input again after the termination candidate at point B is detected. However, since no voice is input for several hundred milliseconds between points C and D, it can be determined that voice production has already ended. Therefore, the termination detection section sends the termination signal EE to the DP processing section 4 and the determination section 5 at point D. As a result, the DP processing unit 4 stops processing, and the determination unit 5
The degree of similarity with each standard pattern is read from the memory 7, the standard pattern with the maximum degree of similarity is detected,
Output it as a solution. Here, memory 7 has C
Since there is no re-input of audio after this point, no termination candidates appear. Therefore, the memory 7 stores the matching results up to point C, which is the actual end. In this way, according to the present invention, extraction processing and matching processing using DP can be realized in real time.

Next, let us compare the amount of hardware between the conventional circuit shown in FIG. 5 and the circuit shown in FIG. 7 which is an embodiment of the present invention. As shown in FIG. 7, the capability of the input audio extraction section 6 is exactly the same as that of the conventional one, except that when a point that seems to be the end (terminus candidate) is found during the process of determining the end, this information is output in the form of a flag. Since it only adds functionality, it can be said that there is almost no increase in the amount of hardware compared to conventional circuits. Next, writing from the DP processing unit 4 to the memory 7,
Although there is a read process from the determination unit 5, there are no simultaneous accesses, that is, no competition occurs, so control is simpler and the amount of hardware is smaller than in conventional real-time circuits. The capacity of the memory 7 is required for the number of words in the standard pattern, and as the number of unrecognized words increases, the memory capacity also increases. However, for a practical recognition device of several hundred words or less, the memory capacity required is smaller than that of the memory 10 used in the conventional device of FIG.

As described above, according to the present invention, it is possible to realize a device which requires less hardware than conventional devices and which performs input pattern cutting and post-cutting processing in real time, which has great effects.

[Brief explanation of drawings]

Figures 1 to 3 are diagrams explaining the principle of pattern matching using DP, Figure 4 is a diagram showing changes in the power of an input audio pattern, and Figure 5 is a diagram showing the block configuration of a conventional pattern matching device. 6 is a diagram showing the matching relationship between the input pattern of FIG. 4 and the standard pattern, and FIG. 7 is a diagram showing the block configuration of one embodiment of the pattern matching device based on the present invention. 6...Audio cutting section.

Claims (1)

[Claims] 1. In a pattern matching device that matches an input pattern and a plurality of standard patterns while extracting an effective signal section in real time, the device includes means for detecting a starting end of the effective signal section and detecting an end candidate of the effective signal section. means for detecting the end of the effective signal section; and means for starting a matching process for determining the degree of similarity between the input pattern and each standard pattern based on the detection of the start end, and detecting the end of the valid signal section based on the detection of the end candidate. a matching processing means for outputting the degree of similarity between the input pattern and each standard pattern at the time of candidate detection; a storage means for retaining the output of the matching processing means at the time of detecting the termination candidate; A pattern mater characterized by comprising: a determining means for reading the output from the matching processing means from the storage means when detecting a termination candidate corresponding to a termination, determining and outputting a standard pattern having the maximum degree of similarity. Ching device.