Visual navigation in perceptual databases

• US 6,121,969 A
• Filed: 07/29/1997
• Issued: 09/19/2000
• Est. Priority Date: 07/29/1997
• Status: Expired due to Term

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Santini, Simone, Jain, Ramesh
• Primary Examiner(s): DELA TORRE, CRESCELLE N
• Application Number:
  US08/902,493
• Time in Patent Office: 1,148 Days
• Field of Search: 345/355, 345/356, 345/357, 345/419, 345/427, 345/440, 345/968, 345/348, 345/339, 707/2, 707/5, 707/6, 707/4, 707/7, 707/104, 382/165, 382/209, 382/218, 382/220, 382/305
• US Class Current: 715/850
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A similarity-based database of images, where images are preferably ranked and correlated in correspondence to biological preattentive similarity, supports a new type of interface for visual navigation within the database to the end that a human may perceive not only selected images resultant from a query, but the relationship between the selected images. In particular, navigation is within a display space whose geometric characteristics depend on the geometry of the perceptual space in which image similarity is measured. The display space is a subset of the three dimensional Euclidean space that, for many of the distance functions appropriate to the images, is contained in the unit cube. The perceptual intuition of the metric is given (i) in part by the distribution of images in the space, and (ii) in part by making the motion of the user uniform with respect to the metric of the space.

Claims

1. An image data presentation system comprising:

a data store means for holding a multiplicity of images;

an input means for permitting an operator to query the multiplicity of images;

a computer means for ranking the multiplicity of images that are within the data store means in response to a query received from the input means on the basis of preattentive similarity, meaning that the multiplicity of images are endowed with a metric structure, rising from the query, so as to create a Riemann manifold of N dimensions A, B, C, . . . L, M, N within which Riemann manifol the multiplicity of images are ordered so as to preserve information about their relationships; and

a display means for displaying in three dimensions the ranked images within the N-dimensional Riemann manifold as (i) a perceptual space having a three-dimensional geometry X, Y, and Z in accordance with some arbitrary three dimensions B, E and H of the metric of the Riemann manifold, with (ii) the ranked images being located within the X, Y and Z coordinates of the three-dimensional perceptual space in accordance with their ranked relationships in the arbitrary three dimensions B, E and H;

wherein the relationship of the displayed images is, at least insofar as regards the X, Y and Z metric of the three-dimensional geometry of the three-dimensional perceptual space, made visible, the images being both (i) located in the perceptual space in accordance with their properties in the arbitrary three dimensions B, E and H of the N-dimensional Riemann manifold, and (ii) located elative to one another in accordance with the similarities or distinctions of these properties.

2. The image data presentation system according to claim 1

wherein the input means is further for permitting an operator to navigate among the images displayed within the perceptual space;

wherein the computer means is dynamically re-ranking the images in accordance with navigational inputs received from the operator via the input means; and

wherein the display means is presenting the re-ranked images dynamically;

wherein the operator adds a kinetic experience to the visual presentation of the geometric organization of the images.

3. An image database system responsive to a user query for displaying selected images best satisfying the query out of a great multiplicity of stored images characterize in that

conventional matching between stored images in response to the user query is replaced by more general similarity measures based on (i) simple sensorial impressions that are accorded the user (ii) in a three-dimensional perceptual space (iii) endowed with a Riemann metric that is more general than is the usual Euclidean distance;

wherein (i) simple sensorial impressions simply means that the user can see or otherwise sense the selected images;

wherein (ii) in a three-dimensional perceptual space simply means that the selected images which accord the user the simple sensorial impressions are within a three-dimensional Euclidean space, or volume;

wherein (iii) endowed with a Riemann metric simply means that the three-dimensional perceptual space is ordered, and thus the selected images displayed therein are sensed by the user to be ordered in accordance with their properties in each of three display dimensions, corresponding to three dimensions of the Riemann metric as were relevant to the query;

wherein the user does not merely sense the selected images, but further senses the relationship between and among the selected images within the three-dimensional perceptual space, and in accordance with the Riemann metric with which the three-dimensional perceptual space is endowed;

wherein three-dimensional geometric aspects of the displayed three-dimensional perceptual space permit the user to understand relation between the displayed images in three different dimensions of the Riemann manifold at the same time, and not merely the presence or absence of any one of the great multiplicity of images.

4. The image database system according to claim 3 further characterized in that

distances in the perceptual space are computed dependent upon a particular query that is being asked.

5. A man-machine interfacing method for permitting a machine user to navigate in a database of visual images, to navigate meaning to come to learn and to see and to know not merely the visual images that are within the database but also relationships between and among these visual images, the method comprising:

