Non-linear quantization and similarity matching methods for retrieving image data

• US 7,295,718 B2
• Filed: 10/18/2001
• Issued: 11/13/2007
• Est. Priority Date: 10/21/2000
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Park, Soo-Jun, Jang, Myung Gil, Won, Chee Sun, Kim, Hyunjin, Park, Sung Hee, Park, Dong-Kwon
• Primary Examiner(s): LAROSE, COLIN M
• Application Number:
  US09/978,668
• Publication Number:
  US 20020136454A1
• Time in Patent Office: 2,217 Days
• Field of Search: 382/168, 382/170, 382/305
• US Class Current: 382/305
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]

Abstract

A method for constructing a database having image information representing a plurality of images including the steps of: a) calculating L×5 number of normalized edge histogram bins to generate L number of edge histograms of a target image, wherein each edge histogram has five normalized edge histogram bins and represents a spatial distribution of five reference edges in a sub-image and L is a positive integer, wherein the reference edges include four directional edges and a non-directional edge; b) non-linearly quantizing the L×5 number of normalized edge histogram bins to generate L×5 number of quantization index values for the target image; c) storing the L×5 number of quantization index values to the database; and d) repeating the steps a) to c) until all of the stored images are processed to thereby construct the database having the image information.

Claims

1. A method for constructing a database having image information representing a plurality of images, the method comprising the steps of:

a) calculating L×

5 number of normalized edge histogram bins to generate L number of edge histograms of a target image, wherein said each edge histogram has five normalized edge histogram bins and represents a spatial distribution of five reference edges in a sub-image and L is a positive integer, wherein the reference edges include four directional edges and a non-directional edge;

b) non-linearly quantizing the L×

5 number of normalized edge histogram bins to generate L×

5 number of quantization index values for the target image;

c) storing the L×

5 number of quantization index values to the database; and

d) repeating the steps a) to c) until all of the stored imaged are processed to thereby construct the database having the image information.

2. The method as recited in claim 1, wherein the directional edges include a vertical edge, a horizontal edge, a 45 degree edge and a 135 degree edge, and the non-directional edge represents an edge of undesignated direction excluding the four directional edges.

3. The method as recited in claim 2, wherein the vertical edge, the horizontal edge, the 45 degree edge, the 135 degree edge and the non-directional edge are, respectively, expressed as:

4. The method as recited in claim 3, wherein the step a) includes the steps of:

a1) partitioning the target image into L number of sub-images, wherein each sub-image is further partitioned into S×

K number of image-blocks, S and K being positive integers; and

a2) assigning one of the reference edges to each image-block to thereby generate L number of edge histograms for the target image, wherein each edge histogram includes the L×

5 edge histogram bins; and

a3) normalizing the edge histogram bins by S×

K which is the number of the image-blocks contained in one sub-image, to thereby generate L×

5 number of normalized edge histogram bins, each normalized edge histogram bin having a real number between 0 and 1.

5. The method as recited in claim 4, wherein the step a1) includes the steps of:

a1-1) dividing the target image into N×

N non-overlapping sub-images to thereby form L number of rectangular sub-images, N being a positive integer; and

a1-2) dividing each sub-image into S×

K non-overlapping blocks to thereby form S×

K number of rectangular image-blocks.

6. The method as recited in claim 5, wherein the step a2) includes the steps of:

a2-1) assigning one of the reference edges to each image block; and

a2-2) counting the number of each reference edge included in each sub-image to generate the L number of the edge histograms for the target image.

7. The method as recited in claim 6, wherein the step a2-1) includes the steps of:

a2-11) dividing each image-block into 2×

2 sub-blocks;

a2-12) assigning a corresponding filter coefficient to each sub-block;

a2-13) calculating a set of five edge magnitudes corresponding to five edges for each image-block by using the filter coefficient; and

a2-14) expressing the image-block as an edge having a maximum edge magnitude by comparing the calculated edge magnitudes to each other.

8. The method as recited in claim 7, wherein the five edge magnitudes are obtained by using five equations, which are expressed as:

