Method and system for search and retrieval of similar patterns

• US 6,584,465 B1
• Filed: 02/25/2000
• Issued: 06/24/2003
• Est. Priority Date: 02/25/2000
• Status: Expired due to Term

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Zhu, Wei, Mehrotra, Rajiv
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): DODDS, HAROLD E
• Application Number:
  US09/513,405
• Time in Patent Office: 1,215 Days
• Field of Search: 707/1-7, 707/9, 707/10, 707/100-104, 707/200, 707/201, 707/203, 709/200, 709/201, 709/217-219, 345/418, 345/419, 345/423, 382/111, 382/181, 382/190, 382/191, 382/192, 382/193, 382/195, 382/199, 382/203, 382/209, 382/276, 382/305
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for retrieving digital patterns similar to a query pattern operates by generating representations of each digital pattern in terms of one or more color invariant properties; storing and organizing the patterns and their representations in a database; and searching the database by reference to the representations to identify and retrieve patterns similar to the query pattern. A preferred color invariant property is an edge property of the digital patterns. A web-based pattern registration and searching architecture enables on-line pattern search and selection utilizing a variety of pattern representations and similarity techniques, including the edge property based system described above.

Claims

1. A method for retrieving digital patterns similar to a query pattern selected by a user, said method comprising the steps of:

(a) generating representations of each digital pattern in terms of one or more color invariant properties, wherein said step (a) of generating representations of each digital pattern in terms of color invariant properties includes generating representations of each digital pattern in terms of its edge properties;

(b) storing and organizing the patterns and their representations in a database; and

(c) searching the database by reference to the representations to identify and retrieve patterns similar to the query pattern.

2. The method as claimed in claim 1 wherein step (b) of storing and organizing the patterns and their representations in the database includes organizing the representations in an index structure.

3. The method as claimed in claim 2 wherein the step (c) of searching the database includes:

(a) searching the index structure to identify a set of candidate patterns; and

(b) analyzing the set of candidate patterns to identify the patterns similar to the query pattern.

4. The method as claimed in claim 1 further including the step of ranking the retrieved patterns in a sorted order of their similarity with respect to the query pattern.

5. The method as claimed in claim 1 wherein each digital pattern is represented in terms of edge orientations.

6. The method as claimed in claim 5 wherein each digital pattern is represented in terms of relative frequency of occurrence of at least some of the possible edge orientations.

7. The method as claimed in claim 6 wherein the relative frequency of occurrence of at least some of the possible edge orientations includes distribution of edge orientations for co-occurring edges.

8. The method as claimed in claim 1 wherein the step (c) of identifying patterns similar to the query pattern includes computing the similarity of the query pattern and a candidate pattern based on the similarity of their edge orientation frequency representations.

9. The method as claimed in claim 1 wherein the step (c) of identifying patterns similar to the query pattern includes computing the similarity of the query pattern and a candidate pattern based on the similarity of their edge orientation co-occurrence frequency representations.

10. A web-based program tool that assists in the review and selection of patterns by utilizing the method as claimed in claim 1 to automatically identify and retrieve patterns similar to a selected pattern.

11. A web-based program tool that assists in the review and selection of fabric for clothing or furniture by utilizing the method as claimed in claim 1 to automatically identify and retrieve clothing or furniture patterns similar to a selected pattern.

12. A web-based interior decoration program tool that assists in the review and selection of wallpaper, tile, floor treatment or window treatment by utilizing the method as claimed in claim 1 to automatically identify and retrieve wallpaper, tile, floor treatment or window treatment patterns similar to a selected pattern.

13. A system for retrieving digital patterns similar to a query pattern selected by a user, said system comprising:

(a) a database of digital patterns;

(b) a processing stage for generating representations of each digital pattern in terms of one or more color invariant properties and organizing the patterns and their representations in a database organization, wherein said processing stage generates representations of each digital pattern in terms of one or more edge properties of each pattern;

(c) a provision for storing the patterns and their representations in the database; and

(d) a searching stage that searches the database by reference to the representations to identify and retrieve patterns similar to the query pattern.

14. The system as claimed in claim 13 wherein the patterns and their representations are organized in an index structure and the searching stage includes a searching algorithm for searching the index structure to identify a set of candidate patterns and analyze the set of candidate patterns to identify the patterns similar to the query pattern.

15. The system as claimed in claim 13 wherein the search stage ranks the retrieved patterns in a sorted order of their similarity with respect to the query pattern.

16. The system as claimed in claim 13 wherein the processing stage generates representations of each pattern in terms of edge orientations.

17. The system as claimed in claim 16 wherein the processing stage generates representations of each pattern in terms of relative frequency of occurrence of at least some of the possible edge orientations.

18. The system as claimed in claim 17 wherein the relative frequency of occurrence of at least some of the possible edge orientations includes distribution of edge orientations for co-occurring edges.

19. A computer program product for retrieving digital patterns similar to a query pattern comprising:

a computer readable storage medium having a computer program stored thereon for performing the steps of;

(a) generating representations of each digital pattern in terms of one or more color invariant properties, wherein said step (a) of generating representations of each digital pattern in terms of color invariant properties includes generating representations of each digital pattern in terms of its edgers properties;

(b) storing and organizing the patterns and their representations in a database; and

(c) searching the database by reference to the representations to identify and retrieve patterns similar to the query pattern.

20. The computer program product as claimed in claim 19 wherein step (b) of storing and organizing the patterns and their representations in the database includes organizing the representations in an index structure.

21. The computer program product as claimed in claim 20 wherein the step (c) of searching the database includes:

(a) searching the index structure to identify a set of candidate patterns; and

(b) analyzing the set of candidate patterns to identify the patterns similar to the query pattern.

22. The computer program product as claimed in claim 19 further including the step of ranking the retrieved patterns in a sorted order of their similarity with respect to the query pattern.

23. The computer program product as claimed in claim 19 wherein each digital pattern is represented in terms of edge orientations.

24. The computer program product as claimed in claim 23 wherein each digital pattern is represented in terms of relative frequency of occurrence of at least some of the possible edge orientations.

25. The computer program product as claimed in claim 23 wherein the relative frequency of occurrence of at least some of the possible edge orientations includes distribution of edge orientations for co-occurring edges.