JP4410172B2 - 動きベクトル推定方法，動きベクトル推定装置，動きベクトル推定プログラムおよび動きベクトル推定プログラム記録媒体 - Google Patents

Description

本発明は，高能率画像信号符号化技術に関し，特に，小数画素精度動き補償における動きベクトルの探索を高速に行うための技術に関するものである。

動画像符号化における重要な技術の一つにブロックマッチングに基づく動き補償（ＭＣ）がある。この方法では，符号化対象フレームｆ_t （ｐ）（ｐ∈｛（ｘ，ｙ）｜ｘ＝０，１，... ，Ｘ−１，ｙ＝０，１，... ，Ｙ−１｝）をいくつかの領域に分割し，領域毎に動き補償（ＭＣ）を用いた次のようなフレーム間予測が行われる。

ここで，Ｂ_i は第ｉ番目の領域であり，ｖ_i は次式を満たす動きベクトルである。

なお，Ｒ_i はＢ_i に対応する探索領域であり，

は，次に続く関数を最小化するｖを返す。すなわち，探索範囲Ｒ_i において，領域Ｂ_i 内での予測誤差を最小化するｖが動きベクトルｖ_i として選ばれる。

予測誤差の最小性を保証した動きベクトル探索の高速化として，代表的なものにＳＥＡ（非特許文献１参照）と呼ばれる手法がある。同手法は，ＭＣ誤差の下限値を予め見積もり，その下限値をもとに探索点を絞り込む手法である。同手法ではＭＣ誤差Ｅ（ｖ）に対して，次式の下限値を用いる。

Ｅ（ｖ）≧Ｃ−Ｓ（ｖ） （２）
ここで，Ｃは符号化ブロックの画素値和，Ｓ（ｖ）は参照ブロックの画素値和であり，各々次式で表される。

式（２）の証明は，以下の通りである。

予測誤差の低減を目的として，動きベクトルを小数画素精度で表現する動き補償が検討されている。１／ｍ画素精度の動き補償の場合，動きベクトルは次式を満たすベクトルとして求める。

ここで，ｆ^* _t-1 （ｐ）はｆ_t-1 （ｐ）から生成される補間画像であり，１／ｍ画素間隔で画素値をもつ。例えば，ISO/IEC 13818-2 ＭＰＥＧ−２における１／２画素精度の動き補償の場合，次のような補間画像を用いる。

ここで，δ_x ＝（１，０），δ_y ＝（０，１）であり，ｐは整数値を要素とするベクトルである。つまり，予測時の参照フレームの位置が２画素の中心なら（式（７ｂ）または式（７ｃ）），２つの画素値の丸め付き平均を予測値として使用し，同位置が正方形の頂点に並んだ４画素の中心なら，４つの画素値の丸め付き平均を予測値として使用することになる（式（７ｄ））。なお，式（７ｂ）〜式（７ｄ）における１／２および２／４の演算は，例えばビットシフト演算によって行われ，小数点以下は切り捨てられる。

図１は，式（７ｂ）〜式（７ｄ）の補間処理における参照画素位置を示している。例えば図１（ａ）は，補間画素位置が水平半画素位置の場合であり，矢印で示した円形がその補間画素位置である。黒い四角形が補間に用いる参照画素位置であり，この黒い四角形の側に示した数字は補間時の重み係数を表している。また，図１（ｂ）は，補間画素位置が垂直半画素位置の場合を，図１（ｃ）は，補間画素位置が対角半画素位置の場合を示している。

以後，式（１）より求めた動きベクトルを用いる動き補償を整数画素精度ＭＣと呼ぶ。一方，式（６）より求めた動きベクトルを用いる動き補償を小数画素精度ＭＣと呼ぶ。また，ｉ番目の領域に注目して議論するので，Ｂ_i はＢと表す。

小数画素精度ＭＣの場合，整数画素精度ＭＣに比較して動きベクトル探索の計算量が増大する。これは，探索領域内に含まれる探索点の数が増加するためである。探索領域が水平方向ｗ，垂直方向ｈのｗ×ｈ点の画素を含む場合，整数画素精度ＭＣにおける探索点がｗ×ｈ点であるのに対し，１／ｍ画素精度の小数画素精度ＭＣにおける探索点は｛ｍ（ｗ−１）＋１｝×｛ｍ（ｈ−１）＋１｝点となる。

小数画素精度ＭＣの動きベクトル探索において計算量を低減させる場合，最適解である式（６）の動きベクトルを求めることをあきらめ，式（６）の準最適解に相当する動きベクトルを求める方法が多く検討されている。この場合，計算量の低減と引き替えに，予測誤差は増加してしまう。しかし，予測誤差を減少させるために導入された小数画素精度ＭＣにおいて，こうした予測誤差の増加は望ましくない。このため，予測誤差を増加させることなく計算量を低減させる動きベクトル探索法が必要となる。

計算量を低減させる手法としては，上述した非特許文献１に示されているＳＥＡがあるが，ＳＥＡは整数画素精度ＭＣへの適用にとどまり，小数画素精度ＭＣについての検討はなされていない。

