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