OpenCV中的KMeans算法介紹與應(yīng)用
我是51CTO學(xué)院講師賈志剛，在51CTO學(xué)院 “4.20 IT充電節(jié)”(4月19~20日) 到來之際，和大家分享一下《OpenCV中KMeans算法應(yīng)用》的經(jīng)驗。正文來啦~~~
一、KMeans算法介紹
KMeans算法是MacQueen在1967年提出的，是最簡單與最常見的數(shù)據(jù)分類方法之一。它做為一種常見數(shù)據(jù)分析技術(shù)在機器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識別、圖像分析等領(lǐng)域都有應(yīng)用。如果從分類角度看，KMeans屬于硬分類即需要人為指定分類數(shù)目，而MeanSift分類方法則可以根據(jù)收斂條件自動決定分類數(shù)目。從學(xué)習(xí)方法上來說，KMeans屬于非監(jiān)督學(xué)習(xí)方法即整個學(xué)習(xí)過程中不需要人為干預(yù)的學(xué)習(xí)方法，自動完成整個數(shù)據(jù)集合分類。對于給定的數(shù)據(jù)集合DS (Data Set)與輸入的分類數(shù)目K，KMeans的整個工作原理可以描述如下：
1. 根據(jù)輸入的分類數(shù)目K定義K個分類，每個分類選擇一個中心點
2. 對DS中每個數(shù)據(jù)點做如下操作：
- 計算它與K個中心點之間的距離
- 把數(shù)據(jù)點指定屬于K個中心點中距離最近的中心點所屬的分類
3. 對K個分類中每個數(shù)據(jù)點計算平均值得到新的K個中心點
4. 比較新K個中心點之間與第一步中已經(jīng)存在的K個中心差值
- 當(dāng)兩者之間的差值沒有變化或者小于指定閾值，結(jié)束分類
- 當(dāng)兩者之間的差值或者條件不滿足時候，用新計算的中心點值做為K個分類的新中心點，繼續(xù)執(zhí)行2~4步。直到條件滿足退出。
從數(shù)學(xué)的角度來說KMeans就是要找到K個分類而且他們的中心點到各個分類中各個數(shù)據(jù)的之間差值平方和最小化，而實現(xiàn)這個過程就是要通過上述2~4步不斷的迭代執(zhí)行，直到收斂為止。公式表示如下：
以上是KMeans算法的基本思想，想要實現(xiàn)或者應(yīng)用該算法有三個注意點值得關(guān)注：
1. 初始的K個分類中每個分類的中心點選擇，多數(shù)的算法實現(xiàn)都是支持隨機選擇與人工指定兩種方式，OpenCV中的KMeans實現(xiàn)同樣支持這兩種方式。
2. 多維數(shù)據(jù)支持，多數(shù)時候我們要分類的特征對象的描述數(shù)據(jù)不止一個數(shù)據(jù)特征，而是一個特征向量來表示，OpenCV中通過Mat對象構(gòu)建實現(xiàn)對多維數(shù)據(jù)KMeans分類支持。
3. 收斂條件 - 一般情況下在達到指定的迭代次數(shù)或者兩次RSS差值小于給定閾值的情況下，結(jié)束執(zhí)行分類處理，輸出最終分類結(jié)果。
下圖是一個例子，黑色的點代表數(shù)據(jù)點，十字表示中心點位置，初始輸入的分類數(shù)目K=2時，KMeans各步執(zhí)行結(jié)果：
二、OpenCV中KMeans相關(guān)函數(shù)說明
KMeans是OpenCV核心模塊的一個API函數(shù)。
各個參數(shù)的詳細(xì)解釋如下：
- data表示輸入的數(shù)據(jù)集合，可以一維或者多維數(shù)據(jù)，類型是Mat類型，比如：
Mat points(count, 2, CV_32F)
表示數(shù)據(jù)集合是二維，浮點數(shù)數(shù)據(jù)集。
- K表示分類的數(shù)目，最常見的是K=2表示二分類。
-bestLabels表示計算之后各個數(shù)據(jù)點的最終的分類索引，是一個INT類型的Mat對象。
-criteria表示算法終止的條件，達到最大循環(huán)數(shù)目或者指定的精度閾值算法就停止繼續(xù)分類迭代計算。
- attempts表示為了獲得最佳的分類效果，算法要不同的初始分類嘗試次數(shù)
- flags表示選擇初始中心點選擇方法用哪一種
KMEANS_RANDOM_CENTERS 表示隨機選擇中心點
KMEANS_PP_CENTERS 基于中心化算法選擇
KMEANS_USE_INITIAL_LABELS第一次分類中心點用輸入的中心點
- centers表示輸出的每個分類的中心點數(shù)據(jù)。
三、應(yīng)用案例-利用KMeans實現(xiàn)圖像分割
KMeans在圖像處理中經(jīng)典應(yīng)用場景就是根據(jù)用戶輸入的分類數(shù)目實現(xiàn)圖像自動區(qū)域分割，本例就是基于OpenCV KMeans函數(shù)實現(xiàn)圖像的自動分割， 對彩色圖像來說，每個像素點都有RGB三個分量，整個圖像可以看成是一個3維數(shù)據(jù)集合，只要把這個三維數(shù)據(jù)集作為輸入?yún)?shù)傳給KMeans函數(shù)即可，算法執(zhí)行完畢之后，根據(jù)分類標(biāo)記的索引設(shè)置不同的顏色即可。所以演示程序的實現(xiàn)步驟如下：
1. 將輸入圖像轉(zhuǎn)換為數(shù)據(jù)集合
2. 使用KMeans算法對數(shù)據(jù)實現(xiàn)分類
3. 根據(jù)每個數(shù)據(jù)點的分類索引，對圖像重新填充顏色，顯示分割后圖像。
運行效果如下：
完整的代碼實現(xiàn)如下：
- #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到數(shù)據(jù)集轉(zhuǎn)換
- 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數(shù)據(jù)分類
- TermCriteria criteria = TermCriteria(CV_TERMCRIT_EPS + CV_TERMCRIT_ITER, 10, 1.0);
- kmeans(points, clusterCount, labels, criteria, 3, KMEANS_PP_CENTERS, centers);
- // 顯示圖像分割結(jié)果
- 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;
- }
作者介紹
賈志剛：圖書作者，51CTO學(xué)院簽約講師，專注于圖像處理相關(guān)領(lǐng)域，精通OpenCV、ImageJ等開發(fā)框架。
51CTO學(xué)院 4.20 IT充電節(jié)
(19-20號兩天，100門視頻課程免單搶，更有視頻課程會員享6折，非會員享7折，套餐折上8折，微職位立減2000元鉅惠)
活動鏈接：http://edu.51cto.com/activity/lists/id-47.html?wenzhang
相關(guān)視頻教程：
《OpenCV視頻分析與對象跟蹤實戰(zhàn)教程》
