離散コサイン変換

離散コサイン変換( DCT ) は、有限のデータ ポイントのシーケンスを、異なる周波数で振動するコサイン関数の和として表現します。 DCT は、 1972 年にNasir Ahmedによって初めて提案され、信号処理とデータ圧縮で広く使用されている変換手法です。デジタル画像( JPEGやHEIFなど)、デジタル ビデオ( MPEGやH.26xなど)、デジタルオーディオ( Dolby Digital、MP3、AACなど)、デジタル テレビ( SDTV、HDTV、VODなど) 、デジタルラジオ ( AAC+やDAB+など)、音声符号化( AAC-LD、Siren、Opusなど) を含むほとんどのデジタル メディアで使用されています。 DCT は、デジタル信号処理、電気通信デバイス、ネットワーク帯域幅の使用量削減、偏微分方程式の数値解法に対するスペクトル法など、科学や工学における他の多くのアプリケーションでも重要です。

DCT は離散フーリエ変換(DFT)に似たフーリエ関連変換ですが、実数のみを使用します。DCT は一般に、周期的かつ対称的に拡張されたシーケンスのフーリエ級数係数に関連していますが、DFT は周期的に拡張されたシーケンスのみのフーリエ級数係数に関連しています。DCT は長さが約 2 倍の DFT に相当し、対称性が偶数である実データに対して動作します(実数で偶数関数のフーリエ変換は実数で偶数であるため)。一方、一部のバリアントでは、入力データまたは出力データがサンプルの半分だけシフトされます。

標準的な DCT バリアントは 8 つあり、そのうち 4 つが一般的です。離散コサイン変換の最も一般的なバリアントはタイプ II DCT で、単にDCTと呼ばれることがよくあります。これは、Ahmed によって最初に提案された元の DCT でした。その逆であるタイプ III DCT は、単に逆 DCTまたはIDCTと呼ばれることがよくあります。関連する 2 つの変換は、実関数と奇関数の DFT に相当する離散サイン変換(DST)と、重複データの DCT に基づく修正離散コサイン変換 (MDCT) です。多次元 DCT (MD DCT) は、DCT の概念を多次元信号に拡張するために開発されました。DCT の実装の計算の複雑さを軽減するために、さまざまな高速アルゴリズムが開発されています。その1つが整数DCT（IntDCT）^[1]であり、標準DCT ^{[2] ：ix、xiii、1、141–304}の整数近似であり、いくつかのISO / IECおよびITU-T国際標準で使用されています。^{[1] [2]}

DCT圧縮はブロック圧縮とも呼ばれ、離散的なDCTブロックのセットでデータを圧縮します。^[3] DCTブロックのサイズには、標準DCTの8x8ピクセルと、4x4から32x32ピクセルまでのさまざまな整数DCTサイズが含まれます。^{[1] [4]} DCTは強力なエネルギー圧縮特性を持ち、^{[5] [6]高い}データ圧縮率で高品質を実現できます。^{[7] [8]}ただし、重いDCT圧縮を適用すると、ブロック状の圧縮アーティファクトが発生する可能性があります。

DCT は、カンザス州立大学に勤務していたNasir Ahmed、 T. Natarajan 、KR Raoによって初めて考案されました。この概念は1972 年に国立科学財団に提案されました。DCTはもともと画像圧縮を目的としていました。^{[9] [1]} Ahmed は、 1973 年にテキサス大学アーリントン校で、博士課程の学生である T. Raj Natarajan、Wills Dietrich、Jeremy Fries、友人のKR Rao博士とともに実用的な DCT アルゴリズムを開発しました。 ^{[9]彼らはその結果を 1974 年 1 月に「}離散コサイン変換」と題する論文で発表しました。^{[5] [6] [10]}この論文では、現在ではタイプ II DCT (DCT-II) ^{[2] : 51}と呼ばれているものや、タイプ III 逆 DCT (IDCT) について説明しました。^[5]

1974年に導入されて以来、DCTに関する研究は盛んに行われてきました。^[10] 1977年、ウェン・シウン・チェンはC.ハリソン・スミス、スタンレー・C.フラリックとともに、高速DCTアルゴリズムを発表した論文を発表しました。^{[11] [10]}さらに発展した論文としては、1978年のMJナラシマとAMピーターソンの論文、1984年のBGリーの論文があります。^{[10]これらの研究論文は、1974年のオリジナルのアーメドの論文と1977年のチェンの論文とともに、1992年に}JPEGの非可逆画像圧縮アルゴリズムの基礎としてJoint Photographic Experts Groupによって引用されました。^{[10] [12]}

離散正弦変換（DST）は、DCTからx=0におけるノイマン条件をディリクレ条件に置き換えることで導き出されました。^{[2] : 35-36} DSTは、1974年のDCT論文でAhmed、Natarajan、Raoによって説明されました。^[5]タイプI DST（DST-I）は、1976年にAnil K. Jainによって説明され、タイプII DST（DST-II）は、1978年にHB KekraとJK Solankaによって説明されました。^[13]

1975年、John A. RoeseとGuner S. Robinsonは、フレーム間 動き補償 ビデオコーディングにDCTを採用しました。彼らはDCTと高速フーリエ変換（FFT）を試し、両方に対応したフレーム間ハイブリッドコーダを開発し、複雑さが少ないためDCTが最も効率的であることを発見しました。DCTは、ビデオ電話のシーンでは、1ピクセルあたり0.25ビットまで画像データを圧縮でき、画質は1ピクセルあたり2ビットを必要とするフレーム内コーダに匹敵します。 ^{[14] [15]} 1979年、Anil K. JainとJaswant R. Jainは、ブロック動き補償とも呼ばれる動き補償DCTビデオ圧縮をさらに開発しました^{[16] [17]}。^[17]これにより、チェンは1981年に動き補償DCTまたは適応シーンコーディングと呼ばれる実用的なビデオ圧縮アルゴリズムを開発しました。 ^[17]動き補償DCTは、1980年代後半以降、ビデオ圧縮の標準的なコーディング技術となりました。^{[18] [19]}

