(57)【要約】【課題】  1回の丸め処理のみによる16点ロスレスアダマール変換を実現する。【解決手段】  16個のデータにアダマール変換行列を乗算して16個の線形アダマール変換係数を得る線形変換工程と、前記16個の線形アダマール変換係数を、各々が奇数個となるよう4種類のグループに分類し、該グループ毎に所定のオフセット値を加算するオフセット工程と、前記オフセット値の加算後に小数点以下を切り捨てて前記ロスレスアダマール変換係数を得る整数化工程と、を有する。【選択図】  図2
2006065678.tif 000002
【特許請求の範囲】
【請求項１】
16個のデータに対するロスレスアダマール変換係数を得るデータ変換方法であって、
前記16個のデータにアダマール変換行列を乗算して16個の線形アダマール変換係数を得る線形変換工程と、
前記16個の線形アダマール変換係数を、各々が奇数個となるよう4種類のグループに分類し、該グループ毎に所定のオフセット値を加算するオフセット工程と、
前記オフセット値の加算後に小数点以下を切り捨てて前記ロスレスアダマール変換係数を得る整数化工程と、
を有することを特徴とするデータ変換方法。
【請求項２】
前記オフセット工程においては、第1のグループの変換係数には加算を行わず、第2のグループの変換係数には0.25を加算し、第3のグループの変換係数には0.5を加算し、第4のグループの変換係数には0.75を加算することを特徴とする請求項１記載のデータ変換方法。
【請求項３】
前記16個の線形アダマール変換係数の小数点以下の値は0，0.25，0.5，0.75のいずれかであることを特徴とする請求項２記載のデータ変換方法。
【請求項４】
前記整数化工程は、floor関数による小数点以下切り捨てを行うことを特徴とする請求項１乃至３のいずれかに記載のデータ変換方法。
【請求項５】
前記16個の線形アダマール変換係数を分類した4種類のグループのうち、3種類のグループでは変換係数の数が各々3個または5個であることを特徴とする請求項１乃至４のいずれかに記載のデータ変換方法。
【請求項６】
さらに、前記ロスレスアダマール変換係数を符号化する符号化工程を有することを特徴とする請求項１乃至５のいずれかに記載のデータ変換方法。
【請求項７】
前記符号化工程においては、エントロピー符号化を行うことを特徴とする請求項６記載のデータ変換方法。
【請求項８】
さらに、前記ロスレスアダマール変換係数を用いてDCT変換を行うDCT変換工程を有することを特徴とする請求項１乃至５のいずれかに記載のデータ変換方法。
【請求項９】
さらに、前記DCT変換工程において得られたDCT係数を用いてJPEG符号化を行うJPEG符号化工程を有することを特徴とする請求項８記載のデータ変換方法。
【請求項１０】
入力された16個のデータに対するロスレスアダマール変換係数を出力するデータ変換装置であって、
前記16個のデータにアダマール変換行列を乗算して16個の線形アダマール変換係数を得る線形変換手段と、
前記16個の線形アダマール変換係数を、各々が奇数個となるよう4種類のグループに分類し、該グループ毎に所定のオフセット値を加算するオフセット手段と、
前記オフセット値の加算後に小数点以下を切り捨てて前記ロスレスアダマール変換係数を得る整数化手段と、
を有することを特徴とするデータ変換装置。
【請求項１１】
16個のデータに対するロスレスアダマール変換係数を得るデータ変換方法であって、
前記16個のデータの総和の奇偶性を表わすパリティを取得する第１のパリティ工程と、
前記16個のデータにアダマール変換行列を乗算して16個の線形アダマール変換係数を得る線形変換工程と、
前記16個の線形アダマール変換係数を、少なくとも2種類のグループに分類し、該グループ毎に所定のオフセット値を加算するオフセット工程と、
前記オフセット値の加算後に小数点以下を切り捨てて前記ロスレスアダマール変換係数を得る整数化工程と、
前記ロスレスアダマール変換係数のうち、所定の係数に前記パリティを加算する第２のパリティ工程と、
を有することを特徴とするデータ変換方法。
【請求項１２】
前記第１のパリティ工程においては、前記16個のデータのうち、所定位置のデータに対し前記パリティを減算することを特徴とする請求項１１記載のデータ変換方法。
【請求項１３】
前記第１のパリティ工程においては、前記16個のデータのうち、所定位置のデータに対し前記パリティを加算することを特徴とする請求項１１記載のデータ変換方法。
【請求項１４】
情報処理装置を制御して、請求項１乃至請求項９の何れかに記載されたデータ変換を実現することを特徴とするプログラム。
【請求項１５】
請求項１４に記載されたプログラムが記録されたことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ変換方法およびデータ変換装置に関し、特に可逆変換が可能な整数アダマール変換を行うデータ変換方法およびデータ変換方法に関する。
【背景技術】
【０００２】
画像、特に多値画像は非常に多くの情報を含んでおり、その画像を蓄積・伝送する際にはデータ量が膨大になってしまうという問題がある。このため画像の蓄積・伝送に際しては、画像の持つ冗長性を除く、或いは画質の劣化が視覚的に認識し難い程度に画像の内容を変更することによってデータ量を削減する高能率符号化が用いられる。
【０００３】
例えば、静止画像の国際標準符号化方式としてISOとITU-Tにより勧告されたJPEG方式では、画像データをブロックごと（8画素×8画素）に離散コサイン変換（DCT）してDCT係数に変換した後、各係数を各々量子化し、さらにエントロピー符号化することにより画像データを圧縮している。このDCTを利用した圧縮技術としてはJPEG以外に、H261，MPEG1/2/4等がある。
【０００４】
このDCT変換の一部の処理として、あるいは画像データの変換を行う処理として、アダマール変換が知られている。アダマール変換は変換行列の要素が1又は-1のみから成り、加算と減算のみで実現できるもっともシンプルな直交変換である。以下、アダマール変換について簡単に説明する。
【０００５】
2点アダマール変換の変換行列Ｈ2は、以下のように定義される。
【０００６】
【数１】
2006065678.tif 000003
【０００７】
一般的なN(=2n)点アダマール変換行列ＨNは、N/2点アダマール変換行列ＨN/2と上記2点アダマール変換行列Ｈ2との間のクロネッカー積により、下記のように再帰的に定義することができる。
【０００８】
【数２】
2006065678.tif 000004
【０００９】
上記定義から4点アダマール変換行列を求めると、
【００１０】
【数３】
2006065678.tif 000005
【００１１】
となる。この変換行列はナチュラル型と呼ばれるもので、基底ベクトルがシーケンシの順番に並んでいない。基底ベクトルの置換を繰り返して2行目の基底ベクトルを4行目に移動すると、基底ベクトルの順序がシーケンシ順である変換行列ＷＨ4となる。
【００１２】
【数４】
2006065678.tif 000006
【００１３】
上記変換行列はウォルシュ型あるいはウォルシュアダマール変換行列と呼ばれている。アダマール変換は可逆な直交変換であることが知られており、上記ナチュラル型、ウォルシュ型のいずれも可逆な変換が可能である上、変換行列が対称行列になっている。
さらに以下に示すように、4点アダマール変換行列に前記クロネッカー積を2回適用すると、16点アダマール変換行列Ｈ16が得られる。図1に、該変換行列Ｈ16の詳細を示す。
【００１４】
【数５】
2006065678.tif 000007
【００１５】
前述したように、一般的にアダマール変換は可逆変換であると言われているが、これは、数学的に可逆であるということである。すなわち、変換時および逆変換時に演算誤差が発生しないことが前提となっている。一方、変換係数を整数化しても可逆変換が可能なように処理する変換を、数学的可逆変換と区別してロスレス変換と呼ぶことが多い。以下、本明細書においても、この「ロスレス変換」の呼称を使用する。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
アダマール変換係数の小数点以下のデータを丸め処理して整数化する場合、単純に切り捨て、或いは、四捨五入してしまうと、逆変換後のデータは元のデータに戻らない。これは、小数点以下のビット情報が失われてしまうためである。
【００１７】
非特許文献1では、4点アダマール変換に特徴のある丸め処理を施すことによって、ロスレス変換を実現している。しかしながら16点アダマール変換では、可逆な変換係数が得られるような丸め処理は提案されていない。
【００１８】
非特許文献1では、4点ロスレスアダマール変換を16点ロスレスアダマール変換、あるいは、2次元4×4点ロスレスアダマール変換へ拡張する方法も示しているが、それは既存の4点ロスレスアダマール変換を縦属接続して2段で処理するものであり、16点ロスレスアダマール変換を直接演算しているものではない。該縦属接続処理により得られる16点ロスレスアダマール変換係数、あるいは、2次元4×4点ロスレスアダマール変換係数には、2回の丸め誤差が重畳される。ロスレス変換を実現するための丸め処理は非線形演算であるため、重畳される丸め誤差は非線形性を有しており、変換係数として好ましくない。すなわち、2回の丸め誤差が重畳されるということは、非線形な丸め誤差が多く重畳されることにほかならず、問題であった。
【００１９】
また、丸め処理も1つの変換係数につき2回行う必要があるため、演算量が増えるといった問題もあった。
【００２０】
本発明は上述の問題を個々にまたはまとめて解決するためになされたものであり、1回の丸め処理のみで、16点ロスレスアダマール変換係数、あるいは、2次元4×4点ロスレスアダマール変換係数を得るためのデータ変換方法およびデータ変換装置を提供することを目的とする。
【００２１】
さらに、該データ変換方法を符号化処理へ適用することによって、可逆符号化処理を実現することを目的とする。
【非特許文献１】中山忠義, 大澤秀史, 河村尚登：“新ロスレス変換とロスレス2次元DCTへの応用”, 画電誌, Vol.31, No.5, pp.787-793, Sept. 2002.
【課題を解決するための手段】
【００２２】
本発明は、上記目的を達成する一手法として、以下の工程を備える。
【００２３】
すなわち、16個のデータに対するロスレスアダマール変換係数を得るデータ変換方法であって、前記16個のデータにアダマール変換行列を乗算して16個の線形アダマール変換係数を得る線形変換工程と、前記16個の線形アダマール変換係数を、各々が奇数個となるよう4種類のグループに分類し、該グループ毎に所定のオフセット値を加算するオフセット工程と、前記オフセット値の加算後に小数点以下を切り捨てて前記ロスレスアダマール変換係数を得る整数化工程と、を有することを特徴とする。
【００２４】
また、前記オフセット工程においては、第1のグループの変換係数には加算を行わず、第2のグループの変換係数には0.25を加算し、第3のグループの変換係数には0.5を加算し、第4のグループの変換係数には0.75を加算することを特徴とする。
【００２５】
さらに、前記ロスレスアダマール変換係数を符号化する符号化工程を有し、該符号化工程においてはエントロピー符号化を行うことを特徴とする。
【００２６】
また、前記ロスレスアダマール変換係数を用いてDCT変換を行うDCT変換工程、および、得られたDCT係数を用いてJPEG符号化を行うJPEG符号化工程をさらに有することを特徴とする。
【発明の効果】
【００２７】
本発明によれば、16点ロスレスアダマール変換を、線形アダマール変換と各変換係数につき１回の丸め処理で実現することによって、丸め誤差の発生を抑制することができる。
【００２８】
また、得られたロスレスアダマール変換係数を直接エントロピー符号化することにより、符号量を抑制することができる。
【００２９】
また、本発明の16点ロスレスアダマール変換をDCT演算に適用することによって、丸め誤差の少ないロスレスDCT変換が実現され、さらにJPEG符号化へ適用することによって、画像データの可逆変換を実現する。
【発明を実施するための最良の形態】
【００３０】
以下、添付の図面を参照して、本発明をその好適な実施形態に基づいて詳細に説明する。
【００３１】
図1に示したように、16個の1次元入力データを16点アダマール変換するための変換行列は、行列のサイズが16×16にもなる。この変換行列は以降Ｈ16という記号を用いて表現すればよいが、16個もある入力データや変換係数の要素を列挙する場合、1次元的に書き並べると極めて見にくいものになってしまう。
【００３２】
そこで本明細書では、1次元16点アダマール変換として考えた方が解かりやすい場合は16点アダマール変換で、2次元4×4点アダマール変換として考えた方が解かりやすい場合は2次元4×4点アダマール変換で、それぞれ記述することとする。なお、1次元16点アダマール変換は、該変換と等価な2次元4×4点アダマール変換に置き換えが可能なので、上記のように同じ変換を異なる次元から見ても厳密性が失われることは無い。
【００３３】
具体的には、図1に示す行列を用いた1次元変換は、下記(6)式に示す2次元変換でも実現できる。(6)式において、中央のd0〜d15を要素とする行列は、1次元の16個のデータを4×4に並べたものである。
【００３４】
【数６】
2006065678.tif 000008
【００３５】
上記(6)式による変換結果（変換係数）は、4×4の行列として得られる。
＜第1実施形態＞
本実施形態では、可逆変換が可能なアダマール変換係数を得る方法について説明する。該変換処理は、通常のアダマール変換で行う線形変換処理工程と、該線形変換処理工程で得られた小数点以下のデータを有する線形変換係数を整数化するための丸め処理工程のみによって実現される。すなわち本実施形態においては、通常のアダマール変換で得られる変換係数に対して各々1回の丸め処理を行うだけの、極めて簡単な処理によって、可逆変換可能なアダマール変換係数が得られる。本実施形態の特徴である丸め処理の工程は、オフセット行列を加算する処理とfloor関数を計算する処理とによって構成される。
【００３６】
図2に、本実施形態におけるアダマール変換処理のフローチャートを示す。ステップS201は従来と同様の演算処理によって線形アダマール変換処理を行う部分である。そしてステップS202がオフセット行列を加算する処理、ステップS203がfloor関数を計算する処理である。ここでfloor(x)は、xを超えない最大の整数値を出力する関数である。このステップS202とS203によって、本実施形態の丸め処理が実現される。
【００３７】
このような処理によって可逆変換が可能なアダマール変換係数が得られるのは、ステップS202で加算するオフセット行列がある特定の構造を有する場合である。以下、該オフセット行列の要素や構造について詳しく説明する。
［オフセット行列］
まず、本実施形態におけるオフセット行列の要素の種類について説明する。オフセット行列の各要素の値は、0，0.25，0.5，0.75の4種類である。この4種類の値は、図1に示す変換行列が有する係数1/4を乗算した結果として発生する、変換係数の小数点以下の値でもある。具体的には、8.75，4.5，1.25，6.0等の変換係数が発生し得る。例えば8.75を切り上げて整数値を得るには0.25を加算すればよく、同じく4.5，1.25を切り上げるには、それぞれ0.5，0.75を加算すればよい。また、どんな値に対しても切り上げを行わないようにするには、0を加算すればよい。よって、小数点以下がいかなる値の時に切り上げを行うかは、加算するオフセットによって決めることができ、16個の変換係数各々に対し該オフセットを独立に決めることができる。なお、オフセット加算後に残る小数点以下の値は、後段のfloor関数によって切り捨てられる。
【００３８】
以上説明したように、本実施形態におけるオフセット行列の要素は、0，0.25，0.5，0.75の4種類で良い。このような0から0.25刻みの4種類の値は、小数点以下を示す2ビットで表現できる。よってオフセット行列は、2つのビットプレーンで表現できることになる。本実施形態においてロスレスアダマール変換係数を得ることができるオフセット行列は、この2つのビットプレーンのパターン構造に大きく依存している。以下、この構造について説明する。
【００３９】
該2つのビットプレーンは各々4×4のサイズを有する。4×4のサイズのビットプレーンにおける2値パターンの種類は全部で2の16乗個になるが、その中で、オフセット行列としての意味を有するのは896種類である。該896種類のパターンとは、行方向の“1”の個数が全4行とも共に奇数または偶数に統一しており、列方向の“1”の個数が全4列とも共に奇数または偶数に統一しており、なおかつ、パターン全体の“1”の総和が6または10となるパターンである。
【００４０】
例えば、ビットプレーンの第i行第j列の要素をａij（0≦i≦3，0≦j≦3，ａij＝0または1）と表わすと、下記(7)式に示すビットプレーン行列において、以下の3つの条件(A1)，(A2)，(A3)を満たすものが、上述したように896種類存在する。
【００４１】
【数７】
2006065678.tif 000009
【００４２】
(A1)  ａi0＋ａi1＋ａi2＋ａi3が、全てのiに対して奇数、もしくは全てのiに対して偶数
(A2)  ａ0j＋ａ1j＋ａ2j＋ａ3jが、全てのjに対して奇数、もしくは全てのjに対して偶数
(A3)  Σａij=6  または  10
上記条件(A1)は、行方向の4ビットの和が全ての行に対して奇数もしくは偶数に統一されていることを意味し、同じく条件(A2)は、列方向の4ビットの和が全ての列に対して奇数もしくは偶数に統一されていることを意味する。ここで、行方向の和が奇数で列方向の和が偶数であるパターンを奇数―偶数パターンと表現すると、奇数−奇数、奇数―偶数、偶数―奇数、偶数―偶数の4種類のパターンに分類できる。図3に、4つに分類したパターンそれぞれの具体例を示す。
【００４３】
行または列方向の和が奇数または偶数で統一しているパターン、すなわち、前記条件(A1)(A2)を満たすパターンは、4つの各分類に対して各々512種類、合計2048種類存在する。これらのパターンの内、条件(A3)を満たすもの、すなわち“1”の数が6個または10個のものだけが、ロスレス変換のオフセット行列として有効であり、その数は2048種類の内の896種類である。細かい内訳としては、奇数−奇数パターンが320種類、その他の分類パターンは各々192種類、合計で320+192×3=896種類である。
【００４４】
何故このようなパターンがオフセット行列として有効であるのかについては、数学的な証明は困難である。しかしながら、シミュレーションによればこれらが実際に有効であることが、出願人によって確認されている。
【００４５】
2つのビットプレーン各々に、該896種類のパターンが有効であるが、オフセット行列としてはその全部の組み合せ、すなわち、896×896種類が有効というわけでは無く、下記の条件(A4)を満たす一部の組み合せに限定される。
【００４６】
(A4)  2つのビットプレーン間で排他的論理和を演算して得られるビットプレーンのパターンが、前記896種類のパターンになる。
【００４７】
この条件を満たす2つのビットプレーン間では、同じ位置に“1”が存在する個数が奇数個に限定されることが、以下の説明から分かる。
【００４８】
上記条件(A3)より、2つのビットプレーンにおける各々の“1”の数は6個または10個であるため、例えば、小数第1位ビットプレーンに10個で第2位ビットプレーンに6個の“1”が存在する等、“1”の個数の組み合せは4通りある。
【００４９】
この場合、両ビットプレーンに共通して“1”が存在しうる数をm個とすると、排他的論理和を演算して得られるビットプレーン上の“1”の数は10+6-2mとなる。ここで-2mの項は、共通して“1”が存在する位置の排他的論理和の結果は“0”であるため、そこでは“1”の数が2個減ることを示している。前記条件(A3)(A4)より、10+6-2m=6，10でなければならないので、m=3，5となる。
【００５０】
同様に計算すると、小数第1位ビットプレーンに6個、第2位ビットプレーンに6個の“1”が存在する場合、2つのビットプレーンに共通して“1”が存在する個数mは、m=1，3となる。また、小数第1位ビットプレーンに10個、第2位ビットプレーンに10個の場合は、m=5，7となる。このように、各組み合せに対して、mの値が2種類ずつ得られる。
【００５１】
本実施形態におけるオフセット値は、以下のように決定される。例えば、共通して“1”が存在する位置のオフセット値は0.75(=3/4)であり、小数第1位ビットプレーンに10個、第2位ビットプレーンに6個の“1”がある場合、小数第1位における残りの10-m個の“1”に対するオフセット値は0.5(=2/4)となり、小数第2位における残りの6-m個の“1”に対するオフセット値は0.25(=1/4)となる。そして、最後に残った16-{m+(10-m)+(6-m)}=m個の位置のオフセット値は0(=0/4)である。
【００５２】
ここで図4に、小数第1位と第2位ビットプレーン中の“1”の個数の4つの組み合せに対する、16個のオフセット値の内訳を整理して示す。図4によれば、“1”が小数第1位ビットプレーンに10個、第2位ビットプレーンに6個ある場合、オフセット値3/4となるものが3個または5個となることが示されている。この場合、オフセット値3/4が3個の時、オフセット値2/4が7個、オフセット値1/4が3個、オフセット値0/4が3個となる。また、オフセット値3/4が5個の時、オフセット値2/4が5個、オフセット値1/4が1個、オフセット値0/4が5個となることが分かる。
【００５３】
図4によれば本実施形態のオフセット行列は、3/4，2/4，1/4，0/4という4種類のオフセット値の各々の数が、(1,5,5,5)、(3,3,3,7)、(3,3,7,3)、(5,1,5,5)、(3,7,3,3)、(5,5,1,5)、(5,5,5,1)、(7,3,3,3)個となる8種類に分類でき、さらに全てが奇数個となっていることが分かる。また、全てのパターンにおいて、3種類のオフセット値が各々3個または5個となっている。この8種類のオフセット行列の具体例を図5A，図5Bに示す。
【００５４】
図5Aおよび図5Bにおいて、例えば図5Aの最上段に示す(1,5,5,5)のオフセット行列の例では、小数点第1位のビットプレーンには奇数−偶数パターンを、小数点第2位のビットプレーンには奇数−奇数パターンを用いた構成を示している。詳細に説明すると、左辺の行列が16点ロスレスアダマール変換用のオフセット行列を表し、右辺の第1項が小数点第1位のビットプレーンを、第2項が小数点第2位のビットプレーンを表わしている。小数点第1位のビットの重みは1/2、小数点第2位のビットの重みは1/4であるので、第1項の行列の前には1/2、第2項の行列の前には1/4が掛かっている。
【００５５】
第1項のビットプレーンは、行単位あるいは列単位の“1”の和が、第0行〜第3行の順に3,1,1,1であり、第0列〜第3列の順に0,2,2,2である、奇数−偶数パターンになっている。また第2項のビットプレーンは、“1”の和が第0行〜第3行の順に1,1,1,3、第0列〜第3列の順に3,1,1,1である、奇数−奇数パターンになっている。“1”の総和はどちらのビットプレーンも6であり、前述の条件(A1)(A2)(A3)を満たしている。
【００５６】
さらに、この2つのビットプレーン間の排他的論理和は(1,1,1,1  1,1,0,0  1,0,1,0  0,1,1,0)となり、該ビットプレーン中の“1”の和は、第0行〜第3行の順に4,2,2,2、第0列〜第3列の順に3,3,3,1である。そして、“1”の総和は10であるから、前記条件(A4)を満たしている。
【００５７】
小数第1位ビットプレーンの1つのパターンに対して、前述の限定条件を満たす小数第2位ビットプレーンのパターン数は320種類存在することが、出願人によって確認されている。よって、有効なオフセット行列として使えるものが、896×320＝286720種類も存在する。その全部をここで示すことは不可能なので、その一部を図6に示す。
【００５８】
図2に示すステップS202において、以上説明したオフセット行列を線形アダマール変換係数へ加算した後、ステップS203でfloor関数値を求めることによって、ロスレスアダマール変換係数が得られる。
【００５９】
［逆変換用のオフセット行列］
ある変換がロスレス変換であるためには、その可逆性を示す必要がある。すなわち、可逆な逆変換処理を示す必要がある。
【００６０】
本実施形態のロスレスアダマール変換に対する逆変換の処理手順は、順変換と同様である。すなわち、図2に示すフローチャートに基づいて逆変換が行われるが、この場合、ステップS202で加算するオフセット行列が、順変換で用いたものとは異なる。
【００６１】
逆変換で用いるオフセット行列（以下、第2のオフセット行列）Ｒは、順変換で用いたオフセット行列（以下、第1のオフセット行列）Ｆに基づいて、以下のように求められる。この第1のオフセット行列Ｆと第2のオフセット行列Ｒとの関係は、本実施形態におけるロスレス変換の特徴のひとつである。
【００６２】
まず、第1のオフセット行列Ｆの2つのビットプレーンにおける各々の重みを無視して、これらを“0”，“1”の要素からなる2値行列と解釈したとき、第2のオフセット行列Ｒにおける2つの2値行列は、下記(8)式により求められる。
【００６３】
【数８】
2006065678.tif 000010
【００６４】
(8)式において、Ｆは順変換、Ｒは逆変換のオフセット行列に対応し、Ｒi、Ｆiは小数点以下i番目のビットの2値行列を表わす。
(8)式で求めた2つの2値行列Ｒ1、Ｒ2に対し、それぞれに対応する重み1/2，1/4をそれぞれに乗算し、それらを加算したものが逆変換用のオフセット行列になる。この演算を下記(9)式に示す。
【００６５】
【数９】
2006065678.tif 000011
【００６６】
この第2のオフセット行列Ｒを用いて逆変換を行うと、変換前のオリジナルデータに戻る。これを数学的に証明することは現時点では成されていない。しかしながら、全種類のデータに対する可逆性を検証するために、その全種類のデータに対して可逆性を確認する必要はなく、一部の特定データに対して確認できれば良いことが、一般的に知られている。本明細書中で説明している一連のロスレス変換は、この一部の特定データに対する可逆性が出願人によって実際に確認されており、実用上なんら問題は無いと考えられる。
一方、第1のオフセット行列Ｆを2つの2値行列に分けることなく重み付きのまま用いて、直接第2のオフセット行列Ｒを求めることも可能である。小数点以下2ビットに対応したオフセット変換式を(10)式に示す。
【００６７】
【数１０】
2006065678.tif 000012
【００６８】
上記(10)式におけるＲ4×4、Ｆ4×4は小数点以下2ビットのレンジを有する行列である。ここで、実際の順変換用のオフセット行列Ｆ4×4と逆変換用のオフセット行列Ｒ4×4の一例を以下に示す。
【００６９】
【数１１】
2006065678.tif 000013
【００７０】
［ロスレス変換／逆変換例］
上記1組の順変換用オフセット行列Ｆ4×4と逆変換用オフセット行列Ｒ4×4を用いて、実際にロスレスアダマール変換係数を計算し、該変換係数を逆変換することによって、元の4×4データが復元できることを示す。以下、下記(12)に示すデータを、変換対象となるオリジナルのデータとして説明する。
【００７１】
【数１２】
2006065678.tif 000014
【００７２】
まず、上記4×4のデータに対して2次元線形アダマール変換を施すと、(13)式に示す結果が得られる（ステップS201に対応）。
【００７３】
【数１３】
2006065678.tif 000015
【００７４】
順変換用オフセット行列Ｆ4×4を用いて上記線形アダマール変換係数を丸め処理すると（ステップS202，S203に対応）、(14)式に示すようにロスレス変換係数が得られる。
【００７５】
【数１４】
2006065678.tif 000016
【００７６】
次に、上記(14)式に示す4×4のロスレス変換係数に対し、2次元線形アダマール逆変換を施すが、変換行列が正規対称行列であるので、(15)式に示すように、逆変換においても順変換と同じ処理を行う（ステップS201に対応）。
【００７７】
【数１５】
2006065678.tif 000017
【００７８】
この結果に対してさらに、逆変換用オフセット行列Ｒ4×4を用いて丸め処理すると（ステップS202，S203に対応）、下記(16)式に示すデータが得られる。これは、上記(12)式に示したオリジナルデータとまったく同じであり、データが完全に復元されたことが分かる。
【００７９】
【数１６】
2006065678.tif 000018
【００８０】
以上説明したように本実施形態によれば、線形アダマール変換と各変換係数1回の丸め処理によって、16点ロスレスアダマール変換が実現できる。
具体的には、16個の線形アダマール変換係数に対して、一部の奇数個の係数は小数点以下を切り捨て、他の一部の奇数個の係数は0.25を加算した後に小数点以下を切り捨て、さらに他の一部の奇数個の係数は0.5を加算した後に小数点以下を切り捨て、残りの奇数個の係数は0.75を加算した後に小数点以下を切り捨てる丸め処理を行うことにより、丸め誤差の少ない16点ロスレスアダマール変換が実現できる。
【００８１】
なお、本実施形態で得られるロスレスアダマール変換係数は、一般的な線形アダマール変換係数との差が小さく、該変換係数との互換性が高いことを特徴とする。
【００８２】
＜第2実施形態＞
以下、本発明に係る第2実施形態について説明する。
【００８３】
第2実施形態においては、上述した第1実施形態で計算したロスレスアダマール変換係数に対し、さらにハフマン符号等のエントロピー符号化を行うことを特徴とする。
【００８４】
ここで非特許文献2では、アダマール変換する4×4個のデータの総和が奇数か偶数かに基づいて丸め処理を切換えることで、ロスレスアダマール変換を実現するといった提案がなされている。
【非特許文献２】中山忠義, 長谷川まどか, 加藤茂夫：“ロッシーアダマール変換のPSNR改善手法とロスレスアダマール変換符号化への応用”, 画電誌, Vol.32, No.5, pp.700-708,  Sept. 2003.  上記非特許文献2に記載された丸め処理の切換えとは、オフセット行列を2種類用意し、アダマール変換対象データの総和が奇数か偶数かに応じて、それを切換えるものである。このような丸め処理の切換えは変換係数の値が分散しやすくなるので、エントロピーが増加しやすい。
【００８５】
それに対し本発明によるロスレスアダマール変換係数においては、第1実施形態で説明したように、丸め処理に用いるオフセット行列は1つでよいため、変換係数値の分散が抑えられ、非特許文献2の方法よりもエントロピーが若干小さい。その違いを図7に示す。なお、図7に示すエントロピー値は、出願人による実際の測定値に基づくものである。
【００８６】
図8に、第2実施形態を実現するための符号化装置の構成例を示す。同図において、変換対象となる4×4データが入力されると、まず線形アダマール変換部801で線形アダマール変換を施し（図2のステップS201に対応）、次にオフセット行列加算部802でオフセット行列を加算する（図2のステップS202に対応）。そして丸め処理部803でfloor関数による丸め処理を行うことによって（図2のステップS203に対応）、第1実施形態で説明したロスレスアダマール変換係数が得られる。そして該変換係数に対し、エントロピー符号化部804でエントロピー符号化処理を施すことによって、従来よりもエントロピーを抑えた符号が得られる。
【００８７】
以上説明したように第2実施形態によれば、第1実施形態で取得したロスレスアダマール変換係数をエントロピー符号化することによって、従来よりも少ない符号量でのエントロピー符号化が可能となる。
【００８８】
＜第3実施形態＞
以下、本発明に係る第3実施形態について説明する。
【００８９】
第3実施形態においては、上述した第1実施形態で計算したロスレスアダマール変換係数を、JPEG符号化処理に用いられるDCT（離散コサイン変換）処理へ適用することを特徴とする。
【００９０】
数学的にはDCT変換は可逆である。しかし、有限のビット精度での演算を行うと演算誤差が発生し、量子化ステップ1で量子化した場合であっても、逆変換により元のデータに復元されない。そこで、DCT変換処理をいくつかの処理に細分化し、それぞれをロスレス変換に置き換えることにより、DCT変換全体をロスレス変換にするといった手法が検討されている。
【００９１】
しかしながらこの手法には、ロスレス化したDCT変換（以下、ロスレスDCT変換）で得られるDCT変換係数を、一般のDCT変換処理で逆変換した際にデータの劣化が大きくなってしまうという問題がある。もちろん、一般のDCT変換処理で変換してそれを逆変換した場合にもロスレス変換ではないため、当然データは劣化するが、その劣化よりも大きな劣化が発生してしまうことになる。
【００９２】
この劣化の最大の要因は、ロスレス変換を実現する際に行う丸め処理によって発生する丸め誤差が、細分化された各々で発生するためである。たとえ各々の丸め誤差が小さくてもDCT変換全体として見ると、これがかなりの誤差となってしまう。この誤差を減らすために、DCT変換処理を細かく分割することを避け、なるべく大きな処理の単位でロスレス変換を実現することが考えられる。
【００９３】
以下に示す非特許文献3によれば、8点DCT変換処理は4点アダマール変換処理とその他の回転処理に分けられることが示されており、この4点アダマール変換処理に対して、ロスレス4点アダマール変換を適用する手法が示されている。
【非特許文献３】福間慎治, 大山公一, 岩橋政宏, 神林紀嘉：“ロスレスアダマール変換を応用したロスレス8点高速離散コサイン変換”, 信学技報, DSP99-103, pp.37-44, Oct. 1999.  8点DCT変換は1次元処理であるため、水平方向と垂直方向の各々に対して8点DCT変換を適用することで、2次元DCT変換を行うことができる。JPEG符号化等において必要となるのは、2次元DCT変換である。
【００９４】
1次元DCT変換内の4点アダマール変換は、2次元DCT変換において4×4の16点アダマール変換に置き換えられる。この置き換えは数学的な式の変形のみで済み、線形代数的に明らかな性質である。以下の非特許文献4には、1次元DCT変換内の2点アダマール変換が、2次元DCT変換では2×2の4点アダマール変換に置き換えられることが数学的に詳細に示されている。上述した置き換えは該文献からも容易に類推できる。
【非特許文献４】小松邦紀, 瀬崎薫：“2次元ロスレス変換とその画像符号化への応用”, 信学技報, IE2000-65, pp.19-26, Oct. 2000.  これにより本発明の16点ロスレスアダマール変換が2次元ロスレスDCT変換に適用可能であることが分かる。したがって、丸め処理の回数が少なく、丸め誤差の小さな2次元ロスレスDCT変換が実現できる。
【００９５】
図9に、第3実施形態における、本発明の16点ロスレスアダマール変換を用いたJPEG符号化装置のブロック構成例を示す。このJPEG符号化装置はすなわち、可逆変換機能を有したものになる。但し、可逆変換となるのは量子化ステップが1である場合に限られる。
【００９６】
図9において、2次元ロスレスDCT演算部910は16点ロスレスアダマール変換部911と、その他のロスレス回転部912からなる。16点ロスレスアダマール変換部911では第1実施形態で示した16点ロスレスアダマール変換処理を行い、その他のロスレス回転部912でその他の回転処理を行うことによって、2次元ロスレスDCT演算が実現する。そしてジグザグスキャン部920でジグザグスキャンされたDCT係数に対し、ハフマン符号化部930でハフマン符号化処理を施すことによって、JPEG符号が得られる。
【００９７】
以上説明したように第3実施形態によれば、第1実施形態で説明した16点ロスレスアダマール変換を2次元ロスレスDCT変換に適用することによって、丸め処理の回数が少なく、丸め誤差の小さな2次元ロスレスDCT変換が可能となる。すなわち、一般の2次元DCT処理で逆変換した際にも、データの劣化を抑えることができる。
【００９８】
また、該2次元ロスレスDCT変換をJPEG符号化に適用することにより、量子化ステップを1にした場合に可逆符号化が実現できると共に、該符号化の結果として得られるコードを一般の2次元DCTを用いて復号しても、復元画像の劣化を抑えることができる。すなわち、一般の非可逆な符号化装置との互換性が高い可逆符号化装置を提供することができる。
【００９９】
＜第4実施形態＞
以下、本発明に係る第4実施形態について説明する。
【０１００】
第4実施形態においては、上述した第1実施形態によって生成可能な16点ロスレスアダマール変換係数、すなわち1回の丸め処理で得られる変換係数を、さらに別の処理によって生成する方法を示す。
【０１０１】
第4実施形態では、16個のデータの和が偶数の場合のみロスレスアダマール変換を可能とする偶数ロスレスアダマール変換（上記非特許文献2に記載）と、パリティ情報を用いた処理を行うことを特徴とする。
【０１０２】
まず、第4実施形態における偶数ロスレスアダマール変換について説明する。16点の偶数ロスレスアダマール変換は、第1実施形態で説明した16点ロスレスアダマール変換よりもシンプルである。それは、丸め処理の前に加算するオフセット行列を1ビットプレーンで表現できるからである。
【０１０３】
データの和が偶数の場合、普通にアダマール変換して得られる係数の最下位ビット（この場合、小数点以下第2ビット目）が必ず0になる。したがって、オフセット行列として小数点以下第2ビット目については何も影響がないため考える必要がなく、小数点以下第1ビット目のみに着目すればよい。この小数点以下第1ビット目のオフセット行列は、上述した第1実施形態で説明した小数点以下第1ビット目と同様であるため、ここでは説明を省略する。
【０１０４】
次に、第4実施形態におけるパリティ処理についての説明に先立って、偶数パリティの概念について説明する。偶数パリティでは、n個のビットデータ中に1が偶数個ある場合にパリティビットが0になり、該ビットデータ中に1が奇数個ある場合にパリティビットが1になるように制御される。
【０１０５】
第4実施形態では偶数パリティをビットデータではなく、アダマール変換対象のデータの和に対して定義する。すなわち、16個のデータの総和が偶数なら0、奇数なら1という値をとるパリティビットを考える。
【０１０６】
[ロスレスアダマール変換]
図10に、第4実施形態におけるロスレスアダマール変換処理のフローチャートを示す。まずアダマール変換処理を行う前のデータの総和を偶数化するために、ステップS1001でパリティビットを求め、該パリティビットの値を16点データの先頭データから、あるいは4×4データの左上のデータから減算する。これにより、パリティビット減算後のデータの総和は必ず偶数となる。そして該データに対し、ステップS1003で上述した偶数ロスレスアダマール変換を適用する。なお、ステップS1001におけるロスレスアダマール変換前のパリティ演算およびパリティ減算処理を、以下では「前段のパリティ処理」と称する。
【０１０７】
ここで、ロスレス変換ではパリティが保存されるという特徴がある。すなわち、変換前のデータの和の奇偶性と、変換後の係数の和の奇偶性は一致する。したがって、総和が奇数であるデータに対して、上記前段のパリティ処理(S1001)、および偶数ロスレスアダマール変換処理(S1003)を施すと、変換係数の総和は必ず偶数になってしまう。また、総和が偶数であるデータに対する該変換係数の総和も当然偶数である。このままでは、変換係数の総和が奇数となる状態が無くなり、状態数が縮退してしまう。これでは可逆性の喪失となってしまう。
【０１０８】
そこで第4実施形態では、元のデータの和が奇数であったという情報を変換係数へ付加するために、ステップS1005にて、変換係数のうち奇数個の係数に対して、前記パリティビットを加算する。奇数個とは具体的には、1，3，5または7個である。なお、ステップS1005における偶数ロスレスアダマール変換後のパリティ加算処理を、以下では「後段のパリティ処理」と称する。元データの総和が偶数の場合、パリティビットの加算(+0)により変換係数が変わることは無いが、総和が奇数の場合には変換係数の奇数個に対してパリティビットが加算(+1)されるため、変換係数の総和は奇数となる。その結果、データの和の奇偶性と変換係数の和の奇偶性が一致し、以下に説明するようにロスレスの逆変換が可能となる。
【０１０９】
[ロスレスアダマール逆変換]
ロスレスアダマール逆変換は、図10に示したフローチャートとは逆の手順によって処理される。すなわち、まずステップS1005に対応して、変換係数の和からパリティビットを求め、順変換時のパリティビットが加算された変換係数から該パリティビットを減算する。ここで、データの和の奇偶性と変換係数の和の奇偶性は一致しているので、変換係数から求めたパリティビットは、元データに対するパリティビットと同じ値となる。
【０１１０】
パリティビット減算後の変換係数の和は偶数に戻り、それに対して、ステップS1003に対応する偶数ロスレスアダマール変換の逆変換処理を施す。この逆変換処理では順変換時に用いたオフセット行列に対する逆変換用のオフセット行列を用いる。そして最後にステップS1001に対応して、逆変換したデータの先頭にパリティビットを加算する。
【０１１１】
[第1実施形態との等価性]
以下に、第4実施形態におけるロスレスアダマール変換処理が、上述した第1実施形態の変換処理と等価であることを示す。ここでは、下記(17)式に示す2ビットプレーンからなるオフセット行列を用いた第1実施形態のロスレスアダマール変換が、第4実施形態における前段のパリティ処理(S1001)、偶数ロスレスアダマール変換処理(S1003)、および、後段のパリティ処理(S1005)に置き換えられることを示す。この(17)式に示すオフセット行列は、データの総和が奇数偶数いずれの場合にも有効なものの1つである。
【０１１２】
【数１７】
2006065678.tif 000019
【０１１３】
ここでまず、データの総和を偶数に限定した場合について考える。この場合、オフセット行列には自由度がでてくる。下記(18)式に、データの総和を偶数に限定したオフセット行列の例を示す。奇数偶数いずれにも有効な(17)式のオフセット行列を用いた変換結果と、偶数に限定した時の(18)式の種々のオフセット行列を用いた変換結果は同じになる。
【０１１４】
【数１８】
2006065678.tif 000020
【０１１５】
このように、データの総和が偶数の時の変換処理では、前段および後段のパリティ処理の影響はまったく無いので、図10に示す処理手順を適用した場合でも、第1実施形態と同様の処理結果が得られる。
次に、データの総和を奇数に限定した場合について考える。この場合、図10の処理手順を適用して第1実施形態と同様の処理結果を得るには、ステップS1003における偶数ロスレスアダマール変換で用いるオフセット行列を次のように変更する必要がある。すなわち、(17)式の全要素に1/4を加算した後、4/4を0/4に置き換える。これにより、下記(19)式に示すオフセット行列が得られる。
【０１１６】
【数１９】
2006065678.tif 000021
【０１１７】
(19)式のオフセット行列において、4/4が0/4に置き換えられた位置（右上の3つの変換係数）には、後段のパリティ処理(S1005)で1が加算される。
以下、第4実施形態における変換処理が、第1実施形態の変換処理と等価であること、すなわち、(19)式のオフセット行列を用いて図10のフローチャートに示す変換処理を行った場合と、(17)式のオフセット行列を用いた変換処理を行った場合とで、同じ結果が得られることを示す。
【０１１８】
すでに述べたように、前段のパリティ処理(S1001)は、データの総和が奇数の時にオール1となるアダマール変換係数の最下位ビット（小数点以下第2ビット目）を切り捨てることと等価である。言い換えると、全ての変換係数から1/4を減算したことと等価である。よって、(17)式のオフセット行列の全要素に対して1/4を加算することは、前段のパリティ処理（S1001）を打ち消す効果があると言える。なお、1/4を加算したことによって整数値(4/4)となった要素については、小数点以下を切り捨てる前に加算しても、切り捨て後に加算しても同じであるため、切り捨て後に加算することにする。
【０１１９】
これにより、小数点以下切り捨て前に加算するオフセット行列の各要素のレンジは0以上3/4以下となって、元のレンジと同じになる。言い換えると、元のオフセット行列と同種のオフセット行列となる。そして、小数点以下切り捨て後に移動した整数値の加算は、後段のパリティ処理(S1005)として実行される。したがって、図10のフローチャートに基づく変換結果は、第1実施形態における変換結果と同じになる。
【０１２０】
小数点以下切り捨て後に移動する整数値加算の数は、元の(17)式のオフセット行列中のオフセット値が3/4の個数と同じであるので、図4より、1，3，5または7個になる。
【０１２１】
また、この偶数ロスレスアダマール変換時点におけるデータの総和は偶数になっているので、上述したようにオフセット行列には自由度があり、下記(20)式に示すような1ビットプレーンで表現できるオフセット行列を用いてもよい。
【０１２２】
【数２０】
2006065678.tif 000022
【０１２３】
以上説明したように第4実施形態によれば、偶数ロスレスアダマール変換とパリティ情報を用いた処理によって、上述した第1実施形態と同様に1回の丸め処理により16点ロスレスアダマール変換係数を得ることができる。
＜第4実施形態の変形例＞
以下、上述した第4実施形態における変形例を示す。
【０１２４】
上述した第4実施形態では、偶数ロスレスアダマール変換の適用を分かりやすくするために、データの総和が偶数になるように、先頭データからパリティビットを減算する例を示した。
【０１２５】
しかし、小数点以下第1位のビットプレーンのみからなるオフセット行列（行列の要素は0と1/2のみからなる）で偶数ロスレスアダマール変換を行う場合、変換係数の小数点以下第2位の値（データの総和が奇数の時に全部1になる）がすべて切り捨てられる。これは、変換前のデータにおいて、先頭データからパリティビットを減算するのと同じことである。
【０１２６】
よって、上述した第4実施形態において、小数点以下第1位のビットプレーンのみからなるオフセット行列を用いて偶数ロスレスアダマール変換を行う場合、図10のステップS1001ではパリティビットのみを求め、パリティビットの減算を行わない、といった変形処理が可能である。
【０１２７】
また第4実施形態では、オフセット行列の全要素に1/4を加算した時に整数値(4/4)となる要素を、すべて0(0/4)に置き換えて後段のパリティ処理で1を加算する例を説明したが、オフセット行列の要素のレンジを0以上3/4以下に限定しなければ、整数値のオフセットの一部あるいは全部をそのまま残し、オフセット行列の加算時に一緒に加算してしまうことが可能である。
【０１２８】
このように、オフセット行列の要素のレンジを拡大するだけでも、この種の変形例がいくつも存在するので、当業者であれば容易に導き出せる数学的に等価な別の処理も多く存在する。当然これらは、本発明の範疇に属するといえる。
【０１２９】
＜第5実施形態＞
以下、本発明に係る第5実施形態について説明する。
【０１３０】
第5実施形態は第4実施形態と同様に、第1実施形態と数学的に等価なロスレスアダマール変換処理を提供する。基本的な処理の流れは、第4実施形態で示した図10と同様である。すなわち、前段パリティ処理、偶数ロスレスアダマール変換処理および後段のパリティ処理を行う。
【０１３１】
第4実施形態では、前段パリティ処理におけるパリティの減算先を先頭データに限定していたが、第5実施形態では、パリティの減算のみならず加算も可とし、加減算対象データも先頭データに限定しない。但し、これら演算と対象データがまったく任意に選択可能というわけではなく、第1実施形態のロスレスアダマール変換処理に用いるオフセット行列に依存して、その種類は限定される。以下、該オフセット行列が下記(21)式のパターンである場合を例として、前段パリティ処理における演算方法を説明する。
【０１３２】
【数２１】
2006065678.tif 000023
【０１３３】
データの総和が偶数となる場合、パリティ処理の影響がないので、第5実施形態における変換結果は第1実施形態ならびに第4実施形態と同じとなる。よって以下では、データの総和が奇数となる場合に限定して説明を行う。
加算結果が0以上1未満に収まり、±1/4の要素が規則性のある特定パターン（詳細は後述する）になるという条件下で、(21)式に示すオフセット行列から加算できるパターンとして、下記(22)または(23)式のパターンがある。
【０１３４】
【数２２】
2006065678.tif 000024
【０１３５】
【数２３】
2006065678.tif 000025
【０１３６】
ここでは、(22)式のパターンに着目する。
(21)式に(22)式を加算し、整数値(4/4)を0に置き換えることにより、(24)式が得られる。
【０１３７】
【数２４】
2006065678.tif 000026
【０１３８】
これを偶数ロスレスアダマール変換の1ビットプレーンのオフセット行列として見ると下記(25)式のようになり、第1実施形態で示した条件(A1)(A2)(A3)を満たしている。
【０１３９】
【数２５】
2006065678.tif 000027
【０１４０】
(24)式において整数値(4/4)から0への置き換えを行った位置には、第4実施形態と同様に後段パリティ処理にて1が加算される。
ロスレスアダマール変換のオフセット行列として(24)式を用い、後段パリティ処理を行うことは、線形アダマール変換係数に(22)式を加算した後、(21)式のオフセット行列を加算して小数点以下を切り捨てることと同じである。
【０１４１】
ここで重要なのが、線形アダマール変換係数に(22)式を加算するということは、アダマール変換前のデータに下記(26)式のパターンを加算することと等価である、ということである。何故ならば、(26)式のアダマール変換結果が(22)式になるからである。ここで、上記(22)，(23)式を説明する際に用いた“特定のパターン”とは、4×4行列のどこか1ヶ所だけが1であとはすべて0である行列を、2次元4×4アダマール変換して得られるパターンを示す。なお、(23)式は下記(27)式をアダマール変換した結果、得られるパターンである。
【０１４２】
【数２６】
2006065678.tif 000028
【０１４３】
【数２７】
2006065678.tif 000029
【０１４４】
以上の説明から分かるように、アダマール変換前のデータから(26)式のパターンを減算すれば、線形アダマール変換係数への(22)式の加算処理を打ち消すことができる。
よって、データの総和が奇数となる場合、まず該データにおける(26)式の1の位置からパリティビットを減算して、データの総和を偶数化する。その後、(24)式または(25)式のオフセット行列を用いて偶数ロスレスアダマール変換を行い、最後に後段のパリティ処理を施す。その結果は、(21)式のオフセット行列を用いて第1実施形態のロスレスアダマール変換をした結果と同じになる。
【０１４５】
なお第5実施形態は上述した第4実施形態とは異なり、前段パリティ処理におけるパリティの減算を省略するという変形処理はできない。
【０１４６】
以上説明したように第5実施形態によれば、第4実施形態と同様に偶数ロスレスアダマール変換とパリティ情報を用いた処理を行う際に、パリティの加減算およびその対象データ位置を限定することなく、ロスレスアダマール変換を実現することができる。
【０１４７】
［他の実施例］
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、スキャナ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複合機など）に適用してもよい。
【０１４８】
また、本発明の目的は、前述した実施例の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体（または記録媒体）を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはCPUやMPU）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施例の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施例の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム(OS)などが実際の処理の一部または全部を行い、その処理によって前述した実施例の機能が実現される場合も含まれることは言うまでもない。
【０１４９】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるCPUなどが実際の処理の一部または全部を行い、その処理によって前述した実施例の機能が実現される場合も含まれることは言うまでもない。
【０１５０】
本発明を上記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【０１５１】
【図１】16点アダマール変換行列を示す図である。
【図２】本実施形態におけるロスレスアダマール変換処理を示すフローチャートである。
【図３】本実施形態におけるオフセット行列のビットプレーン構造の具体例を示す図である。
【図４】ビットプレーンの組み合せ毎における16個のオフセット値の内訳を表わす図である。
【図５Ａ】8種類に分類されたのオフセット行列の具体例を示す図である。
【図５Ｂ】8種類に分類されたのオフセット行列の具体例を示す図である。
【図６】286720種類の有効オフセット行列の一例を示す図である。
【図７】ロスレスアダマール変換係数のエントロピー例を示す図である。
【図８】第2実施形態における、本発明のロスレスアダマール変換を用いた符号化装置の構成を示すブロック図である。
【図９】第3実施形態における、本発明のロスレスアダマール変換を用いたJPEG符号化装置の構成を示すブロック図である。
【図１０】第4実施形態および第5実施形態におけるロスレスアダマール変換処理を示すフローチャートである。
【図１】
2006065678.tif 000030
【図２】
2006065678.tif 000031
【図３】
2006065678.tif 000032
【図４】
2006065678.tif 000033
【図５Ａ】
2006065678.tif 000034
【図５Ｂ】
2006065678.tif 000035
【図６】
2006065678.tif 000036
【図７】
2006065678.tif 000037
【図８】
2006065678.tif 000038
【図９】
2006065678.tif 000039
【図１０】
2006065678.tif 000040