JP2004310735A

JP2004310735A - 高速逆離散余弦変換方法及び装置

Info

Publication number: JP2004310735A
Application number: JP2003389915A
Authority: JP
Inventors: Sang-Chang Cha; 尚昌車; Jong-Hak Ahn; 鐘学安
Original assignee: Samsung Electronics Co Ltd
Current assignee: Samsung Electronics Co Ltd
Priority date: 2002-11-20
Filing date: 2003-11-19
Publication date: 2004-11-04
Also published as: CN1520186A; US20040133613A1; CN1250009C; KR20040044253A; KR100561392B1; EP1422664A2

Abstract

【課題】高速逆離散余弦変換方法及び装置を提供する。
【解決手段】所定の離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する段階と、検索された０でない値を有する元素を２次元逆離散余弦変換する段階と、離散余弦変換行列の０でない値を有する元素の数が前記臨界値を超過する場合、離散余弦変換行列を２次元逆離散余弦変換する段階と、を含む高速逆離散余弦変換方法。
【選択図】図４

Description

本発明は高速逆離散余弦変換方法及び装置に関する。

デジタル形式のデータの圧縮、特に映像信号の圧縮は多様なマルチメディア応用環境において必須な要素であるが、映像信号は多くの情報を処理しなければならないので効率的な伝送や保存及び加工に多くの制約が生じる。このような制約を解決するためにＭＰＥＧ−２、ＭＰＥＧ−４、Ｈ２６３、Ｈ．２６Ｌなど国際的標準は圧縮ストリーム文法及び復号化過程を定義している。

圧縮方式には無損失圧縮方式と損失圧縮方式とがあるが、文字、図形、一般データなどを無損失圧縮すれば完全復旧が可能であるが、圧縮率は平均的に約２対１である。一方、映像、音声、音響などのデータを人間の目と耳とがほとんど感じられない程度に小さな損失を許しながら圧縮すれば１０対１以上の圧縮率を容易に得られる。映像データを効果的に圧縮するための目的として最も広く使われる損失符号化技法は変換符号化である。この方式の基本構造は、空間的に高い相関度を有しつつ配列されているデータを直交変換によって低周波成分から高周波成分に至るまでいろいろな周波数成分に分けて成分別に別途に量子化することである。この時、各周波数成分間には相関度がほとんどなくなり、信号のエネルギーが低周波方向に集中する。直交変換により周波数領域に変わったデータはエネルギーが多く集まる（すなわち、分散値が大きい）周波数成分がさらに多くのビットを割り当てられてその周波数成分をより充実に表現する。分散値が４倍（すなわち、振幅が２倍）になる度に１ビットずつさらに割り当てられるが、このようになれば、あらゆる周波数成分で同じ量子化エラー特性を有する。色々な直交変換のうち、理論的に映像信号のエネルギー集中特性が最も優れて圧縮に最も効果的なものはカルーネンレーブ変換（ＫＬＴ，Ｋａｒｈｕｎｅｎ−ＬｏｅｖｅＴｒａｎｓｆｏｒｍ）である。しかし、これは映像によって変換関数が新しく定義されねばならないために現実的に使用できない。カルーネンレーブ変換に十分に近い性能を有しつつ具現可能な変換が直ちに離散余弦変換（ＤＣＴ，ＤｉｓｃｒｅｔｅＣｏｓｉｎｅＴｒａｎｓｆｏｒｍ）である。現在、いろいろな国際標準に核心技術になっている離散余弦変換は８×８サイズの画素を一つのブロックに縛って変換の単位としている。ブロックを大きくすればするほど圧縮効率は高まるが、変換の具現がもっと難しくなる。実験的に８×８サイズが性能と具現の容易性間の妥協点として選択された。

従来の圧縮技術は一般的に映像を圧縮する時に空間上の重畳性を除去するために離散余弦変換を使用し、時間上の重畳性を除去するために動き推定（ＭＥ，ＭｏｔｉｏｎＥｓｔｉｍａｔｉｏｎ）と動き補償（ＭＣ，ＭｏｔｉｏｎＣｏｍｐｅｎｓａｔｉｏｎ）とを使用する。

図１は従来の２次元逆離散余弦変換（２Ｄ−ＩＤＣＴ，２Ｄｉｍｅｎｓｉｏｎ−ＩｎｖｅｒｓｅＤｉｓｃｒｅｔｅＣｏｓｉｎｅＴｒａｎｓｆｏｒｍ）の方向を示した図面である。

