淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0701201313392300
中文論文名稱 以動量與特徵點為基礎的動態修補演算法
英文論文名稱 The Motion Inpainting Based on Motion Vectors and Feature Points
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 101
學期 1
出版年 102
研究生中文姓名 蔡程緯
研究生英文姓名 Joseph C. Tsai
學號 897410220
學位類別 博士
語文別 英文
口試日期 2012-12-24
論文頁數 70頁
口試委員 指導教授-顏淑惠
委員-趙榮耀
委員-施國琛
委員-許輝煌
委員-顏淑惠
委員-洪啟舜
中文關鍵字 影片修補  影片製作  動作分析  動態修補 
英文關鍵字 Video Inpainting  Video Production  Motion Analysis  Motion Inpainting 
學科別分類 學科別應用科學資訊工程
中文摘要 圖像以及影片修補的技術已經被很廣泛的應用在日常生活中。在過去幾年中,影片修補可以針對攝影機無移動、有移動的幾乎靜止的背景進行物件的取出。然而,要從動態的背景(如煙霧、火焰以及河流)移除物件則是相當困難的研究。利用現有的影像修補演算法進行處理的話,往往會導致動態結構不連續的問題產生。因此在本研究中,我提出一個全新的修補演算法來解決動態結構不連續的問題。我使用一套不同於以往修補演算法的搜尋區塊的方法,結合邊緣、色彩以及動量的資訊進行區塊的尋找,再透過找出最小能量的隙縫進行區塊影片的時間延長,藉此將找出的區塊時間可以與原始影像相同,最後再利用圖片切割以及泊松方程進行區塊的貼入。除了提出這個演算法之外,我還提出一個方法進行修補結果的判斷,讓使用者可以知道修補的效果。我的這個技術可以利用在一些特效的製作以及影片的後置。
英文摘要 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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-01-16公開。
  • 同意授權瀏覽/列印電子全文服務,於2016-01-16起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信