(57)【要約】【課題】符号化効率を向上させることが可能な符号化装置を得る。【解決手段】情報源シンボルの出現確率を推定し、推定出現確率と記憶された特定の出現確率との一致を判定して、推定出現確率が特定の出現確率と一致しないと判定したとき、数直線上の有効区間を第１および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる。一方、推定出現確率が特定の出現確率と一致したと判定したとき、有効区間を特定の出現確率に応じた第１および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる。これらいずれかの方法で所定の情報源シンボルの値に対応させた第１および第２の部分区間のうち、情報源シンボルの値と同一の情報源シンボルの値に対応する部分区間を新たな有効区間とし、この有効区間の内部座標を符号として出力する。【選択図】図１
2006109486.tif 000002
【特許請求の範囲】
【請求項１】
情報源シンボルの出現確率を推定する確率推定手段と、
特定の情報源シンボル出現確率を記憶する記憶手段と、
上記確率推定手段が推定した推定出現確率と上記記憶手段に記憶されている特定の情報源シンボル出現確率との一致を判定する判定手段と、
この判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致しないと判定したとき、数直線上の有効区間を第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる第１の区間分割手段と、
上記判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致したと判定したとき、上記有効区間を上記特定の情報源シンボル出現確率に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる第２の区間分割手段と、
上記第１または第２の区間分割手段が上記所定の情報源シンボルの値に対応させた上記第１の部分区間と上記第２の部分区間のうち、上記情報源シンボルの値と同一の情報源シンボルの値に対応する部分区間を新たな上記有効区間とし、この有効区間の内部座標を符号として出力する符号化手段と
を備えることを特徴とする符号化装置。
【請求項２】
上記記憶手段は、上記特定の情報源シンボル出現確率として１／２のべき乗で表現できる確率を記憶し、
上記第２の区間分割手段は、上記有効区間に対して、上記記憶手段が記憶する１／２のべき乗倍に縮小処理した部分区間を上記第１の部分区間とすることを特徴とする請求項１記載の符号化装置。
【請求項３】
上記記憶手段は、上記特定の情報源シンボル出現確率をその２進小数指数部の正の整数値で記憶し、
上記第２の区間分割手段は、上記有効区間に対する１／２のべき乗倍の縮小処理に上記記憶手段が記憶する上記正の整数値で表される桁数の下位方向へのシフト演算を適用することを特徴とする請求項２記載の符号化装置。
【請求項４】
上記確率推定手段は、上記情報源シンボルの値を入力データの値と対応付け、上記入力データの値を上記情報源シンボルの値に変換するとともに、上記判定手段を利用して上記対応付けの更新要否を判定し、上記推定出現確率が上記特定の情報源シンボル出現確率である１／２となるときに、上記対応付けの更新を実行することを特徴とする請求項２に記載の符号化装置。
【請求項５】
上記符号化手段は、上記有効区間の区間幅と数直線上の位置座標を保持し、その区間幅と位置座標の更新処理を行うとともに、上記区間幅が所定の幅より小さくなると、上記有効区間の区間幅と位置座標を同一倍率で上記所定の幅より大きくなるまで拡大する正規化処理を行い、
上記判定手段における上記推定出現確率と上記特定の情報源シンボル出現確率との一致または不一致の判定によって、上記有効区間の区間幅と位置座標の更新処理と正規化処理を異なる手順で適用することを特徴とする請求項１記載の符号化装置。
【請求項６】
情報源シンボルの出現確率を推定する確率推定手段と、
特定の情報源シンボル出現確率を記憶する記憶手段と、
上記確率推定手段が推定した推定出現確率と上記記憶手段に記憶されている特定の情報源シンボル出現確率との一致を判定する判定手段と、
この判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致しないと判定したとき、数直線上の有効区間を第１の部分区間および第２の部分区間に分割し、
それぞれの部分区間を所定の情報源シンボルの値に対応させる第１の区間分割手段と、
上記判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致したと判定したとき、上記有効区間を上記特定の情報源シンボル出現確率に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる第２の区間分割手段と、
上記第１または第２の区間分割手段が上記所定の情報源シンボルの値に対応させた上記第１の部分区間と上記第２の部分区間のうち、入力される符号の値を内部座標としてもつ部分区間を新たな上記有効区間とし、その部分区間に対応されていた情報源シンボルの値と同一の情報源シンボルの値を出力する復号手段と
を備えることを特徴とする復号装置。
【請求項７】
上記記憶手段は、上記特定の情報源シンボル出現確率として１／２のべき乗で表現できる確率を記憶し、
上記第２の区間分割手段は、上記有効区間に対して、上記記憶手段が記憶する１／２のべき乗倍に縮小処理した部分区間を上記第１の部分区間とすることを特徴とする請求項６記載の復号装置。
【請求項８】
上記記憶手段は、上記特定の情報源シンボル出現確率をその２進小数指数部の正の整数値で記憶し、
上記第２の区間分割手段は、上記有効区間に対する１／２のべき乗倍の縮小処理に上記記憶手段が記憶する上記正の整数値で表される桁数の下位方向へのシフト演算を適用することを特徴とする請求項７記載の復号装置。
【請求項９】
上記確率推定手段は、上記情報源シンボルの値を出力データの値と対応付け、上記情報源シンボルの値を上記出力データの値に変換するとともに、上記判定手段を利用して上記対応付けの更新要否を判定し、上記推定出現確率が上記特定の情報源シンボル出現確率である１／２となるときに、上記対応付けの更新を実行することを特徴とする請求項７に記載の復号装置。
【請求項１０】
上記復号手段は、上記有効区間の区間幅と上記有効区間内部の位置座標として上記符号を保持し、その区間幅と位置座標の更新処理を行うとともに、上記区間幅が所定の幅より小さくなると、上記有効区間の区間幅と位置座標を同一倍率で上記所定の幅より大きくなるまで拡大する正規化処理を行い、
上記判定手段における上記推定出現確率と上記特定の情報源シンボル出現確率との一致または不一致の判定によって、上記有効区間の区間幅と位置座標の更新処理と正規化処理を異なる手順で適用することを特徴とする請求項６記載の復号装置。
【請求項１１】
情報源シンボルの出現確率を推定する確率推定ステップと、
この碓率推定ステップにおいて推定した推定出現確率と特定の情報源シンボル出現確率との一致を判定する判定ステップと、
この判定ステップにおいて上記推定出現確率が上記特定の情報源シンボル出現確率と一致しないと判定したとき、数直線上の有効区間を第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させるとともに、
上記判定ステップにおいて上記推定出現確率が上記特定の情報源シンボル出現確率と一致したと判定したとき、上記有効区間を上記特定の情報源シンボル出現確率に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる分割ステップと、
この分割ステップにおいて上記所定の情報源シンボルの値に対応させた上記第１の部分区間と上記第２の部分区間のうち、上記情報源シンボルの値と同一の情報源シンボルの値に対応する部分区間を新たな上記有効区間とし、この有効区間の内部座標を符号として出力する符号化ステップと
を備えることを特徴とする符号化方法。
【請求項１２】
情報源シンボルの出現確率を推定する確率推定ステップと、
この確率推定ステップにおいて推定した推定出現確率と特定の情報源シンボル出現確率との一致を判定する判定ステップと、
この判定ステップにおいて上記推定出現確率が上記特定の情報源シンボル出現確率と一致しないと判定したとき、数直線上の有効区間を第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させるとともに、
上記判定ステップにおいて上記推定出現確率が上記特定の情報源シンボル出現確率と一致したと判定したとき、上記有効区間を上記特定の情報源シンボル出現確率に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる分割ステップと、
この分割ステップにおいて上記所定の情報源シンボルの値に対応させた上記第１の部分区間と上記第２の部分区間のうち、入力される符号の値を内部座標としてもつ部分区間を新たな上記有効区間とし、その部分区間に対応されていた情報源シンボルの値と同一の情報源シンボルの値を出力する復号ステップと
を備えることを特徴とする復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを圧縮・解凍する符号化装置および復号装置ならびに符号化方法および復号方法に関するものである。
【背景技術】
【０００２】
従来より、従来技術として種々の提案がなされている（例えば、特許文献１参照）。
【０００３】
従来の符号化方式の一例として、高い圧縮率が得られる算術符号化について説明する。具体的に動作を説明する前に、図１６で２値算術符号化の概念を説明する。算術符号化は、０．０以上１．０未満の数直線上の２進小数座標値が符号Ｃとなる。処理過程において、上記数直線上の範囲を有効区間幅Ａとして２値シンボルの出現確率に比例して分割し、実際に出現したシンボルに対応する部分区間を新たな有効区間として分割を繰り返す。ＭＰＳ（More Probable Symbol）は出現確率がより高いデータ値が出たことを示す優勢シンボル、ＬＰＳ（Less Probable Symbol）は出現確率がより低いデータ値が出たことを示す劣勢シンボルである。最終シンボルで更新された有効区間内の１つの座標を符号として出力する。処理中は、符号Ｃを有効区間の下界値として計算し、同図において上界値と下界値の差である有効区間幅とともに更新される。最終的な符号は、座標末尾に続く０を切り捨てた有効区間内で有効桁数が最小の座標値を選択することもできる。
【０００４】
算術符号化の実用化に当たっては、符号演算時の有効桁数増加に対処した減算型算術符号化が一般に用いられる。以下、算術符号は減算型算術符号を指すものとする。図１７は、減算型算術符号化と正規化処理の概念を示す図である。ＬＳＺはＬＰＳに割当てられる部分区間であり、シンボルの出現確率に基づいて予め用意されたテーブルから近似値が選択される。ここで、有効区間が１／２を下回ると２のべき乗倍して１／２以上に拡大する正規化処理を行う。これにより、計算時の小数部の桁数は一定に保たれる。このとき、整数部において小数点から続く１とその上位の０となった桁については後の座標計算で桁上がりの伝播によって変更されることあるため値が確定していないが、それより上位桁は桁上がりの伝播がないため符号器外へ送出してしまうことができる。
【０００５】
最も代表的な減算型算術符号化の符号器（Encoder）・復号器（Decoder）は、ＩＴＵ−Ｔの国際標準勧告Ｔ．８２に記載されるテーブルおよび処理フローによって実現できる。以下、この算術符号化をＱＭコーダー（ＱＭ−Ｃｏｄｅｒ）と呼び、符号化対象データを２値画像として上記先行技術文献で規定される符号化および復号の演算処理について説明する。ここで、ＱＭコーダー（ＱＭ−Ｃｏｄｅｒ）の符号および復号の演算処理には、日本国特許第２１２８１１５号に示されるシンボルに対応する部分区間の補正技術が採用されている。これを図１８で説明するが、ここでは数値を１０進で表現する。同図（ａ）では有効区間が０．６に対して、ＬＰＺとして０．２が選択され、全体の１／３を占める。これは、１／２に満たないのでＬＰＳ、残りの区間をＭＰＳへ割り当てる。しかし、同図（ｂ）のように、ここではＬＳＺが２／３を占め、１／２を超えるとき、出現確率比と実際の占有率のシンボル対応が逆転するため、単純にＭＰＳとＬＰＳで区間を交換することにより補正し、符号化性能の低下を抑えている。これは「条件付きＭＰＳ／ＬＰＳ交換」と呼ばれている。
【０００６】
符号化および復号の演算処理の動作を説明するために必要となるＱＭコーダー（ＱＭ−Ｃｏｄｅｒ）の符号器１Ａおよび復号器１Ｂのブロック構成図を、それぞれ、図１９及び図２０に示す。本従来例では、画像メモリ５Ａおよび５Ｂを符号器１Ａ、復号器１Ｂの内部に配置されるものとして説明する。
【０００７】
これらの図１９及び図２０において、２はコンテクスト（Context）、３は符号化の対象となる画素（Pixel）、４は符号、５Ａ，５Ｂは画像メモリ、７は予測値テーブルＭＰＳ、８はステートテーブルＳＴ、９はＬＰＳ区間幅テーブルＬＳＺ、１０はＭＰＳ状態遷移先テーブルＮＭＰＳ、１１はＬＰＳ状態遷移先テーブルＮＬＰＳ、１２は予測値反転判定テーブルＳＷＴＣＨ、１３Ａ，１３Ｂは算術符号器、１４はシンボル、１５Ａ，１５Ｂは画素シンボル変換器である。
【０００８】
動作について説明する。ＱＭ符号器１Ａにおける画像メモリ５Ａは、入力される画像６を蓄積し、符号化の対象となる画素（Pixel）３に対してモデルテンプレート（Model Template）で所定の符号化済み画素を参照し、その生成されたパターンであるコンテクスト（Context）２と、同時に、符号化対象画素３を出力する。
【０００９】
一方、ＱＭ復号器１Ｂにおける画像メモリ５Ｂは、すでに復号された復号画素３を蓄積し、これから復号の対象とする画素に対するコンテクスト２を生成して出力し、そのコンテクストを使用して復号された復号対象画素を得て蓄え、画像６を出力する。
【００１０】
ＱＭコーダー（ＱＭ−Ｃｏｄｅｒ）では、符号化／復号対象画素に対する各コンテクストごとに画素値の予測一致確率を推定し、その変動に伴って学習しながら符号化／復号を進める。学習は、コンテクスト２をインデクスとする２つの変数テーブル７，８を書き換えることによって行われる。１つは、出現する確率の高い画素値ＭＰＳを予測値として記憶する各１ビットの予測値テーブルＭＰＳ７（以下、ＭＰＳテーブル７とする）である。もう１つは、予測値の予測一致確率の程度を総計１１３個の状態（State）に分類した状態番号（０〜１１２）を記憶する各７ビットのステートテーブルＳＴ８（以下、ＳＴテーブル８とする）である。
【００１１】
変数テーブル７，８の他に、符号化／復号の際に状態番号（ステート）をインデクスとして参照する定数テーブル（確率推定テーブル）９〜１２が存在する。すなわち、ＬＰＳ区間幅を１６ビットで表すＬＰＳ区間幅テーブルＬＳＺ９（以下、ＬＳＺテーブル９とする）、ＭＰＳ遷移先を７ビットで表すＭＰＳ状態遷移先テーブルＮＭＰＳ１０（以下、ＮＭＰＳテーブル１０とする）、ＬＰＳ遷移先を７ビットで表すＬＰＳ状態遷移先テーブルＮＬＰＳ１１（以下、ＮＬＰＳテーブル１１）、及び、予測値反転判定を１ビットで表す予測値反転判定テーブルＳＷＴＣＨ１２（以下、ＳＷＴＣＨテーブル１２とする）である（ここで示した英字の変数・定数テーブル名は、後述の処理フローで用いる配列名とする。）。
【００１２】
ＬＳＺテーブル９は、算術符号器１３Ａ／算術復号器１３Ｂ内の演算部で参照され、適応予測の学習には直接的には関係しない。算術符号器１３Ａ／算術復号器１３Ｂの内部ではＬＳＺ値を用いて演算が行われ、演算精度が低下した際には正規化処理（Renormalize）を行う。この正規化処理が行われるとき、同時に学習を行う。
【００１３】
正規化処理を発生したときの符号化／復号シンボル１４が優勢シンボルであればＮＭＰＳ値を、劣勢シンボルであればＮＬＰＳ値をＳＴテーブル８に書き込み、状態を更新する。優勢シンボルとは、符号化／復号対象画素３が予測値ＭＰＳ７と等しいことを示し、劣勢シンボルとはそれらが等しくないことを示している。符号化のときは、画素シンボル変換器１５Ａがシンボル１４を算術符号器１３Ａへ出力し、復号のときは、復号器１３Ｂがシンボル１４をシンボル画素変換器１５Ｂへ出力する。
【００１４】
また、正規化処理が劣勢シンボルによるものであるとき、その予測一致確率が１／２相当であればＭＰＳ値７を反転（演算「１−ＭＰＳ」）させてＭＰＳテーブル７に書き込む。一致確率が１／２であるかどうかは、ＳＷＴＣＨ値１２をフラグとして判定することができる。
【００１５】
このように、２つの変数テーブルＳＴ８およびＭＰＳ７に対して、それぞれ更新処理を行い、個別に管理しなければならない。
【００１６】
図２１に定数テーブルの例を示す。実際のＱＭコーダー（ＱＭ−Ｃｏｄｅｒ）の定数テーブルは１１３個の状態から構成されるが、簡単なモデルで説明する。ここでは、１０個の状態から構成され、状態０から状態９までＬＰＳの出現確率を０．５から０．０５刻みで小さくなるものとする。状態ｉでＭＰＳ処理時に正規化が発生したときＮＭＰＳ値を参照し、コンテクストで記憶される状態番号を（ｉ＋１）へ更新する。ｉ＝９であればそれ以上確率の低い状態へは遷移できないため留まる。また、状態ｉでＬＰＳ処理されたときＮＬＰＳ値を参照し、（ｉ−１）へ更新する。ｉ＝０であればそれ以上確率の高い状態へは遷移できないため留まるが、このときＳＷＴＣＨ＝１であるため、コンテクストで記憶される予測値ＭＰＳを反転値（１−ＭＰＳ）へ更新する。ここで、ＬＳＺは確率値とするのが理想であるが、実際には有効区間幅が０．５から１．０の間に存在するため、それらに起因する誤差をできるだけ小さくするように決定され、実際の確率をテーブルに持つとは限らない。同図では、単純に状態ｉと状態（ｉ＋１）の確率の平均値を記載した。
【００１７】
また、符号化および復号の演算処理で使用される符号化レジスタＣ３０Ａ、復号レジスタＣ３０Ｂおよび区間幅レジスタＡ３１のビット配置を図２２に示す。符号化レジスタＣ３０Ａにおいて、bit15とbit16の間に小数点を設定し、小数部"x"（１６ビット）はＬＳＺ９に基づく演算部Ｃｘ３２であり、キャリがある場合はより上位の整数部へ伝搬する。整数部において"b"（８ビット）はバイト出力部Ｃｂ３３、"c"（１ビット）は桁上がり判定部Ｃｃ３４である。桁上がりは、直前に出力された符号バイトに伝播され、必要ならばさらにそれ以前の出力バイトまで波及する。符号化の過程において、Ｃレジスタ値は符号４として符号化したシンボルに対応させた区間の下界値となるように更新される。
【００１８】
復号レジスタＣ３０Ｂにおいて、下位レジスタＣＬＯＷ３６と上位レジスタＣＨＩＧＨ３７は、bit23とbit24の間に小数点を設定し、"b"（８ビット）はバイト入力部（ＣＬＯＷレジスタ３５）と同じＣｂ３６、"x"（１７ビット）はＬＳＺ９に基づく演算部Ｃｘ（ＣＨＩＧＨレジスタ３７）３８である。復号の過程において、Ｃレジスタ値は復号したシンボルに対応させた区間の下界値からその区間内の座標である符号４へのオフセット値となるように更新される。
【００１９】
Ｃｂにおける符号バイト入出力は、レジスタ以外の補助変数であるＣＴ５０で正規化処理によるＣレジスタ３０Ａ、３０ＢおよびＡレジスタ３１のシフト数を計数し、値が０となったとき行われる。ＣＴ５０の初期値、再設定値は８である。先行技術文献（勧告T.82）に規定される符号化レジスタは、ＣｘとＣｂの間にＣｓがあるが、説明を簡単にするため省略しているが、Ｃｓを設けるならばその桁数を変数ＣＴの初期値に加える必要がある。また、復号レジスタの整数部bit24は規定されてはおらず、本従来例においては不要である。ＣＬＯＷレジスタ３６は１６ビットで規定されるがＣｂより下位８ビットは使用されないため省略している。これらの記載変更はいずれも符号化性能に影響するものではない。
【００２０】
符号化および復号で共通に使用される区間幅レジスタＡ３１は、符号化／復号レジスタ３０Ａ，３０Ｂの小数点に対応して、"x"レジスタ部に合わせて"a"（１６ビット）が小数部として配置され、初期状態の値でのみ整数部（bit16）が"1"となる。区間幅（区間サイズともいう）は、Ａ−ＬＳＺ（下方区間幅）またはＬＳＺ（上方区間幅）に更新され、初期値(整数部＝"１"）を除いて１／２の重みを示すbit15が"1"となるように正規化され、１／２以上に保つことによって上方区間幅としていかなるＬＳＺ９を選択しても下方区間の確保を保証している。正規化処理では、Ａレジスタ３１、Ｃレジスタ３０Ａまたは３０Ｂを同時に拡大する。
【００２１】
ＱＭコーダー（ＱＭ−Ｃｏｄｅｒ）では、状態に対して固定サイズとなる上方区間ＬＳＺ９は通常ＬＰＳに割り当てられるが、下方区間が上方区間より小さくなるときにはＭＰＳに割り当てる「条件付きＭＰＳ／ＬＰＳ交換」を行っている。ＬＰＳを符号化／復号したとき、および「条件付きＭＰＳ／ＬＰＳ交換」を適用してＭＰＳを符号化／復号したときには正規化処理が必ず行われる。
【００２２】
まず、符号化の演算処理を具体的な処理フローに沿って説明する。
【００２３】
符号化演算処理の開始時において、Ｃレジスタ３０Ａ（図２２）の初期値は０、Ａレジスタ３１の初期値は0x10000、補助変数ＣＴ５０の初期値は上記Ｃレジスタの仕様に基づき８となる。また、すべてのコンテクスト（参照パターン）ＣＸ２（図１９）に対する予測値ＭＰＳ［ＣＸ］７および状態ＳＴ［ＣＸ］８の初期値は０とする。そして、符号化終了時は符号化レジスタ３０Ａの内容を最終符号４として掃き出す規定の処理を行う。
【００２４】
図２３は、符号化対象画素値３と予測値７の一致・不一致から呼び出す処理を切り替える符号化処理（ＥＮＣＯＤＥ）フローである。ステップS１１１では画素値ＰＩＸ３と予測値ＭＰＳ［ＣＸ］７の一致・不一致を判定し、一致ならばＭＰＳ、不一致ならばＬＰＳを符号化する。ステップＳ１１２ではＣＯＤＥＬＰＳ（ＬＰＳ符号化）を呼び出してＬＰＳを、ステップＳ１１３ではＣＯＤＥＭＰＳ（ＭＰＳ符号化）を呼び出してＭＰＳを符号化する。
【００２５】
図２４は、符号化対象画素値３と予測値７が不一致のとき、すなわちＬＰＳを符号化する際に呼び出されるＣＯＤＥＬＰＳ処理フローである。まず、ステップＳ１２０でＬＳＺをＬＳＺ［ＳＴ［ＣＸ］］とする。ステップＳ１２１ではＡレジスタ３１値を一時的に下方区間幅に更新する。ステップＳ１２２の判定でＬＳＺ値（上方区間幅）がＡ値（下方区間幅）より大きければ（Ｙｅｓ）、条件付きＭＰＳ／ＬＰＳ交換が適用され、Ａレジスタ３１値、Ｃレジスタ３０Ａ値ともそのままで有効区間をより小さい下方区間に更新する。ＬＳＺ（上方区間幅）がＡ（下方区間幅）以下ならば（Ｎｏ）、ステップＳ１２３でＣレジスタ３０Ａに下方区間幅（現Ａレジスタ３１）を加えた後、ステップＳ１２４でＡレジスタ３１をＬＳＺとして有効区間をより小さい上方区間に更新する。ステップＳ１２５の判定で定数ＳＷＴＣＨ値１２が１ならば、ステップＳ１２６で予測値７（ＭＰＳテーブル）の反転・更新を行う。ＬＰＳ符号化では、ステップＳ１２７でＮＬＰＳテーブル１１参照による状態遷移を行い、ステップＳ１２８でＲＥＮＯＲＭＥを呼び出して正規化処理を行う。
【００２６】
図２５は、符号化対象画素値３と予測値７が一致のとき、すなわちＭＰＳを符号化する際に呼び出されるＣＯＤＥＭＰＳ処理フローである。まず、ステップＳ１３０でＬＳＺをＬＳＺ［ＳＴ［ＣＸ］］とする。ステップＳ１３１ではＡレジスタ３１値を一時的に下方区間幅に更新する。ステップＳ１３２の判定でＡレジスタ３１値が０ｘ８０００以上ならば（Ｎｏ）、本処理フローを終了する。Ａレジスタ３１値が０ｘ８０００未満ならば（Ｙｅｓ）、ステップＳ１３３の判定でＬＳＺ値（上方区間幅）がＡ値（下方区間幅）より小さければ（Ｙｅｓ）、条件付きＭＰＳ／ＬＰＳ交換が適用され、ステップＳ１３４でＣレジスタ３０Ａに下方区間幅（現Ａレジスタ３１）を加えた後、ステップＳ１３５でＡレジスタ３１をＬＳＺとして有効区間をより大きい上方区間に更新する。一方、ステップＳ１３３の判定で、ＬＳＺ（上方区間幅）がＡ（下方区間幅）以上ならば（Ｎｏ）、Ａレジスタ３１値、Ｃレジスタ３０Ａ値ともそのままで有効区間をより大きい下方区間に更新する。ＭＰＳ符号化では、ステップＳ１３６でＮＭＰＳテーブル１０参照による状態遷移を行い、ステップＳ１３７でＲＥＮＯＲＭＥを呼び出して正規化処理を行う。
【００２７】
図２６は、正規化処理を行うＲＥＮＯＲＭＥ処理フローである。ステップＳ１４１ではＡレジスタ３１、ステップＳ１４２ではＣレジスタ３０Ａを１ビット上位へシフトすることによって２倍の乗算と等価な演算を行う。ステップＳ１４３で変数ＣＴ５０から１を減じ、ステップＳ１４４で変数ＣＴ５０が０か否か判定し、判定がＹｅｓならば、ステップＳ１４５でＣレジスタ３０Ａ（Ｃｂ）から１バイト符号４を出力し、変数ＣＴ５０に８を再設定する。ステップＳ１４６の判定は、正規化処理の終了判定を行っており、Ａレジスタ３１が０ｘ８０００未満ならばステップＳ１４１からステップＳ１４５を繰り返し、０ｘ８０００以上となれば区間が１／２以上となり終了する。
【００２８】
ステップＳ１４５において、Ｃｂレジスタ３３から符号４を１バイト出力するとき、Ｃｃレジスタ３４によりキャリを判定し、既に出力済みの符号バイトへの伝播を行うことになる。そして、キャリ伝播、符号バイト出力の後、Ｃｂレジスタ３３およびＣｃレジスタ３４をクリアする。
【００２９】
次に、復号の演算処理を具体的な処理フローに沿って説明する。
【００３０】
復号演算処理の開始時において、Ｃレジスタ３０Ｂは小数部bit０からbit２３に符号を３バイト入力して初期値とし、Ａレジスタ３１の初期値は0x10000である。また、補助変数ＣＴ５０の初期値は８とし、すべてのコンテクスト（参照パターン）ＣＸ２に対する予測値ＭＰＳ［ＣＸ］７および状態ＳＴ［ＣＸ］８の初期値は０とする。
【００３１】
図２７は、復号対象画素を復号するＤＥＣＯＤＥ処理（復号処理）フローである。まず、ステップＳ２２０でＬＳＺをＬＳＺ［ＳＴ［ＣＸ］］とする。ステップＳ２２１ではＡレジスタ３１値を一時的に下方区間幅に更新する。ステップＳ２２２の判定で符号ＣＨＩＧＨレジスタ３７値がＡレジスタ３１値未満ならば（Ｙｅｓ）、下方区間を復号する。次に、ステップＳ２２３の判定でＡレジスタ３１値が０ｘ８０００未満ならば（Ｙｅｓ）、ステップＳ２２４でＭＰＳ＿ＥＸＣＨＡＮＧＥを呼び出し、ステップＳ２２５でＲＥＮＯＲＭＤを呼び出して正規化処理を行う。一方、ステップＳ２２３の判定で、Ａレジスタ３１値が０ｘ８０００以上ならば（Ｎｏ）、正規化処理することなくＭＰＳを復号し、ステップＳ２２６で画素値３を予測値７とすることで、Ａレジスタ３１値、Ｃレジスタ３０Ｂ値ともそのままで有効区間をより大きい下方区間に更新する。また、ステップＳ２２２の判定で符号ＣＨＩＧＨレジスタ３７値がＡレジスタ３１値以上ならば（Ｎｏ）、上方区間を復号する。ステップＳ２２７でＬＰＳ＿ＥＸＣＨＡＮＧＥを呼び出し、ステップＳ２２８でＲＥＮＯＲＭＤを呼び出して正規化処理を行う。ＭＰＳ＿ＥＸＣＨＡＮＧＥ，ＬＰＳ＿ＥＸＣＨＡＮＧＥを呼び出す処理経路では、それぞれ復号すべき区間は決まっていても区間の大小を比較しないと復号対象がＭＰＳかＬＰＳか判断できない。呼び出した処理フローでそれぞれ復号される画素値３を決定する。
【００３２】
図２８は、上方区間を復号するＬＰＳ＿ＥＸＣＨＡＮＧＥ処理フローである。ステップＳ２３１の判定でＬＳＺ値（上方区間幅）がＡ値（下方区間幅）より小さければ（Ｙｅｓ）、条件付きＭＰＳ／ＬＰＳ交換が適用され、ステップＳ２３２でＣＨＩＧＨレジスタ３７に下方区間幅（現Ａレジスタ３１）を減じた後、ステップＳ２３３でＡレジスタ３１をＬＳＺとする。このとき上方区間は下方区間より大きいためＭＰＳを復号し、ステップＳ２３４で画素値３を予測値７とし、ステップＳ２３５でＮＭＰＳテーブル１０参照による状態遷移を行う。ＬＳＺ（上方区間幅）がＡ（下方区間幅）以上ならば（Ｎｏ）、ステップＳ２３６でＣＨＩＧＨレジスタ３７に下方区間幅（現Ａレジスタ３１）を減じた後、ステップＳ２３７でＡレジスタ３１をＬＳＺとする。このとき上方区間は下方区間より小さいためＬＰＳを復号し、ステップＳ２３８で画素値３を非予測値（１−予測値７）とする。ステップＳ２３９の判定で定数ＳＷＴＣＨ値１２が１ならば、ステップＳ２４０で予測値７（ＭＰＳテーブル）の反転・更新を行う。ステップＳ２４１でＮＬＰＳテーブル１１参照による状態遷移を行う。
【００３３】
図２９は、下方区間を復号するＭＰＳ＿ＥＸＣＨＡＮＧＥ処理フローである。ステップＳ２５１の判定でＬＳＺ値（上方区間幅）がＡ値（下方区間幅）より小さければ（Ｙｅｓ）、条件付きＭＰＳ／ＬＰＳ交換が適用され、ＬＰＳを復号し、ステップＳ２５２で画素値３を非予測値（１−予測値７）とすることで、Ａレジスタ３１値、Ｃレジスタ３０Ｂ値ともそのままで有効区間をより小さい下方区間に更新する。次に、ステップＳ２５３の判定で定数ＳＷＴＣＨ値１２が１ならば、ステップＳ２５４で予測値７（ＭＰＳテーブル）の反転・更新を行い、ステップＳ２５５でＮＬＰＳテーブル１１参照による状態遷移を行う。一方、ステップＳ２５１の判定で、ＬＳＺ（上方区間幅）がＡ（下方区間幅）以上ならば（Ｎｏ）、ＭＰＳを復号し、ステップＳ２５６で画素値３を予測値７とし、ステップＳ２５７でＮＭＰＳテーブル１０参照による状態遷移を行う。
【００３４】
図３０は、正規化処理を行うＲＥＮＯＲＭＤ処理フローである。ステップＳ２６１で変数ＣＴ５０が０か否か判定し、判定がＹｅｓならばステップＳ２６２でＣレジスタ３０Ｂ（Ｃｂ）へ１バイト符号４を入力し、変数ＣＴ５０に８を再設定する。ステップＳ２６３ではＡレジスタ３１、ステップＳ２６４ではＣレジスタ３０Ｂを１ビット上位へシフトすることによって２倍の乗算と等価な演算を行う。ステップＳ２６５で変数ＣＴ５０から１を減じる。ステップＳ２６６の判定は、正規化処理の終了判定を行っており、Ａレジスタ３１が0x8000未満ならばステップＳ２６１からステップＳ２６５を繰り返す。ステップＳ２６７で変数ＣＴ５０が０か否か判定し、判定がＹｅｓならばステップＳ２６８でＣレジスタ３０Ｂ（Ｃｂ）に１バイト符号４を入力し、変数ＣＴ５０に８を再設定する。
【００３５】
なお、上記符号化および復号の演算処理フローにおいて、従来例として引用した上述の先行技術文献（勧告Ｔ．８２）では、上記ステップＳ１２０、Ｓ１３０、Ｓ２２０は記載されておらず、ＬＳＺテーブル９の参照形式で各演算式に直接記載されているが、ここでは、後述の本発明の説明上、処理フローの中でインデクスＳＴ［ＣＸ］を表記しない（テーブル参照形式でない）変数ＬＳＺとして参照できることを明示的に表した。
【００３６】
【特許文献１】特開平８−２４２１７５号公報
【発明の開示】
【発明が解決しようとする課題】
【００３７】
従来の符号化装置および復号装置ならびに符号化方法および復号方法では、算術符号化および復号の過程で有効区間を分割するとき、有効区間幅に関わらず固定近似値を部分区間に割当てるので、その占有率とシンボルの推定出現確率の誤差が大きくなって符号化効率が低下するという問題点があった。
【００３８】
この発明は、かかる問題点を解決するためになされたものであり、特定の確率値のシンボルでは、有効区間を当該特定の確率値に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させて、情報源シンボルの値と同一の情報源シンボルの値に対応する部分区間を新たな上記有効区間とすることによって符号化効率を向上させることが可能な符号化装置及び復号化装置、ならびに、符号化方法及び復号化方法を得ることを目的とする。
【課題を解決するための手段】
【００３９】
この発明は、情報源シンボルの出現確率を推定する確率推定手段と、特定の情報源シンボル出現確率を記憶する記憶手段と、上記確率推定手段が推定した推定出現確率と上記記憶手段に記憶されている特定の情報源シンボル出現確率との一致を判定する判定手段と、この判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致しないと判定したとき、数直線上の有効区間を第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる第１の区間分割手段と、上記判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致したと判定したとき、上記有効区間を上記特定の情報源シンボル出現確率に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる第２の区間分割手段と、上記第１または第２の区間分割手段が上記所定の情報源シンボルの値に対応させた上記第１の部分区間と上記第２の部分区間のうち、上記情報源シンボルの値と同一の情報源シンボルの値に対応する部分区間を新たな上記有効区間とし、この有効区間の内部座標を符号として出力する符号化手段とを備える符号化装置である。
【発明の効果】
【００４０】
この発明は、情報源シンボルの出現確率を推定する確率推定手段と、特定の情報源シンボル出現確率を記憶する記憶手段と、上記確率推定手段が推定した推定出現確率と上記記憶手段に記憶されている特定の情報源シンボル出現確率との一致を判定する判定手段と、この判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致しないと判定したとき、数直線上の有効区間を第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる第１の区間分割手段と、上記判定手段において上記推定出現確率が上記特定の情報源シンボル出現確率と一致したと判定したとき、上記有効区間を上記特定の情報源シンボル出現確率に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させる第２の区間分割手段と、上記第１または第２の区間分割手段が上記所定の情報源シンボルの値に対応させた上記第１の部分区間と上記第２の部分区間のうち、上記情報源シンボルの値と同一の情報源シンボルの値に対応する部分区間を新たな上記有効区間とし、この有効区間の内部座標を符号として出力する符号化手段とを備える符号化装置であるので、特定の確率値のシンボルでは、有効区間を当該特定の確率値に応じた第１の部分区間および第２の部分区間に分割し、それぞれの部分区間を所定の情報源シンボルの値に対応させて、情報源シンボルの値と同一の情報源シンボルの値に対応する部分区間を新たな上記有効区間とすることによって符号化効率を向上させることができる。
【発明を実施するための最良の形態】
【００４１】
本実施の形態では、減算型算術符号のシンボルに対応させる部分区間の補正を従来例の簡易な構成をほぼ保ったまま圧縮性能を向上させる技術について説明する。
【００４２】
実施の形態１．
上述の従来例のような減算型算術符号において、出現推定確率が０．５に近い状態ではＬＳＺ区間の有効区間に対する占有率は非常に高いものとなり、その誤差の大きさが符号化性能の低下の原因となる。本実施の形態では、従来の定数テーブルのＳＷＴＣＨテーブル１２を予測値反転実行判定にのみ用いるのではなく、ＬＳＺテーブル９参照以外に部分区間幅を得るために兼用する。ＳＷＴＣＨテーブル１２は、状態の推定確率値が０．５であることを示すので、このときはＡレジスタ３１値の大小に関わらず、ＬＳＺテーブル９から状態に対する固定値を割り当てるのではなく、Ａレジスタ３１値の１／２を割り当てるようにし、推定確率と有効区間に対する占有率の誤差を縮小し、符号化性能の向上を図る。
【００４３】
図１、図２は、本実施の形態における符号器および復号器の概略構成図を示している。図１９、図２０に示された従来の概略構成図に対して、算術符号器１３Ａ、算術復号器１３Ｂが上記ＳＷＴＣＨテーブル値１２を参照する構成をとっている点が異なり、他の構成については従来例と同様であるため、ここでは説明を省略する。
【００４４】
符号化および復号の演算処理について、具体的な処理フローを用いて説明する。本実施の形態において、図２３のＥＮＣＯＤＥ処理フロー、図２６のＲＥＮＯＲＭＥ処理フロー、図２８のＬＰＳ＿ＥＸＣＨＡＮＧＥ処理フロー、図２９のＭＰＳ＿ＥＸＣＨＡＮＧＥ処理フロー、図３０のＲＥＮＯＲＭＤ処理フローは従来のまま変更せず適用するものとする。
【００４５】
図３は、ＬＰＳを符号化するＣＯＤＥＬＰＳ処理（ＬＰＳ符号化）フローであり、図２４のステップＳ１２０をステップＳ１２０'へ変更したものである。ステップＳ１２０'では、現状態ＳＴ［ＣＸ］に対する定数ＳＷＴＣＨ１２値が０ならば（ステップＳ１２０'−１）、従来通りＬＳＺ［ＳＴ［ＣＸ］］を与え（ステップＳ１２０'−２）、一方、０でなければＡレジスタ３１値の１／２を与える（ステップＳ１２０'−３）。ここでは、Ａレジスタ３１値をＳＷＴＣＨ１２値（＝１）桁だけ右シフトすることにより算出している。このように変数ＬＳＺを設定し、ステップＳ１２１以下の処理は図２４の処理フローと同一である。
【００４６】
図４は、ＭＰＳを符号化するＣＯＤＥＭＰＳ処理（ＭＰＳ符号化）フローであり、図２５のステップＳ１３０をステップＳ１３０'へ変更したものである。ステップＳ１３０'は、上記図３のＳ１２０'と同一の処理であり、またＳ１３１以下の処理は図２５の処理フローと同一である。
【００４７】
図５は、復号対象画素を復号するＤＥＣＯＤＥ処理（復号処理）フローであり、図２７のステップＳ２２０をステップＳ２２０'へ変更したものである。ステップＳ２２０'は、上記図３のステップＳ１２０'と同一の処理であり、またステップＳ２２１以下の処理は図２７の処理フローと同一である。
【００４８】
以上のように、本実施の形態における符号器及び複合器は、学習しながら情報源シンボルの出現確率を推定し、上記推定出現確率の近似値を適用する第１の部分区間と残りの第２の部分区間との２つの部分区間に数直線上の有効区間を分割し、出現したシンボルに対応した部分区間を新たな上記有効区間とする算術符号を適用した符号化装置および復号装置であって、推定出現確率が特定値（ここでは０）であることを記憶する記憶手段（ＳＷＴＣＨテーブル１２）と、記憶手段を参照して推定出現確率が当該特定値であることを判定する判定手段（ステップＳ１２０'−１）と、推定出現確率が当該特定値であることが判定されたときに上記第１、第２の部分区間の割当てを補正する補正手段（ステップＳ１２０'−３）とを備えて、推定出現確率として特定値をとるシンボルに対して部分区間の割当てを補正するようにしたので、符号化性能が向上するという効果が得られる。
【００４９】
なお、本実施の形態では、ＳＷＴＣＨ１２値が１のとき、Ａレジスタ３１値をＳＷＴＣＨ１２値桁だけ右シフトさせてＬＳＺを算出しているが、直接の整数値１と記述しても構わない。また、復号処理フローにおいて、ステップＳ２６７およびステップＳ２６８でＣＴ５０値が０になった時点で次の符号４をＣＬＯＷレジスタ３５に１バイト読み込んでいるが、次のシフト操作で実際に符号４が必要になるまで待ってステップＳ２６１およびステップＳ２６２で読み込んでも構わない。その読込みまでＣＬＯＷレジスタ３５は空のままの状態で復号の演算処理がＣＨＩＧＨレジスタ３７上で進められても問題ない。
【００５０】
また、本実施の形態は、出現推定確率がほぼ０．５である状態の符号化および復号について符号化性能を向上させる効果がある。例えば、２値画像データにおいて、特にディザ手法あるいは誤差拡散手法で表現された疑似中間調画像では学習が進んでも推定確率がほとんど偏ることなく０．５に近い状態に留まることが知られており、文字画像への適用に比較してこの効果がより期待できる。
【００５１】
本実施の形態では、分割されたより大きい区間にＭＰＳを割り当てる条件付きＭＰＳ／ＬＰＳ交換を行う上記先行技術文献の符号化および復号の演算処理フローについて説明したが、上記部分区間を交換しない算術符号化および算術復号においては、さらにＬＳＺ区間の有効区間に対する占有率は推定確率と大小関係が逆転することさえあるため、本手法の適用効果がより大きく得られることはいうまでもない。この効果は、本実施の形態以降の他の実施の形態についても同様である。
【００５２】
実施の形態２．
上述の実施の形態１では、ＬＳＺ値の決定に際してＳＷＴＣＨ１２値の参照を行い、さらに、図３のＣＯＤＥＬＰＳ処理フロー、従来のまま適用する図２８のＬＰＳ＿ＥＸＣＨＡＮＧＥ処理フロー、図２９のＭＰＳ＿ＥＸＣＨＡＮＧＥ処理フローにおいて再度参照を行っており、またＡレジスタ３１値を１／２とすれば正規化処理により直ちに２倍されることになり、１ビットのシフトで終了することは明白であっても図２６のＲＥＮＯＲＭＥ処理フロー、図３０のＲＥＮＯＲＭＤ処理フローでは正規化終了判定を形式上行う点で処理フローに冗長度が大きい。また、Ａレジスタ３１値が奇数であれば１／２とした時点で桁落ちによる誤差が発生して厳密な１／２とはならない。つまり、Ａレジスタ３１値（奇数）を１桁シフトして縮小して部分区間とし、その後その部分区間を正規化処理により１桁シフトして拡大しても元のＡレジスタ３１値には戻らないということである。ただし、ＬＰＳ区間幅とすべきＬＳＺがＡ−ＬＳＺより１小さくなる点ではシンボルの定義上では理に適っているといえる。本実施の形態では、ＳＷＴＣＨ値により処理経路を分離することにより上記冗長度を改善し、正規化手順の変更により上記桁落ち誤差を解消する処理フローを提供する。すなわち、本実施の形態においては、記憶手段が記憶する特定値の一つを１／２とし、該当シンボルに対して上記推定出現確率の推定対象シンボル値の更新を伴う一連の演算処理操作を非該当シンボルの演算処理操作から独立させて構成する。
【００５３】
ここで説明する処理フローにおいて、新しく加えた処理は破線枠で囲み、破線枠内の処理番号は、対応する従来の処理番号にダッシュを付けて示している。本実施例において、図２３のＥＮＣＯＤＥ処理フロー、図２６のＲＥＮＯＲＭＥ処理フロー、図３０のＲＥＮＯＲＭＤ処理フローは従来のまま変更せず適用するものとする。
【００５４】
図６は、ＬＰＳを符号化する本実施の形態におけるＣＯＤＥＬＰＳ処理（ＬＰＳ符号化）フローであり、図２４からステップＳ１２５及びＳ１２６を抜き、ステップＳ１２０の前に破線で囲まれた処理を加えたものである。ステップＳ１２５'の判定ではＳＷＴＣＨ１２値が１のとき破線枠内の処理経路へ切り替える。ステップＳ１２６'で予測値７（ＭＰＳテーブル）の反転・更新を行い、ステップＳ１２７'でＮＬＰＳテーブル１１参照による状態遷移を行う。ステップＳ１４２'は正規化のシフト処理であり、この後、ステップＳ１２３'でＣレジスタ３０ＡにＡレジスタ３１を加える手順により桁落ちを防止している。正規化処理のステップＳ１４３'で変数ＣＴ５０から１を減じ、ステップＳ１４４'で変数ＣＴ５０が０か否か判定し、判定がＹｅｓならばステップＳ１４５'でＣレジスタ３０Ａ（Ｃｂ）から１バイト符号４を出力し、変数ＣＴ５０に８を再設定する。ＳＷＴＣＨ１２値が１でなければステップＳ１２０からステップＳ１２８までステップＳ１２５、ステップＳ１２６を除いて図２４の処理フローと同一である。
【００５５】
図７は、MＰＳを符号化するＣＯＤＥMＰＳ処理（ＭＰＳ符号化）フローであり、図２５のステップＳ１３０の前に破線で囲まれた処理を加えたものである。ステップＳ１３８の判定によりＳＷＴＣＨ１２値が１のとき破線枠内の処理経路を切り替える。ステップＳ１３６'でＮＭＰＳテーブル１０参照による状態遷移を行う。ステップＳ１４２'は正規化のシフト処理である。ステップＳ１４３'で変数ＣＴ５０から１を減じ、ステップＳ１４４'で変数ＣＴ５０が０か否か判定し、判定がＹｅｓならばステップＳ１４５'でＣレジスタ３０Ａ（Ｃｂ）から１バイト符号４を出力し、変数ＣＴ５０に８を再設定する。ＳＷＴＣＨ１２値が１でなければステップＳ１３０からステップＳ１３７まで図２５の処理フローと同一である。
【００５６】
図８は、復号対象画素を復号するＤＥＣＯＤＥ処理フローであり、図２７のステップＳ２２０の前に破線で囲まれた処理を加えたものである。ステップＳ２３９'（ステップＳ２５３'にも相当）の判定によりＳＷＴＣＨ１２値が１のとき破線枠内の処理経路を切り替え、Ａ点から後述の図９の処理フローを実行し、Ｂ点へ戻る。ＳＷＴＣＨ１２値が１でなければステップＳ２２０からステップＳ２２８まで図２７の処理フローと同一である。
【００５７】
図９は、図８に示しきれなかった部分、すなわち、図８の（Ａ）から（Ｂ）までのＤＥＣＯＤＥ処理フローである。ステップＳ２６４'は正規化のシフト処理であり、ステップＳ２６５'で変数ＣＴ５０から１を減じる。ステップＳ２２２'の判定で符号ＣＨＩＧＨレジスタ３７値がＡレジスタ３１値未満ならば（Ｙｅｓ）、下方区間を復号する。本処理フロー部では、下方区間幅と上方区間幅は等しいため、下方区間はＭＰＳに対応する。よって、ステップＳ２５６'で画素値３を予測値７とし、ステップＳ２５７'でＮＭＰＳテーブル１０参照による状態遷移を行う。ステップＳ２２２'の判定で符号ＣＨＩＧＨレジスタ３７値がＡレジスタ３１値以上ならば（Ｎｏ）、ＬＰＳに対応する上方区間を復号する。ステップＳ２３６'でＣＨＩＧＨレジスタ３７に下方区間幅を減じ、ステップＳ２３８'で画素値３を非予測値（１−予測値７）とする。本処理フロー部ではＳＷＴＣＨ１２値は必ず１であるため、図２８の判定ステップＳ２３９は不要となり、ステップＳ２４０'で予測値７（ＭＰＳテーブル）の反転・更新を行う。ステップＳ２４１'でＮＬＰＳテーブル１１参照による状態遷移を行う。状態遷移後、ステップＳ２６７'で変数ＣＴ５０が０か否か判定し、判定がＹｅｓならばステップＳ２６８'でＣレジスタ３０Ｂ（Ｃｂ）に１バイト符号４を入力し、変数ＣＴ５０に８を再設定する。
【００５８】
図１０は、上方区間を復号するＬＰＳ＿ＥＸＣＨＡＮＧＥ処理（上方区間の復号）フローである。図８の判定ステップＳ２３９'によって、本処理フローはＳＷＴＣＨ１２値が１のシンボルの処理経路ではないため、ステップＳ２３９およびＳ２４０は不要となるため削除し、それ以外の処理は図２８の処理フローと同一である。
【００５９】
図１１は、下方区間を復号するＭＰＳ＿ＥＸＣＨＡＮＧＥ処理（下方区間の復号）フローである。図８の判定ステップＳ２３９'によって、本処理フローはＳＷＴＣＨ１２値が１のシンボルの処理経路ではないため、ステップＳ２５３およびＳ２５４は不要となるため削除し、それ以外の処理は図２９の処理フローと同一である。
【００６０】
本実施の形態は、有効区間の演算後、正規化処理による拡大を行う従来例に対して、演算と正規化処理を処理フロー上分けずに拡大後に演算する手順として記述したため、ＳＷＴＣＨ１２値が１のとき、Ａレジスタ３１のＭＰＳおよびＬＰＳの部分区間を等分割する際の表現精度上の制約による桁落ち誤差を防止できる。ただし、先に正規化のシフト処理を実行してＣＨＩＧＨレジスタ３７を演算するため、図２４のＣレジスタ３０Ｂに整数部１桁(bit24)が必要となる。
【００６１】
また、符号化および復号の際にＡレジスタ３０Ａ、３０Ｂの初期値は従来同様に0x10000とするが、従来では第２シンボル以降Ａレジスタ値が該初期値となることはありえないが、本実施例では第１シンボルから以降のシンボルの処理時もＳＷＴＣＨ１２値が１となる限り該初期値のままとり続けることになるが、符号化および復号で再現性のある処理であるため復号可能性を保証できる。ただし、符号化および復号の際にＡレジスタ３０Ａ、３０Ｂの初期値を併せて変更すれば、第１シンボルも含めて0x10000となることはなくなる。このとき、変更値を0xFFFFとすることにより初期値変更による符号化性能の低下（符号長ロス）を最も小さく抑えることができる。第１シンボルで分割される２つの部分領域とも0x7FFF.8（16進小数1桁）となっていずれも0x8000未満となるため正規化が必要となるが、上記処理フローに従えば正規化処理に相当する拡大を先に行うため有効区間の値は0xFFFFのままで処理されることになる。
【００６２】
以上のように、本実施の形態においては、上述の実施の形態１と同様の効果が得られるとともに、さらに、テーブルで記憶する特定値の一つを１／２とし、該当シンボルに対して上記出現確率の推定対象シンボル値の更新を伴う一連の演算処理操作を非該当シンボルの演算処理操作から独立させて構成するようにしたので、冗長性のない演算処理が可能となる。
【００６３】
また、本実施の形態においては、該当シンボルに適用される符号化において、上記補正器は上記第１および第２の部分区間を上記有効区間と等値とみなして補正し、上記有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化処理と、上記正規化手段による符号更新後、出力可能な符号を出力する符号出力処理とを行うので、符号演算を正規化に相当する拡大処理後に行うことにより、有効区間の表現精度を最大に保つことができる。
【００６４】
なお、本実施の形態においては、該当シンボルに適用される復号において、上記補正器は上記第１および第２の部分区間を上記有効区間と等値とみなして補正し、上記有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化処理と、正規化手段による符号拡大後または拡大前に、以後新たに演算部に取り込まれる符号の入力が必要であれば予め準備して入力する符号入力手段を備えて、符号演算を正規化に相当する拡大処理後に行うことにより、有効区間の表現精度を最大に保つことができる。
【００６５】
実施の形態３．
本実施の形態では、ＳＷＴＣＨテーブル１２の用途を拡張し、状態の確率が１／２のべき乗であることを示すフラグとして、その指数ｎを設定するものとする。一例を図１２に示す。ここでは、確率１／２以外に１／４の状態のＳＷＴＣＨ値に２を設定している。このように設定したテーブルを実施例１に示した符号化および復号の処理フローに適用することにより、ステップＳ１２０'、Ｓ１３０'、Ｓ２２０'においてＳＷＴＣＨ１２値が１のときＬＳＺはＡレジスタ３１値をｎ桁だけ右シフトした値が設定され、より誤差の少ない部分区間の割当てが可能となり、符号化性能が向上する。
【００６６】
上記指数ｎは任意であり、定数テーブルを再設定して状態数を増減し、それに伴って対応する確率に１／２のべき乗の状態数が増減しても、同じ確率の状態が複数存在しても構わない。また、確率が１／２のべき乗の状態の一部に確率推定誤差を許容する場合には上記ＳＷＩＴＣＨ１２値の設定を行わなくても構わない。
【００６７】
以上のように、本実施の形態においては、テーブルが記憶する特定値は１／２のべき乗で表現できる確率値であるようにしたので、出現確率が１／２のべき乗となるシンボルを他のシンボルと区別できるため、近似値を適用せずに、より誤差を少なく補正することができる。
【００６８】
なお、上記特定値を１／２のべき乗で表現した場合の２進小数指数部の正の整数値で記憶するようにしてもよく、これにより、記憶容量の節約が可能になるとともに、有効区間を上記正整数桁だけシフト処理で縮小した値を上記第１の部分区間の補正値にするため、補正値をシフト処理で容易に算出することが可能となる。
【００６９】
また、区間幅の更新の際に有効区間を正の整数値の桁だけシフト処理で縮小した値を上記第１の部分区間の補正値にするようにしてもよく、この場合には、補正値を有効区間幅からシフト処理で容易に算出することが可能になり、処理の簡易化及び高速化を図ることができる。
【００７０】
実施の形態４．
本実施の形態は、上記実施の形態２に対して、実施の形態３と同様に１／２のべき乗の確率に対してその指数部ｎを設定したＳＷＴＣＨテーブル１２を適用する場合について説明する。本実施の形態において、図２３のＥＮＣＯＤＥ処理フロー、図２６のＲＥＮＯＲＭＥ処理フロー、図９のＤＥＣＯＤＥ処理フロー、図１０のＬＰＳ＿ＥＸＣＨＡＮＧＥ処理フロー、図１１のＭＰＳ＿ＥＸＣＨＡＮＧＥ処理フロー、図３０のＲＥＮＯＲＭＤ処理フローは変更を加えず適用するものとする。
【００７１】
図１３は、ＬＰＳを符号化するＣＯＤＥＬＰＳ処理フローであり、図６のステップＳ１２０を図３のステップＳ１２０'に変更したものである。
【００７２】
図１４は、ＭＰＳを符号化するＣＯＤＥＭＰＳ処理フローであり、図７のステップＳ１３０を図４のステップＳ１３０'に変更したものである。
【００７３】
図１５は、復号対象画素を復号するＤＥＣＯＤＥ処理フローであり、図８のステップＳ２２０を図５のステップＳ２２０'に変更したものである。
【００７４】
以上のように、この発明は、学習しながら情報源シンボルの出現確率を推定し、上記推定出現確率の近似値を適用する第１の部分区間と残りの第２の部分区間に数直線上の有効区間を分割し、出現したシンボルに対応した部分区間を新たな有効区間とする算術符号を適用した符号化装置であって、推定出現確率が特定値であることを記憶する記憶手段と、記憶手段の特定値を参照して推定出現確率が特定値であることを判定する判定手段と、推定出現確率が上記特定値であることが判定されたときに、第１及び第２の部分区間の割当てを補正する補正手段とを備えた符号化装置であるため、推定出現確率として特定値をとるシンボルに対して部分区間の割当てを補正するので符号化性能が向上するという効果がある。
【００７５】
また、記憶手段が記憶する特定値の一つを１／２とし、該当シンボルに対して推定出現確率の推定対象シンボル値の更新を伴う一連の演算処理操作を非該当シンボルの演算処理操作から独立させて構成するため、出現確率の推定対象シンボル値の更新を伴う確率１／２をとるシンボルの符号化および復号の演算処理を通常の演算処理から独立させるので、冗長性のない演算処理が可能となる。
【００７６】
また、該当シンボルに適用される符号化において、補正手段は上記第１および第２の部分区間を上記有効区間と等値とみなして補正し、有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化手段と、正規化手段による符号更新後、出力可能な符号を出力する符号出力手段とを備えているので、符号演算を正規化に相当する拡大処理後に行うため、有効区間の表現精度を最大に保つことが可能となる。
【００７７】
また、記憶手段が記憶する上記特定値は１／２のべき乗で表現できる確率値であるので、出現確率が１／２のべき乗となるシンボルを他のシンボルと区別できるため、近似値を適用せずにより誤差を少なく補正することが可能となる。
【００７８】
また、記憶手段は上記特定値を上記１／２のべき乗で表現した場合の２進小数指数部の正の整数値で記憶し、判定手段は上記正整数値に基づいて判定を行うので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、記憶容量を節約することが可能となる。
【００７９】
また、記憶手段が記憶した正整数値に対して、補正手段は上記有効区間を正整数桁だけシフト処理で縮小した値を第１の部分区間の補正値にするので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、補正値を有効区間幅からシフト処理で容易に算出することが可能となる。
【００８０】
また、この発明は、学習しながら情報源シンボルの出現確率を推定し、推定出現確率の近似値を適用する第１の部分区間と残りの第２の部分区間に数直線上の有効区間を分割し、出現したシンボルに対応した部分区間を新たな有効区間とする算術符号を適用した復号装置であって、推定出現確率が特定値であることを記憶する記憶手段と、記憶手段の特定値を参照して推定出現確率が特定値であることを判定する判定手段と、推定出現確率が特定値であることが判定されたときに、第１及び第２の部分区間の割当てを補正する補正手段とを備えた復号装置であるため、推定出現確率として特定値をとるシンボルに対して部分区間の割当てを補正するので符号化性能が向上するという効果がある。
【００８１】
また、記憶手段が記憶する特定値の一つを１／２とし、該当シンボルに対して推定出現確率の推定対象シンボル値の更新を伴う一連の演算処理操作を非該当シンボルの演算処理操作から独立させて構成するため、出現確率の推定対象シンボル値の更新を伴う確率１／２をとるシンボルの符号化および復号の演算処理を通常の演算処理から独立させるので、冗長性のない演算処理が可能となる。
【００８２】
また、該当シンボルに適用される復号において、補正手段は第１および第２の部分区間を有効区間と等値とみなして補正し、有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化手段と、正規化手段による符号拡大後に、以後新たに演算部に取り込まれる符号の入力が必要であれば予め準備して入力する符号入力手段とを備えているので、符号演算を正規化に相当する拡大処理後に行うため、有効区間の表現精度を最大に保つことが可能となる。
【００８３】
また、該当シンボルに適用される復号において、補正手段は上記第１および第２の部分区間を上記有効区間と等値とみなして補正し、有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化手段と、正規化手段による符号の拡大前に、演算部に取り込まれる符号の入力が必要であれば入力する符号入力手段とを備えているので、符号演算を正規化に相当する拡大処理後に行うため、有効区間の表現精度を最大に保つことが可能となる。
【００８４】
また、記憶手段が記憶する特定値は１／２のべき乗で表現できる確率値であるので、出現確率が１／２のべき乗となるシンボルを他のシンボルと区別できるため、近似値を適用せずにより誤差を少なく補正することが可能となる。
【００８５】
また、記憶手段は特定値を１／２のべき乗で表現した場合の２進小数指数部の正の整数値で記憶し、判定手段は正整数値に基づいて判定を行うので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、記憶容量を節約することが可能となる。
【００８６】
また、記憶手段が記憶した正整数値に対して、補正手段は有効区間を正整数桁だけシフト処理で縮小した値を上記第１の部分区間の補正値にするので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、補正値を有効区間幅からシフト処理で容易に算出することが可能となる。
【００８７】
また、この発明は、学習しながら情報源シンボルの出現確率を推定し、推定出現確率の近似値を適用する第１の部分区間と残りの第２の部分区間に数直線上の有効区間を分割し、出現したシンボルに対応した部分区間を新たな上記有効区間とする算術符号を適用した符号化方法であって、推定出現確率が特定値であることを記憶する記憶ステップと、記憶ステップにおいて記憶された特定値を参照して推定出現確率が特定値であることを判定する判定ステップと、推定出現確率が特定値であることが判定されたときに、第１及び第２の部分区間の割当てを補正する補正ステップとを備えた符号化方法であるため、推定出現確率として特定値をとるシンボルに対して部分区間の割当てを補正するので符号化性能が向上するという効果がある。
【００８８】
また、記憶ステップにおいて記憶された特定値の一つを１／２とし、該当シンボルに対して推定出現確率の推定対象シンボル値の更新を伴う一連の演算処理操作を非該当シンボルの演算処理操作から独立させて構成するため、出現確率の推定対象シンボル値の更新を伴う確率１／２をとるシンボルの符号化および復号の演算処理を通常の演算処理から独立させるので、冗長性のない演算処理が可能となる。
【００８９】
また、該当シンボルに適用される符号化において、補正ステップは第１および第２の部分区間を有効区間と等値とみなして補正し、有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化ステップと、正規化ステップによる符号更新後、出力可能な符号を出力する符号出力ステップとを備えているので、符号演算を正規化に相当する拡大処理後に行うため、有効区間の表現精度を最大に保つことが可能となる。
【００９０】
また、記憶ステップにおいて記憶される上記特定値は１／２のべき乗で表現できる確率値であるので、出現確率が１／２のべき乗となるシンボルを他のシンボルと区別できるため、近似値を適用せずにより誤差を少なく補正することが可能となる。
【００９１】
また、記憶ステップは特定値を１／２のべき乗で表現した場合の２進小数指数部の正の整数値で記憶し、判定ステップは正整数値に基づいて判定を行うので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、記憶容量を節約することが可能となる。
【００９２】
また、記憶ステップにおいて記憶された正整数値に対して、補正ステップは有効区間を正整数桁だけシフト処理で縮小した値を第１の部分区間の補正値にするので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、補正値を有効区間幅からシフト処理で容易に算出することが可能となる。
【００９３】
また、この発明は、学習しながら情報源シンボルの出現確率を推定し、推定出現確率の近似値を適用する第１の部分区間と残りの第２の部分区間に数直線上の有効区間を分割し、出現したシンボルに対応した部分区間を新たな有効区間とする算術符号を適用した復号方法であって、推定出現確率が特定値であることを記憶する記憶ステップと、記憶ステップにおいて記憶された特定値を参照して推定出現確率が特定値であることを判定する判定ステップと、推定出現確率が特定値であることが判定されたときに、第１及び第２の部分区間の割当てを補正する補正ステップとを備えた復号方法であるため、推定出現確率として特定値をとるシンボルに対して部分区間の割当てを補正するので符号化性能が向上するという効果がある。
【００９４】
また、記憶ステップにおいて記憶される特定値の一つを１／２とし、該当シンボルに対して推定出現確率の推定対象シンボル値の更新を伴う一連の演算処理操作を非該当シンボルの演算処理操作から独立させて構成するため、出現確率の推定対象シンボル値の更新を伴う確率１／２をとるシンボルの符号化および復号の演算処理を通常の演算処理から独立させるので、冗長性のない演算処理が可能となる。
【００９５】
また、該当シンボルに適用される復号において、補正ステップは第１および第２の部分区間を有効区間と等値とみなして補正し、有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化ステップと、正規化ステップによる符号拡大後に、以後新たに演算部に取り込まれる符号の入力が必要であれば予め準備して入力する符号入力ステップとを備えているので、符号演算を正規化に相当する拡大処理後に行うため、有効区間の表現精度を最大に保つことが可能となる。
【００９６】
また、該当シンボルに適用される復号において、補正ステップは第１および第２の部分区間を上記有効区間と等値とみなして補正し、有効区間は変更せず、符号のみ１桁のシフト処理あるいは２倍の乗算で拡大した後、符号値を演算する手順によって有効区間の表現精度を最大に保つ正規化ステップと、正規化ステップによる符号の拡大前に、演算部に取り込まれる符号の入力が必要であれば入力する符号入力ステップとを備えているので、符号演算を正規化に相当する拡大処理後に行うため、有効区間の表現精度を最大に保つことが可能となる。
【００９７】
また、記憶ステップにおいて記憶される特定値は１／２のべき乗で表現できる確率値であるので、出現確率が１／２のべき乗となるシンボルを他のシンボルと区別できるため、近似値を適用せずにより誤差を少なく補正することが可能となる。
【００９８】
また、記憶ステップは特定値を１／２のべき乗で表現した場合の２進小数指数部の正の整数値で記憶し、判定ステップは上記正整数値に基づいて判定を行うので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、記憶容量を節約することが可能となる。
【００９９】
また、記憶ステップにおいて記憶された正整数値に対して、補正ステップは有効区間を正整数桁だけシフト処理で縮小した値を第１の部分区間の補正値にするので、出現確率が１／２のべき乗となるシンボルを２進小数指数部の正の整数値で記憶するため、補正値を有効区間幅からシフト処理で容易に算出することが可能となる。
【図面の簡単な説明】
【０１００】
【図１】この発明の符号器（符号化装置）の構成を示したブロック図である。
【図２】この発明の復号器（復号装置）の構成を示したブロック図である。
【図３】この発明の実施の形態１のＣＯＤＥＬＰＳ処理フローを示す流れ図である。
【図４】この発明の実施の形態１のＣＯＤＥＭＰＳ処理フローを示す流れ図である。
【図５】この発明の実施の形態１のＤＥＣＯＤＥ処理フローを示す流れ図である。
【図６】この発明の実施の形態２のＣＯＤＥＬＰＳ処理フローを示す流れ図である。
【図７】この発明の実施の形態２のＣＯＤＥＭＰＳ処理フローを示す流れ図である。
【図８】この発明の実施の形態２のＤＥＣＯＤＥ処理フローを示す流れ図である。
【図９】この発明の実施の形態２のＤＥＣＯＤＥ処理フローにおいて図８に続く部分を示す流れ図である。
【図１０】この発明の実施の形態２のＬＰＳ＿ＥＸＣＨＡＮＧＥ処理フローを示す流れ図である。
【図１１】この発明の実施の形態２のＭＰＳ＿ＥＸＣＨＡＮＧＥ処理フローを示す流れ図である。
【図１２】この発明の実施の形態３の定数テーブル値を示す説明図である。
【図１３】この発明の実施の形態４のＣＯＤＥＬＰＳ処理フローを示す流れ図である。
【図１４】この発明の実施の形態４のＣＯＤＥＭＰＳ処理フローを示す流れ図である。
【図１５】この発明の実施の形態４のＤＥＣＯＤＥ処理フローを示す流れ図である。
【図１６】２値算術符号化の概念を示す説明図である。
【図１７】減算型算術符号化と正規化処理の概念を示す説明図である。
【図１８】部分区間の分割補正を示す説明図である。
【図１９】従来の符号器の概略構成を示すブロック図である。
【図２０】従来の復号器の概略構成を示すブロック図である。
【図２１】従来の定数テーブル値を示す説明図である。
【図２２】従来の演算用レジスタ構成を示す説明図である。
【図２３】従来のＥＮＣＯＤＥ処理フローを示す流れ図である。
【図２４】従来のＣＯＤＥＬＰＳ処理フローを示す流れ図である。
【図２５】従来のＣＯＤＥＭＰＳ処理フローを示す流れ図である。
【図２６】従来のＲＥＮＯＲＭＥ処理フローを示す流れ図である。
【図２７】従来のＤＥＣＯＤＥ処理フローを示す流れ図である。
【図２８】従来のＬＰＳ＿ＥＸＣＨＡＮＧＥ処理フローを示す流れ図である。
【図２９】従来のＭＰＳ＿ＥＸＣＨＡＮＧＥ処理フローを示す流れ図である。
【図３０】従来のＲＥＮＯＲＭＤ処理フローを示す流れ図である。
【符号の説明】
【０１０１】
１Ａ  ＱＭ符号器、１Ｂ  ＱＭ復号器、２  コンテクスト、３  画素、４  符号、５Ａ、５Ｂ  画像メモリ、６  画像、７  予測値テーブルＭＰＳおよび変数ＭＰＳ、８  ステートテーブルＳＴおよび変数ＳＴ、９  ＬＰＳ区間幅テーブルＬＳＺ、１０  ＭＰＳ状態遷移先テーブルＮＭＰＳ、１１  ＬＰＳ状態遷移先テーブルＮＬＰＳ、１２  予測値反転判定テーブルＳＷＴＣＨ、１３Ａ  算術符号器、１３Ｂ  算術復号器、１４  シンボル、１５Ａ  画素シンボル変換器、１５Ｂ  シンボル画素変換器、１６  反転器、１７  セレクタ、３０Ａ  符号化レジスタＣ、３０Ｂ  復号レジスタＣ、３１  区間幅レジスタＡ、３２  Ｃｘレジスタ、３３  Ｃｂレジスタ、３４  Ｃｃレジスタ、３５  ＣＬＯＷレジスタ、３６  Ｃｂレジスタ、３７  ＣＨＩＧＨレジスタ、３８  Ｃｘレジスタ、５０  ＣＴカウンタ。
【図１】
2006109486.tif 000003
【図２】
2006109486.tif 000004
【図３】
2006109486.tif 000005
【図４】
2006109486.tif 000006
【図５】
2006109486.tif 000007
【図６】
2006109486.tif 000008
【図７】
2006109486.tif 000009
【図８】
2006109486.tif 000010
【図９】
2006109486.tif 000011
【図１０】
2006109486.tif 000012
【図１１】
2006109486.tif 000013
【図１２】
2006109486.tif 000014
【図１３】
2006109486.tif 000015
【図１４】
2006109486.tif 000016
【図１５】
2006109486.tif 000017
【図１６】
2006109486.tif 000018
【図１７】
2006109486.tif 000019
【図１８】
2006109486.tif 000020
【図１９】
2006109486.tif 000021
【図２０】
2006109486.tif 000022
【図２１】
2006109486.tif 000023
【図２２】
2006109486.tif 000024
【図２３】
2006109486.tif 000025
【図２４】
2006109486.tif 000026
【図２５】
2006109486.tif 000027
【図２６】
2006109486.tif 000028
【図２７】
2006109486.tif 000029
【図２８】
2006109486.tif 000030
【図２９】
2006109486.tif 000031
【図３０】
2006109486.tif 000032