(57)【特許請求の範囲】
【請求項１】
２次元の入力値である（ｘ，ｙ）の所定値に対して予め割当てられたハフマン符号語を生成するハフマン符号化装置であって、
前記２次元入力値を１次元のテーブルに対応させる為のアドレス情報に変換する変換手段を有し、
前記変換手段は、前記２次元の入力値（ｘ、ｙ）のｘ又はｙのどちらか一方の値から１次元のテーブルに対応させる為のアドレスのオフセット値を算出するオフセット算出手段と、前記オフセット算出手段で算出されたオフセット値に前記ｘ又はｙの他方の値を加算する加算手段を含み、
前記加算手段を含む変換手段の出力をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第１のハフマン符号化テーブルを有し、
さらに、前記ｘ又はｙのどちらか一方だけの値をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第２のハフマン符号化テーブルを有し、
前記ハフマン符号語は、前記２次元（ｘ，ｙ）の入力値に応じて、１つの符号語として出力する場合と複数の符号語に分割して符号化を行う場合を有し、
前記１つの符号語として出力する場合は、前記第１のハフマン符号化テーブルを用いて出力し、
前記複数の符号語に分割して符号化する場合は、前記第１のハフマン符号化テーブルと前記第２のハフマン符号化テーブルを用いて出力することを特徴とするハフマン符号化装置。
【請求項２】
２次元の入力値である（ｘ，ｙ）の所定値に対して予め割当てられたハフマン符号語を生成するハフマン符号化方法であって、
前記２次元入力値を１次元のテーブルに対応させる為のアドレス情報に変換する変換工程を有し、
前記変換工程は、前記２次元の入力値（ｘ、ｙ）のｘ又はｙのどちらか一方の値から一次元のテーブルに対応させる為のアドレスのオフセット値を算出するオフセット算出工程と、前記オフセット算出工程で算出されたオフセット値に前記ｘ又はｙの他方の値を加算する加算工程を含み、
前記加算工程を含む変換工程の出力をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第１のハフマン符号化テーブルを有し、
さらに、前記ｘ又はｙのどちらか一方だけの値をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第２のハフマン符号化テーブルを有し、
前記ハフマン符号語は、前記２次元の入力値に応じて、１つの符号語として出力する場合と複数の符号語に分割して符号化を行う場合を有し、
前記１つの符号語として出力する場合は、前記第１のハフマン符号化テーブルを用いて出力し、
前記複数の符号語に分割して符号化する場合は、前記第１のハフマン符号化テーブルと前記第２のハフマン符号化テーブルを用いて出力することを特徴とするハフマン符号化方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、２次元の入力値をハフマン符号化するハフマン符号化装置及び方法に関する。
【０００２】
【従来の技術】
従来、画像データを圧縮してデータ量を減らす方法として、２次元ハフマン符号化法がある。
２次元ハフマン符号化法は、２次元の値（ｘ，ｙ）に対し発生確率の高いものに短い符号語を、発生確率の低いものに長い符号語を与えることにより、データ量を減らすものである。ここでは、２次元ハフマン符号化を行う２次元の値（ｘ，ｙ）においては、ｘ≧０，ｙ＞０としｘ，ｙそれぞれ小さい値の方が２次元の値（ｘ，ｙ）の発生確率が高くなるような前処理がされているものとする。
【０００３】
この２次元ハフマン符号化法は従来、テーブルを用いて２次元の値（ｘ，ｙ）を符号語に変換するようにしている。ｘ，ｙの最大値をそれぞれＸｍａｘ，Ｙｍａｘ、符号語長の最大値をＬｍａｘとすると必要なテーブル容量は
（Ｘｍａｘ＋１）×Ｙｍａｘ×Ｌｍａｘ
となる。
【０００４】
しかしながら、２次元の値全てに符号語を割り当てると、符号語長が非常に長くなったり、テーブル容量が非常に大きくなり様々な面で不都合が生じる。そこで従来、符号語長の長いものを２つの符号語に分割しＬｍａｘを小さくすることで、テーブル容量を小さくする手法が考えられている。例えば、符号語長をＬ′（Ｌ′＜Ｌｍａｘ）以下になるようにすればテーブル容量は、おおよそＬ′／Ｌｍａｘに減らすことができる。
【０００５】
以下、その手法について説明する。２次元の値（ｘ，ｙ）の変数ｘ，ｙの意味によって様々な方法が考えられるが、ここでは２つの符号語に分割する方法を
（ｘ，ｙ）の符号語＝（ｘ−１，０）の符号語＋（０，ｙ）の符号語
とする。この２次元ハフマン符号化を行うテーブルの様子を図２に示す。この図２は２次元の入力値（ｘ，ｙ）に対応していて図中ではハフマン符号語が割り当てられた部分のみを表わしており、例えば
ｘ＝０  のとき  ０＜ｙ≦Ｙｍａｘ
ｘ＝１  のとき  ０＜ｙ≦Ｎ２
ｘ＝２  のとき  ０＜ｙ≦Ｎ３
ｘ＝ｉ  のとき  ０＜ｙ≦Ｎ（ｉ＋１）
にハフマン符号語が割り当てられていることになる。
【０００６】
図６は図２の２次元ハフマン符号化テーブルを使用した従来の２次元ハフマン符号化装置である。図中１０１は２次元ハフマン符号化を行う２次元の入力値（ｘ，ｙ）のｘ入力端子、１０２は２次元ハフマン符号化を行う２次元の入力値（ｘ，ｙ）のｙ入力端子、１０３は２つの符号語に分割する場合かどうかを判定するテーブルを有し、その判定結果によって２次元の入力値（ｘ，ｙ）を変換する変換回路、１０４は図の２次元ハフマン符号化テーブル、１０５はこの２次元ハフマン符号化装置１０４から出力されるハフマン符号語である。
【０００７】
上記構成において以下順に動作を説明する。まず、２つの符号語に分割しない場合、変換回路１０３では２次元の入力値（ｘ，ｙ）に対しては何も処理することなく、（ｘ，ｙ）を２次元ハフマン符号化テーブル１０４へ出力する。２次元ハフマン符号化テーブル１０４ではその（ｘ，ｙ）に対するハフマン符号語１０５を出力する。
【０００８】
次に２つの符号語に分割する場合は、変換回路１０３では２次元の入力値（ｘ，ｙ）に対して、まず（ｘ−１，０）を出力しそれに対するハフマン符号語１０５が２次元ハフマン符号化テーブル１０４から出力される。その後変換回路１０３から（０，ｙ）を出力し、それに対するハフマン符号語１０５が２次元ハフマン符号化テーブル１０４から出力される。
【０００９】
【発明が解決しようとする課題】
しかしながら、上記従来の２次元ハフマン符号化装置においては、
（Ｘｍａｘ＋１）×（Ｙｍａｘ＋１）
のアドレスをもつ２次元ハフマン符号化テーブル１０４と、２つの符号語に分割するかどうかを判定するための変換回路１０３内のテーブルとが必要となるが、特に２次元ハフマン符号化テーブル１０４では実際にハフマン符号語が割り当てられていない部分は使用されないため無駄があるという欠点があった。また、通常
（Ｘｍａｘ＋１）×（Ｙｍａｘ＋１）
は非常に大きな値となり、上記２つのテーブルが大容量になるという欠点もあった。
【００１０】
そこで、本発明は各種テーブルを効率良く使うと同時に、テーブル容量をできるだけ小さくすることが可能になるハフマン符号化装置及び方法を得ることを目的とする。
【００１１】
【課題を解決するための手段】
本発明のハフマン符号化装置は、２次元の入力値である（ｘ，ｙ）の所定値に対して予め割当てられたハフマン符号語を生成するハフマン符号化装置であって、前記２次元入力値を１次元のテーブルに対応させる為のアドレス情報に変換する変換手段を有し、前記変換手段は、前記２次元の入力値（ｘ、ｙ）のｘ又はｙのどちらか一方の値から１次元のテーブルに対応させる為のアドレスのオフセット値を算出するオフセット算出手段と、前記オフセット算出手段で算出されたオフセット値に前記ｘ又はｙの他方の値を加算する加算手段を含み、前記加算手段を含む変換手段の出力をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第１のハフマン符号化テーブルを有し、さらに、前記ｘ又はｙのどちらか一方だけの値をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第２のハフマン符号化テーブルを有し、前記ハフマン符号語は、前記２次元（ｘ，ｙ）の入力値に応じて、１つの符号語として出力する場合と複数の符号語に分割して符号化を行う場合を有し、前記１つの符号語として出力する場合は、前記第１のハフマン符号化テーブルを用いて出力し、前記複数の符号語に分割して符号化する場合は、前記第１のハフマン符号化テーブルと前記第２のハフマン符号化テーブルを用いて出力することを特徴とする。
本発明のハフマン符号化装置は、２次元の入力値である（ｘ，ｙ）の所定値に対して予め割当てられたハフマン符号語を生成するハフマン符号化方法であって、前記２次元入力値を１次元のテーブルに対応させる為のアドレス情報に変換する変換工程を有し、前記変換工程は、前記２次元の入力値（ｘ、ｙ）のｘ又はｙのどちらか一方の値から一次元のテーブルに対応させる為のアドレスのオフセット値を算出するオフセット算出工程と、前記オフセット算出工程で算出されたオフセット値に前記ｘ又はｙの他方の値を加算する加算工程を含み、前記加算工程を含む変換工程の出力をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第１のハフマン符号化テーブルを有し、さらに、前記ｘ又はｙのどちらか一方だけの値をアドレスの入力として、ハフマン符号語を出力するテーブルであって、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び替えた第２のハフマン符号化テーブルを有し、前記ハフマン符号語は、前記２次元の入力値に応じて、１つの符号語として出力する場合と複数の符号語に分割して符号化を行う場合を有し、前記１つの符号語として出力する場合は、前記第１のハフマン符号化テーブルを用いて出力し、前記複数の符号語に分割して符号化する場合は、前記第１のハフマン符号化テーブルと前記第２のハフマン符号化テーブルを用いて出力することを特徴とする。
【００１３】
【実施例】
以下、図面を用いて本発明の実施例を説明する。図１は本発明の実施例による２次元ハフマン符号化装置を示すブロック図である。
図中１は２次元ハフマン符号化を行う２次元の入力値（ｘ，ｙ）のｘ入力端子、２は２次元ハフマン符号化を行う２次元の入力値（ｘ，ｙ）のｙ入力端子、３は入力値ｘからｘ−１を計算して結果を出力４とする減算器、５は２次元の値（ｘ，０）（ｘ＝０であるため実質的には１次元）をハフマン符号に変換してハフマン符号語６を出力するテーブル手段としてのハフマン符号化テーブルＡ、７は２次元の入力値（ｘ，ｙ）のｘから２つの符号語に分割するかどうかを判定するしきい値９を出力すると共に、２次元の入力値（ｘ，ｙ）を１次元のテーブルへ対応させるためのアドレスオフセット値８を出力する入力データ変換手段としての変換テーブルである。
【００１４】
１０は変換テーブル７からのしきい値９と２次元の入力値（ｘ，ｙ）のｙとを比較し
２次元の入力値（ｘ，ｙ）のｙ＞しきい値
のとき“０”、をそうでないとき“１”の出力１１を得る比較手段としてのコンパレータ、１２はコンパレータ１０の出力１１が“０”のとき変換テーブル７からのアドレスオフセット値８を０にするアンド回路、１４はアンド回路１２を通過したアドレスオフセット値１３と２次元の入力値（ｘ，ｙ）のｙとを加算した結果を出力１５とする加算器で、アンド回路１２と共に変更手段を構成する。１６は２次元の入力値（ｘ，ｙ）（ただしｙ＞０）に対するハフマン符号化テーブルを１次元的に配列しハフマン符号語１７を出力する上記テーブル手段としてのハフマン符号化テーブルＢである。
【００１５】
１８はコンパレータ１０の出力１１が“０”のときハフマン符号語６を、コンパレータ１０の出力１１が“１”のときハフマン符号語１７の出力１９を得るスイッチ、２０はハフマン符号語１７をディレイさせて出力２１を得るディレイ回路、２２はコンパレータ１０の出力１１をディレイ回路２０と同じ時間ディレイさせて出力２７を得るディレイ回路、２６は出力２７が“１”から“０”に変化したときにディレイ回路２２の遅延時間分だけ“０”を出力２３とするエッジ検出器、２４はエッジ検出器２６の出力２３が“０”のとき出力２１としてのハフマン符号語を、エッジ検出器２６の出力２３が“１”のとき出力１９としてのハフマン符号語を出力端子２５へ出力するスイッチである。尚、スイッチ１８、２４、ディレイ回路２０、２１、エッジ検出器２６により選択手段が構成される。
【００１６】
次に上記構成において以下順に動作を説明する。
まず、図１の変換テーブル７、ハフマン符号化テーブルＡ５及びハフマン符号化テーブルＢ１６について説明する。図２は２次元ハフマン符号化するためのテーブルを示したものであり、２次元の入力値（ｘ，ｙ）に対応している。図中では前述したようにハフマン符号語が割り当てられた部分のみを表わしており、例えば
ｘ＝０  のとき  ０＜ｙ≦Ｙｍａｘ
ｘ＝１  のとき  ０＜ｙ≦Ｎ２
ｘ＝２  のとき  ０＜ｙ≦Ｎ３
ｘ＝ｉ  のとき  ０＜ｙ≦Ｎ（ｉ＋１）
にハフマン符号語が割り当てられていることになる。
【００１７】
図３はハフマン符号化テーブルＢ１６を示すもので、図２のテーブルを１次元的に並び換えたものである。ここでは２次元の値（ｘ，ｙ）に対するハフマン符号語をアドレスとして
【００１８】
【数１】
0003937463.tif 000002
【００１９】
に割り当てている。
【００２０】
図４は変換テーブル７を示すものである。これは２次元の入力値（ｘ，ｙ）のｘに対して２次元の入力値（ｘ，ｙ）を他のテーブル手段としての１次元のテーブルへ対応させるためのアドレスオフセット値８
【００２１】
【数２】
0003937463.tif 000003
【００２２】
を出力すると共に、２次元の入力値（ｘ，ｙ）のｘから２つの符号語に分割するかどうかを判定するしきい値９
Ｎx+1   ただしＮ０＝０，Ｎ１＝Ｙｍａｘ，ｘ≧０
を出力する演算手段を設けた変換テーブルである。
【００２３】
図５は２つの符号語に分割する場合の２次元の入力値（ｘ，ｙ）に対する（ｘ，０）の部分のテーブルであり（ｘ，０）符号語をアドレスとしてｘに割り当てている。
【００２４】
まず、２つの符号語に分割しない場合の２次元の入力値（ｘ，ｙ）（ただしｘ≧０，ｙ＞０）について説明する。２次元の入力値（ｘ，ｙ）はそれぞれ、ｘ入力端子１、ｙ入力端子２へ入力される。ｘは変換テーブル７へ入力され、上記で説明したアドレスオフセット値８と２つの符号語に分割するかどうかを判定するしきい値９とを出力する。２つの符号語に分割しない場合は、
しきい値≧ｙ
であるため、コンパレータ１０からは“１”の出力１１が得られ、アンド回路１２の出力１３はアドレスオフセット値８となる。従って加算器１４では
アドレスオフセット値＋ｙ
が計算され出力１５を得る。
【００２５】
このときの出力１５は
【００２６】
【数３】
0003937463.tif 000004
【００２７】
となる。この値がハフマン符号化テーブルＢ１６に入力されると、２次元の入力値（ｘ，ｙ）のハフマン符号語１７が出力される。このときコンパレータ１０の出力１１は“１”になっているためスイッチ１８はハフマン符号語１７を、スイッチ２４は出力１９を選択するので、出力端子２５に２次元の入力値（ｘ，ｙ）のハフマン符号語１７が出力される。
【００２８】
次に２つの符号語に分割する場合の２次元の入力値（ｘ，ｙ）（ただしｘ≧０，ｙ＞０）について説明する。２次元の入力値（ｘ，ｙ）はそれぞれ、ｘ入力端子１、ｙ入力端子２へ入力される。ｘは変換テーブル７へ入力され、上記で説明したアドレスオフセット値８と、２つの符号語に分割するかどうかを判定するしきい値９とを出力する。２つの符号語に分割する場合は、
しきい値＜ｙ
であるためコンパレータ１０からは“０”の出力１１が得られることになる。従って、アドレスオフセット値８はアンド回路１２で“０”にクリアされ、加算器１４の出力１５はｙとなる。この値がハフマン符号化テーブルＢ１６に入力されると２次元の入力値（ｘ，ｙ）に対して（０，ｙ）のハフマン符号語１７が出力される。
【００２９】
一方、減算器３へ入力されたｘは演算されてｘ−１の出力４が得られ、ハフマン符号化テーブルＡ５からは（ｘ−１，０）のハフマン符号語６が出力される。このときコンパレータ１０の出力１１は“０”となったため、スイッチ１８はハフマン符号語６を選択する。スイッチ２４は始め出力１９としてハフマン符号語６を選択する。次に出力１１がディレイ回路２２で遅延されエッジ検出器２６の出力２３が“０”になると、スイッチ２４は出力２１としてのハフマン符号語１７を選択する。すなわち、始め（ｘ−１，０）のハフマン符号語６が出力され、後に（０，ｙ）のハフマン符号語１７が出力されることになる。
【００３０】
以上のように本実施例によれば、２次元ハフマン符号化テーブルのコードを割り当てられていない部分を削除して並び変えたテーブルと、２次元の入力値（ｘ，ｙ）を上記テーブルに対応するように変換するように構成したことにより、テーブル容量を従来に比べ小さくすることができ、効率の良い２次元ハフマン符号化テーブルが実現できる。
【００３１】
尚、本実施例では２次元ハフマン符号化装置について述べたが本発明は、２次元ハフマン符号化に限らず他の符号化方式にもハフマン符号化と同様に実施することが可能である。
【００３２】
【発明の効果】
以上説明したように、本発明によればテーブル容量を従来に比べ大幅に小さくすることが可能になり、効率の良い符号化テーブルを実現できる効果がある。
【図面の簡単な説明】
【図１】本発明の実施例による２次元ハフマン符号化装置の動作を示すブロック図である。
【図２】２次元ハフマン符号化テーブルの構成を示す構成図である。
【図３】本発明による２次元ハフマン符号化テーブルの構成を示す構成図である。
【図４】本発明による２次元ハフマン符号化テーブルを使うための変換テーブルの構成を示す構成図である。
【図５】本発明による２次元ハフマン符号化テーブルの構成を示す構成図である。
【図６】従来の２次元ハフマン符号化装置を示すブロック図である。
【符号の説明】
５  ハフマン符号化テーブルＡ
７  変換テーブル
１０  コンパレータ
１２  アンド回路
１４  加算器
１６  ハフマン符号化テーブルＢ
１８  スイッチ
２４  スイッチ
２０  ディレイ回路
２２  ディレイ回路
２６  エッジ検出器
【図１】
0003937463.tif 000005
【図２】
0003937463.tif 000006
【図３】
0003937463.tif 000007
【図４】
0003937463.tif 000008
【図５】
0003937463.tif 000009
【図６】
0003937463.tif 000010