Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
2001-02-15
2004-10-05
Couso, Yon J. (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S220000, C382S280000, C382S308000
Reexamination Certificate
active
06801661
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital image processing, and in particular to digital image processing techniques relating to the identification and representation of shape components of an image.
BACKGROUND OF THE INVENTION
Rapid advances in digital imaging are leading to an explosion of large collections of digital images. Once digital imaging truly takes hold in the home consumer market, practically every household will have a collection a digital images. If tradition holds, most of these collections (being archived to tape or CDROM) will end up, e.g., stored in a shoebox on a closet shelf, rarely, if ever, to be viewed again. However, digital imaging offers the ability to prevent this outcome in ways never possible with analog imaging. For example, computer applications can be created to assist in the formation of album pages, story telling, photoquilts, etc. The success of these applications depends on the ease by which consumers can access their images. If they have to randomly look through the collection of digital images, or worse yet, through the index prints on the CD case containing the digital image CDs, for the images they want, then they will quickly throw up their hands in frustration and never use the collection again. However, if a computer was to automatically organize their images, based on each image's content, then retrieval would be simple, fast and effective.
The underlying technology that will be common across all these applications combines the tools of digital image processing with those of database management. The digital image processing tools extract information from the image that provides a compact representation of an image's content. The database management tools provide organizational structures for fast, effective retrieval of images based on their extracted content representation. Currently known database technologies are disclosed in International Application No. WO 9,852,119 (“Feature and Region Based Method for Database Image Retrieval”—which involves classifying images by features and region parameters, and searching a database for images within some threshold of the request), European Patent No. 872,803 (“Image Processing Apparatus for Managing Image Data”) and U.S. Pat. No. 5,852,823 (“Image Classification and Retrieval System Using a Query-by-Example Paradigm”). Current technologies for image content extraction and representation allow for content characterization in terms of low level features: global color, color composition, texture, and shape. The present invention addresses the issue of shape-based image content representation, organization and retrieval. None of the above-cited database references address the issue of shape.
In general, the definition for the task of shape-based image retrieval is as follows:
Given a query image, retrieve images within the database whose regions have a shape similar to those of the query.
There are three significant issues that must be addressed when developing a shape-based retrieval method:
Shape Representation: encoding the shape information in a form useful for organization, similarity determination, and efficient storage and retrieval.
Similarity Measure: producing results that are consistent with human visual perception. This measure is highly dependent upon the shape representation.
Index Structure: providing the organizational capabilities of the representation for efficient retrieval. The type of index depends upon the shape representation being used.
Existing solutions to the problem of image retrieval based on shape have addressed these issues in different ways. NETRA (W.Y. Ma, “Netra: A Toolbox for Navigating Large Image Databases,” Ph.D. Thesis, Dept. of Electrical and Computer Engineering, University of California, Santa Barbara, 1997) uses Fourier Descriptors as the shape representation. As is well known, Fourier Descriptors are not invariant to scale, translation, rotation and starting point, and therefore, must be normalized. In NETRA, the rotation and starting point normalization is achieved by throwing away the phase information (rotation and starting point only affect the phase). Scale invariance is achieved by dividing the magnitudes by the magnitude of the lowest frequency component. The Euclidean distance metric is used to measure the similarity of the normalized magnitudes. NETRA does not address the issue of indexing.
In the article “Similar Shape Retrieval Using Structural Feature Index” (J. E. Gary, R. Mehrotra,
Information Systems,
Vol. 18, No. 7, 525-537, 1993), the shape is represented as the structural components of the shape's boundary. The structural components are normalized and organized in a point access method index. Similarity is determined through a correspondence measure between the query structural component and the component retrieved through an index search.
The general approach used in Photobook (A. Pentland, R. W. Picard, S. Sclaroff, “Photobook: Tools for Content-Based Manipulation of Image Databases,”
SPIE,
Vol. 2185, 34-47) is identified as semantics-preserving image compression, i.e., compact representations that preserve essential image similarities. Their choice for shape is the Finite Element Method models of objects described in the article “Modal Matching for Correspondence and Recognition” (S. Sclaroff, A. Pentland,
M.I.T. Media Laboratory Perceptual Computing Section Technical Report No.
201, 1993). The representation is modes of free vibration of the finite element model of the selected feature points of the shape. Similarity is measured in terms of the deformation energy required to match the query shape to the database shape. Subsequent work developed a method for organizing the representations (S. Sclaroff, “Deformable Prototypes for Encoding Shape Categories in Image Databases,”
Pattern Recognition,
Vol. 30, No. 4, 627-641, 1997).
In the article “A Content-based Image Retrieval System” (C. Huang, D. Huang,
Image and Vision Computing,
Vol. 16, 149-163, 1993), the shape description comprises moments and Fourier Descriptors of the shape's boundary and feature points (unction and curvature) to capture internal structure. Retrieval is done in two phases. First, the moments and Fourier Descriptors of the query shape's boundary is compared using a city block distance measure to every image in the database and the top twenty candidates are chosen. Final similarity is determined through a complex hash table of the feature points.
The QBIC system (which is described in U.S. Pat. No. 5,579,471) initially represented shape through a combination of heuristic features such as area, circularity, eccentricity, major axis orientation, and a set of algebraic moment invariants. Similarity is judged through the Euclidean distance metric. As discussed in U.S. Pat. No. 5,579,471, similar heuristic features and moments do not guarantee perceptually similar shapes. More sophisticated shape descriptors were explored in the article “Retrieving Image by 2D Shape: A Comparison of Computation Methods with Human Perceptual Judgments,” (B. Scassellati, S. Alexopoulos, M. Flickner, Proc.
SPIE Storage and Retrieval for Image and Video Databases II,
San Jose, Calif., 2-14,1994), such as parametric curve distance, turning angle, sign of curvature, and a modified Hausdorf distance, with no decisive result.
In the article “Shape-Based Retrieval: A Case Study with Trademark Image Databases,” (A. K. Jain, A. Vailaya,
Pattern Recognition,
Vol. 31, No. 9, 1369-1390, 1998), the retrieval process comprises two phases with a different shape representation in each phase. In the first phase, “fast pruning”, the shape representation comprises edge angles (a histogram of edge directions) and moment invariants. This representation of the query shape is compared against all images in the database in order to retrieve the top ten candidates to pass on to the next phase. The second phase improves the similarity ranking by employing deformable templates. Again, they reported difficulty agreeing with human sub
Mehrotra Rajiv
Sotak George E.
Couso Yon J.
Eastman Kodak Company
Woods David M.
LandOfFree
Method and system for archival and retrieval of images based... 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 system for archival and retrieval of images based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for archival and retrieval of images based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3313801