2015年8月26日

node.jsによる細線化処理の比較

 

細線化は、画像処理で、二値化やフィルター処理に続いて一般的な処理で、線情報の特徴抽出するための前処理である。ここでは、３つのアルゴリズム（Zhang-Suen、NWG：Nagendraprasad-Wang-Gupta、田村）で細線化にどのような特徴（癖）を持っているか確認を行うこと、node.jsでそれぞれのパフォーマンスを確認することを目的とする。

 

　検討のための元ネタは、次のサイトを利用した（アルゴリズムの解説はこちらのサイトへ）。(1)は、javaからnode.jsへの変換、(2)は、ほんの少々手を入れ、それそれnode.jsの関数とした。これらの関数にBMP画像の読み書き処理を加え、評価するプログラムとした。

(1)  Zhang-Suen thinning algorithm

                            http://rosettacode.org/wiki/Zhang-Suen_thinning_algorithm

(2)  Javascriptで細線化

                            http://www.hundredsoft.jp/win7blog/log/eid119.html

 

細線化結果

　プログラムで細線化を行い、次のような画像を得た。

　

元画像（1bit）　　　　　　　　　　　　　Zhang-Suen法

　

NWG法　　　　　　　　　　　　　　　　　田村法

 

　各アルゴリズムを比較すると、NWG法が一番きれいな細線化であった。Zhang-Suen法は一部に細線化できるところ（図中の赤丸）が見られた。田村法は細線化度が高いが、ヒゲが多く見られた（細線化として正しいように思う）。

　また、Zhang-Suen法で、上記(1)のロジック、上記(2)のロジックで、全く同じ画像が得られた（念のために画像ファイルのMD5値も一致した）。

 

処理スピード

　元画像（640×480）に対して、i5-3337U CPU, 1.8GHzのPC環境で、Zhang-Suen法ロジック(1)は116.7msec、Zhang-Suen法ロジック(2)は51.9msec、NWG法は51..2msec、田村法は41.6msecであった。

 

結果

　細線化はアルゴリズムにより、処理に結果が異なることが分かった。対象画像からどのようなものを抽出するかによって、アルゴリズムを選択する必要がある。

node.jsで画像処理なんかできるの？、遅いのでは？、このように思われる人が多いと思う。実際動かしてみてnode.jsでも十分な処理スピードであった。

 

ソースコード、画像はこちらから。

 

細線化関数

/*
	Zhang-Suen thinning algorithm
		http://rosettacode.org/wiki/Zhang-Suen_thinning_algorithm
	Javascriptで細線化
		http://www.hundredsoft.jp/win7blog/log/eid119.html
	Arranged by T. Osaka(2015/8/26)
*/

var thin=function() {

var grid;
var width;
var height;

/*
	Zhang-Suen thinning algorithm
		http://rosettacode.org/wiki/Zhang-Suen_thinning_algorithm
*/
this.ZhangSuen = function(g, w, h, x1, y1, x2, y2) {

var nbrs = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1]];
var nbrGroups = [[[0, 2, 4], [2, 4, 6]], [[0, 2, 6], [0, 4, 6]]];

	width = w;
	height = h;

	grid = new Buffer(width * height);
	for (var i = 0; i < width * height; i++) grid[i] = g[i];

	var firstStep = false;
	var hasChanged;

	do {
		hasChanged = false;
		firstStep = !firstStep;

		var toWhite = [];

		for (var r = y1; r < y2; r++) {
			for (var c = x1; c < x2; c++) {

				if (grid[r * width + c] != 0x00) continue;

				var nn = numNeighbors(r, c);
				if (nn < 2 || nn > 6) continue;

				if (numTransitions(r, c) != 1) continue;

				if (!atLeastOneIsWhite(r, c, firstStep ? 0 : 1)) continue;

				toWhite.push({x:c, y:r});

				hasChanged = true;
			}
		}

		for (var p in toWhite) grid[toWhite[p].y * width + toWhite[p].x] = 0xff;

	} while (hasChanged || firstStep);


	function numNeighbors(r, c) {
		var count = 0;
		for (var i = 0; i < nbrs.length - 1; i++) {
			if (grid[(r + nbrs[i][1]) * width + c + nbrs[i][0]] == 0x00) count++;
		}
		return count;
	}

	function numTransitions(r, c) {
		var count = 0;
		for (var i = 0; i < nbrs.length - 1; i++) {
			if (grid[(r + nbrs[i][1]) * width + c + nbrs[i][0]] == 0xff) {
				if (grid[(r + nbrs[i + 1][1]) * width + c + nbrs[i + 1][0]] == 0x00) count++;
			}
		}
		return count;
	}

	function atLeastOneIsWhite(r, c, step) {
		var count = 0;
		var group = nbrGroups[step];
		for (var i = 0; i < 2; i++) {
			for (var j = 0; j < group[i].length; j++) {
				var nbr = nbrs[group[i][j]];
				if (grid[(r + nbr[1]) * width + c + nbr[0]] == 0xff) {
					count++;
					break;
				}
			}
		}
		return (count > 1);
	}
};

