離散コサイン変換

離散コサイン変換（りさんコサインへんかん）は、離散信号を周波数領域へ変換する方法の一つであり、信号圧縮に広く用いられている。英語の Discrete Cosine Transform の頭文字から DCT と呼ばれる。以下 DCT と略す。

概要

DCT は、有限数列を、余弦関数数列 cos (nk) を基底とする一次結合（つまり、適切な周波数と振幅のコサインカーブの和）の係数に変換する。余弦関数は実数に対しては実数を返すので、実数列に対してはDCT係数も実数列となる。

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

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

逆変換を逆離散コサイン変換（英:Inverse Discrete Cosine Transform(IDCT)）と呼ぶ。

種類

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

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

応用

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

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

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

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

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

非形式的概説

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

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

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

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

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

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

形式的定義

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

DCT-I

X_{k}={\frac {1}{2}}x_{0}+\sum _{n=1}^{N-2}x_{n}\cos \!\left({\frac {\pi }{N-1}}nk\right)+{\frac {(-1)^{k}}{2}}x_{N-1}

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

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

DCT-I は (全体が 2 倍になる違いを除いて)、2 (N − 1) 個の実数をもつ偶対称関数の DFT とまったく同じものである。たとえば、DCT-I で N = 5 とし、5個の実数を abcde とすると、これは8個の実数 abcdedcb （偶対称）に対する DFT を2で割ったものになる。

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

x_n が n = 0 に関して偶対称、n = N − 1 に関して偶対称。
X_k についても同様。

DCT-II

X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \!\left\{{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)k\right\}

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

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

y_2n = 0 (0 ≤ n < 2N である n について),
y_2n+1 = y_4N−2n−1 = x_n (0 ≤ n < N である n について)

を満たすものとすると、DCT-II はこの実数列 y_n を DFT で変換し 2 で割ったものと一致する。

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

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

DCT-III

X_{k}={\frac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}\cos \!\left\{{\frac {\pi }{N}}n\left(k+{\frac {1}{2}}\right)\right\}

DCT-III は (ある定数倍を無視すれば) DCT-II の逆変換である。そのため、単に「逆DCT」(the inverse DCT, IDCT) と呼ばれることがある。

x₀ の項を ${\sqrt {2}}$ 倍することもある（対応する変形は上記 DCT-II 参照）。そうすると、DCT-II と DCT-III とは互いに転置になる。DCT-III の行列は直交になるが、DFT との直接の対応関係は失われる。

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

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

DCT-IV

X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \!\left\{{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)\left(k+{\frac {1}{2}}\right)\right\}

DCT-IV の行列は（定数倍を無視すれば）直交である。

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

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

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

DCT-V – VIII

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

（自明な実偶配列である、1つの数 a への長さ 1 （奇数）の DFT は、N = 1 の DCT-V である）

逆変換

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

DFT 同様、これらの変換公式の最前部にある標準化係数は便宜的なもので、扱いによって異なる。たとえば変換式を ${\sqrt {2/N}}$ 倍 (DCT-I では {2/(N − 1)}^1/2 倍) する著者もおり、その場合何も乗算しなくても逆変換になる。

計算法

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

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

理論的には、FFT そのものを変更なしで用いた場合、DCT 専用のアルゴリズムに比べいくらかのオーバーヘッドを伴うことになるが、この方法には明瞭な利点がある。高度に最適化された FFT プログラムが広く出回っていることである。かくして実際には、一般的な N 長のデータを扱う場合、FFT を元にしたアルゴリズムの方が容易に性能を出せることが多い（現代の主なハードウェアの速度は、単純な計算量で決まるようなものではなく、プログラムの最適化によって、それに応じたハードウェアの改良も行われる）。一方、DCT 専用アルゴリズムは、少量かつ固定長のデータ（たとえば、JPEG で用いられる 8 × 8 の DCT-II）向けや、音声圧縮用途の小規模な DCT（ないし MDCT）向けに広く用いられている。このような組み込みシステム用には、プログラムコードが短くて済むことも重要だからである。

実際のところ、通常の FFT を用いた DCT アルゴリズムといっても、それはしばしば、実数の偶関数データに対するより大規模な FFT から冗長な処理をそぎ落としたものと等価であり、計算量から見ても最適でありうる。たとえば、DCT-II は 4N の偶対称な実数データ（偶数番目の要素が 0）に対する DFT と等価である。FFT を用いた一般的な計算法（たとえばFFTPACKやFFTWに用いられている）の一つは Makhoul (1980) による。この手法は、実で偶な DFT（DCT-II に対応する）における radix-4 時間間引き FFT の1ステップと見ることもできる（基数を 4 にする radix-4 ステップによって 4N 個のデータに対する DFT が4つの DFT に分解されることになり、それぞれの DFT は N 個の実数データに対するものとなる。4つの DFT のうち2つは 0 で、データが偶対称であることから、残りの2つは互いに等しくなる。かくして N 個の実数データに対する FFT 1回と、O(N) のバタフライ演算で計算できることとなる）。偶数の添字を持つ要素が 0 であるから、radix-4 ステップは split-radix ステップと正確に同じものである。続いて N 個の実数データに対する FFT を実データ split-radix FFT（Sorensen et al., 1987等）を用いて行えば、最終的な算法全体は、すでに述べた 2 の冪乗データに対する DCT-II アルゴリズムのうち、最も計算量が少ないものに匹敵する（実数演算の回数が 2N log₂N − N + 2 のオーダーである^[1]）。したがって、計算量の点では DCT を FFT で計算することが本質的に悪であるというわけではなく、単に使おうとしている FFT アルゴリズムの最適化の問題であることがある。アルゴリズムではなく実装上の問題であるが、データ量 N が小さい場合は、独立した FFT ルーチンを呼び出すための関数呼び出しに伴うオーバーヘッドの方が問題になりうるほどである。

Notes

^ 。正確には、実数演算の回数、特に実数乗算の回数は、変換式のスケーリングに幾分依存する。計算量 2N log₂N − N + 2 は DCT-II について前述の定義を用いた場合で、式全体が ${\sqrt {2}}$ でスケーリングされていれば、乗算を2回節約できる。出力を個別にスケーリングすることが許されるなら、さらに乗算を減らせる。size-8 である JPEG に関する結果を参照されたい (Arai et al. , 1988)

参考文献

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 (Prentice-Hall, New Jersey, 1999).
S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," IEEE Trans. Sig. Processing SP-42, 1038–1051 (1994).
Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/. フリー (GPL ライセンス) の C ライブラリで、任意の大きさの 1 次元と多次元の DCT (タイプ I–IV) を高速に計算できる。 M. Frigo and S. G. Johnson, "The Design and Implementation of FFTW3," Proceedings of the IEEE 93 (2), 216–231 (2005) も参照。
E. Feig, S. Winograd. "Fast algorithms for the discrete cosine transform," IEEE Transactions on Signal Processing 40 (9), 2174–2193 (1992).
P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," Signal Processing 19, 259–299 (1990).
John Makhoul, "A fast cosine transform in one and two dimensions," IEEE Trans. Acoust. Speech Sig. Proc. 28 (1), 27–34 (1980).
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 (1987).
Y. Arai, T. Agui, and M. Nakajima, "A fast DCT-SQ scheme for images," Trans. IEICE 71 (11), 1095–1097 (1988).

概要

種類

応用