1、south china university of technology華南理工大學數據挖掘 實驗報告題目：數據倉庫與數據挖掘實驗 k-means圖像分割學院計算機科學與工程專 業計算機科學與技術（全英創新班）學生姓名黃煒杰學生學號 201230590051指導教師王家兵課程編號145013課程學分2分起始日期2015年5月18日實驗概述【實驗目的及要求】目的：實現a-means聚類算法進行圖像分割.要求：以迭代次數為終止條件用圖像分割berkeley圖片數據庫中的圖片作為數據集根據具體圖像，自主設定k值盡量多使用一些圖像特征，例如組合顏色、空間鄰近性、紋理、sift等特征【實驗環境】操作系統

2、:window 8(64bit)編譯器:matlab r2012b編程語言：matlab實驗內容【實驗方案設計】 實驗流程如下圖1：圖1. k-means圖像分割實驗流程圖 根據像素點色度，把原圖片進行平滑模糊化，減少孤立點數冃，提高聚類質量。 根據原圖片進行變換，提取像素點特征，把圖片轉換為數據矩陣。 對每個像素點進行聚類，根據聚類結果對圖片進行分割，產生分割子圖。實驗過程:模糊化原始圖片中，若清晰度很高，同一物體中(聚類中的同一類)存在少數點與 其他點區分度很大，肉眼粗略看沒有什區別，但是這些點卻會對聚類產生很大影 響，生成些列很零散的點群，降低聚類質量。如圖2中，綠色框中存在大量零 散的

3、孤立點，而紅色框中，可以看到物體的輪廓比較粗糙，分割結果并不理想。圖2樣木圖片模糊化前分割結杲對圖片進行模糊化有助于去除孤立點，減少噪聲，使得分割后的圖像連通性 更強。在木實驗中，模糊的處理方法是根據像素點的鄰居點對本身進行平滑，大 致算法如下：1. 計算每個像素點的8個鄰居點與木身的相似度，根據相似度對每個鄰居點 賦予權重w：, 其中w-similarityj sumsimilarity)2. 設定比值訛，每個像素點的色度t%由本身決定，(1-r%)由鄰居點決定。3. 更新每個像素點的色度：色度二色度*必+鄰居點j色度* wj * (1 - r%)4. 重復步驟廣3 k次，其中k為用戶預設值

4、下圖是進行3次模糊化后，可看出僅僅經過3次模糊化迭代，圖像的銳化程 度大大降低，可見圖中紅色方框，模糊化前狗背部毛發的紋理非常清晰，很多黑 白相間的點，而模糊化后毛發顏色變得平滑，在背景顏色與毛發中某些顏色很相 近的情況中，模糊化前的圖像可能會導致錯誤的分割結果，而后者避免了這-問 題。較之直接根據附近8個鄰居點取平均值進行模糊化，這種加權模糊化的方式 不僅沒有使物體邊界變得模糊，反而增加了其區分度。聚類吋使用的是模糊化的圖像，而最終得到分割圖片僅利用模糊圖片的點進 行索引，內容還是使用模糊化前的圖像。所以模糊化過程僅僅改善分割結果，不 會降低圖片的質量。圖3.樣本圖片模糊化前后對模糊化前后的

5、圖片分別進行kmeans聚類分割，結果對比在圖4中。留意 分割結果中的綠色框，模糊化前產生了較多的零散點群，而模糊化后，零散點群 的數量大概減少了 60%，而物體邊界則變得更加平滑，分割效果變好。雖然分割 結果并沒大大提升，但是此處理方法計算代價比較少，值得采取，其時間復雜度 為o(n*t),其中n為像素點個數，t為迭代次數。模糊化此大小為552*799個像 素點的樣例圖片，只需要1.049秒(其中木機配置：cpu 2.5g四線程,ram=4g, 非ssd硬盤)。特征提取源圖片都以rgb格式存儲，本實驗中把原圖像從rgb三維空間轉化為cielab色彩空間，并提取a,b色彩分量作為像索點為特征值

6、。選擇cielab色彩 空間的原因是cielab色彩空間的相互分量聯系性比較小，有利于分割，相對于 gaboi濾波提取紋理進行分割、采取sift特征來說，其算法復雜性較低，且能產 生較好的結果，缺點之一就是分割圖像的連通性較弱。本實驗中特征提取代碼在runme.m中,核心代碼如下："蔣征提取obfus_lab applycform(obfus.rgb, makecform(j srgb21ab，) ; $圖片從rge轉換為lab空間irowpixels, colpixels, * size (obfus.lab):$軟取89片大小obfus_ab = double (obfus_la

7、b (:, :, 2: 3);5取lab空間的a, b分郭!用于聚類obfus_ab = reshape (obfus_ab, rowpixels*colpixels, 2) ;%三纟隹矩p車轉換成數據矩陣cielab色彩空間轉換如圖5所示，a,b分量能產生較好聚類結果:圖5樣本圖片轉化為cirlab色彩空間k-means 聚類本實驗采用k-means算法偽代碼如下:輸入：k, datan, iter(1) 隨機選擇 k 個初始中心點,例如 co=datao, ck-l=datak-l；(2) 對于datao-. datan,分別與cockt比較，假定與ci距離最小，就標 記為i;(3) 對于

