(57)【要約】【課題】出願頻度を記憶するカウンタのメモリ容量を低減できるようにした適応型可変長符号化装置、適応型可変長符号化方法及び適応型可変長符号化プログラムを提供する。【解決手段】入力データを記憶するデータ記憶手段２と、入力データと符号化データとの関係を表す符号化テーブル４と、符号化テーブルを参照して入力データを符号化する符号化手段３と、入力データをいくつかのグループに分割するグループ化手段５と、グループ化された入力データの各グループ毎のデータ出現頻度を演算するグループデータ出現頻度演算手段６と、グループデータ出現頻度に基づいて符号化テーブルを更新する符号化テーブル更新手段７とで適応型可変長符号化装置を構成する。【選択図】        図１
2005012496.tif 000002
【特許請求の範囲】
【請求項１】
データの出現頻度に基づいて作成された符号化テーブルを参照して前記データの符号化を行う適応型可変長符号化装置であって、入力データを記憶するデータ記憶手段と、前記入力データと符号化データとの関係を表す符号化テーブルと、該符号化テーブルを参照して前記データ記憶手段に記憶された入力データを符号化する符号化手段と、前記入力データをいくつかのグループに分割するグループ化手段と、前記グループ化された入力データの各グループ毎のデータ出現頻度を演算するグループデータ出現頻度演算手段と、前記グループデータ出現頻度に基づいて前記符号化テーブルを更新するための符号化テーブル更新手段とを有することを特徴とする適応型可変長符号化装置。
【請求項２】
前記グループ化手段は、入力データをデータ値の大きさの順に所定の予め決められた間隔毎にグループ化することを特徴とする請求項１に係る適応型可変長符号化装置。
【請求項３】
前記グループ化手段は、入力データをデータ値の大きさの順に前記データの態様を解析するデータ解析手段による解析結果に基づいて決められる間隔毎にグループ化することを特徴とする請求項１に係る適応型可変長符号化装置。
【請求項４】
前記グループデータ出現頻度に基づいて、入力データの各データの有する出現頻度を予測するデータ出現頻度予測手段を、更に有することを特徴とする請求項１に係る適応型可変長符号化装置。
【請求項５】
前記符号化テーブル更新手段は、所定のタンミングで前記グループデータ出現頻度演算手段によるグループデータ出現頻度に基づいて符号化テーブルを更新することを特徴とする請求項１に係る適応型可変長符号化装置。
【請求項６】
前記所定のタンミングは、フレーム毎、ライン毎又はキーフレーム毎であることを特徴とする請求項５に係る適応型可変長符号化装置。
【請求項７】
前記入力データを符号化する際に用いた符号化テーブルのデータを符号化データに埋め込む符号化テーブルデータ埋め込み手段を更に備えていることを特徴とする請求項１〜６のいずれか１項に係る適応型可変長符号化装置。
【請求項８】
データの出現頻度に基づいて作成された符号化テーブルを参照して前記データの符号化処理を行う適応型可変長符号化方法であって、入力データを記憶するステップと、前記記憶された入力データをいくつかのグループに分割するステップと、グループ化された入力データの各グループ毎のデータ出現頻度を演算するステップと、各グループ毎のデータ出現頻度に基づいて前記符号化テーブルを更新するステップと、前記更新された符号化テーブルを参照して前記記憶された入力データを符号化するステップとからなることを特徴とする適応型可変長符号化方法。
【請求項９】
更に、入力データを符号化する際に用いた符号化テーブルのデータを符号化データに埋め込むステップを有することを特徴とする請求項８に係る適応型可変長符号化方法。
【請求項１０】
コンピュータに対して、データの出現頻度に基づいて作成された符号化テーブルを参照して前記データの符号化処理を実行させるための適応型可変長符号化プログラムであって、入力データを記憶する手順と、前記記憶された入力データをいくつかのグループに分割する手順と、グループ化された入力データの各グループ毎のデータ出現頻度を演算する手順と、各グループ毎のデータ出現頻度に基づいて前記符号化テーブルを更新する手順と、前記更新された符号化テーブルを参照して前記記憶された入力データを符号化する手順とを実行させることを特徴とする適応型可変長符号化プログラム。
【請求項１１】
更に、入力データを符号化する際に用いた符号化テーブルのデータを符号化データに埋め込む手順を有することを特徴とする請求項１０に係る適応型可変長符号化プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、画像データ等のデータの符号長を適応的に変えて圧縮した符号化データを生成するための適応型可変長符号化装置、適応型可変長符号化方法及び適応型可変長符号化プログラムに関する。
【０００２】
【従来の技術】
【特許文献１】特開平８−３１６８４８号公報
【０００３】
一般に、画像データ等のデータを記録媒体に記録する場合などにおいては、データの圧縮処理がなされている。この圧縮処理の手法には種々の手法があるが、その中の代表的な手法として、例えば特開平８−３１６８４８号公報（特許文献１）に開示されているような、データの出現頻度を利用したハフマン符号化方式（適応型可変長符号化方式）がある。この方式においては、出現頻度が高いデータをビット長の短い符号化データとし、逆に出現頻度が低いデータはビット長の長い符号化データとすることにより、統計的にデータの圧縮効率を高めようとしている。このハフマン符号化の際は、リアルタイムに演算して符号化することも可能であるが、通常は予め用意した符号化テーブルを参照する場合が多い。テーブル参照の場合、１つのテーブルを使い続ける方式や複数のテーブルから選択する方式があるが、中でも優れた方式の１つに、符号化対象データの発生頻度を値別に計数した結果を基に符号化テーブルを適宜更新する適応型ハフマン符号化方式がある。これによれば、符号化対象データの発生傾向が変化したとしても、それに応じたテーブルを用意できるため、更なる高効率圧縮が望める。
【０００４】
【発明が解決しようとする課題】
しかしながら、この符号化方式においては、画像データ等のデータが取り得るデータ値の大きさ、例えば画像データを８ビットとすると、０から２５５  までのデータ値毎に、その最大出現頻度をカウント可能なメモリ、上記例では  ２５６個のメモリが必要になり、最近のデジタルカメラなどのように、画素数が数百万画素にも及ぶ撮像素子からの画像データを符号化するような場合は、カウンタのメモリ容量が極めて膨大なものとなる。例えば、画素数が  １００万画素で各画素あたりの画像データが８ビットとすると、従来の符号化方式では、符号化テーブル作成のために２０ビットのカウンタが  ２５６個も必要になる。最大カウント値を制限してカウンタのメモリ容量をある程度小さくすることもできるが、それでも、ある程度のメモリ容量のカウンタを備えていないと符号化精度が低下してしまう。
【０００５】
本発明は、従来の適応型可変長符号化方式における上記問題点を解消するためになされたもので、出現頻度を記憶するカウンタのメモリ容量を低減できるようにした適応型可変長符号化装置、適応型可変長符号化方法及び適応型可変長符号化プログラムを提供することを目的とする。
【０００６】
【課題を解決するための手段】
上記問題点を解決するため、請求項１に係る発明は、データの出現頻度に基づいて作成された符号化テーブルを参照して前記データの符号化を行う適応型可変長符号化装置であって、入力データを記憶するデータ記憶手段と、前記入力データと符号化データとの関係を表す符号化テーブルと、該符号化テーブルを参照して前記データ記憶手段に記憶された入力データを符号化する符号化手段と、前記入力データをいくつかのグループに分割するグループ化手段と、前記グループ化された入力データの各グループ毎のデータ出現頻度を演算するグループデータ出現頻度演算手段と、前記グループデータ出現頻度に基づいて前記符号化テーブルを更新するための符号化テーブル更新手段とを有することを特徴とするものである。
【０００７】
請求項２に係る発明は、請求項１に係る適応型可変長符号化装置において、前記グループ化手段は、入力データをデータ値の大きさの順に所定の予め決められた間隔毎にグループ化することを特徴とするものである。
【０００８】
請求項３に係る発明は、請求項１に係る適応型可変長符号化装置において、前記グループ化手段は、入力データをデータ値の大きさの順に前記データの態様を解析するデータ解析手段による解析結果に基づいて決められる間隔毎にグループ化することを特徴とするものである。
【０００９】
請求項４に係る発明は、請求項１に係る適応型可変長符号化装置において、前記グループデータ出現頻度に基づいて、入力データの各データの有する出現頻度を予測するデータ出現頻度予測手段を、更に有することを特徴とするものである。
【００１０】
請求項５に係る発明は、請求項１に係る適応型可変長符号化装置において、前記符号化テーブル更新手段は、所定のタンミングで前記グループデータ出現頻度演算手段によるグループデータ出現頻度に基づいて符号化テーブルを更新することを特徴とするものである。
【００１１】
請求項６に係る発明は、請求項５に係る適応型可変長符号化装置において、前記所定のタンミングは、フレーム毎、ライン毎又はキーフレーム毎であることを特徴とするものである。
【００１２】
請求項７に係る発明は、請求項１〜６のいずれか１項に係る適応型可変長符号化装置において、前記入力データを符号化する際に用いた符号化テーブルのデータを符号化データに埋め込む符号化テーブルデータ埋め込み手段を更に備えていることを特徴とするものである。
【００１３】
請求項８に係る発明は、データの出現頻度に基づいて作成された符号化テーブルを参照して前記データの符号化処理を行う適応型可変長符号化方法であって、入力データを記憶するステップと、前記記憶された入力データをいくつかのグループに分割するステップと、グループ化された入力データの各グループ毎のデータ出現頻度を演算するステップと、各グループ毎のデータ出現頻度に基づいて前記符号化テーブルを更新するステップと、前記更新された符号化テーブルを参照して前記記憶された入力データを符号化するステップとからなることを特徴とするものである。
【００１４】
請求項９に係る発明は、請求項８に係る適応型可変長符号化方法において、更に、入力データを符号化する際に用いた符号化テーブルのデータを符号化データに埋め込むステップを有することを特徴とするものである。
【００１５】
請求項１０に係る発明は、コンピュータに対して、データの出現頻度に基づいて作成された符号化テーブルを参照して前記データの符号化処理を実行させるための適応型可変長符号化プログラムであって、入力データを記憶する手順と、前記記憶された入力データをいくつかのグループに分割する手順と、グループ化された入力データの各グループ毎のデータ出現頻度を演算する手順と、各グループ毎のデータ出現頻度に基づいて前記符号化テーブルを更新する手順と、前記更新された符号化テーブルを参照して前記記憶された入力データを符号化する手順とを実行させるように構成するものである。
【００１６】
請求項１１に係る発明は、請求項１０に係る適応型可変長符号化プログラムにおいて、更に、入力データを符号化する際に用いた符号化テーブルのデータを符号化データに埋め込む手順を有することを特徴とするものである。
【００１７】
【発明の実施の形態】
次に、実施の形態について説明する。図１は、本発明に係る適応型可変長符号化装置の実施の形態を示すブロック構成図であり、また適応型可変長符号化方法の実施の形態を説明するための説明図でもある。なお、この実施の形態は、画像データを符号化する態様を示しているが、符号化の対象となるデータは画像データに限らない。図１において、１は被写体像を光電変換して画像信号を生成する撮像素子、２は撮像素子１からの撮像信号を図示しないＡ／Ｄ変換器でＡ／Ｄ変換した画像データを記憶するデータ記憶手段、３は画像データをデータの出現頻度に基づいて符号化し符号化データとして出力する符号化手段、４は画像データと符号化データとの関係を示す符号化手段３で用いる符号化テーブルで、ハフマン・ラングレスなどのエントロピー符号化テーブルや、ルックアップテーブルなどが用いられる。５は画像データをいくつかのグループに分割するグループ化手段、６はグループ化手段５でグループ化されたデータの各グループ毎のデータ出現頻度を演算するグループデータ出現頻度演算手段、７はグループデータ出現頻度演算手段６により得られたグループデータ出現頻度に基づいて符号化テーブルを更新する符号化テーブル更新手段である。
【００１８】
次に、このように構成されている適応型可変長符号化装置の動作について説明する。撮像素子１で生成されＡ／Ｄ変換された画像データは、一旦データ記憶手段２に格納される。そして、データ記憶手段２に格納された画像データは、符号化手段３に入力すると同時にグループ化手段５にも入力する。この際、画像データはデータ記憶手段２に一旦格納することはせず、直接符号化手段３及びグループ化手段５に入力させるようにしてもよい。また画像データの符号化手段３とグループ化手段５への入力は同時でなく、ずらして入力させるようにしてもよい。
すなわち、グループ化手段５及びグループデータ出現頻度演算手段６における処理時間を必要とし、その演算結果に基づいて符号化テーブルを更新して、それが符号化手段３に反映されるまでタイムラグがあるので、符号化手段３への入力よりグループ化手段５への入力を先行させた方が、符号化手段３における符号化処理の際に、入力画像データに最適な符号化テーブルをリアルタイムに用意できるようになる。このように符号化手段３への入力を遅らすには、デレイバッファを介して画像データを入力させるようにすればよい。
【００１９】
グループ化手段５においては、符号化手段３で符号化の対象となるデータのデータ値を特定の条件でグループ化する。例えば、入力データを８ビットとし、０〜２５５  の値が出現するとし、例えば図２に示すように、０〜１５の符号化対象値をグループ１，１６〜３１の符号化対象値をグループ２，・・・・・  ２４０〜２５５  の符号化対象値をグループ１６のようにグループ分けを行い、グループデータ出現頻度演算手段６で各グループ内での発生頻度をカウントする。
【００２０】
このようにグループ分けして発生頻度をカウントすることにより、カウンタを１／１６にすることができ、カウンタのメモリ容量を低減することができる。もっとも、このグループ分けにより情報を減らすことになるので、精度は低下するが、一般的な画像データや動画データの発生頻度の分布からみて、さほど大きな問題にはならない。
【００２１】
上記グループ化例では、入力データをデータ値の大きさの順に等間隔で単純に１６分割したものを示したが、この手法より精度のよいグループ化手法として、次のような手法がある。すなわち、出現頻度の高い値ほど小規模のグループ化をした方が、より精度のよい適切なテーブル更新ができる。したがって、静止画や動画などの場合は、空間的な差分値あるいはフレーム差分値は、通常零に近い値ほど発生頻度が高いので、０〜１の符号化対象値をグループ１，２〜５の符号化対象値をグループ２，６〜１１の符号化対象値をグループ３，・・・・・  １９２〜２５５の符号化対象値をグループ１６というようにグループ分けを行う。これにより、比較的精度のよいグループ分けを行うことができる。なお、この際、入力データの発生頻度の特性を解析する手段を別途設けておいて、その解析手段の解析結果に基づいて、グループ化の間隔を設定するようにすれば、入力データにより適したテーブル更新が可能となる。
【００２２】
また、上記グループ分け手法では、固定的に各グループ内の符号化対象値の個数を設定したものについて説明したが、グループ分けの条件をユーザが自由に設定可能に構成するのも有効である。すなわち、例えば、グループの個数は１６個と固定しておき、グループ１にはｎ１個、グループ１にはｎ２個、・・・・・グループ１６にはｎ１６個の符号化対象値が属するようにし、各グループの符号化対象値ｎ１〜ｎ１６を、レジスタで変更可能にするように構成することもできる。
【００２３】
例えば、符号化対象値が零を中心にして分布していても、例えば図３の（Ａ）に示すように零中心に集中して分布している場合と、図３の（Ｂ）に示すように零中心ではあるが、なだらかに分布している場合もあるので、図３の（Ａ）に示す分布の場合には、零を中心とした細かいグループ分けを行った方が高精度となるが、図３の（Ｂ）に示す分布の場合には、零を中心とした細かいグループ分けを行うと、他のなだらかな分布領域に対する影響が大きくなり、不適切なグループ分けとなる。したがって、このような場合には、ユーザが適切に任意にグループの規模を変えられるように構成しておいた方が好適である。
【００２４】
以上のようにして、グループ化手段５でグループ化されたデータは、グループデータ出現頻度演算手段６で各グループ毎にデータ出現頻度がカウントされる。
そして、符号化テーブル更新手段７では、グループデータ出現頻度演算手段６で得られた出現頻度に基づいて決められた符号化テーブルと現在選択されている符号化テーブルとを対比し、出現頻度に基づいて決められた新たな符号化テーブルが現在選択されているものと異なる場合は、符号化テーブルの更新に適切なタイミングを見計らって、新たな符号化テーブルを、符号化手段３で使用する符号化テーブルとして選択更新する。符号化手段３は、更新された符号化テーブルを参照しながら符号化処理を行う。
【００２５】
前記符号化テーブル更新手段７による更新のタイミングとしては、種々の設定が可能であるが、例えばライン毎、フレーム毎、キーフレーム（他のフレームの情報を用いずに符号化処理を行うフレーム）毎のタイミングで更新を行う。また更新のタイミングは、符号化テーブル更新手段７が自動で判断して更新するようにしてもよい。例えば、現在用いられている符号化テーブルにおいて、最も短い符号を割り振っている入力データが属するグループＡの符号化対象値の出現頻度が、他のグループＢより低くなった場合には、符号化テーブル更新手段７が、この状態を検出して、グループＢに属する入力データに最も短い符号を割り振る符号化テーブルに自動的に更新するように構成する。
【００２６】
上記実施の形態においては、グループ化手段５でグループ化したデータの各グループ毎のデータ出現頻度に対応した符号化テーブルに更新するようにしたものを示したが、グループ分けによるデータ出現頻度には連続性がなく荒さがあるので、この荒さを緩和するため、図４に示すように、線形補間などによる改善手法を用いることができる。すなわち、別途データ出現頻度予測手段を設け、線形補間により、点線で示すように個別の符号化対象値に対する出現頻度を予測し、その予測値に対応させてテーブル更新を行う。これにより、グループ分けによる荒さが緩和されて、精度のよい符号化テーブルの再構築が可能となる。
【００２７】
また、上記実施の形態において、符号化手段３において符号化データを出力する際に、図５の（Ａ）に示すように、符号化データ列中に符号化手段３で用いた符号化テーブルのデータを埋め込んで、復号化のためのフォーマットで符号化データを構成するようにしてもよい。この場合、符号化手段中に埋め込み機能をもたせることになる。符号化テーブルデータの埋め込みのタイミングは、符号化テーブルの更新のタイミングで、つまりライン単位、あるいはフレーム単位などのタイミングで、符号化データ列中に埋め込まれ、符号化データが構成される。なお、この際、埋め込まれる符号化テーブルデータとしては、任意の手段で圧縮されたデータを用いると、データサイズを無駄に増大させずに済む。
【００２８】
上記埋め込み手法により符号化テーブルデータを埋め込んだ符号化データでは、どこに符号化テーブルデータが挿入されているかデータフォーマット的にわかりずらいので、その点を考慮して、図５の（Ｂ）に示すように、フレーム単位で、フレームヘッダに、そのフレームの符号化データの符号化の際に用いた複数の符号化テーブルデータをまとめて書き込み、符号化データ列中には符号化テーブルの更新点を示す情報のみを挿入しておく手法もある。
【００２９】
更に、図５の（Ｃ）に示すように、フレームヘッダに複数の符号化テーブルデータをまとめて書き込むと同時に、符号化テーブルを更新する座標データを書き込んでおき、符号化データ列中には何も挿入せず連続的に出力させるように構成してもよい。
【００３０】
以上のように、符号化データ中に符号化テーブル情報を埋め込んだフォーマットで符号化データを構成した場合は、符号化データ中に埋め込まれた符号化テーブル情報やタイミング情報をもとに、復号化処理が行われる。
【００３１】
上記実施の形態に係る適応型可変長符号化装置による画像データ等のデータの符号化処理は、ハードウェアによる処理に限らず、上記各構成手段による各処理手順をプログラム化し、コンピュータに実行させるソフトウェア処理とすることも、勿論可能である。
【００３２】
【発明の効果】
以上実施の形態に基づいて説明したように、本発明によれば、入力データをいくつかにグループ化して、グループ単位で出現頻度を算出するようにしているので、出現頻度を記憶するカウンタのメモリ容量の低減可能な適応型可変長符号化装置、適応型可変長符号化方法及び適応型可変長符号化プログラムを実現することができる。
【図面の簡単な説明】
【図１】本発明に係る適応型可変長符号化装置の実施の形態を示すブロック構成図である。
【図２】図１に示した実施の形態におけるグループ化手段によるグループ化の態様例を示す図である。
【図３】符号化対象値が零を中心にして分布している場合の発生頻度態様を示す図である。
【図４】グループ化によるデータ出現頻度を線形補間することにより、個別の符号化対象値に対する出現頻度を予測する態様を示す図である。
【図５】符号化手段から出力される符号化データに符号化テーブルデータを埋め込んだ態様を示す図である。
【符号の説明】
１  撮像素子
２  データ記憶手段
３  符号化手段
４  符号化テーブル
５  グループ化手段
６  グループデータ出現頻度演算手段
７  符号化テーブル更新手段
【図１】
2005012496.tif 000003
【図２】
2005012496.tif 000004
【図３】
2005012496.tif 000005
【図４】
2005012496.tif 000006
【図５】
2005012496.tif 000007