JP7024099B2 - ビデオ動き推定方法、装置、端末、及び記憶媒体 - Google Patents

Description

本願は、２０１８年３月７日に中国特許庁に提出された、出願番号が２０１８１０１８８５５６．６であり、発明の名称が「ビデオ動き推定方法、装置、及び記憶媒体」である中国特許出願の優先権を主張し、そのすべての内容は参照することにより本願に組み込まれる。

本願は、ビデオ圧縮の技術分野に関し、具体的には、ビデオ動き推定方法、装置、端末、及び記憶媒体に関する。

ビデオを符号化する過程では、通常、ビデオの各フレームの画像に対してフレーム間予測を行う必要がある。ここで、フレーム間予測は、主に、ビデオの時間領域での相関性を利用して、隣接する符号化された画像の画素から現在画像の画素を予測することで、ビデオの時間領域での冗長性を効果的に除去するという目的を達成する。現在、ビデオ符号化のフレーム間予測は、主にブロックベースの動き補償技術を使用しており、その原理は、現在画像の各画素ブロック（即ち予測単位）に対して、以前に符号化された画像から最適なマッチングブロックを見つけることであり、この過程は、動き推定（ＭＥ：Ｍｏｔｉｏｎ Ｅｓｔｉｍａｔｉｏｎ）と呼ばれる。ここで、予測に使用される画像は、参照画像と呼ばれ、参照画像の参照ブロックから現在画像の現在画素ブロックへの変位は、動きベクトル（ＭＶ：Ｍｏｔｉｏｎ Ｖｅｃｔｏｒ）と呼ばれる。

従来技術では、ビデオの画像フレームに対して動き推定を行う過程において、まず、フレーム間予測単位（ＰＵ：Ｐｒｅｄｉｃｔｉｏｎ Ｕｎｉｔ）で、画像フレームを２Ｎ×２Ｎ、２Ｎ×Ｎ、Ｎ×２Ｎ、２Ｎ×ｎＵ、２Ｎ×ｎＤ、ｎＬ×２Ｎ、及びｎＲ×２Ｎなどのモードの予測単位に分割する。次に、すべての予測単位に対して統一的な処理方式を採用し、各予測単位の探索開始点を決定した後、それぞれ、探索開始点を中心として、レート歪みコストが最小となる点を探索範囲内で探索し、最後に、各予測単位の、レート歪みコストが最小となる点の位置を各予測単位に対応する動きベクトルとし、各予測単位に対応する動きベクトルに基づいて、画像フレームに対して小数画素動き補償などの後続の処理を行う。

本願の発明者は、従来技術を研究・実施する過程において、従来技術では、すべての予測単位に対して同じ処理方式を統一的に採用しており、予測単位ごとに新たな独立した探索を行い、例えば、すべての予測単位に対して同じ複雑さの探索方法を採用するため、ビデオの動き推定の過程の柔軟性が不十分になり、動き推定の効率が低いことを見出した。

本願による各実施例によれば、ビデオ動き推定方法が提供されている。

ビデオ動き推定方法であって、
ビデオの画像フレームを複数の予測単位に分割し、前記複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分するステップと、
第１探索アルゴリズムによって前記第１タイプの予測単位の動きベクトルを取得するステップと、
第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得するステップであって、前記第２探索アルゴリズムが前記第１探索アルゴリズムと異なる、ステップと、
第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、前記画像フレームに対して小数画素動き推定を行うステップと、を含む。

ビデオ動き推定装置であって、
ビデオの画像フレームを複数の予測単位に分割し、前記複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分する分割ユニットと、
第１探索アルゴリズムによって前記第１タイプの予測単位の動きベクトルを取得する第１取得ユニットと、
第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得する第２取得ユニットであって、前記第２探索アルゴリズムが前記第１探索アルゴリズムと異なる、第２取得ユニットと、
第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、前記画像フレームに対して小数画素動き推定を行う動き推定ユニットと、を備える。

メモリと、１つ又は複数のプロセッサとを備える端末であって、前記メモリには、コンピュータ可読命令が記憶され、前記コンピュータ可読命令は、前記プロセッサにより実行されると、前記１つ又は複数のプロセッサに、
ビデオの画像フレームを複数の予測単位に分割し、前記複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分するステップと、
第１探索アルゴリズムによって前記第１タイプの予測単位の動きベクトルを取得するステップと、
第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得するステップであって、前記第２探索アルゴリズムが前記第１探索アルゴリズムと異なる、ステップと、
第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、前記画像フレームに対して小数画素動き推定を行うステップと、を実行させる。

コンピュータ可読命令を記憶した１つ又は複数の不揮発性記憶媒体であって、コンピュータ可読命令は、１つ又は複数のプロセッサにより実行されると、１つ又は複数のプロセッサに、
ビデオの画像フレームを複数の予測単位に分割し、前記複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分するステップと、
第１探索アルゴリズムによって前記第１タイプの予測単位の動きベクトルを取得するステップと、
第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得するステップであって、前記第２探索アルゴリズムが前記第１探索アルゴリズムと異なる、ステップと、
第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、前記画像フレームに対して小数画素動き推定を行うステップと、を実行させる。

本願の実施例の構成をより明確に説明するために、以下、実施例の説明に必要な図面を簡単的に紹介する。明らかに、以下の説明における図面は本願のいくつかの実施例を示しているにすぎず、当業者にとって、創造的な労働をせずに、これらの図面から他の図面を得ることもできる。
本願の実施例で提供されたビデオ動き推定システムのシナリオ模式図である。 本願の実施例で提供されたビデオ動き推定方法のフローの模式図である。 本願の実施例で提供された、画像フレームを分割してなる予測単位の模式図である。 本願の実施例で提供された菱形探索テンプレートの模式図である。 本願の実施例で提供された未確定点の周囲で２点探索を行う場合の模式図である。 本願の実施例で提供された所定間隔であるステップサイズで探索を行う場合の模式図である。 本願の実施例で提供された四角形モデルを移動させる場合の模式図である。 本願の実施例で提供された六角形モデルを移動させる場合の模式図である。 本願の実施例で提供された異なる予測単位の動きベクトルの探索順番の模式図である。 本願の実施例で提供された第１タイプの予測単位の動きベクトルを探索するフローの模式図である。 本願の実施例で提供された第２タイプの予測単位の動きベクトルを探索するフローの模式図である。 本願の実施例で提供されたビデオ動き推定装置の構成の模式図である。 本願の実施例で提供されたビデオ動き推定装置の別の構成の模式図である。 本願の実施例で提供されたビデオ動き推定装置の別の構成の模式図である。 本願の実施例で提供された端末の構成の模式図である。

以下、本願の実施例の図面を参照しながら、本願の実施例の構成を明確かつ完全に説明するが、明らかなように、説明する実施例は、本願のいくつかの実施例にすぎず、すべての実施例ではない。当業者が創造的な労働をせずに本願の実施例から得るすべての他の実施例は、本願の保護範囲に属する。

本願の実施例では、ビデオ動き推定方法、装置、及びシステムが提供されている。

図１を参照されたいが、図１は、本願の実施例で提供されたビデオ動き推定システムのシナリオ模式図である。該ビデオ動き推定システムは、ビデオ動き推定装置を備えてもよい。該ビデオ動き推定装置は、具体的には、タブレットコンピュータ、携帯電話、ノートブックコンピュータ、デスクトップコンピュータやテレビなど、記憶ユニットを備えるとともに、マイクロプロセッサを搭載して演算能力を持っている端末に統合されてもよく、主に、ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分すること、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得すること、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得すること、次に、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行うことにより、動き推定結果を取得することなどに用いられる。ここで、該ビデオは、端末のローカルから取得されてもよいし、サーバーからダウンロードされてもよい。該予測単位は、予測単位Ａ、予測単位Ｂ、予測単位Ｃ、予測単位Ｄ、予測単位Ｅ、及び予測単位Ｆなどの複数の予測単位を含んでもよい。該第１タイプの予測単位は、予測単位Ａ、予測単位Ｂ、予測単位Ｃなどの複数の予測単位を含んでもよく、第２タイプの予測単位は、予測単位Ｄ、予測単位Ｅ、及び予測単位Ｆなどの複数の予測単位を含んでもよい。第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得する過程では、ポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得してもよい。ここで、該ポリゴンモデルは、菱形又は六角形などのポリゴンモデルであってもよい。第１タイプの予測単位の動きベクトルａ及び第２タイプの予測単位の動きベクトルｂを取得した後、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得してもよい。ここで、探索済み予測単位は、第１タイプの予測単位及び第２タイプの予測単位のうちの少なくとも１つの予測単位を含んでもよい。

また、該ビデオ動き推定システムは、サーバーをさらに備えてもよい。ビデオ動き推定装置は、サーバーからビデオをダウンロードしてもよい。例えば、ビデオ動き推定装置は、サーバーにビデオ取得要求を送信し、この取得要求に応じてサーバーからフィードバックされた、該ビデオに関するビデオファイルなどを受信してもよい。

説明すべきものとして、図１に示すビデオ動き推定システムのシナリオ模式図は一例にすぎず、本願の実施例で説明するビデオ動き推定システム及びシナリオは、本願の実施例の構成をより明確に説明するためのものであり、本願の実施例で提供された構成を限定するものではない。当業者であれば分かるように、ビデオ動き推定システムの進化及び新しいビジネスシナリオの出現に伴い、本願の実施例で提供された構成は、類似した技術的課題にも適用できる。

以下、詳細についてそれぞれ説明する。

本実施例では、ビデオ動き推定装置の観点から説明するが、該ビデオ動き推定装置は、具体的には、コンピュータ、携帯電話やテレビなど、記憶ユニットを備えるとともに、マイクロプロセッサを搭載して演算能力を持っている端末に統合されてもよい。

ビデオ動き推定方法であって、ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分するステップと、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得するステップと、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得するステップと、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行うステップと、を含む。

図２を参照されたいが、図２は、本願の第１実施例で提供されたビデオ動き推定方法のフローの模式図である。該ビデオ動き推定方法は、以下のステップを含んでもよい。

ステップＳ１０１で、ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分する。

ビデオ動き推定装置は、ローカル又はサーバーからビデオを取得してもよい。このビデオを符号化する必要がある場合、ビデオに対してフレーム間予測符号化を行う必要がある。フレーム間予測符号化の過程では、ビデオの各画像フレームに対して動き推定を行う必要がある。画像フレームに対して動き推定を行う際に、フレーム間予測単位（ＰＵ）で、ビデオの画像フレームを２Ｎ×２Ｎ、２Ｎ×Ｎ、Ｎ×２Ｎ、２Ｎ×ｎＵ、２Ｎ×ｎＤ、ｎＬ×２Ｎ、及びｎＲ×２Ｎなどの複数の予測単位に分割してもよい。ここで、図３に示すように、２Ｎ×２Ｎ、２Ｎ×Ｎ、及びＮ×２Ｎなどは、対称モードの予測単位であり、例えば、２Ｎ×Ｎの予測単位は、１：１の上下比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含み、２Ｎ×ｎＵ、２Ｎ×ｎＤ、ｎＬ×２Ｎ、及びｎＲ×２Ｎなどは、非対称モードの予測単位であり、例えば、２Ｎ×ｎＤの予測単位は、３：１の上下比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含む。

異なるモードの予測単位には違いが存在するので、異なるモードの予測単位に対してすべて同じ処理方式を統一的に採用し、例えば、非対称モードの予測単位に対して対称モードの予測単位と同じ複雑さの探索方法を採用することを回避するために、ビデオの動き推定の柔軟性及び効率を向上させるように、複数の予測単位を取得した後、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分してもよい。例えば、該第１タイプの予測単位は、２Ｎ×２Ｎ、２Ｎ×Ｎ、及びＮ×２Ｎなどの対称モードの予測単位を含んでもよく、第２タイプの予測単位は、２Ｎ×ｎＵ、２Ｎ×ｎＤ、ｎＬ×２Ｎ、及びｎＲ×２Ｎなどの非対称モードの予測単位を含んでもよい。

理解できるように、予測単位の分割方式、及び第１タイプの予測単位と第２タイプの予測単位との区分方式は、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な内容を限定しない。

説明すべきものとして、本願の実施例で使用している「第１」及び「第２」などの用語は、説明の目的のみのためであり、示され又は示唆される重要性と理解するわけにはいかない。例えば、第１タイプの予測単位及び第２タイプの予測単位は、いずれも予測単位であり、第１タイプの予測単位が、あるタイプの予測単位に対応し、第２タイプの予測単位が、別のタイプの予測単位に対応するが、第１タイプの予測単位の重要性が第２タイプの予測単位の重要性よりも高いことを意味するものではない。

ステップＳ１０２で、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得する。

第１タイプの予測単位及び第２タイプの予測単位に対して、ビデオ動き推定装置は、それぞれ異なる探索アルゴリズムを用いて、予測単位の動きベクトルを探索してもよい。例えば、第１タイプの予測単位の場合、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得してもよく、第２タイプの予測単位の場合、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得してもよい。ここで、第１探索アルゴリズムと第２探索アルゴリズムとは異なる。以下、詳しく説明する。

いくつかの実施形態では、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得するステップは、
第１タイプの予測単位に対応する第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定するステップ（１）と、
第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップ（２）と、
第２未確定点に対応する探索ステップサイズが第２所定ステップサイズである場合、ステップサイズが第２所定ステップサイズである各点の周囲にある未探索の第２補足点を取得し、第２補足点のレート歪みコストを算出するステップ（３）と、
第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点である場合、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定するステップ（４）と、
第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点ではない場合、第２未確定点及び第２補足点のうちレート歪みコストが最小となる点の位置を第１タイプの予測単位の動きベクトルとして設定するステップ（５）と、を含んでもよい。

具体的には、まず、ビデオ動き推定装置は、探索開始点（即ち、第２探索開始点）を決定する。具体的には、以下のようにしてもよい。

ビデオ動き推定装置は、高度動きベクトル予測（ＡＭＶＰ：Ａｄｖａｎｃｅｄ Ｍｏｔｉｏｎ Ｖｅｃｔｏｒ Ｐｒｅｄｉｃｔｉｏｎ）で、第１タイプの予測単位に対応する第２候補探索開始点を取得してもよい。ここで、ＡＭＶＰ技術は、主に、空間領域及び時間領域での動きベクトルの相関性を利用して、現在の予測単位のために候補予測ＭＶリストを作成し、該リストには複数の候補予測ＭＶがある。ビデオ動き推定装置は、複数の候補予測ＭＶリストから第２候補探索開始点を選択してもよい。もしくは、ビデオ動き推定装置は、Ｍｅｒｇｅモードで、第１タイプの予測単位に対応する第２候補探索開始点を取得してもよい。

第２候補探索開始点を取得した後、ビデオ動き推定装置は、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２開始点探索点として設定してもよい。つまり、この第２探索開始点は、第１タイプの予測単位に対応する、最終的に決定された探索開始点である。レート歪みコストの計算式は、ｒｄｃｏｓｔ＝ｓａｄ＋ｌａｍｂｄａ＊ｂｉｔであってもよい。ここで、ｒｄｃｏｓｔはレート歪みコストを表し、ｓａｄは残差、即ち、動き補償予測誤差を表し、ｌａｍｂｄａは定数係数を表し、ラグランジュ乗数であってもよく、ｂｉｔはビットレート、即ち、動きベクトルに関する情報の符号化ビット数を表す。説明すべきものとして、以下の各レート歪みコストの算出方式は、この式を参照して算出してもよい。

