(57)【要約】【課題】少ない演算量で１画素以下の動きを検出できるようにする。【解決手段】フレームメモリ１１−１乃至１１−４は、入力された画像データを順次１フレーム分ずつ記憶し、クラスコード生成部１２に供給する。クラスコード生成部１２は、注目画素を含むその周囲の３×３画素の画素データを１ビットＡＤＲＣ処理することで、注目画素の特徴量としての９ビットのＡＤＲＣコードを生成する。記憶部１３のアドレスは、ＡＤＲＣコードに対応している。記憶部１３は、各フレームの座標データを、その座標の画素のＡＤＲＣコードに対応するアドレスに記憶する。記憶部１３は、注目画素を含むフレーム以外に４フレーム分の画素の座標データを記憶する。動きベクトル演算部１４は、記憶部１３に、注目画素と同一のアドレスに記憶されている画素のデータに基づいて動きベクトルを演算する。本発明は、画像処理装置に適用できる。【選択図】      図１
2005006254.tif 000002
【特許請求の範囲】
【請求項１】
動きを検出する範囲の複数のフレームの画素データを保持する保持手段と、
前記保持手段により保持された前記画素データのうちの注目画素の特徴を検出する検出手段と、
前記注目画素の前記フレームにおける座標を、前記検出手段により検出された前記特徴を基準にして記憶する記憶手段と、
前記検出手段により検出された前記特徴と同一の特徴を有する他のフレームの画素であって、前記注目画素との残差が最小となる画素を、前記記憶手段に記憶されている前記座標の画素の中から検索する検索手段と、
前記検索手段により検索された前記画素と前記注目画素の座標の差、並びに、前記検索手段により検索された前記画素のフレームと前記注目画素のフレームの差に基づいて、動きベクトルを演算する演算手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記検出手段は、前記特徴として、ＡＤＲＣコードを検出する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記記憶手段は、前記座標を、前記特徴をアドレスとして記憶する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
動きを検出する範囲の複数のフレームの画素データを保持する保持ステップと、
前記保持ステップの処理により保持された前記画素データのうちの注目画素の特徴を検出する検出ステップと、
前記注目画素の前記フレームにおける座標を、前記検出ステップの処理により検出された前記特徴を基準にして記憶する記憶ステップと、
前記検出ステップの処理により検出された前記特徴と同一の特徴を有する他のフレームの画素であって、前記注目画素との残差が最小となる画素を、前記記憶ステップの処理により記憶されている前記座標の画素の中から検索する検索ステップと、
前記検索ステップの処理により検索された前記画素と前記注目画素の座標の差、並びに、前記検索ステップの処理により検索された前記画素のフレームと前記注目画素のフレームの差に基づいて、動きベクトルを演算する演算ステップと
を含むことを特徴とする情報処理方法。
【請求項５】
動きを検出する範囲の複数のフレームの画素データを保持する保持ステップと、
前記保持ステップの処理により保持された前記画素データのうちの注目画素の特徴を検出する検出ステップと、
前記注目画素の前記フレームにおける座標を、前記検出ステップの処理により検出された前記特徴を基準にして記憶する記憶ステップと、
前記検出ステップの処理により検出された前記特徴と同一の特徴を有する他のフレームの画素であって、前記注目画素との残差が最小となる画素を、前記記憶ステップの処理により記憶されている前記座標の画素の中から検索する検索ステップと、
前記検索ステップの処理により検索された前記画素と前記注目画素の座標の差、並びに、前記検索ステップの処理により検索された前記画素のフレームと前記注目画素のフレームの差に基づいて、動きベクトルを演算する演算ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項６】
動きを検出する範囲の複数のフレームの画素データを保持する保持ステップと、
前記保持ステップの処理により保持された前記画素データのうちの注目画素の特徴を検出する検出ステップと、
前記注目画素の前記フレームにおける座標を、前記検出ステップの処理により検出された前記特徴を基準にして記憶する記憶ステップと、
前記検出ステップの処理により検出された前記特徴と同一の特徴を有する他のフレームの画素であって、前記注目画素との残差が最小となる画素を、前記記憶ステップの処理により記憶されている前記座標の画素の中から検索する検索ステップと、
前記検索ステップの処理により検索された前記画素と前記注目画素の座標の差、並びに、前記検索ステップの処理により検索された前記画素のフレームと前記注目画素のフレームの差に基づいて、動きベクトルを演算する演算ステップと
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報処理装置および方法、記録媒体、並びにプログラムに関し、特に、簡単且つ迅速に動きベクトルを変動することができるようにした情報処理装置および方法、記録媒体、並びにプログラムに関する。
【０００２】
【従来の技術】
最近、画像データを圧縮化し、伝送する技術が普及してきた。動画像データを圧縮する場合、画像の動きを検出し、その動きに対応する動きベクトルに基づいて、画像データを圧縮する処理が行われる。動きベクトルを検出するのに各種の提案がなされている（例えば、特許文献１および特許文献２参照）。最もよく使用されるのがブロックマッチング法である。
【０００３】
【特許文献１】
特開平０７−０８７４９４号公報
【０００４】
【特許文献２】
特開平０７−０５９０９３号公報
【０００５】
【発明が解決しようとする課題】
しかしながら、ブロックマッチング法は、演算量が大きく、また、１画素以下の動きを検出することが困難であるという課題があった。
【０００６】
本発明は、このような状況に鑑みてなされたものであり、少ない演算量で１画素以下の動きを検出することができるようにするものである。
【０００７】
【課題を解決するための手段】
本発明の情報処理装置は、動きを検出する範囲の複数のフレームの画素データを保持する保持手段と、保持手段により保持された画素データのうちの注目画素の特徴を検出する検出手段と、注目画素のフレームにおける座標を、検出手段により検出された特徴を基準にして記憶する記憶手段と、検出手段により検出された特徴と同一の特徴を有する他のフレームの画素であって、注目画素との残差が最小となる画素を、記憶手段に記憶されている座標の画素の中から検索する検索手段と、検索手段により検索された画素と注目画素の座標の差、並びに、検索手段により検索された画素のフレームと注目画素のフレームの差に基づいて、動きベクトルを演算する演算手段とを備えることを特徴とする。
【０００８】
前記検出手段は、特徴として、ＡＤＲＣコードを検出するようにすることができる。
【０００９】
前記記憶手段は、座標を、特徴をアドレスとして記憶するようにすることができる。
【００１０】
本発明の情報処理方法は、動きを検出する範囲の複数のフレームの画素データを保持する保持ステップと、保持ステップの処理により保持された画素データのうちの注目画素の特徴を検出する検出ステップと、注目画素のフレームにおける座標を、検出ステップの処理により検出された特徴を基準にして記憶する記憶ステップと、検出ステップの処理により検出された特徴と同一の特徴を有する他のフレームの画素であって、注目画素との残差が最小となる画素を、記憶ステップの処理により記憶されている座標の画素の中から検索する検索ステップと、検索ステップの処理により検索された画素と注目画素の座標の差、並びに、検索ステップの処理により検索された画素のフレームと注目画素のフレームの差に基づいて、動きベクトルを演算する演算ステップとを含むことを特徴とする。
【００１１】
本発明の記録媒体のプログラムは、動きを検出する範囲の複数のフレームの画素データを保持する保持ステップと、保持ステップの処理により保持された画素データのうちの注目画素の特徴を検出する検出ステップと、注目画素のフレームにおける座標を、検出ステップの処理により検出された特徴を基準にして記憶する記憶ステップと、検出ステップの処理により検出された特徴と同一の特徴を有する他のフレームの画素であって、注目画素との残差が最小となる画素を、記憶ステップの処理により記憶されている座標の画素の中から検索する検索ステップと、検索ステップの処理により検索された画素と注目画素の座標の差、並びに、検索ステップの処理により検索された画素のフレームと注目画素のフレームの差に基づいて、動きベクトルを演算する演算ステップとを含むことを特徴とする。
【００１２】
本発明のプログラムは、動きを検出する範囲の複数のフレームの画素データを保持する保持ステップと、保持ステップの処理により保持された画素データのうちの注目画素の特徴を検出する検出ステップと、注目画素のフレームにおける座標を、検出ステップの処理により検出された特徴を基準にして記憶する記憶ステップと、検出ステップの処理により検出された特徴と同一の特徴を有する他のフレームの画素であって、注目画素との残差が最小となる画素を、記憶ステップの処理により記憶されている座標の画素の中から検索する検索ステップと、検索ステップの処理により検索された画素と注目画素の座標の差、並びに、検索ステップの処理により検索された画素のフレームと注目画素のフレームの差に基づいて、動きベクトルを演算する演算ステップとをコンピュータに実行させることを特徴とする。
【００１３】
本発明においては、注目画素のフレームにおける座標が、特徴を基準にして記憶される。また、注目画素の座標と距離が最小となる座標が、記憶されている座標から検索され、検索された座標と注目画素の座標との差、並びに検索された座標の画素のフレームと、注目画素のフレームの差に基づいて動きベクトルが演算される。
【００１４】
【発明の実施の形態】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００１５】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００１６】
［請求項１］  動きを検出する範囲の複数のフレームの画素データを保持する保持手段（例えば、図１のフレームメモリ１１−１乃至１−４）と、
前記保持手段により保持された前記画素データのうちの注目画素の特徴を検出する検出手段（例えば、図１のクラスコード生成部１２）と、
前記注目画素の前記フレームにおける座標を、前記検出手段により検出された前記特徴を基準にして記憶する記憶手段（例えば、図１の記憶部１３）と、
前記検出手段により検出された前記特徴と同一の特徴を有する他のフレームの画素であって、前記注目画素との残差が最小となる画素を、前記記憶手段に記憶されている前記座標の画素の中から検索する検索手段（例えば、図８のマッチング演算部７４、残差取得部７５、最小値抽出部７６）と、
前記検索手段により検索された前記画素と前記注目画素の座標の差、並びに、前記検索手段により検索された前記画素のフレームと前記注目画素のフレームの差に基づいて、動きベクトルを演算する演算手段（例えば、図８の動きベクトル演算部７７）と
を備えることを特徴とする情報処理装置（例えば、図１の動き検出装置１）。
［請求項２］  前記検出手段は、前記特徴として、ＡＤＲＣコードを検出する（例えば、図４のステップＳ３４の処理）
ことを特徴とする請求項１に記載の情報処理装置。
［請求項３］  前記記憶手段は、前記座標を、前記特徴をアドレスとして記憶する（例えば、図６のステップＳ５４の処理）
ことを特徴とする請求項１に記載の情報処理装置。
［請求項４］  動きを検出する範囲の複数のフレームの画素データを保持する保持ステップ（例えば、図３のステップＳ１１）と、
前記保持ステップの処理により保持された前記画素データのうちの注目画素の特徴を検出する検出ステップ（例えば、図３のステップＳ１２）と、
前記注目画素の前記フレームにおける座標を、前記検出ステップの処理により検出された前記特徴を基準にして記憶する記憶ステップ（例えば、図６のステップＳ５４）と、
前記検出ステップの処理により検出された前記特徴と同一の特徴を有する他のフレームの画素であって、前記注目画素との残差が最小となる画素を、前記記憶ステップの処理により記憶されている前記座標の画素の中から検索する検索ステップ（例えば、図９のステップＳ８９）と、
前記検索ステップの処理により検索された前記画素と前記注目画素の座標の差、並びに、前記検索ステップの処理により検索された前記画素のフレームと前記注目画素のフレームの差に基づいて、動きベクトルを演算する演算ステップ（例えば、図９のステップＳ９４）と
を含むことを特徴とする情報処理方法。
【００１７】
なお、請求項５と請求項６の実施の形態との対応関係は、請求項４における場合と同様である。
【００１８】
次に図面を参照して、本発明の実施の形態について説明する。
【００１９】
図１は、本発明を適用した、動き検出装置の構成例を表している。この構成例においては、動き検出装置１は、４つのフレームメモリ１１−１乃至１１−４を有している。図示せぬ装置から入力されたデジタル画像データは、フレームメモリ１１−１に、その１フレーム分が保持された後、そこから読み出されクラスコード生成部１２に供給される。フレームメモリ１１−２には、フレームメモリ１１−１より出力された１フレーム分の画像データが記憶される。フレームメモリ１１−２より出力された画像データは、クラスコード生成部１２に供給されるとともに、フレームメモリ１１−３に供給され、記憶される。フレームメモリ１１−３に記憶された１フレーム分の画像データは、同様にそこから読み出され、クラスコード生成部１２に供給されるとともに、フレームメモリ１１−４に供給される。フレームメモリ１１−４は、入力された画像データを１フレーム分記憶した後、クラスコード生成部１２に出力する。
【００２０】
以上のようにして、フレームメモリ１１−１には、最新の１フレーム分の画像データが保持され、フレームメモリ１１−２には、時間的に１フレーム分だけ過去の画像データが記憶され、フレームメモリ１１−３には、フレームメモリ１１−２に記憶された画像データよりさらに１フレーム分だけ過去の画像データが記憶され、フレームメモリ１１−４には、フレームメモリ１１−３に記憶されたフレームより、さらに１フレーム分だけ過去の画像データが記憶されることになる。結果的にクラスコード生成部１２には、最新の連続する４フレーム分の画像データが供給される。
【００２１】
クラスコード生成部１２は、フレームメモリ１１−１乃至１１−４から入力された４フレーム分の画像データに基づいて、注目画素の特徴を表す特徴量として、１ビットＡＤＲＣ処理によりクラスコードを生成する。
【００２２】
クラスコード生成部１２により生成されたクラスコード（ＡＤＲＣコード）は、動きベクトル演算部１４に供給される。この時動きベクトル演算部１４には、クラスコード以外に注目画素の、そのフレームにおける位置を表す座標データ、並びに画素データそのものが供給される。
【００２３】
動きベクトル演算部１４は、クラスコード生成部１２（または、動きベクトル演算部１４）はまた、記憶部１３に、チップ番号（図２を参照して後述する）、ＡＤＲＣコード、および座標データを出力する。注目画素の座標データは、その注目画素のクラスコード（ＡＤＲＣコード）に対応する記憶部１３のアドレスに記憶される。
【００２４】
動きベクトル演算部１４は、記憶部１３にブロックマッチングのためのＡＤＲＣコードを出力し、対応する候補座標（フレーム番号と座標データ）の供給を受け、座標データを用いて、動きベクトルを演算し、図示せぬ他の装置に出力する。
【００２５】
図２は、記憶部１３の内部の構成例を表している。この構成例においては、記憶部１３は、チップセレクタ３１、スイッチ３２、ＭＥメモリ３３−０乃至３３−４、スイッチ３４、並びにチップセレクタ３５により構成されている。
【００２６】
チップセレクタ３１には、クラスコード生成部１２または動きベクトル演算部１４から、ＡＤＲＣコードと座標データのほか、選択するチップを指定するチップ番号が入力されている。チップセレクタ３５は、入力されたチップ番号に対応してスイッチ３２を制御し、ＭＥメモリ３３−０乃至３３−４のうち、チップ番号に対応するものを選択させる。チップ番号の値Ｎが０である場合、ＭＥメモリ３３−０が選択され、１である場合、ＭＥメモリ３３−１が選択される。以下同様に、チップ番号の値Ｎが、２，３，または４である場合、それぞれＭＥメモリ３３−２，３３−３，または３３−４が選択される。
【００２７】
チップセレクタ３１は、ＭＥメモリ３３−０乃至３３−４のうち、スイッチ３２により選択されたＭＥメモリの、ＡＤＲＣコードに対応するアドレスに座標データを書き込む処理を実行する。
【００２８】
動きベクトル演算部１４より供給されたチップ番号とＡＤＲＣコードが、チップセレクタ３５に供給される。チップセレクタ３５は、スイッチ３４を制御し、ＭＥメモリ３３−０乃至３３−４のうち、チップ番号に対応するものを選択し、そのＡＤＲＣコードに対応するアドレスに記憶されている座標データを読み出させる。チップセレクタ３５は、動きベクトル演算部１４より供給されたチップ番号で指定されたＭＥメモリのＡＤＲＣコードで指定されたアドレスに記憶されている座標データを、メモリ番号とともに、動きベクトル演算部１４に供給する。
【００２９】
スイッチ３２とスイッチ３４は、書き込みが行われていないＭＥメモリから読み出しが行われるように制御される。
【００３０】
次に、図３のフローチャートを参照して、図１の動き検出装置１の動作について説明する。
【００３１】
ステップＳ１１において、フレームメモリ１１−１乃至１１−４により、４フレーム分の画素データを記憶する処理が実行される。すなわち、入力された画像データが、１フレーム分ずつ、フレームメモリ１１−１乃至１１−４に順次記憶され、合計連続する４フレーム分の画像データがフレームメモリ１１−１乃至１１−４に記憶される。
【００３２】
ステップＳ１２において、クラスコード生成部１２は、フレームメモリ１１−１乃至１１−４に記憶された４フレーム分の画像データに基づいて、注目画素のクラスコードを生成する。このクラスコード生成処理については、図４のフローチャートを参照して後述する。
【００３３】
クラスコード生成部１２は、注目画素の特徴量として、注目画素を１ビットＡＤＲＣ（Ａｄａｐｔｉｖｅ  Ｄｙｎａｍｉｃ  Ｒａｎｇｅ  Ｃｏｄｉｎｇ）処理し、ＡＤＲＣコードを生成する。
【００３４】
動きベクトル演算部１３は、ステップＳ１３において、動きベクトル演算処理を実行する。具体的には、クラスコード生成部１２より供給された注目画素の座標データが、その注目画素のＡＤＲＣコードに対応する記憶部１３のアドレスに記憶される。さらに、動きベクトル演算部１４は、注目画素が属するフレーム以外のフレームの、注目画素の特徴（アドレス）に対応するアドレスに記憶されている座標の画素データ中から、注目画素との残差が最小のものを選択し、それに基づいて動きベクトルを演算する。
動きベクトル演算処理の詳細については、図６のフローチャートを参照して後述する。
【００３５】
次に、図４のフローチャートを参照して、図３のステップＳ１２におけるクラスコード生成処理について説明する。
【００３６】
ステップＳ３１において、クラスコード生成部１２は、フレームメモリ１１−１乃至１１−４の中から１つのフレームメモリを選択する。ステップＳ３２において、クラスコード生成部１２は、スッテプＳ３１で選択したフレームメモリに記憶されている画素の中から１つの画素を注目画素として抽出する。
【００３７】
ステップＳ３３において、クラスコード生成部１２は、注目画素の近傍の他の画素をクラスタップとして抽出する。１つの注目画素が選択された場合、それに対応するクラスタップの位置は、予め定められている。
【００３８】
例えば、注目画素を含むその周囲の３×３個（合計９個）の画素データがクラスタップとして抽出される。画素データの値が、０乃至２５５のいずれかの値として表現される場合（８ビットで表現される場合）、予め設定されている所定の閾値、例えば、１２８を基準として、画素データの値が１２８より大きい場合には１とし、小さい場合には、０とする。このようにして、各クラスタップの値を１ビットで表現すると、９個のクラスタップにより、合計９ビットの値で表現される１ビットＡＤＲＣコードが生成される。このＡＤＲＣコードは、注目画素の特徴量を表している。
【００３９】
ステップＳ３５において、クラスコード生成部１２は、ステップＳ３１で選択したフレームの全ての画素を注目画素として選択し、処理したか否かを判定する。まだ全ての画素を処理していない場合には、ステップＳ３２に戻り、他の画素を注目画素として同様の処理が実行される。
【００４０】
ステップＳ３５において、そのフレームの全ての画素についての処理が終了したと判定された場合、ステップＳ３６に進み、クラスコード生成部１２は、フレームメモリ１１−１乃至１１−４に記憶されている全てのフレームについての処理を終了したか否かを判定する。まだ全てのフレームについての処理が終了していない場合には、ステップＳ３１に戻り、クラスコード生成部１２は、フレームメモリ１１−１乃至１１−４のうち、次のフレームメモリを選択し、そのフレームメモリに記憶されている画素データについて同様の処理を実行する。
【００４１】
ステップＳ３６において、動画像の全てのフレームの処理が終了したと判定された場合、処理は終了される。
【００４２】
次に、動きベクトル演算部１４における動きベクトル演算処理について説明する。このため、動きベクトル演算部１４は、図５に示される機能ブロックを有する。
【００４３】
図５において、設定部５１は、チップ番号を表す変数Ｎに所定の値を設定する。取得部５２は、設定部５１により、変数Ｎに所定の値が設定された後、動きベクトル演算に必要なＡＤＲＣコード、座標データ、および画素データをクラスコード生成部１２から取得する。
【００４４】
書き込み部５３は、取得部５２により取得された座標データを、変数Ｎにより指定されるＭＥメモリの、取得部５２により取得されたＡＤＲＣコードに対応するアドレスに書き込む処理を実行する。
【００４５】
絞り込み処理部５４は、記憶部１３に記憶されているデータに基づいて絞り込み処理を実行し、動きベクトルを演算する。
【００４６】
判定部５５は、絞り込み処理部５４により、全ての画素を処理したか否か等の判定処理を実行する。選択部５６は、判定部５５による判定結果に基づいて、次の注目画素を選択し、選択した画素に対応するデータを取得部５２に取得させる。
【００４７】
次に、図６のフローチャートを参照して、動きベクトル演算処理について説明する。
【００４８】
ステップＳ５１において、設定部５１（または、記憶部１３）は、ＭＥメモリ３３−０乃至３３−４のいずれかを表す変数Ｎに値０を初期設定する。すなわちこの処理により、ＭＥメモリ３３−０が処理対象のＭＥメモリとして指定されることになる。
【００４９】
ステップＳ５２において、取得部５２（または、記憶部１３）は、クラスコード生成部１２から注目画素のＡＤＲＣコードに用いた画素データ（すなわち、クラスタップ）を取得する。ステップＳ５３において、取得部５２は、クラスコード生成部１２から、注目画素のＡＤＲＣコードと座標データを取得する。
【００５０】
ステップＳ５４において、書き込み部５３（または、記憶部１３）は、ステップＳ５３の処理で取得された座標データを、ステップＳ５１の処理で設定された変数Ｎで表されるＭＥメモリの、ステップＳ５３の処理で取得されたＡＤＲＣコードに対応するアドレスに書き込む処理を実行する。今の場合、ステップＳ５１において、変数Ｎに０が設定されているため、ＭＥメモリ３３−０の注目画素のＡＤＲＣコードに対応するアドレスに、注目画素の座標データが書き込まれる。
【００５１】
すなわちこのとき、記憶部１３のチップセレクタ３１は、動きベクトル演算部１４の書き込み部５３から、ＭＥメモリ３３−０乃至３３−４のうち、そのいずれかを指定する変数Ｎで表されるチップ番号の入力を受け、スイッチ３２を制御し、その変数Ｎで表されるＭＥメモリ（今の場合３３−０）にスイッチを切り換える。そしてチップセレクタ３１は、ＭＥメモリ３３−０のＡＤＲＣコードで表されるアドレスに、書き込み部５３より供給される座標データを書き込む。
【００５２】
ステップＳ５５において、絞り込み処理部５４は、絞り込み処理を実行する。その処理の詳細は、図９のフローチャートを参照して後述するが、この処理により、注目画素の動きベクトルが演算される。
【００５３】
ステップＳ５６において、判定部５５は、絞り込み処理部５４の出力に基づいて、絞り込み処理が、全ての画素について行われたか否かを判定する。全ての画素について、絞り込み処理をまだ完了していないと判定された場合、ステップＳ５７に進み、選択部５６は、次の注目画素を選択する。その後、ステップＳ５２に戻り、取得部５２は、選択部５６によりステップＳ５７の処理で選択された次の注目画素のＡＤＲＣコード化用画素データを、クラスコード生成部１２から取得する。ステップＳ５３において、取得部５２は、さらに、新たな注目画素のＡＤＲＣコードと座標データをクラスコード生成部１２から取得する。ステップＳ５４において、書き込み部５３は、変数Ｎで指定されるＭＥメモリ（今の場合ＭＥメモリ３３−０）のＡＤＲＣコードに対応するアドレスに、その新たな注目画素の座標データを書き込む。
【００５４】
ステップＳ５５において、絞り込み処理部５４は、再び絞り込み処理を実行する。
【００５５】
ステップＳ５６において、判定部５５は、再び全ての画素を処理したか否かを判定し、まだ処理していない画素がある場合にはステップＳ５７に戻り、上述した場合と同様にそれ以降の処理を繰り返し実行する。
【００５６】
ステップＳ５６において、処理対象とされているフレームの全ての画素を処理したと判定された場合、ステップＳ５８に進み、判定部５５は、全てのフレームを処理したか否かを判定する。全てのフレームをまだ処理していない場合には、ステップＳ５９に進み、判定部５５は、変数Ｎの値が、最大値（ｍａｘ）と等しいか否かを判定する。この最大値（ｍａｘ）は、図２の場合、ＭＥメモリ３３−０乃至３３−４が合計５個あるので、「４」（ＭＥメモリ３３−４を表す値）とされる。
【００５７】
今の場合、変数Ｎは０であり、最大値ではないので、ステップＳ５９においてＮＯと判定され、ステップＳ６０に進む。ステップＳ６０において、設定部５１は、変数Ｎの値を１だけインクリメントする。すなわち、今の場合、変数Ｎの値が１とされる。
【００５８】
その後、ステップＳ５２に戻り、ＭＥメモリ３３−１に関して上述した場合と同様の処理が実行される。
【００５９】
この処理により、ＭＥメモリ３３−１に記憶されているフレームについての動きベクトルが求められることになる。
【００６０】
以下同様に、変数Ｎの値が１ずつインクリメントされ、ＭＥメモリ３３―２，３３−３，３３−４についても同様の処理が実行される。
【００６１】
ステップＳ５９において、変数Ｎの値が最大値と等しいと判定された場合、ステップＳ５１に戻り、再び変数Ｎの値に０が初期設定され、それ以降の処理が繰り返し実行される。
【００６２】
ステップＳ５８において、全てのフレームを処理したと判定された場合、動きベクトル演算処理は終了される。
【００６３】
以上のようにして、ＭＥメモリ３３−０乃至３３−４には、図７に示されるように、注目画素の座標データが、対応するＡＤＲＣコードで表されるアドレスに記憶される。図７の例場合、ＡＤＲＣコードは、９ビットのデータで表されるため、各ＭＥメモリ３３−ｉ（ｉ＝０，１，２，３，４）は、アドレス「０００００００００」乃至「１１１１１１１１１」を有し、注目画素の座標データを、そのＡＤＲＣコードに対応するアドレスに記憶する。図７の例の場合、アドレス「０００００００００」には、（１ａ，０ｂ），（００，０ａ），・・・（００，ａ２）の座標データが記憶されている。
【００６４】
絞り込み処理部５４は、図８に示される機能ブロックを有している。図８の例においては、絞り込み処理部５４は、設定部７１、判定部７２、取得部７３、マッチング演算部７４、残差取得部７５、最小値抽出部７６、及び動きベクトル演算部７７により構成されている。
【００６５】
設定部７１は、各種の変数に所定の値を設定する。判定部７２は、各種の変数が所定の値に達していたか否か等を判定する。取得部７３は、ＭＥメモリ３３−０乃至３３−４のいずれかから、その所定のアドレスに記憶されている座標データと画素データを取得する。マッチング演算部７４は、取得部７３で取得された座標の画素データに基づいて、ブロックマッチング処理を行う。
【００６６】
残差取得部７５は、マッチング演算部７４で行われたブロックマッチングに基づいて得られた結果の残差を取得する。最小値抽出部７６は、残差取得部７５で取得された残差に基づいて、最小の残差の画素の座標を抽出する。動きベクトル演算部７７は、最小値抽出部７６で抽出された座標に基づいて、動きベクトルを演算する。
【００６７】
次に、図９のフローチャートを参照して、図６のステップＳ５５における絞り込み処理の詳細について説明する。
【００６８】
ステップＳ８１において、設定部７１は、変数Ｍと変数ｎに、それぞれ値０を初期設定する。変数Ｍは、ＭＥメモリ３３−０乃至３３−４のうち、いずれか１つを選択するための値であり（従って、変数Ｍの値は０乃至４のいずれかの値となる）、変数ｎは、残差が最小である画素を保持するＭＥメモリを表す。
【００６９】
次に、ステップＳ８２において、設定部７１は、最小の残差の値が代入される変数ｍｉｎに、２５６×ブロック画素数の値を初期設定する。このブロック画素数は、図４のステップＳ３３において抽出されたクラスタップ（ブロック）の画素数に対応する。従って、今の場合、その値は９となる。ステップＳ８２の処理により、変数ｍｉｎに最大値（＝２５６×９）が初期設定されることになる。
【００７０】
ステップＳ８３において、判定部７２は変数Ｍの値が変数Ｎの値と等しいか否かを判定する。今の場合、変数Ｍは０であり、変数Ｎの値は、図６のステップＳ５１またはステップＳ６０の処理で設定された値である。
【００７１】
変数Ｍと変数Ｎの値が等しいと判定された場合、ステップＳ８４乃至ステップＳ８９の処理はスキップされ、ステップＳ９０に進み、判定部７２は、変数Ｍが最大値（ｍａｘ）と等しいか否かを判定する。この最大値（ｍａｘ）もこの例の場合、「４」である。最初、Ｍ＝０であり、「４」ではないので、変数Ｍは最大値ではないと判定され、ステップＳ９１に進み、変数Ｍは１だけインクリメントされ（Ｍ＝１とされ）、ステップＳ８３に戻る。
【００７２】
すなわち、変数Ｎの値は、ＭＥメモリ３３−０乃至３３−４のうち、注目画素を含むフレームのＭＥメモリに対応しており、注目画素を含むフレームにおいては、動きベクトルを検出する必要がないため、動きベクトルを検出するのに必要なステップＳ８４乃至ステップＳ８９の処理はスキップされる。
【００７３】
ステップＳ８３において、変数Ｍが変数Ｎと等しくないと判定された場合、ステップＳ８４に進み、取得部７３は、ＭＥメモリ３３−０乃至３３−４のうち、ステップＳ８１、またはステップＳ９１で設定された変数Ｍに対応するＭＥメモリのアドレスＰを参照する。すなわち取得部７３は、チップセレクタ３５にチップ番号として値Ｍを供給し、アドレス（ＡＤＲＣコード）としてアドレスＰを供給する。このアドレスＰは、図６のステップＳ５３の処理で取得された注目画素のＡＤＲＣコードである。
【００７４】
そして、ステップＳ８５において、取得部７３は、ＭＥメモリ３３−０乃至３３−４のうち、変数Ｍで指定されたＭＥメモリのアドレスＰに記憶されている座標データを、動き候補座標群として読み出す。すなわち、このときチップセレクタ３５は、変数Ｍで指定されるＭＥメモリのアドレスＰに記憶されている座標データを読み出して、取得部７３にメモリ番号とともに供給する。
【００７５】
ステップＳ８６において、マッチング演算部７４は、ステップＳ８５で取得された座標の画素データをクラスコード生成部１２から取得する。ここで取得する画素データは、ステップＳ８５の処理で取得された注目画素と同一のＡＤＲＣコード（特徴量）を有する画素データだけであるので、その数は通常のブロックマッチングにおける場合のように多くはない。従って、演算量が膨大となるようなことは防止される。
【００７６】
マッチング演算部７４は、注目画素の画素データと、対象とされる画素データ（変数Ｍで表されるＭＥメモリに記憶されている画素データであって、注目画素と同一のＡＤＲＣコードを有するもの）との残差として、例えば両者の差分の絶対値を演算する（差分の２乗でもよい）。対象とされる画素が、ｍ個存在する場合、注目画素とｍ個の画素との残差が演算される。これにより、ｍ個の残差が得られる。
【００７７】
ステップＳ８７において、残差取得部７５は、ステップＳ８６の処理でマッチング演算部７４により行われたブロックマッチング処理で得られたｍ個の残差のうち最小のものを、最小の残差を表す変数ｍｉｎｔｍｐに設定する。また、残差取得部７５は、その残差が最小となる画素のｘ，ｙ座標を、候補座標としてのｘ座標ｘｔｍｐと、ｙ座標としてのｙｔｍｐに、それぞれ設定する。
【００７８】
次にステップＳ８８において、最小値抽出部７６は、ステップＳ８７で取得された変数ｍｉｎｔｍｐの値が、変数ｍｉｎの値より小さいか否かを判定する。今の場合、変数ｍｉｎには、ステップＳ８２の処理で最大値が設定されている。従って、変数ｍｉｎｔｍｐは、変数ｍｉｎより小さいと判定され、ステップＳ８９に進み、最小値抽出部７６は、変数ｍｉｎに変数ｍｉｎｔｍｐの値を設定する。同様に、座標ｘに、ステップＳ８７の処理で設定された値ｘｔｍｐの値をが設定され、座標ｙにステップＳ８７の処理で設定された座標ｙｔｍｐの値が設定される。さらに最小値抽出部７６は、変数ｎに変数Ｍの値を設定する。
【００７９】
このように、ステップＳ８９の処理により、座標ｘ，ｙに、残差が最小の画素の座標が設定され、変数ｍｉｎに、最小の残差が設定され、変数ｎに、最小の残差を有する画素のフレームのＭＥメモリの番号が記憶されることになる。
【００８０】
ステップＳ８８において、変数ｍｉｎｔｍｐの値が変数ｍｉｎと等しいか、それより大きいと判定された場合には、ステップＳ８９の処理はスキップされる。
【００８１】
次に、ステップＳ９０に進み、判定部７２は、変数Ｍが最大値（＝４）と等しいか否かが判定され、等しくない場合には、ステップＳ９１に戻り、変数Ｍの値が１だけインクリメントされ（今の場合、Ｍ＝２とされ）、ステップＳ８３に戻り、それ以降の処理が繰り返し実行される。
【００８２】
以上のようにして、注目画素を含むフレーム以外の４つのフレームのそれぞれを参照フレームとして残差が最小の画素の座標が求められる。
【００８３】
換言すれば、４枚の参照フレームの画素であって、注目画素と同一のアドレスに記憶されている画素のうち（注目画素と同一の特徴量を有する画素のうち）、注目画素の画素値との残差が最小の画素が選択される。
【００８４】
次に、ステップＳ９２に進み、判定部７２は、変数ｎが変数Ｎより小さいか否かを判定する。変数ｎが変数Ｎと等しいかそれより大きい場合には、ステップＳ９３に進み、設定部７１は変数Ｎに変数Ｍの値を加算する。この処理は後述するステップＳ９４の処理で、（Ｎ−ｎ）の値を常に正にするためのものである。従って、変数ｎか変数Ｎより小さい場合には、（Ｎ−ｎ）の値は正になるので、ステップＳ９３の処理はスキップされる。
【００８５】
ステップＳ９２において、変数ｎが変数Ｎより小さいと判定された場合、または、ステップＳ９３において、変数Ｎに変数Ｍの値が加算された後、ステップＳ９４において、動きベクトル演算部７７は、次式を演算することで、注目画素に対する動きベクトルの座標（ｘｖｅｃ，ｙｖｅｃ）を演算する。
【００８６】
ｘｖｅｃ＝（ｘ−ｘ０）／（Ｎ−ｎ）
ｙｖｅｃ＝（ｙ−ｙ０）／（Ｎ−ｎ）
【００８７】
上記式の（ｘ０，ｙ０）は、注目画素の座標を表わす。この式の分子の値は、参照フレームの座標と注目画素の座標の差であり、分母は、参照フレームと注目画素のフレームのフレーム数の差を表している。参照フレームとして１枚のフレームだけでなく、合計４枚のフレームを用意し、そのフレームの枚数の差で座標の差を割り算するようにすることで、１画素以下の動きを検出することが可能となる。
【００８８】
以上においては、ステップＳ８６で、ブロックマッチング処理を行うようにしたが、勾配法を用いることも可能である。
【００８９】
また、画素の特徴量をＡＤＲＣコードで検出するようにしたが、その他の特徴量を検出するようにしてもよい。
【００９０】
以上においては、記憶部１３に注目画素を含むフレーム以外に４枚のフレームの画素データを記憶するようにしたが、その枚数は２枚以上であれば何枚でもよい。要は、動きを検出する範囲の複数の参照フレームの画素データが記憶されればよい。
【００９１】
上述した動き検出装置１は、画像データをハードディスク、その他の記録媒体に記録、再生する画像処理装置、その他の情報処理装置に適用できる。
【００９２】
上述した一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、動き検出装置は、図１０に示されるようなパーソナルコンピュータにより構成される。
【００９３】
図１０において、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１２１は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２２に記憶されているプログラム、または記憶部１２８からＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１２３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ１２３にはまた、ＣＰＵ１２１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【００９４】
ＣＰＵ１２１、ＲＯＭ１２２、およびＲＡＭ１２３は、バス１２４を介して相互に接続されている。このバス１２４にはまた、入出力インタフェース１２５も接続されている。
【００９５】
入出力インタフェース１２５には、キーボード、マウスなどよりなる入力部１２６、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  ｄｉｓｐｌａｙ）などよりなるディスプレイ、並びにスピーカなどよりなる出力部１２７、ハードディスクなどより構成される記憶部１２８、モデムなどより構成される通信部１２９が接続されている。通信部１２９は、インターネットを含むネットワークを介しての通信処理を行う。
【００９６】
入出力インタフェース１２５にはまた、必要に応じてドライブ１３０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア１３１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部１２８にインストールされる。
【００９７】
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【００９８】
この記録媒体は、図１０に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）を含む）、光磁気ディスク（ＭＤ（Ｍｉｎｉ−Ｄｉｓｋ）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア１３１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているＲＯＭ１２２や、記憶部１２８に含まれるハードディスクなどで構成される。
【００９９】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１００】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１０１】
【発明の効果】
以上のごとく本発明によれば、動きを検出することができる。特に少ない演算量で１画素以下の動きを検出することが可能となる。
【図面の簡単な説明】
【図１】本発明を適応した動き検出装置の構成例を示すブロック図である。
【図２】図１の記憶部の構成例を示すブロック図である。
【図３】図１の動き検出装置の動き検出処理を説明するフローチャートである。
【図４】図３のステップＳ１２のクラスコード生成処理を説明するフローチャートである。
【図５】図１の動きベクトル演算部の機能的構成を示すブロック図である。
【図６】図４の動きベクトル演算部の動きベクトル演算処理を説明するフローチャートである。
【図７】図２のＭＥメモリに記憶されるデータを説明する図である。
【図８】図５の絞り込み処理部の機能的構成を示すブロック図である。
【図９】図８の絞り込み処理部の絞り込み処理を説明するフローチャートである。
【図１０】本発明の動き検出処理を実行するパーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
１  動き検出装置，  １１−１乃至１１−４  フレームメモリ，  １２  クラスコード生成部，  １３  記憶部，  １４  動きベクトル演算部，  ３１  チップセレクタ，  ３２スイッチ，  ３３−０乃至３３−４  ＭＥメモリ，  ３４  スイッチ，  ３４  チップセレクタ
【図１】
2005006254.tif 000003
【図２】
2005006254.tif 000004
【図３】
2005006254.tif 000005
【図４】
2005006254.tif 000006
【図５】
2005006254.tif 000007
【図６】
2005006254.tif 000008
【図７】
2005006254.tif 000009
【図８】
2005006254.tif 000010
【図９】
2005006254.tif 000011
【図１０】
2005006254.tif 000012