Smooth normals with blobs for surfaces from 3D binary images
Keywords:
Surface Rendering, Boundary Tracking, Smooth Normals, Implicit Surfaces, Spherically Symmetric Basis Functions, Generalized Kaiser-Bessel Functions, Linear Combination of BlobsAbstract
One way of representing a real object on a computer screen is by rendering a polygonal mesh, extracted from the discretized version of the object. This discretization is typically a collection of abutting small cubic voxels. In this work, we present a method that generates better renderings of rectangular meshes (with desirable mathematical properties but blocky renderings) created by a boundary detection algorithm. We achieve this by assigning appropriate normals to the vertices of the mesh and taking advantage of how standard computer graphics methods render images. We assign the normals by evaluating, at the vertices of the mesh, the gradient of a linear combination of Kaiser-Bessel-based basis functions that are spherically symmetric. By using signal processing principles, we select the parameters of these functions and assign normals that yield renderings that show smoother surfaces than the renderings produced by the original voxel based models, without modifying the mesh geometry.
References
Ehud Artzy, Gideon Frieder, and Gabor T. Herman. The theory, design, implementation and evaluation of a three-dimensional surface detection algorithm. Computer Graphics and Image Processing, 15(1):1-24, 1981.
Matthew Berger, Andrea Tagliasacchi, Lee M. Seversky, Pierre Alliez, Joshua A. Levine, Andrei Sharf, and Claudio T. Silva. State of the art in surface reconstruction from point clouds. In Sylvain Lefebvre and Michela Spagnuolo, editors, Eurographics 2014 - State of the Art Reports, pages 161-185, Strasbourg, France, April 2014. The Eurographics Association.
Jim F. Blinn. A generalization of algebraic surface drawing. ACM Transactions on Graphics, 1:235-256, 1982.
Achille J.-P. Braquelaire and Arnault Pousset. Euclidean nets: An automatic and reversible geometric smoothing of discrete 3D object boundaries. In Gunilla Borgefors, Ingela Nyström, and Gabriella Sanniti di Baja, editors, Discrete Geometry for Computer Imagery, volume 1953 of Lecture Notes in Computer Science, pages 198-209. Springer, 2000.
Bruno M. Carvalho and Gabor T. Herman. Helical CT reconstruction from wide cone-beam angle data using ART. In XVI Brazilian Symposium on Computer Graphics and Image Processing, pages 363-370, 2003.
Bruno M. Carvalho and Gabor T. Herman. Low-dose, large-angled cone-beam helical $C T$ data reconstruction using algebraic reconstruction techniques. Image and Vision Computing, 25(1):78-94, 2007.
Thomas J. Cashman. Beyond Catmull-Clark? A survey of advances in subdivision surface methods. Computer Graphics Forum, 31(1):42-61, 2012.
Lih-Shyang Chen, Gabor T. Herman, R. Anthony Reynolds, and Jayaram K. Udupa. Surface shading in the cuberille environment. IEEE Computer Graphics and Applications, 5(12):33-43, 1985.
David Coeurjolly and Jacques-Olivier Lachaud. DGTAL: Digital Geometry tools and algorithms library, October 2017. http://dgtal.org.
David Coeurjolly, Jacques-Olivier Lachaud, and Jérémy Levallois. Multigrid convergent principal curvature estimators in digital geometry. Computer Vision and Image Understanding, 129:27-41, 2014.
Frédéric Flin, Jean-Bruno Brzoska, David Coeurjolly, Romeu André Pieritz, Bernard Lesaffre, Cécile Coléou, Pascal Lamboley, Olivier Teytaud, Gérard L. Vignoles, and Jean-François Delesse. Adaptive estimation of normals and surface area for discrete 3-D objects: Application to snow binary data from X-ray tomography. IEEE Transactions on Image Processing, 14(5):585-596, 2005.
James D. Foley, Andries Van Dam, Steven K. Feiner, and John F. Hughes. Computer Graphics: Principles and Practice. Addison-Wesley Co., New York, 2nd edition, 1996.
Sébastien Fourey and Rémy Malgouyres. Normals estimation for digital surfaces based on convolutions. Computer Graphics, 33:2-10, 2009.
Edgar Gardun̄o and Gabor T. Herman. Optimization of basis functions for both reconstruction and visualization. Discrete Applied Mathematics, 139:95-111, 2004.
Edgar Gardun̄o, Gabor T. Herman, and H. Katz. Boundary tracking in SD binary images to produce rhombic faces for a dodecahedral model. IEEE Transactions on Medical Imaging, 17:1097-1100, 1998.
Henri Gouraud. Continuous shading of curved surfaces. IEEE Transactions on Computers, C-20(6):623-629, 1971.
Gabor T. Herman. Fundamentals of Computerized Tomography: Image Reconstruction from Projections. Advances in Pattern Recognition. Springer, New York, 2nd. edition, 2009.
Di-hui Hong, Gang-min Ning, Ting Zhao, Mu Zhang, and Xiaoxiang Zheng. Method of normal estimation based on approximation for visualization. Journal of Electronic Imaging, 12(3):470-477, 2003.
Tian Jianlei, Liu Xumin, and Guan Yong. Anisotropic smoothing algorithm for triangular mesh models. In International Forum on Computer Science-Technology and Applications, IFCSTA'09, volume 1, pages 126-130, December 2009.
James F. Kaiser and Ronald W. Schafer. On the use of the I0-sinh window for spectrum analysis. IEEE Transactions on Acoustics, Speech and Signal Processing, 28(1):105-107, 1980.
Bertrand Kerautret and Achille Braquelaire. A statistical approach for geometric smoothing of discrete surfaces. In Eric Andres, Guillaume Damiand, and Pascal Lienhardt, editors, Discrete Geometry for Computer Imagery, volume 3429 of Lecture Notes in Computer Science, pages 404-413. Springer, 2005.
Reinhard Klette and Azriel Rosenfeld. Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, 2004.
Tat Yung Kong and Azriel Rosenfeld. Digital topology: Introduction and survey. Computer Vision, Graphics, and Image Processing, 48(3):357-393, 1989.
Jacques-Olivier Lachaud, David Coeurjolly, and Jérémy Levallois. Robust and convergent curvature and normal estimators with digital integral invariants. In Laurent Najman and Pascal Romon, editors, Modern Approaches to Discrete Curvature, volume 2184 of Lecture Notes in Computer Science, pages 293-348. Springer, 2017.
Samuli Laine and Tero Karras. Efficient sparse voxel octrees. IEEE Transactions on Visualization and Computer Graphics, 17(8):1048-1059, 2011.
Alexandre Lenoir, Rémy Malgouyres, and Marinette Revenu. Fast computation of the normal vector field of the surface of a s-D discrete object. In Serge Miguet, Annick Montanvert, and Stéphane Ubéda, editors, Discrete Geometry for Computer Imagery, pages 101-112. Springer, 1996.
Robert M. Lewitt. Multidimensional digital image representations using generalized Kaiser-Bessel window functions. Journal of the Optical Society of America A, 7:1834-1846, 1990.
Robert M. Lewitt. Alternatives to voxels for image representation in iterative reconstruction algorithms. Physics in Medicine & Biology, 37:705-716, 1992.
Li-Min Luo and Jean-Louis Coatrieux. Surface normal for 3D object display in cuberille environment. In Proceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society, volume 1, pages 420-421, 1988.
Roberto Marabini, Gabor T. Herman, and José María Carazo. SD reconstruction in electron microscopy using ART with smooth spherically symmetric volume elements (blobs). Ultramicroscopy, 72:53-65, 1998.
Samuel Matej and Robert M. Lewitt. Efficient SD grids for image-reconstruction using spherically-symmetrical volume elements. IEEE Transactions on Nuclear Science, 42:1361-1370, 1995.
Samuel Matej and Robert M. Lewitt. Practical considerations for S-D image reconstruction using spherically symmetric volume elements. IEEE Transactions on Medical Imaging, 15:68-78, 1996.
Torsten Möller, Raghu Machiraju, Klaus Mueller, and Roni Yagel. Evaluation and design of filters using a Taylor series expansion. IEEE Transactions on Visualization and Computer Graphics, 3(3):184-199, 1997.
Shigeru Muraki. Volumetric shape description of range data using "Blobby Model". Computer Graphics, 25:227-235, 1991.
Shigeru Muraki. Multiscale volume representation by a DoG wavelet. IEEE Transactions on Visualization and Computer Graphics, 1:109-116, 1995.
Hitoshi Nishimura, Makoto Hirai, Toshiyuki Kawai, Toru Kawata, Isao Shirakawa, and Koichi Omura. Object modeling by distribution function and a method of image generation. Transactions of the Institute of Electronics and Communications Engineers of Japan, J68-D(4):718-725, 1985.
Pavol Novotny, Leonid I. Dimitrov, and Milos Sramek. Enhanced voxelization and representation of objects with sharp details in truncated distance fields. IEEE Transactions on Visualization and Computer Graphics, 16(3):484-498, 2010.
Laurent Papier. Polyédrisation et visualisation d'objets discrets tridimensionnels. PhD thesis, Université Louis Pasteur, Strasbourg, France, 1999.
Bui Tuong Phong. Illumination for computer generated pictures. Communications of the ACM, 18:311-317, 1975.
Alexander Reshetov, Alexei Soupikov, and William R. Mark. Consistent normal interpolation. ACM Transactions on Graphics, 29(6):142:1-142:8, 2010.
Stefan Röttger. The volume library, 2006. http://lgdv.cs.fau.de/External/vollib.
Carlos Oscar Sánchez Sorzano, Roberto Marabini, Javier A. Velázquez-Muriel, José Roman Bilbao-Castro, Sjors H. W. Scheres, José María Carazo, and Alberto Pascual-Montano. XMIPP: a new generation of an open-source image processing package for electron microscopy. Journal of Structural Biology, 148(2):194-204, 2004.
Milos Sramek and Arie E. Kaufman. Alias-free voxelization of geometric objects.
IEEE Transactions on Visualization and Computer Graphics, 5:251-267, 1999.
Pierre Tellier and Isabelle Debled-Rennesson. SD discrete normal vectors. In Gilles Bertrand, Michel Couprie, and Laurent Perroton, editors, Proceedings of the 8th International Conference on Discrete Geometry for Computer Imagery, volume 1568 of DCGI'99 in Lecture Notes in Computer Science, pages 447-458, London, UK, 1999. Springer.
Grit Thürmer. Smoothing normal vectors on discrete surfaces while preserving slope discontinuities. Computer Graphics Forum, 20(2):103-114, 2001.
Greg Turk and James F. O'brien. Modelling with implicit surfaces that interpolate.
ACM Transactions on Graphics, 21(4):855-873, 2002.
Brian Wyvill and Geoff Wyvill. Field functions for implicit surfaces. The Visual Computer, 5(1-2):75-82, 1989.
Geoff Wyvill, Craig McPheeters, and Brian Wyvill. Data structure for soft objects. The Visual Computer, 2:227-234, 1986.
Roni Yagel, Daniel Cohen, and Arie E. Kaufman. Normal estimation in SD discrete space. The Visual Computer, 8:278-291, 1991.
