臺灣博碩士論文加值系統

　　近年來，如何能夠透過使用者的互動，方便及快速地將物件從靜態影像中萃取出來，是個非常重要的課題。較典型的影像編輯工具，例如：Photoshop的魔術棒，就是根據使用者所給定的種子點，長出一個和種子點顏色相似的區域，但使用者往往需要給定很多種子點，才能取出其想要的物件。
　　
　　故在本論文中，我們提出一個互動式物件萃取的方法，讓使用者能夠很方便及快速地將想要的物件從圖片中萃取出來，或將不想要的物件去掉。有了這個方便的影像編輯工具，使用者只需要在圖片上指定少量的前景和背景之區域，我們的系統便會根據這些資訊，將使用者所想要的物件萃取出來。假設使用者對於結果不滿意，他可以在圖片上指定更多的資訊，以便我們的系統能夠更正確地萃取出物件。因此，這個工具最重要的就是當使用者指定好前景與背景的區域後，結果必須即時地顯示在螢幕上。為了達到此需求，我們使用分水嶺演算法將影像切割成若干個區塊，如此便可大大地降低資料量，而當使用者指定前/背景的區塊後，我們會將其它的區塊儲在hierarchical queues中，在往後的處理中，這些區塊將會一一被分類成前景或背景。藉由這分類後的區塊，物件即可很容易地被萃取出來。

　Last decade, how to extract an object conveniently and fast with user interaction is a very important research topic. A classical image editing tool, e.g. Photoshop Magic Wand, can grow a region containing a set of pixels which are all similar to the user assigned seed in color information. Using this tool, the user usually needs to assign many seeds so that he can extract the target object.
　　
　Therefore, we propose an interactive object extraction algorithm in this thesis. It helps the user extracting or removing the target object more conveniently and faster. With this convenient image editing tool, the user only needs to mark a few foreground and background parts on the image. Then, our system will extract the target object according the user input information. Assume the user is not satisfied with the result, more information can be given so that our system can extract the object more accurately. Therefore, the most important part of this tool is that the result must be shown on the screen in real-time once the user marks foreground and background parts. In order to achieve this requirement, we perform the watershed algorithm to segment the image into several regions. The data are therefore decreased. After the user marks the foreground and background regions, the remaining regions are stored in the hierarchical queues. In the later processing, these regions will be classified into foreground or background regions. With these classified regions, the object can be extracted easily.

摘要　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　i
Abstract　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ii
誌謝　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　iv
Contents　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　v
Table List 　　　　　　　　　　　　　　　　　　　　　　　　　　　　vii
Figure List　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　vii
CHAPTER 1 INTRODUCTION　　　　　　　　　　　　　　　　　　　　　　　　　　　1
1.1 Background　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1
1.2 Motivation　　　　　　　　　　　　　　　　　　　　　　　　　　　　　3
1.3 Thesis Organization　　　　　　　　　　　　　　　　　　　　　　　　　3
CHAPTER 2 RELATED WORKS　　　　　　　　　　　　　　　　　　　　　　　　　　　4
2.1 Boundary-based Methods　　　　　　　　　　　　　　　　　　　　　　　4
2.2 Region-based Methods　　　　　　　　　　　　　　　　　　　　　　　　6
CHAPTER 3 PROPOSED OBJECT EXTRACTION ALGORITHM　　　　　　　　　　　　　　　　9
3.1 System Flow　　　　　　　　　　　　　　　　　　　　　　　　　　　　　9
3.2 Pre-processing　　　　　　　　　　　　　　　　　　　　　　　　　　　11
3.2.1 Noise Reduction　　　　　　　　　　　　　　　　　　　　　　　　　　11
3.2.2 Color Space Transformation　　　　　　　　　　　　　　　　　　　　　14
3.2.3 Morphological Gradient　　　　　　　　　　　　　　　　　　　　　　　15
3.2.4 Image Segmentation Using Watershed Algorithm　　　　　　　　　　　　17
3.3 Input Foreground and Background Seeds　　　　　　　　　　　　　　　19
3.4 Foreground and Background Regions Classification　　　　　　　　　　20
3.5 User Interface Design　　　　　　　　　　　　　　　　　　　　　　　31
CHAPTER 4 EXPERIMENTAL RESULTS　　　　　　　　　　　　　　　　　　　　　　　33
CHAPTER 5 THE IMPLEMENTATION OF OUR PROPOSED ALGORITHM ON EMBEDDED SYSTEM　　44
5.1 Introduction to Our Embedded System　　　　　　　　　　　　　　　　44
5.2 Foreground and Background Pixels Classification 　　　　　　45
5.3 The Experimental Results on Embedded System 　　　　　　　　　　　48
CHAPTER 6 CONCLUSION AND FUTURE WORK 　　　　　　　　　　　　　　　　　　　　51
REFERENCES 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　52