$\begin{array}{c}{m}_v<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_v<br><br>\left(k\right)<br><br>;<br><br>\\ m_h<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_h<br><br>\left(k\right)<br><br>;<br><br>\\ m_{d-45}<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_{d-45}<br><br>\left(k\right)<br><br>;<br><br>\\ m_{d-135}<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_{d-135}<br><br>\left(k\right)<br><br>;<br><br><br><br><br><br>\mathrm{and}\\ m_{\mathrm{nd}}<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_{\mathrm{nd}}<br><br>\left(k\right)<br><br>,<br><br>\mathrm{where}<br><br><br><br>m_v<br><br>\left(i,j\right),m_h<br><br>\left(i,j\right),m_{d-45}<br><br>\left(i,j\right),\end{array}$

m_d-45(i, j), m_d-135(i, j) and m_nd(i, j), respectively, denote vertical, horizontal, 45 degree, 135 degree and non-directional edge magnitudes for a (i, j)^th image-block;

α

_k(i, j) denotes an average gray level for a sub-block assigned k in the (i, j)^th image-block and ƒ

_v(k), ƒ

_h(k), ƒ

_d-45(k), ƒ

_d-135(k) and ƒ

_nd(k) denote, respectively, filter coefficients for the vertical, horizontal, 45 degree, 135 degree and non-directional edges, where k represents a number assigned to each sub-block.

9. The method as recited in claim 7, wherein the image block is expressed as containing no edge when the maximum edge magnitude is less than a predetermined threshold value.

10. The method as recited in claim 6, wherein semantics of said each edge histogram bin of BinCounts is defined as:

Edge histogram bin Semantics BinCounts[0] Vertical edges in sub-image (0,0) BinCounts[1] Horizontal edges in sub-image (0,0) BinCounts[2] 45 degree edges in sub-image (0,0) BinCounts[3] 135 degree edges in sub-image (0,0) BinCounts[4] Non-directional edges in sub-image (0,0) BinCounts[5] Vertical edges in sub-image (0,1) . . . . . . BinCounts[74] Non-directional edges in sub-image (3,2) BinCounts[75] Vertical edges in sub-image (3,3) BinCounts[76] Horizontal edges in sub-image (3,3) BinCounts[77] 45 degree edges in sub-image (3,3) BinCounts[78] 135 degree edges in sub-image (3,3) BinCounts[79] Non-directional edges in sub-image (3,3).

11. The method as recited in claim 5, wherein said N is 4.

12. The method as recited in claim 1, wherein the step b) includes the step of b1) non-linearly quantizing each of the normalized edge histogram bins by using a corresponding non-linear quantization table, wherein the step b1) is provided with five non-linear quantization tables, each corresponding to a particular reference edge.

13. The method as recited in claim 12, wherein the step b1) includes the steps of:

b2-1) mapping each of the normalized edge histogram bins into a representative value contained in each corresponding reference edge quantization table; and

b2-2) generating three bits of a quantization index value representing a representative value for each normalized edge histogram bin to thereby generate L×

5 number of the quantization index values as a second image descriptor for the target image.

14. The method as recited in claim 12, wherein the normalized edge histogram bins are non-linearly quantized using a non-linear quantizer based on a Lloyd-Max algorithm.

15. The method as recited in claim 14, wherein the quantization table includes a table for a vertical edge histogram bin representing the number of vertical edges in the sub-image, which is expressed as:

Index Range Representative value 0 0.0000000 ~ 0.0343910 0.010867 1 0.0343910 ~ 0.0787205 0.057915 2 0.0787205 ~ 0.1221875 0.099526 3 0.1221875 ~ 0.1702110 0.144849 4 0.1702110 ~ 0.2280385 0.195573 5 0.2280385 ~ 0.3092675 0.260504 6 0.3092675 ~ 0.4440795 0.358031 7 0.4440795 ~ 1.0000000  

0.530128.

16. The method as recited in claim 14, wherein the quantization table further includes a table for a horizontal edge histogram bin representing the number of horizontal edges in the sub-image, which is expressed as:

Index Range Representative value 0 0.0000000 ~ 0.0411000 0.012266 1 0.0411000 ~ 0.0979065 0.069934 2 0.0979065 ~ 0.1540930 0.125879 3 0.1540930 ~ 0.2128515 0.182307 4 0.2128515 ~ 0.2789795 0.243396 5 0.2789795 ~ 0.3631455 0.314563 6 0.3631455 ~ 0.4880235 0.411728 7 0.4880235 ~ 1.0000000  

