Abstract
We present a novel algorithm for recovering a smooth manifold of unknown dimension and topology from a set of points known to belong to it. Numerous applications in computer vision can be naturally interpreted as instanciations of this fundamental problem. Recently, a non-iterative discrete approach, tensor voting, has been introduced to solve this problem and has been applied successfully to various applications. As an alternative, we propose a variational formulation of this problem in the continuous setting and derive an iterative algorithm which approximates its solutions. This method and tensor voting are somewhat the differential and integral form of one another. Although iterative methods are slower in general, the strength of the suggested method is that it can easily be applied when the ambient space is not Euclidean, which is important in many applications. The algorithm consists in solving a partial differential equation that performs a special anisotropic diffusion on an implicit representation of the known set of points. This results in connecting isolated neighbouring points. This approach is very simple, mathematically sound, robust and powerful since it handles in a homogeneous way manifolds of arbitrary dimension and topology, embedded in Euclidean or non-Euclidean spaces, with or without border. We shall present this approach and demonstrate both its benefits and shortcomings in two different contexts: (i) data visual analysis, (ii) skin detection in color images.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Narendra Ahuja and Mihran Tuceryan. Extraction of early perceptual structure in dot patterns. integrating region, boundary, and component Gestalt. CVGIP, 48(3):304–356, December 1989.
Luigi Ambrosio and Halil M. Soner. Level set approach to mean curvature flow in arbitrary codimension. J. of Diff. Geom., 43:693–737, 1996.
A. Becker and W. Cleveland. Brushing scatterplots. Technometrics, 29(2):127–142, 1987.
Marcelo Bertalmio, Li-Tien Cheng, Stanley Osher, and Guillermo Sapiro. Variational problems and partial differential equations on implicit surfaces: The framework and examples in image processing and pattern formation. UCLA Research Report, June 2000.
C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, Oxford, 1995.
J.D. Boissonnat. Representation of objects by triangulating points in 3-d space. In Proceedings of ICPR, pages 830–832, 1982.
J. Dolan and R. Weiss. Perceptual grouping of curved lines. In Image Understanding Workshop, pages 1135–1145, 1989.
H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes. ACM Transactions on Graphics, 13(1):43–72, 1994.
P. Fua and P. Sander. Segmenting unstructured 3d points into surfaces. In Proceedings of the European Conference on Computer Vision, pages 676–680, Santa Margherita Ligure, Italy, 1992.
L. R. Lamberson G. F. Gruska, K. Mirkhani. Non-Normal data Analysis. Garden City, MI: Multiface Publishing., 1967.
Tziritas G. Garcia C. Face detection using quantized skin color regions merging and wavelet packet analysis. IEEE Transactions on Multimedia, 1(3):264–277, 1999.
G. Guy. Inference of multiple curves and surfaces from sparse data. Technical Report 96-345, USC IRIS, Ph.D. thesis, 1996.
G. Hahn and S. Shapiro. Statistical Models in Engineering. John Wiley & Sons, 1967.
S. Hays, W. Statistics, and Y. Holt. Statistics. Holt, Rinehart and Winston, New York, 1981.
Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. Surface reconstruction from unorganized points. Computer Graphics, 26(2):71–78, 1992.
StatSoft Inc. Electronic Statistics Textbook, volume http://www.statsoftinc.com/textbook/stathome.html. Tulsa, StatSoft, 2001.
S. Kachigan. Statistical Analysis. Radius Press, 1986.
M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models. In Proceedings of the First International Conference on Computer Vision, pages 259–268, London, June 1987.
J. M. G. Lammens. A computational model of color perception and color naming (Ph.D. thesis). University of New York, Bufalo, 1994.
L. Lorigo, O. Faugeras, W.E.L. Grimson, R. Keriven, R. Kikinis, and C-F. Westin. Co-dimension 2 geodesic active contours for mra segmentation. In Proceedings of the International Conference on Information Processing in Medical Imaging, pages 126–139, June 1999.
Gérard Medioni, Mi-Suen Lee, and Chi-Keung Tang. A Computational Framework for Segmentation and Grouping. Elsevier, 2000.
P. Parent and S. Zucker. Trace inference, curvature consistency and curve detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2(8), 1989.
Tomaso Poggio and Federico Girosi. A theory of networks for approximation and learning. Technical Report 1140, AIM, 1989.
David. A. Rabenhorst. Interactive exploration of multidimensional data. In Proceedings of the SPIE Symposium on Electronic Imaging, volume 2179, pages 277–286, 1994.
S. Sarkar, K. Boyer, and I. inference. and management of spatial information using bayesian networks: perceptual organization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(3), 1993.
A. Shashua and S. Ullman. Structural saliency: the detection of globally salient structures using a locally connected network. IEEE Transactions on Pattern Analysis and Machine Intelligence, 7(1):90–94, 1988.
J. Shi and J. Malik. Normalized cuts and image segmentation. In Proceedings of the Conference on Computer Vision and Pattern Recognition, 1997.
K. Sobottka and I. Pitas. Extraction of facial regions and features using color and shape information. In Proceedings of the International Conference on Pattern Recognition, volume 3, pages C421–C425, Vienna, Austria, 1996.
R. Szelisky, D. Tonnesen, and D. Terzopoulos. Modelling surfaces of arbitrary topology with dynamic particles. In Proceedings of the Conference on Computer Vision and Pattern Recognition, pages 82–87, New York, June 1993.
Gabriel Taubin. A signal processing approach to fair surface design. Computer Graphics, 29(Annual Conference Series):351–358, 1995.
K.K. Thornber and R.L. Williams. Analytic solution of stochastic completion fields. In Proceedings of SCV, page 11B Segmentation and Grouping II, 1995.
G. Wyszecky and W. S. Stiles. Color science: Concepts and methods, quantitative data and formulae. John Wiley and Sons, New York, 1982.
H. Zhao, S. Osher, B. Merriman, and M. Kang. Implicit and non-parametric shape reconstruction from unorganized points using variational level set method. Computer Vision and Image Understanding, 80(3):295–319, 2000.
S.W. Zucker and R.A. Hummel. Toward a low-level description of dot clusters: Labeling edge, interior, and noise points. In Proceedings of CGIP, volume 9, pages 213–233, 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gomes, J., Mojsilovic, A. (2002). A Variational Approach to Recovering a Manifold from Sample Points. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds) Computer Vision — ECCV 2002. ECCV 2002. Lecture Notes in Computer Science, vol 2351. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47967-8_1
Download citation
DOI: https://doi.org/10.1007/3-540-47967-8_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43744-4
Online ISBN: 978-3-540-47967-3
eBook Packages: Springer Book Archive