數位影像修補及修改技術是一種影像竄改的機制，這種技術可以自動地修補影片中被損毀的區域或是移除影像中的物件。大多數修補技術都使用單一解析度的方法，去推斷被破壞的影像像素資訊，然後進行修補。在本論文中，我們將提出一個使用多重解析度為基礎的演算法，針對不同階層的解析度進行考慮，提供一個影像修補的機制。這個技術的原理是將需要修補的影像切分為許多小區塊，並利用每一區塊與階層中色彩變異度的關係進行評估，決定可用來修補的資訊。
另外，特別針對傳統中國繪畫的特性，提出一個使用多重圖層為考量的修補策略，成功地結合多重解析度的影像修補演算法，針對不同圖層中的解析度進行考慮，並設計一個多重圖層的修補與圖層合併演算法。在此研究中，分別實驗1500張各類的圖片，包括卡通、風景照片、國畫與西洋畫等影像圖片，進行不同比例破壞程度之修補成效測試，並與不同的影像修補技術，進行修補後結果與效率之比較。根據實驗的結果，我們所提出的修補策略，其修補後的圖片，具有相當高的PSNR數值，其執行修補程序的效率，較其他方法快速。

Digital inpainting is an image interpolation mechanism, which can automatically restore a damaged or partially removed image.  Since most inpainting mechanisms use a singular resolution approach on the extrapolation or interpolation of pixels, this thesis proposes a multi-resolution algorithm, which takes into consideration the different levels of detail. The algorithm is based on the concept of image subdivision and estimation of color variations. Noises inside blocks of different sizes are inpainted with different levels of surrounding information.  The results showed that an almost unrecognizable image can be recovered with visually good results.
Furthermore, we study how Chinese paintings are drawn, and propose a multilayer inpainting mechanism which can be used effectively on Chinese and western paintings. The thesis conducts a new approach, which divides a Chinese painting into several layers and each layer is inpainting separately.  A layer fusion mechanism then finds the optimal inpaint among layers, which are restored one-by-one. We apply the algorithm on Chinese and western drawings.  These algorithms were tested on 1500 still images and an evaluation shows the effectiveness of our approach, a high PSNR value as well as a high level of user satisfaction.

ABSTRACT		
CONTENTS.	......................................I
LIST OF FIGURES................................III
LIST OF TABLES..................................VI
CHAPTER 1	INTRODUCTION..........................1
1.1	WHAT IS THE INPAINTING?...............1
1.2	THE IMAGE INPAINTING TECHNOLOGY.......7
1.3	THE OBJECTS OF THIS STUDY............13
1.4	ORGANIZATION OF THE DISSERTATION.....14
CHAPTER 2	BACKGROUND & RELATED WORKS...........15
2.1	COLOR IMAGE PROCESSING...............15
2.2	IMAGE INPAINTING METHODS IN THE LITERATURE......20
CHAPTER 3	THE PROPOSED SCHEMES.................28
3.1	MULTI-RESOLUTION INPAINTING	..........28
3.2	ADAPTIVE DIGITAL IMAGE INPAINTING....35
3.3	PRELIMINARY EXPERIENCE AND GENERAL PRINCIPLE OF PAINTING........................38
3.4	MULTILAYER IMAGE INPAINTING	...........41
CHAPTER 4	THE EVALUATION STRATEGY...............52
4.1	EVALUATION OF PICTURE QUALITY.........52
4.2	THE EVALUATION STRATEGY...............53
CHAPTER 5	EXPERIMENTAL RESULTS & ANALYSIS.......56
5.1	EXPERIMENTAL RESULTS..................56
5.2	ANALYSIS	.............................61
5.3	COMPARISONS...........................68
5.4	EXTREME CASES WITH HIGH PERCENTAGES OF DAMAGES	......................................76
5.5	DISCUSSION OF THE RELATION BETWEEN DAMAGE PERCENTAGES AND PSNR VALUES	....................80
CHAPTER 6	CONCLUSIONS & FUTURE WORK	...........83
6.1	CONCLUSIONS...........................83
6.2	FUTURE WORKS..........................84
BIBLIOGRAPHY...................................85