DCTの変種である修正離散コサイン変換（MDCT）は、1986年のプリンスンとブラッドリーによる研究に続き、1987年にサリー大学のジョン・P・プリンスン、AW・ジョンソン、アラン・B・ブラッドリーによって開発されました。 ^[20] MDCTは、ドルビーデジタル（AC-3）、^{[22] [ 23]} MP3（ハイブリッドDCT - FFTアルゴリズムを使用）、^[24]アドバンストオーディオコーディング（AAC）、^[25]およびVorbis（Ogg）など、ほとんどの最新のオーディオ圧縮形式で使用されています。^[26]

ナシル・アハメドは、1995年にニューメキシコ大学でギリダル・マンディヤム、ニーラジ・マゴトラとともにロスレスDCTアルゴリズムも開発しました。これにより、DCT技術を画像のロスレス圧縮に使用できるようになりました。これは元のDCTアルゴリズムの修正版であり、逆DCTとデルタ変調の要素が組み込まれています。これはエントロピー符号化よりも効果的なロスレス圧縮アルゴリズムです。^[27]ロスレスDCTはLDCTとも呼ばれます。^[28]

DCTは信号処理で最も広く使用されている変換技術であり、^[29]データ圧縮では圧倒的に最も広く使用されている線形変換です。^[30]非圧縮デジタルメディアと可逆圧縮では、メモリと帯域幅の要件が高くなりますが、DCT非可逆圧縮技術によって大幅に削減されます。^{[7] [8]}スタジオ品質に近い場合は8:1から14:1、^[7]許容品質のコンテンツの場合は最大100:1のデータ圧縮率を達成できます。 ^[8] DCT圧縮規格は、デジタル画像、デジタル写真、^{[31] [32]}デジタルビデオ、^{[18] [33]}ストリーミングメディア、^[34]デジタルテレビ、ストリーミングテレビ、ビデオオンデマンド（VOD）、^[8]デジタルシネマ、^[22]高精細ビデオ（HDビデオ）、高精細テレビ（HDTV）などのデジタルメディア技術で使用されています。^{[7] [35]}

DCT、特にDCT-IIは、強力なエネルギー圧縮特性を持つため、信号処理や画像処理、特に非可逆圧縮によく使用されます。^{[5] [6]}一般的なアプリケーションでは、信号情報のほとんどはDCTのいくつかの低周波成分に集中する傾向があります。相関の強いマルコフ過程の場合、DCTはカルーネン・レーブ変換の圧縮効率に近づくことができます（これは非相関の意味で最適です）。以下で説明するように、これはコサイン関数に暗黙的に含まれる境界条件に起因します。

DCT は、スペクトル法による偏微分方程式の解法に広く採用されており、DCT のさまざまなバリエーションは、配列の両端のわずかに異なる偶数境界条件と奇数境界条件に対応します。

DCT はチェビシェフ多項式と密接な関係があり、高速 DCT アルゴリズム (下記) は、たとえばクレンショウ・カーティス積分法など、チェビシェフ多項式の級数による任意関数のチェビシェフ近似に使用されます。

DCT は、次のような多くのアプリケーションで広く使用されています。

DCT-II は重要な画像圧縮技術です。JPEGなどの画像圧縮規格や、H.26x、MJPEG、MPEG、DV、Theora、Daalaなどのビデオ圧縮規格で使用されています。そこでは、ブロックの 2 次元 DCT-IIが計算され、結果が量子化されてエントロピー符号化されます。この場合、は通常 8 で、 DCT-II 式はブロックの各行と列に適用されます。結果は 8 × 8 の変換係数配列で、その要素 (左上) は DC (ゼロ周波数) 成分で、垂直および水平インデックス値が増加するエントリは、より高い垂直および水平空間周波数を表します。 ${\displaystyle N\times N}$${\displaystyle N}$${\displaystyle (0,0)}$

整数DCTはDCTの整数近似であり、^{[2] [1]} 2003年に導入されたAdvanced Video Coding (AVC) ^{[52] [1]}と2013年に導入されたHigh Efficiency Video Coding (HEVC) ^{[4] [1]}で使用されています。整数DCTは、静止画像のコーディングにHEVCビデオコーディング形式のサブセットを使用するHigh Efficiency Image Format (HEIF) でも使用されています。 ^[4] AVCは4 x 4と8 x 8のブロックを使用します。HEVCとHEIFは、4 x 4から32 x 32ピクセルまでのさまざまなブロックサイズを使用します。^{[4] [1]} 2019年現在、AVCはビデオコンテンツの記録、圧縮、配信に最も一般的に使用されている形式であり、ビデオ開発者の91%が使用しています。次に多いのはHEVCで、開発者の43%が使用しています。^{[43][アップデート]}

多次元DCT（MD DCT）には、主に3D DCTなどのアプリケーションがあり、ハイパースペクトル画像符号化システム、^[85]可変時間長3D DCT符号化、^[86] ビデオ符号化アルゴリズム、^[87]適応型ビデオ符号化^[88]および3D圧縮^[89]などのいくつかの新しいアプリケーションがあります。ハードウェア、ソフトウェアの機能強化、およびいくつかの高速アルゴリズムの導入により、MD DCTを使用する必要性が急速に高まっています。DCT-IVは、実数値多相フィルタリングバンク、^[90]ラップ直交変換^{[91] [92]}およびコサイン変調ウェーブレット基底の高速実装でのアプリケーションで人気を博しています。^[93]

DCTはデジタル信号処理、特にデータ圧縮において重要な役割を果たします。DCTはデジタル信号プロセッサ（DSP）やデジタル信号処理ソフトウェアに広く実装されています。多くの企業がDCT技術に基づいたDSPを開発しています。DCTは、エンコード、デコード、ビデオ、オーディオ、多重化、制御信号、シグナリング、アナログからデジタルへの変換などのアプリケーションに広く使用されています。DCTは、高精細テレビ（HDTV）エンコーダ/デコーダチップにも一般的に使用されています。^[1]

