(57)【要約】【課題】  少ない演算量で低遅延な高速ロスレス変換を実現する。そして、このロスレス変換を用いることにより、ロスレス・ロッシー符号化を高速に行なえるようにする。【解決手段】  入力端子に入力したデータＤ0，Ｄ1，Ｄ2，Ｄ3に対し、第１の演算部１１１は、それぞれの入力データに対してそれぞれの重み係数{a0,a1,a2,a3}として{-1/2,-1/2,-1/2,-1/2}を乗じ、その乗じた結果の合算する。また、第１の演算部１１１における丸め処理部１１３は、合算結果を整数化し、その整数化した値Ｅを出力する。第２の演算部１１２は、値Ｅに、入力データ毎に定められた重み係数{b0,b1,b2,b3}としての{1,1,1,1}を乗じ、その乗じた結果をそれぞれの入力データに加算する。そして、第１，第２の重み係数の関係に対して、a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3の値が“−２”又は“０”となるような条件を設定する。【選択図】  図７
2010154328.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力データを入力する入力端子と、複数の変換結果を出力するため出力端子を備えるデータ変換装置であって、
前記入力端子に入力した各入力データに、それぞれに対して設定した第１の重み係数を乗じ、該重み付きデータを合算する第１の演算部と、
該第１の演算部から得られる演算結果に、前記入力データ毎に定められた第２の重み係数を乗じ、当該乗じた結果をそれぞれの入力データに加算する第２の演算部と、
非整数の重み係数を乗ずる前記第１又は第２演算部の少なくとも一方に設けられ、前記非整数の演算結果を整数化する丸め処理部とを備え、
前記入力データ毎の前記第１の重み係数と前記第２の重み係数の積の合計した値が０又は−２とすることを特徴とするデータ変換装置。
【請求項２】
前記入力端子に入力するデータ、及び、前記出力端子から出力する変換データはいずれも整数データであることを特徴とする請求項１に記載のデータ変換装置。
【請求項３】
複数の入力データから、複数の変換データを生成し、出力するデータ変換装置の制御方法であって、
第１の演算手段が、前記入力した各入力データに、それぞれに対して設定した第１の重み係数を乗じ、該重み付きデータを合算する第１の演算工程と、
第２の演算手段が、前記第１の演算工程から得られる演算結果に、前記入力データ毎に定められた第２の重み係数を乗じ、当該乗じた結果をそれぞれの入力データに加算する第２の演算工程と、
非整数の重み係数を乗ずる前記第１又は第２演算工程の少なくとも一方において、丸め処理手段が前記非整数の演算結果を整数化する丸め処理工程とを備え、
前記入力データ毎の前記第１の重み係数と前記第２の重み係数の積の合計した値が０又は−２とすることを特徴とするデータ変換装置の制御方法。
【請求項４】
前記入力データ、前記変換データはいずれも整数データであることを特徴とする請求項３に記載のデータ変換装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データをブロック単位で変換しロスレス符号化とロッシー符号化を統一スキームで処理するために不可欠であるロスレス直交変換において、特に該ロスレス直交変換を構成する各種のロスレス回転変換を実現するための、ｎ次整数データからｎ次整数データへの可逆変換可能なデータ変換技術に関するものである。
【背景技術】
【０００２】
画像、特に多値画像は非常に多くの情報を含んでおり、その画像を蓄積・伝送する際にはデータ量が膨大になってしまうという問題がある。このため画像の蓄積・伝送に際しては、画像の持つ冗長性を除く、或いは画質の劣化が視覚的に認識し難い程度で画像の内容を変更することによってデータ量を削減する高能率符号化が用いられる。
【０００３】
例えば、静止画像の国際標準符号化方式としてＩＳＯとＩＴＵ−Ｔにより勧告されたＪＥＰＧ規格では、画像データをブロックごと（８画素×８画素）に離散コサイン変換（ＤＣＴ）してＤＣＴ係数に変換した後に、各係数を各々量子化し、さらにエントロピー符号化することにより画像データを圧縮している。このＤＣＴを利用した圧縮技術にはＪＰＥＧ以外に、Ｈ２６１，ＭＰＥＧ１／２／４等がある。
【０００４】
ＪＰＥＧ規格において、圧縮・伸長後の画像が元の画像と完全に一致するようロスレス符号化も規格化されたが、当時はロスレス変換技術の研究が進んでおらず、ＤＣＴを用いてロスレス変換を実現することができなかった。そのため、ＤＣＴを用いたブロック変換符号化とは異なる、画素単位の予測符号化という方法でロスレス符号化を実現していた。
【０００５】
その後、ロスレス符号化専用の標準符号化技術（ＪＰＥＧ−ＬＳ）が規格化されたが、ロスレス変換を用いた符号化ではなく、更に後に規格化されたＪＰＥＧ２０００において、初めてロスレス・ウェーブレット変換を用いたロスレス変換符号化が可能になった。このロスレス変換は、整数データ群から整数データ群への可逆な変換である。ロスレス変換を用いた符号化は、変換係数を量子化しなければ文字通りロスレス符号化を行なうが可能になる。また、量子化処理を介在させることにより、ロッシー符号化を行なうことができる。すなわち、同一変換スキームでロスレス符号化とロッシー符号化をシームレスに行なうことができるという利点がある。そのため、ロスレス変換を用いた符号化は、現在国際標準化の作業が進行しているＪＰＥＧ−ＸＲでも用いられている。
【０００６】
ロスレス変換を実現する従来技術の１つとして、ラダー演算（リフティング演算）を用いる方法がある。その代表として非特許文献１が知られている。この非特許文献１では、該ロスレス変換を実現するために、変換行列を三角行列に分解して、それをラダー演算に置き換えるといった複雑な手順で実現している。よって、その構成が複雑になり、演算処理量も多くなってしまう。
【０００７】
また、アダマール変換に限ったロスレス変換手法が、特許文献１に記載されている。この特許文献１に記載の方法は、線形アダマール変換した小数点データの変換係数に対し、奇数個のデータの小数点以下を切り上げ処理し、他の奇数個のデータの小数点以下を切り捨て処理するものである。この特許文献１では、丸め処理の仕方を特徴としており、線形アダマール変換の演算を減らす工夫や丸め処理に要する処理量を減らす工夫などは成されていない。
【特許文献１】特開２００３−２５８６４５号公報
【非特許文献１】福間慎治、大山公一、岩橋政宏、神林紀、“ロスレスアダマール変換を応用したロスレス８点高速離散コサイン変換”、信学技報、ＩＥ９９−６５、ｐｐ．３７−４４、１９９９年１０月
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の通り、これまでのロスレス変換技術は、可逆性を実現するために、ラダー演算で冗長な処理を行なう必要があり、ロスレス変換を使ってロスレス符号化やロッシ−符号化を高速に行なうことの妨げとなっていた。
【０００９】
本願発明は、かかる課題に鑑みなされたものであり、より高速にロスレス変換を行なう技術を提供しようとするものである。
【課題を解決するための手段】
【００１０】
この課題を解決するため、例えば本発明のデータ変換装置は以下の構成を備える。すなわち、
複数の入力データを入力する入力端子と、複数の変換結果を出力するため出力端子を備えるデータ変換装置であって、
前記入力端子に入力した各入力データに、それぞれに対して設定した第１の重み係数を乗じ、該重み付きデータを合算する第１の演算部と、
該第１の演算部から得られる演算結果に、前記入力データ毎に定められた第２の重み係数を乗じ、当該乗じた結果をそれぞれの入力データに加算する第２の演算部と、
非整数の重み係数を乗ずる前記第１又は第２演算部の少なくとも一方に設けられ、前記非整数の演算結果を整数化する丸め処理部とを備え、
前記入力データ毎の前記第１の重み係数と前記第２の重み係数の積の合計した値が０又は−２とすることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、少ない演算量で低遅延な高速ロスレス変換を実現できる。このロスレス変換を用いることにより、ロスレス・ロッシー符号化を高速に行なえるようになる。特に、同一の記述でソフトウェアとハードウェア処理の両方で、高速なロスレスアダマール変換を実現できる演算を可能にした。これは、ソフトウェアとハードウェア開発の共通化が図れる利点がある。
【発明を実施するための最良の形態】
【００１２】
実施形態では、図１に示す構成をベースにしたロスレス変換について説明する。そこで、先ず、図１の構成で実現される変換について詳しく説明する。
【００１３】
図１の装置は、第１の演算部１１１と第２の演算部１１２で構成される。第１の演算部１１１は、入力端子１０１〜１０４から入力される４つのデータＤ0，Ｄ1，Ｄ2，Ｄ3それぞれ各々に重み係数a0，a1，a2，a3を乗じ、その重み付きデータを合算（合計を算出）して、その合算結果Ｅを生成し、出力する。
Ｅ＝a0＊Ｄ0＋a1＊Ｄ1＋a2＊Ｄ2＋a3＊Ｄ3
【００１４】
第２の演算部１１２は該合算結果Ｅに対し、各入力データ毎に設定された第２の重み係数b0，b1，b2，b3を乗じる。第２の演算部１１２は、それぞれを入力データＤ0，Ｄ1，Ｄ2，Ｄ3に乗算結果を加算、すなわち、Ｄ0＋b0＊Ｅ，Ｄ1＋b1＊Ｅ，Ｄ2＋b2＊Ｅ，Ｄ3＋b3＊Ｅを算出し、出力端子１２１〜１２４から出力する。
【００１５】
上記の変換の変換行列は図２のように表わすことができる。この行列式は図３、その逆変の換行列は図４のようになる。ロスレス変換符号化では、変換による冗長性の付加や情報の縮退が発生しないようにするため、行列式Ｔの値は−１または＋１である必要がある。
行列式Ｔの値を−１にするには、a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3＝−２を満たす必要がある。
行列式Ｔの値を＋１にするには、a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3＝０を満たす必要がある。
これが第１の演算部１１１、及び、第２の演算部１１２の重み係数に課せられる設定条件となる。
【００１６】
行列式Ｔの値が−１の時、＋１の時の逆変換行列は図５（ａ）、（ｂ）のようになる。これを見ると、変換行列と逆変換行列との間に興味深い関係があることが分かる。すなわち、行列式Ｔの値が−１の時、変換行列と逆変換行列が完全に一致している。また、行列式Ｔの値が＋１の時、変換行列における２種類の重み係数の内、どちらか一方の重み係数の符号を反転すると逆変換行列になるという点である。
【００１７】
本発明は、このような変換行列（順変換行列）と逆変換行列の類似性を利用して整数データから整数データへの変換における可逆性を実現する。
【００１８】
今、行列式Ｔの値が−１である変換と逆変換を縦属処理して、入力データを変換・逆変換して元の入力データに戻す処理を行なう、図６に示すデータ変換処理に着目する。
【００１９】
このデータ変換処理の結果は、小数データになるのが一般的で、基本的に整数変換にはならない。後述するように、変換側の第１演算部１１１ｆの演算結果と、逆変換側の第１演算部１１１ｒの演算結果は、絶対値が同じで符号が反転しているといった関係がある。この関係を利用して、このデータ変換装置の可逆性を説明することができる。
【００２０】
変換側の第１演算部１１１ｆの演算結果を、第２の演算部１１２ｆが前記第２の重み係数を乗じて、各入力データに加算する。逆変換側では、前記演算結果とは符号が反転している演算結果に、同じ第２の重み係数を乗じて、逆変換入力データに加算する。よって、変換側における加算データと逆変換側における加算データが互いに相殺して、入力データだけが残ると言う訳である。
【００２１】
変換結果は一般的に小数データになるが、該小数データを整数化した場合にも、上記のように「変換における加算データと逆変換における加算データを互いに相殺」させることが出来れば、可逆性を実現することができる。そのためには、変換側の第１演算部１１１ｆの演算結果と、逆変換側の第１演算部１１１ｒの演算結果の符号が反転している関係を、もう少し詳しく解析する必要がある。
【００２２】
図６に示すデータ変換処理において、変換側の第１の演算部１１１ｆの出力から逆変換側の第１の演算部１１１ｒの出力への伝送係数は前述の「a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3＝−２」の関係から−２であることが分かる。
【００２３】
これは、変換側における第１演算部１１１ｆの演算結果Ｅが、この伝送係数により−２Ｅの伝送信号として逆変換側の第１演算部１１１ｒの演算結果に含まれることを意味する。該逆変換側の第１演算部１１１ｒの演算結果には、前記−２Ｅの伝送信号以外に、変換側の入力データに対する逆変換側の第１演算部１１１ｒの演算結果が含まれ、この分の信号は、変換側の第１演算部１１１ｆの演算結果と同様Ｅになる。
【００２４】
よって、逆変換処理における第１演算部１１１ｒの演算結果は最終的に−２Ｅ＋Ｅ＝−Ｅとなり、変換処理における第１演算部１１１ｆの演算結果Ｅとは符号が反転していることが分かる。
【００２５】
整数変換における可逆性を保つには、小数点データを整数に変換した後にも上記伝送係数“−２”を保つ必要があり、そのための丸め処理に関する処理方法として次に説明する３つが考えられる。その３つの方法の違いを対比するため、実施形態の説明に入る前に、ここで３つの方法をまとめて説明する。
【００２６】
１つ目は、小数点以下のデータが発生する重み係数を全て第１の演算部側に集約し、該第１の演算部の最終段の丸め処理部で、小数点データを整数値に丸めた結果を第１の演算手段の演算結果とする。そして、第２の演算部では該演算結果に整数値に限定された第２の重みを乗じて入力データに加算する演算方法である。丸め処理部を有する第１の演算部の構成として、後述する第１の実施形態を表す図７を参照されたい。
【００２７】
このような演算方法で変換と逆変換処理を行なえば、変換側の第１の演算部の出力から逆変換側の第１の演算部における丸め処理部まで、丸め処理を一切しなくて済む。よって、「a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3＝−２」の条件を満たしていれば、変換側の第１演算部の出力を信号源とする伝送値は正確に−２Ｅとなって、逆変換側の第１演算部の丸め処理部に到達する。
【００２８】
この伝送値−２Ｅは、まぎれもなく整数値であり小数点以下のデータを持たないため、丸め処理の対象にはならず、伝送係数は正確に“−２”となり可逆性が保たれる。
【００２９】
２つ目は、第２の重み係数が非整数値である場合の丸め処理の方法である。丸め処理部を有する第２の演算部の構成として、後述する第２の実施形態を表す図８を参照されたい。第２の重み係数を乗じて発生する小数点以下の値を切り捨て、その切り捨てた値を別の信号に重畳して伝送する。逆に切り上げた場合には、切り上げた成分を別の信号から差し引いて重畳して伝送する。
【００３０】
この切り捨て、もしくは、切り上げた成分を別の信号に重畳して伝送する際に、その信号に対する前記第１の重み係数を考慮し、最終的に所望の伝送値となるよう、重畳する値を調整する必要がある。後述する第３の実施形態において、この具体例を述べる。２つ目の方法では、このようにして伝送係数“−２”を正確に実現する。
【００３１】
３つ目も、２つ目と同様、第２の重み係数が非整数値である場合の丸め処理の方法である。２つ目がデータ２つを１組として異なる丸め処理の割り当てを行なったのに対し、それを３つ以上のデータに拡張したのが、この３つ目の処理方法である。この処理は、第１の演算部の演算結果の小数点以下の値が１／ｎずつ増える毎に、ｎ本の信号の内の１つを＋１することにより、１／ｎ単位で信号を伝送する方法である。
【００３２】
例えば、第２の重み係数b0，b1，b2の３つが１／３であった場合、重み係数乗算後、１つは単純に小数点以下を切り捨て、もう１つは１／３を加算後に小数点以下を切り捨て、残りの１つは２／３を加算後に小数点以下を切り捨てて整数化を行なう。これによって、３つの信号を通じて１／３、２／３と言う単位を伝達することができる。
【００３３】
また、第２の重み係数b0とb1の２つが１／２である場合、重み係数乗算後、一方は小数点以下を切り捨て、もう一方は小数点以下を切り上げて整数化すれば、１／２と言う単位を伝達することができる。このように１／ｎという単位をｎ個の信号で伝達することによって、伝送係数“−２”を維持する。
【００３４】
伝送係数が“−２”になるように丸め処理を調整することは、重み係数の値や近似計算の導入などの状況によって、細かい点で異なるため、すべてを網羅して本明細書に記述することは不可能である。しかし、大枠の考え方は、上で述べた３つの方法に大別できる。
【００３５】
以下、本発明に係る実施形態を説明する。
【００３６】
＜第１の実施形態＞
本発明の第１の実施形態におけるデータ変換装置（データ変換回路）の構成を図７、図８に示す。どちらの変換も整数化のための丸め処理を無視した場合、その変換行列は図９に示す行列になる。この変換の物理的な意味は、４つの入力データの直流成分を各入力データから減算するというものである。
【００３７】
圧縮符号化の観点からは、あまり意味のない変換ではあるが、本発明の可逆性を説明するのに適した最もシンプルな変換であるため、本発明の一例として採りあげた。
【００３８】
１つの変換行列に対し、第１の重み係数と第２の重み係数の組み合せが何通りもあり、それに合わせて何種類かの実装形態が存在する。ここでは、代表的な２つの構成を示す。第１の重み係数a0，a1，a2，a3を全て“−１／２”とし、第２の重み係数b0，b1，b2，b3を全て整数値“１”とした時の構成を図７に示す。また、第１の重み係数a0，a1，a2，a3を全て整数値“−１”とし、第２の重み係数b0，b1，b2，b3を全て“１／２”とした時の構成を図８に示す。
【００３９】
図７の可逆性は、前記３つの方法の１つ目によって説明でき、図８の可逆性は、前記３つの方法の３つ目によって説明することができる。
【００４０】
図７、図８の各々において、４つの入力データを上から順に、第１、第２、第３、第４入力データと呼び、各々の演算途中のデータを、第１、第２、第３、第４データと呼ぶことにする。他の実施形態の説明においても同じ呼び方を用いる。
【００４１】
整数化する処理が無ければ、この２つの変換は全く同じであるが、整数化の対象となる信号が異なるため、変換結果が微妙に異なる。
【００４２】
図７の構成では、Ｆ＝a0＊Ｄ0＋a1＊Ｄ1＋a2＊Ｄ2＋a3＊Ｄ3＝（−Ｄ0−Ｄ1−Ｄ2−Ｄ3）／２  を計算するわけであるから、その計算結果Ｆに小数点以下１ビットのデータが発生することがある。このため、これを整数化丸め処理部１１３で整数化したｒｏｕｎｄ（Ｆ）が、第１演算部１１１の出力Ｅとなる。整数化の方法は、逆変換器の整数化と共通であれば、切り捨て・切り上げのどちらでもよい。
【００４３】
該整数化した結果、すなわち、第１の演算部１１１による演算結果Ｅは、第２の重み係数b0，b1，b2，b3をとおして４つの各入力に重畳され、変換結果として、Ｄi’＝Ｄi＋Ｅ（ｉ＝０，１，２，３）を出力する。
【００４４】
該変換結果を逆変換するために、変換処理とまったく同じ処理を行なうと、次のようになる。
ｒｏｕｎｄ（a0＊Ｄ0’＋a1＊Ｄ1’＋a2＊Ｄ2’＋a3＊Ｄ3’）
＝ｒｏｕｎｄ（（−Ｄ0−Ｄ1−Ｄ2−Ｄ3−４Ｅ）／２）
＝ｒｏｕｎｄ（（−Ｄ0−Ｄ1−Ｄ2−Ｄ3）／２−２Ｅ）
＝ｒｏｕｎｄ（（−Ｄ0−Ｄ1−Ｄ2−Ｄ3）／２）−２Ｅ
＝ｒｏｕｎｄ（Ｆ）−２Ｅ
＝Ｅ−２Ｅ
＝−Ｅ
【００４５】
この構成では、変換器の第１演算部１１１の出力から逆変換器の第２演算部の出力への伝送係数は、１×４×（−１／２）＝−２  になるため、逆変換器の第１演算部の出力は上記のように、−Ｅになる。
【００４６】
逆変換器はこの“−Ｅ”に第２の重み係数“１”を乗じた値−Ｅを、該逆変換器の各入力データＤ0’，Ｄ1’，Ｄ2’，Ｄ3’へ加算することにより、元のデータＤ0，Ｄ1，Ｄ2，Ｄ3を復元することができる。
【００４７】
次に、第１の重み係数a0，a1，a2，a3が“−１”、第２の重み係数b0，b1，b2，b3が“１／２”である図８の変換内容について簡単に説明する。
【００４８】
図８の構成では、第２の演算部１１２で第２の重み係数“１／２”を乗ずるため、該第２の演算手段において、第２の重み係数を掛けたデータ毎に丸め処理を行なう必要がある。この丸め処理部が４つ存在することが図８の大きな特徴である。
【００４９】
４つの丸め処理の仕方によって、可逆性を保てたり、保てなかったりすることがある。可逆性を保つには、伝送係数が“−２”である図７の構成と等価な処理を行なうか、或いは、伝送係数が正確に“−２”になるようにする必要がある。
【００５０】
図７の構成と等価な処理とは、４つの丸め処理が全部同じ丸め処理を行なう場合である。すなわち、４つとも一律に切り上げ、もしくは、切り捨て処理を行なう。これは、図７における第１の演算部１１１の丸め処理を、等価な変形によって第２の演算部１１２に移動した場合の構成条件でもある。
【００５１】
可逆性を保つもう１つの方法は、伝送係数が正確に“−２”になるようにすることであり、これは、４つの丸め処理の内、半分の２つを切り捨て、残りの半分の２つを切り上げることによって実現できる。
【００５２】
重み係数“１／２”を乗ずることによって、小数点以下のデータが１ビット発生する可能性がある。該小数点以下のデータを丸め処理によって、正確に伝送できなくなると伝送係数が“−２”でなくなってしまう。だが、この小数点以下１ビットの値を、複数の信号を通してうまく伝送できれば、トータルの伝送係数を“−２”にすることが出来る。
【００５３】
そのためには、２つの信号を１組として一方の丸め処理を切り捨て、もう一方の丸め処理を切り上げる。このように、２つの信号各々で０．５を伝送する代わりに、２つの信号の一方でまとめて１を伝送する。これにより、見かけ上、小数点以下１ビットの値をうまく伝送できる。
【００５４】
上記内容をまとめると、図８の構成において、可逆性のある変換を実現するには、４つの丸め処理の内、偶数個を切り上げ、残りの偶数個を切り捨て処理すればよいと言える。これは、４つの丸め処理の全組み合せ１６通りの内の半分の８通りで可逆性のある変換を行なうことができるということである。
【００５５】
このように比較的単純な変換であっても、可逆性変換が可能な丸め処理のバリエーションが多くあるため、複雑な変換になると、可逆変換可能な丸め処理も複雑になる。その場合でも、基本は、伝送係数を“−２”にすることと、それと等価な処理に変形することである。それによって可逆性を保つことが出来る。
【００５６】
図６、図７及び以上の説明から分かるように、本発明の可逆変換を施した変換データから元のデータを復元するための逆変換は、基本的に変換処理と同じである。
【００５７】
特に、丸め処理が第１の演算部にある場合は、丸め処理を含めて完全に変換と逆変換処理は同じである。たとえ丸め処理が第２の演算部にあっても、前記第１の演算部における丸め処理で置き換えが可能な場合には、該第２の演算部における丸め処理も含めて、変換と同じ処理で逆変換することが出来る。
【００５８】
前記以外で、丸め処理が第２の演算部にある場合には、従来のリフティング演算の逆変換と同じ考え方で丸め処理を行なう。すなわち、変換時のリフティング演算で加算した値と全く同じ値を、逆変換時にも生成し、それを減算することによって元のデータに戻す。
【００５９】
まず、逆変換における第１の演算部の出力（−Ｅ）を−１倍して、変換時の第１の演算部の出力Ｅと同じ値にする。それに第２の重み係数を乗じた後に、変換時の第２の演算部の丸め処理と全く同じ処理を、該逆変換の第２の演算部の丸め処理に適用して、変換時と全く同じ値を生成し、該生成結果を減算する。
【００６０】
図１０（ａ）、（ｂ）に、図７、図８の構成例における具体的な変換データの例を示すので、その可逆性に着目されたい。
【００６１】
＜第１の実施形態の応用例＞
前記第１の実施形態の応用例の装置の構成を図１１に示す。
【００６２】
本応用例は、前記第１の実施形態の構成をそのまま利用し、該構成の前後に僅かな処理を付加することによって、圧縮符号化で最も基本的な変換の１つであるアダマール変換の可逆変換を実現するものである。
【００６３】
図１１は、前記図７に対して、第１の入力データの符号を反転するための第１の符号反転器を設け、該入力データの変換データを出力する際にもう一度符号を反転するために第２の符号反転器を設けたものである。このような構成で変換することによって、４次のロスレスアダマール変換を行なうことが出来る。
【００６４】
第１の符号反転器と第２の符号反転器の働きを行列で表すと、各々、単位行列の第１行第１列要素を符号反転して−１にした行列になる。第１の符号反転器は入力データに、第２の符号反転器は変換出力に作用するため、前記符号反転用の行列を図９に示す変換行列の左右から乗じた結果は、図１２に示すように４次アダマール変換行列になる。これが、図１１に示す構成で実現される変換である。
【００６５】
図８に示す変換器の前後に同じように第１、第２の符号反転器を設けた構成でも、ロスレスアダマール変換が可能であることは説明するまでもない。
【００６６】
＜第２の実施形態＞
本発明の第２の実施形態のデータ変換装置の構成を図１３に示す。該変換の変換行列は前記応用例と同じ図１２に示す式の右辺の行列と同じである。本第２の実施形態は、前記応用例において、入力段と出力段に設けた２つの符号反転器を第１の演算部３０１と第２の演算部３０２で各々吸収し統合したものである。
【００６７】
よって、第１の重み係数a0，a1，a2，a3は各々 1/2，-1/2，-1/2，-1/2であり、第２の重み係数b0，b1，b2，b3は各々 −１，１，１，１である。この時、a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3＝−２であることは言うまでもない。
【００６８】
図１１の構成上で見ると、第１の入力データに対する第１の重み係数と第２の重み係数の符号が各々反転し、重み係数が掛からないデータパス１１５には符号反転器が入ってくる。しかし、入力側からの符号反転器と出力側からの符号反転器が相殺して、該データパス上の符号反転器は結局無くなり、図１３に示す構成となる。
【００６９】
本第２の実施形態の第１の演算部における丸め処理を「切り捨て」とした場合、該第１の演算部の演算結果Ｅは以下のようになる。
Ｅ＝ｒｏｕｎｄ（（Ｄ0−Ｄ1−Ｄ2−Ｄ3）／２）
＝（Ｄ0−Ｄ1−Ｄ2−Ｄ3）＞＞１
この演算結果Ｅを用いて、変換出力は以下のように計算される。
Ｄ0’＝Ｄ0−Ｅ
Ｄ1’＝Ｄ1＋Ｅ
Ｄ2’＝Ｄ2＋Ｅ
Ｄ3’＝Ｄ3＋Ｅ
【００７０】
ロスレスアダマール変換には様々な計算方法があるが、上記計算方法はソフトウェアやハードウェアによる制御の元、いずれでも高速に演算でき、本発明の特徴が最も生かされている。
【００７１】
これまで、ロスレスアダマール変換のソフトウェア、ハードウェアの高速演算法は、どちらか一方のみを高速に演算できるだけであったが、本発明に基づく上記計算方法は両方の処理で高速演算可能である。そのため、ソフト処理とハード処理で同じ計算方法を用いることができる。
【００７２】
さらに、整数化のための丸め処理を行なわない場合、実数演算の４次アダマール変換となるが、該実数アダマール変換も高速に演算が可能である。
【００７３】
先に示した第１実施形態における図８の構成をベースに、上述の符号反転を行なった場合、第１の重み係数a0，a1，a2，a3は各々１，−１，−１，−１であり、第２の重み係数b0，b1，b2，b3は各々 -1/2，1/2，1/2，1/2である。そして、図８と同様に丸め処理は第２の演算部にて行なうことになる。この場合の構成は図１４に示す通りとなる。
【００７４】
図１３の構成における第１演算部の丸め処理を「切り捨て」とした場合、該丸め処理と等価な、図１４の第２演算部の丸め処理は、第１データのみが「切り上げ」、第２〜４データは「切り捨て」となる。
【００７５】
これは、図１２の構成において、第１演算部の丸め処理結果を第１データ系列のみ符号反転しているからである。
【００７６】
同様に、第１演算部の丸め処理を「切り上げ」とした場合、該丸め処理と等価な、図１４の第２演算部の丸め処理は、第１データのみが「切り捨て」、第２〜４データは「切り上げ」となる。これらの丸め処理で変換したデータを、逆変換する場合の丸め処理は、変換時と同じでよい。
【００７７】
一方、図１３とは等価ではない、可逆変換可能な丸め処理は、前記第１の実施形態と同様、多くの種類が存在する。
【００７８】
第１データとペアになるデータは第１データと同じ丸め処理を行ない、残りの２つのデータは互いに反対の丸め処理を行なうことによって、前記伝送係数を“−２”にすることができ、この条件の丸め処理は６種類ある。そして、この場合の丸め処理に対する逆変換は、第１の実施形態と同様、以下のように行う。
【００７９】
逆変換における第１の演算部の出力（−Ｅ）を−１倍して、変換時の第１の演算部の出力Ｅと符号を合わせて同じ値にする。それに第２の重み係数を乗じた後に、変換時の第２の演算部の丸め処理と同じ処理を適用して、変換時と同じ値を再現する。変換時はこの値を入力データに加算してデータ変換しているので、逆変換で同じ値を減算してやれば、元の入力データを復元することができる。
【００８０】
＜第３の実施形態＞
本発明の第３の実施形態のデータ変換装置の構成を図１５と図１６に示す。
【００８１】
図１５と図１６に示す構成は、重み付きの入力データに対して４次ロスレスアダマール変換が可能である。
【００８２】
本第３の実施形態の説明に入る前に、まず、重み付きデータに関して、簡単に説明する。
【００８３】
重み付きのデータは、様々な状況で発生するが、例えば本発明に関連する画像符号化におけるロスレス変換の分野では、少ないリフティング演算でロスレス回転変換を行なおうとすると、その結果、重み付きの変換データが生成される。
【００８４】
一番簡単な例として、４５度回転を２段のリフティング演算で実現する構成を図１８に示す。重みの無いのデータに回転変換する正規変換をリフティング演算で実現するには、３段のリフティング演算が必要であることが知られている。これを２段のリフティング演算で行なうと、重み付きのデータへ変換されてしまう。
【００８５】
図１８の変換によって、生じる重みは（ＣＯＳ４５°，１／ＣＯＳ４５°）、すなわち、（１／√２，√２）である。端子４０２から入力するデータＹｉに、端子４０１から入力するデータＸｉを加算して出力するデータＹｏは、レンジが大きくなり、（√２）の重み付きのデータになる。該データＹｏを１／２倍して、下側のデータから減算して得られるデータＸｏは逆にレンジが小さくなり、（１／√２）の重み付きのデータになる。
【００８６】
従って、仮に（１０、０）の入力データを４５°左方向へ回転した場合、本来は（５√２、５√２）に変換されるべきである。しかし、図１８の構成では最初のリフティング演算で（１０，０＋１０）に変換され、２段目のリフティング演算で（１０−１０／２、１０）＝（５，１０）に変換されてしまい、前記重み付きのデータになってしまう。
【００８７】
このような重み付きの変換を重ねていくと、“２”や“１／２”といった重みが付くことは容易に想像できる。
【００８８】
そこで、本第３の実施形態では、第１〜第４入力データに対し（１，2，1/2，１）という重みが付いたデータに、４次ロスレスアダマール変換を行なうことが可能な構成を２例示す。
【００８９】
図１５に示す構成は、第１の重み係数a0，a1，a2，a3が各々 -1/4，1/8，1/2，1/4であり、第２の重み係数b0，b1，b2，b3が各々 2，-4，-1，-2である。
【００９０】
図１６に示す構成は、第１の重み係数a0，a1，a2，a3が各々 -1/2，1/4，１，1/2であり、第２の重み係数b0，b1，b2，b3が各々 １，-2，-1/2，-１である。
【００９１】
どちらも、a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3＝−２  という条件を満たしている。
【００９２】
図１５の構成は、第２の重み係数が全て整数なので、第１の演算部３０１で丸め処理部を持ち整数化した値を出力すれば、第２の演算部３０２で丸め処理を行なう必要が無い（丸め処理部を持たなくてよい）。この構成は、これまでに説明した実施形態に何度も出てきた構成であり、それらと全く同じ原理でロスレス変換が可能である。
【００９３】
但し、図１５の構成は、一度整数化したデータを第２の演算部３０２で２倍、４倍して用いているため、整数化によってデータに重畳した歪も２倍、４倍されるため、整数化による歪が大きくなってしまう。
【００９４】
上記整数化による歪を小さく抑えたのが、図１６に示す構成である。第１の演算部３１１で整数化したデータを、第２の演算部３１２で２倍にして用いる処理があるが、その箇所は１箇所のみである。
【００９５】
第２の演算部３１２における第２の重み係数の中に、絶対値が１より小さい重み(-1/2)が１つだけ存在し、その係数を乗じた結果を整数化するための丸め処理部が必要になる。よって、図１６に示す構成では、第１の演算部３１１と第２の演算部３１２の両方に丸め処理部を有する。
【００９６】
第２の演算部３１２に存在する丸め処理部の数が１つだけであるため、これまでに説明した実施形態へ適用した手法では、前述の伝送係数を“−２”にすることができず、可逆変換を実現することができない。本実施形態では、前記３つの丸め処理方法の中の２つ目の方法を適用する。
【００９７】
図１６に示す構成で、伝送係数を“−２”にするために、前記第２の演算部の丸め処理部で切り捨てた小数点以下の値を、別のデータに重畳する。もしくは、前記丸め処理部で切り上げた小数点以下の値を、別のデータから減算する必要がある。以下の説明を簡略化するため、前記丸め処理では、小数点以下の値（１／２または０）を切り捨てたものとする。
【００９８】
別のデータに重畳する値は整数値という制限があり、該整数値に1/2 という意味を持たせるには、切り捨てた方のデータと重畳した方のデータとの間で、復号時の第１の重み係数の比が２：１である必要がある。
【００９９】
図１６の構成では、第２の演算部の丸め処理で切り捨てを行なう第３のデータに対し、第４のデータが上記関係を満足している。よって、図１６には示していないが、切り捨てた小数点以下の値を２倍して整数にし、それを第４のデータに加算する。
【０１００】
以上の処理によって、前記伝送係数を“−２”にすることができ、可逆変換が可能になる。最後に、本第３の実施形態におけるデータ変換の例を図１７に示す。
【０１０１】
＜第４の実施形態＞
本発明の第４の実施形態のデータ変換装置の構成を図１９に示す。これまでの実施形態では、４入力データに対する４次変換のみを説明してきたが、本発明は４次変換以外にも適用できる。本実施形態では３次の直交変換の例を示す。
【０１０２】
図１９に示す構成は、第１演算部５１１における第１の重み係数a0，a1，a2は全て 2/3であり、第２演算部５１２における第２の重み係数b0，b1，b2は全て−１である。この重み係数は a0＊b0＋a1＊b1＋a2＊b2＝−２、すなわち、伝送係数は“−２”である。該重み係数によって実現される変換は、図２０に示す変換行列で表すことができる。この変換行列は、各行が直交しており、行毎に要素の二乗和が１であるため、正規直交変換であることが分かる。
【０１０３】
第２の重み係数b0，b1，b2が全て整数であるため、丸め処理は第１の演算部５１１だけで行なうことができ、３による除算が可能な場合は伝送係数を“−２”にすることは容易である。ＰＣ上のソフトウェア処理等では、このような除算が可能である。
【０１０４】
一方、高速処理が要求されるハードウェア処理では、３で割る除算を行なうためにわざわざ除算器で演算することはほとんど無く、乗算で近似計算をすることが多い。この場合、2/3ではなく、その近似値を乗算する。例えば2/3を小数点以下１２ビットまでの値で近似すると1365/2048となり、この値を乗算する。
【０１０５】
一般的には、近似計算を行なうと、３で割り切れる値に対しても、計算誤差が生じ小数点以下のデータが発生する。該近似計算による計算誤差は変換側の第２の重み係数を通して変換出力データに重畳され、逆変換における第１の演算部５１１の出力に伝搬する。
【０１０６】
逆変換における第１演算部の丸め処理は、本来は、元の入力データ成分だけを第１の重み係数を乗じ合算した結果に対してのみ、効くものであるが、前記近似計算による計算誤差が加わるため、丸め処理の影響を把握することは困難になる。
【０１０７】
この状況では、伝送係数が非線形な特性を持ち、定数でなくなってしまうため、もはや−２にすることが出来ない。伝送係数そのものを“−２”にする代わりに、変換側の第１の演算部５１１の出力Ｅに対し、逆変換の第１の演算部の出力が−Ｅになるように演算精度を保つことによって、可逆な変換をできるようにする。
【０１０８】
そのためには、前記2/3の近似精度を上げればよい。変換時の３つの入力データの範囲が０〜２５５の場合、2/3を前述の1365/2048で近似すると、逆変換の第１の演算部の出力が−Ｅになり、可逆な変換が可能になる。当該演算部の出力が前記入力データの範囲内で必ず−Ｅになることを検証するのは容易である。入力データが大きい程、乗算誤差が大きくなるため、入力データが３つとも２５５以下の最大値付近の値で総和が３ｎ、３ｎ＋１、３ｎ＋２の場合に対して、−Ｅになることを確認できればよい。近似精度がこれより１ビットでも低下すると入力データが２５５近辺の値で、前記演算部の出力が−Ｅでなくなるため可逆性が無くなってしまう。ここで伝送係数を“−２”にする場合の可逆性と、前記演算部の出力を−Ｅにする場合の可逆性の違いを述べると、前者の可逆性は入力データの大きさにまったく依存しないのに対し、後者の可逆性は入力データの大きさが所定の範囲内でのみ保証されると言った違いがある。
【０１０９】
３による除算が可能な場合に戻るが、第１の実施形態の前で述べた３つ目の方法、すなわち、３つのデータパスを用いて１／３単位の信号伝送するため、３による除算後の丸め処理を少しずつ変える方法を用いることも可能である。
【０１１０】
＜第５の実施形態＞
本発明の第５の実施形態の構成として、既存のリフティング演算４つを組み合せた構成を図２１に示す。図２１は、伝送係数＝０の第５の実施形態を前段に設け、後段で既存のリフティング演算を行なう構成を付加することにより、ロスレスアダマール変換を実現した構成である。
【０１１１】
図２１における本第５の実施形態の第１演算部６０１の第１の重み係数a0，a1，a2，a3は各々 -1/2，1/2，1/2，1/2であり、第２演算部６０２における第２の重み係数b0，b1，b2，b3は各々 -1，+1，-1，-1である。この重み係数は a0＊b0＋a1＊b1＋a2＊b2＋a3＊b3＝０、すなわち、伝送係数＝０である。該重み係数によって実現される変換は、図２２に示す変換行列で表すことができる。
【０１１２】
図２１に示す変換処理に対応する、逆変換処理の構成は図２３である。これまでに説明した実施形態は伝送係数＝−２の場合のみで、逆変換処理における第１及び第２の重み係数は変換処理と同じであった。しかし、伝送係数＝０の場合は、変換処理と逆変換処理の間に違いがあり、逆変換処理の第２の重み係数は、変換処理の第２の重み係数に対して符号が反転している。それ以外、例えば逆変換処理の第１の演算部は変換処理と同じである。
【０１１３】
伝送係数＝０である本第５の実施形態では、逆変換処理における第１の演算部６０１の出力は、変換処理の第１の演算部６０１の出力と同じである。よって、変換と逆変換の第２の重み係数の関係から、変換時に第２の重み係数を乗じて生成した値に対し、符号を反転した値を逆変換時に生成することができる。それを加算することによって、変換時に加算した値を打ち消し、元のデータを復元することができる。
【０１１４】
ここで、図２１における４つのリフティング演算の意味について説明する。図２２に示す変換行列において、該変換行列の３行目と４行目の両方を、２行目に加算すると共に１行目から減算すると図１２に示す右辺のアダマール変換行列になる。この３行目と４行目を、２行目に加算し、１行目から減算することに対応する処理が、図２１のリフティング演算である。
【０１１５】
伝送係数＝０の構成のみで、有効な変換を実現することは難しいが、既存のリフティング演算と組み合せることによって、４次ロスレスアダマール変換のような有効な変換を実現できることを示した。
【０１１６】
以上で説明したロスレス変換処理（装置）を、例えばＪＰＥＧ符号化で用いられるＤＣＴ変換の一部に用いることによって、ロスレスＤＣＴ変換を高速に演算でき、ロスレスとロッシー圧縮がシームレスに実現できるＤＣＴベースのＪＰＥＧ符号化が高速処理することが可能になる。
【図面の簡単な説明】
【０１１７】
【図１】本発明のロスレス変換の基本となるデータ変換装置のブロック構成図である。
【図２】図１に示す変換処理の変換行列を表す図である。
【図３】図２に示す変換行列の行列式を表す図である。
【図４】図２に示す変換行列の逆行列を表す図である。
【図５】図２の行列式が−１、１の時の図４の逆行列を表す図である。
【図６】図２の行列式が−１の時の可逆性を説明するための図である。
【図７】第１の実施形態のデータ変換装置のブロック構成図である。
【図８】第１の実施形態の他のデータ変換装置のブロック構成図である。
【図９】第１の実施形態の変換内容を表す変換行列を示す図である。
【図１０】第１の実施形態における具体的な変換データの例を表す図である。
【図１１】第１の実施形態の応用例のデータ変換装置のブロック構成図である。
【図１２】図１１の変換内容を表す変換行列を示す図である。
【図１３】第２の実施形態のデータ変換装置のブロック構成図である。
【図１４】第２の実施形態における他のデータ変換装置のブロック構成図である。
【図１５】第３の実施形態のデータ変換装置のブロック構成図である。
【図１６】第３の実施形態の他のデータ変換装置のブロック構成図である。
【図１７】第３の実施形態における具体的な変換データの例を表す図である。
【図１８】２段のリフティング演算を表す図である。
【図１９】第４の実施形態におけるデータ変換装置のブロック構成図である。
【図２０】図１９の変換内容を表す変換行列を示す図である。
【図２１】第５の実施形態におけるデータ変換装置のブロック構成図である。
【図２２】図２１における主要部の変換内容を表す変換行列を示す図である。
【図２３】図２１の逆変換処理を行なうデータ変換装置のブロック構成図である。
【図１】
2010154328.tif 000003
【図２】
2010154328.tif 000004
【図３】
2010154328.tif 000005
【図４】
2010154328.tif 000006
【図５】
2010154328.tif 000007
【図６】
2010154328.tif 000008
【図７】
2010154328.tif 000009
【図８】
2010154328.tif 000010
【図９】
2010154328.tif 000011
【図１０】
2010154328.tif 000012
【図１１】
2010154328.tif 000013
【図１２】
2010154328.tif 000014
【図１３】
2010154328.tif 000015
【図１４】
2010154328.tif 000016
【図１５】
2010154328.tif 000017
【図１６】
2010154328.tif 000018
【図１７】
2010154328.tif 000019
【図１８】
2010154328.tif 000020
【図１９】
2010154328.tif 000021
【図２０】
2010154328.tif 000022
【図２１】
2010154328.tif 000023
【図２２】
2010154328.tif 000024
【図２３】
2010154328.tif 000025