Method and apparatus for pattern recognition using a recognition dictionary partitioned into subcategories

• US 6,778,704 B1
• Filed: 01/04/2002
• Issued: 08/17/2004
• Est. Priority Date: 10/30/1996
• Status: Expired due to Fees

• Current Assignee: HTC Corporation
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kawatani, Takahiko
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/297,499
• Time in Patent Office: 956 Days
• Field of Search: 382/171, 382/174, 382/178, 382/190, 382/199, 382/203, 382/224-226, 382/290, 382/159, 706/20, 706/25-26, 704/200
• US Class Current: 382/224
• CPC Class Codes: G06V 30/242 Division of the character sequences into groups prior to recognition; Selection of dictionaries

Abstract

A pattern recognition method that determines the category of an unknown pattern. The category is one of a set of categories corresponding to a set of known patterns. A subcategory-level recognition dictionary is provided that stores reference information for each one of plural subcategories obtained by partitioning the categories constituting the category set. A pattern signal respresenting the unknown pattern is received (12) and is processed to extract a feature vector from it. The reference information of one subcategory of each category in the recognition dictionary is selected (14, 16) from the recognition dictionary in response to the feature vector. Finally, a distance between the feature vector and the reference information of the subcategory of each category selected in the selected in the selecting step is determined (18) to determine the category of the unknown pattern. The subcategory-level recognition dictionary is generated in response to feature vectors extracted from training pattern signals representing respective training patterns. The recognition dictionary stores reference information for each one of plural categories constituting a category set. Each category is partitioned (54, 56) into 2ⁿ subcategories, where n is greater than zero, and learning by discriminant analysis is applied (58, 62, 64, 68) to each subcategory to generate reference information for the subcategory.

Claims

1. A pattern recognition method for determining the category of an unknown pattern, the category being one of a set of categories corresponding to a set of known patterns, the method comprising:

providing a subcategory-level recognition dictionary adapted to store reference information for each one of plural subcategories obtained by partitioning the categories comprising the category set, wherein each of the categories is partitioned into the subcategories by at least one partitioning vector;

receiving a pattern signal representing the unknown pattern and processing the signal to extract a feature vector therefrom;

selecting the reference information of one subcategory of each category in the recognition dictionary in response to the feature vector, the reference information of one subcategory of each category being selected from the recognition dictionary, and calculating the inner product of the feature vector and at least one partitioning vector; and

determining a distance between the feature vector and the selected reference information of the subcategory of each category to determine the category of the unknown pattern;

wherein there are n partitioning vectors, n being a positive integer; and

wherein selecting the reference information of one subcategory of each category in the recognition dictionary further comprises;

initializing an index i to 0, i being a positive integer, and

iterating the following processes upon the index i being less than n;

comparing the i-th inner product with a threshold and

generating Z_i(k)=1 when the inner product is greater than the threshold and otherwise generating Z_i(k)=0; and

accumulating the results of multiplying 2ⁱ by Z_i(k) to generate an index of a selected subcategory.

2. The method of claim 1, wherein the distance between the feature vector and the reference information comprises a modified Euclidean distance.

3. A method of generating a subcategory-level recognition dictionary for use in pattern recognition, the recognition dictionary including reference information for each one of plural subcategories comprising a category set, the recognition dictionary being generated in response to feature vectors extracted from training signals representing respective training patterns, the method comprising:

partitioning each category into 2ⁿ subcategories, wherein n is an integer greater than zero, and wherein partitioning each category into subcategories includes defining at least one partitioning vector for the category in response to the feature vectors of the training patterns in the category, the at least one partitioning vector partitioning the category into subcategories; and

applying learning by discriminant analysis to each subcategory to generate the reference information for this subcategory, applying learning by discriminant analysis comprising;

defining preliminary reference information for each subcategory;

performing a pattern recognition operation on the training patterns using the preliminary reference information to determine a subcategory for each of the training patterns;

evaluating the recognition result of the pattern recognition operation on each training pattern against the subcategory to which the training pattern was allocated to define a rival pattern set for each subcategory; and

performing a linear discriminant analysis between a category pattern set and the rival pattern set of each subcategory to generate reference modifying information for modifying the initial reference information to generate the reference information for the subcategory.

4. The method of claim 3, wherein partitioning each category into subcategories includes allocating each of the training patterns in the category to one of the subcategories of the category in response to the feature vectors of the training patterns in the category and the at least one partitioning vector.

5. A pattern recognition apparatus adapted to determine the category of an unknown pattern represented by a feature vector extracted from a pattern signal, the category being one of a set of categories corresponding to a set of known patterns, the apparatus comprising:

a subcategory-level recognition dictionary adapted to store reference information for each one of plural subcategories obtained by partitioning the categories comprising the category set in which each of the categories is partitioned into the subcategories by at least one partitioning vector;

a selecting module adapted to select the reference information of one subcategory of each category in response to the feature vector, the reference information of one subcategory of each category being selected from the recognition dictionary;

a distance determining module adapted to determine a distance between the feature vector and the reference information of the subcategory selected by the selecting module for each of the subcategories; and

a module adapted to determine the category of the unknown pattern from the distance generated by the distance determining module for each of the categories;

wherein the selecting module further comprises a module adapted to calculate and inner product of the feature vector and the at least one partitioning, vector; and

wherein there are n partitioning vectors, n being a positive integer; and

wherein the selecting module further comprises;

a module adapted to initialize an index i to 0, i being a positive integer, and

a processing module adapted to generate an index of a selected subcategory upon the index i being less than n, the processing module comprising;

a comparative adapted to compare the i-th inner product with a threshold and to generate Z_i(k) in a 1 state when the inner product is greater than the threshold and to otherwise generate Z_i(k) in a 0 state; and

a multiplier adapted to multiply 2ⁱ by Z_i(k) to generate a product; and

an accumulator adapted to accumulate the products generated by the multiplier to generate an index of a selected subcategory.

6. An apparatus for generating a subcategory-level recognition dictionary for use in pattern recognition, the recognition dictionary including reference information for each of plural subcategories, this subcategory is being subcategories of categories comprising a category set, the reference information being generated from feature vectors extracted from training pattern signals representing training patterns, the apparatus comprising:

a partitioning section adapted to partition each category into 2ⁿ, wherein n is a positive integer greater than zero; and

a section adapted to applying learning by discriminant analysis to each subcategory defined by the partitioning section to generate the reference information for the subcategory;

wherein the section adapted to apply learning by discriminant analysis further comprises;

a preliminary reference information module adapted to define preliminary reference information for each subcategory;

a pattern recognition module adapted to perform pattern recognition on the training patterns using the preliminary reference information to determine a subcategory for each of the training patterns as a recognition result;

a result of valuation module adapted to evaluate the recognition result generated by the pattern recognition module on each training pattern against the subcategory to which the training pattern was allocated by the allocation module to define a rival pattern set for each subcategory; and

a module adapted to perform a linear discriminant analysis between a category pattern set and the rival pattern set of each subcategory to generate reference modifying information to modify the preliminary reference information to generate the reference information for the subcategory.

7. The apparatus of claim 6, wherein the partitioning section is adapted to partitioned the category into the subcategories using at least one partitioning vector and wherein the partitioning section further comprises:

a partitioning vector generator adapted to define the at least one partitioning vector for the category in response to the feature vectors of the training patterns in the category and

a subcategory allocation module adapted to operate in response to the feature vectors of the training patterns and each category and the at least one partitioning vector for the category to allocate each of the training patterns in the category to one of the subcategories of the category.