//
// Javascriptで細線化 Zhang-Suen Algorithm
//		http://www.hundredsoft.jp/win7blog/log/eid119.html
//
this.zhang_suen = function(g, w, h, x1,y1, x2, y2) {
	width = w;
	height = h;

	grid = new Buffer(width * height);
	for (var i = 0; i < g.length; i++) {
		grid[i] = ~g[i];
		g[i] = ~g[i];
	}

	var bFlag = true;

	for (var k = 0; k < 100 && bFlag; k++) {
		if (!(k & 1)) {
			bFlag = false;
		}
		for (var i = 0; i < g.length; i++) {
			g[i] = grid[i];
		}
		for (var y = y1; y < y2; y++) {
			for (var x = x1; x < x2; x++) {
				var i = y * width + x;
				if (g[i]) {
					// [p9 p2 p3]
					// [p8 p1 p4]
					// [p7 p6 p5]
					var p1 = 1;
					var p2 = g[i - width    ] ? 1 : 0;
					var p3 = g[i - width + 1] ? 1 : 0;
					var p4 = g[i		 + 1] ? 1 : 0;
					var p5 = g[i + width + 1] ? 1 : 0;
					var p6 = g[i + width    ] ? 1 : 0;
					var p7 = g[i + width - 1] ? 1 : 0;
					var p8 = g[i		 - 1] ? 1 : 0;
					var p9 = g[i - width - 1] ? 1 : 0;

					var a = 0;
					if (!p2 && p3) {a++;}
					if (!p3 && p4) {a++;}
					if (!p4 && p5) {a++;}
					if (!p5 && p6) {a++;}
					if (!p6 && p7) {a++;}
					if (!p7 && p8) {a++;}
					if (!p8 && p9) {a++;}
					if (!p9 && p2) {a++;}
					var b = p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9;

					if (a == 1 && 2 <= b && b <= 6) {
						if ((!(k & 1) && p2*p4*p6 == 0 && p4*p6*p8 == 0) || ( (k & 1) && p2*p4*p8 == 0 && p2*p6*p8 == 0)) {
							grid[i] = 0;
							bFlag = true;
						}
					}
				}
			}
		}
	}
	for (var i = 0; i < grid.length; i++) {
		g[i] = ~g[i];
		grid[i] = ~grid[i];
	}
};

//
// Javascriptで細線化 NWG Algorithm
//		http://www.hundredsoft.jp/win7blog/log/eid119.html
//
this.nwg_method = function(g, w, h, x1,y1, x2, y2) {
	width = w;
	height = h;

	grid = new Buffer(width * height);
	for (var i = 0; i < g.length; i++) {
		grid[i] = ~g[i];
		g[i] = ~g[i];
	}

	var bFlag = true;

	for (var k = 0; k < 100 && bFlag; k++) {
		bFlag = false;
		for (var i = 0; i < g.length; i++) {
			g[i] = grid[i];
		}
		for (var y = y1; y < y2; y++) {
			for (var x = x1; x < x2; x++) {
				var i = y * w + x;
				if (g[i]) {
					// [p7 p0 p1]
					// [p6	  p2]
					// [p5 p4 p3]
					var p0 = (g[i - w    ]) ? 1 : 0;
					var p1 = (g[i - w + 1]) ? 1 : 0;
					var p2 = (g[i      +1]) ? 1 : 0;
					var p3 = (g[i + w + 1]) ? 1 : 0;
					var p4 = (g[i + w    ]) ? 1 : 0;
					var p5 = (g[i + w - 1]) ? 1 : 0;
					var p6 = (g[i      -1]) ? 1 : 0;
					var p7 = (g[i - w - 1]) ? 1 : 0;
					var a = 0;
					if (!p0 && p1) {a++;}
					if (!p1 && p2) {a++;}
					if (!p2 && p3) {a++;}
					if (!p3 && p4) {a++;}
					if (!p4 && p5) {a++;}
					if (!p5 && p6) {a++;}
					if (!p6 && p7) {a++;}
					if (!p7 && p0) {a++;}
					var b = p0 + p1 + p2 + p3 + p4 + p5 + p6 + p7;

					if (2 <= b && b <= 6) {
						var c = 0;
						if ((p0 + p1 + p2 + p5 == 0 && p4 + p6 == 2)
						 || (p2 + p3 + p4 + p7 == 0 && p0 + p6 == 2)) {
							c = 1;
						}
						if (a == 1 || c == 1) {
							var e = (p2+p4) * p0 * p6;
							var f = (p0+p6) * p2 * p4;
							if ((!(k & 1) && e == 0) || ( (k & 1) && f == 0)) {
								grid[i] = 0;
								bFlag = true;
							}
						}
					}
				}
			}
		}
	}
	for (var i = 0; i < grid.length; i++) {
		g[i] = ~g[i];
		grid[i] = ~grid[i];
	}
};

