Method and apparatus for content-based image retrieval with learning function

• US 6,606,623 B1
• Filed: 09/02/1999
• Issued: 08/12/2003
• Est. Priority Date: 04/09/1999
• Status: Expired due to Term

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Huang, Yea-Shuan, Hsieh, Jun-Wei, Chiang, Cheng-Chin
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US09/388,483
• Time in Patent Office: 1,440 Days
• Field of Search: 707/5, 707/102, 707/4, 707/104.1, 382/156, 382/155
• US Class Current: 707/766
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2178 based on feedback of a supervisor
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An apparatus and method of content-based image retrieval generate a plurality of training images, including a first part and a second part. Each training image of the first part is labeled as one of a positive bag or a negative bag. The training image is labeled a positive bag if the training image has a desirable character and labeled a negative bag if the training image does not have a desirable character. A set of N1 training images is identified from a set of all training images of the second part, which identified images have a feature most closely matching a first feature instance of a training image labeled as a positive bag. A first value corresponding to the first feature instance is calculated, based on the number of images labeled as positive bags that are identified in the set of N1 training images.

Claims

1. A method of content-based image retrieval, the method comprising:

(a) generating a plurality of training images, the plurality of training images comprising a first part and a second part;

(b) labeling each training image of the first part as one of a positive bag and a negative bag, each training image labeled a positive bag if the training image has a desirable character and labeled a negative bag if the training image does not have a desirable character;

(c) identifying a set of N1 training images, from a set of all training images of the second part, that have a feature most closely matching a first feature instance of a training image labeled as a positive bag;

(d) calculating a first value, corresponding to the first feature instance, based on the number of images labeled as positive bags that are identified in the set of N1 training images;

(e) determining whether to include the first feature. instance in a preliminary target concept, which comprises a set of second feature instances, based on the first value;

(f) generating a revised target concept using the preliminary target concept and one or more of the training images labeled as negative bags; and

(g) retrieving a set of target images in accordance with the revised target concept.

2. The method of claim 1, further comprising:

(h) identifying a set of N2 training images, from the set of all training images of the second part, that have a feature most closely matching a second feature instance from the set of second feature instances;

(i) calculating a second value, corresponding to the second feature instance, based on the number of images labeled as negative bags that are not identified in the set of N2 training images; and

(j) determining whether to include the second feature instance in the revised target concept based on the second value.

3. The method of claim 1, wherein the plurality of training images is generated in response to a user'"'"'s query, the first part comprises explicit training images, and the second part comprises an implicit training image database.

4. A method of content-based image retrieval, the method comprising:

(a) generating a plurality of training images comprising a first part and a second part;

(b) extracting a first set of feature instances from the first part;

(c) labeling the feature instances of the first set as positive feature instances or negative feature instances;

(d) labeling the training images of the first part having at least one positive feature instance therein as a positive bag and labeling the training images of the first part having no positive feature instance therein as a negative bag;

(e) generating a preliminary target concept from an amount of similarity between (i) the training images labeled as positive bags and (ii) the training images identified by a query of the second part using the positive feature instances, the preliminary target concept comprising a first subset of the first set of feature instances;

(f) generating a revised target concept from an amount of dissimilarity between (iii) the training images labeled as negative bags and (iv) the training images identified by a query of the second part using the first subset of feature instances, the revised target concept comprising a second subset of the first set of feature instances; and

(g) retrieving a set of target images in accordance with the revised target concept.

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

calculating a first distance between a first one of the positive feature instances and one of the positive bags;

counting a number of images B_k of the second part for which a second distance between B_k and the first one of the positive feature instances is less than the first distance; and

selecting the first one of the positive feature instances as an element of the preliminary target concept if the number is less than a first threshold.

6. The method of claim 5, wherein step (f) further comprises:

calculating a third distance between the selected element of the preliminary target concept and one of the negative bags;

counting a second number of the images Bk of the second part for which a fourth distance between Bk and the selected element of the preliminary target concept is less than the third distance; and

assigning the selected element of the preliminary target concept as an element of the revised target concept if the second number is less than a second threshold.

7. The method according to claim 4, wherein the first part comprises explicit training images, the second part comprises an implicit training image database obtained through a user'"'"'s previous query, and the labeling of the explicit training images is performed by a user.

8. An apparatus for content-based image retrieval, comprising:

(a) a query unit that generates a user'"'"'s query;

(b) a training instance generator that generates a set of explicit training images, retrieved from a source database, in accordance with the user'"'"'s query;

(c) a first labeling means for providing user feedback information and labeling feature instances of the explicit training images as positive feature instances or negative feature instances based on the feedback information;

(d) a second labeling means for labeling each of the explicit training images having at least one positive feature instance therein as a positive bag and for labeling each of the explicit training images having no positive feature instance therein as a negative bag;

(d) a training set generator that generates an implicit training image database based on the user'"'"'s query;

(e) a learned concept unit that generates a preliminary target concept from the explicit training images labeled as positive bags, generates a revised target concept in accordance with;

(i) the explicit training images labeled as negative bags, (ii) the user feedback information, and (iii) the implicit training images, and retrieves a set of target images from the source database in accordance with the revised target concept.

9. The apparatus of claim 8, wherein:

the learned concept unit generates the preliminary target concept by calculating a first distance between a first one of the positive feature instances and one of the explicit training images labeled as the positive bag;

the learned concept unit counts a number of images B_k of the implicit training image database for which a second distance between B_k and the first one of the positive feature instances is less than the first distance; and

the learned concept unit selects the first one of the positive feature instances as an element of the preliminary target concept if the number is less than a first threshold.

10. The apparatus of claim 9, wherein:

the learned concept unit generates the revised target concept by calculating a third distance between the selected element of the preliminary target concept and one of the explicit training images labeled as the negative bag;

the learned concept unit counts a second number of images B_k of the implicit training image database for which a fourth distance between B_k and the selected element of the preliminary target concept is less than the third distance; and

the learned concept unit assigns the selected element of the preliminary target concept as an element of the revised target concept if the second number is less than a second threshold.

11. The apparatus of claim 8, wherein the first and second labeling means are part of a single unit.