図面 (/)

この項目の情報は公開日時点(2006年3月2日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (15)

課題

簡単な構成でもって、4つのベクトルデータの丸め誤差の少ないロスレス4点直交変換を行う。

解決手段

整数表現される4つのベクトルデータX0、X1、X2、X3を入力し、行列演算、 によって、1より大きな奇数である係数aに従って、4つの整数のベクトルデータから整数で表現される変換データを求めるデータ変換装置であって、先ず、D0乃至D3を求める(S301)。そして、D1に除数{1+a2}の半分の値より小さい整数データ加算してE1を求め、残りのD0、D2、D3に除数の半分の値を加算することで除算前の補正データE0、E2、E4を求める(S303)。次に、E0乃至E4を除数で除算して、その結果Y0、Y1、Y2、Y3を出力する(S305)。

概要

背景

静止画像国際標準符号化方式であるJPEGにおいて、圧縮・伸張後の画像が元画像と完全に一致するよう可逆符号化モードが規格化されたが、当時はロスレス変換技術が十分研究されておらず、DCTを用いてロスレス変換を実現することができなかった。そのため、DCTを用いたブロック変換符号化とは異なる技術を用い、画素単位予測符号化という方法で可逆符号化を実現していた。

その後、可逆符号化専用の標準符号化技術:JPEG−LSが規格化されたが、さらに後に規格化されたJPEG2000では、ウェーブレット変換という共通技術でロスレス変換とロスレスではない一般の変換を実現し、それにより劣化の無い可逆符号化と劣化を伴う非可逆符号化の両方の符号化が可能となった。

画像データの圧縮変換処理は、大きく分けて、空間変換処理(DCTやウェーブレット変換等)、量子化処理エントロピー符号化処理の3つに分けられる。この中でエントロピー符号化処理は、量子化された値の集まり(情報)をハフマン符号などの他の符号に変換することにより、前記情報が持つエントロピーに近いビット数に変換するものであり、一種のロスレス変換処理である。

一方、量子化処理は、情報量を削減する工程で、これにより圧縮率の制御も可能となるもので、基本的にロッシー変換である。従って、変換符号化圧縮処理でロスレスとなるようにするには、この量子化処理をしてはならない。しかし、空間変換処理の結果が小数点以下の値を有する時、これを量子化しないと、圧縮前のデータ量よりも圧縮後のデータ量の方が大きくなってしまう。

空間変換処理の結果が小数点以下の値を有する時に、量子化ステップ“1”で量子化することは、それを整数化することになるので、ここで信号の劣化が生じて、伸張後のデータが元のデータと一致するという保証が無くなる。

結局、可逆符号化を実現するには、可逆性が保証された整数値を出力する空間変換処理で得られた値(ロスレス変換係数という)を量子化しないで、そのままエントロピー符号化する必要があることがわかる。この場合、量子化ステップ“1”で量子化しても変換係数がそのまま保持されるので、量子化ステップ“1”で量子化処理をしているという見方もある。

このように、可逆符号化を実現するには、可逆性が保証された整数値を出力する空間変換処理(以下では単に“ロスレス変換”と称す)が必要不可欠である。

従来、そのようなロスレス変換を実現する手法として、Ladder Network(以下では“梯子演算回路網”と称す)というものがあった(非特許文献1)。これは、2点回転変換行列を3つの三角行列に分解し、各々の三角行列を1つの梯子演算に置き換えた後、各梯子演算に丸め処理を導入したものである。また、これを4点直交変換拡張したものもある(非特許文献2)。

以下では、ロスレス2点回転変換とロスレス4点直交変換について、更に詳しく説明する。

2点回転変換行列は下式のように対角成分が“1”の3つの三角行列の積に分解できる。

2つの入力データを2本梯子と見なすと、対角成分が“1”の三角行列の演算構造的に梯子の横木に対応する。すなわち、三角行列の非対角成分の演算は、一方の入力に該成分値乗算し、それをもう一方の入力に加算するものであるから、それをシグナルフローグラフ表現すると、梯子の横木に見えるわけである。よって、2点回転変換は、図1(a)に示すように3段の梯子演算で表現できる。

図1(b)に示すように、各梯子演算における乗算処理後の値を丸め処理して整数化することにより、容易に整数値から整数値へのロスレス変換が実現できる。よって、梯子演算を用いたロスレス変換においては、乗算処理部、丸め処理部、加算処理部(減算処理の場合もある)の3つの処理部で構成できる。図1(b)において、符号111,121,131が乗算処理部であり、113,123,133が丸め処理部であり、115,125,135が加算処理部である。回転角がθであるときの乗算係数は、111,121,131の順に、TAN(θ/2)、−SIN(θ)、TAN(θ/2)である。

梯子演算1段ごとに乗算結果を整数化するための丸め処理を行なうことにより、乗算結果が整数でない限り必ず丸め誤差が発生し、各梯子演算で発生する誤差は出力データに蓄積される。

従来、2点回転変換処理4つからなる4点直交変換のロスレス変換は、図2のように構成されていた。ここで、符号201〜204は各々2点回転変換で、図1(b)に示すように3段の梯子演算で構成される。ロスレス4点直交変換全体でみると、12段の梯子演算があり、同じく12回の丸め処理が行なわれる。当然のように、丸め処理の回数に比例して丸め誤差が増える。

一方、非特許文献2では、4点直交変換を4次元に対応・拡張した梯子演算5回に分割して、ロスレス変換を実現している。n次元の1回の梯子演算は、n−1回の乗算演算を伴うので、4点直交変換では(4−1)×5=15回の乗算演算が必要になる。しかし、梯子演算の性質上、丸め処理を大幅に減らすころができる。多次元の梯子演算では、梯子演算の梯子の先(加算対象となるデータ)が1つのデータに集中するので、それらのデータを合算してから丸め処理を行なうことができ、梯子演算1回につき1回の丸め処理で済ますことができる。よって、非特許文献2の4点直交変換では5回の丸め処理で済む。
F.Bruekers and A.Enden,“New Networks for Perfect Invention and Reconstruction”IEEE JSAC,vol.10,no.1.pp.130−137,Jan 1992
邦紀、崎薫、“可逆的離散コサイン変換とその画像情報圧縮への応用”、信学技報、IE97−83、pp.1−6、1997年11月

概要

簡単な構成でもって、4つのベクトルデータの丸め誤差の少ないロスレス4点直交変換を行う。整数で表現される4つのベクトルデータX0、X1、X2、X3を入力し、行列演算、 によって、1より大きな奇数である係数aに従って、4つの整数のベクトルデータから整数で表現される変換データを求めるデータ変換装置であって、先ず、D0乃至D3を求める(S301)。そして、D1に除数{1+a2}の半分の値より小さい整数データを加算してE1を求め、残りのD0、D2、D3に除数の半分の値を加算することで除算前の補正データE0、E2、E4を求める(S303)。次に、E0乃至E4を除数で除算して、その結果Y0、Y1、Y2、Y3を出力する(S305)。

目的

効果

実績

技術文献被引用数
2件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

整数表現される4つのベクトルデータX0、X1、X2、X3を入力し、行列演算、によって、1より大きな奇数である係数aに従って、整数で表現される変換データを求めるデータ変換装置であって、係数a、及び、ベクトルデータX0、X1、X2、X3を入力し、記憶保持する記憶保持手段と、以下の演算を行う第1乃至第4の演算手段と、第1演算手段:D0=X0+aX1+aX2+a2X3第2演算手段:D1=aX0−X1+a2X2−aX3第3演算手段:D2=aX0+a2X1−X2−aX3第4演算手段:D3=a2X0−aX1−aX2+X3前記記憶保持手段に記憶保持された係数a、ベクトルデータX0、X1、X2、X3を前記第1乃至第4の演算手段に分配する分配手段と、前記第1乃至第4の演算手段で得られたデータD0、D1、D2、D3の少なくとも1つに対して、除数{1+a2}の半分の値より小さい整数データ加算し、残りに除数の半分の値を加算することで除算前の補正データD0'、D1'、D2'、D3'を演算する補正演算手段と、該補正演算手段によって得られた補正データD0'、D1'、D2'、D3'を、前記除数で除算し、該除算結果を値が小さくなる方向へ小数点以下の値を切り捨てて、変換データとして出力する出力手段とを備えることを特徴とするデータ変換装置。

請求項2

整数で表現される4つのベクトルデータX0、X1、X2、X3を入力し、行列演算、によって、1より大きな奇数である係数aに従って、整数で表現される変換データを求めるデータ変換方法であって、係数a、及び、ベクトルデータX0、X1、X2、X3を入力し、記憶保持する記憶保持工程と、以下の演算を行う第1乃至第4の演算工程と、第1演算工程:D0=X0+aX1+aX2+a2X3第2演算工程:D1=aX0−X1+a2X2−aX3第3演算工程:D2=aX0+a2X1−X2−aX3第4演算工程:D3=a2X0−aX1−aX2+X3前記記憶保持工程に記憶保持された係数a、ベクトルデータX0、X1、X2、X3を前記第1乃至第4の演算工程に分配する分配工程と、前記第1乃至第4の演算工程で得られたデータD0、D1、D2、D3の少なくとも1つに対して、除数{1+a2}の半分の値より小さい整数データを加算し、残りに除数の半分の値を加算することで除算前の補正データD0'、D1'、D2'、D3'を演算する補正演算工程と、該補正演算工程によって得られた補正データD0'、D1'、D2'、D3'を、前記除数で除算し、該除算結果を値が小さくなる方向へ小数点以下の値を切り捨てて、変換データとして出力する出力工程とを備えることを特徴とするデータ変換装方法。

請求項3

有効ビットmビットの整数で表現される4つのベクトルデータX0、X1、X2、X3を入力し、行列演算、によって、1より大きな奇数である係数aに従って、整数で表現される有効ビット数がmビットの変換データY0、Y1、Y2、Y3を求めるデータ変換装置であって、係数a、及び、ベクトルデータX0、X1、X2、X3を入力し、記憶保持する記憶保持手段と、演算の際の有効ビット数をnとしたとき、2nを除数{1+a2}で除算した際の整数の商の値R0を演算する第1の前処理演算手段と、該第1の演算手段で求めた商に1を加算した値R1を演算する第2の前処理演算手段と、前記係数aと前記mに基づき、オフセット値を演算する第3の前処理演算手段と、以下の演算を行う第1乃至第4の演算手段と、第1演算手段:D0=X0+aX1+aX2+a2X3第2演算手段:D1=aX0−X1+a2X2−aX3第3演算手段:D2=aX0+a2X1−X2−aX3第4演算手段:D3=a2X0−aX1−aX2+X3前記記憶保持手段に記憶保持された係数a、ベクトルデータX0、X1、X2、X3を前記第1乃至第4の演算手段に分配する分配手段と、前記第1乃至第4の演算手段で得られたデータD0、D1、D2、D3に、前記除数の半分の値を加算する第1の加算手段と、該第1の加算手段で加算した4つのデータのうち、3つに対して前記第3の前処理演算手段で得られたオフセット値を加算する第2の加算手段と、該第2の加算手段の加算の少なくとも1つに前記値R1を乗算し、残りに前記R0を乗算する乗算手段と、該乗算手段で乗算した結果を、前記2nで除算するため、nビット分だけ下位方向にシフトするシフト手段と、シフト手段で得られた値のうち、前記第2の加算手段での加算対象となったデータについて前記オフセットに対応する値を減算する減算手段とを備えることを特徴とするデータ変換装置。

請求項4

有効ビットがmビットの整数で表現される4つのベクトルデータX0、X1、X2、X3を入力し、行列演算、によって、1より大きな奇数である係数aに従って、整数で表現される有効ビット数がmビットの変換データY0、Y1、Y2、Y3を求めるデータ変換方法であって、係数a、及び、ベクトルデータX0、X1、X2、X3を入力し、記憶保持する記憶保持工程と、演算の際の有効ビット数をnとしたとき、2nを除数{1+a2}で除算した際の整数の商の値R0を演算する第1の前処理演算工程と、該第1の演算工程で求めた商に1を加算した値R1を演算する第2の前処理演算工程と、前記係数aと前記mに基づき、オフセット値を演算する第3の前処理演算工程と、以下の演算を行う第1乃至第4の演算工程と、第1演算工程:D0=X0+aX1+aX2+a2X3第2演算工程:D1=aX0−X1+a2X2−aX3第3演算工程:D2=aX0+a2X1−X2−aX3第4演算工程:D3=a2X0−aX1−aX2+X3前記記憶保持工程に記憶保持された係数a、ベクトルデータX0、X1、X2、X3を前記第1乃至第4の演算工程に分配する分配工程と、前記第1乃至第4の演算工程で得られたデータD0、D1、D2、D3に、前記除数の半分の値を加算する第1の加算工程と、該第1の加算工程で加算した4つのデータのうち、3つに対して前記第3の前処理演算工程で得られたオフセット値を加算する第2の加算工程と、該第2の加算工程の加算の少なくとも1つに前記値R1を乗算し、残りに前記R0を乗算する乗算工程と、該乗算工程で乗算した結果を、前記2nで除算するため、nビット分だけ下位方向にシフトするシフト工程と、シフト工程で得られた値のうち、前記第2の加算工程での加算対象となったデータについて前記オフセットに対応する値を減算する減算工程とを備えることを特徴とするデータ変換方法。

請求項5

4つの整数で構成されるベクトルデータに下記行列(aは4以上の偶数)を乗算する積和演算手段と、該演算結果に整数値を加算する手段と、1+a×aなる除数でもって割り算を行なって商を求める除算手段と、該商が持つ丸め誤差を求める誤差演算手段と、丸め誤差が所定の範囲に入っているかどうかを判定する手段とを有し、該判定結果に基づき、4つの商の一部に1を加算もしくは減算することを特徴とするデータ変換装置。

請求項6

4つの整数からなるベクトルデータに下記行列(aは4以上の偶数)を乗算する積和演算工程と、該演算結果に整数値を加算する手段と、1+a×aなる除数でもって割り算を行なって商を求める除算工程と、該商が持つ丸め誤差を求める誤差演算工程と、丸め誤差が所定の範囲に入っているかどうかを判定する工程とを備え、該判定結果に基づき、4つの商の一部に1を加算もしくは減算することを特徴とするデータ変換方法。

請求項7

請求項1又は3又は5に記載のデータ変換処理装置を一部に用いたことを特徴とする2次元DCT変換処理装置

請求項8

請求項1又は3又は5に記載のデータ変換処理装置を一部に用いたことを特徴とする可逆符号化処理装置。

技術分野

0001

本発明は整数データから整数データへの可逆変換が可能なロスレス4点直交変換処理方法、および、該変換処理装置に関する。

背景技術

0002

静止画像国際標準符号化方式であるJPEGにおいて、圧縮・伸張後の画像が元画像と完全に一致するよう可逆符号化モードが規格化されたが、当時はロスレス変換技術が十分研究されておらず、DCTを用いてロスレス変換を実現することができなかった。そのため、DCTを用いたブロック変換符号化とは異なる技術を用い、画素単位予測符号化という方法で可逆符号化を実現していた。

0003

その後、可逆符号化専用の標準符号化技術:JPEG−LSが規格化されたが、さらに後に規格化されたJPEG2000では、ウェーブレット変換という共通技術でロスレス変換とロスレスではない一般の変換を実現し、それにより劣化の無い可逆符号化と劣化を伴う非可逆符号化の両方の符号化が可能となった。

0004

画像データの圧縮変換処理は、大きく分けて、空間変換処理(DCTやウェーブレット変換等)、量子化処理エントロピー符号化処理の3つに分けられる。この中でエントロピー符号化処理は、量子化された値の集まり(情報)をハフマン符号などの他の符号に変換することにより、前記情報が持つエントロピーに近いビット数に変換するものであり、一種のロスレス変換処理である。

0005

一方、量子化処理は、情報量を削減する工程で、これにより圧縮率の制御も可能となるもので、基本的にロッシー変換である。従って、変換符号化圧縮処理でロスレスとなるようにするには、この量子化処理をしてはならない。しかし、空間変換処理の結果が小数点以下の値を有する時、これを量子化しないと、圧縮前のデータ量よりも圧縮後のデータ量の方が大きくなってしまう。

0006

空間変換処理の結果が小数点以下の値を有する時に、量子化ステップ“1”で量子化することは、それを整数化することになるので、ここで信号の劣化が生じて、伸張後のデータが元のデータと一致するという保証が無くなる。

0007

結局、可逆符号化を実現するには、可逆性が保証された整数値を出力する空間変換処理で得られた値(ロスレス変換係数という)を量子化しないで、そのままエントロピー符号化する必要があることがわかる。この場合、量子化ステップ“1”で量子化しても変換係数がそのまま保持されるので、量子化ステップ“1”で量子化処理をしているという見方もある。

0008

このように、可逆符号化を実現するには、可逆性が保証された整数値を出力する空間変換処理(以下では単に“ロスレス変換”と称す)が必要不可欠である。

0009

従来、そのようなロスレス変換を実現する手法として、Ladder Network(以下では“梯子演算回路網”と称す)というものがあった(非特許文献1)。これは、2点回転変換行列を3つの三角行列に分解し、各々の三角行列を1つの梯子演算に置き換えた後、各梯子演算に丸め処理を導入したものである。また、これを4点直交変換拡張したものもある(非特許文献2)。

0010

以下では、ロスレス2点回転変換とロスレス4点直交変換について、更に詳しく説明する。

0011

2点回転変換行列は下式のように対角成分が“1”の3つの三角行列の積に分解できる。

0012

2つの入力データを2本梯子と見なすと、対角成分が“1”の三角行列の演算構造的に梯子の横木に対応する。すなわち、三角行列の非対角成分の演算は、一方の入力に該成分値乗算し、それをもう一方の入力に加算するものであるから、それをシグナルフローグラフ表現すると、梯子の横木に見えるわけである。よって、2点回転変換は、図1(a)に示すように3段の梯子演算で表現できる。

0013

図1(b)に示すように、各梯子演算における乗算処理後の値を丸め処理して整数化することにより、容易に整数値から整数値へのロスレス変換が実現できる。よって、梯子演算を用いたロスレス変換においては、乗算処理部、丸め処理部、加算処理部(減算処理の場合もある)の3つの処理部で構成できる。図1(b)において、符号111,121,131が乗算処理部であり、113,123,133が丸め処理部であり、115,125,135が加算処理部である。回転角がθであるときの乗算係数は、111,121,131の順に、TAN(θ/2)、−SIN(θ)、TAN(θ/2)である。

0014

梯子演算1段ごとに乗算結果を整数化するための丸め処理を行なうことにより、乗算結果が整数でない限り必ず丸め誤差が発生し、各梯子演算で発生する誤差は出力データに蓄積される。

0015

従来、2点回転変換処理4つからなる4点直交変換のロスレス変換は、図2のように構成されていた。ここで、符号201〜204は各々2点回転変換で、図1(b)に示すように3段の梯子演算で構成される。ロスレス4点直交変換全体でみると、12段の梯子演算があり、同じく12回の丸め処理が行なわれる。当然のように、丸め処理の回数に比例して丸め誤差が増える。

0016

一方、非特許文献2では、4点直交変換を4次元に対応・拡張した梯子演算5回に分割して、ロスレス変換を実現している。n次元の1回の梯子演算は、n−1回の乗算演算を伴うので、4点直交変換では(4−1)×5=15回の乗算演算が必要になる。しかし、梯子演算の性質上、丸め処理を大幅に減らすころができる。多次元の梯子演算では、梯子演算の梯子の先(加算対象となるデータ)が1つのデータに集中するので、それらのデータを合算してから丸め処理を行なうことができ、梯子演算1回につき1回の丸め処理で済ますことができる。よって、非特許文献2の4点直交変換では5回の丸め処理で済む。
F.Bruekers and A.Enden,“New Networks for Perfect Invention and Reconstruction”IEEE JSAC,vol.10,no.1.pp.130−137,Jan 1992
邦紀、崎薫、“可逆的離散コサイン変換とその画像情報圧縮への応用”、信学技報、IE97−83、pp.1−6、1997年11月

発明が解決しようとする課題

0017

上記のように、ロスレス変換というのは、その可逆性を保証するために梯子演算という特殊な演算を行なう必要があるため、既に多くの研究がなされている高速演算アルゴリズムなどを適用することができず、演算量を減らすことが困難である。換言すれば、これまでのロスレス変換は、特殊な演算が必要であり、高速化に適したものとは言えなかった。また、丸め処理が多いため、丸め誤差が大きいという欠点もあった。

0018

本発明はかかる問題点に鑑みなされたものであり、装置に実装した際に、簡単な構成でもって、4つのベクトルデータの丸め誤差の少ないロスレス4点直交変換を行う技術を提供しようとするものである。

課題を解決するための手段

0019

この課題を解決するため、本発明のデータ変換装置は以下の構成を備える。すなわち、
整数で表現される4つのベクトルデータX0、X1、X2、X3を入力し、
行列演算

によって、1より大きな奇数である係数aに従って、整数で表現される変換データを求めるデータ変換装置であって、
係数a、及び、ベクトルデータX0、X1、X2、X3を入力し、記憶保持する記憶保持手段と、
以下の演算を行う第1乃至第4の演算手段と、
第1演算手段:D0=X0+aX1+aX2+a2X3
第2演算手段:D1=aX0−X1+a2X2−aX3
第3演算手段:D2=aX0+a2X1−X2−aX3
第4演算手段:D3=a2X0−aX1−aX2+X3
前記記憶保持手段に記憶保持された係数a、ベクトルデータX0、X1、X2、X3を前記第1乃至第4の演算手段に分配する分配手段と、
前記第1乃至第4の演算手段で得られたデータD0、D1、D2、D3の少なくとも1つに対して、除数{1+a2}の半分の値より小さい整数データを加算し、残りに除数の半分の値を加算することで除算前の補正データD0'、D1'、D2'、D3'を演算する補正演算手段と、
該補正演算手段によって得られた補正データD0'、D1'、D2'、D3'を、前記除数で除算し、該除算結果を値が小さくなる方向へ小数点以下の値を切り捨てて、変換データとして出力する出力手段とを備える。

発明の効果

0020

本発明によれば、4つのベクトルデータに整数要素からなる4×4の行列を乗算する手段と、該乗算結果に整数値を加算する手段と、割り算を行なう際に値が小さくなる方向へ切り捨てを行なう除算手段を有し、前記加算手段において、少なくとも1つ以上のデータに対し、除数の半分の値よりも小さな整数値を加算することにより、丸め誤差の少ないロスレス4点直交変換を実現することができる。

0021

4つの整数からなるベクトルデータに4×4の整数行列を乗算する積和演算手段と、該演算結果に整数値を加算する手段と、割り算を行なう際に値が小さくなる方向へ切り捨てを行なって商を求める除算手段と、該商が持つ丸め誤差を求める誤差演算手段と、丸め誤差の絶対値が所定の範囲に入っているかどうかを判定する手段と、丸め誤差の負号を判定する手段とを有し、該判定結果に基づき、4つの商の内の1つに1を加算もしくは減算することにより、丸め誤差の少ないロスレス4点直交変換を実現することができる。また、この種の整数行列の乗算処理には、いろいろな高速演算アルゴリズムがあるので、それらを用いることにより高速に変換処理することができる。

発明を実施するための最良の形態

0022

以下、添付図面に従って本発明に係る実施形態を詳細に説明する。

0023

<第1の実施形態>
本第1の実施形態のロスレス4点変換では、従来行なわれていた梯子演算を用いず、変換前の4つの整数データに対して、整数要素で構成される4×4の行列を乗算し、次に割り算を行なう際の除数の半分の値、もしくは、除数の半分の値よりも小さな値を加算し、最後に値が小さくなる方向へ切り捨てを行なう除算を行なう。

0024

第1の実施形態では、少なくとも1つ以上のデータに対し、前記除数の半分の値よりも小さな値を加算するものである。本実施形態が対象としている変換は、下記(1)式で表現される。

…(1)

0025

上式において、X0,X1,X2,X3は変換前の4つの整数データであり、aは自然数である。ここで、当業者が普通と考える方法で処理した場合の変換例を示す。ここでは、仮に、a=3とし、4つのデータX0、X1、X2、X3がそれぞれ下記の値を持つものとする。
17, 12, 9, 55
ただし、変換結果を整数値で得るため(1+a*a)=10で除算する前に、(1+a*a)/2=5を、各々の演算途中のデータに加算する。この演算結果は次のようになる。
58, −4, −1, 15
これを、同じ変換処理で再変換すると次のようになる。
18, 12, 9, 55

0026

前記の式(1)は数学的に可逆な変換であり、それ自身が逆変換でもある。即ち、整数化せずに式1の変換を2回行なえば、元のデータに戻り、変換前のデータと2回変換後のデータは一致する。

0027

ところが、上の結果ではそうなっていない。この原因は1回目の変換結果を整数化することにより丸め誤差が発生し、該丸め誤差が逆変換時に1番目のデータX0に集中し、逆変換時の四捨五入でそれを打ち消すことができないからである。

0028

ここで、さらに細かく四捨五入の丸め誤差について見ていく。除算演算において10で割る場合、小数点以下の値が0.1単位の値をとる。小数点以下の値が0.1〜0.4の場合には切り捨てを行い、小数点以下が0.6〜0.9の場合に切り上げると、最大で±0.4の丸め誤差が発生するが、この誤差は正負対称に発生する誤差である。

0029

一方、小数点以下の値が0.5の場合、これを切り上げると+0.5の丸め誤差が発生し、これを切り捨てると−0.5の丸め誤差が発生する。この誤差は正負非対称に発生する誤差である。四捨五入という丸め処理は、小数点以下の0.5を切り上げるので、+0.5の非対称誤差を生み出す。

0030

上記、変換・逆変換処理で、元のデータに戻らない原因は、この非対称誤差にあることを突き止めた。原因が非対称誤差にあるため、小数点以下の0.5を切り捨てると、今度は−0.5の非対称誤差が発生するので、やはり、変換・逆変換で元のデータに戻ることはない。

0031

本実施形態では、式(1)をベースにした整数値から整数値への変換においてロスレス変換を実現する。そのために、図3に示す順変換処理図4に示す逆変換処理を提案する。これが本発明の第1の実施形態の特徴点である。

0032

図3におけるステップS301は積和演算処理、ステップS303は加算処理、ステップS305は除算処理である。図4図3とほぼ同じであるがステップS403の加算処理が多少異なる。本実施形態の処理で特徴的なのは、ステップS303、ステップS403で加算する値が、除数(=a2+1)の半分より小さな値があるということである。

0033

即ち、図3のステップS303の2番目の加算演算と、図4のステップS403の3番目以外の加算演算において、除数(=10)の半分の値(=5)より小さな値“4”を加算する。このような加算処理を行なうと、順変換処理と逆変換処理の結果は以下のようになる。
順変換処理後: 58, −5, −1, 15
逆変換処理後: 17, 12, 9, 55
上記の様に、逆変換処理後のデータは、元のデータに一致していることが分かる。従来のような梯子演算を用いてロスレス変換を実現する方法ではなく、本実施形態に示した方法によっても、ロスレス変換を実現できることが示せた。

0034

なお、上記順変換処理と逆変換処理は互いに相補的な関係にある。即ち、逆変換処理をした後、順変換処理をしても元のデータに戻る。よって、図4の処理も順変換処理の1つに入る。この時の逆変換処理は当然図3に示す処理となる。図4の処理を順変換処理として見た時、3つのデータに対して、前記除数の半分の値より小さな値を加算することになる。

0035

図14は上記図3図4の処理を行うための具体的回路構成を示している。図示における各構成要素の全ては整数データを処理するものである点に注意されたい。つまり、以下に説明する「除算」では、余りが発生した、もしくは小数点以下にデータが発生した場合にはそれを切り捨てる。

0036

図示において、符号1乃至5は多ビットのデータを保持するレジスタであり、レジスタ1乃至4は変換元の上記X0乃至X3を記憶保持し、レジスタ5は上記aを記憶保持する。また、符号6もレジスタであるが、これには順変換図3)/逆変換(図4)を切替えるものであって1ビットのデータを保持する。

