使用K-means進行像素聚類

python通過使用K-means對像素聚類以此進行圖像分割

K-means聚類簡介：

K-means算法是最為經典的基于劃分的聚類方法，是十大經典資料挖掘算法之一。K-means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過疊代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

是以，簡單來說Kmeans是一種将輸入資料劃分為k個族的簡單的聚類算法。

算法步驟（基本K-means）：

repeat  
    将每個點指派到最近的質心，形成K個簇  
    重新計算每個簇的質心  
until 簇不發生變化或達到最大疊代次數 
           

步驟

• （1）适當選擇k個類的初始中心；一般是采用随機或猜測的方式初始化類中心，(注：采用随機的方法實作簡單，但是族的品質往往比較差，是以有好幾種關于中心選取的解決方案，比如先使用層次聚類進行聚類，從層次聚類中提取K個簇，并用這些簇的質心作為初始質心。也有通過使類内總方差最小的方式，選擇方差最小的類中心。這篇部落格不是讨論算法本身，是以這裡就不過多叙述，感興趣的同學可以去查一些資料。)
• （2）對任意一個樣本，求其到k個中心的距離，将該樣本歸到距離最短的中心所在的類；(注：常用的距離度量方法包括：歐幾裡得距離和餘弦相似度。兩者都是評定個體間差異的大小的。歐幾裡得距離度量會受名額不同機關刻度的影響，是以一般需要先進行标準化。餘弦相似度傾向給出更優解)
• （3）對所有屬于該類的資料點求平均，将平均值作為新的類中心；（取平均即向量各維取平均）
• （4）重複步驟（2）（3）直到收斂。

該算法的最大優勢在于簡潔和快速，最重要的是容易實作與可并行。最大的缺陷在于要預先設定聚類數k，選擇不當則會導緻聚類效果很差。算法的關鍵在于初始中心的選擇和距離公式。

算法複雜度：

時間複雜度：O(tKmn)，其中，t為疊代次數，K為簇的數目，m為記錄數，n為維數

空間複雜度：O((m+K)n)，其中，K為簇的數目，m為記錄數，n為維數

使用scipy中的K-means：

盡 管 K-means 算 法 很 容 易 實 現, 但 我 們 沒 有 必 要 自 己 實 現 它。 SciPy 矢 量 量 化 包

scipy.cluster.vq 中有 K-means 的實作,下面是使用方法。

scipy K-means 的簡單執行個體:

# -*- coding: utf-8 -*-

#導入scipy中K-means的相關工具
from scipy.cluster.vq import *

#randn是NumPy中的一個函數
from numpy import *

from pylab import *

#生成簡單的二維資料:生成兩類二維正态分布資料。
class1 =  * randn(,)
class2 = randn(,) + array([,])
features = vstack((class1,class2))

#用 k=2 對這些資料進行聚類:
centroids,variance = kmeans(features,)

"""

由于 SciPy 中實作的 K-means 會計算若幹次(預設為 20 次),并為我們選擇方差最
小的結果,是以這裡傳回的方差并不是我們真正需要的。

"""

#用 SciPy 包中的矢量量化函數對每個資料點進行歸類:通過得到的 code ,我們可以檢查是否有歸類錯誤

code,distance = vq(features,centroids)

#可視化結果：畫出這些資料點及最終的聚類中心:函數 where() 給出每個類的索引

figure()

ndx = where(code==)[]
plot(features[ndx,],features[ndx,],'*')
ndx = where(code==)[]
plot(features[ndx,],features[ndx,],'r.')
plot(centroids[:,],centroids[:,],'go')
axis('off')
show()
           

繪制結果：

K-means像素聚類

将圖像區域或像素合并成有意義的部分稱為圖像分割。單純在像素水準上應用 K-means可以用于一些簡單圖像的圖像分割，但是對于複雜圖像得出的結果往往是毫無意義的。對于複雜圖像的圖像分割往往需要更複雜的類模型而非平均像素色彩或空間一緻性。

下面在 RGB 三通道的像素值上運用 K-means 進行聚類：

K-means RGB三通道像素聚類

對像素進行聚類首先要降分辨率處理，否則像素的值太多，運作效率會相當差，噪點也一定很多，一般情況下傳統的方式會以steps×steps個方格為機關對每個方格中的像素值進行均化以達到降低分辨率的目的，但是如果圖像不是正方形或者step值不合适的話，結果就會出現嚴重的變形，是以我将原本step×step的方式改為了stepX*stepY并且根據輸入的step自動計算合理step值，成功解決了這個問題，以下代碼中clusterpixels_square為傳統的像素聚類，clusterpixels_rectangular是我改進之後的聚類方法，希望對大家有所幫助：

