臺灣博碩士論文加值系統

本論文探討並實作了一個基於圖分割演算法的互動式影片分割系
統。近來,基於圖分割演算法的圖像分割、影片分割於電腦圖學與電
腦視覺研究界甚為普遍。然而,絕大多數的關連研究僅僅使用了影片
本身的色彩資訊,作為主要的分割依據。這在前景與背景有部分區域
在色彩上甚為相似的狀況下,容易產生錯誤。而不幸地,這樣的條件
並不罕見,特別是當拍攝對象並非在棚拍等人工環境之下拍攝,而是
以日常場景作為背景之時。因此,在本論文之中,我們提出了除了色
彩之外的依據進行影片分割的演算法。我們觀察到前景的動向與背景
經常是相當不同的,因此,選擇結合色彩以及動向資訊共同進行影片
分割。此外,本系統尚且擴充了原本採用於圖片分割領域的漸進式分
割,使其能夠用於影片分割。最後,我們將本系統的結果與關連研究
進行了比較,以實例證實了本系統的效能確實優於既往研究。

In this thesis, we present an interactive graph cut based video segmenta-
tion system. Recently, graph cut based segmentation tools become prevelant
for image/video segmentation problem. However, most of the previous works
deal with color information only. Such systems could fail under the condition
that there are regions similar in color between foreground and background.
Unfortunately, it is usutally hard to avoid. Especially when the objects are
filmed under a natural environment. To make it more pratical to use, we
propose criterion other than color to conduct the segmentation. Through our
observation, motion is a natural choice, since it is usually the case that fore-
ground and background has different motion pattern. Moreover, we also ex-
tend the Progressive Cut to the temporal-spatial video volume. Experiments
shows that by combining color and motion information, our system outper-
forms the previous works.

中文摘要 i
Abstract iii
1 Introduction 1
1.1 Background 1
1.2 Problem Statement 3
1.3 Thesis Organization 3
2 Related work 5
2.1 Traditional Approaches 5
2.1.1 Chroma Keying 5
2.1.2 Difference Matte 5
2.1.3 Silhouette Tracking 6
2.2 Modern Approaches 6
2.2.1 Interactive approaches in image domain 6
2.2.2 Graph cuts approaches in video domain 7
2.2.3 Video matting 7
2.2.4 Segmentation that handles the occlusion condition 8
2.3 Graph Cuts 8
2.4 Optical Flow 9
3 Graph Cuts 11
3.1 Video Segmentation and Graph Cuts 11
3.2 Problem Statement 12
3.3 Algorithm Summary 12
3.3.1 Local Minimum in Large Moves 12
3.3.2 Encode the Energy Function Specification in Graphs 13
3.4 Implementation Detail 14
4 Video Segmentation with Motion Smoothness 17
4.1 System Overview 17
4.2 Interactive User Interface 18
4.3 Optical Flow Calculation and Refinement 19
4.4 3D Graph Cut Segmentation 20
4.4.1 3D Graph Construction 20
4.4.2 Encode Data Term 20
4.4.3 Encode Color Smoothness Term 21
4.4.4 Encode Temporal Smoothness Term 21
4.4.5 Encode Motion Smoothness Term 22
4.4.6 3D Graph Cut Optimization 22
4.5 Local Refinement by 3D Progressive Cut 23
4.5.1 Some Observation from User Strokes 23
4.5.2 User Term 25
5 Results 27
5.1 Experiment Results 27
5.1.1 Results that Can be Segmented Properly by Color Term Only 27
5.1.2 Results that Better with Motion Smoothness Term 29
5.2 Applications 41
5.3 Limitation 41
5.4 Implementation Details 43
6 Conclusion and Future Work 45
6.1 Conclusion 45
6.2 Future Work 45
Bibliography 47

