||The Motion Inpainting Based on Motion Vectors and Feature Points
||Department of Computer Science and Information Engineering
||Joseph C. Tsai
||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
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
|| J.K. Aggarwal and Q. Cai, “Human Motion Analysis: A Review.” In: IEEE Nonrigid and Articulated Motion Workshop, 1997.
 S. Avidan and A. Shamir, “Seam Carving for Content-Aware Image Resizing,” In ACM Trans. Graph. Vol. 26( 3), Article 10, July 2007.
 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.
 M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, "Image Inpainting," Proceedings of SIGGRAPH 2000, New Orleans, USA, July 2000.
 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.
 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.
 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.
 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.
 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
 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.
 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.
 I. E. G. Richardson, “H.264 and MPEG-4 Video Compression: Video Coding for Next-Generation Multimedia.” John Wiley & Sons Ltd, 2003.
 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.
 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.
 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.
 D. G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, Vol. 60(2), pp. 91-110, 1999.
 D.Q. Nguyen, R. Fedkiw and H.W. Jensen, “Physically Based Modeling and Animation of Fire,” In: SIGGRAPH 2002, Vol. 21(3), Jul. 2002.
 K. Patwardhan, G. Sapiro, M. Bertalmio, "Video Inpainting Under Constrained Camera Motion," IEEE Transactions on Image Processing, Vol. 16(2), pp. 545-553, 2007.
 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.
 C Rother, V Kolmogorov and A Blake, ""GrabCut": interactive foreground extraction using iterated graph cuts," ACM Trans. Graph., vol. 23, pp. 309–314, 2004.
 A. Schodl, R. Szeliski, D.H. Salesin, I. Essa, “Video Textures,” In: SIGGRAPH 2000, pp. 489–498, 2000.
 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.
 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.
 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.
 P. Perez, M. Gangnet and A.Blake, “Poisson Image Editing,” in ACM Transactions on Graphics, Vol. 22(3), Jul., 2003.
 J. Sun, J. Jia, C.-K. Tang, H.-Y. Shum "Poisson matting," in ACM Transactions on Graphics, Vol. 23(3), Aug., 2004.
 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.
 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.
 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.
 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.
 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.
 K. A. Patwardhan, G. Sapiro, and M. Bertalmio, "Video Inpainting Under Constrained Camera Motion," IEEE Trans. on Image Processing, Feb 2007.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 V. Vezhnevets and V. Konouchine, “"Grow-Cut" - Interactive Multi-Label N-D Image Segmentation,” Proc. Graphicon. pp. 150–156.