そこで，本発明者等は，小数画素精度ＭＣについても，予測誤差の最小化を保証した上で，下限値との比較による動きベクトル探索の枝刈りを行い，計算量の低減を図る技術を，非特許文献２において提案している。非特許文献２の手法によれば，特に小数ＭＣ誤差の下限値を求める際に，既に計算した結果を利用することにより計算量の増加を抑え，少ない計算量で小数画素精度ＭＣのもつ高い予測性能を実現することができる。
W.Li and E.Salari ："Successive elimination algorithm for motion estimation"，IEEE Transactions on Image Processing ，Volume 4，Issue 1 ，Jan.，pp.105-107，1995． 坂東幸浩，高村誠之，八島由幸：「全探索小数画素精度動き推定の高速化」，情報処理学会研究報告，2004-AVM-44 ，2004/3/4．

上述のように，非特許文献２に記載された「全探索小数画素精度動き推定の高速化」の技術によれば，ＳＥＡの小数画素精度ＭＣへの適用にあたって，探索点数の増加に伴う計算量増加の問題が軽減され，小数画素精度ＭＣにおける動きベクトル探索の高速化が図られている。

本発明は，非特許文献２に記載された「全探索小数画素精度動き推定の高速化」の技術を，さらに改良し，小数画素精度の動き推定におけるＭＣ誤差の下限値の計算において，参照画素値和の計算上生じる丸め誤差も考慮して，タイトな下限値を算出することにより，探索における枝刈りの促進を図り，小数画素精度ＭＣにおける動きベクトル探索のさらなる高速化を実現することを目的とする。

また，本発明は，上記丸め誤差の算出を少ない計算量で行い，計算量の増加を抑えた動きベクトルの推定を実現することを目的とする。

二つの動きベクトルｖ，ｕのＭＣ誤差を比較する場合，両動きベクトルに対するＭＣ誤差を直接比較するのではなく，動きベクトルｖのＭＣ誤差Ｅ（ｖ）に対して，動きベクトルｕのＭＣ誤差Ｅ（ｕ）の下限値Ｌ（ｕ）との大小比較を行う。この時，
Ｅ（ｖ）≦Ｌ（ｕ）
であれば，Ｌ（ｕ）がＭＣ誤差Ｅ（ｕ）の下限値であるため，
Ｅ（ｖ）≦Ｅ（ｕ）
となり，Ｅ（ｕ）を算出して比較する必要はない。つまり，Ｅ（ｕ）の算出は，
Ｌ（ｕ）＜Ｅ（ｖ）
となる場合のみ行えば十分である。

後述するように，ＭＣ誤差の下限値はＭＣ誤差に比べて，少ない計算量での算出が可能である。このため，ＭＣ誤差の下限値との比較を行い，ＭＣ誤差の算出を省くことにより，予測誤差の最小化を保証した上で，計算量の低減を図ることができる。

本発明は，小数画素精度ＭＣにおいて，フレーム間予測誤差に対する下限値を算出し，下限値を用いた探索の枝刈りを行うとともに，この下限値を算出する際，既に計算済みの加算結果およびシフト演算等を用いて，丸め誤差を算出し，その丸め誤差を用いて下限値を算出する。丸め誤差を考慮した下限値の算出を行うことにより，さらにタイトな枝刈りが可能であり，全探索を行った場合と同等の精度を保持しつつ，大きく計算量を低減することができる。

また，本発明は，上記下限値を算出する際，関連する参照画素群の下位ｎビット（ｎは補間処理で参照される画素数により定まる数）の値に応じて，丸め誤差を予めルックアップテーブルに格納しておき，同テーブルを参照して丸め誤差の補正値を決定し，下限値を算出することにより，さらに計算量を低減することができる。

また，丸め誤差をルックアップテーブルに格納する際，補間処理の対象となる小数画素位置に応じて個別のルックアップテーブルに格納することにより，ルックアップテーブルに必要となるメモリ容量を小さくすることができる。

また，本発明は，予測誤差の下限値を算出する際，２つの動きベクトルが指す参照領域の差異部分のみに注目し，２つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し，一方の動きベクトルの予測誤差の下限値をもとに，他方の動きベクトルに対する予測誤差の下限値を算出する。これにより，計算済みの結果を利用して計算量の低減を図ることができる。

また，本発明は，予測誤差の下限値を算出する際，上記２つの動きベクトルが指す参照領域の差異部分に対する丸め誤差をルックアップテーブルに格納しておき，同テーブルを参照し，一方の動きベクトルに対する予測誤差の下限値をもとに，他方の動きベクトルに対する予測誤差の下限値を算出する。ルックアップテーブルを利用して差異部分に対する丸め誤差を求めることにより，計算量を大幅に低減することができる。

本発明を用いれば，小数画素精度ＭＣにおける予測誤差の最小化を完全に保証しつつ，動きベクトル探索における計算量の低減が可能となる。このため，小数画素精度ＭＣにおいて問題とされてきた計算量の増加を解消でき，少ない計算量で，小数画素精度ＭＣによる高い予測性能を享受できる。特に，補間処理の対象となる小数画素位置の参照画素値の計算において生じる丸め誤差を求め，これにより補正した下限値を算出することにより，探索における枝刈りの効果が大きい。

