Method and apparatus for performing fast closest match in pattern recognition

• US 7,366,352 B2
• Filed: 03/20/2003
• Issued: 04/29/2008
• Est. Priority Date: 03/20/2003
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Slyfield, Jan M., Tannhof, Pascal R., Kravec, Kerry A., Saidi, Ali G.
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): PERUNGAVOOR, SATHYANARAYA V
• Application Number:
  US10/393,146
• Publication Number:
  US 20040184662A1
• Time in Patent Office: 1,867 Days
• Field of Search: 382/225
• US Class Current: 382/225
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding

Abstract

A method and apparatus for determining a closest match of N input patterns relative to R reference patterns using K processing units. Each of a set of input patterns are loaded into the K processing units. One of the Reference patterns is sequentially loaded into each of the processing units and a distance defining the similarity between the reference pattern and each of the input patterns is calculated. A present calculated distance replaces its corresponding stored present minimum distance if it is has a smaller value. After the R reference patterns have been processed the minimum distance and its corresponding identification for all N input patterns is determined without merging outputs. The minimum distances and the identifications may be read either in parallel or serially. The apparatus is easily scalable by adding processors. The number of reference patterns may be easily increased without altering system configuration.

Claims

1. A method for finding a closest match of each of a plurality of N input patterns relative to a plurality of R reference patterns using a plurality of K processing units comprising:

(a) loading a first input pattern into a first processing unit and a second input pattern into a second processing unit;

(b) sending one of said R reference patterns as a selected reference pattern to said first and second processing units;

(c) calculating a first distance in said first processing unit, said first distance representing a similarity of said selected reference pattern to said first input pattern;

(d) calculating a second distance in said second processing unit, said second distance representing a similarity of said selected reference pattern to said second input pattern;

(e) saving said first distance as a present minimum first distance and saving a first identification corresponding to said selected reference pattern used to calculate said present minimum first distance if said first distance is smaller than a stored previous present minimum first distance;

(f) saving said second distance as a present minimum second distance and saving a second identification corresponding to said selected reference pattern used to calculate said present minimum second distance if said second distance is smaller than a stored previous present minimum second distance;

(g) repeating steps (b)-(f) until all of said R reference patterns have been loaded, wherein said present first minimum distance is a final first minimum distance of said first input pattern relative to said R reference patterns and said first identification identifies which of said R reference patterns is a closest match to said first input pattern, and said present second minimum distance is a final second minimum distance of said second input pattern relative to said R reference patterns and said second identification identifies which of said R reference patterns is a closest match to said second input pattern; and

sending said first identification from a first selection circuit in said first processing unit to a second selection circuit in said second processing unit after said R reference patterns have been processed, wherein said first selection circuit selects between said final first minimum distance and said first identification.

2. The method of claim 1, further including the step of sending said second identification from said second selection circuit in said second processing unit to a third selection circuit in a third processing unit after said R reference patterns have been processed, wherein said second selection circuit selects between said final second minimum distance and said second identification.

3. A method for finding a closest match of each of a plurality of N input patterns relative to a plurality of R reference patterns using a plurality of K processing units comprising:

(a) calculating a first distance between a first input pattern and a selected reference pattern in a first processing unit, said first distance representing a similarity of said selected reference pattern to said first input pattern

(b) calculating a second distance between a second input pattern and said selected reference pattern in a second processing unit, said second distance representing a similarity of said selected reference pattern to said second input pattern;

(c) saving said first distance as a present minimum first distance and saving a first identification corresponding to said selected reference pattern used to calculate said present minimum first distance if said first distance is smaller than a stored previous present minimum first distance;

(d) saving said second distance as a present minimum second distance and saving a second identification corresponding to said selected reference pattern used to calculate said present minimum second distance if said second distance is smaller than a stored previous present minimum second distance;

(e) repeating steps (b)-(d) until all of said R reference patterns have been processed, wherein said present first minimum distance is a final first minimum distance of said first input pattern relative to said R reference patterns and said first identification identifies which of said R reference patterns is a closest match to said first input pattern, and said present second minimum distance is a final second minimum distance of said second input pattern relative to said R reference patterns and said second identification identifies which of said R reference patterns is a closest match to said second input pattern; and

sending said first identification from a first selection circuit in said first processing unit to a second selection circuit in said second processing unit after said R reference patterns have been processed, wherein said first selection circuit selects between said final first minimum distance and said first identification.

4. The method of claim 3, further including the step of sending said second identification from said second selection circuit in said second processing unit to a third selection circuit in a third processing unit after said R reference patterns have been processed, wherein said second selection circuit selects between said final second minimum distance and said second identification.