デジタルメディアにおけるDCT圧縮の一般的な問題は、DCTブロックによって引き起こされるブロック状の圧縮アーティファクト^[94]です。 ^[3] DCTアルゴリズムでは、画像（または画像シーケンス内のフレーム）が互いに独立して処理される正方形のブロックに分割され、各ブロック内でDCTブロックが取得され、結果として得られるDCT係数が量子化されます。このプロセスにより、主にデータ圧縮率が高い場合にブロック状のアーティファクトが発生する可能性があります。^{[94]これにより、}デジタルビデオでよく見られるモスキートノイズ効果も発生する可能性があります。^[95]

DCTブロックはグリッチアートでよく使われます。^[3]アーティストのローザ・メンクマンは、 DCTベースの圧縮アーティファクトをグリッチアートに使用しています。^{[96]特に、} JPEGデジタル画像やMP3オーディオなどのほとんどのデジタルメディア形式で見られるDCTブロックです。^[3]もう1つの例は、ドイツの写真家トーマス・ルフによるJpegsで、意図的なJPEGアーティファクトを写真のスタイルの基礎として使用しています。^{[97] [98]}

フーリエ変換と同様に、DCT は関数または信号を、異なる周波数と振幅を持つ正弦波の合計として表現します。DFT と同様に、DCT は有限数の離散データ ポイントで関数を操作します。DCT と DFT の明らかな違いは、前者はコサイン関数のみを使用するのに対し、後者はコサインとサインの両方 (複素指数の形式) を使用することです。ただし、この目に見える違いは、より深い違いの結果に過ぎません。DCT は、DFT やその他の関連変換とは 異なる境界条件を意味します。

DFT や DCT やフーリエ級数など、有限領域上の関数に作用するフーリエ関連の変換は、その関数の領域外への拡張を暗黙的に定義するものと考えることができます。つまり、関数を正弦波の和として記述すると、元の関数が指定されていない場合でも、任意の でその和を評価できます。DFT は、フーリエ級数と同様に、元の関数の周期的な拡張を意味します。DCT は、コサイン変換と同様に、元の関数の 偶数拡張を意味します。${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle x}$${\displaystyle f(x)}$

ただし、DCT は有限の離散シーケンスに対して動作するため、連続コサイン変換には当てはまらない 2 つの問題が生じます。まず、関数がドメインの左境界と右境界の両方で偶数か奇数かを指定する必要があります (つまり、以下の定義ではそれぞれmin- n境界と max- n境界)。次に、関数が偶数か奇数かを指定する必要があります。特に、等間隔に配置された 4 つのデータ ポイントのシーケンスabcd を考え、左境界を偶数に指定したとします。2 つの合理的な可能性があります。データがサンプルa の周りで偶数である場合 (この場合、偶数拡張はdcbabcd )、またはデータがaと前のポイントの中間のポイントの周りで偶数である場合 (この場合、偶数拡張はdcbaabcd ( aが繰り返される))。

各境界は偶数または奇数 (境界ごとに 2 つの選択肢) のいずれかにすることができ、データ ポイントまたは 2 つのデータ ポイントの中間点を中心に対称にすることができ (境界ごとに 2 つの選択肢)、合計 2 × 2 × 2 × 2 = 16 の可能性があります。これらの選択肢により、DCT のすべての標準的なバリエーションと離散正弦変換(DST) が生まれます。これらの可能性の半分、つまり左境界が偶数の場合、8 種類の DCT に対応し、残りの半分は 8 種類の DST に対応します。

これらの異なる境界条件は、変換の適用に大きく影響し、さまざまな DCT タイプに固有の有用な特性をもたらします。最も直接的には、フーリエ関連変換を使用してスペクトル法で偏微分方程式を解く場合、境界条件は解決する問題の一部として直接指定されます。または、MDCT (タイプ IV DCT に基づく) の場合、境界条件は、MDCT の時間領域エイリアシング除去という重要な特性に深く関係しています。より微妙な形では、境界条件は、 DCT を画像や音声の圧縮に役立てるエネルギーのコンパクト化特性に関係しています。境界は、フーリエのような級数の収束率に影響を与えるためです。

特に、関数に不連続性があるとフーリエ級数の収束速度が遅くなり、関数を所定の精度で表すにはより多くの正弦波が必要になることはよく知られています。同じ原理が、信号圧縮における DFT やその他の変換の有用性にも当てはまります。関数が滑らかであればあるほど、関数を正確に表すために必要な DFT または DCT の項が少なくなり、圧縮率も高くなります。(ここでは、関数の「滑らかさ」について述べるために、DFT または DCT をそれぞれ関数のフーリエ級数またはコサイン級数の近似値として考えます。) ただし、DFT の暗黙的な周期性により、通常は境界で不連続性が発生します。信号の任意のランダム セグメントが、左境界と右境界の両方で同じ値を持つことはほとんどありません。 (DST でも同様の問題が発生します。DST では、奇数左境界条件により、その境界でたまたまゼロにならない関数の不連続性が示されます。) 対照的に、両方の境界が偶数である DCT では、境界で常に連続的な拡張が生成されます (ただし、傾きは一般に不連続です)。これが、DCT、特にタイプ I、II、V、および VI の DCT (2 つの偶数境界を持つタイプ) が、信号圧縮において DFT や DST よりも一般的にパフォーマンスが優れている理由です。実際には、計算の利便性などの理由から、このようなアプリケーションではタイプ II の DCT が通常好まれます。

正式には、離散コサイン変換は線形の可逆関数 （ここで、 は実数の集合を表します）、または同等に可逆なN × N正方行列です。 DCT には、定義がわずかに変更されたいくつかのバリエーションがあります。N個の実数は、次のいずれかの式に従って N 個の実数に変換されます。${\displaystyle f:\mathbb {R} ^{N}\to \mathbb {R} ^{N}}$${\displaystyle \mathbb {R} }$ ${\displaystyle ~x_{0},\ \ldots \ x_{N-1}~}$${\displaystyle X_{0},\,\ldots ,\,X_{N-1}}$

