(57)【特許請求の範囲】
【請求項１】
動的確率分布モデルに基づいて画像データを符号化する画像符号化装置であって、
画像データを画素単位に入力する入力手段と、
該入力手段で入力された着目画素データからＧｏｌｏｍｂ符号化の対象となるシンボルを生成するシンボル生成手段と、
前記シンボル生成手段で生成された着目シンボルを、直前のシンボルを符号化する際に決定された符号化パラメータに従ってＧｏｌｏｍｂ符号化し、符号化データを生成する符号化手段と、
該符号化手段の符号化対象となったシンボルを符号化する際に使用した符号化パラメータが、前記符号化対象のシンボルの符号語を目標符号長とするための符号化パラメータの取り得る範囲内にあるか、当該範囲の上限を超えるか、或いは、当該範囲の下限を下回るかを判断する判断手段と、
前記着目シンボルに後続するシンボルの符号化のため、前記判断手段の判断結果に基づき、前記符号化パラメータを更新する更新手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記シンボル生成手段は、
着目画素データの周囲に位置し、既符号化済みの少なくとも１つの画素データから着目画素データの予測値を算出する予測値算出手段と、
算出された予測値と着目画素データとの差である予測誤差を算出する予測誤差算出手段と、
算出された予測誤差の正負の符号を判別可能な、非負の整数値に変換する変換手段とを備え、
当該変換手段で変換された非負の整数値を前記シンボルとして生成することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記シンボルを前記符号化手段で符号化する際に用いた符号化パラメータをＫ、当該シンボルの符号長が目標符号長となる符号化パラメータの範囲の下限と上限をＫＳmin、ＫＳmaxと定義したとき、
前記更新手段は、
Ｋ＜ＫＳminの関係にあるとき、符号化パラメータＫを増加させ、
ＫＳmax＜Ｋの関係にあるとき、符号化パラメータＫを減少させ、
ＫＳmin≦Ｋ≦ＫＳmaxの関係にあるとき、符号化パラメータＫの値を維持することを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
更に、既符号化済みであって、着目画素Ｘの周囲にある画素データに基づき、着目画素位置の状態情報Ｓを算出する状態情報算出手段と、
該状態情報Ｓの取り得る範囲の符号化パラメータ配列Ｋ［］を記憶する符号化パラメータ記憶手段とを備え、
前記符号化手段は、着目画素データの状態情報Ｓで特定される符号化パラメータＫ［Ｓ］に従って符号化し、
前記更新手段は、符号化パラメータＫ［Ｓ］を更新することを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項５】
前記シンボルを前記符号化手段で符号化する際に用いた符号化パラメータをＫ［Ｓ］、当該シンボルの符号長が目標符号長となる符号化パラメータの範囲の下限と上限をＫＳmin、ＫＳmaxと定義したとき、
前記更新手段は、
Ｋ［Ｓ］＜ＫＳminの関係にあるとき、符号化パラメータＫ［Ｓ］を増加させ、
ＫＳmax＜Ｋ［Ｓ］の関係にあるとき、符号化パラメータＫ［Ｓ］を１未満の確率で減少させ、
ＫＳmin≦Ｋ［Ｓ］≦ＫＳmaxの関係にあるとき、符号化パラメータＫ［Ｓ］の値を維持することを特徴とする請求項４に記載の画像符号化装置。
【請求項６】
更に、既符号化済みであって、着目画素Ｘの周囲にある画素データに基づき、着目画素位置の状態情報Ｓを算出する状態情報算出手段と、
該状態情報算出手段で算出された状態情報Ｓの取り得る範囲のインデックス配列ｉ［］を記憶するインデックス記憶手段と、
前記インデックス配列ｉ［］の取り得る範囲の符号化パラメータ配列Ｋ［ｉ［］］を記憶する符号化パラメータ記憶手段とを備え、
前記符号化手段は、着目画素データの状態情報Ｓで特定される符号化パラメータＫ［ｉ［Ｓ］］に従って符号化し、
前記更新手段は、符号化パラメータＫ［ｉ［Ｓ］］を更新することを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項７】
前記シンボルを前記符号化手段で符号化する際に用いた符号化パラメータをＫ、当該シンボルの符号長が目標符号長となる符号化パラメータの範囲の下限と上限をＫＳmin、ＫＳmaxと定義したとき、
前記更新手段は、
Ｋ［ｉ［Ｓ］］＜ＫＳminの関係にあるとき、符号化パラメータＫ［ｉ［Ｓ］］を予め設定された補正値αだけ増加させ、
ＫＳmax＜Ｋ［ｉ［Ｓ］］の関係にあるとき、符号化パラメータＫ［ｉ［Ｓ］］を前記補正値αよりも小さな補正値βだけ減少させ、
ＫＳmin≦Ｋ≦ＫＳmaxの関係にあるとき、符号化パラメータＫ［ｉ［Ｓ］］の値を維持することを特徴とする請求項６に記載の画像符号化装置。
【請求項８】
動的確率分布モデルに基づいて画像データを符号化する画像符号化装置の制御方法であって、
画像データを画素単位に入力する入力工程と、
該入力工程で入力された着目画素データからＧｏｌｏｍｂ符号化の対象となるシンボルを生成するシンボル生成工程と、
前記シンボル生成工程で生成されたシンボルを、直前のシンボルを符号化する際に決定された符号化パラメータに従ってＧｏｌｏｍｂ符号化し、符号化データを生成する符号化工程と、
該符号化工程の符号化対象となったシンボルを符号化する際に使用した符号化パラメータが、前記符号化対象のシンボルの符号語を目標符号長とするための符号化パラメータの取り得る範囲内にあるか、当該範囲の上限を超えるか、或いは、当該範囲の下限を下回るかを判断する判断工程と、
前記着目シンボルに後続するシンボルの符号化のため、前記判断工程の判断結果に基づき、前記符号化パラメータを更新する更新工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項９】
コンピュータが読み込み実行することで、前記コンピュータを、請求項１乃至７いずれか１項に記載の画像符号化装置として機能させるコンピュータプログラム。
【請求項１０】
請求項９に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項１１】
動的確率分布モデルに基づいて符号化された画像データを復号する画像復号装置であって、
画素単位の符号化データを入力する入力手段と、
前記入力手段によって入力された符号化データを、直前の符号化データを復号する際に決定された復号パラメータに従ってＧｏｌｏｍｂ復号し、着目画素のシンボルを生成する復号手段と、
復号して得られたシンボルから、着目画素の画素データに復元する画素データ復元手段と、
前記復号手段で得られたシンボルを復号する際に使用した復号パラメータが、前記シンボルの符号語の符号長を目的符号長に収めるための符号化パラメータの取り得る範囲内にあるか、当該範囲の上限を超えるか、或いは、当該範囲の下限を下回るかを判断する判断手段と、
前記着目符号化データに後続する符号化データの復号のため、前記判断手段の判断結果に基づき、前記復号パラメータを更新する更新手段と
を備えることを特徴とする画像復号装置。
【請求項１２】
動的確率分布モデルに基づいて符号化された画像データを復号する画像復号装置の制御方法であって、
画素単位の符号化データを入力する入力工程と、
前記入力工程によって入力された符号化データを、直前の符号化データを復号する際に決定された復号パラメータに従ってＧｏｌｏｍｂ復号し、着目画素のシンボルを生成する復号工程と、
復号して得られたシンボルから、着目画素の画素データに復元する画素データ復元工程と、
前記復号工程で得られたシンボルを復号する際に使用した復号パラメータが、前記シンボルの符号語の符号長を目的符号長に収めるための符号化パラメータの取り得る範囲内にあるか、当該範囲の上限を超えるか、或いは、当該範囲の下限を下回るかを判断する判断工程と、
前記着目符号化データに後続する符号化データの復号のため、前記判断工程の判断結果に基づき、前記復号パラメータを更新する更新工程と
を備えることを特徴とする画像復号装置の制御方法。
【請求項１３】
コンピュータが読み込み実行することで、前記コンピュータを、請求項１１に記載の画像復号装置として機能させるコンピュータプログラム。
【請求項１４】
請求項１３に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの符号化技術に関するものである。
【背景技術】
【０００２】
画像符号化に用いるエントロピ符号化の形態として、静的な確率分布モデルを用いるものと動的なモデルによるものがある。静的確率分布モデルを用いるものは、情報源の性質を調査、あるいは想定してあらかじめ確率分布のモデルを用意しておき、そのモデルに適した符号化を行うものである。また、動的確率分布モデルを用いるものは、符号化の過程で情報源の性質を学習し、ダイナミックに確率分布のモデルを変更しながら符号化を行うものである。
【０００３】
ここで、多値画像のロスレス（可逆）符号化について、この２つの例を挙げる。
【０００４】
連続階調静止画像の国際標準符号化方式としてＩＳＯとＩＴＵ−Ｔから勧告されるＪＰＥＧに規定されるロスレス符号化方式では、着目画素と予測値との差分をあらかじめ定めたハフマンテーブルを用いて符号化しており、静的モデルを用いている（非特許文献１）。
【０００５】
一方、連続階調静止画像の可逆と準可逆圧縮の国際標準方式としてＩＳＯとＩＴＵ−Ｔから勧告されているＪＰＥＧ−ＬＳ  Ｐａｒｔ１は動的モデルの一例である。ＪＰＥＧ−ＬＳは予測誤差の符号化に、符号化パラメータを変えることによって異なる確率分布に対応可能なＧｏｌｏｍｂ（ゴロム）符号化技術を採用している。着目画素の周囲４画素から決定されるコンテキスト毎に、符号化済みのシンボルの確率分布状況を参考にして「ｋ」を選択することで、ダイナミックに確率分布モデルの変更が行われる（非特許文献２）。
【０００６】
以下、ＪＰＥＧ−ＬＳにおける予測誤差符号化の大まかな流れと、Ｇｏｌｏｍｂ符号化パラメータの決定方法について説明する。なお、以下の説明では、着目画素の周囲画素が全て同一画素値である場合に適用されるランモードや、準可逆符号化のための量子化処理など、本発明に直接関係しない事柄については省略する。標準方式の詳細については規格書を参照されたい。
【０００７】
図３はＪＰＥＧ−ＬＳで参照される着目画素「ｘ」とその周囲画素ａ，ｂ，ｃ，ｄとの相対位置関係を示す。ラスタースキャン順に画素を符号化するため、着目画素「ｘ」の周辺画素ａ，ｂ，ｃ，ｄは全て符号化済みであることに注意されたい。各画素の値もａ，ｂ，ｃ，ｄで表現する。まず、以下の式によりａとｃ、ｃとｂ、ｂとｄの差分を求め、Ｄ１、Ｄ２、Ｄ３を得る。
Ｄ１ ＝ ｄ − ｂ
Ｄ２ ＝ ｂ − ｃ
Ｄ３ ＝ ｃ − ａ
【０００８】
この差分値Ｄ１、Ｄ２、Ｄ３を９通り(−４から４まで)に量子化してそれぞれの差分の量子化値Ｑ１、Ｑ２、Ｑ３を求める。図２に差分値の範囲とその量子化値の対応を示す。Ｔ１、Ｔ２、Ｔ３はあらかじめ定められた非負の整数値である。
【０００９】
例えば、０〜２５５の値を取る８ビットの画像に対しては、Ｔ１＝３、Ｔ２＝７、Ｔ３＝２１といった値が設定される。このようにして得られたＱ１、Ｑ２、Ｑ３の組み合わせ（Ｑ1，Ｑ２，Ｑ３）は、Ｑ１、Ｑ２、Ｑ３がそれぞれ−４から４までの９通りの値を持ち得るので、９×９×９＝７２９通りである。
【００１０】
ここで状態（Ｑ１，Ｑ２，Ｑ３）で予測誤差ｅが発生する確率と、状態（−Ｑ１，−Ｑ２，−Ｑ３）で予測誤差−ｅが発生する確率は同じとして考える。従って、これら２つの状態を統合して３６５通りに縮退する。この組み合わせを示す情報が上記のコンテキストである。３６５通りの状態のいずれであるかを表す識別子をＳとし、以降、この識別子Ｓを状態番号と呼ぶ。
【００１１】
一方、周囲画素ａ，ｂ，ｃを用いて着目画素値ｘに対する予測値ｐを以下の式により求める。
ｐ＝ｍｉｎ（ａ，ｂ）    （ｍａｘ（ａ，ｂ）≦ｃ  の場合） or
ｐ＝ｍａｘ（ａ，ｂ）    （ｍｉｎ（ａ，ｂ）≧ｃ  の場合） or
ｐ＝ａ＋ｂ−ｃ          （上記以外）
ここで、ｍｉｎ（ｘ，ｙ）はｘ、ｙの小さい方を返す関数、ｍａｘ（ｘ，ｙ）は大きい方の値を返す関数である。
【００１２】
予測値ｐの値の取り方は、周囲画素ａ，ｂ，ｃの値の大小関係によって切り替わるが、ａ，ｂ，ｃが符号化済みの画素であるため、切り替わりに関する付加情報を伝送することなく、符号化側と復号側で同じ予測値ｐを取ることができることに注意されたい。ＪＰＥＧ−ＬＳでは予測の精度を向上するために、これまでに状態Ｓで符号化された画素で発生した予測誤差の平均値を参照して予測値ｐを修正するという技術が用いられているが、ここでは説明を省略する。
【００１３】
この予測値ｐと着目画素ｘとの差分ｅを求め、これを非負の整数値に変換してＧｏｌｏｍｂ符号化する。このとき、着目画素のコンテキストに応じて符号化のパラメータｋを決定する。
【００１４】
ＪＰＥＧ−ＬＳではそれぞれの状態Ｓごとに生起回数Ｎ［Ｓ］と、その状態で符号化した予測誤差の絶対値和Ａ［Ｓ］とを保持する。Ｇｏｌｏｍｂ符号化のパラメータｋは、これら２つの値を用いた以下の条件を満たすものである。なお、「ｘ＾ｙ」はｘのｙ乗を示す。
２＾（ｋ−１）＜  Ａ［Ｓ］／Ｎ［Ｓ］  ≦  ２＾ｋ
【００１５】
実際には、Ａ［Ｓ］／Ｎ［Ｓ］の除算を行う必要はない。Ｎ［Ｓ］×２＾ｋ≧Ａ［Ｓ］となる最小のｋを求めれば良い。これにより予測誤差の絶対値平均が大きい状態ではｋパラメータとして大きな値が選択され、反対に絶対値平均が小さい状態では小さなｋパラメータが選択される。
【００１６】
符号化の開始時点ではＡ［Ｓ］、Ｎ［Ｓ］に初期値を設定しておき、符号化処理の過程で随時値を更新していくことにより、動的に各状態の確率分布に追従する。
【非特許文献１】ITU-T T.81 | ISO/IEC 10918-1 : 1994,  Information Technology - Digital compression and coding of continuous-tone still images : Requirements and guidelines
【非特許文献２】ITU-T T.87 (1998) |  ISO/IEC 14495-1 : 1999,  Information Technology - Lossless and near-lossless compression of continuous-tone still images : Baseline
【発明の開示】
【発明が解決しようとする課題】
【００１７】
上述のＪＰＥＧ−ＬＳによる画像処理装置では、各予測誤差の符号化の都度、ｋパラメータ決定のための処理を実行する。
【００１８】
除算を行わないようにするなど、処理負荷を軽減する工夫がされているが、不定回数の判定を伴う処理を毎回行うことは処理負荷の観点から効率的とは言えない。
【００１９】
また、予測誤差の絶対値和を保持するには多くの桁数（ビット数）が必要であり、場合によってはＡ［Ｓ］のメモリ容量が問題となることがある。
【００２０】
また、予測誤差の絶対値平均に基づいて符号化パラメータｋを決定している。このため、例えば状態分離が不十分で統計的性質の変化が大きい情報源を符号化する場合において、大きな予測誤差が発生した際には、それ以降に符号化される多数の予測誤差についてｋパラメータが大きくなるなどの影響が及ぶという問題が残る。
【００２１】
本願発明は、上述の問題点に鑑みてなされたものである。そして、本発明の実施態様によれば、動的な確率分布モデルを用いる画像の符号化において、簡易に符号化パラメータを決定し、かつ、良好な符号化性能を実現する技術を提供する。
【課題を解決するための手段】
【００２２】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
動的確率分布モデルに基づいて画像データを符号化する画像符号化装置であって、
画像データを画素単位に入力する入力手段と、
該入力手段で入力された着目画素データからＧｏｌｏｍｂ符号化の対象となるシンボルを生成するシンボル生成手段と、
前記シンボル生成手段で生成された着目シンボルを、直前のシンボルを符号化する際に決定された符号化パラメータに従ってＧｏｌｏｍｂ符号化し、符号化データを生成する符号化手段と、
該符号化手段の符号化対象となったシンボルを符号化する際に使用した符号化パラメータが、前記符号化対象のシンボルの符号語を目標符号長とするための符号化パラメータの取り得る範囲内にあるか、当該範囲の上限を超えるか、或いは、当該範囲の下限を下回るかを判断する判断手段と、
前記着目シンボルに後続するシンボルの符号化のため、前記判断手段の判断結果に基づき、前記符号化パラメータを更新する更新手段とを備える。
【発明の効果】
【００２３】
本発明によれば、処理負荷およびメモリコストの少ない簡易な方法で符号化パラメータを決定することができ、かつ、画像データを良好な圧縮性能で符号化可能とする。
【発明を実施するための最良の形態】
【００２４】
以下添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。
【００２５】
＜第１の実施形態＞
図１は本実施形態に係る画像処理装置の機能構成を示すブロック構成図である。
【００２６】
図１に示すように、本実施形態に係る画像処理装置は、画像入力部１０１、ラインバッファ１０２、予測器１０３、予測誤差生成部１０４、予測順位変換部１０５、Golomb符号化部１０６、ｋパラメータ更新部１０７、符号列形成部１０８とを備える。同図において１０９は信号線を示す。
【００２７】
以下、図１を参照して、本実施形態に係る画像処理装置が行う画像符号化処理について説明する。ここでは、符号化対象画像は、各画素が８ビット（０〜２５５の範囲）の輝度値または濃度値を表現した画素データにより構成される、モノクロ画像データであるものとする。しかしながら、本方式はＲＧＢやＣＭＹＫなど、１画素が複数のコンポーネント（色）で表現されるカラー画像や、各コンポーネントが８ビット以上のビット精度で表現される画像データに対しても同様に適用可能である。例えば、カラー画像に適用する場合には、コンポーネント毎に分離して、それぞれをモノクロ画像と同様に符号化すれば良い。なお、符号化対象画像は水平方向Ｗ画素、垂直方向Ｇ画素により構成されるものとする。
【００２８】
次に、本実施形態の画像処理装置での各部の動作について説明する。
【００２９】
画像入力部１０１は、符号化対象画像データの画素データｘを入力する。この入力はラスタースキャン順とする。入力源は、イメージスキャナとするが、画像データファイルを記憶している記憶媒体でもあっても良く、その入力源の種類は問わない。
【００３０】
ラインバッファ１０２は画像データを２ライン分格納する記憶容量を持ち、画像入力部１０１から入力される画像データを順次格納していく。つまり、ラインバッファ１０２に必要とされる容量は２×Ｗバイトである。ラインバッファ１０２に保持する２ライン分の画素データは符号化開始時点で所定の値で初期化される。画素の初期値としては符号化装置と復号装置で共通に設定可能な値であれば良い。ここでは説明の簡略化のため、符号化処理を開始する際に、ラインバッファ１０２を「０」で初期化するものとする。
【００３１】
予測器１０３は画像入力部１０１から入力される画素（以降、着目画素と呼ぶ）について、符号化済みの周囲画素ａ，ｂ，ｃを参照して予測値ｐを生成する。着目画素ｘと周囲画素ａ，ｂ，ｃの位置関係は図３に示す通りである。符号化済みの周囲画素ａ，ｂ，ｃはラインバッファ１０２から供給される。なお、着目画素ｘがラインの先頭である場合やラインの最後の画素である場合、周囲画素a、ｂ、ｃのいずれかが符号化対象画像の範囲外となることがある。このような場合には、符号化装置と復号装置で共通の値を用いるが、ここでは画像の範囲外の値は０とする。本実施形態では予測値ｐを以下の式により求める。
ｐ＝ｍｉｎ（ａ，ｂ）    （ｍａｘ（ａ，ｂ）≦ｃ  の場合） or
ｐ＝ｍａｘ（ａ，ｂ）    （ｍｉｎ（ａ，ｂ）≧ｃ  の場合） or
ｐ＝ａ＋ｂ−ｃ          （上記以外）
【００３２】
なお、予測値生成には上記方法以外にも様々な方法を用いることが可能である。例えば、ＪＰＥＧ標準方式のロスレス符号化で使用可能な７つの予測式のように、別の予測式を用いても良い。また、ＪＰＥＧ−ＬＳ標準方式のように、符号化済みの画素で平均的に発生した予測誤差値を用いて上記予測値ｐを補正することで予測の精度を高めるといった方法を用いることもできる。
【００３３】
予測誤差生成部１０４は予測器１０３により生成された予測値ｐと画像入力部１０１から入力される着目画素値ｘとの差分「ｘ−ｐ」を演算し、その結果を予測誤差ｅとして出力する。
【００３４】
予測順位変換部１０５は予測誤差生成部１０４で求めた予測誤差ｅを以下の式により非負の整数値Ｍ（ｅ）にマップする。以降、Ｍ（ｅ）を予測順位と呼ぶ。
Ｍ（ｅ）＝    ２×ｅ      （ｅ≧０の場合）
Ｍ（ｅ）＝  −２×ｅ−１  （ｅ＜０の場合）
上記の結果、Ｍ（ｅ）は非負の整数となり、それが偶数か奇数かでもって予測誤差ｅの正負の符号が識別できる。
【００３５】
Ｇｏｌｏｍｂ符号化部１０６はｋパラメータ更新部１０７の内部に保持するｋパラメータを用いて、予測順位変換部１０５から出力される予測順位Ｍ（ｅ）をＧｏｌｏｍｂ符号化し、２値シンボル列を出力する。
【００３６】
Ｇｏｌｏｍｂ符号は非負の整数値を符号化対象とし、パラメータ変数ｍによって異なる複数の確率モデルによる符号化が可能であるという特徴を持つ。また、符号化対象シンボルとパラメータ変数ｍから符号語を導出することができるため、符号表が不要という利点もある。以下の説明ではパラメータ変数ｍが２＾ｋとなるＧｏｌｏｍｂ符号の特殊形に限定し、ｋをパラメータ変数として説明する。このようなＧｏｌｏｍｂ符号の一形態がISOとITU-Tから国際標準勧告されるJPEG-LS（ISO/IEC  １４４９５−１｜ITU-T  Recommendation T.87）において予測誤差の符号化方式として採用されている。
【００３７】
符号化対象の非負の整数値ｎを符号化パラメータｋでＧｏｌｏｍｂ符号化する手順は次の通りである。まず、ｎをｋビット右シフトして整数値ｕを求める。平たく言えば、整数値ｕは、ｎを２＾ｋで除算した商を意味する。
【００３８】
シンボルｎに対する符号は、ｕ個の「０」に続く「１」（可変長部）と、ｎの下位ｋビット（固定長部）の組み合わせにて構成する。図１６にｋ＝０，１，２におけるＧｏｌｏｍｂ符号の例を示しておく。
【００３９】
例えば、ｋ＝２（従ってｍ＝４）で、シンボルｎ＝５の場合、ｕ＝floor(５／４)＝１となるので、可変長部は２進“０１”となる。また、シンボルｎの下位２ビットは“０１”となるので、ｋ＝２の場合のシンボル「５」のＧｏｌｏｍｂ符号語は“０１０１”となり、符号長は４ビットとなる。
【００４０】
なお、ここに述べた符号の構成方法は一例であり、固定長部と可変長部の順序を逆にしても一意復号可能な符号を構成することができる。また、０と１を反対にして符号を構成しても良い。
【００４１】
ｋパラメータ更新部１０７は、Ｇｏｌｏｍｂ符号化部１０６により予測順位変換部１０５から出力される予測順位Ｍ（ｅ）の符号化後が行われた後に、内部に保持するｋパラメータの更新処理を行う。更新処理は、符号化した予測順位Ｍ（ｅ）の値と現在保持するｋパラメータで最小符号長が得られる範囲（以降、最適シンボル範囲と呼ぶ）とを比較し、必要に応じてｋの値を＋１、あるいは−１することにより行われる。
【００４２】
図５ＡはＧｏｌｏｍｂ符号の、各シンボルの値（縦軸）と、ｋパラメータ（横軸）と２次元空間における符号長を示すテーブルである。図示では、０〜２８までの符号化対象シンボル（予測順位Ｍ（ｅ）に対応する）を、ｋ＝０〜５のそれぞれ符号化パラメータで符号化した場合に発生する符号長（ビット数）を表している。
【００４３】
図示のテーブルでは、３つの領域に分けて示している。１つ目の領域は、個々のシンボルに着目し、その符号語の符号長が最小（最短）となる領域５０である。残りの２つは、領域５０で分断される領域５１、５２である。領域５１は、領域５０を規定する符号化パラメータｋの値よりも大きな符号化パラメータｋと、最小符号長とはならない符号長で定義される領域と言い換えることができる。また、領域５２は、領域５０を規定する符号化パラメータｋの値よりも小さな符号化パラメータｋと、最小符号長とはならない符号長で定義される領域と言い換えることができる。
【００４４】
例えば、符号化対象シンボルが「８」であり、符号化パラメータｋ＝２乃至４の範囲では最小符号長「５」となる。従って、シンボル「８」においては、符号化パラメータｋ＝２乃至４の範囲の符号長が「５」となる位置は、領域５０内にある。
【００４５】
また、符号化対象シンボルが「８」であり、符号化パラメータｋ＝５では、符号長が「６」となり、最小符号長「５」とはならない。それ故、シンボル「８」においては、符号化パラメータｋ＝５の符号長が「６」となる位置は、領域５１内にある。
【００４６】
同様に、符号化対象シンボルが「８」であり、符号化パラメータｋ＝０、１では、符号長が「９」or「６」となり、やはり最小符号長「５」とはならない。それ故、シンボル「８」においては、符号化パラメータｋ＝０、１の符号長が「９」or「６」となる位置は、領域５２内にある。
【００４７】
本実施形態におけるｋパラメータ更新部１０７は、符号化対象の予測順位Ｍ（ｅ）が領域５１内にあった場合、次画素の符号化時には、より小さいｋパラメータが適切と判断し、ｋの値をより小さな値に補正する。具体的には、次画素の符号化に備えて、パラメータｋから１を減じる。
【００４８】
また、符号化した予測順位Ｍ（ｅ）が領域５２内にあった場合、より大きなｋパラメータが適切と判断し、ｋの値をより大きな値に補正する。具体的には、ｋに１を加えて更新する。
【００４９】
そして、符号化した予測順位Ｍ（ｅ）が領域５０内にあった場合、現状のｋパラメータが適切と判断し、ｋの値は補正せず、維持する。
【００５０】
なお、図示の領域５１、５２の境界はパラメータｋから導出することができる。符号化対象シンボルの値をｎで表すとき、領域５１は、「ｎ＜２＾（ｋ−１）」の関係を満たす範囲であり、領域５２は３×２＾ｋ≦ｎの範囲である。換言すれば、図５Ａのテーブルを全て記憶する必要はなく、領域５０を定義する情報のみ記憶すればよい。領域５０は、各シンボルの値と、それぞれのシンボル毎に、それを符号化した際の最小符号長となるパラメータｋの下限値と上限値を記憶すればよい。
【００５１】
また、この判定処理を不要とするため、図５Ｂに示すような、テーブルを予めパラメータ更新部１０７が記憶保持しても構わない。図５Ｂのテーブルは、図５Ａのテーブルに、次回の符号化に備えた補正値（−１、０、＋１）の項目を追加したものである。領域５０内での補正値は“０”、領域５１内での補正値は“−１”、そして、領域５２内での補正値は“＋１”である。従って、補正値Ｈ（＝−１，０、＋１）はＨ（ｎ，ｋ）と表現できるので、この値Ｈ（ｎ，ｋ）を現在のｋパラメータに足し込むことで、ｋパラメータを更新すればよい。
【００５２】
符号列形成部１０８はGolomb符号化部１０６から出力される符号列（２値シンボル列）を結合させ、必要な付加情報を加えて本画像処理装置の出力となる符号化データを形成して信号線１０９より出力する。出力先が記憶装置であれば、ファイルとして格納する。
【００５３】
図９は本画像処理装置の出力符号列の構成を示す図である。出力符号列の先頭には、画像を復号するために必要となる情報、例えば、画像の水平方向画素数、垂直方向画素数、色空間を表す属性情報、コンポーネント数、各コンポーネントのビット数などの付加情報がヘッダとして付けられる。
【００５４】
図４は本実施形態に係る画像処理装置による符号化対象画像データの符号化処理の流れを示すフローチャートである。以下、図４に示したフローチャートを参照して、本実施形態に係る画像処理装置が行う画像符号化処理の全体的な流れについて説明する。
【００５５】
まず、符号化処理に先立ち、ラインバッファ１０２に格納される画素データ、およびｋパラメータ更新部１０７に保持される符号化パラメータｋの初期化が行われる。本実施形態ではラインバッファ１０２の画素データを全て０に初期化し、ｋパラメータ更新部１０７が保持するｋパラメータを「２」に設定する（ステップＳ４００）。続いて、画像入力部１０１はラスタースキャン順に画像データの入力を開始し、入力した画像データの各画素データをラインバッファ１０２に格納すると共に、予測誤差生成部１０４に供給する（ステップＳ４０１）。
【００５６】
次に、ラインバッファ１０２から着目画素の周囲画素ａ，ｂ，ｃを読み出し、予測器１０３にて予測値ｐを生成する（ステップＳ４０２）。予測誤差生成部１０４は、着目画素ｘと予測器１０３の生成した予測値ｐとの差分を求め、予測誤差ｅとして出力する（ステップＳ４０３）。予測順位変換部１０５は、この予測誤差ｅを予測順位Ｍ（ｅ）に変換する（ステップＳ４０４）。Golomb符号化部１０６は、ｋパラメータ更新部１０７の内部に保持するｋパラメータを用いて、予測順位Ｍ（ｅ）をGolomb符号化する（ステップ４０５）。
【００５７】
続いてｋパラメータ更新部１０７にて、符号化した予測順位Ｍ（ｅ）と更新前のｋパラメータにおける最適範囲との比較が行われ、自身が保持するｋパラメータを必要に応じて更新する（ステップＳ４０６）。つまり、予測順位Ｍ（ｅ）と、Golomb符号化部１０６で使用したｋパラメータで示される位置が、図５Ａ又は図５Ｂの領域５０乃至５２のどの領域内にあるかを判断し、いずれの領域にあるかに基づき次の画素の符号化する際に利用することになるｋパラメータを更新（補正）する。
【００５８】
次いで、符号化した画素が画像の最後の画素かどうかを判定し（ステップＳ４０７）、最後の画素である場合には符号化処理を終了し、そうでない場合にはステップ４０１へと処理を移し、次の画素の符号化処理を行う。
【００５９】
以上の処理により、画像全体の符号化が行われる。なお、符号化処理は必ずしもこの順序で行わなければならないという訳ではない。例えば、ここでは画素データの読み込み（ステップＳ４０１）、予測値の生成（ステップＳ４０２）という順番で説明したが、順序を逆にしても良い。また、更新前のｋパラメータを正しく受け渡しできるならば、Ｇｏｌｏｍｂ符号化（ステップＳ４０５）とｋパラメータの更新（ステップＳ４０６）の順序を変える、あるいは並列に行うといった変更を行っても良い。
【００６０】
ここで、予測順位変換部１０５から順に出力される予測順位の列“０，０，２，０，０，１，０，３，０…”を符号化する場合を例にとり、符号化に使用するｋパラメータの値と更新処理の内容、および更新処理後のｋ値の推移を図６に示す。
【００６１】
以下、ｋパラメータの変化を順に説明する。符号化の開始時にｋパラメータの初期値を“２”に設定し、最初のシンボル“０”はこのｋ＝２を用いてGolomb符号化する。ｋ＝２に対してシンボル“０”は、図５Ａの領域５１に該当する。従って、ｋから１を減じて、ｋ＝１と更新する。
【００６２】
２番目のシンボル“０”を更新後のｋ（この場合ｋ＝１）で符号化する。この場合、シンボル“０”は、同じく図５Ａの領域５１に該当するため、ｋから１を減じてｋ＝０と更新する。
【００６３】
次に、シンボル“２”をｋ＝０で符号化する。シンボル“２”はｋ＝０の最適シンボル範囲にあるため、ｋの値は変化させない。以降、同様にシンボル列“０，０，１，０”を符号化するが、同じ理由からｋの値に変化は起こらない。
【００６４】
続いて、シンボル“３”をｋ＝０で符号化し、シンボルが領域５２に該当するため１を加えて、ｋ＝１と更新する。次のシンボル“０”をｋ＝１で符号化し、領域５１に該当するため１を減じて、ｋ＝０と更新する。このようにして、符号化とパラメータｋの更新処理が行われる。この例からも、符号化対象シンボルの局所的な性質に合わせてｋパラメータが変更されていく様子が分かる。
【００６５】
本実施形態の画像処理装置で生成した符号化データを復号するにはヘッダに示される付加情報を参照して、符号化処理の逆の手順でそれぞれの画素を復号していくようにすれば良い。このとき、各シンボルの復号においてＧｏｌｏｍｂ符号化のｋパラメータは符号化側と復号側で同じ値を用いる。即ち、復号側でも符号化側と同じ初期値を与えて復号を開始し、復号したシンボルが現在のｋパラメータに対して最適シンボル範囲にあるか否かを判定し、符号化時と同じアルゴリズムで必要に応じて更新していく。
【００６６】
図１５は復号側の画像処理装置の機能構成を示すブロック図である。先に説明した図１と共通のブロックについては同じ番号を付し、説明を省略する。図に示すように復号側の画像処理装置は、符号化データ入力部１５０１、Golomb符号復号部１５０２、予測順位逆変換部１５０３、画素値復元部１５０４、ヘッダ解析部１５０５、ラインバッファ１０２、予測器１０３、ｋパラメータ更新部１０７とを備える。
【００６７】
以下、復号処理を行う画像処理装置の各処理部の動作について説明する。
【００６８】
符号化データ入力部１５０１は復号対象となる符号化データを入力する。このとき、符号化データ入力部１５０１は、符号化データの構造解析を行い、ヘッダ部はヘッダ解析部１５０５へ、画素符号化データはGolomb符号復号部１５０２へと渡す。
【００６９】
ヘッダ解析部１５０５は符号化データ入力部から送られるヘッダを解析し、符号化された画像データの水平、垂直方向画素数など、復号処理に必要な情報を取り出し、画像処理装置の制御に反映させる。
【００７０】
Golomb符号復号部１５０２はｋパラメータ更新部１０７に保持するｋパラメータを取得し、これを用いて予測順位Ｍ（ｅ）にまで復元する。
【００７１】
ｋパラメータ更新部１０７は先に述べた符号化の際の更新処理と同じ方法により、復号された予測順位Ｍ（ｅ）に基づいて必要に応じてｋパラメータの更新を行う。
【００７２】
予測順位逆変換部１５０３はGolomb符号復号部１５０２で復号された予測順位M(e)から以下の式により予測誤差ｅを復元する。
ｅ＝    Ｍ（ｅ）／２        （Ｍ（ｅ）が偶数の場合 )
ｅ＝−（Ｍ（ｅ）＋１）／２  （Ｍ（ｅ）が奇数の場合 )
【００７３】
画素値復元部１５０４は予測順位逆変換部１５０３で復元される予測誤差ｅと予測器１０３にて生成される予測値ｐから、ｅ＋ｐにより着目画素値ｘを復号して出力する。復号した画素値ｘはラインバッファ１０２に格納され、以降の画素の予測値を生成する際に利用される。
【００７４】
画像を構成する全ての画素が復号されるまで、Ｇｏｌｏｍｂ符号復号部１５０２から画素値復元部１５０４の処理を繰り返し行うことにより、符号化データから画像データの復号を行う。
【００７５】
以上の説明のように、本実施形態に係る画像処理装置では、符号化したシンボル、または復号したシンボルが現在のｋパラメータにおける最適シンボル範囲にあるか否かを判定して、最適シンボル範囲にない場合に＋１または−１して更新し、適切なｋパラメータとなるよう制御している。これにより局所的に統計的性質の異なる画像データであっても性質の変化に追従した効率の良い符号化ができる。
【００７６】
＜第１の実施形態の変形例＞
上記の実施形態を、パーソナルコンピュータ等の汎用情報処理装置と、それ上で実行されるコンピュータプログラムで実現しても構わない。
【００７７】
図１４は本変形例に係る情報処理装置の基本構成を示す図である。図中、１４０１はＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理を実行する。
【００７８】
１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備えると共に、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。
【００７９】
１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。
【００８０】
１４０４、１４０５は夫々キーボード、マウス等のポインティングデバイスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。
【００８１】
１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。
【００８２】
１４０７は外部記憶装置で、ハードディスクドライブ装置等の大容量情報記憶装置であって、ここにＯＳや後述する画像符号化、復号化処理の為のアプリケーションプログラム、符号化対象の画像データなどが保存されている。ＯＳやアプリケーションは、ＣＰＵ１４０１による制御によって、ＲＡＭ１４０２上の所定のエリアにロードすることで、実行されることになる。
【００８３】
１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化処理の為のプログラム、符号化対象画像を記録しておいても良く、その場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。
【００８４】
１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えはＩ／Ｆ１４０９を介して符号化対象となる画像データを本装置の本装置のＲＡＭ１４０２や外部記憶装置１４０７に入力することや、逆に、本装置のＲＡＭ１４０２や外部記憶装置１４０７から生成した画像符号化データを装置外部に出力することができる。１４１０は上述の各部を繋ぐバスである。
【００８５】
画像符号化処理を行なう場合、外部記憶装置１４０７から対応するプログラムをＲＡＭ１４０２にロードし、ＣＰＵ１４０１がその処理を実行する。この符号化処理のプログラムは、基本的に図４のフローチャートに従って処理を行なえば良い。また、そのプログラムは、図１に示すような各構成に相当するモジュール（関数、サブルーチンと言っても良い）で構成すれば良いであろう。ただし、ラインバッファ１０８は、ＲＡＭ１４０２にその容量分のデータ領域を確保することになる。
【００８６】
また、復号処理に係るプログラムも、図１５に示すモジュールで構成すれば良いのは明らかであろう。
【００８７】
＜第２の実施形態＞
次に、第２の実施形態を以下に説明する。第１の実施形態の画像処理装置では符号化対象のシンボルが最適シンボル範囲外となる度に符号化パラメータｋを増減して、補正させた。この場合、情報源の統計的性質の変化にすばやく対応できる利点がある反面、性質の変化の少ない情報源においては安定性が問題となる。
【００８８】
例えば、それぞれのｋパラメータで符号化効率が最大となる確率分布ｆ（ｎ、ｋ）＝(1/2)^Ｌ（ｎ，ｋ）について考える。Ｌ（ｎ，ｋ）は符号化対象シンボルｎを符号化パラメータｋでＧｌｏｍｂ符号化した場合の符号長であり、Ｌ（ｎ，ｋ）＝ｋ＋１＋floor（ｎ／（２^ｋ）}で与えられる。なお、ｘ＾ｙはｘのｙ乗、floor(x)はｘを超えない最大整数を返す関数を表わす。
【００８９】
図７にｋ＝１の場合の確率分布ｆ（ｎ、１）を図示する。
【００９０】
確率分布ｆ（ｎ、ｋ）について図５Ａに示した領域５２に属する何れかのシンボルが出現する確率、即ち、或るｋにおいて領域５２に属するシンボルの出現確率の和を調べると、どのｋパラメータにおいても１２．５％であることが分かる。
【００９１】
同様に領域５１について見ると、ｋ＝０の場合を除いて、領域５１のシンボルの出現確率は２５％となっている。即ち、あるｋパラメータ（ｋ≠０）で、その理想的な確率分布の情報源ｆ（ｎ、ｋ）を符号化している場合であっても、３７．５％（＝１２．５％＋２５％）の確率でｋパラメータが変化することを意味する。
【００９２】
図８（ａ）はｋ＝０である場合、同図（ｂ）はｋ＞０である場合に、それぞれｆ（ｎ、ｋ）の確率分布を持つ情報源のシンボルを符号化して起こるｋパラメータの遷移を示している。
【００９３】
ここでは本発明の第２の実施形態として、ｋパラメータの変動を抑制し、安定性を向上させる方法について述べる。
【００９４】
図１０は、本第２の実施形態に係る画像処理装置の機能構成を示すブロック図である。第１の実施形態で説明した図１と共通のブロックについては同じ番号を付し、説明を省略する。
【００９５】
本第２の実施形態に係る画像処理装置は、画像入力部１０１、ラインバッファ１０２、予測器１０３、予測誤差生成部１０４、予測順位変換部１０５、Golomb符号化部１０６、コンテキスト生成部１００１、ｋパラメータ更新部１００２、符号列形成部１０８を備える。また、同図において１０９は信号線を示す。
【００９６】
なお、本第２の実施形態に係る画像処理装置の基本構成は、それぞれの機能を専用のハードウェアによって構成しても良い。また、先に説明した第１の実施形態の変形例と同様に図１４に示す構成とし、図１０に示す各部の機能をコンピュータに実現させるプログラムにより実現するものとしても構わない。後者の場合、そのプログラムは上記外部記憶装置１４０７や記憶媒体ドライブ１４０８、もしくはＩ／Ｆ１４０９を介して外部装置からＲＡＭ１４０２にロードされ、ＣＰＵ１４０１が実行することになる。
【００９７】
以下、図１０を用いて本第２の実施形態に係る画像処理装置が行う処理について説明する。
【００９８】
本第２の実施形態に係る画像処理装置の符号化対象とする画像データは、第１の実施形態と同じく、各画素８ビットで０〜２５５の範囲の輝度値を表現したモノクロ画像データとして説明する。ただし、ＲＧＢやＣＭＹＫカラー画像など、複数コンポーネント（成分）で構成される画像データにも適用可能である。また、符号化対象の画像データはラスタースキャン順に各画素の値を並べて構成されるものとする。画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。
【００９９】
本第２の実施形態の画像処理装置においても第１の実施形態の画像処理装置と同様に、画像入力部１０１は符号化対象となる画素データｘを入力し、その画素データｘをラインバッファ１０２に格納する。先に説明した予測器１０３、予測誤差生成部１０４、予測順位変換部１０５によって、エントロピ符号化の対象となる非負の整数値Ｍ（ｅ）が生成される。
【０１００】
一方、コンテキスト生成部１００１では、着目画素ｘの周囲画素ａ，ｂ，ｃ，ｄをラインバッファ１０２から読み出し、着目画素の周囲の状態を表すコンテキストを生成する。本実施形態ではＪＰＥＧ−ＬＳと類似の手法により、状態番号Ｓが０〜７２８である７２９通りの状態に分離するものとする。
【０１０１】
従来技術の説明部分で述べた通り、周辺画素ａ，ｂ，ｃ，ｄについて、ａとｂ、ｂとｃ、ｃとｄの差分をそれぞれ図２のテーブルに従って量子化してＱ１、Ｑ２、Ｑ３を得る。この組み合わせを一意に表わす状態番号Ｓを生成する。本第２の実施の形態では以下の式により状態番号Ｓを定める。
Ｓ＝８１×Ｑ１＋９×Ｑ２＋Ｑ３＋３６４
【０１０２】
なお、ＪＰＥＧ−ＬＳと同様に状態（Ｑ１，Ｑ２，Ｑ３）と状態（−Ｑ１、−Ｑ２、−Ｑ３）と統合して３６５状態に縮退したり、ａ，ｂ，ｃ，ｄ以外の周辺画素を参照してコンテキストを生成しても構わない。
【０１０３】
ｋパラメータ更新部１００２の内部には各状態Ｓに応じたｋパラメータを格納する配列Ｋ［Ｓ］と、後述する更新処理にて参照するフラグ配列Ｆ［Ｓ］を保持する。符号化の開始時に配列Ｋ［Ｓ］（Ｓ＝０、１、２、…）は初期値（本実施形態では２とする）に設定され、フラグ配列Ｆ［Ｓ］（Ｓ＝０、１、２、…）を“０”に初期化する。
【０１０４】
図１１は、着目画素ｘの符号化時のｋパラメータ更新部１００２の処理の流れを示すフローチャートである。同図を用いて各画素で行われるｋパラメータ更新部１００２の処理の流れを説明する。
【０１０５】
まず、ｋパラメータ更新部１００２は、コンテキスト生成部１００１から出力される状態番号Ｓと予測順位変換部１０５から出力される予測順位Ｍ（ｅ）を取得する（ステップＳ１１０１）。次いで、ｋパラメータ更新部１００２は、入力された状態番号Ｓに対応するｋパラメータを配列要素Ｋ[Ｓ]により取得し、それをＧｏｌｏｍｂ符号化部１０６へと出力する（ステップＳ１１０２）。これにより、Ｇｏｌｏｍｂ符号化部１０６は、予測順位Ｍ（ｅ）の符号化を行うことになる。
【０１０６】
次いで、現在のｋパラメータの値、即ちＫ［Ｓ］と、シンボルである予測順位Ｍ（ｅ）とで示される位置（Ｋ［Ｓ］，Ｍ（ｅ））が、領域５１内にあるか否かを判断する（ステップＳ１１０３）。
【０１０７】
これは、現在のｋパラメータの値が、予測順位Ｍ（ｅ）の最小符号長となるｋパラメータの上限値を超えているか否かを判断する、と言い換えることもできる。
【０１０８】
位置（Ｋ［Ｓ］，Ｍ（ｅ））が、領域５１内にあると判断した場合には、ステップＳ１１０７へ処理を進め、フラグ配列の要素Ｆ[Ｓ]が“１”であるか否かを判定する。“１”でないと判定した場合には、フラグ配列要素Ｆ[Ｓ]に“１”を設定する（ステップＳ１１１０）。また、ステップＳ１１０７にて、フラグ配列の要素Ｆ[Ｓ]が“１”であると判定した場合には、Ｋ［Ｓ］から“１”を減じて更新し（ステップＳ１１０８）、フラグ配列の要素Ｆ［Ｓ］に“０”を設定する（ステップＳ１１０９）。
【０１０９】
一方、ステップＳ１１０３にて、位置（Ｋ［Ｓ］，Ｍ（ｅ））が領域５１に属さないと判断された場合には、ステップＳ１１０４に進んで、位置（Ｋ［Ｓ］，Ｍ（ｅ））が領域５２内にあるか否かを判定する。
【０１１０】
これは、現在のｋパラメータの値が、予測順位Ｍ（ｅ）の最小符号長となるｋパラメータの下限を下回っているか否かを判断する、と言い換えることもできる。
【０１１１】
位置（Ｋ［Ｓ］，Ｍ（ｅ））が領域５２内にあると判定した場合、Ｋ［Ｓ］に“１”を加えて更新し、Ｆ［Ｓ］に“０”を設定する（ステップＳ１１０６）。
【０１１２】
また、ステップＳ１１０４にて、位置（Ｋ［Ｓ］，Ｍ（ｅ））が領域５２に属さないと判定した場合、すなわち、位置（Ｋ［Ｓ］，Ｍ（ｅ））が領域５０内にあると判定した場合、現在の符号化処理状態は最適シンボル範囲にあると判定し、ｋパラメータの更新は行わない。
【０１１３】
これ以降、更新されたＫ［Ｓ］は着目画素以降、同じ状態番号Ｓとなる画素の符号化に適用される。
【０１１４】
以上をまとめると、本第２の実施形態では、位置（Ｋ［Ｓ］，Ｍ（ｅ））が領域５２内にある場合には第１の実施形態と同様に直ちにｋパラメータに１を加えて更新する。しかし、位置（Ｋ［Ｓ］，Ｍ（ｅ））が領域５１内にある場合には１を減じて更新する処理を、フラグＦ［Ｓ］を使用して１／２の頻度にしている。
【０１１５】
ここで、再び、あるｋパラメータで本実施形態の説明の冒頭で述べた確率分布ｆ（ｎ，ｋ）の情報源を符号化している場合を考える。本実施形態では、ｋを大きくする方向の更新が起こる確率が１２．５％、小さくする方向の更新が起こる確率が１２．５％以下と考えられるため、ｋパラメータの遷移が行われない確率が７５％以上に向上する。
【０１１６】
従って、ｋパラメータ更新における、増加方向と減少方向の確率の偏りを軽減し、かつ、不要なｋパラメータ変動の発生確率を少なくすることができる。
【０１１７】
第１の実施形態と同様にして、予測順位Ｍ（ｅ）はＧｏｌｏｍｂ符号化部１０６により、ｋパラメータ更新部１０７から出力されるｋパラメータを用いて符号化され、符号列形成部１０８にて符号化対象の画像データに対する符号列として結合される。符号列形成部１０８で生成された最終符号列は信号線１０９を通じて装置外部へと出力される。
【０１１８】
本第２の実施形態に係る画像処理装置による符号化対象画像データの符号化処理の流れは、図４に示した第１の実施形態の画像処理装置のフローチャートに僅かな変更が施されたのみである。具体的には、ステップＳ４０１からステップＳ４０４の処理のタイミングでコンテキスト生成部１００１によるコンテキスト生成処理が行われる。例えば、ステップＳ４０１による着目画素データの読み込みと、ステップＳ４０２による予測値生成の間で、このコンテキスト生成処理を実施するといった具合である。
【０１１９】
本第２の実施形態の画像処理装置で生成した符号化データを復号するにはヘッダに示される付加情報を参照して、符号化処理の逆の手順でそれぞれの画素を復号していくようにすれば良い。
【０１２０】
このとき、各シンボルの復号においてＧｏｌｏｍｂ符号化のｋパラメータは符号化側と復号側で同じ値を用いる。
【０１２１】
即ち、復号側でも符号化側と同じ初期値を与えて復号を開始し、復号したシンボルが現在のｋパラメータに対して最適シンボル範囲にあるか否かを判定し、符号化時と同じアルゴリズムで必要に応じて更新していけばよい。
【０１２２】
以上の説明のように、本第２の実施形態に係る画像処理装置では、簡易な方法により情報源の性質に追従した符号化を行うことができる。また、パラメータ遷移の頻度を調整することで、統計的性質の変化が少ない情報源に対して無用なパラメータ遷移を少なくすることができる。
【０１２３】
＜第３の実施形態＞
上述の第２の実施形態では、領域５１のシンボルが２回発生した場合にｋパラメータを減少させる手法について示したが、ｋパラメータによって更新を実施する発生回数を変えても構わない。その例を第３の実施形態として説明する。
【０１２４】
本第３の実施形態の画像処理装置のブロック図は、第２の実施形態で説明した図１０と同じであり、ｋパラメータ更新部１００２の処理のみ異なる。以下、本第３の実施形態におけるｋパラメータ更新部１００２の処理について説明する。
【０１２５】
本第３の実施形態のｋパラメータ更新部１００２は、図１２に示すようなインデックス値ｉとパラメータｋとの対応テーブル、および、コンテキスト生成部１００１により分類される３６５個の各状態番号Ｓについてインデクス値ｉを格納する配列Ｉ［Ｓ］を保持する。配列Ｉ［Ｓ］の全要素は符号化の開始時点で初期値（ここでは４とする）に設定される。つまり、状態番号Ｓのいずれであっても、初期状態のパラメータｋは「２」となる。より分かりやすく言えば、インデックスｉに基づくｋパラメータを配列Ｋ［ｉ］で表現するのであれば、Ｋ［ｉ］＝Ｋ［Ｉ［Ｓ］］と表記できる。
【０１２６】
図１３は、着目画素ｘの符号化時のｋパラメータ更新部１００２の処理の流れを示すフローチャートである。同図を用いて各画素で行われるｋパラメータ更新部１００２の処理の流れを説明する。
【０１２７】
ｋパラメータ更新部１００２は、コンテキスト生成部１００１から出力される状態番号Ｓと予測順位変換部１０５から出力される予測順位Ｍ（ｅ）を取得する（ステップＳ１３０１）。入力された状態番号Ｓのインデックス値配列の要素Ｉ［Ｓ］を取り出し、図１２の対応表を参照してこれに対応するｋパラメータの値をＧｏｌｏｍｂ符号化部１０６へと出力する（ステップＳ１３０２）。例えば、ある状態番号ＳについてＩ［Ｓ］の値が５であるとするならば、対応表を参照してｋパラメータはＫ［Ｉ［Ｓ］］＝Ｋ「５」となるので、ｋパラメータとして「３」をＧｏｌｏｍｂ符号化部１０６ｋに出力するといった具合である。これにより、Ｇｏｌｏｍｂ符号化部１０６は、注目画素ｘに対応する予測順位Ｍ（ｅ）の符号化を行なうことになる。
【０１２８】
続いて、現在のｋパラメータと、予測順位Ｍ（ｅ）で示される位置が領域５１内にあるか否かを判断する（ステップＳ１３０３）。その位置が領域５１内に属する場合にはステップＳ１３０８へ処理を移し、属さない場合にはステップＳ１３０４へと移る。
【０１２９】
領域５１に属する場合、配列要素Ｉ［Ｓ］が０であるか否かを調べ（ステップＳ１３０８）、０でない場合にはＩ［Ｓ］の値から１を減じて更新する（ステップＳ１３０９）。また、配列要素Ｉ［Ｓ］が０の場合には、それ以上の減算は行なわない。
【０１３０】
一方、ステップＳ１３０３にてパラメータｋとＭ（ｅ）で示される位置が領域５１外にあると判断された場合、その位置が領域５２内にあるか否かを判断する（ステップＳ１３０４）。
【０１３１】
領域５２内にあると判断した場合には、Ｉ［Ｓ］の値に“２”を加算して更新する（ステップＳ１３０５）。また、Ｉ［Ｓ］があらかじめ定めたインデックスの最大値（本実施形態の場合には２３）を超えていないかどうかを調べ（ステップＳ１３０６）、超えている場合にはＩ［Ｓ］を最大値に設定する（ステップＳ１３０７）。
【０１３２】
また、ステップＳ１３０４にて、パラメータｋとＭ（ｅ）で示される位置が領域５２に属さないと判断した場合、その位置は領域５０内にあることを示す。すなわち、最適シンボル範囲にあると判定し、インデックスＩ［Ｓ］の更新は行わない。更新されたＩ［Ｓ］は着目画素以降、同じ状態番号Ｓとなる画素の符号化の際に使用される。
【０１３３】
上記の処理からもわかるように、本第３の実施形態ではｋパラメータが小さい部分ではインデックスＩ［Ｓ］とｋパラメータの遷移が早く行われ、ｋパラメータが大きい部分では遷移がゆっくりになる例について示した。
【０１３４】
直接ｋパラメータを増減させて更新させるだけでなく、本第３の実施形態のようにインデックス値を導入して間接的にｋパラメータを制御することによって、符号化対象の情報源の動的特性に合わせて、より自由に符号化システムを設計することができる。
【０１３５】
＜他の変形例＞
本発明は上述した実施の形態に限定されるものではない。例えば、予測誤差の生成方法としてＪＰＥＧ−ＬＳと同じ方法により、ａ，ｂ，ａ＋ｂ−ｃの３種類の予測式を適応的に切り替える例を示したが、（ａ＋ｂ）／２など、これ以外の予測式を適用しても構わない。さらに、符号化済みの領域から予測値を生成する方法であれば良く、例えば、複数のフレームから構成される動画像において符号化済みの直前のフレームにおいて着目画素と同じ空間位置に存在する画素値を予測値とするといった手法を用いても良い。
【０１３６】
また、ＪＰＥＧ−ＬＳで採用されているように、符号化済みの予測誤差を参照することにより予測値を修正して予測精度を高めるようにしても構わない。
【０１３７】
また、予測誤差の符号を予測して符号反転したり、モジュロ変換によりダイナミックレンジを落とすといった効率改善の工夫と組み合わせて使用しても良い。
【０１３８】
また、第１乃至第３の実施形態では、符号長が最小となる範囲を基準としてｋパラメータの更新を判断する構成について示した。例えば、ｋ＝２である場合、符号化対象のシンボル（実施形態ではＭ（ｅ））が２〜１１である場合に最適シンボル範囲としてパラメータ更新を行わず、０または１である場合にｋを小さくする方向、１２以上の場合にｋを大きくする方向で更新処理を行った。
【０１３９】
しかしながら、例えば最小符号長＋１までを適切な範囲と考えるなど、範囲を広げたり狭めたりする修正を行っても良い。
【０１４０】
ｋ＝２で最小符号長＋１までを適切範囲と考えるならば、シンボルの値が１〜１５の場合にパラメータ更新が行われなくなり、パラメータの安定性が上がる。但し、この場合、ｋ＝１からｋ＝０へ遷移しなくなるので、ｋ＝１の場合には範囲の拡張を適用しないなどの例外処理が必要である。
【０１４１】
また、上述の実施形態では、エントロピ符号化としてパラメータ変数ｍ＝２＾ｋとなるＧｏｌｏｍｂ符号を用いる例について示したが、これに限定されるものではない。２＾ｋとならないｍを使用して本手法を適用しても構わない。さらに、Exponential-Golomb 符号など、Golomb符号の派生形に対して適用することもできる。
【０１４２】
また、実施形態では、特に符号化／復号を行なう画像処理装置を例にしたが、画像の符号化或いは復号を行なう装置、例えば複写機、プリンタ、リーダ等の装置に適当しても構わない。また、先に説明したように、本実施形態の機能は、コンピュータが読み込み実行するコンピュータプログラムによっても実現できるものであるから、当然、本発明はコンピュータプログラムをもその範疇とする。また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されていて、それをコンピュータの読み込み装置（ＣＤ−ＲＯＭドライブ等）にセットし、システムにコピーもしくはインストールすることで実行可能となる。よって、このようなコンピュータ可読記憶媒体も本発明の範疇にあるのは明らかである。
【図面の簡単な説明】
【０１４３】
【図１】第１の実施形態に係る画像処理装置のブロック構成図である。
【図２】周囲画素間の差分の量子化のためのテーブルを示す図である。
【図３】符号化対象画素ｘと、その周辺画素ａ，ｂ，ｃの相対位置関係を示す図である。
【図４】第１の実施形態に係る符号化処理の流れを示すフローチャートである。
【図５Ａ】Ｇｏｌｏｍｂ符号のｋパラメータと各シンボルの符号長の関係を示すテーブル図である。
【図５Ｂ】Ｇｏｌｏｍｂ符号のｋパラメータ、各シンボルの符号長、並びに、補正値の関係を示すテーブル図である。
【図６】第１の実施形態に係る画像処理装置におけるｋパラメータ遷移の例を示す図である。
【図７】ｋ＝１の場合に符号化効率が最大となる確率分布ｆ（ｎ、１）を示す図である。
【図８】ｋパラメータの遷移確率を示す図である。
【図９】本画像処理装置の出力符号列の構成を示す図である。
【図１０】第２および第３の実施形態に係る画像処理装置のブロック構成図である。
【図１１】第２の実施形態におけるｋパラメータ更新部１００２の処理の流れを示すフローチャートである。
【図１２】第３の実施形態におけるインデックス値iとパラメータｋとの対応を示す図である。
【図１３】第３の実施形態におけるｋパラメータ更新部１００２の処理の流れを示すフローチャートである。
【図１４】第１乃至第３の実施形態をソフトウェアで実現する場合の情報処理装置のブロック構成図である。
【図１５】第１の実施形態における復号を行う画像処理装置のブロック構成図である。
【図１６】Ｇｏｌｏｍｂ符号の例を示す図である。
【図１】
0004732203.tif 000002
【図２】
0004732203.tif 000003
【図３】
0004732203.tif 000004
【図４】
0004732203.tif 000005
【図５Ａ】
0004732203.tif 000006
【図５Ｂ】
0004732203.tif 000007
【図６】
0004732203.tif 000008
【図７】
0004732203.tif 000009
【図８】
0004732203.tif 000010
【図９】
0004732203.tif 000011
【図１０】
0004732203.tif 000012
【図１１】
0004732203.tif 000013
【図１２】
0004732203.tif 000014
【図１３】
0004732203.tif 000015
【図１４】
0004732203.tif 000016
【図１５】
0004732203.tif 000017
【図１６】
0004732203.tif 000018