圖像以及影片修補的技術已經被很廣泛的應用在日常生活中。在過去幾年中，影片修補可以針對攝影機無移動、有移動的幾乎靜止的背景進行物件的取出。然而，要從動態的背景(如煙霧、火焰以及河流)移除物件則是相當困難的研究。利用現有的影像修補演算法進行處理的話，往往會導致動態結構不連續的問題產生。因此在本研究中，我提出一個全新的修補演算法來解決動態結構不連續的問題。我使用一套不同於以往修補演算法的搜尋區塊的方法，結合邊緣、色彩以及動量的資訊進行區塊的尋找，再透過找出最小能量的隙縫進行區塊影片的時間延長，藉此將找出的區塊時間可以與原始影像相同，最後再利用圖片切割以及泊松方程進行區塊的貼入。除了提出這個演算法之外，我還提出一個方法進行修補結果的判斷，讓使用者可以知道修補的效果。我的這個技術可以利用在一些特效的製作以及影片的後置。

Image and video inpainting technologies were studied in the literature. In the past few years, video inpainting methods remove objects from stationary or non-station videos, with mostly static backgrounds. However, to remove objects in a dynamic background, such as fire or smoke scene, most video inpainting algorithms result in a discontinuous visual effect. Although there are several technologies that can be used to generate dynamic textures, there still exists problems for inpainting, such as bad motion continuity due to improper color or motion with respect to the original video. We propose a novel inpainting algorithm to solve the motion textures problem, called motion inpainting. A few steps are introduced in the algorithm, including searching for motion patches from different time slots, extending motion streams, and motion patch blending. We also propose a mechanism to evaluate motion coherence in our experiments. The algorithm is generic and can be used in special effect applications.

Table of Content
Chapter 1	Introduction	1
1.1	Motivation	1
1.2	Overview of Inpainting	2
1.3	Organization of this Dissertation	5
Chapter 2	Related Works	7
2.1	Motion Estimation and Object Extraction	7
2.2	Dynamic Background Generation	9
Chapter 3	Proposed Methodologies	12
3.1	Object Segmentation	12
3.2	Computing Priority Map for Inpainting	21
3.3	The New Motion Inpainting Algorithm	26
3.3.1	The Similarity of Patches	26
3.3.2	Video Extension of Patch Stream	36
3.3.3	Patch Stream Insertion	44
3.4	Motion Coherence and Patch Re-searching	49
3.4.1	The Motion Coherence Function	49
3.4.2  Analysis of Patch Motions for Re-searching  52
Chapter 4	Experimental Results and Analysis	55
4.1	The Motion Mean Squared Error	55
4.2	The Experimental Results	56
Chapter 5	Conclusion	66
5.1	Conclusion	66
Reference  68

Table of Figures
Figure 1. The flowchart of proposed approach	6
Figure 2. Object tracking and extracting	8
Figure 3. Dynamic texture generation	9
Figure 4. Cross-Diamond-Hexagonal Search	15
Figure 5. A sample of the proposed tracking algorithm	16
Figure 6. The area to be analyzed is showed in (b). The blue area contains the patches with both foreground and background information.	18
Figure 7. (a) shows the selected region in the video. The red area will be inpainted, also shown in (b). In (b), area I represents the whole video frame, where Φ is the background and Ω is the selected region. In (c), the point P is a point to compute the priority value.	22
Figure 8. The left figure is the source image, with the gradient and edge on the right.	23
Figure 9. Figure (a) shows the volume of the video in 3D. Figures (b) and (c) are two patches in different frames, where several feature points are used on the contour.	28
Figure 10. Multiple candidate patches (in red) may exist in more than one frame, when compared with the source patch (in yellow).	32
Figure 11. The feature points on patches.	32
Figure 12. The inpainting result without patch stream extension in time.	35
Figure 13. The connection and monotonic of the pixels in seam	39
Figure 14 The result of the seam extracted from the plane. The red line is the seam.  Seams can be duplicated or interpolated for video extension.	39
Figure 15. The upper figure is the x-t plane with seam, the lower figure is the y-t plane with the seam.	40
Figure 16. The sample with discontinuous seams	41
Figure 17. The method to find the optimal curve	41
Figure 18. The example of search the curve	42
Figure 19. Difference between direct pasting a patch and using our patch pasting method	46
Figure 20. The inpainting result is in figure (a). Figure (b) shows the motion vectors. The red arrows are the motion vectors in the inpainting area, the white are the motions around this area.	48
Figure 21. The analysis of motion vectors (the red arrows are the motion vectors in the inpainted area; the white arrows are the motion vectors in the original background.).	51
Figure 22. Experimental Results.	65

