Pattern matching method with pixel vectors

• US 5,708,731 A
• Filed: 07/02/1996
• Issued: 01/13/1998
• Est. Priority Date: 08/09/1993
• Status: Expired due to Fees

• Current Assignee: Nireco Corporation
• Original Assignee: Nireco Corporation
• Inventors: Kobayashi, Kiyoo, Shimotori, Akira
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/676,098
• Time in Patent Office: 560 Days
• Field of Search: 382/197, 382/205, 382/194, 382/209
• US Class Current: 382/205
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G06V 10/70 using pattern recognition or machine learning optical pattern recognition or electronic computations therefor G06V10/88
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/184 by analysing segments intersecting the pattern

Abstract

Each of a certain number of sequences of binary pixels chosen according to some prescribed rules from m×n matrix of pixcels is referred to vector v_i. A standard character k is represented with m×n matrix of binary pixels, from which the vectors g_ki are derived. The reference vectors G_ki are comprised of the vectors g_ki and g_ki which are generated by modification of g_ki. A recognition object is captured to yield m×n matrix of binary pixels, from which the vectors v_i are derived for comparison with the reference vectors G_ki. Matching of v_i with one of the reference vectors G_ki adds a count to the standard pattern k corresponding to G_ki. The standard character k with the maximum score of the matching count is recognized as the recognition object.

Claims

1. A method for matching a pattern with one of a plurality of standard samples comprising the steps of:

representing a recognition image captured from a recognition-objected sample by an m×

n matrix of binary pixels forming a binary image, where each of m and n is an integer;

forming a plurality of M pixel trains v_i by choosing, from said m×

n matrix of binary pixels, a consecutive sequence of binary pixels according to prescribed rules for each pixel train v_i, where i is an index having integer values in a range between 1 and a predetermined integer M;

choosing a predetermined subset of said pixel trains v_i of said binary pixels;

matching each of said chosen subset of pixel trains v_i to reference pixel trains G_ki respectively corresponding thereto for each of a plurality of N standard samples, where k is an index having integer values between 1 and a predetermined integer N;

wherein said reference pixel trains G_ki are formed by obtaining a cluster of pixel trains g_ki from N m×

n pixel matrices each representing a respective standard image for a standard sample k, and by generating multiplex pixel trains g_ki, by performing a predetermined systematic modification of pixels in said pixel trains g_ki to form, together with said pixel trains g_ki, said reference pixel trains G_ki ;

maintaining a score for each standard sample k of said N standard samples in accordance with a number of matches between said reference pixel trains G_ki thereof and the corresponding chosen subset of pixel trains v_i, and

identifying a particular one of said N standard samples as matching said recognition-objected sample when said particular standard sample has a maximum score of said scores maintained for said standard samples.

2. A method in accordance with claim 1, wherein said step of maintaining a score comprises adding a predetermined amount to the score of any standard sample k of said N standard samples when a particular pixel train G_ki thereof matches a corresponding one of said chosen subset of pixel trains v_i.

3. A method in accordance with claim 2 wherein, for a certain number of pixel trains in said subset of pixel trains, said step of choosing a consecutive sequence of binary pixels comprises choosing consecutive sequences of said pixels according to said prescribed rules from m rows in said m×

n matrix of binary pixels representing said recognition image.

4. A method in accordance with claim 2 wherein, for a certain number of pixel trains in said subset of pixel trains, said step of choosing a consecutive sequence of binary pixels comprises choosing consecutive sequences of said pixels according to said prescribed rules from n columns in said m×

n matrix of binary pixels representing said recognition image.

5. A method in accordance with claim 2 wherein, for a certain number of pixel trains in said subset of pixel trains, said step of choosing a consecutive sequence of binary pixels comprises choosing according to said prescribed rules a series of pixels in a line at an angle of 45°

in said m×

n matrix of binary pixels representing said recognition image.

6. A method in accordance with claim 2 wherein, for a certain number of pixel trains in said subset of pixel trains, said step of choosing a consecutive sequence of binary pixels comprises choosing according to said prescribed rules a series of pixels, in arbitrary position, number, and order, from feature parts of said recognition-objected sample in said m×

n matrix of binary pixels representing said recognition image.

7. A method in accordance with claim 2 wherein, for a certain number of pixel trains in said subset of pixel trains, said step of choosing a consecutive sequence of binary pixels comprises choosing according to said prescribed rules, a combination of at least two groups of pixels, in rows chosen from m rows in said m×

n matrix of binary pixels representing said recognition image and in columns chosen from n columns in said m×

n matrix of binary pixels representing said recognition image, choosing a series of pixels in a line at an angle of 45°

