臺灣博碩士論文加值系統

本論文中，我們基於分割-合併的兩階段，提出一套非監督式階層式資料分群演算法，我們並以影像切割應用為例，具體開發出一套優於現有影像切割技術的新演算法。在資料分割階段，以貝氏循序切割(BSP)演算法進行改良，我們提出一套有效率的資料切分演算法，將影像的像素資料切割成許多像素點顏色平滑變化的區塊; 在合併階段中，我們提出一套以機率為基礎的循序合併方法，對切割出之資料區塊建立階層結構。相較於現有方法多需事先決定分割區塊數目，所提出之方法能一次產生整體階層結構，更有利於後續處理, 如: 物體辨識, 場景分析等。經實驗證實，相較於現有方法，我們所提出之方法不僅能提供更具彈性的影像分割，也能提供更接近人眼視覺的分割成果。而此一技術也能廣泛應用於其他類型的資料分析應用上，並能有效率地處理高維度的巨量資料。

In this thesis, we present an unsupervised hierarchical clustering algorithm based on a split-and-merge scheme. Using image segmentation as an example of the applications, we propose an unsupervised image segmentation algorithm which outperforms the existing algorithms. In the split phase, we propose an efficient partition algorithm, named Just-Noticeable-Difference Bayesian Sequential Partitioning (JND-BSP), to partition image pixels into a few regions, within which the color variations are perceived to be smoothly changing without apparent color differences. In the merge phase, we proposed a Probability Based Sequential Merging algorithm to sequentially construct a hierarchical structure that represents the relative similarity among these partitioned regions. Instead of generating a segmentation result with a fixed number of segments, the new algorithm produces an entire hierarchical representation of the given image in a single run. This hierarchical representation is informative and can be very useful for subsequent processing, like object recognition and scene analysis. To demonstrate the effectiveness and efficiency of our method, we compare our new segmentation algorithm with several existing algorithms. Experiment results show that our new algorithm can not only offers a more flexible way to segment images but also provides segmented results close to human’s visual perception. The proposed algorithm can also be widely used on applications analyzing other types of data, and can be used to analyze Big Data with high dimension efficiently.

Chapter 1. Introduction 1
1.1 Motivations of the Research 1
1.2 Contributions of the Research 3
Chapter 2. Related Works 4
2.1 Graph Based Image Segmentation 4
2.1.1 Normalized Cuts 5
2.1.2 Minimal Spanning Tree Based Method 7
2.2 Clustering Based Image Segmentation 8
Chapter 3. Proposed Method 11
3.1 JND-BSP Based Splitting 12
3.1.1 Bayesian Sequential Partitioning 12
3.1.1.1 Binary Partition 12
3.1.1.2 Partition Score and Sequential Build-up 13
3.1.2 JND-BSP 16
3.1.2.1 JND-Random Walk Model 17
3.1.2.2 The New Formulation for BSP 20
3.1.3 Boundary Relaxation 23
3.2 Probability Based Sequential Merging 26
3.2.1 Model Formulation 26
3.2.2 Sequential Merging 26
Chapter 4. Experimental Results 29
Chapter 5. Conclusions and Future Works 34
Chapter 6. Acknowledgments 35
Chapter 7. Appendix 36
Bibliography 38

[1] B. Peng, L. Zhang, and D. Zhang, “A survey of graph theoretical approaches to image segmentation,” Pattern Recognition, vol. 46, no. 3, pp. 1020-1038, 2013.
[2] L. Lu, H. Jiang and W. H. Wong, “Multivariate Density Estimation by Bayesian Sequential Partitioning,” Journal of the American Statistical Association, 2013 Published Online.
[3] M. Mahy, L. Van Eyckden, and A. Oosterlinck, “Evaluation of uniform color spaces developed after the adoption of CIELAB and CIELUV,” Color Res. Appl., 19(2), 105-121, 1994.
[4] T. Cour, F. Benezit and J. Shi, “Spectral Segmentation with Multiscale Graph Decomposition,” Computer Vision and Pattern Recognition, vol. 2, pp. 1124-1131, 2005.
[5] Pedro F. Felzenszwalb and Daniel P. Huttenlocher, “Efficient Graph-Based Image Segmentation,” International Journal of Computer Vision, Volume 59, Number 2, September 2004.
[6] D. Comaniciu and P. Meer, “Mean shift: a robust approach toward feature space analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, NO. 5, pp. 603-619, 2002.
[7] U. v. Luxburg, “A tutorial on spectral clustering,” Statistics and Computing, vol. 17, no. 4, pp. 395-416, 2007.
[8] P. Arbelaez, M. Maire, C. Fowlkes and J. Malik, “Contour Detection and Hierarchical Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 5, pp. 898-916, 2011.
[9] P. Meer and B. Georgescu, “Edge detection with embedded confidence,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 12, pp. 1351-1365, 2001.
[10] C. Christoudias, B. Georgescu and P. Meer, “Synergism in Low Level Vision,” Proc. Int',l Conf. Pattern Recognition, vol. 4, pp. 150-156, 2002.
[11] J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, 2000.
[12] R. Franzen, “Kodak Lossless True Color Image Suite.” http://r0k.us/graphics/kodak/
[13] Heller, Katherine A., and Zoubin Ghahramani. "Bayesian hierarchical clustering," Proceedings of the 22nd International Conference on Machine learning, ACM, 2005.
[14] Vantaram, Sreenath Rao, and Eli Saber. “Survey of contemporary trends in color image segmentation,” Journal of Electronic Imaging 21.4 (2012): 040901-1.
[15] http://www.cs.unc.edu/~lazebnik/research/spring08/lec21_segmentation.ppt
[16] http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/TUZEL1/MeanShift.pdf
[17] http://www.cis.upenn.edu/~jshi/software/
[18] http://cs.brown.edu/~pff/segment/
[19] Hao-Wei Yeh, Chen-Yu Tseng, Tung-Yu Wu, and Sheng-Jyh Wang, “Unsupervised Hierarchical Image Segmentation Based on Bayesian Sequential Partitioning”, Proceedings of IEEE International Conference on Image Processing, Sep., 2015.