(57)【要約】  本明細書は、“２回パス”アプローチに基づいてビデオ・コーディングを改善することが可能なレート制御技術を記載する。１回目のパスは、その１回目のパスの統計値に基づいてビデオ系列のレート−歪特性を推定する目的のために第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列をコード化する。第２のＱＰのセットは、次に２回目のコーディング・パスのために規定されることができる。１回目のパスの推定されるレート−歪特性は、ビデオ系列の複数のフレーム間の歪を最小にする方法で２回目のパスのためのＱＰを選択するために使用される。その上、第２のＱＰのセットの選択が、最小化された品質変動で低い平均フレーム歪を実現するために実質的に最小にされた品質変動でフレームの品質を同様に最高にすることができる。
2009509477.tif 000002
【特許請求の範囲】
【請求項１】
１回目のコーディング・パスにおいて第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列のフレームをコード化するための手段；
該１回目のコーディング・パスの該コード化されたビデオ系列に関するレート−歪統計値を得るための手段；
該レート−歪統計値に基づいて該ビデオ系列のレート−歪特性を推定するための手段；及び
該ビデオ系列中の該フレームの２回目のコーディング・パスのための第２のＱＰのセットを選択するために該推定したレート−歪特性を使用して該２回目のコーディング・パスにおいて該ビデオ系列の該複数のフレーム間の品質変動を実質的に最小にするための手段
を具備するビデオ・コーディング・デバイス。
【請求項２】
該実質的に最小にされた品質変動で該フレームの品質を実質的に最高にするための手段をさらに具備する、請求項１のビデオ・コーディング・デバイス。
【請求項３】
該２回目のコーディング・パスにおいて該第２のＱＰのセットを使用して該ビデオ系列をコード化するための手段をさらに具備する、請求項１のビデオ・コーディング・デバイス。
【請求項４】
該推定するための手段は、該レート−歪統計値へのレート・モデルと歪モデルとの適用に基づいて該レート−歪特性を推定する、請求項１のビデオ・コーディング・デバイス。
【請求項５】
該実質的に最小にするための手段は、該品質変動を実質的に最小にするために該ビデオ系列に関するレート・バジェットにおける歪変動を実質的に最小にする、請求項１のビデオ・コーディング・デバイス。
【請求項６】
該実質的に最小にするための手段は、該品質変動を実質的に最小にするために該ビデオ系列に関するレート・バジェットにおける該第２のＱＰのセット中のＱＰ変動を実質的に最小にする、請求項１のビデオ・コーディング・デバイス。
【請求項７】
該実質的に最小にするための手段は、該品質変動を実質的に最小にするために該ビデオ系列に関するレート・バジェットにおける歪変動及びレート変動を実質的に最小にする、請求項１のビデオ・コーディング・デバイス。
【請求項８】
該第１のセット中の各ＱＰを規定するためのレート・バジェットを使用するグリーディ（greedy）アルゴリズムに基づいて該第１のＱＰのセットをダイナミックに選択するための手段をさらに具備する、請求項１のビデオ・コーディング・デバイス。
【請求項９】
該実質的に最小にするための手段は、該品質変動を実質的に最小にするために該ビデオ系列の該フレームに関係する最大歪値を実質的に最小にする、請求項１のビデオ・コーディング・デバイス。
【請求項１０】
該実質的に最小にするための手段は、該品質変動を実質的に最小にするために該ビデオ系列の該フレームに関係する歪値をプログラム可能な歪しきい値よりも下に減少させる、請求項１のビデオ・コーディング・デバイス。
【請求項１１】
１回目のコーディング・パスにおいて第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列のフレームをコード化すること；
該コード化されたビデオ系列に関するレート−歪統計値を得ること；
該レート−歪統計値に基づいて該ビデオ系列のレート−歪特性を推定すること；及び
該ビデオ系列中の該フレームの２回目のコーディング・パスのための第２のＱＰのセットを選択するために該推定したレート−歪特性を使用して該２回目のコーディング・パスにおいて該ビデオ系列の複数の該フレーム間の品質変動を実質的に最小にすること
を具備する方法。
【請求項１２】
該実質的に最小にされた品質変動で該フレームの品質を実質的に最高にすることをさらに具備する、請求項１１の方法。
【請求項１３】
該２回目のコーディング・パスにおいて該第２のＱＰのセットを使用して該ビデオ系列をコード化することをさらに具備する、請求項１１の方法。
【請求項１４】
該レート−歪特性を推定することは、該レート−歪統計値にレート・モデルと歪モデルとを適用することを備える、請求項１１の方法。
【請求項１５】
該品質変動を実質的に最小にすることは、該ビデオ系列に関するレート・バジェットにおける歪変動を実質的に最小にすることを備える、請求項１１の方法。
【請求項１６】
該品質変動を実質的に最小にすることは、該ビデオ系列に関するレート・バジェットにおける該第２のＱＰのセット中のＱＰ変動を実質的に最小にすることを備える、請求項１１の方法。
【請求項１７】
該品質変動を実質的に最小にすることは、該ビデオ系列に関するレート・バジェットにおける歪変動及びレート変動を実質的に最小にすることを備える、請求項１１の方法。
【請求項１８】
該第１のセット中の各ＱＰを規定するレート・バジェットを使用するグリーディ・アルゴリズムに基づいて該第１のＱＰのセットをダイナミックに選択することをさらに具備する、請求項１１の方法。
【請求項１９】
該品質変動を実質的に最小にすることは、該ビデオ系列の該フレームに関係する最大歪値を最小にすることを備える、請求項１１の方法。
【請求項２０】
該品質変動を実質的に最小にすることは、該ビデオ系列の該フレームに関係する歪値をプログラム可能な歪しきい値よりも下に減少させることを備える、請求項１１の方法。
【請求項２１】
ビデオ・コーディング・デバイス中で実行されるときに下記を行うプログラム・コードを具備するコンピュータ読み取り可能な媒体であって、該プログラム・コードは：
１回目のコーディング・パスにおいて第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列のフレームをコード化する；
該１回目のコーディング・パスの該コード化されたビデオ系列に基づいてビデオ系列に関するレート−歪統計値を得る；
該レート−歪統計値に基づいて該ビデオ系列のレート−歪特性を推定する；及び
該ビデオ系列中の該フレームの２回目のコーディング・パスのための第２のＱＰのセットを選択するために該推定したレート−歪特性を使用して該２回目のコーディング・パスにおいて該ビデオ系列の複数の該フレーム間の品質変動を実質的に最小にする
上記プログラム・コードである、コンピュータ読み取り可能な媒体。
【請求項２２】
該実質的に最小にされた品質変動で該フレームの品質を実質的に最高にするために第２のＱＰのセットを選択するプログラム・コードをさらに具備する、請求項２１のコンピュータ読み取り可能な媒体。
【請求項２３】
該２回目のコーディング・パスにおいて該第２のＱＰのセットを使用して該ビデオ系列をコード化するプログラム・コードをさらに具備する、請求項２１のコンピュータ読み取り可能な媒体。
【請求項２４】
該プログラム・コードは、該レート−歪特性を推定するために該レート−歪統計値にレート・モデルと歪モデルとを適用する、請求項２１のコンピュータ読み取り可能な媒体。
【請求項２５】
該プログラム・コードは、該品質変動を実質的に最小にするために該ビデオ系列に関するレート・バジェットにおける歪変動を実質的に最小にする、請求項２１のコンピュータ読み取り可能な媒体。
【請求項２６】
該プログラム・コードは、該品質変動を実質的に最小にするために該ビデオ系列に関するレート・バジェットにおける該第２のＱＰのセット中のＱＰ変動を実質的に最小にする、請求項２１のコンピュータ読み取り可能な媒体。
【請求項２７】
該プログラム・コードは、該品質変動を実質的に最小にするために該ビデオ系列に関するレート・バジェットにおける歪変動及びレート変動を実質的に最小にする、請求項２１のコンピュータ読み取り可能な媒体。
【請求項２８】
該プログラム・コードは、該第１のセット中の各ＱＰを規定するレート・バジェットを使用するグリーディ・アルゴリズムに基づいて該第１のＱＰのセットをダイナミックに選択する、請求項２１のコンピュータ読み取り可能な媒体。
【請求項２９】
該プログラム・コードは、該品質変動を実質的に最小にするために該ビデオ系列の該フレームに関係する最大歪値を実質的に最小にする、請求項２１のコンピュータ読み取り可能な媒体。
【請求項３０】
該プログラム・コードは、該品質変動を実質的に最小にするために該ビデオ系列の該フレームに関係する歪値をプログラム可能な歪しきい値よりも下に減少させる、請求項２１のコンピュータ読み取り可能な媒体。
【請求項３１】
ビデオ系列を記憶するビデオ・メモリ；
ビデオ・コーディングの期間に該ビデオ系列の少なくとも一部を記憶するローカル・メモリ；及び
下記により該ビデオ系列をコード化するビデオ・コーダ、
を具備し、該ビデオ・コーダは、
１回目のコーディング・パスにおいて第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列のフレームをコード化すること；
該コード化されたビデオ系列に関するレート−歪統計値を得ること；
該レート−歪統計値に基づいて該ビデオ系列のレート−歪特性を推定すること；
該ビデオ系列中の該フレームの２回目のコーディング・パスのための第２のＱＰのセットを選択するために該推定したレート−歪特性を使用して該２回目のコーディング・パスにおいて該ビデオ系列の複数の該フレーム間の品質変動を実質的に最小にすること；及び
該２回目のコーディング・パスにおいて該第２のＱＰのセットを使用して該ビデオ系列をコード化すること
を実行する上記ビデオ・コーダである、ビデオ・コーディング・デバイス。
【請求項３２】
該ビデオ・コーダは、動き推定器、動き補償器、残差コーダ、及びレート制御ユニットを含む、ここにおいて、該動き推定器、該動き補償器、及び該残差コーダは、該１回目のコーディング・パスにおいて該第１のＱＰのセットを使用して該ビデオ系列をコード化し、そして該２回目のコーディング・パスにおいて該第２のＱＰのセットを使用して該ビデオ系列をコード化する、そしてここにおいて、該レート制御ユニットは、該第２のＱＰのセットを選択するために、該レート−歪統計値を取得し、レート−歪特性を推定し、そして品質変動を実質的に最小にする、請求項３１のビデオ・コーディング・デバイス。
【請求項３３】
該ビデオ系列を取り込むビデオ取込みデバイス、及び該２回目のコーディング・パスの該コード化されたビデオ系列を送信するための送信機、をさらに具備する、請求項３２のビデオ・コーディング・デバイス。
【請求項３４】
該ビデオ・コーダは、空間推定器、フレーム内予測ユニット、残差コーダ、及びレート制御ユニットを含む、ここにおいて、該空間推定器、フレーム内予測ユニット、及び残差コーダは、該１回目のコーディング・パスにおいて該第１のＱＰのセットを使用して該ビデオ系列をコード化し、そして該２回目のコーディング・パスにおいて該第２のＱＰのセットを使用して該ビデオ系列をコード化する、そしてここにおいて、該レート制御ユニットは、該第２のＱＰのセットを選択するために、該レート−歪統計値を取得し、レート−歪特性を推定し、そして品質変動を実質的に最小にする、請求項３１のビデオ・コーディング・デバイス。
【請求項３５】
１回目のコーディング・パスにおいて第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列のフレームをコード化すること；
該コード化されたビデオ系列に関するレート−歪統計値を得ること；
該レート−歪統計値に基づいて該ビデオ系列のレート−歪特性を推定すること；
該ビデオ系列中の該フレームの２回目のコーディング・パスのための第２のＱＰのセットを選択するために該推定したレート−歪特性を使用して該２回目のコーディング・パスにおいて該ビデオ系列の複数の該フレーム間の品質変動を実質的に最小にすること；及び
該２回目のコーディング・パスにおいて該第２のＱＰのセットを使用して該ビデオ系列をコード化すること
によって該ビデオ系列をコード化するビデオ・コーダ。
【発明の詳細な説明】
【関連文献】
【０００１】
本出願は、係争中の米国特許仮出願番号第６０／７１９，７７５号、２００５年９月２２日出願、に優先権を主張する。
【技術分野】
【０００２】
本発明は、ディジタル・ビデオ処理に係り、そして特に、ビデオ系列のレート制御されたコーディングに関する。
【背景技術】
【０００３】
ディジタル・ビデオ能力は、広範囲のデバイスへと組み込まれることが可能であり、それはディジタル・テレビ、ディジタル直接放送システム、無線通信デバイス、個人ディジタル補助装置（ＰＤＡ：personal digital assistants）、ラップトップ・コンピュータ、デスクトップ・コンピュータ、ディジタル・カメラ、ディジタル記録デバイス、セルラ電話機又は衛星無線通信電話機、及びその他を含む。ディジタル・ビデオ・デバイスは、フル動画ビデオ系列を製作し、修正し、伝送し、記憶し、記録し、そして再生する際に、従来のアナログ・ビデオ・システムに対して著しい改善を提供することが可能である。
【０００４】
複数の異なるビデオ符号化規格が、ディジタル・ビデオ系列をコーディングするために制定されてきている。動画エキスパート・グループ（ＭＰＥＧ：Moving Picture Expert Group）は、例えば、ＭＰＥＧ−１，ＭＰＥＧ−２及びＭＰＥＧ−４を含む複数の規格を開発している。その他の規格は、国際電気通信連合（ＩＴＵ：International Telecommunication Union）Ｈ．２６３規格、カルフォルニア州キューパーティーノ市のアップル・コンピュータにより開発されたクイックタイム（QuickTime（登録商標））技術、ワシントン州レドモンド市のマイクロソフト株式会社により開発されたウィンドウズ（登録商標）のためのビデオ、インテル株式会社により開発されたインディオ（Indeo（登録商標））、ワシントン州シアトル市リアルネットワーク株式会社からのリアルビデオ（RealVideo（登録商標））、スーパーマック株式会社により開発されたシネパック（Cinepak（登録商標））を含む。さらに、ＩＴＵ  Ｈ．２６４規格及び複数の専有規格を含む新たな規格が、出現し続けそして発展し続けている。
【０００５】
複数のビデオ・コーディング規格は、圧縮された方式でデータをコーディングすることによりビデオ系列の伝送レートの改善を可能にする。圧縮は、ビデオ・フレームの効率的な伝送のために伝送される必要があるデータの全体量を削減することができる。大部分のビデオ・コーディング規格は、例えば、圧縮なしで実現されることが可能なものよりも狭い帯域幅を通してビデオ及び画像の伝送を容易にするために設計されたグラフィックス圧縮及びビデオ圧縮技術を利用する。ＭＰＥＧ規格及びＩＴＵ  Ｈ．２６３とＩＴＵ  Ｈ．２６４規格は、例えば、フレーム間圧縮を提供するために、時間的な相関又はフレーム間相関と呼ばれる連続する複数のビデオ・フレーム間の類似性を利用するビデオ・コーディング技術をサポートする。そのようなフレーム間圧縮は、動き推定及び動き補償コーディング技術を介して一般的に実現される。それに加えて、あるビデオ・コーディング技術は、ビデオ・フレームを圧縮するために、空間相関又はフレーム内相関と呼ばれるフレーム内部の類似性を利用することができる。
【０００６】
複数のレート制御技術が、ビデオ・コーディングのために開発されてきている。レート制御技術は、ビデオ系列のリアル・タイム伝送を容易にするために特に重要であるが、非リアル・タイム・コーディング設定においても同様に使用されることができる。レート制御に関して、コーディング技術は、フレーム当りのコード化されるビット数を絶えず調節することができる。特にレート制御は、ビデオ系列が所定のレートで効率的にコード化されることが可能であり、それゆえ割り当てられた帯域幅を経由して伝送されることを確実するために、フレーム当りのコード化されるビット数を制限することができる。コーディング技術がビデオ系列の場面の変化に敏感でない場合には、ビデオ系列のリアル・タイム伝送のためのビット・レートは、場面の変化につれて著しく変動することがある。同様に、（無線ビデオ電話のような）ある種のアプリケーションに関して、帯域幅の利用可能性は、あるビデオ系列がコード化されようとしている間に変化することがある。これらの理由又はその他の理由のために、レート制御技術は、コーディングの期間にフレーム当りに使用されるビット数を絶えず調節するために使用されることができる。
【発明の開示】
【サマリー】
【０００７】
本明細書は、ビデオ・コーディングを改善することが可能なレート制御技術を記載する。特に、本明細書は、“２回パス”コーディングに基づいた複数のレート制御技術を記載するが、追加のパスが同様に使用されることができる。１回目のパスは、その１回目のパスの統計値に基づいてビデオ系列のレート−歪特性を推定する目的のために第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列をコード化する。第２のＱＰのセットは、次に２回目のコーディング・パスのために定められることができる。１回目のコーディング・パスがビデオ系列のレート−歪特性の推定値を提供するので、２回目のパスのためのＱＰの選択は、フレーム間の依存性を考慮することによって改善されることができる。
【０００８】
様々な実施形態及び変形が本明細書中で説明される。しかしながら、この開示に整合する２つの基本的な選択肢が、一般的に提案される。第１のケースでは、１回目のパスの推定されるレート−歪特性は、ビデオ系列のフレームの歪を最小にする方法で２回目のパスのためのＱＰを選択するために使用される。第２のケースでは、１回目のパスの推定レート−歪特性は、ビデオ系列の複数のフレーム間の品質変動を最小にする方法で２回目のパスのためのＱＰを選択するために使用され、そしてしかも、低い平均フレーム歪を実現するために最小化された品質変動において品質を最高にすることができる。
【０００９】
１つの実施形態では、本開示は、ビデオ・コーディング・デバイスを提供し、それは１回目のコーディング・パスにおいて第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列のフレームをコード化するための手段、該１回目のコーディング・パスの該コード化されたビデオ系列に関するレート−歪統計値を得るための手段、該レート−歪統計値に基づいて該ビデオ系列のレート−歪特性を推定するための手段、及び該推定したレート−歪特性に基づいて該ビデオ系列中の該フレームの２回目のコーディング・パスのために第２のＱＰのセットを選択するための手段、を具備する。
【００１０】
別の１つの実施形態では、本開示は、ビデオ・コーディング・デバイスを提供し、それは、１回目のコーディング・パスにおいて第１の量子化パラメータ（ＱＰ）のセットを使用してビデオ系列のフレームをコード化するための手段、該コード化されたビデオ系列に関するレート−歪統計値を得るための手段、該レート−歪統計値に基づいて該ビデオ系列のレート−歪特性を推定するための手段、及び該ビデオ系列中の該フレームの２回目のコーディング・パスのために第２のＱＰのセットを選択するために該推定したレート−歪特性を使用して２回目のコーディング・パスにおいて該ビデオ系列の複数の該フレーム間の品質変動を実質的に最小にするための手段、を具備する。
【００１１】
本明細書中に記述されるレート制御コーディング技術は、ハードウェア、ソフトウェア、ファームウェア、又はこれらの任意の組み合わせでビデオ・コーディング・デバイスにおいて実装されることができる。ソフトウェアにおいて実装される場合には、ソフトウェアは、ビデオ・コーディングのために使用するプログラム可能なプロセッサのような、プロセッサにおいて実行されることができる。本技術を実行するソフトウェアは、コンピュータ読み取り可能な媒体中に最初は記憶されることができ、そしてそのようなレート制御されたビデオ・コーディングを実行するためにプロセッサにロードされ、そして実行されることができる。
【００１２】
様々な実施形態のさらなる詳細は、添付された図面及び以下の説明に記述される。その他の特徴、目的及び利点は、詳細な説明及び図面から、そして特許請求の範囲から明らかにされるであろう。
【詳細な説明】
【００１３】
本明細書は、ビデオ・コーディングのためのレート制御技術を説明する。説明される技術は、“２回パス”アプローチに基づき、そこでは１回目のコーディング・パスが、ビデオ系列の特性を推定するために使用され、そしてその推定された特性は、次に２回目のパスのための量子化パラメータ（ＱＰ：quantization parameter）の選択の際に改善するために使用される。本発明は、ビデオ系列のレート−歪特性のフレーム依存性のある種の特性を利用することができる。特に、本発明は、多くのケースでは（特に、本明細書で検討されるケースでは）、現在のフレームのレートと歪は、直前のフレームにおいて使用されるＱＰに大きく依存することを認めるが、直前のフレームの前のフレームに対して使用されるＱＰは、現在のフレームのレートと歪にほとんど影響しないことを認める。これらの認識を使用して、計算量の著しい削減が、近似へとレート・モデル及び歪モデルを本質的に単純化することによってコーディング・デバイスにおいて実現されることができる。
【００１４】
１回目のコーディング・パスは、１回目のパスの統計値に基づいてビデオ系列のレート−歪特性を推定する目的のために第１のＱＰのセットを使用してビデオ系列をコード化する。第１のＱＰのセットは、任意の方式で、例えば、各フレームに同じＱＰを割り当てることにより、又はいわゆる“グリーディ（greedy）”アルゴリズムを使用することにより、選択されることができ、そのグリーディ・アルゴリズムは、ＱＰを決定するためにレート・バジェットを使用し、そして次に、それぞれのその後のＱＰを規定するために残りのフレーム全体にわたりそのレート・バジェットを再割り当てする。第１のＱＰのセットが１回目のコーディング・パスに対してどのように選択されるか又は決定されるかに拘らず、ビデオ系列に関するレート−歪統計値は、１回目のコーディング・パスにより得られることができる。
【００１５】
１回目のコーディング・パスの後で、ビデオ系列のレート−歪特性は、そのレート−歪統計値に基づいて推定されることができる。レート−歪特性が推定される方法は、異なる実施形態では変わることがあるが、一般に１回目のコーディング・パスにおいて得られたレート−歪統計値に対するレート・モデル及び歪モデルの適用を含む。レート−歪特性が推定された後で、これらの特性は、ビデオ系列中のフレームの２回目のコーディング・パスのための第２のＱＰのセットを選択するために使用される。２回目のコーディング・パスは、次に、ビデオ系列を最終的にコード化するために使用されることができ、そして２回目のコーディング・パスのために選択されたＱＰは、そのようなコーディングの際にビデオ品質の向上を実現することができる。
【００１６】
様々な実施形態及び変形が、本明細書中に記載される。しかしながら、本明細書に整合する２つの基本的な選択肢が、一般的に提案される。第１のケースでは、１回目のパスの推定されるレート−歪特性は、ビデオ系列のフレームの歪を最小にする方法で２回目のパスのためのＱＰを選択するために使用されることができる。第２のケースでは、１回目のパスの推定レート−歪特性は、ビデオ系列の複数のフレーム間の品質変動を最小にする方法で２回目のパスのためのＱＰを選択するために使用される。歪の最小化が平均してより良い総合コーディングを結果としてもたらすことができるが、品質変動の最小化は、急激な品質変化に起因する望ましくないフリッカリング問題を低減する又は除去することができる。これらの２つのケースの組み合わせは、この開示により同様に予想される。
【００１７】
図１は、具体例のビデオ・コーディング・デバイス１０を例示するブロック図である。ビデオ・コーディング・デバイス１０は、ビデオ・データをコード化することが可能でありそして送信することが可能であるディジタル・ビデオ・デバイスの一部を形成することができる。ビデオ・データは、ビデオ・カメラから取り込まれることができるか、ビデオ・アーカイブから検索されることができるか、又は別の方法で得られることができる。コーディング・デバイス１０は、例えは、ディジタル・テレビ、ディジタル直接放送システム、無線通信デバイス、個人ディジタル補助装置（ＰＤＡ：personal digital assistants）、ラップトップ・コンピュータ、デスクトップ・コンピュータ、ディジタル・カメラ、ディジタル記録デバイス、セルラ電話機又は衛星無線通信電話機、又はビデオ電話方式（ＶＴ：video telephony）能力を有するいずれかの電気通信デバイスのような、デバイスに搭載されることができる。コーディング・デバイス１０は、例えば、ＭＰＥＧ−４、ＩＴＵ−Ｔ  Ｈ．２６３、ＩＴＵ−Ｔ  Ｈ．２６４、又は量子化されたビデオ・コーディングのためにＱＰ選択を必要とするいずれかのビデオ・コーディング規格、に準拠することができる。コーディング・デバイス１０は、動き推定及び動き補償のようなフレーム間コーディングをサポートすることができ、そして同様に、空間推定及びフレーム内コーディングのために使用する内部予測コーディング技術のような、別の技術をサポートすることができる。
【００１８】
図１に示されるように、コーディング・デバイス１０は、ビデオ系列をコード化するためのビデオ・コーディング装置１２、及びそのようなコーディングの前と後のビデオ系列を記憶するためのビデオ・メモリ２０を含む。デバイス１０は、しかも、コード化された系列を別のデバイスに送信するための送信機２２、及びおそらく、ビデオ系列を取り込みそしてメモリ２０中にその取り込まれた系列を記憶するための、ビデオ・カメラのようなビデオ取込みデバイス１８’を含むことができる。コーディング・デバイス１０の様々な素子は、通信バス１５を介して通信的に接続されることができる。種々のフィルタのような様々な他の素子、又は別の素子は、同様にコーディング・デバイス１０中に含まれることができるが、単純化のために具体的に図示されていない。図１に示された構造は、単に具体例であり、それは本明細書中で説明される技術が様々な別の構造を用いて与えられることができるためである。
【００１９】
ビデオ・メモリ２０は、一般的に比較的大きなメモリ空間を備える。ビデオ・メモリ２０は、例えば、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ：dynamic random access memory）、又はＦＬＡＳＨメモリを備えることができる。その他の例では、ビデオ・メモリ２０は、不揮発性メモリ又はいずれかの他のデータ記憶デバイスを備えることができる。
【００２０】
ビデオ・コーディング装置１２は、移動無線電話機のためのいわゆる“チップ・セット”を備えることができ、ハードウェア、ソフトウェア、ファームウェアの任意の組み合わせを、及び／又は１又はそれより多くのマイクロプロセッサ、ディジタル信号プロセッサ（ＤＳＰ：digital signal processor）、用途特定集積回路（ＡＳＩＣ：application specific integrated circuit）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ：field programmable gate array）、又はこれらの様々な組み合わせを含むことができる。ビデオ・コーディング装置１２は、一般にローカル・メモリ１８に接続されたビデオ・コーダ１４を含む。ビデオ・コーダ１４は、ディジタル・ビデオ・データをエンコードしそしてデコードするためのエンコーダ／デコーダ（ＣＯＤＥＣ）を備えることができる。ローカル・メモリ１８は、ビデオ・メモリ２０と比較して小さくそしてより早いメモリ空間を備えることができる。一例として、ローカル・メモリ１８は、シンクロナス・ダイナミック・ランダム・アクセス・メモリ（ＳＤＲＡＭ：synchronous dynamic random access memory）を備えることができる。ローカル・メモリ１８は、ビデオ・コーディング装置１２の別のコンポーネントに集積された“オン−チップ”メモリを備えることができ、プロセッサに集中するコーディング・プロセスの期間にデータへの非常に高速なアクセスを提供する。しかしながら、メモリ２０と１８は、同じメモリ・パーツへと統合されることができる、又は複数の別の構成で与えられることができる。
【００２１】
本明細書中に説明されるように、ビデオ・コーダ１４は、“２回パス”コーディング・アプローチを実行し、そこでは１回目のコーディング・パスは、ビデオ系列の特性を推定するために使用され、そして２回目のコーディング・パスは、その推定された特性を使用して、コーディングの品質を向上させるために２回目のパスにおいて使用するＱＰの選択に改良を与える。レート制御ユニット３０は、ＱＰ選択プロセスを取り扱い、それは１回目のコーディング・パスにおいて推定された特性を使用する。レート制御ユニット３０により実行される技術は、レート・モデル及び歪モデルを近似へと本質的に単純化することによって計算量の著しい削減を実現するために、ビデオ系列のレート−歪特性を推定することによってフレーム依存性の利点を利用することが可能である。
【００２２】
レート制御ユニット３０は、１回目のパスの統計値に基づいてビデオ系列のレート−歪特性を推定する目的のために１回目のコーディング・パスにおいて第１のＱＰのセットを適用する。１回目のコーディング・パスの後で、レート制御ユニット３０は、レート−歪統計値に基づいてビデオ系列のレート−歪特性を推定する。レート制御ユニット３０は、これらの推定したレート−歪特性を使用して、ビデオ系列中のフレームの２回目のコーディング・パスのための第２のＱＰのセットを選択する。２回目のコーディング・パスは、次に、そのビデオ系列を最終的にコード化するために使用されることができ、そして２回目のコーディング・パスのために選択されたＱＰは、そのようなコーディングにおいてビデオ品質の改善を実現することができる。本明細書にしたがって、推定された特性は、２回目のパスにおいてＱＰ選択を改善することを可能にする方法でフレーム依存性を定量化することができる。
【００２３】
各コーディング・パスに関して、所定のビデオ・フレームのコーディングの期間に、コード化されようとしている現在のビデオ・ブロックは、ビデオ・メモリ２０からローカル・メモリ１８へロードされることができる。予測ビデオ・ブロックの位置を決めるために使用する検索空間は、同様にビデオ・メモリ２０からローカル・メモリ１８にロードされることができる。検索空間は、１又はそれより多くの前のビデオ・フレーム（又は引き続くフレーム）のピクセルのサブセットを備えることができる。選ばれたサブセットは、コード化されようとしている現在のビデオ・ブロックにぴったりと符合する予測ビデオ・ブロックの識別のために有望な位置として事前に同定されることができる。
【００２４】
ローカル・メモリ１８は、コード化されようとしている現在のビデオ・ブロック及び検索空間をロードされる。動き推定器／空間推定器２４は、予測ビデオ・ブロックを同定するために現在のビデオ・ブロックを検索空間中の様々なビデオ・ブロックと比較する。動き推定器／空間推定器２４は、一般に、フレーム間コーディングのために動き推定を実行する動き推定器、フレーム内コーディングのために空間推定を実行する空間推定器、又は動き推定と空間推定とを実行することが可能な複合ユニット、を表す。一般に、予測ビデオ・ブロックは、フレーム間相関（又はフレーム内相関）の目的のために現在のビデオ・ブロックと適切な符合を与えるために見つけられる候補ビデオ・ブロックであり、それは最もぴったりと符合する候補ビデオ・ブロックであり得る。予測ビデオ・ブロックは、現在のビデオ・ブロックと比較して最小の差異値を有するビデオ・ブロックを同定するために、動き推定プロセスの期間に評価される複数の候補ビデオ・ブロックのうちの１つである。
【００２５】
コード化されようとしている現在のビデオ・ブロックとメモリ１８の検索空間中の候補ビデオ・ブロックとの間の比較を実行するために、動き推定器／空間推定器２４は、絶対差の総和（ＳＡＤ：sum of absolute difference）技術、二乗差の総和（ＳＳＤ：sum of squared difference）技術、又は他の比較技術を実行することができる。このようにして、動き推定器／空間推定器２４は、異なる候補ビデオ・ブロックに対する差異値を決定することができる。より小さな差異値は、一般に候補ビデオ・ブロックが良く符合すること、そしてそれゆえより大きな差異値を生じる他の候補ビデオ・ブロックよりも動き推定コーディングの際に使用するためのさらに良い候補であることを示す。予測ビデオ・ブロックは、適切な符合が一旦見つけられると、同定されることができる。
【００２６】
一旦、コード化されようとしているビデオ・ブロックに対して、予測ビデオ・ブロックが動き推定器／空間推定器２４によって同定されると、動き補償器／内部予測ユニット２６は、残差（residual）を生成する。残差は、コード化されようとしている現在のブロックと動き推定又は空間推定によって同定される予測ビデオ・ブロックとの間の差を示すデータのブロックである。動き補償器／内部予測ユニット２６は、一般に動き補償器、内部予測ユニット、又は複合ユニットを表し、動き補償器はフレーム間コーディングのために動き補償を実行し、内部予測ユニットはフレーム内コーディングのために空間補償を実行し、そして複合ユニットはフレーム間コーディング又はフレーム内コーディングが使用されようとしているかどうかに応じて動き補償と内部予測とのいずれかを実行することができる。動き補償器／内部予測ユニット２６は、動きベクトルを使用して予測ブロックをフェッチすることができ、そして次に、その予測ブロックを入力ブロックから引き算して残差を生成する。残差は、一般的に、元々のビデオ・ブロックよりも実質的に少ないデータを含み、それは差異ブロックにより表される。
【００２７】
動き補償器／内部予測ユニット２６が残差を生成した後で、残差コーダ２８は、１又はそれより多くの残差コーディング・ステップを実行することができ、例えば、離散余弦変換（ＤＣＴ：discrete cosine transform）ジグ−ザグ・スキャニング、ラン長コーディング、可変長（ハフマン）コーディング、又は所定のコーディング規格において使用されるいずれかの他のプロセス、である。非常に多くの他の残差コーディング・ステップが、同様に実行されることができる。
【００２８】
レート制御ユニット３０は、本明細書と矛盾のない２つの選択肢のうちの１つを実行することができる。第１のケースでは、レート制御ユニット３０は、１回目のパスの推定レート−歪特性を使用して、ビデオ系列の全てのフレームにわたり歪を最小にする方法で２回目のパスのためのＱＰを選択する。第２のケースでは、レート制御ユニット３０は、１回目のパスの推定レート−歪特性を使用して、その系列のフレームの品質変動を最小にする方法で２回目のパスのためにＱＰを選択する。歪の最小化が平均としてより良い総合コーディングという結果をもたらすとはいえ、品質変動の最小化は、急激な品質変化に起因するフリッカリング問題を減少させるため又は除去するために望まれることがある。これらの２つの選択肢のそれぞれの詳細は、以下にさらに詳細に述べられる。
【００２９】
図２−１５の検討は、一般に第１のアプローチの概要を示し、そこでのゴールは、コード化されたビデオ系列の歪を実質的に最小にすることであり、一方で、図１６−２６は、一般に第２のアプローチの概要を示し、そこでのゴールは、コード化されたビデオ系列の品質変動を実質的に最小にすることである。しかしながら、図２−２６のいずれかに関して検討されるいずれの詳細も、各アプローチの１又はそれより多くの態様が本明細書にしたがった組み合わせで同様に使用されることができるので、いずれかのアプローチに限定されるように解釈されるべきでない。本明細書中で議論されるテスト系列の種々の実験グラフでは、テスト系列は、一般にコーディング品質を試験するためそして比較するために一般的に使用されるクォーター共通画像フォーマット（ＱＣＩＦ：Quarter Common Image Format）系列である。
【００３０】
図２は、本明細書にしたがったレート制御されたビデオ・コーディングのための技術を説明するフロー図である。図２に示されるように、ビデオ・コーダ１４は、第１のＱＰのセットを使用してビデオ系列のフレームをコード化する（４０）。レート制御ユニット３０は、次に、１回目のコーディング・パスのコード化されたビデオ系列に関するレート−歪統計値を得る（４１）。ビデオ・コーダ１４の様々な他のユニット２４，２６と２８は、レート制御ユニット３０によって同定された第１のＱＰのセットを使用して１回目のコーディング・パスにおいて提供されることができる。第１のＱＰのセットは、様々な異なる方法で、又はいずれかのレート制御アルゴリズムにしたがって選択されることができる。一例では、第１のＱＰのセットは、いわゆる“グリーディ（greedy）”アルゴリズムに基づいてレート制御ユニット３０によってダイナミックに選択され、そのグリーディ・アルゴリズムは、系列中のフレームの数に関係するレート・バジェット（rate budget）に基づいてフレームに対するＱＰを選択するが、その後、残りのレート・バジェットを残りのフレーム全体にわたり再割り当てする。別の例では、同じＱＰが、事前に選択されることができ、そして１回目のパスにおいて全てのフレームに対して使用されることができ、そのケースでは、第１のＱＰのセット中のＱＰは、互いに同じである。
【００３１】
１回目のコーディング・パスの後で、レート制御ユニット３０は、１回目のコーディング・パスによって得られたレート−歪統計値に基づいてビデオ系列のレート−歪特性を推定する（４２）。一般に、レート−歪特性を推定するプロセスは、レート−歪統計値にレート・モデルと歪モデルとを適用することを含む。具体例の数学モデルが、下記に非常に詳細に説明され、それは近似のために計算の複雑さを低減することができ、しかも非常に良い推定値と良いコーディング結果を与える。再び、推定される特性は、２回目のパスにおいて改善されたＱＰ選択を可能にする方法でフレーム依存性を定量化することが可能である。
【００３２】
レート制御ユニット３０は、次に、レート−歪特性に基づいて２回目のコーディング・パスのための第２のＱＰのセットを選択する（４３）。第２のＱＰのセットは、第１のＱＰのセットとは異なり、そしてコーディングの品質を向上させるために選択される。１回目のコーディング・パスは、低い方の品質のコーディング・パスであり得るが、正確なモデル化に適用するために必要な情報を提供し、そしてビデオ系列をコーディングする際のフレーム間依存性を説明することができる。一例では、レート制御ユニット３０は、下記にさらに詳細に論じられるように、推定レート−歪特性にラグランジュ緩和演算を実行することによって第２のＱＰのセットを選択する。このケースでは又は類似のケースでは、第２のＱＰのセットの選択は、ビデオ系列中のフレームの歪を実質的に最小にすることを含むことができる。いずれにせよ、一旦、レート制御ユニット３０が第２のＱＰのセットを選択すると、ビデオ・コーダ１４は、第２のＱＰのセットを使用してビデオ系列をコード化する（４４）。
【００３３】
ビデオ・コーディングにおいて、基本的な問題は、ビデオ系列の最良の総合品質を実現するために、複数のフレームの間でビットを効率的に割り当てること、又は各フレームのためのＱＰを効率的に選択することである。この問題の困難さは、フレームのコーディング依存性に、そして指数関数的な数のノードを含んでいる候補空間を検索するために結果としてのコストに、主に起因する。本明細書の１つの実施形態では、２回目のパスのコーディングにおける実際的なレートと歪状態を近似するために推定モデルの集合を使用する解が、提案される。そのモデルは、多くのケースでは現在のフレームのレートと歪は、その前のフレームの量子化レベルに大きく依存すること、そして最後のフレームよりも早い前のフレームのＱＰ選択は現在のフレームの性能にほとんど影響しないこと、の観測に基づいている。モデルと観測は、問題の候補空間の著しい削減を可能にする。さらに、ラグランジュ緩和とダイナミックなプログラミングを使用することによって、拘束された問題は、非拘束問題へと変換されることが可能であり、そして最短パス検索アルゴリズムを使用することにより解かれることができる。実験結果は、ある従来のＣＯＤＥＣにおいて使用される“グリーディ”フレーム−レベル・レート制御アルゴリズムと比較して１．７ｄＢまでの著しい向上を示している。
【００３４】
多くの従来のレート制御方式は、リアル・タイム・コーディング・アプリケーションのために設計されており、そしてグリーディ・フレーム−レベル・ビット割当て方針に適合する。そのグリーディ・フレーム−レベル・ビット割当て方針は、今後のフレームが一様に分散されたテクスチャの複雑さを有するはずであると仮定する。それゆえ、グリーディ・フレーム−レベル・ビット割当て方針は、残りのビットを今後の複数のフレームの間で等しく割り当てる。
【００３５】
不幸にして、良いフレーム・ビット割当てを得ることは、平凡な課題ではない、その理由は、フレームのレート−歪（Ｒ−Ｄ：rate-distortion）関数が前のコード化されたフレームについての量子化パラメータ（ＱＰ）選択に依存するためである。言い換えると、全体のビデオ系列に関するグローバル・レート−歪関数の生成は、フレーム依存性のために非常に困難である。
【００３６】
本明細書は、正確なレート及び歪推定モデルに基づくフレーム−レベル・レート制御アルゴリズムを提案する。それは、フレーム歪が前のフレームの量子化のレベルに大きく依存することを観測している。それに加えて、２回目のパス・コーディングの間の歪は、統計によって近似されることができ、その統計は、例えば、（同じレベルの量子化を使用する）１回目のパスにおける歪の関数、１回目のパスにおける動き補償された残差のエネルギー、及び１回目のパスにおける前のフレーム歪である。直前のフレームより前のフレームの量子化選択が現在のフレームのフレーム歪にほとんど影響を与えないことが、同様に観測される。上記の観測及び各フレームに対する推定されたρ−ＱＰとＤ−ＱＰの表（それはメモリ１８中に記憶されることができる）を用いて、ラグランジュ緩和技術は、各フレームに対して望ましいＱＰ選択を見つけるために使用されることができる。値ρは、フレーム中の非ゼロ量子化ＤＣＴ係数の数を表し、ＱＰは、量子化パラメータを表し、そしてＤは歪を表す。
【００３７】
１つの実施形態にしたがって、問題は、１回目のパス・コーディングの期間に集められた統計量に基づいて、ビデオ系列の最良総合品質を実現するための取り組みの際に各フレームに対してＱＰを選択することとして規定されることができる。１回目のパス・コーディングをどのように行うかの問題は実際的に意味があるけれども、問題を単純化するために、“グリーディ”フレーム−レベル・ビット割当てアルゴリズムが１回目のパスにおいてフレームをコード化するために使用されることを仮定することができる。当然ながら、他の１回目のパス・コーディング技術が、同様に、本開示の２回パス技術にしたがって使用されることができる。下記では、フレーム・ビット・レートは、ρの関数としてモデル化され、そのρはフレーム中の非ゼロ量子化ＤＣＴ係数の数である。そのようなわけで、ビット・レートは、次式により表されることができる：
Ｒ＝Ａρ＋Ｂ                                                      （式１）
ここで、ＡとＢは、定数のモデル化パラメータである。Ａは、非ゼロ量子化ＤＣＴ係数をコード化するために必要な平均ビット数を表すことができ、そしてＢは、非テクスチャ情報、例えば、予測モード及び動きベクトル、のために使用するビットを表すことができる。
【００３８】
Ｎが処理されるビデオ系列中の全フレーム数を表すとする。｛Ｑ＾ｉ｝はＱＰを表す。｛Ａ＾ｉ｝は、非ゼロ量子化ＤＣＴ係数当りの平均ビット数を表す。｛Ｂ＾ｉ｝は、非テクスチャ情報をコーディングするためのビット数を表す。｛ρ＾ｉ｝は、非ゼロ量子化ＤＣＴ係数の数を表す。｛σ＾ｉ２｝は、動き補償された残差のエネルギーを表す。｛Ｄ＾ｉ｝１回目のパス・コーディングの結果のｉ番目のフレームの歪を表し、そして（ｉ＝１，２，．．．，Ｎ）は、系列のフレームを同定する。“＾”によって同定される変数は、１回目のコーディング・パスによって推定される変数である。識別子“＾”のない変数は、同じように名前を付けられた２回目のパス変数であり、例えば、近似値又は解かれようとしている２回目のパス変数である。
【００３９】
Ｒｂｕｄｇｅｔがビデオ系列に関する全ビット・バジェットを表すとし、そして｛Ｑｉ｝，｛Ｒｉ｝と｛Ｄｉ｝が２回パス・コーディングの際のｉ番目のフレームのＱＰ、ビット・レート、及び歪を表すとする。それゆえ、問題は、次式によって表されることができる
【数１】
2009509477.tif 000003
【００４０】
ＲｉとＤｉの両者は、予測コーディングが使用されるという事実のためにＱ１，Ｑ２，．．．，Ｑｉの関数である。それに加えて、Ｒｉ（Ｑ＾１，Ｑ＾２，．．．，Ｑ＾ｉ）＝Ａ＾ｉρ＾ｉ＋Ｂ＾ｉ，そしてＤｉ（Ｑ＾１，Ｑ＾２，．．．，Ｑ＾ｉ）＝Ｄ＾ｉ（ｉ＝１，．．．，Ｎ）である。
【００４１】
フレーム依存性は、前のフレームのＱＰ選択が現在のフレームのレート−歪性能への主な影響を有するという観測に基づいて著しく単純化されることができる。言い換えると、ｉ−テュープル（i-tuple:ｉ個の要素からなる）関数Ｒｉ（Ｑ１，Ｑ２，．．．，Ｑｉ）とＤｉ（Ｑ１，Ｑ２，．．．，Ｑｉ）は、２−テュープル関数Ｒｉ（Ｑｉ−１，Ｑｉ）とＤｉ（Ｑｉ−１，Ｑｉ）とに約されることができ、その理由は、Ｑ１，Ｑ２，．．．，Ｑｉ−２の選択が、ｉ番目のフレームに関するレート及び歪についての著しい変化を生じさせないためである。この観測は、図３−６に示されるように、“フットボールＱＣＩＦビデオ系列”と呼ばれる系列について検証されてきている。
【００４２】
特に、図３は、４５と表示された（ＱＰ１＝１０、ＱＰ２＝１０）、４６と表示された（ＱＰ１＝１０、ＱＰ２＝２０）、４７と表示された（ＱＰ１＝２０、ＱＰ２＝１０）、及び４８と表示された（ＱＰ１＝２０、ＱＰ２＝２０）を使用する系列の４番目のフレームに対するレート−歪曲線の実験結果をプロットする。図４は、５１と表示された（ＱＰ１＝１０、ＱＰ２＝１０）、５２と表示された（ＱＰ１＝１０、ＱＰ２＝２０）、５３と表示された（ＱＰ１＝２０、ＱＰ２＝１０）、及び５４と表示された（ＱＰ１＝２０、ＱＰ２＝２０）を使用する系列の４番目のフレームに対するレート−ＱＰ曲線の実験結果をプロットする。図５は、５６と表示された（ＱＰ１＝１０、ＱＰ２＝１０）、５７と表示された（ＱＰ１＝１０、ＱＰ２＝２０）、５８と表示された（ＱＰ１＝２０、ＱＰ２＝１０）、及び５９と表示された（ＱＰ１＝２０、ＱＰ２＝２０）を使用する系列の４番目のフレームに対するロー−ＱＰ曲線の実験結果をプロットする。図６は、６１と表示された（ＱＰ１＝１０、ＱＰ２＝１０）、６２と表示された（ＱＰ１＝１０、ＱＰ２＝２０）、６３と表示された（ＱＰ１＝２０、ＱＰ２＝１０）、及び６４と表示された（ＱＰ１＝２０、ＱＰ２＝２０）を使用する系列の４番目のフレームの歪−ＱＰ曲線の実験結果をプロットする。
【００４３】
図３−６の結果により例示される実験に関して、１番目のフレーム（Ｉ−フレーム）のＱＰは５に設定され、そしてＱＰ組み合わせ（１０，１０）、（１０，２０）、（２０，１０）及び（２０，２０）は、２番目及び３番目のフレームのために使用される。図３−６から、ＱＰ１（２番目のフレームのためのＱＰ）の選択が４番目のフレームのレート及び歪についてほとんど影響を与えないが、ＱＰ２（３番目のフレームのためのＱＰ）の選択が４番目のフレームの性能に直接影響することが示される。それゆえ、いかなる重要な品質も犠牲にすることなく、連続するフレームの依存性だけを考慮することによって問題を単純化することができる。
【００４４】
それゆえ、Ｑｉ−１とＱｉの候補の全ての組み合わせに対するＲｉ（Ｑｉ−１，Ｑｉ）とＤｉ（Ｑｉ−１，Ｑｉ）の表を手に入れる場合には、式２の問題は、さらに易しく解かれることができる。以下の議論では、正確な推定モデルは、１回目のパス・コーディングにおいて得られた情報を使用することにより、レート及び歪関数を近似するために提案される。次に、式２の問題は、ラグランジュ緩和を使用して解かれることが可能であり、問題を非拘束問題に変換する。ラグランジュ緩和を使用して問題を変換した後で、非拘束問題は、グラフ理論問題へとマッピングされることができ、そして最短パス検索アルゴリズムを使用して解かれることができる。
【００４５】
歪推定モデルに関して、１回目のコーディング・パスにおいて、ｉ番目のフレームについて、ｑ＝１，２，．．．，３１に対してＤｉ（Ｑ＾ｉ−１，ｑ）の全ての値を得ることが可能であることが、注目される。それに加えて、σ＾ｉ２（Ｑ＾ｉ−１）の値も、同様に得ることができる。Ｚ．Ｈｅ，Ｙ．Ｋｉｍ及びＳ．Ｋ．Ｍｉｔｒａにより提案された歪モデル、“ρ−ドメイン・ソース・モデリングを介したＤＣＴビデオ・コーディングのための低遅延レート制御（Low-Delay Rate Control for DCT Video Coding viaρ-Domain Source Modeling）”、ＩＥＥＥ学会報、ビデオ技術のための回路及びシステム、９２８−９４０ページ、２００１年８月、に基づいて、次式を得る：
【数２】
2009509477.tif 000004
【００４６】
そして
【数３】
2009509477.tif 000005
【００４７】
ここで、αｉはモデル・パラメータである。
【００４８】
図５から、ロー−ＱＰ曲線が、現在のフレームのＱＰによって主に導かれることを観測することができる。言い換えると、ρｉ（Ｑ＾ｉ−１，Ｑｉ）≒ρｉ（Ｑｉ−１，Ｑｉ）は、Ｑｉが（例えば、１５より大きい）大きな数を割り当てられる場合に対して特に成り立つ。用語ローは、本明細書中で定義されるように用語ρを呼ぶ。式３と４から、次式を得ることができる：
【数４】
2009509477.tif 000006
【００４９】
式５は、“フットボールＱＣＩＦビデオ系列”と呼ばれる系列の初めから３つのフレームをコーディングすることにより実験的に検証される。この実験の結果は、図７と図８に図示される。系列の１番目のフレーム（Ｉ−フレーム）は、ＱＰ＝５を使用してコード化された、そして２番目のフレーム（Ｐ−フレーム）は、それぞれＱＰ＝５，１０，１５，２０と３０を使用してコード化された。図７は、各設定に対する３番目のフレームのＤ−ＱＰ曲線を示す。図７において、設定（Ｉ−フレーム、Ｐ−フレーム）に対する結果は、次のように番号を付けられる：（５，５）は７１と番号を付けられ、（５，１０）は７２と番号を付けられ、（５，１５）は７３と番号を付けられ、（５，２０）は７４と番号を付けられ、そして（５，３０）は７５と番号を付けられる。
【００５０】
図８において、２番目のフレーム（Ｐ−フレーム）に対してＱＰ＝１０を設定することにより生成される３番目のフレームの実際のＤ−ＱＰ曲線は、２番目のフレームに対するＱＰ＝５，１５，２０と３０を使用するケースにより、そして式５を使用することにより生成されるデータから推定されるＤ−ＱＰ曲線と比較される。図８では、設定（Ｉ−フレーム、Ｐ−フレーム）に対する結果は、次のように番号を付けられる：実際の（５，１０）は８１と番号を付けられ、予測された（５，５）は８２と番号を付けられ、予測された（５，１５）は８３と番号を付けられ、予測された（５，２０）は８４と番号を付けられ、そして予測された（５，３０）は８５と番号を付けられる。この結果は、式５が非常に正確であることを示す。
【００５１】
式５のσｉ２（Ｑｉ−１）を推定するために、Ｍはフレーム中の全ピクセルを表すために使用され、ｙｋ（ｋ＝１，．．．，Ｍ）はフレーム中のｋ番目のオリジナル・ピクセルを、ｘｋは前のフレーム中のｋ番目のオリジナル・ピクセルを、ｘ＾ｋと
【数５】
2009509477.tif 000007
【００５２】
は１回目のパス・コーディングと２回目のパス・コーディングにおける前のフレームからの対応する動き補償されたピクセルを表す。ここで、特別なケースが考察され、そこでは、全てのビデオ・ブロック（例えば、マクロブロック）がゼロ動きベクトルを使用する、それはｘ＾ｋと
【数６】
2009509477.tif 000008
【００５３】
が１回目のパス・コーディングと２回目のパス・コーディングにおける前のフレームの対応する再構成されたピクセルであることを意味する。このケースでは、
【数７】
2009509477.tif 000009
【００５４】
同様に、
【数８】
2009509477.tif 000010
【００５５】
式６と式７は、次式をもたらす：
【数９】
2009509477.tif 000011
【００５６】
それは、画像データの分布が、ガウス分布又はラプラス分布になると仮定される場合に
【数１０】
2009509477.tif 000012
【００５７】
という理由のためである。
【００５８】
それゆえ、
【数１１】
2009509477.tif 000013
【００５９】
そして、したがって：
【数１２】
2009509477.tif 000014
【００６０】
式６から、レート関数のフレーム間依存性が適度に低く、そして線形関係が動き補償された残差の偏差と参照フレームのコーディング・エラーとの間に存在することは、観測されることができる。しかしながら、現在のフレームのレートがその前のフレームのＱＰ選択にある依存性を有することが、観測されることができる。
【００６１】
｛Ａｉ｝，｛Ｂｉ｝，｛ρｉ｝を非ゼロ量子化ＤＣＴ係数当りの平均ビット数、非テクスチャ情報をコーディングするためのビット数、及び２回目のパス・コーディングの結果として非ゼロ量子化ＤＣＴ係数の数として表す。明らかに、Ｒｉ＝Ａｉρｉ＋Ｂｉである。下記の本文では、これらのパラメータは、次のように経験的にモデル化される：
【数１３】
2009509477.tif 000015
【００６２】
式１１では、ρｉの値は、動き補償された残差のエネルギー（それは前のフレームのＱＰに依存する）及び現在のフレームＱＰに依存する。（図３−６の結果により例示される同じ実験のように）“フットボールＱＣＩＦ”系列をコーディングすることにより、そして２番目のフレームと３番目のフレームの両者をＱＰ＝１０に設定しそして式１１を使用して生成された１回パス・データから（２番目のフレームに対してＱＰ＝１０、３番目のフレームに対してＱＰ＝２０を用いて）４番目のフレームのロー−ＱＰ曲線を推定することにより、式１１の精度は、検証されることができる。図９に示されたように、推定されたロー−ＱＰ曲線９１は、実際のロー−ＱＰ曲線９２に非常に近い。同様に、非テクスチャ・ビットの数（Ｂｉ）は、式１２によってモデル化されるので、残差のエネルギー及び現在のフレームのＱＰに同様に依存する。式１３を使用して、ρ＾ｉの値に基づいてＡｉの値を制御することができる。Ａｉの値は、高ビット・レートのケースでは非常に安定である。しかしながら、ρ＾ｉが非常に小さいときに、Ａ＾ｉは、過度に大きくなるはずである。
【００６３】
ここまでは、本明細書は、Ｑｉ−１とＱｉの候補の全ての組み合わせに対してＲｉ（Ｑｉ−１，Ｑｉ）とＤｉ（Ｑｉ−１，Ｑｉ）とを推定するためのモデルを展開してきた。このモデルが正確であると仮定すると、式２の問題に対する所望の解を展開することが可能である。特に、ラグランジュ緩和アプローチ使用することが可能であり、そしてそれは制約された問題の凸包近似に導く。
【００６４】
次式としてラグランジュ・コスト関数を定義する：
【数１４】
2009509477.tif 000016
【００６５】
ここで、λはラグランジュ乗数である。λ＊が存在し、その結果
【数１５】
2009509477.tif 000017
【００６６】
がＲ（｛Ｑｉ｝＊）＝Ｒｂｕｄｇｅｔに導く場合には、｛Ｑｉ｝＊が式２に対する所望の解である。それゆえ、式２を解くタスクは、コスト関数Ｊλ（｛Ｑｉ｝）を最小にする非制約問題に対する所望の解を見出し、そしてその制約を満足する近似のラグランジュ乗数を選択する簡単なタスクと等価である。
【００６７】
問題を解くためのアルゴリズムを実行するために、コスト関数Ｇｋ（Ｑｋ−１，Ｑｋ）を定義することができ、それはＱｋ−１とＱｋが（ｋ−１）番目とｋ番目のフレームに対する判断ベクトルであることが与えられと、ｋ番目のフレームを含むそこまでの最小全ビット・レートと歪とを表す。このケースでは、ｋ＝Ｎ、ＧＮ（ＱＮ−１，ＱＮ）は、全てのフレーム対する最小全ビット・レートと歪とを表し、そしてそれゆえ、
【数１６】
2009509477.tif 000018
【００６８】
である。
【００６９】
効率的なアルゴリズムを導くための１つの鍵となる観測は、（ｋ−２）番目と（ｋ−１）番目のフレームに対する判断ベクトルＱｋ−２とＱｋ−１及びコスト関数Ｇｋ−１（Ｑｋ−２，Ｑｋ−１）が与えられると、次の判断ベクトルＱｋの選択は、前の判断ベクトルＱ１，Ｑ２，．．．，Ｑｋ−３の選択とは無関係である、という事実である。これは、コスト関数が次式として帰納的に表されることができることを意味する：
【数１７】
2009509477.tif 000019
【００７０】
上記のコスト関数の帰納的な表示は、過去のステップに従属するプロセスの今後のステップを作り、それはダイナミック・プログラミングの基礎である。
【００７１】
問題は、方向性非循環グラフ（ＤＡＧ：directed acyclic graph）において最短経路を見出すグラフ理論問題へと変換されることができる。そのようなアルゴリズムは、指数関数的な演算上の複雑さを有する網羅的な検索アルゴリズムよりもはるかに効率的である。
【００７２】
実験は、複数のビデオ・チップについて行われた、そしてそのような実験の結果は、下記の文書において検討される。最初に、実験は、推定された歪、Ａ、Ｂとρを２回目のパス・コーディングにおけるそれらの実際の値とを比較することにより提案されたレート及び歪モデルの精度を検証した。図１０−１３に示されるように、８０ｋｂｐｓにおける“親子（Mother and Daughter）”系列として呼ばれる系列をコーディングする際の結果は、提案された推定モデルが極めて正確であることを立証する。
【００７３】
図１０は、コード化された“親子”系列の推定された歪１０１と実際の歪１０２のグラフである。図１１は、コード化された“親子”系列に関するＡの推定された値（１１１と番号を付けられる）をＡの実際の値（１１２と番号を付けられる）と比較する。図１２は、コード化された“親子”系列に関するρの推定された値（１２１と番号を付けられる）をρの実際の値（１２２と番号を付けられる）と比較する。図１３は、コード化された“親子”系列に関するＢの推定された値（１３１と番号を付けられる）をＢの実際の値（１３２と番号を付けられる）と比較する。実際の値に対して相対的な推定された値の精度は、図１０−１３から明白である。
【００７４】
第２の実験では、“親子”ＱＣＩＦ系列は、４０ｋｂｐｓから１２０ｋｂｐｓのビット・レートの範囲でコード化された、そしてその結果は、２つの別のアプローチと比較された：（１）フレーム−レベル・グリーディ・レート制御、それはこれから来るフレームが一様に分布するテクスチャの複雑さを有し、そしてそれゆえ、それは残りのフレームを今後の複数のフレームの間に等しく割り当てる、と仮定する；（２）１回目のパスからのモデル・パラメータを使用する２回パス・レート制御。図１４に示される結果は、本明細書中のアプローチが全てのビット・レート範囲で他の２つのアプローチに対して０．５−０．７ｄＢの利益を得ることを示す。図１４では、フレーム−レベル・グリーディ・レート制御アプローチは、１４１と番号を付けられ、１回パス・モデル・パラメータを再使用するアプローチは、１４２と番号を付けられ、そして本明細書中で規定される正確なモデルを用いる提案されたアプローチは、１４３と番号を付けられる。提案されたアプローチの結果の改善は、図１４において明らかである。
【００７５】
第３の実験では、３つのビデオ場面：高いアクティビティ（早い動作）を含んでいる“ステファン”と呼ばれる標準ＱＣＩＦテスト系列の最初の１００フレーム、低いアクティビティ（遅い動作）を含んでいる“コンテナ” と呼ばれる標準ＱＣＩＦテスト系列の最初の１００フレーム、及び中間のアクティビティ（局部的な顔の動き）を含んでいる“カーフォーン” と呼ばれる標準ＱＣＩＦテスト系列の最初の１００フレーム、をシミュレーションすることによって構成することにより、ビデオ・クリップは、異なるコンテントの複雑性を有する様々なセグメントを含む。提案されたアプローチは、前の実験で使用した２つの別のアルゴリズムと比較して利益をもたらした。その結果は、図１５に示され、そして提案されたアルゴリズムが他のアプローチに対して最大１．７ｄＢの有意なゲインを有することを示す。この改善は、ビット・レートが増加するときに減少する。提案されたアルゴリズムが全体のビデオ・クリップに対してもっと最適のビット割当て解を見出すために候補空間の端から端まで検索することの利点を有するという理由で、改善が期待される。図１５では、フレーム−レベル・グリーディ・レート制御アプローチは、１５１と番号を付けられ、１回パス・モデル・パラメータを再使用するアプローチは、１５２と番号を付けられ、そして本明細書中で規定される正確なモデルを有する提案されたアプローチは、１５３と番号を付けられる。提案されたアプローチの結果の改善は、図１５において明らかである。
【００７６】
上記に概要を示された技術と図３−１５に例示された結果は、本明細書にしたがったモデル−ベースの２回パス・レート制御アルゴリズムの１つの実施形態を示す。再び、前のフレームの量子化パラメータ選択が現在のフレームのレート−歪性能への主な影響を有することを観測することによって、フレーム依存性問題は、上手く単純化され、そしてサイズ候補空間は、指数関数から多項式へと大きく削減された。その後で、１組の正確なモデルが実際のコーディングの間のレート及び歪状態を近似するために展開された。これらのモデルは、候補空間を生成するため、そして問題をグラフ理論問題へとマッピングするための能力を直接的に利用可能にする。ラグランジュ緩和とダイナミック・プログラミングを用いて、元々の制約問題は、非制約問題へと変換され、そして最短経路検索アルゴリズムにより解かれた。実験結果は、他の既存のレート制御アルゴリズムと比較して最大１．７ｄＢの有意なゲインを示す。
【００７７】
図１６は、品質変動がビデオ系列のフレームに対して最小にされる本明細書の別の１実施形態にしたがった２回パス・レート制御されたビデオ・コーディング技術を説明するフロー図である。図２と同様に、図１６は、図１のビデオ・コーディング・デバイス１０の関係で説明される。図１６に示されるように、ビデオ・コーダ１４は、第１のＱＰのセットを使用してビデオ系列のフレームをコード化する（１６０）。レート制御ユニット３０は、次に１回目のコーディング・パスのコード化されたビデオ系列に関するレート−歪統計値を得る（１６１）。ビデオ・コーダ１４の様々な他のユニット２４，２６と２８は、レート制御ユニット３０によって同定された第１のＱＰのセットを使用して１回目のコーディング・パスにおいて与えられることができる。第１のＱＰのセットは、様々な異なる方法で選択される、又は任意のレート制御アルゴリズムにしたがって選択されることができる。１つの例では、第１のＱＰのセットは、いわゆる“グリーディ”アルゴリズムに基づいてレート制御ユニット３０によってダイナミックに選択され、そのアルゴリズムは系列内のフレーム数に関係するレート・バジェットに基づいてフレームのためのＱＰを選択するが、次に残りのレート・バジェットを残りの複数のフレームにわたり再割り当てする。他の１つの例では、同じＱＰが、１回目のパスにおいて全てのフレームに対して事前に選択されることができ、そして使用されることができ、そのケースでは、第１のＱＰのセット中のＱＰは、互いに同じである。しかしながら、別の技術が、１回目のコーディング・パスのための第１のＱＰのセットを規定するために使用されることができる。
【００７８】
１回目のコーディング・パスの後で、レート制御ユニット３０は、１回目のコーディング・パスによって得られたレート−歪統計値に基づいてビデオ系列のレート−歪特性を推定する。一般に、レート−歪特性を推定するプロセスは、レート−歪統計値にレート・モデルと歪モデルとを適用することを含む。レート制御ユニット３０は、次に、そのレート−歪特性を使用して品質変動を実質的に最小にすることにより２回目のコーディング・パスのための第２のＱＰのセットを選択する（１６３）。第２のＱＰのセットを選択する際に、レート制御ユニット３０は、最小化した品質変動を有する低い平均フレーム歪を実現するために、実質的に最小化した品質変動でフレームの品質を同様に実質的に最高にすることができる。
【００７９】
第２のＱＰのセットは、第１のＱＰのセットとは異なり、そしてコーディングの品質を向上するために選択される。このケースでは、第２のＱＰのセットは、全系列にわたり歪を最小にしないことがあるが、ビデオ品質を劣化させることがある別の問題を扱う。具体的に、図１６の技術は、異なるフレームのコーディング品質における変動を最小にする、例えば、本技術はレート−歪変動を最小にする。このようにして、フリッカリング問題は、低減される又は除去されることができる。そうでなければ、フリッカリングは、コーディング品質が２つの連続するフレーム間で急激に変化するときに生じることがある。一旦、レート制御ユニット３０が品質変動を実質的に最小にすることにより（そしてその最小化した品質変動で品質をおそらく最高にすることにより）第２のＱＰのセットを選択してしまうと、ビデオ・コーダ１４は、第２のＱＰのセットを使用してビデオ系列をコード化する（１６４）。
【００８０】
図２の技術のように、図１６の技術では、１回目のコーディング・パスは、低い方の品質のコーディング・パスであり得るが、正確なモデリングを適用するために必要な情報を提供し、そしてビデオ系列のコーディングの際にフレーム間依存性を考慮することができる。レート−歪の最小化は、多種多様な方法で実行されることができる。１つの例では、品質変動を実質的に最小化することは、ビデオ系列に関するレート・バジェットにおける歪変動を実質的に最小化することを含む。他の１つの例では、品質変動を実質的に最小化することは、ビデオ系列に関するレート・バジェットにおける第２のＱＰのセット中のＱＰ変動を実質的に最小化することを含む。しかも他の１つの例では、品質変動を実質的に最小化することは、ビデオ系列に関するレート・バジェットにおける歪変動及びレート変動を実質的に最小化することを含む。さらに他の１つの例では、品質変動を実質的に最小化することは、ビデオ系列のフレームに関係する最大歪値を最小化することを含む。さらに他の１つの例では、品質変動を実質的に最小化することは、ビデオ系列のフレームに関係する歪値をプログラム可能な歪しきい値よりも下に減少させることを含む。この実施形態のさらなる詳細は、下記の文章において説明される。
【００８１】
上記に概要を示された技術のように、下記の文章において概要を示される技術は、２回パス・フレーム−レベル・レート制御方式を指向した一定−ビデオ−品質を提供する。しかしながら、下記の文章では、本技術は、最小最大（ＭＩＮＭＡＸ）歪基準に基づく。この枠組みで、ビデオ系列に関するビット・バジェットが与えられると、コーダは、各フレームに対するコーディング・パラメータをダイナミックに調節して、ピークの最大フレーム歪を最小にする、それは再構成されるビデオ系列の一定品質を間接的に保証する。この枠組みは、指定される変動制約でコード化された系列内のフレーム−レベル・ビット・レート変動の制御を同様に可能にする。しきい値の繰り返し調節に基づいて、コーダは、ビット・レート制約を満足するコーディング・パラメータのセットを見出すことができる。ダイナミック・プログラミングは、コーディング効率を改善するために適用される。この提案される枠組みは、ビット・バジェットで制約されるビデオ通信アプリケーションに対する良い選択を提供することができ、そのゴールは、許容可能なフレーム毎のビデオ品質（すなわち、良い平均ＰＳＮＲ）を維持しつつ、最低の可能な歪であるがほとんど一定の歪を実現することである。しかしながら、上記したように、品質変動を実質的に最小にするプロセスは、同様に複数の別の方法で行われることができる。
【００８２】
下記は、正確なレート・モデル及び歪推定モデルを展開して、２回目のパス・コーディングにおける実際的なレート及び歪ステータスを近似する。モデルは、再び、現在のフレームのレート及び歪がその前のフレームのＱＰに大きく依存すること、そして直前のフレームよりも早い時期の前のフレームのＱＰ選択が現在のフレームの性能にほとんど影響しないことの観測に基づく。そのモデル及び観測は、２回パス・アプローチにおけるＱＰ選択のプロセスの計算上の複雑さの著しい減少を可能にする。その問題をグラフ理論問題へとマッピングすることによって、最短経路アルゴリズムが、最適な解を効率的に見出すために適用される。提案される技術は、シミュレーションされそして試験されてきている。実験結果は、グリーディ・フレーム−レベル・レート制御アルゴリズムに比較してピーク信号対ノイズ比（ＰＳＮＲ：peak signal to noise ratio）変動の最大７０％までの著しい減少を示している。
【００８３】
“総合ビデオ品質”に関して複数の代わりの意味があり、２、３だけの名前をあげると、例えば、フレーム当りの良い平均品質、一定のフレーム品質、そして優れた認識できるビデオ品質である。しかしながら、一般に、全ての態様を考慮に入れるために利用可能な標準化され統一されたビデオ品質測定はない。一般に、最小平均歪（ＭＩＮＡＶＥ）基準が、ビデオ歪を測定するために多くの場合使用される。フレーム−レベル・レート制御アルゴリズムは、デコードされたビデオ系列の最良の平均ＰＳＮＲを実現するための試みにおいて提案されてきている。しかしながら、ＭＩＮＡＶＥ基準を用いる従来の解は、時々、フレーム全体にわたり一様でない歪に導き、それは複数のフレーム間の急激な品質の変化に起因する“フリッカリング”問題を引き起こす。ある最近の研究は、許容できるフレーム当りのＰＳＮＲを維持しつつ、系列全体にわたる歪変化をどのように減少させるかについて焦点を当てている。しかしながら、これらのアプローチは、厳しい遅延制約を有するリアル・タイム・アプリケーションのために主に設計されており、そしてそれゆえ、その性能は多くの場合良くない。
【００８４】
ＭＩＮＡＶＥアプローチに対する代わりのアプローチとして、最小最大（ＭＩＮＭＡＸ）歪アプローチは、そのゴールがほぼ一定の歪を実現することであるアプリケーションに対して良い選択であり得る。このアプローチの背後にある原理は、最大ソース歪を最小にすることによって、１つのソース歪も極端に大きくなることがなく、そしてそれゆえ、全体の品質は、極めて一定である。本発明は、ＭＩＮＭＡＸ基準に基づく２回パス一定品質レート制御アルゴリズムを提案する。正確なレート及び歪推定モデルは、フレーム−レベルＱＰ選択のために設定される。そのモデルは、再び、フレーム歪がその前のフレームの量子化レベルに大きく依存する、ところが前のフレームよりも早いフレームの量子化選択が現在のフレームのフレーム歪にほとんど影響しないことの観測に基づく。本明細書で説明されるモデルでは、２回目のパス・コーディングの間の実際の歪は、（同じＱＰを使用する）１回目のパスにおける歪の関数と、１回目のパスにおける動き補償された残差のエネルギーと、そして１回目のパスにおける前のフレームの歪とにより近似されることができる。それに加えて、本明細書は、提案したレート制御方式のレート変動を減少させることの影響を検討し、そして両方のタスクを達成するための解を提案する。
【００８５】
提案した技術は、ハイブリッドの枠組みを表現することができ、その枠組みは、最小最大歪基準を使用してコーディング・パラメータをダイナミックに選択することによりＰＳＮＲとビット・レートの両者において低い変動を達成することが可能である。しかも、その枠組みは、フレーム・レート及び歪についての正確な推定モデルのセットとともに働くことができる。計算における近似は、サンプリングと空間を指数関数から多項式へと減少させることによって、コーディング性能を効率的に高速化することができる。
【００８６】
この実施形態における問題は、１回パス・コーディングの間に集められた統計値に基づいて、許容可能な総合平均ＰＳＮＲを維持しつつそしてあるレート変動制約を満足しつつ、最小の品質変動を有するデコードされたビデオ系列を実現するために、各フレームに対する量子化パラメータを選択することである。１回パス・コーディングをどのようにして行うかの問題が直接関係するとはいえ、問題を単純化するために、グリーディ・フレーム−レベル・ビット割当てアルゴリズムが１回目のパスにおいてフレームをコード化するために使用されることを仮定することができる。しかしながら、別のＱＰ選択技術が、１回目のパスにおいて代わりに使用されることができる。
【００８７】
フレーム内の非ゼロ量子化ＤＣＴ係数の数である、ρの関数としてのフレーム・ビット・レートに関するモデルは、次式により表されることができる：
Ｒ＝Ａρ＋Ｂ，
ここで、ＡとＢは一定のモデリング・パラメータであり、そしてＡは非ゼロ量子化ＤＣＴ係数をコード化するために必要な平均ビット数を表し、そしてＢは非テクスチャ情報、例えば、予測モード及び動きベクトル、によるビットを表す。
【００８８】
Ｎが処理されたビデオ系列内の全フレーム数を表すとし、そして｛Ｑ＾ｉ｝，｛Ａ＾ｉ｝，｛Ｂ＾ｉ｝，｛ρ＾ｉ｝，｛σ＾ｉ２｝，及び｛Ｄ＾ｉ｝（ｉ＝１，２，．．．，Ｎ）がそれぞれ量子化パラメータＱＰ、非ゼロ量子化ＤＣＴ係数当りの平均ビット数、非テクスチャ情報をコーディングするためのビット数、非ゼロ量子化ＤＣＴ係数の数、動き補償された残差のエネルギー、及び１回目のパス・コーディングの結果としてｉ番目のフレームの歪、を表すとする。上記で使用されたように、“＾”によって識別される変数は、１回目のコーディング・パスによって推定される変数である。識別子“＾”のない変数は、一般に２回目のパス変数であり、例えば、近似値又は解かれようとしている２回目のパス変数である。
【００８９】
Ｒｂｕｄｇｅｔがビデオ系列に関する全ビット・バジェットを表すとし、Ｒｄｅｖ＿ｔｈｒｅｓｈｏｌｄが実際のフレーム・ビット・レートの平均ビット・レートからの最大の許容可能な偏差を表すとし、そして｛Ｑｉ｝，｛Ｒｉ｝と｛Ｄｉ｝が２回パス・コーディングの際のｉ番目のフレームのＱＰ、ビット・レート、及び歪を表すとする。それゆえ、問題に対する表示は：
【数１８】
2009509477.tif 000020
【００９０】
ここで、ＲｉとＤｉの両者は、予測コーディングの性質のためにＱ１，Ｑ２，．．．，Ｑｉの関数である。それに加えて、Ｒｉ（Ｑ＾１，Ｑ＾２，．．．，Ｑ＾ｉ）＝Ａ＾ｉρ＾ｉ＋Ｂ＾ｉ，そしてＤｉ（Ｑ＾１，Ｑ＾２，．．．，Ｑ＾ｉ）＝Ｄ＾ｉ（ｉ＝１，．．．，Ｎ）である。
【００９１】
式１７では、歪の平均と偏差の両者は、系列に関する所与のビット・バジェットにおいて最小にされる。しかしながら、式１７は、解を保証しない、その理由は、平均歪を最小にするＱＰ選択が歪の偏差を最小にできないことがあるため、そしてその逆も同様である。重み付けアプローチは、式１７の問題を次式の形式へと変形するために使用されることができる：
【数１９】
2009509477.tif 000021
【００９２】
ここで、α∈［０，１］は、重み付けされた因子であり、それは歪の平均と偏差の相対的な重要性を規定する。予想されるように、αを増加させることは、増加した平均歪のコストにおける歪偏差を減少させる。しかしながら、αの決定は、ユーザの情報交換なしでは極めて困難である。
【００９３】
この開示にしたがって、問題は、次式により形式化されることができる：
【数２０】
2009509477.tif 000022
【００９４】
そのうえ、問題は、次式のようにさらに単純化されることができる：
【数２１】
2009509477.tif 000023
【００９５】
それは、目標の結果が一定のビデオ品質を実現することであるという仮定に基づき、そして１回目のパスと２回目のパスとの間の平均歪に大きな違いを予想しないという仮定に基づく。
【００９６】
再び、前のフレームのＱＰ選択が現在のフレームのレート−歪性能に重大な影響を持たないという観測に基づいて、フレーム依存性は単純化されることが可能である。言い換えると、本開示にしたがったフレーム依存性の観測が与えられると、ｉ−テュープル関数Ｒｉ（Ｑ１，Ｑ２，．．．，Ｑｉ）とＤｉ（Ｑ１，Ｑ２，．．．，Ｑｉ）は、２−テュープル関数Ｒｉ（Ｑｉ−１，Ｑｉ）とＤｉ（Ｑｉ−１，Ｑｉ）とに約すことができ、その理由は、Ｑ１，Ｑ２，．．．，Ｑｉ−２の選択が、ｉ番目のフレームに関するレート及び歪についての著しい変化を生じさせないはずであるためである。それゆえ、Ｒｉ（Ｑｉ−１，Ｑｉ）とＤｉ（Ｑｉ−１，Ｑｉ）の表が、Ｑｉ−１とＱｉの候補の全ての組み合わせに対して得られる場合には、式２０の問題は、問題を次式へと直接単純化して解くことができる：
【数２２】
2009509477.tif 000024
【００９７】
式２１の問題は、最初に別の問題を解くことにより解かれることが可能であり、すなわち：
【数２３】
2009509477.tif 000025
【００９８】
これは、歪がＣＯＤＥＣに関してビット・レートの非増加関数であることを仮定することによって行われることができる。言い換えると、利用可能なビット数を増加させることによって、ＣＯＤＥＣの性能は、同じままで留まるか改善するかのどちらかである。それゆえ、Ｄｍａｘがゼロから無限大、Ｒ＊（Ｄｍａｘ）、まで変化するとき、式２２に対する解は、図１７に示された階段状曲線１７５の跡をたどる。それゆえ、二分割は、Ｒ＊（Ｄ＊ｍａｘ）≦Ｒｂｕｄｇｅｔを満足するＤ＊ｍａｘを見つけるために使用されることができ、そしてそれによって、式２１の問題を解く。
【００９９】
式２２を解くためのアルゴリズムを与えるために、コスト関数Ｃｋ（Ｑｋ−１，Ｑｋ）を作ることができ、それは、Ｑｋ−１とＱｋが（ｋ−１）番目とｋ番目のフレームに対するＱＰであることが与えられると、式２２の歪制約を有するｋ番目のフレームを含むｋ番目のフレームまでの最小全レートを表す。そのように、
【数２４】
2009509477.tif 000026
【０１００】
に対する解は、同様に、式２２に対する所望の解である。
【０１０１】
効率的なアルゴリズムを導き出すための１つの鍵となる観測は、（ｋ−１）番目とｋ番目のフレームに対する判断ベクトルＱｋ−２とＱｋ−１、及びコスト関数Ｃｋ−１（Ｑｋ−２，Ｑｋ−１）を与えられると、次の判断ベクトルＱｋの選択は、前の判断ベクトルＱ１，Ｑ２，．．．，Ｑｋ−３の選択とは無関係である、という事実である。これは、コスト関数が次式として帰納的に表されることができるために真実である：
【数２５】
2009509477.tif 000027
【０１０２】
上記のコスト関数の帰納的表示は、ダイナミック・プログラミングの基礎である前のステップとは無関係に最適化プロセスの任意の今後のステップを行う。
【０１０３】
式２３によって定義されるコスト関数を用いて、この問題は、方向性非循環グラフ（ＤＡＧ）において最短経路を見出すグラフ理論問題へと変換されることができる。この解は、網羅的な検索アルゴリズムの指数関数的な計算上の複雑さよりもはるかに有効である。
【０１０４】
推定モデルは、レート及び歪に対して使用されることができる。すなわち：
【数２６】
2009509477.tif 000028
【０１０５】
式２５−２９において推定されるレート及び歪を式２２−２４に置き換えることにより、問題又は式５は、効率的に解かれることが可能である。
【０１０６】
実験は、ビット・レート範囲が６０ｋｂｐｓから１２０ｋｂｐｓである、“テーブル・テニス”、“フォアマン”、及び“ダンサー”として識別されるビデオ系列を含む複数の標準ビデオ・テスト系列に実施された。結果は、下記の文章で報告される。
【０１０７】
実験の第１セットは、ビット・レート変動制約を緩めることにより図１６に概要を示されたアルゴリズムの一定品質の特徴に注目した。上記に概要を示された提案のＭＩＮＭＡＸアプローチは、他の２つのアプローチと比較された、それらは（１）フレーム−レベル・グリーディ・レート制御、それは今後現れるフレームが一様に分布されたテクスチャの複雑さを有し、それゆえ残りのビットを今後の複数のフレームの間に一様に割り当てることを仮定する、及び（２）より高いＰＳＮＲ期待値を有するＭＩＮＭＡＸアプローチ、すなわち、同様に一定品質を求めるが、２回目のパスにおいて実現されるべき平均ＰＳＮＲが１回目のパスのそれと同じレベルであることを要求するＭＩＮＭＡＸアプローチ、である。問題の定式化は、式３０に示され、次式の通りである；
【数２７】
2009509477.tif 000029
【０１０８】
ここで、εは非常に小さな数である。式３０は、平均ＰＳＮＲについての追加の制約を除いて、式２１に極めて類似する。
【０１０９】
図１８−２０では、“フォアマン”系列についてのテスト結果が示される。この例では、全ての３つのアプローチは、類似のレート−歪性能を有するが、ＭＩＮＭＡＸアプローチはフレームＰＳＮＲの標準偏差を５０％だけ削減した。詳細なＰＳＮＲ分布は、図２０に示され、ＭＩＮＭＡＸアプローチを使用することによるＰＳＮＲ変動の低減を立証する。図１８では、グリーディ・フレーム−レベル・レート制御アルゴリズムは、１８１と番号を付けられ、提案されたＭＩＮＭＡＸアプローチは、１８２と番号を付けられ、そしてより高いＰＳＮＲ期待値を有する変形ＭＩＮＭＡＸアプローチは、１８３と番号を付けられている。図１９では、グリーディ・フレーム−レベル・レート制御アルゴリズムは、１９１と番号を付けられ、提案されたＭＩＮＭＡＸアプローチは、１９２と番号を付けられ、そしてより高いＰＳＮＲ期待値を有する変形ＭＩＮＭＡＸアプローチは、１９３と番号を付けられている。図２０では、グリーディ・フレーム−レベル・レート制御アルゴリズムは、２０１と番号を付けられ、提案されたＭＩＮＭＡＸアプローチは、２０２と番号を付けられている。
【０１１０】
“テーブル・テニス”系列についてのテスト結果が、図２１−２３に示される。予想されるように、提案されたＭＩＮＭＡＸアプローチは、より低い平均フレームＰＳＮＲを有するが、ＰＳＮＲ変動をグリーディ・アルゴリズムから６０−７０％だけ削減する。より高いＰＳＮＲ期待値を有するＭＩＮＭＡＸアプローチは、ＰＳＮＲ変動の２０−３０％の削減を有するグリーディ・アルゴリズムのそれと同様のＰＳＮＲを得た。図２１では、グリーディ・フレーム−レベル・レート制御アプローチは、２１１と番号を付けられ、提案されたＭＩＮＭＡＸアプローチは、２１２と番号を付けられ、そしてより高いＰＳＮＲ期待値を有する変形ＭＩＮＭＡＸアプローチは、２１３と番号を付けられている。図２２では、グリーディ・フレーム−レベル・レート制御アプローチは、２２１と番号を付けられ、提案されたＭＩＮＭＡＸアプローチは、２２２と番号を付けられ、そしてより高いＰＳＮＲ期待値を有する変形ＭＩＮＭＡＸアプローチは、２２３と番号を付けられている。
【０１１１】
図２３は、ビット・レートが１２０ｋｂｐｓに等しいときに、“テーブル・テニス”系列における詳細なＰＳＮＲ分布を示しているグラフである。図２４は、ビット・レートが１２０ｋｂｐｓに等しいときに、“テーブル・テニス”系列における詳細なＱＰ分布を示しているグラフである。図２３では、グリーディ・フレーム−レベル・レート制御アプローチは、２３１と番号を付けられ、提案されたＭＩＮＭＡＸアプローチは、２３２と番号を付けられている。図２４では、グリーディ・フレーム−レベル・レート制御アプローチは、２４１と番号を付けられ、提案されたＭＩＮＭＡＸアプローチは、２４２と番号を付けられている。
【０１１２】
図２５と図２６は、５０００から２５０００の範囲内のビット・レート変動しきい値の様々な設定を用いて１２０ｋｂｐｓにおいて“テーブル・テニス”系列をコーディングすることによってシステム性能へのビット・レート変動制約の影響を例示する。図２５は、特に、ビット・レート変動しきい値の関数としてＰＳＮＲの標準偏差の曲線２５１を図示する。予想されるように、しきい値が図２５に示されたように増加するとＰＳＮＲ変動は減少する。
【０１１３】
詳細なレート変動は、同様に図２６で比較される。具体的に、曲線２６１は、１００００であるレート変動しきい値に対応し、そして曲線２６２は、２５０００であるレート変動しきい値に対応する。明らかに、より狭いしきい値を用いると、系列に関する結果のビット・レートは、より平滑になる。このしきい値を使用することによって、本技術が、仮想バッファを使用するようにビット・レート変動をダイナミックに制御することができ、バッファのオーバーフローとアンダーフローを回避することができ、同様にコード化されたビデオ系列の一定ビデオ品質特性を維持することができることに気付くことは、重要である。
【０１１４】
記載されたＭＩＮＭＡＸフレーム−レベル・レート制御アルゴリズムは、ピーク最大フレーム歪を最小にするために使用されることができ、それは間接的に再構成されるビデオ系列の一定品質を保証する。ビデオ系列のレート変動は、ビデオ・コーディング・デバイス中のプログラム可能なしきい値によって制御されることが可能である。前のフレームの量子化パラメータ選択が現在のフレームのレート−歪性能に重大な影響を有するという観測に基づいて、ビデオ・コーディング・デバイスは、正確なレート及び歪モデルの集合を用いて開発されることが可能である。その観測は、フレーム依存性問題を単純化し、そしてそれとともに候補空間のサイズを指数関数から多項式へと削減する。図１７−２６のグラフに説明された実験結果は、従来のグリーディ・アルゴリズム・アプローチと比較してビデオ系列全体にわたりＰＳＮＲ標準偏差の最大７０％までの著しい削減を示す。
【０１１５】
複数の実施形態が説明されてきている。特に、“２回パス”アプローチを使用する、様々なレート制御技術が、提案されてきており、そこでは、１回目のコーディング・パスがビデオ系列の特性を推定するために使用され、そしてその推定された特性が２回目のパスのための量子化パラメータ（ＱＰ）の選択を改善するために次に使用される。より詳しくは、本明細書と矛盾のない２つの基本的な選択肢が、提案されてきている。第１のケースでは、１回目のパスの推定されたレート−歪特性は、ビデオ系列のフレームの歪を最小にする方法で２回目のパスのためのＱＰを選択するために使用される。第２のケースでは、１回目のパスの推定されたレート−歪特性は、ビデオ系列の複数のフレーム間の品質変動を最小にする方法で２回目のパスのためのＱＰを選択するために使用される。
【０１１６】
本明細書中に記載された技術は、ハードウェア、ソフトウェア、ファームウェア、又はそれらの組み合わせとして与えられることができる。ソフトウェアにおいて与えられる場合、本技術は、プログラム・コードを備えるコンピュータ読み取り可能な媒体に向けられることができ、そのプログラムは、ビデオ系列をコード化するデバイスにおいて実行されるときに、本明細書中に記載された１又はそれより多くの技術を実行する。そのケースでは、コンピュータ読み取り可能な媒体は、（ＲＡＭ：random access memory）を含むことができ、例えば、シンクロナス・ランダム・アクセス・メモリ（ＳＤＲＡＭ：synchronous random access memory）、読み出し専用メモリ（ＲＯＭ：read only memory）、不揮発性ランダム・アクセス・メモリ（ＮＶＲＡＭ：non-volatile random access memory）、電気的消去可能ＲＯＭ（ＥＥＰＲＯＭ：electrically erasable ROM）、フラッシュ・メモリ、及びその他である。
【０１１７】
プログラム・コードは、コンピュータ読み取り可能な命令の形式でメモリに記憶されることができる。そのケースでは、ＤＳＰのようなプロセッサは、本明細書中に記載された１又はそれより多くの技術を実行するためにメモリ中に記憶された命令を実行することができる。あるケースでは、本技術は、ＤＳＰによって実行されることができ、そのＤＳＰはコーディング・プロセスを加速するために様々なハードウェア・コンポーネントを呼び出す。別のケースでは、ビデオ・コーダは、マイクロプロセッサ、１又はそれより多くの用途特定集積回路（ＡＳＩＣ：application specific integrated circuit）、１又はそれより多くのフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡｓ：field programmable gate arrays）、又はある別のハードウェア−ソフトウェアの組み合わせとして搭載されることができる。
【０１１８】
２つのアプローチが別々に記載されているが、その２つのアプローチの様々な態様は、同様に組み合わせで使用されることができる。したがって、異なる技術の様々な態様は、本発明により予想されるさらに別の実施形態に統合されることができる。同様に、２回パス・アプローチが記載されてきているが、より多くのパスでさえも、しかも本明細書にしたがって実行されることができる。言い換えると、本明細書は、２回パス・アプローチに限定されず、少なくとも２つのコーディング・パスがそこで使用されるいずれかの複数回パス・アプローチにさらに広範に適用可能である。これらの実施形態及び他の実施形態は、特許請求の範囲の範囲内である。
【図面の簡単な説明】
【０１１９】
【図１】図１は、本明細書にしたがった具体例のビデオ・コーディング・デバイスを例示するブロック図である。
【図２】図２は、レート−歪特性があるビデオ系列に関する量子化パラメータを規定するために推定されそして使用される本明細書の１実施形態にしたがった２回パス・レート制御されるビデオ・コーディング技術を説明するフロー図である。
【図３】図３は、本明細書の技術の一態様を説明するデータのグラフである。
【図４】図４は、本明細書の技術の一態様を説明するデータのグラフである。
【図５】図５は、本明細書の技術の一態様を説明するデータのグラフである。
【図６】図６は、本明細書の技術の一態様を説明するデータのグラフである。
【図７】図７は、本明細書の技術の一態様を説明するデータのグラフである。
【図８】図８は、本明細書の技術の一態様を説明するデータのグラフである。
【図９】図９は、本明細書の技術の一態様を説明するデータのグラフである。
【図１０】図１０は、本明細書の技術の一態様を説明するデータのグラフである。
【図１１】図１１は、本明細書の技術の一態様を説明するデータのグラフである。
【図１２】図１２は、本明細書の技術の一態様を説明するデータのグラフである。
【図１３】図１３は、本明細書の技術の一態様を説明するデータのグラフである。
【図１４】図１４は、本明細書の技術の一態様を説明するデータのグラフである。
【図１５】図１５は、本明細書の技術の一態様を説明するデータのグラフである。
【図１６】図１６は、品質変動がビデオ系列のフレームに対して最小にされる本明細書の１実施形態にしたがった２回パス・レート制御ビデオ・コーディング技術を説明するフロー図である。
【図１７】図１７は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図１８】図１８は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図１９】図１９は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図２０】図２０は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図２１】図２１は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図２２】図２２は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図２３】図２３は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図２４】図２４は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図２５】図２５は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図２６】図２６は、本明細書の技術の一態様を説明するデータのさらなるグラフである。
【図１】
2009509477.tif 000030
【図２】
2009509477.tif 000031
【図３】
2009509477.tif 000032
【図４】
2009509477.tif 000033
【図５】
2009509477.tif 000034
【図６】
2009509477.tif 000035
【図７】
2009509477.tif 000036
【図８】
2009509477.tif 000037
【図９】
2009509477.tif 000038
【図１０】
2009509477.tif 000039
【図１１】
2009509477.tif 000040
【図１２】
2009509477.tif 000041
【図１３】
2009509477.tif 000042
【図１４】
2009509477.tif 000043
【図１５】
2009509477.tif 000044
【図１６】
2009509477.tif 000045
【図１７】
2009509477.tif 000046
【図１８】
2009509477.tif 000047
【図１９】
2009509477.tif 000048
【図２０】
2009509477.tif 000049
【図２１】
2009509477.tif 000050
【図２２】
2009509477.tif 000051
【図２３】
2009509477.tif 000052
【図２４】
2009509477.tif 000053
【図２５】
2009509477.tif 000054
【図２６】
2009509477.tif 000055