インクリメンタルクラスタリング(IncrementalClustering)の実装

前回、javascriptのthreadをやって、並列実行してから実行するという話だったのですが、

当てにしていたConcurent.Threadがクラスのフィールドを取得出来ないという問題が発生したので、

今回は自分のフォルダに格納していたインクリメンタルクラスタリングという手法を実装したファイルを掲載する。

（おっと、それって逃げじゃね？ってツッコミは今回は無しだ）

このソースだとOpenCVのcvImageを二値化して出た白い点をノードとして扱うようにする処理している。

IncrementalClustering.h

class Random{
public:
	Random();
	unsigned int operator()(unsigned int max);
};

class Node{
public:
	double x, y;
	Node(double tx, double ty):x(tx), y(ty){}
};

class Cluster{
public:
	std::vector<Node> nodes;
	double x, y;
	Cluster():x(0), y(0){}
	void incrementNode(Node n);
};

class IncrementalClustering{
private:
	int max_cluster, m;
	double thr_d;
	std::vector<Node> nodes;
	//Cluster* clusters;
	std::vector<Cluster> clusters;
public:
	IncrementalClustering(){}
	void initialize(int q, double thr_d);
	void makeNodes(IplImage* img);
	void process();
	double computeDisntace(double x, double y, Node n);
};

IncrementalClustering.cpp

#include<iostream>
#include<cmath>
#include<cfloat>
#include<cstdlib>
#include<sstream>
#include<fstream>
#include<ctime>
#include<cv.h>
#include<highgui.h>
#include<windows.h>
#include "IncrementalClustering.h"

#define PIXVAL(iplimagep, x, y) (*(uchar *)((iplimagep)->imageData + (y) * (iplimagep)->widthStep + (x)))
#define PIXVALB(iplimagep, x, y) (*(uchar *)((iplimagep)->imageData + (y) * (iplimagep)->widthStep + (x)*3))
#define PIXVALG(iplimagep, x, y) (*(uchar *)((iplimagep)->imageData + (y) * (iplimagep)->widthStep + (x)*3+1))
#define PIXVALR(iplimagep, x, y) (*(uchar *)((iplimagep)->imageData + (y) * (iplimagep)->widthStep + (x)*3+2))

using namespace std;
using namespace cv;

// -- Random
// コンストラクタで乱数の種の生成を行う
Random::Random()
{
	srand(static_cast<unsigned int>(time(NULL)));
}

// 関数オブジェクト
unsigned int
Random::operator()(unsigned int max)
{
	double tmp = static_cast<double>( rand() ) / static_cast<double>( RAND_MAX );
	return static_cast<unsigned int>( tmp * max );
}


// -- Cluster
// クラスタ内のノードの数を増やし、クラスタの中心位置を更新する
void
Cluster::incrementNode(Node n)
{
	nodes.push_back(n);
	double num = nodes.size();
	x = ((num - 1) * x + n.x) / num;
	y = ((num - 1) * y + n.y) / num;
}

// -- IncrementalClustering
// 初期化
void
IncrementalClustering::initialize(int q, double thr_d)
{
	m = 0;
	max_cluster = q;
	this->thr_d = thr_d;
	//clusters = (Cluster*)malloc(sizeof(Cluster) * max_cluster);
}

// 二値化した画像の白い点をノードとして配列に格納する
void
IncrementalClustering::makeNodes(IplImage* img)
{
	bool first = true;
	for(int y = 0; y < img->height; y++){
		for(int x = 0; x < img->width; x++){
			int pixel = PIXVAL(img, x, y);
			if(pixel){
				nodes.push_back(Node(x, y));
				if(first){
					clusters.push_back(Cluster());
					clusters[m].incrementNode(Node(x, y));
					first = false;
				}
			}
		}
	}
	// ノードの順列をランダムに入れ替える
	Random r;
	random_shuffle(nodes.begin(), nodes.end(), r);
}

// インクリメンタルクラスタリングを実行する
void
IncrementalClustering::process()
{
	for(int i = 1; i < nodes.size(); i++){
		double min_d = DBL_MAX;
		int k;
		// ひとつのノードと全てのクラスタを探索
		for(int j = 0; j <= m; j++){
			double d = computeDisntace(clusters[j].x, clusters[j].y, nodes[i]);
			// 距離が最短だった場合は更新し、クラスタの番号を記憶する
			if(min_d > d){
				min_d = d;
				k = j;
			}
		}
		// 全てのクラスタのノードに、閾値として設定した
		if(min_d > thr_d && m < (max_cluster - 1)){
			clusters.push_back(Cluster());
			m++;
			clusters[m].incrementNode(nodes[i]);
		}
		// 新しいクラスタを生成し、mを増加させる
		else{
			clusters[k].incrementNode(nodes[i]);
		}
	}
}

// クラスタの中心位置とノードの距離を取得する
double
IncrementalClustering::computeDisntace(double x, double y, Node n)
{
	double dx = x - n.x, dy = y - n.y;
	return sqrt(dx * dx + dy * dy);
}