JP3543151B2

JP3543151B2 - Data compression method and data compression apparatus

Info

Publication number: JP3543151B2
Application number: JP11109393A
Authority: JP
Inventors: 亨渡邉
Original assignee: Casio Computer Co Ltd
Current assignee: Casio Computer Co Ltd
Priority date: 1993-04-13
Filing date: 1993-04-13
Publication date: 2004-07-14
Anticipated expiration: 2019-07-14
Also published as: JPH06303596A

Description

【０００１】
【産業上の利用分野】
本発明は、画像データの圧縮処理等に用いられるデータ圧縮方法及びデータ圧縮装置に係り、詳細には、データ変換演算処理の際の演算精度を向上させることが可能なデータ圧縮方法及びデータ圧縮装置に関する。
【０００２】
【従来の技術】
近時、ディジタル技術の急速な発達に伴い、ディジタル技術によってディジタルデータの伝送、交換、サービスを統合するＩＳＤＮ（サービス総合ディジタル通信網）が実用化され、音声と画像をディジタルデータに変換して送・受信する環境が整いつつある。
【０００３】
このような環境でディジタル化した画像データを送・受信する場合、画像は、そのままディジタル化するとデータ量が膨大になるため、画像をディジタル化する際にデータ量を圧縮する画像圧縮技術に対する要求が高まっている。従来の画像圧縮技術の代表的なものとしては、直交変換符号化が高能率の符号化技術として知られている。この直交変換符号化による符号化方式としては、例えば、変換行列の要素が単純で加減算処理のみで変換可能なアダマール変換方式がある。このアダマール変換方式では、変換行列の要素が“＋１”と“−１”からなり、式（１）に示す基本変換行列を基にして式（２）に示すように高次形へと変換行列が拡張されている。このアダマール変換方式では、ハードウエア構成を簡素化することができる。
【０００４】
【数１】

【０００５】
【数２】

また、画像圧縮技術の国際標準規格としてＪＰＥＧ（Joint Photographic Ex-pert Group）やＭＰＥＧ（Moving Picture Expert Group ）がある。ＪＰＥＧは、静止画像を圧縮することを目的としており、すでにカラー静止画像の符号化手法が決定し、国際標準規格として承認される予定である。ＪＰＥＧについては、チップも製品化されており、このチップを用いたボードも市場に出始めている。ＪＰＥＧアルゴリズムは、大きく２つの圧縮方式に分けられる。第１の方式は、直交変換符号化の一符号化方式であるＤＣＴ（Discrete Cosine Transform ：離散コサイン変換）を基本とした方式であり、第２の方式は二次元空間でＤＰＣＭ（Differntial PCM）を行なうSpatial（空間関数）方式である。ＤＣＴ方式は量子化を含むため一般には完全に元の画像は再現されない非可逆符号化であるが、少ないビット数においても十分な復号画像品質を得ることができ、本アルゴリズムの基本となる方式である。一方、Spatial 方式は、圧縮率は小さいが元の画像を完全に再現する可逆符号化であり、この特性を実現するために標準方式として付加された方式である。
【０００６】
このような従来のＤＣＴ方式を利用して画像データを圧縮するデータ圧縮装置としては、例えば、図６に示すものがある。図６において、２は、データ記憶装置であり、圧縮を施そうとする画像データを１フレーム単位で蓄積する。３は、データ変換演算装置であり、データ記憶装置２から出力される１フレーム単位の画像データに対して上記ＤＣＴ演算等のデータ変換演算処理により特定の周波数成分を抽出した後、再度、データ記憶装置２に書き戻す。このデータ変換演算装置３の処理は、一次元の場合であり、画像データのように二次元の場合は、例えば、図７（ａ）〜（ｃ）に示すように、画像データを８×８画素から成るブロック単位で上述した周波数成分の抽出処理を縦横（順不同）二次元に施す。
【０００７】
４は、量子化装置であり、データ記憶装置２に蓄えられたデータ変換演算後のデータに対して、例えば図８に示すような量子化テーブルの値で除算をする（あるいは、逆数の乗算）ことによって量子化演算を行なう。５は、制御装置であり、上記各装置の動作を制御してデータ圧縮装置１全体を制御する。
【０００８】
また、上記図６に示したデータ変換演算装置３の内部構成としては、例えば、図９に示すブロック図のようなものがある。図９において、６は、係数ＲＯＭであり、乗算器７が画像データに対して乗算する係数データを格納する。乗算器７は、上記データ記憶装置２から入力される画像データに対して係数ＲＯＭ６から読み出した係数を乗算してバレルシフタ８に出力する。バレルシフタ８は、乗算器７から入力される乗算後のデータを必要なビット数だけ残し、右シフト（切り捨て）し、加減算器９に出力する。加減算器９は、バレルシフタ８から入力される値に前回の値との和（差）を求める。
【０００９】
このデータ変換演算装置３では、バレルシフタ８により右シフト（切り捨て）処理が行われると、その出力される結果は、図１０に示すように、全体的により小さい値をとることになる。この図では、１ビット右シフトした場合の出力値の様子を示しており、“○”がその値を含まないことを示し、“●”がその値を含むことを示している。
【００１０】
また、上記図９に示したデータ変換演算装置３と異なるものとして、例えば、図１１に示すデータ変換演算装置３のように、バレルシフタ８の後にインクリメンタ１０を追加して四捨五入処理を行うようにしたもの、あるいは図１２に示すデータ変換演算装置３のように、バレルシフタ８と加減算器９をバス１２で接続し、バレルシフタ８と加減算器９のバス切換え、インクリメンタの動作を加減算器９に行わせることより四捨五入処理を行うようにしたものもある。
【００１１】
【発明が解決しようとする課題】
しかしながら、このような従来のデータ変換演算処理を行うデータ圧縮装置にあっては、上記図９に示したデータ変換演算装置３のようにバレルシフタ８により右シフト（切り捨て）処理を行う場合は、その出力される結果が、上記図１０に示したように、全体的により小さい値をとるため、本来とるべき値との演算誤差が大きくなるという欠点があった。
【００１２】
また、上記図１１に示したデータ変換演算装置３のようにインクリメンタ１０を追加して四捨五入処理を行う場合は、回路規模が大きくなるという問題点があり、上記図１２に示したデータ変換演算装置３のようにバレルシフタ８と加減算器９をバス１２で接続し、バレルシフタ８と加減算器９のバス切換えにより加減算器９が四捨五入処理を行う場合、バス切換えの増加だけですむが、加減算器９で２回演算を行うことにより演算時間が長くなってしまうという問題点があった。
【００１３】
そこで本発明は、データ圧縮方法及びデータ圧縮装置において、回路規模の増大や演算時間を長引かせることなくデータ変換演算処理の演算誤差を改善することを目的とする。
【００１４】
【課題を解決するための手段】
本発明の手段は次の通りである。
【００１５】
請求項１記載の発明は、上記目的達成のため、所定のデータを記憶する第１の工程と、前記第１の工程により出力されたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、一次元目のデータ変換演算を実行する第２の工程と、前記第２の工程により一次元目のデータ変換演算が行われたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、二次元目のデータ変換演算を実行する第３の工程と、前記第２及び第３の工程によるデータ変換後のデータに対して量子化演算を実行する第４の工程と、を具備したことを特徴としている。
【００１６】
請求項２記載の発明は、相関する２つのデータから構成されるデータを記憶する第１の工程と、前記相関する２つのデータの一方に対して、所定の変換係数を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算を行う第２の工程と、前記相関する２つのデータの他方に対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算を行う第３の工程と、前記第２の工程におけるデータ変換演算で得られたデータから、前記第３の工程におけるデータ変換演算で得られたデータを減算する第４の工程と、前記第４の工程における減算処理後のデータに対して量子化演算を実行する第５の工程と、を具備したことを特徴としている。
【００１８】
請求項３記載の発明は、所定のデータを記憶するデータ記憶手段と、前記データ記憶手段から出力されたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、一次元目のデータ変換演算を実行する第１の演算手段と、前記第１の演算手段により一次元目のデータ変換演算が行われたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、二次元目のデータ変換演算を実行する第２の演算手段と、前記第１の演算手段及び第２の演算手段による一次元目及び二次元目のデータ変換後のデータに対して量子化演算を実行する量子化手段と、前記データ記憶手段、前記第１の演算手段、前記第２の演算手段及び前記量子化手段を制御する制御手段と、を備えることを特徴としている。
【００１９】
請求項４記載の発明は、相関する２つのデータから構成されるデータを記憶するデータ記憶手段と、前記相関する２つのデータの一方に対して、所定の変換係数を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算を行う第１の演算手段と、前記相関する２つのデータの他方に対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算を行う第２の演算手段と、前記第１の演算手段によるデータ変換演算で得られたデータから、前記第２の演算手段によるデータ変換演算で得られたデータを減算する第３の演算手段と、前記第３の演算手段による減算処理後のデータに対して量子化演算を実行する量子化手段と、前記データ記憶手段、前記第１の演算手段、前記第２の演算手段、前記第３の演算手段及び前記量子化手段を制御する制御手段と、を備えることを特徴としている。
【００２８】
【作用】
本発明の手段の作用は次の通りである。
【００２９】
請求項１記載の発明では、第１の工程で所定のデータが記憶され、第２の工程により前記第１の工程により出力されたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、一次元目のデータ変換演算が実行され、第３の工程により前記第２の工程により一次元目のデータ変換演算が行われたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、二次元目のデータ変換演算が実行され、第４の工程により前記第２及び第３の工程によるデータ変換後のデータに対して量子化演算が実行される。
【００３０】
請求項２記載の発明では、第１の工程で相関する２つのデータから構成されるデータが記憶され、第２の工程により前記相関する２つのデータの一方に対して、所定の変換係数を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算が行われ、第３の工程により、前記相関する２つのデータの他方に対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算が行われ、第４の工程により、前記第２の工程におけるデータ変換演算で得られたデータから、前記第３の工程におけるデータ変換演算で得られたデータが減算され、第５の工程により、前記第４の工程における減算処理後のデータに対して量子化演算が実行される。
【００３３】
請求項３記載の発明では、データ記憶手段により、所定のデータが記憶され、第１の演算手段により、前記データ記憶手段から出力されたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、一次元目のデータ変換演算が実行され、第２の演算手段により、前記第１の演算手段により一次元目のデータ変換演算が行われたデータに対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てる処理を施すことにより、二次元目のデータ変換演算が実行され、量子化手段により、前記第１の演算手段及び第２の演算手段による一次元目及び二次元目のデータ変換後のデータに対して量子化演算が実行され、制御手段により、前記データ記憶手段、前記第１の演算手段、前記第２の演算手段及び前記量子化手段が制御される。
【００３４】
請求項４記載の発明では、データ記憶手段により、相関する２つのデータから構成されるデータが記憶され、第１の演算手段により、前記相関する２つのデータの一方に対して、所定の変換係数を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算が行われ、第２の演算手段により、前記相関する２つのデータの他方に対して、所定の変換係数と−１を乗算して、所定ビット数の下位ビットを切り捨てるデータ変換演算が行われ、第３の演算手段により、前記第１の演算手段によるデータ変換演算で得られたデータから、前記第２の演算手段によるデータ変換演算で得られたデータが減算され、量子化手段により、前記第３の演算手段による減算処理後のデータに対して量子化演算が実行され、制御手段により、前記データ記憶手段、前記第１の演算手段、前記第２の演算手段、前記第３の演算手段及び前記量子化手段が制御される。
【００３７】
したがって、データを変換演算する際に発生する演算誤差を、−１を乗算した値で相殺して全体的な演算誤差を小さくすることができ、データ変換演算処理における演算精度を向上させるデータ圧縮装置を提供することができる。
【００４０】
【実施例】
以下、本発明を図面に基づいて説明する。
【００４１】
原理説明
まず、本発明の基本的な考え方を説明する。
【００４２】
上記従来で説明したアダマール変換方式による二次元データの変換演算処理、または、上記従来の図６に示したＤＣＴ方式によるデータ圧縮装置１では、データ変換演算装置３は、バレルシフタ８により右シフト（切り捨て）処理を行うことによって画像データの必要なビット数を残すようにしていたため、出力結果が全体的に本来とるべき値よりも小さくなり、演算誤差が大きくなっていた。
【００４３】
ところが、従来の画像データのデータ変換演算では、上記従来の各図９、図１１、図１２に示したいずれのデータ変換演算装置３においても、一次元目と二次元目の変換演算で係数ＲＯＭから読み出した係数データを乗算する処理を２回行っており、以下に、この係数の乗算過程と乗算結果の関係を解析するとことにより、本発明の基本的な考え方を説明する。
【００４４】
まず、上記従来の図１０に示した演算出力結果の図を参照して説明すると、その演算出力結果の正の数と負の数をそれぞれ絶対値として見た場合、正の数は小さくなり、負の数は大きくなる。
【００４５】
いま、入力データが正の数であったとすると、従来の二次元演算処理による演算結果と絶対値の関係を以下に列記する。
【００４６】
（一次元目）
まず、一次元目の演算では、係数として、例えば、“ｃｏｓ２／１６”という正の係数を乗算したとすると、その乗算結果は正の数で、その正の数の必要ビット数以下を切り捨てると、絶対値として見た場合、本来とるべき値よりも
小さい値をとることになる。
【００４７】
（二次元目）
次いで、二次元目の演算では、一次元目の結果に、さらに正の係数を乗算したとすると、その乗算結果は正の数で、その正の数の必要ビット数以下を切り捨てると、絶対値として見た場合、一次元の乗算結果よりもさらに小さい値を
とることになり、本来とるべき値からの誤差がさらに拡大する。
【００４８】
すなわち、従来の二次元演算処理では、一次元目と二次元目で乗算する係数が共に正の係数で切り捨てを行うと、その２回の演算結果を絶対値として見た場合、本来とるべき値からの誤差が大きくなってしまう。したがって、以上に述べた従来の二次元演算処理で演算結果を、例えば、ＣＣＩＴＴ（国際電信電話諮問委員会）のＨ．２６１に規定されている画像圧縮技術に関する演算精度を満たそうとすると、演算桁数を増やして切り捨てるビット数を減らす必要がある。
【００４９】
そこで、本発明では、上記従来の一次元目、二次元目の演算処理の際に、得られる結果を絶対値として見た場合、それぞれの演算過程で、従来の変換係数に−１を乗算すると、最終的に得られる演算結果の絶対値は、本来とるべき値からの誤差が小さくなることに着目し、その基本的な演算過程についてさらに説明する。
【００５０】
例えば、上記従来の一次元目の演算過程で、正の変換係数に（−１）を乗算すると、その演算結果は負の数となり、この負の数に対して切り捨て処理を行うと、その絶対値は少し大きい値をとることになる。
【００５１】
続いて、上記従来の二次元目の演算過程で、正の変換係数に再び（−１）を乗算すると、その演算結果は正の数となり、この正の数に対して切り捨て処理を行うと、その絶対値は少し小さい値をとることになる。
【００５２】
すなわち、一次元目と二次元目の演算処理でともに正の変換係数に（−１）を乗算することにより、最終的に得られる演算結果の正、負の符号は同じものとなり、さらに、一次元目と二次元目の演算結果により、それぞれの演算過程で発生する演算誤差を相殺することとなり、全体の演算誤差を絶対値としてとらえることにより従来に比べて演算誤差を小さくすることができる。
【００５３】
ここで、上記本発明の基本原理をアダマール変換方式に適用した場合について以下に説明する。
【００５４】
図１は、従来のアダマール変換方式により処理されるａ、ｂ、ｃ、ｄの４つの元からなる二次元データの演算過程を示す図である。
【００５５】
いま、図１（ａ）に示す二次元データに対して一次元アダマール変換（横方向）を施すと、図１（ｂ）に示す演算結果が得られ、さらに、この演算結果に一次元アダマール変換（縦方向）を施すと、図１（ｃ）に示す演算結果が得られる。以上が通常の二次元アダマール変換処理である。
【００５６】
このアダマール変換では、ｘ、ｙの２つの入力に対して、式（３）、（４）を求めている。
【００５７】
【数３】

