Pattern processing system

• US 4,541,115 A
• Filed: 02/08/1983
• Issued: 09/10/1985
• Est. Priority Date: 02/08/1983
• Status: Expired due to Term

• Current Assignee: Electro-Sensors Inc
• Original Assignee: Pattern Processing Technologies, Inc. (Datalogic S.p.A.)
• Inventors: Werth, Larry J.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/465,008
• Time in Patent Office: 945 Days
• Field of Search: 382/7, 382/10, 382/14, 382/15, 382/37, 382/41, 382/49, 382/23, 364/513, 364/488-491, 358/101, 358/107
• US Class Current: 382/159
• CPC Class Codes: G06T 7/00 Image analysis
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: G08B 13/194 using image scanning and comparing systems

Abstract

A pattern processing system associates image input patterns with desired response codes. The image input is stored in an image buffer as an addressable array of sample values. An address sequencer provides a sequence of addresses (or "address stream") to the image buffer and to a response memory. The next address provided by the address sequencer is based upon the current address and the state of the sample value stored in the image buffer at the location corresponding to the current address. Once the address sequencer repeats an address, the address stream is in a repetitive address loop as long as the image stored in the image buffer remains constant. The address loop continues to be generated, since the address sequencer always produces the same next address based upon the same current address and the same sample value stored at that current address. During a training mode, a pattern to be recognized is supplied to the image buffer and a training code representing a desired response is written into the response memory at selected locations that correspond to addresses in the address loop being generated. During a later recognition mode, when the same pattern is supplied to the image buffer, the same address loop is again generated. The previously stored training codes are read from the response memory. A response detector provides a response code output representative of the pattern based upon the most frequent code read out from the response memory.

Claims

1. A method of associating an input pattern with an output response, wherein the input pattern comprises a plurality of sample values, the method comprising:

producing the sample values based upon the input pattern;

storing the sample values of the input pattern in a first array of addressable locations;

sequentially addressing the first array with a sequence of addresses in which each next address of the sequence is determined by a preceding address of the sequence and the sample value stored at the addressable location of the first array corresponding to the preceding address, so that a repetitive address loop which is a function of the input pattern is generated as long as the input pattern remains unchanged; and

associating the output response with the address loop which is a function of the input pattern.

2. The method of claim 1 wherein associating the output response with the address loop comprises:

sequentially addressing a second array of addressable locations with the sequence of addresses;

storing a code representative of the output response at selected locations of the second array which are addressed by the sequence of addresses;

reading codes from the locations of the second array addressed by the sequence of addresses; and

providing the output response based upon the codes read from the second array.

3. The method of claim 1 wherein each next address of the sequence has a plurality of possible address values based upon the preceding address, and wherein the next address is selected from among the possible address values based upon a sample value related to the preceding address.

4. The method of claim 3 wherein each next address of the sequence has a plurality of possible address values based upon the preceding address, and wherein the next address is selected from among the possible address values based upon a sample value related to the preceding address.

9. The pattern processing system of claim 1 wherein the means responsive to the address stream comprises:

response memory means for storing codes in a second array of locations addressable by the address stream;

training controller means for selectively causing a predetermined training code to be associated with a selected input pattern to be written into the response memory means at locations of the second array addressed by the address stream when the selected input pattern is addressed by the address sequencer means; and

response detector means for providing an an output response based upon codes read out from locations of the second array addressed by the address stream.

10. The pattern processing system of claim 9 wherein the response detector means provides the output response based upon frequency of the codes read out from the response memory means.

5. A method of associating a pattern with an output response, the method comprising:

sequentially sampling elements of the pattern to produce sample values representative of a characteristic of the elements sampled, the elements sampled being selected by a sequence of addresses in which each next address of the sequence is determined by a preceding address of the sequence and the sample value corresponding to the preceding address, so that a repetitive address loop which is a function of the pattern is generated as long as the pattern remains unchanged; and

associating the output response with the address loop which is a function of the pattern.

6. The method of claim 5 wherein associating the output response with the address loop comprises:

sequentially addressing a response memory with the sequence of addresses;

storing a code representative of the output response at selected locations of the response memory which are addressed by the sequence;

reading codes from locations of the response memory which are addressed by the sequence; and

providing the output response based upon the codes read from the response memory.

7. A method of associating an input pattern with an output response, wherein the input pattern comprises a plurality of sample values, the method comprising:

periodically storing the sample values of the input pattern at a first rate in a first array of addressable locations;

sequentially addressing the first array at a second higher rate with a sequence of addresses in which each next address of the sequence is determined by a preceding address of the sequence and the sample value stored at the addressable location of the first array corresponding to the preceding address, so that a repetitive address loop which is a function of the input pattern is generated as long as the input pattern remains unchanged; and

associating the output response with the address loop which is a function of the input pattern.

8. A pattern processing system for identifying an input pattern comprising:

addressable means for providing, for each of a plurality of addressable locations, a sample value representative of a characteristic of an input pattern at that addressable location;

