在本篇論文中，我們首先探討了現在具代表性的幾種inpainting演算法，發現基於偏微分方程的inpainting演算法對於結構性的保留的效果良好，但是大部分基於偏微分方程的inpainting演算法其計算複雜度都相當高。所以我們提出一個用來修補卡通的新inpainting演算法，我們使用顏色分群的技術來取得結構性資料或稱輪廓線並且使用餘弦定理來計算輪廓線取樣長度，以我們取樣的輪廓線推算出在修補區域內輪廓線的結構性，進而使用類似於現實生活中的貝茲曲線來重建消失的結構性資料。本篇論文中所提之演算法運算速度非常快，並且能充分保留修補區域內結構性的資料。

In this study, we first studied several inpainting algorithms. Inpainting algorithms based PDE (Partial Differential Equation) preserve the construction very well, but time consuming. We propose a new inpainting algorithm for cartoon based on color segmentation to preserve the structure of image. After trying several different ways to find the map of contour lines, we use color segmentation to construct the map of contour lines, and use the law of cosine to estimate the length of contour line we sample. We also estimate the slope of contour lines and compute how they should extend in the inpainting domain. We use the advantage of Bézier curves that fit the curves to the real world to reconstruct the contour lines. The algorithm also fit to more general cases.

目錄
第一章　緒論 ......................................1
1.1　研究動機 .....................................1
1.2　相關研究 .....................................4
1.3　研究目的 ....................................11
1.4　論文組織架構 ................................11
1.5　研究方法概述 ................................12
第二章　基礎理論 .................................13
2.1　Color model色彩模型 .........................13
2.2　Sobel 邊緣偵測 ..............................20
2.3　Canny邊緣偵測 ...............................22
2.4　K-means分群技術 .............................25
2.5　Mean-shift based 分群技術 ...................28
2.6　Bézier curve貝茲曲線 ........................30
第三章　研究方法 .................................34
3.1　演算法流程 ..................................34
3.2　輪廓線的取得與資訊計算 ......................35
3.3　輪廓線延伸的估計方法 ........................41
3.4　輪廓線的重建 ................................44
3.5　個案討論 ....................................45
第四章　實驗結果、討論與實驗環境 .................47
4.1　實驗環境 ....................................47
4.2　實驗結果與討論 ..............................56
第五章　結論與未來研究方向 .......................66
5.1　結論 ........................................66
5.2　未來研究方向 ................................67
參考文獻 .........................................68
英文論文 .........................................71

圖目錄
圖1 紋理的產生與合成 ..............................2
圖2 刮痕的修補 ....................................3
圖3 Isophote line .................................4
圖4 Total Variation model的缺點 ...................5
圖5 Oliveira的方法與加上barrier之後的差異 .........7
圖6 Exemplar-Based Image Inpainting步驟 ...........8
圖7 Exemplar-Based Image Inpainting變數示意圖 .....9
圖8 DM與YM的算法示意圖 ...........................10
圖9 初始的修補概念 ...............................12
圖10 RGB color space .............................14
圖11 HIS color space .............................17
圖12 Sobel edge detection的結果 ..................21
圖13 Canny edge detection的結果 ..................23
圖14 k-means演算法執行範例 .......................27
圖15 EDISON 系統執行之畫面 .......................29
圖16 原圖與輪廓線圖 ..............................29
圖17 Linear Bézier curve .........................31
圖18 Quadratic Bézier curve ......................32
圖19 Cubic Bézier curve ..........................33
圖20 流程圖 ......................................34
圖21 輪廓線上的點 ................................35
圖22 輪廓線上的向量 ..............................36
圖23 斜率變化圖 ..................................37
圖24向量構成之三角形 .............................38
圖25  之圖形 .....................................40
圖26 取樣長度的決定 ..............................41
圖27 輪廓線延伸後之交會點 ........................44
圖28 Ｙ型輪廓線之修補結果 ........................45
圖29 Ｔ型輪廓線 ..................................46
圖30 Borland C++ Build IDE介面 ...................48
圖31 元件樹狀結構區圖示 ..........................49
圖32 元件選取區圖示 ..............................50
圖33 元件編輯區圖示 ..............................50
圖34 系統設計與程式撰寫區圖示 ....................51
圖35 Form1的元件架構示意圖 .......................52
圖36 選取要顯示的圖片 ............................53
圖37 顯示分析輪廓線的資訊 ........................54
圖38 Form2的元件架構示意圖 .......................55
圖39 offset計算示意圖 ............................56
圖40 Set1之修補結果 ..............................58
圖41 Set2之修補結果 ..............................63

[1] M. Bertalmio, G. Sapiro, V. Caselles, and C. Ballester, “Image Inpainting,” in Proceedings of the ACM SIGGRAPH Conference on Computer Graphics 2000, Pages 417-424

[2] Tony F. Chan, Jianhong Shen, “Mathematical Models for Local Deterministic Inpaintings,” in UCLA Computational and Applied Mathematics Reports, TR 00-11, March 2000.

[3] Tony F. Chan, Jianhong Shen, “Non-Texture Inpainting by Curvature-Driven Diffusions (CCD),” in UCLA Computational and Applied Mathematics Reports, TR 00-35, September 2000.

[4] M. Oliveira, B. Bowen, R. McKenna, and Y.-S. Chang, “Fast Digital Image Inpainting,” Proceedings of International Conference on Visualization, Imaging, and Image Processing 2001, Pages 261-266

[5] A. Criminisi, P. Perez, K. Toyama, “Object Removal by Exemplar-Based Inpainting,” Proceedings of Computer Vision and Pattern Recognition 2003.

[6] Shih-Chang Hsia, “A Fast Efficient Restoration Algorithm for High-noise Image Filtering with Adaptive Approach,” Journal of Visual Communication and Image Presentation, June, 2005, Pages 379-392.

[7] Sobel, I., Feldman, G., “A 3x3 Isotropic Gradient Operator for Image Processing,“ presented at a talk at the Stanford Artificial Project in 1968, unpublished but often cited, orig. in Pattern Classification and Scene Analysis, Duda, R. and Hart, P., John Wiley and Sons, 1973, pp271-2

[8] Canny, J., “A Computational Approach to Edge Detection,” in IEEE Transactions of Pattern Analysis and Machine Intelligence, 1986, Vol.8 Pages 679-714.

[9] J. B. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,” in Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability", Berkeley, University of California Press, 1967, Vol.1, Pages 281-297

[10] D. Comaniciu and P. Meer, “Mean shift: A Robust Approach toward Feature Space,” in IEEE Transactions of Pattern Analysis and Machine Intelligence, 2002, Vol.24, Pages 603-619