(57)【要約】【課題】動きベクトルを高速に安定的に求められるようにする。【解決手段】多重解像度化部３１は、入力画像を複数の解像度の画像に変換し、多重解像度画像バッファ３２−１は、複数の解像度に変換された第１のタイミングの第１の画像を蓄積し、多重解像度画像バッファ３２−２は、複数の解像度に変換された第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積し、対応点探索部３３は、第１の解像度の第２の画像の各画素と第１の解像度の第１の画像の各画素との対応点を探索し、対応点動きベクトルバッファ３４に格納し、格納された第１の解像度の対応点情報に基づいて、第１の解像度よりも高解像度の第２の解像度の第２の画像の各画素と第２の解像度の第１の画像の各画素との対応点を探索し、順次繰り返す。本発明は、撮像装置に適用することができる。【選択図】図４
2008053875.tif 000002
【特許請求の範囲】
【請求項１】
入力画像を複数の解像度の画像に変換する多重解像度化手段と、
前記多重解像度化手段により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積手段と、
前記多重解像度化手段により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積手段と、
第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索手段と、
前記対応点探索手段により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納手段とを含み、
前記対応点探索手段は、前記格納手段に格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す
画像処理装置。
【請求項２】
前記対応点探索手段は、
前記第１の解像度における第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の評価値をブロックマッチングにより求める評価値計算手段をさらに含み、
前記評価値計算手段により計算された評価値が最小となる画素を対応点として探索する
請求項１に記載の画像処理装置。
【請求項３】
前記評価値計算手段は、前記ブロックマッチングのブロック内の注目画素からの距離に応じた重み付け評価を用いて、前記第１の解像度の第２の画像の各画素と前記第１の解像度の第１の画像の各画素との対応点の評価値を求める
請求項２に記載の画像処理装置。
【請求項４】
前記評価値計算手段は、前記ブロックマッチングのブロック間の対応画素間の画素値の差に応じた重み付け評価を用いて、前記第１の解像度の第２の画像の各画素と前記第１の解像度の第１の画像の各画素との対応点の評価値を求める
請求項２に記載の画像処理装置。
【請求項５】
所定の解像度の画像における対応点の近傍にある５個の画素に対する５個の評価値を計算し、前記５個の評価値に基づいた近似関数の係数により、前記対応点を求めるフィッティング計算手段をさらに含む
請求項２に記載の画像処理装置。
【請求項６】
所定の解像度の画像における対応点の近傍にある９個の画素に対する９個の評価値を計算し、前記９個の評価値に基づいた近似関数の係数により、前記対応点を求めるフィッティング計算手段をさらに含む
請求項２に記載の画像処理装置。
【請求項７】
前記多重解像度化手段は、前記入力画像を、前記入力画像よりも低解像度の複数の解像度の画像、または、前記入力画像よりも高解像度の複数の解像度の画像に変換する
請求項１に記載の画像処理装置。
【請求項８】
入力画像を複数の解像度の画像に変換する多重解像度化ステップと、
前記多重解像度化ステップの処理により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積ステップと、
前記多重解像度化ステップの処理により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積ステップと、
第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索ステップと、
前記対応点探索ステップの処理により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納ステップとを含み、
前記対応点探索ステップの処理は、前記格納ステップの処理で格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す
画像処理方法。
【請求項９】
入力画像を複数の解像度の画像に変換する多重解像度化ステップと、
前記多重解像度化ステップの処理により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積ステップと、
前記多重解像度化ステップの処理により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積ステップと、
第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索ステップと、
前記対応点探索ステップの処理により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納ステップとを含み、
前記対応点探索ステップの処理は、前記格納ステップの処理で格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す
プログラム。
【請求項１０】
請求項９に記載のプログラムが格納されたプログラム格納媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および方法、プログラム、並びにプログラム格納媒体に関し、特に、動きベクトルを画素単位で高速に、かつ、安定して抽出できるようにした画像処理装置および方法、プログラム、並びにプログラム格納媒体に関する。
【背景技術】
【０００２】
動画像中の物体の動きを求める手段や画像間の対応を求める手段としてブロックマッチングがある。
【０００３】
これは、例えば、図１で示されるように、再生されるタイミングが連続した２つの画像PA，PB（画像PAが再生された後に画像PBが再生される）が与えられたとき、画像PA上のある画素p1（または画像領域）が画像PB上の、どの画素に（またはどの画像領域に）「対応」するかを、画素p1近傍の画素からならるブロックで検索し、対応位置の画素p2を特定する処理である。尚、図１においては、Sbは、マッチングブロックのサイズSb×Sbの１辺の画素数を示したものであり、Ssは、マッチングブロックを移動させる範囲、すなわち、探索範囲を示す探索範囲Ss×Ssの１辺の画素数を示したものである。
【０００４】
また、図２で示されるように、特に、動画において時間的に連続したフレーム画像B2，B1，CF，F1，F2とする場合、上述の「対応」は、フレーム画像CF上の画素p1およびフレーム画像F1上の画素p2に基づいて、v1=p2-p1を求めれば画素p1を起点とする二次元の動きベクトルv1という形で表現することができる。尚、図２においては、フレームB2，B1，CF，F1，F2の順序で時間方向に配置されており、実線で囲まれ、水平方向および垂直方向に点線が入ったマスが画素を示しており、特に各マスの点線の交点部分が画素中心を示している。
【０００５】
ブロックマッチングは画像処理の幅広い分野で重要な基礎技術として利用されており、例えば、高ダイナミックレンジ化、ノイズ削減、手ぶれ防止、フレーム挿入などに応用されている（特許文献１参照）。
【０００６】
【特許文献１】特開２００２−０４４６６９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、近年の画像処理技術は、ブロックサイズを小さくし大局的なオブジェクトの構造および動特性を配慮することにより、さらなる圧縮率の向上を狙う傾向にある。また、撮像素子の解像度が上がったため、データ量が増え、フレームあたりの処理時間を下げることが一層困難になってきている。ここで、画素単位でブロックマッチングに必要な計算量を考えてみる。
【０００８】
すなわち、図１で示されるように参照画像PAと目的画像PBの2枚からオプティカルフローを求める。
【０００９】
ここで、画像解像度は、画像PA，PBともに、W×H = W×(Ar×W)（Arはアスペクト比）であり、マッチングブロックサイズは、Sb×Sb=(Kb×W)×(Kb×W)であり、ブロック可動範囲（探索範囲）はSs×Ss=(Ks×W)×(Ks×W)であり、Sb<<MIN(W,H)かつSS<<MIN(W,H)であり、ブロックマッチングにおけるブロック間のマッチングの評価は、e(p1，p2)＝Σ（dyが−Sb/2乃至Sb/2）Σ（dxが−Sb/2乃至Sb/2）Diff(C1（x1＋dx，y1＋dy），C（x2＋dx，y2＋dy）)であるものとする。尚、MIN（W,H）は、WまたはHのいずれか小さい方の値を取る関数を示している。
【００１０】
さらに、C(x，y)は座標p={x，y}における輝度値を表す。またDiff(C，C’)は輝度値CとC’の非類似度を表す関数で、たとえば二乗誤差などがよく使われる。また各添字はフレーム番号に対応する。
【００１１】
さらに、Tcは、１画素同士のマッチング計算f(C，C’)にかかる時間(データ転送も含む)であるものとする。
【００１２】
これらの条件のもとで、全探索をかける場合、計算時間Tは、T=W×H×Sb×Sb×Ss×Ss×Tc=Ar×Ks^2×Kb^2×W^6×Tcと概算でき、Wの６乗に比例する計算量となる。
【００１３】
例えば、マッチングブロックサイズを固定したとしてもWの４乗に比例する計算量である。これではSD（Standard Definition）画質の6倍の画素数を持つHD（High Definition）画質の動画を処理すると最悪の場合、（√6）^6=216倍（「^」はべき乗を示している）の時間がかかることになる。さらに、昨今はカメラの撮像素子の画素サイズが小さくなった分、相対的に低感度となり、その影響で暗ノイズが増える傾向にある。そのため暗い環境で撮影された画像では、ブロックマッチングが破綻し、ロバスト性を低下させる可能性が高い。また、さらに高フレームレート化し、より動特性の高い画像を得ようとすると、フレームあたりの光量が減り、必然的に暗ノイズが増え、一層ロバスト性を低下させることとなり、さらにデータ量が増大することにより処理時間が一層増す。結果として、処理時間を短縮させることは、一層困難なものとなりつつある。
【００１４】
そこで、これらの問題を解決するため、従来においては、専用計算ハードウェアを使用したり、探索範囲を限定した計算（Lucas-Kanade法やエピポーラの使用）を行ったり、上述の手法で一部の代表点だけ計算した後で必要な部分を補間するようにしたり、入力画像を多重解像度化して計算したり、入力画像を十分に高画質化した後でマッチングを計算したり、さらには、撮像素子を改良するといった方法のいずれか１つを用いるか、あるいは複数に組み合わせることで解決を図る試みが続けられてきた。
【００１５】
これらの試行の一つとして、与えられた画像から徐々に解像度を低くしていった画像群、いわゆる画像ピラミッドを使う方法が提案されている。画像ピラミッドは、入力画像を低解像度化する処理が繰り返されることで生成される複数の解像度の画像群である。入力画像を低解像度化する場合、複数の画素を平均化する平均化フィルタのようなローパスフィルタが用いられ、低解像度レベルの画像から処理を開始し、徐々に高解像度レベルの画像に切り替えながら画素間の対応の計算を高精度化してゆく。この方法が用いられることによりマッチングブロックサイズと探索範囲とは、大幅に小さくすることが可能となり、結果として、処理の高速化が可能になる。例えば1280×960の画像を倍数1/4で低解像度化して、7種類の画像から構成される画像ピラミッドを考える。
【００１６】
すなわち、解像度レベル(0)では解像度を1280×960とし、解像度レベル(0)相当の探索範囲Ss×Ssを196×196とし、解像度レベル(0)相当のマッチングブロックサイズSb×Sbを196×196とすると、検査回数は、1280×960×196^4となる。
【００１７】
これに対して、解像度レベル(0)では解像度を640×480となり、解像度レベル(0)相当の探索範囲Ss×Ssは96×96となり、解像度レベル(0)相当のマッチングブロックサイズSb×Sbは96×96となるので、検査回数は、解像度レベル(0)での1/2^4倍となる。
【００１８】
また、解像度レベル(2)では解像度を320×240となり、解像度レベル(0)相当の探索範囲Ss×Ssは48×48となり、解像度レベル(0)相当のマッチングブロックサイズSb×Sbは48×48となるので、検査回数は、解像度レベル(0)での1/2^8倍となる。
【００１９】
さらに、解像度レベル(3)では解像度を160×120となり、解像度レベル(0)相当の探索範囲Ss×Ssは24×24となり、解像度レベル(0)相当のマッチングブロックサイズSb×Sbは24×24となるので、検査回数は、解像度レベル(0)での1/2^12倍となる。
【００２０】
また、同様に、解像度レベル(4)では解像度を80×60となり、解像度レベル(0)相当の探索範囲Ss×Ssは12×12となり、解像度レベル(0)相当のマッチングブロックサイズSb×Sbは12×12となるので、検査回数は、解像度レベル(0)での1/2^16倍となる。
【００２１】
さらに、同様に、解像度レベル(0)では解像度を40×30となり、解像度レベル(0)相当の探索範囲Ss×Ssは6×6となり、解像度レベル(0)相当のマッチングブロックサイズSb×Sbは6×6となるので、検査回数は、解像度レベル(0)での1/2^20倍となる。
【００２２】
また、同様に、解像度レベル(6)では解像度を20×15となり、解像度レベル(0)相当の探索範囲Ss×Ssは3×3となり、解像度レベル(0)相当のマッチングブロックサイズSb×Sbは3×3となるので、検査回数は、解像度レベル(0)での1/2^24倍（=20×15×3^4）となる。
【００２３】
このとき解像度レベル(0)で大きなSsとSbを設定したとしても解像度レベル(6)では相対的に非常に小さなW,H,Ss,Sbでよいため、結果的に計算量を小さくすることが可能となる。より具体的には、例えば、Ss=Sb=196としても、解像度レベル(6)では高々3×3画素の検索範囲でしかも高々3×3画素のマッチングブロックを用いた処理を高々20×15点で調べればよい。
【００２４】
また、低解像度でのオブジェクト構造概形からスタートして徐々に詳細化してゆくので、動きベクトル同士の関係構造を崩さず、動力学的にそれぞれの画像中の2次元オブジェクトのある部位同士が構造上の同一部位であるという意味での対応を求めることが可能である。
【００２５】
しかしながら、下位レベルで求めた対応を適切に上位レベルに反映させることができないと、安定的に精度を向上させていくことができない恐れがある。
【００２６】
また、どの応用においても低照度などの悪条件下での撮像映像への対処として、十分に高画質化した後にブロックマッチングを実行することが必須となる。しかしながら、画質そのものを向上させるためにブロックマッチングを実施するのであって、ブロックマッチングを行うために画質向上を事前にするということでは本末転倒になってしまうことがあった。また、単純な撮像素子の改良では膨大なコストがかかる上、すでに存在する画像に対処することはできない恐れがあった。
【００２７】
結果として、いずれの方法でも確立したロバストな方法がない上、コスト高となる恐れがあった。
【００２８】
本発明はこのような状況に鑑みてなされたものであり、特に、ノイズ耐性を維持しつつ、高速で、かつ、高精度に動きベクトルを検出できるようにするものである。
【課題を解決するための手段】
【００２９】
本発明の一側面の画像処理装置は、入力画像を複数の解像度の画像に変換する多重解像度化手段と、前記多重解像度化手段により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積手段と、前記多重解像度化手段により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積手段と、第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索手段と、前記対応点探索手段により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納手段とを含み、前記対応点探索手段は、前記格納手段に格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す。
【００３０】
前記対応点探索手段には、前記第１の解像度における第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の評価値をブロックマッチングにより求める評価値計算手段をさらに含ませるようにすることができ、前記評価値計算手段により計算された評価値が最小となる画素を対応点として探索させるようにすることができる。
【００３１】
前記評価値計算手段には、前記ブロックマッチングのブロック内の注目画素からの距離に応じた重み付け評価を用いて、前記第１の解像度の第２の画像の各画素と前記第１の解像度の第１の画像の各画素との対応点の評価値を求めるようにさせることができる。
【００３２】
前記評価値計算手段には、前記ブロックマッチングのブロック間の対応画素間の画素値の差に応じた重み付け評価を用いて、前記第１の解像度の第２の画像の各画素と前記第１の解像度の第１の画像の各画素との対応点の評価値を求めるようにさせることができる。
【００３３】
所定の解像度の画像における対応点の近傍にある５個の画素に対する５個の評価値を計算し、前記５個の評価値に基づいた近似関数の係数により、前記対応点を求めるフィッティング計算手段をさらに含ませるようにすることができる。
【００３４】
所定の解像度の画像における対応点の近傍にある９個の画素に対する９個の評価値を計算し、前記９個の評価値に基づいた近似関数の係数により、前記対応点を求めるフィッティング計算手段をさらに含ませるようにすることができる。
【００３５】
前記多重解像度化手段には、前記入力画像を、前記入力画像よりも低解像度の複数の解像度の画像、または、前記入力画像よりも高解像度の複数の解像度の画像に変換させるようにすることができる。
【００３６】
本発明の一側面の画像処理方法は、入力画像を複数の解像度の画像に変換する多重解像度化ステップと、前記多重解像度化ステップの処理により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積ステップと、前記多重解像度化ステップの処理により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積ステップと、第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索ステップと、前記対応点探索ステップの処理により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納ステップとを含み、前記対応点探索ステップの処理は、前記格納ステップの処理で格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す。
【００３７】
本発明の一側面のプログラムは、入力画像を複数の解像度の画像に変換する多重解像度化ステップと、前記多重解像度化ステップの処理により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積ステップと、前記多重解像度化ステップの処理により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積ステップと、第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索ステップと、前記対応点探索ステップの処理により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納ステップとを含み、前記対応点探索ステップの処理は、前記格納ステップの処理で格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す。
【００３８】
本発明の一側面のプログラム格納媒体は、請求項９に記載のプログラムが格納されている。
【００３９】
本発明の画像処理装置は、独立した装置であっても良いし、画像処理を行うブロックであっても良い。
【発明の効果】
【００４０】
本発明の一側面によれば、動きベクトルを画素単位で、高速に、かつ、安定して抽出することが可能となる。
【発明を実施するための最良の形態】
【００４１】
以下に本発明の実施の形態を説明するが、本明細書に記載の発明と、発明の実施の形態との対応関係を例示すると、次のようになる。この記載は、本明細書に記載されている発明をサポートする実施の形態が本明細書に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、発明に対応するものとして、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その発明に対応するものではないことを意味するものではない。逆に、実施の形態が発明に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その発明以外の発明には対応しないものであることを意味するものでもない。
【００４２】
さらに、この記載は、本明細書に記載されている発明の全てを意味するものではない。換言すれば、この記載は、本明細書に記載されている発明であって、この出願では請求されていない発明の存在、すなわち、将来、分割出願されたり、補正により出現、追加される発明の存在を否定するものではない。
【００４３】
即ち、本発明の一側面の画像処理装置は、入力画像を複数の解像度の画像に変換する多重解像度化手段（例えば、図４の多重解像度化部３１）と、前記多重解像度化手段により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積手段（例えば、図４の多重解像度画像バッファ３２−１）と、前記多重解像度化手段により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積手段（例えば、図４の多重解像度画像バッファ３２−２）と、第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索手段（例えば、図４の対応点探索部３３）と、前記対応点探索手段により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納手段（例えば、図４の対応点動きベクトルバッファ３４）とを含み、前記対応点探索手段は、前記格納手段に格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す。
【００４４】
前記対応点探索手段には、前記第１の解像度における第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の評価値をブロックマッチングにより求める評価値計算手段（例えば、図４の評価計算部３３ｃ）をさらに含ませるようにすることができ、前記評価値計算手段により計算された評価値が最小となる画素を対応点として探索させるようにすることができる。
【００４５】
前記評価値計算手段（例えば、図４の評価計算部３３ｃ）には、前記ブロックマッチングのブロック内の注目画素からの距離に応じた重み付け評価を用いて、前記第１の解像度の第２の画像の各画素と前記第１の解像度の第１の画像の各画素との対応点の評価値を求めるようにさせることができる。
【００４６】
前記評価値計算手段（例えば、図４の評価計算部３３ｃ）には、前記ブロックマッチングのブロック間の対応画素間の画素値の差に応じた重み付け評価を用いて、前記第１の解像度の第２の画像の各画素と前記第１の解像度の第１の画像の各画素との対応点の評価値を求めるようにさせることができる。
【００４７】
所定の解像度の画像における対応点の近傍にある５個の画素に対する５個の評価値を計算し、前記５個の評価値に基づいた近似関数の係数により、前記対応点を求めるフィッティング計算手段（例えば、図１４のフィッティング計算部６１）をさらに含ませるようにすることができる。
【００４８】
所定の解像度の画像における対応点の近傍にある９個の画素に対する９個の評価値を計算し、前記９個の評価値に基づいた近似関数の係数により、前記対応点を求めるフィッティング計算手段（例えば、図１４のフィッティング計算部６１）をさらに含ませるようにすることができる。
【００４９】
前記多重解像度化手段（例えば、図４の多重解像度化部３１）には、前記入力画像を、前記入力画像よりも低解像度の複数の解像度の画像（例えば、図４の多重解像度化部３１の低解像度化フィルタ３１ａ）、または、前記入力画像よりも高解像度の複数の解像度の画像に変換させる（例えば、図４の多重解像度化部３１の高解像度化フィルタ３１ｂ）ようにすることができる。
【００５０】
本発明の一側面の画像処理方法およびプログラムは、入力画像を複数の解像度の画像に変換する多重解像度化ステップ（例えば，図６のステップＳ２２，Ｓ２３）と、前記多重解像度化ステップの処理により複数の解像度に変換された第１のタイミングの第１の画像を蓄積する第１の蓄積ステップ（例えば，図６のステップＳ２２，Ｓ２３）と、前記多重解像度化ステップの処理により複数の解像度に変換された前記第１のタイミングよりも時間的に直前の第２のタイミングの第２の画像を蓄積する第２の蓄積ステップ（例えば，図６のステップＳ２１）と、第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点を探索する対応点探索ステップと、前記対応点探索ステップ（例えば，図６のステップＳ２５）の処理により探索された前記第１の解像度における前記第２の画像の画素と前記第１の解像度における前記第１の画像の画素との対応点の情報を格納する格納ステップ（例えば，図６のステップＳ２６）とを含み、前記対応点探索ステップの処理は、前記格納ステップの処理で格納された前記第１の解像度における対応点の情報に基づいて、前記第１の解像度よりも高解像度の第２の解像度における第２の画像の画素と前記第２の解像度における前記第１の画像の画素との対応点を探索し、順次繰り返す。
【００５１】
図３を参照して、本発明を適用した手ぶれ補正処理装置の一実施の形態の構成について説明する。
【００５２】
図３の手ぶれ補正装置１は、画像を撮像する際、手ぶれにより発生する画像のちらつきを、動きベクトルに応じて補正するものである。
【００５３】
画像バッファ１１は、撮像された画像を一時的に蓄積し、動きベクトル検出部１２および手ぶれ補正部１４に適宜供給する。
【００５４】
動きベクトル検出部１２は、画像バッファ１１に蓄積された画像の各画素について動きベクトルを検出し、動きベクトルバッファ１３に蓄積させる。
【００５５】
手ぶれ補正部１４は、画像バッファ１１に蓄積されている画像を読み出し、動きベクトルバッファ１３に蓄積されている動きベクトルに応じて、手ぶれを補正して出力する。
【００５６】
次に、図４を参照して、動きベクトル検出部１２の構成例について説明する。
【００５７】
多重解像度化部３１は、画像バッファ１１に蓄積されている画像を低解像度化フィルタ３１ａおよび高解像度化フィルタ３１ｂにより複数の解像度の画像に変換し、多重解像度画像バッファ３２−１に供給する。低解像度化フィルタ３１ａは、入力画像を水平方向および垂直方向に隣接する画素を平均化するなどして、低解像度化する処理を所定回数繰り返し、順次低解像度化した画像に変換する。また、高解像度化フィルタ３１ｂは、入力画像を水平方向および垂直方向に隣接する画素間の画素を補間するなどして、高解像度化する処理を所定回数繰り返し、順次高解像度化した画像に変換する。
【００５８】
多重解像度画像バッファ３２−１は、入力画像を含む、入力画像を複数の解像度の画像に変換した画像を一時的に記憶し、次の入力画像について入力されるとき、記憶している複数の解像度の画像を多重解像度画像バッファ３２−２に転送する。すなわち、多重解像度画像バッファ３２−１，３２−２は、時間的に連続する２枚の入力画像について、それぞれ複数の多重解像度化された画像を一時的に記憶している。尚、多重解像度画像バッファ３２−１，３２−２は、新たな入力画像の多重解像度化画像が供給されてくると、それまでに記憶していた画像を消去し、新たな入力画像の多重解像度化画像を記憶する。
【００５９】
対応点探索部３３は、多重解像度画像バッファ３２−１，３２−２に記憶されている最低解像度の画像から各画素について対応点を探索する。すなわち、対応点探索部３３は、多重解像度画像バッファ３２−２に記憶されている直前の画像の画素における動きベクトルの終点となる対応点を、多重解像度画像バッファ３２−１に記憶されている画像の決められた探索範囲内を探索することにより決定し、対応点動きベクトルバッファ３４に格納する。
【００６０】
マッチングブロック設定部３３ａは、多重解像度画像のうち、最低解像度の画像については、直前の画像の注目画素に対応するマッチングブロックを構成する画素を抽出すると供に、今現在の画像における各画素について、探索範囲となるマッチングブロックを構成する画素を抽出する。
【００６１】
また、マッチングブロック設定部３３ａは、多重解像度画像のうち、最低解像度以外の画像については、所定の解像度の直前の画像における注目画素について、初期値動きベクトルバッファ３６に格納されている所定の解像度よりも解像度レベルが１レベル低い画像における対応点（動きベクトルの終点）の情報に基づいて、初期対応点決定部３３ｅにより決定された初期対応点を基準として、探索範囲内の画素とマッチングブロックを構成する画素、すなわち、直前の画像における注目画素と、その近傍の画素を抽出すると供に、探索範囲設定部３３ｂにおいて注目画素に対応して設定される現在の画像上の探索範囲内でマッチングブロックを移動させて、順次マッチングブロックを構成する画素を抽出する。
【００６２】
評価計算部３３ｃは、マッチングブロック設定部３３ａより供給されてくる直前の画像と、現在の画像とのそれぞれのマッチングブロックを構成する画素により評価値を計算する。
【００６３】
対応点決定部３３ｄは、評価計算部３３ｃにより計算された評価値のうち、最も小さな評価値をとる現在の画像の画素、すなわち、直前の画像と現在の画像との間で最も類似しているとみなされる画素を、注目画素の対応点（注目画素の動きベクトルの終点）として対応点動きベクトルバッファ３４に格納する。また、対応点決定部３３ｄは、最も解像度の高い画像（または、動きベクトルを求めようとする所定の解像度の画像）における対応点の情報を動きベクトル生成部３７に供給する。
【００６４】
動きベクトル出力判定部３５は、対応点動きベクトルバッファ３４に新たに対応点の情報が蓄積されると、初期値動きベクトルバッファ３６に転送する。
【００６５】
動きベクトル生成部３７は、最高解像度の画像（または、動きベクトルを求めようとする所定の解像度の画像）における直前の画像における各画素に対応した今現在の画像の対応点の情報に基づいて、動きベクトルを求めて動きベクトルバッファ１３に順次格納する。
【００６６】
次に、図５のフローチャートを参照して、手ぶれ補正処理について説明する。
【００６７】
ステップＳ１において、画像バッファ１１は、入力画像をバッファリングする。
【００６８】
ステップＳ２において、動きベクトル検出部１２は、画像バッファ１１に格納された画像を読み出し、動きベクトル検出処理を実行し、入力された画像の各画素単位で動きベクトルを検出して動きベクトルバッファ１３に格納させる。
【００６９】
ここで、図６のフローチャートを参照して、動きベクトル検出処理について説明する。
【００７０】
ステップＳ２１において、多重解像度化部３１は、多重解像度画像バッファ３２−１を制御して、それまでに記憶していた複数の解像度の画像を多重解像度画像バッファ３２−２に転送させる。このとき、多重解像度画像バッファ３２−２は、それまでに記憶していた多重解像度画像を消去すると供に、新たに供給されてきた多重解像度画像を記憶する。
【００７１】
ステップＳ２２において、多重解像度化部３１は、低解像度化フィルタ３１ａを制御して、入力画像を順次低解像度化した画像に変換して多重解像度画像バッファ３２−１に記憶させる。すなわち、低解像度化フィルタ３１ａは、入力画像（解像度レベル(0)の画像＝Level 0の画像）を、図７で示されるように、水平方向および垂直方向に３×３画素単位で、例えば、以下の式（１）で示されるようなフィルタ処理により画素値を１画素に変換することにより入力画像よりも低解像度の解像度レベル(1)の画像（Level １の画像）に変換する。図７においては、下から順に低解像度化された解像度レベル(0)，(1)，(2)の画像（＝Level ０，１，２の画像）を示しており、それぞれ水平方向、または、垂直方向の１次元の方向の配列状態を示している。また、図中のバツ印は、画素ｐの画素中心を示し、縦棒は画素境界であり、各番号が画素ｐを識別する番号である。従って、図７においては、解像度レベル(0)の画像（Level ０の画像）について、画素p0乃至p15が表示されており、解像度レベル(1)の画像（Level １の画像）について、画素p0乃至p８が表示されており、解像度レベル(2)の画像（Level ２の画像）について、画素p0乃至p４が表示されている。
【００７２】
【数１】
2008053875.tif 000003
【００７３】
尚、式（１）は、ガウシアンフィルタの例を示している。
【００７４】
また、解像度レベル(1)の画像における画素p3は、解像度レベル(0)の画像における画素p5乃至p7の画素値をフィルタ処理した画素値であり、同様にして、解像度レベル(1)の画像における画素p4は、解像度レベル(0)の画像における画素p7乃至p9の画素値をフィルタ処理した画素値であり、解像度レベル(1)の画像における画素p5は、解像度レベル(0)の画像における画素p9乃至p11の画素値をフィルタ処理した画素値である。
【００７５】
同様にして、解像度レベル(2)の画像における画素p2は、解像度レベル(1)の画像における画素p3乃至p5の画素値をフィルタ処理した画素値である。
【００７６】
尚、図７においては、水平方向、または、垂直方向からみた1次元の配置について表現されているため、１レベル（Level）分低い解像度の画像を生成する際、３画素をフィルタ処理した値が、低解像度の１画素として構成されるように表現されているが、実際には、注目画素を中心とした３×３画素に対してフィルタ処理された値が１レベル分低い解像度の画素値として求められることになる。さらに、幾何学的に水平方向および垂直方向に対して画素p0の画素中心の位置が同一位置となり、図中の右端部で示されるように、各レベルの右端部の画素中心が、1レベル上位画像における端部の画素境界と一致するように配置される。
【００７７】
ステップＳ２３において、多重解像度化部３１は、高解像度化フィルタ３１ｂを制御して、入力画像を順次高解像度化した画像に変換して多重解像度画像バッファ３２−２に記憶させる。すなわち、高解像度化フィルタ３１ｂは、入力画像（解像度レベル(0)の画像＝図中のLevel 0の画像）を、図８で示されるように、水平方向および垂直方向に４×４画素単位で、バイキュービックフィルタ処理により画素値を１画素に変換することにより入力画像よりも高解像度の解像度レベル（-1）の画像（Level −１の画像）に変換する。図８においては、上から順に高解像度化された解像度レベル(0)，(-1)，(-2)の画像（＝Level ０，−１，−２の画像）を示しており、それぞれ水平方向、または、垂直方向の１次元の方向の配列状態を示している。従って、図８においては、解像度レベル(0)の画像について、画素p0乃至p3が表示されており、解像度レベル(-1)の画像について、画素p0乃至p7が表示されており、解像度レベル(-2)の画像について、画素p0乃至p１５が表示されている。
【００７８】
また、解像度レベル(-1)の画像における画素p2は、解像度レベル(0)の画像における画素p0乃至p3の画素値をバイキュービックフィルタ処理した画素値である。
【００７９】
同様にして、解像度レベル(-2)の画像における画素p6は、解像度レベル(-1)の画像における画素p2乃至p5の画素値をバイキュービックフィルタ処理した画素値である。
【００８０】
尚、図８においては、水平方向、または、垂直方向からみた1次元の配置について表現されているため、１レベル（Level）分高い解像度の画像を生成する際、４画素のフィルタ処理結果が、高解像度の１画素として構成されるように表現されているが、実際には、注目画素に対して所定の位置に存在する４×４画素に対してバイキュービックフィルタ処理された値が１レベル分高い解像度の画素値として求められることになる。また、高解像度化される場合、上下左右の端部における画素の境界は一致するように変換される。
【００８１】
ステップＳ２４において、対応点探索部３３は、最低解像度対応点抽出処理を実行して、最低解像度の直前の画像の各画素についての対応点（各画素の動きベクトルの終点）を抽出する。
【００８２】
ここで、図９のフローチャートを参照して、最低解像度対応点抽出処理について説明する。
【００８３】
ステップＳ４１において、マッチングブロック設定部３３ａは、多重解像度画像バッファ３２−２に記憶されている、直前の画像における最低解像度の画像のうち、未処理の画素を注目画素pbとして設定すると供に、注目画素pbに対応するマッチングブロックを構成する画素群を抽出し、評価計算部３３ｃに供給する。マッチングブロック設定部３３ａにより設定されるマッチングブロックのサイズは、例えば、Sb[k]×Sb[k]である。ここで、Sb[k]は、以下の式（２）で示される。
【００８４】
【数２】
2008053875.tif 000004
【００８５】
式（２）において、MAX（Ａ，Ｂ）は、ＡまたはＢのうち、いずれか大きい値をとることを示している。また、INT（A）は、値Aの小数点以下を切り捨てた値をとることを示している。さらに、ｋは、解像度レベル(k)（Level）を示すものであり、ｋは、le≦k≦Lの整数である。すなわち、解像度レベル(L)の画像は、最低解像度の画像であり、解像度レベル(le)の画像は、最高解像度の画像である。従って、Sb[0]は、入力画像（解像度レベル(0)の画像）に対するマッチングブロックサイズである。
【００８６】
ステップＳ４２において、探索範囲設定部３３ｂは、多重解像度画像バッファ３２−２に記憶されている最低解像度の画像（直前の画像）上の注目画素pbに対応する、多重解像度画像バッファ３２−１に記憶されている最低解像度の画像（今現在の画像）上の未処理の探索範囲を設定する。ここで、探索範囲サイズは、例えば、Ss[k]×Ss[k]である。ここで、Ss[k]は、以下の式（３）で示される。
【００８７】
【数３】
2008053875.tif 000005
【００８８】
従って、Ss[0]は、入力画像（解像度レベル(0)の画像）に対する探索範囲サイズである。
【００８９】
ステップＳ４３において、探索範囲設定部３３ｂは、探索範囲内における未処理の対応点画素pfを今現在の画像上に設定する。
【００９０】
ステップＳ４４において、マッチングブロック設定部３３ａは、対応点画素pfに対応する、多重解像度画像バッファ３２−１に記憶されている最低解像度の画像（現在の画像）マッチングブロックを構成する画素群を抽出し、評価計算部３３ｃに供給する。
【００９１】
ステップＳ４５において、評価計算部３３ｃは、マッチングブロック設定部３３ａより供給されてきた、直前の最低解像度の画像上の注目画素pbに対応するマッチングブロックを構成する画素群と、現在の最低解像度の画像上の対応点画素pfに対応するマッチングブロックを構成する画素群とを用いて、以下の式（４）を計算することにより、注目画素pbと対応点画素pfとの評価値e（Pb，Pf）を計算する。
【００９２】
【数４】
2008053875.tif 000006
【００９３】
【数５】
2008053875.tif 000007
【００９４】
ここでROIはマッチングブロックの範囲を示す。また、ｄは、マッチングブロックを構成する各画素の注目画素pbまたは対応点画素pfからの距離を示している。さらに、Cb（），Cf（）は、それぞれ注目画素pbまたは対応点画素pfを中心としたマッチングブロックを構成する画素の輝度を示している。また、式（４）における関数g（x，σ）は、式（５）で示される関数であり、図１０で示されるように、変数ｘに対して0付近で強度が大きく、０から離れるに従って急激に小さくなる、いわゆるガウス関数である。従って、g（x，σd）は、画素間の距離に関するガウス関数であり、g（x，σI）は、画素間の輝度差に関するガウス関数である。
【００９５】
すなわち、式（４）は2乗誤差によって非類似度を測る方式を基礎に据え、式（５）を利用することにより、マッチングブロックの中心画素からの距離が遠く、輝度差が大きい、画素間の評価寄与度を下げるように働く。つまり、マッチングブロックの中心位置に存在する画素（＝注目画素pbまたは対応点画素pf）同士のマッチングを最大限に重視しつつ、大きすぎる色の差は無視するように働く。σd, σIによってこれらの具合を調整することができる。
【００９６】
結果として、式（４）により計算される評価値eは、完全に一致するパターン同士の評価値が最小である０となり、比べたいマッチングブロック同士で多少の画像変形（拡大、縮小、回転、歪）が起きていても画素同士のマッチングはうまく行きやすく、ノイズ、エッジ、または異なる背景パターンは、ほぼ無視することができるといった特徴を備えている。
【００９７】
ステップＳ４６において、探索範囲設定部３３ｂは、探索範囲内における全ての対応点画素pfについて、注目画素pbとの評価値ｅが計算されたか否かを判定する。ステップＳ４６において、全ての対応点画素pfについて、注目画素pbとの評価値eが計算されていないと判定された場合、処理は、ステップＳ４３に戻る。すなわち、探索範囲内における全ての対応点画素pfについて、注目画素pbとの評価値ｅが計算されるまで、ステップＳ４３乃至Ｓ４６の処理が繰り返される。
【００９８】
そして、ステップＳ４６において、探索範囲内における全ての対応点画素pfについて、注目画素pbとの評価値ｅが計算されたと判定された場合、処理は、ステップＳ４７に進む。
【００９９】
ステップＳ４７において、探索範囲設定部３３ｂは、注目画素pbについて未処理の探索範囲が存在するか否かを判定し、未処理の探索範囲が存在する場合、処理は、ステップＳ４２に戻り、未処理の探索範囲がなくなるまで、ステップＳ４２乃至Ｓ４７の処理が繰り返される。
【０１００】
ステップＳ４７において、未処理の探索範囲が存在しないと判定された場合、ステップＳ４８において、対応点決定部３３ｄは、評価値ｅが最小となる注目画素pbおよび対応点画素pfとの組み合わせを検索し、その対応点画素pfを注目画素pbの対応点、すなわち、動きベクトルVL＝P[L](pb)として、対応点動きベクトルバッファ３４に記憶させる。
【０１０１】
ステップＳ４９において、マッチングブロック設定部３３ａは、未処理の注目画素が存在するか否かを判定し、未処理の注目画素が存在する場合、処理は、ステップＳ４１に戻る。すなわち、最低解像度の全ての画素について、対応点が求められるまで、ステップＳ４１乃至Ｓ４９の処理が繰り返され、ステップＳ４９において、直前の最低解像度の画像の全ての画素について対応点が求められた場合、すなわち、直前の最低解像度の画像の全ての画素について動きベクトルが求められた場合、処理は終了する。尚、処理が終了される際、動きベクトル出力判定部３５は、解像度レベルが最高解像度ではないとき、対応点動きベクトルバッファ３４の情報を初期値動きベクトルバッファ３６に転送する。
【０１０２】
以上の処理により、直前の画像における各画素が順次注目画素として設定され、画像全体をカバーするように探索範囲が設定され、マッチングブロックを順次移動させながらブロックマッチングが繰り返されことにより、最低解像度の画像の各画素について、対応点、すなわち、始点を各画素としたときの動きベクトルの終点が求められ、対応点動きベクトルバッファ３４に記憶される。この際、画像全体に対して探索範囲が順次設定されても、解像度が十分に低いので、対応点は、高速に求められることになる。
【０１０３】
ここで、図６のフローチャートの説明に戻る。
【０１０４】
ステップＳ２４において、最低解像度対応点抽出処理により最低解像度の画像における各画素の対応点が求められると、ステップＳ２５において、対応点探索部３３は、順次対応点抽出処理を実行し、最低解像度の画像における対応点を用いて、順次高い解像度の画像における対応点を探索していく。
【０１０５】
ここで、図１１のフローチャートを参照して、順次対応点抽出処理について説明する。
【０１０６】
ステップＳ６１において、マッチングブロック設定部３３ａは、解像度レベル(k)を示す図示せぬカウンタkを（L−１）に設定する。尚、ｋは、上述したように、le≦k≦Lの整数である。
【０１０７】
ステップＳ６２において、マッチングブロック設定部３３ａは、多重解像度画像バッファ３２−２に記憶されている、直前の画像における解像度レベル(k)の画像のうち、未処理の画素を注目画素pbとして設定すると供に、注目画素pbに対応するマッチングブロックを構成する画素群を抽出し、評価計算部３３ｃに供給する。マッチングブロック設定部３３ａにより設定されるマッチングブロックのサイズは、例えば、Sb[k]×Sb[k]である。ここで、Sb[k]は、以下の式（６）で示される。
【０１０８】
【数６】
2008053875.tif 000008
【０１０９】
ステップＳ６３において、初期対応点決定部３３ｅは、解像度レベル（k+1）の画像における対応点の情報を利用して、解像度レベル(k)の注目画素pbに対応する初期対応点Q[k](pb)を設定し、設定した初期対応点Q[k](pb)の情報を探索範囲設定部３３ｂに供給する。
【０１１０】
より詳細には、図１２で示されるように、初期対応点決定部３３ｅは、解像度レベル(k)の注目画素pbの座標（x[k]，y[k]）を、解像度レベル(k+1)の画像空間における座標（x[k+1]，y[k+1]）に変換することにより、対応する解像度レベル(k+1)の画像上の注目画素pb’の座標（x[k+1]，y[k+1]）を求める。図１２においては、解像度レベル(k)の画像上の画素p1が、注目画素pbに設定されており、注目画素pbに対応する、解像度レベル(k+1)の画像上の画素が画素pb’に設定されており、解像度レベル(k+1)の画像上の座標で表現されている。
【０１１１】
次に、初期値動きベクトルバッファ３６には、解像度レベル(k+1)の画像上の各画素について対応点が求められているので、初期対応点決定部３３ｅは、画素pb’の近傍に存在する、解像度レベル(k+1)の画像上の４画素の対応点を用いて、4近傍双一次補間処理により近似対応点P[k+1](pb’)を求める。すなわち、図１２においては、水平方向、または、垂直方向の1次元の配置のみが示されているので、画素pb’の近傍の画素としては、画素p0，p1のみが示されているが、さらに2画素が近傍に存在する。ここでは、画素pb’の近傍の画素として画素p0，p1の他に、画素pA，pB（図示せず）が存在するものとすると、初期対応点決定部３３ｅは、それらの対応点P[k+1](p0)，P[k+1](p1)，P[k+1](pA)，P[k+1](pB)を用いて、4近傍双一次補間処理により近似対応点P[k+1](pb’)（＝P[k+1](p0)・｛1−α｝｛1−β｝＋P[k+1](p1)・α｛1−β｝+P[k+1](pA)・｛1−α｝β+P[k+1](pB)・αβ（α（０≦α≦１）は、それぞれ画素p1，p2間の近似対応点P[k+1](pb’)の位置する空間的な比率、β（０≦β≦１）は、画素pA，pB間の近似対応点P[k+1](pb’)の位置する空間的な比率））を求める。さらに、初期対応点決定部３３ｅは、その近似対応点P[k+1](pb’)の座標を、解像度レベル（k+1）の画像における座標から、解像度レベル（k）の画像における座標に変換することで、初期対応点Q[k](pb)を求める。
【０１１２】
尚、解像度レベル（k），（k+1）間の座標変換は、カウンタｋが０より大きい場合、すなわち、入力画像よりも低解像度の場合、以下の式（７）のように変換され、カウンタｋが０より小さい場合、以下の式（８）のように変換される。
【０１１３】
【数７】
2008053875.tif 000009
【０１１４】
【数８】
2008053875.tif 000010
【０１１５】
ステップＳ６４において、探索範囲設定部３３ｂは、多重解像度画像バッファ３２−２に記憶されている解像度レベル(k)の画像（直前の画像）上の注目画素pbに対応する多重解像度画像バッファ３２−１に記憶されている解像度レベル(k)の画像（今現在の画像）上の、初期対応点Q[k](pb)に対応した探索範囲（例えば、初期対応点Q[k](pb)を中心とした探索範囲）を設定する。ここで、探索範囲サイズは、例えば、Ss[k]×Ss[k]である。ここで、Ss[k]は、以下の式（９）で示される。
【０１１６】
【数９】
2008053875.tif 000011
【０１１７】
ステップＳ６５において、探索範囲設定部３３ｂは、探索範囲内における未処理の対応点画素pfを今現在の画像上に設定する。
【０１１８】
ステップＳ６６において、マッチングブロック設定部３３ａは、対応点画素pfに対応する、多重解像度画像バッファ３２−１に記憶されている解像度レベル(k)の画像（現在の画像）におけるマッチングブロックを構成する画素群を抽出し、評価計算部３３ｃに供給する。
【０１１９】
ステップＳ６７において、評価計算部３３ｃは、マッチングブロック設定部３３ａより供給されてきた、直前の解像度レベル(k)の画像上の注目画素pbに対応するマッチングブロックを構成する画素群と、現在の解像度レベル(k)の画像上の対応点画素pfに対応するマッチングブロックを構成する画素群とを用いて、上述の式（４）を計算することにより、注目画素pbと対応点画素pfとの評価値e（Pb，Pf）を計算する。
【０１２０】
ステップＳ６８において、探索範囲設定部３３ｂは、探索範囲内における全ての対応点画素pfについて、注目画素pbとの評価値ｅが計算されたか否かを判定する。ステップＳ６８において、全ての対応点画素pfについて、注目画素pbとの評価値eが計算されていないと判定された場合、処理は、ステップＳ６６に戻る。すなわち、探索範囲内における全ての対応点画素pfについて、注目画素pbとの評価値ｅが計算されるまで、ステップＳ６６乃至Ｓ６８の処理が繰り返される。
【０１２１】
そして、ステップＳ６８において、探索範囲内における全ての対応点画素pfについて、注目画素pbとの評価値ｅが計算されたと判定された場合、処理は、ステップＳ６９に進む。
【０１２２】
ステップＳ６９において、対応点決定部３３ｄは、評価値ｅが最小となる注目画素pbおよび対応点画素pfとの組み合わせを検索し、その対応点画素pfを注目画素pbの対応点、すなわち、動きベクトルVk＝P[k](pb)として、対応点動きベクトルバッファ３４に記憶させる。
【０１２３】
ステップＳ７０において、マッチングブロック設定部３３ａは、未処理の注目画素が存在するか否かを判定し、未処理の注目画素が存在する場合、処理は、ステップＳ６２に戻る。すなわち、解像度レベル(k)の画像の全ての画素について、対応点が求められるまで、ステップＳ６２乃至Ｓ７０の処理が繰り返され、ステップＳ７０において、直前の解像度レベル(k)の画像の全ての画素について対応点が求められた場合、すなわち、直前の解像度レベル(k)の画像の全ての画素について動きベクトルが求められた場合、処理は、ステップＳ７１に進む。
【０１２４】
ステップＳ７１において、マッチングブロック設定部３３ａは、解像度レベルを示す図示せぬカウンタkが最小値であるか否かを判定し、最小値ではない、すなわち、さらに、解像度の高い画像が存在すると判定された場合、ステップＳ７２において、カウンタkを１デクリメントし、処理は、ステップＳ６２に戻り、それ以降の処理が繰り返される。すなわち、解像度レベル(L-1)乃至(le)までの解像度レベル（k+1）で求められた対応点の情報を利用することにより、さらに、１レベル分上位の解像度レベルkの画像における各画素の対応点を求める処理が順次繰り返される。尚、このとき、動きベクトル出力判定部３５は、対応点動きベクトルバッファ３４の情報を初期値動きベクトルバッファ３６に転送する。
【０１２５】
一方、ステップＳ７１において、カウンタkが最小値であると判定された場合、すなわち、最高解像度レベルより１レベル低解像度の画像における各画素の対応点が求められた場合、処理は、終了する。
【０１２６】
以上の処理により、解像度レベルの高い、低解像度の画像より、直前の画像における各画素が順次注目画素として設定され、直前の解像度レベルの画像における対応点に基づいて設定される初期対応点にのみ探索範囲が設定され、マッチングブロックを順次移動させながらブロックマッチングが繰り返されことにより、各解像度レベルの画像の各画素について、対応点、すなわち、始点を各画素としたときの動きベクトルの終点が求められ、対応点動きベクトルバッファ３４に記憶される。そして、この処理が、最高解像度の１レベル低解像度の解像度レベル(le)の画像にまで、繰り返される。
【０１２７】
結果として、探索範囲を初期対応点の近傍付近のみとすることが可能となるため、各解像度レベルの画像の各画素について、探索範囲を1回設定するのみでよいので、マッチングブロックの移動回数を低減させる事が可能となる。結果として、対応点の探索に必要な評価値の計算回数を低減することが可能となる。さらに、異なる解像度レベルで同様の処理を繰り返すことにはなるが、解像度レベルに関わらず、探索範囲を1回設定するだけでよいため、所望とする解像度レベルの画像において、動きベクトルの終点である対応点を高速で、かつ、安定的に探索することが可能となる。
【０１２８】
ここで、図６のフローチャートの説明に戻る。
【０１２９】
ステップＳ２５において、順次対応点抽出処理により、最高解像度の解像度レベル（le）の画像における各画素の対応点P[le](p)が求められることになる。
【０１３０】
ステップＳ２６において、動きベクトル生成部３７は、解像度レベル(le)の各画素における対応点を利用して、動きベクトル生成処理により最終的に動きベクトルを生成し、動きベクトルバッファ１３に記憶させて、処理を終了する。
【０１３１】
ここで、図１３のフローチャートを参照して、動きベクトル生成処理について説明する。
【０１３２】
ステップＳ９１において、動きベクトル生成部３７は、最高解像度である解像度レベル(le)の画像上の未処理の画素より注目画素pを設定する。
【０１３３】
ステップＳ９２において、動きベクトル生成部３７は、対応点動きベクトルバッファ３４に記憶されている、注目画素pの対応点P[le](p)を読み出し、ステップＳ９３において、動きベクトルの終点である対応点から始点である注目画素を用いて、以下の式（１０）を計算することにより、動きベクトルV(p)を生成する。
【０１３４】
【数１０】
2008053875.tif 000012
【０１３５】
ステップＳ９４において、動きベクトル生成部３７は、生成した注目画素pにおける動きベクトルV(p)を動きベクトルバッファ１３に記憶させる。
【０１３６】
ステップＳ９５において、動きベクトル生成部３７は、未処理の画素があるか否かを判定し、未処理の画素が存在すると判定した場合、処理は、ステップＳ９１に戻り、未処理の画素がなくなるまで、ステップＳ９１乃至Ｓ９５の処理を繰り返す。そして、ステップＳ９５において、未処理の画素が存在しない、すなわち、全ての画素について動きベクトルが生成されたと判定された場合、処理は終了する。
【０１３７】
以上の処理により、低解像度の解像度レベルの画像より順次、直前の対応点の情報に基づいて、初期対応点を求め、その初期対応点近傍のみをマッチングブロックの探索範囲として設定することが可能となるので、高速で、かつ、安定的に動きベクトルを検出することが可能となる。尚、より高解像度の画像について、動きベクトルが必要である場合、さらに、多重解像度化部３１により高解像度の画像を生成し、解像度レベル（le）を低くするように変化させるようにしてもよい。
【０１３８】
ここで、図５のフローチャートの説明に戻る。
【０１３９】
ステップＳ３において、手ぶれ補正部１４は、動きベクトルバッファ１３に格納されている各画素の動きベクトルの情報を読み出し、画像バッファ１１より読み出した画像の各画素について、動きベクトルと逆方向の位置に画素を移動させるようにすることで、画像に生じた手ぶれを補正して、出力する。
【０１４０】
ステップＳ４において、手ぶれ補正部１４は、画像バッファ１１に、次の画像が供給されてきたか否かを判定し、次の画像が供給されてきた場合、処理は、ステップＳ１に戻り、手ぶれを補正する処理が順次繰り返す。そして、ステップＳ４において、次の画像が供給されてきていないと判定された場合、処理は、終了する。
【０１４１】
以上の処理により、手ぶれの発生しているような画像であっても、上述した手法により、各画素について高速で動きベクトルが求められるので、動きベクトルに基づいて、手ぶれを補正して出力することが可能となる。
【０１４２】
以上においては、繰り返し計算により対応点の精度を向上させるものであったが、例えば、パラメータフィッティングにより１回の計算で対応点を精度良く求めることもできる。
【０１４３】
図１４は、パラメータフィッティングにより１回の計算で対応点を精度良く求めるようにした動きベクトル検出部１２の構成を示している。尚、図１４において、図４と同様の構成については、同一の符号を付しており、その説明は適宜省略するものとする。
【０１４４】
図１４において、図４と異なるのは、フィッティング計算部６１および動きベクトル生成部６２が設けられている点である。フィッティング計算部６１は、２次関数により解像度レベルが１レベル下位の複数の画素を用いて解析的に対応点の位置を計算する。動きベクトル生成部６２は、フィッティング計算部６１より供給されてくる対応点に基づいて動きベクトルを生成する。
【０１４５】
図１４の動きベクトル検出部１２を用いた手ぶれ補正処理について説明するが、図６のフローチャートにおけるステップＳ２６の動きベクトル生成処理を除いて、図４の動きベクトル検出部１２を用いた場合と同様であるので、図１４の動きベクトル検出部１２における動きベクトル生成処理のみを説明し、その他の処理は同様であるので、その説明は省略するものとする。
【０１４６】
まず、５点の近傍の画素値を用いたフィッティング計算を行う例について、図１５のフローチャートを参照して説明する。
【０１４７】
ステップＳ１１１において、フィッティング計算部６１は、未処理の画素より注目画素ｐを設定する。
【０１４８】
ステップＳ１１２において、フィッティング計算部６１は、注目画素ｐ[k]の初期対応点Q[k](p)を求める。すなわち、例えば、解像度レベル(le)については、le＝１とし、動きベクトルを最終的に求める画像の解像度が、解像度レベル(0)、すなわち、入力画像の各画素における動きベクトルを求めるものとすれば、図１２で示した方法と同様の手法により、フィッティング計算部６１は、注目画素pから解像度レベルが1レベル上位の画素p’を求め、画素p’の対応点である画素P[1](p’)を求め、さらに、対応点画素P[1](p’)を座標変換により、解像度レベル(0)での対応点画素P[0](p)の初期対応点Q[0](p)を求める。
【０１４９】
ステップＳ１１３において、フィッティング計算部６１は、図１６で示されるように、解像度レベル(0)において、Q[0](p)に最も近い画素の画素中心q[0]とその周りの画素の画素中心４点、すなわちq[i]：{i=0,1,3,5,7}の計5点で式（４）の評価値e[i]：{i=0,1,3,5,7}を計算する。
【０１５０】
ステップＳ１１４において、フィッティング計算部６１は、初期対応点Q[0](p)の近傍の５画素の評価値e[i]：{i=0,1,3,5,7}を、以下の式（１１）で示される関係式に代入し、加算ベクトル（s，t）を求め、さらに、初期対応点Q[0](p)に最も近い画素q[0]にベクトル加算し、対応点P[0](p)を計算し、動きベクトル生成部６２に供給する。
【０１５１】
【数１１】
2008053875.tif 000013
【０１５２】
ここで、ｓ，ｔは、図１６で示されるように、初期対応点Q[0](p)に最も近い画素q[0]を中心とした空間の軸である。また、st空間内の位置に応じた評価値の関係は、例えば、以下の式（１２）の近似関数F(q)＝f(s,t)により表現することができる。
【０１５３】
【数１２】
2008053875.tif 000014
【０１５４】
ここで、a，b，c，d，α，βは、パラメータである。
【０１５５】
そこで、式（１２）で示される近似関数F(q)＝f(s,t)に、評価値e[i]：{i=0,1,3,5,7}を、それぞれのst空間上の座標と供に代入すると、以下の式（１３）で示される５個の関係式が得られる。
【０１５６】
【数１３】
2008053875.tif 000015
【０１５７】
さらに、パラメータのうちαが０であると仮定すれば、パラメータｓ，ｔのそれぞれについて、偏微分すると、以下の式（１４），式（１５）で示されるような連立方程式となり、これを解くことにより、近似関数ｆを最小にする（ｓ，ｔ）が式（１１）となる。
【０１５８】
【数１４】
2008053875.tif 000016
【０１５９】
【数１５】
2008053875.tif 000017
【０１６０】
ステップＳ１１５において、動きベクトル生成部６２は、動きベクトルの終点である対応点から始点である注目画素を用いて、上述した式（１０）を計算することにより、動きベクトルV(p)を生成する。
【０１６１】
ステップＳ１１６において、動きベクトル生成部６２は、生成した注目画素pにおける動きベクトルV(p)を動きベクトルバッファ１３に記憶させる。
【０１６２】
ステップＳ１１７において、動きベクトル生成部６２は、未処理の画素があるか否かを判定し、未処理の画素が存在すると判定した場合、処理は、ステップＳ１１１に戻り、未処理の画素がなくなるまで、ステップＳ１１１乃至Ｓ１１７の処理を繰り返す。そして、ステップＳ１１７において、未処理の画素が存在しない、すなわち、全ての画素について動きベクトルが生成されたと判定された場合、処理は終了する。
【０１６３】
以上の処理により、たかだか5点の評価値を求めるだけで、繰り返し計算ではなく1回の計算で高精度な動きベクトルを求めることができる。また、オリジナル解像度以上の画像はピラミッド中に必要としないので、多重解像度画像バッファ３２−１，３２−２の容量を節約することが可能となる。
【０１６４】
また、以上においては、５点を用いたフィッティングの例であるが、それ以上の画素に対応する評価値を用いるようにしてもよく、例えば、９点によるフィッティングを行うようにしても良い。
【０１６５】
図１７は、９点の画素によるフィッティングを用いた動きベクトル生成処理を説明するフローチャートである。尚、図１７におけるステップＳ１３１，Ｓ１３２、およびＳ１３５乃至Ｓ１３７の処理については、図１５におけるステップＳ１１１，Ｓ１１２、およびＳ１１５乃至Ｓ１１７の処理と同様であるので、その説明は省略する。
【０１６６】
すなわち、ステップＳ１３３において、フィッティング計算部６１は、図１６で示されるように、解像度レベル(0)において、Q[0](p)に最も近い画素の画素中心q[0]とその周りの画素の画素中心８点、すなわちq[i]：{i=0乃至8}の計９点で式（４）の評価値e[i]：{i=0乃至8}を計算する。
【０１６７】
ステップＳ１３４において、フィッティング計算部６１は、初期対応点Q[0](p)の近傍の９画素の評価値e[i]：{i=0乃至8}を、以下の式（１６）で示される関係式に代入し、加算ベクトル（s，t）を求め、さらに、初期対応点Q[0](p)に最も近い画素q[0]にベクトル加算し、対応点P[0](p)を計算し、動きベクトル生成部６２に供給する。
【０１６８】
【数１６】
2008053875.tif 000018
【０１６９】
すなわち、式（１６）は、上述したように、5点を用いた方法でa，b，c，d，βは、αをパラメータとした値として表現するものとすれば、新たな画素q[i]：{i=2,4,6,8}の4点に関して、式（１２）の近似関数F(q)＝f(s,t)と評価値eとの間の差が最も小さくなるよう、最小二乗法によりf(s,t)のパラメータαを決定して、fの最小値をとる座標を一回の計算で決定できるようにしたものである。尚、式（１６）については、パラメータa，b，c，d，αは、それぞれ（e[1]＋e[5]−2e[0]）/2，（e[1]−e[5]）/2，（e[3]＋e[7]）/2，（e[3]＋e[7]−2e[0]）/2，（e[2]−e[4]＋e[6]−e[8]）/4である。
【０１７０】
新たな画素q[i]：{i=2,4,6,8}の4点に関する評価値eは、以下の式（１７）により表現される。
【０１７１】
【数１７】
2008053875.tif 000019
【０１７２】
さらに、式（１７）は、図１６で示されるst空間における座標系で表現すれば、以下の式（１８）により表現されることになる。
【０１７３】
【数１８】
2008053875.tif 000020
【０１７４】
このような場合、以下の式（１９）で示されるように、真値であるF(q[i])：{i=2,4,6,8}とサンプル値である評価値e[i]：{i=2,4,6,8}との誤差二乗和Eを定義すれば、パラメータαは、誤差二乗和Eを最小とするときの値となる。
【０１７５】
【数１９】
2008053875.tif 000021
【０１７６】
式（１９）で示される誤差二乗和Eが最小となるのは、以下の式（２０）で示されるように、αにより偏微分した関数が０となる条件を満たしたときとなる。
【０１７７】
【数２０】
2008053875.tif 000022
【０１７８】
この条件に従って、式（１９）を解くと、以下の式（２１）で示されるように、αが求められる。
【０１７９】
【数２１】
2008053875.tif 000023
【０１８０】
以上の処理により、全てのパラメータが決定されることにより、以下の式（２２），式（２３）で示されるように、関数F(q)=f(s,t)をそれぞれs,tで偏微分した値を０とすれば、式（１６）を求めることができる。
【０１８１】
【数２２】
2008053875.tif 000024
【０１８２】
【数２３】
2008053875.tif 000025
【０１８３】
以上の処理により、9点の評価値を求めるだけで、繰り返し計算ではなく1回の計算により、より高精度な動きベクトルを求めることが可能となる。なお、図１５，図１７のフローチャートを参照して説明した図１４の動きベクトル検出部１２の処理は、説明の例として解像度レベル（le）がle=1のときを述べたが、メモリの制約や動きベクトル保持方法などが変われば、leは１以外の値でも良い。
【０１８４】
また、これまで述べた方法は動きベクトル画像を過去から未来への変化として一方向にしか考えなかったが、２つの入力画像を入れ替えれば同様の処理で未来から過去のへの動きベクトルも生成できる。
【０１８５】
以上のような処理により、ロバストかつ高精度な動きベクトルの検出を高速で実現することが可能となる。
【０１８６】
本発明によれば、特に条件の悪い画像群を用いた、画像圧縮、映像特殊効果、静止画像/フレーム高画質化、動画性向上、物体追跡など、動きベクトルや対応点探索を利用した様々な画像処理における精度と処理速度を向上させることが可能となる。
【０１８７】
ところで、上述した一連の画像処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０１８８】
図１８は、汎用のパーソナルコンピュータの構成例を示している。このパーソナルコンピュータは、CPU(Central Processing Unit)１００１を内蔵している。CPU１００１にはバス１００４を介して、入出力インタフェース１００５が接続されている。バス１００４には、ROM(Read Only Memory)１００２およびRAM(Random Access Memory)１００３が接続されている。
【０１８９】
入出力インタフェース１００５には、ユーザが操作コマンドを入力するキーボード、マウスなどの入力デバイスよりなる入力部１００６、処理操作画面や処理結果の画像を表示デバイスに出力する出力部１００７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部１００８、LAN（Local Area Network）アダプタなどよりなり、インターネットに代表されるネットワークを介した通信処理を実行する通信部１００９が接続されている。また、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory)、DVD(Digital Versatile Disc)を含む）、光磁気ディスク（ＭＤ(Mini Disc)を含む）、もしくは半導体メモリなどのリムーバブルメディア１０１１に対してデータを読み書きするドライブ１０１０が接続されている。
【０１９０】
CPU１００１は、ROM１００２に記憶されているプログラム、または磁気ディスク、光ディスク、光磁気ディスク、もしくは半導体メモリ等のリムーバブルメディア１０１１から読み出されて記憶部１００８にインストールされ、記憶部１００８からRAM１００３にロードされたプログラムに従って各種の処理を実行する。RAM１００３にはまた、CPU１００１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１９１】
尚、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理は、もちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理を含むものである。
【０１９２】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【図面の簡単な説明】
【０１９３】
【図１】従来の動きベクトルの求め方を説明する図である。
【図２】従来の動きベクトルの求め方を説明する図である。
【図３】本発明を適用した手ぶれ補正処理装置の構成例について説明するブロック図である。
【図４】図３の動きベクトル検出部の構成例を説明するブロック図である。
【図５】図３の手ぶれ補正処理装置による手ぶれ補正処理を説明するフローチャートである。
【図６】図４の動きベクトル検出部による動きベクトル検出処理を説明するフローチャートである。
【図７】多重解像度化部による低解像度化の多重解像度化処理を説明する図である。
【図８】多重解像度化部による高解像度化の多重解像度化処理を説明する図である。
【図９】図４の動きベクトル検出部による最低解像度対応点抽出処理を説明するフローチャートである。
【図１０】ガウス関数を説明する図である。
【図１１】図４の動きベクトル検出部による順次対応点抽出処理を説明するフローチャートである。
【図１２】初期対応点の設定方法を説明する図である。
【図１３】図４の動きベクトル検出部による動きベクトル生成処理を説明するフローチャートである。
【図１４】図３の動きベクトル検出部のその他の構成例を説明するブロック図である。
【図１５】図１４の動きベクトル検出部による動きベクトル生成処理を説明するフローチャートである。
【図１６】図１４の動きベクトル検出部による動きベクトル生成処理を説明する図である。
【図１７】図１４の動きベクトル検出部によるその他の動きベクトル生成処理を説明するフローチャートである。
【図１８】パーソナルコンピュータの構成例を説明する図である。
【符号の説明】
【０１９４】
３１  多重解像度化部，  ３１ａ  像度化部，  ３１ｂ  像度化部，  ３２，３２−１，３２−２  多重解像度画像バッファ，  ３３          対応点探索部，  ３３ａ  マッチングブロック設定部，  ３３ｂ  探索範囲設定部，  ３３ｃ  評価計算部，  ３３ｄ  対応点決定部，  ３３ｅ  初期対応点決定部３３ｅ，  ３４  対応点動きベクトルバッファ，  ３５  動きベクトル出力判定部，  ３６  初期値動きベクトルバッファ，  ３７  動きベクトル生成部
【図１】
2008053875.tif 000026
【図２】
2008053875.tif 000027
【図３】
2008053875.tif 000028
【図４】
2008053875.tif 000029
【図５】
2008053875.tif 000030
【図６】
2008053875.tif 000031
【図７】
2008053875.tif 000032
【図８】
2008053875.tif 000033
【図９】
2008053875.tif 000034
【図１０】
2008053875.tif 000035
【図１１】
2008053875.tif 000036
【図１２】
2008053875.tif 000037
【図１３】
2008053875.tif 000038
【図１４】
2008053875.tif 000039
【図１５】
2008053875.tif 000040
【図１６】
2008053875.tif 000041
【図１７】
2008053875.tif 000042
【図１８】
2008053875.tif 000043