在影片中物件的行為是可以被更換的，亦即所謂的影片重製，雖然這項研究議題或許會引發一些較為負面的影響像是刻意將影片造假等，但是將這種技術應用於好的地方是會帶來相當大的貢獻，就有如成功的降低電影特效製造的成本或是讓人們方便編輯自己美好的回憶。而為了達到上述的目的，則必須實做出像是物件追蹤、動量估測、影像影片修補、動作分析與植入等技術。
在本文中，首先我們提出了一個經改良後的影像修補方法。這個影像修補方法可以適用於擁有各種不同特性的影片，像是屬於靜態背景的影片、內含有動態背景及物件有自身運動模式的等片等，均可使用我們提出的方法進行物件移除以及影像修補，修補完的結果亦是相當完善。其次，我們提出了一個全新的物件再造技術。這個技術納入了像是Mean Shift Segmentation顏色分群演算法、四步搜尋及十字菱形六角形搜尋等動量估測的方法以及在這次計畫中我們自己設計的動作分析與動作植入演算法。首先我們使用Mean Shift Segmentation將影片中的色彩做分群，以利統計出背景與物件各自得色彩分佈資訊，接著我們除了使用四步搜尋及十字菱形六角形搜尋演算法分別針對背景與物件實測出其內含的動量資訊以用於動作分析與動作植入程序，也使用了細化演算法來取得物件的骨架，並以此骨架為基本模組來推測出物件的新動作。在推出物件的新動作後，配合透過我們提出的影像修補方法所產生出的影片背景圖即可達成所謂影片重製的目標。

The behavior of people in a video can be altered. In order to change the content of video, issues such as object tracking, motion interpolation, video inpainting, and video layer fusing need to be implemented.
In this dissertation, at first we extend an exemplar-based image inpainting algorithm by incorporating an improved patch matching strategy for video inpainting. The proposed new video inpainting algorithm produces very few “ghost shadows”, which were produced by most image inpainting algorithms directly applied on video. Secondly, we propose a novel motion interpolation algorithm by using the mean-shift segmentation and motion analysis technique. Mean shift segmentation is frequently used to extract objects from video according to its efficiency and robustness of non-rigid object tracking. For diminishing the computational complexity in motion estimation and object tracking process, several efficient block matching algorithms was used. In the motion analysis procedure, the stick figure of object obtained by thinning process is considered as guidance to gather the statistics of motion information. The model of new behavior of object is produced by motion analysis and used as an input to our motion interpolation procedure. In conclusion, a new video with different plots can be generated after the new object and corresponding background information are produced by our motion interpolation procedure and video inpainting technique separately.

List of Figure	II
List of Table	V
Chapter 1 Introduction	1
1. 1. Motivation	1
1. 2 Overview of Inpainting	2
1. 3. Organization of this Dissertation	4
Chapter 2 Related Works	5
2. 1 Object Tracking and Motion Estimation	5
2. 2 Inpainting Techniques	7
Chapter 3 Proposed Methodologies	13
3. 1 Object Tracking and Segmentation	13
3. 2 Image Inpainting Methods	19
3. 3 Video Inpainting Without Ghost Shadow	31
3. 4 Video Falsifying	47
Chapter 4 Experimental Results and Analysis	65
4. 1 Results of Image Inpainting	65
4. 2 Results of Video Inpainting	70
4. 3 Examples of Video Falsifying	75
4. 4 Comparisons and Analysis	77
Chapter 5 Conclusion and Future Work	80
5.1 Conclusion	80
5.2	Future work	81
Bibliography	82

