Patent
1995-12-29
1998-01-20
Nguyen, Phu K.
G06F 1500
Patent
active
057108773
ABSTRACT:
A data structure representation of an image called an image structure map (ISM) accurately and explicitly represents the geometry, topology and signal properties of regions in an original image and allows for efficient and accurate spatial indexing of the image and those regions. The ISM may serve as the basis for an image interaction system in which a user interacts with a rendered view of an original image that is produced from the ISM data structure. The rendered view of the original image represents the geometry and topology of the original image as represented in the ISM. The user interacts with the rendered view to make alterations to, or to query, the structures in the ISM. The user may also modify the ISM by interacting directly with a displayed view of the original image. The user may further invoke automatic operations to be performed using the original image data structure that produce image region data, such as signal property descriptors and boundary data, that may be used to modify the ISM. An image interaction system implemented in this manner takes full advantage of automatic computation methods to capture the geometric and topological properties of an image while permitting a user to employ human perceptual skills to augment the automatic operations. An illustrated implementation of the system uses an ISM having the form of a vertical cell decomposition that is mathematically robust, topologically consistent with the original image and is able to be modified dynamically--that is, without recomputing the entire ISM when a change is made.
REFERENCES:
patent: 4631690 (1986-12-01), Corthout et al.
patent: 4914605 (1990-04-01), Loughmiller, Jr. et al.
patent: 5440652 (1995-08-01), Ting
patent: 5485568 (1996-01-01), Venable et al.
patent: 5499322 (1996-03-01), Thirion et al.
patent: 5546107 (1996-08-01), Deretsky et al.
patent: 5583953 (1996-12-01), Harrington
patent: 5586232 (1996-12-01), Yoshida
Ketan Mulmuley, Computational Geometry: An introduction Through Randomized Algorithms, Prentice-Hall, 1994, ch. 2, pp. 29-35, 52-55, 58-66, and 78-96; ch. 3, pp. 111-114 and 117-119; ch. 4, pp. 126-135, 140-149, and 162-167; and ch. 5, pp. 192-210.
Adobe Photoshop.TM. 2.5 for Macintosh, User Guide and Tutorial, pp. 15-29 and pp. 79-86; Adobe Systems Incorporated, Mountain View, California, 1993.
Colorize 2.0.TM. (DS Design Inc. of Cary, North Carolina), software product review in MacWEEK, p. 30, Jul. 24, 1995.
G. Koepfler, C. Lopez and J.M. Morel, "A Multiscale Algorithm for Image Segmentation by Variational Method," Journal of Numerical Analysis of the Society of Industrial and Applied Mathematics, vol. 31, No. 1, Feb. 1994, pp. 282-299.
L. Guibas and D. Marimont, "Rounding Arrangements Dynamically," Proceedings of the 11th ACM Symposium on Computational Geometry (SCG '95), Vancouver, B.C., Jun., 1995.
Daniel H. Greene and Frances F. Yao, "Finite-Resolution Computational Geometry," Proc. 27th Ann. Symp. on Foundations of Computer Science, 1986, pp. 143-152.
Ketan Mulmuley, in "A fast planar partition algorithm I", Journal of Symbolic Computation, v. 10, 1990, pp. 253-280.
Ketan Mulmuley, "Randomized Multidimensional Search Trees: Dynamic Sampling," Proceedings of the 7th ACM Symposium on Computational Geometry (SCG,) 1991, pp. 121-131.
H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel and M. Sharir, "Arrangements of Curves in the Plane-Topology, Combinatoris, and Algorithms", Theoretical Computer Science 92 (1992), pp. 319-336.
M. Gangnet, J-C Herve, T. Pudet and J-M Van Thong, "Incremental Computation of Planar Maps," Computer Graphics (SIGGRAPH '89), vol. 23, No. 3, 1989, pp. 345-354.
Malik, Jitendra, "Interpreting line drawings of curved objects" International Journal of Computer Vision, vol. 1, No. 1, pp. 73-103, 1987.
P Vaxiviere et al., "Celesstin: CAD Conversion of Mechanical Drawings," IEEE Computer, vol. 25, No. 7, Jul. 1992, pp. 46-54.
L. Boatto, et al., in "An Interpretation System for Land Register Maps," IEEE Computer, vol. 25, No. 7, Jul. 1992, pp. 25-33.
Adobe Streamline 3.0 User's Manual, Adobe Systems Incorporated, Oct. 1993, Chapters 1, 2, 4, and 5, and p. 62.
M. Garland and P. Heckbert, "Fast Polygonal Approximation of Terrains and Height Fields," CMU Technical Report No. CMU-CS-95-181, Carnegie Mellon University, Pittsburg, PA, Sep., 1995.
L. de Floriani and E. Puppo, "Hierarchical Triangulation for Multiresolution Surface Description," ACM Transactions on Graphics, vol. 14, No. 4, Oct. 1995, pp. 363-411.
Paul J. Besl and Ramesh C. Jain, "Segmentation Through Variable-Order Surface Fitting," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, No. 2, pp. 167-192, 1988.
M. Kocher and M. Kunt, "Image data compression by contour texture modeling" in Applications of Digital Image Processing, Andre Oosterlink, Andrew G. Tescher, Eds., Proceedings of the SPIE, 1983, pp. 132-139.
Nahred, A., and Peroche, B., "A 21/2-D hierarchical model based on planar maps", Computer & Graphics, vol. 20, No. 1, Jan./Feb. 1996, pp. 115-123.
Guibas Leonidas John
Marimont David H.
Baves Judith C.
Nguyen Phu K.
Xerox Corporation
LandOfFree
User-directed interaction with an image structure map representa does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with User-directed interaction with an image structure map representa, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and User-directed interaction with an image structure map representa will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-732183