重建物體三維資訊時，通常會因掃描產生數據的遺失，而造成三維模型破洞的產生；一個存在非預期破洞的模型無法有效的提供資訊於後續的運用，例如在三維物件的特徵擷取、辨識…等應用主題。近年來，許多破洞修復的演算法利用破洞附近的頂點與三角網格資訊進行修復，然而，若是破洞包含曲率變化劇烈的區域時，這些方法可能會修補出錯誤結果。

本論文提出一個利用二維影像輪廓疊合技術的改良式三維模型補洞演算法(Improved 3D Hole-filling Algorithm Based on Image Contour Matching, IHICM)，使修補結果可更加接近真實物件的網格模型。首先，運用Advancing Front mesh(AFM)法對破洞區域產生新增點以完成粗略的修補；接著，擷取修補網格的切片平面，獲得三維物體的表面(slicing surface)資訊，並以二維影像輪廓(contour)為基準進行新增點的位置調整，使新增點能更符合真實三維模型。本論文使用電腦模擬的三維模型與實際物體掃描的模型，分別執行AFM與IHICM方法於三維破洞修復。其實驗結果顯示，IHICM能有效的修補模型上的破洞區域，其體積誤差與ICP計算較小於AFM的修補結果，並更接近真實三維模型原來的樣貌。

The hole-filling is an amending processing to fit the real appearance of real subjects, and it is an important issue for the construction of a 3D mesh model. Recently, there are many algorithms have been proposed to accomplish the hole-filling task upon voxel-based and triangle-based in the neighborhood. However, the construction of hole-filling may unreliable if the hole is independent to the neighborhood.

Instead of referring to the neighboring meshes, we propose an improved 3D Hole-filling Algorithm based on 2D Image Contour Matching (IHICM). First, the advancing front mesh technique (AFM) is applied to repair the hole by creating new vertices. Next, the new vertices from vertical slice are correspondent adjusting to the contour in 2D image, and the new vertices from vertical slice are repositioned according to the curvature of the surface. In the experiments, we use synthetic and real subjects to demonstrate that the proposed IHICM is reliable and valid in hole-filling. The experimental results show that IHICM algorithm can amend holes effectively, and the volume error and ICP of IHICM is lower than that of the AFM.

