Pattern identification system

• US 4,228,421 A
• Filed: 03/22/1979
• Issued: 10/14/1980
• Est. Priority Date: 03/28/1978
• Status: Expired due to Term

• Current Assignee: Tokyo Shibaura Denki Kabushiki Kaisha (Toshiba Corporation)
• Original Assignee: Tokyo Shibaura Denki Kabushiki Kaisha (Toshiba Corporation)
• Inventors: Asada, Haruo
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/022,875
• Time in Patent Office: 572 Days
• Field of Search: 340/146.3 MA, 340/146.3 AG, 340/146.3 AC, 340/146.3 H, 364/725, 364/728, 364/731
• US Class Current: 382/209
• 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

Abstract

A covariance matrix of a set of m number of column components of a two-dimensional input pattern and a covariance matrix of a set of n number of row components are obtained. The column covariance matrix and a column covariance matrix of a set of column components of a standard pattern belong to the corresponding one of various categories are multiplied and summed to obtain a column multiply-sum data and the row covariance matrix and a row covariance matrix of a set of row components of the standard pattern are multiplied and summed to obtain row multiply-sum data. The column and row multiply-sum data are multiplied by a multiplier to obtain product data. A maximum detector detects a maximum product data from the product data obtained by the multiplier with respect to all categories. The category corresponding to the maximum product data is recognized as belonging to the input pattern.

Claims

1. A pattern identification system comprising memory means for storing a plurality of standard pattern data each calculated based on covariance matrix of a set of pattern components known to belong to a corresponding one of a plurality of categories;

calculation means for obtaining an input pattern data based on covariance matrix of a set of pattern components of an input pattern;

multiplier-adder means for multiplying and summing the element included in the covariance matrix of the input pattern data and the corresponding element of the covariance matrix of each standard pattern data;

detection means for detecting the largest of the results obtained by the multiplier-adder means with respect to all categories; and

identification means for identifying the input pattern as belonging to the category represented by the largest result detected by the detection means.

2. A pattern identification system comprising memory means for storing a plurality of standard column pattern data each calculated based on covariance matrix of a set of column pattern components of a two-dimensional pattern known to belong a corresponding one of each of a plurality of categories and a plurality of standard row pattern data each calculated based on covariance matrix of a set of row pattern components of the two-dimensional pattern;

calculation means for obtaining a column covariance matrix data representing covariance matrix of a set of column pattern components of a two-dimensional input pattern and a row column covariance matrix data representing covariance matrix of a set of row pattern components of the two-dimensional input pattern;

multiplier-adder means for multiplying and summing the column covariance matrix data corresponding to the standard and input column pattern components to obtain column multiply-sum data and multiplying and summing the row covariance matrix data corresponding to the standard and input row pattern components to obtain row multiply-sum data;

means for multiplying the column multiply-sum data and the row multiply-sum data, respectively, to obtain product data;

detecting means for detecting a product data repesenting a maximum from the product data obtained by the multiplying means with respect to all categories; and

identification means for identifying the two-dimensional input pattern as belonging to the category represented by the maximum product data detected by the detection means.

3. A pattern identification system according to claim 2, wherein said calculation means comprises m number of n-bit shift registers for storing m number of column pattern component data corresponding to m number of column pattern components of a two-dimensional input pattern;

n number of m-bit shift registers for storing n number of row pattern component data corresponding to n number of row pattern components of the two-dimensional input pattern;

a column covariance matrix calculation circuit for receiving at a time two column pattern component data from the n-bit shift registers so as to obtain covariance matrix of the two column pattern component data;

a row covariance matrix calculation circuit for receiving at a time two row pattern component data from the m-bit shift registers so as to obtain covariance matrix of the two row pattern component data; and

memory means connected to the column and row covariance matrix calculation circuits for storing the column and row cavariance matrix data obtained by the column and row covariance matrix calculation circuits.

4. A pattern identification system according to claim 2, wherein said multiplier-adder means comprises a column multiplier circuit for multiplying the column covariance matrix data with each standard column pattern data;

a column adder circuit for summing the outputs of the column multiplier circuit;

a row multiplier circuit for multiplying the row covariance matrix data with each standard row pattern data; and

a row adder circuit for summing the outputs of the row multiplier circuit.

5. A pattern identification system according to claim 2, wherein said memory means includes a summing circuit for summing covariance matrix data corresponding to all two-dimensional patterns known to belong to each category;

a norm calculation circuit connected to the summing circuit for obtaining the norm of the covariance matrix data;

a divider circuit for dividing the product of the multiplication by the summing circuit by the norm obtained by the norm calculation circuit; and

a memory for storing the output of the divider circuit as a standard pattern data.

6. A pattern identification system for identifying an input pattern constituted by m number of column pattern components and n number of row pattern components, compring an input pattern covariance matrix calculation unit including m number of n-bit shift registers for storing m number of column pattern component data corresponding to the column pattern components, n number of m-bit shift registers for storing n number of row pattern component data corresponding to the row pattern components, a column covariance matrix calculation circuit for receiving at a time two column pattern component data from the n-bit shift registers so as to obtain covariance matrix of the two column pattern component data, a row covariance matrix calculation circuit for receiving at a time two row pattern component data from the m-bit shift registers so as to obtain covariance matrix of the two row pattern component data, and memory means for storing the column and row covariance matrix data obtained by teh column and row covariance matrix calculation circuits;

and a similarity calculation unit including memory means for storing a plurality of standard column pattern covariance matrix data each calculated based on covariance matrix of column pattern components known to belong to the corresponding one of the categories and a plurality of standard row pattern covariance matrix data each calculated based on covariance matrix of row pattern components, column multiplier-adder means for multiplying and summing the column covariance matrix data read out from the memory means of the input pattern covariance matrix calculation unit and each standard column pattern covariance matrix data, row multiplier-adder means for multiplying and summing the row covariance matrix data read out from the memory means of the input pattern covariance matrix calculation unit and each standard row pattern covariance matrix data, multiplier means for multiplying the output data of the column and row multiplier-adder means so as to obtain product data, detection means for detecting the largest of the product data obtained by the multiplier means, and identifying means for identifying the input pattern as belonging to the category represented by the largest product data detected by the detection means.

7. A pattern identification system according to claim 6, wherein said similarity calculation unit further includes column norm calculation means for obtaining the norm of the column covariance matrix data read out from the memory means of said input pattern covariance matrix calculation unit, column dividing means for dividing the output data of said column multiplier-adder means by the norm data from the column norm calculation means, row norm calculation means for obtaining the norm of the row covariance matrix data read out from the memory means of said input pattern covariance matrix calculation unit, and row dividing means for dividing the output data of said row multiplier-adder means by the norm data from the row norm calculation means, the output data of said column and row dividing means being supplied to said multiplier means of the similarity calcualtion unit.