【００５８】
【数４】

この図１（ａ）〜（ｃ）のアダマール演算に対して上記原理説明で述べた（−１）を乗算した場合の演算過程を図２に示して説明する。
【００５９】
図２は、上記式（３）、（４）に（−１）を乗算するものであり、式（５）、（６）を求めるものである。
【００６０】
【数５】

【００６１】
【数６】

すなわち、図２（ｂ）は、図１（ｂ）の値に（−１）を乗算したものであり、図２（ｃ）は、図１（ｃ）の値に（−１）を乗算したものであり、すなわち、それぞれの一次元アダマール変換に乗算される値は、（−１）×（−１）＝１となるため、最終的に得られる演算結果は変わらないことがわかる。
【００６２】
さらに、これらの関係を一般式に適用した例を以下に示すデータ変換演算式（７）により説明する。
【００６３】
【数７】

この式（７）は、一次元のときの演算式であり、乗算及び加算には演算誤差は無いものとするが、実際には、係数ａi を有限ビット数で表現する場合に誤差が発生することもある。この式（７）に対してバレルシフタによる切り捨て処理を行うと、式（８）に示すように、“−Δi ”が一次元目の演算誤差として出力される。
【００６４】
【数８】

すなわち、式（８）から式（７）を減算した結果が、式（９）に示す一次元目の演算処理した後の実際の演算誤差の一般式である。
【００６５】
【数９】

さらに、式（８）に対して、二次元目の演算処理を施して切り捨て処理を行うと、式（１０）に示すように、“−Δj ”の項が二次元目の演算誤差として出力される。
【００６６】
【数１０】

ここまでが従来と同様の二次元演算処理の一般式である。すなわち、式（１０）から式（７）を減算した結果が、式（１１）に示す二次元目の演算処理した後の実際の演算誤差の一般式である。
【００６７】
【数１１】

ここで、例えば、上記アダマール変換で示した式（３）の様に、その係数が全て正の数である場合を考えると、式（１１）の各項は、“−Δi ”と“−Δj ”と全て負の数をとるため、上記従来の図１０に示した演算誤差を示した図と同様に本来とるべき値よりも全体的に小さい値となり、大きな誤差が発生する。
【００６８】
本発明では、この式（１１）の係数“ａj ”に対して（−１）を乗算すると、式（１２）によって表される。
【００６９】
【数１２】