次に、ビデオ動き推定装置は、探索ウィンドウの範囲内で未確定点（即ち、第２未確定点）を探索する。具体的には、以下のようにしてもよい。

ビデオ動き推定装置は、菱形テンプレート又は正方形テンプレートなどを使用して探索を行ってもよい。図４に示すように、菱形テンプレートを例にすると、第２探索開始点を菱形テンプレートの中心として、１である探索ステップサイズから始め、図４に示す菱形テンプレートに従って、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得する。ここで、第２所定インクリメンタルステップサイズは、２の整数乗のようにインクリメンタルするステップサイズであってもよい。つまり、まず、１である探索ステップサイズから始め、次に２、４、及び８などである探索ステップサイズで順次に探索を行うことにより、複数の第２候補点を取得する。この第２候補点は、図４でマークされた五芒星の位置のように、各探索ステップサイズに対応する菱形テンプレートの頂点、及び２つの頂点の間の中点などであってもよい。ここで、例えば、最大探索ステップサイズが８に設定されている場合、対応する探索ウィンドウの範囲は、８である探索ステップサイズに対応する菱形テンプレートの内側の環状領域であり、最大探索ステップサイズが１６に設定されている場合、対応する探索ウィンドウの範囲は、１６である探索ステップサイズに対応する菱形テンプレートの内側の環状領域である。次に、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別し、複数の第２候補点のうちレート歪みコストが最小となる点を第２未確定点として設定する。

次に、第２未確定点に対応する探索ステップサイズが第２所定ステップサイズである場合、未確定点の周囲で２点探索を行う。具体的には、以下のようにしてもよい。

第２未確定点を取得した後、ビデオ動き推定装置は、該第２未確定点に対応する探索ステップサイズが第２所定ステップサイズであるか否かを判断してもよい。該第２所定ステップサイズは、実際のニーズに応じて柔軟に設定してもよい。例えば、第２所定ステップサイズを１に設定してもよい。つまり、第２未確定点に対応する探索ステップサイズが１である場合、ステップサイズが第２所定ステップサイズである各点の周囲にある未探索の第２補足点を取得してもよい。該第２補足点は、図５に示すように、１つ又は複数の点を含んでもよい。

例えば、図５において、第２未確定点を探索するための探索テンプレートが菱形テンプレートである場合、取得された第２未確定点に対応する探索ステップサイズが１であれば、探索ステップサイズが１である菱形に対応する頂点は、点２、点４、点５、点７という４つの点である。この場合、取得された、レート歪みコストが最小となる第２未確定点が点２の位置であると、点２の位置に対して点Ａ、点Ｂという２つの点を補足し、点Ａ、点Ｂという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点４の位置であると、点４の位置に対して点Ｃ、点Ｅという２つの点を補足し、点Ｃ、点Ｅという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点５の位置であると、点５の位置に対して点Ｄ、点Ｆという２つの点を補足し、点Ｄ、点Ｆという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点７の位置であると、点７の位置に対して点Ｇ、点Ｈという２つの点を補足し、点Ｇ、点Ｈという２つの点を第２補足点として設定してもよい。

最後に、第２補足点及び第２未確定点の中から、レート歪みコストが最小となる点を選別する。具体的には、以下のようにしてもよい。

第２補足点を取得した後、ビデオ動き推定装置は、各第２補足点のレート歪みコストを算出し、第２補足点のレート歪みコストを第２未確定点のレート歪みコストと比較し、第２補足点及び第２未確定点のうちレート歪みコストが最小となる点が第２未確定点であるか否かを判断してもよい。第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点である場合、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定する。

第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点ではない場合、第２未確定点及び第２補足点のうちレート歪みコストが最小となる点の位置を第１タイプの予測単位の動きベクトルとして設定する。

任意選択的に、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定するステップは、
画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第１タイプの予測単位における対応位置の第２目標レート歪みコストを算出するステップ（ａ）と、
第２未確定点のレート歪みコストを第２目標レート歪みコストと比較するステップ（ｂ）と、
第２未確定点のレート歪みコストが第２目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第１タイプの予測単位の動きベクトルとして設定するステップ（ｃ）と、
第２未確定点のレート歪みコストが第２目標レート歪みコスト以下である場合、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定するステップ（ｄ）と、を含んでもよい。

ビデオ動き推定装置は、第１タイプの予測単位の動きベクトルを決定するにあたって、画像フレームの探索済み予測単位の動きベクトルに基づいて、探索中の第１タイプの予測単位の動きベクトルを補正してもよい。具体的には、ビデオ動き推定装置は、各予測単位の動きベクトルの探索過程において、探索済み予測単位の動きベクトルを記憶してもよく、予測単位の識別子と動きベクトルとのマッピング関係を生成してもよい。

探索中の第１タイプの予測単位の動きベクトルを補正する過程において、ビデオ動き推定装置は、探索済み予測単位の識別子に対応するマッピング関係を取得し、該マッピング関係に基づいて、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第１タイプの予測単位における対応位置の第２目標レート歪みコストを算出してもよい。例えば、探索済み予測単位の動きベクトルに基づいて、その指す先の対応位置を決定し、この対応位置のレート歪みコストを算出し、算出されたこの対応位置のレート歪みコストを第２目標レート歪みコストとして設定してもよい。次に、第２未確定点のレート歪みコストを第２目標レート歪みコストと比較してもよい。

第２未確定点のレート歪みコストが第２目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第１タイプの予測単位の動きベクトルとして設定し、即ち、第１タイプの予測単位の動きベクトルを探索済み予測単位の動きベクトルに補正する。第２未確定点のレート歪みコストが第２目標レート歪みコスト以下である場合、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定する。

説明すべきものとして、探索済み予測単位は、１つ又は複数の予測単位を含んでもよい。該探索済み予測単位は、画像フレームの第１タイプの予測単位のうちの１つ又は複数の予測単位を含んでもよく、又は画像フレームの第２タイプの予測単位のうちの１つ又は複数の予測単位を含んでもよく、又は画像フレームの第１タイプの予測単位のうちの１つ又は複数の予測単位も画像フレームの第２タイプの予測単位のうちの１つ又は複数の予測単位も含んでもよい。このように類推して、探索済み予測単位の動きベクトルも１つ又は複数であってもよい。

例えば、ビデオ動き推定装置が２Ｎ×２Ｎの予測単位及び２Ｎ×Ｎの予測単位の動きベクトルの探索を既に完了した場合、現在Ｎ×２Ｎの予測単位の動きベクトルを探索する際に、２Ｎ×２Ｎの予測単位及び２Ｎ×Ｎの予測単位の動きベクトルを用いて、Ｎ×２Ｎの予測単位の動きベクトルを補正してもよい。

任意選択的に、第１タイプの予測単位は、第３分割ブロックと第４分割ブロックとを含み、第１タイプの予測単位に対応する第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定するステップは、
高度動きベクトル予測で第１タイプの予測単位の第４分割ブロックに対応する少なくとも１つの第２候補探索開始点を取得するステップと、
第１タイプの予測単位の第３分割ブロックの予測が完了すると、第３分割ブロックの予測結果を取得し、各第２候補探索開始点のレート歪みコストを算出し、第３分割ブロックの予測結果に基づいて、前記第３分割ブロックの位置のレート歪みコストを算出するステップと、
少なくとも１つの第２候補探索開始点及び第３分割ブロックのうち、レート歪みコストが最小となる点を第１タイプの予測単位の第４分割ブロックの探索開始点として設定し、第４分割ブロックの探索開始点を第２探索開始点として設定するステップと、を含んでもよい。

説明すべきものとして、上記第１タイプの予測単位は、インデックス０の第３分割ブロックと、インデックス１の第４分割ブロックとを含んでもよい。ビデオ動き推定装置は、第１タイプの予測単位の第３分割ブロック及び第４分割ブロックの動きベクトルをそれぞれ探索してもよい。第１タイプの予測単位の第４分割ブロックの探索開始点を決定する際に、探索済みの第３分割ブロックの動きベクトルを参考にして、現在の第４分割ブロックの探索過程を指導してもよい。つまり、探索済みの第３分割ブロックの動きベクトルに対応する位置を現在の第４分割ブロックの候補探索開始点の１つとしてもよい。又は、探索済みの第４分割ブロックの動きベクトルに対応する位置を現在の第３分割ブロックの候補探索開始点の１つとする。以下、探索済みの第３分割ブロックの動きベクトルに対応する位置を現在の第４分割ブロックの探索開始点の１つとする場合を例にして説明する。

具体的には、ビデオ動き推定装置は、第１タイプの予測単位の第４分割ブロックの探索過程において、ＡＭＶＰ技術で第１タイプの予測単位の第４分割ブロックに対応する少なくとも１つの第２候補探索開始点を取得し、第１タイプの予測単位の第３分割ブロックの探索が完了したか否かを判断し、つまり、第１タイプの予測単位の第３分割ブロックの予測が完了したか否かを判断してもよい。第１タイプの予測単位の第３分割ブロックの予測が完了した場合、第３分割ブロックの予測結果を取得する。該予測結果は、第３分割ブロックの動きベクトルであってもよい。このとき、第３分割ブロックの予測結果に基づいて、第３分割ブロックの位置のレート歪みコストを算出し、つまり、第３分割ブロックの動きベクトルに基づいて、第３分割ブロックの位置のレート歪みコストを算出してもよい。例えば、第３分割ブロックの動きベクトルに基づいて、その指す先の対応位置を決定し、この対応位置のレート歪みコストを算出し、算出されたこの対応位置のレート歪みコストを第３分割ブロックの位置のレート歪みコストとして設定してもよい。また、各第２候補探索開始点のレート歪みコストを算出し、少なくとも１つの第２候補探索開始点及び第３分割ブロックのうち、レート歪みコストが最小となる点を第１タイプの予測単位の第４分割ブロックの探索開始点として設定し、第４分割ブロックの探索開始点を第２探索開始点として設定する。これにより、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップを実行する。

例えば、２Ｎ×Ｎの予測単位を例にすると、２Ｎ×Ｎの予測単位のインデックス０の分割ブロックの予測が完了したとすれば、２Ｎ×Ｎの予測単位のインデックス１の分割ブロックの予測を行う際に、インデックス０の分割ブロックに対応する予測結果のうちの動きベクトルに対応する位置を、インデックス１の分割ブロックの候補探索開始点の位置の１つとしてもよい。これにより、候補探索開始点の中から、レート歪みコストが最小となる点を探索開始点として選択することができ、このようにして、探索開始点を動き推定の最適位置により近くし、探索過程をより迅速に終了させることができる。

いくつかの実施形態では、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップの後、ビデオ動き推定方法は、
第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内である場合、第２未確定点を中心とする所定範囲内で、所定間隔であるステップサイズで探索を行うことにより、複数の探索点を取得し、各探索点のレート歪みコストを算出するステップと、
第２未確定点及び複数の探索点のうちレート歪みコストが最小となる点を第２探索開始点とし、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップに戻るステップと、をさらに含んでもよい。

具体的には、第２未確定点を取得した後、ビデオ動き推定装置は、該第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第３所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよい。又は、レート歪みコストが最小となる点から探索ウィンドウの範囲の中心までの距離を取得し、該距離が第１所定距離閾値の範囲内であるか否かを判断してもよい。該第１所定距離閾値の範囲は、実際のニーズに応じて柔軟に設定してもよい。例えば、該第１所定距離閾値の範囲は、５以上かつ８以下であってもよい。第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内である（又は、レート歪みコストが最小となる点から探索ウィンドウの範囲の中心までの距離が第１所定距離閾値の範囲内である）場合、第２未確定点を中心とする所定範囲内で、所定間隔であるステップサイズで探索を行うことにより、複数の探索点を取得する。ここで、所定範囲、及び所定間隔であるステップサイズは、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な値を限定しない。例えば、該所定間隔であるステップサイズは、各行及び各列に５ステップ分の間隔を置くように設定してもよい。図６に示すように、第２未確定点を中心とする探索ウィンドウの範囲内で、ラスター走査方式によって５行５列おきにすべての点を走査することにより、複数の探索点を取得する。図６は、探索ウィンドウの範囲内で、所定間隔であるステップサイズで探索を行う場合の部分的な模式図だけであり、該探索ウィンドウの範囲は、実際のニーズに応じて柔軟に設定してもよく、例えば、１２８行×１２８列であってもよい。

次に、各探索点のレート歪みコストを算出し、第２未確定点及び複数の探索点のうちレート歪みコストが最小となる点を第２探索開始点とし、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップに戻る。

いくつかの実施形態では、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップの後、ビデオ動き推定方法は、
第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内である場合、第２未確定点を第２探索開始点とし、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップに戻るステップをさらに含んでもよい。

具体的には、第２未確定点を取得した後、ビデオ動き推定装置は、該第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第４所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよい。又は、レート歪みコストが最小となる点から探索ウィンドウの範囲の中心までの距離を取得し、該距離が第２所定距離閾値の範囲内であるか否かを判断してもよい。該第２所定距離閾値の範囲は、実際のニーズに応じて柔軟に設定してもよく、例えば、１より大きくかつ５未満であってもよい。第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内である（又は、レート歪みコストが最小となる点から探索ウィンドウの範囲の中心までの距離が第１所定距離閾値の範囲内である）場合、第２未確定点を第２探索開始点とし、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップに戻る。

ステップＳ１０３で、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得する。

第２タイプの予測単位に対して、ビデオ動き推定装置は、第２探索アルゴリズムを用いて第２タイプの予測単位の動きベクトルを取得してもよい。

いくつかの実施形態では、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得するステップは、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得するステップと、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得するステップと、を含んでもよい。

ここで、いくつかの実施形態では、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得するステップは、
第２探索アルゴリズムによって、第２タイプの予測単位における第１未確定点を取得するステップ（１）と、
第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得し、ポリゴンモデルに基づいて第１目標点を取得するステップ（２）と、
第１目標点が第１未確定点と一致しない場合、ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得するステップ（３）と、
最適点が第１目標点と一致する場合、最適点の位置を第２タイプの予測単位の現在動きベクトルとして設定するステップ（４）と、を含んでもよい。

具体的には、ビデオ動き推定装置は、ＡＭＶＰ技術で第２タイプの予測単位に対応する第１候補探索開始点を取得し、第１候補探索開始点の中から第１探索開始点を選別し、次に、第１探索開始点を菱形テンプレート又は正方形テンプレートの中心として探索を行うことにより、複数の第１候補点を取得し、複数の第１候補点の中から第１未確定点を選別してもよい。

第１未確定点を取得した後、ビデオ動き推定装置は、該第１未確定点に対応する探索ステップサイズが第１所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第１所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよい。第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、ポリゴンモデルを取得する。ここで、該ポリゴンモデルは、四角形又は六角形などであってもよい。

