Image retrieval method based on combination of color and image features

• US 20020122587A1
• Filed: 01/09/2002
• Published: 09/05/2002
• Est. Priority Date: 01/09/2001
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lim, Choi Yang, Ik, Cho Nam, Won, Kwak Jung
• Granted Patent: US 7,062,083 B2
• Time in Patent Office: Days
• US Class Current: 382/165
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An image retrieval method with improved performance in which a data image similar to a query image is retrieved by appropriately combining color and texture features. The method for retrieving a data image similar to a query image in an image database containing a plurality of data images involves: calculating color and texture distances between a query image and each data image in the image database; weighting the calculated color and texture distances with predetermined weighting factors; calculating a feature distance between the query image and each data image by combining the weighted color and texture distances by considering human visual perception attributes; and determining the data image similar to the query image using the feature distance. According to the image retrieval method, data images similar to a query image can be retrieved based on the human visual perception mechanism by combining both color and texture features extracted from image regions. In particular, the image region based retrieval enables accurate retrieval of more objects and many kinds of information from a single image.

Claims

1. A method for retrieving a data image similar to a query image using a feature distance calculated by combining one or more color distances and one or more texture distances by considering human visual perception attributes.

2. A method for retrieving a data image similar to a query image in an image database containing a plurality of data images, the method comprising:

(a) calculating a plurality of color distances and a plurality of texture distances between a query image and each data image in the image database;

(b) weighting each of the calculated color distances and texture distances with a respective predetermined weighting factor;

(c) calculating a feature distance between the query image and each data image by combining the weighted color distances and the weighted texture distances by considering human visual perception attributes; and

(d) determining the data image similar to the query image using the feature distance.

3. The method of claim 2, before step (a), further comprising:

(pa-1) segmenting the query image and each data image into a plurality of first regions using a plurality of color features; and

(pa-2) determining a plurality of sample regions in the query image and each data image for extraction of a plurality of texture features.

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

(a1) generating a plurality of color vectors of the first regions using the color features and calculating a plurality of color distances; and

(a2) generating a plurality of texture vectors of the sample regions using the texture features and calculating a plurality of texture distances.

5. The method of claim 3, wherein step (pa-1) comprises quantizing a plurality of color vectors of the query image and each data image.

6. The method of claim 5, wherein quantizing the color vectors comprises:

(pa-1-1) performing a peer group filtering on the query image and each data image for noise removal and smoothing effects; and

(pa-1-2) clustering a plurality of filtered pixel values of the query image and each data image using a generalized Lloyd algorithm.

7. The method of claim 5, further comprising:

defining a J-value indicating a color uniformity in each pixel of a plurality of pixels of the query image and each data image, which have undergone quantization;

storing the J-value in each pixel of the query image and each data image to obtain a plurality of J-images;

segmenting each J-image into a plurality of second regions by a predetermined segmentation method;

repeating the segmentation of each J-image to obtain a map of one or more over-segmented regions for each J-image; and

obtaining a final map for each J-image by merging the over-segmented regions based on a correlation of color.

8. The method of claim 7, further comprising indexing a feature vector space by a representative color and a percentage of the representative color in each second region.

9. The method of claim 6, wherein step (pa-1-2) comprises applying a predetermined algorithm to increase the number of resulting clusters or to merge the resulting clusters.

10. The method of claim 4, wherein the color features are expressed by a color feature descriptor f_c(I_k) with a representative color vector and a percentage of the representative color vector for each first region.

11. The method of claim 10, wherein the color feature descriptor f_c(I_k) is expressed by:

f_c(I_k)={({overscore (c)}_k1,p_k1),({overscore (c)}_k2,p_k2), . . . , ({overscore (c)}_kNk,p_kNk)}

wherein k is a positive integer indicating a serial number of each region, {overscore (c)}_k1 is an i-th representative color vector of a k-th region (i=1, 2, . . . , N), p_k1 is a percentage of the i-th color representative color vector in the k-th region, and N_k is the number of the representative color vectors in the k-th region.

12. The method of claim 8, wherein indexing the feature vector space comprises:

assigning a plurality of representative colors to a plurality of grid points in a color space having a grid structure; and

storing the result of the assignment as a table in a database.

13. The method of claim 11, wherein the color distance between each color vector of each region of the query image and each color vector of each region of each data image is calculated using:

14. The method of claim 4, wherein step (a2) uses a Gabor function.

15. The method of claim 14, wherein, in step (a2), the texture vectors of the plurality of sample regions are generated using the Gabor function having N frequency channels and M orientation channels, where N and M are both predetermined positive integers.

16. The method of claim 15, wherein the texture features are expressed by a texture feature descriptor f_t(I_k):

f_t(I_k)={(m_k11,σ

_k11), (m_k12,σ

_k12), . . . , (m_k1M,σ

_k1M),(m_k21,σ

_k21), . . . , (m_kij,σ

_kij), . . . , (m_kNM,σ

_kNM)}

wherein m_kij is a mean value of a plurality of pixel values of the i-th frequency channel and the j-th orientation channel for a sample region I_k, and σ