List of Figure
Figure 1. Object tracking and segmentation	5
Figure 2. A Video from Video Game and the Motion Map (courtesy of Nintendo)	6
Figure 3. Image Inpainting Process	7
Figure 4. Color segmentation	15
Figure 5. Feature space analysis	16
Figure 6 Object tracking and segmentation	17
Figure 7. Algorithm of Object Tracking	18
Figure 8. Using Mean Shift for Object Tracking	19
Figure 9. Exemplar-based Image Inpainting	20
Figure 10 An Example of Producing Edge Map	22
Figure 11. Algorithm of modified exemplar-based inpainting	26
Figure 12. Inpainting of Stationary Video (courtesy of Benesse Taiwan Inc.)	27
Figure 13. Result of Image Inpainting	28
Figure 14. Result of Image Inpainting	29
Figure 15. Result of video Inpainting	30
Figure 16. A Video from Video Game and the Motion Map (courtesy of Nintendo)	34
Figure 17. Four Step Search	37
Figure 18 An Original Frame and its Edge Map	38
Figure 19. Motion Map after Step 1	40
Figure 20. Motion Map after Steps 2 and 3	41
Figure 21 Motion Map after Step 3	42
Figure 22 Separation of Holes and Completed Holes in Consecutive Video Frames	44
Figure 23 Video Falsifying (In the same video, speed of the two runners in the red boxes are changed. The rest are intact.)	48
Figure 24. Procedure of Video Falsifying	50
Figure 25. Examples of Motion Segmentation	52
Figure 26. Example of Motion Interpolation	53
Figure 27. Patch Selection in 3D Video Inpainting	54
Figure 28. Stick Figure and Contour of a Runner	55
Figure 29. Normalization of Target Objects	56
Figure 30 Stick figure and Contour of a Runner	56
Figure 31. Algorithm of stick figure referencing	57
Figure 32 Interpolated Stick Figure	58
Figure 33. Stick Figures for Patch Assertion	59
Figure 34. Algorithm of Patch assertion	60
Figure 35. Searching for Motion Vectors	61
Figure 36. Motion Vectors of Patches on Sticks	62
Figure 37. Algorithm of Motion Interpolation	63
Figure 38 Motion Completion via Inpainting	64
Figure 39. Result of Image Inpainting – Video Game	66
Figure 40. Result of Image Inpainting – Eng. Bldg.	67
Figure 41. Results of Image Inpainting – Crowed	68
Figure 42. Results of Image Inpainting – Jump	69
Figure 43 Video Inpainting under Different Camera Motion	74
Figure 44 Examples of Video Falsifying	76

List of Table
TABLE I A Comparison of Existing Methods with Our Newly Proposed Mechanism	79