0.564319.

17. The method as recited in claim 14, wherein the quantization table further includes a table for a 45 degree edge histogram bin representing the number of 45 degree edges in the sub-image, which is expressed as:

Index Range Representative value 0 0.0000000 ~ 0.0150225 0.004193 1 0.0150255 ~ 0.0363560 0.025852 2 0.0363560 ~ 0.0576895 0.046860 3 0.0576895 ~ 0.0809025 0.068519 4 0.0809025 ~ 0.1083880 0.093286 5 0.1083880 ~ 0.1424975 0.123490 6 0.1424975 ~ 0.1952325 0.161505 7 0.1952325 ~ 1.0000000  

0.228960.

18. The method as recited in claim 14, wherein the quantization table further includes a table for a 135 degree edge histogram bin representing the number of 135 degree edges in the sub-image, which is expressed as:

Index Range Representative value 0 0.0000000 ~ 0.0150490 0.004174 1 0.0150490 ~ 0.0360780 0.025924 2 0.0360780 ~ 0.0566975 0.046232 3 0.0566975 ~ 0.0784090 0.067163 4 0.0784090 ~ 0.1025230 0.089655 5 0.1025230 ~ 0.1336475 0.115391 6 0.1336475 ~ 0.1848245 0.151904 7 0.1848245 ~ 1.0000000  

0.217745.

19. The method as recited in claim 14, wherein the quantization table further includes a table for a non-directional edge histogram bin representing the number of non-directional edges, which is expressed as:

Index Range Representative value 0 0.0000000 ~ 0.0292225 0.006778 1 0.0292225 ~ 0.0801585 0.051667 2 0.0801585 ~ 0.1374535 0.108650 3 0.1374535 ~ 0.1952415 0.166257 4 0.1952415 ~ 0.2549585 0.224226 5 0.2549585 ~ 0.3210330 0.285691 6 0.3210330 ~ 0.4036735 0.356375 7 0.4036735 ~ 1.0000000  

0.450972.

20. A method for retrieving corresponding images in response to a query image based on a database, the method comprising the steps of:

a) calculating L number of local edge histograms of the query image as an image descriptor for the query image, wherein each local edge histogram represents a spatial distribution of five reference edges in a sub-image and L is a positive integer, wherein the reference edges include four directional edges and a non-directional edge;

b) extracting a plurality of image descriptors for target images based on image information from the database, wherein the image descriptor for each target image includes L number of local edge histograms for each target image;

c) comparing the image descriptor for the query image with each image descriptor for the target images to generate a comparison result; and

d) retrieving at least one target image similar to the query image based on the comparison result.

21. The method as recited in claim 20, wherein each local edge histogram has five edge histogram bins corresponding to the reference edges.

22. The method as recited in claim 20, wherein the directional edges include a vertical edge, a horizontal edge, a 45 degree edge and a 135 degree edge, and the non-directional edge represents an edge of undesignated direction excluding the four directional edges.

23. The method as recited in claim 22, wherein the step a) includes the steps of:

a1) partitioning the query image into N×

N non-overlapping sub-images to thereby form L number of rectangular sub-images, wherein each sub-image is further partitioned into S×

K number of image-blocks, S and K being positive integers; and

a2) assigning one of the reference edges to each image-block to thereby generate L number of edge histograms for the query image, wherein the edge histogram includes the L×

5 edge histogram bins; and

a3) normalizing the edge histogram bins by S×

K which is the number of image-blocks contained in one sub-image, to thereby generate L×

5 number of normalized edge histogram bins, each normalized edge histogram bin having a real number between 0 and 1.

24. The method as recited in claim 23, wherein the step a2) includes the steps of:

a2-1) assigning one of the reference edges to each image block; and

a2-2) counting the number of each reference edge included in each sub-image to generate the L number of the edge histograms for the query image.

25. The method as recited in claim 24, wherein the step a2-1) includes the steps of:

a2-11) dividing each image-block into 2×

2 sub-blocks;

a2-12) assigning a corresponding filter coefficient to each sub-block;

a2-13) calculating a set of five edge magnitudes corresponding to five edges for each image-block by using the filter coefficient; and