in said m×

n matrix of binary pixels representing said recognition image, and choosing a series of pixels in arbitrary position, number, and order from feature parts of said recognition-objected sample in said m×

n matrix of binary pixels representing said recognition image.

8. A method in accordance with claim 2, comprising the step of providing a plurality of standard images including original images for each of said standard samples under a predetermined capture condition and additional images for each of said standard samples under various capture conditions differing from said predetermined capture condition, and the step of forming said reference pixel trains for each of the plurality of standard images.

9. A method in accordance with claim 2, comprising the step of providing said predetermined systematic modification of constituent pixels in said pixel trains by changing a number of pixels in a segment of a pixel train which includes a continuous series of pixels of a single binary value.

10. A method in accordance with claim 1, wherein said step of obtaining a cluster of pixel trains g_ki of said reference pixel trains G_ki from said N pixel matrices representing said standard images comprises choosing consecutive sequences of binary pixels from said N pixel matrices according to said prescribed rules used for forming the respectively corresponding pixel trains v_i from said matrix representing said recognition image.

11. A method for matching a pattern with one of a plurality of standard samples comprising the steps of:

representing a recognition image captured from a recognition-objected sample by an m×

n matrix of binary pixels forming a binary image, where each of m and n is an integer;

forming a plurality of M pixel trains v_i by choosing, from said m×

n matrix of binary pixels, a consecutive sequence of binary pixels according to prescribed rules for each pixel train v_i, where i is an index having integer values in a range between 1 and a predetermined integer M;

choosing a predetermined subset of said pixel trains v_i of said binary pixels;

matching each of said chosen subset of pixel trains v_i to reference pixel trains G_ki respectively corresponding thereto for each of a plurality of N standard samples, where k is an index having integer values between 1 and a predetermined integer N;

wherein said reference pixel trains G_ki are formed by obtaining a cluster of pixel trains g_ki from N m×

n pixel matrices each representing a respective standard image for a standard sample k, and by generating multiplex pixel trains g_ki '"'"' by performing a predetermined systematic modification of pixels in said pixel trains g_ki to form, together with said pixel trains g_ki, said reference pixel trains G_ki ;

maintaining a score for each standard sample k of said N standard samples in accordance with a number of matches between said reference pixel trains G_ki thereof and the corresponding chosen subset of pixel trains v_i, by;

i) adding a predetermined amount to the score of any standard sample k of said N standard samples when a particular pixel train G_ki thereof matches a corresponding one of said chosen subset of pixel trains v_i, and

ii) subtracting a predetermined amount from the score of any standard sample k of said N standard samples when a particular pixel train G_ki thereof never matches a corresponding one of said chosen subset of pixel trains v_i,

and

identifying a particular one of said N standard sample as matching and representing said recognition-objected sample when said particular standard sample has a maximum score of said scores maintained for said standard samples.

12. In a method for matching a recognition object with one of a plurality of N standard patterns where N is an integer, implemented on an apparatus including means for capturing the recognition object, binarizing and normalizing the recognition object and forming a matrix of binary pixels representing a binary image of the recognition object, improvement comprising:

generating input signals corresponding to a plurality of input pixel trains v_i, said input signals for each input pixel train representing a respective consecutive sequence of binary pixels selected in accordance with prescribed rules from said matrix, where i is an index having integer values greater than 1,

producing reference signals corresponding to reference pixel trains G_ki of a kth one of said plurality of standard patterns, where k is an integer between 1 and N, said reference pixel trains representing sequences of binary pixels from matrices representing binary images of the standard patterns respectively corresponding to said sequences of binary pixels selected from said matrix representing the recognition object, by;

a) obtaining first signals corresponding to a cluster of pixel trains g_ki from said N pixel matrices each representing a respective standard image for a standard sample k, and

b) obtaining second signals corresponding to multiplex pixel trains g_ki '"'"' by performing a predetermined systematic modification of said first signals for pixels to form, together with said first signals, said reference signals corresponding to said reference pixel trains G_ki ;

generating output signals representing matches between said input signals, corresponding to said input pixel trains v_i of the recognition object, and reference signals corresponding to reference pixel trains G_ki

maintaining a score for each of said plurality of N standard patterns in accordance with a number of matches occurring between said input pixel trains v_i and said reference pixel trains G_ki thereof, and

providing an output signal identifying a particular one of said standard patterns as matching said recognition object when said particular standard sample has a maximum score of said scores maintained for said N standard patterns.

13. In an apparatus for matching a recognition object with one of a plurality of N standard patterns including means for capturing the recognition object, where N is an integer, and for binarizing and normalizing the recognition object and forming an m×