_kij is a deviation of the pixel values of the i-th frequency channel and the j-th orientation channel for the sample region I_k.

17. The method of claim 16, wherein, in step (a2), the texture distance between each color vector of each region of the query image and each color vector of each sample region of each data image is calculated using:

18. The method of claim 3, wherein step (pa-2) comprises:

(pb-1) obtaining a grid map of the query image and each data image; and

(pb-2) obtaining a texture sample of a desired size for each sample region based on the grid map.

19. The method of claim 18, wherein step (pb-1) comprises:

(pb-1-1) taking a rectangle M(i, j) having largest side lengths for a sample region, wherein 0≦

i≦

n and 0≦

j≦

m;

(pb-1-2) dividing the rectangle M(i, j) into a plurality of sub-rectangles each having a 1×

1 size; and

(pb-1-3) obtaining a grid map for the sample region using a predetermined function which outputs 1 if all the divided grids belong to the sample region, and otherwise, outputs 0, the predetermined function expressed by;

$M_{\mathrm{grid}}<br><br>\left(i,j\right)=\{\begin{array}{cc}1& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>p_{\mathrm{ij}}<br><br>\left(x,y\right)⋐<br><br>I_k<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>\left(x,y\right)\\ 0& \mathrm{otherwise}\end{array}$

wherein

$0\le <br><br>i\le <br><br>\left[\frac{n}{l}\right]-1,0\le <br><br>j\le <br><br>\left[\frac{m}{l}\right]-1,$

0≦

x≦

l−

1, 0≦

y≦

l−

1, and p_ij(x, y) is a point that belongs to rectangle M(il+x, jl+y).

20. The method of claim 19, after step (pb-1-3), further comprising:

(pb-1-4) transforming the grid map obtained in step (pb-1-3) to a grid distance map by repeating computations with;

{M_grid^d(i,j)}₀=M_grid(i,j),

and

{M_grid^d(i,j)}_n=min({M_grid^d(i,j−

1)}<sub>n−

1</sub>,{M_grid^d(i−

1,j)}<sub>n−

1</sub>,{M_grid^d(i,j+1)}<sub>n−

1</sub>,{M_grid^d(i+1,j)}<sub>n−

1</sub>)+1, if {M_grid^d(i,j)}<sub>n−

1</sub>={M=hu d_grid(i,j)}_n,M^grid_d(i,j)={M_grid^d(i,j)}_n,

and

(pb-1-5) performing region growing in every direction from a seed of the grid map, which has the largest distance in the grid and is expressed by (a, b)=_{(i, j)}^{arg max}{M_grid^d(i, j)}, to satisfy the relation M_grid^d(i, j)>

0 until a maximum area rectangle is extracted.

21. The method of claim 20, further comprising fitting the maximum area rectangle extracted in step (pb-1-5) to the desired size of the texture sample by wrapping.

22. The method of claim 20, further comprising fitting the maximum area rectangle extracted in step (pb-1-5) to the desired size of the texture sample by mirroring.

23. The method of claim 3, wherein step (b) comprises:

(b-1) placing each of the color distances and the texture distances in a 2-dimensional vector space, each vector space defined by the respective distances and associated predetermined weighting factors; and

(b-2) projecting the result of the placement onto the 2-dimensional vector spaces onto a 1-dimensional distance space based on the human visual perception mechanism.

24. The method of claim 2, wherein the predetermined weighting factor to the color distance is determined based on a distribution of representative colors.

25. The method of claim 23, wherein the predetermined weighting factor to the color distance is determined by:

26. The method of claim 23, wherein each texture distance is defined by:

27. The method of claim 23, wherein the predetermined weighting factor applied to each texture distance is determined based on an area of an initial sample region extracted from the query image and the area of a sample region extracted from each data image.

28. The method of claim 27, wherein the predetermined weighting factor applied to each texture distance is determined by:

29. The method of claim 23, before step (b-2), further comprising normalizing each of the color distances and the texture distances.

30. The method of claim 29, wherein normalizing each of the color distances and the texture distances is performed using a Gaussian normalization.

31. The method of claim 30, wherein normalizing each of the color distances and the texture distances comprises:

wherein v_k is a Gaussian sequence, performing a normalization within a range of [−

1, 1] using

$v_{m,k}=\frac{v_{m,k}-{\mathrm{\mu <br><br>}}_k}{3<br><br>{\mathrm{\sigma <br><br>}}_k}$

based on a mean value μ

_k and a deviation σ

_k of the sequence v_k; and

mapping the result of the normalization into a range of [0, 1] using

$v_{m,k}^{\mathrm{\prime <br><br>}}=\frac{v_{m,k}+1}{2}.$

32. The method of claim 31, wherein normalizing each of the color distances and the texture distances comprises normalizing the texture distances by updating the mean value μ

_t and the deviation σ

_t of the texture distances by excluding a largest texture distance until the condition of

33. The method of claim 23, wherein step (b-2) comprises projecting the color distances and the texture distances onto a 1-dimensional distance space using: