(57)【要約】【課題】より少ない計算量で、より迅速に、動きベクトルを検出する。【解決手段】特徴量抽出部１０１は、画素の特徴量を抽出する。特徴量フレームメモリ２０１は、カレントフレームに対して時間的に前のフレームである参照フレームの一部の領域毎に設けられた記憶領域であって、参照フレームの参照画素の特徴量に対応するアドレスで指定されるものへの、参照画素の位置を示す画素位置情報の記憶を制御する。候補ベクトル検出部２０２乃至最小誤差ベクトル選択部２０５は、記憶領域に記憶されている、参照画素の位置を示す画素位置情報を基に、カレントフレームの注目画素の特徴量と同じ特徴量の参照画素の位置の中から、動いた先が注目画素である参照画素の位置を選択する。本発明は、動きベクトルを検出する画像処理装置に適用できる。【選択図】      図１１
2004164117.tif 000002
【特許請求の範囲】
【請求項１】
画素の特徴量を抽出する特徴量抽出手段と、
第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、前記第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、前記第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御手段と、
前記記憶領域に記憶されている、前記第１の画素の位置を示す前記画素位置情報を基に、前記第１のフレームの前記第２の画素の特徴量と同じ特徴量の前記第１の画素の位置の中から、動いた先が前記第２の画素である前記第１の画素の位置を選択する選択手段と
を含むことを特徴とする画像処理装置。
【請求項２】
前記記憶制御手段は、前記第１の画素が属する前記領域に対応する前記記憶領域への、前記画素位置情報の記憶を制御し、
前記選択手段は、前記第１の画素が属する前記領域に対応する前記記憶領域に記憶されている前記画素位置情報を基に、動いた先が前記第２の画素である前記第１の画素の位置を選択する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記第２のフレームの一部の前記領域は、前記第２の画素の動きベクトルの大きさに対応して、前記第２のフレームの一部の他の領域と重複するように設けられている
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記記憶制御手段は、前記第１の画素の位置が属する、前記領域に対応する前記記憶領域、および重複している前記他の領域に対応する前記記憶領域への、前記第１の画素の位置を示す前記画素位置情報の記憶を制御する
ことを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記第２の画素の位置、および選択された前記第１の画素の位置から、前記第２の画素の動きベクトルを算出する算出手段をさらに含む
ことを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記選択手段は、記憶されている、前記第１の画素の位置を示す前記画素位置情報を基に、前記第２の画素の特徴量に近似する特徴量の前記第１の画素の位置の中から、動いた先が前記第２の画素である前記第１の画素の位置を選択する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項７】
前記選択手段は、前記第１のフレームにおける、前記第２の画素を含む第１のブロックと、前記第２のフレームにおける、前記画素位置情報で示される前記第１の画素を含む第２のブロックとのブロックマッチングにより、前記第２の画素の特徴量と同じ特徴量の前記第１の画素の位置の中から、動いた先が前記第２の画素である前記第１の画素の位置を選択する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項８】
画素の特徴量を抽出する特徴量抽出ステップと、
第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、前記第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、前記第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御ステップと、
前記記憶領域に記憶されている、前記第１の画素の位置を示す前記画素位置情報を基に、前記第１のフレームの前記第２の画素の特徴量と同じ特徴量の前記第１の画素の位置の中から、動いた先が前記第２の画素である前記第１の画素の位置を選択する選択ステップと
を含むことを特徴とする画像処理方法。
【請求項９】
画素の特徴量を抽出する特徴量抽出ステップと、
第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、前記第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、前記第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御ステップと、
前記記憶領域に記憶されている、前記第１の画素の位置を示す前記画素位置情報を基に、前記第１のフレームの前記第２の画素の特徴量と同じ特徴量の前記第１の画素の位置の中から、動いた先が前記第２の画素である前記第１の画素の位置を選択する選択ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１０】
画素の特徴量を抽出する特徴量抽出ステップと、
第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、前記第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、前記第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御ステップと、
前記記憶領域に記憶されている、前記第１の画素の位置を示す前記画素位置情報を基に、前記第１のフレームの前記第２の画素の特徴量と同じ特徴量の前記第１の画素の位置の中から、動いた先が前記第２の画素である前記第１の画素の位置を選択する選択ステップと
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理装置および方法、記録媒体、並びにプログラムに関し、特に、画像の動きを検出する画像処理装置および方法、記録媒体、並びにプログラムに関する。
【０００２】
【従来の技術】
画像の動きを示す動きベクトルを求め、この動きベクトルに基づいて効率よく動画像を処理する技術がある。
【０００３】
上述の動きベクトルを求める手法としては、いくつか提案されているが、代表的な手法としてブロックマッチングアルゴリズムと呼ばれる手法がある。
【０００４】
図１は、ブロックマッチングアルゴリズムを採用した従来の画像処理装置の構成を示すブロック図である。
【０００５】
フレームメモリ１１は、例えば、時刻ｔ１において、画像（画像データ）が入力されると、１フレーム分の画像を格納し、記憶する。さらに、フレームメモリ１１は、次のフレームのタイミングとなる時刻ｔ２において、次のフレームの画像が入力されると、新たに入力された時刻ｔ２の１フレーム分の画像を格納し、記憶するとともに、時刻ｔ１の１フレーム分の画像をサーチエリア生成部１２に出力する。
【０００６】
ラインメモリ１３は、時刻ｔ２のタイミングで、入力されてきた１フレームの所定のラインの画像を格納し、時刻ｔ２のタイミングで、ブロック生成部１４に出力する。
【０００７】
すなわち、フレームメモリ１１が、上述の時刻ｔ２のタイミングで入力される（今現在の）１フレーム分の画像の画素値を格納し、記憶するとき、フレームメモリ１１は、時刻ｔ１（１タイミング過去）の１フレーム分の画像の画素値をサーチエリア生成部１２に出力する。ラインメモリ１３は、時刻ｔ２のタイミングで入力された（今現在の）１フレームのラインの画像の画素値をブロック生成部１４に出力する。なお、以下において、ラインメモリ１３に格納される画像のラインに対応するフレームをカレントフレームＦｃ、フレームメモリ１１から出力される画像を参照フレームＦｒと称する。
【０００８】
サーチエリア生成部１２は、フレームメモリ１１から供給された参照フレームＦｒからサーチエリアＳＲを生成し、サーチエリアＳＲの画素の画素値をマッチング部１５に供給する。
【０００９】
ブロック生成部１４は、ラインメモリ１３から供給されたカレントフレームＦｃから基準ブロックＢｂを生成し、基準ブロックＢｂの画素の画素値をマッチング部１５に供給する。
【００１０】
図２に示すように、参照フレームＦｒのサーチエリアＳＲは、横にＮＳ（画素数）、縦にＭＳ（画素数）の画素からなり、カレントフレームＦｃの基準ブロックＢｂは、横にＮＢ（画素数）、縦にＭＢ（画素数）の画素からなる。通常、サーチエリアＳＲは、基準ブロックＢｂに比較して大きな領域（画素数が多い）からなる。
【００１１】
この場合、サーチエリアＳＲの縦および横の画素数を同じ数のＬとすることができる。
【００１２】
マッチング部１５は、サーチエリア生成部１２から供給されたサーチエリアＳＲの画素の画素値と、ブロック生成部１４から供給された基準ブロックＢｂの画素の画素値とを基に、サーチエリアＳＲの参照ブロックＢｒｎを構成する各画素の画素値と、基準ブロックＢｂの各画素の画素値との差分絶対値和を算出して、参照ブロックＢｒｎから基準ブロックＢｂへのベクトルと共に、差分絶対値和を誤差値として、誤差最小選択部１６に供給する。
【００１３】
誤差最小選択部１６は、最小である誤差値に対応するベクトルを選択して、選択されたベクトルを動きベクトルとして出力する。
【００１４】
ここで、ブロックマッチングアルゴリズムについて説明する。例えば、図３で示すように、カレントフレームＦｃ内の注目画素Ｐ（ｉ，ｊ）に対応する動きベクトルを求める場合、まず、カレントフレームＦｃ上に注目画素Ｐ（ｉ，ｊ）を中心としたＬ（画素数）×Ｌ（画素数）からなる基準ブロックＢｂ（ｉ，ｊ）、参照フレームＦｒ上に、注目画素Ｐ（ｉ，ｊ）の位置に対応するサーチエリアＳＲ、そして、そのサーチエリアＳＲ内に、Ｌ（画素数）×Ｌ（画素数）の画素からなる参照ブロックＢｒｎ（ｉ，ｊ）がそれぞれ設定される。
【００１５】
次に、この基準ブロックＢｂ（ｉ，ｊ）と、参照ブロックＢｒｎ（ｉ，ｊ）の各画素間の画素値の差分の絶対値の和を求める処理が、参照ブロックＢｒｎをサーチエリアＳＲ内の全域で水平方向、または、垂直方向に１画素分ずつラスタスキャン順に移動させながら、図３中のＢｒ１からＢｒｍ（参照ブロックＢｒｎが、サーチエリアＳＲ内にｍ個設定できるものとする）まで繰り返される。
【００１６】
このようにして求められた基準ブロックＢｂ（ｉ，ｊ）と、参照ブロックＢｒｎ（ｉ，ｊ）の各画素間の差分絶対値和のうち、差分絶対値和が最小となる参照ブロックＢｒｎを求めることにより、基準ブロックＢｂ（ｉ，ｊ）に最も近い（類似している）参照ブロックＢｒｎ（ｉ，ｊ）を構成するＬ×Ｌ個の画素の中心となる参照画素Ｐｎ（ｉ，ｊ）が求められる。
【００１７】
そして、このカレントフレームＦｃ上の注目画素Ｐ（ｉ，ｊ）に対応する参照フレームＦｒ上の画素Ｐ’（ｉ，ｊ）を始点とし、参照画素Ｐｎ（ｉ，ｊ）を終点とするベクトルが、注目画素Ｐ（ｉ，ｊ）の動きベクトル（Ｖｘ，Ｖｙ）として出力される。ここで、例えば、Ｐ（ｉ，ｊ）＝（ａ，ｂ）、および、Ｐｎ（ｉ，ｊ）＝（ｃ，ｄ）である場合、（Ｖｘ，Ｖｙ）は、（Ｖｘ，Ｖｙ）＝（ｃ−ａ，ｄ−ｂ）となる。
【００１８】
すなわち、注目画素Ｐ（ｉ，ｊ）に対応する参照フレーム上の参照画素Ｐ’（ｉ，ｊ）を始点とし、基準ブロックＢｂ（ｉ，ｊ）に最も近い（類似している）参照ブロックＢｒｎ（ｉ，ｊ）を構成するＬ×Ｌ個の画素の中心となる参照画素Ｐｎ（ｉ，ｊ）を終点とするベクトルが動きベクトルとして求められる。
【００１９】
次に、図４のフローチャートを参照して、図１の画像処理装置の動き検出処理について説明する。
【００２０】
ステップＳ１において、サーチエリア生成部１２は、カレントフレームＦｃ上の注目画素Ｐ（ｉ，ｊ）の画素位置に応じて、サーチエリアＳＲを設定する。
【００２１】
ステップＳ２において、誤差最小選択部１６は、上述のように、基準ブロックＢｂ（ｉ，ｊ）と参照ブロックＢｒｎ（ｉ，ｊ）の画素間の差分絶対値和の最小値を設定する変数ｍｉｎを、画素の階調数に基準ブロックＢｂ（ｉ，ｊ）を構成する画素数を乗じた値に設定することにより初期化する。すなわち、例えば、１画素が８ビットのデータであった場合、１画素の階調数は、２の８乗となるため２５６階調（２５６色）となる。また、基準ブロックＢｂ（ｉ，ｊ）がＬ画素×Ｌ画素＝３画素×３画素から構成される場合、その画素数は、９個となる。結果として、変数ｍｉｎは、２３０４（＝２５６（階調数）×９（画素数））に初期化される。
【００２２】
ステップＳ３において、マッチング部１５は、参照ブロックＢｒｎをカウントするカウンタ変数ｎを１に初期化する。
【００２３】
ステップＳ４において、誤差最小選択部１６は、基準ブロックＢｂと参照ブロックＢｒｎの画素間の差分絶対値和を代入するために用いる変数ｓｕｍを０に初期化する。
【００２４】
ステップＳ５において、マッチング部１５は、基準ブロックＢｂ（ｉ，ｊ）と参照ブロックＢｒｎ（ｉ，ｊ）の画素間の差分絶対値和（＝ｓｕｍ）を求める。すなわち、基準ブロックＢｂ（ｉ，ｊ）の各画素がＰ＿Ｂｂ（ｉ，ｊ）、基準ブロックＢｒｎ（ｉ，ｊ）の各画素がＰ＿Ｂｒｎ（ｉ，ｊ）としてそれぞれ示される場合、マッチング部１５は、以下の式（１）で示される演算を実行して、基準ブロックＢｂ（ｉ，ｊ）と参照ブロックＢｒｎ（ｉ，ｊ）の画素間の差分絶対値和を求める。
【００２５】
【数１】
2004164117.tif 000003
【００２６】
ステップＳ６において、誤差最小選択部１６は、変数ｍｉｎが変数ｓｕｍよりも大きいか否かを判定し、例えば、変数ｍｉｎが変数ｓｕｍよりも大きいと判定する場合、ステップＳ７において、変数ｍｉｎを変数ｓｕｍに更新し、その時点でのカウンタｎの値を動きベクトル番号として登録する。すなわち、今求めた差分絶対値和を示す変数ｓｕｍが、最小値を示す変数ｍｉｎよりも小さいと言うことは、これまで演算したどの参照ブロックよりも、今演算している参照ブロックＢｒｎ（ｉ，ｊ）が基準ブロックＢｂ（ｉ，ｊ）により類似したものであるとみなすことができるので、動きベクトルを求める際の候補とするため、その時点でのカウンタｎが動きベクトル番号として登録される。また、ステップＳ６において、変数ｍｉｎが変数ｓｕｍよりも大きくないと判定された場合、ステップＳ７の処理がスキップされる。
【００２７】
ステップＳ８において、マッチング部１５は、カウンタ変数ｎがサーチエリアＳＲの参照ブロックＢｒｎの総数ｍであるか否か、すなわち、今の参照ブロックＢｒｎがＢｒｎ＝Ｂｒｍであるか否かを判定し、例えば、総数ｍではないと判定した場合、ステップＳ９において、カウンタ変数ｎを１インクリメントし、その処理は、ステップＳ４に戻る。
【００２８】
ステップＳ８において、カウンタ変数ｎがサーチエリア内の参照ブロックＢｒｎの総数ｍである、すなわち、今の参照ブロックＢｒｎがＢｒｎ＝Ｂｒｍであると判定された場合、ステップＳ１０において、誤差最小選択部１６は、登録されている動きベクトル番号に基づいて動きベクトルを出力する。すなわち、ステップＳ４乃至Ｓ９が繰り返されることにより、差分絶対値和が最小となる参照ブロックＢｒｎに対応するカウンタ変数ｎが動きベクトル番号として登録されることになるので、誤差最小選択部１６は、この動きベクトル番号に対応する参照ブロックＢｒｎのＬ×Ｌ個の画素のうち、その中心となる参照画素Ｐｎ（ｉ，ｊ）を求め、カレントフレームＦｃ上の注目画素Ｐ（ｉ，ｊ）に対応する参照フレームＦｒ上の画素Ｐ’（ｉ，ｊ）を始点とし、参照画素Ｐｎ（ｉ，ｊ）を終点とするベクトルを、注目画素Ｐ（ｉ，ｊ）の動きベクトル（Ｖｘ，Ｖｙ）として求めて出力する。
【００２９】
図１に構成を示す画像処理装置において、１フレーム当たりの計算量は、１フレームの画素の数×差分絶対値和の計算量×基準ブロックＢｂに含まれる画素の数×サーチエリアＳＲに含まれる画素の数で求められる。
【００３０】
差分絶対値和の計算量を１クロックで表し、基準ブロックＢｂに８×８の画素が含まれ、サーチエリアＳＲに２０×２０の画素が含まれるとしたとき、１画素についての動きベクトルを求める処理の計算量は、８×８×２０×２０×１クロック、すなわち２５６００クロックとなる。
【００３１】
膨大な計算量が必要となるので、動画像をリアルタイムで処理することはできない。
【００３２】
演算量を少なくするために、ブロックマッチングアルゴリズムの一種として、代表点ブロックマッチングアルゴリズムが用いられている。
【００３３】
代表点ブロックマッチングアルゴリズムにおいては、図５に示すように、基準ブロックＢｂに代えて、代表点ブロックが用いられる。代表点ブロックに含まれる画素のうち、代表点ブロックの中央の画素、または代表点ブロックの所定の位置の画素など、１または複数の画素が代表点として選択される。
【００３４】
代表点ブロックマッチングアルゴリズムにおいては、代表点と、サーチエリアＳＲの参照代表画素との差分絶対値和が算出され、最小の差分絶対値和が選択される。そして、カレントフレームＦｃ上の代表点（ｉ，ｊ）に対応する参照フレームＦｒ上の画素Ｐ’（ｉ，ｊ）を始点とし、最小の差分絶対値和に対応する参照代表画素（ｉ，ｊ）を終点とするベクトルが、代表点ブロックの動きベクトル（Ｖｘ，Ｖｙ）とされ出力される。
【００３５】
代表点ブロックマッチングにおいて、計算量は、画素の数×差分絶対値和の計算量×代表点ブロックに含まれる画素の数×サーチエリアＳＲに含まれる画素の数／代表点ブロックに含まれる画素の数で求められる。
【００３６】
差分絶対値和の計算量を１クロックで表し、代表点ブロックに８×８の画素が含まれ、サーチエリアＳＲに２０×２０の画素が含まれるとしたとき、１画素についての動きベクトルを求める処理の計算量は、８×８×２０×２０／（８×８）×１クロック、すなわち４００クロックとなる。
【００３７】
代表点ブロックマッチングにおいては、計算量が少なくなるが、動きベクトルが代表点ブロックに対して求められるので、動きベクトルの精度は劣化することになる。
【００３８】
また、ブロックマッチング法により動きベクトルを検出する時に、定常成分および過渡成分の絶対値差分を累算した値の加重平均から得られる評価値に基づいて動きベクトルを検出することにより、演算量を低減させるようにするものがある（例えば、特許文献１参照）。
【００３９】
さらに、参照ブロックおよび探索範囲内の画素値を符号化してコード値に基づいてマッチング演算を行い、演算結果に基づいて第１の動きベクトルを算出し、第１の動きベクトルに応じた動き補償を行った後に第１の動きベクトルに係る候補ブロックを１画素を単位としてずらすことで得られる新たな探索範囲について、画素値の差分に基づくブロックマッチングを行うことにより、第２の動きベクトルを算出して、第１の動きベクトルと第２の動きベクトルの和として最終的な動きベクトルを算出することで、演算を簡素化するものがある（例えば、特許文献２参照）。
【００４０】
【特許文献１】
特開平０７−０８７４９４号公報
【特許文献２】
特開２０００−２７８６９１号公報
【００４１】
【発明が解決しようとする課題】
以上のように、従来は、動きベクトルを検出するためには膨大な計算量を必要とし、迅速に動きベクトルを検出することができなかった。また、より正確な動きベクトルを求める場合、さらに計算量が増加するという問題点があった。
【００４２】
本発明はこのような状況に鑑みてなされたものであり、より少ない計算量で、より迅速に、動きベクトルを検出できるようにすることを目的とする。
【００４３】
【課題を解決するための手段】
本発明の画像処理装置は、画素の特徴量を抽出する特徴量抽出手段と、第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御手段と、記憶領域に記憶されている、第１の画素の位置を示す画素位置情報を基に、第１のフレームの第２の画素の特徴量と同じ特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置を選択する選択手段とを含むことを特徴とする。
【００４４】
記憶制御手段は、第１の画素が属する領域に対応する記憶領域への、画素位置情報の記憶を制御し、選択手段は、第１の画素が属する領域に対応する記憶領域に記憶されている画素位置情報を基に、動いた先が第２の画素である第１の画素の位置を選択するようにすることができる。
【００４５】
第２のフレームの一部の領域は、第２の画素の動きベクトルの大きさに対応して、第２のフレームの一部の他の領域と重複するように設けることができる。
【００４６】
記憶制御手段は、第１の画素の位置が属する、領域に対応する記憶領域、および重複している他の領域に対応する記憶領域への、第１の画素の位置を示す画素位置情報の記憶を制御するようにすることができる。
【００４７】
画像処理装置は、第２の画素の位置、および選択された第１の画素の位置から、第２の画素の動きベクトルを算出する算出手段をさらに設けることができる。
【００４８】
選択手段は、記憶されている、第１の画素の位置を示す画素位置情報を基に、第２の画素の特徴量に近似する特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置を選択するようにすることができる。
【００４９】
選択手段は、第１のフレームにおける、第２の画素を含む第１のブロックと、第２のフレームにおける、画素位置情報で示される第１の画素を含む第２のブロックとのブロックマッチングにより、第２の画素の特徴量と同じ特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置を選択するようにすることができる。
【００５０】
本発明の画像処理方法は、画素の特徴量を抽出する特徴量抽出ステップと、第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御ステップと、記憶領域に記憶されている、第１の画素の位置を示す画素位置情報を基に、第１のフレームの第２の画素の特徴量と同じ特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置を選択する選択ステップとを含むことを特徴とする。
【００５１】
本発明の記録媒体のプログラムは、画素の特徴量を抽出する特徴量抽出ステップと、第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御ステップと、記憶領域に記憶されている、第１の画素の位置を示す画素位置情報を基に、第１のフレームの第２の画素の特徴量と同じ特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置を選択する選択ステップとを含むことを特徴とする。
【００５２】
本発明のプログラムは、コンピュータに、画素の特徴量を抽出する特徴量抽出ステップと、第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、第１の画素の位置を示す画素位置情報の記憶を制御する記憶制御ステップと、記憶領域に記憶されている、第１の画素の位置を示す画素位置情報を基に、第１のフレームの第２の画素の特徴量と同じ特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置を選択する選択ステップとを実行させることを特徴とする。
【００５３】
本発明の画像処理装置および方法、記録媒体、並びにプログラムにおいては、画素の特徴量が抽出され、第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、第１の画素の位置を示す画素位置情報の記憶が制御される。そして、記憶領域に記憶されている、第１の画素の位置を示す画素位置情報を基に、第１のフレームの第２の画素の特徴量と同じ特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置が選択される。
【００５４】
画像処理装置は、独立した装置であっても良いし、画像処理を行うブロックであってもよい。
【００５５】
【発明の実施の形態】
図６は、本発明に係る画像処理装置の一実施の形態の構成を示すブロック図である。画像処理装置に入力された画像は、特徴量抽出部１０１および特徴量抽出部１０３に供給される。
【００５６】
特徴量抽出部１０１は、入力された画像の画素を、例えばラスタスキャン順に参照画素とし、参照画素に対応する特徴量を抽出する。特徴量とは、画素の特徴を表す量である。例えば、特徴量抽出部１０１は、参照画素を中心とした、３×３のブロックに含まれる画素の画素値を所定の順（例えば、ラスタスキャン順）に並べた値を特徴量とする。参照画素を中心とした、３×３のブロックに含まれる画素の画素値を所定の順に並べた値が特徴量であるとき、ブロックに含まれるいずれかの画素の画素値が変化した場合、特徴量は変化することになる。
【００５７】
特徴量抽出部１０１は、参照画素の画面上の位置を示す画素位置情報と共に、抽出した特徴量を特徴量フレームメモリ１０２に供給する。
【００５８】
特徴量フレームメモリ１０２は、特徴量抽出部１０１から供給された、参照画素の画面上の位置を示す画素位置情報、および特徴量を取得し、特徴量に対応するアドレスに画素位置情報を記憶する。
【００５９】
図７は、特徴量フレームメモリ１０２が記憶する画素位置情報および画素位置情報の数の配置を説明する図である。
【００６０】
図中においてＤで示される四角は、それぞれ、１つの画素位置情報、または１つの画素位置情報の数を格納する格納領域Ｄを示す。
【００６１】
図７において、格納領域Ｄの縦方向（列方向）の位置は、特徴量アドレスで特定され、１つの（１つの種類の）特徴量に対応する。すなわち、１つの特徴量アドレスは、１つの特徴量を示すと言える。特徴量アドレスが異なる場合、それぞれの特徴量アドレスは、異なる特徴量を示す。図７に示す特徴量フレームメモリ１０２の例においては、０乃至Ｎ−１の範囲のＮ個の特徴量アドレスが設定されている。言い換えれば、図７に示す特徴量フレームメモリ１０２は、Ｎ種類の特徴量に分類された画素の画素位置情報を記憶することができる。
【００６２】
図７において、格納領域Ｄの横方向（行方向）の位置は、フラグアドレスで特定される。フラグアドレスが０である、図中の左側の列の格納領域Ｄには、特徴量アドレスで特定される特徴量を有する画素の数が格納される。同じ特徴量の画素の数は、その画素の位置を示す画素位置情報の数と等しいので、フラグアドレスが０である、図中の左側の列の格納領域Ｄには、同一の特徴量の画素の画素位置情報の数が格納されることになる。言い換えれば、所定の特徴量アドレスで特定される、フラグアドレス０の格納領域Ｄには、その特徴量アドレスで特定される格納領域Ｄに格納される画素位置情報の数が格納されることになる。
【００６３】
以下、特徴量アドレスがａで、フラグアドレスがｂである格納領域Ｄの位置をアドレス（ａ，ｂ）と表す。
【００６４】
フラグアドレスが１乃至Ｍである、図中の列の格納領域Ｄには、特徴量アドレスで特定される特徴量を有する画素の画素位置を示す画素位置情報の１つが格納される。例えば、特徴量アドレス２に対応する特徴量を有する最初の画素の画素位置を示す画素位置情報は、アドレス（２，１）の格納領域Ｄに格納される。そして、特徴量アドレス２に対応する特徴量を有する２番目の画素の画素位置を示す画素位置情報は、アドレス（２，２）の格納領域Ｄに格納される。
【００６５】
このように、特徴量アドレス２に対応する特徴量が抽出されたとき、その特徴量が抽出された参照画素の画素位置を示す画素位置情報が、特徴量アドレス２で示される格納領域Ｄであって、フラグアドレス１乃至Ｍで指定されるものに、図中の左側から右側に順に格納される。
【００６６】
同様に、０乃至Ｎ−１のいずれかの特徴量アドレスに対応する特徴量が抽出されたとき、その特徴量が抽出された参照画素の画素位置を示す画素位置情報が、０乃至Ｎ−１のいずれかの特徴量アドレスで示される格納領域Ｄであって、フラグアドレス１乃至Ｍで指定されるものに、図中の左側から右側に順に格納される。
【００６７】
各格納領域Ｄには、例えば、１ワード（例えば、３２ビット）の記憶領域を配置することができる。
【００６８】
特徴量フレームメモリ１０２は、以上のように、特徴量によって分類される画素の画素位置情報を順に記憶する。
【００６９】
特徴量フレームメモリ１０２が記憶する、特徴量アドレス毎に記憶されている画素位置情報は、全体として、対照表とも称する。
【００７０】
特徴量フレームメモリ１０２は、カレントフレームＦｃ（現在のフレーム）に対応する画素位置情報と、参照フレームＦｒ（１つ前のフレーム）に対応する画素位置情報とをそれぞれに記憶し、それぞれ読み出すことができる。すなわち、特徴量フレームメモリ１０２は、カレントフレームＦｃに対応する図７に示す格納領域Ｄのページと、参照フレームＦｒに対応する図７に示す格納領域Ｄのページとを有し、ページを切り替えることにより、特徴量抽出部１０１から供給されたカレントフレームＦｃの画素位置情報を記憶するとともに、記憶されている参照フレームＦｒの画素位置情報を読み出して、参照画素位置検出部１０４に供給することができる。
【００７１】
特徴量抽出部１０３は、入力された画像の画素を、例えばラスタスキャン順に注目画素とし、特徴量抽出部１０１と同様の処理で、注目画素に対応する特徴量を抽出する。例えば、特徴量抽出部１０１は、参照画素を中心とした、３×３のブロックに含まれる画素の画素値を所定の順に並べた値を特徴量とする。
【００７２】
特徴量抽出部１０３は、注目画素の画面上の位置を示す画素位置情報と共に、抽出した特徴量を参照画素位置検出部１０４に供給する。
【００７３】
なお、特徴量抽出部１０１または特徴量抽出部１０３が出力する特徴量を算出するためのブロックに含まれる画素の数は、任意の数とすることができ、３×３に限定されるものではない。特徴量を算出するためのブロックから、所定の数の画素を抽出して、抽出された画素から特徴量を求めるようにしてもよい。
【００７４】
また、特徴量抽出部１０１または特徴量抽出部１０３が抽出する特徴量は、ブロックに含まれる画素の画素値を並べた値に限らず、注目画素または参照画素の画素値そのもの、画素値の和、画素値の平均値、画素値の上位の所定のビットを抽出した値の配列、和、若しくは平均値などでもよい。
【００７５】
さらに、特徴量抽出部１０１または特徴量抽出部１０３は、ＡＤＲＣ（Ａｄａｐｔｉｖｅ  Ｄｙｎａｍｉｃ  Ｒａｎｇｅ  Ｃｏｄｉｎｇ）またはラプラシアンなど、画素値に所定の演算を適用して得られた結果を基に特徴量を算出するようにしてもよい。
【００７６】
参照画素位置検出部１０４は、特徴量抽出部１０３から供給された注目画素の特徴量、および特徴量フレームメモリ１０２に記憶されている参照フレームＦｒの画素位置情報を基に、注目画素の特徴量と同じ特徴量を有する、参照フレームＦｒの画素の画素位置を検出する。参照画素位置検出部１０４は、検出された注目画素の特徴量と同じ特徴量を有する、参照フレームＦｒの画素の画素位置から、動いた先が注目画素である参照フレームＦｒの画素の位置を選択する。そして、参照画素位置検出部１０４は、注目画素の画素位置情報と参照フレームＦｒの選択された画素の画素位置とから、注目画素の位置に対応する位置の参照フレームＦｒ上の画素を始点とし、注目画素の特徴量と同じ特徴量を有する参照フレームＦｒの選択された画素を終点とする動きベクトルを求めて、求めた動きベクトルを出力する。
【００７７】
なお、フレームを単位として処理を実行すると説明したが、フィールドを単位として処理を実行するようにしてもよいことは、勿論である。また、処理の対象は、時間的に隣接するフレームまたはフィールドに限らず、時間的に離れたフレームまたはフィールドとすることができる。以下の実施の形態においても同様である。
【００７８】
図８は、図６に構成を示す画像処理装置による、動きベクトルの検出の処理を説明するフローチャートである。
【００７９】
ステップＳ１０１において、特徴量抽出部１０１および特徴量フレームメモリ１０２は、参照フレームＦｒの画素位置情報の格納の処理を実行することにより、画素位置情報を記憶する。画素位置情報の格納の処理の詳細は、図９のフローチャートを参照して、後述する。
【００８０】
ステップＳ１０２において、特徴量抽出部１０３および参照画素位置検出部１０４は、注目画素に対応する画素の位置の検出の処理を実行して、注目画素の特徴量と同じ特徴量を有する、参照フレームＦｒの画素の画素位置を検出する。注目画素に対応する画素の位置の検出の処理の詳細は、図１０のフローチャートを参照して、後述する。
【００８１】
ステップＳ１０３において、参照画素位置検出部１０４は、特徴量抽出部１０３から供給された注目画素の画素位置情報、およびステップＳ１０２の処理で検出された、参照フレームＦｒの画素の画素位置を基に、動きベクトルを求める。例えば、参照画素位置検出部１０４は、注目画素の位置に対応する位置の参照フレームＦｒ上の画素を始点とし、注目画素の特徴量と同じ特徴量を有する参照フレームＦｒの画素を終点とする動きベクトルを求める。
【００８２】
ステップＳ１０４において、参照画素位置検出部１０４は、ステップＳ１０３の処理で求めた動きベクトルを出力して、処理は終了する。
【００８３】
図９は、ステップＳ１０１に対応する、画素位置情報の格納の処理を説明するフローチャートである。
【００８４】
ステップＳ１２１において、特徴量フレームメモリ１０２は、特徴量フレームメモリ１０２に格納されているデータを初期化する。例えば、特徴量フレームメモリ１０２は、フラグアドレスが０である格納領域Ｄに０を設定し、フラグアドレスが１乃至Ｍである格納領域Ｄにヌル（ｎｕｌｌ）を設定することにより、データを初期化する。
【００８５】
ステップＳ１２２において、特徴量抽出部１０１は、カウンタ変数ｎを初期化する。カウンタ変数ｎは、処理の対象となる画素の数を数えるための変数である。例えば、特徴量フレームメモリ１０２は、ステップＳ１２２において、カウンタ変数ｎに１を設定する。
【００８６】
ステップＳ１２３において、特徴量抽出部１０１は、参照フレームＦｒの画素のなかからまだ参照画素とされていない画素を選択して参照画素とする。特徴量抽出部１０１は、参照画素に対応するブロックの特徴量を算出することにより、参照画素の特徴量を抽出し、参照画素の位置を示す画素位置情報と共に、抽出した特徴量を特徴量フレームメモリ１０２に供給する。例えば、特徴量抽出部１０１は、参照画素を中心とした、３×３のブロックに含まれる画素の画素値をラスタスキャン順に並べた値である特徴量を算出する。
【００８７】
ステップＳ１２４において、特徴量フレームメモリ１０２は、ステップＳ１２３の処理で算出された特徴量に対応する画素位置情報の数を読み出す。例えば、参照画素の特徴量に対応する特徴量アドレスがｋであるとき、特徴量フレームメモリ１０２は、アドレス（ｋ，０）の格納領域Ｄから、特徴量に対応する画素位置情報の数を読み出す。
【００８８】
ステップＳ１２５において、特徴量フレームメモリ１０２は、ステップＳ１２４の処理で読み出した画素位置情報の数をインクリメントする。すなわち、特徴量フレームメモリ１０２は、ステップＳ１２４の処理で読み出した画素位置情報の数に１を加算する。
【００８９】
ステップＳ１２６において、特徴量フレームメモリ１０２は、ステップＳ１２５の処理でインクリメントされた画素位置情報の数を記憶する。例えば、特徴量フレームメモリ１０２は、特徴量に対応する特徴量アドレスがｋであるとき、アドレス（ｋ，０）の格納領域Ｄに、インクリメントされた画素位置情報の数を書き込む。
【００９０】
ステップＳ１２７において、特徴量フレームメモリ１０２は、特徴量に対応する特徴量アドレスと、画素位置情報の数に対応するフラグアドレスとから特定されるアドレスの格納領域Ｄに、参照画素の画素位置を示す画素位置情報を書き込む。例えば、特徴量フレームメモリ１０２は、参照画素の特徴量に対応する特徴量アドレスがｋであり、画素位置情報の数がｑであるとき、アドレス（ｋ，ｑ）の格納領域Ｄに、参照画素の画素位置を示す画素位置情報を書き込む。
【００９１】
このようにすることで、同じ特徴量の画素を示す画素位置情報は、同じ特徴量アドレスの格納領域Ｄに、図７中の左側から右側に向かって順に格納されることになる。ここで、１つの格納領域Ｄは、１つの画素位置情報を格納する。
【００９２】
ステップＳ１２８において、特徴量抽出部１０１は、カウンタ変数ｎをインクリメントする。すなわち、特徴量抽出部１０１は、カウンタ変数ｎに１を加算する。
【００９３】
ステップＳ１２９において、特徴量抽出部１０１は、カウンタ変数ｎの値が、フレームの画素の数に等しいか否かを判定し、カウンタ変数ｎの値が、フレームの画素の数に等しくないと判定された場合、まだ、参照画素とされていない画素がある、すなわち特徴量が抽出されていない画素があるので、ステップＳ１２３に戻り、上述した処理を繰り返し、次の参照画素について特徴量を抽出して、画素位置情報を特徴量フレームメモリ１０２に格納する。
【００９４】
ステップＳ１２９において、カウンタ変数ｎの値が、フレームの画素の数に等しいと判定された場合、フレームの全ての画素が参照画素とされ、フレームの全ての画素の特徴量が抽出されて、全ての画素に対応する画素位置情報が特徴量フレームメモリ１０２に格納されたので、処理は終了する。
【００９５】
図１０は、ステップＳ１０２の処理に対応する、注目画素に対応する画素位置の検出の処理を説明するフローチャートである。
【００９６】
ステップＳ１４１において、参照画素位置検出部１０４は、カウンタ変数ｎを初期化する。カウンタ変数ｎは、処理の対象となる画素の数を数えるための変数である。例えば、特徴量フレームメモリ１０２は、ステップＳ１４１において、カウンタ変数ｎに１を設定する。
【００９７】
ステップＳ１４２において、特徴量抽出部１０３は、特徴量抽出部１０１と同様の処理で、カレントフレームＦｃの画素のうち、まだ注目画素とされていない画素のなかから注目画素を選択する。特徴量抽出部１０３は、選択された注目画素に対応するブロックの特徴量を算出することにより、注目画素の特徴量を抽出し、注目画素の画面上の位置を示す画素位置情報と共に、抽出した特徴量を参照画素位置検出部１０４に供給する。例えば、特徴量抽出部１０３は、注目画素を中心とした、３×３のブロックに含まれる画素の画素値をラスタスキャン順に並べた値である特徴量を算出する。
【００９８】
ステップＳ１４３において、参照画素位置検出部１０４は、特徴量フレームメモリ１０２から、ステップＳ１４２の処理で算出された特徴量に対応する画素位置情報を読み出す。すなわち、参照画素位置検出部１０４は、ステップＳ１４２の処理で特徴量抽出部１０３から供給された特徴量と同一の特徴量の画素の位置を示す画素位置情報を読み出す。
【００９９】
より具体的には、特徴量抽出部１０３から供給された注目画素の特徴量に対応する特徴量アドレスがｋであるとき、参照画素位置検出部１０４は、特徴量フレームメモリ１０２のアドレス（ｋ，０）である格納領域Ｄから画素位置情報の数ｑを読み出す。そして、参照画素位置検出部１０４は、特徴量フレームメモリ１０２のアドレス（ｋ，１）乃至（ｋ，ｑ）である格納領域Ｄから、ｑ個の画素位置情報を読み出す。
【０１００】
ステップＳ１４４において、参照画素位置検出部１０４は、注目画素の動きに対応した参照画素の位置として（動いた先が注目画素である参照画素の位置として）、ステップＳ１４３の処理で読み出した画素位置情報で示される画素の位置のうち、注目画素に最も近い画素の位置を選択する。すなわち、参照画素位置検出部１０４は、画素位置情報で示される参照画素（の位置）Ｐｎ（ｉ，ｊ）と注目画素Ｐ（の位置）（ｉ，ｊ）との距離を求め、距離が最小の参照画素の位置を選択する。
【０１０１】
なお、参照画素位置検出部１０４は、注目画素の動きに対応した参照画素の位置として、注目画素に最も近い画素の位置を選択すると説明したが、注目画素に最も近い画素の位置に限らず、注目画素の画素値に最も近い画素値を有する参照画素の位置、または注目画素を含む所定のブロックの画素の画素値に最も近い画素値の画素からなるブロックに対応する参照画素の位置など、他の基準を基に、動いた先が注目画素である参照画素の位置を選択するようにしてもよい。
【０１０２】
以下に説明する、画素の位置を選択する処理においても同様である。
【０１０３】
ステップＳ１４５において、参照画素位置検出部１０４は、選択された画素の位置と注目画素の位置との距離が、予め定めた閾値より短いか否かを判定し、選択された画素の位置と注目画素の位置との距離が、予め定めた閾値より短いと判定された場合、注目画素の動きに対応した正しい画素の位置が選択されたので、ステップＳ１５２に進む。
【０１０４】
ステップＳ１４５において、選択された画素の位置と注目画素の位置との距離が、予め定めた閾値以上であると判定された場合、注目画素の動きに対応した正しい画素の位置が選択されていないので、ステップＳ１４６に進み、参照画素位置検出部１０４は、注目画素に対応するブロックの特徴量の近傍の特徴量を選択する。ここで、近傍の特徴量とは、近似の特徴を有する画素を示す特徴量をいう。例えば、所定のブロックに含まれる各画素の画素値に近い画素値を有する画素からなるブロックから算出される特徴量は、元のブロックの特徴量の近傍の特徴量である。また、所定のブロックに含まれる画素の各画素値の変化（例えば、画素値の差分の並び）と同様に変化し、元の画素値に近い画素値を有する画素からなるブロックから算出される特徴量は、元のブロックの近傍の特徴量である。
【０１０５】
例えば、元のブロックに含まれる１つの画素の画素値の最下位ビットを反転させて得られたブロックから算出される特徴量は、元のブロックの特徴量の近傍の特徴量である。特徴量が３×３のブロックに含まれる画素の画素値を所定の順に並べた値が特徴量であるとき、ブロックに含まれる全ての画素値の最下位ビットを反転させたブロックの特徴量は、元のブロックの特徴量の近傍の特徴量である。
【０１０６】
ステップＳ１４７において、参照画素位置検出部１０４は、特徴量フレームメモリ１０２から、近傍の特徴量に対応する画素位置情報を読み出す。すなわち、参照画素位置検出部１０４は、ステップＳ１４６の処理で選択された近傍の特徴量と同一の特徴量の画素の位置を示す画素位置情報を読み出す。より具体的には、例えば、近傍の特徴量に対応する特徴量アドレスがｋ’であるとき、参照画素位置検出部１０４は、特徴量フレームメモリ１０２のアドレス（ｋ’，０）である格納領域Ｄから画素位置情報の数ｑ’を読み出す。そして、参照画素位置検出部１０４は、特徴量フレームメモリ１０２のアドレス（ｋ’，１）乃至（ｋ’，ｑ’）である格納領域Ｄから、ｑ’個の画素位置情報を読み出す。
【０１０７】
ステップＳ１４８において、参照画素位置検出部１０４は、動いた先が注目画素である画素の位置として、ステップＳ１４７の処理で読み出した画素位置情報で示される画素の位置のうち、注目画素に最も近い画素の位置を選択する。
【０１０８】
ステップＳ１４９において、参照画素位置検出部１０４は、選択された画素の位置と注目画素の位置との距離が、予め定めた閾値より短いか否かを判定し、選択された画素の位置と注目画素の位置との距離が、予め定めた閾値より短いと判定された場合、注目画素の動きに対応した正しい画素の位置が選択されたので、ステップＳ１５２に進む。
【０１０９】
ステップＳ１４９において、選択された画素の位置と注目画素の位置との距離が、予め定めた閾値以上であると判定された場合、注目画素の動きに対応した正しい画素の位置が選択されていないので、ステップＳ１５０に進み、参照画素位置検出部１０４は、所定の範囲の近傍の特徴量を全て選択したか否かを判定する。
【０１１０】
例えば、参照画素位置検出部１０４は、特徴量が３×３のブロックに含まれる画素の画素値を所定の順に並べた値が特徴量抽出部１０３から供給された特徴量であるとき、選択する近傍の特徴量の範囲には、ブロックに含まれる全ての画素値の最下位ビットを反転させたブロックの特徴量、ブロックに含まれる全ての画素値の下位２ビットを反転させたブロックの特徴量、およびブロックに含まれる全ての画素値の下位３ビットを反転させたブロックの特徴量を含めることができる。
【０１１１】
ステップＳ１５０において、所定の範囲の近傍の特徴量を全て選択していないと判定された場合、まだ選択すべき近傍の特徴量があるので、ステップＳ１４６に戻り、他の近傍の特徴量を選択して、ステップＳ１４７乃至ステップＳ１４９の処理を繰り返す。
【０１１２】
ステップＳ１５０において、所定の範囲の近傍の特徴量を全て選択したと判定された場合、近傍の特徴量にも注目画素の動きに対応した正しい画素がないので、ステップＳ１５１に進み、参照画素位置検出部１０４は、予め定めた値を画素位置に設定して、ステップＳ１５２に進む。ステップＳ１５１において、参照画素位置検出部１０４は、エラーコードを注目画素に対応して設定するようにしてもよい。
【０１１３】
ステップＳ１５２において、参照画素位置検出部１０４は、カウンタ変数ｎをインクリメントする。すなわち、特徴量抽出部１０１は、カウンタ変数ｎに１を加算する。
【０１１４】
ステップＳ１５３において、参照画素位置検出部１０４は、カウンタ変数ｎの値が、フレームの画素の数に等しいか否かを判定し、カウンタ変数ｎの値が、フレームの画素の数に等しくないと判定された場合、まだ、注目画素とされていない画素がある、すなわち対応する画素の位置が検出されていない画素があるので、ステップＳ１４２に戻り、上述した処理を繰り返し、次の注目画素に対応する画素の位置を検出する。
【０１１５】
ステップＳ１５３において、カウンタ変数ｎの値が、フレームの画素の数に等しいと判定された場合、まだ、フレームの全ての画素が注目画素とされ、フレームの全ての画素に対応する画素の位置が検出されたので、処理は終了する。
【０１１６】
以上のように、図６に構成を示す画像処理装置は、従来に比較して、より少ない演算量で、より迅速に、より正確な動きベクトルを検出することができる。
【０１１７】
しかしながら、特徴量に対応する画素位置情報の数は、一定ではなく、画像によっては、多数の画素に対して１つの特徴量が抽出される場合がある。このような場合、１つの特徴量に対応する１つのアドレスに対して、多数（例えば、１０数万）の画素位置情報が記憶されることになる。
【０１１８】
１つの特徴量に対応するアドレスに対して、多数の画素位置情報が記憶されるとき、多数の画素位置情報に対して、上述した処理が実行されることになる。特に、画素位置情報のアクセスの処理に時間がかかる。
【０１１９】
そこで、画素位置情報を記憶する対照表を、画面の領域毎に区切ってしまえば、多数の画素位置情報をアクセスする必要が無くなり、より少ない画素位置情報から最適な動きベクトルを生成することができるようになる。すなわち、画素位置情報を記憶する対照表を、画面の領域毎に区切って、動きベクトルに無関係の画素位置情報をアクセスしないようにすれば、より少ない画素位置情報から最適な動きベクトルを生成することができるようになる。
【０１２０】
従って、より容易に画像処理装置を実現することができるようになる。
【０１２１】
図１１は、本発明に係る画像処理装置の他の実施の形態の構成を示すブロック図である。図６に示す場合と同様の部分には同一の番号を付してあり、その説明は省略する。
【０１２２】
図１１に構成を示す画像処理装置の特徴量抽出部１０１は、画素の特徴量および画素の位置を示す画素位置情報を、特徴量フレームメモリ２０１および候補ベクトル検出部２０２に供給する。
【０１２３】
図１１に構成を示す画像処理装置において、特徴量抽出部１０１が出力する特徴量および画素位置情報を、特徴量フレームメモリ２０１は、参照フレームＦｒの参照画素の特徴量および参照画素の画素位置情報として記憶し、候補ベクトル検出部２０２は、カレントフレームＦｃの注目画素の特徴量および注目画素の画素位置情報として利用する。
【０１２４】
特徴量フレームメモリ２０１は、画面の一部の領域のそれぞれに対応する、１または複数の対照表を記憶する。特徴量フレームメモリ２０１は、特徴量抽出部１０１から供給された、参照画素の画面上の位置を示す画素位置情報、および特徴量を取得し、参照フレームＦｒの一部の領域であって、参照画素が属する領域に対応する、対照表に画素位置情報を記憶する。より詳しく説明すれば、特徴量フレームメモリ２０１は、参照フレームＦｒの一部の領域であって、参照画素が属する領域に対応する対照表の、特徴量に対応するアドレスの格納領域Ｄに画素位置情報を記憶する。
【０１２５】
図１２は、図６に構成を示す画像処理装置における、画素位置情報の記憶の処理を示す図である。上述したように、図６に構成を示す画像処理装置は、１つのフレームの画面について１つの対照表を記憶する。図６に構成を示す画像処理装置においては、１つのフレームの画面の全ての画素について特徴量が抽出され、１つのフレームの画面の全ての画素についての画素位置情報が、１つの対照表に格納される。
【０１２６】
１つのフレームの横方向の画素の数が、Ｗであり、縦方向の画素の数が、Ｈであるとき、１つのフレームの画素の総数は、Ｗ×Ｈである。１つの画素の画素値が８ビットであれば、１つのフレームの情報量は、Ｗ×Ｈバイトである。
【０１２７】
画素位置情報が、画素の、フレーム上の横方向の位置と、フレーム上の縦方向の位置とを示す座標からなり、フレーム上の横方向の位置が、２バイトで表され、フレーム上の縦方向の位置が、２バイトで表されるとすれば、対照表には、少なくとも、４×Ｗ×Ｈバイトの情報である、画素位置情報が格納されることになる。
【０１２８】
これに対して、図１３に示すように、図１１に構成を示す画像処理装置においては、参照フレームＦｒの画面が、複数の領域に分割される。例えば、参照フレームＦｒの画面２２１は、横方向にＫ、縦方向にＬ、計Ｋ×Ｌの数の領域に分割される。図１１に構成を示す画像処理装置は、図１３に示すように、参照フレームＦｒの画面２２１から分割された領域である分割領域２２２を生成する。
【０１２９】
図１１に構成を示す画像処理装置は、検出しようとする動きベクトルの大きさに対応して、１つの分割領域２２２に対して、１つの拡張分割領域２２３を生成する。例えば、横方向のＶｘの成分を有し、縦方向のＶｙを有する動きベクトルを検出しようとするとき、画像処理装置は、分割領域２２２を、右方向および左方向に、Ｖｘだけ拡張し、上方向および下方向に、Ｖｙだけ拡張して、拡張分割領域２２３を生成する。
【０１３０】
逆に言えば、図１１に構成を示す画像処理装置が、分割領域２２２を、右方向および左方向に、Ｖｘだけ拡張し、上方向および下方向に、Ｖｙだけ拡張して、拡張分割領域２２３を生成するとき、横方向にＶｘ、縦方向にＶｙの範囲の動きベクトルを検出することができる。
【０１３１】
すなわち、拡張分割領域２２３の拡張された領域は、カレントフレームＦｃの注目画素の画面上の座標と同じ座標の参照フレームＦｒの画素が、参照フレームＦｒの１つの分割領域２２２に属するとき、注目画素に対するサーチエリア（の大きさ）を確保するために設けられたものである。
【０１３２】
従って、分割領域２２２の数が、Ｋ×Ｌであるとき、図１１に構成を示す画像処理装置は、Ｋ×Ｌの数の拡張分割領域２２３を生成する。
【０１３３】
画素の総数が、Ｗ×Ｈである参照フレームＦｒを、横方向にＫ、縦方向にＬ、計Ｋ×Ｌの数の領域に分割することにより分割領域２２２が生成され、このように生成された分割領域２２２を、右方向および左方向に、Ｖｘだけ拡張し、上方向および下方向に、Ｖｙだけ拡張して拡張分割領域２２３が生成されたとき、拡張分割領域２２３に属する画素の数は、（Ｗ／Ｋ＋２×Ｖｘ）×（Ｈ／Ｌ＋２×Ｖｙ）である。
【０１３４】
図１１に構成を示す画像処理装置は、１つのフレームの全ての画素について特徴量を抽出し、拡張分割領域２２３毎に対照表を生成し、生成した対照表を特徴量フレームメモリ２０１に記憶する。例えば、拡張分割領域２２３の数が、Ｋ×Ｌであるとき、図１１に構成を示す画像処理装置は、図１３に示すように、拡張分割領域２２３のそれぞれに対応する、Ｋ×Ｌの数の対照表を生成する。
【０１３５】
Ｋ×Ｌの数の対照表のそれぞれには、拡張分割領域２２３の画素の特徴量毎に、画素位置情報が記憶される。拡張分割領域２２３毎の対照表は、例えば、図７に例を示す対照表と同じ構成とすることができる。
【０１３６】
画素位置情報が、画素の、フレーム上の横方向の位置と、フレーム上の縦方向の位置とを示す座標からなり、フレーム上の横方向の位置が、２バイトで表され、フレーム上の縦方向の位置が、２バイトで表されるとすれば、１つの拡張分割領域２２３に対応する１つの対照表には、少なくとも、４×（Ｗ／Ｋ＋２×Ｖｘ）×（Ｈ／Ｌ＋２×Ｖｙ）バイトの情報である、画素位置情報が格納されることになる。従って、Ｋ×Ｌの数の対照表には、全体として、Ｋ×Ｌ×４×（Ｗ／Ｋ＋２×Ｖｘ）×（Ｈ／Ｌ＋２×Ｖｙ）バイトの情報である、画素位置情報が格納される。言い換えれば、所定の数の対照表には、全体として、４×（（１つの拡張分割領域２２３の画素数）／（１つの分割領域２２２の画素数））×Ｗ×Ｈバイトの情報である、画素位置情報が格納される。
【０１３７】
図１４は、分割領域２２２および拡張分割領域２２３を説明する図である。
【０１３８】
画素２４１は、カレントフレームＦｃの注目画素の画面上の座標と同じ座標の参照フレームＦｒの画素である。図１４中の点線で示すサーチエリア２４２は、画素２４１を中心とした、所定の幅および所定の高さの領域である。動いた先が注目画素である画素が、サーチエリア２４２に属する画素から選択される。すなわち、画像処理装置は、動いた先が注目画素である画素の位置を、サーチエリア２４２に属する画素の位置から選択する。
【０１３９】
例えば、画素２４１から左方向に１０画素、右方向に１０画素、画素２４１から上方向に１０画素、下方向に１０画素の領域が、サーチエリア２４２とされる。
【０１４０】
カレントフレームＦｃの注目画素の画面上の座標と同じ座標の参照フレームＦｒの画素２４１が、分割領域２２２の左上に位置するとき、画素２４１を中心とするサーチエリア２４２が含まれるように、拡張分割領域２２３が決定される。例えば、画素２４１から左方向に１０画素、画素２４１から上方向に１０画素の領域が、サーチエリア２４２に属するとするとき、拡張分割領域２２３は、分割領域２２２に対して、左方向に１０画素、上方向に１０画素、拡張される。
【０１４１】
同様に、カレントフレームＦｃの注目画素の画面上の座標と同じ座標の参照フレームＦｒの画素２４１が、分割領域２２２の右上に位置するとき、画素２４１を中心とするサーチエリア２４２が含まれるように、拡張分割領域２２３が決定される。例えば、画素２４１から右方向に１０画素、画素２４１から上方向に１０画素の領域が、サーチエリア２４２に属するとするとき、拡張分割領域２２３は、分割領域２２２に対して、右方向に１０画素、上方向に１０画素、拡張される。
【０１４２】
カレントフレームＦｃの注目画素の画面上の座標と同じ座標の参照フレームＦｒの画素２４１が、分割領域２２２の左下に位置するとき、画素２４１を中心とするサーチエリア２４２が含まれるように、拡張分割領域２２３が決定される。例えば、画素２４１から左方向に１０画素、画素２４１から下方向に１０画素の領域が、サーチエリア２４２に属するとするとき、拡張分割領域２２３は、分割領域２２２に対して、左方向に１０画素、下方向に１０画素、拡張される。
【０１４３】
同様に、カレントフレームＦｃの注目画素の画面上の座標と同じ座標の参照フレームＦｒの画素２４１が、分割領域２２２の右下に位置するとき、画素２４１を中心とするサーチエリア２４２が含まれるように、拡張分割領域２２３が決定される。例えば、画素２４１から右方向に１０画素、画素２４１から下方向に１０画素の領域が、サーチエリア２４２に属するとするとき、拡張分割領域２２３は、分割領域２２２に対して、右方向に１０画素、下方向に１０画素、拡張される。
【０１４４】
このように、検出しようとする、注目画素の動きベクトルの大きさ（画素を単位とした大きさ）だけ、分割領域２２２を拡張して拡張分割領域２２３を生成することにより、注目画素のカレントフレームＦｃ上の位置と同じ、参照フレームＦｒ上の位置の画素が、分割領域２２２に属する場合、動いた先が注目画素である参照フレームＦｒ上の画素は、拡張分割領域２２３に属することになる。
【０１４５】
ｃｓａｗは、画素を基準とした、分割領域２２２の幅を示す。ｃｓａｈは、画素を基準とした、分割領域２２２の高さを示す。
【０１４６】
ａｓａｗは、画素を基準とした、拡張分割領域２２３の幅を示す。ａｓａｈは、画素を基準とした、拡張分割領域２２３の高さを示す。
【０１４７】
ｓａｗは、画素を基準とした、サーチエリア２４２の幅を示す。ｓａｈは、画素を基準とした、サーチエリア２４２の高さを示す。
【０１４８】
拡張分割領域２２３の分割領域２２２に対する拡張の幅（左方向または右方向のうちの一方の拡張の幅）を、ｈｍｓａｗで示す。拡張分割領域２２３の分割領域２２２に対する拡張の高さ（上方向または下方向のうちの一方の拡張の高さ）を、ｈｍｓａｈで示す。
【０１４９】
分割領域２２２の幅ｃｓａｗ、拡張分割領域２２３の幅ａｓａｗ、および拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗについて、式（２）が成立する。
ａｓａｗ＝ｃｓａｗ＋２×ｈｍｓａｗ                                        （２）
【０１５０】
分割領域２２２の高さｃｓａｈ、拡張分割領域２２３の高さａｓａｈ、および拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈについて、式（３）が成立する。
ａｓａｈ＝ｃｓａｈ＋２×ｈｍｓａｈ                                        （３）
【０１５１】
図１５は、拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗを１０とし、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈを１０としたときの、分割領域２２２のサイズ、拡張分割領域２２３のサイズ、およびメモリ倍率の例を示す図である。
【０１５２】
メモリ倍率は、１つの対照表に画面全ての画素位置情報を格納する場合を基準とした、全ての対照表に記憶される画素位置情報の量の比率を示す。メモリ倍率ｍｔは、式（４）で求めることができる。
ｍｔ＝（ａｓａｗ×ａｓａｈ）／（ｃｓａｗ×ｃｓａｈ）                              （４）
【０１５３】
拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗが１０であり、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈが１０なので、サーチエリア２４２の幅ｓａｗは、２１であり、サーチエリア２４２の高さｓａｈは、２１である。
【０１５４】
分割領域２２２の幅ｃｓａｗを５とし、分割領域２２２の高さｃｓａｈを５としたとき、拡張分割領域２２３の幅ａｓａｗは、２５となり、拡張分割領域２２３の高さａｓａｈは、２５となり、メモリ倍率ｍｔは、２５となる。
【０１５５】
分割領域２２２の幅ｃｓａｗを１０とし、分割領域２２２の高さｃｓａｈを１０としたとき、拡張分割領域２２３の幅ａｓａｗは、３０となり、拡張分割領域２２３の高さａｓａｈは、３０となり、メモリ倍率ｍｔは、９となる。
【０１５６】
分割領域２２２の幅ｃｓａｗを２０とし、分割領域２２２の高さｃｓａｈを２０としたとき、拡張分割領域２２３の幅ａｓａｗは、４０となり、拡張分割領域２２３の高さａｓａｈは、４０となり、メモリ倍率ｍｔは、４となる。
【０１５７】
図１６は、分割領域２２２の幅ｃｓａｗを１０とし、分割領域２２２の高さｃｓａｈを１０としたときの、拡張分割領域２２３の分割領域２２２に対する拡張の幅および高さ、拡張分割領域２２３のサイズ、およびメモリ倍率の例を示す図である。
【０１５８】
拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗを５とし、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈを１０としたとき、拡張分割領域２２３の幅ａｓａｗは、２０となり、拡張分割領域２２３の高さａｓａｈは、３０となり、メモリ倍率ｍｔは、６となる。この場合、拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗが５であり、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈが１０なので、サーチエリア２４２の幅ｓａｗは、１１であり、サーチエリア２４２の高さｓａｈは、２１である。
【０１５９】
拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗを１０とし、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈを１０としたとき、拡張分割領域２２３の幅ａｓａｗは、３０となり、拡張分割領域２２３の高さａｓａｈは、３０となり、メモリ倍率ｍｔは、９となる。この場合、拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗが１０であり、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈが１０なので、サーチエリア２４２の幅ｓａｗは、２１であり、サーチエリア２４２の高さｓａｈは、２１である。
【０１６０】
拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗを２０とし、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈを１０としたとき、拡張分割領域２２３の幅ａｓａｗは、５０となり、拡張分割領域２２３の高さａｓａｈは、３０となり、メモリ倍率ｍｔは、１５となる。この場合、拡張分割領域２２３の分割領域２２２に対する拡張の幅ｈｍｓａｗが２０であり、拡張分割領域２２３の分割領域２２２に対する拡張の高さｈｍｓａｈが１０なので、サーチエリア２４２の幅ｓａｗは、４１であり、サーチエリア２４２の高さｓａｈは、２１である。
【０１６１】
このように、検出しようとする動きベクトルの大きさなどを基に、拡張分割領域２２３の分割領域２２２に対する拡張の幅、および拡張分割領域２２３の分割領域２２２に対する拡張の高さを任意に設定することができる。
【０１６２】
サーチエリア２４２をより広くする場合、すなわち、拡張分割領域２２３の分割領域２２２に対する拡張の幅、および拡張分割領域２２３の分割領域２２２に対する拡張の高さをより大きくする場合、メモリ倍率は高くなる。従って、より大きい動きベクトルを検出する場合、サーチエリア２４２をより広く、すなわち、拡張分割領域２２３の分割領域２２２に対する拡張の幅、および拡張分割領域２２３の分割領域２２２に対する拡張の高さをより大きくする必要があるので、より広いメモリ空間が必要となる。
【０１６３】
図１７は、特徴量フレームメモリ２０１に記憶されている、複数の対照表の例を示す図である。
【０１６４】
特徴量フレームメモリ２０１に記憶されている複数の対照表のそれぞれは、１つの拡張分割領域２２３に対応するので、特徴量フレームメモリ２０１に記憶されている対照表の数は、拡張分割領域２２３の数に対応する。例えば、拡張分割領域２２３の数が、Ｋ×Ｌであるとき、特徴量フレームメモリ２０１は、Ｋ×Ｌの数の対照表を記憶する。
【０１６５】
Ｋ×Ｌ＝Ｊであるとき、特徴量フレームメモリ２０１には、Ｊ個の対照表２５１−１乃至２５１−Ｊが記憶される。対照表２５１−１乃至２５１−Ｊのそれぞれは、図７に構成を示す対照表と同じ構成とすることができる。
【０１６６】
この場合において、対照表のフラグアドレスの最大値Ｍは、拡張分割領域２２３に含まれる画素の数／Ｎとすることができる。１つの特徴量に対応する、拡張分割領域２２３に含まれる画素の数／Ｎを超える画素位置情報が、対照表に格納されるとき、例えば、他のアドレスの空いている格納領域Ｄに画素位置情報が格納されるとともに、画素位置情報が格納された他のアドレスが記憶される。
【０１６７】
なお、拡張分割領域２２３の数と同じ数の特徴量フレームメモリ２０１を設け、特徴量フレームメモリ２０１毎に１つの対照表を記憶するようにしてもよい。
【０１６８】
次に、図１８を参照して、メモリ倍率ｍｔが整数であるときの、特徴量フレームメモリ２０１における、画素位置情報の格納の処理を説明する。
【０１６９】
参照フレームＦｒの画面２２１の横方向の画素の数が、Ｗであり、縦方向の画素の数が、Ｈであるとき、参照フレームＦｒの画面２２１の画素の総数は、Ｗ×Ｈである。画面２２１の画素の総数Ｗ×Ｈ、分割領域２２２の幅ｃｓａｗ（分割領域２２２の横に並ぶ画素の数）、および分割領域２２２の高さｃｓａｈ（分割領域２２２の縦に並ぶ画素の数）から、分割領域２２２の数ｎｃｓａは、式（５）で求めることができる。
ｎｃｓａ＝（Ｗ×Ｈ）／（ｃｓａｗｔ×ｃｓａｈ）                              （５）
【０１７０】
メモリ倍率ｍｔが整数であるとき、１つの拡張分割領域２２３に含まれる分割領域２２２の数は、メモリ倍率ｍｔに等しい。逆に言えば、１つの分割領域２２２は、メモリ倍率ｍｔの数の拡張分割領域２２３に含まれる。
【０１７１】
従って、１つの画素（のブロック）の特徴量は、ｍｔ個の拡張分割領域２２３に対応するｍｔ個の対応表に格納される。
【０１７２】
例えば、図１８に示すように、分割領域２２２の幅ｃｓａｗを１０とし、分割領域２２２の高さｃｓａｈを１０とし、拡張分割領域２２３の幅ａｓａｗを３０とし、拡張分割領域２２３の高さａｓａｈを３０としたとき、式（４）より、メモリ倍率ｍｔは、９となる。
【０１７３】
分割領域２２２の幅ｃｓａｗを１０とし、分割領域２２２の高さｃｓａｈを１０とし、拡張分割領域２２３の幅ａｓａｗを３０とし、拡張分割領域２２３の高さａｓａｈを３０としたとき、１つの画素（のブロック）の特徴量は、９個の拡張分割領域２２３に対応する９個の対応表に格納される。
【０１７４】
図１８に示すように、分割領域２２２の幅ｃｓａｗを１０とし、分割領域２２２の高さｃｓａｈを１０とし、拡張分割領域２２３の幅ａｓａｗを３０とし、拡張分割領域２２３の高さａｓａｈを３０としたとき、１つの拡張分割領域２２３には、９個の分割領域２２２が含まれる。
【０１７５】
逆に、分割領域２２２の幅ｃｓａｗを１０とし、分割領域２２２の高さｃｓａｈを１０とし、拡張分割領域２２３の幅ａｓａｗを３０とし、拡張分割領域２２３の高さａｓａｈを３０としたとき、１つの分割領域２２２は、９つの拡張分割領域２２３に含まれることになる。
【０１７６】
図１８において、１乃至２５は、分割領域２２２の番号ｃｎである。
【０１７７】
例えば、番号ｃｎが１３である分割領域２２２は、番号ｃｎが１である分割領域２２２、番号ｃｎが２である分割領域２２２、番号ｃｎが３である分割領域２２２、番号ｃｎが６である分割領域２２２、番号ｃｎが７である分割領域２２２、番号ｃｎが８である分割領域２２２、番号ｃｎが１１である分割領域２２２、番号ｃｎが１２である分割領域２２２、および番号ｃｎが１３である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１７８】
番号ｃｎが１３である分割領域２２２は、番号ｃｎが２である分割領域２２２、番号ｃｎが３である分割領域２２２、番号ｃｎが４である分割領域２２２、番号ｃｎが７である分割領域２２２、番号ｃｎが８である分割領域２２２、番号ｃｎが９である分割領域２２２、番号ｃｎが１２である分割領域２２２、番号ｃｎが１３である分割領域２２２、および番号ｃｎが１４である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１７９】
番号ｃｎが１３である分割領域２２２は、番号ｃｎが３である分割領域２２２、番号ｃｎが４である分割領域２２２、番号ｃｎが５である分割領域２２２、番号ｃｎが８である分割領域２２２、番号ｃｎが９である分割領域２２２、番号ｃｎが１０である分割領域２２２、番号ｃｎが１３である分割領域２２２、番号ｃｎが１４である分割領域２２２、および番号ｃｎが１５である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１８０】
また、番号ｃｎが１３である分割領域２２２は、番号ｃｎが６である分割領域２２２、番号ｃｎが７である分割領域２２２、番号ｃｎが８である分割領域２２２、番号ｃｎが１１である分割領域２２２、番号ｃｎが１２である分割領域２２２、番号ｃｎが１３である分割領域２２２、番号ｃｎが１６である分割領域２２２、番号ｃｎが１７である分割領域２２２、および番号ｃｎが１８である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１８１】
番号ｃｎが１３である分割領域２２２は、番号ｃｎが７である分割領域２２２、番号ｃｎが８である分割領域２２２、番号ｃｎが９である分割領域２２２、番号ｃｎが１２である分割領域２２２、番号ｃｎが１３である分割領域２２２、番号ｃｎが１４である分割領域２２２、番号ｃｎが１７である分割領域２２２、番号ｃｎが１８である分割領域２２２、および番号ｃｎが１９である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１８２】
番号ｃｎが１３である分割領域２２２は、番号ｃｎが８である分割領域２２２、番号ｃｎが９である分割領域２２２、番号ｃｎが１０である分割領域２２２、番号ｃｎが１３である分割領域２２２、番号ｃｎが１４である分割領域２２２、番号ｃｎが１５である分割領域２２２、番号ｃｎが１８である分割領域２２２、番号ｃｎが１９である分割領域２２２、および番号ｃｎが２０である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１８３】
さらに、番号ｃｎが１３である分割領域２２２は、番号ｃｎが１１である分割領域２２２、番号ｃｎが１２である分割領域２２２、番号ｃｎが１３である分割領域２２２、番号ｃｎが１６である分割領域２２２、番号ｃｎが１７である分割領域２２２、番号ｃｎが１８である分割領域２２２、番号ｃｎが２１である分割領域２２２、番号ｃｎが２２である分割領域２２２、および番号ｃｎが２３である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１８４】
番号ｃｎが１３である分割領域２２２は、番号ｃｎが１２である分割領域２２２、番号ｃｎが１３である分割領域２２２、番号ｃｎが１４である分割領域２２２、番号ｃｎが１７である分割領域２２２、番号ｃｎが１８である分割領域２２２、番号ｃｎが１９である分割領域２２２、番号ｃｎが２２である分割領域２２２、番号ｃｎが２３である分割領域２２２、および番号ｃｎが２４である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１８５】
番号ｃｎが１３である分割領域２２２は、番号ｃｎが１３である分割領域２２２、番号ｃｎが１４である分割領域２２２、番号ｃｎが１５である分割領域２２２、番号ｃｎが１８である分割領域２２２、番号ｃｎが１９である分割領域２２２、番号ｃｎが２０である分割領域２２２、番号ｃｎが２３である分割領域２２２、番号ｃｎが２４である分割領域２２２、および番号ｃｎが２５である分割領域２２２からなる拡張分割領域２２３に含まれる。
【０１８６】
このように、分割領域２２２の幅ｃｓａｗを１０とし、分割領域２２２の高さｃｓａｈを１０とし、拡張分割領域２２３の幅ａｓａｗを３０とし、拡張分割領域２２３の高さａｓａｈを３０としたとき、１つの分割領域２２２は、異なる９つの拡張分割領域２２３に含まれる。
【０１８７】
拡張分割領域２２３の番号ａｓａｎを、拡張分割領域２２３の中央に位置する分割領域２２２の番号ｃｎで表すことができる。
【０１８８】
この場合、例えば、番号ｃｎが１３の分割領域２２２は、番号ａｓａｎが、７，８，９，１２，１３，１４，１７，１８、および１９である拡張分割領域２２３のそれぞれに含まれる。
【０１８９】
拡張分割領域２２３の番号ａｓａｎを、拡張分割領域２２３の中央に位置する分割領域２２２の番号ｃｎで表し、上下に接する分割領域２２２の番号ｃｎの差をｆｒａｃｗｃｓａｗで表すとき、番号ｃｎの分割領域２２２に属する画素の画素位置情報は、番号ａｓａｎが、ｃｎ−ｆｒａｃｗｃｓａｗ−１，ｃｎ−ｆｒａｃｗｃｓａｗ，ｎ−ｆｒａｃｗｃｓａｗ＋１，ｃｎ−１，ｃｎ，ｃｎ＋１，ｃｎ＋ｆｒａｃｗｃｓａｗ−１，ｃｎ＋ｆｒａｃｗｃｓａｗ、およびｃｎ＋ｆｒａｃｗｃｓａｗ＋１である拡張分割領域２２３のそれぞれに対応する、対照表に記憶される。例えば、上下に接する分割領域２２２の番号ｃｎの差ｆｒａｃｗｃｓａｗが５であるとき、番号ｃｎが１３である分割領域２２２に属する画素の画素位置情報は、番号ａｓａｎが、７，８，９，１２，１３，１４，１７，１８、および１９である拡張分割領域２２３のそれぞれに対応する、対照表に記憶される。特徴量フレームメモリ２０１に記憶されている対照表は、例えば、拡張分割領域２２３の番号ａｓａｎにより特定される。
【０１９０】
このように、特徴量フレームメモリ２０１は、拡張分割領域２２３のそれぞれに対応する、対照表の特徴量に対応するアドレスの格納領域Ｄに画素位置情報を記憶する。
【０１９１】
特徴量フレームメモリ２０１は、カレントフレームＦｃ（現在のフレーム）に対応する画素位置情報と、参照フレームＦｒ（１つ前のフレーム）に対応する画素位置情報とをそれぞれに記憶し、それぞれ読み出すことができる。すなわち、特徴量フレームメモリ２０１は、カレントフレームＦｃに対応する対照表（の格納領域Ｄ）のページと、参照フレームＦｒに対応する対照表（の格納領域Ｄ）のページとを有し、ページを切り替えることにより、特徴量抽出部１０１から供給されたカレントフレームＦｃの画素位置情報を記憶するとともに、記憶されている参照フレームＦｒの画素位置情報を読み出して、候補ベクトル検出部２０２に供給することができる。
【０１９２】
図１１に戻り、候補ベクトル検出部２０２は、特徴量抽出部１０１から供給された、カレントフレームＦｃの注目画素の特徴量、および注目画素の画素位置情報を基に、注目画素の画面上の位置と同じ画面上の位置の参照フレームＦｒの画素が属する分割領域２２２を拡張した拡張分割領域２２３に対応する対照表から、注目画素の特徴量と同じ特徴量を有する、参照フレームＦｒの画素の画素位置を選択することにより、候補ベクトルを検出する。また、候補ベクトル検出部２０２は、特徴量抽出部１０１から供給された、カレントフレームＦｃの注目画素の特徴量、および注目画素の画素位置情報を基に、注目画素の画面上の位置と同じ画面上の位置の参照フレームＦｒの画素が属する分割領域２２２を拡張した拡張分割領域２２３に対応する対照表から、注目画素の特徴量の近傍の特徴量を有する、参照フレームＦｒの画素の画素位置を選択することにより、候補ベクトルを検出する。
【０１９３】
すなわち、候補ベクトル検出部２０２は、注目画素の画面上の位置と同じ画面上の位置の参照フレームＦｒの画素が属する分割領域２２２を拡張した拡張分割領域２２３に対応する対照表の格納領域Ｄに記憶されている、参照画素の位置を示す画素位置情報を基に、注目画素の特徴量と同じ、または、近傍の特徴量の参照画素の位置を選択する。候補ベクトル検出部２０２が選択する参照画素の位置には、動いた先が注目画素である参照画素の位置が含まれる。候補ベクトル検出部２０２は、選択された参照画素の位置から、注目画素の動きベクトルの候補である候補ベクトルを算出する。
【０１９４】
候補ベクトル検出部２０２は、候補ベクトルの数と共に、候補ベクトルをサーチエリア内候補ベクトル選択部２０３に供給する。
【０１９５】
サーチエリア内候補ベクトル選択部２０３は、候補ベクトル検出部２０２から供給された候補ベクトルの中から、サーチエリア２４２に属する画素を示している候補ベクトルを選択し、選択された候補ベクトルの数と共に、選択された候補ベクトルをブロックマッチング部２０４に供給する。
【０１９６】
ブロックマッチング部２０４は、サーチエリア内候補ベクトル選択部２０３から供給された候補ベクトルについて、候補ベクトルで示される、参照フレームＦｒの画素に対応するブロックと、カレントフレームＦｃの注目画素に対応するブロックとのマッチングを調べる。すなわち、ブロックマッチング部２０４は、候補ベクトルで示される、参照フレームＦｒの画素に対応するブロックに含まれる画素の画素値と、カレントフレームＦｃの注目画素に対応するブロックに含まれる画素の画素値との誤差値を算出する。参照フレームＦｒの画素に対応するブロックに含まれる画素の数と、カレントフレームＦｃの注目画素に対応するブロックに含まれる画素の数は、同じであってもよく、参照フレームＦｒの画素に対応するブロックに含まれる画素の数が、カレントフレームＦｃの注目画素に対応するブロックに含まれる画素の数より多くてもよい。
【０１９７】
例えば、ブロックマッチング部２０４は、候補ベクトルで示される、参照フレームＦｒの画素を中心とした５×５画素のブロックに含まれる画素の画素値と、カレントフレームＦｃの注目画素を中心とした５×５画素のブロックに含まれる画素の画素値との差分の２乗の和を誤差値として算出する。
【０１９８】
なお、誤差値は、画素値の差分の絶対値和など、他の種類のものであってもよく、誤差値の演算方式は、本発明を限定するものではない。
【０１９９】
ブロックマッチング部２０４は、候補ベクトル毎に算出した誤差値を、候補ベクトルおよび候補ベクトル数と共に、最小誤差ベクトル選択部２０５に供給する。
【０２００】
最小誤差ベクトル選択部２０５は、ブロックマッチング部２０４から供給された、誤差値、候補ベクトル、および候補ベクトル数を基に、誤差が最小である候補ベクトルを選択して、選択した候補ベクトルを動きベクトルとして出力する。
【０２０１】
なお、参照フレームＦｒの参照画素の特徴量を抽出する特徴量抽出部と、カレントフレームＦｃの注目画素の特徴量を抽出する特徴量抽出部とを別個に設けるようにしてもよい。
【０２０２】
図１９は、拡張分割領域２２３を３０×３０画素の領域とし、サーチエリア２４２を２１×２１画素の領域とした場合の１つの注目画素に対する動きベクトルの検出の処理に要する時間と、拡張分割領域２２３を参照フレームＦｒの全画面とし、サーチエリア２４２を２１×２１画素の領域とした場合の１つの注目画素に対する動きベクトルの検出の処理に要する時間とを比較する図である。
【０２０３】
図１１に構成を示す画像処理装置において、１つの注目画素に対する処理に要する時間ｃｌｋｂｍは、式（６）で算出される。
ｃｌｋｂｍ＝ｎｃｓａｍａｘ×ｂｍｘ×ｂｍｙ＋（ｎｃａｓａｍａｘ−ｎｃｓａｍａｘ）            （６）
【０２０４】
式（６）において、ｎｃｓａｍａｘは、サーチエリア２４２に属する画素の数、すなわち、サーチエリア２４２に対応する対照表に格納される画素位置情報の数を示す。
【０２０５】
サーチエリア２４２を２１×２１画素の領域としたとき、ｎｃｓａｍａｘは、４４１である。
【０２０６】
式（６）において、ｂｍｘは、ブロックマッチング部２０４において、ブロックマッチングの処理の対象となる、カレントフレームＦｃの注目画素に対応するブロックの幅（横方向に並ぶ、ブロックに属する画素の数）（この場合、参照フレームＦｒの画素に対応するブロックの幅に等しい）であり、ｂｍｙは、ブロックマッチング部２０４において、ブロックマッチングの処理の対象となる、カレントフレームＦｃの注目画素に対応するブロックの高さ（縦方向に並ぶ、ブロックに属する画素の数）（この場合、参照フレームＦｒの画素に対応するブロックの高さに等しい）である。従って、ｂｍｘ×ｂｍｙは、ロックマッチング部２０４において、ブロックマッチングの処理の対象となる、カレントフレームＦｃの注目画素に対応するブロックに含まれる画素の数である。
【０２０７】
ｂｍｘを５、ｂｍｙを５としたとき、ｂｍｘ×ｂｍｙは、２５である。
【０２０８】
式（６）において、ｎｃａｓａｍａｘは、拡張分割領域２２３に属する画素の数、すなわち、拡張分割領域２２３に対応する対照表に格納される画素位置情報の数を示す。
【０２０９】
拡張分割領域２２３を３０×３０画素の領域としたとき、ｎｃａｓａｍａｘは、９００である。拡張分割領域２２３を参照フレームＦｒの全画面としたとき、ｎｃａｓａｍａｘを、１０万とする。
【０２１０】
式（６）の右辺の第１項、すなわち、ｎｃｓａｍａｘ×ｂｍｘ×ｂｍｙは、サーチエリア２４２に属する全ての画素の特徴量が、注目画素の特徴量と同じ場合、可能性としてある、ブロックマッチングの処理における最大演算量を示す。式（６）の右辺の第２項、すなわち、（ｎｃａｓａｍａｘ−ｎｃｓａｍａｘ）は、特徴量フレームメモリ２０１から対照表を読み出す処理に要する時間である。
【０２１１】
拡張分割領域２２３を３０×３０画素の領域とし、サーチエリア２４２を２１×２１画素の領域とした場合の１つの注目画素に対する動きベクトルの検出の処理に要する時間ｃｌｋｂｍは、１１４８４である。
【０２１２】
これに対して、拡張分割領域２２３を参照フレームＦｒの全画面とし、サーチエリア２４２を２１×２１画素の領域とした場合の１つの注目画素に対する動きベクトルの検出の処理に要する時間ｃｌｋｂｍは、１１０５８４である。
【０２１３】
このように、参照フレームＦｒの一部の領域毎に対照表を生成し、参照フレームＦｒの一部の領域毎の対照表を基に、動きベクトルを検出するようにしたとき、より迅速に動きベクトルを算出することができるようになる。
【０２１４】
図２０は、図１１に構成を示す画像処理装置による、動きベクトルの検出の処理を説明するフローチャートである。
【０２１５】
ステップＳ２０１において、特徴量抽出部１０１および特徴量フレームメモリ２０１は、参照フレームＦｒの画素位置情報の格納の処理を実行することにより、拡張分割領域２２３に対応する対照表毎に、画素位置情報を記憶する。画素位置情報の格納の処理の詳細は、図２１のフローチャートを参照して、後述する。
【０２１６】
ステップＳ２０２において、特徴量抽出部１０１乃至最小誤差ベクトル選択部２０５は、注目画素に対応する動きベクトルの検出の処理を実行して、処理は終了する。注目画素に対応する動きベクトルの検出の処理において、注目画素の特徴量と同じ特徴量を有する、参照フレームＦｒの画素の画素位置の中から、動いた先が注目画素である画素の位置が選択され、選択された画素位置から注目画素の動きベクトルが算出される。注目画素に対応する動きベクトルの検出の処理の詳細は、図２２のフローチャートを参照して、後述する。
【０２１７】
図２１は、ステップＳ２０１に対応する、画素位置情報の格納の処理を説明するフローチャートである。
【０２１８】
ステップＳ２２１において、特徴量フレームメモリ２０１は、特徴量フレームメモリ２０１に記憶されている全ての対照表のデータを初期化する。例えば、特徴量フレームメモリ２０１は、これから画素位置情報を書き込もうとするページの、全ての対照表について、フラグアドレスが０である格納領域Ｄに０を設定し、フラグアドレスが１乃至Ｍである格納領域Ｄにヌル（ｎｕｌｌ）を設定することにより、データを初期化する。
【０２１９】
ステップＳ２２２において、特徴量抽出部１０１は、カウンタ変数ｎを初期化する。カウンタ変数ｎは、処理の対象となる画素の数を数えるための変数である。例えば、特徴量抽出部１０１は、ステップＳ２２２において、カウンタ変数ｎに１を設定する。
【０２２０】
ステップＳ２２３において、特徴量抽出部１０１は、参照フレームＦｒの画素のなかからまだ参照画素とされていない画素を選択して参照画素とする。特徴量抽出部１０１は、参照画素に対応するブロックの特徴量を算出することにより、参照画素の特徴量を抽出し、参照画素の位置を示す画素位置情報と共に、抽出した特徴量を特徴量フレームメモリ２０１および候補ベクトル検出部２０２に供給する。例えば、特徴量抽出部１０１は、参照画素を中心とした、３×３のブロックに含まれる画素の画素値をラスタスキャン順に並べた値である特徴量を算出する。
【０２２１】
ステップＳ２２４において、特徴量フレームメモリ２０１は、特徴量抽出部１０１から供給された画素位置情報を基に、参照画素の位置に対応する分割領域２２２の番号ｃｎを算出する。例えば、特徴量フレームメモリ２０１は、画素位置情報で示される、参照画素の画面上の座標から、分割領域２２２の番号ｃｎを算出する。
【０２２２】
より詳細に説明すれば、例えば、特徴量フレームメモリ２０１は、参照画素の画面上の縦方向の位置を示すｙ座標を、分割領域２２２の高さｃｓａｈで除算する。特徴量フレームメモリ２０１は、除算の結果得られた商に、参照フレームＦｒに横方向に配置される分割領域２２２の数（例えば、図１３のＫ）を乗算する。
【０２２３】
さらに、特徴量フレームメモリ２０１は、参照画素の画面上の横方向の位置を示すｘ座標を、分割領域２２２の幅ｃｓａｗで除算する。特徴量フレームメモリ２０１は、参照画素の画面上の座標のｘ座標を、分割領域２２２の幅ｃｓａｗで除算した結果得られた商を、乗算の結果得られた積に加算し、参照画素の画面上の座標のｘ座標を、分割領域２２２の幅ｃｓａｗで除算した結果の余りが１以上であるとき、さらに１を加算することにより、分割領域２２２の番号ｃｎを得る。
【０２２４】
ステップＳ２２５において、特徴量フレームメモリ２０１は、カウンタ変数ｍを初期化する。カウンタ変数ｍは、画素位置情報が格納される対照表の数を数えるための変数である。例えば、特徴量フレームメモリ２０１は、ステップＳ２２５において、カウンタ変数ｍに１を設定する。
【０２２５】
ステップＳ２２６において、特徴量フレームメモリ２０１は、分割領域２２２の番号ｃｎおよびカウンタ変数ｍで特定される対照表から、特徴量に対応する画素位置情報の数を読み出す。すなわち、特徴量フレームメモリ２０１は、分割領域２２２の番号ｃｎおよびカウンタ変数ｍから、拡張分割領域２２３を特定し、特定された拡張分割領域２２３に対応する対照表から、特徴量に対応する画素位置情報の数を読み出す。
【０２２６】
例えば、図１８に示す例において、分割領域２２２の番号ｃｎが１３であり、カウンタ変数ｍが１である場合、番号ａｓａｎが、７である拡張分割領域２２３が選択される。特徴量フレームメモリ２０１は、７である拡張分割領域２２３に対応する対照表から、特徴量に対応する画素位置情報の数を読み出す。特徴量フレームメモリ２０１は、７である拡張分割領域２２３に対応する対照表の、特徴量に対応する特徴量アドレスと、０であるフラグアドレスで特定される格納領域Ｄから画素位置情報の数を読み出す。
【０２２７】
図１８の例において、カウンタ変数ｍが１から９まで順に変化したとき、特徴量フレームメモリ２０１は、番号ａｓａｎが、７，８，９，１２，１３，１４，１７，１８、および１９である拡張分割領域２２３を順に選択し、７，８，９，１２，１３，１４，１７，１８、および１９である拡張分割領域２２３のそれぞれに対応する対照表を順に選択する。
【０２２８】
ステップＳ２２７において、特徴量フレームメモリ２０１は、ステップＳ２２６の処理で読み出した、特徴量に対応する画素位置情報の数をインクリメントする。すなわち、特徴量フレームメモリ２０１は、ステップＳ２２６の処理で読み出した、特徴量に対応する画素位置情報の数に１を加算する。
【０２２９】
ステップＳ２２８において、特徴量フレームメモリ２０１は、分割領域２２２の番号ｃｎおよびカウンタ変数ｍで特定される対照表に、ステップＳ２２７の処理でインクリメントされた、特徴量に対応する画素位置情報の数を記憶させる。例えば、特徴量フレームメモリ２０１は、特徴量に対応する特徴量アドレスがｋであるとき、分割領域２２２の番号ｃｎおよびカウンタ変数ｍで特定される対照表の、アドレス（ｋ，０）の格納領域Ｄに、インクリメントされた画素位置情報の数を書き込む。
【０２３０】
ステップＳ２２９において、特徴量フレームメモリ２０１は、分割領域２２２の番号ｃｎおよびカウンタ変数ｍで特定される対照表の、特徴量に対応する特徴量アドレスと、画素位置情報の数に対応するフラグアドレスとから特定されるアドレスの格納領域Ｄに、画素位置情報を書き込む。例えば、特徴量フレームメモリ１０２は、参照画素の特徴量に対応する特徴量アドレスがｋであり、画素位置情報の数がｑであるとき、分割領域２２２の番号ｃｎおよびカウンタ変数ｍで特定される対照表の、アドレス（ｋ，ｑ）の格納領域Ｄに、参照画素の画素位置を示す画素位置情報を書き込む。
【０２３１】
ステップＳ２３０において、特徴量フレームメモリ２０１は、カウンタ変数ｍの値が、１つの分割領域２２２が属する拡張分割領域２２３の数に等しいか否か、すなわち、カウンタ変数ｍの値が、式（４）で算出されるメモリ倍率ｍｔに等しいか否かを判定し、カウンタ変数ｍの値が、１つの分割領域２２２が属する拡張分割領域２２３の数に等しくないと判定された場合、まだ画素位置情報を格納すべき対照表があるので、ステップＳ２３１に進み、カウンタ変数ｍをインクリメントして、ステップＳ２２６に戻り、次のカウンタ変数ｍで特定される対照表に画素位置情報を格納する処理を繰り返す。
【０２３２】
ステップＳ２３０において、カウンタ変数ｍの値が、１つの分割領域２２２が属する拡張分割領域２２３の数に等しいと判定された場合、画素位置情報を格納すべき対照表の全てに画素位置情報が格納されたので、ステップＳ２３２に進み、カウンタ変数ｎをインクリメントする。すなわち、特徴量抽出部１０１は、カウンタ変数ｎに１を加算する。
【０２３３】
ステップＳ２３３において、特徴量抽出部１０１は、カウンタ変数ｎの値が、フレームの画素の数に等しいか否かを判定し、カウンタ変数ｎの値が、フレームの画素の数に等しくないと判定された場合、まだ、参照画素とされていない画素がある、すなわち特徴量が抽出されていない画素があるので、ステップＳ２２３に戻り、上述した処理を繰り返し、次の参照画素について特徴量を抽出して、画素位置情報を特徴量フレームメモリ２０１に格納する。
【０２３４】
ステップＳ２３３において、カウンタ変数ｎの値が、フレームの画素の数に等しいと判定された場合、フレームの全ての画素が参照画素とされ、フレームの全ての画素の特徴量が抽出されて、全ての画素に対応する画素位置情報が特徴量フレームメモリ２０１の格納すべき対照表に格納されたので、処理は終了する。
【０２３５】
図２２は、ステップＳ２０２に対応する、注目画素に対応する動きベクトルの検出の処理を説明するフローチャートである。
【０２３６】
ステップＳ２５１において、特徴量抽出部１０１は、カウンタ変数ｎを初期化する。
【０２３７】
ステップＳ２５２において、特徴量抽出部１０１は、カレントフレームＦｃの画素のなかからまだ注目画素とされていない画素を選択して注目画素とする。
【０２３８】
なお、ステップＳ２５１およびステップＳ２５２の処理は、ステップＳ２２２およびステップＳ２２３の処理と同一である。ステップＳ２２２およびステップＳ２２３の処理は、現在のフレームを参照フレームＦｒとして、特徴量抽出部１０１が実行する処理を説明したものである。これに対して、ステップＳ２５１およびステップＳ２５２の処理は、現在のフレームをカレントフレームＦｃとして、特徴量抽出部１０１が実行する処理を説明したものである。言い換えれば、ステップＳ２２２およびステップＳ２２３の処理は、特徴量フレームメモリ２０１から見た、特徴量抽出部１０１が実行する処理である。ステップＳ２５１およびステップＳ２５２の処理は、候補ベクトル検出部２０２から見た、特徴量抽出部１０１が実行する処理である。
【０２３９】
ステップＳ２５３において、候補ベクトル検出部２０２は、特徴量抽出部１０１から供給された画素位置情報を基に、注目画素に対応する拡張分割領域２２３の番号ａｓａｎを算出する。すなわち、候補ベクトル検出部２０２は、注目画素の画面上の位置と同じ位置の参照フレームＦｒの画素が属する分割領域２２２を拡張した拡張分割領域２２３の番号ａｓａｎを算出する。
【０２４０】
例えば、候補ベクトル検出部２０２は、ステップＳ２２４の処理と同様の処理で、特徴量抽出部１０１から供給された画素位置情報を基に、注目画素の画面上の位置と同じ位置の参照フレームＦｒの画素が属する分割領域２２２の番号ｃｎを算出する。そして、候補ベクトル検出部２０２は、分割領域２２２の番号ｃｎから、番号ｃｎの分割領域２２２を拡張した拡張分割領域２２３の番号ａｓａｎを算出する。例えば、拡張分割領域２２３の番号ａｓａｎを、拡張分割領域２２３の中央に位置する分割領域２２２の番号ｃｎとした場合、候補ベクトル検出部２０２は、注目画素の画面上の位置と同じ位置の参照フレームＦｒの画素が属する分割領域２２２の番号ｃｎを、拡張分割領域２２３の番号ａｓａｎに設定することにより、注目画素の画面上の位置と同じ位置の参照フレームＦｒの画素が属する分割領域２２２を拡張した拡張分割領域２２３の番号ａｓａｎを算出する。
【０２４１】
ステップＳ２５４において、候補ベクトル検出部２０２は、特徴量フレームメモリ２０１から、拡張分割領域２２３の番号ａｓａｎで特定される対照表から、注目画素の特徴量に対応する画素位置情報を読み出す。すなわち、候補ベクトル検出部２０２は、ステップＳ２５２の処理で特徴量抽出部１０３から供給された特徴量と同一の特徴量の画素の位置を示す画素位置情報を、注目画素が属する分割領域２２２を拡張した拡張分割領域２２３に対応する対照表から読み出す。
【０２４２】
より具体的には、特徴量抽出部１０１から供給された注目画素の特徴量に対応する特徴量アドレスがｋであるとき、候補ベクトル検出部２０２は、特徴量フレームメモリ２０１に記憶されている、拡張分割領域２２３の番号ａｓａｎで特定される対照表のアドレス（ｋ，０）である格納領域Ｄから画素位置情報の数ｑを読み出す。そして、候補ベクトル検出部２０２は、特徴量フレームメモリ２０１に記憶されている、拡張分割領域２２３の番号ａｓａｎで特定される対照表のアドレス（ｋ，１）乃至（ｋ，ｑ）である格納領域Ｄから、ｑ個の画素位置情報を読み出す。
【０２４３】
ステップＳ２５５において、候補ベクトル検出部２０２は、特徴量フレームメモリ２０１に記憶されている、拡張分割領域２２３の番号ａｓａｎで特定される対照表から、注目画素の特徴量に対応する画素位置情報の全てを読み出したか否かを判定し、注目画素の特徴量に対応する画素位置情報の全てを読み出していないと判定された場合、ステップＳ２５４に戻り、画素位置情報の読み出しの処理を繰り返す。
【０２４４】
ステップＳ２５５において、特徴量フレームメモリ２０１に記憶されている、拡張分割領域２２３の番号ａｓａｎで特定される対照表から、注目画素の特徴量に対応する画素位置情報の全てを読み出したと判定された場合、ステップＳ２５６に進み、候補ベクトル検出部２０２は、ステップＳ２５４の処理で読み出された画素位置情報から候補ベクトルを生成する。候補ベクトル検出部２０２は、生成した候補ベクトルを、候補ベクトルの数を示す候補ベクトル数と共にサーチエリア内候補ベクトル選択部２０３に供給する。
【０２４５】
例えば、候補ベクトル検出部２０２は、注目画素の位置に対応する位置の参照フレームＦｒ上の画素を始点とし、注目画素の特徴量と同じ特徴量を有する、画素位置情報で特定される、参照フレームＦｒの画素を終点とする候補ベクトルを生成する。
【０２４６】
ステップＳ２５７において、サーチエリア内候補ベクトル選択部２０３は、候補ベクトルで示される位置が、サーチエリア２４２内であるか否かを判定し、候補ベクトルで示される位置が、サーチエリア２４２内であると判定された場合、候補ベクトルの中に動きベクトルと同じベクトルが含まれているので、ステップＳ２５８に進む。サーチエリア内候補ベクトル選択部２０３は、サーチエリア２４２に属する画素を示す候補ベクトルを選択し、選択された候補ベクトルを、サーチエリア２４２に属する画素を示す候補ベクトルの数を示す候補ベクトル数と共にブロックマッチング部２０４に供給する。
【０２４７】
ステップＳ２５８において、ブロックマッチング部２０４は、サーチエリア内候補ベクトル選択部２０３から供給された候補ベクトルおよび候補ベクトル数を基に、カレントフレームＦｃの注目画素に対応するブロックと、参照フレームＦｒの候補ベクトルで示されるブロックとの誤差を算出する。
【０２４８】
例えば、カレントフレームＦｃの、注目画素を中心とした５×５画素からなるブロックと、参照フレームＦｒの、候補ベクトルで示される画素を中心とした５×５画素からなるブロックについて、それぞれに対応する画素の画素値の差分の自乗の和を誤差値とする。
【０２４９】
ブロックマッチング部２０４は、候補ベクトルおよび候補ベクトル数と共に、誤差値を最小誤差ベクトル選択部２０５に供給する。
【０２５０】
ステップＳ２５９において、最小誤差ベクトル選択部２０５は、ブロックマッチング部２０４から供給された、誤差値、候補ベクトル、および候補ベクトル数を基に、誤差が最小の候補ベクトルを選択する。
【０２５１】
ステップＳ２６０において、最小誤差ベクトル選択部２０５は、ステップＳ２５９の処理で選択された候補ベクトルを動きベクトルとして出力して、ステップＳ２６４に進む。
【０２５２】
ステップＳ２５７において、候補ベクトルで示される位置が、サーチエリア２４２内でないと判定された場合、候補ベクトルの中に動きベクトルと同じベクトルが含まれていないので、ステップＳ２６１に進み、候補ベクトル検出部２０２は、所定の範囲の近傍の特徴量を全て選択したか否かを判定し、所定の範囲の近傍の特徴量を全て選択していないと判定された場合、ステップＳ２６２に進む。
【０２５３】
ステップＳ２６２において、候補ベクトル検出部２０２は、注目画素に対応するブロックの特徴量の近傍の特徴量を選択して、ステップＳ２５４に戻り、選択した近傍の特徴量について、上述した処理を繰り返す。
【０２５４】
なお、注目画素に対応する特徴量と同じ特徴量の参照画素の画素位置情報と、注目画素に対応する特徴量の近傍の特徴量の参照画素の画素位置情報とを、拡張分割領域２２３の番号ａｓａｎで特定される対照表から、同時に読み出すようにしてもよい。
【０２５５】
ステップＳ２６１において、所定の範囲の近傍の特徴量を全て選択したと判定された場合、動きベクトルを検出することができなかったので、ステップＳ２６３に進み、最小誤差ベクトル選択部２０５は、エラーコードを出力して、ステップＳ２６４に進む。
【０２５６】
ステップＳ２６４において、特徴量抽出部１０１は、カウンタ変数ｎをインクリメントする。すなわち、特徴量抽出部１０１は、カウンタ変数ｎに１を加算する。
【０２５７】
ステップＳ２６５において、特徴量抽出部１０１は、カウンタ変数ｎの値が、フレームの画素の数に等しいか否かを判定し、カウンタ変数ｎの値が、フレームの画素の数に等しくないと判定された場合、まだ、注目画素とされていない画素がある、すなわち動きベクトルが検出されていない画素があるので、ステップＳ２５２に戻り、上述した処理を繰り返し、次の注目画素に対応する動きベクトルを検出する。
【０２５８】
ステップＳ２６５において、カウンタ変数ｎの値が、フレームの画素の数に等しいと判定された場合、まだ、フレームの全ての画素が注目画素とされ、フレームの全ての画素に対応する画素の位置が検出されたので、処理は終了する。
【０２５９】
なお、ステップＳ２６４およびステップＳ２６５の処理は、ステップＳ２３２およびステップＳ２３３の処理と同一である。すなわち、ステップＳ２３２およびステップＳ２３３は、特徴量フレームメモリ２０１から見た、特徴量抽出部１０１が実行する処理である。ステップＳ２６４およびステップＳ２６５の処理は、候補ベクトル検出部２０２から見た、特徴量抽出部１０１が実行する処理である。
【０２６０】
このように、図１１に構成を示す画像処理装置は、より少ない演算量で、より迅速に動きベクトルを検出することができる。
【０２６１】
以上のように、動いた先が注目画素である参照画素の位置を検出するようにした場合、動きベクトルを検出することができる。
【０２６２】
また、画素の特徴量を抽出し、第１のフレームに対して時間的に前のフレームである第２のフレームの一部の領域毎に設けられた記憶領域であって、第２のフレームの第１の画素の特徴量に対応するアドレスで指定されるものへの、第１の画素の位置を示す画素位置情報の記憶を制御し、記憶領域に記憶されている、第１の画素の位置を示す画素位置情報を基に、第１のフレームの第２の画素の特徴量と同じ特徴量の第１の画素の位置の中から、動いた先が第２の画素である第１の画素の位置を選択するようにした場合、より少ない計算量で、より迅速に、動きベクトルを検出できる。
【０２６３】
上述した一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０２６４】
図２３は、上述した一連の処理をプログラムにより実行するパーソナルコンピュータの構成の例を示すブロック図である。ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）４０１は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）４０２、または記憶部４０８に記憶されているプログラムに従って各種の処理を実行する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）４０３には、ＣＰＵ４０１が実行するプログラムやデータなどが適宜記憶される。これらのＣＰＵ４０１、ＲＯＭ４０２、およびＲＡＭ４０３は、バス４０４により相互に接続されている。
【０２６５】
ＣＰＵ４０１にはまた、バス４０４を介して入出力インタフェース４０５が接続されている。入出力インタフェース４０５には、キーボード、マウス、マイクロホンなどよりなる入力部４０６、ディスプレイ、スピーカなどよりなる出力部４０７が接続されている。ＣＰＵ４０１は、入力部４０６から入力される指令に対応して各種の処理を実行する。そして、ＣＰＵ４０１は、処理の結果得られた画像や音声等を出力部４０７に出力する。
【０２６６】
入出力インタフェース４０５に接続されている記憶部４０８は、例えばハードディスクなどで構成され、ＣＰＵ４０１が実行するプログラムや各種のデータを記憶する。通信部４０９は、インターネット、その他のネットワークを介して外部の装置と通信する。この例の場合、通信部４０９は、入力画像を取得するか、または出力画像を出力する、外部とのインタフェースとして動作する。
【０２６７】
また、通信部４０９を介してプログラムを取得し、記憶部４０８に記憶してもよい。
【０２６８】
入出力インタフェース４０５に接続されているドライブ４１０は、磁気ディスク４５１、光ディスク４５２、光磁気ディスク４５３、或いは半導体メモリ４５４などが装着されたとき、それらを駆動し、そこに記録されているプログラムやデータなどを取得する。取得されたプログラムやデータは、必要に応じて記憶部４０８に転送され、記憶される。
【０２６９】
一連の処理をさせるプログラムが格納されている記録媒体は、図２３に示すように、コンピュータとは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク４５１（フレキシブルディスクを含む）、光ディスク４５２（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）を含む）、光磁気ディスク４５３（ＭＤ（Ｍｉｎｉ−Ｄｉｓｃ）（商標）を含む）、若しくは半導体メモリ４５４などよりなるパッケージメディアにより構成されるだけでなく、コンピュータに予め組み込まれた状態でユーザに提供される、プログラムが記録されているＲＯＭ４０２や、記憶部４０８に含まれるハードディスクなどで構成される。
【０２７０】
なお、上述した一連の処理を実行させるプログラムは、必要に応じてルータ、モデムなどのインタフェースを介して、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の通信媒体を介してコンピュータにインストールされるようにしてもよい。
【０２７１】
また、本明細書において、記録媒体に格納されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０２７２】
【発明の効果】
以上のように、本発明によれば、動きベクトルを検出することができる。
【０２７３】
また、本発明によれば、より少ない計算量で、より迅速に、動きベクトルを検出できる。
【図面の簡単な説明】
【図１】ブロックマッチングアルゴリズムを採用した従来の画像処理装置の構成を示すブロック図である。
【図２】サーチエリアＳＲおよび基準ブロックＢｂを説明する図である。
【図３】ブロックマッチングアルゴリズムを説明する図である。
【図４】従来の動き検出の処理を説明するフローチャートである。
【図５】代表点ブロックマッチングにおける、サーチエリアＳＲおよび代表点ブロックを説明する図である。
【図６】本発明に係る画像処理装置の一実施の形態の構成を示すブロック図である。
【図７】特徴量フレームメモリ１０２が記憶する画素位置情報および画素位置情報の数の配置を説明する図である。
【図８】図６に構成を示す画像処理装置による、動きベクトルの検出の処理を説明するフローチャートである。
【図９】ステップＳ１０１に対応する、画素位置情報の格納の処理を説明するフローチャートである。
【図１０】ステップＳ１０２の処理に対応する、注目画素に対応する画素位置の検出の処理を説明するフローチャートである。
【図１１】本発明に係る画像処理装置の他の実施の形態の構成を示すブロック図である。
【図１２】図６に構成を示す画像処理装置における、画素位置情報の記憶の処理を示す図である。
【図１３】図１１に構成を示す画像処理装置における、画素位置情報の記憶の処理を示す図である。
【図１４】分割領域２２２および拡張分割領域２２３を説明する図である。
【図１５】分割領域２２２のサイズ、拡張分割領域２２３のサイズ、およびメモリ倍率の例を示す図である。
【図１６】分割領域２２２のサイズ、拡張分割領域２２３のサイズ、およびメモリ倍率の例を示す図である。
【図１７】特徴量フレームメモリ２０１に記憶されている、複数の対照表の例を示す図である。
【図１８】特徴量フレームメモリ２０１における、画素位置情報の格納の処理を説明する図である。
【図１９】動きベクトルの検出の処理に要する時間を比較する図である。
【図２０】図１１に構成を示す画像処理装置による、動きベクトルの検出の処理を説明するフローチャートである。
【図２１】ステップＳ２０１に対応する、画素位置情報の格納の処理を説明するフローチャートである。
【図２２】ステップＳ２０２に対応する、注目画素に対応する動きベクトルの検出の処理を説明するフローチャートである。
【図２３】一連の処理をプログラムにより実行するパーソナルコンピュータの構成の例を示すブロック図である。
【符号の説明】
１０１  特徴量抽出部，  １０２  特徴量フレームメモリ，  １０３  特徴量抽出部，  １０４  参照画素位置検出部，  ２０１  特徴量フレームメモリ，  ２０２  候補ベクトル検出部，  ２０３  サーチエリア内候補ベクトル選択部，２０４  ブロックマッチング部、  ２０５  最小誤差ベクトル選択部，  ２２２  分割領域，  ２２３  拡張分割領域，  ２４２  サーチエリア，  ２５１−１乃至２５１−Ｊ  対照表，  ４０１  ＣＰＵ，  ４０２  ＲＯＭ，  ４０３  ＲＡＭ，  ４０８  記憶部，  ４５１  磁気ディスク，  ４５２  光ディスク，４５３  光磁気ディスク，  ４５４  半導体メモリ
【図１】
2004164117.tif 000004
【図２】
2004164117.tif 000005
【図３】
2004164117.tif 000006
【図４】
2004164117.tif 000007
【図５】
2004164117.tif 000008
【図６】
2004164117.tif 000009
【図７】
2004164117.tif 000010
【図８】
2004164117.tif 000011
【図９】
2004164117.tif 000012
【図１０】
2004164117.tif 000013
【図１１】
2004164117.tif 000014
【図１２】
2004164117.tif 000015
【図１３】
2004164117.tif 000016
【図１４】
2004164117.tif 000017
【図１５】
2004164117.tif 000018
【図１６】
2004164117.tif 000019
【図１７】
2004164117.tif 000020
【図１８】
2004164117.tif 000021
【図１９】
2004164117.tif 000022
【図２０】
2004164117.tif 000023
【図２１】
2004164117.tif 000024
【図２２】
2004164117.tif 000025
【図２３】
2004164117.tif 000026