LIST OF FIGURES
Figure 1.1:  The example of old picture and the painting work.....................................................2
Figure 1.2: An example of inpainted result...............3
Figure 1.3: Reconstruction results for more drastic losses...................................................3
Figure 1.4:  An inpainting example of move the object....4
Figure 1.5: Restoration of an image sequence	...........5
Figure 1.6: Sample results of inpainting surface holes	..6
Figure 1.7:  Restoration of an old photograph	...........7
Figure 1.8: An inpainted result with visible watermarking.............................................8
Figure 1.9:  Image restoration using multi-resolution texture  synthesis and image inpainting..................9
Figure 1.10:  Removing large objects from images........10
Figure 1.11:  An example of fragment-based image completion..............................................12
Figure 1.12: A category of the image inpainting problem.................................................12
Figure 2.1: Propagation direction as the normal to the signed distance to the boundary of the region to be inpainted	...............................................22
Figure 2.2: A color image and removal of superimposed text....................................................22
Figure 2.3:  Pseudocode for the fast inpainting algorithm...............................................24
Figure 2.4:  Different diffusion kernels used  with the fast image inpainting algorithm.........................24
Figure 2.5:  An 1865 photograph of Abraham Lincoln......24
Figure 2.6:  An example with digital zoom-in based on  the TV inpainting scheme....................................25
Figure 2.7: A sample result by CDD inpainting scheme..	.27
Figure 3.1: An illustration of part of damaged image....29
Figure 3.2: The flowchart of the multi-resolution algorithm................................................32
Figure 3.3: A multi-resolution inpainting tool...........33
Figure 3.4: The results of multi-resolution inpainting algorithm	................................................34
Figure 3.5: An example of removing object from a photo...39
Figure 3.6: An example of inpainting on western painting.................................................40
Figure 3.7: An example of the painting a landscape.......40
Figure 3.8: The flowchart of the multi layer image inpainting procedure.....................................42
Figure 3.9: An example of layer separation in 3 layers...45
Figure 3.10: An example of multi layer fusion	...........48
Figure 3.11: The flowchart of the multilayer fusion algorithm	................................................49
Figure 3.12: A multi layer inpainting tool...............50
Figure 3.13: The complete procedure for multilayer image inpainting	51
Figure 4.1: An example of the quad-tree representation	..55
Figure 5.1: A multi-resolution inpainting tool...........57
Figure 5.2: The damaged sample for inpainting simulation...............................................58
Figure 5.3: A sample test set for image inpainting.......58
Figure 5.4: Experiment results by single and multiple resolution inpainting algorithms.........................59
Figure 5.5: A multi layer inpainting tool with divided the test picture in three layers.............................60
Figure 5.6: The sample result of the multilayer inpainting tool.....................................................61
Figure 5.7: Results from 1000 pictures...................63
Figure 5.8: Damaged and inpainted pictures (Flowers).....66
Figure 5.9: Damaged and inpainted pictures (People)......67
Figure 5.10: Damaged and inpainted pictures (Landscape)..............................................67
Figure 5.11: An example of inpainting on cartoon drawing..................................................70
Figure 5.12: The microphone has been removed in the test picture..................................................72
Figure 5.13: The enlargement of image from Figure 5.12 (see the differences in the ovals)............................72
Figure 5.14: Comparison with diffusion-based inpainting model....................................................73
Figure 5.15: The details of image restoration example....73
Figure 5.16: Result of the inpainted images with different methods	................................................75
Figure 5.17: Test images set from the literature.........77
Figure 5.18: Extreme results by different inpainting strategies–test images from the literature..............78
Figure 5.19: Extreme results by different inpainting strategies – photos.....................................79
Figure 5.20: Noise ratio vs. PSNR values (all test pictures)................................................81

 
LIST OF TABLES

Table 3.1: Threshold values	.............................38
Table 5.1: Test results of average PSNR value (dB)  with 2 sets of parameters using 1000 pictures..................62
Table 5.2: Test results of area percentages with PSNR > 30 dB......................................................62
Table 5.3: Average PSNR values (dB) with 1500 pictures..65
Tabel 5.5: PSNR values of image with different methods..75
Table 5.6: PSNR values of image with different ratios of noise (some results are shown in Figure 5.18)	..........78
Table 5.7: PSNR values of image with different ratios of noise (some results are shown in Figure 5.19)	..........79
Table 5.8: PSNR values of image with different ratios of noise and different categories test pictures	..........80

