Shape spaces via medial axis transforms for segmentation of complex geometry in 3D voxel data

Jochen Abhau; Oswin Aichholzer; Sebastian Colutto; Bernhard Kornberger; Otmar Scherzer

doi:10.3934/ipi.2013.7.1

Article Contents

2013, Volume 7, Issue 1: 1-25. Doi: 10.3934/ipi.2013.7.1

This issue Previous Article Next Article The attenuated magnetic ray transform on surfaces

Shape spaces via medial axis transforms for segmentation of complex geometry in 3D voxel data

1.
Computational Science Center, University of Vienna, Nordbergstraße 15, A-1090 Wien, and Institute of Mathematics, University of Innsbruck, Technikerstraße 21a, A-6020 Innsbruck
2.
Institute for Software Technology, Graz University of Technology
3.
Institute of Mathematics, University of Innsbruck, Technikerstraße 21a, A-6020 Innsbruck, and Department of Digitization and Digital Preservation, University of Innsbruck, Innrain 52, A-6020 Innsbruck
4.
Geom e.U. Softwareentwicklung, Brockmanngasse 15, A-8010 Graz
5.
Radon Institute of Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Straße 69, A-4040 Linz

Received: July 2011

Revised: May 2012

Published: February 2013

Abstract / Introduction Related Papers Cited by

Abstract

In this paper we construct a shape space of medial ball representations from given shape training data using methods of Computational Geometry and Statistics. The ultimate goal is to employ the shape space as prior information in supervised segmentation algorithms for complex geometries in 3D voxel data. For this purpose, a novel representation of the shape space (i.e., medial ball representation) is worked out and its implications on the whole segmentation pipeline are studied. Such algorithms have wide applications for industrial processes and medical imaging, when data are recorded under varying illumination conditions, are corrupted with high noise or are occluded.

Keywords:

Mathematics Subject Classification: 65D18, 65F22, 68U10, 94A08.

Citation:

Related Papers

Cited by

References

