(57)【要約】【課題】  繰り返しパターンから正しい動きベクトルを検出する。【解決手段】  現在フレームの注目ブロックと参照フレームの複数の参照ブロックのそれぞれとの間の複数のマッチング誤差を計算し、それらの最小マッチング誤差を計算し、前記複数のマッチング誤差の散らばりが大きいほど大きい閾値を計算し、前記注目ブロックと異なる他の注目ブロックについて検出された動きベクトルから補正ベクトルを計算し、前記参照ブロックのうち前記マッチング誤差と前記最小マッチング誤差との差分が前記閾値以内であるブロックの中で、前記注目ブロックとの間の相対位置ベクトルが前記補正ベクトルに最も近いブロックに関する前記相対位置ベクトルを、前記注目ブロックの動きベクトルとして決定する。【選択図】  図１
2012053770.tif 000002
【特許請求の範囲】
【請求項１】
現在フレームの注目ブロックと参照フレームの複数の参照ブロックのそれぞれとの間の複数のマッチング誤差を計算するマッチング誤差算出部と、
前記マッチング誤差の中から最小マッチング誤差を計算する最小マッチング誤差算出部と、
前記複数のマッチング誤差の散らばりが大きいほど大きい閾値を計算する閾値算出部と、
前記注目ブロックと異なる他の注目ブロックについて検出された動きベクトルから補正ベクトルを計算する補正ベクトル算出部と、
前記参照ブロックのうち前記マッチング誤差と前記最小マッチング誤差との差分が前記閾値以内であるブロックの中で、前記注目ブロックとの間の相対位置ベクトルが前記補正ベクトルに最も近いブロックに関する前記相対位置ベクトルを、前記注目ブロックの動きベクトルとして決定する動きベクトル決定部と、
を備える動きベクトル検出装置。
【請求項２】
前記動きベクトル決定部は、前記参照ブロックのうち、前記マッチング誤差と前記最小マッチング誤差との差分が前記閾値以内であって、かつ、前記マッチング誤差が局所的に最小となるブロックの中から、前記注目ブロックの動きベクトルを決定する、
請求項１に記載の動きベクトル検出装置。
【請求項３】
前記補正ベクトル算出部は、前記他の注目ブロックについて検出された動きベクトルの平均ベクトル、または、メディアンベクトルを前記補正ベクトルとして算出する、請求項１に記載の動きベクトル検出装置。
【請求項４】
前記閾値算出部は、前記複数のマッチング誤差の分散を定数倍した値を閾値として算出する、請求項１に記載の動きベクトル検出装置。
【請求項５】
前記閾値算出部は、前記複数のマッチング誤差の最大値と最小値の差分を定数倍した値を閾値として算出する、請求項１に記載の動きベクトル検出装置。
【請求項６】
前記補正ベクトル算出部は、前記現在フレームとは異なる時刻の過去フレームで算出済みの前記動きベクトルの中で、前記過去フレーム上で前記注目ブロックに対応するブロックの周辺ブロックの前記動きベクトルの平均ベクトル、または、メディアンベクトルを前記補正ベクトルとして算出する、請求項１に記載の動きベクトル検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は動きベクトル検出装置及び方法に関する。
【背景技術】
【０００２】
一般的にブロックマッチングを用いた動き探索では、現在フレームを格子状にブロックに分割し、ブロック毎に動きベクトルを探索する。以下、これから動きベクトルを検出するブロックを注目ブロックとする。ブロックマッチング法では、注目ブロックとのマッチング誤差が最も小さい参照ブロックが参照フレームから探索され、参照ブロックと注目ブロックとの間の相対位置ベクトルが動きベクトルとして検出される。ブロックマッチング法では、ＳＡＤ（Ｓｕｍ  ｏｆ  Ａｂｓｏｌｕｔｅ  Ｄｉｆｆｅｒｅｎｃｅ）やＳＳＤ（Ｓｕｍ  ｏｆ  Ｓｑｕａｒｅｄ  Ｄｉｆｆｅｒｅｎｃｅ）がマッチング誤差として用いられることが多い。
【０００３】
入力フレーム内に周期的な繰り返しパターンが含まれる場合、複数の参照ブロックで小さなＳＡＤ値となることがある。ＳＡＤ値によるブロックマッチングでは、誤った動きベクトルが検出されることがある。そこで、候補ベクトルとマッチング誤差を対応付けたＳＡＤマップの水平、垂直投影ヒストグラムを用いたパターン分析に基づいて、注目ブロックが繰り返しパターンであるか否かを判定し、注目ブロック周辺で既に検出済みの動きベクトルの平均ベクトルで補正する技術がある。しかし、水平、垂直投影ヒストグラムを用いているため、斜め方向へのパターンに対しては、繰り返しパターンであるか否かの判定ができず、正しい動きベクトルを検出することができない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４１５５９５２号公報（米国特許第７５５５１６６号）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述したように、従来技術では斜め方向のパターンに対して、繰り返しパターンであるか否かの判定ができず、正しい動きベクトルを検出することができない。本発明の実施形態は、誤りの少ない動きベクトルを決定する動きベクトル検出、方法およびプログラムを提供する。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明の一実施形態の動きベクトル検出装置は、現在フレームの注目ブロックと参照フレームの複数の参照ブロックのそれぞれとの間の複数のマッチング誤差を計算するマッチング誤差算出部と、前記マッチング誤差の中から最小マッチング誤差を計算する最小マッチング誤差算出部と、前記複数のマッチング誤差の散らばりが大きいほど大きい閾値を計算する閾値算出部と、前記注目ブロックと異なる他の注目ブロックについて検出された動きベクトルから補正ベクトルを計算する補正ベクトル算出部と、前記参照ブロックのうち前記マッチング誤差と前記最小マッチング誤差との差分が前記閾値以内であるブロックの中で、前記注目ブロックとの間の相対位置ベクトルが前記補正ベクトルに最も近いブロックに関する前記相対位置ベクトルを、前記注目ブロックの動きベクトルとして決定する動きベクトル決定部と、を備える。
【図面の簡単な説明】
【０００７】
【図１】実施形態に係わる動きベクトル検出装置のブロック図。
【図２】実施形態の手順の一例を示すフローチャート。
【図３】実施形態の処理内容を表す概念図。
【図４】過去フレームから補正ベクトルを求める処理を説明するための補助図。
【図５】マッチング誤差の散らばりの程度が小さいほど閾値が小さくなる様子を示す図。
【図６】現在フレームから補正ベクトルを求める処理を説明するための補助図。
【発明を実施するための形態】
【０００８】
以下、本発明の一実施形態に係る動きベクトル検出装置について説明する。
【０００９】
図１は、本実施形態に係わる動きベクトル検出装置のブロック図である。
【００１０】
本実施形態の動きベクトル検出装置１０は、注目ブロックと参照ブロックとのマッチング誤差を計算するマッチング誤差算出部１０１と、最小マッチング誤差を計算する最小マッチング誤差算出部１０２と、閾値を計算する閾値算出部１０３と、既に動き検出がなされたブロックの動きベクトルに基づいて補正ベクトルを算出する補正ベクトル算出部１０４と、前述の補正ベクトルと前述の閾値に基づいて前述の注目ブロックの動きベクトルを決定する動きベクトル決定部１０５とを備える。
【００１１】
マッチング誤差算出部１０１は、現在フレームの注目ブロックと参照フレームに設定される複数の参照ブロックのそれぞれとの間の、複数のマッチング誤差を計算する。最小マッチング誤差算出部１０２は、マッチング誤差算出部１０１で求められた複数のマッチング誤差の中から最小マッチング誤差を計算する。閾値算出部１０３は、前述の複数のマッチング誤差の散らばりが大きいほど大きくなるように閾値を計算する。補正ベクトル算出部１０４は、注目ブロックよりも前に動きベクトルが求められた１つ以上のブロックで検出済みの１つ以上の動きベクトルから補正ベクトルを算出する。動きベクトル決定部１０５は、前記最小マッチング誤差からの差分が前記閾値以内である前記参照ブロックと前記注目ブロックの相対位置ベクトルのうち、前記補正ベクトルとの差分が最も小さい前記相対位置ベクトルを前記注目ブロックの前記動きベクトルとして決定する動きベクトル決定部１０５とを備えている。
【００１２】
図２は、本実施形態の動きベクトル検出装置の動作を示すフローチャートである。
【００１３】
マッチング誤差算出部１０１は、注目ブロックと参照ブロックとの間のマッチング誤差１０６を算出するとともに、ＳＡＤマップ１０７を求める（ステップＳ２０１）。マッチング誤差算出部１０１には、現在フレーム１１２と参照フレーム１１３が入力される。現在フレーム１１２と参照フレーム１１３は異なるフレームである。注目ブロックと参照フレームに設定される複数の参照ブロックとのマッチング誤差の集合Ｃｄは、数式１に基づいて算出される。
【数１】
2012053770.tif 000003
【００１４】
数式１中のＤ（ｕ）は、注目ブロックに対して動きベクトルｕを割り当てた場合のマッチング誤差を表す。Ｃは探索候補ベクトルの集合を表す。例えば、探索候補ベクトルの集合Ｃとして、注目ブロックを中心とした一定領域内の画素の相対位置ベクトルの集合を用いることができる。また、注目ブロックの周辺ブロックで検出済みの動きベクトルと、過去フレームで注目ブロックに対応するブロック周辺で検出済みの動きベクトルと、現在フレーム、参照フレームをそれぞれ縮小した画素単位で算出された動きベクトルを探索候補ベクトルとして用いてもよい。この場合、マッチング誤差算出部１０１に動きベクトル決定部１０５から出力された動きベクトル１１０を更に入力する。マッチング誤差Ｄ（ｕ）は、例えば、数式２に基づいて算出される。
【数２】
2012053770.tif 000004
【００１５】
数式２中のＢは注目ブロック内の画素位置を示す位置ベクトル集合を表し、Ｉｓｒｃは現在フレーム１１２を表し、Ｉｒｅｆは参照フレーム１１３を表す。また、マッチング誤差Ｄ（ｕ）は数式２で算出される値に限らず、数式３や数式４で算出される値を用いても構わない。
【数３】
2012053770.tif 000005
【数４】
2012053770.tif 000006
【００１６】
数式４中の｜Ｂ｜は位置ベクトル集合Ｂの要素数を表す。
【００１７】
マッチング誤差算出部１０１から出力されるＳＡＤマップ１０７の概念図を図３に示す。ＳＡＤマップ１０７はマッチング誤差と探索候補ベクトルを対応付けたデータである。本来ＳＡＤマップ１０７は３次元で表現されるものであるが、説明を簡単にするために図３では２次元で表現している。図３における横軸は探索候補ベクトルが示す相対位置を表し、縦軸はその位置に対応するＳＡＤ値を表す。図３の曲線が算出されたマッチング誤差を表す曲線である。以下適宜図３を参照しながら説明する。
【００１８】
最小マッチング誤差算出部１０２は、入力されたマッチング誤差１０６に基づいて最小マッチング誤差１０８を計算する（ステップＳ２０２）。最小マッチング誤差算出部１０２は、数式５に基づき、マッチング誤差集合Ｃｄの要素の最小値である最小マッチング誤差１０８ｄｍｉｎを算出する。
【数５】
2012053770.tif 000007
【００１９】
数式５のｍｉｎ（）は最小値を求めるオペレータである。
【００２０】
閾値算出部１０３は、入力されたマッチング誤差１０６に基づいて閾値１１１を算出する（ステップＳ２０３）。閾値算出部１０３は、まず数式６に基づいてマッチング誤差１０６の分散σｄを算出する。
【数６】
2012053770.tif 000008
【００２１】
数式６のμｄはマッチング誤差１０６の平均値であり、数式７によって算出される。
【数７】
2012053770.tif 000009
【００２２】
次に数式８に基づいて閾値１１１εを算出する。（図３のε）
【数８】
2012053770.tif 000010
【００２３】
数式８のτは定数である。閾値をσｄに比例させることで、マッチング誤差１０６の散らばりに応じて閾値１１１を動的に変化させることができるので、輝度変化がほとんど無い領域での誤検出を防ぐことができる。例えば、輝度変化がほとんど無い領域におけるＳＡＤマップは図５のようになり、マッチング誤差１０６の散らばりが小さいときには閾値１１１εも小さくなる。また、閾値１１１εは、数式９に従って、マッチング誤差の最大値と最小値との差分を用いて計算しても構わない。
【数９】
2012053770.tif 000011
【００２４】
数式９のｄｍａｘはマッチング誤差の最大値であり、数式１０に従って算出される。
【数１０】
2012053770.tif 000012
【００２５】
数式１０のｍａｘ（）は最大値を求めるオペレータである。また、閾値１１１εは数式１１に従って算出しても構わない。
【数１１】
2012053770.tif 000013
【００２６】
数式１１のｄｉはマッチング誤差集合Ｃｄのｉ番目の要素を表す。
【００２７】
補正ベクトルを算出するステップＳ２０４では、後述する動きベクトル決定部１０５で求められた動きベクトル１１０が補正ベクトル算出部１０４に入力され、補正ベクトル１０９が求められる。補正ベクトル１０９は数式１２に従って求められる。図４は補正ベクトル１０９を求めるために参照されるブロックの位置関係を示す。補正ベクトル１０９は、過去フレーム４０上で注目ブロック４１０に対応するブロック４００の周辺ブロック４０１、４０２、４０３、４０４に関して検出された動きベクトル１１０の平均である。
【数１２】
2012053770.tif 000014
【００２８】
数式１２で、ｕａｍｄ１（ｂ）は補正ベクトル１０９であり、ｂは注目ブロックの位置ベクトルであり、ｕｔ−１（ｐ）は過去フレームで位置ベクトルｐのブロックに割り当てられている動きベクトル１１０であり、Ｌ１（ｂ）は位置ベクトルｂのブロック周辺にあるブロックの位置ベクトル集合である。Ｌ１（ｂ）は、例えば、ブロックｂおよび、ブロックｂの隣接４近傍のブロック（上、下、左、右のブロック）として数式１３のように定義することができる。
【数１３】
2012053770.tif 000015
【００２９】
動きベクトルはブロック毎に定義されるため、ブロックの位置ベクトルはブロックを最小構成単位とした座標系で表される。Ｌ１（ｂ）はブロックｂの周辺であればよく、隣接８近傍のブロックを用いても構わない。また、補正ベクトル１０９として数式１４のｕａｍｄ２（ｂ）を用いても構わない。すなわち、過去フレームの動きベクトルではなく、現在フレームで検出済みの動きベクトル１１０を平均したものを用いても構わない。
【数１４】
2012053770.tif 000016
【００３０】
数１４のＬ２（ｂ）は位置ベクトルｂのブロック周辺にあるブロックの位置ベクトル集合である。図６は画面内の各ブロックの動きベクトルをラスタスキャン順に算出する場合の例である。注目ブロック４１０から見て、左、左上、上、右上のブロック６０１、６０２、６０３、６０４のそれぞれの動きベクトルは既に検出済みである。よって、Ｌ２（ｂ）は、例えば、数式１５のように定義されることができる。
【数１５】
2012053770.tif 000017
【００３１】
補正ベクトル１０９として、過去フレームで検出済みの全ての動きベクトル１１０を平均したベクトルを用いても構わないし、過去フレームで検出済みの動きベクトル１１０のメディアンベクトルを用いても構わない。
【００３２】
動きベクトルを決定するステップＳ２０５では、最小マッチング誤差１０８、閾値１１１及びＳＡＤマップ１０７に基づいて、動きベクトル決定部１０５が動きベクトル１１０を決定する。動きベクトル決定部１０５は、参照ブロックの中から候補ブロックを求める。最小マッチング誤差１０８と候補ブロックのマッチング誤差との差は閾値以下である。動きベクトル決定部１０５は、候補ブロックと注目ブロックとの間の候補ベクトル３００のうち、補正ベクトル１０９との差分が最も小さい候補ベクトル３００を、注目ブロックの動きベクトル１１０（ｕｏｕｔ）として決定する。数式１６に基づいて、動きベクトル１１０（ｕｏｕｔ）を決定する。
【数１６】
2012053770.tif 000018
【００３３】
数式１６で、ｕａｍｄは補正ベクトル算出部１０４によって算出された補正ベクトル１０９（すなわちｕａｍｄ１、ｕａｍｄ２）であり、「｜｜ｘ｜｜」はベクトルｘのノルムである。例えば、Ｌ１ノルムやＬ２ノルムである。Ｃεは候補ブロックのそれぞれに対応する候補ベクトル集合であり、数式１７のように定義する。
【数１７】
2012053770.tif 000019
【００３４】
ステップＳ２０６では全てのブロックについて処理していれば終了し、そうでなければ、ステップＳ２０１に戻る。
【００３５】
このように、実施形態に係わる動きベクトル装置は、ＳＡＤマップを閾値処理することで、補正ベクトルに最も近い動きベクトルを選択する。これにより、テクスチャの形状の影響による誤りを抑制することが可能となる。
【００３６】
なお、この動きベクトル検出装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。すなわち、マッチング誤差算出部１０１、最小マッチング誤差算出部１０２、閾値算出部１０３、補正ベクトル算出部１０４および動きベクトル決定部１０５は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、動きベクトル検出装置は、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現しても構わない。
【００３７】
上述の実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。上述の実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。上述の実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明（とその均等）の範囲に含まれる。
【符号の説明】
【００３８】
１０    動きベクトル検出装置            １０１  マッチング誤差算出部
１０２  最小マッチング誤差算出部        １０３  閾値算出部
１０４  補正ベクトル算出部              １０５  動きベクトル決定部
１０６  マッチング誤差                  １０７  ＳＡＤマップ
１０８  最小マッチング誤差              １０９  補正ベクトル
１１０  動きベクトル                    １１１  閾値
１１２  現在フレーム                    １１３  参照フレーム
【図１】
2012053770.tif 000020
【図２】
2012053770.tif 000021
【図３】
2012053770.tif 000022
【図４】
2012053770.tif 000023
【図５】
2012053770.tif 000024
【図６】
2012053770.tif 000025