(57)【要約】【課題】ブロック内に異なる動きが混在しているような場合にも、より正確に動ベクトルを求めることができるマッチング方法および装置を提供すること。【解決手段】第１の反復勾配法１では、入力された現フレームと前フレームの画像を使用して、第１段の反復勾配法（ブロックサイズ８×８；大ブロック）が実行され、ブロック出力ベクトルａが求められる。初期変位ベクトル決定部２は、該ブロック出力ベクトルａおよび／あるいは該ブロック出力ベクトルａを基に計算により求めた動ベクトルを候補とし、入力された現フレームと前フレームの画像を使用して、該候補から第２の反復勾配法３（ブロックサイズ４×４；小ブロック）の初期変位ベクトルｂを決定する。第２の反復勾配法３では、該初期変位ベクトルｂを基に第２段の反復勾配法が実行され、小ブロック毎の動ベクトル（出力ベクトルｃ）を求める。【選択図】        図１
2004356747.tif 000002
【特許請求の範囲】
【請求項１】
初期変位ベクトルを基に反復的に画像のブロック毎の動きや視差を推定する反復勾配法を使用し、画像のマッチングを行うマッチング方法において、
ブロックを複数個のブロックに分割して複数個の小ブロックを形成し、該小ブロックの各々に対して反復勾配法を適用して小ブロック毎に動きや視差を求めることを特徴とする画像のマッチング方法。
【請求項２】
請求項１に記載の画像のマッチング方法において、
前記ブロックの周辺ブロックの動ベクトルを前記小ブロックの初期変位ベクトルの候補動ベクトルとし、該候補動ベクトルの中から該小ブロックの初期変位ベクトルを選択することを特徴とする画像のマッチング方法。
【請求項３】
請求項２に記載の画像のマッチング方法において、
前記候補動ベクトルは、前記ブロックに対応する前フレームのブロックおよびその周辺ブロックの動ベクトルを含むことを特徴とする画像のマッチング方法。
【請求項４】
請求項２又は３に記載の画像のマッチング方法において、
前記候補動ベクトルは、前記ブロックの周辺ブロックの動ベクトルおよび該ブロックに対応する前フレームのブロックおよびその周辺ブロックの動ベクトルの少なくとも一つを演算して求めた動ベクトルを含むことを特徴とする画像のマッチング方法。
【請求項５】
初期変位ベクトルを基に反復的に画像のブロック毎の動きや視差を推定する反復勾配法を使用し、画像のマッチングを行うマッチング装置において、
ブロックを複数個のブロックに分割することにより得られた小ブロックの初期変位ベクトルを決定する初期変位ベクトル決定部と、
該初期変位ベクトル決定部で決定された初期変位ベクトルを基に前記小ブロックの動ベクトルを求める第２の反復勾配法実行手段とを具備したことを特徴とする画像のマッチング装置。
【請求項６】
請求項５に記載の画像のマッチング装置において、
前記画像のブロックの動ベクトルを求める第１の反復勾配法実行手段をさらに具備し、
前記初期変位ベクトル決定部は、前記第１の反復勾配法実行手段で求められた現フレームおよび前フレームのブロックの少なくとも一方の動ベクトルを格納するベクトルメモリと、
該ベクトルメモリから読み出された当該ブロックの周辺ブロックの動ベクトルから前記小ブロックの初期変位ベクトルを選択する初期変位ベクトル選択部とを具備したことを特徴とする画像のマッチング装置。
【請求項７】
請求項６に記載の画像のマッチング装置において、
前記初期変位ベクトル決定部は、前記ベクトルメモリから読み出された動ベクトルを演算して前記候補動ベクトルを求める演算部をさらに具備し、
前記ベクトルメモリから読み出された当該ブロックの周辺ブロックの動ベクトルおよびその演算結果の動ベクトルの少なくとも一つを候補動ベクトルとし、該候補動ベクトルの中から前記小ブロックの初期変位ベクトルを決定することを特徴とする画像のマッチング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像のマッチング方法および装置に関し、特に、動き補正テレビ方式変換や動画像符号化を行う場合、あるいはステレオ画像（左眼画像と右目画像からなる１組の静止画または動画）からの奥行抽出処理を行う場合等に好適な、動画像の中の動きを自動推定したり、左眼・右眼用画像からなるステレオ画像の間の対応点を自動検出したりする画像のマッチング方法および装置に関する。
【０００２】
【従来の技術】
従来、テレビ放送やテレビ電話など、動画像の中の動きを自動推定したり、左眼用画像と右眼用画像からなるステレオ画像の間の対応点を自動検出したりする画像のマッチングの処理においてしばしば使用される方式としては、ブロックマッチング法や反復勾配法が挙げられる。これらの方法を説明する文献としては、次の文献を挙げることができる。
川田他：“動き補正テレビ方式変換の改善”、映像情報メディア学会誌、Ｖｏｌ．５１，Ｎｏ．９（１９９７），ｐｐ．１５７７〜１５８６。
【０００３】
これらの方法は、動き推定の場合、画像を、ある小さいサイズの多数のブロックに分割して、そのブロックごとに現フレームと前フレームとを比較して動きを求めることを基本としている。なお、ステレオマッチングの場合は、前記「現フレーム」と「前フレーム」を、「左眼画像」と「右眼画像」に置き換えて考えればよいので、本願の発明は動き推定の場合を中心に説明し、ステレオマッチングの場合の詳細な説明は省略する。
【０００４】
反復勾配法では、初期変位ベクトルを用いた勾配法を実施する。すなわち、前フレームや現フレームにおいて既に動ベクトルが求まったブロックの動ベクトルの中から選択もしくは計算により動ベクトルを求め、これから計算しようとしているブロックの初期変位ベクトルとする。それを基に勾配法演算を行い、差分ベクトルを得る。差分ベクトルと初期変位ベクトルを加算したものが当該ブロックにおける決定動ベクトルとなる。
【０００５】
より詳しく書くと、次のようになる。すなわち、反復勾配法により求まる動き動ベクトルｖ（画像内のブロック毎）  は、初期偏位動ベクトルをｖ０ として、次の式（１）で求められる（上記文献参照）。
ｖ  ＝  Δｖ  ＋ｖ０  ・・・（１）
ここに、差分ベクトルΔｖ  の水平、垂直成分Δｖｘ、Δｖｙ  は、画素値の水平勾配Δｘ、垂直勾配Δｙ、および初期偏位動ベクトルｖ０  による動き補正フィールド（フレーム）  間差分Δｔ  によって、下記の式（２）および式（３）のように表される。なお、和は当該ブロック内の全画素について適用される。
【０００６】
【数１】
2004356747.tif 000003
【０００７】
【数２】
2004356747.tif 000004
【０００８】
ここに、初期偏位動ベクトルｖ０は、過去に求められた周辺のブロックの動ベクトルを候補としてマッチングにより決定される（詳細は上記文献参照）。
【０００９】
【発明が解決しようとする課題】
しかしながら、このようなブロックベースのマッチング処理の場合、そのブロック内に異なる動きが混在する場合、例えばブロック内に動物体画像と背景画像の境界がある場合、正確な動ベクトルが求まらないという課題がある。
【００１０】
本発明の目的は、前記した従来技術の課題に鑑みてなされたものであり、ブロック内に異なる動きが混在しているような場合にも、より正確に動ベクトルを求めることができるマッチング方法および装置を提供することにある。
【００１１】
【課題を解決するための手段】
前記した目的を達成するために、本発明は、初期変位ベクトルを基に反復的に画像のブロック毎の動きや視差を推定する反復勾配法を使用し、画像のマッチングを行うマッチング方法において、ブロックを複数個のブロックに分割して複数個の小ブロックを形成し、該小ブロックの各々に対して反復勾配法を適用して小ブロック毎に動きや視差を求めるようにした点に第１の特徴がある。
【００１２】
この特徴によれば、、ブロック内に異なる動きが混在しているような場合にも、より正確に動ベクトルを求めることができ、動きや視差をより正確に求めることができるようになる。
【００１３】
また、本発明は、前記ブロックの周辺ブロックの動ベクトルを前記小ブロックの初期変位ベクトルの候補動ベクトルとし、該候補動ベクトルの中から該小ブロックの初期変位ベクトルを選択するようにした点に第２の特徴がある。
【００１４】
この特徴によれば、前記小ブロックの初期変位ベクトルを容易にかつ正確に決定でき、反復勾配法による小ブロックの動ベクトルをより正確に求めることができるようになる。
【００１５】
また、本発明は、初期変位ベクトルを基に反復的に画像のブロック毎の動きや視差を推定する反復勾配法を使用し、画像のマッチングを行うマッチング装置において、ブロックを複数個のブロックに分割することにより得られた小ブロックの初期変位ベクトルを決定する初期変位ベクトル決定部と、該初期変位ベクトル決定部で決定された初期変位ベクトルを基に前記小ブロックの動ベクトルを求める第２の反復勾配法実行手段とを具備した点に第３の特徴がある。
【００１６】
この特徴によれば、小ブロックに対する反復勾配法を、効率よくかつ高精度で実行でき、ブロック内に異なる動きが混在しているような場合にも、より正確に動ベクトルを求めることができるようになる。また、動きや視差をより正確に求めることが可能になる。
【００１７】
【発明の実施の形態】
以下に、本発明を詳細に説明する。まず、本発明の原理を説明する。画像の動き推定や画像のステレオマッチングの概要は、次の通りである。すなわち、画像の動き推定は、動き補償予測符号化やテレビの動き補正方式変換において、動画像（映像）  の各部の動きを推定する処理である。通常、画面を多数のブロックに分割してそのブロックごとに動きを求める。そのブロックサイズは、例えば８画素×８ラインである。
【００１８】
また、画像のステレオマッチングとは、２台のカメラを使用し、左眼画像と右眼画像の１組の画像の組を得る。これは静止画である場合も、動画である場合もある。そして、左眼画像中の各部分が右眼画像中のどの部分に対応しているかをマッチングにより求める。これにより最終的には画像中各部がカメラに対しどのくらい離れているかの奥行きを推定するのがステレオマッチング処理の最終目的となる。このステレオマッチングについては、例えば次の文献が参考となる。
尾上守夫編「画像処理ハンドブック」（昭晃堂）（３９５ページ付近など）。
【００１９】
上記の画像動き推定では現フレームと前フレームとのマッチングを求めるのであるから、これら動き推定とステレオマッチングは、マッチング処理としては全く類似の処理となる。そこで、以下に、画像の動き推定処理を例として、説明を続ける。
【００２０】
画像の動き推定方法を行う代表的な方法として、反復勾配法がある。これについては、前掲の文献の川田他：“動き補正テレビ方式変換の改善”、映像情報メディア学会誌、Ｖｏｌ．５１、Ｎｏ．９（１９９７）などに詳しく書かれている。該反復勾配法により求まる動きベクトルｖは、該文献に記載されているように、式（１）、式（２）、式（３）  のように表現される。
【００２１】
さて、該反復勾配法では、各ブロックに一つだけの動ベクトルを検出するため、当該ブロックに仮に異なる動きや視差が混在していた場合、正確な動ベクトルを検出することができなくなるという不具合がある。そこで、このブロック（例えば、８画素×８ライン）をさらに小ブロック（例えば、４画素×４ライン）に分割し、該小ブロックごとにさらに反復勾配法を適用してより細かい動きや視差の変化に対応できるようにするのが本発明の原理である。
【００２２】
以下に、本発明の一実施形態を、図面を参照して説明する。図１は、本発明の画像のマッチング方法の一実施形態を示すブロック図である。
【００２３】
第１の反復勾配法１では、入力された現フレームと前フレームの画像を使用して、第１段の反復勾配法（ブロックサイズ８×８；大ブロック）が実行され、ブロック毎に動ベクトルが求められる。該動ベクトルは、ブロック出力ベクトルａとして初期変位ベクトル決定部２に入力される。該初期変位ベクトル決定部２は、該ブロック出力ベクトルａおよび／あるいは該ブロック出力ベクトルａを基に計算により求めた動ベクトルを候補とし、入力された現フレームと前フレームの画像を使用して、該候補から第２の反復勾配法３（ブロックサイズ４×４；小ブロック）の初期変位ベクトルｂを決定する。第２の反復勾配法３では、該初期変位ベクトルｂを基に第２段の反復勾配法が実行され、小ブロック毎の動ベクトル（出力ベクトルｃ）が求められる。
【００２４】
以上のマッチング方法により、ブロック内に異なる動きが混在しているような場合にも、より正確に動ベクトルを求めることができる。
【００２５】
次に、前記初期変位ベクトル決定部２の一実施例の構成と動作を、図２を参照して説明する。初期変位ベクトル決定部２は、現フレームのブロック出力ベクトルａを記憶する現フレームベクトルメモリ１１と、前フレームのブロック出力ベクトルａを記憶する前フレームベクトルメモリ１２と、例えば平均化演算を行う演算部１３と、初期変位ベクトル選択部１４とから構成されている。初期変位ベクトル選択部１４は、現フレームおよび前フレームの画像を使用してマッチング処理することにより、現フレームベクトルメモリ１１、前フレームベクトルメモリ１２、および演算部１３から送られてくる動ベクトル候補から最適な動ベクトルを選択し、初期変位ベクトルｂとして、出力する。
【００２６】
次に、図２の初期変位ベクトル決定部２の動作を、図３（ａ）、（ｂ）を参照して説明する。図３（ａ）は、反復勾配法を行って動ベクトルを求める当該ブロック２０と、現フレームベクトルメモリ１１に格納されている当該ブロック２０の周辺動ベクトルＢ，Ｃの概念図Ｆ１を示し、同図（ｂ）は、前フレームベクトルメモリ１２に格納されている前フレームの当該ブロック２０に対応するブロック２０’の動ベクトルＤおよびその周辺ベクトルＥの概念図Ｆ２を示す。ここに、Ｅは、前記動ベクトルＤを含む９個の動ベクトルの平均化動ベクトルを示す。なお、該Ｅは、平均化に限らず他の演算で求めた動ベクトルであってもよい。
【００２７】
いま、図３（ａ）に示されているように、当該ブロック２０内に異なる動きや視差が混在しているとすると、例えば当該ブロック２０内の動ベクトルＣ側はＺ方向に動く物体（Ｘ）に属し、動ベクトルＢ側は背景（Ｙ）に属しているとすると、当該ブロック２０は小ブロックに分割され、該小ブロックの動ベクトルを求める動作が行われる。現フレームベクトルメモリ１１からは当該ブロック２０の周辺動ベクトルＢ，Ｃが候補動ベクトルとして初期変位ベクトル選択部１４に送られる。一方、前フレームベクトルメモリ１２からは当該ブロック２０に対応する前フレームのブロック２０’の動ベクトルＤと、演算部１３で平均化された動ベクトルＥが候補動ベクトルとして初期変位ベクトル選択部１４に送られる。
【００２８】
当該ブロック２０を４分割した小ブロックの初期変位ベクトルＡを決定する場合には、初期変位ベクトル選択部１４は、候補動ベクトルＢ〜Ｅと該当小ブロック内部の画素値を用いて前フレームとの対応点演算を行い、差分自乗和を計算し、それを最小とする動ベクトルを初期変位ベクトルｂとして決定する。したがって、当該小ブロックの初期変位ベクトルＡとしては、より正確な動ベクトルが選択される可能性が高くなる。同様に、物体（Ｘ）側に属する小ブロックの初期変位ベクトルＡ’も、より正確な動ベクトルが選択される可能性が高くなる。
【００２９】
なお、前記候補動ベクトルとして、現フレームベクトルメモリ１１に蓄積されている当該ブロックの周辺ブロックの動ベクトルのみとしても良い。
【００３０】
図４は、前記初期変位ベクトル決定部２の変形例を示し、図２と異なるところは、現フレームベクトルメモリ１１に蓄積されている周辺動ベクトルを演算部１３に入力し、該演算部１３により得られた現および前フレームベクトルの平均化動ベクトルを、初期変位ベクトル選択部１４の候補動ベクトルに加えるようにした点にある。
【００３１】
上記の実施例では、当該ブロック２０の上および左隣の周辺動ベクトルＢ，Ｃ、当該ブロック２０に対応する前フレームのブロック２０’の動ベクトルＤおよび平均化動ベクトルＥを候補動ベクトルとしたが、本発明はこれに限定されず、他の周辺動ベクトルを候補動ベクトルに加える、あるいは候補動ベクトルとしてもよい。
【００３２】
以上のようにして小ブロックの初期変位ベクトルが決定されると、第２段の反復勾配法３がこの初期変位ベクトルを使用して実施され、小ブロック毎のより正確な動ベクトルが出力ベクトルとして出力されることになる。
【００３３】
【発明の効果】
以上の説明から明らかなように、請求項１の発明によれば、ブロック内に異なる動きが混在しているような場合にも、より正確に動ベクトルを求めることができ、動きや視差をより正確に求めることができるようになる。
【００３４】
また、請求項２の発明によれば、前記小ブロックの初期変位ベクトルを容易にかつ正確に決定でき、反復勾配法による小ブロックの動ベクトルをより正確に求めることができるようになる。
【００３５】
また、請求項３、４の発明によれば、有効なブロックベクトルを、小ブロックの初期変位ベクトルの候補動ベクトルとすることができるようになる。
【００３６】
また、請求項５の発明によれば、小ブロックに対する反復勾配法を、効率よくかつ高精度で実行できるマッチング装置を提供することができる。
【００３７】
また、請求項６、７の発明によれば、有効なブロックベクトルを、小ブロックの初期変位ベクトルの候補動ベクトルとすることができるマッチング装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態の構成を示すブロック図である。
【図２】図１の初期変位ベクトル決定部の一実施例の構成を示すブロック図である。
【図３】本実施形態の動作を説明するための候補動ベクトルの説明図である。
【図４】初期変位ベクトル決定部の他の実施例の構成を示すブロック図である。
【符号の説明】
１・・・第１の反復勾配法、２・・・初期変位ベクトル決定部、３・・・第２の反復勾配法、１１・・・現フレームベクトルメモリ、１２・・・前フレームベクトルメモリ、１３・・・演算部、１４・・・初期変位ベクトル選択部。
【図１】
2004356747.tif 000005
【図２】
2004356747.tif 000006
【図３】
2004356747.tif 000007
【図４】
2004356747.tif 000008