ポリゴンモデルを取得した後、ビデオ動き推定装置は、ポリゴンモデルに基づいて第１目標点を取得してもよい。例えば、ビデオ動き推定装置は、ポリゴンモデルの中心及び各々の頂点の位置のレート歪みコストを算出し、ポリゴンモデルの中心及び各々の頂点のうちレート歪みコストが最小となる点を第１目標点として設定してもよい。

第１目標点を取得した後、ビデオ動き推定装置は、該第１目標点が第１未確定点と一致するか否かを判断してもよい。第１目標点が第１未確定点と一致しない場合は、取得された第１目標点が最適点ではない可能性があり、第１目標点の周囲には、レート歪みコストが第１目標点のレート歪みコストよりも小さい最適点が存在する可能性があることを示す。この場合、ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得する。該最適点は、移動させたポリゴンモデルのうちレート歪みコストが最小となる点であってもよい。

任意選択的に、第１目標点が第１未確定点と一致しない場合、ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得するステップは、第１目標点が第１未確定点と一致しない場合、ポリゴンモデルの中心を第１目標点の位置に移動させるステップと、移動させたポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最小となる点を選別することにより、最適点を取得するステップと、を含んでもよい。

該ポリゴンモデルは、移動後に元の形状が変わらないように維持される。例えば、ポリゴンモデルの中心を第１目標点の位置に移動させてもよい。次に、移動させたポリゴンモデルの中心及び各々の頂点の位置のレート歪みコストを算出し、移動させたポリゴンモデルの中心及び各々の頂点のうちレート歪みコストが最小となる点を最適点として設定する。

最適点を取得した後、ビデオ動き推定装置は、最適点が第１目標点と一致するか否かを判断し、最適点が第１目標点と一致する場合、最適点の位置を第２タイプの予測単位の現在動きベクトルとして設定してもよい。

任意選択的に、ポリゴンモデルに基づいて第１目標点を取得するステップの後、ビデオ動き推定方法は、第１目標点が第１未確定点と一致する場合、第１目標点の位置を第２タイプの予測単位の現在動きベクトルとして設定するステップをさらに含んでもよい。

例えば、図７に示すように、ポリゴンモデルが菱形モデルである場合、図７（ａ）において、菱形モデルの中心及び上下左右の各々の頂点のレート歪みコストを算出することにより取得された、レート歪みコストが最小となる点（即ち最適点）が菱形モデルの右頂点の位置であれば、図７（ｂ）に示すように、菱形モデルの中心を右頂点の位置に移動させる。このとき、移動させた菱形モデルの中心及び上下左右の各々の頂点のレート歪みコストを算出する。取得された、レート歪みコストが最小となる点が菱形モデルの下頂点の位置であれば、図７（ｃ）に示すように、菱形モデルの中心を下頂点の位置に移動させる。このとき、移動させた菱形モデルの中心及び上下左右の各々の頂点のレート歪みコストを算出する。取得された、レート歪みコストが最小となる点が菱形モデルの下頂点の位置であれば、図７（ｄ）に示すように、菱形モデルの中心を下頂点の位置に移動させる。このとき、移動させた菱形モデルの中心及び上下左右の各々の頂点のレート歪みコストを算出する。取得された、レート歪みコストが最小となる点が菱形モデルの中心の位置であれば、即ち、最適点が菱形モデルの中心の位置であれば、菱形モデルを移動させず、菱形モデルの中心の位置（即ち最適点の位置）を第２タイプの予測単位の現在動きベクトルとして設定する。

いくつかの実施形態では、第２探索アルゴリズムによって第２タイプの予測単位における第１未確定点を取得し、第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得し、ポリゴンモデルに基づいて第１目標点を取得するステップは、
第２探索アルゴリズムによって、第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップ（ａ）と、
第１未確定点に対応する探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得するステップ（ｂ）と、
ポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最小となる点を選択することにより、第１目標点を取得するステップ（ｃ）と、を含んでもよい。

具体的には、ビデオ動き推定装置は、ＡＭＶＰ技術で第２タイプの予測単位に対応する第１候補探索開始点を取得し、第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる点を第１探索開始点として設定し、次に、第１探索開始点を菱形テンプレート又は正方形テンプレートの中心として探索を行うことにより、複数の第１候補点を取得し、各第１候補点のレート歪みコストを算出し、複数の第１候補点の中から、レート歪みコストが最小となる点を選別し、レート歪みコストが最小となる点を第１未確定点として設定してもよい。

第１未確定点を取得した後、ビデオ動き推定装置は、該第１未確定点に対応する探索ステップサイズが第１所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第１所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよい。第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とする四角形又は六角形などのポリゴンモデルを取得する。

ポリゴンモデルを取得した後、ビデオ動き推定装置は、ポリゴンモデルの中心及び各々の頂点の位置のレート歪みコストを算出し、ポリゴンモデルの中心及び各々の頂点のうちレート歪みコストが最小となる点を第１目標点として設定してもよい。ビデオ動き推定装置は、ポリゴンモデルの中心、各々の頂点、及び各辺の中点の位置（又は各辺の三等分点の位置）のレート歪みコストを算出し、レート歪みコストが最小となる点を第１目標点として設定してもよい。

任意選択的に、第２探索アルゴリズムによって、第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップは、
第２探索アルゴリズムによって、第２タイプの予測単位に対応する第１候補探索開始点を取得するステップと、
各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定するステップと、
第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで取得するステップと、
複数の第１候補点の中から、レート歪みコストが最小となる点を選別することにより、第１未確定点を取得するステップと、を含んでもよい。

具体的には、ビデオ動き推定装置は、ＡＭＶＰ技術又はＭｅｒｇｅモードで、第２タイプの予測単位に対応する第１候補探索開始点を取得し、次に、各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定してもよい。即ち、該第１探索開始点は、第２タイプの予測単位に対応する、最終的に決定された探索開始点である。

第１探索開始点を取得した後、ビデオ動き推定装置は、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで探索してもよい。ここで、探索ウィンドウの範囲は、菱形テンプレート又は正方形テンプレートの探索範囲であってもよい。例えば、探索ウィンドウの範囲は、菱形テンプレート又は正方形テンプレートの最大探索ステップサイズに対応する内側の環状領域であってもよい。例えば、菱形テンプレートの最大探索ステップサイズが８に設定されている場合、対応する探索ウィンドウの範囲は、探索ステップサイズ８に対応する菱形テンプレートの内側の環状領域である。第１所定インクリメンタルステップサイズは、２の整数乗のようにインクリメンタルするステップサイズであってもよく、又は実際のニーズに応じて柔軟に設定してもよい。

菱形テンプレートを例にすると、図４に示すように、第１探索開始点を菱形テンプレートの中心とし、１である探索ステップサイズから始め、２の整数乗のようにインクリメンタルするステップサイズで探索を行うことにより、複数の第１候補点を取得する。この第１候補点は、図４でマークされた五芒星の位置のように、各探索ステップサイズに対応する菱形テンプレートの頂点、及び２つの頂点の間の中点などであってもよい。次に、各第１候補点のレート歪みコストを算出し、複数の第１候補点の中から、レート歪みコストが最小となる点を選別し、複数の第１候補点のうちレート歪みコストが最小となる点を第１未確定点として設定する。

いくつかの実施形態では、第２タイプの予測単位は、第１分割ブロックと第２分割ブロックとを含み、第２探索アルゴリズムによって、第２タイプの予測単位に対応する第１候補探索開始点を取得し、各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定するステップは、
第２探索アルゴリズムによって、高度動きベクトル予測で第２タイプの予測単位の第２分割ブロックに対応する少なくとも１つの第１候補探索開始点を取得するステップと、
第２タイプの予測単位の第１分割ブロックの予測が完了すると、第１分割ブロックの予測結果を取得し、各第１候補探索開始点のレート歪みコストを算出し、前記第１分割ブロックの予測結果に基づいて、前記第１分割ブロックの位置のレート歪みコストを算出するステップと、
少なくとも１つの第１候補探索開始点及び第１分割ブロックの中から、レート歪みコストが最小となる点を取得するステップと、
取得された、レート歪みコストが最小となる点を、第２タイプの予測単位の第２分割ブロックの探索開始点として設定し、第２分割ブロックの探索開始点を第１探索開始点として設定するステップと、を含んでもよい。

説明すべきものとして、上記第２タイプの予測単位は、インデックス０の第１分割ブロックと、インデックス１の第２分割ブロックとを含んでもよい。ビデオ動き推定装置は、第２タイプの予測単位の第１分割ブロック及び第２分割ブロックの動きベクトルをそれぞれ探索してもよい。第２タイプの予測単位の第２分割ブロックの探索開始点を決定する際に、探索済みの第１分割ブロックの動きベクトルを参考にして、現在の第２分割ブロックの探索過程を指導してもよい。つまり、探索済みの第１分割ブロックの動きベクトルに対応する位置を現在の第２分割ブロックの探索開始点の１つとしてもよい。又は、探索済みの第２分割ブロックの動きベクトルに対応する位置を現在の第１分割ブロックの候補探索開始点の１つとする。以下、探索済みの第１分割ブロックの動きベクトルに対応する位置を現在の第２分割ブロックの探索開始点の１つとする場合を例にして説明する。

具体的には、ビデオ動き推定装置は、第２タイプの予測単位の第２分割ブロックの探索過程において、ＡＭＶＰ技術で第２タイプの予測単位の第２分割ブロックに対応する少なくとも１つの第１候補探索開始点を取得し、第２タイプの予測単位の第１分割ブロックの探索が完了したか否かを判断し、つまり、第２タイプの予測単位の第１分割ブロックの予測が完了したか否かを判断してもよい。第２タイプの予測単位の第１分割ブロックの予測が完了した場合、第１分割ブロックの予測結果を取得する。該予測結果は、予測により取得された第１分割ブロックの動きベクトルであってもよい。第１分割ブロックの予測結果に基づいて、第１分割ブロックの位置のレート歪みコストを算出し、つまり、第１分割ブロックの動きベクトルに基づいて、第１分割ブロックの位置のレート歪みコストを算出してもよい。例えば、第１分割ブロックの動きベクトルに基づいて、その指す先の対応位置を決定し、この対応位置のレート歪みコストを算出し、算出されたこの対応位置のレート歪みコストを第１分割ブロックの位置のレート歪みコストとして設定してもよい。また、各第１候補探索開始点のレート歪みコストを算出し、少なくとも１つの第１候補探索開始点及び第１分割ブロックのうち、レート歪みコストが最小となる点を第２タイプの予測単位の第２分割ブロックの探索開始点として設定し、第２分割ブロックの探索開始点を第１探索開始点として設定する。これにより、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで探索し、各第１候補点のレート歪みコストを算出するステップを実行する。

例えば、ｎＲ×２Ｎの予測単位を例にすると、ｎＲ×２Ｎの予測単位のインデックス０の分割ブロックの予測が完了したとすれば、ｎＲ×２Ｎの予測単位のインデックス１の分割ブロックの予測を行う際に、インデックス０の分割ブロックに対応する予測結果のうちの動きベクトルの位置を、インデックス１の分割ブロックの候補探索開始点位置の１つとしてもよい。これにより、候補探索開始点の中から、レート歪みコストが最小となる点を探索開始点として選択することができ、このようにして、探索開始点を動き推定の最適位置により近くし、探索過程をより迅速に終了させることができる。

いくつかの実施形態では、第２探索アルゴリズムによって、第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップの後、ビデオ動き推定方法は、
第１未確定点に対応する探索ステップサイズが第１所定ステップサイズである場合、ステップサイズが第１所定ステップサイズである各点の周囲にある未探索の第１補足点を取得し、第１補足点のレート歪みコストを算出するステップと、
第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点である場合、第１未確定点の位置を第２タイプの予測単位の現在動きベクトルとして設定するステップと、
第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点ではない場合、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点の位置を第２タイプの予測単位の現在動きベクトルとして設定するステップと、をさらに含んでもよい。

具体的には、第１未確定点を取得した後、ビデオ動き推定装置は、該第１未確定点に対応する探索ステップサイズが第１所定ステップサイズであるか否かを判断してもよい。ここで、該第１所定ステップサイズは、実際のニーズに応じて柔軟に設定してもよい。例えば、第１所定ステップサイズを１に設定してもよい。つまり、第１未確定点に対応する探索ステップサイズが１の場合、ステップサイズが第１所定ステップサイズである各点の周囲にある未探索の第１補足点を取得してもよい。該第１補足点は、図５に示すように、１つ又は複数の点を含んでもよい。

例えば、図５において、第１未確定点を探索するための探索テンプレートが菱形テンプレートである場合、取得された第１未確定点に対応する探索ステップサイズが１であれば、探索ステップサイズが１である菱形に対応する頂点は、点２、点４、点５、点７という４つの点である。この場合、例えば、取得された、レート歪みコストが最小となる第１未確定点が点２の位置であると、点２の位置に対して点Ａ、点Ｂという２つの点を補足し、点Ａ、点Ｂという２つの点を第１補足点として設定してもよく、取得された、レート歪みコストが最小となる第１未確定点が点５の位置であると、点５の位置に対して点Ｄ、点Ｆという２つの点を補足し、点Ｄ、点Ｆという２つの点を第１補足点として設定してもよい。

第１補足点を取得した後、ビデオ動き推定装置は、第１補足点のレート歪みコストを算出し、第１補足点のレート歪みコストを第１未確定点のレート歪みコストと比較し、第１補足点及び第１未確定点のうちレート歪みコストが最小となる点が第１未確定点であるか否かを判断してもよい。第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点である場合、第１未確定点の位置を第２タイプの予測単位の現在動きベクトルとして設定する。第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点ではない場合、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点の位置を第２タイプの予測単位の現在動きベクトルとして設定する。

いくつかの実施形態では、第２探索アルゴリズムによって、第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップの後、ビデオ動き推定方法は、
第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内である場合、第１未確定点を第１探索開始点として設定し、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで探索するステップに戻るステップをさらに含んでもよい。

具体的には、第１未確定点を取得した後、ビデオ動き推定装置は、該第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第２所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよい。第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内である場合、第１未確定点を第１探索開始点として設定し、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで探索し、各第１候補点のレート歪みコストを算出するステップに戻る。

第２タイプの予測単位の現在動きベクトルを取得した後、ビデオ動き推定装置は、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて現在動きベクトルを補正してもよい。これにより、第２タイプの予測単位の動きベクトルを取得することができる。具体的には、以下のようにしてもよい。

第２タイプの予測単位の現在動きベクトルを取得した後、ビデオ動き推定装置は、画像フレームの探索済み予測単位の動きベクトルを取得してもよい。ここで、探索済み予測単位は、１つ又は複数の予測単位を含んでもよい。該探索済み予測単位は、画像フレームの第１タイプの予測単位のうちの１つ又は複数の予測単位を含んでもよく、又は画像フレームの第２タイプの予測単位のうちの１つ又は複数の予測単位を含んでもよく、又は画像フレームの第１タイプの予測単位のうちの１つ又は複数の予測単位も画像フレームの第２タイプの予測単位のうちの１つ又は複数の予測単位も含んでもよい。次に、探索済み予測単位の動きベクトルに基づいて現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得する。

