臺灣博碩士論文加值系統

　　本論文中，我們提出一個影像分群法來解決影像分割的問題。我們的
方法是以叢聚樹演算法為基礎，並加以修改而得來的。叢聚樹演算法是一
種以決策樹為基礎的叢聚演算法。與現存的叢聚演算法大不相同的是它不
需要事先的假設條件及參數輸入，即可以找到叢聚的描述。叢聚樹演算法
採用進一步增益的方法來切割資料空間，使之成為資料密集分布區域以及
資料稀疏散佈的區域。
　　由於叢聚結果的好壞是依據使用者主觀的判定，因此我們的方法將提
供三種影像分割的結果。由實驗顯示，這些影像分割結果都有很好的表
現。

　　In this thesis, we propose an image clustering method
based on CLTree for image segmentation. CLTree is a clustering
algorithm that uses decision-tree technique. It’s quit
different from existing clustering methods, and it finds
clusters without making any prior assumptions or any input
parameters.
Whether a clustering is good or bad depends on the user's
subjective judgment, so we offer three image segmentation
results. The experimental results reveal that all of them
perform well.

目　錄
書名頁 ……………………………………………………………………i
論文口試委員審定書 ……………………………………………………ii
授權書 …………………………………………………………………iii
中文摘要 ………………………………………………………………iv
英文摘要 ………………………………………………………………v
誌謝 …………………………………………………………………………vii
目錄 ………………………………………………………………………viii
圖表目錄 ……………………………………………………………………ix
第一章　導論
第一節 數位影像處理…………………………………………………………1
第二節 影像分割………………………………………………………………2
第三節 臨界值分割法…………………………………………………………3
第四節 分類……………………………………………………………………5
第五節 叢聚……………………………………………………………………7
第六節 研究動機與目的……………………………………………………11
第七節 名詞定義……………………………………………………………13
第八節 我們提出的方法……………………………………………………14
第九節 論文組織……………………………………………………………14
第二章 文獻探討…………………………………………………………15
第一節 臨界值的影像分割演算法…………………………………………15
第二節 決策樹………………………………………………………………17
第三節 叢聚演算法…………………………………………………………23
第四節 文獻探討的小結論…………………………………………………34
第三章　以決策樹為基礎的影像分群演算法………………………………36
　　第一節 以決策樹為基礎的影像分群演算法…………………………35
第二節 建立我們的叢聚樹…………………………………………………39
第三節 叢聚樹的修剪………………………………………………………48
第四章 　實驗結果與討論………………………………………………53
　　第一節 實驗設計………………………………………………………53
第二節 實現結果與討論……………………………………………………53
第五章　結論與未來展望…………………………………………………62
第一節 研究貢獻……………………………………………………………62
　　第二節 未來展望………………………………………………………63
文獻參考……………………………………………………………………64