[1]	Medical image computing and computer assisted intervention. Available from: http://www.miccai2009.org.
[2]	J. Abhau, W. Hinterberger and O. Scherzer, Segmenting surfaces of arbitrary topology: A two-step approach, in "Ultrasonic Imaging and Signal Processing," Proceedings of SPIE - Volume 6437, 2007.
[3]	R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications," Prentice Hall, Inc., Englewood Cliffs, NJ, 1993.
[4]	O. Aichholzer, F. Aurenhammer, T. Hackl, M. Kornberger, B. M. Peternell and H. Pottmann, Approximating boundary-triangulated objects with balls, in "Proc. 23rd European Workshop on Computational Geometry," Graz, (2007), 130-133.
[5]	O. Aichholzer, F. Aurenhammer and B. Kornberger, Stable piecewise-linear approximations of 3d medial axes, Manuscript.
[6]	O. Aichholzer, F. Aurenhammer, B. Kornberger, S. Plantinga, G. Rote, A. Sturm and G. Vegter, Recovering structure from $r$-sampled objects, in "Proc. Eurographics Symposium on Geometry Processing," 28, Berlin, (2009), 1349-1360.
[7]	N. Amenta and M. Bern, Surface reconstruction by Voronoi filtering, Discrete & Computational Geometry, 22 (1999), 481-504.doi: 10.1007/PL00009475.
[8]	N. Amenta and R. Kolluri, Accurate and efficient unions of balls, In "Proc. 16th Ann. Symp. Computational Geometry" (Hong Kong, 2000), ACM, New York, (2000), 119-128.doi: 10.1145/336154.336193.
[9]	H. Blum and R. N. Nagel, Shape description using weighted symmetric axis features, Pattern Recognition, 10 (1978), 167-180.
[10]	J.-D. Boissonnat and M. Teillaud, eds., "Effective Computational Geometry for Curves and Surfaces," Mathematics and Visualization, Springer-Verlag, Berlin, 2007.
[11]	F. L. Bookstein, "Morphometric tools for landmark data: Geometry and biology," Cambridge University Press, Cambridge, 1997.
[12]	X. Bresson, P. Vandergheynst and J. P. Thiran, A variational model for object segmentation using boundary information and shape prior driven by the mumford-shah functional, Int. J. Comput. Vision, 28 (2006), 145-162.
[13]	T. Chan and L. Vese, Active contours without edges, IEEE Trans. Image Process., 10 (2001), 266-277.
[14]	G. Charpiat, O. Faugeras and R. Keriven, Approximations of shape metrics and application to shape warping and empirical shape statistics, Foundations of Computational Mathematics, 5 (2004), 1-58.doi: 10.1007/s10208-003-0094-x.
[15]	Q. Chen, Z. M. Zhou, M. Tang, P. A. Heng and D. S. Xia, Shape statistics variational approach for the outer contour segmentation of left ventricle mr images, IEEE Trans. Inf. Technol. Biomed., 10 (2006), 588-597.
[16]	Y. Chen, H. D. Tagare, S. Thiruvenkadam, F. Huang, D. Wilson, K. S. Gopinath, R. W. Briggs and E. A. Geiser, Using prior shapes in geometric active contours in a variational framework, Int. J. Comput. Vision, 50 (2002), 315-328.
[17]	S. Colutto, F. Fr¨¹hauf, M Fuchs and O. Scherzer, The CMA-ES on Riemannian manifolds to reconstruct shapes in 3D voxel images, IEEE Transactions on Evolutionary Computation, 14 (2010), 227-245.
[18]	D. Cremers, T. Kohlberger and C. Schnoerr, Shape statistics in kernel space for variational image segmentation, Pattern Recognition, 36 (2003), 1929-1943.
[19]	D. Cremers, F. Tischh0Š1user, J. Weickert and Ch. Schn0‹2rr, Diffusion snakes: Introducing statistical shape knowledge into the Mumford-Shah functional, Int. J. Comput. Vision, 50 (2002), 295-313.
[20]	I. L. Dryden and K. V. Mardia, "Statistical Shape Analysis," Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 1998.
[21]	H. Edelsbrunner, Deformable smooth surface design, Discrete Comp. Geom., 21 (1999), 87-115.doi: 10.1007/PL00009412.
[22]	H. Edelsbrunner and E. P. M¨¹cke, Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms, in "Proceedings of the Fourth Annual Symposium on Computational Geometry" (Urbana, IL, 1988), ACM, New York, (1988), 118-133.doi: 10.1145/73393.73406.
[23]	W. Fang and K. L. Chan, Incorporating shape prior into geodesic active contours for detecting partially occluded object, Pattern Recognition, 40 (2007), 2163-2172.
[24]	P. T. Fletcher, S. Joshi, C. Ju and S. M. Pizer, Principal geodesic analysis for the study of nonliner statistics of shape, IEEE Trans. Med. Imag., 23 (2004), 995-1005.
[25]	D. S. Fritsch, S. M. Pizer, L. Yu, V. Johnson and E. L. Chaney, Localization and segmentation of medical image objects using deformable shape loci, Lecture Notes in Computer Science, 1230 (1997), 127-140, 1997.
[26]	M. Fuchs and S. Gerber, Variational shape detection in microscope images based on joint shape and image feature statistics, in "CVPR Workshops 2008. IEEE Computer Society Conference on," (2008), 1-8.
[27]	M. Gastaud, M. Barlaut and G. Aubert, Combining shape prior and statistical features for active contour segmentation, IEEE Trans. Circuits and Systems, 14 (2004), 726-734.
[28]	N. Hansen, S. D. M¨¹ller and P. Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evolutionary Computation, 11 (2003), 1-18.
[29]	K. Jafari-Khouzani, K. Elisevich, S. Patel and H. Soltanian-Zadeh, Dataset of magnetic resonance images of nonepileptic subjects and temporal lobe epilepsy patients for validation of hippocampal segmentation techniques, Neuroinformatics, (2011).
[30]	S. Joshi, S. Pizer, P. T. Fletcher, A. Thall and G. Tracton, Multi-scale 3-d deformable model segmentation based on medical description, in "Proc. International Conference on Information Processing in Medical Imaging (IPMI)," (2001), 64-77.
[31]	T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman and A. Y. Wu, An efficient k-means clustering algorithm: Analysis and implementation, IEEE Trans. Pattern Anal. Mach. Intell., 24 (2002), 881-892.
[32]	M. Kass, A. Witkin and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vision, 1 (1987), 321-331.
[33]	D. G. Kendall, Shape manifolds, Procrustean metrics, and complex projective spaces, Bull. Lond. Math. Soc., 16 (1984), 81-121.doi: 10.1112/blms/16.2.81.
[34]	J. T. Kent, K. V. Mardia and C. C. Taylor, Matching problems for unlabelled configurations, Bioinf. Images Wavelets, (2004), 33-36.
[35]	J. T. Kent, K. V. Mardia and C. C. Taylor, Matching unlabelled configurations and protein bioinformatics, to appear.
[36]	S. Kern and N. Hansen, Evaluating the cma evolution strategy on multimodal test functions, in "Eigth International Conference on Parallel Problem Solving from Nature PPSN VIII," 3242, Springer, (2004), 282-291.
[37]	N. Kruithof and G. Vegter, Meshing skin surfaces with certified topology, Comput. Geom., 36 (2007), 166-182.doi: 10.1016/j.comgeo.2006.01.003.
[38]	M. E. Leventon, W. E. L. Grimson and O. Faugeras, Statistical shape influence in geodesic active contours, in "Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR-00)," Los Alamitos, (2000), 316-323.
[39]	K. V. Mardia, J. T. Kent and J. M. Bibby, "Multivariate Analysis," Academic Press, London, 1977.
[40]	G. McLachlan and T. Krishnan, "The EM Algorithm and Extensions," Second edition, Wiley Series in Probability and Statistics, Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2008.doi: 10.1002/9780470191613.
[41]	D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685.doi: 10.1002/cpa.3160420503.
[42]	S. M. Pizer, P. T. Fletcher, S. Joshi, A. Thall, J. Z. Chen, Y. Fridman, D. S. Fritsch, A. G. Gash, J. M. Glotzer, M. R. Jiroutek, C. Lu, K. E. Muller, G. Tracton, P. Yushkevich and E. L. Chaney, Deformable m-reps for 3d medical image segmentation, Int. J. Comput. Vision, 55 (2003), 85-106.
[43]	S. M. Pizer, A. L. Thall and D. T. Chen, M-reps: A new object representation for graphics, Technical Report TR99-030, Department of Computer Science, University of North Carolina, Chapel Hill, 1999.
[44]	M. A. Puso and T. A. Laursen, A 3-d contact smoothing algorithm method using gregory patches, Numer. Meth. in Engineering, (2002).
[45]	M. Rousson and N. Paragios, Shape priors for level set representations, in "European Conference in Computer Vision (ECCV)," (2002), 78-93.
[46]	M. Rousson and N. Paragios, Prior knowledge, level set representations & visual grouping, Int. J. Comput. Vision, 76 (2007), 231-243.
[47]	K. Siddiqi and S. M., Pizer, eds., "Medial representations. Mathematics, Algorithms and Applications," Computational Imaging and Vision, 37, Springer, New York, 2008.doi: 10.1007/978-1-4020-8658-8.
[48]	C. G. Small, "The Statistical Theory of Shape," Springer Series in Statistics, Springer-Verlag, New York, 1996.doi: 10.1007/978-1-4612-4032-7.
[49]	S. Suri, Bipartite matching and the hungarian method, 2006. Available from: http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf.
[50]	A. Tsai, A. Yezzi, C. Tempany, D. Tucker, A. Fan, W. E. L. Grimson and A. Willsky, A shape-based approach to the segmentation of medical imagery using level sets, IEEE Trans. Med. Imag., 22 (2003), 137-154.
[51]	A. Witkin, M. Kass and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vision, 1 (1987), 321-331.
[52]	P. Yushkevich, P. T. Fletcher, S. C. Joshi, A. Thall and S. M. Pizer, Continuous medial representations for geometric object modeling in 2D and 3D, Image and Vision Computing, 21 (2003), 17-27.
[53]	P. A. Yushkevich, J. Piven, C. Hazlett, H.and G. Smith, R. Ho, S., J. C. Gee and G. Gerig, User-guided 3D active contour segmentation of anatomical structures: Significantly improved efficiency and reliability, Neuroimage, 31 (2006), 1116-1128.