Topological Equivalence between a 3D Object and the Reconstruction of Its Digital Image
|
Digitization is not as easy as it looks. If one digitizes a 3D object even with a dense sampling grid, the reconstructed digital object may have topological distortions and, in general, there exists no upper bound for the Hausdorff distance. This explains why so far no algorithm has been known which guarantees topology preservation. However, as we will show, it is possible to repair the obtained digital image in a locally bounded way so that it is homeomorphic and close to the 3D object. The resulting digital object is always well-composed, which has nice implications for a lot of image analysis problems. Moreover, we will show that the surface of the original object is homeomorphic to the result of the marching cubes algorithm. This is really surprising since it means that the well-known topological problems of the marching cubes reconstruction simply do not occur for digital images of r-regular objects. Based on the trilinear interpolation, we also construct a smooth isosurface from the digital image that has the same topology as the original surface. Finally, we give a surprisingly simple topology preserving reconstruction method by using overlapping balls instead of cubical voxels. This is the first approach of digitizing 3D objects which guarantees topology preservation and gives an upper bound for the geometric distortion. Since the output can be chosen as a pure voxel presentation, a union of balls, a reconstruction by trilinear interpolation, a smooth isosurface, or the piecewise linear marching cubes surface, the results are directly applicable to a huge class of image analysis algorithms. Moreover, we show how one can efficiently estimate the volume and the surface area of 3D objects by looking at their digitizations. Measuring volume and surface area of digital objects are important problems in 3D image analysis. Good estimators should be multigrid convergent, i.e., the error goes to zero with increasing sampling density. We will show that every presented reconstruction method can be used for volume estimation and we will give a solution for the much more difficult problem of multigrid-convergent surface area estimation. Our solution is based on simple counting of voxels and we are the first to be able to give absolute bounds for the surface area.
[1] 126 T. Pavlidis, Algorithms for Graphics and Image Processing. Computer Science Press. 1982.
[2] J. Serra, Image Analysis and Mathematical Morphology. Academic Press, 1982.
[3] L.J. Latecki, C. Conrad, and A. Gross, “Preserving Topology by a Digitization Process,” J. Math. Imaging and Vision, vol. 8, pp. 131-159, 1998.
[4] M. Tajine and C. Ronse, “Topological Properties of Hausdorff Discretization, and Comparison to Other Discretization Schemes,” Theoretical Computer Science, vol. 283, no. 1, pp. 243-268, 2002.
[5] U. Köthe and P. Stelldinger, “Shape Preserving Digitization of Ideal and Blurred Binary Images,” Proc. Discrete Geometry for Computer Imagery, pp. 82-91, Nov. 2003.
[6] P. Stelldinger and U. Köthe, “Shape Preservation during Digitization: Tight Bounds Based on the Morphing Distance,” Proc. Symp. Deutsche Arbeitsgemeinschaft für Mustererkennung, pp.108-115, Sept. 2003.
[7] P. Stelldinger and U. Köthe, “Towards a General Sampling Theory for Shape Preservation,” Image and Vision Computing J., special issue on discrete geometry for computer imagery, vol. 23, no. 2, pp. 237-248, 2005.
[8] P. Stelldinger and L.J. Latecki, “3D Object Digitization: Topology Preserving Reconstruction,” Proc. IEEE Int'l Conf. Image Analysis, 2006.
[9] P. Stelldinger and L.J. Latecki, “3D Object Digitization: Majority Interpolation and Marching Cubes,” Proc. IEEE Int'l Conf. Image Analysis, 2006.
[10] P. Stelldinger and L.J. Latecki, “3D Object Digitization: Volume and Surface Area Estimation,” Proc. IEEE Int'l Conf. Image Analysis, 2006.
[11] T. Kong and A. Rosenfeld, “If We Use 4- or 8-Connectedness for Both the Objects and the Background, the Euler Characteristics Is Not Locally Computable,” Pattern Recognition Letters, vol. 11, no. 4, pp. 231-232, 1990.
[12] D. Marr, Vision. Freeman, 1983.
[13] L.J. Latecki, “3D Well-Composed Pictures,” Graphical Models and Image Processing, vol. 59, no. 3, pp. 164-172, 1997.
[14] W.E. Lorensen and H.E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,” SIGGRAPH '87: Proc. 14th Ann. Conf. Computer Graphics and Interactive Techniques, pp. 163-169, 1987.
[15] M.J. Dürst, “Letters: Additional Reference to ‘Marching Cubes’,” Proc. SIGGRAPH Computer Graphics, vol. 22, no. 2, p. 243, 1988.
[16] G.M. Nielson and B. Hamann, “The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes,” Proc. Second IEEE Conf. Visualization, pp. 83-91, Oct. 1991.
[17] R. Klette and A. Rosenfeld, Digital Geometry. Morgan Kaufman, 2004.
[18] A. Lopes and K. Brodlie, “Improving the Robustness and Accuracy of the Marching Cubes Algorithm for Isosurfacing,” IEEE Trans. Visualization and Computer Graphics, vol. 9, no. 1, pp.16-27, Jan.-Mar. 2003.
[19] M. Siqueira, L.J. Latecki, and J. Gallier, “Making 3D Binary Digital Images Well-Composed,” Proc. IS&T/SPIE Conf. Vision Geometry XIII, pp. 150-163, Jan. 2005.
[20] A. Rosenfeld, T. Kong, and A. Nakamura, “Topology-Preserving Deformations of Two-Valued Digital Pictures,” Graphical Models and Image Processing, vol. 60, no. 1, pp. 24-34, 1998.
[21] L. Westover, “Interactive Volume Rendering,” Proc. Chapel Hill Workshop Volume Visualization, 1989.
[22] E. Chernyaev, “Marching Cubes 33: Construction of Topologically Correct Isosurfaces,” Technical Report CN/95-17, Conseil Européen pour la Recherche Nucléaire (CERN), 1995.
[23] J. Wilhelms and A.V. Gelder, “Topological Considerations in Isosurface Generation,” Computer Graphics, vol. 24, no. 5, pp. 79-86, 1990.
[24] L.A. Francis, “Dualing Cubes,” Proc. 37th Ann. Southeast Regional Conf., 1999.
[25] G.M. Nielson, “Dual Marching Cubes,” Proc. 15th IEEE Visualization, pp. 489-496, 2004.
[26] T. Lewiner, H. Lopes, A. Wilson, and G. Tavares, “Efficient Implementation of Marching Cubes Cases with Topological Guarantee,” J. Graphics Tools, vol. 8, pp. 1-15, 2003.
[27] N. Sukumar, “Meshless Methods and Partition of Unity Finite Elements,” Proc. Sixth Int'l ESAFORM Conf. Material Forming, pp.603-606, Apr. 2003.
[28] Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H-.P. Seidel, “Multi-Level Partition of Unity Implicits,” ACM Trans. Graphics, vol. 22, no. 3, pp. 463-470, 2003.
[29] C.S. Co, S.D. Porumbescu, and K.I. Joy, “Meshless Isosurface Generation from Multiblock Data,” Proc. Joint Eurographics-IEEE TCVG Symp. Visualization, pp. 273-282, May 2004.
[30] Y. Kenmochi and R. Klette, “Surface Area Estimation for Digitized Regular Solids,” Proc. IS&T/SPIE Conf. Vision Geometry IX, vol. 4117, pp. 100-111, Jan. 2001.
[31] R. Klette and J. Zunic, “Multigrid Convergence of Calculated Features in Image Analysis,” J. Math. Imaging and Vision, vol. 13, pp. 173-191, 2000.
[32] F. Sloboda and B. Zatko, “On Approximation of Jordan Surfaces in 3D,” Proc. Discrete Geometry for Computer Imagery, pp. 365-388, 2001.
[33] D. Coeurjolly, F. Flin, O. Teytaud, and L. Tougne, “Multigrid Convergence and Surface Area Estimation,” Proc. Geometry, Morphology, and Computational Imaging, pp. 101-119, 2003.
[34] D. Bailey, “An Efficient Euclidean Distance Transform,” Proc. Combinatorial Image Analysis, pp. 394-408, 2004.
Index Terms:
r-regular, topology, digitization, 3D, marching cubes, trilinear interpolation, well-composed.
Citation:
Peer Stelldinger, Longin Jan Latecki, Marcelo Siqueira, "Topological Equivalence between a 3D Object and the Reconstruction of Its Digital Image," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 126-140, Jan. 2007, doi:10.1109/TPAMI.2007.21
PURCHASE ARTICLE: $19
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb