(57)【要約】分割ユニット（２）は、ジグザグスキャン／ランレングス処理まで終了した入力データの各記号列を出現頻度の違いによって出現頻度が類似した複数の部分集合に分割する。そして、テーブル作成ユニット（３）は、各部分集合を走査して各部分集合に対してハフマン符号化テーブルを作成する。符号化ユニット（４）は、各部分集合をその部分集合に対して作成されたハフマン符号化テーブルを用いてハフマン符号化する処理を複数の部分集合の全ての部分集合について実行する。
2010013290.tif 000002
【特許請求の範囲】
【請求項１】
入力データを圧縮して圧縮データを出力する圧縮処理装置であって、
前記入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する分割ユニットと、
前記複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する符号化ユニットとを備える圧縮処理装置。
【請求項２】
１つの部分集合に含まれる符号化対象データの出現頻度を調べて前記１つの部分集合に対応するハフマン符号化テーブルを作成する処理を前記複数の部分集合の全てについて実行し、前記複数のハフマン符号化テーブルを作成するテーブル作成ユニットをさらに備える、請求の範囲第１項に記載の圧縮処理装置。
【請求項３】
前記符号化ユニットは、前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求の範囲第１項に記載の圧縮処理装置。
【請求項４】
各々が複数のハフマン符号からなる第１および第２の符号化テーブルを保持するテーブル保持ユニットと、
前記第１および第２の符号化テーブルのうち、前記入力データのハフマン符号化に用いられていない一方の符号化テーブルを前記符号化対象データの出現頻度に応じて出現頻度が最も多い符号化対象データが最も短いハフマン符号に変換されるように更新する更新ユニットとをさらに備え、
前記符号化ユニットは、前記圧縮データの圧縮率がしきい値以下であるとき、前記第１および第２の符号化テーブルのうちの他方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化し、前記圧縮率が前記しきい値よりも大きくなると、前記更新ユニットによって更新された一方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求の範囲第３項に記載の圧縮処理装置。
【請求項５】
前記更新ユニットは、全ての符号化対象データに対して出現頻度をカウントするとともに、１つの符号化対象データに対する出現頻度が最大値に達する毎に、前記出現頻度が前記最大値に達した順番が早いほど短い長さを有する新しいハフマン符号を前記１つの符号化対象データに対して割り当てる処理を前記全ての符号化対象データに対して実行し、前記一方の符号化テーブルを更新する、請求の範囲第４項に記載の圧縮処理装置。
【請求項６】
前記更新ユニットは、前記符号化ユニットから出力された圧縮データに基づいて前記圧縮率を演算するとともに、その演算した圧縮率が前記しきい値よりも大きくなったとき、または前記全ての符号化対象データに対して前記新しいハフマン符号を割り当てたとき、前記符号化テーブルを切換えるための切換信号を生成して前記符号化ユニットへ出力し、
前記符号化ユニットは、前記切換信号に応じて前記符号化テーブルを切換え、その切換え後の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求の範囲第５項に記載の圧縮処理装置。
【請求項７】
画像に含まれる対象物に基づいて前記画像を複数の画像に分割して複数の入力データを生成する画像分割ユニットをさらに備え、
前記分割ユニットは、前記複数の入力データのうちの１つの入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する処理を前記複数の入力データの全てに対して実行し、
前記符号化ユニットは、前記１つの入力データから分割された複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する処理を前記複数の入力データの全てに対して実行する、請求の範囲第１項に記載の圧縮処理装置。
【請求項８】
入力データを圧縮して圧縮データを出力する圧縮処理方法であって、
分割ユニットが、前記入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する第１のステップと、
符号化ユニットが、前記複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する第２のステップとを備える圧縮処理方法。
【請求項９】
テーブル作成ユニットが、１つの部分集合に含まれる符号化対象データの出現頻度を調べて前記１つの部分集合に対応するハフマン符号化テーブルを作成する処理を前記複数の部分集合の全てについて実行し、前記複数のハフマン符号化テーブルを作成する第３のステップをさらに備える、請求の範囲第８項に記載の圧縮処理方法。
【請求項１０】
前記第２のステップにおいて、前記符号化ユニットは、前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求項８に記載の圧縮処理方法。
【請求項１１】
更新ユニットが、各々が複数のハフマン符号からなる第１および第２の符号化テーブルのうち、前記入力データのハフマン符号化に用いられていない一方の符号化テーブルを符号化対象データの出現頻度に応じて出現頻度が最も多い符号化対象データが最も短いハフマン符号に変換されるように更新する第３のステップをさらに備え、
前記第２のステップにおいて、前記符号化ユニットは、前記圧縮データの圧縮率がしきい値以下であるとき、前記第１および第２の符号化テーブルのうちの他方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化し、前記圧縮率が前記しきい値よりも大きくなると、前記一方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求の範囲第１０項に記載の圧縮処理方法。
【請求項１２】
前記第３のステップは、
前記更新ユニットが、全ての符号化対象データに対して出現頻度をカウントする第１のサブステップと、
前記更新ユニットが、１つの符号化対象データに対する出現頻度が最大値に達する毎に、前記出現頻度が前記最大値に達した順番が早いほど短い長さを有する新しいハフマン符号を前記１つの符号化対象データに対して割り当てる処理を前記全ての符号化対象データに対して実行し、前記一方の符号化テーブルを更新する第２のサブステップとを含む、請求の範囲第１１項に記載の圧縮処理方法。
【請求項１３】
前記第３のステップは、
前記更新ユニットが、前記符号化ユニットから出力された圧縮データに基づいて前記圧縮率を演算する第３のサブステップと、
前記更新ユニットが、前記第３のサブステップにおいて演算された圧縮率が前記しきい値よりも大きくなったとき、または前記全ての符号化対象データに対して前記新しいハフマン符号を割り当てたとき、前記符号化テーブルを切換えるための切換信号を生成して前記符号化ユニットへ出力する第４のサブステップとをさらに含み、
前記第２のステップにおいて、前記符号化ユニットは、前記切換信号に応じて前記符号化テーブルを切換え、その切換え後の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求の範囲第１２項に記載の圧縮処理方法。
【請求項１４】
画像分割ユニットが、画像に含まれる対象物に基づいて前記画像を複数の画像に分割して複数の入力データを生成する第３のステップをさらに備え、
前記第１のステップにおいて、前記分割ユニットは、前記複数の入力データのうちの１つの入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する処理を前記複数の入力データの全てに対して実行し、
前記第２のステップにおいて、前記符号化ユニットは、前記１つの入力データから分割された複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する処理を前記複数の入力データの全てに対して実行する、請求の範囲第８項に記載の圧縮処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを圧縮する圧縮処理装置および圧縮処理方法に関するものである。
【背景技術】
【０００２】
従来、ハフマン符号化は、データ圧縮技術の中で最も効率のよい可逆圧縮技術の一つとして知られている（D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE, no. 40, pp. 1098-1101, Sept. 1952.）。【０００３】
一般的なハフマン符号化は、圧縮処理を行なう前に、全ての符号化対象の記号列を精査することにより、はじめに、対象データに合わせた符号化テーブルを作成し、その作成した符号化テーブルを、再び、同様の記号列に対して用いて圧縮処理を行なう。【０００４】
しかし、この方法では、圧縮を行なうためにデータを２回スキャンする必要があるため、オンラインでのリアルタイム圧縮が困難になる。また、符号化対象の記号列の種類が多く、出現頻度に偏りがある場合、圧縮率の向上が望めない場合がある。【０００５】
そこで、最近では、静的ハフマン符号化と動的（「適応型」とも言う）ハフマン符号化（D. E. Kunth, “Dynamic Huffmann coding,” J. Algorithms, vol. 6, pp. 163-180, 1985.）の２通りに分かれている。【０００６】
静的ハフマン符号化は、ソフトウェアおよびハードウェア共に、最も広く実装されている形態である。そして、静的ハフマン符号化は、符号化処理をリアルタイムに実行するために、予め数多くのサンプルデータからデータの出現頻度を調査しておき、この結果を元に作成した既存のテーブルを用意して符号化を行なうものである。【０００７】
また、動的ハフマン符号化は、従来のハフマン符号化の問題点であるオンラインでの圧縮、および静的ハフマン符号化の問題点である既存のテーブルが存在しない任意の記号列に合わせた圧縮を改善するために開発されたものである。そして、動的ハフマン符号化は、記号を処理するごとにハフマン木を更新し、その時点で構成されたツリーによって符号化を行なうものである。
【発明の開示】
【０００８】
しかし、従来の動的ハフマン符号化においては、圧縮効率およびリアルタイム性についていくつかの問題がある。すなわち、動的ハフマン符号化は、アルゴリズムの特性上、符号化データに加え、初出現の記号を符号化せずに送らなければならないため、その分、データ量が増加する。
【０００９】
また、動的ハフマン符号化においては、圧縮開始からある時間は、ハフマン木が十分なものでないため、圧縮率が低いことが多い。これは、圧縮中にデータの出現分布が変化した場合にも同様のことが言える。
【００１０】
更に、データの局所性により、集中的に出現した記号に短い符号が割り当てられたとしても、それ以降出現しない場合には、データ量が大きくなるにつれて静的ハフマン符号化よりも圧縮効率が下がる場合がある。
【００１１】
これに対しては、符号化テーブルの定期的なリフレッシュという方法が採用されることもあるが、過去のデータの生起確率を破棄することは、逆に圧縮効率を悪化させることにもなる。また、符号化の際に、その都度、ハフマン木を更新するため、処理により多くの時間を必要とする。これにより、オンラインでの処理が可能であるとしても、動的ハフマン符号化は、リアルタイム性を要するアプリケーションには向かない場合がある。
【００１２】
そこで、圧縮効率の向上が可能な圧縮処理装置を提供することが望まれる。
【００１３】
また、圧縮効率の向上が可能な圧縮処理方法を提供することが望まれる。
【００１４】
圧縮処理装置は、入力データを圧縮して圧縮データを出力する圧縮処理装置であって、分割ユニットと、符号化ユニットとを備える。分割ユニットは、入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する。符号化ユニットは、複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、圧縮データを出力する。
【００１５】
圧縮処理装置は、テーブル作成ユニットをさらに備えてもよい。テーブル作成ユニットは、１つの部分集合に含まれる符号化対象データの出現頻度を調べて１つの部分集合に対応するハフマン符号化テーブルを作成する処理を複数の部分集合の全てについて実行し、複数のハフマン符号化テーブルを作成する。
【００１６】
符号化ユニットは、複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化してもよい。
【００１７】
圧縮処理装置は、テーブル保持ユニットと、更新ユニットとをさらに備えてもよい。テーブル保持ユニットは、各々が複数のハフマン符号からなる第１および第２の符号化テーブルを保持する。更新ユニットは、第１および第２の符号化テーブルのうち、入力データのハフマン符号化に用いられていない一方の符号化テーブルを符号化対象データの出現頻度に応じて出現頻度が最も多い符号化対象データが最も短いハフマン符号に変換されるように更新する。そして、符号化ユニットは、圧縮データの圧縮率がしきい値以下であるとき、第１および第２の符号化テーブルのうちの他方の符号化テーブルに基づいて複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化し、圧縮率がしきい値よりも大きくなると、更新ユニットによって更新された一方の符号化テーブルに基づいて複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化してもよい。
【００１８】
更新ユニットは、全ての符号化対象データに対して出現頻度をカウントするとともに、１つの符号化対象データに対する出現頻度が最大値に達する毎に、出現頻度が最大値に達した順番が早いほど短い長さを有する新しいハフマン符号を１つの符号化対象データに対して割り当てる処理を全ての符号化対象データに対して実行し、一方の符号化テーブルを更新してもよい。
【００１９】
更新ユニットは、符号化ユニットから出力された圧縮データに基づいて圧縮率を演算するとともに、その演算した圧縮率がしきい値よりも大きくなったとき、または全ての符号化対象データに対して新しいハフマン符号を割り当てたとき、符号化テーブルを切換えるための切換信号を生成して符号化ユニットへ出力してもよい。符号化ユニットは、切換信号に応じて符号化テーブルを切換え、その切換え後の符号化テーブルに基づいて複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化してもよい。
【００２０】
圧縮処理装置は、画像分割ユニットをさらに備えてもよい。画像分割ユニットは、画像に含まれる対象物に基づいて画像を複数の画像に分割して複数の入力データを生成する。そして、分割ユニットは、複数の入力データのうちの１つの入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する処理を複数の入力データの全てに対して実行する。符号化ユニットは、１つの入力データから分割された複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、圧縮データを出力する処理を複数の入力データの全てに対して実行してもよい。
【００２１】
また、圧縮処理方法は、入力データを圧縮して圧縮データを出力する圧縮処理方法であって、分割ユニットが、入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する第１のステップと、符号化ユニットが、複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、圧縮データを出力する第２のステップとを備える。
【００２２】
圧縮処理方法は、テーブル作成ユニットが、１つの部分集合に含まれる符号化対象データの出現頻度を調べて１つの部分集合に対応するハフマン符号化テーブルを作成する処理を複数の部分集合の全てについて実行し、複数のハフマン符号化テーブルを作成する第３のステップをさらに備えてもよい。
【００２３】
第２のステップにおいて、符号化ユニットは、複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化してもよい。
【００２４】
圧縮処理方法は、更新ユニットが、各々が複数のハフマン符号からなる第１および第２の符号化テーブルのうち、入力データのハフマン符号化に用いられていない一方の符号化テーブルを符号化対象データの出現頻度に応じて出現頻度が最も多い符号化対象データが最も短いハフマン符号に変換されるように更新する第３のステップをさらに備え、第２のステップにおいて、符号化ユニットは、圧縮データの圧縮率がしきい値以下であるとき、第１および第２の符号化テーブルのうちの他方の符号化テーブルに基づいて複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化し、圧縮率がしきい値よりも大きくなると、一方の符号化テーブルに基づいて複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化してもよい。
【００２５】
第３のステップは、更新ユニットが、全ての符号化対象データに対して出現頻度をカウントする第１のサブステップと、更新ユニットが、１つの符号化対象データに対する出現頻度が最大値に達する毎に、出現頻度が最大値に達した順番が早いほど短い長さを有する新しいハフマン符号を１つの符号化対象データに対して割り当てる処理を全ての符号化対象データに対して実行し、一方の符号化テーブルを更新する第２のサブステップとを含んでもよい。
【００２６】
第３のステップは、更新ユニットが、符号化ユニットから出力された圧縮データに基づいて圧縮率を演算する第３のサブステップと、更新ユニットが、第３のサブステップにおいて演算された圧縮率がしきい値よりも大きくなったとき、または全ての符号化対象データに対して新しいハフマン符号を割り当てたとき、符号化テーブルを切換えるための切換信号を生成して符号化ユニットへ出力する第４のサブステップとをさらに含み、第２のステップにおいて、符号化ユニットは、切換信号に応じて符号化テーブルを切換え、その切換え後の符号化テーブルに基づいて複数のハフマン符号化テーブルを作成しながら各部分集合毎に符号化対象データをハフマン符号化してもよい。
【００２７】
圧縮処理方法は、画像分割ユニットが、画像に含まれる対象物に基づいて画像を複数の画像に分割して複数の入力データを生成する第３のステップをさらに備え、第１のステップにおいて、分割ユニットは、複数の入力データのうちの１つの入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する処理を複数の入力データの全てに対して実行し、第２のステップにおいて、符号化ユニットは、１つの入力データから分割された複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、圧縮データを出力する処理を複数の入力データの全てに対して実行してもよい。
【００２８】
圧縮処理装置または圧縮処理方法は、入力データを各記号列の出現頻度の違いによって複数の部分集合に分割し、その分割した複数の部分集合の各部分集合毎にハフマン符号化テーブルを作成し、その作成したハフマン符号化テーブルを用いて各部分集合毎にハフマン符号化を行なう。
【００２９】
その結果、従来のハフマン符号化を用いた場合よりも、各部分集合に含まれる符号化対象データに対して短いハフマン符号が割り当てられる。
【００３０】
したがって、圧縮率を向上できる。
【図面の簡単な説明】
【００３１】
【図１】この発明の実施の形態１による圧縮処理装置の構成を示す概略ブロック図である。
【図２】従来のハフマン符号化を示す概念図である。
【図３】図１に示す圧縮処理装置におけるハフマン符号化を示す概念図である。
【図４】図１に示す圧縮処理装置における画像圧縮の概念図である。
【図５】部分集合への分割の具体例を説明するための図である。
【図６】部分集合への分割の他の具体例を説明するための図である。
【図７】実施の形態１における圧縮処理方法を説明するためのフローチャートである。
【図８】実施の形態２による圧縮処理装置の概略ブロック図である。
【図９】図８に示すエンコーダおよび最適器の構成図である。
【図１０】図９に示す割当モジュールの構成図である。
【図１１】図９に示す交換モジュールの構成図である。
【図１２】図９に示す交換モジュールの他の構成図である。
【図１３】一方の符号化テーブルを用いたハフマン符号化の動作を説明するための図である。
【図１４】他方の符号化テーブルを用いたハフマン符号化の動作を説明するための図である。
【図１５】シャドウテーブルの役割を果たす符号化テーブルの更新を説明するための図である。
【図１６】図９に示すエンコーダおよび最適器における動作を説明するためのフローチャートである。
【図１７】図８に示す圧縮処理装置におけるハフマン符号化を具体的に説明するための図である。
【図１８】実施の形態２における圧縮処理方法を説明するためのフローチャートである。
【図１９】実施の形態３による圧縮処理装置の概略ブロック図である。
【図２０】画像の分割方法を説明するための図である。
【図２１】領域成長型分割分割アルゴリズムを用いた画像の分割方法を説明するためのフローチャートである。
【図２２】実施の形態３における圧縮処理方法を説明するためのフローチャートである。
【図２３】実施の形態３による圧縮処理装置の他の構成を示す概略ブロック図である。
【図２４】実施の形態３における他の圧縮処理方法を説明するためのフローチャートである。
【発明を実施するための最良の形態】
【００３２】
本発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰返さない。【００３３】
［実施の形態１］
図１は、この発明の実施の形態１による圧縮処理装置の構成を示す概略ブロック図である。図１を参照して、この発明の実施の形態１による圧縮処理装置１０は、処理部１と、分割ユニット２と、テーブル作成ユニット３と、符号化ユニット４とを備える。【００３４】
処理部１は、従来のハフマン符号を用いた圧縮方法における原画像の複数の画素への分割、ＲＧＢからＹＣｂＣｒへの変換／サンプリング、レベルシフト、離散コサイン変換、量子化、およびジグザグスキャン／ランレングス処理を行なう。そして、処理部１は、ジグザグスキャンおよびランレングス処理後のデータを入力データとして分割ユニット２へ出力する。【００３５】
分割ユニット２は、処理部１から受けた入力データを入力データに含まれる各要素の特徴（出現頻度）によって複数の部分集合に分割し、その分割した複数の部分集合をテーブル作成ユニット３および符号化ユニット４へ出力する。【００３６】
テーブル作成ユニット３は、分割ユニット２から複数の部分集合を受ける。そして、テーブル作成ユニット３は、１つの部分集合に含まれる符号化対象データの出現頻度を調査し、その調査した出現頻度に基づいて、従来のハフマン木の構築方法を用いて１つの部分集合に対するハフマン符号化テーブルを作成する。テーブル作成ユニット３は、この処理を複数の部分集合の全ての部分集合に対して実行し、複数の部分集合に対して複数のハフマン符号化テーブルを作成する。そうすると、テーブル作成ユニット３は、その作成した複数のハフマン符号化テーブルを符号化ユニット４へ出力する。【００３７】
符号化ユニット４は、分割ユニット２から複数の部分集合を受け、テーブル作成ユニット３から複数のハフマン符号化テーブルを受ける。そして、符号化ユニット４は、複数の部分集合に含まれる符号化対象データを複数のハフマン符号化テーブルを用いてハフマン符号化し、圧縮データを出力する。この場合、符号化ユニット４は、１つの部分集合に含まれる符号化対象データを１つの部分集合に対応して作成されたハフマン符号化テーブルを用いてハフマン符号化する。そして、符号化ユニット４は、この処理を複数の部分集合の全ての部分集合に対して実行し、複数の部分集合に含まれる全ての符号化対象データをハフマン符号化する。【００３８】
図２は、従来のハフマン符号化を示す概念図である。また、図３は、図１に示す圧縮処理装置１０におけるハフマン符号化を示す概念図である。図２を参照して、入力データからなる母集合Ｕは、白丸、白四角および白三角によって表される複数の要素からなり、複数の要素の全ては、部分集合Ａに属する。【００３９】
したがって、従来のハフマン符号化においては、部分集合Ａに対して１つのハフマン符号化テーブルを作成するため、要素数と、その種類が多い場合、ハフマン符号化テーブルの作成に時間を要し、圧縮効率の向上も難しくなる。【００４０】
一方、図３に示すように、この発明によるハフマン符号化では、母集合Ｕに属する複数の要素をそれぞれの特徴に分けていくつかの部分集合Ｂ，Ｃ，Ｄに分割する。そして、各部分集合Ｂ，Ｃ，Ｄごとにハフマン符号化テーブルを作成し、その作成したハフマン符号化テーブルを用いて各部分集合Ｂ，Ｃ，Ｄごとにハフマン符号化を行なう。【００４１】
このように、この発明によるハフマン符号化では、各部分集合ごとにハフマン符号化を行なうため、圧縮率を向上できる。また、部分集合ごとにハフマン符号化テーブルを作成して圧縮処理を行なうため、要素数が多い場合でも、符号後のデータを直ぐに得ることができる。【００４２】
図４は、図１に示す圧縮処理装置１０における画像圧縮の概念図である。図４を参照して、画像を圧縮する場合、圧縮処理装置１０の処理部１は、原画像を複数の要素に分割し、その分割した複数の要素ごとにＲＧＢからＹＣｂＣｒへの変換を行ない、サンプリングする。【００４３】
その後、圧縮処理装置１０の処理部１は、サンプリング結果をレベルシフトし、その後、離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）を行なう。【００４４】
引き続いて、圧縮処理装置１０の処理部１は、量子化を行ない、その量子化後のデータを原画像の左上から右下に向かってジグザクスキャンするとともに、ランレングス処理を行なう。【００４５】
その後、圧縮処理装置１０の分割ユニット２は、入力データ（「ジグザクスキャンおよびランレングス処理後のデータ」を言う。以下、同じ。）を複数の部分集合に分割し、テーブル作成ユニット３は、分割ユニット２によって分割された複数の部分集合の各々についてハフマン符号化テーブルを作成し、符号化ユニット４は、テーブル作成ユニット３によって作成された複数のハフマン符号化テーブルを用いて部分集合ごとにハフマン符号化を行ない、圧縮画像を出力する。【００４６】
したがって、「入力データを部分集合に分割」のブロックおよび「部分集合毎にハフマン符号化」のブロックが従来の画像圧縮方法と異なる点である。【００４７】
ここで、圧縮処理装置１０の分割ユニット２における入力データの複数の部分集合への分割方法について説明する。たとえば、入力データが「ＡＴＡＡＣＣＣＣＧＧ」の記号列からなる場合、分割ユニット２は、各記号の出現頻度の違いによって、「ＡＴＡＡＣＣＣＣＧＧ」の記号列を「ＡＴＡＡ」の記号列と、「ＣＣＣＣＧＧ」の記号列とに分割する。【００４８】
ジグザクスキャンおよびランレングス処理が行なわれた後のデータは、「ＡＴＡＡ」の記号列および「ＣＣＣＣＧＧ」の記号列のように類似した記号列が配列された部分が分散的に配置されている。したがって、分割ユニット２は、ジグザクスキャンおよびランレングス処理が行なわれた後の記号列を参照して、類似した記号列を一まとめにして入力データを複数の部分集合に分割する。【００４９】
このように、分割ユニット２は、ジグザクスキャンおよびランレングス処理後のデータを各記号列の出現頻度の違いによって複数の部分集合に分割する。【００５０】
図５は、部分集合への分割の具体例を説明するための図である。図５を参照して、原画像は、空の部分、山の部分および地面の部分からなる風景画である。このような原画像は、空の部分、山の部分および地面の部分において、各記号列の出現頻度が異なる。したがって、分割ユニット２は、各記号列の出現頻度の違いによって、原画像のデータを空の部分からなる部分集合Ａ、山の部分からなる部分集合Ｂおよび地面の部分からなる部分集合Ｃに分割する。【００５１】
そして、テーブル作成ユニット３は、空の部分からなる部分集合Ａをスキャンして部分集合Ａに対してハフマン符号化テーブルＡを作成し、山の部分からなる部分集合Ｂをスキャンして部分集合Ｂに対してハフマン符号化テーブルＢを作成し、地面の部分からなる部分集合Ｃをスキャンして部分集合Ｃに対してハフマン符号化テーブルＣを作成する。【００５２】
そうすると、符号化ユニット４は、ハフマン符号化テーブルＡを用いて空の部分からなる部分集合Ａに含まれる符号化対象データをハフマン符号化し、ハフマン符号化テーブルＢを用いて山の部分からなる部分集合Ｂに含まれる符号化対象データをハフマン符号化し、ハフマン符号化テーブルＣを用いて地面の部分からなる部分集合Ｃに含まれる符号化対象データをハフマン符号化する。【００５３】
従来のハフマン符号化は、空の部分、山の部分および地面の部分のようなデータの違いに関係なく、予め定められているハフマン符号化テーブルを用いてハフマン符号化を行なっていた。または、従来のハフマン符号化は、画像全体をスキャンした後に作成したハフマン符号化テーブルを用いてハフマン符号化を行なっていた。【００５４】
しかし、これらの方法では、図に含まれるデータの種類が多くなるにつれて、割り当てるハフマン符号のビット長が次第に長くなり、圧縮後のデータサイズが大きくなる傾向にある。【００５５】
これに対して、この発明による方法では、空、山および地面毎に最適化したハフマン符号化テーブルＡ，Ｂ，Ｃを用いてハフマン符号化するため、画像の部分集合毎にビット長の短い最適なハフマン符号を割り当てることができる。したがって、圧縮率を向上できる。【００５６】
図６は、部分集合への分割の他の具体例を説明するための図である。図６を参照して、原画像は、背景の部分および人物の部分からなる人物のスナップ写真である。このような原画像は、背景の部分および人物の部分において、各記号列の出現頻度が異なる。したがって、分割ユニット２は、各記号列の出現頻度の違いによって、原画像のデータを背景の部分からなる部分集合Ｄおよび人物の部分からなる部分集合Ｅに分割する。【００５７】
そして、テーブル作成ユニット３は、背景の部分からなる部分集合Ｄをスキャンして部分集合Ｄに対してハフマン符号化テーブルＤを作成し、人物の部分からなる部分集合Ｅをスキャンして部分集合Ｅに対してハフマン符号化テーブルＥを作成する。【００５８】
そうすると、符号化ユニット４は、ハフマン符号化テーブルＤを用いて背景の部分からなる部分集合Ｄに含まれる符号化対象データをハフマン符号化し、ハフマン符号化テーブルＥを用いて人物の部分からなる部分集合Ｅに含まれる符号化対象データをハフマン符号化する。【００５９】
この場合にも、この発明による方法では、上述した理由と同じ理由によって、従来のハフマン符号化よりも圧縮率を向上できる。【００６０】
図７は、実施の形態１における圧縮処理方法を説明するためのフローチャートである。図７を参照して、一連の動作が開始されると、圧縮処理装置１０の処理部１は、原画像について、ＲＧＢからＹＣｂＣｒへの変換、サンプリング、レベルシフト、離散コサイン変換、量子化およびジグザグスキャン／ランレングス処理を実行して符号化対象データ群（＝入力データ）を生成する（ステップＳ１）。【００６１】
そして、分割ユニット２は、処理部１から受けた符号化対象データ群から類似した記号列を抽出し、部分集合を生成する（ステップＳ２）。【００６２】
その後、テーブル作成ユニット３は、分割ユニット２によって生成された部分集合内をスキャンし、ハフマン符号化テーブルを作成する（ステップＳ３）。【００６３】
引き続いて、符号化ユニット４は、分割ユニット２から部分集合を受け、テーブル作成ユニット３からハフマン符号化テーブルを受ける。そして、符号化ユニット４は、ハフマン符号化テーブルを用いて部分集合内の符号化対象データをハフマン符号化する（ステップＳ４）。【００６４】
その後、全ての部分集合に対してハフマン符号化が終了したか否かが判定され（ステップＳ５）、全ての部分集合に対してハフマン符号化が終了していない場合、一連の動作は、ステップＳ２へ戻り、上述したステップＳ２〜ステップＳ５が繰り返し実行される。【００６５】
そして、ステップＳ５において、全ての部分集合に対してハフマン符号化が終了していると判定されると、一連の動作は終了する。【００６６】
上述したように、実施の形態１によれば、圧縮処理装置１０は、入力データを各記号列の出現頻度の違いによって複数の部分集合に分割し、その分割した複数の部分集合の各部分集合毎にハフマン符号化テーブルを作成し、その作成したハフマン符号化テーブルを用いて各部分集合毎にハフマン符号化を行なう。【００６７】
その結果、従来のハフマン符号化を用いた場合よりも、各部分集合に含まれる符号化対象データに対して短いハフマン符号が割り当てられる。したがって、圧縮率を向上できる。【００６８】
［実施の形態２］
図８は、実施の形態２による圧縮処理装置の概略ブロック図である。図８を参照して、実施の形態２による圧縮処理装置１０Ａは、図１に示す圧縮処理装置１０の分割ユニット２、テーブル作成ユニット３および符号化ユニット４をエンコーダ１１および最適器１２に代えたものであり、その他は、圧縮処理装置１０と同じである。【００６９】
エンコーダ１１は、各々がハフマン符号からなる２つの符号化テーブルを保持する。そして、エンコーダ１１は、符号化テーブルを切換えるための切換信号ＥＸＣを最適器１２から受けないとき、２つの符号化テーブルのうち、一方の符号化テーブルを用いて、処理部１から受けた入力データをハフマン符号化し、圧縮データを出力する。また、エンコーダ１１は、切換信号ＥＸＣを最適器１２から受けると、２つの符号化テーブルのうちの一方の符号化テーブルから他方の符号化テーブルへ切換えて入力データをハフマン符号化し、圧縮データを出力する。【００７０】
最適器１２は、エンコーダ１１におけるハフマン符号化と並行して、エンコーダ１１が入力データのハフマン符号化に用いていない符号化テーブルを更新するとともに、切換信号ＥＸＣを生成してエンコーダ１１へ出力する。【００７１】
図９は、図８に示すエンコーダ１１および最適器１２の構成図である。図９を参照して、エンコーダ１１は、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）１１１と、選択器１１２と、符号化テーブル１１３，１１４とを含む。最適器１２は、割当モジュール１２１と、交換モジュール１２２とを含む。【００７２】
ＣＡＭ１１１は、複数の記憶記号と、複数の記憶記号にそれぞれ対応付けられた複数のアドレスとを記憶する。複数の記憶記号は、ＣＡＭ１１１へ入力可能な記号からなる。ＣＡＭ１１１は、入力データを構成する各入力記号を処理部１から受けると、記憶している複数の記憶記号を探索し、入力記号に一致する記憶記号を検出するとともに、その検出した記憶記号に対応付けられたアドレスを検出する。そして、ＣＡＭ１１１は、その検出したアドレスを一致アドレスＭＡｄｄとして選択器１１２および最適器１２の割当モジュール１２１へ出力する。【００７３】
選択器１１２は、最適器１２の割当モジュール１２１および交換モジュール１２２からそれぞれ切換信号ＥＸＣ１，ＥＸＣ２（切換信号ＥＸＣの一種）を受けないとき、ＣＡＭ１１１から受けた一致アドレスＭＡｄｄをアクティブテーブル１１３へ出力し、割当モジュール１２１および交換モジュール１２２からそれぞれ切換信号ＥＸＣ１，ＥＸＣ２を受けると、ＣＡＭ１１１から受けた一致アドレスＭＡｄｄをシャドウテーブル１１４へ出力する。【００７４】
アクティブテーブル１１３，１１４の各々は、複数のアドレスと、複数のコードワードとからなる。複数のコードワードは、複数のアドレスにそれぞれ対応付けられている。そして、複数のコードワードの各々は、ハフマン符号からなる。【００７５】
符号化テーブル１１３は、選択器１１２から一致アドレスＭＡｄｄを受けると、アクティブテーブルの役割を果たす。そして、符号化テーブル１１３は、その受けた一致アドレスＭＡｄｄに対応付けられたコードワードを読み出し、その読み出したコードワードを圧縮データとして出力する。【００７６】
また、符号化テーブル１１３は、選択器１１２から一致アドレスＭＡｄｄを受けないとき、シャドウテーブルの役割を果たす。【００７７】
符号化テーブル１１４は、符号化テーブル１１３と同じ構成からなり、符号化テーブル１１３と同じ機能を果たす。【００７８】
なお、符号化テーブル１１３，１１４の各々は、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）からなる。【００７９】
割当モジュール１２１は、ＣＡＭ１１１から一致アドレスＭＡｄｄを受けると、その一致アドレスＭＡｄｄをＣＡＭ１１１から受けた回数をカウントし、そのカウントしたカウント値が最大値Ｃｏｕｎｔ＿ＭＡＸに達すると、一致アドレスＭＡｄｄに代わる新しいアドレスと、新しいコードワードとを後述する方法によって発生し、その発生した新しいアドレスと新しいコードワードとによって符号化テーブル１１４（＝シャドウテーブル）を更新する。また、割当モジュール１２１は、新しいコードワードを交換モジュール１２２へ出力する。更に、割当モジュール１２１は、ＣＡＭ１１１から受ける一致アドレスＭＡｄｄの全てに対するカウント値が最大値Ｃｏｕｎｔ＿ＭＡＸに達したとき、切換信号ＥＸＣ１を生成して選択器１１２へ出力する。【００８０】
交換モジュール１２２は、新しいコードワードを割当モジュール１２１から受け、アクティブテーブルの役割を果たす符号化テーブル１１３（または符号化テーブル１１４）から圧縮データとして出力されるコードワード（「古いコードワード」と言う。以下、同じ。）を受ける。【００８１】
そして、交換モジュール１２２は、新しいコードワードと古いコードワードとに基づいて圧縮率を演算し、その演算した圧縮率がしきい値よりも大きくなると、切換信号ＥＸＣ２を生成して選択器１１２および割当モジュール１２１へ出力する。【００８２】
図１０は、図９に示す割当モジュール１２１の構成図である。図１０を参照して、割当モジュール１２１は、デコーダ１２００と、カウンタ１２０１〜１２０ｎ（ｎは２以上の整数）と、アドレスエンコーダ１２１１と、アドレスカウンタ１２１２と、アドレスレジスタ１２１３と、マルチプレクサ（ＭＵＸ）１２１４と、アドレスポインタ１２１５と、基本テーブル１２１６と、コントローラ１２１７とを含む。【００８３】
デコーダ１２００は、エンコーダ１１のＣＡＭ１１１から受けた一致アドレスＭＡｄｄをデコードし、そのデコードした一致アドレスＭＡｄｄを一致アドレスＭＡｄｄに対応して設けられたカウンタ（カウンタ１２０１〜１２０ｎのいずれか）へ出力する。【００８４】
カウンタ１２０１〜１２０ｎは、ＣＡＭ１１１が記憶するｎ個のアドレスに対応して設けられる。カウンタ１２０１〜１２０ｎの各々は、最大値Ｃｏｕｎｔ＿ＭＡＸが予め設定されている。この最大値Ｃｏｕｎｔ＿ＭＡＸは、ハフマン符号化する対象となるデータの種類に応じて決定されるものである。【００８５】
カウンタ１２０１〜１２０ｎの各々は、デコーダ１２００から一致アドレスＭＡｄｄを受けると、その一致アドレスＭＡｄｄを受けた回数をカウントし、そのカウント値が最大値Ｃｏｕｎｔ＿ＭＡＸに達すると、オーバーフロー信号ＯＦＬを生成し、その生成したオーバーフロー信号ＯＦＬをアドレスエンコーダ１２１１、アドレスカウンタ１２１２およびコントローラ１２１７へ出力する。【００８６】
また、カウンタ１２０１〜１２０ｎの各々は、コントローラ１２１７からリセット信号ＲＳＥＴを受けると、カウント値をリセットする。【００８７】
アドレスエンコーダ１２１１は、カウンタ１２０１〜１２０ｎがそれぞれ対応付けられているアドレスを保持している。そして、アドレスエンコーダ１２１１は、カウンタ１２０１〜１２０ｎのいずれかからオーバーフロー信号ＯＦＬを受けると、そのオーバーフロー信号ＯＦＬを出力したカウンタ（カウンタ１２０１〜１２０ｎのいずれか）が対応付けられたアドレスをエンコードし、そのエンコードしたアドレスをシャドウテーブル１１４において更新されるべきアドレスＡｄｄ＿ｏｌｄとしてアドレスレジスタ１２１３およびマルチプレクサ１２１４へ出力する。【００８８】
アドレスカウンタ１２１２は、カウンタ１２０１〜１２０ｎのいずれかからオーバーフロー信号ＯＦＬを受け、更新されるべきアドレスＡｄｄ＿ｏｌｄのうち、最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸをアドレスレジスタ１２１３から受ける。そして、アドレスカウンタ１２１２は、オーバーフロー信号ＯＦＬを受けると、最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸ以下の範囲で更新アドレスＡｄｄ＿ｎｅｗを順次生成し、その生成した更新アドレスＡｄｄ＿ｎｅｗをアドレスポインタ１２１５へ出力する。【００８９】
この更新アドレスＡｄｄ＿ｎｅｗは、基本テーブル１２１６において指定すべきアドレスを示し、基本テーブル１２１６は、後述するように、コードワードのビット長の短い順にアドレスを割り当てて複数のコードワードを記憶する。【００９０】
したがって、アドレスカウンタ１２１２は、最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸ以下の範囲で小さいアドレスから順に更新アドレスＡｄｄ＿ｎｅｗを生成する。【００９１】
また、アドレスカウンタ１２１２は、交換モジュール１２２から切換信号ＥＸＣ２を受けると、“０”から順にアドレスＡｄｄ０〜Ａｄｄｎを発生し、その発生したアドレスＡｄｄ０〜Ａｄｄｎをマルチプレクサ１２１４およびアドレスポインタ１２１５へ出力する。【００９２】
アドレスレジスタ１２１３は、アドレスエンコーダ１２１１から受けたアドレスＡｄｄ＿ｏｌｄのうち、最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸだけを保持するとともに、その保持した最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸをアドレスカウンタ１２１２へ出力する。【００９３】
マルチプレクサ１２１４は、アドレスエンコーダ１２１１からアドレスＡｄｄ＿ｏｌｄを受けると、その受けたアドレスＡｄｄ＿ｏｌｄをシャドウテーブル１１３へ出力する。【００９４】
また、マルチプレクサ１２１４は、アドレスカウンタ１２１２からアドレスＡｄｄ０〜Ａｄｄｎを受けると、その受けたアドレスＡｄｄ０〜Ａｄｄｎを符号化テーブル１１４（＝シャドウテーブル）へ出力する。【００９５】
アドレスポインタ１２１５は、アドレスカウンタ１２１２から更新アドレスＡｄｄ＿ｎｅｗを受けると、その受けた更新アドレスＡｄｄ＿ｎｅｗに一致する基本テーブル１２１６中のアドレスを指定する。【００９６】
また、アドレスポインタ１２１５は、アドレスカウンタ１２１２からアドレスＡｄｄ０〜Ａｄｄｎを受け、オーバーフロー信号ＯＦＬを出力したカウンタ１２０１〜１２０ｎが対応付けられたｎ個のアドレスをコントローラ１２１７から受ける。そして、アドレスポインタ１２１５は、アドレスカウンタ１２１２から受けたアドレスＡｄｄ０〜Ａｄｄｎのうち、コントローラ１２１７からのアドレスに一致しないアドレスを基本テーブル１２１６において指定する。【００９７】
基本テーブル１２１６は、複数のアドレスと、複数のコードワードとを記憶する。そして、複数のコードワードは、複数のアドレスにそれぞれ対応付けられている。この場合、基本テーブル１２１６は、コードワードのビット長の短い順に複数のコードワードを記憶する。したがって、ビット長が最も短いコードワードは、最小のアドレスに対応付けられ、ビット長が最も長いコードワードは、最大のアドレスに対応付けられている。【００９８】
基本テーブル１２１６は、アドレスポインタ１２１５からアドレスを指定されると、その指定されたアドレスに対応付けられたコードワードを新しいコードワードＣ＿ｎｅｗとして符号化テーブル１１４（＝シャドウテーブル）および交換モジュール１２２へ出力する。【００９９】
コントローラ１２１７は、カウンタ１２０１〜１２０ｎの全てからオーバーフロー信号ＯＦＬを受けると、切換信号ＥＸＣ１を生成し、その生成した切換信号ＥＸＣ１をエンコーダ１１の選択器１１２へ出力するとともに、オーバーフロー信号ＯＦＬを出力したカウンタ１２０１〜１２０ｎが対応付けられたｎ個のアドレスをアドレスポインタ１２１５へ順次出力する。【０１００】
また、コントローラ１２１７は、切換信号ＥＸＣ１を出力したとき、または交換モジュール１２２から切換信号ＥＸＣ２を受けたとき、リセット信号ＲＳＥＴを生成してカウンタ１２０１〜１２０ｎへ出力する。【０１０１】
図１１は、図９に示す交換モジュール１２２の構成図である。図１１を参照して、交換モジュール１２２は、減算器１２２１と、加算器１２２２と、比較器１２２３と、累積レジスタ１２２４と、信号生成器１２２５とを含む。【０１０２】
減算器１２２１は、割当モジュール１２１からコードワードＣ＿ｎｅｗを受け、アクティブテーブルの役割を果たす符号化テーブル１１３（または符号化テーブル１１４）からコードワードＣ＿ｏｌｄを受ける。そして、減算器１２２１は、コードワードＣ＿ｏｌｄからコードワードＣ＿ｎｅｗを減算し、その減算結果を加算器１２２２へ出力する。【０１０３】
加算器１２２２は、減算器１２２１から減算結果を受け、累積レジスタ１２２４から累積値を受ける。そして、加算器１２２２は、累積値に減算結果を加算し、その加算結果を累積レジスタ１２２４へ出力する。【０１０４】
比較器１２２３は、割当モジュール１２１からコードワードＣ＿ｎｅｗを受け、アクティブテーブルの役割を果たす符号化テーブル１１３（または符号化テーブル１１４）からコードワードＣ＿ｏｌｄを受ける。そして、比較器１２２３は、コードワードＣ＿ｎｅｗのビット長をコードワードＣ＿ｏｌｄのビット長と比較し、コードワードＣ＿ｎｅｗのビット長がコードワードＣ＿ｏｌｄのビット長よりも短いとき、累積レジスタ１２２４を活性化するためのイネーブル信号ＥＮを生成し、その生成したイネーブル信号ＥＮを累積レジスタ１２２４へ出力する。なお、比較器１２２３は、コードワードＣ＿ｎｅｗのビット長がコードワードＣ＿ｏｌｄのビット長以上であるとき、イネーブル信号ＥＮを累積レジスタ１２２４へ出力しない。【０１０５】
累積レジスタ１２２４は、比較器１２２３からイネーブル信号ＥＮを受けると、加算器１２２２から受けた加算結果を累積値として保持するとともに、その保持した累積値を加算器１２２２および信号生成器１２２５へ出力する。【０１０６】
信号生成器１２２５は、圧縮率のしきい値が予め設定されている。そして、信号生成器１２２５は、累積レジスタ１２２４から受けた累積値をしきい値と比較し、累積値がしきい値よりも大きくなると、切換信号ＥＸＣ２を生成し、その生成した切換信号ＥＸＣ２をエンコーダ１１の選択器１１２および割当モジュール１２１のコントローラ１２１７へ出力する。【０１０７】
累積レジスタ１２２４は、コードワードＣ＿ｎｅｗのビット長がコードワードＣ＿ｏｌｄのビット長よりも短いときのみ、イネーブル信号ＥＮによって活性化され、累積値を信号生成器１２２５へ出力する。そして、信号生成器１２２５は、累積値が圧縮率のしきい値よりも大きいとき、切換信号ＥＸＣ２を生成する。また、累積値は、コードワードＣ＿ｏｌｄからコードワードＣ＿ｎｅｗを減算した減算結果を累積した値であるので、圧縮データのビット長が短くなった累積値を示す。この発明においては、この累積値を「圧縮率」と言う。【０１０８】
従って、信号生成器１２２５は、圧縮率をしきい値と比較し、圧縮率がしきい値よりも大きいとき、切換信号ＥＸＣ２を生成する。【０１０９】
図１２は、図９に示す交換モジュール１２２の他の構成図である。また、図１２に示すように，比較器１２２３を利用せずに、減算器１２２１に代えて、ＡＬＵ（Ａｒｉｔｈｍｅｔｉｃ  Ｌｏｇｉｃ  Ｕｎｉｔ）のような演算ユニット１２２６を利用した場合、Ｃ＿ｏｌｄとＣ＿ｎｅｗとの演算を工夫することで、累積レジスタの値を細かく調整することができる。たとえば、Ｃ＿ｏｌｄよりＣ＿ｎｅｗのビット長が長い場合、減算結果は、負となるが、その値も累積することで、効率よいコードワードを残すことも可能となる。また、減算のみでなく加算や乗算を利用することでも、よりよい効果が得られる場合がある。【０１１０】
図１３は、一方の符号化テーブル１１３を用いたハフマン符号化の動作を説明するための図である。また、図１４は、他方の符号化テーブル１１４を用いたハフマン符号化の動作を説明するための図である。なお、図１３および図１４においては、選択器１１２が省略されている。【０１１１】
図１３を参照して、選択器１１２は、切換信号ＥＸＣ１またはＥＸＣ２を受けないとき、符号化テーブル１１３を選択する。したがって、符号化テーブル１１３は、アクティブテーブルの役割を果たし、符号化テーブル１１４は、シャドウテーブルの役割を果たす。【０１１２】
符号化テーブル１１３は、アドレス［００００］〜［１１１１］と、コードワード［００００２］〜［ｆｆｆｅｆ］とからなる。そして、コードワード［００００２］〜［ｆｆｆｅｆ］の各々は、ハフマン符号であり、複数のコードワード［００００２］〜［ｆｆｆｅｆ］は、それぞれ、複数のアドレス［００００］〜［１１１１］に対応付けられている。【０１１３】
ＣＡＭ１１１は、［０１１００１０１］を入力記号として処理部１から受けると、記憶している複数の記憶記号［１００００００１］，［１０００００１０］，・・・，［１１１１１０１０］を探索し、入力記号＝［０１１００１０１］に一致する記憶記号＝［０１１００１０１］を検出し、その検出した記憶記号＝［０１１００１０１］に対応付けられたアドレス＝［００１１］を一致アドレスＭＡｄｄとして選択器１１２を介してアクティブテーブルの役割を果たす符号化テーブル１１３へ出力する。【０１１４】
符号化テーブル１１３は、一致アドレスＭＡｄｄ＝［００１１］を受けると、その受けた一致アドレスＭＡｄｄ＝［００１１］に一致するアドレス＝［００１１］に対応付けられたコードワード＝［０００４３］を検出し、その検出したコードワード＝［０００４３］を圧縮データとして出力する。【０１１５】
図１４を参照して、選択器１１２は、切換信号ＥＸＣ１またはＥＸＣ２を受けると、使用する符号化テーブルを符号化テーブル１１３から符号化テーブル１１４へ切換える。したがって、符号化テーブル１１４は、アクティブテーブルの役割を果たし、符号化テーブル１１３は、シャドウテーブルの役割を果たす。【０１１６】
符号化テーブル１１４は、アドレス［００００］〜［１１１１］と、コードワード［０００２３］〜［ｆｆｆｅｆ］とからなる。そして、コードワード［０００２３］〜［ｆｆｆｅｆ］の各々は、ハフマン符号であり、複数のコードワード［０００２３］〜［ｆｆｆｅｆ］は、それぞれ、複数のアドレス［００００］〜［１１１１］に対応付けられている。【０１１７】
ＣＡＭ１１１は、［０１１００１０１］を入力記号として処理部１から受けると、上述した動作と同じ動作によって、一致アドレスＭＡｄｄ＝［００１１］を選択器１１２を介して符号化テーブル１１４へ出力する。【０１１８】
符号化テーブル１１４は、一致アドレスＭＡｄｄ＝［００１１］を受けると、その受けた一致アドレスＭＡｄｄ＝［００１１］に一致するアドレス＝［００１１］に対応付けられたコードワード＝［００００２］を検出し、その検出したコードワード＝［００００２］を圧縮データとして出力する。【０１１９】
このように、エンコーダ１１は、符号化テーブル１１３または符号化テーブル１１４を用いて入力記号＝［０１１００１０１］をコードワード＝［０００４３］または［００００２］へ変換する。【０１２０】
エンコーダ１１は、入力記号＝［０１１００１０１］以外の入力記号が入力された場合も、上述した動作によって入力記号をコードワードに変換する。【０１２１】
したがって、エンコーダ１１をＣＡＭ１１１と２つの符号化テーブル１１３，１１４とによって構成することにより、入力記号を容易にハフマン符号化できる。【０１２２】
図１５は、シャドウテーブルの役割を果たす符号化テーブル１１４の更新を説明するための図である。なお、図１５において、コードワードの括弧内の数字は、コードワードのビット長を表す。【０１２３】
２つの符号化テーブル１１３，１１４は、カウンタ１２０１〜１２０ｎの全てがオーバーフロー信号ＯＦＬを出力したとき、または圧縮率がしきい値よりも大きくなったとき、アクティブテーブルおよびシャドウテーブルの役割が切換えられる。【０１２４】
そして、符号化テーブル１１３，１１４および基本テーブル１２１６は、最初、同じアドレスおよび同じコードワードがデフォルト設定として設定されている。【０１２５】
たとえば、アドレス＝［００１０］に対応付けられたカウンタ１２０３が上述した方法によってオーバーフロー信号ＯＦＬを出力すると、アドレスエンコーダ１２１１は、カウンタ１２０３が対応付けられたアドレスをエンコードし、アドレス＝［００１０］をアドレスレジスタ１２１３およびマルチプレクサ１２１４へ出力する。【０１２６】
そして、アドレスレジスタ１２１３は、アドレスエンコーダ１２１１からアドレス＝［００１０］を受けると、既に保持しているアドレスをアドレス＝［００１０］と比較し、既に保持しているアドレスがアドレス＝［００１０］よりも大きい場合、既に保持しているアドレスの保持を維持し、既に保持しているアドレスがアドレス＝［００１０］よりも小さい場合、既に保持しているアドレスに代えてアドレス＝［００１０］を保持する。その後、アドレスレジスタ１２１３は、アドレス＝［００１０］を最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸとしてアドレスカウンタ１２１２へ出力する。【０１２７】
アドレスカウンタ１２１２は、カウンタ１２０３からオーバーフロー信号ＯＦＬを受け、アドレスレジスタ１２１３から最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸを受ける。そして、アドレスカウンタ１２１２は、最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸ以下の範囲でアドレス値の小さい順に更新アドレスＡｄｄ＿ｎｅｗを発生し、その発生した更新アドレスＡｄｄ＿ｎｅｗをアドレスポインタ１２１５へ出力する。【０１２８】
マルチプレクサ１２１４は、アドレスエンコーダ１２１１から受けたアドレスＡｄｄ＿ｏｌｄをシャドウテーブルの役割を果たす符号化テーブル１１４へ出力する。【０１２９】
一方、アドレスポインタ１２１５は、更新アドレスＡｄｄ＿ｎｅｗに一致する基本テーブル１２１６中のアドレスを指定し、基本テーブル１２１６は、アドレスポインタ１２１５によって指定されたアドレスに対応付けられたコードワード＝［００００２］をコードワードＣ＿ｎｅｗとして符号化テーブル１１４（＝シャドウテーブル）および交換モジュール１２２へ出力する。【０１３０】
そうすると、符号化テーブル１１４（＝シャドウテーブル）は、割当モジュール１２１のマルチプレクサ１２１４からアドレスＡｄｄ＿ｏｌｄ＝［００００２］を受け、基本テーブル１２１６からコードワードＣ＿ｎｅｗ＝［００００２］を受ける。そして、符号化テーブル１１４（＝シャドウテーブル）は、コードワードＣ＿ｎｅｗ＝［００００２（２）］をアドレス＝［００１０］に対応付けられたコードワード＝［００１ｅ５（５）］に上書きする。これによって、符号化テーブル１１４−１（＝シャドウテーブル）は、符号化テーブル１１４−２（＝シャドウテーブル）へ更新され、アドレス＝［００１０］に対応付けられたコードワードは、３ビットだけ短くなる（図１５参照）。【０１３１】
その後、同様にして、コードワード＝［０００２３（３）］がアドレス＝［１１１０］に対応付けれられたコードワード＝［ｆｆｆ４ｆ（１６）］に上書きされ、符号化テーブル１１４−２（＝シャドウテーブル）は、符号化テーブル１１４−３（＝シャドウテーブル）へ更新される。これによって、アドレス＝［１１１０］に対応付けられたコードワードは、１３ビットだけ短くなる。【０１３２】
それ以降、同様にして、符号化テーブル１１４−３（＝シャドウテーブル）は、符号化テーブル１１４−４（＝シャドウテーブル）へ更新される。この符号化テーブル１１４（＝シャドウテーブル）におけるコードワードの上書きは、最後のカウンタ（カウンタ１２０１〜１２０ｎのいずれか）がオーバーフロー信号ＯＦＬを出力するまで、または圧縮率がしきい値よりも大きくなるまで繰り返される。【０１３３】
アドレスカウンタ１２１２は、最後のカウンタ（カウンタ１２０１〜１２０ｎのいずれか）からオーバーフロー信号ＯＦＬを受けて更新アドレスＡｄｄ＿ｎｅｗをアドレスポインタ１２１５へ出力した後、または交換モジュール１２２から切換信号ＥＸＣ２を受けたとき、“０”から開始してアドレスを順次発生し、その発生したアドレスをマルチプレクサ１２１４およびアドレスポインタ１２１５へ出力する。【０１３４】
また、コントローラ１２１７は、オーバーフロー信号ＯＦＬを出力したカウンタ１２０１〜１２０ｎが対応付けられたｎ個のアドレスをアドレスポインタ１２１５へ順次出力する。【０１３５】
そうすると、アドレスポインタ１２１５は、アドレスカウンタ１２１２から受けたアドレスのうち、コントローラ１２１７からのアドレスに一致しないアドレスを基本テーブル１２１６において指定する。そして、基本テーブル１２１６は、指定されたアドレスに対応付けられたコードワードを読み出して符号化テーブル１１４（＝シャドウテーブル）へ出力する。【０１３６】
一方、マルチプレクサ１２１４は、アドレスカウンタ１２１２から出力されたアドレスを符号化テーブル１１４（＝シャドウテーブル）へ出力する。【０１３７】
そうすると、符号化テーブル１１４（＝シャドウテーブル）は、マルチプレクサ１２１４からのアドレスと、基本テーブル１２１６からのコードワードとを受け、その受けたアドレスおよびコードワードに基づいて、オーバーライトの過程においてコードワードが上書きされなかったコードワード上に基本テーブル１２１６から受けたコードワードを上書きする。【０１３８】
その結果、図１５に示すように、オーダーライトにおいて、アドレス＝［００００］，［０００１］，・・・，［００１０］に対応付けられたコードワードがそれぞれコードワード＝［００ｆｅ８］，［００ｆａ９］，・・・，［０３ｆ９ａ］によって上書きされる。これによって、符号化テーブル１１４−４（＝シャドウテーブル）は、符号化テーブル１１４−５，１１４−６，１１４−７（＝シャドウテーブル）へ順次更新され、重複したコードワードが無くなる。この処理を最大のアドレスＡｄｄ＿ｏｌｄ＿ＭＡＸの値まで行なう。【０１３９】
上述した符号化テーブル１１４（＝シャドウテーブル）の更新においては、割当モジュール１２１は、オーバーフロー信号ＯＦＬを受けた順番により短いコードワードを符号化テーブル１１４（＝シャドウテーブル）へ出力し、符号化テーブル１１４（＝シャドウテーブル）を更新する。したがって、割当モジュール１２１は、出現頻度のカウント値が最大値に達した順番が早いほど短い長さのコードワードを１つの符号化対象データに割り当てることになる。【０１４０】
また、上述した符号化テーブル１１４（＝シャドウテーブル）の更新は、エンコーダ１１が符号化テーブル１１３（＝アクティブテーブル）を用いて上述した方法によって入力記号をハフマン符号に変換している動作に並行して行なわれる。【０１４１】
なお、符号化テーブル１１３がシャドウテーブルの役割を果たす場合も、上述した方法によって、符号化テーブル１１３が更新される。【０１４２】
図１６は、図９に示すエンコーダ１１および最適器１２における動作を説明するためのフローチャートである。【０１４３】
図１６を参照して、一連の動作が開始されると、エンコーダ１１のＣＡＭ１１１は、入力記号を受け（ステップＳ１１）、その受けた入力記号を記憶記号と比較する（ステップＳ１２）。【０１４４】
そして、エンコーダ１１のＣＡＭ１１１は、入力記号に一致する記憶記号に対応付けられたアドレスを検出すると、その検出したアドレスを一致アドレスＭＡｄｄとして選択器１１２および割当モジュール１２１へ出力する。そして、エンコーダ１１の選択器１１２は、一致アドレスＭＡｄｄを符号化テーブル１１３（＝アクティブテーブル）および割当モジュール１２１へ出力する（ステップＳ１３）。【０１４５】
引き続いて、エンコーダ１１の符号化テーブル１１３（＝アクティブテーブル）は、一致アドレスＭＡｄｄに一致するアドレスに対応付けられたコードワードを出力する（ステップＳ１４）。【０１４６】
その後、全ての入力記号がハフマン符号に変換されたか否かが判定され（ステップＳ１５）、全ての入力記号がハフマン符号に変換されていない場合、一連の動作は、ステップＳ１１へ戻り、エンコーダ１１において、上述したステップＳ１１〜ステップＳ１５が繰り返し実行される。【０１４７】
一方、ステップＳ１５において、全ての入力記号がハフマン符号に変換されたと判定されたとき、一連の動作は、終了する。【０１４８】
ステップＳ１３の後、最適器１２において、一致アドレスＭＡｄｄに対応付けられたカウンタ（カウンタ１２０１〜１２０ｎのいずれか）は、カウンタ値を“１”だけインクリメントし（ステップＳ１６）、カウンタ値が最大値であるか否かを判定する（ステップＳ１７）。【０１４９】
ステップＳ１７において、カウンタ値が最大値でないと判定されたとき、交換モジュール１２２は、上述した方法によって、圧縮率がしきい値以下であるか否かを判定する（ステップＳ１８）。【０１５０】
ステップＳ１８において、圧縮率がしきい値以下であると判定されたとき、一連の動作は、ステップＳ１６へ戻り、上述したステップＳ１６〜ステップＳ１８が繰り返し実行される。【０１５１】
一方、ステップＳ１８において、圧縮率がしきい値よりも大きいと判定されたとき、一連の動作は、ステップＳ２２へ移行する。【０１５２】
一方、ステップＳ１７において、カウンタ値が最大値であると判定されたとき、上述した方法によって、新しいハフマン符号が符号化テーブル１１４（＝シャドウテーブル）に割当てられ（ステップＳ１９）、符号化テーブル１１４（＝シャドウテーブル）は、新しいハフマン符号によって更新される（ステップＳ２０）。【０１５３】
その後、全てのカウンタ値が最大値であるか否かが判定され（ステップＳ２１）、全てのカウンタ値が最大値であるとき、一連の動作は、ステップＳ２２へ移行する。【０１５４】
一方、ステップＳ２１において、全てのカウンタ値の少なくとも１つが最大値でないと判定されたとき、一連の動作は、ステップＳ１６へ移行する。【０１５５】
ステップＳ１８において、圧縮率がしきい値よりも大きいと判定されたとき、またはステップＳ２１において、全てのカウンタ値が最大値であると判定されたとき、符号化テーブルが切換えられる（ステップＳ２２）。そして、一連の動作は、ステップＳ１３へ移行する。【０１５６】
なお、上述したステップＳ１１〜ステップＳ１５は、エンコーダ１１によって実行され、上述したステップＳ１６〜ステップＳ２２は、最適器１２によって実行される。したがって、最適器１２における動作は、エンコーダ１１における動作と並行して行なわれる。【０１５７】
図１７は、図８に示す圧縮処理装置１０Ａにおけるハフマン符号化を具体的に説明するための図である。【０１５８】
図１７を参照して、エンコーダ１１は、処理部１においてジグザクスキャンおよびランレングス処理が行なわれた後の入力データを受ける。【０１５９】
そして、エンコーダ１１は、入力データを構成する各記号を符号化テーブル１１３（＝アクティブテーブル）を用いて上述した方法によってハフマン符号化する。ここで、エンコーダ１１は、図１７に示す人物画像の背景部分をハフマン符号化する場合、圧縮率がしきい値以下である限り、符号化テーブル１１３（＝アクティブテーブル）を用いて背景部分の符号化対象データをハフマン符号化する。したがって、エンコーダ１１は、符号化テーブル１１３（＝アクティブテーブル）に格納された一部のコードワードを用いて背景部分のハフマン符号化に適したハフマン符号化テーブルを作成しながら背景部分の符号化対象データをハフマン符号化することになる。【０１６０】
その後、エンコーダ１１は、人物画像の顔部分の符号化対象データを受けると、圧縮率がしきい値以下である限り、符号化テーブル１１３（＝アクティブテーブル）を用いて顔部分の符号化対象データをハフマン符号化し、圧縮率がしきい値よりも大きくなると、符号化テーブル１１４（＝シャドウテーブル）に切換えて顔部分の符号化対象データをハフマン符号化する。したがって、エンコーダ１１は、顔部分の符号化対象データをハフマン符号化する場合、符号化テーブル１１３（＝アクティブテーブル）に格納された一部のコードワードまたは符号化テーブル１１４（＝シャドウテーブル）に格納された一部のコードワードを用いて顔部分のハフマン符号化に適したハフマン符号化テーブルを作成しながら顔部分の符号化対象データをハフマン符号化することになる。【０１６１】
エンコーダ１１が人物画像の胴部分の符号化対象データをハフマン符号化する場合も同様である。【０１６２】
その結果、エンコーダ１１および最適器１２は、処理部１から入力された入力データをハフマン符号化することによって、人物画像を背景部分、顔部分および胴部分の部分集合に分割し、かつ、背景部分、顔部分および胴部分の部分集合にそれぞれ適したハフマン符号化テーブルを作成しながら背景部分、顔部分および胴部分の部分集合をそれぞれハフマン符号化する。【０１６３】
この場合、エンコーダ１１は、図１に示す分割ユニット２および符号化ユニット４を構成し、エンコーダ１１および最適器１２は、図１に示すテーブル作成ユニット３を構成する。【０１６４】
したがって、実施の形態２による圧縮処理装置１０Ａ（図８参照）は、実施の形態１による圧縮処理装置１０（図１参照）と同じ構成からなる。【０１６５】
図１８は、実施の形態２における圧縮処理方法を説明するためのフローチャートである。【０１６６】
図１８を参照して、一連の動作が開始されると、圧縮処理装置１０Ａの処理部１は、原画像について、ＲＧＢからＹＣｂＣｒへの変換、サンプリング、レベルシフト、離散コサイン変換、量子化およびジグザグスキャン／ランレングス処理を実行して符号化対象データ群（＝入力データ）を生成する（ステップＳ３１）。【０１６７】
そして、処理部１は、符号化対象データをエンコーダ１１へ出力し（ステップＳ３２）、エンコーダ１１は、処理部１から受けた符号化対象データ（＝入力記号）に一致する記憶記号に対応付けられたアドレスを検出し、その検出したアドレスを一致アドレスＭＡｄｄとして最適器１２へ出力する。【０１６８】
そして、最適器１２は、一致アドレスＭＡｄｄを受けた回数をカウントすることにより、符号化対象データ毎に出現頻度をカウントする（ステップＳ３３）。【０１６９】
その後、最適器１２は、カウンタ１２０１〜１２０ｎのいずれかがオーバーフロー信号ＯＦＬを出力したか否かによって出現頻度が最大値（＝最大値Ｃｏｕｎｔ＿ＭＡＸ）に達する符号化対象データがあるか否かを判定する（ステップＳ３４）。この場合、最適器１２は、カウンタ１２０１〜１２０ｎのいずれかがオーバーフロー信号ＯＦＬを出力した場合、出現頻度が最大値（＝最大値Ｃｏｕｎｔ＿ＭＡＸ）に達する符号化対象データがあると判定し、カウンタ１２０１〜１２０ｎのいずれもオーバーフロー信号ＯＦＬを出力しない場合、出現頻度が最大値（＝最大値Ｃｏｕｎｔ＿ＭＡＸ）に達する符号化対象データがないと判定する。【０１７０】
ステップＳ３４において、出現頻度が最大値（＝最大値Ｃｏｕｎｔ＿ＭＡＸ）に達する符号化対象データがあると判定されたとき、最適器１２は、上述した方法によって、符号化テーブル１１４（＝シャドウテーブル）を更新して該当符号に短いハフマン符号を割り当てる（ステップＳ３５）。【０１７１】
ステップＳ３５の後、またはステップＳ３４において、出現頻度が最大値（＝最大値Ｃｏｕｎｔ＿ＭＡＸ）に達する符号化対象データがないと判定されたとき、最適器１２は、カウンタ１２０１〜１２０ｎの全てがオーバーフロー信号ＯＦＬを出力したか否かによってハフマン符号の新規割当回数が閾値を越えたか否かを判定する（ステップＳ３６）。【０１７２】
この場合、最適器１２は、カウンタ１２０１〜１２０ｎの全てがオーバーフロー信号ＯＦＬを出力したとき、ハフマン符号の新規割当回数が閾値を越えたと判定し、カウンタ１２０１〜１２０ｎの少なくとも１つがオーバーフロー信号ＯＦＬを出力しないとき、ハフマン符号の新規割当回数が閾値を越えていないと判定する。【０１７３】
ステップＳ３６において、ハフマン符号の新規割当回数が閾値を越えたと判定されたとき、エンコーダ１１は、アクティブテーブルを符号化テーブル１１３から符号化テーブル１１４へ切換え、その切換えた符号化テーブル１１４において新規にハフマン符号化テーブルを作成しながら符号化対象データをハフマン符号化する（ステップＳ３７）。【０１７４】
一方、ステップＳ３６において、ハフマン符号の新規割当回数が閾値を越えていないと判定されたとき、エンコーダ１１は、符号化テーブル１１３を用いて既に作成されたハフマン符号化テーブルを用いて符号化対象データをハフマン符号化する（ステップＳ３８）。【０１７５】
そして、ステップＳ３７またはステップＳ３８の後、全ての符号化対象データの符号化が終了したか否かが判定される（ステップＳ３９）。ステップＳ３９において、少なくとも１つの符号化対象データの符号化が終了していないと判定されたとき、一連の動作は、ステップＳ３２へ戻り、ステップＳ３９において、全ての符号化対象データの符号化が終了したと判定されるまで、上述したステップＳ３２〜ステップＳ３９が繰り返し実行される。【０１７６】
そして、ステップＳ３９において、全ての符号化対象データの符号化が終了したと判定されると、一連の動作は終了する。【０１７７】
上述したように、実施の形態２においては、圧縮処理装置１０Ａは、入力データの部分集合への分割、および分割された部分集合に適したハフマン符号化テーブルの作成を行ないながら符号化対象データをハフマン符号化する。【０１７８】
したがって、符号化対象データを高速にハフマン符号化できるとともに、圧縮率を向上できる。【０１７９】
その他は、実施の形態１と同じである。【０１８０】
なお、実施の形態２においては、符号化テーブル１１３，１１４は、「テーブル保持ユニット」を構成し、最適器１２は、「更新ユニット」を構成する。【０１８１】
［実施の形態３］
図１９は、実施の形態３による圧縮処理装置の概略ブロック図である。図１９を参照して、実施の形態３による圧縮処理装置１０Ｂは、図１に示す圧縮処理装置１０に画像分割ユニット５を追加したものであり、その他は、圧縮処理装置１０と同じである。【０１８２】
画像分割ユニット５は、原画像の対象物に基づいて原画像データを複数の画像データに分割し、その分割した複数の画像データを処理部１へ出力する。【０１８３】
圧縮処理装置１０Ｂにおいては、処理部１は、画像分割ユニット５から入力された複数の画像データを各画像データ毎に上述した方法によって処理し、複数の画像データに対応する複数の入力データを分割ユニット２へ出力する。【０１８４】
また、圧縮処理装置１０Ｂにおいては、分割ユニット２は、各入力データ毎に複数の部分集合に分割する処理を複数の入力データの全ての入力データに対して実行し、テーブル作成ユニット３は、各入力データ毎に分割された複数の部分集合に適した複数のハフマン符号化テーブルを作成する処理を複数の入力データの全ての入力データに対して実行し、符号化ユニット４は、各入力データ毎に複数の部分集合に含まれる符号化対象データを複数の部分集合に適した複数のハフマン符号化テーブルを用いて各部分集合毎にハフマン符号化する処理を複数の入力データの全ての入力データに対して実行する。【０１８５】
図１９に示す画像分割ユニット５における画像の分割方法について説明する。画像分割ユニット５は、たとえば、領域成長型分割分割アルゴリズムを用いて画像を複数の画像に分割する。【０１８６】
この領域成長型分割分割アルゴリズムは、たとえば、３×３の画素からリーダセルを決定し、その決定したリーダセルの領域から相対的に大きい結合重みを有する周囲の画素の領域へ領域を成長させて行く処理をリーダセルが存在しなくまで繰り返して画像を分割する方法である。【０１８７】
図２０は、画像の分割方法を説明するための図である。画像分割ユニット５は、領域成長型画像分割方法によって１つのフレームを各対象物の画像に分割する。【０１８８】
この領域成長型画像分割方法は、ＬＥＧＩＯＮモデル（D. L. Wang, and D. Terman, “Image segmentation based on oscillator correlation,” Neural Computation, Volume 9(4), pp. 805-836(1997).）の振動子ネットワークの各画素に対する振動子の振る舞いを自己発火（Ｓｅｌｆ−Ｅｘｃｉｔａｔｉｏｎ）、自己発火可能（Ｓｅｌｆ−Ｅｘｃｉｔａｂｌｅ）、発火（Ｅｘｃｉｔａｔｉｏｎ）および鎮火（Ｉｎｈｉｂｉｔｉｏｎ）という４つの状態で取り扱うものである。そして、この領域成長型画像分割方法は、初期化、自己発火、発火、および鎮火の４つのステップからなる。【０１８９】
画像分割ユニット５は、図２０の（ａ）に示す３×３の構成からなる入力画像を受ける。そして、画像分割ユニット５は、入力画像を構成する９個の画素における画素間の８個の結合重みＣＷ１〜ＣＷ８を演算し、その演算した８個の結合重みＣＷ１〜ＣＷ８を各画素間に対応付けてメモリ（画像分割ユニット５に内蔵されている）に保持する。なお、図２０の（ｂ）においては、（２，２）の画素と周囲の画素との８個の結合重みが図示されている。【０１９０】
そうすると、画像分割ユニット５は、メモリに保持された８個の結合重みＣＷ１〜ＣＷ８を読み出し、その読み出した８個の結合重みＣＷ１〜ＣＷ８の和ＳＵＭ（ＣＷ）を演算する。そして、画像分割ユニット５は、その演算した和ＳＵＭ（ＣＷ）がリーダセルを決定するためのしきい値φＰよりも大きいか否かを判定する。なお、この出願においては、ＳＵＭは、数学におけるシグマ記号によって表される和を演算することを意味する。【０１９１】
画像分割ユニット５は、和ＳＵＭ（ＣＷ）がしきい値φＰよりも大きいと判定したとき、結合重みの計算の中心となった画素をリーダセルに設定し、リーダセルフラグｐｉｊ＝１を設定する。一方、画像分割ユニット５は、和ＳＵＭ（ＣＷ）がしきい値φＰ以下であると判定したとき、結合重みの計算の中心となった画素をリーダセルに設定せず、リーダセルフラグｐｉｊ＝０を設定する。【０１９２】
画像分割ユニット５は、この処理を入力画像の９個の画素の各々を結合重みの計算の中心となる画素に設定して実行し、リーダセルを決定する（図２０の（ｃ）参照）。【０１９３】
その後、画像分割ユニット５は、リーダセルの１つを自己発火させる（発火フラグｘｉｊ＝１）（図２０の（ｄ）参照）。そして、画像分割ユニット５は、各セル（ｉ，ｊ）に隣接する８個の画素に対応するセル（ｋ，ｌ）∈Ｎｉｊが発火していれば、セル（ｉ，ｊ）とセル（ｋ，ｌ）との間の結合重みの和ＳＵＭ（ｋ，ｌ）∈Ｎｉｊ∧ｘｋｌ＝１Ｗｉｊ；ｋｌを演算し、その演算した和ＳＵＭ（ｋ，ｌ）∈Ｎｉｊ∧ｘｋｌ＝１Ｗｉｊ；ｋｌがしきい値φＺよりも大きく、かつ、まだ、セル（ｉ，ｊ）がどの分割領域にも属していない（ラベルフラグｌｉｊ＝０）場合に、自動的に発火（ｘｉｊ＝１）させる（引火・領域成長）（図２０の（ｅ）参照）。この引火処理によって、領域が広がって行き、図２０の（ｆ）に示すように、新たに発火するセルが存在しなくなると、１領域の分割が終了する。【０１９４】
その後、画像分割ユニット５は、この分割された領域を保存するために、図２０の（ｇ）に示すように、発火しているセルへ分割領域識別のためのラベル番号を書き込み、発火したセルが既に分割されたセルであることを示すラベルフラグをセットし（ｌｉｊ＝１）、鎮火処理（ｘｉｊ＝０，ｐｉｊ＝０）を行なう。【０１９５】
画像分割ユニット５は、鎮火処理が終了すると、再び、次の領域の分割のための自己発火の処理に戻る。そして、画像分割ユニット５は、リーダセルが存在しなくなるまで、上述した処理を繰り返し実行し、各領域を分割する。そして、画像分割ユニット５は、全てのリーダセルが発火した後、全ての領域にラベル付けを行ない、１フレームの画像の分割を終了する（図２０の（ｈ）参照）。【０１９６】
図２１は、領域成長型分割分割アルゴリズムを用いた画像の分割方法を説明するためのフローチャートである。【０１９７】
図２１を参照して、一連の動作が開始されると、画像分割ユニット５は、１フレームを構成する複数の画素における各画素間の結合重みを演算するとともに、上述した方法によって、リーダセルを決定する（ステップＳ４１）。【０１９８】
そして、画像分割ユニット５は、自己発火可能なセルを検出したか否かを判定し（ステップＳ４２）、自己発火可能なセルを検出したと判定したとき、上述した方法によって自己発火を行なう（ステップＳ４３）。【０１９９】
その後、画像分割ユニット５は、発火セルが存在するか否かを判定し（ステップＳ４４）、発火セルが存在するとき、上述した方法によって周囲へ引火（領域成長）を行なう（ステップＳ４５）。そして、一連の動作は、ステップＳ４４へ戻り、ステップＳ４４において、発火セルが存在しなくなるまで、ステップＳ４４，Ｓ４５が繰り返し実行される。【０２００】
ステップＳ４４において、発火セルが存在しないと判定されると、画像分割ユニット５は、上述した方法によって、引火終了・領域決定を行なうとともに、ラベル付け（鎮火）を行なう（ステップＳ４６）。その後、一連の動作は、ステップＳ４２へ戻り、ステップＳ４２において、自己発火可能なセルが検出されないと判定されるまで、ステップＳ４２〜ステップＳ４６が繰り返し実行される。【０２０１】
そして、ステップＳ４２において、自己発火可能なセルが検出されないと判定されると、一連の動作は、終了する。【０２０２】
なお、画像分割ユニット５は、図２１に示すフローチャートを繰り返し実行し、各フレームを各対象物の画像に分割する。【０２０３】
図２２は、実施の形態３における圧縮処理方法を説明するためのフローチャートである。図２２に示すフローチャートは、図７に示すフローチャートのステップＳ２〜ステップＳ５にステップＳ５１〜ステップＳ５３を追加したものであり、その他は、図７に示すフローチャートと同じである。【０２０４】
図２２を参照して、一連の動作が開始されると、圧縮処理装置１０Ｂの画像分割ユニット５は、図２１に示すフローチャートに従って原画像を複数の画像に分割する（ステップＳ５１）。【０２０５】
そして、処理部１は、複数の画像の１つの画像について、ＲＧＢからＹＣｂＣｒへの変換、サンプリング、レベルシフト、離散コサイン変換、量子化およびジグザグスキャン／ランレングス処理を実行して符号化対象データ群（＝入力データ）を生成する（ステップＳ５２）。【０２０６】
その後、上述したステップＳ２〜ステップＳ５が順次実行される。そして、ステップＳ５において、全ての部分集合に対して符号化が終了したと判定されると、全ての画像に対して符号化が終了したか否かが判定される（ステップＳ５３）。【０２０７】
ステップＳ５３において、全ての画像に対して符号化が終了していないと判定されたとき、一連の動作は、ステップＳ５２へ戻り、ステップＳ５３において、全ての画像に対して符号化が終了したと判定されるまで、上述したステップＳ５２，Ｓ２〜Ｓ５，Ｓ５３が繰り返し実行される。【０２０８】
そして、ステップＳ５３において、全ての画像に対して符号化が終了したと判定されると、一連の動作が終了する。【０２０９】
図２３は、実施の形態３による圧縮処理装置の他の構成を示す概略ブロック図である。実施の形態３による圧縮処理装置は、図２３に示す圧縮処理装置１０Ｃであってもよい。【０２１０】
図２３を参照して、圧縮処理装置１０Ｃは、図８に示す圧縮処理装置１０Ａに画像ユニット５を追加したものであり、その他は、圧縮処理装置１０Ａと同じである。【０２１１】
画像分割ユニット５については、上述したとおりである。したがって、圧縮処理装置１０Ｃは、原画像を対象物に注目して複数の画像に分割し、その分割した複数の画像の各々について、複数の部分集合への分割、および複数の部分集合に適した複数のハフマン符号化テーブルの作成を行ないながら複数の部分集合に含まれる全ての符号化対象データをハフマン符号化する処理を実行し、原画像データを圧縮する。【０２１２】
図２４は、実施の形態３における他の圧縮処理方法を説明するためのフローチャートである。図２４に示すフローチャートは、図１８に示すフローチャートのステップＳ３２〜ステップＳ３９にステップＳ５１〜ステップＳ５３を追加したものであり、その他は、図１８に示すフローチャートと同じである。【０２１３】
図２４を参照して、一連の動作が開始されると、上述したステップＳ５１，Ｓ５２が順次実行され、その後、上述したステップＳ３２〜ステップＳ３９が順次実行される。そして、ステップＳ３９において、全ての符号化対象データの符号化が終了したと判定されると、上述したステップＳ５３が実行され、ステップＳ５３において、全ての画像に対して符号化が終了したと判定されると、一連の動作は、終了する。【０２１４】
上述したように、実施の形態３においては、対象物に注目して原画像を複数の画像に分割し、その分割した複数の画像の各々について、実施の形態１による圧縮処理方法または実施の形態２による圧縮処理方法を用いて原画像データを圧縮することを特徴とする。【０２１５】
原画像の分割は、各対象物を抽出するように行なわれるので、分割された各画像は、類似した画像データからなる。したがって、これらの各画像に対して実施の形態１，２によるハフマン符号化を適用することによって、データの圧縮を柔軟に行なうことができる。【０２１６】
たとえば、図５に示す風景画は、空からなる画像、山からなる画像、および地面からなる画像の３個の画像に分割される。その結果、３個の画像の各画像は、出現頻度が類似した記号列からなるので、各画像に対して柔軟に対応したハフマン符号化テーブルを作成できる。したがって、データの圧縮を柔軟に行なうことができる。【０２１７】
なお、上記においては、画像分割は、領域成長型画像分割方法を用いて行なわれると説明したが、この発明においては、これに限らず、画像分割は、下記の（１）〜（４）に記載された方法を用いて行なわれてもよい。【０２１８】
（１）B. Jaehne, “Digital Image Processing 5th revised and extended edition,” Springer-Verlag, pp. 427-440, 2001.
（２）J. C. Russ, “The Image Processing Handbook,” CRC PRESS, pp. 371-429, 1999.36
（３）T. Braeunl, S. Feyrer, W. Rapf, and M. Reinhardt, “Parallel Image Processing,”Springer-Verlag, 2000.
（４）W. Y. Ma, and B. S. Manjunath, “Edgeflow: a technique for boundary detection and segmentation,” IEEE Transactions on Image Processing, vol. 9 (8), pp. 1375-1388, 2004.
その他は、実施の形態１，２と同じである。【０２１９】
上述した実施の形態１〜３においては、画像データを圧縮する場合について説明したが、この発明においては、これに限らず、この発明による圧縮処理装置および圧縮処理方法は、文章データおよびオーディオデータを上述した方法によって圧縮してもよい。【０２２０】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【０２２１】
この発明は、圧縮効率の向上が可能な圧縮処理装置に適用される。また、この発明は、圧縮効率の向上が可能な圧縮処理方法に適用される。
【図１】
2010013290.tif 000003
【図２】
2010013290.tif 000004
【図３】
2010013290.tif 000005
【図４】
2010013290.tif 000006
【図５】
2010013290.tif 000007
【図６】
2010013290.tif 000008
【図７】
2010013290.tif 000009
【図８】
2010013290.tif 000010
【図９】
2010013290.tif 000011
【図１０】
2010013290.tif 000012
【図１１】
2010013290.tif 000013
【図１２】
2010013290.tif 000014
【図１３】
2010013290.tif 000015
【図１４】
2010013290.tif 000016
【図１５】
2010013290.tif 000017
【図１６】
2010013290.tif 000018
【図１７】
2010013290.tif 000019
【図１８】
2010013290.tif 000020
【図１９】
2010013290.tif 000021
【図２０】
2010013290.tif 000022
【図２１】
2010013290.tif 000023
【図２２】
2010013290.tif 000024
【図２３】
2010013290.tif 000025
【図２４】
2010013290.tif 000026
【手続補正書】
【提出日】平成21年3月30日(2009.3.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力データを圧縮して圧縮データを出力する圧縮処理装置であって、
前記入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する分割ユニットと、
前記複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する符号化ユニットと、
各々が複数のハフマン符号からなる第１および第２の符号化テーブルを保持するテーブル保持ユニットと、
前記第１および第２の符号化テーブルのうち、前記入力データのハフマン符号化に用いられていない一方の符号化テーブルを前記符号化対象データの出現頻度に応じて出現頻度が最も多い符号化対象データが最も短いハフマン符号に変換されるように更新する更新ユニットとを備え、
前記符号化ユニットは、前記圧縮データの圧縮率がしきい値以下であるとき、前記第１および第２の符号化テーブルのうちの他方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化し、前記圧縮率が前記しきい値よりも大きくなると、前記更新ユニットによって更新された一方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、圧縮処理装置。
【請求項２】
１つの部分集合に含まれる符号化対象データの出現頻度を調べて前記１つの部分集合に対応するハフマン符号化テーブルを作成する処理を前記複数の部分集合の全てについて実行し、前記複数のハフマン符号化テーブルを作成するテーブル作成ユニットをさらに備える、請求項１に記載の圧縮処理装置。
【請求項３】
前記更新ユニットは、全ての符号化対象データに対して出現頻度をカウントするとともに、１つの符号化対象データに対する出現頻度が最大値に達する毎に、前記出現頻度が前記最大値に達した順番が早いほど短い長さを有する新しいハフマン符号を前記１つの符号化対象データに対して割り当てる処理を前記全ての符号化対象データに対して実行し、前記一方の符号化テーブルを更新する、請求項１に記載の圧縮処理装置。
【請求項４】
前記更新ユニットは、前記符号化ユニットから出力された圧縮データに基づいて前記圧縮率を演算するとともに、その演算した圧縮率が前記しきい値よりも大きくなったとき、または前記全ての符号化対象データに対して前記新しいハフマン符号を割り当てたとき、前記符号化テーブルを切換えるための切換信号を生成して前記符号化ユニットへ出力し、
前記符号化ユニットは、前記切換信号に応じて前記符号化テーブルを切換え、その切換え後の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求項３に記載の圧縮処理装置。
【請求項５】
画像に含まれる対象物に基づいて前記画像を複数の画像に分割して複数の入力データを生成する画像分割ユニットをさらに備え、
前記分割ユニットは、前記複数の入力データのうちの１つの入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する処理を前記複数の入力データの全てに対して実行し、
前記符号化ユニットは、前記１つの入力データから分割された複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する処理を前記複数の入力データの全てに対して実行する、請求項１に記載の圧縮処理装置。
【請求項６】
入力データを圧縮して圧縮データを出力する圧縮処理方法であって、
分割ユニットが、前記入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する第１のステップと、
符号化ユニットが、前記複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する第２のステップと、
更新ユニットが、各々が複数のハフマン符号からなる第１および第２の符号化テーブルのうち、前記入力データのハフマン符号化に用いられていない一方の符号化テーブルを符号化対象データの出現頻度に応じて出現頻度が最も多い符号化対象データが最も短いハフマン符号に変換されるように更新する第３のステップとを備え、
前記第２のステップにおいて、前記符号化ユニットは、前記圧縮データの圧縮率がしきい値以下であるとき、前記第１および第２の符号化テーブルのうちの他方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化し、前記圧縮率が前記しきい値よりも大きくなると、前記一方の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、圧縮処理方法。
【請求項７】
テーブル作成ユニットが、１つの部分集合に含まれる符号化対象データの出現頻度を調べて前記１つの部分集合に対応するハフマン符号化テーブルを作成する処理を前記複数の部分集合の全てについて実行し、前記複数のハフマン符号化テーブルを作成する第４のステップをさらに備える、請求項６に記載の圧縮処理方法。
【請求項８】
前記第３のステップは、
前記更新ユニットが、全ての符号化対象データに対して出現頻度をカウントする第１のサブステップと、
前記更新ユニットが、１つの符号化対象データに対する出現頻度が最大値に達する毎に、前記出現頻度が前記最大値に達した順番が早いほど短い長さを有する新しいハフマン符号を前記１つの符号化対象データに対して割り当てる処理を前記全ての符号化対象データに対して実行し、前記一方の符号化テーブルを更新する第２のサブステップとを含む、請求項６に記載の圧縮処理方法。
【請求項９】
前記第３のステップは、
前記更新ユニットが、前記符号化ユニットから出力された圧縮データに基づいて前記圧縮率を演算する第３のサブステップと、
前記更新ユニットが、前記第３のサブステップにおいて演算された圧縮率が前記しきい値よりも大きくなったとき、または前記全ての符号化対象データに対して前記新しいハフマン符号を割り当てたとき、前記符号化テーブルを切換えるための切換信号を生成して前記符号化ユニットへ出力する第４のサブステップとをさらに含み、
前記第２のステップにおいて、前記符号化ユニットは、前記切換信号に応じて前記符号化テーブルを切換え、その切換え後の符号化テーブルに基づいて前記複数のハフマン符号化テーブルを作成しながら前記各部分集合毎に前記符号化対象データをハフマン符号化する、請求項８に記載の圧縮処理方法。
【請求項１０】
画像分割ユニットが、画像に含まれる対象物に基づいて前記画像を複数の画像に分割して複数の入力データを生成する第４のステップをさらに備え、
前記第１のステップにおいて、前記分割ユニットは、前記複数の入力データのうちの１つの入力データからなる母集合に含まれる複数の要素を各要素の特徴を用いて複数の部分集合に分割する処理を前記複数の入力データの全てに対して実行し、
前記第２のステップにおいて、前記符号化ユニットは、前記１つの入力データから分割された複数の部分集合に対応して設けられた複数のハフマン符号化テーブルを用いて各部分集合毎に符号化対象データをハフマン符号化し、前記圧縮データを出力する処理を前記複数の入力データの全てに対して実行する、請求項６に記載の圧縮処理方法。
【国際調査報告】
2010013290.tif 000027
2010013290.tif 000028