信号処理入門

このブログポストは、Matt Pettineo氏のSIGNAL PROCESSING PRIMER(2012)を、原著者の許可を得て翻訳・公開したものです。全ての権利は、原著者にあります。

エイリアスとアンチエイリアスを理論的に理解するために、信号処理とサンプリング定理の分野を学習しよう。このアーティクルでは、この関連した二つの分野の基礎について私の言葉で理論的な視点から説明する。次回のアーティクルでは、このアーティクルで説明する概念を使って、リアルタイムグラフィックスの分析をする。そのときには、それらを信号処理の文脈で記述することができるようになっているだろう。もしより詳しい文献がほしければ、Physically Based Renderingの7章、Real-Time Rendering第三版の5章、Principles of Digital Image Synthesis(これは無料でダウンロードできる)を薦める。

いつものように、私は私のことを賢いと思わせるような教材よりも、教材が正確であることのほうが大切だと思っている。だから、ここにある内容が正確ではないと感じたり、シェアしたい知識があったらコメント欄に書いてほしい。(訳注:翻訳版にはコメント欄はありません)

サンプリング定理

サンプリング定理は、「連続した一つか複数個のパラメターが変化する何らか信号」の処理と、「それらのパラメーターを離散的にサンプリングすること」を扱う。もし信号や信号処理について詳しくなければ、信号を何次元かの連続した関数でそれぞれの領域で変化するものと考えればいい。それをサンプルすれば、その曲線に沿った関数の特定の位置の値を計算したことになる。ふつうはサンプルする点は均等な間隔にあり、それをユニフォームサンプリングと呼ぶ。たとえば、1次元の信号を$$f(x) = x^2$$と定義し、サンプルはx=0,x=1,x=2,x=3の位置でするかもしれない。これにより離散的なサンプルの集合を得ることになる。この例では0,1,4,9だ。次の図が連続した関数$$f(x)=x^2$$の関数と、それをxが整数の場所で離散的にサンプリングをしたものだ。

連続関数を離散的にサンプリングしたもの

離散的にサンプリングすることは、たくさんのメリットがある。例えば、任意の信号をメモリーの中に保存したければ、単純にサンプルされた値を配列として格納すればいい。また信号に対する操作も、同じ操作を全てのサンプルされた点に対して繰り返し行えばいい。しかしサンプルされていない位置の信号の値が必要になったときはどうすればいいのだろうか。このような場合は、元々の連続関数の近似を算出する「再構成」として知られる処理が使える。この近似によって、新しいサンプル位置に対するサンプル、つまり"リ"サンプリングができるようになる。狭い区間での不連続値から、その"間の値"を計算する「補間」と呼ばれることもある。

実際の再構成の処理は、なんらかの再構成フィルターを離散的なサンプルに対して適用することにより行われる。典型的にはこのようなフィルターは、x=0で対称な形をしており、x=0の近辺でしか0以外の値がないような形をしている。次の図は再構成フィルターによく使われる関数のいくつかの例だ。

* 再構成フィルターに使われるさまざまな関数。左上から時計回りに、矩形関数、三角形関数、sinc関数だ。 図はReal-Time Rendering, 3rd Edition, A K Peters 2008より

このフィルターは畳み込みと呼ばれる処理で適用される。

サンプルが離散的である場合は、畳み込みはフィルター関数の中心を、各サンプル位置に移動させたあとに全てのサンプル位置の値と乗算したものを足し合わせる処理を意味する。このことについてよくわからなかったら、次の三つの図を見ると良い。これらは三つの良く知られた再構成フィルターによる畳み込みの結果を表している。

矩形関数、三角形関数、sinc関数による離散的にサンプルされた信号の再構成。Real-Time Rendering, 3rd Edition, A K Peters 2008より

フルスクリーンでのガウシアンブラーのシェーダを書いたことがあるなら、あなたは畳み込みを使ったことがあることになる。どのようにそのようなシェーダーを書いたかを思い出して欲しい。「テクスチャ中の近くのピクセル値を走査する(サンプル点に相当)、サンプルしたそれぞれの値と出力するピクセルからの距離をガウス関数に評価させた結果を乗算し、それらを合算する」。サンプル点への距離を使って関数を評価したことは、(あなたはそう思っていなかったもしれないが)フィルター関数をサンプル点に移動させたことと同じことになる。

よくある再構成フィルターの中でsincフィルターは特に面白い。このフィルターは十分にサンプルされた信号が与えられすれば、理論上では元々の連続した信号を正確に再構成することができるからだ。これは完全再構成として知られている。連続した信号が"十分にサンプルされた"ことを定義するには、エイリアシングについて議論しなくてはならない。

まとめ。

  • 連続した信号(関数)は離散的な位置でサンプルすることが出来る。
  • 離散的な位置でサンプルされた値に対してフィルターを適用することで連続した信号の近似を再構成できる。

周波数とエイリアシング