この式（１２）の各項について同様に誤差を考えると、Σ内の第１項は正の数、第２項は負の数となり、上記のように各項の演算誤差を絶対値としてとらえると互いに誤差を相殺し、式（１１）よりも誤差を小さくすることができ、演算精度の向上を図りつつデータ変換演算を行うことができる。
【００７０】
また、上記式（１２）の例では、変換係数に（−１）を乗算して、二次元変換演算によってその誤差を減少させるようにしたが、係数が負の数の場合には、かえって演算誤差が大きくなってしまう可能性がある。
【００７１】
そこで、本来の係数の値に（−１）を乗算した値を予め係数ＲＯＭ等に格納しておき、例えば、式（１３）に対して、偶数番目の項（αi ，ｂi ＝２ｍ）には、本来の係数を乗算して“αi ＝１”と“ｂi ＝ａi ”とし、奇数番目の項（αi ，ｂi ＝２ｍ＋１）には、（−１）を乗算した係数を用いて“αi ＝−１”と“ｂi ＝−ａi ”とし、加減算器によってその（−１）を乗算した分を補正するようにする。
【００７２】
【数１３】

この式（１３）の偶数項に本来の変換係数を乗算し、奇数項に本来の変換係数と（−１）を乗算した結果は、式（１４）となる。
【００７３】
【数１４】

この式（１４）の各項について同様に誤差を考えると、Σ内の第１項は負の数、第２項は正の数となり、上記のように各項の演算誤差を絶対値としてとらえると互いに誤差を相殺し、上記式（１１）よりも誤差を小さくすることができ、係数が全て負の数である場合にも対応できる。また、二次元変換演算だけでなく、一次元演算においても本発明の基本原理を応用すれば、演算精度を向上させることができる。
【００７４】
第１実施例
以下、上記本発明の基本的な考え方に基づいて実施例を説明する。
【００７５】
図３、図４は、本発明に係るデータ圧縮装置の第１実施例を示す図であり、ＤＣＴ変換方式に基づくデータ圧縮装置に適用した例である。
【００７６】
まず、構成を説明する。図３は、データ圧縮装置２０のブロック構成図である。この図において、データ圧縮装置２０は、圧縮を施そうとする画像データを１フレーム単位で蓄積するデータ記憶装置２１と、データ記憶装置２１から読出した１フレーム単位の画像データに対してＤＣＴ演算処理により上記図７に示したように、例えば、画像データを８×８画素から成るブロック単位で特定の周波数成分の抽出処理を縦横（順不同）二次元に施すとともに、その二次元変換演算処理に際して後述する乗算処理を施すデータ変換演算装置２２と、データ記憶装置２０に蓄えられたデータ変換演算後のデータに対して、例えば上記図８に示したような量子化テーブルの値で除算をする（あるいは、逆数の乗算）ことによって量子化演算を行なう量子化装置２３と、各部装置の動作を制御してデータ圧縮装置２０全体を制御する制御装置２４とにより構成される。
【００７７】
データ変換演算装置２２は、図４に示すように、乗算器３３が画像データに対して乗算する係数データを格納する係数ＲＯＭ３１と、乗算器３３が画像データに対して乗算する数値データを格納する補数ＲＯＭ３２、上記データ記憶装置２１から入力される画像データに対して係数ＲＯＭ３１から読み出した係数と補数ＲＯＭ３２から読み出した数値とを乗算してバレルシフタ３４に出力する乗算器３３と、乗算器３３から入力される乗算後のデータを必要なビット数だけ残し、右シフト（切り捨て）し、加減算器３５に出力するバレルシフタ３４と、バレルシフタ３４から入力される値に前回の値との和（差）を求める加減算器３５とにより構成されている。
【００７８】
すなわち、本データ変換演算装置２２の補数ＲＯＭ３２は、係数ＲＯＭ３１に格納されている係数データに乗算する数値データを予め格納し、乗算器３３は、データ記憶装置２１から入力される画像データに対して二次元変換演算処理を行う際に、一次元目と二次元目の乗算に必要な係数データを係数ＲＯＭ３１から読み出して乗算するとともに、必要に応じてその係数データに乗算する数値データを補数ＲＯＭ３２から読み出して乗算するようにしている。これは上記基本原理で説明したように、バレルシフタ３４により切り捨てられ、加減算器３５により最終的に出力される二次元の演算結果の誤差を小さくするようにするためである。
【００７９】
次に、本実施例の動作を説明する。
【００８０】
まず、データ記憶装置２１には、原画像のデータが保持されているものとする。データ変換演算装置２２は、データ記憶装置２１から画像データを読込んでＤＣＴ演算を行ない、そのＤＣＴ演算出力は、量子化装置２３に送られる。また、量子化装置２３では、データ変換演算装置２２からの入力に対して所定の量子化テーブルの値に従って量子化演算を行なう。
【００８１】
このとき、本実施例のデータ変換演算装置２２では、例えば、式（１５）に示す４次行列の画像データに対してＤＣＴ方式の二次元変換演算処理が行われるものとする。
【００８２】
【数１５】

このデータ変換演算装置２２における演算過程を上記基本原理で説明した一般式（７）〜（１２）に対応させて説明する。
【００８３】
まず、この式（１５）の画像データに対して一次元目の変換演算処理を行って係数ＲＯＭ３１から読み出した係数を乗算器３３で乗算すると、上記一般式（７）に対応する式（１６）に示す値が演算結果として出力される。
【００８４】
【数１６】

この式（１６）に対してバレルシフタ３４による切り捨て処理を行うと、上記一般式（８）に対応する式（１７）に示す値が演算結果として出力される。
【００８５】
【数１７】

このとき式（１７）に示すように、各項で“−Δ00，−Δ01，−Δ02，−Δ03”が一次元目の演算誤差として出力される。
【００８６】
すなわち、式（１７）から式（１６）を減算した結果が、式（１８）に示す一次元目の演算処理した後の演算誤差が負の値で出力される。
【００８７】
【数１８】

さらに、式（１７）に対して、二次元目の変換演算処理を行って係数ＲＯＭ３１から読み出した係数を乗算器３３で乗算すると、上記一般式（１０）に対応する式（１９）に示す負の値が演算結果として出力される。
【００８８】
【数１９】

この式（１９）に対してバレルシフタ３４による切り捨て処理を行うと、上記一般式（１１）に対応する式（２０）に示す値が演算結果として出力される。
【００８９】
【数２０】

このとき式（２０）に示すように、上記式（１８）に示した演算誤差に加えて各項にニ次元目の負の値の演算誤差が出力され、全体として負の値にシフトした演算誤差となり、本来とるべき値からの誤差が大きくなっている。すなわち、式（２０）の各項のＣＯＳ係数は全て正の数であるため、この各項では、“−Δij”（i ＝０，１、j ＝０〜９）と全て負の数をとるため、上記従来の図１０に示した演算誤差を示した図と同様に本来とるべき値よりも全体的に小さい値となり、大きな誤差が発生する。ここまでが従来のＤＣＴ方式による二次元変換演算処理の演算過程である。
【００９０】
本実施例では、この式（２０）の各項の係数に対して補数ＲＯＭ３２から読み出した数値データとして（−１）を乗算器３３で乗算すると、上記一般式（１２）に対応する式（２１）に示す演算結果が出力される。
【００９１】
【数２１】

