(57)【要約】【課題】動きベクトルを小数画素精度で表現する動き補償（ＭＣ）において，予測誤差の最小化を完全に保証しつつ，動きベクトル探索における計算量を低減する。【解決手段】下限値算出部１０６は，動きベクトルに対する予測誤差の下限値Ｌを算出する。下限値比較部１０７は，算出された下限値Ｌとそれまでに算出された予測誤差の最小値Ｍとを比較する。下限値Ｌの方が小さい場合にだけ，フレーム間予測誤差算出部１０８は，小数画素精度の動きベクトルに対する予測誤差Ｅを算出する。誤差比較部１０９は，算出された予測誤差Ｅとそれまでの予測誤差の最小値Ｍとを比較し，予測誤差Ｅの方が小さければ，最小値更新部１１０により，以降，その予測誤差Ｅを予測誤差の最小値Ｍとする。動きベクトル推定装置１００は，最終的に最小となった予測誤差の動きベクトルを符号化対象ブロックの動きベクトルとする。【選択図】図１
2005252569.tif 000002
【特許請求の範囲】
【請求項１】
小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定方法であって，
動きベクトルを小数画素精度で探索する際に，小数画素精度の動きベクトルごとに，動き補償後のフレーム間予測誤差に対する下限値を算出する第１の過程と，
算出した下限値と，動きベクトルの探索範囲内においてそれまでに算出されたフレーム間予測誤差の最小値とを比較する第２の過程と，
前記下限値のほうが前記最小値よりも小さい場合にのみ，前記動きベクトルに対するフレーム間予測誤差を算出する第３の過程と，
算出したフレーム間予測誤差と前記最小値とを比較する第４の過程と，
前記算出したフレーム間予測誤差のほうが前記最小値よりも小さい場合に，当該フレーム間予測誤差を，新たなフレーム間予測誤差の最小値として設定し，そのときの動きベクトルを記憶する第５の過程とを有し，
前記第１の過程から前記第５の過程を，探索範囲内のすべての小数画素精度の動きベクトルについて繰り返し，最終的に前記第５の過程で記憶した動きベクトルを，動き補償に用いる動きベクトルとする
ことを特徴とする動きベクトル推定方法。
【請求項２】
請求項１に記載の動きベクトル推定方法において，
前記第１の過程の前に，
符号化対象フレームにおける符号化対象領域の画素値の和を算出し記憶する過程と，
参照フレームにおける整数画素位置の参照領域における画素値の和を算出し記憶する過程とを有し，
前記第１の過程では，あらかじめ算出された前記符号化対象領域の画素値の和と，前記整数画素位置の参照領域における画素値の和とを用いて，小数画素精度の動きベクトルに対するフレーム間予測誤差の下限値を算出する
ことを特徴とする動きベクトル推定方法。
【請求項３】
請求項２に記載の動きベクトル推定方法において，
前記参照フレームにおける整数画素位置の参照領域における画素値の和を算出し記憶する過程では，当該参照領域の近傍の参照領域に対して，以前に算出され記憶された画素値の和と，当該参照領域と前記近傍の参照領域との差分の領域の画素値の和とから，当該参照領域における画素値の和を算出する
ことを特徴とする動きベクトル推定方法。
【請求項４】
小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定装置であって，
動きベクトルを小数画素精度で探索する際に，小数画素精度の動きベクトルごとに，動き補償後のフレーム間予測誤差に対する下限値を算出する第１の手段と，
算出した下限値と，動きベクトルの探索範囲内においてそれまでに算出されたフレーム間予測誤差の最小値とを比較する第２の手段と，
前記下限値のほうが前記最小値よりも小さい場合にのみ，前記動きベクトルに対するフレーム間予測誤差を算出する第３の手段と，
算出したフレーム間予測誤差と前記最小値とを比較する第４の手段と，
前記算出したフレーム間予測誤差のほうが前記最小値よりも小さい場合に，当該フレーム間予測誤差を，新たなフレーム間予測誤差の最小値として設定し，そのときの動きベクトルを記憶する第５の手段とを備え，
前記第１の手段による処理から前記第５の手段による処理を，探索範囲内のすべての小数画素精度の動きベクトルについて繰り返し，最終的に前記第５の手段で記憶した動きベクトルを，動き補償に用いる動きベクトルとする
ことを特徴とする動きベクトル推定装置。
【請求項５】
請求項４に記載の動きベクトル推定装置において，
符号化対象フレームにおける符号化対象領域の画素値の和を算出し記憶する手段と，
参照フレームにおける整数画素位置の参照領域における画素値の和を算出し記憶する手段とを備え，
前記第１の手段では，あらかじめ算出された前記符号化対象領域の画素値の和と，前記整数画素位置の参照領域における画素値の和とを用いて，小数画素精度の動きベクトルに対するフレーム間予測誤差の下限値を算出する
ことを特徴とする動きベクトル推定装置。
【請求項６】
請求項５に記載の動きベクトル推定装置において，
前記参照フレームにおける整数画素位置の参照領域における画素値の和を算出し記憶する手段では，当該参照領域の近傍の参照領域に対して，以前に算出され記憶された画素値の和と，当該参照領域と前記近傍の参照領域との差分の領域の画素値の和とから，当該参照領域における画素値の和を算出する
ことを特徴とする動きベクトル推定装置。
【請求項７】
請求項１から請求項３までのいずれか１項に記載の動きベクトル推定方法をコンピュータに実行させるための動きベクトル推定プログラム。
【請求項８】
請求項１から請求項３までのいずれか１項に記載の動きベクトル推定方法をコンピュータに実行させるためのプログラムを，コンピュータ読み取り可能な記録媒体に記録した
ことを特徴とする動きベクトル推定プログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，高能率画像信号符号化の技術に関し，特に，動き補償における動きベクトルの探索を高速に行うための技術に関するものである。
【背景技術】
【０００２】
動画像符号化における重要な技術の一つに，ブロックマッチングに基づく動き補償（以下，ＭＣともいう）がある。
【０００３】
図４は，一般的な動画像符号化装置の構成例を示す図である。図４に示す動画像符号化装置は，ブロックマッチングに基づく動き補償を用いて動画像のフレーム間予測を行い，予測誤差信号を符号化する。符号化は，入力した符号化対象フレームをいくつかに分割した領域（以下，ブロックともいう）ごとに，以下のように行われる。ここで，フレームメモリ２には，過去に符号化処理された参照フレームが蓄えられているものとする。
【０００４】
動き探索部１は，符号化対象フレームのブロックごとに，フレームメモリ２に蓄積された参照フレームとのブロックマッチングにより動きベクトルを探索する。探索により得られた動きベクトルの情報は，動き補償部３と符号化部７へ送られる。
【０００５】
動き補償部３は，フレームメモリ２に蓄積された参照フレームと動き探索部１から送られた動きベクトルの情報とから，予測画像を生成する。生成された予測画像は，減算器４と加算器１０へ送られる。
【０００６】
減算器４は，動き補償部３から送られた予測画像と入力された符号化対象フレームとの間の予測誤差を算出する。ＤＣＴ部５は，算出された予測誤差に対して離散コサイン変換を行う。量子化部６は，離散コサイン変換された予測誤差を量子化する。量子化された予測誤差は，符号化部７と逆量子化部８へ送られる。
【０００７】
符号化部７は，量子化部６から送られた量子化された予測誤差を可変長符号化し，また，動き探索部１から送られたブロックごとの動きベクトルの情報を符号化して，ビットストリームとして出力する。
【０００８】
逆量子化部８は，量子化部６から送られた量子化された予測誤差を逆量子化する。逆ＤＣＴ部９は，逆量子化された予測誤差に対して逆離散コサイン変換を行う。加算器１０は，逆離散コサイン変換された予測誤差と動き補償部３から送られた予測画像とから次の符号化対象フレームに対する参照フレームを生成し，フレームメモリ２に蓄える。
【０００９】
以上のように，ブロックマッチングに基づく動き補償では，符号化対象フレームｆt （ｐ），ｐ∈｛（ｘ，ｙ）｜ｘ＝０，１，…，Ｘ−１，ｙ＝０，１，…，Ｙ−１｝をいくつかの領域に分割する。分割した領域ごとに，参照フレームｆt-1 （ｐ），ｐ∈｛（ｘ，ｙ）｜ｘ＝０，１，…，Ｘ−１，ｙ＝０，１，…，Ｙ−１｝との間の動きベクトルｖを探索する。
【００１０】
予測フレームをｆ’t （ｐ），ｐ∈｛（ｘ，ｙ）｜ｘ＝０，１，…，Ｘ−１，ｙ＝０，１，…，Ｙ−１｝と表すものとすると，分割された領域ごとに，次の式（１）に示すような動き補償（ＭＣ）を用いたフレーム間予測が行われる。
【００１１】
ｆ’t （ｐ）＝ｆt-1 （ｐ−ｖi ），ｐ∈Ｂi                           （１）
式（１）において，Ｂi は，符号化対象フレームの第ｉ番目の領域を示す。ｖi は，次の式（２）を満たす動きベクトルである。
【００１２】
【数１】
2005252569.tif 000003
なお，式（２）において，Ｒi はＢi に対応する探索領域であり，ｖ∈Ｒi を添字とするａｒｇ  ｍｉｎは，次に続く関数を最小化するｖを返す。すなわち，式（２）では，探索範囲Ｒi において，領域Ｂi 内での予測誤差を最小化するｖが動きベクトルｖi として選ばれる。
【００１３】
予測誤差の最小性を保証した動きベクトル探索の高速化手法として，代表的なものにＳＥＡと呼ばれる手法がある（例えば，非特許文献１参照）。同手法は，フレーム間予測誤差（以下，ＭＣ誤差ともいう）Ｅ（ｖ）の下限値をあらかじめ見積もり，その下限値をもとに探索点を絞り込む手法である。同手法では，ＭＣ誤差Ｅ（ｖ）に対して，次の式（３）の下限値を用いる。
【００１４】
Ｅ（ｖ）≧Ｃ−Ｓ（ｖ）                                              （３）
ここで，Ｃは符号化ブロックの画素値和，Ｓ（ｖ）は参照ブロックの画素値和であり，各々，次の式（４），式（５）で表すことができる。
【００１５】
【数２】
2005252569.tif 000004
式（３）の証明は，以下の通りである。
【００１６】
【数３】
2005252569.tif 000005
予測誤差の低減を目的として，動きベクトルを小数画素精度で表現する動き補償が検討されている。１／ｍ画素精度の動き補償の場合，動きベクトルｖi は，次の式（７）を満たすベクトルとして求める。
【００１７】
【数４】
2005252569.tif 000006
ここで，ｆ* t-1 （ｐ）はｆt-1 （ｐ）から生成される補間画像であり，１／ｍ画素間隔で画素値をもつ。例えば，ＩＳＯ／ＩＥＣ  １３８１８−２  ＭＰＥＧ−２における１／２画素精度の動き補償の場合，次のような補間画像を用いる。
【００１８】
【数５】
2005252569.tif 000007
ここで，δx ＝（１，０），δy ＝（０，１）であり，ｐは整数値を要素とするベクトルである。つまり，予測時の参照フレームの位置が２画素の中心なら，２つの画素値の丸め付き平均を予測値として使用し（式（８ｂ），式（８ｃ）），予測時の参照フレームの位置が正方形の頂点に並んだ４画素の中心なら，４つの画素値の丸め付き平均を予測値として使用することになる（式（８ｄ））。
【００１９】
以下，式（２）から求めた動きベクトルを用いる動き補償を整数ＭＣと呼び，式（７）から求めた動きベクトルを用いる動き補償を小数ＭＣと呼ぶ。また，以下ではｉ番目の領域に注目して議論するので，Ｂi はＢと表し，ｖi はｖと表す。
【非特許文献１】“Successive elimination algorithm for motion estimation”W.Li and E.Salari ，IEEE Transactions on Image Processing Volume 4，Issue 1 ，Jan.，pp.105-107，1995
【発明の開示】
【発明が解決しようとする課題】
【００２０】
小数ＭＣの場合，整数ＭＣに比較して動きベクトル探索の計算量が増大する。これは，探索領域内に含まれる探索点の数が増加するためである。探索領域がｗ×ｈ点の画素を含む場合，整数ＭＣにおける探索点がｗ×ｈ点であるのに対し，１／ｍ画素精度の小数ＭＣにおける探索点は，｛ｍ（ｗ−１）＋１｝×｛ｍ（ｈ−１）＋１｝点となる。
【００２１】
小数ＭＣの動きベクトル探索において計算量を低減させる場合，最適解である式（７）の動きベクトルを求めることをあきらめ，式（７）の準最適解に相当する動きベクトルを求める方法が多く検討されている。この場合，計算量の低減とひきかえに，予測誤差は増加してしまう。しかし，予測誤差を減少させるために導入された小数ＭＣにおいて，こうした予測誤差の増加は望ましくない。このため，予測誤差を増加させることなく計算量を低減させる動きベクトル探索法が必要となる。
【００２２】
本発明は，以上のような事情に鑑みてなされたものであって，小数ＭＣにおける動きベクトル探索の高速な計算法を確立することを目的とする。
【課題を解決するための手段】
【００２３】
本発明は，上記の課題を解決するため，小数ＭＣにおける動きベクトル探索において，二つの動きベクトルｕ，ｖのＭＣ誤差を比較する場合に，両動きベクトルに対するＭＣ誤差の大小を直接比較するのではなく，動きベクトルｕのＭＣ誤差Ｅ（ｕ）と，動きベクトルｖのＭＣ誤差Ｅ（ｖ）の下限値Ｌ（ｖ）との大小を比較することを特徴とする。
【００２４】
この時，
Ｅ（ｕ）≦Ｌ（ｖ）                                                  （９）
であれば，Ｌ（ｖ）がＭＣ誤差Ｅ（ｖ）の下限値であるため，
Ｅ（ｕ）≦Ｅ（ｖ）                                                （１０）
となり，Ｅ（ｖ）を算出して比較する必要はない。つまり，Ｅ（ｖ）の算出は，
Ｌ（ｖ）＜Ｅ（ｕ）                                                （１１）
となる場合にのみ行えば十分である。
【００２５】
後述するように，ＭＣ誤差の下限値は，ＭＣ誤差に比べて少ない計算量での算出が可能である。このため，ＭＣ誤差の下限値との比較を行って不要なＭＣ誤差の算出を省くことにより，予測誤差の最小化を保証した上での計算量の低減を図ることができる。前述のＳＥＡも，同様の原理に基づく手法であるが，ＳＥＡは整数ＭＣへの適用にとどまっており，小数ＭＣへの適用は，おそらく探索点数の増加に伴う計算量増加の問題から検討されていない。
【００２６】
本発明はこの問題を解決し，特に小数ＭＣ誤差の下限値を求める際に，符号化対象ブロックの画素値和および整数動きベクトルの指す参照ブロックの画素値和を事前に求めて再利用することにより計算量の低減を図り，少ない計算量で小数ＭＣのもつ高い予測性能を実現するものである。
【００２７】
具体的には，本発明は，小数画素精度動き補償を用いてフレーム間予測を行う画像符号化方式における動きベクトル推定方法であって，動きベクトルを小数画素精度で探索する際に，小数画素精度の動きベクトルごとに，動き補償後のフレーム間予測誤差に対する下限値を算出する第１の過程と，算出した下限値と，動きベクトルの探索範囲内においてそれまでに算出されたフレーム間予測誤差の最小値とを比較する第２の過程と，前記下限値のほうが前記最小値よりも小さい場合にのみ，前記動きベクトルに対するフレーム間予測誤差を算出する第３の過程と，算出したフレーム間予測誤差と前記最小値とを比較する第４の過程と，前記算出したフレーム間予測誤差のほうが前記最小値よりも小さい場合に，当該フレーム間予測誤差を，新たなフレーム間予測誤差の最小値として設定し，そのときの動きベクトルを記憶する第５の過程とを有し，前記第１の過程から前記第５の過程を，探索範囲内のすべての小数画素精度の動きベクトルについて繰り返し，最終的に前記第５の過程で記憶した動きベクトルを，動き補償に用いる動きベクトルとすることを特徴とする。
【００２８】
また，本発明は，前記第１の過程の前に，符号化対象フレームにおける符号化対象領域の画素値の和を算出し記憶する過程と，参照フレームにおける整数画素位置の参照領域における画素値の和を算出し記憶する過程とを有し，前記第１の過程では，あらかじめ算出された前記符号化対象領域の画素値の和と，前記整数画素位置の参照領域における画素値の和とを用いて，小数画素精度の動きベクトルに対するフレーム間予測誤差の下限値を算出することを特徴とする。
【００２９】
また，前記参照フレームにおける整数画素位置の参照領域における画素値の和を算出し記憶する過程では，当該参照領域の近傍の参照領域に対して，以前に算出され記憶された画素値の和と，当該参照領域と前記近傍の参照領域との差分の領域の画素値の和とから，当該参照領域における画素値の和を算出することを特徴とする。
【発明の効果】
【００３０】
本発明を用いることにより，小数ＭＣにおける予測誤差の最小化を完全に保証しつつ，動きベクトル探索における計算量の低減が可能となる。このため，小数ＭＣにおいて問題とされてきた計算量の増加を解消でき，少ない計算量で，小数ＭＣのもつ高い予測性能を享受することができる。
【発明を実施するための最良の形態】
【００３１】
以下，本発明の実施の形態について，図を用いて説明する。
【００３２】
図１は，本発明の実施の形態に係る動きベクトル推定装置の構成例を示す図である。動きベクトル推定装置１００は，例えば図４に示す動画像符号化装置の動き探索部１に用いられるものである。この動きベクトル推定装置１００は，ハードウェアやファームウェアによって実現することができ，また，コンピュータとソフトウェアプログラムとによっても実現することができる。
【００３３】
最小値記憶部１０５は，動き探索においてフレーム間予測誤差の最小値Ｍを記憶しておくものであり，ブロックごとの動きベクトルの探索開始時には，初期値として十分に大きな値を設定しておく。
【００３４】
符号化対象ブロック画素値和算出部１０１は，符号化対象フレーム１２０において，これから符号化しようとするブロックの画素値和を算出し，算出した画素値和Ｃを画素値和記憶部１０３に記憶する。一方，整数画素位置の参照ブロック画素値和算出部１０２は，参照フレーム１２１における整数動きベクトルの指す参照ブロックの画素値和を算出し，算出した画素値和Ｓxyを画素値和記憶部１０４に記憶する。この画素値和Ｓxyの算出では，後に詳述するように既に算出済みの画素値和Ｓxy’を利用して演算数を削減することができる。
【００３５】
下限値算出部１０６は，画素値和記憶部１０３の画素値和Ｃと，画素値和記憶部１０４の画素値和Ｓxyとを利用して，小数画素精度の動きベクトルｖ* に対するＭＣ誤差の下限値Ｌを算出する。
【００３６】
下限値比較部１０７は，算出された下限値Ｌとそれまでで最小のＭＣ誤差である最小値記憶部１０５の最小値Ｍとを比較する。フレーム間予測誤差算出部１０８は，下限値比較部１０７での比較の結果，下限値ＬがＭＣ誤差の最小値Ｍより小さかった場合にのみ，動きベクトルｖ* に対するＭＣ誤差Ｅ（ｖ* ）を算出する。誤差比較部１０９は，算出されたＭＣ誤差Ｅ（ｖ* ）とＭＣ誤差の最小値Ｍとを比較し，ＭＣ誤差Ｅ（ｖ* ）のほうが小さければ，最小値更新部１１０にＭＣ誤差Ｅ（ｖ* ）を渡す。最小値更新部１１０は，そのＭＣ誤差Ｅ（ｖ* ）をＭＣ誤差の最小値Ｍとして最小値記憶部１０５に格納する。また，動きベクトル記憶部１１１に，そのときの動きベクトルｖ* をその時点で最も相応しい動きベクトルとして記憶する。
【００３７】
下限値比較部１０７による比較の結果，下限値ＬがＭＣ誤差の最小値Ｍ以上の場合，また，誤差比較部１０９による比較の結果，算出されたＭＣ誤差Ｅ（ｖ* ）がＭＣ誤差の最小値Ｍ以上の場合，または最小値更新部１１０による更新処理の終了後に，動きベクトル更新部１１２により，探索範囲内の次の参照ブロックを定める動きベクトルｖ* を小数画素精度で更新し，下限値算出部１０６によりその動きベクトルｖ* に対するＭＣ誤差の下限値Ｌを算出し，同様に処理を繰り返す。探索範囲に含まれるすべての動きベクトルに対する処理が終了したならば，最終的に動きベクトル記憶部１１１に記憶している動きベクトルｖ* を，動きベクトル推定装置１００の出力とする。
【００３８】
〔下限値の導出〕
以下，本実施の形態におけるＭＣ誤差の下限値の導出について説明する。本実施の形態では，小数画素精度の動きベクトルｖ* に対するＭＣ誤差（以下，小数ＭＣ誤差という）の下限値を導出する。以下では，式（８ａ）〜（８ｄ）の補間画像を用いた１／２画素精度ＭＣを例として説明する。このとき，動きベクトルｖ* のとり得る値は，次の４通りである。
【００３９】
【数６】
2005252569.tif 000008
ここで，δx ＝（１，０），δy ＝（０，１）であり，ｖは整数値を要素とするベクトルである。なお，動きベクトルｖ* が，ｖ* ＝ｖとして整数値を要素とする場合には整数動きベクトルと呼び，それ以外の場合には小数動きベクトルと呼ぶものとする。以下，ｖ* の値に応じてＥ（ｖ* ）を４通りに場合分けし，各下限値を求める。
【００４０】
（ｉ）ｖ* ＝ｖの場合：
動きベクトルｖ* は参照フレーム中の画素位置を指すため，整数ＭＣにおけるＳＥＡの場合と同様に，ＭＣ誤差Ｅ（ｖ* ）は次の下限値を持つ。
【００４１】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）                                          （１３）
ここで，Ｃ，Ｓ（ｖ）は，各々上記の式（４），式（５）で表されるものとする。
【００４２】
（ii）ｖ* ＝ｖ＋δx ／２の場合：
動きベクトルｖ* の指す参照フレームの位置は２画素の中心となり，ＭＣ誤差Ｅ（ｖ* ）は次の下限値を持つ。
【００４３】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）／２−Ｓ（ｖ＋δx ）／２                  （１４）
式（１４）の証明は以下の通りである。なお，以下の証明において，式（１５ａ）から式（１５ｂ）への展開では，動きベクトルｖ* の指す参照フレームの位置は２画素の中心となることから，式（８ｂ）を用いた。
【００４４】
【数７】
2005252569.tif 000009
（iii ）ｖ* ＝ｖ＋δy ／２の場合：
上述の（ii）の場合と同様に，動きベクトルｖ* の指す参照フレームの位置は２画素の中心となり，ＭＣ誤差Ｅ（ｖ* ）は次の下限値を持つ。
【００４５】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）／２−Ｓ（ｖ＋δy ）／２                  （１６）
証明は（ii）の場合と同様に行うことができる。
【００４６】
（iv）ｖ* ＝ｖ＋（δx ＋δy ）／２の場合：
動きベクトルｖ* の指す参照フレームの位置は４画素の中央となり，ＭＣ誤差Ｅ（ｖ* ）は次の下限値を持つ。
【００４７】
Ｅ（ｖ* ）≧Ｃ−Ｓ（ｖ）／４−Ｓ（ｖ＋δx ）／４
−Ｓ（ｖ＋δy ）／４−Ｓ（ｖ＋δx ＋δy ）／４      （１７）
式（１７）の証明は以下の通りである。なお，以下の証明において，式（１８ａ）から式（１８ｂ）への展開では，動きベクトルｖ* の指す参照フレームの位置は４画素の中央となることから，式（８ｄ）を用いた。
【００４８】
【数８】
2005252569.tif 000010
以上（ｉ）〜（iv）をまとめると，ＭＣ誤差の下限値Ｌ（ｖ* ）は，次の式（１９）に示す通りとなる。
【００４９】
【数９】
2005252569.tif 000011
〔下限値の高速な計算法〕
以下，本実施の形態における小数ＭＣ誤差の下限値の高速な計算法について説明する。ここでは，上述の下限値Ｌ（ｖ* ）が少ない計算量で算出できることを示す。
【００５０】
式（１９）に示す下限値Ｌ（ｖ* ）の計算は，式（４）と式（５）との２要素からなる。つまり，小数画素位置でのＭＣ誤差の下限値Ｌ（ｖ* ）が，整数画素位置の画素値から定まるということである。したがって，上述の（ｉ）の整数動きベクトルの場合にＳ（ｖ）を計算しておけば，残る（ii）〜（iv）の場合には，その計算結果を再利用して大幅に計算量を削減できる。なお，Ｃについては，動きベクトルｖによらず一定であるので，一度計算しておけば，再計算の必要はない。
【００５１】
さらに，Ｓ（ｖ）の計算では，すでに計算済みの整数動きベクトルｕに対する計算結果Ｓ（ｕ）を利用することにより，計算量を少なく抑えることができる。以下，図２を用いて説明する。
【００５２】
図２は，本実施の形態におけるＳ（ｖ）の高速な計算法を説明する図である。図２において，Ａ（ｖ）は，参照フレーム中で動きベクトルｖが指す領域であり，ｆt-1 （ｐ−ｖ），ｐ∈Ｂを含んでいる。このとき，ｑ＝ｐ−ｖとすると，上記の式（５）は，次の式（２０）のように表すことができる。
【００５３】
【数１０】
2005252569.tif 000012
動きベクトルｖの指す領域Ａ（ｖ）と動きベクトルｕの指す領域Ａ（ｕ）とが，図２（ａ）に示す関係にあるものとし，領域Ａ（ｖ）と領域Ａ（ｕ）とに共通する領域（図２においてハッチングされた部分）を領域Ｃ（ｕ，ｖ）とする。このとき，図２（ｂ）に示す関係を用いて，次のような式展開が可能である。なお，領域Ａ（ｖ）から領域Ｃ（ｕ，ｖ）を除いた領域をＡ（ｖ）／Ｃ（ｕ，ｖ）と表し，領域Ａ（ｕ）から領域Ｃ（ｕ，ｖ）を除いた領域をＡ（ｕ）／Ｃ（ｕ，ｖ）と表すものとする。
【００５４】
【数１１】
2005252569.tif 000013
このように，Ｓ（ｖ）の計算において，すでに計算済のＳ（ｕ）を利用すれば，新たに計算するのはＳ（ｖ）とＳ（ｕ）との差分のみとなり，計算量を少なく抑えることができる。
【００５５】
〔動きベクトル推定処理〕
図３は，本実施の形態における動きベクトル推定処理フローチャートである。ここでは，符号化対象フレームｆt （ｐ）および参照フレームｆt-1 （ｐ）を入力とし，探索範囲Ｒi に含まれる動きベクトルｖ∈Ｒi からフレーム間予測誤差Ｅ（ｖ）を最小化する動きベクトルを探索し，それを出力とする。なお，図３に示す動きベクトルの探索は，符号化対象フレームの各領域Ｂi ごとに行われる。
【００５６】
まず，フレーム間予測誤差の最小値を格納するレジスタＭに，十分に大きな値を入れ，初期化する（ステップＳ１０）。次に，動きベクトルｖ＝（ｘ，ｙ）に対するフレーム間予測誤差の下限値を求めるのに先立ち，符号化ブロックの画素値和Ｃを算出し，それをレジスタｃに格納する（ステップＳ１１）。また，整数動きベクトルの指す参照ブロックの画素値和Ｓ（ｖ）を算出し，レジスタｓ［ｘ，ｙ］に格納する（ステップＳ１２）。ここで，参照ブロックの画素値和Ｓ（ｖ）は，上記の式（２１）に示すように，すでにレジスタに格納された近傍の参照ブロックの画素値和Ｓ（ｕ）を利用して求める。
【００５７】
なお，この参照ブロックの画素値和Ｓ（ｖ）は，図１に示す整数画素位置の参照ブロック画素値和算出部１０２において，参照フレーム１２１における全ての整数画素位置の参照ブロックについて事前に算出するようにすれば，各符号化対象ブロックの符号化処理ごとに求める必要はない。
【００５８】
次に，上記の式（１９）により動きベクトルｖに対するフレーム間予測誤差の下限値Ｌ（ｖ* ）を算出し，レジスタＬに格納する（ステップＳ１３）。このとき，小数画素位置の動きベクトルに対するフレーム間予測誤差の下限値の計算では，上記の下限値の高速な計算法で説明したように，レジスタｃに格納された符号化ブロックの画素値和Ｃ，およびレジスタｓ［ｘ，ｙ］に格納された整数画素位置の動きベクトルに対する参照ブロック画素値和Ｓ（ｖ）の値を参照することにより，重複する計算を省略することができる。
【００５９】
レジスタＬの値とレジスタＭの値とを比較し（ステップＳ１４），Ｍ≦Ｌが満たされる場合には，動きベクトルｖに対するフレーム間予測誤差Ｅ（ｖ）がＭ≦Ｅ（ｖ）となるので，この動きベクトルｖは最適解の候補から外れる。したがって，ステップＳ１８へ進む。
【００６０】
一方，Ｍ＞Ｌの場合には，フレーム間予測誤差Ｅ（ｖ）がレジスタＭの値よりも小さくなる可能性があるので，フレーム間予測誤差Ｅ（ｖ）を算出する（ステップＳ１５）。続いて，フレーム間予測誤差Ｅ（ｖ）とレジスタＭの値との大小比較を行い（ステップＳ１６），Ｍ≦Ｅ（ｖ）が満たされる場合には，この動きベクトルｖは最適解の候補から外れるので，ステップＳ１８へ進む。
【００６１】
ステップＳ１６において，Ｍ＞Ｅ（ｖ）の場合（フレーム間予測誤差Ｅ（ｖ）のほうが小さい場合）には，レジスタＭの値を，ステップＳ１５で算出したフレーム間予測誤差Ｅ（ｖ）に更新し，このときの動きベクトルｖを最適な動きベクトルの候補としてレジスタＵに格納する（ステップＳ１７）。
【００６２】
ステップＳ１３〜Ｓ１７の処理を，動きベクトルを更新しながら探索範囲Ｒi に含まれるすべての動きベクトルについて行い（ステップＳ１８，Ｓ１９），最終的なレジスタＵの値を最適な動きベクトルとして出力する（ステップＳ２０）。
【図面の簡単な説明】
【００６３】
【図１】本発明の実施の形態に係る動きベクトル推定装置の構成例を示す図である。
【図２】本実施の形態におけるＳ（ｖ）の高速な計算法を説明する図である。
【図３】本実施の形態における動きベクトル推定処理フローチャートである。
【図４】一般的な動画像符号化装置の構成例を示す図である。
【符号の説明】
【００６４】
１  動き探索部
２  フレームメモリ
３  動き補償部
４  減算器
５  ＤＣＴ部
６  量子化部
７  符号化部
８  逆量子化部
９  逆ＤＣＴ部
１０  加算器
１００  動きベクトル推定装置
１０１  符号化対象ブロック画素値和算出部
１０２  整数画素位置の参照ブロック画素値和算出部
１０３，１０４  画素値和記憶部
１０５  最小値記憶部
１０６  下限値算出部
１０７  下限値比較部
１０８  フレーム間予測誤差算出部
１０９  誤差比較部
１１０  最小値更新部
１１１  動きベクトル記憶部
１１２  動きベクトル更新部
１２０  符号化対象フレーム
１２１  参照フレーム
【図１】
2005252569.tif 000014
【図２】
2005252569.tif 000015
【図３】
2005252569.tif 000016
【図４】
2005252569.tif 000017