Method for pattern recognition using prototype transformations and hierarchical filtering

• US 5,572,604 A
• Filed: 11/23/1994
• Issued: 11/05/1996
• Est. Priority Date: 11/22/1993
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Simard, Patrice Y.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): PATEL, JAYANTI K
• Application Number:
  US08/344,791
• Time in Patent Office: 713 Days
• Field of Search: 382/160, 382/224, 382/225, 382/228
• US Class Current: 382/224
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence

Abstract

Articles being graphical input patterns are sorted by a pattern-recognition machine that includes a data base of prototype patterns, each labeled with its respective class. The sorting method includes stops of storing input patterns in the pattern-recognition machine and classifying the stored input patterns. The classification is performed by calculating at least two distance functions between input patterns and prototype patterns. The distance functions belong to a hierarchy of distance functions that vary in the degree to which they are computationally intensive, and concomitantly, in their accuracy. Overall computational requirements are reduced by using less computationally intensive distance functions to preliminary filter out those prototype patterns that are farthest from the input pattern.

Claims

1. A method for sorting articles bearing graphical patterns to be referred to as input patterns, the method comprising the steps of:

converting each input pattern to a pixel array, storing the pixel array in a digital pattern-recognition machine, classifying each input pattern, and performing a prescribed physical manipulation of each article in response to the result of classifying the pattern borne by that article;

wherein the machine comprises a storage device and a library of prototype patterns stored within the storage device, each prototype pattern belongs to one of a multiplicity of known classes, and each prototype pattern is labeled with its respective class, and the classifying step comprises, in said machine;

a) for each input pattern, retrieving each of the prototype patterns from the storage device and evaluating a distance function d₁ between the input pattern and each of the prototype patterns, wherein d₁ is the first of a plurality of distance functions d_i, i=1, . . . , M, M a positive integer at least 2;

b) responsive to (a), keeping the K₁ closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein K₁ is a positive integer less than the total number of prototype patterns in the library;

c) evaluating at least one further distance function d_j between the input pattern and at least some of the K₁ closest prototype patterns, wherein j is a positive integer at least 2 and at most M;

d) responsive to the evaluation of each further distance function d_i, i=2, . . . M, keeping the K_i closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein K_i is a positive integer less than K_i-1 ; and

e) choosing the best class, according to an appropriate decision procedure, from the classes represented in a population of prototype patterns that is limited in response to the evaluation of the last distance function d_M, wherein;

f) each evaluation of step (c) is carded out between the input pattern and the K_j-1 closest prototype patterns that were kept in response to the evaluation of the last preceding distance function d_j-1 ;

g) at least one of the further distance functions d_i, i at least 2, such distance to be referred to as a tangent distance of complexity L_i, is evaluated with reference to a set of image transformations that are selected to leave the respective classes of the prototype patterns invariant, and such evaluation comprises the further steps of;

generating L_i tangent vectors from a subset of said image transformations, wherein L_i is at least 1, and the L_i tangent vectors define an input hyperplane containing the input pattern; and

evaluating a Euclidean distance with respect to a transformed pattern lying on the input hyperplane.

3. The method of claim 1 or claim 2, wherein each distance function d_i, i=1, . . . , M, is a distance function in a vector space of a respective dimensionality.

4. The method of claim 3, wherein at least two distance functions are evaluated in respective vector spaces having different dimensionalities, and the distance function having the smaller dimensionality is evaluated before the distance function having the larger dimensionality.

5. The method of claim 3, wherein at least two of the distance functions are tangent distances having different respective complexities, and the distance function having the smaller complexity is evaluated before the distance function having the greater complexity.

6. The method of claim 3, further comprising, for each value of i, after evaluating the distances d_i, the further steps of:

evaluating a confidence score that measures the effectiveness of d_i for distinguishing between at least two prototype classes; and

if the confidence score exceeds a predetermined threshold, going to the step of choosing the best class without performing the step of evaluating a succeeding distance d_i+1.

7. The method of claim 6, wherein each confidence score is the difference between d i for the closest prototype pattern P₀, and d_i for the closest prototype pattern not in the same class as P₀.

2. A method for sorting articles bearing graphical patterns to be referred to as input patterns, the method comprising the steps of:

converting each input pattern to a pixel array, storing the pixel array in a digital pattern-recognition machine, classifying each input pattern, and performing a prescribed physical manipulation of each article in response to the result of classifying the pattern borne by that article;

wherein the machine comprises a storage device and a library of prototype patterns stored within the storage device, each prototype pattern belongs to one of a multiplicity of known classes, and each prototype pattern is labeled with its respective class; and

the classifying step comprises, in said machine;

a) for each input pattern, retrieving each of the prototype patterns from the storage device and evaluating a distance function d₁ between the input pattern and each of the prototype patterns, wherein d₁ is the first of a plurality of distance functions d_i, i=1, . . . , M, M a positive integer at least 2;

b) responsive to (a), keeping the K₁ closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein K₁ is a positive integer less than the total number of prototype patterns in the library;

c) evaluating at least one further distance function d_j between the input pattern and at least some of the K₁ closest prototype patterns, wherein j is a positive integer at least 2 and at most M;

d) responsive to the evaluation of each further distance function d_i, i=2, . . . M, keeping the K_i closest prototype patterns and eliminating from consideration the rest of the prototype patterns, wherein K_i is a positive integer less than K_i-1 ; and

e) choosing the best class, according to an appropriate decision procedure, from the classes represented in a population of prototype patterns that is limited in response to the evaluation of the last distance function d_M, wherein;

f) each evaluation of step (c) is carded out between the input pattern and the K_j-1 closest prototype patterns that were kept in response to the evaluation of the last preceding distance function d_j-1 ;

g) at least one of the further distance functions d_i, i at least 2, such distance to be referred to as a tangent distance of complexity L_i, is evaluated with reference to a set of image transformations that are selected to leave the respective classes of the prototype patterns invariant, and such evaluation comprises the further steps of;

generating L_i tangent vectors from a subset of said image transformations, wherein L_i is at least 1, and the L_i tangent vectors define a prototype hyperplane containing a prototype pattern; and

evaluating a Euclidean distance with respect to a transformed pattern lying on the prototype hyperplane.