［第１の実施形態］
小数画素精度の動きベクトルｖ^* に対するＭＣ誤差（小数画素精度ＭＣ誤差）の下限値を導出する。以下では，式（７ａ）〜（７ｄ）の補間画像を用いる１／２画素精度ＭＣを例にあげ，説明する。このとき，動きベクトルｖ^* の取り得る値は次の４通りである。

ここで，δ_x ＝（１，０），δ_y ＝（０，１）であり，ｖは整数値を要素とするベクトルである。なお，以下では，動きベクトルｖ^* がｖ^* ＝ｖとして整数値を要素とする場合，整数動きベクトルと呼び，それ以外を小数動きベクトルと呼ぶ。以下，ｖ^* の値に応じてＥ（ｖ^* ）を４通りに場合分けし，各下限値を求める。

（ｉ）ｖ^* ＝ｖの場合：
動きベクトルは参照フレーム中の画素位置を指すため，整数画素精度ＭＣにおけるＳＥＡの場合と同様に，ＭＣ誤差は次の下限値を持つ。

Ｅ（ｖ^* ）≧Ｃ−Ｓ（ｖ） （９）
ここで，Ｃ，Ｓ（ｖ）は，各々式（３），式（４）で表されるものとする。

（ii）ｖ^* ＝ｖ−δ_x ／２の場合：
動きベクトルの指す参照フレームの位置は２画素の中心となり，ＭＣ誤差Ｅ（ｖ^* ）は次の下限値を持つ。

Ｅ（ｖ^* ）≧Ｃ−Ｓ（ｖ）／２−Ｓ（ｖ−δ_x ）／２−Ｒ_h （ｖ） （１０）
ここで，Ｒ_h （ｖ）は丸め誤差の補正値であり，次式より求まる。

ここで，○付きの＋はビット毎の論理積を行う演算子を表す。

式（１０）の証明は，以下の通りである。なお，以下の証明において，式（１２ａ）から式（１２ｂ）への展開では，動きベクトルの指す参照フレームの位置は２画素の中心となることから，式（７ｂ）を用いた。

(iii) ｖ^* ＝ｖ−δ_y ／２の場合：
上述の（ii）と同様に動きベクトルの指す参照フレームの位置は２画素の中心となり，ＭＣ誤差は次の下限値を持つ。

Ｅ（ｖ^* ）≧Ｃ−Ｓ（ｖ）／２−Ｓ（ｖ−δ_y ）／２−Ｒ_v （ｖ） （１３）
証明は（ii）の場合と同様に行える。なお，Ｒ_v （ｖ）は丸め誤差の補正値であり，次式より求まる。

（iv）ｖ^* ＝ｖ−（δ_x ＋δ_y ）／２の場合：
動きベクトルの指す参照フレームの位置は４画素の中央となり，ＭＣ誤差は次の下限値を持つ。

Ｅ（ｖ^* ）≧Ｃ−Ｓ（ｖ）／４−Ｓ（ｖ−δ_x ）／４−Ｓ（ｖ−δ_y ）／４
−Ｓ（ｖ−δ_x −δ_y ）／４−Ｒ_d （ｖ） （１５）
なお，Ｒ_d （ｖ）は丸め誤差の補正値であり，次式より求まる。

式（１５）の証明は，以下の通りである。なお，以下の証明において，式（１７ａ）から式（１７ｂ）への展開では，動きベクトルの指す参照フレームの位置は４画素の中央となることから，式（７ｄ）を用いた。

以上（ｉ）〜（iv）をまとめると，ＭＣ誤差の下限値Ｌ（ｖ^* ）は次式となる。

［第２の実施形態：補正値テーブルの利用］
丸め誤差の補正値は補正値テーブルと呼ぶルックアップテーブルに格納し，予測誤差の下限値の計算時には，同テーブルを参照するものとする。以下，同テーブルの作成法について詳述する。

上述（ii）の場合：
Ｒ_h （ｖ）は，以下のように展開できる。

この式（１９）から明らかであるように，参照領域をｘ方向に１７画素，ｙ方向に１画素の幅を持つ１７×１画素の矩形領域に分割したとすると，各矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。

この補正値は，１７の画素の下位１ビットから定まり，０から１６の値を取り得る。従って，この補正値に対するルックアップテーブルのサイズは，
５×２¹⁷＝０．６５５３６［Ｍｂｉｔｓ］
となる。

上述 (iii)の場合：
Ｒ_v （ｖ）は，以下のように展開できる。

この式（２１）から明らかであるように，各列における丸め誤差は独立に定まる。すなわち，参照領域をｘ方向に１画素，ｙ方向に１７画素の幅を持つ１×１７画素の矩形領域に分割したとすると，各矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。

この補正値は，１７個の画素の下位１ビットから定まり，０から１６の値を取り得る。従って，この補正値に対するルックアップテーブルのサイズは，
５×２¹⁷＝０．６５５３６［Ｍｂｉｔｓ］
となる。

上述（iv）の場合：
Ｒ_d （ｖ）は，以下のように展開できる。

ここで，Φ（ｘ，ｙ，ｔ）は，以下の通りとする。

