Controlled-topology filtering

ABSTRACT

Many applications require the extraction of isolines and isosurfaces from scalar functions defined on regular grids. These scalar functions may have many different origins: from MRI and CT scan data to terrain data or results of a simulation. As a result of noise and other artifacts, curves and surfaces obtained by standard extraction algorithms often suffer from topological irregularities and geometric noise.While it is possible to remove topological and geometric noise as a post-processing step, in the case when a large number of isolines are of interest there is a considerable advantage in filtering the scalar function directly. While most smoothing filters result in gradual simplification of the topological structure of contours, new topological features typically emerge and disappear during the smoothing process.In this paper, we describe an algorithm for filtering functions defined on regular 2D grids with controlled topology changes, which ensures that the topological structure of the set of contour lines of the function is progressively simplified.

REFERENCES

• 1: Carlos Andújar , Pere Brunet , Dolors Ayala, Topology-reducing surface simplification using a discrete solid representation, ACM Transactions on Graphics (TOG), v.21 n.2, p.88-105, April 2002 [doi>10.1145/508357.508359]
• 2: Bajaj, C., and Schikore, D. 1998. Topology preserving data simplification with error bounds. Journal on Computers and Graphics vol. 22, 1, 3--12.
• 3: Bremer, P.-T., Pascucci, V., Edelsbrunner, H., and Hamann, B. 2004. A topological hierarchy for functions on triangulated surfaces. IEEE Trans. Vis. Comput. Graphics 10, 385--396.
• 4: Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.918-926, January 09-11, 2000, San Francisco, California, United States
• 5: Hamish Carr , Jack Snoeyink , Michiel van de Panne, Simplifying Flexible Isosurfaces Using Local Geometric Measures, Proceedings of the conference on Visualization '04, p.497-504, October 10-15, 2004 [doi>10.1109/VIS.2004.96]
• 6: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 7: Damon, J. 1995. Local Morse theory for solutions to the heat equation and Gaussian blurring. J. Differential Equations 115, 2, 368--401.
• 8: Wim de Leeuw , Robert van Liere, Collapsing flow topology using area metrics, Proceedings of the conference on Visualization '99: celebrating ten years, p.349-354, October 1999, San Francisco, California, United States
• 9: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 10: Udo Diewald , Tobias Preuβer , Martin Rumpf, Anisotropic Diffusion in Vector Field Visualization on Euclidean Domains and Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.139-149, April 2000 [doi>10.1109/2945.856995]
• 11: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• 12: H. Edelsbrunner , D. Letscher , A. Zomorodian, Topological persistence and simplification, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.454, November 12-14, 2000
• 13: Herbert Edelsbrunner , John Harer , Afra Zomorodian, Hierarchical morse complexes for piecewise linear 2-manifolds, Proceedings of the seventeenth annual symposium on Computational geometry, p.70-79, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378626]
• 14: Herbert Edelsbrunner , John Harer , Vijay Natarajan , Valerio Pascucci, Morse-smale complexes for piecewise linear 3-manifolds, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777846]
• 15: Jihad El-Sana , Amitabh Varshney, Controlled simplification of genus for polygonal models, Proceedings of the 8th conference on Visualization '97, p.403-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 16: Luc Florack , Arjan Kuijper, The Topological Structure of Scale-Space Images, Journal of Mathematical Imaging and Vision, v.12 n.1, p.65-79, Feb. 2000 [doi>10.1023/A:1008304909717]
• 17: Freeman, H., and Morse, S. P. 1967. On searching a contour map for a given terrain profile. Journal of the Franklin Institute 248, 1--25.
• 18: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 19: Han, X., Xu, C., and Prince, J. 2001. A topology preserving deformable model using level sets. In Computer Vision and Pattern Recognition, vol. 2, 765--770.
• 20: Hart, J. C. 1998. Morse theory for implicit surface modeling. In Mathematical Visualization, H.-C. Hege and K. Polthier, Eds. Springer-Verlag, Oct., 257--268.
• 21: Taosong He , Lichan Hong , Amitabh Varshney , Sidney W. Wang, Controlled Topology Simplification, IEEE Transactions on Visualization and Computer Graphics, v.2 n.2, p.171-184, June 1996 [doi>10.1109/2945.506228]
• 22: James L. Helman , Lambertus Hesselink, Visualizing Vector Field Topology in Fluid Flows, IEEE Computer Graphics and Applications, v.11 n.3, p.36-46, May 1991 [doi>10.1109/38.79452]
• 23: Karim Mahrous , Janine Bennett , Gerik Scheuermann , Bernd Hamann , Kenneth I. Joy, Topological Segmentation in Three-Dimensional Vector Fields, IEEE Transactions on Visualization and Computer Graphics, v.10 n.2, p.198-205, March 2004 [doi>10.1109/TVCG.2004.1260771]
• 24: Milnor, J. 1963. Morse Theory. Princeton Univ. Press, New Jersey.
• 25: Xinlai Ni , Michael Garland , John C. Hart, Fair morse functions for extracting the topological structure of a surface mesh, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 26: Peer-Timo Bremer , Valerio Pascucci , Bernd Hamann, Maximizing Adaptivity in Hierarchical Topological Models, Proceedings of the International Conference on Shape Modeling and Applications 2005 (SMI' 05), p.300-309, June 13-17, 2005 [doi>10.1109/SMI.2005.28]
• 27: P. Perona , J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.629-639, July 1990 [doi>10.1109/34.56205]
• 28: Rana, S., Ed. 2004. Topological Data Structures for Surfaces: An Introduction to Geographical Information Science. Wiley and Sons.
• 29: Sircar, J. K., and Cerbrian, J. A. 1986. Application of image processing techniques to the automated labelling of raster figitized contours. In Int. Symp. on Spatial Data Handling, 171--184.
• 30: Bong-Soo Sohn , Chandrajit Bajaj, Time-Varying Contour Topology, IEEE Transactions on Visualization and Computer Graphics, v.12 n.1, p.14-25, January 2006 [doi>10.1109/TVCG.2006.16]
• 31: Yiying Tong , Santiago Lombeyda , Anil N. Hirani , Mathieu Desbrun, Discrete multiscale vector field decomposition, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 32: Xavier Tricoche , Gerik Scheuermann , Hans Hagen, A topology simplification method for 2D vector fields, Proceedings of the conference on Visualization '00, p.359-366, October 2000, Salt Lake City, Utah, United States
• 33: Xavier Tricoche , Gerik Scheuermann , Hans Hagen, Continuous topology simplification of planar vector fields, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 34: Tricoche, X., Wischgoll, T., Scheuermann, G., and Hagen, H. 2002. Topology tracking for the visualization of time-dependent two-dimensional flows. Computers & Graphics 26, 2 (Apr.), 249--257.
• 35: Tricoche, X. 2002. Vector and Tensor Field Topology Simplification, Tracking, and Visualization. PhD thesis, Universitat Kaiser-slautern.
• 36: Marc van Kreveld , René van Oostrum , Chandrajit Bajaj , Valerio Pascucci , Dan Schikore, Contour trees and small seed sets for isosurface traversal, Proceedings of the thirteenth annual symposium on Computational geometry, p.212-220, June 04-06, 1997, Nice, France [doi>10.1145/262839.269238]
• 37: Witkin, A. P. 1983. Scale-space filtering. In International Joint Conference on Artificial Intelligence, 1019--1022.
• 38: Zoë Wood , Hugues Hoppe , Mathieu Desbrun , Peter Schröder, Removing excess topology from isosurfaces, ACM Transactions on Graphics (TOG), v.23 n.2, p.190-208, April 2004 [doi>10.1145/990002.990007]
• 39: Afra Joze Zomorodian , Herbert Edelsbrunner, Computing and comprehending topology: persistence and hierarchical morse complexes, 2001
• 40: Afra J. Zomorodian , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Topology for Computing (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
computational topology, critical points, filtering, isosurfaces