[ ホーム ] [ PC技術/システム技術 ] [ VB.NETプログラミング ] [ VB.NETコンポーネント ] [ VC++コンポーネント ] [ 共通事項 ] [ インフォメーション ]

上へ
C++ネイティブDLL
試作第1号
試作第2号

●概要

　空間フィルタは目星がついたのでランクフィルタの試作をした。

●予備実験

　取りあえず、現行方式をそのままC++に移行した。C++が担うのは、簡易輝度にした拡張済Long配列を受け取り、局所空間の画素濃度をソートし、指定順位の画素を結果バイト配列に格納すると言うもの。

　そのため、新たに、クイックソート関数もC++で作成した。しかし、期待に反して、VB + マーシャル転送 より遅くなった。1.2〜1.5倍程度。ガックリ。

　試しに、VB のArray.Sort メソッドと、C++ のクイックソートを省いて実行すると、C++ が断然速くなった。VB の3〜5 倍。原因は、クイックソートである。.NET のArray.Sort の方式は不明であるが、作成したクイックソートは、再帰呼び出しをしており、しかも、画像の画素数分の回数だけ呼び出されるので、多分、オーバーヘッドが大きいかもしれない。Long(C++ では、long long )をやめ、Integer にしても、同じであった。比較的ソートデータ数が小さく（大きくても100前後）、呼び出し回数が圧倒的に多いのが敗因か？Webを調べると、同じような意見が出ていた。

●新アルゴリズムの検討

　C++を折角始めたのに、ここで挫折したくないので、全体として高速化でき、しかもC++が優位になるような手法を検討する。

○ソート方式の検討

　クイックソートの高速化はやめ、再帰呼び出し不要なアルゴリズムを検討することにした。最も速いのは、バケットソートである。これは、Ｏ(n) の時間見積りになる。しかし、このソートは原始的なハッシュ法なので、実用する場合は、データ値が、ある連続空間にないといけないし、データ値分の入れ物が必要になる。現在は、Long値がデータなので、このままでは適用できない。

○データ空間を限定化する

　現在は、(R+G+B)*2³² + (R,G,B)₃₂ である。下32ビットは、ソートされた値から、元のRGB値を再生するためのものであり、また、R+G+Bが同じ値の場合は、R、G、B の優先度で順位を決められることも狙っている。

　ところで、簡易濃度はこの際、YCC空間の輝度Yにすれば、256までに圧縮できるし、輝度として比較的正確に表現できる。これにより、(Y,R,G,B)₃₂ と、8ビット単位でパックした下図のようなUInteger値にする。

YRGBのパック値

○構想

　以下のように考える。

1. 画素をYCCで輝度変換し、パック値とする。
2. 局所領域の画素で、パック値からYを取り出し、バケットソートする。基本的には、Yをインデックスにして、ソート配列に局所領域の位置情報を入れるだけ。同じ値の場合は、後のものが有効。
3. ソート領域は、歯抜けになっているので、要素が0の部分を詰める。
4. 詰められた空間と局所領域のマッピング係数を決める。
5. 指定のランク(順位) を、ソート空間にマッピングし、対象の画素を選ぶ。
6. その画素を新しい値とする。

○カーネル

　VBでの処理である。C++ も全く同じとなる。

MSz ：局所領域サイズ(フィルタ要素数)
DR() ：UIntegerのパック値配列
bpp ：パック値配列のインデックス

Dim AT(MSz - 1) As Integer         '局所領域アドレステーブル
Dim BS(255) As Integer             'バケットソート領域

'一つの局所領域の処理

Array.Clear(BS, 0, 256)                  'ソート領域をクリア
For fp = 0 To MSz - 1
   IY = DR(bpp + AT(fp))
   IY = IY >> 24                             'Yを取り出す
   BS(IY) = fp + 1                          'バケットソート
Next
pp = 0
For k = 0 To 255                            '歯抜けを詰める
   If BS(k) > 0 Then
      BS(pp) = BS(k) - 1
      pp = pp + 1
   End If
Next
mm = (pp - 1) / (MSz - 1)               'マッピング係数

'指定のランクの画素は、

IY = DR(bpp + AT(BS(CInt(mm * Rank))))
IR =(IY & 0xFF0000) >> 16;
IG =(IY & 0xFF00) >> 8;
IB =(IY & 0xFF);

で取り出せる。

●結果

メディアンハイフィルタ、1024 X 1024 画像、フィルタサイズ 15 X 15 にて実測した。 3者とも同じ結果が得られたことも確認できた。