Φ（ｘ，ｙ，ｔ）＝ｆ_t （ｘ，ｙ）＋ｆ_t （ｘ−１，ｙ）
＋ｆ_t （ｘ，ｙ−１）＋ｆ_t （ｘ−１，ｙ−１）
この式（２３）から明らかであるように，参照領域中の，ｘ方向に１７画素，ｙ方向に２画素の幅を持つ１７×２画素の矩形領域における丸め誤差は独立に定まる。しかし，この矩形領域に対して補正値のルックアップテーブルを作成した場合，同ルックアップテーブルのサイズは８５．８９９［Ｇｂｉｔｓ］となり，実装を考慮した場合，現実的なサイズとはいえない。そこで，同矩形領域を２つに分割し，２×８画素の矩形領域単位で補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。

ｒ_d （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ）に格納する補正値は，１８個の画素の下位１ビットから定まり，０から８の値を取り得る。従って，このルックアップテーブルのサイズは，
４×２¹⁸＝１．０４８６［Ｍｂｉｔｓ］
となる。

［第３の実施形態］
連続した動きベクトルに対する予測誤差の最小値を求める場合，隣接参照領域における差異領域に注目することで計算量を削減できる。予測誤差の下限値が式（１８）で与えられる場合，Ｌ（ｖ^* −δ_x ）とＬ（ｖ^* ）とは，以下の関係にある。

ここで，Ｓ^* （ｖ^* ），Ｒ^* （ｖ^* ）は，以下の通りである。

図２，図３，図４に動きベクトルｖ^* −δ_x およびｖ^* の指す領域を示す。これらは，いずれも動き補償の領域が４×４［画素］の例を図示したものである。

Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）が計算すべき補正値である。以下，ｖ^* の値に応じて，Ｓ^* （ｖ^* −δ_x ）−Ｓ^* （ｖ^* ），Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）の計算法について詳述する。以下，動き補償の領域は１６×１６とする。

（ｉ）ｖ^* ＝ｖの場合：
この場合，丸め誤差は発生しないため，補正値は必要ない。また，Ｓ^* （ｖ^* −δ_x ）−Ｓ^* （ｖ^* ）は次式のようになる。

（ii）ｖ^* ＝ｖ−δ_x ／２の場合：
Ｓ^* （ｖ^* −δ_x ）−Ｓ^* （ｖ^* ）は次式となる。

また，Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）は次式となる。

(iii) ｖ^* ＝ｖ−δ_y ／２の場合：
Ｓ^* （ｖ^* −δ_y ）−Ｓ^* （ｖ^* ）は次式となる。

また，Ｒ^* （ｖ^* −δ_y ）−Ｒ^* （ｖ^* ）は次式となる。

（iv）ｖ^* ＝ｖ−δ_x ／２−δ_y ／２の場合：
Ｓ^* （ｖ^* −δ_x −δ_y ）−Ｓ^* （ｖ^* ）は次式となる。

また，Ｒ^* （ｖ^* −δ_x −δ_y ）−Ｒ^* （ｖ^* ）は次式となる。

［第４の実施形態：差分補正値テーブルの利用］
連続した動きベクトルに対する予測誤差の最小値を求める場合，隣接参照領域における差異領域に注目することで計算量を削減できる。このときに用いる丸め誤差の補正値は差分補正値テーブルと呼ぶルックアップテーブルに格納し，予測誤差の下限値の計算時には，同テーブルを参照するものとする。

予測誤差の下限値が式（１８）で与えられる場合，Ｌ（ｖ^* −δ_x ）とＬ（ｖ^* ）とは前述の式（２５）の関係にある。Ｓ^* （ｖ^* −δ_x ）−Ｓ^* （ｖ^* ）については，前述した「第３の実施形態：丸め誤差の補正値」の通りである。Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）が差分補正値テーブルに格納される値となる。以下，ｖ^* の値に応じて，同テーブルの作成法について詳述する。

（ｉ）ｖ^* ＝ｖの場合：
この場合，丸め誤差は発生しないため，補正値は必要ない。

（ii）ｖ^* ＝ｖ−δ_x ／２の場合：
Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）は式（３０）となる。同式によれば，ｘ方向に２画素，ｙ方向に１６画素の幅を持つ２×１６画素の矩形領域における丸め誤差は独立に定まる。この矩形領域に対する補正値のルックアップテーブルのサイズが実装するシステムに対して大きすぎる場合は，同矩形領域を２つに分割し，２×８画素の矩形領域単位で補正値をルックアップテーブル＾ｒ_h （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）に格納する。＾ｒ_h （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）を，

として定義すると，Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）は次式のように表せる。

(iii) ｖ^* ＝ｖ−δ_y ／２の場合：
Ｒ^* （ｖ^* −δ_y ）−Ｒ^* （ｖ^* ）は式（３２）となる。同式によれば，ｘ方向に１画素，ｙ方向に１７画素の幅を持つ１×１７画素の矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で補正値をルックアップテーブル＾ｒ_v （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）に格納する。＾ｒ_v （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）を，

として定義すると，Ｒ^* （ｖ^* −δ_y ）−Ｒ^* （ｖ^* ）は次式のように表せる。

