US 5,479,523 AGranted

Constructing classification weights matrices for pattern recognition systems using reduced element feature subsets

AssigneeEastman Kodak Company

InventorsRoger S. Gaborski, Peter G. Anderson, David G. Tilley, Christopher T. Asbury

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods and apparatus for constructing a classification weights matrix for a pattern recognition system are provided which enable large system feature sets to be reduced and yield at least the same level of performance achieved using the large feature set. Methods and apparatus are also described for determining (evaluating) the classification efficiency of selected subsets of a given feature set. Further aspects of the invention are directed to: (a) methods and apparatus for constructing reduced element classification weights matrices utilizing a genetic search process to find the subset having a maximum classification efficiency; and (b) pattern recognition systems (including, in particular, character identification systems), which utilize classifiers constructed in accordance with the aforementioned aspects of the invention to actually perform pattern recognition.

Claims25

Dependent claims

A method for constructing and using a classification weights matrix A' in a pattern recognition system, comprising the steps of:

(a) providing a digital computer with a first set of signals representing a correlation matrix Z between a predetermined set of exemplar feature vectors, each representing the values of a predefined set of F features, and a set of classification target vectors corresponding to said feature vectors;
(b) providing said digital computer with a second set of signals representing the autocorrelation matrix W of said set of exemplar feature vectors;
(c) determining a classification efficiency of selected subsets of said set of F features, wherein said step of determining the classification efficiency for a given subset comprises the steps of:
(c1) utilizing said given subset to construct submatrices of said correlation and autocorrelation matrices;
(c2) forming a weights matrix for a linear discriminator, in the vector space of said given subset of features, as a function of said submatrices, and
(c3) testing said linear discriminator weights matrix on a predefined set of exemplars to yield the classification efficiency of said given subset;
(d) searching a space S of f-element subsets of said set of F features, where f is prespecified and less than F, for an f-element subset having a maximum classification efficiency;
(e) selecting one of the f-element subsets in said space, S, as having a maximum classification efficiency as a result of said step of searching;
(f) defining said classification weights matrix A' as the product of submatrix Z' of said correlation matrix Z, and an inverse of submatrix W' of said autocorrelation matrix W, where submatrices Z' and W' are constructed as a function of S;
(g) capturing a pattern to be recognized using an input device;
and
(h) performing pattern recognition of the pattern captured with the digital computer using said classification weights matrix A'.

9 more elements

A method for classifying an unclassified pattern input to a pattern recognition system that includes a digital computer, comprising the steps of:

(a) inputting said unclassified pattern to said digital computer in a normalized form from an input device;
(b) constructing, utilizing said digital computer, a classification weights matrix A' for a pattern recognition system, comprising the steps of:
(b1) providing said digital computer with a first set of signals representing a correlation matrix Z between a predetermined set of exemplar feature vectors, each representing the values of a predefined set of F features, and a set of classification target vectors corresponding to said feature vectors;
(b2) providing said digital computer with a second set of signals representing the autocorrelation matrix W of said set of exemplar feature vectors;
(b3) determining a classification efficiency of selected subsets of said set of F features, wherein said step of determining the classification efficiency for a given subset comprises the steps of:
(b31) utilizing said given subset to construct submatrices of said correlation and autocorrelation matrices;
(b32) forming a weights matrix for a linear discriminator, in the vector space of said given subset of features, as a function of said submatrices, and
(b33) testing said linear discriminator weights matrix on a predefined set of exemplars to yield the classification efficiency of said given subset;
(c) searching a space of f-element subsets of said set of F features, where f is prespecified and less than F, for an f-element subset having a maximum classification efficiency;
(d) selecting one of the f-element subsets in said space as having a maximum classification efficiency as a result of said step of searching;
(e) defining said classification weights matrix A' as the product of submatrix Z' of said correlation matrix Z, and an inverse of submatrix W' of said autocorrelation matrix W, where submatrices Z' and W' are constructed as a function of said subset having the maximum classification efficiency;
and
(f) applying A' to the normalized unclassified pattern provided to said computer system in step (a) to recognize and classify said pattern.

10 more elements

A pattern recognition system, comprising:

a programmable digital computer;
and
an input device coupled to said digital computer and providing a set of patterns to be classified by said system, to said computer in a normalized form;
said programmable digital computer comprising means for constructing a classification weights matrix A' for said system from a first set of signals, available to said computer, representing a correlation matrix Z between a predetermined set of exemplar feature vectors, each representing the values of a predefined set of F features, and a set of classification target vectors corresponding to said feature vectors, and from a second set of signals, available to said computer, representing the autocorrelation matrix W of said set of exemplar feature vectors, and means for performing pattern recognition of unclassified patterns using the classification weights matrix, wherein said means for constructing further comprises:
(c1) means for determining a classification efficiency of selected subsets of said set of F features, wherein said means for determining the classification efficiency for a given subset further comprises:
(c11) means for constructing, utilizing said given subset, submatrices of said correlation and autocorrelation matrices;
(c12) means for forming a weights matrix for a linear discriminator, in the vector space of said given subset of features, as a function of said submatrices, and
(c13) means for testing said linear discriminator weights matrix on a predefined set of exemplars to yield the classification efficiency of said given subset;
(c2) means for searching a space of f-element subsets of said set of F features, where f is prespecified and less than F, for an f element subset having a maximum classification efficiency;
(c3) means for selecting one of the f-element subsets in said space as having a maximum classification efficiency as a result of the search performed by said means for searching;
and
(c4) means for defining said classification weights matrix A' as the product of submatrix Z' of said correlation matrix Z, and an inverse of submatrix W' of said autocorrelation matrix W, where submatrices Z' and W' are constructed as a function of said subset having the maximum classification efficiency.

9 more elements

A method for constructing and using a classification weights matrix A' in a pattern recognition system that includes a digital computer provided with (a) a first set of signals representing a correlation matrix Z between a predetermined set of exemplar feature vectors, each representing the values of a predefined set of F features, and a set of classification target vectors corresponding to said feature vectors, and (b) a second set of signals representing the autocorrelation matrix W of said set of exemplar feature vectors, comprising the steps of:

(a) forming, using the digital computer, an initial population of P individuals, wherein each individual is a randomly chosen f-element subset of said predetermined set of said set of F features, where f<<F;
(b) evaluating, using the digital computer, a fitness of each individual subset;
(c) determining, using the digital computer, if a stopping condition has been met based on the evaluated fitness of each individual;
(d) defining, using the digital computer, whenever a stopping condition has been met, the individual subset S that satisfies a stopping condition as the most fit individual;
(e) defining, using the digital computer, said classification weights matrix A' as the product of submatrix Z' of said correlation matrix Z, and an inverse of submatrix W' of said autocorrelation matrix W, where submatrix Z' is an array whose columns are the columns of Z selected by subset S, and where submatrix W' is an array whose rows and columns are the rows and columns of W selected by subset S;
(f) inputting an unclassified pattern using an input device;
and
(g) performing pattern recognition of the unclassified pattern using the digital computer with the classification weights matrix A'.

5 more elements

Dependencies are inferred from the claim text.