Pixel hashing image recognition system

• US 5,875,264 A
• Filed: 09/30/1996
• Issued: 02/23/1999
• Est. Priority Date: 12/03/1993
• Status: Expired due to Term

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Kaman Sciences Corp (ITT, Inc.)
• Inventors: Carlstrom, David L.
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/722,390
• Time in Patent Office: 876 Days
• Field of Search: 382/100, 382/181, 382/276, 382/277, 382/278, 382/218, 345/192, 345/193, 345/517
• US Class Current: 382/181
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/184 by analysing segments intersecting the pattern

Abstract

A character recognition system employs a "hashing" technique of imaged pixels wherein a digital image constituting an array of pixels is divided into a series of sub-arrays. The sub-array digital signal patterns themselves correspond directly to addresses in associated system memories. Each memory address indicates a predetermined set of the possible characters. There is an apparatus for combining the list of possible characters so that signals corresponding to only one character are output.

Claims

1. A system for pattern recognition comprising:

a receiving means receiving a sequence of signals configured in a signal array, including signals denoting an overall pattern;

a configuring means for configuring said signal sequence into a plurality of signal sub-arrays, each of said signal sub-arrays responding to a portion of said overall pattern;

a hashing means for mapping each of said digital pattern signal sub-arrays to an address in an associated memory having a set of stored signals corresponding to possible overall patterns;

a return means for retrieving said possible overall pattern signals from each of said mapped addresses; and

a combining means for combining said retrieved possible overall pattern signals and generating therefrom identification signals indicative of the overall pattern unanimously indicated by the combination of all of said retrieved possible overall pattern signals.

2. The system of claim 1 wherein said signal array comprises signals received from a signal database.

3. The system of claim 1 wherein said possible overall pattern signals identify a plurality of overall patterns, each having signals that correspond to said identified overall pattern.

4. The system of claim 3 wherein said combining means further comprises means for assigning equal weight to each of said possible overall pattern signals such that said identified overall pattern corresponds to the overall pattern identified by all of said memories.

5. The system of claim 3 wherein each of said possible overall pattern signals identify a set of overall patterns and wherein said identified overall pattern corresponds to the intersection set of said overall patterns.

6. The system of claim 1 wherein said overall pattern corresponds to an image formed by digital signals.

7. The system of claim 1 wherein said signal sequence corresponds to an array of digital signals of equivalent received optical pixels and wherein said overall pattern corresponds to an optical image.

8. The system of claim 1 wherein said signal sequence corresponds to an array of digital signal equivalents of received discrete acoustical signals and wherein said overall pattern corresponds to an acoustical image.

9. The system of claim 1 wherein said signal sequence corresponds to an array of digital signal equivalents received at discreet temporal intervals.

10. The system of claim 7 further comprising a means for configuring said pixels in an N by M array.

11. The system of claim 10 further comprising a means for configuring each of said sub-arrays into a dimension 1 by M.

12. The system of claim 10 wherein said sub-array pixel signals comprise 2^M pixel signal digital patterns and each of said signal digital patterns has a unique associated memory address.

13. The system of claim 12 wherein said combining means further comprises a means for associating each of said memory addresses with respective portions of said optical image.

15. The system of claim 10 further comprising a means for configuring each of said sub-arrays into dimension J by K.

16. The system of claim 11 wherein each of said M pixels in said sub-arrays is configured in a sequence of M bits, said system further comprising a merging means for combing each of said M bits, adjacent pixels in a plurality of said sub-arrays and generating a logical "1" signal for a bit should any of said corresponding adjacent pixels correspond to a logical "1".

17. The system of claim 16 wherein each of said sub-arrays are of dimension 1 by M and wherein said comparator compares at least three of said adjacent sub-array signals.

18. The system of claim 10 wherein each of said sub-arrays are linear in dimension and are comprised of pixels randomly selected from said N by M array.

19. The system of claim 10 wherein said sub-arrays ate of dimension 1 by M and are comprised of pixels selected so as to extend said sub-arrays diagonally in relation to said N by M array.