classifying a database of visual images in accordance with an N-dimensional metric of the images, each dimension A, B, C . . . L, M, N of the database'"'"'s metric being defined by the user as input to the machine;

displaying a subset of the visual images that are classified in the N-dimensional database in a three-dimensional Euclidean display space that is contained in a unit cube, the three-dimensional unit cube having axes X, Y and Z corresponding to some arbitrary user-selected dimensions B, D, G of the N-dimensional database;

wherein the metric inside the display space is derived from the user inputs as to both the dimensions A, B, C . . . L, M, N of the database, and also as to the particular arbitrary dimensions B, D, G of the database that are displayed along axis X, Y and Z;

populating the three-dimensional display space with visually perceptible images from the N-dimensional data base of images, each image being located in X, Y and Z coordinate locations of the three-dimensional display space in accordance with the B, D and G metrics of the image; and

permitting the user, by further input in the nature of movement of a computer mouse, to visually navigate among the displayed image in the three-dimensional display space;

therein by the permitted visual navigation the user may come to know both (i) the images that are within the database and the relationships among and between these images, at least for the metrics currently displayed within the three-dimensional display space, which metrics were derived from the user'"'"'s own inputs, and, also, (ii) the suitability of the chosen metrics, which metrics were defined by the user as input to the machine, to reveal relationships among and between the images.

6. A man-machine interface method of recursively interacting with a database containing object records having a multiplicity of attributes to the end of (i) interactively developing particular criterion or criteria, out of multiplicity of criteria, by which (ii) a plurality of object records that have attributes that are, by particular finally-developed criterion or criteria, closest to a reference object record may best be identified, the method comprising the steps of:

manually selecting three criterion corresponding to an associated three or more attributes possessed by object records having a multiplicity of attributes that are located within a machine database;

searching and ordering with the machine the object records of the machine database in accordance with each of the selected three criterion;

displaying with the machine the results of the searching and ordering in a three-dimensional plot with each of the three criterion serving as a metric of an associated one axis and with each object record plotted, each in accordance with its attributes, relative to each axis, the attributes of a reference object record being at the origin of the plot;

manually observing a distribution of the three-dimensionally plotted and displayed object records in any of their locations, dispersion, or clustering in each ordinate axis of the display in order to recognize and to formulate one or more new criterion that might potentially be more advantageous for associating and for identifying selected object records closely corresponding to the reference object record than are a corresponding one or more of the old criterion by which the displayed object records are presently ranked and ordered;

recursively repeating the steps of manually selecting with the new criterion substituted for the old criterion, machine searching and ordering, machine displaying, and manually observing to formulate new criterion until, finally, the object records are three-dimensionally finally plotted and finally displayed in accordance with a finally-developed three criteria;

identifying from the final display those individual object records that are closest by the finally-developed three criteria to the reference object record, which reference object record is always plotted at the origin;

wherein the most telling three criterion and associated object record attributes to identity those individual object records closest to the reference object record may not have been known at the start of the process, but as the steps of the process are correctly recursively performed it is possible to draw out of the database of object records those object records that are truly close, at least in three criterion that are presumptively meaningful, to the reference object record.

7. The man-machine interface method according to claim 6

wherein the displaying is further of a visually perceptible attribute of at least some of the ordered, plotted, records;

wherein during the manually observing an observation of this visually perceptible attribute aids in the recognition and the formulation of the one or more new criterion.

8. The man-machine interface method according to claim 7

wherein the displaying of the ordered, plotted, records along with a visually perceptible attribute of at least some of these records is so that the visually perceptible attributes are co-located with the plotted records within the three-dimensional plot;

wherein association of any one plotted record with its associated visual attribute is itself visual, and unambiguous.

9. A method of displaying a multiplicity of object records, each of which object records is visually perceptible meaning that at least to some trained human eye a distinction of the object record when displayed from other object records likewise displayed is readily visually sensible, from a database of a great multiplicity of visually perceptible object records, the display method comprising:

selecting a plurality of criterion corresponding to an associated plurality of attributes possessed by each of a great multiplicity of object records, each having a multiplicity of object records of the machine database in accordance with the selected plurality of criterion;

displaying the results of the searching and ordering in a plot with each of the selected plurality of criterion lying along an associated one axis, with each object record being plotted along all axis in accordance with its attributes, and with an arbitrary object record being at the origin of the plot;

concurrently with the displaying of the plot, displaying at the same time at least some of the plotted object records in a manner in which these object records are both (i) visually perceptible, and (ii) positionally associated with the plot, any attributes of the object records that are so visually perceptible not necessarily being those that correspond to any of the plurality of the criterion of the plot;