このように係数に（−１）を乗算すると、各項で正の値と負の値が相殺し合って全体的な演算誤差を上記式（２０）に比べて小さくすることができる。
【００９２】
したがって、本実施例のＤＣＴ方式による画像データの二次元変換演算処理では、各項の係数に予め補数ＲＯＭに格納した数値（−１）を乗算することにより、一次元目と二次元目に発生する負の演算誤差を正の演算誤差として相殺して全体的な演算誤差を小さくすることができ、二次元変換演算処理の演算精度を向上させることができる。
【００９３】
したがって、上記従来の図９に示したデータ変換演算装置３のようにバレルシフタ８により右シフト（切り捨て）処理を行う場合に比べて、本実施例のデータ圧縮装置２０では、その出力する演算結果を本来とるべき値との演算誤差がより小さくなるように算出することができる。
【００９４】
また、上記従来の図１１に示したデータ変換演算装置３のようにインクリメンタ１０を追加して四捨五入処理を行う場合に比べて、上記従来の図９と同等の回路構成で本実施例のデータ圧縮装置２０を実現でき、回路規模を大きくすることなく低コストで演算精度を向上させることができる。
【００９５】
また、上記従来の図１２に示したデータ変換演算装置３のようにバレルシフタ８と加減算器９をバス１２で接続し、バレルシフタ８と加減算器９のバス切換えにより加減算器９が四捨五入処理を行う場合に比べて、本実施例のデータ圧縮装置２０では演算時間を長引かせることなく演算精度を向上させることができる。なお、上記実施例では、補数ＲＯＭを別に設けるようにしたが、従来の係数ＲＯＭの空き領域に格納してもよく、実際にはハード構成を追加することなく、格納する係数データの変更と処理プログラム等を変更するだけでよく、低コストで本実施例を実現することができる。
【００９６】
第２実施例
また、第１実施例では、本発明を画像データの二次元変換演算処理としてＤＣＴ方式に適用した場合を説明したが、すなわち、乗算、切り捨て、加減算処理を２回繰り返し行う処理の場合に、本発明の乗算処理が有効である旨を説明したが、強い相関を持つデータが隣接して存在する場合には、その各データに順次一次元変換演算処理する場合であっても本発明の乗算処理は有効である。すなわち、二次元の画像データを奇数ラインと偶数ラインに分け、そのライン毎に一次元変換演算処理を実行する場合、又は、画素データ毎に一次元変換演算処理を実行する場合である。
【００９７】
このような強い相関を持つ隣接データに対する一次元変換演算処理に本発明のデータ圧縮装置を適用した例を以下に第２実施例として説明する。
【００９８】
図５は、本発明のデータ圧縮装置の第２実施例を示す図であり、ＤＣＴ変換方式に基づくデータ圧縮装置に適用した例である。図５は、データ圧縮装置内のデータ変換演算装置のブロック構成図である。なお、本実施例のデータ圧縮装置の全体のブロック構成は、上記第１実施例の図３に示したデータ圧縮装置と同一であるため図示及び説明は省略する。
【００９９】
図５において、データ変換演算装置４０は、乗算器４３が画像データに対して乗算する係数データを格納する係数ＲＯＭ４１と、乗算器４３が画像データに対して乗算する数値データを格納する補数ＲＯＭ４２、上記データ記憶装置２１から入力されるライン毎の画像データあるいは画素データに対し、そのラインデータ毎あるいは画素データ毎に係数ＲＯＭ４１から読み出した係数と補数ＲＯＭ４２から読み出した数値とを乗算してバレルシフタ４４に出力する乗算器４３と、乗算器４３から入力される乗算後のデータを必要なビット数だけ残し、右シフト（切り捨て）し、加減算器４５に出力するバレルシフタ４４と、バレルシフタ４４から入力される値に前回の値との和（差）を求める加減算器４５とにより構成されている。
【０１００】
すなわち、本データ変換演算装置４０の補数ＲＯＭ４２は、係数ＲＯＭ４１に格納されている係数データに乗算する数値データを予め格納し、乗算器４３は、データ記憶装置２１から入力されるライン毎の画像データあるいは画素データに対して一次元変換演算処理を行う際に、乗算に必要な係数データを係数ＲＯＭ４１から読み出して乗算するとともに、必要に応じてその係数データに乗算する数値データを補数ＲＯＭ４２から読み出して乗算するようにしている。これは上記基本原理で説明したように、バレルシフタ４４により切り捨てられ、加減算器４５により出力される一次元の演算結果の誤差を小さくするようにするためである。
【０１０１】
次に、本実施例の動作を説明する。
【０１０２】
まず、データ記憶装置２１には、原画像のデータが保持されているものとする。データ変換演算装置４０は、データ記憶装置２１からライン毎の画像データあるいは画素データを読込んでＤＣＴ演算を行ない、そのＤＣＴ演算出力は、上記量子化装置２３に送られる。また、量子化装置２３では、データ変換演算装置２２からの入力に対して所定の量子化テーブルの値に従って量子化演算を行なう。このとき、本実施例のデータ変換演算装置４０では、例えば、上記式（１５）に示した４次行列の画像データに対してＤＣＴ方式の一次元変換演算処理が行われるものとする。このデータ変換演算装置４０における演算過程を上記基本原理で説明した一般式（１３）に対応させて説明する。
【０１０３】
まず、この式（１５）の画像データに対して一次元の変換演算処理を行って係数ＲＯＭ４１から読み出した係数と補数ＲＯＭ４２を乗算器４３で乗算すると、上記一般式（１３）に対応する式（２２）に示す値が演算結果として出力される。
【０１０４】
【数２２】

この式（２２）では、第１項目及び第３項目では通常の係数を乗算し、第２項目及び第４項目では係数と（−１）を乗算している。すなわち、各項の係数が全て正の数であるため、奇数項には係数のみを乗算し、偶数項には係数と（−１）を乗算することにより、奇数項の演算誤差を正の数として小さくし、偶数項の演算誤差を負の数として大きくし、奇数項と偶数項で演算誤差を相殺するようにしている。
【０１０５】
したがって、一次元変換演算処理で全ての項の係数が同一符号であっても、奇数項あるいは偶数項に（−１）を乗算することにより、奇数項と偶数項で発生する演算誤差が相殺するように演算結果を得ることができ、全体の演算誤差を小さくすることができる。
【０１０６】
したがって、上記第１実施例では、二次元変換演算処理で乗算する係数が全て正の数の場合に−１を乗算する場合を説明したが、係数が負の数の場合には、かえって演算誤差が大きくなってしまう可能性がある（但し、この場合でも上記従来のデータ圧縮装置で発生する演算誤差を超えることはない）が、第２実施例では、各項の係数に対して奇数項あるいは偶数項のみに（−１）を乗算しているので、奇数項と偶数項の間で演算誤差を小さくすることができ、全体の演算誤差を確実に小さくすることができる。
【０１０７】
その結果、一次元変換演算処理においても従来よりも演算誤差を小さくすることができ、一次元変換演算処理における演算精度の向上を図ることができる。また、本実施例では、上記第１実施例と同様に、補数ＲＯＭを別に設けるようにしたが、従来の係数ＲＯＭの空き領域に格納してもよく、実際にはハード構成を追加することなく、格納する係数データの変更と処理プログラム等を変更するだけでよく、低コストで本実施例を実現することができる。
【０１０８】
また、本実施例は、相関性の高いデータであれば、画像データ以外のデータに対しても適用可能であり、例えば、データが奇数ブロックと偶数ブロックに分けられるような場合にも適用可能である。
【０１０９】
なお、上記各実施例では、本発明をＤＣＴ方式のデータ圧縮装置に適用した場合について説明したが、このＤＣＴ方式に限定されず、データ圧縮を行うものであればどのような装置にも適用できることは言うまでもない。例えば、ＪＰＥＧ（Joint Photographic Expert Group ）やＭＰＥＧ（Motion Picture Image Co-ding Experts Group）に準拠したデータ圧縮装置にも適用することができる。
【０１１１】
また、本実施例では、データ変換演算装置にＤＣＴを適用しているが、これら符号化方式には限定されず、符号化演算を行なうものであればどのような装置にも適用できることは言うまでもない。例えば、ハール（Harr）変換、傾斜変換（スラント変換）、対称性サイン変換などを用いたデータ圧縮伸張装置に適用することができる。
【０１１２】
また、入力データに対してデータ変換を行なうものであれば、データ変換の種類は何でもよく、ＤＣＴによる周波数成分の変換のほか、例えばＦＦＴ，ＬＯＴ（Lapped Orthogonal Transform：重合直交変換）等の直交データ変換に適用可能である。
【０１１３】
【発明の効果】
本発明によれば、データ記憶手段から出力されたデータに対してデータ変換演算手段により所定の変換係数に基づく変換符号化、直交変換あるいは周波数変換により二次元のデータ変換演算を実行し、該データ変換演算では、入力データに対して変換係数と−１を乗算するようにしたため、データを変換演算する際に発生する演算誤差を、−１を乗算した値で相殺して全体的な演算誤差を小さくすることができ、データ変換演算処理における演算精度を向上させることができる。
【図面の簡単な説明】
【図１】本発明の基本原理説明において従来のアダマール変換方式により処理される二次元データの演算過程を示す図。
【図２】本発明の基本原理説明において本発明のアダマール変換方式により処理される二次元データの演算過程を示す図。
【図３】本発明を適用した第１実施例のデータ圧縮装置のブロック構成図。
【図４】図３のデータ変換演算装置のブロック構成図。
【図５】本発明を適用した第２実施例のデータ変換演算装置のブロック構成図。
【図６】従来のデータ圧縮装置のブロック構成図。
【図７】図６のデータ圧縮装置により処理される画像データの構成を示す図。
【図８】図６の量子化装置により利用される量子化テーブルの構成を示す図。
【図９】図６のデータ変換演算装置のブロック構成図。
【図１０】図９のデータ変換演算装置により出力される演算結果を説明するための図。
【図１１】従来のその他のデータ変換演算装置のブロック構成図。
【図１２】従来のその他のデータ変換演算装置のブロック構成図。
【符号の説明】
２０データ圧縮装置
２１データ記憶装置
２２データ変換演算装置
２３量子化装置
２４制御装置
３１、４１係数ＲＯＭ
３２、４２補数ＲＯＭ
３３、４３乗算器
３４、４４バレルシフタ
３５、４５加減算器[0001]
[Industrial applications]
The present invention relates to a data compression method and a data compression apparatus used for compression processing of image data and the like, and more particularly, to a data compression method and a data compression apparatus capable of improving calculation accuracy in data conversion calculation processing. About.
[0002]
[Prior art]
Recently, with the rapid development of digital technology, ISDN (Integrated Services Digital Communication Network), which integrates the transmission, exchange and service of digital data, has been put into practical use by digital technology. -The receiving environment is being prepared.
[0003]
When sending and receiving digitized image data in such an environment, if the image is digitized as it is, the amount of data becomes enormous. Therefore, there is a demand for an image compression technique for compressing the data amount when digitizing the image. Is growing. As a typical image compression technique in the related art, orthogonal transform coding is known as a highly efficient coding technique. As an encoding method based on the orthogonal transform encoding, for example, there is a Hadamard transform method in which elements of a transformation matrix are simple and can be transformed only by addition / subtraction processing. In this Hadamard transform method, the elements of the transformation matrix are composed of “+1” and “−1”, and the transformation matrix is transformed into a higher order form as shown in equation (2) based on the basic transformation matrix shown in equation (1). Has been extended. With this Hadamard transform method, the hardware configuration can be simplified.
[0004]
(Equation 1)