n matrix of binary pixels representing a binary image of the recognition object, the improvement comprising;

a first circuit having an input for receiving input signals representing a plurality of input pixel trains v_i, each input pixel train representing a respective consecutive sequence of binary pixels selected in accordance with prescribed rules from said m×

n matrix, where i is an index having integer values greater than 1,

said first circuit having an output for outputting signals representing matches between each input pixel train v_i of the recognition object, representing a sequence of pixels from said m×

n matrix, and corresponding reference pixel trains G_ki of a kth one of said plurality of standard patterns, representing respectively corresponding sequences of binary pixels from matrices representing binary images of the standard patterns, where k is an integer between 1 and N,

wherein said reference pixel trains G_ki comprise;

a) a cluster of first pixel trains g_ki, from N m×

n matrices each representing a respective kth binary image, for a kth standard pattern, and

b) multiplex pixel trains g_ki '"'"', generated by predetermined systematic modification of constituent pixels in said first pixel trains g_ki,

a second circuit for maintaining a score for each of said plurality of N standard patterns in accordance with a number of matches between said input pixel trains v_i and said reference pixel trains G_ki thereof, and

a selector for identifying a particular one of said standard patterns as matching and representing said recognition object when said particular standard sample has a maximum score of said scores maintained for said N standard patterns.

14. An apparatus in accordance with claim 13, wherein said second circuit for maintaining a score comprises means for adding a predetermined amount to the score of a kth standard pattern when a particular pixel train G_ki thereof matches a respectively corresponding one of said input pixel trains v_i.

15. An apparatus in accordance with claim 14, wherein said second circuit for maintaining a score further comprises means for subtracting a predetermined amount from the score of a kth standard pattern when a particular pixel train G_ki thereof never matches a respectively corresponding one of said input pixel trains v_i.

16. An apparatus in accordance with claim 13, wherein said second circuit for maintaining a score comprises a plurality of N adders corresponding to said N standard patterns, each adder maintaining a kth score, for a kth standard pattern, by incrementing the kth score in response to a match between a particular pixel train G_ki of said kth standard pattern and a respectively corresponding one of said input pixel trains v_i.

17. An apparatus in accordance with claim 13, wherein said first circuit comprises a memory having a plurality of storage locations, each storage location identified by an address, wherein said input receives a multi-bit input pixel train v_i as an address, and wherein a storage location of said memory identified by an address v_i stores identifications of any values of k identifying matching standard patterns which include a reference pixel train G_ki which matches said input pixel train v_i, said output of said memory outputting signals representing said values of k for said matching standard patterns.

18. An apparatus in accordance with claim 13, further comprising a logic circuit for generating said pixel trains v_i from said binary pixels of said m×

n matrix, including;

a) pixel train decoding means for receiving as an input a pixel train identification number i and for providing an output signal on one of a plurality of output lines;

b) a plurality of first gates, each of said first gates connected for receiving an input value representing a particular binary pixel from a particular position in said m×

n matrix,

c) a plurality of second gates receiving outputs from said first gates for outputting a pixel train v_i for said m×

n matrix in response to input of said pixel train identification number i to said pixel train decoding means;

wherein each of said output lines from said pixel train decoding means is connected for enabling a set of said first gates selected in accordance with said prescribed rules to transmit respective input values of binary pixels inputted thereto to said second gates.

19. An apparatus in accordance with claim 18, further comprising a pixel train counter for generating a sequence of pixel train identification numbers in response to a clock signal,

wherein said pixel train decoding means and said first circuit are each connected for receiving said pixel train identification numbers from said pixel train counter, thereby to provide said input pixel train v_i and said pixel train identification number i to said first circuit substantially simultaneously.

20. An apparatus in accordance with claim 19, wherein said second circuit and said pixel train counter are each connected to be clocked by said clock signal, thereby synchronizing said second circuit with said signal representing matches outputted from said first circuit.

21. An apparatus in accordance with claim 20, wherein said first circuit comprises a memory having a plurality of storage locations, each storage location identified by an address, wherein said input receives a multi-bit input pixel train v_i as an address, and wherein a storage location of said memory identified by an address v_i stores identifications of any values of k identifying matching standard patterns which include a reference pixel train G_ki which matches said input pixel train v_i, said output of said memory outputting signals representing said values of k for said matching standard patterns, and

said second circuit comprises a plurality of N adders corresponding to said N standard patterns, each adder maintaining a kth score, for a kth standard pattern, by incrementing the kth score in response to an output from said a match between a particular pixel train G_ki of said kth standard pattern and a respectively corresponding one of said input pixel trains v_i.