${\displaystyle X_{k}={\frac {1}{2}}(x_{0}+(-1)^{k}x_{N-1})+\sum _{n=1}^{N-2}x_{n}\cos \left[\,{\tfrac {\ \pi }{\,N-1\,}}\,n\,k\,\right]\qquad {\text{ }}~k=0,\ \ldots \ N-1~ の場合。}$

著者によっては、さらに、項と項を で乗算し、それに応じて、項と項を で乗算します。これにさらに全体のスケール係数 を乗算すると、DCT-I 行列は直交しますが、実数-偶数DFTとの直接的な対応が失われます。 ${\displaystyle x_{0}}$${\displaystyle x_{N-1}}$${\displaystyle {\sqrt {2\,}}\,,}$${\displaystyle X_{0}}$${\displaystyle X_{N-1}}$${\displaystyle 1/{\sqrt {2\,}}\,,}$${\displaystyle {\sqrt {{\tfrac {2}{N-1\,}}\,}},}$

DCT-Iは、偶数対称性の実数のDFTとまったく同じです (全体のスケール係数が 2 まで) 。たとえば、実数の DCT-I は、8 つの実数(偶数対称性) の DFT を 2 で割ったものとまったく同じです (対照的に、DCT タイプ II-IV では、同等の DFT で半サンプル シフトが発生します)。 ${\displaystyle 2(N-1)}$${\displaystyle N=5}$${\displaystyle a\b\c\d\e}$${\displaystyle a\b\c\d\e\d\c\b}$

ただし、DCT-Iは2未満では定義されていないのに対し、他のすべてのDCTタイプは任意の正の値に対して定義されていることに注意してください。${\displaystyle N}$${\displaystyle N.}$

したがって、DCT-Iは境界条件に対応します。 は の周りで偶数であり、 の周りで偶数です。同様に、${\displaystyle x_{n}}$${\displaystyle n=0}$${\displaystyle n=N-1}$${\displaystyle X_{k}.}$

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\left(n+{\tfrac {1}{2}}\right)k\,\right]\qquad {\text{ }}~k=0,\ \dots \ N-1~ の場合。}$

DCT-IIはおそらく最も一般的に使用されている形式であり、単に「DCT」と呼ばれることが多い。^{[5] [6]}

この変換は、偶数インデックス要素がゼロである偶数対称の実数入力のDFTとまったく同じです (全体のスケール係数が 2 まで) 。つまり、およびの入力のDFTの半分です。 2 N信号に続いて半シフトによる乗算を使用することで、DCT-II 変換も可能です。これは Makhoul によって実証されています。 ${\displaystyle 4N}$${\displaystyle 4N}$${\displaystyle y_{n},}$${\displaystyle y_{2n}=0,}$ ${\displaystyle y_{2n+1}=x_{n}}$${\displaystyle 0\leq n<N,}$ ${\displaystyle y_{2N}=0,}$${\displaystyle y_{4N-n}=y_{n}}$${\displaystyle 0<n<2N.}$

著者によっては、さらに項を で乗算し、行列の残りを全体のスケール係数 で乗算する（DCT-III での対応する変更については下記を参照）。これにより、DCT-II 行列はで直交するが、半シフト入力の実偶数DFTとの直接的な対応が崩れる。これは、たとえばMatlabで使用される正規化である（ を参照）。 ^[99] JPEGなどの多くのアプリケーションでは、スケール係数を後続の計算ステップ（たとえば、 JPEG ^[100]の量子化ステップ）と組み合わせることができるため、スケーリングは任意であり、より少ない乗算で DCT を計算できるようなスケーリングを選択できる。^{[101] [102]}${\displaystyle X_{0}}$${\displaystyle 1/{\sqrt {N\,}}\,}$${\textstyle {\sqrt {{2}/{N}}}}$

DCT-IIは境界条件を意味します:は偶数で、 は偶数で、は奇数です${\displaystyle x_{n}}$${\displaystyle n=-1/2}$${\displaystyle n=N-1/2\,;}$ ${\displaystyle X_{k}}$${\displaystyle k=0}$${\displaystyle k=N.}$

${\displaystyle X_{k}={\tfrac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\left(k+{\tfrac {1}{2}}\right)n\,\right]\qquad {\text{ for }}~k=0,\ \ldots \ N-1~.}$

これはスケール係数（下記参照）までのDCT-IIの逆であるため、単に「逆DCT」（「IDCT」）と呼ばれることもあります。^[6]

著者によっては、項を2 ではなくで割り（全体の項になる）、結果の行列に全体のスケール係数 を掛けて（DCT-II の対応する変更については上記を参照）、DCT-II と DCT-III が互いに転置されるようにする人もいます。これにより、DCT-III 行列は に直交しますが、半分シフトされた出力の 実数偶数DFTとの直接的な対応が失われます。${\displaystyle x_{0}}$${\displaystyle {\sqrt {2}}}$${\displaystyle x_{0}/{\sqrt {2}}}$${\textstyle {\sqrt {2/N}}}$

DCT-IIIは境界条件を意味します:は偶数では奇数で は偶数で は偶数${\displaystyle x_{n}}$${\displaystyle n=0}$${\displaystyle n=N;}$ ${\displaystyle X_{k}}$${\displaystyle k=-1/2}$${\displaystyle k=N-1/2.}$

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\,\left(n+{\tfrac {1}{2}}\right)\left(k+{\tfrac {1}{2}}\right)\,\right]\qquad {\text{ for }}k=0,\ \ldots \ N-1~.}$

DCT-IV行列は、全体のスケール係数をさらに乗算すると直交行列（したがって、明らかに対称であるため、その逆行列）になる。${\textstyle {\sqrt {2/N}}.}$

DCT-IVの変形で、異なる変換からのデータが重ね合わされるものは、修正離散コサイン変換（MDCT）と呼ばれます。^[103]

DCT-IVは境界条件を暗示します。は偶数で、 は奇数です。${\displaystyle x_{n}}$${\displaystyle n=-1/2}$${\displaystyle n=N-1/2;}$${\displaystyle X_{k}.}$

