Image retrieval method and apparatus using iterative matching

• US 7,298,931 B2
• Filed: 08/29/2003
• Issued: 11/20/2007
• Est. Priority Date: 10/14/2002
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: Kim, Tae-kyun, Kim, Hyun-woo, Kee, Seok-cheol, Hwang, Won-jun
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US10/650,964
• Publication Number:
  US 20040073543A1
• Time in Patent Office: 1,544 Days
• Field of Search: 382/209, 382/219, 382/305, 382/115, 382/118, 382/190, 382/307, 707/3, 707/6, 707/7, 340/5.52, 340/8.82
• US Class Current: 382/305
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

An image retrieval method and apparatus using iterative matching are provided. The method comprises: (a) extracting K similar images in order of matching rank by retrieving N reference images stored in an image database through comparison between a query image selected by a user and the reference images; and (b) performing iterative matching for M similar images, which are ranked higher and selected from the K similar images, with a predetermined frequency, and rearranging the matching ranks of the M similar images. According to the method and apparatus, among similar images retrieved by using a query image selected by a user, M similar images that are ranked higher are selected, and by performing iterative matching for the M similar images using the high-ranked similar image, M similar images are rearranged in order of similarity and output. Accordingly, accuracy of the matching can improve greatly and a load to the retrieval engine due to iterative retrieval can be minimized.

Claims

1. An image retrieval method comprising:

(a) comparing a query image to N reference images stored in an image database and extracting K similar images in order of matching rank from the N reference images; and

(b) performing iterative matching for M similar images, which are ranked higher among the K similar images, with a predetermined frequency of iteration, by selecting a similar image ranked the highest among to-be-iteratively-matched similar images as a new query image for each iteration, and rearranging the matching ranks of the M similar images for each iteration by updating a matching score using a predetermined weighted value parameter.

2. The method of claim 1, further comprising:

(c) adding (K−

M) similar images, which exclude the M similar images in the K similar images extracted in the step (a), to the M similar images rearranged in the step (b), and outputting the result.

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

(b1) storing the M similar images whose matching ranks are higher among the K similar images extracted in the step (a);

(b2) selecting a similar image ranked the highest among the M similar images as a new query image, and performing iterative matching for a retrieval range of (M−

1) similar images that excludes the image ranked the highest; and

(b3) after changing the new query image and the retrieval range in the step (b2), performing iterative matching with the predetermined frequency of iteration and rearranging the matching ranks of the M similar images.

4. The method of claim 3, wherein the step (b) further comprises:

(b4) storing (K−

M) similar images excluding the M similar images in the K similar images extracted in the step (a).

5. The method of claim 4, wherein the step (b) further comprises:

(b5) adding the (K−

M) similar images stored in the step (b4) to the M similar images rearranged in the step (b3) and outputting the result.

6. A computer readable medium having embodied thereon a computer program for executing the method of claim 3.

7. The method of claim 1, wherein the weighted value parameter is a value which decreases exponentially in proportion to the increase of an the iteration frequency.

8. The method of claim 1, wherein the matching score is updated according to the following equation:

s^(n-1)(i)+W_n-1·

D(q^(n-1),q_i^(n-1))

where i is between 1 and M, s^(n-1)(i) denotes a matching score corresponding to each similar image {q_i^(n-1)|i=1, . . . , M}which are rearranged when iterative matching is performed n times, w_n-1 is the weighted value parameter which is applied when iterative matching is performed n times, and D(q^(n-1), q_i^(n-1)denotes the absolute value of a characteristic information distance between a query image q^(n-1)and the rearranged similar images q_i^(n-1).

9. The method of claim 8, wherein the weighted value parameter (w_n-1) is (w₁)^n-1 and w₁ is w.

10. The method of claim 1, wherein the iteration frequency is set by the user.

11. The method of claim 1, wherein the iteration frequency is automatically set according to a number of images whose ranks change in the M similar images compared to an existing previous rank.

12. The method of claim 1, wherein the iteration frequency is automatically set according to whether ranks of the M similar images change after an i-th matching rank.

13. A computer readable medium having embodied thereon a computer program for executing the method of claim 1.

14. An image retrieval apparatus comprising:

a 1st retrieval unit which compares a query image to N reference images stored in an image database and extracts K similar images in order of matching rank from the N reference images; and

a 2nd retrieval unit which performs iterative matching for M similar images, which are ranked higher among the K similar images, with a predetermined frequency of iteration, by selecting a similar image ranked the highest among to-be-iteratively-matched similar images as a new query image for each iteration, and rearranges the matching ranks of the M similar images for each iteration by updating a matching score using a predetermined weighted value parameter.

15. The apparatus of claim 14, further comprising:

a user interface unit which receives the query image and retrieval conditions selected by user the be provided to the 1st retrieval unit and the 2nd retrieval unit, and displays the M similar images rearranged by the 2nd retrieval unit.

16. The apparatus of claim 14, wherein the 2nd retrieval unit comprises:

a 1st storage unit which stores the M similar images whose matching ranks are higher among the K similar images provided by the 1st retrieval unit; and

an iterative matching unit which selects a similar image ranked the highest among the M similar images stored in the 1st storage unit as a new query image, performs iterative matching for a retrieval range of (M−

1) similar images that excludes the image ranked the highest, rearranges the ranks of the M similar images, and stores the rearranged M similar images in the 1st storage unit.

17. The apparatus of claim 16, wherein the iterative matching unit changes the new query image and the retrieval range each iteration.

18. The apparatus of claim 16, wherein if M<

K, the apparatus further includes a 2nd storage unit for storing (K−

M) similar images except the M similar images stored in the 1st storage unit.

19. The apparatus of claim 18, wherein the 2nd retrieval unit further comprises:

a retrieval result combining unit which adds the (K−

M) similar images stored in the 2nd storage unit to the M similar images which are rearranged according to matching ranks by the iterative matching unit and stored in the 1st storage unit, and outputs the result as a retrieval result.

20. The apparatus of claim 14, wherein the weighted value parameter is a value which decreases exponentially in proportion to the increase of the iteration frequency.

21. The apparatus of claim 14, wherein the iteration frequency is set by the user.

22. The apparatus of claim 14, wherein the iteration frequency is automatically set according to a number of images whose ranks change in the M similar images compared to an existing previous rank.

23. The apparatus of claim 14, wherein the iteration frequency is automatically set according whether ranks change after an i-th matching rank.