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

• US 6,487,554 B2
• Filed: 10/30/2001
• Issued: 11/26/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:
  US10/020,346
• Publication Number:
  US 20020099721A1
• Time in Patent Office: 392 Days
• Field of Search: 707/3, 707/2, 707/10, 707/6, 707/104, 382/162, 382/163
• 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 method of processing information signals, the method comprising the steps of:

extracting color and texture information from a first information signal selected by a user, using a predetermined vocabulary comprising one or more dimensions; and

generating a distance measure characterizing the relationship of the first information signal to a 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.

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

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

4. The method 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 method further includes the step of generating 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 method of claim 4 wherein the grammar comprises one or more of the following rules:

equal pattern, overall appearance, similar pattern, dominant color and general impression, and the method further includes the step of applying the rules to the set of values.

6. The method of claim 1 wherein the step of generating a distance measure further includes the steps of generating a color metric characterizing the similarity of the color information associated with the first and second information signals, and generating a texture metric characterizing the similarity of the texture information associated with the first and second information signals.

7. The method of claim 1 wherein the extracting step further includes extracting an achromatic pattern map from the first information signal using a color distribution generated from the first information signal.

8. The method of claim 7 further including the step of estimating the color distribution using a set of color codebooks, with each of the color codebooks corresponding to a different luminance level of the first information signal.