信号は周波数から説明されることがよくある。周波数は領域内でどれだけ信号が変化したかを表す大雑把な用語だ。現実の信号は一つの周波数からは成立するわけではなく、周波数のスペクトラムとなる。数学的には、元の信号(たいていは時間領域か空間領域で表現されている。どちらになるかは文脈による)から周波数スペクトラム(周波数領域として知られている)にフーリエ変換を使うことで変換ができる。いちど周波数領域に変換したら、最大周波数、つまりそれ以上の全ての周波数の強さが0になるような周波数が存在するか確認できる。最大周波数があった場合、その信号は帯域制限信号と呼ばれる。つまり信号の帯域を決めることができることができるのだ。文脈により、"帯域"という用語は通過帯域の意味と基底帯域の意味の二通りの意味になる。通過帯域は最大周波数から最小周波数を引いたもので、基底帯域は単純に最大周波数を指す。信号理論では、基底帯域の意味で使われていると考えたほうがいい。なぜなら基底帯域は信号のナイキストレートを決定するからだ。ナイキストレートは、エイリアシングの発生を抑制するために最低限必要なサンプリングレートのことで、それは基底帯域の二倍だ。"エイリアシング"とは、信号はサンプル数が少ないときに実際の周波数よりもより低い周波数の信号と区別がつかなくなるという事実を指す。下記の図は、この現象のデモンストレーションだ。周波数の違う二つのsin波に対して、どのようなサンプルであっても同じ値となってしまっている。

サンプルされたSin波のエイリアシング。図はWikipediaより

実際問題、アンダーサンプリングによって生じるエイリアシングは信号の再構成としては誤りだ。言い換えれば、信号は最終的には元々のサンプリング元とは違うものとなってしまう。帯域制限をされていない信号は、最大周波数や、これだけやれば再構成後にエイリアシングが発生しないと言えるようなサンプリングレートはない。

どうしてそしてなぜエイリアシングが起こるかについてより深く理解するには、周波数領域で考えてみるとよい。任意の信号の周波数スペクトラムがプロットされたものを見てみよう。

任意の信号の周波数スペクトラム。図はWikipediaより

プロットを見てわかるように、"B"が最大周波数だ。つまりこの信号は帯域制限されており、Bがその帯域だ。この信号を離散的にサンプルすれば、さまざまな位置での信号の有限のコピーが現れる。つまり次の図のようになっているのだ。

信号の周波数スペクトラムのコピー。図はWikipediaより

信号のコピーがどこに配置されるかはサンプリングレートによってきまる。サンプリングレートは、"fs"とプロット中では記載されている。これらのコピーがあるので、それを取り除くためにフィルター(再構成フィルター)を使い、もとの信号の(基底周波数の意味での)帯域のみが含まれる周波数スペクトラムのみを残すようにしないといけない。最も明快な解決方法は周波数領域で矩形関数を使うことだ。なぜなら矩形関数は決められた範囲に対して1を掛け、範囲外に対しては0を掛けることを意味しているからだ。そのため幅Bを持つ矩形関数を使えば、コピーされた信号を取り除き、元の信号をそのまま切り取れる。次の図はこれがどのように働くかを示している。

信号のスペクトラムのコピーから分離するために再構成フィルターを使う。図はWikipediaより

ただ普通は再構成フィルターを周波数領域ではなく空間領域において適用させる必要があるということを念頭に置かないといけない。つまり周波数領域での矩形関数を、空間領域に持っていったものを使わないといけないのだ。そしてこれは結局は前に触れたsinc関数だ。さてこれでなぜsinc関数が特定の周波数の範囲を残し他の周波数を完全に取り除くことができる完全再構成フィルターとなっているのかがわかった。同じ理由で周波数領域での矩形関数が理想的なローパスフィルターとして知られていることもわかった。

ここで適切なレートで信号をサンプルしなかったときにどうなるかを見てみよう。最初の方で見たように、信号のコピーはサンプル周波数の乗算として現れる。そのためサンプリングレートを上げれば上げるほど隣にあるコピーは離れ、逆にサンプリングレートを下げれば下げるほど近づいていく。信号のサンプリングレートの限界は2Bであることを最初の方で知った。なので、すでに2B以下のレートでサンプルされた信号のプロットを見てみよう。

適切ではないサンプリングレートのために信号のコピーを跨いだ場合。図はWikipediaより

信号のナイキストレート以下になってしまうと、周波数領域において信号のコピーが重なってしまう。こうなってしまうとsincフィルターでコピーと元の信号を分離することはできなくなり、エイリアシングが発生してしまう。上図の下のプロットは元の信号のエイリアスがどのようになるかを示したものだ。周波数応答は元の信号と同じになってしまうので、区別することができなくなる。

まとめ。

  • 信号は周波数のスペクトラムに分解でき、そのスペクトラムは信号の変化を表す。
  • 周波数の最大値がある信号は、基底帯域が信号だ。
  • 信号のナイキストレートは最大周波数の二倍で、エイリアシングを発生させることなく再構成をさせるために最低限必要なレートだ。
  • 信号の再構成は、周波数領域での信号のスペクトラムの"コピー"の除去として考えることができる。

再構成フィルターの設計

