(57)【特許請求の範囲】
【請求項１】
小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定方法であって，
動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する過程と，
前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する過程とを有し，
前記下限値を算出する際，丸め誤差を参照画素群の下位ビットの値に応じて予めルックアップテーブルに格納し，そのルックアップテーブルを参照することにより決定した丸め誤差を用いて下限値を算出する
ことを特徴とする動きベクトル推定方法。
【請求項２】
請求項１記載の動きベクトル推定方法において，
前記丸め誤差をルックアップテーブルに格納する際，補間処理の対象となる小数画素位置に応じて個別のルックアップテーブルに格納する
ことを特徴とする動きベクトル推定方法。
【請求項３】
小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定方法であって，
動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する過程と，
前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する過程とを有し，
前記下限値を算出する際，
既に予測誤差の下限値が算出された第１の動きベクトルと，これから予測誤差の下限値を算出する第２の動きベクトルとの，２つの動きベクトルが指す参照領域の差異部分から，これらの２つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し，
前記第１の動きベクトルの予測誤差の下限値をもとに，前記第２の動きベクトルに対する予測誤差の下限値を算出する
ことを特徴とする動きベクトル推定方法。
【請求項４】
請求項３記載の動きベクトル推定方法において，
前記下限値を算出する際，
前記２つの動きベクトルが指す参照領域の差異部分に対する丸め誤差を，参照画素群の下位ビットの値に応じて予めルックアップテーブルに格納し，そのルックアップテーブルを参照することにより前記差異部分に対する丸め誤差を決定し，前記第１の動きベクトルに対する予測誤差の下限値をもとに，前記第２の動きベクトルに対する予測誤差の下限値を算出する
ことを特徴とする動きベクトル推定方法。
【請求項５】
小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定装置であって，
動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する手段と，
前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する手段とを備え，
前記下限値を算出する手段は，丸め誤差を参照画素群の下位ビットの値に応じて予めルックアップテーブルに格納し，そのルックアップテーブルを参照することにより決定した丸め誤差を用いて下限値を算出する
ことを特徴とする動きベクトル推定装置。
【請求項６】
小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定装置であって，
動きベクトルおよび参照画素をもとに，小数画素精度による補間処理に伴う参照画素値和の丸め誤差を算出し，被予測画素値和と参照画素値和と前記丸め誤差とから決定される動き補償後のフレーム間予測誤差に対する下限値を算出する手段と，
前記算出された下限値を用いて動きベクトル探索の枝刈りを行い，フレーム間予測誤差を最小化する動きベクトルを小数画素精度で探索する手段とを備え，
前記下限値を算出する手段は，
既に予測誤差の下限値が算出された第１の動きベクトルと，これから予測誤差の下限値を算出する第２の動きベクトルとの，２つの動きベクトルが指す参照領域の差異部分から，これらの２つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し，
前記第１の動きベクトルの予測誤差の下限値をもとに，前記第２の動きベクトルに対する予測誤差の下限値を算出する
ことを特徴とする動きベクトル推定装置。
【請求項７】
請求項１から請求項４までのいずれか１項に記載された動きベクトル推定方法を，コンピュータに実行させるための動きベクトル推定プログラム。
【請求項８】
請求項１から請求項４までのいずれか１項に記載された動きベクトル推定方法を，コンピュータに実行させるための動きベクトル推定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，高能率画像信号符号化技術に関し，特に，小数画素精度動き補償における動きベクトルの探索を高速に行うための技術に関するものである。
【背景技術】
【０００２】
動画像符号化における重要な技術の一つにブロックマッチングに基づく動き補償（ＭＣ）がある。この方法では，符号化対象フレームｆt （ｐ）（ｐ∈｛（ｘ，ｙ）｜ｘ＝０，１，... ，Ｘ−１，ｙ＝０，１，... ，Ｙ−１｝）をいくつかの領域に分割し，領域毎に動き補償（ＭＣ）を用いた次のようなフレーム間予測が行われる。
【０００３】
【数１】
0004410172.tif 000002
ここで，Ｂi は第ｉ番目の領域であり，ｖi は次式を満たす動きベクトルである。
【０００４】
【数２】
0004410172.tif 000003
なお，Ｒi はＢi に対応する探索領域であり，
【０００５】
【数３】
0004410172.tif 000004
は，次に続く関数を最小化するｖを返す。すなわち，探索範囲Ｒi において，領域Ｂi 内での予測誤差を最小化するｖが動きベクトルｖi として選ばれる。
【０００６】
予測誤差の最小性を保証した動きベクトル探索の高速化として，代表的なものにＳＥＡ（非特許文献１参照）と呼ばれる手法がある。同手法は，ＭＣ誤差の下限値を予め見積もり，その下限値をもとに探索点を絞り込む手法である。同手法ではＭＣ誤差Ｅ（ｖ）に対して，次式の下限値を用いる。
【０００７】
Ｅ（ｖ）≧Ｃ−Ｓ（ｖ）                                              （２）
ここで，Ｃは符号化ブロックの画素値和，Ｓ（ｖ）は参照ブロックの画素値和であり，各々次式で表される。
【０００８】
【数４】
0004410172.tif 000005
式（２）の証明は，以下の通りである。
【０００９】
【数５】
0004410172.tif 000006
予測誤差の低減を目的として，動きベクトルを小数画素精度で表現する動き補償が検討されている。１／ｍ画素精度の動き補償の場合，動きベクトルは次式を満たすベクトルとして求める。
【００１０】
【数６】
0004410172.tif 000007
ここで，ｆ* t-1 （ｐ）はｆt-1 （ｐ）から生成される補間画像であり，１／ｍ画素間隔で画素値をもつ。例えば，ISO/IEC 13818-2 ＭＰＥＧ−２における１／２画素精度の動き補償の場合，次のような補間画像を用いる。
【００１１】
【数７】
0004410172.tif 000008
ここで，δ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．
【発明の開示】
【発明が解決しようとする課題】
【００１８】
上述のように，非特許文献２に記載された「全探索小数画素精度動き推定の高速化」の技術によれば，ＳＥＡの小数画素精度ＭＣへの適用にあたって，探索点数の増加に伴う計算量増加の問題が軽減され，小数画素精度ＭＣにおける動きベクトル探索の高速化が図られている。
【００１９】
本発明は，非特許文献２に記載された「全探索小数画素精度動き推定の高速化」の技術を，さらに改良し，小数画素精度の動き推定におけるＭＣ誤差の下限値の計算において，参照画素値和の計算上生じる丸め誤差も考慮して，タイトな下限値を算出することにより，探索における枝刈りの促進を図り，小数画素精度ＭＣにおける動きベクトル探索のさらなる高速化を実現することを目的とする。
【００２０】
また，本発明は，上記丸め誤差の算出を少ない計算量で行い，計算量の増加を抑えた動きベクトルの推定を実現することを目的とする。
【課題を解決するための手段】
【００２１】
二つの動きベクトルｖ，ｕのＭＣ誤差を比較する場合，両動きベクトルに対するＭＣ誤差を直接比較するのではなく，動きベクトルｖのＭＣ誤差Ｅ（ｖ）に対して，動きベクトルｕのＭＣ誤差Ｅ（ｕ）の下限値Ｌ（ｕ）との大小比較を行う。この時，
Ｅ（ｖ）≦Ｌ（ｕ）
であれば，Ｌ（ｕ）がＭＣ誤差Ｅ（ｕ）の下限値であるため，
Ｅ（ｖ）≦Ｅ（ｕ）
となり，Ｅ（ｕ）を算出して比較する必要はない。つまり，Ｅ（ｕ）の算出は，
Ｌ（ｕ）＜Ｅ（ｖ）
となる場合のみ行えば十分である。
【００２２】
後述するように，ＭＣ誤差の下限値はＭＣ誤差に比べて，少ない計算量での算出が可能である。このため，ＭＣ誤差の下限値との比較を行い，ＭＣ誤差の算出を省くことにより，予測誤差の最小化を保証した上で，計算量の低減を図ることができる。
【００２３】
本発明は，小数画素精度ＭＣにおいて，フレーム間予測誤差に対する下限値を算出し，下限値を用いた探索の枝刈りを行うとともに，この下限値を算出する際，既に計算済みの加算結果およびシフト演算等を用いて，丸め誤差を算出し，その丸め誤差を用いて下限値を算出する。丸め誤差を考慮した下限値の算出を行うことにより，さらにタイトな枝刈りが可能であり，全探索を行った場合と同等の精度を保持しつつ，大きく計算量を低減することができる。
【００２４】
また，本発明は，上記下限値を算出する際，関連する参照画素群の下位ｎビット（ｎは補間処理で参照される画素数により定まる数）の値に応じて，丸め誤差を予めルックアップテーブルに格納しておき，同テーブルを参照して丸め誤差の補正値を決定し，下限値を算出することにより，さらに計算量を低減することができる。
【００２５】
また，丸め誤差をルックアップテーブルに格納する際，補間処理の対象となる小数画素位置に応じて個別のルックアップテーブルに格納することにより，ルックアップテーブルに必要となるメモリ容量を小さくすることができる。
【００２６】
また，本発明は，予測誤差の下限値を算出する際，２つの動きベクトルが指す参照領域の差異部分のみに注目し，２つの動きベクトルが指す参照領域の予測誤差の下限値の差分値を算出し，一方の動きベクトルの予測誤差の下限値をもとに，他方の動きベクトルに対する予測誤差の下限値を算出する。これにより，計算済みの結果を利用して計算量の低減を図ることができる。
【００２７】
また，本発明は，予測誤差の下限値を算出する際，上記２つの動きベクトルが指す参照領域の差異部分に対する丸め誤差をルックアップテーブルに格納しておき，同テーブルを参照し，一方の動きベクトルに対する予測誤差の下限値をもとに，他方の動きベクトルに対する予測誤差の下限値を算出する。ルックアップテーブルを利用して差異部分に対する丸め誤差を求めることにより，計算量を大幅に低減することができる。
【発明の効果】
【００２８】
本発明を用いれば，小数画素精度ＭＣにおける予測誤差の最小化を完全に保証しつつ，動きベクトル探索における計算量の低減が可能となる。このため，小数画素精度ＭＣにおいて問題とされてきた計算量の増加を解消でき，少ない計算量で，小数画素精度ＭＣによる高い予測性能を享受できる。特に，補間処理の対象となる小数画素位置の参照画素値の計算において生じる丸め誤差を求め，これにより補正した下限値を算出することにより，探索における枝刈りの効果が大きい。
【発明を実施するための最良の形態】
【００２９】
［第１の実施形態］
小数画素精度の動きベクトルｖ* に対するＭＣ誤差（小数画素精度ＭＣ誤差）の下限値を導出する。以下では，式（７ａ）〜（７ｄ）の補間画像を用いる１／２画素精度ＭＣを例にあげ，説明する。このとき，動きベクトルｖ* の取り得る値は次の４通りである。
【００３０】
【数８】
0004410172.tif 000009
ここで，δx ＝（１，０），δy ＝（０，１）であり，ｖは整数値を要素とするベクトルである。なお，以下では，動きベクトルｖ* がｖ* ＝ｖとして整数値を要素とする場合，整数動きベクトルと呼び，それ以外を小数動きベクトルと呼ぶ。以下，ｖ* の値に応じてＥ（ｖ* ）を４通りに場合分けし，各下限値を求める。
【００３１】
（ｉ）ｖ* ＝ｖの場合：
動きベクトルは参照フレーム中の画素位置を指すため，整数画素精度ＭＣにおけるＳＥＡの場合と同様に，ＭＣ誤差は次の下限値を持つ。
【００３２】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）                                            （９）
ここで，Ｃ，Ｓ（ｖ）は，各々式（３），式（４）で表されるものとする。
【００３３】
（ii）ｖ* ＝ｖ−δx ／２の場合：
動きベクトルの指す参照フレームの位置は２画素の中心となり，ＭＣ誤差Ｅ（ｖ* ）は次の下限値を持つ。
【００３４】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）／２−Ｓ（ｖ−δx ）／２−Ｒh （ｖ）      （１０）
ここで，Ｒh （ｖ）は丸め誤差の補正値であり，次式より求まる。
【００３５】
【数９】
0004410172.tif 000010
ここで，○付きの＋はビット毎の論理積を行う演算子を表す。
【００３６】
式（１０）の証明は，以下の通りである。なお，以下の証明において，式（１２ａ）から式（１２ｂ）への展開では，動きベクトルの指す参照フレームの位置は２画素の中心となることから，式（７ｂ）を用いた。
【００３７】
【数１０】
0004410172.tif 000011
(iii)  ｖ* ＝ｖ−δy ／２の場合：
上述の（ii）と同様に動きベクトルの指す参照フレームの位置は２画素の中心となり，ＭＣ誤差は次の下限値を持つ。
【００３８】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）／２−Ｓ（ｖ−δy ）／２−Ｒv （ｖ）      （１３）
証明は（ii）の場合と同様に行える。なお，Ｒv （ｖ）は丸め誤差の補正値であり，次式より求まる。
【００３９】
【数１１】
0004410172.tif 000012
（iv）ｖ* ＝ｖ−（δx ＋δy ）／２の場合：
動きベクトルの指す参照フレームの位置は４画素の中央となり，ＭＣ誤差は次の下限値を持つ。
【００４０】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）／４−Ｓ（ｖ−δx ）／４−Ｓ（ｖ−δy ）／４
−Ｓ（ｖ−δx −δy ）／４−Ｒd （ｖ）    （１５）
なお，Ｒd （ｖ）は丸め誤差の補正値であり，次式より求まる。
【００４１】
【数１２】
0004410172.tif 000013
式（１５）の証明は，以下の通りである。なお，以下の証明において，式（１７ａ）から式（１７ｂ）への展開では，動きベクトルの指す参照フレームの位置は４画素の中央となることから，式（７ｄ）を用いた。
【００４２】
【数１３】
0004410172.tif 000014
以上（ｉ）〜（iv）をまとめると，ＭＣ誤差の下限値Ｌ（ｖ* ）は次式となる。
【００４３】
【数１４】
0004410172.tif 000015
［第２の実施形態：補正値テーブルの利用］
丸め誤差の補正値は補正値テーブルと呼ぶルックアップテーブルに格納し，予測誤差の下限値の計算時には，同テーブルを参照するものとする。以下，同テーブルの作成法について詳述する。
【００４４】
上述（ii）の場合：
Ｒh （ｖ）は，以下のように展開できる。
【００４５】
【数１５】
0004410172.tif 000016
この式（１９）から明らかであるように，参照領域をｘ方向に１７画素，ｙ方向に１画素の幅を持つ１７×１画素の矩形領域に分割したとすると，各矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。
【００４６】
【数１６】
0004410172.tif 000017
この補正値は，１７の画素の下位１ビットから定まり，０から１６の値を取り得る。従って，この補正値に対するルックアップテーブルのサイズは，
５×２17＝０．６５５３６［Ｍｂｉｔｓ］
となる。
【００４７】
上述 (iii)の場合：
Ｒv （ｖ）は，以下のように展開できる。
【００４８】
【数１７】
0004410172.tif 000018
この式（２１）から明らかであるように，各列における丸め誤差は独立に定まる。すなわち，参照領域をｘ方向に１画素，ｙ方向に１７画素の幅を持つ１×１７画素の矩形領域に分割したとすると，各矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。
【００４９】
【数１８】
0004410172.tif 000019
この補正値は，１７個の画素の下位１ビットから定まり，０から１６の値を取り得る。従って，この補正値に対するルックアップテーブルのサイズは，
５×２17＝０．６５５３６［Ｍｂｉｔｓ］
となる。
【００５０】
上述（iv）の場合：
Ｒd （ｖ）は，以下のように展開できる。
【００５１】
【数１９】
0004410172.tif 000020
ここで，Φ（ｘ，ｙ，ｔ）は，以下の通りとする。
【００５２】
Φ（ｘ，ｙ，ｔ）＝ｆt （ｘ，ｙ）＋ｆt （ｘ−１，ｙ）
＋ｆt （ｘ，ｙ−１）＋ｆt （ｘ−１，ｙ−１）
この式（２３）から明らかであるように，参照領域中の，ｘ方向に１７画素，ｙ方向に２画素の幅を持つ１７×２画素の矩形領域における丸め誤差は独立に定まる。しかし，この矩形領域に対して補正値のルックアップテーブルを作成した場合，同ルックアップテーブルのサイズは８５．８９９［Ｇｂｉｔｓ］となり，実装を考慮した場合，現実的なサイズとはいえない。そこで，同矩形領域を２つに分割し，２×８画素の矩形領域単位で補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。
【００５３】
【数２０】
0004410172.tif 000021
ｒd （ｘ0 ，ｙ0 ，ｖx ，ｖy ）に格納する補正値は，１８個の画素の下位１ビットから定まり，０から８の値を取り得る。従って，このルックアップテーブルのサイズは，
４×２18＝１．０４８６［Ｍｂｉｔｓ］
となる。
【００５４】
［第３の実施形態］
連続した動きベクトルに対する予測誤差の最小値を求める場合，隣接参照領域における差異領域に注目することで計算量を削減できる。予測誤差の下限値が式（１８）で与えられる場合，Ｌ（ｖ* −δx ）とＬ（ｖ* ）とは，以下の関係にある。
【００５５】
【数２１】
0004410172.tif 000022
ここで，Ｓ* （ｖ* ），Ｒ* （ｖ* ）は，以下の通りである。
【００５６】
【数２２】
0004410172.tif 000023
図２，図３，図４に動きベクトルｖ* −δx およびｖ* の指す領域を示す。これらは，いずれも動き補償の領域が４×４［画素］の例を図示したものである。
【００５７】
Ｒ* （ｖ* −δx ）−Ｒ* （ｖ* ）が計算すべき補正値である。以下，ｖ* の値に応じて，Ｓ* （ｖ* −δx ）−Ｓ* （ｖ* ），Ｒ* （ｖ* −δx ）−Ｒ* （ｖ* ）の計算法について詳述する。以下，動き補償の領域は１６×１６とする。
【００５８】
（ｉ）ｖ* ＝ｖの場合：
この場合，丸め誤差は発生しないため，補正値は必要ない。また，Ｓ* （ｖ* −δx ）−Ｓ* （ｖ* ）は次式のようになる。
【００５９】
【数２３】
0004410172.tif 000024
（ii）ｖ* ＝ｖ−δx ／２の場合：
Ｓ* （ｖ* −δx ）−Ｓ* （ｖ* ）は次式となる。
【００６０】
【数２４】
0004410172.tif 000025
また，Ｒ* （ｖ* −δx ）−Ｒ* （ｖ* ）は次式となる。
【００６１】
【数２５】
0004410172.tif 000026
(iii)  ｖ* ＝ｖ−δy ／２の場合：
Ｓ* （ｖ* −δy ）−Ｓ* （ｖ* ）は次式となる。
【００６２】
【数２６】
0004410172.tif 000027
また，Ｒ* （ｖ* −δy ）−Ｒ* （ｖ* ）は次式となる。
【００６３】
【数２７】
0004410172.tif 000028
（iv）ｖ* ＝ｖ−δx ／２−δy ／２の場合：
Ｓ* （ｖ* −δx −δy ）−Ｓ* （ｖ* ）は次式となる。
【００６４】
【数２８】
0004410172.tif 000029
また，Ｒ* （ｖ* −δx −δy ）−Ｒ* （ｖ* ）は次式となる。
【００６５】
【数２９】
0004410172.tif 000030
［第４の実施形態：差分補正値テーブルの利用］
連続した動きベクトルに対する予測誤差の最小値を求める場合，隣接参照領域における差異領域に注目することで計算量を削減できる。このときに用いる丸め誤差の補正値は差分補正値テーブルと呼ぶルックアップテーブルに格納し，予測誤差の下限値の計算時には，同テーブルを参照するものとする。
【００６６】
予測誤差の下限値が式（１８）で与えられる場合，Ｌ（ｖ* −δx ）とＬ（ｖ* ）とは前述の式（２５）の関係にある。Ｓ* （ｖ* −δx ）−Ｓ* （ｖ* ）については，前述した「第３の実施形態：丸め誤差の補正値」の通りである。Ｒ* （ｖ* −δx ）−Ｒ* （ｖ* ）が差分補正値テーブルに格納される値となる。以下，ｖ* の値に応じて，同テーブルの作成法について詳述する。
【００６７】
（ｉ）ｖ* ＝ｖの場合：
この場合，丸め誤差は発生しないため，補正値は必要ない。
【００６８】
（ii）ｖ* ＝ｖ−δx ／２の場合：
Ｒ* （ｖ* −δx ）−Ｒ* （ｖ* ）は式（３０）となる。同式によれば，ｘ方向に２画素，ｙ方向に１６画素の幅を持つ２×１６画素の矩形領域における丸め誤差は独立に定まる。この矩形領域に対する補正値のルックアップテーブルのサイズが実装するシステムに対して大きすぎる場合は，同矩形領域を２つに分割し，２×８画素の矩形領域単位で補正値をルックアップテーブル＾ｒh （ｘ0 ，ｙ0 ，ｄx ，ｄy ）に格納する。＾ｒh （ｘ0 ，ｙ0 ，ｄx ，ｄy ）を，
【００６９】
【数３０】
0004410172.tif 000031
として定義すると，Ｒ* （ｖ* −δx ）−Ｒ* （ｖ* ）は次式のように表せる。
【００７０】
【数３１】
0004410172.tif 000032
(iii)  ｖ* ＝ｖ−δy ／２の場合：
Ｒ* （ｖ* −δy ）−Ｒ* （ｖ* ）は式（３２）となる。同式によれば，ｘ方向に１画素，ｙ方向に１７画素の幅を持つ１×１７画素の矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で補正値をルックアップテーブル＾ｒv （ｘ0 ，ｙ0 ，ｄx ，ｄy ）に格納する。＾ｒv （ｘ0 ，ｙ0 ，ｄx ，ｄy ）を，
【００７１】
【数３２】
0004410172.tif 000033
として定義すると，Ｒ* （ｖ* −δy ）−Ｒ* （ｖ* ）は次式のように表せる。
【００７２】
【数３３】
0004410172.tif 000034
（iv）ｖ* ＝ｖ−δx ／２−δy ／２の場合：
Ｒ* （ｖ* −δx −δy ）−Ｒ* （ｖ* ）は式（３４）となる。同式によれば，ｘ方向に２画素，ｙ方向に１７画素の幅を持つ２×１７画素の矩形領域における丸め誤差は独立に定まる。この矩形領域に対する補正値のルックアップテーブルのサイズが実装するシステムに対して大きすぎる場合は，同矩形領域を２つに分割し，２×８画素の矩形領域単位で補正値をルックアップテーブル＾ｒd （ｘ0 ，ｙ0 ，ｄx ，ｄy ）に格納する。＾ｒd （ｘ0 ，ｙ0 ，ｄx ，ｄy ）を，
【００７３】
【数３４】
0004410172.tif 000035
として定義すると，Ｒ* （ｖ* −δx −δy ）−Ｒ* （ｖ* ）は次式のように表せる。
【００７４】
【数３５】
0004410172.tif 000036
【実施例１】
【００７５】
［符号化処理の流れ］
本発明の実施例に係る符号化処理の流れについて，図５を参照して説明する。
【００７６】
ステップＳ１：被予測画素，参照画素，初期動きベクトルを入力とし，初期動きベクトルとして指定された動きベクトルｖ* に対して，予測誤差Ｅ（ｖ* ）を計算し，それを出力する。
【００７７】
ステップＳ２：被予測画素を入力とし，被予測画素値和をレジスタに書き出す。より具体的には，被予測画素値和を式（３）により算出する。
【００７８】
ステップＳ３：動きベクトル，参照画素を入力とし，この動きベクトルを用いた場合の予測誤差の下限値Ｌ（ｖ* ）を算出する処理を行う。詳細は，後述する。
【００７９】
ステップＳ４：ステップＳ３で求めた下限値Ｌ（ｖ* ），予測誤差の最小値として格納された値εを入力とし，Ｌ（ｖ* ）とεとの大小比較を行い，
Ｌ（ｖ* ）＜ε
であればステップＳ５の処理に移り，そうでなければステップＳ８の処理に移る。
【００８０】
ステップＳ５：被予測画素，参照画素を入力とし，動きベクトルｖ* に対する予測誤差Ｅ（ｖ* ）を算出する処理を行い，Ｅ（ｖ* ）を出力する。
【００８１】
ステップＳ６：動きベクトルｖ* に対する予測誤差Ｅ（ｖ* ），予測誤差の最小値として格納された値εを入力とし，両値の大小比較を行う処理を行い，
Ｅ（ｖ* ）＜ε
であればステップＳ７の処理に移り，そうでなければステップＳ８の処理に移る。
【００８２】
ステップＳ７：動きベクトルｖ* ，同動きベクトルに対する予測誤差Ｅ（ｖ* ）を各々，レジスタＭ，εに代入する処理を行う。
【００８３】
ステップＳ８，Ｓ９：全ての動きベクトルについて，上述の処理を繰り返し，最終的に，全動きベクトルの中で予測誤差を最小化する動きベクトルとして，レジスタＭに格納された値を出力する。
【００８４】
以下にステップＳ３の詳細を示す。なお，初期動きベクトルに対しては，図６または図７の処理を行う。
【００８５】
「第１の実施形態」の場合：
図６を用いて，「第１の実施形態」の場合の下限値の算出の流れを説明する。
【００８６】
ステップＳ１１：図５のステップＳ２で書き出した被予測画素値和をレジスタから読み込む。
【００８７】
ステップＳ１２：動きベクトル，参照画素を入力とし，動きベクトルに対する参照画素値和Ｓ（ｖ* ）を算出し，レジスタに書き出す。より具体的には，式（４）により参照画素値和を算出する。
【００８８】
ステップＳ１３：動きベクトル，参照画素を入力とし，小数画素位置毎の丸め誤差に対する補正値Ｒ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 （ｘ0 ，ｙ0 ，ｖx ，ｖy ），ｒh （ｘ0 ，ｙ0 ，ｖx ，ｖy ），ｒd （ｘ0 ，ｙ0 ，ｖx ，ｖy ）を予め格納しておく。
【０１２３】
「第３の実施形態」の場合：
図１２に本発明の第３の実施形態に係る装置構成図を示す。
【０１２４】
参照画素値和差分値決定部３０４は，動きベクトル，参照画素を入力とし，現在の動きベクトルと更新前の動きベクトルに対する参照画素値和の差分値を算出し，参照画素値和差分値記憶部３０５に書き出す。より具体的には，式（２８），式（２９），式（３１），式（３３）により算出する。また，同時に計算過程で算出する値ｆt-1 （ｘ0 ＋１６−ｖx ，ｙ−ｖy ）＋ｆt-1 （ｘ0 ＋１７−ｖx ，ｙ−ｖy ）（式（２８）の場合），ｆt-1 （ｘ0 −ｖx ，ｙ−ｖy ）＋ｆt-1 （ｘ0 ＋１−ｖx ，ｙ−ｖy ）（式（２９）の場合），ｆt-1 （ｘ0 ＋１６−ｖx ，ｙ−ｖy ）＋ｆt-1 （ｘ0 ＋１６−ｖx ，ｙ＋１−ｖy ），ｆt-1 （ｘ0 −ｖx ，ｙ−ｖy ）＋ｆt-1 （ｘ0 −ｖx ，ｙ＋１−ｖy ）（式（３１）の場合），Φ（ｘ0 ＋１６−ｖx ，ｙ−ｖy ，ｔ−１），Φ（ｘ0 −ｖx ，ｙ−ｖy ，ｔ−１）（式（３３）の場合）（ｙ0 ≦ｙ≦ｙ0 ＋１５）を部分参照画素値和記憶部３１６に書き出す。
【０１２５】
予測誤差下限値決定部３０６は，参照画素値和差分値記憶部３０５から読み出した参照画素値和の差分値，補正値差分値記憶部３０７から読み出した補正値の差分値，下限値記憶部３０８から読み出した更新前の動きベクトルに対する予測誤差の下限値を入力とし，動きベクトルの予測誤差の下限値を算出する処理を行い，算出した下限値を下限値記憶部３０８に書き出す。同下限値の具体的算出は式（２５）に従う。
【０１２６】
補正値差分値算出部３１５は，部分参照画素値和記憶部３１６から読み出した部分参照画素値和を入力とし，小数画素位置毎の丸め誤差に対する補正値の差分値を算出し，補正値差分値記憶部３０７に書き出す処理を行う。同差分値は，より具体的には，式（３０），式（３２），式（３４）により求める。
【０１２７】
初期動きベクトル予測誤差算出部３０１および参照画素値和差分値決定部３０４から動きベクトル制御部３１４は各々，図１０で説明した初期動きベクトル予測誤差算出部１０１および参照画素値和決定部１０４から動きベクトル制御部１１４と同様な処理を行う。
【０１２８】
「第４の実施形態」の場合：
図１３に本発明の第４の実施形態に係る装置構成図を示す。
【０１２９】
初期動きベクトル予測誤差算出部４０１から動きベクトル制御部４１４は各々，図１２の初期動きベクトル予測誤差算出部３０１から動きベクトル制御部３１４と同じ処理を行う。
【０１３０】
補正値差分値算出部４１５は，ルックアップテーブル記憶部４１６から読み出した値を入力として，補正値の差分値を算出し，補正値差分値記憶部４０７に書き出す。補正値の具体的な算出は，式（３６），式（３８），式（４０）に従う。
【０１３１】
ルックアップアップテーブル記憶部４１６には，補正値の差分値の算出時に参照する差分補正値ルックアップテーブルの値＾ｒv （ｘ0 ，ｙ0 ，ｖx ，ｖy ），＾ｒh （ｘ0 ，ｙ0 ，ｖx ，ｖy ），＾ｒd （ｘ0 ，ｙ0 ，ｖx ，ｖy ）を予め格納しておく。
【０１３２】
１／２画素精度ＭＣの例について説明したが，１／ｍ（ｍ＞２）画素精度ＭＣに容易に拡張できることは，以上の説明から明らかである。
【０１３３】
以上の動きベクトルを推定し符号化する処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【０１３４】
【図１】補間処理における参照画素を示す図である。
【図２】参照画素の差異部分に着目した下限値の算出を説明する図である。
【図３】参照画素の差異部分に着目した下限値の算出を説明する図である。
【図４】参照画素の差異部分に着目した下限値の算出を説明する図である。
【図５】本発明の実施例に係る符号化処理の流れを示す図である。
【図６】下限値算出処理の流れ（その１）を示す図である。
【図７】下限値算出処理の流れ（その２）を示す図である。
【図８】下限値算出処理の流れ（その３）を示す図である。
【図９】下限値算出処理の流れ（その４）を示す図である。
【図１０】本発明の実施例に係る装置構成（その１）を示す図である。
【図１１】本発明の実施例に係る装置構成（その２）を示す図である。
【図１２】本発明の実施例に係る装置構成（その３）を示す図である。
【図１３】本発明の実施例に係る装置構成（その４）を示す図である。
【符号の説明】
【０１３５】
１０１，２０１，３０１，４０１  初期動きベクトル予測誤差算出部
１０２，２０２  被予測画素値和決定部
１０３，２０３  被予測画素値和記憶部
１０４，２０４  参照画素値和決定部
３０４，４０４  参照画素値和差分値決定部
１０５，２０５  参照画素値和記憶部
３０５，４０５  参照画素値和差分値記憶部
１０６，２０６，３０６，４０６  予測誤差下限値決定部
１０７，２０７  補正値記憶部
３０７，４０７  補正値差分値記憶部
１０８，２０８，３０８，４０８  下限値記憶部
１０９，２０９，３０９，４０９  枝刈り判定部
１１０，２１０，３１０，４１０  予測誤差算出部
１１１，２１１，３１１，４１１  最適動きベクトル判定部
１１２，２１２，３１２，４１２  暫定最小予測誤差記憶部
１１３，２１３，３１３，４１３  暫定最適動きベクトル記憶部
１１４，２１４，３１４，４１４  動きベクトル制御部
１１５，２１５  補正値算出部
３１５，４１５  補正値差分値算出部
１１６，３１６  部分参照画素値和記憶部
２１６，４１６  ルックアップテーブル記憶部
ＳＷ１，ＳＷ２  スイッチ
【図１】
0004410172.tif 000037
【図２】
0004410172.tif 000038
【図３】
0004410172.tif 000039
【図４】
0004410172.tif 000040
【図５】
0004410172.tif 000041
【図６】
0004410172.tif 000042
【図７】
0004410172.tif 000043
【図８】
0004410172.tif 000044
【図９】
0004410172.tif 000045
【図１０】
0004410172.tif 000046
【図１１】
0004410172.tif 000047
【図１２】
0004410172.tif 000048
【図１３】
0004410172.tif 000049