(57)【特許請求の範囲】
【請求項１】
スカラＸｉｊ（ｉ，ｊ＝０，１，２，・・・，Ｎ−１｝とＹｉｊの各カラムをベクトルＸｉ＝｛Ｘｉ０，Ｘｉ１，・・・，Ｘｉ（Ｎ−１）｝とベクトルＹｉ＝｛Ｙｉ０，Ｙｉ１，・・・，Ｙｉ（Ｎ−１）｝に定義する過程と、
【数１】
0003816213.tif 000015
をスカラレジスタに貯蔵する過程と、
前記Ｘｉ＝｛Ｘｉ０，Ｘｉ１，・・・，Ｘｉ（Ｎ−１）｝をベクトルレジスタに貯蔵する過程と、
前記スカラレジスタとベクトルレジスタに貯蔵された値を読み出して、
【数２】
0003816213.tif 000016
によってスカラ−ベクトル乗算及びベクトル−ベクトル加算を並列処理してＹｉ＝｛Ｙｉ０，Ｙｉ１，・・・，Ｙｉ（Ｎ−１）｝を求める過程と、
前述の過程をＮ回繰り返して第１方向の１次元ＩＤＣＴを行って第１方向１次元ＩＤＣＴ値を求める段階と、
前記求められた第１方向１次元ＩＤＣＴ値の転置行列を求める段階と、
前記転置行列に対して前記第１方向１次元ＩＤＣＴと同一の過程を経て値を求め、求められた値の転置行列を求めて第２方向の１次元ＩＤＣＴを求めて最終２次元ＩＤＣＴ値を求める段階とを備え、
ここで、
前記スカラ−ベクトル乗算及びベクトル−ベクトル加算は前記
【数３】
0003816213.tif 000017
の偶数カラムの対称性を用いて、
第１行はＡ１＝cos4θ×（Ｘ０＋Ｘ４）＋cos2θ×Ｘ２＋cos6θ×Ｘ６
Ａ２＝cosθ×Ｘ１＋cos3θ×Ｘ３＋cos5θ×Ｘ5＋cos7θ×Ｘ７
第２行はＢ１＝cos4θ×（Ｘ０−Ｘ４）＋cos6θ×Ｘ２＋cos2θ×Ｘ6
Ｂ２＝cos3θ×Ｘ１−cos7θ×Ｘ３−cosθ×Ｘ５−cos5θ×Ｘ７
第３行はＣ１＝cos4θ×（Ｘ０−Ｘ４）−cos6θ×Ｘ２＋cos2θ×Ｘ6
Ｃ２＝cos5θ×Ｘ１−cosθ×Ｘ3＋cos7θ×Ｘ5＋cos3θ×Ｘ７
第４行はＤ１＝cos4θ×（Ｘ０＋Ｘ４）−cos2θ×Ｘ２−cos6θ×Ｘ６
Ｄ2＝cos7θ×Ｘ1−cos5θ×Ｘ3＋cos3θ×Ｘ５−cosθ×Ｘ７
に整理し、
Ｙ０＝Ａ１＋Ａ２、Ｙ1＝Ｂ１＋Ｂ２、Ｙ２＝Ｃ１＋Ｃ２、Ｙ３＝Ｄ１＋Ｄ２、Ｙ４＝Ｄ１−Ｄ２、Ｙ５＝Ｃ１−Ｃ２、Ｙ６＝Ｂ１−Ｂ２、Ｙ７＝Ａ１−Ａ２によってベクトルＹｉ＝｛Ｙｉ０，Ｙｉ１，・・・，Ｙｉ（Ｎ−１）｝を求め、
前記Ｘ０＋Ｘ４とＸ０−Ｘ４は予め求めて計算し、
前記乗算及び加算は固定小数点方式の１６ビットプロセッサで処理するが、前記求められた第１方向１次元ＩＤＣＴ値は右側に１１ビット移動させた後第２方向１次元ＩＤＣＴに伝達し、第２方向１次元ＩＤＣＴでは計算結果を右側に１９ビット移動させて最終２次元ＩＤＣＴ値を求めることを特徴とする２次元逆離散余弦変換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は逆離散余弦変換(ＩＤＣＴ:Inverse Discrete Cosine Transform)方法に係り、特に国際標準化されたビット正確度(bit accuracy)を満足しながら計算量を減らすことのできるＩＤＣＴ方法に関する。
【０００２】
【従来の技術】
画像の画素間相関性を用いたデータ圧縮技法としてＤＣＴが広く用いられている。このＤＣＴ方式はＭＰＥＧ，ＪＰＥＧ，Ｈ.２６１など国際標準規格に採用されている。従って、ＤＣＴ方式を用いて圧縮された画像データを受信する受信装置ではＤＣＴ方式で圧縮された情報を逆変換するためのＩＤＣＴが要求される。ＩＤＣＴには多くの乗算と加減算が要求されるので、演算処理の高速化に対する研究が行われている。
【０００３】
ＩＤＣＴの遂行にかかる計算量と時間を減らすために多くの技術が用いられている。その一つがＪ.Ｙａｎｇによって発表された“An Efficient Two-Dimensional Inverse Discrete Cosine Transform Algorithm for HDTV Receivers”（IEEE Trans. Circuits and Systems for Video Technology, Vol.5, No.1,Feb.1995）に開示されている。しかし、Ｙａｎｇによって開示された基本演算はベクトル化(Vectorization)が容易でないので、並列処理(parallel processing)が難しく、計算量が多いという問題点がある。
【０００４】
他の技術ではＮ.Ｄｅｍａｓｓｉｅｕｘ及びＦ.Ｊｕｔａｎｄの“Orthogonal Transforms in VLSI Implementations for Image Communications”(Edited by P.Pirsch, Elsevier Science Publishers, The Netherlands, 1993)に開示されている。高速アルゴリズムによるバタフライチェーン(Butterfly chain based fast algorithm)は多くの乗算動作によってビット正確度を低下させ、前述の国際標準を満足させ難い。
【０００５】
通常、ＩＤＣＴで用いられるコサイン値のために、ＩＤＣＴは浮動小数点プロセッサを用いて処理している。高速処理を行うためには高性能のプロセッサを必要とするので、これにより受信装置のコストを上昇させる要因となる。
【０００６】
２次元ＩＤＣＴは数式で整理すると、次のようである。
【０００７】
【数８】
0003816213.tif 000002
となり、前記式（１）は次の数式（２）のように行列式で表現することができる。
【０００８】
［ｆ］＝［Ｃ］T［Ｆ]［Ｃ]                         ・・・・（２）
ここで、転置行列は垂直方向への１次元ＩＤＣＴに該当し、行列Ｃは水平方向への１次元ＩＤＣＴに該当する。従って、２次元ＩＤＣＴのためには水平及び垂直の両方向に計算処理されるべきであるが、一般的なベクトルプロセッサでは一方向にのみ並列処理が可能であるため、両方向作動のベクトル化は困難である。
【０００９】
【発明が解決しようとする課題】
従って、本発明の目的は、かかる従来の技術の問題点を解決するために、計算量を減らし且つ国際標準のビット正確度を満足させることができるＩＤＣＴ方法を提供することにある。
【００１０】
【課題を解決するための手段】
上記目的を達成するために、第１の発明としての、圧縮した画像データに対する逆離散余弦変換方法は、
【数９】
0003816213.tif 000003
によってＮ×Ｎ ＤＣＴデータ Ｘijを１次元ＩＤＣＴするに際し、前記スカラＸijとＹijの各カラムをベクトルＸi＝｛Ｘi0，Ｘi1，・・・，Ｘi(N-1)｝とベクトルＹi＝｛Ｙi0，Ｙi1，・・・，Ｙi(N-1)｝に定義する段階と、
【数１０】
0003816213.tif 000004
をスカラレジスタに貯蔵する段階と、前記ベクトルＸi＝｛Ｘi0，Ｘi1，・・・，Ｘi(N-1)｝をベクトルレジスタに貯蔵する段階と、前記スカラレジスタとベクトルレジスタに貯蔵された値を読み出して、
【数１１】
0003816213.tif 000005
によってスカラ-ベクトル乗算及びベクトル-ベクトル加算を並列処理してＹi＝｛Ｙi0，Ｙi1，・・・，Ｙi(N-1)｝を求める段階と、及び前記段階をＮ回繰り返し行う段階とを備えることを特徴とする。
【００１１】
尚、第２の発明としての、圧縮した画像データに対する逆離散余弦変換方法は、スカラＸij（ｉ，ｊ＝０，１，２，・・・，Ｎ−１｝とＹijの各カラムをベクトルＸi＝｛Ｘi0，Ｘi1，・・・，Ｘi(N-1)｝とベクトルＹi＝｛Ｙi0，Ｙi1，・・・，Ｙi(N-1)｝に定義する過程と、
【数１２】
0003816213.tif 000006
をスカラレジスタに貯蔵する過程と、前記Ｘi＝｛Ｘi0，Ｘi1，・・・，Ｘi(N-1)｝をベクトルレジスタに貯蔵する過程と、前記スカラレジスタとベクトルレジスタに貯蔵された値を読み出して、
【数１３】
0003816213.tif 000007
によってスカラ-ベクトル乗算及びベクトル-ベクトル加算を並列処理してＹi＝｛Ｙi0，Ｙi1，・・・，Ｙi(N-1)｝を求める過程と、前述の過程をＮ回繰り返して第１方向の１次元ＩＤＣＴを行って第１方向１次元ＩＤＣＴ値を求める段階と、前記求められた第１方向１次元ＩＤＣＴ値の転置行列を求める段階と、前記転置行列に対して前記第１方向１次元ＩＤＣＴと同一の過程を経て値を求め、求められた値の転置行列を求めて第２方向の１次元ＩＤＣＴを求めて最終２次元ＩＤＣＴ値を求める段階とを備えることを特徴とする。
【００１２】
【発明の実施の形態】
以下、添付図面を参照して本発明の一実施形態をより詳しく説明する。
【００１３】
図１は８×８ＤＣＴ係数ブロックと８×８ピクセルブロックを示す。８×８１次元ＩＤＣＴは行列式で表現すると、次の式（３）の通りである。
【００１４】
［Ｙ］＝［Ｃ］［Ｘ］                ・・・（３）
前記式（３）をθ＝π／１６とし、８×８ＤＣＴ係数Ｘijに対して具体的に表現すると、次の式（４）の通りである。
【００１５】
【数１４】
0003816213.tif 000008
従って、本発明では１６ビット固定小数点プロセッサで２次元ＩＤＣＴを行うために、次のような３種類の改善案を提示する。
【００１６】
まず第１に、２次元ＩＤＣＴをベクトル演算によって並列処理するために、前記式（３）を次の式（５）に変換させる。
【００１７】
0003816213.tif 000009
式（５）は垂直方向の１次元ＩＤＣＴを行い、その結果を転置行列にして再び垂直方向の１次元ＩＤＣＴを行った後その結果を転置させることにより、２次元ＩＤＣＴを行うことが可能になる。即ち、一方向である垂直方向にのみＩＤＣＴを行うことができるので、全並列（ｆｕｌｌ-ｐａｒａｌｌｅｌ）処理が可能であって全ベクトル化が可能になる。より具体的に説明すると、Ｎ×ＮのＸが入力される場合、１次元ＩＤＣＴは式（６）で表現される。
【００１８】
【数１５】
0003816213.tif 000010
ここで、Ｘ，Ｙ，Ｃはスカラ値なので、式（６）による１次元ＩＤＣＴを遂行するためにはＮ3回の乗算とＮ2（Ｎ−１）回の加算が必要であることが分かる。しかし、本発明によるベクトル-並列処理を適用してスカラＸijとＹijの各カラムをベクトルＸi＝｛Ｘi0，Ｘi1，・・・，Ｘi(N-1)｝とベクトルＹｉ＝｛Ｙi0，Ｙi1，・・・，Ｙi(N-1)｝に定義すると、次の式（７）のように表現することができる。
【００１９】
【数１６】
0003816213.tif 000011
をスカラレジスタに貯蔵させ、前記ベクトルＸi＝｛Ｘi0，Ｘi1，・・・，Ｘi(N-1)｝をベクトルレジスタに貯蔵させた後式（７）によって計算すると、Ｎ2回のスカラ-ベクトル乗算及びＮ（Ｎ−１）回のベクトル-ベクトル加算によって式（６）に対応する同一結果を得ることができる。従って、本発明では一方向に２次元ＩＤＣＴを行うことにより全ベクトル化が可能なので、全体的な計算回数を大幅に減らすことができる。
【００２０】
次に第２に、前記スカラ-ベクトル乗算及びベクトル-ベクトル加算は前記式（４）に示すように、
【数１７】
0003816213.tif 000012
の偶数カラムの対称性を用いて、
0003816213.tif 000013
に整理し、
Ｙ0＝Ａ1＋Ａ2、
Ｙ1＝Ｂ1＋Ｂ2、
Ｙ2＝Ｃ1＋Ｃ2、
Ｙ3＝Ｄ1＋Ｄ2、
Ｙ4＝Ｄ1−Ｄ2、
Ｙ5＝Ｃ1−Ｃ2、
Ｙ6＝Ｂ1−Ｂ2、
Ｙ7＝Ａ1−Ａ2、
によってベクトルＹi＝｛Ｙi0，Ｙi1，・・・，Ｙi(N-1)｝を求める。前記Ｘ0＋Ｘ4とＸ0−Ｘ4は予め求めて計算することが好ましい。このような対称性を用いると、乗算がＮ2／２回、加算が（Ｎ（Ｎ−１））／２回に減るので、式（７）に関連して説明した計算と比較すると約半分に計算量が減少する。
【００２１】
第３に、前記第２の段階で１６ビット乗算から求められる３２ビットのＡ1，Ａ2，・・・Ｄ1，Ｄ2を加算及び減算したい場合に、１６ビットに直した後計算しなければならないため小数点以下は全て切り捨てることになり、よって、次の１次元ＩＤＣＴにエラーが累積して国際標準で定めておいたビット正確度を満足しない。国際標準とは浮動小数点ＩＤＣＴの結果と提案された固定小数点ＩＤＣＴの結果との間のエラーに対する最大制限値を定めておくことをいう。従って、本発明ではこの国際標準を満足させるために適切なダイナミック範囲を定める。
【００２２】
元より固定小数点プロセッサで浮動小数点計算をするためには、まず浮動小数点値を適当なビットだけ左側移動させて整数値に変換させた後所望の計算を行ってからその結果を再び右側移動させることにより、最終の結果が得られる。
【００２３】
例えば、０.３７５×６の計算による整数部分を得ようとする場合には次のように計算することができる。
【００２４】
0003816213.tif 000014
この計算において、≪３は左側に３ビット移動、≫３は右側に３ビット移動を意味する。前記計算で小数点以下を四捨五入(round-up)したいなら、右側移動する前に適切な位置で行うことができる。
【００２５】
このような方式を用いてまず１次元ＩＤＣＴの浮動小数点値のコサイン値を左側に１５ビット移動させて整数化した後、計算によって得られた３２ビットの結果を再び１５ビット右側移動させることにより、所望する１６ビットの結果を得る。２次元ＩＤＣＴを行うためにはこのような計算が２回繰り返されるところを、従来では第１のＩＤＣＴ過程で小数点以下は全て切り捨てるので、第２のＩＤＣＴ過程でエラーが累積して所望のビット正確度を得ることができなかった。結局、所望のビット正確度を満足させるためには３２ビットプロセッサが必要であるということなので、これはＩＤＣＴのコストを上昇させる問題点がある。本発明では１６ビット固定小数点プロセッサで前述の問題点を解決しようとする。
【００２６】
つまり、本発明では、図２に示すように求められた第１方向１次元ＩＤＣＴ値は左側に１１ビット移動させた後第２方向１次元ＩＤＣＴに伝達し、第２方向１次元ＩＤＣＴでは計算結果を右側に１９ビット移動させて最終２次元ＩＤＣＴ値を求める。なぜなら、ＩＤＣＴ係数の特性上、ＤＣＴデータを１次元ＩＤＣＴした結果の最大値は１２ビットを超えないので、全体１６ビット中の上位４ビットは何の意味もない。従って、上位４ビットの代わりに小数点以下の４ビットを保つことにより、２次元ＩＤＣＴにおいてエラーを減らすことができる。
【００２７】
【発明の効果】
以上説明したように、本発明では２次元ＩＤＣＴを１６ビット固定小数点プロセッサによって行うことができるようにするため、全ベクトル化によって並列処理し、コサイン行列の対称性を用いて計算量を大幅に減らし且つ国際標準のビット正確度を満足させることにより、ＩＤＣＴ処理装置のコストを節減することができる。
【図面の簡単な説明】
【図１】８×８ＤＣＴ係数ブロックと８×８ピクセルブロックを示す図である。
【図２】本発明による１６ビット固定小数点プロセッサでＩＤＣＴを処理する方法を説明するための図である。
【図１】
0003816213.tif 000018
【図２】
0003816213.tif 000019