(57)【要約】【課題】  アダマール変換係数のＤＣ係数と３つのＡＣ係数を各々２段の演算で計算して、それら４つの係数を同じタイミングで計算することができ、全体として高速な変換技術を提供する。【解決手段】  加減算部１０６は、入力端子１０１乃至１０４から入力した変換対象の４つの整数データのそれぞれを加減算し、中間データを生成する。減算部１１１は入力端子１０１に入力したデータから中間データを減算してＤＣ係数データを生成し、出力端子１１２より出力する。加算部１１２乃至１１４は、減算部１１１と同じタイミングで、入力端子１０２乃至１０４に入力したそれぞれのデータに中間データを加算してＡＣ係数データを生成し、出力端子１２２乃至１２４から出力する。【選択図】  図１
2011257806.tif 000002
【特許請求の範囲】
【請求項１】
変換対象の４つの整数データから、４つの整数データであって可逆なアダマール変換係数を生成するデータ変換装置であって、
前記変換対象の４つの整数データのそれぞれを加減算することで中間データを生成する中間データ生成部と、
前記中間データ生成部によって生成された中間データを、前記変換対象の４つの整数データそれぞれに加算もしくは減算する中間データ加減算部とを備え、
前記中間データ加減算部で生成された４つの整数データを、可逆なアダマール変換係数として出力することを特徴とするデータ変換装置。
【請求項２】
前記変換対象の４つの整数データに基づいて値が“１”または“０”に確定するオフセット、あるいは、“１”なるオフセットを、前記中間データ生成部における、前記入力した４つの整数データのそれぞれを前記加減算した結果に加算する加算部を有することを特徴とする第１項に記載のデータ変換装置。
【請求項３】
更に、前記変換対象の４つの整数データを逐次入力し、該入力の順序のまま遅延させる、データ遅延手段を有することを特徴とする請求項１または２に記載のデータ変換装置。
【請求項４】
変換対象の４つの整数データから、４つの整数データであって可逆なアダマール変換係数を生成するデータ変換装置の制御方法であって、
中間データ生成部が、前記変換対象の４つの整数データのそれぞれを加減算することで中間データを生成する中間データ生成工程と、
中間データ加減算部が、前記中間データ生成部によって生成された中間データを、前記変換対象の４つの整数データそれぞれに加算もしくは減算する中間データ加減算工程とを備え、
前記中間データ加減算工程で生成された４つの整数データを、可逆なアダマール変換係数として出力することを特徴とするデータ変換装置の制御方法。
【請求項５】
変換対象の４つの整数データから、４つの整数データであって可逆なアダマール変換係数を生成するデータ変換装置であって、
前記変換対象の４つの整数データを互いに加減算し、当該加減算の結果を第１の中間データとして生成する第１の中間データ生成部と、
該第１の中間データ生成部における前記加減算の結果から、前記第１の中間データが示す値に対して差が１以内の値を持つ第２の中間データを生成する第２の中間データ生成部と、
前記変換対象の４つの整数データのうち、２つに対して前記第１の中間データを加算もしくは減算し、残りの２つ対して前記第２の中間データを加算もしくは減算する加減算部とを備え、
前記加減算部で生成された４つの整数データを、可逆なアダマール変換係数として出力することを特徴とするデータ変換装置。
【請求項６】
変換対象の４つの整数データから、４つの整数データであって可逆なアダマール変換係数を生成するデータ変換装置の制御方法であって、
第１の中間データ生成部が、前記変換対象の４つの整数データを互いに加減算し、当該加減算の結果を第１の中間データとして生成する第１の中間データ生成工程と、
第２の中間データ生成部が、該第１の中間データ生成工程における前記加減算の結果から、前記第１の中間データが示す値に対して差が１以内の値を持つ第２の中間データを生成する第２の中間データ生成工程と、
加減算部が、前記変換対象の４つの整数データのうち、２つに対して前記第１の中間データを加算もしくは減算し、残りの２つ対して前記第２の中間データを加算もしくは減算する加減算工程とを備え、
前記加減算工程で生成された４つの整数データを、可逆なアダマール変換係数として出力することを特徴とするデータ変換装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ変換技術、特に、画像データ等の実空間ブロックの整数データから周波数空間ブロックの整数データへの可逆なアダマール変換技術、並びにそれを用いた符号化技術に関するものである。
【背景技術】
【０００２】
静止画像の国際標準符号化方式として勧告されているＪＥＰＧ２０００、並びに、ＪＰＥＧ  ＸＲそれぞれは、同一の符号化スキームで非可逆圧縮、可逆圧縮を実現している。すなわち、実空間から周波数空間への系列変換に、整数演算の可逆変換を適用し、量子化しない、或いは、量子化ステップ“１”で量子化した時の係数をエントロピー符号化すれば可逆圧縮を行うことが可能となる。
【０００３】
ＪＰＥＧ２０００では整数演算の可逆変換として５−３タップのウェーブレット変換が使われている。一方、ＪＰＥＧ  ＸＲでは基本的な変換として整数演算型の可逆アダアール変換が使われている。具体的にはＦＣＴ変換の前半部の変換処理と、ＤＣ係数の演算に使われている。また、旧来のＪＰＥＧ符号化における８×８ＤＣＴを可逆な変換にする際にも、整数演算型の可逆アダマール変換が有効であることが、非特許文献１にて報告されている。
【０００４】
このように、画像に対して系列変換を適用して可逆圧縮を行う際にもっとも基本的な変換の１つが整数演算型の可逆アダマール変換である。該整数演算型可逆アダマール変換の演算方法として、いくつか提案が成されているが、その中で発明者が把握している最も高速と思われるのが、特許文献１に記載されている演算方法である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第４３１１７５９号公報
【非特許文献】
【０００６】
【非特許文献１】福間慎治、大山公一、岩橋政宏、神林紀、“ロスレスアダマール変換を応用したロスレス８点高速離散コサイン変換”、信学技報、ＩＥ９９−６５、ｐｐ．３７−４４、１９９９年１０月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１における整数演算型の４次可逆アダマール変換のＤＣ係数は１段の演算で計算でき高速に出力できるが、残りの３つのＡＣ係数は３段の演算を必要とし、全体としては高速な変換が実現できていなかった。
【０００８】
また、上記変換における丸め処理の方法は、前記ＤＣ係数の切り捨て又は切り上げの２通りしかなく、どちらの丸め処理を用いても、微小電力の変換入力データを可逆アダマール変換すると、該変換に伴う丸め誤差の発生により、逆変換後の係数が分散し電力が増大するという問題があった。
【０００９】
さらに、先行技術を用いて、ブロックデータの２次元変換を行うには、変換途中のデータを一時的に保存して転置するか、転置しない場合には制御が複雑な逐次入力・逐次出力型変換回路を構成する必要があり、２次元変換装置の構成に適した演算ではなかった。
【００１０】
本発明はかかる問題点に鑑みなされたものである。また、本発明は、アダマール変換係数のＤＣ係数と３つのＡＣ係数を各々２段の演算で計算して、それら４つの係数を同じタイミングで計算することにより、全体として高速な変換技術を提供しようとするものである。
【課題を解決するための手段】
【００１１】
この課題を解決するため、例えば本発明のデータ変換装置は以下の構成を備える。すなわち、
変換対象の４つの整数データから、４つの整数データであって可逆なアダマール変換係数を生成するデータ変換装置であって、
前記変換対象の４つの整数データのそれぞれを加減算することで中間データを生成する中間データ生成部と、
前記中間データ生成部によって生成された中間データを、前記変換対象の４つの整数データそれぞれに加算もしくは減算する中間データ加減算部とを備え、
前記中間データ加減算部で生成された４つの整数データを、可逆なアダマール変換係数として出力することを特徴とする。
【発明の効果】
【００１２】
本発明によれば、従来技術より簡易な演算と構成で可逆アダマール変換を実行することができる。
【００１３】
また、本発明特有の丸め処理により、従来技術には無かった特性を持つ可逆アダマール変換を実現でき、微小信号入力時の可逆アダマール変換特性を改善することが可能となった。具体的には、微小信号入力時の信号電力を保存し、係数の分散を抑圧した変換が可能となり、これにより圧縮性能の向上に寄与できる。又、この優位性のある可逆変換を、従来技術と同等程度の回路規模で実現することができる。
【００１４】
さらに、本発明の変換方法によれば、逐次処理用の変換装置と並列処理用の変換装置を構成することが可能であり、ブロックデータを２次元変換する場合、該２種類の変換装置を用いることにより、データの転置が不要な２次元変換装置を構成することが可能である。
【図面の簡単な説明】
【００１５】
【図１】第１の実施形態に記載の可逆アダマール変換装置の構成を表す図。
【図２】第１の実施形態に記載の別の可逆アダマール変換装置の構成を表す図。
【図３】実施形態による可逆アダマール変換の変換結果の一例を示す図。
【図４】第２の実施形態に記載の可逆アダマール変換装置の構成を表す図。
【図５】第２の実施形態に記載の別の可逆アダマール変換装置の構成を表す図。
【図６】実施形態による可逆アダマール変換による逐次変換装置の構成を示す図。
【図７】逐次変換部と並列変換部を用いる２次元可逆アダマール変換装置の構成を示す図。
【図８】可逆アダマール変換の適用が好適な画像符号化装置の構成を示す図。
【図９】２次元可逆アダマール変換の変換結果の一例を示す図。
【発明を実施するための形態】
【００１６】
下記（１）式に示すのは本発明の前提となる４次のアダマール変換の変換行列である。この変換は数学的に可逆な変換であり、変換係数の小数点以下を保持して逆変換すれば必ず元のデータに戻る。本発明のデータ変換装置で行う整数演算型のアダマール変換は、途中の演算過程で小数点以下の数値を一切発生させず、可逆変換が可能な整数のアダマール変換係数を生成する。
2011257806.tif 000003
【００１７】
整数変換係数を生成する可逆な変換は、以下に示す＜変換＞と＜逆変換＞で実現する。本発明の演算処理において、“Ｘ＞＞１”という演算は、複数ビットで構成されるデータＸを右方向（下位方向）に１ビットだけシフトするビットシフト演算を意味する。
＜変換＞
ｔ０＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋ｆ０）＞＞１
ｔ１＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋ｆ１）＞＞１
ｔ２＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋ｆ２）＞＞１
ｔ３＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋ｆ３）＞＞１
Ｅ０＝Ｄ０−ｔ０
Ｅ１＝Ｄ１＋ｔ１
Ｅ２＝Ｄ２＋ｔ２
Ｅ３＝Ｄ３＋ｔ３                …（２）
＜逆変換＞
ｔ０＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３＋ｒ０）＞＞１
ｔ１＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３＋ｒ１）＞＞１
ｔ２＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３＋ｒ２）＞＞１
ｔ３＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３＋ｒ３）＞＞１
Ｄ０＝Ｅ０−ｔ０
Ｄ１＝Ｅ１＋ｔ１
Ｄ２＝Ｅ２＋ｔ２
Ｄ３＝Ｅ３＋ｔ３                …（３）
【００１８】
上記、＜変換＞、＜逆変換＞における〔ｆ０,ｆ１,ｆ２,ｆ３〕，〔ｒ０,ｒ１,ｒ２,ｒ３〕は、それぞれ、変換・逆変換におけるオフセットベクトルと呼ぶ。各要素は、０又は１の値をとる変数である。
【００１９】
この２つのオフセットベクトルが次の関係式を満たすと可逆変換が可能である。その可逆性については各実施形態にて説明する。
〔ｆ０,ｆ１,ｆ２,ｆ３〕−〔１,１,１,１〕・（Σｆｉ）／２＋〔ｒ０,ｒ１,ｒ２,ｒ３〕＝０
ここで、Σｆｉ＝ｆ０＋ｆ１＋ｆ２＋ｆ３である。ｆｉに関する項を右辺へ移動すると、
〔ｒ０,ｒ１,ｒ２,ｒ３〕＝〔１,１,１,１〕・（Σｆｉ）／２−〔ｆ０,ｆ１,ｆ２,ｆ３〕
となる。これによって、変換時のオフセットベクトルから逆変換時のオフセットベクトルを算出することができる。これを要素毎に表したのが下記（４）式である。
ｒｉ＝（ｆ０＋ｆ１＋ｆ２＋ｆ３）／２−ｆｉ  （ｉ＝０，１，２，３）    …（４）
【００２０】
なお、上記＜変換＞、＜逆変換＞におけるｔ０，ｔ１，ｔ２，ｔ３、及び、これに類するデータを以下では、中間データと呼ぶこととする。
【００２１】
以下に説明する各種実施形態にて、上記（２）（３）（４）式に基づくデータ変換処理と変換装置の例を示し、その後に、本発明の変換が逐次処理に適することを示し、最後に、本発明のデータ変換処理とデータ変換装置が有効な画像符号化装置の例を示す。
【００２２】
［第１の実施形態］
第１の実施形態では、オフセットベクトルの各要素が、０又は１の確定した値をとる場合について説明する。前記確定した値とは、オフセットベクトルが入力データに依存して定まる値ではないことを意味する。
【００２３】
まず、ｆ０＝ｆ１＝ｆ２＝ｆ３＝０  のとき、ｒ０＝ｒ１＝ｒ２＝ｒ３＝０  となり、中間データは１つの値ｔで表すことができる。また、この結果、前記（２）（３）式の＜変換＞と＜逆変換＞の演算処理は各々以下のようになる。
＜変換１＞
ｔ＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３）＞＞１
Ｅ０＝Ｄ０−ｔ
Ｅ１＝Ｄ１＋ｔ
Ｅ２＝Ｄ２＋ｔ
Ｅ３＝Ｄ３＋ｔ                ・・・（５）
＜逆変換１＞
ｔ＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３）＞＞１
Ｄ０＝Ｅ０−ｔ
Ｄ１＝Ｅ１＋ｔ
Ｄ２＝Ｅ２＋ｔ
Ｄ３＝Ｅ３＋ｔ                ・・・（６）
【００２４】
上記＜変換１＞に対応する整数演算の可逆アダマール変換装置の回路構成を図１に示す。図示の如く、この装置は、４つ変換対象の整数のデータを入力するデータ入力端子１０１乃至１０４、４つの入力データを加減算する加減算部１０６、ビットシフト部１０８、減算部１１１、加算部１１２乃至１１４、変換結果を出力する出力端子１２１乃至１２４を有する。＜逆変換１＞も図１と同一構成の装置で変換できる。ここで出力端子１２１から出力されるのがロスレスアダマール変換のＤＣ係数であり、残りの出力端子１２２乃至１２４から出力されるのがＡＣ係数となる。なお、図１の構成をハードウェアで構成する場合、ビットシフト部１０８によって発生得る処理遅延は皆無であり、変換処理時間には全くカウントされない。なぜなら、加減算部１０６と、減算部１１１、加算部１１２乃至１１４とを結ぶデータバスの信号線を１本だけ下位にずらして配線するだけで、ビットシフト部１０８と等価の機能を果たせるからである。これは、後述する各実施形態におけるビットシフト部でも同様である。
【００２５】
図１に示す整数演算・可逆アダマール変換装置と上記（５）式に示す＜変換１＞処理は、機能的に同等である。それ故、上記（５）式をベースに変換処理の可逆性について説明する。
【００２６】
変換入力データＤ０乃至Ｄ３の総和が奇数の時、Ｄ０−Ｄ１−Ｄ２−Ｄ３も奇数になる。何故なら、Ｄ０−Ｄ１−Ｄ２−Ｄ３＝（Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３）−２（Ｄ１＋Ｄ２＋Ｄ３）であり、この右辺第２項が偶数であるため、左辺の奇偶性（奇数または偶数である性質）は、右辺第１項の入力データの総和の奇偶性と同じだからである。ちなみに、変換結果の総和は、入力データの総和に２ｔを加算した値になるため、変換結果の総和の奇偶性も同じである。そこで、上記変換の可逆的な性質を、入力データの総和が偶数の場合と奇数の場合に分けて説明する。
【００２７】
＜変換１＞において、Ｄ０−Ｄ１−Ｄ２−Ｄ３が偶数の時、すなわち、入力データの総和が偶数の時、演算による丸め誤差が一切発生しないため、整数演算であっても“数学的に可逆”な変換が行われる。逆に、入力データの総和が奇数の時、ビットシフト演算により切り捨ての丸め誤差が発生する。
【００２８】
そこで、総和が奇数の入力データを〔ｄ０,ｄ１,ｄ２,ｄ３〕＋〔１,０,０,０〕と表すと、〔ｄ０,ｄ１,ｄ２,ｄ３〕の総和は偶数になるため、前記整数演算にて可逆変換が可能である。前記入力データを〔ｄ０,ｄ１,ｄ２,ｄ３〕に〔１,０,０,０〕が重畳したデータとして解釈すると、〔１,０,０,０〕の重畳の有無にかかわらずtの値は同じである。よって、〔１,０,０,０〕が重畳しても、変換結果のＥ１，Ｅ２，Ｅ３の値は変わらず、Ｅ０のみが１増加することが分かる。
【００２９】
したがって、〔ｄ０,ｄ１,ｄ２,ｄ３〕に〔１,０,０,０〕を重畳したデータを変換すると〔ｄ０,ｄ１,ｄ２,ｄ３〕に対する変換結果に〔１,０,０,０〕を重畳した変換結果が得られる。逆変換結果にも同様に〔１,０,０,０〕が重畳して、元の入力データである〔ｄ０,ｄ１,ｄ２,ｄ３〕＋〔１,０,０,０〕に戻る。
【００３０】
以上より、総和が奇数の入力データ及び総和が偶数の入力データのいずれにおいても＜変換１＞と＜逆変換１＞によって可逆な変換が実現される。
【００３１】
次に、ｆ０＝ｆ１＝ｆ２＝ｆ３＝１  のとき、ｒ０＝ｒ１＝ｒ２＝ｒ３＝１  となり、前の変換と同様、中間データは１つの値ｔで表すことができ、前記（２）（３）式の＜変換＞と＜逆変換＞の演算処理は各々以下のようになる。
＜変換２＞
ｔ＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋１）＞＞１
Ｅ０＝Ｄ０−ｔ
Ｅ１＝Ｄ１＋ｔ
Ｅ２＝Ｄ２＋ｔ
Ｅ３＝Ｄ３＋ｔ
＜逆変換２＞
ｔ＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３＋１）＞＞１
Ｄ０＝Ｅ０−ｔ
Ｄ１＝Ｅ１＋ｔ
Ｄ２＝Ｅ２＋ｔ
Ｄ３＝Ｅ３＋ｔ
【００３２】
入力データの総和の奇偶性と変換結果の総和の奇偶性との関係は、前述の＜変換１＞、＜逆変換１＞と場合と同じである。同様に、変換の可逆性についても、入力データの総和が偶数の場合と奇数の場合に分けて説明する。
【００３３】
上記＜変換２＞において、Ｄ０−Ｄ１−Ｄ２−Ｄ３が偶数の時、ビットシフト演算の前に行う演算“＋１”はビットシフト演算によって切り捨てられ、中間データの値は前記＜変換１＞と同一となる。また、変換結果の総和も偶数となるため、逆変換の結果も前記＜変換１＞と同一となり、元の入力データに戻る。
【００３４】
次に、総和が奇数の入力データを〔ｄ０,ｄ１,ｄ２,ｄ３〕−〔１,０,０,０〕と表す。総和が偶数である〔ｄ０,ｄ１,ｄ２,ｄ３〕項は、既に説明したように＜変換２＞にて可逆変換が可能である。
【００３５】
同様に入力データを〔ｄ０,ｄ１,ｄ２,ｄ３〕に〔−１,０,０,０〕が重畳したデータとして解釈する。この場合、第１要素の“−１”と前記中間データの計算における“＋１”とが相殺し〔ｄ０,ｄ１,ｄ２,ｄ３〕入力時と同一の中間データtが得られ、Ｅ１，Ｅ２，Ｅ３の値は変わらず、Ｅ０のみが１減少する。
【００３６】
すなわち、〔ｄ０,ｄ１,ｄ２,ｄ３〕に〔−１,０,０,０〕を重畳したデータを変換すると〔ｄ０,ｄ１,ｄ２,ｄ３〕に対する変換結果に〔−１,０,０,０〕を重畳した変換結果が得られる。逆変換結果にも同様に〔−１,０,０,０〕が重畳して、元の入力データである〔ｄ０,ｄ１,ｄ２,ｄ３〕＋〔−１,０,０,０〕に戻る。
【００３７】
したがって、総和が奇数の入力データ及び偶数の入力データのいずれにおいても＜変換２＞と＜逆変換２＞によって可逆な変換が実現される。
【００３８】
ちなみに、＜変換２＞と＜逆変換２＞に対応する変換装置の構成は、前記図１の構成において、加減算部１０６とビットシフト部１０８との間に“＋１回路”を設けて、“１”を加算するだけである。
【００３９】
次に、ｆ０＝ｆ１＝１，ｆ２＝ｆ３＝０の場合について考える。前記（４）式より、ｒ０＝ｒ１＝０，ｒ２＝ｒ３＝１となる。中間データは２つの値ｔ０，ｔ１で表され、前記（２）（３）式の＜変換＞と＜逆変換＞の演算処理は各々以下のようになる。
＜変換３＞  （図２は該変換の変換装置に対応）
ｔ０＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３）＞＞１
ｔ１＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋１）＞＞１
Ｅ０＝Ｄ０−ｔ１
Ｅ１＝Ｄ１＋ｔ１
Ｅ２＝Ｄ２＋ｔ０
Ｅ３＝Ｄ３＋ｔ０
＜逆変換３＞
ｔ０＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３）＞＞１
ｔ１＝（Ｅ０−Ｅ１−Ｅ２−Ｅ３＋１）＞＞１
Ｄ０＝Ｅ０−ｔ０
Ｄ１＝Ｅ１＋ｔ０
Ｄ２＝Ｅ２＋ｔ１
Ｄ３＝Ｅ３＋ｔ１
【００４０】
総和が偶数の入力データに対しては、前記＜変換１＞＜変換２＞と同様に、可逆な整数変換が可能であることが容易に類推できるため、総和が奇数の入力データについてのみ説明する。
【００４１】
＜変換３＞において、総和が奇数の入力データを〔ｄ０,ｄ１,ｄ２,ｄ３〕＋〔１,０,０,０〕と表し、第２項を重畳データと解釈する。
【００４２】
前記重畳データにより、２種類ある中間データのうち、ｔ１は１増加するが、ｔ０は変化せず同じ値のままである。よって、変換係数Ｅ０に着目すると、重畳データによりＤ０は＋１されるものの、中間データｔ１は−１され、これらが相殺して結果的に変換係数Ｅ０の値は変わらない。それに対し、変換係数Ｅ１は中間データｔ１によって＋１される。一方、変換係数Ｅ２，Ｅ３は、中間データｔ０が同じ値のままなので、変化しない。結局、重畳データ〔１,０,０,０〕により、変換係数は〔０,１,０,０〕だけ変化する。
【００４３】
逆変換側では、変換係数における前記変化分〔０,１,０,０〕を重畳係数と解釈し、それに対する変化量を調べる。該重畳係数により、逆変換の中間データは、ｔ０が１減少するが、ｔ１は不変である。
【００４４】
よって、逆変換データＤ０は、中間データｔ０を通して＋１される。それに対し、逆変換データＤ１は重畳係数により＋１、中間データｔ０により−１され、これらが相殺して結果的に値は変わらない。一方、逆変換データＤ２，Ｄ３は、中間データｔ１が同じ値のままなので、変化しない。結局、重畳係数〔０,１,０,０〕により、逆変換データは〔１,０,０,０〕だけ変化する。
【００４５】
入力から逆変換データまで通してみると、入力データに重畳するデータ〔１,０,０,０〕によって、変換係数が〔０,１,０,０〕だけ変化し、これによって、逆変換データが〔１,０,０,０〕だけ変化する。真に、入力データに重畳された成分だけ逆変換データが変化する。したがって、総和が奇数のデータに対しても可逆な変換が可能である。
【００４６】
上記＜変換３＞と＜逆変換３＞に対応する変換装置の構成は、図１の構成に対し、加減算部１０６の出力に１を加算する “＋１回路”２０１と、該加算結果を１ビット右シフトするビットシフト部２０３を設けた、図２に示す構成となる。新たに設けたビットシフト部２０３の出力は減算部１１１と加算部１１２に供給される。図１の構成が１つの中間データ生成部を有していたのに対して、図２の構成は第１の中間データを生成する第１の中間データ生成部、並びに、第１の中間データの値に対してその差が１以内の値を持つ第２の中間データを生成する第２の中間データ生成部を有する点が異なる。
【００４７】
以上の第１の実施形態ではオフセットベクトルとして、〔０,０,０,０〕, 〔１,１,１,１〕, 〔１,１,０,０〕の３つを示した。可逆変換が可能なオフセットベクトルは全部で８種類あり、その８種類とは〔０,０,０,０〕, 〔０,０,１,１〕, 〔０,１,０,１〕, 〔１,０,０,１〕, 〔０,１,１,０〕, 〔１,０,１,０〕, 〔１,１,０,０〕, 〔１,１,１,１〕である。ベクトル要素中の１の数が偶数個であることが特徴である。
【００４８】
これらのベクトルデータを〔ｆ０,ｆ１,ｆ２,ｆ３〕として、前記（４）式に代入すると、０，１要素のみからなる逆変換用のオフセットベクトル〔ｒ０,ｒ１,ｒ２,ｒ３〕が得られる。その特徴を簡単に述べると、要素が全部０又は全部１のベクトルは、変換用と逆変換用のオフセットベクトルが同じであり、それ以外のベクトルは０と１が反転する関係にある。１要素の数が奇数個のオフセットベクトルを用いて変換すると、変換結果が縮退し可逆ではなくなってしまう。これに対応して、前記（４）式で計算される逆変換用のオフセットベクトルの各要素は非整数値となり、０，１要素から成る解が得られなくなる。
【００４９】
前記＜変換３＞と＜逆変換３＞では中間データｔ０，ｔ１の演算に冗長な記述をしたが、これはｔ０とｔ１の違いが分かり易いようにするためである。ｔ０とｔ１を効率的に演算する方法の１つとして次の演算が考えられる。
ｓ＝Ｄ０−Ｄ１−Ｄ２−Ｄ３
ｔ０＝ｓ＞＞１
ｔ１＝（ｓ＋１）＞＞１    又は、  ｔ１＝ｔ０＋（ｓ ＆ １）
上記演算における（ｓ ＆ １）は、ｓと値“１”の論理積を示すものであり、平たく言えばｓのＬＳＢ（最下位ビット）を抽出する演算ということができる。
【００５０】
本実施形態で説明した各種変換処理・変換装置は各々に種々の変形が可能である。これまでに説明した変換では、中間データは、Ｄ０−Ｄ１−Ｄ２−Ｄ３  という演算で計算しているが、該演算の符号を反転して、−Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３  に置き換えることができる。この時、以下に示すように、該中間データと入力データ間の演算の符号も反転する。
＜変換４＞
ｔ＝（−Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３）＞＞１
Ｅ０＝Ｄ０＋ｔ
Ｅ１＝Ｄ１−ｔ
Ｅ２＝Ｄ２−ｔ
Ｅ３＝Ｄ３−ｔ
【００５１】
上記＜変換４＞は＜変換２＞と同じ結果になることを確認しており、前記＜逆変換２＞によって、元のデータに戻すことができる。もちろん、Ｅｉ（ｉ＝０，１，２，３）をＤｉに代入した後、＜変換４＞を再度適用して逆変換を行うことにより元のデータを復元することができる。
【００５２】
別の変形として、入力データの置換が考えられる。これまでに説明した変換は全て、４つの入力データの中で、Ｄ０のみが特別で、他のＤ１，Ｄ２，Ｄ３とは異なる符号で合算し、中間データを計算していた。前段の処理の都合によって、その特別なデータが例えばＤ２として入力されるようなシステムも有り得る。その場合の変換は以下のようになる。
＜変換５＞
ｔ＝（−Ｄ０−Ｄ１＋Ｄ２−Ｄ３）＞＞１
Ｅ０＝Ｄ０＋ｔ
Ｅ１＝Ｄ１＋ｔ
Ｅ２＝Ｄ２−ｔ
Ｅ３＝Ｄ３＋ｔ
【００５３】
この変換に対しては、ＥｉをＤｉに代入後、上記＜変換５＞で逆変換が可能であることを確認している。一方、前記（１）式による変換と入力データの符号を合せるために、変換結果を置換・符号反転して＜変換５＞を＜変換６＞のように変形することも出来る。この２つの変換の違いは、＜変換５＞ではＤＣ係数がＥ２に得られたが、＜変換６＞は＜変換１〜４＞と同様、Ｅ０にＤＣ係数が得られる点である。この＜変換６＞の逆変換は、オフセット（ベクトル）を０と１の間で反転させれば対応できる。
＜変換６＞
ｔ＝（−Ｄ０−Ｄ１＋Ｄ２−Ｄ３）＞＞１
Ｅ０＝  Ｄ２−ｔ
Ｅ１＝−Ｄ３−ｔ
Ｅ２＝  Ｄ０＋ｔ
Ｅ３＝−Ｄ１−ｔ
＜逆変換６＞
ｔ＝（−Ｅ０−Ｅ１＋Ｅ２−Ｅ３＋１）＞＞１
Ｄ０＝  Ｅ２−ｔ
Ｄ１＝−Ｅ３−ｔ
Ｄ２＝  Ｅ０＋ｔ
Ｄ３＝−Ｅ１−ｔ
【００５４】
［第２の実施形態］
第２の実施形態では、前記（２）（３）式におけるオフセットが０又は１といった固定の数値ではなく、入力データに依存して、０又は１のオフセットが確定する。この例を２つ示す。
【００５５】
該２つの例の概略を簡単に述べると、１つ目は、４つの入力データの加減算結果の下位ビットに依存して、オフセットが０又は１の値をとるものである。後述する２つ目は、４入力データ中の２データ間の差分の下位ビットに依存するものである。以下、詳細説明に入る。
【００５６】
１つ目のオフセットは次のようなものである。変換時のオフセットは、ｆ０＝ｆ１＝ｆ２＝ｆ３＝（（Ｄ０−Ｄ１−Ｄ２−Ｄ３）＞＞１） ＆ １ と計算し、変換結果をＥ１，Ｅ２，Ｅ３，Ｅ４と表した時、逆変換時のオフセットは、ｒ０＝ｒ１＝ｒ２＝ｒ３＝（（Ｅ０−Ｅ１−Ｅ２−Ｅ３）＞＞１） ＆ １ と計算する。
【００５７】
変換と逆変換の２つのオフセットは別のデータから計算するが、変換と逆変換でオフセットが同一の値（０又は１）になることを確認しており、それによって、可逆な変換が実現される。
【００５８】
このオフセットを用いた丸め処理により、微小信号入力時の電力を変換後に保存するような可逆変換が可能になる。本第２の実施形態による＜変換７＞の変換結果と既存の切り捨て・切り上げによる変換結果、それと実数演算結果を合せて図３に示す。
【００５９】
アダマール変換は正規直交変換であるため、小数点以下の値を保持する実数演算で変換すれば、入力信号のパワーは出力の変換係数に保存されて当然である。しかし、整数データから整数係数への可逆変換では、入力信号のパワーが出力の変換係数に保存されないことが図３における＜変換１＞＜変換２＞の欄から見てとれる。
【００６０】
さらに、図３の変換結果から次のことが言える。パワーが“１”の入力データを＜変換１＞＜変換２＞の方法で変換した場合、２つの変換結果の一方は、入力データと同一で、もう一方は、変換の結果パワーが３倍になっている。
【００６１】
どちらの変換結果が、正しい変換結果である実数演算結果に近いとも言い切れないため、符号化上の観点からは、パワーの増加や有意係数の増加を抑制することが望まれる。すなわち、パワーが“１”の入力データは変換しないことが望まれる。
【００６２】
本実施形態では、パワーが“１”の入力データを変換しないように、中間データｔが“０”になるようにしている。但し、既存の丸め処理において、入力パワーが“１”の時だけ単純に中間データを“０”にしても、変換係数の縮退が発生し、可逆性が損なわれる。本実施形態では中間データを偶数化する丸め処理によって変換係数の縮退を防ぎ、可逆性を維持している。
【００６３】
ここで、Ｄ０−Ｄ１−Ｄ２−Ｄ３＝ｓ  と置くと、前述のオフセットによる丸め処理は次のように表現することができる。
・ｓの下位２ビットが“１１”の時に切り上げて中間データｔを生成する。
・ｓの下位２ビットが“０１”の時に切り捨てて中間データｔを生成する。
さらに言い換えると、この丸め処理は、中間データが２で割り切れない時に、偶数になるように整数化を行うものである。具体的な変換処理と逆変換処理を以下に示す。変換と逆変換における入力データの合算値を区別するため、以下のように表記した。
＜変換７＞  （対応する変換装置の構成は図４）
ｓ＝Ｄ０−Ｄ１−Ｄ２−Ｄ３
ｔ＝（ｓ＋（（ｓ＞＞１） ＆ １））＞＞１
Ｅ０＝Ｄ０−ｔ
Ｅ１＝Ｄ１＋ｔ
Ｅ２＝Ｄ２＋ｔ
Ｅ３＝Ｄ３＋ｔ
＜逆変換７＞
ｕ＝Ｅ０−Ｅ１−Ｅ２−Ｅ３
ｔ＝（ｕ＋（（ｕ＞＞１） ＆ １））＞＞１
Ｄ０＝Ｅ０−ｔ
Ｄ１＝Ｅ１＋ｔ
Ｄ２＝Ｅ２＋ｔ
Ｄ３＝Ｅ３＋ｔ
【００６４】
上記＜変換７＞と＜逆変換７＞の可逆性の説明のために、総和が奇数の４入力データ〔Ｄ０,Ｄ１,Ｄ２,Ｄ３〕を〔ｍ０,ｍ１,ｍ２,ｍ３〕＋〔±１,０,０,０〕と表す。ここで、（ｍ０−ｍ１−ｍ２−ｍ３） ｍｏｄ ４＝０、言い換えると、合算値（ｍ０−ｍ１−ｍ２−ｍ３）を４で割った余りは０である。すなわち、４入力データを、前記性質を有するデータ〔ｍ０,ｍ１,ｍ２,ｍ３〕と、それ以外の成分〔±１,０,０,０〕とに分離し、両者の和で表す。
【００６５】
まず、データ〔ｍ０，ｍ１，ｍ２，ｍ３〕を入力して変換した場合、該入力データの合算値ｓに対し、ｓ  ｍｏｄ  ４＝０  が成り立っている。次に、該〔ｍ０,ｍ１,ｍ２,ｍ３〕を変換した結果を逆変換した時の合算値ｕが、ｕ  ｍｏｄ  ４＝０となる理由を示す。〔ｍ０,ｍ１,ｍ２,ｍ３〕を変換した時の中間データｔは４つの入力データの各々に加減算して重畳され、変換時の合算値ｓに対し逆変換の合算値ｕは４ｔだけ小さくなる。すなわち、ｕ＝ｓ−４ｔ  である。
【００６６】
よって、ｓ  ｍｏｄ  ４＝０  なら、ｕ  ｍｏｄ  ４＝０  になる。この関係は、中間データtが１種類であれば、そのｔの生成方法に依存すること無く成り立ち、変換時の丸め処理（偶数化）が逆変換時でも有効であることが分かる。
【００６７】
なお、〔ｍ０，ｍ１，ｍ２，ｍ３〕に対してはもちろん、総和が偶数のデータに対する変換処理では丸め誤差が一切発生しないため、数学的（理論的）な可逆性に基づいて、可逆な変換が行われる。
【００６８】
次に、総和が奇数の入力データ、すなわち、〔ｍ０,ｍ１,ｍ２,ｍ３〕＋〔±１,０,０,０〕の場合であるが、第１の実施形態でした説明と同様に、入力データの変換結果は、〔ｍ０,ｍ１,ｍ２,ｍ３〕の変換結果に〔±１,０,０,０〕を重畳した値になる。何故なら、入力データに重畳された〔±１,０,０,０〕による中間データtへの影響は、前記偶数化処理に吸収されてしまい、中間データtの変化として現れないからである。よって、前記重畳成分によってＤ０のみが変化し、該Ｄ０を通してＥ０に重畳成分が伝搬する。
【００６９】
そして、逆変換の結果も同様に、〔ｍ０,ｍ１,ｍ２,ｍ３〕＋〔±１,０,０,０〕となり、元の入力データに戻る。したがって、総和が偶数、奇数いずれの場合においても、可逆な変換が行われると言える。
【００７０】
上記＜変換７＞の演算を行なう回路構成を図４に示す。図１に示した構成に対し、合算器１０６とビットシフト部１０８の間に、前記（ｓ＞＞１） ＆ １を演算するビット演算部４０１と該ビットデータを加算する加算器４０３を設けたのが特徴である。
【００７１】
一方、中間データｔの演算は、前記演算方法以外に次の演算でも可能であることを確認している。
ｔ＝（ｓ＞＞１）＋（ｓ＞＞１） ＆ ｓ ＆ １
以上で、１つ目のオフセットに関する説明を終える。
【００７２】
次に２つ目のオフセットについて説明する。２つ目は、変換時のオフセットを、ｆ０＝ｆ１＝ｆ２＝ｆ３＝（Ｄ０−Ｄ１） ＆ １ と設定し、逆変換のオフセットも同様に、ｒ０＝ｒ１＝ｒ２＝ｒ３＝（Ｄ０−Ｄ１） ＆ １ とする。
【００７３】
ここでは、変換と逆変換の演算を区別せず一緒に説明するため、変換処理と逆変換処理の記述を統一した。
＜変換８＞  （図５に対応する変換装置の構成を示す）
ｔ＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋（（Ｄ０−Ｄ１） ＆ １））＞＞１
Ｅ０＝Ｄ０−ｔ
Ｅ１＝Ｄ１＋ｔ
Ｅ２＝Ｄ２＋ｔ
Ｅ３＝Ｄ３＋ｔ
＜逆変換８＞
・変換後のＥｉがＤｉ（ｉ＝０，１，２，３）に代入されているものとする
ｔ＝（Ｄ０−Ｄ１−Ｄ２−Ｄ３＋（（Ｄ０−Ｄ１） ＆ １））＞＞１
Ｅ０＝Ｄ０−ｔ
Ｅ１＝Ｄ１＋ｔ
Ｅ２＝Ｄ２＋ｔ
Ｅ３＝Ｄ３＋ｔ
【００７４】
上記変換および逆変換における中間データｔの演算式中のオフセットは、次の式を変形して得られたものである。
ｔ＝（（Ｄ０−Ｄ１＋１）＞＞１）＋（（−Ｄ２−Ｄ３）＞＞１）
【００７５】
上記演算は、Ｄ０−Ｄ１が奇数なら該第１項を切り上げ、−Ｄ２−Ｄ３が奇数なら該第２項を切り捨てるものである。２つの項が両方とも偶数なら丸め誤差は一切発生しないが、両方とも奇数の場合は第１項を切り上げて、第２項を切り捨てるため丸め誤差が相殺して結果的に丸め誤差は無くなる。
【００７６】
上記２つの項を１つにまとめたのが＜変換８＞＜逆変換８＞における中間データのオフセット演算式である。また、該オフセット演算式（（Ｄ０−Ｄ１） ＆ １）は、各データの最下位ビット間の排他的論理和演算、すなわち、（Ｄ０ ＆ １）ＸＯＲ（Ｄ１ ＆ １）によって演算することもできる。図５に示す可逆アダマール変換装置では、入力データの最下位ビット間の排他的論理和演算によって、オフセットを計算している。図中の５０１が排他的論理和演算部である。
【００７７】
該オフセットを用いた丸め処理により、当該変換係数に重畳する丸め誤差の分布が±対称となり、データの下位ビットに相関が無ければ、丸め誤差の偏りが無くなる。
【００７８】
これまでの整数演算型可逆アダマール変換では、丸め誤差が一方向に偏っていたため、圧縮画像の復号過程で行う逆量子化時に、この偏りを補正していた。具体的には、逆量子化前の量子化係数に偏りを打ち消す小数値を加算してから逆量子化をし、そのために、演算ビット数を数ビット増やす必要があった。重畳する丸め誤差に偏りが無ければ、補正のために演算ビット数を増やす必要が無いという利点がある。
【００７９】
前記オフセット演算式（（Ｄ０−Ｄ１） ＆ １）は、これまでに説明してきたオフセットとして解釈することができ、変換時のオフセットが決まれば、それを逆変換するオフセットが、前記（４）式により、一意に決まる。
【００８０】
前記（４）式のｆｉ（ｉ＝０，１，２，３）に（（Ｄ０−Ｄ１） ＆ １）を代入すれば、ｒｉ（ｉ＝０，１，２，３）も（（Ｄ０−Ｄ１） ＆ １）になる。
【００８１】
上記の例では、４つのオフセットは全て同じであるが、先の第１の実施形態で示したように、オフセットは必ず全て同じである必要は無い。４つのオフセットを２つずつの２グループに分けた一方のグループのみを上記オフセットとし、もう一方のグループのオフセットを０に設定しても可逆な変換が可能である。
【００８２】
但し、変換時の（Ｄ０−Ｄ１）の奇偶性と、逆変換時の（Ｄ０−Ｄ１）の奇偶性を一致させておく必要がある。もし前記奇遇性が変わり、オフセットの値が逆変換時に変わってしまうと可逆変換にならなくなるからである。該（Ｄ０−Ｄ１）の奇偶性を保つためには、オフセットを、ｆ０,ｆ１のグループと、ｆ２,ｆ３のグループに分ける必要がる。
【００８３】
［第３の実施形態］
アダマール変換はブロックデータに対する変換であるため、一般的には、変換入力データを並列に入力して、変換係数を並列に出力するハードウェア実装が採られる。これまでに示した図１、図２、図４、図５の構成はこれに該当する。
【００８４】
本発明の整数演算の可逆アダマール変換方法は、もちろん並列入力・並列出力の変換回路の小規模化に有効であるが、データを逐次入力し、変換係数を逐次出力する逐次変換回路にも好適である。
【００８５】
先の第１の実施形態の中で説明した変換の中で、代表的な変換である＜変換１＞と＜変換２＞を逐次処理する回路の構成を図６に示す。図６の回路における主要な構成要素は、以下の３つである。
・中間データ生成部６１０：逐次入力されるデータを加減算して中間データを生成する
・データ遅延部６２０：入力順にデータをシフトさせ、４データ分遅延させる
・中間データ加減算部６３０：遅延されたデータに中間データを加減算する
【００８６】
次に、図６に示す可逆アダマール変換回路の動作を簡単に説明する。端子６０１から逐次入力されるデータＤ０，Ｄ１，Ｄ２，Ｄ３は、４段のレジスタから成るデータ遅延部６２０に入力されると共に、中間データ生成部６１０に送られる。
【００８７】
中間データ生成部６１０は、加減算部６１３にて前記入力データを逐次加減算して合算値（Ｄ０−Ｄ１−Ｄ２−Ｄ３）を計算し、この合算値に加算部６１４にてオフセット（ｆ）を加算し、ビットシフト部６１５で合計値の下位１ビットを取り除いた値を、整数の中間データ（ｔ）としてレジスタ６１６に保持し、４つの変換係数を出力するまで保持し続ける。
【００８８】
中間データ加減算部６３０は、前記データ遅延部６２０によって遅延されたデータに、中間データ生成部から出力される中間データ（ｔ）を加減算する。より詳細に述べると、遅延されたデータＤ０からは前記中間データ（ｔ）を減算し、Ｄ０の後に続く３つのデータＤ１，Ｄ２，Ｄ３へは中間データ（ｔ）を加算する。
【００８９】
中間データ生成部６１０における加減算部６１３と中間データ加減算部６３０は、加算と減算を切替える必要がある。これは不図示の制御信号生成部によって生成され、端子６０２から入力される制御信号６０３によって行われる。
【００９０】
４つの入力データと変換係数の入出力の順序は、一般的には、Ｄ０，Ｄ１，Ｄ２，Ｄ３の順に入力し、Ｅ０，Ｅ１，Ｅ２，Ｅ３の順に出力するが、データの入力順に特に拘束は無い。例えば、Ｄ２，Ｄ１，Ｄ０，Ｄ３といった順に入力することが可能である。この場合、前記加減算部６１３が、３番目に入力されるデータＤ０を加算し、他の３つのデータを減算するような制御信号を生成すれば対応できる。前記中間データ加減算部６３０も同じ制御信号で加減算を制御すれば、目的とする変換係数を得ることができる。すなわち、中間データ加減算部６３０はＥ０出力時に減算部として動作し、それ以外の係数を出力する時は加算部として動作する。その結果、前記データの入力順に対応し、Ｅ２，Ｅ１，Ｅ０，Ｅ３といった順序で変換係数が演算され出力される。
【００９１】
上記逐次変換部と、従来技術で容易に構成できる並列変換部を図７のように組み合せると、これらの変換部だけで２次元の可逆アダマール部を構成することができる。
【００９２】
また、後段の並列変換部として、他の変換部を用いることができる。例えば、ＪＰＥＧ  ＸＲにおける可逆変換の中の、Ｔ＿ｈ（）、Ｔｏｄｄ（）、Ｔｏｄｄｏｄｄ（）等の複数の並列変換部を用意し、前段の逐次変換部からの４つの出力を、前記複数の並列変換部で切替えて処理すれば、データの転置が不要なＦＣＴ変換部を実現できる。この場合、前段の４つの逐次変換部に同時に入力するデータ順序は、後段の並列変換部の処理単位と合致していれば、入力順序はどうでもよい。
【００９３】
上記の構成で得られた変換係数を逆変換する場合の構成について簡単に述べる。前記並列変換部に対応する並列逆変換部を前段に設け、後段に上記逐次変換部を並列に４つ設けた構成にて逆変換を行なう。ここで、該逐次変換部は同一の構成にて逆変換が可能である。
【００９４】
前段に設ける並列逆変換部がアダマール変換部のみの場合、全体として２次元の逆アダマール変換部となり、また、並列逆変換部がＪＰＥＧ  ＸＲにおける、Ｔ＿ｈ（）、ＩｎｖＴｏｄｄ（）、ＩｎｖＴｏｄｄｏｄｄ（）から成る場合、全体としてＩＣＴ変換部となる。
【００９５】
［第４の実施形態］
次に、本発明の可逆アダマール変換部の適用に好適な画像符号化装置８００の構成を図８に示す。
【００９６】
本画像符号化装置は、画像データを入力する画像入力部８０１と、符号化前の画像データ及び符号化後の符号化データを格納する半導体メモリ等のデータ記憶部８０２、該画像データを符号化する符号化部８１０、および、それらを結ぶデータバス８０５等から構成される。データバス８０５には、ネットワーク経由でデータを送受することが出来るようネットワークＩ／Ｆ（インターフェース）８０３がつながっていてもよい。
【００９７】
画像データは、画像入力部８０１からデータバス８０５に入力したり、ネットワークを経由してネットワークＩ／Ｆから入力し、データバス８０５を通してデータ記憶部８０２に格納する。画像入力部８０１は例えばスキャナ又はイメージセンサである。
【００９８】
符号化部８１０は、画像バッファ８１１、ブロックデータ予測部８３２、予測残差計算部８１２、系列変換部８１３、量子化部８１４、エントロピー符号化部８１５、局部復号部８２０、局部復号画像格納部８３１を有する。ここでは、説明を簡略化するため、ブロックサイズは４×４画素の固定サイズとする。
【００９９】
非可逆符号化と可逆符号化を同一の符号化スキームで行うことを前提とし、系列変換として、整数データから整数係数への可逆変換を用い、量子化の有無により、非可逆符号化と可逆符号化を実現する。すなわち、量子化しない、或いは、量子化ステップ“１”で量子化した時に可逆符号化となり、“１”より大きな量子化ステップで量子化した時に非可逆な符号化を行うものとする。
【０１００】
データ記憶部８０２に格納されている画像データは、数ブロック単位で符号化部８１０内にある画像バッファ８１１に転送され、該バッファから４×４画素のサイズのブロック単位でデータを読出し、圧縮符号化を行う。
【０１０１】
４×４サイズの画像データが有する冗長性を取り除くために、局部復号画像格納部８３１内にある既に符号化・復号済みの画像データを参照して、ブロックデータ予測部８３２にて、符号化対象ブロックとの差分の小さなデータを予測データとして生成する。静止画の符号化や、動画のフレーム内予測の符号化では、同一フレームの画像データのみを参照するが、動画のフレーム間予測では、別のフレームの画像データも参照する。本発明においては、この違いに意味が無く、どちらであってもよいが、ここでは、静止画を符号化するものとする。
【０１０２】
そして、予測残差計算部８１２にて、予測データを、符号化対象のブロックデータから減算して、予測残差のブロックデータを算出する。
【０１０３】
可逆符号化時は、局部復号した画像データに劣化が無いため、参照画素データと符号化対象画素データの相関が強ければ、それに応じて予測残差は大きく減少することがある。具体的には、非可逆符号化時の参照画像は、エッジが鈍ってしまうため、該エッジの両側の画素で大きな予測誤差が発生してしまう。
【０１０４】
しかし、可逆符号化時は、劣化の無い元の画像を復元して参照することが出来るため、相関の強いエッジをうまく位置合わせできれば、差分値すなわち、予測残差は大幅に小さくできる。ようするに、可逆符号化時の予測残差は、非可逆符号化時と較べて、小さくできる可能性が大きい。
【０１０５】
予測残差は、系列変換部８１３にて変換され、変換係数となる。この系列変換は、４×４の２次元可逆アダマール変換、あるいは、２次元可逆ＤＣＴ等を適用することができるが、ここでは、説明済みの変換処理だけで実現できる２次元可逆アダマール変換にて系列変換を行うものとする。
【０１０６】
Ｈ．２６４／ＡＶＣ符号化のように、系列変換と量子化がセットで定義されている場合、系列変換の前後でパワー（データや変換係数の二乗和）を保存することは必須ではないが、量子化とは独立に系列変換を行う場合、パワーを保存することが望まれる。一般の実数演算型のアダマール変換やＤＣＴでは、演算有効ビット数による演算誤差の範囲内でパワーが変動するが、これは無視できる範囲である。それに対し、整数係数への可逆変換では、変換係数毎に整数への丸め誤差が生じるため、ブロック全体では無視できない。
【０１０７】
具体的に、４×４画素の予測誤差データに対し、先に説明した＜変換７＞のみで水平方向と垂直方向の２次元の変換をした場合、＜変換１＞と＜変換２＞を組み合せて２次元変換した場合の変換結果を図９に示す。
【０１０８】
図９に示した例は一番極端な例であるが、変換前のパワー“１”の予測誤差データが変換後には“９”に増え、有意係数の数が増えてしまい、これによって符号量が増加してしまうことがある。
【０１０９】
このような状況が発生するのは、量子化をしない可逆符号化時であって、４×４サイズのブロック予測データが、符号化対象データと一致はしないが極めて近い値となる場合のみであるため、極めて稀なことではある。しかも、変換処理の複雑さに違いがあるため、一概に＜変換７＞が良いとは言い切れない。＜変換７＞は、符号量は減るが、変換処理が複雑になる。＜変換１＞や＜変換２＞はその逆である。
【０１１０】
符号量の減少具合は、符号化対象画像の性質や、前記予測データの生成方法、エントロピー符号化方式、等のさまざまな要因によって変わってくる。よって、これら諸要因によって決まる符号量の減少の効果が、変換の複雑さを上回ると判断できれば、＜変換７＞を用いた符号化方式とすればよい。
【０１１１】
上述の変換処理で得られる変換係数は、量子化部８１４で量子化した後、エントロピー符号化部８１５にて可変長符号化される。
【０１１２】
前記＜変換７＞とそれ以外の変換による差は、非可逆圧縮時に行う必ず行う量子化処理のステップが大きい程、その差がほとんど無くなるが、量子化をしない可逆圧縮において一番大きな差が見られる。
【０１１３】
エントロピー符号化の方法は様々な方法がある。ここでは、量子化した量子化係数（可逆圧縮時は量子化しない変換係数）における連続するゼロ値をスキャン順序でカウントしてランレングス化し、そのランレングス情報とゼロ値でない有意係数を可変長符号で符号化することを想定する。このようなエントロピー符号化は一般的な手法である。該符号化において、量子化係数中に有意係数が少ない、すなわち、ゼロ値が多いとランレングス情報としてまとめられるので、符号量を削減しやすくなる。
【０１１４】
エントロピー符号化して得られた符号は、一時的に符号バッファ８１６に蓄え、所定量の符号を蓄えたところで、データバス８０５を経てデータ記憶部８０２にまとめて転送し、該データ記憶部で保持する。
【０１１５】
一方、前記量子化した量子化係数は、局部復号部８２０内の逆量子化部８２１にて逆量子化し、系列逆変換部８２２にて逆変換し、復号画像生成部８２３にて前記ブロックの予測データを加算して局部復号画像データを生成する。この局部復号画像データは、前記局部復号画像格納部８３１に格納され、次の符号化対象ブロックデータの予測データ生成のために参照される。
【０１１６】
以上説明した画像符号化装置の系列変換部において、本発明の可逆アダマール変換処理方法や可逆アダマール変換装置が極めて有効であることを示すことができた。
【０１１７】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2011257806.tif 000004
【図２】
2011257806.tif 000005
【図３】
2011257806.tif 000006
【図４】
2011257806.tif 000007
【図５】
2011257806.tif 000008
【図６】
2011257806.tif 000009
【図７】
2011257806.tif 000010
【図８】
2011257806.tif 000011
【図９】
2011257806.tif 000012