[0005]
(Equation 2)

In addition, there are JPEG (Joint Photographic Ex-pert Group) and MPEG (Moving Picture Expert Group) as international standards of image compression technology. The purpose of JPEG is to compress a still image, and a coding method of a color still image has already been determined and will be approved as an international standard. As for JPEG, a chip has been commercialized, and a board using this chip has begun to appear on the market. The JPEG algorithm is roughly divided into two compression methods. The first method is a method based on DCT (Discrete Cosine Transform), which is one encoding method of orthogonal transform coding, and the second method uses DPCM (Differntial PCM) in a two-dimensional space. This is a Spatial (spatial function) method. Since the DCT method includes quantization, generally, the original image is an irreversible encoding in which the original image is not completely reproduced. However, sufficient decoding image quality can be obtained even with a small number of bits. is there. On the other hand, the Spatial method is a reversible coding that has a small compression ratio but completely reproduces the original image, and is a method added as a standard method to realize this characteristic.
[0006]
As a data compression apparatus for compressing image data using such a conventional DCT method, for example, there is a data compression apparatus shown in FIG. In FIG. 6, reference numeral 2 denotes a data storage device, which stores image data to be compressed in units of one frame. Reference numeral 3 denotes a data conversion operation device, which extracts a specific frequency component from the image data of one frame unit output from the data storage device 2 by a data conversion operation such as the DCT operation and then stores the data again. Write back to device 2. The processing of the data conversion operation device 3 is a one-dimensional case, and in a two-dimensional case like image data, for example, as shown in FIGS. The above-described frequency component extraction processing is performed two-dimensionally in the vertical and horizontal directions (in no particular order) for each block of pixels.
[0007]
Numeral 4 denotes a quantization device which divides the data after the data conversion operation stored in the data storage device 2 by a value of a quantization table as shown in FIG. 8 (or multiplication by a reciprocal). Thus, a quantization operation is performed. Reference numeral 5 denotes a control device, which controls the operation of each of the above devices and controls the entire data compression device 1.
[0008]
Also, as an internal configuration of the data conversion operation device 3 shown in FIG. 6, for example, there is a block diagram shown in FIG. In FIG. 9, reference numeral 6 denotes a coefficient ROM, which stores coefficient data by which the multiplier 7 multiplies the image data. The multiplier 7 multiplies the image data input from the data storage device 2 by the coefficient read from the coefficient ROM 6 and outputs the result to the barrel shifter 8. The barrel shifter 8 shifts to the right (rounds down) the multiplied data input from the multiplier 7, leaving the required number of bits, and outputs the data to the adder / subtractor 9. The adder / subtractor 9 calculates a sum (difference) between the value input from the barrel shifter 8 and the previous value.
[0009]
In the data conversion operation device 3, when the barrel shifter 8 performs a right shift (round down) process, the output result takes a smaller value as a whole as shown in FIG. In this figure, the output value when right shifted by one bit is shown, where “○” indicates that the value is not included, and “●” indicates that the value is included.
[0010]
Further, as a difference from the data conversion operation device 3 shown in FIG. 9, for example, as in the data conversion operation device 3 shown in FIG. 11, an incrementer 10 is added after the barrel shifter 8 to perform a rounding process. The barrel shifter 8 and the adder / subtractor 9 are connected by a bus 12, and the bus switching of the barrel shifter 8 and the adder / subtractor 9 and the operation of the incrementer are performed by the adder / subtractor 9 as in the data conversion operation device 3 shown in FIG. In some cases, the rounding process is performed instead.
[0011]
[Problems to be solved by the invention]
However, in the data compression apparatus that performs such a conventional data conversion operation, when the barrel shifter 8 performs the right shift (round down) processing as in the data conversion operation apparatus 3 shown in FIG. Since the output result takes a smaller value as a whole as shown in FIG. 10, there is a disadvantage that a calculation error from a value to be originally taken becomes large.
[0012]
Further, when the rounding process is performed by adding the incrementer 10 as in the data conversion operation device 3 shown in FIG. 11, there is a problem that the circuit scale becomes large, and the data conversion operation shown in FIG. When the barrel shifter 8 and the adder / subtractor 9 are connected by a bus 12 as in the device 3, and the adder / subtractor 9 performs a rounding process by switching the bus between the barrel shifter 8 and the adder / subtractor 9, only the bus switching needs to be increased. However, there is a problem in that the calculation time is lengthened by performing the calculation twice.
[0013]
SUMMARY OF THE INVENTION It is an object of the present invention to provide a data compression method and a data compression apparatus that improve the calculation error of the data conversion calculation processing without increasing the circuit scale or prolonging the calculation time.
[0014]
[Means for Solving the Problems]
The means of the present invention are as follows.
[0015]
According to a first aspect of the present invention, in order to achieve the above object, a first step of storing predetermined data, and multiplying the data output in the first step by a predetermined conversion coefficient and -1.Then, by performing a process of truncating lower bits of a predetermined number of bits,A second step of performing a first-dimensional data conversion operation, and multiplying the data on which the first-dimensional data conversion operation has been performed by the second step by a predetermined conversion coefficient and −1.Then, by performing a process of truncating lower-order bits of a predetermined number of bits,A third step of executing a data conversion operation of a dimension, and a fourth step of executing a quantization operation on the data after the data conversion by the second and third steps. And
[0016]
The invention according to claim 2 isConsists of two correlated dataA first step of storing data;A second step of performing a data conversion operation of multiplying one of the two correlated data by a predetermined conversion coefficient and discarding a predetermined number of lower bits, and a second step of performing a data conversion operation on the other of the two correlated data. And a third step of performing a data conversion operation of multiplying a predetermined conversion coefficient by −1 and truncating lower-order bits of a predetermined number of bits, and the data obtained by the data conversion operation in the second step, A fourth step of subtracting the data obtained by the data conversion operation in the third step; and a fifth step of performing a quantization operation on the data after the subtraction processing in the fourth step. What you didFeatures.
[0018]
According to a third aspect of the present invention, there is provided a data storage means for storing predetermined data, and multiplying the data outputted from the data storage means by a predetermined conversion coefficient and -1.Then, by performing a process of truncating lower-order bits of a predetermined number of bits, a first arithmetic unit for executing a first-dimensional data conversion operation, and a first-dimensional data conversion operation performed by the first arithmetic unit are performed. WasMultiply data by a specified conversion factor and -1And performing a process of truncating lower-order bits of a predetermined number of bits, thereby performing second-dimensional data conversion operation.,By the first and second computing meansQuantization means for performing a quantization operation on the data after the first-dimensional and second-dimensional data conversion, the data storage means,The first arithmetic means, the second arithmetic meansAnd control means for controlling the quantization means.
[0019]
The invention according to claim 4 isConsists of two correlated dataData storage means for storing data;A first calculating means for multiplying one of the two correlated data by a predetermined conversion coefficient and performing a data conversion operation for cutting off lower-order bits of a predetermined number of bits; On the other hand, a second operation means for performing a data conversion operation of multiplying a predetermined conversion coefficient by -1 and discarding lower-order bits of a predetermined number of bits, and data obtained by the data conversion operation by the first operation means A third operation means for subtracting data obtained by the data conversion operation by the second operation means from the second operation means;Quantizing means for performing a quantization operation on the data of the data storage means,The first arithmetic means, the second arithmetic means, and the third arithmetic meansAnd control means for controlling the quantization means,To haveFeatures.
[0028]
[Action]
The operation of the means of the present invention is as follows.
[0029]
According to the first aspect of the present invention, predetermined data is stored in the first step, and the data output in the first step in the second step is multiplied by a predetermined conversion coefficient and -1.Then, by performing a process of truncating lower bits of a predetermined number of bits,The first-dimensional data conversion operation is executed, and the data obtained by performing the first-dimensional data conversion operation in the second step in the third step is multiplied by a predetermined conversion coefficient by -1.Then, by performing a process of truncating lower-order bits of a predetermined number of bits,A data conversion operation of the dimension is executed, and a quantization operation is executed in a fourth step on the data after the data conversion in the second and third steps.
[0030]
According to the invention described in claim 2, in the first step,Consists of two correlated dataThe data is stored and by the second stepA data conversion operation for multiplying one of the two correlated data by a predetermined conversion coefficient and truncating lower-order bits of a predetermined number of bits is performed, and the third step performs a data conversion operation on the other of the two correlated two data. Is subjected to a data conversion operation of multiplying by a predetermined conversion coefficient and −1 to discard a predetermined number of lower bits, and is obtained in a fourth step by the data conversion operation in the second step. The data obtained by the data conversion operation in the third step is subtracted from the data, and in the fifth step, a quantization operation is performed on the data after the subtraction processing in the fourth step.
[0033]
In the invention according to claim 3,The predetermined data is stored by the data storage means, and the predetermined data is stored by the first arithmetic means.Multiply the data output from the data storage means by a predetermined conversion coefficient and -1Then, by performing a process of truncating lower-order bits of a predetermined number of bits, the first-dimensional data conversion operation is performed, and the first-dimensional data conversion operation is performed by the first operation unit by the second operation unit. It was conductedMultiply data by a specified conversion factor and -1Then, by performing a process of truncating lower-order bits of a predetermined number of bits, a second-dimensional data conversion operation is performed., By the quantization means,By the first and second computing meansA quantization operation is performed on the data after the first and second dimension data conversion.The control means controls the data storage means, the first calculation means, the second calculation means, and the quantization means.
[0034]
In the invention according to claim 4,The data storage means stores data composed of two correlated data, and the first arithmetic means multiplies one of the two correlated data by a predetermined conversion coefficient to obtain a predetermined number of bits. A data conversion operation for discarding the lower bits of is performed, and the other of the two correlated data is multiplied by a predetermined conversion coefficient by −1 by the second calculating means, and the lower bits of the predetermined number of bits are converted. A data conversion operation for rounding down is performed, and the data obtained by the data conversion operation by the second operation unit is subtracted from the data obtained by the data conversion operation by the first operation unit by the third operation unit. ,By the quantization means,After the subtraction processing by the third arithmetic meansQuantization operation is performed on the dataThe control means controls the data storage means, the first calculation means, the second calculation means, the third calculation means, and the quantization means.
[0037]
Therefore, the calculation error that occurs when converting the data is calculated., -1Can be reduced by the value obtained by multiplying the data, the overall operation error can be reduced, and a data compression device that improves the operation accuracy in the data conversion operation process can be provided.
[0040]
【Example】
Hereinafter, the present invention will be described with reference to the drawings.
[0041]
Explanation of principle
First, the basic concept of the present invention will be described.
[0042]
In the above-described conventional Hadamard transform-based two-dimensional data conversion operation processing, or in the conventional data compression apparatus 1 based on the DCT method shown in FIG. Since the necessary number of bits of the image data is left by performing the processing, the output result is generally smaller than the value to be originally taken, and the calculation error is increased.
[0043]
However, in the conventional data conversion operation of image data, in any of the conventional data conversion operation devices 3 shown in FIGS. 9, 11 and 12, the coefficient ROM is used in the first and second dimension conversion operations. The process of multiplying the coefficient data read from the second step is performed twice, and the basic concept of the present invention will be described below by analyzing the relationship between the coefficient multiplication process and the multiplication result.
[0044]
First, a description will be given with reference to a diagram of the operation output result shown in FIG. 10 of the related art described above. When a positive number and a negative number of the operation output result are viewed as absolute values, the positive number becomes smaller, Negative numbers increase.
[0045]
Now, assuming that the input data is a positive number, the relationship between the calculation result of the conventional two-dimensional calculation process and the absolute value is listed below.
[0046]
(First dimension)
First, in the first dimension calculation, if a coefficient is multiplied by a positive coefficient, for example, “cos 2/16”, the multiplication result is a positive number. , When viewed as an absolute value,
It will take a small value.
[0047]
(2nd dimension)
Next, in the calculation of the second dimension, if the result of the first dimension is further multiplied by a positive coefficient, the result of the multiplication is a positive number. , A value smaller than the one-dimensional multiplication result
Therefore, the error from the value to be originally taken is further increased.
[0048]
That is, in the conventional two-dimensional arithmetic processing, if the coefficients to be multiplied in the first dimension and the second dimension are both rounded down to a positive coefficient, when the results of the two arithmetic operations are viewed as absolute values, The error from is large. Therefore, the calculation result obtained by the above-described conventional two-dimensional calculation processing is described in, for example, CCITT (International Telegraph and Telephone Consultative Committee) In order to satisfy the calculation accuracy related to the image compression technique specified in H.261, it is necessary to increase the number of calculation digits and reduce the number of bits to be truncated.
[0049]
Therefore, in the present invention, when the obtained result is viewed as an absolute value in the above-described conventional first-dimensional and second-dimensional arithmetic processing,In each calculation process, multiply the conventional conversion coefficient by -1Focusing on the fact that the absolute value of the finally obtained operation result is smaller than the original value, the basic operation process will be further described.
[0050]
For example, in the above-mentioned conventional first dimension calculation process,, Multiplying the positive transform coefficient by (-1), The result of the operation is a negative number, and if the round-down process is performed on this negative number, its absolute value will take a slightly larger value.
[0051]
Next, in the above-described conventional second dimension calculation process,, The positive transform coefficient is again multiplied by (-1), The result of the operation is a positive number, and if the rounding process is performed on this positive number, the absolute value will take a slightly smaller value.
[0052]
In other words, in the first and second dimensionsBy multiplying the positive conversion coefficient by (-1)The positive and negative signs of the finally obtained calculation result are the same, and furthermore, the calculation results of the first and second dimensions cancel out the calculation errors generated in the respective calculation processes, and the overall By taking the calculation error as an absolute value, the calculation error can be reduced as compared with the related art.
[0053]
Here, a case where the basic principle of the present invention is applied to a Hadamard transform method will be described below.
[0054]
FIG. 1 is a diagram showing a calculation process of two-dimensional data composed of four elements a, b, c, and d processed by a conventional Hadamard transform method.
[0055]
Now, when one-dimensional Hadamard transform (horizontal direction) is performed on the two-dimensional data shown in FIG. 1A, an operation result shown in FIG. 1B is obtained. When (vertical direction) is applied, the calculation result shown in FIG. 1C is obtained. The above is the ordinary two-dimensional Hadamard transform processing.
[0056]
In the Hadamard transform, equations (3) and (4) are obtained for two inputs x and y.
[0057]
(Equation 3)

