Retrieval system, retrieval method and computer readable recording medium that records retrieval program

• US 6,338,062 B1
• Filed: 09/01/1999
• Issued: 01/08/2002
• Est. Priority Date: 09/28/1998
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Liu, Shaoming
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/387,850
• Time in Patent Office: 860 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The object of the present invention is to enable high-speed and high-precision pattern retrieval. Therefore, a retrieval dictionary generation unit classifies learned patterns into plural clusters, and generates a retrieval dictionary using the clusters. A nearest cluster detector detects the nearest cluster to an input retrieval pattern among clusters stored in the retrieval dictionary. A learned pattern detector compares each learned pattern which belongs to the nearest cluster with the retrieval pattern and detects a learned pattern at predetermined distance from the retrieval pattern. A retrieval range decision unit decides a retrieval range using the learned pattern detected by the learned pattern detector and retrieval information. A retrieval unit executes the retrieval of the retrieval pattern from among all the learned patterns in the retrieval range.

Claims

1. A retrieval system that executes pattern retrieval, comprising:

a retrieval dictionary generation unit that classifies learned patterns into plural clusters, and generates a retrieval dictionary using the clusters;

a nearest cluster detector that detects the nearest cluster to an input retrieval pattern among said clusters based upon said retrieval dictionary;

a learned pattern detector that compares each learned pattern which belongs to the nearest cluster with said retrieval pattern and detects a learned pattern at predetermined distance from said retrieval pattern;

a retrieval range decision unit that decides a retrieval range using said learned pattern detected by said learned pattern detector and said retrieval dictionary; and

a retrieval unit that retrieves said retrieval pattern among all the learned patterns in said retrieval range.

2. The retrieval system according to claim 1, wherein:

said retrieval dictionary generation unit classifies all the said learned patterns into plural clusters based upon distance between said learned patterns, obtains the representative of said clusters, calculates the radius of said clusters, distance between said clusters, distance between said learned pattern and said clusters, obtains order in comparing said clusters when the nearest cluster with said retrieval pattern is detected, and generates said retrieval dictionary.

3. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit obtains the mean value of the features in each dimension of all the said learned patterns which belong to said cluster if a pattern is represented by its feature when the representative of said cluster is obtained, and sets obtained said mean value as the representative of said cluster.

4. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit calculates distance between each learned pattern which belongs to said cluster if a pattern is represented by a thing other than its feature when the representative of said cluster is obtained, and sets, as the representative of said cluster, a learned pattern for which the sum of distance from said learned pattern to each learned pattern which belongs to said cluster is the minimum.

5. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit calculates distance between each learned pattern which belongs to said cluster and the representative of said cluster when the radius of said cluster is obtained, and sets the maximum distance to the radius of said cluster.

6. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit sets distance between the representatives of said clusters to distance between said clusters when distance between said clusters is obtained.

7. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit sets distance between said learned pattern or said retrieval pattern and the representative of said cluster to distance between said learned pattern or said retrieval pattern and said cluster when distance between said learned pattern or said retrieval pattern and said cluster is obtained.

8. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit obtains the mean value of said features in each dimension of the representatives of all the said clusters if a pattern is represented by its feature when order in comparing said clusters in case said nearest cluster is detected is obtained, and obtains comparison order such that a cluster in the vicinity of said obtained mean value is first compared.

9. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit sets a cluster for which the sum of distance from said cluster to each cluster is the minimum to a cluster to be first compared if a pattern is represented by a thing other than its feature when order in comparing said clusters in case said nearest cluster is detected is obtained, sorts distance between said cluster to be first compared and another cluster in ascending order, and sets the sorted order as comparison order.

10. The retrieval system according to claim 2, wherein:

said retrieval dictionary generation unit has hierarchical structure and has distance between each of said clusters, order in comparing said clusters and the information of each cluster on a high order hierarchy; and

said information of each of said clusters is composed of the data structure of the representative of said clusters, the radius of said clusters, the number of learned patterns which belong to said clusters and the learned pattern information of said clusters.

11. The retrieval system according to claim 10, wherein:

said learned pattern information which said retrieval dictionary generation unit has is composed of the name of said learned pattern, the data structure of said learned pattern and distance between said learned pattern and said cluster representative.

12. The retrieval system according to claim 1, wherein:

