(57)【要約】  基本レイヤと少なくとも１つの上位レイヤとにビデオデータを分割する方法であって、ビデオデータを受信するステップと、前記基本レイヤ及び前記少なくとも１つの上位レイヤを形成するためにビデオフレームの複数のブロックについてのＤＣＴ係数を決定するステップと、各ブロックについてＤＣＴ係数を量子化するステップと、前記基本レイヤの前記量子化されたＤＣＴ係数を（ラン，レングス）対のセットに変換するステップと、どの対が凸包上に存するかを決定するステップとを有する方法。この後、前記凸包上に存する対のみから、因果的に最適な方法で、レート−歪最適分割点が決定される。前記分割点以前の（ラン，レングス）対は基本レイヤに符号化され、他の（ラン，レングス）対は上位レイヤに符号化される。本方法を適用するビデオ符号化器（２２）及び復号化器（２８）もまた開示される。
2007506347.tif 000002
【特許請求の範囲】
【請求項１】
基本レイヤと少なくとも１つの上位レイヤとにビデオデータを分割する方法であって、
前記ビデオデータを複数のフレームに分離するステップと、
各前記フレームを複数のブロックに分離するステップと、
前記ブロックについてＤＣＴ係数を決定するステップと、
を有し、更に各前記ブロックについて、
前記ＤＣＴ係数を量子化するステップと、
前記量子化されたＤＣＴ係数を、少なくとも一部が凸包上に存する（ラン，レングス）対のセットに変換するステップと、
前記凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析することにより分割点を決定するステップと、
前記分割点以前の（ラン，レングス）対のみを前記基本レイヤの伝送に符号化し、前記分割点より後の（ラン，レングス）対を前記少なくとも１つの上位レイヤの伝送に符号化する方法。
【請求項２】
前記分割点を決定するステップは、前記（ラン，レングス）対の符号化及び前記（ラン，レングス）対の復号化の際に同時に因果的に最適な凸包が決定可能なように、因果的に最適な凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析するステップを有する、請求項１に記載の方法。
【請求項３】
前記分割点を決定するステップは、
前記（ラン，レングス）対の全ての隣接する対の間の線の勾配を決定するステップと、
前記（ラン，レングス）対の隣接する対の間の線の勾配に基づいて、どの前記（ラン，レングス）対が因果的凸包上に存するかを決定するステップと、
前記因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づき、前記分割点を決定するステップと、
を有する請求項２に記載の方法。
【請求項４】
前記因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づき、前記分割点を決定するステップは、各フレーム中の全てのブロックに共通する品質係数に対して前記線の勾配を比較するステップを有する、請求項３に記載の方法。
【請求項５】
前記フレーム中のヘッダに前記品質係数を配置するステップを更に有する、請求項４に記載の方法。
【請求項６】
前記分割点は、前記因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づき、且つフレーム中の全てのブロックに共通する品質係数に基づき決定される、請求項３に記載の方法。
【請求項７】
前記どの前記（ラン，レングス）対が因果的凸包上に存するかを決定するステップは、前記セット中の最初及び最後の（ラン，レングス）対を除く各前記（ラン，レングス）対について、
当該対と先行する対との間、及び当該対と後続する対との間の歪−レングス勾配を決定するステップと、
当該対と後続する対との間の歪−レングス勾配が、当該対と先行する対との間の歪−レングス勾配よりも小さいか否かを決定し、そうであれば当該対が前記因果的凸包上に存するとみなすステップと、
を有する、請求項３に記載の方法。
【請求項８】
前記因果的凸包上に存すると決定された（ラン，レングス）対と、（ラン，レングス）対の前記セット中の最初の対とから、因果的凸包のセットを形成するステップを更に有する、請求項７に記載の方法。
【請求項９】
スケーラブルなビデオシステムであって、
ビデオデータを符号化し、基本レイヤ及び少なくとも１つの上位レイヤを有する符号化されたデータを出力するソース符号化器を有し、前記ソース符号化器は、
前記ビデオデータを複数のフレームに分離し、
各前記フレームを複数のブロックに分離し、
各前記フレームについてヘッダを提供し、
前記ブロックについてＤＣＴ係数を決定するように構成され、更に前記ソース符号化器は、各ブロックについて、
前記ＤＣＴ係数を量子化し、
前記量子化されたＤＣＴ係数を（ラン，レングス）対のセットに変換し、
因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析することにより分割点を決定し、
前記分割点以前の（ラン，レングス）対のみを前記基本レイヤの伝送に符号化し、前記分割点より後の（ラン，レングス）対を前記少なくとも１つの上位レイヤの伝送に符号化するように構成されたビデオシステム。
【請求項１０】
前記符号化器は、前記（ラン，レングス）対の符号化及び前記（ラン，レングス）対の復号化の際に同時に因果的に最適な凸包が決定可能なように、因果的に最適な凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析することにより、前記分割点を決定するように構成された、請求項９に記載のシステム。
【請求項１１】
前記符号化器は、前記（ラン，レングス）対の全ての隣接する対の間の線の勾配を決定し、前記（ラン，レングス）対の隣接する対の間の線の勾配に基づいて、どの前記（ラン，レングス）対が因果的凸包上に存するかを決定し、前記因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づき前記分割点を決定することにより、前記分割点を決定するように構成された、請求項１０に記載のシステム。
【請求項１２】
前記符号化器は、各フレーム中の全てのブロックに共通する品質係数に対して前記線の勾配を比較することにより、前記因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づき前記分割点を決定するように構成された、請求項１１に記載のシステム。
【請求項１３】
前記符号化器は、フレーム中の全てのブロックに共通する品質係数に基づき前記分割点を決定するように構成された、請求項９に記載のシステム。
【請求項１４】
前記符号化器は、前記因果的凸包上の各対と先行する対との間、及び当該対と後続する対との間の歪−レングス勾配を決定することにより、どの対が前記因果的凸包上に存するかを決定し、当該対と後続する対との間の歪−レングス勾配が、当該対と先行する対との間の歪−レングス勾配よりも小さいか否かを決定し、そうであれば当該対が前記因果的凸包上に存するとみなすように構成された、請求項１０に記載のシステム。
【請求項１５】
基本レイヤ及び少なくとも１つの上位レイヤを有するビデオデータを復号化し、復号化されたデータを出力するソース復号化器を更に有し、前記復号化器は、前記基本レイヤ及び前記少なくとも１つの上位レイヤ中の（ラン，レングス）対を分析し、前記ビデオデータの復号化における使用のために前記分割点を決定するように構成された、請求項９に記載のシステム。
【請求項１６】
前記復号化器は、コンピュータ実行可能な処理ステップを保存するメモリと、前記メモリに保存された処理ステップを実行し、前記基本レイヤ及び前記少なくとも１つの上位レイヤを受信し、因果的な（ラン，レングス）対のみを分析することにより、前記基本レイヤ及び前記少なくとも１つの上位レイヤに含まれる（ラン，レングス）対に基づいて分割点を決定するプロセッサとを含む、請求項１５に記載のシステム。
【請求項１７】
前記符号化器は、コンピュータ実行可能な処理ステップを保存するメモリと、前記メモリに保存された処理ステップを実行し、因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析することにより分割点を決定し、前記分割点以前の（ラン，レングス）対のみを前記基本レイヤに含め、前記分割点より後の（ラン，レングス）対を前記少なくとも１つの上位レイヤに含めるプロセッサとを含む、請求項９に記載のシステム。
【請求項１８】
ビデオフレーム中の複数のマクロブロックについて（ラン，レングス）対を表すデータを含む基本レイヤと少なくとも１つの上位レイヤとにデータを分割することが可能なスケーラブルな符号化器であって、
コンピュータ実行可能な処理ステップを保存するメモリと、
前記メモリに保存された処理ステップを実行し、因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析することにより分割点を決定し、前記分割点以前の（ラン，レングス）対のみを前記基本レイヤに含め、前記分割点より後の（ラン，レングス）対を前記少なくとも１つの上位レイヤに含めるプロセッサと、
を有する符号化器。
【請求項１９】
前記プロセッサは、前記（ラン，レングス）対の全ての隣接する対の間の線の勾配を決定し、前記（ラン，レングス）対の隣接する対の間の線の勾配に基づいて、どの前記（ラン，レングス）対が因果的凸包上に存するかを決定し、前記因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づき、前記分割点を決定することにより、前記分割点を決定するように構成された、請求項１８に記載の符号化器。
【請求項２０】
ビデオフレーム中の複数のマクロブロックについて（ラン，レングス）対を表すデータを含む基本レイヤと少なくとも１つの上位レイヤとからデータをマージすることが可能なスケーラブルな復号化器であって、
コンピュータ実行可能な処理ステップを保存するメモリと、
前記メモリに保存された処理ステップを実行し、前記基本レイヤ及び前記少なくとも１つの上位レイヤを受信し、因果的な（ラン，レングス）対のみを分析することにより、前記基本レイヤ及び前記少なくとも１つの上位レイヤに含まれる（ラン，レングス）対に基づいて分割点を決定するプロセッサと、
を有する復号化器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にスケーラブルなビデオ符号化システムに関し、より詳細には、ビデオ伝送のための離散コサイン変換（ＤＣＴ）係数のレート−歪最適化されたデータ分割（rate-distortion optimized data partitioning、ＲＤＤＰ）に関する。
【背景技術】
【０００２】
ビデオは、画像のシーケンスである。各画像は、画素の配列によって形成される。圧縮されていないビデオのサイズは非常に大きく、それ故サイズを減少させデータ伝送レートを改善するためにビデオ圧縮がしばしば利用される。ディジタル記憶媒体における動画及び関連するオーディオの符号化された表現についての国際規格を提供するため、種々のビデオ符号化方法（例えばＭＰＥＧ１、ＭＰＥＧ２及びＭＰＥＧ４）が確立されてきた。
【０００３】
かようなビデオ符号化方法は、レートを減少させた伝送のために、未処理の（raw）ビデオデータをフォーマットし圧縮する。例えば、ＭＰＥＧ２規格のフォーマットは４層から成る。即ちグループ・オブ・ピクチャ、ピクチャ、スライス及びマクロブロックである。ビデオシーケンスは、１以上のグループ・オブ・ピクチャ（ＧＯＰ）を含むシーケンスヘッダから始まり、エンド・オブ・シーケンスコードで終わる。グループ・オブ・ピクチャ（ＧＯＰ）は、ヘッダと、ビデオシーケンスへのランダムアクセスを可能とするように意図された一連の１以上のピクチャとを含む。ＭＰＥＧ２規格は、３つのタイプのピクチャを定義している。即ち、Ｉピクチャ（Intra Pictures）、Ｐピクチャ（Predicted Pictures）及びＢピクチャ（Bidirectional Pictures）であり、これらは組み合わせられてグループ・オブ・ピクチャを形成する。
【０００４】
ピクチャは、ビデオシーケンスの主たる符号化単位である。ピクチャは輝度値（Ｙ）及び２つの色差値（Ｃｂ及びＣｒ）を表す、３つの長方形のマトリクスから成る。Ｙマトリクスは偶数個の行及び列を持つ。Ｃｂ及びＣｒマトリクスは、各方向（水平及び垂直）にＹマトリクスの半分のサイズを持つ。スライスは、１以上の「隣接する」マクロブロックである。スライス内のマクロブロックの順序は、左から右及び上から下である。
【０００５】
マクロブロックは、ＭＰＥＧアルゴリズムにおける基本符号化単位である。マクロブロックは、フレーム中の１６×１６の画素セグメントである。各色素成分は輝度成分の半分の水平方向サイズ及び垂直方向サイズを持つため、１つのマクロブロックは４つのＹブロック、１つのＣｒブロック及び１つのＣｂブロックから成る。ブロックは、ＭＰＥＧアルゴリズムにおける最小の符号化単位である。ブロックは８×８画素から成り、３つのタイプ即ち輝度（Ｙ）、赤色差（Ｃｒ）及び青色差（Ｃｂ）のうちの１つであり得る。ブロックは、フレーム内符号化（intra frame coding）における基本単位である。
【０００６】
ＭＰＥＧ変換符号化アルゴリズムは、以下の符号化ステップ即ち離散コサイン変換（ＤＣＴ）、量子化及びランレングス符号化のステップを含む。
【０００７】
ビデオ符号化における重要な手法は、スケーラビリティ（scalability）である。この点に関して、埋め込まれたサブセットに分割されることができるビットストリームを生成することが可能なコーデックとして、スケーラブルなビデオコーデックが定義されている。これらのサブセットは、向上された質のビデオシーケンスを提供するために、独立に復号化されることができる。従って、単一の圧縮操作が、異なるレート及び再構築された質を持つビットストリームを生成することができる。元のビットストリームの小さなサブセットが最初に送信され基本レイヤ（base layer）の品質を提供し、後に更なる層が上位レイヤ（enhancement layer）として送信される。スケーラビリティは、ＭＰＥＧ−２、ＭＰＥＧ−４及びＨ．２６３のような殆どのビデオ圧縮規格によってサポートされている。
【０００８】
スケーラビリティの重要な用途は、エラー回復性のあるビデオ伝送におけるものである。スケーラビリティは、上位レイヤよりも基本レイヤに対してより強いエラー保護（即ち不均等エラー保護）を適用するために利用されることができる。従って、不利な伝送チャネルの条件の間でも、高い確率で基本レイヤは正常に復号化される。
【０００９】
データ分割（ＤＰ、Data Partitioning）は、スケーラビリティを容易化するために符号化器と関連して利用される。一方、マージ手法が、正常なビデオ画像を形成するようにデータをマージするために復号化器と関連して利用される。
【００１０】
データ分割に関しては、例えばＭＰＥＧ２においては、スライスレイヤが、特定のビットストリームに含まれるブロック変換係数の最大数（優先分割点（priority break point）として知られる）を示す。データ分割は、６４個の量子化された変換係数のブロックを２つのビットストリームに分割する、周波数ドメインの方法である。第１の、高い優先度のビットストリーム（例えば基本レイヤ）は、より重要な低周波数係数及び副情報（ＤＣ値及び動きベクトルのような）を含む。第２の、低い優先度のビットストリーム（例えば上位レイヤ）は、高周波ＡＣデータを担持する。
【００１１】
符号化器の外部でデータ分割を実装するための一手法は、各可変長符号について利用されるビットの数を可変長復号化器（ＶＬＤ）から受信し、優先分割点（ＰＢＰ）値に基づいてビットストリームを分割するデマルチプレクサを、送信器において備えることを必要とする。ＰＢＰは、利用されるレート分割ロジックに基づいて、各スライスにおいて変更されても良いことに留意されたい。従来のデータ分割（ＤＰ）ビデオ符号化器（例えばＭＰＥＧ）においては、単一のレイヤのビットストリームが、ＤＣＴドメインにおいて２以上のビットストリームに分割される。伝送の間、ビットレートのスケーラビリティを実現するために、１以上のビットストリームが送信される。チャネル劣化に対する耐性を改善するため、基本レイヤ及び上位レイヤに対して不均等エラー保護が適用されることができる。
【００１２】
復号化器の外部における分割されたデータのマージに関しては、基本レイヤ及び上位レイヤのストリームを処理し、次いでレイヤを形成しないビットストリームを出力する、２つのＶＬＤが利用されても良い。ＰＢＰ値は、符号化されたストリームがどのように分割されるかを定義する。復号化の前に、リソースの割り当て及び／又は受信器の能力に依存して、受信されたビットストリーム又はそのサブセットが、単一のビットストリームにマージされ、復号化される。
【００１３】
従来のＤＰ構造は、ホームネットワーク環境において多くの利点を持つ。具体的には、最良の品質の場合に、ＤＰのレート−歪性能が、対応する単一層と同様に優れており、一方でレートスケーラビリティも可能である。レート−歪（Ｒ−Ｄ）性能は、レートと歪との最適な組み合わせを見つけることに関連する。該最適な組み合わせは、コストと品質の最適な組み合わせともみなされるが、唯一となるものではない。Ｒ−Ｄ方式は、とり得る最も少ないビットで、同時に最良の再生品質に導くような方法で、情報を表すように試みるものである。
【００１４】
従来のＤＰ構造においては、最良の品質の場合に、付加的な復号化の複雑さが非常に小さく、同時にＤＰは広い範囲の復号化器の複雑さのスケーラビリティを提供することにも留意されたい。このことは、最も計算的にコストの掛かる部分であるＤＣＴのラン−レングス対の可変長復号化（ＶＬＤ）がスケーラブルになるからである。
【００１５】
従来のＤＰ構造においては、ＤＣＴ優先分割点（ＰＢＰ）値が、副情報として明確に送信される必要がある。オーバヘッドを最小化するため、ＰＢＰ値は通常、各スライス又はビデオパケット内の全てのＤＣＴブロックについて固定される。従来のＤＰは単純であり多くの利点を持つが、各スライス又はビデオパケット内の全てのブロックについて１つのＰＢＰ値のみが利用されるため、基本レイヤについて最適化のための余地が殆ど無い。
【００１６】
従来のＤＰ方法は単純であり幾つかの利点を持つが、各スライス又はビデオパケットについて１つのＰＢＰ値のみが利用されるため、基本レイヤの最適化を適応させることが不可能である。
【００１７】
従って、従来のデータ分割方式の限界を克服し、改善された基本レイヤの最適化を提供するビデオ符号化手法に対するニーズが存在する。
【００１８】
本発明者の「System and Method of Rate-Distortion Optimized Data Partition for Video Coding Using a Parametric Rate-Distortion Model」（米国特許出願シリアル番号60/463,747、2003年4月18日出願、2003年7月29日再出願、米国特許出願シリアル番号60/490,835（本出願人の参照番号703553に対応））と題された関連する開示（参照により全体が本明細書に組み込まれたものとする）において、コンテキストベースの逆方向適合（backward adaptation）を利用することにより、最小のオーバヘッド（各スライス又はビデオパケットについて約２０ビット）で、ＰＢＰ値をそれぞれＤＣＴブロックレベルで適合させることを可能とすることにより、データ分割のための改善を提供する、レート−歪最適化されたデータ分割（ＲＤＤＰ）が記載されている。かようなブロック毎の適合は常に、レート−歪（ＲＤ）面上の特定の凸状（convexity）条件の下で、ＲＤＤＰが略最適なビデオ品質を達成するように保証するレート−歪最適化方式で実行される。
【００１９】
ＲＤＤＰは、ラグランジュ最適化（Lagrangian optimization）アルゴリズムに基づく。レート−歪最適化のためのラグランジュ方式の主な利点は、各信号要素に対する独立したプロパティである。より具体的には、データ分割の理論的な性能限界が、以下のコスト関数を最小化することにより達成される。
【数１】
2007506347.tif 000003
ここでＤｉ（ｈ）及びＲｉ（ｈ）は、分割点がｈである場合のｉ番目のＤＣＴブロックの基本レイヤについての歪及びレートを示す。Ｑは、各フレーム中のＤＣＴブロックの総数である。ラグランジュ最適化問題（１）の解は、Ｒ−Ｄ点の凸包（convex hull）中に存する。
【００２０】
図１に示すような典型的な凸状Ｒ−Ｄ曲線を考えると、最小のラグランジュ関数は、該レート−歪曲線に当たる絶対値の勾配λ（Ｓ＝−λ）の平面波によって最初に「衝突される」点について達成される。とり得る全ての動作点が凸包上に存する場合、最適な動作点の前の絶対値の勾配はλより大きく、前記最適点の後の絶対値の勾配はλ以下となる。このことは、凸状Ｒ−Ｄ曲線についてのＤＣＴのラン−レベル対は以下の条件を満たすことを意味する。
【数２】
2007506347.tif 000004
ここでλはラグランジュ乗数又は品質係数である。Ｎｉｋ及びＣｉｋはそれぞれ、ｉ番目のＤＣＴブロックについてのｋ番目のＤＣＴ符号長及びレベルを示す。ｈｉは、ｉ番目のＤＣＴブロックについての最適な分割点値を示す。Ｃｉｋ及びＮｉｋの値は符号化器と復号化器との両方にとって既知であるため、ＲＤＤＰの基本的な着想は、最適な分割点値ｈｉを符号化及び送信する代わりに、品質係数λのみが符号化され復号化器に送信され、次いで復号化器が分割点ｈｉをＣｉｋ及びＮｉｋから推定するものである。
【００２１】
式（２）を用いたＲＤＤＰアルゴリズムは、最適なものに比べて、１つだけ多いラン−レベル対が基本レイヤに含められるという意味で、最適に近いことが分かっている。該ラン−レベル対は、λより大きい勾配からλ以下に変わるレート−歪曲線上の点である。
【発明の開示】
【発明が解決しようとする課題】
【００２２】
実際には、ＤＣＴブロックについてのＲ−Ｄ曲線は、しばしば非凸状になる。この場合には、式（２）によって与えられる分割規則は必ずしも有効ではなく、ＲＤＤＰの最適さはもはや保証されない。例えば、図２に示される非凸状Ｒ−Ｄ曲線については、最適な又は優先分割点（ＰＢＰ）値はｋ２となるが、ＲＤＤＰアルゴリズムは分割点値ｋ１を提供し、基本レイヤの分割が不足（under-partitioned）となる。
【００２３】
優先分割点（ＰＢＰ）は、符号化されたビットストリームがどのように分割されるかを定義する（即ち、復号化の目的のため、受信されたビットストリームが優先分割点に基づいて復号化される）ため、符号化及び復号化の目的の両方のために、同一の優先分割点（ＰＢＰ）値を持つ又は決定することが可能であることが重要である。
【００２４】
本発明の目的は、改善されたレート−歪最適化されたデータ分割手法及びアルゴリズムを提供することにある。本発明の他の目的は、逆方向適合を利用したビデオのためのレート−歪最適化されたデータ分割手法を提供することにある。本発明の更なる目的は、他のＲＤＤＰアルゴリズムの欠点を克服する、凸包及び勾配のインクリメンタル（incremental）計算アルゴリズムを利用する、新たなレート−歪最適化されたデータ分割（ＲＤＤＰ）手法を提供することにある。
【００２５】
本発明の更に他の目的は、従来のデータ分割手法の限界を克服し、改善された基本レイヤの最適化を提供するビデオ符号化手法を提供することにある。
【課題を解決するための手段】
【００２６】
これらの及び他の目的を達成するため、本発明の一形態によれば、基本レイヤと少なくとも１つの上位レイヤとにビデオデータを分割する方法は、ビデオデータを受信し前記ビデオデータを複数のフレームに分離するステップと、各前記フレームを複数のブロックに更に分離するステップと、前記ブロックについてＤＣＴ係数を決定するステップと、各前記ブロックについて、前記ＤＣＴ係数を量子化するステップと、前記基本レイヤの前記量子化されたＤＣＴ係数を（ラン，レングス）対のセットに変換するステップと、前記凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析することにより分割点を決定するステップとを有する。前記分割点が決定されると、前記分割点以前の（ラン，レングス）対のみが前記基本レイヤにおける伝送のために符号化され、前記分割点より後の（ラン，レングス）対が前記上位レイヤにおける伝送のために符号化される。
【００２７】
一実施例においては、因果的に最適な（causally optimal）凸包に存する（ラン，レングス）対の隣接する対の間のみで線の勾配を分析することにより、分割点が決定される。これにより、前記因果的に最適な凸包が、（ラン，レングス）対の符号化及び（ラン，レングス）対の復号化の際に同時に決定されることができる。
【００２８】
より具体的には、分割点を決定するための方法の一例において、（ラン，レングス）対の全ての隣接する対の間の線の勾配が決定され、（ラン，レングス）対の隣接する対の間の線の勾配に基づいて、どの（ラン，レングス）対が因果的（causal）凸包上に存するかに関しての決定が為される。分割点は次いで、因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づいて決定される。例えば、因果的凸包上に存する（ラン，レングス）対の間の線の勾配が、各フレーム中の全てのブロックに共通する品質係数に対して比較される。品質係数はフレームのヘッダ中に配置されても良い。このようにして、各ブロックについて変化し得る、各ブロックについての分割点が、因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配、及びフレーム中の全てのブロックに共通する品質係数に基づいて決定される。
【００２９】
どの対が因果的凸包上に存するかの決定は、セット中の各対（最初のものと最後のものを除く）と先行する対との間、及び当該対と後続する対との間の歪−レングスの勾配を決定すること、並びに当該対と後続する対との間の歪−レングスの勾配が、当該対と先行する対との間の歪−レングスの勾配よりも小さいか否かを決定し、そうであれば、当該対が因果的凸包上に存するとみなすことを必要とする。因果的凸包のセットはかくして、因果的凸包上に存すると決定された対及び（ラン，レングス）セットにおける最初の対から形成される。
【００３０】
本発明の他の形態によれば、スケーラブルなビデオシステムは、ビデオデータを符号化し、基本レイヤ及び少なくとも１つの上位レイヤを有する符号化されたデータを出力するソース符号化器を有する。前記符号化器は、ビデオフレームの複数のブロックについてＤＣＴ係数を決定し、基本レイヤ及び少なくとも１つの上位レイヤを形成し、各ブロックについて、ＤＣＴ係数を量子化し、基本レイヤの量子化されたＤＣＴ係数を（ラン，レングス）対のセットに変換し、凸包上に存する（ラン，レングス）対の隣接する対の間のみの線の勾配を分析することにより、分割点を決定する。符号化器は次いで、前記分割点以前の（ラン，レングス）対のみを基本レイヤの伝送へと符号化し、前記分割点の後の（ラン，レングス）対を上位レイヤの伝送へと符号化する。より具体的には、前記符号化器は、（ラン，レングス）対の全ての隣接する対の間の線の勾配を決定し、（ラン，レングス）対の隣接する対の間の線の勾配に基づいて、どの（ラン，レングス）対が因果的凸包上に存するかを決定し、次いで因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づいて、分割点を決定することにより、分割点を決定するように設計されることができる。
【００３１】
ビデオシステムは、基本レイヤ及び少なくとも１つの上位レイヤを持つビデオデータを復号化し、復号化されたデータを出力するソース復号化器を含んでも良い。前記復号化器は、基本レイヤ及び上位レイヤ中の因果的な（ラン，レングス）対から決定された分割点に基づいてビデオデータを復号化する。
【００３２】
本発明は、その更なる目的及び利点と共に、添付する図と共に以下の説明を参照することにより最も良く理解され得る。ここで同様の参照番号は同様の要素を示す。
【発明を実施するための最良の形態】
【００３３】
本発明は、レイヤ（layered）ソース符号化器が入力ビデオデータを符号化し、レイヤソース復号化器が前記符号化されたデータを復号化する、レイヤ符号化（layered coding）及び伝送の優先順位付けを伴うスケーラブルなビデオシステムにおいて適用可能である。前記ソース符号化器の出力は、基本レイヤ及び１以上の上位レイヤを含む。複数のチャネルが出力される符号化されたデータを担持する。
【００３４】
レイヤ符号化を実装する種々の方法がある。例えば、時間ドメインレイヤ符号化においては、基本レイヤは低いフレームレートを持つビットストリームを含み、上位レイヤは高いフレームレートを持つ出力を得るためのインクリメンタル情報を含む。空間ドメインレイヤ符号化においては、基本レイヤは元のビデオシーケンスのサブサンプリングされたバージョンを符号化し、上位レイヤは復号化器において高い空間分解能を得るための付加情報を含む。一般に、異なるレイヤは異なるデータストリームを利用し、チャネル誤りに対して別個に異なる耐性を持つ。チャネル誤りに対処するため、レイヤ符号化は通常、伝送優先順位付けと組み合わせられ、より高度なエラー保護によって基本レイヤが配信されるようにする。基本レイヤが失われると、上位レイヤに含まれるデータは無用になり得る。
【００３５】
基本レイヤのビデオ品質は、ＤＣＴブロックレベルで柔軟に制御されても良い。所望の基本レイヤは、各ＤＣＴブロックについてＲＤ面の凸包を近似するためにパラメトリックＲＤモデルを利用することにより、ＤＣＴブロックレベルでＰＢＰ値を適合させることにより制御されることができる。これにより、符号化器及び復号化器において同時に最適な分割点が見出される。
【００３６】
ＤＣＴは、隣接するエラー画素の間の空間的な相関を減少させ、エラー画素のエネルギーを数個の係数に圧縮するために利用される。多くの高周波係数は量子化の後にゼロになるため、可変長符号化（ＶＬＣ）がランレングス符号化方法によって実現される。該方法は、前記係数を、低周波係数が高周波係数の前に配置されるように所謂ジグザグスキャン（zig-zag scan）を利用して、１次元の配列に順序付けする。このようにして、量子化された係数は、ゼロでない値と、先行するゼロの数とで規定される。それぞれがゼロのランレングスとゼロでない値との対に対応する種々のシンボルが、可変長符号語を利用して符号化される。
【００３７】
スケーラブルなビデオシステムは、量子化されたＤＣＴ係数が、該係数をジグザグの順序でスキャンすることにより１次元の配列に再配置されるエントロピー符号化を利用する。当該再配置は、ＤＣ係数を前記配列の最初の位置に配置し、残りのＡＣ係数が、水平方向及び垂直方向共に、低い周波数から高い周波数への順に配列される。高周波における量子化されたＤＣＴ係数はゼロになる見込みが高いと仮定し、ゼロでない部分とゼロの部分とを分ける。再配置された配列は、ラン−レベル対のシーケンスに符号化される。ランは、前記配列中の２つのゼロでない係数間の距離として定義される。レベルは、ゼロのシーケンスの直後に後続するゼロでない値である。該符号化方法は、８×８個のＤＣＴ係数の圧縮された表現を生成する。なぜなら、多くの係数は既にゼロ値に量子化されているからである。
【００３８】
ラン−レベル対、及び動きベクトルのようなマクロブロックについての情報、並びに予測タイプは、エントロピー符号化を利用して更に圧縮される。可変長符号化及び固定長符号化の両方が、この目的のために利用される。
【００３９】
ビデオシステムの設計は、演算（operational）レート−歪（ＲＤ）理論によって動機付けされる。ＲＤ理論は、符号化及び圧縮の場合に有用である。ここでは、利用可能な帯域幅が予め知られており、当該帯域幅内で達成できる最良の再生品質を達成することが目的である（即ち、適合アルゴリズム）。
【００４０】
ここで図３を参照すると、本発明により、図２に示されたような凸包及び勾配のＲ−Ｄ曲線に対してインクリメンタル計算アルゴリズムが利用される。インクリメンタルアルゴリズムは、各ビデオフレームの各ＤＣＴブロックについて、凸包及びＲ−Ｄ勾配を、先行ランレングス可変長符号化器（ＶＬＣ）を利用して、計算的に効率の良い方法で計算する。凸包の計算は、計算される凸包が所与の（ラン，レングス）対の因果的な対についての真の凸包であるという意味において、因果的−最適（causal-optimal）である。それ故、同一の凸包及びＲ−Ｄ勾配が、符号化器及び復号化器において同時に計算される。
【００４１】
一般に、ビデオフレームの各ＤＣＴブロックについて、ＤＣＴ係数が量子化され、（ラン，レングス）対のセットに変換される（ステップ１０）。各（ラン，レングス）対は、図４に示されるように、（Ｌｉ（ｋ），Ｄｉ（ｋ））によって表される。（ラン，レングス）対の隣接する各対の間の線の勾配が、次いで決定される（ステップ１２）。例えば、最初の（ラン，レングス）対（０で示される）と２番目の（ラン，レングス）対（１で示される）との間の勾配、２番目の（ラン，レングス）対（１で示される）と３番目の（ラン，レングス）対（１で示される）との間の勾配、等が決定される。
【００４２】
（ラン，レングス）対の隣接する対の間の勾配が決定されると、どの（ラン，レングス）対が凸包上に存するかについての決定が為される（ステップ１４）。前記ビデオフレームのブロックの符号化及び復号化は、決定された線の勾配に基づく。
【００４３】
本手法は図４を用いて説明される。ここでは、ｉ番目のＤＣＴブロックの（ラン，レングス）のＲ−Ｄ対が示され、（Ｌｉ（ｋ），Ｄｉ（ｋ））はｋ個の（ラン，レングス）対までを含む基本レイヤのレート−歪対を示し、ｈｉｐは凸包上のｐ番目のレート−歪対を示す。凸包勾配（Ｓで示される）は−λｉ（ｈｉｐ）に等しく、ｈｉｐにおける「歪−レングス」勾配を示す。
【００４４】
図４に示されるように、幾つかのレート−歪対は凸包上に存しない。即ち、５つの（ラン，レングス）対のみ即ちｋ＝０、２、４、７及び９についての（Ｌｉ（ｋ），Ｄｉ（ｋ））が、凸包上に存する。最適化問題（即ちコスト関数式（１）の最小化）の解は、これら５つのレート−歪対のなかにある。即ち、ｈ∈｛０，２，４，７，９｝である。従って、全てのレート−歪対にアクセスできるとしても、これらのレート−歪対のみが、基本レイヤと上位レイヤとの間の分割勾配を決定するために利用される。利用可能な点を見つけるために、凸包及び結果の歪−レングス勾配が計算される。凸包及び歪−レングス勾配の高速なインクリメンタル計算アルゴリズムの例が以下に示される：
【数３】
2007506347.tif 000005
【００４５】
上述のアルゴリズムにおいて、Ｈｉは凸包のセットを示し、該セットは更なるレート−歪対が処理されると連続的に更新される。データ分割問題において、ΔＤ及びΔＬは以下のように容易に計算されることができる：
【数４】
2007506347.tif 000006
ここでＣｉｋ，Ｎｉｋは、逆量子化されたＤＣＴ係数及びｋ番目のＤＣＴ（ラン，レングス）対の符号長を示す。
【００４６】
凸包上の（ラン，レングス）対が決定されると、品質係数８（同一のフレーム中の全てのブロックについて等しい）、及び凸包上の（ラン，レングス）対の隣接する対の間の線の傾斜に基づき、各ブロックについての分割点が決定される。
【００４７】
全てのレート−歪対が「真の」凸包及び歪−レングス傾斜を構成するために処理されるべきであるという意味において、本アルゴリズムは因果的ではない。副情報なしでは、復号化器は、因果的なレート−歪対に基づいて分割点を決定することしかできない。それ故、好適な実施例においては、上述の凸包検索アルゴリズムは、因果的なレート−歪又は（ラン，レングス）対のみを利用するように変更される。上述のアルゴリズム及び式（１）を適用することにより、因果的な（ラン，レングス）対から分割点が得られ、該分割点より前の（ラン，レングス）対が基本レイヤに符号化され（これら対が凸包上に存するか否かにかかわらず）、一方で該分割点より後の（ラン，レングス）対が上位レイヤに符号化される（ステップ１８）。このようにして、本発明は、因果的に最適な凸包計算に基づく副情報の伝送を必要としない新たな分割規則を提供する。
【００４８】
復号化器側では、復号化器が送信された基本レイヤ及び上位レイヤを受信し、該基本レイヤ及び上位レイヤ中に含まれる（ラン，レングス）対に基づいて、（ラン，レングス）対の各隣接する対の間の線の傾斜を算出し、どれが因果的な凸包上に存するかを決定し、次いで品質係数８に基づき分割点を決定する（ステップ２０）。符号化器及び復号化器において、同一のアルゴリズムが分割点を決定するために利用されるため、同一の分割点が得られる。線の間の傾斜の算出は符号化器側及び復号化器側の両方で必要とされるが、副情報の伝送を回避する利点が維持される。
【００４９】
基本レイヤと上位レイヤとの間の分割に関して、提案されるアルゴリズムは以下の方法で与えられる：
アルゴリズム：符号化器
【数５】
2007506347.tif 000007
復号化器側では、マージアルゴリズムが以下のように与えられる：
アルゴリズム：復号化器
【数６】
2007506347.tif 000008
【００５０】
結果の凸包が所与の因果的な（ラン，レングス）対について最適な凸包であるという意味において、提案されるアルゴリズムは因果的に最適である。それ故、復号化器はまた、品質係数λを比較することにより、同一の凸包及び同一の分割点を更に再構築することができる。
【００５１】
図５は、上述したアルゴリズムを適用することが可能なスケーラブルなビデオシステム２２を示す。前記スケーラブルなビデオシステムは、ビデオフレーム中の複数のマクロブロックについて（ラン，レングス）対を表すデータを持つ少なくとも１つの上位レイヤと基本レイヤとにデータを分割することが可能なスケーラブルソース符号化器２４を含む。エンコーダ２４は、コンピュータ実行可能な処理ステップを保存するメモリ２６と、分割点を決定するためにメモリ２６に保存された前記処理ステップを実行するプロセッサ２８とを含む。このことは、例えば因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配のみを分析し、分割点以前の（ラン，レングス）対のみを基本レイヤに含め、前記分割点より後の（ラン，レングス）対を上位レイヤに含めることによってのように、上述した方法で実現されても良い。プロセッサ２８はかくして、（ラン，レングス）対の全ての隣接する対の間の線の勾配を決定することにより、及び前記（ラン，レングス）対の隣接する対の間の線の勾配に基づきどの（ラン，レングス）対が因果的凸包上に存するかを決定することにより、前記分割点を決定することができる。前記分割点は次いで、前記因果的凸包上に存する（ラン，レングス）対の隣接する対の間の線の勾配に基づいて決定される。
【００５２】
システム２２はまた、基本レイヤ及び上位レイヤからのデータをマージすることが可能なスケーラブル復号化器３０を含む。復号化器３０は、コンピュータ実行可能な処理ステップを保存するメモリ３２と、メモリ３２に保存された処理ステップを実行し、基本レイヤ及び上位レイヤを受信し、因果的な（ラン，レングス）対のみを分析することにより、基本レイヤ及び上位レイヤに含まれる（ラン，レングス）対に基づいて分割点を決定するプロセッサ３４とを含む。
【００５３】
本発明の説明的な実施例はここで添付する図を参照しながら説明されたが、本発明はこれらの実施例のみに限定されるものではなく、本発明の範囲又は精神から逸脱することなく、種々の他の変更及び修正が当業者によって実行され得ることは理解されるべきである。
【図面の簡単な説明】
【００５４】
【図１】凸状レート−歪（Ｒ−Ｄ）曲線の例である。
【図２】他のＲＤＤＰ手法の適用は最適な分割点値を提供しないが、本発明の実施例が適用され得る、非凸状のＲ−Ｄ曲線を示す。
【図３】本発明によるビデオデータを処理する方法におけるステップを示すフロー図である。
【図４】本発明によるアルゴリズムが適用される、ＤＣＴブロックについての切断点により形成される凸包を示す。
【図５】本発明による手法を適用することが可能なビデオシステムの図を示す。
【図１】
2007506347.tif 000009
【図２】
2007506347.tif 000010
【図３】
2007506347.tif 000011
【図４】
2007506347.tif 000012
【図５】
2007506347.tif 000013
【国際調査報告】
2007506347.tif 000014
2007506347.tif 000015