非線形フィルタ

　逆変換で元に戻らないようなフィルタで、ランクフィルタ、メディアンフイルタ、最頻値フィルタなどがある。

　局所領域内の画素値を小さい順に並べ、指定の順位の画素を注目画素とするものである。ソート結果から元の画素を取り出せるようにRGBをパック処理し、それに輝度情報もパックし、それをソートする。こうすれば、アンパックすれば元のRGB値が得られる。パック/アンパック処理は、VBでもシフト命令が使えるので高速に処理ができる。

　ソートが支配的となる。幸い、VBでは、ArrayクラスのSortメソッドを使用すれば、最速となる。しかし、C++では、クイックソートなどは、データ数が比較的小さいので(高々100程度)、再帰や関数呼び出しのオーバーヘッドが大きくなり、それほど高速にならないことが分かった。そこで、クイックソートではなく、バケットソートに変更した。これは、データ数とその値が限定されることで可能となる方式である。詳しくはココを参照。

　メディアンフィルタもランクフィルタで、ランク(順位)を中間にした特別なものとなる。

　ごま塩ノイズやスクラッチノイズを除去するために使用される。平滑フィルタと比べ画像のエッジが保存さる利点がある。しかし、原理上、最近傍補間のようなものとなるので、濃度密度の高域(つまりきめ細かさ)は、たとえば 3 x 3 において 2/3程度に落ちる。全体として、のっぺりする。これは、常に機械的に中間順位のピクセルに置き換えるためで、ノイズではないピクセルも置き換わってしまうからである。

　そこで、このライブラリでは、ハイフィルタと称して、注目ピクセルが、ランクが上位と下位(双方ともノイズと推定される)に等しくなければ、置き換えないモードを独自に追加している(例によって、これが正しい方法という保証はない)。

　上図のように、注目値が、ノイズと推定される値の場合は良いが、注目画素が実際には、緑線であっても、採用値に置き換わってしまう。

　局所領域内の画素値(濃度ではなく色として)で度数分布を取り、その度数が最大の画素を注目画素にする。これを施すと、油絵のような感じになる。

　例えば、色の階調を32に落とせば、色空間は、256*256*256 = 16777216から、32*32*32 =32768 となる。これぐらいなら、ヒトグラムとして処理が可能となる。しかし、画素毎のヒストグラムの処理で、32768の大きさの配列をクリアーするのは、オーバーヘッドとしてかなりのものとなり、処理時間はとても実用とはならなかった。また、実際にヒストグラムとしてカウントされるのは、高々フィルタサイズ分なので、配列利用率は 3 X 3 フィルタでは、9/32768 = 0.003% と余りに無駄が多い。

　そこで、ハッシュテーブルにして見た。VB.NETでは標準でハッシュテーブルクラスがあり、何も気にしないで使用できる。これにて、空間の利用率はほぼ100%となる(つまり、32768の空間を9に写像してくれる)し、画素毎の初期化もオーバーヘッドにならない。しかも、特に、階調を圧縮しなくても処理はできる。これは効果が絶大である。

　しかし、C++エンジンで困ってしまった。ハッシュテーブルクラスは標準C/C++関数ではない(なんとなくC++にはありそうなのだが、筆者の今の実力では不明)。そこで、以下のような簡易ハッシュテーブル方式を考えた。

　ネットを調べると、C++によるハッシュテーブル関数などのコード例が紹介されているが、皆汎用なので複雑すぎる。そこで、今回の用途に限定してみた。

　この場合、フィルタサイズ以上の種類(個数)のデータは絶対にないので、これにてハッシュテーブルサイズを限定し固定化できる。サイズを可変にすると途端に複雑になる。フィルタサイズの最大を 21 X 21 とすると、ヒストグラムで現れるデータ種は、441種となる。ハッシュのコリジョンを考慮し、(超)最悪でも1000あれば問題ない。コリジョン処理は、リスト形式にするのが定石であるが、今回は、コリジョン分は、一箇所に集め、そこは線形検索方式にした。コリジョンの確率が低いと見た。下図参照。

　ハッシュされるのは、Integerの整数とできるので、階調は減らす必要はない。ハッシュコード Hc は、

で求める。443 は、441以上の最も小さな素数。このHcがハッシュテーブル本体の格納位置となる。ハッシュテーブルは、元の値IV(Key) と、度数が格納されている。始めに度数をクリアーし、局所領域内の画素単位で以下の処理を行う。