アンダーサンプルの結果によるエイリアシングは再構成が行われる前にすでに発生しているので、プリエイリアシングと呼ばれる。しかしアーティファクトは再構成の処理そのものによりからも起こりえる。例えば、再構成フィルターとして、とても幅の広い矩形関数を使った場合を想像してみよう。結果は次のようになる。

幅のある再構成フィルターがオリジナルのスペクトラムとそのコピーとを分離するのに失敗している。図はWikipediaより

このような再構成方法では、十分にサンプルされていたとしても、再構成した信号にアーティファクトが生じてしまう。

デモンストレーションしたように、間違った大きさの矩形関数を周波数領域で使うと、再構成された信号のクオリティに悪影響を与えてしまう。すでに述べたように空間領域でのフィルターとして様々な関数を使うことが出来る。そしてそれらの関数全ては周波数領域での関数をもち、そしてそれは前に議論した矩形関数とは違う。つまりフィルターを選択するとき、そのフィルターが周波数領域でどのくらいよく信号を分離するかと、再構成された信号にどの程度ポストエイリアシングを起こすかを推測することができる。よく知られたフィルター関数を見てみて、その関数に対応する周波数空間の関数のプロットを見比べてみよう。

空間領域のフィルター関数に対応する周波数領域の関数を見てみると、興味がある周波数の範囲をどの程度保持し、関心の無い信号スペクトラムのコピー部分をどの程度取り除くかをおおよそ推測できる。フィルター設計の分野では、フィルターの周波数領域でのスペクトラムを解析するこのプロセスに最も関心を払い、フィルターの全体的なパフォーマンスの評価、推定に利用している。上の図でプロットされたスペクトラムを見てみると、sinc関数以外全て基底周波数が何らかの形で狭くなっている。いくつかの関数では、周波数領域では、周波数の上限値の最大周波数がなく、どちらの方向にも無限に拡張しているものものある。これはつまるところ、無限にある信号のスペクトラムのコピーが、再構成された信号ににじみ出しエイリアシングを発生させるということだ。

空間領域でのフィルター関数とその周波数領域での同等の関数のプロットを観察することで一つ一般的な法則があることがわかる。片方の変化の量と、その反対の変化量に逆相関の関係があるということだ。例えば、空間領域での矩形関数を見てみよう。矩形関数は非連続な関数で、非連続な場所は変化量が無限になっている。そのため、この関数の周波数領域での関数は無限の幅があるsincとなっている。これは矩形関数の非連続さ、つまり無限の変化量の影響を受けたことを表している。同じようにして、空間領域でのsinc関数は、周波数領域では矩形関数となる。これはこの二つが交換の関係だからだ。ガウス関数は特別だ。空間領域でも周波数領域でも同じ関数になる。なぜならガウス関数が、スムースな変化の関数とシャープな変化の関数のちょうど中間にあるからだ。この関係のもう一つの重要な点は、このフィルターの幅をより大きくでき(入力された距離を1より大きな数で割ればよい)、そうすればこの関数による周波数スペクトラムはより狭くなるということだ。例として、幅が1の単位長の矩形関数のスペクトラムと、幅4の矩形関数のスペクトラムを比べてみよう。

幅1の矩形関数の周波数領域でのスペクトラム

幅4の矩形関数の周波数領域でのスペクトラム

この図は、フィルターのカーネルが広くなればなるほど、周波数の低い方の強さがより強くなることを明確に示している。これは前に述べた空間領域と周波数領域での変化量のもう一つの特徴だ。"広い"関数はより緩やかに変化するので、より低い周波数の成分をその周波数スペクトラムに含むようになる。

フィルター設計の難しいところは、フィルターの周波数領域での形についてだけではなく、再構成された信号になる空間領域での形の影響についても考えないということだ。特に、sincフィルターのような負のローブを持つフィルターは慎重にならないといけない。このようなフィルターを鋭い変化のある非連続の部分に適用するとリンギングとして知られる現象が発生する。sincフィルターによって再構成された矩形波を見てみよう。

矩形波をsincフィルターで再構成したときのギブス現象

まとめ。

  • 不十分なサンプリングレートによるエラーはプレエイリアシングとして知られている。まずいフィルターによって発生するエラーはポストエイリアシングとして知られている。
  • あるフィルターがエイリアシングをどの程度抑制するかは、そのフィルターの周波数領域での形を見れば推定することができる。
  • あるフィルターの空間領域での変化量と、周波数領域での変化量は逆相関になっている。
  • あるフィルターの空間領域での形は信号の再構成のクオリティに影響を与える。もっともわかりやすい影響は非連続領域に発生するリギングだ。

参考文献

[1]http://en.wikipedia.org/wiki/Signal_processing
[2]http://en.wikipedia.org/wiki/Nyquist-Shannon_sampling_theorem
[3]Pharr, Matt and Humphreys, Greg. Physically Based Rendering – From Theory to Implementation, 2nd Edition.
[4]Akenine-Möller, Tomas, Haines, Eric, and Hoffman, Naty. Real-Time Rendering, 3rd Edition
[5]Glassner, Andrew. Principles of Digital Image Synthesis

個人的なメモ