[1]	M. Ahmed, R. Ward, "A Rotation Invariant Rule-based Thinning Algorithm for Character Recognition," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, pp.1672-1678, Issue 12, Dec. 2002.
[2]	R. Bornard, E. Lecan, L. Laborelli, J. H. Chenot, "Missing Data Correction in Still Images and Image Sequences", ACM Multimedia’02, Juan-les-Pins, France, December 1-6 2002.
[3]	R. V. Babu, P. Perez, P. Bouthemy, "Robust tracking with motion estimation and kernel-based color modeling," IEEE International Conference on Image Processing, 2005. ICIP 2005., Vol. 1, pp.717-720, 11-14 ,Sept. 2005. 
[4]	A. Criminisi, P. Perez and K. Toyama, "Region Filling and Object Removal by Exemplar-Based Image Inpainting," IEEE Trans. on Image Processing, vol. 13, Sept. 2004, pp. 1200-1212. 
[5]	A. Criminisi, P. Perez, K. Toyama, "Object removal by exemplar-based inpainting", Proceedings of 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 2  18-20 June 2003 pp.II-721 - II-728
[6]	C. H. Cheung, L. M. Po, "Novel cross-diamond-hexagonal search algorithms for fast block motion estimation,"  IEEE Transactions on Multimedia , Vol. 7,  Issue 1, pp. 16-22, Feb. 2005
[7]	R. T. Collins, "Mean-shift blob tracking through scale space," Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 2, pp.234-240 18-20, June 2003. 
[8]	D. Comaniciu and P. Meer, "Mean Shift: A Robust Approach toward Feature Space Analysis," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 24, May 2002, pp. 603 - 619 
[9]	D. Comaniciu, V. Ramesh, P. Meer, "Real-time tracking of non-rigid objects using mean shift," IEEE Conference on Computer Vision and Pattern Recognition, 2000. Proceedings., Vol. 2, pp.142-149, 13-15 June 2000 
[10]	T. F. Chan, J. Shen, "Nontexture Inpainting by Curvature-Driven Diffusions", Journal of Visual Communication and Image Representation, Vol. 12 2001  pp.436-449 
[11]	T. F. Chan, J. Shen, "Mathematical Models for Local Nontexture Inpaintings," SIAM: Journal on Applied Mathematics, 62(3), 2002, pp. 1019-1043.
[12]	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. 
[13]	K. Hariharakrishnan and D. Schonfeld, "Fast Object Tracking Using Adaptive Block Matching," IEEE Trans. on Multimedia, Vol. 7, Oct. 2005, pp. 853-859.
[14]	J. Hays, Alexei A. Efros, "Scene Completion Using Millions of Photographs," ACM Trans. on Graphics (SIGGRAPH 2007), Vol. 26, No. 3, August 2007.
[15]	J. Jia, T. P. Wu, Y. W. Tai, and C. K. 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. 
[16]	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, May 2006, pp. 832-839
[17]	Y. T. Jia, S. M. Hu, R. R. Martin, "Video completion using tracking and fragment merging," in Pacific Graphics 2005, Visual Computing, Vol. 21: 601–610, Sept. 2005, pp. 
[18]	C. Kim and J. N. Hwang, "Video Object Extraction for Object-Oriented Applications," Journal of VLSI Signal Processing - Systems for Signal, Image, and Video Technology, Vol. 29(1/2):7-22, Aug. 2001.
[19]	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, Vol.2, Oct. 1997, pp. 191 - 194. 
[20]	V. Kwatra, A. Schodl, I. Essa, Greg Turk, Aaron Bobick, "Graphcut Textures: Image and Video Synthesis Using Graph Cuts," ACM SIGGRAPH 2003. 
[21]	D. Liang, Qingming Huang, Shuqiang Jiang, Hongxun Yao , Wen Gao, "Mean-Shift Blob Tracking with Adaptive Feature Selection and Scale Adaptation," IEEE International Conference on Image Processing, 2007, ICIP'07., Vol. 3, pp.369-372, Sept. 16 2007-Oct. 19 2007
[22]	F. Nielsen, R. Nock, "ClickRemoval: interactive pinpoint image object removal", in Proc. of the 13th annual ACM international conference on Multimedia 2005, pp.315 – 318.
[23]	M. M. Oliveira, B. Bowen, R. McKenna, Y. S. Chang, "Fast Digital Image Inpainting", International Conference on Visualization, Imaging and Image Processing (VIIP 2001) , 2001 pp. 261-266
[24]	K. A. Patwardhan and G. Sapiro, "Projection Based Image and Video Inpainting Using Wavelets," in Proceedings: 2003 International Conference on Image Processing, (ICIP’03), 2003, pp. 857-860.
[25]	K. A. Patwardhan, G. Sapiro, and M. Bertalmio, "Video Inpainting of Occluding and Occluded Objects," in The 2005 IEEE International Conference on Image Processing, Vol. 2, Sept. 2005, pp. 69-72.
[26]	K. A. Patwardhan, G. Sapiro, and M. Bertalmío, "Video Inpainting Under Constrained Camera Motion," IEEE Trans. on Image Processing, Vol. 16, Feb. 2007, pp. 545-553.
[27]	L. M. Po and W. C. Ma, "A Novel Four-step Search Algorithm for Fast Block Motion Estimation," IEEE Trans. on Video Technology, Vol. 6, Jun. 1996, pp. 313-317.
[28]	T. K. Shih, N. C. Tang, W. S. Yeh, T. J. Chen, and W. Lee, "Video Inpainting and Implant via Diversified Temporal Continuations," in ACM Multimedia Conference 2006, Oct. 2006, pp. 133-136.
[29]	T. K. Shih, N. C. Tang, and J. N. Hwang, "Ghost Shadow Removal in Multi-Layered Video Inpainting," in Proc. of the IEEE 2007 International Conference on Multimedia & Expo (ICME 2007), July 2007, pp. 1471-1474
[30]	J. Sun, L. Yuan, J. Jia and H. Y. Shum, "Image Completion with Structure Propagation," in Proc. of ACM SIGGRAPH 2005, Vol. 24, 2005, pp.861 – 868.
[31]	T. Wang, Irene Y.H. Gu, Andrew Backhouse, Pengfei Shi, "Moving Object Tracking from Videos Based on Enhanced Space-Time-Range Mean Shift and Motion Consistency," IEEE International Conference on Multimedia and Expo, 2007, pp.2002-2005, 2-5 July 2007
[32]	Y. Wexler, E. Shechtman, M. Irani, "Space-Time Completion of Video," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 29, Mar. 2007, pp. 463 – 476. 
[33]	A. Yilmaz, "Object Tracking by Asymmetric Kernel Mean Shift with Automatic Scale and Orientation Selection," IEEE Conference on Computer Vision and Pattern Recognition, 2007, CVPR'07., pp.1-6, 17-22 June 20 
[34]	H. Yamauchi, J. Haber and H. P. Seidel, "Image restoration using multiresolution texture synthesis and image inpainting", Computer Graphics International, 2003  pp.108-113
[35]	Y. Zhang, J. Xiao, and M. Shah, "Motion Layer Based Object Removal in Videos," in The Seventh IEEE Workshops on Application of Computer