address sequencer means for providing an address stream containing a sequence of addresses in which each next address of the sequence is determined by a preceding address and the sample value from the location corresponding to the preceding address;

so that upon repetition of an address which has previously been provided in the sequence, the address stream cycles repetitively through an address loop which is a function of the input pattern for as long as the input pattern remains unchanged; and

means responsive to the address stream for identifying the input pattern based upon the address loop which it causes to be provided by the address sequencer means.

11. The pattern processing system of claim 8 wherein each next address of the sequence provided by the address sequencer means has a plurality of possible values based upon the preceding address, and wherein the sample value from the location corresponding to the preceding address determines which of the plurality of possible values is provided by the address sequencer means as the next address.

12. The pattern processing system of claim 11 wherein the address sequencer means comprises:

a plurality of address sequencers, each address sequencer providing a sequence of addresses in which the next address of the sequence has a plurality of possible values depending on a preceding address provided by the address sequencer, and in which the sample value from the preceding address provided by the address sequencer determines which of the plurality of possible values is provided as the next address, so that each address sequencer of the plurality generates an address loop which is a function of the input pattern; and

means for interleaving the sequence of addresses from the plurality of address sequences to produce the address stream.

13. The pattern processing system of claim 8 and further comprising:

means for modifying the address stream from the address sequencer means and providing the modified address stream to the addressable means.

14. The pattern processing system of claim 13 wherein the means for modifying the address stream comprises:

scaling means for scaling the addresses of the address stream.

15. The pattern processing system of claim 13 wherein the means for modifying the address stream comprises:

translation means for translating the addresses of the address stream.

17. A pattern processing system for identifying combinations of first and second input patterns, the system comprising:

first addressable means for providing first sample values representative of the first input pattern at a plurality of addressable locations;

second addressable means for providing second sample values representative of the second input pattern at a plurality of addressable locations;

first address sequencer means for providing a first address stream to the first addressable means, the first address stream containing a sequence of addresses in which each next address of the sequence is determined by a preceding address and the first sample value from the location corresponding to the preceding address;

second address sequencer means for providing a second address stream to the second addressable means, the second address stream containing a sequence of addresses in which each next address of the sequence is determined by a preceding address and the second sample value from the location corresponding to the preceding address; and

means for identifying combinations of the first and second input patterns based upon the first and second streams.

16. The pattern processing system of claim 18 wherein the means responsive to the address stream comprises:

signature analysis circuit means for converting the address loops contained in the address stream to output codes.

18. The pattern processing system of claim 17 wherein the means for identifying comprises:

third addressable means for storing third sample values representative of a third input pattern at a plurality of addressable locations, the third sample values being based upon the addresses combined in the first and second address streams;

third address sequencer means for providing a third address stream containing a sequence of addresses in which each next address of the sequence is determined by a preceding address and the third sample value from the location corresponding to the preceding address; and

means responsive to the third address stream for identifying combinations of the first and second input patterns based upon repetitive address loops contained in the third address stream.

19. A pattern processing system comprising:

first addressable means for storing at a plurality of addressable locations sample values representative of an input pattern during a first temporal interval;

first address sequencer means for providing a first address stream containing a sequence of addresses in which each next address of the sequence is determined by the preceding address and the first sample value from a location of the first addressable means corresponding to the preceding address, so that upon repetition of an address which has previously been provided in the sequence, the address stream cycles repeatedly through an address loop which is a function of the input pattern;

second addressable means for storing at a plurality of addressable locations an array of second sample values representative of addresses contained in the first address stream during a second temporal interval which includes a plurality of first temporal intervals;

second address sequencer means for providing a second address stream containing a sequence of addresses in which each next address of the sequence is determined by a preceding address and the second sample value from the location corresponding to the preceding address, so that upon repetition of an address which has previously been provided in the sequence, the address stream cycles repetitively through an address loop which is a function of the array of second samle values; and

means responsive to the second address stream for identifying the input pattern during the second temporal interval based upon an address loop contained in the second address stream.

20. A pattern processing system for identifying a pattern, the system comprising:

means for generating an address stream containing at least one sequence of addresses in which each next address of the sequence has a plurality of possible next address values based upon at least one preceding address, and wherein the next address is selected from among the possible next address values based upon at least one sample value related to the one preceding address so that at least one repetitive address loop which is a function of the pattern is generated;

means for providing, in response to each address of the address stream, a sample value representative of a characteristic of a sampled element of a pattern corresponding to that address; and

means for identifying the pattern based upon the sequence of addresses generated when the pattern is sampled as a function of addresses of the address stream.

21. The pattern processing system of claim 20 wherein the means for providing sample values comprises:

source means for providing sample values representative of the characteristics of the sampled elements of a pattern; and

buffer means for storing the sample values in a first array of locations addressable by the address stream, the buffer means providing the sample values to the means for generating the address stream in response to the address stream.