逆離散余弦変換過程の計算量を減らすことにより、高速で逆離散余弦変換するための従来の一方式として、図１のように１次元逆離散余弦変換を横及び縦方向に各々独立的に実施したが、これを２次元逆離散余弦変換という。特に、図１は横Ｎ回、縦Ｎ回に対する２つの逆離散余弦変換と転置を通したＲＣＡ（ＲｏｗＣｏｌｕｍｎＡｌｇｏｒｉｔｈｍ）方式を使用した２次元逆離散余弦変換である。すなわち、列方向に１次元逆離散余弦変換を行った後、その結果値を行に計算するために、転置した後、１次元逆離散余弦変換を行う。

図２は従来の逆離散余弦変換アルゴリズムの計算量を比較した比較表を示した図面である。
前記図１の２次元逆離散余弦変換を実現するための逆離散余弦変換アルゴリズムには行列因数分解（ＳｐａｒｓｅＭａｔｒｉｘＦａｃｔｏｒｉｚａｔｉｏｎｓ）に基づいたＣｈｅｎｇアルゴリズム、Ｗａｎｇアルゴリズムと離散フーリエ変換（ＤｉｓｃｒｅｔｅＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍ）に基づいたＬｅｅアルゴリズム、ＡＡＮアルゴリズムがある。図２にはこれらアルゴリズムを行うのに要求される乗算及び加算の回数を表示した。

図３は従来の高速逆離散余弦変換アルゴリズムのうち一つであるＷａｎｇアルゴリズムを示した図面である。
入力信号ｘ（０）〜ｘ（７）に対して出力信号Ｘ（０）〜Ｘ（７）が出力される。この過程で各接点には以前接点との計算結果が伝えられねばならない。接点と接点間の定数Ｃ０〜Ｃ７は、次の接点を計算する時、以前接点に乗算されねばならない値を示す。例として、Ｃ０＝ｘ（１）＋ｘ（７）のように計算できる。このような方法によりすべての計算を完了すれば、乗算器は１６つ、加算器は２６つが必要になる。具体的な実施において少しずつ方法の差はあるが、大多数の高速アルゴリズムは類似した形態を取っている。

従来の高速逆離散余弦変換アルゴリズムは、逆離散余弦変換計算の複雑度はだいぶ減少させるが、圧縮を解く復元過程で、逆離散余弦変換過程が最も多くの計算量を要求するという問題点があった。多様なマルチメディアサービスを提供する現在のモバイル環境で、エンコーダはマルチメディアサービスを提供する事業者のサーバーシステムであるためにサイズ及び電力消耗において、大きい制約を受けないが、デコーダは携帯電話、ＰＤＡ（ＰｅｒｓｏｎａｌＤｉｇｉｔａｌＡｓｓｉｓｔａｎｔ）など移動通信機器であるためにサイズ及び電力消耗において制約を受け、デコーダで行われる逆離散余弦変換は計算量が減少されねばならない問題点があった。

本発明が解決しようとする技術的課題は、有効な値を有する元素の数によって離散余弦変換行列を元素別に２次元逆離散余弦変換、または行列別に２次元逆離散余弦変換することによって、逆離散余弦変換過程の計算量を顕著に減少させる方法及び装置を提供するところにある。

前記問題点を解決するための本発明による高速逆離散余弦変換方法は、所定の離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する段階と、前記検索された０でない値を有する元素を２次元逆離散余弦変換する段階と、前記離散余弦変換行列の０でない値を有する元素の数が前記臨界値を超過する場合、前記離散余弦変換行列を２次元逆離散余弦変換する段階と、を含む。

前記他の問題点を解決するための本発明による高速逆離散余弦変換装置は、所定の離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する元素検索部と、前記元素検索部で検索された０でない値を有する元素を２次元逆離散余弦変換する元素別２次元逆離散余弦変換部と、前記離散余弦変換行列の０でない値を有する元素の数が前記臨界値を超過する場合、前記離散余弦変換行列を２次元逆離散余弦変換する行列別２次元逆離散余弦変換部と、を含む。

