Image analysis – Pattern recognition – Template matching
Reexamination Certificate
2000-04-11
2002-03-12
Mehta, Bhavesh (Department: 2621)
Image analysis
Pattern recognition
Template matching
C382S243000, C707S793000
Reexamination Certificate
active
06356658
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a system for searching a digital image database to identify a set of images that bear a similarity to a first digital image of interest and for permitting a user at a remote terminal connected to a main computer by way of a limited bandwidth communicative link to efficiently obtain representations of the identified images.
With the advent of widespread computer technology and the formation of large databases of digital imagery, the ability to search through a database to find images of interest is becoming increasingly important. A number of approaches have been taken to address this problem.
Tal, U.S. Pat. No. 4,975,969, discloses a system for identifying peoples' faces. The system works by forming a ratio between two facial parameters, such as the distance between eyes and the tip of the nose and the distance between the tip of the nose and the bottom of the upper lip. This system is narrowly drawn toward the recognition of unique facial features and does not shed much light on the problem of finding particular digital images of interest from a more generalized database of digital images that includes many images that are not human faces.
Bradley, U.S. Pat. No. 4,991,223, discloses a system for recognizing image features using color elements. The image is scanned and each color in the image is represented by a code. Then the scanned and coded image is processed by a correlator which detects color discontinuities and thereby identifies differently colored features. This system is designed for use in inspection systems, in which a great deal of prior information is available and is not applicable to digital image database search systems, in which a great deal of search query formation flexibility is required.
Agrawal et al., U.S. Pat. No. 5,647,058, discloses a method for high-dimensionality indexing in a multi-media database. In this method a series of vectors are extracted from the objects in a database and used in a similarity search with a target object. A secondary search is performed to eliminate false positives.
Arman et al., U.S. Pat. No. 5,521,841, disclose a system for browsing the contents of a given video sequence. Representative frames are chosen from the video sequence. Each representative frame is abstracted into a group of 16×16 pixel blocks and compared with a similarly abstracted representation of a frame for which the user is attempting to find a match. Representative frames with a degree of similarity above a threshold are presented to the user for further inspection.
Barber et al., U.S. Pat. No. 5,579,471, disclose a method for searching an image databased on a query that is compiled by a human user by selecting image characteristics, such as color, from a display on a screen and for example, indicating where in the sought after image the color should occur. Using the user compiled query the computer system searches through the database and returns images which fall within some threshold of nearness to the query. No system is described by Barber et al. for abstracting complex shapes. This patent does, however, reference G. Taubin and D. B. Cooper “Recognition and Positioning of Rigid Objects Using Algebraic Moment Invariants,” Geometric Methods in Computer Vision, SPIE Vol. 1570, pp 175-186, 1992. Barber et al., also disclose providing a set of images determined to be similar to the search image. There is, however, in this patent no preabstraction of the digital image database nor shape abstraction based on point saliency.
Coincidentally, with the development of object based programming, scenes may be digitally represented as a set of data objects. For example, a scene with a horse-drawn carriage crossing a bridge may be divided into a data object representing the carriage, another data object representing the horse pulling the carriage, and yet another data object representing the static imagery in the scene. This technique of scene representation increases the importance of shape recognition for searching through an image database, because a data object representation may have a distinctive, and therefore recognizable, shape.
One problem encountered by those linked to an image database by means of a standard telephone line or other narrow bandwidth link is the slow download time for detailed images. This may present a problem in searching through the digital image database because if, for example, a search of an image database returns 10 images and each image requires 3 minutes to download to the user's image display apparatus, it will take the user 30 minutes to download all of the images in order to find an image of interest. This could prove frustrating, because it is possible that many of the images could have been eliminated quickly if not for the lengthy download time.
Therefore, an efficient way to search a digital image database for the presence of a particular shape and to efficiently return a preliminary set of search results to the user is needed but not yet available.
SUMMARY OF THE INVENTION
The present invention is a method for expediting a search of a candidate digital image database, comprising constructing a hierarchy of reduced detail image abstraction layers ranked by level of detail. A search is then conducted of the image abstractions and a set of reduced detail image abstractions is returned to the user, thereby reducing download time through a finite bandwidth communicative link. The user may peruse these images, which may be reduced in size to allow many to fit on the user's display screen at once, in order to find an image or images of interest. The image corresponding to a downloaded abstraction may be selected for delivery in its entirety or at some other higher level of detail.
In a separate aspect of the present invention, a method for searching a digital image database includes the initial step of identifying a target point set representing a digital image outline from the target image. Then a target most salient point set is identified from the target point set. A target point set representing a digital image outline from a user supplied target image is identified. Then, a target most salient point set from the target point set is found. Finally, the target most salient point set is compared to the candidate most salient point set and the candidate image is noted for further inspection if the target most salient point set meets a threshold of similarity with the candidate most salient point set.
In a separate aspect, the present invention comprises a search method for finding a match for a target digital image in a set of candidate images, comprising for each candidate image, forming a hierarchy of abstractions ranked by amount of data needed to represent each abstraction, from a least detailed candidate image abstraction to a most detailed candidate image abstraction and forming a target least detailed image abstraction from said target digital image. Then, comparing target least detailed image abstraction to each candidate least data intensive target image abstraction to form a first subset of candidate images. Next, iteratively comparing the target digital image to each said nth detailed abstraction of the (n−1) th subset of candidate images to form an nth subset of candidate images until a completion test is satisfied, resulting in the selection of a final candidate image set and returning said final candidate images.
The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention, taken in conjunction with the accompanying drawings. dr
BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS
FIG. 1
is a flow chart for practicing an exemplary method of the present invention.
FIG. 2
is an illustration of a digital image object library containing hierarchical representations (coded or not coded) of shape and texture and objects.
FIG. 3
is a block diagram depicting the method of the invention.
FIG. 4
is a schematic
Qian Richard Junqiang
Sezan Muhammed Ibrahim
Bayat Ali
Chernoff Vilhauer McClung & Stenzel LLP
Mehta Bhavesh
Sharp Laboratories of America Inc.
LandOfFree
Method for fast return of abstracted images from a digital... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for fast return of abstracted images from a digital..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for fast return of abstracted images from a digital... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2859666