基于聚類分析的圖像分割研究畢業(yè)論文.doc

南京郵電大學通達學院畢 業(yè) 設 計（論 文）題 目： 基于聚類分析的圖像分割研究 專 業(yè)： 信息工程 學生姓名： 朱丹青 班級學號： 100002 10000215 指導教師： 李雷 指導單位： 理學院 日期： 2014 年 1月 16 日 至 2014 年 6 月 13 日畢業(yè)設計（論文）原創(chuàng)性聲明本人鄭重聲明：所提交的畢業(yè)設計（論文），是本人在導師指導下，獨立進行研究工作所取得的成果。除文中已注明引用的內容外，本畢業(yè)設計（論文）不包含任何其他個人或集體已經發(fā)表或撰寫過的作品成果。對本研究做出過重要貢獻的個人和集體，均已在文中以明確方式標明并表示了謝意。 論文作者簽名： 日期： 年 6月 2日 目錄第一章 緒論11.1圖像分割的背景及意義11.2圖像分割的研究現狀31.3本文的主要工作5第二章 聚類分析理論72.1 聚類分析概述72.2 常見的聚類算法122.3 模糊聚類算法142.4圖像分割方法162.5本章總結18第三章 基于k-means算法的圖像分割方法193.1顏色空間193.2定義和概述193.3 簡單的例子介紹213.4 k-means圖像分割233.5改進的k-均值聚類圖像分割算法273.6本章總結31第四章 基于fcm算法的圖像分割324.1模糊聚類的概念324.2fcm算法的概述344.3本章總結43總結與展望445.1總結445.2研究展望45結束語46致謝47參考文獻48附錄a52基于k-means算法的matlab源程序52附錄b54基于k-均值聚類改進前的matlab源程序54附錄c57基于fcm聚類算法的matlab源程序57摘 要在飛速發(fā)展的信息時代，圖像是人類獲取信息的重要手段之一，因而圖像的處理就變得極其重要。而圖像分割通常是為了進一步對圖像進行分析、識別、跟蹤、理解、壓縮編碼等，分割的好壞直接影響后期的圖像識別和理解。圖像分割是指將一幅圖像分解成若干互不相交區(qū)域的集合，其實質是一個像素的聚類過程。本文以圖像分割的聚類實質為線索，對近幾年國內外最新的圖像分割算法進行了分析比較，指出了聚類在這個領域的重要性。本論文針對聚類算法在圖像分割中的應用，主要涉及了以下幾個內容：（1）詳細介紹當前圖像分割以及聚類分析的研究背景，現狀。（2）對基于模糊k均值的圖像分割算法進行探討，并對k均值算法進行改進，通過粗糙集理論提供 k-均值聚類所需要的初始類的個數和均值，提高了聚類的效率和分類的精度。（3）對基于標準模糊 c 均值聚類的圖像分割算法進行了探討，研究了基于模糊聚類的圖像分割方法中初始類別數的選取、初始類中心和初始隸屬度矩陣的確定等問題。（4）將基于模糊k均值的圖像分割算法與基于標準模糊 c 均值聚類的圖像分割算法進行對比分析。關鍵詞： 聚類分析， 模糊聚類，圖像分割，k均值算法，c均值算法abstract the rapid development in the information age , the image is an important means of human access to information , and thus the image processing becomes extremely important. and the image segmentation of the image is usually performed to further analysis, identification , tracking , understanding , compression , etc., directly affects the post- split image recognition and understanding.image segmentation refers to the collection of an image is decomposed into several disjoint regions , and its essence is a pixel clustering process . in this paper, image segmentation clustering substantive clue , at home and abroad in recent years, image segmentation algorithms are analyzed and compared , pointed out the importance of clustering in this field . this thesis clustering algorithm for image segmentation , mainly related to the following elements :( 1 ) a detailed description of current research background image segmentation and clustering analysis of the status .( 2 ) image segmentation algorithm based on fuzzy k-means were discussed , and the k-means algorithm is improved , providing the initial class and the mean number of k- means clustering required by rough set theory , improve the efficiency of clustering and classification accuracy.( 3 ) the standard image segmentation algorithm based on fuzzy c -means clustering were discussed , studied to select the initial number of categories based on fuzzy clustering method of image segmentation , determining the initial cluster centers and the initial membership matrix of other issues.( 4 ) the segmentation algorithm for image segmentation algorithm based on fuzzy c-means clustering standard comparative analysis based on k-means fuzzy image .keywords: cluster analysis , fuzzy clustering , image segmentation , k -means algorithm , c -means algorithm南京郵電大學通達學院2014屆本科生畢業(yè)設計(論文)第一章 緒論 在當前快速發(fā)展信息化時代，通過圖像來獲取信息是人類認識世界改造世界的重要方式之一，由此看來圖像的處理就變得十分重要1。圖像處理(image processing)，用計算機對圖像進行分析，以達到所需結果的技術。又稱影像處理。基本內容 圖像處理一般指數字圖像處理。數字圖像是指用數字攝像機、掃描儀等設備經過采樣和數字化得到的一個大的二維數組，該數組的元素稱為像素，其值為一整數，稱為灰度值。圖像處理技術的主要內容包括圖像壓縮，增強和復原，匹配、描述和識別3個部分2。 常見的處理有圖像數字化、圖像編碼、圖像增強、圖像復原、圖像分割和圖像分析等。其中圖像分割的目的是為了后續(xù)對圖像進行分析、識別、跟蹤、理解、壓縮編碼等，分割的準確性直接影響后續(xù)任務的效果，具有極其重要的意義。所以本課題將研究方向確定在利用圖像分割技術來進行圖像的識別3。1.1圖像分割的背景及意義 聚類分析研究有很長的歷史，幾十年來，其重要性及其研究方向的交叉特性得到人們的肯定。聚類分析是數據挖掘研究方向的重要研究內容之一，在識別數據的內在結構方面有極其重要的作用。數據挖掘技術是從上世紀80年代開始發(fā)展起來的一門交叉學科，涉及到數據庫、統(tǒng)計學、人工智能和機器學習多個領域。計算機的應用普及產生了大量數據，數據挖掘就是利用上述學科的技術進行大量的數據處理。數據挖掘的應用范圍非常的廣泛，從農業(yè)生產的預測到基因分類，從信用卡欺詐到稅務稽查，數據挖掘技術對未來社會的各個領域將起到越來越大的作用4。 在一副圖像中，我們在通常情況下只是對其中的某些目標感興趣，它們通常在要分割的圖像中占據一定的區(qū)域，而且在某些特性上與周圍的圖像存在一定的差別。這些差別有時候可能是特別明顯的，也有可能是非常微小的，以至于人的肉眼無法察覺的到的。圖像分割是按照一定的制約規(guī)則把圖像劃分為若干個互不相交，具有特定性質的區(qū)域,是把我們關注的區(qū)域從需要分割的圖像中提取出來，從此進行進一步研究和處理的技術。它使得其中的圖像分析和識別等處理過程中所要處理的數據量大大減少了，同時有保留了有關圖像結構特征的信息。圖像分割的結果是圖像特征提取和識別等圖像理解的基礎，對圖像分割的研究一直是數字圖像處理技術的焦點和熱點。關于圖像分割的概念有很多，但最終都歸于一個基本思想，即圖像分割時根據實際需求與應用，按照指定特征信息，對圖像中有意義的邊界、興趣區(qū)域或者對相一致的區(qū)域（灰度、顏色、紋理等）進行分解和提取的技術和過程5。 圖像分割的數學解釋：假定一幅圖像中所有像素的集合為，有關均勻性的假設為。分割定義把劃分為若干子集，其中每個子集都構成一個空間連通區(qū)域。用四個條件進行數學描述，即6：；。式中，為空集。 圖像分割的重要性，可以從圖像工程的三個層次來理解，如圖1.1所示。圖像工程是指對圖像進行采樣、量化、編碼、傳輸、增強、邊緣檢測、分割、形態(tài)分析、目標識別、目標表達等一系列的加工處理、分析和理解的綜合工程技術。 圖像工程根據抽象程度和研究方法的不同分為三個層次：圖像處理、圖像分析和圖像理解。而圖像分割是圖像識別和圖像理解的基礎，分割的好壞結果直接影響到后期的識別和理解7。 圖1.1圖像分割在圖像工程中的位置 圖像分割在實際中也已得到廣泛的應用，例如在工業(yè)自動化，在線產品檢驗，以及軍事、體育、農業(yè)工程等方面8。概括來說，在各種圖像應用中，只要需對圖像目標進行提取，測量等都離不開圖像分割。 圖像分割技術的發(fā)展與許多其它學科和領域，例如數學、物理、心理學、電子學、計算機科學等學科密切相關。近年來，隨著各學科許多新理論和方法的提出，人們也提出了許多結合一些特定理論、方法和工具的分割技術9。每當有新的數學工具或方法提出來，人們就試著將其用于圖像分割，因而提出了不少特殊的算法。例如利用馬爾可夫隨機場、數學形態(tài)學、模擬退火、遺傳算法、聚類分析。新的分割算法還在不斷涌現。其中，基于聚類分析的圖像分割方法是圖像分割領域中一類極其重要和應用相當廣泛的算法，其在應用領域取得的巨大成功引起了廣大關注10。 1.2圖像分割的研究現狀 基于聚類分析的圖像分割方法是圖像領域中一類極其重要和應用相當廣泛的算法，無論是灰度圖像分割、彩色圖像分割還是紋理圖像或者其他類型的圖像分割，都可運用聚類分析方法11。 聚類是把具有相似性質的事物區(qū)分開并加以分類，它是運用數學方法對處理給定對象的進行分類。聚類問題是一個古老的問題，是伴隨人類的產生和發(fā)展而不斷深化的一個問題，有關聚類分析的理論和應用的研究己有大量的文獻。經典分類學是從單個因素或有限幾個因素出發(fā)，憑經驗和專業(yè)知識對事物分類，這種分類具有非此即彼的特性，分出的類別界限很清晰。隨著認識的深入，發(fā)現這種分類不適用于具有模糊性的分類問題，如圖像中的區(qū)域之間的邊界就往往是模糊不清的。模糊數學的產生為上述軟分類提供了數學基礎，由此產生了模糊聚類分析12。 用普通數學方法進行分類的聚類法稱為普通聚類分析，而把應用模糊數學方法進行分析的聚類分析稱為模糊聚類分析。由于圖像技術本身的復雜性和相關性，在圖像處理過程中出現了不確定性和不精確性。這種不確定性和不精確性主要體現在圖像灰度的不確定性、幾何形狀的不確定性和不確定性知識等。這種不確定性是經典的數學理論無法解決的，并且這種不確定性不是隨機的，因而不適于用概率論來解決13。 因為模糊理論對于圖像的這種不確定性有很好的描述能力，所以可以引入模糊理論作為有效描述圖像特點和人的視覺特性的模型和方法。近年來一些學者致力于將模糊理論引入到圖像處理中，取得很好的效果，經過專家學者幾十年的研究，圖像的模糊處理技術獲得極大的發(fā)展?；谀：碚摰膱D像分割方法主要可分為模糊閾值分割和模糊聚類分割。圖像分割的實質簡單地說是一個按照像素屬性（灰度，紋理，顏色等）聚類的過程14。 因此，聚類分析就廣泛應用于圖像分割之中。其中模糊聚類分割方法是最先提出、也是最經典的一種圖像模糊分割方法。本文中基于聚類分析的圖像分割算法主要是針對模糊聚類算法應用于圖像分割中的介紹和研究。實際中應用最為廣泛的模糊聚類方法是模糊c-均值算法(fuzzy c-means)，簡稱fcm，本文中的模糊聚類算法也特指模糊c均值算法15。fcm算法首先是由ruspini提出的，但真正有效的方法是由dunn給出的。1974 年dunn將硬c-均值聚類算法推廣到模糊情形，同年，bezdek將dunn的方法一般化，建立了模糊c-均值聚類理論。1980 年bezdek又證明了模糊c-均值聚類算法的收斂性，并討論了模糊c-均值聚類算法與硬c-均值聚類算法的關系16。從此，基于目標函數的模糊聚類方法蓬勃發(fā)展起來，目前從不同的角度對基于目標函數的模糊聚類方法進行研究，歸納起來主要集中在以下四個方面：模糊聚類新方法的研究、實現途徑的研究、聚類有效性的研究和模糊聚類的應用研究。 fcm 算法采用迭代法優(yōu)化目標函數來獲得對數據集的模糊分類，算法具有很好的收斂性。采用模糊 c-均值聚類的方法進行圖像分割的優(yōu)點是避免了設定閾值的問題，并且能解決閾值化分割難以解決的多個分支的分割問題。fcm 適合于圖像中存在不確定性和模糊性的特點，同時 fcm 算法是屬于無監(jiān)督的分類方法，聚類過程中不需要任何人工的干預，很適合于自動分割的應用領域17。 利用fcm算法進行圖像分割主要有以下難點和問題：聚類類別數c的確定 在聚類進行之前必需給定類的數目，否則聚類無法進行。在實際應用中，尤其是自動化的系統(tǒng)中這是不太現實的。均值聚類方法中最困難的是圖像分割的類別數的確定。初始類中心初始隸屬度矩陣的確定 模糊聚類分割方法必須給出初始聚類中心和確定初始隸屬度矩陣。根據數學分析理論任何一個迭代并且最后收斂的序列，如果迭代的初始值比較接近于最后的收斂結果的話，收斂的速度會明顯提高，迭代次數也會較大幅度地減小。同時，也因為接近最后結果陷入其它局部最優(yōu)的可能性減小。另外，如果聚類迭代的初始值接近于某個局部極值的話，就很有可能最終陷入局部極值，從而得不到全局最優(yōu)值，所以fcm算法對初始值相當敏感。在沒有任何先驗知識也沒有任何輔助手段的情況下，系統(tǒng)可以采用隨機選取類中心的辦法。但那樣就過于盲目，而且很容易陷入局部最優(yōu)迭代，收斂速度可能很低，迭代的次數也可能會增加很多，這樣也就會增加計算時間。所以初始參數的確定，對于計算量的降低顯得尤其重要。然而目前尚無有效的理論指導，如何選擇合適的聚類初始值仍然是一個難題。迭代過程中的大計算量問題 由于聚類是一個非線性優(yōu)化過程，聚類迭代算法在一般情況下收斂速度較慢。圖像分割是一個樣本量很大的分類問題，尤其當特征空間是多維空間時（如彩色圖像分割時的三維顏色空間聚類時）迭代算法中計算量過大而且只能串行，耗時很多，基于模糊聚類的計算量就更大了，使得fcm算法的實際應用具有一定的局限性，更不用說實時應用了。為了解決模糊聚類中大計算量的問題，降低計算時間，人們一般從三個方面來考慮：選擇接近最后結果的初始值，盡可能地減少迭代的次數；改進算法，減少每一輪迭代的計算量；設計快速的實現算法。丁震等人提出了一種針對模糊聚類的快速二值化方法，該方法將圖像映射到灰度特征空間，然后在特征空間中進行聚類，顯然特征空間中灰度級是很少的，而圖像的像素則是大樣本集，這樣一來計算量大幅度降低，分割質量也還可以。但是該算法只適用于將圖像分割成目標和背景兩類的灰度圖像應用?？臻g信息的使用 模糊均值聚類方法分割的另一個問題是它只考慮到了灰度特征或彩色圖像的色特征，忽略了圖像中固有的豐富的空間信息，從而導致它對噪聲比較敏感，而且使得分割出的區(qū)域往往不連續(xù)，導致本屬于同類的像素沒有連在一起，不能形成有意義的子圖。如何有效地利用空間信息，提高分割質量，同時又不至于大幅增加計算量是一個很有意義的研究課題。聚類的后處理的問題 由于模糊聚類法分割是一般都沒有有效地利用圖像像素之間的空間關系信息，容易導致分割出來的區(qū)域可能不連續(xù)；另一個分割時類別數未必是正確的，往往有過分割的可能。于是一般在聚類完成后對分割出的結果需要進行一些合并類的后處理，使得最后分割出的區(qū)域都是有意義的。針對模糊聚類fcm存在的這個問題，ray等人提出了一種基于解微分方程的曲線進化的方法，該方法利用截集理論來演變分割圖中的幾何曲線，進而描述圖像的區(qū)域。該方法不失為一種較好的后處理方法，它排除了分割圖中的不連續(xù)性，使得各區(qū)域之間的邊界是封閉和連續(xù)的。但該方法的邊界曲線演變過程的計算復雜度很高，非常耗時；它存在的另一個問題是后處理過程可能會產生新的分割錯誤。然而，好的后處理方法應該分析聚類后存在的各種不同的問題，然后采用不同的方法進行處理，既要降低計算復雜度，又要避免引入新的噪聲。二十幾年來，研究工作者們對傳統(tǒng)fcm算法進行不斷的研究，提出許多不同的改進，但上述問題仍然沒有完全解決。 1.3本文的主要工作 本文在介紹圖像分割的定義、方法、應用及研究意義和研究現狀以及支持向量機的基礎理論之后做了如下任務：（1）詳細介紹當前圖像分割以及聚類分析的研究背景，現狀。（2）介紹了基于聚類算法的圖像分割的算法步驟，以及本文所使用matlab軟件工具；（3）對基于模糊k均值的圖像分割算法進行探討，并對k均值算法進行改進，通過粗糙集理論提供 k-均值聚類所需要的初始類的個數和均值，提高了聚類的效率和分類的精度。（4）對基于標準模糊 c 均值聚類的圖像分割算法進行了探討，研究了基于模糊聚類的圖像分割方法中初始類別數的選取、初始類中心和初始隸屬度矩陣的確定等問題（5）總結了本文的主要研究內容，并就本文尚存在的不足進行了展望。第二章 聚類分析理論聚類分析是一種新興的多元統(tǒng)計方法，是當代分類學與多元分析的結合。聚類分析是將分類對象置于一個多維空間中，依據樣本間關聯的度量標準將其自動分成幾個群組，且使同一群組內的樣本相似，而屬于不同群組的樣本相異的一組方法。聚類的樣本是用度量指針的一個向量表示，即用多維空間的一個點來表示。同類中的樣本比屬于不同類的樣本彼此具有更高的相似性。聚類分析通常是基于距離的，通過構造一個 m 維空間的距離函數，利用這個距離函數來進行聚類。 2.1 聚類分析概述 迄今為止，聚類還沒有一個學術界公認的定義，這里給出everittis在1974年關于聚類所下的定義：一個類簇內的實體是相似的，不同類簇的實體是不相似的；一個類簇是測試空間中點的會聚，同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離；類簇可以描述為一個包含密度相對較高的點集的多維空間中的連通區(qū)域，它們借助包含密度相對較低的點集的區(qū)域與其他區(qū)域（類簇）相分離。 定義 2.1簇(cluster)：一個數據對象的集合。在同一簇中，對象具有相似性，不同簇中，對象之間是相異的。 定義 2.2聚類分析(clustering analysis)：把一個給定的數據對象集合分成不同的簇,即在空間 x 中給定一個有限的取樣點集或從數據庫中取得有限個例子的集合，xini=1。聚類的目標是將數據聚集成類，使得類間的相似性最小，而類內的相似性盡可能得大。 沒有任何一種聚類技術（聚類算法）可以普遍適用于揭示各種多維數據集中所呈現出來的多種多樣的結構，根據數據在聚類中積聚規(guī)則以及應用這些規(guī)則的方法，有多種聚類算法。聚類算法有多種分類方法：1劃分方法給定一個包含n 個對象的數據集，劃分方法將數據集劃分為k 個子集。其中每個子集均代表一個聚類（k=n）。給定需要劃分的個數k，一個劃分方法創(chuàng)建一個初始劃分，然后利用循環(huán)再定位技術，即通過移動不同劃分中的對象來改變劃分內容。一個好的劃分衡量標準通常就是同一個組中的對象彼此相近或相關，而不同組中的對象較遠或差距較大。主要的劃分方法有：k-means 聚類法和k-medoid 聚類法。k-means 聚類法在處理海量數據庫方面較有效，特別是對數值屬性處理，它對異常數據很敏感。pam（圍繞中心對象進行劃分）方法是最初提出的k-medoid 聚類算法之一。k-medoid 聚類算法比k-means 聚類算法在處理異常數據和噪聲數據方面更為魯棒，但是前者的處理時間要比后者更大。2層次方法層次方法就是通過分解所給定的數據對象集來創(chuàng)建一個層次。根據層次分解形成的方式，可以將層次方法分為自下而上（也稱凝聚方式）和自上而下（也稱分割方式）兩種類型。自下而上的層次方法從每個對象均為一個單獨的組開始,逐步將這些組進行合并，直到組合并到了層次頂端或滿足終止條件為止。自上而下層次方法從所有對象均屬于一個組開始，每一次循環(huán)將其分解為更小的組，直到每個對象構成一組或滿足終止條件為止。birch 和cure 算法就是層次方法的實例。3基于密度方法基于密度的聚類方法就是不斷增長所獲得的聚類直到鄰近密度小于一定閾值為止。這種方法可以用于消除數據中的噪聲（異常數據）。dbscan 就是一個典型的基于密度的方法，該方法根據密度閾值不斷增長聚類。4基于網格方法基于網格方法將對象空間劃分為有限數目的單元以形成網格結構。所有聚類操作均是在這一網格結構上進行的。這種方法主要優(yōu)點就是處理事件由于與數據對象個數無關而僅與劃分對象空間的網格數相關，從而顯得相對較快。sting 就是一個典型的基于網格的方法。5基于模型方法基于模型的方法就是為每個聚類假設一個模型，再去發(fā)現符合相應模型的數據對象。一個基于模型的算法可以通過構造一個描述數據點空間分布的密度函數來確定具體聚類。它根據標準統(tǒng)計方法并考慮到“噪聲”或異常數據，可以自動確定聚類個數，因此它可以產生很魯棒的聚類方法。如神經網絡方法。 2.1.1聚類分析中的數據類型數據挖掘的一個重要步驟是數據準備，這包括對選定的數據進行規(guī)范化、整合和預處理等等，這是進行數據挖掘的前提，也同樣是聚類算法能正常實施的必要前提。要對數據對象進行聚類，基于統(tǒng)計方法，其最重要的前提是要計算各個數據對象之間的距離即相異度，針對不同的數據類型有不同的相異度計算方法。許多基于內存的聚類算法常使用以下兩種有代表性的數據結構：數據矩陣和相異度矩陣。 數據矩陣與相異度矩陣 設聚類問題中有n個對象:(i=1,2,.,n)，對每個對象選擇了p個變量，用間隔尺度測定后，第i個對象的第j個變量的觀測值用表示，則這n個對象所有p個變量的觀測值可以看成是如下的 np 矩陣: （2.1）矩 陣 (2.1)常被稱為數據矩陣，它是對象變量結構的數據表達方式，其中 第i個對象的p個變量的觀測值可以記為向量:=t (2.2)聚類中常用的另外一種數據結構是相異度矩陣，它存儲的是n個對象兩兩之間的近似性，表現形式為一個 nn 矩陣: (2.3)其中 d(i,j) , 是對象 i 與對象 1 之間相異性的量化表示，通常它是一個非負的數值，當對象 i 和對象 j 越相似和越“接近”， d(i,j) , 的值就越接近。反之，如果兩個對象越不同或相距“越遠”， d(i,j) , 的值就越大。顯然d(i,j) ,d(i,j) ，且d(i,j) , =0，因此可以得到形如(2.3)的矩陣。相異度矩陣是對象對象結構的一種數據表達方式。2.1.2聚類分析的典型要求 聚類是一個富有挑戰(zhàn)性的研究領域，它的潛在應用提出了各自特殊的要求。數據挖掘對聚類的典型要求如下。1) 可伸縮性許多聚類算法在小于200 個數據對象的小數據集合上工作得很好；但是，一個大規(guī)模數據庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類又可能會導致偏差的結果。我們需要具有高度可伸縮性的算法。2）處理不同類型屬性的能力許多算法被設計用來聚類數值類型的數據。但是，應用可能要求聚類其他類型的數據，如二元類型（binary），分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。3）發(fā)現任意形狀的聚類許多聚類算法基于歐幾里的距離或者曼哈坦距離度量來決定聚類?；谶@樣的距離度量的算法趨向于發(fā)現具有相近尺度合密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發(fā)現任意形狀簇的算法是很重要的。4）處理噪聲數據的能力絕大多數現實世界中的數據庫都包含了孤立點，空缺，未知數據或者錯誤的數據。一些聚類算法對于這樣的數據敏感，可能導致低質量的聚類結果。5）對于輸入記錄的順序不敏感一些聚類算法對于輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序提交同一個算法時，可能生成差別很大的聚類結果。開發(fā)對數據輸入順序布敏感的算法具有重要的意義。6）高維性（high dimensionality）一個數據庫或者數據倉庫可能包含若干維或者屬性。許多聚類三算法擅長處理低維數據，可能只涉及兩到三維。人類最多在三維的情況下能夠很好地判斷聚類的質量。在高維空間中聚類數據對象時非常有挑戰(zhàn)性的，特別是考慮到這樣的數據可能非常稀疏，而且高度偏斜。 2.1.3聚類分析的一般步驟 在實際應用聚類分析中，根據有無領域知識參與可將整個過程分解為三個環(huán)節(jié)，每個環(huán)節(jié)都有其明確的任務，這樣對于整個聚類分析的過程就會有更清晰的認識，如圖 1.1 所示。 圖1.1聚類的一般步驟第一步是特征抽取。 它的輸入是原始樣本，由領域專家決定使用哪些特征來深刻地刻畫樣本的本質性質和結構。它的結果輸出是一個矩陣，矩陣的每一行是一個樣本，每一列是一個特征指標變量。選取特征的優(yōu)劣將直接影響以后的分析和決策。如果第一步就選擇了和聚類意圖根本無關的特征變量，那企圖得到良好的聚類結果則無異于緣木求魚。合理的特征選取方案應當使得同類樣本在特征空間中相距較近，異類樣本則相距較遠。在有些應用場合還需要將得到的樣本矩陣進行一些后處理工作。比如為了統(tǒng)一量綱就對變量進行標準化處理，這樣采用不同量綱的變量才具有可比性；有些場合可能選擇的特征變量太多，不利于以后的分析和決策，這時可以先進行降維處理；僅憑經驗和領域知識選擇的特征變量有可能是相關的，進行主成分分析就可以消除變量間的相關性，從而得到一些相互獨立的特征變量。第二步是執(zhí)行聚類算法，獲得聚類譜系圖。 它的輸入是一個樣本矩陣，它把一個樣本想象成特征變量空間中的一個點。聚類算法的目的就是獲得能夠反映 x 維空間中這些樣本點之間的最本質的“簇成一團”性質。這一步沒有領域專家的參與，它除了幾何知識外不考慮任何的領域知識，不考慮特征變量在其領域中的特定含義，僅僅認為它是特征空間中一維而己。聚類算法的輸出一般是一個聚類譜系圖，由粗到細地反映了所有的分類情況；或者直接給出具體的分類方案，包括總共分成幾類，每類具體包含那些樣本點等等。第三步是選取合適的分類閾值。 在得到了聚類譜系圖之后，領域專家憑借經驗和領域知識，根據具體的應用場合，決定閾值的選取。選定閾值之后，就能夠從聚類譜系圖上直接看出分類方案。領域專家還可以對聚類結果結合領域知識進行進一步的分析，從而加深樣本點和特征變量的認識。 總之，實際應用聚類分析是一個需要多方參與的過程，它無法脫離開領域專家的參與，聚類算法僅僅是整個聚類流程中的一環(huán)而己，光依靠聚類算法一般不會得到令人滿意的效果。2.2 常見的聚類算法2.2.1 k-means 算法k-means 聚類算法是給定類的個數 k，利用距離最近的原則，將 n 個對象分到 k 個類中去，聚類的結果由 k 個聚類中心來表達，基于給定的聚類目標函數（或稱聚類效果判別函數），算法采用迭代更新的方法，每一次迭代過程都是向目標函數值減少的方向進行；在每一輪中，依據 k 個參照點將其周圍的點分別組成 k 個簇，而每個簇的幾何中心將被作為下一輪迭代的參照點，迭代使得選取的參照點越來越接近真實的簇幾何中心，使得類內對象之間的相似性最大，類之間的相似性最小。聚類效果的好壞用目標函數 j表示:， (2.4) 其中是與之間的距離函數，如歐氏距離。目標函數j 其實就是每個數據點與所在簇的質心的距離之和，所以，j值越小，簇就越緊湊，相對越獨立。因此，算法通過不斷優(yōu)化j的取值來尋求好的聚類方案，當j取極小值時，對應的聚類方案即是最優(yōu)方案。根據聚類結果的表達方式可以將聚類算法劃分為：硬k-means（hcm）算法、模糊k-means（fcm）算法和概率k-means 算法（pcm）。k-means 算法描述如下：步驟 1) 隨機選取k個對象作為初始的簇的質心; 步驟 2) 計算對象與各個族的質心的距離，將對象劃分到距離其最近的簇 ; 步驟 3) 重新計算每個新簇的均值，即質心;步驟 4) 若簇的質心不再變化，則返回劃分結果，否則轉步驟2）.k-means 算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果較好。面對大規(guī)模數據集，該算法是相對可擴展的，并且具有較高的效率。算法的復雜度為o(nkt),其中，n為數據集中對象的數目，k為期望得到的簇的數目，t為迭代的次數。通常情況下，算法可以終止于局部最優(yōu)解。 但是，kmeans算法只有在簇的平均值被定義的情況下才能使用。這可能不適用于某些應用，例如涉及有分類屬性的數據。其次，這種算法要求事先給出要生成的簇的數目k，顯然，這在某些應用中是不實際的。另外，k-means算法不適用于發(fā)現非凸面形狀的簇，或者大小差別很大的簇。還有，它對于噪音和孤立點數據是敏感的。 kmeans算法有很多變種，例如，k-模算法用模代替簇的平均值，用新的相異性度量方法來處理分類對象，用基于頻率的方法來修改聚類的模。而k平均算法和k模算法相結合，用來處理有數值類型和分類類型屬性的數據，就產生了k-原型算法。2 .2. 2 d bscan 算法dbscan 算法可以將足夠高密度的區(qū)域劃分為簇, 并可以在帶有 “噪聲” 的空間數據庫中發(fā)現任意形狀的聚類 。 dbscan 通過檢查數據庫中每個點的e 2鄰域來尋找聚類 。 如果一個點 p 的 e 2 鄰域包含多于m inp ts 個點, 則創(chuàng)建一個以 p 作為核心對象的新簇 。然后反復地尋找從這些核心對象直接密度可達的對象, 當沒有新的點可以被添加到任何簇時, 該過程結束 。 如果采用空間索引, dbscan 的計算復雜度是o(n log n ) 。 2.2.3 sting算法sting（statistical information grid)算法是一種基于網格的多分辨率聚類方法，它將空間區(qū)域劃分為若干矩形網格單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結構，高層的每個單元被劃分為多個低一層的單元。關于每個網格單元屬性的統(tǒng)計信息，如平均值、最大值、最小值等，被預先計算和存儲。 高層單元的統(tǒng)計參數可以很容易地從低層單元的計算得到。這些統(tǒng)計參數包括:屬性無關的參數count；屬性相關的參數m(平均值)，s(標準方差)，min(最小值)，max(最大值)，以及該單元中屬性值遵循的分布(distribution)類型，例如正態(tài)分布、平均分布、指數分布或無(如果分布未知)。當數據被裝載進數據庫時，底層單元的參數count、m、s, min和max直接進行計算。如果分布的類型事先知道，distribution的值可以由用戶指定，也可以通過假設檢驗來獲得。 統(tǒng)計參數的使用可以按照以下自頂向下的基于網格的方法:首先，在層次結構中選定一層作為查詢處理的開始點。通常該層包含少量的單元。對當前層次的每個單元，我們計算置信度區(qū)間或者估算其概率范圍，用以反映該單元與給定查詢的關聯程度，不相關的單元就不再考慮。低一層的處理就只檢查剩余的相關單元。這個過程反復進行，直到達到底層。此時，如果滿足查詢條件，那么返回相關單元的區(qū)域。否則，檢索和進一步處理相關單元中的數據，直到它們滿足查詢條件。 與其他聚類方法相比，sting算法的優(yōu)點在于: (1) 由于存儲在每個單元中的統(tǒng)計信息提供了單元中的數據不依賴于查詢的匯總信息，所有基于網格的計算是獨立于查詢的； (2) 網格結構有利于并行處理和增量更新； (3) 算法效率很高。sting算法通過掃描一次數據庫來計算單元的統(tǒng)計信息，產生聚類的時間復雜度是on)，其中n為對象的數目。在層次結構建好后，查詢處理的時間復雜度是o(g)，其中g是最低網格單元的數目，通常遠遠小于n 。 sting 算法的性能取決于最底層單元的粒度，該粒度也決定著聚類結果的質量。sting算法在粒度較大時，速度非?？?，但這時聚類的質量不夠好。當粒度較小時，聚類結果的質量好，但處理的代價會增加。2.3 模糊聚類算法2.3.1 模糊聚類算法概述模糊聚類算法是一種基于函數最優(yōu)方法的聚類算法，使用微積分計算技術求最優(yōu)代價函數。在基于概率算法的聚類方法中將使用概率密度函數，為此要假定合適的模型，模糊聚類算法的向量可以同時屬于多個聚類，從而擺脫上述問題。在模糊聚類算法中，定義了向量與聚類之間的近鄰函數，并且聚類中向量的隸屬度由隸屬函數集合提供。對模糊方法而言，在不同聚類中的向量隸屬函數值是相互關聯的。硬聚類可以看成是模糊聚類方法的一個特例。2.3.2 模糊聚類算法的分類模糊聚類分析算法大致可分為三類4： 1）分類數不定，根據不同要求對事物進行動態(tài)聚類，此類方法是基于模糊等價矩陣聚類的，稱為模糊等價矩陣動態(tài)聚類分析法。 2）分類數給定，尋找出對事物的最佳分析方案，此類方法是基于目標函數聚類的，稱為模c均值聚類。3）在攝動有意義的情況下，根據模糊相似矩陣聚類，此類方法稱為基于攝動的模糊聚類分析法。2.3.3 fcm算法fcm算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對象之間相似度最大，而不同簇之間的相似度最小。 模糊c均值算法是普通c均值算法的改進，普通c均值算法對于數據的劃分是硬性的，而fcm則是一種柔性的模糊劃分。在介紹fcm具體算法之前我們先介紹一些模糊集合的基本知識。隸屬度函數是表示一個對象x隸屬于集合a的程度的函數，通常記做a(x)，其自變量范圍是所有可能屬于集合a的對象（即集合a所在空間中的所有點），取值范圍是0,1，即0=1，a(x)1是一個加權指數 構造如下新的目標函數，可求得使（1.2）式達到最小值的必要條件：(2.6)這里lj，j=1到n，是（6.9）式的n個約束式的拉格朗日乘子。對所有輸入參量求導，使式（6.10）達到最小的必要條件為：(2.7) 和(2.8)2.4圖像分割方法2.4.1. 基于閾值的分割方法包括全局閾值、自適應閾值、最佳閾值等等。閾值分割算法的關鍵是確定閾值，如果能確定一個合適的閾值就可準確地將圖像分割開來。閾值確定后，將閾值與像素點的灰度值比較和像素分割可對各像素并行地進行，分割的結果直接給出圖像區(qū)域。全局閾值是指整幅圖像使用同一個閾值做分割處理，適用于背景和前景有明顯對比的圖像。它是根據整幅圖像確定的：t=t(f)。但是這種方法只考慮像素本身的灰度值，一般不考慮空間特征，因而對噪聲很敏感。常用的全局閾值選取方法有利用圖像灰度直方圖的峰谷法、最小誤差法、最大類間方差法、最大熵自動閾值法以及其它一些方法。 在許多情況下，物體和背景的對比度在圖像中的各處不是一樣的，這時很難用一個統(tǒng)一的閾值將物體與背景分開。這時可以根據圖像的局部特征分別采用不同的闞值進行分割。實際處理時，需要按照具體問題將圖像分成若干子區(qū)域分別選擇閾值，或者動態(tài)地根據一定的鄰域范圍選擇每點處的閾值，進行圖像分割。這時的閾值為自適應閾值。 閾值的選擇需要根據具體問題來確定，一般通過實驗來確定。對于給定的圖像，可以通過分析直方圖的方法確定最佳的閾值，例如當直方圖明顯呈現雙峰情況時，可以選擇兩個峰值的中點作為最佳閾值。2.4.2基于邊緣的分割方法檢測灰度級或者結構具有突變的地方，表明一個區(qū)域的終結，也是另一個區(qū)域開始的地方。這種不連續(xù)性稱為邊緣。不同的圖像灰度不同，邊界處一般有明顯的邊緣，利用此特征可以分割圖像。圖像中邊緣處像素的灰度值不連續(xù)，這種不連續(xù)性可通過求導數來檢測到。對于階躍狀邊緣，其位置對應一階導數的極值點，對應二階導數的過零點(零交叉點)。因此常用微分算子進行邊緣檢測。常用的一階微分算子有roberts算子、prewitt算子和sobel算子，二階微分算子有l(wèi)aplace算子和kirsh算子等。在實際中各種微分算子常用小區(qū)域模板來表示，微分運算是利用模板和圖像卷積來實現。這些算子對噪聲敏感，只適合于噪聲較小不太復雜的圖像。 由于邊緣和噪聲都是灰度不連續(xù)點，在頻域均為高頻分量，直接采用微分運算難以克服噪聲的影響。因此用微分算子檢測邊緣前要對圖像進行平滑濾波。log算子和canny算子是具有平滑功能的二階和一階微分算子，邊緣檢測效果較好，如圖4所示。其中l(wèi)og算子是采用laplacian算子求高斯函數的二階導數，canny算子是高斯函數的一階導數，它在噪聲抑制和邊緣檢測之間取得了較好的平衡。2.4.3基于聚類分析的圖像分割方法 特征空間聚類法進行圖像分割是將圖像空間中的像素用對應的特征空間點表示，根據它們在特征空間的聚集對特征空間進行分割，然后將它們映射回原圖像空間，得到分割結果。其中，k均值、模糊c均值聚類(fcm)算法是最常用的聚類算法。k均值算法先選k個初始類均值，然后將每個像素歸入均值離它最近的類并計算新的類均值。迭代執(zhí)行前面的步驟直到新舊類均值之差小于某一閾值。模糊c均值算法是在模糊數學基礎上對k均值算法的推廣，是通過最優(yōu)化一個模糊目標函數實現聚類，它不像k均值聚類那樣認為每個點只能屬于某一類，而是賦予每個點一個對各類的隸屬度，用隸屬度更好地描述邊緣像素亦此亦彼的特點，適合處理事物內在的不確定性。利用模糊c均值(fcm)非監(jiān)督模糊聚類標定的特點進行圖像分割，可以減少人為的干預，且較適合圖像中存在不確定性和模糊性的特點。2.5本章總結 本章主要介紹了聚類分析的概述以及定義，聚類分析的一般步驟，常見的聚類算法k-means 算法，d bscan 算法，sting算法，fcm算法，和常見的圖像分割方法，本章是該研究所需要的預備基礎知識。第三章 基于k-means算法的圖像分割方法對于彩色圖像的研究都是在特定的顏色空間進行的，常用的顏色空間有、等。顏色空間的選擇應盡可能與人類的視覺系統(tǒng)和心理感知一致。本章就是在空間研究k-means算法應用于圖像分割的效果。 3.1顏色空間彩色空間非常簡單，如圖4.1所示，彩色空間是一個立方體三維坐標空間結構，分別用紅、綠、藍表示三個坐標軸。任何顏色都落入彩色立方體內。圖3.1彩色空間但是，存在如下一些不足：（1）空間用紅、綠、藍三基色的混合比例定義不同的色彩，從而不同的顏色難以用準確的數值來表示，定量分析比較困難。（2）系統(tǒng)中，彩色通道之間的相關性很好，從而合成圖像的飽和度偏低，色調變化較小，圖像視覺效果較差。（3）人眼只能夠通過感知顏色的亮度、色調以及飽和度來區(qū)分