離散コサイン変換

離散コサイン変換は、離散信号を周波数領域へ変換する方法の一つである。

1. 概要
-----

DCTは、有限数列を、余弦関数数列 cos を基底とする一次結合の係数に変換する。余弦関数は実数に対しては実数を返すので、実数列に対してはDCT係数も実数列となる。

これは、離散フーリエ変換  が、実数に対しても複素数を返す exp を使うため、実数列に対しても複素数列となるのと大きな違いである。なお、DFTも偶関数数列に対しては実係数を返す、つまりコサイン成分のみとなるが、DCTは//y//軸で折り返して偶関数化してDFTすることと等価であり、実際にそう計算することが多い。

DCTでは、係数が実数になる上、特定の成分への集中度があがる。JPEGなどの画像圧縮、AACやMP3、ATRACといった音声圧縮、デジタルフィルタ等広い範囲で用いられている。

逆変換を逆離散コサイン変換と呼ぶ。

2. 種類
-----

DCTには標準的な方法が8通りあり、そのうち4つがふつうに用いられる。最も一般的な方法は type-II DCT であり、単にDCTと呼んだ場合これを指すことが多い。同様に、DCT-IIの逆変換である type-III DCT は単に逆DCT  ないしIDCTと呼ばれることが多い。

DCTに関連する変換法が二つある。一つは離散サイン変換  であり、実領域で奇関数を用いた離散フーリエ変換  と等価である。もう一つの修正離散コサイン変換  は「互いに重なりのある」データのDCTに基づいている。

3. 応用
-----

DCT、特にDCT-IIは信号・画像処理にしばしば用いられる。特に不可逆圧縮に頻用されるが、これはDCTの持つ強力な「エネルギー圧縮」特性による。DCTで変換すると、情報が少数の低周波成分に集中する傾向が生まれ、マルコフ過程の制限に基づく信号について、非相関成分の検出に最適であるKarhunen-Loève変換に近い。

たとえばDCTはJPEG、MJPEG、MPEG、DV等の画像圧縮に用いられる。これらの画像圧縮では、//N// × //N// のブロックに2次元DCT-IIを行い、その結果を量子化し、エントロピー圧縮する。典型的には //N// = 8 であり、そのブロックの行ごと、列ごとにDCT-IIの式を適用する。その結果得られる 8 × 8 行列は、要素  をDC成分とし、行・列とも、添字が大きくなるほど垂直ないし水平方向の空間周波数が高い成分を表す。

音声圧縮に用いられるMDCT、AAC、Vorbis、MP3も関連した変換法である。

DCTは、偏微分方程式をスペクトル法で解くときにも広く使われる。その場合、配列の両端での境界条件の偶奇性に対応して、異なるDCTの変種が使われる。

DCTはまた、チェビシェフ多項式とも密接に関係しており、高速DCT算法はクレーンショー・カーチス数値積分則のような、任意の関数についてのチェビシェフ近似に用いられる。

4. 非形式的概説
---------

フーリエ変換やそれに類似の変換のように、離散コサイン変換  も関数あるいは信号を異なる周波数と振幅をもつ三角関数の和として表現する。また、DCTは、離散フーリエ変換  と同じく、離散的なデータ点からなる有限の関数に対して施される。一見してそれとわかるDCTとDFTとの違いはDCTがコサイン関数のみを使うのに対してDFTがコサインとサイン関数の両方を使うという点である。しかし、この見かけの違いはもっと本質的な違いの帰結でしかない。すなわち、DCTとDFTあるいは他の関連する変換は境界条件において異なっているということである。

有限の定義域をもつ関数に施される類フーリエ変換、すなわちDFTやDCTやフーリエ級数は、暗黙のうちにその定義域の外部に関数を「拡張」して定義しているのだと考えることができる。つまり、ある関数 //f// を一旦三角関数の和として表現してしまうと、任意の //x// に対し、それがたとえ元の関数 //f// が定義されていない //x// であったとしても、その //x// におけるその三角関数の和を計算できる。DFTやフーリエ級数では元の関数の周期的な拡張がなされていると考えることができる。DCTでは、コサイン変換と同様に、元の関数を偶関数に拡張することを意味する。

