離散コサイン変換
[Wikipedia|▼Menu]
DCT-Iと同様の理由により、これを2倍したものや、(2/N)1/2 倍したものとして定められている場合もあり、また直交化のために X0 の項のみ 2?1/2 倍されている場合もある。最後の場合DFTとの直接の対応は失われる。

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

y2n = 0   (0 ? n < 2N である n について),

y2n+1 = y4N?2n?1 = xn   (0 ? n < N である n について)

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

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

xn が n = ?1/2 に関して偶対称、n = N ? 1/2 に関して偶対称。

Xk が k = 0 に関して偶対称、k = N に関して奇対称。

DCT-III X k = 1 2 x 0 + ∑ n = 1 N − 1 x n cos { π N n ( k + 1 2 ) } {\displaystyle 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) と呼ばれることがある。

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

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

xn が n = 0 で偶対称かつ n = N で奇対称。

Xk が k = ?1/2 で偶対称かつ k = N ? 1/2 で偶対称。

DCT-IV X k = ∑ n = 0 N − 1 x n cos { π N ( n + 1 2 ) ( k + 1 2 ) } {\displaystyle 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は次の境界条件に対応する:

xn が n = ?1/2 で偶対称、n = N ? 1/2 で奇対称。

Xk についても同様。

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

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

当然ながら、ふつうは、最も効率がいいのはDCT専用のアルゴリズムであり、FFTはそれに及ばない(例外については後述する)。とはいうものの、DCTに特化したアルゴリズム(少なくとも2の冪乗個のデータに関しては、現在知られている中で最も計算量の少ないものを含め)は通常、FFTのアルゴリズムと密接に関連している。というのも、DCTは本質的には偶である実数データに対するDFTであるから、高速DCTのアルゴリズムの設計には、FFTを元にして、データの対称性に基づき冗長な計算を減らすことができる。この設計は自動化もできる (Frigo & Johnson, 2005)。クーリー・テューキーのアルゴリズム(英語版)に基づくものが最も一般的だが、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を用いた一般的な計算法(たとえばFFTPACKFFTWに用いられている)の一つは 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 log2N ? N + 2 のオーダーである[1])。したがって、計算量の点ではDCTをFFTで計算することが本質的に悪であるというわけではなく、単に使おうとしているFFTアルゴリズムの最適化の問題であることがある。


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:34 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef