Apparatus for performing fast closest match in pattern recognition

• US 7,724,963 B2
• Filed: 02/22/2008
• Issued: 05/25/2010
• Est. Priority Date: 03/20/2003
• Status: Expired due to Term

• 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): PERUNGAVOOR, SATHYANARAYA V
• Application Number:
  US12/035,570
• Publication Number:
  US 20080199086A1
• Time in Patent Office: 823 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 system for finding a closest match of a plurality of N input patterns relative to a plurality of R reference patterns using a plurality of K processing units comprising:

circuitry for loading a first input pattern into a first processing unit and a second input pattern into a second processing unit;

circuitry for sending a selected same one of said R reference patterns to said first and second processing units in response to an index signal selecting a reference pattern;

circuitry for 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;

circuitry for 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;

circuitry for 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;

circuitry for 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; and

circuitry for incrementing said index signal when said calculations of said first and second distance values are complete for each of said R reference patterns.

2. The system of claim 1, further comprising circuitry for determining when all of said R reference patterns have been sent indicating that a closest match to said first and second input patterns has been determined, 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.

3. The system of claim 1, further including circuitry for outputting said first and second identification values on a bus coupling said K processing units after said R reference patterns have been processed.

4. The system of claim 1, further including circuitry for outputting said final first and second minimum distance values on a bus coupling said K processing units after said R reference patterns have been processed.

5. The system of claim 1, further including circuitry for 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.

6. The system of claim 5, further including circuitry for 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.

7. The system of claim 6, wherein said K processing units are in a plurality of integrated circuits.

8. The system of claim 1, wherein said K processing units are in a single integrated circuit.

9. The system of claim 1, wherein said K processing units are in a plurality of integrated circuits.

10. The system of claim 1, wherein K is equal to N.