0037

符号7乃至10は整数演算器であって、それぞれはレジスタ1乃至5から分配されたデータを入力し、図示の演算を行う。これら整数演算器7乃至10は、図3のステップS301、又は、図4のステップS401に相当する演算を行うものでもあり、整数の加算器及び乗算器で構成されるものであって、演算誤差は発生しない。

0038

符号11も整数演算器であり、レジスタ5に格納されたaを二乗し、それに“1”を加算した結果「a*a+1」を出力する。符号12は入力したデータを2で除算する除算器である。2の除算は、1ビット右(下位方向)シフトで実現できるので、除算器12はビットシフト器で構成し得る。符号13は除算器12の出力データから“1”を減算する減算器である。

0039

符号15乃至18はそれぞれ加算器であって、該加算器に入力された2つのデータを加算し、その結果を出力する。19乃至22は除算器であって、入力端子Pのデータを、入力端子Qのデータで除算する。

0040

符号14はセレクタであって、レジスタ6にセットされた値(0or1)に応じて、入力端子P、Qに入力されたデータを選択し、加算器15乃至18に出力する。具体的には、レジスタ6にセットされた値が“0”(順変換)の場合、入力端子Pより入力したデータを加算器16に出力し、入力端子Qより入力したデータを加算器15、17、18に出力する。また、レジスタ6にセットされた値が“1”(逆変換)の場合には、入力端子Pから入力したデータを加算器15、16、18に出力し、入力端子Qから入力したデータを加算器17に出力する。

