午後わてんのブログ

ベランダ菜園とWindows用アプリ作成(WPFとC#)

3x3のメディアンフィルタの高速化をC#で書いてみた

 
イメージ 1
前回4.39秒だったのが0.20秒になった
439/20≒22で、約22倍も速くなったことになる、すごい

使った画像は

f:id:gogowaten:20191214131827j:plain

2048x1536ピクセル、これをグレースケール画像(ピクセルフォーマットGray8)に変換したもの
パソコンのCPUはPhenomⅡX3 720@3.0GHz(2009年発売は10年前)
7/7発売予定のRyzen 9 3900Xだとどれくらい速いんだろうねえ
グレードを合わせるとPhenomⅡX3 720はRyzen 5 3400Gかもう少し下かな、ちょうど10年でどれだけ速くなったのかとか、わたし、気になります
 
2020年1月17日追記ここから
2400Gだけど気になりました!
2020年1月17日追記ここまで 
 
前回はLINQでソートしていた
メディアンフィルタの処理は自身の値を、自身と周囲8近傍の値でソートして、その中央値に置き換える
この処理の中で時間がかかるのが中央値を得るための「ソート」
前回はここをLINQのOrderByメソッドを使って
 
中央値 = 値の配列.OrderBy(z => z).ToList()[4];
 
こう書いていた
1行で済むからラクだけど、これが遅い
 
 
 
イメージ 5
7, 2, 6
6,10, 9
9, 3, 2
この中の中央値を求める
9つの数値を順番に並べ替えて中央(5番目)
 
 
3つのユニットに分ける
イメージ 4
3列に分ける、グループって書いてるけどunitで
 
 
step1、1回目のソート
イメージ 6
unitの中をソートする
 
 
step2、ユニットのソート
イメージ 7
ユニットの中央値を使ってユニットをソート
 
 
ここまでで確定したところを不等号で表す
イメージ 3
不等号がないところは不確定
 
さっきの数値を入れてみると
イメージ 8
ソートはこれで終了
次はここから中央値を見つけ出す
配列のインデックス
イメージ 9
配列のインデックスを左上から下に割り振ったところ
中央の[4]に注目して
[4]より大きな数値が入っていることが確定している場所は
左上の3つ[0][1][3]で
逆に小さいことが確定しているのは
右下の3つ[5][7][8]
不確定なのは[2][6]
case 1
もし[4]が[2][6]との中間なら
[4]の値が中央値として確定
イメージ 10
[2] >= [4] >= [6]
または[6] >= [4] >= [2]
なら
[4]が中央値

[4]からみて上位3つと下位3つは確定していて

上位 不明 下位
上位		不明		下位
[][][]	[][][]	[][][]

もし[2] >= [4] >= [6]なら
[2]は上位に入って、[6]は下位に入ることになる
もし[6] >= [4] >= [2]なら
[6]は上位に入って、[2]は下位に入ることになる
どちらにしても結果は
上位			下位
[][][][]	[4]	[][][][]
[2][6]の順位はわからないけど[4]が中央なのが確定する
 


case 2
[4]が小さい
イメージ 11
if (v[2] >= v[4] && v[6] >= v[4])
[4]が[2][6]以下だった場合は
[4]が大きい順だと6番目が確定
これは
 
イメージ 12
[4]より大きいのが確定していた[0][1][3]に[2][6]が加わったので
[4]は6番目
これで中央値は[0][1][3][2][6]の中の5番目(最小値)ってことになる
ここで[0][1]は[2]より大きいので対象から外れて
 
のこりの[3][2][6]の最小値が中央値になる
イメージ 13
あとはMathクラスのMinメソッドで求める
中央値 = Math.Min(v[2], Math.Min(v[3], v[6]));


case 3
case1, 2どちらにも当てはまらなかったときは
[4]が[2][6]以上なので
イメージ 14
case 2の逆になっただけ
 
[4]は小さい順の6番目が確定なので
イメージ 16
残りの5個の中の最大値が中央値(5番目)
[7][8]は[6]より小さいので最大値になりえないので
残りの[2][5][6]のどれかに絞られる
 
Maxメソッドで
イメージ 15
[2][5][6]の最大値を求めればいい
中央値 = Math.Max(v[2], Math.Max(v[5], v[6]));
これで全部
 
 
さっきの例だと
イメージ 17
step2のソートが終わった状態(右)
case 1の
[2] >= [4] >= [6]または[6] >= [4] >= [2]
に当てはまる
6>=6>=10
10>=6>=6←これ
なので中央値は6
ここまでの方法を使ったのがメディアンフィルタ高速化1ボタン
イメージ 18
これで4.39/0.25≒17.5倍速くなった
 
 
もっと速く
イメージ 19
(2, 2)を処理、次は右隣の
 
イメージ 20
(3,2)
 
前後の処理範囲で重なる部分
イメージ 21
赤の範囲を処理したときの右2列は次回の青の範囲にもなるので
赤のときのソート結果を記録しておけば
青のときにソートする手間が省ける
これを使ったのが
イメージ 22
これでLINQより22倍速くなって
高速化1より25/20=1.25倍速くなった
素晴らしい
 
イメージ 23
156~164、自身と8近傍の値はユニットごとに分けずに一つの配列に入れた
ユニットの中をソートする
 
イメージ 24
この部分の処理
168行目の,MedianSort3x3byteメソッドは
イメージ 25
地道な並べ替え
 
 
イメージ 26
step 2のソート
174行目のMedianSortUnitは
イメージ 27
地道すぎる
 
 
176行目、ソートが終わった配列から中央値を見つけ出す
MedianFind
イメージ 28
これでやっと中央値がわかる
LINQだと1行なのに100行くらいになったw
 
 
 
イメージ 29
高速化1の改変で、一時記録用の変数が増えただけなんだけど、長くなってしまった
違っていところはユニットの中をソートするところ、3ユニットから1ユニットに減っているので、9要素の配列のどこから3つをソートするかを指定できる
MedianSortUnitを365、370、395行目で使っている
 
イメージ 30
3ユニットまとめてソートするMedianSort3x3byteとほとんど同じ


最初はユニットごとに配列にして、さらにそれを配列にしたもの、つまり配列の配列byteを使おうとしたんだけど、うまく書けなかった
前後のピクセルで処理が重なる6ピクセル分のソート結果を一時記録しておく変数も6個の変数じゃなくて配列にまとめたかったけど、これもうまく書けなかった
まだ参照型の値渡し、参照型の参照渡し、そもそも参照型ってのが理解できていない
高速化1に比べてソートするユニットは3から1ユニットに減っているのに、速度は1.25倍に留まったのは、やっぱり書き方が良くないのかも
 
高速化1はあっさり書けて、それで10倍くらい速くなったから気を良くしてたんだけど、高速化2のほうは2日もかかった、それで1.25倍だったからねちょっとがっかりしたのがあったw
でももとに比べると22倍速くなったからね
 
 
ReleaseとDebugの速度差
イメージ 31
LINQはReleaseでもDebugでもほとんど変化なしだけど、手動でソートする高速化はReleaseだとかなり速くなる
 
 
参照したところ
さらに速くする方法も書いてあるみたいだけど理解できなかった…
でも、こういうの思いつくのすごい!
20倍以上も速くなるなんて思ってなかったから驚いた
 
 
ギットハブ
アプリダウンロード先
イメージ 32
画像表示は画像ファイルドロップorクリップボードからの貼り付け
フィルタは重ねがけできるようにしてあるので、それぞれのフィルタの速度差を測るときは、フィルタを掛けたら一度元の画像に戻すを押してから次のフィルタをすると、同じ条件でできる
画像クリックで元の画像と切り替え
 
 
関連記事
前回、2019/5/29は3日前

gogowaten.hatenablog.com

メディアンフィルタで画像のノイズ除去試してみた、WPFC# ( ソフトウェア ) - 午後わてんのブログ - Yahoo!ブログ
https://blogs.yahoo.co.jp/gogowaten/15965377.html