About BBS

その他の関数

作成者: 怡土順一, 最終変更者: 怡土順一, 最終変更リビジョン: 366, 最終変更日時: 2008-02-11 21:51:13 +0900 (月, 11 2月 2008)
This is a local copy taken at 2010/09/20. CLICK HERE to the original page at opencv.jp.

■ クラスタリング

クラスタリングとは,与えられたデータを,一定の規則に従っていくつかの組(クラスタ)に分類する処理である. 画像処理の分野では,画像そのものの分類はもちろん,各画像領域の分類や減色処理などに利用される. クラスタリングを行うための代表的な手法として, 初期データ数個のクラスタから各クラスタを階層的に結合していく手法, ニューラルネットの一種である自己組織化マップ(Self-organizing maps, SOM)などの手法, ユーザが指定した個数のクラスタにデータを分割するK-Means法(k平均法)などが挙げられる. また,さらに,データが複数のクラスタにまたがる様な手法や,特徴空間距離以外のデー タを利用する手法など,多種の手法が存在する.

サンプル


K-means法によるクラスタリング cvKMeans2

K-means法で,サンプルのクラスタリングを行う.これは,OpenCV付属のサンプルコード(とほぼ同一)である.

サンプルコード

#include <cv.h> #include <highgui.h> #include <time.h> #define MAX_CLUSTERS (5) int main (int argc, char **argv) { CvScalar color_tab[MAX_CLUSTERS] = { CV_RGB (255, 0, 0), CV_RGB (0, 255, 0), CV_RGB (100, 100, 255), CV_RGB (255, 0, 255), CV_RGB (255, 255, 0) }; IplImage *img = cvCreateImage (cvSize (500, 500), IPL_DEPTH_8U, 3); CvRNG rng = cvRNG (time (NULL)); CvPoint ipt; while (1) { int c; int k, cluster_count = cvRandInt (&rng) % MAX_CLUSTERS + 1; int i, sample_count = cvRandInt (&rng) % 1000 + MAX_CLUSTERS; CvMat *points = cvCreateMat (sample_count, 1, CV_32FC2); CvMat *clusters = cvCreateMat (sample_count, 1, CV_32SC1); // (1)複数のガウシアンから成るランダムサンプルを生成する for (k = 0; k < cluster_count; k++) { CvPoint center; CvMat point_chunk; center.x = cvRandInt (&rng) % img->width; center.y = cvRandInt (&rng) % img->height; cvGetRows (points, &point_chunk, k * sample_count / cluster_count, k == cluster_count - 1 ? sample_count : (k + 1) * sample_count / cluster_count, 1); cvRandArr (&rng, &point_chunk, CV_RAND_NORMAL, cvScalar (center.x, center.y, 0, 0), cvScalar (img->width * 0.1, img->height * 0.1, 0, 0)); } // (2)ランダムサンプルをシャッフルする for (i = 0; i < sample_count / 2; i++) { CvPoint2D32f *pt1 = (CvPoint2D32f *) points->data.fl + cvRandInt (&rng) % sample_count; CvPoint2D32f *pt2 = (CvPoint2D32f *) points->data.fl + cvRandInt (&rng) % sample_count; CvPoint2D32f temp; CV_SWAP (*pt1, *pt2, temp); } // (3)K-menas法によるクラスタリング cvKMeans2 (points, cluster_count, clusters, cvTermCriteria (CV_TERMCRIT_EPS + CV_TERMCRIT_ITER, 10, 1.0)); // (4)クラスタ毎に色を変えてサンプルを描画する cvZero (img); for (i = 0; i < sample_count; i++) { int cluster_idx = clusters->data.i[i]; ipt.x = (int) points->data.fl[i * 2]; ipt.y = (int) points->data.fl[i * 2 + 1]; cvCircle (img, ipt, 2, color_tab[cluster_idx], CV_FILLED, CV_AA, 0); } cvReleaseMat (&points); cvReleaseMat (&clusters); // (5)画像を表示,"Esc"キーが押されたときに終了 cvNamedWindow ("Clusters", CV_WINDOW_AUTOSIZE); cvShowImage ("Clusters", img); c = cvWaitKey (0); if (c == '\x1b') break; cvReleaseMat (&clusters); cvReleaseMat (&points); } cvDestroyWindow ("Clusters"); cvReleaseImage (&img); return 0; }

// (1)複数のガウシアンから成るランダムサンプルを生成する
まず,クラスタリング対象データとなるデータ集合を作成する. 各データは2次元座標を持つ点であり,その全データは,1×sample_countの行列(各要素は,CV_32FC2)pointsで表される. 関数cvGetRowsにより擬似的に(クラスタ数分に)分割された部分行列を, 正規分布するデータで初期化する.このときの平均は,最初にランダムに生成された値,分散は,0.1*画像のサイズ,である. この行列の初期化には,関数cvRandArr()を用いる.

// (2)ランダムサンプルをシャッフルする
また,生成されたサンプルは,この時点では各クラスタごとに正しく整列しているので, これを,マクロCV_SWAP()によりシャッフルする. マクロ CV_SWAPは,cxtypes.h 内で,次の様に定義される.

#define CV_SWAP(a,b,t) ((t) = (a), (a) = (b), (b) = (t))

// (3)K-menas法によるクラスタリング
関数cvKMeans2()により,K-menas法によるクラスタリングを行う. 引数には,それぞれ,サンプルデータ,クラスタ数,出力クラスタ,終了条件,を与える. 出力クラスタには,各サンプルがどのクラスタに属するかを示すクラスタインデックスが入る. また,終了条件は,繰り返し計算の最大数と,センターの各ステップにおける 移動距離の最小値が与えられ,このどちらかが満足されると計算が終了する.

// (4)クラスタ毎に色を変えてサンプルを描画する
clusters->data.i[i]に,i番めのサンプルが属するクラスタのインデックス (int型)が保存されているので, それに従い,全てのサンプルを色分けして円で描画する.

// (5)画像を表示,"Esc"キーが押されたときに終了
実際に画像を表示し,ユーザの入力を待つ. "Esc"キーが押された場合は終了し,それ以外の入力が合った場合は,再びランダムサンプルを生成する.

実行結果例

各クラスタを代表する最初のセンターは,OpenCV内部でランダムに初期化されるため, 必ずしも適切なクラスタリング結果になるわけではない.


クラスタリングによる減色処理 cvKMeans2

k-means法によるクラスタリングを利用して,非常に単純な減色を行う

サンプルコード

#include <cv.h> #include <highgui.h> #define MAX_CLUSTERS (32) /* クラスタ数 */ int main (int argc, char **argv) { int i, size; IplImage *src_img = 0, *dst_img = 0; CvMat *clusters; CvMat *points; CvMat *color = cvCreateMat (MAX_CLUSTERS, 1, CV_32FC3); CvMat *count = cvCreateMat (MAX_CLUSTERS, 1, CV_32SC1); // (1)画像を読み込む if (argc != 2 || (src_img = cvLoadImage (argv[1], CV_LOAD_IMAGE_COLOR)) == 0) return -1; size = src_img->width * src_img->height; dst_img = cvCloneImage (src_img); clusters = cvCreateMat (size, 1, CV_32SC1); points = cvCreateMat (size, 1, CV_32FC3); // (2)ピクセルの値を行列へ代入 for (i = 0; i < size; i++) { points->data.fl[i * 3 + 0] = (uchar) src_img->imageData[i * 3 + 0]; points->data.fl[i * 3 + 1] = (uchar) src_img->imageData[i * 3 + 1]; points->data.fl[i * 3 + 2] = (uchar) src_img->imageData[i * 3 + 2]; } // (3)クラスタリング cvKMeans2 (points, MAX_CLUSTERS, clusters, cvTermCriteria (CV_TERMCRIT_EPS + CV_TERMCRIT_ITER, 10, 1.0)); // (4)各クラスタの平均値を計算 cvSetZero (color); cvSetZero (count); for (i = 0; i < size; i++) { int idx = clusters->data.i[i]; int j = ++count->data.i[idx];; color->data.fl[idx * 3 + 0] = color->data.fl[idx * 3 + 0] * (j - 1) / j + points->data.fl[i * 3 + 0] / j; color->data.fl[idx * 3 + 1] = color->data.fl[idx * 3 + 1] * (j - 1) / j + points->data.fl[i * 3 + 1] / j; color->data.fl[idx * 3 + 2] = color->data.fl[idx * 3 + 2] * (j - 1) / j + points->data.fl[i * 3 + 2] / j; } // (5)クラスタ毎に色を描画 for (i = 0; i < size; i++) { int idx = clusters->data.i[i]; dst_img->imageData[i * 3 + 0] = (char) color->data.fl[idx * 3 + 0]; dst_img->imageData[i * 3 + 1] = (char) color->data.fl[idx * 3 + 1]; dst_img->imageData[i * 3 + 2] = (char) color->data.fl[idx * 3 + 2]; } // (6)画像を表示,キーが押されたときに終了 cvNamedWindow ("src", CV_WINDOW_AUTOSIZE); cvShowImage ("src", src_img); cvNamedWindow ("low-color", CV_WINDOW_AUTOSIZE); cvShowImage ("low-color", dst_img); cvWaitKey (0); cvDestroyWindow ("src"); cvDestroyWindow ("low-color"); cvReleaseImage (&src_img); cvReleaseImage (&dst_img); cvReleaseMat (&clusters); cvReleaseMat (&points); cvReleaseMat (&color); cvReleaseMat (&count); return 0; }

// (1)画像を読み込む
関数 vcLoadImage() により,入力像をカラー画像として読み込む.

// (2)ピクセルの値を行列へ代入
各ピクセルをクラスタリングするために,各ピクセルのRGBチャンネルの値を CvMat 型の変数に代入する.

// (3)クラスタリング
前述のサンプルと同様に,関数 cvKMeans2() により,k-means法を利用したクラスタリングを行う. クラスタ数はあらかじめ定義されており,これが,減色後の色数となる.

// (4)各クラスタの平均値を計算
クラスタリングされた各ピクセル群を,そのクラスタのセンターで代表できれば処理が簡単であるが, OpenCVでは,関数 cvKMeans2() によりクラスタリングされた各クラスタのセンターにアクセスできない. そこで,このサンプルではクラスタリング後の各クラスタの(K個の代表値ではない)完全な平均値を求め,それを各クラスタの代表値とする.

// (5)クラスタ毎に色を描画
各クラスタのピクセルを,求められた平均値で埋める.

// (6)画像を表示,キーが押されたときに終了
実際に,入力画像とクラスタリング(減色)された画像を表示し,何かキーが押されるまで待つ.

このようにK-means法を用いて減色を行う事は,色による画像の領域分割と等しい. それらの処理については, 画像分割,領域結合,輪郭検出 を参照の事.

実行結果例

入力画像 4色 8色 16色 32色

OpenCV-1.0 リファレンス マニュアル
OpenCV-1.1pre リファレンス マニュアル
OpenCVサンプルコード


画素値の直接操作
部分画像のシャッフル
画像の連結
画像のコピー
画像形状の変形
タイリング
画像の反転
逆行列(擬似逆行列)の計算
色空間の写像
離散フーリエ変換
階層構造を持つ輪郭の座標取得
図形の描画
ポリゴンの描画
凸ポリゴンの描画
テキストの描画
IplImage構造体情報の保存
マップのシーケンスを保存
IplImage構造体情報の読み込み
マップのシーケンスを読み込む
K-means法によるクラスタリング
クラスタリングによる減色処理
エッジの検出
コーナーの検出
並進移動のためのピクセルサンプリング
回転移動のためのピクセルサンプリング
画像のサイズ変更
画像のアフィン変換(1)
画像のアフィン変換(2)
画像の透視投影変換
全方位画像の透視投影変換
モルフォロジー変換
平滑化
ユーザ定義フィルタ
境界線の作成
画像の二値化
画像の二値化(大津の手法)
画像ピラミッドの作成
画像ピラミッドを用いた画像の領域分割
平均値シフト法による画像のセグメント化
Watershedアルゴリズムによる画像の領域分割
輪郭の検出と描画
画像のモーメントを計算
ハフ変換による直線検出
ハフ変換による円検出
距離変換とその可視化
不要オブジェクトの除去
ヒストグラムの描画
ヒストグラム間の距離
二次元のヒストグラム
バックプロジェクションパッチ
ヒストグラムの均一化
テンプレートマッチング
形状のマッチング
点列を包含する矩形
輪郭領域の面積と輪郭の長さ
二つの矩形を包含する矩形
楕円のフィッティング
点列を包含する図形
動的背景更新による物体検出
snakeによる輪郭追跡(静止画)
オプティカルフロー1
オプティカルフロー2
オプティカルフロー3
Condensation
顔の検出
カメラキャリブレーション
歪み補正
マップを利用した歪み補正
サポートベクターマシン
画像の各ピクセル値を特徴ベクトルとしたSVMの学習
画像の各ピクセル値を特徴ベクトルとしたSVMによる物体検出
マウスイベントの取得
トラックバーの利用
カメラからの画像キャプチャ
動画としてファイルへ書き出す
ラベリング