0041

より詳しくは、レジスタ6に“0”をセットすると、加算器16には「(a*a+1)/2−1」が供給され、加算器15、17、18には「(a*a+1)/2」が供給される。また、レジスタ6に“1”をセットすると、加算器17には「(a*a+1)/2」が供給され、加算器15、16、18には「(a*a+1)/2−1」が供給される。レジスタ6に“0”をセットした変換を順変換とすると、レジスタ6に“1”をセットした変換は逆変換となるが、順変換と逆変換は相対的なものであり、レジスタ6に“1”をセットした変換を順変換と捉えれば、レジスタ6に“0”をセットした変換は逆変換となる。

0042

更に具体的に述べると、レジスタ5にaの値として“3”をセットし、レジスタ6に“0”をセットした場合、加算器15乃至18は、ちょうど図3のステップS303の処理を行うことになる。一方、レジスタ6に“1”をセットすると、加算器15乃至18は図4のステップS403の処理を行うことになる。

0043

以上の結果、図14の回路構成によって、順変換、逆変換処理を切替えることが可能となる。

0044

なお、ステップS303,S403以外の加算処理方法もある点に注意されたい。一例として、ステップS303における“4”の加算演算を2番目から3番目に変更してもよい。これに対応する逆変換の加算処理は2番目の加算演算で“5”を加算し、2番目以外の加算演算で“4”を加算したものとなる。