しかしながら、DCTは「有限」で「離散的」な数列に対して施されるものであるから、連続なコサイン変換にはない2つの微妙な問題が引き起こされる。まず、有限の点で定義された関数は定義域に左端と右端とをもつので、その//両方//それぞれで偶対称であるか奇対称であるかを指定しなければならない。次に、関数の定義域は離散的であるので、//どの位置//に関して関数が偶/奇対称であるのかを指定しなければならない。例えば、//abcd// という均等に離れた4つの点の列を考えてみよう。そして例えば、//左//の境界で偶対称であると指定したとしよう。このときどの位置で対称なのかという微妙な相違が生ずる。すなわち、データは点 //a// に関して偶対称であって偶関数への拡張は //dcbabcd// なのだろうか、それともデータは //a// とその前の点との//中間//点に関して偶対称であって拡張は //dcbaabcd// であるのか？

これら2重の選択が、DCTと離散サイン変換  との標準的なさまざまな変種すべてを生じさせることになる。各々の境界は偶対称であるか奇対称であるかどちらかであることができ、さらに、各々の境界であるデータ点に関して対称か、2つのデータ点の中間点に関して対称かどちらかであることができる。結局、2 × 2 × 2 × 2 = 16 種類の選択肢がある。これらの選択肢のうち//左//の境界が偶対称であるものがDCTとよばれ、選択肢の半分の8つのタイプに対応する。残りの半分がDSTの8つのタイプとなる。

これらは境界条件が異なるだけで施される変換はすべて離散フーリエ変換であるが、これらの違いは変換を応用する際にその用途に強く影響し、さまざまなDCTの変種に対してそれぞれに有用な特性を与えている。最も直接的には、偏微分方程式をスペクトル法で解くために類フーリエ変換を用いるとき、境界条件は解かせることになる問題の一部として直接指定される。あるいはまた、修正離散コサイン変換  に対しては、境界条件はMDCTの本質的な特性である時間領域のエイリアシングの消去に密接に関係している。もっと微妙なあり方ながら、境界は任意の類フーリエ級数において収束の速さに影響しているので、境界条件は画像や音声圧縮に対してDCTを有用なものとしているいわゆる「エネルギー圧縮」の特性を与える原因となっている。

特に、関数に不連続性があればフーリエ級数の収束率を減少させることはよく知られている。同じ原理は信号圧縮に対して類フーリエ変換の有用性を決定している。よりなめらかな関数はそれをより正確に表すために必要となるDFTやDCTの係数がより少なくてすみ、より圧縮できることになる。しかし、DFTがもつ非明示的な周期性は境界において通常不連続性を作り出すことを意味する。任意に選んだ信号の断片において左と右の境界の値が共に同じ値を持つということはめったに起こることではない。対照的に、「両方」の境界が「常に」偶対称であるDCTはこれらの境界において連続した拡張を与える。これがなぜDCTが、とりわけDCTのタイプ I, II, V, VI が一般にDFTよりも信号圧縮でよい成績を収めるのかという理由である。応用上は、こうした用途には一部には計算の容易さからDCT-IIが最も好まれている。

5. 形式的定義
--------

形式的には、1次元のDCT //F//: R//N// → R//N// は、ある可逆な線形写像、または同じことであるが、ある正則な //N// × //N// 正方行列であって、以下に示された式で表される。ただし、これらの式では、//N// 個の実数列 //x//0, ..., //x////N//−1 が //N// 個の実数列 //X//0, ..., //X////N//−1 に変換される。

5.1. DCT-I
----------

フーリエ変換や他の類似の変換と同じように式全体にかかる定数係数にはばらつきがあり、文献やライブラリによっては、DFTとの対応からこの式を 2 倍したものや、逆変換との対称性から {2/}1/2 倍したものによって定義している場合もあるので注意を要する。また、//x//0 と //x////N//−1 の項を 21/2 倍し、対応して //X//0 と //X////N//−1 を 2−1/2 倍していることもある。後者の変更によって、ある定数倍を除いて変換は直交変換となるが、このときには実偶関数に対するDFTとは直接の関連を失うことになる。

DCT-Iでは、境界条件から 2 周期に拡張された関数を考えていることに対応するので、//N// ≥ 2 でないと定義できないことに注意されたい。他のタイプのDCTはすべて、//N// ≥ 1 であればよい。なお、//N// = 2 のときは上式の総和の項は消え、//X//0 = 1/2 , //X//1 = 1/2  となる。

