(57)【要約】      （修正有）【課題】簡単な構成で、探索中心点が最も類似度が高くなっても、追跡を停止しないで、その先が追跡可能な、局所解に陥りにくい、追跡型動きベクトル検出装置を提供する。【解決手段】上下左右の探索点に対応する参照ブロックのうち、対象ブロックとの類似度が最も高いブロックを検出する類似ブロック検出手段７−３と、これまで検出された前記参照ブロックのうち、類似度が最も高いブロックを記憶する記憶手段７−６と、前記検出された参照ブロックと前記記憶された参照ブロックを比較して、記憶された参照ブロックの類似度の方が高く、かつ追跡回数が偶数番目の場合に限り終了と判定する終了判定手段７−８と、終了とされなかった場合には前記検出された参照ブロックの位置を追跡中心として次の追跡動作に入る一方、終了とされた場合には、前記検出された参照ブロックの位置から動きベクトルを検出する制御手段７−１とを備える。【選択図】図２
2007235333.tif 000002
【特許請求の範囲】
【請求項１】
動き補償予測符号化で圧縮の対象となる画像ブロックを、所定の探索パターンに基づいて配置された参照画像上の複数のブロックと比較し、前記比較した複数のブロックの中で最も類似した参照ブロックを検出し、前記検出した参照ブロックの位置に前記探索パターンを移動させて移動による追跡処理を繰り返すことにより、圧縮対象ブロックに最も類似した参照ブロックを検出して、動きベクトルを求める追跡型動きベクトル検出装置において、
上下左右４つの探索点を有する探索パターンの追跡中心位置を、参照画像上に設定する追跡中心位置設定手段と、
前記圧縮対象ブロックのアドレス、および前記追跡中心位置設定された探索パターンの探索点に配置された複数の参照ブロックのアドレスを設定するアドレス設定手段と、
前記アドレス設定された圧縮対象ブロックと前記アドレス設定された複数の各参照ブロックとの画像をそれぞれ比較して、前記比較された各参照ブロックの類似度を計算する類似度計算手段と、
前記計算された類似度により、前記複数の参照ブロックのうち、類似度の最も高い参照ブロックを検出する類似ブロック検出手段と、
前記類似ブロック検出手段で検出された類似度の最も高い参照ブロックの類似度と、記憶部に既に記憶されている参照ブロックの類似度とを比較して、前記記憶された参照ブロックの類似度の方が低い場合には、この参照ブロックの類似度および参照ブロックの位置を、前記検出された参照ブロックの類似度および参照ブロックの位置に置き換えて更新する一方、前記記憶された参照ブロックの類似度の方が高いか等しく、かつ繰り返し回数が隔数回の場合に限り、終了と判定する更新終了判定手段と、
前記更新終了判定手段により終了と判定されなかった場合には、前記追跡中心位置設定手段により探索パターンの追跡中心位置として設定された前記検出された参照ブロックの位置に基づいて、追跡処理を繰り返すよう制御する一方、終了と判定された場合には、前記記憶部に記憶されている参照ブロックの位置から動きベクトル検出するよう制御する制御手段と、
を備えたことを特徴とする動きベクトル検出装置。
【請求項２】
動き補償予測符号化で圧縮の対象となる画像ブロックを、所定の探索パターンに基づいて配置された参照画像上の複数のブロックと比較し、前記比較した複数のブロックの中で最も類似した参照ブロックを検出し、前記検出した参照ブロックの位置に前記探索パターンを移動させて移動による追跡処理を繰り返すことにより、圧縮対象ブロックに最も類似した参照ブロックを検出して、動きベクトルを求める追跡型動きベクトル検出装置において、
上下左右４つの探索点を有する探索パターンの追跡中心位置を、参照画像上に設定する追跡中心位置設定手段と、
前記圧縮対象ブロックのアドレス、および前記追跡中心位置設定された探索パターンの探索点に配置された複数の参照ブロックのアドレスを設定するアドレス設定手段と、
前記アドレス設定された圧縮対象ブロックと前記アドレス設定された複数の各参照ブロックとの画像をそれぞれ比較して、前記比較された各参照ブロックの類似度を計算する類似度計算手段と、
前記計算された類似度により、前記複数の参照ブロックのうち、類似度の最も高い参照ブロックを検出する類似ブロック検出手段と、
前記類似ブロック検出手段で検出された類似度の最も高い参照ブロックの類似度と、記憶部に既に記憶されている参照ブロックの類似度とを比較して、前記記憶された参照ブロックの類似度の方が低い場合には、この参照ブロックの類似度および参照ブロックの位置を、前記検出された参照ブロックの類似度および参照ブロックの位置に置き換えて更新する一方、前記記憶された参照ブロックの類似度の方が高いか等しく、かつ前記類似ブロック検出手段で検出された参照ブロックの位置と前記記憶部に記憶された参照ブロックの位置を比較して、一致した場合に限り終了と判定する更新終了判定手段と、
前記更新終了判定手段により終了と判定されなかった場合には、前記追跡中心位置設定手段により探索パターンの追跡中心位置として設定された前記検出された参照ブロックの位置に基づいて、追跡処理を繰り返すよう制御する一方、終了と判定された場合には、前記記憶部に記憶されている参照ブロックの位置から動きベクトル検出するよう制御する制御手段と、
を備えたことを特徴とする動きベクトル検出装置。
【請求項３】
動き補償予測符号化で圧縮の対象となる画像ブロックを、所定の探索パターンに基づいて配置された参照画像上の複数のブロックと比較し、前記比較した複数のブロックの中で最も類似した参照ブロックを検出し、前記検出した参照ブロックの位置に前記探索パターンを移動させて移動による追跡処理を繰り返すことにより、圧縮対象ブロックに最も類似した参照ブロックを検出して、動きベクトルを求める追跡型動きベクトル検出装置において、
上下左右４つの探索点を有する探索パターンの追跡中心位置を、参照画像上に設定する追跡中心位置設定手段と、
前記圧縮対象ブロックのアドレス、および前記追跡中心位置設定された探索パターンの探索点に配置された複数の参照ブロックのアドレスを設定するアドレス設定手段と、
前記アドレス設定された圧縮対象ブロックと前記アドレス設定された複数の各参照ブロックとの画像をそれぞれ比較して、前記比較された各参照ブロックの類似度を計算する類似度計算手段と、
前記計算された類似度により、前記複数の参照ブロックのうち、類似度の最も高い参照ブロックを検出する類似ブロック検出手段と、
前記類似ブロック検出手段で検出された類似度の最も高い参照ブロックの類似度と、記憶部に既に記憶されている参照ブロックの類似度とを比較して、前記記憶された参照ブロックの類似度の方が低い場合には、この参照ブロックの類似度および参照ブロックの位置を、前記検出された参照ブロックの類似度および参照ブロックの位置に置き換える更新手段と、
前記追跡処理の繰り返し回数が所定の追跡処理回数になると、終了と判定する終了判定手段と、
前記終了判定手段により終了と判定されなかった場合には、前記追跡中心位置設定手段により探索パターンの追跡中心位置として設定された前記検出された参照ブロックの位置に基づいて、追跡処理を繰り返すよう制御する一方、終了と判定された場合には、前記記憶部に記憶されている参照ブロックの位置から動きベクトル検出するよう制御する制御手段と、
を備えたことを特徴とする動きベクトル検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像圧縮符号化に用いられる追跡型の動きベクトルの検出装置に関するものである。
【背景技術】
【０００２】
蓄積メディア、放送、通信などの動画像の圧縮符号化には、ＭＰＥＧに代表される動き補償予測を使った符号化方式が使われている。この方式では、画像のブロック（例えば、マクロブロック。以下、画像のブロックを代表してＭＢとも記す。）を単位として、フレーム間の動き量に相当する動きベクトル（以下、ＭＶとも記す。）を求め、圧縮対象ブロックの画像を伝送する代わりに、１フレーム前の参照画像上の前記ブロック予測位置におけるＭＢと前記ＭＢの画像の差分（予測誤差）を伝送して、データ量を減らすものである。
【０００３】
この動きベクトルＭＶは、圧縮対象画像ブロックＭＢｏを、所定の探索範囲の参照画像と画像比較（ブロックマッチング）して、類似度を計算し、参照画像上の最も類似したブロックＭＢｒを検出し、圧縮対象ブロックの位置ＰＢｏと最も類似した参照ブロックの位置ＰＢｒのずれとして検出する。なお、位置は画素を単位として（Ｘ，Ｙ）座標で表す。
ＭＶ＝ＰＢｏ−ＰＢｒ
ただし、類似度には、通常類似度とは逆相関の関係にある誤差評価値が使われ、例えばＭＢ間の差分絶対値の総和（ＳＡＤ：Ｓｕｍ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ）を使うが、差分自乗和、または圧縮符号化後の符号量などを用いてもよい。（以下、誤差評価値を代表してＳＡＤとも記す。）
この動きベクトルの検出精度は、データ量、結果的には画像品質に大きく影響するが、ＭＶ検出には大量の演算が必要となるため、少ない演算量で効果のある方法が求められている。そこで、解像度の低い画像でおおまかなＭＶを求め、さらに精度を上げてＭＶを求める階層型検出法、後述する追跡型検出法（逐次探索型検出法ともいう。）、またブロックマッチングによらない勾配法などの演算量の少ない動きベクトル探索手法が提案され、用途に合わせて、単独あるいは組み合わせて使われている。
【０００４】
従来の追跡型動きベクトル検出法について、図１０を参照して説明する。
追跡型動きベクトル検出法では、追跡中心点の周りに上下左右に１画素ずらした４点および追跡中心点の５点の探索点を有する探索パターン（図１０（Ａ）参照。）に基づいて、複数の探索点に配置された参照ブロックの中から圧縮対象ブロックと最も類似した参照ブロックを検出して、その検出点に探索パターンの中心を移動させる。そして、この処理を中心点が極小となり移動が停止するまで繰り返し、最も類似した参照ブロックを追跡することにより、対象ブロックと最も類似した参照ブロックの位置を求め、動きベクトルを検出するものである。（例えば、特許文献１参照。）
以下、追跡動作を具体的に説明する。図１０（Ｂ）は、探索範囲を垂直３画素、水平８画素とした場合の、ＳＡＤの分布例、また図１０（Ｃ）は、探索パターンによる追跡動作の繰り返し回数（カウント）を、追跡回数＃（番号）として表示したものである。なお、以下、探索パターンの位置は中心点で代表させ、ブロックの位置は１行１列目の左上の点で代表させるとともに、説明の簡略化のため、対象ブロック位置、および灰色で示した初期中心点をともに（０，０）とする。
追跡回数＃１では、探索パターンを初期中心点（０，０）において、十字型探索パターン５点のＳＡＤが計算され、右点（ＳＡＤ＝２０）が５点最小点として検出され、追跡中心点を右に１画素移動する。ＳＡＤ最小点の位置ＰＢｍｉｎは、（１，０）となる。
次に、追跡回数＃２では、追跡中心点（１，０）において、同様に探索パターン５点のＳＡＤが計算され、右点（ＳＡＤ＝１６）が５点最小点として検出され、追跡中心点は右に１画素移動する。ＳＡＤ最小点の位置ＰＢｍｉｎは、（２，０）となる。
追跡回数＃３では、追跡中心点（２，０）において、同様に探索パターン５点のＳＡＤが計算されるが、ここでは、中心点（ＳＡＤ＝１６）が５点最小点として検出されるので、追跡は終了して、記憶されているＳＡＤ最小点の位置ＰＢｍｉｎ（２，０）がＭＶとなる。
実はこの追跡動作例では、図１０（Ｂ）に示すＳＡＤ分布の場合、極小点（２，０）まで達しているが、最小点（５，０）には達していない。すなわち、追跡型動きベクトル検出法は、探索範囲を全てブロックマッチングして調べる方法に比べて、ブロックマッチングの回数が少なく、演算量も少なくて済むが、必ずしも正しいＭＶを求められるとは限らず、追跡ルート上の局所解に陥り追跡を停止してしまうこともある。すなわち、上下左右周辺点上にＳＡＤが単調減少する追跡ルートがある間は、最小値を求めて追跡を続けるが、中心点が極小となって、上下左右４点のＳＡＤがいずれも大きい場合には、それらが障壁となって、その先にもっと小さなＳＡＤがあっても、そこに到達することはできない。
このため、追跡型検出法は、階層型探索法により予め探索範囲を狭めてから補助的に使う組み合わせ用途、また演算処理能力が低い携帯端末などの簡易型用途などに使われる。
【特許文献１】特開２００４−２３６０２３号公報（第５−７頁、第１−３図）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
追跡型動きベクトル探索法は、少ない演算量で動きベクトルを効率的に検出できるが、その追跡過程で、単調減少ルートが見つからない場合には、その１画素先に最小値があっても、そこで追跡は終了し局所解に陥るという問題があった。
【０００６】
そこで、本発明は、上記のような問題点を解消するためになされたもので、演算量を増やすことなく、簡単な構成で、１画素だけであれば、単調減少ルートが途切れても、さらに先の最小値を追跡でき、局所解に陥りにくい動きベクトルの検出装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本願発明における第１の発明は、動き補償予測符号化で圧縮の対象となる画像ブロックを、所定の探索パターンに基づいて配置された参照画像上の複数のブロックと比較し、前記比較した複数のブロックの中で最も類似した参照ブロックを検出し、前記検出した参照ブロックの位置に前記探索パターンを移動させて移動による追跡処理を繰り返すことにより、圧縮対象ブロックに最も類似した参照ブロックを検出して、動きベクトルを求める追跡型動きベクトル検出装置において、上下左右４つの探索点を有する探索パターンの追跡中心位置を、参照画像上に設定する追跡中心位置設定手段（追跡中心設定部７−４）と、前記圧縮対象ブロックのアドレス、および前記追跡中心位置設定された探索パターンの探索点に配置された複数の参照ブロックのアドレスを設定するアドレス設定手段（アドレス設定部７−５）と、前記アドレス設定された圧縮対象ブロックと前記アドレス設定された複数の各参照ブロックとの画像をそれぞれ比較して、前記比較された各参照ブロックの類似度を計算する類似度計算手段（ＳＡＤ計算部７−２）と、前記計算された類似度により、前記複数の参照ブロックのうち、類似度の最も高い参照ブロックを検出する類似ブロック検出手段（ＳＡＤ４点最小ブロック検出部７−３）と、前記類似ブロック検出手段で検出された類似度の最も高い参照ブロックの類似度と、記憶部に既に記憶されている参照ブロックの類似度とを比較して、前記記憶された参照ブロックの類似度の方が低い場合には、この参照ブロックの類似度および参照ブロックの位置を、前記検出された参照ブロックの類似度および参照ブロックの位置に置き換えて更新する一方、前記記憶された参照ブロックの類似度の方が高いか等しく、かつ繰り返し回数が隔数回の場合に限り、終了と判定する更新終了判定手段（最小点記憶部７−６、ＳＡＤ最小点検出部７−７、終了判定部７−８）と、前記更新終了判定手段により終了と判定されなかった場合には、前記追跡中心位置設定手段により探索パターンの追跡中心位置として設定された前記検出された参照ブロックの位置に基づいて、追跡処理を繰り返すよう制御する一方、終了と判定された場合には、前記記憶部に記憶されている参照ブロックの位置から動きベクトル検出するよう制御する制御手段（制御部７−１）とを備えたことを特徴とする動きベクトル検出装置を提供する。
第２の発明は、動き補償予測符号化で圧縮の対象となる画像ブロックを、所定の探索パターンに基づいて配置された参照画像上の複数のブロックと比較し、前記比較した複数のブロックの中で最も類似した参照ブロックを検出し、前記検出した参照ブロックの位置に前記探索パターンを移動させて移動による追跡処理を繰り返すことにより、圧縮対象ブロックに最も類似した参照ブロックを検出して、動きベクトルを求める追跡型動きベクトル検出装置において、上下左右４つの探索点を有する探索パターンの追跡中心位置を、参照画像上に設定する追跡中心位置設定手段（追跡中心設定部７−４）と、前記圧縮対象ブロックのアドレス、および前記追跡中心位置設定された探索パターンの探索点に配置された複数の参照ブロックのアドレスを設定するアドレス設定手段（アドレス設定部７−５）と、前記アドレス設定された圧縮対象ブロックと前記アドレス設定された複数の各参照ブロックとの画像をそれぞれ比較して、前記比較された各参照ブロックの類似度を計算する類似度計算手段（ＳＡＤ計算部７−２）と、前記計算された類似度により、前記複数の参照ブロックのうち、類似度の最も高い参照ブロックを検出する類似ブロック検出手段（ＳＡＤ４点最小ブロック検出部７−３）と、前記類似ブロック検出手段で検出された類似度の最も高い参照ブロックの類似度と、記憶部に既に記憶されている参照ブロックの類似度とを比較して、前記記憶された参照ブロックの類似度の方が低い場合には、この参照ブロックの類似度および参照ブロックの位置を、前記検出された参照ブロックの類似度および参照ブロックの位置に置き換えて更新する一方、前記記憶された参照ブロックの類似度の方が高いか等しく、かつ繰り返し回数が隔数回の場合に限り、終了と判定する更新終了判定手段（最小点記憶部７−６、ＳＡＤ最小点検出部７−７、終了判定部７−８）と、前記更新終了判定手段により終了と判定されなかった場合には、前記追跡中心位置設定手段により探索パターンの追跡中心位置として設定された前記検出された参照ブロックの位置に基づいて、追跡処理を繰り返すよう制御する一方、前記記憶された参照ブロックの類似度の方が高いか等しく、かつ前記類似ブロック検出手段で検出された参照ブロックの位置と前記記憶部に記憶された参照ブロックの位置を比較して、一致した場合に限り終了と判定する更新終了判定手段（最小点記憶部７−６、ＳＡＤ最小点検出部７−７、終了判定部７−９）と、前記更新終了判定手段により終了と判定されなかった場合には、前記追跡中心位置設定手段により探索パターンの追跡中心位置として設定された前記検出された参照ブロックの位置に基づいて、追跡処理を繰り返すよう制御する一方、終了と判定された場合には、前記記憶部に記憶されている参照ブロックの位置から動きベクトル検出するよう制御する制御手段（制御部７−１）とを備えたことを特徴とする動きベクトル検出装置を提供する。
第３の発明は、動き補償予測符号化で圧縮の対象となる画像ブロックを、所定の探索パターンに基づいて配置された参照画像上の複数のブロックと比較し、前記比較した複数のブロックの中で最も類似した参照ブロックを検出し、前記検出した参照ブロックの位置に前記探索パターンを移動させて移動による追跡処理を繰り返すことにより、圧縮対象ブロックに最も類似した参照ブロックを検出して、動きベクトルを求める追跡型動きベクトル検出装置において、上下左右４つの探索点を有する探索パターンの追跡中心位置を、参照画像上に設定する追跡中心位置設定手段（追跡中心設定部７−４）と、前記圧縮対象ブロックのアドレス、および前記追跡中心位置設定された探索パターンの探索点に配置された複数の参照ブロックのアドレスを設定するアドレス設定手段（アドレス設定部７−５）と、前記アドレス設定された圧縮対象ブロックと前記アドレス設定された複数の各参照ブロックとの画像をそれぞれ比較して、前記比較された各参照ブロックの類似度を計算する類似度計算手段（ＳＡＤ計算部７−２）と、前記計算された類似度により、前記複数の参照ブロックのうち、類似度の最も高い参照ブロックを検出する類似ブロック検出手段（ＳＡＤ４点最小ブロック検出部７−３）と、前記類似ブロック検出手段で検出された類似度の最も高い参照ブロックの類似度と、記憶部に既に記憶されている参照ブロックの類似度とを比較して、前記記憶された参照ブロックの類似度の方が低い場合には、この参照ブロックの類似度および参照ブロックの位置を、前記検出された参照ブロックの類似度および参照ブロックの位置に置き換える更新手段（最小点記憶部７−６、ＳＡＤ最小点検出部７−７）と、前記追跡処理の繰り返し回数が所定の追跡処理回数になると、終了と判定する終了判定手段（終了判定部７−１０）と、前記終了判定手段により終了と判定されなかった場合には、前記追跡中心位置設定手段により探索パターンの追跡中心位置として設定された前記検出された参照ブロックの位置に基づいて、追跡処理を繰り返すよう制御する一方、終了と判定された場合には、前記記憶部に記憶されている参照ブロックの位置から動きベクトル検出するよう制御する制御手段（制御部７−１）とを備えたことを特徴とする動きベクトル検出装置を提供する。
【発明の効果】
【０００８】
各請求項記載の本発明によれば、上下左右の周辺点に配置された参照ブロックのうち圧縮対象ブロックと最も類似した参照ブロックへ追跡中心点の移動を繰り返して、最も類似した参照ブロックの位置を追跡するが、必ずしも追跡中心点が上下左右の周辺点で最も類似した位置に達した場合に追跡を終了するわけではなく、さらに先の類似した位置を追跡することができる。このため、局所解に陥る確率を減少させることができる。
また第１の発明によれば、繰り返し回数が偶数または奇数どちらかの追跡処理の場合に限り追跡を終了する構成であるので、従来例をほとんど変更しないで、簡単に実現できる。
また第２の発明によれば、追跡中に中心点が同一位置に回帰することにより追跡を終了する。このため、追跡回数の偶数／奇数などに左右されず、局所解に陥る確率をさらに減少させることができる。
また第３の発明によれば、所定の追跡回数になると追跡を終了するため、制限回数になるまでの追跡処理で見つかった最も類似した参照ブロックから動きベクトルを検出する。このため、動きベクトルの検出にかかる時間はいつも一定であり、同期した処理が必要な圧縮符号化装置に使用すると好適である。
【発明を実施するための最良の形態】
【０００９】
本発明は、追跡型動きベクトル検出方法の従来の終了判定方法を改良することによって、局所解に陥る確率を減少させたものである。以下、本発明を実施するための最良の形態につき、好ましい実施例を用い説明する。
【実施例１】
【００１０】
実施例１について、図１〜図５を用いて説明する。図１は、動画像符号化装置の構成を示した図である。図２は、動き補償予測部の構成を示した図である。図３は、動作フローチャートを示す。図４と図５は、追跡動作の例を示した図である。
【００１１】
最初に、動き補償予測符号化装置について説明する。本実施例における動画像符号化装置は、図１に示すように、対象画像メモリ１、減算器２、予測誤差符号化部３、予測誤差復号化部４、加算器５、参照画像メモリ６、動き補償予測部７、可変長符号化部８から構成され、以下のように動画像符号化を実現している。
入力された画像は、対象画像メモリ１に蓄積されて、コントローラ（表示せず。）の制御のもとに、ＭＢを単位として、圧縮対象画像として出力され、減算器２により後述する予測画像との差分をとって、予測誤差を生成して、予測誤差符号化部３によりＤＣＴ変換・量子化された符号を、可変長符号化部８により可変長符号化、フォーマット化して、圧縮画像として出力される。また前記予測画像は、動き補償予測部７により、対象画像メモリ１出力の対象画像と参照画像メモリ６出力の１フレーム前の参照画像とから、動きベクトルを求めて、動き補償された予測画像として生成されたもので、動きベクトルとともに出力される。この時の参照画像は、局部復号され参照画像メモリ６に蓄積された符号化済みの画像画像が使われる。局部復号は、前記ＤＣＴ変換・量子化された符号が、予測誤差復号化部４によりもとの予測誤差に復号されて、加算器５により前記予測画像に加算されることにより復号される。
【００１２】
次に、本発明の主要部である前期動き補償予測部７の構成、および各要素の機能について説明する。動き補償予測部７は、制御部７−１、ＳＡＤ計算部７−２、ＳＡＤ４点最小ブロック検出部７−３、追跡中心設定部７−４、アドレス設定部７−５、最小点記憶部７−６、ＳＡＤ最小点検出部７−７、終了判定部７−８から構成されている。
ＳＡＤ計算部７−２は、４つのＳＡＤ計算部を備え、圧縮対象ＭＢ、および上下左右探索点の各参照ＭＢを入力して、ブロックマッチングを行って、差分絶対値和ＳＡＤを求め、上下左右探索点のＳＡＤをそれぞれ、ＳＡＤ４点最小ブロック検出部７−３に出力する。なお、ＳＡＤ計算部７−２は、本来３個備えていれば演算は可能であるが、移動方向の判定処理などが必要となるため、本実施例では、４個として高速化したものである。また、ＳＡＤ計算部２つで時分割処理を行い、４個のＳＡＤを計算しても、同様の効果が得られる。
ＳＡＤ４点最小ブロック検出部７−３は、ＳＡＤ計算部７−２から出力された上下左右ＭＢのＳＡＤの値が最小となるＭＢを判別して、前記最小ＭＢのＳＡＤの値（以下、ＳＡＤ４ｍｉｎとも記す。）、およびそのＭＢ位置（以下、ＰＢ４ｍｉｎとも記す。）を出力する。
追跡中心設定部７−４は、前記ＰＢ４ｍｉｎを入力して、これを追跡中心点として出力する。なお、追跡開始の初期設定時には、制御部７−１から入力した初期中心点を追跡中心点として出力する。
アドレス設定部７−５は、制御部７−１から入力した対象画像メモリ１の圧縮対象ＭＢのアドレス、および前記追跡中心設定部７−４から入力した追跡中心点にもとづく参照画像メモリ６の上下左右の参照ＭＢのアドレスを設定して、対応するＭＢデータをＳＡＤ計算部に読み込ませる。また、ＭＶ検出が完了した時には、終了処理として、参照画像メモリ６から、記憶部７−６に記憶されたＰＢｍｉｎ位置の参照ＭＢを読み出して予測画像として出力する機能も持つ。
最小点記憶部７−６は、これまで現れたＳＡＤの最小値ＳＡＤｍｉｎ、およびそのＭＢ位置ＰＢｍｉｎを記憶する部位である。
ＳＡＤ最小点検出部７−７は、ＳＡＤ４点最小ブロック検出部７−３から出力されたＳＡＤ４ｍｉｎと最小点記憶部７−６に記憶されたＳＡＤｍｉｎを比較して、ＳＡＤ４ｍｉｎの方が小さい場合には、ＳＡＤｍｉｎをＳＡＤ４ｍｉｎに書き換えるとともに、付随するＰＢｍｉｎもＰＢ４ｍｉｎに書き換えて、ＳＡＤが最小値となる最小点を更新する。逆にＳＡＤ４ｍｉｎの方が大きいか等しい場合には、追跡中心点が最小となったことを示す中心点極小信号を出力する。
終了判定部７−８は、中心点極小信号を受けて、制御部７−１に制御され、追跡回数が偶数回目の時に限り、制御部７−１に終了信号を出力する。奇数回目の時は無視する。
制御部７−１は、基本的には、全ての構成要素を制御（図示せず。）して、ＭＶ検出の進行制御を行い、ＭＶの追跡ステップを進める。特に、終了処理として、アドレス設定部７−５を制御して、予測画像を出力するとともに、対象ブロック位置ＰＢｏと参照ブロックの位置ＰＢｍｉｎの座標差分（図示せず。）を動きベクトルＭＶとして出力する。そして、各構成要素を制御して、次のＭＢのＭＶ検出にうつる。
なお、従来例では、中心点極小信号はそのまま終了信号となっている。すなわち、本実施例から、終了判定部７−８を削除して、中心点極小信号を終了信号としてそのまま出力すれば、従来例と一致するものである。
【００１３】
次に、前記構成の動き補償予測部７によるＭＶ検出動作手順について、図３のフローチャートを用いて説明する。
所定のＭＢのＭＶ検出が開始されると、まず制御部７−１は、圧縮対象ＭＢ位置ＰＢｏを更新して、初期設定を行う（ステップＳ１）。初期中心点は、周辺ＭＢから予測した位置（例えば、一つ前のＭＢのＭＶとＰＢｏの和）とする。記憶部７−６のＰＢｍｉｎは初期中心点位置、ＳＡＤｍｉｎは、初期中心点のＳＡＤの値とする。ただし、初期中心点のＳＡＤが不明な場合は、設定できる最大の値とする。終了判別部７−８の追跡回数ＣＴ（カウンタ）の値を０にセットする。
【００１４】
次に、追跡動作について説明する。追跡中心設定部７−４は、ＳＡＤ４点最小ブロック検出部７−３から出力されたＰＢ４ｍｉｎを追跡中心点として設定する（ステップＳ２）。ただし、最初は、初期設定の初期中心点のままとする。
アドレス設定部７−５は、圧縮対象ＭＢ位置ＰＢｏのＭＢを対象画像メモリ１から読み出してＳＡＤ計算部に書き込むとともに、追跡中心点ＰＢ４ｍｉｎの上下左右のＭＢを参照画像メモリ６から読み出して各上下左右のＳＡＤ計算部５−２に書き込む（ステップＳ３）。
ＳＡＤ計算部７−２は、前記書き込まれた圧縮対象ＭＢと参照ＭＢの各対応する画素の差分をとり、その絶対値の加算結果をＳＡＤとして計算して、上下左右それぞれ出力する。（ステップＳ４）
ＳＡＤ４点最小ブロック検出部７−３は、前記上下左右４つのＳＡＤのうち最も小さいＳＡＤのＭＢを最小ブロックとして、その中心点位置をＰＢ４ｍｉｎ、ＳＡＤの値をＳＡＤ４ｍｉｎとして出力する（ステップＳ５）。
【００１５】
次に、終了判定方法について説明する。制御部７−１は、追跡回数ＣＴの値を＋１する。また、ＳＡＤ最小点検出部７−７は、前記出力されたＳＡＤ４ｍｉｎを最小点記憶部７−６に記憶されているＳＡＤｍｉｎと比較して、ＳＡＤｍｉｎが大きい場合には、ステップＳ６−２に進み、小さいか等しい場合には、中心点が最小であることを示す中心点極小信号を出力するとともに、ステップＳ６−３に進む（ステップＳ６−１）。
ステップＳ６−２では、最小点記憶部７−６に記憶されているＳＡＤｍｉｎ、ＰＢｍｉｎをＳＡＤ４ｍｉｎ、ＰＢ４ｍｉｎに置き換えて、ステップＳ２に進み、次の追跡にうつる（ステップＳ６−２）
ステップＳ６−３では、終了判定部７−８は、追跡回数ＣＴの値が奇数の場合には、ステップＳ２に進み、次の追跡にうつり、偶数の場合には、終了信号を出力してステップＳ７に進み、終了処理に入る（ステップＳ６−３）。
【００１６】
制御部７−１は、終了信号を入力すると、終了処理として、最小点記憶部７−６、アドレス設定部７−５を制御して予測画像を出力するとともに、ＭＶを出力して、このＭＢの動き補償予測処理を終了する（ステップＳ７）。
【００１７】
次に、以上の構成、動作ステップを持つ動き補償予測部７によるＭＶ検出動作について２つの追跡例により具体的に説明する。なお、以下の図面上では、従来例同様、対象ブロック位置、および初期中心点位置を（０，０）とする。
まず、図４により追跡動作１について説明する。図４（Ａ）は、従来例の図１０（Ｂ）と同一のＳＡＤ分布図、図４（Ｂ）は、図１０（Ｃ）に相当する追跡動作を表している。
追跡回数＃１では、初期中心点で、ＳＡＤｍｉｎ＝（大きな数）、ＰＢｍｉｎ＝（０，０）であり、上下左右周辺点のＳＡＤが計算されると、右点（ＳＡＤ４ｍｉｎ＝２０）が４点最小点として検出される。ここでは追跡回数が奇数で終了判定されないため、追跡中心点は右に１画素移動する。そして、ＳＡＤｍｉｎ＝２０、ＰＢｍｉｎ＝（１，０）となる。
次に、追跡回数＃２では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１６）が４点最小点として検出される。ここでは追跡回数が偶数で終了判定されるが、ＳＡＤｍｉｎよりＳＡＤ４ｍｉｎが小さいので、追跡は続行される。そして、ＳＡＤｍｉｎ＝１６、ＰＢｍｉｎ＝（２，０）となり、追跡中心点は右に１画素移動する。
追跡回数＃３では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１７）が４点最小点として検出される。ここでは、ＳＡＤｍｉｎよりＳＡＤ４ｍｉｎが大きいので、本来であればＭＶの追跡は終了するはずであるが、追跡回数が奇数で終了判定されないため、追跡は続行される。そして、ＳＡＤｍｉｎ＝１６、ＰＢｍｉｎ＝（２，０）は、維持され、追跡中心点は右に１画素移動する。
追跡回数＃４では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１５）が４点最小点として検出される。ここでは追跡回数が偶数で終了判定されるが、ＳＡＤｍｉｎよりＳＡＤ４ｍｉｎが小さいので、追跡は続行される。そして、ＳＡＤｍｉｎ＝１５、ＰＢｍｉｎ＝（４，０）となり、追跡中心点は右に１画素移動する。
追跡回数＃５では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１４）が４点最小点として検出される。ここでは、追跡回数が奇数で終了判定されず、ＳＡＤｍｉｎよりＳＡＤ４ｍｉｎが小さいので、ＳＡＤｍｉｎ＝１４、ＰＢｍｉｎ＝（５，０）となり、追跡中心点は右に１画素移動する。
追跡回数＃６では、同様に周辺点のＳＡＤが計算され、左点（ＳＡＤ４ｍｉｎ＝１５）が４点最小点として検出される。そして追跡回数が偶数で終了判定され、ＳＡＤｍｉｎよりＳＡＤ４ｍｉｎが大きいので、追跡中心点が極小点となって追跡は停止する。このときのＰＢｍｉｎ＝（５，０）から、ＭＶ＝ＰＢｏ−ＰＢｍｉｎとして動きベクトルＭＶが検出される。
なお、＃６の追跡中心点が、例えばＳＡＤ＝１６のように、終了判定点で極小点とならない場合には、ＳＡＤｍｉｎ＝１５のままで、＃５に戻り、ＳＡＤ４ｍｉｎ＝ＳＡＤｍｉｎが検出された時点に、探索を停止してＭＶを求めることになる。
本追跡例で、ＳＡＤｍｉｎ＝１４の最小点に到達している。これは、＃３で、追跡中心点のＳＡＤが極小となるにもかかわらず、たまたま終了判定がないため、ＳＡＤ＝１７という障壁を１つ飛び越して、＃４へと追跡を続けることができたためである。
【００１８】
次に、図５により追跡動作２について説明する。追跡動作２は、図５（Ａ）に示すように、追跡に関係するＳＡＤの分布は追跡動作１と同じとして、初期中心点を左に１画素だけずらして、追跡回数ＣＴの奇数／偶数を逆転させたものである。
この場合、追跡回数＃１では、上下左右周辺点のＳＡＤが計算されると、右点（ＳＡＤ４ｍｉｎ＝２２）が４点最小点として検出される。ここでは追跡回数が奇数で終了判定されないため、追跡中心点は右に１画素移動する。そして、ＳＡＤｍｉｎ＝２２、ＰＢｍｉｎ＝（１，０）となる。
次に、追跡回数＃２では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝２０）が４点最小点として検出される。ここでは追跡回数が偶数で終了判定されるが、ＳＡＤｍｉｎよりＳＡＤ４ｍｉｎが小さいので、追跡は続行される。そして、ＳＡＤｍｉｎ＝２０、ＰＢｍｉｎ＝（２，０）となり、追跡中心点は右に１画素移動する。
追跡回数＃３では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１６）が４点最小点として検出される。ここでは追跡回数が奇数で終了判定されないため、追跡中心点は右に１画素移動する。そして、ＳＡＤｍｉｎ＝１６、ＰＢｍｉｎ＝（３，０）となる。
追跡回数＃４では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１７）が４点最小点として検出される。ここでは追跡回数が偶数で終了判定され、ＳＡＤｍｉｎよりＳＡＤ４ｍｉｎが大きいので、追跡は終了する。このときのＰＢｍｉｎ＝（３，０）から、ＭＶ＝ＰＢｏ−ＰＢｍｉｎとして動きベクトルＭＶが検出される。
本追跡例では、終了判定する位置を追跡動作１から左に１画素だけずらしたため、＃４で終了判定され、ＳＡＤｍｉｎ＝１６の局所解に落ち込んで、最小点には到達できていない。
【００１９】
以上のように、実施例１によれば、追跡回数ＣＴにより、１カウントおきにしか終了判定を行わないため、終了判定を行わない時、すなわち１／２の確率で、１画素だけであれば、追跡ルート上の単調減少から逸脱した障壁を乗り越えて、さらに先の最小値を追跡できる。なお、次のカウントの追跡時には、終了判定を行い、前記中心点は、周辺点として再度調べることになるので、極小値となることを見逃すことはない。
さらに、制御部７−１は、中心点極小信号を受けると、追跡カウントが偶数回目の時だけ終了処理を行い、奇数回目の時は無視するようにして、終了判定部７−８の機能を吸収すれば、従来例の構成のまま最小限の変更で、局所解に陥る確率を減少させることも可能となり、既に従来例の構成で運用している場合には実用上の効果は大きい。
【実施例２】
【００２０】
実施例２について、図６、図７、および図４を用いて説明する。図６は、動き補償予測部の構成を示した図である。図７は、動作フローチャートを示す。図４は、追跡動作の例を示した図である。
【００２１】
実施例２における動画像符号化装置の構成は、実施例１と同一なので、説明は省略する。
また、動き補償予測部７の構成は、終了判定に関与するＳＡＤ最小点検出部７−７の一部機能、および終了判定部７−９を除いて、実施例１と同一である。すなわち、実施例１の探索回数の奇数／偶数による終了判定部７−８を、同一点回帰による終了判定部７−９に置き換えて、ＳＡＤ最小点検出部７−７の中心点極小信号の出力機能を除去したものである。終了判定に関与しない部分は、従来例１と同一なので、説明は省略する。
そして、終了判定部７−９は、ＳＡＤ４最小ブロック検出部７−３出力のＰＢ４ｍｉｎを最小点記憶部７−６に記憶されたＰＢｍｉｎを比較して同一かどうかチェックして、同一である場合、すなわち同一点に戻った場合に限り終了信号を出力する。
【００２２】
次に、前記構成の動き補償予測部７によるＭＶ検出動作手順について、図７のフローチャートを用いて説明する。
最初のステップＳ１の初期設定（ただし、ＣＴは不使用。）、および次のステップＳ２〜Ｓ５の追跡動作については、実施例１と同一なので、説明を省略する。
続いて終了判定について説明する。ＳＡＤ最小点検出部７−７は、前記出力されたＳＡＤ４ｍｉｎを最小点記憶部７−６に記憶されているＳＡＤｍｉｎと比較して、ＳＡＤｍｉｎが大きい場合には、ステップＳ８−２に進み、小さいか等しい場合には、ステップＳ８−３に進む（ステップＳ８−１）。
ステップＳ８−２では、最小点記憶部７−６に記憶されているＳＡＤｍｉｎ、ＰＢｍｉｎをＳＡＤ４ｍｉｎ、ＰＢ４ｍｉｎに置き換えて、ステップＳ２に進み次の追跡にうつる（ステップＳ８−２）。
ステップＳ８−３では、終了判定部７−９は、ＰＢｍｉｎとＰＢ４ｍｉｎを比較して異なる場合には、ステップＳ２に進み次の追跡にうつり、同じ場合には、終了信号を出力してステップＳ７に進み終了処理に入る（ステップＳ８−３）。
ステップＳ７では、制御部７−１は、終了信号を入力して終了処理に入ると、実施例１同様、予測画像、およびＭＶを出力して、このＭＢの動き補償予測処理を終了する（ステップＳ７）。
【００２３】
次に、図４の追跡動作１を用いて、ＭＶ検出動作について具体的に説明する。図４（Ａ）は、ＳＡＤ分布図、図４（Ｂ）は、追跡動作を表している。
追跡回数＃１では、初期中心点で、ＳＡＤｍｉｎ＝（大きな数）、ＰＢｍｉｎ＝（０，０）であり、上下左右周辺点のＳＡＤが計算されると、右点（ＳＡＤ４ｍｉｎ＝２０）が４点最小点として検出されるが、ＰＢｍｉｎとＰＢ４ｍｉｎは異なるので、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝２０、ＰＢｍｉｎ＝（１，０）となる。
次に、追跡回数＃２では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１６）が４点最小点として検出されるが、ＰＢｍｉｎとＰＢ４ｍｉｎは異なるので、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１６、ＰＢｍｉｎ＝（２，０）となる。
追跡回数＃３では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１７）が４点最小点として検出されるが、ＰＢｍｉｎとＰＢ４ｍｉｎは異なるので、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１６、ＰＢｍｉｎ＝（２，０）は、維持される。
追跡回数＃４では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１５）が４点最小点として検出されるが、ＰＢｍｉｎとＰＢ４ｍｉｎは異なるので、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１５、ＰＢｍｉｎ＝（４，０）となる。
追跡回数＃５では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１４）が４点最小点として検出されるが、ＰＢｍｉｎとＰＢ４ｍｉｎは異なるので、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１４、ＰＢｍｉｎ＝（５，０）となる。
追跡回数＃６では、同様に周辺点のＳＡＤが計算され、左点（ＳＡＤ４ｍｉｎ＝１５）が４点最小点として検出されるが、ＰＢｍｉｎ（５，０）とＰＢ４ｍｉｎ（４，０）は異なるので、追跡中心点は左に１画素戻って追跡を続ける。ＳＡＤｍｉｎ＝１４、ＰＢｍｉｎ＝（５，０）を維持する。
追跡回数＃７では、＃５に戻って、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１４）が４点最小点として検出されるが、ＰＢｍｉｎとＰＢ４ｍｉｎが一致するので、追跡は停止される。このときのＰＢｍｉｎ＝（５，０）から、ＭＶ＝ＰＢｏ−ＰＢｍｉｎとして動きベクトルＭＶが検出される。
本追跡例で、ＳＡＤｍｉｎ＝１４の最小点に到達している。
【００２４】
以上のように、実施例２によれば、中心点極小で終了判定するのではないので、１画素だけであれば単調減少から逸脱した障壁を乗り越えてさらに先の極小値を追跡できる。このため、局所解に陥る確率を減少できる。
さらに、実施例２によれば、同一極小点に回帰するかどうかにより終了判定するため、極小点に到達したら直ちに終了処理する場合よりも、１追跡回数分余分に時間がかかるが、実施例１のように、追跡回数の偶数／奇数に左右されないで、障壁を乗り越えることが可能となり、さらに先の最小値を追跡できる。
【実施例３】
【００２５】
実施例３について図８、図９、および図４を用いて説明する。図８は、動き補償予測部の構成を示した図である。図９は、動作フローチャートを示す。図４は、追跡動作の例を示した図である。
【００２６】
実施例３における動画像符号化装置の構成は、実施例１と同一なので、説明は省略する。
また、動き補償予測部７の構成は、終了判定に関与する終了判定部７−１０を除いて、実施例２と同一である。すなわち、実施例２の同一点回帰による終了判定部７−９を、回数制限による終了判定部７−１０に置き換えたものである。終了判定に関与しない部分は、従来例２と同一なので、説明は省略する。
終了判定部７−１０は、追跡回数ＣＴをチェックして、追跡回数が設定した制限回数になった時に限り、終了信号を出力するものである。
【００２７】
次に、前記構成の動き補償予測部７によるＭＶ検出動作手順について、図９のフローチャートを用いて説明する。
ステップＳ１の初期設定では、対象ＭＢ位置、初期中心点、ＳＡＤ最小点（ＰＢｍｉｎ、ＳＡＤｍｉｎ）の設定は、実施例１の場合と同一である。また、終了判別部７−１０は、追跡回数チェック用ＣＴの値を所定の回数制限したい値にセットする（ステップＳ１）。
また、ステップＳ２〜Ｓ５の追跡動作は、実施例１の場合と同一なので、説明を省略する。
終了判定については、まず、ＳＡＤ最小点検出部７−７は、前記出力されたＳＡＤ４ｍｉｎを最小点記憶部７−６に記憶されているＳＡＤｍｉｎと比較して、ＳＡＤｍｉｎが大きい場合には、ステップＳ９−２に進み、小さいか等しい場合には、ステップＳ９−３に飛ぶ（ステップＳ９−１）。
ステップＳ９−２では、最小点記憶部７−６に記憶されているＳＡＤｍｉｎ、ＰＢｍｉｎをＳＡＤ４ｍｉｎ、ＰＢ４ｍｉｎに書き換えて最小点を更新して、ステップＳ９−３に進む（ステップＳ９−２）
ステップＳ９−３では、終了判定部７−１０は、追跡回数チェック用ＣＴの値を−１して（ステップＳ９−３）、チェック用ＣＴの値が０でない場合には、ステップＳ２に飛び次の追跡動作にうつり、チェック用ＣＴの値が０の場合には、終了信号を出力してステップＳ７に進み（ステップＳ９−４）、終了処理に入る。
ステップＳ７では、制御部７−１は、終了信号を入力して終了処理に入ると、実施例１同様、予測画像、およびＭＶを出力して、このＭＢの動き補償予測処理を終了する（ステップＳ７）。
【００２８】
次に、図４の追跡動作１を用いて、ＭＶ検出動作について具体的に説明する。図４（Ａ）は、ＳＡＤ分布図、図４（Ｂ）は、追跡動作を表している。
追跡回数＃１では、初期中心点で、ＳＡＤｍｉｎ＝（大きな数）、ＰＢｍｉｎ＝（０，０）であり、上下左右周辺点のＳＡＤが計算されると、右点（ＳＡＤ４ｍｉｎ＝２０）が４点最小点として検出され、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝２０、ＰＢｍｉｎ＝（１，０）となる。
次に、追跡回数＃２では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１６）が４点最小点として検出され、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１６、ＰＢｍｉｎ＝（２，０）となる。
追跡回数＃３では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１７）が４点最小点として検出され、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１６、ＰＢｍｉｎ＝（２，０）は、維持される。
追跡回数＃４では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１５）が４点最小点として検出され、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１５、ＰＢｍｉｎ＝（４，０）となる。
追跡回数＃５では、同様に周辺点のＳＡＤが計算され、右点（ＳＡＤ４ｍｉｎ＝１４）が４点最小点として検出され、追跡中心点は右に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１４、ＰＢｍｉｎ＝（５，０）となる。
追跡回数＃６では、同様に周辺点のＳＡＤが計算され、左点（ＳＡＤ４ｍｉｎ＝１５）が４点最小点として検出され、追跡中心点は左に１画素移動して追跡を続ける。ＳＡＤｍｉｎ＝１４、ＰＢｍｉｎ＝（５，０）である。
追跡回数＃７は、左に戻ったため、＃５と全く同じ動作となり、右に１画素移動する。
追跡回数＃８は、＃５と全く同じ動作となる。
以下、制限回数となるまで、＃５と＃６の往復運動を繰り返す。そして、制限回数になると、追跡は停止される。このときのＰＢｍｉｎ＝（５，０）から、ＭＶ＝ＰＢｏ−ＰＢｍｉｎとして動きベクトルＭＶが検出される。
【００２９】
以上のように、実施例３によれば、中心点極小で終了判定するのではないので、１画素だけであれば単調減少から逸脱した障壁を乗り越えてさらに先の極小値を追跡できる。このため、局所解に陥る確率を減少できる。
また、追跡回数により終了判定するため、制限回数となるまで上下左右周辺点のＳＡＤ最小方向への移動を繰り返し、見つかったＳＡＤが最小となる位置ＰＢｍｉｎから、動きベクトルを検出する。このため、実施例１、２と比べて、本来検出できているのに時間を余らせて往復運動をして待つような場合、また逆に時間が足りなくて行き着くはずのＭＶを求められない場合もあるが、検出にかかる時間はいつも一定であり、同期した処理が必要な圧縮符号化装置に使用すると好適である。
【００３０】
なお、逆に実施例１、実施例２は、探索範囲のＳＡＤ分布によっては、検出に想定以上の時間がかかる場合もあるので、実施例３に述べた回数制限を併用すると、最大検出時間を制限することができる。
また、実施例３は回数制限により終了判定をしたが、追跡回数ＣＴを時間ＣＴに置き換えるだけで、時間制限による終了判定が可能となり、全く同様の効果を得ることができる。
【図面の簡単な説明】
【００３１】
【図１】本発明の実施例における動画像符号化装置の構成を示した図である。
【図２】本発明実施例の動き補償予測部の構成を示した図である。（実施例１）
【図３】本発明実施例の動作フローチャートを示す。
【図４】本発明実施例の追跡動作の説明図で、（Ａ）は、探索範囲におけるＳＡＤの分布図、（Ｂ）は、追跡動作を示す。（例１）
【図５】本発明実施例の追跡動作の説明図で、（Ａ）は、探索範囲におけるＳＡＤの分布図、（Ｂ）は、追跡動作を示す。（例２）
【図６】本発明実施例の動き補償予測部の構成を示した図である。（実施例２）
【図７】本発明実施例の動作フローチャートを示す。
【図８】本発明実施例の動き補償予測部の構成を示した図である。（実施例３）
【図９】本発明実施例の動作フローチャートを示す。
【図１０】従来例の説明図で、（Ａ）は、探索パターン、（Ｂ）は、探索範囲におけるＳＡＤの分布図、（Ｃ）は、追跡動作を示す。
【符号の説明】
【００３２】
１  対象画像メモリ、２  減算器、３  予測誤差符号化部、４  予測誤差復号化部、５  加算器、６  参照画像メモリ、７  動き補償予測部、７−１  制御部、７−２  ＳＡＤ計算部、７−３  ＳＡＤ４点最小ブロック検出部、７−４  追跡中心設定部、７−５  アドレス設定部、７−６  最小点記憶部、７−７  ＳＡＤ最小点検出部、７−８  終了判定部（偶数回目中心点極小）、７−９  終了判定部（同一点回帰）、７−１０  終了判定部（回数制限）、８  可変長符号化部
【図１】
2007235333.tif 000003
【図２】
2007235333.tif 000004
【図３】
2007235333.tif 000005
【図４】
2007235333.tif 000006
【図５】
2007235333.tif 000007
【図６】
2007235333.tif 000008
【図７】
2007235333.tif 000009
【図８】
2007235333.tif 000010
【図９】
2007235333.tif 000011
【図１０】
2007235333.tif 000012