0045

本実施形態においては、aの値が“3”に限定されるものでない。また、aの値が3以上の奇数の逆数であってもよい。何故なら、前記式1全体をn2倍すると、係数“1”と係数“a2”の負号とが入れ替わり変数aがnに置き換わるが、結局、変換前後のデータを置換すると元の式1の変換と同じになるからである。

0046

さらに、式(1)の直交変換行列の行の置換や負号反転等の操作によって、上記のような順変換と逆変換の対応が変わってくるが、その範疇で考えられる処理の変形は本実施形態の範囲内であることは言うまでも無い。

0047

本実施形態は、データ変換処理方法として説明してあるが、各演算処理を実行する演算器を用意して、図3図4処理フローの順に従って、各演算器を接続しデータを処理させれば、ロスレスデータ変換処理装置を構成できる。これは当業者であれば容易に考えられることである。

0048

また、aの値が偶数の時、除数(1+a*a)は奇数になるので、該除数の半分の値は整数+0.5という値になる。この場合は、全部の4つの加算演算において前記整数部のみを加算すればロスレス変換になってしまう。よって、4つとも除数を1ビット右シフトした値を加算すればよい。

0049

これに対処するためには、図14における減算器13は、値aの最下位ビット(LSB)を減算する処理を行えば良い。つまり、aの値が偶数の場合、該LSBは“0”になるので、減算器13は“1”を減じる処理を行わず、整数部分のみを出力する。この場合、セレクタ14の入力端子P,Qの値は同じになるため、どちらの入力を選択しても出力は同じである。

