Method and apparatus for comparing patterns

A pattern comparing method comprising;

• a first step for converting each of input signals to an input pattern comprising a series of feature vectors, each input feature vector being produced at every frames each of which corresponds to a constant time unit of the input signal;
• a second step for calculating a vector-to-vector distance as a frame-to-frame distance between a frame of said input pattern and a frame of a reference pattern, said vector-to-vector distance indicating the degree of similarity between the input feature vector of the ith frame of each input pattern and a feature vector of the jth frame of said reference pattern;
• a third step for calculating ##EQU30## regarding i=1 to I where D(0)=0, and memorizing m as a back pointer B(i) and n as the rearmost reference pattern name N(i) when each D(i) is calculated, where,
• D(i) represents the sum of frame-to-frame distance between the local pattern of the first to the ith frames of the input pattern and a reference pattern or a combination pattern of a plurality of reference patterns,
• D(m) represents the sum of frame-to-frame distance between the local pattern of the first to the mth (m<i) frames of the input pattern and a reference pattern or a combination pattern of a plurality of reference patterns,
• D.sup.n (m+1;i) represents a local cumulative distance which is a pattern-to-pattern distance between the local pattern of m+1 to ith frames of the input pattern and the nth reference pattern, and
• n represents a number given to said reference pattern;
• a fourth step for calculating said local cumulative distance D.sup.n (m+1;i) by calculating by a dynamic programming method on an i-j plane whose abscissa is the frame numbers i of the input pattern and whose ordinate is the frame number of the reference pattern, a matching path whose starting point is (m+1,1) determined with respect of i and terminating point is (i,J.sup.n), in which the sum of the product of said frame-to-frame distance and weight along said path is minimum, and memorizing said sum of the product of said frame-to-frame distance and weight with respect of said m, where
• J.sup.n represents frame number of reference pattern n,
• said matching path represents a path connecting corresponding points,
• said corresponding point represents a point for indicating which frame-to-frame distance between the input pattern and the standard pattern should be calculated, and
• said weight depends on the types of the path from the first preceding corresponding point to present corresponding point, the sum of said weight along the matching path being dependent only on the length of the pattern;
• and
• a fifth step for determining a reference pattern sequence corresponding to the input pattern in a reverse order to the input using said back pointer B(i) and the rearmost reference pattern name N(i);
• characterized in that
• said fourth step comprises steps of:
• (1) obtaining only one path by minimizing as to m, the sum of said weight along the matching path being dependent only on the length of the reference pattern,
• (2) normalizing the sum of the products of said frame-to-frame distance and weight by the sum of said weight along the matching path, and
• (3) calculating the local cumulative distance for a plurality of local input patterns having different frame lengths by multiplying said normalized sum of the products of said frame-to-frame distance and weight by a first frame number of said local input pattern and by a second frame number obtained by adding a number to or by subtracting a number from said first frame number.

A pattern comparing method comprising;

• a first step for converting each of input signals to an input pattern comprising a series of feature vectors, each input feature vector being produced at every frames each of which corresponds to a constant time unit of the input signal;
• a second step for calculating a vector-to-vector distance as a frame-to-frame distance between a frame of said input pattern and a frame of a reference pattern, said vector-to-vector distance indicating the degree of similarity between the input feature vector of the ith frame of each input pattern and a feature vector of the jth frame of said reference pattern;
• a third step for calculating ##EQU31## regarding i=1 to I where D(0)=0, and memorizing m as a back pointer B(i) and n as the rearmost reference pattern name N(i) when each D(i) is calculated, where,
• D(i) represents the sum of frame-to-frame distance between the local pattern of the first to the ith frames of the input pattern and a reference pattern or a combination pattern of a plurality of reference patterns,
• D(m) represents the sum of frame-to-frame distance between the local pattern of the first to the mth (m<i) frames of the input pattern and a reference pattern or a combination pattern of a plurality of reference patterns,
• D.sup.n (m+1;i) represents a local cumulative distance which is a pattern-to-pattern distance between the local pattern of m+1 to ith frames of the input pattern and the nth reference pattern, and
• n represents a number given to said reference pattern;
• a fourth step for calculating said local cumulative distance D.sup.n (m+1;i) by calculating by a dynamic programming method on an i-j plane whose abscissa is the frame numbers i of the input pattern and whose ordinate is the frame number of the reference pattern, a matching path whose starting point is (m+1,1) determined with respect of i and terminating point is (i, J.sup.n), in which the sum of the product of said frame-to-frame distance and weight along said path is minimum, and memorizing said sum of the product of said frame-to-frame distance and weight with respect of said m, where
• J.sup.n represents frame number of reference pattern n,
• said matching path represents a path connecting corresponding points,
• said corresponding point represents a point for indicating which frame-to-frame distance between the input pattern and the standard pattern should be calculated, and
• said weight depends on the types of the path from the first preceding corresponding point to present corresponding point, the sum of said weight along the matching path being dependent only on the length of the pattern;
• and
• a fifth step for determining a reference pattern sequence corresponding to the input pattern in a reverse order to the input using said back pointer B(i) and the rearmost reference pattern name N(i);
• characterized in that
• said fourth step comprises steps of:
• (1) obtaining by a dynamic programming method a plurality of matching paths in which the sum of the product of said frame-to-frame distance and weight is close to minimum, the sum of said weight along the matching path being dependent only on the length of the reference pattern,
• (2) normalizing the sum of the products of said frame-to-frame distance and weight by the sum of said weight along the matching path, and
• (3) calculating the local cumulative distance for a plurality of local input patterns having different frame lengths by multiplying said normalized sum of the products of said frame-to-frame distance and weight by a first frame number of said local input pattern and by a second frame number obtained by adding a number to or by subtracting a number from said first frame number.

