Method and device for seeking images based on the content taking into account the content of regions of interest

• US 7,117,226 B2
• Filed: 11/30/2000
• Issued: 10/03/2006
• Est. Priority Date: 12/03/1999
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Labelle, Lilian
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US09/726,023
• Publication Number:
  US 20010024517A1
• Time in Patent Office: 2,133 Days
• Field of Search: 382/165, 382/209, 707/3, 707/6, 707/5, 707/10, 707/101, 707/102, 707/103.R, 707/104.1
• US Class Current: 382/282
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method of seeking images, from an example image, from amongst a plurality of images stored in a database, each of the stored images being associated with an index, representing at least one characteristic of the visual content of the image, includes the following steps: a step of receiving a data item of a second type representing the location of at least one region of interest in the example image; a step of receiving, for each region of interest, a data item of a third type indicating a type of taking into account of the content of the region of interest for the seeking of images; a step of calculating an index of the example image, representing at least one characteristic of the visual content of the example image, the method of calculating this index depending on the data item of the second type and the data items of the third type; a step of calculating a similarity between the example image and each of the images from amongst at least one subset of the stored images, this similarity being calculated from the index associated with the stored image and the index associated with the example image; and a step of supplying at least one image, referred to as the result image, of the database, this result image being selected from amongst the images in the database according to its degree of similarity with the example image.

Claims

1. Method of seeking images, from an example image containing a plurality of regions of interest, from amongst a plurality of images stored in a database, each of the stored images being associated with a data item of a first type, referred to as an index of the stored image, representing at least one characteristic of the visual content of the image, said method comprising the following steps:

for each region of interest, receiving a data item of a second type indicative of a user selection for a type of taking into account of the content of said region of interest for the seeking of images;

calculating a data item of a third type, referred to as the index of the example image, representing at least one characteristic of the visual content of the example image, the structure of said data item of the third type and the method of calculating said data item of the third type depending on said data items of the second type;

selecting an image research strategy according to said data items of the second type;

calculating a similarity, according to the selected image research strategy, between the example image and each of the images amongst at least one subset of the stored images, said similarity being calculated from said data item of the first type associated with the stored image and the data item of the third type associated with the example image; and

supplying at least one image, referred to as the result image, in the database, said at least one result image being selected from amongst said stored images in the database according to its degree of similarity with said example image.

2. Image search method according to claim 1, wherein said data item of the second type associated with a region of interest, is a scalar data item which can take all the values lying between a predefined lower value V_min, and a predefined higher value V_max, and wherein:

if said data item of the second type is equal to the predefined lower value V_min, the content of the images sought must not be similar to the content of the corresponding region of interest,

if said data item of the second type is equal to the predefined higher value V_max, the content of the images sought must be similar to the content of the corresponding region of interest, and

if said data item of the second type lies strictly between the lower predefined value V_min and the higher predefined value V_max, the content of the images sought must be more or less similar to that of the corresponding region of interest depending on whether the value of said data item of the second type is close to V_max or is close to V_min, the overall content of the example image also having to be taken into consideration.

3. Image search method according to claim 1 or 2, wherein said data item of the first type, called index of the stored image, associated with each of said stored images, consists of a histogram of colours relating to the global content of the image.

4. Image search method according to claim 3, wherein, if all said data items of the second type are equal to said lower predefined value V_min, or if all said data of the second type are equal to said higher predefined value V_max, or if each of said data of the second type is equal to V_min or equal to V_max, then said step of calculating a data item of a third type, called index of the example image, includes a step of calculating a vector, each component of which consists of the histogram of colours representing the visual content of one of said regions of interest, said vector constituting the index of said example image.

5. Image search method according to claim 4, wherein if all said data of the second type are strictly between said lower predefined value V_min and said higher predefined value V_max, then said step of calculating a data item of a third type, called index of the example image, includes the following steps:

calculating a matrix with M rows and M columns, where M is a integer number designating the number of colours available, each element of whose diagonal corresponds to one of the M colours available, each of the elements of the diagonal having a value which is calculated as a function of the dominant character of the colour associated with said element in said at least one region of interest associated with said example image, and of said data item of the second type associated with said at least one region of interest;

calculating the histogram of colours representing the overall visual content of said example image; and

defining said index of the example image as being the result of the product of said matrix and said histogram of colours representing the overall visual content of said example image.