0050

<第2の実施形態>
ハードウェアでは除算を乗算に置き換えた方が処理が容易になり、除算速度の遅いマイクロコントローラにおいても、このような処理の置き換えにより高速化が図れる。このような状況に対応するため、本第2の実施形態は、前記式1の変換における除算演算を、該除数の逆数の乗算演算と小数点以下の切り捨て処理に置き換えたものである。

0051

10進数で切りのよい数字でも、プロセッサの内部数値表現である2進数では、無限小数になることがある。10の逆数である0.1を2進数表現すると0.000110012(下線部は循環小数)となる。

0052

演算では無限小数を扱うことが出来ないので、上記循環小数は有限小数に丸めなければならない。その際、通常は丸め後の桁数によって、切り上げになったり、切り捨てになったりする。例えば、小数点9桁(ビット)に丸める場合、0.0001100112にするのが誤差が一番少なく、小数点11桁(ビット)に丸める場合、0.000110011012にするのが誤差が一番少ない。結果として、前者は切り捨て、後者は切り上げ処理になっている。

0053

本実施形態では、切り捨て・切り上げ処理した2種類の有限小数を使い分ける。即ち、有限ビットの小数に丸めた値として、切り捨て処理した値と切り上げ処理した値の両方を用意する。有効ビット数の大きな小数の切り捨て・切り上げを厳密に管理するには、固定小数点で扱うのが一般的である。

0054

そのために、本第2の実施形態の処理を表す図5のステップS501にて、除数の逆数を所定ビットに切り上げ処理した値と、切り捨て処理した値を固定小数点で計算する。該固定小数点の有効ビット数をn、除数(1+a*a)をdとすると、2をn乗した値(1をnビット左シフトした値)を除数dで割った時の余りが0以外の場合(実施形態では、これを通常の場合と考えている)、その時の商が、前記切り捨て処理した固定小数点の逆数r0になる。該逆数の最下位ビットの重みは2-nである。そして、前記逆数r0に1を加算したものが、前記切り上げ処理した固定小数点の逆数r1になる。前記有効ビット数nの決め方については後述する。

0055

前記余りが0となるのは、除数(1+a*a)が2のべき乗となる時のみであり、そのような関係は少なくとも想定している範囲では有りえない(数学的にも存在しないと考えられる)。そして、除数d、逆数r0、r1以外に、除数dの半分の値をhに、後述するオフセットをfに求めておく。

0056

以上で説明したS501の処理は、画像データなどの大量のデータを直交変換する前に一度計算しておくだけでよい。

0057

上記説明で計算した2種類の逆数を用いて、以下に説明するロスレスの4点直交変換を行なう。

0058

まず、ステップS502の積和演算処理は、図3のステップS301とまったく同じ処理を行なう。次に、ステップS503の第1の加算処理では、前記除数の半分の値を加算する。前記第1の実施形態では、除数の半分の値と、半分より小さな値の2種類を加算していたが、ここでは、1種類の値のみを加算する。

0059

ステップS504の第2の加算処理では、変換行列の2〜4行目の演算結果に対してオフセットを加算する。該オフセットを加算する目的は、前記逆数を乗算する対象である被乗数を0より大きな値へレベルシフトするためである。よって、ステップS503の処理結果で想定される最も小さな値(負の値)を0より大きな値へレベルシフトするに足りる値を加算する。この値は式1の変換行列におけるマイナス要素に入力の最大値を乗算して合算した値から計算できる(処理対象データを0以上と仮定する)。1行目の演算結果にオフセットを加算しないのは、加算演算かなく演算結果がマイナスになる要因がないからである。

0060

変換行列の4行目に着目すると、−aの要素が2つあるので、a=3、入力の最大値を255とした場合、3×255×2=1530となる。また、オフセットは、後述する理由から除数(1+a*a)の整数倍(p倍)である必要がある。a=3の場合、除数は10になるので、前記計算結果である“1530”は条件を満たしているので、これをオフセットとして加算する。この場合には、p=153となる。

0061

前記式1の変換行列では、aの二乗の項が全部プラスになっているが、負号反転など操作で、aの二乗の項がマイナスになっている変換行列を用いる場合、オフセットの値を大きくしなければならない。

0062

ステップS505の乗算処理は、固定小数点の逆数r0、r1を乗算し、ビットシフト処理を行なうことによって、先のステップS305の除算処理の替わりを行なう。

0063

最後に、ステップS506の減算処理でp(=153)を減算する。この処理はステップS504で加算したオフセットを取り除くための処理である。ここで完全にオフセットを取り除くために、オフセットは除数の整数倍(p倍)である必要があったわけである。

0064

上記説明では、変換行列の2〜4行目の演算すべてにおいて、同一のオフセットを加算しているが、2行目と3行目は、上述の値“1530”よりも小さなオフセットでもよいことが分かる。具体的には、(1+3)×255=1020 という値でもよい。

