(57)【要約】【課題】ＭＰＥＧ−４  ＡＶＣ／Ｈ．２６４で使われる複数ブロックサイズの動きベクトル探索において、必要となる処理量を大幅に削減する動きベクトル検出装置を提供する。【解決手段】対象ブロックに隣接する同一サイズの動きベクトルと、対象ブロックに隣接して右または下方向に位置する小ブロックサイズの動きベクトルの両方を使って動きベクトルを予測する。予測した動きベクトルのＳＡＤまたは動き補償残差コストが十分に小さいか、予測した動きベクトルが周囲±１／４画素の範囲で極小であれば、予測動きベクトルを当該対象ブロックの動きベクトルとして出力する。【選択図】      図４
2008109632.tif 000002
【特許請求の範囲】
【請求項１】
動画像におけるフレームを複数のブロックに分割し、それぞれの動きベクトルを求める動きベクトル検出装置において、
前記動きベクトルを求める対象となる対象ブロックの各々に隣接するブロックの動きベクトルの中から、
（１）前記対象ブロックと同じサイズのブロックである第１ブロックの第１動きベクトル、及び、
（２）前記対象ブロックより小さいブロックである第２ブロックの第２動きベクトル、
を含む複数の動きベクトル候補を抽出する候補抽出部と、
前記複数の動きベクトル候補の中から、前記対象ブロックの動きベクトルの予測値である第１予測動きベクトルを選択するベクトル選択部と、
前記第１予測動きベクトルが指し示す点から所定の範囲内にある複数の近傍探索点に対応する複数の近傍動きベクトルの残差コストを算出する候補残差コスト算出部と、
前記複数の近傍動きベクトルの中から最小の残差コストを有する第２予測動きベクトルを選択する最小の残差コスト選択部と、
前記最小の残差コストを有する第２予測動きベクトルと前記第１予測動きベクトルとが同じであるか否かを比較する第１ベクトル比較部と、
前記最小の残差コストを有する第２予測動きベクトルが前記第１予測動きベクトルと同じときは、前記第１予測動きベクトルを前記対象ブロックの動きベクトルとして検出する検出部と、
前記最小の残差コストを有する第２予測動きベクトルが前記第１予測動きベクトルとが異なるときは、前記第１予測動きベクトルの指し示す点を中心とした任意の探索範囲の動きベクトルを、ブロックマッチングによって求めることにより、前記動きベクトルを探索する第１探索部と、
を有する動きベクトル検出装置。
【請求項２】
前記候補抽出部は、
前記対象ブロックより小さいブロックのうち、
（１）ブロックサイズが最大である、
（２）重心が前記対象ブロックに最も近い、及び、
（３）前記対象ブロックの左側に隣接するブロックのうち最も下にある、または、前記対象ブロックの上側に隣接するブロックのうち最も右にある、
という条件を満たす第２ブロックを抽出するブロック抽出部を有する、
請求項１記載の動きベクトル検出装置。
【請求項３】
前記ベクトル選択部は、
前記動きベクトル候補の各々を用いた前記対象ブロックの動き補償予測による予測残差を求め、
これら予測残差に基づく前記各動きベクトル候補の残差コストを求め、
前記動きベクトル候補の中から前記残差コストが最小となる動きベクトル候補を前記第１予測動きベクトルとして決定する、
請求項１記載の動きベクトル検出装置。
【請求項４】
前記複数の動きベクトル候補に対応する周囲の隣接ブロックの画素当たりに換算された残差コストの最小値から算出される第１閾値を求める第１閾値算出部と、
前記第１閾値と前記第１予測動きベクトルの残差コストとを比較する第１コスト比較部と、
前記第１閾値よりも前記第１予測動きベクトルのコストが小さい場合には、前記第２予測動きベクトルの残差コストの算出を行わずに、前記第１予測動きベクトルを前記対象ブロックの動きベクトルに決定する動きベクトル決定部と、
をさらに有する請求項１記載の動きベクトル検出装置。
【請求項５】
前記第１閾値よりも前記第１予測動きベクトルの残差コストが大きい場合には、前記周囲の隣接ブロックの画素当たりに換算された残差コストの最小値から算出される第２閾値を求める第２閾値算出部と、
前記第２閾値と前記第１予測動きベクトルの残差コストとを比較する第２コスト比較部と、
前記第２閾値よりも前記第１予測動きベクトルの残差コストが大きい場合には、前記複数の近傍動きベクトルの残差コストの算出を行わずに、前記第１探索部と同じ探索処理を行う第１判断処理部と、
をさらに有する請求項４記載の動きベクトル検出装置。
【請求項６】
前記複数の動きベクトル候補に対応する周囲の隣接ブロックの画素当たりに換算された残差コストの最大値から算出される第３閾値を求める第３閾値算出部と、
前記第３閾値と前記第１予測動きベクトルの残差コストとを比較する第３コスト比較部と、
前記第３閾値よりも前記第１予測動きベクトルの残差コストが大きい場合には、前記複数の近傍動きベクトルの残差コストの算出を行わずに、前記第１探索部と同じ探索処理を行う第２判断処理部と、
を有する請求項１記載の動きベクトル検出装置。
【請求項７】
前記第１予測動きベクトルの周囲を３画素以上の精度で残差コストに基づいた粗い動き探索を行う第３探索部と、
前記探索された動きベクトル候補を第１予測動きベクトルと決定する第２決定部と、
前記精度で粗い動き探索を行った後、前記第１予測動きベクトルと前記動き探索前のベクトルが同一か否かを比較する第２ベクトル比較部と、
前記第１予測動きベクトルと前記動き探索前のベクトルが異なる場合には、前記第１探索部と同じ探索処理を行う第３判断処理部と、
を有する請求項１記載の動きベクトル検出装置。
【請求項８】
前記複数の近傍動きベクトルの残差コストは、
（１）当該動きベクトルが指し示す点に基づく領域と前記対象ブロックの対応画素間の差分絶対値和と、（２）当該動きベクトルを符号化した場合に必要とする符号量に所定の係数λを乗じた値と、を加算した値であり、
前記各動きベクトル候補の残差コストと前記第３探索部で用いる残差コストは、前記動きベクトルが指し示す点に基づく領域と前記対象ブロックの対応画素間の差分絶対値和によって計算される、
請求項７記載の動きベクトル検出装置。
【請求項９】
動画像におけるフレームを複数のブロックに分割し、それぞれの動きベクトルを求める動きベクトル検出方法において、
前記動きベクトルを求める対象となる対象ブロックの各々に隣接するブロックの動きベクトルの中から、
（１）前記対象ブロックと同じサイズのブロックである第１ブロックの第１動きベクトル、及び、
（２）前記対象ブロックより小さいブロックである第２ブロックの第２動きベクトル、
を含む複数の動きベクトル候補を抽出する候補抽出ステップと、
前記複数の動きベクトル候補の中から、前記対象ブロックの動きベクトルの予測値である第１予測動きベクトルを選択するベクトル選択ステップと、
前記第１予測動きベクトルが指し示す点から所定の範囲内にある複数の近傍探索点に対応する複数の近傍動きベクトルの残差コストを算出する候補残差コスト算出ステップと、
前記複数の近傍動きベクトルの中から最小の残差コストを有する第２予測動きベクトルを選択する最小の残差コスト選択ステップと、
前記最小の残差コストを有する第２予測動きベクトルと前記第１予測動きベクトルとが同じであるか否かを比較する第１ベクトル比較ステップと、
前記最小の残差コストを有する第２予測動きベクトルが前記第１予測動きベクトルと同じときは、前記第１予測動きベクトルを前記対象ブロックの動きベクトルとして検出する検出ステップと、
前記最小の残差コストを有する第２予測動きベクトルが前記第１予測動きベクトルとが異なるときは、前記第１予測動きベクトルの指し示す点を中心とした任意の探索範囲の動きベクトルを、ブロックマッチングによって求めることにより、前記動きベクトルを探索する第１探索ステップと、
を有する動きベクトル検出方法。
【請求項１０】
前記候補抽出ステップは、
前記対象ブロックより小さいブロックのうち、
（１）ブロックサイズが最大である、
（２）重心が前記対象ブロックに最も近い、及び、
（３）前記対象ブロックの左側に隣接するブロックのうち最も下にある、または、前記対象ブロックの上側に隣接するブロックのうち最も右にある、
という条件を満たす第２ブロックを抽出するブロック抽出ステップを有する、
請求項９記載の動きベクトル検出方法。
【請求項１１】
前記ベクトル選択ステップは、
前記動きベクトル候補の各々を用いた前記対象ブロックの動き補償予測による予測残差を求め、
これら予測残差に基づく前記各動きベクトル候補の残差コストを求め、
前記動きベクトル候補の中から前記残差コストが最小となる動きベクトル候補を前記第１予測動きベクトルとして決定する、
請求項９記載の動きベクトル検出方法。
【請求項１２】
前記複数の動きベクトル候補に対応する周囲の隣接ブロックの画素当たりに換算された残差コストの最小値から算出される第１閾値を求める第１閾値算出ステップと、
前記第１閾値と前記第１予測動きベクトルの残差コストとを比較する第１コスト比較ステップと、
前記第１閾値よりも前記第１予測動きベクトルのコストが小さい場合には、前記第２予測動きベクトルの残差コストの算出を行わずに、前記第１予測動きベクトルを前記対象ブロックの動きベクトルに決定する動きベクトル決定ステップと、
をさらに有する請求項９記載の動きベクトル検出方法。
【請求項１３】
前記第１閾値よりも前記第１予測動きベクトルの残差コストが大きい場合には、前記周囲の隣接ブロックの画素当たりに換算された残差コストの最小値から算出される第２閾値を求める第２閾値算出ステップと、
前記第２閾値と前記第１予測動きベクトルの残差コストとを比較する第２コスト比較ステップと、
前記第２閾値よりも前記第１予測動きベクトルの残差コストが大きい場合には、前記複数の近傍動きベクトルの残差コストの算出を行わずに、前記第１探索ステップと同じ探索処理を行う第１判断処理ステップと、
をさらに有する請求項１２記載の動きベクトル検出方法。
【請求項１４】
前記複数の動きベクトル候補に対応する周囲の隣接ブロックの画素当たりに換算された残差コストの最大値から算出される第３閾値を求める第３閾値算出ステップと、
前記第３閾値と前記第１予測動きベクトルの残差コストとを比較する第３コスト比較ステップと、
前記第３閾値よりも前記第１予測動きベクトルの残差コストが大きい場合には、前記複数の近傍動きベクトルの残差コストの算出を行わずに、前記第１探索ステップと同じ探索処理を行う第２判断処理ステップと、
を有する請求項９記載の動きベクトル検出方法。
【請求項１５】
前記第１予測動きベクトルの周囲を３画素以上の精度で残差コストに基づいた粗い動き探索を行う第３探索ステップと、
前記探索された動きベクトル候補を第１予測動きベクトルと決定する第２決定ステップと、
前記精度で粗い動き探索を行った後、前記第１予測動きベクトルと前記動き探索前のベクトルが同一か否かを比較する第２ベクトル比較ステップと、
前記第１予測動きベクトルと前記動き探索前のベクトルが異なる場合には、前記第１探索ステップと同じ探索処理を行う第３判断処理ステップと、
を有する請求項９記載の動きベクトル検出方法。
【請求項１６】
前記複数の近傍動きベクトルの残差コストは、
（１）当該動きベクトルが指し示す点に基づく領域と前記対象ブロックの対応画素間の差分絶対値和と、（２）当該動きベクトルを符号化した場合に必要とする符号量に所定の係数λを乗じた値と、を加算した値であり、
前記各動きベクトル候補の残差コストと前記第３探索ステップで用いる残差コストは、前記動きベクトルが指し示す点に基づく領域と前記対象ブロックの対応画素間の差分絶対値和によって計算される、
請求項１５記載の動きベクトル検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，動画像符号化を行う際に必要な動きベクトル検出装置及びその方法に関するものである。
【背景技術】
【０００２】
動画像符号化においては、フレーム間の冗長性を利用したフレーム間動き補償が用いられている。動き補償に必要な動きベクトル検出処理は、必要演算量が大きいことが知られており、その高速化方法は古くから様々な方法が提案されている。また、高速なアルゴリズムを採用した際の動きベクトル検出精度を向上させる方法も提案されている。
【０００３】
例えば、特許文献１に示される方法では、ＭＰＥＧ−４  ＡＶＣ／Ｈ．２６４に代表される複数のブロック分割サイズを選択可能な符号化方式における動きベクトル検出において、ベクトル検出対象ブロックが内包するより小さなブロックブロックサイズの動きベクトルを参照し、探索中心点を定める方法が提示されている。
【０００４】
この方法では、例えば、図９に示すように、より小さなブロックサイズ（例えば、４×４画素のブロック）の動きベクトルを予め求めておき、これから動き検出を行う対象ブロック（例えば８×８画素のブロック）の動きベクトル探索のときには、当該ブロックが内包する小ブロックに対応するＭＶＡ，ＭＶＢ，ＭＶＣ，ＭＶＤの４種類の動きベクトルの中央値を探索中心点として動きベクトル探索を行う。
【０００５】
また、特許文献２では、対象となるブロックの周囲に位置するブロックの動きベクトルに対応する予測残差コスト（当該周囲ブロックとその動きベクトルが指し示す参照ブロックとの画素間の差分に基づく評価値であり、各差分の絶対値を累積加算したＳＡＤ＝差分絶対値和がよく用いられる）から対象ブロックの予測残差コストの閾値を定め、動きベクトル探索中の予測残差コストが当該閾値を下回った時点で処理を打ち切る方法が提示されている。
【０００６】
例えば、図１０に示すように、動きベクトル検出対象ブロックの周囲にあるブロックＡ，Ｂ及びＣの動きベクトルＭＶＡ，ＭＶＢ，ＭＶＣと、その動きベクトルの予測残差コストＳＡＤＡ，ＳＡＤＢ，ＳＡＤＣを用い、最初に探索を打ち切る閾値を例えば最小値ＳＡＤＴＨ＝ｍｉｎ（ＳＡＤＡ，ＳＡＤＢ，ＳＡＤＣ）を用いて設定する。次に、周囲の動きベクトルＭＶＡ，ＭＶＢ，ＭＶＣの最頻値（２．７５，０）を探索中心として、非特許文献１に示されるようなダイヤモンドサーチを用いて動き検出を行う。ダイヤモンドサーチは、探索中心点から勾配法的に各探索点の予測残差コストを求め、それが±２画素の範囲で収束するまで探索を続ける方法である。
【０００７】
そして、特許文献２の方法では、収束前でも当該予測残差コストが前記閾値を下回ったところでその先の探索を打ち切るため、従来よりも探索に要する演算量を削減することができる。
【特許文献１】特開２００５−３２３２９９号公報
【特許文献２】特開２００１−１４５１０９号公報
【非特許文献１】S. Zhu and K. K. Ma, ''A new diamond search algorithm for fast block matching motion estimation,'' IEEE Trans. on Image Processing, vol. 9, no. 2, pp. 287-290, Feb. 2000
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に示される方法は、動きベクトルの誤検出を誘発する危険性を有するという問題点がある。
【０００９】
また、特許文献２に示される方法は、必ずしも常に演算量を効果的に削減することができないという問題点がある。
【００１０】
ところで、先述のＳＡＤという指標は、ブロック内の画素数が少なければ少ないほどノイズなどの外乱の影響を受けやすくなる。画素間のノイズが無相関の場合、ＳＡＤを求める際に累積加算した分だけＳＡＤの値は大きくなるが、そこに含まれるノイズ成分の大きさは互いに打ち消しあう作用が働くために増大しない。このため、画素を数多く加算した方が、言い換えれば面積の大きなブロックのＳＡＤの方が相対的にノイズの影響を受けにくくなる。したがって、小さなブロックサイズの動きベクトルの信頼性は必ずしも高くない。また、対象ブロックに内包される小ブロックの動きベクトルは、その対象ブロックの部分集合である小ブロックだけについてＳＡＤを求めれば必ず周囲の探索点と比較して極小となる。例えば、図９に示した例では、ＭＶＢとＭＶＤに等しい動きベクトルが予測ベクトルとして採用される。
【００１１】
このとき、ブロックを構成するＡ，Ｂ，Ｃ，Ｄのそれぞれの領域のうち小ブロックＢ及び小ブロックＤの領域におけるＳＡＤは、その周囲に存在する探索点の中で極小となる。したがって、本来あるべき動きベクトルが異なる位置にある場合でも、領域Ｂ，Ｄの領域の極小性を領域Ａ及びＣのＳＡＤで打ち消すことができなければ、ダイヤモンドサーチにおける探索を継続させることはできない。すなわち、非特許文献１にあるような、周囲の探索点との極小性に基づく動きベクトル検出とは、本方法とは相性が悪く、ベクトルの誤検出を生む原因となる。このようにして誤った動きベクトルが求められてしまうと、特許文献２に示した方法もさらに適用させた場合に、設定する閾値自体が本来よりも大きくなってしまうことも考えられ、相乗的に動きベクトルの探索精度を低下させることも考えられる。
【００１２】
また、特許文献２に示される打ち切り方法は、周囲のブロックに動き補償を施した際の残差コストが、対象ブロックの動き補償後の残差コストと相関が高い、すなわち周囲のブロックの動きが対象ブロックの動きに類似していることを前提としており、動きやテクスチャが複雑なシーンではこの前提が必ずしも成り立たないため、符号化効率を低下させる原因となる。
【００１３】
図１１は、映像情報メディア学会発行の標準テレビジョン方式・システム評価用標準動画像（http://www.nes.or.jp/gijutsu/kyoiku/ichiran.html（２００６年９月現在）あるいは、http://www.nes.or.jp/standardimage/imagelist.html（２００７年７月現在）を参照）に含まれる３種類の画像（Ｎｏ．１０の「路面電車」、Ｎｏ．３５の「競馬」、Ｎｏ．３７の「走る自動車」）の最初の６フレームに対して、非特許文献１に記載のダイヤモンドサーチをベースとした動きベクトル検出を行ったときに、周囲のブロックから求められる予測動きベクトルを対象ブロックに適用したときのＳＡＤと前述の閾値との差分の頻度を求めたものである。
【００１４】
画像「競馬」と「路面電車」については、設定した閾値で約半数のブロックの探索打ち切りが可能である。しかしながら、画像「走る自動車」の場合には、打ち切り可能数が３０％前後と大幅に減少する。「走る自動車」に関しては、ほかの画像に比べて明らかに分布が広範囲にわたっており、これはすなわち、周囲ブロックから求める閾値と、実際に打ち切りを行わずに動きベクトルを求めた際のＳＡＤとの相関が低いことを意味している。したがって、このような画像に対して、より打ち切りの頻度を上げるべく閾値を大きく設定してしまえば、符号化効率に深刻な影響を与えてしまうことは明確である。すなわち、「走る自動車」のような画像に対して、より効果的な探索の打ち切り処理を導入するためには、前述の閾値だけでなく他の評価指標が必要となる。
【００１５】
そこで本発明は、上記問題点に鑑みてなされたものであり、動きベクトルを求める際の演算量を削減しつつその精度を向上させることを目的とする動きベクトル検出装置及びその方法を提供する。
【課題を解決するための手段】
【００１６】
本発明は、動画像におけるフレームを複数のブロックに分割し、それぞれの動きベクトルを求める動きベクトル検出装置において、前記動きベクトルを求める対象となる対象ブロックの各々に隣接するブロックの動きベクトルの中から、（１）前記対象ブロックと同じサイズのブロックである第１ブロックの第１動きベクトル、及び、（２）前記対象ブロックより小さいブロックである第２ブロックの第２動きベクトル、を含む複数の動きベクトル候補を抽出する候補抽出部と、前記複数の動きベクトル候補の中から、前記対象ブロックの動きベクトルの予測値である第１予測動きベクトルを選択するベクトル選択部と、前記第１予測動きベクトルが指し示す点から所定の範囲内にある複数の近傍探索点に対応する複数の近傍動きベクトルの残差コストを算出する候補残差コスト算出部と、前記複数の近傍動きベクトルの中から最小の残差コストを有する第２予測動きベクトルを選択する最小の残差コスト選択部と、前記最小の残差コストを有する第２予測動きベクトルと前記第１予測動きベクトルとが同じであるか否かを比較する第１ベクトル比較部と、前記最小の残差コストを有する第２予測動きベクトルが前記第１予測動きベクトルと同じときは、前記第１予測動きベクトルを前記対象ブロックの動きベクトルとして検出する検出部と、前記最小の残差コストを有する第２予測動きベクトルが前記第１予測動きベクトルとが異なるときは、前記第１予測動きベクトルの指し示す点を中心とした任意の探索範囲の動きベクトルを、ブロックマッチングによって求めることにより、前記動きベクトルを探索する第１探索部と、を有する動きベクトル検出装置である。
【発明の効果】
【００１７】
本発明によれば、少ない演算量でより本来の動きを追いやすい動きベクトル検出が、可能となる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の一実施形態の動きベクトル検出装置について図面に基づいて説明する。
【００１９】
（１）動きベクトル検出装置の構成
図１は、本実施形態の動きベクトル検出装置の構成を示すブロック図である。
【００２０】
動きベクトル検出装置は、ノイマン型のコンピュータに画像の入出力回路を付加したものであり、ＣＰＵ１、ＲＡM３、ＲＯM４、画像入力回路５、符号化画像出力回路６がバス２で接続される構成となっている。ＲＯM４の内部には、動きベクトル検出のためのプログラムが格納されており、ＣＰＵ１がＲＯM４からプログラムを逐次読み出して動きベクトル検出を行う。
【００２１】
画像は、画像入力回路５を通して入力され、一時的にＲＡM３に保存される。ＣＰＵ１は、保存された画像情報を元にプログラムにしたがって動きベクトル検出を行うことになる。動きベクトル検出が終了すると、ＲＯM４の別の領域に記憶されている符号化プログラムがＣＰＵ１に逐次読み込まれ、動き補償、２次元周波数変換、量子化、エントロピー符号化などの処理を経て符号化処理が行われ、その結果生成される符号化画像情報が、符号化画像出力回路６を介して外部へ出力される。
【００２２】
画像入力回路５は、例えば、カメラから出力される画像信号をデジタル／アナログ変換して得られるデジタル信号入力回路や、予め画像情報を保存しておいたハードディスクドライブや光ディスクなどで構成される。
【００２３】
同様に、符号化画像出力回路６は、ネットワークインタフェースでも良いし、画像入力回路５と同一のハードディスクドライブや光ディスクなどで構成しても良い。ＣＰＵ１は、動きベクトル検出において繰り返し演算されるＳＡＤ（差分絶対値和）を高速に実行できるＳＩMＤ命令を備えたものが好ましい。しかし、対象画像の解像度が低い場合やフレームレートが低い場合には、安価に供給されている組み込み向けＣＰＵで構成することもできる。
【００２４】
（２）動きベクトルを求めるブロック
ＭＰＥＧ−４  ＡＶＣ／Ｈ．２６４では、動画像を構成する１枚のフレームをマクロブロックと呼ばれる１６×１６画素のブロックに分割し、それを単位として符号化が行われる。さらに、マクロブロックは４×４、４×８、８×４、８×８、８×１６、１６×８、１６×１６画素の小ブロックに分割することができ、これら様々なブロックサイズを組み合わせた分割パターンを混在させてマクロブロックを構成するような制御が行われる。
【００２５】
動きベクトルは、この小ブロック毎に独立して割り当てることになるため、最も単純には、これらの分割パターンに含まれる小ブロックそれぞれに対して動きベクトル検出を行い、その中から最良の分割パターンを選ぶことになる。
【００２６】
本実施形態では、単純化のため、これらのうち図２に示すような４個の８×８画素ブロック、２個の８×１６画素ブロック、２個の１６×８画素ブロック、さらに１個の１６×１６画素ブロックの動きベクトルをそれぞれ求めるものとする。
【００２７】
（３）動きベクトル検出の処理
動きベクトル検出の流れを示すフローチャートを図３に示す。
【００２８】
Ｓ２０１で８×８画素ブロックの動きベクトルを求める。
【００２９】
Ｓ２０２で８×１６画素ブロックの動きベクトルを求める。
【００３０】
Ｓ２０３で１６×８画素ブロックの動きベクトルを求める。
【００３１】
Ｓ２０４で１６×１６画素ブロックの動きベクトルを求める。
【００３２】
この中で、ステップ２０１、Ｓ２０２、Ｓ２０３で複数の小ブロックの動きベクトルを求めるときには、図２のそれぞれ（ａ），（ｂ），（ｃ）で示した番号の順序で動きベクトルを求めるものとする。すなわち、１つのマクロブロック内での小ブロックの動き検出は左上から右下へのラスタスキャンで行われる。
【００３３】
（４）各画素ブロックの動きベクトルを求める処理
図４は、各画素ブロックの動きベクトルを求める際の処理の流れを示すフローチャートである。図４は図３に示した各ステップの１個のブロックに対して動きベクトル検出を行う際の処理手順を示したものである。
【００３４】
図４のフローチャートに従った処理を説明するため、図２（ｃ）に示される１６×８画素上側のブロックに対して動きベクトル検出を行う場合について述べる。
【００３５】
（４−１）ステップ１０１
まず、ステップ１０１では、対象ブロックに隣接する同一ブロックサイズのブロックの動きベクトル（ＭＶ）と残差コスト（ＣＭＥ）をそれぞれ予測ＭＶ候補、閾値候補として取得する。
【００３６】
その例を図５に示す。但し、、残差コストＣＭＥとは参照ブロックと対象ブロックとの画素値差分絶対値和（ＳＡＤ）に、予測ＭＶ候補を符号化したときの符号量ＲＭＶに所定の係数λを乗じたものを加えたものとし、次式で定義されるものとする。
【数１】
2008109632.tif 000003
【００３７】
ここでＲ（ｘ，ｙ）はＭＶが指し示す参照ブロック上の座標（ｘ，ｙ）上の画素値、Ｃ（ｘ，ｙ）は対象ブロック上の座標（ｘ，ｙ）上の画素値を示す。
【００３８】
対象ブロック３０１に隣接する同一ブロックサイズのブロックの中で、既に探索済みの中から３０２，３０３，３０４の各ブロックを抽出する。その結果、予測ＭＶ候補ＭＶｐｒｅｄ＿ｃａｎｄは
ＭＶｐｒｅｄ＿ｃａｎｄ
＝｛（２．５，０．５），（２．７５，０．５），（３．２５，１．０）｝
閾値候補ＣＭＥｔｈ＿ｃａｎｄは
ＣＭＥｔｈ＿ｃａｎｄ＝｛１２３，１２２，１２０｝
となる。
【００３９】
（４−２）ステップ１０２
ステップ１０２では、さらに対象ブロックよりも小さなブロックサイズの隣接ブロックから予測ＭＶ候補、閾値候補を取得する。対象ブロックに接している小ブロックは、図６に示す３５１，３５２，３５３の３種類であるが、ここではこの中でさらに次のいずれかの条件を満たすものだけを抽出する。
【００４０】
対象ブロックの上側に接する小ブロックのうち最も右にあるもの、対象ブロックの左側に接する小ブロックのうち最も下にあるもの。
【００４１】
図６の例で言えば、小ブロック３５１と３５３が選択される。その結果、予測ＭＶ候補ＭＶｐｒｅｄ＿ｃａｎｄは以下のリストとなる。但し、重複するものは一つにまとめる。
【００４２】
ＭＶｐｒｅｄ＿ｃａｎｄ
＝｛（２．５，０．５），（２．７５，０．５），（２．７５，１．０），（３．２５，１．０）｝
また、閾値候補ＣＭＥｔｈ＿ｃａｎｄにも小ブロック３５１と３５３の情報を加えるが、これら２つの小ブロックは、対象ブロックに比べ面積が１／２であるので、動きベクトルを対象ブロックに適用した場合を考え、ＣＭＥのうちＳＡＤに相当する項（式（１）における第１項）を２倍にしたものをリストに加える。例えば、小ブロック３５３の場合、ＳＡＤが５７であるので、リストに加える値は次式で計算される。
【００４３】
ＳＡＤ×２＋λ×ＲＭＶ＝５７×２＋（６１−５７）＝１１８
ここでも重複するものは一つにまとめる。
【００４４】
ＣＭＥｔｈ＿ｃａｎｄ＝｛１２３，１２２，１２０，１１８｝
（４−３）ステップ１０３
ステップ１０３では、求めた閾値リストＣＭＥｔｈ＿ｃａｎｄから次式に従って閾値ＣＭＥｔｈを算出する。
【００４５】
ＣＭＥｔｈ＝ｍｉｎ（ＣＭＥｔｈ＿ｃａｎｄ）＝１１８    ・・・（２）
（４−４）ステップ１０４
ステップ１０４では、これまでのステップで求めた予測ＭＶ候補を対象ブロックに適用して、その残差の大きさであるＳＡＤに基づいて予測ＭＶを選択する。
【００４６】
図７に例を挙げる。この例では、ＭＶ＝（３．２５，１．０）のときがＳＡＤが最も小さく（１１８）、その意味でＭＶ＝（３．２５，１．０）が真の動きベクトルに最も近いと考えられる。そこで、予測ＭＶとしてＭＶｐｒｅｄ＝（３．２５，１．０）を採用する。
【００４７】
なお、ここで式（１）に定義された残差コストではなく、ＳＡＤを用いて候補を選択することで、周囲の動きベクトルとの類似性は加味せず、純粋に残差の大きさだけを評価しているが、これにより、本来の動きにより近い予測ＭＶを選択することができる。また、このときのＣＭＥ値（１２６）をＣＭＥｐｒｅｄとして保持する。すなわち、ＭＶｐｒｅｄとは周囲に存在する大小両方のブロックから予測される動きベクトルであり、ＣＭＥｐｒｅｄは、その動きベクトルを当該動きベクトル検出対象のブロックに適用したときの残差コストである。
【００４８】
もし、ＣＭＥｐｒｅｄがＣＭＥｔｈよりも小さいかそれほど変わらない場合、ＭＶｐｒｅｄは最適な動きベクトルに十分近づいていると考えられる。そこで、先述の特許文献２と同様、この場合には探索を打ち切っても動き補償残差は十分に小さいので、処理を打ち切ってＭＶｐｒｅｄを動きベクトルとして出力する。
【００４９】
（４−５）ステップ１０７
すなわち、ステップ１０７では次式が成り立つかどうかを判定し、成り立つ場合にはＭＶｐｒｅｄを対象ブロックの動きベクトルとして出力する。
【００５０】
ＣＭＥｐｒｅｄ−ＣＭＥｔｈ＜ｄ１
但し、ｄ１は十分に小さな正の定数とする。
【００５１】
（４−６）ステップ１０５
次に、ステップ１０５では、求めたＭＶｐｒｅｄの周囲を±４画素の精度で粗く探索を行う。
【００５２】
前述したように、複雑な動きを持った画像シーケンスなどにおいては、隣接するブロックから求めた予測動きベクトルが対象ブロックの動きベクトルから遠く離れ、予測が合いにくい場合がある。そのため、非特許文献１に示される探索パターンをさらに倍の大きさに拡大した上、斜め方向の探索点を省略した図８に示されるような探索パターンで、ダイヤモンドサーチと同様の動きベクトル探索を行うことでより広大な範囲を高速に探索することができる。また、この探索を行う際の動きベクトルの評価には、式（１）に定義された残差コストではなくＳＡＤを用いることで、本来の動きに対する追従性を高めることできる。このようにして得られた、更新された予測動きベクトルをＭＶｐｒｅｄとして保持する。また、元のＭＶｐｒｅｄをＭＶｐｒｅｄ０として保持する。併せて更新されたＭＶｐｒｅｄに対応する残差コストをＣＭＥｐｒｅｄとして保持する。
【００５３】
このようにして求めたＣＭＥｐｒｅｄが、未だに周囲のブロックから求めた閾値ＣＭＥｔｈよりも十分に大きい場合、最適な動きベクトルはこれまで探索してきた探索点以外に存在することが考えられる。ステップ１０５では４画素単位での探索しか行っていないので、元々の予測ベクトルから４画素おきに存在する探索点以外にも、探索点は数多く存在する。
【００５４】
（４−７）ステップ１０６
そこでステップ１０６では、もし次式を満足するならば、ＭＶｐｒｅｄを動きベクトルとして採用することを中止してステップ１１１にジャンプする。
【００５５】
ＣＭＥｐｒｅｄ−ＣＭＥｔｈ＞ｄ０    ・・・（３）
但し、ｄ０は十分に大きな定数とする。
【００５６】
（４−８）ステップ１０８
ステップ１０８では、ＭＶｐｒｅｄとＭＶｐｒｅｄ０の同一性をテストする。
【００５７】
もし、周囲ブロックからの動きベクトル予測がうまく働いていた場合、ＭＶｐｒｅｄは小数画素精度（ＭＰＥＧ−４／Ｈ．２６４ならば１／４画素精度、ＭＰＥＧ−１／２では１／２画素精度）で求められており、また、ＭＶｐｒｅｄとＭＶｐｒｅｄ０は同一のはずである。
【００５８】
一方、予測がうまく働いていなかった場合にはＭＶｐｒｅｄとＭＶｐｒｅｄ０は異なり、かつ、ＭＶｐｒｅｄは４画素単位の精度しか持たない。この場合には、ＭＶｐｒｅｄを中心に改めて整数精度、小数精度の動きベクトル検出を行ってより精度の高い動きベクトルを求める必要があると考えられる。
【００５９】
一方、ＭＶｐｒｅｄ＝ＭＶｐｒｅｄ０の場合には、ＣＭＥｐｒｅｄこそある程度大きな値を持っているものの、対象ブロックにとって最適なベクトルである可能性はまだ残されている。そこで、ＭＶｐｒｅｄとＭＶｐｒｅｄ０が異なる場合には、ＭＶｐｒｅｄを動きベクトルとして採用することをあきらめてステップ１１１にジャンプすることで、次のステップで行われる±１／４画素のＣＭＥ算出処理をキャンセルする。
【００６０】
（４−９）ステップ１０９
ステップ１０９では、ＭＶｐｒｅｄの上下左右１／４画素の探索点をテストしてＭＶｐｒｅｄの極小性を判定する。すなわち、ＭＶｐｒｅｄが指し示す探索点の周囲±１／４画素の各探索点において、ＣＭＥを求める。ＭＶｐｒｅｄのＣＭＥと、これら±１／４画素の各探索点のＣＭＥとを比較する。そして、ＭＶｐｒｅｄのＣＭＥが±１／４画素の範囲で極小であることは、ＭＶｐｒｅｄが最適な動きベクトルを示している可能性が高いと考えることができる。
【００６１】
（４−１０）ステップ１１０
そこで、ステップ１１０において、ステップ１０９にてＭＶｐｒｅｄが極小と判定された場合には、ステップ１１３に進み、ＭＶｐｒｅｄを動きベクトルとして出力する。一方、極小と判定されなかった場合には、ステップ１１１に進む。
【００６２】
（４−１１）ステップ１１１、Ｓ１１２
以上のようなステップを経て、それでもＭＶｐｒｅｄが動きベクトルとして十分でないと判断された場合に実行されるのがステップ１１１である。
【００６３】
ステップ１１１では、ＭＶｐｒｅｄを探索中心点とし、非特許文献１に記載のダイヤモンドサーチによって動きベクトル探索を行う。この結果、ステップ１１２に進み、求められた動きベクトルを、対象ブロックの動きベクトルとして出力する。
【００６４】
（５）効果
以上説明したように本実施形態によれば、動きベクトルを予測する際に、隣接する同一ブロックサイズと隣接する小ブロックサイズの動きベクトルの両方を使って予測動きベクトルを求める。隣接同一サイズブロックの動きベクトルはノイズに対してロバストである一方で、ブロックの重心が小ブロックと比べて離れているために動きへの追従性に劣る。一方、隣接小ブロックサイズの動きベクトルは、ノイズに対して脆弱であるが、動きに対しては敏感であるために動きへの追従性が高い。
【００６５】
また、参照するブロックを対象ブロックが内包していないため、さらに予測ベクトルの残差コストから動きベクトルの符号量を取り除いたＳＡＤだけで評価するために、予測動きベクトルがローカルミニマムに陥る可能性を低減でき、より正確な動きベクトルを検出することができる。
【００６６】
また、予測ベクトルに対してＳＡＤに基づいた粗い動き予測を行うことは、予測ベクトルが誤っている場合の補正を行うことに相当するので、さらに前述のローカルミニマムに陥る可能性を低減することができる。
【００６７】
また、予測ベクトルに対応するＣＭＥの大小と極小性に基づいて２段階の処理打ち切りを行うことで、従来法に比べより多くの処理打ち切りを行うことができる。
【００６８】
極小性に基づく打ち切り方法は、予測ベクトルに対するＣＭＥの大小に基づく打ち切りに比べ、多くの場合動きベクトルの精度を維持したまま打ち切り割合を高めることができる。しかし、極小性を判定するためには、例えば予測動きベクトルの周囲１／４画素の探索点についてＣＭＥの計算を行わなければならず、余分に計算量を消費する。この判定処理を予測ベクトルに対応するＣＭＥの大小に応じてスキップすることで、閾値処理と極小性判定処理という単一の打ち切り方法を単純に足し合わせた以上の処理量削減と正確な動きベクトル検出を両立できる。
【００６９】
（６）変更例
本発明は上記実施形態に限らず、その主旨を逸脱しない限り種々に変更することができる。
【００７０】
（６−１）変更例１
上記実施形態のステップ１０４において、対象ブロック１６×８には、小ブロックが８×８が接していた。しかし、対象ブロックが１６×１６で、小ブロックとして８ｘ８に加えて１６×８、または、８×１６も接する場合には、予測ＭＶ候補、閾値候補を取得する条件としては、
・対象ブロックの上側に接する小ブロックのうち、最も右にあり、かつ、サイズが最大であり、かつ、重心の位置が対象ブロックに最も近いもの、
・対象ブロックの左側に接する小ブロックのうち、最も下にあり、かつ、サイズが最大であり、重心の位置が対象ブロックに最も近いもの、
となる。
【００７１】
（６−２）変更例２
上記実施形態において、ステップ１０５では、求めたＭＶｐｒｅｄの周囲を±４画素の精度で粗く探索を行った。しかし、±３画素以上で粗い探索を行えばよい。
【００７２】
（６−３）変更例３
上記実施形態のステップ１０６では、周囲のブロックが持つ残差コストＣＭＥｔｈ＿ｃａｎｄの最小値から閾値を求めていた。しかし、代わりにステップ１０３において、ＣＭＥｔｈ＿ｃａｎｄの最小値だけでなく最大値：
ＣＭＥｔｈ２＝ｍａｘ（ＣＭＥｔｈ＿ｃａｎｄ）＝１２３
を求めておき、式（３）に述べた判定式を次のように変更しても良い。
【００７３】
ＣＭＥｐｒｅｄ−ＣＭＥｔｈ２＞ｄ３
但し、ｄ３は正の定数とする。
【図面の簡単な説明】
【００７４】
【図１】本発明の実施例における動きベクトル検出装置の構成を表すブロック図である。
【図２】マクロブロックの構成とその分割パターンである。
【図３】動きベクトルを求める順序をあらわすフローチャートである。
【図４】動きベクトル検出方法を示すフローチャートである。
【図５】同一ブロックサイズの隣接ブロックである。
【図６】隣接する小ブロックである。
【図７】予測ＭＶ候補を対象ブロックに適用した場合のＣＭＥの例である。
【図８】ステップ１０５で探索を行う探索点である。
【図９】小さな分割パターンからの動きベクトル予測の例である。
【図１０】残差閾値の設定方法の例である。
【図１１】予測ベクトルを用いた際のＳＡＤと閾値とのずれのブロック毎の出現頻度である。
【符号の説明】
【００７５】
１    ＣＰＵ
２    バス
３    ＲＡM
４    ＲＯM
５    画像入力回路
６    符号化画像出力回路
【図１】
2008109632.tif 000004
【図２】
2008109632.tif 000005
【図３】
2008109632.tif 000006
【図４】
2008109632.tif 000007
【図５】
2008109632.tif 000008
【図６】
2008109632.tif 000009
【図７】
2008109632.tif 000010
【図８】
2008109632.tif 000011
【図９】
2008109632.tif 000012
【図１０】
2008109632.tif 000013
【図１１】
2008109632.tif 000014