クラスタリング ===================== .. highlight:: c .. index:: KMeans2 .. _KMeans2: KMeans2 ------- `id=0.497149842278 Comments from the Wiki `__ .. cfunction:: int cvKMeans2(const CvArr* samples, int nclusters, CvArr* labels, CvTermCriteria termcrit, int attempts=1, CvRNG* rng=0, int flags=0, CvArr* centers=0, double* compactness=0) ベクトルの集合を,指定された数のクラスタに分割します. :param samples: 入力サンプルの浮動小数点型行列,1つの行が1つのサンプルを表します. :param nclusters: 分割クラスタ数. :param labels: 各サンプルが属するクラスタのインデックスが保存される,整数型の出力ベクトル. :param termcrit: 反復数の最大値と(または),精度(連続する反復処理間においてクラスタ中心が移動する距離)の指定. :param attempts: このアルゴリズムが,異なる初期ラベルを与えられて実行される回数.これは,最もコンパクトな分割を行うラベル(最後のパラメータを参照)を返します. :param rng: オプションである外部乱数発生器.この関数の挙動を完全に制御したい場合に用いられます. :param flags: 0 あるいは ``CV_KMEANS_USE_INITIAL_LABELS`` .後者の場合,最初の試行で(だけ)は,ランダムに生成されるラベルの代わりに,ユーザが与えたラベルを初期推定値として用います.2回目以降の試行では,ランダムに生成されたラベルを利用します. :param centers: オプション.クラスタ中心が出力される配列. :param compactness: オプション出力.各試行後に :math:`\sum_i ||\texttt{samples}_i - \texttt{centers}_{\texttt{labels}_i}||^2` として求められます.最も良い値(最小値)が選択され,この関数はそれに対応するラベルを返します.基本的に次のようにすれば,ユーザはこの関数の基本部分だけを利用することができる.まず,試行回数を1にセットし,独自アルゴリズムを利用してラベルを毎回初期化します( ``flags`` = ``CV_KMEANS_USE_INITIAL_LABELS`` ).そして,出力されるコンパクトネスやその他の基準に基づいて,最良のクラスタリグを選択します 関数 ``cvKMeans2`` は, ``nclusters`` 個のクラスタの中心を求め,入力サンプルを各クラスタに分類する k-means アルゴリズムの実装です.また出力として,行列 ``samples`` の 行 :math:`i` で与えられたサンプルが属するクラスタのインデックスが, :math:`\texttt{labels}_i` に格納されます. .. code-block:: c #include "cxcore.h" #include "highgui.h" void main( int argc, char** argv ) { #define MAX_CLUSTERS 5 CvScalar color_tab[MAX_CLUSTERS]; IplImage* img = cvCreateImage( cvSize( 500, 500 ), 8, 3 ); CvRNG rng = cvRNG(0xffffffff); color_tab[0] = CV_RGB(255,0,0); color_tab[1] = CV_RGB(0,255,0); color_tab[2] = CV_RGB(100,100,255); color_tab[3] = CV_RGB(255,0,255); color_tab[4] = CV_RGB(255,255,0); cvNamedWindow( "clusters", 1 ); for(;;) { int k, cluster_count = cvRandInt(&rng) int i, sample_count = cvRandInt(&rng) CvMat* points = cvCreateMat( sample_count, 1, CV_32FC2 ); CvMat* clusters = cvCreateMat( sample_count, 1, CV_32SC1 ); /* 多変量ガウス分布からランダムサンプルを生成します */ for( k = 0; k < cluster_count; k++ ) { CvPoint center; CvMat point_chunk; center.x = cvRandInt(&rng) center.y = cvRandInt(&rng) cvGetRows( points, &point_chunk, k*sample_count/cluster_count, (k == (cluster_count - 1)) ? sample_count : (k+1)*sample_count/cluster_count ); cvRandArr( &rng, &point_chunk, CV_RAND_NORMAL, cvScalar(center.x,center.y,0,0), cvScalar(img->width/6, img->height/6,0,0) ); } /* サンプルをシャッフルします */ for( i = 0; i < sample_count/2; i++ ) { CvPoint2D32f* pt1 = (CvPoint2D32f*)points->data.fl + cvRandInt(&rng) CvPoint2D32f* pt2 = (CvPoint2D32f*)points->data.fl + cvRandInt(&rng) CvPoint2D32f temp; CV_SWAP( *pt1, *pt2, temp ); } cvKMeans2( points, cluster_count, clusters, cvTermCriteria( CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 10, 1.0 )); cvZero( img ); for( i = 0; i < sample_count; i++ ) { CvPoint2D32f pt = ((CvPoint2D32f*)points->data.fl)[i]; int cluster_idx = clusters->data.i[i]; cvCircle( img, cvPointFrom32f(pt), 2, color_tab[cluster_idx], CV_FILLED ); } cvReleaseMat( &points ); cvReleaseMat( &clusters ); cvShowImage( "clusters", img ); int key = cvWaitKey(0); if( key == 27 ) break; } } .. .. index:: SeqPartition .. _SeqPartition: SeqPartition ------------ `id=0.569473619333 Comments from the Wiki `__ .. cfunction:: int cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, CvCmpFunc is_equal, void* userdata ) シーケンスを同値類(同値クラス)に分割します. :param seq: 分割されるシーケンス. :param storage: 同値クラスラベルのシーケンスが保存されるストレージブロック.NULLの場合は,ラベルの出力場所として ``seq->storage`` が利用されます. :param labels: 出力パラメータ.入力シーケンスの各要素に割り振られた(分割結果を表す)0から始まるラベルのシーケンスへのダブルポインタ. :param is_equal: 相関関数.2つのシーケンス要素が同じクラスに属する場合,相関関数は 0 以外を返し,そうでなければ 0 を返します.この分割アルゴリズムは,分類の基準として相関関数の推移閉包を用います. :param userdata: 関数 ``is_equal`` に引数としてそのまま渡されるパラメータ. .. code-block:: c typedef int (CV_CDECL* CvCmpFunc)(const void* a, const void* b, void* userdata); .. 関数 ``cvSeqPartition`` は,集合を1つ以上の同値クラスに分割する二次アルゴリズムの実装です.この関数は,同値クラスの個数を返します. .. code-block:: c #include "cxcore.h" #include "highgui.h" #include CvSeq* point_seq = 0; IplImage* canvas = 0; CvScalar* colors = 0; int pos = 10; int is_equal( const void* _a, const void* _b, void* userdata ) { CvPoint a = *(const CvPoint*)_a; CvPoint b = *(const CvPoint*)_b; double threshold = *(double*)userdata; return (double)((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)) <= threshold; } void on_track( int pos ) { CvSeq* labels = 0; double threshold = pos*pos; int i, class_count = cvSeqPartition( point_seq, 0, &labels, is_equal, &threshold ); printf(" cvZero( canvas ); for( i = 0; i < labels->total; i++ ) { CvPoint pt = *(CvPoint*)cvGetSeqElem( point_seq, i ); CvScalar color = colors[*(int*)cvGetSeqElem( labels, i )]; cvCircle( canvas, pt, 1, color, -1 ); } cvShowImage( "points", canvas ); } int main( int argc, char** argv ) { CvMemStorage* storage = cvCreateMemStorage(0); point_seq = cvCreateSeq( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage ); CvRNG rng = cvRNG(0xffffffff); int width = 500, height = 500; int i, count = 1000; canvas = cvCreateImage( cvSize(width,height), 8, 3 ); colors = (CvScalar*)cvAlloc( count*sizeof(colors[0]) ); for( i = 0; i < count; i++ ) { CvPoint pt; int icolor; pt.x = cvRandInt( &rng ) pt.y = cvRandInt( &rng ) cvSeqPush( point_seq, &pt ); icolor = cvRandInt( &rng ) | 0x00404040; colors[i] = CV_RGB(icolor & 255, (icolor >> 8)&255, (icolor >> 16)&255); } cvNamedWindow( "points", 1 ); cvCreateTrackbar( "threshold", "points", &pos, 50, on_track ); on_track(pos); cvWaitKey(0); return 0; } ..