K-means算法原理理論+opencv實現(xiàn)

寫在前面：之前想分類圖像的時候有看過k-means算法，當時一知半解的去使用，不懂原理不懂使用規(guī)則。。。顯然最后失敗了，然后看了《機器學(xué)習(xí)》這本書對k-means算法有了理論的認識，現(xiàn)在通過賈志剛老師的視頻有了實際應(yīng)用的理解。

k-means算法原理

注：還是和之前一樣，核心都是別人的，我只是知識的搬運工并且加上了自己的理解。弄完之后發(fā)現(xiàn)理論部分都是別人的~~沒辦法這算法太簡單了。。。

k-means含義：無監(jiān)督的聚類算法。

無監(jiān)督：就是不需要人干預(yù)，拿來一大批東西直接放進算法就可以進行分類。SVM和神經(jīng)網(wǎng)絡(luò)都是需要提前訓(xùn)練好然后再進行分類這樣就是監(jiān)督學(xué)習(xí)。而k-means和K近鄰都是無監(jiān)督學(xué)習(xí)。

聚類：通過一個中心聚在一起的分類，比如給你一批數(shù)據(jù)讓你分成三類，那就是三個中心，那這三個中心代表的意思就是三個類。

k-means步驟：

從上圖中，我們可以看到，A，B，C，D，E是五個在圖中點。而灰色的點是我們的種子點，也就是我們用來找點群的點。有兩個種子點，所以K=2。

然后，K-Means的算法如下：

隨機在圖中取K（這里K=2）個種子點。

然后對圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那么Pi屬于Si點群。（上圖中，我們可以看到A，B屬于上面的種子點，C，D，E屬于下面中部的種子點）

接下來，我們要移動種子點到屬于他的“點群”的中心。（見圖上的第三步）

然后重復(fù)第2）和第3）步，直到，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了A，B，C，下面的種子點聚合了D，E）。

這個算法很簡單，但是有些細節(jié)我要提一下，求距離的公式我不說了，大家有初中畢業(yè)水平的人都應(yīng)該知道怎么算的。我重點想說一下“求點群中心的算法”。

求點群中心的算法

一般來說，求點群中心點的算法你可以很簡的使用各個點的X/Y坐標的平均值。不過，我這里想告訴大家另三個求中心點的的公式：

Minkowski Distance公式——λ可以隨意取值，可以是負數(shù)，也可以是正數(shù)，或是無窮大。

Euclidean Distance公式——也就是第一個公式λ=2的情況

CityBlock Distance公式——也就是第一個公式λ=1的情況

k-means的缺點：

在 K-means 算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的。很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適。這也是 K-means 算法的一個不足。

在 K-means 算法中，首先需要根據(jù)初始聚類中心來確定一個初始劃分，然后對初始劃分進行優(yōu)化。這個初始聚類中心的選擇對聚類結(jié)果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結(jié)果，這也成為 K-means算法的一個主要問題。

從 K-means 算法框架可以看出，該算法需要不斷地進行樣本分類調(diào)整，不斷地計算調(diào)整后的新的聚類中心，因此當數(shù)據(jù)量非常大時，算法的時間開銷是非常大的。

opencv+K-means

沒什么好寫的，因為這個k-means比較簡單，主要說的就是函數(shù)參數(shù)的應(yīng)用而已：

voidRNG::fill(InputOutputArraymat, intdistType, InputArraya, InputArrayb, boolsaturateRange=false)

這個函數(shù)是對矩陣mat填充隨機數(shù)，隨機數(shù)的產(chǎn)生方式有參數(shù)2來決定，如果為參數(shù)2的類型為RNG::UNIFORM，則表示產(chǎn)生均一分布的隨機數(shù)，如果為RNG::NORMAL則表示產(chǎn)生高斯分布的隨機數(shù)。對應(yīng)的參數(shù)3和參數(shù)4為上面兩種隨機數(shù)產(chǎn)生模型的參數(shù)。比如說如果隨機數(shù)產(chǎn)生模型為均勻分布，則參數(shù)a表示均勻分布的下限，參數(shù)b表示上限。如果隨機數(shù)產(chǎn)生模型為高斯模型，則參數(shù)a表示均值，參數(shù)b表示方程。參數(shù)5只有當隨機數(shù)產(chǎn)生方式為均勻分布時才有效，表示的是是否產(chǎn)生的數(shù)據(jù)要布滿整個范圍（沒用過，所以也沒仔細去研究）。另外，需要注意的是用來保存隨機數(shù)的矩陣mat可以是多維的，也可以是多通道的，目前最多只能支持4個通道。