6. Image search method according to claim 5, wherein, when said data of the second type are not all equal to said lower predefined value V_min, and are also not all equal to said higher predefined value V_max, and are also not each equal either to V_min or to V_max, and also not all strictly between V_min and V_max, said index of the example image consists of the result of the product of said matrix and said histogram of colours representing the overall visual content of said example image, and of said vector, each component of which consists of the histogram of colours representing the visual content of one of said regions of interest.

7. Image search method according to claim 6, wherein said step of calculating a similarity between the example image and each of the images amongst at least one subset of the stored images, includes the step of calculating a similarity, denoted SIM₁, obtained by means of the following formula:

SIM₁(D)=Max[H_M(D)∩

H_M(ROI_r^S0)

in which H_M(D) designates a histogram of colours calculated for the stored image under consideration;

ROI_R^S0 designates any region of interest in the example image for which the associated data item of the second type is equal to V_min;

H_M(ROI_R^S0) designates a histogram of colours calculated for this region of interest;

the operator ∩

designates the intersection operation between histograms; and

the function Max takes the largest value obtained by these intersections.

8. Image search method according to claim 6, wherein said step of calculating a similarity between the example image and each of the images amongst at least one subset of the stored images includes the step of calculating a similarity, denoted SIM2, obtained by means of the following formula:

SIM₂(D)=Max[H_M(D)∩

H_M(ROI_r^S1)]

in which H_M(D) designates a histogram of colours calculated for the stored image under consideration;

ROI_r^S1 designates any region of interest in the example image for which the associated data item of the second type is equal to V_max;

H_M(ROI_r^S1) designates a histogram of colours calculated for this region of interest;

the operator ∩

designates the intersection operation between histograms, and the function Max takes the largest value obtained by these intersections.

9. Image search method according to claim 6, wherein said step of calculating a similarity between the example image and each of the images amongst at least one subset of the stored images includes the step of calculating a similarity, denoted SIM₃, obtained by means of the following formula:

SIM₃(D)=H_M(D)∩

X(Q) with X(Q)=W·

H_M(Q)

in which H_M(D) designates a histogram of colours calculated for the stored image under consideration;

W designates said matrix;

H_M(Q) is a histogram of colours representing the global visual content of said example image; and

the operator ∩

designates the intersection operation between histograms.

10. Image search method according to claim 1, wherein the selected image research strategy uses a measurement of similarity selected from amongst a plurality of possible measurements of similarity based on said at least one data item of the second type.

11. Image search method according to claim 1 or 10, further comprising a step of receiving a data item of a fourth type representing the location of at least one region of interest in the example image.

12. Image search method according to claim 11, wherein said data item of the fourth type representing the location of at least one region of interest in the example image consists of a set of two-dimensional points indicative of the shape of said at least one region of interest and its location in the image plane of said example image.

13. Device seeking images, from an example image, from amongst a plurality of images stored in a database, said device comprising means adapted to implement an image search method according to claim 1 or 2.

15. Computer comprising means adapted to implement an image search method according to claim 1 or 2.

16. Computer comprising an image search device according to claim 13 or 14.

17. Image search method according to claim 1, further comprising a step of classifying the plurality of regions of interest into a plurality of sets depending on the data items of the second type respectively associated therewith, wherein the structure of said data item of the third type and the method of calculating said data item of the third type are selected based on the result of the step of classifying.

18. Image search method according to claim 1, further comprising a step of classifying the plurality of regions of interest into a plurality of sets depending on the data items of the second type respectively associated therewith, wherein the selected image research strategy uses a measurement of similarity selected from amongst a plurality of possible measurement of similarities based on the result of the step of classifying.

14. Device for seeking images, from an example image containing a plurality of regions of interest, from amongst a plurality of images stored in a database, each of the stored images being associated with a data item of a first type, referred to as an index of the stored image, representing at least one characteristic of the visual content of the image, said device comprising:

means for receiving, for each region of interest, a data item of a second type indicative of a user selection for a type of taking into account of the content of said region of interest for the seeking of images;

means for calculating a data item of a third type, referred to as the index of the example image, representing at least one characteristic of the visual content of the example image, the structure of said data item of the third type and the calculation of said data item of the third type depending on said data items of the second type;

means for selecting an image research strategy according to said data items of the second type;

means for calculating a similarity, according to the selected research strategy, between the example image and each of the images amongst at least one subset of the stored images, based on said data item of the first type associated with the stored image and on the data item of the third type associated with the example image; and

means for supplying at least one image, referred to as the result image, in the database, based on a selection from amongst said stored images in the database according to a degree of similarity of said result image with said example image.