本発明によれば、逆離散余弦変換を行うに当って、離散余弦変換行列の元素値の大多数を占める“０”による不要な計算を最大限減らしうる。また、圧縮ファイルの圧出率が低くて、“０”でない値を有する元素の数が少ない時には既存の高速逆離散余弦変換アルゴリズムを使用することにより、量子化スケールによって最適の逆離散余弦変換アルゴリズムを提供するという効果がある。特に、本発明で提示した元素別２次元逆離散余弦変換アルゴリズムと既存の高速逆離散余弦変換アルゴリズムとを混用する場合、広く使われる映像信号に対して元素別２次元逆離散余弦変換アルゴリズムと既存の高速逆離散余弦変換アルゴリズムとの適用比率は適用対象によって差があるが、大体８０％以上、元素別２次元逆離散余弦変換アルゴリズムが適用されるために、逆離散余弦変換の計算量が顕著に減少するという効果がある。さらに、ビデオデコーダで全体計算量のうち２５〜３０％に該当する逆離散余弦変換モジュールの計算量を画期的に減らすことにより、さらに安定して性能が改善されたビデオデコーダを設計でき、消耗電力が減少するために小型化されたモバイル用ビデオデコーダを設計できるという効果がある。

また、ＥＯＢ（ＥｎｄＯｆＢｌｏｃｋ，ブロック内の演算対象係数の数）を参照して計算する他の高速離散余弦変換アルゴリズムではスキャン方式によって他の方法を適用しなければならないが、本発明はスキャン方式に関係なく、すなわちジグザグスキャン、水平優先スキャン、垂直優先スキャンに関係なく適用可能である。また、計算過程で有効数字を最大限利用する。すなわち、ラウンド回数がただ１回であるために、既存の逆離散余弦変換よりＰＳＮＲ（ＰｅａｋＳｉｇｎａｌ−ｔｏ−ＮｏｉｓｅＲａｔｉｏ）が優秀である。

以下、図面を参照して本発明の望ましい実施例を詳細に説明する。
図４は本発明による高速逆離散余弦変換装置の構成図である。
高速逆離散余弦変換装置は有効元素数計算部４０、元素検索部４１、元素別２次元逆離散余弦変換部４２、及び行列別２次元逆離散余弦変換部４３で構成される。

一般的に映像データを圧縮する過程は次の通りである。まず、時間領域の映像信号をいくつかの信号電力が高周波である領域と低周波である領域とに分解して変換する離散余弦変換を行う。ここで、映像信号の電力は低周波領域に集中しているために適切なビット配分に量子化すれば、全体のビット数を減少させてデータを圧縮できる。次いで、一定のサイズを有する量子に分けることによって、小さな値は０にして全体的なデータ量を減らすための量子化を行う。この時、０になって消えた数字のために若干の情報損失がある。次いで、連続的に反復される文字（ここでは０）を一つの文字とその長さとに代えるランレングスエンコーディングを行う。反復される文字が長いか、さらに頻繁に現れるほど圧縮効率は高まる。次いで、ジグザグスキャニングを通じて作られた整数列を２進数に変換するハフマンエンコーディングを行う。前記のあらゆる圧縮過程を通過すれば、８×８行列はいくつかの０と１との組合わせに減る。このように圧縮された映像データを解くためには、前記の圧縮過程を逆に行えばよい。

前記のように、映像データを離散余弦変換した後に量子化すれば、圧縮情報の大部分は低周波領域に集まり、高周波領域はほとんどゼロになる。量子化スケールが大きいほど多くの値が０になるために、離散余弦変換行列で０でない値を有する元素の数は減り、量子化スケールが小さいほど、０でない値を有する元素の数は多くなる。量子化スケールが大きくて、離散余弦変換行列で０でない値を有する元素の数が少ない時には従来の高速逆離散余弦アルゴリズムを利用して、行列全体を逆離散余弦変換する必要なく、０でない値を有する元素だけを逆離散余弦変換すればよい。しかし、量子化スケールが小さくて、離散余弦変換行列で０でない値を有する元素の数が多い時には従来の高速逆離散余弦アルゴリズムを利用することが効率的である。

