(57)【特許請求の範囲】
【請求項１】
４n（ｎは２以上の整数）個の整数データで構成されるブロックから、当該ブロックに対する可逆変換可能な整数変換係数のうちＤＣ係数を算出するデータ変換装置であって、
前記ブロックを予め設定された４個のデータで構成されるサブブロックに区分し、サブブロック毎に、それぞれのサブブロックを構成する４個のデータの総和値が偶数か奇数かを表わす０又は１のいずれかの値を持つパリティを生成するパリティ生成手段と、
前記ブロックを構成する全てのデータが示す値の総和値を算出する総和演算手段と、
該総和演算手段で算出した総和値と、前記パリティ生成部で算出された各サブブロックのパリティの値とを加算する加算手段と、
該加算手段で得られた値から、前記ブロックに対する可逆な整数のＤＣ係数データを演算するＤＣ係数演算手段と
を備えることを特徴とするデータ変換装置。
【請求項２】
同じ位のビット間の論理積演算子を「＆」、排他的論理和の演算子を「＾」、着目しているサブブロックを構成する４つのデータをData[0], Data[1], Data[2], Data[3]と表わしたとき、
前記パリティ生成手段は、前記着目しているサブブロックのパリティＰを、
Ｐ ＝ (Data[0] ＆ 1) ＾ (Data[1] ＆ 1) ＾ (Data[2] ＆ 1) ＾ (Data[3] ＆ 1)
として算出する回路を有することを特徴とする請求項１に記載のデータ変換装置。
【請求項３】
前記ＤＣ係数演算手段は、前記加算手段による加算結果の値をビットシフトし、当該ビットシフトで得られたデータを前記係数ブロックの可逆変換のＤＣ係数データとして出力することを特徴とする請求項１又は２に記載のデータ変換装置。
【請求項４】
ｎ＝２とする請求項１に記載のデータ変換装置を２つ有し、１つ目のデータ変換装置で算出されたＤＣ係数を４×４個を集めてブロックを構成し、２つ目のデータ変換装置で前記ブロックのデータ変換を行うことで、マクロブロックＤＣ係数を算出することを特徴とするデータ変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの圧縮符号化技術に関するものであり、特に、実空間ブロック整数データから周波数空間ブロック整数データへの可逆な変換における直流成分係数への変換技術に関するものである。
【背景技術】
【０００２】
静止画像の国際標準符号化方式として、ＩＳＯとＩＴＵ−Ｔにより勧告されたＪＥＰＧがある。ＪＥＰＧでは、画像データを８×８画素のブロック単位に分割し、該ブロックに８×８サイズの離散コサイン変換を適用して、周波数空間上の係数データに変換する。そして、該係数データを量子化し、該量子化したデータをエントロピー符号化して画像データの非可逆な圧縮を行なう。
【０００３】
ここで、上記の量子化における量子化ステップの大小の制御によって圧縮率を調整することができる。量子化によって失われた情報は復元することは出来ないが、視覚的に目立ちにくい部分から情報を削ることによって、それ以前の符号化よりも大幅に画像データを圧縮することができる。
【０００４】
ＪＰＥＧ符号化方式において、量子化ステップを“１”に設定して量子化を行なうとする。この場合、ＤＣＴという正規直交変換の性質から、ブロック内の実空間上のデータの二乗和と、周波数空間上の係数データの二乗和が等しくなり、変換によって信号パワーが失われることなく保存される。しかし、情報的には欠損を生じるため、係数データを逆変換しても元のデータを完全に復元することが出来ない。これは、量子化ステップを“１”に設定して量子化したとしても、可逆符号化を行なうことが出来ないことを意味する。よって、ＪＰＥＧでは、ＤＣＴとは全く異なる隣接画素間の予測差分に対するエントロピー符号化という、別の符号化プロセスを定めることで、この可逆符号化を実現している。
【０００５】
ＪＰＥＧの次に定められた静止画像の国際標準符号化方式であるＪＰＥＧ２０００では非可逆圧縮用のウェーブレット変換と可逆圧縮用のウェーブレット変換の２種類を用意して、非可逆圧縮と可逆圧縮に対応させた。変換より後の符号化プロセスは非可逆圧縮と可逆圧縮で共通化されたが、変換までは共通化されていない。
【０００６】
さらにその後、国際標準符号化方式として定められたＪＰＥＧ‐ＸＲでは、後に示す非特許文献１に記載されているラダー演算（リフティング演算）を用いることにより、非可逆圧縮と可逆圧縮に共通する整数データから整数係数への可逆な変換を定めている。これによって、符号化プロセス全てを非可逆圧縮と可逆圧縮で共通化することが可能になった。
【０００７】
ＪＰＥＧ‐ＸＲでは、４×４画素サイズのブロック、１６×１６画素サイズのマクロブロック、それより大きなタイルを定義しており、タイル単位で符号化を行なう。また、実空間から周波数空間への変換は次のように階層的に行なっている。
【０００８】
図１（Ａ）に示す４×４画素サイズのブロックを、それぞれが図１（Ｂ）乃至（Ｅ）に示す４画素で構成されるサブブロックに区分する。そしてそれぞれのサブブロックに対して整数係数への可逆なアダマール変換（以下、整数可逆アダマール変換と称す）を適用して、４つの係数に変換する。
【０００９】
更に、４つのサブブロックそれぞれの同一レベルの変換係数を集めて、４組の変換係数群を形成し、それに対し、さらに変換を適用する。すなわち、サブブロックの直流成分係数（ＤＣ係数）を４つ集めた組に対しては、再度、整数可逆アダマール変換が適用され、ブロック単位のＤＣ係数（ブロックＤＣ係数）と３つの非直流係数（ＡＣ係数）が生成される。その他の３つの組に対しては、各々４つのデータを２×２データと見なし、それを２軸方向から回転変換する変換を適用してＡＣ係数に変換される。この段階で得られるＡＣ係数はＨＰ係数に分類される。結局、１つのブロックデータ（４×４画素データ）は、１個のブロックＤＣ係数と、１５個のＨＰ係数に変換されることになる。
【００１０】
該ブロックＤＣ係数は、マクロブロックを構成する１６個のブロックから集められ４×４のブロックＤＣ係数データに対して、上記と同様のブロック変換が再び適用される。該変換によって得られるＡＣ係数はＬＰ係数に分類され、この変換で得られる直流成分係数はマクロブロックのＤＣ成分を表し、これが最終的なＤＣ係数に分類される。本明細書では該ＤＣ係数を、前述のブロックＤＣ係数と混同しないようにマクロブロックＤＣ係数と呼んで区別する。
【００１１】
ＪＰＥＧ‐ＸＲの符号化モードには、Ｓｐａｔｉａｌ  Ｍｏｄｅと、Ｆｒｅｑｕｅｎｃｙ   Ｍｏｄｅとがある。Ｆｒｅｑｕｅｎｃｙ  Ｍｏｄｅでは、タイル内の全てのマクロブロックＤＣ係数を符号化処理した後に、タイル内の全てのＬＰ係数、続いてＨＰ係数の順に符号化処理して符号化ストリームを形成する。
【００１２】
リフティング演算を用いて演算する整数可逆変換では、入力データを相互に逐次的に更新して変換してくため、ブロックＤＣ係数を生成する際に、ＡＣ係数も同時に生成するのが一般的であり、その方が効率よく変換できる。しかし、ブロックＤＣ係数のみを残し、ＡＣ係数または途中の演算結果を一切保存せずに消し去ったりすると、変換処理の効率が著しく低下する。ＪＰＥＧ‐ＸＲで採用されている各種リフティング演算は、特許文献１に詳細に記載されているが、やはり、ＤＣ係数とＡＣ係数を同時に生成することがその前提になっている。
【００１３】
よって、１つのマクロブロックＤＣ係数を生成した時点で、通常は１５個のＬＰ係数と２４０個（＝１５係数×１６ブロック）のＨＰ係数が同時に生成される。これらＬＰ係数やＨＰ係数を、廃棄すると極端に変換処理の効率が悪くなるため、メモリやバッファ等に一時的に保存しておく必要がある。
【００１４】
ここで言う「バッファ」は圧縮符号化等の機能を実装したＬＳＩ（大規模集積回路）の内部に持つ小容量の記憶部、「メモリ」は比較的容量の大きな汎用メモリをさす。該汎用メモリは前記ＬＳＩに接続し大容量記憶部として使われる。
【００１５】
前記ＬＰ係数、ＨＰ係数の保存先は、機器によって異なる。どちらの係数もメモリに保存する場合もあれば、ＬＰ係数をバッファへＨＰ係数をメモリへ保存する場合もある。いずれにしても、データ量の多い係数ほど容量の大きなメモリへ保存する可能性が高い。
【００１６】
前記Ｆｒｅｑｕｅｎｃｙ  Ｍｏｄｅでは、タイル内の複数のマクロブロックＤＣ係数を続けて符号化し、それに対応する大量のＨＰ係数やＬＰ係数が生成されるため、これらは、基本的に「メモリ」へ保存される。また、メモリへ保存した係数データは、実際に符号化処理するタイミングで読み出して、前記ＬＳＩへ供給する必要がある。このようなメモリへの保存や読み出しは、メモリアクセス帯域が増加することを意味する。そこでメモリアクセス回数の概算を以下に示す。
【００１７】
今、仮に、符号化処理すべき画像データがメモリに保存されていたとすると、周波数空間上の係数データへの変換処理で画像データを１回読み出す必要がある。
【００１８】
該変換処理で生成したＬＰ係数とＨＰ係数の両方をメモリに保存する場合、２５６個の画素データ当たり２５５個の係数を保存することになるため、平均して２５５／２５６回≒１回の書き込みを行なう必要がある。保存した係数データは後に符号化処理するために必ず読み出すわけであるから、該係数データの読み出し回数は前記書き込み回数と同等である。結局、元の画像データからカウントすると計３回の読み出し又は書き込みを行なう必要がある。
【００１９】
Ｆｒｅｑｕｅｎｃｙ  Ｍｏｄｅでは無くＳｐａｔｉａｌ  Ｍｏｄｅの場合、マクロブロック単位でＤＣ係数、ＬＰ係数とＨＰ係数の順に符号化する。この場合には、１マクロブロック分の係数を保持するだけでよいため、ＬＳＩ内部のバッファで係数データを保持することが可能である。よって、前記メモリからの画像データの読み出しは１回だけで済む。比較するとＦｒｅｑｕｅｎｃｙ  Ｍｏｄｅは、Ｓｐａｔｉａｌ  Ｍｏｄｅの３倍のメモリアクセス量になる。
【００２０】
前述のように、ＬＰ係数・ＨＰ係数を廃棄すると、変換処理の効率が極端に悪くなるため、生成したＬＰ係数・ＨＰ係数は一時保存しておく必要があるが、メモリに保存するとメモリアクセス量が増大してしまう。もし、ブロックＤＣ係数のみの生成を簡易に実現できれば、同時にＨＰ係数を生成する必要が無くなり、その結果、ＨＰ係数を廃棄したり、一時保存することも必要無くなる。マクロブロックＤＣ係数を生成する際のＬＰ係数の生成に関しても同様のことが言える。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００６−１９７５７２号公報
【非特許文献】
【００２２】
【非特許文献１】Ｆ．Ｂｒｕｅｋｅｒｓ  ａｎｄ  Ａ．Ｅｎｄｅｎ，“Ｎｅｗ  Ｎｅｔｗｏｒｋｓ  ｆｏｒ  Ｐｅｒｆｅｃｔ  Ｉｎｖｅｒｓｉｏｎ  ａｎｄ  Ｐｅｒｆｅｃｔ  Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ”ＩＥＥＥ  ＪＳＡＣ，ｖｏｌ．１０，ｎｏ．１．ｐｐ．１３０−１３７，Ｊａｎ  １９９２
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上記の通り、これまでの整数可逆ブロック変換を実現する従来の演算装置では、演算を効率よく行なうために、ＤＣ係数とＡＣ係数を合せて生成する必要があった。そのＡＣ係数を直ちに符号化しないモードでは、該ＡＣ係数をメモリ等に一時保存する必要があり、これがメモリアクセス回数を増大させるという新たな問題を引き起こしていた。
【００２４】
本発明は、２次元配列の係数ブロックから、簡単な構成で、その係数ブロックの可逆変換ＤＣ係数データを算出する技術を提供しようとするものである。
【課題を解決するための手段】
【００２５】
この課題を解決するため、例えば本発明のデータ変換装置は以下の構成を備える。すなわち、
４n（ｎは２以上の整数）個の整数データで構成されるブロックから、当該ブロックに対する可逆変換可能な整数変換係数のうちＤＣ係数を算出するデータ変換装置であって、
前記ブロックを予め設定された４個のデータで構成されるサブブロックに区分し、サブブロック毎に、それぞれのサブブロックを構成する４個のデータの総和値が偶数か奇数かを表わす０又は１のいずれかの値を持つパリティを生成するパリティ生成手段と、
前記ブロックを構成する全てのデータが示す値の総和値を算出する総和演算手段と、
該総和演算手段で算出した総和値と、前記パリティ生成部で算出された各サブブロックのパリティの値とを加算する加算手段と、
該加算手段で得られた値から、前記ブロックに対する可逆な整数のＤＣ係数データを演算するＤＣ係数演算手段とを備える。
【発明の効果】
【００２６】
本発明によれば、格段に小さな回路規模で、整数可逆変換のＤＣ係数を生成することが可能になる。
【００２７】
該演算装置をＤＣ係数の専用生成回路として、符号化装置内に設けることにより、ＬＰ係数・ＨＰ係数を生成すること無く、ＤＣ係数を簡易に生成でき、ＬＰ係数・ＨＰ係数をメモリへ保存する必要が無くなる。よって、ＬＰ係数・ＨＰ係数のメモリ書き込みが不要になった分だけ、メモリアクセス回数を削減することができる。
【図面の簡単な説明】
【００２８】
【図１】ブロックと４つのサブブロックの関係を示す図。
【図２】本発明の適用に好適な符号化装置の構成を表す図。
【図３】パリティ生成部の構成を表す図。
【図４】本発明の第１の実施形態であるＤＣ係数演算装置の構成を表す図。
【図５】本発明の第２の実施形態であるＤＣ係数演算装置の構成を表す図。
【図６】本発明の第３の実施形態であるＤＣ係数演算装置の構成の例を表す図。
【図７】本発明の第４の実施形態であるＤＣ係数演算装置の構成を表す図。
【発明を実施するための形態】
【００２９】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。なお、本実施形態において、本発明のデータ変換装置をＪＰＥＧ  ＸＲに適用した例を説明する。
【００３０】
符号化対象のマクロブロックＤＣ係数データを生成するには、それ以前にこのマクロブロックを構成する１６個のブロックにおけるブロックＤＣ係数データを生成する必要がある。Ｆｒｅｑｕｅｎｃｙ  Ｍｏｄｅでは、該ブロックＤＣ係数データを生成する時に、同時にＨＰ係数を生成すると、その係数データは膨大な量になるため、メモリ等に一時保存するか、あるいは廃棄する必要がある。前述したように、これは大変効率の悪い処理である。
【００３１】
そこで、本発明を前提にした符号化処理手順を以下の１〜９に示し、該処理手順を実現可能な符号化装置の構成を図２に示す。図２に示すように、この符号化装置は、第１の変換部３０１、セレクタ３０２、第２の変換部３０４、第３の変換部３０３、メモリ制御部３０５、画像記憶部３０６、セレクタ３０７、階層制御部３０８、係数符号化部３１０を有する。この符号化装置において、各処理手順を以下に示す。また、各処理手順がどの構成要素で処理されるのかを右矢印（→）の右側に記す。
１．ブロックＤＣ係数データを生成（→第１の変換部３０１）
２．生成したブロックＤＣ係数データを一時保存（→バッファ３０９）
３．４×４個のブロックＤＣ係数データからマクロブロックＤＣ係数データを生成（→第３の変換部３０３）
４．マクロブロックＤＣ係数データを符号化（→係数符号化部３１０）
（これら１〜４をタイル内の全データに対して行なう）
５．４×４個のブロックＤＣ係数データをブロック変換してＬＰ係数を生成（→第２の変換部３０４）
６．ＬＰ係数データを符号化（→係数符号化部３１０）
（５と６をタイル内の全ブロックＤＣ係数に対して行なう）
７．画像データにブロック変換を行ない、ＨＰ係数データを生成（→第２の変換部３０４）
８．ＨＰ係数データを符号化（→係数符号化部３１０）
（７と８をタイル内の全画像データに対して行なう）
９．次に符号化すべきタイル画像データに上記手順１〜８を適用
【００３２】
通常、ブロックＤＣ係数データとＨＰ係数データは、画像データのブロック変換（周波数変換）によって同時に生成する。また、マクロブロックＤＣ係数データとＬＰ係数データも、前記ブロックＤＣ係数データのブロック変換によって同時に生成する。それに対し、上記処理フローでは、ブロックＤＣ係数データ、或いは、マクロブロックＤＣ係数データのみを、本実施形態基づく独自の方法、すなわち、サブブロック単位で計算するパリティを利用した演算によって生成する。
【００３３】
以下では、第１の実施形態で、ブロックに対する可逆変換可能な整数変換係数のうちＤＣ係数データのみの生成方法を示し、第２以降の実施形態で、マクロブロックＤＣ係数データの生成方法を示す。
【００３４】
ＪＰＥＧ−ＸＲ勧告書に記載されたブロック変換のＤＣ係数データは、既に説明したように、図１（Ａ）に示す４×４個の整数データを、図１（Ｂ）乃至（Ｅ）に示す４つのサブブロックに区分して、以下のように変換処理することによって生成できる。
【００３５】
まず、４つのサブブロックそれぞれに対し１段目の整数可逆アダマール変換を行なうことで、４つのサブブロックＤＣ係数データを得る。そして、その４つのサブブロックＤＣ係数データに対して、２段目の整数可逆アダマール変換を行なう。この２段目の整数可逆アダマール変換のＤＣ係数データが、前記ブロックＤＣ係数である。
【００３６】
１つのサブブロック（図１（Ｂ）乃至（Ｅ）のいずれか）に着目したとき、そのサブブロック内のデータの総和値が偶数であるなら、その総和値を２で割った値と、そのサブブロックのサブブロックＤＣ係数データが示す値は等しい。つまり、着目サブブロックに対する、１段目の整数可逆アダマール変換では丸め誤差が発生しない。
【００３７】
一方、着目サブブロックにおけるデータの総和値が奇数の場合、その総和値を２で割った値には、０．５の小数データが付く。この小数点を切り上げた値が、ＪＰＥＧ−ＸＲと互換性のある整数のサブブロックＤＣ係数データの値になる。この場合、＋０．５の丸め誤差が発生する。総和値が奇数のサブブロック毎に＋０．５の丸め誤差が発生し、それが２段目のアダマール変換へ入力される。
【００３８】
一方、ＪＰＥＧやＭＰＥＧにおけるＤＣＴ（離散コサイン変換）のような線形直交変換であれば、ブロック（４×４サイズ）内の全データの総和値を求め、これを１／４倍するだけで線形変換ＤＣ係数を演算することができる。該全データの総和値はデータの入力順序を気にせず、入力されたデータを順に加算するだけで演算でき、単純な構成で線形変換ＤＣ係数を生成できる。
【００３９】
［第１の実施形態：行方向の４データの並列入力する場合］
そこで、本第１の実施形態では、ブロック内全データの総和値をベースに、整数可逆変換のブロックＤＣ係数を演算可能な演算装置を開示する。該演算装置によれば、単純な構成で前記ブロックＤＣ係数を生成可能になる。以下に説明するブロックＤＣ係数演算装置は、図２における第１の変換部３０１、第３の変換部３０３に適用されるものでもある。
【００４０】
まず、本第１の実施形態の大きな特徴である、サブブロック単位のパリティの計算方法とパリティ生成部の構成を先に示し、その後に、該パリティ生成部を用いたブロックＤＣ係数演算装置の構成を示す。
【００４１】
先に示した２段目のアダマール変換へ入力される４つのデータの和は、線形変換におけるブロック内データの総和値より、サブブロック毎に発生する丸め誤差の分だけ大きい。よって、ブロック内データの総和値へ、各サブブロックの整数可逆アダマール変換の丸め誤差を正確に加算できれば、２段目のアダマール変換へ入力される４つのデータの和を計算することができる。
【００４２】
ここで、前述したように、ブロック内データの総和値はデータの入力順序に依存せず、該データを入力された順に加算するだけでよく、単純な構成で演算できる。
【００４３】
それに対し、サブブロック単位で丸め誤差が発生するかどうかは、データの入力順序に依存した演算を行なう必要がある。但し、丸め誤差（＋０．５または０）を表す信号は１ビットで、サブブロック内データの総和値の奇偶（性）に一致する。
【００４４】
そこで、本実施形態では、４つのサブブロック毎に、そのデータの総和値が奇数／偶数のどちらになるかをパリティ（ビット）Ｐｉ（ｉ＝０，１，２，３）として計算し生成する。以下、パリティＰｉの演算内容を説明するが、図１（Ａ）の４×４個のブロックデータをラスタ走査順に、Ｄａｔａ［ｉ］（ｉ＝０，１，２，３，，，１３，１４，１５）と表わす。
【００４５】
図１（Ｂ）のサブブロックのパリティをＰ０、図１（Ｃ）のサブブロックのパリティをＰ１、図１（Ｄ）のサブブロックのパリティをＰ２、図１（Ｅ）のサブブロックのパリティをＰ３とすると、それらは次式（１）により演算できる。
P0 = (Data[0] ＆ 1) ^ (Data[3] ＆ 1) ^ (Data[12] ＆ 1) ^ (Data[15] ＆ 1)
P1 = (Data[1] ＆ 1) ^ (Data[2] ＆ 1) ^ (Data[13] ＆ 1) ^ (Data[14] ＆ 1)
P2 = (Data[4] ＆ 1) ^ (Data[7] ＆ 1) ^ (Data[8] ＆ 1) ^ (Data[11] ＆ 1)
P3 = (Data[5] ＆ 1) ^ (Data[6] ＆ 1) ^ (Data[9] ＆ 1) ^ (Data[10] ＆ 1)  …(1)
ここで、上記（１）式における、“＆”は同じ位のビット間の論理積演算子を示し、“＾”はビット間の排他的論理和演算子を示す。従って、“Data[i] ＆ 1”によって、Ｄａｔａ［ｉ］の最下位１ビットが抽出される。上記の演算の結果、図１（Ｂ）のサブブロック内の４つのデータの総和値が偶数ならＰ０＝０となり、その総和値が奇数ならＰ０＝１となる。他のサブブロックも同様である。
【００４６】
また、上記（１）式の替わりに下記（２）式のように演算することもできる。この演算はサブブロックの４つのデータが並列に入力され、該４つのデータの加算を容易に行える場合に有効である。
P0＝(Data[0] + Data[3] + Data[12] + Data[15]) ＆ 1
P1＝(Data[1] + Data[2] + Data[13] + Data[14]) ＆ 1
P2＝(Data[4] + Data[7] + Data[8]  + Data[11]) ＆ 1
P3＝(Data[5] + Data[6] + Data[9]  + Data[10]) ＆ 1  …(2)
ここで、演算子“+”は文字とおり数値の加算を表わす。
【００４７】
式（１）に示したパリティ計算式に基づいてパリティＰ０，Ｐ１，Ｐ２，Ｐ３を生成するパリティ生成部４００の構成を図３に示す。ここでは、ブロックデータがラスタ走査順に４並列で入力されるものとしている。また、図３のパリティ生成部４００には、並列入力される４つのデータそれぞれの最下位ビット（ＬＳＢ）のみが入力されるものとする。
【００４８】
図３の構成において、端子群４０１からは、上記の並列に入力される４つのデータの最下位ビットが入力されるが、最初の４並列入力データ{Data[0], Data[1], Data[2], Data[3]}から、
(Data[0] ＆ 1)^(Data[3] ＆ 1）
(Data[1] ＆ 1)^(Data[2] ＆ 1)
が算出される。
【００４９】
２番目の４並列入力データ{Data[4], Data[5], Data[6], Data[7]}から、
(Data[4] ＆ 1)^(Data[7] ＆ 1）
(Data[5] ＆ 1)^(Data[6] ＆ 1)
が算出される。
【００５０】
これらの演算は、排他的論理和素子４１１、４１２にて計算され、排他的論理和素子４１３、４１４を通過して、参照符号４２０乃至４２３で示される１ビットのレジスタＲ０，Ｒ１，Ｒ２，Ｒ３に格納される。これらレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納されたビットデータは、パリティＰ０，Ｐ１，Ｐ２，Ｐ３を生成するために利用される。
【００５１】
次に３番目の４並列入力データ{Data[8], Data[9], Data[10], Data[11]}から、
(Data[8] ＆ 1)^(Data[11] ＆ 1）
(Data[9] ＆ 1)^(Data[10] ＆ 1)
が算出される。そして、これらは各々、セレクタ４３１，４３２で選択されたレジスタＲ２とＲ３に保持されている１ビットデータと排他的論理和素子４１３、４１４にて排他的論理和演算され、パリティＰ２，Ｐ３として端子４４１，４４２から出力される。
【００５２】
最後の４番目の４並列入力データ{Data[12], Data[13], Data[14], Data[15]}から、
(Data[12] ＆ 1)^(Data[15] ＆ 1）
(Data[13] ＆ 1)^(Data[14] ＆ 1)
が算出される。そして、これらは各々、セレクタ４３１，４３２で選択されるレジスタＲ０とＲ１に保持されている１ビットデータと排他的論理和素子４１３、４１４にて排他的論理和演算され、パリティＰ０，Ｐ１として端子４４１，４４２から出力される。
【００５３】
１ブロックを４サイクルで処理すると仮定すると、排他的論理和素子４１３、４１４から端子４４１，４４２に出力するパリティが有効なのは、後半２サイクルのみとなり、前半２サイクルでは端子４４１，４４２からは意味の無いデータが出力される。そのため、不図示の制御信号とマスク回路により、前半２サイクルの間は該２つの信号を共に“０”にマスクしておく。
【００５４】
以上に説明したパリティ生成部４００を用いて、整数可逆変換のブロックＤＣ係数を演算する装置の構成、すなわち、本第１実施形態の構成を図４に示す。パリティ生成部４００以外の主な構成要素は、入力データの総和値を計算する総和計算部５１０、パリティを値として加算するパリティ加算器５２０、前記総和計算部の出力を２ビット右へシフトする２ビットシフタ５３０である。
【００５５】
ブロックＤＣ係数を得る従来の演算では、１段目と２段目のアダマール変換器に加え、ラスタ走査順に入力データされるデータをサブブロック単位で処理するための、データ順序変換バッファが必要であった。本実施形態のＤＣ係数演算装置において、前記データ順序変換バッファは不要となり、端子５０１乃至５０４から並列に入力される４つのデータの総和値を演算する第１の加算器５１１と、該加算器５１１から得られる加算結果を累積加算する第２の加算器５１２、並びに、レジスタ５１３のみが必要となる。これら第１の加算器５１１、及び、第２の加算器５１２によって、ブロック内のデータの総和値を求めることができる。ここで、レジスタ５１３は、１つのブロックのブロックＤＣ係数の演算を開始するごとに、ゼロクリアされるものとする。
【００５６】
第１の加算器５１１の入力データが、サブブロックを構成する４つのデータであれば、該４つのデータを加算して２で割った値が、該サブブロックのＤＣ係数となる。これは、前記第１の加算器５１１から第２の加算器５１２へ出力するデータの最下位ビットが、小数点以下第１位のビットを意味する。一方、前記（１）または（２）式に基づいて計算したパリティＰ０は０．５の丸め誤差を表すため、値として見た時の重みは、前記固定小数点データの小数点以下１ビットと同じである。
【００５７】
よって、パリティＰｉ（ｉ＝０，１，２，３）は、第２の加算器５１２への入力データの最下位ビットと同じ重みであり、パリティ生成部４００から出力される２つのパリティを、パリティ加算器５２０で加算する場合、累積加算データの最下位ビットへ加算する。これによって、前記１段目の整数可逆アダマール変換で重畳する丸め誤差をすべて加算したサブブロックＤＣ係数の総和値を、第２の加算器５１２の出力として得られる。
【００５８】
２段目の４次アダマール変換のＤＣ係数も同様に、４つのデータの総和値を２で割った値であるため、入力の小数点位置に対し、第２の加算器５１２の出力における小数点位置を上位ビット方向へ１ビットずらす。元々、第２の加算器の入力は下位１ビットを小数とする固定小数点のデータであるため、最終的に、第２の加算器５１２の出力は下位２ビットが小数データになる。
【００５９】
２段目の整数可逆アダマール変換は、ＪＰＥＧ−ＸＲ勧告書の解釈によると、小数点以下を切り捨てる丸め処理に対応している。よって、２ビットシフタ５３０にて、レジスタ５１３が保持する値の下位２ビットを右シフトして、単純に切り捨て、その結果を、ブロックＤＣ係数として出力する。
【００６０】
なお、図４に示す演算はソフトウェアとハードウェアのどちらでも実現できるが、ハードウェアで実現する場合、シフタ５３０は、レジスタ５１３の出力バスの２ビット分の信号線をずらして出力端子５０５と接続すれば良い。
【００６１】
また、ソフトウェア処理において、ブロックデータが配列で引き渡される場合、サブブロックデータの加算を容易に行なうことができるため、式（２）に示した演算でパリティを計算すると効率的である。
【００６２】
以下は、式（２）に示したパリティ計算方法を用いて、整数可逆変換のブロックＤＣ係数を演算する処理手順を示している。
sum0 = Data[0] + Data[3] + Data[12] + Data[15];
sum1 = Data[1] + Data[2] + Data[13] + Data[14];
sum2 = Data[4] + Data[7] + Data[8]  + Data[11];
sum3 = Data[5] + Data[6] + Data[9]  + Data[10];
P0 = sum0 ＆ 1;
P1 = sum1 ＆ 1;
P2 = sum2 ＆ 1;
P3 = sum3 ＆ 1;
sum = sum0 + sum1 + sum2 + sum3 + P0 + P1 + P2 + P3;
DC = sum ＞＞ 2;
（ここで、“x ＞＞ y”は、ｘを下位方向にｙビットシフトすることを表わす）
【００６３】
上記の１行目から４行目で、サブブロック毎にデータを加算し、５行目から８行目で、前記サブブロック毎のデータ加算結果から最下位の１ビットをパリティとして抽出し、９行目で、前記加算結果とパリティをすべて合算する。最後の１０行目で、合算結果を２ビット右シフトして整数可逆変換のブロックＤＣ係数を生成する。
【００６４】
［第２の実施形態：１つずつ入力されるデータを加算する場合］
上記第１の実施形態における図４の構成は、図２の第１の変換部３０１、第３の変換部３０３に適用可能であるが、ブロックを形成する４×４データの１行分４つのデータを並列入力して処理することを前提にするものであった。ところが、第３の変換部３０３（マクロブロックＤＣ係数を生成する整数可逆変換部）について着目すると、第３の変換部３０３は、図４のブロックＤＣ係数演算部から出力されるブロックＤＣ係数を入力として変換するため、該入力ＤＣ係数を１つずつ入力することも可能である。より詳細には、図４の変換部は４×４データを４つ単位で並列処理し、４サイクル毎に１つのブロックＤＣ係数が生成するため、該ＤＣ係数を断続的に１つずつ前記第３の変換部３０３に供給することができる。
【００６５】
このような入力形式だと、マクロブロックＤＣ係数を生成するために必要な入力データの総和値を計算するための加算器は１つで済む。この場合も、各サブブロックのパリティは、入力データの最下位１ビットのみを抽出してサブブロック単位で排他的論理和を計算する式（１）に示した演算を行なって生成する。
【００６６】
そこで、第２の実施形態では、特に、図２における第３の変換部３０３として使用可能なマクロブロックＤＣ係数演算装置の構成を図５に示す。同図の通り、マクロブロックＤＣ係数演算装置は、入力データの最下位ビットからパリティを計算するパリティ生成部７０２、入力データにパリティを加算するパリティ加算器７２１、入力データの総和値を計算する総和計算部７３０、シフタ５３０で構成される。図３、図４と共通の機能を有するものは同一の部番を付してある。
【００６７】
上記パリティ生成部７０２、パリティ加算器７２１、総和計算部７３０のすべてが、前記第１実施形態（図３）に比べて簡易な構成になっていることが分かる。ここで、パリティ生成部７０２におけるパリティ演算は以下のように行なわれる。なお、入力端子７０１からは、４×４個のサブブロックＤＣ係数が、ラスタースキャン順に入力されるものとする。
【００６８】
まず、各レジスタＲ０，Ｒ１，Ｒ２，Ｒ３を“０”に初期化する。また、このタイミングでレジスタ７３２もゼロクリアする。
【００６９】
その後、１つのサブブロックＤＣ係数が入力端子７０１から入力されるたびに、セレクタ７１５は、Ｒ０，Ｒ１，Ｒ１，Ｒ０，Ｒ２，Ｒ３，Ｒ３，Ｒ２，Ｒ２，Ｒ３，Ｒ３，Ｒ２，Ｒ０，Ｒ１，Ｒ１，Ｒ０の順にレジスタ出力を選択し、入力したサブブロックＤＣ係数の最下位ビットとの間で、排他的論理和を演算し、選択したレジスタへ格納し直す。
【００７０】
上記のセレクタ７１５の動作により、レジスタＲ０は、０，３，１２，１５番目のデータ入力時に選択されるため、式（１）式と同等の演算が行なわれて該演算結果が、パリティＰ０としてパリティ加算器７２１へ出力される。
【００７１】
同様に、レジスタＲ１は１，２，１３，１４番目のデータ入力時に選択され、レジスタＲ２は４，７，８，１１番目のデータ入力時に選択され、レジスタＲ３は、５，６，９，１０番目のデータ入力時に選択される。このため、式（１）に示したパリティ計算式と同等の演算が行なわれる。
【００７２】
パリティ生成部７０２の出力が有効なのは、１０，１１，１４，１５番目のデータ入力の時のみで、それ以外は不図示の制御信号とマスク回路により、パリティ加算器７２１への出力を“０”にマスクし、不要なデータを加算しないようにする。
【００７３】
生成された有効なパリティＰ０，Ｐ１，Ｐ２，Ｐ３はパリティ加算器７２１にて入力データに加算され、該加算結果は総和計算部７３０のレジスタ７３２に累積加算されていく。そして、最終的に、ブロック内の全データと前記パリティを加算した結果がレジスタ７３２に格納されると、その値がシフタ５３０に出力される。
【００７４】
後は、第１実施形態と同様、該総和計算部の出力をシフタ５３０にて２ビット右シフトし、該シフトした値をマクロブロックＤＣ係数として出力することになる。第１の実施形態ではデータが４並列で入力され、第２の実施形態ではデータが断続的に１つずつ入力される場合の演算装置の構成を示した。入力の形態は、これ以外にも２並列、８並列、１６並列入力等が考えられるが、それらに対応する演算装置は、当業者であれば、ここで説明した２つの実施形態から容易に構成することができるであろう。
【００７５】
また、パリティ加算器７２１と総和計算部における加算器７３１は、１ビットのパリティをキャリーとして加算することが可能な、キャリー入力付きの加算器１つにまとめることが出来る。この場合、パリティ加算手段は、キャリー入力付き加算器のキャリー入力として具現化される。これを使用した例は次に示す第３の実施形態にて示す。
【００７６】
［第３の実施形態：パリティ計算は３つのみ、２種類の演算処理を示す］
第１、第２の実施形態では、サブブロック毎にパリティを計算していたが、第３の実施形態では、パリティ計算の一部を省略し、回路規模を更に小さくする例を説明する。
【００７７】
具体的には、第１、第２の実施形態で計算していた４つのパリティの内、３つのパリティのみを計算し、マクロブロックＤＣ係数を演算するものである。
【００７８】
第２実施形態をベースに、本第３の実施形態を具現化した演算装置の構成を図６（Ａ）、及び、その変形例を図６（Ｂ）に示す。
【００７９】
本第３の実施形態では、パリティＰ０の演算を省略し、その替わりに総和演算部の出力の最下位ビットをパリティＰ０として加算するのが図６（Ａ）に示す構成であり、パリティＰ０を恒常的に“１”として加算するのが図６（Ｂ）に示す構成である。このような演算が可能な理由を以下に説明する。
【００８０】
変換対象となる４×４個のデータの総和値が偶数の時、４つのパリティの和も偶数になり、データの総和値が奇数の時はパリティの和も奇数になる。よって、データの総和値にパリティを加算した結果は必ず偶数になる。
【００８１】
この関係を別の視点から見ると、データの総和値に３つのパリティを加算した結果が偶数なら、残りのパリティは“０”であることになる。また、データの総和値に３つのパリティを加算した結果が奇数であれば残りのパリティは“１”であることになる。ようするに、データの総和値に３つのパリティを加算した結果から、残りのパリティの値は一意に決まり、残りのパリティは前記加算結果の最下位ビットに等しい、ということが言える。
【００８２】
よって、データの総和値に３つのパリティを加算した結果の最下位ビットを残りのパリティとして加算することが可能である。この原理に基づく演算装置が図６（Ａ）に示す構成である。同図における参照符号８０１は第２実施形態の最後で説明したキャリー入力付きの加算器であり、参照符号８０２は前記総和値の最下位ビットを残りのパリティとして加算する加算器、参照符号８０３は前記３つのパリティのみを計算するパリティ生成部である。その他の構成要素は、図５における同一部番の要素と同じである。
【００８３】
一方、データの総和値に３つのパリティを加算した結果の最下位ビットが“０”の時に“１”を加算した場合、最後に行なう小数点以下２ビットの切り捨てにより、該加算したばかりの“１”は切り捨てられる。また、最下位ビットが“１”の時は“１”を加算する必要がある。
【００８４】
よって、前記最下位ビットの値に拠らず常に“１”を加算しても何ら問題は無い。これに基づく演算装置が図６（Ｂ）に示す構成である。この構成では、総和演算部におけるレジスタ８０４の初期値を“１”に設定することにより、パリティとして“１”を加算する演算を省略している。また、パリティ生成部からＰ０を出力するタイミングで“１”を出力して、それを加算することも可能である。
【００８５】
［第４の実施形態：サブブロック単位で切り捨て、ブロック単位で切り上げ］
第１，第２，第３実施形態では、ＪＰＥＧ−ＸＲにおける整数可逆変換と互換性を有するＤＣ係数を演算することを念頭にしていたので、１段目のサブブロック単位での丸め処理は切り上げを行ない、２段目のブロックレベルでは切り棄てを行なっていた。
【００８６】
本発明はＪＰＥＧ−ＸＲにおける整数可逆変換に限定されるものでは無く、例えば、４×４ブロックの１６点整数可逆アダアール変換などにも有効である。
【００８７】
本発明が適用可能な１６点整数可逆アダアール変換は、例えば特登録０３９０２９９０に記載されている。ここでは、列方向あるいは行方向の４つのデータをサブブロックとして１段目の４次整数可逆アダマール変換を適用し、２段目は列と行の方向を変えた４つのデータを単位として４次整数可逆アダマール変換を適用する。これによって、４×４ブロックデータに対する２次元の整数可逆アダマール変換、すなわち、１６点整数可逆アダマール変換を実現している。該変換において、１段目と２段目の整数可逆アダマール変換の丸め処理の組み合せは、非常に多く存在する。
【００８８】
ここでは一例として、１段目の変換の丸め処理は切り捨て、２段目の変換の丸め処理を切り上げとした時に、本発明においてどのような演算装置の構成になるかを示す。
【００８９】
丸め処理によって発生する丸め誤差は、切り上げの場合が＋０．５であったのに対し、切り捨ての場合は−０．５となる。この丸め誤差をブロックデータの総和値に反映するには、１段目の変換単位であるサブブロックに対するパリティを、前記データの総和値から減算する。また、２段目の変換の丸め処理を切り上げとするには、前記パリティを反映したデータの総和値に“１０”なる２ビットのデータを加算し、該加算結果を２ビット右シフトする。ここで加算する２ビット “１０”は、小数点以下２ビットのデータであるため、０．５という重みのデータである。
【００９０】
上記で説明した内容を第２の実施形態へ盛り込んだ、ＤＣ係数を求める演算装置の構成を図７に示す。
【００９１】
基本的には第２の実施形態と同じ処理であるが、以下のような違いがある。
【００９２】
パリティを加算する４つの処理が、パリティを減算（又は、正負の符号を反転して加算）する処理へ置き換えられると共に、２ビットシフトする直前の総和データに“１０”（２進数）すなわち“２”（１０進数）を加算している。
【００９３】
以上本発明に係る実施形態を説明した。上記実施形態では、係数ブロックのサイズを４×４としたが、サブブロックに含まれる係数の個数が４つであれば良いので、一般に４n（ｎは２以上の整数）に適用できるので、上記実施形態によって本発明が限定されるものではない。
【００９４】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
0005546329.tif 000002
【図２】
0005546329.tif 000003
【図３】
0005546329.tif 000004
【図４】
0005546329.tif 000005
【図５】
0005546329.tif 000006
【図６】
0005546329.tif 000007
【図７】
0005546329.tif 000008