Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-01
2002-02-12
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06347313
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to database object indexing and retrieval and more specifically to content-based multimedia retrieval that is responsive to user relevance feedback.
DESCRIPTION OF THE RELATED ART
Due to the rapidly growing amount of digital multimedia data available via the Internet or stored on private systems, there is a need for effective techniques for managing large multimedia databases. Content-searchable image database management systems often use an approach based on search-by-explicit queries, in which the user must provide some description of a desired object. Typically, the system retrieves objects, such as images, based on a similarity metric that correlates the description with various features associated with stored objects in the database. The metric might be calculated as a weighted sum of values for a set of low level image (i.e., attributes) such as color, shape, size, and texture patterns.
A concern with image retrieval from databases is the difficulty in establishing a correlation between the worded description and the low level image features which are utilized to organize database images. An image database management system is effective at retrieving an image if the description is specific with respect to one or more of the searchable image features, such as a search for “all square yellow objects.” However, the system will be much less effective if the description is less specific to the searchable image features and more specific to the desired object, such as a search for “all yellow cars,” because cars have many different shapes and sizes that are shared by other objects. Moreover, the same car can appear dramatically different depending on the vantage point from which the image was generated and depending on the lighting of the car. Although human perception is effective at interpreting two images of the same yellow car which are taken in different lighting and from a different perspective, current image databases perform the interpretation much less effectively.
U.S. Pat. No. 5,696,964 to Cox et al. describes a queryless multimedia database search method and system having a Bayesian inference engine which utilizes user relevance feedback to direct a search. The system maintains a probability distribution which represents a probability that each image in the database is the target of the search. The distribution is utilized to select the set of images to display to the user and further selections from the displayed images are solicited from the user. Each database image has a set of quantified features (i.e., attribute values) and the user indicates which of the selected images are similar to the target image. The selection of particular images having specific quantified features triggers an adjustment of the probability distribution. The adjusted probability distribution determines the next set of images which will be displayed to the user in a subsequent iteration of the search.
One of the problems of the Cox et al. database search system is that the system relies on features selected by a system operator or designer to describe and index the database images. The user feedback is utilized to modify the probability distribution only within the parameters defined by the features that have been quantified. Consequently, if a user is focused on a feature not included within the system-defined features, the effectiveness of the Cox et al. database search system dramatically declines. For example, if a user focuses on the curvature of the neck of a flamingo in making selections during a search and the system does not include quantification which takes into account the curvature of objects within images, the likelihood of a successful search will be low. Although configuration of a more comprehensive feature set would provide a partial solution to this problem, a truly comprehensive feature set is difficult to obtain because of the near infinite variety of features on which possible viewers may focus in analyzing image content. Furthermore, as the feature set grows larger, the processing requirements of the database search system become prohibitive.
What is needed is a method and a system for searching and retrieving database objects which are capable of associating low level features (“attributes”) utilized to characterize objects in the database with high level semantic features to enable effective database searching based on the high level semantic features.
SUMMARY OF THE INVENTION
A method and a system for indexing and retrieving database objects (typically images) include utilizing user relevance feedback received during a first object retrieval session to establish similarity correlations among the database objects and among clusters of database objects. The similarity correlations are updated continuously during user interaction with the database and are utilized to select database objects in response to query objects during subsequent iterations of a particular object retrieval session and during subsequent object retrieval sessions. The clusters are preliminarily determined by system-perceived relationships (i.e., similarities among system-quantified features), while after continued use the cluster-to-cluster correlations are indicative of user-perceived relationships among the groups.
In a preferred embodiment, the database objects are organized into clusters such that each cluster includes database objects having similar values for selected quantified features. Each database object is assigned a vector for multiple quantified features and can be mapped to a point within a multi-dimensional feature space according to the feature values associated with the database object. The similarity between clusters of database objects is represented by the distance between clusters in the multi-dimensional feature space. Thus, the initial organization is based exclusively on the system-perceived relationships. In response to a first user-generated query object which includes a set of quantified features, a database manager selects a first set of database objects for presentation to a user. The selected database objects are those objects within a cluster of the database which is closest to the first query object within the multi-dimensional feature space.
The selected database objects preferably also include randomly selected database objects to counteract a tendency of the system to “over learn” during a retrieval session and to present to the user database objects which otherwise would have a low probability of being selected during the retrieval session. For example, if the user selects an image of an airplane as relevant during a search for an image of a bird, the system might select only images of airplanes for consecutive iterations of the search. In order to reduce the likelihood that the system will progress along an inaccurate focus, at each iteration in a search random images are selected for presentation along with the other selected images.
The user designates particular database objects to be relevant to the retrieval session and other database objects to be irrelevant. In a preferred embodiment, in response to the user-designations of relevance and irrelevance, an updating mechanism updates the correlation matrix. For example, one of the clusters in the database might include images of yellow objects which are displayed to the user in response to the query image of a yellow car. In response to designations of relevance for images of a truck and a motorcycle and designations of irrelevance for images of a house and a flower, which are all included in a first cluster, the database processor divides the first cluster into two clusters. The first cluster retains the images of the truck and the motorcycle, which were determined by the user to be relevant, and a second cluster is created which includes the images of the flower and the house. Furthermore, other images of the first cluster which might not have been displayed must be segregated into either the first or second cluster. Those non-displayed images
Lee Catherine S.
Ma Wei-Ying
Zhang Hong-Jiang
LandOfFree
Information embedding based on user relevance feedback for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information embedding based on user relevance feedback for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information embedding based on user relevance feedback for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2935783