此篇論文最主要的目的是要找出一個執行時間短且不耗費大量記憶體的多區塊切割方法。首先，我們會在影像上先選擇以及畫一些所感興趣之點。然後，建立圖、延伸Boykov 及 Kolmogorov所提出之圖形切割方法，讓每個端點是其他端點的起始(source)與終點(sink)，以及加入一限制條件，來對所選擇之區塊做切割。實驗結果顯示，在同一張影像中相同的切割數量下，本篇論文所提出的方法不僅執行速度快，還能夠有效的切割出所要之區塊。此外，本論文所提出的方法不會因為切割區塊的增加而使執行時間以及記憶體使用量增多。

A unified approach for the interactive multiple region segmentation method based on the graph cuts algorithm is proposed in this thesis. First, select and scribble some different pixels inside the region of interest in an image. Then, create graph once and split the selected regions by means of extending the Boykov and Kolmogorov’s binary max flow/min cut method and letting each terminal be others’ source and sink in a graph. Experiment results show that the proposed method yields accurate segmentation results and the execution time is decreased. Furthermore, the proposed method does not create more than one graph, so the execution time and memory usage of the proposed method are independent of the number of split regions.

[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, 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] M. Chupin, A. Hammers, R.S.N. Liu, O. Colliot, J. Burdett, E. Bardinet, J.S. Duncan, L. Garnero, and L. Lemieux, “Automatic segmentation of the hippocampus and the amygdala driven by hybrid constraints: method and validation,” NeuroImage, vol. 46, no. 3, pp. 749-761, 2009.
[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] A. X. Falcao, F. P. G. Bergo, P. A. V. Miranda, and L. M. Rocha, “Automatic image segmentation by tree pruning,” Journal of Mathematical Imaging and Vision, vol. 29, pp. 141-162, 2007.
[16] A. X. Falcao, J. Stolfi, and R. de Alencar Lotufo, “The image foresting transform:theory, algorithms, and applications,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 1, pp. 19-29, 2004.
[17] M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: active contour models,” International Journal of Computer Vision, vol. 1, no. 4, pp. 321-331, 1988.
[18] T. Chan and L. Vese, “Active contours without edges,” IEEE Transactions on Image Processing, vol. 10, no. 2, pp. 266-277, 2001.
[19] V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,” International Journal of Computer Vision, vol. 22, pp. 61-79, 1997.
[20] 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.
[21] 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.
[22] 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.
[23] 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, 2001.
[24] Y. Li, J. Sun, C. K. Tangm, and H. Y. Shum, “Lazy snapping,” SIGGRAPH Conference, pp. 303-308, 2004.
[25] 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.
[26] 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.
[27] 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.
[28] 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.
[29] 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.
[30] 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.
[31] L. Ford and D. Fulkerson, “Flows in networks,” Princeton University Press, 1962.
[32] J. S. Kim and K. S. Hong, “Color–texture segmentation using unsupervised graph cuts,” Pattern Recognition, vol. 42, no. 5, pp. 735-750, 2009.
[33] 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.
[34] MIT VisTex texture database. (http://vismod.media.mit.edu/vismod/imagery/ VisionTexture/vistex.html).
[35] D. Martin, C. Fowlkes, D. Tal, and J. Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” IEEE International Conference on Computer Vision, vol. 2, pp. 416-423, 2001.