voidrandShuffle(InputOutputArraydst, doubleiterFactor=1.,RNG*rng=0)

該函數(shù)表示隨機打亂1D數(shù)組dst里面的數(shù)據(jù)，隨機打亂的方式由隨機數(shù)發(fā)生器rng決定。iterFactor為隨機打亂數(shù)據(jù)對數(shù)的因子，總共打亂的數(shù)據(jù)對數(shù)為：dst.rows*dst.cols*iterFactor，因此如果為0，表示沒有打亂數(shù)據(jù)。

Class TermCriteria

類TermCriteria 一般表示迭代終止的條件，如果為CV_TERMCRIT_ITER，則用最大迭代次數(shù)作為終止條件，如果為CV_TERMCRIT_EPS則用精度作為迭代條件，如果為CV_TERMCRIT_ITER+CV_TERMCRIT_EPS則用最大迭代次數(shù)或者精度作為迭代條件，看哪個條件先滿足。

doublekmeans(InputArraydata, intK, InputOutputArraybestLabels, TermCriteriacriteria, intattempts, intflags, OutputArraycenters=noArray())

該函數(shù)為kmeans聚類算法實現(xiàn)函數(shù)。參數(shù)data表示需要被聚類的原始數(shù)據(jù)集合，一行表示一個數(shù)據(jù)樣本，每一個樣本的每一列都是一個屬性；參數(shù)k表示需要被聚類的個數(shù)；參數(shù)bestLabels表示每一個樣本的類的標簽，是一個整數(shù)，從0開始的索引整數(shù)；參數(shù)criteria表示的是算法迭代終止條件；參數(shù)attempts表示運行kmeans的次數(shù)，取結(jié)果最好的那次聚類為最終的聚類，要配合下一個參數(shù)flages來使用；參數(shù)flags表示的是聚類初始化的條件。其取值有3種情況，如果為KMEANS_RANDOM_CENTERS，則表示為隨機選取初始化中心點，如果為KMEANS_PP_CENTERS則表示使用某一種算法來確定初始聚類的點；如果為KMEANS_USE_INITIAL_LABELS，則表示使用用戶自定義的初始點，但是如果此時的attempts大于1，則后面的聚類初始點依舊使用隨機的方式；參數(shù)centers表示的是聚類后的中心點存放矩陣。該函數(shù)返回的是聚類結(jié)果的緊湊性，其計算公式為：

注意點一：

這是說個我自己不理解的地方：fill(InputOutputArraymat, intdistType, InputArraya, InputArrayb, boolsaturateRange=false)

這里的InputArraya, InputArrayb------>>>分別用了Scalar(center.x, center.y, 0, 0), Scalar(img.cols*0.05, img.rows*0.05, 0, 0)去替換

去查了一下手冊：InputArray這個接口類可以是Mat、Mat_、Mat_、vector、vector>、vector。沒有提到Scalar()可以使用

特意定義了一個：InputArray test = Scalar(1,1);這個又是可以的，定義Mat不行，Vector也不行，這個真的不知道什么原因，有時間得去看源碼a,b的使用。

//----下面的定義都是錯誤的，運行的結(jié)果都不對，原因暫時不知道

Mat a = (Mat_(1, 2) << center.x, center.y);

Mat b = (Mat_(1, 2) << img.cols*0.05, img.rows*0.05);

InputArray a1 = Scalar(center.x, center.y);

InputArray b1 = Scalar(img.cols*0.05, img.rows*0.05);

Mat a2 = a1.getMat();

Mat b2 = b1.getMat();

Mat c(1, 2, CV_8UC1);

c = Scalar(center.x, center.y);

Mat c1(1, 2, CV_8UC1);

c1 = Scalar(img.cols*0.05, img.rows*0.05);

rng.fill(pointChunk, RNG::NORMAL, a, b, 0);

注意點二：

kmeans()函數(shù)的輸入只接受data0.dims <= 2 && type == CV_32F && K > 0 ，

第一個dims一般都不會越界（三維不行）

第二個參數(shù)CV_32F == float，千萬別帶入CV_8U == uchar

第三個參數(shù)不用說了，設(shè)置的種類肯定是大于0的

注意點三：

opencv里面k-means函數(shù)的樣本數(shù)據(jù)、標簽、中心點的存儲：

#include

#include

using namespace cv;

