OpenCV中的KMeans算法介紹與應用
一、KMeans算法介紹
KMeans算法是MacQueen在1967年提出的，是最簡單與最常見的數據分類方法之一。它做為一種常見數據分析技術在機器學習、數據挖掘、模式識別、圖像分析等領域都有應用。如果從分類角度看，KMeans屬于硬分類即需要人為指定分類數目，而MeanSift分類方法則可以根據收斂條件自動決定分類數目。從學習方法上來說，KMeans屬于非監督學習方法即整個學習過程中不需要人為干預的學習方法，自動完成整個數據集合分類。對于給定的數據集合DS (Data Set)與輸入的分類數目K，KMeans的整個工作原理可以描述如下：
1. 根據輸入的分類數目K定義K個分類，每個分類選擇一個中心點
2. 對DS中每個數據點做如下操作：
- 計算它與K個中心點之間的距離
- 把數據點指定屬于K個中心點中距離最近的中心點所屬的分類
3. 對K個分類中每個數據點計算平均值得到新的K個中心點
4. 比較新K個中心點之間與第一步中已經存在的K個中心差值
- 當兩者之間的差值沒有變化或者小于指定閾值，結束分類
- 當兩者之間的差值或者條件不滿足時候，用新計算的中心點值做為K個分類的新中心點，繼續執行2~4步。直到條件滿足退出。
從數學的角度來說KMeans就是要找到K個分類而且他們的中心點到各個分類中各個數據的之間差值平方和最小化，而實現這個過程就是要通過上述2~4步不斷的迭代執行，直到收斂為止。公式表示如下：
以上是KMeans算法的基本思想，想要實現或者應用該算法有三個注意點值得關注：
1. 初始的K個分類中每個分類的中心點選擇，多數的算法實現都是支持隨機選擇與人工指定兩種方式，OpenCV中的KMeans實現同樣支持這兩種方式。
2. 多維數據支持，多數時候我們要分類的特征對象的描述數據不止一個數據特征，而是一個特征向量來表示，OpenCV中通過Mat對象構建實現對多維數據KMeans分類支持。
3. 收斂條件 - 一般情況下在達到指定的迭代次數或者兩次RSS差值小于給定閾值的情況下，結束執行分類處理，輸出最終分類結果。
下圖是一個例子，黑色的點代表數據點，十字表示中心點位置，初始輸入的分類數目K=2時，KMeans各步執行結果：
二、OpenCV中KMeans相關函數說明
KMeans是OpenCV核心模塊的一個API函數。
各個參數的詳細解釋如下：
- data表示輸入的數據集合，可以一維或者多維數據，類型是Mat類型，比如：
Mat points(count, 2, CV_32F)
表示數據集合是二維，浮點數數據集。
- K表示分類的數目，最常見的是K=2表示二分類。
-bestLabels表示計算之后各個數據點的最終的分類索引，是一個INT類型的Mat對象。
-criteria表示算法終止的條件，達到最大循環數目或者指定的精度閾值算法就停止繼續分類迭代計算。
- attempts表示為了獲得最佳的分類效果，算法要不同的初始分類嘗試次數
- flags表示選擇初始中心點選擇方法用哪一種
KMEANS_RANDOM_CENTERS 表示隨機選擇中心點
KMEANS_PP_CENTERS 基于中心化算法選擇
KMEANS_USE_INITIAL_LABELS第一次分類中心點用輸入的中心點
- centers表示輸出的每個分類的中心點數據。
三、應用案例-利用KMeans實現圖像分割
KMeans在圖像處理中經典應用場景就是根據用戶輸入的分類數目實現圖像自動區域分割，本例就是基于OpenCV KMeans函數實現圖像的自動分割， 對彩色圖像來說，每個像素點都有RGB三個分量，整個圖像可以看成是一個3維數據集合，只要把這個三維數據集作為輸入參數傳給KMeans函數即可，算法執行完畢之后，根據分類標記的索引設置不同的顏色即可。所以演示程序的實現步驟如下：
1. 將輸入圖像轉換為數據集合
2. 使用KMeans算法對數據實現分類
3. 根據每個數據點的分類索引，對圖像重新填充顏色，顯示分割后圖像。
運行效果如下：
完整的代碼實現如下：
#include<opencv2/opencv.hpp>
#include<iostream>
usingnamespace cv;
usingnamespace std;
int main(intargc, char** argv) {
Mat src = imread("D:/vcprojects/images/toux.jpg");
imshow("input", src);
int width = src.cols;
int height = src.rows;
int dims = src.channels();
// 初始化定義
int sampleCount = width*height;
int clusterCount = 4;
Mat points(sampleCount, dims, CV_32F, Scalar(10));
Mat labels;
Mat centers(clusterCount, 1, points.type());
// 圖像RGB到數據集轉換
int index = 0;
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
index = row*width + col;
Vec3b rgb = src.at<Vec3b>(row, col);
points.at<float>(index, 0) = static_cast<int>(rgb[0]);
points.at<float>(index, 1) = static_cast<int>(rgb[1]);
points.at<float>(index, 2) = static_cast<int>(rgb[2]);
}
}
// 運行K-Means數據分類
TermCriteria criteria = TermCriteria(CV_TERMCRIT_EPS + CV_TERMCRIT_ITER, 10, 1.0);
kmeans(points, clusterCount, labels, criteria, 3, KMEANS_PP_CENTERS, centers);
// 顯示圖像分割結果
Mat result = Mat::zeros(src.size(), CV_8UC3);
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
index = row*width + col;
int label = labels.at<int>(index, 0);
if (label == 1) {
result.at<Vec3b>(row, col)[0] = 255;
result.at<Vec3b>(row, col)[1] = 0;
result.at<Vec3b>(row, col)[2] = 0;
}
elseif (label == 2) {
result.at<Vec3b>(row, col)[0] = 0;
result.at<Vec3b>(row, col)[1] = 255;
result.at<Vec3b>(row, col)[2] = 0;
}
elseif (label == 3) {
result.at<Vec3b>(row, col)[0] = 0;
result.at<Vec3b>(row, col)[1] = 0;
result.at<Vec3b>(row, col)[2] = 255;
}
elseif (label == 0) {
result.at<Vec3b>(row, col)[0] = 0;
result.at<Vec3b>(row, col)[1] = 255;
result.at<Vec3b>(row, col)[2] = 255;
}
}
}
imshow("kmeans-demo", result);
//imwrite("D:/vcprojects/images/cvtest.png", result);
waitKey(0);
return 0;
}
來自：http://developer.51cto.com/art/201704/536860.htm