[0058]
(Equation 4)

The Hadamard operation of FIGS. 1A to 1C has been described in the principle description.(-1)The calculation process in the case of multiplying by is described with reference to FIG.
[0059]
FIG. 2 shows the above equations (3) and (4).Multiply (-1)Equations (5) and (6) are obtained.
[0060]
(Equation 5)

[0061]
(Equation 6)

That is, FIG. 2B is obtained by multiplying the value of FIG. 1B by (−1), and FIG. 2C is obtained by multiplying the value of FIG. 1C by (−1). Is, that is, each one-dimensional Hadamard transform is multipliedvalue is, (−1) × (−1) = 1, it can be seen that the operation result finally obtained does not change.
[0062]
Further, an example in which these relationships are applied to a general expression will be described using a data conversion operation expression (7) below.
[0063]
(Equation 7)

This equation (7) is a one-dimensional operation equation, and it is assumed that there is no operation error in multiplication and addition. However, actually, an error occurs when the coefficient ai is represented by a finite number of bits. Sometimes. When the truncation processing by the barrel shifter is performed on Expression (7), “−Δi” is output as a first-dimensional calculation error as shown in Expression (8).
[0064]
(Equation 8)

That is, the result obtained by subtracting Expression (7) from Expression (8) is a general expression of the actual operation error after the first-dimensional operation shown in Expression (9).
[0065]
(Equation 9)

Further, when the expression (8) is subjected to the second-dimensional arithmetic processing and truncated, the term “−Δj” is output as the second-dimensional arithmetic error, as shown in the expression (10). You.
[0066]
(Equation 10)

The above is the general expression of the two-dimensional arithmetic processing similar to the conventional one. That is, the result obtained by subtracting Expression (7) from Expression (10) is a general expression of the actual operation error after the second-dimensional operation shown in Expression (11).
[0067]
(Equation 11)

Here, for example, assuming that the coefficients are all positive numbers as in Equation (3) shown in the above Hadamard transform, each term of Equation (11) is represented by “−Δi” and “−Δj”. As shown in FIG. 10, the value of the calculation error is generally smaller than the original value, and a large error occurs.
[0068]
In the present invention, the coefficient “aj” in the equation (11) isMultiply (-1)And represented by equation (12).
[0069]
(Equation 12)

When errors are similarly considered for each term of the equation (12), the first term in Σ is a positive number and the second term is a negative number, and the calculation error of each term is taken as an absolute value as described above. And the error can be offset each other, and the error can be made smaller than in the equation (11), and the data conversion operation can be performed while improving the calculation accuracy.
[0070]
In the example of the above equation (12),Multiply the conversion coefficient by (-1),The error is reduced by the two-dimensional conversion operation. However, if the coefficient is a negative number, the operation error may be rather increased.
[0071]
Therefore, a value obtained by multiplying the value of the original coefficient by (-1) is stored in advance in a coefficient ROM or the like. For example, with respect to equation (13), even-numbered terms (αi, bi = 2m) The original coefficients are multiplied to obtain "αi = 1" and "bi = ai". For the odd-numbered terms (αi, bi = 2m + 1), the coefficients multiplied by (-1) are used as "αi =- 1 "and" bi = -ai ", and the value obtained by multiplying (-1) by the adder / subtractor is corrected.
[0072]
(Equation 13)