いくつかの実施形態では、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得するステップは、
画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第２タイプの予測単位における対応位置の第１目標レート歪みコストを算出するステップと、
第２タイプの予測単位の現在動きベクトルに基づいて、第２タイプの予測単位の現在レート歪みコストを決定するステップと、
第２タイプの予測単位の現在レート歪みコストを第１目標レート歪みコストと比較するステップと、
第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第２タイプの予測単位の動きベクトルとして設定するステップと、
第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコスト以下である場合、現在レート歪みコストに対応する点の位置を第２タイプの予測単位の動きベクトルとして設定するステップと、を含んでもよい。

具体的には、ビデオ動き推定装置は、第２タイプの予測単位の動きベクトルを決定する際に、画像フレームの探索済み予測単位の動きベクトルに基づいて、探索中の第２タイプの予測単位の現在動きベクトルを補正してもよい。具体的には、ビデオ動き推定装置は、各予測単位の動きベクトルの探索過程において、探索済み予測単位の動きベクトルを記憶してもよく、予測単位の識別子と動きベクトルとのマッピング関係を生成してもよい。

探索中の第２タイプの予測単位の動きベクトルを補正する過程において、ビデオ動き推定装置は、探索済み予測単位の識別子に対応するマッピング関係を取得し、該マッピング関係に基づいて、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第２タイプの予測単位における対応位置の第１目標レート歪みコストを算出してもよい。例えば、探索済み予測単位の動きベクトルに基づいて、その指す先の対応位置を決定し、この対応位置のレート歪みコストを算出し、算出されたこの対応位置のレート歪みコストを第１目標レート歪みコストとして設定してもよい。

次に、ビデオ動き推定装置は、第２タイプの予測単位の現在レート歪みコストを第１目標レート歪みコストと比較してもよい。第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第２タイプの予測単位の動きベクトルとして設定し、第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコスト以下である場合、現在レート歪みコストに対応する点の位置を第２タイプの予測単位の動きベクトルとして設定する。

例えば、図９に示すように、ビデオ動き推定装置が、２Ｎ×２Ｎの予測単位、２Ｎ×Ｎの予測単位、Ｎ×２Ｎの予測単位、２Ｎ×ｎＵの予測単位、２Ｎ×ｎＤの予測単位、ｎＬ×２Ｎの予測単位、及びｎＲ×２Ｎの予測単位などの順番で、各予測単位に対応する動きベクトルを順次探索する場合、現在２Ｎ×ｎＤの予測単位を探索する際に、以前に探索された２Ｎ×２Ｎの予測単位、２Ｎ×Ｎの予測単位、Ｎ×２Ｎの予測単位、及び２Ｎ×ｎＵの予測単位などの動きベクトルを用いて、探索中の２Ｎ×ｎＤの予測単位の動きベクトルを補正してもよい。

ステップＳ１０４で、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行う。

第１タイプの予測単位の動きベクトル及び第２タイプの予測単位の動きベクトルを取得した後、ビデオ動き推定装置は、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行ってもよい。ここで、取得された第１タイプの予測単位の動きベクトル及び第２タイプの予測単位の動きベクトルは、主に画像フレームに対して整数画素動き予測（即ち、整数画素探索）を行うことにより取得された整数画素動きベクトルである。例えば、画像フレームに対して小数画素動き推定を行う際に、ビデオ動き推定装置は、整数画素動き予測により取得された動きベクトルに基づいて、１／２画素探索及び１／４画素精度の探索を行うことにより、精度動きベクトルを取得してもよい。精度動きベクトルに対して動き補償処理を行い、例えば、取得された精度動きベクトルに対して、離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｒｍ）や量子化などの処理を行うことにより、残差係数を取得する。次に、取得された残差係数をエントロピー符号化モジュールに入力することにより、符号列を出力することができる。また、残差係数に対して逆量子化・逆変換を行うことにより、再構成画像の残差値を取得し、残差値に基づいて再構成画像を取得し、再構成画像に対してループ内フィルタリングを行ったものを参照フレームキューに入れて、次のフレームの参照画像とする。このように、１フレームずつ符号化を行っていく。

以上から分かるように、本願の実施例では、ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を分類し、例えば、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分することができる。異なるタイプの予測単位に対しては、異なる探索アルゴリズムを用いて、異なるタイプの予測単位の動きベクトルを取得し、例えば、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得し、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得する。その後、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行うことができる。この構成では、複数の予測単位を分類し、異なる探索アルゴリズムを用いて、異なるタイプの予測単位の動きベクトルを取得することができ、探索効率が高いため、異なる予測単位に対してすべて同じ処理方式を統一的に採用する従来技術よりも、ビデオの動き推定の効率及び柔軟性が向上する。

上記実施例で説明した方法に基づき、以下、例を挙げてさらに詳しく説明する。

上記ビデオ動き推定装置は、コンピュータ、携帯電話やテレビなど、記憶ユニットを備えるとともに、マイクロプロセッサを搭載して演算能力を持っている端末に統合されてもよい。以下、端末の観点から説明する。

端末は、ローカル又はサーバーからビデオを取得し、フレーム間予測単位（ＰＵ）でビデオの画像フレームを２Ｎ×２Ｎ、２Ｎ×Ｎ、Ｎ×２Ｎ、２Ｎ×ｎＵ、２Ｎ×ｎＤ、ｎＬ×２Ｎ、及びｎＲ×２Ｎなどの複数の予測単位に分割してもよい。

ここで、図３に示すように、２Ｎ×Ｎの予測単位は、１：１の上下比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含み、Ｎ×２Ｎの予測単位は、１：１の左右比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含み、２Ｎ×ｎＵの予測単位は、１：３の上下比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含み、２Ｎ×ｎＤの予測単位は、３：１の上下比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含み、ｎＬ×２Ｎの予測単位は、１：３の左右比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含み、ｎＲ×２Ｎの予測単位は、３：１の左右比率で分けられた、インデックス０の分割ブロックと、インデックス１の分割ブロックとを含む。

次に、端末は、取得された複数の予測単位を、対称性に従って、第１タイプの予測単位と第２タイプの予測単位とに区分してもよい。該第１タイプの予測単位は、２Ｎ×２Ｎ、２Ｎ×Ｎ、及びＮ×２Ｎなどの対称モードの予測単位を含んでもよく、第２タイプの予測単位は、２Ｎ×ｎＵ、２Ｎ×ｎＤ、ｎＬ×２Ｎ、及びｎＲ×２Ｎなどの非対称モードの予測単位を含んでもよい。

端末は、第１タイプの予測単位及び第２タイプの予測単位のそれぞれに対して、異なる探索アルゴリズムを用いて、予測単位の動きベクトルを探索してもよい。以下、詳細に説明する。

第１タイプの予測単位の場合は、図１０を参照されたい。図１０は、本願の実施例で提供された第１タイプの予測単位の動きベクトルを探索するフローの模式図である。該方法のフローは、以下のステップを含んでもよい。

Ｓ２０１で、端末は、第１タイプの予測単位に対応する第２候補探索開始点を取得し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定する。

端末は、ＡＭＶＰ技術又はＭｅｒｇｅモードで１つ又は複数の第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定してもよい。即ち、該第２探索開始点は、第１タイプの予測単位に対応する、最終的に決定された探索開始点である。

ここで、レート歪みコストの計算式は、ｒｄｃｏｓｔ＝ｓａｄ＋ｌａｍｂｄａ＊ｂｉｔであってもよい。ここで、ｒｄｃｏｓｔはレート歪みコストを表し、ｓａｄは残差、即ち、動き補償予測誤差を表し、ｌａｍｂｄａは定数係数を表し、ラグランジュ乗数であってもよく、ｂｉｔはビットレート、即ち、動きベクトルに関する情報の符号化ビット数を表す。

説明すべきものとして、第１タイプの予測単位は、インデックス０の第３分割ブロックと、インデックス１の第４分割ブロックとを含んでもよい。端末は、第１タイプの予測単位の第３分割ブロック及び第４分割ブロックの動きベクトルをそれぞれ探索してもよい。第１タイプの予測単位の第４分割ブロックの探索開始点を決定する際に、探索済みの第３分割ブロックの動きベクトルに対応する位置を現在の第４分割ブロックの候補探索開始点の１つとしてもよい。具体的には、端末は、第１タイプの予測単位の第４分割ブロックの探索過程において、ＡＭＶＰ技術で第１タイプの予測単位の第４分割ブロックに対応する少なくとも１つの第２候補探索開始点を取得し、第１タイプの予測単位の第３分割ブロックの予測が完了したか否かを判断してもよい。第１タイプの予測単位の第３分割ブロックの予測が完了した場合、予測された第３分割ブロックの動きベクトルを取得し、予測された第３分割ブロックの動きベクトルに対応する予測点を決定し、各第２候補探索開始点及び第３分割ブロックのレート歪みコストを算出する。少なくとも１つの第２候補探索開始点及び第３分割ブロックのうち、レート歪みコストが最小となる点を第１タイプの予測単位の第４分割ブロックの探索開始点として設定し、ステップＳ２０２を実行するために、第４分割ブロックの探索開始点を第２探索開始点として設定する。

例えば、２Ｎ×Ｎの予測単位を例にすると、２Ｎ×Ｎの予測単位のインデックス０の分割ブロックの予測が完了したとすれば、２Ｎ×Ｎの予測単位のインデックス１の分割ブロックの予測を行う際に、インデックス０の分割ブロックに対応する予測結果のうちの動きベクトルに対応する位置を、インデックス１の分割ブロックの候補探索開始点位置の１つとしてもよい。これにより、候補探索開始点の中から、レート歪みコストが最小となる点を探索開始点として選択することができ、このようにして、探索開始点を動き推定の最適位置により近くし、探索過程をより迅速に終了させることができる。

Ｓ２０２で、端末は、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得する。

第２探索開始点を取得した後、端末は、菱形テンプレート又は正方形テンプレートなどを利用して、第２探索開始点を中心とする探索ウィンドウの範囲内で、第２所定インクリメンタルステップサイズで探索を行うことにより、複数の第２候補点を取得してもよい。

例えば、正方形テンプレートを例にすると、第２探索開始点を正方形テンプレートの中心として、１である探索ステップサイズから始め、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得する。ここで、第２所定インクリメンタルステップサイズは、２の整数乗のようにインクリメンタルしてもよい。つまり、まず、１である探索ステップサイズから始め、次に２、４、及び８などである探索ステップサイズで順次に探索を行うことにより、複数の第２候補点を取得する。この第２候補点は、各探索ステップサイズに対応する正方形テンプレートの頂点、及び２つの頂点の間の四等分に対応する点などであってもよい。ここで、例えば、最大探索ステップサイズが８に設定されている場合、対応する探索ウィンドウの範囲は、８である探索ステップサイズに対応する正方形テンプレートの内側の環状領域であり、最大探索ステップサイズが１６に設定されている場合、対応する探索ウィンドウの範囲は、１６である探索ステップサイズに対応する正方形テンプレートの内側の環状領域である。

次に、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別し、複数の第２候補点のうちレート歪みコストが最小となる点を第２未確定点として設定する。

Ｓ２０３で、第２未確定点に対応する探索ステップサイズが第２所定ステップサイズである場合、端末は、ステップサイズが第２所定ステップサイズである各点の周囲にある未探索の第２補足点を取得する。

第２未確定点を取得した後、端末は、該第２未確定点に対応する探索ステップサイズが第２所定ステップサイズであるか否かを判断してもよい。該第２所定ステップサイズは、実際のニーズに応じて柔軟に設定してもよい。例えば、第２所定ステップサイズを１又は２などに設定してもよい。

第２未確定点に対応する探索ステップサイズが第２所定ステップサイズである場合、端末は、ステップサイズが第２所定ステップサイズである各点の周囲にある未探索の第２補足点を取得する。

例えば、第２未確定点を探索するための探索テンプレートが正方形テンプレートである場合、取得された第２未確定点に対応する探索ステップサイズが１であれば、探索ステップサイズが１である正方形に対応する頂点は、点１、点３、点６、点８という４つの点であり、点２、点４、点５、点７は、該正方形の各辺の中点である。この場合、取得された、レート歪みコストが最小となる第２未確定点が点１の位置であると、点１の位置に対して点Ａ、点Ｃという２つの点を補足し、点Ａ、点Ｃという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点２の位置であると、点２の位置に対して点Ａ、点Ｂという２つの点を補足し、点Ａ、点Ｂという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点３の位置であると、点３の位置に対して点Ｂ、点Ｄという２つの点を補足し、点Ｂ、点Ｄという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点４の位置であると、点４の位置に対して点Ｃ、点Ｅという２つの点を補足し、点Ｃ、点Ｅという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点５の位置であると、点５の位置に対して点Ｄ、点Ｆという２つの点を補足し、点Ｄ、点Ｆという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点６の位置であると、点６の位置に対して点Ｅ、点Ｇという２つの点を補足し、点Ｅ、点Ｇという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点７の位置であると、点７の位置に対して点Ｇ、点Ｈという２つの点を補足し、点Ｇ、点Ｈという２つの点を第２補足点として設定してもよい。取得された、レート歪みコストが最小となる第２未確定点が点８の位置であると、点８の位置に対して点Ｆ、点Ｈという２つの点を補足し、点Ｆ、点Ｈという２つの点を第２補足点として設定してもよい。

Ｓ２０４で、端末は、第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点であるか否かを判断し、第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点である場合、ステップＳ２０５を実行し、第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点ではない場合、ステップＳ２０６を実行する。

第２補足点を取得した後、端末は、各第２補足点のレート歪みコストを算出し、第２補足点のレート歪みコストを第２未確定点のレート歪みコストと比較し、第２補足点及び第２未確定点のうちレート歪みコストが最小となる点が第２未確定点であるか否かを判断してもよい。

Ｓ２０５で、端末は、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定し、動きベクトルを補正する。

Ｓ２０６で、第２未確定点及び第２補足点のうちレート歪みコストが最小となる点の位置を第１タイプの予測単位の動きベクトルとして設定し、動きベクトルを補正する。

第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点である場合、端末は、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定する。第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が第２未確定点ではない場合、端末は、第２未確定点及び第２補足点のうちレート歪みコストが最小となる点の位置を第１タイプの予測単位の動きベクトルとして設定する。

この場合、端末は、第１タイプの予測単位の動きベクトルを補正してもよい。具体的には、端末は、各予測単位の動きベクトルの探索過程において、探索済み予測単位の動きベクトルを記憶してもよく、予測単位の識別子と動きベクトルとのマッピング関係を生成してもよい。

探索中の第１タイプの予測単位の動きベクトルを補正する過程において、端末は、探索済み予測単位の識別子に対応するマッピング関係を取得し、該マッピング関係に基づいて、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第１タイプの予測単位の第２目標レート歪みコストを算出してもよい。次に、第２未確定点のレート歪みコストを第２目標レート歪みコストと比較してもよい。

