Context-based surface completion

ABSTRACT

Sampling complex, real-world geometry with range scanning devices almost always yields imperfect surface samplings. These "holes" in the surface are commonly filled with a smooth patch that conforms with the boundary. We introduce a context-based method: the characteristics of the given surface are analyzed, and the hole is iteratively filled by copying patches from valid regions of the given surface. In particular, the method needs to determine best matching patches, and then, fit imported patches by aligning them with the surrounding surface. The completion process works top down, where details refine intermediate coarser approximations. To align an imported patch with the existing surface, we apply a rigid transformation followed by an iterative closest point procedure with non-rigid transformations. The surface is essentially treated as a point set, and local implicit approximations aid in measuring the similarity between two point set patches. We demonstrate the method at several point-sampled surfaces, where the holes either result from imperfect sampling during range scanning or manual removal.

REFERENCES

• 1: ADOBE, 2002. Adobe photoshop 7.0.
• 2: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 3: Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995 [doi>10.1145/218380.218424]
• 4: Gill Barequet , Micha Sharir, Filling gaps in the boundary of a polyhedron, Computer Aided Geometric Design, v.12 n.2, p.207-229, March 1995 [doi>10.1016/0167-8396(94)00011-G]
• 5: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791]
• 6: Yang Chen , Gérard Medioni, Object modelling by registration of multiple range images, Image and Vision Computing, v.10 n.3, p.145-155, April 1992 [doi>10.1016/0262-8856(92)90066-C]
• 7: U. Clarenz , U. Diewald , G. Dziuk , M. Rumpf , R. Rusu, A finite element method for surface restoration with smooth boundary conditions, Computer Aided Geometric Design, v.21 n.5, p.427-445, May 2004 [doi>10.1016/j.cagd.2004.02.004]
• 8: CRIMINISI, A., PÉREZ, P., AND TOYAMA, K. 2003. Object removal by exemplar-based inpainting. In 2003 Conference on Computer Vision and Pattern Recognition (CVPR 2003), 721--728.
• 9: 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]
• 10: DAVIS, J., MARSCHNER, S. R., GARR, M., AND LEVOY, M. 2002. Filling holes in complex surfaces using volumetric diffusion. In Proceedings of the 1st International Symposium on 3D Data Processing Visualization and Transmission (3DPVT-02), IEEE Computer Society, Los Alamitos, CA, G. M. Cortelazzo and C. Guerra, Eds., 428--438.
• 11: Iddo Drori , Daniel Cohen-Or , Hezy Yeshurun, Fragment-based image completion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 12: Alexei A. Efros , William T. Freeman, Image quilting for texture synthesis and transfer, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.341-346, August 2001 [doi>10.1145/383259.383296]
• 13: Alexei A. Efros , Thomas K. Leung, Texture Synthesis by Non-Parametric Sampling, Proceedings of the International Conference on Computer Vision-Volume 2, p.1033, September 20-25, 1999
• 14: Aaron Hertzmann , Charles E. Jacobs , Nuria Oliver , Brian Curless , David H. Salesin, Image analogies, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.327-340, August 2001 [doi>10.1145/383259.383295]
• 15: Aaron Hertzmann , Nuria Oliver , Brian Curless , Steven M. Seitz, Curve analogies, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 16: ILIC, S., AND FUA, P. 2003. Implicit meshes for modeling and reconstruction. In 2003 Conference on Computer Vision and Pattern Recognition (CVPR 2003), 483--492.
• 17: JIA, J., AND TANG, C.-K. 2003. Image repairing: Robust image synthesis by adaptive nd tensor voting. In 2003 Conference on Computer Vision and Pattern Recognition (CVPR 2003), 643--650.
• 18: Vivek Kwatra , Arno Schödl , Irfan Essa , Greg Turk , Aaron Bobick, Graphcut textures: image and video synthesis using graph cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 19: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 20: Peter Liepa, Filling holes in meshes, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 21: Yutaka Ohtake , Alexander Belyaev , Marc Alexa , Greg Turk , Hans-Peter Seidel, Multi-level partition of unity implicits, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 22: SAVCHENKO, V., AND KOJEKINE, N. 2002. An approach to blend surfaces. In CGI, 139--150.
• 23: SUN, J., ZHENG, N.-N., TAO, H., AND SHUM, H.-Y. 2003. Image hallucination with primal sketch priors. In 2003 Conference on Computer Vision and Pattern Recognition (CVPR 2003), 729--736.
• 24: Gabriel Taubin, Distance approximations for rasterizing implicit curves, ACM Transactions on Graphics (TOG), v.13 n.1, p.3-42, Jan. 1994 [doi>10.1145/174462.174531]
• 25: VERDERA, J., CASELLES, V., BERTALMIO, M., AND SAPIRO, G. 2003. Inpainting surface holes. In 2003 International Conference on Image Processing 2003 ICIP.
• 26: Li-Yi Wei , Marc Levoy, Fast texture synthesis using tree-structured vector quantization, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.479-488, July 2000 [doi>10.1145/344779.345009]
• 27: Lexing Ying , Aaron Hertzmann , Henning Biermann , Denis Zorin, Texture and Shape Synthesis on Surfaces, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.301-312, June 25-27, 2001
• 28: Zhengyou Zhang, Iterative point matching for registration of free-form curves and surfaces, International Journal of Computer Vision, v.13 n.2, p.119-152, Oct. 1994 [doi>10.1007/BF01427149]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations