FIGURE CLASSIFYING METHOD, FIGURE CLASSIFYING SYSTEM, FEATURE EXTRACTING METHOD FOR FIGURE CLASSIFICATION, METHOD FOR PRODUCING TABLE FOR FIGURE CLASSIFICATION, INFORMATION RECORDING MEDIUM, METHOD FOR EVALUATING DEGREE OF SIMILARITY OR DEGREE OF DIFFERENCE BETWEEN FIGURES, FIGURE NORMALIZING METHOD, AND METHOD FOR DETERMINING CORRESPONDENCE BETWEEN FIGURES

• US 6,424,746 B1
• Filed: 10/27/1998
• Issued: 07/23/2002
• Est. Priority Date: 10/28/1997
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Nishida, Hirobumi
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/179,418
• Time in Patent Office: 1,365 Days
• Field of Search: 382/203, 382/206, 382/190, 382/195, 382/199, 382/218, 382/219, 382/224, 382/276
• US Class Current: 382/195
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

A figure is input, and structural features of the input figure are extracted. Structural features of deformed figures are produced, in accordance with a specific transformation rule, from the extracted structural features. The input figure is classified based on the structural features thus extracted and thus produced.

Claims

1. A figure classifying method comprising the steps of:

a) providing stored data corresponding to structural features of model figures and structural features of first deformed figures produced from said structural features of said model figures; and

subsequently, inputting a figure;

b) extracting structural features of the input figure;

c) producing structural features of second deformed figures, in accordance with a specific transformation rule, from the extracted structural features; and

d) classifying the input figure based on said stored data, the extracted structural features of said input figure and said structural features of said second deformed figures.

2. The figure classifying method as claimed in claim 1, wherein said step d) comprises the steps of:

d1) calculating indexes from the structural features extracted in said step b) and produced in said step c);

d2) referring to model identifier lists of entries of a table, which entries correspond to the indexes, in said table, calculated in said step d1), respectively; and

d3) voting on model identifiers included in the model identifier lists referred to in said step d2),

wherein each index of said table is calculated from either the structural features of a model figure, the model identifier of which is included in the model identifier list of the entry corresponding to said index, or the structural features of a deformed figure produced in accordance with a specific transformation rule from the structural features of the model figure.

3. The figure classifying method as claimed in claim 1, further comprising the step of

e) searching a figure database based on a result of said step d).

4. The figure classifying method as claimed in claim 3, wherein said step d) and step e) comprise the steps of:

d1) calculating indexes from the structural features extracted in said step b) and produced in said step c);

d2) referring to model identifier lists of entries of a table, which entries correspond to the indexes, in said table, calculated in said step d1), respectively;

d3) on voting model identifiers included in the model identifier lists referred to in said step d2); and

e1) searching a figure database using the model identifiers as search keys, the numbers of votes of said model identifiers being larger,

wherein each index of said table is calculated from either the structural features of a model figure, the model identifier of which is included in the model identifier list of the entry corresponding to said index, or the structural features of a deformed figure produced in accordance with a specific transformation rule from the structural features of the model figure.

10. The figure classifying method as claimed in claim 1, wherein the specific transformation rule comprises rules for a plurality of feature transformations selected from a group consisting of a change along a normal line of a contour, change of characteristic number due to rotation of the figure, and local transformation of the figure.

11. The figure classifying method of claim 10, wherein said step of providing stored data includes the steps of applying transformation rules to said first deformed figures, and wherein the number of said transformation rules applied to said structural features of said first deformed figures is greater than the number of rules applied to said structural features of said second deformed figures, such that at least one of said transformation rules applied to said structural features of said first deformed figures is not applied to said structural features of said second deformed figures.

5. A figure classifying system comprising:

a figure inputting portion inputting a figure;

a feature extracting portion extracting structural features of the input figure;

a feature producing portion producing structural features of deformed figures, in accordance with a specific transformation rule, from the extracted structural features, wherein the specific transformation rule comprises rules for a plurality of feature transformations selected from a group consisting of a change along a normal line of a contour, change of characteristic number due to rotation of the figure, and local transformation of the figure;

a storing portion storing a table; and

a classifying portion calculating indexes from die structural features extracted by said feature extracting portion and produced by said feature producing portion, referring to model identifier lists of entries of said table, which entries correspond to the thus-calculated indexes in said table, and voting on model identifiers included in the thus-referred-to model identifier lists, wherein some of said indexes of said table are calculated from the structural features of a model figure, the model identifier of which is included in the model identifier list of the entry corresponding to said index, and wherein others of said indexes of said table are calculated from the structural features of a deformed figure produced in accordance with a specific transformation rule from the structural features of the model figure.

6. The figure classifying system as claimed in claim 5, further comprising a figure database, wherein said classifying portion searching said figure data base using the model identifiers as search keys, the numbers of votes of said model identifiers being larger.

7. A method for producing a table for figure classification comprising the steps of:

a) extracting structural features of each model figure included in a set of model figures;

b) producing structural features of deformed figures, in accordance with a specific transformation rule, from structural figures extracted in said step a); and

c) producing a table for figure classification, wherein some of said indexes of said table are calculated from the structural features extracted from said model figure in said step a), an identifier of which model figure is included in a model identifier list of an entry corresponding to said index, and wherein others of said indexes of said table are calculated from the structural features produced in said step b).

12. The method of claim 7, wherein the specific transformation rule comprises rules for a plurality of feature transformations selected from a group consisting of a change along a normal line of a contour, change of characteristic number due to rotation of the figure, and local transformation of the figure.

8. A computer-readable information recording medium storing a figure classifying program for causing a computer to function as:

figure inputting means for inputting a figure;

feature extracting means for extracting structural features of the input figure;

feature producing means for producing structural features of deformed figures, in accordance with a specific transformation rule, from the extracted structural features, wherein the specific transformation rule comprises rules for a plurality of feature transformations selected from a group consisting of a change along a normal line of a contour, change of characteristic number due to rotation of the figure, and local transformation of the figure; and

classifying means for calculating indexes from the structural features extracted by said feature extracting means and produced by said feature producing means, referring to model identifier lists of entries of a table, which entries correspond to the thus-calculated indexes in said table, and voting on model identifiers included in the thus-referred-to model identifier lists, wherein some of said indexes of said table are calculated from the structural features of a model figure, the model identifier of which is included in the model identifier list of the entry corresponding to said index, and wherein others of said indexes of said table are calculated from the structural features of a deformed figure produced in accordance with a specific transformation rule from the structural features of the model figure.

9. The computer-readable information recording medium storing the figure classifying program as claimed in claim 8, wherein said classifying means searching a figure data base using the model identifiers as search keys, the numbers of votes of said model identifiers being larger.