（iv）ｖ^* ＝ｖ−δ_x ／２−δ_y ／２の場合：
Ｒ^* （ｖ^* −δ_x −δ_y ）−Ｒ^* （ｖ^* ）は式（３４）となる。同式によれば，ｘ方向に２画素，ｙ方向に１７画素の幅を持つ２×１７画素の矩形領域における丸め誤差は独立に定まる。この矩形領域に対する補正値のルックアップテーブルのサイズが実装するシステムに対して大きすぎる場合は，同矩形領域を２つに分割し，２×８画素の矩形領域単位で補正値をルックアップテーブル＾ｒ_d （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）に格納する。＾ｒ_d （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）を，

として定義すると，Ｒ^* （ｖ^* −δ_x −δ_y ）−Ｒ^* （ｖ^* ）は次式のように表せる。

［符号化処理の流れ］
本発明の実施例に係る符号化処理の流れについて，図５を参照して説明する。

ステップＳ１：被予測画素，参照画素，初期動きベクトルを入力とし，初期動きベクトルとして指定された動きベクトルｖ^* に対して，予測誤差Ｅ（ｖ^* ）を計算し，それを出力する。

ステップＳ２：被予測画素を入力とし，被予測画素値和をレジスタに書き出す。より具体的には，被予測画素値和を式（３）により算出する。

ステップＳ３：動きベクトル，参照画素を入力とし，この動きベクトルを用いた場合の予測誤差の下限値Ｌ（ｖ^* ）を算出する処理を行う。詳細は，後述する。

ステップＳ４：ステップＳ３で求めた下限値Ｌ（ｖ^* ），予測誤差の最小値として格納された値εを入力とし，Ｌ（ｖ^* ）とεとの大小比較を行い，
Ｌ（ｖ^* ）＜ε
であればステップＳ５の処理に移り，そうでなければステップＳ８の処理に移る。

ステップＳ５：被予測画素，参照画素を入力とし，動きベクトルｖ^* に対する予測誤差Ｅ（ｖ^* ）を算出する処理を行い，Ｅ（ｖ^* ）を出力する。

ステップＳ６：動きベクトルｖ^* に対する予測誤差Ｅ（ｖ^* ），予測誤差の最小値として格納された値εを入力とし，両値の大小比較を行う処理を行い，
Ｅ（ｖ^* ）＜ε
であればステップＳ７の処理に移り，そうでなければステップＳ８の処理に移る。

ステップＳ７：動きベクトルｖ^* ，同動きベクトルに対する予測誤差Ｅ（ｖ^* ）を各々，レジスタＭ，εに代入する処理を行う。

ステップＳ８，Ｓ９：全ての動きベクトルについて，上述の処理を繰り返し，最終的に，全動きベクトルの中で予測誤差を最小化する動きベクトルとして，レジスタＭに格納された値を出力する。

以下にステップＳ３の詳細を示す。なお，初期動きベクトルに対しては，図６または図７の処理を行う。

「第１の実施形態」の場合：
図６を用いて，「第１の実施形態」の場合の下限値の算出の流れを説明する。

ステップＳ１１：図５のステップＳ２で書き出した被予測画素値和をレジスタから読み込む。

ステップＳ１２：動きベクトル，参照画素を入力とし，動きベクトルに対する参照画素値和Ｓ（ｖ^* ）を算出し，レジスタに書き出す。より具体的には，式（４）により参照画素値和を算出する。

ステップＳ１３：動きベクトル，参照画素を入力とし，小数画素位置毎の丸め誤差に対する補正値Ｒ_h （ｖ^* ），Ｒ_v （ｖ^* ），Ｒ_d （ｖ^* ）を算出し，レジスタに書き出す処理を行う。より具体的には，式（１１），式（１４），式（１６）により求める。

ステップＳ１４：被予測画素値和Ｃ，参照画素値和Ｓ（ｖ^* ），小数画素位置毎の丸め誤差に対する補正値Ｒ_h （ｖ^* ），Ｒ_v （ｖ^* ），Ｒ_d （ｖ^* ）を入力とし，動きベクトルの予測誤差の下限値Ｌ（ｖ^* ）を算出する処理を行い，レジスタに書き出す。より具体的には，式（１８）により同下限値を求める。

「第２の実施形態」の場合：
図７を用いて，「第２の実施形態」の場合の下限値の算出の流れを説明する。

ステップＳ２１：ステップＳ１１に同じ。

ステップＳ２２：ステップＳ１２に同じ。

ステップＳ２３：予めレジスタに格納された補正値ルックアップテーブルを読み込む。

ステップＳ２４：参照画素，ステップＳ２３で読み込んだ補正値ルックアップテーブルを入力とし，参照画素値に基づき補正値ルックアップテーブルを参照し，小数画素位置毎の丸め誤差に対する補正値を求め，同補正値をレジスタに書き出す処理を行う。

ステップＳ２５：ステップＳ１４に同じ。

「第３の実施形態」の場合：
図８を用いて，「第３の実施形態」の場合の下限値の算出の流れを説明する。

ステップＳ３１：更新前の動きベクトルに対する予測誤差の下限値をレジスタから読み込む。

ステップＳ３２：動きベクトル，参照画素を入力とし，動きベクトルに対する参照画素値和の差分値を算出し，レジスタに書き出す。より具体的には，式（２８），式（２９），式（３１），式（３３）により参照画素値和を算出する。

