(57)【要約】【課題】２つより多い符号語より構成される符号対象データをエントロピー符号する際、ハフマン符号復号器か、符号語をビットプレーンに分割して２値の算術符号復号器を適用していた。ハフマン符号復号器では一般に算術符号復号器より圧縮効率が悪く、ビットプレーンに分割した算術符号復号器では  ビットプレーン分割分実行スピードが低下するという課題があった。【解決手段】符号語数が２つの場合の算術符号は従来より発明されている。これを２つより多い符号語数の場合にも拡張できるように符号語数分に母区間を分割する事にした。【選択図】図１
2017212709.tif 000002
【特許請求の範囲】
【請求項１】
当該時点での符号語の発生確率で区分する母区間を表すＡｒｅｇ部と、
当該時点までの符号語系列発生確率を２進少数で表しているＣｒｅｇ部と、
母区間が小さくなり演算精度が減少することを防ぐための正規化を行うＲｅＮｏｒｍ部と、
符号時用のＣｒｅｇ加算部と、
符号時用の符号化データを出力するＢｙｔｅＯｕｔ部と、
復号時用のＣｒｅｇ減算部と、
復号時用の符号化データを入力するＢｙｔｅＩｎ部とを有する算術符号復号器において、
２つより多い数の符号語にも対応可能とした多値算術符号復号器。
【請求項２】
前記多値算術符号復号器を実現するため、各符号語発生順位毎に発生頻度を計数し、且つ符号語系列の当該時点での総数を計数するカウンタ部と、
符号語発生順位毎の当該時点での発生確率と、符号語系列発生確率を２進少数で表しているＣｒｅｇの変化量を算出するＱｅＱｃ推定部と、
発生順位の更新を行う順位更新部を有する事を特徴とする多値算術符号復号器。
【請求項３】
前記カウンタ部において、符号語数がＮｕｍＣｏｄｅ数あり、最大発生度数の順位を０位とし、最小発生度数の順位をＮｕｍＣｏｄｅ−１位とする場合、ＮｕｍＣｏｄｅ−２位のカウントはＮｕｍＣｏｄｅ−１位とＮｕｍＣｏｄｅ−２位の合算をカウントし、ＮｕｍＣｏｄｅ−３位のカウントは（ＮｕｍＣｏｄｅ−１）、（ＮｕｍＣｏｄｅ−２）および（ＮｕｍＣｏｄｅ−３）の合算をカウントし、０位のカウントは全符号語の発生度数をカウントするような低位からの累積カウンタするカウンタ部を有し、
前記ＱｅＱｃ推定部において、発生順位ｉ位の累積カウント値Ｃｏｕｎｔ［ｉ］より符号語系列発生確率を２進少数で表しているＣｒｅｇの変化量Ｑｃ［ｉ］をＱｃ［ｉ］＝（Ａｒｅｇ＊Ｃｏｕｎｔ［ｉ］／符号語系列数）により算出し、符号語発生順位ｉ位の当該時点での発生確率区分Ｑｅ［ｉ］をＱｅ［ｉ］＝Ｑｃ［ｉ＋１］−Ｑｃ「ｉ」より算出するＱｃＱｃ推定部をゆうする事を特徴とする多値算術符号復号器。
【請求項４】
前記ＱｅＱｃ推定部において、母区分を符号語数ＮｕｍＣｏｄｅ個に区分する符号語毎の確率区分Ｑｅと、当該時点での各順位の符号語系列の発生確率を表す代表点への変化量を表すＱｃを、計算する方法として、当該時点での母区分Ａｒｅｇと、当該時点での符号語総数でテーブルを組むことにより除算を回避したＱｅＱｃ部を有する算術符号復号器。
【発明の詳細な説明】
【技術分野】
【０００１】本発明は、エントロピー符号復号技術の内、算術符号復号技術に関し、特に２より多い符号語で構成される場合の符号復号する技術に関する。
【背景技術】
【０００２】  ２つより多い多値符号語を対象としたエントロピー符号復号器としてはハフマン符号復号器が、従来技術としてある。この技術はＪＰＥＧ（ＩＳＯ／ＩＥＣ  １０９１８）に国際標準として採用されている。
また、２つの符号語より構成されるデータを符号復号する技術としては算術符号復号器が、従来技術としてある。本発明と区別するため、２値算術符号復号器と呼称する。この技術はＪＢＩＧ（ＩＳＯ／ＩＥＣ）に国際標準として採用されている。
簡単に２値算術符号復号器を説明する。
符号語”０”の発生確率をＰ０、
符号語”１”の発生確率をＰ１、
符号語系列ＳＮ（Ｎ個の符号語の並び）の発生確率ＰＮ、
符号語系列ＳＮの中で符号語”０”の個数をＮ０、
符号語系列ＳＮの中で符号語”１”の個数をＮ１、とすると、
符号語系列ＳＮの発生確率は
Ｐ（ＳＮ）＝Ｐ０Ｎ０×Ｐ１Ｎ１となる。
Ｐ（ＳＮ）を表す２進少数のｂｉｔ数ＬＮは
ＬＮ＝１−ｌｏｇ２（Ｐ（ＳＮ））
（ＬＮ／Ｎ）＝−（Ｎ０／Ｎ）・ｌｏｇ２（Ｐ０）−（Ｎ１／Ｎ）・ｌｏｇ２（Ｐ１）＋（１／Ｎ）
となりＮが十分大きい時にはエントロピーに近づくのでＮ個のシンボル系列の発生確率を符号対象とすると圧縮効率が良い事が分かる。
シンボル系列の発生確率を符号対象とすることの効果は上述したが  これを実現するのに開発されたのが２値算術符号復号器である。重要な点は２点ある。
１点目はシンボルの発生確率が事前には分からない点である。この問題に対する回答としてＰ１（もしくはＰ０）の発生確率を予測確率として解決した点である。
２点目は確率の乗算計算を下記のようなしかけでシフトと加減算で代用できるようにした点である。劣性シンボルＬＰＳ（シンボルＰ０とＰ１の中で予測発生確率が小さい方）の予測発生確率を
Ｐ（ＬＰＳ）＝２−Ｑ、  Ｑは正の整数          （式２）
で近似する。優勢シンボルをＭＰＳと表す。シンボル系列ＳＮが発生した後にＬＰＳが発生する予測確率Ｐ（ＳＮ・ＬＰＳ）及びシンボル系列ＳＮが発生した後にＭＰＳが発生する予測確率Ｐ（ＳＮ・ＭＰＳ）は以下のようになる。
Ｐ（ＳＮ・ＬＰＳ）＝Ｐ（ＳＮ）・２−Ｑ、              （式３）
Ｐ（ＳＮ・ＭＰＳ）＝Ｐ（ＳＮ）・（１−２−Ｑ）、
＝Ｐ（ＳＮ）−Ｐ（ＳＮ・ＬＰＳ）、（式４）
これを再帰的に行っていくことで  ２値算術符号復号器を実現している。
一般にハフマン符号復号器より算術符号復号器のほうが圧縮効率がよい為、２つ以上の符号語よりなる多値符号語より構成されるデータへの適用が試みられ、ＪＰＥＧ２０００（ＩＳＯ／ＩＥＣ  １５４４４）では多値符号語データをビットプレーン毎にスライスして２値符号語とすることにより、２値算術符号復号器を多値符号語データに対しても適用することに成功した。
【先行技術文献】
【０００３】ＩＳＯ／ＩＥＣ  １５４４４
ＩＳＯ／ＩＥＣ  １０９１８
【発明の概要】
【発明が解決しようとする課題】
【０００４】  背景技術に前記したＪＰＥＧ２０００ではビットプレーンにスライスして２値算術符号復号器を適用すると走査回数がビットプレーン数以上必要となり、処理速度はハフマン符号復号器より低速となる。
本発明の目的は、この欠点を除去し多値符号語データに対して算術符号復号器を適用可能な、多値算術符号復号器を提供することにある。
【課題を解決するための手段】
【０００５】当該時点での符号語の発生確率で区分する母区間を表すＡｒｅｇ部と、
当該時点までの符号語系列発生確率を２進少数で表しているＣｒｅｇ部と、
母区間が小さくなり演算精度が減少することを防ぐための正規化を行うＲｅＮｏｒｍ部と、
符号時用のＣｒｅｇ加算部と、
符号時用の符号化データを出力するＢｙｔｅＯｕｔ部と、
復号時用のＣｒｅｇ減算部と、
復号時用の符号化データを入力するＢｙｔｅＩｎ部とを有する  算術符号復号器において、
２つより多い数の符号語に対応可能として多値算術符号復号器を実現する。
【発明の効果】
【０００６】  本発明により多値符号語に対して算術符号復号器を適用する個とが可能となり、ハフマン符号復号器と同等の実行スピードと、２値算術符号復号器と同等以上の圧縮効率を得ることになる。
【図面の簡単な説明】
【０００７】
【図１】多値算術符号復号器の概念図
【図２】多値算術符号復号器の符号化ブロック図
【図３】多値算術符号復号器の復号化ブロック図
【図４】多値算術符号復号器の共通部ブロック図
【図５】多値算術符号復号器の符号化フローチャート図
【図６】多値算術符号復号器の復号化フローチャート図
【発明を実施するための形態】
【実施例１】
【０００８】  次に、本発明の実施例１について図面を参照して説明する。図１は多値算術符号復号器の概念を４値を例にした概念図である。図２は符号化時のブロック構成図、図５は符号化時のフローチャートである。
図１の１３の点線部分は確当該時点の確率母区間。２値算術の場合にはこれを２つに区分していたが多値算術時には符号語数分、この例では４つに区分する。第３位の符号語が出現した場合、第２位の符号語が出現した場合、第１位の符号語が出現した場合、および第０位の符号語が出現した場合の４通りである。次の母区分Ａｒｅｇの候補としてＡｒｅｇを４つに区分したＱｅ［３］、Ｑｅ［２］、Ｑｅ［１］、Ｑｅ［０］を図５の１６のフローで用意しておく。［］内の数字は順位を表す。図１の１０，９，８，７を参照。また符号語系列の発生確率２進少数表現Ｃｒｅｇの変化量Ｑｃ［０］、Ｑｃ［１］，Ｑｃ［２］、Ｑｃ［３］も図５の１６のフローで用意しておく。
まず、符号化時の動作を説明する。符号化時には符号語が入力されるので、それよりその符号語の発生順位がわかる。図５の１５を参照。発生順位が１位であった。従って１位の確率区分Ｑｅ［１］が次の符号語時の母区分Ａｒｅｇとなる。図１の８を参照。この際、符号語系列の発生確率２進少数表現Ｃｒｅｇの値はＱｃ［１］加算されて図１の１４のようにＣｒｅｇは変化する。次の符号語は０位だった。従って０位の確率区分が次の符号語の母区分ＡｒｅｇとなりＣｒｅｇの値は不変となる。これを符号語系列に従い再帰的に実行する。母区分Ａｒｅｇは図１でもわかるように単調減少していき最終的にはゼロになり、実行不可能となる。これを防止するため、母区間Ａｒｅｇをある一定の値以上になるよう毎回左シフトを行うことにより防止する。これは２進小数点の桁を下げることを意味する。Ｃｒｅｇも母区間Ａｒｅｇと同じだけ左シフトを行う。これをＲｅＮｏｒｍと呼称する。これは従来の２値算術符号復号器と同じ動作である。
次に復号化時の動作を説明する。図１の概念図上での動作は符号化時と同じである。復号化時には符号語が入力されるのではなく、符号化データより符号語を算出しなければならない。この部分は図６の１９である。Ｃｒｅｇの値と符号化時と同じく用意したＱｃとを比較し発生順位ｉｉを決定する。この発生順位ｉｉに対応する符号語Ｄｉが復号結果となる。
【実施例２】  Ｃｏｕｎｔｅｒ［ｉｉ］は順位ｉｉのそれまでの積算値。
Ａｒｅｇは一つ前の符号語を算術符号した後の確率区分。
Ｓｕｍは当該時点までの符号語系列の総数。
Ｑｃ［ｉｉ］は当該時点で、順位ｉｉが発生する符号語系列の確率を表す代表点への変化量。
Ａｒｅｇを次の符号語の取り得る個数に符号語の予想発生確率に従って区分しないといけない。そこでそこまでの積算値Ｃｏｕｎｔｅｒ［ｉｉ］よりベイズ推定して以下のように当該順位［ｉｉ］の発生確率Ｑｃ［ｉｉ］］を予測する。
ＴｅｍｐＱｃ［ｉｉ］＝Ａｒｅｇ＊Ｃｏｕｎｔｅｒ［ｉｉ］／Ｓｕｍ
Ｑｃ［ｉｉ］＝Ａｒｅｇ−ＴｅｍｐＱｃ［ｉｉ］
Ｓｕｍでの除算を回避するためＡｒｅｇの上位ビットとＳｕｍの上位ビットとＳｕｍの桁数で場合分けを行いテーブルを作成し近似する。
ＴｅｍｐＱｃ［ｉｉ］≒ＱｃＴａｂｌｅ＊Ｃｏｕｎｔｅｒ［ｉｉ］
Ｑｃ［ｉｉ］＝Ａｒｅｇ−ＴｅｍｐＱｃ［ｉｉ］
当該時点での順位ｉｉが発生する符号語系列の確率を表す代表点への変化量Ｑｃ［ｉｉ］の算出後、次の通り確率区分Ｑｅを算出する。
ｉｉ！＝０：Ｑｅ［ｉｉ］＝ＴｅｍｐＱｃ［ｉｉ］−ＴｅｍｐＱｃ［ｉｉ−１］
ｉｉ＝＝０：Ｑｅ［０］＝Ａｒｅｇ−ＴｅｍｐＱｃ［１］
前記の通り符号語系列の発生確率２進少数表現Ｃｒｅｇの変化量と、次の母区分Ａｒｅｇの候補Ｑｅを計算することにより除算を回避し、実現性の高い多値算術符号復号器を実現する。
【符号の説明】
【０００９】１  符号語
２  符号語系列の発生確率を表す代表点への変化量を表すＱｃ
３  ＲｅＮｏｒｍ前の母区間Ａｒｅｇ信号
４  ＲｅＮｏｒｍ処理により桁補正完了後の母区間値Ａｒｅｇ
５  符号データ
６  符号語Ｄｉ決定するブロック
７  ０位が発生した場合の次の母区間Ｑｅ［０］＝Ａｒｅｇ−Ｑｃ［１］  且つ符号語系列発生確率を２進少数で表しているＣｒｅｇを１位が発生した場合の変化量Ｑｃ［１］
８  １位が発生した場合の次の母区間Ｑｅ［１］＝Ｑｃ［１］−Ｑｃ［０］
９  ２位が発生した場合の次の母区間Ｑｅ［２］＝Ｑｃ［２］−Ｑｃ［１］
１０  ２位が発生した場合の次の母区間Ｑｅ［３］＝Ｑｃ［３］−Ｑｃ［２］
１１  符号語系列発生確率を２進少数で表しているＣｒｅｇを２位が発生した場合の変化量Ｑｃ［２］
１２  符号語系列発生確率を２進少数で表しているＣｒｅｇを３位が発生した場合の変化量Ｑｃ［３］
１３  当該時点での符号語の発生確率で区分する母区間を表すＡｒｅｇ
１４  符号語系列発生確率を２進少数で表しているＣｒｅｇ
１５  符号語Ｄｉを入力しその発生順位ｉｉを出力するブロック
１６  ＱｅＱｃ推定部
１７  Ａｒｅｇの更新ブロック
１８  Ｃｒｅｇの更新ブロック
１９  符号語Ｄｉ決定するブロック内部のフローチャート
【図１】
2017212709.tif 000003
【図２】
2017212709.tif 000004
【図３】
2017212709.tif 000005
【図４】
2017212709.tif 000006
【図５】
2017212709.tif 000007
【図６】
2017212709.tif 000008