A pattern comparing method comprising;

• a first step for converting each of input signals to an input pattern comprising a series of feature vectors, each input feature vector being produced at every frames each of which corresponds to a constant time unit of the input signal;
• a second step for calculating a vector-to-vector distance as a frame-to-frame distance between a frame of said input pattern and a frame of a reference pattern, said vector-to-vector distance indicating the degree of similarity between the input feature vector of the ith frame of each input pattern and a feature vector of the jth frame of said reference pattern;
• a third step for calculating ##EQU32## regarding i=1 to I where D.sub.0 (0)=0, and memorizing m as a back pointer B.sub.x (i) and n as the rearmost reference pattern name N.sub.x (i) when each D.sub.x (i) is calculated, where,
• D.sub.x (i) represents the sum of frame-to-frame distance between the local pattern of the first to the ith frames of the input pattern and a reference pattern or a combination pattern of reference patterns, the number of said reference pattern being x,
• D.sub.x-1 (m) represents the sum of frame-to-frame distance between the local pattern of the first to the mth (m<i) frames of the input pattern and a reference pattern or a combination pattern of reference patterns, the number of said reference pattern being x-1,
• D.sup.n (m+1;i) represents a local cumulative distance which is a pattern-to-pattern distance between the local pattern of m+1 to ith frames of the input pattern and the nth reference pattern, and
• n represents a number given to said reference pattern;
• a fourth step for calculating said local cumulative distance D.sup.n (m+1:i) by calculating by a dynamic programming method on an i-j plane whose abscissa is the frame numbers i of the input pattern and whose ordinate is the frame number of the reference pattern, a matching path whose starting point is (m+1,1) determined with respect of i and terminating point is (i,J.sup.n), in which the sum of the product of said frame-to-frame distance and weight along said path is minimum, and memorizing said sum of the product of said frame-to-frame distance and weight with respect of said m, where
• J.sup.n represents frame number of reference pattern n,
• said matching path represents a path connecting corresponding points,
• said corresponding point represents a point for indicating which frame-to-frame distance between the input pattern and the standard pattern should be calculated, and
• said weight depends on the types of the path from the first preceding corresponding point to present corresponding point, the sum of said weight along the matching path being dependent only on the length of the pattern;
• and
• a fifth step for determining a reference pattern sequence corresponding to the input pattern in a reverse order to the input using said back pointer B.sub.x (i) and the rearmost reference pattern name N.sub.x (i);
• characterized in that
• said fourth step comprises step of:
• (1) obtaining only one path by minimizing as to m, the sum of said weight along the matching path being dependent only on the length of the reference pattern,
• (2) normalizing the sum of the products of said frame-to-frame distance and weight by the sum of said weight along the matching path, and
• (3) calculating the local cumulative distance for a plurality of local input patterns having different frame lengths by multiplying said normalized sum of the products of said frame-to-frame distance and weight by a first frame number of said local input pattern and by a second frame number obtained by adding a number to or by subtracting a number from said first frame number.

A pattern comparing method comprising:

• a first step for converting each of input signals to an input pattern comprising a series of feature vectors, each input feature vector being produced at every frames each of which corresponds to a constant time unit of the input signal;
• a second step for calculating a vector-to-vector distance as a frame-to-frame distance between a frame of said input pattern and a frame of a reference pattern, said vector-to-vector distance indicating the degree of similarity between the input feature vector of the ith frame of each input pattern and a feature vector of the jth frame of said reference pattern;
• a third step for calculating ##EQU33## regarding i=1 to I where D.sub.0 (0)=0, and memorizing m as a back pointer B.sub.x (i) and n as the rearmost reference pattern name N.sub.x (i) when each D.sub.x (i) is calculated, where,
• D.sub.x (i) represents the sum of frame-to-frame distance between the local pattern of the first to the ith frames of the input pattern and a reference pattern or a combination pattern or reference patterns, the number of said reference pattern being x,
• D.sub.x-1 (m) represents the sum of frame-to-frame distance between the local pattern of the first to the mth (m<i) frames of the input pattern and a reference pattern or a combination pattern of reference patterns, the number of said reference pattern being x-1,
• D.sup.n (m+1;i) represents a local cumulative distance which is a pattern-to-pattern distance between the local pattern of m+1b 1;i) represents a local cumulative distance which is a pattern-to-pattern distance between the local pattern of m+1 to ith frames of the input pattern and the nth reference pattern, and
• n represents a number given to said reference pattern;
• a fourth step for calculating said local cumulative distance D.sup.n (m+1:i) by calculating by a dynamic programming method on an i-j plane whose abscissa is the frame numbers i of the input pattern and whose ordinate is the frame number of the reference pattern, a matching path whose starting point is (m+1,1) determined with respect of i and terminating point is (i,J.sup.n), in which the sum of the product of said frame-to-frame distance and weight along said path is minimum, and memorizing said sum of the product of said frame-to-frame distance and weight with respect of said m, where
• J.sup.n represents frame number of reference pattern n,
• said matching path represents a path connecting corresponding points,
• said corresponding point represents a point for indicating which frame-to-frame distance between the input pattern and the standard pattern should be calculated, and
• said weight depends on the types of the path from the first preceding corresponding point to present corresponding point, the sum of said weight along the matching path being dependent only on the length of the pattern;
• and
• a fifth step for determining a reference pattern sequence corresponding to the input pattern in a reverse order to the input using said back pointer B.sub.x (i) and the rearmost reference pattern name N.sub.x (i);
• characterized in that
• said fourth step comprises steps of:
• (1) obtaining by a dynamic programming method a plurality of matching paths in which the sum of the product of said frame-to-frame distance and weight is close to minimum, the sum of said weight along the matching path being dependent only on the length of the reference pattern,
• (2) normalizing the sum of the products of said frame-to-frame distance and weight by the sum of said weight along the matching path, and
• (3) calculating the local cumulative distance for a plurality of local input patterns having different frame lengths by multiplying said normalized sum of the products of said frame-to-frame distance and weight by a first frame number of said local input pattern and by a second frame number obtained by adding a number to or by subtracting a number from said first frame number.

A pattern comparing method comprising;

• a first step for converting each of input signals to an input pattern comprising a series of feature vectors, each input feature vector being produced at every frames each of which corresponds to a constant time unit of the input signal;
• a second step for calculating a vector-to-vector distance as a frame-to-frame distance between a frame of said input pattern and a frame of a reference pattern, said vector-to-vector distance indicating the degree of similarity between the input feature vector of the ith frame of each input pattern and a feature vector of the jth frame of said reference pattern;
• a third step for calculating ##EQU34## i=1 to I where D.sub.0 (0)=0, and memorizing m as a back pointer B.sub.q (i) for the frame, n as the rearmost reference pattern name N.sub.q (i) and q as a back pointer Q.sub.q (i) for a state when each D.sub.q (i) is calculated, where
• D.sub.q (i) represents the sum of frame-to-frame distance between the local pattern of the first to the ith frames of the input pattern and a combination pattern of reference patterns when the rearmost reference pattern is outputted and transmitted to a state q,
• D.sub.p (m) represents the sum of frame-to-frame distance between the local pattern of the first to the mth (m<i) frames of the input pattern and a combination pattern of reference patterns when the rearmost reference pattern is outputted and transmitted to the state q,
• D.sup.n (m+1;i) represents a local cumulative distance which is a pattern-to-pattern distance between the local pattern of m+1 to ith frames of the input pattern and the nth reference pattern, and
• n represents a number given to said reference pattern;
• a fourth step for calculating said local cumulative distance D.sup.n (m+1:i) by calculating by a dynamic programming method on an i-j plane whose abscissa is the frame numbers i of the input pattern and whose ordinate is the frame number of the reference pattern, a matching path whose starting point is (m+1,1) determined with respect of i and terminating point is (i, J.sup.n), in which the sum of the product of said frame-to-frame distance and weight along said path is minimum, and memorizing said sum of the product of said frame-to-frame distance and weight with respect of said m, where
• J.sup.n represents frame number of reference pattern n,
• said matching path represents a path connecting corresponding points,
• said corresponding point represents a point for indicating which frame-to-frame distance between the input pattern and the standard pattern should be calculated, and
• said weight depends on the types of the path from the first preceding corresponding point to present corresponding point, the sum of said weight along the matching path being dependent only on the length of the pattern;
• and
• a fifth step for determining a reference pattern sequence corresponding to the input pattern in a reverse order to the input using said back pointers B.sub.q (i) and Q.sub.q (i) and the rearmost reference pattern name N.sub.q (i);
• characterized in that
• said fourth step comprises steps of:
• (1) obtaining only one path by minimizing as to m, the sum of said weight along the matching path being dependent only on the length of the reference pattern,
• (2) normalizing the sum of the products of said frame-to-frame distance and weight by the sum of said weight along the matching path, and
• (3) calculating the local cumulative distance for a plurality of local input patterns having different frame lengths by multiplying said normalized sum of the products of said frame-to-frame distance and weight by a first frame number of said local input pattern and by a second frame number obtained by adding a number to or by subtracting a number from said first frame number.

A pattern comparing method comprising;

• a first step for converting each of input signals to an input pattern comprising a series of feature vectors, each input feature vector being produced at every frames each of which corresponds to a constant time unit of the input signal;
• a second step for calculating a vector-to-vector distance as a frame-to-frame distance between a frame of said input pattern and a frame of a reference pattern, said vector-to-vector distance indicating the degree of similarity between the input feature vector of the ith frame of each input pattern and a feature vector of the jth frame of said reference pattern;
• a third step for calculating ##EQU35## regarding i=1 to I where D.sub.0 (0)=0, and memorizing m as a back pointer B.sub.q (i) for the frame, n as the rearmost reference pattern name N.sub.q (i) and q as a back pointer Q.sub.q (i) for a state when each D.sub.q (i) is calculated, where,
• D.sub.q (i) represents the sum of frame-to-frame distance between the local pattern of the first to the ith frames of the input pattern and a combination pattern of reference patterns when the rearmost reference pattern is outputted and transmitted to a state q,
• D.sub.p (m) represents the sum of frame-to-frame distance between the local pattern of the first to the mth (m<i) frames of the input pattern and a combination pattern of reference patterns when the rearmost reference pattern is outputted and transmitted to the state q,
• D.sup.n (m+1;i) represents a local cumulative distance which is a pattern-to-pattern distance between the local pattern of m+1 to ith frames of the input pattern and the nth reference pattern, and
• n represents a number given to said reference pattern;
• a fourth step for calculating said local cumulative distance D.sup.n (m+1;i) by calculating by a dynamic programming method on an i-j plane whose abscissa is the frame numbers i of the input pattern and whose ordinate is the frame number of the reference pattern, a matching path whose starting point is (m+1,1) determined with respect of i and terminating point is (i,J.sup.n), in which the sum of the product of said frame-to-frame distance and weight along said path is minimum, and memorizing said sum of the product of said frame-to-frame distance and weight with respect of said m, where
• J.sup.n represents frame number of reference pattern n,
• said matching path represents a path connecting corresponding points,
• said corresponding point represents a point for indicating which frame-to-frame distance between the input pattern and the reference pattern should be calculated, and
• said weight depends on the types of the path from the first preceding corresponding point to present corresponding point, the sum of said weight along the matching path being dependent only on the length of the pattern;
• and
• a fifth step for determining a reference pattern sequence corresponding to the input pattern in a reverse order to the input using said back pointers B.sub.q (i) and Q.sub.q (i) and the rearmost reference pattern name N.sub.q (i);
• characterized in that
• said fourth step comprises steps of:
• (1) obtaining by a dynamic programming method a plurality of matching paths in which the sum of the product of said frame-to-frame distance and weight is close to minimum, the sum of said weight along the matching path being dependent only on the length of the reference pattern,
• (2) means for normalizing the sum of the products of said frame-to-frame distance and weight by the sum of said weight along the matching path, and
• (3) calculating the local cumulative distance for a plurality of local input patterns having different frame lengths by multiplying said normalized sum of the products of said frame-to-frame distance and weight by a first frame number of said local input pattern and by a second frame number obtained by adding a number to or by subtracting a number from said first frame number.