ステップＳ３３：動きベクトル，参照画素を入力とし，小数画素位置毎の丸め誤差に対する補正値の差分値を算出し，レジスタに書き出す処理を行う。より具体的には，式（３０），式（３２），式（３４）により求める。

ステップＳ３４：参照画素値和の差分値，小数画素位置毎の丸め誤差に対する補正値の差分値，更新前の動きベクトルに対する予測誤差の下限値を入力とし，動きベクトルの予測誤差の下限値Ｌ（ｖ^* ）を算出する処理を行う。より具体的には，式（２５）により下限値Ｌ（ｖ^* ）を求める。

「第４の実施形態」の場合：
図９を用いて，「第４の実施形態」の場合の下限値の算出の流れを説明する。

ステップＳ４１：ステップＳ３１に同じ。

ステップＳ４２：ステップＳ３２に同じ。

ステップＳ４３：予めレジスタに格納された差分補正値ルックアップテーブルを読み込む。

ステップＳ４４：参照画素，ステップＳ４３で読み込んだ差分補正値ルックアップテーブルを入力とし，参照画素値に基づき差分補正値ルックアップテーブルを参照し，小数画素位置毎の丸め誤差に対する補正値の差分値Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ），Ｒ^* （ｖ^* −δ_y ）−Ｒ^* （ｖ^* ），Ｒ^* （ｖ^* −δ_x −δ_y ）−Ｒ^* （ｖ^* ）を求め，レジスタに書き出す処理を行う。

ステップＳ４５：ステップＳ３４に同じ。

［符号化装置］
次に，符号化装置の構成例について説明する。

「第１の実施形態」の場合：
図１０に本発明の第１の実施形態に係る装置構成図を示す。

スイッチＳＷ１は，動きベクトルが初期動きベクトルの場合，初期動きベクトル予測誤差算出部１０１および被予測画素値和決定部１０２の処理を行う。それ以外の場合，参照画素値和決定部１０４の処理を行うように切り替える。

初期動きベクトル予測誤差算出部１０１は，符号化対象ブロックの画素，参照画素，初期動きベクトルに対応する動きベクトルを入力とし，予測誤差を算出する処理を行い，同予測誤差を暫定最小予測誤差記憶部１１２に出力し，同動きベクトルを暫定最適動きベクトル記憶部１１３に出力する。

被予測画素値和決定部１０２は，符号化対象ブロックの画素を入力とし，同ブロック内の被予測画素値和を算出する処理を行い，この被予測画素値和を被予測画素値和記憶部１０３に出力する。より具体的には，式（３）により被予測画素値和を算出する。

参照画素値和決定部１０４は，参照画素，動きベクトルを入力とし，参照画素値和を算出する処理を行い，この参照画素値和を参照画素値和記憶部１０５に出力する。より具体的には，式（４）により参照画素値和を算出する。また，同時に計算過程で算出する値ｆ_t-1 （ｐ−ｖ）＋ｆ_t-1 （ｐ−ｖ＋δ_x ），ｆ_t-1 （ｐ−ｖ）＋ｆ_t-1 （ｐ−ｖ＋δ_y ），ｆ_t-1 （ｐ−ｖ）＋ｆ_t-1 （ｐ−ｖ＋δ_x ）＋ｆ_t-1 （ｐ−ｖ＋δ_y ）＋ｆ_t-1 （ｐ−ｖ＋δ_x ＋δ_y ）（ｐ∈Ｂ）を，部分参照画素値和記憶部１１６に書き出す。

補正値算出部１１５は，部分参照画素値和記憶部１１６から部分参照画素値和を読み込み，予測誤差の下限値の補正値を算出する処理を行い，同補正値を補正値記憶部１０７に出力する。補正値の具体的な算出は，小数画素位置毎に式（１１），式（１４），式（１６）により求める。

予測誤差下限値決定部１０６は，動きベクトルを入力とし，被予測画素値和記憶部１０３，参照画素値和記憶部１０５，補正値記憶部１０７から各々，被予測画素値和，参照画素値和，補正値を読み込み，予測誤差の下限値を算出する処理を行い，同下限値を下限値記憶部１０８に出力する。下限値の具体的な算出は，式（１８）により行う。

枝刈り判定部１０９は，下限値記憶部１０８および暫定最小予測誤差記憶部１１２から各々，予測誤差の下限値，およびこれまでに格納された予測誤差の最小値を読み込み，２つの値の大小比較を行い，同下限値の方が小さい場合は，次の処理へ進む（スイッチＳＷ２）。それ以外の場合は，現在の動きベクトルに対する処理を終了する。

予測誤差算出部１１０は，符号化対象ブロックの画素，参照画素，動きベクトルを入力とし，予測誤差を算出する処理を行い，同予測誤差を出力する。

最適動きベクトル判定部１１１は，予測誤差算出部１１０で算出された予測誤差を入力とし暫定最小予測誤差記憶部１１２からこれまでに格納された予測誤差の最小値を読み込み，２つの値の大小比較を行い，予測誤差算出部１１０で算出された予測誤差の方が小さい場合，同予測誤差を暫定最小予測誤差記憶部１１２に記憶し，同動きベクトルを暫定最適動きベクトル記憶部１１３に記憶する。