元素検索部４１は、離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する。元素別２次元逆離散余弦変換部４２は、元素検索部４１で検索された０でない値を有する元素を２次元逆離散余弦変換する。前記のように、離散余弦変換行列で０でない値を有する元素の数が元素別に逆離散余弦変換を行うか、あるいは行列別に逆離散余弦変換を行うかを決定するために、適当な大きさの臨界値を定めて、０でない値を有する元素の数をこの臨界値と比較する。言い換えれば、元素別に逆離散余弦変換を行うことが行列別に逆離散余弦変換を行うことより演算の量が減少する場合において、離散余弦変換行列の０でない値を有する元素の数が最大値になるように決定した値が臨界値である。実験によれば、量子化スケールが１０以下の場合に臨界値を１５に定め、１０を超える場合には臨界値を１０に定めることが最も効率的であった。

前記のように、圧縮ファイルに対する一連のデコーディング過程は圧縮過程の逆過程であるために、ハフマンデコーディング、ランレングスデコーディング、逆量子化、及び逆離散余弦変換の過程を経て行われる。離散余弦変換行列の０でない値を有する元素の数は逆離散余弦変換前に行われるランレングスデコーディング過程であらかじめ分かる。ランレングスエンコーディング過程は連続的に反復される０を一つの０とその長さとに代えることであるために、ランレングスデコーディング過程で０の長さが分かる。したがって、ランレングスデコーディング過程で０でない値を有する元素の数が分かる。

すなわち、有効元素数計算部４０は所定の圧縮ファイルに対する一連のデコーディング過程の一過程である、前記離散余弦変換行列の各元素に対して０でない値を有する元素を検索する前に行われるランレングスデコーディング過程で、０でない値を有する元素だけをカウントすることによって０でない値を有する元素の数を計算する。例えば、エンコーディング過程で量子化スケールが１０以下であり、したがって臨界値を１５に定めたとしよう。量子化スケールが１０以下の離散余弦変換行列の０でない値を有する元素の数が１５以下である場合には、行列別に逆離散余弦変換することより元素別に逆離散余弦変換することが効率的である。

行列別２次元逆離散余弦変換部４３は、離散余弦変換行列の０でない値を有する元素の数が臨界値を超過する場合、離散余弦変換行列を２次元逆離散余弦変換する。前記例で、量子化スケールが１０以下の離散余弦変換行列の０でない値を有する元素の数が１５を超過する場合には、元素別に逆離散余弦変換することより、行列別に逆離散余弦変換することが効率的である。行列別逆離散余弦変換部４３はＷａｎｇアルゴリズム、Ｃｈｅｎアルゴリズム、Ｌｅｅアルゴリズム、またはＡＡＮアルゴリズムのうちいずれか一つの高速逆離散余弦変換アルゴリズムを使用して２次元逆離散余弦変換する。

図５は一般的な８×８離散余弦変換行列の一例を示した図面である。
映像情報が集中した元素であるほど暗く図示した。前記のように、映像情報が最も多く集中した元素、すなわち最も低い周波数帯の元素であるＡ１が最も暗く図示されている。特に、Ａ１の値をＤＣ（低周波）値といい、残りの６３つの元素値をＡＣ（高周波）値という。ＤＣ値及びこの近くにある元素値、行列左側の上段にある元素値は映像全体の輝度を牛耳る非常に重要な情報を含んでいる。

元素検索部４１で離散余弦変換行列の各元素に対して０でない値を有する元素は、水平方向に各元素につながる順序で検索することもあり、垂直方向に各元素につながる順序で検索することもあるが、０でない値を有する元素は行列の左側上段に集まっているために、Ａ１を出発点としてジグザグ方向に各元素につながる順序で検索する。すなわち、Ａ１、Ａ２、Ａ３、…につながる順序で検索することが最も少ない処理量で最も多くの０でない値を有する元素を検索できる。

図６は本発明による前記図４の元素別２次元逆離散余弦変換部４２の詳細構成図である。
前記図４の元素別２次元逆離散余弦変換部４２は一部値算出部６１、及び完全値算出部６２で構成される。

一般的に、２次元逆離散余弦変換を行うためには次のような式を使用する。

但し、ｉ≠０及びｊ≠０である場合はＣ（ｉ，ｊ）＝２／Ｎ、ｉ＝０またはｊ＝０である場合はＣ（ｉ，ｊ）＝１／Ｎ

式(1)でＴ（ｉ，ｊ）は離散余弦変換行列Ｔのｉ＋１、ｊ＋１座標にある元素値であり、Ｖ（ｘ，ｙ）は離散余弦変換行列から逆離散余弦変換された復元行列Ｖのｘ＋１、ｙ＋１座標にある元素値である。もし、離散余弦変換行列Ｔが一般的に使われる８×８行列であれば、ｉ、ｊ、ｘ、ｙは０〜７間の値を有し、Ｎ＝８である。