# -*- coding: utf-8 -*-

"""
對像素進行聚類。
在像素級水準進行聚類可以用在一些很簡單的圖像

載入圖像，并将其下采樣到一個較低的分辨率，然後對這些區域用k-means進行聚類

K-means 的輸入是一個有 stepsX × stepsY 行的數組,數組的每一行有 3 列,各列分别為區域塊 R、G、B 三個通道的像素平均值。

為可視化最後的結果 , 我們用 SciPy 的imresize() 函數在原圖像坐标中顯示這幅圖像。

參數 interp 指定插值方法;我們在這裡采用最近鄰插值法,以便在類間進行變換時不需要引入新的像素值。

"""

from scipy.cluster.vq import *
from scipy.misc import imresize

from pylab import *

from PIL import Image

#steps*steps像素聚類
def clusterpixels_square(infile, k, steps):

    im = array(Image.open(infile))    

    #im.shape[0] 高 im.shape[1] 寬
    dx = im.shape[] / steps
    dy = im.shape[] / steps
    # 計算每個區域的顔色特征
    features = []
    for x in range(steps):
        for y in range(steps):
            R = mean(im[x * dx:(x + ) * dx, y * dy:(y + ) * dy, ])
            G = mean(im[x * dx:(x + ) * dx, y * dy:(y + ) * dy, ])
            B = mean(im[x * dx:(x + ) * dx, y * dy:(y + ) * dy, ])
            features.append([R, G, B])
    features = array(features, 'f')     # 變為數組
    # 聚類， k是聚類數目
    centroids, variance = kmeans(features, k)
    code, distance = vq(features, centroids)

    # 用聚類标記建立圖像
    codeim = code.reshape(steps, steps)
    codeim = imresize(codeim, im.shape[:], 'nearest')
    return codeim

#stepsX*stepsY像素聚類
def clusterpixels_rectangular(infile, k, stepsX):

    im = array(Image.open(infile))

    stepsY = stepsX * im.shape[] / im.shape[]

    #im.shape[0] 高 im.shape[1] 寬
    dx = im.shape[] / stepsX
    dy = im.shape[] / stepsY
    # 計算每個區域的顔色特征
    features = []
    for x in range(stepsX):
        for y in range(stepsY):
            R = mean(im[x * dx:(x + ) * dx, y * dy:(y + ) * dy, ])
            G = mean(im[x * dx:(x + ) * dx, y * dy:(y + ) * dy, ])
            B = mean(im[x * dx:(x + ) * dx, y * dy:(y + ) * dy, ])
            features.append([R, G, B])
    features = array(features, 'f')     # 變為數組
    # 聚類， k是聚類數目
    centroids, variance = kmeans(features, k)
    code, distance = vq(features, centroids)
      # 用聚類标記建立圖像
    codeim = code.reshape(stepsX, stepsY)
    codeim = imresize(codeim, im.shape[:], 'nearest')
    return codeim



#計算最優steps 為保證速度以及減少噪點 最大值為maxsteps 其值為最接近且小于maxsteps 的x邊長的約數
def getfirststeps(img,maxsteps):

    msteps = img.shape[]

    n = 

    while(msteps>maxsteps):

        msteps =   img.shape[]/n
        n = n +     

    return msteps



#Test


#圖像檔案 路徑
infile = './data/10.jpg'

im = array(Image.open(infile))

#參數
m_k = 

m_maxsteps = 

#顯示原圖empire.jpg
figure()

subplot()

title('source')

imshow(im)

# 用改良矩形塊對圖檔的像素進行聚類
codeim= clusterpixels_rectangular(infile, m_k,getfirststeps(im,m_maxsteps))

subplot()

title('New steps = '+str(getfirststeps(im,m_maxsteps))+' K = '+str(m_k));

imshow(codeim)

#方形塊對圖檔的像素進行聚類
codeim= clusterpixels_square(infile, , )

subplot()

title('Old steps = 200 K = '+str(m_k));

imshow(codeim)

show()

           

聚類結果：

我們看到，使用xy方向步數相等的方式出現了嚴重的圖像變形缺失，使用我改良的方法則解決了這個問題

聚類效果方面，對于人物這種簡單圖檔效果還是不錯的。

但是對于風景這種複雜圖檔效果就比較一般了，可能采取分水嶺這種專門的分割算法能達到一個比較好的效果。