a2-14) expressing the image-block as an edge having a maximum edge magnitude by comparing the calculated edge magnitudes to each other.

26. The method as recited in claim 25, wherein the five edge magnitudes are obtained by using five equations, which are expressed as:

$\begin{array}{c}{m}_v<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_v<br><br>\left(k\right)<br><br>;<br><br>\\ m_h<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_h<br><br>\left(k\right)<br><br>;<br><br>\\ m_{d-45}<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_{d-45}<br><br>\left(k\right)<br><br>;<br><br>\\ m_{d-135}<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_{d-135}<br><br>\left(k\right)<br><br>;<br><br><br><br><br><br>\mathrm{and}\\ m_{\mathrm{nd}}<br><br>\left(i,j\right)=<br><br>\underset{k=0}{\overset{3}{\sum <br><br>}}<br><br>a_k<br><br>\left(i,j\right)\times <br><br>f_{\mathrm{nd}}<br><br>\left(k\right)<br><br>,<br><br>\mathrm{where}<br><br><br><br>m_v<br><br>\left(i,j\right),m_h<br><br>\left(i,j\right),m_{d-45}<br><br>\left(i,j\right),\end{array}$

m_d-45(i, j), m_d-135(i, j) and m_nd(i, j), respectively, denote vertical, horizontal, 45 degree, 135 degree and non-directional edge magnitudes for a (i, j)^th image-block;

α

_k(i, j) denotes an average gray level for a sub-block assigned k in the (i, j)^th image-block and ƒ

_v(k), ƒ

_h(k), ƒ

_d-45(k), ƒ

_d-135(k) and ƒ

_nd(k) denote, respectively, filter coefficients for the vertical, horizontal, 45 degree, 135 degree and non-directional edges, where k represents a number assigned to each sub-block.

27. The method as recited in claim 25, wherein the image block is expressed as containing no edge when the maximum edge magnitude is less than a predetermined threshold value.

28. The method as recited in claim 20, wherein the image descriptors for the query and target images further include a global edge histogram and R number of the semi-global histograms based on the L×

5 number of normalized edge histogram bins, respectively, with R being a positive integer.

29. The method as recited in claim 28, wherein the global edge histogram represents an edge distribution in a whole space of the query and target images and each semi-global edge histogram represents an edge distribution in a corresponding set of sub-images of the query and target images.

30. The method as recited in claim 28, wherein said N and R are 4 and 13, respectively.

31. The method as recited in claim 30, wherein each of the 13 semi-global edge histograms is generated for each of 13 sets of four sub-images, the 13 sets including four sets of four sub-images, each set including four sub-images in each of first to fourth columns of the image in a vertical direction;

four sets of four sub-images, each set including four sub-images in each of first to fourth rows in a horizontal direction;

four sets of four sub-images, each set including a corresponding sub-image and three sub-images neighboring the corresponding sub-image, wherein the corresponding sub-image is respectively located on a left-top, on a right-top, on a left-bottom and on a right-bottom of the image; and

a set including four sub-images around a center of the image.

32. The method as recited in claim 20, wherein the step b) includes the steps of:

b1) retrieving L×

5 number of quantization index values for each of the target images;

b2) converting each of the L×

5 number of quantization index values into L×

5 number of normalized edge histogram bins for each target image by using five non-linear inverse quantization tables; and

b3) generating L number of local edge histograms based on the L×

5 number of normalized edge histogram bins.

33. The method as recited in claim 32, wherein the step b) further includes the step of:

b4) further generating a global edge histogram and R number of semi-global histograms for each of the target images based on the L×

5 number of normalized edge histogram bins.

34. The method as recited in claim 33, wherein the step c) includes the step of:

estimating a distance between the query image and said each target image by an equation as;