24. The system of claim 1 further comprising a training apparatus for use in assigning, for each of said sub-arrays, signals corresponding to portions of said overall pattern to an address of said associated memory.

25. The system of claim 24 wherein said training apparatus further comprises a means for assigning an address in a one of said memories to a one of said signal sub-array digital patterns.

26. The system of claim 24 wherein said training apparatus further comprises a means for assigning an address in a one of said memories to a new one of said signal sub-array digital patterns should a given signal sub-array digital pattern be determined to be non-identical with known signal sub-array digital patterns.

29. The method of claim 26 further comprising the steps of configuring said identification signals to identify a plurality of overall patterns, each having signals that correspond to said identified overall pattern.

30. The system of claim 24 wherein said training apparatus further comprises a means for combining said signals in a set union operation.

31. The system of claim 1 wherein said combining means further comprises a means for merging during training at each of said sub-arrays, desired new identity memory signals with signals corresponding to prior training of a portion of said overall pattern using a set union operator.

32. The system of claim 1 wherein said hashing means further comprises a means for approximating said digital pattern portion signals to allow more than one of said possible digital pattern portions to be mapped to a memory address.

33. The system of claim 32 wherein said approximating means further comprises a means for truncating values of said digital pattern portion signals.

34. The system of claim 32 wherein said approximating means further comprises a means for increasing said digital pattern portion signals values to a higher value.

35. The system of claim 1 wherein said received signal sequence includes signals indicative of at least two overall patterns, said system further comprising:

a means for identifying, for each of said sub-array memories, all addresses containing signals indicative of a first overall pattern;

a means for identifying, for each of said sub-array memories, all addresses containing signals indicative of a second overall pattern; and

a means for combining said first and second identified sub-array memory addresses to generate new signals for storage at a new address therein to ensure combination with previously generated identification signals.

37. The system of claim 1 wherein said signal receiving means further comprises a means for receiving signals of only two states.

52. The system of claim 1 wherein said signal sequence is serial and wherein said signal sequence receiving means further comprises a plurality of bit registers for mapping said signals into corresponding bit cells.

55. The system of claim 1 wherein said signal sequence comprises digital signals with n bits of grey level, said system further comprising n of said configuring means, n of said means hashing means and n of said combining means respectively configured to generate said identification signals for each of said grey levels, said system further comprising an overall grey level combining means for generating said identification signals from combined signals from said grey levels.

56. The system of claim 1 wherein said signal sequence comprises digital signals with n bits of color, said system further comprising n of said configuring means, n of said means hashing means and n of said combining means respectively configured to generate said identification signals for each of said colors, said system further comprising an overall color combining means for generating said identification signals from combined signals from said colors.

57. The system of claim 1 further comprising a temporal combining means for combining said identification signals from an initial signal array with identification signals from a subsequent signal array.

58. The system of claim 57 wherein said identification signals are indicative of the velocity of said overall pattern.

14. A system for pattern recognition comprising:

a receiving means receiving a sequence of signals configured in a signal array, including signals denoting an overall pattern wherein said signal sequence corresponds to an array of digital signals of equivalent received optical pixels of an optical image;

a configuring means for configuring said signal sequence into a plurality of signal sub-arrays, each of said signal sub-arrays having digital pattern signals corresponding to a portion of said overall pattern wherein said sub-array pixel signal, comprise 2^M pixel signal digital patterns

a means for configuring said pixels in an N by M array;

a hashing means for mapping each of said digital pattern signal sub-arrays to an address in an associated memory having a set of stored signals corresponding to possible overall patterns and each of said signal digital patterns has a unique associated memory address;

a return means for retrieving said possible overall pattern signals from each of said mapped addresses; and

a combining means for combining said retrieved possible overall pattern signals and generating therefrom identification signals indicative of the overall pattern unanimously indicated by the combination of all of said retrieved possible overall pattern signals;

