Abstract
In this paper, we address the problem of 3D inpainting using example-based methods for point cloud data. 3D inpainting is a process of filling holes or missing regions in the reconstructed 3D models. Typically inpainting methods addressed in the literature fill missing regions due to occlusions or inaccurate scanning of 3D models. However, we focus on scenarios involving naturally existing damaged models which are partly broken or incomplete in artifacts at cultural heritage sites. We propose two example-based inpainting techniques, namely region of interest (ROI)-based and patch-based methods, to inpaint the missing regions of the damaged model. For both the methods, we represent the 3D model as a set of Riemannian manifolds in Euclidean space, to capture the inherent geometry using metric tensor and Christoffel symbols as geometric features and decompose into basic shape (such as spherical, conical and cylindrical) regions using decomposition algorithm derived from supervised learning. In ROI-based method, instead of using single similar example for inpainting, we select the most relevant regions that best-fit the missing region from the set of basic shape regions derived from n similar examples. And in patch-based method, we not only select the most relevant regions but cluster the regions into a set of patches. The best corresponding patches that match the missing region to be inpainted are considered to be the most relevant best-fit patches that cover the complete missing region. We demonstrate the performance of proposed inpainting methods on cultural heritage artifacts with varying complexities and sizes for both synthetically generated holes and real missing regions.
Similar content being viewed by others
Notes
Hausdorff distance [13] between two 3D models X and Y is the maximum function between a set of points in X to the nearest point in the Y:
\(d_{\mathrm H}(X,Y) = \max \{\,\sup _{x \in X} \inf _{y \in Y} d(x,y),\, \sup _{y \in Y} \inf _{x \in X} d(x,y)\,\} \)
References
Amberg, B., Romdhani, S., Vetter, T.: Optimal step nonrigid ICP algorithms for surface registration. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–8 (2007)
Barthe, L., Kobbelt, L.: Subdivision scheme tuning around extraordinary vertices. Comput. Aided Geom. Des. 21(6), 561–583 (2004)
Bendels, G.H., Schnabel, R., Klein, R.: Detail-preserving surface inpainting. In: International Conference on Virtual Reality, Archaeology and Intelligent Cultural Heritage, pp. 41–48. Eurographics Association (2005)
Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. In: SIGGRAPH, pp. 417–424. ACM Press/Addison-Wesley Publishing Co. (2000)
Bischoff, S., Pavic, D., Kobbelt, L.: Automatic restoration of polygon models. ACM Trans. Graph. 24(4), 1332–1352 (2005)
Boy, S., Guennebaud, G., Schlick, C.: Least squares subdivision surfaces. Comput. Graph. Forum 29(7), 2021–2028 (2010)
Caselles, V., Haro, G., Sapiro, G., Verdera, J.: On geometric variational models for inpainting surface holes. Comput. Vis. Image Underst. 111(3), 351–373 (2008)
Chang, C.C., Lin, C.J.: Libsvm: A library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(3), 27:1–27:27 (2011)
Clarenz, U., Diewald, U., Dziuk, G., Rumpf, M., Rusu, R.: A finite element method for surface restoration with smooth boundary conditions. Comput. Aided Geom. Des. 21(5), 427–445 (2004)
Corsini, M., Cignoni, P., Scopigno, R.: Efficient and flexible sampling with blue noise properties of triangular meshes. IEEE Trans. Vis. Comput. Graph. 18(6), 914–924 (2012)
Criminisi, A., Perez, P., Toyama, K.: Region filling and object removal by exemplar-based image inpainting. Trans. Image Proc. 13(9), 1200–1212 (2004)
Davis, J., Marschner, S.R., Garr, M., Levoy, M.: Filling holes in complex surfaces using volumetric diffusion. In: International Symposium on 3D Data Processing Visualization and Transmission. Proceedings, pp. 428–441. IEEE (2002)
Distance, H.: https://en.wikipedia.org/wiki/Hausdorff_distance. Accessed 10 Nov 2016
Gal, R., Shamir, A., Hassner, T., Pauly, M., Cohen-Or, D.: Surface reconstruction using local shape priors. In: Eurographics Symposium on Geometry Processing (SGP), pp. 253–262. Eurographics Association (2007)
Ganihar, S.A., Joshi, S., Setty, S., Mudenagudi, U.: Metric tensor and christoffel symbols based 3D object categorization. In: Computer Vision-ACCV Workshops, pp. 138–151. Springer, Berlin (2014)
Ganihar, S.A., Joshi, S., Shetty, S., Mudenagudi, U.: Metric tensor and christoffel symbols based 3D object categorization. In: ACM SIGGRAPH Posters, pp. 38:1–38:1 (2014)
Guo, X., Xiao, J., Wang, Y.: A survey on algorithms of hole filling in 3D surface reconstruction. Vis. Comput. 1–11 (2016)
Guo, Y., Bennamoun, M., Sohel, F., Lu, M., Wan, J., Kwok, N.M.: A comprehensive performance evaluation of 3D local feature descriptors. Int. J. Comput. Vis. 116(1), 66–89 (2016)
Harary, G., Tal, A., Grinspun, E.: Context-based coherent surface completion. ACM Trans. Graph. 33(1), 5:1–5:12 (2014)
Harary, G., Tal, A., Grinspun, E.: Feature-preserving surface completion using four points. Comput. Graph. Forum 33(5), 45–54 (2014)
Jost, J.: Riemannian geometry and geometric analysis. In: Springer Universitat Texts, 6 edn. Springer, Berlin (2011)
Ju, T.: Robust repair of polygonal models. ACM Trans. Graph. 23(3), 888–895 (2004)
Ju, T.: Fixing geometric errors on polygonal models: a survey. J. Comput. Sci. Technol. 24(1), 19–29 (2009)
Kazhdan, M., Bolitho, M., Hoppe, H.: Poisson surface reconstruction. In: Eurographics Symposium on Geometry Processing (SGP), pp. 61–70. Eurographics Association (2006)
Kinect: http://www.xbox.com/en-IN/Kinect/ (2010). Accessed 10 Nov 2016
Kraevoy, V., Sheffer, A.: Template-based mesh completion. In: Eurographics Symposium on Geometry Processing (SGP). Eurographics Association (2005)
Liepa, P.: Filling holes in meshes. In: Eurographics Symposium on Geometry Processing (SGP), pp. 200–205. Eurographics Association (2003)
Oliveira, M.M., Bowen, B., McKenna, R., sung Chang, Y.: Fast digital image inpainting. In: International Conference on Visualization, Imaging and Image Processing (VIIP), pp. 261–266. ACTA Press (2001)
Pauly, M., Mitra, N.J., Giesen, J., Gross, M.H., Guibas, L.J.: Example-based 3D scan completion. In: Eurographics Symposium on Geometry Processing (SGP), pp. 23–32. Eurographics Association (2005)
Pernot, J.P., Moraru, G., Véron, P.: Filling holes in meshes using a mechanical model to simulate the curvature variation minimization. Comput. Graph. 30(6), 892–902 (2006)
Podolak, J., Rusinkiewicz, S.: Atomic volumes for mesh completion. In: Eurographics Symposium on Geometry Processing (SGP). Eurographics Association (2005)
Rusinkiewicz, S., Levoy, M.: Efficient variants of the ICP algorithm. In: 3D Digital Imaging and Modeling, pp. 145–152 (2001)
Sahay, P., Rajagopalan, A.: Geometric inpainting of 3D structures. In: IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 1–7 (2015)
Sahay, P., Rajagopalan, A.N.: Harnessing self-similarity for reconstruction of large missing regions in 3D models. In: International Conference on Pattern Recognition (ICPR), pp. 101–104. IEEE (2012)
Schnabel, R., Wahl, R., Klein, R.: Efficient ransac for point-cloud shape detection. Comput. Graph. Forum 26(2), 214–226 (2007)
Sharf, A., Alexa, M., Cohen-Or, D.: Context-based surface completion. ACM Trans. Graph. TOG 23(3), 878–887 (2004)
Sumner, R.W., Popović, J.: Deformation transfer for triangle meshes. ACM Trans. Graph. 23(3), 399–405 (2004)
Telea, A.: An image inpainting technique based on the fast marching method. J. Graph. GPU Game Tools 9, 23–34 (2004)
Verdera, J., Caselles, V., Bertalmio, M., Sapiro, G.: Inpainting surface holes. Int. Conf. Image Process. ICIP 2, 903–906 (2003)
Wang, J., Oliveira, M.M.: A hole-filling strategy for reconstruction of smooth surfaces in range images. In: SIBGRAPI, pp. 11–18. IEEE Computer Society (2003)
Wu, X.J., Wang, M.Y., Han, B.: An automatic hole-filling algorithm for polygon meshes. Comput. Aided Des. Appl. 5, 889–899 (2008)
Zhao, W., Gao, S., Lin, H.: A robust hole-filling algorithm for triangular mesh. Vis. Comput. 23(12), 987–997 (2007)
Acknowledgements
This research work is partly supported by the Indian Digital Heritage project (NRDMS/11/2013/013/ Phase-III) under the Digital Hampi initiative of the Department of Science and Technology, Government of India.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Setty, S., Mudenagudi, U. Example-based 3D inpainting of point clouds using metric tensor and Christoffel symbols. Machine Vision and Applications 29, 329–343 (2018). https://doi.org/10.1007/s00138-017-0886-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00138-017-0886-7