(57)【要約】【課題】動きベクトル等を精度良く検出する。【解決手段】例えば、クラスコード用タップに含まれる９画素の画素値Ｐ１乃至Ｐ９が図１７に示すような状態である場合、まず、９ビットのクラスコード１０１０００１１０が生成される。次に、第２のテーブルに基づいて、注目画素の真上の画素が、０と１の２通りに場合分けするビットの画素位置に決定されたとすれば、注目画素の真上の画素の画素値Ｐ２が、０に符号化する場合と１に符号化する場合の２通りの場合分けされて、２種類の９ビットのクラスコード１０１０００１１０，１１１０００１１０が生成される。本発明は、動画像信号を圧縮符号化するエンコーダに適用することができる。【選択図】      図１７
2004164116.tif 000002
【特許請求の範囲】
【請求項１】
特徴量を示すクラスコードを生成し、生成した前記クラスコードに基づき、データを処理するデータ処理装置において、
入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定手段と、
前記設定手段によって設定された前記ブロックに含まれる複数の前記データに基づいて閾値を算出する算出手段と、
前記設定手段によって設定された前記ブロックに含まれる複数の前記データを、それぞれ、前記算出手段によって算出された前記閾値に基づいて０または１に符号化し、前記注目データに対する前記クラスコードを生成する第１の生成手段と、
前記クラスコードのそれぞれに対して、前記クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルを保持する保持手段と、
前記保持手段によって保持された前記対応テーブルに基づき、前記第１の生成手段によって生成された前記クラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定手段と、
前記第１の生成手段によって生成された前記クラスコードを構成する複数のビットのうち、前記決定手段によって前記場合分けビットに決定されたビットを、０と１の２通りに場合分けして、前記注目データに対する複数の前記クラスコードを生成する第２の生成手段と
を含むことを特徴とするデータ処理装置。
【請求項２】
決定手段は、前記保持手段によって保持された前記対応テーブルに基づき、前記第１の生成手段によって生成された前記クラスコードを構成する複数のビットのうち、ビット反転の発生頻度が高い方の所定の数を、前記場合分けビットを決定する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
決定手段は、前記保持手段によって保持された前記対応テーブルに基づき、前記第１の生成手段によって生成された前記クラスコードを構成する複数のビットのうち、ビット反転の発生頻度の高い方のものから順に、前記発生頻度の累計値が所定の値なるまで、前記場合分けビットを決定する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項４】
決定手段は、前記保持手段によって保持された前記対応テーブルに基づき、全ての前記クラスコードを構成する複数のビットのうち、ビット反転の発生頻度が高い方の所定の数を、前記場合分けビットを決定する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項５】
決定手段は、前記保持手段によって保持された前記対応テーブルに基づき、前記第１の生成手段によって生成された前記クラスコードを構成する複数のビットのうち、ビット反転の発生頻度が所定の値以上のものを、前記場合分けビットを決定する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項６】
前記対応テーブルは、サンプルとなる複数のデータを用いた統計結果に従って予め生成されている
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項７】
前記算出手段は、前記設定手段によって設定された前記ブロックに含まれる複数の前記データの最小値に、前記ブロックに含まれる複数の前記データのダイナミックレンジの１／２を加算して、前記閾値を算出する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項８】
前記データは、画像を構成する画素の画素値である
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項９】
特徴量を示すクラスコードを生成し、生成した前記クラスコードに基づき、データを処理するデータ処理装置のデータ処理方法において、
入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定ステップと、
前記設定ステップの処理で設定された前記ブロックに含まれる複数の前記データに基づいて閾値を算出する算出ステップと、
前記設定ステップの処理で設定された前記ブロックに含まれる複数の前記データを、それぞれ、前記算出ステップの処理で算出された前記閾値に基づいて０または１に符号化し、前記注目データに対する前記クラスコードを生成する第１の生成ステップと、
前記クラスコードのそれぞれに対して、前記クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルに基づき、前記第１の生成ステップの処理で生成された前記クラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定ステップと、
前記第１の生成ステップの処理で生成された前記クラスコードを構成する複数のビットのうち、前記決定手段によって前記場合分けビットに決定されたビットを、０と１の２通りに場合分けして、前記注目データに対する複数の前記クラスコードを生成する第２の生成ステップと
を含むことを特徴とするデータ処理方法。
【請求項１０】
特徴量を示すクラスコードを生成し、生成した前記クラスコードに基づき、データを処理するためのプログラムであって、
入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定ステップと、
前記設定ステップの処理で設定された前記ブロックに含まれる複数の前記データに基づいて閾値を算出する算出ステップと、
前記設定ステップの処理で設定された前記ブロックに含まれる複数の前記データを、それぞれ、前記算出ステップの処理で算出された前記閾値に基づいて０または１に符号化し、前記注目データに対する前記クラスコードを生成する第１の生成ステップと、
前記クラスコードのそれぞれに対して、前記クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルに基づき、前記第１の生成ステップの処理で生成された前記クラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定ステップと、
前記第１の生成ステップの処理で生成された前記クラスコードを構成する複数のビットのうち、前記決定手段によって前記場合分けビットに決定されたビットを、０と１の２通りに場合分けして、前記注目データに対する複数の前記クラスコードを生成する第２の生成ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１１】
特徴量を示すクラスコードを生成し、生成した前記クラスコードに基づき、データを処理するコンピュータに、
入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定ステップと、
前記設定ステップの処理で設定された前記ブロックに含まれる複数の前記データに基づいて閾値を算出する算出ステップと、
前記設定ステップの処理で設定された前記ブロックに含まれる複数の前記データを、それぞれ、前記算出ステップの処理で算出された前記閾値に基づいて０または１に符号化し、前記注目データに対する前記クラスコードを生成する第１の生成ステップと、
前記クラスコードのそれぞれに対して、前記クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルに基づき、前記第１の生成ステップの処理で生成された前記クラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定ステップと、
前記第１の生成ステップの処理で生成された前記クラスコードを構成する複数のビットのうち、前記決定手段によって前記場合分けビットに決定されたビットを、０と１の２通りに場合分けして、前記注目データに対する複数の前記クラスコードを生成する第２の生成ステップと
を含む処理を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ処理装置および方法、記録媒体、並びにプログラムに関し、例えば、時間的に連続する画像対の画素同士をマッチングさせ、マッチングの結果に基づいて画素単位の動きベクトルを検出する場合に用いて好適なデータ処理装置および方法、記録媒体、並びにプログラムに関する。
【０００２】
【従来の技術】
例えば、ＭＰＥＧ２（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）方式等の画像信号を圧縮符号化する処理においては、隣接する２フレーム間の相関関係に基づく符号化処理、いわゆる動き補償フレーム間予測が用いられている。動き補償フレーム間予測では、隣接する２フレーム（一方を対象フレーム、他方を参照フレームと記述する）の間における各画素単位または所定サイズの画素ブロック単位の動きベクトルを検出する処理が必要となる。
【０００３】
動きベクトルを検出する方法としては、従来、ブロックマッチングアルゴリズムと称される方法が用いられている（例えば、特許文献１参照）。
【０００４】
図１は、ブロックマッチングアルゴリズムに従って動きベクトルを検出する動きベクトル検出装置の構成例を示している。この動きベクトル検出装置１は、入力される画像信号を１フレーム分だけ保持して後段に出力するフレームメモリ２，３、およびフレームメモリ２，３からそれぞれ１フレームずつ入力される画像信号に基づき、フレームメモリ２から入力される画像信号の画像内の動きベクトルを検出する検出部４から構成される。
【０００５】
フレームメモリ２は、入力された画像信号を１フレームだけ保持し、次のフレームの画像信号が入力されたとき、保持していた画像信号をフレームメモリ３および検出部４に出力する。フレームメモリ３は、フレームメモリ２から入力された画像信号を１フレーム分だけ保持し、次のフレームの画像信号が入力されたとき、保持していた画像信号を検出部４に出力する。
【０００６】
したがって、検出部４には、前後する２フレームの画像信号が入力されることになる。以下、フレームメモリ２から検出部４に入力された１フレームの画像信号の画像を、対象フレームＦｃと記述する。また、フレームメモリ３から検出部４に入力された、対象フレームＦｃよりも１フレームだけ以前の画像信号の画像を、参照フレームＦｒと記述する。
【０００７】
検出部４は、ブロックマッチングアルゴリズムに従い、対象フレームＦｃ内の動きベクトルを算出する。ブロックマッチングアルゴリズムについて、対象フレームＦｃと参照フレームＦｒの対応関係を示す図２および処理に順序を示す図３のフローチャートを参照して説明する。
【０００８】
ブロックマッチングアルゴリズムでは、対象フレームＦｃ内の全ての画素が、順次、注目画素に指定され、注目画素を中心とする所定サイズ（Ｌ×Ｌ画素）の基準ブロックと、参照フレームＦｒに設けられたサーチエリアＳＲ内で移動される参照ブロック（基準ブロックと同じサイズ）との対応する画素対の画素値の差分絶対値和が次式（１）に従って演算される。
ΣｉΣｊ＝｜Ｆｃ（ｉ，ｊ）−Ｆｒｎ（ｉ，ｊ）｜              ・・・（１）
【０００９】
ただし、Ｆｃ（ｉ，ｊ）は基準ブロックの画素の画素値であり、Ｆｒｎ（ｉ，ｊ）は識別番号ｎの参照ブロックの画素の画素値である。また、Σｉはｉを１からＬまで１ずつインクリメントしたときの総和演算を意味し、Σｊはｊを１からＬまで１ずつインクリメントしたときの総和演算を意味するものとする。
【００１０】
そして、基準ブロックと参照ブロックとの対応する画素対の画素値の差分絶対値和が最小となるときの参照ブロックの中心座標と注目画素の座標との差分ベクトルが動きベクトルとして算出される。
【００１１】
具体的には、対象フレームＦｃの注目画素に対して、以下の処理が実行される。ステップＳ１において、検出部４は、参照フレームＦｃに、対象フレームＦｃの注目画素の座標と同じ座標を中心として、基準ブロックよりも大きなサイズのサーチエリアＳＲを設定する。
【００１２】
ステップＳ２において、検出部４は、差分絶対値和の最小値を格納する変数ｍｉｎを、その最大値に初期化する。例えば、１画素の画素値が８ビット、基準ブロックのサイズが４×４画素である場合、変数ｍｉｎが、４０９６（＝２８×１６）に初期化される。
【００１３】
ステップＳ３において、検出部４は、サーチエリアＳＲ内で移動させる参照ブロックの識別番号ｎを１に初期化する。ステップＳ４において、検出部４は、差分絶対値和の演算結果を格納する変数ｓｕｍを０に初期化する。
【００１４】
ステップＳ５において、検出部４は、対象フレームＦｃの基準ブロックと、参照フレームＦｒに設定したサーチエリアＳＲ内の識別番号ｎの参照ブロックとの対応する場所に位置する画素対の画素値の差分絶対値和を演算して、変数ｓｕｍに代入する。ステップＳ６において、検出部４は、ステップＳ５の演算結果である変数ｓｕｍと変数ｍｉｎを比較し、変数ｓｕｍが変数ｍｉｎよりも小さいか否かを判定する。変数ｓｕｍが変数ｍｉｎよりも小さいと判定された場合、処理はステップＳ７に進む。
【００１５】
ステップＳ７において、検出部４は、変数ｍｉｎを、変数ｓｕｍで置換する。また、検出部４は、いまの参照ブロックの識別番号ｎを、動きベクトル番号として記憶する。
【００１６】
ステップＳ８において、検出部４は、参照ブロックの識別番号ｎが最大値であるか否か、すなわち、サーチエリアＳＲの全域に参照ブロックを移動し終えたか否かを判定する。参照ブロックの識別番号ｎが最大値ではないと判定された場合、処理はステップＳ９に進む。ステップＳ９において、検出部４は、参照ブロックの識別番号ｎを１だけインクリメントし、ステップＳ４の処理に戻って、それ以降の処理を繰り返す。
【００１７】
なお、ステップＳ６において、変数ｓｕｍが変数ｍｉｎよりも小さくないと判定された場合、処理はステップＳ７の処理はスキップされる。
【００１８】
その後、ステップＳ８において、参照ブロックの識別番号ｎが最大値ではないと判定された場合、すなわち、サーチエリアＳＲの全域に参照ブロックを移動し終えた場合、処理はステップＳ１０に進む。
【００１９】
ステップＳ１０において、検出部４は、動きベクトル番号として記憶している識別番号ｎに対応する参照ブロックの中心座標と、対象フレームＦｃの注目画素の座標との差分ベクトルを、対象フレームＦｃの注目画素の動きベクトルとして算出する。以上で、ブロックマッチングアルゴリズムの説明を終了する。
【００２０】
【特許文献１】
特許第３２７７４１７号公報
【００２１】
【発明が解決しようとする課題】
上述したブロックマッチングアルゴリズムは、ステップＳ５の処理における画素対の画素値の差分絶対値和の演算量が非常に膨大となっており、画像圧縮処理に要する時間の大半がこの演算に費やされてしまうという課題があった。
【００２２】
本発明はこのような状況に鑑みてなされたものであり、僅かな演算量だけで画像間のマッチングを行うことができ、しかも動きベクトル等を精度良く検出できるようにすることを目的とする。
【００２３】
【課題を解決するための手段】
本発明のデータ処理装置は、入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定手段と、設定手段によって設定されたブロックに含まれる複数のデータに基づいて閾値を算出する算出手段と、設定手段によって設定されたブロックに含まれる複数のデータを、それぞれ、算出手段によって算出された閾値に基づいて０または１に符号化し、注目データに対するクラスコードを生成する第１の生成手段と、クラスコードのそれぞれに対して、クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルを保持する保持手段と、保持手段によって保持された対応テーブルに基づき、第１の生成手段によって生成されたクラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定手段と、第１の生成手段によって生成されたクラスコードを構成する複数のビットのうち、決定手段によって場合分けビットに決定されたビットを、０と１の２通りに場合分けして、注目データに対する複数のクラスコードを生成する第２の生成手段とを含むことを特徴とする。
【００２４】
前記決定手段は、保持手段によって保持された対応テーブルに基づき、第１の生成手段によって生成されたクラスコードを構成する複数のビットのうち、ビット反転の発生頻度が高い方の所定の数を、場合分けビットを決定するようにすることができる。
【００２５】
前記決定手段は、保持手段によって保持された対応テーブルに基づき、第１の生成手段によって生成されたクラスコードを構成する複数のビットのうち、ビット反転の発生頻度の高い方のものから順に、発生頻度の累計値が所定の値なるまで、場合分けビットを決定するようにすることができる。
【００２６】
前記決定手段は、保持手段によって保持された対応テーブルに基づき、全てのクラスコードを構成する複数のビットのうち、ビット反転の発生頻度が高い方の所定の数を、場合分けビットを決定するようにすることができる。
【００２７】
前記決定手段は、保持手段によって保持された対応テーブルに基づき、第１の生成手段によって生成されたクラスコードを構成する複数のビットのうち、ビット反転の発生頻度が所定の値以上のものを、場合分けビットを決定するようにすることができる。
【００２８】
前記対応テーブルは、サンプルとなる複数のデータを用いた統計結果に従って予め生成されているようにすることができる。
【００２９】
前記算出手段は、設定手段によって設定されたブロックに含まれる複数のデータの最小値に、ブロックに含まれる複数のデータのダイナミックレンジの１／２を加算して、閾値を算出するようにすることができる。
【００３０】
前記データは、画像を構成する画素の画素値であるようにすることができる。
【００３１】
本発明のデータ処理方法は、入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定ステップと、設定ステップの処理で設定されたブロックに含まれる複数のデータに基づいて閾値を算出する算出ステップと、設定ステップの処理で設定されたブロックに含まれる複数のデータを、それぞれ、算出ステップの処理で算出された閾値に基づいて０または１に符号化し、注目データに対するクラスコードを生成する第１の生成ステップと、クラスコードのそれぞれに対して、クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルに基づき、第１の生成ステップの処理で生成されたクラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定ステップと、第１の生成ステップの処理で生成されたクラスコードを構成する複数のビットのうち、決定手段によって場合分けビットに決定されたビットを、０と１の２通りに場合分けして、注目データに対する複数のクラスコードを生成する第２の生成ステップとを含むことを特徴とする。
【００３２】
本発明の記録媒体のプログラムは、入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定ステップと、設定ステップの処理で設定されたブロックに含まれる複数のデータに基づいて閾値を算出する算出ステップと、設定ステップの処理で設定されたブロックに含まれる複数のデータを、それぞれ、算出ステップの処理で算出された閾値に基づいて０または１に符号化し、注目データに対するクラスコードを生成する第１の生成ステップと、クラスコードのそれぞれに対して、クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルに基づき、第１の生成ステップの処理で生成されたクラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定ステップと、第１の生成ステップの処理で生成されたクラスコードを構成する複数のビットのうち、決定手段によって場合分けビットに決定されたビットを、０と１の２通りに場合分けして、注目データに対する複数のクラスコードを生成する第２の生成ステップとを含むことを特徴とする。
【００３３】
本発明のプログラムは、入力されたデータに基づいて、注目データを含む所定のサイズのブロックを設定する設定ステップと、設定ステップの処理で設定されたブロックに含まれる複数のデータに基づいて閾値を算出する算出ステップと、設定ステップの処理で設定されたブロックに含まれる複数のデータを、それぞれ、算出ステップの処理で算出された閾値に基づいて０または１に符号化し、注目データに対するクラスコードを生成する第１の生成ステップと、クラスコードのそれぞれに対して、クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルに基づき、第１の生成ステップの処理で生成されたクラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットを決定する決定ステップと、第１の生成ステップの処理で生成されたクラスコードを構成する複数のビットのうち、決定手段によって場合分けビットに決定されたビットを、０と１の２通りに場合分けして、注目データに対する複数のクラスコードを生成する第２の生成ステップとを含む処理をコンピュータに実行させることを特徴とする。
【００３４】
本発明のデータ処理装置および方法、並びにプログラムにおいては、注目データを含む所定のサイズのブロックに含まれる複数のデータが、それぞれ、算出された閾値に基づいて０または１に符号化されて注目データに対するクラスコードが生成され、クラスコードのそれぞれに対して、クラスコードを構成する複数のビットの各位置におけるビット反転の発生頻度が対応付けられた対応テーブルに基づき、生成されたクラスコードを構成する複数のビットのうち、０と１の２通りに場合分けする場合分けビットが決定される。さらに、生成されたクラスコードを構成する複数のビットのうち、場合分けビットに決定されたビットが、０と１の２通りに場合分けされて、注目データに対する複数のクラスコードが生成される。
【００３５】
【発明の実施の形態】
本発明を適用した動きベクトル検出装置の構成例について、図４を参照して説明する。この動きベクトル検出装置１１は、フレームメモリ１２，１３、クラスコード生成部１４、テーブルメモリ１５、ＭＥメモリ１６、および動きベクトル演算部１７から構成される。
【００３６】
フレームメモリ１２は、入力された画像信号を１フレームだけ保持し、次のフレームの画像信号が入力されたとき、保持していた画像信号をフレームメモリ１３およびクラスコード生成部１４に出力する。フレームメモリ１３は、入力された画像信号を１フレームだけ保持し、次のフレームの画像信号がフレームメモリ１２から入力されたとき、保持していた画像信号をクラスコード生成部１４に出力する。
【００３７】
したがって、クラスコード生成部１４には、時間的に前後する２フレームの画像信号が入力されることになる。以下、フレームメモリ１２からクラスコード生成部１４に入力される１フレームの画像信号の画像を、対象フレームＦｃと記述する。また、フレームメモリ１３から検出部４に入力される、対象フレームＦｃよりも１フレームだけ以前の画像信号の画像を、参照フレームＦｒと記述する。
【００３８】
クラスコード生成部１４は、対象フレームＦｃの全ての画素に対し、それぞれ、近傍の画素の画素値を用いた空間的な特徴を示すクラスコードを１種類だけ生成して、動きベクトル演算部１７に出力する。具体的には、対象フレームＦｃの全ての画素を、順次、注目画素に設定し、注目画素を中心とする所定サイズのクラスコード用タップ（例えば、図５に示すような３×３画素）を決定して、クラスコード用タップに含まれる複数の画素（図５の場合、９画素）の画素値を、１ビットＡＤＲＣ（Ａｄａｐｔｉｖｅ  Ｄｙｎａｍｉｃ  Ｒａｎｇｅ  Ｃｏｄｉｎｇ）によってそれぞれ０また１に符号化して、所定のビット数（図５の場合、９ビット）のクラスコードを生成する。
【００３９】
また、クラスコード生成部１４は、参照フレームＦｒの全ての画素に対し、それぞれ、近傍の画素の画素値を用いた空間的な特徴を示すクラスコードを１種類だけ生成する。ただし、参照フレームＦｒは、１回前のタイミングにおいて対象フレームＦｃであったものであるので、参照フレームＦｒの各画素に対する１種類のクラスコードは、既に１回前のタイミングにおいて生成されている。よって、１回前のタイミングにおいて対象フレームＦｃの各画素に対して生成されたクラスコードを保持するようにして、今回のタイミングにおける参照フレームＦｒの各画素に対するクラスコードとして流用するようにしてもよい。
【００４０】
さらに、クラスコード生成部１４は、テーブルメモリ１５に予め保持されている、第１または第２のテーブルに基づいて、生成した１種類のクラスコードを構成する複数のビットのうち、所定のビットをそれぞれ０にした場合と１にした場合の２通りを場合分けして、１種類以上のクラスコードを生成し、ＭＥメモリ１６に出力する。なお、参照フレームＦｒの画素に対してクラスコードを生成する処理については後述する。
【００４１】
テーブルメモリ１５には、クラスコードと、０と１の２通りに場合分けして符号化させるビット数との対応を示す第１のテーブルと、クラスコードとクラスコード用タップにおける各画素位置のビット反転の発生の頻度を示す第２のテーブルが記憶されている。なお、第１および第２のテーブルは、サンプルとなる複数の画像信号を用いて予め統計的に生成されて、テーブルメモリ１５に予め記憶されているものとする。
【００４２】
第１のテーブルを生成する処理について、図６乃至図８を参照して説明する。まず、サンプルとなる複数の画像信号の各画素に対して、クラスコード用タップが設定されて、ＡＤＲＣによりクラスコードが生成される。次に、生成された全てのクラスコードがそれぞれ元となったクラスコード用タップ内の複数の画素値と比較されて、クラスコードの中でビット反転が生じているビットが判定され、そのビット数が計数される。そして、その計数結果に基づき、図６に示すような、横軸にビット数、縦軸に正規化されたビット反転の発生頻度を示すヒストグラムが生成される。
【００４３】
なお、図６には、４種類のクラスコードに対する計数結果を示す折れ線ａ乃至ｄが示されているが、実際には、例えば、クラスコードが９ビットである場合、５１２（＝２９）種類のクラスコードに対する計数結果をそれぞれ示す５１２本の折れ線が得られることになる。さらに、各クラスコードについて、ビット反転の発生頻度の累計が所定の値となるようにビット数Ｋが決定されて、第１のテーブルに書き込まれる。なお、当該所定の値は、全てのクラスコードに対して共通の値が用いられる。
【００４４】
例えば、当該所定の値が４０％と定められた場合、折れ線ｄに対応するクラスコードに対しては、図７に示すように、ビット数Ｋ＝１が決定される。また、例えば、当該所定の値が８０％と定められた場合、折れ線ｄに対応するクラスコードに対しては、図８に示すように、ビット数Ｋ＝３が決定される。
【００４５】
図９は、図５のクラスコード用タップが用いられて生成された９ビットのクラスコードに対応する第１のテーブルの一例を示している。この例では、クラスコード１０００１１１１１とビット数Ｋ＝３が対応付けられていることを示している。また、クラスコード１０１００１１１１とビット数Ｋ＝２が対応付けられていることを示している。
【００４６】
次に、第２のテーブルを生成する処理について、図１０を参照して説明する。まず、複数のサンプルの画像信号の各画素に対して、クラスコード用タップが設定されて、ＡＤＲＣによりクラスコードが生成される。次に、生成された全てのクラスコードがそれぞれ元となったクラスコード用タップ内の複数の画素値と比較されて、クラスコードの中でビット反転が生じているビットが判定され、ビット反転が生じているビットに対する画素のクラスコード用タップにおける位置が判定される。そして、その判定結果に基づき、図１０に示すような、横軸にクラスコード用タップにおける画素の位置、縦軸に正規化されたビット反転の頻度を示すヒストグラムが生成されて、第２のテーブルが生成される。
【００４７】
なお、図１０には、３種類のクラスコードに対する判定結果が折れ線ｅ乃至ｇを用いて示されているが、実際には、例えば、クラスコードが９ビットである場合、５１２（＝２９）種類のクラスコードに対する判定結果をそれぞれ示す５１２本の折れ線が得られることになる。
【００４８】
図１１は、図５のクラスコード用タップが用いられて生成された９ビットのクラスコードに対応する第２のテーブルの一例を示している。第２のテーブルには、９ビットの各クラスコードにそれぞれ対応して、９カ所の画素位置のビット反転の発生頻度が格納されることになる。
【００４９】
例えば、クラスコード０００００００００については、注目画素の左上の画素値Ｐ１を符号化した際のビット反転の発生頻度が０であり、注目画素の真上の画素値Ｐ２を符号化した際のビット反転の発生頻度が０．０５であり、注目画素の右上の画素値Ｐ３、真左の画素値Ｐ４、および注目画素の画素値Ｐ５を符号化した際のビット反転の発生頻度が０であり、注目画素の真右の画素値Ｐ６を符号化した際のビット反転の発生頻度が０．０６であり、注目画素の左下の画素値Ｐ７、真下の画素値Ｐ８、および右下の画素値Ｐ９を符号化した際のビット反転の発生頻度が０であることを示している。
【００５０】
また、例えば、クラスコード１０１０００１１０については、注目画素の左上の画素値Ｐ１を符号化した際のビット反転の発生頻度が０．０９であり、注目画素の真上の画素値Ｐ２を符号化した際のビット反転の発生頻度が０．５５であり、注目画素の右上の画素値Ｐ３を符号化した際のビット反転の発生頻度が０．０４であり、注目画素の真左の画素値Ｐ４を符号化した際のビット反転の発生頻度が０．３であり、注目画素の画素値Ｐ５を符号化した際のビット反転の発生頻度が０．１であり、注目画素の真右の画素値Ｐ６を符号化した際のビット反転の発生頻度が０．０９であり、注目画素の左下の画素値Ｐ７を符号化した際のビット反転の発生頻度が０．１５であり、注目画素の真下の画素値Ｐ８および右下の画素値Ｐ９を符号化した際のビット反転の発生頻度が０．０８であることを示している。
【００５１】
図４に戻る。ＭＥメモリ１６は、クラスコード生成部１４から入力される参照フレームＦｒの各画素に対する１種類以上のクラスコードを、クラスコードに各画素の座標を対応付けて記憶する。
【００５２】
図１２は、ＭＥメモリ１６の構造を示している。ＭＥメモリ１６は、特徴量アドレス０乃至ａと、フラグアドレス０乃至ｂによって示される（ａ＋１）×（ｂ＋１）個のセルにより構成される。以下、例えば、特徴量アドレス１、フラグアドレス２のセルをセル（１，２）と記述する。
【００５３】
特徴量アドレスは、クラスコード生成部１４によって生成される参照フレームＦｒの各画素に対して生成されたクラスコードに対応する。例えば、クラスコードが９ビットである場合、特徴量アドレスの最大値ａ＝２９となる。
【００５４】
特徴量アドレス０のフラグアドレス１以降のセルには、クラスコード生成部１４によってクラスコード０が生成された参照フレームＦｒの画素の座標がラスタ順に格納される。特徴量アドレス０のフラグアドレス０のセル（０，０）には、クラスコード０の画素の座標が既に格納されている、特徴量アドレス０のフラグアドレス１以降のセル、すなわち、使用済のセルの数が格納される。例えば、参照フレームＦｒの画素のうち、３画素に対してそれぞれクラスコード０が生成された場合、セル（０，１）、セル（０，２）、セル（０，３）に３画素それぞれの座標が格納され、セル（０，０）に座標が格納されているセルの数である３が格納される。
【００５５】
特徴量アドレス１のフラグアドレス１以降のセルには、クラスコード生成部１４によってクラスコード１が生成された参照フレームＦｒの画素の座標がラスタ順に格納される。特徴量アドレス１のフラグアドレス０のセル（１，０）には、クラスコード１の画素の座標が格納されている、特徴量アドレス０のフラグアドレス１以降のセルの数が格納される。例えば、参照フレームＦｒの画素のうち、１０画素に対して同一のクラスコード１が生成された場合、セル（１，１）、…、セル（１，１０）に１０画素それぞれの座標が格納され、セル（１，０）に、座標が格納されているセルの数である１０が格納される。特徴量アドレス２以降のセルについても同様であるので、その説明は省略する。
【００５６】
また、例えば、参照フレームＦｒのある画素に対して３種類のクラスコードが生成された場合、当該画素の座標が、３種類のクラスコードに対応する特徴量アドレスの３つのセルに格納されることになる。
【００５７】
図４に戻る。動きベクトル演算部１７は、対象フレームＦｃの各画素について、同じクラスコードが生成された参照フレームＦｒの画素の座標を、ＭＥメモリ１６から検索し、検索された画素のうち、注目画素の座標に最も距離が近い座標の画素を、対象フレームＦｃの注目画素に対応する参照フレームＦｒの画素に決定して、注目画素の動きベクトルを算出する。
【００５８】
なお、ＭＥメモリ１６の構造、および動きベクトル演算部１７による処理の詳細については、本出願人が特願２００２−２２２０４４号として既に提案済である。
【００５９】
次に、クラスコード生成部１４による第１のテーブルを用いたクラスコード生成処理について、図１３のフローチャートを参照して説明する。この処理は、参照フレームＦｒの各画素が、順次、注目画素に指定され、注目画素に対して実行されるものである。
【００６０】
ステップＳ１１において、クラスコード生成部１４は、注目画素を中心とする所定サイズのクラスコード用タップを設定し、クラスコード用タップに含まれる複数の画素の画素値を取得する。以下においては、図５に示されたように、クラスコード用タップのサイズを３×３画素とし、注目画素の左上、真上、右上、真左、注目画素自身、真右、左下、真下、右下の画素の画素値を、それぞれＰ１乃至Ｐ９として説明を継続する。
【００６１】
ステップＳ１２において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９の最大値ＰＭＡＸと最小値ＰＭＩＮを判定する。ステップＳ１３において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９のダイナミックレンジＤＲ（＝｜最大値ＰＭＡＸ−最小値ＰＭＩＮ｜）を算出する。ステップＳ１４において、クラスコード生成部１４は、次式（２）のように、画素値Ｐ１乃至Ｐ９の最小値ＰＭＩＮに、ダイナミックレンジＤＲ／２を加算して閾値Ｔｈを算出する。
Ｔｈ＝ＰＭＩＮ＋ＤＲ／２                                    ・・・（２）
【００６２】
ステップＳ１５において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９を、それぞれ閾値Ｔｈと比較し、閾値Ｔｈよりも大きい場合には１に符号化し、閾値Ｔｈよりも小さい場合には０に符号化して画素の配置の順に並べ、９ビットのクラスコードを生成する。
【００６３】
なお、ステップＳ１１乃至Ｓ１５の処理は、対象フレームＦｃの各画素に対してクラスコードを生成する処理として、現在の参照フレームＦｒが１回前のタイミングにおいて対象フレームＦｃであったときに実行されているので、その結果を流用してもよい。
【００６４】
ステップＳ１６において、クラスコード生成部１４は、テーブルメモリ１５に記憶されている第１のテーブルを参照して、ステップＳ１５の処理で生成したクラスコードに対応するビット数Ｋを取得する。なお、ここで取得したビット数Ｋ＝０である場合、以下に述べるステップＳ１７の処理は省略される。
【００６５】
ステップＳ１７において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９のうち、閾値Ｔｈに最も近いＫ個の画素値については、それぞれ０に符号化する場合と１に符号化する場合の２通りに場合分けして、その他の画素値については、ステップＳ１５の処理と同様に、閾値Ｔｈとの比較により、０または１に符号化して、注目画素に対する２Ｋ種類のクラスコードを生成する。なお、当該その他の画素値の符号化については、ステップ１５の結果を流用するようにしてもよい。
【００６６】
例えば、クラスコード用タップに含まれる９画素の画素値Ｐ１乃至Ｐ９が図１４に示すような状態である場合、ステップＳ１５の処理により９ビットのクラスコード１０００１１１１１が生成される。そして、ステップＳ１６の処理により、第１のテーブルから、９ビットのクラスコード１０００１１１１１に対応するビット数Ｋ＝３が取得される。さらに、ステップＳ１７において、閾値Ｔｈに最も近い３個の画素値Ｐ３，Ｐ６，Ｐ８について、それぞれ０に符号化する場合と１に符号化する場合の２通りに場合分けされ、８（＝２３）種類の９ビットのクラスコード１０００１０１０１，１０００１０１１１，１０００１１１０１，１０００１１１１１，１０１０１０１０１，１０１０１０１１１，１０１０１１１０１，１０１０１１１１１が生成される。
【００６７】
また例えば、クラスコード用タップに含まれる９画素の画素値Ｐ１乃至Ｐ９が図１５に示すような状態である場合、ステップＳ１５の処理により９ビットのクラスコード１０１００１１１１が生成される。そして、ステップＳ１６の処理により、第１のテーブルから、９ビットのクラスコード１０１００１１１１に対応するビット数Ｋ＝２が取得される。さらに、ステップＳ１７において、閾値Ｔｈに最も近い２個の画素値Ｐ６，Ｐ８について、それぞれ０に符号化する場合と１に符号化する場合の２通りに場合分けされ、４（＝２２）種類の９ビットのクラスコード１０１０００１０１，１０１０００１１１，１０１００１１０１，１０１００１１１１が生成される。
【００６８】
以上で、クラスコード生成部１４による第１のテーブルを用いたクラスコード生成処理の説明を終了する。
【００６９】
次に、クラスコード生成部１４による第２のテーブルを用いたクラスコード生成処理について、図１６を参照して説明する。この処理は、参照フレームＦｒの各画素が、順次、注目画素に指定され、注目画素に対して実行されるものである。
【００７０】
ステップＳ２１において、クラスコード生成部１４は、注目画素を中心とする所定サイズのクラスコード用タップを設定し、クラスコード用タップに含まれる複数の画素の画素値を取得する。以下においては、図５に示されたように、クラスコード用タップのサイズを３×３画素とし、注目画素の左上、真上、右上、真左、注目画素自身、真右、左下、真下、右下の画素の画素値を、それぞれＰ１乃至Ｐ９として説明を継続する。
【００７１】
ステップＳ２２において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９の最大値ＰＭＡＸと最小値ＰＭＩＮを判定する。ステップＳ２３において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９のダイナミックレンジＤＲ（＝｜最大値ＰＭＡＸ−最小値ＰＭＩＮ｜）を算出する。ステップＳ２４において、クラスコード生成部１４は、式（２）のように、画素値Ｐ１乃至Ｐ９の最小値ＰＭＩＮに、ダイナミックレンジＤＲ／２を加算して閾値Ｔｈを算出する。
【００７２】
ステップＳ２５において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９を、それぞれ閾値Ｔｈと比較し、閾値Ｔｈよりも大きい場合には１に符号化し、閾値Ｔｈよりも小さい場合には０に符号化して画素の配置の順に並べ、９ビットのクラスコードを生成する。
【００７３】
なお、ステップＳ２１乃至Ｓ２５の処理は、対象フレームＦｃの各画素に対してクラスコードを生成する処理として、現在の参照フレームＦｒが１回前のタイミングにおいて対象フレームＦｃであったときに実行されているので、その結果を流用してもよい。
【００７４】
ステップＳ２６において、クラスコード生成部１４は、テーブルメモリ１５に記憶されている第２のテーブルを参照して、ステップＳ２５の処理で生成したクラスコードのうち、０と１の２通りに場合分けするビットの画素位置を、以下の４種類の方法のうち、予め定められている方法を用いて決定する。
【００７５】
第１の方法は、各クラスコードについて、ビット反転の発生頻度が高い方の上位の所定の数カ所（例えば、２カ所）の画素位置を、０と１の２通りに場合分けするビットの画素位置に決定する方法である。
【００７６】
第２の方法は、各クラスコードについて、ビット反転の発生頻度の累計が所定の値になるまで、発生頻度が高い方から順に数カ所の画素位置を、０と１の２通りに場合分けするビットの画素位置に決定する方法である。
【００７７】
第３の方法は、第２のテーブルの全てのクラスコードにそれぞれ対応する合計２９×９カ所の発生頻度のうち、ビット反転の発生頻度が高い方の上位の所定の数カ所（例えば、１００カ所）の画素位置を、０と１の２通りに場合分けするビットの画素位置に決定する方法である。
【００７８】
第４の方法は、各クラスコードについて、ビット反転の発生頻度が所定の値（例えば、０．４）以上である画素位置を、０と１の２通りに場合分けするビットの画素位置に決定する方法である。
【００７９】
ステップＳ２６において、ステップＳ２５の処理で生成したクラスコードのうち、０と１の２通りに場合分けするビットの画素位置が決定された後、処理はステップＳ２７に進む。なお、ステップＳ２６において、ステップＳ２５の処理で生成したクラスコードのうち、いずれのビットも０と１の２通りに場合分けするビットに決定されなかった場合、以下に述べるステップＳ２７の処理は省略される。
【００８０】
ステップＳ２７において、クラスコード生成部１４は、画素値Ｐ１乃至Ｐ９のうち、ステップＳ２６の処理で０と１の２通りに場合分けするビットの画素位置に決定された画素位置の画素値については、それぞれ０に符号化する場合と１に符号化する場合の２通りを設定し、その他の画素値については、ステップＳ２５の処理と同様に、閾値Ｔｈとの比較により、０または１に符号化して、注目画素に対する１種類以上のクラスコードを生成する。なお、当該その他の画素値の符号化については、ステップ２５の結果を流用するようにしてもよい。
【００８１】
例えば、クラスコード用タップに含まれる９画素の画素値Ｐ１乃至Ｐ９が図１７に示すような状態である場合、ステップＳ２５の処理により９ビットのクラスコード１０１０００１１０が生成される。そして、ステップＳ２６の処理により、第２のテーブルに基づいて、注目画素の真上の画素が、０と１の２通りに場合分けするビットの画素位置に決定されたとすれば、ステップＳ２７において、注目画素の真上の画素の画素値Ｐ２が、０に符号化する場合と１に符号化する場合の２通りの場合分けされて、２種類の９ビットのクラスコード１０１０００１１０，１１１０００１１０が生成される。
【００８２】
以上で、クラスコード生成部１４による第１のテーブルを用いたクラスコード生成処理の説明を終了する。
【００８３】
このように、クラスコード用タップに含まれる全画素をＡＤＲＣによって符号化し、クラスコードを生成した際、ビット反転が生じ易いと統計的に判断できるビットについては、０に符号化した場合と１に符号化した場合の２通りに場合分けして、参照フレームＦｒの各画素に対して１種類以上のクラスコードを生成するようにしたので、クラスコードのロバスト性を向上させることができる。
【００８４】
なお、クラスコード用タップを構成する画素の数、すなわち、クラスコードのビット数は、上述した例に限るものではなく任意である。
【００８５】
以上説明したように、本実施の形態によれば、クラスコード生成部１４は、参照フレームＦｒの各画素に対し、１ビットＡＤＲＣという容易な演算により、高いロバスト性を有するクラスコードを生成することができる。よって、対象フレームＦｃの画素と参照フレームＦｒの画素とを、高い精度でマッチングさせることができる。したがって、動きベクトルを精度良く検出することが可能となる。
【００８６】
また、本発明は、画像を構成する画素の画素値の他、例えば、音声データなどの任意のデータに対してクラスコードを生成する場合に適用することが可能である。
【００８７】
ところで、上述した一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば、図１８に示すように構成される汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【００８８】
このパーソナルコンピュータは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３１を内蔵している。ＣＰＵ３１にはバス３４を介して、入出力インタフェース３５が接続されている。バス３４には、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３２およびＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３３が接続されている。
【００８９】
入出力インタフェース３５には、ユーザが操作コマンドを入力するキーボード、マウスなどの入力デバイスよりなる入力部３６、操作画面や処理結果を示す画面などを表示するＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）またはＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等よりなる出力部３７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部３８、およびモデム、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）アダプタなどよりなりインタネットに代表されるネットワークを介した通信処理を実行する通信部３９が接続されている。また、磁気ディスク４１、光ディスク４２、光磁気ディスク４３、および半導体メモリ４４などの記録媒体に対してデータを読み書きするドライブ４０が接続されている。
【００９０】
ＣＰＵ３１に上述した一連の処理を実行させるプログラムは、磁気ディスク４１（フレキシブルディスクを含む）、光ディスク４２（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−ＲｅａｄＯｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）を含む）、光磁気ディスク４３（ＭＤ（Ｍｉｎｉ  Ｄｉｓｃ）を含む）、もしくは半導体メモリ４４に格納された状態でパーソナルコンピュータに供給され、ドライブ４０によって読み出されて記憶部３８に内蔵されるハードディスクドライブにインストールされている。記憶部３８にインストールされているプログラムは、入力部３６に入力されるユーザからのコマンドに対応するＣＰＵ３１の指令によって、記憶部３８からＲＡＭ３３にロードされて実行される。
【００９１】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に従って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【００９２】
【発明の効果】
以上のように、本発明によれば、僅かな演算量のみで画像間のマッチングを行うことができる。また、本発明によれば、動きベクトル等を精度良く検出することが可能となる。
【図面の簡単な説明】
【図１】従来の動きベクトル検出装置の構成例を示すブロック図である。
【図２】対象フレームＦｃと参照フレームＦｒの対応関係を示す図である。
【図３】ブロックマッチングアルゴリズムを説明するフローチャートである。
【図４】本発明の一実施の形態である動きベクトル検出装置の構成例を示すブロック図である。
【図５】３×３画素のクラスコード用タップを示す図である。
【図６】第１のテーブルを生成する処理を説明するための図である。
【図７】第１のテーブルを生成する処理を説明するための図である。
【図８】第１のテーブルを生成する処理を説明するための図である。
【図９】第１のテーブルの一例を示す図である。
【図１０】第２のテーブルを生成する処理を説明するための図である。
【図１１】第２のテーブルの一例を示す図である。
【図１２】図４のＭＥメモリの構造を示す図である。
【図１３】図４のクラスコード生成部による第１のテーブルを利用したクラスコード生成処理を説明するフローチャートである。
【図１４】第１のテーブルを利用したクラスコード生成処理の一例を示す図である。
【図１５】第１のテーブルを利用したクラスコード生成処理の一例を示す図である。
【図１６】図４のクラスコード生成部による第２のテーブルを利用したクラスコード生成処理を説明するフローチャートである。
【図１７】第２のテーブルを利用したクラスコード生成処理の一例を示す図である。
【図１８】汎用のパーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
１１  動きベクトル検出装置，  １２，１３  フレームメモリ，  １４  クラスコード生成部，  １５  テーブルメモリ，  １６  ＭＥメモリ，  １７  動きベクトル演算部，  ３１  ＣＰＵ，  ４１  磁気ディスク，  ４２  光ディスク，４３  光磁気ディスク，  ４４  半導体メモリ
【図１】
2004164116.tif 000003
【図２】
2004164116.tif 000004
【図３】
2004164116.tif 000005
【図４】
2004164116.tif 000006
【図５】
2004164116.tif 000007
【図６】
2004164116.tif 000008
【図７】
2004164116.tif 000009
【図８】
2004164116.tif 000010
【図９】
2004164116.tif 000011
【図１０】
2004164116.tif 000012
【図１１】
2004164116.tif 000013
【図１２】
2004164116.tif 000014
【図１３】
2004164116.tif 000015
【図１４】
2004164116.tif 000016
【図１５】
2004164116.tif 000017
【図１６】
2004164116.tif 000018
【図１７】
2004164116.tif 000019
【図１８】
2004164116.tif 000020