Retrieval and matching of color patterns based on a predetermined vocabulary and grammar

• US 6,411,953 B1
• Filed: 01/25/1999
• Issued: 06/25/2002
• Est. Priority Date: 01/25/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Ganapathy, S. Kicha, Safranek, Robert James, Mojsilovic, Aleksandra, Kovacevic, Jelena, Hu, Jianying
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/236,854
• Time in Patent Office: 1,247 Days
• Field of Search: 707/6, 707/3, 707/104, 707/2, 430/367, 430/369, 345/582, 345/426, 345/502, 345/592, 345/606, 358/447, 358/515, 358/537, 358/1.9, 382/305, 382/220, 382/165, 382/167, 382/209, 382/229
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G06F 18/24765 Rule-based classification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

The invention provides a perceptually-based system for pattern retrieval and matching, suitable for use in a wide variety of information processing applications. An illustrative embodiment of the system uses a predetermined vocabulary comprising one or more dimensions to extract color and texture information from an information signal, e.g., an image, selected by a user. The system then generates a distance measure characterizing the relationship of the selected image to another image stored in a database, by applying a grammar, comprising a set of predetermined rules, to the color and texture information extracted from the selected image and corresponding color and texture information associated with the stored image. The vocabulary may include dimensions such as overall color, directionality and orientation, regularity and placement, color purity, and pattern complexity and heaviness. The rules in the grammar may include equal pattern, overall appearance, similar pattern, and dominant color and general impression, with each of the rules expressed as a logical combination of values generated for one or more of the dimensions. The distance measure may include separate color and texture metrics characterizing the similarity of the respective color and texture of the two images being compared. The invention is also applicable to other types of information signals, such as sequences of video frames.

Claims

1. A system for processing information signals, the system comprising:

a processor operative to compare a first information signal to a second information signal in response to a user query, wherein the first information signal is selected by the user and the second information signal is stored in a database associated with the system, wherein the processor extracts color and texture information from at least the first information signal using a predetermined vocabulary comprising one or more dimensions, and generates a distance measure characterizing the relationship of the first information signal to the second information signal by applying a grammar comprising a set of predetermined rules to the color and texture information extracted from the first information signal and corresponding color and texture information associated with the second information signal, wherein the processor receives the first information signal in the form of an input image A submitted in conjunction with a query from the user, and wherein the processor is further operative to measure dimensions DIM_i(A) from the vocabulary, for i=1, . . . , N, and for each image B from an image database, to apply rules R_i from the grammar to obtain corresponding distance measures dist_i(A, B), where dist_i(A, B) is the distance between the images A and B according to the rule i.

2. The system of claim 1 wherein at least one of the first and second information signals comprises an image.

3. The system of claim 1 wherein at least one of the first and second information signals comprises a sequence of video frames.

4. The system of claim 1 wherein the vocabulary comprises one or more of the following dimensions:

overall color, directionality and orientation, regularity and placement, color purity, and pattern complexity and heaviness, and the system generates for at least one of the first and second information signals a set of values associated with one or more of the dimensions.

5. The system of claim 4 wherein the system applies the rules to the set of values.

6. The system of claim 5 wherein the equal pattern file is a function of the dimension of directionality and orientation and the dimension of regularity and placement.

7. The system of claim 5 wherein the overall appearance rule is a function of the dimension of overall color and the dimension of directionality and orientation.

8. The system of claim 5 wherein the similar pattern rule is a function of at least one of the dimension of directionality and orientation and the dimension of regularity and placement.

9. The system of claim 5 wherein the dominant color rule is a function of the dimension of overall color.

10. The system of claim 5 wherein the general impression rule is a function of the dimension of color purity and the dimension of pattern complexity.

11. The system of claim 5 wherein each rule is expressed as a logical combination of one or more of the values generated for at least a subset of the dimensions.

12. The system of claim 1 wherein the processor is further operative to extract an achromatic pattern map from the first information signal using a color distribution generated from the first information signal.

13. The system of claim 1 wherein the color distribution is estimated using a set of color codebooks, with each of the color codebooks corresponding to a different luminance level of the first information signal.

14. The system of claim 1 wherein the processor is further operative to generate a color metric characterizing the similarity of the color information associated with the first and second information signals.

15. The system of claim 1 wherein the processor is further operative to generate a texture metric characterizing the similarity of the texture information associated with the first and second information signals.

16. A system for processing information signals, the system comprising:

a processor operative to compare a first information signal to a second information signal in response to a user query, wherein the first information signal is selected by the user and the second information signal is stored in a database associated with the system, wherein the processor extracts color and texture information from at least the first information signal using a predetermined vocabulary comprising one or more dimensions, and generates a distance measure characterizing the relationship of the first information signal to the second information signal by applying a grammar comprising a set of predetermined rules to the color and texture information extracted from the first information signal and corresponding color and texture information associated with the second information signal, wherein the set of predetermined rules comprises one or more of the following rules;

equal pattern, overall appearance, similar pattern, dominant color and general impression, wherein the processor receives the first information signal in the form of an input image A submitted in conjunction with a query from the user, and wherein the processor is, further operative to measure dimensions DIM_i(A) from the vocabulary, for i=1, . . . , N, and for each image B from an image database, to apply rules R_i from the grammar to obtain corresponding distance measures dist_i(A, B), where dist_i(A, B) is the distance between the images A and B according to the rule i.

17. A system for processing information signals, the system comprising:

a processing device having a processor coupled to a memory, the processor being operative to compare a first information signal to a second information signal in response to a user query, wherein the first information signal is selected by the user and the second information signal is stored in a database associated with the system, wherein the processor extracts color and texture information from at least the first information signal using a predetermined vocabulary comprising one or more dimensions, and generates a distance measure characterizing the relationship of the first information signal to the second information signal by applying a grammar comprising a set of predetermined rules to the color and texture information extracted from the first information signal and corresponding color and texture information associated with the second information signal, wherein the set of predetermined rules comprises one or more of the following rules;

equal pattern, overall appearance, similar pattern, dominant color and general impression, wherein the processor receives the first information signal in the form of an input image A submitted in conjunction with a query from the user, and wherein the processor is further operative to measure dimensions DIM_i(A) from the vocabulary, for i=1, . . . , N, and for each image B from an image database, to apply rules R_i from the grammar to obtain corresponding distance measures dist_i(A, B), where dist_i(A, B) is the distance between the images A and B according to the rule i.

18. A system for processing information signals, the system comprising:

a processing device having a processor coupled to a memory, the processor being operative to compare a first information signal to a second information signal in response to a user query, wherein the first information signal is selected by the user and the second information signal is stored in a database associated with the system, wherein the processor extracts color and texture information from at least the first information signal using a predetermined vocabulary comprising one or more dimensions, and generates a distance measure characterizing the relationship of the first information signal to the second information signal by applying a grammar comprising a set of predetermined rules to the color and texture information extracted from the first information signal and corresponding color and texture information associated with the second information signal, wherein the processor receives the first information signal in the form of an input image A submitted in conjunction with a query from the user, and wherein the processor is further operative to measure dimensions DIM_i(A) from the vocabulary, for i=1, . . . , N, and for each image B from an image database, to apply rules R_i from the grammar to obtain corresponding distance measures dist_i(A, B), where dist_i(A, B) is the distance between the images A and B according to the rule i.