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

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 – オプション出力.各試行後に \sum_i ||\texttt{samples}_i - \texttt{centers}_{\texttt{labels}_i}||^2 として求められます.最も良い値(最小値)が選択され,この関数はそれに対応するラベルを返します.基本的に次のようにすれば,ユーザはこの関数の基本部分だけを利用することができる.まず,試行回数を1にセットし,独自アルゴリズムを利用してラベルを毎回初期化します( flags = CV_KMEANS_USE_INITIAL_LABELS ).そして,出力されるコンパクトネスやその他の基準に基づいて,最良のクラスタリグを選択します

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

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

目次

このページ