離散余弦変換行列で０でない値を有する元素だけを処理するために重畳の原理を使用する。すなわち、重畳の原理によって、離散余弦変換行列の元素値ブロックを一部ずつ、または一つずつ分けて各々逆離散余弦変換した後、その結果を合せれば全体を一度に逆離散余弦変換したことと同じ結果が出る。本発明では離散余弦変換行列の元素値のブロック値を一つずつ検索して、有効な値がある部分だけを逆離散余弦変換した後、その結果を最終的に合せて復元行列を求める。元素別に２次元逆離散余弦変換するためには０でない値を有する離散余弦変換行列の元素に対して次の式のように計算しなければならない。

ここで、ＩＤＣＴ（Ｔ）は８×８離散余弦変換行列Ｔから逆離散余弦変換された８×８復元行列Ｖをいい、ＩＤＣＴ（Ｔ（０，０））は数式１に離散余弦変換行列の最初の行及び最初の列の元素値であるＴ（０，０）とその座標値ｉ＝０、ｊ＝０とを代入した後、復元行列Ｖのそれぞれの座標値ｘ＝０〜７、ｙ＝０〜７を代入した結果値が、ｘ、ｙ座標にある元素値になる８×８行列であり、これは８×８復元行列Ｖの一部値になる。すなわち、離散余弦変換行列Ｔの０でないあらゆる元素に対して、復元行列Ｖの一部値になる行列を全部求めた後に合せれば、重畳の原理によって求めようとする復元行列の値を得られる。本発明を実際的に具現する時には、前記の復元行列Ｖの一部値になる行列はメモリにテーブル形態に保存し、以後に保存されたあらゆるテーブルの対応するメモリアドレスにある値を合せることによって、復元行列値を求めることができる。

前記のように、離散余弦変換行列の０でない値を有する元素の数が量子化スケールによって６以下、１０以下、または１５以下の場合に適用でき、これより多い場合には一般的な高速アルゴリズムを使用しなければならない。このような適用が可能な理由は、ＭＰＥＧ２、ＭＰＥＧ４、Ｈ．２６１などの映像圧縮アルゴリズムで０でない値を有する元素の数が大部分１０以下であるからである。

もし、離散余弦変換行列において、０でない値を有する元素の数が１０であれば、元素別２次元逆離散余弦変換は次の式のようになる。

すなわち、一部値計算部６１は前記図４の元素検索部６１で検索された０でない値を有する元素値Ｔ（ｉ，ｊ）を代入した逆離散余弦変換式、すなわち数式１に前記検索された０でない値を有する元素の座標値ｉ，ｊを代入し、前記離散余弦変換行列に対して記逆離散余弦変換された復元行列の各元素の座標値ｘ、ｙを代入して前記復元行列の各元素の一部値ＩＤＣＴ（Ｔ（ｉ，ｊ））を算出する。完全値算出部６２は重畳の原理によって、元素検索部４１で検索された０でない値を有するあらゆる元素に対して、前記一部値算出部６１で算出された復元行列の各元素の一部値ＩＤＣＴ（Ｔ（ｉ，ｊ））を合せて、前記復元行列の各元素の完全値Ｖ（ｘ，ｙ）を算出する。

図７は本発明による高速逆離散余弦変換方法のフローチャートである。

まず、所定の圧縮ファイルに対する一連のデコーディング過程の一過程である、前記離散余弦変換行列の各元素に対して０でない値を有する元素を検索する前に行われるランレングスデコーディング過程で、０でない値を有する元素だけをカウントすることによって０でない値を有する元素の数を計算する（７０）。

まず、離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合（７１）、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する（７２）。ここで、前記０でない値を有する元素の数は所定の圧縮ファイルに対する一連のデコーディング過程のうち、逆離散余弦変換前に行われるランレングスデコーディング過程であらかじめ出力された値である。また、前記臨界値は、元素別に２次元逆離散余弦変換することが行列別に２次元逆離散余弦変換することより演算の量が減少する場合において、前記離散余弦変換行列の０でない値を有する元素の数が最大値になるように決定したものである。また、前記順序は第１行及び第１列に位置した元素を出発点としてジグザグ方向に各元素につながる順序をいう。

