(57)【要約】【課題】抽出する候補ベクトルの精度を向上させることで、動きベクトルの検出精度を向上させることができるようにする。【解決手段】評価値テーブル生成部６２は、代表点メモリ６１に記憶された基準画像のなかの複数の代表点を用いた代表点マッチング法により評価値テーブルを生成する。ピーク検出部６３は、評価値テーブルの度数の最大値に対応する位置を動きベクトルの候補ベクトルとして検出する。相関判定部６４は、基準画像の代表点と、それに対応する参照画像の参照点との相関判定を行い、相関の高い代表点を代表点メモリ６１から除外することにより、代表点メモリ６１を更新する。評価値テーブルの生成、候補ベクトルの検出、並びに、代表点と参照点との相関判定およびその判定結果による代表点メモリ６１の更新は、有意な候補ベクトルが存在すると判定される限り繰り返される。本発明は、例えば、動きベクトルを検出する画像処理装置に適用できる。【選択図】図７
2011141824.tif 000002
【特許請求の範囲】
【請求項１】
基準画像を参照画像と比較し、前記基準画像の各画素の動きベクトルを検出するために代表して動きベクトルを検出する代表点である前記基準画像の複数の画素それぞれを記憶する代表点記憶手段と、
前記代表点記憶手段に記憶された複数の代表点を用いた代表点マッチング法により評価値テーブルを生成する評価値テーブル生成手段と、
前記評価値テーブルの度数の最大値に対応する位置を前記動きベクトルの候補ベクトルとして検出するピーク検出手段と、
前記代表点記憶手段に記憶された複数の代表点について、前記基準画像の前記代表点と、それに対応する前記候補ベクトル先の前記参照画像の画素である参照点との相関判定を行い、相関の高い代表点を前記代表点記憶手段から除外することにより、前記代表点記憶手段を更新する相関判定手段と
を備え、
前記評価値テーブル生成手段による、前記代表点記憶手段に記憶された代表点に基づく前記評価値テーブルの生成、
前記ピーク検出手段による、前記候補ベクトルの検出、
前記相関判定手段による、前記代表点と前記参照点との相関判定およびその判定結果による前記代表点記憶手段の更新
を、有意な候補ベクトルが存在すると判定される限り繰り返す
画像処理装置。
【請求項２】
前記評価値テーブルの生成、前記候補ベクトルの検出、並びに、前記相関判定および前記代表点記憶手段の更新、の繰り返しを制御する制御手段をさらに備え、
前記制御手段は、前記評価値テーブルの度数の最大値に応じて、繰り返しを中止させる
請求項１に記載の画像処理装置。
【請求項３】
前記評価値テーブルの生成、前記候補ベクトルの検出、並びに、前記相関判定および前記代表点記憶手段の更新、の繰り返しを制御する制御手段をさらに備え、
前記制御手段は、前記代表点記憶手段に記憶されている代表点が更新された個数に応じて、繰り返しを中止させる
請求項１に記載の画像処理装置。
【請求項４】
前記相関判定手段は、前記代表点とその近傍の画素の代表点近傍画素データと、前記参照点とその近傍の画素の参照点近傍画素データを比較することにより、前記代表点と前記参照点との相関判定を行う
請求項２に記載の画像処理装置。
【請求項５】
前記相関判定手段は、前記代表点の画素値が前記参照点の近傍の画素の画素値に挟まれる関係にあるか、または、前記参照点の画素値が前記代表点の近傍の画素の画素値に挟まれる関係にあるという条件を満たすか否かにより、前記代表点と前記参照点との相関判定を行う
請求項４に記載の画像処理装置。
【請求項６】
前記相関判定手段は、前記代表点とその近傍の画素の画素値の波形パターンが、右上がり、右下がり、上に凸、下に凸の、いずれかを解析して、波形パターンに応じて異なる相関判定を行う
請求項５に記載の画像処理装置。
【請求項７】
近傍の画素と画素値の変化があるかを判別することにより、前記基準画像の画素のなかから前記代表点を決定し、前記代表点記憶手段に記憶させる代表点選別手段をさらに備える
請求項１に記載の画像処理装置。
【請求項８】
所定の画像処理を行う画像処理装置が、
代表点記憶手段に記憶されている代表点としての基準画像の複数の画素それぞれを参照画像と比較する代表点マッチング法により評価値テーブルを生成し、
前記評価値テーブルの度数の最大値に対応する位置を、前記基準画像と前記参照画像の動きベクトルの候補ベクトルとして検出し、
前記代表点記憶手段に記憶された複数の代表点について、前記基準画像の前記代表点と、それに対応する前記候補ベクトル先の前記参照画像の画素である参照点との相関判定を行い、相関の高い代表点を前記代表点記憶手段から除外することにより、前記代表点記憶手段を更新する処理を、
有意な候補ベクトルが存在すると判定される限り繰り返す
ステップを含む画像処理方法。
【請求項９】
コンピュータに、
代表点記憶手段に記憶されている代表点としての基準画像の複数の画素それぞれを参照画像と比較する代表点マッチング法により評価値テーブルを生成し、
前記評価値テーブルの度数の最大値に対応する位置を、前記基準画像と前記参照画像の動きベクトルの候補ベクトルとして検出し、
前記代表点記憶手段に記憶された複数の代表点について、前記基準画像の前記代表点と、それに対応する前記候補ベクトル先の前記参照画像の画素である参照点との相関判定を行い、相関の高い代表点を前記代表点記憶手段から除外することにより、前記代表点記憶手段を更新する処理を、
有意な候補ベクトルが存在すると判定される限り繰り返す
ステップを含む処理を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理方法、およびプログラムに関し、特に、抽出する候補ベクトルの精度を向上させることで、動きベクトルの検出精度を向上させることができるようにする画像処理装置、画像処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年の動画像の信号処理の発展に伴い、画像中の各物体の動きベクトルを検出する技術が、様々なところで利用されている。例えば、高能率符号化における動き補償型画像符号化、動画像のフレームレート変換、交通監視システムにおける動物体の検出処理や動き検出などに、動きベクトルを検出する技術が利用されている。ステレオカメラで撮影した画像からの動物体の検出や奥行き計測等には、複数視点の画像から視差ベクトルを検出する技術が利用されている。動画像の動きベクトルの検出と多視点画像の視差ベクトルの検出は、対応をとる画像間の関係が異なるだけであり、技術的には同じなので、単に、ベクトル検出と呼ぶことにする。
【０００３】
従来、ベクトル検出には、ブロックマッチング法などがよく用いられてきた。ブロックマッチング法は、サーチエリア内の全てのデータの比較を行う全探索であるため、検出に要する比較の回数が非常に多く、ベクトル検出に時間がかかるという欠点があった。
【０００４】
また、ブロック内に動き方向の異なる複数の部分が含まれるような場合、ブロックを単位として検出された動きは、ブロック内の個々の動きを正確に検出したものとは言えない。このような問題は、ブロックサイズの設定により調整可能であるが、例えば、ブロックを大きくすると、演算量の増大に加えて、ブロック内の複数動きの問題が発生し易くなる。逆に、ブロック内に複数の動きが含まれないように、ブロックのサイズを小さくした場合には、マッチングの判断の領域が小さくなるので、動き検出の精度が低下するという問題が生じる
【０００５】
そこで、本出願人は、特許文献１、特許文献２などにより、演算量を増大させずに、１画素毎に動きベクトル検出ができ、且つ、誤検出が防止された動きベクトル検出装置、および動きベクトル検出方法を提案している。
【０００６】
特許文献１，２における動きベクトル検出方法のポイントは、画素またはブロック毎に評価値を算出し、ベクトルを決定するのではなく、候補ベクトル方式の採用によって、従来の問題点を解決したことにある。候補ベクトル方式では、最初に、第１ステップとして、代表点マッチング法により１画面内で評価値テーブルを生成し、生成された評価値テーブルから、幾つかの候補ベクトルが抽出される。そして、第２ステップとして、抽出された候補ベクトルのなかから、１画素毎に最良と思われる候補ベクトルを選択することにより、画素毎の動きベクトルが決定される。
【０００７】
候補ベクトル方式によれば、サーチエリア内の有効な位置（候補ベクトルの位置）を第１ステップで抽出しておくことで、演算量を軽減することができる。また、ベクトルの誤検出が起こりやすい被写体の境界部分においても、予め絞りこんだ候補ベクトルの中から、最良のベクトルを判定するので、サーチエリア内の全探索に比べて、同じ評価値となる確率が減り、誤検出を軽減することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−１７５８６９号公報
【特許文献２】特開２００５−１７５８７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１，２における動きベクトル検出方法では、評価値テーブルから候補ベクトルを抽出する際、予め候補ベクトルの抽出個数を設定する必要があるため、次のような問題があった。
【００１０】
候補ベクトルの抽出個数として、画像内に存在する有意な候補ベクトル数より大きい値を設定すると、抽出した候補ベクトルの中に不必要な候補ベクトルが含まれる確率が増える。そのため、第２ステップの処理で最良と思われるベクトルを決定する際に誤検出の可能性が高まる。逆に、誤検出を減らすため、候補ベクトルの抽出個数を小さく設定すると、抽出された候補ベクトルの中に必要な候補ベクトルが含まれない確率が増える。この場合も、第２ステップの処理で最良と思われるベクトルを決定する際に誤検出となる可能性が高くなる。
【００１１】
即ち、最良な動きベクトルを決定するためには、第１ステップで抽出される候補ベクトルの精度が良いことが前提となる。しかしながら、設定した候補ベクトルの抽出個数によって不必要な候補ベクトルが含まれたり、必要な候補ベクトルが含まれないことにより、候補ベクトルの精度が低くなることがあった。
【００１２】
本発明は、このような状況に鑑みてなされたものであり、候補ベクトル方式において、抽出する候補ベクトルの精度を向上させることで、動きベクトルの検出精度を向上させることができるようにするものである。
【課題を解決するための手段】
【００１３】
本発明の一側面の画像処理装置は、基準画像を参照画像と比較し、前記基準画像の各画素の動きベクトルを検出するために代表して動きベクトルを検出する代表点である前記基準画像の複数の画素それぞれを記憶する代表点記憶手段と、前記代表点記憶手段に記憶された複数の代表点を用いた代表点マッチング法により評価値テーブルを生成する評価値テーブル生成手段と、前記評価値テーブルの度数の最大値に対応する位置を前記動きベクトルの候補ベクトルとして検出するピーク検出手段と、前記代表点記憶手段に記憶された複数の代表点について、前記基準画像の前記代表点と、それに対応する前記候補ベクトル先の前記参照画像の画素である参照点との相関判定を行い、相関の高い代表点を前記代表点記憶手段から除外することにより、前記代表点記憶手段を更新する相関判定手段とを備え、前記評価値テーブル生成手段による、前記代表点記憶手段に記憶された代表点に基づく前記評価値テーブルの生成、前記ピーク検出手段による、前記候補ベクトルの検出、前記相関判定手段による、前記代表点と前記参照点との相関判定およびその判定結果による前記代表点記憶手段の更新を、有意な候補ベクトルが存在すると判定される限り繰り返す。
【００１４】
本発明の一側面の画像処理方法は、所定の画像処理を行う画像処理装置が、代表点記憶手段に記憶されている代表点としての基準画像の複数の画素それぞれを参照画像と比較する代表点マッチング法により評価値テーブルを生成し、前記評価値テーブルの度数の最大値に対応する位置を、前記基準画像と前記参照画像の動きベクトルの候補ベクトルとして検出し、前記代表点記憶手段に記憶された複数の代表点について、前記基準画像の前記代表点と、それに対応する前記候補ベクトル先の前記参照画像の画素である参照点との相関判定を行い、相関の高い代表点を前記代表点記憶手段から除外することにより、前記代表点記憶手段を更新する処理を、有意な候補ベクトルが存在すると判定される限り繰り返す
ステップを含む。
【００１５】
本発明の一側面のプログラムは、コンピュータに、代表点記憶手段に記憶されている代表点としての基準画像の複数の画素それぞれを参照画像と比較する代表点マッチング法により評価値テーブルを生成し、前記評価値テーブルの度数の最大値に対応する位置を、前記基準画像と前記参照画像の動きベクトルの候補ベクトルとして検出し、前記代表点記憶手段に記憶された複数の代表点について、前記基準画像の前記代表点と、それに対応する前記候補ベクトル先の前記参照画像の画素である参照点との相関判定を行い、相関の高い代表点を前記代表点記憶手段から除外することにより、前記代表点記憶手段を更新する処理を、有意な候補ベクトルが存在すると判定される限り繰り返すステップを含む処理を実行させる。
【００１６】
本発明の一側面においては、代表点記憶手段に記憶されている代表点としての基準画像の複数の画素それぞれが、参照画像と比較される代表点マッチング法により評価値テーブルが生成され、評価値テーブルの度数の最大値に対応する位置が、基準画像と参照画像の動きベクトルの候補ベクトルとして検出され、代表点記憶手段に記憶された複数の代表点について、基準画像の代表点と、それに対応する候補ベクトル先の参照画像の画素である参照点との相関判定が行われ、相関の高い代表点が代表点記憶手段から除外されることにより、代表点記憶手段が更新される処理が、有意な候補ベクトルが存在すると判定される限り繰り返される。
【００１７】
なお、プログラムは、伝送媒体を介して伝送することにより、又は、記録媒体に記録して、提供することができる。
【００１８】
画像処理装置は、独立した装置であっても良いし、１つの装置を構成している内部ブロックであっても良い。
【発明の効果】
【００１９】
本発明の一側面によれば、抽出する候補ベクトルの精度を向上させることで、動きベクトルの検出精度を向上させることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明を適用した画像処理装置の一実施の形態の構成例を示すブロック図である。
【図２】画像処理装置１全体の処理を説明するフローチャートである。
【図３】代表点マッチング法による評価値テーブルの生成処理およびベクトル（ｕ，ｖ）の算出について説明する図である。
【図４】代表点マッチング法による評価値テーブルの生成処理およびベクトル（ｕ，ｖ）の算出について説明する図である。
【図５】空間勾配の有無を検出するために用いられる近傍画素を説明する図である。
【図６】代表点選別部の詳細構成例を示すブロック図である。
【図７】候補ベクトル抽出部の詳細な構成例を含む画像処理装置のブロック図である。
【図８】候補ベクトル抽出処理について説明するフローチャートである。
【図９】相関判定部の詳細な構成例を示すブロック図である。
【図１０】波形パターンの種類を示す図である。
【図１１】波形パターンが右上がりである場合の相関判定処理の詳細について説明する図である。
【図１２】波形パターンが右下がりである場合の相関判定処理の詳細について説明する図である。
【図１３】波形パターンが下に凸である場合の相関判定処理の詳細について説明する図である。
【図１４】波形パターンが上に凸である場合の相関判定処理の詳細について説明する図である。
【図１５】評価関数Ｆ１乃至Ｆ４をまとめて示した図である。
【図１６】相関判定処理を説明するフローチャートである。
【図１７】候補ベクトル割当処理の概念図を示す図である。
【図１８】候補ベクトル割当処理を説明するフローチャートである。
【図１９】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００２１】
［本発明を適用した画像処理装置のブロック図］
図１は、本発明を適用した画像処理装置の一実施の形態の構成例を示している。
【００２２】
画像処理装置１は、図１に示されるように、代表点選別部１１、候補ベクトル抽出部１２、制御部１３、および候補ベクトル割当部１４により構成される。
【００２３】
画像処理装置１には、複数の画像を構成する画像データが入力される。複数の画像は、例えば、動画像を構成する時間的に連続するフレーム画像や、異なる視点で撮像された複数枚のフレーム画像である。入力された画像データは、代表点選別部１１、候補ベクトル抽出部１２、および候補ベクトル割当部１４に供給される。
【００２４】
画像処理装置１は、入力される所定の２枚のフレーム画像の一方を基準フレーム（基準画像）、他方を参照フレーム（参照画像）として、基準フレームと参照フレームを比較して、基準フレームに含まれる画素の動きベクトルを検出し、ベクトルデータとして出力する。画像データとして、画像処理装置１に３枚以上のフレーム画像が入力される場合には、画像処理装置１は、順次入力されるフレーム画像に対し、動きベクトルの検出処理を繰り返し実行する。この場合、基準フレームは、固定の１枚のフレーム画像を基準フレームとしてもよいし、入力されるフレーム画像を順次、基準フレームとすることも可能である。
【００２５】
なお、以下の説明においては、入力される画像データがフレーム画像のデータであるとして説明するが、本発明は、フレーム画像に限らず、フィールド画像であっても適用可能である。また、入力される画像データは、テレビジョン信号に基づく画像データでもよいし、テレビジョン信号以外の様々な画像データでもよい。また、入力される画像データは、インターレースまたはノンインターレースの何れのデータでもよい。
【００２６】
代表点選別部１１は、入力される基準フレームを構成する各画素のなかから、動きベクトルを検出する対象として適切な１以上の画素を代表点として決定する。例えば、基準フレームに含まれる部分のうち、同じような画素値が隣接している平坦な部分の画素を代表点として決定した場合には、仮に、その部分に動きがあったとしても、その動き量が平坦な部分の範囲内であれば、その変化を検出することができない。従って、基準フレームに含まれる部分のうち、隣接する範囲内で画素値に変化のある部分、即ち、テクスチャのある部分の画素を代表点とする方が、動きベクトルをより正確に検出することができる。そこで、代表点選別部１１は、近傍の画素と画素値の変化があるかを判別することにより、動きベクトルを検出する対象として適切な１以上の画素を代表点として決定する。なお、代表点選別部１１は、所定の基準を満たす画素を、すべて代表点として決定し、個数の制限等は行わない。
【００２７】
代表点選別部１１は、基準フレームに対して決定した代表点を示す情報を、候補ベクトル抽出部１２に供給する。例えば、代表点選別部１１は、基準フレームを構成する各画素に対して、代表点であるか否かを示す ‘‘１’’または ‘‘０’’の情報を候補ベクトル抽出部１２に供給する。
【００２８】
なお、本実施の形態では、基準フレームを構成する全ての画素に対して、代表点であるか否かを示す ‘‘１’’または ‘‘０’’の情報を生成することとするが、基準フレームから抜き出した所定個数の画素のみについて代表点を示す情報を生成するようにしてもよい。
【００２９】
候補ベクトル抽出部１２は、制御部１３の制御にしたがい、画像処理装置１が出力する動きベクトルの候補となる候補ベクトルを抽出し、制御部１３に供給する。より詳しくは、候補ベクトル抽出部１２は、代表点選別部１１で決定された１以上の代表点を所定の順序で選択し、選択された代表点の動きベクトル（ｕ，ｖ）を算出する。そして、候補ベクトル抽出部１２は、算出された動きベクトル（ｕ，ｖ）を候補ベクトルとして制御部１３に供給する処理を、制御部１３から中止されるまで繰り返す。なお、以下において、候補ベクトル抽出部１２により算出される動きベクトル（ｕ，ｖ）を、画像処理装置１が出力する動きベクトルと区別するため、単に、ベクトル（ｕ，ｖ）と称する。
【００３０】
制御部１３は、候補ベクトル抽出部１２を制御するとともに、候補ベクトル抽出部１２から供給された候補ベクトルを、候補ベクトル割当部１４に供給する。
【００３１】
候補ベクトル割当部１４は、基準フレームの所定の画素を処理対象として注目する注目画素に設定し、注目画素の動きベクトルを、複数の候補ベクトルのなかから最適な候補ベクトルを割り当てることにより決定し、出力する。
【００３２】
候補ベクトル割当部１４が基準フレームのどの画素を注目画素とするかは、任意に決定することができる。例えば、候補ベクトル割当部１４は、基準フレームの各画素を注目画素として、各画素それぞれについて動きベクトルを決定するようにしてもよい。また、基準フレームを複数のブロックに分割し、ブロック内の１画素のみを注目画素としてもよい。ブロック内の１画素を注目画素とした場合、ブロック内の全画素の動きベクトルは、注目画素とした１画素と同一の動きベクトルとされる。
【００３３】
［画像処理装置１全体の処理フロー］
図２は、画像処理装置１全体の処理を示すフローチャートである。
【００３４】
画像処理装置１に、基準フレームと参照フレームを含む画像データが入力される。すると、ステップＳ１において、代表点選別部１１は、基準フレームを構成する各画素のなかから、動きベクトルを検出する対象として適切な１以上の画素を代表点として決定し、代表点を示す情報を、候補ベクトル抽出部１２に供給する。
【００３５】
ステップＳ２において、候補ベクトル抽出部１２は、代表点選別部１１で決定された１以上の代表点について、候補ベクトルを抽出し、制御部１３に供給する。候補ベクトル抽出部１２は、制御部１３から処理の中止が命令された場合、候補ベクトルの抽出処理を止めるので、代表点選別部１１で決定された代表点の全てについて、候補ベクトルが抽出されるわけではない。
【００３６】
ステップＳ３において、候補ベクトル割当部１４は、抽出された候補ベクトルを基に、基準フレームの全画素に対して動きベクトルを決定し、出力する。即ち、候補ベクトル割当部１４は、基準フレームを構成する画素それぞれに対して、抽出された複数の候補ベクトルのなかから最適な候補ベクトルを、その画素の動きベクトルとして決定し、出力する。
【００３７】
以上のように、画像処理装置１では、入力される基準フレームと参照フレームとから、基準フレームの各画素について、動きベクトルが検出され、ベクトルデータとして出力される。
【００３８】
［代表点マッチング法の説明］
画像処理装置１の処理は、［背景技術］に記載の特許文献１，２等で提案した候補ベクトル方式を改良したものである。そこで、画像処理装置１が実行する候補ベクトル方式のうち、特許文献１，２等で提案した候補ベクトル方式と同一の処理を行う部分について先に説明する。
【００３９】
図３と図４を参照して、代表点マッチング法による評価値テーブルの生成処理およびベクトル（ｕ，ｖ）の算出について説明する。
【００４０】
代表点マッチング法では、最初に、基準フレームの代表点に対応するサーチエリアが参照フレームに設定される。サーチエリアは、例えば、代表点に対応する参照フレームの画素を中心とするｐ画素×ｑ画素の領域（ｐ，ｑ＞０）とされる。
【００４１】
図３は、基準フレームの代表点Ｒａに対して、参照フレームのサーチエリアＳａが、基準フレームの代表点Ｒｂに対して、参照フレームのサーチエリアＳｂが、それぞれ設定されている例を示している。
【００４２】
なお、図３では、説明を分かりやすくするため、水平方向ｍ画素、垂直方向ｎ画素のブロックに均等分割した中央の画素を代表点として示しているが、実際には、代表点は、このように均等に決定されるわけではない。
【００４３】
次に、代表点それぞれについて、設定されたサーチエリア内の各画素と代表点の相関が判定され、サーチエリア内の画素ごとに評価値が設定される。具体的には、サーチエリア内の画素の画素値が代表点の画素値と近似していれば（代表点の画素値に対して所定の閾値内であれば）、評価値として ‘‘１’’が設定され、近似していなければ ‘‘０’’が設定される。その結果、１つの代表点に対して、サーチエリアと同一の領域の ‘‘１’’または ‘‘０’’の評価値が得られる。
【００４４】
最後に、代表点ごとに求められたサーチエリアと同一の領域の ‘‘１’’または ‘‘０’’の評価値を、図４Ａに示すように、サーチエリアの同一の位置どうしで積算することにより、図４Ｂに示すような、サーチエリアと同一の大きさ（領域）の評価値テーブルが生成される。
【００４５】
評価値テーブルでは、相関の度合いが高い（画素値の一致度合いが高い）サーチエリア内の位置ほど評価値の度数（累積値）は大きくなる。ここで、代表点に対応するサーチエリア内の位置である中心位置の座標を（０，０）として、その中心位置（０，０）を基準とする度数の大きい位置の相対座標を（ｕ，ｖ）で表す。ｕ，ｖは、座標値であるので整数となる。候補ベクトル抽出部１２においては、後述するように、度数の大きい順に順次検出される相対位置（ｕ，ｖ）がベクトル（ｕ，ｖ）とされる。
【００４６】
［代表点選別部１１の詳細構成］
次に、代表点選別部１１の詳細について説明する。
【００４７】
候補ベクトル抽出部１２では、上述したように、評価値テーブルの度数に基づいて、ベクトル（ｕ，ｖ）が決定され、ここで決定されたベクトル（ｕ，ｖ）が最終的に候補ベクトルとなる。そのため、評価値テーブルの精度を高めることが、精度の高い候補ベクトルの抽出につながる。
【００４８】
代表点選別部１１は、次の２つの理由から、近傍の画素と画素値に変化がある画素を代表点として選択する。第１に、代表点マッチング法では、上述したようにサーチエリア内の画素と代表点の画素どうしの相関判定を行うので、評価値テーブルの精度を高めるためには、相関判定結果の信頼性を高めることが必要である。相関判定結果の信頼性を高めるには、フレーム画像内で一意に特定できるようにするため、基準フレームのなかの平坦な部分ではなく、何らかの変化のある部分（テクスチャのある部分）を代表点とするのが望ましい。第２に、後述する候補ベクトル抽出部１２の相関判定部６４（図７）では、代表点を含む近傍画素の画素値を用いた相関判定を行うため、代表点とその近傍の画素に画素値の変化があることが必須となるためである。
【００４９】
以上の理由から、代表点選別部１１は、隣接する画素の画素値を結んで形成される傾き（以下、空間勾配ともいう。）の有無を検出し、基準フレームを構成する画素のうち、空間勾配のある画素を代表点として決定する。
【００５０】
図５は、代表点選別部１１が、画素値Ｐ（ｘ，ｙ）を有する基準フレームの画素（ｘ，ｙ）に対し、空間勾配の有無を検出するために用いられる近傍画素を示している。
【００５１】
即ち、基準フレームを構成する画素のうち、いま代表点とするか否かを判定する画素として注目する注目画素が（ｘ，ｙ）である場合、代表点選別部１１は、注目画素（ｘ，ｙ）に対し、水平（左右）方向と垂直（上下）方向に隣接する画素を用いる。
【００５２】
ここで、注目画素（ｘ，ｙ）の左側の画素（ｘ−１，ｙ）の画素値はＰ（ｘ−１，ｙ）であり、右側の画素（ｘ＋１，ｙ）の画素値がＰ（ｘ＋１，ｙ）である。また、注目画素（ｘ，ｙ）の上側の画素（ｘ，ｙ−１）の画素値はＰ（ｘ，ｙ−１）であり、下側の画素（ｘ，ｙ＋１）の画素値がＰ（ｘ，ｙ＋１）である。
【００５３】
代表点選別部１１は、注目画素の画素値Ｐ（ｘ，ｙ）と、水平方向に隣接する画素の画素Ｐ（ｘ−１，ｙ）およびＰ（ｘ＋１，ｙ）それぞれとの間で差分絶対値を計算する。また、代表点選別部１１は、注目画素の画素値Ｐ（ｘ，ｙ）と、垂直方向に隣接する画素の画素値Ｐ（ｘ，ｙ−１）およびＰ（ｘ，ｙ＋１）それぞれとの間で差分絶対値を計算する。
【００５４】
そして、代表点選別部１１は、計算された差分絶対値を、予め設定された閾値と比較して、注目画素の右側、左側、上側、下側のそれぞれで、空間勾配があるかを判定する。さらに、代表点選別部１１は、空間勾配があるか否かを、注目画素の水平方向と垂直方向で独立に判定し、水平方向と垂直方向の判定結果の論理積をとることで、水平方向と垂直方向の両方に空間勾配がある場合にのみ、その注目画素を代表点に決定する。
【００５５】
図６は、代表点選別部１１の詳細構成例を示すブロック図である。
【００５６】
代表点選別部１１は、左側勾配計算部４１Ｌ、右側勾配計算部４１Ｒ、上側勾配計算部４１Ｕ、下側勾配計算部４１Ｄ、ＯＲ演算部４２、ＯＲ演算部４３、およびＡＮＤ演算部４４により構成される。
【００５７】
左側勾配計算部４１Ｌ、右側勾配計算部４１Ｒ、上側勾配計算部４１Ｕ、および下側勾配計算部４１Ｄは、それぞれ、注目画素の左側、右側、上側、下側の勾配の有無を判定し、１ビットの判定結果を出力する。
【００５８】
左側勾配計算部４１Ｌ、右側勾配計算部４１Ｒ、上側勾配計算部４１Ｕ、および下側勾配計算部４１Ｄそれぞれは、レジスタ５１、減算器５２、絶対値計算部５３、および比較部５４を有し、注目画素の左側、右側、上側、下側に対応する符号（Ｌ，Ｒ，Ｕ，Ｄ）を付している。
【００５９】
左側勾配計算部４１Ｌを例に説明すると、注目画素が図５に示した画素（ｘ，ｙ）である場合には、レジスタ５１Ｌには、比較される左側の画素の画素値Ｐ（ｘ−１，ｙ）が記憶される。減算器５２Ｌは、注目画素の画素値Ｐ（ｘ，ｙ）と、レジスタ５１Ｌに記憶されている左側の画素の画素値Ｐ（ｘ−１，ｙ）とを減算する。絶対値計算部５３Ｌは、減算器５２Ｌの減算結果の絶対値を計算する。比較部５４Ｌは、絶対値計算部５３Ｌの計算結果を、予め設定されている閾値と比較する。比較部５４Ｌは、絶対値が閾値より大きく、空間勾配があると判定した場合、ビット ‘‘１’’を出力する。一方、比較部５４Ｌは、絶対値が閾値以下であり、空間勾配がないと判定した場合、ビット ‘‘０’’を出力する。
【００６０】
右側勾配計算部４１Ｒ、上側勾配計算部４１Ｕ、および下側勾配計算部４１Ｄについても、注目画素と比較される対象の画素が異なる以外は同様であるので、その説明は省略する。
【００６１】
ＯＲ演算部４２には、注目画素と左側の画素との間に空間勾配があるか否かを表す１ビットの情報と、注目画素と右側の画素との間に空間勾配があるか否かを表す１ビットの情報が入力される。ＯＲ演算部４２は、入力される２つの１ビットの論理和を演算し、演算結果を出力する。即ち、ＯＲ演算部４２は、注目画素が左側の画素か、または、右側の画素の少なくとも一方との間に空間勾配がある場合に ‘‘１’’を、両方の画素との間に空間勾配がない場合に ‘‘０’’を出力する。
【００６２】
ＯＲ演算部４３には、注目画素と上側の画素との間に空間勾配があるか否かを表す１ビットの情報と、注目画素と下側の画素との間に空間勾配があるか否かを表す１ビットの情報が入力される。ＯＲ演算部４３は、入力される２つの１ビットの論理和を演算し、演算結果を出力する。即ち、ＯＲ演算部４３は、注目画素が上側の画素か、または、下側の画素の少なくとも一方との間に空間勾配がある場合に ‘‘１’’を、両方の画素との間に空間勾配がない場合に ‘‘０’’を出力する。
【００６３】
ＡＮＤ演算部４４には、ＯＲ演算部４２から水平方向の空間勾配の有無を表す１ビットの情報と、ＯＲ演算部４３から垂直方向の空間勾配の有無を表す１ビットの情報が入力される。ＡＮＤ演算部４４は、入力される２つの１ビットの論理積を演算し、演算結果を出力する。即ち、水平方向および垂直方向の両方で空間勾配がある場合に ‘‘１’’を、少なくとも一方に空間勾配がない場合に ‘‘０’’を出力する。
【００６４】
以上のように構成される代表点選別部１１により、空間勾配のある画素を代表点として決定することで、高信頼度の評価値テーブルを生成することができるので、高精度なベクトル検出が可能となる。
【００６５】
［候補ベクトル抽出部１２の詳細構成］
次に、候補ベクトル抽出部１２の詳細について説明する。
【００６６】
図７は、候補ベクトル抽出部１２の詳細な構成例を示した画像処理装置１全体のブロック図である。
【００６７】
候補ベクトル抽出部１２は、代表点メモリ６１、評価値テーブル生成部６２、ピーク検出部６３、および相関判定部６４により構成されている。
【００６８】
代表点メモリ６１は、代表点選別部１１から供給される代表点情報、即ち、基準フレームの各画素が代表点であるか否かを示す ‘‘１’’または ‘‘０’’の情報を記憶する。また、代表点メモリ６１に記憶される代表点情報は、相関判定部６４によって更新される。代表点メモリ６１は、代表点情報が更新されたとき、更新によって変更された代表点数を制御部１３に供給する。
【００６９】
評価値テーブル生成部６２は、図３と図４を参照して説明した代表点マッチング法による評価値テーブルの生成処理を実行し、評価値テーブルを生成する。即ち、評価値テーブル生成部６２は、その時点で代表点メモリ６１に記憶されている全ての代表点について、サーチエリア内の各画素とマッチングを行った結果を積算し、評価値テーブルを生成する。生成された評価値テーブルは、ピーク検出部６３に供給される。
【００７０】
ピーク検出部６３は、評価値テーブル生成部６２から供給された評価値テーブルのなかで、度数が最大（ピーク）となっている位置を検出する。ピーク検出部６３は、度数が最大となっている画素の相対位置（ｕ，ｖ）を、ベクトル（ｕ，ｖ）として制御部１３および相関判定部６４に供給する。また、ピーク検出部６３は、ベクトル（ｕ，ｖ）に対応する評価値テーブルの度数、即ち、検出された度数の最大値も、制御部１３に供給する。
【００７１】
ピーク検出部６３から制御部１３にベクトル（ｕ，ｖ）とテーブルの度数（最大値）が供給されると、制御部１３は、テーブルの度数と、代表点メモリ６１から供給される代表点数が所定の条件を満たすか否かを判定する。所定の条件を満たすと判定された場合、制御部１３は、テーブルの度数とともに供給されたベクトル（ｕ，ｖ）を候補ベクトルとする。所定の条件を満たさないと判定された場合、制御部１３は、候補ベクトル抽出部１２に候補ベクトルの抽出処理を終了させる。従って、所定の条件を満たすと判定されている間、ピーク検出部６３から供給されるベクトル（ｕ，ｖ）は、すべて候補ベクトルとなる。そこで、以下では、ベクトル（ｕ，ｖ）を候補ベクトル（ｕ，ｖ）ともいう。
【００７２】
相関判定部６４は、代表点メモリ６１に記憶されている各代表点について、代表点と参照点の相関判定を行う。ここで、参照点とは、代表点に対応する参照フレームの画素から、ベクトル（ｕ，ｖ）先の参照フレームの画素（以下、参照点という。）をいう。そして、相関判定部６４は、相関判定の結果、相関が高いと判定された代表点を、候補ベクトル（ｕ，ｖ）が寄与する代表点であるとして、代表点メモリ６１の代表点情報から除外する。即ち、相関判定部６４は、代表点メモリ６１の、相関が高いと判定された代表点の代表点情報を ‘‘０’’に変更する。
【００７３】
［候補ベクトル抽出処理フロー］
図８のフローチャートを参照して、候補ベクトル抽出部１２と制御部１３による候補ベクトル抽出処理について説明する。
【００７４】
初めに、ステップＳ２１において、制御部１３は、カウンタｉをゼロに初期化するともに、過去に求めた候補ベクトルを初期化する。
【００７５】
ステップＳ２２において、代表点メモリ６１は、代表点選別部１１から供給される代表点情報を記憶する。
【００７６】
ステップＳ２３において、評価値テーブル生成部６２は、図３と図４を参照して説明した代表点マッチング法による評価値テーブルの生成処理を実行し、評価値テーブルを生成する。即ち、評価値テーブル生成部６２は、現時点で代表点メモリ６１に記憶されている全ての代表点について、サーチエリア内の各画素とマッチングを行った結果を積算し、評価値テーブルを生成する。生成された評価値テーブルは、ピーク検出部６３に供給される。
【００７７】
ステップＳ２４において、ピーク検出部６３は、評価値テーブル生成部６２から供給された評価値テーブルから、度数の最大値Ａを検出する。
【００７８】
ステップＳ２５において、ピーク検出部６３は、度数の最大値Ａに対応するベクトル（ｕ，ｖ）を抽出する。即ち、ピーク検出部６３は、最大値Ａの相対位置（ｕ，ｖ）をベクトル（ｕ，ｖ）として抽出し、制御部１３および相関判定部６４に供給する。また、ピーク検出部６３は、検出された度数の最大値Ａを制御部１３に供給する。
【００７９】
ステップＳ２６において、相関判定部６４は、代表点メモリ６１に記憶されている代表点それぞれについて、ベクトル（ｕ，ｖ）を用いて代表点に対応する参照点を決定し、代表点と参照点の相関判定を行う。
【００８０】
ステップＳ２７において、相関判定部６４は、相関判定の結果に基づいて、代表点メモリ６１の代表点情報を更新する。即ち、相関判定部６４は、代表点メモリ６１の、相関が高いと判定された代表点情報を ‘‘１’’から ‘‘０’’に変更する。
【００８１】
ステップＳ２８において、代表点メモリ６１は、相関判定部６４による更新によって、 ‘‘１’’から ‘‘０’’に変更された代表点数Ｂを制御部１３に供給して、通知する。
【００８２】
ステップＳ２９において、制御部１３は、有意な候補ベクトルが検出されているかを判定する。具体的には、評価値テーブルの最大値Ａが閾値ＴＨ１よりも大であり、かつ、変更された代表点数Ｂが閾値ＴＨ２よりも大であって、カウンタｉがＮ回より少ない場合、制御部１３は、有意な候補ベクトルが検出されていると判定する。即ち、検出された評価値テーブルの最大値Ａがある程度大きく、同じベクトル（ｕ，ｖ）の画素が多く存在し、候補ベクトルの検出個数も所定個数（Ｎ個）に満たない場合には、有意な候補ベクトルが検出されていると判定される。一方、評価値テーブルの最大値Ａが小さいか、同じベクトル（ｕ，ｖ）の画素が少ないか、または、十分な個数（Ｎ個）の候補ベクトルが既に検出されている場合には、有意な候補ベクトルが検出されていないと判定される。
【００８３】
ここで、ベクトル（ｕ，ｖ）の検出個数の上限を設定するＮの制約は、［背景技術］に記載の特許文献１，２等で提案した方法による候補ベクトルの抽出個数と異なり、抽出個数の最大値を設定できるようにしたものである。従って、判定条件におけるＮの制約は省略することができる。
【００８４】
ステップＳ２９で、有意な候補ベクトルが検出されていると判定された場合、処理はステップＳ３０に進み、制御部１３は、ピーク検出部６３から供給された最大値Ａに対応するベクトル（ｕ，ｖ）を候補ベクトルに決定する。
【００８５】
そして、ステップＳ３１において、制御部１３は、カウンタｉを１だけインクリメントして、処理をステップＳ２３に戻す。これにより、ステップＳ２３乃至Ｓ２９の処理が再度実行される。即ち、更新後の代表点情報に基づいて、評価値テーブルが再生成され、再生成された評価値テーブルのなかの最大値Ａが検出され、最大値Ａに対応するベクトル（ｕ，ｖ）が抽出される。そして、ベクトル（ｕ，ｖ）を用いて代表点と参照点の相関判定が行われ、相関判定の結果に基づいて、代表点情報が、再び更新される。
【００８６】
一方、ステップＳ２９で、有意な候補ベクトルが検出されていないと判定された場合、処理はステップＳ３２に進み、制御部１３は、ステップＳ２３乃至Ｓ３１のループ処理で順次決定された候補ベクトルを、候補ベクトル割当部１４に供給する。
【００８７】
ここで、最大値Ａまたは代表点数Ｂの条件を満たさず、ループ処理が終了した場合には、検出された候補ベクトルの数はｉ個となり、Ｎ個の制限によりループ処理が終了した場合には、検出された候補ベクトルの数はＮ個となる。
【００８８】
以上のように、候補ベクトル抽出処理は、［背景技術］に記載の特許文献１，２等で提案した候補ベクトル抽出処理のように、予め設定された個数の候補ベクトルを抽出するものではない。即ち、候補ベクトル抽出処理は、有意な候補ベクトルが存在すると判定される限り、候補ベクトルの抽出処理が繰り返され、候補ベクトルを、存在する数だけ過不足なく抽出することができる。
【００８９】
候補ベクトル割当部１４では、図２を参照して説明したように、候補ベクトル抽出部１２で抽出された有意な候補ベクトルのなかから、各画素の動きベクトルが決定される。従って、有意な候補ベクトルを、存在する数だけ過不足なく抽出することにより、誤検出の少ない高精度な動きベクトルの検出が可能となる。
【００９０】
［相関判定部６４の詳細構成］
候補ベクトル抽出処理では、相関判定部６４によって、代表点メモリ６１に記憶されている代表点それぞれについて、候補ベクトル（ｕ，ｖ）を用いた代表点と参照点の相関判定が行われる（図８のステップＳ２６の処理）。
【００９１】
そこで、次に、相関判定部６４が行う相関判定の詳細について説明する。
【００９２】
図９は、相関判定部６４の詳細な構成例を示すブロック図である。
【００９３】
相関判定部６４は、代表点近傍画素データ構築部８１、参照点近傍画素データ構築部８２、波形形状解析部８３、第１評価関数演算部８４、第２評価関数演算部８５、第３評価関数演算部８６、第４評価関数演算部８７、および統合判定部８８により構成される。
【００９４】
相関判定部６４は、候補ベクトル（ｕ，ｖ）を用いて、代表点メモリ６１に記憶されている代表点情報に基づく基準フレームの各代表点と、それに対応する参照点の相関判定を行う。そして、相関判定部６４は、相関が高いと判定された代表点については、候補ベクトル（ｕ，ｖ）が有意な代表点であるとして代表点メモリ６１の代表点情報から除外する。即ち、代表点メモリ６１の、相関が高いと判定された代表点の代表点情報が ‘‘０’’に変更される。
【００９５】
ピーク検出部６３（図７）で検出される候補ベクトル（ｕ，ｖ）は、上述したように整数値であるが、基準フレームと参照フレーム間の真の対応ベクトル（真の動きベクトル）は実数値である。即ち、候補ベクトル（ｕ，ｖ）は整数精度であるのに対して、本来のオブジェクトの動きは実数精度である。そこで、相関判定部６４では、整数精度の候補ベクトル（ｕ，ｖ）として検出したことによる１画素以下の画素ずれ（以下、画素以下ずれという。）を考慮するため、代表点および参照点の近傍の画素も用いて、代表点と参照点との相関判定が行われる。
【００９６】
代表点近傍画素データ構築部８１は、代表点メモリ６１に記憶されている基準フレームの各代表点に対し、代表点とその近傍の画素の画素データでなる代表点近傍画素データを構築する。構築された代表点を含む近傍の画素の画素データは、波形形状解析部８３、第１評価関数演算部８４、第２評価関数演算部８５、第３評価関数演算部８６、および第４評価関数演算部８７に供給される。
【００９７】
参照点近傍画素データ構築部８２は、参照フレームの参照点、即ち、代表点に対応する参照フレームの画素から候補ベクトル（ｕ，ｖ）先の画素と、その近傍の画素の画素データでなる参照点近傍画素データを構築する。構築された参照点を含む近傍の画素の画素データは、第１評価関数演算部８４、第２評価関数演算部８５、第３評価関数演算部８６、および第４評価関数演算部８７に供給される。
【００９８】
代表点近傍画素データ構築部８１と参照点近傍画素データ構築部８２において、代表点または参照点の近傍の画素としては、図５を参照して説明した代表点選別部１１と同様、右側、左側、上側、下側の画素が採用される。
【００９９】
波形形状解析部８３は、代表点を中心とする水平方向および垂直方向それぞれの３画素の画素値を結んで形成される波形パターン（空間勾配の形状）を解析する。代表点選別部１１では、空間勾配のある画素が代表点として選択されている。従って、代表点を中心とする水平方向または垂直方向のそれぞれで波形パターンをみたとき、波形パターンは、図１０に示すように、右上がり、右下がり、上に凸、下に凸の、いずれかとなっている。波形形状解析部８３は、代表点を中心とする水平方向および垂直方向それぞれの波形パターンが、右上がり、右下がり、上に凸、または下に凸の、いずれであるかを解析する。波形形状解析部８３は、解析結果の、右上がり、右下がり、上に凸、または下に凸のいずれかの波形パターンの情報を、第１評価関数演算部８４、第２評価関数演算部８５、第３評価関数演算部８６、第４評価関数演算部８７、および統合判定部８８に供給する。
【０１００】
第１評価関数演算部８４は、波形パターンが、右上がり、右下がり、上に凸、または下に凸のいずれであるかに応じて異なる、代表点を中心とする３画素の画素値を用いた第１評価関数を演算し、演算結果を統合判定部８８に供給する。演算結果は、１ビットの情報で表される。ここで、第１評価関数は、水平方向と垂直方向のそれぞれでも異なり、水平方向の第１評価関数をＦ１、垂直方向の第１評価関数をＧ１とする。
【０１０１】
第２評価関数演算部８５は、適用する評価関数が第２評価関数となる以外は、第１評価関数演算部８４と同様である。即ち、第２評価関数演算部８５は、波形パターンが、右上がり、右下がり、上に凸、または下に凸のいずれであるかに応じて異なる、代表点を中心とする３画素の画素値を用いた第２評価関数を演算し、１ビットの演算結果を統合判定部８８に供給する。第２評価関数は、水平方向と垂直方向のそれぞれでも異なり、水平方向の第２評価関数をＦ２、垂直方向の第２評価関数をＧ２とする。
【０１０２】
第３評価関数演算部８６は、適用する評価関数が第３評価関数となる以外は、第１評価関数演算部８４と同様である。第４評価関数演算部８７は、適用する評価関数が第４評価関数となる以外は、第１評価関数演算部８４と同様である。
【０１０３】
統合判定部８８は、第１評価関数演算部８４乃至第４評価関数演算部８７のそれぞれから供給される１ビットの演算結果を統合し、代表点と参照点の相関が高いか否かの最終判定を行う。また、統合判定部８８は、代表点メモリ６１の、相関が高いと判定した代表点の代表点情報を ‘‘１’’から ‘‘０’’に変更する。
【０１０４】
［右上がりの場合の相関判定処理］
次に、図１１を参照して、代表点を中心とする水平方向の３画素の波形パターンが右上がりである場合の相関判定処理の詳細について説明する。
【０１０５】
候補ベクトル（ｕ，ｖ）は整数精度であるのに対して、本来のオブジェクトの動きは実数精度であるため、候補ベクトル（ｕ，ｖ）により、代表点と参照点を重ね合わせても、代表点と参照点は基本的には一致しない。従って、代表点と参照点を重ね合わせた場合、代表点と参照点との間に１画素以下の画素ずれが生じる。この１画素以下の画素ずれ（以下、適宜、画素以下ずれという。）をｓｘとすると、代表点と参照点の画素値にも、画素以下ずれｓｘによる画素値ずれが生じる。画素以下ずれｓｘによる画素値ずれを、フレーム間画素値差分ｄｔとする。このフレーム間画素値差分ｄｔは、画素以下ずれｓｘの方向によって、プラス側にずれる場合とマイナス側にずれる場合がある。
【０１０６】
図１１は、代表点（ｘ，ｙ）と、候補ベクトル（ｕ，ｖ）先の参照点（ｘ＋ｕ，ｙ＋ｖ）を、相対的にずらして整数精度で重ねて示した図である。
【０１０７】
なお、図１１では、代表点（ｘ，ｙ）の画素値がＰ（ｘ，ｙ）で、代表点（ｘ，ｙ）の候補ベクトル（ｕ，ｖ）先の参照フレームの参照点（ｘ＋ｕ，ｙ＋ｖ）の画素値がＱ（ｘ＋ｕ，ｙ＋ｖ）で表されている。
【０１０８】
ただし、図１１では、代表点を中心とする水平方向の波形だけを考慮すればよいので、ｙ方向の座標は省略し、代表点と参照点の画素値をそれぞれＰ（ｘ）、Ｑ（ｘ＋ｕ）と表現した。図１１のｘ軸は代表点と参照点の相対座標を表し、ｙ軸は画素値（画素レベル）を表す。
【０１０９】
図１１Ａは、画素以下ずれｓｘがプラス方向に存在する場合のフレーム間画素値差分ｄｔを示している。画素以下ずれｓｘがプラス方向に存在する場合、波形パターンが右上がりなので、代表点と参照点のフレーム間画素値差分ｄｔは、マイナス方向に発生する。
【０１１０】
従って、代表点を基準に参照点との関係を考えると、図１１Ａに示されるように、代表点の画素値Ｐ（ｘ）は参照点の画素値Ｑ（ｘ＋ｕ）と参照点の右側の画素の画素値Ｑ（ｘ＋ｕ＋１）に挟まれる関係にあるはすである。
【０１１１】
即ち、代表点の画素値Ｐ（ｘ）は、
Ｐ（ｘ）≧Ｑ（ｘ＋ｕ）  ＆＆  Ｐ（ｘ）≦Ｑ（ｘ＋ｕ＋１）
・・・・・・・・・・（１）
を満たす。
【０１１２】
また、参照点を基準に代表点との関係を考えると、参照点の画素値Ｑ（ｘ＋ｕ）は代表点の画素値Ｐ（ｘ）と代表点の右側の画素の画素値Ｐ（ｘ−１）に挟まれる関係にあるはすである。
【０１１３】
即ち、参照点の画素値Ｑ（ｘ＋ｕ）は、
Ｑ（ｘ＋ｕ）≧Ｐ（ｘ−１）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ）
・・・・・・・・・・（２）
を満たす。
【０１１４】
そこで、第１評価関数演算部８４は、水平方向の波形パターンが右上がりである場合、次式（３）で表されるＦ１を演算する。
Ｆ１＝｛Ｐ（ｘ）≧Ｑ（ｘ＋ｕ）  ＆＆  Ｐ（ｘ）≦Ｑ（ｘ＋ｕ＋１）｝？１：０
・・・・・・・・・・（３）
【０１１５】
式（３）によれば、第１評価関数演算部８４は、｛  ｝内の式（１）を満たす場合には、’’１’’を、満たさない場合には ‘‘０’’を、演算結果として出力する。
【０１１６】
また、第２評価関数演算部８５は、水平方向の波形パターンが右上がりである場合、次式（４）で表されるＦ２を演算する。
Ｆ２＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ−１）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ）｝？１：０
・・・・・・・・・・（４）
【０１１７】
式（４）によれば、第２評価関数演算部８５は、｛  ｝内の式（２）を満たす場合には、’’１’’を、満たさない場合には ‘‘０’’を、演算結果として出力する。
【０１１８】
図１１Ｂは、画素以下ずれｓｘがマイナス方向に存在する場合のフレーム間画素値差分ｄｔを示している。画素以下ずれｓｘがマイナス方向に存在する場合、波形パターンが右上がりなので、代表点と参照点のフレーム間画素値差分ｄｔは、プラス方向に発生する。
【０１１９】
従って、代表点を基準に参照点との関係を考えると、図１１Ｂに示されるように、代表点の画素値Ｐ（ｘ）は、参照点の左側の画素の画素値Ｑ（ｘ＋ｕ−１）と参照点の画素値Ｑ（ｘ＋ｕ）に挟まれる関係にあるはずである。
【０１２０】
即ち、代表点の画素値Ｐ（ｘ）は、
Ｐ（ｘ）≧Ｑ（ｘ＋ｕ−１）  ＆＆  Ｐ（ｘ）≦Ｑ（ｘ＋ｕ）
・・・・・・・・・・（５）
を満たす。
【０１２１】
また、参照点を基準に代表点との関係を考えると、参照点の画素値Ｑ（ｘ＋ｕ）は、代表点の画素値Ｐ（ｘ）と代表点の右側の画素の画素値Ｐ（ｘ＋１）に挟まれる関係にあるはずである。
【０１２２】
即ち、参照点の画素値Ｑ（ｘ＋ｕ）は、
Ｑ（ｘ＋ｕ）≧Ｐ（ｘ）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ＋１）
・・・・・・・・・・（６）
を満たす。
【０１２３】
そこで、第３評価関数演算部８６は、水平方向の波形パターンが右上がりである場合、次式（７）で表されるＦ３を演算する。
Ｆ３＝｛Ｐ（ｘ）≧Ｑ（ｘ＋ｕ−１）  ＆＆  Ｐ（ｘ）≦Ｑ（ｘ＋ｕ）｝？１：０
・・・・・・・・・・（７）
【０１２４】
式（７）によれば、第３評価関数演算部８６は、｛  ｝内の式（５）を満たす場合には、’’１’’を、満たさない場合には ‘‘０’’を、演算結果として出力する。
【０１２５】
また、第４評価関数演算部８７は、水平方向の波形パターンが右上がりである場合、次式（８）で表されるＦ４を演算する。
Ｆ４＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ＋１）｝？１：０
・・・・・・・・・・（８）
【０１２６】
式（８）によれば、第４評価関数演算部８７は、｛  ｝内の式（６）を満たす場合には、’’１’’を、満たさない場合には ‘‘０’’を、演算結果として出力する。
【０１２７】
以上は、水平方向の波形のみについてであり、垂直方向の波形について、Ｆ１乃至Ｆ４のｘをｙに置き換え、ｕをｖに置き換えたＧ１乃至Ｇ４の式が成り立つ。
【０１２８】
即ち、第１評価関数演算部８４は、垂直方向の波形パターンが右上がりである場合、次式（９）のＧ１を演算する。
Ｇ１＝｛Ｐ（ｙ）≧Ｑ（ｙ＋ｖ）  ＆＆  Ｐ（ｙ）≦Ｑ（ｙ＋ｖ＋１）｝？１：０
・・・・・・・・・・（９）
【０１２９】
第２評価関数演算部８５は、垂直方向の波形パターンが右上がりである場合、次式（１０）のＧ２を演算する。
Ｇ２＝｛Ｑ（ｙ＋ｖ）≧Ｐ（ｙ−１）  ＆＆  Ｑ（ｙ＋ｖ）≦Ｐ（ｙ）｝？１：０
・・・・・・・・・（１０）
【０１３０】
第３評価関数演算部８６は、垂直方向の波形パターンが右上がりである場合、次式（１１）のＧ３を演算する。
Ｇ３＝｛Ｐ（ｙ）≧Ｑ（ｙ＋ｖ−１）  ＆＆  Ｐ（ｙ）≦Ｑ（ｙ＋ｖ）｝？１：０
・・・・・・・・・（１１）
【０１３１】
第４評価関数演算部８７は、垂直方向の波形パターンが右上がりである場合、次式（１２）のＧ４を演算する。
Ｇ４＝｛Ｑ（ｙ＋ｖ）≧Ｐ（ｙ）  ＆＆  Ｑ（ｙ＋ｖ）≦Ｐ（ｙ＋１）｝？１：０
・・・・・・・・・（１２）
【０１３２】
水平方向および垂直方向の波形パターンが右上がりである場合、統合判定部８８には、以上のようなＦ１乃至Ｆ４とＧ１乃至Ｇ４の演算結果が供給される。
【０１３３】
次に、統合判定部８８の統合判定について説明する。
【０１３４】
水平方向については、代表点を基準に考えても、参照点を基準に考えてもよい。従って、上述のＦ１かまたはＦ２の一方が成立すればよく、Ｆ３とＦ４についてもいずれか一方が成立すればよい。また、上述の式には等しい場合も含まれているので、プラス方向（Ｆ１またはＦ２）か、または、マイナス方向（Ｆ３またはＦ４）のどちらかは成立するはずである。従って、統合判定部８８は、水平方向についての統合判定として、次式（１３）の統合関数Ｆを演算する。
【０１３５】
Ｆ＝｛（Ｆ１｜Ｆ２）xor（Ｆ３｜Ｆ４）｝？１：０
・・・・・・・・・（１３）
【０１３６】
式（１３）の ‘‘xor’’は、排他的論理和を表す。
【０１３７】
垂直方向についても同様に、統合判定部８８は、垂直方向の統合判定として、次式（１４）の統合関数Ｇを演算する。
Ｇ＝｛（Ｇ１｜Ｇ２）xor（Ｇ３｜Ｇ４）｝？１：０
・・・・・・・・・・（１４）
【０１３８】
次に、統合判定部８８は、水平方向と垂直方向を統合した最終判定を行う。
【０１３９】
代表点と参照点が画像として対応関係がとれている場合、水平方向と垂直方向のどちらも相関があるはずである。従って、統合判定部８８は、最終的な相関判定として、次式（１５）の統合関数Ｈを演算する。
Ｈ＝Ｆ＆Ｇ
・・・・・・・・・・（１５）
【０１４０】
式（１５）は、ＦとＧの両方が ‘‘１’’である場合のみ演算結果が ‘‘１’’となり、それ以外は ‘‘０’’となる演算式である。
【０１４１】
統合判定部８８は、次式（１５）の統合関数Ｈの演算結果から、代表点と参照点の相関が高いと判定した場合、即ち、統合関数Ｈの演算結果が ‘‘１’’である場合、代表点メモリ６１の、相関が高いと判定した代表点の代表点情報を ‘‘１’’から ‘‘０’’に変更する。
【０１４２】
［右下がりの場合の相関判定処理］
次に、代表点を中心とする水平方向の３画素の波形パターンが右下がりである場合の相関判定処理について説明する。
【０１４３】
図１２は、波形パターンが右下がりである場合について、図１１と同様に、代表点と参照点を整数精度で重ねて示した図である。
【０１４４】
水平方向の波形パターンが右下がりであり、画素以下ずれｓｘがプラス方向に存在する場合、代表点を基準とする参照点との関係から、第１評価関数演算部８４は、次式（１６）のＦ１を演算する。
Ｆ１＝｛Ｐ（ｘ）≧Ｑ（ｘ＋ｕ＋１）  ＆＆  Ｐ（ｘ）≦Ｑ（ｘ＋ｕ）｝？１：０
・・・・・・・・・・（１６）
【０１４５】
また、第２評価関数演算部８５は、水平方向の波形パターンが右下がりであり、画素以下ずれｓｘがプラス方向に存在する場合、参照点を基準とする代表点との関係から、次式（１７）のＦ２を演算する。
Ｆ２＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ−１）｝？１：０
・・・・・・・・・・（１７）
【０１４６】
第３評価関数演算部８６は、水平方向の波形パターンが右下がりであり、画素以下ずれｓｘがマイナス方向に存在する場合、代表点を基準とする参照点との関係から、次式（１８）のＦ３を演算する。
Ｆ３＝｛Ｐ（ｘ）≧Ｑ（ｘ＋ｕ）  ＆＆  Ｐ（ｘ）≦Ｑ（ｘ＋ｕ−１）｝？１：０
・・・・・・・・・・（１８）
【０１４７】
第４評価関数演算部８７は、水平方向の波形パターンが右下がりであり、画素以下ずれｓｘがマイナス方向に存在する場合、参照点を基準とする代表点との関係から、次式（１９）のＦ４を演算する。
Ｆ４＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ＋１）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ）｝？１：０
・・・・・・・・・・（１９）
【０１４８】
垂直方向の波形についても、Ｆ１乃至Ｆ４のｘをｙに置き換え、ｕをｖに置き換えたＧ１乃至Ｇ４の式が成り立つ。そして、水平方向および垂直方向の波形パターンが右下がりである場合、統合判定部８８は、式（１３）と式（１４）を演算し、さらに、その演算結果を用いて式（１５）を演算する。
【０１４９】
［下に凸の場合の相関判定処理］
次に、代表点を中心とする水平方向の３画素の波形パターンが下に凸である場合の相関判定処理について説明する。
【０１５０】
図１３は、波形パターンが下に凸である場合について、図１１と同様に、代表点と参照点を整数精度で重ねて示した図である。
【０１５１】
水平方向の波形が下に凸であり、画素以下ずれｓｘがプラス方向に存在する場合、代表点を基準に参照点との関係を考えると、代表点の画素値Ｐ（ｘ）は、参照フレームの画素値に挟まれる関係にはない。従って、第１評価関数演算部８４は、Ｆ１の演算を行わない。
【０１５２】
一方、水平方向の波形が下に凸であり、画素以下ずれｓｘがプラス方向に存在する場合、参照点を基準とする代表点との関係から、第２評価関数演算部８５は、次式（２０）のＦ２を演算する。
Ｆ２＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ＋１）｝？１：０
・・・・・・・・・・（２０）
【０１５３】
次に、水平方向の波形が下に凸であり、画素以下ずれｓｘがマイナス方向に存在する場合で、代表点を基準に参照点との関係を考えた場合、代表点の画素値Ｐ（ｘ）は、参照フレームの画素値に挟まれる関係にはない。従って、第３評価関数演算部８６は、Ｆ３の演算を行わない。
【０１５４】
一方、水平方向の波形が下に凸であり、画素以下ずれｓｘがマイナス方向に存在する場合、参照点を基準とする代表点との関係から、第４評価関数演算部８７は、次式（２１）のＦ４を演算する。
Ｆ４＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ−１）｝？１：０
・・・・・・・・・・（２１）
【０１５５】
垂直方向の波形についても、Ｆ２とＦ４のｘをｙに置き換え、ｕをｖに置き換えたＧ２とＧ４の式が成り立つ。そして、水平方向および垂直方向の波形パターンが下に凸である場合、統合判定部８８は、式（１３）と式（１４）に代えて、式（２２）と式（２３）を演算し、その演算結果を用いて式（１５）を演算する。
【０１５６】
Ｆ＝｛（Ｆ２）or（Ｆ４）｝？１：０
・・・・・・・・・・（２２）
Ｇ＝｛（Ｇ２）or（Ｇ４）｝？１：０
・・・・・・・・・・（２３）
【０１５７】
式（１３）と式（１４）は、水平方向および垂直方向の波形が下に凸である場合には、Ｆ１とＦ３およびＧ１とＧ３が存在しないこと、Ｆ２とＦ４、または、Ｇ２とＧ４は両方満たす場合もあり得ること、の２点の理由から、式（２２）と式（２３）のように表すことができる。
【０１５８】
［上に凸の場合の相関判定処理］
次に、代表点を中心とする水平方向の３画素の波形パターンが上に凸である場合の相関判定処理について説明する。
【０１５９】
図１４は、波形パターンが上に凸である場合について、図１１と同様に、代表点と参照点を整数精度で重ねて示した図である。
【０１６０】
水平方向の波形が上に凸であり、画素以下ずれｓｘがプラス方向に存在する場合、代表点を基準に参照点との関係を考えると、代表点の画素値Ｐ（ｘ）は、参照フレームの画素値に挟まれる関係にはない。従って、波形パターンが下に凸である場合と同様に、第１評価関数演算部８４は、Ｆ１の演算を行わない。
【０１６１】
一方、水平方向の波形が上に凸であり、画素以下ずれｓｘがプラス方向に存在する場合、参照点を基準とする代表点との関係から、第２評価関数演算部８５は、次式（２４）のＦ２を演算する。
Ｆ２＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ＋１）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ）｝？１：０
・・・・・・・・・・（２４）
【０１６２】
次に、水平方向の波形が上に凸であり、画素以下ずれｓｘがマイナス方向に存在する場合で、代表点を基準に参照点との関係を考えた場合、代表点の画素値Ｐ（ｘ）は、参照フレームの画素値に挟まれる関係にはない。従って、第３評価関数演算部８６は、波形パターンが下に凸である場合と同様に、Ｆ３の演算を行わない。
【０１６３】
一方、水平方向の波形が上に凸であり、画素以下ずれｓｘがマイナス方向に存在する場合、参照点を基準とする代表点との関係から、第４評価関数演算部８７は、次式（２５）のＦ４を演算する。
Ｆ４＝｛Ｑ（ｘ＋ｕ）≧Ｐ（ｘ−１）  ＆＆  Ｑ（ｘ＋ｕ）≦Ｐ（ｘ）｝？１：０
・・・・・・・・・・（２５）
【０１６４】
垂直方向の波形についても、Ｆ２とＦ４のｘをｙに置き換え、ｕをｖに置き換えたＧ２とＧ４の式が成り立つ。そして、水平方向および垂直方向の波形パターンが上に凸である場合、統合判定部８８は、波形パターンが下に凸である場合と同様に、式（２２）と式（２３）を演算し、その演算結果を用いて式（１５）を演算する。
【０１６５】
図１５は、水平方向についての第１評価関数演算部８４乃至第４評価関数演算部８７の評価関数Ｆ１乃至Ｆ４をまとめたものである。
【０１６６】
なお、図１５の評価関数Ｆ１乃至Ｆ４は、画像データのノイズ等を考慮して、マージンthを含めた式となっている。
【０１６７】
垂直方向についての評価関数Ｇ１乃至Ｇ４は、Ｆ１乃至Ｆ４のｘをｙに置き換え、ｕをｖに置き換えたものであるので、図示は省略する。
【０１６８】
以上のように、相関判定部６４は、代表点の画素値が参照点の近傍の画素の画素値に挟まれる関係にあるか、または、参照点の画素値が代表点の近傍の画素の画素値に挟まれる関係にあるという条件を満たすか否かにより、代表点と参照点との相関判定を行う。
【０１６９】
［相関判定処理フロー］
次に、図１６のフローチャートを参照して、相関判定部６４による、代表点メモリ６１に記憶されている代表点の１つに対する相関判定処理について説明する。
【０１７０】
初めに、ステップＳ４１において、代表点近傍画素データ構築部８１は、代表点メモリ６１に記憶されている代表点の１つを取得し、取得した代表点とその近傍の画素の画素データでなる代表点近傍画素データを構築する。
【０１７１】
ステップＳ４２において、参照点近傍画素データ構築部８２は、参照フレームの参照点とその近傍の画素の画素データでなる参照点近傍画素データを構築する。
【０１７２】
ステップＳ４３において、波形形状解析部８３は、代表点近傍の波形パターンを、水平方向および垂直方向それぞれについて解析する。即ち、波形形状解析部８３は、代表点を中心とする水平方向および垂直方向それぞれの３画素の画素値を結んで形成される波形パターンを解析する。解析結果は、第１評価関数演算部８４乃至第４評価関数演算部８７と統合判定部８８に供給される。
【０１７３】
ステップＳ４４において、第１評価関数演算部８４乃至第４評価関数演算部８７は、水平方向の波形パターンが右上がりであるかを判定する。ステップＳ４４で、水平方向の波形パターンが右上がりであると判定された場合、処理はステップＳ４５に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、波形パターンが右上がりであるときの評価関数Ｆ１乃至Ｆ４を演算する。具体的には、第１評価関数演算部８４は式（３）のＦ１を、第２評価関数演算部８５は式（４）のＦ２を、第３評価関数演算部８６は式（７）のＦ３を、第４評価関数演算部８７は式（８）のＦ４を、それぞれ演算する。その後、統合判定部８８は、式（１３）の統合関数Ｆ＝｛（Ｆ１｜Ｆ２）xor（Ｆ３｜Ｆ４）｝？１：０  を演算する。
【０１７４】
一方、ステップＳ４４で、水平方向の波形パターンが右上がりではないと判定された場合、処理はステップＳ４６に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、水平方向の波形パターンが右下がりであるかを判定する。ステップＳ４６で、水平方向の波形パターンが右下がりであると判定された場合、処理はステップＳ４７に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、波形パターンが右下がりであるときの評価関数Ｆ１乃至Ｆ４を演算する。具体的には、第１評価関数演算部８４は式（１６）のＦ１を、第２評価関数演算部８５は式（１７）のＦ２を、第３評価関数演算部８６は式（１８）のＦ３を、第４評価関数演算部８７は式（１９）のＦ４を、それぞれ演算する。その後、統合判定部８８は、式（１３）の統合関数Ｆ＝｛（Ｆ１｜Ｆ２）xor（Ｆ３｜Ｆ４）｝？１：０  を演算する。
【０１７５】
一方、ステップＳ４６で、水平方向の波形パターンが右下がりではないと判定された場合、処理はステップＳ４８に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、水平方向の波形パターンが下に凸であるかを判定する。ステップＳ４８で、水平方向の波形パターンが下に凸であると判定された場合、処理はステップＳ４９に進み、第２評価関数演算部８５および第４評価関数演算部８７は、波形パターンが下に凸であるときの評価関数Ｆ２およびＦ４を演算する。具体的には、第２評価関数演算部８５は式（２０）のＦ２を、第４評価関数演算部８７は式（２１）のＦ４を、それぞれ演算する。その後、統合判定部８８は、式（２２）の統合関数Ｆ＝｛（Ｆ２）or（Ｆ４）｝？１：０  を演算する。
【０１７６】
一方、ステップＳ４８で、水平方向の波形パターンが下に凸ではないと判定された場合、即ち、水平方向の波形パターンが上に凸である場合、処理はステップＳ５０に進む。ステップＳ５０において、第２評価関数演算部８５および第４評価関数演算部８７は、波形パターンが上に凸であるときの評価関数Ｆ２およびＦ４を演算する。具体的には、第２評価関数演算部８５は式（２４）のＦ２を、第４評価関数演算部８７は式（２５）のＦ４を、それぞれ演算する。その後、統合判定部８８は、式（２２）の統合関数Ｆ＝｛（Ｆ２）or（Ｆ４）｝？１：０  を演算する。
【０１７７】
ステップＳ４５，Ｓ４７，Ｓ４９、またはＳ５０の処理後、ステップＳ５１において、第１評価関数演算部８４乃至第４評価関数演算部８７は、垂直方向の波形パターンが右上がりであるかを判定する。ステップＳ５１で、垂直方向の波形パターンが右上がりであると判定された場合、処理はステップＳ５２に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、波形パターンが右上がりであるときの評価関数Ｇ１乃至Ｇ４を演算する。その後、統合判定部８８は、式（１４）の統合関数Ｇ＝｛（Ｇ１｜Ｇ２）xor（Ｇ３｜Ｇ４）｝？１：０  を演算する。
【０１７８】
一方、ステップＳ５１で、垂直方向の波形パターンが右上がりではないと判定された場合、処理はステップＳ５３に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、垂直方向の波形パターンが右下がりであるかを判定する。ステップＳ５３で、垂直方向の波形パターンが右下がりであると判定された場合、処理はステップＳ５４に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、波形パターンが右下がりであるときの評価関数Ｇ１乃至Ｇ４を演算する。その後、統合判定部８８は、式（１４）の統合関数Ｇ＝｛（Ｇ１｜Ｇ２）xor（Ｇ３｜Ｇ４）｝？１：０  を演算する。
【０１７９】
一方、ステップＳ５３で、垂直方向の波形パターンが右下がりではないと判定された場合、処理はステップＳ５５に進み、第１評価関数演算部８４乃至第４評価関数演算部８７は、垂直方向の波形パターンが下に凸であるかを判定する。ステップＳ５５で、垂直方向の波形パターンが下に凸であると判定された場合、処理はステップＳ５６に進み、第２評価関数演算部８５および第４評価関数演算部８７は、波形パターンが下に凸であるときの評価関数Ｇ２およびＧ４を演算する。その後、統合判定部８８は、式（２３）の統合関数Ｇ＝｛（Ｇ２）or（Ｇ４）｝？１：０  を演算する。
【０１８０】
一方、ステップＳ５５で、垂直方向の波形パターンが下に凸ではないと判定された場合、即ち、垂直方向の波形パターンが上に凸である場合、処理はステップＳ５７に進む。ステップＳ５７において、第２評価関数演算部８５および第４評価関数演算部８７は、波形パターンが上に凸であるときの評価関数Ｇ２およびＧ４を演算する。その後、統合判定部８８は、式（２３）の統合関数Ｇ＝｛（Ｇ２）or（Ｇ４）｝？１：０  を演算する。
【０１８１】
なお、水平方向の波形パターンが下に凸または上に凸である場合、第１評価関数演算部８４および第３評価関数演算部８６は演算しないが、演算結果がＦ１＝０，Ｆ３＝０となる関数をダミーとして演算させてもよい。
【０１８２】
ステップＳ５２，Ｓ５４，Ｓ５６、またはＳ５７の処理後、ステップＳ５８において、統合判定部８８は、最終的な相関判定として式（１５）の統合関数Ｈ＝Ｆ＆Ｇ  を演算する。統合関数Ｈの演算結果が ‘‘１’’である場合、相関判定結果は代表点と参照点の相関が高いことを表し、演算結果が ‘‘０’’である場合、相関判定結果は代表点と参照点の相関が低いことを表す。
【０１８３】
図８のステップＳ２６では、図１６の相関判定処理が、代表点メモリ６１に記憶されている代表点それぞれに対して行われる。
【０１８４】
代表点がエッジ部など空間勾配の大きい箇所である場合には、フレーム間画素値差分ｄｔは、１画素以下の画素ずれであっても非常に大きな値となることがある。従って、代表点と参照点の相関判定を予め設定した閾値で判断することは難しい。
【０１８５】
画像処理装置１の相関判定処理では、代表点とその近傍の画素からなる代表点近傍画素データと、参照点とその近傍の画素からなる参照点近傍画素データに基づいた適応的な相関判定を行う。即ち、代表点の画素値が、参照点の近傍の画素の画素値に挟まれる関係にあるか、または、参照点の画素値が、代表点の近傍の画素の画素値に挟まれる関係にあるという条件を満たすか否かにより相関判定を行う。これにより、高精度な相関判定を行うことができる。
【０１８６】
そして、高精度な相関判定の結果に基づいて、代表点メモリ６１の代表点が選別されて代表点情報が更新され、更新後に残存する代表点について再度評価値テーブルが生成されるので、更新後に生成される評価値テーブルも信頼度の高いものとなる。従って、高精度なベクトル検出が可能である。
【０１８７】
［候補ベクトル割当部１４の候補ベクトル割当処理］
次に、候補ベクトル割当部１４の候補ベクトル割当処理について説明する。この処理は、図２のステップＳ３で行われる処理に相当する。
【０１８８】
図１７は、候補ベクトル割当部１４が行う候補ベクトル割当処理の概念図を示している。
【０１８９】
図１７では、３つの候補ベクトルＶ１，Ｖ２、およびＶ３が、制御部１３から供給された例が示されている。
【０１９０】
候補ベクトル割当部１４は、基準フレームの所定の画素を、動きベクトルを決定する画素として注目する注目画素に設定する。そして、候補ベクトル割当部１４は、注目画素を中心として予め決められたブロックサイズからなる、注目ブロックを構築する。図１７の例では、注目画素を中心として、水平方向３画素、垂直方向３画素からなるブロックで、注目ブロックが構築されている。
【０１９１】
そして、候補ベクトル割当部１４は、候補ベクトルＶ１，Ｖ２、およびＶ３のそれぞれについて、注目ブロックに対応する検査ブロックを参照フレームに設定する。検査ブロックは、注目ブロックと同サイズのブロックで構成される。
【０１９２】
図１７では、候補ベクトルＶ１，Ｖ２、およびＶ３に対する、検査ブロックＢＬV1，ＢＬV2、およびＢＬV3が示されている。
【０１９３】
候補ベクトル割当部１４は、検査ブロックＢＬV1，ＢＬV2、およびＢＬV3それぞれと注目ブロックとでブロックマッチングを行う。これにより、候補ベクトル割当部１４は、制御部１３から供給された候補ベクトルＶ１，Ｖ２、およびＶ３のなかで、注目画素に最適な候補ベクトルを決定する。そして、候補ベクトル割当部１４は、決定された最適な候補ベクトルを、注目画素の動きベクトルに決定し、出力する。
【０１９４】
図１８は、候補ベクトル割当部１４による候補ベクトル割当処理のフローチャートを示している。
【０１９５】
候補ベクトル割当処理では、最初に、候補ベクトル割当部１４は、ステップＳ８１において、制御部１３から供給された全ての候補ベクトルを取得する。
【０１９６】
ステップＳ８２において、候補ベクトル割当部１４は、基準フレームの所定の画素を注目画素に設定する。
【０１９７】
ステップＳ８３において、候補ベクトル割当部１４は、注目画素を中心として予め決められたブロックサイズからなる注目ブロックを基準フレームに設定し、注目ブロックの画素データを構築する。
【０１９８】
ステップＳ８４において、候補ベクトル割当部１４は、取得された全ての候補ベクトルについて、注目ブロックに対応する検査ブロックを参照フレームに設定し、設定した検査ブロックそれぞれの画素データを構築する。
【０１９９】
ステップＳ８５において、候補ベクトル割当部１４は、それぞれの検査ブロックと注目ブロックとでブロックマッチングを行うことにより、制御部１３から供給された全ての候補ベクトルのなかで、注目画素に最適な候補ベクトルを決定する。
【０２００】
たとえば、候補ベクトル割当部１４は、検査ブロックと注目ブロックの対応する画素どうしの画素値の差分絶対値総和を評価値として計算し、計算された評価値が最小となる検査ブロックの候補ベクトルを、注目画素に最適な候補ベクトルに決定する。
【０２０１】
ステップＳ８６において、候補ベクトル割当部１４は、最適な候補ベクトルとして決定した候補ベクトルを、注目画素の動きベクトルに決定し、出力する。
【０２０２】
ステップＳ８７において、候補ベクトル割当部１４は、基準フレームの全ての画素を注目画素に設定したかを判定する。ステップＳ８７で、基準フレームの全ての画素をまだ注目画素に設定していないと判定された場合、処理はステップＳ８２に戻る。ステップＳ８２では、まだ注目画素に設定されていない基準フレームの画素が注目画素に設定され、ステップＳ８２以降の処理が再度実行される。
【０２０３】
一方、ステップＳ８７で、基準フレームの全ての画素を注目画素に設定したと判定された場合、処理は終了する。
【０２０４】
以上のように、候補ベクトル割当部１４では、制御部１３から供給された複数の候補ベクトルを用いて、基準フレームの各画素の動きベクトルが決定され、出力される。
【０２０５】
なお、図１８の処理では、基準フレームの全画素を注目画素とすることにより、基準フレームの各画素の動きベクトルを決定するようにした。しかしながら、上述したように、基準フレームを複数のブロックに分割し、分割されたブロック単位で動きベクトルを決定するようにしてもよい。
【０２０６】
また、図１８の処理では、ブロックマッチングの評価値として、対応する画素どうしの画素値の差分絶対値総和を計算するようにしたが、評価値には、その他の演算結果、たとえば、差分絶対値二乗和などを用いることもできる。さらに、評価値として、正規化相互相関を用いた場合には、評価値が最大となる検査ブロックの候補ベクトルを、注目画素に最適な候補ベクトルとすることができる。
【０２０７】
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０２０８】
図１９は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０２０９】
コンピュータにおいて、CPU（Central Processing Unit）２０１，ROM（Read Only Memory）２０２，RAM（Random Access Memory）２０３は、バス２０４により相互に接続されている。
【０２１０】
バス２０４には、さらに、入出力インタフェース２０５が接続されている。入出力インタフェース２０５には、入力部２０６、出力部２０７、記憶部２０８、通信部２０９、及びドライブ２１０が接続されている。
【０２１１】
入力部２０６は、キーボード、マウス、マイクロホンなどよりなる。出力部２０７は、ディスプレイ、スピーカなどよりなる。記憶部２０８は、ハードディスクや不揮発性のメモリなどよりなる。通信部２０９は、ネットワークインタフェースなどよりなる。ドライブ２１０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体２１１を駆動する。
【０２１２】
以上のように構成されるコンピュータでは、CPU２０１が、例えば、記憶部２０８に記憶されているプログラムを、入出力インタフェース２０５及びバス２０４を介して、RAM２０３にロードして実行することにより、上述した一連の処理が行われる。
【０２１３】
コンピュータ（CPU２０１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体２１１に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０２１４】
コンピュータでは、プログラムは、リムーバブル記録媒体２１１をドライブ２１０に装着することにより、入出力インタフェース２０５を介して、記憶部２０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２０９で受信し、記憶部２０８にインストールすることができる。その他、プログラムは、ROM２０２や記憶部２０８に、あらかじめインストールしておくことができる。
【０２１５】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０２１６】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０２１７】
１  画像処理装置，  １１  代表点選別部，  １２  候補ベクトル抽出部，  １３  制御部，  １４  候補ベクトル割当部，  ６１  代表点メモリ，  ６２  評価値テーブル生成部，  ６３  ピーク検出部，  ６４  相関判定部，  ８１  代表点近傍画素データ構築部，  ８２  参照点近傍画素データ構築部，  ８３  波形形状解析部，  ８４  第１評価関数演算部，  ８５  第２評価関数演算部，  ８６  第３評価関数演算部，  ８７  第４評価関数演算部，  ８８  統合判定部
【図１】
2011141824.tif 000003
【図２】
2011141824.tif 000004
【図３】
2011141824.tif 000005
【図４】
2011141824.tif 000006
【図５】
2011141824.tif 000007
【図６】
2011141824.tif 000008
【図７】
2011141824.tif 000009
【図８】
2011141824.tif 000010
【図９】
2011141824.tif 000011
【図１０】
2011141824.tif 000012
【図１１】
2011141824.tif 000013
【図１２】
2011141824.tif 000014
【図１３】
2011141824.tif 000015
【図１４】
2011141824.tif 000016
【図１５】
2011141824.tif 000017
【図１６】
2011141824.tif 000018
【図１７】
2011141824.tif 000019
【図１８】
2011141824.tif 000020
【図１９】
2011141824.tif 000021