Image analysis – Image segmentation – Region labeling
Patent
1996-04-29
1998-05-12
Boudreau, Leo
Image analysis
Image segmentation
Region labeling
382203, G06K 900
Patent
active
057518521
ABSTRACT:
A data structure representation of an original image called an image structure map (ISM) accurately, compactly and explicitly represents the geometry, topology and signal properties of regions in an original image. In mathematical terms, the ISM is a partition of the original image induced by a set of image region boundaries. The ISM data structure includes, for each region in the original image, a region data item that indicates the region boundary data items that form the region and a signal property descriptor indicating the value of signals computed for or assigned to the region. Region boundary data items represent image region boundaries that are determined to occur in the original image as a result of analyzing signal properties of original image locations. Vertices (endpoints and intersections) of region boundary data items are represented in the ISM in machine representable values that result from modifying infinite precision vertex values using a rounding operation that mathematically ensures topological and geometric consistency with the original image. The image structure map includes a spatial image indexing data structure in the form of hierarchy of partitions of the original image of varying levels of detail that allows for efficient point location. An illustrated implementation of the data structure has the form of a vertical cell decomposition. The ISM may be implemented to permit dynamic modifications so that changes to regions resulting from the insertion or deletion of new or changed region boundaries may be made without recomputing the entire ISM.
REFERENCES:
patent: 4490848 (1984-12-01), Beall et al.
patent: 4631690 (1986-12-01), Corthout et al.
patent: 4914605 (1990-04-01), Loughmiller, Jr. et al.
patent: 5226175 (1993-07-01), Deutsch et al.
patent: 5416890 (1995-05-01), Beretta
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
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.
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.
Nahed, 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.
Ketan Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1984, 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 Mathmatics, 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, no page number.
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, Combinatorics, 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, no author.
M. Garland and P. Heckbert, "Fast Polygonal Approximation of Terrains and Height Fields,"CMU Technical Report No. CMU-CS-95-181, Carnegie Mellon University, Pittsburgh, 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.
Guibas Leonidas John
Marimont David H.
Boudreau Leo
Tadayon Bijan
Xerox Corporation
LandOfFree
Image structure map data structure for spatially indexing an img does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image structure map data structure for spatially indexing an img, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image structure map data structure for spatially indexing an img will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-991589