次いで、検索された０でない値を有する元素を２次元逆離散余弦変換する（７３）。すなわち、検索された０でない値を有する元素の値を代入した逆離散余弦変換式に検索された０でない値を有する元素の座標値を代入し、離散余弦変換行列に対して逆離散余弦変換された復元行列の各元素の座標値を代入して復元行列の各元素の一部値を算出する。次いで、重畳の原理によって、検索された０でない値を有するあらゆる元素に対して算出された復元行列の各元素の一部値を合せて前記復元行列の各元素の完全値を算出する。

次いで、離散余弦変換行列の０でない値を有する元素の数が臨界値を超過する場合（７１）、離散余弦変換行列を２次元逆離散余弦変換する（７４）。すなわち、Ｗａｎｇアルゴリズム、Ｃｈｅｎアルゴリズム、Ｌｅｅアルゴリズム、またはＡＡＮアルゴリズムのうちいずれか一つの高速逆離散余弦変換アルゴリズムを使用して２次元逆離散余弦変換する。

図８は、本発明による高速逆離散余弦変換の計算量と従来の高速逆離散余弦変換の計算量とを比較した比較表を示した図面である。

これは量子化スケールが大きい、制限的な範囲で実験した結果値である。前記のように、量子化スケールが小さな場合は既存の高速２次元離散余弦変換アルゴリズムを利用しなければならない。

一方、前述した本発明の実施例はコンピュータで実行できるプログラムで作成可能であり、コンピュータで読取れる記録媒体を利用して前記プログラムを動作させる汎用ディジタルコンピュータで具現できる。

前記コンピュータで読取れる記録媒体はマグネチック保存媒体（例えば、ＲＯＭ、フロッピー（登録商標）ディスク、ハードディスク等）、光学的判読媒体（例えば、ＣＤ−ＲＯＭ、ＤＶＤ等）及びキャリヤウェーブ（例えば、インターネットを通した伝送）などの保存媒体を含む。

今まで本発明についてその望ましい実施例を中心に説明した。当業者であれば本発明が本発明の本質的な特性から離脱しない範囲で変形された形態に具現されうることを理解できる。したがって、開示された実施例は限定的な観点でなく説明的な観点で考慮されねばならない。本発明の範囲は前述した説明ではなく特許請求の範囲に現れており、それと同等な範囲内にあるあらゆる差異点は本発明に含まれていると解釈されねばならない。

本発明は逆離散余弦変換に係り、ＭＰＥＧ−２、ＭＰＥＧ−４、Ｈ２６３、Ｈ．２６Ｌなど国際的標準によって圧縮されたデジタル形式のデータを復号化するシステムに用いられる。主に、圧縮された映像データを復号化して再生する映像再生装置に用いられる。

従来の２次元逆離散余弦変換の方向を示した図面である。従来の逆離散余弦変換アルゴリズムの計算量を比較した比較表を示した図面である。従来の高速逆離散余弦変換アルゴリズムのうち一つであるＷａｎｇアルゴリズムを示した図面である。本発明による高速逆離散余弦変換装置の構成図である。一般的な８×８離散余弦変換行列の一例を示した図面である。本発明による前記図４の元素別２次元逆離散余弦変換部の詳細構成図である。本発明による高速逆離散余弦変換方法のフローチャートである。本発明による高速逆離散余弦変換の計算量と従来の高速逆離散余弦変換の計算量とを比較した比較表を示した図面である。

符号の説明

４０有効元素数計算部
４１元素検索部
４２元素別２次元逆離散余弦変換部
４３行列別２次元逆離散余弦変換部

Claims