wherein the displayed (i) plot, in combination with (ii) visually perceptible attributes of at least some of the plotted object records positionally associated with these at least some object records, permits a human to form an impression that those plotted object records that are located relatively more closely to, and relatively more distant from, the arbitrary object record along any one or more of the axes either are, or are not, coherently related one to another in their perceptible attributes displayed;

wherein if the human is given the impression that the at least some object records displayed are, along some axis or axes an at some location or locations of the plot, coherently related, then this means that object records within associated regions of the plot, whether ranked in accordance with the visually perceptible attributes or not, are likewise coherently related, meaning that the object records have likely been successfully (i) rationally ordered by (ii) some rational criteria of ordering;

wherein if the human is given the impression from the at least some object records displayed that there is no location of the plot where at least some object records are coherently related, then this does not conclusively mean that there are no such regions, nor any such attributes, but it does indicate that, at least for the perceptible attributes and for the at least some object records displayed, to the human the object records have unlikely been (i) rationally ordered by (ii) any rational criteria of ordering;

wherein the method is as much a test for the rationality of some criteria of ordering as it is a basis for ordering object records in accordance with some criteria.

10. A computer method of displaying digital images comprising:

ordering with a computer digital images in each of three criteria A, B, C each of which criterion A or B or C is perceptible to the human eye in the images should they be displayed;

defining with the computer a display space that is

three-dimensional, with axes of criterion A and criterion B and criterion C, and

endowed with a non-linear metric along at least one of the axes of criterion A or B or C, said non-linear metric simply meaning that mapping of an associated criterion to the at least one axis is, although in monotonic rank order, not so that equal differences in the associated criterion will map to equal distances along the at least one axis but that, instead, equal differences in the associated criterion will map to unequal distances along the at least one axis;

generating with the computer thumbnail images corresponding to each of the digital images;

displaying with the computer the generated thumbnail images in the defined three-dimensional display space in accordance with their ordering in each of the three criteria A, B, and C.

11. The method according to claim 10 further comprising:

scaling the displaying in accordance with input to the computer from a human viewer of the thumbnail images within the three-dimensional display space;

wherein at expanded scale the human viewer can better distinguish between individual thumbnail images.

12. The method according to claim 11 further comprising:

orienting he displaying in accordance with input to the computer from the human viewer of the thumbnail images within the three-dimensional display space;

wherein a differing angular orientations the human viewer can better distinguish which of the criterion A, B and C most, and least, pronouncedly separates the individual thumbnail images in aggregate, and in scaled regions of the three-dimensional display space.

13. A computerized method of generating and displaying a particular computer-user-navigatable three-dimensional computer-generated virtual-reality space, the method characterized in that

visual perceptible elements in the form of separate detached images are displayed within the three-dimensional space where

the displayed separate images are ranked and are located within the three-dimensional space in accordance with their individual values in each of three criteria A, B, and C that comprise the axes of the three-dimensional space,

the three criteria A, B and C are each perceptible to a human viewer of the images that are displayed within the three-dimensional pace, and thus the separate images themselves are distinguishable one to the next as displayed, and

a viewer of the displayed images can navigate among the displayed images and within the three-dimensional space in order to observe the ranking and locations thereof in accordance with each of the three criteria;

while

successive inputs from the viewer cause re-ranking and re-locating an re-displaying of the separate images in the three-dimensional space in accordance with successive new, viewer-specified, criteria, thus producing over time successive new three-dimensional spaces each with separate images displayed therein;

wherein by control of the criteria by which the images are displayed, the viewer of the displayed images may come, over time, to identify and choose criteria that are suitable to isolate particular images of interest from all other images.

14. An iterative man-computer method so that the man

(i) may come to identify criteria useful individually or in combination or both to individually and in combination so as to find one or more sought-after images within a database of a great multiplicity of images unindexed at least by any criteria that is useful for the finding, and

(ii) may use the criteria so identified to, ultimately, find the one or more sought-after images, the method comprising:

first manually inputting to the computer three criteria by which all the images within the database are to be ordered;

creating with the computer a three-dimensional display space having three metrics derived from the three criteria of the user;

displaying within the created display space thumbnail images of all the great multiplicity of images;

second manually inputting to the computer by movement of a computer mouse spatial data therein to cause visual navigation among the displayed thumbnail images in each and in all of the three metrics of the display space, the man noting which metrics seem relatively more effective to distinguish among and between the displayed thumbnail images in manners potentially effective to isolate the sought-after images and which metrics seem relatively less effective;

iteratively repeating, with new criteria manually derived from experience in the navigation, the first manually inputting, the creating, the displaying, and the second manually inputting until, ultimately, criteria are developed that permit, during the course of navigation to a man-selectable region of the image space, a finding of the one or more sought-after images.