said nearest cluster detector selects said clusters in order in comparing said clusters stored in said retrieval dictionary, calculates distance between said cluster representative and said retrieval pattern, obtains a cluster in the vicinity of said retrieval pattern, and reduces a range in which clusters are compared.

13. The retrieval system according to claim 12, wherein:

said nearest cluster detector sets the number of an ‘

i’

th cluster in order in comparing clusters stored in said retrieval dictionary to S(i) when a range in which said clusters are compared is obtained, sets a cluster for which distance from said retrieval pattern on the way of detection is the minimum to C_MinClass, sets distance stored in said retrieval dictionary between C_MinClass and a cluster C_s(i) to D (C_MinClass, C_s(i)) and sets all clusters which satisfy a formula, D (C_MinClass, C_s(i))<

2*D_MinC to a range in which said clusters are compared if distance obtained on the way of detection between the retrieval pattern and C_MinClass is set to D_MinC.

14. A retrieval system according to claim 1, wherein:

said retrieval range decision unit obtains a retrieved range of clusters, checks to see whether or not learned patterns which belong to the clusters in said retrieved range are required to be retrieved and obtains a range in which said learned patters which belong to the cluster required to be retrieved are retrieved.

15. A retrieval system according to claim 14, wherein:

said retrieval range decision unit sets distance between the cluster C_MinClass and a cluster C_i to D (C_MinClass, C_i) when said range in which clusters are retrieved is obtained, sets distance between a retrieval pattern q and C_MinClass to D (q, C_MinClass), sets the minimum distance obtained on the way of detection between said retrieval pattern and said learned pattern to D_MinP and sets all the clusters that satisfy a formula, D (C_MinClass, C_i)<

D (q, C_MinClass)+D_MinP+R_i if the radius stored in said retrieval dictionary of the cluster C_i is R_i to said range in which clusters are retrieved.

16. The retrieval system according to claim 14, wherein:

said retrieval range decision unit determines that learned which belong to said cluster are required to be retrieved if a formula, D (q, C_i)<

D_MinP+R_i is satisfied in case distance D (q, C_i) between the retrieval pattern q and the cluster C_i in said range in which clusters are retrieved is calculated when it is checked whether or not learned patterns which belong to each cluster in said range in which clusters are retrieved are required to be retrieved.

17. The retrieval system according to claim 14, wherein:

said retrieval range decision unit sets all the learned patterns that satisfy a formula, D (p, C_i)>

D (q, C_i)−

D_MinP to a retrieval range if distance stored in said retrieval dictionary from a learned pattern p which belongs to the cluster C_i to the representative of the cluster C_i is D (p, C_i) when said range in which learned patterns are retrieved is obtained.

18. A retrieval method of executing pattern retrieval, wherein:

learned patterns are classified into plural clusters, and a retrieval dictionary is generated using said clusters;

the nearest cluster to an input retrieval pattern is detected among said clusters stored in said retrieval dictionary;

a learned pattern at predetermined distance from said retrieval pattern is detected by comparing all the learned patterns that belong to the nearest cluster with said retrieval pattern;

a retrieval range is decided using said learned pattern and said retrieval dictionary; and

said retrieval pattern is retrieved from among all the learned patterns in said retrieval range.

19. A retrieval method according to claim 18, wherein:

said cluster is selected in order in comparing said clusters stored in said retrieval dictionary when said nearest cluster is detected;

distance between the representative of said cluster and said retrieval pattern is calculated;

a cluster in the vicinity of said retrieval pattern is obtained; and

a range in which clusters are compared is reduced.

20. A computer readable recording medium that records a retrieval program for instructing a computer to execute pattern retrieval, wherein:

the retrieval program instructs the computer to function as;

a retrieval dictionary generation unit that generates a retrieval dictionary for classifying learned patterns into plural clusters;

a nearest cluster detector that detects the nearest cluster to an input retrieval pattern among said clusters stored in said retrieval dictionary;

a learned pattern detector that detects a learned pattern at predetermined distance from said retrieval pattern by comparing all the learned patterns that belong to the nearest cluster with said retrieval pattern;

a retrieval range decision unit that decides a retrieval range using said learned pattern detected by said learned pattern detector and said retrieval dictionary; and

a retrieval unit that retrieves said retrieval pattern from among all the learned patterns in said retrieval range.