Automatically determining an optimal content image search algorithm by choosing the algorithm based on color

• US 6,445,818 B1
• Filed: 01/29/1999
• Issued: 09/03/2002
• Est. Priority Date: 05/28/1998
• Status: Expired due to Term

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: LG Electronics, Inc. (LG Corporation)
• Inventors: Lee, Jin Soo, Kim, Hyeon Jun
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/239,527
• Time in Patent Office: 1,313 Days
• Field of Search: 345/418, 358/403, 358/522, 382/162, 382/165, 382/168, 382/170, 382/172, 382/190, 382/209, 382/217, 382/218, 382/220, 382/224, 382/278, 382/282, 382/305, 707/1, 707/3, 707/6, 707/104
• US Class Current: 382/165
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis
• 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

A method for designating a local representative color value and automatically determining image searching algorithm for a color based image searching system is disclosed. A method for designating a local representative color values generally includes the steps of dividing a color image area; and obtaining a color histogram for each block, obtaining a color group from hue histograms of each block, or obtaining a maximum color group value to designate the representative color value. Also, a method determining a search algorithm generally includes the steps of detecting the number of color blocks CB having color information from the blocked information of a reference image; comparing the number of the color blocks with a determined reference value and assigning different weights to at least two search algorithm according to the comparison results; and performing a comparison search of an image by the search algorithm based on the determined weight.

Claims

1. A method for automatically determining an optimal search algorithm in a content based image searching system, comprising:

(a) determining a characteristic of an image based upon a global histogram, a local histogram, and a major color information, wherein the step (a) comprises,

dividing the input image into a plurality of blocks, and

detecting a number of blocks with a designated color value assigned according to a first predetermined condition;

(b) automatically assigning different weights to at least two searching algorithms according to the determined characteristic; and

(c) utilizing the assigned weights to perform an image search, wherein step (b) comprises assigning greater weight to a search algorithm based upon a global histogram if the detected number of blocks meets a second predetermined condition.

2. The method of claim 1, wherein said weights may be assigned by either a linear or non-linear distribution.

3. The method of claim 1, wherein step (a) comprises:

designating a local representative color (LRC) value to each block if the first predetermined condition is satisfied;

detecting the number of blocks with the designated LRC value and using the detected number as the characteristic.

4. The method of claim 1, wherein step (b) further comprises the step of assigning greater weight to a search algorithm based upon a global histogram if the detected number of blocks is less than or equal to a first reference number.

5. The method of claim 4, wherein step (b) further comprises the step of assigning a greater weight to a search algorithm based upon a local histogram if the detected number of blocks is greater than the first reference number.

6. The method of claim 4, wherein step (b) further comprises the steps of assigning a greater weight to a search algorithm based upon a local histogram if the detected number of blocks is greater than the first reference number and greater than a second reference number;

otherwise assigning a greater weight to a search algorithm based upon a major color region.

7. The method of claim 1, wherein the designating the LRC value comprises:

(aa) building a color histogram for each block and designating the maximum color value of a color histogram as a LRC value of a corresponding block if the maximum color value is greater than a first reference value;

otherwise

(bb) building hue group histograms from adjacent blocks of the block, selecting a maximum color group from the hue group histograms and determining the mean value of the maximum color group, and designating the mean value of the maximum color group as a LRC value of the block if the mean value of the maximum color group is greater than a second reference value;

otherwise

(cc) building local hue group histograms and determining a local representative hue group value from the local hue group histograms, and designating the mean value of the local representative hue group value as a LRC value if the local representative hue group value is greater than or equal to a third reference value and if a distribution of the local representative hue group is greater than or equal to a fourth reference value;

otherwise designating the block as a “

don'"'"'t care”

region; and

(dd) repeating steps (aa) through (cc) until the last block of the image is processed.

8. A method for automatically choosing a search algorithm without any user input in a content based image searching system, comprising:

(a) determining a characteristic of an image based upon a global histogram, a local histogram, and a major color information, wherein the step (a) comprises,

dividing the input image into a plurality of blocks, and

detecting a number of blocks with a designated color value assigned according to a first predetermined condition;

(b) evaluating an effectiveness of a plurality of search algorithms according to the determined characteristic, wherein step (b) comprises assigning greater weight to a search algorithm based upon a global histogram if the detected number of blocks meets a second predetermined condition;

(c) choosing one search algorithm based on the effectiveness; and

(d) utilizing the chosen search algorithm to perform an image search.

9. The method of claim 8, wherein step (a) comprises:

dividing the input image into equal blocks;

designating a local representative color (LRC) value to each block if the first predetermined condition is satisfied; and

detecting the number of blocks with a designated LRC value and using the detected number as the characteristic representative of the global histogram, the local histogram and the major color information.

10. A method for automatically determining a search algorithm without any user input in a content based image searching system, comprising:

(a) determining a characteristic of an image based upon a global histogram, a local histogram, and a major color information;

(b) evaluating an effectiveness of a plurality of search algorithms according to the determined characteristic;

(c) assigning a relative value C within a prescribed range based on the evaluated effectiveness;

(d) comparing the relative value C to a first reference value R within the prescribed range; and

(e) selecting one of the search algorithms based on the comparison, wherein step (a) comprises,

dividing the input image into a plurality of blocks;

designating a local representative color (LRC) value to each block if a first predetermined condition is satisfied, and

detecting the number of blocks with a designated LRC value and using the detected number as the characteristic, wherein the designating the LRC value comprises,

(aa) building color histogram for each blocks and designating the maximum color value of a color histogram as a LRC value of a corresponding block if the maximum color value is greater than a first reference value, otherwise

(bb) building hue group histograms from adjacent blocks of the block, selecting a maximum color group from the hue group histograms and determining the mean value of the maximum color group, and designating the mean value of the maximum color group as a LRC value of the block if the mean value of the maximum color group is greater than a second reference value, otherwise

(cc) building local hue group histograms and determining a local representative hue group value from the local hue group histograms, and designating the mean value of the local representative hue group value as a LRC value if the local representative hue group value is greater than or equal to a third reference value and if a distribution of the local representative hue group is greater than or equal to a fourth reference value;

otherwise designating the block as a “

don'"'"'t care”

region, and

(dd) repeating steps (aa) through (cc) until the last block of the image is processed.

11. The method of claim 10, wherein the characteristic is a number of colored blocks having at least one of a plurality of reference colors greater than a prescribed value, wherein a global histogram search is chosen if the condition C<

R is satisfied.

12. The method of claim 11, further comprising comparing the relative value C to a second reference value S that is greater than the first reference value R in the prescribed range, where a local histogram search is chosen if the condition C>

S is satisfied.