Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-10-30
2002-11-26
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C382S162000, C382S163000
Reexamination Certificate
active
06487554
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to techniques for processing images, video and other types of information signals, and more particularly to automated systems and devices for retrieving, matching and otherwise manipulating information signals which include color pattern information.
BACKGROUND OF THE INVENTION
Flexible retrieval and manipulation of image databases and other types of color pattern databases has become an important problem with applications in video editing, photo-journalism, art, fashion, cataloging, retailing, interactive CAD, geographic data processing, etc. Until recently, content-based retrieval (CBR) systems have generally required a user to enter key words to search image and video databases. Unfortunately, this approach often does not work well, since different people describe what they see or what they search for in different ways, and even the same person might describe the same image differently depending on the context in which it will be used.
One of the earliest CBR systems, known as ART MUSEUM and described in K. Hirata and T. Katzo, “Query by visual example, ” Proc. of 3
rd
Int. Conf. on Extending Database Technology, performs retrieval entirely based on edge features. A commercial content-based image search engine with profound effects on later systems was QBIC, described in W. Niblack et al. “The QBIC project: Quering images by content using color, texture and shape, ” Proc. SPIE Storage and Retrieval for Image and Video Data Bases, February 1994. As color representation, this system uses a k-element histogram and average of (R,G,B), (Y,i,q), and (L,a,b) coordinates, whereas for the description of texture it implements Tamura's feature set, as described in H. Tamura et al., “Textural features corresponding to visual perception, ” IEEE Transactions on Systems, Man and Cybernetics, Vol. 8, pp. 460-473, 1982.
In a similar fashion, color, texture and shape are supported as a set of interactive tools for browsing and searching images in the Photobook system developed at the MIT Media Lab, as described in A. Pentland et al., “Photobook: Content-based manipulation of image databases, ” International Journal of Computer Vision, 1996. In addition to providing these elementary features, systems such as VisualSeek, described in J. R. Smith and S. Chang, “VisualSeek: A fully automated content-based query system,” Proc. ACM Multimedia 96, 1996, Netra, described in W. Y. Ma and B. S. Manjunath, “Netra: A toolbox for navigating large image databases, ” Proc. IEEE Int. Conf. on Image Processing, 1997, and Virage, described in A. Gupta, and R. Jain, “Visual information retrieval, ” Communications of the ACM, Vol. 40, No. 5, 1997, each support queries based on spatial relationships and color layout. Moreover, in the above-noted Virage system, the user can select a combination of implemented features by adjusting the weights according to his or her own “perception.” This paradigm is also supported in RetrievalWare search engine described in J. Dowe, “Content based retrieval in multimedia imaging,” Proc. SPIE Storage and Retrieval for Image and Video Databases, 1993.
A different approach to similarity modeling is proposed in the MARS system, described in Y. Rui et al., “Content-based image retrieval with relevance feed-back in Mars,” Proc. IEEE Conf. on Image Processing, 1997, where the main focus is not in finding a best representation, but rather on the relevance feedback that will dynamically adapt multiple visual features to different applications and different users. Hence, although great progress has been made, none of the existing search engines offers a complete solution to the general image retrieval problem, and there remain significant drawbacks with the existing techniques which prevent their use in many important practical applications.
These drawbacks can be attributed to a very limited understanding of color patterns compared to other visual phenomena such as color, contrast or even gray-level textures. For example, the basic dimensions of color patterns have not yet been adequately identified, a standardized and effective set of features for addressing their important characteristics does not exist, nor are there rules defining how these features are to be combined. Previous investigations in this field have concentrated mainly on gray-level natural textures, e.g., as described in the above-cited H. Tamura et al. reference, and in A. R. Rao and G. L. Lohse, “Towards a texture naming system: Identifying relevant dimensions of texture,” Vision Res., Vol. 36, No. 11, pp. 1649-1669, 1996. For example, the Rao and Lohse reference focused on how people classify textures in meaningful, hierarchically-structured categories, identifying relevant features used in the perception of gray-level textures. However, these approaches fail to address the above-noted color pattern problem, and a need remains for an effective framework for analyzing color patterns.
SUMMARY OF THE INVENTION
The invention provides a perceptually-based system for pattern retrieval and matching, suitable for use in a wide variety of information processing applications. The system is based in part on a vocabulary, i.e., a set of perceptual criteria used in comparison between color patterns associated with information signals, and a grammar, i.e., a set of rules governing the use of these criteria in similarity judgment. The system utilizes the vocabulary to extract perceptual features of patterns from images or other types of information signals, and then performs comparisons between the patterns using the grammar rules. The invention also provides new color and texture distance metrics that correlate well with human performance in judging pattern similarity.
An illustrative embodiment of a perceptually-based system in accordance with the invention uses a predetermined vocabulary comprising one or more dimensions to extract color and texture information from an information signal, e.g., an image, selected by a user. The system then generates a distance measure characterizing the relationship of the selected image to another image stored in a database, by applying a grammar, comprising a set of predetermined rules, to the color and texture information extracted from the selected image and corresponding color and texture information associated with the stored image. For example, the system may receive the selected image in the form of an input image A submitted in conjunction with a query from the user. The system then measures dimensions DIM
i
(A) from the vocabulary, for i=1, . . . , N, and for each image B from an image database, applies rules R
i
from the grammar to obtain corresponding distance measures dist
i
(A, B), where dist
i
(A, B) is the distance between the images A and B according to the rule i.
In accordance with the invention, the vocabulary may include dimensions such as overall color, directionality and orientation, regularity and placement, color purity, and pattern complexity and heaviness. The rules in the grammar may include equal pattern, overall appearance, similar pattern, and dominant color and general impression, with each of the rules expressed as a logical combination of values generated for one or more of the dimensions. The distance measure may include separate color and texture metrics characterizing the similarity of the respective color and texture of the two patterns being compared.
A major advantage of a pattern retrieval and matching system in accordance with the invention is that it eliminates the need for selecting the visual primitives for image retrieval and expecting the user to assign weights to them, as required in most current systems. Furthermore, the invention is suitable for use in a wide variety of pattern domains, including art, photography, digital museums, architecture, interior design, and fashion.
REFERENCES:
patent: 5699453 (1997-12-01), Ozaki
patent: 5751829 (1998-05-01), Ringland et al.
patent: 5852823 (1998-12-01), De Bonet
patent: 6072904 (2000-06-01), Desai et al.
patent: 6122391 (2000-
Ganapathy S. Kicha
Hu Jianying
Kovacevic Jelena
Mojsilovic Aleksandra
Safranek Robert James
Corrielus Jean M.
Lucent Technologies - Inc.
Ryan & Mason & Lewis, LLP
LandOfFree
Retrieval and matching of color patterns based on a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Retrieval and matching of color patterns based on a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Retrieval and matching of color patterns based on a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2967702