[1] A. Agarwala, A. Hertzmann, and D. H. Salesin. Keyframe-based tracking for roto-
scoping and animation. ACM Trans. Graph, 23:584–591, 2004.
[2] X. Bai and G. Sapiro. A geodesic framework for fast interactive image and video
segmentation and matting. In ICCV07, pages 1–8, 2007.
[3] A. Blake and M. Isard. Active Contours. Springer-Verlag, 1998.
[4] Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max-flow
algorithms for energy minimization in vision. IEEE Transactions on Pattern Analy-
sis and Machine Intelligence, 26(9):1124–1137, 2004.
[5] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via
graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence,
23(11):1222–1239, 2001.
[6] T. Brox, A. Bruhn, N. Papenberg, and J. Weickert. High accuracy optical flow
estimation based on a theory for warping. In Computer Vision - ECCV 2004, pages
25–36. Springer, 2004.
[7] B.-Y. Chen, K.-Y. Lee, W.-T. Huang, and J.-S. Lin. Capturing intention-based full-
frame video stabilization. Computer Graphics Forum, 27(7):1805–1814, 2008. Pa-
cific Graphics 2008 Conference Proceedings.
[8] Y.-Y. Chuang, A. Agarwala, B. Curless, D. H. Salesin, and R. Szeliski. Video mat-
ting of complex scenes. In SIGGRAPH ’02: Proceedings of the 29th annual confer-
ence on Computer graphics and interactive techniques, pages 243–248, New York,
NY, USA, 2002. ACM.
[9] Y.-Y. Chuang, B. Curless, D. H. Salesin, and R. Szeliski. A bayesian approach to
digital matting. In Proceedings of IEEE CVPR 2001, volume 2, pages 264–271.
IEEE Computer Society, December 2001.
47
[10] M. Gleicher. Image snapping. In Proceedings of SIGGRAPH 95, Computer Graphics
Proceedings, Annual Conference Series, pages 183–190, Aug. 1995.
[11] D. B. Goldman. Computer Graphics Supervisor. Industrial Light & Magic, personal
communication, 2003.
[12] M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models. Interna-
tional Journal of Computer Vision, V1(4):321–331, January 1988.
[13] V. Kolmogorov and R. Zabin. What energy functions can be minimized via graph
cuts? Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(2):147–
159, 2004.
[14] Y. Li, J. Sun, and H.-Y. Shum. Video object cut and paste. ACM Transactions on
Graphics, 24(3):595–600, 2005. (SIGGRAPH 2005 Conference Proceedings).
[15] Y. Li, J. Sun, C.-K. Tang, and H.-Y. Shum. Lazy snapping. ACM Transactions on
Graphics, 23(3):303–308, 2004. (SIGGRAPH 2004 Conference Proceedings).
[16] B. D. Lucas and T. Kanade. An iterative image registration technique with an appli-
cation to stereo vision (ijcai). In Proceedings of the 7th International Joint Confer-
ence on Artificial Intelligence (IJCAI ’81), pages 674–679, April 1981.
[17] Y. Matsushita, E. Ofek, W. Ge, X. Tang, and H.-Y. Shum. Full-frame video stabiliza-
tion with motion inpainting. IEEE Trans. Pattern Anal. Mach. Intell., 28(7):1150–
1163, 2006.
[18] T. Mitsunaga, T. Yokoyama, and T. Totsuka. Autokey: Human assisted key extrac-
tion. In Proceedings of SIGGRAPH 95, Computer Graphics Proceedings, Annual
Conference Series, pages 265–272, Aug. 1995.
[19] E. N. Mortensen and W. A. Barrett. Intelligent scissors for image composition. In
Proceedings of SIGGRAPH 95, Computer Graphics Proceedings, Annual Confer-
ence Series, pages 191–198, Aug. 1995.
[20] D. S. Richard Duda, Peter Hart. Pattern Classification. Wiley Press, 2000.
[21] C. Rother, V. Kolmogorov, and A. Blake. ”grabcut”: interactive foreground ex-
traction using iterated graph cuts. ACM Transactions on Graphics, 23(3):309–314,
2004. (SIGGRAPH 2004 Conference Proceedings).
[22] A. R. Smith and J. F. Blinn. Blue screen matting. In SIGGRAPH ’96: Proceedings
of the 23rd annual conference on Computer graphics and interactive techniques,
pages 259–268, New York, NY, USA, 1996. ACM.
48
[23] C. Wang, Q. Yang, M. Chen, X. Tang, and Z. Ye. Progressive cut. In ACM Multi-
media 2006 Conference Proceedings, pages 251–260, 2006.
[24] J. Wang, P. Bhat, R. A. Colburn, M. Agrawala, and M. F. Cohen. Interactive video
cutout. 24(3):585–594, July 2005.
[25] J. J. Xiao and M. Shah. Motion layer extraction in the presence of occlusion using
graph cuts. IEEE Trans. Pattern Analysis and Machine Intelligence, 27(10):1644–
1659, Oct. 2005.
[26] H. yeung Shum, J. Sun, Y. Li, and C. keung Tang. Pop-up light field: An interac-
tive image-based modeling and rendering system. ACM Transaction of Graphics,
23:143–162, 2004.