using namespace std;

int main(int argc, char** argv) {

Mat img(500, 500, CV_8UC3);

RNG rng(12345);

const int Max_nCluster = 5;

Scalar colorTab[] = {

Scalar(0, 0, 255),

Scalar(0, 255, 0),

Scalar(255, 0, 0),

Scalar(0, 255, 255),

Scalar(255, 0, 255)

};

//InputArray a = Scalar(1,1);

int numCluster = rng.uniform(2, Max_nCluster + 1);//隨機類數(shù)

int sampleCount = rng.uniform(5, 1000);//樣本點數(shù)量

Mat matPoints(sampleCount, 1, CV_32FC2);//樣本點矩陣：sampleCount X 2

Mat labels;

Mat centers;

// 生成隨機數(shù)

for (int k = 0; k < numCluster; k++) {

Point center;//隨機產(chǎn)生中心點

center.x = rng.uniform(0, img.cols);

center.y = rng.uniform(0, img.rows);

Mat pointChunk = matPoints.rowRange( k*sampleCount / numCluster,

(k + 1)*sampleCount / numCluster);

//-----這句話的意思我不明白作用是什么，沒意義?。?/p>

/*Mat pointChunk = matPoints.rowRange(k*sampleCount / numCluster,

k == numCluster - 1 ? sampleCount : (k + 1)*sampleCount / numCluster);*/

//-----符合高斯分布的隨機高斯

rng.fill(pointChunk, RNG::NORMAL, Scalar(center.x, center.y, 0, 0), Scalar(img.cols*0.05, img.rows*0.05, 0, 0));

}

randShuffle(matPoints, 1, &rng);//打亂高斯生成的數(shù)據(jù)點順序

// 使用KMeans

kmeans(matPoints, numCluster, labels, TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1), 3, KMEANS_PP_CENTERS, centers);

// 用不同顏色顯示分類

img = Scalar::all(255);

for (int i = 0; i < sampleCount; i++) {

int index = labels.at(i);

Point p = matPoints.at(i);

circle(img, p, 2, colorTab[index], -1, 8);

}

// 每個聚類的中心來繪制圓

for (int i = 0; i < centers.rows; i++) {

int x = centers.at(i, 0);

int y = centers.at(i, 1);

printf("c.x= %d, c.y=%d", x, y);

circle(img, Point(x, y), 40, colorTab[i], 1, LINE_AA);

}

imshow("KMeans-Data-Demo", img);

waitKey(0);

return 0;

}

分類代碼：

#include

#include

using namespace cv;

using namespace std;

RNG rng(12345);

const int Max_nCluster = 5;

int main(int argc, char** argv) {

//Mat img(500, 500, CV_8UC3);

Mat inputImage = imread("1.jpg");

assert(!inputImage.data);

Scalar colorTab[] = {

Scalar(0, 0, 255),

Scalar(0, 255, 0),

Scalar(255, 0, 0),

Scalar(0, 255, 255),

Scalar(255, 0, 255)

};

Mat matData = Mat::zeros(Size(inputImage.channels(), inputImage.rows*inputImage.cols), CV_32FC1);

int ncluster = 5; //rng.uniform(2, Max_nCluster + 1);//聚類數(shù)量

Mat label;//聚類標簽

Mat centers(ncluster, 1, matData.type());

for (size_t i = 0; i < inputImage.rows; i++)//把圖像存儲到樣本容器

{

uchar* ptr = inputImage.ptr(i);

for (size_t j = 0; j < inputImage.cols; j++)

{

matData.at(i*inputImage.cols + j, 0) = ptr[j*inputImage.channels()];

matData.at(i*inputImage.cols + j, 1) = ptr[j*inputImage.channels() +1];

matData.at(i*inputImage.cols + j, 2) = ptr[j*inputImage.channels() +2];

}

}

Mat result = Mat::zeros(inputImage.size(), inputImage.type());

TermCriteria criteria = TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 20, 0.1);

kmeans(matData, ncluster, label, criteria, 3, KMEANS_PP_CENTERS, centers);

for (size_t i = 0; i < inputImage.rows; i++)

{

for (size_t j = 0; j < inputImage.cols; j ++)

{

int index = label.at(i*inputImage.cols + j,0);

result.at(i, j)[0] = colorTab[index][0];

result.at(i, j)[1] = colorTab[index][1];

result.at(i, j)[2] = colorTab[index][2];

}

}

imshow("12", result);

waitKey(0);

return 0;

}