(57)【要約】  【課題】  より効率的な符号化処理を実現する符号化装置を提供する。  【解決手段】  画像処理装置２は、ソースコーダで生成されたシンボルを、既定数のシンボルからなるブロックにまとめ、ブロック毎に符号語を割り振る。すなわち、図１（Ｂ）に例示するように、ブロックに対しては１対１の符号であるが、シンボルから見ると多対１の符号を構成する。これにより、可変長符号の処理に起因する分岐処理又はフィードバックループは、シンボル単位で発生することがなくなり、処理速度の向上が期待できる。【選択図】図１
2008067361.tif 000002
【特許請求の範囲】
【請求項１】
複数の被圧縮情報をまとめて、被圧縮情報のグループを生成するグループ生成手段と、
前記グループ生成手段により生成されたグループに対して、符号を割り当てる符号割当手段と、
それぞれのグループに属する被圧縮情報を、各グループに割り当てられた符号を用いて符号化する被圧縮情報符号化手段と
を有する符号化装置。
【請求項２】
前記グループ生成手段は、複数の被圧縮情報をまとめて、被圧縮情報の下位グループを生成し、
前記グループ生成手段により生成された下位グループを、上位グループに分類するグループ分類手段
をさらに有し、
前記符号割当手段は、前記上位グループに対して、符号を割り当て、
前記被圧縮情報符号化手段は、同一の前記上位グループに属する下位グループの被圧縮情報を、この上位グループに割り当てられた可変長符号を用いて符号化する
請求項１に記載の符号化装置。
【請求項３】
前記グループ生成手段は、入力された複数の被圧縮情報を入力順に既定数ずつまとめて、既定数の被圧縮情報が含まれた下位グループを生成し、
前記グループ分類手段は、前記下位グループに属する被圧縮情報を表現するためのビット数に基づいて、下位グループを上位グループに分類する
請求項２に記載の符号化装置。
【請求項４】
前記符号割当手段は、各グループの出現確率に応じて、それぞれのグループにエントロピー符号を割り当てる
請求項１に記載の符号化装置。
【請求項５】
入力された被圧縮情報に基づいて、この被圧縮情報よりも少ないビット数で表現されたビット列に変換する被圧縮情報変換手段
をさらに有し、
前記被圧縮情報符号化手段は、それぞれのグループに属する被圧縮情報について前記被圧縮情報変換手段により変換されたビット列と、このグループに割り当てられた符号とを用いて、符号化する
請求項１に記載の符号化装置。
【請求項６】
グループに含まれうる複数の被圧縮情報をこれらの被圧縮情報の符号データに対応付ける符号テーブルを用いて、被圧縮情報のグループを符号化するテーブル利用符号化手段と、
前記グループ生成手段により生成された被圧縮情報のグループを、前記符号割当手段と前記被圧縮情報符号化手段との組、又は、前記テーブル利用符号化手段に割り振る割振り手段と
をさらに有し、
前記符号割当手段は、前記割振り手段により割り振られたグループについて、符号を割り当て、
前記被圧縮情報符号化手段は、前記割振り手段により割り振られたグループの被圧縮情報を符号化する
請求項１に記載の符号化装置。
【請求項７】
複数の被圧縮情報からなるグループに割り当てられた符号に基づいて、このグループに属する被圧縮情報の符号長を特定する符号長特定手段と、
前記符号長特定手段により特定された各被圧縮情報の符号長に基づいて、前記グループに属する被圧縮情報を復号化する被圧縮情報復号化手段と
を有する復号化装置。
【請求項８】
複数の被圧縮情報をまとめて、被圧縮情報のグループを生成し、
生成されたグループに対して、符号を割り当て、
それぞれのグループに属する被圧縮情報を、各グループに割り当てられた符号を用いて符号化する
符号化方法。
【請求項９】
複数の被圧縮情報をまとめて、被圧縮情報のグループを生成するステップと、
生成されたグループに対して、符号を割り当てるステップと、
それぞれのグループに属する被圧縮情報を、各グループに割り当てられた符号を用いて符号化するステップと
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エントロピー符号化を行う符号化方法に関する。
【背景技術】
【０００２】
例えば、特許文献１には、入力データを直交変換し、直交変換された入力データのゼロ長を抽出し、直交変換された入力データをグルーピングし、抽出されたゼロ長とグループ係数とに基づいて求められた符号長における当該符号の発生頻度と、符号長に基づいて求められた符号長の符号の中で最も発生頻度の高い符号とからハフマン符号化を行なう方法が開示されている。
【特許文献１】特開平１０−３２２２２１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、上述した背景からなされたものであり、より効率的な符号化処理を実現する符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
［符号化装置］
上記目的を達成するために、本発明にかかる符号化装置は、複数の被圧縮情報をまとめて、被圧縮情報のグループを生成するグループ生成手段と、前記グループ生成手段により生成されたグループに対して、符号を割り当てる符号割当手段と、それぞれのグループに属する被圧縮情報を、各グループに割り当てられた符号を用いて符号化する被圧縮情報符号化手段とを有する。
【０００５】
好適には、前記グループ生成手段は、複数の被圧縮情報をまとめて、被圧縮情報の下位グループを生成し、前記グループ生成手段により生成された下位グループを、上位グループに分類するグループ分類手段をさらに有し、前記符号割当手段は、前記上位グループに対して、符号を割り当て、前記被圧縮情報符号化手段は、同一の前記上位グループに属する下位グループの被圧縮情報を、この上位グループに割り当てられた可変長符号を用いて符号化する。
【０００６】
好適には、前記グループ生成手段は、入力された複数の被圧縮情報を入力順に既定数ずつまとめて、既定数の被圧縮情報が含まれた下位グループを生成し、前記グループ分類手段は、前記下位グループに属する被圧縮情報を表現するためのビット数に基づいて、下位グループを上位グループに分類する。
【０００７】
好適には、前記符号割当手段は、各グループの出現確率に応じて、それぞれのグループにエントロピー符号を割り当てる。
【０００８】
好適には、入力された被圧縮情報に基づいて、この被圧縮情報よりも少ないビット数で表現されたビット列に変換する被圧縮情報変換手段をさらに有し、前記被圧縮情報符号化手段は、それぞれのグループに属する被圧縮情報について前記被圧縮情報変換手段により変換されたビット列と、このグループに割り当てられた符号とを用いて、符号化する。
好適には、グループに含まれうる複数の被圧縮情報をこれらの被圧縮情報の符号データに対応付ける符号テーブルを用いて、被圧縮情報のグループを符号化するテーブル利用符号化手段と、前記グループ生成手段により生成された被圧縮情報のグループを、前記符号割当手段と前記被圧縮情報符号化手段との組、又は、前記テーブル利用符号化手段に割り振る割振り手段とをさらに有し、前記符号割当手段は、前記割振り手段により割り振られたグループについて、符号を割り当て、前記被圧縮情報符号化手段は、前記割振り手段により割り振られたグループの被圧縮情報を符号化する。
【０００９】
［復号化装置］
また、本発明にかかる復号化装置は、複数の被圧縮情報からなるグループに割り当てられた符号に基づいて、このグループに属する被圧縮情報の符号長を特定する符号長特定手段と、前記符号長特定手段により特定された各被圧縮情報の符号長に基づいて、前記グループに属する被圧縮情報を復号化する被圧縮情報復号化手段とを有する。
【００１０】
［符号化方法］
また、本発明にかかる符号化方法は、複数の被圧縮情報をまとめて、被圧縮情報のグループを生成し、生成されたグループに対して、符号を割り当て、それぞれのグループに属する被圧縮情報を、各グループに割り当てられた符号を用いて符号化する。
【００１１】
［プログラム］
また、本発明にかかるプログラムは、複数の被圧縮情報をまとめて、被圧縮情報のグループを生成するステップと、生成されたグループに対して、符号を割り当てるステップと、それぞれのグループに属する被圧縮情報を、各グループに割り当てられた符号を用いて符号化するステップとをコンピュータに実行させる。
【発明の効果】
【００１２】
本発明の符号化装置によれば、より効率的な符号化処理を実現することができる。
【発明を実施するための最良の形態】
【００１３】
［第１実施形態］
まず、本発明の理解を助けるために、その背景及び概略を説明する。
例えば、ハフマン符号は、各シンボル値に対して１対１で付与される。すなわち、ハフマン符号化処理は、１入力（シンボル）に対して１出力（符号語）を与える。ここで、シンボルとは、エントロピー符号化処理の対象となる被圧縮情報である。換言すると、被圧縮情報には、エントロピー符号化処理の対象となるシンボルの他、モデリングがなされる前の被圧縮データ（例えば、ＪＰＥＧ符号化処理における画像データ又はＤＣＴ係数など）も含まれうる。
このような１対１の符号化処理は、構成及び設計が簡単であるが、図１（Ａ）に例示するように、１シンボルごとに符号長が変わる。このため、ソフトウェア処理で出力のためにシリアライズする処理では、分岐が多発するため処理速度を低下させる要因となる。また、ハードウェア処理であっても、符号語長がフィードバックループを形成するため、処理速度に対する制約となる。
なお、説明の便宜上、ハフマン符号という用語を使ったが、上記の問題点は、国際標準ＪＰＥＧの固定的なハフマン符号を含めて一般的な可変長符号化に存在する。
【００１４】
そこで、第１の実施形態における画像処理装置２は、複数のシンボル（以下、ブロックと呼ぶ）毎に符号語を割り振る。すなわち、図１（Ｂ）に例示するように、ブロックに対しては１対１の符号であるが、シンボルから見ると多対１の符号を構成することになる。
これにより、分岐又はフィードバックループは、シンボル単位からブロック単位に削減できるため、処理速度の向上が期待できる。
なお、本実施形態では、ブロックごとに符号語を割り振るエントロピーコーダと、ソースコーダとを組み合わせた形態を具体例として説明するが、この場合に、エントロピーコーダのブロックがソースコーダのブロックと一致する必要はなく、実装コストなどの理由でブロックサイズを変えてもよい。ただし、エントロピーコーダとソースコーダのブロックサイズについて、何らかの関係（例えば、いずれか一方が他方の約数となる関係）がある方が好ましいケースもある。
【００１５】
［ハードウェア構成］
次に、本実施形態における画像処理装置２のハードウェア構成を説明する。
図２は、本発明にかかる符号化方法が適応される画像処理装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
図２に例示するように、画像処理装置２は、ＣＰＵ２０２及びメモリ２０４などを含む制御装置２０、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、並びに、ＬＣＤ表示装置あるいはＣＲＴ表示装置及びキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２６から構成される。
画像処理装置２は、例えば、プリンタ装置１０に設けられた処理装置であり、通信装置２２又は記録装置２４などを介して画像データを取得し、取得された画像データを符号化して蓄積し、蓄積された符号データを復号化して印刷する。
【００１６】
［符号化プログラム］
図３は、制御装置２０（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
図３に例示するように、符号化プログラム５は、ソースコーダ５００、グループ生成部５１０、ビット数算出部５２０、シンボル変換部５３０、グループ分類部５４０、符号割当部５５０、及び符号統合部５６０を有する。
符号化プログラム５は、例えば、図２に例示した記録媒体２４０に記録され、この記録媒体２４０を介して、制御装置２０（図２）に供給される。
なお、本例では、画像データを符号化する場合を具体例として説明する。
【００１７】
符号化プログラム５において、ソースコーダ５００は、入力されたデータファイルに基づいて、可変長符号化処理の対象となるシンボルを生成し、生成されたシンボルをグループ生成部５１０に出力する。
本例のソースコーダ５００は、既定の予測方法を用いて注目画素の画素値を予測し、この予測値と注目画素値との差分値（以下、予測誤差値）を算出し、算出された予測誤差値をシンボルとする。画像データでは近傍画素間で相関が高いため、シンボル値（予測誤差値）の出現頻度は０近傍で高くなることが期待できる。
【００１８】
グループ生成部５１０は、ソースコーダ５００から入力された複数のシンボルをまとめて、シンボルのグループ（以下、ブロック）を生成し、生成されたシンボルのブロックをビット数算出部５２０及びシンボル変換部５３０に出力する。
本例のグループ生成部５１０は、ソースコーダ５００から入力されたシンボルを、入力順に既定数ずつまとめて、既定数のシンボルが含まれたブロックを生成する。
【００１９】
ビット数算出部５２０は、シンボルを表現するために必要となるビット数を算出する。
本例のビット数算出部５２０は、グループ生成部５１０からシンボルのブロックが入力されると、ブロックに含まれる各シンボルについて、必要最小限のビット数（必要ビット数）を算出し、算出された必要ビット数をグループ分類部５４０及びシンボル変換部５３０に出力する。
【００２０】
シンボル変換部５３０は、グループ生成部５１０から入力されたシンボルを、入力されたシンボルよりも少ないビット数で表現されたビット列に変換し、変換されたシンボルのビット列を符号統合部５６０に出力する。
本例のシンボル変換部５３０は、グループ生成部５１０から入力されたシンボルを、ビット数算出部５２０から入力された必要ビット数のビット列（すなわち、必要ビット数で表現されたシンボル）に変換する。
【００２１】
グループ分類部５４０は、ビット数算出部５２０により算出されたシンボルの必要ビット数に基づいて、グループ生成部５１０により生成されたブロック（下位グループ）を上位グループに分類する。
本例のグループ分類部５４０は、ブロックに含まれるシンボルの必要ビット数の組合せに基づいて、このブロックを分類すべき上位グループを決定する。
【００２２】
符号割当部５５０は、複数のシンボルが含まれたグループ（ブロック又は上位グループ）に対して、符号を割り当てる。
本例の符号割当部５５０は、上位グループ毎に、ブロックの出現頻度を計数し、上位グループ毎の出現頻度に応じて、各上位グループにハフマン符号（以下、グループ符号）を割り当てる。
なお、本例の符号割当部５５０は、グロックの出現頻度を上位グループ毎に計数し、計数値に基づいて符号表を設計するが、出現頻度を推定し、推定値に基づいて符号表を設計してもよいし、推定される出現頻度に応じて予め設計された符号表を用いてもよい。
【００２３】
符号統合部５６０は、符号割当部５５０により割り当てられた符号と、シンボル変換部５３０により生成されたビット列とに基づいて、ブロックに含まれるシンボル群の符号（以下、ブロック符号）を生成する。
本例の符号統合部５６０は、符号割当部５５０により割り当てられた符号（グループ符号）と、シンボル変換部５３０により変換されたシンボル値のビット列（必要ビット数で表現されたシンボル値）とを統合して、ブロック符号を生成する。
【００２４】
図４は、符号化プログラム５（図３）による符号化処理を説明する図である。
図４（Ａ）に例示するように、グループ生成部５１０は、ソースコーダ５００から入力されるシンボル（８ビット）を入力順に４つずつまとめて、４つのシンボルＳ０〜Ｓ３が含まれたブロックを生成する。本例では、各シンボルＳ０〜Ｓ３は、８ビットで表現された予測誤差値であり、１ブロックのビット数は３２ビットである。
シンボル変換部５３０は、図４（Ｂ）に例示するように、ブロックに含まれる各シンボルを、必要ビット数で表現されたシンボルに変換する。シンボル表現に必要なビット数（必要ビット数）は、シンボル値に対して底２のlogをとり１を加算することで得られる。ただし、シンボル値０は０ビットと定義する。例えば、シンボル値１は１ビット、シンボル値２〜３は２ビット、シンボル値４〜７は３ビットである。本例では、シンボルが８ビットであるため、必要ビット数は、０〜８ビットの９種類となる。そして、例えば、あるブロックの必要ビット数が３、１、４、１だったとすると、本例のグループ分類部５４０は、これらの必要ビット数の組合せ「３、１、４、１」に基づいて、ブロックを上位グループに分類するため、このブロックは、上位グループ「３１４１」に縮退する。このような上位グループは６５６１（＝９の４乗）種類存在するが、符号割当部５５０は、各上位グループ毎にブロックの出現確率を計測してハフマン符号を設計し、符号語とする。
なお、上位グループ「３１４１」には、５１２（＝８×２×１６×２）のブロックが縮退される。これらを個別に見分けるために、各シンボルを必要ビット数で表現したものを上述の符号語の後に付加する。すなわち、符号統合部５６０は、図４（Ｃ）に例示するように、上位グループに割り当てられた符号（上位グループ「３１４１」の符号語）と、ブロックに含まれるシンボル値（必要ビット数で表現されたシンボル値）とを統合する。
【００２５】
［符号化動作］
次に、画像処理装置２（符号化プログラム５）の全体動作を説明する。
図５は、符号化プログラム５（図３）による符号化処理（Ｓ１０）のフローチャートである。
図５に示すように、ステップ１００（Ｓ１００）において、ソースコーダ５００は、画像データが入力されると、走査順に予測誤差値を算出し、算出された予測誤差値をシンボルとしてグループ生成部５１０に出力する。
グループ生成部５１０は、ソースコーダ５００から入力されるシンボル（予測誤差）を入力順に４つずつまとめて、４つのシンボルが含まれたブロックを生成し、生成されたブロック（下位グループ）をビット数算出部５２０及びシンボル変換部５３０に出力する。
【００２６】
ステップ１１０（Ｓ１１０）において、符号化プログラム５は、ブロック生成部５１０により生成されたブロックの中から、順に注目ブロック（すなわち、符号化対象となるブロック）を設定する。
【００２７】
ステップ１２０（Ｓ１２０）において、ビット数算出部５２０は、グループ生成部５１０から入力された注目ブロックの各シンボルについて、必要ビット数を算出し、算出された必要ビット数をグループ分類部５４０及びシンボル変換部５３０に出力する。本例では、各ブロックについて４つの必要ビット数が算出される。
【００２８】
ステップ１３０（Ｓ１３０）において、グループ分類部５４０は、ビット数算出部５２０により算出された注目ブロックの必要ビット数の組に基づいて、注目ブロックを上位グループに分類する。
【００２９】
ステップ１４０（Ｓ１４０）において、符号割当部５５０は、グループ分類部５４０により注目ブロックが分類された上位グループが通知されると、この上位グループの出現頻度値を１増加させる。
【００３０】
ステップ１５０（Ｓ１５０）において、シンボル変換部５３０は、注目ブロックに含まれる各シンボルを、ビット数算出部５２０により算出された必要ビット数で表現されたシンボルに変換し、必要ビット数で表現された４つのシンボルを符号統合部５６０に出力する。
【００３１】
ステップ１６０（Ｓ１６０）において、符号化プログラム５は、全シンボルが処理されたか否かを判断し、全シンボルが処理された場合に、Ｓ１７０の処理に移行し、未処理のシンボルが存在する場合に、Ｓ１１０の処理に戻る。
【００３２】
ステップ１７０（Ｓ１７０）において、符号割当部５５０は、上位グループの出現頻度値に基づいて、各上位グループに対してハフマン符号（グループ符号）を割り当てる。
【００３３】
ステップ１８０（Ｓ１８０）において、符号統合部５６０は、各ブロックが分類された上位グループのハフマン符号と、このブロックのシンボル（必要ビット数で表現されたもの）とを統合して、ブロック符号を生成し、生成されたブロック符号を出力符号として外部に出力する。
【００３４】
このように、本実施形態における画像処理装置２は、複数のシンボルが含まれたブロック単位で、可変長符号を生成することにより、符号化処理を高速化することができる。
また、本画像処理装置２は、複数のブロックを上位グループに分類し、上位グループに対して符号を割り当てることにより、符号表のサイズを抑えることができる。
また、本画像処理装置２は、ブロック内のシンボルに対する処理を独立に並列化することができるので、そのような処理が可能なアーキテクチャで高速化を図ることができる。
【００３５】
［復号化プログラム］
図６は、制御装置２０（図２）により実行される復号化プログラム６の機能構成を例示する図である。
図６に例示するように、復号化プログラム６は、符号長特定部６００、シンボル抽出部６１０、シンボル復号部６２０、及びデータ再生部６３０を有する。
復号化プログラム６は、例えば、図２に例示した記録媒体２４０に記録され、この記録媒体２４０を介して、制御装置２０（図２）に供給される。
【００３６】
符号化プログラム６において、符号長特定部６００は、入力された符号データに基づいて、ブロック単位で各シンボルの符号長を特定する。
本例の符号長特定部６００は、上位ブロックに割り当てられた符号（グループ符号）に基づいて、ブロックに含まれる各シンボルのビット数（すなわち必要ビット数）を特定し、特定されたビット数をシンボル抽出部６１０に出力する。
【００３７】
シンボル抽出部６１０は、入力された符号データから、符号長特定部６００により特定された符号長に基づいて、各シンボルの符号を抽出する。
本例のシンボル抽出部６１０は、符号長特定部６００により特定されたシンボルのビット数に基づいて、ブロックに含まれる各シンボルのビット列（必要ビット数で表現されたシンボル値）を切り出す。
【００３８】
シンボル復号部６２０は、シンボル抽出部６１０により抽出された各シンボルの符号を復号化して、各シンボル値を生成する。
本例のシンボル復号部６２０は、シンボル抽出部６１０により切り出されたシンボルのビット列（必要ビット数で表現されたシンボル値）の上位に０のビット列を付加して８ビット表現のシンボルを生成し、生成されたシンボルをデータ再生部６３０に出力する。
【００３９】
データ再生部６３０は、シンボル復号部６２０により復号化されたシンボルに基づいて、データファイルを再生する。
本例のデータ再生部６３０は、シンボル復号部６２０から入力されるシンボル（予測誤差値）に基づいて、元の画像データを生成する。
【００４０】
［復号化動作］
図７は、復号化プログラム６（図６）による復号化処理（Ｓ２０）のフローチャートである。
図７に示すように、ステップ２００（Ｓ２００）において、符号長特定部６００は、入力された符号データのグループ符号を復号化して、各ブロックの必要ビット数の組を特定する。
【００４１】
ステップ２１０（Ｓ２１０）において、復号化プログラム６は、入力された符号データの中から、順に注目ブロックの符号を設定する。
【００４２】
ステップ２２０（Ｓ２２０）において、シンボル抽出部６１０は、符号長特定部６００により特定された必要ビット数に基づいて、注目ブロックのビット列の中から、各シンボルのヒット列（すなわち、必要ビット数で表現されたシンボル）を切り出す。例えば、図４（Ｃ）に例示するように、グループ符号が上位グループ「３１４１」に相当する場合、先頭から、３ビット、１ビット、４ビット、１ビットがそれぞれシンボルのビット列（符号）として切り出される。
【００４３】
ステップ２３０（Ｓ２３０）において、シンボル復号部６２０は、シンボル抽出部６１０により切り出されたシンボルのビット列（必要ビット数で表現されたもの）に対して、０の上位ビットを付加して、８ビット表現のシンボルを生成する。例えば、図４（Ｂ）に例示するシンボル（３ビット、１ビット、４ビット、１ビット）は、上位に０ビットが付加されて、図４（Ａ）に例示するシンボルＳ０〜Ｓ３が生成される。
【００４４】
ステップ２４０（Ｓ２４０）において、復号化プログラム６は、全ブロックについて復号化処理が終了したか否かを判断し、全ブロックが処理された場合に、Ｓ２５０の処理に移行し、未処理のシンボルが存在する場合に、Ｓ２１０の処理に戻る。
【００４５】
ステップ２５０（Ｓ２５０）において、データ再生部６３０は、シンボル復号部６２０により生成されたシンボル（予測誤差値）に基づいて、元の画像データを生成する。
【００４６】
このように、本実施形態における画像処理装置２は、ブロック単位で符号長を特定するため、復号化処理を高速化することができる。
【００４７】
［変形例１］
次に、上記実施形態の変形例１を説明する。
上記実施形態では、図４に例示するように、ブロックに含まれるシンボルの必要ビット数の組合せに基づいて、各ブロックを上位グループに分類していたが、第１の変形例では、ブロックに含まれるシンボルの必要ビット数のうちの最大値に基づいて、各ブロックを上位グループに分類する。
例えば、図８（Ａ）に例示するように、４つのシンボルＳ０〜Ｓ３が含まれたブロックが存在する場合に、これらのシンボルの必要ビット数のうち、最大値を検出する。本例では、シンボルＳ０（予測誤差４）の必要ビット数が３ビットであり、シンボルＳ１（予測誤差１）の必要ビット数が１ビットであり、シンボルＳ２（予測誤差１１）の必要ビット数が４ビットであり、シンボルＳ３（予測誤差１）の必要ビット数が１ビットである。そのため、本例の最大値は４である。
そして、本変形例では、最大値となったビット数でブロック内の各シンボルが表現される。すなわち、本例では、図８（Ｂ）に例示するように、シンボルＳ０〜Ｓ３が全て４ビットで表現される。
そして、図８（Ｃ）に例示するように、上位ブロックに割り当てられた符号（グループ符号）と、最大値のビット数で表現されたシンボル値（本例では、４ビット表現されたシンボルＳ０〜Ｓ３）とを統合して、ブロック符号が作成される。
【００４８】
図９は、第２の符号化プログラム５２の機能構成を例示する図である。なお、本図に示された各構成のうち、図３に示された構成と実質的に同一のものには同一の符号が付されている。
図９に例示するように、第２の符号化プログラム５２は、図３の符号化プログラム５に最大値検出部５７０を追加した構成をとる。
【００４９】
符号化プログラム５２において、最大値検出部５７０は、各ブロックについて、ブロック内に含まれるシンボルの中から、必要ビット数が最大となるシンボルを検出する。
本例の最大値検出部５７０は、ブロックに含まれる複数のシンボルのうち、シンボル値が最大となるシンボルを検出する。
【００５０】
本変形例のビット数算出部５２０は、最大値検出部５７０により検出されたシンボルについて、必要ビット数を算出する。
本変形例のシンボル変換部５３０は、ビット数算出部５２０により算出された必要ビット数で、ブロックに含まれる全シンボルを表現する。
本変形例のグループ分類部５４０は、ビット数算出部５２０により算出された必要ビット数（すなわち、最大値検出部５７０により検出されたシンボルの必要ビット数）に基づいて、各ブロックを上位グループに分類する。
【００５１】
このように、変形例１では、ブロック内の符号長を同一にすることにより、上記実施形態よりも処理を高速化できる。
なお、ブロックに含まれるシンボル数を８の倍数にすれば、最大値の必要ビット数で表現されるパートが、バイトバウンダリになる。さらにハフマン符号語をバイトバウンダリで設計すれば、符号全体がバイトバウンダリになり、さらなる高速化が期待できる。
また、ハフマン符号語は、いくつかのブロックをまとめて表現してもよい。例えば１バイトを４ビットずつに分けて、上位４ビットで第１のブロックを、また下位４ビットで第２のブロックの符号語を格納するようにしてもよい。
【００５２】
［変形例２］
上記実施形態では、図１０（Ａ）に例示するように、各シンボルを必要ビット数で表現したが、第２の変形例では、図１０（Ｂ）に例示するように、必要ビット数で表現されたシンボルのビット列から、さらに最上位ビット（すなわち、シンボルのＭＳＢ）を省略する。すなわち、Ｎビット表現すべきシンボルが、同一ビットを含む場合、そのビットは省略してもよい。例えば、シンボル２とシンボル３を２ビット表現する場合、いずれもＭＳＢ（Most Significant Bit）は、１となる。したがって、このビットを２ビット表現に含める必要はない。
また、第２の変形例では、Ｎビット表現されるシンボルが１種類である場合、Ｎビット表現を省略してもよい。例えば、図１０（Ａ）に例示するシンボル値「１」は、１ビット表現されるが、１ビット表現されるシンボルはシンボル値「１」の１種類だけであるから、図１０（Ｂ）に例示するように、シンボル値「１」のビット列を省略できる。このシンボル値「１」は、グループ符号「３１４１」の「１」によって復号化できる。
【００５３】
［変形例３］
上記実施形態及び変形例１では、暗黙にシンボル値が小さいシンボルほど高い頻度で出現するという仮定をおいていた。特に前段にソースコーダを設ける場合、そのような仮定はごく一般的であり、またそうなるようにソースコーダを設計することも比較的容易である。
しかしそうでないケースもありえる。そこで、第３の変形例では、シンボル値そのままではなく、変換する例について述べる。
本変形例は、必要ビット数を算出する前にシンボル値の変換を行う。この変換は、より多く出現するシンボル値に、より小さいインデクスが振られるように行う。これは予め計測したり他のデータから予測したりして出現頻度を求め、これをソートして得られる出現頻度順のシンボル値を表すルックアップテーブルなどで簡単に実現できる。
【００５４】
［変形例４］
上記変形例３のさらなる変形例として、１パス目では上記変形例２（実施形態でもよい）で説明した符号化処理を行いつつ、同時に出現頻度を計測しておき、さらに圧縮率を高めたい場合に、上記変形例３で再処理する。このとき出現頻度から正確に再処理後の符号量が求められるので、これを元に再処理の是非を判定するような構成でもよい。
【００５５】
［その他の変形例］
また、上記実施形態では、シンボル変換部５３０がシンボル単位でシンボルの変換を行っているが、複数シンボル単位で変換を行ってもよい。例えば、隣あう２シンボルのパターンについて、ルックアップテーブルを生成すればよい。こうすることで記憶を有する情報源の圧縮率を向上することができる。
また、上記実施形態では、ソースコーダ５００がシンボルとして予測誤差値を算出しているが、他の方法でシンボルを生成してもよい。
【００５６】
［第２実施形態］
次に、第２の実施形態を説明する。
上記第１の実施形態ではブロック内の必要ビット数Nを求め、グループを決定し、ブロック内の各要素をそれぞれNビット表現したものをマージするというステップを踏む。
もしこの結果生成されるパターンの種類が少なければ、この処理をロジックで行うよりも、最終データを保持しておいてルックアップテーブル（LUT）で選択した方が高速に処理できる。例えばハフマン符号表はそのようなLUTの一種と考えることもできる。
しかし、そのようなテーブルは、上記実施形態のような入力が複数シンボルの場合は、一般に非常に大きくなるので、不合理なことが多い。上記実施形態の場合、仮に１ブロック８シンボルとすると、N=1で（2^1）^8=256通りの出力が起こりえる。同様にN=2では（2^2）^8=6.6×10^4通り、N=8では（2^8）^8=1.8×10^19通りとなるので、現在の技術では実現が難しいサイズになる。
しかし、例えばN=1に限定することができれば256エントリのLUTで済むので、十分実現可能となる。そこで、第２の実施形態では、N=1となる入力シンボルだけを、LUTによる処理の対象として符号化する。ここでN=1となるのは0または1のシンボルである。
【００５７】
図１１は、第２の実施形態における符号化プログラム７の機能構成を例示する図である。なお、本図に示された各構成のうち、図３に示された構成と実質的に同一のものには同一の符号が付されている。
図１１に例示するように、本実施形態の符号化プログラム７は、図３の符号化プログラム５に、振分け部７００及びテーブル符号化部７１０を追加した構成をとる。
【００５８】
符号化プログラム７において、振分け部７００は、グループ生成部５１０により生成されたブロックを、ビット数算出部５２０及びシンボル変換部５３０の組、又は、テーブル符号化部７１０に出力する。すなわち、振分け部７００は、本発明に係る割振り手段の一例である。より具体的には、振分け部７００は、グループ生成部５１０から入力されるブロックの必要ビット数が所定値となる場合に、このブロックをテーブル符号化部７１０に出力し、これ以外の場合に、ビット数算出部５２０及びシンボル変換部５３０に出力する。この場合の所定値とは、例えば、基準値以下の値であり、１ブロックに８シンボルが含まれている場合には、所定値は１又は２である。すなわち、必要ビット数が１又は２である場合には、テーブル符号化部７１０によって符号化されることになる。
【００５９】
テーブル符号化部７１０は、符号テーブルを用いて、振分け部７００から入力されたブロックを符号化する。符号テーブルは、ブロックに含まれうる複数のシンボルと、これらのシンボルの符号データとを互いに対応付けるルックアップテーブルである。すなわち、本例のテーブル符号化部７１０は、振分け部７００から入力されたブロックのシンボルに基づいて、符号テーブルから符号データを読み出し、読み出された符号データを外部に出力する。
【００６０】
図１２は、図１１のテーブル符号化部７１０が利用する符号テーブルを例示する図である。
図１２は、１ブロック８シンボルの場合におけるN=1または2の符号テーブルである。いま各シンボルが８ビットだとすると、図１２の符号テーブルは、6.6×10^4エントリで構成できる。ただし、テーブル符号化部７１０がこの符号テーブルを引くために8ビット×8のデータからエントリを探す処理が必要となる。これは簡単なビット操作で実行できる。
本実施例において、テーブル符号化部７１０が符号テーブル（LUT）をひくときに固定的なビット処理を要するものの、本来必要だったハフマン符号表をひく処理（符号割当部５５０などの処理）や、得られた符号と符号長で分岐しつつ符号をマージして符号語を生成する処理（符号統合部５６０などの処理）を省くことができる。これにより上記第１の実施形態と比較して、符号化処理の高速化を図ることができる。
【００６１】
図１３は、符号化プログラム７（図１１）による符号化処理（Ｓ３０）のフローチャートである。なお、本図に示された各処理のうち、図５に示された処理と実質的に同一のものには同一の符号が付されている。
図１３に示すように、Ｓ１００において、ソースコーダ５００は、画像データが入力されると、走査順に予測誤差値を算出し、算出された予測誤差値をシンボルとしてグループ生成部５１０に出力する。グループ生成部５１０は、ソースコーダ５００から入力されるシンボル（予測誤差）を入力順に８つずつまとめて、８つのシンボルが含まれたブロックを生成し、生成されたブロック（下位グループ）を振分け部７００に出力する。
Ｓ１１０において、符号化プログラム７は、ブロック生成部５１０により生成されたブロックの中から、順に注目ブロック（すなわち、符号化対象となるブロック）を設定する。
【００６２】
ステップ３００（Ｓ３００）において、振分け部７００は、注目ブロックの必要ビット数が基準値２以下であるか否かを判断し、必要ビット数が基準値以下である場合に、注目ブロックをテーブル符号化部７１０に出力し、必要ビット数が基準値より大きい場合に、注目ブロックをビット数算出部５２０及びシンボル変換部５３０に出力する。
符号化プログラム７は、注目ブロックの必要ビット数が基準値以下である場合に、Ｓ３１０の処理に移行し、注目ブロックの必要ビット数が基準値よりも大きい場合に、Ｓ１２０の処理に移行する。
【００６３】
ステップ３１０（Ｓ３１０）において、テーブル符号化部７１０は、図１２に例示する符号テーブルから、注目ブロックのシンボルに対応する符号データを読み出し、読み出された符号データを外部に出力する。
【００６４】
Ｓ１２０において、ビット数算出部５２０は、グループ生成部５１０から入力された注目ブロックの各シンボルについて、必要ビット数を算出し、算出された必要ビット数をグループ分類部５４０及びシンボル変換部５３０に出力する。
Ｓ１３０において、グループ分類部５４０は、ビット数算出部５２０により算出された注目ブロックの必要ビット数の組に基づいて、注目ブロックを上位グループに分類する。
Ｓ１４０において、符号割当部５５０は、グループ分類部５４０により注目ブロックが分類された上位グループが通知されると、この上位グループの出現頻度値を１増加させる。
Ｓ１５０において、シンボル変換部５３０は、注目ブロックに含まれる各シンボルを、ビット数算出部５２０により算出された必要ビット数で表現されたシンボルに変換し、必要ビット数で表現された８つのシンボルを符号統合部５６０に出力する。
Ｓ１６０において、符号化プログラム７は、全シンボルが処理されたか否かを判断し、全シンボルが処理された場合に、Ｓ１７０の処理に移行し、未処理のシンボルが存在する場合に、Ｓ１１０の処理に戻る。
Ｓ１７０において、符号割当部５５０は、上位グループの出現頻度値に基づいて、各上位グループに対してハフマン符号（グループ符号）を割り当てる。
Ｓ１８０において、符号統合部５６０は、各ブロックが分類された上位グループのハフマン符号と、このブロックのシンボル（必要ビット数で表現されたもの）とを統合して、ブロック符号を生成し、生成されたブロック符号を出力符号として外部に出力する。
【００６５】
このように、本実施形態における画像処理装置２は、必要ビット数が基準値以下であるブロックについては、Ｓ１２０からＳ１８０までの処理をＳ３１０の処理で代替するため、符号化処理を高速化できる。
【００６６】
［変形例］
次に、第２の実施形態の変形例を説明する。
本変形例では、上記第２の実施形態を画像圧縮に適用する。画像圧縮では、データの連続性による冗長度を削減するために、前値差分などの予測残差への変換が行われる。
図１４は、本変形例における符号化プログラム７２の機能構成を例示する図である。なお、本図に示された各構成のうち、図９又は図１１に示された構成と実質的に同一のものには同一の符号が付されている。
図１４に示すように、本変形例の符号化プログラム７２は、図９の符号化プログラム５２から、ソースコーダ５００を除き、振分け部７００、テーブル符号化部７１０及び予測残差算出部７２０を追加した構成をとる。
【００６７】
符号化プログラム７２において、グループ生成部５１０は、入力された画像データの中から、走査順に８画素分の画素値をまとめて、８つの画素値が含まれたブロックを振分け部７００に出力する。
【００６８】
振分け部７００は、グループ生成部５１０から入力されたブロックが白黒モードに相当するか否かを判断し、白黒モードに相当するブロックをテーブル符号化部７１０に出力し、白黒モードに相当しないブロックを予測残差算出部７２０に出力する。
本変形例では、予測残差を符号化対象シンボルとするが、予測残差は正負ともにとりえるので、負値を２の補数で表現し、最大値の検出と必要ビット数算出では出現頻度を考慮して、[-1,0]に1bit、[-2,1]に2bitといったように配分するなどする。これは信号処理ではごく一般的な技術である。
本例の振分け部７００は、外部からの指示によって白黒モードであるか否かを判断する。ここで、白黒モードとは、入力画像が白黒２値で作成されている場合や、白黒２値での出力が指定されている場合である。白黒モードモードでは、画像信号としては0か255の２値しかとり得ない。この場合、予測残差は−255、0、255のいずれかになるが、8bit限定で2の補数表現を考えれば、それぞれ1、0、−1と同値になる。このように変換しても一意性は失われない。例えば真値が0で予測値が255の場合、予測残差は−255なので、予測値と予測残差から真値を再現するには255＋（−255）=0と求められる。この予測残差を1と表現して8bit限定の演算で置き換えてみると、255+1=256となるが、8bitに限定すれば、つまり下位8bitを取り出せば、256→0となって真値が再現できることがわかる。このような演算はラップアラウンドなどと称され、一般的な技術である。
このラップアラウンドの表現を用いれば、0または255の画像から発生する予測残差は1、0、−1で表現できるので、必要ビット数N=1ないし2となる。つまりそのような場合はLUT処理が可能となる。したがって、本変形例の振分け部７００は、白黒モードが選択された際に、LUT（すなわち、テーブル符号化部７１０の処理）を選択するように動作する。
なお、振分け部７００は、入力画像を分析して、白黒２値の場合を検出するように構成していてもよいし、実際に予測残差を計算し、N=1または2にできるときだけLUTを通すようにしてもよい。この場合、後段の予測残差と処理を逆にすれば処理を削減できる。
【００６９】
予測残差算出部７２０は、注目画素の画素値と、その直前画素値との差分を算出し、算出された差分（すなわち、予測残差）をシンボル変換部５３０及び最大値検出部５７０に出力する。
【００７０】
上記構成によれば、符号テーブル（LUT）によって削減できる処理が増えるので、より一層の高速化が実現できる。
なお、上記変形例ではN=1または2のケースについて述べたが、実現性が許せばこれをN=1から3までや、その他のケースにしてもよい。
【図面の簡単な説明】
【００７１】
【図１】シンボル単位で符号長が変化する形態と、ブロック単位で符号長が変化する形態とを比較する図である。
【図２】本発明にかかる符号化方法が適応される画像処理装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
【図３】制御装置２０（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
【図４】符号化プログラム５（図３）による符号化処理を説明する図である。
【図５】符号化プログラム５（図３）による符号化処理（Ｓ１０）のフローチャートである。
【図６】制御装置２０（図２）により実行される復号化プログラム６の機能構成を例示する図である。
【図７】復号化プログラム６（図６）による復号化処理（Ｓ２０）のフローチャートである。
【図８】ブロック内の最大値の必要ビット数でシンボルを表現する形態を説明する図である。
【図９】第２の符号化プログラム５２の機能構成を例示する図である。
【図１０】必要ビット数で表現されたシンボルのＭＳＢを省略する形態を説明する図である。
【図１１】第２の実施形態における符号化プログラム７の機能構成を例示する図である。
【図１２】図１１のテーブル符号化部７１０が利用する符号テーブルを例示する図である。
【図１３】符号化プログラム７（図１１）による符号化処理（Ｓ３０）のフローチャートである。
【図１４】本変形例における符号化プログラム７２の機能構成を例示する図である。
【符号の説明】
【００７２】
２・・・画像処理装置
５,５２・・・符号化プログラム
５００・・・ソースコーダ
５１０・・・グループ生成部
５２０・・・ビット数算出部
５３０・・・シンボル変換部
５４０・・・グループ分類部
５５０・・・符号割当部
５６０・・・符号統合部
５７０・・・最大値検出部
６・・・復号化プログラム
６００・・・符号長特定部
６１０・・・シンボル抽出部
６２０・・・シンボル復号部
６３０・・・データ再生部
【図１】
2008067361.tif 000003
【図２】
2008067361.tif 000004
【図３】
2008067361.tif 000005
【図４】
2008067361.tif 000006
【図５】
2008067361.tif 000007
【図６】
2008067361.tif 000008
【図７】
2008067361.tif 000009
【図８】
2008067361.tif 000010
【図９】
2008067361.tif 000011
【図１０】
2008067361.tif 000012
【図１１】
2008067361.tif 000013
【図１２】
2008067361.tif 000014
【図１３】
2008067361.tif 000015
【図１４】
2008067361.tif 000016