第２未確定点のレート歪みコストｃｏｓｔ＿ｂｅｓｔが第２目標レート歪みコストｃｏｓｔ＿ｒｅｆよりも大きい場合、探索済み予測単位の動きベクトルｍｖ＿ｒｅｆを第１タイプの予測単位の動きベクトルｍｖ＿ｂｅｓｔとして設定し、即ち、第１タイプの予測単位の動きベクトルｍｖ＿ｂｅｓｔを探索済み予測単位の動きベクトルｍｖ＿ｒｅｆに補正する（ｍｖ＿ｂｅｓｔ＝ｍｖ＿ｒｅｆ）。第２未確定点のレート歪みコストが第２目標レート歪みコスト以下である場合、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定する。

例えば、各予測単位の動きベクトルを予め命名しておいてもよい。その命名アルゴリズムは、ｍｖ＿ｂｅｓｔ＿予測単位タイプ＿予測単位インデックスとしてもよい。例えば、ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１は、２Ｎ×Ｎの予測単位のインデックス１の分割ブロックの動きベクトルを表す。端末が既に２Ｎ×２Ｎの予測単位及び２Ｎ×Ｎの予測単位の動きベクトルを探索したとすれば、現在Ｎ×２Ｎの予測単位の動きベクトルを探索する際に、２Ｎ×２Ｎの予測単位及び２Ｎ×Ｎの予測単位の動きベクトルを用いて、Ｎ×２Ｎの予測単位の動きベクトルを補正してもよい。例えば、Ｎ×２Ｎの予測単位のインデックス０の分割ブロックＰＵ０及びインデックス１の分割ブロックＰＵ１の動きベクトルは、２Ｎ×２Ｎの予測単位及び２Ｎ×Ｎの予測単位の動きベクトル＝｛ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１｝を参照してもよい。

Ｓ２０７で、第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内である場合、端末は、第２未確定点を中心とする所定範囲内で、所定間隔であるステップサイズで探索を行うことにより、複数の探索点を取得し、第２未確定点及び複数の探索点のうちレート歪みコストが最小となる点を第２探索開始点とし、ステップＳ２０２に戻る。

第２未確定点を取得した後、端末は、該第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第３所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な値を限定しない。

第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内である場合、第２未確定点を中心とする所定範囲内で、所定間隔であるステップサイズで探索を行うことにより、複数の探索点を取得する。ここで、所定範囲、及び所定間隔であるステップサイズは、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な値を限定しない。例えば、図６に示すように、第２未確定点を中心とする探索ウィンドウの範囲内で、ラスター走査方式によって５行５列おきにすべての点を走査することにより、複数の探索点を取得する。

次に、各探索点のレート歪みコストを算出し、第２未確定点及び複数の探索点のうちレート歪みコストが最小となる点を第２探索開始点として設定し、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップに戻る。

Ｓ２０８で、第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内である場合、端末は、第２未確定点を第２探索開始点とし、ステップＳ２０２に戻る。

第２未確定点を取得した後、端末は、該第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第４所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な内容を限定しない。第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内である場合、第２未確定点を第２探索開始点とし、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップに戻る。

第２タイプの予測単位の場合は、図１１を参照されたい。図１１は、本願の実施例で提供された第２タイプの予測単位の動きベクトルを探索するフローの模式図である。該方法のフローは、以下のステップを含んでもよい。

Ｓ３０１で、端末は、第２タイプの予測単位に対応する第１候補探索開始点を取得し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定する。端末は、ＡＭＶＰ技術又はＭｅｒｇｅモードで、第２タイプの予測単位に対応する第１候補探索開始点を取得し、次に、各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定してもよい。即ち、該第１探索開始点は、第２タイプの予測単位に対応する、最終的に決定された探索開始点である。

説明すべきものとして、第２タイプの予測単位は、インデックス０の第１分割ブロックと、インデックス１の第２分割ブロックとを含んでもよい。端末は、第２タイプの予測単位の第１分割ブロック及び第２分割ブロックの動きベクトルをそれぞれ探索してもよい。第２タイプの予測単位の第２分割ブロックの探索開始点を決定する際に、探索済みの第１分割ブロックの動きベクトルに対応する位置を現在の第２分割ブロックの探索開始点の１つとしてもよい。具体的には、端末は、第２タイプの予測単位の第２分割ブロックの探索過程において、ＡＭＶＰ技術で第２タイプの予測単位の第２分割ブロックに対応する少なくとも１つの第１候補探索開始点を取得し、第２タイプの予測単位の第１分割ブロックの探索が完了したか否かを判断し、即ち、第２タイプの予測単位の第１分割ブロックの予測が完了したか否かを判断してもよい。第２タイプの予測単位の第１分割ブロックの予測が完了した場合、予測された第１分割ブロック動きベクトルを取得し、予測された第１分割ブロックの動きベクトルに対応する予測点を決定し、各第１候補探索開始点及び第１分割ブロックのレート歪みコストを算出する。少なくとも１つの第１候補探索開始点及び第１分割ブロックのうち、レート歪みコストが最小となる点を第２タイプの予測単位の第２分割ブロックの探索開始点として設定し、ステップＳ３０２を実行するために、第２分割ブロックの探索開始点を第２探索開始点として設定する。

例えば、２Ｎ×ｎＤの予測単位を例にすると、２Ｎ×ｎＤの予測単位のインデックス０の分割ブロックの予測が完了したとすれば、２Ｎ×ｎＤの予測単位のインデックス１の分割ブロックの予測を行う際に、インデックス０の分割ブロックに対応する動きベクトルの位置を、インデックス１の分割ブロックの候補探索開始点位置の１つとしてもよい。これにより、候補探索開始点の中から、レート歪みコストが最小となる点を探索開始点として選択することができ、このようにして、探索開始点を動き推定の最適位置により近くし、探索過程をより迅速に終了させることができる。

Ｓ３０２で、端末は、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで取得し、複数の第１候補点の中から、レート歪みコストが最小となる点を選別することにより、第１未確定点を取得する。

第１探索開始点を取得した後、端末は、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで探索してもよい。ここで、探索ウィンドウの範囲は、菱形テンプレート又は正方形テンプレートの探索範囲であってもよい。例えば、探索ウィンドウの範囲は、菱形テンプレート又は正方形テンプレートの最大探索ステップサイズに対応する内側の環状領域であってもよい。例えば、菱形テンプレートの最大探索ステップサイズが８に設定されている場合、対応する探索ウィンドウの範囲は、８である探索ステップサイズに対応する菱形テンプレートの内側の環状領域である。第１所定インクリメンタルステップサイズは、２の整数乗のようにインクリメンタルするステップサイズであってもよく、又は実際のニーズに応じて柔軟に設定してもよい。

例えば、正方形テンプレートを例にすると、第１探索開始点を正方形テンプレートの中心として、１である探索ステップサイズから始め、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を、２の整数乗のようにインクリメンタルする探索ステップサイズで探索することにより、複数の第１候補点を取得する。この第１候補点は、各探索ステップサイズに対応する正方形テンプレートの頂点、及び２つの頂点の間の四等分に対応する点などであってもよい。

次に、各第１候補点のレート歪みコストを算出し、複数の第１候補点の中から、レート歪みコストが最小となる点を選別し、複数の第１候補点のうちレート歪みコストが最小となる点を第１未確定点として設定する。

Ｓ３０３で、第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、端末は、第１未確定点を中心とするポリゴンモデルを取得し、ポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最小となる点を選択することにより、第１目標点を取得する。

第１未確定点を取得した後、端末は、該第１未確定点に対応する探索ステップサイズが第１所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第１所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な値を限定しない。

第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、端末は、第１未確定点を中心とするポリゴンモデルを取得する。該ポリゴンモデルは、四角形又は六角形などであってもよい。

ポリゴンモデルを取得した後、端末は、ポリゴンモデルの中心及び各々の頂点の位置のレート歪みコストを算出し、ポリゴンモデルの中心及び各々の頂点のうちレート歪みコストが最小となる点を第１目標点として設定してもよい。

Ｓ３０４で、第１目標点が第１未確定点と一致する場合、端末は、第１目標点の位置を第２タイプの予測単位の現在動きベクトルとして設定し、現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得する。

第１目標点を取得した後、端末は、該第１目標点が第１未確定点と一致するか否かを判断してもよい。第１目標点が第１未確定点と一致する場合、端末は、第１目標点の位置を第２タイプの予測単位の現在動きベクトルとして設定してもよい。

第２タイプの予測単位の現在動きベクトルを取得した後、端末は、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第２タイプの予測単位の現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得してもよい。ここで、探索済み予測単位は、１つ又は複数の予測単位を含んでもよい。

具体的には、端末は、各予測単位の動きベクトルの探索過程において、探索済み予測単位の動きベクトルを記憶してもよく、予測単位の識別子と動きベクトルとのマッピング関係を生成してもよい。探索中の第２タイプの予測単位の動きベクトルを補正する過程において、端末は、探索済み予測単位の識別子に対応するマッピング関係を取得し、該マッピング関係に基づいて、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第２タイプの予測単位の第１目標レート歪みコストを算出してもよい。

次に、端末は、第２タイプの予測単位の現在レート歪みコストを第１目標レート歪みコストと比較してもよい。第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第２タイプの予測単位の動きベクトルとして設定し、第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコスト以下である場合、現在レート歪みコストに対応する点の位置を第２タイプの予測単位の動きベクトルとして設定する。

例えば、各予測単位の動きベクトルを予め命名しておいてもよい。その命名アルゴリズムは、ｍｖ＿ｂｅｓｔ＿予測単位タイプ＿予測単位インデックスとしてもよい。例えば、ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１は、２Ｎ×Ｎの予測単位のインデックス１の分割ブロックの動きベクトルを表す。２Ｎ×Ｎの予測単位にとって、画像フレームの探索済み予測単位の動きベクトルは、｛ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ１｝を含んでもよい。

Ｎ×２Ｎの予測単位にとって、画像フレームの探索済み予測単位の動きベクトルは、｛ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１｝を含んでもよい。

２Ｎ×ｎＵの予測単位にとって、画像フレームの探索済み予測単位の動きベクトルは、｛ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ１｝を含んでもよい。

２Ｎ×ｎＤの予測単位にとって、画像フレームの探索済み予測単位の動きベクトルは、｛ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＵ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＵ＿ＰＵ１｝を含んでもよい。

ｎＬ×２Ｎの予測単位にとって、画像フレームの探索済み予測単位の動きベクトルは、｛ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＵ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＵ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＤ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＤ＿ＰＵ１｝を含んでもよい。

ｎＲ×２Ｎの予測単位にとって、画像フレームの探索済み予測単位の動きベクトルは、｛ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿Ｎ×２Ｎ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＵ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＵ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＤ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿２Ｎ×ｎＤ＿ＰＵ１，ｍｖ＿ｂｅｓｔ＿ｎＬ×２Ｎ＿ＰＵ０，ｍｖ＿ｂｅｓｔ＿ｎＬ×２Ｎ＿ＰＵ１｝を含んでもよい。

Ｓ３０５で、第１目標点が第１未確定点と一致しない場合、端末は、ポリゴンモデルの中心を第１目標点の位置に移動させ、移動させたポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最小となる点を選別することにより、最適点を取得する。

第１目標点が第１未確定点と一致しない場合、端末は、ポリゴンモデルの中心を第１目標点の位置に移動させてもよい。該ポリゴンモデルは、移動後に元の形状が変わらないように維持される。次に、移動させたポリゴンモデルの中心及び各々の頂点の位置のレート歪みコストを算出し、移動させたポリゴンモデルの中心及び各々の頂点のうちレート歪みコストが最小となる点を最適点として設定する。

例えば、図８に示すように、ポリゴンモデルが六角形モデルである場合、図８（ａ）において、六角形モデルの中心及び各々の頂点のレート歪みコストを算出することにより取得された、レート歪みコストが最小となる点（即ち最適点）が六角形モデルの右頂点の位置であれば、図８（ｂ）に示すように、六角形モデルの中心を右頂点の位置に移動させる。このとき、移動させた六角形モデルの中心及び各々の頂点のレート歪みコストを算出する。取得された、レート歪みコストが最小となる点が六角形モデルの右上の頂点の位置であれば、図８（ｃ）に示すように、六角形モデルの中心を右上の頂点の位置に移動させる。このとき、移動させた六角形モデルの中心及び各々の頂点のレート歪みコストを算出する。取得された、レート歪みコストが最小となる点が六角形モデルの左上の頂点の位置であれば、図８（ｄ）に示すように、六角形モデルの中心を左上の頂点の位置に移動させる。このとき、移動させた六角形モデルの中心及び各々の頂点のレート歪みコストを算出する。取得された、レート歪みコストが最小となる点が六角形モデルの中心の位置であれば、即ち、最適点が六角形モデルの中心の位置であれば、六角形モデルを移動させず、六角形モデルの中心の位置（即ち最適点の位置）を第２タイプの予測単位の現在動きベクトルとして設定する。

Ｓ３０６で、端末は、最適点が第１目標点と一致するか否かを判断し、最適点が第１目標点と一致する場合、ステップＳ３０７を実行し、最適点が第１目標点と一致しない場合、ステップＳ３０８を実行する。

最適点を取得した後、端末は、最適点が第１目標点と一致するか否かを判断してもよい。

Ｓ３０７で、端末は、最適点の位置を第２タイプの予測単位の現在動きベクトルとして設定し、現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得する。

最適点が第１目標点と一致する場合、端末は、最適点の位置を第２タイプの予測単位の現在動きベクトルとして設定してもよい。また、端末は、上記のような、第２タイプの予測単位の現在動きベクトルを補正する方式によって、取得された第２タイプの予測単位の現在動きベクトルを補正してもよい。

Ｓ３０８で、端末は、最適点を第１探索開始点として設定し、ステップＳ３０２に戻る。

最適点が第１目標点と一致しない場合、端末は、最適点を第１探索開始点として設定し、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで探索し、複数の第１候補点の中から、レート歪みコストが最小となる点を選別することにより、第１未確定点を取得するステップに戻る。

Ｓ３０９で、第１未確定点に対応する探索ステップサイズが第１所定ステップサイズである場合、端末は、ステップサイズが第１所定ステップサイズである各点の周囲にある未探索の第１補足点を取得する。

第１未確定点を取得した後、端末は、該第１未確定点に対応する探索ステップサイズが第１所定ステップサイズであるか否かを判断してもよい。ここで、該第１所定ステップサイズは、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な値を限定しない。第１未確定点に対応する探索ステップサイズが第１所定ステップサイズである場合、端末は、ステップサイズが第１所定ステップサイズである各点の周囲にある未探索の第１補足点を取得してもよい。

例えば、第１未確定点を探索するための探索テンプレートが正方形テンプレートである場合、取得された第１未確定点に対応する探索ステップサイズが１であれば、探索ステップサイズが１である正方形に対応する頂点は、点１、点３、点６、点８という４つの点であり、点２、点４、点５、点７は、該正方形の各辺の中点である。この場合、取得された、レート歪みコストが最小となる第１未確定点が点１の位置であると、点１の位置に対して点Ａ、点Ｃという２つの点を補足し、点Ａ、点Ｃという２つの点を第１補足点として設定してもよく、取得された、レート歪みコストが最小となる第１未確定点が点３の位置であると、点３の位置に対して点Ｂ、点Ｄという２つの点を補足し、点Ｂ、点Ｄという２つの点を第１補足点として設定してもよく、取得された、レート歪みコストが最小となる第１未確定点が点６の位置であると、点６の位置に対して点Ｅ、点Ｇという２つの点を補足し、点Ｅ、点Ｇという２つの点を第１補足点として設定してもよく、取得された、レート歪みコストが最小となる第１未確定点が点８の位置であると、点８の位置に対して点Ｆ、点Ｈという２つの点を補足し、点Ｆ、点Ｈという２つの点を第１補足点として設定してもよい。

