以統計直方圖為基礎的K-Means分群法:應用於影像分割上

Statistical Histogram-Based K-Means Clustering for Image Segmentation

黃峙瑋(Chih-Wei Huang)

指導教授 ： 許巍嚴 ； 張怡秋

國立中正大學/管理學院/資訊管理學系/碩士(2013年)

摘要

由於使用K-means分群法執行圖片分割時，其運算速度效能不佳。因此，本研究提出一創新的以統計直方圖為基礎的K-means分群法來增加執行效能，並且預期達到與K-means分群法一樣的效果。此方法先使用統計直方圖來獲得圖片像素值的離散機率密度函數，以同像素的概念來做權重分割。如此，將統計直方圖和K-means分群法兩者結合在一起，以改進原始K-means分群法遭遇圖片像素太大或分群數過多時拖慢演算速度的缺點。此外，以大津法初始我們改良的K-means分群法，並且以多階的方式實現四值化分割。接著，以加州大學柏克萊分校電資學院(UC Berkeley EECS)的圖片集，執行多值化的分割，並評估原始K-means分群法與我們所提出方法分割的結果與效能。結果於實驗中以統計直方圖為基礎的K-means分群法在執行效能上顯著地比原始K-mean分群法快十倍以上。

關鍵字

K-means分群法 ； 直方圖 ； 影像分割

並列摘要

When K-means cluster is used for image segmentation, it is very time consuming. In this preliminary study, we proposed a novel statistical histogram-based K-means clustering to increase the computational performance and to achieve the same segmented results as K-means clustering. The proposed method uses the statistical histogram to obtain probability density function of pixels of a figure and segment with weighting for the same intensity. We combine histogram and K-means clustering together to improve the shortcoming of high computational cost for K-means clustering. In addition, the histogram-based K-means clustering is initialized by means of Otsu’ method and, it achieves the four-level segmentation with a multi-level approach. Finally, the images captured from UC Berkeley EECS are used for the multi-level segmentation and the evaluation of results and performance. The results indicate that the proposed method is significantly faster than K-means clustering by more than ten times.

並列關鍵字

K-means clustering ； Histogram ； Image segmentation

參考文獻

蔡明忠, 吳宗諭, & 田芬寧. (2009). 以密度為基礎之改良型快速分群演算法及其於偏光板瑕疵檢測之應用. Journal of Technology, 24(4), 267-274.

Bezdek, J.C. (1981). Pattern recognition with fuzzy objective function algorithms. Norwell, MA: Kluwer Academic Publishers.

Bobrowski, L., & Bezdek, J.C. (1991). C-means clustering with the l1 and l∞ norms. IEEE Transactions on Systems, Man and Cybernetics, 21(3), 545-554. doi: 10.1109/21.97475

Borsotti, M, Campadelli, Paola, & Schettini, Raimondo. (1998). Quantitative evaluation of color image segmentation results. Pattern recognition letters, 19(8), 741-747.

Canny, J. (1986). A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence(6), 679-698. doi: 10.1109/TPAMI.1986.4767851