離散コサイン変換

出典: フリー百科事典『ウィキペディア（Wikipedia）』

二次元 DCT と DFT との比較。左はスペクトル、右はヒストグラム。低周波域での相違を示すため、スペクトルは 1/4 だけ示してある。DCT では、パワーのほとんどが低周波領域に集中していることがわかる。

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

[編集] 概要

DCT は離散フーリエ変換の特殊なものであり、実数からなる信号から実数からなる係数への変換を行う。 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）成分とし、行・列とも、添字が大きくなるほど垂直ないし水平方向の空間周波数が高い成分を表す。

2次元DCTとDFTとの比較。

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

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

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

[編集] 数式による定義

公式的には、DCT は線形で可逆な関数

$F\colon \mathbb{R}^N \rightarrow \mathbb{R}^N$

（ $\mathbb{R}$ は実数の集合）であり、N × N 正方行列に等価である。DCT には、すこしずつ定義の違ったいくつかの変種がある。以下の公式のどれか1つを使って、N 個の実数列 x₀, ..., x_N−1 を N 個の実数列 $X_0, \ldots, X_{N - 1}$ に変換する。

[編集] DCT-I

$X_k = \frac{1}{2} \{x_0 + (-1)^k x_{N-1}\} + \sum_{n=1}^{N-2} x_n \cos\!\left\{\frac{\pi}{N-1} n k \right\}$

著者によっては、x₀ と x_N−1 の項をさらに $\sqrt{2}$ 倍し、X₀ と X_N−1 を $1 / \sqrt{2}$ 倍することもある。こうすると、1つのスケールファクタについて DCT-I の行列が直交することになるが、偶関数に対する実領域の DFT とは直接の関連を失うことになる。

DCT-I は全体のスケールファクタが2までの場合、2N − 2 個の実数をもつ偶対称関数の DFT とまったく同じものである。たとえば、DCT-I で N = 5 とし、5個の実数を abcde とすると、これは8個の実数 abcdedcb （偶対称）に対する DFT を2で割ったものになる。

DCT-I は、N ≥ 2 でないと定義できないことに注意されたい。他の DCT はすべて、N ≥ 1 であればよい。

かように、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 と呼ばれることもある。

この方法は全体のスケールファクタが2までの場合、入力される実数の数が 4N 個であり、偶対称で、かつ偶数番目の要素が 0 である場合の DFT とまったく同じものである。すなわち、4N 個の入力を y_n とし、

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

を満たすものとすると、入力 y_n の DFT の 1/2 になる。

DCT-I の場合のように、X₀ の項を $1 / \sqrt{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」(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 の行列は（1つのスケールファクタに関する限り）直交である。

各変換のデータが「重なり合ってる」変形を、修正離散コサイン変換 (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}$ 倍する著者もおり、その場合何も乗算しなくても逆変換になる。

[編集] 計算法

上記の公式を直接使うと、計算量は 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 (Academic Press, Boston, 1990).
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/. A free (GPL) C library that can compute fast DCTs (types I-IV) in one or more dimensions, of arbitrary size. Also 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).

[編集] 関連項目

この項目「離散コサイン変換」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。

"http://ja.wikipedia.org../../../%E9%9B%A2/%E6%95%A3/%E3%82%B3/%E9%9B%A2%E6%95%A3%E3%82%B3%E3%82%B5%E3%82%A4%E3%83%B3%E5%A4%89%E6%8F%9B.html" より作成

カテゴリ: 数学関連のスタブ項目 | 信号処理 | フーリエ解析