0065

このように、加算するオフセットを必要最小の値にした場合、オフセット加算後の各行の演算結果の最大値は(1+3+3+9)×255+5=4085 となる。共通のオフセットを用いると最大値は1530と1020との差分“510”だけ大きくなる。よって、最大値は“4595”となる。

0066

この値に対して、切り捨てした逆数r0や切り上げした逆数r1を乗算した時に発生する誤差が、各々絶対値で1/10未満になるように逆数の精度を確保する必要がある。これは、1/10単位の演算結果が区別できるようにするためである。これに基づいて逆数の範囲を限定すると、以下のようになる。

0067

よって、逆数の誤差は絶対値で1/45960以下である必要がある。この誤差は、15.5ビットの演算精度に相当するので、それより精度のよい16ビット精度の逆数にする。ここでやっと、n=16という値がでてくる。

0068

次に、以上に説明した各種パラメータを用いて、実際の演算結果について検討する。

0069

まず、1/10を16ビットで切り捨て近似した逆数r0は216÷10=6553になり、切り上げ近似した逆数r1は6554になる(固定小数点表示なので実際の1の重みは1/65536である)。これらのパラメータから各処理の結果がどのようになるかを以下に示す。
元のデータ : 247, 252, 9, 5
積和演算後 : 1075, 555, 2985, 1445
第1加算処理後 : 1080, 560, 2990, 1450
第2加算処理後 : 1080, 2090, 4520, 2980
逆数乗算シフト後: 108, 208, 452, 298
オフセット減算後: 108, 55 299, 145

0070

上記オフセット減算後の値が第2実施形態のロスレス変換処理結果である。この変換結果は、図6に示す逆変換処理によって元のデータに復元される。図6の逆変換処理は、第1実施形態と同様、基本的に順変換処理と同じであるが、次の点が異なる。

0071

前述の説明で、元のデータを0〜255としているので、逆変換後の値も同じ0〜255の範囲となる。途中の演算結果にマイナスの値があっても、最終的には除数の半分の値hを加算することで0以上になる。よって、逆変換処理ではオフセットの加算処理(ステップS504)とそれを打ち消す減算処理(ステップS506)が不要となる。また、順変換処理における逆数r0、r1の乗算箇所に対応して逆変換処理における逆数r0、r1の乗算箇所を変える。この逆数r0、r1の乗算箇所を変えた処理がステップS605である(図示の記号“>>”は下位方向へのビットシフトを示している)。

0072

もし、元のデータの範囲を負の値まで広げると、逆変換処理にも上記オフセットの加算処理(ステップS504)とそれを打ち消す減算処理(ステップS506)が必要となり、図5とほとんど同じ処理となる。違いは、ステップS605のみとなる。

0073

上記、ロスレス変換処理結果を逆変換処理した時の各ステップの処理結果を以下に示す。
変換結果 : 108, 55 299, 145
積和演算後 : 2475, 2525, 85, 55
第1加算処理後 : 2480, 2530, 90, 60
逆数乗算シフト後: 247, 252, 9, 5

0074

上記の如く、逆変換処理後のデータは元のデータに一致していることが分かる。ステップS605における逆数r0、r1の用い方は何種類もあるのは、前記第1実施形態と同様である。

0075

本第2の実施形態も先の第1実施形態で示した図14と同様、各演算処理を実行する演算器を用意して、図5図6の処理フローに従って、各演算器にデータを流せば、ロスレスデータ変換処理装置を構成できるのは、これまでの説明からすれば容易に理解できよう。

0076

<第3の実施形態>
本第3の実施形態では、aの値が偶数(2n)の場合に、どのようにしてロスレス変換を実現するのかについて述べる。但しa=2(n=1)の場合は四捨五入(と等価な)処理のみで何の問題もなくロスレス変換を実現できるので、以下ではnの値が2以上の場合について考える。

0077

aが偶数の場合、除数(1+a*a)は奇数となるので除算処理の結果、小数点以下の値が0.5になることは無い。よって、aが奇数の時のような問題は発生しない。しかし、別の新たな問題が発生する。すなわち、四捨五入と同様の処理のみでは、ロスレス変換とはならず、aが奇数の時のような手法も用いることが出来ない。

0078

a=2n(n≧2)の場合、順変換時の四捨五入処理で発生した丸め誤差が大きいと、逆変換時の四捨五入処理で前記丸め誤差を打ち消すことが出来ず、その結果ロスレス変換にはならなくなってしまう。

0079

これを解決するため、逆変換時の四捨五入処理で順変換の丸め誤差を打ち消すことが出来ないような大きな丸め誤差に対して、四捨五入とは逆の丸め処理を行なう。具体的には、四捨五入では切り捨てられていた小数点以下の値を切り上げ、四捨五入で切り上げられていた小数点以下の値を切り捨てるといった処理を行なう。以下ではこの処理を、通常の四捨五入の丸め処理と区別するため、“逆四捨五入丸め処理”と称す。

0080

逆四捨五入丸め処理の対象となる丸め誤差の範囲は、該丸め誤差の絶対値を除数(1+a*a)倍した値をTとすると、2n*n−n+1≦T≦2n*n−1 となる。

0081

概念的には上述した処理内容であるが、丸め誤差を求めるために、一度、四捨五入処理をして、上記逆四捨五入丸め処理の対象となる丸め誤差かどうか判定して、再度丸め処理を行なうのは効率が悪いので、それと等価な処理として、丸め誤差の負号を反転する方向へ、変換結果に1を加減算する処理を行なうのが現実的である。

0082

具体的に、丸め誤差が−(2n*n−1)の時、これは切り捨て処理されて発生した丸め誤差であることが分かる。この絶対値は逆四捨五入丸め処理の対象内の値であるため、切り捨てとは反対の切り上げ処理を行なうことになる。

0083

切り捨てから切り上げへ変更すると変換結果は1だけ増加するので、結局、丸め誤差が負でその絶対値が逆四捨五入丸め処理の対象内の値であるときは、変換結果を+1すればよい。同様に、丸め誤差が正(プラス)でその値が逆四捨五入丸め処理の対象内の値であるときは、変換結果を−1すればよいことがわかる。

0084

ここで、逆四捨五入丸め処理の対象となる変換結果は必ず2つ同時に現われることについて説明する。

0085

前記式1の変換処理に四捨五入丸め処理を適用すると、1番目と4番目の変換結果が有する丸め誤差は必ず正負反転する。これは、4番目の変換式を以下のように変形すると明らかである。

…(2)

0086

小数点以下の値を発生する最後の項が1番目の変換式とは正負反転していることが分かる。同様に、2番目と3番目の変換結果が有する丸め誤差は必ず同じになる。これは、3番目の変換式を以下のように変形すると明らかである。

…(3)
小数点以下の値を発生する最後の項が2番目の変換式と同じになっていることが分かる。

0087

このように、丸め誤差の絶対値が同じものが必ず2つ現われる。即ち、前記逆四捨五入丸め処理の対象となる変換結果は2つ同時に出てくるが、ロスレス変換となるようにするには、2つの内のどちらか一方だけを逆四捨五入丸め処理する。

0088

上述した処理をフローチャートで示したのが図7及び図8である。

0089

