(57)【要約】【課題】Ｈ．２６４の動き推定の計算量を低減する適応的計算量制御アルゴリズムが提案される。【解決手段】予期されるＲＤ符号化利得の損失に基づいて動き推定の計算量を制限することを主旨とする。計算量を所望のレベルに効率的に低減するために、動き推定に計算量スケーラビリティを与えて、ビデオ品質と計算量との間で柔軟なトレードオフを行うようにＡＣＣが設計される。本発明では、提案するアルゴリズムを用いて、ＲＤ性能を大きく低下させることなく動き推定の計算量を３／４に低減できることを実証する。【選択図】図１
2007166608.tif 000002
【特許請求の範囲】
【請求項１】
複数のマクロブロックをそれぞれ含むフレームの列を含むビデオの階層レベルを上から下の順番に解析する工程と、
計算量予算の一部を前記解析に応じて各階層レベルに前記上から下の順番に割り当てる工程と、
前記ビデオの各マクロブロックを該マクロブロックに割り当てられた前記計算量予算の前記一部に応じて符号化して符号化ビットストリームを生成する工程と
を含むビデオ符号化方法。
【請求項２】
前記階層レベルは、ビデオレベル、ピクチャグループレベル、フレームレベル、マクロブロックレベル、ブロック境界レベル、及びブロックレベルを含む請求項１に記載のビデオ符号化方法。
【請求項３】
各ブロックは４×４の画素アレイである請求項２に記載のビデオ符号化方法。
【請求項４】
ピクチャグループの１番目のフレームは瞬時復号更新ピクチャである請求項２に記載のビデオ符号化方法。
【請求項５】
前記符号化は符号化時間制限に従ってレート歪み損失を最小限に抑える請求項１に記載のビデオ符号化方法。
【請求項６】
前記符号化時間制限は、
【数１】
2007166608.tif 000047
であり、ここで、Ｎはマクロブロック符号化インスタンスであり、(オーバーバー)ｃｘは計算量ベクトルであり、ＪＯＰＴは動き推定が計算量制約なしで適用されるときのラグランジュレート歪みコストであり、λはラグランジュ乗数であり、ωｌはブロックサイズｌを有するブロック境界の重みであり、ｃｍｋはｋ番目のマクロブロックにおける境界ｍの探索点の数であり、Ｋはフレーム内のマクロブロックの総数であり、Ｌは所与のマクロブロックのブロック境界の数であり、Ｍはブロック境界内のブロック数であり、Ｂｉ(ｊ)は、ｉ番目のピクチャグループにおけるｊ番目のフレームに割り当てられたフレーム予算である請求項５に記載のビデオ符号化方法。
【請求項７】
前記ピクチャグループレベルの任意のピクチャグループについて１番目のフレームの制約なしの動き推定を求める工程と、
前記ピクチャグループレベルにおける次のフレームについて、前記１番目のフレームの動き推定に割り当てられた計算量予算を目標予算から引くことによってフレームレベルの計算量予算を求める工程と、
前記ピクチャグループにおける残りのフレームの計算量予算を、フレームレベルの計算量の処理時間が減少する場合に増加させることによって更新する工程と、
そうでない場合に、前記ピクチャグループにおける残りのフレームの前記計算量予算を減少させる工程と
をさらに含む請求項４に記載のビデオ符号化方法。
【請求項８】
複数のマクロブロックをそれぞれ含むフレームの列を含むビデオの階層レベルを上から下の順番に解析するとともに、計算量予算の一部を該解析に応じて各階層レベルに前記上から下の順番に割り当てるように構成された計算量解析／割り当てユニットと、
前記ビデオの各マクロブロックを、該マクロブロックに割り当てられた前記計算量予算の前記一部に応じて符号化して符号化ビットストリームを生成するように構成された符号化ユニットと
を備えるビデオ符号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはビデオ符号化に関し、特に、ビデオ符号化中の動き推定の計算量を適応的に制御することに関する。
【背景技術】
【０００２】
Ｈ．２６４／ＡＶＣビデオ圧縮規格は、従来の規格に比べて高い圧縮効率を提供する。ＭＰＥＧ−４パート１０としても知られるＨ．２６４は、デジタルビデオコーデックの規格である。Ｈ．２６４規格と、ＭＰＥＧ−４パート１０規格(ＩＳＯ／ＩＥＣ１４４９６−１０)とは、技術的に同一である。この規格によって規定される技術は、高度ビデオ符号化(ＡＶＣ)としても知られる。
【０００３】
Ｈ．２６４／ＡＶＣは、可変ブロックサイズ動き補償、Ｑｕａｒｔｅｒ−ＰＥＬ動き補償、及び長期メモリ(long-term memory)動き補償を含む一組の高度な符号化ツールにより符号化利得を達成する。しかし、最適な圧縮効率が達成されるような、動きベクトル及び予測モードを含む一組の最適な符号化パラメータを選択することは難しい。
【０００４】
特に、可変ブロックサイズを用いる長期メモリ動き補償予測(ＬＴＭＣＰ)は、Ｈ．２６４／ＡＶＣエンコーダにおける主要な計算量のボトルネックである。一般性を失うことなく、利用可能な計算資源が限られているとき、リアルタイムビデオ符号化の計算量はスケーラブル(増減可能)であることが好ましい。
【０００５】
従来技術では、Ｈ．２６４／ＡＶＣエンコーダのモード決定及び動き推定の計算量を低減するために様々な試みがなされてきた。１つの方法は、ブロックサイズの異なる動きベクトル間の相関に基づいて初期探索中心を求める(Z. Zhou、M.-T. Sun、Y.-F. Hsu著「Fast variable block-size motion estimation algorithm based on merge and slit procedures for H.264/MPEG-4 AVC」Proceedings of the 2004 International Symposium on Circuits and Systems, Vol. 3, May 2004)。
【０００６】
他の方法は、効率的予測ゾーン(efficient predictive zonal)アルゴリズム(ＥＰＺ)等の高速動き推定プロセスを用いる(A.M. Tourapis、O.C. Au、M.L. Liou著「Highly efficient predictive zonal algorithms for fast block-matching motion estimation」IEEE Transactions on Circuits and Systems for Video Technology, Vol. 12, Issue 10, Oct. 2002、UMHexagonS、Jianfeng Xu、Zhibo Chen、Yun He著「Efficient fast ME predictions and early-termination strategy based on H.264 statistical characters」Proceedings of the Joint Conference of the Fourth International Conference on Information, Communications and Signal Processing, 2003 and the Fourth Pacific Rim Conference on Multimedia. Vol. 1, Dec. 2003、及びSEA, M. Yang、H. Cui、K. Tang著「Efficient tree structured motion estimation using successive elimination」IEE Proceedings- Vision, Image and Signal Processing, Vol. 151, Issue 5, Oct. 2004)。これらの方法は、動き推定中の探索点の数を低減する。
【０００７】
他の方法は、最新偏向(recent-biased)探索(Chi-Wang Ting、Hong Lam、Lai-Man Po著「Fast block-matching motion estimation via recent-biased search for multiple reference frames」International Conference on Image Processing, Vol. 4, Oct. 2004)、及び順方向動き追跡(M-J. Chen、Y-Y. Chiang、H-J Li、M-C. Chi著「Efficient multi-frame motion estimation algorithms for MPEG-4 AVC/JVT/H.264」Proceedings of the 2004 International Symposium on Circuits and Systems, Vol. 3, May 2004)を用いて、長期メモリ動き推定の計算量を低減する。
【０００８】
粗密(coarse-to-fine)手法に基づくモード決定方法は、ブロックサイズにわたる単調なレート歪み(ＲＤ)関係を仮定する(P. Yin、H.C. Tourapis、A.M. Tourapis、J. Boyce著「Fast mode decision and motion estimation for JVT/H.264」IEEE International Conference on Image Processing, Vol. 3, Sept. 2003)。しかし、計算量のさらなる低減が依然として強く望まれている。
【０００９】
いくつかの方法は、ビデオエンコーダの計算量を直接制御する。Zhong他は、符号化プロセス中にバッファ監視を使用することによる符号化計算量の制御を開示する(下記特許文献１参照)。Song他は、動き推定の打ち切り(early termination)閾値を調整し、ＤＣＴ変換は平均数の探索点を用いる(下記特許文献２参照)。El-Maleh他は、メモリにおける計算量と処理時間とのバランスをとるために、構成可能な閾値に基づいて予測符号化セクション及び非予測符号化セクションを選択する(下記特許文献３参照)。
【００１０】
符号化計算量をヒューリスティックに制御するほとんどの方法は、符号化プロセスの計算量を近似して閾値を調整し、符号化モードの決定、又はＤＣＴ若しくは動き推定等のプロセスの打ち切りといった目的を達成する。
【００１１】
【特許文献１】米国特許出願公開第２００３／０１２３５４０号明細書
【特許文献２】米国特許出願公開第２００３／０１５６６４４号明細書
【特許文献３】米国特許出願公開第２００５／０１０５６１５号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１２】
符号化プロセスにおける主な計算量は、動き推定及びモード決定によるものである。しかし、これまでのところ、これらのプロセスの計算量の正確な制御はできなかった。
【００１３】
本発明の一つの実施の形態は、ビデオ符号化プロセスの計算量を長期メモリ動き補償予測(ＬＴＭＣＰ)及び予測符号化モードの決定により効率的に制御するための適応的計算量制御の枠組みを提供する。
【００１４】
本発明の目的は、計算量のスケーラブルなエンコーダを提供することである。本発明の一つの実施の形態は、可変ブロックサイズを用いて、レート歪み性能の低下を最小限に抑えて符号化計算量を所望のレベルまで低減する適応的計算量制御の枠組みを提供する。
【００１５】
動き補償ハイブリッド動き補償ビデオ符号化における動き推定の計算量を制御する方法を開示する。動き推定の計算量は、探索点の数を重み付けしたものとして定義される。計算量制御プロセスは、ピクチャグループ、フレーム、マクロブロック、ブロック境界、及びブロックに対して計算量を階層的に降順で割り当てる。
【課題を解決するための手段】
【００１６】
本発明は、複数のマクロブロックをそれぞれ含むフレームの列を含むビデオの階層レベルを上から下の順番に解析する工程と、計算量予算の一部を前記解析に応じて各階層レベルに前記上から下の順番に割り当てる工程と、前記ビデオの各マクロブロックを該マクロブロックに割り当てられた前記計算量予算の前記一部に応じて符号化して符号化ビットストリームを生成する工程とを含むビデオ符号化方法にある。
【００１７】
また、複数のマクロブロックをそれぞれ含むフレームの列を含むビデオの階層レベルを上から下の順番に解析するとともに、計算量予算の一部を該解析に応じて各階層レベルに前記上から下の順番に割り当てるように構成された計算量解析／割り当てユニットと、前記ビデオの各マクロブロックを、該マクロブロックに割り当てられた前記計算量予算の前記一部に応じて符号化して符号化ビットストリームを生成するように構成された符号化ユニットとを備えるビデオ符号化システムにある。
【発明の効果】
【００１８】
本発明では、計算量のスケーラブルなビデオの符号化を提供することができる。
【発明を実施するための最良の形態】
【００１９】
図１に示すように、本発明の一実施の形態は、ビデオ１０１の符号化(１２０)中に動き推定の計算量を制御するシステム及び方法１００を提供する。完全な方法を図４に示す。計算量を制御する方法及びシステムは、図２に示すように、計算量予算１０３をビデオの階層レベルに適応的に割り当てる。
【００２０】
図１において、実線はデータフローを示し、破線は制御を示す。システムは、入力１０１としてビデオを取り入れ、出力１０２として符号化ビットストリームを、特定のアプリケーションによって提供される計算量予算１０３に応じて生成する。計算量予算１０３を、予期されるレート歪み(ＲＤ)コスト利得に応じて符号化ユニット１２０に割り当て(１１０)、最適な計算量割り当てを達成する。
【００２１】
図２に示すように、階層レベルは、ビデオ１０１、ピクチャグループ(ＧＯＰ)２０５、フレーム２１０、マクロブロック２１５、ブロック境界２２０、及びブロック２２５を含むことができる。各ブロックは画素２３０の４×４アレイである。ＧＯＰの１番目のフレーム２２１は瞬時復号更新ピクチャ(instantaneous decoding refresh picture)(ＩＤＲ)と呼ばれる。
【００２２】
再び図１を参照すると、入力ビデオ１０１が解析／割り当てユニット１１０及び符号化ユニット１２０に供給される。符号化ユニットは、各階層レベルに配分された計算量予算１１１に従って出力ビットストリーム１０２を生成する。符号化中、符号化ユニット１２０は、実際に消費された計算量予算１２１を出力して計算量解析／割り当てユニット１１０に戻す。この割り当てユニットは、それに応じて、配分された計算量予算１１１を動的に調整する。
【００２３】
適応的計算量制御(ＡＣＣ)方法は、レート歪み損失を最小限に抑えるように、
【００２４】
【数１】
2007166608.tif 000003
【００２５】
のような所与の符号化時間制限に従って、利用可能な計算量予算１１１を符号化ユニット１２０にレベル毎に割り当てる。ここで、Ｎ、(オーバーバー)ｃｘ、ＪＯＰＴ、ｔｘ及びＴは、マクロブロック符号化インスタンス、そのユニットに割り当てられる計算量ベクトル、所与の動き推定アルゴリズムが計算量制約なしで完全に使用されるときのラグランジュＲＤ(レート歪み)コスト、動き推定時間、及び動き推定のための所与の符号化時間予算をそれぞれ表す。
【００２６】
ラムダ(λ)はラグランジュ乗数であり、マクロブロックの符号化、本発明の場合には動き推定中にレート歪みのトレードオフを制御する。すなわち、
コストＪ＝歪み(Ｄ)＋ラムダ＊レート(Ｒ)
である。例として、λ＝０であるとき、最適化は歪みを最小化し、λ＝∞であるとき、最適化はレートを最小化する。一般に、比較的低ビットレートにおいてλは増加するため、レート項が最適化のより重要な部分となる。
【００２７】
ＡＣＣ方法の目的は、符号化階層の各レベルにおける動き推定計算量にスケーラビリティを与えることである。したがって、本方法は、エンコーダが特定の動き推定プロセスについて計算量を所望のレベルまで低減させることを可能にする。同時に、ＡＣＣ方法は、ラグランジュＲＤコスト−動き推定計算量(Ｊ−Ｃ)曲線に基づく計算量の割り当てを使用することによって、予期されるＲＤ性能の低下を最小限に抑える。
【００２８】
動き推定の計算量の定義
動き推定の計算量は、動き推定時間に比例する、機械に依存しない測度、例えば、探索点の数を重み付けしたものを使用して調整することができる。動き推定では、画像のブロックが参照画像と比較されて、参照画像のどのブロックがそのブロックに最も良く一致するかが判定される。参照画像中の最良一致ブロックを判定するために、差分測度を用いて、マクロブロックと、参照画像中の可能な各ブロックとの間の差分量を測定する。
【００２９】
探索点が、動き推定プロセスにおいて現ブロックと比較される参照画像中のブロックとして定義される。探索点は通常、探索窓内に限定される。網羅的な動き推定では、探索窓内の全ての可能な探索点が評価される。高速動き推定方法は、探索窓内の全ての可能な探索点のサブセットを評価する。動き推定の計算量は、各ブロック境界における探索点の数を重み付けしたものの一次結合によって次のように定義される。
【００３０】
【数２】
2007166608.tif 000004
【００３１】
ここで、ωｌはブロックサイズｌを有するブロック境界の重みを表し、ｃｍｋはｋ番目のマクロブロックにおける境界ｍの探索点の数である。変数Ｋ、Ｌ、Ｍ及びＢｉ(ｊ)はそれぞれ、フレーム内のマクロブロックの総数、所与のマクロブロックのブロック境界の数、ブロック境界内のブロック数、及びｉ番目のピクチャグループ(ＧＯＰ)におけるｊ番目のフレームに割り当てられたフレーム予算である。重みωｌは、大きな境界ほど動きコストの計算時間が長くなるため、次のようにブロック境界に基づく。
【００３２】
【数３】
2007166608.tif 000005
【００３３】
ここで、Ｎ、Ｍ、及びｎ４×４は、画素数で表される水平ブロック境界長、画素数で表される垂直ブロック境界長、及び最小ブロック内の画素数である。最小ブロック内の画素数は例えば１６である。制約
【００３４】
【数４】
2007166608.tif 000006
【００３５】
を式(２)で置き換えることにより、式(１)は次のようになる。
【００３６】
【数５】
2007166608.tif 000007
【００３７】
フレームレベルの計算量制御
制約なしの動き推定が、１番目の予測フレームに対して行われる。ＧＯＰにおける２番目の予測フレームから、フレームレベルの計算量予算Ｂｉ(ｊ)(ｊ＝２，・・・，Ｎｉ)は、式(４)に記載されるように、前のフレームの動き推定に割り当てられた計算量予算ｂｉ(ｊ−１)を、前の目標予算Ｂｉ(ｊ−１)から引くことによって求められる。ＧＯＰにおける残りのフレームについては、単位計算量の処理時間が減少する場合に計算量予算を増加させ、逆の場合には減少させる。
【００３８】
現フレームに対する計算量予算が割り当てられ、次のようにフレーム毎に連続して更新される。
【００３９】
【数６】
2007166608.tif 000008
【００４０】
ここで、Ｂｉ(ｊ)はｉ番目のＧＯＰにおける(ｊ−１)番目のフレームの後の計算量予算であり、
【００４１】
【数７】
2007166608.tif 000009
【００４２】
は、ｉ番目のＧＯＰにおける１番目の予測フレームの動き推定時間Ｔｉ(ｊ)における標準化された計算量である。変数Ｎｉ、Ｆｒ及びｂｉ(ｊ−１)はそれぞれ、予測フレームの総数、事前に定義されたフレームレート、及び(ｊ−１)番目のフレームにおいて用いられる実際の計算量予算である。
【００４３】
初期の標準化計算量Ｒｉ(ｊ＝１)は、制約なしの動き推定を行うことによって得られる。１番目のフレームに対してフルの動き探索を行う理由は、重み付けされた探索点と動き推定時間との比を得るためである。これにより、１番目のフレームに対する不正確な予算割り当てによるＲＤ性能の低下が防止される。
【００４４】
マクロブロックレベルの計算量制御
現フレームに対する計算量予算
【００４５】
【数８】
2007166608.tif 000010
【００４６】
は最初に、予期されるＲＤ性能及び関連する必要な計算量に応じてマクロブロックＭ１，・・・，ＭＫの各々に割り当てられる。各マクロブロックの符号化の終了時に、残りのマクロブロックに対する初期予算を、計算量予算
【００４７】
【数９】
2007166608.tif 000011
【００４８】
に基づいて更新し、以前に符号化されたマクロブロックに割り当てる。現フレームが初期予算に可変量の追加予算を足したもの
【００４９】
【数１０】
2007166608.tif 000012
【００５０】
で符号化される場合、
【００５１】
【数１１】
2007166608.tif 000013
【００５２】
が、残りのフレームのフレーム予算に加算される。
【００５３】
マクロブロックレベルの計算量制御は、Ｊ−Ｃ曲線に基づく割り当てを使用することによって、予期されるＲＤ性能の低下が最小限に抑えられるように、利用可能な計算量予算を各マクロブロックに割り当てるように設計される。
【００５４】
現マクロブロックのＪ−Ｃ曲線を推定するために、前のフレームにおける連結したマクロブロックの曲線を反復毎にメモリに記憶する。反復は、任意数の重み付けされた探索点として定義することができる。ここでは反復は、各ブロックサイズ１≦ｌ≦Ｌ＝７の１つの参照フレーム１≦ｎｒｅｆ≦Ｎｒｅｆにおいて用いられる重み付けされた探索点の数として
【００５５】
【数１２】
2007166608.tif 000014
【００５６】
のように定義される。１つの参照のみを用いる場合、最大で７回の反復、すなわちＪ−Ｃ曲線における７つの(Ｊ，Ｃ)対が生じる可能性があり、ブロック順序が降順に１６×１６から４×４へチェックされる。
【００５７】
Ｊ−Ｃ曲線によって示される実験結果から、本発明者は、背景又は滑らかに移動する物体のような、単純な動きを有するマクロブロックの大部分が、凸形状ではなく直線的なＪ−Ｃ曲線を有することに気付いた。その一方で、動きの複雑なマクロブロックは概ね凸状のＪ−Ｃ曲線を示した。
【００５８】
図５は、例示的なＪ−Ｃの凸状曲線５００を示す。縦軸Ｊはラグランジュレート歪み(ＲＤ)コストであり、横軸Ｃは制約なしの動き推定に対する計算量である。
【００５９】
直感的に、細かいエリアにおける複雑な動きは通常、大きなブロックに対して大きな符号化コストを生じ、コストは、ブロックサイズが小さくなるにつれて下位レベルに収束する。対照的に、動きの滑らかなエリアは概して、より大きなブロックサイズに迅速に収束する。また、本発明者は、現マクロブロックのＪ−Ｃ曲線と、その時間的に連結したマクロブロックのＪ−Ｃ曲線との間に強い相関があることに気付いた。したがって、現マクロブロックのＪ−Ｃ曲線は、前のフレームにおける連結マクロブロックのＪ−Ｃ曲線から推定される。推定誤差によるＪ−Ｃの傾きの不一致問題は、境界レベル予算の調整及び更新により効率的に対処される。
【００６０】
各マクロブロックの推定Ｊ−Ｃ曲線は、最大で
【００６１】
【数１３】
2007166608.tif 000015
【００６２】
の複数の傾きを有する可能性がある。計算量予算をフレームに効率的に割り当てるために、貪欲探索をＪ−Ｃ曲線に適用して、割り当てるべき計算量予算を求める。
【００６３】
まず、ゼロ値の予算を有するブロック境界を防ぐために、最低予算がフレーム内の各マクロブロックに割り当てられる。各マクロブロックにつき１つの点が最低予算として選択される。各点は、各マクロブロックの予測動きベクトルに割り当てられる。予測動きベクトルは、そのマクロブロックの空間近傍における動きベクトルの中央値ベクトルである。区分線形Ｊ−Ｃ曲線に基づいて、以下の制約に従って予算を使い切るまで、貪欲探索を用いて初期予算を各マクロブロックに割り当てる。
【００６４】
最高予算：
【００６５】
【数１４】
2007166608.tif 000016
【００６６】
である場合、各マクロブロックの予算は、連結するマクロブロックのＪ−Ｃ曲線における最高予算によって決まり、残りの
【００６７】
【数１５】
2007166608.tif 000017
【００６８】
は、式(５)及び調整された最低の計算量予算に基づいて再分配される。
【００６９】
Ｊ−Ｃ曲線の近似：前フレームの各マクロブロックは、
【００７０】
【数１６】
2007166608.tif 000018
【００７１】
回の反復を行って、
【００７２】
【数１７】
2007166608.tif 000019
【００７３】
に従うｎｋ個の傾きを有することができる。ここで、ｋ＝［１，・・・，Ｋ］であり、ｘ＝［１，・・・，ｎｋ］であり、ｋ、ｘ及びＫはそれぞれ、マクロブロックインデックス、反復インデックス、及びフレーム内のマクロブロックの総数である。各傾きは、その反復におけるＲＤ符号化利得の向上の可能性を示す。
【００７４】
Ｊ−Ｃ曲線の凸包：K. L. Clarkson及びP. W. Shor著「Applications of Random Sampling in Computational Geometry, II」Discrete and Computational Geometry, Vol. 4, No. 1, pp. 387-421, 1989(参照により本明細書中に援用される)に記載されるようなＯ(ｎ  ｌｏｇ  ｎ)プロセスを用いることによってマクロブロック毎に凸包が構成される。
【００７５】
計算量の割り当て：推定区分線形Ｊ−Ｃ曲線は凸状であるため、貪欲探索を用いて、傾き
【００７６】
【数１８】
2007166608.tif 000020
【００７７】
に基づいて探索点を割り当てることができる。
【００７８】
全予算から引かれる最低予算を各マクロブロックについて引いたものである残りの予算を、図３に示すように、次のように割り当てる。
ａ．全てのマクロブロックについて、
【００７９】
【数１９】
2007166608.tif 000021
【００８０】
のような初期の傾きリストを構築し、初期予算を全てのマクロブロックについて最高予算
【００８１】
【数２０】
2007166608.tif 000022
【００８２】
として設定する。
ｂ．リスト中の各マクロブロックの傾き
【００８３】
【数２１】
2007166608.tif 000023
【００８４】
を比較し、最小の傾きを有するマクロブロックに
【００８５】
【数２２】
2007166608.tif 000024
【００８６】
を割り当てる。
ｃ．選択されたマクロブロックｋｍｉｎの反復インデックスｘを低減して
【００８７】
【数２３】
2007166608.tif 000025
【００８８】
となるようにし、それに応じて傾きリストを更新する。
ｄ．全ての傾きインデックスがインデックスｘ＝１を示すか、又はフレーム予算Ｂｉ(ｊ)を使い果たすまで、ステップｂ．及びステップｃ．を繰り返す。
ｅ．予算が残っている場合、残りの予算を、
【００８９】
【数２４】
2007166608.tif 000026
【００９０】
のような初期の割り当て量である推定需要に応じて全てのマクロブロックに再分配する。
ｆ．１つの傾きの近似の場合、式(６)を用いた単純な傾きにより重み付けされた割り当てを初期の割り当て：
【００９１】
【数２５】
2007166608.tif 000027
【００９２】
に適用することができる。
【００９３】
次に、最低の計算量予算を次のように調整することができる。本発明では、初期に割り当てられた最低の計算量予算に応じて各マクロブロックについて動き推定を行い、現フレームにおける反復毎にＪ−Ｃの傾き
【００９４】
【数２６】
2007166608.tif 000028
【００９５】
を測定する。時間的に隣接するＪ−Ｃ曲線は相関するが、現マクロブロックのＪ−Ｃ曲線は、初期の割り当てに使用された連結マクロブロックとは異なる傾きを有する可能性があることに留意することが重要である。また、現マクロブロックのＪ−Ｃの傾き
【００９６】
【数２７】
2007166608.tif 000029
【００９７】
は、現在の反復について動き推定が完了すると得られる。Ｊ−Ｃ曲線の不一致の影響を動的に補償するために、追加の反復についてε個までの少数の探索点が条件付きで許可される。
【００９８】
【数２８】
2007166608.tif 000030
【００９９】
追加の探索点の量
【０１００】
【数２９】
2007166608.tif 000031
【０１０１】
が、残りのマクロブロックのマクロブロック予算に加算される。直感的に、追加の探索点
【０１０２】
【数３０】
2007166608.tif 000032
【０１０３】
は、新たな傾きが前の傾きよりも大きい、すなわち、
【０１０４】
【数３１】
2007166608.tif 000033
【０１０５】
である限り、事前に定義された閾値
【０１０６】
【数３２】
2007166608.tif 000034
【０１０７】
を満たすまで、ブロックサイズレベルで割り当てることができるマクロブロックレベルでの増分又は減分の和である。
【０１０８】
現マクロブロックの動き推定が完了すると、計算量予算が更新される。全てのマクロブロックが初期のフレーム予算に可変量の追加予算を加えたものＢｉ(ｊ)±ΔＢで符号化される場合、
【０１０９】
【数３３】
2007166608.tif 000035
【０１１０】
が、残りのフレームのフレーム予算に加算される。
【０１１１】
ブロック境界レベルの計算量制御
計算量予算は次のようにマクロブロックに割り当てられる。ｋ番目のマクロブロックについて、フレームｊにおけるマクロブロックレベルの計算量予算
【０１１２】
【数３４】
2007166608.tif 000036
【０１１３】
は、最も確度の高いブロック境界から最も確度の低いブロック境界へと割り当てられる。ブロック境界は、推定ＲＤコストに基づく優先順位に応じてソートされる。
【０１１４】
ブロック境界のソートには高速インターモード決定プロセスを用いることができる(Qionghai Dai、Dongdong Zhu、Rong Ding著「Fast mode decision for inter prediction in H.264」International Conference on Image Processing, Vol. 1, pp. 119-122, Oct. 2004(参照により本明細書中に援用される))。
【０１１５】
各ブロック境界の符号化の終了時に、残りのブロック境界の初期予算
【０１１６】
【数３５】
2007166608.tif 000037
【０１１７】
が、以前に符号化されたブロック境界に割り当てられた計算量予算
【０１１８】
【数３６】
2007166608.tif 000038
【０１１９】
に基づいて更新される。全てのブロック境界が初期マクロブロック予算に可変量の追加予算を足したもの
【０１２０】
【数３７】
2007166608.tif 000039
【０１２１】
で符号化される場合、
【０１２２】
【数３８】
2007166608.tif 000040
【０１２３】
が、残りのマクロブロックのマクロブロック予算に加算される。本発明の一実施の形態において、エンコーダは、マクロブロック予算を各ブロック境界に均等に割り当てることができる。
【０１２４】
ブロックレベルの計算量制御
図４は、ｌ番目のブロック境界におけるブロックレベルの計算量制御を示す。マクロブロックｋのブロック境界レベルの計算量予算
【０１２５】
【数３９】
2007166608.tif 000041
【０１２６】
は、最も確度の高いブロックから最も確度の低いブロックへと割り当てられる。ブロックは、推定ＲＤコストに基づく優先順位に応じてソートされる。動き探索は、割り当てられたブロックレベルの予算
【０１２７】
【数４０】
2007166608.tif 000042
【０１２８】
が許す限り、複数の参照フレームにわたって行われる。
【０１２９】
各ブロックの符号化の終了時に、残りのブロックの初期予算
【０１３０】
【数４１】
2007166608.tif 000043
【０１３１】
が、以前に符号化されたブロックに割り当てられた計算量予算
【０１３２】
【数４２】
2007166608.tif 000044
【０１３３】
に基づいて更新される。全てのブロックが初期ブロック予算に可変量の追加予算を足したもの
【０１３４】
【数４３】
2007166608.tif 000045
【０１３５】
で符号化される場合、
【０１３６】
【数４４】
2007166608.tif 000046
【０１３７】
が、残りのブロック境界のブロック境界予算に加算される。簡略にするために、エンコーダは、ブロック境界予算を各ブロックに均等に割り当てることができる。
【０１３８】
図４は、ビデオの符号化中に動き推定の計算量を制御する方法の反復を各階層レベルについてより詳細に示す。各ＧＯＰ４１０について、フレーム４２０、マクロブロック４３０、ブロック境界４４０、及びブロック４５０がそれぞれ、フレーム４１１、マクロブロック４２１、ブロック境界４３１、ブロック４４１、及び動き推定４５１を割り当てるステップを行う。その後、ＧＯＰ４１２の最後に、フレーム４２２、マクロブロック４３２、ブロック境界４４２、及びブロック４５２がそれぞれ、ＧＯＰ４１３、フレーム４２３、マクロブロック４３３、ブロック境界４４３、及びブロック４５３の予算をそれぞれ、最後のＧＯＰ４１４、フレーム４２４、マクロブロック４３４、ブロック境界４４４、及びブロック４５４まで更新する。
【０１３９】
所与のマクロブロックのブロック境界又はブロック境界の組を、マクロブロックの所与の計算量予算に基づいて決定することができる。
【図面の簡単な説明】
【０１４０】
【図１】本発明の一実施の形態によるビデオエンコーダの図である。
【図２】計算量予算を割り当てるためのビデオの階層レベルの図である。
【図３】本発明の一実施の形態による計算量予算を割り当てる工程の図である。
【図４】本発明の一実施の形態による適応的計算量制御の流れ図である。
【図５】本発明の一実施の形態によるＪ−Ｃ曲線の一例である。
【図１】
2007166608.tif 000048
【図２】
2007166608.tif 000049
【図３】
2007166608.tif 000050
【図４】
2007166608.tif 000051
【図５】
2007166608.tif 000052
【外国語明細書】
2007166608.tif 000053
2007166608.tif 000054
2007166608.tif 000055
2007166608.tif 000056
2007166608.tif 000057
2007166608.tif 000058
2007166608.tif 000059
2007166608.tif 000060
2007166608.tif 000061
2007166608.tif 000062
2007166608.tif 000063
2007166608.tif 000064
2007166608.tif 000065
2007166608.tif 000066
2007166608.tif 000067
2007166608.tif 000068
2007166608.tif 000069
2007166608.tif 000070
2007166608.tif 000071
2007166608.tif 000072
2007166608.tif 000073
2007166608.tif 000074
2007166608.tif 000075
2007166608.tif 000076
2007166608.tif 000077
2007166608.tif 000078
2007166608.tif 000079
2007166608.tif 000080