[1] 繆紹綱， "數位影像處理　活用Matlab"，全華科技圖書股份有限公司，2000。
[2] 衛祖賞，"數位影像處理"，全華圖書，1982。
[3] Pratt, W.K. "Digital Image Processing", John Wiley & Sons, New York, 1991.
[4] Sahoo, P.K., et al., "A Survey of Thresholding Techniques", Computer, Vision, Graphics, and Image Processing 41, pp.233-260, 1988.
[5] J. N. Kapur, P. K. Sahoo, and A. K. C. Wong, '' A new method for gray-level picture thresholding using the entropy of the histogram'', Computer Vision, Graphics and Image Processing, Vol. 29, No. 3, pp. 273-285, 1985.
[6] A. D. Brink, ``Using spatial information as an aid to maximum entropy image threshold selection'', Pattern Recognition Letters, vol. 17, no. 1, pp. 29--36, 1996.
[7] P. K. Sahoo, and Dick W.Slaaf, Thomas A.Albert, ''Threshold selection using a minimal histogram entropy difference'', Optical Engineering, Vol.36, No. 7, pp. 1976-1981, July, 1997.
[8] S. D. Zenzo, L. Cinque, and S. Levialdi, ''Image thresholding using fuzzy entropies'', IEEE Trans. Systems, Man, and Cybernetics - Part B, vol. 28, no. 1, pp. 15--23, 1998.
[9] L. K. Huang and M. J. J. Wang, ''Image thresholding by minimizing the measures of fuzziness'', Pattern Recognition, vol. 28, no. 1, pp. 41--51, 1995.
[10] F. H. Y. Chan, F. K. Lam, and H. Zhu, ``Adaptive thresholding by variational method,'' IEEE Trans. Image Processing, vol. 7, no. 3, pp. 468-- 473, 1998.
[11] Otsu, N., "A threshold selection method from gray-level histograms", IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-9, NO.1, pp.62-66,1979.
[12] Glasbey, C.A. "An analysis of histogram-based thresholding algorithms", CVGIP: Graphical Models and Image Processing, 55, 532-537, 1993.
[13] N. R. Pal, and S. K. Pal, ''Entropic thresholding'', Signal Processing, Vol. 16, No. 2, pp. 97-108, 1989.
[14] K. S. Fu and J. k. Mui, ''A survey on image segmentation'', Pattern Recognition 13, 1980,3-16.
[15] A. S. Abutaleb, ''Automatic thresholding of gray-level pictures using two- dimensional entropy'', Computer Vision, Graphics, and Image Processing, Vol. 47, No. 1, pp. 22-32, 1989.
[16] A. D. Brink, ''Thresholding of digital images using two-dimensional entropies'', Pattern Recognition, Vol. 25, No. 8, pp. 803-808, 1992.
[17] E. David Jansing, Thomas A. Albert, and Darrel L. Chenoweth, ''Two-dimensional entropic segmension'', Pattern Recognition, 1999.
[18] Jiawei Han, ''Micheline Kamber, Data Minig: Concepts and Techniques'', Morgan Kaufmann Publishers,2001.
[19] J. R. Quinlan, ''Induction on decision tree'', Machine Learning, Vol. 1,
pp. 82-106, 1986.
[20] J. R. Quinlan, ''C4.5: Programs for Machine Learning.'' San Mateo, CA: Morgan
Kaufmann, 1993.
[21] Quinlan, J. R., 1996, ''Learning Decesion Tree Classifiers'' ,ACM Computing Surveys,Vol. 28,No. 1
[22] 陳宏銘，設計最佳化之演化式模糊決策樹，逢甲大學資訊工程學系研究所碩士論文，2001。
[23] 決策樹介紹，http://www.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/c4.5_prob1.html
[24] R. C. Dubes and A. K. Jain. ''Algorithms for Clustering Data ''. Prentice Hall, 1988.
[25] L. Kaufman and P. J. Rousseeuw. ''Finding Groups in Data: an Introduction
to Cluster Analysis'', John Wiley & Sons, 1990.
[26] S. Guha, R. Rastogi, K. Shim, '' ROCK: A Robust Clustering Algorithm for Categorical Attributes'', Proceedings of the IEEE Conference on Data Engineering, 1999.
[27] S. Guha, R. Rastogi, K. Shim, ''CURE: An Efficient Clustering Algorithm for Large Databases'', In Proceedings of ACM-SIGMOD 1998.
[28] T. Zhang, R.Ramakrishnan, and M. Livny, ''BIRCH: An Efficient Data Clustering Method for very Large Databases'', Proc. Of the 1996 ACM SIGMOD int Conf. On Management of Data, Montreal, Canada, pp. 103-114, June 1996.
[29] L. Talavera and j. Bejar, '' Efficient Construction of Comprehensible Hierarchical Clustering'', In 2nd European Symposium on Principles of Data Mining and Knowledge Discovery, PKDD'98. pp. 93-101.
[30] Daniel Fasulo, ''An Analysis of Recent Work on Clustering Algorithms'', Department of Computer Science & Engineering Technical Report # 01-03-02, 1999.
[31] Bing Liu, Yiyuan Xia, Hpilip S. Yu, ''Clustering Through Decision Tree Construction'', IBM Research Report RC 21695 (97797), 20 March 2000.
[32]M. Ester, H. Kriegel, J. Sander, and X. Xu. ''A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. '' Proc. Of the 2nd Int’l Conf. On Knowledge Discovery and Data Mining, August 1996.
[33] E. Schikuta. Grid clustering: ''An efficient Hierarchical Clustering Method for Very Large Data Sets, Proc. 13th Int’l Conference on Pattern Recognition, 2, 1996.