wherein said optical image is one of a plurality of optical images and a means for returning, in dependence on said memory address signal value, signals indicative of at least one of said optical images in said optical image plurality.

20. The system of claim 14 wherein said plurality of optical images respectively correspond to a single selected figure imaged at selected distances from an origin.

21. The system of claim 14 wherein said plurality of optical images respectively correspond to a single selected figure imaged at selected rotational positions as compared to an initial figure position.

22. The system of claim 20 wherein said plurality of optical images correspond to a single selected figure imaged at selected positions rotated about a selected one of a yaw, pitch and roll axis.

23. The system of claim 21 wherein said yaw, pitch and roll axes have their intersection at the center of said object.

43. The system of claim 20 said identification signal generating means further comprises a means for storing a distance variable as a binary coded set with the most significant bit (MSB) having a weight equal to half of a desired dynamic range and the least significant bit (LSB) having a weight equal to a desired accuracy value.

27. A method of pattern recognition comprising the steps of:

receiving a sequence of signals configured in a signal array, including signals denoting an overall pattern;

configuring said signal sequence into a plurality of signal sub-arrays, each of said signal sub-arrays having digital pattern signals corresponding to a portion of said overall pattern;

mapping each of said signal sub-array digital pattern signals to an address in an associated memory having a sequence of stored signals corresponding to possible overall patterns;

retrieving said possible overall pattern signals from each of said mapped addresses; and

combining said retrieved possible overall pattern signals and generating therefrom identification signals indicative of the overall pattern unanimously indicated by the combination of all of said possible overall pattern signals.

28. The method of claim 27 further comprising the steps of configuring said sub-array digital patterns so that each of said sub-array digital patterns correspond to a unique associated address in a memory.

36. The method of claim 27 further comprising the steps of:

identifying, for each of said sub-array memories, all addresses containing signals indicative of a first overall pattern;

identifying, for each of said sub-array memories, all addresses containing signals indicative of a second overall pattern; and

combining said first and second identified subarray memory addresses to generate new signals for storage at a new address therein to ensure combination with previously generated identification signals.

38. A system for pattern recognition comprising:

a receiving means for receiving a sequence of signals configured in a signal array, including signals denoting an overall pattern having a centroid and an area;

a means for configuring said sequence of signals into a plurality of signal sub-arrays, each of said signal sub-arrays having a digital pattern corresponding to a portion of said overall pattern area;

a hashing means for mapping each of said signal sub-array digital patterns to an address in an associated memory having a set of stored signals corresponding to numeric values respectively providing area, horizontal moment and vertical moment contribution signals for each of said memory addresses;

a return means for retrieving said stored signals from each of said mapped addresses; and

a combining means for combining said retrieved memory address signals and generating therefrom moment signals indicative of the horizontal and vertical components of said centroid.

39. The system of claim 38 further comprising a means for configuring said sub-arrays to be of n by n dimension.

41. The system of claim 38 further comprising a means for configuring said sub-arrays to be of 1 by n dimension.

42. The system of claim 38 further comprising a means for arranging said signal sub-array plurality about a center of said array such that each of said pixels in said array index away from said array center toward an array perimeter.

40. A system for pattern recognition comprising:

a receiving means for receiving a sequence of signals configured in a signal array, including signals denoting an overall pattern having a centroid and an area;

a means for configuring said sequence of signals into a plurality of signal sub-arrays, each of said signal sub-arrays having a digital pattern corresponding to a portion of said overall pattern area;

a hashing means for mapping each of said signal sub-array digital patterns to an address in an associated memory having a set of stored signals corresponding to numeric values respectively providing area, horizontal moment and vertical moment contribution signals for each of said memory addresses;

a return means for retrieving said stored signals from each of said mapped addresses; and

a combining means for combining said retrieved memory address signals and generating therefrom moment signals indicative of the horizontal and vertical components of said centroid wherein said combining means further comprises;

a means for summing said area moment signals and generating a total area signal;

a means for summing said moment signals indicative of vertical component of said centroid and generating a total vertical component signal;