Array.Clear(HT, 0, 1000)　　　'ハッシュテーブル　度数　初期化
Array.Clear(HK, 0, 1000)　　　'ハッシュテーブル　Key　初期化
le = 500                             'コリジョンカウンタ、ロケータ初期化
For k = 0 To MSz - 1
   pp = bpp + AT(k)
   KK = Dy(pp)                     '画素値
   DK = KK Mod 443              'ハッシュコード
   If HT(DK) = 0 Then
      HK(DK) = KK
      HT(DK) = HT(DK) + 1       '新規登録
   Else
      If HK(DK) = KK Then
         HT(DK) = HT(DK) + 1　　'一致
      Else
         For l = 500 To le - 1　　　'コリジョン領域検索
            If HK(l) = KK Then
               HT(l) = HT(l) + 1      'コリジョンにて一致
               Exit For
            End If
         Next
         If l > le - 1 Then
            HK(l) = KK
            HT(l) = HT(l) + 1　　　　　'コリジョンに登録
            le = l + 1
         End If
      End If
   End If
Next

このあと、ハッシュテーブルの度数を総なめして最大度数を見つければ良い。

　下の表は、以前のVBでのハッシュクラス利用時の速度である。画像転送はいずれもマーシャルである。通常版がそのままでヒスト処理の場合、高速版がハッシュクラスである。

　簡易ハッシュテーブル版のVBとC++での結果は、次の通り(フィルタサイズ(筆サイズ)は、3 X 3)となった。

画像サイズ	VB	C++
512 X 512	0.8 S	0.4 S
1024 X 1024	3.24 S	1.6 S
2048 X 2048	13 S	6.4 S

　改善されている。C++では更なる改善ができた。簡易ハッシュテーブル法は有効である。

　C++版では、フィルタサイズが15 X 15 以上になると、なんとVBより遅くなってしまう。色々調べた結果、コリジョン処理部分で、コリジョン領域の開始ポイントが、0 になっていた。正しい値は500。修正してOKとなった。その調査のため、試験画像におけるコリジョン数の最大を計側したが、フィルタサイズが大きくなると、その数も大きくなっており、19 X 19 では、180 位であった。意外に大きいので、やはり、リスト構造にした方が良いかも。この場合、線形検索のための平均比較回数は、(180/2) * (180/4) でおよそ4000回となる。毎画素4000回なのでバカにならない。

　と言うことで、ハッシュテーブルを少し本物らしく改良した。コリジョン領域は、そのハッシュコードに対するリスト構造にした。これで、コリジョンを起こしたハッシュコード分のみのリスト検索となり、余計な検索(常に全てのコリジョンを検索すること)はなくなる。

ハッシュテーブルは多次元配列を排除するため項目単位に独立した配列にしている。

Dim HK(1000) As Integer     'ハッシュキー
Dim HC(1000) As Integer    'ハッシュカウント
Dim HP(1000) As Integer    'コリジョンポインタ

Array.Clear(HC, 0, 1000)         'カウントのみ初期化、あとは登録時に個々に初期化
CLP = 500                            'コリジョン空き先頭ポインタ
For k = 0 To MSz - 1
   pp = bpp + AT(k)
   KK = Dy(pp)
   DK = KK Mod 443               'ハッシュコード(443未満を保証)
   If HC(DK) = 0 Then               '新規
      HK(DK) = KK
      HC(DK) = HC(DK) + 1
      HP(DK) = 0
   ElseIf HK(DK) = KK Then          '一致
      HC(DK) = HC(DK) + 1
   ElseIf HP(DK) = 0 Then                 'コリジョンの新規
      HK(CLP) = KK
      HC(CLP) = 1
      HP(CLP) = 0
      CLP = CLP + 1
   Else                                     'コリジョン検索開始(リスト処理開始)
      IX = HP(DK)
      Do
         If IX = 0 OrElse HP(IX) = 0 Then        'コリジョン内で新規
            HK(CLP) = KK
            HC(CLP) = 1
            HP(CLP) = 0
            CLP = CLP + 1
            Exit Do
         ElseIf HK(IX) = KK Then                'コリジョンで一致
            HC(IX) = HC(IX) + 1
            Exit Do
         End If
         IX = HP(IX)                             '次のアイテム
      Loop
   End If
Next

　改良簡易ハッシュテーブル版のVBとC++での結果は、次の通り(フィルタサイズ(筆サイズ)は、3 X 3)となった。

画像サイズ	VB	C++
512 X 512	0.57 S	0.28 S
1024 X 1024	2.28 S	1.28 S
2048 X 2048	9.06 S	5.24 S

手抜きハッシュ法より更に速くなった。