Pattern recognition system

A pattern recognition method of dynamic time warping of two sequences of feature sets onto each other is provided. The method includes the steps of creating a rectangular graph having the two sequences on its two axes, defining a swath of width r, where r is an odd number, centered about a diagonal line connecting the beginning point at the bottom left of the rectangle to the endpoint at the top right of the rectangle and also defining r-1 lines within the swath. The lines defining the swath are parallel to the diagonal line. Each array element k of an r-sized array is associated with a separate array of the r lines within the swath and for each row of the rectangle, the dynamic time warping method recursively generates new path values for each array element k as a function of the previous value of the array element k and of at least one of the current values of the two neighboring array elements k-1 and k+1 of the array element k. The latter step of recursively generating new path values is repeat for all of the rows of the rectangle and the value of the middle array element is selected as the output value sought.

FIELD OF THE INVENTION 
The present invention relates generally relates to pattern recognition 
systems, and in particular, to pattern recognition systems using a 
weighted cepstral distance measure. 
BACKGROUND OF THE INVENTION 
Pattern recognition systems are used, for example, for the recognition of 
characters and speech patterns. 
Pattern recognition systems are known which are based on matching the 
pattern being tested against a reference database of pattern templates. 
The spectral distance between the test pattern and the database of 
reference patterns is measured and the reference pattern having the 
closest spectral distance to the test pattern is chosen as the recognized 
pattern. 
An example of the prior art pattern recognition system using a distance 
measure calculation is shown in FIGS. 1, 2 and 3, to which reference is 
now made. FIG. 1 is a flow chart illustrating the prior art pattern 
recognition system for speech patterns using a conventional linear 
predictor coefficient (LPC) determiner and a distance calculator via 
dynamic time warping (DTW). FIG. 2 illustrates the relationship between 
two speech patterns A and B, along i-axis and j-axis, respectively. FIG. 3 
illustrates the relationship between two successive points of pattern 
matching between speech patterns A and B. 
Referring to FIG. 1, the audio signal 10 being analyzed, has within it a 
plurality of speech patterns. Audio signal 10 is digitized by an 
analog/digital converter 12 and the endpoints of each speech pattern are 
detected by a detector 14. The digital signal of each speech pattern is 
broken into frames and for each frame, analyzer 16 computes the linear 
predictor coefficients (LPC) and converts them to cepstrum coefficients, 
which are the feature vectors of the test pattern. Reference patterns, 
which have been prepared as templates, are stored in a database 18. A 
spectral distance calculator 20 uses a dynamic time warping (DTW) method 
to compare the test pattern to each of the reference patterns stored in 
database 18. The DTW method measures the local spectral distance between 
the test pattern and the reference pattern, using a suitable method of 
measuring spectral distance, such as the Euclidean distance between the 
cepstral coefficients or the weighted cepstral distance measure. The 
template whose reference pattern is closest in distance to the analyzed 
speech pattern, is then selected as being the recognized speech pattern. 
In a paper, entitled "Dynamic Programming Algorithm Optimization for Spoken 
Word Recognition", published by the IEEE Transactions on Acoustics. Speech 
and Signal Processing in February 1978, Sakoe and Chiba reported on a 
dynamic programming (DP) based algorithm for recognizing spoken words. DP 
techniques are known to be an efficient way of matching speech patterns. 
Sakoe and Chiba introduced the technique known as "slope constraint", 
wherein the warping function slope is restricted so as to discriminate 
between words in different categories. 
Numerous spectral distance measures have been proposed including the 
Euclidean distance between cepstral coefficients which is widely used with 
LPC-derived cepstral coefficients. Furui in a paper, entitled "Cepstral 
Analysis Techniques for Automatic Speaker Verification", published by the 
IEEE Transactions on Acoustics. Speech and Signal Processing in April 
1981, proposed a weighted cepstral distance measure which further reduces 
the percentage of errors in recognition. 
In a paper, entitled "A Weighted Cepstral Distance Measure for Speech 
Recognition", published by the IEEE Transactions on Acoustics. Speech and 
Signal Processing in October 1987, Tahkura proposed an improved weighted 
cepstral distance measure as a means to improve the speech recognition 
rate. 
Referring now to FIG. 2, the operation of the DTW method will be explained. 
In FIG. 2., speech patterns A and B are shown along the i-axis and j-axis, 
respectively. Speech patterns A and B are expressed as a sequence of 
feature vectors a.sub.1, a.sub.2, a.sub.3 . . . a.sub.m and b.sub.1, 
b.sub.2, b.sub.3 . . . b.sub.m, respectively. 
The timing differences between two speech patterns A and B, can be depicted 
by a series of `points` Ck(i,j). A `point` refers to the intersection of a 
frame i from pattern A to a frame j of pattern B. The sequence of points 
C1, C2, C3 . . . Ck represent a warping function 30 which effects a map 
from the time axis of pattern A, having a length m, on to the time axis of 
pattern B, having a length n. In the example of FIG. 2, function 30 is 
represented by points c1(1,1), c2(1,2), c3(2,2), c4(3,3), c5(4,3) . . . 
ck(n,m). Where timing differences do not exist between speech patterns A 
and B, function 30 coincides with the 45 degree diagonal line (j=i). The 
greater the timing differences, the further function 30 deviates from the 
45 degree diagonal line. 
Since function 30 is a model of time axis fluctuations in a speech pattern, 
it must abide by certain physical conditions. Function 30 can only advance 
forward and cannot move backwards and the patterns must advance together. 
These restrictions can be expressed by the following relationships: 
EQU i(k)-i(k-1).ltoreq.1 and j(k)-j(k-1).ltoreq.1; 
EQU and 
EQU i(k-1).ltoreq.i(k) and j(k-1) .ltoreq.j(k) (1) 
Warping function 30 moves one step at a time from one of three possible 
directions. For example, to move from C3(2,2) to C4(3,3), function 30 can 
either move directly in one step from (2,2) to (3,3) or indirectly via the 
points at (2,3) or (3,2). 
Function 30 is further restricted to remain within a swath 32 having a 
width r. The outer borders 34 and 36 of swath 32 are defined by (j=i+r) 
and (j =i-r), respectively. 
A fourth boundary condition is defined by: 
EQU i(1)=1, j(1)=1, and i(end)=m, j(end)=n. 
Referring now to FIG. 3, where, for example, the relationship between 
successive points C10(.sub.10,10) and C11(.sub.11,11), of pattern matching 
between speech patterns A and B is illustrated. In accordance with the 
conditions as described hereinbefore, there are three possible ways to 
arrive at point C11(.sub.11,11), that is, either directly from 
C10(.sub.10,10) to C11(.sub.11,11), indicated by line 38 or from 
C10(.sub.10,10) via point (.sub.11,10) to C11(.sub.11,11) indicated by 
lines 40 and 42, or thirdly from C10(.sub.10,10) via point (.sub.10,11) to 
C11(.sub.11,11), indicated by lines 44 and 46. 
Furthermore, associated with each arrival point (i,j), such as point C11 
(.sub.11,11), is a weight W.sub.ij, such as the Euclidean or Cepstral 
distance between the ith frame of pattern A and the jth frame of pattern 
B. By applying a weight W.sub.ij to each of indirect paths 40, 42, 44 and 
46 and a weight of 2W.sub.ij to direct path 38, the path value S.sub.ij, 
at the point (i,j) can be recursively ascertained from the equation: 
##EQU1## 
In order to arrive at endpoint S.sub.nm, it is necessary to calculate the 
best path value S.sub.ij at each point. Row by row is scanned and the 
values of S.sub.ij for the complete previous row plus the values of the 
present row up to the present point are stored. The value for Snm is the 
best path value. 
SUMMARY OF THE INVENTION 
It is thus the general object of the present invention to provide an 
improved pattern recognition method. 
According to the invention there is provided a method of dynamic time 
warping of two sequences of feature sets onto each other. The method 
includes the steps of creating a rectangular graph having the two 
sequences on its two axes, defining a swath of width r, where r is an odd 
number, centered about a diagonal line connecting the beginning point at 
the bottom left of the rectangle to the endpoint at the top right of the 
rectangle and also defining r-1 lines within the swath. The lines defining 
the swath are parallel to the diagonal line. Each array element k of an 
r-sized array is associated with a separate array of the r lines within 
the swath and for each row of the rectangle, the dynamic time warping 
method recursively generates new path values for each array element k as a 
function of the previous value of the array element k and of at least one 
of the current values of the two neighboring array elements k-1 and k+1 of 
the array element k. The latter step of recursively generating new path 
values is repeat for all of the rows of the rectangle and the value of the 
middle array element is selected as the output value sought. 
Furthermore, according to the invention there is provided a method of 
dynamic time warping of two sequences of feature sets onto each other 
where the first sequence set has a length L1 and the second sequence set 
having a length L2 and L1 being greater than L2. The method includes the 
steps of creating a rectangular graph having the first longer sequence on 
its horizontal axis and the second sequence on its vertical axis, defining 
a swath of width r, where r is an odd number, centered about a diagonal 
line connecting the beginning point at the bottom left of the rectangle to 
the endpoint at the top right of the rectangle and also defining r-1 
lines, which are parallel to the diagonal line within the swath. The 
method further includes the steps of associating each array element k of 
an r-sized array with a separate array of the r lines within the swath and 
for each row of the rectangle, recursively generating new path values for 
each array element k as a function of the previous value of array element 
k and of at least one of the current values of the two neighboring array 
elements k-1 and k+1. The latter step is repeated for all of the rows of 
the rectangle. For every L1/(L1-L2) rows of the rectangle, a new path 
value for an array element k=max(k)+1 of the array element k is also 
generated and for each of the array elements k, the new path values are 
replaced by the value of its neighboring array element k+1. The value of 
the middle array element is selected as the output value sought. 
Furthermore, in accordance with a preferred embodiment of the invention, 
the step of selecting the output value is replaced by the step of 
selecting, as output, the smallest value stored in the array elements and 
the array element number associated therewith. 
Furthermore, in accordance with a preferred embodiment of the invention, 
the feature sets have integer values. Additionally, in accordance with a 
preferred embodiment of the invention, the step of defining a swath of 
width r, is replaced by the step of defining a swath connecting the 
beginning point at the top right of the rectangle to the endpoint at the 
bottom left of the rectangle. 
Furthermore, in accordance with a preferred embodiment of the invention, 
there is provided a method of pattern recognition including the steps of 
generating feature sets, having floating points, of a set of reference 
patterns, normalizing the feature sets by their standard deviations across 
the set of reference patterns and selecting only the integer portions of 
the result, storing the portions as integer feature sets for the reference 
patterns, for every input pattern, generating a feature set and formatting 
an integer value in accordance with the step normalizing the feature sets 
by their standard deviations described above and comparing the integer 
feature sets of the input pattern to at least one of the integer feature 
sets of the reference patterns. 
Additionally, in accordance with a preferred embodiment of the invention, 
the step of formatting an integer value includes the steps of calculating 
the average value of the input patterns, calculating the standard 
deviation of each of the feature sets, dividing each of the feature sets 
by the calculated standard deviation and multiplying by a factor q and 
calculating the integer value.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT 
Reference is now made to FIG. 4 which is a flow chart representation of the 
distance pattern recognition system (DPR), constructed and operative in 
accordance with a preferred embodiment of the present invention. The 
following description relates to audio or speech patterns, though it 
should be understood that the present invention is not restricted thereto 
and can apply to any kind of pattern. 
The DPR system converts the audio pattern 50 to be analyzed, into a feature 
set in an integer format, using a processor, generally designated 52. The 
integer feature set for the test pattern is then compared with a database 
54 containing reference patterns, by measuring the spectral distance 
between the test pattern and each reference pattern, using dynamic time 
warping (DTW) by the DTW unit 56. The reference pattern which is closest 
to the test pattern, is then selected as the recognized speech pattern 58. 
It should be noted that integer format requires less storage space than 
floating point format. 
Processor 52 digitizes audio pattern 50 using an analog/digital converter 
60 and then detects the endpoints of each audio pattern 50 using detector 
62. The output is an audio word. Processor 52 breaks the word into frames 
and then extracts the features of each frame via a feature extractor, 
generally designated 64. Feature extractor 64 comprises a linear 
prediction coefficient (LPC) calculator 66, a cepstrum converter 68 and an 
integer formatter 70. LPC calculator 66 computes the linear prediction 
coefficients (LPC) for each frame. Cepstrum converter 68 converts the LPC 
coefficients of each frame into a set of cepstrum coefficients. Finally 
integer formatter 70 normalizes and converts the cepstrum coefficients of 
each frame into integer format. The integer coefficients are the feature 
set of the frame. Database 54 comprises reference patterns, which have 
been previously prepared, using the process hereinbefore described. 
Prior to operation, for each cepstrum coefficient, D1, D2, etc. in the 
feature sets of the database, integer formatter 70 calculates its average 
value and the standard deviation. Then, for each cepstrum coefficient in 
each feature set (whether of the reference database or of an incoming 
feature set), integer formatter 70 divides each cepstrum coefficient 
D.sub.1 by its associated standard deviation .sigma..sub.1, multiplies the 
result by a factor q and saves the integer portion of the result. The 
constant q is any number which results in the integer portions for all the 
cepstrum coefficients being within a range of -100 to +100. Thus, the 
integer coefficient does not require storage of more than one byte of 8 
bits. Using integer formatter 70 enables the full dynamic range of the 
resolution to be used. 
Thus, for example, for five D.sub.1 cepstrum coefficients 5.2, -4.0, 5.4, 
6.4, and 20, the standard deviation .rho. is 6.6513. If q=20, dividing 
each cepstrum coefficient by .sigma. results in values of 15.64, -12.03, 
16.23, 19.24 and 60.14, respectively. The integer coefficients are thus 
15, -12, 16, 19 and 60, respectively. 
Reference is now made to FIG. 5 which is a schematic illustration of the 
relationship between two audio patterns X and Y, of equal length, along 
i-axis and j-axis, respectively. Patterns X and Y have a sequence of 
frames associated with which are integer feature vectors, designated 
x.sub.1, x.sub.2 , . . . x.sub.m and y.sub.1, y.sub.2, . . . y.sub.n, 
respectively. FIG. 5 is useful for understanding the operation of the DTW 
unit 56 and is similar to FIG. 2. 
For identical speech patterns, that is, where timing differences do not 
exist, the warping function F coincides with a 45 degree diagonal line D 
(where x=y). The warping function approximates to the 45 degree diagonal 
line D. The DTW unit of the present invention scans row by row through a 
swath of width r. 
In the present invention, the points in a scan row are labeled S.sub.p 
where p is defined by:-r/2.ltoreq.p.ltoreq.+r/2(4) 
Thus, for example, for a swath width of r=5, p is -2, -10, +1 or +2. Thus, 
each line contains five points, designated S.sub.-2, S.sub.-1, S.sub.0, 
S.sub.+1 and S.sub.+2, centered about point S.sub.0 which lies on the 
ideal diagonal line D. The beginning and end of the path through space of 
FIG. 5 are represented by Sb and Se and also lie on diagonal line D. 
It is a feature of the present invention that DTW unit 56 measures the 
spectral distance between the test pattern X and the reference pattern Y 
by calculating the best path value S.sub.p at each point centered about 
S.sub.0. 
As hereinbefore described with respect to the prior art, weightings can be 
applied to the distance measurements. Any weighing formulation can be 
utilized. A weight Wij is applied to the indirect paths and a weight of 
2Wij is applied to the direct path. 
It is noted that since p is centered about the diagonal line D, j=i+p. 
At point T.sub.0, the path values which are used for calculating the best 
value at T.sub.0 are along direct path S.sub.0 and indirect paths, 
T.sub.-1 and S.sub.+1. Similarly, at point T.sub.+1, the path values which 
are used for calculating the best value at T.sub.+1, are T.sub.0, S.sub.+1 
and S.sub.+2. Thus, at point T.sub.0, the path values which need to be 
retained for calculating subsequent best values are S.sub.0, S.sub.+1, 
S.sub.+2, T.sub.-2 and T.sub.-1. 
It is noted that, in the case of the present invention, once the best path 
value for T.sub.0 is calculated, the value S.sub.0 is no longer required 
and the value T.sub.0 can be stored `in place` of S.sub.0. Thus, at point 
T.sub.+1, the path values which are required for calculating the best 
value can be rewritten as S.sub.0, S.sub.+1 and S.sub.+2 where S.sub.0 is 
the `new` value which equals the value for T.sub.0. Similarly, the values 
T.sub.-1 and T.sub.-2 are stored `in place` of S.sub.-2 and S.sub.-1, 
respectively. The final value of S.sub.0 for endpoint Se yields the 
required path value for the test pattern X, vis-a-vis the reference 
pattern Y. 
The above description can be written recursively as equation: 
##EQU2## 
For test audio pattern X, having a length m, the best path value S.sub.k to 
arrive at any point S.sub.x,y for x=1 . . . m, is the minimum distance of 
three possibilities. Points outside the swath, that is, for k&gt;r+2 or 
k&lt;k-2, equal infinity. 
In summary, the only values which need to be stored for subsequent 
calculations of best path values are the path values for S.sub.-2, 
S.sub.-1, S.sub.0, S.sub.+1 and S+2. 
Reference is now made to FIG. 6 which schematically details the end and 
start points, Se and Sb, respectively between two patterns X and Y, 
respectively. 
The startpoint Sb which lies on the diagonal line D is assumed to have a 
path value S.sub.0 and similarly the final best value for S.sub.0 
coincides with endpoint Se. When endpoint Se is reached, the final five 
values retained (S.sub.-2, S.sub.-1, S.sub.0, S.sub.+1 and S.sub.+2) refer 
to the five points, designated E.sub.-2, E.sub.-1, E.sub.0, E.sub.+1 and 
E.sub.+2, along the boundary of the warping function. Since r/2=2 and the 
warping function follows a 45 degree line, the last row only contains the 
path values E.sub.-2, E.sub.-1 and E.sub.0. All other points in the row 
would have to utilize points outside the swath, which is not allowed. The 
previous row retains the value of E.sub.+1, which has not been 
overwritten, since the new path values for the last row are outside the 
swath. Similarly, the value stored in E.sub.+2 refers to the second to 
last row. 
Since the endpoint detector 62 may have incorrectly selected the endpoints 
of the audio pattern, the start and end points, Sb and Se, respectively, 
are not necessarily correct. Therefore, even if the startpoint Sb is 
known, the final value of S.sub.0 corresponding with endpoint Se may not 
accurately reflect the end point and may not have the best path value. 
If the endpoint Se is known and the startpoint Sb is unknown, the best path 
value process, described hereinabove, can be carried out in reverse. Thus, 
the final path value for Sb is the best of the five boundary values 
B.sub.-2, B.sub.-1, B.sub.0, B.sub.+1 and B.sub.+2, illustrated. 
If the best overall path value is found to be E.sub.+1, for example, the 
assumed length for the test pattern is shorter than previously and thus is 
not equal in length to the reference pattern. Thus, the path values for 
E.sub.-2, E.sub.-1, E.sub.0, E.sub.+1 and E.sub.+2 have to be normalized 
by their path lengths and only then compared. 
If neither start nor end points are known, the startpoint Sb is assumed 
with a value S.sub.0 and the final best path value (one of the five values 
E.sub.-2, E.sub.-1, E.sub.0, E.sub.+1 and E.sub.+2) is found. The point 
having the best total path value is then taken as the startpoint and the 
process carried out in reverse to find the best path value for Sb. 
Therefore, in accordance with the present invention, the path value for 
the reference pattern is the best path value from among the boundary path 
values B.sub.-2, B.sub.-1, B.sub.0, B.sub.+1 and B.sub.+2. 
Reference is now made to FIG. 7 which is a schematic illustration of the 
relationship between two audio patterns X and Y, of unequal length, along 
the i-axis and j-axis, respectively. The relationship between the lengths 
of X and Y is shown, for example, as being 8:12 (2:3). That is pattern Y 
is 1.5 times longer than pattern X. 
For non-identical speech patterns, the straight line G, connecting the 
start and end points Sb and Se, respectively, does not coincide with the 
45 degree diagonal line D, shown dashed. In the example of FIG. 7, path 
values coincide with line G only every third row. That is, points i=2,j=3 
and i=5,j=7 lie on line G. 
The path values S.sub.-2, S.sub.-1, S.sub.0, S.sub.+1 and S.sub.+2 are 
shown for each of rows x=1, x=2 and x=3. Each group of path values is 
designated with a prefix indicating the row, such as the prefix "1" for 
x=1. Thus, path values 1S.sub.-2, 1S.sub.-1, 1S.sub.0, 1S.sub.+1 and 
1S.sub.+2 refer to the row x=1. 
The best path value process is carried out as described hereinbefore for 
patterns of equal length. Thus, startpoint Sb assumes a value of S.sub.0. 
Values are calculated for each row. Every z rows, where z=n/(n-m), it is 
necessary to adjust for the inequality of the test pattern lengths. In the 
example, where z=3 {12/(12-8)}, an extra path value S.sub.+3 is calculated 
every third row. Thus, for the first two rows (x=0 and x=1), the five Sk 
values (S.sub.-2, S.sub.-1, S.sub.0, S.sub.+1 and S.sub.+2) are 
calculated, as hereinbefore described. For the third row, an extra value 
for 2S.sub.+3 is calculated. Then value 2S.sub.-2 is discarded and the 
value for 2S.sub.-1 is stored `in place` of 2S.sub.-2. Similarly, each of 
the stored values, 2S.sub.0, 2S.sub.+1, 2S.sub.+2 and 2S.sub.+3 are stored 
`in place` of their neighbors, 2S.sub.-1, 2S.sub.0, 2S.sub.+1 and 
2S.sub.+2, respectively. 
Every z rows, the path value stored in S.sub.0 `jumps` back on track and 
coincides with the straight line G. Thus, in the example, a `jump` is made 
on rows x=2, x=5 and final row x=8. The final value of S.sub.0 will then 
coincide with the endpoint Se and yield the total path value for the two 
patterns. 
The path values for patterns of unequal length may be represented by the 
following equation: 
##EQU3## 
where: l=number of `jumps` performed to date, which is updated every z 
rows and z=n/(n-m). 
The track of the path value S.sub.0 is shown by double line H. 
As will be appreciated by persons knowledgeable in the art, the various 
embodiments hereinbefore referred to, are given by way of example only and 
do not in any way limit the present invention. 
Those skilled in the art will be readily appreciate that various changes, 
modifications and variations may be applied to the preferred embodiments 
without departing from the scope of the invention as defined in and by the 
appended claims.