（ａ）所定の離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する段階と、
（ｂ）前記検索された０でない値を有する元素を２次元逆離散余弦変換する段階と、
（ｃ）前記離散余弦変換行列の０でない値を有する元素の数が前記臨界値を超過する場合、前記離散余弦変換行列を２次元逆離散余弦変換する段階と、を含むことを特徴とする高速逆離散余弦変換方法。
前記（ｂ）段階は、
前記検索された０でない値を有する元素の値を代入した逆離散余弦変換式に前記０でない値を有する元素の座標値を代入し、前記離散余弦変換行列に対して逆離散余弦変換された復元行列の各元素の座標値を代入して前記復元行列の各元素の一部値を算出する段階と、
前記検索された０でない値を有するあらゆる元素に対して、前記算出された復元行列の各元素の一部値を合せて前記復元行列の各元素の完全値を算出する段階と、を含むことを特徴とする請求項１に記載の高速逆離散余弦変換方法。
前記（ｃ）段階はＷａｎｇアルゴリズム、Ｃｈｅｎアルゴリズム、Ｌｅｅアルゴリズム、またはＡＡＮアルゴリズムのうちいずれか一つの高速逆離散余弦変換アルゴリズムを使用して２次元逆離散余弦変換することを特徴とする請求項１に記載の高速逆離散余弦変換方法。
（ａ−１）所定の圧縮ファイルに対する一連のデコーディング過程の一過程である、前記離散余弦変換行列の各元素に対して０でない値を有する元素を検索する前に行われるランレングスデコーディング過程で、０でない値を有する元素だけをカウントすることによって前記０でない値を有する元素の数を計算する段階を含むことを特徴とする請求項１に記載の高速逆離散余弦変換方法。
前記臨界値は、元素別に２次元逆離散余弦変換することが行列別に２次元逆離散余弦変換することより演算の量が減少する場合において、前記離散余弦変換行列の０でない値を有する元素の数が最大値になるように決定することを特徴とする請求項１に記載の高速逆離散余弦変換方法。
前記順序は第１行及び第１列に位置した元素を出発点としてジグザグ方向に各元素につながる順序であることを特徴とする請求項１に記載の高速逆離散余弦変換方法。
所定の離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する元素検索部と、
前記元素検索部で検索された０でない値を有する元素を２次元逆離散余弦変換する元素別２次元逆離散余弦変換部と、
前記離散余弦変換行列の０でない値を有する元素の数が前記臨界値を超過する場合、前記離散余弦変換行列を２次元逆離散余弦変換する行列別２次元逆離散余弦変換部と、を含むことを特徴とする高速逆離散余弦変換装置。
前記元素別２次元逆離散余弦変換部は、
前記元素検索部で検索された０でない値を有する元素の値を代入した逆離散余弦変換式に前記０でない値を有する元素の座標値を代入し、前記離散余弦変換行列に対して逆離散余弦変換された復元行列の各元素の座標値を代入して前記復元行列の各元素の一部値を算出する一部値算出部と、
前記元素検索部で検索された０でない値を有するあらゆる元素に対して、前記一部値算出部で算出された復元行列の各元素の一部値を合せて、前記復元行列の各元素の完全値を算出する完全値算出部と、を含むことを特徴とする請求項７に記載の高速逆離散余弦変換装置。
前記行列別２次元逆離散余弦変換部はＷａｎｇアルゴリズム、Ｃｈｅｎアルゴリズム、Ｌｅｅアルゴリズム、またはＡＡＮアルゴリズムのうちいずれか一つの高速逆離散余弦変換アルゴリズムを使用して２次元逆離散余弦変換することを特徴とする請求項７に記載の高速逆離散余弦変換装置。
所定の圧縮ファイルに対する一連のデコーディング過程の一過程である、前記離散余弦変換行列の各元素に対して０でない値を有する元素を検索する前に行われるランレングスデコーディング過程で、０でない値を有する元素だけをカウントすることによって前記０でない値を有する元素の数を計算する有効元素数計算部を含むことを特徴とする請求項７に記載の高速逆離散余弦変換方法。
前記臨界値は、元素別に２次元逆離散余弦変換することが行列別に２次元逆離散余弦変換することより演算の量が減少する場合において、前記離散余弦変換行列の０でない値を有する元素の数が最大値になるように決定することを特徴とする請求項７に記載の高速逆離散余弦変換装置。
前記順序は第１行及び第１列に位置した元素を出発点としてジグザグ方向に各元素につながる順序であることを特徴とする請求項７に記載の高速逆離散余弦変換装置。
（ａ）所定の離散余弦変換行列の０でない値を有する元素の数が所定の臨界値以下である場合、離散余弦変換行列の各元素に対して所定の順序で０でない値を有する元素を検索する段階と、
（ｂ）前記検索された０でない値を有する元素を２次元逆離散余弦変換する段階と、
（ｃ）前記離散余弦変換行列の０でない値を有する元素の数が前記臨界値を超過する場合、前記離散余弦変換行列を２次元逆離散余弦変換する段階と、を含むことを特徴とする高速逆離散余弦変換方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取れる記録媒体。