|
技術解説 |
|
空間フィルタ |
| 最終更新日：2007/04/26 修正 |
●概要
画像に二次元フィルタ関数をコンボリューションする処理である。ここでは実空間フィルタを対象とし、その理論ではなく、処理方式について述べる。理論については、世の中に腐るほど解説されている。
●原理
連続系では畳み込み積分であるが、離散系なので積和となる。実空間では、ひたすら画像のピクセルに対して、フィルタマトリクスを掛けて足す演算を繰り返す。
●処理方式
与えられた空間フィルタは、N X M (N、M ＞ 3 で奇数 )とする。
○原画空間の準備
ある空間フィルタで、どうも周辺に枠のようなアーチファクトが出るので、文献で調べると、画像空間の拡張は、鏡像拡張にするとあった。単なるリピートではやはり特有の癖がでるらしいので、早速対応した。
- 画像ビットマップからマーシャルにてバイト配列を取り出す。
- 目的に応じて、輝度あるいはRGBにする。
- 原画は、周辺処理のために周辺(上辺、下辺、左辺、右辺)を鏡像拡張する。四隅は、下図のように、原画の各四隅を中心とした点対称でコピーする。
○コンボリューションする
- 原画の左上の画素から順にフィルタ関数と積和演算する。積和演算はDouble で行う。
- 方向性のあるフィルタの場合、画像の方向とフィルタの方向が整合するように注意する。
- 積和結果をバイトに丸めて原画のバイト配列に入れる。
○処理画像を生成する
指定の結果ビットマップの画像として、上記の結果を入れたバイト配列を転送する。
●高速化
○画素アクセス速度
ループ回数が大きいので、ループ処理のオーバヘッドは演算時間に影響が多い。画像は、二次元なので、何の気なしに二次元配列で演算してしまう。しかし、この二次元配列は便利ではあるが、実はオーバヘッドが大きい。内部でのアドレス演算で乗算が使用されるからである。従って、画像や、空間フィルタは一次元配列で演算するほうが速くなると期待される。
ビットマップからマーシャルにて取り出した画素バイト配列は一次元となっているので、問題ない。空間フィルタ演算では、周囲に画素を拡張しているが、このとき、二次元にすることが多い。果たして二次元はどうなのか確認のため実測してみた。測定値はカーネル部分のみの時間で、実際の空間フィルタ全体の時間ではない。
・2D関数と1D関数
空間フィルタの関数を二次元配列か一次元配列かによる違い。縦軸は、フィルタサイズである。上図は、1画素あたりの係数アクセス時間(係数を配列から取り出す時間)を測定したものである。明らかに、一次元配列の方が2〜3倍速い。
・2D関数2D画像、1D関数2D画像、1D関数1D画像
カーネルのみでは、ぴんとこないので、1024 X 1024
画像に対する空間フィルタ演算の係数と画素の取り出し、積和演算の総時間を模倣して計測した。予想通り、1D関数1D画像が一番速くなっている。何も考えないでコードした場合の約3倍速くなっている。暗黙的にも、明示的にも、アドレス(インデックス)算出時の乗算を排除すれば、高速化ができると言うことである。
○アドレッシング
関数は一次元にして、順番にアクセスすれば良い。データ(画素)は、不連続になるので、演算が必要になるが、この時、乗算を排除すれば良い。しかし、係数に対応する画素の相対位置は決まっているので、予めテーブルを準備しておけば良い。これで、相対位置の値を簡単に求められる。
○参考 二次元配列とCPUキャッシュ
二次元配列である程度大きいと、CPUキャッシュの影響が大きくなる。それは、二次元配列の要素のメモリ上の並び方とアクセスの仕方で決まる。下図は、同じ二次元配列(Double)の、縦、横のアクセス順を変えて要素の取り出し時間を計測したものである。参考までに、完全一次元配列での速度も測定した。
同じ配列でもアクセス順が異なると時間に大きな差が出ていることが分かる。サイズが大きくなると10倍以上の開きが出ている。
・X,Y DD(X, Y ) において、For X = 0 To 〜 For Y 0 To 〜 としたアクセス
・Y,X DD(X, Y ) において、For Y = 0 To 〜 For X 0 To 〜 としたアクセス
配列とアクセス順の自然さでは、Y,X となるが、これは遅くなる。つまり、D(X,Y) では、メモリ上では、X0Y0, X0Y1, X0Y2
と並んでいることになる。画像の縦横イメージ(Xが横軸)を維持して二次元で早くアクセスする場合は、D(Y,X) とし、For Y = 0 To 〜 For X 0
To 〜 とアクセスするのが良い。
いずれにしても、一次元が最も速い。但し、画素のアクセスが概ね、頭から末尾に向けて順々にアクセスする場合の話で、ランダムアクセスであれば、配列構造と無関係になる。しかし、空間フィルタなどは、頭から末尾に向けて順々にアクセスするので、配列構造には注意を向けた方が良い。
○C++版
全てのフィルタメソッドにはC++版を用意している。