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

• US 20010024517A1
• Filed: 11/30/2000
• Published: 09/27/2001
• Est. Priority Date: 12/03/1999
• Status: Active Grant

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Labelle, Lilian
• Granted Patent: US 7,117,226 B2
• Time in Patent Office: Days
• US Class Current: 382/170
• 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, 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:

receiving a data item of a second type representing the location of at least one region of interest in the example image;

for each region of interest, ROI_r, receiving a data item of a third type, V_r, indicative of a type of taking into account of the content of the said region of interest for the seeking of images;

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

calculating a similarity 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 fourth type associated with the example image;

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 third type V_r associated with a region of interest ROI_r, 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 third type V_r 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 ROI_r,

if said data item of the third type V_r 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 ROI_r, and

if said data item of the third type V_r 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 ROI_r depending on whether the value of V_r 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 third type are equal to said lower predefined value V_min, or if all said data of the third type are equal to said higher predefined value V_max, or if each of said data of the third type is equal to V_min or equal to V_max, then said step of calculating a data item of a fourth type, called index of the example image, includes a step of calculating a vector, (G_R(Q)), 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 3

or

4

, wherein if all said data of the third 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 fourth type, called index of the example image, includes the following steps:

calculating a matrix (W) 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 third type associated with said at least one region of interest;

calculating the histogram of colours (H_M(Q)) representing the overall visual content of said example image (Q);

defining said index of the example image (Q) as being the result (X(Q)) of the product of said matrix (W) and said histogram of colours (H_M(Q)) representing the overall visual content of said example image (Q).

6. Image search method according to

claim 5

when it is dependent on

claim 4

, wherein, when said data of the third 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 (X(Q)) of the product of said matrix (W) and said histogram of colours (H_M(Q)) representing the overall visual content of said example image (Q), and of said vector, (G_R(Q)), 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 third type V_r 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

or

7

, 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^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 third type V_r 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 any one of

claim 6

,

7

or 8, 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 (Q); and

the operator ∩

designates the intersection operation between histograms.

10. Image search method according to any one of the preceding claims, wherein said data item of the second 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.

11. Device for 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 any one of the preceding claims.

12. Computer comprising means adapted to implement an image search method according to any one of

claims 1

to

10

.

13. Computer comprising an image search device according to

claim 11

.