同図において、各ステップS701乃至S717は次の処理である。
S701は、同じ計算の繰り返しを減らすためのパラメータ計算処理
S703は、4入力ベクトル整数変換行列の積を計算する積和演算処理
S705は、次の除算処理で四捨五入となるように除数の1/2を加える加算処理、
S707は、値が小さくなる方へ切り捨て除算し変換結果を求める除算処理、
S709は、丸め誤差の除数(1+a*a)倍の値を求める処理
S711は、1番目の変換結果の丸め誤差の絶対値の大きさを判定する処理、
S713は、1番目の変換結果の丸め誤差の負号を判定する処理、
S715は、1番目の変換結果から1を減算する処理、
S717は、1番目の変換結果に1を加算する処理、
S721は、2番目の変換結果の丸め誤差の絶対値の大きさを判定する処理、
S723は、2番目の変換結果の丸め誤差の負号を判定する処理、
S725は、2番目の変換結果から1を減算する処理、
S727は、2番目の変換結果に1を加算する処理。

0090

本実施形態の特徴的な処理は、ステップS709以降の処理であるので、以下では、ステップS709以降の処理について説明する。

0091

ステップS709において丸め誤差を(1+a*a)倍した値を求めるのは、該丸め誤差を整数値として正確な値を得るためである。逆に言うと正確な値が得られるのであれば、必ずしも(1+a*a)倍した値である必要はない。

0092

ここで計算された(1+a*a)倍された2つの丸め誤差E0,E1は、ステップS711、S721にて逆四捨五入丸め処理の対象となる範囲のものであるかどうかを各々判定する。

0093

丸め誤差E0が逆四捨五入丸め処理の対象となると判定されたら、ステップS713にてE0の正負の符号を判定する。丸め誤差E0が正であれば、先のステップS707で求めた変換結果Y0から1を減算し(ステップS715)、E0が負であればY0に1を加算する(ステップS717)。

0094

E0が逆四捨五入丸め処理の対象とならず、E1が逆四捨五入丸め処理の対象となると判定されたら、同様に、ステップS723にてE1の正負の符号を判定して、E1が正であれば先のステップS707で求めた変換結果Y1から1を減算し(ステップS725)、E1が負であればY1に1を加算する(ステップS727)。

0095

以上の処理でロスレス変換した結果が得られる。具体的にa=8(n=4)の計算例を以下に示す。4つの入力データX0,X1,X2,X3が次のような値の時、四捨五入による変換結果と(1+a*a)倍した丸め誤差は以下のようになる。

0096

参考に該変換結果を単純な四捨五入で丸めて逆変換した時の結果も示す。入力データの値と僅かに違っていることが分かる。
入力データ: 5, 33, 43, 0
変換結果 : 9, 42, 32, −4
丸め誤差: −28, −29, −29, 28
逆変換結果: 5, 32, 42, 0 (参考)

0097

先に説明したように、1番目と4番目の丸め誤差は正負反転しており、2番目と3番目の丸め誤差が同じであることが確認できる。2番目の丸め誤差−29は該絶対値が、31〜29(2n*n−1〜2n*n−n+1)の範囲に入っており、負号がマイナスなので、2番目の変換結果に1を加算する。よって、以下のようなロスレス変換結果を得る。
ロスレス変換結果: 9, 43, 32, −4

0098

上記ロスレス変換結果を逆変換して元のデータを復元するための処理は前記図7図8とまったく同じでる。ステップS707における逆変換結果、該変換結果の丸め誤差、2番目の変換結果に1を加算した逆変換結果を以下に示す。
逆変換結果(S707): 5, 32, 43, 0
丸め誤差 : −28,−29, −29, 28
逆変換結果(±1後) : 5, 33, 43, 0

0099

本実施形態では、1番目の変換結果もしくは2番目の変換結果に逆四捨五入丸め処理をする場合について説明したが、順変換処理と逆変換処理が同じであれば、逆四捨五入丸め処理を行なう対象は1,4番目のどちらか1つと、2,3番目のどちらか1つの組み合せであれば何でもよい。

0100

順変換処理と逆変換処理が同じという条件も、変換式が前記(1)式の場合に言えることであって、変換行列の行の置換操作などを行なうと順変換処理と逆変換処理が同じというわけにはいかなくなる。しかし、変換行列がきちんと定義され、順変換処理が定まれば、ロスレス変換を実現するための逆変換処理も一意に決まる。このような変換行列の置換操作などによる処理の変形は本発明の範疇に属する。

0101

また、丸め誤差の比較方法には、様々なバリエーションが考えられる。本実施形態では、正確な記述ができる整数演算で処理するため、丸め誤差を除数倍したものを比較処理したが、実際の丸め誤差は小数点以下の値になるので、それを浮動小数点データまたは固定小数点データとして扱い、そのデータタイプで比較する方法も考えられる。さらに、丸め誤差の絶対値での比較結果と丸め誤差の負号の判定結果に基づく分岐は、丸め誤差が負の値に対応する比較処理と正の値に対応する比較処理を行ない、該比較結果に基づいて分岐するようにも変形出来る。

0102

本実施形態は、データ変換処理方法として説明してあるが、各演算処理を実行する演算器を用意して、図7図8の処理フローの順に従って、各演算器を接続しデータを処理し、判定処理比較器で行ない、該比較結果に応じて演算結果をセレクタで切り替えれば、ロスレスデータ変換処理装置を構成できる。これは当業者であれば容易に考えられる構成である。

0103

<第4の実施形態>
上記第3の実施形態では、丸め誤差を求めてその絶対値が逆四捨五入丸め処理の対象範囲かどうかを判定していたが、本第4の実施形態では、前記積和演算処理の結果を除数で割った余り、即ち、除数を法とする剰余を求めて、該剰余から逆四捨五入丸め処理を適用するかどうか判定するものである。

0104

基本的な考え方は上記第3の実施形態と同じであり、本実施形態は別の処理方法を示すものである。図9に本実施形態のフローチャートを示すが、上記第3の実施形態のS701〜S707、即ち、図7の部分はまったく同じ処理を行なうので、以下では図8に置き換わる処理を図9に示す。同図における各ステップSは次の通りである。
S801は、積和演算処理結果に対して除数(1+a*a)を法とする剰余を求める処理、
S811〜S814は、該剰余が逆四捨五入丸め処理に該当するかどうか判定する処理、
S821〜S824は、上記判定結果に対応する逆四捨五入丸めを行なう処理。

0105

以下で述べる丸め誤差とは、除数(1+a*a)倍した丸め誤差を言う。

0106

切り捨て処理をした場合、剰余は負の丸め誤差となる。よって負の丸め誤差は剰余の負号を反転したものである。一方、正の丸め誤差は除数から剰余を引いたものである。

0107

よって、正の丸め誤差(2n*n−1〜2n*n−n+1)を剰余に換算すると、2n*n+n〜2n*n+2 という範囲になる。この換算した値はステップS812,S814の判定処理で用いる。

0108

以下では、図9の各処理について説明する。ステップS801では、図7の処理結果を受け取り、1番目、2番目の積和演算結果を除数(1+a*a)で、値が小さくなる方向へ切り捨てて除算した結果(別の言い方をすれば、積和演算結果を除数で割ったfloor関数値)をC0,C1に求め、それを用いて各々の剰余R0,R1を求めている。この計算結果では、被除数が負の場合でも剰余は0以上除数未満の範囲に入る。

0109

ステップS811では、負の丸め誤差と仮定した時の前記逆四捨五入丸め処理が必要となる剰余の範囲にR0が入っているかどうか判定し、該範囲内であればステップS821へ行き、切り上げ除算結果を得るため、C0に1を加算した値でY0を更新する。

0110

ステップS812では、正の丸め誤差と仮定した時の前記逆四捨五入丸め処理が必要となる剰余の範囲にR0が入っているかどうか判定し、該範囲内であればステップS822へ行き、切り捨て除算結果を得るため、Y0をC0に更新する。

0111

