(57)【要約】  【課題】  より効率的な符号化処理を実現する符号化装置を提供する。  【解決手段】  符号化装置２は、バッファリングの負荷を削減するために、入力されたデータファイルに依存しない固定的符号化処理と、入力されたデータファイルに依存する可変的符号化処理とを直列に組み合わせる。このうち固定的符号化処理は、バッファリング処理の前段で実行することにより、バッファリングすべきデータのデータサイズを小さくして、バッファリングの負荷を削減する。そして、バッファリングされたシンボルに対しては、可変的符号化処理を追加的に行うことにより、可変的符号化処理と同様の圧縮率を実現する。【選択図】図３
2007324971.tif 000002
【特許請求の範囲】
【請求項１】
未処理のデータに依存しないエントロピー符号化方式を用いて、入力されたデータファイルを符号化し、中間符号を生成する第１の符号生成手段と、
前記第１の符号生成手段により生成された中間符号に基づいて、入力されたデータファイルの出力符号を生成する第２の符号生成手段と
を有する符号化装置。
【請求項２】
前記第２の符号生成手段は、未処理のデータに依存する符号化方式を用いて、前記出力符号を生成する
請求項１に記載の符号化装置。
【請求項３】
前記第２の符号生成手段は、データファイル全体に対する統計処理に基づいて、前記出力符号を生成する
請求項１に記載の符号化装置。
【請求項４】
前記第１の符号生成手段による符号化処理の少なくとも一部と並行して、前記統計処理を行う統計処理手段
をさらに有し、
前記第２の符号生成手段は、前記統計処理手段による統計処理の結果に基づいて、前記出力符号を生成する
請求項３に記載の符号化装置。
【請求項５】
前記第１の符号生成手段は、前記第２の符号生成手段よりも大きなデータ単位で、符号化処理を行う
請求項１に記載の符号化装置。
【請求項６】
前記第１の符号生成手段は、予め設計された固定符号表を用いて、入力されたデータファイルを符号化し、
前記第２の符号生成手段は、入力されたデータファイルそれぞれに応じて設計される可変符号表を用いて、前記出力符号を生成する
請求項１に記載の符号化装置。
【請求項７】
前記第１の符号生成手段により生成された中間符号を記憶する記憶手段
をさらに有し、
前記第２の符号生成手段は、前記記憶手段に記憶された中間符号を符号化して、前記出力符号を生成する
請求項１又は４に記載の符号化装置。
【請求項８】
未処理のデータに依存しないエントロピー符号化方式を用いて、入力されたデータファイルを符号化し、中間符号を生成し、
生成された前記中間符号に基づいて、入力されたデータファイルの出力符号を生成する
符号化方法。
【請求項９】
未処理のデータに依存しないエントロピー符号化方式を用いて、入力されたデータファイルを符号化し、中間符号を生成するステップと、
生成された前記中間符号に基づいて、入力されたデータファイルの出力符号を生成するステップと
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データファイルを符号化する符号化方法に関する。
【背景技術】
【０００２】
例えば、特許文献１には、求める限定色の色数を指定して、カラー画像の色分布より目的の数の限定色を抽出し、カラー画像より各限定色に割り当てられる画素数の頻度分布を計数し、頻度分布を使って生起確率を求め限定色の各々にハフマン符号を割り当て、画素ごとに、画素の限定色が隣接画素の限定色と同一であれば位置関係の符号を、それ以外は限定色の符号を割り当て、圧縮データとして保存し、最後に圧縮データの付加情報の保存処理を行う方法が開示されている。
【特許文献１】特開平６−２７４６０９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、上述した背景からなされたものであり、より効率的な符号化処理を実現する符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
［符号化装置］
上記目的を達成するために、本発明にかかる符号化装置は、未処理のデータに依存しないエントロピー符号化方式を用いて、入力されたデータファイルを符号化し、中間符号を生成する第１の符号生成手段と、前記第１の符号生成手段により生成された中間符号に基づいて、入力されたデータファイルの出力符号を生成する第２の符号生成手段とを有する。
【０００５】
好適には、前記第２の符号生成手段は、未処理のデータに依存する符号化方式を用いて、前記出力符号を生成する。
【０００６】
好適には、前記第２の符号生成手段は、データファイル全体に対する統計処理に基づいて、前記出力符号を生成する。
【０００７】
好適には、前記第１の符号生成手段による符号化処理の少なくとも一部と並行して、前記統計処理を行う統計処理手段をさらに有し、前記第２の符号生成手段は、前記統計処理手段による統計処理の結果に基づいて、前記出力符号を生成する。
【０００８】
好適には、前記第１の符号生成手段は、前記第２の符号生成手段よりも大きなデータ単位で、符号化処理を行う。
【０００９】
好適には、前記第１の符号生成手段は、予め設計された固定符号表を用いて、入力されたデータファイルを符号化し、前記第２の符号生成手段は、入力されたデータファイルそれぞれに応じて設計される可変符号表を用いて、前記出力符号を生成する。
【００１０】
好適には、前記第１の符号生成手段により生成された中間符号を記憶する記憶手段をさらに有し、前記第２の符号生成手段は、前記記憶手段に記憶された中間符号を符号化して、前記出力符号を生成する。
【００１１】
［符号化方法］
また、本発明にかかる符号化方法は、未処理のデータに依存しないエントロピー符号化方式を用いて、入力されたデータファイルを符号化し、中間符号を生成し、生成された前記中間符号に基づいて、入力されたデータファイルの出力符号を生成する。
【００１２】
［プログラム］
また、本発明にかかるプログラムは、未処理のデータに依存しないエントロピー符号化方式を用いて、入力されたデータファイルを符号化し、中間符号を生成するステップと、生成された前記中間符号に基づいて、入力されたデータファイルの出力符号を生成するステップとをコンピュータに実行させる。
【発明の効果】
【００１３】
本発明の符号化装置によれば、より効率的な符号化処理を実現することができる。
【発明を実施するための最良の形態】
【００１４】
まず、本発明の理解を助けるために、その背景及び概略を説明する。
ハフマン符号は、実現構成が簡単なので、広く使われている符号化方式である。本来は、入力されたデータファイル毎に、各入力シンボルの出現頻度分布を求め、その分布に応じた符号表（可変符号表）を設計する（以下、これを可変的ハフマン符号という）。
しかし、国際標準JPEGをはじめ、一般によく使われているハフマン符号では、事前に想定された出現頻度分布に対して設計した符号表（固定符号表）を、固定的に適用することが多い（以下、これを固定的ハフマン符号という）。
【００１５】
画像圧縮にハフマン符号を適用する場合には、前段でソースコーディングと呼ぶ変換処理をかけて、符号化対象となるシンボルを生成する。このとき後段の符号化処理が固定的ハフマン符号を適用すると、ソースコーダの出力（シンボル）が想定出現頻度に合わない場合に圧縮率が低下する。
そのため、例えば、ＣＧ画像に対しては効率的であるが、写真画像に対しては比較的効率が悪い、といった偏ったソースコーダは使いづらいという問題があった。
一方、可変的ハフマン符号化処理では、１パス目でシンボルの統計をとり、２パス目で符号化するため、処理速度が固定的ハフマン符号を適用する場合よりも遅い。また、可変的ハフマン符号を適用する場合には、２パス処理のためには入力データを丸ごとバッファリングすることが必要となり、処理時間とメモリコストがネックになる。
【００１６】
図１は、可変的ハフマン符号を適用する符号化プログラム９の機能構成を例示する図である。
可変的ハフマン符号化の処理を遅くする原因のひとつは、バッファリング処理にある。特に画像圧縮に可変的ハフマン符号を適用する場合、ソースコーダ９００によるソースコーディングをかけてシンボルを生成することが多いが、画像とは別にこのシンボルをシンボルバッファ９１０に記憶しておく必要がある。
例えば、予測符号化方式のソースコーディングを行い場合、ソースコーダ９００は、入力された画像データの画素値を予測誤差値に変換し、この予測誤差値をシンボルとする。この予測誤差値は、符号表が作成されるまでの間、シンボルバッファ９１０にバッファリングされる。すなわち、シンボル計数部９２０は、ソースコーダ９００から出力されるシンボルを計数し、符号表生成部９３０は、シンボル計数部９２０による計数結果（出現頻度）に基づいて可変符号表を生成し、ハフマン符号化部９４０は、符号表生成部９３０により符号表が生成されたことを条件として、シンボルバッファ９１０からシンボルを読み出し、読み出されたシンボルを符号化していく。
バッファリングされる予測誤差値は、画素数分だけあるので、シンボルバッファ９１０は画像１ページ分のメモリを要し、このメモリの書込み及び読出しも１ページ分丸ごと必要になる。特に、予測符号化の場合、ソースコーダ９００の処理は軽く、並列化も比較的容易なので、バッファリングの相対的処理負荷が高くなる。
【００１７】
そこで、本実施形態における符号化装置２は、バッファリングの負荷を削減するために、入力されたデータファイルに依存しない固定的符号化処理（例えば、固定的ハフマン符号化処理）と、入力されたデータファイルに依存する可変的符号化処理（例えば、入力画像に適応した可変的ハフマン符号化処理）とを直列に組み合わせる。このうち固定的符号化処理は、バッファリング処理の前段で実行することにより、バッファリングすべきデータのデータサイズを小さくして、バッファリングの負荷を削減する。そして、バッファリングされたシンボル（固定的符号化処理で符号化された符号）に対しては、可変的符号化処理を追加的に行うことにより、可変的符号化処理と同様の圧縮率を実現する。なお、以下の説明では、固定的符号化処理で符号化された符号（バッファリングされる符号）を中間符号という。
【００１８】
なお、固定的符号化処理は以下の条件を満たすことが望ましい。
［条件１］
データファイル（本例では画像データ）の大局的性質によらない処理であること。より具体的には、少なくとも、未処理のデータ（符号化されていない部分データ）に依存しない符号化処理であること。換言すると、１パスで処理できるような局所的性質の限度で、他のデータに依存関係を有する符号化処理であること。
［条件２］
可変的符号化処理と比較して、比較的高速であること。
［条件３］
固定的符号化処理と可変的符号化処理とを組み合わせることによるオーバーヘッドが少ないこと。
【００１９】
例えば、条件１に関して、可変的ハフマン符号の生成に必要なページ全体の統計処理は大局的性質である。逆に、コンテクストモデリングは後続のデータ（すなわち、未処理のデータ）に依存しないため局所的性質である。
条件２に関して、バッファリングの負荷削減という目的から要請されるものであり、可変的符号化処理は、ビットシフトなどの処理で重くならざるを得ないので、固定的符号化処理は、軽いほうが望ましい。ただし、固定的符号化処理と可変的符号化処理の負荷の和が、もとのエントロピー符号化の処理負荷と同程度であれば、多少固定的符号化処理がバランス的に重くなっても構わない。
条件３に関して、処理単位を揃えることなどがこの条件を満たす手段として考えられる。例えば、可変的符号化処理で可変的ハフマン符号を適用するのに、固定的符号化処理で算術符号を適用する場合に、可変的符号化処理の前に算術符号化の復号化処理が必要となり、オーバーヘッドが大きくなりすぎる。
上記条件を満たす固定的符号化処理及び可変的符号化処理を組み合わせることにより、バッファリングすべきデータ量が削減できるので、バッファリングの処理時間が減り、メモリサイズも統計的に削減することができるようになる。
【００２０】
［ハードウェア構成］
まず、本実施形態における符号化装置２のハードウェア構成を説明する。
図２は、本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
図２に例示するように、符号化装置２は、ＣＰＵ２０２及びメモリ２０４などを含む制御装置２０、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、並びに、ＬＣＤ表示装置あるいはＣＲＴ表示装置及びキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２６から構成される。
符号化装置２は、例えば、プリンタ装置１０に設けられた処理装置であり、通信装置２２又は記録装置２４などを介して画像データを取得し、取得された画像データを符号化する。
【００２１】
［符号化プログラム］
図３は、制御装置２０（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
図３に例示するように、符号化プログラム５は、ソースコーダ５００、第１符号部５１０、シンボル計数部５２０、中間符号記憶部５３０、符号表生成部５４０、及び第２符号部５５０を有する。
符号化プログラム５は、例えば、図２に例示した記録媒体２４０に記録され、この記録媒体２４０を介して、制御装置２０（図２）に供給される。
なお、本例では、画像データを符号化する場合を具体例として説明する。
【００２２】
符号化プログラム５において、ソースコーダ５００は、入力されたデータファイルに基づいて、エントロピー符号化処理の対象となるシンボルを生成し、生成されたシンボルを第１符号部５１０及びシンボル計数部５２０に出力する。
本例のソースコーダ５００は、既定の予測方法を用いて注目画素の画素値を予測し、この予測値と注目画素値との差分値（以下、予測誤差値）を算出し、算出された予測誤差値をシンボルとする。なお、本例のソースコーダ５００は、算出された予測誤差値が０である場合（すなわち、予測が的中した場合）には、予測的中の連続数（ラン）を計数し、計数された連続数（予測誤差値が連続して０となる回数）をシンボルとする。
【００２３】
第１符号部５１０は、ソースコーダ５００から入力されたシンボルを、未処理のデータに依存しないエントロピー符号化方式（例えば、予め設計された固定符号表を用いた符号化方式）を用いて符号化し、生成された符号（すなわち、中間符号）を中間符号記憶部５３０に出力する。
本例の第１符号部５１０は、ソースコーダ５００から入力されたシンボルを、固定的ハフマン符号で符号化して、中間符号を生成する。
【００２４】
シンボル計数部５２０は、ソースコーダ５００から入力されたシンボルを計数し、計数結果に基づいて既定の統計処理を行い、統計処理の結果を符号表生成部５４０に出力する。シンボル計数部５２０は、本発明にかかる統計処理手段の一例であり、符号表生成に要する統計処理を行う。
本例のシンボル計数部５２０は、ソースコーダ５００から入力される全シンボルの出現頻度を計数して、各シンボル値の出現頻度分布を生成する。
【００２５】
中間符号記憶部５３０は、第１符号部５１０から入力された中間符号をメモリに記憶し、記憶された中間符号を第２符号部５５０に供給する。
本例の中間符号記憶部５３０は、少なくとも、符号表生成部５４０により可変的ハフマン符号の符号表が生成されるまでの間、第１符号部５１０により符号化された中間符号をバッファリングし、第２符号部５５０が可変的符号化処理を実行可能になったことを条件として、バッファリングしている中間符号を第２符号部５５０に出力する。
【００２６】
符号表生成部５４０は、シンボル計数部５２０による統計処理の結果に基づいて、可変的符号化処理に用いる符号表を生成し、生成された符号表を第２符号部５５０に出力する。符号表生成部５４０により生成される符号表は、入力されるデータファイルそれぞれに応じて設計されるものであり、可変符号表とよぶ。
本例の符号表生成部５４０は、各シンボルの出現頻度分布に応じて、可変的ハフマン符号の符号表を生成する。
【００２７】
第２符号部５５０は、符号表生成部５４０から入力された可変符号表と、中間符号記憶部５５０に記憶されている中間符号とに基づいて、入力されたデータファイルの出力符号を生成する。
本例の第２符号部５５０は、符号表生成部５４０から入力された可変的ハフマン符号の符号表を用いて、中間符号記憶部５３０にバッファリングされている中間符号を順に符号化して、出力符号を生成する。
【００２８】
図４は、ソースコーダ５００（図３）によるソースコーディングを説明する図である。
図４（Ａ）に例示するように、ソースコーダ５００は、注目画素Ｘのシンボルを生成する場合に、走査方向上流の画素Ａ〜Ｃのいずれか（すなわち、既処理の画素）を参照して、予測誤差値を算出する。
例えば、ソースコーダ５００は、図４（Ｂ）に例示する（式１）を用いて、予測誤差（シンボル）を算出する。すなわち、注目画素Ｘの画素値と、主走査方向直前の画素Ａの画素値との差分値が、予測誤差値（シンボル）となる。
また、ソースコーダ５００は、図４（Ｂ）に例示する（式２）を用いて、予測誤差（シンボル）を算出してもよい。この場合、画素Ａ及び画素Ｂ（副走査方向直上画素）の画素値の合算値から画素Ｃの画素値をひいた値が予測値となり、この予測値と注目画素Ｘの画素値との差分がシンボルとなる。
また、ソースコーダ５００は、図４（Ｂ）に例示する（式３）を用いて、予測誤差を算出してもよい。この場合、画素Ａ及び画素Ｂの平均画素値が予測値となり、この予測値と注目画素Ｘの画素値との差分がシンボルとなる。
【００２９】
さらに、ソースコーダ５００は、予測誤差が０となる場合に、その連続数（ラン）を計数し、連続数（ラン）をシンボルとする。これにより、図４（Ｃ）に例示するように、予測が的中した画素群については、予測的中の連続数（ラン）がシンボルとなり、予測が外れた画素群については、予測誤差値がシンボルとなる。
画像データをソースコーディングした場合、予測誤差値の出現頻度分布が０の近傍に偏ることが期待できる。
【００３０】
図５（Ａ）は、第１符号部５１０（図３）による固定的ハフマン符号を例示し、図５（Ｂ）は、中間符号記憶部５３０（図３）に記憶される中間符号のフォーマットを例示する図である。
本例の第１符号部５１０は、図５（Ａ）に例示する固定符号表５１２を用いて、シンボルを符号化する。
すなわち、シンボルが連続数（ラン）である場合に、識別子「００」と８ビット表現された連続数とを組み合わせたビット列が、中間符号となる。本例では、連続数を８ビットで表現するため、最大ラン長２５６でランが分割される。
シンボルが−８から７までの間の予測誤差値である場合に、識別子「０１」と４ビット表現された予測誤差値（すなわち、予測誤差値の下位４ビット）とを組み合わせたビット列が、中間符号となる。
シンボルが−８よりも小さい予測誤差値又は７よりも大きな予測誤差値である場合に、識別子「１０」と８ビット表現された予測誤差値とを組み合わせたビット列が、中間符号となる。
この中間符号は、非常に単純だが、−８から７の予測誤差値の出現確率が高いことを想定した固定的ハフマン符号である。
【００３１】
この固定符号表５１２は、予め設計されたものであり、入力される画像データに依存しないため、上記条件１を満たす。なお、本例の固定符号表５１２は、符号量を最小化するものではないが、バッファリングすべきデータ量が減少すれば十分であり、必ずしも符号量を最小化する必要はないので、目的に適っている。
また、本例の第２符号部５５０は、可変ハフマン符号を適用し、この固定符号表５１２は、予測誤差値が０付近に多くなるという特性に基づいて予め設計された固定ハフマン符号であり、共にハフマン符号であるから、上記条件３を満たす。
【００３２】
本例の中間符号記憶部５３０は、上記条件２を満たすために中間符号を４ビット単位で管理する。すなわち、本例の中間符号記憶部５３０は、図５（Ｂ）に例示するバッファリング符号フォーマット５１４を用いて、中間符号をバッファリングする。
具体的には、図５（Ａ）に例示する中間符号は、識別子（２ビット）と属性値（４ビット又は８ビット）とからなるので、そのままでは４ビット単位で管理できない。そこで、本例の中間符号記憶部５３０は、４つの中間符号を１つのフォーマットに統合する。すなわち、中間符号記憶部５３０は、図５（Ｂ）に例示するように、４つの中間符号の識別子（＃０〜＃３）をまとめ、４つの中間符号の属性値（＃０〜＃３）をまとめることにより、４ビット単位での管理を実現する。
これにより、過度なビットシフト処理が避けられ、上記条件２が満たしやすくなる。
【００３３】
［全体動作］
次に、符号化装置２（符号化プログラム５）の全体動作を説明する。
図６は、符号化プログラム５（図３）による符号化処理（Ｓ１０）のフローチャートである。
図６に示すように、ステップ１００（Ｓ１００）において、符号化プログラム５（図３）は、外部から、画像データが入力されると、入力された画像データにおいて走査順に注目画素Ｘを設定する。注目画素とは、処理対象となる画素である。
ソースコーダ５００（図３）は、注目画素Ｘの画素値と画素Ａ（図４）の画素値との差分を算出し、算出された差分値（予測誤差値）に基づいてシンボルを生成する。
符号化プログラム５は、注目画素Ｘの位置を走査順に移動させて、全画素についてシンボルを生成する。生成されたシンボルは、第１符号部５１０及びシンボル計数部５２０に出力される。
【００３４】
ステップ１１０（Ｓ１１０）において、符号化プログラム５は、生成されたシンボル群の中から、順に注目シンボル（すなわち、符号化対象となるシンボル）を設定する。
【００３５】
ステップ１２０（Ｓ１２０）において、第１符号部５１０は、図５（Ａ）の固定符号表５１２を用いて、注目シンボルを符号化する。
【００３６】
ステップ１３０（Ｓ１３０）において、中間符号記憶部５３０は、第１符号部５１０により符号化された注目シンボル（すなわち、中間符号）を、図５（Ｂ）のバッファリング符号フォーマット５１４に従ってバッファリングする。
【００３７】
ステップ１４０（Ｓ１４０）において、シンボル計数部５２０は、第１符号部５１０の符号化処理（Ｓ１２０）と並行して、ソースコーダ５００により生成されるシンボルを計数して、各シンボル値の出現頻度分布を生成する。
【００３８】
ステップ１５０（Ｓ１５０）において、符号化プログラム５は、全シンボルが処理されたか否かを判断し、全シンボルが処理された場合に、Ｓ１６０の処理に移行し、未処理のシンボルが存在する場合に、Ｓ１１０の処理に戻る。
【００３９】
ステップ１６０（Ｓ１６０）において、符号表生成部５４０は、シンボル計数部５２０により生成されたシンボル値の出現頻度分布に応じて、可変ハフマン符号の符号表（可変符号表）を生成し、生成された可変符号表を第２符号部５５０に出力する。
【００４０】
ステップ１７０（Ｓ１７０）において、第２符号部５５０は、中間符号記憶部５３０によりバッファリングされている中間符号の属性値を、符号表生成部５４０により生成された可変符号表を用いて符号化し、符号化された属性値を出力符号とする。
【００４１】
以上説明したように、本実施形態における符号化装置２は、固定的符号化処理と可変的符号化処理とを直列に組み合わせることにより、シンボルのバッファリングに要する負荷を軽減することができる。これにより、高速なエントロピー符号化処理が実現される。
【００４２】
［変形例１］
次に、上記実施形態の変形例１を説明する。
上記実施形態では、第１符号部５１０及び第２符号部５５０は、同じ最大ラン長を適用して、ランを符号化しているが、これに限定されるものではない。すなわち、第１符号部５１０による符号化処理と、第２符号化部５５０による符号化処理とが、多少相違してもよい。
例えば、固定的符号化処理（すなわち、第１符号部５１０による符号化処理）で適用される最大ラン長は、可変的符号化処理（すなわち、第２符号部５５０による符号化処理）で適用される最大ラン長と異なってもよい。
ランレングス化では、最大ラン長をいくつにするかがパラメータとなる。上記実施形態では、可変的ハフマン符号を適用する関係上、シンボル計数部５２０は、可変的処理での最大ラン長Ｒに合わせて、ラン長１〜ラン長Ｒの出現頻度を計数する必要がある。したがって、固定的符号化処理で最大ラン長Ｒのランレングス化をすることは合理的である。
しかし、固定的符号化処理で最大ラン長をもっと大きくとってもよいケースが存在する。例えば、予測誤差値０のランが、長く続くような画像データを対象とする場合である。そのような場合には、固定的符号化処理における最大ラン長をなるべく長くとることで、バッファリングするデータ量を減らすことができる。
このとき、第２符号部５５０は、長いランを最大ラン長Ｒ単位に切り離す必要があり、これがオーバーヘッドとなる。したがって、そのオーバーヘッドと上記の効果が引き合うようであれば、ラン長を長くとってもよい。このとき固定的符号化処理で適用する最大ラン長が、可変的符号化処理で適用する最大ラン長の倍数になっていると、可変的処理が簡略化できるため好ましい。
【００４３】
図７は、固定的符号化処理で最大ラン長２５６を適用し、可変的符号化処理で３２の最大ラン長３２を適用する場合の処理を説明する図である。
例えば、図７（Ａ）に例示する３００のランが第１符号部５１０に入力されると、第１符号部５１０は、図７（Ｂ）に例示するように、３００のランを２５６のランと４４のランに分割し、それぞれをシンボルとして符号化する。
そして、第２符号部５５０は、２５６のランを８分割して３２のランを生成し、４４のランを３２のランと１２のランに分割して、分割された各ランをそれぞれシンボルとして符号化する。この場合に、符号表生成部５４０は、ラン１からラン３２までの出現頻度分布に応じて符号表を生成し、第２符号部５５０は、この符号表を用いて、ランを可変ハフマン符号で符号化する。
【００４４】
［変形例２］
次に、上記実施形態の変形例２を説明する。
上記実施形態では、第１符号部５１０及び第２符号部５５０は、同じデータ単位（シンボル単位）で符号化処理を行っているが、これに限定されるものではなく、例えば、第１の符号部５１０の処理単位（データ単位）は、第２の符号部５５０の処理単位（データ単位）よりも大きくてもよい。
そこで、変形例２では、第１符号部５１０は、複数の画素からなるブロックを処理単位として符号化し、第２符号部５５０は、１画素を処理単位として符号化する形態を説明する。すなわち、上記実施形態では、固定的符号化処理で識別子を画素ごとに付与するため、例えば全白の画像でも２ビット/画素が必要となる。また画素単位の識別子は、画素単位での処理切替えを意味するため、固定的符号化処理及び可変的符号化処理で分岐処理を多発させ処理速度を低下させる可能性がある。
そこで、本変形例２の第１符号部５１０は、複数画素を集めたブロック単位に識別子を付与する。近年のＣＰＵ（中央演算装置）は、幅の広いレジスタを分割して並列処理を行うことができるので、そのような手法の適用が可能なソースコーダとのマッチングもよい。
【００４５】
図８（Ａ）は、ブロック単位で符号化する場合の固定符号表５１３を例示し、図８（Ｂ）及び（Ｃ）は、ブロック単位で生成された中間符号を符号化するときに適用される可変符号表を例示する図である。なお、本変形例では、３２画素を１ブロックとする形態を具体例とする。
本変形例の第１符号部５１０は、ブロック内の画素に対応する全シンボルがランである場合、識別子「００」とラン長（本例では、３２）とのセットを、このブロックの中間符号とする。
また、第１符号部５１０は、ブロック内の画素に対応する全シンボルが−８から７までの予測誤差値である場合に、識別子「０１」と、ブロック内の全予測誤差値（４ビット表現）とのセットを、このブロックの中間符号とする。この中間符号に含まれる予測誤差値（４ビット）の中には、予測誤差値０（４ビット表現）も含まれうる。
また、第１符号部５１０は、ブロック内の画素に対応するシンボルのいずれかが−８よりも小さい予測誤差値又は７よりも大きな予測誤差値である場合に、識別子「１０」と、このブロック内の全予測誤差値（８ビット表現）とのセットを、このブロックの中間符号とする。この中間符号に含まれる予測誤差値（８ビット表現）の中には、−８から７までの予測誤差値（８ビット表現）も含まれうる。
【００４６】
次に、可変的符号化処理に用いる符号表であるが、上記のように、予測誤差値０は、ラン表現、４ビット表現、及び８ビット表現の３種類で表現される可能性があり、−８〜７の予測誤差値（０を除く）は、４ビット表現及び８ビット表現の２種類で表現される可能性がある。
そこで、本変形例の符号表生成部５４０は、図８（Ｂ）に例示するように、−８から７までの予測誤差値をシンボルとして含む８ビット入力可変符号表５５２と、予測誤差値０をシンボルとして含む４ビット入力可変符号表５５４とを生成する。８ビット入力可変符号表５５２では、−８から７までの予測誤差値（０も含む）が８ビットのシンボルとして表現されており、４ビット入力可変符号表５５４は、予測誤差値０も４ビットのシンボルとして表現されている。
この８ビット入力可変符号表５５２及び４ビット入力可変符号表５５４は、それぞれ８ビットシンボル又は４ビットシンボルをエントリとするルックアップテーブルである。例えば、８ビット入力可変符号表５５２として、２５６個のシンボルに対して２５６エントリのルックアップテーブルを用意し、４ビット入力可変符号表５５４として、１６エントリのルックアップテーブルを用意すればよい。このように本変形例では２つのルックアップテーブルが必要になるが、４ビット入力可変符号表５５４のエントリ数が小さいため、影響は小さい。
【００４７】
なお、固定的符号化処理では、ブロック単位で識別子が付与され、属性値は画素単位である。すなわち、１ブロックの属性値の中に３２画素の属性値が含まれている。
したがって、処理単位はブロックであってもデータの粒度は画素単位であって、このため可変的符号化処理との処理単位のミスマッチは生じない。
【００４８】
［その他の変形例］
また、符号化装置２は、複数のシンボルをエントリとする可変符号表を生成し、この可変符号表を用いて可変的符号化処理を行うことにより、符号化処理を高速化してもよい。
図９は、２シンボルをエントリとする２シンボル可変符号表５５６を例示する図である。
第２符号部５５０は、図９に例示する２シンボル可変符号表５５６を用いて、２シンボルを同時に符号化することにより、符号化処理の高速化を図れる。本例の２シンボル可変符号表５５６は、−８から７までの予測誤差値（シンボル値０〜１５）をエントリとしている。画像データを対象とする場合に、シンボル（予測誤差値）は０近辺に集中する、つまり出現頻度が高いので、このような高速化は効果的である。
【００４９】
［実験結果］
図１０は、実験結果のグラフである。なお、本図におけるグラフの横軸は、符号化処理に要した時間（処理時間）であり、縦軸は、符号量である。
図１０に示すように、固定的ハフマン符号のみを適用した場合には、処理時間が短いが、符号量が大きくなってしまう。一方、可変的ハフマン符号のみを適用した場合には、符号量を小さくすることができるが、処理時間が長くなってしまう。
上記変形例２のように、ブロック単位で固定的ハフマン符号化処理を行い、中間符号を可変的ハフマン符号化すると、比較的短い処理時間で、高い圧縮率を実現することができる。
【図面の簡単な説明】
【００５０】
【図１】可変的ハフマン符号を適用する符号化プログラム９の機能構成を例示する図である。
【図２】本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
【図３】制御装置２０（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
【図４】ソースコーダ５００（図３）によるソースコーディングを説明する図である。
【図５】（Ａ）は、第１符号部５１０（図３）による固定的ハフマン符号を例示し、（Ｂ）は、中間符号記憶部５３０（図３）に記憶される中間符号のフォーマットを例示する図である。
【図６】符号化プログラム５（図３）による符号化処理（Ｓ１０）のフローチャートである。
【図７】固定的符号化処理で最大ラン長２５６を適用し、可変的符号化処理で３２の最大ラン長３２を適用する場合の処理を説明する図である。
【図８】（Ａ）は、ブロック単位で符号化する場合の固定符号表５１３を例示し、（Ｂ）及び（Ｃ）は、ブロック単位で生成された中間符号を符号化するときに適用される可変符号表を例示する図である。
【図９】２シンボルをエントリとする２シンボル可変符号表５５６を例示する図である。
【図１０】実験結果のグラフである。
【符号の説明】
【００５１】
２・・・符号化装置
５・・・符号化プログラム
５００・・・ソースコーダ
５１０・・・第１符号部
５２０・・・シンボル計数部
５３０・・・中間符号記憶部
５４０・・・符号表生成部
５５０・・・第２符号部
【図１】
2007324971.tif 000003
【図２】
2007324971.tif 000004
【図３】
2007324971.tif 000005
【図４】
2007324971.tif 000006
【図５】
2007324971.tif 000007
【図６】
2007324971.tif 000008
【図７】
2007324971.tif 000009
【図８】
2007324971.tif 000010
【図９】
2007324971.tif 000011
【図１０】
2007324971.tif 000012