a means for summing said moment signals indicative of horizontal component of said centroid and generating a total horizontal component signal;

a means for dividing said total area signal by said total vertical area signal and generating a vertical centroid signal; and

a means for dividing said total area signal by said total horizontal area signal and generating a horizontal centroid signal.

44. A rank order signal filter system comprising:

a means for receiving a sequence of signals in one of two signal states, including signals denoting an overall pattern and noise signals corresponding to signals having a state opposite a desired state;

a means for configuring a selected portion of said signals into a signal sampling array having a central signal element,

a means for configuring said signal array into a plurality of signal sub-arrays, each of said signal sub-arrays having digital pattern signals corresponding to a portion of said overall pattern;

a hashing means for mapping each of said digital pattern signal sub-arrays to an address in an associated memory having a set of stored signals indicative of a numeric value corresponding to the number of elements of said sub-array in a selected one of said signal states;

a return means for retrieving said stored signals from each of said mapped addresses; and

a combining means for combining said retrieved memory address signals and generating therefrom signals adjusting the state of said center element in dependence on the numeric values said array elements.

45. The system of claim 44 wherein said signal sampling array is of even dimension.

46. The system of claim 44 further comprising a means for advancing said sampling array through said sequence of signals element by element and adjusting said center element state at each element.

47. The system of claim 44 further comprising a thresholding means for adjusting the state of said center element only if the numeric value indicated by said memory address signals exceeds a threshold.

48. The system of claim 47 wherein said elements correspond to pixels and wherein said thresholding means adjusts said center pixel state to an enabled state if at least one half of said pixels in said array have an enabled state.

49. The system of claim 44 further comprising a training means for storing in said memory addresses numeric signals indicative of the total number of enabled elements in a corresponding sub-array.

50. The system of claim 49 further comprising:

a means for generating, from said subarray, total number signals, signals indicative of the sum total of enabled elements in said array; and

a comparing means for comparing said sum total signals with a threshold value and adjusting said center pixel state should said sum total signals exceed said threshold value.

51. An electrical circuit for use in a pattern recognition system, said circuit comprising:

a means for receiving a serial sequence of pixel signals, including signals denoting an overall pattern;

a means for configuring said signal sequence into a plurality of signal sub-arrays, each of said signal sub-arrays having digital pattern signals corresponding to a portion of said overall pattern;

a hashing means for mapping each of said digital pattern signal sub-arrays to an address in an associated memory having a set of stored signals corresponding to numeric values respectively providing area, horizontal moment and vertical moment contribution signals for each of said memory addresses;

a return means for retrieving said stored signals from each of said mapped addresses; and

a combining means for combining said retrieved stored signals of said memory addresses and generating therefrom moment signals indicative of the horizontal and vertical components of said centroid.

53. A system for pattern recognition comprising:

a receiving means having a plurality of bit registers for mapping said signals into corresponding bit cells for receiving a sequence of serial signals configured in a signal array, including signals denoting an overall pattern;

a configuring means for configuring said signal sequence into a plurality of signal sub-arrays, each of said signal sub-arrays having digital pattern signals corresponding to a portion of said overall pattern;

a hashing means for mapping each of said digital pattern signal sub-arrays to an address in an associated memory having a set of stored signals corresponding to possible overall patterns, said hashing means further comprises a plurality of memory banks configured to receive said signal sequence in parallel;

a return means for retrieving said possible overall pattern signals from each of said mapped addresses; and

a combining means for combining said retrieved possible overall pattern signals and generating therefrom identification signals indicative of the overall pattern unanimously indicated by the combination of all of said retrieved possible overall pattern signals.

54. The system of claim 53 wherein said signal sequence comprises pixel signals and wherein the number of addresses in said memory banks is greater than the number of pixels in said signal array;

said combining means further comprising adder circuitry for logically combining output signals from said memory banks and comparator means for logically comparing said adder circuitry signals to a threshold signal and generating logical "1" output signals should said adder circuitry signals exceed said threshold.