この2つの判定に引っかからない場合、ステップS707で計算された結果がそのままY0の値となる。この値は四捨五入で丸められた値である。

0112

上記ステップS811,S812とまったく同様に、剰余R1に対する判定をステップS813,S814にて行ない、判定結果に対応してY1の更新をS823,S824にて行なう。

0113

以上が、本第4の実施形態の処理内容である。得られる結果は上記第3の実施形態と同じであるため、具体的な数値例は省略する。

0114

<第5の実施形態>
本第5の実施形態では、ロスレス4点変換を2次元8×8のロスレスDCT変換に適用すると共に、符号化処理への応用例を説明する。

0115

8点DCT変換は、アダマール変換といくつかの2点回転変換とに分解されることが知られており、該2点回転変換の中に、π/16,3π/16という回転変換がある。そして、この回転変換はDCT変換処理の最後の処理に位置する。

0116

2次元DCT変換ではアダマール変換と2点回転変換を2方向から行なう必要がある。すなわち、各列データに対する水平方向の変換と、各行データに対する垂直方向の変換である。2次元変換を行列演算で考えると、8×8のデータ行列に対する水平方向の変換はデータ行列の右側から乗算する変換行列で実現され、垂直方向の変換はデータ行列の左側から乗算する変換行列で実現される。

0117

先に述べたようにDCT変換処理は、アダマール変換や2点回転変換に分解されるので、それらに対応する複数の変換行列をデータ行列の左右から乗算することで2次元DCT変換を実現できる。これら左右から乗算する行列の演算順序は、真中のデータ行列に近い内側から演算すればどのような順序で左右の行列を演算してもよいことは、線形代数における基本的な性質である。よって、前述のπ/16,3π/16回転以外の処理をすべて済ませ、最後に2方向からの上記回転変換を行なうことが可能である。

0118

1方向からのπ/16,3π/16という回転処理をシグナルフローグラフで表わしたのが図10であり、このシグナルフローグラフでπ/16回転処理されるデータのみを8×8データの中に示したのが図11(a)である。一列中の2つのデータに対して行なう2点回転処理を全8列に適用するため、図11(a)における斜線部のデータが回転処理されることになる。そして、2方向からの回転変換によって処理されるデータは図11(b)における斜線部のデータとなる。

0119

同様に、2方向からの3π/16回転変換によって処理されるデータを表わしたのが図12の斜線部である。

0120

図11(b)、図12の各々において、2方向からの回転変換が両方行なわれる4つのデータが存在する。該4つのデータに対する変換は、各々4点直交変換になっている。該4つのデータをX00,X01,X10,X11とすると、該データに対する2方向からの回転処理は式4のように演算できる。

…(4)
式(4)において、α=cos(π/16),β=sin(π/16)、または、α=cos(3π/16),β=sin(3π/16)である。

0121

式4の2次元変換を1次元変換に書き換えると次のようになる。

…(5)
さらに、変換行列を上下反転すると次のようになる。

…(6)
ここで、 α=m/√(m2+n2)、β=n/√(m2+n2)とおくと、

…(7)
上記式(7)は式(1)において、a=n/mと置き、行列の前から掛かる分数分母行列内の各要素を各々mの二乗倍することによって得られるので、式1の変換と等価であることがわかる。

0122

ロスレス変換は整数化するための丸め処理が必須であるため、通常の線形変換に対して丸め処理による変換誤差が必ず生じる。ということは、ロスレス変換処理の際に多少の近似計算をしても、その近似による誤差が前記丸め処理による誤差と同程度かそれより小さければ許容される。

0123

そこで、π/16回転をtan-1(1/5),3π/16回転をtan-1(2/3)で近似する。この近似による回転角の誤差は、0.533%,−0.178%である。一方、255レベル値に対する±0.5の丸め誤差の割合は、0.196%であり、レベル値が小さい時にはこの割合がレベル値に反比例して増大する。そのような状況から考えると、3π/16回転をtan-1(2/3)で近似するのはまったく問題がなく、π/16回転をtan-1(1/5)で近似するのは、従来方式で丸め処理を何回も行なうことを考慮するとほとんど問題がないと言える。

0124

π/16回転をtan-1(1/5)で近似した時の4点直交変換行列は、前記式(7)においてm=5,n=1と置いた行列となり、式(8)に示す変換になる。これは先に説明した第1の実施形態において、a=5と置いた時の変換と同じであるため、第1の実施形態で示した処理方法でロスレス変換が実現できる。

…(8)

0125

一方、3π/16回転をtan-1(2/3)で近似した時の4点直交変換行列は、前記式(7)においてm=3,n=2と置いた行列となり、次式(9)のようになる。

…(9)
この場合は、変換時も逆変換時も普通に四捨五入すれば、ロスレス変換が実現できる。具体的には、非除数に6を加算して、13で除算する時に値が小さくなる方向へ切り捨て処理をすればよい。(7)式の変換において、mとnが整数で、その差が1の時は除算時に普通に四捨五入するだけで、整数ベクトルから整数ベクトルへのロスレス変換が実現できる。

0126

以上で述べたように、2次元8×8のロスレスDCT変換における処理の一部に、本発明のロスレス4点直交変換が適用できることが理解できよう。

0127

なお、本願発明者は、2次元8×8ロスレスDCT変換に最適な2次元4×4ロスレスアダマール変換を既に提案している(特開2004-038451)である。このアダマール変換と本実施形態のロスレス4点直交変換を利用し、他の回転変換には従来方式のロスレス2点回転変換を適用することにより、従来方式より丸め誤差が小さい2次元8×8ロスレスDCT変換を実現できる。

0128

上記の8×8ロスレス2次元DCT変換を画像データに対して行ない、得られた変換係数を、図13に示すように、量子化処理、ハフマン符号化処理を行なうと、JPEG符号化データを得ることができる。

0129

量子化ステップが全て“1”の時にはロスレスDCT変換係数がそのままエントロピー符号化されるため、ロスレス符号化を行なうことができる。すなわち、復号処理時に、ロスレスDCT変換に対応する不図示のロスレス逆DCT変換を行なえば、完全に元のデータを復元できる。

0130

また、ロスレス逆DCT変換処理機能がない、一般のJPEGデコーダ復号処理をした場合、完全な元のデータを復元することはできず、前述のロスレス変換処理で発生した丸め誤差が重畳するデータが復元される。しかし、見た目にはこの違いは区別できず、符号化された元の画像を見るだけならほとんど問題はない。

0131

符号化処理時の量子化ステップを“1”に設定すれば可逆符号化を、“1”より大きく設定すれば劣化のある非可逆符号化を行なうことができ、可逆から非可逆まで連続的に圧縮・伸張画質を制御できることになる。

図面の簡単な説明

0132

従来からあるロスレス2点直交回転変換処理部の構成を示す図
従来のロスレス4点直交変換処理部の構成を示す図
第1実施形態のロスレス変換処理のフローを示す図
第1実施形態のロスレス変換処理の逆変換処理のフローを示す図
第2実施形態のロスレス変換処理のフローを示す図
第2実施形態のロスレス変換処理の逆変換処理のフローを示す図
第3実施形態のロスレス変換の処理フローを示す図
第3実施形態のロスレス変換の処理フローを示す図
第4実施形態のロスレス変換の処理フローを示す図
8点DCTにおけるπ/16、3π/16回転処理の位置を示す図
8×8データの中でπ/16回転処理されるデータを示す図
8×8データの中で3π/16回転処理されるデータを示す図
符号化処理の構成を示す図
第1の実施形態におけるロスレス変換を行う回路構成を示す図である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