Ｓ３１０で、端末は、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点であるか否かを判断し、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点である場合、ステップＳ３１１を実行し、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点ではない場合、ステップＳ３１２を実行する。

第１補足点を取得した後、端末は、第１補足点のレート歪みコストを算出し、第１補足点のレート歪みコストを第１未確定点のレート歪みコストと比較し、第１補足点及び第１未確定点のうちレート歪みコストが最小となる点が第１未確定点であるか否かを判断してもよい。

Ｓ３１１で、端末は、第１未確定点の位置を第２タイプの予測単位の現在動きベクトルとして設定し、現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得する。

第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点である場合、第１未確定点の位置を第２タイプの予測単位の現在動きベクトルとして設定する。また、端末は、上記のような、第２タイプの予測単位の現在動きベクトルを補正する方式によって、取得された第２タイプの予測単位の現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得する。

Ｓ３１２で、端末は、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点の位置を第２タイプの予測単位の現在動きベクトルとして設定し、現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得する。

第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点ではない場合、端末は、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点の位置を第２タイプの予測単位の現在動きベクトルとして設定してもよい。また、端末は、上記のような、第２タイプの予測単位の現在動きベクトルを補正する方式によって、取得された第２タイプの予測単位の現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得してもよい。

Ｓ３１３で、第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内である場合、端末は、第１未確定点を第１探索開始点として設定し、ステップＳ３０２に戻る。

第１未確定点を取得した後、端末は、該第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内であるか否かを判断してもよい。ここで、第２所定ステップサイズ閾値の範囲は、実際のニーズに応じて柔軟に設定してもよいが、ここでは具体的な値を限定しない。

第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内である場合、第１未確定点を第１探索開始点として設定し、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで探索し、複数の第１候補点の中から、レート歪みコストが最小となる点を選別することにより、第１未確定点を取得するステップに戻る。

第１タイプの予測単位の動きベクトル及び第２タイプの予測単位の動きベクトルを取得した後、端末は、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行ってもよい。例えば、端末は、取得された動きベクトルに基づいて、離散コサイン変換や量子化などの処理を行うことにより、残差係数を取得してもよい。次に、取得された残差係数をエントロピー符号化モジュールに入力することにより、符号列を出力することができる。また、残差係数に対して逆量子化・逆変換を行うことにより、再構成画像の残差値を取得し、残差値に基づいて再構成画像を取得し、再構成画像に対してループ内フィルタリングを行ったものを参照フレームキューに入れて、次のフレームの参照画像とする。このように、１フレームずつ符号化を行っていく。

本願の実施例では、ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分することができる。第１タイプの予測単位に対しては、複雑な探索アルゴリズムを用いて探索を行うことができ、第２タイプの予測単位に対しては、高速な探索アルゴリズムを用いて探索を行うことができる。これによって、動き推定過程を速めることができる。そして、１つの予測単位に２つの分割ブロックが存在する場合、後で探索する分割ブロックに対しては、探索済みの分割ブロックの最終的な探索結果を参照することができる。これによっても、動き推定過程を速めることができる。さらに、補正ストラテジーによって、局所最適位置を探索した可能性がある若干の結果が補正され、探索エラーが回避され、符号化の速度が大幅に向上するとともに、圧縮率の損失が少ない。

本願の実施例で提供されたビデオ動き推定方法をより良く実施することに便利なように、本願の実施例は、上記ビデオ動き推定方法に基づく装置をさらに提供する。その用語の意味は上記ビデオ動き推定方法と同じであり、具体的な実現の詳細については方法の実施例の説明を参照すればよい。

図１２を参照されたいが、図１２は、本願の実施例で提供されたビデオ動き推定装置の構成の模式図である。ここで、該ビデオ動き推定装置は、分割ユニット４０１と、第１取得ユニット４０２と、第２取得ユニット４０３と、動き推定ユニット４０４とを備えてもよい。

ここで、分割ユニット４０１は、ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分する。

分割ユニット４０１の具体的な実施については、ステップＳ１０１に関して説明した上記実施例を参照すればよい。

第１取得ユニット４０２は、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得する。

第１取得ユニット４０２の具体的な実施については、ステップＳ１０２に関して説明した上記実施例を参照すればよい。

いくつかの実施形態では、図１４に示すように、第１取得ユニット４０２は、第２取得サブユニット４０２１と、算出サブユニット４０２２と、第３取得サブユニット４０２３と、第３設定サブユニット４０２４と、第４設定サブユニット４０２５などを備えてもよい。具体的には、以下のようにしてもよい。

第２取得サブユニット４０２１は、第１タイプの予測単位に対応する第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定する。

算出サブユニット４０２２は、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得する。

第３取得サブユニット４０２３は、前記第２未確定点に対応する探索ステップサイズが第２所定ステップサイズである場合、ステップサイズが前記第２所定ステップサイズである各点の周囲にある未探索の第２補足点を取得し、前記第２補足点のレート歪みコストを算出する。

第３設定サブユニット４０２４は、前記第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が前記第２未確定点である場合、前記第２未確定点の位置を前記第１タイプの予測単位の動きベクトルとして設定する。

第４設定サブユニット４０２５は、前記第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が前記第２未確定点ではない場合、前記第２未確定点を第２探索開始点として設定し、前記算出サブユニットによって、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップを実行する。

上記第２取得サブユニット４０２１、算出サブユニット４０２２、第３取得サブユニット４０２３、第３設定サブユニット４０２４、及び第４設定サブユニット４０２５の具体的な実施については、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得するステップに関して説明した上記実施例を参照すればよい。

任意選択的に、第３設定サブユニット４０２４は、具体的に、
画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第１タイプの予測単位における対応位置の第２目標レート歪みコストを算出し、
第２未確定点のレート歪みコストを第２目標レート歪みコストと比較し、
第２未確定点のレート歪みコストが第２目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第１タイプの予測単位の動きベクトルとして設定し、
第２未確定点のレート歪みコストが第２目標レート歪みコスト以下である場合、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定する。

第３設定サブユニット４０２４の具体的な実施については、第２未確定点の位置を第１タイプの予測単位の動きベクトルとして設定するステップに関して説明した上記実施例を参照すればよい。

任意選択的に、第２タイプの予測単位は、第３分割ブロックと第４分割ブロックとを含み、第２取得サブユニット４０２１は、具体的に、
高度動きベクトル予測で第１タイプの予測単位の第４分割ブロックに対応する少なくとも１つの第２候補探索開始点を取得し、
第１タイプの予測単位の第３分割ブロックの予測が完了すると、第３分割ブロックの予測結果を取得し、各第２候補探索開始点のレート歪みコストを算出し、第３分割ブロックの予測結果に基づいて、第３分割ブロックの位置のレート歪みコストを算出し、
少なくとも１つの第２候補探索開始点及び第３分割ブロックのうち、レート歪みコストが最小となる点を第１タイプの予測単位の第４分割ブロックの探索開始点として設定し、第４分割ブロックの探索開始点を第２探索開始点として設定する。

第２取得サブユニット４０２１の具体的な実施については、第１タイプの予測単位に対応する第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定するステップに関して説明した上記実施例を参照すればよい。

いくつかの実施形態では、第１取得ユニット４０２は、
第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内である場合、第２未確定点を中心とする所定範囲内で、所定間隔であるステップサイズで探索を行うことにより、複数の探索点を取得し、各探索点のレート歪みコストを算出する探索サブユニットと、
第２未確定点及び複数の探索点のうちレート歪みコストが最小となる点を第２探索開始点として設定し、算出サブユニットによって、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップを実行する第１実行サブユニットと、をさらに備えてもよい。探索サブユニット及び第１実行サブユニットの具体的な実施については、第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内である場合に関して説明した上記実施例を参照すればよい。

いくつかの実施形態では、第１取得ユニット４０２は、
第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内である場合、第２未確定点を第２探索開始点として設定し、算出サブユニットによって、第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップを実行する第２実行サブユニットをさらに備えてもよい。

第２実行サブユニットの具体的な実施については、第２未確定点に対応する探索ステップサイズが第４所定ステップサイズ閾値の範囲内である場合に関して説明した上記実施例を参照すればよい。

第２取得ユニット４０３は、第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得する。

いくつかの実施形態では、図１３に示すように、第２取得ユニット４０３は、第１取得サブユニット４０３１及び補正サブユニット４０３２などを備えてもよい。具体的には、以下のようにしてもよい。

第１取得サブユニット４０３１は、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得する。

補正サブユニット４０３２は、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得する。

第２取得ユニット４０３の具体的な実施については、ステップＳ１０３に関して説明した上記実施例を参照すればよい。

ここで、いくつかの実施形態では、第１取得サブユニット４０３１は、
第２探索アルゴリズムによって、第２タイプの予測単位における第１未確定点を取得する探索モジュールと、
第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得し、ポリゴンモデルに基づいて第１目標点を取得する取得モジュールと、
第１目標点が第１未確定点と一致しない場合、ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得する移動モジュールと、
最適点が第１目標点と一致する場合、最適点の位置を第２タイプの予測単位の現在動きベクトルとして設定する第１設定モジュールと、を備えてもよい。

上記探索モジュール、取得モジュール、及び移動モジュールの具体的な実施については、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得するステップに関して説明した上記実施例を参照すればよい。

任意選択的に、移動モジュールは、具体的に、
第１目標点が第１未確定点と一致しない場合、ポリゴンモデルの中心を第１目標点の位置に移動させ、
移動させたポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最小となる点を選別することにより、最適点を取得してもよい。

上記移動モジュールの具体的な実施については、第１目標点が第１未確定点と一致しない場合、ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得するステップに関して説明した上記実施例を参照すればよい。

任意選択的に、第１取得サブユニット４０３１は、
第１目標点が第１未確定点と一致する場合、第１目標点の位置を第２タイプの予測単位の現在動きベクトルとして設定する第２設定モジュールをさらに備えてもよい。

いくつかの実施形態では、探索モジュールは、
第２探索アルゴリズムによって、第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得する探索サブモジュールを備えてもよく、
取得モジュールは、具体的に、
第１未確定点に対応する探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得し、
ポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最小となる点を選択することにより、第１目標点を取得する。

上記探索サブモジュール、取得モジュールの具体的な実施については、第２探索アルゴリズムによって、第２タイプの予測単位における第１未確定点を取得し、第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得し、ポリゴンモデルに基づいて第１目標点を取得するステップに関して説明した上記実施例を参照すればよい。

任意選択的に、探索サブモジュールは、具体的に、
第２探索アルゴリズムによって、第２タイプの予測単位に対応する第１候補探索開始点を取得し、
各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定し、
第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで取得し、
複数の第１候補点の中から、レート歪みコストが最小となる点を選別することにより、第１未確定点を取得してもよい。

上記探索サブモジュールの具体的な実施については、第２探索アルゴリズムによって、第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップに関して説明した上記実施例を参照すればよい。

いくつかの実施形態では、第２タイプの予測単位は、第１分割ブロックと第２分割ブロックとを含み、探索サブモジュールは、さらに、具体的に、
第２探索アルゴリズムによって、高度動きベクトル予測で第２タイプの予測単位の第２分割ブロックに対応する少なくとも１つの第１候補探索開始点を取得し、
第２タイプの予測単位の第１分割ブロックの予測が完了すると、第１分割ブロックの予測結果を取得し、各第１候補探索開始点のレート歪みコストを算出し、第１分割ブロックの予測結果に基づいて第１分割ブロックの位置のレート歪みコストを算出し、
少なくとも１つの第１候補探索開始点及び第１分割ブロックの中から、レート歪みコストが最小となる点を取得し、
取得されたレート歪みコストが最小となる点を第２タイプの予測単位の第２分割ブロックの探索開始点として設定し、第２分割ブロックの探索開始点を第１探索開始点として設定する。

上記第１分割ブロック、第２分割ブロック、及び探索サブモジュールの具体的な実施については、第２探索アルゴリズムによって、第２タイプの予測単位に対応する第１候補探索開始点を取得し、各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定するステップに関して説明した上記実施例を参照すればよい。

いくつかの実施形態では、取得モジュールは、さらに、具体的に、
第１未確定点に対応する探索ステップサイズが第１所定ステップサイズである場合、ステップサイズが第１所定ステップサイズである各点の周囲にある未探索の第１補足点を取得し、第１補足点のレート歪みコストを算出し、
第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点である場合、第１未確定点の位置を第２タイプの予測単位の現在動きベクトルとして設定し、
第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が第１未確定点ではない場合、第１未確定点及び第１補足点のうちレート歪みコストが最小となる点の位置を第２タイプの予測単位の現在動きベクトルとして設定してもよい。

上記取得モジュールの具体的な実施については、第２探索アルゴリズムによって、第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップの後に説明した上記実施例を参照すればよい。

いくつかの実施形態では、取得モジュールは、さらに、具体的に、
第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内である場合、第１未確定点を第１探索開始点として設定し、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで取得するステップに戻ってもよい。

いくつかの実施形態では、補正サブユニット４０３２は、具体的に、
画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第２タイプの予測単位における対応位置の第１目標レート歪みコストを算出し、
第２タイプの予測単位の現在動きベクトルに基づいて、第２タイプの予測単位の現在レート歪みコストを決定し、
第２タイプの予測単位の現在レート歪みコストを第１目標レート歪みコストと比較し、
第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第２タイプの予測単位の動きベクトルとして設定し、
第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコスト以下である場合、現在レート歪みコストに対応する点の位置を第２タイプの予測単位の動きベクトルとして設定する。

上記補正サブユニット４０３２の具体的な実施については、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得するステップに関して説明した上記実施例を参照すればよい。

動き推定ユニット４０４は、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行う。

動き推定ユニット４０４の具体的な実施については、ステップＳ１０４に関して説明した上記実施例を参照すればよい。

これに応じて、本願の実施例では、さらに、端末が提供されている。図１５に示すように、該端末は、無線周波数（ＲＦ：Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ）回路６０１、１つ又は複数のコンピュータ可読記憶媒体を含むメモリ６０２、入力ユニット６０３、表示ユニット６０４、センサ６０５、オーディオ回路６０６、ワイヤレスフィデリティ（ＷｉＦｉ：Ｗｉｒｅｌｅｓｓ Ｆｉｄｅｌｉｔｙ）モジュール６０７、１つ又は複数の処理コアを含むプロセッサ６０８や電源６０９などのコンポーネントを備えてもよい。当業者であれば理解できるように、図１５に示される端末の構成は、端末を限定するものではなく、図示されたものよりも多く又は少ないコンポーネントを含んでもよく、或いは特定のコンポーネントを組み合わせたものであってもよく、或いはコンポーネントの異なる配置を有してもよい。