タイプ I ～ IV の DCT は、対称点に関して両方の境界を一貫して扱います。つまり、両方の境界のデータ ポイントの周囲または両方の境界の 2 つのデータ ポイントの中間で、境界が偶数または奇数になります。対照的に、タイプ V ～ VIII の DCT は、一方の境界のデータ ポイントの周囲で境界が偶数または奇数になり、もう一方の境界の 2 つのデータ ポイントの中間で境界が偶数または奇数になることを意味します。

言い換えれば、DCTタイプI～IVは、対応するDFTの長さが（DCT-Iの場合）または（DCT-IIとIIIの場合）または（DCT-IVの場合）であるため、偶数次の実偶数DFT（が偶数か奇数かに関係なく）と同等です。離散コサイン変換^[104]の4つの追加タイプは、本質的には論理的に奇数次の実偶数DFTに対応し、コサイン引数の分母にの因子を持ちます。 ${\displaystyle N}$${\displaystyle 2(N-1)}$${\displaystyle 4N}$${\displaystyle 8N}$${\displaystyle N\pm {1}/{2}}$

ただし、これらのバリエーションは実際にはほとんど使用されていないようです。その理由の 1 つは、奇数長 DFT のFFTアルゴリズムは、偶数長 DFT のFFTアルゴリズムよりも一般的に複雑であるためと考えられます (たとえば、最も単純な基数 2 のアルゴリズムは偶数長のみを対象としています)。この複雑さの増大は、以下で説明するように DCT にも引き継がれます。

（単純な実数偶数配列、すなわち長さ1のDFT（奇数長）は、 長さのDCT-Vに対応する） ${\displaystyle N=1.}$

上記の正規化規則を用いると、DCT-Iの逆変換はDCT-Iに2/( N −1)を掛けたものになる。DCT-IVの逆変換はDCT-IVに2/ N を掛けたものになる。DCT-IIの逆変換はDCT-IIIに2/ Nを掛けたものになり、その逆も同様である。^[6]

DFTの場合と同様に、これらの変換定義の前の正規化係数は単なる慣例であり、処理ごとに異なります。たとえば、一部の著者は、逆変換に追加の乗法係数が必要ないように、変換にを乗算します。√ 2 の適切な係数 (上記を参照) と組み合わせると、変換行列を直交にすることができます。 ${\textstyle {\sqrt {2/N}}}$

さまざまな DCT タイプの多次元バリアントは、1 次元の定義から直接導かれます。つまり、それらは単に各次元に沿った DCT の分離可能な積 (つまり、合成) です。

たとえば、画像または行列の 2 次元 DCT-II は、上記の 1 次元 DCT-II を行に沿って実行し、次に列に沿って実行したものです (またはその逆)。つまり、2D DCT-II は次の式で表されます (上記のように正規化やその他のスケール係数は省略します)。

${\displaystyle {\begin{aligned}X_{k_{1},k_{2}}&=\sum _{n_{1}=0}^{N_{1}-1}\left(\sum _{n_{2}=0}^{N_{2}-1}x_{n_{1},n_{2}}\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\right)\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\\&=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{n_{1},n_{2}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right].\end{aligned}}}$

多次元 DCT の逆は、対応する 1 次元 DCT の逆の分離可能な積にすぎません (上記を参照)。たとえば、行列アルゴリズムで一度に 1 つの次元に沿って適用される 1 次元の逆などです。

3-D DCT-IIは2 -D DCT-IIを3次元空間に拡張したもので、数学的には次の式で計算できます。

${\displaystyle X_{k_{1},k_{2},k_{3}}=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}\sum _{n_{3}=0}^{N_{3}-1}x_{n_{1},n_{2},n_{3}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\cos \left[{\frac {\pi }{N_{3}}}\left(n_{3}+{\frac {1}{2}}\right)k_{3}\right],\quad {\text{for }}k_{i}=0,1,2,\dots ,N_{i}-1.}$

3-D DCT-IIの逆は3-D DCT-IIIであり、次の式から計算できる。

${\displaystyle x_{n_{1},n_{2},n_{3}}=\sum _{k_{1}=0}^{N_{1}-1}\sum _{k_{2}=0}^{N_{2}-1}\sum _{k_{3}=0}^{N_{3}-1}X_{k_{1},k_{2},k_{3}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\cos \left[{\frac {\pi }{N_{3}}}\left(n_{3}+{\frac {1}{2}}\right)k_{3}\right],\quad {\text{for }}n_{i}=0,1,2,\dots ,N_{i}-1.}$

技術的には、各次元に沿った 1 次元 DCT のシーケンスによって 2 次元、3 次元 (または多次元) DCT を計算することは、行列アルゴリズムとして知られています。ただし、多次元 FFT アルゴリズムと同様に、計算を異なる順序で実行しながら同じことを計算する他の方法も存在します (つまり、異なる次元のアルゴリズムをインターリーブ/組み合わせる)。3-D DCT に基づくアプリケーションの急速な成長により、3-D DCT-II の計算用にいくつかの高速アルゴリズムが開発されています。ベクトル基数アルゴリズムは、MD DCT の計算に適用され、計算の複雑さを軽減し、計算速度を上げます。3-D DCT-II を効率的に計算するために、高速アルゴリズムである周波数におけるベクトル基数デシメーション (VR DIF) アルゴリズムが開発されました。

VR DIFアルゴリズムを適用するには、入力データを次のように定式化し、並べ替える必要があります。^{[105] [106]}変換サイズN×N×Nは2と仮定します。

${\displaystyle {\begin{array}{lcl}{\tilde {x}}(n_{1},n_{2},n_{3})=x(2n_{1},2n_{2},2n_{3})\\{\tilde {x}}(n_{1},n_{2},N-n_{3}-1)=x(2n_{1},2n_{2},2n_{3}+1)\\{\tilde {x}}(n_{1},N-n_{2}-1,n_{3})=x(2n_{1},2n_{2}+1,2n_{3})\\{\tilde {x}}(n_{1},N-n_{2}-1,N-n_{3}-1)=x(2n_{1},2n_{2}+1,2n_{3}+1)\\{\tilde {x}}(N-n_{1}-1,n_{2},n_{3})=x(2n_{1}+1,2n_{2},2n_{3})\\{\tilde {x}}(N-n_{1}-1,n_{2},N-n_{3}-1)=x(2n_{1}+1,2n_{2},2n_{3}+1)\\{\tilde {x}}(N-n_{1}-1,N-n_{2}-1,n_{3})=x(2n_{1}+1,2n_{2}+1,2n_{3})\\{\tilde {x}}(N-n_{1}-1,N-n_{2}-1,N-n_{3}-1)=x(2n_{1}+1,2n_{2}+1,2n_{3}+1)\\\end{array}}}$

どこ${\displaystyle 0\leq n_{1},n_{2},n_{3}\leq {\frac {N}{2}}-1}$

隣の図は、VR DIF アルゴリズムを使用して 3-D DCT-II を計算する際に必要な 4 つの段階を示しています。最初の段階は、上記の式で示したインデックス マッピングを使用した 3-D 並べ替えです。2 番目の段階はバタフライ計算です。各バタフライは、下の図に示すように 8 つのポイントをまとめて計算します。 ${\displaystyle c(\varphi _{i})=\cos(\varphi _{i})}$

オリジナルの3D DCT-IIは次のように記述できる。

${\displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}=1}^{N-1}\sum _{n_{2}=1}^{N-1}\sum _{n_{3}=1}^{N-1}{\tilde {x}}(n_{1},n_{2},n_{3})\cos(\varphi k_{1})\cos(\varphi k_{2})\cos(\varphi k_{3})}$