// 
// Javascriptで細線化 田村 Algorithm
//		http://www.hundredsoft.jp/win7blog/log/eid119.html
//
this.tamura = function(g, w, h, x1,y1, x2, y2) {
	width = w;
	height = h;

	grid = new Buffer(width * height);
	for (var i = 0; i < g.length; i++) {
		grid[i] = ~g[i];
		g[i] = ~g[i];
	}

	// [p0 p1 p2]
	// [p3 p4 p5]
	// [p6 p7 p8]
	//
	// P[0-8]を2bitで表す。白bit:10, 黒bit:01, その他bit:00
	// 先頭にbit00を付加し、１バイト/列で１つのパターンを３バイトで表現。
	// Bit並びは、00[p0][p1][p2]00[p3][p4][p5]00[p6][p7][p8]とする。

	// 除去するパターン(1)
	var pat1  = new Array(0x040800, 0x000900);
	// 除去しないパターン(1)
	var pat1n = new Array(0x040a09, 0x182900,
				0x001908, 0x042804, 0x081900, 0x040a04, 0x001824, 0x241800,
				0x060900, 0x000906, 0x192a11, 0x190a19, 0x112a19, 0x192819);

	// 除去するパターン(2)
	var pat2  = new Array(0x000804, 0x001800);
	// 除去しないパターン(2)
	var pat2n = new Array(0x182804, 0x001a09,
				0x001908, 0x042804, 0x081900, 0x040a04, 0x001824, 0x241800,
				0x060900, 0x000906, 0x192a11, 0x190a19, 0x112a19, 0x192819);

	var bFlag = true;
	for (var k = 0; k < 100 && bFlag; k++) {
		bFlag = false;
		for (var i = 0; i < g.length; i++) {
			g[i] = grid[i];
		}
		var pat, patn;
		if (k & 1) {
			pat = pat2;
			patn = pat2n;
		} else {
			pat = pat1;
			patn = pat1n;
		}

		for (var y = y1; y < y2; y++) {
			for (var x = x1; x < x2; x++) {
				var i = y * w + x;
				if (g[i]) {
					var f = 0x000800;

					if (g[i - w - 1])	{f |= 0x200000;}
					else				{f |= 0x100000;}
					if (g[i - w    ])	{f |= 0x080000;}
					else				{f |= 0x040000;}
					if (g[i - w + 1])	{f |= 0x020000;}
					else				{f |= 0x010000;}
					if (g[i      -1])	{f |= 0x002000;}
					else				{f |= 0x001000;}
//					if (g[i        ])	{f |= 0x000800;}
//					else				{f |= 0x000400;}
					if (g[i      +1])	{f |= 0x000200;}
					else				{f |= 0x000100;}
					if (g[i + w - 1])	{f |= 0x000020;}
					else				{f |= 0x000010;}
					if (g[i + w    ])	{f |= 0x000008;}
					else				{f |= 0x000004;}
					if (g[i + w + 1])	{f |= 0x000002;}
					else				{f |= 0x000001;}

					// 除去するパターンに一致
					if ((f & pat[0]) == pat[0] || (f & pat[1]) == pat[1]) {
						// 除去しないパターンに一致
						if ((f & patn[ 0]) == patn[ 0] || (f & patn[ 1]) == patn[ 1]
						 || (f & patn[ 2]) == patn[ 2] || (f & patn[ 3]) == patn[ 3]
						 || (f & patn[ 4]) == patn[ 4] || (f & patn[ 5]) == patn[ 5]
						 || (f & patn[ 6]) == patn[ 6] || (f & patn[ 7]) == patn[ 7]
						 || (f & patn[ 8]) == patn[ 8] || (f & patn[ 9]) == patn[ 9]
						 || (f & patn[10]) == patn[10] || (f & patn[11]) == patn[11]
						 || (f & patn[12]) == patn[12] || (f & patn[13]) == patn[13]) {
							;
						} else {
							grid[i] = 0;
							bFlag = true;
						}
					}
				}
			}
		}
	}
	for (var i = 0; i < grid.length; i++) {
		g[i] = ~g[i];
		grid[i] = ~grid[i];
	}
};

this.getData = function() {
	return grid;
}

}

module.exports = thin;

（記　大坂　哲司）