ＲＦ回路６０１は、情報の送受信中又は通話中に信号を送受信するために使用することができ、特に、基地局のダウンリンク情報を受信して、１つ又は複数のプロセッサ６０８に渡して処理するとともに、アップリンクに関するデータを基地局に送信する。一般に、ＲＦ回路６０１は、アンテナ、少なくとも１つの増幅器、チューナ、１つ又は複数の発振器、加入者識別モジュール（ＳＩＭ：Ｓｕｂｓｃｒｉｂｅｒ Ｉｄｅｎｔｉｔｙ Ｍｏｄｕｌｅ）カード、トランシーバ、カプラー、低雑音増幅器（ＬＮＡ：Ｌｏｗ Ｎｏｉｓｅ Ａｍｐｌｉｆｉｅｒ）、デュプレクサなどを含むが、これらに限定されない。また、ＲＦ回路６０１は、無線通信を介してネットワークや他のデバイスと通信することもできる。前記無線通信には、グローバルモバイル通信システム（ＧＳＭ：Ｇｌｏｂａｌ Ｓｙｓｔｅｍ ｏｆ Ｍｏｂｉｌｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ）、汎用パケット無線サービス（ＧＰＲＳ：Ｇｅｎｅｒａｌ Ｐａｃｋｅｔ Ｒａｄｉｏ Ｓｅｒｖｉｃｅ）、コード分割多元接続（ＣＤＭＡ：Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）、広帯域コード分割多元接続（ＷＣＤＭＡ：Ｗｉｄｅｂａｎｄ Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）、長期的進化（ＬＴＥ：Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ）、電子メール、ショートメッセージングサービス（ＳＭＳ：Ｓｈｏｒｔ Ｍｅｓｓａｇｉｎｇ Ｓｅｒｖｉｃｅ）などを含むが、これらに限定されない任意の通信規格又はプロトコルを使用してもよい。

メモリ６０２は、コンピュータ可読命令及びモジュールを記憶するために使用することができ、プロセッサ６０８は、メモリ６０２に記憶されたコンピュータ可読命令及びモジュールを実行することにより、様々な機能アプリケーション及びデータ処理を実行する。メモリ６０２は、主にコンピュータ可読命令記憶領域及びデータ記憶領域を含んでもよい。ここで、コンピュータ可読命令記憶領域には、オペレーティングシステム、少なくとも１つの機能（例えば、音響再生機能、画像再生機能など）に必要なアプリケーションプログラムなどを記憶してもよい。データ記憶領域には、端末の使用に応じて作成されたデータ（例えば、オーディオデータ、電話帳など）などを記憶してもよい。また、メモリ６０２は、高速ランダムアクセスメモリを含んでもよいし、不揮発性メモリ、例えば、少なくとも１つの磁気ディスク記憶デバイス、フラッシュメモリデバイス、又は他の不揮発性ソリッドステート記憶デバイスを含んでもよい。これに応じて、メモリ６０２は、メモリコントローラをさらに含んでもよい。これにより、プロセッサ６０８及び入力ユニット６０３によるメモリ６０２へのアクセスが提供される。

入力ユニット６０３は、入力された数字又は文字の情報を受信することと、ユーザ設定及び機能制御に関する、キーボード、マウス、ジョイスティック、光学又はトラックボールによる信号入力を生成することとに使用することができる。具体的には、特定の実施例では、入力ユニット６０３は、タッチセンシティブ表面及び他の入力デバイスを含んでもよい。タッチセンシティブ表面は、タッチスクリーン又はタッチパッドとも呼ばれ、その上又はその近くでのユーザのタッチ操作を収集し（例えば、ユーザが指、スタイラスなどの任意の適切なもの又はアクセサリを使用して、タッチセンシティブ表面の上又はタッチセンシティブ表面の近くで行う操作）、プリセットプログラムに従って、相応の接続装置を駆動することができる。任意選択的に、タッチセンシティブ表面は、タッチ検出装置及びタッチコントローラの２つの部分を含んでもよい。ここで、タッチ検出装置は、ユーザのタッチ方位を検出し、タッチ操作による信号を検出し、信号をタッチコントローラに伝送する。タッチコントローラは、タッチ検出装置からタッチ情報を受信し、それをタッチポイント座標に変換してプロセッサ６０８に送信するとともに、プロセッサ６０８から送信されたコマンドを受信して実行することができる。また、抵抗膜、静電容量、赤外線や表面弾性波などの複数の形態によって、タッチセンシティブ表面を実現してもよい。入力ユニット６０３は、タッチセンシティブ表面に加えて、他の入力デバイスも含んでもよい。具体的には、他の入力デバイスは、物理キーボード、ファンクションキー（例えば、ボリュームコントロールキー、スイッチキーなど）、トラックボール、マウス、ジョイスティックなどのうち１つ又は複数を含んでもよいが、これらに限定されない。

表示ユニット６０４は、ユーザが入力した情報又はユーザに提供する情報、及び端末の様々なグラフィカルユーザインターフェースを表示するために使用することができる。これらのグラフィカルユーザインターフェースは、グラフィック、テキスト、アイコン、ビデオ、及びそれらの任意の組み合わせから構成されてもよい。表示ユニット６０４は、表示パネルを備えてもよい。任意選択的に、表示パネルは、液晶ディスプレイ（ＬＣＤ：Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）や有機発光ダイオード（ＯＬＥＤ：Ｏｒｇａｎｉｃ Ｌｉｇｈｔ－Ｅｍｉｔｔｉｎｇ Ｄｉｏｄｅ）などの形態で配置してもよい。さらに、タッチセンシティブ表面は、表示パネルを覆ってもよい。タッチセンシティブ表面は、その上又はその近くでのタッチ操作を検出すると、タッチイベントのタイプを決定するために、該タッチ操作をプロセッサ６０８に伝送する。次に、プロセッサ６０８は、タッチイベントのタイプに応じて、相応の視覚的出力を表示パネルに提供する。図１５において、タッチセンシティブ表面及び表示パネルは、２つの別個のコンポーネントとして、入力機能及び出力機能を実現するが、いくつかの実施例では、タッチセンシティブ表面及び表示パネルを統合して、入力機能及び出力機能を実現してもよい。

端末は、例えば、光センサ、モーションセンサ、及び他のセンサなどの少なくとも１種のセンサ６０５をさらに含んでもよい。具体的には、光センサは、環境光センサ及び近接センサを含んでもよい。環境光センサは、環境光の明るさに応じて表示パネルの輝度を調整することができ、近接センサは、端末が耳に近づくと、表示パネル及び／又はバックライトをオフにすることができる。モーションセンサの１種として、重力加速度センサは、各方向（通常、３軸）における加速度の大きさを検出でき、静止時に重力の大きさ及び方向を検出でき、端末の姿勢を認識するアプリケーション（例えば、画面の縦横切り替え、関連ゲーム、磁力計の姿勢キャリブレーション）、振動認識関連の機能（例えば、歩数計、タップ）などに利用可能である。端末に配置可能な他のセンサ、例えば、ジャイロスコープ、気圧計、湿度計、温度計、赤外線センサなどについては、ここでは説明を省略する。

オーディオ回路６０６、スピーカー、マイクロフォンは、ユーザと端末との間のオーディオインターフェースを提供することができる。オーディオ回路６０６は、受信されたオーディオデータから変換された電気信号をスピーカーに伝送することができる。スピーカーは、電気信号を音響信号に変換して出力する。一方、マイクロフォンは、収集された音響信号を電気信号に変換する。オーディオ回路６０６は、電気信号を受信してオーディオデータに変換し、オーディオデータをプロセッサ６０８に出力して、プロセッサ６０８によってオーディオデータを処理した後、ＲＦ回路６０１を介してオーディオデータを例えば他の端末に送信するか、又は、さらなる処理のために、オーディオデータをメモリ６０２に出力する。オーディオ回路６０６は、外付けイヤホンと端末との通信を提供するためのイヤホンジャックを含んでもよい。

ＷｉＦｉは、近距離無線伝送技術に属する。端末は、ＷｉＦｉモジュール６０７によって、ユーザによる電子メールの送受信、Ｗｅｂページの閲覧、及びストリーミングメディアのアクセスを助けることができる。ＷｉＦｉは、無線ブロードバンドインターネットアクセスをユーザに提供する。図１５にＷｉＦｉモジュール６０７を示しているが、理解できるように、ＷｉＦｉモジュール６０７は、端末の必須構成に属せず、必要に応じて、本願の本質を変更しない範囲内で完全に省略可能である。

プロセッサ６０８は、端末の制御センターであり、端末全体の各部分を様々なインターフェース及び回線で接続し、メモリ６０２に記憶されたコンピュータ可読命令及び／又はモジュールを実行又は遂行して、メモリ６０２に記憶されたデータを呼び出すことにより、端末の様々な機能を実行してデータを処理し、端末を全体的に監視制御する。任意選択的に、プロセッサ６０８は、１つ又は複数の処理コアを含んでもよい。好ましくは、プロセッサ６０８には、アプリケーションプロセッサ及びモデムプロセッサが統合されてもよい。ここで、アプリケーションプロセッサは、主にオペレーティングシステム、ユーザ画面、及びアプリケーションプログラムなどを処理し、モデムプロセッサは主に無線通信を処理する。理解できるように、上記モデムプロセッサは、プロセッサ６０８に統合されなくてもよい。

端末は、各コンポーネントに電力を供給する電源６０９（例えば、電池）をさらに含む。好ましくは、電源は、電源管理システムを介して、プロセッサ６０８に論理的に接続されてもよい。これにより、電源管理システムによって、充電、放電、及び電力消耗管理などの機能を実現する。電源６０９は、１つ又は複数の直流又は交流電源、再充電システム、電源故障検出回路、電源変換器又はインバータ、電源状態インジケータなどの任意のコンポーネントを含んでもよい。

図示されていないが、端末は、カメラ、ブルートゥースモジュールなども含んでもよいが、ここでは説明を省略する。具体的には、本実施例では、端末のプロセッサ６０８は、以下のコンピュータ可読命令に従って、１つ又は複数のアプリケーションプログラムのプロセスに対応する実行可能ファイルをメモリ６０２にロードする。また、プロセッサ６０８は、メモリ６０２に記憶されたアプリケーションプログラムを実行することにより、
ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分するステップと、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得するステップと、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得するステップと、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行うステップとの様々な機能を実現する。

任意選択的に、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得するステップは、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得するステップと、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得するステップと、を含んでもよい。

任意選択的に、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得するステップは、
第２探索アルゴリズムによって第２タイプの予測単位における第１未確定点を取得するステップと、第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得し、ポリゴンモデルに基づいて第１目標点を取得するステップと、第１目標点が第１未確定点と一致しない場合、ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得するステップと、最適点が第１目標点と一致する場合、最適点の位置を第２タイプの予測単位の現在動きベクトルとして設定するステップと、を含んでもよい。

任意選択的に、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得するステップは、
画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、第２タイプの予測単位における対応位置の第１目標レート歪みコストを算出するステップと、第２タイプの予測単位の現在動きベクトルに基づいて、第２タイプの予測単位の現在レート歪みコストを決定するステップと、第２タイプの予測単位の現在レート歪みコストを第１目標レート歪みコストと比較するステップと、第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを第２タイプの予測単位の動きベクトルとして設定するステップと、第２タイプの予測単位の現在レート歪みコストが第１目標レート歪みコスト以下である場合、現在レート歪みコストに対応する点の位置を第２タイプの予測単位の動きベクトルとして設定するステップと、を含んでもよい。

上記の各処理の具体的な実施については、前述した実施例を参照すればよいが、ここでは説明を省略する。

以上から分かるように、本願の実施例では、ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を分類し、例えば、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分することができる。異なるタイプの予測単位に対しては、異なる探索アルゴリズムを用いて、異なるタイプの予測単位の動きベクトルを取得し、例えば、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得し、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得する。その後、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行うことができる。この構成では、複数の予測単位を分類し、異なる探索アルゴリズムを用いて、異なるタイプの予測単位の動きベクトルを取得することができ、探索効率が高いため、異なる予測単位に対してすべて同じ処理方式を統一的に採用する従来技術よりも、ビデオの動き推定の効率及び柔軟性が向上する。

当業者であれば理解できるように、上記実施例の各方法におけるステップの全部又は一部は、コンピュータ可読命令によって実現されてもよいし、又はコンピュータ可読命令によって関連ハードウェアを制御することにより実現されてもよい。該コンピュータ可読命令は、コンピュータ可読記憶媒体に記憶され、プロセッサによってロード・実行されてもよい。

このため、本願の実施例では、複数のコンピュータ可読命令を記憶したコンピュータ可読記憶媒体が提供されている。該コンピュータ可読命令は、プロセッサによってロードされることで、本願の実施例で提供されたいずれか１つのビデオ動き推定方法のステップを実行させることが可能である。例えば、該コンピュータ可読命令は、
ビデオの画像フレームを複数の予測単位に分割し、複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分するステップと、第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得するステップと、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得するステップと、第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、画像フレームに対して小数画素動き推定を行うステップと、を実行させることが可能である。

任意選択的に、第２探索アルゴリズムによって第２タイプの予測単位の動きベクトルを取得するステップは、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得するステップと、画像フレームの探索済み予測単位の動きベクトルを取得し、探索済み予測単位の動きベクトルに基づいて、現在動きベクトルを補正することにより、第２タイプの予測単位の動きベクトルを取得するステップと、を含んでもよい。

任意選択的に、第２探索アルゴリズムによってポリゴンモデルを取得し、ポリゴンモデルを移動させることで第２タイプの予測単位の現在動きベクトルを取得するステップは、
第２探索アルゴリズムによって第２タイプの予測単位における第１未確定点を取得するステップと、第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、第１未確定点を中心とするポリゴンモデルを取得し、ポリゴンモデルに基づいて第１目標点を取得するステップと、第１目標点が第１未確定点と一致しない場合、ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得するステップと、最適点が第１目標点と一致する場合、最適点の位置を第２タイプの予測単位の現在動きベクトルとして設定するステップと、を含んでもよい。

上記の各処理の具体的な実施については、前述した実施例を参照すればよいが、ここでは説明を省略する。

ここで、該記憶媒体は、読み取り専用メモリ（ＲＯＭ：Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ランダムアクセスメモリ（ＲＡＭ：Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、磁気ディスク、又は光ディスクなどを含んでもよい。

該記憶媒体に記憶されたコンピュータ可読命令は、本願の実施例で提供されたいずれか１つのビデオ動き推定方法のステップを実行させることが可能であるので、本願の実施例で提供されたいずれか１つのビデオ動き推定方法によって達成できる有益な効果を達成させることができる。その詳細については、前述した実施例を参照すればよいが、ここでは説明を省略する。

以上、本願の実施例で提供されたビデオ動き推定方法、装置、及びシステムについて詳細に説明した。本明細書では、本願の原理及び実施形態を説明するために具体例を使用したが、以上の実施例の説明は、本願の方法及びその主旨の理解を助けるためにのみ使用される。また、当業者にとっては、本願の構想に基づき、具体的な実施形態及び適用範囲のいずれにも変更があり得る。上述のように、本明細書の内容は、本願を制限するものと理解されるべきではない。

