(57)【要約】  情報源をエントロピー符号化した符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、符号系列終端に付加ビットとして設定可能なビット数を算出する付加ビット数算出手段１０７と、当該ビット数の付加ビットを符号系列終端に設定する付加ビット符号化手段１０８とを備える。
2008129883.tif 000002
【特許請求の範囲】
【請求項１】
情報源シンボルをエントロピー符号化して符号系列を生成する符号化装置において、
前記符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、前記符号系列終端に付加ビットとして設定可能なビット数を算出する付加ビット数算出手段と、
当該ビット数の付加ビットを前記符号系列終端に設定する付加ビット符号化手段とを備えたことを特徴とする符号化装置。
【請求項２】
情報源シンボルを算術符号化する算術演算手段と、
前記算術演算手段により符号化された情報源シンボルに対応する数直線上の有効区間を示す座標値が格納される符号化レジスタと、
数直線上の有効区間を情報源シンボルの出現確率に応じて分割した区間幅を規定する数値が格納される区間幅レジスタと、
前記区間幅が所定の幅より小さくなると、前記区間幅レジスタと前記符号化レジスタの値を同一倍率で所定の値より大きくなるまで拡大する正規化処理の回数を計数するＣＴカウンタとを備え、
付加ビット数算出手段は、前記算術演算手段による情報源シンボルの算術符号化の終了時点における前記符号化レジスタの値、前記区間幅レジスタの値、前記ＣＴカウンタにより計数された正規化の回数、及び算術符号化の終了直前に前記符号化レジスタから出力された符号に基づいて、符号系列終端に付加ビットとして設定可能なビット数を算出することを特徴とする請求項１記載の符号化装置。
【請求項３】
算術演算手段は、情報源シンボルを２値算術符号化し、
付加ビット符号化手段は、前記算術演算手段に対して、前記情報源シンボルの２値算術符号化の終了時点における有効区間を所定の値以上の値とし、優勢シンボルの値を０又は１の固定値として、前記優勢シンボル及び劣勢シンボルに対する区間幅を共に前記全区間の１／２の固定値を設定して付加ビットを符号化することを特徴とする請求項２記載の符号化装置。
【請求項４】
付加ビット符号化手段は、付加ビット系列を特定のビット数だけビットシフトした値を符号化レジスタの値に加算し、当該符号化レジスタにおいて、ＣＴカウンタにより符号化の過程で計数された正規化の回数から定まる最上位のバイトから特定の位置のビットを含むバイトまでを符号とすることを特徴とする請求項２記載の符号化装置。
【請求項５】
付加ビット数算出手段は、付加ビットを設定しない場合の符号系列の符号長と同じ符号長となるように付加ビット数を設定することを特徴とする請求項３または請求項４記載の符号化装置。
【請求項６】
情報源シンボルがエントロピー符号化された符号系列を復号する復号装置において、
前記符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、前記符号系列終端から付加ビットとして設定されたビット数を算出する付加ビット数算出手段と、
当該ビット数の付加ビットを復号する付加ビット復号手段とを備えたことを特徴とする復号装置。
【請求項７】
情報源シンボルが算術符号化された符号系列を算術復号する算術演算手段と、
前記算術演算手段により復号された情報源シンボルに対応させた有効区間を示す座標値からその区間内の座標である符号へのオフセット値が格納される復号レジスタと、
数直線上の有効区間を情報源シンボルの出現確率に応じて分割した区間幅を規定する数値が格納される区間幅レジスタと、
前記区間幅が所定の幅より小さくなると、前記区間幅レジスタと前記復号レジスタの値を同一倍率で所定の値より大きくなるまで拡大する正規化処理の回数を計数するＣＴカウンタとを備え、
付加ビット数算出手段は、前記算術演算手段による情報源シンボルの算術復号の終了時点における正規化の回数、及び算術復号の終了直前に前記復号レジスタに入力された符号に基づいて、前記符号系列終端に設定された付加ビットのビット数を算出することを特徴とする請求項６記載の復号装置。
【請求項８】
算術演算手段は、情報源シンボルが２値算術符号化された符号系列を算術復号し、
付加ビット復号手段は、前記算術演算手段に対して、前記情報源シンボルの２値算術符号化の終了時点における有効区間を所定の値以上の値とし、優勢シンボルの値を０又は１の固定値として、前記優勢シンボル及び劣勢シンボルに対する区間幅を共に前記全区間の１／２の固定値を設定して付加ビットを復号することを特徴とする請求項７記載の復号装置。
【請求項９】
情報源シンボルをエントロピー符号化して符号系列を生成する符号化装置としてコンピュータを機能させるプログラムにおいて、
前記符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、前記符号系列終端に付加ビットとして設定可能なビット数を算出する付加ビット数算出手段、
当該ビット数の付加ビットを前記符号系列終端に設定する付加ビット符号化手段として前記コンピュータを機能させるプログラム。
【請求項１０】
情報源シンボルがエントロピー符号化された符号系列を復号する復号装置としてコンピュータを機能させるプログラムにおいて、
前記符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、前記符号系列終端から付加ビットとして設定されたビット数を算出する付加ビット数算出手段、
当該ビット数の付加ビットを復号する付加ビット復号手段としてコンピュータを機能させるプログラム。
【請求項１１】
情報源シンボルがエントロピー符号化された符号系列に付加ビットを埋め込む符号変換装置において、
前記符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、前記符号系列終端に付加ビットとして埋め込むビット数を算出する付加ビット数算出手段と、
当該ビット数の付加ビットが前記符号系列に含まれるように前記符号系列を変換する付加ビット符号化手段とを備えたことを特徴とする符号変換装置。
【請求項１２】
情報源シンボルを算術符号化することにより生成される符号系列を算術復号する算術演算手段と、
前記算術演算手段により復号された情報源シンボルに対応させた有効区間を示す座標値からその区間内の座標である符号へのオフセット値が格納される復号レジスタと、
数直線上の有効区間を情報源シンボルの出現確率に応じて分割した区間幅を規定する数値が格納される区間幅レジスタと、
前記区間幅が所定の値より小さくなると、前記区間幅レジスタと前記復号レジスタの値を同一倍率で所定の値より大きくなるまで拡大する正規化処理の回数を計数する復号器ＣＴカウンタと、
前記符号系列を生成した符号器における符号系列生成終了時点での状態を算出する符号器情報算出手段とを備え、
付加ビット数算出手段は、前記符号系列を生成した符号器における符号系列生成終了時点での符号器の状態に基づいて、符号系列終端に設定可能な付加ビットのビット数を算出することを特徴とする請求項１１記載の符号変換装置。
【請求項１３】
情報源シンボルに対応する数直線上の有効区間を示す座標値が格納される符号化レジスタと、
前記区間幅が所定の値より小さくなると、前記区間幅レジスタと前記符号化レジスタの値を同一倍率で所定の値より大きくなるまで拡大する正規化処理の回数を計数する符号器ＣＴカウンタと、
符号系列を生成した符号器における符号系列生成終了時点での前記符号化レジスタ及び前記符号器ＣＴカウンタの値を算出する符号器情報算出手段とを備え、
算術演算手段は、前記符号器情報算出手段が算出した前記符号化レジスタ及び前記符号器ＣＴカウンタの値を使って、前記付加ビット数の付加ビットを算術符号化して符号を生成し、生成された符号により前記符号系列内の対応するバイトを変更することを特徴とする請求項１２記載の符号変換装置。
【請求項１４】
算術演算手段における付加ビットの符号化において、情報源シンボルの２値算術符号化の終了時点における有効区間を所定の値以上の値とし、優勢シンボルの値を０又は１の固定値として、前記優勢シンボル及び劣勢シンボルに対する区間幅を共に前記有効区間設定値の１／２の値に設定して、付加ビットを符号化することを特徴とする請求項１３記載の符号変換装置。
【請求項１５】
付加ビット数算出手段は、符号系列とバイト長が変わらない範囲の付加ビット数を設定することを特徴とする請求項１４記載の符号変換装置。
【請求項１６】
算術演算手段における付加ビットの符号化において、付加ビット系列を特定のビット数だけビットシフトした値を符号化レジスタの値に加算し、当該符号化レジスタにおいて、符号器ＣＴカウンタにより符号化の過程で計数された正規化の回数から定まる最上位のバイトから特定の位置のビットを含むバイトまでを符号とすることを特徴とする請求項１３記載の符号変換装置。
【請求項１７】
付加ビット数算出手段は、符号系列とバイト長が変わらない範囲の付加ビット数を設定することを特徴とする請求項１６記載の符号変換装置。
【請求項１８】
情報源シンボルを算術符号化することにより生成される符号系列を算術復号する算術演算手段と、
前記算術演算手段により復号された情報源シンボルに対応させた有効区間を示す座標値からその区間内の座標である符号へのオフセット値が格納される復号レジスタと、
数直線上の有効区間を情報源シンボルの出現確率に応じて分割した区間幅を規定する数値が格納される区間幅レジスタと、
前記区間幅が所定の値より小さくなると、前記区間幅レジスタと前記復号レジスタの値を同一倍率で所定の値より大きくなるまで拡大する正規化処理の回数を計数する復号器ＣＴカウンタと、
前記符号系列を生成した符号器における符号系列生成終了時点での状態を算出する符号器情報算出手段とを備え、
付加ビット数算出手段は、前記符号系列を生成した符号器における符号系列生成終了時点での符号器の状態に基づいて、符号系列終端に設定された付加ビットのビット数を算出することを特徴とする請求項６記載の復号装置。
【請求項１９】
算術演算手段における付加ビットの復号において、情報源シンボルの２値算術復号の終了時点における有効区間を所定の値以上の値とし、優勢シンボルの値を０又は１の固定値として、前記優勢シンボル及び劣勢シンボルに対する区間幅を共に上記有効区間設定値の１／２の値に設定して、付加ビットを復号することを特徴とする請求項１８記載の復号装置。
【請求項２０】
情報源シンボルがエントロピー符号化された符号系列に付加ビットを埋め込む符号変換装置としてコンピュータを機能させるプログラムにおいて、
前記符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、前記符号系列終端に付加ビットとして埋め込むビット数を算出する付加ビット数算出手段、
当該ビット数の付加ビットが前記符号系列に含まれるように前記符号系列を変換する付加ビット符号化手段として前記コンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、エントロピー符号系列に付加ビットを埋め込む符号化装置、復号装置、符号変換装置及びこれら装置としてコンピュータを機能させるプログラムに関するものである。
【背景技術】
【０００２】
算術符号化は、情報源シンボルの生起確率に応じた効率的な符号化が実現可能な方法として広く利用されている。画像符号化方式としては、２値算術符号化方式ＱＭコーダが標準画像圧縮方式であるＪＰＥＧ（Joint Photographic Experts Group）及びＪＢＩＧ（Joint Bi-level Image experts Group）に採用されており、２値算術符号化方式ＭＱコーダがＪＰＥＧ２０００及びＪＢＩＧ２に採用されている。【０００３】
これらの２値算術符号化では、０．０以上１．０未満の数直線上の２進小数座標値が符号となる。この処理過程において、上記数直線上の範囲を有効区間幅Ａとして２値シンボルの出現確率に比例して、ＭＰＳ（More Probable Symbol）及びＬＰＳ（Less Probable Symbol）に分割し、実際に出現したシンボルに対応する部分区間を新たな有効区間として分割を繰り返す。ここで、ＭＰＳとは、出現確率がより高いデータ値が出現したことを示す優勢シンボルであり、ＬＰＳとは、出現確率がより低いデータ値が出現したことを示す劣勢シンボルである。【０００４】
最終シンボルで更新された有効区間を示す際に必要な精度の座標値が符号として出力される。処理中は、有効区間の下界値を計算し、上界値と下界値の差である有効区間幅とともに更新される。最終的な符号は、座標末尾に続く１を切り捨てた有効区間内で有効桁数が最小の座標値を選択することもできる。【０００５】
算術符号化では符号演算の処理量低減のため、減算型算術符号化が広く用いられる。減算型算術符号化では、シンボルの出現確率に基づいて予め用意されたテーブルからＬＰＳに割当てられる部分区間ＬＳＺの近似値が選択される。ここで、有効区間が１／２を下回ると２のべき乗倍して１／２以上の有効区間幅になるように拡大する正規化処理を行う。これにより、計算時の小数部の桁数が一定に保たれる。【０００６】
なお、ＭＱコーダの符号化及び復号処理の詳細については非特許文献１に記載されているので省略する。ここでは、符号化の最後に実行する符号化レジスタの終端処理（以下、フラッシュと呼ぶ）について説明する。上述したように、算術符号化では、最終符号化シンボルにより決定される有効区間幅Ａを示すために必要な精度の２進小数を符号として伝送する。この符号としては、ＭＱ符号化器における符号化レジスタの最下位までの全ビットを伝送する必要はない。【０００７】
ＭＱコーダでは、復号時に復号する符号が無くなった場合、値０ｘＦＦ（０ｘは１６進数を示す）を符号として補填する規則になっている。この場合、符号化レジスタの最終符号化シンボルによる演算結果のうち、図３の符号化レジスタの上位ビットから１５ビット目を含むバイトを符号として出力すれば、正しい復号が保証されることが知られている。【０００８】
非特許文献１に記載されるフラッシュ処理を説明する。先ず、最終符号化シンボルによる算術演算後の有効区間幅をＡ、符号化レジスタ値をＣとした場合、中間値ＴＥＭＰＣ＝Ｃ＋Ａ、Ｃ＝Ｃ  ＯＲ  ０ｘＦＦＦＦ（ＯＲはビット和を表す）を実行する。次に、符号化レジスタ値ＣがＴＥＭＰＣ以上であるか否かを判定する。このとき、符号化レジスタの値ＣがＴＥＭＰＣ未満であれば、中間値ＴＥＭＰＣをそのまま最終的な符号とする。また、符号化レジスタ値ＣがＴＥＭＰＣ以上であれば、符号化レジスタ値Ｃから０ｘ８０００を引いた値が最終的な符号となる。【０００９】
この処理の後、符号化レジスタの上位から１５ビット目を含むバイトまでを出力する。但し、ＪＰＥＧ２０００では、符号の最後を値０ｘＦＦのバイトとすることが禁止されているので、最終バイトが０ｘＦＦとなる場合には最終バイトが切り捨てられる。前回符号を出力してからの正規化回数ＣＴによるが、１バイトあるいは２バイトの符号が符号化レジスタから出力される。【００１０】
また、ＪＰＥＧ２０００には、エラー耐性を高めるためにセグメンテーションシンボルとして、２値シンボルを符号化する過程で、ある周期毎に特定のビット列（１０１０）を余分に符号化する機能がある（非特許文献１参照）。復号処理において、この特定のビット列が正しく復号されているかを検査することで伝送エラーの有無が推定される。【００１１】
【非特許文献１】ITU-T Rec.T.800 | ISO/IEC 15444-1, Information technology-JPEG 2000 image coding system: Core coding system.http://www.jpeg.org/jpeg2000/index.html
【００１２】
従来の符号化装置では、上述したように符号化対象の情報源シンボルに対して付加ビットを追加する場合、符号長が増加する可能性があり、また復号側では受信した符号から何ビットの付加ビットが符号化されているかを判別できないという課題があった。【００１３】
この発明は、上記のような課題を解決するためになされたもので、エントロピー符号化系列の符号長を増加させずに付加ビットを埋め込むことができる符号化装置、該符号系列を復号する復号装置及びこれら装置としてコンピュータを機能させるプログラムを得ることを目的とする。
【発明の開示】
【００１４】
この発明に係る符号化装置は、情報源シンボルをエントロピー符号化して符号系列を生成する符号化装置において、符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、符号系列終端に付加ビットとして設定可能なビット数を算出する付加ビット数算出手段と、当該ビット数の付加ビットを符号系列終端に設定する付加ビット符号化手段とを備えるものである。
【００１５】
このことによって、符号系列の符号長を増加させずに付加ビットを埋め込むことができるという効果がある。
【図面の簡単な説明】
【００１６】
【図１】この発明の実施の形態１による符号化装置の構成を示すブロック図である。
【図２】実施の形態１による復号装置の構成を示すブロック図である。
【図３】符号化レジスタの構成を示す図である。
【図４】符号化レジスタの構成を示す図である。
【図５】符号化レジスタの構成を示す図である。
【図６】付加ビット数の決定における場合分けを示す図である。
【図７】付加ビット数の決定における場合分けを示す図である。
【図８】付加ビット数の決定における場合分けを示す図である。
【図９】図１中の符号化装置による付加ビット数の算出処理を示すフローチャートである。
【図１０】図２中の復号装置による符号化側ＣＴカウンタ値の算出処理を示すフローチャートである。
【図１１】図２中の復号装置による付加ビット数の算出処理を示すフローチャートである。
【図１２】この発明の実施の形態２による符号変換装置の構成を示すブロック図である。
【図１３】実施の形態２による復号装置の構成を示すブロック図である。
【図１４】実施の形態２による符号化レジスタと復号レジスタの構成を示す図である。
【図１５】実施の形態２による符号器情報の算出処理を示すフローチャートである。
【図１６】実施の形態２による符号器情報の算出処理を示すフローチャートである。
【図１７】実施の形態２による付加ビット数の算出処理を示すフローチャートである。
【図１８】算術符号系列の一例を示す図である。
【発明を実施するための最良の形態】
【００１７】
以下、この発明をより詳細に説明するために、この発明を実施するための最良の形態について、添付の図面に従って説明する。
実施の形態１．
この実施の形態１では、画像データの符号化に伴って生じる２値シンボル（以下、２値シンボルと呼ぶ）を算術符号化対象とし、画像データ符号化処理の終了直後に２値シンボルとは異なる付加情報である付加ビット（以下、付加ビットと呼ぶ）を符号化してからフラッシュ処理を行って符号を出力する符号化処理及びこの符号に埋め込まれた付加ビットを抽出する復号処理を説明する。なお、実施の形態１では、付加ビットを符号化しても、非特許文献１に記載される算術符号のフラッシュ（以下、推奨フラッシュと呼ぶ）を行った場合（付加ビットの符号化は行わない）と符号長が変わらないことを前提としている。【００１８】
図１は、この発明の実施の形態１による符号化装置の構成を示すブロック図であり、本発明を画像データを算術符号化する画像符号化装置に適用した場合を示している。図１において、コンテクスト作成手段１０１は、符号化対象となる画像データの２値シンボルの出現確率を推定するための条件付けをするコンテクストＣＸを決定する。確率推定手段１０２は、コンテクストＣＸから符号化対象となる２値シンボルの予測値と出現確率を示すパラメータＬＳＺとを算出する。【００１９】
算術演算手段１０３は、予測値が符号化対象の２値シンボルと一致したか否か、つまり符号化対象の２値シンボルがＭＰＳであるかＬＰＳであるかを示す情報（以降、２値情報（ＭＰＳ／ＬＰＳ）と記す）及び推定確率（ＬＳＺ）に基づいて算術演算を実行し、符号データを出力する。ＣＴカウンタ１０４は、算術演算手段１０３から直前に符号データが出力されてからの正規化回数をカウントして記憶する。【００２０】
符号化レジスタ１０５には、符号化された２値シンボルに対応する有効区間の下界値が格納される。また、符号化レジスタ１０５において、値０ｘＦＦの符号を格納する場合、この符号の直後にビット値０が挿入される。【００２１】
さらに、算術演算手段１０３による符号化演算の過程で発生した符号化レジスタ値の桁上がりは、直前に出力された符号バイトまで伝播される。なお、符号化レジスタ１０５において、直前の符号バイトの値が０ｘＦＦで、桁上がりが発生した場合、値０ｘＦＦの直後に挿入されたビット値０がビット値１になる。これにより、桁上がりが吸収されるので、それ以前の符号バイトまで桁上がりが伝播することはない。【００２２】
区間幅レジスタ１０６には、数直線上の有効区間を２値シンボルの出現確率に応じて分割した区間幅を規定する数値が格納される。また、符号化の過程において、区間幅は、Ａ−ＬＳＺ（上方区間幅）又はＬＳＺ（下方区間幅）に更新される。但し、Ａは符号化の過程における直前の有効区間幅である。【００２３】
付加ビット数算出手段１０７は、２値シンボルの符号化終了時点におけるＣＴカウンタ１０４の値、符号化レジスタ１０５の値、及び直前に出力された符号等の復号側で検出可能な情報を用いて、推奨フラッシュを行った場合と符号長が変わらない範囲で符号化可能なビット数の付加ビットを決定する。【００２４】
付加ビット符号化手段１０８は、付加ビット符号化のために算出した値ΔＣを符号化レジスタ１０５に加算して、符号化した付加ビットを含む符号を生成する。排他的論理和回路１０９は、符号化対象の２値シンボルと確率推定手段１０２から入力した２値シンボルの予測値との排他的論理和から、符号化対象の２値シンボルがＭＰＳであるかＬＰＳであるかを示す２値情報（ＭＰＳ／ＬＰＳ）を求める。【００２５】
上述した、コンテクスト作成手段１０１、確率推定手段１０２、算術演算手段１０３、付加ビット数算出手段１０７及び付加ビット符号化手段１０８は、本発明の趣旨に従う符号化用プログラムをコンピュータに読み込ませてその動作を制御することにより、当該コンピュータ上でソフトウエアとハードウェアが協働した具体的な手段として図１に示す符号化装置を実現することができる。【００２６】
図２は、実施の形態１による復号装置の構成を示すブロック図であり、本発明を符号化画像データを算術復号する画像復号装置に適用した場合を示している。図２において、コンテクスト作成手段２０１は、復号対象となる符号化データの２値シンボルの出現確率を推定するための条件付けをするコンテクストＣＸを決定する。確率推定手段２０２は、コンテクストＣＸから復号対象となる２値シンボルの予測値と出現確率を示すパラメータＬＳＺとを算出する。【００２７】
算術演算手段２０３は、符号データと推定確率から予測値が復号対象の２値シンボルと一致したか否か、つまり復号対象の２値シンボルがＭＰＳであるかＬＰＳであるかを算出する。ＣＴカウンタ２０４は、算術演算手段２０３が直前に符号データを読み込んでからの正規化回数をカウントし記憶する。【００２８】
復号レジスタ２０５には、復号した２値シンボルに対応させた有効区間の下界値からその区間内の座標である符号へのオフセット値が格納される。【００２９】
区間幅レジスタ２０６には、数直線上の有効区間を２値シンボルの出現確率に応じて分割した区間幅を規定する数値が格納される。付加ビット数算出手段２０７は、復号する符号データにおける付加ビットの数を決定する。付加ビット復号手段２０８は、符号系列最後の情報に基づいて付加ビットを復号する。【００３０】
上述した、コンテクスト作成手段２０１、確率推定手段２０２、算術演算手段２０３、付加ビット数算出手段２０７及び付加ビット復号手段２０８は、本発明の趣旨に従う復号用プログラムをコンピュータに読み込ませてその動作を制御することにより、当該コンピュータ上でソフトウエアとハードウェアが協働した具体的な手段として図２に示す復号装置を実現することができる。【００３１】
なお、コンピュータ自体の構成及びその基本的な機能については、本発明の技術分野における技術常識に基づいて当業者が容易に認識できるものであり、本発明の本質に直接関わるものでないので詳細な記載を省略する。【００３２】
次に動作について説明する。
図１に示す実施の形態１による符号化装置では、非特許文献１に記載されるＭＱコーダと同様の処理によって、符号化対象の２値シンボルを符号化する。ＣＴカウンタ、符号化レジスタ、区間幅レジスタの構成も非特許文献１と同一である。このとき、付加ビット数算出手段１０７及び付加ビット符号化手段１０８は動作しない。つまり、付加ビット数算出手段１０７及び付加ビット符号化手段１０８を除いた、コンテクスト作成手段１０１、確率推定手段１０２、算術演算手段１０３、ＣＴカウンタ１０４、符号化レジスタ１０５、区間幅レジスタ１０６及び排他的論理和回路１０９によって、符号化対象の画像データが符号化される。【００３３】
付加ビット数算出手段１０７及び付加ビット符号化手段１０８は、符号化対象の２値シンボルの符号化が終了した後、この時点でのＣＴカウンタ１０４のカウント値、符号化レジスタ１０５の値、及び算術演算手段１０３から直前に出力された符号を参照して、付加ビットのビット数を決定し付加ビットを符号化する。【００３４】
先ず、付加ビット数算出手段１０７及び付加ビット符号化手段１０８によってなされる付加ビット符号化の処理手順について説明する。
（１）符号化する付加ビットのビット数Ｌｅｘｔの算出処理
付加ビット数算出手段１０７は、２値シンボル符号化の終了時点における、ＣＴカウンタ１０４のカウント値、符号化レジスタ１０５の値、直前に出力した符号など、復号側で検出可能な情報を使って、推奨フラッシュと符号長が変わらない範囲で符号化可能な付加ビットのビット数Ｌｅｘｔを決定する。図３〜図５は、符号化レジスタの構成を示す図であり、これらの図を用いて、図６〜図８に示す付加ビット数の決定処理における場合分けを説明する。【００３５】
図３〜図５の例において、符号化レジスタ１０５の１５ビット目と１６ビット目の間に小数点を設定し、小数点位置を境に上位を整数部、下位を小数部とする。また、整数部における１６ビット目から１８ビット目までの３ビットはスペーサビット部Ｃｓ、１９ビット目から２６ビット目までの８ビットがバイト出力部Ｃｂであり、２７ビット目の１ビットは桁上がり判定部Ｃｃである。【００３６】
なお、図３〜図５中の実線で囲んだバイトは、符号として出力される符号バイトを示しており、破線で囲まれた斜字の数値を記載したバイトは、条件によっては出力されないバイトを示している。また、図３〜図５及び図６〜図８の−１で示すバイトは、復号側で読み込まれても符号がないために値０ｘＦＦをとるバイトが補填される符号を表している。つまり、図３〜図５において、破線で囲まれ−１を付したバイトは、出力されないバイトであり、復号側ではＦＦとして補填されるバイトとなる。【００３７】
正規化処理では、符号化の過程において、有効区間幅Ａ及び符号化レジスタ値Ｃの演算の際に小数点以下の有効桁を一定にするため、有効区間幅Ａの値が必ず０．５〜１．０の間に入るよう、有効区間幅Ａと符号化レジスタ値Ｃの小数点位置が同じビット数分下位にずらされる。ＣＴカウンタ１０４によって符号化レジスタ１０５及び区間幅レジスタ１０６のシフト数をカウントし、バイト出力部Ｃｂにおける符号バイト出力は、カウント値が０となったときに行われる。なお、ＣＴカウンタ１０４の初期値、再設定値は８である。【００３８】
また、図３〜図５において、２値シンボル符号化の終了時点におけるＣＴカウンタ１０４のカウント値をＣＴｅｎｃ、算術演算手段１０３から直前に出力された１バイトの符号データをＲ１、ＣＴカウンタ１０４のカウント値によって規定される符号化レジスタ１０５の有効なビットのうち、最初の符号バイトをＲ２、２番目の符号バイトをＲ３とする。また、Ｒ１，Ｒ２，Ｒ３に対応するビット位置の最終的な符号のバイトをそれぞれＢ１，Ｂ２，Ｂ３とする。【００３９】
例えば、図３に示すＲ１≠０ｘＦＦかつＲ２≠０ｘＦＦの条件では、ＣＴカウンタ１０４の値ＣＴｅｎｃが１のとき、符号化レジスタ１０５の１８ビット目から２５ビット目までが符号バイトＲ２、１０ビット目から１７ビット目までが符号バイトＲ３、直前に出力された符号バイトがＲ１となる。但し、Ｒ１＝０ｘＦＥかつ符号化レジスタ１０５からＲ１に桁上がりが生じている場合、つまり図３においてＲ１＝０ｘＦＥかつ符号化レジスタ１０５の２６ビット目が１になっている場合は、図３に示す条件から除外される。【００４０】
また、図４に示すようにＢ１＝０ｘＦＦとなる場合、上述したように符号の直後に１ビットが挿入されるので、符号化レジスタ１０５からは７ビットが出力される。図４の例では、上記条件でＣＴカウンタ１０４の値ＣＴｅｎｃが１の場合、挿入される１ビットと１９ビット目から２５ビット目までがＲ２となる。図５に示すＢ２＝０ｘＦＦとなる条件においても、符号の直後に１ビットが挿入されることから、符号化レジスタ１０５からは７ビットが出力される。図５の例では、上記条件でＣＴカウンタ１０４の値ＣＴｅｎｃが１の場合、１１ビット目から１７ビット目までがＲ３となる。【００４１】
図９は、図１中の符号化装置による付加ビット数の算出処理を示すフローチャートであり、この図及び図６〜８を用いて付加ビット数の算出手順を説明する。なお、図９に示したＲ２’，Ｒ３’は、推奨フラッシュを行った場合のＲ２，Ｒ３に対応するビット列であり、以下のように算出する。【００４２】
画像データの符号化終了時点における、符号化レジスタ１０５の値をＣ、区間幅レジスタ１０６の値をＡとした場合、次の処理を行ってＣ’を算出する。
Ｃ’＝Ｃ  ＯＲ  ０ｘＦＦＦＦ  （ＯＲはビット和を表す）
ｉｆ（Ｃ’≧（Ｃ＋Ａ））  Ｃ’＝Ｃ’−０ｘ８０００
変数Ｃ’で、Ｒ２に対応するビット列がＲ２’となり、Ｒ３に対応するビット列がＲ３’となる。【００４３】
先ず、付加ビット数算出手段１０７は、ＣＴカウンタ１０４のカウント値ＣＴｅｎｃが３以下であるか否かを判定する（ステップＳＴ１）。このとき、ＣＴカウンタ１０４のカウント値ＣＴｅｎｃが３以下でなく４以上の範囲である場合、付加ビット数算出手段１０７は、ステップＳＴ２の処理に進む。【００４４】
また、ＣＴカウンタ１０４のカウント値ＣＴｅｎｃが１〜３の範囲であると、付加ビット数算出手段１０７は、符号バイトＲ１が値０ｘＦＦであるか否かを判定する（ステップＳＴ３）。上述したように、符号バイトＲ１が値０ｘＦＦとなるのは、２値シンボルの符号化終了時に既に出力されている符号バイトＲ１が値０ｘＦＦである場合の他、Ｒ１＝０ｘＦＥかつＲ１へ桁上がりが発生している場合、つまりＲ１＝０ｘＦＥかつ符号化レジスタ１０５の（２７−ＣＴｅｎｃ）ビット目の値が１の場合も含むものとする。【００４５】
ここで、Ｒ１が値０ｘＦＦであると、付加ビット数算出手段１０７は、Ｒ３’が値０ｘＦＦであるか否かを判定する（ステップＳＴ４）。このとき、Ｒ３’が値０ｘＦＦであれば、付加ビット数算出手段１０７は、付加ビットのビット数Ｌｅｘｔが０であると判断して（ステップＳＴ５）、処理を終了する。一方、Ｒ３’が値０ｘＦＦでなければ、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ＋３）と決定して（ステップＳＴ６）、処理を終了する。このステップＳＴ５及びステップＳＴ６の場合分けが、図７に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが１〜３の範囲に相当する。【００４６】
例えば、図７において、カウント値ＣＴｅｎｃが１であるとき、ステップＳＴ５又はステップＳＴ６の処理によって、付加ビット数Ｌｅｘｔが０又は（ＣＴｅｎｃ＋３）＝４となる。なお、図７中の※１は、条件によっては−１となるバイトを示しており、−１であると、付加ビット数Ｌｅｘｔが０となる。図７では、カウント値ＣＴｅｎｃが１〜３の場合、ステップＳＴ４でＢ３’が値０ｘＦＦであれば、Ｂ３は−１となり、付加ビット数Ｌｅｘｔが０となる。【００４７】
ステップＳＴ３において、符号バイトＲ１が値０ｘＦＦでないと、付加ビット数算出手段１０７は、符号バイトＲ２が値０ｘＦＦであるか否かを判定する（ステップＳＴ７）。ここで、Ｒ２が値０ｘＦＦであるとき、ステップＳＴ８に進んで、Ｒ３’が値０ｘＦＦであるか否かを判定する。Ｒ３’が値０ｘＦＦであると、付加ビット数算出手段１０７は、付加ビットのビット数Ｌｅｘｔが０であると判断して（ステップＳＴ９）、処理を終了する。一方、Ｒ３’が値０ｘＦＦでなければ、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ＋３）と決定して（ステップＳＴ１０）、処理を終了する。【００４８】
このステップＳＴ９及びステップＳＴ１０の場合分けが、図８に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが１〜３の範囲に相当する。例えば、図８において、カウント値ＣＴｅｎｃが１であるとき、ステップＳＴ９又はステップＳＴ１０の処理によって、付加ビット数Ｌｅｘｔが０又は（ＣＴｅｎｃ＋３）＝４となる。なお、図８中の※２は、Ｂ３が値０ｘ７Ｆである場合は付加ビット数Ｌｅｘｔが０となることを示している。【００４９】
また、ステップＳＴ７において、Ｒ２が値０ｘＦＦでなければ、付加ビット数算出手段１０７は、Ｒ３’が値０ｘＦＦであるか否かを判定する（ステップＳＴ１１）。ここで、Ｒ３’が値０ｘＦＦであると、付加ビット数算出手段１０７は、付加ビットのビット数Ｌｅｘｔが０であると判断して（ステップＳＴ１２）、処理を終了する。一方、Ｒ３’が値０ｘＦＦでなければ、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ＋４）と決定して（ステップＳＴ１３）、処理を終了する。【００５０】
このステップＳＴ１２及びステップＳＴ１３の場合分けが、図６に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが１〜３の範囲に相当する。例えば、図６において、カウント値ＣＴｅｎｃが１であるとき、ステップＳＴ１２又はステップＳＴ１３の処理によって、付加ビット数Ｌｅｘｔが０又は（ＣＴｅｎｃ＋４）＝５となる。なお、図６中の※１は、図７の場合と同様である。【００５１】
一方、ステップＳＴ２において、付加ビット数算出手段１０７は、カウント値ＣＴｅｎｃが４であるか否かを判定する。カウント値ＣＴｅｎｃが４であれば、ステップＳＴ１４に進み、付加ビットのビット数Ｌｅｘｔが０であると判断して処理を終了する。【００５２】
また、カウント値ＣＴｅｎｃが５以上である場合、付加ビット数算出手段１０７は、Ｒ１が値０ｘＦＦであるか否かを判定する（ステップＳＴ１５）。ここで、Ｒ１が値０ｘＦＦであると、付加ビット数算出手段１０７は、ステップＳＴ１７に進み、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ−５）と決定して処理を終了する。【００５３】
ステップＳＴ１５においてＲ１が値０ｘＦＦでない場合、付加ビット数算出手段１０７は、Ｒ２’が値０ｘＦＦであるか否かを判定する（ステップＳＴ１６）。このとき、符号バイトＲ２’が値０ｘＦＦであると、付加ビット数算出手段１０７は、付加ビットのビット数Ｌｅｘｔが０であると判断して（ステップＳＴ１８）、処理を終了する。また、符号バイトＲ２’が値０ｘＦＦでない場合、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ−４）と決定して（ステップＳＴ１９）、処理を終了する。【００５４】
このステップＳＴ１４の場合分けが、図６〜図８に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが４の範囲に相当する。また、ステップＳＴ１７の場合分けが、図７に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが５〜８の範囲に相当する。例えば、図７において、カウント値ＣＴｅｎｃが５であるとき、ステップＳＴ１７の処理によって、付加ビット数Ｌｅｘｔが（ＣＴｅｎｃ−５）＝０となる。【００５５】
ステップＳＴ１８の場合分けは、図８に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが５〜８の範囲に相当する。例えば、図８において、カウント値ＣＴｅｎｃが５であるとき、ステップＳＴ１８の処理によって、付加ビット数Ｌｅｘｔが（ＣＴｅｎｃ−５）＝０となる。また、ステップＳＴ１９の場合分けは、図６に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが５〜８の範囲に相当する。例えば、図６において、カウント値ＣＴｅｎｃが５であるとき、ステップＳＴ１９の処理によって、付加ビット数Ｌｅｘｔが（ＣＴｅｎｃ−４）＝１となる。【００５６】
このようにして、付加ビット数算出手段１０７は、復号側で検出可能な情報である、符号化レジスタ１０５の値、区間幅レジスタ１０６の値、正規化処理の回数、及びエントロピー符号化終了直前に符号化レジスタ１０５から出力された符号に基づいて、最終的に符号データとして出力する符号系列のうち、符号長が変わらない範囲で付加ビット数を決定する。【００５７】
なお、図６〜図８に示した付加ビット数は、符号化可能な付加ビット数の一例であり、さらに複雑な条件の分類をして、符号長が所定の条件を越えない範囲で更に多くの付加ビットを符号化することも可能である。また、逆に符号長が所定の条件を越えない範囲で図６〜図８で示した付加ビット数より少ない数とすることも可能である。【００５８】
（２）符号化レジスタ値に付加ビットを反映する処理
上述の手順（１）により付加ビットのビット数Ｌｅｘｔが決定されると、付加ビット符号化手段１０８は、付加ビット数Ｌｅｘｔを用いて下記式（１）から付加ビットに対応する値ΔＣを算出する。この後、付加ビット符号化手段１０８は、下記式（２）に従ってΔＣを符号化レジスタＣに加算し、付加ビットを反映させた符号化レジスタ値Ｃ”を算出する。なお、下記式（１）におけるＳｉは付加ビットを構成する各ビット値を示しており、Ｓ１，Ｓ２，・・・，ＳLext（Ｓｉ＝０または１）となる。
【数１】
2008129883.tif 000003
【００５９】
上記式（１）による処理は、例えば図３でカウント値ＣＴｅｎｃが５〜８の場合における符号バイト中に数字を付したビットに対して、付加ビットの値を加算することに相当する。これにより、符号長が一定のままで、付加ビットが符号バイトの終端部に埋め込まれる。但し、図３〜図６中に斜字で示したビットは、条件によって付加ビット数＝０となる（付加ビットを加算しない）ことを表している。以降、ΔＣを加算した符号化レジスタ１０５に格納されるＲ２，Ｒ３に対応するバイトをＲ２”，Ｒ３”と表記する。【００６０】
（３）符号出力処理
付加ビット符号化手段１０８は、手順（２）で符号化レジスタ１０５にΔＣを加算して符号化レジスタ値Ｃ”を得ると、ΔＣを加算した符号化レジスタ１０５の１５ビット目を含むバイトまでを符号とする旨を算術演算手段１０３に通知する。これにより、算術演算手段１０３は、該符号を符号データとして出力する。【００６１】
例えば、図３に示す場合分け条件であるＲ１≠０ｘＦＦかつＲ２≠０ｘＦＦにおいて、ＣＴカウンタ１０４のカウント値ＣＴｅｎｃが６である場合、Ｒ２”（ΔＣの加算によりＲ２端部の２ビットに付加ビットが加算された値）までが符号として出力される。また、図３に示す場合分け条件であるＲ１≠０ｘＦＦかつＲ２≠０ｘＦＦにおいて、カウント値ＣＴｅｎｃが１である場合は、図９中のステップＳＴ１１の処理により、Ｒ３’も参照され、Ｒ３’＝０ｘＦＦならば付加ビット数＝０となり、Ｒ３’≠０ｘＦＦならばＲ３”までが符号として出力される。【００６２】
一方、手順（１）において付加ビット数Ｌｅｘｔが０と決定された場合、付加ビット符号化手段１０８は、その旨を算術演算手段１０３に通知する。これにより、算術演算手段１０３は、符号化レジスタ１０５の値に対して推奨フラッシュ処理を施す。推奨フラッシュでは、原則として符号化レジスタ１０５からＲ２’，Ｒ３’の２バイトを符号として出力するが、Ｒ３’が値０ｘＦＦである場合には、Ｒ３’は出力しない。【００６３】
ここで、具体例を挙げて手順（１）〜（３）の付加ビット埋め込み処理を説明する。
２値シンボルの符号化終了時点における符号化レジスタ１０５の値Ｃを０ｘ１４４０４６８とし、ＣＴカウンタ１０４のカウント値ＣＴｅｎｃを２、バイトＲ１を値０ｘＦ５とする。この場合、Ｒ２＝０ｘＡ２、Ｒ３＝０ｘ０２であるので、図９に示すフローチャートに従うと、付加ビット数Ｌｅｘｔが６と決定される。【００６４】
６ビットの付加ビットの値を｛１１０１００｝とすると、上記式（１）によってΔＣ＝０ｘ６８００となり、上記式（２）によって、付加ビットを反映させた符号化レジスタ値Ｃ”は、Ｃ＋ΔＣ＝０ｘ１４４６Ｃ６８となる。このとき、上述したＲ２，Ｒ３に対応するバイトＲ２”，Ｒ３”は、それぞれ、Ｒ２”＝０ｘＡ２、Ｒ３”＝０ｘ３６となる。これにより、最終的に算術演算手段１０３から出力される符号データの符号系列の最後３バイトは、Ｆ５  Ａ２  ３６となる。【００６５】
なお、上記説明では、手順（２）でΔＣを加算してＣ”を算出し、手順（３）で符号を出力する例を示した。手順（２）については、上述した処理手順の他、２値シンボル符号化の終了時点に以下の各変数を固定値に設定し（学習は行わない）、付加ビットを手順（１）で定まった付加ビット数だけ、通常のＱＭコーダの処理により符号化することも可能である。このようにして手順（３）で符号を出力しても全く同じ符号化結果が得られる。
区間幅レジスタ１０６の値Ａ＝０ｘ８０００
優勢シンボル（ＭＰＳ）の区間幅＝０ｘ４０００
劣勢シンボル（ＬＰＳ）の区間幅＝０ｘ４０００
優勢シンボルＭＰＳ＝１，劣勢シンボルＬＰＳ＝０【００６６】
次に、復号側の処理について説明する。
図２に示す実施の形態１による復号装置では、非特許文献１に記載されるＭＱコーダと同様の処理によって、画像の符号データを復号する。ＣＴカウンタ、符号化レジスタ、区間幅レジスタの構成も非特許文献１と同一である。このとき、付加ビット数算出手段２０７及び付加ビット復号手段２０８は、動作しない。つまり、付加ビット数算出手段２０７及び付加ビット復号手段２０８を除いた、コンテクスト作成手段２０１、確率推定手段２０２、算術演算手段２０３、ＣＴカウンタ２０４、復号レジスタ２０５、区間幅レジスタ２０６及び排他的論理和回路２０９によって、画像の符号データが復号される。【００６７】
付加ビット数算出手段２０７及び付加ビット復号手段２０８は、２値シンボルを復号した最終的な２値シンボルが復号された後、この時点でのＣＴカウンタ２０４のカウント値、復号レジスタ２０５の値、及び算術演算手段２０３により直前に読み込まれた符号を参照して、付加ビットのビット数を決定し付加ビットを復号する。【００６８】
ここでは、付加ビット数算出手段２０７及び付加ビット復号手段２０８によってなされる付加ビット復号の処理手順について説明する。
（１ａ）符号化側ＣＴカウンタのカウント値ＣＴｅｎｃの算出処理
付加ビット数算出手段２０７は、２値シンボル復号終了時点でのＣＴカウンタ２０４のカウント値ＣＴｄｅｃから、符号化側での２値シンボル符号化終了時点におけるＣＴカウンタ１０４のカウント値ＣＴｅｎｃを算出する。図６〜図８に示すように、符号化側のＣＴカウンタ１０４と復号側のＣＴカウンタ２０４とのカウント値は同一ではなく、値０ｘＦＦをとるバイトの発生によりその差も変化する。【００６９】
図１０は、図２中の画像復号装置による符号化側ＣＴカウンタ値の算出処理を示すフローチャートであり、この図を用いてＣＴカウンタ１０４のカウント値ＣＴｅｎｃの算出手順を説明する。なお、図１０に示したＣｏｄｅ［ｉ］は、２値シンボル復号終了時点までに復号側で読み込んだ符号を示している。ここで、最終バイトがＣｏｄｅ［ｎ］、それ以前のバイトが順にＣｏｄｅ［ｎ−１］、Ｃｏｄｅ［ｎ−２］、Ｃｏｄｅ［ｎ−３］，・・・となる。【００７０】
先ず、付加ビット数算出手段２０７は、ＣＴカウンタ２０４のカウント値ＣＴｄｅｃが４以下であるか否かを判定する（ステップＳＴ１ａ）。このとき、ＣＴカウンタ２０４のカウント値ＣＴｄｅｃが４以下の範囲である場合、付加ビット数算出手段２０７は、ステップＳＴ２ａの処理に進む。ステップＳＴ２ａにおいて、付加ビット数算出手段２０７は、復号側で読み込んだ符号Ｃｏｄｅ［ｎ−３］（Ｂ２に対応）が値０ｘＦＦ又は符号Ｃｏｄｅ［ｎ−２］（Ｂ３に対応）が値０ｘＦＦであるか否かを判定する。【００７１】
ここで、符号Ｃｏｄｅ［ｎ−３］が値０ｘＦＦ又は符号Ｃｏｄｅ［ｎ−２］が値０ｘＦＦであると、付加ビット数算出手段２０７は、符号化側のＣＴカウンタ１０４の値ＣＴｅｎｃを（ＣＴｄｅｃ＋４）と決定し（ステップＳＴ４ａ）、ステップＳＴ８ａの処理に進む。また、符号Ｃｏｄｅ［ｎ−３］が値０ｘＦＦ又は符号Ｃｏｄｅ［ｎ−２］が値０ｘＦＦでない場合は、符号化側のＣＴカウンタ１０４の値ＣＴｅｎｃを（ＣＴｄｅｃ＋３）と決定し（ステップＳＴ５ａ）、ステップＳＴ８ａの処理に進む。【００７２】
一方、ステップＳＴ１ａにおいて、ＣＴカウンタ２０４のカウント値ＣＴｄｅｃが４以下でなく、５以上の範囲である場合、付加ビット数算出手段２０７は、ステップＳＴ３ａの処理に進む。ステップＳＴ３ａにおいて、付加ビット数算出手段２０７は、復号側で読み込んだ符号Ｃｏｄｅ［ｎ−４］（Ｂ１に対応）が値０ｘＦＦ又は符号Ｃｏｄｅ［ｎ−３］が値０ｘＦＦであるか否かを判定する。【００７３】
ステップＳＴ３ａで、符号Ｃｏｄｅ［ｎ−４］が値０ｘＦＦ又は符号Ｃｏｄｅ［ｎ−３］が値０ｘＦＦであると、付加ビット数算出手段２０７は、符号化側のＣＴカウンタ１０４の値ＣＴｅｎｃを（ＣＴｄｅｃ＋４）と決定し（ステップＳＴ６ａ）、ステップＳＴ８ａの処理に進む。また、符号Ｃｏｄｅ［ｎ−４］が値０ｘＦＦ又は符号Ｃｏｄｅ［ｎ−３］が値０ｘＦＦでない場合は、符号化側のＣＴカウンタ１０４の値ＣＴｅｎｃを（ＣＴｄｅｃ＋３）と決定し（ステップＳＴ７ａ）、ステップＳＴ８ａの処理に進む。【００７４】
ステップＳＴ８ａにおいて、付加ビット数算出手段２０７は、ステップＳＴ４ａ〜ステップＳＴ７ａの各処理で決定したカウント値ＣＴｅｎｃが８を超えるか否かを判定する。このとき、付加ビット数算出手段２０７は、カウント値ＣＴｅｎｃが８を超えなければ処理を終了し、カウント値ＣＴｅｎｃが８を超える場合はステップＳＴ９ａの処理に移行する。ステップＳＴ９ａでは、付加ビット数算出手段２０７が、カウント値ＣＴｅｎｃから８を減算した値をカウント値ＣＴｅｎｃに設定する。【００７５】
このように、付加ビット数算出手段２０７は、２値シンボル復号終了時点までに復号側で読み込んだ符号の値に基づいて、２値シンボル符号化終了時点における符号化側のＣＴカウンタ１０４のカウント値ＣＴｅｎｃを算出することができる。【００７６】
（２ａ）復号する付加ビット数Ｌｅｘｔの算出処理
図１１は、図２中の画像復号装置による付加ビット数の算出処理を示すフローチャートであり、この図及び図６〜８を用いて付加ビット数の算出手順を説明する。
先ず、付加ビット数算出手段２０７は、手順（１ａ）で算出した符号化側のＣＴカウンタ１０４の値ＣＴｅｎｃが３以下であるか否かを判定する（ステップＳＴ１ｂ）。このとき、カウント値ＣＴｅｎｃが３以下でなく４以上の範囲である場合、付加ビット数算出手段２０７は、ステップＳＴ２ｂの処理に進む。【００７７】
また、ＣＴｅｎｃが１〜３の範囲であると、付加ビット数算出手段２０７は、Ｃｏｄｅ［ｎ−４］（Ｂ１に対応）が値０ｘＦＦであるか否かを判定する（ステップＳＴ３ｂ）。ここで、Ｃｏｄｅ［ｎ−４］が値０ｘＦＦであると、付加ビット数算出手段２０７は、Ｃｏｄｅ［ｎ−２］（Ｂ３に対応）が−１であるか否かを判定する（ステップＳＴ４ｂ）。上述したように、−１は、復号側で読み込まれても符号がないために値０ｘＦＦをとるバイトが補填される符号を表している。【００７８】
ステップＳＴ４ｂにおいて、Ｃｏｄｅ［ｎ−２］が−１であれば、付加ビット数算出手段２０７は、付加ビットのビット数Ｌｅｘｔが０であると判断し（ステップＳＴ５ｂ）、処理を終了する。一方、Ｃｏｄｅ［ｎ−２］が−１でなければ、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ＋３）と決定して（ステップＳＴ６ｂ）、処理を終了する。このステップＳＴ５ｂ及びステップＳＴ６ｂの場合分けが、図７に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが１〜３の範囲に相当する。【００７９】
例えば、図７において、カウント値ＣＴｅｎｃが１（ＣＴｄｅｃ＝５）であるとき、ステップＳＴ５ｂ又はステップＳＴ６ｂの処理によって、付加ビット数Ｌｅｘｔが０又は（ＣＴｅｎｃ＋３）＝４となる。このとき、画像データの２値シンボルへの復号が終了する直前に受信、補填された符号５バイトは図７に示すようになり、値０ｘＦＦで補填する回数は、−１が設定された２バイトを補填する２回か、Ｂ３を補填する場合を含めた３回となる。図７では、カウント値ＣＴｅｎｃが１〜３の場合（ＣＴｄｅｃが５〜７）、ステップＳＴ４ｂでＣｏｄｅ［ｎ−２］が−１であれば、Ｂ３は−１となり、付加ビット数Ｌｅｘｔが０となる。【００８０】
ステップＳＴ３ｂにおいて、Ｃｏｄｅ［ｎ−４］が値０ｘＦＦでないと、付加ビット数算出手段２０７は、Ｃｏｄｅ［ｎ−３］（Ｂ２に対応）が値０ｘＦＦであるか否かを判定する（ステップＳＴ７ｂ）。ここで、Ｃｏｄｅ［ｎ−３］が値０ｘＦＦであるとき、ステップＳＴ８ｂに進んで、Ｃｏｄｅ［ｎ−２］が値０ｘ７Ｆであるか否かを判定する。Ｃｏｄｅ［ｎ−２］が値０ｘ７Ｆであると、付加ビット数算出手段２０７は、付加ビットのビット数Ｌｅｘｔが０であると判断して（ステップＳＴ９ｂ）、処理を終了する。一方、Ｃｏｄｅ［ｎ−２］が値０ｘ７Ｆでなければ、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ＋３）と決定して（ステップＳＴ１０ｂ）、処理を終了する。【００８１】
このステップＳＴ９ｂ及びステップＳＴ１０ｂの場合分けが、図８に示したＣＴカウンタ１０４のカウント値ＣＴｅｎｃが１〜３の範囲に相当する。例えば、図８において、カウント値ＣＴｅｎｃが１であるとき、ステップＳＴ９ｂ又はステップＳＴ１０ｂの処理によって、付加ビット数Ｌｅｘｔが０又は（ＣＴｅｎｃ＋３）＝４となる。このとき、画像データの２値シンボルの復号が終了する直前に受信、補填された符号５バイトは、図８に示すようになり、値０ｘＦＦで補填する回数は−１が設定された２バイトを補填する２回となる。【００８２】
また、ステップＳＴ７ｂにおいて、Ｃｏｄｅ［ｎ−３］が値０ｘＦＦでなければ、付加ビット数算出手段２０７は、Ｃｏｄｅ［ｎ−２］が−１であるか否かを判定する（ステップＳＴ１１ｂ）。ここで、Ｃｏｄｅ［ｎ−２］が−１であると、付加ビット数算出手段２０７は、付加ビットのビット数Ｌｅｘｔが０であると判断して（ステップＳＴ１２ｂ）、処理を終了する。一方、Ｃｏｄｅ［ｎ−２］が−１でなければ、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ＋４）と決定して（ステップＳＴ１３ｂ）、処理を終了する。【００８３】
このステップＳＴ１２ｂ及びステップＳＴ１３ｂの場合分けが、図６に示したカウント値ＣＴｅｎｃが１〜３の範囲に相当する。例えば、図６において、カウント値ＣＴｅｎｃが１であるとき、ステップＳＴ１２ｂ又はステップＳＴ１３ｂの処理によって、付加ビット数Ｌｅｘｔが０又は（ＣＴｅｎｃ＋４）＝５となる。このとき、画像データの２値シンボルの復号終了直前に受信、補填された符号５バイトは、図６に示すようになり、値０ｘＦＦで補填する回数は、−１が設定された２バイトを補填する２回か、Ｂ３を補填する場合を含めた３回となる。【００８４】
一方、ステップＳＴ２ｂにおいて、付加ビット数算出手段２０７は、カウント値ＣＴｅｎｃが４であるか否かを判定する。カウント値ＣＴｅｎｃが４であれば、ステップＳＴ１４ｂに進み、付加ビットのビット数Ｌｅｘｔが０であると判断して処理を終了する。【００８５】
また、カウント値ＣＴｅｎｃが５以上である場合、付加ビット数算出手段２０７は、Ｃｏｄｅ［ｎ−３］が値０ｘＦＦであるか否かを判定する（ステップＳＴ１５ｂ）。ここで、Ｃｏｄｅ［ｎ−３］が値０ｘＦＦであると、付加ビット数算出手段２０７は、ステップＳＴ１７ｂに進み、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ−５）と決定して処理を終了する。【００８６】
ステップＳＴ１５ｂにおいてＣｏｄｅ［ｎ−３］が値０ｘＦＦでない場合、付加ビット数算出手段２０７は、Ｃｏｄｅ［ｎ−２］が値０ｘＦＦであるか否かを判定する（ステップＳＴ１６ｂ）。このとき、Ｃｏｄｅ［ｎ−２］が値０ｘＦＦであると、付加ビット数算出手段２０７は、付加ビットのビット数Ｌｅｘｔが０であると判断して（ステップＳＴ１８ｂ）、処理を終了する。また、Ｃｏｄｅ［ｎ−２］が値０ｘＦＦでない場合、付加ビットのビット数Ｌｅｘｔを（ＣＴｅｎｃ−４）と決定して（ステップＳＴ１９ｂ）、処理を終了する。【００８７】
このステップＳＴ１４ｂの場合分けが、図６〜図８に示したカウント値ＣＴｅｎｃが４の範囲に相当する。また、ステップＳＴ１７ｂの場合分けが、図７に示したカウント値ＣＴｅｎｃが５〜８の範囲に相当する。例えば、図７において、カウント値ＣＴｅｎｃが５であるとき、ステップＳＴ１７ｂの処理によって、付加ビット数Ｌｅｘｔが（ＣＴｅｎｃ−５）＝０となる。【００８８】
ステップＳＴ１８ｂの場合分けは、図８に示したカウント値ＣＴｅｎｃが５〜８の範囲に相当する。例えば、図８において、カウント値ＣＴｅｎｃが５であるとき、ステップＳＴ１８ｂの処理によって、付加ビット数Ｌｅｘｔが（ＣＴｅｎｃ−５）＝０となる。また、ステップＳＴ１９ｂの場合分けは、図６に示したカウント値ＣＴｅｎｃが５〜８の範囲に相当する。例えば、図６において、カウント値ＣＴｅｎｃが５であるとき、ステップＳＴ１９ｂの処理によって、付加ビット数Ｌｅｘｔが（ＣＴｅｎｃ−４）＝１となる。【００８９】
このようにして、付加ビット数算出手段２０７は、復号レジスタ２０５の値、区間幅レジスタ２０６の値、手順（１ａ）で算出した符号化側での正規化処理の回数、及び画像データの２値シンボルの復号が終了する直前に復号レジスタ２０５に格納された符号に基づいて、受信した符号データの符号系列のうち、復号すべき付加ビット数を決定する。【００９０】
（３ａ）付加ビットの復号処理
上述の手順（２ａ）により復号すべき付加ビット数Ｌｅｘｔが決定されると、付加ビット復号手段２０８は、当該ビット数の付加ビットを復号するにあたり、算術演算手段２０３による算術復号に関わる変数を入力された符号系列を生成した符号化装置において付加ビットを符号化する際に区間幅レジスタ１０６、優勢シンボルの区間幅、劣勢シンボルの区間幅の値と同じ値に設定する。
もし、符号化装置において２値シンボルの符号化終了後、
区間幅レジスタ１０６の値Ａ＝０ｘ８０００
優勢シンボル（ＭＰＳ）の区間幅＝０ｘ４０００
劣勢シンボル（ＬＰＳ）の区間幅＝０ｘ４０００
優勢シンボルＭＰＳ＝１，劣勢シンボルＬＰＳ＝０
としたならば、
区間幅レジスタ２０６の値Ａ＝０ｘ８０００
優勢シンボル（ＭＰＳ）の区間幅＝０ｘ４０００
劣勢シンボル（ＬＰＳ）の区間幅＝０ｘ４０００
優勢シンボルＭＰＳ＝１，劣勢シンボルＬＰＳ＝０
とする。なお、この付加ビット復号の間は、出現確率の学習は行わない。【００９１】
この設定により、算術演算手段２０３は、１ビット復号するたびに必ず１回の正規化を行うことになる。算術演算手段２０３では、手順（２ａ）で算出された付加ビット数Ｌｅｘｔの回数だけのＭＱコーダの復号処理を繰り返し、付加ビットを付加ビット復号手段２０８に送信する。これにより、付加ビット復号手段２０８から付加ビットが出力される。【００９２】
ここで、具体例を挙げて手順（１ａ）〜（３ａ）の付加ビット復号処理を説明する。
画像データの復号終了時点における復号側のＣＴカウンタ２０４のカウント値ＣＴｄｅｃを７、画像データ復号終了間際に復号レジスタ２０５に読み込まれた５バイトの符号を、Ｃｏｄｅ［ｎ−４］＝０ｘＦ５、Ｃｏｄｅ［ｎ−３］＝０ｘＡ２、Ｃｏｄｅ［ｎ−２］＝０ｘ３６、Ｃｏｄｅ［ｎ−１］＝−１、Ｃｏｄｅ［ｎ］＝−１とする（なお、−１は符号が無くなってＦＦを補填したことを表す）。【００９３】
図１０に示すフローチャートに従うと、画像データ符号化終了時のＣＴカウンタ１０４の値ＣＴｅｎｃが２となる。また、図１１に示すフローチャートに従った処理によって、付加ビット数Ｌｅｘｔ＝６が算出される。続いて、手順（３ａ）で設定した変数値で付加ビットのビット数だけＭＱコーダに従った復号を行うことにより、付加ビット｛１１０１００｝が復号される。【００９４】
以上のように、この実施の形態１によれば、情報源シンボルをエントロピー符号化した符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、符号系列終端に付加ビットとして設定可能なビット数を算出する付加ビット数算出手段１０７と、当該ビット数の付加ビットを符号系列終端に設定する付加ビット符号化手段１０８とを備えたので、符号系列の符号長を増加させずに付加ビットを埋め込むことができる。また、著作権情報や画像入力デバイスのパラメータなどの属性情報をデータに付加することができ、ひいては画像データの利便性を向上させることができる。【００９５】
また、上記実施の形態１によれば、付加ビットの算術符号化において、符号化レジスタ１０５の値、区間幅レジスタ１０６の値、正規化の回数、及びエントロピー符号化終了直前に符号化レジスタ１０５から出力された符号から付加ビット数を決定するので、符号あるいは符号器の状況に応じたビット数の付加ビットを付加し、より効率的に情報を付加することが可能である。【００９６】
さらに、上記実施の形態１によれば、付加ビットの算術符号化及び算術復号において、有効区間Ａを所定の値以上の値（例えば、全区間の１／２）とし、優勢シンボル（ＭＰＳ）の値を０又は１の固定値、優勢シンボルＭＰＳ、劣勢シンボルＬＰＳに対する区間幅を共に全区間の１／２の固定値に設定することにより、１シンボルの符号化、復号で必ず１回の正規化が発生する。このようにすることで、付加シンボルの符号長の計算が容易になる。【００９７】
さらに、上記実施の形態１によれば、符号化レジスタにおいて、正規化の回数から定まる最上位のバイトから特定の位置のビットを含むバイトまでを符号として生成するので、算術符号化のフラッシュ処理を簡易化することができる。【００９８】
さらに、上記実施の形態１によれば、付加ビットを埋め込んでも、埋め込まなくても符号長が変わらないよう付加ビットが埋め込まれるので、符号化以降の処理において付加ビットを埋め込まない場合と同じ処理を適用することができ、処理を簡易化できる。【００９９】
さらに、上記実施の形態１によれば、付加ビット系列を特定のビット数だけビットシフトして生成される値を加算した符号化レジスタにおいて、正規化の回数から定まる最上位のバイトから特定の位置のビットを含むバイトまでを符号として生成するので、複数の付加ビットをビット毎に算術符号化する処理が不要であり、符号化処理を簡易化することができる。【０１００】
実施の形態２．
この実施の形態２では、画像データの符号化に伴って生じる２値シンボル（以下、２値シンボルと呼ぶ）を非特許文献１に記載されるＭＱコーダを使って（フラッシュは任意の方法を使用）算術符号化することにより生成した符号系列を対象として、２値シンボルとは異なる付加情報である付加ビット（以下、付加ビットと呼ぶ）を埋め込む符号変換処理、及びこの符号に埋め込まれた付加ビットを抽出する復号処理を説明する。なお、この実施の形態２では、付加ビットを埋め込んでも、入力される付加ビットを埋め込まない符号系列と符号長（バイト数）が変わらないことを前提としている。【０１０１】
図１２は、この発明の実施の形態２による符号変換装置の構成を示すブロック図であり、本発明を画像データを算術符号化した符号系列に対して適用した場合を示している。図１２において、コンテクスト作成手段１２０１は、復号対象となる２値シンボルの出現確率を推定するための条件付けをするコンテクストＣＸを決定する。確率推定手段１２０２は、コンテクストＣＸから復号対象となる２値シンボルの予測値と出現確率を示すパラメータＬＳＺとを算出する。【０１０２】
算術演算手段１２０３は、符号データと推定確率から予測値が復号対象の２値シンボルと一致したか否か、つまり復号対象の２値シンボルがＭＰＳであるかＬＰＳであるかを算出する。復号器ＣＴカウンタ１２０５は、算術演算手段１２０３が直前に符号データを読み込んでからの正規化回数をカウントし記憶する。【０１０３】
復号レジスタ１２０６には、復号した２値シンボルに対応させた有効区間の下界値からその区間内の座標である符号へのオフセット値が格納される。区間幅レジスタ１２０４には、数直線上の有効区間を２値シンボルの出現確率に応じて分割した区間幅を規定する数値が格納される。【０１０４】
符号化レジスタ１２０８には、２値シンボル符号化終了時点での、符号化された２値シンボルに対応する有効区間の下界値が格納される。符号器ＣＴカウンタ１２０７には、符号化レジスタ１２０８における正規化の回数が格納される。【０１０５】
符号器情報算出手段１２０９は、２値シンボル復号終了時点での区間幅レジスタ１２０４、復号器ＣＴカウンタ１２０５、復号レジスタ１２０６の値と、直前に読み込んだ数バイトの符号から、符号データを生成した符号器の符号化終了時点での符号化レジスタ及び符号器ＣＴカウンタの値を算出する。【０１０６】
付加ビット数算出手段１２１０は、埋め込み可能な付加ビットの数を決定する。付加ビット符号化手段１２１１は、入力される符号データのうち、終端の付加ビットを埋め込んだ符号データは修正を加え、付加ビットを埋め込まない部分の符号データは変更せずにそのまま出力する。【０１０７】
上述した、コンテクスト作成手段１２０１、確率推定手段１２０２、算術演算手段１２０３、符号器情報算出手段１２０９、付加ビット数算出手段１２１０及び付加ビット符号化手段１２１１は、本発明の趣旨に従う符号変換用プログラムをコンピュータに読み込ませてその動作を制御することにより、当該コンピュータ上でソフトウエアとハードウェアが協働した具体的な手段として図１２に示す符号変換装置を実現することができる。【０１０８】
図１３は、実施の形態２による復号装置の構成を示すブロック図であり、実施の形態２の符号変換装置で生成した符号系列に対して、実施の形態２の復号装置を適用する場合を示している。実施の形態２の符号変換装置との違いは、入力が実施の形態２の符号変換装置で生成した符号データであること、出力が復号された２値シンボルと埋め込まれていた付加ビットであること、付加ビット符号化手段１２１１の代わりに付加ビット復号手段１３１１を有することである。【０１０９】
符号器ＣＴカウンタ１３０７、符号化レジスタ１３０８、区間幅レジスタ１３０４、復号器ＣＴカウンタ１３０５、復号レジスタ１３０６、符号器情報算出手段１３０９、及び付加ビット数算出手段１３１０は、図１２に示した実施の形態２による符号変換装置と同様であるので説明を省略する。付加ビット復号手段１３１１は、２値シンボル復号終了後、入力された符号系列に埋め込まれた付加ビットのビット数だけ復号を実行し、付加ビットを抽出する。【０１１０】
上述した、コンテクスト作成手段１３０１、確率推定手段１３０２、算術演算手段１３０３、符号情報算出手段１３０９、付加ビット数算出手段１３１０及び付加ビット復号手段１３１１は、本発明の趣旨に従う符号変換用プログラムをコンピュータに読み込ませてその動作を制御することにより、当該コンピュータ上でソフトウエアとハードウェアが協働した具体的な手段として図１３に示す符号変換装置を実現することができる。【０１１１】
なお、コンピュータ自体の構成及びその基本的な機能については、本発明の技術分野における技術常識に基づいて当業者が容易に認識できるものであり、本発明の本質に直接関わるものでないので詳細な記載を省略する。【０１１２】
次に動作について説明する。
図１２に示す実施の形態２による符号変換装置では、最初に非特許文献１に記載されるＭＱコーダと同様の処理によって画像の符号データを復号する。復号器ＣＴカウンタ、復号レジスタ、区間幅レジスタの構成も非特許文献１と同一である。このとき、符号器情報算出手段１２０９、付加ビット数算出手段１２１０及び付加ビット符号化手段１２１１は、動作しない。つまり、符号器情報算出手段１２０９、付加ビット数算出手段１２１０、付加ビット符号化手段１２１１、符号器ＣＴカウンタ１２０７、及び符号化レジスタ１２０８を除いた、コンテクスト作成手段１２０１、確率推定手段１２０２、算術演算手段１２０３、符号器ＣＴカウンタ１２０７、復号レジスタ１２０６、区間幅レジスタ１２０４及び排他的論理和回路１２１２によって、２値シンボルが復号される。【０１１３】
２値シンボルの復号が終了した後に、符号器情報算出手段１２０９と付加ビット数算出手段１２１０により付加ビット数を算出し、付加ビット符号化手段１２１１により付加ビットを符号データに埋め込む。【０１１４】
実施の形態２で使う変数Ｃｏｄｅ［ｉ］は、上記実施の形態１と同様に、画像データ復号終了時点までに復号側で読み込んだ符号データを示している。ここで、最終バイトがＣｏｄｅ［ｎ］、それ以前のバイトが順にＣｏｄｅ［ｎ−１］、Ｃｏｄｅ［ｎ−２］、Ｃｏｄｅ［ｎ−３］，・・・となる。構成図には図示しないが、Ｃｏｄｅ［ｎ］〜Ｃｏｄｅ［ｎ−４］まで、つまり直近５バイトの符号データを保存しておくメモリが必要となる。この他、符号化レジスタ１２０８の値Ｃｅｎｃ、符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃも、上記実施の形態１で示した符号化レジスタ１０５の値Ｃｅｎｃ、ＣＴカウンタ１０４の値ＣＴｅｎｃと同様である。【０１１５】
（１ｃ−１）符号器の情報（符号器ＣＴカウンタ）の算出処理
図１４は、実施の形態２による符号化レジスタと復号レジスタの構成を示す図である。実施の形態２においては、付加ビットを除いて符号化処理は行わないので、２値シンボルが復号されるたびに、符号化レジスタ、符号器ＣＴカウンタの値が更新されることはない。２値シンボルの復号終了後に、その符号を生成した符号器（明示しないが、実施の形態１で説明した図１と同様の符号器）の２値シンボルの符号化終了時点での符号化レジスタ、ＣＴカウンタの値を後述する方法で再現して、それらを符号化レジスタ１２０８、符号器ＣＴカウンタ１２０７に設定する。符号器の符号化レジスタ（図１ならば符号化レジスタ１０５）から２値シンボルの符号化終了の直前に出力された１バイトの符号データをＲ１、符号器ＣＴカウンタ（図１ならばＣＴカウンタ１０４）の値によって規定される符号化レジスタの有効なビットのうち、最初の符号バイトをＲ２、２番目の符号バイトをＲ３とする。また、Ｒ１，Ｒ２，Ｒ３に対応するビット位置の最終的な符号データをそれぞれＢ１，Ｂ２，Ｂ３とする。Ｒ２’，Ｒ３’は、推奨フラッシュで必要な以下の処理を行った場合のＲ２，Ｒ３に対応するビット列であり、以下のように算出する。【０１１６】
２値シンボルの符号化終了時点における、符号化レジスタ１２０８の値をＣ、区間幅レジスタ１２０４の値をＡとした場合、次の処理を行って、Ｃ’を算出する。
Ｃ’＝Ｃ  ＯＲ  ０ｘＦＦＦＦ  （ＯＲはビット和を表す）
ｉｆ（Ｃ’≧（Ｃ＋Ａ））  Ｃ’＝Ｃ’−０ｘ８０００
変数Ｃ’で、Ｒ２に対応するビット列がＲ２’となり、Ｒ３に対応するビット列がＲ３’となる。【０１１７】
また、図１４は、Ｒ１≠０ｘＦＦかつＲ２’≠０ｘＦＦの場合の符号化レジスタと復号レジスタの構成を示している。さらに、図１４は、２値シンボル符号化終了時点で符号器ＣＴカウンタの値が１〜８までの各値となった場合に、符号として出力されるバイトが符号化レジスタ内でどの位置に格納されているか、入力された符号が復号レジスタ内のどの位置に格納されているかを示している。【０１１８】
例えば、符号器ＣＴカウンタの値ＣＴｅｎｃ＝７の場合、２値シンボルの復号終了時点で符号化レジスタの対応する符号データは、斜線で示した１バイトとそれに続く“？”を付した２バイトである。この場合、符号化レジスタの最上位バイトから、復号レジスタの最下位バイトまでに何バイトの符号データが含まれるかを示す値、読み込みバイト数Ｎｕｍ＿Ｂｙｔｅｓ＝３とする。【０１１９】
ここで、符号化時に推奨フラッシュを行ったならば、図１４中で斜線で示した１バイトが最終バイトとなり、残りの２バイトは復号側で補填された値０ｘＦＦをとるバイトである。しかし、別のフラッシュを行うと、図１４中に“？”で示したバイトが符号として出力される、あるいはそれ以降のバイトまでが符号として出力されることがあり得る。【０１２０】
さらに、これらのバイトが値０ｘＦＦをとると、後続のバイトでは最初の１ビットが桁上がり用の制御ビットに使用されるため、復号レジスタには７ビット分しか読み込まれない。そのため、符号器ＣＴカウンタ、読み込みバイト数の算出時には、後述するように、０ｘＦＦの発生を考慮した処理が必要となる。【０１２１】
図１５は、実施の形態２による符号器情報の算出処理を示すフローチャートである。この図１５のフローチャートを使い、２値シンボル復号終了時点での符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃ及び読み込みバイト数Ｎｕｍ＿Ｂｙｔｅｓの算出手順を説明する。【０１２２】
最初に、符号器情報算出手段１２０９は、復号器ＣＴカウンタ１２０５の値ＣＴｄｅｃから符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃを算出する。ステップＳＴ１４０１〜ステップＳＴ１４０３において、符号器情報算出手段１２０９が、符号化レジスタ１２０８の最上位バイトから復号レジスタ１２０６の最下位バイトまでに０ｘＦＦの符号データが含まれていない場合の復号器ＣＴカウンタ１２０７の値ＣＴｄｅｃを算出する。【０１２３】
次に、ステップＳＴ１４０４〜ステップＳＴ１４０９において、符号器情報算出手段１２０９は、読み込んだ符号データに０ｘＦＦが含まれている場合を想定した、符号器ＣＴカウンタ１２０７の値の調整を行う。ここでは、最終バイトから３バイト目まででの０ｘＦＦをチェックし、０ｘＦＦが含まれていたら、その個数をＣＴｅｎｃの値に加算する。【０１２４】
ステップＳＴ１４１０において、符号器情報算出手段１２０９は、復号器ＣＴカウンタ１２０５の値が５以下か否かを判定する。６以上ならば必ず読み込みバイトＮｕｍ＿Ｂｙｔｅｓは４であるが、５以下の場合には、Ｎｕｍ＿Ｂｙｔｅｓは３あるいは４となる。【０１２５】
復号器ＣＴカウンタ１２０５の値が５以下の場合、ステップＳＴ１４１１の時点での符号器ＣＴカウンタ１２０７の値が８を超えていると判定されたら、読み込みバイト数は４と判断できる。ステップＳＴ１４１２において、符号器情報算出手段１２０９は、最終バイトから５バイト目が０ｘＦＦであるかを判定し、０ｘＦＦならばステップＳＴ１４１３で符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃに１を加える。さらに、ステップＳＴ１４１４において、符号器情報算出手段１２０９は、符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃから８を引く。【０１２６】
ステップＳＴ１４１１の時点での符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃが８以下の場合、読み込みバイトＮｕｍ＿Ｂｙｔｅｓは、３または４となる。ステップＳＴ１４１６において、符号器情報算出手段１２０９は、符号器ＣＴカウンタの値ＣＴｅｎｃ＝８かつＣｏｄｅ［ｎ−４］＝０ｘＦＦであるか否かを判断する。このとき、値ＣＴｅｎｃ＝８かつＣｏｄｅ［ｎ−４］＝０ｘＦＦであるならば（Ｙｅｓ）、符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃ＝１、読み込みバイト数Ｎｕｍ＿Ｂｙｔｅｓ＝４となる。また、ステップＳＴ１４１６での判定結果が値ＣＴｅｎｃ＝８かつＣｏｄｅ［ｎ−４］＝０ｘＦＦでない場合（Ｎｏ）のみ、読み込みバイト数Ｎｕｍ＿Ｂｙｔｅｓ＝３と判断できる。【０１２７】
復号器ＣＴカウンタ１２０７の値ＣＴｅｎｃが６以上の場合、必ず読み込みバイトＮｕｍ＿Ｂｙｔｅｓは４である。また、ステップＳＴ１４２０で最終バイトから５バイト目が０ｘＦＦであることが判定されると、符号器情報算出手段１２０９は、符号器ＣＴカウンタの値ＣＴｅｎｃに１を加える（ステップＳＴ１４２１）。【０１２８】
以上の処理により、２値シンボル復号終了時点（符号化終了時点）での、符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃ、読み込みバイト数Ｎｕｍ＿Ｂｙｔｅｓが算出される。【０１２９】
（１ｃ−２）符号器の情報（符号化レジスタ）の算出処理
次に、図１５のフローチャートから続く、図１６のフローチャートでは、図１５で求めた符号器ＣＴカウンタ１２０７の値ＣＴｅｎｃ、読み込みバイト数Ｎｕｍ＿Ｂｙｔｅｓを使い、符号化レジスタ１２０８の値を算出する手順を説明する。【０１３０】
ＭＱコーダでは、２値シンボル符号化終了時点での符号化レジスタ１２０８の値Ｃｅｎｃが最終有効領域の下界値を示す。一方、復号レジスタ１２０６は、最終的に符号として出力された座標値と有効領域下界値との差を示している。この処理では、最終的に符号として出力された座標値からそれと有効領域下界値との差である復号レジスタ１２０６の値を引くことにより、２値シンボル符号化終了時点での符号化レジスタ１２０８の値を算出する。【０１３１】
図１６に示すステップＳＴ１５０１〜ステップＳＴ１５１０において、符号器情報算出手段１２０９は、符号化レジスタ１２０８に実際に符号として出力された（あるいは復号側で補填された）符号データを読み込んで、符号として出力された座標値を算出する。【０１３２】
ステップＳＴ１５０３〜ステップＳＴ１５１０で構成されるループでは、読み込みバイト数Ｎｕｍ＿Ｂｙｔｅｓの符号データを符号化レジスタ１２０８に代入する。ここで、構成図には明記しないが、符号化レジスタ１２０８に書き込むバイト数を示す変数ｔと符号データの各バイトを符号化レジスタ１２０８内のどのビット位置に書き込むかを示す変数ｂが使用されている。基本的に変数ｂは、１バイト書き込むたびに８ビット加算するが、ステップＳＴ１５０３で書き込みバイトが０ｘＦＦと判断された場合には、７ビットの加算となる。また、ステップＳＴ１５０７、ステップＳＴ１５０８で、Ｃｏｄｅ［ｎ−ｂ＋１]＝−１（０ｘＦＦを補填）の場合には、Ｃｏｄｅ[ｎ−ｂ＋１]＝０ｘＦＦとして処理するものとする。【０１３３】
次に、ステップＳＴ１５１１〜ステップＳＴ１５１３において、符号器情報算出手段１２０９は、符号化レジスタ１２０８に格納されている、符号として出力された座標値から復号レジスタ１２０６の値を引くことにより、有効領の下界値、つまり２値シンボル符号化終了時点での符号化レジスタ１２０８の値を算出する。【０１３４】
復号レジスタ１２０６を８ビットシフトしているのは、図１４に示すように、符号化レジスタ１２０８と復号レジスタ１２０６で８ビットのずれがあるからである。また、ステップＳＴ１５１１において、符号器情報算出手段１２０９は、符号化レジスタ１２０８で桁上がりが発生しているか否かを判定する。桁上がりが発生している場合（ステップＳＴ１５１１でＮｏの判定）、符号器情報算出手段１２０９は、ステップＳＴ１５１２で符号化レジスタ１２０８の最上位ビットを１にする。【０１３５】
なお、上記の手法では、２値シンボル復号終了時に利用可能な情報から、符号化レジスタ１２０８、符号器ＣＴカウンタ１２０７などの符号器の情報を算出した。これとは異なり、実施の形態２による符号変換装置にＭＱコーダの算術符号器も実装し、２値シンボルが復号されるたびにそれを算術符号化して、２値シンボル復号終了時点での符号器情報を得るように構成してもよい。この場合、算術復号と並行して算術符号化も行うことになるので、演算負荷が高くなるが、復号終了後に符号器の情報を算出する処理は不要になる。【０１３６】
（２ｃ）付加ビット数Ｌｅｘｔの算出処理
図１７は、実施の形態２による付加ビット数の算出処理を示すフローチャートである。この図１７のフローチャートを使い、入力符号系列とバイト長を変えない埋め込み付加ビット数Ｌｅｘｔの算出手順を説明する。なお、実施の形態２では、上記実施の形態１と同様の手順で付加ビット数を算出する、つまり推奨フラッシュを施した符号系列の符号長を変えない範囲で埋め込み可能なビット数の付加ビットを埋め込むものとする。また、この実施の形態２では、任意のフラッシュを想定しているので、推奨フラッシュを施した符号系列よりも長い符号系列が入力されることも考えられる。しかしながら、この場合でも、上記実施の形態１よりも長い付加ビットを埋め込むことはしない。【０１３７】
逆に、埋め込み対象の符号系列が推奨フラッシュを施した符号系列よりも短い場合は、埋め込み付加ビット数Ｌｅｘｔ＝０とする。このために、図１７に示すフローチャートの最初のステップＳＴ１６０１で、付加ビット数算出手段１２１０が、Ｃｏｄｅ［ｎ−２］＝−１であるか、つまり３バイト前に読み込まれた符号が補填された０ｘＦＦであったかを判定し、Ｙｅｓならば、埋め込み付加ビット数Ｌｅｘｔ＝０とする。【０１３８】
付加ビット数Ｌｅｘｔの算出処理を行う段階では、符号化レジスタ１２０８、符号器ＣＴカウンタ１２０７などの符号器に関する情報が求められている。従って、これ以降の処理では、図１１に示した上記実施の形態１の場合と同様であるので、詳細な説明は省略する。ただし、この実施の形態２は、推奨フラッシュを施した符号系列と符号長が異なることがあるため、直前に出力したバイトＲ１を参照するには、上記（１ｃ−１）で求めたＮｕｍ＿Ｂｙｔｅｓを使い、Ｒ１＝Ｃｏｄｅ［ｎ−Ｎｕｍ＿Ｂｙｔｅｓ］を実行する。【０１３９】
なお、上記の付加ビット数は、符号化可能な付加ビット数の一例であり、さらに複雑な条件の分類をして、符号長が所定の条件を越えない範囲でさらに多くの付加ビットを符号化することも可能である。また、逆に符号長が所定の条件を越えない範囲で上記の付加ビット数より少ない数とすることも可能である。【０１４０】
（３ｃ）符号化レジスタ値に付加ビットを反映する処理
上記手順（２ｃ）により付加ビットのビット数Ｌｅｘｔが決定されると、付加ビット符号化手段１２１１は、上記実施の形態１で示した上記式（１）から付加ビットに対応する値ΔＣを算出する。この後、付加ビット符号化手段１２１１は、上記式（２）に従って、ΔＣを符号化レジスタＣに加算し、付加ビットを反映させた符号化レジスタの値Ｃ”を算出する。【０１４１】
上記手順は、２値シンボルの復号終了以降、以下のように各変数を固定値に設定して付加ビットを符号化する処理に相当する。
区間幅レジスタ１２０４の値Ａ＝０ｘ８０００
優勢シンボル（ＭＰＳ）の区間幅＝０ｘ４０００
劣勢シンボル（ＬＰＳ）の区間幅＝０ｘ４０００
優勢シンボルＭＰＳ＝１，劣勢シンボルＬＰＳ＝０【０１４２】
なお、必ずしも上記設定値でなくとも、以下のように各変数を固定値に設定してもよい。つまり、付加ビットを１ビット符号化（復号）するたびに、１回の再正規化が発生すれば任意の方法が可能である。
区間幅レジスタ１２０４の値Ａ＝２値シンボル復号終了時点での区間幅レジスタ値
優勢シンボル（ＭＰＳ）の区間幅＝２値シンボル復号終了時点での区間幅レジスタ値／２
劣勢シンボル（ＬＰＳ）の区間幅＝２値シンボル復号終了時点での区間幅レジスタ値／２
優勢シンボルＭＰＳ＝１，劣勢シンボルＬＰＳ＝０【０１４３】
（４ｃ）符号出力処理
上記（１ｃ）〜（３ｃ）の処理は、画像データの２値シンボルの復号が終了した後、実行する処理で、それ以前は、入力される符号データを変更することなく、そのまま出力する。以下では、画像データの２値シンボルの復号終了後の符号出力処理を説明する。【０１４４】
付加ビット符号化手段１２１１は、手順（３ｃ）で符号化レジスタ１２０８にΔＣを加算して符号化レジスタ値Ｃ”を得ると、ΔＣを加算した符号化レジスタ１２０８の１５ビット目を含むバイトまでを符号として決定する。この後、付加ビット符号化手段１２１１は、決定した符号データで、入力された符号系列の対応する符号データを置き換える。さらに入力符号系列が続く場合には、以下の処理を行い、出力される符号系列を入力符号系列と同じバイト数にする。【０１４５】
（４ｃ−１）１バイト長い場合
符号化レジスタ１２０８の値Ｃにおいて、ΔＣが加算されたバイトの次のバイトが０ｘＦＦの場合は、付加ビットの埋め込みは行わず、入力符号系列を変更せずに出力する。これは、ΔＣが加算されたバイトの次のバイトを０ｘＦＦにしないと付加ビットが正しく復号できないが、最終バイトを０ｘＦＦとすることがＭＱコーダでは禁止されているためである。ΔＣが加算されたバイトの次のバイトが０ｘＦＦ以外の場合は、次のバイト、つまり符号の最終バイトを０ｘＦＥとして出力する。
（４ｃ−２）２バイト以上長い場合
最初の２バイトは、０ｘＦＦ，０ｘ７Ｆとする。それ以降は、０ｘＦＥを追加して、出力される符号系列を入力符号系列と同じバイト数に合わせる。【０１４６】
例えば、図１４に示す条件（Ｒ１≠０ｘＦＦかつＲ２≠０ｘＦＦ）で、符号器ＣＴカウンタ１２０７のカウント値ＣＴｅｎｃが６である場合、入力された符号系列が推奨フラッシュを行って生成されたならば、Ｒ２”（ΔＣの加算によりＲ２端部の２ビットに付加ビットが加算された値）までが符号として出力される。このとき、推奨フラッシュを行うならば、Ｒ２“が符号系列の最終バイトとなる。【０１４７】
ここでは、入力された符号系列が、図１８に示すようにＲ２までのバイト数に加えて、さらに２バイト長い符号系列であった場合を考える。この場合、付加ビット符号化手段１２１１は、Ｒ１に対応するバイト（Ｃｏｄｅ［ｎ−３］）までは、入力符号データを変更することなく出力する。Ｒ２に対応するバイト（Ｃｏｄｅ［ｎ−２］）については、Ｒ２”に置き換える。さらに残った２バイトについては、０ｘＦＦ、０ｘ７Ｆに置き換えて、入力符号系列と同じバイト数の符号系列を出力する。【０１４８】
次に復号側での動作について説明する。
図１３に示す実施の形態２による復号装置では、最初に非特許文献１に記載されるＭＱコーダと同様の処理によって画像の符号データを復号する。復号器ＣＴカウンタ１３０５、復号レジスタ１３０６、区間幅レジスタ１３０４の構成も非特許文献１と同一である。このとき、符号器情報算出手段１３０９、付加ビット数算出手段１３１０及び付加ビット復号手段１３１１は、動作しない。つまり、符号器情報算出手段１３０９、付加ビット数算出手段１３１０及び付加ビット復号手段１３１１、符号器ＣＴカウンタ１３０７、符号化レジスタ１３０８を除いた、コンテクスト作成手段１３０１、確率推定手段１３０２、算術演算手段１３０３、符号器ＣＴカウンタ１３０５、復号レジスタ１３０６、区間幅レジスタ１３０４及び排他的論理和回路１３１０によって、画像の符号データから２値シンボルが復号される。【０１４９】
付加ビット復号手段１３１１は、最終的な２値シンボルが得られた後、符号系列を生成した符号器での符号化レジスタ及び符号器ＣＴカウンタの値を、符号器情報算出手段１３０９で算出する。さらに付加ビット数算出手段１３１０が、埋め込まれている付加ビット数を算出し、付加ビット復号手段１３１１が、埋め込まれている付加ビットを復号する。ここで、符号器情報算出手段１３０９及び付加ビット数算出手段１３１０の処理は、実施の形態２による符号変換装置の符号器情報算出手段１２０９及び付加ビット数算出手段１２１０と同様であるので説明を省略し、付加ビット復号手段１３１１の処理を以下に説明する。【０１５０】
上述の（１ｃ）〜（２ｃ）と同じ手順により復号すべき付加ビット数Ｌｅｘｔが決定されると、付加ビット復号手段１３１１は、当該ビット数の付加ビットを復号するにあたり、算術演算手段１３０３による算術復号に関わる変数を入力された符号系列を生成した符号変換装置において付加ビットを符号化する際に設定した区間幅レジスタ１２０４、優勢シンボルの区間幅、劣勢シンボルの区間幅の値と同じ値に設定する。
もし、符号変換装置において２値シンボルの復号終了後、
区間幅レジスタ１２０４の値Ａ＝０ｘ８０００
優勢シンボル（ＭＰＳ）の区間幅＝０ｘ４０００
劣勢シンボル（ＬＰＳ）の区間幅＝０ｘ４０００
優勢シンボルＭＰＳ＝１，劣勢シンボルＬＰＳ＝０
としたならば、
区間幅レジスタ１３０４の値Ａ＝０ｘ８０００
優勢シンボル（ＭＰＳ）の区間幅＝０ｘ４０００
劣勢シンボル（ＬＰＳ）の区間幅＝０ｘ４０００
優勢シンボルＭＰＳ＝１，劣勢シンボルＬＰＳ＝０
とする。なお、この付加ビット復号の間は、出現確率の学習は行わない。【０１５１】
この設定により、算術演算手段１３０３は、１ビット復号するたびに必ず１回の正規化を行うことになる。算術演算手段１３０３では、手順（２ｃ）で算出された付加ビット数Ｌｅｘｔの回数だけのＭＱコーダの復号処理を繰り返し、付加ビットを付加ビット復号手段１３１１に送信する。これにより、付加ビット復号手段１３１１から付加ビットが出力される。【０１５２】
以上のように、この実施の形態２によれば、符号系列を構成する符号データから導かれる符号系列終端の情報に基づいて、符号系列終端に付加ビットとして埋め込むビット数を算出する付加ビット数算出手段１２１０と、当該ビット数の付加ビットが符号系列に含まれるように符号系列を変換する付加ビット符号化手段１２１１とを備えたので、符号系列の符号長を増加させずに付加ビットを埋め込むことができる。また、著作権情報や画像入力デバイスのパラメータなどの属性情報をデータに付加することができ、ひいては画像データの利便性を向上させることができる。
【産業上の利用可能性】
【０１５３】
以上のように、この発明に係る符号化装置は、符号系列の符号長を増加させずに付加ビットを埋め込むことができることから、著作権情報や画像入力デバイスのパラメータなどの属性情報をデータに付加することができ、画像データを符号化する画像符号化装置に適している。
【図１】
2008129883.tif 000004
【図２】
2008129883.tif 000005
【図３】
2008129883.tif 000006
【図４】
2008129883.tif 000007
【図５】
2008129883.tif 000008
【図６】
2008129883.tif 000009
【図７】
2008129883.tif 000010
【図８】
2008129883.tif 000011
【図９】
2008129883.tif 000012
【図１０】
2008129883.tif 000013
【図１１】
2008129883.tif 000014
【図１２】
2008129883.tif 000015
【図１３】
2008129883.tif 000016
【図１４】
2008129883.tif 000017
【図１５】
2008129883.tif 000018
【図１６】
2008129883.tif 000019
【図１７】
2008129883.tif 000020
【図１８】
2008129883.tif 000021
【国際調査報告】
2008129883.tif 000022
2008129883.tif 000023
2008129883.tif 000024
2008129883.tif 000025