Image retrieval method based on combination of color and texture features

• US 7,062,083 B2
• Filed: 01/09/2002
• Issued: 06/13/2006
• Est. Priority Date: 01/09/2001
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lim, Choi Yang, Ik, Cho Nam, Won, Kwak Jung
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Hung, Yubin
• Application Number:
  US10/040,621
• Publication Number:
  US 20020122587A1
• Time in Patent Office: 1,616 Days
• Field of Search: 382/164, 382/165, 382/190, 382/195, 382257-260, 382/279, 382/305, 382/220, 348/582, 707/6
• US Class Current: 382/164
• 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 weighted color distances and one or more weighted texture distances by considering human visual perception attributes,

wherein the one or more weighted color distances and the one or more weighted texture distances are obtained by applying predetermined weighting factor to each texture distance and to each color distance, and

wherein the predetermined weighting factor applied to said each texture distance is determined based on an area of an initial sample region extracted from the iuery image and an area of a sample region extracted from each data image.

2. The method according to claim 1, wherein said combining of the one or more weighted color distances and the one or more weighted texture distances comprises weighing the one or more weighted color distances and the one or more weighted texture distances with differing weighing factors, said variation of the weighting factors reflect the human visual perception attributes.

3. 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 first 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 applying a second set of differing weighing factors that reflect human visual perception attributes; and

(d) determining the data image similar to the query image using the feature distances,

wherein the first predetermined weighting factor applied to said each texture distance is determined based on an area of an initial sample region extracted from the query image and an area of a sample region extracted from each data image.

4. The method of claim 3, 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.

5. The method of claim 4, 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.

6. The method of claim 5, 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.

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

f_c(I_k)={{overscore (c)}_k1, p_ki), ({overscore (c)}_k2, p_k2), . . . , ({overscore (c)}_KNk, pKN_K)}

wherein k is a positive integer indicating a serial number of each region, {overscore (c)}_ki is an i-th representative color vector of a k-th region i=(1, 2, . . . , N_K), P_ki is a percentage of the ith 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.

8. The method of claim 7, 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:

$d_c<br><br>\left(I_1,I_2\right)=\underset{i=1}{\overset{N_1}{\sum <br><br>}}<br><br><br><br>p_{1<br><br>i}^2+\underset{i=1}{\overset{N_2}{\sum <br><br>}}<br><br><br><br>p_{2<br><br>i}^2-\underset{i=1}{\overset{N_1}{\sum <br><br>}}<br><br><br><br>\underset{j=1}{\overset{N_2}{\sum <br><br>}}<br><br><br><br>2<br><br>a_{1<br><br>i,2<br><br>j}<br><br>p_{1<br><br>i}<br><br>p_{2<br><br>j}$

wherein when T_d is a maximum distance by which a similarity of two colors is determined, α

is a predetermined scaling coefficient, d_max=α

α

T_d, and d_ij is the Euclidean distance ∥

c_i–

c_j∥

between two color vectors c_i, and c_j, such that

$a_{\mathrm{ij}}=1-\frac{d_{\mathrm{ij}}}{d_{\max }}$

if d_ij≦

T_d,

and

α

_lj=0 if d_lj>

T_d.

9. The method of claim 5, wherein step (a2) uses a Gabor function.

10. The method of claim 9, 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.

11. The method of claim 10, 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 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.

12. The method of claim 11, 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:

$d_t<br><br>\left(I_1,I_2\right)=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br><br><br>\frac{m_{1<br><br>\mathrm{ij}}-m_{2<br><br>\mathrm{ij}}}{\mathrm{\sigma <br><br>}<br><br>\left(m_{\mathrm{ij}}\right)}<br><br>+\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br><br><br><br><br>\frac{{\mathrm{\sigma <br><br>}}_{1<br><br>\mathrm{ij}}-{\mathrm{\sigma <br><br>}}_{2<br><br>\mathrm{ij}}}{\mathrm{\sigma <br><br>}<br><br>\left({\mathrm{\sigma <br><br>}}_{\mathrm{ij}}\right)}<br><br>$

where σ

(m_ij) and σ

(σ

_ij) are the standard deviations for all m_ij and σ

_ij, respectively.

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

14. The method of claim 13, 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.

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

16. The method of claim 13, 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.

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

18. The method of claim 17, 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.

19. The method of claim 4, 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.

20. The method of claim 19, 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 l×

