“Context-based surface completion” by Sharf, Alexa and Cohen-Or

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.

1. ADOBE, 2002. Adobe photoshop 7.0.Google Scholar
2. AMENTA, N., BERN, M., AND KAMVYSSELIS, M. 1998. A new voronoi-based surface reconstruction algorithm. In Proceedings of SIGGRAPH 98, Computer Graphics Proceedings, Annual Conference Series, 415–422. Google ScholarDigital Library
3. BAJAJ, C. L., BERNARDINI, F., AND XU, G. 1995. Automatic reconstruction of surfaces and scalar fields from 3D scans. In Proceedings of SIGGRAPH 95, Computer Graphics Proceedings, Annual Conference Series, 109–118. Google ScholarDigital Library
4. BAREQUET, G., AND SHARIR, M. 1995. Filling gaps in the boundary of a polyhedron. Computer Aided Geometric Design 12, 2, 207–229. Google ScholarDigital Library
5. BESL, P., AND MCKAY, N. 1992. A method for registration of 3D shapes. IEEE Transaction on Pattern Analysis and Machine Intelligence 14, 2, 239–256. Google ScholarDigital Library
6. CHEN, Y., AND MEDIONI, G. 1992. Object modeling by registration of multiple range images. Image and Vision Computing 10, 3, 145–155. Google ScholarDigital Library
7. CLARENZ, U., DIEWALD, U., DZIUK, G., RUMPF, M., AND RUSU, R. 2004. A finite element method for surface restoration with smooth boundary conditions. In CAGD. submitted, available from http://numerik.math.uni-duisburg.de/. Google ScholarDigital Library
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.Google ScholarCross Ref
9. CURLESS, B., AND LEVOY, M. 1996. A volumetric method for building complex models from range images. In Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, 303–312. Google ScholarDigital Library
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.Google ScholarCross Ref
11. DRORI, I., COHEN-OR, D., AND YESHURUN, H. 2003. Fragment-based image completion. ACM Transactions on Graphics 22, 3 (July), 303–312. Google ScholarDigital Library
12. EFROS, A. A., AND FREEMAN, W. T. 2001. Image quilting for texture synthesis and transfer. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 341–346. Google ScholarDigital Library
13. EFROS, A. A., AND LEUNG, T. K. 1999. Texture synthesis by non-parametric sampling. In IEEE International Conference on Computer Vision, 1033–1038. Google ScholarDigital Library
14. HERTZMANN, A., JACOBS, C. E., OLIVER, N., CURLESS, B., AND SALESIN, D. H. 2001. Image analogies. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 327–340. Google ScholarDigital Library
15. HERTZMANN, A., OLIVER, N., CURLESS, B., AND SEITZ, S. M. 2002. Curve analogies. In Rendering Techniques 2002: 13th Eurographics Workshop on Rendering, 233–246. Google ScholarDigital Library
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.Google ScholarCross Ref
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. Google ScholarDigital Library
18. KWATRA, V., SCHÖDL, A., ESSA, I., TURK, G., AND BOBICK, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. ACM Transactions on Graphics 22, 3 (July), 277–286. Google ScholarDigital Library
19. LEVOY, M., PULLI, K., CURLESS, B., RUSINKIEWICZ, S., KOLLER, D., PEREIRA, L., GINZTON, M., ANDERSON, S., DAVIS, J., GINSBERG, J., SHADE, J., AND FULK, D. 2000. The digital michelangelo project: 3D scanning of large statues. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 131–144. Google ScholarDigital Library
20. LIEPA, P. 2003. Filling holes in meshes. In Symposium on Geometry Processing, 200–205. Google ScholarDigital Library
21. OHTAKE, Y., BELYAEV, A., ALEXA, M., TURK, G., AND SEIDEL, H.-P. 2003. Multi-level partition of unity implicits. ACM Transactions on Graphics 22, 3 (July), 463–470. Google ScholarDigital Library
22. SAVCHENKO, V., AND KOJEKINE, N. 2002. An approach to blend surfaces. In CGI, 139–150.Google Scholar
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.Google Scholar
24. TAUBIN, G. 1994. Distance approximation for rasterizing implicit curves. ACM Transactions on Graphics 13, 1 (Jan.), 3–42. Google ScholarDigital Library
25. VERDERA, J., CASELLES, V., BERTALMIO, M., AND SAPIRO, G. 2003. Inpainting surface holes. In 2003 International Conference on Image Processing 2003 ICIP.Google ScholarCross Ref
26. WEI, L.-Y., AND LEVOY, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, 479–488. Google ScholarDigital Library
27. YING, L., HERTZMANN, A., BIERMANN, H., AND ZORIN, D. 2001. Texture and shape synthesis on surfaces. In Rendering Techniques 2001: 12th Eurographics Workshop on Rendering, 301–312. Google ScholarDigital Library
28. ZHANG, Z. 1992. Iterative point matching for registration of free-form curves and surfaces. International Journal of Computer Vision 13, 2, 119–152. Google ScholarDigital Library