うえぽんSW局

　以前どこかで入手した画像。
　おっさんの中でもシューターしか知らないだろう問題を5歳児に出題するあたりがナイスと思います。
　（これ以外の問題も難しいらしい）

[追記]
　メールをいただきました。クイズ問題はタイトー社内から公募したもののようです。一緒に画像も貰ったの連結してみました。「INSERT COIN」とある通りデパートの屋上なんかにあるアーケードゲームなんですね。

　ネット検索してもメディアンフィルタ（中央値フィルタ）をSIMD（SSE2などのこと）で高速化しているのをあまり見かけないので作ってみました。
　AviUtl用のフィルタです。いつものところにアップしてあります。

　作った理由は、デジカメを最近買って、ごま塩ノイズを除去するのにはメディアンフィルタが一番だろうと思ったからです。

　さてメディアンフィルタは教科書に載っているような基本的なノイズ除去フィルタです。
　仕組みは注目点およびその周辺の8近傍もしくは4近傍をソートし中央値（メディアン）を求め、それを注目点に置き換えるという単純なものです。
　中央値は平均値と似たような値になるので系統としてはぼかし系のノイズ除去になります。平均値との違いは、極端な値（ごま塩ノイズなど）の影響を受けにくいことです。

【サンプル】
　デジカメは露光時間が長くなると白い点がぽつぽつ出てきます。下左の画像は8秒間露光撮影した画像の一部です。下右は分かりやすいように白い点に赤丸を付けました



　処理後は下のとおり。



【分岐しないソート】
　ソートアルゴリズムには様々ありますが、条件分岐があると遅くなるので、分岐しないソートを使うことにしました。
　SSE2には2値を比べてmax（もしくはmin）を求める命令があるので、それを使って比較してスワップということします。組み込み関数を使うとこんな感じです。



　SSE2未対応CPU用にMMX版もあります。



　さて、ソートするといっても中央値を求めれば充分なので完全にはソートしません。8近傍（注目点を含め9点）の場合、19回の比較で中央値は求まります。19回の順番はパズルゲームのようなものなので、答えは自分で考えてください。バブルソート風に比較した場合は28回ぐらいだと思います。

　[追記:2010/04/17]
　MMX版は以下のようにXORでやった方が速いようです。楓 software: x86 SIMD Technique アーカイブを参考にしました。



　SSE2版も同じように試してみましたが、これは_mm_max_epi*を使用した方が速かったです。もしかしたらCPUによるかもしれません。

【SIMD化】
　上を見れば分かりますが、副作用でSIMD化されてます。
　SSE2はshort型(16bit)を8個同時に計算できるので、平均比較回数は19/8 = 2.375回となります。

【マルチスレッド化】
　処理範囲を分割すれば容易にマルチスレッド化できます。しかもAviUtlにはマルチスレッド用の関数が用意されているので簡単です。
　こういうページも参考になるかと思います。
　並列アプリケーションを作ってみよう - SourceForge.JP Magazine

【高速メモリコピー】
　SIMD化や分岐しないソートで高速化しましたが、ここまでやるとメモリーコピーの速度に近くなります。もっと速くしようとすると高速メモリコピーと同じことをする必要があります。
　高速なメモリーコピーについてはアマレココの作者のこの雑記が参考になります。
　アマレココのサイト：過去雑記2009年12月〜2月
　プリフェッチはあまり効果が無いとあります。たしかにCPUにはハードウェアプリフェッチ機能があるので少し先をプリフェッチしただけでは効果はありません。もし効果を得たいのであればずっと先をプリフェッチする（1ライン先をL2にプリフェッチぐらいのことをする）必要があります。

【ベンチマーク】
　getclk_p.aufで測定。デジカメ用に作ったのでテスト素材はサイズが4000x3000の画像です。有効桁数は3桁。



　[追記:2010/04/17]
　MMX版をXORにしたところ以下のように速くなりました。



　SSE2で輝度のみの方が少し遅くなるのは、SIMD用に並び替えするコストの方が大きいからだと思います。