どこ${\displaystyle \varphi _{i}={\frac {\pi }{2N}}(4N_{i}+1),{\text{ and }}i=1,2,3.}$

と の偶数部と奇数部を考慮すると、3-D DCT-IIの計算の一般的な式は次のように表すことができます。${\displaystyle k_{1},k_{2}}$${\displaystyle k_{3}}$

${\displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}=1}^{{\tfrac {N}{2}}-1}\sum _{n_{2}=1}^{{\tfrac {N}{2}}-1}\sum _{n_{1}=1}^{{\tfrac {N}{2}}-1}{\tilde {x}}_{ijl}(n_{1},n_{2},n_{3})\cos(\varphi (2k_{1}+i)\cos(\varphi (2k_{2}+j)\cos(\varphi (2k_{3}+l))}$

どこ

${\displaystyle {\tilde {x}}_{ijl}(n_{1},n_{2},n_{3})={\tilde {x}}(n_{1},n_{2},n_{3})+(-1)^{l}{\tilde {x}}\left(n_{1},n_{2},n_{3}+{\frac {n}{2}}\right)}$

${\displaystyle +(-1)^{j}{\tilde {x}}\left(n_{1},n_{2}+{\frac {n}{2}},n_{3}\right)+(-1)^{j+l}{\tilde {x}}\left(n_{1},n_{2}+{\frac {n}{2}},n_{3}+{\frac {n}{2}}\right)}$

${\displaystyle +(-1)^{i}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2},n_{3}\right)+(-1)^{i+j}{\tilde {x}}\left(n_{1}+{\frac {n}{2}}+{\frac {n}{2}},n_{2},n_{3}\right)}$

${\displaystyle +(-1)^{i+l}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2},n_{3}+{\frac {n}{3}}\right)}$

${\displaystyle +(-1)^{i+j+l}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2}+{\frac {n}{2}},n_{3}+{\frac {n}{2}}\right){\text{ where }}i,j,l=0{\text{ or }}1.}$