l 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><br><br>p_{\mathrm{ij}}<br><br>\left(x,y\right)\in <br><br>I_k<br><br><br><br>\mathrm{for}<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,$

being a result of applying the floor function,

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

where [m/l] is a result of applying the ceiling function, 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).

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

(ph-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)}_n-1, {M_grid^d(i−

1, j)}_n-1, {M_grid^d(i, j+1)}_n-1, {M_grid^d(i+1, j)}_n-1)+1,

if {M_grid^d(i, j)}_n-1={M_grid^d(i, j)}_n, M_grind^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

$\left(a,b\right)=\underset{\left(i,j\right)}{\arg <br><br><br><br>\max }<br><br>\left\{M_{\mathrm{grid}}^d<br><br>\left(i,j\right)\right\},$

to satisfy the relation M_grid^d(i, j)<

0 until a maximum area rectangle is extracted.

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

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

24. The method of claim 4, 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.

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

${\mathrm{\omega <br><br>}}_c=1-\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>p_{\mathrm{qi}}<br><br>{\log }_{10}<br><br>\left(\frac{1}{p_{\mathrm{qi}}}\right)$

wherein p_qi is a percentage of an i-th representative color of one of the first regions of the query image.

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

$d_t^{\mathrm{\prime <br><br>}}<br><br>\left(I_q,I_l\right)=a^{\text{(}<br><br>\frac{A<br><br>\left(s\right)}{A<br><br>\left(I_l\right)}+\left(\mathrm{count}<br><br><br><br>\left(I_l\right)-1\right)}<br><br>d_t<br><br>\left(I_q,I_l\right)$

wherein I_q denotes the query image or each first region of the query image, s denotes a sample region of a desired size, A(·

) denotes the area of the sample region of the desired size, count(·

) is the number of wrappings done to obtain the sample region of the desired size, and α

is a constant, and where d_t(I_q,I_l) is a distance function for two images based on their texture vectors.

27. The method of claim 24, 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:

${\mathrm{\omega <br><br>}}_t=\frac{1}{a^{\left(\frac{A<br><br>\left(s\right)}{A<br><br>\left(I_q\right)}+\left(\mathrm{count}<br><br>\left(I_q\right)-1\right)\right)}}$

wherein I_q denotes the query image or each first region of the query image, s denotes a sample region of a desired size, A(·

) denotes the area of the sample region of the desired size, count(·

) is the number of wrappings done to obtain the sample region of the desired size, and α

is a constant.

29. The method of claim 24, 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

$k\times <br><br>\frac{{\mathrm{\mu <br><br>}}_c}{{\mathrm{\sigma <br><br>}}_c}\le <br><br>\frac{{\mathrm{\mu <br><br>}}_t}{{\mathrm{\sigma <br><br>}}_t},$

wherein k is a constant, is satisfied.

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

$d<br><br>\left(I_q,I_l\right)=W_c<br><br>d_c<br><br>\left(I_q,I_l\right)<br><br>\left(1+\frac{2}{\mathrm{\pi <br><br>}}<br><br>{\tan }^{-1}<br><br>\frac{d_t^{\mathrm{\prime <br><br>}}<br><br>\left(I_q,I_l\right)}{d_c<br><br>\left(I_q,I_l\right)}\right)+W_t<br><br>d_t^{\mathrm{\prime <br><br>}}<br><br>\left(I_q,I_l\right)<br><br>\left(1+\frac{2}{\mathrm{\pi <br><br>}}<br><br>{\tan }^{-1}<br><br>\frac{d_c<br><br>\left(I_q,I_l\right)}{d_t^{\mathrm{\prime <br><br>}}<br><br>\left(I_q,I_l\right)}\right)<br><br><br><br>\mathrm{wherein}<br><br><br><br>W_c=\frac{{\mathrm{\omega <br><br>}}_c}{{\mathrm{\omega <br><br>}}_c+{\mathrm{\omega <br><br>}}_t}<br><br><br><br>\mathrm{and}<br><br><br><br>W_t=\frac{{\mathrm{\omega <br><br>}}_t}{{\mathrm{\omega <br><br>}}_c+{\mathrm{\omega <br><br>}}_t}.$

wherein ω

_c and ω

_t are weighing factors of the color distances and texture distances respectively, where d_c(I_q, I_l) and where d_t′

(I_q, I_l) represent normalized distance functions for two image regions based on their color and texture vectors, respectively.

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