クラスタリングと多次元空間探索

KMeans2

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)

ベクトルの集合を指定された数のクラスタに分割します．

パラメタ:

• samples – 入力サンプルの浮動小数点型行列，1つの行が1つのサンプルを表します
• nclusters – 分割クラスタ数
• labels – 各サンプルが属するクラスタのインデックスが保存される，整数型の出力ベクトル
• termcrit – 反復数の最大値と（または），精度（連続する反復処理間においてクラスタ中心が移動する距離）の指定
• attempts – このアルゴリズムが，異なる初期ラベルを与えられて実行される回数．これは，最もコンパクトな分割を行うラベル（最後のパラメータを参照）を返します
• rng – オプションである外部乱数発生器．この関数の挙動を完全に制御したい場合に用いられます
• flags – 0 あるいは CV_KMEANS_USE_INITIAL_LABELS ．後者の場合，最初の試行で（だけ）は，ランダムに生成されるラベルの代わりに，ユーザが与えたラベルを初期推定値として用います．2回目以降の試行では，ランダムに生成されたラベルを利用します
• centers – オプション．クラスタ中心が出力される配列
• compactness – オプション出力．各試行後に として求められます．最も良い値（最小値）が選択され，この関数はそれに対応するラベルを返します．基本的に次のようにすれば，ユーザはこの関数の基本部分だけを利用することができる．まず，試行回数を1にセットし，独自アルゴリズムを利用してラベルを毎回初期化します（ flags = CV_KMEANS_USE_INITIAL_LABELS ）．そして，出力されるコンパクトネスやその他の基準に基づいて，最良のクラスタリグを選択します

関数 cvKMeans2 は， nclusters 個のクラスタの中心を求め，入力サンプルを各クラスタに分類する k-means アルゴリズムの実装です．また出力として，行列 samples の 行 で与えられたサンプルが属するクラスタのインデックスが， に格納されます．

#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;
    }
}

SeqPartition

int cvSeqPartition(const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, CvCmpFunc is_equal, void* userdata)

シーケンスを同値類（同値クラス）に分割します．

パラメタ:

• seq – 分割されるシーケンス
• storage – 同値クラスラベルのシーケンスが保存されるストレージブロック．NULLの場合は，ラベルの出力場所として seq->storage が利用されます
• labels – 出力パラメータ．入力シーケンスの各要素に割り振られた（分割結果を表す）0から始まるラベルのシーケンスへのダブルポインタ
• is_equal – 相関関数．2つのシーケンス要素が同じクラスに属する場合，相関関数は 0 以外を返し，そうでなければ 0 を返す．この分割アルゴリズムは，分類の基準として相関関数の推移閉包を用います
• userdata – 関数 is_equal に引数としてそのまま渡されるパラメータ

typedef int (CV_CDECL* CvCmpFunc)(const void* a, const void* b, void* userdata);

関数 cvSeqPartition は，集合を1つ以上の同値クラスに分割する2次アルゴリズムの実装です．この関数は，同値クラスの個数を返します．

#include "cxcore.h"
#include "highgui.h"
#include <stdio.h>

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;
}