22. The pattern processing system of claim 20 wherein the means for identifying the pattern comprises:

response memory means for storing codes in locations addressable by the address stream;

training controller means for selectively causing a predetermined training code associated with the pattern to be written into the response memory means at locations addressed by the address stream when the pattern is addressed by the address sequencer means; and

response detector means for providing an output response based upon codes read out from locations of the response memory means addressed by the address stream.

23. The pattern processing system of claim 22 wherein the response detector means provides the output response based upon frequency of the codes read out from the response memory means.

24. A pattern processing system for associating an input pattern comprising a plurality of sample values with an output response, the system comprising:

buffer means for storing the sample values of the input pattern in a first array of addressable locations;

response memory means for storing codes in a second array of addressable locations;

address sequencer means for providing a sequence of addresses, a next address of the sequence being determined by a preceding address and the sample value stored by the buffer means at the location corresponding to the preceding address;

so that upon repetition of an address which has been previously provided, the sequence of addresses cycles repetitively through an address loop which is a function of the input pattern;

training controller means for selectively causing a predetermined code associated with the input pattern to be written into the response memory means at locations of the second array determined by the addresses of an address loop produced when the input pattern is stored by the buffer means and addressed by the address sequencer means; and

response detector means for providing the output response based upon codes read out from locations of the second array addressed by the sequence of addresses provided by the address sequencer means.

25. The system of claim 24 and further comprising:

means for modifying the addresses provided by the address sequencer means and providing a sequence of modified addresses to the buffer means.

26. The system of claim 25 wherein the means for modifying comprises:

scaling means for modifying the addresses provided by the address sequencer means by a scaling factor.

27. The system of claim 25 wherein the means for modifying comprises:

translation means for modifying the addresses provided by the address sequencer means by a translation factor.

28. A pattern processing system for associating an input pattern comprising a plurality of sample values with an output response during a training mode and subsequently providing the output response when the input pattern is present during a subsequent identifying mode, the system comprising:

means for storing sample values of the input pattern in a first array of addressable locations;

means for storing codes in a second array of addressable locations;

means for providing a sequence of addresses corresponding to addressable locations of the first and second arrays, a next address of the sequence being determined by a preceding address of the sequence and the sample value stored at the location at the first array corresponding to the preceding address;

so that upon repetition of an address which has been previously provided, the sequence of addresses cycles repetitively through an address loop which is a function of the input pattern and which includes a plurality of addresses, as long as the input pattern remains unchanged;

means for causing a predetermined code representative of the output response to be stored at selected locations of the second array determined by the addresses of the address loop produced during the training mode when the sample values of the input pattern are stored in the first array and are addressed by the sequence of addresses; and

means for providing the output response based upon the codes read out from locations of the second array addressed by the sequence of addresses generated during the identifying mode when the sample values of the input pattern are stored in the first array and are addressed by the sequence of addresses.

29. A pattern processing system for associating an input pattern comprising a plurality of sample values with an output response, the system comprising:

buffer means for storing the sample values of the input pattern in a first array of addressable locations, the sample values stored being updated at a first rate;

response memory means for storing codes in a second array of addressable locations;

address sequencer means for providing a sequence of addresses at a second rate which is greater than the first rate, a next address of the sequence being determined by a preceding address and the sample value stored by the buffer means at the location corresponding to the preceding address;

so that upon repetition of an address which has been previously provided, the sequence of addresses cycles repetitively through an address loop which is a function of the input pattern;

training controller means for selectively causing a predetermined code associated with the input pattern to be written into the response memory means at locations of the second array determined by the addresses of an address loop produced when the input pattern is stored by the buffer means and addressed by the address sequencer means; and

response detector means for providing the output response based upon codes read out from locations of the second array addressed by the sequence of addresses provided by the address sequencer means.

30. A pattern processing system for associating an input pattern comprising a plurality of sample values with an output response during a training mode and subsequently providing the output response when the input pattern is present during a subsequent identifying mode, the system comprising:

means for periodically storing, at a first rate, sample values of the input pattern in a first array of addressable locations;

means for storing codes in a second array of addressable locations;

means for providing a sequence of addresses corresponding to addressable locations of the first and second arrays at a second rate which is greater than the first rate, a next address of the sequence being determined by a preceding address of the sequence and the sample value stored at the location at the first array corresponding to the preceding address;

so that upon repetition of an address which has been previously provided, the sequence of addresses cycles repetitively through an address loop which is a function of the input pattern and which includes a plurality of addresses, as long as the input pattern remains unchanged;

means for causing a predetermined code representative of the output response to be stored at selected locations of the second array determined by the addresses of the address loop produced during the training mode when the sample values of the input pattern are stored in the first array and are addressed by the sequence of addresses; and

means for providing the output response based upon the codes read out from locations of the second array addressed by the sequence of addresses generated during the identifying mode when the sample values of the input pattern are stored in the first array and are addressed by the sequence of addresses.