Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-04-22
2002-07-02
Shah, Sanjiu (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06415282
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of querying a database of images and particularly to providing an interface for organizing the results of queries applied to a database of images.
2. Description of the Related Art
Search engines are some of the most popular and widely accessed sites on the World Wide Web (WWW) because they allow a user to find information of interest. These engines gather textual information about resources on the Web and build up indices. The indices allow for the retrieval of documents containing user specified keywords. Another method of searching for information on the Web utilizes subject-based directories, which provide a useful browsable organization of information.
However, with the explosive growth of information that is available on the WWW, most queries applied to the search engines result in a large number of retrieved documents. This leads to a key limitation suffered by most of the popular search engines available today. More specifically, most search engines show the results of a query as pages of scrolled lists. If a large number of documents are retrieved, scrolling through such lists to find documents of interest to the user is extremely tedious and not at all user friendly.
An image search engine, called Advanced Multimedia Oriented Retrieval Engine (AMORE), developed by the present inventors at NEC, allows the user to specify an image and find images that are visually similar to it. See Mukhetjea et al., “Towards a Multimedia World-Wide Web Information Retrieval Engine,” Proceedings of the Sixth International World-Wide Web Conference, pages 177-188, April, 1997. In AMORE the user can specify keywords, where all the images relevant to the keywords are retrieved. However, as more and more images are indexed, AMORE is suffering from the same problems affecting traditional text search engines. More specifically, a query presented by the user of the search engine may result in a large number of retrieved images. Many user queries result in more than 100 retrieved images. As with other search engines, AMORE shows a few of the retrieved images per page and allows the user to go to other pages of retrieved images. This is shown in FIG.
1
. Obviously, this is not a very user-friendly way of displaying search results to the user of the search engine.
Various searching and clustering techniques have been proposed to attempt to make systems more user-friendly. However, most have focused on text-based mechanisms. For example, clustering has been an emerging information retrieval tool. See Salton et al., “Introduction to Modern Information Retrieval,” McGraw-Hill, 1983; Van-Rijsbergen, “Information Retrieval,” Butterworths, 1979. The focus has been on the use of text clustering to speed up the searching process. Instead of comparing all documents in a large collection to find the relevant documents, such efforts have focused on initially comparing only a representative cluster vector for each cluster with the search request. Thereafter, only documents from clusters which matched favorably are compared. Clustering is also useful for browsing large online collections of text as shown by a scatter/gather technique. See Cutting et al., “Scatter/Gather: A Cluster-based Approach to Browsing Large Document Clusters,” Proceedings of the ACM SIGIR '92 Conference on Research and Development in Information Retrieval, pages 318-329, June, 1992. Once again, this effort focuses on browsing a text collection, rather than an image collection.
In some instances, clustering has been used for searching large image databases as a pre-processing step to filter out non-interesting images. This reduces the number of images to be processed by more computer-intensive fine matching procedures. In addition, using the classification results produced by clustering, users can roughly grasp the contents of the entire image database and use this information for their interaction with the image retrieval system. Image clustering can be based on various image features such as colors, textures, shapes, etc. For example, Hirata et al., “The Concept of Media-based Navigation and Its Implementation on Hypermedia System “Miyabi,”” NEC Research and Development, 35(4):410-420, 1994, discusses a technique that focuses on color information in an image. Color values from the image are extracted and mapped on the HLS color spaces. Based on the results, users can filter out the images before searching. On the other hand, the work described in Del Bimbo et al., “Shape Indexing by Structural Properties,” International Conference on Human Factors in Computing Systems, page 370-377, June, 1997, clusters by shape similarity. Using multi-scale analysis, a hierarchical structure of shape is extracted. Based on this structure, searching capabilities are provided. However, this method assumes that boundary analysis correctly extracts the boundaries of objects in the image. However, this is very difficult to do for WWW images containing many objects. Similarly, image clustering using feature vectors based on moment invariant (See Flickner et al., “Query by Image and Video Content: The QBIC System,” IEEE Computer, 28(9):23-31, September, 1995) or boundary features (See Mehrotra et al., “Similar-Shape Retrieval in Shape Data Management,” IEEE Computer, pages 57-62, September, 1995) also assumes the correct extraction of objects (or input by a user). Therefore, it is very hard to apply these techniques to the WWW. Additionally, each of these techniques focuses on providing only a single cluster mechanism. The techniques do not address providing a user-friendly interface.
The search techniques are also being applied to the WWW. Research at Xerox Palo Alto Research Center (PARC) uses clustering to extract useful structures from the WWW. See Pirolli et al., “Silk from a Sow's Ear: Extracting Usable Structures from the Web,” Proceedings of the ACM SIGCHI '96 Conference on Human Factors in Computing Systems, pages 118-125, April, 1996; Pitkow et al, “Life, Death and Lawfulness on the Electronic Frontier,” Proceedings of the ACM SIGCHI '97 Conference on Human Factors in Computing Systems, pages 383-390, March, 1997. The clusters are determined by various criteria like co-citation analysis. Clustering by textual similarity to organize the results of Web text search engines is described in Chang et al., “Customizable Multi-Engine Search Tool with Clustering,” Proceedings of the Sixth International World-Wide Web Conference, pages 257-264, April, 1997. However, such implementations also fail to provide a user friendly user interface.
Examples of interfaces which have been developed for viewing information retrieval results include SenseMaker (See Baldonado et al., “SenseMaker: An Information-Exploration Interface Supporting the Contextual Evolution of a User's Interest,” Proceedings of the ACM SIGCHI '97 Conference on Human Factors in Computing Systems, pages 11-18, March, 1997) and Cat-a-Cone (See Hearst et al., “Cat-a-Cone: An Interactive Interface for Specifying Searches and Viewing Retrieval Results using a Large Category Hierarchy,” Proceedings of the ACM SIGIR '97 Conference on Research and Development in Information Retrieval, July, 1997). These articles, as well as those discussed above are hereby incorporated herein by reference.).
SenseMaker is an interface for information exploration across heterogeneous sources in a digital library. SenseMaker allows the user to interactively change the level of granularity and the organizational dimensions of a collection of documents that match the user's interest. Cat-a-Cone is a 3D interface that allows a user to search and browse a large category hierarchy and the associated documents. The documents and the categories can be viewed concurrently. However, as with other systems, SenseMaker and Cat-a-Cone both focus on the text properties of documents and also present differing text organizational structures.
Other Web Image Search engines, such as Excalibur&
Hara Yoshinori
Hirata Kyogi
Mukherjea Sougata
Kindred Alford W.
NEC USA Inc.
Shah Sanjiu
LandOfFree
Method and apparatus for query refinement 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 and apparatus for query refinement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for query refinement will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2837691