本篇文章實現了以graph cuts為基礎的一次性快速多區塊影像分割方法，文章中介紹了兩個的方法，一個是高效能的互動式多區塊影像分割方法，而另一個則是延伸此互動式方法的一個全自動式多區塊影像分割方法。在本篇互動式方法執行過程中，首先需要使用者對感興趣的部分進行標記，接著演算法會建立擁有多個端點的graph，並透過Boykov和Kolmogorov的最大流/最小割的方法和每個端點都可以是其他端點的source或是sink的概念來解決問題。至於全自動式的分割方法則介紹一個可以自動選擇種子點來取代使用者所標記的像素點的方法。實驗結果證明本篇的互動式分割方法擁有正確的分割結果，而且因為此方法使用一個graph來進行一次性的分割，所以執行時間和使用的記憶體比起其他使用graph cuts的多區塊分割方法有著顯著的提升。此外，實驗結果也證明本篇的全自動式分割方法在執行時間上繼承了本篇互動式分割方法的速度，可以迅速的自動分割影像，而在一些影像上面有著不錯的分割結果。

In this paper, we proposed the disposable fast multiple region image segmentation method based on graph cuts. Two methods are introduced in this paper. One is an efficient interactive multiple region image segmentation method, the other is a fully automatic multiple region image segmentation method that extends the interactive method. In the implementation of the interactive approach, users are required to label parts of interest first. Then, the algorithm builds the graph with multiple terminals and solves the problem through the maximum flow/minimum cut method of Boykov and Kolmogorov and the notion that each terminal can be either the source of the terminal or the sink in a graph. As for the fully automatic segmentation method, a method of automatically selecting seeds to replace pixels labeled by the user is introduced. Experimental results show that the interactive segmentation method has the correct segmentation results. Also, since this method uses a graph for one-time segmentation, execution time and memory usage are significantly improved compared to other graph cuts based multiple region segmentation methods. In addition, the experimental results also show that the fully automatic segmentation method inherits the speed of the interactive segmentation method in the execution time, and can segment the image automatically and quickly. Some images have good segmentation results.

