(57)【特許請求の範囲】
【請求項１】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられ、入力したデータの符号を反転する符号反転器と、
前記第１のパス上に設けられ、入力したデータの値を２倍に拡大する変換器と、
前記第２乃至第４のパス上に設けられ、前記変換器に供給されるデータを、前記３つの変換対象データそれぞれに加算、もしくは、減算する第１の演算器群と、
前記第１のパス上の、前記変換器よりも前記第１の出力端子側に設けられ、前記第１の演算器群による３つの演算結果それぞれを前記変換器の変換結果に対して減算、もしくは加算する第２の演算器群と、
前記第１のパス上の、前記第２の演算器群よりも前記第１の出力端子側に設けられ、前記第２の演算器群の出力を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化し、第１の出力端子に向けて出力する丸め処理器と、
前記第２乃至第４のパス上に設けられ、前記丸め処理器と前記第１の出力端子の間のデータを、前記第１の演算器群で得られた３つのデータそれぞれに減算、もしくは加算し、前記第２乃至第４の出力端子に出力する第３の演算器群とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置。
【請求項２】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられ、入力したデータの符号を反転する符号反転器と、
前記第２乃至第４のパス上に設けられ、前記第１のパス上のデータを、前記３つの変換対象データそれぞれに減算、もしくは加算する第１の演算器群と、
該第１の演算器群で演算された３つの演算結果を加算し、当該加算結果を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化し、当該整数化したデータを前記第１のパス上のデータに加算し、当該加算結果を前記第１のパス上の前記第１の出力端子に向けて出力する第２の演算器群と、
前記第２乃至第４のパス上に設けられ、前記第２の演算器群で得られたデータを、前記第１の演算器群で得られた３つのデータそれぞれに減算、もしくは加算し、前記第２乃至第４の出力端子に出力する第３の演算器群とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置。
【請求項３】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられ、入力したデータの符号を反転する符号反転器と、
前記第１のパス上に設けられ、前記第２乃至第４のパス上の３つの変換対象データを、前記第１のパスのデータに減算もしくは加算する第１の演算器群と、
前記第１のパス上に設けられ、前記第１の演算器群により得られたデータの値を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化する丸め処理器と、
当該丸め処理器による丸め処理した結果を２倍に拡大する変換器と、
前記第２乃至第４のパス上に設けられ、前記丸め処理器から出力されたデータを、前記３つの変換対象データそれぞれに加算、もしくは、減算し、前記第２乃至第４の出力端子に向けて出力する第２の演算器群と、
前記第１のパス上に設けられ、前記変換器から出力されたデータに、前記第２の演算器群による３つの演算結果を減算、もしくは加算し、前記第１の出力端子に向けて出力する第３の演算器群と、
前記第１のパス上に設けられ、前記第１の演算器群により得られたデータの最下位ビットを抽出し、前記第３の演算器群により得られたデータに加算もしくは減算する演算器とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置。
【請求項４】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられ、入力したデータの符号を反転する符号反転器と、
前記第１のパス上に設けられ、前記第２乃至第４のパス上の３つの変換対象データを、前記第１のパスのデータに減算もしくは加算する第１の演算器群と、
前記第１のパス上に設けられ、前記第１の演算器群により得られたデータの最下位ビットを２倍にした結果を、当該第１の演算器群により得られたデータから減じ、前記第１のパス上に出力する減算器と、
前記第１の演算器群で演算されたデータの値を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化する丸め処理器と、
前記第２乃至第４のパス上に設けられ、前記丸め処理器から出力されたデータを、前記３つの変換対象データそれぞれに加算、もしくは、減算し、前記第２乃至第４の出力端子に向けて出力する第２の演算器群と、
前記第１のパス上に設けられ、前記減算器から出力されたデータに、前記第２の演算器群による３つの演算結果を減算、もしくは加算し、前記第１の出力端子に向けて出力する第３の演算器群とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置。
【請求項５】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第２のパス上に設けられ、入力したデータの符号を反転する符号反転器と、
前記第１、第３、第４のパス上に設けられ、前記第２のパス上のデータを前記第１のパス上の変換対象データに加算、もしくは減算し、第１のパス上に出力すると共に、前記第２のパス上のデータを前記第３、第４のパス上の変換対象データに減算、もしくは加算し、前記第３、第４のパス上に出力する第１の演算器群と、
前記第２のパス上に設けられ、入力したデータの値を２倍に拡大する処理器と、
前記第２のパス上に設けられ、前記処理器による処理結果に、前記第１の演算器群で演算された３つの演算結果を、減算、若しくは加算し、前記第２のパス上に出力する第２の演算器群と、
前記第２のパス上に設けられ、前記第２の演算器群から出力されたデータの値を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化し、当該整数化した結果を、ＡＣ変換係数データを出力する出力端子に向けて出力する丸め処理器と、
前記第１、第３、第４のパス上に設けられ、前記丸め処理器からのデータを前記第１の演算器群で演算された３つのデータに加算、もしくは減算し、第１、第３、第４のパス上に出力する第３の演算器群とを備え、
前記第１のパスの出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置。
【請求項６】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置の制御方法であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられた符号反転器が、入力したデータの符号を反転する符号反転工程と、
前記第１のパス上に設けられた変換器が、入力したデータの値を２倍に拡大する変換工程と、
前記第２乃至第４のパス上に設けられた第１の演算器群が、前記変換器に供給されるデータを、前記３つの変換対象データそれぞれに加算、もしくは、減算する第１の演算工程と、
前記第１のパス上の、前記変換器よりも前記第１の出力端子側に設けられた第２の演算器群が、前記第１の演算器群による３つの演算結果それぞれを前記変換器の変換結果に対して減算、もしくは加算する第２の演算工程と、
前記第１のパス上の、前記第２の演算器群よりも前記第１の出力端子側に設けられた丸め処理器が、前記第２の演算器群の出力を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化し、第１の出力端子に向けて出力する丸め処理工程と、
前記第２乃至第４のパス上に設けられた第２の演算器群が、前記丸め処理器と前記第１の出力端子の間のデータを、前記第１の演算器群で得られた３つのデータそれぞれに減算、もしくは加算し、前記第２乃至第４の出力端子に出力する第３の演算工程とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置の制御方法。
【請求項７】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置の制御方法であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられた符号反転器が、入力したデータの符号を反転する符号反転工程と、
前記第２乃至第４のパス上に設けられた第１の演算器群が、前記第１のパス上のデータを、前記３つの変換対象データそれぞれに減算、もしくは加算する第１の演算工程と、
第２の演算器群が、該第１の演算器群で演算された３つの演算結果を加算し、当該加算結果を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化し、当該整数化したデータを前記第１のパス上のデータに加算し、当該加算結果を前記第１のパス上の前記第１の出力端子に向けて出力する第２の演算工程と、
前記第２乃至第４のパス上に設けられた第３の演算器群が、前記第２の演算器群で得られたデータを、前記第１の演算器群で得られた３つのデータそれぞれに減算、もしくは加算し、前記第２乃至第４の出力端子に出力する第３の演算工程とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置の制御方法。
【請求項８】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置の制御方法であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられた符号反転器が、入力したデータの符号を反転する符号反転工程と、
前記第１のパス上に設けられた第１の演算器群が、前記第２乃至第４のパス上の３つの変換対象データを、前記第１のパスのデータに減算もしくは加算する第１の演算工程と、
前記第１のパス上に設けられた変換器が、前記第１の演算器群により得られたデータの値を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化する丸め処理工程と、
変換器が、当該丸め処理器による丸め処理した結果を２倍に拡大する変換工程と、
前記第２乃至第４のパス上に設けられた第２の演算器群が、前記丸め処理器から出力されたデータを、前記３つの変換対象データそれぞれに加算、もしくは、減算し、前記第２乃至第４の出力端子に向けて出力する第２の演算工程と、
前記第１のパス上に設けられた第３の演算器群が、前記変換器から出力されたデータに、前記第２の演算器群による３つの演算結果を減算、もしくは加算し、前記第１の出力端子に向けて出力する第３の演算工程と、
前記第１のパス上に設けられた加減算器が、前記第１の演算工程により得られたデータの最下位ビットを抽出し、前記第３の演算工程により得られたデータに加算もしくは減算する加減算工程とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置の制御方法。
【請求項９】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置の制御方法であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられた符号反転器が、入力したデータの符号を反転する符号反転工程と、
前記第１のパス上に設けられた第１の演算器群が、前記第２乃至第４のパス上の３つの変換対象データを、前記第１のパスのデータに減算もしくは加算する第１の演算工程と、
前記第１のパス上に設けられた減算器が、前記第１の演算器群により得られたデータの最下位ビットを２倍にした結果を、当該第１の演算器群により得られたデータから減じ、前記第１のパス上に出力する減算工程と、
丸め処理器が、前記第１の演算器群で演算されたデータの値を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化する丸め処理工程と、
前記第２乃至第４のパス上に設けられた第２の演算器群が、前記丸め処理器から出力されたデータを、前記３つの変換対象データそれぞれに加算、もしくは、減算し、前記第２乃至第４の出力端子に向けて出力する第２の演算工程と、
前記第１のパス上に設けられた第３の演算器群が、前記減算器から出力されたデータに、前記第２の演算器群による３つの演算結果を減算、もしくは加算し、前記第１の出力端子に向けて出力する第３の演算工程とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置の制御方法。
【請求項１０】
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置の制御方法であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第２のパス上に設けられた符号反転器が、入力したデータの符号を反転する符号反転工程と、
前記第１、第３、第４のパス上に設けられた第１の演算器群が、前記第２のパス上のデータを前記第１のパス上の変換対象データに加算、もしくは減算し、第１のパス上に出力すると共に、前記第２のパス上のデータを前記第３、第４のパス上の変換対象データに減算、もしくは加算し、前記第３、第４のパス上に出力する第１の演算工程と、
前記第２のパス上に設けられた処理器が、入力したデータの値を２倍に拡大する処理工程と、
前記第２のパス上に設けられた第２の演算器群が、前記処理器による処理結果に、前記第１の演算器群で演算された３つの演算結果を、減算、若しくは加算し、前記第２のパス上に出力する第２の演算工程と、
前記第２のパス上に設けられた丸め処理器が、前記第２の演算器群から出力されたデータの値を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化し、当該整数化した結果を、ＡＣ変換係数データを出力する出力端子に向けて出力する丸め処理工程と、
前記第１、第３、第４のパス上に設けられた第３の演算器群が、前記丸め処理器からのデータを前記第１の演算器群で演算された３つのデータに加算、もしくは減算し、第１、第３、第４のパス上に出力する第３の演算工程とを備え、
前記第１のパスの出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とするデータ変換装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、整数データを可逆アダマール変換し、変換結果を出力するデータ変換技術に関するものである。
【背景技術】
【０００２】
画像、特に多値画像は非常に多くの情報を含んでおり、蓄積のためには膨大なメモリを必要とし、伝送には多くの時間を要するという問題がある。このため画像の蓄積、伝送に際しては、画像の持つ冗長性を除く処理、或いは画質の劣化が視覚的に認識し難い程度で画像の内容を変更することによって、そのデータ量を削減する高能率符号化が用いられる。
【０００３】
例えば、静止画像の国際標準符号化方式としてＩＳＯとＩＴＵ−Ｔにより勧告されたＪＥＰＧでは、画像データをブロックごと（８×８画素）に離散コサイン変換（ＤＣＴ）して、ＤＣＴ変換係数を得る。そして、そのＤＣＴ変換係数を各々量子化し、さらにエントロピー符号化するという処理手順を経ることで、画像データを圧縮している。このＤＣＴを利用する圧縮技術として、ＪＰＥＧ以外にも、Ｈ２６１，ＭＰＥＧ−１／２／４等が知られている。
【０００４】
このＤＣＴ変換の一部の処理として、あるいは、画像データを変換する処理としてアダマール変換がある。アダマール変換は変換行列の要素が１又は−１のみから成る直交変換で、加算と減算のみで実現できるもっともシンプルな直交変換である。
【０００５】
２点アダマール変換の変換行列Ｈ2は、以下の数式（１）ように定義される。
【０００６】
【数１】
0004933405.tif 000002
【０００７】
一般的なＮ（＝２n）点アダマール変換行列ＨNは、Ｎ／２点アダマール変換行列ＨN/2と上記２点アダマール変換行列Ｈ2との間のクロネッカー積で再帰的に定義することができる。
【０００８】
【数２】
0004933405.tif 000003
【０００９】
例えば、上記定義から、４点アダマール変換行列は次のようになる。
【００１０】
【数３】
0004933405.tif 000004
【００１１】
この変換行列はナチュラル型と呼ばれるもので、基底ベクトルがシーケンシの順番に並んでいない。基底ベクトルの置換を繰り返して、２行目の基底ベクトルを４行目に移動し、元の３、４行目の基底ベクトルをそれぞれ１つ上の行に移動すると、基底ベクトルの順序がシーケンシ順序の変換行列ＷＨ4となる。
【００１２】
【数４】
0004933405.tif 000005
【００１３】
上記変換行列はウォルシュ型あるいはウォルシュアダマール変換行列と呼ばれている。アダマール変換は可逆な直交変換であることが知られており、上記ナチュラル型、ウォルシュ型のいずれも可逆な変換が可能である上、変換行列が対称行列になっている。
【００１４】
ナチュラル型のアダマール変換行列Ｈ4の基底ベクトルを置換して得られる対称行列は、ウォルシュ型以外にも存在する。対角成分が＋１といった特徴を持つ次に示す変換行列Ｔ4である。
【００１５】
【数５】
0004933405.tif 000006
【００１６】
本発明では、この型のアダマール変換を用いる例を説明する。
【００１７】
先に説明したように、アダマール変換は可逆変換であると一般的に言われている。しかしながら、これはあくまで数学的に可逆であるという意味である。すなわち、変換時および逆変換において演算誤差が発生しないことを前提としており、そのためのデータ形式として固定小数点あるいは浮動小数点で演算を行なう必要がある。また、変換処理後の有効桁数をすべて保持する必要もある。
【００１８】
しかし、変換符号化、特に可逆の変換符号化に用いるアダマール変換では、変換処理後に有効桁数を少しでも減らしたい。具体的には、整数の入力のデータを変換処理して発生する小数点以下のデータは、明らかに入力データより増加した桁数（情報）と捉えることができるので、この小数点以下のデータを無くしたい。ところが、この小数点以下のデータを単純に丸め処理してしまうと可逆性は損なわれてしまう。例えば、
１２３、  ７８、  ８４、  ５６
の４つのデータを（５）式の変換行列でアダマール変換を行なうと、その変換結果は次のようになる。
１７０．５、  ３０．５、  ３６．５、  ８．５
これらを単純に小数点以下を四捨五入して整数化すると
１７１、  ３１、  ３７、  ９
となる。ここで、式（５）で示される変換行列は、転置行列である点に注意されたい。すなわち、上記整数化した結果を、再度、式（５）で変換することは、逆変換することと等価となり、その逆変換結果は、次のようになる。
１２４、  ７８、  ８４、  ５６
この結果を見ると、先頭データの“１２３”が、変換、そして、その逆変換により“１２４”になってしまう。つまり、整数化したデータを出力するアダマール変換は可逆性を保証できないことを意味する。
【００１９】
以下では、整数化したデータを出力するアダマール変換を整数型アダマール変換と呼び、可逆変換が可能な整数型アダマール変換を整数型可逆アダマール変換あるいはロスレスアダマール変換と呼ぶことにする。
【００２０】
ロスレス４点アダマール変換を実現する先行技術は２つに大別できる。１つはＬａｄｄｅｒ  Ｎｅｔｗｏｒｋ（梯子演算）を用いるものである。そして、もう１つは、線形アダマール変換の後に、或る規則の丸め処理を行うものである。前者は非特許文献１に、後者は特許文献１に開示されている。
【非特許文献１】福間慎治、大山公一、岩橋政宏、神林紀、“ロスレスアダマール変換を応用したロスレス８点高速離散コサイン変換”、信学技報、ＩＥ９９−６５、ｐｐ．３７−４４、１９９９年１０月
【特許文献１】特開２００３−２５８６４５号公報
【発明の開示】
【発明が解決しようとする課題】
【００２１】
非特許文献１では、該ロスレス変換を実現するために、４点アダマール変換行列を三角行列に分解して、それを梯子演算に置き換えるといった複雑な手順で実現している。図８がその構成の例である。図示のように、その回路構成は複雑であり、演算の内容も直感的に分かり難い。このため、ソフトウェアやハードウェアに実装する時にミスがあっても発見しにくい上に、演算処理量が少ないというわけでもない。
【００２２】
一方、後者の特許文献１に開示されている方法は、線形アダマール変換した小数点データの変換係数に対し、奇数個のデータの小数点以下を切り上げ処理し、他の奇数個のデータの小数点以下を切り捨て処理するものである。この特許文献１は、丸め処理の仕方を特徴としているのみであって、線形アダマール変換の演算を減らす工夫、丸め処理に要する処理量を減らす工夫などは成されていない。
【００２３】
このように、既存のロスレス４点アダマール変換は、可逆性に重点が置かれていたため、冗長な処理が行われており、変換処理を高速に行うには不向きであった。本発明はまさにかかる点を改善するものである。
【課題を解決するための手段】
【００２４】
かかる課題を解決するため、例えば本発明のデータ変換装置は以下の構成を備える。すなわち、
第１乃至第４の入力端子に入力された、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換し、当該変換結果を第１乃至第４の出力端子から、ロスレスアダマール変換係数として出力するデータ変換装置であって、
前記４つの変換対象データのうちの１つの変換対象データを入力する第１の入力端子と前記ＤＣ変換係数データを出力する第１の出力端子とを結ぶパスを第１のパス、前記１つの変換対象データを除く３つの変換対象データを入力する第２乃至第４の入力端子それぞれと前記３つのＡＣ変換係数データを出力する第２乃至第４の出力端子それぞれとを結ぶパスを第２乃至第４のパスと定義したとき、
前記第１のパス上に設けられ、入力したデータの符号を反転する符号反転器と、
前記第１のパス上に設けられ、入力したデータの値を２倍に拡大する変換器と、
前記第２乃至第４のパス上に設けられ、前記変換器に供給されるデータを、前記３つの変換対象データそれぞれに加算、もしくは、減算する第１の演算器群と、
前記第１のパス上の、前記変換器よりも前記第１の出力端子側に設けられ、前記第１の演算器群による３つの演算結果それぞれを前記変換器の変換結果に対して減算、もしくは加算する第２の演算器群と、
前記第１のパス上の、前記第２の演算器群よりも前記第１の出力端子側に設けられ、前記第２の演算器群の出力を１／２に縮小し、小数点以下を切り上げ若しくは切り捨てることで整数化し、第１の出力端子に向けて出力する丸め処理器と、
前記第２乃至第４のパス上に設けられ、前記丸め処理器と前記第１の出力端子の間のデータを、前記第１の演算器群で得られた３つのデータそれぞれに減算、もしくは加算し、前記第２乃至第４の出力端子に出力する第３の演算器群とを備え、
前記第１の出力端子に供給されたデータをＤＣ変換係数データ、前記第２乃至第４の出力端子に供給された３つのデータをＡＣ変換係数データとして出力することを特徴とする。
【発明の効果】
【００２５】
本発明によれば、ロスレスアダマール変換係数の演算処理において、着目する１つのデータを他の３つのデータへ加減算する処理と、該着目する１つのデータへ他の３つのデータを加減算する加減演算処理を交互に３回行い、加減演算処理の間に着目する１つのデータに対して丸め処理を行うことにより、ロスレス変換係数を得ることができる。
【００２６】
よって、丸め処理の回数を削減でき、中間データの生成・保存といった処理が必要無いため、少ない処理量でロスレスアダマール変換を実現することができる。
【００２７】
さらに、汎用ＣＰＵのＳＩＭＤ命令の制約下において、レジスタ保持データのコピー回数を削減した。これにより、ロスレスアダマール変換処理におけるトータルの処理ステップ数や、ロスレスアダマール変換処理装置における回路規模の削減を図ることができる。
【発明を実施するための最良の形態】
【００２８】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００２９】
［第１の実施形態］
ロスレス４点アダマール変換を行なう場合、整数表現された４つの変換対象データを、周波数空間上の、整数で表わされる１つのＤＣ変換係数データと３つのＡＣ変換係数データに変換する。このとき、重要な点は、４つの変換係数の内の１つを小数点以下を切り捨てることで得るようにした場合、他の３つのは逆に切り上げることで算出することである。また、１つ変換係数を、その小数点以下を切り上げることで得るようにした場合、他の３つのＡＣ変換係数は逆に切り捨てることである。
【００３０】
本発明の第１の実施形態におけるデータ変換装置（ロスレス４点アダマール変換装置）の回路構成を図１に示し、以下のその制御処理内容を説明する。
【００３１】
同図において、１０１〜１０４は整数表現された４つのデータＤ０，Ｄ１，Ｄ２，Ｄ３（変換対象データ）を入力するため端子（第１乃至第４の入力端子）である。
【００３２】
１１１乃至１１３は加算器であって、これら３つの加算器で第１の演算器群１００１を構成する。１２１乃至１２３は減算器であり、これら３つの減算器で第２の演算器群１００２を構成する。１３１乃至１３３は減算器であり、これら３つの減算器で第３の演算器群１００３を構成する。
【００３３】
Ｄ０−Ｙ０を結ぶパスを第１のパスとし、Ｄ１−Ｙ１、Ｄ２−Ｙ２、Ｄ３−Ｙ３を結ぶパスをそれぞれ第２乃至第４のパスとすると、図示の第１の演算器群１００１は第２乃至第４のパス上に設けられ、第２の演算器群１００２は第１のパス上に設けられ、第３の演算器群は第２乃至第４のパス上に設けられることになる。
【００３４】
１０６は入力したデータを１ビット左（上位方向）にシフトするシフタである。つまり、このシフタは入力したデータの値を２倍にする乗算器として機能する。１０７は、減算器１２３からの演算結果を１ビット右（下位方向）にシフトするシフタ（除算器）である。つまり、このシフタ１０７は、１／２に縮小し、小数点以下を切り捨てる丸め処理器として機能する。１０８はシフタ１０７の処理結果であるデータの符号を反転する符号反転器である。
【００３５】
１４１乃至１４４はロスレスアダマール変換した結果をＹ０乃至Ｙ３として出力する出力端子（第１乃至第４の出力端子）である。
【００３６】
以下、図１の構成における演算内容について説明する。
【００３７】
まず、第１の演算器群１００１を構成する３つの加算器１１１〜１１３は、第１の入力端子に入力された入力データＤ０を、第２乃至第４の入力端子に入力された、他の３つの入力データＤ１，Ｄ２，Ｄ３に加算し、その加算結果Ｄ０＋Ｄ１，Ｄ０＋Ｄ２，Ｄ０＋Ｄ３を出力する。
【００３８】
シフタ１０６は、入力データＤ０を１ビット左シフトし、そのシフト結果を出力する。つまり、シフタ１０６は、入力データを２倍に拡大する処理（乗算）を行ない、その処理結果を出力する変換器として機能する。なお、以下、整数データＸを１ビット左シフトした値を、“Ｘ＜＜１”と表し、１ビット右シフトした値を“Ｘ＞＞１”と表わす。従って、シフタ１０６からの出力値は“Ｄ０＜＜１”と表わすことができる。このシフタ１０６による処理は該入力データＤ０を２倍することと同じであるが、後述するシフタ１０７による１ビット右シフト処理と対になる処理であるため、本実施形態では１ビット左シフト処理として表現している。
【００３９】
加算器１１１乃至１１３による３つの加算結果は、第２の演算器群１００２を構成する３つの減算器１２１〜１２３にそれぞれ供給される。この結果、第２の演算器群１００２の最後に位置する減算器１２３から出力されるデータは次の通りになる。
（Ｄ０＜＜１）−（Ｄ０＋Ｄ１）−（Ｄ０＋Ｄ２）−（Ｄ０＋Ｄ３）
＝２×Ｄ０−３・Ｄ０−Ｄ１−Ｄ２−Ｄ３
＝−Ｄ０−Ｄ１−Ｄ２−Ｄ３
【００４０】
上記演算結果は、先に示した式（５）のＤＣ変換係数の“−２倍”の値であることが理解できよう。そこで、上記減算結果を、シフタ１０７にて１ビット右シフト処理した後、符号反転器１０８にて正負の符号を反転する。よって、この符号反転器１０８の出力、すなわち、第１の出力端子１４１から出力されるＤＣ成分データＹ０は以下のようになる。
Ｙ０＝−（（−Ｄ０−Ｄ１−Ｄ２−Ｄ３）＞＞１）
＝（Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３＋１）＞＞１        …（６）
【００４１】
１ビット右シフト処理では、２で割った時に発生する小数点以下のデータが切り捨てによって丸め処理される。この演算では、小数点以下が１ビットしかないので、１ビット右シフト処理によって発生する、絶対値が最大の誤差（以下、最大丸め誤差と称す）は−０．５である。
【００４２】
丸め処理の後に、符号を反転すると、該切り捨てによって発生した誤差の符号も反転し、上記最大丸め誤差は０．５となる。これは、小数点以下を切り上げた時の丸め誤差と同じである。よって、符号反転後のデータに対して丸め処理を行う場合には、小数点以下を切り上げないと同じ結果にならない。
【００４３】
式（６）において、符号反転後のデータを加算し、＋１をした後に１ビット右シフトするのは、上記のように、小数点以下を切り上げる演算にするためである。ここまでの演算によって、小数点以下を切り上げた整数のＤＣ変換係数が得られ、該ＤＣ変換係数はデータＹ０として端子１４１から出力される。
【００４４】
上記のようにして得られたＤＣ変換係数データＹ０は、第３の演算器群１００３を構成する３つの減算器１３１乃至１３３それぞれに出力される。減算器１３１乃至１３３は、３つの加算器１１１乃至１１３それぞれからの出力値から、ＤＣ変換係数Ｙ０を減算し、その結果を第２乃至第４の出力端子に向けて出力する。この減算により、以下の（７）乃至（９）に示すＡＣ変換係数データＹ１乃至Ｙ３が得られる。
Ｙ１＝Ｄ０＋Ｄ１−（（Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３＋１）＞＞１）
＝（Ｄ０＋Ｄ１−Ｄ２−Ｄ３）＞＞１            …（７）
Ｙ２＝Ｄ０＋Ｄ２−（（Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３＋１）＞＞１）
＝（Ｄ０−Ｄ１＋Ｄ２−Ｄ３）＞＞１            …（８）
Ｙ３＝Ｄ０＋Ｄ３−（（Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３＋１）＞＞１）
＝（Ｄ０−Ｄ１−Ｄ２＋Ｄ３）＞＞１            …（９）
【００４５】
小数点以下を切り上げた整数のＤＣ変換係数を減算するため、該ＤＣ変換係数に重畳する最大丸め誤差（０．５）の符号を反転した丸め誤差が、各ＡＣ変換係数データに重畳する。
【００４６】
すなわち、各ＡＣ変換係数データには、−０．５の最大丸め誤差が重畳する。これは、切り捨て丸め処理によって発生する丸め誤差と同じである。
【００４７】
よって、本実施形態の整数ＡＣ変換係数は３つとも、切り捨て処理によって丸める変換式に置き換えられるため、上記（７）乃至（９）に示したように式を変形することができる。
【００４８】
上記式（６）、及び、式（７）乃至（９）の出力結果は、先に示した式（５）に示したアダマール変換行列Ｔ4による、ロスレスアダマール変換結果に対応していることが理解できよう。すなわち、実施形態では、切り捨て処理された変換係数の数が奇数個（１個）で、切り上げ処理された変換係数の数も奇数個（３個）なので、この構成で得られるアダマール変換係数はロスレス変換係数になっている。
【００４９】
なおかつ、ＤＣ変換係数だけが他の変換係数と異なる丸め処理になっているため、同一の丸め処理で逆変換が可能である。これは、図１の構成でロスレスの逆変換が可能であることを意味する。
【００５０】
以上説明したように、本第１の実施形態におけるデータ変換装置は、ロスレス４点アダマール変換装置として機能することになる。
【００５１】
上記ロスレスアダマール変換を、変換符号化における変換処理として汎用マイクロプロセッサ（ＣＰＵ）で行う場合、複数ブロックのデータを並列に処理するための並列演算機能を利用することにより、高速な変換処理が可能である。
【００５２】
これは、６４ビット、１２８ビット長のレジスタを４、もしくは８分割して、８または１６ビットデータを並列に処理するためのＳＩＭＤ（Single Instruction stream Multiple Data stream）型命令というもので、近年のＣＰＵでは普通に組み込まれている。
【００５３】
このＳＩＭＤ型命令は一般的に２オペランド形式であり、ソースレジスタとデスティネーションレジスタ間の演算結果がデスティネーションレジスタに格納される。
【００５４】
その条件の元で、図１の構成のソフト処理ステップ数を評価すると、図９に示すように、１２ステップになる。ある変数から別の変数へ値をコピーする代入文が一切無いため、加減算回数が９回となる。
【００５５】
ちなみに、図８の構成に対応するソフト処理は図１０のようになり、１３ステップを要する上に、変換データを一部置換する必要がある。また、図１０に示される１３ステップに置換は含まれていない。
【００５６】
従来技術では、丸め処理を２つもしくは４つのデータに対して行う必要があった。これに対し、本実施形態での丸め処理は１つで済み、データをコピー回数も０回である。すなわち、図９に示すソフト処理は、丸め処理やコピー処理等の多くの項目において、これまでよりも少ない演算回数でロスレスアダマール変換を実現することが可能であることが理解できよう。
【００５７】
なお、上記第１の実施形態では、シフタ１０７が１ビット右シフトすることで、第２の演算器群１００２の演算結果の小数点以下を切り捨てる１／２処理を行なったが、これに限定されるものではない。例えば、シフタ１０７の代わりに、小数点以下を有効した１／２演算器、及び、この１／２演算器の結果の小数点以下を切り上げる丸め処理部を設けても良い。この場合、１／２演算器は第２演算器群１００２からの演算結果を１／２を演算し、小数点以下を含む値を丸め処理部に出力する。丸め処理部は、１／２演算器からの値に“０．５”を加算した後に小数点以下を切り捨てて整数化し、その結果を符号反転器１０８に出力しても構わない。これは、以下に説明する他の変形例、並びに、他の実施形態でも同様である。
【００５８】
また、上記実施形態をハードウェアにて実現する場合であるが、シフタ１０６は、入力したデータのビット０乃至Ｍ（Ｍは設計に応じて適宜決めればよい）を、出力のビット１乃至Ｍ＋１の信号線に割り当て、出力のビット０から“０”を出力すれば実現できる。また、シフタ１０７は、逆に入力したビット１乃至Ｍ＋１を、出力のビット０乃至Ｍに割り当てれば良い。つまり、シフタ１０６、１０７は、単純に回路の配線で実現できるものであるから、それに要する時間は実際は無視できる。これは、以下に説明する他の変形例や他の実施形態でも、同様なことが言える。
【００５９】
［第１の実施形態の変形例１］
第１の実施形態の構成と等価の構成を図２に示す。図２と図１との違いは、符号反転器１０８の位置を第１の出力端子側に移動した点と、第３の演算器群１００３内の減算器１３１乃至１３３の代わりに、加算器１３１’乃至１３３’を新たな第３の演算器群１００３として用いる点である。
【００６０】
符号反転して減算することと、符号反転しないで加算することは等価である。従って、図２の構成が、図１と等価であることは容易に理解できよう。
【００６１】
［第１の実施形態の変形例２］
図２の構成は、図１における符号反転器１０８を第１の出力端子側へ移動したものであった。それとは逆に、符号反転器１０８を入力側へ移動、すなわち、シフタ１０７の前段へ移動した構成を図３に示す。但し、この図３の構成は図１の構成と等価にはならない。
【００６２】
端子１４１から出力される整数ＤＣ変換係数データＹ０は、１ビット右シフタ１０７の出力であるため、該ＤＣ変換係数の丸め処理は切り捨てになる。その結果、このＤＣ変換係数を減算して生成される３つのＡＣ変換係数データＹ１乃至Ｙ３の丸め処理は切り上げになる。
【００６３】
すなわち、図１では、整数ＤＣ変換係数データＹ０は小数点以下を切り上げ、他の３つのＡＣ変換係数データＹ１乃至Ｙ３は小数点以下を切り捨てしたのに対し、図３では逆の丸め処理の関係になっているので、図１とは等価ではない。しかし、この図３の構成でもロスレス変換が行なえるのは、容易に理解できよう。
【００６４】
［第１の実施形態の変形例３］
上記第２の変形例における符号反転器１０８をさらに入力側へ移動した構成を図４に示す。同図において、４１１〜４１３は減算器、４２１〜４２３は加算器である。その他の構成要素は、前記図１における構成要素と共通する機能を有するものは同一の部番を付し説明を省略する。
【００６５】
該図４の構成が、前記図３の構成と等価であることは、これまでの説明から容易に理解できよう。
【００６６】
［第１の実施形態の変形例４］
図４では、ＤＣ変換係数データＹ０は切り捨て、他の３つのＡＣ変換係数Ｙ１乃至Ｙ３は切り上げるものであった。この図４の構成を多少変形することで、図１と同様に、ＤＣ変換係数データＹ０を得るための丸め処理を切り上げ、他の３つのＡＣ変換係数データＹ１乃至Ｙ３を得るための丸め処理を切り捨てにすることができる。図５はその例である。図５と図４との違いは、図５ではシフタ１０７の前に＋１回路５１０を配置した点である。
【００６７】
＋１回路５１０は、加算器４２３による加算結果に“＋１”を加算し、その結果をシフタ１０７に出力する。シフタ１０７は、この＋１回路５１０からの値を１ビット右シフトするものであるから、端子１４１から出力する整数ＤＣ変換係数データＹ０は、切り上げ丸め処理されたのと等価になる。他の出力端子から出力する整数ＡＣ変換係数データＹ１乃至Ｙ３は、切り捨てによる丸め処理となる。従って、該図５の構成は、先に示した図１及び図２の構成と等価であることがわかる。
【００６８】
［第１の実施形態の変形例５］
図３、図４と等価な別の構成を図６に示す。図４では、データＤ０をシフト処理しているが、図６の構成では、Ｄ０以外のデータ、すなわち、Ｄ０に加算あるいは減算するデータを一まとめにしてからシフト処理を行う。
【００６９】
図示において、６１１は４つの入力データの内、３つのデータＤ１，Ｄ２，Ｄ３を合算する３入力の合算器である。６１３は、合算器６１１の出力を１ビット右シフトするシフタである。６１５は、シフタ６１３の出力を、入力データＤ０に加算する加算器である。その他の構成要素は、図４における同じ部番の構成要素と同一であるので、その説明は省略する。図６の構成において、第２の演算器群１００２を構成しているのは、上述の６１１、６１５である。以下では、図４との比較を行うことによって、図４と図６との等価性を示す。
【００７０】
図４では、入力データＤ０を符号反転し、その後に１ビット左シフトした。そして、入力データＤ０以外の他の３つのデータを該データＤ０に加算した後、該加算結果を１ビット右シフトしている。この処理は、３つの入力データＤ１、Ｄ２、Ｄ３を合算器６１１で合算し、その合算結を１ビット右シフトし、そのシフト結果を入力データＤ０に加算することでも同じ結果になる。
【００７１】
入力データＤ０を、その符号反転して１ビット左シフトした値は偶数になるため、合算データの奇偶性（奇数か偶数のどちらであるかということ）と、合算データを入力データＤ０に加算した値の奇偶性は必ず一致する。
【００７２】
奇偶性が一致する該２つデータは、１ビット右シフト処理で切り捨てられる値は同じであり、丸め誤差も同一になるので、前記加算前後のどちらでシフト処理をしても結果は同じである。
まとめると、図６に示す構成は、図４に以下の２点の変更を加えた構成と解釈できる。
（ｉ）入力データＤ０を符号反転したデータへ加算する３つのデータＤ１乃至Ｄ３を合算器６１１で合算する。そして、１ビット右シフト処理を、この合算データのみに行うように変形する。
（ii）上記（ｉ）の変更により、入力データＤ０を符号反転したデータに対する１ビット左シフト処理と１ビット右シフト処理は相殺されて、まったく意味が無くなるため削除する。
【００７３】
以上より、図６に示す構成は図４に示す構成と等価であることが分かる。
【００７４】
［第１の実施形態の変形例６］
図７は、図６における符号反転器１０８の位置を入力側から出力側へ移動した構成を示している。入力データＤ０のデータパス上にある符号反転器１０８を移動すると、移動前後で、該Ｄ０データパスに対する加算と減算は相互に置き換わり、該データパスから他のデータに対する加算と減算も相互に置き換わる。
【００７５】
具体的に、加算器６１５が減算器７２１に、減算器４１１〜４１３が加算器１１１〜１１３に、減算器１３１〜１３３が加算器２３１〜２３３に置き換わる。
【００７６】
Ｄ０データパスの丸め処理について見てみると、１ビット右シフタ６１３で切り捨てられた値を減算器７２１で減算したデータは、見かけ上、切り上げ処理したデータになる。このデータを符号反転器１０８で符号反転することにより、見かけ上、切り捨て処理したデータになって出力される。一方、ＡＣ変換係数は符号反転前の切り上げデータを加算して生成するので、切り上げ処理したデータとして出力される。
【００７７】
よって、図７の構成における各出力の丸め処理は、図３の構成から得られるＤＣ・ＡＣ変換係数の丸め処理とまったく同じであり、図３に示す構成と等価である。
【００７８】
以上説明した第１の実施形態とその変形例を説明した。上記の７つの構成を総括すると、図１、図２、図５の３つの構成が等価な関係にあり、図３、図４、図６、図７の４つの構成が等価にあることがわかる。
【００７９】
また、符号反転器１０８が最も出力側にある図２と、該符号反転器が最も入力側にある図４を比較すると、３つの演算器群における各々の演算器は、加算器と減算器がすべて相互に入れ替わっていることが分かる。
【００８０】
［第２の実施形態］
本発明の第２の実施形態における構成を図１１に示す。同図において、８１１〜８１３は第１の演算器群１００１を構成する３つの減算器、８２１〜８２３は第２の演算器群１００２を構成する３つの加算器、８３１〜８３３は第３の演算器群１００３を構成する３つの減算器である。図１の第１の演算器群１００１、第３の演算器群１００３は第２乃至第４のパス上に設けられていて、第２の演算器群１００２は第１のパス上に設けられていた。図１１では、この配置関係が逆、すなわち、第１の演算器群１００１、第３の演算器群１００３が第１のパス上に配置され、第２の演算器群１００２が第２乃至第４のパス上に設けられている点に注意されたい。
【００８１】
８４１は第１の演算器群１００１による演算結果の最下位ビット（ＬＳＢ）を加算する加算器である。
【００８２】
その他の構成要素は、図１における構成要素と共通する機能を有するものは同一の部番を付し説明を省略する。
【００８３】
本第２の実施形態では、第２の演算器群１００２で演算処理する前に、第１の演算器群１００１の演算結果をシフタ１０７にて１ビット右シフトする。
【００８４】
シフタ１０７による１ビット右シフトした値は、第１の演算器群１００１による演算結果のＬＳＢを切り捨てて、２で割った値と同じである。言い換えると、２で割って切り捨て処理した結果と同じである。
【００８５】
よって、該１ビットシフトした値を加算して生成する本第２の実施形態の３つのＡＣ変換係数には、切り捨てによる丸め誤差“−０．５”が重畳するため、切り捨て処理したデータと同じである。
【００８６】
第３の演算器群１００３において、該３つのＡＣ変換係数を全て同じデータから減算すると、各々のＡＣ変換係数に重畳した丸め誤差が、該被減算データに集中する。この集中した丸め誤差の最大丸め誤差は“＋１．５”という大きさになる。
【００８７】
１ビット右シフトした後に１ビット左シフトしたデータは、元のデータのＬＳＢを切り捨てた値と同じなので、元のデータが奇数の場合に、前記左シフトしたデータには切り捨て誤差“−１”（最大丸め誤差）が重畳する。
【００８８】
該切り捨て誤差に前記集中丸め誤差を加えると、＋０．５が残るので、該データは、最大丸め誤差が“＋０．５”となる丸め処理、すなわち、切り上げ処理がなされたと解釈することができる。
【００８９】
その後に符号反転処理が加わるため、後述するＬＳＢ加算処理を無視した場合のＤＣ変換係数出力には、最大丸め誤差“−０．５”の丸め誤差が重畳し、見かけ上、切り捨て処理された変換係数データとなる。
【００９０】
よって、ＤＣ変換係数の見かけ上の丸め処理は、ＡＣ変換係数の丸め処理と同じになり、すべての変換係数が切り捨て処理された状態になっているため、該変換係数はロスレス変換には成り得なくなってしまう。
【００９１】
これを避けるには、出力するＤＣ変換係数に重畳する最大丸め誤差が“＋０．５”となるようにして、見かけ上、切り上げ処理したデータに変換する必要がある。
【００９２】
そこで、加算器８４１は、第１の演算器群１００１の演算結果のＬＳＢ（１ビット）を、第３の演算器群１００３の演算結果に加算し、その結果をＤＣ変換係数として出力する。
【００９３】
第１の演算器群１００１の演算結果が偶数の時、１ビット右シフト処理による丸め誤差が発生しないため、出力結果であるロスレス変換係数にも丸め誤差は重畳しない。この場合、ＬＳＢ＝０なので、該ＬＳＢをＤＣ変換係数に加算しても何も影響はない。
【００９４】
一方、第１の演算器群１００１の演算結果が奇数の時、ＬＳＢの値は１となり、変換した係数データには丸め誤差が重畳する。このＬＳＢを利用して、ＤＣ変換係数の丸め誤差が切り上げ処理した時と同じになるようにする。
【００９５】
切り捨て処理した変換係数には−０．５、切り上げ処理した変換係数には＋０．５の丸め誤差が重畳するため、ＤＣ変換係数に重畳する丸め誤差が＋０．５になるように、値が“１”であるＬＳＢを加算器８４１にて、ＤＣ変換係数へ加算するわけである。
【００９６】
以上説明した処理により、ＤＣ変換係数は切り上げ、３つのＡＣ変換係数は切り捨て処理した場合と同じ丸め誤差となり、ロスレス変換係数になる。
【００９７】
［第２の実施形態の変形例１］
上記第２の実施形態の図１１の符号反転器１０８を入力側に移動した構成を図１２に示し、以下、同図を第２の実施形態の変形例１として説明する。
【００９８】
先に説明した第１の実施形態における図２と図４の関係から分かるように、符号反転処理を入力側へ移動することによって、図１１における加算器はすべて減算器へ、減算器はすべて加算器に置き換わる。
【００９９】
よって、第１の演算器群１００１を構成するのは、加算器９１１〜９１３となる。また、第２の演算器群１００２を構成するのは減算器９２１〜９２３となる。そして、第３の演算器群１００３を構成するのは加算器９３１〜９３３となる。その他の構成要素は、図１における構成要素と共通である。
【０１００】
シフタ１０８によって、第１の演算器群１００１の演算結果を１ビット右シフトした値は、２で割って切り捨て処理した結果と同じであり、第２の演算器群１００２を用いて該シフト結果を減算して生成したＡＣ変換係数の見かけ上の丸め処理は、切り捨てとは逆の切り上げとなる。
【０１０１】
図１１に示す構成におけるＡＣ変換係数の見かけ上の丸め処理が切り捨てであったので、図１２に示す構成は図１１に示す構成と等価では無く、丸め処理の関係がまったく逆である。
【０１０２】
本変形例１のＡＣ変換係数出力には最大丸め誤差“＋０．５”の丸め誤差が重畳し、該丸め誤差は、第３の演算器群１００３である加算器９３１〜９３３によって、ＤＣ変換係数へ加算される。
【０１０３】
該ＤＣ変換係数には、シフタ１０８による１ビット右シフト処理と、シフタ１０６による１ビット左シフト処理によって、最大丸め誤差“−１．０”の丸め誤差も重畳しているので、トータルで“＋０．５”の丸め誤差が重畳していることになる。
【０１０４】
このままでは、該ＤＣ変換係数の見かけ上の丸め誤差が切り上げになり、ＡＣ変換係数の丸め処理と同じになってしまうため、第２の実施形態で説明した理由とは正反対の理由で、ＬＳＢをＤＣ変換係数から減算し、ＤＣ変換係数の見かけ上の丸め処理を切り捨て処理に変え、変換係数がロスレス変換係数になるようにする。
【０１０５】
＜第２の実施形態の変形例２＞
第２の実施形態の変形例２の構成を図１３に示す。同図において、８６１は第１の演算器群１００１による演算結果のＬＳＢを２倍にする１ビットのシフタである。８７１はシフタ８６１で２倍にしたＬＳＢ×２の値を、演算途中のデータから減算する減算器である。その他の構成要素は、図１１における同一部番の構成要素と共通である。
【０１０６】
本第２の実施形態の変形例２では、１ビット右シフトした第１の演算器群１００１による演算結果を、左シフトして使用するのでは無く、１ビット右シフト前の演算結果をそのまま用いるのが特徴である。
【０１０７】
減算器８７１は、シフタ８６１によってＬＳＢを２倍にした値を、第１の演算器群１００１の演算結果から減算することにより、最大丸め誤差“−２”の差分が発生する（これも重畳した丸め誤差と解釈して以下の説明を行う）。
【０１０８】
ＡＣ変換係数を減算することにより重畳する誤差“＋１．５”を、前記重畳誤差に加えると、トータルで“−０．５”の重畳誤差となる。該重畳誤差が実際に発生するのはＬＳＢ＝１の時だけである。
【０１０９】
この重畳誤差は、符号反転器１０８にて、“＋０．５”に変わるため、端子１４１から出力するＤＣ変換誤差の見かけ上の丸め処理は切り上げになる。
【０１１０】
ＡＣ変換係数の丸め処理は第２の実施形態（図１１）で説明したように、切り捨てであるため、該ＤＣ，ＡＣ変換係数はロスレス変換係数となる。ちなみに、図１３の構成は図１１の構成と等価である。
【０１１１】
［実施形態２の変形例３］
第２の実施形態の変形例３の構成を図１４に示す。同図は、図１３の構成において、符号反転器１０８を入力側に移動した構成と解釈できるし、図１１の構成から図１３へ置き換えを、図１２に適用したものとも解釈できる。よって、図１４の構成は図１２と等価な構成であることは明らかであり、その説明は不要であろう。
【０１１２】
［第３の実施形態］
本発明の第３の実施形態の構成を図１５に示す。
【０１１３】
これまでに説明してきた第１，第２の実施形態、並びにその変形例は、演算の中心はＤＣ変換係数であった。
【０１１４】
すなわち、第１乃至３の演算器群において、共通に加算あるいは減算するデータは、入力端子１０１から入力したデータＤ０に種々の演算を施して出力端子１４１からＤＣ変換係数データＹ０として出力するものであった。
【０１１５】
本実施形態では、共通に加算あるいは減算するデータを、端子１０２から入力したデータに演算を施し、出力端子１４２からＡＣ変換係数として出力するパス上のデータとする。これが本第３の実施形態の最大の特徴である。
【０１１６】
図１５において、９４１〜９４３は、第１の演算器群１００１を構成する１つの加算器と２つの減算器である。９５１〜９５３は、第２のパス上に設けられた第２の演算器群１００２を構成する１つの減算器と２つの加算器である。９６１〜９６３は、第３の演算器群１００３を構成する１つの加算器と２つの減算器である。その他の構成要素は、図１における構成要素と共通する機能を有するものは同一の部番を付し説明を省略する。
【０１１７】
第１実施形態と同様、本第３の実施形態における演算内容について説明する。
【０１１８】
まず、第１の演算器群１００１を構成する加算器９４１と減算器９４２，９４３により、入力データＤ１を入力データＤ０に加算すると共に、入力データＤ１を入力データＤ２，Ｄ３からそれぞれ減算する。この加算および減算結果として、Ｄ０＋Ｄ１，−Ｄ１＋Ｄ２，−Ｄ１＋Ｄ３が生成される。
【０１１９】
次に入力データＤ１をシフタ１０６により１ビット左シフトする。
【０１２０】
上記３つの演算結果は、第２の演算器群１００２を構成する減算器９５１と加算器９５２、９５３により、前記シフタ１０６の出力に減算もしくは加算する。この演算結果は以下のようになる。
（Ｄ１＜＜１）−（Ｄ０＋Ｄ１）＋（−Ｄ１＋Ｄ２）＋（−Ｄ１＋Ｄ３）
＝２・Ｄ１−Ｄ０−３・Ｄ１＋Ｄ２＋Ｄ３
＝−Ｄ０−Ｄ１＋Ｄ２＋Ｄ３              …（１０）
【０１２１】
上記式（１０）の値は、あるＡＣ変換係数の−２倍の値であることが分かる。そこで、この式（１０）で得られた値を、シフタ１０７にて１ビット右シフト処理した後、符号反転器１０８にて、その符号を反転することによって、ＡＣ変換係数データＹ１を得る。このＡＣ変換係数データＹ１は次のようになる。
Ｙ１＝−（（−Ｄ０−Ｄ１＋Ｄ２＋Ｄ３）＞＞１）
＝（Ｄ０＋Ｄ１−Ｄ２−Ｄ３＋１）＞＞１    …（１１）
【０１２２】
上記式（１１）の演算内の＋１は丸め処理を切り上げ処理にするためのものであり、この演算は第１の実施形態における式（６）と同じである。
【０１２３】
そして、式（１１）における符号反転前のデータ、即ち（−Ｄ０−Ｄ１＋Ｄ２＋Ｄ３）＞＞１を、第３の演算器群１００３を構成する加算器９３１と減算器９３２，９３３によって、第１の演算器群１００１の各々の演算結果に加算、もしくは減算する。この加減算により、以下の式（１２）で示されるＤＣ変換係数データＹ０、及び、式（１３）、（１４）で、残りの２つのＡＣ変換係数データＹ２、Ｙ３が得られる。
Ｙ０＝Ｄ０＋Ｄ１＋（（−Ｄ０−Ｄ１＋Ｄ２＋Ｄ３）＞＞１）
＝（２・Ｄ０＋２・Ｄ１−Ｄ０−Ｄ１＋Ｄ２＋Ｄ３）＞＞１
＝（Ｄ０＋Ｄ１＋Ｄ２＋Ｄ３）＞＞１        …（１２）
Ｙ２＝−Ｄ１＋Ｄ２−（（−Ｄ０−Ｄ１＋Ｄ２＋Ｄ３）＞＞１）
＝−Ｄ１＋Ｄ２＋（（＋Ｄ０＋Ｄ１−Ｄ２−Ｄ３＋１）＞＞１）
＝（−２・Ｄ１＋２・Ｄ２＋Ｄ０＋Ｄ１−Ｄ２−Ｄ３＋１）＞＞１
＝（Ｄ０−Ｄ１＋Ｄ２−Ｄ３＋１）＞＞１    …（１３）
Ｙ３＝−Ｄ１＋Ｄ３−（（−Ｄ０−Ｄ１＋Ｄ２＋Ｄ３）＞＞１）
＝−Ｄ１＋Ｄ３＋（（＋Ｄ０＋Ｄ１−Ｄ２−Ｄ３＋１）＞＞１）
＝（−２・Ｄ１＋２・Ｄ３＋Ｄ０＋Ｄ１−Ｄ２−Ｄ３＋１））＞＞１
＝（Ｄ０−Ｄ１−Ｄ２＋Ｄ３＋１）＞＞１    …（１４）
【０１２４】
式（１３）、（１４）のように、切り捨て処理した変換係数データを減算して生成した変換係数は、見かけ上、切り上げ処理した変換係数データになる。
【０１２５】
それに対し、式（１２）のように、切り捨て処理した変換係数データを加算して生成した変換係数は、見かけ上、切り捨て処理した変換係数データになる。
【０１２６】
４つの変換係数出力において、見かけ上、切り捨て処理したデータが１つ、切り上げ処理したデータが３つになるため、該変換係数はロスレス変換係数となる。
【０１２７】
本第３の実施形態では、共通に加算あるいは減算するデータを、入力端子１０２から入力したデータＤ１に演算を施し、出力端子１４２からＡＣ変換係数データＹ１として出力するパス上のデータとした。
【０１２８】
上記パス上のデータ以外に、入力端子１０３から入力し、出力端子１４３から出力するパス上のデータ、あるいは入力端子１０４から入力し、出力端子１４３から出力するパス上のデータを、前記共通に加算あるいは減算するデータとすることも可能である。理由は、３つのＡＣ変換係数は互いに対等で、ある１つのＡＣ変換係数に対して適用可能な手法は、他の２つのＡＣ変換係数のいずれにも同様に適用できるからである。他の２つのＡＣ変換係数への適用例を、本明細書に記述することは冗長なので省略する。
【０１２９】
＜第３の実施形態の変形例１＞
第３の実施形態の変形例１を図１６に示す。
【０１３０】
図１６の構成は、図１５の構成において、符号反転器１０８を入力側に移動した構成である。図１５と図１６の関係は、ちょうど図２と図４の関係と同じである。よって、図１６における出力変換係数における丸め処理は、図１５の丸め処理とは正反対の関係にあり、切り上げ変換係数が１つ、切り捨て変換係数が３つになるため、ロスレス変換係数になることが理解できよう。
【０１３１】
以上、本発明に係る実施形態とその変形例を説明した。
【０１３２】
先に示した非特許文献１に記載されているように、ロスレスアダマール変換を用いると、効率よくロスレスＤＣＴ変換を行うことができるが、本実施形態によるロスレスアダマール変換を用いれば、さらに効率のよくロスレスＤＣＴ変換を行うことが可能である。
【０１３３】
該ロスレスＤＣＴの変換係数を量子化してエントロピー符号化すれば、ＪＰＥＧと互換性のあるロッシー型の符号化を行うことができ、量子化しないで符号化すれば、文字通りロスレス符号化を行うことが可能である。
【０１３４】
すなわち、量子化処理の有無により、同じ変換処理でロッシー符号化とロスレス符号化をシームレスに切り替えることが可能である。
量子化しないで符号化した場合は、復号時にロスレスの逆変換を行えば、元の画像データを完全に復元することができる。ロスレスの逆変換を行わず、一般のＤＣＴ逆変換処理を施すと、元のデータに近い画像データに復元できる。
【０１３５】
本発明において、入力データは一貫して整数としてきたが、該入力データは固定小数点データでもよいことは、明白である。
【０１３６】
小数点以下ｎビットを有する入力データを本発明に基づいてロスレス変換した場合、ロスレス変換係数も、小数点以下ｎビットを有するデータとなる。
【０１３７】
小数点の位置は、データの解釈の問題であり、入出力データ間で同じように小数点を移動させれば、どこに小数点があっても構わない。
【図面の簡単な説明】
【０１３８】
【図１】第１の実施形態のロスレス４点アダマール変換を行なうデータ変換装置の構成を示す図である。
【図２】第１の実施形態の変形例１のデータ変換装置の構成を示す図である。
【図３】第１の実施形態の変形例２のデータ変換装置の構成を示す図である。
【図４】第１の実施形態の変形例３のデータ変換装置の構成を示す図である。
【図５】第１の実施形態の変形例４のデータ変換装置の構成を示す図である。
【図６】第１の実施形態の変形例５のデータ変換装置の構成を示す図である。
【図７】第１の実施形態の変形例６のデータ変換装置の構成を示す図である。
【図８】従来のロスレス４点アダマール変換装置の構成を示す図である。
【図９】第１の実施形態の変換処理をコンピュータプログラムで実現した際の処理手順を示す図である。
【図１０】従来のロスレス４点アダマール変換方法をコンピュータプログラムで実現した際の処理手順を示す図である。
【図１１】第２の実施形態のロスレス４点アダマール変換を行なうデータ変換装置の構成を示す図である。
【図１２】第２の実施形態の変形例１のデータ変換装置の構成を示す図である。
【図１３】第２の実施形態の変形例２のデータ変換装置の構成を示す図である。
【図１４】第２の実施形態の変形例３のデータ変換装置の構成を示す図である。
【図１５】第３の実施形態のロスレス４点アダマール変換を行なうデータ変換装置の構成を示す図である。
【図１６】第３の実施形態の変形例１のデータ変換装置の構成を示す図である。
【図１】
0004933405.tif 000007
【図２】
0004933405.tif 000008
【図３】
0004933405.tif 000009
【図４】
0004933405.tif 000010
【図５】
0004933405.tif 000011
【図６】
0004933405.tif 000012
【図７】
0004933405.tif 000013
【図８】
0004933405.tif 000014
【図９】
0004933405.tif 000015
【図１０】
0004933405.tif 000016
【図１１】
0004933405.tif 000017
【図１２】
0004933405.tif 000018
【図１３】
0004933405.tif 000019
【図１４】
0004933405.tif 000020
【図１５】
0004933405.tif 000021
【図１６】
0004933405.tif 000022