Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-24
2004-04-13
Pardo, Thuy N. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06721759
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates generally to browsing and database technology and, more particularly, to image browsing and image database technology.
2. Background of the Invention
Research is being performed to determine improved techniques for the representation of various types of data in a database for purposes of efficient and intuitive browsing or searching of the data. For example, some researchers have investigated the organization of objects, such as images, based on the similarities of the images. This approach is based on the model that humans perceive image data based on similarities, and thus, such an approach for a computer-implemented technique would provide a more intuitive approach.
MultiDimensional Scaling (MDS) is a well-known technique for representing various types of data in a spatial arrangement that is based on similarity or dissimilarity data. In particular, MDS can be used as a technique for storing objects, such as images, as a relative set of nodes in a low dimensional space (with respect to the size of the set). The relative location of the nodes is dependent upon the object similarities or dissimilarities, which are interpreted as a set of distances between the nodes. The object similarities or dissimilarities can be determined by a variety of techniques, which can then be used to determine the set of distances between the nodes in the MDS space.
However, MDS is a computationally expensive technique. In particular, for image databases, MDS can be impractical due to its global nature, which requires extensive matrix processing. For example, the typical MDS techniques may not be practical for larger image databases (e.g., on the order of hundreds or thousands of images). Moreover, the typical MDS techniques do not necessarily provide biologically plausible techniques for the spatial representation of data, and in particular, do not allow for intuitive browsing of, for example, images in an image database.
SUMMARY OF THE INVENTION
Accordingly, the present invention provides improved techniques for spatial representation of data and browsing based on similarity. For example, improved techniques for spatial representation of image data and browsing of stored images based on the similarities (or dissimilarities) of the stored images are provided. In one embodiment, a process for querying a computer-implemented hierarchical MultiDimensional Scaling (MDS) database for images includes measuring dissimilarity of a set of images using feature detectors; obtaining a set of distances between control points corresponding to images in a root node; performing a single node update at the root node to determine a first position in the root node of an image being queried or added; determining a first bounding box for a first subnode, in which the first subnode is a child of the root node; and determining a list of traversed nodes and traversed control points, performing a single node update at the first subnode, and sorting distances to the traversed control points in the traversed nodes, in which the first subnode is a leaf node. In one embodiment, the process further includes obtaining a list of images in a second subnode, in which the second subnode is the child of the first subnode; and repeating the performing of the single node update and the determining of a second bounding box for the second subnode.
In one embodiment, a process for a computer-implemented hierarchical spatial database of objects includes determining distances between control points corresponding to objects in a root node of the hierarchical spatial database of objects; and determining a position of a first control point in the root node for a first object, in which the first object is being queried, and in which the hierarchical spatial database of objects includes the root node and a first subnode, the first subnode being a child of the root node. The process can further include traversing a first subnode and performing a single node update on the first subnode; performing the single node update at a leaf node, the leaf node being a descendant of the first subnode; and determining traversed subnodes and traversed control points, and sorting distances between the traversed control points in the traversed subnodes and the control points in the root node to the control point for the first object. Also, for performing an add operation on the hierarchical spatial database of objects, the process can further include adding the first object to the hierarchical spatial database of objects, in which the leaf node is subdivided if the leaf node is full, and in which multidimensional scaling is executed on the leaf node and updating all bounding boxes in the traversed path to the first object. The hierarchical spatial database of objects can be initialized by executing instructions for approximating a convex hull. For example, this process can be used for browsing and modifying a hierarchical MDS database for images, in which the images are stored on one or more memories (e.g., local or remote memories of data processing devices).
In one embodiment, a process for a computer-implemented hierarchical spatial database of objects includes calculating multiple stress vectors, in which the multiple stress vectors represent stress factors between a first control point and multiple control points of the hierarchical spatial database of objects, and in which the multiple control points correspond to multiple objects, and the first control point corresponds to an object being queried; and mapping the multiple stress vectors to multiple deformation vectors; combining the multiple deformation vectors into a single node update vector; and updating the first control point by moving a position of the first control point based on a fraction of the single node update vector. Further, the multiple control points can include multiple source control points, and the first control point can represent a target control point, in which the calculating of the multiple stress vectors includes the following: storing values for multiple source bundle fields and multiple target bundle fields; and determining multiple source field values, the multiple source field values corresponding to the multiple source control points, the multiple source control points in a neighborhood of the target control point, in which a position of the target control point is modified using the source field values, and in which the stress on the target control point in a node of the hierarchical spatial database of objects is minimized. For example, the fields can advantageously correspond to local fields (e.g., as opposed to the global stress factor of standard MDS techniques) or anisotropic fields.
REFERENCES:
patent: 5710916 (1998-01-01), Barbara et al.
patent: 5832182 (1998-11-01), Zhang et al.
patent: 5963956 (1999-10-01), Smartt
patent: 6047080 (2000-04-01), Chen et al.
patent: 6148295 (2000-11-01), Megiddo et al.
patent: 6161105 (2000-12-01), Keighan et al.
patent: 6263334 (2001-07-01), Fayyad et al.
patent: 6289354 (2001-09-01), Aggarwal et al.
patent: 6446068 (2002-09-01), Kortge
Agrawal et al., “Modeling Multidimensional Databases”, IEEE, 1997, pp. 232-243.*
Kao et al., “Efficient Proximity Search in Multivariate Data”, IEEE, Jul. 1998, pp. 145-154.*
Piamsa-nga et al., “A Parallel Model for Multimedia Database on Cluster System”, IEEE, Jul. 1998, pp. 648-652.*
Petrakis, “Similarity Searching in Medical Image Databases”, IEEE, 1997, pp. 435-447.*
Rehrauer et al., “Multiscale Markov Random Fields for Large Image Datasets Representation”, IEEE, 1997, pp. 255-257.*
Yang et al., “MB+-Tree: A New Index Structure for Multimedia Databases”, IEEE, 1995, pp. 151-158.*
Hou et al., “Medical Image Retrieval by Spatial Features”, IEEE, 1992, pp. 1364-1369.
Blakely , Sokoloff, Taylor & Zafman LLP
Pardo Thuy N.
LandOfFree
Techniques for spatial representation of data and browsing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Techniques for spatial representation of data and browsing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Techniques for spatial representation of data and browsing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229118