動きベクトル制御部１１４は，以上の処理を全ての動きベクトルに対して繰り返し，最終的に暫定最適動きベクトル記憶部１１３に記憶された値を最適な動きベクトルとして出力する。

「第２の実施形態」の場合：
図１１に本発明の第２の実施形態に係る装置構成図を示す。

初期動きベクトル予測誤差算出部２０１から動きベクトル制御部２１４は各々，図１０で説明した初期動きベクトル予測誤差算出部１０１から動きベクトル制御部１１４と同じ処理を行う。

補正値算出部２１５は，事前に補正値が格納済みのルックアップテーブル記憶部２１６から読み出した値を入力として，補正値Ｒ_h （ｖ^* ），Ｒ_v （ｖ^* ），Ｒ_d （ｖ^* ）を算出し，補正値記憶部２０７に書き出す。補正値の具体的な算出は，式（１９），式（２１），式（２３），に従う。

ルックアップテーブル記憶部２１６には，補正値Ｒ_h （ｖ^* ），Ｒ_v （ｖ^* ），Ｒ_d （ｖ^* ）の算出時に参照する補正値テーブルの値ｒ_v （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ），ｒ_h （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ），ｒ_d （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ）を予め格納しておく。

「第３の実施形態」の場合：
図１２に本発明の第３の実施形態に係る装置構成図を示す。

参照画素値和差分値決定部３０４は，動きベクトル，参照画素を入力とし，現在の動きベクトルと更新前の動きベクトルに対する参照画素値和の差分値を算出し，参照画素値和差分値記憶部３０５に書き出す。より具体的には，式（２８），式（２９），式（３１），式（３３）により算出する。また，同時に計算過程で算出する値ｆ_t-1 （ｘ₀ ＋１６−ｖ_x ，ｙ−ｖ_y ）＋ｆ_t-1 （ｘ₀ ＋１７−ｖ_x ，ｙ−ｖ_y ）（式（２８）の場合），ｆ_t-1 （ｘ₀ −ｖ_x ，ｙ−ｖ_y ）＋ｆ_t-1 （ｘ₀ ＋１−ｖ_x ，ｙ−ｖ_y ）（式（２９）の場合），ｆ_t-1 （ｘ₀ ＋１６−ｖ_x ，ｙ−ｖ_y ）＋ｆ_t-1 （ｘ₀ ＋１６−ｖ_x ，ｙ＋１−ｖ_y ），ｆ_t-1 （ｘ₀ −ｖ_x ，ｙ−ｖ_y ）＋ｆ_t-1 （ｘ₀ −ｖ_x ，ｙ＋１−ｖ_y ）（式（３１）の場合），Φ（ｘ₀ ＋１６−ｖ_x ，ｙ−ｖ_y ，ｔ−１），Φ（ｘ₀ −ｖ_x ，ｙ−ｖ_y ，ｔ−１）（式（３３）の場合）（ｙ₀ ≦ｙ≦ｙ₀ ＋１５）を部分参照画素値和記憶部３１６に書き出す。

予測誤差下限値決定部３０６は，参照画素値和差分値記憶部３０５から読み出した参照画素値和の差分値，補正値差分値記憶部３０７から読み出した補正値の差分値，下限値記憶部３０８から読み出した更新前の動きベクトルに対する予測誤差の下限値を入力とし，動きベクトルの予測誤差の下限値を算出する処理を行い，算出した下限値を下限値記憶部３０８に書き出す。同下限値の具体的算出は式（２５）に従う。

補正値差分値算出部３１５は，部分参照画素値和記憶部３１６から読み出した部分参照画素値和を入力とし，小数画素位置毎の丸め誤差に対する補正値の差分値を算出し，補正値差分値記憶部３０７に書き出す処理を行う。同差分値は，より具体的には，式（３０），式（３２），式（３４）により求める。

初期動きベクトル予測誤差算出部３０１および参照画素値和差分値決定部３０４から動きベクトル制御部３１４は各々，図１０で説明した初期動きベクトル予測誤差算出部１０１および参照画素値和決定部１０４から動きベクトル制御部１１４と同様な処理を行う。

「第４の実施形態」の場合：
図１３に本発明の第４の実施形態に係る装置構成図を示す。

初期動きベクトル予測誤差算出部４０１から動きベクトル制御部４１４は各々，図１２の初期動きベクトル予測誤差算出部３０１から動きベクトル制御部３１４と同じ処理を行う。

補正値差分値算出部４１５は，ルックアップテーブル記憶部４１６から読み出した値を入力として，補正値の差分値を算出し，補正値差分値記憶部４０７に書き出す。補正値の具体的な算出は，式（３６），式（３８），式（４０）に従う。

ルックアップアップテーブル記憶部４１６には，補正値の差分値の算出時に参照する差分補正値ルックアップテーブルの値＾ｒ_v （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ），＾ｒ_h （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ），＾ｒ_d （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ）を予め格納しておく。

１／２画素精度ＭＣの例について説明したが，１／ｍ（ｍ＞２）画素精度ＭＣに容易に拡張できることは，以上の説明から明らかである。