1.Barcelos, C. A. Z., Batista, M. A., Martins, A. M., & Nogueira, A. C. (2004). Level lines continuation based digital inpainting. Proceedings - Brazialian Symposium on Computer Graphics and Image Processing, 2004, 50-57.
2Berns, R. S., Krueger, J., & Swicklik, M. (2002). Multiple pigment selection for inpainting using visible reflectance spectrophotometry. Studies in Conservation, 47(1), 46-61. 
3.Bertalmio, M., Sapiro, G., Caselles, V., & Ballester, C. (2000). Image inpainting. ACM SIGGRAPH 2000, Jul 23-28 2000, 417-424.
4.Bertalmio, M., Bertozzi, A. L., & Sapiro, G. (2001). Navier-Stokes, fluid dynamics, and image and video inpainting. 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Dec 8-14 2001, 1, 355-362. 
5.Bertalmio, M., Vese, L., Sapiro, G., & Osher, S. (2003). Simultaneous structure and texture image inpainting. IEEE Transactions on Image Processing, 12(8), 882-889. 
6.Bertalmio, M., Vese, L., Sapiro, G., & Osher, S. (2003). Image filling-in in a decomposition space. Proceedings: 2003 International Conference on Image Processing, ICIP-2003, Sep 14-17 2003, 1, 853-855.
7.Bornard, R., Lecan, E., Laborelli, L., & Chenot, J-H. (2002). Missing data correction in still images and image sequences. ACM Multimedia, 2002, 355–361.
8.Ceccarelli, M., and Laccetti, G. (2003). High performance missing data detection and interpolation for video compression and restoration applications. Proceedings: International Parallel and Distributed Processing Symposium (IPDPS’03), April 2003, 1-5.
9.Chan, T. F., & Shen, J. (2001A). Nontexture inpainting by curvature-driven diffusions. Journal of Visual Communication and Image Representation, 12(4), 436-449. 
10.Chan, T.-F., & Shen, J. (2001B). Mathematical models for local non-texture inpaintings.  SIAM Journal on Applied Mathematics, 2001, 62(3), 1019–1043.
11.Chan, T.-F., & Shen, J. (2001C). Variational restoration of non-flat image features: models and algorithms. SIAM Journal on Applied Mathematics, 2001, 61(4), 1338–1361.
12.Chan, T.-F., & Shen, J. (2002A). Inpainting based on nonlinear transport and diffusion. Contemporary Mathematics, 2002, 313, 53-66.
13.Chan, T. F., & Shen, J. (2002B). Mathematical models for local nontexture inpaintings. SIAM Journal on Applied Mathematics, 62(3), 1019-1043.
14.Chen, Y.-H. (1993). Chinese painting by Chen Yung-Hao. (Chinese), 1993, 24-42.
15.Caselles, V., Morel, J.-M. & Sbert, C. (1998). An axiomatic approach to image interpolation. IEEE Transactions Image Processing, 1998, 7(3), 376–386.
16.Cocquerez, J. P., Chanas, L., & Blanc-Talon, J. (2003). Simultaneous inpainting and motion estimation of highly degraded video-sequences. LECTURE NOTES IN COMPUTER SCIENCE, (2749), 685-692. 
17.Criminisi, A., Pérez, P., & Toyama, K. (2003). Object removal by exemplar-based inpainting. Proceedings: 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Jun 18-20 2003, 2, 721-728.
18.Criminisi, A., Pérez, P., & Toyama, K. (2004). Region filling and object removal by exemplar-based image inpainting. IEEE Transactions on Image Processing, 13(9), 1200-1212. 
19.Davis, J., Marschner, S., Garr, M., and Levoy, M.(2002). Filling holes in complex surfaces using volumetric diffusion. First International Symposium on 3D Data Processing, Visualization, Transmission, (3DPVT’02), 2002, 858-862.
20.Drori, I., Cohen-Or, D., & Yeshurun, H. (2003). Fragment-based image completion. ACM SIGGRAPH 2003, 303 – 312.
21.Esedoglu, S., & Shen, J. (2002). Digital inpainting based on the mumford-shah-euler image model.  European Journal of Applied Mathematics, 2002, 13(4), 353-370.
22.Gonzalez, R. C. & Woods, R. E. (2002). Digital image processing. 2nd Ed., NJ:Prentice Hall, 2002, 205-261.
23.Gonzalez, R. C., Woods, R. E. & Eddins, S.L. (2004). Digital image processing using MATLAB.  NJ:Prentice Hall, 2004, 195-241.
24.Huang, C.-H., & Wu, J.-L. (2004). Attacking visible watermarking schemes. IEEE Transactions on Multimedia, 6(1), 16-30. 
25.Kim, W.S., Park, R.H., (1996). Color image palette construction based on the HSI color system for minimizing the reconstruction error. IEEE International Conference on Image Processing, 1996, 1041-1044.
26.Kokaram, A.-C., Morros, R.-D., Fitzerald, W.-J., and Rayner, P.-J.-V. (1995). Detection of missing data in image sequences. IEEE Transactions Image Processing, 1995, 4(11), 1496-1508.
27.Kwok, W., & Sun, H. (1993). Multidirectional interpolation for spatial error concealment. IEEE Transactions Consumer Electronics, 1993, 39(3):455-460.
28.Levin, A., Zomet, A., & Weiss, Y. (2003). Learning how to inpaint from global image statistics. Proceedings: Ninth IEEE International Conference on Computer Vision, Oct. 13-16 2003, 1, 305-312. 
29.Littmann, E., & Ritter, H. (1997). Adaptive color segmentation - a comparison of neural and statistical methods. IEEE Transaction on Neural Network, 1997, 8(1), 175-185.
30.Masnou, S., & Morel, J.-M. (1998). Level-lines based disocclusion.  Proceedings: 5th IEEE International Conference on Image Processing, Chicago, 1998, 259–263.
31.Oliveira, M. M., Bowen, B., McKenna, R., & Chang, Y.-S. (2001) Fast digital image inpainting. Proceedings: 2001 International Conference on Visualization, Imaging and Image Processing (VIIP’ 01), 2001, 261-266.
32.Orchard, M.T., & Bouman, C.A. (1991). Color quantization of images. IEEE Transactions Signal Process, 1991, 39(12), 2677-2690.
33.Patwardhan, K. A., & Sapiro, G. (2003). Projection based image and video inpainting using wavelets. Proceedings: 2003 International Conference on Image Processing, ICIP-2003, Sep. 14-17 2003, 1, 857-860. 
34.Park, J., Park, D.-C., Marks, R.-J., and El-Sharkawi, M.-A. (2005). Recovery of image blocks using the method of alternating projections. IEEE Transactions Image Processing, Apr. 2005, 14(4), 461-474. 
35.Rane, S. D., Sapiro, G., & Bertalmio, M. (2003). Structure and texture filling-In of missing image blocks in wireless transmission and compression applications. IEEE Transactions on Image Processing, 12(3), 296-303.
36.Rares, A., Reinders, M. J. T., Biemond, J., & Lagendijk, R. L. (2002). A spatiotemporal image sequence restoration algorithm. International Conference on Image Processing (ICIP'02), Sep. 22-25 2002, 2:857-860.
37.Robinson, G.S. (1977). Color edge detection, Optical Engineering, 1977, 16(5), 479-484.
38.Shih, T. K., Lu, L.-C., & Chang, R.-C. (2003). A automatic image inpaint tool. Proceedings of the ACM International Multimedia Conference and Exhibition, 2003, 102-103. 
39.Shih, T. K., Chang, R.-C., Lu, L.-C., Ko, W., & Wang, C. (2004). Adaptive digital image inpainting. Proceedings: 18th International Conference on Advanced Information Networking and Applications, AINA 2004, Mar. 29-31 2004, 1, 71-76. 
40.Shih, T. K., Chang, R.-C., Lu, L.-C., & Lin, L. H. (2004). Large block inpainting by color continuation analysis. Proceedings: 10th International Multimedia Modelling Conference, MMM 2004, Jan. 5-7 2004, 196-202. 
41.Shih, T. K., Chang, R.-C., Lu, L.-C., & Huang, H.-C. (2004). Multi-layer inpainting on Chinese artwork. Proceedings: 2004 IEEE International Conference Multimedia and Expro, ICME 2004, Jun. 27-30 2004, 1, 21-24. 
42.Tan, P., Lin, S., Quan, L., & Shum, H. (2003). Highlight removal by illumination-constrained inpainting. Proceedings: Ninth IEEE International Conference on Computer Vision, Oct. 13-16 2003, 1, 164-169. 
43.Tsai, A., Yezzi, J. A., & Willsky, A. S. (2001). Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation and magnification. IEEE Transactions Image Processing, 2001, 10(8), 1169–1186.
44.Verdera, J., Caselles, V., Bertalmio, M., & Sapiro, G. (2003). Inpainting surface holes. Proceedings: 2003 International Conference on Image Processing, ICIP-2003, Sep. 14-17 2003, 2, 903-906. 
45.Wei, L.-Y. & Levoy, M. (2000). Fast texture synthesis using tree-structured vector quantization. Proceedings: the 27th Annual Conference on Computer Graphics and Interactive Techniques, 2000, 479-488
46.Yamauchi, H., Haber, J., & Seidel, H.-P. (2003). Image restoration using multiresolution texture synthesis and image inpainting. Computer Graphics International, 2003, 108-113.
47.Zheng, J., & Wang, S. (2003). Image restoration using total variation approach. Journal of Computer-Aided Design and Computer Graphics, 2003, 15(10), 1218-12