HTML5 canvas 画像処理 輪郭追跡 Freeman chain code

gistfile1.js

// 輪郭追跡を行い，輪郭部のみに色を出力する
function contourDetection(contextIn, contextOut, width, height) {
	var imgData=contextIn.getImageData(0, 0, width, height);
	// 読み取り用ピクセルデータ（書き換えない）
	var pixelData = new Array(width);
	for(var i=0; i<width; ++i) {
		pixelData[i] = new Array(height);
		for(var j=0; j<height; ++j) {
			pixelData[i][j] = imgData.data[4*(width*j+i)];
		}
	}
	// 更新用ピクセルデータ
	var buf=new Array(width);
	for(var i=0; i<width; ++i) {
		buf[i] = new Array(height);
		for(var j=0; j<height; ++j) {
			buf[i][j] = 255;
		}
	}

	// あるピクセルを * で表し、
	// 周囲のピクセルを下のように番号を付けて表す
	// 3 2 1
	// 4 * 0
	// 5 6 7 
	var nextCode=[7, 7, 1, 1, 3, 3, 5, 5];
	// Freeman's chain code
	var chainCode=[
		[1, 0], [1, -1], [0, -1], [-1, -1],
		[-1, 0], [-1, 1], [0, 1], [1, 1]
	];

	var rel;	// relativee pisition
	var relBuf;	// previous rel
	var dPx = [];	// detected pixel 輪郭として検出されたピクセルのテンポラリー変数
	var startPx = [];	// 輪郭追跡の開始ピクセル
	var sPx = [];	// searching pixel
	var isClosed = false;	// 輪郭が閉じていれば true
	var isStandAlone;	// 孤立点ならば true
	var pxs=[];	// 輪郭のピクセル座標の配列を格納するテンポラリー配列
	var boundaryPxs=[];	// 複数の輪郭を格納する配列
	var pxVal;	// 着目するピクセルの色
	var duplicatedPx = [];	// 複数回、輪郭として検出されたピクセル座標を格納（将来的にこのような重複を許さないアルゴリズムにしたい）
	while(1) {
		// 輪郭追跡開始ピクセルを探す
		dPx = searchStartPixel();
		// 画像全体が検索された場合はループを終了
		if(dPx[0]==width && dPx[1]==height) {
			break;
		}
		pxs=[];
		pxs.push([dPx[0], dPx[1]]);
		startPx=[dPx[0], dPx[1]];
		isStandAlone=false;
		isClosed=false;
		relBuf=5;	// 最初に調べるのは5番
		// 輪郭が閉じるまで次々に周囲のピクセルを調べる
		while(!isClosed){
			for(var i=0; i<8; ++i) {
				rel = (relBuf+i)%8;	// relBufから順に調べる
				sPx[0] = dPx[0]+chainCode[rel][0];
				sPx[1] = dPx[1]+chainCode[rel][1];
				// sPx が画像上の座標外ならば白として評価する
				if(sPx[0]<0 || sPx[0]>=width || sPx[1]<0 || sPx[1]>=height){
					pxVal = 255;
				} else {
					pxVal = pixelData[sPx[0]][sPx[1]]
				}
				// もし調べるピクセルの色が黒ならば新しい輪郭とみなす
				// 最初のピクセルに戻れば次の輪郭を探す
				// 周囲の8ピクセルがすべて白ならば孤立点なので次の輪郭を探す
				if(pxVal==0) {
					if(buf[sPx[0]][sPx[1]]==0) {
						duplicatedPx.push([sPx[0],sPx[1]]);
					}
					// 検出されたピクセルが輪郭追跡開始ピクセルならば
					// 追跡を終了して次の輪郭に移る
					if(sPx[0]==startPx[0] && sPx[1]==startPx[1]) {
						isClosed=true;
						break;
					}
					buf[sPx[0]][sPx[1]]=0;	// 検出された点を黒にする
					dPx[0]=sPx[0];
					dPx[1]=sPx[1];
					pxs.push([dPx[0], dPx[1]]);
					relBuf=nextCode[rel];
					break;
				}
				if(i==7) {
					isStandAlone = true;
				}
			}
			if(isStandAlone) {
				break;
			}
		}
		boundaryPxs.push(pxs);
	}

	// 左上から操作し開始点（白から黒に代わるピクセル）を見つける
	function searchStartPixel() {
		var idx;
		var x, y;
		var leftPx;
		for(y=0; y<height; ++y) {
			for(x=0; x<width; ++x) {
				if(x==0) {
					leftPx = 255;
				} else {
					leftPx=pixelData[x-1][y];
				}
				if(leftPx == 255 && pixelData[x][y] == 0 && buf[x][y]==255) {
					buf[x][y]=0;
					return [x, y];
				}
			}
		}
		return [width, height];
	}

	// 輪郭ごとに色を変えて描画する
	contextOut.clearRect(0,0,width,height);
	colors = ['red', 'green', 'blue', 'orange', 'purple', 'cyan'];
	for(var i=0; i<boundaryPxs.length; ++i) {
		contextOut.strokeStyle=colors[i%colors.length];
		contextOut.beginPath();
		contextOut.moveTo(boundaryPxs[i][0][0], boundaryPxs[i][0][1]);
		for(var j=1; j<boundaryPxs[i].length; ++j) {
			contextOut.lineTo(boundaryPxs[i][j][0], boundaryPxs[i][j][1]);
		}
		contextOut.lineTo(boundaryPxs[i][0][0], boundaryPxs[i][0][1]);
		contextOut.stroke();
	}
	contextOut.strokeStyle='black';
}