Back to results
US 6,721,759 B1Granted
Techniques for spatial representation of data and browsing based on similarity
AssigneesSony Corporation, Sony Electronics Inc.
InventorHawley K. Rising, III
Life of this patent
Estimating the term…
Abstract
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 the image data based on the similarities (or dissimilarities) of the images are provided. In one embodiment, a hierarchical MultiDimensional Scaling (MDS) database for a set of images is provided, which allows for computationally efficient querying and updating of an image database. In one embodiment, techniques for modifying an MDS database for images are provided to allow for more intuitive browsing (or searching) of the images.
Claims15
A process for a computer-implemented hierarchical multidimensional scaling database for images, the process comprising:
- measuring dissimilarity of a set of images using a feature detector;
- 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, wherein the first subnode is a child of the root node;
- and
- determining a list of traversed nodes and traversed control points, performing the single node update at the first subnode, and sorting distances to the traversed control points in the traversed nodes, wherein the first subnode is a leaf node.
3 more elements
A process for a computer-implemented hierarchical spatial database of objects, the process comprising:
- calculating multiple stress vectors, wherein the multiple stress vectors represent stress factors between a first control point and multiple control points of the hierarchical spatial database, the multiple control points comprise multiple source control points and correspond to multiple objects, and the first control point comprises a target control point and corresponds to an object being queried, and wherein the calculating of the multiple stress vectors further comprises:
- storing values for multiple source bundle fields and multiple targets to 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 being a neighborhood of the target control point, wherein a position of the target control point is modified using the source field values, and wherein stress on the target control point in a node of the hierarchical spatial database is minimized;
- 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.
5 more elements
An article of manufacture or a hierarchical multidimensional scaling of database for objects, the article of manufacture comprising:
- a configuration for the hierarchical multidimensional scaling database, the hierarchical multidimensional scaling database comprising a root node and a leaf node, the leaf node being a subnode of the root node, wherein the root node and the leaf node each comprise control points corresponding to objects;
- and
- a query manager comprising:
- executable instructions for querying the hierarchical multidimensional scaling database;
- executable instructions for calculating multiple stress vectors, wherein the multiple stress vectors represent stress between a first control point and multiple control points of a node of the hierarchical multidimensional scaling database, the multiple control points comprise multiple source control points and correspond to multiple objects, the first control point comprises a target control point and corresponds to an object being queried, and the executable instructions for calculating comprise:
- instructions for storing values for multiple source bundle fields and multiple target bundle fields;
- and
- instructions for determining multiple source field values, the multiple source field values corresponding to multiple source control points, the multiple source control points being in a neighborhood of a target control point, wherein a position of the target control point is modified using the source field values, and wherein the stress on the target control point in a node of the hierarchical multidimensional scaling database is minimized;
- executable instructions for mapping the multiple stress vectors to multiple deformation vectors;
- executable instructions for combining the multiple deformation vectors into a single node update vector;
- and
- executable instructions for modifying a position of the first control point by moving the position of the first control point a fraction of the single node update vector.
9 more elements
A machine executing instructions for a hierarchical multidimensional scaling database for objects, the machine comprising:
- instructions executed on a microprocessor of the machine for managing a configuration of the hierarchical multidimensional scaling database, the hierarchical multidimensional scaling database comprising a root node and a leaf node, the leaf node being a subnode of the root node, wherein the root node and the leaf node each comprise control points corresponding to objects;
- instructions executed on a microprocessor of the machine for querying the hierarchical multidimensional scaling database, the objects being stored in a memory;
- instructions executed on the microprocessor of the machine for calculating multiple stress vectors, wherein the multiple stress vectors represent stress between a first control point and multiple control points of a node of the hierarchical multidimensional scaling database, and wherein the multiple control points comprise multiple source control points and correspond to multiple objects, the first control point comprises a target control point and corresponds to an object being queried, and the instructions executed for calculating comprise:
- instructions executed on the microprocessor of the machine for storing values for multiple source bundle fields and multiple target bundle fields;
- and
- instructions executed on the microprocessor of the machine for determining multiple source field values, the multiple source field values corresponding to multiple source control points, the multiple source control points being in a neighborhood of the target control point, wherein a position of the target control point is modified using the source field values, and wherein the stress on the target control point in a node of the hierarchical multidimensional scaling database is minimized;
- instructions executed in the microprocessor of the machine for mapping the multiple stress vectors to multiple deformation vectors;
- instructions executed on the microprocessor of the machine for combining the multiple deformation vectors into a single node update vector;
- and
- instructions executed in the microprocessor of the machine for updating the first control point by moving the first control point a fraction of the single node update vector.
7 more elements
An article of manufacture for a hierarchical multidimensional scaling of database for images, the article of manufacture comprising:
- a configuration for the hierarchical multidimensional scaling database, the hierarchical multidimensional scaling database comprising a root node and a leaf node, the leaf node being a subnode of the root node, wherein the root node and the leaf node each comprise control points corresponding to images;
- a query manager, the query manager comprising executable instructions for querying the hierarchical multidimensional scaling database of images, the instructions comprising:
- instructions for measuring dissimilarity of a set of images using a feature detector;
- instructions for obtaining a set of distances between control points corresponding to images in the root node;
- instructions for 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;
- instructions for determining a first bounding box for a first subnode, wherein the first subnode is a child of the root node;
- and
- instructions for determining a list of traversed nodes and traversed control points, performing the single node update at the first subnode, and sorting distances to the traversed control points in the traversed nodes, wherein the first subnode is a leaf node.
5 more elements
A machine executing instructions for a hierarchical multidimensional scaling database for images, the machine comprising:
- instructions executed on a microprocessor of the machine for managing a configuration of the hierarchical multidimensional scaling database, the hierarchical multidimensional scaling database comprising a root node and a leaf node, the leaf node being a subnode of the root node, wherein the root node and the leaf node each comprise control points corresponding to images;
- and
- instructions executed on a microprocessor of the machine for querying the hierarchical multidimensional scaling database, the images being stored in a memory, the instructions for querying comprising:
- instructions for measuring dissimilarity of a set of images using a feature detector;
- instructions for obtaining a set of distances between control points corresponding to images in the root node;
- instructions for 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;
- instructions for determining a first bounding box for a first subnode, wherein the first subnode is a child of the root node;
- and
- instructions for determining a list of traversed nodes and traversed control points, performing the single node update at the first subnode, and sorting distances to the traversed control points in the traversed nodes, wherein the first subnode is a leaf node.
6 more elements
An apparatus for a hierarchical multidimensional scaling database for images, the apparatus comprising:
- means for managing a configuration for the hierarchical multidimensional scaling database, the hierarchical multidimensional scaling database comprising a root node and a leaf node, the leaf node being a subnode of the root node, wherein the root node and the leaf node each comprise control points corresponding to images;
- and
- means for querying the hierarchical multidimensional scaling database, the means for querying comprising:
- means for measuring dissimilarity of a set of images using a feature detector;
- means for obtaining a set of distances between control points corresponding to images in the root node;
- means for 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;
- means for determining a first bounding box for a first subnode, wherein the first subnode is a child of the root node;
- and
- means for determining a list of traversed nodes and traversed control points, and further for sorting distances to the traversed control points in the traversed nodes, wherein the first subnode is a leaf node and the means for performing performs the single node update at the first subnode.
6 more elements
An apparatus for a hierarchical multidimensional scaling of database for objects, the apparatus comprising:
- means for managing a configuration for the hierarchical multidimensional scaling database, the hierarchical multidimensional scaling database comprising a root node and a leaf node, the leaf node being a subnode of the root node, wherein the root node and the leaf node each comprise control points corresponding to objects;
- and
- means for querying the hierarchical multidimensional scaling database, the means for querying comprising:
- means for calculating multiple stress vectors, wherein the multiple stress vectors represent stress between a first control point and multiple control points of a node of the hierarchical multidimensional scaling database, the multiple control points comprise multiple source control points and correspond to multiple objects, the first control point comprises a target control point and corresponds to an object being queried, and the means for calculating comprises:
- means for storing values for multiple source bundle fields and multiple target bundle fields;
- and
- means for determining multiple source field values, the multiple source field values corresponding to multiple source control points, the multiple source control points being in a neighborhood of the target control point, wherein a position of the target control point is modified using the source field values, and wherein the stress on the target control point in a node of the hierarchical multidimensional scaling database is minimized;
- means for mapping the multiple stress vectors to multiple deformation vectors;
- means for combining the multiple deformation vectors into a single node update vector;
- and
- means for modifying a position of the first control point by moving the position of the first control point a fraction of the single node update vector.
8 more elements
Dependencies are inferred from the claim text.