K-means法と画像の階調分類

K-means法とは、クラスタリングと呼ばれる、類似したデータをいくつかのグループに分類するアルゴリズムの一つです。このアルゴリズムを利用して、画像の減色処理を行うことができます。
この画像処理のコードについて、昔作ったjavaのコードですが引っ張り出してきました。
メソッドだけのっけます

public static BufferedImage ClasterUse(BufferedImage read,int CLASTNUM,boolean t)
{
	long start = System.currentTimeMillis();

	BufferedImage out = new BufferedImage(read.getWidth(),read.getHeight(),BufferedImage.TYPE_INT_RGB);
	int width=read.getWidth(),height=read.getHeight(),obj[]=new int[3],i,x,y,j,k,index=0,avg[][]=new int[CLASTNUM][3],temp=0,c=0;
	int[][] claster = new int[width][height];
	boolean flag=true;
	double min,tmp=0;
	int num[] = new int[CLASTNUM];
	short clascolor[][] = new short[CLASTNUM][3];
	short[][][] image= CreateImagearray(read);
	for(i= 0;i<CLASTNUM;i++)
	for(j=0;j<3;j++)
		clascolor[i][j] = (short) (255*Math.random());
	do{
		Arrays.fill(num,0);
		flag = true;
		for(i=0;i<CLASTNUM;i++)
			for(j=0;j<3;j++)
				avg[i][j] = 0;
		for(x=0;x<width;x++){
			for(y=0;y<height;y++){
			min=-1;
			for(i=0;i<CLASTNUM;i++)
				if(min  > (tmp = Math.pow((double)(clascolor[i][0]-image[x][y][0]),2)+Math.pow((double)(clascolor[i][1]-image[x][y][1]),2)+Math.pow((double)(clascolor[i][2]-image[x][y][2]),2)) || min==-1 ){
					min = tmp;
					index = i;
				}
				claster[x][y] = index;
			}
		}
		for(x=0;x<width;x++)
			for(y=0;y<height;y++){
				for(k=0;k<3;k++)
					avg[claster[x][y]][k] += image[x][y][k];
				num[claster[x][y]]++;
			}
		for(i=0;i<CLASTNUM;i++)
			for(k=0;k<3;k++){
				if(num[i] == 0)
					continue;
				if(clascolor[i][k] != (temp = avg[i][k]/num[i]))
					flag = false;
				clascolor[i][k] = (short)temp;

			}

		}while(	!flag);
		for(x=0;x<width;x++){
			for(y=0;y<height;y++){
				for(j=0;j<3;j++)
						obj[j] = clascolor[claster[x][y]][j];
				out.setRGB(x,y,RGBtoint(obj));
					}
		}

		long end = System.currentTimeMillis();
		System.out.println((end - start)  + "ms");
		return out;
	}

実行結果
元画像
f:id:xxxasdfghjk999:20170723004718j:plain
8色
f:id:xxxasdfghjk999:20170723004535p:plain
4色
f:id:xxxasdfghjk999:20170723004550p:plain

アルゴリズムをざっくり説明すると、最初に適当に画素値のセットRGBを分けたいグループ数(コードではCLASTNUM)の数だけ設定します。プログラムの方では乱数を用いています。このクラスター集合の画素のRGBと画像の各ピクセルのRGBの色の距離(R-R')^2+(G-G')^2+(B-B')^2 (平方根が付きますが、比較するだけなら問題ありません) をクラスター集合すべてに対して計算し、各画素に対してこの値が最も小さいものに対して、そのクラスターの番号を振ります。すべての画素にクラスターの番号を振り終えたら、クラスターの画素値を更新します。クラスターに属する画素の平均値にすべてのクラスターが持つ画素値を変更します(画像の画素値はまだ変更しません)。そして最初に戻り、色の距離をすべてのピクセルに対して計算...ということをクラスターの画素値の変更がなくなるまで続けます。これが終わったとき、すべてのピクセルは適切なクラスターに割り振られていることが期待できます。ただし、画像処理のプログラムとしても、なかなか時間がかかるものとなっています。そのため、計算時間を印字する部分を作っています。はじめのクラス分けに乱数を用いているので、何度も実行すると、何度も違う結果が得られます。