(57)【要約】【課題】参照フレームとカレントフレームとで画素の特徴量が変化しても正しく検出する。【解決手段】上位４ビットの値を用いて求められるコードＡの同一コードの画素範囲は１６ステップであり、上位３ビットの値を用いて求められるコードＢの同一コードの画素範囲は３２ステップである。ノイズなどの影響により、参照フレームとカレントフレームとで画素の特徴量が変化した場合に、コードの境界部分で誤検知しないように、参照フレームのコードＢおよびコードＣが、それぞれ、コードＡの境界部分を含んでオーバーラップするように、コードＢのコードの境界はマイナス側に３ビットシフトされ、コードＣのコードの境界はプラス側に３ビットシフトされる。従って、特徴量の変動が３ビット以内であれば、コードＢかコードＣのいずれかで、正しい検出結果を得ることができる。本発明は、画像処理装置の動き検出部に適用できる。【選択図】　　　図５
2004134932.tif 000002
【特許請求の範囲】
【請求項１】
第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出手段と、
前記第１のフレームより時間的に前のフレームである第２のフレームの画像データから第２の特徴量を抽出する第２の特徴量抽出手段と、
前記第２の特徴量抽出手段により抽出された前記第２の特徴量毎に、対応する画素位置の情報を記憶する記憶手段と、
前記記憶手段により記憶されている前記画素位置の情報のうち、前記第１の特徴量抽出手段により抽出された前記第１のフレームに含まれる注目画素の前記第１の特徴量と対応する前記第２の特徴量の前記画素位置の情報を検索する検索手段と
を備え、
前記第２の特徴量抽出手段は、前記第１の特徴量抽出手段により抽出される前記第１の特徴量を含む、前記第１の特徴量より広範囲の特徴量を、前記第２の特徴量として抽出する
ことを特徴とする画像処理装置。
【請求項２】
前記検索手段により検索された前記画素位置の情報のうち、前記第１のフレーム中の前記注目画素との距離が最小となる画素位置を検出し、検出された前記画素位置と、前記注目画素の画素位置の情報とを基に、動きベクトルを生成する動きベクトル生成手段
を更に備えることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記第２の特徴量抽出手段は、前記第１の特徴量と同一の特徴量を含む複数の特徴量を、前記第２の特徴量として抽出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記第１のフレームおよび前記第２のフレームに含まれている画素の画素値は、所定のステップ数で量子化され、
前記第１の特徴量抽出手段は、量子化された前記第１のフレームの画素値を基に、ｎステップが１グループに属するような第１の規準でグループ化することにより前記第１の特徴量を抽出し、
前記第２の特徴量抽出手段は、量子化された前記第２のフレームの画素値を基に、ｎより大きいｍステップが１グループに属するように、かつ、前記第１の規準によるグループ化のグループの境界と異なる位置に境界ができるようにグループ化する第２の規準で、前記第２の特徴量を抽出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記第１のフレームおよび前記第２のフレームに含まれている画素の画素値は、所定のビット数のデータに量子化され、
前記第１の特徴量抽出手段は、量子化された前記第１のフレームの画素値の上位ｎビットを用いて、前記第１の特徴量を抽出し、
前記第２の特徴量抽出手段は、量子化された前記第２のフレームの画素値の上位（ｎ−１）ビットを用い、正方向に所定のビット数だけシフトして得られる第１の値と、負方向に所定のビット数だけシフトして得られる第２の値とを、前記第２の特徴量として抽出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記第１の特徴量抽出手段は、
前記第１の特徴量として、前記第１のフレームに含まれている画素の画素値を基に、ＡＤＲＣに基づくｎビットの量子化コードを抽出する第１のコード抽出手段を有し、
前記第２の特徴量抽出手段は、
前記第２のフレームに含まれている画素の画素値を基に、ＡＤＲＣに基づく
ｎビットの前記量子化コードを抽出する第２のコード抽出手段と、
前記第２のコード抽出手段により抽出された前記量子化コードのｎビットの
うちの１ビットを反転させたｎ個のコードを生成する生成手段と
を有し、
前記第１の特徴量は、前記第１のコード抽出手段により抽出された前記量子化コードであり、
前記第２の特徴量は、前記第２のコード抽出手段により抽出された前記量子化コード、および、前記生成手段により生成された、前記ｎ個のコードである
ことを特徴とする請求項１に記載の画像処理装置。
【請求項７】
参照フレームの画素に関する情報を記憶する記憶手段を備える画像処理装置の画像処理方法において、
第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出ステップと、
前記第１のフレームより時間的に前のフレームである第２のフレームの画像データから、前記第１の特徴量抽出ステップの処理により抽出される前記第１の特徴量を含む、前記第１の特徴量より広範囲の特徴量である第２の特徴量を抽出する第２の特徴量抽出ステップと、
前記第２の特徴量抽出ステップの処理により抽出された前記第２の特徴量を基に、前記記憶手段への、前記第２の特徴量毎の対応する画素位置の情報の記憶を制御する記憶制御ステップと、
前記記憶制御ステップの処理により記憶が制御されている前記画素位置の情報のうち、前記第１の特徴量抽出ステップの処理により抽出された前記第１のフレームに含まれる注目画素の前記第１の特徴量と対応する前記第２の特徴量の前記画素位置の情報を検索する検索ステップと
を含むことを特徴とする画像処理方法。
【請求項８】
参照フレームの画素に関する情報を記憶する記憶手段を用いて、カレントフレームの注目画素に対応する前記参照フレームの画素を検出する処理を実行するプログラムであって、
第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出ステップと、
前記第１のフレームより時間的に前のフレームである第２のフレームの画像データから、前記第１の特徴量抽出ステップの処理により抽出される前記第１の特徴量を含む、前記第１の特徴量より広範囲の特徴量である第２の特徴量を抽出する第２の特徴量抽出ステップと、
前記第２の特徴量抽出ステップの処理により抽出された前記第２の特徴量を基に、前記記憶手段への、前記第２の特徴量毎の対応する画素位置の情報の記憶を制御する記憶制御ステップと、
前記記憶制御ステップの処理により記憶が制御されている前記画素位置の情報のうち、前記第１の特徴量抽出ステップの処理により抽出された前記第１のフレームに含まれる注目画素の前記第１の特徴量と対応する前記第２の特徴量の前記画素位置の情報を検索する検索ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項９】
参照フレームの画素に関する情報を記憶する記憶手段を用いて、カレントフレームの注目画素に対応する前記参照フレームの画素を検出する処理を実行する処理をコンピュータに実行させるプログラムであって、
第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出ステップと、
前記第１のフレームより時間的に前のフレームである第２のフレームの画像データから、前記第１の特徴量抽出ステップの処理により抽出される前記第１の特徴量を含む、前記第１の特徴量より広範囲の特徴量である第２の特徴量を抽出する第２の特徴量抽出ステップと、
前記第２の特徴量抽出ステップの処理により抽出された前記第２の特徴量を基に、前記記憶手段への、前記第２の特徴量毎の対応する画素位置の情報の記憶を制御する記憶制御ステップと、
前記記憶制御ステップの処理により記憶が制御されている前記画素位置の情報のうち、前記第１の特徴量抽出ステップの処理により抽出された前記第１のフレームに含まれる注目画素の前記第１の特徴量と対応する前記第２の特徴量の前記画素位置の情報を検索する検索ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理装置および方法、記録媒体、並びにプログラムに関し、特に、より正確に動きベクトルを検出できるようにした画像処理装置および方法、記録媒体、並びにプログラムに関する。
【０００２】
【従来の技術】
画像の動きを示す動きベクトルを求め、この動きベクトルに基づいて効率よく動画像を圧縮する技術がある。
【０００３】
この動画像圧縮技術における上述の動きベクトルを求める手法としては、いくつか提案されているが、代表的な手法としてブロックマッチングアルゴリズムと呼ばれる手法がある。
【０００４】
図１は、ブロックマッチングアルゴリズムを採用した従来の画像処理装置の動き検出部１の構成例を示している。
【０００５】
動き検出部１のフレームメモリ１１は、例えば、時刻ｔ１において、入力端子Ｔｉｎから画像信号が入力されると、１フレーム分の情報を格納する。さらに、フレームメモリ１１は、次のタイミングとなる時刻ｔ２において、入力端子Ｔｉｎから次のフレームの画像信号が入力されると、時刻ｔ１において、格納した１フレーム分の画像情報をフレームメモリ１２に出力した後、新たに入力された１フレーム分の画像情報を格納する。
【０００６】
また、フレームメモリ１２は、時刻ｔ２のタイミングで、フレームメモリ１１から入力されてくる時刻ｔ１のタイミングで入力端子Ｔｉｎから入力されてきた１フレーム分の画像情報を格納する。
【０００７】
すなわち、フレームメモリ１１が、上述の時刻ｔ２のタイミングで入力される（今現在の）１フレーム分の画像情報を格納するとき、フレームメモリ１２は、時刻ｔ１のタイミングで入力された（１タイミング過去の）１フレーム分の画像情報を格納していることになる。なお、以下において、フレームメモリ１１に格納される画像情報をカレントフレームＦｃ、フレームメモリ１２に格納される画像情報を参照フレームＦｒと称するものとする。
【０００８】
動きベクトル検出部１３は、フレームメモリ１１，１２に格納されているカレントフレームＦｃと参照フレームＦｒをそれぞれから読出し、このカレントフレームＦｃと参照フレームＦｒに基づいて、ブロックマッチングアルゴリズムにより動きベクトルを検出し、出力端子Ｔｏｕｔから出力する。
【０００９】
ここで、ブロックマッチングアルゴリズムについて説明する。例えば、図２で示すように、カレントフレームＦｃ内の注目画素Ｐ（ｉ，ｊ）に対応する動きベクトルを求める場合、まず、カレントフレームＦｃ上に注目画素Ｐ（ｉ，ｊ）を中心としたＬ（画素数）×Ｌ（画素数）からなる基準ブロックＢｂ（ｉ，ｊ）、参照フレームＦｒ上に、注目画素Ｐ（ｉ，ｊ）の位置に対応するサーチエリアＳＲ、そして、そのサーチエリアＳＲ内に、Ｌ（画素数）×Ｌ（画素数）の画素からなる参照ブロックＢｒｎ（ｉ，ｊ）がそれぞれ設定される。
【００１０】
次に、この基準ブロックＢｂ（ｉ，ｊ）と、参照ブロックＢｒｎ（ｉ，ｊ）の各画素間の差分の絶対値の和を求める処理が、参照ブロックＢｒｎをサーチエリアＳＲ内の全域で水平方向、または、垂直方向に１画素分ずつ移動させながら、図２中のＢｒ１からＢｒｍ（参照ブロックＢｒｎが、サーチエリアＳＲ内にｍ個設定できるものとする）まで繰り返される。
【００１１】
このようにして求められた基準ブロックＢｂ（ｉ，ｊ）と、参照ブロックＢｒｎ（ｉ，ｊ）の各画素間の差分絶対値和のうち、差分絶対値和が最小となる参照ブロックＢｒｎを求めることにより、基準ブロックＢｂ（ｉ，ｊ）に最も近い（類似している）参照ブロックＢｒｎ（ｉ，ｊ）を構成するＬ×Ｌ個の画素の中心となる参照画素Ｐｎ（ｉ，ｊ）が求められる。
【００１２】
そして、このカレントフレームＦｃ上の注目画素Ｐ（ｉ，ｊ）に対応する参照フレームＦｒ上の画素Ｐ’（ｉ，ｊ）を始点とし、参照画素Ｐｎ（ｉ，ｊ）を終点とするベクトルが、注目画素Ｐ（ｉ，ｊ）の動きベクトル（Ｖｘ，Ｖｙ）として出力される。ここで、例えば、Ｐ（ｉ，ｊ）＝（ａ，ｂ）、および、Ｐｎ（ｉ，ｊ）＝（ｃ，ｄ）である場合、（Ｖｘ，Ｖｙ）は、（Ｖｘ，Ｖｙ）＝（ｃ−ａ，ｄ−ｂ）となる。
【００１３】
すなわち、注目画素Ｐ（ｉ，ｊ）に対応する参照フレームＦｒ上の参照画素Ｐ’（ｉ，ｊ）を始点とし、基準ブロックＢｂ（ｉ，ｊ）に最も近い（類似している）参照ブロックＢｒｎ（ｉ，ｊ）を構成するＬ×Ｌ個の画素の中心となる参照画素Ｐｎ（ｉ，ｊ）を終点とするベクトルが動きベクトルとして求められる。
【００１４】
次に、図３のフローチャートを参照して、図１の動き検出部１の動き検出処理について説明する。
【００１５】
ステップＳ１において、動きベクトル検出部１３は、フレームメモリ１１に格納されているカレントフレームＦｃ上の注目画素Ｐ（ｉ，ｊ）の画素位置に応じて、サーチエリアＳＲを設定する。
【００１６】
ステップＳ２において、動きベクトル検出部１３は、上述のように、基準ブロックＢｂ（ｉ，ｊ）と参照ブロックＢｒｎ（ｉ，ｊ）の画素間の差分絶対値和の最小値を設定する変数Ｍｉｎを、画素の諧調数に基準ブロックＢｂ（ｉ，ｊ）を構成する画素数を乗じた値に設定することにより初期化する。すなわち、例えば、１画素が８ビットのデータであった場合、１画素の諧調数は、２の８乗となるため２５６階調（２５６色）となる。また、基準ブロックＢｂ（ｉ，ｊ）がＬ画素×Ｌ画素＝３画素×３画素から構成される場合、その画素数は、９個となる。結果として、変数Ｍｉｎは、２３０４（＝２５６（諧調数）×９（画素数））に初期化される。
【００１７】
ステップＳ３において、動きベクトル検出部１３は、参照ブロックＢｒｎをカウントするカウンタ変数ｎを１に初期化する。
【００１８】
ステップＳ４において、動きベクトル検出部１３は、基準ブロックＢｂと参照ブロックＢｒｎの画素間の差分絶対値和を代入するために用いる変数ｓｕｍを０に初期化する。
【００１９】
ステップＳ５において、動きベクトル検出部１３は、基準ブロックＢｂ（ｉ，ｊ）と参照ブロックＢｒｎ（ｉ，ｊ）の画素間の差分絶対値和（＝ｓｕｍ）を求める。すなわち、基準ブロックＢｂ（ｉ，ｊ）の各画素がＰ＿Ｂｂ（ｉ，ｊ）、基準ブロックＢｒｎ（ｉ，ｊ）の各画素がＰ＿Ｂｒｎ（ｉ，ｊ）としてそれぞれ示される場合、動きベクトル検出部１３は、以下の式（１）で示される演算を実行して、基準ブロックＢｂ（ｉ，ｊ）と参照ブロックＢｒｎ（ｉ，ｊ）の画素間の差分絶対値和を求める。
【００２０】
【数１】
2004134932.tif 000003
【００２１】
ステップＳ６において、動きベクトル検出部１３は、変数Ｍｉｎが変数ｓｕｍよりも大きいか否かを判定し、例えば、変数Ｍｉｎが変数ｓｕｍよりも大きいと判定する場合、ステップＳ７において、変数Ｍｉｎを変数ｓｕｍに更新し、その時点でのカウンタｎの値を動きベクトル番号として登録する。すなわち、今求めた差分絶対値和を示す変数ｓｕｍが、最小値を示す変数Ｍｉｎよりも小さいと言うことは、これまで演算したどの参照ブロックよりも、今演算している参照ブロックＢｒｎ（ｉ，ｊ）が基準ブロックＢｂ（ｉ，ｊ）により類似したものであるとみなすことができるので、動きベクトルを求める際の候補とするため、その時点でのカウンタｎが動きベクトル番号として登録される。また、ステップＳ６において、変数Ｍｉｎが変数ｓｕｍよりも大きくないと判定された場合、ステップＳ７の処理がスキップされる。
【００２２】
ステップＳ８において、動きベクトル検出部１３は、カウンタ変数ｎがサーチエリアＳＲの参照ブロックＢｒｎの総数ｍであるか否か、すなわち、今の参照ブロックＢｒｎがＢｒｎ＝Ｂｒｍであるか否かを判定し、例えば、総数ｍではないと判定した場合、ステップＳ９において、カウンタ変数ｎを１インクリメントし、その処理は、ステップＳ４に戻る。
【００２３】
ステップＳ８において、カウンタ変数ｎがサーチエリア内の参照ブロックＢｒｎの総数ｍである、すなわち、今の参照ブロックＢｒｎがＢｒｎ＝Ｂｒｍであると判定された場合、ステップＳ１０において、動きベクトル検出部１３は、登録されている動きベクトル番号に基づいて動きベクトルを出力する。すなわち、ステップＳ４乃至Ｓ９が繰り返されることにより、差分絶対値和が最小となる参照ブロックＢｒｎに対応するカウンタ変数ｎが動きベクトル番号として登録されることになるので、動きベクトル検出部１３は、この動きベクトル番号に対応する参照ブロックＢｒｎのＬ×Ｌ個の画素のうち、その中心となる参照画素Ｐｎ（ｉ，ｊ）を求め、カレントフレームＦｃ上の注目画素Ｐ（ｉ，ｊ）に対応する参照フレームＦｒ上の画素Ｐ’（ｉ，ｊ）を始点とし、参照画素Ｐｎ（ｉ，ｊ）を終点とするベクトルを、注目画素Ｐ（ｉ，ｊ）の動きベクトル（Ｖｘ，Ｖｙ）として求めて出力する。
【００２４】
以上説明したようなブロックマッチング法により、動きベクトルを検出する場合において、動きベクトル検出対象ブロック、および、参照フレームの小ブロック毎に定常成分および過渡成分を抽出し、これらの定常成分および過渡成分の差分をそれぞれ検出して、絶対値差分を累算した値を加重平均して評価値を形成し、この評価値に基づいて動きベクトルを検出することにより、演算量を低減することができ、また、誤検出のおそれを防止することができるようにする技術がある（例えば、特許文献１参照）。また、１ビットＡＤＲＣによって各画素値を１ビットのコード値に符号化し、そのコード値を使用してマッチング演算を行うことにより、動きベクトルの検出に係る回路構成、演算時間等を簡素化することができる技術がある（例えば、特許文献２参照）。
【００２５】
【特許文献１】
特開平０７−０８７４９４号公報
【特許文献２】
特開２０００−２７８６９１号公報
【００２６】
【発明が解決しようとする課題】
しかしながら、上述したブロックマッチングアルゴリズムは、式（１）の演算量が非常に膨大なものとなるため、ＭＰＥＧ（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）等の画像圧縮処理においては、大半の時間がこの処理に費やされてしまうという課題があった。
【００２７】
また、カレントフレームＦｃ、または、参照フレームＦｒの動きベクトルの始点、または、終点付近でノイズが含まれた場合、ブロックマッチングでは基準ブロックに類似する参照ブロックを検出することができず、正確な動きベクトルを検出することができないという課題があった。
【００２８】
本発明はこのような状況に鑑みてなされたものであり、正確に動きベクトルを生成することができるようにするものである。
【００２９】
【課題を解決するための手段】
本発明の画像処理装置は、第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出手段と、第１のフレームより時間的に前のフレームである第２のフレームの画像データから第２の特徴量を抽出する第２の特徴量抽出手段と、第２の特徴量抽出手段により抽出された第２の特徴量毎に、対応する画素位置の情報を記憶する記憶手段と、記憶手段により記憶されている画素位置の情報のうち、第１の特徴量抽出手段により抽出された第１のフレームに含まれる注目画素の第１の特徴量と対応する第２の特徴量の画素位置の情報を検索する検索手段とを備え、第２の特徴量抽出手段は、第１の特徴量抽出手段により抽出される第１の特徴量を含む、第１の特徴量より広範囲の特徴量を、第２の特徴量として抽出することを特徴とする。
【００３０】
検索手段により検索された画素位置の情報のうち、第１のフレーム中の注目画素との距離が最小となる画素位置を検出し、検出された画素位置と、注目画素の画素位置の情報とを基に、動きベクトルを生成する動きベクトル生成手段を更に備えさせるようにすることができる。
【００３１】
第２の特徴量抽出手段には、第１の特徴量と同一の特徴量を含む複数の特徴量を、第２の特徴量として抽出させるようにすることができる。
【００３２】
第１のフレームおよび第２のフレームに含まれている画素の画素値は、所定のステップ数で量子化されるものとすることができ、第１の特徴量抽出手段には、量子化された第１のフレームの画素値を基に、ｎステップが１グループに属するような第１の規準でグループ化することにより第１の特徴量を抽出させるようにすることができ、第２の特徴量抽出手段には、量子化された第２のフレームの画素値を基に、ｎより大きいｍステップが１グループに属するように、かつ、第１の規準によるグループ化のグループの境界と異なる位置に境界ができるようにグループ化する第２の規準で、第２の特徴量を抽出させるようにすることができる。
【００３３】
第１のフレームおよび第２のフレームに含まれている画素の画素値は、所定のビット数のデータに量子化されるものとすることができ、第１の特徴量抽出手段には、量子化された第１のフレームの画素値の上位ｎビットを用いて、第１の特徴量を抽出させるようにすることができ、第２の特徴量抽出手段には、量子化された第２のフレームの画素値の上位（ｎ−１）ビットを用い、正方向に所定のビット数だけシフトして得られる第１の値と、負方向に所定のビット数だけシフトして得られる第２の値とを、第２の特徴量として抽出させるようにすることができる。
【００３４】
第１の特徴量抽出手段は、第１の特徴量として、第１のフレームに含まれている画素の画素値を基に、ＡＤＲＣに基づくｎビットの量子化コードを抽出する第１のコード抽出手段を有するものとすることができ、第２の特徴量抽出手段は、第２のフレームに含まれている画素の画素値を基に、ＡＤＲＣに基づくｎビットの量子化コードを抽出する第２のコード抽出手段と、第２のコード抽出手段により抽出された量子化コードのｎビットのうちの１ビットを反転させたｎ個のコードを生成する生成手段とを有するものとすることができ、第１の特徴量は、第１のコード抽出手段により抽出された量子化コードであるものとすることができ、第２の特徴量は、第２のコード抽出手段により抽出された量子化コード、および、生成手段により生成された、ｎ個のコードであるものとすることができる。
【００３５】
本発明の画像処理方法は、第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出ステップと、第１のフレームより時間的に前のフレームである第２のフレームの画像データから、第１の特徴量抽出ステップの処理により抽出される第１の特徴量を含む、第１の特徴量より広範囲の特徴量である第２の特徴量を抽出する第２の特徴量抽出ステップと、第２の特徴量抽出ステップの処理により抽出された第２の特徴量を基に、記憶手段への、第２の特徴量毎の対応する画素位置の情報の記憶を制御する記憶制御ステップと、記憶制御ステップの処理により記憶が制御されている画素位置の情報のうち、第１の特徴量抽出ステップの処理により抽出された第１のフレームに含まれる注目画素の第１の特徴量と対応する第２の特徴量の画素位置の情報を検索する検索ステップとを含むことを特徴とする。
【００３６】
本発明の記録媒体に記録されているプログラムは、第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出ステップと、第１のフレームより時間的に前のフレームである第２のフレームの画像データから、第１の特徴量抽出ステップの処理により抽出される第１の特徴量を含む、第１の特徴量より広範囲の特徴量である第２の特徴量を抽出する第２の特徴量抽出ステップと、第２の特徴量抽出ステップの処理により抽出された第２の特徴量を基に、記憶手段への、第２の特徴量毎の対応する画素位置の情報の記憶を制御する記憶制御ステップと、記憶制御ステップの処理により記憶が制御されている画素位置の情報のうち、第１の特徴量抽出ステップの処理により抽出された第１のフレームに含まれる注目画素の第１の特徴量と対応する第２の特徴量の画素位置の情報を検索する検索ステップとを含むことを特徴とする。
【００３７】
本発明のプログラムは、第１のフレームの画像データから第１の特徴量を抽出する第１の特徴量抽出ステップと、第１のフレームより時間的に前のフレームである第２のフレームの画像データから、第１の特徴量抽出ステップの処理により抽出される第１の特徴量を含む、第１の特徴量より広範囲の特徴量である第２の特徴量を抽出する第２の特徴量抽出ステップと、第２の特徴量抽出ステップの処理により抽出された第２の特徴量を基に、記憶手段への、第２の特徴量毎の対応する画素位置の情報の記憶を制御する記憶制御ステップと、記憶制御ステップの処理により記憶が制御されている画素位置の情報のうち、第１の特徴量抽出ステップの処理により抽出された第１のフレームに含まれる注目画素の第１の特徴量と対応する第２の特徴量の画素位置の情報を検索する検索ステップとを含むことを特徴とする。
【００３８】
本発明の画像処理装置および方法、並びにプログラムにおいては、第１のフレームの画像データから第１の特徴量が抽出され、第１のフレームより時間的に前のフレームである第２のフレームの画像データから、第１の特徴量を含む、第１の特徴量より広範囲の特徴量である第２の特徴量が抽出され、抽出された第２の特徴量を基に、第２の特徴量毎に、対応する画素位置の情報が記憶され、記憶されている画素位置の情報のうち、第１のフレームに含まれる注目画素の第１の特徴量と対応する第２の特徴量の画素位置の情報が検索される。
【００３９】
【発明の実施の形態】
以下、図を参照して、本発明の実施の形態について説明する。
【００４０】
図４は、本発明を適用した画像処理装置の動き検出部５１の構成を示すブロック図である。
【００４１】
動き検出部５１は、フレームメモリ６１および６２、特徴量抽出部６３および６４、データベース制御部６５、データベース検索部６６、および、動きベクトル決定部６７で構成されている。
【００４２】
第１のフレームメモリであるフレームメモリ６１は、入力端子Ｔｉｎから入力された画像信号の１画面の情報を格納し、フレームメモリ６２および特徴量抽出部６３に供給する。入力端子Ｔｉｎから入力される画像信号は、各画素の画素値が、所定のビット数に量子化された情報であり、例えば、ＰＣＭ符号化などにより、符号化されていてもかまわない。ここでは、画素値が、８ビットに量子化されているものとして説明する。
【００４３】
特徴量抽出部６３は、フレームメモリから供給された画面情報、すなわちカレントフレームＦｃの情報を基に、注目画素の特徴量を抽出する。特徴量には、例えば、注目画素の画素値、注目画素を中心とした所定の画素範囲のブロックの複数の画素値またはこれらの画素値の平均値、注目画素を中心とした所定の画素範囲のブロックの画素値を基に算出されるＡＤＲＣ（Ａｄａｐｔｉｖｅ　Ｄｙｎａｍｉｃ　Ｒａｎｇｅ　Ｃｏｄｉｎｇ）のコード、ブロック内の画素値分布のダイナミックレンジ、あるいは、ブロック内の画素値分布の最小値などがある。
【００４４】
ここでは、特徴量抽出部６３は、特徴量として、注目画素の画素値を用いるものとして説明する。特徴量抽出部６３は、注目画素の画素値として、８ビットのデータの入力を受け、上位４ビットを用いて、コード化を実行する。すなわち、８ビットで示される画素値０乃至２８−１が、２４種類のコードで示される。具体的には、特徴量抽出部６３において、次の式（２）により、コードＡ（ｃｏｄｅＡ）が算出される。
【００４５】
ｃｏｄｅＡ＝［ｐ（ｘ、ｙ）／１６］・・・（２）
【００４６】
ただし、ｐ（ｘ、ｙ）は、注目画素の画素値であり、［］の括弧内の計算値は、小数点以下を切り捨てるものとする。特徴量抽出部６３は、算出されたコードＡを、第１の特徴量として、対応する画素の位置（例えば、座標情報）とともに、データベース検索部６６に供給する。
【００４７】
第２のフレームメモリであるフレームメモリ６２は、フレームメモリ６１に格納されていた、以前（たとえば１画面前）の画面情報の入力を受け、参照フレームＦｒの情報として格納し、順次、特徴量抽出部６４に供給する。
【００４８】
参照フレームＦｒとカレントフレームＦｃにおいて対応する画素は、本来、同一の特徴を有しているはずであるが、例えば、ノイズなどの影響により、その特徴が多少変化することがある。参照フレームＦｒとカレントフレームＦｃにおいて、いずれも、式（２）を用いて説明したコードＡの演算結果を特徴量として用いた場合、例えば、参照フレームＦｒにおいて、画素値が１５であった画素が、カレントフレームＦｃにおいて、画素値１６となってしまったとき、コードＡの算出結果は、参照フレームＦｒではコードＡ＝０、カレントフレームＦｃではコードＡ＝１となる。このような場合、同一の特徴量算出結果を得ることができないため、本来、対応する画素であるとして検出されるべきである画素を検出することができず、動きベクトルを正しく検出することができなくなってしまう。
【００４９】
そこで、特徴量抽出部６４は、フレームメモリ６２から供給された参照フレームＦｒの情報を基に、特徴量抽出部６３とは異なる規準を用いて、注目画素の特徴量を抽出する。
【００５０】
特徴量抽出部６４は、供給された画素値のうち、上位３ビットを用いて、コード化を実行する。すなわち、８ビットで示される画素値０乃至２８−１が、２３種類のコードで示されるのであるが、ここでは、２種類のコードを算出する。従って、算出されるコードの種類の総数は、２３×２種類となり、特徴量抽出部６３において算出されるコードの種類と同数となる。具体的には、次の式（３）および式（４）により、コードＢ（ｃｏｄｅＢ）およびコードＣ（ｃｏｄｅＣ）が算出される。
【００５１】
ｃｏｄｅＢ＝［｛ｐ（ｘ、ｙ）＋８｝／３２］×２・・・（３）
ｃｏｄｅＣ＝［｛ｐ（ｘ、ｙ）−８｝／３２］×２＋１・・・（４）
【００５２】
ここでも、［］の括弧内の計算値は、小数点以下切り捨てるものとする。特徴量抽出部６３において算出されるコードＡと、特徴量抽出部６４において算出されるコードＢおよびコードＣとの関係を図５に示す。
【００５３】
コードＡが、上位４ビットの値を用いてコード化されているのに対し、コードＢおよびコードＣは、上位３ビットの値を用いてコード化されているため、同一コードに含まれる画素範囲は、コードＡにおいては１６ステップであり、コードＢおよびコードＣにおいては、コードＡにおける場合の２倍の３２ステップとなる。そして、コードＢのコードの境界は、コードＡの境界と比較して、マイナス側に３ビットシフトされ、コードＣのコードの境界は、コードＡの境界と比較して、プラス側に３ビットシフトされている。
【００５４】
ノイズなどの影響により、参照フレームＦｒとカレントフレームＦｃとにおいて画素の特徴量が変化した場合、最も誤検知を起こしやすいのは、コードの境界部分である。従って、この部分を誤検知しないように、参照フレームＦｒのコードＢおよびコードＣが、それぞれ、コードＡの境界部分を含んで、同じ画素値範囲でオーバーラップするように設定される。
【００５５】
図５に示されるように、上述した式（３）および式（４）によって生成されるコードＢまたはコードＣは、それぞれ、コードＡ＝Ｘ（Ｘは、０乃至１４）と、コードＡ＝Ｘ＋１との境界部分の画素値を含む。そして、コードＡ＝Ｘと、コードＡ＝Ｘ＋１との境界部分となる画素値において、コードＢ＝Ｘとなり、コードＣ＝Ｘ＋１となる。
【００５６】
具体的には、例えば、注目画素の画素値が６３である場合、カレントフレームＦｃにおいて、コードＡ＝３となり、参照フレームＦｒにおいて、コードＢ＝４、かつ、コードＣ＝３となる。また、注目画素の画素値が６４である場合、カレントフレームＦｃにおいて、コードＡ＝４となり、参照フレームＦｒにおいて、コードＢ＝４、かつ、コードＣ＝３となる。
【００５７】
従って、参照フレームＦｒとカレントフレームＦｃとにおいて画素の特徴量が６３と６４で変化してしまった場合においても、コードＢかコードＣのいずれかにおいて、コードＡと同一のコードを得ることが可能となる。上述した式（３）および式（４）によってコードＢおよびコードＣが生成された場合、コードＢまたはコードＣは、コードＡの対応する境界を挟んで、３ビット（画素値で８ステップ）ずつずれているので、参照フレームＦｒとカレントフレームＦｃとにおいての画素の特徴量の変動が３ビット（画素値で８ステップ）以内であれば、コードＢかコードＣのいずれかにおいて、正しい検出結果を得ることが可能となる。
【００５８】
ここでは、コードＡを検出するために用いる情報のビット数を上位４ビットとし、コードＢおよびコードＣを検出するために用いる情報のビット数を上位３ビットとして説明したが、特徴量としてのコードの検出方法はこの限りではない。例えば、コードＡを検出するために用いる情報のビット数を上位５ビットとし、コードＢおよびコードＣを検出するために用いる情報のビット数を上位４ビットとしてもよい。
【００５９】
特徴量抽出部６４は、算出されたコードＢおよびコードＣを、第２の特徴量、および第３の特徴量として、対応する画素の位置（例えば、座標情報）とともに、データベース制御部６５に供給する。
【００６０】
データベース制御部６５は、特徴量抽出部６４から供給された、参照フレームＦｒの特徴量情報を基に、特徴量をアドレスとして、画素の位置情報をデータベース７１に格納することにより、参照フレーム情報を生成する。データベース制御部６５は、内部に、処理済の画素数をカウントするためのカウンタを有している。
【００６１】
データベース７１に格納される参照フレーム情報の構成を図６に示す。
【００６２】
データベース７１は、特徴量アドレス０乃至ａと、フラグアドレス０乃至ｂによって示される（ａ＋１）×（ｂ＋１）個のセルにより構成されている。ここで、特徴量であるコードＡ、コードＢ、およびコードＣが、上述した方法で算出される場合、特徴量アドレス０乃至ａは、それぞれ、コードＡ、コードＢ、およびコードＣのコード番号０乃至１５に対応する（ａ＝１５）。
【００６３】
データベース制御部６５は、参照フレームＦｒの画素の特徴量であるコードＢ、およびコードＣを、特徴量アドレスに対応つけて、その画素の位置情報を、データベース７１の、特徴量アドレスに対応するフラグアドレス１乃至ｂに順次格納する。そして、フラグアドレス０には、現在、その特徴量アドレスに格納されている位置情報の数が、順次、インクリメントされて格納される。具体的には、特徴量アドレス１に、１つの位置情報が格納されている場合、セル（１，０）には、格納されている位置情報の数として、１が格納される。そして、次の注目画素の特徴量が、特徴量アドレス１に対応するものであった場合、セル（１，０）に格納されている値は、インクリメントされて２となり、注目画素の位置情報が、セル（１，２）に格納される。
【００６４】
そして、参照フレームＦｒの注目画素１つに付き、コードＢ、およびコードＣに対応する２つの画素位置情報が、特徴量アドレスに対応するフラグアドレス１乃至ｂのいずれかに格納される。１フレーム分の格納処理が終了したとき、データベース７１のセル（０，１）からセル（ａ，ｂ）には、１フレームの画素数の２倍の画素位置情報が格納される。
【００６５】
再び、図４に戻り、動き検出部５１の構成について説明する。データベース検索部６６は、特徴量抽出部６３から供給されたカレントフレームＦｃの特徴量情報と、データベース制御部６５のデータベース７１に記憶されている参照フレーム情報とのマッチング処理を実行する。すなわち、データベース検索部６１は、特徴量抽出部６３から、カレントフレームＦｃの注目画素の特徴量であるコードＡの入力を受け、データベース７１の参照フレーム情報を参照して、カレントフレームＦｃの注目画素の特徴量と一致する特徴量アドレスに記載されている、複数の参照画素候補の画素位置情報を検出して、カレントフレームＦｃの注目画素の画素位置情報とともに、動きベクトル決定部６７に供給する。
【００６６】
動きベクトル決定部６７は、カレントフレームＦｃの注目画素の画素位置情報と、複数の参照画素候補の画素位置情報との距離を演算し、例えば、算出された距離が最小である参照画素候補を、カレントフレームＦｃの注目画素に対応する参照画素であると決定し、その位置情報に基づいて、差分座標を検出して出力する。出力された差分座標は、注目画素の動きベクトル（Ｖｘ，Ｖｙ）である。
【００６７】
ここでは、距離演算結果が最小のものを選択することにより、複数の参照画素候補のうち、カレントフレームＦｃの注目画素に対応する参照画素を決定するものとして説明したが、参照画素の決定方法は、それ以外の方法であってもかまわないことは言うまでもない。
【００６８】
図７を参照して、動き検出部５１が実行する動き検出処理１について説明する。
【００６９】
ステップＳ３１において、フレームメモリ６１は、フレームの入力を受ける。
【００７０】
ステップＳ３２において、フレームメモリ６１は、ステップＳ３１において入力されたフレームを、第２のフレームメモリであるフレームメモリ６２に供給する。フレームメモリ６２は、例えば、ｎ番目のフレームがフレームメモリ６１からフレームメモリ６２に供給されるよりも前に、格納されていたｎ−１番目のフレームを、特徴量抽出部６４に供給する。
【００７１】
ステップＳ３３において、図９を用いて後述する参照フレーム情報生成処理が、特徴量抽出部６４において実行される。
【００７２】
特徴量抽出部６３は、ステップＳ３４において、フレームメモリ６１から入力されたフレームの注目画素の画素値の上位４ビットを抽出し、ステップＳ３５において、コードＡを算出する。ステップＳ３４およびステップＳ３５の処理は、上述した、式（２）の演算処理に等しい。
【００７３】
ステップＳ３６において、図１１を用いて後述するマッチング処理が実行されて、処理が終了される。
【００７４】
ステップＳ３１乃至ステップＳ３６の処理は、一部、並行して実行される。例えば、ｎ−１番目に入力されたフレーム（ｎ−１フレーム）、ｎ番目に入力されたフレーム（ｎフレーム）、および、ｎ＋１番目に入力されたフレーム（ｎ＋１フレーム）が処理されるタイミングの例について、図８を用いて説明する。
【００７５】
例えば、フレームメモリ６１にｎフレームが入力されたとき、特徴量抽出部６４においては、ｎ−１フレームのコードＢおよびコードＣが算出される。
【００７６】
次に、特徴量抽出部６３において、ｎフレームのコードＡが算出されているとき、第２のフレームメモリであるフレームメモリ６２にｎフレームが供給され、特徴量抽出部６４において算出されたｎ−１フレームのコードＢおよびコードＣが、データベース制御部６５の処理により、データベース７１に登録される。
【００７７】
そして、その後、データベース検索部６６において、特徴量抽出部６３において算出されたｎフレームのコードＡに対応する特徴量を有する画素位置の情報が、データベース７１に登録されているｎ−１フレームの情報より抽出される（マッチング）。このとき、特徴量抽出部６４において、ｎフレームのコードＢおよびコードＣが算出され、フレームメモリ６１にｎ＋１フレームが入力される。
【００７８】
次に、特徴量抽出部６３において、ｎ＋１フレームのコードＡが算出されているとき、第２のフレームメモリであるフレームメモリ６２にｎ＋１フレームが供給されるとともに、特徴量抽出部６４において算出されたｎフレームのコードＢおよびコードＣが、データベース制御部６５の処理により、データベース７１に登録される。
【００７９】
そして、データベース検索部６６において、特徴量抽出部６３において算出されたｎ＋１フレームのコードＡに対応する特徴量を有する画素位置の情報が、データベース７１に登録されているｎフレームの情報より抽出され、以下、同様に処理が繰り返される。
【００８０】
このようにして、ステップＳ３１乃至ステップＳ３６の処理は、一部、並行して実行される。
【００８１】
次に、図９を参照して、図８のステップＳ３３において実行される、参照フレーム情報生成処理について説明する。
【００８２】
ステップＳ５１において、データベース制御部６５は、データベース７１に登録されている参照フレーム情報を初期化する。すなわち、データベース制御部６５は、全ての特徴量アドレスに対応するフラグアドレス０のセルに０を書き込み、フラグアドレス１乃至ｂに格納されている位置情報を削除する。
【００８３】
ステップＳ５２において、データベース制御部６５は、１フレームメモリ内の画素をカウントするカウンタのカウンタ変数ｎを０に初期化する。
【００８４】
ステップＳ５３において、特徴量抽出部６３は、図１０を用いて後述する特徴量算出処理を実行する。
【００８５】
ステップＳ５４において、データベース制御部６５は、特徴量抽出部６３において抽出された参照フレームＦｒの注目画素の特徴量であるコードＢおよびコードＣの供給を受け、データベース７１から、コードＢおよびコードＣに対応する特徴量アドレスの、フラグアドレス０に記載されている値Ｋを読み込む。上述したように、１つの注目画素に対して、２つの特徴量であるコードＢおよびコードＣが決定されるので、２箇所の特徴量アドレスに対応する値Ｋが読み出される。
【００８６】
ステップＳ５５において、データベース制御部６５は、ステップＳ５４において読み出した値Ｋを、それぞれ、Ｋ＝Ｋ＋１とし、データベース７１の対応する特徴量アドレスの、フラグアドレス０に書き込む。
【００８７】
ステップＳ５６において、データベース制御部６５は、特徴量抽出部６３から供給された、参照フレームＦｒの注目画素の位置情報を、データベース７１の対応する特徴量アドレスのフラグアドレスＫ＋１で示される２箇所のセルに書き込む。
【００８８】
ステップＳ５７において、データベース制御部６５は、カウンタ変数ｎをインクリメントして、ｎ＝ｎ＋１とする。
【００８９】
ステップＳ５８において、データベース制御部６５は、カウンタ変数ｎ＝１フレームの画素数であるか否かを判断する。ステップＳ５８において、カウンタ変数ｎ＝１フレームの画素数ではないと判断された場合、処理は、ステップＳ５３に戻り、それ以降の処理が繰り返される。ステップＳ５８において、カウンタ変数ｎ＝１フレームの画素数であると判断された場合、処理は、終了される。
【００９０】
このような処理により、図６を用いて説明したデータベース７１のフラグアドレス＝０のセルであるセル（０，０）乃至セル（ａ，０）に、対応する特徴量を有する参照フレームＦｒの画素位置の候補の数が格納され、データベース７１のフラグアドレス＝１乃至ｂのセルであるセル（０，１）乃至セル（ａ，ｂ）に、対応する特徴量を有する参照フレームＦｒの画素位置が格納される。換言すれば、参照フレームＦｒにおいて、同一の特徴量を有する可能性の高い画素の画素位置が、特徴量毎にアドレシングされて、データベース７１に格納される。
【００９１】
次に、図１０のフローチャートを参照して、図９のステップＳ５３において実行される特徴量算出処理について説明する。
【００９２】
ステップＳ８１において、特徴量抽出部６４は、入力された参照フレームＦｒの注目画素の画素値の上位３ビットを抽出する。
【００９３】
ステップＳ８２において、特徴量抽出部６４は、コードＢおよびコードＣを算出して、処理は、図９のステップＳ５４に戻る。
【００９４】
ステップＳ８１およびステップＳ８２の処理は、具体的には、上述した、式（３）および式（４）を用いて、コードＢおよびコードＣを算出する処理と等価である。
【００９５】
この処理により、コードＢおよびコードＣの２つのコードが特徴量として算出されるため、図８のステップＳ５４においては、コードＢおよびコードＣに対応する２つの特徴量アドレスにおいて、フラグアドレス０に記載されている値Ｋが読み込まれて、ステップＳ５５において、それぞれインクリメントされ、ステップＳ５６において、コードＢおよびコードＣに対応する２つの特徴量アドレスに対応するフラグアドレスＫ＋１に、注目画素の画素位置情報が記載される。
【００９６】
すなわち、１フレームの画素全ての処理が終了した場合、図６を用いて説明したデータベース７１のセルのうち、１フレームの画素数の２倍のセルに、位置情報が記載される。
【００９７】
次に、図１１のフローチャートを参照して、図８のステップＳ３６において実行されるマッチング処理について説明する。
【００９８】
ステップＳ１０１において、データベース検索部６６は、特徴量抽出部６３から、カレントフレームＦｃの注目画素のコードＡの入力を受ける。
【００９９】
ステップＳ１０２において、データベース検索部６６は、データベース７１に記録されている参照フレームＦｒの特徴量のうち、カレントフレームＦｃのコードＡと等しいものを検出する。
【０１００】
ステップＳ１０３において、データベース検索部６６は、検出された特徴量のアドレスのフラグアドレス１乃至フラグアドレスＫのセルに記載されている画素位置情報を読み込んで、動きベクトル決定部６７に供給する。
【０１０１】
ステップＳ１０４において、動きベクトル決定部６７は、読み込まれた画素位置の中で、カレントフレームＦｃの注目画素に最も近い画素位置を検出する。
【０１０２】
ステップＳ１０５において、動きベクトル決定部６７は、注目画素の画素位置と検出された画素位置を基に、動きベクトルを算出し、処理が終了される。
【０１０３】
ここでは、カレントフレームＦｃの注目画素から最も近い候補が、対応する参照フレームＦｒの画素であるものとして説明したが、動きベクトルの検出方法は、これ以外の方法であってもかまわない。
【０１０４】
また、データベースを２つ設けることにより、データベースへの登録処理である参照フレーム情報生成処理と、データベースに登録された情報を用いて実行されるマッチング処理を、並行して行えるようにし、処理を高速化することができる。
【０１０５】
図１２は、データベースを２つ備えるようにした動き検出部１０１の構成を示すブロック図である。なお、図４における場合と対応する部分には同一の符号を付してあり、その説明は適宜省略する。
【０１０６】
すなわち、図１２の動き検出部１０１は、データベース制御部６５に代わり、データベース７１−１およびデータベース７１−２の２つのデータベースを備え、データベース選択処理部１２１を有するデータベース制御部１１１が備えられ、フレームメモリ６２が省略されている以外は、基本的に、図４を用いて説明した動き検出部５１と同様の構成を有するものである。
【０１０７】
図１３は、図１２のデータベース制御部の更に詳細な構成を示すブロック図である。データベース選択処理部１２１は、データベース７１−１およびデータベース７１−２の一方に、特徴量抽出部６４から供給されるカレントフレームＦｃの特徴量が登録され、他方にすでに登録されている参照フレームＦｒの情報が、データベース検索部６６により読み込まれるように、情報の入出力を制御する。
【０１０８】
すなわち、データベース制御部１１１には、データベース７１−１およびデータベース７１−２の２つのデータベースが備えられ、例えば、カレントフレームＦｃの特徴量が、データベース７１−２に登録されている間、その前の処理でデータベース７１−１に登録された参照フレームＦｒの情報が、データベース検索部６６により読み込まれる。そして、データベース７１−１に登録された参照フレームＦｒと、カレントフレームＦｃとのマッチング処理、および、カレントフレームＦｃの特徴量のデータベース７１−２への登録処理が終了した後、次のフレームがカレントフレームＦｃとなり、カレントフレームＦｃの特徴量がデータベース７１−１に登録され、データベース７１−２に登録されている情報が、参照フレームＦｒの情報としてデータベース検索部６６により読み込まれる。
【０１０９】
すなわち、データベース７１−１からの情報の読み出しと、データベース７１−２への情報の書き込みが、並行して行われ、データベース７１−２からの情報の読み出しと、データベース７１−１への情報の書き込みが、並行して行われる。
【０１１０】
図１４のフローチャートを参照して、図１２の動き検出部１０１が実行する動き検出処理２について説明する。
【０１１１】
ステップＳ１２１において、フレームメモリ６１は、フレームの入力を受ける。フレームメモリ６１は、入力されたフレームを、特徴量抽出部６３および特徴量抽出部６４に供給する。
【０１１２】
ステップＳ１２２において、図９を用いて説明した参照フレーム情報生成処理が、特徴量抽出部６４において実行される。
【０１１３】
特徴量抽出部６３は、ステップＳ１２３において、フレームメモリ６１から入力されたフレームの注目画素の画素値の上位４ビットを抽出し、ステップＳ１２４において、コードＡを算出する。ステップＳ１２３およびステップＳ１２４の処理は、上述した、式（２）の演算処理に等しい。
【０１１４】
ステップＳ１２５において、図１１を用いて説明したマッチング処理が実行されて、処理が終了される。
【０１１５】
ステップＳ３１乃至ステップＳ３６の処理は、一部、並行して実行される。例えば、ｎ−１番目に入力されたフレーム（ｎ−１フレーム）、ｎ番目に入力されたフレーム（ｎフレーム）、および、ｎ＋１番目に入力されたフレーム（ｎ＋１フレーム）が処理されるタイミングの例について、図１５を用いて説明する。
【０１１６】
例えば、フレームメモリ６１にｎフレームが入力されたとき、特徴量抽出部６４において、ｎ−１フレームのコードＢおよびコードＣが算出されて、データベース制御部１１１に供給される。
【０１１７】
次に、特徴量抽出部６３において、ｎフレームのコードＡが算出されているとき、特徴量抽出部６４において、ｎフレームのコードＢおよびコードＣが算出される。この処理と並行して、特徴量抽出部６４において算出されたｎ−１フレームのコードＢおよびコードＣがデータベース制御部１１１の処理により、データベース７１のいずれか一方（以下、データベース１と称する）に登録される。このとき、フレームメモリ６１には、ｎ＋１フレームが入力される。
【０１１８】
そして、その後、データベース検索部６６において、特徴量抽出部６３において算出されたｎフレームのコードＡに対応する特徴量を有する画素位置の情報が、データベース１に登録されているｎ−１フレームの情報より抽出される（マッチング）。このとき、特徴量抽出部６４において算出された、フレームｎのコードＢおよびコードＣが、データベース制御部１１１の処理により、データベース７１の他方（以下、データベース２と称する）に登録される。
【０１１９】
すなわち、データベース１からの情報の読み出しと、データベース２への情報の書き込みが、並行して行われる。更に、並行して、特徴量抽出部６３において、ｎ＋１フレームのコードＡが算出され、特徴量抽出部６４において、ｎ＋１フレームのコードＢおよびコードＣが算出される。
【０１２０】
そして、データベース検索部６６において、特徴量抽出部６３において算出されたｎ＋１フレームのコードＡに対応する特徴量を有する画素位置の情報が、データベース２に登録されているｎフレームの情報より抽出される（マッチング）。このとき、特徴量抽出部６４において算出されたフレームｎ＋１のコードＢおよびコードＣが、データベース制御部１１１の処理によりデータベース１に登録され、以下、同様に処理が繰り返される。
【０１２１】
このような構成にすることにより、図８を用いて説明した場合と比較して、処理を高速化することが可能となる。
【０１２２】
以上の処理では、特徴量として、注目画素の画素値を用いるものとして説明したが、特徴量として、これ以外のものが用いられた場合においても、本発明は適用される。特徴量としては、例えば、注目画素の画素値、注目画素を中心とした所定の画素範囲のブロックの複数の画素値またはこれらの画素値の平均値、注目画素を中心とした所定の画素範囲のブロックの画素値を基に算出されるＡＤＲＣのコード、ブロック内の画素値分布のダイナミックレンジ、あるいは、ブロック内の画素値分布の最小値などが、単独、または、複数の特徴量の集合として用いられる。
【０１２３】
例えば、特徴量として、ＡＤＲＣが用いられる場合、特徴量抽出部６３は、図１６に示されるブロック図のように構成される。
【０１２４】
クラスタップ抽出部１５１は、入力された画像情報のうち、特徴量の抽出に必要な注目画素に対応する周辺画素（クラスタップ）の情報（画素値）を抽出しＤＲ（ダイレクトレンジ）演算部１５２、および、ＡＤＲＣコード生成部１５３に出力する。また、クラスタップ抽出部１５１は、クラスタップのパターンを記憶したタップテーブル１５１ａを有しており、タップテーブル１５１ａに記憶されているクラスタップのパターンに基づいて、抽出するクラスタップのパターンを決定する。
【０１２５】
すなわち、タップテーブル１５１ａは、クラスタップのパターンとして、図１７で示すように注目画素（図中黒丸で表示されている画素）を中心とした３画素×３画素からなるブロックの最外周位置に配置される８画素（図中斜線で塗りつぶされている画素）のパターンや、図１８で示すように、注目画素（図中黒丸で表示されている画素）を中心とした５画素×５画素からなるブロックの最外周位置に配置される１６画素（図中斜線で塗りつぶされている画素）のパターンや、図１９で示すように、注目画素（図中黒丸で表示されている画素）を中心とした７画素×７画素からなるブロックの最外周位置に配置される２４画素（図中斜線で塗りつぶされている画素）パターンや、さらに、図示しないが、注目画素（図中黒丸で表示されている画素）を中心としたｎ画素×ｎ画素からなるブロックの最外周位置に配置される４（ｎ−１）画素パターンを記憶している。
【０１２６】
また、クラスタップのパターンは、図２０で示すように、注目画素の上下左右の１画素からなる４画素であってもよいし、図２１で示すように、注目画素の上下左右の２画素からなる８画素であってもよいし、図２２で示すように、注目画素の上下左右の３画素からなる１２画素であってもよいし、さらには、図示しないが、注目画素の上下左右のｍ画素からなる４ｍ画素であってもよい。さらに、クラスタップは、図示した以外の構成でもよく、例えば、注目画素との位置関係が非対称となる配置のものであってもよい。
【０１２７】
ＤＲ（ダイナミックレンジ）演算部１５２は、クラスタップ抽出部１５１より入力されるクラスタップの情報（画素値）からダイナミックレンジを求め、ダイナミックレンジをＡＤＲＣ（Ａｄａｐｔｉｖｅ　Ｄｙｎａｍｉｃ　Ｒａｎｇｅ　Ｃｏｄｉｎｇ）コード生成部１５３に出力するとともに、ダイナミックレンジを求める際に得られる最小値の情報をＡＤＲＣコード生成部１５３に出力する。すなわち、クラスタップのパターンが、例えば、図２０で示すものであった場合、各クラスタップＣ１乃至Ｃ４の情報（画素値レベル）が、（Ｃ１，Ｃ２，Ｃ３，Ｃ４）＝（６０，９０，５１，１００）であるとき、その関係は、図２３で示すようになる。このような場合、ダイナミックレンジは、画素値レベルの最小値と最大値の差として定義され、その値は、以下の式（５）で定義される。
【０１２８】
ＤＲ＝Ｍａｘ−Ｍｉｎ＋１・・・（５）
【０１２９】
ここで、Ｍａｘは、クラスタップの情報である画素値レベルの最大値であり、Ｍｉｎは、クラスタップの画素値レベルの最小値を示す。ここで、１を加算するのは、クラスを定義するためである（例えば、０，１で示されるクラスを設定する場合、両者の差分は１であるが、クラスとしては２クラスとなるため、差分に１を加算する）。従って、図２３の場合、クラスタップＣ３の画素値レベル１００が最大値であり、クラスタップＣ１の画素値レベル５１が最小値となるので、ＤＲは、５０（＝１００−５１＋１）となる。
【０１３０】
このように、ＤＲ演算部１５２は、ダイナミックレンジを演算するにあたり、クラスタップの画素値レベルのうちの最小値と最大値を検出することになるので、その最小値（または最大値）をＡＤＲＣコード生成部１５３に出力する。
【０１３１】
ＡＤＲＣコード生成部１５３は、ＤＲ演算部１５２より入力されたダイナミックレンジの値と最小値Ｍｉｎとから、クラスタップの各画素値レベルを基に、ＡＤＲＣコードからなる量子化コードを生成して出力する。より詳細には、ＡＤＲＣコードは、クラスタップの各画素値レベルを以下の式（６）の代入することにより求められる。
【０１３２】
Ｑ＝Ｒｏｕｎｄ（（Ｌ−Ｍｉｎ＋０．５）×（２＾ｎ）／ＤＲ）・・・（６）
【０１３３】
ここで、Ｒｏｕｎｄは切捨てを、Ｌは画素値レベルを、ｎは割当てビット数を、（２＾ｎ）は２のｎ乗を、それぞれ示している。
【０１３４】
従って、例えば、割当てビット数ｎが１であった場合、各クラスタップの画素値レベルは、以下の式（７）で示される閾値ｔｈ以上であれば１であり、閾値ｔｈより小さければ０とされる。
【０１３５】
ｔｈ＝ＤＲ／２−０．５＋Ｍｉｎ・・・（７）
【０１３６】
結果として、割当てビット数ｎが１である場合、図２３で示すようなクラスタップが得られたとき、閾値ｔｈは、７５．５（＝５０／２−０．５＋５１）となるので、ＡＤＲＣコードは、ＡＤＲＣ（Ｃ１，Ｃ２，Ｃ３，Ｃ４）＝０１０１となる。
【０１３７】
そして、特徴量抽出部６３が図１６を用いて説明した構成を有している場合、特徴量抽出部６４は、図２４のように構成される。なお、図１６における場合と対応する部分には同一の符号を付してあり、その説明は適宜省略する。
【０１３８】
すなわち、図２４の特徴量抽出部６４は、ＡＤＲＣコード生成部１５３により生成されたＡＤＲＣコードを変換するコード変換部１６１が更に備えられている以外は、図１６の特徴量抽出部６３と基本的に同様の構成を有するものである。
【０１３９】
コード変換部１６１は、供給されたＡＤＲＣコードを１ビットずつ反転したコードを生成し、データベース制御部６５、または、データベース制御部１１１に供給する。具体的には、コード変換部１６１は、ＡＤＲＣコード生成部１５３から、ＡＤＲＣ（Ｃ１，Ｃ２，Ｃ３，Ｃ４）＝０１０１の供給を受けた場合、１ビット反転された１１０１，０００１，０１１１，０１００の４つのコードを生成して、入力されたＡＤＲＣ（Ｃ１，Ｃ２，Ｃ３，Ｃ４）＝０１０１とともに、データベース制御部６５、または、データベース制御部１１１に供給する。
【０１４０】
参照フレームＦｒとカレントフレームＦｃの対応する画素の特徴量は、同一であるはずであるが、例えば、ノイズなどの影響により、特徴が変化してしまうことが考えられる。特徴量として、ＡＤＲＣコードが用いられる場合、例えば、画素値が閾値ｔｈに近い値を有しているいずれかのビットが、特徴量の変化によって反転してしまう恐れがある。
【０１４１】
特徴量抽出部６４においては、コード変換部１６１の処理により、生成されるＡＤＲＣコードから、１ビット反転されたコードが生成されて、出力される。すなわち、ノイズなどの影響により変化する可能性のある特徴量を含む複数の特徴量が出力される。
【０１４２】
データベース制御部６５、または、データベース制御部１１１は、供給されたＡＤＲＣ（Ｃ１，Ｃ２，Ｃ３，Ｃ４）＝０１０１と、１１０１，０００１，０１１１，０１００の４つのコードとを特徴量として、データベース７１の対応する特徴量アドレスに、それらの画素位置情報を格納する。そして、上述した場合と同様にして、マッチング処理が実行されて、カレントフレームＦｃの注目画素から最も近い候補が、対応する参照フレームＦｒの画素として求められて、動きベクトルが検出される。
【０１４３】
ここでは、１ビット反転により、ノイズなどの影響により変化する可能性のある特徴量を含む複数の特徴量を生成するものとして説明しているが、例えば、ノイズの影響が大きい場合など、データベース７１の記憶容量を増やして、１ビット反転のみならず、２ビット反転のコードを作成し、データベース７１に格納するようにすることにより、参照フレームＦｒとカレントフレームＦｃの対応する画素の特徴量が大きく変化してしまった場合においても、正しい動きベクトルを求めるようにすることができる。
【０１４４】
上述した一連の処理は、ソフトウェアにより実行することもできる。そのソフトウェアは、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０１４５】
この記録媒体は、図２５に示すように、コンピュータとは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク２４１（フレキシブルディスクを含む）、光ディスク２４２（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ　Ｄｉｓｋ−Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ），ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｋ）を含む）、光磁気ディスク２４３（ＭＤ（Ｍｉｎｉ−Ｄｉｓｋ）（商標）を含む）、もしくは半導体メモリ１４４などよりなるパッケージメディアなどにより構成される。
【０１４６】
図２５を用いて、パーソナルコンピュータ２０１について説明する。
【０１４７】
ＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）２２１は、入出力インターフェース２２２および内部バス２２３を介して、ユーザが、入力部２２４を用いて入力した各種指令に対応する信号や、ネットワークインターフェース２３０を介して、他のパーソナルコンピュータが送信した制御信号の入力を受け、入力された信号に基づいた各種処理を実行する。ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）２２５は、ＣＰＵ２２１が使用するプログラムや演算用のパラメータのうちの基本的に固定のデータを格納する。ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）２２６は、ＣＰＵ２２１の実行において使用するプログラムや、その実行において適宜変化するパラメータを格納する。ＣＰＵ２２１、ＲＯＭ２２５、およびＲＡＭ２２６は、内部バス２２３により相互に接続されている。
【０１４８】
内部バス２２３は、入出力インターフェース２２２とも接続されている。入力部２２４は、例えば、キーボード、タッチパッド、ジョグダイヤル、あるいはマウスなどからなり、ユーザがＣＰＵ２２１に各種の指令を入力するとき操作される。表示部２２７は、例えば、ＣＲＴ（Ｃａｔｈｏｄｅ　Ｒａｙ　Ｔｕｂｅ）や液晶表示装置などからなり、各種情報をテキスト、あるいはイメージなどで表示する。
【０１４９】
ＨＤＤ（ｈａｒｄ　ｄｉｓｋ　ｄｒｉｖｅ）２２８は、ハードディスクを駆動し、それらにＣＰＵ２２１によって実行するプログラムや情報を記録または再生させる。ドライブ２２９には、必要に応じて磁気ディスク２４１、光ディスク２４２、光磁気ディスク２４３、および半導体メモリ２４４が装着され、データの授受を行う。
【０１５０】
ネットワークインターフェース２３０は、他のパーソナルコンピュータや、パーソナルコンピュータ以外の各種装置と所定のケーブルを用いて有線で、もしくは無線で接続され、それらの機器との情報の授受を行ったり、インターネットを介してウェブサーバにアクセスし、情報の授受を行う。
【０１５１】
これらの入力部２２４乃至ネットワークインターフェース２３０は、入出力インターフェース２２２および内部バス２２３を介してＣＰＵ２２１に接続されている。
【０１５２】
また、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１５３】
【発明の効果】
このように、本発明によれば、カレントフレームの注目画素に対応する前記参照フレームの画素を検出することができる。特に、参照フレームとカレントフレームとで画素の特徴量が変化しても、正しく検出することができるので、正しい動きベクトルを求めることが可能となる。
【図面の簡単な説明】
【図１】従来の動き検出部の構成を示すブロック図である。
【図２】動きベクトルの検出方法を説明する図である。
【図３】図１の動き検出部による動き検出処理を説明するフローチャートである。
【図４】本発明を適用した動き検出部の構成を示すブロック図である。
【図５】特徴量として算出されるコードＡ、コードＢ、およびコードＣについて説明する図である。
【図６】図４のデータベースの構造を説明する図である。
【図７】図４の動き検出部による動き検出処理１を説明するフローチャートである。
【図８】図４の動き検出部による動き検出処理のタイミングを説明する図である。
【図９】参照フレーム情報生成処理を説明するフローチャートである。
【図１０】特徴量算出処理を説明するフローチャートである。
【図１１】マッチング処理を説明するフローチャートである。
【図１２】本発明を適用した動き検出部の他の構成を示すブロック図である。
【図１３】図１２のデータベース制御部の更に詳細な構成を示すブロック図である。
【図１４】図１２の動き検出部による動き検出処理２を説明するフローチャートである。
【図１５】図１２の動き検出部による動き検出処理のタイミングを説明する図である。
【図１６】特徴量抽出部の他の構成例を示すブロック図である。
【図１７】クラスタップを説明する図である。
【図１８】クラスタップを説明する図である。
【図１９】クラスタップを説明する図である。
【図２０】クラスタップを説明する図である。
【図２１】クラスタップを説明する図である。
【図２２】クラスタップを説明する図である。
【図２３】ＡＤＲＣコードを説明する図である。
【図２４】特徴量抽出部の他の構成例を示すブロック図である。
【図２５】パーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
５１　動き検出部，　６１，６２　フレームメモリ，　６３，６４　特徴量抽出部，　６５　データベース制御部，　６６　データベース検索部，　６７　動きベクトル決定部，　７１　データベース，　１０１　動き検出部，　１１１　データベース制御部，　１２１　データベース選択処理部，　１５１　クラスタップ抽出部，　１５１ａ　タップテーブル，　１５２　ＤＲ演算部，　１５３　ＡＤＲＣコード生成部，　１６１　コード変換部
【図１】
2004134932.tif 000004
【図２】
2004134932.tif 000005
【図３】
2004134932.tif 000006
【図４】
2004134932.tif 000007
【図５】
2004134932.tif 000008
【図６】
2004134932.tif 000009
【図７】
2004134932.tif 000010
【図８】
2004134932.tif 000011
【図９】
2004134932.tif 000012
【図１０】
2004134932.tif 000013
【図１１】
2004134932.tif 000014
【図１２】
2004134932.tif 000015
【図１３】
2004134932.tif 000016
【図１４】
2004134932.tif 000017
【図１５】
2004134932.tif 000018
【図１６】
2004134932.tif 000019
【図１７】
2004134932.tif 000020
【図１８】
2004134932.tif 000021
【図１９】
2004134932.tif 000022
【図２０】
2004134932.tif 000023
【図２１】
2004134932.tif 000024
【図２２】
2004134932.tif 000025
【図２３】
2004134932.tif 000026
【図２４】
2004134932.tif 000027
【図２５】
2004134932.tif 000028
【手続補正書】
【提出日】平成14年10月15日(2002.10.15)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2004134932.tif 000029