3-D DCT の計算には段階が必要であり、各段階ではバタフライが行われます。3-D DCT の計算にはバタフライが必要です。各バタフライには、7 回の実数乗算 (単純な乗算を含む) と 24 回の実数加算 (単純な加算を含む) が必要です。したがって、この段階に必要な実数乗算の総数は、バタフライ段階の直後またはビット反転段階の後に計算できる後加算 (再帰加算) を含む実数加算の総数は、次のように与えられます^[106]${\displaystyle ~[\log _{2}N]~}$${\displaystyle ~{\tfrac {1}{8}}\ N^{3}~}$${\displaystyle ~\left[{\tfrac {1}{8}}\ N^{3}\log _{2}N\right]~}$${\displaystyle ~\left[{\tfrac {7}{8}}\ N^{3}\ \log _{2}N\right]~,}$ ${\displaystyle ~\underbrace {\left[{\frac {3}{2}}N^{3}\log _{2}N\right]} _{\text{Real}}+\underbrace {\left[{\frac {3}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]} _{\text{Recursive}}=\left[{\frac {9}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]~.}$

MD-DCT-IIを計算する従来の方法は、計算が複雑で、最新のハードウェアプラットフォームでは生産性が低い行-列-フレーム（RCF）アプローチを使用しています。VR DIFアルゴリズムを計算するために必要な乗算の数は、RCFアルゴリズムと比較してかなり少なくなっています。RCFアプローチに含まれる乗算と加算の数は、それぞれとで与えられます。表1から、合計数は ${\displaystyle ~\left[{\frac {3}{2}}N^{3}\log _{2}N\right]~}$${\displaystyle ~\left[{\frac {9}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]~,}$

3-D DCT VR アルゴリズムに関連する乗算の​​回数は、RCF アプローチに関連する乗算の​​回数より 40% 以上少なくなります。さらに、RCF アプローチでは、新しい VR アルゴリズムよりも行列転置とインデックス作成およびデータ スワップが多くなります。これにより、3-D DCT VR アルゴリズムはより効率的になり、ビデオ圧縮やその他の 3-D 画像処理アプリケーションなど、3-D DCT-II を含む 3-D アプリケーションにより適したものになります。

高速アルゴリズムを選択する際の主な考慮事項は、計算と構造の複雑さを回避することです。コンピューターと DSP の技術が進歩するにつれて、算術演算 (乗算と加算) の実行時間は非常に高速になり、規則的な計算構造が最も重要な要素になります。^[107]したがって、上記で提案された 3-D VR アルゴリズムは、乗算回数の理論的な下限を達成していませんが、^[108]他の 3-D DCT アルゴリズムと比較して計算構造が単純です。単一のバタフライを使用して実装でき、 3-D でCooley-Tukey FFT アルゴリズムの特性を備えています。したがって、3-D VR は、バタフライスタイルのCooley-Tukey FFT アルゴリズムを特徴付ける単純な構造を維持しながら、3-D DCT-II の計算で算術演算を削減するための優れた選択肢となります。

右の画像は、8 × 8 の 2 次元 DCT の水平周波数と垂直周波数の組み合わせを示しています。左から右、上から下への各ステップは、周波数が 1/2 サイクル増加します。たとえば、左上の正方形から右に 1 つ移動すると、水平周波数が半サイクル増加します。右にもう 1 つ移動すると、半サイクルが 2 つ増加します。下に移動すると、水平方向に半サイクルが 2 つ、垂直方向に半サイクルが 1 つ増加します。ソース データ(8×8)は、これらの 64 個の周波数正方形の 線形結合に変換されます。${\displaystyle (~N_{1}=N_{2}=8~)}$

MD DCT-IVは、1次元DCT-IVをM次元領域に拡張したものです 。行列または画像の2次元DCT-IVは次のように表されます。

${\displaystyle X_{k,\ell }=\sum _{n=0}^{N-1}\;\sum _{m=0}^{M-1}\ x_{n,m}\cos \left(\ {\frac {\,(2m+1)(2k+1)\ \pi \,}{4N}}\ \right)\cos \left(\ {\frac {\,(2n+1)(2\ell +1)\ \pi \,}{4M}}\ \right)~,}$

および​${\displaystyle ~~k=0,\ 1,\ 2\ \ldots \ N-1~~}$${\displaystyle ~~\ell =0,\ 1,\ 2,\ \ldots \ M-1~.}$

MD DCT-IVは、通常の行-列法を使って計算することも、高速かつ効率的に計算するために多項式変換法^[109]を使うこともできます。このアルゴリズムの主なアイデアは、多項式変換を使用して多次元DCTを一連の1次元DCTに直接変換することです。MD DCT-IVは、さまざまな分野でいくつかの用途があります。

これらの式を直接適用するには演算が必要ですが、高速フーリエ変換(FFT)と同様に計算を因数分解することで、複雑さのみで同じことを計算できます。また、前処理および後処理のステップと組み合わせた FFT を介して DCT を計算することもできます。一般に、 DCT を計算する方法は、高速コサイン変換 (FCT) アルゴリズムとして知られています。 ${\displaystyle ~{\mathcal {O}}(N^{2})~}$${\displaystyle ~{\mathcal {O}}(N\log N)~}$${\displaystyle ~{\mathcal {O}}(N)~}$${\displaystyle ~{\mathcal {O}}(N\log N)~}$

原則として、最も効率的なアルゴリズムは通常、通常の FFT と追加の演算を使用するのではなく、DCT に直接特化されたものです(例外については以下を参照)。ただし、「特化された」DCT アルゴリズム (少なくとも2 の累乗のサイズで、既知の算術カウントが最も少ないものすべてを含む) でさえ、通常は FFT アルゴリズムと密接に関連しています。DCT は本質的に実数偶数データの DFT であるため、FFT を取得してこの対称性による冗長な演算を排除することで、高速 DCT アルゴリズムを設計できます。これは自動的に行うこともできます (Frigo & Johnson 2005)。Cooley -Tukey FFT アルゴリズムに基づくアルゴリズムが最も一般的ですが、他の FFT アルゴリズムも適用できます。たとえば、Winograd FFT アルゴリズムは、一般的には加算が多くなるというコストはかかりますが、DFT の最小乗算アルゴリズムにつながり、同様のアルゴリズムが DCT 用に提案されました (Feig & Winograd 1992a)。 DFT、DCT、および類似の変換のアルゴリズムはすべて密接に関連しているため、1 つの変換のアルゴリズムを改善すると、理論的には他の変換にもすぐに効果が現れます (Duhamel & Vetterli 1990)。 ${\displaystyle ~{\mathcal {O}}(N)~}$

変更されていない FFT を使用する DCT アルゴリズムは、最良の専用 DCT アルゴリズムと比較して理論上のオーバーヘッドが多少あることがよくありますが、前者には明確な利点もあります。高度に最適化された FFT プログラムが広く利用できるからです。したがって、実際には、一般的な長さNに対しては、FFT ベースのアルゴリズムの方が高いパフォーマンスを得るのが簡単な場合が多いです。^[a] 一方、専用 DCT アルゴリズムは、JPEG圧縮で使用される8 × 8 DCT-IIや、オーディオ圧縮で一般的に使用される小さな DCT (または MDCT) など、固定された小さなサイズの変換に広く使用されています。(組み込みデバイス アプリケーションでは、コード サイズが小さいことも、専用 DCT を使用する理由の 1 つです。)

実際、通常の FFT を使用する DCT アルゴリズムは、実対称データのより大きな FFT から冗長な操作をプルーニングすることと同等である場合があり、算術カウントの観点から最適である場合もあります。たとえば、タイプ II DCT は、偶数インデックス要素がゼロである実偶数対称のサイズの DFT と同等です。これを FFT で計算する最も一般的な方法の 1 つ (たとえば、FFTPACKおよびFFTWで使用される方法) は、Narasimha & Peterson (1978) および Makhoul (1980) によって説明されました。この方法は、後から考えると、DCT-II に対応する「論理」実偶数 DFT に適用された基数 4 の時間デシメーション Cooley–Tukey アルゴリズムの 1 つのステップと見なすことができます。^[b] 偶数インデックス要素がゼロであるため、この基数 4 のステップは、分割基数ステップとまったく同じです。後続のサイズの実データFFTも実データ分割基数アルゴリズム（Sorensenら（1987）のように）によって実行される場合、結果として得られるアルゴリズムは、実際には、2の累乗DCT-II（実数演算^[c] ）に対して長い間公表されていた最も低い演算カウントと一致します。 ${\displaystyle ~4N~}$${\displaystyle ~N~}$${\displaystyle ~2N\log _{2}N-N+2~}$

最近では、演算回数を減らして実データFFTも使用しています。^[110]そのため、算術的な観点からFFTでDCTを計算することに本質的に悪い点はありません。対応するFFTアルゴリズムが最適かどうかという問題に過ぎない場合があります。(実際問題として、別のFFTルーチンを呼び出す際の関数呼び出しのオーバーヘッドは小さい場合には大きいかもしれませんが、これはアルゴリズムの問​​題ではなく実装の問題であり、アンロールまたはインライン展開によって解決できます。) ${\displaystyle ~{\tfrac {17}{9}}N\log _{2}N+{\mathcal {O}}(N)}$${\displaystyle ~N~,}$

大文字の A の 8x8 グレースケール画像を検討してください。

各基底関数にその係数を乗算し、その積を最終画像に加算します。

• 離散ウェーブレット変換
• JPEG  - 離散 コサイン 変換 -  DCT変換のより理解しやすい例が含まれています
• フーリエ関連変換の一覧
• 修正離散コサイン変換

• Narasimha, M.; Peterson, A. (1978 年 6 月)。「離散コサイン変換の計算について」IEEE Transactions on Communications 26 ( 6): 934–936. doi :10.1109/TCOM.1978.1094144。
• Makhoul, J. (1980 年 2 月)。「1 次元および 2 次元での高速コサイン変換」IEEE Transactions on Acoustics, Speech, and Signal Processing 28 ( 1): 27–34. doi :10.1109/TASSP.1980.1163351。
• Sorensen, H.; Jones, D.; Heideman, M.; Burrus , C. (1987 年 6 月)。「実数値高速フーリエ変換アルゴリズム」。IEEE Transactions on Acoustics, Speech, and Signal Processing。35 ( 6): 849–863。CiteSeerX 10.1.1.205.4523。doi : 10.1109 / TASSP.1987.1165220。 
• Plonka, G. ; Tasche, M. (2005 年 1 月). 「離散コサイン変換のための高速かつ数値的に安定したアルゴリズム」.線形代数とその応用. 394 (1): 309–345. doi : 10.1016/j.laa.2004.07.015 .
• Duhamel, P.; Vetterli, M. (1990 年 4 月)。「高速フーリエ変換:チュートリアル レビューと最新技術」。信号処理(投稿原稿)。19 ( 4): 259–299。Bibcode :1990SigPr..19..259D。doi : 10.1016/0165-1684(90)90158-U。
• Ahmed, N. ( 1991 年 1 月)。「離散コサイン変換を思いついた経緯」。デジタル信号処理。1 (1): 4–9。Bibcode : 1991DSP .....1....4A。doi :10.1016/1051-2004(91)90086-Z。
• Feig, E .; Winograd, S. (1992b 年 9 月)。「離散コサイン変換の高速アルゴリズム」。IEEE Transactions on Signal Processing。40 ( 9): 2174–2193。Bibcode : 1992ITSP ...40.2174F。doi : 10.1109/78.157218。
• マルバー、エンリケ（1992）、ラップ変換による信号処理、ボストン：アーテックハウス、ISBN 978-0-89006-467-2
• Martucci, SA (1994 年 5 月)。「対称畳み込みと離散正弦および余弦変換」。IEEE Transactions on Signal Processing。42 ( 5 ) : 1038–1051。Bibcode : 1994ITSP ...42.1038M。doi : 10.1109/78.295213。
• オッペンハイム、アラン、シェーファー、ロナルド、バック、ジョン（1999）、離散時間信号処理（第2版）、アッパーサドルリバー、ニュージャージー：プレンティスホール、ISBN 978-0-13-754920-7
• Frigo, M .; Johnson, SG (2005 年 2 月)。「FFTW3の設計と実装」( PDF)。IEEEの議事録。93 (2): 216–231。Bibcode :2005IEEEP..93..216F。CiteSeerX 10.1.1.66.3097。doi : 10.1109 /JPROC.2004.840301。S2CID 6644892  。 
• Boussakta, Said.; Alshibami, Hamoud O. (2004 年 4 月)。「3-D DCT-II の高速アルゴリズム」( PDF)。IEEE Transactions on Signal Processing。52 ( 4): 992–1000。Bibcode : 2004ITSP ...52..992B。doi : 10.1109/TSP.2004.823472。S2CID 3385296  。
• Cheng, LZ; Zeng, YH (2003). 「多次元タイプIV DCTの新しい高速アルゴリズム」. IEEE Transactions on Signal Processing . 51 (1): 213–220. doi :10.1109/TSP.2002.806558.
• Wen-Hsiung Chen、Smith、 C.、Fralick、S. (1977 年 9 月)。「離散コサイン変換の高速計算アルゴリズム」IEEE Transactions on Communications 25 (9): 1004–1009。doi : 10.1109/TCOM.1977.1093941。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 12.4.2. コサイン変換」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8、2011年8月11日にオリジナルからアーカイブされ、2011年8月13日に取得

• Syed Ali Khayam: 離散コサイン変換 (DCT): 理論と応用
• 8x8 IDCT の MPEG 整数近似の実装 (ISO/IEC 23002-2)
• Matteo Frigo およびSteven G. Johnson : FFTW、FFTW ホームページ。任意のサイズの 1 次元または複数次元の高速 DCT (タイプ I-IV) を計算できる無料 ( GPL ) C ライブラリ。
• Takuy​​a Ooura: 汎用 FFT パッケージ、FFT パッケージ 1 次元 / 2 次元。1 次元、2 次元、または 3 次元、2 の累乗サイズの高速 DCT (タイプ II ～ III) を計算するための無料の C および FORTRAN ライブラリ。
• Tim Kientzle: 8 ポイント DCT および IDCT を計算するための高速アルゴリズム、Algorithm Alley。
• LTFAT は、タイプ I ～ IV の DCT および DST の FFTW 実装へのインターフェースを備えた無料の Matlab/Octave ツールボックスです。