Apparatus for calculating pattern dissimilarity between patterns

• US 4,571,697 A
• Filed: 12/28/1982
• Issued: 02/18/1986
• Est. Priority Date: 12/29/1981
• Status: Expired due to Term

• Current Assignee: Nippon Electric Company Limited (NEC Corporation)
• Original Assignee: Nippon Electric Company Limited (NEC Corporation)
• Inventors: Watanabe, Takao
• Primary Examiner(s): Chin, Gary
• Application Number:
  US06/453,867
• Time in Patent Office: 1,148 Days
• Field of Search: 364/560, 364/561, 364/562, 364/513, 364/513.5, 364/728, 381/42, 381/43
• US Class Current: 704/238
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes

Abstract

Apparatus for calculating the distance between two patterns, each given in the form of time sequences of vectors, by using the distance between a feature vector of one pattern and a line segment connecting two feature vectors of the other pattern. The apparatus calculates the distance D representing the length of the line segment between two adjacent vectors a_i+l and a_i of a first time sequence of vectors, A. It also calculates the distance X and Y representing, respectively, the distance between the vector a_i+l and a vector b_j, and the distance between the vectors a_i and b_j, where the vector b_j is a vector of the second time sequence of vectors, B. Processing units generate a distance signal Z representing the perpendicular distance from the vector b_j to the line segment connecting adjacent vectors a_i+l and a_i. Comparing the absolute value of the difference between the distance X and Y to the length of the line segment D determines a selection signal which selects one of the distances X, Y or Z as the most correct distance between the two patterns.

Claims

1. An apparatus for determining a dissimilarity between a first pattern and a second pattern by adopting a distance between a line segment connecting two adjacent vectors of said first pattern and one vector of said second pattern, each of said first and second patterns being given in form of a time sequence of vectors, said apparatus comprising:

first memory means for storing said first pattern, including said two adjacent vectors;

second memory means for storing said second pattern; and

calculating means, responsive to said first and second patterns stored in said first and second memory means, respectively, for calculating said distance, said calculating means comprising;

first means for calculating a first distance D between said two adjacent vectors in a first time sequence of vectors, said first time sequence corresponding to said first pattern;

second means for calculating second distances X and Y, respectively, between one of said two adjacent vectors in said first pattern and said one vector in a second time sequence of vectors, and between the other of said two adjacent vectors in said first pattern and said one vector in a second time sequence of vetors, said second time sequence correponding to said second pattern;

third means for calculating said distance between said line segment connecting two adjacent vectors of said first pattern and said one vector of said second pattern by calculating Z(=XY-1/4(X+Y-D)²)/D) in response to said first distance and said second distances to thereby determine a dissimilarity between said first and second patterns; and

means for selecting one of said distances X, Y and Z, wherein said selecting means selects said distance X when D=0, said distance Z when D≠

0 and -D≦

X-Y≦

D, said distance X when D≠

0 and X-Y<

-D, and said distance Y when D≠

0 and X-Y>

D.

2. An apparatus for determining a dissimilarity measure between a first pattern A and a second pattern B by adopting a distance between a line segment connecting two adjacent vectors of said first pattern A and one vector of said second pattern B, said first pattern A being given in the form of a first time sequence of vectors {a₁, a₂, - - - , a_i, - - - , a_I } and said second pattern B being given in the form of a second time sequence of vectors {b₁, b₂, - - - , b_j, - - - b_j } said apparatus comprising:

first memory means for storing said first pattern, including said two adjacent vectors;

second memory means for storing said second pattern; and

calculating means, responsive to said first and second patterns stored in said first and second memory means, respectively, for calculating said distance, said calculating means comprising;

first means for calculating a distance D(=d(a_i+1, a_i)) between two adjacent vectors a_i+1 and a_i of said first time sequence in a vector space;

second means for calculating a distance X(=d(a_i+1, b_j)) between said vector a_i+1 of said first time sequence and one vector b_j of said second time sequence in the vector space, and for calculating a distance Y(=d(a_i, b_j)) between said vector a_i of said first time sequence and said one vector b_j of said second time sequence;

third means for calculating said distance between said line segment connecting said two adjacent vectors of said first pattern A and said one vector of said second pattern B by calculating Z(=(XY-1/4(X+Y-D)² /D) in response to said distances D, X and Y to thereby determine a dissimilarity between said first and second patterns; and

means for selecting one of said distances X, Y and Z, wherein said selecting means selects said distance X when D=0, said distance Z when D≠

0 and -D≦

X-Y≦

D, said distance X when D≠

0 and X-Y<

-D, and said distance Y when D≠

0 and X-Y>

D.

3. The apparatus as claimed in claim 2, wherein said third means for calculating a distance Z comprises;

multiplier means for producing the product of the distances X and Y, first coefficient multiplication means for multiplying the distance D by the value -1, first adder means for adding the distances X, Y and -D, squaring means for squaring the value (X+Y-D), second coefficient multiplication means for multiplying the value (X+Y-D)² by (-1/4), second adder means for adding the product XY to the value -1/4(X+Y-D)² and divider means for dividing the value XY-1/4(X+Y-D)² by the distance D to produce a value Z defined as (XY-1/4(X+Y-D)²)/D.

4. The apparatus as claimed in claim 3, wherein said selecting means comprises;

subtraction means for producing the difference between distance X and distance Y, first coefficient multiplication means for multiplying the distance D by the value -1, comparator means for comparing the value X-Y with the distances D and -D and for producing a selection signal indicating which of the relationships -D≦

X-Y≦

D, X-Y<

-D or X-Y>

D is true, and means for detecting whether the distance D is equal to zero or not, wherein said selecting means selects one of said distances X, Y and Z in response to said selection signal and an output of said detecting means.