DCT-Iは、2 個の実数をもつ偶対称関数のDFTとまったく同じものである。たとえば、DCT-Iで //N// = 5 とし、5個の実数を abcde とすると、これは8個の実数 abcdedcbに対するDFTを 2 で割ったものになる。

DCT-Iは次の境界条件の場合に対応している:

//x////n// が //n// = 0 に関して偶対称、//n// = //N// − 1 に関して偶対称。
//X////k// についても同様。

5.2. DCT-II
-----------

DCT-IIは信号の圧縮分野などの応用では最も広く用いられている方法で、単にDCT  と呼ばれることもある。DCT-Iと同様の理由により、これを2倍したものや、1/2 倍したものとして定められている場合もあり、また直交化のために //X//0 の項のみ 2−1/2 倍されている場合もある。最後の場合DFTとの直接の対応は失われる。

このタイプは境界の両側に要素の間隔の半分のシフトを含んだ偶対称への拡張を考える。例えば //N// = 5 のときの実数列を //abcde// とすれば、2//N// = 10 個の実数列 //abcdeedcba// となる。両端の要素 //a//, //e// が繰り返される点がDCT-Iとは異なっている。ただし半分のシフトを行っているため、DFTとの対応を考える場合にはさらに倍にして偶数の添字の要素を 0 とした 4//N// 個の実数列をとる。すなわち、4//N// 個の実数列 //y//0, ..., //y//4//N//−1 を、

//y//2//n// = 0       ,
//y//2//n//+1 = //y//4//N//−2//n//−1 = //x////n//       を満たすものとすると、DCT-IIはこの実数列 //y////n// をDFTで変換し 2 で割ったものと一致する。

DCT-IIは次の境界条件に対応する:

//x////n// が //n// = −1/2 に関して偶対称、//n// = //N// − 1/2 に関して偶対称。
//X////k// が //k// = 0 に関して偶対称、//k// = //N// に関して奇対称。

5.3. DCT-III
------------

DCT-IIIはDCT-IIの逆変換である。そのため、単に「逆DCT」 と呼ばれることがある。

//x//0 の項を 倍することもある。そうすると、DCT-IIとDCT-IIIとは互いに転置になる。DCT-IIIの行列は直交になるが、DFTとの直接の対応関係は失われる。

DCT-IIIは次の境界条件にあたる:

//x////n// が //n// = 0 で偶対称かつ //n// = //N// で奇対称。
//X////k// が //k// = −1/2 で偶対称かつ //k// = //N// − 1/2 で偶対称。

5.4. DCT-IV
-----------

DCT-IVの行列は直交である。

DCT-IVの変種のひとつで、各変換のデータが「重なり合っている」変形を、修正離散コサイン変換  と呼ぶ。

DCT-IVは次の境界条件に対応する:

//x////n// が //n// = −1/2 で偶対称、//n// = //N// − 1/2 で奇対称。
//X////k// についても同様。

5.5. DCT-V – VIII
-----------------

DCTタイプ I – IV は、実偶関数への偶数次DFTと等価である。原理的には、実際にはさらに、実偶関数への奇数次DFTに対応する4タイプのDCTタイプ V – VIII が存在する 。タイプ V – VIII は、cos 関数の引数の分母に //N// + 1/2 の係数がある。ただし、タイプ V – VIII は実際にはほとんど使われない。

6. 逆変換
------

DCT-Iの逆変換は、DCT-Iの 2/ 倍である。DCT-IVの逆変換は、DCT-IVの 2///N// 倍である。DCT-IIの逆変換はDCT-IIIの 2///N// 倍で、DCT-IIIの逆変換はDCT-IIの 2///N// 倍である。

DFT同様、これらの変換公式の最前部にある標準化係数は便宜的なもので、扱いによって異なる。たとえば変換式を 倍する著者もおり、その場合何も乗算しなくても逆変換になる。

7. 計算法
------

上記の公式を直接使うと、計算量は O となるが、高速フーリエ変換  と同様の技法を使って、計算量を O に減らせる。また、計算量 O の事前処理と事後処理を加えることで、FFTそのものを使ってもDCTを計算できる。

