(57)【特許請求の範囲】
【請求項１】
情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法において、
情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、
情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、
各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、
上記カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、上記シンボルカウンタ型確率推定手順または上記状態遷移型確率推定手順を選択する確率推定判定手順と
を備えたことを特徴とする適応確率推定方法。
【請求項２】
上記シンボルカウンタ型確率推定手順は、
全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、上記カウント記憶手順に記憶させる累積出現頻度記憶手順と、
上記各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、
上記全情報源シンボルの累積出現頻度と上記劣勢シンボルの累積出現頻度との比あるいは上記優勢シンボルの累積出現頻度及び上記劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する
ことを特徴とする請求項１記載の適応確率推定方法。
【請求項３】
上記状態遷移型確率推定手順は、
上記カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、
上記遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する
ことを特徴とする請求項１または２記載の適応確率推定方法。
【請求項４】
情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法を用いて情報源シンボルを符号化する適応符号化方法において、
情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、
情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、
各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、
上記カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、上記シンボルカウンタ型確率推定手順または上記状態遷移型確率推定手順を選択する確率推定判定手順と、
上記シンボルカウンタ型確率推定手順または上記状態遷移型確率推定手順により推定された出現確率あるいは出現確率に相当する指標を用いて情報源シンボルを符号化する符号化手順と
を備えたことを特徴とする適応符号化方法。
【請求項５】
上記シンボルカウンタ型確率推定手順は、
全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、上記カウント記憶手順に記憶させる累積出現頻度記憶手順と、
上記各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、
上記全情報源シンボルの累積出現頻度と上記劣勢シンボルの累積出現頻度との比あるいは上記優勢シンボルの累積出現頻度及び上記劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する
ことを特徴とする請求項４記載の適応符号化方法。
【請求項６】
上記状態遷移型確率推定手順は、
上記カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、
上記遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する
ことを特徴とする請求項４または５記載の適応符号化方法。
【請求項７】
情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法を用いて、符号化された情報源シンボルを復号する適応復号方法において、
情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、
情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、
各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、
上記カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、上記シンボルカウンタ型確率推定手順または上記状態遷移型確率推定手順を選択する確率推定判定手順と、
上記シンボルカウンタ型確率推定手順または上記状態遷移型確率推定手順により推定された出現確率あるいは出現確率に相当する指標を用いて、符号化された情報源シンボルを復号する復号手順と
を備えたことを特徴とする適応復号方法。
【請求項８】
上記シンボルカウンタ型確率推定手順は、
全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、上記カウント記憶手順に記憶させる累積出現頻度記憶手順と、
上記各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、
上記全情報源シンボルの累積出現頻度と上記劣勢シンボルの累積出現頻度との比あるいは上記優勢シンボルの累積出現頻度及び上記劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する
ことを特徴とする請求項７記載の適応復号方法。
【請求項９】
上記状態遷移型確率推定手順は、
上記カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、
上記遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する
ことを特徴とする請求項７または８記載の適応復号方法。
【請求項１０】
情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置において、
情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、
情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、
各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、
上記カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、上記シンボルカウンタ型確率推定手段または上記状態遷移型確率推定手段を選択する確率推定判定手段と
を備えたことを特徴とする適応確率推定装置。
【請求項１１】
上記シンボルカウンタ型確率推定手段は、
全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、上記カウント記憶手段に記憶させる累積出現頻度記憶手段と、
上記各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、
上記全情報源シンボルの累積出現頻度と上記劣勢シンボルの累積出現頻度との比あるいは上記優勢シンボルの累積出現頻度及び上記劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する
ことを特徴とする請求項１０記載の適応確率推定装置。
【請求項１２】
上記状態遷移型確率推定手段は、
上記カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、
上記遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する
ことを特徴とする請求項１０または１１記載の適応確率推定装置。
【請求項１３】
情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置を用いて情報源シンボルを符号化する適応符号化装置において、
情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、
情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、
各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、
上記カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、上記シンボルカウンタ型確率推定手段または上記状態遷移型確率推定手段を選択する確率推定判定手段と、
上記シンボルカウンタ型確率推定手段または上記状態遷移型確率推定手段により推定された出現確率あるいは出現確率に相当する指標を用いて情報源シンボルを符号化する符号化手段と
を備えたことを特徴とする適応符号化装置。
【請求項１４】
上記シンボルカウンタ型確率推定手段は、
全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、上記カウント記憶手段に記憶させる累積出現頻度記憶手段と、
上記各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、
上記全情報源シンボルの累積出現頻度と上記劣勢シンボルの累積出現頻度との比あるいは上記優勢シンボルの累積出現頻度及び上記劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する
ことを特徴とする請求項１３記載の適応符号化装置。
【請求項１５】
上記状態遷移型確率推定手段は、
上記カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、
上記遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する
ことを特徴とする請求項１３または１４記載の適応符号化装置。
【請求項１６】
情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置を用いて、符号化された情報源シンボルを復号する適応復号装置において、
情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、
情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、
各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、
上記カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、上記シンボルカウンタ型確率推定手段または上記状態遷移型確率推定手段を選択する確率推定判定手段と、
上記シンボルカウンタ型確率推定手段または上記状態遷移型確率推定手段により推定された出現確率あるいは出現確率に相当する指標を用いて、符号化された情報源シンボルを復号する復号手段と
を備えたことを特徴とする適応復号装置。
【請求項１７】
上記シンボルカウンタ型確率推定手段は、
全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、上記カウント記憶手段に記憶させる累積出現頻度記憶手段と、
上記各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、
上記全情報源シンボルの累積出現頻度と上記劣勢シンボルの累積出現頻度との比あるいは上記優勢シンボルの累積出現頻度及び上記劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する
ことを特徴とする請求項１６記載の適応復号装置。
【請求項１８】
上記状態遷移型確率推定手段は、
上記カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、
上記遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する
ことを特徴とする請求項１６または１７記載の適応復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ信号の符号化、特にエントロピー符号化における適応確率推定方法、適応符号化方法、適応復号方法、適応確率推定装置、適応符号化装置及び適応復号装置に関する。
【０００２】
【従来の技術】
従来例１．
高効率なエントロピー符号化、復号を実現するためには、エンコードされ、その後のデコードされるべき信号の確率推定が必要であることが知られている。算術符号化（エンコーディング）と復号（デコーディング）では、精度の高い確率推定によって大きいデータの圧縮を可能とする。このために、確率推定はシンボル確率の変化に適応させることが望ましい。
【０００３】
従来の既知の米国特許（ＵＳＰ５０２５２５８号）や日本国特許（特公平８−３４４３３号公報）にはエンコードやデコードされるシンボルの推定確率への適応の程度を最適化することが開示されている。上記従来の技術について図１７、図１８にもとづいて詳細に説明する。
【０００４】
図１７は従来のエントロピー・エンコーダ１０１の簡単化したブロック・ダイヤグラムを示しており、それは、シンボルｓ（ｋ）を受入れ、これらのシンボルｓ（ｋ）をデータストリームａ（ｉ）の中へエンコードし、そしてこれらのシンボルｓ（ｋ）を伝送媒体１０２を介して遠隔のエントロピー・デコーダ１０３へ伝送する。エントロピー・デコーダ１０３は、受信機データストリームを得るために、伝送媒体を介して、それを伝送されたシンボルｓ（ｋ）のレプリカとしてデコードする。シンボルｓ（ｋ）はエレメント（０，…，Ｓ−１）即ち、
【０００５】
【数１】
0003708744.tif 000002
【０００６】
を含む。このように、シンボルは所望の多値または２値で与えられる。
従って、エンコーダ１０１は、この例では、算術エンコーダ・ユニット１０４、文脈抽出器１０５、適応確率推定器１０６、およびライン・インタフェース１０７を含んでいる。シンボルｓ（ｋ）と確率推定ｐ（ｋ）は、算術エンコーダ・ユニット１０４へ供給され、エンコードされたデータストリームａ（ｉ）を作るための周知の方法がそこで用いられる。
【０００７】
そのような算術エンコーダ・ユニットは当技術分野では周知である。「算術コーディングをもつ黒白画像の圧縮」(Compression of Black-White Image with Arithmetic Coding)と題する１９８１年６月発行のＩＥＥＥ Transaction on Communications VOL.cos-29.P858-867の文献、また、２値要素をもつシンボルをエンコード／デコードするための算術エンコーダ／デコーダに関する１９８６年１２月３０日発行の米国特許（ＵＳＰ４，６３３，４９０号）、更に多値の要素を持つシンボルをエンコード／デコードするための算術エンコーダ／デコーダに関する１９８７年６月発行のCommunications of the ACM 第３０巻、第６号、P.520-540の「データ圧縮のための算術コーディング」(Arithmetic Coding for Data Compression)と題する文献などで明らかである。
【０００８】
ライン・インタフェース１０７は、エンコードされたデータストリームａ（ｉ）をインタフェースして、伝送媒体１０２に送り、この伝送媒体１０２は順番に遠隔のデコーダ１０３に供給する。このためライン・インタフェース１０７は、伝送媒体１０２で用いられている信号フォーマットにデータストリームをフォーマッティングするための適切な装置を含んでいる、可能な伝送媒体１０２の良く知られた例としては、Ｔ−搬送トランク、ＩＳＤＮ基礎加入者回線、ローカル・エリア・ネットワークなどがある。その様なライン・インタフェースは、この技術分野では周知である。
文脈抽出器１０５は、受信シンボルｓ（ｋ）の文脈、ここでは
【０００９】
【数２】
0003708744.tif 000003
【００１０】
を得る。即ち、文脈抽出器１０５は、前に供給されたシンボルを基礎にしたシンボルｓ（ｋ）のための独特の文脈（即ち、状態）を生成する。例えば画像圧縮システムを例にすれば、シンボルｓ（ｋ）はエンコードされるべき現在の画素の色を表し、文脈ｃ（ｋ）は上記のごとく前の画素の色によって決められる。例えば、同じラインの現在の画素に隣接し、かつ直前の画素（Ｐ）の色と、現在の画素の直前のライン上の前の画素（Ａ）の色は、２値適用のシンボルｓ（ｋ）のための文脈ｃ（ｋ）を作るために用いられる。このようにして、画素Ｐと画素Ａの双方が白ならばｃ（ｋ）は０であり、画素Ｐが白で画素Ａが黒ならばｃ（ｋ）は１であり、画素Ｐが黒で画素Ａが白ならばｃ（ｋ）は２であり、画素Ｐと画素Ａの双方が黒ならばｃ（ｋ）は３である。米国特許（ＵＳＰ４，６３３，４９０号）には、２進法を用いた別の文脈抽出器（状態作成器）が示されている。この技術の当業者にとっては、いかにしてその様な２進法文脈抽出器が、多値を適用した文脈を得るために拡張されたかは明らかであろう。抽出されて表現された文脈ｃ（ｋ）は適応確率推定器１０６へ供給される。
適応確率推定器１０６は、入力信号
【００１１】
【数３】
0003708744.tif 000004
【００１２】
と関連文脈
【００１３】
【数４】
0003708744.tif 000005
【００１４】
のための確率推定値
【００１５】
【数５】
0003708744.tif 000006
【００１６】
を作るために用いられる。
【００１７】
適応確率推定器１０６は、シンボルカウント型と状態遷移型に大別することが出来る。以下にそれぞれの適応確率推定器について説明する。
【００１８】
（１）シンボルカウント型適応確率推定器
シンボルカウント型適応確率推定器は、シンボルｓ(ｋ)の過去の出現回数から出現確率を算出する方法であり、例えば米国特許（ＵＳＰ５，０２５，２５８号）にその考えが示されている。
【００１９】
シンボルカウント型の適応確率推定器１０６は、次元ＳとＣを持つアレイ（ｎs,c ）を最後まで保持する。ここでアレイの各要素ｎs,c は、文脈ｃの中でのシンボルｓの発生の累積、即ち“カウント”であり、ｓとｃはアレイ中のｎs,c の場所を識別するダミー・インデックスである。適応確率推定器１０６は、コンピュータまたはディジタル信号プロセッサを適切にプログラミングすることによって容易に実現できる。しかし実装のより優れたモードでは、半導体チップの高集積（ＶＬＳＩ）回路の形態にあると想像される。
【００２０】
図１８のフローチャートは、シンボルカウンタ型の適応確率推定器１０６の動作を示している。適応確率推定器１０６の動作は、スタート・ステップ２０１から始まる。次に動作ブロック２０２は、ｋ＝０と、
【００２１】
【数６】
0003708744.tif 000007
【００２２】
とすべきすべての
【００２３】
【数７】
0003708744.tif 000008
【００２４】
と
【００２５】
【数８】
0003708744.tif 000009
【００２６】
に対するｎs,c のカウントを初期化する。ここでＮs,c はある所定値である。操作ブロック２０３は、新しい文脈ｃ（ｋ）を得る。新しい文脈は前に得た文脈と同じであることが注目される。次に動作ブロック２０４は、すべての
【００２７】
【数９】
0003708744.tif 000010
【００２８】
に対して得られた文脈ｃ（ｋ）のためのカウントの合計Ｚを得る。即ち、
【００２９】
【数１０】
0003708744.tif 000011
【００３０】
動作ブロック２０５は、適応確率推定器１０６（図１７）に、算術エンコーダ・ユニット１０４（図１７）へ順番に供給される確率推定値を出力させる。この確率推定値は最初の実行なので、初期条件と得られた文脈ｃ（ｋ）のみを基礎にしている。次の実行では、確率推定は文脈ｃ（ｋ）のためのシンボルｓ（ｋ）の発生カウントの合計、即ち累積を基礎にする。このようにしてステップ２０５は、確率推定値を出力させる。即ち、
【００３１】
【数１１】
0003708744.tif 000012
【００３２】
【数１２】
0003708744.tif 000013
【００３３】
動作ブロック２０６は、エンコードされるシンボルｓ（ｋ）を得る。動作ブロック２０７は、得られたシンボルｓ（ｋ）と文脈ｃ（ｋ）のためのカウントを１だけ増加させる。即ち、
【００３４】
【数１３】
0003708744.tif 000014
【００３５】
は１だけ増加される。
動作ブロック２０８は、パラメータの規定されたセットの少なくとも第１特性と少なくとも第２特性を得る。この例では、パラメータの規定されたセットの各要素は、エンコードされる受信シンボルの文脈に応じる累積、即ちカウントの関数である。即ち、パラメータの所定のセットは、文脈ｃ（ｋ）に対するシンボルｓ（ｋ）の発生を“累積した”出現回数、即ち、ｎ0,c(k)，…，ｎs-1,c(k)である。この例では、少なくとも第１特性は、文脈ｃ（ｋ）に対する累積された出現回数の最小値である。即ち、
【００３６】
【数１４】
0003708744.tif 000015
【００３７】
この例では、少なくとも第２特性は、文脈ｃ（ｋ）に対する累積された出現回数の最大値である。即ち、
【００３８】
【数１５】
0003708744.tif 000016
【００３９】
条件分岐点２０９は、少なくとも第１特性が、少なくとも第１しきい値に等しいかまたは大きいか、即ち、
【００４０】
【数１６】
0003708744.tif 000017
【００４１】
または少なくとも第２特性が、少なくとも第２しきい値に等しいかまたは大きいか、即ち、
【００４２】
【数１７】
0003708744.tif 000018
【００４３】
を決めるために試験する。
少なくとも第１特性（ＭＩＮ）の使用は、適応確率推定器１０６（図１７）の適応の程度の最適化を可能にするということが重要である。この例では前述したＭＩＮである少なくとも第１の特性と、８である小さいしきい値Ｔ1 を使うことにより解決する。このようにして従来では、文脈ｃ（ｋ）に対する各可能な信号発生、即ち（０，…，Ｓ−１）は、
【００４４】
【数１８】
0003708744.tif 000019
【００４５】
の条件を満たすには少なくとも８回発生しなければならない。その結果、少なくとも第１特性ＭＩＮと少なくとも第１のしきい値Ｔ1 ＝８の使用は、評価されている実際の確率値に理想的に適合する適応速度を作る。この例での範囲を制限すると解釈されないために、２進法の適用と１／２に評価されている確率を例にとれば、累積された発生は文脈ｃ（ｋ）をほぼ
【００４６】
【数１９】
0003708744.tif 000020
【００４７】
回参照された後に調整される。１／４に評価されている確率に対しては、文脈ｃ（ｋ）をほぼ
【００４８】
【数２０】
0003708744.tif 000021
【００４９】
回参照された後に、累積された発生は調整され、１／８に評価されている確率に対しては、文脈ｃ（ｋ）をほぼ
【００５０】
【数２１】
0003708744.tif 000022
【００５１】
回参照された後に、累積された発生は調整される。このようにして適応速度は、評価されているより大きい（小さくない）確率値に対しては速くなり、評価されているより小さい確率値に対しては必然的に遅くなる。適応速度の調整はステップ２０９と２１０から明らかである。
【００５２】
この例のＭＡＸである少なくとも第２の特性は、少なくとも第２のしきい値Ｔ2 と関連して、文脈ｃ（ｋ）の中のシンボルｓ（ｋ）の発生の累積中でのオーバーフローを防ぐために用いられる。評価されている確率が異常に小さい値でさえなければ、ＭＡＸはパラメータ調整を要する特性とはならない。一例をあげれば、Ｔ2 の値は２０４８である。それはパラメータのセットの別の特性が用いられることを意味する。例えばステップ２０４で得られた合計ＺがＭＡＸの代わりに用いられる。
このようにして、条件式
【００５３】
【数２２】
0003708744.tif 000023
【００５４】
または式
【００５５】
【数２３】
0003708744.tif 000024
【００５６】
のどちらかが満たされると、ステップ２０９に戻って、動作ブロック２１０は文脈ｃ（ｋ）中に累積されたシンボル要素の調整を行う。適応速度の調整は、調整の原因となるステップ２０９と関連してステップ２１０によって実現され、例えば、すべての
【００５７】
【数２４】
0003708744.tif 000025
【００５８】
に対する文脈ｃ（ｋ）のための累積された発生の次式でセットされたいわゆる半減化により、表示された累積、即ちカウントを決める。
【００５９】
【数２５】
0003708744.tif 000026
【００６０】
従来では、式ＭＩＮＴ1 または式ＭＡＸＴ2 のどちらかの条件を満たすときに、カウントは同じ方法で調整されるが、ある種の適用に対しては、カウントを上記条件のそれぞれに対して別々に調整したほうが便利であろう。一旦、カウントが調整されると、それが累積された発生の表示となることに注意する必要がある。この累積された発生の調整は、確率推定を文脈ｃ（ｋ）中のより新しい発生にもつと従属される。上述のごとく、ＭＩＮＴ1 に従って発生する累積された発生の調整を行うことにより、適応の程度は評価されている実際の確率に理想的に合致する。即ちＭＡＸＴ2 に応答して発生する文脈ｃ（ｋ）中のシンボルｓ（ｋ）の累積された発生の調整は、非常に小さい確率値が推定されている稀な状況で、可能な算術オーバーフロー条件を保護することである。
【００６１】
その後、条件分岐点２１１は、シンボルｓ（ｋ）がエンコード／デコードする最後のシンボルかどうかを決めるために試験する。エンコードされるべきシンボルの数は通常既知である。もし既知でなければシンボルの数の表示が適応確率推定器１０６へ供給される。もしステップ２１１の試験結果がＹＥＳなら、適応確率推定器１０６の要素の動作は、ＥＮＤ・ステップ２１２を経て終了する。もしステップ２１１の試験結果がＮＯなら、ステップ２１３で１を加えた増分インデックスｋが作られ、制御はステップ２０３に戻され、ステップ２１１がＹＥＳになるまで、ステップ２０３から２１１への適切な動作が繰り返される。
【００６２】
（２）状態遷移型適応確率推定器
状態遷移型適応確率推定とは、予めそれぞれに対応する確率を持った複数の状態を設定しておき、ある規則に基づき状態間を遷移することにより、現在、滞在する状態の確率を推定確率とする確率推定方式である。例えば、日本国特許  特公平８−３４４３３号公報にその考え方が述べられている。シンボルカウント型確率推定では、文脈ｃ(ｋ)毎にシンボルｓ(ｋ)の累積出現頻度を記憶するメモリや確率を計算するための割り算が必要なのに対し、状態遷移型は、各状態に対する推定確率を示す表を参照することで確率が推定できるため、一般に簡易で、高速な処理が可能という特長がある。
【００６３】
ここでの例では、入力データは２値データ、つまり
【数２６】
0003708744.tif 000027
【００６４】
とし、出現確率が他方のシンボルより高いと推定されるシンボル(優勢シンボル)の出現確率PMPSと出現確率が低いと推定されるシンボル(劣勢シンボル)の出現確率ＰLPSを推定するものとする。この例では、状態は１７状態とし、図２０の表のように、各状態に対する推定劣勢シンボル出現確率Ｑ（Ｉ）、遷移優勢シンボル出現頻度Ｇ（Ｉ）を予め設定しておく。また、確率推定器は、文脈ｃ毎に、その時点での状態の状態インデックスＩc(０≦Ｉc≦１６)、優勢シンボルの値ＭＰＳc(０または１)、現在の状態で発生した優勢シンボルの頻度mMPS cを記憶しておく必要がある。
【００６５】
図１９のフローチャートは、状態遷移型の適応確率推定器１０６の動作を示している。スタートステップ３０１から始まり、ステップ3０２では、入力データのインデックスｋをｋ＝０とすると共に、各文脈毎の変数、つまり状態インデックスIc、優勢シンボル値ＭＰＳc、優勢シンボルの出現頻度mMPS cをそれぞれ０に初期化する。次に、ステップ３０３で新しい文脈ｃ（ｋ）を得た後、ステップ３０４で、ｃ（ｋ）に応じた各シンボルの推定出現確率を算出する。状態遷移型確率推定では、各文脈ｃ（ｋ）に対応する状態の状態インデックスＩcが記憶されているので、その状態インデックスに対応する劣勢シンボルの推定確率PLPS（ｋ）＝Ｑ（Ｉc）が、図２０の表を参照することにより得られる。このように、表を参照することで推定確率が得られるので、除算が必要なシンボルカウンタ型確率推定に比べて、確率推定の処理は一般に簡易となる。また、この例では２値情報源を対象としているので、優勢シンボルの推定出現確率PMPS(k)＝1- PLPS(k)も容易に算出でき、これらの確率は算術エンコーダユニット１０４に出力される。
【００６６】
確率推定用の変数の更新は以下のように行う。ステップ３０５で得られた新シンボルｓ（ｋ）と、文脈ｃ（ｋ）に対応する優勢シンボルの値ＭＰＳcを条件分岐点３０６で比較し、新シンボルが優勢シンボルか劣勢シンボルかを判断する。
【００６７】
新シンボルが優勢シンボルの場合は、ステップ３１１において、優勢シンボルの出現頻度ｍMPS cに１を加える。ここで、条件分岐点３１２において、優勢シンボルの出現頻度ｍMPS cが各状態毎に定められた遷移ＭＰＳ出現頻度G（Ｉ）に達したと判断されたならば、まず、操作ブロック３１３において、優勢シンボルの出現頻度ｍMPS cを０にリセットする。そして、その時点での状態インデックスＩcが最大値ＩMAX(この例では、１６)でなければ、その文脈の状態インデックスを１段階上げる。また、条件分岐点３１２において、優勢シンボルの出現頻度ｍMPS cが各状態毎に定められた規定頻度G（Ｉ）に達していないと判断された場合には、上記処理(３１３〜３１５)は行われない。
【００６８】
新シンボルが劣勢シンボルの場合は、ステップ３０７において、優勢シンボルの出現頻度ｍMPS cを０にリセットする。ここで、状態インデックスが最小値(＝０)でなければ、ステップ３０９において、状態インデックスを一段階下げる。状態インデックスが最小値の場合には、優勢シンボルの値ＭＰＳcを反転、つまりＭＰＳc=1-ＭＰＳcとする。以上の更新アルゴリズムによる状態遷移により、出現したシンボルに応じて、推定確率が更新されることになる。
【００６９】
その後、条件分岐点３１６は、シンボルｓ（ｋ）がエンコード／デコードする最後のシンボルかどうかを決めるために試験する。エンコードされるべきシンボルの数は通常既知である。もし既知でなければシンボルの数の表示が適応確率推定器１０６へ供給される。もしステップ３１６の試験結果がＹＥＳなら、適応確率推定器１０６の要素の動作は、ＥＮＤ・ステップ３１７を経て終了する。もしステップ３１６の試験結果がＮＯなら、ステップ３１８で１を加えた増分インデックスｋが作られ、制御はステップ３０３に戻され、ステップ３１６がＹＥＳになるまで、ステップ３０３から３１５までの適切な動作が繰り返される。
【００７０】
以上が、シンボルカウント型適応確率推定器あるいは状態遷移型適応確率推定器と算術エンコーダユニット１０６動作の概要である。
【００７１】
デコーダ１０３は、ライン・インタフェース１０８、算術デコーダ・ユニット１０９、文脈抽出器１１０、および適応確率推定器１１１を含んでいる。ライン・インタフェース１０８はライン・インタフェース１０７の逆の機能を行い、データストリームｓ（ｉ）を得るために、既知の方法で入力信号をデフォーマットする。算術デコーダ・ユニット１０９は、算術エンコーダ・ユニット１０４の逆の機能を行う。このため、受信したデータストリームａ（ｉ）と適応確率推定器１１１からの確率推定は算術デコーダ・ユニット１０９へ供給され、シンボルｓ（ｋ）を得るために既知の方法でそこで使われる。
【００７２】
そのような算術デコーダユニットはこの技術分野では周知である。これは、前に引用した“算術コーディングの圧縮黒白画像”(Compression of Black-White Image with Arithmetic Coding)と題する文献および２値適用の米国特許（ＵＳＰ４，６３３，４９０号）、および多値適用の“データ圧縮用算術コーディング”(Arithmetic Coding for Data Compression)と題する文献に述べられている。文献抽出器１１０は構造も動作も１０５と同一なので説明を省く。同様に１１１も１０６と同一なので説明を省く。
【００７３】
従来例２．
従来例２では、２値シンボルの符号化／復号方法として、米国特許（４１９１９７４号）に示される符号化／復号方法をとりあげる。
【００７４】
この符号化／復号方法では、図２１に示すように、１つ又は複数の２値シンボル列に対して１つの符号語を割り当てる。つまり、符号化は、ある一定数（以下、この一定数を符号次数という）の連続した優勢シンボルが出現した場合、或いは、劣勢シンボルが出現した場合に符号語が確定し、その符号語を出力する。この際、連続する優勢シンボルの数は、符号器内部（又は外部）の優勢シンボルカウンタによって計数され、優勢シンボルの値は、優勢シンボルメモリに記憶され、状態番号（後述）は、状態番号メモリ（図示せず）に記憶される。
【００７５】
符号次数は、任意の自然数を取ることが可能であるが、この例では、２n （２のｎ乗）に限定して説明する。優勢シンボルの連続出現数（優勢シンボルカウンタの値）が、符号次数と等しくなった場合には、符号次数と等しい数の連続した優勢シンボルに対して１ビットの符号語“０”を割り当てる。また、優勢シンボルの連続出現数が符号次数と等しくなる以前に劣勢シンボルが出現した場合には、直前に符号語を出力してからその劣勢シンボルが出現するまでの優勢シンボルの連続出現数を、ｎビットの２進数で表し、そのｎビットの２進の先頭に優勢シンボルのみの符号語“０”と区別するための１ビットの“１”を加えた（ｎ＋１）ビットの符号語を、いくつかの優勢シンボルとひとつの劣勢シンボルからなるシンボル列に対して割り当てる。符号語が割り当てられる２値シンボル列の単位を、以下メッセージという。符号語が確定し、符号語が出力されると同時に、優勢シンボルカウンタがリセットされる。このように、出力された各符号語を、一連の系列として出力したものが符号となる。一方、符号を復号する場合は、入力される符号を符号語に分解し、復号器毎に２値シンボル列を復元し、画素を再現することによって行われる。
【００７６】
上述した符号化／復号方法では、符号次数を過去の２値シンボル系列から推定される０／１の出現確率に応じて適切な値に切り換えることによって、更に優れた符号化効率を実現することができる。
【００７７】
この次数決定に状態遷移型確率推定を使った第一の例を次に示す。
符号器／復号器が２値シンボル系列を符号化／復号する場合、図２２に示す３２状態のいずれかの状態にあり、その状態に応じて符号次数が定まる。符号器／復号器における状態番号の初期値は、０とする。また、符号化／復号処理開始時において、各符号器／復号器の優勢シンボルカウンタはリセットされる。符号器／復号器は、符号化／復号処理中に符号語が確定するとき状態遷移を実行する。優勢シンボルの連続出現数が符号次数と等しくなった場合には、状態番号を１つ上げる。優勢シンボルの連続出現数が符号次数と等しくなる以前に劣勢シンボルが出現した場合には、状態番号を１つ下げる。ただし、状態番号３１で優勢シンボルの連続出現数が符号次数と等しくなった場合、或いは、状態番号０で劣勢シンボルが出現した場合、符号器／復号器は、状態を遷移させずにそのままとする。
【００７８】
次に符号次数を決定する第二の例として、シンボルカウンタ型確率推定を使った方式、つまり、２値シンボル系列に出現した０、１の個数ｎ0，ｎ1を送受信側で同一範囲（例えば、１ライン）で計数し、その計数結果に基づいて、符号次数を計算する方式を示す。この符号次数を決定する方式は、例えば、米国特許（ＵＳＰ４１９１９７４号：対応日本国特許  特公昭５９−２７５０１号公報）に示されている。その計算方式は、２n+1ｎ1＞ｎ0≧２nｎ1による。ただし、状態遷移先となる符号次数２n は、既定最高値以下で既定最低値以上とする。
【００７９】
図２１の符号化方式については、次のような性質が知られている。即ち、２つのシンボル“０”，“１”の出現確率が、それぞれｐ，１−ｐ（ｐ≧１／２）なる２値情報源を図２１の方式で符号化するとき、シンボルの出現形態を任意としたときの各次数における最大符号長を最小にするｎは、次式を満たすものである。
【００８０】
【数２７】
0003708744.tif 000028
【００８１】
従って、上式よりｎを定めれば、ほぼ最適な符号次数が選択できる。
ここで、２値シンボルの計数値、即ち、“０”の計数値をｎ0、“１”の計数値をｎ1とすると、
【００８２】
【数２８】
0003708744.tif 000029
【００８３】
であるから、上式より、
【００８４】
【数２９】
0003708744.tif 000030
【００８５】
となる。つまり、シンボルカウンタ型確率推定では、ｎ1を２倍することを繰り返し、その数値がｎ0を最初に越えた時点で、２倍した回数を次数選択に用いればよい。
【００８６】
【発明が解決しようとする課題】
従来技術のシンボルカウンタ型確率推定は高い劣勢シンボル出現確率を持つ情報源に対し高い符号化性能を有するが、低い劣勢シンボル出現確率を持つ情報源に対しては大きく性能が劣化する。一方、状態遷移型確率推定は、低い劣勢シンボル出現確率を持つ情報源に対してもある程度の性能を維持するものの、高い劣勢シンボル出現確率では、シンボルカウンタ型よりも性能が劣るという問題点があった。
【００８７】
この発明は、以上のような問題点を解決するためになされたものであり、幅広いシンボル出現確率を有する情報源に対しても、常に高い符号化効率を実現することを目的とする。
【００８８】
【課題を解決するための手段】
この発明に係る適応確率推定方法は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順を選択する確率推定判定手順とを備えている。
【００８９】
また、シンボルカウンタ型確率推定手順は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手順に記憶させる累積出現頻度記憶手順と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。
【００９０】
さらに、状態遷移型確率推定手順は、カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。
【００９１】
また、他の発明に係る適応符号化方法は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法を用いて情報源シンボルを符号化する適応符号化方法において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順を選択する確率推定判定手順と、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順により推定された出現確率あるいは出現確率に相当する指標を用いて情報源シンボルを符号化する符号化手順とを備えている。
【００９２】
また、シンボルカウンタ型確率推定手順は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手順に記憶させる累積出現頻度記憶手順と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。
【００９３】
さらに、状態遷移型確率推定手順は、カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。
【００９４】
また、他の発明に係る適応復号方法は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法を用いて、符号化された情報源シンボルを復号する適応復号方法において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順を選択する確率推定判定手順と、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順により推定された出現確率あるいは出現確率に相当する指標を用いて、符号化された情報源シンボルを復号する復号手順とを備えている。
【００９５】
また、シンボルカウンタ型確率推定手順は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手順に記憶させる累積出現頻度記憶手順と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。
【００９６】
さらに、状態遷移型確率推定手順は、カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。
【００９７】
また、他の発明に係る適応確率推定装置は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段を選択する確率推定判定手段とを備えている。
【００９８】
また、シンボルカウンタ型確率推定手段は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手段に記憶させる累積出現頻度記憶手段と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。
【００９９】
また、状態遷移型確率推定手段は、カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。
【０１００】
また、他の発明に係る適応符号化装置は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置を用いて情報源シンボルを符号化する適応符号化装置において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段を選択する確率推定判定手段と、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段により推定された出現確率あるいは出現確率に相当する指標を用いて情報源シンボルを符号化する符号化手段とを備えている。
【０１０１】
また、シンボルカウンタ型確率推定手段は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手段に記憶させる累積出現頻度記憶手段と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。
【０１０２】
さらに、状態遷移型確率推定手段は、カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。
【０１０３】
また、他の発明に係る適応復号装置は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置を用いて、符号化された情報源シンボルを復号する適応復号装置において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段を選択する確率推定判定手段と、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段により推定された出現確率あるいは出現確率に相当する指標を用いて、符号化された情報源シンボルを復号する復号手段とを備えている。
【０１０４】
また、シンボルカウンタ型確率推定手段は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手段に記憶させる累積出現頻度記憶手段と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。
【０１０５】
さらに、状態遷移型確率推定手段は、カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。
【０１０６】
【発明の実施の形態】
実施の形態１．
実施の形態の符号化の一例として、２値データに対するエントロピー符号器として、算術符号器を適用する際の符号化処理手順を示す。
なお、優勢シンボルの領域を下方配置し、符号を有効領域の下界値座標として符号化する。このとき演算精度は２進小数１６ビットで打ち切り、整数部を符号出力とするものとする。
【０１０７】
また、本実施の形態１においては、従来技術の図１７の適応確率推定器１０６と算術エンコーダユニット１０４の処理について説明する。ただし、本実施の形態においては、図１に示すように、適応確率推定器１０６が２つの確率推定器（３５１、３５２）を有し、それらを確率推定切換器３５０（確率推定判定手段）が適応的に切り換えていることが大きな特徴である。ここでは、第一の確率推定器３５１に従来の技術に示したシンボルカウンタ型確率推定（シンボルカウンタ型確率推定手段）を、第二の確率推定器３５２としては、従来の技術に示した状態遷移型確率推定（状態遷移型確率推定手段）を使用している。適応確率推定器１０６と算術エンコーダユニット１０４以外の図１７のエンコーダの構成要素は本実施の形態においても用いることは周知であるので、説明を省略する。ここであえて述べておくが、他の実施の形態においても、図１７のエンコーダの他の構成を用いることは周知である。
【０１０８】
また、本説明で用いる変数は、次の通りである。
Ｃは符号値、
Ａは領域幅値、
ＡＬは劣勢シンボル領域幅値、
ＭＰＳは優勢シンボル値、、
Ｓは入力シンボル値、
ＮLPSは劣勢シンボルの出現頻度（カウンタ）、
ＮTは両シンボル（０、１）の出現頻度（カウンタ）、
ＭLPSはＭＰＳの連続出現頻度（カウンタ）、
Ｉは状態インデックス、
Ｇ（Ｉ）は、状態インデックスＩの状態の遷移優先シンボル出現頻度、
Ｐは劣勢シンボルの出現確率、
ＦＬＡＧは、その時点で選択している確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグである。
【０１０９】
更にまた、処理手順における定数は、次の通りである。
ＮMAXは、ＮTの計数最大値、
ＮMINは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移る場合のＮLPSの値、
ＩBは、状態遷移型確率推定での最小状態インデックス、
ＮLPSBは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移った直後のＮLPSの値、
ＮTBは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移った直後のＮTの値。
【０１１０】
本実施の形態における符号化処理手順は、次の図２、図３、図４、図５、図６による。図２は図１７の適応確率推定器１０６と算術エンコーダユニット１０４の処理に基づく２値データの算術符号化の処理手順を示すフローチャートである。このフローチャートにおいて、４００はシンボルカウンタ型確率推定のために、優勢シンボル値ＭＰＳ、劣勢シンボル出現頻度ＮLPS，両シンボル出現頻度ＮT、確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧの初期化を行う。４０１は符号値Ｃ、領域幅Ａの初期化を行う。４０２は、シンボルＳを得て、劣勢シンボルの出現確率ＰをＧＥＴＰＲＯＢの呼び出しにより算出する。４０３は、全体の領域幅値Ａに劣勢シンボルの出現確率Ｐを乗算して劣勢シンボルに対応する領域幅値ＡＬを算出する。４０４は、シンボルＳが優勢シンボルか否かを判定する。
【０１１１】
４０４の判定がＹＥＳならば、４０５は、領域幅値Ａを優勢シンボルに対応する領域幅値（Ａ−ＡＬ）に更新するが、符号値Ｃは優勢シンボルが下方配置なので更新は行わない。４０６は、更新された領域幅値Ａが０．５より小さいならば、４０７のＲＥＮＯＲＭＡＬＩＺＥの呼び出しによって０．５以上となるまで領域幅値Ａ、符号値Ｃを２のべき乗倍する正規化処理を行う。４０８は、ＵＰＤＡＴＥＭＰＳの呼び出しによって確率推定のための変数を更新する。
【０１１２】
また、４０４の判定がＮ０ならば、４０９は、下方の優勢シンボルに対応する領域値（Ａ−ＡＬ）を領域下界値である符号値Ｃに加え、また領域幅値Ａを劣勢シンボルに対応する領域幅値ＡＬに更新し、このとき領域幅値Ａが０．５より必ず小さくなるためＲＥＮＯＲＭＡＬＩＺＥの呼び出しによって０．５以上となるまで領域幅値Ａ、符号値Ｃを２のべき乗倍する正規化処理を行う。４１０は、ＵＰＤＡＴＥＬＰＳの呼び出しによって確率推定のための変数を更新する。
【０１１３】
４１１は、処理したシンボルＳが最後か否かを判定し、最後でなければ４０２から４１０の処理を繰り返させる。４１２は、符号化の後処理で、符号値Ｃの小数部（精度ＦＬＵＳＨＢＩＴ＝１６）の１６ビットを２の１６乗倍して整数部に出力させる。要するに、ディジタル信号（データ信号）の符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、数直線上の所定の範囲に対応させ、その数直線上の座標を符号語として出力する。なお、この符号化の一般的内容については特公平８−３４４３４に詳細に記載されている。
【０１１４】
図３は、劣勢シンボルの出現確率Ｐを算出するＧＥＴＰＲＯＢの処理手順である。４２０は、その時点で使用すべき確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧに応じて、劣勢シンボルの出現確率Ｐの算出方法を切り換える（確率推定判定手順）。つまり、ＦＡＬＧ＝０ならば、４２１でシンボルカウンタ型確率推定方式により劣勢シンボルの出現確率Ｐを算出し（シンボルカウンタ型確率推定手順）、ＦＬＡＧ＝１ならば、４２２で状態遷移型確率推定方式により図２０の表に基づき劣勢シンボルの出現確率Ｐを算出する（状態遷移型確率推定手順）。
【０１１５】
図４は、算術符号化変数の正規化処理ＲＥＮＯＲＭＡＬＩＺＥの処理手順である。４３０は、領域幅値Ａ、符号値Ｃを２倍する。４３１は、領域幅値Ａが０．５より小さいならば、０．５以上となるまで４３０の処理を繰り返させる。ここで、領域幅値Ａ、符号値Ｃを同時に２倍するごとに小数部から整数部に符号が１ビット出力される（符号化手順）。
【０１１６】
図５は、劣勢シンボルが出現した場合に確率推定のための変数を更新するＵＰＤＡＴＥＬＰＳの処理手順である。４４０は、その時点で使用すべき確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧに応じて、変数の更新方法を切り換える。つまり、ＦＬＡＧ＝０ならば、シンボルカウンタ型確率推定のための変数を更新し、ＦＬＡＧ＝１ならば、状態遷移型確率推定のための変数を更新する。
【０１１７】
ＦＬＡＧ＝０の場合、４４１は、劣勢シンボルの出現頻度カウンタＮLPSおよび両シンボルの出現頻度カウンタＮTに、それぞれ１を加える（累積出現頻度カウント手順）。４４２は、両シンボルの出現頻度カウンタＮTが、予め規定された最大値ＮMAXに達したか否かを判断し、最大値ＮMAXに達したならば４４３によって、ＮLPS、ＮTをそれぞれ、（ＮLPS＋１）／２、（ＮT＋１）／２に半減させる（半減手順）。次に、４４４は、４４１から４４３の処理により、現在劣勢シンボルとみなしているシンボルが優勢シンボルになっていないかを判断する。もし、ＮT＜ＮLPS×２ならば、４４５は、ＮLPSに、ＮT−ＮLPSを代入すると共に、優勢シンボル値ＭＰＳの値を反転し、優勢シンボルと劣勢シンボルを入れ換える。
【０１１８】
ＦＬＡＧ＝１の場合、４５０は、優勢シンボルの連続出現頻度ＭMPSを０にリセットし、状態インデックスＩを一段階下げる。４５１は、状態インデックスＩが、シンボルカウンタ型から状態遷移型に移行した直後の状態インデックスＩB未満の値となったか否かを判断する。最小値ＩB未満の値とならなければ、これ以降も確率推定は状態遷移型で続けられる。もし、最小値ＩB未満の値となったならば、確率推定方式は状態遷移型からシンボルカウンタ型に変更される。そのために、４５２は、劣勢シンボルの出現頻度ＮLPS、両シンボルの出現頻度ＮTを定数ＮLPSB、ＮTBに再度設定し直す。さらに、４５３は、使用する確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧを０に設定する。
【０１１９】
図６は、優勢シンボルが出現した場合に確率推定のための変数を更新するＵＰＤＡＴＥＭＰＳの処理手順である。４６０は、その時点で使用すべき確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧに応じて、変数の更新方法を切り換える。つまり、ＦＬＡＧ＝０ならば、シンボルカウンタ型確率推定のための変数を更新し、ＦＬＡＧ＝１ならば、状態遷移型確率推定のための変数を更新する。
【０１２０】
ＦＬＡＧ＝０の場合、４６１は、両シンボルの出現頻度カウンタＮTに１を加える。４６２は、両シンボルの出現頻度カウンタＮTが、予め規定された最大値ＮMAXに達したか否かを判断する。最大値ＮMAXに達していなければ、ＵＰＤＡＴＥＭＰＳの処理は終了し、これ以降も確率推定はシンボルカウンタ型で行われる。最大値ＮMAXに達した場合には、さらに４６３が、その劣勢シンボルの出現頻度ＮLPSが予め設定された最小値ＮMIN以下か否かを判断する。ＮLPSがＮMINよりも大きければ４６４によって、ＮLPS、ＮTをそれぞれ、（ＮLPS＋１）／２、（ＮT＋１）／２に半減させ、これ以降も確率推定はシンボルカウンタ型で行われる。ＮLPSがＮMIN以下の場合には、確率推定方式はシンボルカウンタ型から状態遷移型に変更される。そのために、４６５は、状態インデックスＩを、定数ＩBに設定し、優勢シンボルの連続出現頻度ＭMPSを０にリセットする。更に、４６６は、使用する確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧを１に設定する。
【０１２１】
ＦＬＡＧ＝１の場合、４７０は、優勢シンボルの連続出現頻度ＭMPSに１を加える。４７１は、優勢シンボルの連続出現頻度ＭMPSが図２０の表に示した遷移優勢シンボル出現頻度Ｇ（Ｉ）に達したか否かを判断する。遷移優勢シンボル出現頻度Ｇ（Ｉ）に達していない場合には、ＵＰＤＡＴＥＭＰＳの処理は終了する。優勢シンボルの連続出現頻度ＭMPSが遷移優勢シンボル出現頻度Ｇ（Ｉ）に達した場合には、４７２において、優勢シンボルの連続出現頻度ＭMPSを０にリセットする。そして、その時点での状態インデックスＩが最大値ＩMAX(この例では、１６)でなければ、４７４において状態インデックスＩを１段階引き上げる。
【０１２２】
図７は本発明による確率推定の適応化の様子を示している。図の左半分は、シンボルカウンタ型確率推定における、劣勢シンボル／優先シンボル出現に伴う推定劣勢シンボル出現確率の推移を示している（四角で囲んだ数値が推定劣勢シンボル出現確率＝劣勢シンボル出現頻度／両シンボル出現頻度。ただし、NMAX=256, NMIN=1, IB=8, NLPSB=1, NTB=128としている）。シンボルカウンタ型確率推定での推定劣勢シンボル出現確率が１／２５５である時に、優勢シンボルが出現すると、確率推定方式は図の右半分に示す状態遷移型に変わる。楕円が各状態を表しており、楕円内の数値がその状態での推定劣勢シンボル出現確率を示している。本実施の形態で述べた状態遷移型確率推定では、複数個の連続した優勢シンボルの出現あるいは１個の劣勢シンボルの出現に伴い、図に示すように状態が遷移する。
【０１２３】
上記説明した処理手順はシングルコンテクストを仮定して説明しているが、マルチコンテクストで扱うとき、４０２でシンボルＳと同時にコンテクストＣＸを得てそれをインデクスとする配列（テーブル）として対応すればよい。  例えば、ＭＰＳ（ＣＸ）は、優勢シンボル値、ＮLPS（ＣＸ）は、劣勢シンボルの出現頻度（カウンタ）、ＮT（ＣＸ）は両シンボルの出現頻度（カウンタ）、ＭMPS（ＣＸ）は、優勢シンボルの連続出現頻度（カウンタ）、Ｉ（ＣＸ）は状態インデックスとする。
【０１２４】
上記説明での算術符号化部は優勢シンボルを劣勢シンボルに対して下位配置としているが、上位配置でも構わない。また、与えられる２値データに対して算術符号化部に２値算術符号化を適用しているが、多値データが与えられる場合には多値算術符号化に置き換えて適用できる。さらに、最終符号値から最小有効桁数への修正処理及び終端に続く符号ビット０の省略処理の実行に関わらす、確率推定精度と符号化効率を本質的に向上させる効果に何ら影響を与えるものではない。
【０１２５】
上記説明での算術符号化部として、確率領域の分割に掛け算を使用する算術符号を使用しているが、例えば「ITU-T Recommendation T.82, "Information Technology - Coded Representation of Picture and Audio Information - Progressive Bi-level Image Compression"」などに示されている掛け算を使用しない確率領域分割処理を簡易化した算術符号を適用することも可能である。
【０１２６】
また、上記説明では、シンボルカウンタ型確率推定において、優勢シンボルと両シンボルの累積出現頻度をカウントしているが、優勢シンボルと劣勢シンボルの累積出現をカウントすること、あるいはシンボル０とシンボル１の累積出現頻度をカウントすることも可能である。
【０１２７】
また、上記説明では、状態遷移型確率推定において、表４に示す状態のセットを使ったが、これら以外の状態のセットを使うことも可能である。更に、状態遷移の規則として、その状態で発生したＭＰＳの連続出現頻度に基づいた遷移規則を説明したが、状態遷移型確率推定方式はこれに限らず、例えば「ITU-T Recommendation T.82, "Information Technology - Coded Representation of Picture and Audio Information - Progressive Bi-level Image Compression"」に記載されている算術符号の状態遷移規則などを適用することも可能である。
【０１２８】
劣勢シンボルの出現確率の異なる複数のランダムデータ系列（Ｐ＝２-1〜２-13）を計算機で発生させ、それぞれを実際に本発明を使った算術符号化器で符号化した際の符号化効率（＝エントロピ／符号量）を図８に示す。ただし、それぞれの確率のランダムデータ系列をシングルコンテクストで符号化し、NMAX＝２５６、NMIN＝１、IB＝８、NLPSB＝１、NTB＝１２８としている。また、参考のために、従来の技術で示した確率推定方式、つまりシンボルカウント型確率推定のみを使った場合と状態遷移型確率推定方式のみを使った場合の符号化効率も併せて示した。図８からわかるように、シンボルカウンタ型確率推定は高い劣勢シンボル出現確率を持つシンボルに対し高い符号化性能を有するが、低い劣勢シンボル出現確率を持つシンボルに対しては大きく性能が劣化する。また、状態遷移型確率推定は、低い劣勢シンボル出現確率を持つシンボルに対してもある程度の性能を維持するものの、高い劣勢シンボル出現確率では、シンボルカウンタ型よりも性能が劣っている。これらに対し、本発明による確率推定方式では、幅広い劣勢シンボル出現確率において、従来の確率推定方式と同等かそれ以上の符号化効率を実現していることがわかる。
【０１２９】
実施の形態２．
この実施の形態の復号の一例として、２値データに対するエントロピー復号器として、算術復号器を適用する際の復号処理手順を示す。なお、優勢シンボルの領域を下方配置し、符号は有効領域の下界値座標として復号する。このとき演算精度は２進小数１６ビットで打ち切り、整数部を符号出力とするものとする。
【０１３０】
また、本実施の形態２においては、従来技術の図１７の適応確率推定器１１１と算術デコーダユニット１０９の処理について説明する。ただし、本実施の形態においては、図９に示すように、適応確率推定器１１１が２つの確率推定器（３５６、３５７）を有し、それらを確率推定切換器３５５（確率推定判定手段）が適応的に切り換えていることが大きな特徴である。ここでは、第一の確率推定器３５６に従来の技術に示したシンボルカウンタ型確率推定（シンボルカウンタ型確率推定手段）を、第二の確率推定器３５７には従来の技術に示した状態遷移型確率推定（状態遷移型確率推定手段）を使用している。適応確率推定器１１１と算術デコーダユニット１０９以外の図１７のデコーダの構成要素は本実施の形態においても用いることは周知であるので、説明を省略する。
【０１３１】
また、本説明で用いる変数、Ｃ、Ａ、ＡＬ、ＭＰＳ、ＮLPS、ＮT、ＭLPS、Ｉ、Ｐ、ＦＬＡＧは、実施の形態１と同じなので説明は省略する。変数に関して、実施の形態１との違いは、Ｓが出力シンボル値であること、符号ビットを表す変数ａが新たに加わったことである。
【０１３２】
更にまた、処理手順における定数ＮMAX、ＮMIN、ＩB、ＮLPSB、ＮTBは、実施の形態１と同様なので説明は省略する。
【０１３３】
本実施の形態における復号処理手順は、次の図１０、図１１、図３、図５、図６による。図１０は図１７の適応確率推定器１１１と算術デコーダユニット１０９の処理に基づく２値データの算術符号化の処理手順を示すフローチャートである。このフローチャートにおいて、５００はシンボルカウンタ型確率推定のために、優勢シンボル値ＭＰＳ、劣勢シンボル出現頻度ＮLPS，両シンボル出現頻度ＮT、確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧの初期化を行う。５０１は符号値Ｃ、領域幅Ａの初期化を行う。ここで、領域幅Ａは、符号化時と同様A=1と設定されるが、符号値Ｃについては、符号データａを符号値Ｃのレジスタ長のビット数だけ読み込み、符号値Ｃの初期値として設定する。５０２は、劣勢シンボルの出現確率ＰをＧＥＴＰＲＯＢの呼び出しにより算出する。５０３は、全体の領域幅値Ａに劣勢シンボルの出現確率Ｐを乗算して劣勢シンボルに対応する領域幅値ＡＬを算出する。
【０１３４】
５０４は、優勢シンボルの領域幅Ａ−ＡＬと符号値Ｃの大小を判定する。符号値Ｃの方が小さければ、復号シンボルはＭＰＳとなるので、５０５は、復号シンボル値ＳにＭＰＳを代入する。そして、５０６は、領域幅値Ａを優勢シンボルに対応する領域幅値（Ａ−ＡＬ）に更新するが、符号値Ｃは優勢シンボルが下方配置なので更新は行わない。５０７は、更新された領域幅値Ａが０．５より小さいか否かを判断し、０．５より小さいならば、５０８のＲＥＮＯＲＭ＿ＤＥＣの呼び出しによって０．５以上となるまで領域幅値Ａ、符号値Ｃを２のべき乗倍する正規化処理を行う。５０９は、ＵＰＤＡＴＥＭＰＳの呼び出しによって確率推定のための変数を更新する。
【０１３５】
５０４で、符号値Ｃの方が優勢シンボルの領域幅Ａ−ＡＬより大きいと判断されたならば、復号シンボルは劣勢シンボルとなるので、５１０は、復号シンボル値Ｓに劣勢シンボル値１−ＭＰＳを代入する。そして、５１１は、下方配置されている優勢シンボルに対応する領域値（Ａ−ＡＬ）を符号値Ｃから減算し、また領域幅値Ａを劣勢シンボルに対応する領域幅値ＡＬに更新する。このとき領域幅値Ａが０．５より必ず小さくなるためＲＥＮＯＲＭ＿ＤＥＣの呼び出しによって０．５以上となるまで領域幅値Ａ、符号値Ｃを２のべき乗倍する正規化処理を行う。５１２は、ＵＰＤＡＴＥＬＰＳの呼び出しによって確率推定のための変数を更新する。
【０１３６】
５１３は、復号したシンボルＳが最後か否かを判定し、最後でなければ５００から５１２の処理を繰り返させる。要するに、ディジタル信号（データ信号）の復号にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、数直線上の所定の範囲に対応させ、符号語が示すその数直線上の座標が含まれる領域に対応するシンボルを復号シンボルとする。
【０１３７】
図１１は、算術符号化変数の正規化処理ＲＥＮＯＲＭ＿ＤＥＣの処理手順である。５３０は、領域幅値Ａ、符号値Ｃを２倍する。５３１は、符号データから次に復号すべき符号データを１ビット読み出し、符号値Ｃの最下位ビットに設定する。５３１は、領域幅値Ａが０．５より小さいならば、０．５以上となるまで５３０、５３１の処理を繰り返させる。
【０１３８】
劣勢シンボルの出現確率Ｐを算出するＧＥＴＰＲＯＢの処理手順（図３）、劣勢シンボルが出現した場合に確率推定のための変数を更新するＵＰＤＡＴＥＬＰＳの処理手順（図５）、優勢シンボルが出現した場合に確率推定のための変数を更新するＵＰＤＡＴＥＭＰＳの処理手順（図６）は、実施の形態１と同一であるので説明を省略する。
【０１３９】
なお、上記説明した処理手順はシングルコンテクストを仮定して説明しているが、マルチコンテクストで扱うとき、次の変数を、５０２でＬＰＳ出現確率を推定する前にコンテクストＣＸを得てそれをインデクスとする配列（テーブル）として対応すればよい。例えば、ＭＰＳ（ＣＸ）は、優勢シンボル値、ＮLPS（ＣＸ）は、劣勢シンボルの出現頻度（カウンタ）、ＮT（ＣＸ）は両シンボルの出現頻度（カウンタ）、ＭMPS（ＣＸ）は、優勢シンボルの連続出現頻度（カウンタ）、Ｉ（ＣＸ）は状態インデックスとする。
【０１４０】
上記説明での算術復号部は優勢シンボルを劣勢シンボルに対して下位配置としているが、上位配置でも構わない。また、与えられる２値データに対して算術復号部に２値算術復号を適用しているが、多値データが与えられる場合には多値算術復号に置き換えて適用できる。
【０１４１】
上記説明での算術符号化部として、確率領域の分割に掛け算を使用する算術符号を使用しているが、例えば「ITU-T Recommendation T.82, "Information Technology - Coded Representation of Picture and Audio Information - Progressive Bi-level Image Compression"」などに示されている掛け算を使用しない算術符号を適用することも可能である。
【０１４２】
また、上記説明では、シンボルカウンタ型確率推定において、優勢シンボルと両シンボルの累積出現頻度をカウントしているが、優勢シンボルと劣勢シンボルの累積出現をカウントすること、シンボル０とシンボル１の累積出現頻度をカウントすることなども可能である。
【０１４３】
また、上記説明では、状態遷移型確率推定において、表４に示す状態のセットを使ったが、これら以外の状態のセットを使うことも可能である。更に、状態遷移の規則として、その状態で発生したＭＰＳの連続出現頻度に基づいた遷移規則を説明したが、状態遷移型確率推定方式はこれに限らず、例えば「ITU-T Recommendation T.82, "Information Technology - Coded Representation of Picture and Audio Information - Progressive Bi-level Image Compression"」に記載されている算術符号の状態遷移規則を適用することも可能である。
【０１４４】
実施の形態３．
本実施の形態３においては、従来技術の図１７の算術エンコーダユニット１０４の代わりに図２１で示した２値エントロピー符号化を用いた符号化器を使用している。以下、この２値エントロピー符号化と確率推定の処理をフローチャートを用いて説明する。
【０１４５】
確率推定器は、実施の形態１と同様に、図１に示すよう２つの確率推定器（３５１、３５２）を有し、それらを確率推定切換器３５０が適応的に切り換えている。本実施の形態では、第一の確率推定器３５１にシンボルカウンタ型確率推定を、第二の確率推定器３５２には、状態遷移型確率推定を使用する例を示す。適応確率推定器１０６と算術エンコーダユニット１０４以外の図１７のエンコーダの構成要素は本実施の形態においても用いることは周知であるので、説明を省略する。
【０１４６】
また、本説明で用いる変数は、次の通りである。
ＭＰＳは優勢シンボル値、、
Ｓは入力シンボル値、
ＮLPSは劣勢シンボルの出現頻度（カウンタ）、
ＮMPSは優勢シンボルの出現頻度（カウンタ）、
ＭLPSは優勢シンボルの連続出現頻度（カウンタ）、
Ｉは状態インデックス、
Ｐは劣勢シンボルの出現確率、
ＦＬＡＧは、その時点で選択している確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグ、
ＲＣは、符号次数、
Ｒ（Ｉ）は、状態インデックスＩの状態の符号次数、
Ｊ、ＮTMPは、演算処理に使う一時的な変数である。
【０１４７】
更にまた、処理手順における定数は、次の通りである。
ＮMAXは、ＮMPSあるいはＮLPSの計数最大値、
ＮMINは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移る際のＮLPSの値、
ＩBは、状態遷移型確率推定での最小状態インデックス、
ＮLPSBは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移った直後のＮLPSの値、
ＮMPSBは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移った直後のＮMPSの値。
【０１４８】
本実施の形態における符号化処理手順は、次の図１２、図１３、図１４、図１５による。図１２は、本発明の適応確率推定方式と図２１に示す２値エントロピー符号化の処理手順を示すフローチャートである。このフローチャートにおいて、６００は、優勢シンボル値ＭＰＳ、劣勢シンボル出現頻度ＮLPS，優勢シンボル出現頻度ＮMPS、確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧ、符号次数ＲＣ、優勢シンボル連続出現頻度ＭMPSの初期化を行う。優勢シンボル連続出現頻度ＭMPSとは、前回符号語を出力してから発生した優勢シンボルの出現頻度で、符号語を出力する度に０にリセットされる。
【０１４９】
６０１は、入力シンボルＳを得て、６０２はそのシンボルＳが優勢シンボルか劣勢シンボルかを判定する。６０２の判定がＹＥＳならば、つまり、優勢シンボルが発生したならば、６０３は、優勢シンボル連続出現頻度ＭMPSに１を加える。そして、６０４は、優勢シンボル連続出現頻度ＭMPSが符号次数ＲＣに達したか否かを判断し、達したならば６０６は、１ビットの符号語０を出力する。次に、６０７のＵＰＤＡＴＥＭＰＳ＿ＢＬＫ１の呼び出しにより、符号次数と確率推定のための変数を更新する。６０８は、優勢シンボル連続出現頻度ＭMPSを０にリセットし、次の符号語の出力に備える。
【０１５０】
６０４が優勢シンボル連続出現頻度ＭMPSが符号次数ＲＣに達していないと判断したならば、６０５のＵＰＤＡＴＥＭＰＳ＿ＢＬＫ０の呼び出しにより、確率推定のための変数を更新する。なお、符号次数ＲＣ更新は、符号語を出力したときにだけ行うので、ＵＰＤＡＴＥＭＰＳ＿ＢＬＫ０では、符号次数の更新は行わない。
【０１５１】
次に、６０２で入力シンボルが劣勢シンボルと判断された場合には、６０９が符号を出力する。従来例２の説明で述べられているように、１ビットの１を出力した後、優勢シンボル連続出現頻度ＭMPSをlog2ＲＣ桁の２進数で表現して出力する。この後、６１０のＵＰＤＡＴＥＬＰＳ＿ＢＬＫの呼び出しにより、符号次数と確率推定のための変数を更新し、６０８は優勢シンボル連続出現頻度ＭMPSを０にリセットして次の符号語の出力に備える。
【０１５２】
６１２は、処理したシンボルＳが最後か否かを判定し、最後でなければ６０１から６１１の処理を繰り返させる。
【０１５３】
図１３は、劣勢シンボルが出現した場合に、符号次数と確率推定のための変数を更新するＵＰＤＡＴＥＬＰＳ＿ＢＬＫの処理手順である。６２０は、その時点で使用すべき確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧに応じて、変数の更新方法を切り換える。つまり、ＦＬＡＧ＝０ならば、シンボルカウンタ型確率推定のための変数を更新し、ＦＬＡＧ＝１ならば、状態遷移型確率推定のための変数を更新する。
【０１５４】
ＦＬＡＧ＝０の場合、６２１は、劣勢シンボルの出現頻度カウンタＮLPSに１を加える。６２２は、劣勢シンボルの出現頻度カウンタＮLPSが、予め規定された最大値ＮMAXに達したか否かを判断し、最大値ＮMAXに達したならば６２３によって、ＮLPS、ＮMPSをそれぞれ、（ＮLPS＋１）／２、（ＮMPS＋１）／２に半減させる。次に、６２４は、６２１から６２３の処理により、現在劣勢シンボルとみなしているシンボルが優勢シンボルになっていないかを判断する。もし、ＮMPS＜ＮLPSならば、６２５は、ＮLPSとＮMPSの値を入れ換えると共に、優勢シンボル値ＭＰＳの値を反転する。
【０１５５】
次に、６２６から６２９は符号次数ＲＣの更新を行う。従来例２で述べたように、シンボルカウンタ型確率推定では、ＮLPSを２倍することを繰り返し、その数値がＮMPSを最初に越えた時点で、２倍した回数を次数選択に用いればよい。６２６は、２倍する回数を示すカウンタＪを０にセットする。６２７は、２J+1×ＮLPSとＮMPSの大小を比較し、ＮMPSが小さければ、６２８でＪに１を加え再度、比較を行う。２J+1×ＮLPSよりＮMPSの方が、大きければ、６２９は符号次数ＲＣを２Jに設定する。
【０１５６】
６２０でＦＬＡＧ＝１と判断された場合、つまり状態遷移型確率推定の場合、６３０は、状態インデックスＩを一段階下げる。ここで、６３１は、状態インデックスＩが、シンボルカウンタ型から状態遷移型に移行した直後の状態インデックスＩB未満の値となったか否かを判断する。最小値ＩB未満の値にならなければ、６３４は、状態インデックスＲＣを状態インデックスＩの状態の符号次数Ｒ（Ｉ）に更新し、これ以降も確率推定は状態遷移型で続けられる。
【０１５７】
Ｉが最小値ＩB未満の値となったならば、確率推定方式は状態遷移型からシンボルカウンタ型に変更される。そのために、６３２は、劣勢シンボルの出現頻度カウンタＮLPS、優勢シンボルの出現頻度カウンタＮMPSを定数ＮLPSB、ＮMPSBに再度設定し直す。さらに、６３３は、使用する確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧを０に設定する。そして、６２６から６２９の処理を行い、更新されたＮLPS、ＮMPSに基づく新たな符号次数ＲＣを算出する。
【０１５８】
図１４は、優勢シンボルが出現し、かつ符号語を出力しなかった場合に確率推定のための変数を更新するＵＰＤＡＴＥＭＰＳ＿ＢＬＫ０の処理手順である（符号語を出力しなかった場合には、符号次数ＲＣは更新しない）。６５０は、その時点で使用すべき確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧに応じて、変数の更新方法を切り換える。
【０１５９】
ＦＬＡＧ＝０の場合、状態遷移型確率推定の変数の更新はないため、そのままＵＰＤＡＴＥＭＰＳ＿ＢＬＫ１を終了し、これ以降も同じ符号次数で符号化が行われる。
【０１６０】
ＦＬＡＧ＝１の場合、符号次数は更新しないが、確率推定のための変数ＮMPS、ＮLPSは、更新する必要がある。６５１は、優勢シンボルの出現頻度カウンタＮMPSに１を加える。６５２は、優勢シンボルの出現頻度カウンタＮMPSが、予め規定された最大値ＮMAXに達したか否かを判断する。最大値ＮMAXに達していなければ、ＵＰＤＡＴＥＭＰＳ＿ＢＬＫ０の処理は終了し、これ以降も確率推定はシンボルカウンタ型で行われる。最大値ＮMAXに達した場合には、さらに６５３が、劣勢シンボルの出現頻度ＮLPSが予め設定された最小値ＮMIN以下か否かを判断する。
【０１６１】
ＮLPSがＮMINよりも大きければ、６５５は、ＮLPS、ＮMPSをそれぞれ、（ＮLPS＋１）／２、（ＮMPS＋１）／２に半減させる。ＮLPSがＮMIN以下の場合、算術符号を使用した実施の形態１では確率推定方式がシンボルカウンタ型から状態遷移型に変更されたが、本実施の形態では、符号語出力時のみ確率推定方式の変更を行うため、ここでは変更しない。ただ、これ以降も優勢シンボルの発生が続いて次に符号語が出力された時に状態遷移型へ移れるように、６５４はＮMPSから１を引き、シンボル出現頻度のカウンタをＵＰＤＡＴＥＭＰＳ＿ＢＬＫ０実行前の値に戻しておく。
【０１６２】
図１５は、優勢シンボルが出現し、かつ符号語を出力した場合に符号次数および確率推定のための変数を更新するＵＰＤＡＴＥＭＰＳ＿ＢＬＫ１の処理手順である。６６０は、その時点で使用すべき確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧに応じて、変数の更新方法を切り換える。つまり、ＦＬＡＧ＝０ならば、シンボルカウンタ型確率推定のための変数を更新し、ＦＬＡＧ＝１ならば、状態遷移型確率推定のための変数を更新する。
【０１６３】
ＦＬＡＧ＝０の場合、６６１は、優勢シンボルの出現頻度カウンタＮMPSに１を加える。６６２は、優勢シンボルの出現頻度カウンタＮMPSが、予め規定された最大値ＮMAXに達したか否かを判断する。最大値ＮMAXに達していなければ、６６８〜６７１は、ＵＰＤＡＴＥＬＰＳ＿ＢＬＫの６２６から６２９の処理と同様に、符号次数ＲＣを算出する。そして、ＵＰＤＡＴＥＭＰＳ＿ＢＬＫ１の処理は終了し、これ以降も確率推定はシンボルカウンタ型で行われる。
【０１６４】
６６２で優勢シンボルの出現頻度カウンタＮMPSが最大値ＮMAXに達したと判断された場合には、さらに６６３が、劣勢シンボルの出現頻度カウンタＮLPSが予め設定された最小値ＮMIN以下か否かを判断する。ＮLPSがＮMINよりも大きければ６６７によって、ＮLPS、ＮMPSをそれぞれ、（ＮLPS＋１）／２、（ＮMPS＋１）／２に半減する。更に、ＮLPS、ＮMPSに基づいて６６８から６７１が、符号次数を算出し、これ以降も確率推定はシンボルカウンタ型で行われる。ＮLPSがＮMIN以下の場合には、確率推定方式はシンボルカウンタ型から状態遷移型に変更される。そのために、６６４は、状態インデックスＩを、状態遷移へ変更後の初期状態のインデックスであるＩBに設定し、６６５はその状態の符号次数Ｒ（Ｉ）を符号次数ＲＣに代入する。更に、６６６は、使用する確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧを１に設定する。
【０１６５】
ＦＬＡＧ＝１の場合、６７２は、状態インデックスＩが最大値ＩMAX(図２２の例では、３１)に達したか否かを判断し、達していなければ、６７３は状態インデックスＩを１段階引き上げる。次に、６７４は、符号次数ＲＣを設定し、ＵＰＤＡＴＥＭＰＳ＿ＢＬＫ１の処理は終了する。
【０１６６】
上記説明した処理手順はシングルコンテクストを仮定して説明しているが、マルチコンテクストで扱うとき、６０１でシンボルＳと同時にコンテクストＣＸを得てそれをインデクスとする配列（テーブル）として対応すればよい。例えば、ＭＰＳ（ＣＸ）は、優勢シンボル値、ＮLPS（ＣＸ）は、劣勢シンボルの出現頻度（カウンタ）、ＮMPS（ＣＸ）は優勢シンボルの出現頻度（カウンタ）、ＭMPS（ＣＸ）は、優勢シンボルの連続出現頻度（カウンタ）、Ｉ（ＣＸ）は状態インデックス、ＲＣ（ＣＸ）は符号次数とする。この時、メッセージの先頭符号化シンボルの発生順に符号語を伝送する必要があるが、この符号語の順序制御については、米国特許（ＵＳＰ４１９１９７４号）に記載されている。
【０１６７】
また、上記説明では、シンボルカウンタ型確率推定において、優勢シンボルと劣勢シンボルの累積出現頻度をカウントしているが、優勢シンボルと両シンボル（０と１）の累積出現をカウントすること、あるいはシンボル０とシンボル１の累積出現頻度をカウントすることも可能である。また、上記説明では、状態遷移型確率推定において、表４Ｂに示す３２状態のセットを使ったが、これら以外の状態のセットを使うことも可能である。
【０１６８】
実施の形態４．
本実施の形態４においては、従来技術の図１７の算術デコーダユニット１０９の代わりに図２１で示した符号を用いた復号器を使用している。以下、この２値エントロピー復号と確率推定の処理をフローチャートを用いて説明する。確率推定器は、実施の形態２と同様に、図９に示すよう２つの確率推定器（３５６、３５７）を有し、それらを確率推定切換器３５５が適応的に切り換えている。本実施の形態では、第一の確率推定器３５６にシンボルカウンタ型確率推定を、第二の確率推定器３５７には、状態遷移型確率推定を使用する例を示す。適応確率推定器１１１と算術デコーダユニット１０９以外の図１７のデコーダの構成要素は本実施の形態においても用いることは周知であるので、説明を省略する。
【０１６９】
また、本説明で用いる変数は、次の通りである。
ＭＰＳは優勢シンボル値、、
Ｓは出力シンボル値、
ＮLPSは劣勢シンボルの出現頻度（カウンタ）、
ＮMPSは優勢シンボルの出現頻度（カウンタ）、
ＭLPSは復号したメッセージ内のまだ出力していない劣勢シンボルの個数（カウンタ）、
ＭMPSは復号したメッセージ内のまだ出力していない優勢シンボルの個数（カウンタ）、
Ｉは状態インデックス、
Ｐは劣勢シンボルの出現確率、
ＦＬＡＧは、その時点で選択している確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグ、
ＲＣは、符号次数、
Ｒ（Ｉ）は、状態インデックスＩが示す状態の符号次数である。
【０１７０】
更にまた、処理手順における定数は、次の通りである。
ＮMAXは、ＮMPSあるいはＮLPSの計数最大値、
ＮMINは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移る場合のＮLPSの値、
ＩBは、状態遷移型確率推定での最小状態インデックス、
ＮLPSBは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移った直後のＮLPSの値、
ＮMPSBは、確率推定方式が状態遷移型確率推定からシンボルカウンタ型確率推定に移った直後のＮMPSの値である。
【０１７１】
本実施の形態における符号化処理手順は、次の図１６、図１３、図１４、図１５による。図１６は、本発明の適応確率推定方式と図２１に示す符号を用いた場合の復号処理手順を示すフローチャートである。このフローチャートにおいて、７００は、優勢シンボル値ＭＰＳ、劣勢シンボル出現頻度ＮLPS，優勢シンボル出現頻度ＮMPS、確率推定方式がシンボルカウンタ型か状態遷移型かを示すフラグＦＬＡＧ、符号次数ＲＣ、復号メッセージ内の優勢シンボル個数ＭMPS、劣勢シンボル個数ＭLPSの初期化を行う。
【０１７２】
７０１は、復号メッセージ内のまだ出力していない優勢シンボル個数ＭMPSと劣勢シンボル個数ＭLPSが共に０か否かを判定する。共に０の場合、つまり復号したメッセージを全て出力し終わってしまった場合には、７０２が、符号データから次の符号語を読み込み、図２１の表に従ってその符号語に対応するメッセージを復号し、そのメッセージ内の優勢シンボル個数、劣勢シンボル個数をＭMPS，ＭLPSに設定する。
【０１７３】
７０３は、メッセージ内のまだ出力していない優勢シンボル個数ＭMPSが０より大きいか否かを判断する。０より大きければ、優勢シンボルを出力する。つまり、７０４が復号シンボルＳに優勢シンボルを代入し、７０５は、メッセージ内の優勢シンボル個数ＭMPSから１を減じる。次に、符号次数あるいは確率推定のための変数の更新を行うが、符号次数の更新は復号したメッセージを完全に出力し終わった後だけに行う。そこで、７０６は、復号メッセージ内のまだ出力していない優勢シンボル個数ＭMPSと劣勢シンボル個数ＭLPSが共に０か否か、つまり前回復号したメッセージを完全に出力し終わったか否かを判定する。ＭMPSとＭLPSが共に０ならば、７０８のＵＰＤＡＴＥＭＰＳ＿ＢＬＫ１の呼び出しにより、符号次数と確率推定のための変数を更新する。ＭMPSとＭLPSが共に０でなければ、７０７のＵＰＤＡＴＥＭＰＳ＿ＢＬＫ０の呼び出しにより、確率推定のための変数を更新する。
【０１７４】
次に、７０３でメッセージ内のまだ出力していない優勢シンボル個数ＭMPSが０であると判断された場合には（この場合、ＭLPSは必ず１である）、劣勢シンボルを出力する。つまり、７０９が復号シンボルＳに劣勢シンボルを代入し、７１０は、メッセージ内の劣勢シンボル個数ＭLPSから１を減じる。そして、７１１のＵＰＤＡＴＥＬＰＳ＿ＢＬＫの呼び出しにより、符号次数と確率推定のための変数を更新する。
【０１７５】
７１２は、処理したシンボルＳが最後か否かを判定し、最後でなければ７０１から７１１の処理を繰り返させる。
【０１７６】
劣勢シンボルを出力した後に符号次数、確率推定のための変数を更新するＵＰＤＡＴＥＬＰＳ＿ＢＬＫの処理手順（図１３）、メッセージ内に出力していないシンボルが残っている場合に、確率推定のための変数を更新するＵＰＤＡＴＥＬＰＳ＿ＢＬＫ０の処理手順（図１４）、優勢シンボルのみからなるメッセージ内の全てのシンボルを出力した後、符号次数、確率推定のための変数を更新するＵＰＤＡＴＥＭＰＳ＿ＢＬＫ１の処理手順（図１５）は、実施の形態３と同一であるので説明を省略する。
【０１７７】
上記説明した処理手順はシングルコンテクストを仮定して説明しているが、マルチコンテクストで扱うとき、６０１でシンボルＳと同時にコンテクストＣＸを得てそれをインデクスとする配列（テーブル）として対応すればよい。  例えば、ＭＰＳ（ＣＸ）は、優勢シンボル値、ＮLPS（ＣＸ）は、劣勢シンボルの出現頻度（カウンタ）、ＮMPS（ＣＸ）は優勢シンボルの出現頻度（カウンタ）、ＭMPS（ＣＸ）は、優勢シンボルの連続出現頻度（カウンタ）、Ｉ（ＣＸ）は状態インデックス、ＲＣ（ＣＸ）は符号次数とする。この時、メッセージの先頭符号化シンボルの発生順に符号語を伝送する必要があるが、この符号語の順序制御については、米国特許（ＵＳＰ４１９１９７４号）に記載されている。
【０１７８】
また、上記説明では、シンボルカウンタ型確率推定において、優勢シンボルと劣勢シンボルの累積出現頻度をカウントしているが、優勢シンボルと両シンボル（０と１）の累積出現をカウントすること、あるいはシンボル０とシンボル１の累積出現頻度をカウントすることも可能である。また、上記説明では、状態遷移型確率推定において、表４Ｂに示す３２状態のセットを使ったが、これら以外の状態のセットを使うことも可能である。
【０１７９】
【発明の効果】
この発明に係る適応確率推定方法は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順を選択する確率推定判定手順とを備えている。そのため、幅広いシンボル出現確率を有する情報源に対しても、情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができる。
【０１８０】
また、シンボルカウンタ型確率推定手順は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手順に記憶させる累積出現頻度記憶手順と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。そのため、累積出現頻度の記憶を少なくできると共に、各情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができる。
【０１８１】
さらに、状態遷移型確率推定手順は、カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。そのため、予め設定された複数の状態間を遷移させることにより、情報源シンボルの出現確率あるいは出現確率に相当する指標を推定することができる。
【０１８２】
また、他の発明に係る適応符号化方法は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法を用いて情報源シンボルを符号化する適応符号化方法において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順を選択する確率推定判定手順と、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順により推定された出現確率あるいは出現確率に相当する指標を用いて情報源シンボルを符号化する符号化手順とを備えている。そのため、幅広いシンボル出現確率を有する情報源に対しても、情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い符号化効率を実現する。
【０１８３】
また、シンボルカウンタ型確率推定手順は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手順に記憶させる累積出現頻度記憶手順と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。そのため、累積出現頻度の記憶を少なくできると共に、各情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い符号化効率を実現する。
【０１８４】
さらに、状態遷移型確率推定手順は、カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。そのため、予め設定された複数の状態間を遷移させることにより、情報源シンボルの出現確率あるいは出現確率に相当する指標を推定することができ、常に高い符号化効率を実現する。
【０１８５】
また、他の発明に係る適応復号方法は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定方法を用いて、符号化された情報源シンボルを復号する適応復号方法において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手順と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手順と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手順と、カウント記憶手順に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順を選択する確率推定判定手順と、シンボルカウンタ型確率推定手順または状態遷移型確率推定手順により推定された出現確率あるいは出現確率に相当する指標を用いて、符号化された情報源シンボルを復号する復号手順とを備えている。そのため、幅広いシンボル出現確率を有する情報源に対しても、情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い復号化効率を実現する。
【０１８６】
また、シンボルカウンタ型確率推定手順は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手順に記憶させる累積出現頻度記憶手順と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手順とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。そのため、累積出現頻度の記憶を少なくできると共に、各情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い復号化効率を実現する。
【０１８７】
さらに、状態遷移型確率推定手順は、カウント記憶手順に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手順とを備え、遷移手順は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。そのため、予め設定された複数の状態間を遷移させることにより、情報源シンボルの出現確率あるいは出現確率に相当する指標を推定することができ、常に高い復号化効率を実現する。
【０１８８】
また、他の発明に係る適応確率推定装置は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段を選択する確率推定判定手段とを備えている。そのため、幅広いシンボル出現確率を有する情報源に対しても、情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができる。
【０１８９】
また、シンボルカウンタ型確率推定手段は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手段に記憶させる累積出現頻度記憶手段と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。そのため、累積出現頻度の記憶を少なくできると共に、各情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができる。
【０１９０】
また、状態遷移型確率推定手段は、カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。そのため、予め設定された複数の状態間を遷移させることにより、情報源シンボルの出現確率あるいは出現確率に相当する指標を推定することができる。
【０１９１】
また、他の発明に係る適応符号化装置は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置を用いて情報源シンボルを符号化する適応符号化装置において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段を選択する確率推定判定手段と、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段により推定された出現確率あるいは出現確率に相当する指標を用いて情報源シンボルを符号化する符号化手段とを備えている。そのため、幅広いシンボル出現確率を有する情報源に対しても、情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い符号化効率を実現する。
【０１９２】
また、シンボルカウンタ型確率推定手段は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手段に記憶させる累積出現頻度記憶手段と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。そのため、累積出現頻度の記憶を少なくできると共に、各情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い符号化効率を実現する。
【０１９３】
さらに、状態遷移型確率推定手段は、カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。そのため、予め設定された複数の状態間を遷移させることにより、情報源シンボルの出現確率あるいは出現確率に相当する指標を推定することができ、常に高い符号化効率を実現する。
【０１９４】
また、他の発明に係る適応復号装置は、情報源シンボルの累積出現頻度に基づいて推定される符号化対象シンボルの出現確率あるいは出現確率に相当する指標から符号化パラメータを選択する適応確率推定装置を用いて、符号化された情報源シンボルを復号する適応復号装置において、情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスを記憶するカウント記憶手段と、情報源シンボルの出現頻度に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定するシンボルカウンタ型確率推定手段と、各情報源シンボルの状態間の遷移に基づき、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する状態遷移型確率推定手段と、カウント記憶手段に記憶された情報源シンボルの出現頻度あるいは情報源シンボルの状態のインデックスに基づいて、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段を選択する確率推定判定手段と、シンボルカウンタ型確率推定手段または状態遷移型確率推定手段により推定された出現確率あるいは出現確率に相当する指標を用いて、符号化された情報源シンボルを復号する復号手段とを備えている。そのため、幅広いシンボル出現確率を有する情報源に対しても、情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い復号化効率を実現する。
【０１９５】
また、シンボルカウンタ型確率推定手段は、全情報源シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度あるいは、優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度をカウントし、カウント記憶手段に記憶させる累積出現頻度記憶手段と、各々の累積出現頻度が所定の値に達した場合、累積出現頻度を半減する半減手段とを備え、全情報源シンボルの累積出現頻度と劣勢シンボルの累積出現頻度との比あるいは優勢シンボルの累積出現頻度及び劣勢シンボルの累積出現頻度との比から、各情報源シンボルの出現確率あるいは出現確率に相当する指標を推定する。そのため、累積出現頻度の記憶を少なくできると共に、各情報源シンボルの出現確率あるいは出現確率に相当する指標を確実に推定することができ、常に高い復号化効率を実現する。
【０１９６】
さらに、状態遷移型確率推定手段は、カウント記憶手段に記憶された情報源シンボルのインデックスと出現した情報源シンボルに応じて、情報源シンボルの状態を予め設定された複数の状態間を遷移させることにより推定する遷移手段とを備え、遷移手段は、各情報源シンボルの状態に定められている出現確率あるいは出現確率に相当する指標を、その情報源シンボルの出現確率あるいは出現確率に相当する指標であると推定する。そのため、予め設定された複数の状態間を遷移させることにより、情報源シンボルの出現確率あるいは出現確率に相当する指標を推定することができ、常に高い復号化効率を実現する。
【図面の簡単な説明】
【図１】  本発明の適応確率推定装置を算術エンコーダユニットに用いた場合の要部を示す構成図である。
【図２】  適応確率推定器と算術エンコーダユニットの処理に基づく２値データの算術符号化の処理手順を示すフローチャートである。
【図３】  劣勢シンボルの出現確率Ｐを算出する処理手順を示す図である。
【図４】  算術符号化変数の正規化処理の処理手順を示す図である。
【図５】  劣勢シンボルが出現した場合に確率推定のための変数を更新する処理手順を示す図である。
【図６】  優勢シンボルが出現した場合に確率推定のための変数を更新する処理手順を示す図である。
【図７】  確率推定の適応化の様子を示す図である。
【図８】  劣勢シンボルの出現確率の異なる複数のランダムデータ系列を計算機で発生させ、それぞれを実際に算術符号化器で符号化した際の符号化効率を示す図である。
【図９】  本発明の適応確率推定装置を算術デコーダユニットに用いた場合の要部を示す構成図である。
【図１０】  適応確率推定器と算術デコーダユニットの処理に基づく２値データの算術符号化の処理手順を示すフローチャートである。
【図１１】  算術符号化変数の正規化処理の処理手順を示す図である。
【図１２】  適応確率推定方式と２値エントロピー符号化の処理手順を示すフローチャートである。
【図１３】  劣勢シンボルが出現した場合に、符号次数と確率推定のための変数を更新する処理手順を示す図である。
【図１４】  優勢シンボルが出現し、かつ符号語を出力しなかった場合に確率推定のための変数を更新する処理手順を示す図である。
【図１５】  優勢シンボルが出現し、かつ符号語を出力した場合に符号次数および確率推定のための変数を更新する処理手順を示す図である。
【図１６】  適応確率推定方式と図２１に示す符号を用いた場合の復号処理手順を示すフローチャートである。
【図１７】  従来のエントロピー・エンコーダの簡単化したブロック・ダイヤグラムを示す図である。
【図１８】  シンボルカウンタ型の適応確率推定器の動作を示す図である。
【図１９】  状態遷移型の適応確率推定器の動作を示す図である。
【図２０】  各状態に対する推定劣勢シンボル出現確率Ｑ（Ｉ）、遷移優勢シンボル出現頻度Ｇ（Ｉ）を予め設定しておく例を示す図である。
【図２１】  １つ又は複数の２値シンボル列に対して１つの符号語を割り当てる符号化／復号方法を示す図である。
【図２２】  符号器／復号器が２値シンボル系列を符号化／復号する場合その状態に応じて符号次数が定まる様子を示す図である。
【符号の説明】
４２０  確率推定判定手順、４２１  シンボルカウンタ型確率推定手順、４２２  状態遷移型確率推定手順、４３０  符号化手順、４４１  カウント記憶手順、４４３  半減手順、３５０，３５５  確率推定切換器（確率推定判定手段）、３５１，３５６  第一の確率推定器（シンボルカウンタ型確率推定手段）、３５２，３５７  第一の確率推定器（状態遷移型確率推定手段）。
【図１】
0003708744.tif 000031
【図２】
0003708744.tif 000032
【図３】
0003708744.tif 000033
【図４】
0003708744.tif 000034
【図５】
0003708744.tif 000035
【図６】
0003708744.tif 000036
【図７】
0003708744.tif 000037
【図８】
0003708744.tif 000038
【図９】
0003708744.tif 000039
【図１０】
0003708744.tif 000040
【図１１】
0003708744.tif 000041
【図１２】
0003708744.tif 000042
【図１３】
0003708744.tif 000043
【図１４】
0003708744.tif 000044
【図１５】
0003708744.tif 000045
【図１６】
0003708744.tif 000046
【図１７】
0003708744.tif 000047
【図１８】
0003708744.tif 000048
【図１９】
0003708744.tif 000049
【図２０】
0003708744.tif 000050
【図２１】
0003708744.tif 000051
【図２２】
0003708744.tif 000052