8、所有標記為i點,重新計算ci = 所有標記為i的datajx和/標記為i的 個數；(4) 重復(2) (3),直到所有ci值的變化小于給定閾值或不發生任何變化或迭代次數達 至!j iter 次。距離度量采用歐幾里得距離，最大迭代次數為100次。核心代碼如下：初次聚類：%初次聚類centersanple=inputdata(randsel (1: clusternum), :) :%隨機迭取初值中心點dismat.l- (sun( (inputdata(:, 1: feasize)-repmat (centersample (1, :), samplesize, 1)"2, 2)

9、9;) *0. 5：弔每個樣本點離第一個中心點距離-for 1=2: clusternuadi smat_2= (sum (inputd at a (:, 1: f easize)-repmat (centersample (i, :), samplesize, 1). *2, 2)?). *0. 5:% 每個樣本點離第 i 個中心點距; clusteridx (dismat_2<dismat_l) = i : 5更新類別 dismat_l=min(dismat_l, dismat_2) :%更新距離end初次聚類時，隨機選取中心點，先計算第一個中心點與所冇樣本點的距離，并把所冇樣本 點

10、歸為類別1。對于其他類別，逐個計算與中心點的距離，若距離小于當前距離記錄，把樣本 點的類別更新為當前類，并把距離更新為當前距離。迭代聚類：if iter>max_iter jfpnntf ( exceed naxinua iteration timesw ) :break; end®達到最大迭代次數時傳止 itersiter+l ifprmtf ( ik-means iter:n , iter):更新當前迭代次數，若達到最大迭代次數，則返回centersampletenpwcentersample;for 1=1:clusternumcentersasple (i> :

11、)=nean (inputd at a (c lust er_ i dx= 1: feasize):、更新質心、endif max (max (abs (centersamplelemp-centersample) j=0: break: end %?q果不再發生孌化'則傳止更新各個類的質心，若質心沒有發牛變化，則返回cluster_idx=ones(l, samplesize):dismat.l*(sub(inputdata(: 1 feasise)-repast (centersa«ple(l : ) saaplesize* 1). *2* 2y ) *0. 5;、每個樣

12、本點離第一個中心點距離 for i»2:clusternumdismat.2-(sun(inputdata(:. 1: feasize)*repbat(centersaaple(it ) saaplesise* 1).2)*). 0. 5:%fl5個樣本點離第i個中心點距離cluster.idx (dismat_2<dismat.l)«i:、更藕類別 dismat.l-mincdismatl, dismat_2):、更贛距厲end先計算笫一個中心點與所有樣本點的距離，并把所有樣本點歸為類別1。對于其他類別， 逐個計算與屮心點的距離，若距離小于當前距離記錄，把樣木點的類

13、別更新為當前類，并把距 離更新為當前距離。本算法時間復雜度為0 (nkt),其中n為像素點個數，k為聚類個數，t為迭代次數。在 木實驗屮，n通常為百萬數量級，k在25之間，t平均為20次左右。只需較少時間則能產生 很好的聚類結果。實驗結果【數據集選取】本實驗采用了 berkeley圖片數據庫中的bsds500數據集中的10張圖片作為 分割圖片，圖片存儲在代碼文件夾的image/文件夾下。本報告中選取了 5張圖片 進行說明，它們分別是：編號圖片聚類數目期望結果1曰2類1:北極熊類2：背景類1：巖石 類2：海與天類1：魚類2：珊瑚類3：海水類1：藍天類2：白云類3：山、地面類1：天空類2：巖石類3

14、：植物類4：地面【實驗結果分析】圖片1:北極熊和白色的雪地背景成功分開了，嘴屮的食物也被歸到背景當屮，孤立點較 少，在屮下方和右下方各有一處，分割結果優秀。圖片厶成功區分巖石和海，海上的一小塊巖石也被識別。不過巖石上方的一小部分被分 割到海與天部分，巖石部分中也存在少量海的部分，分割結果良好。圖片3：分割子團分割子圖2分割子團3海、魚、珊瑚都被成功區分，單魚下方的海底也被歸到魚中問題不人，因為只有 3個類，而珊瑚中卻含有一部分海，且孤立點群較多，分割結果一般。圖片4：藍天、白云、山與地都被非常好地區分了，幾乎沒有錯誤，分割結果優秀。圖片5：分割子圉/分割子團2分割子團3分割子團藍天、巖石都被正確分割，單植物有一部分被歸到地而上去了，分割結果一般。 實驗結論與心得通過本次實驗我看到了 k-means的強大之處。一開始我很質疑這么多的像素 點，這么多的顏色，k-means怎么能區分出來。剛開始實驗的時候我只是簡單地 用rbg三個色彩作為特征值，分出來的結果一團糟，后來上網查閱了相關內容, 做了對比后選取了 l