(57)【要約】【課題】本開示は、ビットプレーン符号化に基づく、ＭＰＥＧ−４精細粒度拡大縮小可能性（ＦＧＳ）を改善するための、確率論的ビットリシャッフリング方法を伴う、文脈ベースのバイナリ算術符号化を実行する方法に関する。【解決手段】該方法は：ＭＰＥＧ−４ＡＶＣ（進化したビデオ符号化）の４×４整数変換係数を、８×８ＤＣＴで置換し；各々の変換係数を有意ビット及び装飾ビットに区分し；変換ブロック内のエネルギー分布と隣接ブロック内の空間的相関に基づいて、有意ビットの文脈を設定し；装飾ビットに対し、符号化確率を誘導するために、推定ラプラシアン分布を用い；かつ側面情報ビットを保存するために、各々の有意ビットプレーンを区分するビットプレーンに亘る文脈を用いるステップからなる。【選択図】図１
2007006469.tif 000002
【特許請求の範囲】
【請求項１】
ＭＰＥＧ−４ＡＶＣの４×４整数変換係数を、８×８ＤＣＴで置換し；
各々の変換係数を有意ビット及び装飾ビットに区分し；
変換ブロック内のエネルギー分布と隣接ブロック内の空間的相関に基づいて、有意ビットの文脈を設定し；
装飾ビットに対し、符号化確率を誘導するために、推定ラプラシアン分布を用い；かつ
側面情報ビットを保存するために、各々の有意ビットプレーンを区分するビットプレーンに亘る文脈を用いるステップからなることを特徴とする精細粒度拡大縮小可能性のための確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【請求項２】
側面情報ビットを保存するために、各々の有意ビットプレーンを区分するビットプレーンに亘る文脈を用いる該ステップが、側面情報ビットを保存するために各々の有意ビットプレーンを二つの部分に区分するための、より高いビットプレーンのＥＯＳＰ位置を用いることを含むことを特徴とする請求項１に記載の確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【請求項３】
その推定されたレート歪みにより、各々のビットの符号化順序を決定することをさらに含み、推定されたビットレートに亘る、推定された歪み削減の比に従って、全ての符号化されるビットが降順に順序づけられることを特徴とする請求項１に記載の確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【請求項４】
各々のビットに対する該推定されたレート歪みが、変換係数をモデルにするために不連続ラプラシアン分布を用いることにより得られることを特徴とする請求項３に記載の確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【請求項５】
符号化ビットレートの推定のためにバイナリエントロピーを用い、かつ該ラプラシアン分布のパラメータの推定を提供するために最尤原理を用いることをさらに含むことを特徴とする請求項１または３に記載の確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【請求項６】
確率論的ビットリシャッフリングのために、動的符号化フローを用いることをさらに含むことを特徴とする請求項１に記載の確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【請求項７】
該ビットリシャッフリングが、レート歪みの最適化、主観的品質の改善及び関心領域の機能性のような、種々の目的に対する、係数、ブロック、領域またはサイクルレベルのリシャッフリングに拡張可能であることを特徴とする請求項１に記載の確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【請求項８】
異なるプライオリティの割り当てを用いることをさらに含み、特定の用途に対する異なる粒度でのリシャッフリングを実行することを特徴とする請求項１に記載の確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、精細粒度拡大縮小可能性のための、確率論的ビットリシャッフリングを伴う、文脈適応バイナリ算術符号化を実行する方法に関する。本発明は特に、ビットプレーンコーディングに基づく、精細粒度拡大縮小可能性（ＦＧＳ）の改善のための確率論的ビットリシャッフリングを伴う文脈適応バイナリ算術符号化を実行する方法に関する。
【背景技術】
【０００２】
拡大縮小可能なビデオコーディング（ＳＶＣ）は、インターネット及びワイヤレスチャネルにおける、マルチメディアのアプリケーションの急速な成長に伴って重要性が増大し、このようなアプリケーションにおけるビデオ情報は、変動するバンド幅を伴う修復ミスの多いチャネルで送信され、異なるネットワークを通して、多様な装置で用いられる。異質な環境下でマルチメディアのアプリケーションを提供するために、ＭＰＥＧ−４委員会は、ＤＣＴベースのレイヤの方法での拡大縮小可能なアプローチを提供する精細粒度拡大縮小可能性（ＦＧＳ）（Ｗ・Ｌｉ「ＭＰＥＧ−４規格における精細粒度拡大縮小可能性の概観」ＩＥＥＥトランザクションビデオ技術回路システム、Ｖｏｌ．１１、Ｎｏ．３、ｐｐ３０１−３１７、２００１年）を開発した。エンハンスメントレイヤが精細粒度拡大縮小可能性を実行するために、エンベッデドビットプレーン符号化を伴うイントラ符号化されるのに対し、ベースレイヤは拡大縮小可能でない、ＭＰＥＧ−４先進シンプルプロファイル（ＡＳＰ）により符号化される。同様のビットプレーン符号化法は、最新のＭＰＥＧ−４ｐａｒｔ１０，Ａｍｄ．１の拡大縮小可能なビデオ符号化規格で適合されている。
【０００３】
現在のビットプレーン符号化においては、エンハンスメントレイヤフレームは最初に８×８ＤＣＴに変換される。精細粒度拡大縮小可能性を提供するために、変換係数はビットプレーン毎のやり方で符号化される。最上位のビットプレーンから最下位のビットプレーンまで、ＤＣＴブロックの符号化はラスタスキャンでオーダーされる。ＤＣＴブロックの各々のビットプレーンは、（ＲＵＮ，ＥＯＰ）記号により独立に表示され、ホフマンテーブルで符号化される。しかし、現在のアプローチは、下記の二つの問題を有する。
【０００４】
ａ．低い符号化効率
第１の問題は、符号化効率の低さである。そのような問題は、三つの因子に由来する：
第１は、情報の異なる重みを携行するビットが、区別なく符号化されることである。第２は、ビットプレーン間及び空間的に隣接するブロックの間の現存する相関が利用されないことである。最後に、ホフマン符号化は符号化過程での統計量の変化に効率的に適合しないことである。現在のアプローチでは、ビットプレーン内のビットの異なる重みは（Ｒｕｎ，ＥＯＰ）記号により一緒にグループ化される。その上、一つのブロック内の各ビットプレーンは相関関係がない。さらに各々の変換ブロックは、独立に符号化される。これらの点は、共に符号化効率を低下させる。
【０００５】
ｂ．低い主観的品質
第２の問題は、決定論的ラスタスキャンが、エンハンスメントレイヤが部分的に復号された時に、品質の食い違いを引き起こすことである。現在は各々のビットプレーン内で、ＭＰＥＧ−４ＦＧＳがブロック毎の方法で符号化を実行している。全てのブロックが、ラスタスキャンでオーダーされる。一つのブロックの符号化は、前の一つの符号化が完了した場合にのみ、先だって実行されることができる。エンハンスメントレイヤが部分的に復号されると、そのようなオーダーは復号されたフレームの上部の１つの特別なビットプレーンのみを洗練する。不均一な再洗練は主観的な品質を低下させる。
【０００６】
何人かの研究者は、ビットプレーン符号化ベースのＤＣＴの符号化効率の改善を提案している。現存するアプローチの、下記非特許文献１、及び下記非特許文献２は、効率的なＤＣＴベースのビットプレーン符号化のための、文脈ベースのバイナリ算術符号化を採用した。下記非特許文献１は、ＤＣＴ変換のエネルギー分布を用いて符号化効率を改善した。さらに、下記非特許文献２はそれらの文脈設計の際の隣接ブロックの共存係数に存在する空間相関を考察した。しかしながらこれらの先駆的業績は、ビットプレーンを貫通する相関を考慮していない。さらなる符号化効率の向上が、可能である。さらに、これらの先駆的業績は、各々のビットプレーン符号化でラスタスキャンオーダーを未だに用いている。不均一な品質分布の問題は、残されている。
【０００７】
さらに、下記非特許文献３はこの用途の先駆的業績であるが、しかしながらこの文献のリシャッフリング方法は、同じビットプレーン内の再順序づけを限定する。
【０００８】
さらに、下記特許文献１〜５のような、符号化効率の改善のためのビットリシャッフリング方法及び再順序づけ効率方法を開示する、いくつかの特許が存在する。しかしながらそれらは、複雑な浮動小数点操作を必要とする、符号化前の８×８ＤＣＴを実行し、ＭＳＢビットプレーンからＬＳＢビットプレーンに始まるそれらの符号化フローは、コンテントアウェアリシャッフリングのためである、レート歪みデータ更新を考慮していない。
【０００９】
従って、ＦＧＳベースのビットプレーン符号化の符号化効率を改善するように、操作を簡便にすることができ、ビット符号化のオーダーをより柔軟に出来るようにする、方法を開発することが必要である。
【００１０】
【特許文献１】米国特許公開２００３／０１３３４９９号公報
【特許文献２】米国特許第６２７５５３１号公報
【特許文献３】米国特許第６６２５３２１号公報
【特許文献４】米国特許公開２００４／００１７７９４９公報
【特許文献５】米国特許第６５０１３９７号公報
【非特許文献１】Ｎ・Ｋ・ローレンス、Ｄ・Ｍ・モンロー、「有意性をマスクしたエンベッデトＤＣＴ符号化」ＩＥＥＥ、音響、スピーチ及び信号処理国際学会１９９７
【非特許文献２】Ｄ・ニスター、Ｃ・クリストポーロス、「エンベッデドＤＣＴベースのスチル画像符号化アルゴリズム」ＩＥＥＥ、音響、スピーチ及び信号処理国際学会１９９８
【非特許文献３】Ｗ・Ｈ・ペン、Ｃ・Ｎ・ワング、Ｔ・チアン、Ｈ・Ｍ・フアンの「ＦＧＳのための確率論的ビットリシャッフリングを伴う文脈ベースのバイナリ算術符号化」ＩＥＥＥ回路とシステムの国際会議、バンクーバー、２００４年５月の文書
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上記の課題を考慮して本発明の目的は、符号化効率とＦＧＳベースのビットプレーン符号化の主観的品質の双方を改善するために、精細粒度拡大縮小可能性のための、確率論的ビットリシャッフリングを伴う、文脈適応バイナリ算術符号化を実行する方法を提供することである。
【課題を解決するための手段】
【００１２】
上記の目的を達成するために本発明に従えば、ＭＰＥＧ−４ＡＶＣ（Ａｄｖａｎｃｅｄ ＶｉｄｅｏＣｏｄｉｎｇ、Ｈ．２６４としても知られる）の４×４整数変換係数を、８×８ＤＣＴで置換し；各々の変換係数を有意ビット及び装飾ビットに区分し；変換ブロック内のエネルギー分布と隣接ブロック内の空間的相関に基づいて、有意ビットの文脈を設定し；装飾ビットに対し、符号化確率を誘導するために、推定ラプラシアン分布を用い；かつ側面情報ビットを保存するために、各々の有意ビットプレーンを区分するビットプレーンに亘る文脈を用いるステップからなる、精細粒度拡大縮小可能性のための、確率論的ビットリシャッフリングを伴う、文脈適応バイナリ算術符号化を実行する方法が提供される。
【００１３】
さらに本発明の上記方法に従えば、側面情報ビットを保存するために、各々の有意ビットプレーンを区分するビットプレーンに亘る文脈を用いる該ステップが、側面情報ビットを保存するために各々の有意ビットプレーンを二つの部分に区分するための、より高いビットプレーンのＥＯＳＰ位置を用いることを含む。
【００１４】
さらに本発明の上記方法に従えば、該方法はその推定されたレート歪みにより、各々のビットの符号化順序を決定するステップをさらに含み、推定されたビットレートに亘る、推定された歪み削減の比に従って、全ての符号化されるビットが降順に順序づけられる。
【００１５】
さらに本発明の上記方法に従えば、各々のビットに対する該推定されたレート歪みが、変換係数をモデルにするために不連続ラプラシアン分布を用いることにより得られる。
【００１６】
その上、本発明の上記方法に従えば、該方法はさらにビットレート推定を符号化するためのバイナリエントロピーを用いるステップと、ラプラシアン分布のパラメータについての推定を備えるべく最尤原理を用いるステップを含む。
【００１７】
さらに本発明の上記方法に従えば、該方法は確率論的ビットリシャッフリングのために、動的符号化フローを用いるステップをさらに含む。
【００１８】
上記及びその他の本発明の目的、特徴及び利点は、添付の図面を参照して進行する、本発明の望ましい実施形態の詳細な記述から、より明らかになるであろう。
【発明を実施するための最良の形態】
【００１９】
Ａ．用語
先ず、図１を参照して、「フレームのＭＳＢビットプレーン」、「ブロックのＭＳＢビットプレーン」及び「係数のＭＳＢ」に言及する時の用語を定義する。単純化のために、全エンハンスメントレイヤフレームは３つの変換ブロックを有し、各々のブロックは４つの係数を有することと仮定する。縦軸は、変換係数のビン番号を示す。係数のＭＳＢビットは、その最有意ビットを表わす。あるフレームのＭＳＢビットプレーンは、全フレーム内での最大係数のＭＳＢビットを含むものを表わす。他方、あるブロックのＭＳＢビットプレーンは、ブロックの最大係数のＭＳＢビットを含むものを表わす。
【００２０】
Ｂ．ビット分類及びビットプレーン分割
各々の変換係数のビットは、有意ビット、装飾ビット及び符号ビットを含む３種類に分割される。ブロックのＭＳＢビットプレーンからＬＳＢビットプレーンまで、係数の有意ビットはそのＭＳＢビットの前（及びそれを含む）のビットである。他方装飾ビットは、ＭＳＢの後のビットである。符号ビットは、係数の符号を表わす。
【００２１】
さらに変換ブロックの各々のビットプレーンに対して、ここでは二つの側面情報シンボルを提案する。それらは、Ｅｎｄ−Ｏｆ−Ｓｉｇｎｉｆｉｃａｎｔ−Ｂｉｔ−ｐｌａｎｅ（ＥＯＳＰ）及びＰａｒｔ＿II＿ＡＬＬ＿ＺＥＲＯである。ＥＯＳＰは、ビットプレーン内の有意ビット符号化の終端について表わすために、ゼロでない有意ビットの後に符号化される。ＥＯＳＰビットを最少にするために、ラストＳと名付けられた、前のビットプレーン内の最後のゼロでない有意ビットの位置に従って、ビットプレーンの有意ビットを二つの部分に分割する。最初の部分（パートＩ）はジグザグな順序でラストＳの前の有意ビットの組を参照し、第２の部分（パートII）は残りの有意ビットをカバーする。図２は有意ビットプレーンの分割の一例を示す。図２の各々の列は、変換係数のバイナリ表現を表わす。上から下までの各々の行は、ビットプレーンを表わす。ビット分割について、ビットプレーン２のラストＳはＡＣ３である。ビットプレーン２について、ＡＣ３の前の有意ビットはパートＩに分類され、残りの有意ビットはパートIIに分類される。ここで述べるアルゴリズムでは、パートIIのゼロでない有意ビットの後のＥＯＳＰ記号を送信することにより、ＥＯＳＰビットを保存する。
【００２２】
進行中のビットプレーンの符号化の最後のゼロでない有意ビットはラストＳの前で実際に起こるので、パートIIの全てのゼロの有意ビットを送信する必要がある。これらの冗長ビットの符号化を避けるために、全てがゼロの場合について復号器に通知する、Ｐａｒｔ＿II＿Ａｌｌ＿ＺＥＲＯ記号を用いる。特に、そのような記号は、各々のビットプレーンのパートII符号化の前に送信される。
【００２３】
【表１】
2007006469.tif 000003
【００２４】
【表２】
2007006469.tif 000004
【００２５】
Ｃ．内容設計
１．ＭＳＢ＿ＲＥＡＣＨＥＤ
ＭＳＢ＿ＲＥＡＣＨＥＤ記号は、あるブロックのＭＳＢビットプレーンがＲＥＡＣＨＥＤされたか否かを表わす、側面情報ビットである。ＭＳＢ＿ＲＥＡＣＨＥＤ記号の文脈指標の計算のために、隣接する９ブロックのＭＳＢ＿ＲＥＡＣＨＥＤ状態を参照する。表１は、実行する詳細な手順を一覧表にしたものである。
【００２６】
２．有意ビット
表２は、有意ビットの符号化用の参照文脈をリストしたものである。特に表２の重み付け総和指標の計算のために、表１のＭＳＢ＿ＲＥＡＣＨＥＤを同じ場所に配置された係数の有意状態と置換し、指標計算のための表１の手続と同じ手続を繰り返す。さらに、コストと性能をトレードオフするために、各々の参照された文脈指標の値が適宜に切り上げられる。図３は有意ビットの文脈モデルの一例を与え、そこでは「Ｒｕｎ」の値は１、有意状態の重み付け総和は４、かつ周波数帯域位置は８である。
【００２７】
３．装飾ビット
装飾ビットの符号化確率を誘導するために推定されたラプラシアンモデルを用いる。装飾ビットのためには、それ以上の文脈モデルは生成されない。以下に示されるように、装飾ビットの確率モデルは推定されたラプラシアン分布から誘導されることができる。
【００２８】
４．符号ビット
符号ビットの符号化のためにここでは等確率モデルを用いるものとする。
【００２９】
【表３】
2007006469.tif 000005
【００３０】
５．有意ビットプレーンの終端（ＥＯＳＰ）
図３はＥＯＳＰビットのために参照した文脈モデルを要約している。最初に、最も近い４ブロックの平均のＥＯＳＰ位置を採用することにより、ＥＯＳＰ位置を予測する。予測された位置から、現在のゼロでない有意ビットと予測されたＥＯＳＰ位置の間のずれとして、ＥＯＳＰの文脈を定義する。このズレの値は負の値でありうることに留意するべきである。さらに、参照された文脈の一部としてビットプレーン指標を含む。ブロックのＭＳＢビットプレーンからＬＳＢビットプレーンまで、ビットプレーン指標はゼロから１ずつ歩進される。メモリの節約のため、４以上のビットプレーン指標は切り捨てられる。
【００３１】
６．Ｐａｒｔ＿II＿Ａｌｌ＿Ｚｅｒｏ
Ｐａｒｔ＿II＿Ａｌｌ＿Ｚｅｒｏ記号のための文脈モデルとして、ここではブロックのビットプレーン指標を採用する。ブロックのＭＳＢビットプレーンからＬＳＢビットプレーンまで、この指標はゼロから１ずつ歩進される。メモリを節約するため、４以上のビットプレーン指標は切り捨てられる。
【００３２】
【表４】
2007006469.tif 000006
【００３３】
Ｄ．決定論的ラスタスキャンを伴う符号化フロー
表４はラスタスキャン順序を用いたビットプレーン符号化の疑似コードを示す１つの提案である。これにより各々のエンハンスメントレイヤフレームに対し、ＭＳＢからＬＳＢまでビットプレーン符号化を始める。各々のビットプレーンに対し、符号化はブロック毎の方法で実行される。各々のブロック内で、係数はジグザグな順序で訪ねられる。各々のブロックの符号化の前に、現在のブロックがＭＳＢビットプレーンに到着したか否かを通知するために、ＭＳＢ＿ＲＥＡＣＨＥＤ記号が最初に符号化される。ＭＳＢ＿ＲＥＡＣＨＥＤが真である場合には、ビットプレーンの符号化を起動する。符号化に際して、異なるビット型式は異なって符号化される。考察されている入力ビットが有意ビットである場合、現在の有意ビットが属するパーティションを検査する。パートＩの有意ビットに対しては、符号ビットと共に有意ビットを単純に符号化する。パートIIの有意ビットに対しては、符号ビットの後にさらにＥＯＳＰビットを符号化する。そして、特に各々のパートII有意ビットの符号化の最初に、Ｐａｒｔ＿II＿Ａｌｌ＿Ｚｅｒｏビットを符号化する。Ｐａｒｔ＿II＿Ａｌｌ＿ＺｅｒｏまたはＥＯＳＰが真であるならば、現在のブロックの符号化を停止し、次のブロックに移行する。入力ビットが装飾ビットである場合は、単に装飾ビットそれ自身を符号化する。実験による結果から、ＭＰＥＧ−４ＦＧＳアプローチと比較して、０．５〜１ｄＢのＰＳＮＲの改善を得た。より詳細な実験結果は、後に示される。
【００３４】
Ｅ．確率論的ビットリシャッフリング
主観的品質を改善するために、確率論的ビットリシャッフリング方法が提案される。確率論的レート歪みの意味で、ビットリシャッフリングを実行する。各々のビットに二つの推定因子を割り当てるが、それらは、（１）誤差低減の二乗：ΔＤ、（２）符号化コスト：ΔＲである。誤差低減の二乗は誤差改善の二乗への寄与を表わし、符号化コストは要求されるビットレートを意味する。各々のビットにこれら二つの因子を与えて、式（１）は符号化順序の基準を定義し、そこでは
2007006469.tif 000007
は推定を取ることを表わし、上付き記号はビットの身元を表わし、下付き記号は符号化順序を表わす。端的には、推定されたΔＲに亘って推定されたΔＤの比に従い、降順で全ての符号化ビットを再度順序づける。
2007006469.tif 000008
【００３５】
Ｆ．パラメータ推定
１．不連続ラプラシアン分布
各々のビットのΔＤ及びΔＲを推定するために、それらの期待値を用いる。期待値の計算のために、変換係数の確率分布を必要とする。復号器は正確な確率分布を有さないので、復号器のオーバーヘッドを最小化するアプローチに基づくモデルを採択する。特にエンハンスメントレイヤでのＭＰＥＧ−４ＡＶＣ／Ｈ．２６４の４×４整数変換を用いる。ラプラシアン分布を伴うランダム変数として、各々の４×４変換係数をモデルにする。式（２）は、不連続ラプラシアン分布の確率モデルを定式化し、そこではＣｎはｎ番目のジグザグ順の係数を表わし、Ｋｎはその結果を表わし、αｎは決定されるべきラプラシアンパラメータである。
2007006469.tif 000009
【００３６】
２．ラプラシアンパラメータの推定
式（３）は、ラプラシアンパラメータに対する、最尤推定器を示す。示されるようにαｎを推定するために、ｎ番目のジグザグ位置で同じ場所に存在する係数の絶対値の平均を最初に計算し、次にそれを式（３）に代入する。ここで述べるアプローチでは、推定は符号化器で行われ、推定されたパラメータは復号器に送信される。４×４整数変換では、輝度成分に対して１６のパラメータを、色度成分に対して他の１６のパラメータを単に必要とする。
2007006469.tif 000010
【００３７】
３．ΔＤの推定
次に、二乗誤差の期待値についての削減により、各々の係数ビットのΔＤを推定する。図４に、ある係数の予め定義されたラプラシアン分布を示し、ΔＤの推定を描く二つの例を与えた。左側に、係数のＭＳＢがゼロに符号化された、有意ビットの例を示す。右側には、係数のＭＳＢがゼロでなく符号化された、装飾ビットの場合を示す。
【００３８】
符号化されたＭＳＢビットから、実際の値が存在する不確実な期間を告げることができる。有意ビットの場合については、ＭＳＢの符号化の後に期間Ｂに実際の値があることが判る。同様に装飾ビットの場合には、実際の値は期間Ａに存在する。これらの期間を与えられると、各々の係数ビットの符号化はさらに不確実な期間を削減する。例えば図４では符号化されるべき有意ビットは、実際の値が期間Ｂ１＋、Ｂ０またはＢ１−内にあることを決定することである。同様に、符号化されるべき装飾ビットは、実際の値が期間Ａ１またはＡ０にあることを決定することである。
【００３９】
不確実な期間の削減は、二乗誤差の期待値の削減を表わす。各々の期間に対して、期間内の変動として二乗誤差の期待値を定義する。このようにして各々のビットに対するΔＤの推定は、変動の削減として記述される。式（４）は、図４の有意ビットの例に対しΔＤの推定、
2007006469.tif 000011
を定義し、ここでＥ（Ｘ｜Ｙ）は与えられたＹの条件でのＸの条件期待値を表わし、Ｐ（Ｘ｜Ｙ）は条件確率を意味する。式（４）では、最初の項は期間Ｂでの変動を表わし、三つの減算項はそれぞれ期間Ｂ１＋、Ｂ１−及びＢ０の重み付けされた変動を意味する。符号化前にはどの期間に実際の値が存在するか決定することができないので、各々の減算項の重み付け因子は各々の部分期間の確率を表わす。同じ手続に従って、他の全てのビットに対するΔＤの推定が、計算されることができる。式（５）は、図４における装飾ビットの場合に対する、ΔＤの推定を定義する。
【００４０】
有意ビットのリシャッフリングの内容を明らかにするために、式（４）の部分期間の確率を文脈確率モデルに置換する。式（６）は、有意ビットに対する内容が明らかなΔＤの推定を定義する。式（６）において、Ｐｃｔｘ（）は有意ビットの、関連する文脈確率を意味する。
【００４１】
装飾ビットに対しては何らの文脈モデルをも開発していないので、装飾ビットのΔＤ推定に対しては式（５）に従う。
2007006469.tif 000012
2007006469.tif 000013
2007006469.tif 000014
【００４２】
４．ΔＲの推定
ΔＲの推定に対しては、式（７）に定義されるバイナリエントロピーを用いるが、ここでＰ（１）は入力ビットのゼロでない確率を意味する。
2007006469.tif 000015
【００４３】
式（８）では、有意ビットのΔＲの推定を示す。最初の項は議論されたような関連する文脈確率モデルを用いた、有意ビットのバイナリエントロピーを表わし、第２の項は符号ビットのコストの推定を意味する。式（８）では、各々の符号ビットが平均的に１ビットを消費すること、さらに、符号のコストは有意ビットのゼロでない確率で重み付けされること、が仮定されている。特にゼロでない確率は、関連する文脈確率モデルから誘導される。
【００４４】
式（９）では、装飾ビットのΔＲ推定が示される。装飾ビットには特別な文脈確率モデルがないので、バイナリエントロピー計算に対するラプラシアンモデルから誘導される、ゼロでない確率を用いる。特に、ゼロでない確率は対応部分区間確率である。例えば、図４の装飾ビットの例では、Ｐモデル（１）はＰ（Ａ１｜Ａ）に等しい。
2007006469.tif 000016
2007006469.tif 000017
【００４５】
Ｇ．確率論的ビットリシャッフリングの符号化フロー
確率論的レート歪みの最適化に対し、符号化器と復号器の双方が符号化のプライオリティを維持するために、二つの動的な符号化リストを備えている。一つは有意ビット用であり、他方は装飾ビット用である。リスト中の各々のビットが、ビット位置、ビット型式、符号化文脈及び推定レート歪みのデータを記憶するために、レジスタを割り当てられている。
【００４６】
ここで使用したアルゴリズムでは、余剰側面情報ビット及び冗長ビットの符号化を避けるために、符号化順序に二つの制約を課している。それらの制約は：（１）各々の係数に対し、符号化はＭＳＢからＬＳＢまで連続的に行われること、及び（２）変換ブロックの各々のビットプレーンに対し、パートII内の有意ビットの符号化順序は常にジグザグのスキャンに従う、ことである。
【００４７】
図５は、これらの制約を与えられた場合の、符号化フローの概観を示す。単純化のために、有意ビットのリストのみが示されている。装飾ビットに対してはレート歪みデータの更新が不要であること以外は、装飾ビットのフローについても同じである。始めに初期化ステップが、リスト内のエンハンスメントレイヤフレームのＭＳＢビットプレーンに、全てのＤＣ係数ビットを置く。次に、推定レート歪みデータに従って、リスト内のビットをリシャッフルする。リシャッフリングの結果から、最高のプライオリティビットを得て、バイナリ算術符号化を実行する。符号化の後、関連する文脈確率モデルを更新する。文脈確率モデルは洗練され、同じ場所に存在する有意ビットの文脈は符号化後に変更されることができるので、リスト内の古くなったレート歪みデータは更新される。更新後に、より多くのビットをリシャッフリングに含むために、拡散に似た機構が用いられる。図５のステップ（ｂ）から（ｅ）は、全ての入力ビットが符号化されるまで繰り返される。
【００４８】
2007006469.tif 000018
【００４９】
１．レート歪みデータの更新
推定レート歪みデータの更新は、推定のために常に最新の文脈確率モデルを用いることを保証することである。特に、ここでは有意ビットのレート歪みデータを更新するのみである。装飾ビットのそれは、推定ラプラシアン確率モデルから誘導されるので、更新されない。推定ラプラシアン確率モデルは、リシャッフリングの処理中は固定されている。
【００５０】
アルゴリズムでは、リスト内の更新されるべき有意ビットは：
カテゴリ１：現在符号化された有意ビットと、同じ文脈を用いる有意ビット。
カテゴリ２：隣接するブロック内の、同じ場所に存在する係数の有意ビット。
カテゴリ３：現在符号化されたビットの（ジグザグの順序で）次のパートＩの有意ビット。
【００５１】
２．新しいビットの包含
全ての入力ビットが同時にリシャッフリングのリストに置かれることは出来ないので、リシャッフリングと符号化により多くのビットを含めるために、拡散方式に似た方式が提案される。基本的なアイデアは、最初に符号化されたビットの周囲のまだ符号化されていないビットを含むことである。表５は、現在符号化されたビットと含まれるべきそれに続くビットの間の、写像規則を定義する。
【００５２】
図６は、その一例を示す。図６（ａ）から図６（ｄ）まで連続的に、変換ブロックの最初の４つの符号化状態が示される。単純化のために、変換ブロックは４つの係数のみを有する。各々の列は係数のバイナリ表現を意味し、各々の行はビットプレーンを表わす。左から右へ、係数はジグザグの順序である。各々の係数について、空白の四角形はまだ符号化されていないビットを意味する。他方、二進数を伴う四角形は、符号化された値を示す。影を付された四角形は符号化されたビットを表わし、点線の四角形はリスト中のビットを意味する。リスト中のこれらのビットに対しては、それらのビット型式を表わすために、Ｓ＿Ｉ、Ｓ＿IIまたはＲが用いられる。Ｓ＿ＩはパートＩの有意ビットを意味し、Ｓ＿IIはパートIIの有意ビットを意味する。他方、Ｒは装飾ビットを表わす。
【００５３】
図６（ａ）は、ＢＰ３でのＤＣ係数のビットが最上のプライオリティビットとして認識され、ゼロに符号化されることを示す。この符号化の後、表５の第３の規則に従って、リスト内のＢＰ３でのＡＣ１の有意ビット、及びＢＰ２でのＤＣ０の有意ビットが包含される。リシャッフリングの後、図６（ｂ）はＢＰ３でのＡＣ１の有意ビットが符号化される場合を示す。同様に、ＢＰ３でのＡＣ２の有意ビット、及びＢＰ２でのＡＣ１の有意ビットが包含される。その後、図６（ｃ）はＢＰ２でのＡＣ１の有意ビットが、ＢＰ２でのＤＣ０の有意ビットに先立って符号化される場合を示す。定義により、ＡＣ１の有意ビットの「Ｒｕｎ」文脈は、ＤＣ０の有意状態に依存する。しかしながら、それがレート歪みの特性をよりよく推定する限り、符号化の事実でない文脈を使用することが許容される。表５の第一の規則に従って、符号化後にＢＰ１でのＡＣ１の装飾ビットを包含する。最終的に図６（ｄ）は、ＡＣ２のＭＳＢが最上のプライオリティであり、ＢＰ３のＥＯＳＰとして認識される場合を示す。表５の第５の規則に従って、リスト内のＢＰ２でのＡＣ２の装飾ビット、及びＢＰ２でのＡＣ３の有意ビットを包含する。表５の規則に従って、他の全ての入力ビットの符号化を完了させることができる。
【００５４】
Ｈ．動的なメモリの組織化
有意ビットの更新とリシャッフリングは、集約的な計算を必要とする。計算を低減するために、有意ビットリスト内のレジスタを管理する、動的なメモリの組織化方法を提案する。これによりリスト内の全てではない有意ビットが、更新とリオーダリングを必要とすることを見いだした。従ってこの方法は、単にそのように作用するビットをリオーダーして更新し、他のビットには手を触れないでおく。
【００５５】
現在符号化された有意ビットと同じ文脈を用いる有意ビットを早急に特定するために、リンクリストを用いて同じ文脈の有意ビットがグループ化される。図７の右側に、各々の円が有意ビットの関連するレジスタを表わし、各々の四角形が文脈のグループを表わす、一例が示されている。定義により、レジスタＡ３、Ｂ３，Ｃ３、Ｄ３は同じ文脈を有する。各々のグループの最上のプライオリティビットを特定するために、
2007006469.tif 000019
の比に従って、グループ内のレジスタがさらに再度順序づけられる。左から右へ、プライオリティ（即ち、
2007006469.tif 000020
）が降順である。
【００５６】
上述のグループ化方法では、リストの最上のプライオリティビットが、各々のグループの最上のプライオリティビットの比較により、見いだされることができる。そのような比較を実行するために、グループ内の最上のプライオリティビットを示す、文脈グループポインタが各グループに割り当てられる。各々のグループの最上のプライオリティビットに従って文脈グループポインタを再度順序づけることにより、リスト内の最上のプライオリティビットが特定される。特に順序を維持するために、リンクリスト構造を伴う文脈グループポインタを用いる。図７では、文脈グループポインタが中央部に示されている。上から下へ、プライオリティが降順であり、即ちＡ３>Ａ１>Ａ５>…>ＡＮである。この例では、Ａ３はＣｔｘ３グループの最上のプライオリティビットであるばかりでなく、リストの最上のプライオリティビットでもある。
【００５７】
最上のプライオリティビットが特定されて符号化された後、その文脈が変更された有意ビットを更新する必要がある。符号化は動的であるので、どの有意ビットが更新されるべきか事前に決定することはできない。結果的に、ゼロでない有意ビットが符号化される都度、古くなった有意ビットのビット位置を誘導するために、前の章のカテゴリ２及びカテゴリ３の定義に従う。誘導されたビット位置に従って、符号化されたビットの状態をリバースする事により、符号化前のそれらの文脈を再計算する。古くなったビットの文脈指標から、それらの文脈グループ内のサーチを限定することができる。全ての文脈グループポインタ内の徹底的なサーチを避けるために、入力として文脈指標を用い、出力として関連する文脈グループポインタを生成する、参照表を構築する。図７の左側は、そのような参照表を示す。実際には、その表は文脈グループポインタを指し示す、ポインタのアレイとして実装される。
【００５８】
全ての更新と再順序づけのフローの図式化のために、各々のグループの有意ビットと文脈グループポインタが初期化から再順序づけされていると仮定した、ある例として図７を用いる。このようにして実際の符号化では、有意ビットが符号化される都度、単にレジスタの部分を修正して再順序づけすればよい。この例では、Ａ３がリストの最上位プライオリティビットである。Ａ３が符号化されると、Ｂ３とＤ３が符号化されたビットと同じ文脈を有するので、それらが更新されるべきである。さらに図７では、Ａ３の符号化の後その文脈が変更された二つの有意ビットがあることが仮定されている。Ａ３の符号化前のこれら二つのビットの文脈が、Ｃｔｘ５、Ｃｔｘ２であるとそれぞれ仮定する。他方、Ａ３の符号化後の対応する文脈は、Ｃｔｘ４、Ｃｔｘ６であると仮定される。これら二つの有意ビットの文脈は変更されたので、最新の文脈確率モデルを用いてレジスタを更新し、関連するレジスタを一つのグループから他のグループに移動させる。符号化前の文脈指標は、更新のためにレジスタをサーチするため、内容グループを特定する。他方符号化後の文脈指標は、修正されたレジスタをどのグループに置くべきかの宛先グループを決定する。これら全ての文脈指標により、サーチして更新する文脈グループへ早急にアクセスするために、参照表を用いる。グループ内のサーチはビット位置の比較により為されることに、留意するべきである。図７に示されるように、レジスタＢ５はＣｔｘ５グループからＣｔｘ４グループのＢ４位置に、更新されて移動される。同様に、レジスタＡ２はＣｔｘ２グループからＣｔｘ６グループのＡ６位置に、更新されて移動される。特に、修正されたレジスタが宛先グループに置かれる時に、リンクリスト内のその位置は更新されたレート歪みデータにより決定される。例えばレジスタＢ５は、それらのプライオリティがＡ４>Ｂ４（Ｂ５）>Ｃ４なので、Ｂ４に移動される。更新及び移動の後、Ｃｔｘ３グループ、Ｃｔｘ２グループ及びＣｔｘ６グループの最上位のプライオリティビットは変更される。このようにして、文脈グループポインタのリンクリスト内のこれらのグループの順序は、再度決定される。特にこれらのグループポインタが、最初にリンクリストから取り除かれる。次に更新された最上位のプライオリティビットの比較により、それらが連続して適宜の位置に入れ戻される。そのような方法で、変更されない文脈グループを手つかずにすることができる。これらの実装において、リストから任意のノードをランダムかつ早急に取り除くことができるように、文脈グループポインタのリンクリストは双方向に実装される。
【００５９】
Ｉ．実験結果
１．主観的品質比較
主観的品質比較では、ベースレイヤとしてＨ．２６４ＪＭ４、及びエンハンスメントレイヤとしてＲＦＧＳを用いた。特に主観的品質測定として、ＰＳＮＲを用いた。ベースラインシステムは再教育された表を伴う、ＭＰＥＧ−４ＦＧＳベースのビットプレーン符号化を用い、同じ評価条件で評価した。図８〜図１１は、ＰＳＮＲ比較を示す。上述したように、本発明に係るアルゴリズムは、平均的にベースラインシステムより０．５〜１．５ｄＢＰＳＮＲを改善する。
【００６０】
２．客観的品質比較
図１２は異なるアプローチの間の、主観的品質比較を示す。比較のためのアプローチは：（ａ）ラスタスキャンを伴う、ＭＰＥＧ−４ＦＧＳベースのビットプレーン符号化、（ｂ）ラスタスキャンを伴う、提案されるＣＡＢＡＣ、（ｃ）ビットプレーン内のリシャッフリング［４］を伴う、提案されるＣＡＢＡＣ、（ｄ）本特許で示される、増進された確率論的リシャッフリング方法を伴う、提案されるＣＡＢＡＣ、である。期待されたように、図１２（ａ）及び図１２（ｂ）は決定論的ラスタスキャンアプローチが不均一な品質分布を有することを示す。上部は滑らかな品質を示すが、下部は明らかなブロックする擬像を示す。それに対し図１２（ｃ）及び図１２（ｄ）は、全フレームに亘ってより均一な品質を示す。特に図１２（ｄ）は、増進された確率論的ビットリシャッフリングが、［４］のビットプレーン内に限定されたリシャッフリングより、さらに良いものを実行することを示す。他の一連の実験結果も、同様の性能を示す。
【００６１】
Ｊ．ビットリシャッフリングの用途
ビットリシャッフリングの概念は、レート歪みの最適化、主観的品質の改善及び関心領域の機能性のような、種々の目的に対する、係数、ブロック、領域またはサイクルレベルのリシャッフリングに拡張可能である。開示されたアイデアは、異なるプライオリティの割り当てに採用することができ、特定の用途に対する異なる粒度でのリシャッフリングを実行することができる。
【００６２】
ここで、ＭＰＥＧ−４パート１０Ａｍｄ．１拡大縮小可能なビデオ符号化の循環的ブロック符号化に対する、レート歪み特性及び主観的品質の改善における、開示されたビットリシャッフリングの拡張を示す。図１３は、ＭＰＥＧ−４パート１０Ａｍｄ．１拡大縮小可能なビデオ符号化における、循環的ブロック符号化の象徴的な表現を示す。示されるように、各々の変換ブロックは符号化サイクルにおいて、（ＥＯＢ，Ｒｕｎ，Ｌｅｖｅｌ）または装飾記号で等しく符号化される。ゼロでないもの以下の係数を伴うブロックは、ゼロでない以上の係数を有するブロックに先立って完了される。しかしながらレート歪み最適化の観点からは、エネルギーのより高いブロックはより高い符号化プライオリティを割り当てられるべきである。開示されたビットリシャッフリング方法は拡張され、異なる記号、ブロックまたは領域の重要性を区別するために適用されることができる。
【００６３】
図１４は、プライオリティを付された循環的なブロックの符号化の実施形態を示す。示されるように異なるブロックは、符号化サイクルにおいて不均等に符号化される。特にプライオリティ情報の送信を避けるために（オーバーヘッド）、ビットリシャッフリングに対する開示されたパラメータ推定方法と丁度同じように、符号化器と復号化器はブロックまたは記号のプライオリティ割り当てに対する同じ文脈を参照することができる。さらにプライオリティを付された循環的ブロック符号化は、関心領域の機能性のために用いられることができる。関心領域内のブロックは、より高いプライオリティで符号化されることができる。特にプライオリティ情報は、ビットストリーム内に埋め込まれるか、または文脈基準により暗示されることができる。
【００６４】
本発明は、ＭＰＥＧ−４ＦＧＳベースのビットプレーン符号化の、符号化効率と主観的品質の双方を改善するために、確率論的ビットリシャッフリング方法を伴う、新規な文脈に基づくバイナリ算術符号化を開示する。提案される方法はＭＰＥＧ−４ＦＧＳにおいてのみならず、ロバストＦＧＳ（ＲＦＧＳ）、Ｈ・Ｃ・フアン、Ｃ・Ｎ・ワング及びＴ・チャン「格子ベースの予測可能な漏れを用いた丈夫な精細粒度拡大縮小可能性」ＩＥＥＥトランザクションオンビデオ技術回路システム、Ｖｏｌ．１２、Ｎｏ．６、ｐｐ３７２−３８５、２００２年、進歩的なＦＧＳ（ＰＦＧＳ）、Ｆ・ウー、Ｓ・リー及びＹ・Ｑ・チャン、「効率的で進歩的な精細粒度拡大縮小可能なビデオの符号化のためのフレームワーク」ＩＥＥＥトランザクションビデオ技術回路システム、Ｖｏｌ．１１、ｐｐ３３２−３４４、２００１年等のような、他の進化したＦＧＳ方法においても用いられることができる。さらに確率論的ビットリシャッフリングの概念は、エンベッデドエントロピー符号化方法に適用することができる。
【００６５】
以上、本発明の望ましい実施形態を記述したが、しかしながら種々の変更と修正が、添付の請求項で定義される本発明の精神と範囲から逸脱することなくなされることが、当業者には自明であるべきである。
【図面の簡単な説明】
【００６６】
【図１】図１は、最有意ビットプレーンと最有意ビットの定義を示す、グラフである。
【図２】図２は、本発明に従う、有意ビットプレーン分割の一例を示す。
【図３】図３は、本発明に従う、有意ビットのコンテントインデックスの一例を示す。
【図４】図４は、不連続ラプラシアン分布及びΔＤの推定の一例を示す。
【図５】図５は、本発明に従う、確率論的レート分布最適化のための動的符号化フローの概観を示す。
【図６】図６は、本発明に従う、変換ブロックにおける新しいビットを含む例を示し、その最初の４つの符号化ビットは以下である：（ａ）ＢＰ３でのＤＣ係数の有意ビット、（ｂ）ＢＰ３でのＡＣ１の有意ビット、（ｃ）ＢＰ２でのＡＣ１の装飾ビット、（ｄ）ＢＰ３でのＡＣ２の有意ビット。
【図７】図７は、本発明に従う、確率論的ビットリシャッフリングの動的メモリ組織化の概観を示す。
【図８】図８は、フォアマンのＰＳＮＲ（主観的品質）の比較を示し、ここでベースレイヤは、Ｑｐ＝３８、フレームレート＝１０フレーム／秒、フレームサイズ＝ＣＩＦ（３５２×２８８）である。
【図９】図９は、テンピートのＰＳＮＲ（主観的品質）の比較を示し、ここでベースレイヤは、Ｑｐ＝３８、フレームレート＝１０フレーム／秒、フレームサイズ＝ＣＩＦ（３５２×２８８）である。
【図１０】図１０は、モバイルのＰＳＮＲ（主観的品質）の比較を示し、ここでベースレイヤは、Ｑｐ＝３８、フレームレート＝１０フレーム／秒、フレームサイズ＝ＣＩＦ（３５２×２８８）である。
【図１１】図１１は、ニュースのＰＳＮＲ（主観的品質）の比較を示し、ここでベースレイヤは、Ｑｐ＝３８、フレームレート＝１０フレーム／秒、フレームサイズ＝ＣＩＦ（３５２×２８８）である。
【図１２】図１２は、フォアマンシーケンスを有する主観的品質比較を示し、ここでベースレイヤは、Ｑｐ＝３８、フレームレート＝１０フレーム／秒であり、エンハンスメントレイヤは３８４ｋビット／秒で切り捨てられる。
【図１３】図１３は、ＭＰＥＧ−４パート１０Ａｍｄ．１拡大縮小可能なビデオ符号化における、循環的ブロック符号化の象徴的な表現を示す。
【図１４】図１４は、プライオリティを付された循環的なブロックの符号化の実施形態を示す。
【図１】
2007006469.tif 000021
【図２】
2007006469.tif 000022
【図３】
2007006469.tif 000023
【図４】
2007006469.tif 000024
【図５】
2007006469.tif 000025
【図６】
2007006469.tif 000026
【図７】
2007006469.tif 000027
【図８】
2007006469.tif 000028
【図９】
2007006469.tif 000029
【図１０】
2007006469.tif 000030
【図１１】
2007006469.tif 000031
【図１３】
2007006469.tif 000032
【図１４】
2007006469.tif 000033
【図１２】
2007006469.tif 000034