Target recognition using string-to-string matching

• US 4,845,610 A
• Filed: 03/13/1987
• Issued: 07/04/1989
• Est. Priority Date: 07/13/1984
• Status: Expired due to Fees

• Current Assignee: Loral Aerospace Corp. (MHR Holdings LLC (New York))
• Original Assignee: Ford Aerospace & Communications Corporation
• Inventors: Parvin, Bahram A.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/025,745
• Time in Patent Office: 844 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/419, 364/518, 364/523, 364/516, 358/109, 358/101, 382/16, 382/30, 382/50, 382/7, 382/48
• US Class Current: 712/17
• CPC Class Codes: G06F 15/8046 Systolic arrays
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

A method for determining whether a perceived target is acceptably close to a model target. The perceived target is first segmented using a relaxation based procedure. Structural features from the perceived target are extracted by producing a compact one-dimensional description of the perceived target'"'"'s boundary. Said structural features are classified by using string-to-string matching, wherein one of two symbolic strings is a representation of the compact one-dimensional description of the boundary of the perceived target, and the other of said two symbolic strings is a pre-stored representation of the model target. The string-to-string matching entails measuring the distance between the two strings based upon deletion, insertion, and substitution of symbols from one string to the other. Performing the string-to-string matching measures how closely local structural features of the perceived target resemble local structural features of the model target.

Claims

1. A method for determining whether a perceived target is acceptably close to a model target, said method comprising the steps of:

segmenting the perceived target using a relaxation based procedure;

extracting structural features from the perceived target by producing a compact one-dimensional description of the perceived target'"'"'s boundary; and

classifying said structural features by using string-to-string matching, wherein one of two symbolic strings is a representation of the compact one-dimensional description of the boundary of the perceived target, and the other of said two symbolic strings is a prestored representation of the model target, and the string-to-string matching entails measuring the distance between the two strings based upon deletion, insertion, and substitution of symbols from one string to the other;

so that;

performing the string-to-string matching measures how closely local structural features of the perceived target resemble local structural features of the model target.

2. The method of claim 1 wherein the perceived target is a ship and the compact one-dimensional description of the perceived target'"'"'s boundary covers just upper portions of the ship'"'"'s profile.

3. The method of claim 1 wherein the distance measurement entails solving an algorithm having cyclic loop dependency, in which two nested loops are executed n and m times, respectively, where n and m are the number of elements in the two symbolic strings, respectively;

and

the algorithm is solved in n+m-1 steps by a systolic array comprising many identical cells serially connected to form a chain, so that each cell, except for first and last cells in the chain, is connected only to its two adjacent cells, while the first and last cells in the chain are connected only to their sole adjacent cells;

wherein;

at certain moments during said algorithm solving, more than one cell is activated to perform a part of said solving so that the total time required to solve the algorithm is a linear function of the numbers of times the loops are executed.