The result of multiplying the even term of this equation (13) by the original transform coefficient and the odd term by the original transform coefficient by (−1) is, Equation (14).
[0073]
[Equation 14]

When the error is similarly considered for each term of the equation (14), the first term in Σ is a negative number and the second term is a positive number, and the calculation error of each term is taken as an absolute value as described above. And the error can be offset each other, and the error can be made smaller than in the above equation (11), and it is possible to cope with the case where all the coefficients are negative numbers. In addition to the two-dimensional conversion operation, the operation accuracy can be improved by applying the basic principle of the present invention to one-dimensional operation.
[0074]
First embodiment
Hereinafter, embodiments will be described based on the basic concept of the present invention.
[0075]
FIGS. 3 and 4 are diagrams showing a first embodiment of the data compression apparatus according to the present invention, and are examples applied to a data compression apparatus based on the DCT transform method.
[0076]
First, the configuration will be described. FIG. 3 is a block diagram of the data compression device 20. In FIG. 1, a data compression device 20 includes a data storage device 21 for storing image data to be compressed in units of one frame, and a DCT operation process for image data in units of one frame read from the data storage device 21. As shown in FIG. 7, for example, image data is subjected to two-dimensional vertical and horizontal (in no particular order) extraction processing of a specific frequency component in units of 8 × 8 pixels.Perform the multiplication process described laterThe data after the data conversion calculation stored in the data conversion calculation device 22 and the data storage device 20 is divided by a value of a quantization table as shown in FIG. 8 (or multiplication of a reciprocal number). Thus, a quantization device 23 that performs a quantization operation and a control device 24 that controls the operation of each unit and controls the entire data compression device 20.
[0077]
As shown in FIG. 4, the data conversion operation device 22 includes a coefficient ROM 31 storing coefficient data to be multiplied by the multiplier 33 with the image data, and the multiplier 33 multiplying the image data.Numeric data, A coefficient read from the coefficient ROM 31 and a coefficient read from the complement ROM 32 for the image data input from the data storage device 21.NumberAnd a barrel shifter 34 that outputs the multiplied data input from the multiplier 33 to the required number of bits, shifts right (rounds down), and outputs the data to the adder / subtractor 35. , An adder / subtractor 35 for calculating the sum (difference) of the value input from the barrel shifter 34 and the previous value.
[0078]
That is, the complement ROM 32 of the data conversion operation device 22 is stored in the coefficient ROM 31.Numeric data to multiply the coefficient dataIs stored in advance, and when performing a two-dimensional conversion operation on the image data input from the data storage device 21, the multiplier 33 stores coefficient data necessary for multiplication in the first dimension and the second dimension in the coefficient ROM 31. And multiply, and if necessary, the coefficient dataNumeric data to multiply byIs read from the complement ROM 32 and multiplied. This is to reduce the error of the two-dimensional calculation result which is truncated by the barrel shifter 34 and finally output by the adder / subtractor 35, as described in the above basic principle.
[0079]
Next, the operation of this embodiment will be described.
[0080]
First, it is assumed that the data storage device 21 holds the data of the original image. The data conversion operation device 22 reads image data from the data storage device 21 and performs a DCT operation. The output of the DCT operation is sent to the quantization device 23. Further, the quantization device 23 performs a quantization operation on the input from the data conversion operation device 22 according to a value of a predetermined quantization table.
[0081]
At this time, it is assumed that the data conversion operation device 22 of this embodiment performs, for example, a two-dimensional conversion operation of the DCT method on the image data of the quartic matrix shown in Expression (15).
[0082]
(Equation 15)

The calculation process in the data conversion calculation device 22 will be described with reference to the general formulas (7) to (12) described on the basic principle.
[0083]
First, the image data of the equation (15) is subjected to a first-dimensional conversion operation, and the coefficient read from the coefficient ROM 31 is multiplied by the multiplier 33 to obtain the equation (16) corresponding to the general equation (7). Are output as the calculation results.
[0084]
(Equation 16)

When the barrel shifter 34 performs a truncation process on the equation (16), the value shown in the equation (17) corresponding to the general equation (8) is output as a calculation result.
[0085]
[Equation 17]

At this time, as shown in Expression (17), “−Δ00, −Δ01, −Δ02, −Δ03” is output as a first-dimensional calculation error in each term.
[0086]
That is, the result obtained by subtracting the expression (16) from the expression (17) is output as a negative value after the first-dimensional operation shown in the expression (18).
[0087]
(Equation 18)

Further, when the coefficient read out from the coefficient ROM 31 by performing the second-dimensional conversion operation on the equation (17) is multiplied by the multiplier 33, the negative equation shown in the equation (19) corresponding to the general equation (10) is obtained. Is output as the calculation result.
[0088]
[Equation 19]

When the truncation process is performed on the expression (19) by the barrel shifter 34, the value shown in the expression (20) corresponding to the general expression (11) is output as a calculation result.
[0089]
(Equation 20)

At this time, as shown in Expression (20), in addition to the operation error shown in Expression (18), a second-dimensional operation error of a negative value is output to each term, and the operation is shifted to a negative value as a whole. This is an error, and the error from the value to be originally taken is large. That is, since the COS coefficients of each term of the equation (20) are all positive numbers, each term takes a negative value of “−Δij” (i = 0, 1, j = 0 to 9). Therefore, similarly to the above-described diagram showing the calculation error shown in FIG. 10, the value is generally smaller than the value originally to be taken, and a large error occurs. The above is the calculation process of the two-dimensional conversion calculation process by the conventional DCT method.
[0090]
In the present embodiment, the coefficient of each term of the equation (20) is read from the complement ROM 32.Numeric dataWhen (−1) is multiplied by the multiplier 33, the operation result shown in the equation (21) corresponding to the general equation (12) is output.
[0091]
(Equation 21)

Thus, the coefficient(-1)Is multiplied by each other, the positive value and the negative value cancel each other out, so that the overall calculation error can be reduced as compared with the equation (20).
[0092]
Therefore, in the two-dimensional transform operation of the image data by the DCT method according to the present embodiment, the coefficients of each term are stored in the complement ROM in advance.Numerical value (-1), The negative calculation error generated in the first dimension and the second dimension can be canceled out as a positive calculation error to reduce the overall calculation error, and the calculation accuracy of the two-dimensional conversion calculation process can be reduced. Can be improved.
[0093]
Therefore, in comparison with the case where the barrel shifter 8 performs the right shift (round down) processing as in the conventional data conversion operation device 3 shown in FIG. The calculation can be performed such that the calculation error with the value to be originally taken becomes smaller.
[0094]
Further, as compared with the case where the incrementer 10 is added and the round-off processing is performed as in the above-described conventional data conversion operation device 3 shown in FIG. 11, the data of the present embodiment has the same circuit configuration as that of FIG. The compression device 20 can be realized, and the calculation accuracy can be improved at low cost without increasing the circuit scale.
[0095]
Further, when the barrel shifter 8 and the adder / subtractor 9 are connected by the bus 12 as in the conventional data conversion operation device 3 shown in FIG. 12, and the adder / subtractor 9 performs rounding processing by switching the bus between the barrel shifter 8 and the adder / subtractor 9. In comparison, the data compression device 20 according to the present embodiment can improve the calculation accuracy without prolonging the calculation time. In the above embodiment, the complement ROM is provided separately. However, the complement ROM may be stored in a free area of the conventional coefficient ROM. In practice, the change and processing of the coefficient data to be stored can be performed without adding a hardware configuration. The present embodiment can be realized at low cost only by changing the program or the like.
[0096]
Second embodiment
Further, in the first embodiment, the case where the present invention is applied to the DCT method as the two-dimensional conversion operation processing of image data has been described. That is, in the case of performing multiplication, truncation, and addition / subtraction processing twice,Multiplication processing of the present inventionIs effective, but when data having a strong correlation exists adjacent to each other, even if the data is sequentially subjected to one-dimensional conversion operation processing,Multiplication processing of the present inventionIs valid. In other words, this is a case where the two-dimensional image data is divided into odd lines and even lines, and one-dimensional conversion operation is performed for each line, or one-dimensional conversion operation is performed for each pixel data.
[0097]
An example in which the data compression device of the present invention is applied to one-dimensional conversion operation processing on such adjacent data having a strong correlation will be described below as a second embodiment.
[0098]
FIG. 5 is a diagram showing a second embodiment of the data compression apparatus according to the present invention, which is an example applied to a data compression apparatus based on the DCT transform method. FIG. 5 is a block diagram of the data conversion operation device in the data compression device. The overall block configuration of the data compression apparatus of this embodiment is the same as that of the data compression apparatus of the first embodiment shown in FIG.
[0099]
In FIG. 5, a data conversion operation device 40 includes a coefficient ROM 41 that stores coefficient data that the multiplier 43 multiplies with image data, and a multiplier 43 that multiplies the image data.Numeric dataROM 42 for storing image data or pixel data for each line input from the data storage device 21. The coefficient read from the coefficient ROM 41 and the coefficient read from the complement ROM 42 for each line data or pixel data.NumberAnd a barrel shifter 44 that outputs the data after multiplication input from the multiplier 43 to the required number of bits, shifts right (rounds down), and outputs the data to the adder / subtractor 45. , An adder / subtractor 45 for calculating the sum (difference) of the value input from the barrel shifter 44 and the previous value.
[0100]
That is, the complement ROM 42 of the data conversion operation device 40 is stored in the coefficient ROM 41.Numeric data to multiply the coefficient dataThe multiplier 43 reads coefficient data necessary for multiplication from the coefficient ROM 41 when performing a one-dimensional conversion operation on image data or pixel data for each line input from the data storage device 21. And multiply byNumeric data to multiply the coefficient dataIs read from the complement ROM 42 and multiplied. This is to reduce the error of the one-dimensional calculation result which is truncated by the barrel shifter 44 and output by the adder / subtractor 45, as described in the above basic principle.
[0101]
Next, the operation of this embodiment will be described.
[0102]
First, it is assumed that the data storage device 21 holds the data of the original image. The data conversion operation device 40 reads image data or pixel data for each line from the data storage device 21 and performs a DCT operation. The output of the DCT operation is sent to the quantization device 23. Further, the quantization device 23 performs a quantization operation on the input from the data conversion operation device 22 according to a value of a predetermined quantization table. At this time, it is assumed that the data conversion operation device 40 of the present embodiment performs, for example, the one-dimensional conversion operation of the DCT method on the image data of the quaternary matrix shown in the above equation (15). The calculation process in the data conversion calculation device 40 will be described with reference to the general formula (13) described in the above basic principle.
[0103]
First, when the coefficient read out from the coefficient ROM 41 and the complement ROM 42 are multiplied by the multiplier 43 by performing a one-dimensional conversion operation on the image data of the equation (15), the equation (13) corresponding to the general equation (13) is obtained. The value shown in 22) is output as the calculation result.
[0104]
(Equation 22)

