(57)【要約】  本発明は、ビデオシーケンスにおいて画像の現在のブロックのための動きベクトルを決定するための探索空間の構築に関する。探索空間の構築は、第１部分探索空間及び第２部分探索空間がそれぞれ決定される２つのメインステージに分割される。動きベクトルの初期推定値に基づいて、第１探索空間が最初に構築される。第１探索空間の第１動き候補及び第２動き候補は、コスト関数に従って特定される。第１動きベクトル候補及び第２動きベクトル候補に基づいて、第２探索空間が構築される。現在のブロックのための動きベクトルは、第１探索空間及び第２探索空間の動きベクトル候補から選択される。
2020526112.tif 000002
【特許請求の範囲】
【請求項１】
映像フレームの現在のブロックのインター予測に用いられる動きベクトルを決定するための装置であって、前記装置は、
前記動きベクトルの推定値を取得し、前記推定値に基づいて、複数の動きベクトル候補を備える第１探索空間を決定し、コスト関数に従って、前記第１探索空間における第１動きベクトル候補及び第２動きベクトル候補を選択し、及び前記第１動きベクトル候補及び前記第２動きベクトル候補に基づいて、１つ又は複数の動きベクトル候補を備える第２探索空間を決定するように構成された探索空間決定ユニット（３１０）と、
前記第１探索空間及び前記第２探索空間の前記動きベクトル候補の中から前記現在のブロックのための前記動きベクトルを選択するように構成された動きベクトル選択ユニット（３４０）と
を備える装置。
【請求項２】
前記コスト関数は、予め定められたテンプレートに基づいており、前記動きベクトル候補のそれぞれに対して、前記予め定められたテンプレートと、前記動きベクトル候補のそれぞれによって指し示された予測値との間の類似性のレベルを示す、請求項１に記載の装置。
【請求項３】
前記探索空間決定ユニット（３１０）は、前記第１動きベクトル候補及び前記第２動きベクトル候補が指し示す位置を接続する直線の方向に従って前記第２探索空間のサイズ及び／又は位置を決定するように構成される、請求項１又は２に記載の装置。
【請求項４】
前記探索空間決定ユニット（３１０）によって前記第１探索空間を前記決定することは、
整数のピクセル解像度を有するように前記第１探索空間を設定することを備え、
前記探索空間決定ユニットによって前記第２探索空間を前記決定することは、
前記第１動きベクトル及び前記第２動きベクトル候補（ＭＶ０'，ＭＶ０'ｓｅｃｏｎｄＢｅｓｔ）が指し示す前記位置（４０９，４０６）を接続する直線の前記方向にある位置（４１１，４１２）を指し示す１つ又は複数の動きベクトル候補を、前記第２探索空間に含めることを備え、前記第２探索空間は、小数のピクセル解像度を有する、
請求項３に記載の装置。
【請求項５】
前記第２探索空間の少なくとも一つの前記動きベクトル候補は、前記第１動きベクトル候補及び前記第２動きベクトル候補（ＭＶ０'，ＭＶ０'ｓｅｃｏｎｄＢｅｓｔ）によって指し示された前記位置（４０９，４０６）間の位置（４１１）を指し示す、
請求項４に記載の装置。
【請求項６】
前記探索空間決定ユニット（３１０）は、
少なくとも二つの動きベクトル候補がそれぞれ指し示す少なくとも二つの位置を含む領域の位置を決定するように構成され、前記少なくとも二つの位置は、前記第２探索空間のピクセル解像度において隣接し、
前記第１探索空間に属さない前記領域のこれらの位置として前記第２探索空間を決定するように構成される、
請求項１〜３の何れか一項に記載の装置。
【請求項７】
前記探索空間決定ユニットによって前記第１探索空間を前記決定することは、
前記動きベクトルの前記推定値によって指し示された位置に対して、前記第１探索空間のピクセル解像度において隣接する前記位置を指し示す前記動きベクトル及び動きベクトル候補の前記推定値を、前記第１探索空間に含めることを備える、
請求項１〜３の何れか一項、又は請求項６に記載の装置。
【請求項８】
前記探索空間決定ユニット（３１０）は、
前記第１探索空間において特定される前記第１動きベクトル候補及び前記第２動きベクトル候補によって、指し示された前記位置に対して、前記第１探索空間の前記ピクセル解像度において隣接し、前記動きベクトルの前記推定値によって指し示された前記位置とは異なる前記位置を指し示す動きベクトル候補を、前記第２探索空間の第１動きベクトル候補として選択するように構成される、
請求項７に記載の装置。
【請求項９】
前記探索空間決定ユニット（３１０）は、
前記動きベクトルの前記推定値と前記第２探索空間の前記候補とを接続する直線上にほぼ位置する、前記第２探索空間の解像度における、位置を指し示す動きベクトル候補を、前記第２探索空間の更なる動きベクトル候補として決定するように構成され、前記第２探索空間の前記ピクセル解像度は、前記第１探索空間の前記ピクセル解像度より高い、
請求項８に記載の装置。
【請求項１０】
前記第２探索空間の前記更なる動きベクトル候補は、前記第２探索空間の前記第１動きベクトル候補及び前記動きベクトルの前記推定値によって指し示された前記位置間にある位置を指し示す、
請求項９に記載の装置。
【請求項１１】
前記第２探索空間は、前記第１探索空間より高い解像度を有する、
請求項１〜１０の何れか一項に記載の装置。
【請求項１２】
前記現在のブロックに隣接する少なくとも一つのブロックの動きベクトルを含む動きベクトルのリストから前記動きベクトルの前記推定値を決定するための動きベクトル決定ユニットを
さらに備える、請求項１〜１１の何れか一項に記載の装置。
【請求項１３】
ビットストリームから複数の画像をデコードするためのビデオデコーダであって、
前記ビットストリームから前記動きベクトルの前記推定値の指示を取得するためのビットストリームパーサーと、
請求項１〜１２の何れか一項に記載の装置を含み、前記現在のブロックの前記動きベクトルが指し示す予測ブロックを決定するようにさらに構成されたインター予測ユニットと、
前記予測ブロックに基づいて、前記現在のブロックを再構築するための再構築ユニットと
を備える、ビデオデコーダ。
【請求項１４】
複数の画像をビットストリームにコード化するためのビデオエンコーダであって、
請求項１〜１２の何れか一項に記載の前記装置を含み、前記現在のブロックの前記動きベクトルが指し示す予測ブロックを決定するようにさらに構成されたインター予測ユニットと、
前記ビットストリームに前記動きベクトルの前記推定値の指示を含めるためのビットストリームフォーマーと、
前記予測ブロックに基づいて、前記現在のブロックを再構築し、メモリに再構築された前記ブロックを記憶するための再構築ユニットと
を備える、ビデオエンコーダ。
【請求項１５】
映像フレームの現在のブロックのインター予測に用いられる動きベクトルを決定するための方法であって、前記方法は、
前記動きベクトルの推定値を取得する段階と、
前記推定値に基づいて、複数の動きベクトル候補を備える第１探索空間を決定する段階と、
コスト関数に従って、前記第１探索空間においる第１及び第２動きベクトル候補を選択する段階と、
前記第１動きベクトル候補（ＭＶ０'）及び前記第２動きベクトル候補（ＭＶ０'ｓｅｃｏｎｄＢｅｓｔ）に基づいて、１つ又は複数の動きベクトル候補を備える第２探索空間を決定する段階と、
前記第１空間及び前記第２空間の前記動きベクトル候補の中から前記現在のブロックのための前記動きベクトルを選択する段階と
を備える、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオシーケンスにおいて画像のブロックの動きベクトルを決定するための探索空間の構築に関する。
【背景技術】
【０００２】
現在、ハイブリッドビデオコーデックは、予測コーディングを利用する。ビデオシーケンスの画像は、ピクセルのブロックに細分化され、これらのブロックは、その後、コーディングされる。ピクセルごとにブロックをコーディングする代わりに、全体のブロックは、ブロックの空間的又は時間的に近接した既にコード化されたピクセルを用いて予測される。エンコーダは、ブロックとその予測との間の差のみをさらに処理する。典型的には、さらなる処理は、変換領域において、ブロックピクセルの係数への変換を含む。  その後、係数は、さらに圧縮され（例えば、量子化を用いて）、ビットストリーム形式にさらに圧縮（例えばエントロピー符号化によって）されてもよい。ビットストリームは、デコーダがコード化されたビデオをデコード可能にするシグナリング情報をさらに含むことができる。例えば、シグナリングは、入力画像のサイズ、フレームレート、量子化ステップ指示、画像のブロックに適用予測、又は同様のものなどのエンコーダ設定に関する設定を含んでもよい。
【０００３】
ブロックとその予測との間の差は、ブロックの残差として知られている。より具体的には、ブロックのそれぞれのピクセルは、そのピクセルの強度レベルとその予測強度レベルとの差である残差を有する。ピクセルの強度レベルは、ピクセル値又はピクセルの値と称される。ブロックの全てのピクセルの残差は、集合的に、ブロックの残差と称される。言い換えれば、ブロックは、ブロックの全てのピクセルの残差からなるセット又はマトリクスである残差を有する。
【０００４】
時間的予測は、ビデオの画像（フレームとも称される）間の時間的相関を利用する。時間的予測は、それは異なる映像フレーム間（インター）の依存関係を用いて予測するので、インター予測とも呼ばれる。従って、現在のブロックとも称されるデコードされるブロックは、参照画像とも称される１つ又は複数のこれまでにデコードされた画像から予測される。１つ又は複数の参照画像は、ビデオシーケンスの表示順序で配置されている現在のブロックの中で、必ずしも、現在の画像に先行する画像ではない。エンコーダは、表示順序とは異なるコーディング順序で画像をコード化してもよい。現在のブロックの予測として、参照画像内の同位置ブロック（予測値と称される）が決定されてよい。同位置ブロックは、現在の画像内の現在のブロックと同じ位置で、参照画像内に配置されてよい。そのような予測は、静止画像領域、すなわち、１つの画像からもう１つへ動きがない画像領域に対して正確である。
【０００５】
エンコーダにおいて、動きを考慮に入れる予測値、すなわち、動き補償された予測値を取得するために、典型的には動き推定が使用される。現在のブロックは、動きベクトルによって示される位置の参照画像に配置されたブロックによって予測される。動きベクトルは、同位置ブロックの位置から現在のブロックの位置を指し示す（又はその逆も、符号の規約に応じて）。デコーダがエンコーダのように現在のブロックと同じ予測を決定可能とすべく、動きベクトルは、ビットストリームにおいて信号で伝えられてよい。ブロックのそれぞれについて動きベクトルをシグナリングすることによって生じたシグナリングオーバヘッドをさらに縮小すべく、動きベクトルそのものが推定されてもよい。動きベクトル推定は、空間的及び／又は時間的領域において、現在のブロックに隣接するブロックの動きベクトルに基づいて実行されてよい。
【０００６】
現在のブロックの予測は、１つの参照画像を用いて、又は２つ以上の参照画像から取得された予測に重みを付加することによって、演算されてよい。隣接画像は、現在の画像に類似する可能性が最も高いので、参照画像は、隣接画像でもよく、すなわち、表示順序において、現在の画像の直前又は直後の画像でもよい。しかしながら、一般的に、参照画像は、表示順序において、現在の画像に先行する又は後続する任意の画像でもよく、ビットストリームにおいて（デコード順序）現在の画像に先行する画像でもよい。これは、ビデオコンテンツにおいて、例えば、閉鎖された状態（オクルージョン）及び／又は非線形の動き場合に利点を提供することができる。参照画像は、ビットストリームにおいて信号で伝えられてよい。 
【０００７】
インター予測の特殊モードは、現在のブロックの予測の生成に２つの参照画像が使用される状態で、双方向予測と呼ばれる。具体的には、それぞれの２つの参照画像において決定された２つの予測は、現在のブロックの予測信号に組み合わされる。双方向予測は、単予測よりも、すなわち、単一の参照画像を使用するだけの予測よりも、より正確な現在のブロックの予測をもたらすことができる。より正確な予測は、現在のブロック及び予測のピクセル間の差をより小さくすることになり（すなわち、より小さい残差）、予測はより効率的にコード化されてよく、すなわち、より短いビットストリームに圧縮される。
【０００８】
より正確な動き推定を提供するために、参照画像の解像度は、例えば、ピクセル間の補間サンプルによって、上げられてよい。小数ピクセル補間は、最も近いピクセルの加重平均化によって実行できる。例えば、ハーフピクセル解像度の場合、双線形補間が使用できる。他の小数ピクセルは、例えば、予測されるピクセルに最も近いそれぞれのピクセル間の距離の逆数によって重みづけされた最も近いピクセルの平均として計算できる。
【０００９】
動きベクトルは、例えば、現在のブロックと、参照画像において動きベクトル候補によって指し示された対応する予測ブロックとの間の類似性を計算することによって推定できる。これは、複雑な演算タスクになり得る。複雑さを減らすべく、動きベクトル候補の数は、特定の探索空間への動きベクトル候補を制限することによって減少できる。探索空間は、例えば、現在の画像における現在のブロックの位置に対応する参照画像内の位置を囲む複数のピクセルの数及び／又は位置によって定義されてよい。代替として、動きベクトル候補は、隣接するブロックの動きベクトルの形成された動きベクトル候補のリストによって定義されてよい。
【００１０】
動きベクトルは、通常、少なくとも部分的に、エンコーダ側で決定され、コーディングされたビットストリームにおいて、デコーダに信号で伝えられる。しかしながら、動きベクトルもまたデコーダで導出できる。そのような場合において、現在のブロックは、デコーダで利用できず、現在のブロックと、参照画像において動きベクトル候補が指し示す任意のブロックとの間の類似性を計算するために使用できない。それゆえ、現在のブロックの代わりに、テンプレートが使用でき、既にデコードされたブロックのピクセルから構築できる。例えば、現在のブロックに隣接する既にデコードされたピクセルが用いられてよい。そのような動き推定は、シグナリングを低減することの利点を提供する：動きベクトルは、エンコーダ及びデコーダの両方で同様に導出され、従って、シグナリングは必要ない。一方、そのような動き推定の精度は、より低くてもよい。
【００１１】
精度及びシグナリングオーバヘッド間のトレードオフを提供するために、動きベクトル推定は、動きベクトルの導出と動きベクトルの改良との２つの段階に分割されてよい。例えば、動きベクトルの導出は、候補のリストからの動きベクトルの選択を含んでよい。選択された動きベクトルは、例えば、探索空間の範囲内の検索によって、さらに改良されてよい。探索空間における検索は、それぞれの動きベクトル候補のため、すなわち、動きベクトル候補が指し示すブロックの候補点のそれぞれのためのコスト関数の計算に基づく。
【００１２】
文書JVET-D0029：両側テンプレートマッチングに基づくデコーダ側の動きベクトルの改良、X. Chen, J. An, J. Zheng  （文書は、http://phenix.it-sudparis.eu/jvet/ siteで、見ることができる）は、整数のピクセル解像度において第１動きベクトルの改良が見つけられ、第１動きベクトル周りの探索空間におけるハーフピクセル解像度をともなう検索によってさらに改良される状態で、動きベクトルを示す。ここで、ピクセル解像度（例えば、整数又は半整数）は、探索空間の解像度、すなわち、プロセスに入力される非改良の動きベクトルに対する探索位置の変位を表現する。結果として、改良段階の検索座標は、必ずしも、画像平面上の実際のピクセル座標と一致しない。
【発明の概要】
【００１３】
上述の手法から出発して、本開示の目的は、コーディング効率の改善及び／又は複雑さを縮小するために、動きベクトル推定の効率をさらに増大することである。
【００１４】
これを達成するために、動きベクトルの改良用の探索空間を構築するためのスキームが提供され、探索空間は、第１探索空間及び第２探索空間を含む。位置の数及び／又は第２探索空間の位置は、コスト関数に基づいて導出される第１探索空間における２つの位置に従って決定される。 
【００１５】
具体的には、第１態様によれば、映像フレームの現在のブロックのインター予測において使用される動きベクトルを決定する装置が提供される。装置は、動きベクトルの推定値を取得するとともに、推定値に基づいて、複数の動きベクトル候補を備える第１探索空間を決定し、コスト関数に従って、第１探索空間における第１動きベクトル候補及び第２動きベクトル候補を選択し、第１動きベクトル候補及び第２動きベクトル候補に基づいて、１つ又は複数の動きベクトル候補を備える第２探索空間を決定するための探索空間決定ユニットを備える。装置は、第１探索空間及び第２探索空間の動きベクトル候補の中から、現在のブロックのための動きベクトルを選択する動きベクトル選択ユニットをさらに備える。
【００１６】
利点として、デコーダ側での動きベクトルの改良の処理においてテストされる動きベクトル候補の数は、画像品質及びビットレートに関して高品質コーディング性能を維持しながら減少してよい。
【００１７】
有利に、コスト関数は、予め定められたテンプレートに基づいており、動きベクトル候補のそれぞれに対して、予め定められたテンプレートと、それぞれの動きベクトル候補によって指し示された予測値との間の類似性のレベルを示す。従って、探索空間決定ユニットは、予め定められたテンプレートに最も類似する現在のブロックの予測値を指し示す第１探索空間における２つの動きベクトル候補を、第１動きベクトル候補及び第２動きベクトル候補として、選択するように構成される。
【００１８】
第１実施形態によれば、探索空間決定ユニットは、第１動きベクトル候補及び第２動きベクトル候補によって指し示された位置を接続する直線の方向に従って、言い換えれば、第１動きベクトル候補及び第２動きベクトル候補の差分ベクトルの方向に従って、第２探索空間のサイズ及び／又は位置を決定するように、さらに構成される。差分ベクトルは、第２動きベクトル候補から差し引かれた第１動きベクトル候補として、又はその逆も同様に、定義できる。
【００１９】
例えば、探索空間決定ユニットは、整数のピクセル解像度を有するために、第１探索空間を設定するように、さらに構成される。探索空間決定ユニットは、第２探索空間において、第１動きベクトル候補及び第２動きベクトル候補が指し示す位置を接続する直線の方向にある位置を指し示す１つ又は複数の動きベクトル候補を含むように構成され、第２探索空間は、小数のピクセル解像度を有する。言い換えれば、その直線の方向は、第１動きベクトル候補及び第２動きベクトル候補の差分ベクトルの方向である。
【００２０】
例として、第２探索空間の少なくとも一つの動きベクトル候補は、第１動きベクトル候補及び第２動きベクトル候補によって指し示された位置の間の位置を指し示す。
【００２１】
第２実施形態によれば、探索空間決定ユニットは、少なくとも二つの動きベクトル候補がそれぞれ指し示す少なくとも二つの位置を含む領域の位置を決定するように構成され、上記少なくとも二つの位置は、第２探索空間のピクセル解像度において隣接し、第１探索空間に属さない領域のこれらの位置として第２探索空間を決定するように構成される。
【００２２】
例えば、探索空間決定ユニットは、動きベクトルの上記推定値によって指し示された位置に対して、第１探索空間のピクセル解像度において隣接する位置に指し示される動きベクトル及び動きベクトル候補の推定値を含む第１探索空間を決定するように構成されてよい。
【００２３】
第３実施形態によれば、探索空間決定ユニットは、第１探索空間において特定された第１動きベクトル候補及び第２動きベクトル候補によって指し示された位置に対して第１探索空間のピクセル解像度において隣接し、動きベクトルの推定値によって指し示された位置とは異なる位置を指し示す動きベクトル候補を、第２探索空間の第１動きベクトル候補として決定するようにさらに構成される。
【００２４】
例えば、探索空間決定ユニットは、第２探索空間の更なる動きベクトル候補として、動きベクトルの推定値と第２探索空間の候補とを接続する直線上にほぼ位置する第２探索空間の解像度における位置を指し示す動きベクトル候補を選択するようにさらに構成され、第２探索空間のピクセル解像度は、第１探索空間のピクセル解像度より高い。
【００２５】
例として、第２探索空間の更なる動きベクトル候補は、第２探索空間の第１動きベクトル候補及び動きベクトルの推定値によって指し示された位置の間に配置された位置を指し示す。
【００２６】
第１態様の実施形態の全ての例として、第２探索空間は、第１探索空間より高い解像度を有する。
【００２７】
更なる例として、装置は、現在のブロックに隣接する少なくとも一つのブロックの動きベクトルを含む動きベクトルのリストから動きベクトルの推定値を決定する動きベクトル決定ユニットをさらに備える。
【００２８】
さらに、ビットストリームから複数の画像をデコードするためのビデオデコーダが提供される。ビデオデコーダは、ビットストリームから動きベクトルの推定値の指示を取得するためのビットストリームパーサーと、現在のブロックの動きベクトルが指し示す予測ブロックを決定するようにさらに構成され、第１態様の任意の実施形態及び実施例に係る装置を含むインター予測ユニットと、予測ブロックに基づいて、現在のブロックを再構築するための再構築ユニットとを備える。
【００２９】
また、複数の画像をビットストリームにコード化するためのビデオエンコーダが提供される。ビデオエンコーダは、現在のブロックの動きベクトルが指し示す予測ブロックを決定するようにさらに構成された第１態様の任意の実施形態及び実施例に係る装置を含むインター予測ユニットと、動きベクトルの推定値の指示をビットストリームに含めるためのビットストリームフォーマーと、予測ブロックに基づいて、現在のブロックを再構築し、メモリに再構築されたブロックを格納するための再構築ユニットを備える。
【００３０】
第２態様によれば、方法は、現在のブロックのインター予測において使用される動きベクトルを決定するために提供される。方法は、動きベクトルの推定値を取得する段階と、推定値に基づいて、複数の動きベクトル候補を備える第１探索空間を決定する段階と、コスト関数に従って、第１探索空間における第１動きベクトル候補及び第２動きベクトル候補を選択する段階と、第１動きベクトル候補及び第２動きベクトル候補に基づいて、１つ又は複数の動きベクトル候補を備える第２探索空間を決定する段階と、第１空間及び第２空間の動きベクトル候補の中から、現在のブロックのための動きベクトルを選択する段階とを備える。
【００３１】
有利に、コスト関数は、予め定められたテンプレートに基づいており、動きベクトル候補のそれぞれに対して、予め定められたテンプレートと、それぞれの動きベクトル候補によって指し示された予測値との間の類似性のレベルを示す。従って、第１動きベクトル候補及び第２動きベクトル候補を選択する段階は、予め定められたテンプレートに最も類似する現在のブロックの予測値を指し示す第１探索空間における２つの動きベクトル候補を選択する段階を含む。
【００３２】
例示的な第１実施形態では、第２探索空間を決定する段階において、第２探索空間のサイズ及び／又は位置は、第１動きベクトル候補及び第２動きベクトル候補が指し示す位置を接続する直線の方向に従って決定される。
【００３３】
例として、複数の動きベクトル候補を含む第１探索空間を決定する段階において、第１探索空間は、整数のピクセル解像度を有する。第２探索空間を決定する段階において、第２探索空間は、第１動きベクトル候補及び第２動きベクトル候補が指し示す位置を接続する直線の方向にある位置を指し示す１つ又は複数の動きベクトル候補として決定され、第２探索空間は、小数のピクセル解像度を有する。
【００３４】
例えば、第２探索空間の少なくとも一つの動きベクトル候補は、第１動きベクトル候補及び第２動きベクトル候補によって指し示された位置の間の位置を指し示す。
【００３５】
例示的な第２実施形態によれば、第２探索空間を決定する段階において、少なくとも二つの動きベクトル候補がそれぞれ指し示す少なくとも二つの位置を含む領域の位置が決定され、上記少なくとも二つの位置は、第２探索空間のピクセル解像度において隣接し、第２探索空間は、第１探索空間に属さない領域のこれらの位置として決定される。
【００３６】
例として、第１探索空間を決定する段階において、第１探索空間は、動きベクトルの上記推定値によって指し示された位置に対して、第１探索空間のピクセル解像度において隣接する位置を指し示す動きベクトル及び動きベクトル候補の推定値を含む。
【００３７】
例示的な第３実施形態によれば、第２探索空間を決定する段階において、第２探索空間の第１動きベクトル候補として、動きベクトル候補は、第１探索空間において特定された第１動きベクトル候補及び第２動きベクトル候補によって指し示された位置に対して第１探索空間のピクセル解像度において隣接し、動きベクトルの推定値によって指し示された位置とは異なる位置を指し示すように決定される。
【００３８】
例えば、第２探索空間の更なる少なくとも１つの動きベクトル候補として、動きベクトル候補は、動きベクトルの推定値と第２探索空間の候補とを接続する直線上にほぼ位置する第２探索空間の解像度における位置を指し示すように決定される。ここに、第２探索空間のピクセル解像度は、第１探索空間のピクセル解像度より高い。
【００３９】
例として、第２探索空間の上記更なる動きベクトル候補は、第２探索空間の第１動きベクトル候補及び動きベクトルの推定値によって指し示された位置の間に配置された位置を指し示す。
【００４０】
第２態様の実施形態の全ての例として、第２探索空間は、第１探索空間より高い解像度を有する。
【００４１】
更なる例として、動きベクトルの推定値を取得する段階は、現在のブロックに隣接する少なくとも一つのブロックの動きベクトルを含む動きベクトルのリストから動きベクトルの推定値を決定することによって実行される。
【図面の簡単な説明】
【００４２】
以下の例示的な実施形態では、添付の図面を参照してより詳細に説明される。 
【図１】ビデオエンコーダの構成例を示すブロック図である。
【図２】ビデオデコーダの構成例を示すブロック図である。
【図３】動きベクトルを決定するための装置の構成例を示すブロック図である。
【図４】現在のブロック及び例示的な探索空間構成の概略図である。
【図５】例示的な第１実施形態に係る探索空間構成の概略図である。
【図６】例示的な第１実施形態に係る探索空間構成の概略図である。
【図７】例示的な第１実施形態に係る探索空間構成の概略図である。
【図８】例示的な第１実施形態に係る探索空間構成の概略図である。
【図９】例示的な第１実施形態に係る第２探索空間の決定を示す概略図である。
【図１０】第１実施形態に係る更なる探索空間構成の概略図である。
【図１１】第１実施形態に係る更なる探索空間構成の概略図である。
【図１２】第２実施形態に係る現在のブロック及び例示的な探索空間構成の概略図である。
【図１３】第２実施形態に係る現在のブロック及び例示的な探索空間構成の概略図である。
【図１４】第３実施形態に係る探索空間の決定を示す概略図である。
【図１５】第３実施形態に係る探索空間決定ユニットのブロック図である。
【図１６】異なる実施形態の組み合わせに係る探索空間構成の概略図である。
【図１７】異なる実施形態を組み合わせることによる探索空間の例示的な決定を示す概略図である。
【図１８】動きベクトルの改良のための方法を示すフローチャートである。
【図１９】探索空間位置に関するコスト計算のための方法を示すフローチャートである。
【発明を実施するための形態】
【００４３】
本開示は、動き補償のための探索空間の効率的な決定に関し、動きベクトルの改良のために、特に有利である。探索空間の決定は、ビデオのコード化及びデコードの間に適用される動き推定値において使用されてよい。以下において、本開示の探索空間の構築を使用する動き推定を実装することができる例示的なエンコーダ及びデコーダが説明される。
【００４４】
図１は、ビデオストリームのフレーム又は画像の入力ブロックを受信するための入力及びコード化済みビデオビットストリームを提供するための出力を備えるエンコーダ１００を示す。本開示において「フレーム」との用語は、画像と同義語として使用される。しかしながら、本開示は、インターレースが適用される場合のフィールドにも適用可能であることに留意されたい。一般的に、画像は、ｎピクセルのｍ倍が含まれる。これらは、画像サンプルに対応し、それぞれ１つ又は複数の色成分を備えることができる。簡略化のために、以下の説明では、輝度のサンプルを意味するピクセルに言及する。しかしながら、本発明の動きベクトル検索は、クロミナンスを含む任意の色成分又はＲＧＢ又は同様のもののような色空間の成分に適用できることに留意されたい。一方、一つの成分のみに対する動きベクトル推定を実行すること、及びより多くの（又は全ての）成分に対して決定された動きベクトルに適用することは、有益であり得る。 
【００４５】
コーディングされることになっている入力ブロックは、必ずしも同一サイズを有していない。１つの画像は、異なるサイズのブロックを含んでよく、異なる画像のブロックラスターもまた異なっていてもよい。
【００４６】
エンコーダ１００は、ビデオストリームに対して、予測、変換、量子化、及びエントロピー符号化を適用するように構成される。変換、量子化、及びエントロピー符号化は、出力としてコード化済みビデオビットストリームを生成するために、それぞれ、変換ユニット１０１、量子化ユニット１０２、及びエントロピエンコードユニット１０３によって実行される。
【００４７】
ビデオストリームは、複数のフレームを含んでよい。それぞれのフレームは、イントラかそれともインターコーディングされたブロックに分割される。例えば、ビデオストリームの第１フレームのブロックは、イントラ予測ユニット１０９を用いてイントラコーディングされる。他のフレームから独立してデコードされ得るように、イントラフレームは、そのフレームのみからの情報を使用してコーディングされる。従って、イントラフレームは、例えば、ランダムアクセスのために、ビットストリームにおいてエントリポイントを提供することができる。ビデオストリームの他のフレームのブロックは、インター予測ユニット１１０を用いてインターコーディングされてよく、インターコーディングされたフレームのそれぞれのブロックは、もう１つのフレーム（参照フレーム）、例えば、これまでにコーディングされたフレームにおいて、ブロックから予測される。モード選択ユニット１０８は、フレームのブロックは、イントラ予測か、又はインター予測か、すなわち、イントラ予測ユニット１０９か、又はインター予測ユニット１１０かによって処理されるかを選択するように構成される。また、モード選択ユニット１０８は、イントラ又はインター予測のパラメータを制御する。画像情報のリフレッシュを可能にするために、インターコーディングされたフレームは、インターコーディングされたブロックだけでなく、１つ又は複数のイントラコーディングされたブロックもまた備えることができる。対照的に、イントラフレームは、イントラコーディングされ、インターコーディングされていないブロックのみを含む。イントラフレームは、デコードのためのエントリポイント、すなわち、デコーダが先行するフレームからの情報を使用することなくデコードを開始できる位置を提供するために、ビデオシーケンスに挿入されてよい（例えば、定期的に、特定の複数のインターフレームの後のそれぞれの時間に）。
【００４８】
イントラ予測ユニット１０９は、ブロック予測ユニットである。空間的又は時間的予測を実行するために、コーディングされたブロックは、逆量子化ユニット１０４及び逆変換ユニット１０５によってさらに処理され得る。ブロックの再構築後、ループフィルタリングユニット１０６は、デコードされた画像の品質をさらに改善するように適用され得る。フィルタリングブロックは、そのとき、参照フレームを形成し、そのとき、参照フレームは、フレームバッファ１０７に記憶される。エンコーダ側でのそのようなデコードループ（デコーダ）は、デコーダ側で再構築された参照画像と同一である有益な参照フレームの生成を提供する。従って、エンコーダ及びデコーダ側は、対応する方式で動作する。ここで、「再構築」との用語は、デコードされた残差ブロックを予測ブロックに加えることによって、再構築されたブロックを取得することを言う。
【００４９】
インター予測ユニット１１０は、入力として、インターコーディングされる現在のフレーム又は画像のブロック、及び１つ又は複数の参照フレーム又は画像を、フレームバッファ１０７から受信する。動き推定及び動き補償は、インター予測ユニット１１０によって実行される。動き推定は、例えば、コスト関数に基づいて、動きベクトル及び参照フレームを取得するために使用される。次に、動き補償は、参照フレームについての参照ブロックの現在のフレームへの変換に関して、すなわち、動きベクトルによって、現在のフレームについての現在のブロックを記述する。インター予測ユニット１１０は、予測ブロックがコスト関数を最小化するように、１つ又は複数の参照フレーム内のブロック候補のセット（すなわち、予測値候補）の中から、現在のブロックのための予測ブロック（すなわち、予測値）を選択する。言い換えれば、コスト関数が最小であるブロック候補は、予測ブロックとして、現在のブロックのために使用される。
【００５０】
例えば、コスト関数は、現在のブロックとブロック候補との差の量、すなわち、ブロック候補に関して現在のブロックの残差の量でもよい。例えば、コスト関数は、現在のブロックの全てのピクセル（サンプル）と、参照画像候補内のブロック候補の全てピクセルとの間の絶対差の合計（ＳＡＤ）でもよい。しかしながら、一般的に、任意の類似性基準は、平均二乗誤差（ＭＳＥ）又は構造的類似性基準（ＳＳＩＭ）のように、使用できる。
【００５１】
しかしながら、コスト関数は、そのようなインターブロック、及び／又はそのようなコーディングに起因する歪を、コーディングするために必要なビット数でもよい。従って、レート歪み最適化手順は、動きベクトルの選択、及び／又は、ブロックに対してインター予測又はイントラ予測のどちらを使用するか、どの設定を使用するかなどの一般的にエンコーディングパラメータを決定するために使用されてよい。
【００５２】
イントラ予測ユニット１０９は、入力として、イントラコーディングされる現在のフレーム又は画像のブロック、及び現在のフレームの既に再構築されたエリアから１又はいくつかの参照サンプルを受信する。次に、イントラ予測は、現在のフレームの参照サンプルの関数に関して、現在のフレームの現在のブロックのピクセルを記述する。イントラ予測ユニット１０９は、現在のブロックのために予測ブロックを出力し、上記の予測ブロックは、コーディングされる現在のブロックと、その予測ブロックとの差を有利に最小化し、すなわち、このことは、残差ブロックを最小化する。残差ブロックの最小化は、例えば、レート歪み最適化手順をベースとすることができる。具体的には、予測ブロックは、参照サンプルの方向の補間として取得される。その方向は、レート歪み最適化によって、及び／又はインター予測に関連して、上記のように類似性の量を計算することによって、決定されてもよい。 
【００５３】
現在のブロックと、その予測、すなわち、残差ブロックとの間の差は、その後、変換ユニット１０１によって変換される。変換係数は、量子化ユニット１０２によって量子化され、エントロピエンコードユニット１０３によって、エントロピーコーディングされる。従って、生成されたコード化されたビデオビットストリームは、イントラコーディングされたブロック及びインターコーディングされたブロック対応するシグナリング（モード指示、動きベクトルの指示、及び／又はイントラ予測方向など）を備える。変換ユニット１０１は、離散フーリエ変換（ＤＦＴ）又は離散コサイン変換（ＤＣＴ）などの線形変換を適用することができる。そのような空間周波数領域への変換は、結果として得られる係数が、より低周波数において典型的により高い値を有するという利点を提供する。従って、効果的な係数スキャニング（ジグザグなど）及び量子化の後、結果となる値のシーケンスは、最初と最後にゼロの連続を伴って、通常はいくつかのより大きい値を有する。これは、さらに効率的なコーディングを可能にする。量子化ユニット１０２は、係数値の解像度を低減することによって、不可逆の圧縮を実行する。次に、エントロピーコーディングユニット１０３は、２進法のコードワードを係数値に割り当てる。コードワードは、コード化されたビットストリームと呼ばれるビットストリームに書き込まれる。また、エントロピーコーダーは、シグナリング情報をコーディングする（図１において不図示）。
【００５４】
図２は、ビデオデコーダ２００の例を示す。ビデオデコーダ２００は、具体的には、参照画像バッファ２０７、及びブロック予測ユニットであるイントラ予測ユニット２０９を備える。参照画像バッファ２０７は、コード化済みビデオビットストリームのコード化済みビデオビットストリームから再構築された少なくとも一つの参照フレームを格納するように構成される。イントラ予測ユニット２０９は、デコードされるブロックの推定値である予測ブロックを生成するように構成される。イントラ予測ユニット２０９は、参照画像バッファ２０７から取得された参照サンプルに基づいてこの予測を生成するように構成される。 
【００５５】
デコーダ２００は、ビデオエンコーダ１００によって生成されたコード化済みビデオビットストリームをデコードするように構成され、好ましくは、デコーダ２００及びエンコーダ１００の両方が、コード化／デコードされるそれぞれのブロックのために同一の予測を生成する。参照画像バッファ２０７及びイントラ予測ユニット２０９の機能は、図１の参照画像バッファ１０７及びイントラ予測ユニット１０９の機能に類似する。
【００５６】
ビデオデコーダ２００は、同様のビデオエンコーダ１００にも存在するようなユニット、例えば、逆量子化ユニット２０４、逆変換ユニット２０５、及びループフィルタリングユニット２０６をさらに備え、これらは、それぞれ、ビデオコーダー１００の逆量子化ユニット１０４、逆変換ユニット１０５、及びループフィルタリングユニット１０６に対応する。
【００５７】
エントロピーデコーディングユニット２０３は、量子化された残差変換係数及びシグナリング情報を取得するために、受信したコード化済みビデオビットストリームをデコードするように構成される。量子化された残差変換係数は、逆量子化ユニット２０４及び逆変換ユニット２０５に供給され、残差ブロックを生成する。残差ブロックは、予測ブロックに加えられ、その結果である合計は、デコードされたビデオブロックを取得するために、ループフィルタリングユニット２０６に供給される。デコードされたビデオのフレームは、参照画像バッファ２０７に記憶されることができ、インター予測のための参照フレームとして機能する。概して、図１および図２のイントラ予測ユニット１０９および２０９は、既にコード化済みのエリアから参照サンプルを使用して、コード化される必要がある、又はデコードされる必要があるブロックのために予測信号を生成することができる。
【００５８】
エントロピーデコーディングユニット２０３は、その入力として、コード化済みビットストリームを受信する。ビットストリームは、まず、解析されることができ、すなわち、シグナリングパラメータ及び残差がビットストリームから抽出される。ビットストリームの構文及び意味は、エンコーダ及びデコーダが相互利用可能な方式で機能でき得るように、基準によって定義され得る。上記の背景技術の欄で説明されているように、コード化済みビットストリームは、予測残差に加えてさらに情報を含む。動き補償された予測の場合、動きベクトル表示は、また、ビットストリームにおいてコーディングされ、デコーダでビットストリームから解析される。動きベクトル表示は、動きベクトルが提供される範囲内の参照画像を用いて、及び、動きベクトル座標を用いて、与えられることができる。この例では、動きベクトル座標は、参照画像内のｘ及びｙ座標であり、座標（０，０）は、現在のフレームで処理されている現在のブロックの位置に対応する参照フレーム内の位置であると仮定して、動きベクトルが示すポイントを定義する。しかしながら、動きベクトル表示は、直接、座標を伝える必要はない。一般的に、動きベクトルの任意の識別は、ポインタ（インデックス）などを、動きベクトル候補のリスト、又はブロックのインター予測を識別することが可能な任意の他の識別子に適用可能である。
【００５９】
効率的に参照画像をコーディングするために、Ｈ．２６５コーダ・デコーター（ＩＴＵ−Ｔ、Ｈ２６５、シリーズＨ：オーディオビジュアル及びマルチメディアシステム：高効率ビデオコーディング）は、参照画像のリストを提供する。リストのそれぞれのエントリは、特定の参照フレームを示す。言い換えれば、リストのそれぞれのインデックス（すなわち、エントリ数）には、それぞれの参照フレームが割り当てられる。ビットストリームは、それぞれインターフレームのために、それぞれリストインデックスを含み、それゆえ、そのインターフレームを再構築するための特定の参照フレームを識別する。リストは、基準において定義され、又は、ビデオあるいは多数のフレームのセットの先頭で信号で伝えられ得る。Ｈ．２６５では、Ｌ０及びＬ１と呼ばれ、定義された参照画像の２つのリストがあることに留意されたい。その後、参照画像は、リスト（Ｌ０又はＬ１）を示すこと、及び所望の参照画像に関連するそのリストにおいてインデックスを示すことによって、ビットストリームにおいて信号で伝えられる。２つ以上のリストの提供は、より良好な圧縮のために利点を有することができる。例えば、Ｌ１が双方向にインター予測されたスライスのためにのみ用いられ得る間に、Ｌ０は、一方向にインター予測されたスライス及び双方向にインター予測されたスライスの両方のために用いられ得る。しかしながら、一般的に、本開示は、Ｌ０及びＬ１リストの任意のコンテンツに限定されるものではない。 
【００６０】
動きベクトルは、（参照画像において）動きベクトルが指し示すブロックの座標によって、直接、信号で伝えられてよい。代替として、Ｈ．２６５において規定されるように、動きベクトル候補のリストが構築されてよく、リストによって、特定の動きベクトルに関連されたインデックスが送信されることができる。
【００６１】
現在のブロックの動きベクトルは、現在の画像において、又は、より先にコーディングされた画像において、隣接するブロックの動きベクトルと、しばしば、相互に関連がある。これは、隣接するブロックは、同様の動きを有する同一の移動オブジェクトに対応する可能性が高く、オブジェクトの動きは、時間の経過とともに突然変化する可能性が低いためである。したがって、１つ又は複数の空間的に又は時間的に隣接するブロックの動きベクトルを用いて、現在のブロックの動きベクトルのために、予測値（動きベクトル予測値として称される、ＭＶＰ）を定義することは、信号で伝えられる動きベクトル差のサイズを減少させる。ＭＶＰは、空間的に隣接するブロックから、又は同位置画像１において時間的に隣接するブロックから、既にデコード済の動きベクトルから導出される得る。Ｈ．２６４／ＡＶＣでは、これは、空間的に隣接する３つの動きベクトルの中央値に成分的にすることによって、行われる。この手法を用いると、予測値のシグナリングは必要ない。同位置画像からの時間的ＭＶＰｓは、現在、Ｈ．２６４／ＡＶＣのいわゆる時間的ダイレクトモードでのみ考慮される。Ｈ．２６４／ＡＶＣダイレクトモードは、また、動きベクトル以外の動きデータを導出するために使用される。したがって、それらは、ＨＥＶＣにおいて、ブロックマージコンセプトに、より関連する。ＨＥＶＣにおいて、ＭＶＰの暗示的導出の手法は、ＭＶＰのリストから動きベクトルの導出のためにどのＭＶＰが用いられるかを明確に伝える、動きベクトルの競争として知られる技術によって置き換えられた。ＨＥＶＣ内の四分木ブロック構造コーディング変数は、潜在的ＭＶＰ候補としての動きベクトルと共にいくつかの隣接するブロックを有する１つのブロックをもたらし得る。例として左に隣接するものをとると、最も悪い場合、６４×６４ルマ予測ブロックは、６４×６４ルマ予測ブロックがさらに分割されず、左のものが最大深さに分割される場合、左に対して１６  ４×４ルマ予測ブロックを有することができる。
【００６２】
アドバンスト動きベクトル予測（ＡＭＶＰ）は、そのようなフレキシブルブロック構造を構成するために動きベクトルの競争を修正することを導入した。ＨＥＶＣの開発の間、初期のＡＭＶＰ設計は、コーディング効率とフレンドリ設計の実装との間の好適なトレードオフを提供するために大きく簡略化された。初期のＡＭＶＰの設計は、予測値の３つの異なるクラスから５つのＭＶＰを含んだ。これらは、空間隣接からの３つの動きベクトル、３つの空間予測値の中央値、及び同位置にある時間的に隣接するブロックからのスケーリングされた動きベクトルである。さらに、予測値のリストは、第１位置に最も起こりそうな動き予測値を置くことを再度命令することによって、及び最小のシグナリングオーバヘッドを保証するために余剰な候補を除去することによって、修正された。ＡＭＶＰ候補リスト構築の最終設計は、以下の２つのＭＶＰ候補を含む。ａ）５つの空間隣接するブロックから導出された空間的候補ＭＶＰを２つまで、ｂ）両方の空間的候補ＭＶＰが利用できない、又はそれらが同一である場合、２つの時間的、同位置ブロックから導出された時間的ＭＶＰ候補を１つ、及びｃ）空間的、時間的、又は両方の候補が利用できない場合、動きベクトルはゼロである。動きベクトルの決定に関する詳細は、ｖ．  Ｓｚｅ  ｅｔ  ａｌ  （Ｅｄ．）による本「高効率ビデオコーディング（ＨＥＶＣ）：アルゴリズム及びアーキテクチャ、Ｓｐｒｉｎｇｅｒ、２０１４」、特に、第５章で見つけることができ、参照により本明細書に組み込まれる。
【００６３】
以下で詳細に説明されるように、エンコーダ側で導出されて、ビットストリームにおいてに提供される動きベクトルは、さらに改良され得る。従って、動きベクトル推定は、シグナリングオーバヘッドでさらに増大することなく改良される。動きベクトルの改良は、エンコーダからの支援なしで、デコーダで実行され得る。エンコーダにおけるデコーダループは、対応する参照画像を取得するために、同一の改良を利用できる。改良は、テンプレートを決定すること、探索空間を決定すること、及び探索空間において、テンプレートに最も一致する参照画像の部分の位置を見つけることによって、実行され得る。最も一致する部分の位置は、現在のブロック、すなわち、再構築される現在のブロックの予測値を取得すために、その後、使用される最良の動きベクトルを決定する。
【００６４】
動作中、図１のビデオエンコーダ１００に実装され得るインター予測ユニット１１０の回路は、現在のブロックのインター予測のために動きベクトルを取得すべく、動き推定を実行する（図３参照）。また、同様の予測は、図２のビデオデコーダ２００のインター予測ユニット２１０によって、実行することができ、図３及び付随する説明は、同様に適用される。
【００６５】
完全な動きベクトルの第１推定値又は近似とみなすことができる初期動きベクトルＭＶ０は、インター予測ユニット１１０によって取得される。例えば、ＭＶ０は、動きベクトル候補のリストから選択することができる。リストは、現在のブロックに隣接する少なくとも一つのブロックの動きベクトルを含むことができる。代替として、ＭＶ０は、エンコーダ側で一致するブロックによって取得され、ビットストリームの範囲内でデコーダ側に信号で伝えられてよい。これに応じて、デコーダ側で、インター予測ユニット２１０は、ビットストリームから初期動きベクトルＭＶ０を取得できる。例えば、候補のリストへのインデックスは、ビットストリームから抽出され、そのインデックスによって特定された動きベクトル候補は、初期動きベクトルＭＶ０としてインター予測ユニットに提供される。代替として、ＭＶ０の座標は、ビットストリームから直接抽出される。しかしながら、本開示は、初期動きベクトルＭＶ０を取得する何か特定の方法に限定されるものではない。一般的に、ＭＶ０は、任意の方式、例えば、エンコーダ及びデコーダで同様にテンプレートマッチングによって、決定されてよい。更なる代替として、動きベクトルは、空間的又は時間的領域において、現在のブロックに対して隣接するブロックの動きベクトルの関数として予測され得る。 
【００６６】
初期動きベクトルＭＶ０は、現在のブロックのインター予測において使用される最終動きベクトルＭＶ０''の初期推定値である。それは、最終動きベクトルＭＶ０''が出力されることの最後で、改良プロセスのための入力を構成する。改良プロセスは、探索空間を決定する段階、及び探索空間から最終動きベクトルを選択する段階を含む。
【００６７】
概して、（例えば、インター予測ユニット１１０または２１０の探索空間決定ユニット３１０によって実行される）探索空間の構築は、構築される探索空間の部分のそれぞれにおいて、２つの段階を含む。動きベクトル選択ユニット３４０（また、インター予測ユニット１１０及び／又は２１０の一部）は、その後、マッチングコストに従って、（探索空間位置の座標に対応する）動きベクトルＭＶ０''を選択する。探索空間のある動きベクトル候補のために、おそらく、それぞれの段階で決定されたそれぞれの探索空間部分の全ての動きベクトル候補のために、探索空間の構築の間の一部として、コストは前々から計算されてもよいことを留意されたい。
【００６８】
探索空間の構築は、第１探索空間（一部の）の構築の第１段階３０１を含む。第１段階３０１で決定された第１探索空間の位置のから、少なくとも２つの候補位置が選択され３０２、どちらの候補位置が第２段階３０３でチェックされるかを決定するために使用される。
【００６９】
言い換えれば、初期動きベクトルＭＶ０に基づいて、複数の動きベクトル候補を含む第１探索空間が決定される３０１。第１探索空間では、第１動きベクトル候補及び第２動きベクトル候補は、コスト関数に従って特定される３０２。第１動きベクトル候補及び第２動きベクトル候補に基づいて、第２探索空間は、１つ又は複数の動きベクトル候補を含むように決定される３０３。第１探索空間及び第２探索空間の両方動きベクトル候補の中から、現在のブロックのための動きベクトルＭＶ０''は、動きベクトル選択ユニット３４０によって選択される。具体的には、第２探索空間が評価された後、コスト関数を最小化する候補が見つかり、この候補は、インター予測において適用される最終動きベクトルＭＶ０''として、選択される。第１探索空間は、参照画像内の位置の第１サブセット、すなわち、第１探索空間の動きベクトル候補によって指し示されたサブセットの位置に相当する。同様に、第２探索空間は、参照画像内の位置の第２サブセット、すなわち、第２探索空間の動きベクトル候補によって指し示されたの位置のサブセットに相当する。 
【００７０】
動きベクトルの改良は、参照画像内でのサブセットの位置、及び、第１探索空間及び第２探索空間の位置を含む探索空間において、実行される。その位置は、それぞれの動きベクトル候補が指し示す位置、すなわち、評価されるテンプレートと一致する位置である。参照画像は、整数又は小数解像度において、利用可能でもよい。参照画像解像度に関係なく、探索空間又はその一部は、参照画像からより低い又はより高い独自の解像度を有してもよい。より高い解像度は、小数ピクセルを取得するために小数ピクセル補間を実行することによって実現され得る。
【００７１】
例えば、初期動きベクトルＭＶ０は、フルピクセル位置とも称される整数のピクセル位置を指し示すことができる。代替として、ＭＶ０は、小数ピクセル位置、例えば、ハーフピクセル位置又は１／４ピクセル位置を指し示すことができる。ここで、残りの説明において同様であり、「ハーフピクセル位置」（及び、それぞれ、「１／４ピクセル位置」）は、隣接する２つのフルピクセル位置間（すなわち、フルピクセル解像度において隣接するピクセル）の直線上の位置を言い、小数ピクセル位置は、隣接する２つフルピクセル位置間の距離の半分（または、それぞれ、１／４）である次の全ピクセル位置までの距離を有する。
【００７２】
本開示の異なる実施形態では、ＭＶ０がフルピクセル又はハーフピクセル位置を指し示しているかどうかに関わらず、第１探索空間及び第２探索空間は、解像度において、同じ解像度かそれとも異なる解像度かを有することができる。例えば、第２探索空間は、第１探索空間より高い解像度を有することができる。それゆえ、第２探索空間は、第１探索空間の改良として見なすことができる。
【００７３】
有利には、第１探索空間は、フルピクセル解像度を有する。そのとき、もし、第２探索空間の解像度が第１探索空間の解像度と異なるならば、第２探索空間の解像度は、ハーフピクセル解像度などの小数のピクセル解像度でもよい。探索空間の解像度は、参照画像の解像度と異なっていともよいことに留意されたい。例えば、初期動きベクトルは、参照画像内のハーフピクセルを指し示すことができる。それにもかかわらず、第１探索空間は、互いからの少なくとも整数ピクセルの距離内にある複数の位置のみを含むことができる。それにもかかわらず、これらの位置は、参照画像のピクセルのサブピクセル上に全て配置されてもよい。
【００７４】
本開示の様々な実施形態による探索空間の異なる構成が示されている残りの図と同様に、図４では、フルピクセル解像度は、網掛けされた（フル）ドットを用いて示されているが、それに対して、小数ピクセル位置は網掛けなしの（空の）ドットとして図示されている。コーディングされ又はデコードされるビデオ内の画像のピクセルは、正方形パターンに配置されてもよい。しかしながら、一般に、それらは、必ずしも正方形パターンではない一般的な矩形ピクセルパターンを有することができる。概して、本開示は、何か特定のピクセルパターンに限定されるものではない。また、ピクセルは、矩形ではないパターンに配置されてもよい。一実施形態では、現在のブロックのための動きベクトル候補は、現在の画像内（座標（０，０）を有すると仮定され）の現在のブロックの左上のピクセルから、（図４で図示されるように）参照画像での予測ブロック候補のそれぞれの左上のピクセルを指し示す。それゆえ、予測ブロック候補の左上のピクセルは、参照画像内の探索空間を表す。この実施形態ではブロックの左上のピクセルは、ブロックの位置として、利用される。しかしながら、ブロックの任意の他のピクセルは、ブロックの位置として利用でき、同じ位置規定が全てのブロックに適用されることが理解される。例えば、動きベクトルは、現在のブロックの中心ピクセルからそれぞれのブロック候補の中心ピクセルまで、連続するように同等に定義されてもよい。
【００７５】
例として（再び図４を参照）、第１探索空間は、９個の動きベクトル候補、すなわち、フルピクセル解像度において、その４つの最も近い隣接位置、及びその４つの２番目に最も近い隣接位置と同様に動きベクトルの初期推定値ＭＶ０を含む。図４における第１探索空間のコンスタレーション（類似のコンスタレーション）は、垂直及び水平においてピクセル間の距離が同一であるという意味である「正方形」コンスタレーションである。本開示の実施形態を説明する場合に示されるように、様々なサイズ及び形状を有するコンスタレーションは、第１探索空間のために使用され得る。
【００７６】
上記で説明したように、動きベクトルの改良スキームは、追加のコントロールシグナリングなしで、エンコーダ及びデコーダで同じ方法で実行され得る。これは、例えば、デコーダ側と同様にエンコーダ側でテンプレートを提供することをによって、実現され得る。例えば、テンプレートは、既にコード化済み／デコード済みピクセルから決定され得る（例えば、上で述べた文書JVET-D0029で説明した技術の一つを使用して）。そのようなテンプレートの例は、現在のブロック及び隣接する現在のブロックの前に、デコードされた１つ又は複数のブロックのピクセルでもよい。より具体的には、現在のブロックについての動きベクトルの改良のためのテンプレートは、左境界で隣接するブロックのＮピクセル及び上側の境界で隣接するブロックのＭピクセルとなるように決定されてよく、通常、ブロックのデコードは、左から右へ、上から下へ、実行されることが仮定される。Ｍ及びＮは、１より大きい整数である。 しかしながら、テンプレートは、それとは別に決定されてもよく、現在のブロックとの境界に直接的に隣接するブロックのピクセル、隣接するブロックの他のピクセル、及び／又は１つ又は複数の隣接するブロックの境界全体から離れて含んでよい。
【００７７】
実際には、動きベクトルの改良は、デコーダにほとんど関係する。情報は、特定の動きベクトルの改良に関係するビットストリームにおいて、コード化されないので、エンコード側は、改良された動きベクトルを考慮に入れる参照画像を作り出すために、デコードループのみに改良を適用する。 
【００７８】
類似性は、例えば、テンプレートと、動きベクトル候補によって指し示された位置でのテンプレートに対応する参照画像エリアとの絶対差の合計でもよいコスト関数によって測定することができる。全ての動きベクトル候補についての絶対差の合計（ＳＡＤ）の計算後、最少ＳＡＤを有する候補が選択される。しかしながら、ＳＡＤは、単に一例であり、二乗差の合計又は相関など同様の任意の他の類似性基準が適用され得ることに留意されたい。
【００７９】
第１動きベクトル候補及び第２動きベクトル候補は、予め定められたテンプレートに最も類似する（及び２番目に最も類似する、それぞれ）現在のブロックの予測値の位置について、それぞれ言及する。テンプレートは、例えば、ＪＶＥＴ−Ｄ００２９で説明された技術の一つを使用して、先行する段階で生成されてもよい。
【００８０】
改良による動きベクトルの決定についての方法は、図１８に関して以下に説明される。方法は、Ｓ１８０１でスタートする。Ｓ１８０２において、動きベクトルの初期推定値ＭＶ０が取得され、第１探索空間は、動きベクトルの初期推定値に基づいて設定される。第１探索空間は、ＭＶ０に関連した位置を囲む位置を指し示す動きベクトル候補を含む。第１探索空間の動きベクトル候補に関連するコストがＳ１８０３で計算され、計算されたコストに従って、第１動きベクトル候補及び第２動きベクトル候補、Ｐ１及びＰ２が選択される。Ｐ１及びＰ２従って、１つ又は複数の動きベクトル候補を含む第２探索空間が段階Ｓ１８０４で設定される。第２探索空間は、２つの最も有望な位置に基づいて設定されるので、かなり小さくする（それゆえ、すぐに検索される）ことができる。具体的には、２つの（又は２より多くの）位置を考慮することによって、コスト（すなわち、コスト関数の値）が減少する（又はおそらく減少する）トレンド方向が決定されてよく、第２探索空間は、トレンド方向において設定されてよく、例えば、初期動きベクトルにのみ基づいて、又は単一の最良位置に基づいて、第２探索空間を設定するのに比べて、より小さいサイズを有してよい。さらに、一般に、本開示は、２つの最良の動きベクトル候補（それらが指し示すそれぞれの位置）を考慮に入れることに限定されるものではないことにさらに留意されたい。一般的に、コスト関数のトレンドは、２より多くの最良の位置を考慮に入れることによって、より高精度に決定され得る。そのような場合において、コスト関数が減少する方向は、第１探索空間の位置のうち最低コストと考慮される２又はそれより多くの位置に基づいて決定される。第２探索空間は、そのとき、トレンドの方向における位置に設定される。従って、探索空間、及び、特に、第２探索空間の位置の数は、最も有望の位置を依然としてチェックしながら、低く維持され得る。 
【００８１】
第２探索空間の動きベクトル候補に関連するコストは、Ｓ１８０５で計算される。第１探索空間及び第２探索空間の動きベクトル候補から、最良の動きベクトル候補、すなわち、最低コストに関連する動きベクトル候補が選択される（Ｓ１８０６において）。最良の動きベクトル候補の選択後、動きベクトルの改良は、終了する（Ｓ１８０７において）。本開示の異なる実施形態は、とりわけ、以下に説明されるように、第１探索空間及び第２探索空間が決定される方法において異なってよい。
【００８２】
例示的な第１実施形態
【００８３】
例示的な第１実施形態によれば（図４参照）、コスト関数は、第１探索空間の動きベクトル候補のそれぞれについて評価される。言い換えれば、これらの動きベクトルのそれぞれについて、コスト関数の値であるそれぞれのコストが計算され、又は推定され、あるいは決定される。この評価に従って、最小コストをともなう候補及び２番目に最小なコストをともなう候補が選択される。図４の例では、初期動きベクトルＭＶ０は、位置４０５を指し示す。第１探索空間内の位置４０９は、最低コストを有し、それゆえ、第１動きベクトル候補ＭＶ０'として選択される。ＭＶ０の右に隣接する４０６は、２番目に最小なコストを有し、それゆえ、第２動きベクトル候補ＭＶ０'ｓｅｃｏｎｄＢｅｓｔとして選択される。ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、第２探索空間を構築するために使用される。例では、第２探索空間は、位置４０９および４０６（すなわち、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔ）を接続する直線上にあるハーフピクセル位置４１１および４１２（図では空の円）を指し示す２つの追加の動きベクトル候補を含む。この例では、ハーフピクセル位置４１１および４１２は、それぞれ、ＭＶ０'の上方及び下方のハーフピクセル位置である。第１探索空間の候補及び第２探索空間の候補から、最小コストをともなう候補が、最終動きベクトルＭＶ０''として選択され、この例では位置４１２である。
【００８４】
図４の例は、１つの現在のブロック及び１つの参照画像のための動きベクトルの改良を図示し、すなわち、参照画像は、参照画像リストＬ０において、インデックス０が割り当てられる。現在のブロックの図面は、単なる概略図であり、探索空間ポイントの位置が、テンプレートの左上角部によって定められた検索テンプレートの位置に対応することを図示する。本開示は、テンプレートの任意のサイズ及び形状とともに適用可能である。テンプレートは、有利に、現在のブロックのサイズのブロックであり、２つの最良の動きベクトル候補の検索は、第１探索空間及び第２探索空間において、テンプレート（ブロック）マッチングによって実行される。現在のブロックは、一般的に、デコーダで利用できないので、テンプレートは、既にデコード済みの画像部分から構築される。例えば、双方向予測の場合、それぞれの２つの参照画像Ｒｅｆｐｉｃ０およびＲｅｆｐｉｃ１と関連する２つの初期動きベクトルＭＶ０及びＭＶ１がある。そのとき、動きベクトルの改良のためのテンプレートブロックは、ＭＶ０ｉｎＲｅｆｐｉｃ０及びＭＶ１ｉｎＲｅｆｐｉｃ１によってそれぞれ指し示される２つのブロックの加重平均化によって構築されてもよい。他テンプレートの構築は、現在の画像、又は、それぞれの参照画像、あるいは、既にデコードされた最も近い画像から、既にデコード済みのピクセルに基づいて、可能である。
【００８５】
第１動きベクトル候補の先端（すなわち、エンドポイント）と、第２動きベクトル候補ＭＶ０'ｓｅｃｏｎｄＢｅｓｔの先端とを接続する直線の方向に従って、第２探索空間（すなわち、第２探索空間の動きベクトル候補によって指し示された位置）のサイズ（すなわち、候補の数）及び／又は位置（位置）が決定される。具体的には、第１動きベクトル候補、及び第１動きベクトル候補及び第２動きベクトル候補の先端を接続することによって定められた方向（線）は、第２段階において使用される候補の数及び／又は座標を決定するために使用される。第２探索空間のサイズは、第１動きベクトル候補ＭＶ０が指し示す位置に従って決定されてもよい。しかしながら、本発明は、２つの最良な位置に基づいて、第２探索空間のサイズ及び位置の両方を決定することに限定されるものではないことに留意されたい。例えば、第２探索空間のサイズ（位置の数に関して）は、一定とすることができ、第２探索空間の位置のみが、２つの最良の位置に基づいて、決定されてもよい。
【００８６】
本開示の第１実施形態による探索空間構成は、図５〜図８、図１０、及び図１１に例示的に図示されている。これらの例では、第２探索空間のサイズは常に２であり、しかし、その位置は、第１探索空間の２つの最良な位置によって定められる。図からわかるように、第１（例えば整数）ピクセル解像度を有する第１探索空間は、既に図４で示された「正方形」コンスタレーションを有する。この第１探索空間から、９点で（初期ベクトルポイントＭＶ０を囲む８つの点）、第１動きベクトル候補ＭＶ０'及び第２動きベクトル候補ＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、コスト関数に従って特定される。
【００８７】
有利に、第１実施形態によれば、複数の動きベクトル候補を含む第１探索空間は、整数のピクセル解像度を有する。従って、第１段階後、コスト関数が最小化される位置を指し示す第１動きベクトル候補ＭＶ０'、及びコスト関数が２番目に最小な値を有する第２動きベクトル候補ＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、整数ピクセル検索解像度を使用して最初に決定される。
【００８８】
さらに、第２探索空間は、第１探索空間の解像度に関して小数のピクセル解像度を有し、第１探索空間に含まれた第１動きベクトル候補及び第２動きベクトル候補によって定められる方向にある位置を指し示す１つ又は複数の動きベクトル候補を含む。従って、第２段階において（より正確に言えば、図３の「段階２」３０３）、第２探索空間（すなわち、新しい検索ウィンドウ）の１つ又は複数の、例えば２つの、ハーフピクセル位置、これは、第１探索空間の最良の候補が周知のＭＶ０'をともなうので、動きベクトルの選択を最後に実行するために、ＭＶ０'よりもより低コストを有する動きベクトル候補が見つけられるまで、ＭＶ０'のコストは、第２探索空間の追加のポイントのコストとさらに比べる必要が単にあることを意味する。この場合、第２探索空間を含む第２探索段階は、第１検索段階より細かい正確さを有する。言い換えれば、もし、第２探索空間が第１探索空間より高い解像度（すなわち、探索空間位置間の距離がより短い）を有するならば、有利であり得る。この方法において、探索空間は、その構築のそれぞれの段階をともなって改良され、そのような段階を２より多く含んでもよい。例えば、第１探索空間及び第２探索空間ジョイントの２つの最良な位置に基づいて、第１探索空間及び第２探索空間より高い解像度をともなう第３探索空間が構築されてもよい。 
【００８９】
図４〜図８の例において、第２探索空間の１つ又は複数のハーフピクセル位置は、ＭＶ０'と、差分ベクトルＭＶ０'ｄｉｆｆ＝（ＭＶ０'−ＭＶ０'ｓｅｃｏｎｄＢｅｓｔ）に対応するＭＶ０'ｓｅｃｏｎｄＢｅｓｔとを接続する直線の方向に従って選択される。従って、第２探索空間は、ＭＶ０'ｄｉｆｆと画像境界（または、参照画像においてピクセルの水平行）との角度従って決定される。第２探索段階の最後で、図３の段階３０４で最終動きベクトルＭＶ０''が決定される。
【００９０】
さらに、第２探索空間の少なくとも一つの動きベクトル候補は、有利に、第１探索空間に含まれた第１動きベクトル候補及び第２動きベクトル候補によって指し示された複数の位置間の位置を指し示す。第２探索空間は、第１動きベクトル候補及び第２動きベクトル候補間のポイントである単一の動きベクトル候補を含んでよいことを留意すべきである。
【００９１】
さらに、本開示の第１実施形態による例示的な探索空間のコンスタレーションは、図５〜図８、図１０、及び図１１に関して以下に説明される。
【００９２】
図５〜図８において、ＭＶ０'は、初期動きベクトルＭＶ０に対して（すなわち、第１探索空間の中心における位置の）最も近いまたは２番目に最も近い隣接位置の１つを、すなわち、ＭＶ０の位置を直接囲む位置の１つを指し示す。第２探索空間は、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する直線上の位置に対して、両方の位置をほぼ指し示す、ＭＶ０'の両側の位置を指し示す２つの動きベクトル候補を含むように決定される。言い換えれば、第２探索空間は、ＭＶ０'とＭＶ０'ｓｅｃｏｎｄＢｅｓｔとの間の第１位置と、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する方向において第１位置とは反対側に配置された第２位置とを含む。 
【００９３】
ここで、本出願の残りで同様に、「最も近い」隣接、又は隣接する、又は隣接位置は、考慮された（一部の）探索空間の解像度において与えられ位置に隣接する位置を言及する。例えば、参照画像が小数１／４ピクセル解像度を有するとしても、仮に第１探索空間が整数解像度を有するならば、隣接位置もまた、第１探索空間において互いから整数ピクセル距離を有する。これが適用されるが、第１探索空間位置は、参照画像の小数ピクセル位置上に配置されてもよい。 
【００９４】
さらに、「２番目に最も近い位置」は、２つの最も近い隣接点に隣接する位置を言及する（矩形に配置された探索空間において対角に隣接する）。しかしながら、どの図にも示されていない一般的な場合において、１つの方向（例えば垂直方向）において隣接位置までの距離は、他の方向（例えば水平）における距離と異なってもよい。この場合、本開示で使用されるような用語「最も近い隣接点」は、距離において可能性がある差にかかわらず、両方向における隣接位置に適用される。
【００９５】
図５及び図６では、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、第１探索空間（すなわち、フルピクセル解像度）の解像度において互いに関して最も近い隣接である。図において、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する直線は、垂直線である。図５に示される探索空間のコンスタレーションは、図４に示される探索空間のコンスタレーションと同一である。もし、ＭＶ０'ｓｅｃｏｎｄＢｅｓｔが、ＭＶ０'の上方又は下方に置かれるよりむしろ、ＭＶ０'の左又は右に置かれるならば、第１動きベクトル候補及び第２動きベクトル候補を接続する直線は、水平線に対応する。図に示されていないが、第１実施形態は、第１動きベクトル候補及び第２動きベクトル候補が水平線によって結び付けられる場合にも適用される。
【００９６】
図７に示される例では、第２動きベクトル候補ＭＶ０'は、第１動きベクトル候補ＭＶ０'の２番目に近い隣接点を指す。そのような場合には、第１動きベクトル候補及び第２動きベクトル候補を接続する直線は対角線である。
【００９７】
現在のブロックの予測値と、テンプレートブロックとの間の類似性は、１つの方向において単調に増大することが、通常、期待される。従って、図５〜図８に示されるように、第１探索空間の解像度において、候補ベクトルＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、最も近い又は２番目に近い隣接とすべきである。しかしながら、図８に示されるように、それぞれの動きベクトル候補ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔのためよりも高い、コスト関数の値のために、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔ間の探索空間の第３動きベクトル候補があることが起こり得る。例えば、そのような状況は、コード化され／デコードされるビデオにおけるノイズに起因して生じるかもしれない。そのような状況において、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する直線上の２つの小数ピクセル位置は、ＭＶ０'ｓｅｃｏｎｄＢｅｓｔよりもＭＶ０'により近い第２探索空間を形成するために選択されてよい、しかし、それでも、依然として、第１探索空間の２つの最良な位置によって定められる方向にあってもよい。しかしながら、本開示は、そのような手順によって限定されるものではない。例えば、低い複雑さを維持するために、最低コストをともなう２又はより多くの位置に基づいて、コスト関数トレンドが単調でないならば、デフォルトの第２探索空間は、例えば、水平方向であると仮定するように設定されてよい。水平方向は、普通のビデオにおける典型的な被写体の動きとして同様に、カメラのパニングに起因して、普通のビデオシーケンスにおいて、より可能性がある方向として考慮されてよい。言い換えれば、第１探索空間の第１最良動きベクトル候補及び第２最良動きベクトル候補に基づくコスト関数の明確なトレンドがないならば、好ましくは、第１最良の動きベクトル候補周りのあるポイントは、第２探索空間として設定される。第２探索空間のサイズを減らすために、デフォルト方向が仮定されてよく、対応するデフォルトの第２探索空間が設定されてよい。 
【００９８】
第１実施形態に係る第２段階における第２探索空間の決定のための手順は、図９に図示される。具体的には、第２探索空間の動きベクトル候補が指し示すピクセル位置は、差分ベクトルＭＶ０'ｄｉｆｆ  ＝  （ＭＶ０'  −  ＭＶ０'ｓｅｃｏｎｄＢｅｓｔ）の成分に従って決定される。
【００９９】
もし、ＭＶ０'ｄｉｆｆが水平成分のみを有するならば（すなわち、ゼロではない）、第２探索空間は、図９（ａ）に示されるように、第２探索空間の解像度（例えばハーフピクセル解像度）に対応するＭＶ０'までの距離をそれぞれ有するＭＶ０'の左右に２つの位置を備えるように決定される。
さらに、もし、ＭＶ０'ｄｉｆｆが垂直成分のみを有するならば、第２探索空間は、第２探索空間の解像度に対応するＭＶ０'までの距離をそれぞれ有するＭＶ０'の上方及び下方の２つの位置を備えるように決定される（図９（ｂ）参照）。 
【０１００】
もし、ＭＶ０'ｄｉｆｆが、部分（ｃ）及び（ｄ）に示されるように、水平成分及び垂直成分の両方を有するならば（ゼロではない値をともなう）、第２探索空間は、第２探索空間の解像度におけるＭＶ０に関連する位置に関して２番目に最も近い（対角）隣接点位置に選択される。もし、水平成分及び垂直成分は、両方とも正、又は両方とも負ならば、２番目に近い隣接点の位置は、図９（ｃ）に示されるように、ＭＶ０に関して左上及び右下に選択される。もし、一方の成分が正であり、他方の成分が負であるならば、２番目に近い隣接点の位置は、ＭＶ０'に関して左下及び右上に選択される（図９（ｄ））。別の方法で、もし、ＭＶ０'ｄｉｆｆが決定することができないならば（例えば、同一コストを有する第１探索空間の全て候補などのコスト関数の特性に起因する）、ＭＶ０'ｄｉｆｆは（０，０）として設定されてもよく、例えば図９（ａ）−（ｄ）において示される代替のうち、任意の選択は、デフォルトの第２探索空間のためになされてよい。しかしながら、図９（ａ）のこの場合には、検索ポイントの構成は、一般的に、ビデオシーケンスのプロパティの統計（オブジェクト又はカメラの水平の動きは、通常、水平方向に存在する利益のエリアとして、垂直よりも可能性がある。）に起因することが好ましい（図９（ｂ），（ｃ），及び（ｄ））。
【０１０１】
図９において、考慮される座標にある本出願の残りにおいて同様に、横軸（ｘ軸）の正方向は右を指し示し（通常のデカルト座標システムにと同様）、それに対して、縦軸の正方向（ｙ軸）は下を指し示す（デカルト規定とは対照的だが、典型的には、画像処理において使用される）ことを留意されたい。
【０１０２】
図５〜図８に示されるように、探索空間のコンスタレーションの全てにおいて、第１動きベクトル候補ＭＶ０'は、第１探索空間の端であるピクセル位置を指し示す。具体的には、一つの動きベクトル候補は、第１探索空間の２つの動きベクトル候補間の位置を指し示す。第２探索空間の他の動きベクトル候補は、第１探索空間の外側の位置、すなわち、第１探索空間の動きベクトル候補によって囲まれていない位置、を指し示す。
【０１０３】
しかしながら、上記のように、第２探索空間の動きベクトル候補の位置だけでなく、動きベクトル候補ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する直線の方向に従ったサイズも（すなわち、動きベクトル候補の数）。より具体的には、もし、第１動きベクトル候補ＭＶ０が第１探索空間の中心における位置を指し示すならば、１つのベクトル候補は、第２探索空間のために十分である。具体的には、第２探索空間の単一の動きベクトル候補は、そのとき、第１探索空間の２つの動きベクトル候補間の第２探索空間の解像度の位置を指し示す。しかしながら、図５〜図８に示される探索空間のコンスタレーションとは対照的に、第１探索空間の外側の第２動きベクトル候補は除外される。図９に図示された手順は、第２探索空間、すなわち、第２探索段階の検索ウィンドウの一つの動きベクトル候補のみを決定することに従って変更される。
【０１０４】
一つの動きベクトル候補のみを含む第２探索空間の例は、図１０および１１に示される。図１０におけるＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、最も近い隣接点であり（水平に隣接）、並びに、図１１におけるＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、２番目に近い隣接点である（対角線上に隣接）。両方の図に示されるように、ＭＶ０'は、第１探索空間の範囲内の位置を指し示す。言い換えれば、ＭＶ０'に隣接するピクセル位置の全てを指し示す動きベクトル候補がある。隣接位置を指し示すこれらの動きベクトル候補の一つは、ＭＶ０'ｓｅｃｏｎｄＢｅｓｔである。
【０１０５】
言い換えれば、もし、第１動きベクトル候補ＭＶ０'ならば、もし、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続することによって定められ方向にあり、第１探索空間においてＭＶ０'に隣接する第２位置が、第１探索空間に属するならば、第２探索空間は、第１動きベクトル候補及び第２動きベクトル候補間の小数ピクセル位置を指し示す一つの動きベクトル候補のみを含む。そのような状況において、第２位置は、計算され、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔより高いコストを既に有するので、低コスト候補がこの方向において見つけることができる可能性は、むしろ低い。また、一般的に、探索空間における位置の数は、ＭＶ０'より良好な（コストに関して）動きベクトル候補が見つけられる確率によって決めてもよい。その確率は、第１探索空間の位置のために計算されたコスト関数を補間及び／又は外挿することによって推定され得る。
【０１０６】
上記例において、第１探索空間は、正方形グリッド内に配置された９つの隣接位置を有することが示されていることを留意されたい。しかしながら、本開示は、特定のサイズの探索空間又は特定の構成のピクセルに限定されるものではな。同様に、第１実施形態は、同一又は異なる解像度を有する第１探索空間及び第２探索空間に適用できる（後で図５〜図８に示される）。第２探索空間は、また、２以上の位置を有することができる。 
【０１０７】
例示的な第１実施形態によれば、図１８の改良方法における第１探索空間の動きベクトル候補のためのコスト計算のサブ段階Ｓ１８０３が、図１９に示される。変数ｉ，Ｐ１，及びＰ２は初期化され、ここで、ｉは、探索空間（例えば、第１探索空間）のそれぞれの候補のそれぞれを後に示すインデックス変数である。変数Ｐ１及びＰ２は、それぞれ、最低コスト及び２番目に低いコストをともなう動きベクトル候補示す（すなわち、探索空間における位置、及びその位置に関連するコスト値）。最初に、Ｐ１及びＰ２は、任意の位置に関連しない値に初期化されてよく、Ｐ１及びＰ２に関連するそれぞれのコストは、おそらくコスト計算において、取得された任意の値よりも高い値に、すなわち、変数をともなって表される最大コストに、初期化されてよい。ｉを繰り返すループにおいて、ｉ番目の動きベクトル候補のコストが計算される（Ｓ１９０２）。ｉ番目の動きベクトル候補のコストは、最低コストをともない現在記憶されている動きベクトルＰ１のコストと比較される（Ｓ１９０３）。もし、ｉ番目の動きベクトル候補のコストが、記憶されたＰ１より低いコストであるならば、その後、Ｐ１は、ｉ番目の動きベクトル候補に設定され、記憶される（Ｓ１９０４）。もし、ｉ番目の動きベクトル候補のコストが、Ｐ１より低いコストではなければ、その後、ｉ番目の動きベクトル候補のコストは、Ｐ２のコストと比較される（Ｓ１９０５）。もし、ｉ番目の動きベクトル候補のコストが、Ｐ２より低いコストであるならば、その後、Ｐ２は、ｉ番目の動きベクトル候補に設定され、記憶される（Ｓ１９０６）。２つの比較の段階Ｓ１９０３，Ｓ１９０５、及びおそらく、１つの記憶の段階のＳ１９０４，Ｓ１９０６後、ｉは増加される。もし、ｉが、第１探索空間内の動きベクトル候補の数を表す最大値ｉｍａｘに、まだ達していないならば（Ｓ１９０８）、方法は、コスト計算段階Ｓ１９０２に戻る。もし、ｉがｉｍａｘに達したならば（Ｓ１９０８）、コスト計算は終了し（Ｓ１９０９）、図１８の改良が続く。
【０１０８】
第２探索空間の動きベクトル候補のためのコスト計算のサブ段階（Ｓ１８０５）は、図１９の上記の記述で説明された段階と同様に実行され得る。しかしながら、Ｐ２のコストをともなうｉ番目の動きベクトル候補のコストと比較する段階（Ｓ１９０５）、及び第２動きベクトル候補Ｐ２を記憶する段階（Ｓ１９０６）は除外され得る。これは、第２探索空間の検索において、その結果は、第１探索空間及び第２探索空間にわたって、最良の動きベクトルだからである。もし、第２探索空間がさらに拡大しないならば、２番目の最良の動きベクトルは、それ以上使用されない。
【０１０９】
例示的な第２実施形態
【０１１０】
例示的な第２実施形態によれば、第２探索空間の決定に使用される第１動きベクトル候補及び第２動きベクトル候補は、最低及び２番目のマッチングコスト（例示的な第１実施形態のように）にそれぞれ関連する第１探索空間に含まれる動きベクトル候補である。
【０１１１】
さらに、例示的な第２実施形態によれば、図３の探索空間決定ユニット３１０は、動作中において、領域だる第２探索空間の位置を決定する。ここで、「領域」との用語は、少なくとも二つの動きベクトル候補がそれぞれ指し示す少なくとも二つの位置を含む空間を言及する。具体的には、上記の少なくとも二つの位置は、第２探索空間のピクセル解像度において隣り合っている。第２探索空間は、図１２および１３に示されるように、第１探索空間と同じ解像度を有することができる。 しかしながら、探索空間は、解像度において異なってもよい。
【０１１２】
有利に、図３の探索空間の構築の第１段階３０１で決定される探索空間は、隣接する位置、すなわち、ＭＶ０によって指し示された位置に、第１探索空間のピクセル解像度に動きベクトルの初期推定値の最も近い隣接点を指し示す動きベクトルＭＶ０及び動きベクトル候補の初期推定値を含む。言い換えれば、「正方形」配置（形状）を有する第１探索空間が、構築の第１段階である第１段階３０１において構築される第１実施形態と対照的に、第１探索空間は、「クロス」配置を有する。しかしながら、第１探索空間は、エンコーダ及びデコーダの両方に同一の探索空間が使用される限り、任意の形状でもよいことに留意されたい。これは、実装の簡略化のために有利であり、もし、探索空間が、クロス又は正方形配置又は任意の他の構成などの予め定められた特定の形状を有するならば、初期ベクトルＭＶ０の位置は、そのような第１探索空間の位置に単に決定される。一方、本発明は、サイズ（候補ＭＶによって指し示された位置に関して）及び／又は形状が異なる第１探索空間と共に機能してもよい。コスト関数の最低値をともなう第１動きベクトル候補ＭＶ０'、及び２番目に最小な値をともなう２番目の候補ＭＶ０'ｓｅｃｏｎｄＢｅｓｔが計算され、選択される（３０２）。
【０１１３】
ＭＶ０'が指し示す位置を定義し、第１動きベクトル候補ＭＶ０'及び第２動きベクトル候補ＭＶ０'ｓｅｃｏｎｄＢｅｓｔが指し示す位置を接続する直線によって定められた方向の座標に基づいて、図３の第２段階３０３において、第２探索空間の構築を実行するために、領域が選択される。
【０１１４】
より具体的には、第２探索空間に含まれる一つの動きベクトル候補は、第１探索空間内に含まれない第１動きベクトル候補及び第２動きベクトル候補の位置を接続する直線上の第２探索空間の解像度において、ＭＶ０'の位置に最も近い位置を指し示す。１つ又は複数の追加の動きベクトル候補は、第２探索空間のピクセル解像度において隣接する位置を指し示す第２探索空間に含まれ、第２探索空間は、第１探索空間に含まれない。
【０１１５】
この第２実施形態による探索空間構成の例は、図１２および１３に示される。例として、第２探索空間のピクセル解像度は、第１探索空間のピクセル解像度と同一である。図からわかるように、初期の動きベクトル候補が指し示す位置は、それぞれピクセル解像度において、ＭＶ０に隣接する４つのピクセル位置、すなわち、４つの最も近い隣接点によって囲まれる。ＭＶ０、及びＭＶ０に隣接するこれらの４つの位置を指し示す動きベクトル候補は、第１探索空間に含まれる。コスト関数に従って、第１探索空間の最低コスト及び２番目に低いコストをともなう第１動きベクトル候補ＭＶ０'及び第２動きベクトル候補ＭＶ０'ｓｅｃｏｎｄＢｅｓｔが決定される。ＭＶ０'によって指し示された位置、及び差分ベクトルＭＶ０'ｄｉｆｆによって定められたＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する直線の方向は、図３の第２段階３０３において、第２探索空間を決定するために使用される。ここで、ＭＶ０'ｄｉｆｆの定義は、例示的な第１実施形態の記述と同一である。図１２および１３の両方において、第２探索空間は、（ＭＶ０'＋ＭＶ０'ｄｉｆｆ）によって定められＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する直線上の位置、及び第１探索空間の動きベクトル候補によって指し示されない上記直線上の上記位置に隣接する位置（すなわち、最も近い隣接）をほぼ指し示す動きベクトル候補を含む。
【０１１６】
図１２において、ＭＶ０'及びＭＶ０ｓｅｃｏｎｄＢｅｓｔは、第１探索空間の解像度において隣接していない、それらは２番目に近い点である。第２探索空間は、ベクトル、すなわち上記直線上の上記位置、及び上記位置に最も近い４つの隣接点を指し示すベクトルを含む。図１３におけるＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔは、第１探索空間の解像度における隣接位置を指し示す。この場合、（ＭＶ０'＋ＭＶ０'ｄｉｆｆ）によって定義されたＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔを接続する直線上の第２探索空間における位置は、ＭＶ０に対して最も近い隣接点である。第２探索空間は、その後、（ＭＶ０'＋ＭＶ０'ｄｉｆｆ）に対応する位置を指し示すベクトル、及びＭＶ０'に等しくない（ＭＶ０'＋ＭＶ０'ｄｉｆｆ）に対して３つの最も近い隣接点を指し示す動きベクトル候補を含む。従って、第２探索空間は、４つの動きベクトル候補を含む。
【０１１７】
しかしながら、もし、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔが、第１探索空間のピクセル解像度において、最も近いわけでなく、２番目に近いわけでもないならば、すなわち、もし、ＭＶ０'及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔがそれぞれ指し示すピクセル位置間の第１探索空間に１つのピクセル位置があるならば、同一の第２探索空間／ウィンドウは、図１３に示されるよう場合のように、決定され得る。
【０１１８】
もし、第２探索空間によって示される検索座標が、既に、第１探索空間に含まれているならば、その後、第２探索操作は実行されない（終了する）。もし、第１段階及び第２段階で使用されるマッチングテンプレート及び／又はコスト関数が同一ならば、これは、具体的な場合かもしれない。さらに、他の代替として、マッチングテンプレート及び／又はコスト関数が、第１探索段階及び第２探索段階において異なる場合、第２探索操作が実行され得る。本開示は、探索空間のサイズの減少、及び、具体的には、コスト関数開発の特性に基づいて、第２探索空間を設定することによる削減に関することに留意されたい。第１探索空間及び第２探索空間、又は、もし探索空間の決定が２以上の段階につながるならば、更なる探索空間など、それぞれの探索空間部分について同一又は異なってもよい任意のテンプレートが、本発明に適用可能である。
【０１１９】
例示的な第２実施形態によれば、図１８に示される動きベクトルの改良における第１探索空間の（第２探索空間（Ｓ１８０５）の）動きベクトル候補のコストを計算するためのサブ段階（Ｓ１８０３）は、図１９に関して上述の第１実施形態に係る計算と同様に実行できる。
【０１２０】
例示的な第３実施形態
【０１２１】
今まで説明された実施形態において、図３に示される探索空間決定ユニット３１０は、マッチングコストが最小及び２番目に最小な第１探索空間の動きベクトル候補である第１探索空間から第１動きベクトル候補及び第２動きベクトル候補を識別する。
【０１２２】
本発明の例示的な第３実施形態によれば、第１動きベクトル候補及び第２動きベクトル候補の選択３０２のために、テンプレートマッチングコストは、動きベクトルの初期推定値ＭＶ０が指し示す開始位置周りの位置を指し示す４つの動きベクトル候補について、演算される。具体的には、第２探索空間を決定するために、動きベクトルの推定値ＭＶ０によって指し示される位置に対して、第１探索空間のピクセル解像度において、隣接するピクセル位置のマッチングコストが評価される。上記の第１動きベクトル候補及び第２動きベクトル候補によって指し示された位置に対して、第１探索空間のピクセル解像度において隣接し、動きベクトルの推定値によって指し示された位置とは異なる第２探索空間の第１動きベクトル候補によって指し示されるように、ピクセル位置は決定される。第１動きベクトル候補は、図１４に示されるように、マッチングコストが減少することが期待される象限上まで指し示される。
【０１２３】
図１５では、図３に示される探索空間決定ユニット３１０より一般的な改変である探索空間決定ユニット１５１０が示される。動きベクトルの初期推定値ＭＶ０に基づいて、図１４（ａ）に例示的に図示される第１探索空間は、図１５の探索空間の構築１５０１の段階１において決定され、動きベクトルのための初期推定値の座標は、（ＭＶ０＿ｘ及びＭＶ０＿ｙ）として示される。第１探索空間は、ＭＶ０、及びＭＶ０に対応する位置、例えば、第１探索空間のピクセル解像度においてＭＶ０に対して最も近い隣接点の周りのピクセル位置を指し示す動きベクトル候補、からなる。マッチングコストは、第１探索空間の動きベクトル候補のために計算される。第１動きベクトル候補及び第２動きベクトル候補１５０１を選択することによって、好ましくは直交方向に沿った２つの方向（例えば、縦横）が、マッチングコストが減少することが期待されるように計算される。
【０１２４】
図１４において、座標が考慮される本出願の残りの部分と同様に、横軸（ｘ軸）の正方向は右を指し示し、それに対して、縦軸の正方向（ｙ軸）は下を指し示す。
【０１２５】
より正確に言えば、ＭＶ０に対応する位置ピクセルに対して隣接する位置が、２つのグループに分類されるために、２つの比較１５０２１、１５０２２が実行される。初期の動きベクトル候補によって指し示されるピクセル位置に対して、第１探索空間のピクセル解像度において、隣接し、初期の動きベクトル候補と同じ垂直成分を有する２つのピクセル位置のマッチングコストが比較される。この第１比較１５０２１で評価された２つの比較されたベクトルから、より低いマッチングコストをともなうベクトルが、第１探索空間の第１動きベクトル候補として選択される。
【０１２６】
また、初期の動きベクトル候補によって指し示されるピクセル位置に対して、第１探索空間のピクセル解像度において、隣接し、初期の動きベクトル候補と同じ水平成分を有する２つのピクセル位置のマッチングコストが比較される。この第２比較１５０２２で評価された２つの比較されたベクトルから、より低いマッチングコストをともなうベクトルが、第１探索空間の第２動きベクトル候補として選択される。
【０１２７】
これの２つの比較の結果として、ピクセル位置は、第１動きベクトル候補と同じ垂直成分を有し、第２動きベクトル候補と同じ水平成分を有する第２探索空間の第１動きベクトル候補によって指し示されるように決定される。第１動きベクトル候補及び第２動きベクトル候補は、垂直方向及び水平方向において、正又は負の半平面をそれぞれ定義する。これら重複する象限は、マッチングコストが減少することが期待されるエリアとして選択され、第２空間を定義する。図１４（ｂ）において、第２探索空間は、１つのポイントのみを含む。
【０１２８】
第１探索空間は、動きベクトルの初期推定値ＭＶ０、及びその最も近い隣接点、すなわち、第１探索空間の解像度において、ＭＶ０に隣接するピクセル位置を指し示す動きベクトル候補を含むことができる。第２実施形態に関して、また、説明された「クロス」配置を有するそのような探索空間構成は、図１４（ａ）に示される。使用されるコスト関数に従うマッチングコストは、探索空間のこれらの５つの動きベクトル候補のために計算される。
【０１２９】
以下において、一般性を失うことなく、動きベクトルの初期推定値ＭＶ０が指し示すピクセル位置の座標は、（０，０）であると仮定する。第２探索空間の第１動きベクトルの座標（水平、垂直）を決定するための上述の２つの比較は、その後、例えば、以下の手順に従って実行され得る。
【０１３０】
垂直＝−１，水平＝−１；
もし（動きベクトル候補（０，１）のコスト＜動きベクトル候補（０，−１）のコスト）ならば
垂直＝−１；
もし（動きベクトル候補（１，０）のコスト＜動きベクトル候補（−１，０）のコスト）ならば
水平＝１；
【０１３１】
上に示された手順又は同様の手順に基づいて、動きベクトル（垂直，水平）を決定することによって、マッチングコストが減少することが期待されるように、象限が選択される。
【０１３２】
従って、第２探索空間（図３の３０３）の決定に使用される象限は、座標ｘ，ｙ＞０（水平＊ｘ，垂直＊ｙ）を有する候補と、上述の手順によって決定された値を有する「水平」及び「垂直」と、を含む。象限の決定は、例示的に、図１４（ｂ）に示される。示される例において、動きベクトル（−１，１）は、選択された象限を定義するために決定される（すなわち、右上象限）。この特定の例において、第２探索空間に含まれない他の３つの象限における潜在的な動きベクトルは、より小さドットとして示される。
【０１３３】
本開示は、上記手順の明確な定義を使用することに限定されるものではない。例えば、（１，１）は、（−１，−１）の代わりの初期値として、又は初期座標の設定の代わりの初期値として、使用されてよく、「別の方法で」−条項が使用されてよく（図１５において、ｉｆ−別の方法で比較１５０２１，１５０２２）、「ｉｆ」条件文の命令（シーケンス）がやり取りされてもよい。
【０１３４】
上述のように、第２探索空間の第１動きベクトル候補が決定される場合、そのマッチングコストが計算される。特定の場合として、第２探索空間は、一つの上記第１動きベクトル候補のみを含んでよい。この場合、チェックされた動きベクトル候補から（説明した例において、第１探索空間の５つの動きベクトル候補、及び第２探索空間の一つの動きベクトル候補）、最も低いマッチングコストをともなう動きベクトル候補は、現在のブロックのために使用される動きベクトルとして選択される。
【０１３５】
しかしながら、第２探索空間の更なる少なくとも１つの動きベクトル候補として、第２探索空間の解像度における位置を指し示す動きベクトル候補が、決定されてもよい。この少なくとも一つの更なる動きベクトル候補は、動きベクトルの推定値と第２探索空間の候補とを接続する直線上にほぼ配置された第２探索空間の解像度における位置を指し示す。第２探索空間のピクセル解像度は、第１探索空間のピクセル解像度より高くてもよい。第２探索空間の更なる動きベクトル候補は、第２探索空間の第１動きベクトル候補、及び動きベクトルの推定値によって指し示された位置間に配置された位置を指し示してもよい。
【０１３６】
具体的には、第２探索空間１５０３の決定の第１動きベクトル候補の後、第２探索空間の決定の第２段階において、継続されてよく、第２探索空間は、その後、第２探索空間の第１動きベクトル候補によって定義された象限内の位置に指し示される少なくとも一つの追加の動きベクトル候補を含むように決定されてよい。例えば、今までチェックされた候補から、最小及び２番目の最小マッチングコストをともなう２つの候補が特定され、第２探索空間の動きベクトル候補が指し示す更なるポイントの決定のための方向を計算するために使用され得る。
【０１３７】
最小マッチングコスト及び２番目の最小マッチングコストをともなう候補に基づいて計算された方向の計算のための例示的な手順は、以下に示され、最低及び２番目に低いマッチングコストをともなう候補の座標は、（Ｐ＿ｍｉｎ＿ｘ，Ｐ＿ｍｉｎ＿ｙ）及び（Ｐ＿ｓｅｃｏｎｄ＿ｘ，Ｐ＿ｓｅｃｏｎｄ＿ｙ）として示され、変数「方向＿垂直」及び「方向＿水平」は、上記方向を定義するベクトルの成分を示す。
【０１３８】
方向＿垂直＝０，方向＿水平＝０；
もし（Ｐ＿ｍｉｎ＿ｘ！＝Ｐ＿ｓｅｃｏｎｄ＿ｘ）ならば、
方向＿水平＝−１；
もし（Ｐ＿ｍｉｎ＿ｙ！＝Ｐ＿ｓｅｃｏｎｄ＿ｙ）ならば、
方向＿垂直＝１；
【０１３９】
図１６に示されるように、第２探索空間のための新しい動きベクトル候補は、ベクトル（方向＿垂直，方向＿水平）及び０．５×（Ｐ＿ｍｉｎ＿ｘ＋方向＿垂直，Ｐ＿ｍｉｎ＿ｙ−方向＿水平）及び０．５×（Ｐ＿ｍｉｎ＿ｘ−垂直，Ｐ＿ｍｉｎ＿ｙ；水平）、及び最も低いマッチングコストをともなう動きベクトル候補の座標（Ｐ＿ｍｉｎ＿ｘ，Ｐ＿ｍｉｎ＿ｙ）、又は第１探索空間び第１動きベクトル候補及び第２動きベクトル候補が指し示すピクセル位置に応じたこれらの２つポイントの一つ、によって定められた方向に基づいて選択されてもよい。第２探索空間の新しい動きベクトル候補のマッチングコストが計算され、第１探索空間及び第２探索空間の動きベクトル候補から、最小マッチングコストをともなう動きベクトル候補が動きベクトルの改良処理の出力、すなわち、図３のＭＶ０''として、選択される。
【０１４０】
図１６の例として、第２探索空間は小数のピクセル解像度、具体的には、ハーフピクセル解像度を有する（第２探索空間の追加の動きベクトル候補の位置に向かう方向を指定するベクトルの係数０．５に従って）。１つ又は２つ動きベクトル候補に代わり、１／４ピクセル解像度などの代替的なピクセル解像度が使用されてもよく、動きベクトル候補（Ｐ＿ｍｉｎ＿ｘ,Ｐ＿ｍｉｎ＿ｙ）、及び方向（方向＿垂直，方向＿水平）によって定められた線をおおよそ指し示す２つ又は４つの動きベクトル候補が使用されてもよい。
【０１４１】
図１６に示される例示的な探索空間構成では、第２探索空間の第１動きベクトルは、０．５×（Ｐ＿ｍｉｎ＿ｘ＋方向＿垂直，Ｐ＿ｍｉｎ＿ｙ−方向＿水平）及び０．５×（Ｐ＿ｍｉｎ＿ｘ−垂直，Ｐ＿ｍｉｎ＿ｙ＋水平）がベースである第２探索空間の追加の動きベクトルの計算に関して最も低いマッチングコストを伴う動きベクトル候補（Ｐ＿ｍｉｎ＿ｘ，Ｐ＿ｍｉｎ＿ｙ）と一致する。
【０１４２】
実施形態の組み合わせ
【０１４３】
上述の例示的な実施形態のそれぞれによれば、第２探索空間は、３０１で決定された第１探索空間、及び第１探索空間３０２から選択された第１動きベクトル候補及び第２動きベクトル候補において、第１段階の出力に基づいて選択される。しかしながら、検索処理の全ては、第１探索空間及び第２探索空間の決定、及びそれぞれの探索空間からの１つ又は２つの候補の選択より多くの段階に分割されてもよい。それぞれの段階又はサブ段階において、新しい探索空間は、例示的な実施形態の一つに従って決定されてもよい。例えば、図１６に関して上述の探索空間構成は、一例であり、第２探索空間の決定は、例示的な第３実施形態及び例示的な第１実施形態への適用を、次に、示唆する。これは、以下において説明される。
【０１４４】
図１６に示される例示的な探索空間構成では、第２探索空間は、第２探索空間の第１動きベクトル候補、及び２つの追加の動きベクトル候補を含む。第２探索空間のこれらの２つの追加の動きベクトル候補は、第１探索空間及び第２の５つの動きベクトル候補のうちの最も低いマッチングコストをともなう動きベクトル候補のピクセル位置によって、及び上で示された手順に従って計算された方向＿水平及び方向＿垂直の座標を有するベクトルによって定められた方向を有する線によって定義された線上のピクセル位置をほぼ指し示す。この手順は、２つの動きベクトル候補を接続する直線によって定められた方向に従う２つの動きベクトル候補の計算のための例である。この手順は、図５〜図１１を参照する上述された第１実施形態の第２探索空間の計算に使用されてもよい。言い換えれば、第３実施形態に係る第２探索空間の決定の任意の第２段階は、第１実施形態に係る第２探索空間の決定に対応する。
【０１４５】
言い換えれば、第２探索空間の第１動きベクトル候補のみより多くの動きベクトル候補を有する第２探索空間を決定する上記の例において、探索空間の追加の動きベクトルは、第１実施形態を伴う本開示のこの第３実施形態を組み合わせることによって、取得されている。
【０１４６】
図１６を参照して説明された例示的な第３実施形態の例において、第３実施形態及び第１実施形態は、第２探索空間を決定する場合、組み合わされる。しかしながら、本開示は、異なる実施形態の組み合わせの特定の例に限定されるものではない。
【０１４７】
さらに、本開示は、２つの異なる実施形態を組み合わせることに限定されるものではない。代替として、第２探索空間は、第１実施形態に係る第２段階３０３を次に適用し、従って、例えば、第１にハーフピクセル解像度、第２に１／４ピクセル解像度など、異なるピクセル解像度を有するネストされた探索空間を決定することによって、決定されてもよい。
【０１４８】
異なる例示的な実施形態の組み合わせの更なる例は、図１７に図示される。図１７（ａ）においてわかるように、５つの動きベクトル候補、すなわち、初期推定値動きベクトル、及び第１探索空間のピクセル解像度（例えば、フルピクセル解像度）における初期推定値動きベクトルに隣接する４つの動きベクトル候補を含む第１探索空間は、例示的な第２実施形態に従って、決定される。最低及び２番目に低いマッチングコストをともなう動きベクトル候補は、図１７に示される更なる５つの動きベクトル候補を備える第２実施形態に従った領域である第２探索空間を決定することに使用される。これらの更なる５つの動きベクトル候補に関して、第３実施形態、すなわち、図１７（ｃ）に示される追加の動きベクトル候補に適用される手法は、図１５の、ＭＶ０'ｆｉｒｓｔ及びＭＶ０'ｓｅｃｏｎｄである第１動きベクトル候補及び第２動きベクトル候補の選択（１５０２）を適用することによって、決定される。再ひ、第１実施形態に従って、最低及び２番目に低いマッチングコストをともなう２つの動きベクトル候補が決定される（図においてＭＶ０'ｃ及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔ＿ｃを示す）。図１７においてわかるように、ＭＶ０'ｃ及びＭＶ０'ｓｅｃｏｎｄＢｅｓｔ＿ｃに対応する位置を接続する直線上の位置をおおよそ指し示し、今まで使用された解像度より高いピクセル解像度（例えば、ハーフピクセル解像度）のピクセル位置を指し示す２つの追加の動きベクトル候補が追加される。
【０１４９】
異なる実施形態の組み合わせの利点は、参照画像の増大したエリアにおいて、同様の精度に維持しながら、動きベクトル候補の数が低く維持されることである。例えば、図１７においてわかるように、３つの実施形態に対応する３つの段階の連鎖は、７×７のフルピクセルの正方形に対応するエリアのためのハーフピクセル解像度の精度における予測値の位置の提供を可能とする。
【０１５０】
上述の動きベクトルの改良を含む動きベクトルの決定は、ビデオ信号（動画）のコード化及び／又はデコードの一部として実装され得る。しかしながら、動きベクトルの決定は、動き検出、動き解析、又は同様のものなどの画像処理において、他目的において使用されることもできる。 
【０１５１】
動きベクトルの決定は、装置のように実装されてよい。そのような装置は、ソフトウェア及びハードウェアをの組み合わせでもよい。例えば、動きベクトルの決定は、一般的な目的のプロセッサ、又はデジタル信号プロセッサ（ＤＳＰ）、又は現場でプログラム可能なゲートアレイ（ＦＰＧＡ）、又は同様のものなどのチップによって実行され得る。しかしながら、本発明は、プログラム可能なハードウェアに実装することに限定されるものではない。それは、特定用途向け集積回路（ＡＳＩＣ）、又は上で言及したハードウェア構成要素の組み合わせによって、実装され得る。 
【０１５２】
また、動きベクトルの決定は、コンピュータ可読媒体に記憶されたプログラム命令によって実装されてもよい。プログラムは、実行された場合、動きベクトルの推定値を取得する段階と、推定値に基づいて、複数の動きベクトル候補を含む第１探索空間を決定する段階と、コスト関数に従って、第１探索空間における第１動きベクトル候補及び第２動きベクトル候補を識別する段階と、第１動きベクトル候補及び第２動きベクトル候補に基づいて、１つ又は複数の動きベクトル候補を含む第２探索空間を決定する段階と、第１空間及び第２空間の動きベクトル候補の中から現在のブロックのための動きベクトルを選択する段階とをコンピュータに実行させる。コンピュータ可読媒体は、プログラムが記憶されたＤＶＤ、ＣＤ、ＵＳＢ（フラッシュ）ドライブ、ハードディスク、ネットワーキングを経由して利用できるサーバストレージなどの任意の媒体とすることができる。 
【０１５３】
エンコーダ及び／又はデコーダは、ＴＶセット、セットトップボックス、ＰＣ、タブレット、スマートフォン又は同様のものを含む様々なデバイスに実装され得る。それは、方法の段階を実装するソフトウェア、アプリでもよい。 
【０１５４】
要約すると、本発明は、ビデオシーケンスにおいて画像の現在のブロックのための動きベクトルを決定するための探索空間の構築に関する。探索空間の構築は、第１部分探索空間及び第２部分探索空間がそれぞれ決定される２つのメインステージに分割される。動きベクトルの初期推定値に基づいて、第１探索空間が最初に構築される。第１探索空間の第１動き候補及び第２動き候補は、コスト関数に従って特定される。第１動きベクトル候補及び第２動きベクトル候補に基づいて、第２探索空間が構築される。現在のブロックのための動きベクトルは、第１探索空間及び第２探索空間の動きベクトル候補から選択される。
【０１５５】
発明が動画ビデオコーディングのフレームワーク内で主に上述されたが、提案された技術は、２つ以上の画像を備える任意の画像セットのコーディング（すなわち、コード化又はデコード）のために同様に適用できる。画像セットは、例えば、コンピュータ断層撮影（ＣＴ）スキャン画像のシーケンスなどの医療撮像アプリケーションにおいて、取得される、例えば、静止画像のセットを含んでよい。添付の請求項では、「ビデオ」との用語は、故に、動画シーケンス、又は２つ以上の画像を含む任意の他の画像セットを意味してもよい。
【図１】
2020526112.tif 000003
【図２】
2020526112.tif 000004
【図３】
2020526112.tif 000005
【図４】
2020526112.tif 000006
【図５】
2020526112.tif 000007
【図６】
2020526112.tif 000008
【図７】
2020526112.tif 000009
【図８】
2020526112.tif 000010
【図９（ａ）】
2020526112.tif 000011
【図９（ｂ）】
2020526112.tif 000012
【図９（ｃ）】
2020526112.tif 000013
【図９（ｄ）】
2020526112.tif 000014
【図１０】
2020526112.tif 000015
【図１１】
2020526112.tif 000016
【図１２】
2020526112.tif 000017
【図１３】
2020526112.tif 000018
【図１４】
2020526112.tif 000019
【図１５】
2020526112.tif 000020
【図１６】
2020526112.tif 000021
【図１７（ａ）】
2020526112.tif 000022
【図１７（ｂ）】
2020526112.tif 000023
【図１７（ｃ）】
2020526112.tif 000024
【図１７（ｄ）】
2020526112.tif 000025
【図１８】
2020526112.tif 000026
【図１９】
2020526112.tif 000027
【手続補正書】
【提出日】令和2年2月4日(2020.2.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
映像フレームの現在のブロックのインター予測に用いられる動きベクトルを決定するための装置であって、前記装置は、
前記動きベクトルの推定値を取得し、前記推定値に基づいて、複数の動きベクトル候補を備える第１探索空間を決定し、コスト関数に従って、前記第１探索空間における第１動きベクトル候補及び第２動きベクトル候補を選択し、及び前記第１動きベクトル候補及び前記第２動きベクトル候補に基づいて、１つ又は複数の動きベクトル候補を備える第２探索空間を決定するように構成された探索空間決定ユニットと、
前記第１探索空間及び前記第２探索空間の前記動きベクトル候補の中から前記現在のブロックのための前記動きベクトルを選択するように構成された動きベクトル選択ユニットと
を備える装置。
【請求項２】
前記コスト関数は、予め定められたテンプレートに基づいており、前記動きベクトル候補のそれぞれに対して、前記予め定められたテンプレートと、前記動きベクトル候補のそれぞれによって指し示された予測値との間の類似性のレベルを示す、請求項１に記載の装置。
【請求項３】
前記探索空間決定ユニットは、前記第１動きベクトル候補及び前記第２動きベクトル候補が指し示す位置を接続する直線の方向に従って前記第２探索空間のサイズ及び／又は位置を決定するように構成される、請求項１又は２に記載の装置。
【請求項４】
前記探索空間決定ユニットによって前記第１探索空間を前記決定することは、
整数のピクセル解像度を有するように前記第１探索空間を設定することを備え、
前記探索空間決定ユニットによって前記第２探索空間を前記決定することは、
前記第１動きベクトル及び前記第２動きベクトル候補が指し示す前記位置を接続する直線の前記方向にある位置を指し示す１つ又は複数の動きベクトル候補を、前記第２探索空間に含めることを備え、前記第２探索空間は、小数のピクセル解像度を有する、
請求項３に記載の装置。
【請求項５】
前記第２探索空間の少なくとも一つの前記動きベクトル候補は、前記第１動きベクトル候補及び前記第２動きベクトル候補によって指し示された前記位置間の位置を指し示す、
請求項４に記載の装置。
【請求項６】
前記探索空間決定ユニットは、
少なくとも二つの動きベクトル候補がそれぞれ指し示す少なくとも二つの位置を含む領域の位置を決定するように構成され、前記少なくとも二つの位置は、前記第２探索空間のピクセル解像度において隣接し、
前記第１探索空間に属さない前記領域のこれらの位置として前記第２探索空間を決定するように構成される、
請求項１〜３の何れか一項に記載の装置。
【請求項７】
前記探索空間決定ユニットによって前記第１探索空間を前記決定することは、
前記動きベクトルの前記推定値によって指し示された位置に対して、前記第１探索空間のピクセル解像度において隣接する前記位置を指し示す前記動きベクトル及び動きベクトル候補の前記推定値を、前記第１探索空間に含めることを備える、
請求項１〜３の何れか一項、又は請求項６に記載の装置。
【請求項８】
前記探索空間決定ユニットは、
前記第１探索空間において特定される前記第１動きベクトル候補及び前記第２動きベクトル候補によって、指し示された前記位置に対して、前記第１探索空間の前記ピクセル解像度において隣接し、前記動きベクトルの前記推定値によって指し示された前記位置とは異なる前記位置を指し示す動きベクトル候補を、前記第２探索空間の第１動きベクトル候補として選択するように構成される、
請求項７に記載の装置。
【請求項９】
前記探索空間決定ユニットは、
前記動きベクトルの前記推定値と前記第２探索空間の前記第１動きベクトル候補とを接続する直線上にほぼ位置する、前記第２探索空間の解像度における、位置を指し示す動きベクトル候補を、前記第２探索空間の更なる動きベクトル候補として決定するように構成され、前記第２探索空間の前記ピクセル解像度は、前記第１探索空間の前記ピクセル解像度より高い、
請求項８に記載の装置。
【請求項１０】
前記第２探索空間の前記更なる動きベクトル候補は、前記第２探索空間の前記第１動きベクトル候補及び前記動きベクトルの前記推定値によって指し示された前記位置間にある位置を指し示す、
請求項９に記載の装置。
【請求項１１】
前記第２探索空間は、前記第１探索空間より高い解像度を有する、
請求項１〜１０の何れか一項に記載の装置。
【請求項１２】
前記現在のブロックに隣接する少なくとも一つのブロックの動きベクトルを含む動きベクトルのリストから前記動きベクトルの前記推定値を決定するための動きベクトル決定ユニットを
さらに備える、請求項１〜１１の何れか一項に記載の装置。
【請求項１３】
ビットストリームから複数の画像をデコードするためのビデオデコーダであって、
前記ビットストリームから前記動きベクトルの前記推定値の指示を取得するためのビットストリームパーサーと、
請求項１〜１２の何れか一項に記載の装置を含み、前記現在のブロックの前記動きベクトルが指し示す予測ブロックを決定するようにさらに構成されたインター予測ユニットと、
前記予測ブロックに基づいて、前記現在のブロックを再構築するための再構築ユニットと
を備える、ビデオデコーダ。
【請求項１４】
複数の画像をビットストリームにコード化するためのビデオエンコーダであって、
請求項１〜１２の何れか一項に記載の前記装置を含み、前記現在のブロックの前記動きベクトルが指し示す予測ブロックを決定するようにさらに構成されたインター予測ユニットと、
前記ビットストリームに前記動きベクトルの前記推定値の指示を含めるためのビットストリームフォーマーと、
前記予測ブロックに基づいて、前記現在のブロックを再構築し、メモリに再構築された前記ブロックを記憶するための再構築ユニットと
を備える、ビデオエンコーダ。
【請求項１５】
映像フレームの現在のブロックのインター予測に用いられる動きベクトルを決定するための方法であって、前記方法は、
前記動きベクトルの推定値を取得する段階と、
前記推定値に基づいて、複数の動きベクトル候補を備える第１探索空間を決定する段階と、
コスト関数に従って、前記第１探索空間においる第１及び第２動きベクトル候補を選択する段階と、
前記第１動きベクトル候補及び前記第２動きベクトル候補に基づいて、１つ又は複数の動きベクトル候補を備える第２探索空間を決定する段階と、
前記第１探索空間及び前記第２探索空間の前記動きベクトル候補の中から前記現在のブロックのための前記動きベクトルを選択する段階と
を備える、方法。
【請求項１６】
コンピュータに請求項１５に記載の方法を実行させるためのプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
例えば、探索空間決定ユニットは、第２探索空間の更なる動きベクトル候補として、動きベクトルの推定値と第２探索空間の第１動きベクトル候補とを接続する直線上にほぼ位置する第２探索空間の解像度における位置を指し示す動きベクトル候補を選択するようにさらに構成され、第２探索空間のピクセル解像度は、第１探索空間のピクセル解像度より高い。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
例えば、第２探索空間の更なる少なくとも１つの動きベクトル候補として、動きベクトル候補は、動きベクトルの推定値と第２探索空間の第１動きベクトル候補とを接続する直線上にほぼ位置する第２探索空間の解像度における位置を指し示すように決定される。ここに、第２探索空間のピクセル解像度は、第１探索空間のピクセル解像度より高い。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１３５
【補正方法】変更
【補正の内容】
【０１３５】
しかしながら、第２探索空間の更なる少なくとも１つの動きベクトル候補として、第２探索空間の解像度における位置を指し示す動きベクトル候補が、決定されてもよい。この少なくとも一つの更なる動きベクトル候補は、動きベクトルの推定値と第２探索空間の第１動きベクトル候補とを接続する直線上にほぼ配置された第２探索空間の解像度における位置を指し示す。第２探索空間のピクセル解像度は、第１探索空間のピクセル解像度より高くてもよい。第２探索空間の更なる動きベクトル候補は、第２探索空間の第１動きベクトル候補、及び動きベクトルの推定値によって指し示された位置間に配置された位置を指し示してもよい。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１５５
【補正方法】変更
【補正の内容】
【０１５５】
発明が動画ビデオコーディングのフレームワーク内で主に上述されたが、提案された技術は、２つ以上の画像を備える任意の画像セットのコーディング（すなわち、コード化又はデコード）のために同様に適用できる。画像セットは、例えば、コンピュータ断層撮影（ＣＴ）スキャン画像のシーケンスなどの医療撮像アプリケーションにおいて、取得される、例えば、静止画像のセットを含んでよい。添付の請求項では、「ビデオ」との用語は、故に、動画シーケンス、又は２つ以上の画像を含む任意の他の画像セットを意味してもよい。非一時的なコンピュータ可読媒体は、プロセッサによって実行されるとき、項目１５に記載の方法を実行させる命令を備える。
【国際調査報告】
2020526112.tif 000028
2020526112.tif 000029