[1] Y. B. Chen, O. T. C. Chen, H. T. Chang, and J. T. Chien, “An automatic medical-assistance diagnosis system applicable on x-ray images,” IEEE MWCAS, vol. 2, pp. 910-914, 2001.
[2] Y. B. Chen and O. T. C. Chen, “Semi-automatic image segmentation using dynamic direction prediction,” IEEE ICASSP, vol. 4, pp. 3369-3372, 2002.
[3] Z. Salah, D. Bartz, F. Dammann, E. Schwaderer, M. Maassen, and W. Strasser, “A fast and accurate approach for the segmentation of the paranasal sinus,” Workshop Bildverarbeitung, pp. 93-97, Springer, 2005.
[4] M. Atkins and B. Mackiewich, “Fully automatic segmentation of the brain in MRI,” IEEE Trans. Med. Imag., vol. 17, no. 1, pp. 98-107, 1998.
[5] G. B. Aboutanos, J. Nikanne, N. Watkins, and B. M. Dawant. “Model creation and deformation for the automatic segmentation of the brain in MR images,” IEEE Trans. Biomedical Engineering, vol. 46, no. 11, pp. 1346-1356, 1999.
[6] Z. Yue, A. Goshtasby, and L. V. Ackerman, “Automatic detection of rib borders in chest radiographs,” IEEE Trans. Med. Imag., vol. 14, no. 3, pp. 525-536, 1995.
[7] T. F. Cootes, D. Cooper, C. J. Taylor, and J. Graham, “Active shape models - Their training and application,” Computer Vision and Image Understanding, vol. 61, no. 1, pp. 38-59, 1995.
[8] T. F. Cootes, G. J. Edwards, and C. J. Taylor., Active appearance models, Proc. European Conference on Computer Vision, (H. Burkhardt & B. Neumann Ed.s), Springer, vol. 2, pp. 484-498, 1998.
[9] Chanho Jung, and Changick Kim, “A Unified Spectral-Domain Approach for Saliency Detection and Its Application to Automatic Object Segmentation,” IEEE Transactions on Image Processing, vol. 21, no. 3, pp. 1272-1283, 2012.
[10] A. X. Falcao and F. P. G. Bergo, “Interactive volume segmentation with differential image foresting transforms,” IEEE Transactions on Medical Imaging, vol. 23, no. 9, pp. 1100-1108, 2004.
[11] L. Grady, T. Schiwietz, S. Aharon, and R. Westermann, “Random walks for interactive alpha-matting,” Proceedings of the Visualization Imaging and Image Processing (VIIP), pp. 423-429, 2005.
[12] F. Wang, C. Zhang, H. C. Shen, and J. Wang, “Semi-supervised classification using linear neighborhood propagation,” IEEE Computer Vision and Pattern Recognition, vol. 1, pp. 160-167, 2006.
[13] L. Grady, “Random walks for image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, pp. 1768-1783, 2006.
[14] A. Protiere, and G. Sapiro, “Interactive image segmentation via adaptive weighted distances,” IEEE Transactions on Image Processing, vol. 16, no. 4, pp. 1046-1057, 2007.
[15] M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, vol. 1, no. 4, pp. 321-331, 1988.
[16] T. Chan and L. Vese, “Active contours without edges,” IEEE Transactions on Image Processing, vol. 10, no. 2, pp. 266-277, 2001.
[17] V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,” International Journal of Computer Vision, vol. 22, pp. 61-79, 1997.
[18] D. M. Greig, B. T. Porteous, and A. H. Seheult, “Exact maximum a posteriori estimation for binary images,” Journal of the Royal Statistical Society Series B, vol. 51, no. 2, pp. 271-279, 1989.
[19] Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239, 2001.
[20] Y. Boykov and V. Kolmogorov, “An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, pp. 1124-1137, 2004.
[21] Y. Boykov and M. P. Jolly, “Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images,” International Conference on Computer Vision, pp. 105-112, Vancouver, BC, Canada, 2001.
[22] Y. Li, J. Sun, C. K. Tangm, and H. Y. Shum, “Lazy snapping,” SIGGRAPH Conference, pp. 303-308, New York, NY, USA, 2004.
[23] E. Bae and X. C. Tai, “Graph cuts for the multiphase mumford–Shah model using piecewise constant level set methods,” UCLA, Applied Mathematics, CAM-Report-08-36, vol. 3, no. 9, pp. 121-135, 2008.
[24] K. Ni, B. W. Hong, S. Soatto, and T. Chan, “Unsupervised multiphase segmentation: A recursive approach,” Computer Vision and Image Understanding, vol. 113, pp. 502-510, 2009.
[25] L. A. Vese and T. F. Chan, ”A multiphase level set framework for image segmentation using the mumford and shah model,” International Journal of Computer Vision, vol. 50, no. 3, pp. 271-293, 2002.
[26] J. S. Kim and K. S. Hong, “A new graph cut-based multiple active contour algorithm without initial contours and seed points,” Machine Vision and Applications, vol. 19, no. 3, pp. 181-193, 2008.
[27] H. Ishikawa, “Exact optimization for markov random fields with convex priors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, 2003.
[28] W. Tao, F. Chang, L. Liu, H. Jin, and T. Wang, “Interactively multiphase image segmentation based on variational formulation and graph cuts,” Pattern Recognition, vol. 43, no. 10, pp. 3208-3218, 2010.
[29] Zhi Liu, Ran Shi, Liquan Shen, Yinzhu Xue, King Ngi Ngan, and Zhaoyang Zhang, “Unsupervised Salient Object Segmentation Based on Kernel Density Estimation and Two-Phase Graph Cut,” IEEE Transactions on Multimedia, vol. 14, no. 4, pp. 1275-1289, 2012
[30] Huazhu Fu, Xiaochun Cao, Zhuowen Tu, and Dongdai Lin, “Symmetry Constraint for Foreground Extraction,” IEEE Transactions on Cybernetics, vol. 44, no. 5, pp. 644-654, 2014
[31] Chanho Jung, and Changick Kim, ” A Unified Spectral-Domain Approach for Saliency Detection and Its Application to Automatic Object Segmentation,” Transactions on Image Processing, vol. 21, no. 3, pp. 1272-1283, 2012
[32] Quoc Bao Truong and Byung Ryong Lee, “Automatic Multi-thresholds Selection for Image Segmentation based on Evolutionary Approach,” International Journal of Control, Automation, and Systems, pp.834-844, 2013.
[33] X. Zhang, Y. Shan, W. Wei and Z. Zhu, “An Image Segmentation Method Based on Improved Watershed Algorithm,” Computational and Information Sciences, pp. 258-261, 2010.
[34] P. Li, S. Wang, J. Jing and Z. Zhu, “The segmentation in textile printing image based on mean shift,” In Proc. Computer-Aided Industrial Design and Conceptual Design, pp. 1528-1532, 2009.
[35] L. Ford and D. Fulkerson, “Flows in networks,” Princeton University Press, 1962.
[36] V. Kolmogorov and R. Zabih, “What energy functions can be minimized via graph cuts,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 147-159, 2004.
[37] Berkeley image segmentation database (https://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ BSDS300/html/dataset/images.html)