In this equation (22), the first and third items are multiplied by ordinary coefficients, and the second and fourth items are multiplied by a normal coefficient.Multiply coefficient by (-1)are doing. That is, since all the coefficients of each term are positive numbers, odd-numbered terms are multiplied only by coefficients, and even-numbered terms are multiplied.Multiply coefficient by (-1)By doing so, the operation error of the odd-numbered term is reduced as a positive number, the calculation error of the even-numbered term is increased as a negative number, and the odd-numbered term and the even-numbered term cancel out the calculation error.
[0105]
Therefore, even if the coefficients of all the terms have the same sign in the one-dimensional conversion operation, they are converted to odd or even terms.Multiply (-1)By doing so, it is possible to obtain a calculation result such that calculation errors generated in odd and even terms cancel each other out, and it is possible to reduce the total calculation error.
[0106]
Therefore, in the first embodiment, all the coefficients to be multiplied in the two-dimensional conversion operation areMultiply by -1 for positive numbersAlthough the case has been described, when the coefficient is a negative number, the calculation error may be rather large (however, even in this case, the calculation error does not exceed the calculation error generated in the above-described conventional data compression apparatus). ), But in the second embodiment, only the odd or even term is used for the coefficient of each term.Multiply (-1)Therefore, the calculation error between the odd term and the even term can be reduced, and the entire calculation error can be reliably reduced.
[0107]
As a result, even in the one-dimensional conversion operation processing, the operation error can be made smaller than before, and the calculation accuracy in the one-dimensional conversion operation processing can be improved. Further, in this embodiment, a complement ROM is separately provided as in the first embodiment. However, the complement ROM may be stored in a free area of the conventional coefficient ROM, and without actually adding a hardware configuration. The present embodiment can be realized at low cost only by changing the stored coefficient data and changing the processing program and the like.
[0108]
Further, the present embodiment can be applied to data other than image data as long as the data has high correlation. For example, the present embodiment can be applied to a case where data is divided into odd blocks and even blocks. is there.
[0109]
In each of the above embodiments, the case where the present invention is applied to a DCT data compression apparatus has been described. However, the present invention is not limited to this DCT method, and can be applied to any apparatus that performs data compression. Needless to say. For example, the present invention can be applied to a data compression apparatus conforming to JPEG (Joint Photographic Expert Group) or MPEG (Motion Picture Image Coding Experts Group).
[0111]
In this embodiment, the DCT is applied to the data transform operation device. However, it is needless to say that the present invention is not limited to these encoding methods and can be applied to any device that performs the encoding operation. . For example, the present invention can be applied to a data compression / decompression device using a Harr transform, a gradient transform (slant transform), a symmetric sine transform, or the like.
[0112]
Any type of data conversion may be used as long as it performs data conversion on input data. In addition to frequency component conversion by DCT, orthogonal data such as FFT and LOT (Lapped Orthogonal Transform) are used. Applicable to conversion.
[0113]
【The invention's effect】
According to the present invention, the data output from the data storage means is subjected to a two-dimensional data conversion operation by the data conversion operation means by transform coding, orthogonal transform or frequency transform based on a predetermined transform coefficient. In the conversion operation,Since the input data is multiplied by the conversion coefficient and −1, it is possible to reduce the overall calculation error by canceling the calculation error generated when converting the data by the value multiplied by −1. The calculation accuracy in the data conversion calculation process can be improved.
[Brief description of the drawings]
FIG. 1 is a diagram showing an operation process of two-dimensional data processed by a conventional Hadamard transform method in explanation of a basic principle of the present invention.
FIG. 2 is a diagram showing a process of calculating two-dimensional data processed by the Hadamard transform method of the present invention in the explanation of the basic principle of the present invention.
FIG. 3 is a block diagram of a data compression apparatus according to a first embodiment to which the present invention is applied.
FIG. 4 is a block diagram of the data conversion operation device of FIG. 3;
FIG. 5 is a block diagram illustrating a data conversion operation device according to a second embodiment of the present invention;
FIG. 6 is a block diagram of a conventional data compression device.
FIG. 7 is a diagram showing a configuration of image data processed by the data compression device of FIG. 6;
FIG. 8 is a diagram showing a configuration of a quantization table used by the quantization device in FIG. 6;
FIG. 9 is a block diagram of the data conversion operation device of FIG. 6;
FIG. 10 is a diagram for explaining a calculation result output by the data conversion calculation device of FIG. 9;
FIG. 11 is a block diagram of another conventional data conversion operation device.
FIG. 12 is a block diagram of another conventional data conversion operation device.
[Explanation of symbols]
20 Data compression device
21 Data storage device
22 Data conversion operation device
23 Quantizer
24 Control device
31, 41 coefficient ROM
32, 42's complement ROM
33, 43 Multiplier
34, 44 barrel shifter
35, 45 Adder / subtractor

Claims

A first step of storing predetermined data;
The first-dimensional data conversion operation is performed by multiplying the data output in the first step by a predetermined conversion coefficient and -1 and discarding a predetermined number of lower bits. A second step;
By performing a process of multiplying the data subjected to the first-dimensional data conversion operation in the second step by a predetermined conversion coefficient and −1 and discarding a predetermined number of lower bits, a two- dimensional process is performed. A third step of performing an eye data conversion operation;
A fourth step of performing a quantization operation on the data after the data conversion in the second and third steps;
A data compression method comprising:

A first step of storing data composed of two correlated data ;
A second step of multiplying one of the two correlated data by a predetermined conversion coefficient and performing a data conversion operation of truncating lower-order bits of a predetermined number of bits;
A third step of multiplying the other of the two correlated data by a predetermined conversion coefficient and −1, and performing a data conversion operation of truncating lower bits of a predetermined number of bits;
A fourth step of subtracting the data obtained by the data conversion operation in the third step from the data obtained by the data conversion operation in the second step;
A fifth step of performing a quantization operation on the data after the subtraction processing in the fourth step;
A data compression method comprising :

Data storage means for storing predetermined data;
By performing a process of multiplying the data output from the data storage unit by a predetermined conversion coefficient and −1 and discarding a predetermined number of lower bits, a first-dimensional data conversion operation is performed. 1 arithmetic means;
By performing a process of multiplying the data on which the first-dimensional data conversion operation has been performed by the first operation means by a predetermined conversion coefficient by −1 and truncating lower-order bits of a predetermined number of bits, Second arithmetic means for performing a data conversion operation of the dimension ,
Quantization means for performing a quantization operation on the data after the first-dimensional and second-dimensional data conversion by the first arithmetic means and the second arithmetic means ;
Control means for controlling the data storage means, the first calculation means, the second calculation means, and the quantization means;
A data compression device comprising:

Data storage means for storing data composed of two correlated data;
First arithmetic means for performing a data conversion operation of multiplying one of the two correlated data by a predetermined conversion coefficient and discarding a predetermined number of lower bits,
A second operation unit for performing a data conversion operation of multiplying the other of the two correlated data by a predetermined conversion coefficient and −1 and discarding a predetermined number of lower bits,
A third operation unit for subtracting data obtained by the data conversion operation by the second operation unit from data obtained by the data conversion operation by the first operation unit;
Quantization means for performing a quantization operation on the data after the subtraction processing by the third operation means ,
Control means for controlling the data storage means, the first calculation means, the second calculation means, the third calculation means, and the quantization means;
Data compression apparatus comprising: a.