Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-10-20
2002-05-21
Brier, Jeffrey (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06392649
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data computer database visualization and searching, and more particularly, to a method and apparatus for updating a multidimensional scaling database.
BACKGROUND OF THE INVENTION
The representation of similarity between objects is of great interest in human vision, in image processing, and in computer vision. Quite recently, Cutzu and Edelman reported on results which inferred that humans perhaps organize objects for recognition based on similarities. Their notion is that a “pattern of proximities” modeled an object in an internal representation space. See Cutzu, F. and S. Edelman, “Representation of object similarity in human vision: psychophysics and a computational model”. Vision Research 38(15/16), 1998, pp. 2229-2257. In addition, T. Kohonen has for years worked on a model, the self-organizing feature map, that clusters data while preserving the topological arrangement of the clusters. Kohonen's arguments are based on biologically plausible notions. See Kohonen, T. Self-Organizing Maps, 2nd ed. New York: Springer-Verlag, 1997; Tipping, M. E. “Topographic Mappings and Feed-Forward Neural Networks.” Ph.D. Thesis, University of Aston in Birmingham, February 1996.
Representations of object similarity in Cutzu and Edelman were visualized using Multidimensional Scaling (MDS), a technique where the relative locations of a set of nodes in a low dimensional (with respect to the size of the set) space are sought, given information that may be interpreted as distances. This follows the use of MDS for arranging images for visualization (Tomasi et al.) or to determine human perceptions of their relationships (Rogowitz et al.). See Rogowitz, B., T. Frese, J. R. Smith, and C. A. Bouman “Perceptual Image Similarity”, Human Vision and Electronic Imaging II, SPIE Proceedings 3299, 1998.
Multidimensional scaling (MDS) is a technique used for representing many types of data in a spatial arrangement that is generated from dissimilarity or similarity data. The dissimilarity data is put into a matrix of values which represent distances between data nodes, and then the configuration of data in space which most closely fits the matrix of values is looked for, by using a minimization procedure. Because all of the data is used in the minimization procedure at one time, the procedure is slow when applied to a large set of data nodes. In most MDS techniques, when a data node is added the entire matrix of values is used to recompute the configuration again. The computation technique, which at minimum involves a least squares solution, is therefore order O(n
3
) with respect to the number of data nodes, for a fixed number of iterations. Because MDS produces optimal results, database designers typically wish to use this technique for organizing the data in a database of images, some of which may contain thousands of images. However, a procedure of order O(n
3
) is generally unacceptable for even modest sized databases. This has been noted by others who have given methods for doing an acceptable job without using the MDS technique, in order to reduce the computational time. For example, see Faloutsos, C. and K. I. Lin., “FastMap: A Fast Method for Indexing. Datamining and Visualization of Traditional and Multimedia Datasets.” SIGMOD, 1995, pp. 163-174; and Tipping, M. E., “Topographic Mappings and Feed-Forward Neural Networks”, Ph.D. Thesis, University of Aston in Birmingham, February 1996.
Because of the considerations described above, there is a need for a way to update a new node in a MDS database which can be performed in a computationally efficient manner, preferably in order O(n) time or better.
SUMMARY OF THE INVENTION
The present invention provides a method, apparatus and article of manufacture for updating a new node in a multidimensional scaling (MDS) database having an existing node. The new node is compared to the existing node to obtain a disparity value. A distance value is calculated between the new node and the existing node, a sum of differences value is calculated for the disparity value and the distance value, and a sum of squares value is calculated for the disparity value and the distance value. The position of the new node is modified according to the sum of differences value and the sum of squares value.
REFERENCES:
patent: 5181259 (1993-01-01), Rorvig
patent: 5596703 (1997-01-01), Eick et al.
patent: 5835085 (1998-11-01), Eick et al.
patent: 5913211 (1999-06-01), Nitta
patent: 5986673 (1999-11-01), Martz
patent: 6012058 (2000-01-01), Fayyad et al.
Tipping, Michael E., “Topographic Mappings and Feed-Forward Neutral Networks”, The University of Aston in Birmingham, pp. 1-157, Feb. 1996.
Lindman and Caelli, “Constant Curvature Riemannian Scaling” Journal of Mathematical Psychology 17, pp. 89-109, 1978.
Rogowitz, Frese, Smith, Bouman, and Kalin, “Perpeptual Image Similarity Experiments”, Human Vision and Electronic Imaging IV, Proceedings of the SPIE, pp. 1-15, Jan. 26-29, 1998.
Faloutsos and Lin, “FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datastets”.
Kohonen, Teuvo,Self-Organizing Maps, 2nd Ed., Springer-Verlag, pp. 157-201, Jan. 1997.
Borg and Groenen,Modern Multidimensional Scaling, Theory and Applications, Springer-Verlag, pp. 135-157, 1997.
H. K. , Rising, “Generalizing a Fuzzy Edge Detection Model With Radon Transforms,” Unpublished, (Accepted for IEEE FUZZ '98 withdrawn because of non-attendance) pp. 1-6.
H. K.., Rising, “Deriving And combining Biologically Plausible Visual Processes with The Windowed Radon Transform,” Human Vision and Electronic Imaging III, SPIE, Vol. 3299, San Jose, pp. 519-525, Jan. 1998.
Blakely , Sokoloff, Taylor & Zafman LLP
Brier Jeffrey
Harrison Chante
LandOfFree
Method and apparatus for updating a multidimensional scaling... 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 apparatus for updating a multidimensional scaling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for updating a multidimensional scaling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2874145