$\begin{array}{c}\mathrm{Distance}<br><br><br><br>\left(A,B\right)=<br><br>\underset{i=0}{\overset{79}{\sum <br><br>}}<br><br><br><br>{\mathrm{Local}}_{\mathrm{—<br><br>}}<br><br>A<br><br>\left[i\right]-{\mathrm{Local}}_{\mathrm{—<br><br>}}<br><br>B<br><br>\left[i\right]<br><br>+\\ <br><br>5\times <br><br>\underset{i=0}{\overset{4}{\sum <br><br>}}<br><br><br><br>{\mathrm{Global}}_{\mathrm{—<br><br>}}<br><br>A<br><br>\left[i\right]-{\mathrm{Global}}_{\mathrm{—<br><br>}}<br><br>B<br><br>\left[i\right]<br><br>+\\ <br><br>\underset{i=0}{\overset{64}{\sum <br><br>}}<br><br><br><br>{\mathrm{Semi}}_{\mathrm{—<br><br>}}<br><br>{\mathrm{Global}}_{\mathrm{—<br><br>}}<br><br>A<br><br>\left[i\right]-{\mathrm{Semi}}_{\mathrm{—<br><br>}}<br><br>{\mathrm{Global}}_{\mathrm{—<br><br>}}<br><br>B<br><br>\left[i\right]<br><br>\end{array}$

where Local_A[i] and Local_B[i] denote, respectively, the edge histogram bins of BinCount[i] of the query image A and the target image B;

Global_A[] and Global_B[] denote, respectively, the edge histogram bins for the global edge histograms of the query image A and the target image B; and

Semi_Global_A[] and Semi_Global_B[] denote, respectively, the histogram bin values for the semi-global edge histogram bins of the query image A and the target image B.

35. The method as recited in claim 20, wherein the step b) includes the steps of:

b1) retrieving L×

5 number of quantization index values for each of the target images;

b2) converting each of the L×

5 number of quantization index values into L×

5 number of normalized edge histogram bins for each target image by normalizing the L×

5 number of quantization index values; and

b3) generating L number of local histograms based on the L×

5 number of normalized edge histogram bins.

36. The method as recited in claim 34, wherein the step b) further includes the step of:

b4) further generating a global edge histogram and R number of semi-global histograms for each of the target images based on the L×

5 number of normalized edge histogram bins.

37. The method as recited in claim 36, wherein the step c) includes the step of:

estimating a distance between the query image and said each target image by an equation as;

$\mathrm{Distance}<br><br>\left(A,B\right)=\underset{i=0}{\overset{79}{\sum <br><br>}}<br><br><br><br>\mathrm{Local\_A}<br><br>\left[i\right]-\mathrm{Local\_B}<br><br>\left[i\right]<br><br>+5\times <br><br>\underset{i=0}{\overset{4}{\sum <br><br>}}<br><br><br><br>\mathrm{Global\_A}<br><br>\left[i\right]-\mathrm{Global\_B}<br><br>\left[i\right]<br><br>+\underset{i=0}{\overset{64}{\sum <br><br>}}<br><br><br><br>\mathrm{Semi\_Global}<br><br>\mathrm{\_A}<br><br>\left[i\right]-\mathrm{Semi\_Global}<br><br>\mathrm{\_B}<br><br>\left[i\right]<br><br>$

where Local_A[i] and Local_B[i] denote, respectively, the edge histogram bins of BinCount[i] of the query image A and the target image B;

Global_A[] and Global_B[] denote, respectively, the edge histogram bins for the global edge histograms of the query image A and the target image B; and

Semi_Global_A[] and Semi_Global_B[] denote, respectively, the histogram bin values for the semi-global edge histogram bins of the query image A and the target image B.

38. A method for constructing a bit-representation of an edge histogram descriptor for a target image, comprising the steps of:

a) partitioning the target image into 16 sub-images, wherein each sub-image is further partitioned into S×

K number of image-blocks, S and K being positive integers;

b) assigning one of five reference edges to each image-block to thereby generate 16 edge histograms for the target image, wherein the edge histogram includes the 80 edge histogram bins and the reference edges include four directional edges and a non-directional edge;

c) normalizing the edge histogram bins contained in each edge histogram by S×

K to thereby generate 80 normalized edge histogram bins, each normalized edge histogram bin having a real number between 0 and 1; and

d) non-linearly quantizing 80 normalized edge histogram bins to generate 80 quantization index values as a second image descriptor for the target image.

39. The method as recited in claim 38, wherein each quantization index value is represented by three bits.

40. The method as recited in claim 39, wherein the directional edges include a vertical edge, a horizontal edge, a 45 degree edge and a 135 degree edge, and the non-directional edge represents an edge of undesignated direction excluding the four directional edges.