Table of Tables
Table 1. The weight differences of direction pairs. 34
Table 2. The Coherence value of Three Samples. 50
Table 3. The sets of weights of the analysis. 57
Table 4. The MMSE Values to Test Different Parameters. 58
Table 5. The MMSE Analysis for All Samples. 59
Table 6. The performance of the Experimental Results.  61

[1]	J.K. Aggarwal and Q. Cai, “Human Motion Analysis: A Review.” In: IEEE Nonrigid and Articulated Motion Workshop, 1997.
[2]	S. Avidan and A. Shamir, “Seam Carving for Content-Aware Image Resizing,” In  ACM Trans. Graph. Vol. 26( 3), Article 10, July 2007.
[3]	J.L. Barron , D.J. Fleet, and S. Beauchemin. "Performance of optical flow techniques." Internation Journal of Computer Vision, Vol. 12, pp. 43-77, 1994.
[4]	M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, "Image Inpainting," Proceedings of SIGGRAPH 2000, New Orleans, USA, July 2000.
[5]	M. Bertalmio, L. Vese, G. Sapiro and S. Osher, "Simultaneous structure and texture image inpainting", IEEE Transactions on Computer Vision and Pattern Recognition, Vol. 12(8), pp. 882 -889, Aug. 2003.
[6]	Y. Boykov, O. Veksler, R. Zabih, "Fast approximate energy minimization via graph cuts," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23(11), pp. 1222-1239, Nov. 2001.
[7]	C.H. Cheung and L.M. Po, "Novel cross-diamond-hexagonal search algorithms for fast block motion estimation," IEEE Transactions on Multimedia, Vol. 7 (1), pp. 16-22, Feb. 2005.
[8]	R. Costantini, L. Sbaiz, S. Susstrunk, “Higher Order SVD Analysis for Dynamic Texture Synthesis,” In IEEE Transactions on Image Processing, Vol. 17 (1). pp. 42-52., 2008.
[9]	A. Criminisi, P. Perez, and K. Toyama, "Region filling and object removal by exemplar-based inpainting," in IEEE Transactions on Image processing, vol. 13(9), pp. 1200-1212, Jan. 2004
[10]	A. Criminisi, P. Perez and K. Toyama, “Object removal by exemplar-based inpainting,” In: IEEE Transactions on Computer Vision and Pattern Recognition, Vol. 2, pp. 721 -728, 2003.
[11]	K. Hariharakrishnan and D. Schonfeld, “Fast object tracking using adaptive block matching.” Publish in: IEEE Transactions on Multimedia, Vol. 7(5), pp. 853 – 859, 2005.
[12]	I. E. G. Richardson, “H.264 and MPEG-4 Video Compression: Video Coding for Next-Generation Multimedia.” John Wiley & Sons Ltd, 2003.
[13]	J. Jia, J. Sun, C. Tang, and H. Shum, “Drag-and-Drop Pasting,” In: ACM Trans. Graph. (TOG), Vol. 25(3), pp. 631-637, 2006.
[14]	Z. H. Khan, I.Y. Gu and A. Backhouse, "Robust Visual Object Tracking using Multi-Mode Anisotropic Mean Shift and Particle Filters," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 21 (1) pp. 74-87, 2011.
[15]	C.W. Lin and N.C. Cheng, “Video bsckground inpainting using dynamic texture synthesis,” In Proceedings of 2010 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1559 – 1562, 2010.
[16]	D. G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, Vol. 60(2), pp. 91-110, 1999.
[17]	D.Q. Nguyen, R. Fedkiw and H.W. Jensen, “Physically Based Modeling and   Animation of Fire,” In: SIGGRAPH 2002, Vol. 21(3), Jul. 2002.
[18]	K. Patwardhan, G. Sapiro, M. Bertalmio, "Video Inpainting Under Constrained Camera Motion," IEEE Transactions on Image Processing, Vol. 16(2), pp. 545-553, 2007.
[19]	A. Rav-Acha, Y. Pritch, D. Lischinski and S. Peleg, “Dynamosaics: Video Mosaics with Non-Chronological Time,” In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 58 – 65. San Diego, USA, 2005.
[20]	C Rother, V Kolmogorov and A Blake, ""GrabCut": interactive foreground extraction using iterated graph cuts," ACM Trans. Graph., vol. 23, pp. 309–314, 2004.
[21]	A. Schodl, R. Szeliski, D.H. Salesin, I. Essa, “Video Textures,” In: SIGGRAPH 2000, pp. 489–498, 2000.
[22]	T.K. Shih, N.C. Tang, J.N. Hwang, “Exemplar-based Video Inpainting without Ghost Shadow Artifacts by Maintaining Temporal Continuity” In IEEE Transactions on Circuits and Systems for Video Technology, Vol. 19(3), pp. 347-360, Mar. 2009.
[23]	T.K. Shih, N.C. Tang,, J. Tsai, J.N. Hwang, “Video Motion Interpolation for Special Effect Applications,” accepted by IEEE Transactions on Systems, Man, and Cybernetics --Part C: Applications and Reviews, 2010.
[24]	S. Vicente, V. Kolmogorov, and C. Rother, "Graph cut based image segmentation with connectivity priors," in IEEE Conference on Computer Vision and Pattern Recognition, pp. 23-28 Jun. 2008.
[25]	P. Perez, M. Gangnet and A.Blake, “Poisson Image Editing,” in ACM Transactions on Graphics, Vol. 22(3), Jul., 2003.
[26]	J. Sun, J. Jia, C.-K. Tang, H.-Y. Shum "Poisson matting," in ACM Transactions on Graphics, Vol. 23(3), Aug., 2004.
[27]	L.B. White and B. Boashash, "Cross Spectral Analysis of Non-Stationary Processes", IEEE Transactions on Information Theory, Vol. 36, No. 4, pp. 830-835, July 1990.
[28]	I.W. Selensnick and K. Y. Li, “Video denoising using 2d and 3d dual-tree complex wavelet transforms,” in SPIE Wavelets X, San Diego, CA, August 4-8 2003.
[29]	Y. Matsushita, E. Ofek, X. Tang and H. Y. Shum, “Full-frame video stabilization,” Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2005(CVPR 2005), Vol. 1, pp:50-57, June 2005.
[30]	J. Jia, Tai-Pang Wu, Yu-Wing Tai, and Chi-Keung Tang, “Video Repairing: Inference of Foreground and Background under Severe Occlusion,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June-July 2004, Pages I: 364-371.
[31]	J. Jia, Y. W. Tai, T. P. Wu and C. K. Tang, “Video Repairing Under Variable Illumination Using Cyclic Motions,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 28, no. 5, 2006. 
[32]	K. A. Patwardhan, G. Sapiro, and M. Bertalmio, "Video Inpainting Under Constrained Camera Motion," IEEE Trans. on Image Processing, Feb 2007.
[33]	Y. Wexler, E. Shechtman, M. Irani, “Space-Time Completion of Video,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 29, Issue 3, March 2007 Page(s):463 – 476.
[34]	Y. Zhang, J. Xiao, and M. Shah, “Motion Layer Based Object Removal in Videos,” The Seventh IEEE Workshops on Application of Computer Vision, 2005, pp. 516-521.
[35]	I. Drori, D. Cohen-Or, and H. Yeshurun, “Fragment-based image completion,” ACM Trans. Graphics (SIGGRAPH), vol. 22, San Diego, CA, pp. 303-312, 2003.
[36]	J. Sun, L. Yuan, J. Jia and H. Y. Shum, “Image Completion with Structure Propagation,” in Proc. of ACM SIGGRAPH 2005,Vol. 24 Issue 3 2005 pp.861 – 868.
[37]	A. C. Kokaram and S. J. Godsill, “Joint Detection, Interpolation, Motion and Parameter Estimation for Image Sequences with Missing Data,” in International Conference on Image Processing, 26-29 Oct. 1997, Page(s):191 - 194 vol.2.
[38]	R. Li, B. Zeng, and M. L. Liou, “A New Three-Step Search Algorithm for Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., Vol. 4, No. 4, pp. 438-442, Aug. 1994.
[39]	L.-M. Po, and W.-C. Ma, “A Novel Four-Step Search Algorithm for Fast Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, No. 3, pp. 313-317, Jun. 1996.
[40]	J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, No. 4, pp. 369-377, Aug. 1998.
[41]	V. Vezhnevets and V. Konouchine, “"Grow-Cut" - Interactive Multi-Label N-D Image Segmentation,” Proc. Graphicon. pp. 150–156.