４０１ 分割ユニット
４０２ 第１取得ユニット
４０３ 第２取得ユニット
４０４ 動き推定ユニット
４０２１ 第２取得サブユニット
４０２２ 算出サブユニット
４０２３ 第３取得サブユニット
４０２４ 第３設定サブユニット
４０２５ 第４設定サブユニット
４０３１ 第１取得サブユニット
４０３２ 補正サブユニット
６０１ 無線周波数回路
６０２ メモリ
６０３ 入力ユニット
６０４ 表示ユニット
６０５ センサ
６０６ オーディオ回路
６０７ ＷｉＦｉモジュール
６０８ プロセッサ
６０９ 電源

Claims (17)

1. 端末が実行するビデオ動き推定方法であって、
   ビデオの画像フレームを複数の予測単位に分割し、前記複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分するステップと、
   第１探索アルゴリズムによって前記第１タイプの予測単位の動きベクトルを取得するステップと、
   第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得するステップであって、前記第２探索アルゴリズムが前記第１探索アルゴリズムと異なる、ステップと、
   第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、前記画像フレームに対して小数画素動き推定を行うステップと、
   を含み、
   第１探索アルゴリズムによって第１タイプの予測単位の動きベクトルを取得するステップは、
   第１タイプの予測単位に対応する第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定するステップと、
   第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得するステップと、
   前記第２未確定点に対応する探索ステップサイズが第２所定ステップサイズである場合、ステップサイズが前記第２所定ステップサイズである各点の周囲にある未探索の第２補足点を取得し、前記第２補足点のレート歪みコストを算出するステップと、
   前記第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が前記第２未確定点である場合、前記第２未確定点の位置を前記第１タイプの予測単位の動きベクトルとして設定するステップと、
   前記第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が前記第２未確定点ではない場合、前記第２未確定点及び第２補足点のうちレート歪みコストが最小となる点の位置を前記第１タイプの予測単位の動きベクトルとして設定するステップと、
   を含み、
   前記第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得するステップは、
   前記第２探索アルゴリズムによってポリゴンモデルを取得し、前記ポリゴンモデルを移動させることで前記第２タイプの予測単位の現在動きベクトルを取得するステップと、
   前記画像フレームの探索済み予測単位の動きベクトルを取得し、前記探索済み予測単位の動きベクトルに基づいて前記現在動きベクトルを補正することにより、前記第２タイプの予測単位の動きベクトルを取得するステップと、
   を含むことを特徴とするビデオ動き推定方法。
2. 前記第２探索アルゴリズムによってポリゴンモデルを取得し、前記ポリゴンモデルを移動させることで前記第２タイプの予測単位の現在動きベクトルを取得するステップは、
   前記第２探索アルゴリズムによって前記第２タイプの予測単位における第１未確定点を取得するステップと、
   前記第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、前記第１未確定点を中心とするポリゴンモデルを取得し、前記ポリゴンモデルに基づいて第１目標点を取得するステップと、
   前記第１目標点が前記第１未確定点と一致する場合、前記第１目標点の位置を前記第２タイプの予測単位の現在動きベクトルとして設定するステップと、
   前記第１目標点が前記第１未確定点と一致しない場合、前記ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得し、前記最適点が前記第１目標点と一致する場合、前記最適点の位置を前記第２タイプの予測単位の現在動きベクトルとして設定するステップと、
   を含むことを特徴とする請求項１に記載のビデオ動き推定方法。
3. 前記第１目標点が前記第１未確定点と一致しない場合、前記ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得するステップは、
   前記第１目標点が前記第１未確定点と一致しない場合、前記ポリゴンモデルの中心を前記第１目標点の位置に移動させるステップと、
   移動させたポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最も小さい点を選別することにより、最適点を取得するステップと、
   を含むことを特徴とする請求項２に記載のビデオ動き推定方法。
4. 前記第２探索アルゴリズムによって前記第２タイプの予測単位における第１未確定点を取得するステップは、
   前記第２探索アルゴリズムによって、前記第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップ
   を含み、
   前記第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、前記第１未確定点を中心とするポリゴンモデルを取得し、前記ポリゴンモデルに基づいて第１目標点を取得するステップは、
   前記第１未確定点に対応する探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、前記第１未確定点を中心とするポリゴンモデルを取得するステップと、
   前記ポリゴンモデルの中心及び各々の頂点の中から、レート歪みコストが最小となる点を選択することにより、第１目標点を取得するステップと、
   を含むことを特徴とする請求項２に記載のビデオ動き推定方法。
5. 前記第２探索アルゴリズムによって、前記第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップは、
   前記第２探索アルゴリズムによって、第２タイプの予測単位に対応する第１候補探索開始点を取得するステップと、
   各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定するステップと、
   第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで取得するステップと、
   複数の第１候補点の中から、レート歪みコストが最小となる点を選別することにより、第１未確定点を取得するステップと、
   を含むことを特徴とする請求項４に記載のビデオ動き推定方法。
6. 前記第２タイプの予測単位は、第１分割ブロックと第２分割ブロックとを含み、
   前記第２探索アルゴリズムによって、第２タイプの予測単位に対応する第１候補探索開始点を取得するステップは、
   前記第２探索アルゴリズムによって、高度動きベクトル予測で第２タイプの予測単位の第２分割ブロックに対応する第１候補探索開始点を取得するステップ
   を含み、
   各第１候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第１候補探索開始点を第１探索開始点として設定するステップは、
   第２タイプの予測単位の第１分割ブロックの予測が完了すると、第１分割ブロックの予測結果を取得し、各第１候補探索開始点のレート歪みコストを算出し、前記第１分割ブロックの予測結果に基づいて、前記第１分割ブロックの位置のレート歪みコストを算出するステップと、
   前記第１候補探索開始点及び第１分割ブロックの中から、レート歪みコストが最小となる点を取得するステップと、
   取得された、レート歪みコストが最小となる点を、前記第２タイプの予測単位の第２分割ブロックの探索開始点として設定し、前記第２分割ブロックの探索開始点を第１探索開始点として設定するステップと、
   を含むことを特徴とする請求項５に記載のビデオ動き推定方法。
7. 前記第２探索アルゴリズムによって、前記第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップの後、
   前記第１未確定点に対応する探索ステップサイズが第１所定ステップサイズである場合、ステップサイズが前記第１所定ステップサイズである各点の周囲にある未探索の第１補足点を取得し、前記第１補足点のレート歪みコストを算出するステップと、
   前記第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が前記第１未確定点である場合、前記第１未確定点の位置を前記第２タイプの予測単位の現在動きベクトルとして設定するステップと、
   前記第１未確定点及び第１補足点のうちレート歪みコストが最小となる点が前記第１未確定点ではない場合、前記第１未確定点及び第１補足点のうちレート歪みコストが最小となる点の位置を前記第２タイプの予測単位の現在動きベクトルとして設定するステップと、
   をさらに含むことを特徴とする請求項４に記載のビデオ動き推定方法。
8. 前記第２探索アルゴリズムによって、前記第２タイプの予測単位においてレート歪みコストが最小となる点を取得することにより、第１未確定点を取得するステップの後、
   前記第１未確定点に対応する探索ステップサイズが第２所定ステップサイズ閾値の範囲内である場合、前記第１未確定点を第１探索開始点として設定し、第１探索開始点を中心とする探索ウィンドウの範囲内で、複数の第１候補点を第１所定インクリメンタルステップサイズで取得するステップに戻るステップ、
   をさらに含むことを特徴とする請求項４に記載のビデオ動き推定方法。
9. 前記画像フレームの探索済み予測単位の動きベクトルを取得し、前記探索済み予測単位の動きベクトルに基づいて前記現在動きベクトルを補正することにより、前記第２タイプの予測単位の動きベクトルを取得するステップは、
   前記画像フレームの探索済み予測単位の動きベクトルを取得し、前記探索済み予測単位の動きベクトルに基づいて、前記第２タイプの予測単位における対応位置の第１目標レート歪みコストを算出するステップと、
   前記第２タイプの予測単位の現在動きベクトルに基づいて、前記第２タイプの予測単位の現在レート歪みコストを決定するステップと、
   前記第２タイプの予測単位の現在レート歪みコストを前記第１目標レート歪みコストと比較するステップと、
   前記第２タイプの予測単位の現在レート歪みコストが前記第１目標レート歪みコストよりも大きい場合、前記探索済み予測単位の動きベクトルを前記第２タイプの予測単位の動きベクトルとして設定するステップと、
   前記第２タイプの予測単位の現在レート歪みコストが前記第１目標レート歪みコスト以下である場合、前記現在レート歪みコストに対応する点の位置を前記第２タイプの予測単位の動きベクトルとして設定するステップと、
   を含むことを特徴とする請求項１～８のいずれか１項に記載のビデオ動き推定方法。
10. 前記第２未確定点の位置を前記第１タイプの予測単位の動きベクトルとして設定するステップは、
    前記画像フレームの探索済み予測単位の動きベクトルを取得し、前記探索済み予測単位の動きベクトルに基づいて、前記第１タイプの予測単位における対応位置の第２目標レート歪みコストを算出するステップと、
    前記第２未確定点のレート歪みコストを第２目標レート歪みコストと比較するステップと、
    前記第２未確定点のレート歪みコストが第２目標レート歪みコストよりも大きい場合、探索済み予測単位の動きベクトルを前記第１タイプの予測単位の動きベクトルとして設定するステップと、
    前記第２未確定点のレート歪みコストが第２目標レート歪みコスト以下である場合、前記第２未確定点の位置を前記第１タイプの予測単位の動きベクトルとして設定するステップと、
    を含むことを特徴とする請求項１に記載のビデオ動き推定方法。
11. 前記第１タイプの予測単位は、第３分割ブロックと第４分割ブロックとを含み、
    前記第１タイプの予測単位に対応する第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定するステップは、
    高度動きベクトル予測で第１タイプの予測単位の第４分割ブロックに対応する第２候補探索開始点を取得するステップと、
    第１タイプの予測単位の第３分割ブロックの予測が完了すると、第３分割ブロックの予測結果を取得し、各第２候補探索開始点のレート歪みコストを算出し、第３分割ブロックの予測結果に基づいて前記第３分割ブロックの位置のレート歪みコストを算出するステップと、
    前記第２候補探索開始点及び第３分割ブロックにおいてレート歪みコストが最小となる点を第１タイプの予測単位の第４分割ブロックの探索開始点として設定し、前記第４分割ブロックの探索開始点を第２探索開始点として設定するステップと、
    を含むことを特徴とする請求項１に記載のビデオ動き推定方法。
12. ビデオ動き推定装置であって、
    ビデオの画像フレームを複数の予測単位に分割し、前記複数の予測単位を第１タイプの予測単位と第２タイプの予測単位とに区分する分割ユニットと、
    第１探索アルゴリズムによって前記第１タイプの予測単位の動きベクトルを取得する第１取得ユニットと、
    第２探索アルゴリズムによって前記第２タイプの予測単位の動きベクトルを取得する第２取得ユニットであって、前記第２探索アルゴリズムが前記第１探索アルゴリズムと異なる、第２取得ユニットと、
    第１タイプの予測単位の動きベクトルと第２タイプの予測単位の動きベクトルとに基づいて、前記画像フレームに対して小数画素動き推定を行う動き推定ユニットと、
    を備え、
    前記第１取得ユニットは、
    第１タイプの予測単位に対応する第２候補探索開始点を取得し、各第２候補探索開始点のレート歪みコストを算出し、レート歪みコストが最小となる第２候補探索開始点を第２探索開始点として設定する第２取得サブユニットと、
    第２探索開始点を中心とする探索ウィンドウの範囲内で、複数の第２候補点を第２所定インクリメンタルステップサイズで取得し、各第２候補点のレート歪みコストを算出し、複数の第２候補点の中から、レート歪みコストが最小となる点を選別することにより、第２未確定点を取得する算出サブユニットと、
    前記第２未確定点に対応する探索ステップサイズが第２所定ステップサイズである場合、ステップサイズが前記第２所定ステップサイズである各点の周囲にある未探索の第２補足点を取得し、前記第２補足点のレート歪みコストを算出する第３取得サブユニットと、
    前記第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が前記第２未確定点である場合、前記第２未確定点の位置を前記第１タイプの予測単位の動きベクトルとして設定する第３設定サブユニットと、
    前記第２未確定点及び第２補足点のうちレート歪みコストが最小となる点が前記第２未確定点ではない場合、前記第２未確定点を第２探索開始点として設定する第４設定サブユニットと、
    を備え、
    前記第２取得ユニットは、
    前記第２探索アルゴリズムによってポリゴンモデルを取得し、前記ポリゴンモデルを移動させることで前記第２タイプの予測単位の現在動きベクトルを取得する第１取得サブユニットと、
    前記画像フレームの探索済み予測単位の動きベクトルを取得し、前記探索済み予測単位の動きベクトルに基づいて前記現在動きベクトルを補正することにより、前記第２タイプの予測単位の動きベクトルを取得する補正サブユニットと、
    を備えることを特徴とするビデオ動き推定装置。
13. 前記第１取得サブユニットは、
    前記第２探索アルゴリズムによって前記第２タイプの予測単位における第１未確定点を取得する探索モジュールと、
    前記第１未確定点の探索ステップサイズが第１所定ステップサイズ閾値の範囲内である場合、前記第１未確定点を中心とするポリゴンモデルを取得し、前記ポリゴンモデルに基づいて第１目標点を取得する取得モジュールと、
    前記第１目標点が前記第１未確定点と一致しない場合、前記ポリゴンモデルを移動させ、移動させたポリゴンモデルに基づいて最適点を取得する移動モジュールと、
    前記最適点が前記第１目標点と一致する場合、前記最適点の位置を前記第２タイプの予測単位の現在動きベクトルとして設定する第１設定モジュールと、
    を備えることを特徴とする請求項１２に記載のビデオ動き推定装置。
14. 前記第１取得ユニットは、
    前記第２未確定点に対応する探索ステップサイズが第３所定ステップサイズ閾値の範囲内である場合、前記第２未確定点を中心とする所定範囲内で、所定間隔であるステップサイズで探索することにより、複数の探索点を取得し、各探索点のレート歪みコストを算出する探索サブユニットと、
    前記第２未確定点及び複数の探索点のうちレート歪みコストが最小となる点を第２探索開始点とする第１実行サブユニットと、
    を備えることを特徴とする請求項１２に記載のビデオ動き推定装置。
15. メモリとプロセッサとを備える端末であって、前記メモリには、コンピュータ可読命令が記憶され、前記コンピュータ可読命令は、１つ又は複数のプロセッサにより実行されると、前記１つ又は複数のプロセッサに、請求項１～１１のいずれか１項に記載のビデオ動き推定方法のステップを実行させる端末。
16. コンピュータ可読命令を記憶した不揮発性コンピュータ可読記憶媒体であって、前記コンピュータ可読命令は、１つ又は複数のプロセッサにより実行されると、前記１つ又は複数のプロセッサに、請求項１～１１のいずれか１項に記載のビデオ動き推定方法のステップを実行させるコンピュータ可読記憶媒体。
17. 請求項１～１１のいずれか１項に記載のビデオ動き推定方法を端末に実行させるコンピュータプログラム。

Images