[1]Mortensen, E. N., Barrett, W. A., “Toboggan-based intelligent scissors with a four parameter edge model.” In Proceedings of CVPR’99. (1999)

[2]Carsten Rother, Vladimir Kolmogorov, Andrew Blake, “"GrabCut": interactive foreground extraction using iterated graph cuts.” ACM Transactions on Graphics (TOG), Volume 23 Issue 3 (2004)

[3]Yin Li, Jian Sun, Chi-Keung Tang, Heung-Yeung Shum, “Lazy snapping.” ACM Transactions on Graphics (TOG), Volume 23 Issue 3 (2004)

[4]Jhing-Fa Wang, Han-Jen Hsu, Shang-Chia Liao, “A novel framework for object removal from digital photograph.” International Conference on Image Processing. (2005)

[5]Gleicher, M., “Image snapping.” In Proceedings of ACM SIGGRAPH’95. (1995)

[6]Perez, P., Blake, A., Gangent, M., “Jetstream: Probabilistic contour extraction with particles.” In Proceedings of ICCV 2001. (2001)

[7]林岡品, “彩色影像的半自動切割方法”, 中山大學 (2002)

[8]Rafael C. Gonzalez, Richard E. Woods., “Digital Image Processing.” Prentice-Hall, Inc. (2002)

[9]Hai Gao, Wan-Chi Siu, Chao-Huan Hou, “Improved Techniques for Automatic Image Segmentation.” Circuits and Systems for Video Technology, IEEE Trans. on Volume 11, Issue 12, pp. 1273 - 1280 (2001)

[10]R. S. Berns, “Principles of Color Technology”, 3rd ed. New York: Wiley (2000)

[11]D. Ballard and C. Brown, “Computer Vision.” Englewood Cliffs, NJ: Prentice-Hall (1982)

[12]X. Wu, “Adaptive split-and merge segmentation based on piecewise least-square approximation.” IEEE Trans. Pattern Analysis Machine Intelligence Vol. 15, Page 808-815 (1993)

[13]Meyer, F., “Color Image Segmentation.” Image Processing and its Applications, International Conference 303 - 306 (1992)

[14]Drori, D. Cohen-Or, H. Yeshurun, “Fragment-based image completion.” in ACM Trans. Graphics (TOG), vol.22, no. 3, pp. 303-312 (2003)

[15]Jia, and C. K. Tang, “Inference of segmented color and texture description by tensor voting.” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, June (2004)

[16]Jian Sun, Jiaya Jia, Chi-Keung Tang, Heung-Yeung Shum, “Poisson matting.” ACM Transactions on Graphics (TOG), Volume 23 Issue 3 (2004)

[17]J. M. Kasson, W. Plouffe, “An Analysis of Selected Computer Interchange Color Spaces.” ACM Transactions on Graphics, Vol. 11, No. 4, October, Pages 373-405 (1992)

[18]Luc Vincent, Pierre Soille, “Watersheds in Digitan Spaces: An Efficient Algorithm Based on Immersion Simulations.” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, June (1991)

[19]Yung-Yu Chuang, Brian Curless, David Salesin, Richard Szeliski, “A Bayesian Approach to Digital Matting.” IEEE Computer Society International Conference on CVPR (2001)