以上の動きベクトルを推定し符号化する処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。

補間処理における参照画素を示す図である。 参照画素の差異部分に着目した下限値の算出を説明する図である。 参照画素の差異部分に着目した下限値の算出を説明する図である。 参照画素の差異部分に着目した下限値の算出を説明する図である。 本発明の実施例に係る符号化処理の流れを示す図である。 下限値算出処理の流れ（その１）を示す図である。 下限値算出処理の流れ（その２）を示す図である。 下限値算出処理の流れ（その３）を示す図である。 下限値算出処理の流れ（その４）を示す図である。 本発明の実施例に係る装置構成（その１）を示す図である。 本発明の実施例に係る装置構成（その２）を示す図である。 本発明の実施例に係る装置構成（その３）を示す図である。 本発明の実施例に係る装置構成（その４）を示す図である。

符号の説明

１０１，２０１，３０１，４０１ 初期動きベクトル予測誤差算出部
１０２，２０２ 被予測画素値和決定部
１０３，２０３ 被予測画素値和記憶部
１０４，２０４ 参照画素値和決定部
３０４，４０４ 参照画素値和差分値決定部
１０５，２０５ 参照画素値和記憶部
３０５，４０５ 参照画素値和差分値記憶部
１０６，２０６，３０６，４０６ 予測誤差下限値決定部
１０７，２０７ 補正値記憶部
３０７，４０７ 補正値差分値記憶部
１０８，２０８，３０８，４０８ 下限値記憶部
１０９，２０９，３０９，４０９ 枝刈り判定部
１１０，２１０，３１０，４１０ 予測誤差算出部
１１１，２１１，３１１，４１１ 最適動きベクトル判定部
１１２，２１２，３１２，４１２ 暫定最小予測誤差記憶部
１１３，２１３，３１３，４１３ 暫定最適動きベクトル記憶部
１１４，２１４，３１４，４１４ 動きベクトル制御部
１１５，２１５ 補正値算出部
３１５，４１５ 補正値差分値算出部
１１６，３１６ 部分参照画素値和記憶部
２１６，４１６ ルックアップテーブル記憶部
ＳＷ１，ＳＷ２ スイッチ

Claims (8)

1. 小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定方法であって，
   動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する過程と，
   前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する過程とを有し，
   前記下限値を算出する際，丸め誤差を参照画素群の下位ビットの値に応じて予めルックアップテーブルに格納し，そのルックアップテーブルを参照することにより決定した丸め誤差を用いて下限値を算出する
   ことを特徴とする動きベクトル推定方法。
2. 請求項１記載の動きベクトル推定方法において，
   前記丸め誤差をルックアップテーブルに格納する際，補間処理の対象となる小数画素位置に応じて個別のルックアップテーブルに格納する
   ことを特徴とする動きベクトル推定方法。
3. 小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定方法であって，
   動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する過程と，
   前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する過程とを有し，
   前記下限値を算出する際，
   既に予測誤差の下限値が算出された第１の動きベクトルと，これから予測誤差の下限値を算出する第２の動きベクトルとの，２つの動きベクトルが指す参照領域の差異部分から，これらの２つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し，
   前記第１の動きベクトルの予測誤差の下限値をもとに，前記第２の動きベクトルに対する予測誤差の下限値を算出する
   ことを特徴とする動きベクトル推定方法。
4. 請求項３記載の動きベクトル推定方法において，
   前記下限値を算出する際，
   前記２つの動きベクトルが指す参照領域の差異部分に対する丸め誤差を，参照画素群の下位ビットの値に応じて予めルックアップテーブルに格納し，そのルックアップテーブルを参照することにより前記差異部分に対する丸め誤差を決定し，前記第１の動きベクトルに対する予測誤差の下限値をもとに，前記第２の動きベクトルに対する予測誤差の下限値を算出する
   ことを特徴とする動きベクトル推定方法。
5. 小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定装置であって，
   動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する手段と，
   前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する手段とを備え，
   前記下限値を算出する手段は，丸め誤差を参照画素群の下位ビットの値に応じて予めルックアップテーブルに格納し，そのルックアップテーブルを参照することにより決定した丸め誤差を用いて下限値を算出する
   ことを特徴とする動きベクトル推定装置。
6. 小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定装置であって，
   動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する手段と，
   前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する手段とを備え，
   前記下限値を算出する手段は，
   既に予測誤差の下限値が算出された第１の動きベクトルと，これから予測誤差の下限値を算出する第２の動きベクトルとの，２つの動きベクトルが指す参照領域の差異部分から，これらの２つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し，
   前記第１の動きベクトルの予測誤差の下限値をもとに，前記第２の動きベクトルに対する予測誤差の下限値を算出する
   ことを特徴とする動きベクトル推定装置。
7. 請求項１から請求項４までのいずれか１項に記載された動きベクトル推定方法を，コンピュータに実行させるための動きベクトル推定プログラム。
8. 請求項１から請求項４までのいずれか１項に記載された動きベクトル推定方法を，コンピュータに実行させるための動きベクトル推定プログラムを記録したコンピュータ読み取り可能な記録媒体。

Images