(57)【要約】【課題】  簡単な構成でもって、４つのベクトルデータの丸め誤差の少ないロスレス４点直交変換を行う。【解決手段】  整数で表現される４つのベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、  行列演算、2006060703.tif 000021  によって、１より大きな奇数である係数ａに従って、４つの整数のベクトルデータから整数で表現される変換データを求めるデータ変換装置であって、先ず、Ｄ０乃至Ｄ３を求める（Ｓ３０１）。そして、Ｄ１に除数｛１＋ａ2｝の半分の値より小さい整数データを加算してＥ１を求め、残りのＤ０、Ｄ２、Ｄ３に除数の半分の値を加算することで除算前の補正データＥ０、Ｅ２、Ｅ４を求める（Ｓ３０３）。次に、Ｅ０乃至Ｅ４を除数で除算して、その結果Ｙ０、Ｙ１、Ｙ２、Ｙ３を出力する（Ｓ３０５）。【選択図】  図３
2006060703.tif 000002
【特許請求の範囲】
【請求項１】
整数で表現される４つのベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、
行列演算、
2006060703.tif 000015
によって、１より大きな奇数である係数ａに従って、整数で表現される変換データを求めるデータ変換装置であって、
係数ａ、及び、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、記憶保持する記憶保持手段と、
以下の演算を行う第１乃至第４の演算手段と、
第１演算手段：Ｄ０＝Ｘ０＋ａＸ１＋ａＸ２＋ａ2Ｘ３
第２演算手段：Ｄ１＝ａＸ０−Ｘ１＋ａ2Ｘ２−ａＸ３
第３演算手段：Ｄ２＝ａＸ０＋ａ2Ｘ１−Ｘ２−ａＸ３
第４演算手段：Ｄ３＝ａ2Ｘ０−ａＸ１−ａＸ２＋Ｘ３
前記記憶保持手段に記憶保持された係数ａ、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を前記第１乃至第４の演算手段に分配する分配手段と、
前記第１乃至第４の演算手段で得られたデータＤ０、Ｄ１、Ｄ２、Ｄ３の少なくとも１つに対して、除数｛１＋ａ2｝の半分の値より小さい整数データを加算し、残りに除数の半分の値を加算することで除算前の補正データＤ０'、Ｄ１'、Ｄ２'、Ｄ３'を演算する補正演算手段と、
該補正演算手段によって得られた補正データＤ０'、Ｄ１'、Ｄ２'、Ｄ３'を、前記除数で除算し、該除算結果を値が小さくなる方向へ小数点以下の値を切り捨てて、変換データとして出力する出力手段と
を備えることを特徴とするデータ変換装置。
【請求項２】
整数で表現される４つのベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、
行列演算、
2006060703.tif 000016
によって、１より大きな奇数である係数ａに従って、整数で表現される変換データを求めるデータ変換方法であって、
係数ａ、及び、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、記憶保持する記憶保持工程と、
以下の演算を行う第１乃至第４の演算工程と、
第１演算工程：Ｄ０＝Ｘ０＋ａＸ１＋ａＸ２＋ａ2Ｘ３
第２演算工程：Ｄ１＝ａＸ０−Ｘ１＋ａ2Ｘ２−ａＸ３
第３演算工程：Ｄ２＝ａＸ０＋ａ2Ｘ１−Ｘ２−ａＸ３
第４演算工程：Ｄ３＝ａ2Ｘ０−ａＸ１−ａＸ２＋Ｘ３
前記記憶保持工程に記憶保持された係数ａ、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を前記第１乃至第４の演算工程に分配する分配工程と、
前記第１乃至第４の演算工程で得られたデータＤ０、Ｄ１、Ｄ２、Ｄ３の少なくとも１つに対して、除数｛１＋ａ2｝の半分の値より小さい整数データを加算し、残りに除数の半分の値を加算することで除算前の補正データＤ０'、Ｄ１'、Ｄ２'、Ｄ３'を演算する補正演算工程と、
該補正演算工程によって得られた補正データＤ０'、Ｄ１'、Ｄ２'、Ｄ３'を、前記除数で除算し、該除算結果を値が小さくなる方向へ小数点以下の値を切り捨てて、変換データとして出力する出力工程と
を備えることを特徴とするデータ変換装方法。
【請求項３】
有効ビットがｍビットの整数で表現される４つのベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、
行列演算、
2006060703.tif 000017
によって、１より大きな奇数である係数ａに従って、整数で表現される有効ビット数がｍビットの変換データＹ０、Ｙ１、Ｙ２、Ｙ３を求めるデータ変換装置であって、
係数ａ、及び、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、記憶保持する記憶保持手段と、
演算の際の有効ビット数をｎとしたとき、２nを除数｛１＋ａ2｝で除算した際の整数の商の値Ｒ０を演算する第１の前処理演算手段と、
該第１の演算手段で求めた商に１を加算した値Ｒ１を演算する第２の前処理演算手段と、
前記係数ａと前記ｍに基づき、オフセット値を演算する第３の前処理演算手段と、
以下の演算を行う第１乃至第４の演算手段と、
第１演算手段：Ｄ０＝Ｘ０＋ａＸ１＋ａＸ２＋ａ2Ｘ３
第２演算手段：Ｄ１＝ａＸ０−Ｘ１＋ａ2Ｘ２−ａＸ３
第３演算手段：Ｄ２＝ａＸ０＋ａ2Ｘ１−Ｘ２−ａＸ３
第４演算手段：Ｄ３＝ａ2Ｘ０−ａＸ１−ａＸ２＋Ｘ３
前記記憶保持手段に記憶保持された係数ａ、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を前記第１乃至第４の演算手段に分配する分配手段と、
前記第１乃至第４の演算手段で得られたデータＤ０、Ｄ１、Ｄ２、Ｄ３に、前記除数の半分の値を加算する第１の加算手段と、
該第１の加算手段で加算した４つのデータのうち、３つに対して前記第３の前処理演算手段で得られたオフセット値を加算する第２の加算手段と、
該第２の加算手段の加算の少なくとも１つに前記値Ｒ１を乗算し、残りに前記Ｒ０を乗算する乗算手段と、
該乗算手段で乗算した結果を、前記２nで除算するため、ｎビット分だけ下位方向にシフトするシフト手段と、
シフト手段で得られた値のうち、前記第２の加算手段での加算対象となったデータについて前記オフセットに対応する値を減算する減算手段と
を備えることを特徴とするデータ変換装置。
【請求項４】
有効ビットがｍビットの整数で表現される４つのベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、
行列演算、
2006060703.tif 000018
によって、１より大きな奇数である係数ａに従って、整数で表現される有効ビット数がｍビットの変換データＹ０、Ｙ１、Ｙ２、Ｙ３を求めるデータ変換方法であって、
係数ａ、及び、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、記憶保持する記憶保持工程と、
演算の際の有効ビット数をｎとしたとき、２nを除数｛１＋ａ2｝で除算した際の整数の商の値Ｒ０を演算する第１の前処理演算工程と、
該第１の演算工程で求めた商に１を加算した値Ｒ１を演算する第２の前処理演算工程と、
前記係数ａと前記ｍに基づき、オフセット値を演算する第３の前処理演算工程と、
以下の演算を行う第１乃至第４の演算工程と、
第１演算工程：Ｄ０＝Ｘ０＋ａＸ１＋ａＸ２＋ａ2Ｘ３
第２演算工程：Ｄ１＝ａＸ０−Ｘ１＋ａ2Ｘ２−ａＸ３
第３演算工程：Ｄ２＝ａＸ０＋ａ2Ｘ１−Ｘ２−ａＸ３
第４演算工程：Ｄ３＝ａ2Ｘ０−ａＸ１−ａＸ２＋Ｘ３
前記記憶保持工程に記憶保持された係数ａ、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を前記第１乃至第４の演算工程に分配する分配工程と、
前記第１乃至第４の演算工程で得られたデータＤ０、Ｄ１、Ｄ２、Ｄ３に、前記除数の半分の値を加算する第１の加算工程と、
該第１の加算工程で加算した４つのデータのうち、３つに対して前記第３の前処理演算工程で得られたオフセット値を加算する第２の加算工程と、
該第２の加算工程の加算の少なくとも１つに前記値Ｒ１を乗算し、残りに前記Ｒ０を乗算する乗算工程と、
該乗算工程で乗算した結果を、前記２nで除算するため、ｎビット分だけ下位方向にシフトするシフト工程と、
シフト工程で得られた値のうち、前記第２の加算工程での加算対象となったデータについて前記オフセットに対応する値を減算する減算工程と
を備えることを特徴とするデータ変換方法。
【請求項５】
４つの整数で構成されるベクトルデータに下記行列（ａは４以上の偶数）を乗算する積和演算手段と、
2006060703.tif 000019
該演算結果に整数値を加算する手段と、
１＋ａ×ａなる除数でもって割り算を行なって商を求める除算手段と、
該商が持つ丸め誤差を求める誤差演算手段と、
丸め誤差が所定の範囲に入っているかどうかを判定する手段と
を有し、該判定結果に基づき、４つの商の一部に１を加算もしくは減算することを特徴とするデータ変換装置。
【請求項６】
４つの整数からなるベクトルデータに下記行列（ａは４以上の偶数）を乗算する積和演算工程と、
2006060703.tif 000020
該演算結果に整数値を加算する手段と、
１＋ａ×ａなる除数でもって割り算を行なって商を求める除算工程と、
該商が持つ丸め誤差を求める誤差演算工程と、
丸め誤差が所定の範囲に入っているかどうかを判定する工程と
を備え、該判定結果に基づき、４つの商の一部に１を加算もしくは減算することを特徴とするデータ変換方法。
【請求項７】
請求項１又は３又は５に記載のデータ変換処理装置を一部に用いたことを特徴とする２次元ＤＣＴ変換処理装置。
【請求項８】
請求項１又は３又は５に記載のデータ変換処理装置を一部に用いたことを特徴とする可逆符号化処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は整数データから整数データへの可逆変換が可能なロスレス４点直交変換処理方法、および、該変換処理装置に関する。
【背景技術】
【０００２】
静止画像の国際標準符号化方式であるＪＰＥＧにおいて、圧縮・伸張後の画像が元画像と完全に一致するよう可逆符号化モードが規格化されたが、当時はロスレス変換技術が十分研究されておらず、ＤＣＴを用いてロスレス変換を実現することができなかった。そのため、ＤＣＴを用いたブロック変換符号化とは異なる技術を用い、画素単位の予測符号化という方法で可逆符号化を実現していた。
【０００３】
その後、可逆符号化専用の標準符号化技術：ＪＰＥＧ−ＬＳが規格化されたが、さらに後に規格化されたＪＰＥＧ２０００では、ウェーブレット変換という共通技術でロスレス変換とロスレスではない一般の変換を実現し、それにより劣化の無い可逆符号化と劣化を伴う非可逆符号化の両方の符号化が可能となった。
【０００４】
画像データの圧縮変換処理は、大きく分けて、空間変換処理（ＤＣＴやウェーブレット変換等）、量子化処理、エントロピー符号化処理の３つに分けられる。この中でエントロピー符号化処理は、量子化された値の集まり（情報）をハフマン符号などの他の符号に変換することにより、前記情報が持つエントロピーに近いビット数に変換するものであり、一種のロスレス変換処理である。
【０００５】
一方、量子化処理は、情報量を削減する工程で、これにより圧縮率の制御も可能となるもので、基本的にロッシー変換である。従って、変換符号化圧縮処理でロスレスとなるようにするには、この量子化処理をしてはならない。しかし、空間変換処理の結果が小数点以下の値を有する時、これを量子化しないと、圧縮前のデータ量よりも圧縮後のデータ量の方が大きくなってしまう。
【０００６】
空間変換処理の結果が小数点以下の値を有する時に、量子化ステップ“１”で量子化することは、それを整数化することになるので、ここで信号の劣化が生じて、伸張後のデータが元のデータと一致するという保証が無くなる。
【０００７】
結局、可逆符号化を実現するには、可逆性が保証された整数値を出力する空間変換処理で得られた値（ロスレス変換係数という）を量子化しないで、そのままエントロピー符号化する必要があることがわかる。この場合、量子化ステップ“１”で量子化しても変換係数がそのまま保持されるので、量子化ステップ“１”で量子化処理をしているという見方もある。
【０００８】
このように、可逆符号化を実現するには、可逆性が保証された整数値を出力する空間変換処理（以下では単に“ロスレス変換”と称す）が必要不可欠である。
【０００９】
従来、そのようなロスレス変換を実現する手法として、Ｌａｄｄｅｒ  Ｎｅｔｗｏｒｋ（以下では“梯子演算回路網”と称す）というものがあった（非特許文献１）。これは、２点回転変換行列を３つの三角行列に分解し、各々の三角行列を１つの梯子演算に置き換えた後、各梯子演算に丸め処理を導入したものである。また、これを４点直交変換に拡張したものもある（非特許文献２）。
【００１０】
以下では、ロスレス２点回転変換とロスレス４点直交変換について、更に詳しく説明する。
【００１１】
２点回転変換行列は下式のように対角成分が“１”の３つの三角行列の積に分解できる。
2006060703.tif 000003
【００１２】
２つの入力データを２本梯子と見なすと、対角成分が“１”の三角行列の演算は構造的に梯子の横木に対応する。すなわち、三角行列の非対角成分の演算は、一方の入力に該成分値を乗算し、それをもう一方の入力に加算するものであるから、それをシグナルフローグラフで表現すると、梯子の横木に見えるわけである。よって、２点回転変換は、図１（ａ）に示すように３段の梯子演算で表現できる。
【００１３】
図１（ｂ）に示すように、各梯子演算における乗算処理後の値を丸め処理して整数化することにより、容易に整数値から整数値へのロスレス変換が実現できる。よって、梯子演算を用いたロスレス変換においては、乗算処理部、丸め処理部、加算処理部（減算処理の場合もある）の３つの処理部で構成できる。図１（ｂ）において、符号１１１，１２１，１３１が乗算処理部であり、１１３，１２３，１３３が丸め処理部であり、１１５，１２５，１３５が加算処理部である。回転角がθであるときの乗算係数は、１１１，１２１，１３１の順に、ＴＡＮ（θ／２）、−ＳＩＮ（θ）、ＴＡＮ（θ／２）である。
【００１４】
梯子演算１段ごとに乗算結果を整数化するための丸め処理を行なうことにより、乗算結果が整数でない限り必ず丸め誤差が発生し、各梯子演算で発生する誤差は出力データに蓄積される。
【００１５】
従来、２点回転変換処理４つからなる４点直交変換のロスレス変換は、図２のように構成されていた。ここで、符号２０１〜２０４は各々２点回転変換で、図１（ｂ）に示すように３段の梯子演算で構成される。ロスレス４点直交変換全体でみると、１２段の梯子演算があり、同じく１２回の丸め処理が行なわれる。当然のように、丸め処理の回数に比例して丸め誤差が増える。
【００１６】
一方、非特許文献２では、４点直交変換を４次元に対応・拡張した梯子演算５回に分割して、ロスレス変換を実現している。ｎ次元の１回の梯子演算は、ｎ−１回の乗算演算を伴うので、４点直交変換では（４−１）×５＝１５回の乗算演算が必要になる。しかし、梯子演算の性質上、丸め処理を大幅に減らすころができる。多次元の梯子演算では、梯子演算の梯子の先（加算対象となるデータ）が１つのデータに集中するので、それらのデータを合算してから丸め処理を行なうことができ、梯子演算１回につき１回の丸め処理で済ますことができる。よって、非特許文献２の４点直交変換では５回の丸め処理で済む。
【非特許文献１】Ｆ．Ｂｒｕｅｋｅｒｓ  ａｎｄ  Ａ．Ｅｎｄｅｎ，“Ｎｅｗ  Ｎｅｔｗｏｒｋｓ  ｆｏｒ  Ｐｅｒｆｅｃｔ  Ｉｎｖｅｎｔｉｏｎ  ａｎｄ  Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ”ＩＥＥＥ  ＪＳＡＣ，ｖｏｌ．１０，ｎｏ．１．ｐｐ．１３０−１３７，Ｊａｎ  １９９２
【非特許文献２】小松邦紀、瀬崎薫、“可逆的離散コサイン変換とその画像情報圧縮への応用”、信学技報、ＩＥ９７−８３、ｐｐ．１−６、１９９７年１１月
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上記のように、ロスレス変換というのは、その可逆性を保証するために梯子演算という特殊な演算を行なう必要があるため、既に多くの研究がなされている高速演算アルゴリズムなどを適用することができず、演算量を減らすことが困難である。換言すれば、これまでのロスレス変換は、特殊な演算が必要であり、高速化に適したものとは言えなかった。また、丸め処理が多いため、丸め誤差が大きいという欠点もあった。
【００１８】
本発明はかかる問題点に鑑みなされたものであり、装置に実装した際に、簡単な構成でもって、４つのベクトルデータの丸め誤差の少ないロスレス４点直交変換を行う技術を提供しようとするものである。
【課題を解決するための手段】
【００１９】
この課題を解決するため、本発明のデータ変換装置は以下の構成を備える。すなわち、
整数で表現される４つのベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、
行列演算、
2006060703.tif 000004
によって、１より大きな奇数である係数ａに従って、整数で表現される変換データを求めるデータ変換装置であって、
係数ａ、及び、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を入力し、記憶保持する記憶保持手段と、
以下の演算を行う第１乃至第４の演算手段と、
第１演算手段：Ｄ０＝Ｘ０＋ａＸ１＋ａＸ２＋ａ2Ｘ３
第２演算手段：Ｄ１＝ａＸ０−Ｘ１＋ａ2Ｘ２−ａＸ３
第３演算手段：Ｄ２＝ａＸ０＋ａ2Ｘ１−Ｘ２−ａＸ３
第４演算手段：Ｄ３＝ａ2Ｘ０−ａＸ１−ａＸ２＋Ｘ３
前記記憶保持手段に記憶保持された係数ａ、ベクトルデータＸ０、Ｘ１、Ｘ２、Ｘ３を前記第１乃至第４の演算手段に分配する分配手段と、
前記第１乃至第４の演算手段で得られたデータＤ０、Ｄ１、Ｄ２、Ｄ３の少なくとも１つに対して、除数｛１＋ａ2｝の半分の値より小さい整数データを加算し、残りに除数の半分の値を加算することで除算前の補正データＤ０'、Ｄ１'、Ｄ２'、Ｄ３'を演算する補正演算手段と、
該補正演算手段によって得られた補正データＤ０'、Ｄ１'、Ｄ２'、Ｄ３'を、前記除数で除算し、該除算結果を値が小さくなる方向へ小数点以下の値を切り捨てて、変換データとして出力する出力手段とを備える。
【発明の効果】
【００２０】
本発明によれば、４つのベクトルデータに整数要素からなる４×４の行列を乗算する手段と、該乗算結果に整数値を加算する手段と、割り算を行なう際に値が小さくなる方向へ切り捨てを行なう除算手段を有し、前記加算手段において、少なくとも１つ以上のデータに対し、除数の半分の値よりも小さな整数値を加算することにより、丸め誤差の少ないロスレス４点直交変換を実現することができる。
【００２１】
４つの整数からなるベクトルデータに４×４の整数行列を乗算する積和演算手段と、該演算結果に整数値を加算する手段と、割り算を行なう際に値が小さくなる方向へ切り捨てを行なって商を求める除算手段と、該商が持つ丸め誤差を求める誤差演算手段と、丸め誤差の絶対値が所定の範囲に入っているかどうかを判定する手段と、丸め誤差の負号を判定する手段とを有し、該判定結果に基づき、４つの商の内の１つに１を加算もしくは減算することにより、丸め誤差の少ないロスレス４点直交変換を実現することができる。また、この種の整数行列の乗算処理には、いろいろな高速演算アルゴリズムがあるので、それらを用いることにより高速に変換処理することができる。
【発明を実施するための最良の形態】
【００２２】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００２３】
＜第１の実施形態＞
本第１の実施形態のロスレス４点変換では、従来行なわれていた梯子演算を用いず、変換前の４つの整数データに対して、整数要素で構成される４×４の行列を乗算し、次に割り算を行なう際の除数の半分の値、もしくは、除数の半分の値よりも小さな値を加算し、最後に値が小さくなる方向へ切り捨てを行なう除算を行なう。
【００２４】
第１の実施形態では、少なくとも１つ以上のデータに対し、前記除数の半分の値よりも小さな値を加算するものである。本実施形態が対象としている変換は、下記（１）式で表現される。
2006060703.tif 000005
…（１）
【００２５】
上式において、Ｘ０，Ｘ１，Ｘ２，Ｘ３は変換前の４つの整数データであり、ａは自然数である。ここで、当業者が普通と考える方法で処理した場合の変換例を示す。ここでは、仮に、ａ＝３とし、４つのデータＸ０、Ｘ１、Ｘ２、Ｘ３がそれぞれ下記の値を持つものとする。
１７，    １２，    ９，    ５５
ただし、変換結果を整数値で得るため（１＋ａ＊ａ）＝１０で除算する前に、（１＋ａ＊ａ）／２＝５を、各々の演算途中のデータに加算する。この演算結果は次のようになる。
５８，    −４，  −１，    １５
これを、同じ変換処理で再変換すると次のようになる。
１８，    １２，    ９，    ５５
【００２６】
前記の式（１）は数学的に可逆な変換であり、それ自身が逆変換でもある。即ち、整数化せずに式１の変換を２回行なえば、元のデータに戻り、変換前のデータと２回変換後のデータは一致する。
【００２７】
ところが、上の結果ではそうなっていない。この原因は１回目の変換結果を整数化することにより丸め誤差が発生し、該丸め誤差が逆変換時に１番目のデータＸ０に集中し、逆変換時の四捨五入でそれを打ち消すことができないからである。
【００２８】
ここで、さらに細かく四捨五入の丸め誤差について見ていく。除算演算において１０で割る場合、小数点以下の値が０．１単位の値をとる。小数点以下の値が０．１〜０．４の場合には切り捨てを行い、小数点以下が０．６〜０．９の場合に切り上げると、最大で±０．４の丸め誤差が発生するが、この誤差は正負対称に発生する誤差である。
【００２９】
一方、小数点以下の値が０．５の場合、これを切り上げると＋０．５の丸め誤差が発生し、これを切り捨てると−０．５の丸め誤差が発生する。この誤差は正負非対称に発生する誤差である。四捨五入という丸め処理は、小数点以下の０．５を切り上げるので、＋０．５の非対称誤差を生み出す。
【００３０】
上記、変換・逆変換処理で、元のデータに戻らない原因は、この非対称誤差にあることを突き止めた。原因が非対称誤差にあるため、小数点以下の０．５を切り捨てると、今度は−０．５の非対称誤差が発生するので、やはり、変換・逆変換で元のデータに戻ることはない。
【００３１】
本実施形態では、式（１）をベースにした整数値から整数値への変換においてロスレス変換を実現する。そのために、図３に示す順変換処理と図４に示す逆変換処理を提案する。これが本発明の第１の実施形態の特徴点である。
【００３２】
図３におけるステップＳ３０１は積和演算処理、ステップＳ３０３は加算処理、ステップＳ３０５は除算処理である。図４も図３とほぼ同じであるがステップＳ４０３の加算処理が多少異なる。本実施形態の処理で特徴的なのは、ステップＳ３０３、ステップＳ４０３で加算する値が、除数（＝ａ2＋１）の半分より小さな値があるということである。
【００３３】
即ち、図３のステップＳ３０３の２番目の加算演算と、図４のステップＳ４０３の３番目以外の加算演算において、除数（＝１０）の半分の値（＝５）より小さな値“４”を加算する。このような加算処理を行なうと、順変換処理と逆変換処理の結果は以下のようになる。
順変換処理後：    ５８，    −５，    −１，    １５
逆変換処理後：    １７，    １２，      ９，    ５５
上記の様に、逆変換処理後のデータは、元のデータに一致していることが分かる。従来のような梯子演算を用いてロスレス変換を実現する方法ではなく、本実施形態に示した方法によっても、ロスレス変換を実現できることが示せた。
【００３４】
なお、上記順変換処理と逆変換処理は互いに相補的な関係にある。即ち、逆変換処理をした後、順変換処理をしても元のデータに戻る。よって、図４の処理も順変換処理の１つに入る。この時の逆変換処理は当然図３に示す処理となる。図４の処理を順変換処理として見た時、３つのデータに対して、前記除数の半分の値より小さな値を加算することになる。
【００３５】
図１４は上記図３、図４の処理を行うための具体的回路構成を示している。図示における各構成要素の全ては整数データを処理するものである点に注意されたい。つまり、以下に説明する「除算」では、余りが発生した、もしくは小数点以下にデータが発生した場合にはそれを切り捨てる。
【００３６】
図示において、符号１乃至５は多ビットのデータを保持するレジスタであり、レジスタ１乃至４は変換元の上記Ｘ０乃至Ｘ３を記憶保持し、レジスタ５は上記ａを記憶保持する。また、符号６もレジスタであるが、これには順変換（図３）／逆変換（図４）を切替えるものであって１ビットのデータを保持する。
【００３７】
符号７乃至１０は整数演算器であって、それぞれはレジスタ１乃至５から分配されたデータを入力し、図示の演算を行う。これら整数演算器７乃至１０は、図３のステップＳ３０１、又は、図４のステップＳ４０１に相当する演算を行うものでもあり、整数の加算器及び乗算器で構成されるものであって、演算誤差は発生しない。
【００３８】
符号１１も整数演算器であり、レジスタ５に格納されたａを二乗し、それに“１”を加算した結果「ａ＊ａ＋１」を出力する。符号１２は入力したデータを２で除算する除算器である。２の除算は、１ビット右（下位方向）シフトで実現できるので、除算器１２はビットシフト器で構成し得る。符号１３は除算器１２の出力データから“１”を減算する減算器である。
【００３９】
符号１５乃至１８はそれぞれ加算器であって、該加算器に入力された２つのデータを加算し、その結果を出力する。１９乃至２２は除算器であって、入力端子Ｐのデータを、入力端子Ｑのデータで除算する。
【００４０】
符号１４はセレクタであって、レジスタ６にセットされた値（０or１）に応じて、入力端子Ｐ、Ｑに入力されたデータを選択し、加算器１５乃至１８に出力する。具体的には、レジスタ６にセットされた値が“０”（順変換）の場合、入力端子Ｐより入力したデータを加算器１６に出力し、入力端子Ｑより入力したデータを加算器１５、１７、１８に出力する。また、レジスタ６にセットされた値が“１”（逆変換）の場合には、入力端子Ｐから入力したデータを加算器１５、１６、１８に出力し、入力端子Ｑから入力したデータを加算器１７に出力する。
【００４１】
より詳しくは、レジスタ６に“０”をセットすると、加算器１６には「（ａ＊ａ＋１）／２−１」が供給され、加算器１５、１７、１８には「（ａ＊ａ＋１）／２」が供給される。また、レジスタ６に“１”をセットすると、加算器１７には「（ａ＊ａ＋１）／２」が供給され、加算器１５、１６、１８には「（ａ＊ａ＋１）／２−１」が供給される。レジスタ６に“０”をセットした変換を順変換とすると、レジスタ６に“１”をセットした変換は逆変換となるが、順変換と逆変換は相対的なものであり、レジスタ６に“１”をセットした変換を順変換と捉えれば、レジスタ６に“０”をセットした変換は逆変換となる。
【００４２】
更に具体的に述べると、レジスタ５にａの値として“３”をセットし、レジスタ６に“０”をセットした場合、加算器１５乃至１８は、ちょうど図３のステップＳ３０３の処理を行うことになる。一方、レジスタ６に“１”をセットすると、加算器１５乃至１８は図４のステップＳ４０３の処理を行うことになる。
【００４３】
以上の結果、図１４の回路構成によって、順変換、逆変換処理を切替えることが可能となる。
【００４４】
なお、ステップＳ３０３，Ｓ４０３以外の加算処理方法もある点に注意されたい。一例として、ステップＳ３０３における“４”の加算演算を２番目から３番目に変更してもよい。これに対応する逆変換の加算処理は２番目の加算演算で“５”を加算し、２番目以外の加算演算で“４”を加算したものとなる。
【００４５】
本実施形態においては、ａの値が“３”に限定されるものでない。また、ａの値が３以上の奇数の逆数であってもよい。何故なら、前記式１全体をｎ2倍すると、係数“１”と係数“ａ2”の負号とが入れ替わり、変数ａがｎに置き換わるが、結局、変換前後のデータを置換すると元の式１の変換と同じになるからである。
【００４６】
さらに、式（１）の直交変換行列の行の置換や負号反転等の操作によって、上記のような順変換と逆変換の対応が変わってくるが、その範疇で考えられる処理の変形は本実施形態の範囲内であることは言うまでも無い。
【００４７】
本実施形態は、データ変換処理方法として説明してあるが、各演算処理を実行する演算器を用意して、図３、図４の処理フローの順に従って、各演算器を接続しデータを処理させれば、ロスレスデータ変換処理装置を構成できる。これは当業者であれば容易に考えられることである。
【００４８】
また、ａの値が偶数の時、除数（１＋ａ＊ａ）は奇数になるので、該除数の半分の値は整数＋０．５という値になる。この場合は、全部の４つの加算演算において前記整数部のみを加算すればロスレス変換になってしまう。よって、４つとも除数を１ビット右シフトした値を加算すればよい。
【００４９】
これに対処するためには、図１４における減算器１３は、値ａの最下位ビット（ＬＳＢ）を減算する処理を行えば良い。つまり、ａの値が偶数の場合、該ＬＳＢは“０”になるので、減算器１３は“１”を減じる処理を行わず、整数部分のみを出力する。この場合、セレクタ１４の入力端子Ｐ，Ｑの値は同じになるため、どちらの入力を選択しても出力は同じである。
【００５０】
＜第２の実施形態＞
ハードウェアでは除算を乗算に置き換えた方が処理が容易になり、除算速度の遅いマイクロコントローラにおいても、このような処理の置き換えにより高速化が図れる。このような状況に対応するため、本第２の実施形態は、前記式１の変換における除算演算を、該除数の逆数の乗算演算と小数点以下の切り捨て処理に置き換えたものである。
【００５１】
１０進数で切りのよい数字でも、プロセッサの内部数値表現である２進数では、無限小数になることがある。１０の逆数である０．１を２進数表現すると０．０００１１００１2（下線部は循環小数）となる。
【００５２】
演算では無限小数を扱うことが出来ないので、上記循環小数は有限小数に丸めなければならない。その際、通常は丸め後の桁数によって、切り上げになったり、切り捨てになったりする。例えば、小数点９桁（ビット）に丸める場合、０．０００１１００１１2にするのが誤差が一番少なく、小数点１１桁（ビット）に丸める場合、０．０００１１００１１０１2にするのが誤差が一番少ない。結果として、前者は切り捨て、後者は切り上げ処理になっている。
【００５３】
本実施形態では、切り捨て・切り上げ処理した２種類の有限小数を使い分ける。即ち、有限ビットの小数に丸めた値として、切り捨て処理した値と切り上げ処理した値の両方を用意する。有効ビット数の大きな小数の切り捨て・切り上げを厳密に管理するには、固定小数点で扱うのが一般的である。
【００５４】
そのために、本第２の実施形態の処理を表す図５のステップＳ５０１にて、除数の逆数を所定ビットに切り上げ処理した値と、切り捨て処理した値を固定小数点で計算する。該固定小数点の有効ビット数をｎ、除数（１＋ａ＊ａ）をｄとすると、２をｎ乗した値（１をｎビット左シフトした値）を除数ｄで割った時の余りが０以外の場合（実施形態では、これを通常の場合と考えている）、その時の商が、前記切り捨て処理した固定小数点の逆数ｒ０になる。該逆数の最下位ビットの重みは２-nである。そして、前記逆数ｒ０に１を加算したものが、前記切り上げ処理した固定小数点の逆数ｒ１になる。前記有効ビット数ｎの決め方については後述する。
【００５５】
前記余りが０となるのは、除数（１＋ａ＊ａ）が２のべき乗となる時のみであり、そのような関係は少なくとも想定している範囲では有りえない（数学的にも存在しないと考えられる）。そして、除数ｄ、逆数ｒ０、ｒ１以外に、除数ｄの半分の値をｈに、後述するオフセットをｆに求めておく。
【００５６】
以上で説明したＳ５０１の処理は、画像データなどの大量のデータを直交変換する前に一度計算しておくだけでよい。
【００５７】
上記説明で計算した２種類の逆数を用いて、以下に説明するロスレスの４点直交変換を行なう。
【００５８】
まず、ステップＳ５０２の積和演算処理は、図３のステップＳ３０１とまったく同じ処理を行なう。次に、ステップＳ５０３の第１の加算処理では、前記除数の半分の値を加算する。前記第１の実施形態では、除数の半分の値と、半分より小さな値の２種類を加算していたが、ここでは、１種類の値のみを加算する。
【００５９】
ステップＳ５０４の第２の加算処理では、変換行列の２〜４行目の演算結果に対してオフセットを加算する。該オフセットを加算する目的は、前記逆数を乗算する対象である被乗数を０より大きな値へレベルシフトするためである。よって、ステップＳ５０３の処理結果で想定される最も小さな値（負の値）を０より大きな値へレベルシフトするに足りる値を加算する。この値は式１の変換行列におけるマイナス要素に入力の最大値を乗算して合算した値から計算できる（処理対象データを０以上と仮定する）。１行目の演算結果にオフセットを加算しないのは、加算演算かなく演算結果がマイナスになる要因がないからである。
【００６０】
変換行列の４行目に着目すると、−ａの要素が２つあるので、ａ＝３、入力の最大値を２５５とした場合、３×２５５×２＝１５３０となる。また、オフセットは、後述する理由から除数（１＋ａ＊ａ）の整数倍（ｐ倍）である必要がある。ａ＝３の場合、除数は１０になるので、前記計算結果である“１５３０”は条件を満たしているので、これをオフセットとして加算する。この場合には、ｐ＝１５３となる。
【００６１】
前記式１の変換行列では、ａの二乗の項が全部プラスになっているが、負号反転など操作で、ａの二乗の項がマイナスになっている変換行列を用いる場合、オフセットの値を大きくしなければならない。
【００６２】
ステップＳ５０５の乗算処理は、固定小数点の逆数ｒ０、ｒ１を乗算し、ビットシフト処理を行なうことによって、先のステップＳ３０５の除算処理の替わりを行なう。
【００６３】
最後に、ステップＳ５０６の減算処理でｐ（＝１５３）を減算する。この処理はステップＳ５０４で加算したオフセットを取り除くための処理である。ここで完全にオフセットを取り除くために、オフセットは除数の整数倍（ｐ倍）である必要があったわけである。
【００６４】
上記説明では、変換行列の２〜４行目の演算すべてにおいて、同一のオフセットを加算しているが、２行目と３行目は、上述の値“１５３０”よりも小さなオフセットでもよいことが分かる。具体的には、（１＋３）×２５５＝１０２０  という値でもよい。
【００６５】
このように、加算するオフセットを必要最小の値にした場合、オフセット加算後の各行の演算結果の最大値は（１＋３＋３＋９）×２５５＋５＝４０８５  となる。共通のオフセットを用いると最大値は１５３０と１０２０との差分“５１０”だけ大きくなる。よって、最大値は“４５９５”となる。
【００６６】
この値に対して、切り捨てした逆数ｒ０や切り上げした逆数ｒ１を乗算した時に発生する誤差が、各々絶対値で１／１０未満になるように逆数の精度を確保する必要がある。これは、１／１０単位の演算結果が区別できるようにするためである。これに基づいて逆数の範囲を限定すると、以下のようになる。
2006060703.tif 000006
【００６７】
よって、逆数の誤差は絶対値で１／４５９６０以下である必要がある。この誤差は、１５．５ビットの演算精度に相当するので、それより精度のよい１６ビット精度の逆数にする。ここでやっと、ｎ＝１６という値がでてくる。
【００６８】
次に、以上に説明した各種パラメータを用いて、実際の演算結果について検討する。
【００６９】
まず、１／１０を１６ビットで切り捨て近似した逆数ｒ０は２16÷１０＝６５５３になり、切り上げ近似した逆数ｒ１は６５５４になる（固定小数点表示なので実際の１の重みは１／６５５３６である）。これらのパラメータから各処理の結果がどのようになるかを以下に示す。
元のデータ      ：    ２４７，    ２５２，        ９，        ５
積和演算後      ：  １０７５，    ５５５，  ２９８５，  １４４５
第１加算処理後  ：  １０８０，    ５６０，  ２９９０，  １４５０
第２加算処理後  ：  １０８０，  ２０９０，  ４５２０，  ２９８０
逆数乗算シフト後：    １０８，    ２０８，    ４５２，    ２９８
オフセット減算後：    １０８，      ５５      ２９９，    １４５
【００７０】
上記オフセット減算後の値が第２実施形態のロスレス変換処理結果である。この変換結果は、図６に示す逆変換処理によって元のデータに復元される。図６の逆変換処理は、第１実施形態と同様、基本的に順変換処理と同じであるが、次の点が異なる。
【００７１】
前述の説明で、元のデータを０〜２５５としているので、逆変換後の値も同じ０〜２５５の範囲となる。途中の演算結果にマイナスの値があっても、最終的には除数の半分の値ｈを加算することで０以上になる。よって、逆変換処理ではオフセットの加算処理（ステップＳ５０４）とそれを打ち消す減算処理（ステップＳ５０６）が不要となる。また、順変換処理における逆数ｒ０、ｒ１の乗算箇所に対応して逆変換処理における逆数ｒ０、ｒ１の乗算箇所を変える。この逆数ｒ０、ｒ１の乗算箇所を変えた処理がステップＳ６０５である（図示の記号“＞＞”は下位方向へのビットシフトを示している）。
【００７２】
もし、元のデータの範囲を負の値まで広げると、逆変換処理にも上記オフセットの加算処理（ステップＳ５０４）とそれを打ち消す減算処理（ステップＳ５０６）が必要となり、図５とほとんど同じ処理となる。違いは、ステップＳ６０５のみとなる。
【００７３】
上記、ロスレス変換処理結果を逆変換処理した時の各ステップの処理結果を以下に示す。
変換結果        ：    １０８，      ５５      ２９９，    １４５
積和演算後      ：  ２４７５，  ２５２５，      ８５，      ５５
第１加算処理後  ：  ２４８０，  ２５３０，      ９０，      ６０
逆数乗算シフト後：    ２４７，    ２５２，        ９，        ５
【００７４】
上記の如く、逆変換処理後のデータは元のデータに一致していることが分かる。ステップＳ６０５における逆数ｒ０、ｒ１の用い方は何種類もあるのは、前記第１実施形態と同様である。
【００７５】
本第２の実施形態も先の第１実施形態で示した図１４と同様、各演算処理を実行する演算器を用意して、図５、図６の処理フローに従って、各演算器にデータを流せば、ロスレスデータ変換処理装置を構成できるのは、これまでの説明からすれば容易に理解できよう。
【００７６】
＜第３の実施形態＞
本第３の実施形態では、ａの値が偶数（２ｎ）の場合に、どのようにしてロスレス変換を実現するのかについて述べる。但しａ＝２（ｎ＝１）の場合は四捨五入（と等価な）処理のみで何の問題もなくロスレス変換を実現できるので、以下ではｎの値が２以上の場合について考える。
【００７７】
ａが偶数の場合、除数（１＋ａ＊ａ）は奇数となるので除算処理の結果、小数点以下の値が０．５になることは無い。よって、ａが奇数の時のような問題は発生しない。しかし、別の新たな問題が発生する。すなわち、四捨五入と同様の処理のみでは、ロスレス変換とはならず、ａが奇数の時のような手法も用いることが出来ない。
【００７８】
ａ＝２ｎ（ｎ≧２）の場合、順変換時の四捨五入処理で発生した丸め誤差が大きいと、逆変換時の四捨五入処理で前記丸め誤差を打ち消すことが出来ず、その結果ロスレス変換にはならなくなってしまう。
【００７９】
これを解決するため、逆変換時の四捨五入処理で順変換の丸め誤差を打ち消すことが出来ないような大きな丸め誤差に対して、四捨五入とは逆の丸め処理を行なう。具体的には、四捨五入では切り捨てられていた小数点以下の値を切り上げ、四捨五入で切り上げられていた小数点以下の値を切り捨てるといった処理を行なう。以下ではこの処理を、通常の四捨五入の丸め処理と区別するため、“逆四捨五入丸め処理”と称す。
【００８０】
逆四捨五入丸め処理の対象となる丸め誤差の範囲は、該丸め誤差の絶対値を除数（１＋ａ＊ａ）倍した値をＴとすると、２ｎ＊ｎ−ｎ＋１≦Ｔ≦２ｎ＊ｎ−１  となる。
【００８１】
概念的には上述した処理内容であるが、丸め誤差を求めるために、一度、四捨五入処理をして、上記逆四捨五入丸め処理の対象となる丸め誤差かどうか判定して、再度丸め処理を行なうのは効率が悪いので、それと等価な処理として、丸め誤差の負号を反転する方向へ、変換結果に１を加減算する処理を行なうのが現実的である。
【００８２】
具体的に、丸め誤差が−（２ｎ＊ｎ−１）の時、これは切り捨て処理されて発生した丸め誤差であることが分かる。この絶対値は逆四捨五入丸め処理の対象内の値であるため、切り捨てとは反対の切り上げ処理を行なうことになる。
【００８３】
切り捨てから切り上げへ変更すると変換結果は１だけ増加するので、結局、丸め誤差が負でその絶対値が逆四捨五入丸め処理の対象内の値であるときは、変換結果を＋１すればよい。同様に、丸め誤差が正（プラス）でその値が逆四捨五入丸め処理の対象内の値であるときは、変換結果を−１すればよいことがわかる。
【００８４】
ここで、逆四捨五入丸め処理の対象となる変換結果は必ず２つ同時に現われることについて説明する。
【００８５】
前記式１の変換処理に四捨五入丸め処理を適用すると、１番目と４番目の変換結果が有する丸め誤差は必ず正負反転する。これは、４番目の変換式を以下のように変形すると明らかである。
2006060703.tif 000007
…（２）
【００８６】
小数点以下の値を発生する最後の項が１番目の変換式とは正負反転していることが分かる。同様に、２番目と３番目の変換結果が有する丸め誤差は必ず同じになる。これは、３番目の変換式を以下のように変形すると明らかである。
2006060703.tif 000008
…（３）
小数点以下の値を発生する最後の項が２番目の変換式と同じになっていることが分かる。
【００８７】
このように、丸め誤差の絶対値が同じものが必ず２つ現われる。即ち、前記逆四捨五入丸め処理の対象となる変換結果は２つ同時に出てくるが、ロスレス変換となるようにするには、２つの内のどちらか一方だけを逆四捨五入丸め処理する。
【００８８】
上述した処理をフローチャートで示したのが図７及び図８である。
【００８９】
同図において、各ステップＳ７０１乃至Ｓ７１７は次の処理である。
Ｓ７０１は、同じ計算の繰り返しを減らすためのパラメータ計算処理、
Ｓ７０３は、４入力ベクトルと整数変換行列の積を計算する積和演算処理
Ｓ７０５は、次の除算処理で四捨五入となるように除数の１／２を加える加算処理、
Ｓ７０７は、値が小さくなる方へ切り捨て除算し変換結果を求める除算処理、
Ｓ７０９は、丸め誤差の除数（１＋ａ＊ａ）倍の値を求める処理
Ｓ７１１は、１番目の変換結果の丸め誤差の絶対値の大きさを判定する処理、
Ｓ７１３は、１番目の変換結果の丸め誤差の負号を判定する処理、
Ｓ７１５は、１番目の変換結果から１を減算する処理、
Ｓ７１７は、１番目の変換結果に１を加算する処理、
Ｓ７２１は、２番目の変換結果の丸め誤差の絶対値の大きさを判定する処理、
Ｓ７２３は、２番目の変換結果の丸め誤差の負号を判定する処理、
Ｓ７２５は、２番目の変換結果から１を減算する処理、
Ｓ７２７は、２番目の変換結果に１を加算する処理。
【００９０】
本実施形態の特徴的な処理は、ステップＳ７０９以降の処理であるので、以下では、ステップＳ７０９以降の処理について説明する。
【００９１】
ステップＳ７０９において丸め誤差を（１＋ａ＊ａ）倍した値を求めるのは、該丸め誤差を整数値として正確な値を得るためである。逆に言うと正確な値が得られるのであれば、必ずしも（１＋ａ＊ａ）倍した値である必要はない。
【００９２】
ここで計算された（１＋ａ＊ａ）倍された２つの丸め誤差Ｅ０，Ｅ１は、ステップＳ７１１、Ｓ７２１にて逆四捨五入丸め処理の対象となる範囲のものであるかどうかを各々判定する。
【００９３】
丸め誤差Ｅ０が逆四捨五入丸め処理の対象となると判定されたら、ステップＳ７１３にてＥ０の正負の符号を判定する。丸め誤差Ｅ０が正であれば、先のステップＳ７０７で求めた変換結果Ｙ０から１を減算し（ステップＳ７１５）、Ｅ０が負であればＹ０に１を加算する（ステップＳ７１７）。
【００９４】
Ｅ０が逆四捨五入丸め処理の対象とならず、Ｅ１が逆四捨五入丸め処理の対象となると判定されたら、同様に、ステップＳ７２３にてＥ１の正負の符号を判定して、Ｅ１が正であれば先のステップＳ７０７で求めた変換結果Ｙ１から１を減算し（ステップＳ７２５）、Ｅ１が負であればＹ１に１を加算する（ステップＳ７２７）。
【００９５】
以上の処理でロスレス変換した結果が得られる。具体的にａ＝８（ｎ＝４）の計算例を以下に示す。４つの入力データＸ０，Ｘ１，Ｘ２，Ｘ３が次のような値の時、四捨五入による変換結果と（１＋ａ＊ａ）倍した丸め誤差は以下のようになる。
【００９６】
参考に該変換結果を単純な四捨五入で丸めて逆変換した時の結果も示す。入力データの値と僅かに違っていることが分かる。
入力データ：        ５，    ３３，    ４３，      ０
変換結果  ：        ９，    ４２，    ３２，    −４
丸め誤差  ：    −２８，  −２９，  −２９，    ２８
逆変換結果：        ５，    ３２，    ４２，      ０  （参考）
【００９７】
先に説明したように、１番目と４番目の丸め誤差は正負反転しており、２番目と３番目の丸め誤差が同じであることが確認できる。２番目の丸め誤差−２９は該絶対値が、３１〜２９（２ｎ＊ｎ−１〜２ｎ＊ｎ−ｎ＋１）の範囲に入っており、負号がマイナスなので、２番目の変換結果に１を加算する。よって、以下のようなロスレス変換結果を得る。
ロスレス変換結果：  ９，    ４３，    ３２，    −４
【００９８】
上記ロスレス変換結果を逆変換して元のデータを復元するための処理は前記図７、図８とまったく同じでる。ステップＳ７０７における逆変換結果、該変換結果の丸め誤差、２番目の変換結果に１を加算した逆変換結果を以下に示す。
逆変換結果（Ｓ７０７）：      ５，    ３２，    ４３，      ０
丸め誤差              ：    −２８，−２９，  −２９，    ２８
逆変換結果（±１後）  ：      ５，    ３３，    ４３，      ０
【００９９】
本実施形態では、１番目の変換結果もしくは２番目の変換結果に逆四捨五入丸め処理をする場合について説明したが、順変換処理と逆変換処理が同じであれば、逆四捨五入丸め処理を行なう対象は１，４番目のどちらか１つと、２，３番目のどちらか１つの組み合せであれば何でもよい。
【０１００】
順変換処理と逆変換処理が同じという条件も、変換式が前記（１）式の場合に言えることであって、変換行列の行の置換操作などを行なうと順変換処理と逆変換処理が同じというわけにはいかなくなる。しかし、変換行列がきちんと定義され、順変換処理が定まれば、ロスレス変換を実現するための逆変換処理も一意に決まる。このような変換行列の置換操作などによる処理の変形は本発明の範疇に属する。
【０１０１】
また、丸め誤差の比較方法には、様々なバリエーションが考えられる。本実施形態では、正確な記述ができる整数演算で処理するため、丸め誤差を除数倍したものを比較処理したが、実際の丸め誤差は小数点以下の値になるので、それを浮動小数点データまたは固定小数点データとして扱い、そのデータタイプで比較する方法も考えられる。さらに、丸め誤差の絶対値での比較結果と丸め誤差の負号の判定結果に基づく分岐は、丸め誤差が負の値に対応する比較処理と正の値に対応する比較処理を行ない、該比較結果に基づいて分岐するようにも変形出来る。
【０１０２】
本実施形態は、データ変換処理方法として説明してあるが、各演算処理を実行する演算器を用意して、図７、図８の処理フローの順に従って、各演算器を接続しデータを処理し、判定処理は比較器で行ない、該比較結果に応じて演算結果をセレクタで切り替えれば、ロスレスデータ変換処理装置を構成できる。これは当業者であれば容易に考えられる構成である。
【０１０３】
＜第４の実施形態＞
上記第３の実施形態では、丸め誤差を求めてその絶対値が逆四捨五入丸め処理の対象範囲かどうかを判定していたが、本第４の実施形態では、前記積和演算処理の結果を除数で割った余り、即ち、除数を法とする剰余を求めて、該剰余から逆四捨五入丸め処理を適用するかどうか判定するものである。
【０１０４】
基本的な考え方は上記第３の実施形態と同じであり、本実施形態は別の処理方法を示すものである。図９に本実施形態のフローチャートを示すが、上記第３の実施形態のＳ７０１〜Ｓ７０７、即ち、図７の部分はまったく同じ処理を行なうので、以下では図８に置き換わる処理を図９に示す。同図における各ステップＳは次の通りである。
Ｓ８０１は、積和演算処理結果に対して除数（１＋ａ＊ａ）を法とする剰余を求める処理、
Ｓ８１１〜Ｓ８１４は、該剰余が逆四捨五入丸め処理に該当するかどうか判定する処理、
Ｓ８２１〜Ｓ８２４は、上記判定結果に対応する逆四捨五入丸めを行なう処理。
【０１０５】
以下で述べる丸め誤差とは、除数（１＋ａ＊ａ）倍した丸め誤差を言う。
【０１０６】
切り捨て処理をした場合、剰余は負の丸め誤差となる。よって負の丸め誤差は剰余の負号を反転したものである。一方、正の丸め誤差は除数から剰余を引いたものである。
【０１０７】
よって、正の丸め誤差（２ｎ＊ｎ−１〜２ｎ＊ｎ−ｎ＋１）を剰余に換算すると、２ｎ＊ｎ＋ｎ〜２ｎ＊ｎ＋２  という範囲になる。この換算した値はステップＳ８１２，Ｓ８１４の判定処理で用いる。
【０１０８】
以下では、図９の各処理について説明する。ステップＳ８０１では、図７の処理結果を受け取り、１番目、２番目の積和演算結果を除数（１＋ａ＊ａ）で、値が小さくなる方向へ切り捨てて除算した結果（別の言い方をすれば、積和演算結果を除数で割ったｆｌｏｏｒ関数値）をＣ０，Ｃ１に求め、それを用いて各々の剰余Ｒ０，Ｒ１を求めている。この計算結果では、被除数が負の場合でも剰余は０以上除数未満の範囲に入る。
【０１０９】
ステップＳ８１１では、負の丸め誤差と仮定した時の前記逆四捨五入丸め処理が必要となる剰余の範囲にＲ０が入っているかどうか判定し、該範囲内であればステップＳ８２１へ行き、切り上げ除算結果を得るため、Ｃ０に１を加算した値でＹ０を更新する。
【０１１０】
ステップＳ８１２では、正の丸め誤差と仮定した時の前記逆四捨五入丸め処理が必要となる剰余の範囲にＲ０が入っているかどうか判定し、該範囲内であればステップＳ８２２へ行き、切り捨て除算結果を得るため、Ｙ０をＣ０に更新する。
【０１１１】
この２つの判定に引っかからない場合、ステップＳ７０７で計算された結果がそのままＹ０の値となる。この値は四捨五入で丸められた値である。
【０１１２】
上記ステップＳ８１１，Ｓ８１２とまったく同様に、剰余Ｒ１に対する判定をステップＳ８１３，Ｓ８１４にて行ない、判定結果に対応してＹ１の更新をＳ８２３，Ｓ８２４にて行なう。
【０１１３】
以上が、本第４の実施形態の処理内容である。得られる結果は上記第３の実施形態と同じであるため、具体的な数値例は省略する。
【０１１４】
＜第５の実施形態＞
本第５の実施形態では、ロスレス４点変換を２次元８×８のロスレスＤＣＴ変換に適用すると共に、符号化処理への応用例を説明する。
【０１１５】
８点ＤＣＴ変換は、アダマール変換といくつかの２点回転変換とに分解されることが知られており、該２点回転変換の中に、π／１６，３π／１６という回転変換がある。そして、この回転変換はＤＣＴ変換処理の最後の処理に位置する。
【０１１６】
２次元ＤＣＴ変換ではアダマール変換と２点回転変換を２方向から行なう必要がある。すなわち、各列データに対する水平方向の変換と、各行データに対する垂直方向の変換である。２次元変換を行列演算で考えると、８×８のデータ行列に対する水平方向の変換はデータ行列の右側から乗算する変換行列で実現され、垂直方向の変換はデータ行列の左側から乗算する変換行列で実現される。
【０１１７】
先に述べたようにＤＣＴ変換処理は、アダマール変換や２点回転変換に分解されるので、それらに対応する複数の変換行列をデータ行列の左右から乗算することで２次元ＤＣＴ変換を実現できる。これら左右から乗算する行列の演算順序は、真中のデータ行列に近い内側から演算すればどのような順序で左右の行列を演算してもよいことは、線形代数における基本的な性質である。よって、前述のπ／１６，３π／１６回転以外の処理をすべて済ませ、最後に２方向からの上記回転変換を行なうことが可能である。
【０１１８】
１方向からのπ／１６，３π／１６という回転処理をシグナルフローグラフで表わしたのが図１０であり、このシグナルフローグラフでπ／１６回転処理されるデータのみを８×８データの中に示したのが図１１（ａ）である。一列中の２つのデータに対して行なう２点回転処理を全８列に適用するため、図１１（ａ）における斜線部のデータが回転処理されることになる。そして、２方向からの回転変換によって処理されるデータは図１１（ｂ）における斜線部のデータとなる。
【０１１９】
同様に、２方向からの３π／１６回転変換によって処理されるデータを表わしたのが図１２の斜線部である。
【０１２０】
図１１（ｂ）、図１２の各々において、２方向からの回転変換が両方行なわれる４つのデータが存在する。該４つのデータに対する変換は、各々４点直交変換になっている。該４つのデータをＸ00，Ｘ01，Ｘ10，Ｘ11とすると、該データに対する２方向からの回転処理は式４のように演算できる。
2006060703.tif 000009
…（４）
式（４）において、α＝cos（π／１６），β＝sin（π／１６）、または、α＝cos（３π／１６），β＝sin（３π／１６）である。
【０１２１】
式４の２次元変換を１次元変換に書き換えると次のようになる。
2006060703.tif 000010
…（５）
さらに、変換行列を上下反転すると次のようになる。
2006060703.tif 000011
…（６）
ここで、 α＝ｍ／√（ｍ2＋ｎ2）、β＝ｎ／√（ｍ2＋ｎ2）とおくと、
2006060703.tif 000012
…（７）
上記式（７）は式（１）において、ａ＝ｎ／ｍと置き、行列の前から掛かる分数の分母と行列内の各要素を各々ｍの二乗倍することによって得られるので、式１の変換と等価であることがわかる。
【０１２２】
ロスレス変換は整数化するための丸め処理が必須であるため、通常の線形変換に対して丸め処理による変換誤差が必ず生じる。ということは、ロスレス変換処理の際に多少の近似計算をしても、その近似による誤差が前記丸め処理による誤差と同程度かそれより小さければ許容される。
【０１２３】
そこで、π／１６回転をtan-1（１／５），３π／１６回転をtan-1（２／３）で近似する。この近似による回転角の誤差は、０．５３３％，−０．１７８％である。一方、２５５レベル値に対する±０．５の丸め誤差の割合は、０．１９６％であり、レベル値が小さい時にはこの割合がレベル値に反比例して増大する。そのような状況から考えると、３π／１６回転をtan-1（２／３）で近似するのはまったく問題がなく、π／１６回転をtan-1（１／５）で近似するのは、従来方式で丸め処理を何回も行なうことを考慮するとほとんど問題がないと言える。
【０１２４】
π／１６回転をtan-1（１／５）で近似した時の４点直交変換行列は、前記式（７）においてｍ＝５，ｎ＝１と置いた行列となり、式（８）に示す変換になる。これは先に説明した第１の実施形態において、ａ＝５と置いた時の変換と同じであるため、第１の実施形態で示した処理方法でロスレス変換が実現できる。
2006060703.tif 000013
…（８）
【０１２５】
一方、３π／１６回転をtan-1（２／３）で近似した時の４点直交変換行列は、前記式（７）においてｍ＝３，ｎ＝２と置いた行列となり、次式（９）のようになる。
2006060703.tif 000014
…（９）
この場合は、変換時も逆変換時も普通に四捨五入すれば、ロスレス変換が実現できる。具体的には、非除数に６を加算して、１３で除算する時に値が小さくなる方向へ切り捨て処理をすればよい。（７）式の変換において、ｍとｎが整数で、その差が１の時は除算時に普通に四捨五入するだけで、整数ベクトルから整数ベクトルへのロスレス変換が実現できる。
【０１２６】
以上で述べたように、２次元８×８のロスレスＤＣＴ変換における処理の一部に、本発明のロスレス４点直交変換が適用できることが理解できよう。
【０１２７】
なお、本願発明者は、２次元８×８ロスレスＤＣＴ変換に最適な２次元４×４ロスレスアダマール変換を既に提案している（特開2004-038451）である。このアダマール変換と本実施形態のロスレス４点直交変換を利用し、他の回転変換には従来方式のロスレス２点回転変換を適用することにより、従来方式より丸め誤差が小さい２次元８×８ロスレスＤＣＴ変換を実現できる。
【０１２８】
上記の８×８ロスレス２次元ＤＣＴ変換を画像データに対して行ない、得られた変換係数を、図１３に示すように、量子化処理、ハフマン符号化処理を行なうと、ＪＰＥＧ符号化データを得ることができる。
【０１２９】
量子化ステップが全て“１”の時にはロスレスＤＣＴ変換係数がそのままエントロピー符号化されるため、ロスレス符号化を行なうことができる。すなわち、復号処理時に、ロスレスＤＣＴ変換に対応する不図示のロスレス逆ＤＣＴ変換を行なえば、完全に元のデータを復元できる。
【０１３０】
また、ロスレス逆ＤＣＴ変換処理機能がない、一般のＪＰＥＧデコーダで復号処理をした場合、完全な元のデータを復元することはできず、前述のロスレス変換処理で発生した丸め誤差が重畳するデータが復元される。しかし、見た目にはこの違いは区別できず、符号化された元の画像を見るだけならほとんど問題はない。
【０１３１】
符号化処理時の量子化ステップを“１”に設定すれば可逆符号化を、“１”より大きく設定すれば劣化のある非可逆符号化を行なうことができ、可逆から非可逆まで連続的に圧縮・伸張画質を制御できることになる。
【図面の簡単な説明】
【０１３２】
【図１】従来からあるロスレス２点直交回転変換処理部の構成を示す図
【図２】従来のロスレス４点直交変換処理部の構成を示す図
【図３】第１実施形態のロスレス変換処理のフローを示す図
【図４】第１実施形態のロスレス変換処理の逆変換処理のフローを示す図
【図５】第２実施形態のロスレス変換処理のフローを示す図
【図６】第２実施形態のロスレス変換処理の逆変換処理のフローを示す図
【図７】第３実施形態のロスレス変換の処理フローを示す図
【図８】第３実施形態のロスレス変換の処理フローを示す図
【図９】第４実施形態のロスレス変換の処理フローを示す図
【図１０】８点ＤＣＴにおけるπ／１６、３π／１６回転処理の位置を示す図
【図１１】８×８データの中でπ／１６回転処理されるデータを示す図
【図１２】８×８データの中で３π／１６回転処理されるデータを示す図
【図１３】符号化処理の構成を示す図
【図１４】第１の実施形態におけるロスレス変換を行う回路構成を示す図である。
【図１】
2006060703.tif 000022
【図２】
2006060703.tif 000023
【図３】
2006060703.tif 000024
【図４】
2006060703.tif 000025
【図５】
2006060703.tif 000026
【図６】
2006060703.tif 000027
【図７】
2006060703.tif 000028
【図８】
2006060703.tif 000029
【図９】
2006060703.tif 000030
【図１０】
2006060703.tif 000031
【図１１】
2006060703.tif 000032
【図１２】
2006060703.tif 000033
【図１３】
2006060703.tif 000034
【図１４】
2006060703.tif 000035