[1]Poggio, T. and Edelman, S., “A network that learns to recognize three-dimensional objects,” Nature, Vol, 343, pp. 263–266 (1990).
[2]Tommasini, T., Fusiello, A., Trucco, E. and Roberto, V., “Making good features track better,” Computer Vision and Pattern Recognition, pp. 178–183 (1998).
[3]Lee, Y.C., Terzopoulos, D. and Waters, K., “Constructing Physics-Based Facial Models of Individuals,” Proceedings of Graphics Interface, pp. 1–8 (1993).
[4]Fofi, D., Sliwa, T. and Voisin, Y., “A comparative survey on invisible structured light,” In: Machine vision applications in industrial inspection XII, Vol.5303. San Jose, USA. pp. 90–98 (2004).
[5]Yin, Z., Yu, W., Li, M. and Lin, X., “Hole Filling using Dynamic Programming for Archaeological Data Completion,” Proceedings of the 2010 IEEE International Conference on Computer Science and Education, ICCSE 2010, No. 5593832, pp. 1750–1754 (2010).
[6]Davis, J., Marschner, S.R., Garr, M. and Levoy, M., “Filling Holes in Complex Surfaces using Volumetric Diffusion,” In 3DPVT Conference, pp. 428–438 (2002).
[7]Podolak, J. and Rusinkiewicz, S., “Atomic Volumes for Mesh Completion,” In Symposium on Geometry Processing. pp. 33–41 (2005).
[8]Ju, T., “Robust repair of polygonal models,” ACM Transactions on Graphics, pp. 888–895 (2004).
[9]Zhao, W., Gao, S. and Lin, H., “A Robust Hole-Filling Algorithm for Triangular Mesh,” The Visual Computer, Vol. 23, No. 10, pp. 987–997 (2007).
[10]George, L.P. and Seveno, E., “The advancing-front mesh generation method revisited,” International Journal of Numerical Methods, Vol. 37, No. 7, pp. 3605–3619 (1994).
[11]Jun, Y., “A piecewise hole-filling algorithm in reverse engineering,” Computer–Aided Design, Vol. 22, No. 8, pp. 263–270 (2005).
[12]Qiang, H., Shusheng, Z., Xiaoliang, B. and Xin, Z., “Hole filling based on local surface approximation,” ICCASM 2010 – 2010 International Conference on Computer Application and System Modeling, Vol. 3, No. 5620018, pp. V3242–V3245 (2010).
[13]Tekumalla, L. and Cohen, E., “A hole-filling algorithm for triangular meshes,” Technical Report UUCS–04–019, School of Computing, University of Utah, Dec. (2004).
[14]Wang, R., Liu, G., Lin, L. and Li, J., “Feature enhancing based hole filling algorithm for 3D mesh model,” World Congress on Intelligent Control and Automation, China, pp. 6168–6172 (2010).
[15]Sharf, A., Alexa, M. and Cohen-Or, D., “Context-based surface completion,” In SIGGRAPH’04: ACM SIGGRAPH 2004 Papers, New York, NY, USA, pp. 878–887 (2004).
[16]Brunton, A., Wuhrer, S., Shu, C., Bose, P. and Demaine, E.D., “Filling holes in triangular meshes by curve unfolding,” 2009 IEEE International Conference on Shape Modeling and Applications, SMI 2009, No. 5170165, pp. 66-72 (2009).
[17]Breckon, T. P. and Fisher, R. B., “Non-Parametric 3D Surface Completion,” IEEE Computer Society. In 3DIM’05: Proceedings of the Fifth International Conference on 3-D Digital Imaging and Modeling, Washington, DC, USA, pp. 573–580 (2005).
[18]Xiao, C., Zheng, W., Miao, Y., Zhao, Y. and Peng, Q., “A unified method for appearance and geometry completion of point set surfaces,” The Visual Computer, Vol. 23, No. 6, pp. 433–443 (2007).
[19]Pauly, M., Mitra, N., Giesen, J., Gross, M. and Guibas, L.J., “Example-based 3D scan completion,” In: Symposium on Geometry Processing, pp. 23–32 (2005).
[20]Lee, K. H., Woo, H. and Suk, T., “Data Reduction Methods for Reverse Engineering,” The International Journal of Advanced Manufacturing Technology, Vol. 17, pp. 735–743 (2001).
[21]鍾國亮，影像處理與電腦視覺，東華書局，台北，民國九十五年。
[22]Suetake, N., Uchino, E. and Hirata, K., “Generalized fuzzy Hough transform for detecting arbitrary shapes in a vague and noisy image,” Soft Computing, No. 10, pp. 1161–1168 (2006).
[23]Furht, B., Encyclopedia of Multimedia, Second Edition, Springer, pp. 222 (2008).
[24]Wikipedia,(2008), “Structured-light 3D scanner” http://en.wikipedia.org/wiki/Structured-light_3D_scanner, 1 July 2011.
[25]冬陽，3D遊戲程式設計，第2-26頁∼第2-28頁，台北，宸宇出版社，民國九十二年。
[26]Besl, P. J. and McKay, N. D., ”A Method for Registration of 3-D Shapes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, pp. 239–256 (1992).
[27]Perez, P., Gangnet, M. and Blake, A., “Poisson image editing,” Proceedings of SIGGRAPH, pp. 313–318. (2003).
[28]Perez, E., Salamanca, S., Merchan, P., Adan, A., Cerrada C. and Cambero, I. “Filling holes in 3D meshes based on image restoration,” Lecture Notes in Computer Science 5259 LNCS, pp. 742–751 (2008).
[29]Levin, A., “Combined subdivision schemes for the design of surfaces satisfying boundary conditions,” Computer Aided Geometric Design, No. 16, pp. 345–354 (1999).
[30]Golias, N.A. and Dutton, R.W., “Delaunay triangulation and 3D adaptive mesh generation,” Finite Elements in Analysis and Design, Vol. 25, No. 91, pp. 331–341 (1997).
[31]Dong J., Ma, S., Li L. and Yu Z., ”Hole filling on three–dimensional surface texture,” Proceedings of the 2007 IEEE International Conference on Multimedia and Expo, ICME 2007, No. 4284896, pp. 1299–1302 (2007).
[32]Gonazlez, R. C. and Woods, R. E., Digital Image Processing, Third Edition Prentice-Hall, New York (2008).