当然ながら、ふつうは、最も効率がいいのはDCT専用のアルゴリズムであり、FFTはそれに及ばない。とはいうものの、DCTに特化したアルゴリズムは通常、FFTのアルゴリズムと密接に関連している。というのも、DCTは本質的には偶である実数データに対するDFTであるから、高速DCTのアルゴリズムの設計には、FFTを元にして、データの対称性に基づき冗長な計算を減らすことができる。この設計は自動化もできる 。クーリー・テューキーのアルゴリズムに基づくものが最も一般的だが、FFTのアルゴリズムならこれに限らず何でも用いることができる。たとえば、ウィノグラードのアルゴリズム  を用いると、加算の回数が増える代わりに乗算の回数を最小化することができ、一般的には効率があがる。同様なアルゴリズムは Feig & Winograd  によってもDCT向きに提唱されている。DFT、DCT、および類似の変換法のアルゴリズムは互いに密接に関連しているため、どれかの変換法で改善が行われると、理論的には他の変換法にも即座に応用することができる 。

理論的には、FFTそのものを変更なしで用いた場合、DCT専用のアルゴリズムに比べいくらかのオーバーヘッドを伴うことになるが、この方法には明瞭な利点がある。高度に最適化されたFFTプログラムが広く出回っていることである。かくして実際には、一般的な //N// 長のデータを扱う場合、FFTを元にしたアルゴリズムの方が容易に性能を出せることが多い。一方、DCT専用アルゴリズムは、少量かつ固定長のデータ向けや、音声圧縮用途の小規模なDCT向けに広く用いられている。このような組み込みシステム用には、プログラムコードが短くて済むことも重要だからである。

実際のところ、通常のFFTを用いたDCTアルゴリズムといっても、それはしばしば、実数の偶関数データに対するより大規模なFFTから冗長な処理をそぎ落としたものと等価であり、計算量から見ても最適でありうる。たとえば、DCT-IIは 4//N// の偶対称な実数データに対するDFTと等価である。FFTを用いた一般的な計算法の一つは Makhoul  による。この手法は、実で偶なDFTにおける radix-4 時間間引きFFTの1ステップと見ることもできる。偶数の添字を持つ要素が 0 であるから、radix-4 ステップは split-radix ステップと正確に同じものである。続いて //N// 個の実数データに対するFFTを実データ split-radix FFTを用いて行えば、最終的な算法全体は、すでに述べた 2 の冪乗データに対するDCT-IIアルゴリズムのうち、最も計算量が少ないものに匹敵する。したがって、計算量の点ではDCTをFFTで計算することが本質的に悪であるというわけではなく、単に使おうとしているFFTアルゴリズムの最適化の問題であることがある。アルゴリズムではなく実装上の問題であるが、データ量 //N// が小さい場合は、独立したFFTルーチンを呼び出すための関数呼び出しに伴うオーバーヘッドの方が問題になりうるほどである。

8. 注釈
-----

9. 参考文献
-------

K.R. Rao and P. Yip, //Discrete Cosine Transform: Algorithms, Advantages, Applications//, 1990, Academic Press:Boston; K.R. Rao, P. Yip, and V. Britanak, 2006, 2 sub ed., ISBN 0-12-580251-X; 安田浩, 藤原洋訳 『画像符号化技術 — DCTとその国際標準』, 1992, オーム社, ISBN 4-274-03401-1
A. V. Oppenheim, R. W. Schafer, and J. R. Buck, //Discrete-Time Signal Processing//, second edition .
S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," //IEEE Trans. Sig. Processing// SP-42, 1038–1051 .
Matteo Frigo and Steven G. Johnson: //FFTW//, http://www.fftw.org/. フリーの C ライブラリで、任意の大きさの 1 次元と多次元の DCTを高速に計算できる。 M. Frigo and S. G. Johnson, "[1]," //Proceedings of the IEEE// 93 , 216–231  も参照。
E. Feig, S. Winograd. "Fast algorithms for the discrete cosine transform," //IEEE Transactions on Signal Processing// 40 , 2174–2193 .
P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," //Signal Processing// 19, 259–299 .
John Makhoul, "A fast cosine transform in one and two dimensions," //IEEE Trans. Acoust. Speech Sig. Proc.// 28 , 27–34 .
H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, "Real-valued fast Fourier transform algorithms," //IEEE Trans. Acoust. Speech Sig. Processing// ASSP-35, 849–863 .
Y. Arai, T. Agui, and M. Nakajima, "A fast DCT-SQ scheme for images," //Trans. IEICE// 71 , 1095–1097 .

10. 関連項目
--------

修正離散コサイン変換 
[2]
[3]