【手続補正書】
【提出日】平成17年7月25日(2005.7.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
バイナリ状態を持ち符号化されるべきシンボルを、現時点の区間幅Ｒと上記符号化されるべきシンボルのための確率予測を表現する確率とに基づいて算術的に符号化するための方法において、
上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
上記方法は、上記符号化されるべきシンボルを符号化するステップを含み、この符号化のステップは、
上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングするサブステップと、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、区間分割を実行して部分区間幅の値を得るサブステップと、を含み、
上記マッピングのサブステップは、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフトおよびビットマスキング操作を適用することを含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、上記符号化の方法はさらに、
上記現時点の区間幅を上記部分区間幅の値を利用して更新し、更新された新たな区間幅を得るステップを含むことを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、
上記部分区間幅の値は、符号化されるべきシンボルのための部分区間の幅を、現時点の区間幅を持つ現時点の区間の低い確率状態で特定することを特徴とする方法。
【請求項４】
請求項１乃至３のいずれかに記載の方法において、
上記符号化されるべきシンボルの上記バイナリ状態に依存して、上記現時点の区間幅の更新がさらに実行されることを特徴とする方法。
【請求項５】
請求項１乃至４のいずれかに記載の方法において、
上記符号化の方法はさらに、
上記確率予測の適応のステップであって、この確率予測の適応のステップは、
上記符号化されるべきシンボルの確率状態が低い場合には、上記確率指標を用いて、ＬＰＳ変換規則表(Next＿State＿LPS)内のルックアップを実行して新たな確率指標を獲得し、上記符号化されるべきシンボルの確率状態が高い場合には、上記確率指標を用いて、ＭＰＳ変換規則表(Next＿State＿MPS)内のルックアップを実行して新たな確率指標を獲得するステップを含むことを特徴とする方法。
【請求項６】
請求項５に記載の方法において、
上記符号化の方法はさらに、上記確率指標が所定の確率指標であり、上記符号化されるべきシンボルが最初に示された状態とは異なるバイナリ状態を持つ場合には、上記符号化されるべきシンボルの上記バイナリ状態に対して最初に示された状態の上記高い確率状態を示す値を適合させるステップを含むことを特徴とする方法。
【請求項７】
請求項１乃至６のいずれかに記載の方法において、
上記現時点の区間幅を更新するサブステップは、
上記新たな区間幅を、上記現時点の区間幅から上記部分区間幅の値を引き算した差と同等にするステップと、
次に、もし上記符号化されるべきシンボルの確率状態が低い場合には、上記新たな区間幅を、上記部分区間幅の値と同等とするステップと、
を含むことを特徴とする方法。
【請求項８】
請求項１乃至７のいずれかに記載の方法において、
上記現時点の区間は上記現時点の区間幅と現時点のオフセットポイントとによって表され、
上記符号化の方法はさらに
上記符号化されるべきシンボルの確率状態が低い場合には、上記現時点のオフセットポイントと、現時点の区間幅と部分区間幅の値との差とを累積し、更新された新たなオフセットポイントを得るステップを含むことを特徴とする方法。
【請求項９】
符号化されバイナリ状態を持つシンボルを、現時点の区間幅Ｒと、上記符号化されたシンボルのための確率予測を表現する確率とに基づいて算術的に復号化するための方法において、
上記確率は、複数の代表的確率状態から１つの確率状態を示す１つの確率指標によって表現され、
上記方法は、上記符号化されたシンボルを復号化するステップを含み、この復号化のステップは、
上記現時点の区間幅Ｒを複数の代表的な量子化指標から１つの量子化指標へとマッピングするサブステップと、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、区間分割を実行して部分区間幅の値を得るサブステップと、を含み、
上記マッピングのサブステップは、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフトおよびビットマスキング操作を適用することを含むことを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、上記復号化の方法はさらに、
上記現時点の区間幅を上記部分区間幅の値を利用して更新し、更新された新たな区間幅を得るステップを含むことを特徴とする方法。
【請求項１１】
請求項９または１０に記載の方法において、
上記部分区間幅の値は、符号化されたシンボルのための部分区間の幅を、現時点の区間幅を持つ現時点の区間の低い確率状態で特定することを特徴とする方法。
【請求項１２】
請求項９乃至１１のいずれかに記載の方法において、
上記現時点の部分区間幅と新たな部分区間内の値とによって特徴付けられた上記新たな部分区間内の値に依存して、上記現時点の区間幅の更新がさらに実行されることを特徴とする方法。
【請求項１３】
請求項１２に記載の方法において、
上記復号化はさらに、
上記新たな部分区間内の値が、上記現時点の区間幅と部分区間幅の値との差と比較して大きいか小さいかに依存して、上記符号化されたシンボルのバイナリ状態を、確率が低い状態かまたは高い状態かのいずれか１つと同等にするステップを含むことを特徴とする方法。
【請求項１４】
請求項１２または１３に記載の方法において、上記復号化はさらに、上記新たな部分区間内の値を、読み込まれるべき次のビットを用いて更新するステップを含むことを特徴とする方法。
【請求項１５】
請求項１２乃至１４のいずれかに記載の方法において、
上記復号化の方法はさらに、
上記確率予測を更新するステップであって、この確率予測を更新するステップは、上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも大きい場合には、上記確率指標を用いて、ＬＰＳ変換規則表(Next＿State＿LPS)内のルックアップを実行して新たな確率指標を獲得し、
上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも小さい場合には、上記確率指標を用いて、ＭＰＳ変換規則表(Next＿State＿MPS)内のルックアップを実行して新たな確率指標を獲得するステップを含むことを特徴とする方法。
【請求項１６】
請求項１２乃至１５のいずれかに記載の方法において、
上記復号化の方法はさらに、
上記確率指標が所定の確率指標であり、上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも大きい場合には、上記符号化されたシンボルの異なるバイナリ状態に対して最初に示された状態の上記高い確率状態を示す値を適合させるステップを含むことを特徴とする方法。
【請求項１７】
請求項１乃至１６のいずれかに記載の方法において、
上記現時点の区間幅はｂビットの精度で表現され、上記区間分割表から得られた上記部分区間幅の値はｂ−２ビットの精度で表現されることを特徴とする方法。
【請求項１８】
請求項１乃至１７のいずれかに記載の方法において、
上記マッピングのサブステップは、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフト操作を適用して上記現時点の区間幅のための量子化された値を得ることと、表（Ｑtab）への下流方向アクセスにより量子化の指標を得ることを含むことを特徴とする方法。
【請求項１９】
請求項１乃至１８のいずれかに記載の方法において、
上記区間分割表内には、出現可能な全ての量子化指標と出現可能な全ての確率指標とに対応する上記現時点の区間幅のための値が、量子化の指標と表Ｒtab 内の確率指標との生成値としてファイリングされることを特徴とする方法。
【請求項２０】
請求項１乃至１９のいずれかに記載の方法において、
上記確率予測を更新するステップであって、
この確率予測の更新は変換規則によって実行され、この変換規則は、上記符号化されるべきシンボルおよび／または符号化されたシンボルに基づいて、複数の確率状態からいずれの新たな確率状態が次の符号化されるべきシンボルおよび／または符号化されたシンボルのために使用されるべきかを特定するステップをさらに含むことを特徴とする方法。
【請求項２１】
請求項１乃至２０のいずれかに記載の方法において、
上記確率予測を更新するステップであって、
この確率予測の更新は、上記確率指標を用いて、変換規則表(Next＿State＿LPS)内のルックアップを実行して新たな確率指標を得ることを含むステップをさらに含むことを特徴とする方法。
【請求項２２】
請求項１乃至２１のいずれかに記載の方法において、
上記出現可能な量子化指標の数および／または上記確率状態の数が、上記符号化のプリセットされた精度および／または有効情報蓄積容量に依存して選択されることを特徴とする方法。
【請求項２３】
請求項１乃至２２のいずれかに記載の方法において、
上記更新された新たなオフセットポイントと上記更新された新たな区間幅とを再正規化するサブステップをさらに含むことを特徴とする方法。
【請求項２４】
請求項９乃至２３のいずれかに記載の方法において、上記復号化は、
１．ＬＰＳの決定のステップと、
２．Ｒの量子化のステップと、
q＿index = Ｑtab[R≫q]
３．RLPSとＲの決定のステップと、
RLPS = Rtab [q＿index, p＿state]
R = R− RLPS 
４．上記部分区間の位置に依存するビットの決定のステップであって、
(Ｖ≧Ｒ）のとき
bit ← LPS
V ← V − R
R ← RLPS
(p＿state = 0)のときvalMPS←1− valMPS 
p＿state ← Next＿State＿LPS[p＿state]
その他は
bit ← MPS
p＿state ← Next＿State＿MPS [p＿state]
となるステップと、
５．Ｒの再正規化と、１ビットの読み出しと、Ｖの更新のステップであって、
q＿index はＱtab から読み出された量子化値の指標を示し、
p＿state は上記現時点の確率状態を示し、
RLPSは上記ＬＰＳに対応する区間幅を示し、
ValMPSは上記ＭＰＳに対応するビットを示し、
V は上記現時点の部分区間の内部からの値を示すステップと、
を含むことを特徴とする方法。
【請求項２５】
請求項１乃至２４のいずれかに記載の方法において、
符号化および／または復号化において、上記量子化の指標q＿index へのマッピングが次の計算規則：
q＿index = (R≫q)＆ Qmask
に従って実行され、Qmaskは確率状態の数に依存して適切に選択されたビットマスクを示し、Ｒは上記現時点の区間幅を示し、q はビットの数を示すことを特徴とする方法。
【請求項２６】
請求項１乃至２５のいずれかに記載の方法において、
もし均一な確率分布が存在している場合には、
符号化において、以下に示す計算規則：
R ← R ≫ 1
(bit = 1) のとき
L ← L + R
が実行されるか、または、以下に示す計算規則：
L ← L ≪ 1
(bit = 1)のとき 
L ← L + R
が実行され、最後の段階で２倍の決定しきい値を用いた再正規化が実行され、ＬとＲとは２倍されず、かつ、請求項９に記載の復号化において、以下に示す計算規則：
R ← R ≫ 1
(V ≧ R)のとき、
bit ← 1
V ← V − R
その他は
bit ← 0
が実行されるか、または、以下に示す計算規則：
１．１つのビットの読み出しとＶの更新
２．上記部分区間の位置に従うビットの決定: 
(V ≧ R)のとき、
bit ← 1
V ← V − R
その他は
bit ← 0
が実行されることを特徴とする方法。
【請求項２７】
請求項１乃至２６のいずれかに記載の方法において、
確率モデルの初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
【請求項２８】
請求項１乃至２７のいずれかに記載の方法において、
上記確率モデルの初期化が次のステップ：
１．preState = min(max(1, ((m * SliceQP)≫4)+n), 2*N)
２. (preState ＜＝ N) のとき
p＿state = N − preState 
valMPS = 0 
その他は
p＿state = preState−(N＋1)
valMPS = 1
を含み、valMPSはＭＰＳに対応するビットを示し、SliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
【請求項２９】
請求項１乃至２８のいずれかに記載の方法において、
上記確率状態の上記確率予測が有限状態機械（ＦＳＭ）を用いて実行されることを特徴とする方法。
【請求項３０】
請求項１乃至２９のいずれかに記載の方法において、
上記確率状態の生成はオフラインで実行されることを特徴とする方法。
【請求項３１】
請求項１乃至３０のいずれかに記載の方法において、
上記確率状態の選択は、符号化されるべきデータの統計および／または上記確率状態の数に依存することを特徴とする方法。
【請求項３２】
バイナリ状態を持ち符号化されるべきシンボルを、現時点の区間幅Ｒと上記符号化されるべきシンボルのための確率予測を表現する確率とに基づいて算術的に符号化するための装置において、
上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
上記装置は、上記符号化されるべきシンボルを符号化する手段を含み、この手段は、
上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングする手段と、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、上記区間分割を実行して部分区間幅の値を得る手段と、を含み、
上記マッピング手段は、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフトおよびビットマスキング操作を適用するように構成されていることを特徴とする装置。
【請求項３３】
バイナリ状態を持ち符号化されたシンボルを、現時点の区間幅Ｒと上記符号化されたシンボルのための確率予測を表現する確率とに基づいて算術的に復号化するための装置において、
上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
上記装置は、上記符号化されたシンボルを復号化する手段を含み、この手段は、
上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングする手段と、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、上記区間分割を実行して部分区間幅の値を得る手段と、を含み、
上記マッピング手段は、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフトおよびビットマスキング操作を適用するように構成されていることを特徴とする装置。
【請求項３４】
コンピュータが請求項１または９に記載の方法を実行できるように、コンピュータを作動させるコンピュータプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
本発明によれば、この目的は請求項１, ９，３２〜３４に記載の特徴と序文に記載の特徴との組み合わせにより達成される。本発明の望ましい実施例は、従属項の中で示される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
本発明の復号化方法のある特別な実施例は、以下のステップを含む：
１．ＬＰＳの決定
２．Ｒの量子化：
q_index = Qtab[R≫q]
３．ＲLPS とＲの決定：
RLPS = Rtab [q_index, p_state]
R = R - RLPS
４．部分区間の位置に依存するビットの決定
（Ｖ ≧ Ｒ）のとき
bit ← LPS
V ← V − R
R ← RLPS
(p_state = 0) のときvalMPS ← 1 - valMPS
p_state ← Next_State_LPS[p_state]
その他は
bit ← MPS
p_state ← Next_State_MPS [p_state]
５．Ｒの再正規化と、１ビットの読み出しと、Ｖの更新、このとき
q_index はＱtab から読み出された量子化値の指標を示し、
p_state  は現時点の確率状態を示し、
RLPS はＬＰＳに対応する区間幅を示し、
valMPS  はＭＰＳに対応するビットを示し、
V は現時点の部分区間の内部からの値を示す。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
もし均一な確率分布(probability distribution)が存在している場合には、表を利用したバイナリ算術符号化および復号化のための方法のさらなる最適化は、符号化において、以下に示す計算規則、即ち、
R ← R ≫ 1
(bit = 1)のとき
L ← L + R
という計算規則に従って実行されるか、または、以下に示す計算規則、即ち、
L ← L ≪ 1
(bit = 1)のとき
L ← L + R
に従って実行され、最後の段階において、再正規化が２倍された決定しきい値(doubled decision threshold)を用いて実行され、ＬとＲとは２倍されないという計算規則に従って実行され、かつ、請求項２４に記載の復号化においては、サブステップ１〜４が以下に示す計算規則、即ち、
R ← R ≫ 1 
(V ≧ R)のとき、
bit ← 1
V ← V− R
その他は
bit ← 0 
という計算規則に従って実行されるか、または、請求項２４に記載の復号化においては、サブステップ１〜５が以下に示す計算規則、即ち、
1.１つのビットの読み出しとＶの更新
2.部分区間の位置に従うビットの決定: 
(V ≧ R) のとき
bit ← 1
V ← V− R
その他は
bit ← 0
という計算規則に従って実行されるという事実から達成される。 
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
このようなコンピュータプログラムは、例えば、（有料または無料で自由にアクセス可能かまたはパスワードで保護された状態で）データあるいはコミュニケーションネットワークの中にダウンロードできるよう提供可能である。また、このように提供されるコンピュータプログラムは、次の方法により使用可能となる。すなわち、請求項３４に記載のコンピュータプログラムが、例えばインターネット等の送信用ネットワークからそのネットワークに接続されたデータ処理手段へとダウンロードされる方法である。
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2005525018.tif 000001