Method for fast return of abstracted images from a digital image database

• US 6,356,658 B1
• Filed: 04/11/2000
• Issued: 03/12/2002
• Est. Priority Date: 06/13/1997
• Status: Expired due to Term

• Current Assignee: Rakuten, Inc. (Rakuten Group, Inc.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Qian, Richard Junqiang, Sezan, Muhammed Ibrahim
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/546,925
• Time in Patent Office: 700 Days
• Field of Search: 382/201, 382/202, 382/203, 382/204, 382/209, 382/192, 382/224, 382/198, 382/214, 382/216, 382/218, 382/240, 382/276, 382/298, 382/243, 382/227, 707/104, 707/4, 707/5, 707/3, 707/6
• US Class Current: 382/209
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for expediting a search of a digital image database comprises, for each digital image, constructing a set of at least two abstracted images varying in level of detail and searching the abstracted images. Selected ones of the abstracted images are downloaded to a user thereby reducing download time through a finite bandwidth communicative medium relative to the time needed to download complete digital images.

Claims

1. A method for identifying a match for a target digital image from among a set of candidate digital images, comprising:

(a) identifying at least one candidate most salient point set from at least one of said candidate digital images, wherein said at least one candidate most salient point set is characterized by a majority of said point set being representative of vertices of at outer contour of an image depicted by said at least one of said candidate digital images;

(b) identifying a target most salient point set from said target digital image;

(c) comparing said at least one candidate most salient point set to said target most salient point set; and

(d) for each said at least one said candidate digital image marking said candidate digital image for further inspection if said candidate most salient point set meets a similarity threshold with said target most salient point set.

2. The method of claim 1, further comprising the following steps:

(a) identifying a target intermediate salient point set from said target point set;

(b) for each said candidate digital image marked for further inspection identifying a candidate intermediate salient point set from said candidate point set; and

(c) if said database image has been marked for further inspection, comparing said target intermediate salient point set with said candidate intermediate salient point set and marking said candidate image for yet further inspection if said candidate intermediate salient point set meets a similarity threshold with said target intermediate salient point set.

3. The method of claim 2 in which the steps of identifying said candidate most salient point set and said candidate intermediate salient point set are performed prior to any of the other steps.

4. A method for finding a match for a target digital image in a set of candidate digital images, comprising:

(a) for each image in said set of candidate digital images, forming a hierarchy of N, greater than one, abstractions ranked by level of detail from a first level, least detailed, candidate image abstraction, arbitrarily assigned number 1, to an Nth level, most detailed, candidate image abstraction;

(b) forming an hierarchy of N abstractions ranked by level of detail for said target digital image;

(c) comparing said target least detailed image abstraction to each said least detailed candidate image abstraction to form a first subset of digital images;

(d) starting with n=2 and iteratively incrementing n, iteratively comparing said nth level of detail abstraction of the target digital image to each said nth level of detail abstraction of the (n−

1)th subset of candidate digital images to form an nth subset of candidate digital images until a sufficiently small number of digital images remains; and

(e) returning abstractions of said sufficiently small number of candidate digital images for display to a user.

5. The method of claim 4 wherein said abstractions of said candidate digital images returned for display to said user are abstracted to one of the N levels of abstraction.

6. The method of claim 5, further including the step of picking at least one of said abstracted images and commanding the return and display of a corresponding unabstracted one of said candidate digital image.