作成　2015年8月7日

３×３メディアンフィルター高速版の実装

撮影した画像にはカメラ素子に起因したランダムなノイズが含まれている。このノイズは画像処理に悪影響を与えるため、何らかの方法でノイズを除去してから画像処理を行うことが一般的である。

　ここでは、浜村、入江の“３×３メディアンフィルターの高速アルゴリズム”の実装を行い、バブルソート版との比較を行う。

ロジック説明（詳細は浜村らの論文参照）

３×３のデータから中央値を求めるため、それぞれ３群のデータをソートし、それぞれの中央値で３群をソートする（上図、浜村らの論文を引用）。ここで大きい群の最小値をｙ、中央の中央値をｘ、小さい群の最大値をｚとし、ｘ、ｙ、ｚの関係から中央値を求める。

　　　

　　　

中央値判定は、次の４パターンで行った。

case１は、ｙ<=ｘ<=ｚの関係で、ｘが中央値となる。

case１’は、ｚ<=ｘ<=ｙの関係で、ｘが中央値となる。

case２は、ｘ<ｙかつｘ<ｚの関係で、ｘは大きい方から６番目となる。５番目の値は、ｙ、ｚとｘのより大きい値の３つの最小値で、求める中央値となる。

case３は、ｘ>ｙかつｘ>ｚの関係で、ｘが大きい方から４番目となる。５番目の値は、ｙ、ｚとｘのより小さい値の３つの最大値で、求める中央値となる。

結果

640×480のモノクロ画像について、i5-3337U CPU, 1.8GHzのPC環境で、高速版のメディアンフィルターが133.2msec、バブルソート版が163.2msec（5回平均）で、高速版はバブルソート版に比べ約18%高速であることを確認した。尚、標準のソートの処理時間は460.0msecであった。

　この実装ではnode.jsを用い、画像処理を行った。画像のサイズは640×480で307.2KBの容量となるが、Javascriptでも十分画像処理ができることが分かった。

サンプルコード

サンプルコードは、24bitBMP若しくは8bitBMPファイルを読み込み、メディアンフィルターを掛け、8bitBMPファイルに書き出す。ソースコードはこちら。

node.jsで書いたメディアンフィルターのコード

//8近傍の中央値を求める
function v33(x) {
	var _y = new Array(4);
	for (var i = 0; i < 3; i++) {
		_y[i] = v3(x[i][0], x[i][1], x[i][2]);
	}

	_y[3] = v3(_y[0][1].v, _y[1][1].v, _y[2][1].v);//3群の3値データの中央値をソートする
	for (var i = 0; i < 3; i++) {
if(i!=2)
console.log(x[i][0] + "," + x[i][1] + "," + x[i][2] + "," + _y[i][0].v + "," + _y[i][1].v + "," + _y[i][2].v);
else
console.log(x[i][0] + "," + x[i][1] + "," + x[i][2] + "," + _y[i][0].v + "," + _y[i][1].v + "," + _y[i][2].v + "," + _y[3][0].v + "," + _y[3][1].v + "," + _y[3][2].v);
	}

	var _Y = new Array(3);
	for (var i = 0; i < 3; i++) {//中央値に従い、3群のデータを小大順に並び替える
		_Y[i] = _y[_y[3][i].p];
	}

console.log(" ");

	for (var i = 0; i < 3; i++) {
console.log(_Y[i][0].v + "," + _Y[i][1].v + "," + _Y[i][2].v);
	}

	if (_Y[1][1].v >= _Y[2][0].v && _Y[1][1].v <= _Y[0][2].v) {
console.log("case1="+ _Y[1][1].v);//中央値が5番目
	}
	else if (_Y[1][1].v <= _Y[2][0].v && _Y[1][1].v >= _Y[0][2].v) {
console.log("case1'="+ _Y[1][1].v);//中央値が5番目
	}
	else if ( _Y[1][1].v < _Y[2][0].v && _Y[1][1].v < _Y[0][2].v) {
//_Y[1][1]は大きい方から6番目で、_Y[1][1]より大きい_Y[1][2]、_Y[2]の最小値と_Y[0]の最大値をソートして、その最小値が5番目となる
		var X = v3(_Y[2][0].v, _Y[0][2].v, _Y[1][2].v);
console.log("case2=" + X[0].v);
	}
	else if ( _Y[1][1].v > _Y[2][0].v && _Y[1][1].v > _Y[0][2].v) {
//_Y[1][1]は大きい方から4番目で、_Y[1][1]より小さい_Y[1][0]、_Y[2]の最小値と_Y[0]の最大値をソートして、その最大値が5番目となる
		var X = v3(_Y[2][0].v, _Y[0][2].v, _Y[1][0].v);
console.log("case3=" + X[2].v);
	}
}

//3値データをソートする
function v3(a, b, c) {
	var x = new Array(3);
	if (a > b) {
		if (a > c) {
			if (b > c) {//a>b>c
				x[2] = {v:a, p:0};
				x[1] = {v:b, p:1};
				x[0] = {v:c, p:2};
			}
			else {//a>c>b
				x[2] = {v:a, p:0};
				x[1] = {v:c, p:2};
				x[0] = {v:b, p:1};
			}
		}
		else {//c>a>b
				x[2] = {v:c, p:2};
				x[1] = {v:a, p:0};
				x[0] = {v:b, p:1};
		}
	}
	else {
		if (a > c) {
			if (b > c) {//b>a>c
				x[2] = {v:b, p:1};
				x[1] = {v:a, p:0};
				x[0] = {v:c, p:2};
			}
		}
		else {
			if (b > c) {//b>c>a
				x[2] = {v:b, p:1};
				x[1] = {v:c, p:2};
				x[0] = {v:a, p:0};
			}
			else {//c>b>a
				x[2] = {v:c, p:2};
				x[1] = {v:b, p:1};
				x[0] = {v:a, p:0};
			}
		}
	}
	return x;
}

（記　大坂　哲司）