(57)【特許請求の範囲】
【請求項１】
第１の画像データを複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割するステップと、
第２の画像データを複数の検査ブロックへ分割し、上記検査ブロックをさらに複数の検査サブブロックへ分割するステップと、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出するステップと、
上記検査サブブロックについて、上記代表画素データとの比較に使用する画素データを選択するステップと、
上記検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す特徴量データを抽出するステップと、
上記代表画素データの値が上記特徴量データの示す上記範囲内に存在する場合に０となり、上記代表画素データの値が上記範囲内に存在しない場合に上記代表画素データの値と上記最大値または上記最小値との差分となる評価値を複数の上記検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成するステップと、
上記ブロック単位の評価値の大小に基づいて上記第１および上記第２の画像データの部分的照合を行うステップとからなり、
上記代表画素データとの比較に使用する画素データを選択するステップは、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記検査ブロック内の複数の上記検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合方法。
【請求項２】
第１の画像データを複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割する手段と、
第２の画像データを複数の検査ブロックへ分割し、上記検査ブロックをさらに複数の検査サブブロックへ分割する手段と、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出する手段と、
上記検査サブブロックについて、上記代表画素データとの比較に使用する画素データを選択する手段と、
上記検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す特徴量データを抽出する手段と、
上記代表画素データの値が上記特徴量データの示す上記範囲内に存在する場合に０となり、上記代表画素データの値が上記範囲内に存在しない場合に上記代表画素データの値と上記最大値または上記最小値との差分となる評価値を複数の上記検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成する手段と、
上記ブロック単位の評価値の大小に基づいて上記第１および上記第２の画像データの部分的照合を行う手段とからなり、
上記代表画素データとの比較に使用する画素データを選択する手段は、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記検査ブロック内の複数の上記検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合装置。
【請求項３】
第１の画像データをそれぞれが検査ブロックと同一の大きさの複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割するステップと、
第２の画像データを複数の上記基準ブロックと同一の大きさの検査ブロックへ分割すると共に、上記検査ブロックをさらに複数の検査サブブロックに分割し、上記検査サブブロックを各々所定画素数拡大した複数の修正検査サブブロックを構成するステップと、
上記基準サブブロック内の全画素の値の最小値から最大値までの範囲を示す第１の特徴量データを抽出するステップと、
上記基準サブブロックと対応する上記修正検査サブブロックについて、上記第１の特徴量データとの比較に使用する画素データを選択するステップと、
上記修正検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す第２の特徴量データを抽出するステップと、
上記第１の特徴量データの上記最小値および上記最大値のそれぞれが上記第２の特徴量データの上記最小値および最大値の範囲内に存在する場合に０となり、上記最小値および上記最大値のそれぞれが上記範囲内に存在しない場合に、上記最小値および上記最大値のそれぞれと、上記第２の特徴量データの上記最小値および上記最大値のそれぞれとの差分の加算値となる評価値を複数の上記修正検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成するステップと、
上記ブロック単位の評価値の大小に基づいて上記第１および第２の画像データの部分的照合を行うステップとからなり、
上記第１の特徴量データとの比較に使用する画素データを選択するステップは、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出し、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記複数の修正検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の修正検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合方法。
【請求項４】
第１の画像データをそれぞれが検査ブロックと同一の大きさの複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割する手段と、
第２の画像データを複数の上記基準ブロックと同一の大きさの検査ブロックへ分割すると共に、上記検査ブロックをさらに複数の検査サブブロックに分割し、上記検査サブブロックを各々所定画素数拡大した複数の修正検査サブブロックを構成する手段と、
上記基準サブブロック内の全画素の値の最小値から最大値までの範囲を示す第１の特徴量データを抽出する手段と、
上記基準サブブロックと対応する上記修正検査サブブロックについて、上記第１の特徴量データとの比較に使用する画素データを選択する手段と、
上記修正検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す第２の特徴量データを抽出する手段と、
上記第１の特徴量データの上記最小値および上記最大値のそれぞれが上記第２の特徴量データの上記最小値および最大値の範囲内に存在する場合に０となり、上記最小値および上記最大値のそれぞれが上記範囲内に存在しない場合に、上記最小値および上記最大値のそれぞれと、上記第２の特徴量データの上記最小値および上記最大値のそれぞれとの差分の加算値となる評価値を複数の上記修正検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成する手段と、
上記ブロック単位の評価値の大小に基づいて上記第１および第２の画像データの部分的照合を行う手段とからなり、
上記第１の特徴量データとの比較に使用する画素データを選択する手段は、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出し、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記複数の修正検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の修正検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合装置。
【請求項５】
第１の画像データを複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割するステップと、
上記第１の画像と時間的に異なる第２の画像データを複数の検査ブロックへ分割し、上記検査ブロックをさらに複数の検査サブブロックへ分割するステップと、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出するステップと、
上記検査サブブロックについて、上記代表画素データとの比較に使用する画素データを選択するステップと、
上記検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す特徴量データを抽出するステップと、
上記代表画素データの値が上記特徴量データの示す上記範囲内に存在する場合に０となり、上記代表画素データの値が上記範囲内に存在しない場合に上記代表画素データの値と上記最大値または上記最小値との差分となる評価値を複数の上記検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成するステップと、
所定の探索範囲内で上記検査ブロックを移動することで生成された上記ブロック単位の評価値の大小に基づいて、上記基準ブロックと最も合致する上記検査ブロックの位置と対応する動きベクトルを検出するステップとからなり、
上記代表画素データとの比較に使用する画素データを選択するステップは、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記検査ブロック内の複数の上記検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする動きベクトル検出方法。
【請求項６】
第１の画像データを複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割する手段と、
第２の画像データを複数の検査ブロックへ分割し、上記検査ブロックをさらに複数の検査サブブロックへ分割する手段と、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出する手段と、
上記検査サブブロックについて、上記代表画素データとの比較に使用する画素データを選択する手段と、
上記検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す特徴量データを抽出する手段と、
上記代表画素データの値が上記特徴量データの示す上記範囲内に存在する場合に０となり、上記代表画素データの値が上記範囲内に存在しない場合に上記代表画素データの値と上記最大値または上記最小値との差分となる評価値を複数の上記検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成する手段と、
所定の探索範囲内で上記検査ブロックを移動することで生成された上記ブロック単位の評価値の大小に基づいて、上記基準ブロックと最も合致する上記検査ブロックの位置と対応する動きベクトルを検出する手段とからなり、
上記代表画素データとの比較に使用する画素データを選択する手段は、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記検査ブロック内の複数の上記検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする動きベクトル検出装置。
【請求項７】
第１の画像データをそれぞれが検査ブロックと同一の大きさの複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割するステップと、
第２の画像データを複数の上記基準ブロックと同一の大きさの検査ブロックへ分割すると共に、上記検査ブロックをさらに複数の検査サブブロックに分割し、上記検査サブブロックを各々所定画素数拡大した複数の修正検査サブブロックを構成するステップと、
上記基準サブブロック内の全画素の値の最小値から最大値までの範囲を示す第１の特徴量データを抽出するステップと、
上記基準サブブロックと対応する上記修正検査サブブロックについて、上記第１の特徴量データとの比較に使用する画素データを選択するステップと、
上記修正検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す第２の特徴量データを抽出するステップと、
上記第１の特徴量データの上記最小値および上記最大値のそれぞれが上記第２の特徴量データの上記最小値および最大値の範囲内に存在する場合に０となり、上記最小値および上記最大値のそれぞれが上記範囲内に存在しない場合に、上記最小値および上記最大値のそれぞれと、上記第２の特徴量データの上記最小値および上記最大値のそれぞれとの差分の加算値となる評価値を複数の上記修正検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成するステップと、
所定の探索範囲内で上記検査ブロックを移動することで生成された上記ブロック単位の評価値の大小に基づいて、上記基準ブロックと最も合致する上記検査ブロックの位置と対応する動きベクトルを検出するステップとからなり、
上記第１の特徴量データとの比較に使用する画素データを選択するステップは、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出し、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記複数の修正検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の修正検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする動きベクトル検出方法。
【請求項８】
第１の画像データをそれぞれが検査ブロックと同一の大きさの複数の基準ブロックへ分割し、上記基準ブロックをさらに複数の基準サブブロックへ分割する手段と、
第２の画像データを複数の上記基準ブロックと同一の大きさの検査ブロックへ分割すると共に、上記検査ブロックをさらに複数の検査サブブロックに分割し、上記検査サブブロックを各々所定画素数拡大した複数の修正検査サブブロックを構成する手段と、
上記基準サブブロック内の全画素の値の最小値から最大値までの範囲を示す第１の特徴量データを抽出する手段と、
上記基準サブブロックと対応する上記修正検査サブブロックについて、上記第１の特徴量データとの比較に使用する画素データを選択する手段と、
上記修正検査サブブロック内の上記選択された画素データの値の最小値から最大値までの範囲を示す第２の特徴量データを抽出する手段と、
上記第１の特徴量データの上記最小値および上記最大値のそれぞれが上記第２の特徴量データの上記最小値および最大値の範囲内に存在する場合に０となり、上記最小値および上記最大値のそれぞれが上記範囲内に存在しない場合に、上記最小値および上記最大値のそれぞれと、上記第２の特徴量データの上記最小値および上記最大値のそれぞれとの差分の加算値となる評価値を複数の上記修正検査サブブロックについてそれぞれ求め、求められた上記評価値を積算してブロック単位の評価値を生成する手段と、
所定の探索範囲内で上記検査ブロックを移動することで生成された上記ブロック単位の評価値の大小に基づいて、上記基準ブロックと最も合致する上記検査ブロックの位置と対応する動きベクトルを検出する手段とからなり、
上記第１の特徴量データとの比較に使用する画素データを選択する手段は、
上記基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出し、
上記基準ブロックの複数の上記代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
上記複数の修正検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、上記第１の指示データと同一種類の値を示す第２の指示データを形成し、
上記第１および第２の指示データの差がしきい値以下の場合に、上記複数の修正検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする動きベクトル検出装置。
【請求項９】
請求項２または６に記載の装置において、
上記代表画素データがブロック内の中央位置の画素のデータであることを特徴とする装置。
【請求項１０】
請求項２または６に記載の装置において、
上記第特徴量データが示す範囲の上記最小値および上記最大値がブロック内の複数画素の最大値、最小値およびダイナミックレンジの内の二つのデータで表されたものであることを特徴とする装置。
【請求項１１】
請求項２または６に記載の装置において、
上記特徴量データが示す範囲の上記最小値および上記最大値がブロック内の画素のダイナミックレンジおよび最大値若しくは最小値のうちの一方で表されたものである場合に、演算によって上記最大値および最小値を求めることを特徴とする装置。
【請求項１２】
請求項２または６に記載の装置において、
上記特徴量データが示す範囲の上記最小値および上記最大値がブロック内の複数画素の平均値と標準偏差の和データおよび上記平均値と標準偏差の差データで表されたものであることを特徴とする装置。
【請求項１３】
請求項４または８に記載の装置において、
上記第１および第２の特徴量データが示す範囲の上記最小値および上記最大値がブロック内の複数画素の最大値、最小値およびダイナミックレンジの内の二つのデータで表されたものであることを特徴とする装置。
【請求項１４】
請求項４または８に記載の装置において、
上記第１および第２の特徴量データが示す範囲の上記最小値および上記最大値がブロック内の画素のダイナミックレンジおよび最大値若しくは最小値のうちの一方で表されたものである場合に、演算によって上記最大値および最小値を求めることを特徴とする装置。
【請求項１５】
請求項４または８に記載の装置において、
上記第１および第２の特徴量データが示す範囲の上記最小値および上記最大値がブロック内の複数画素の平均値と標準偏差の和データおよび上記平均値と標準偏差の差データで表されたものであることを特徴とする装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は、一般的には、二つのディジタル画像の部分的照合をとるための方法および装置、より具体的には、ブロックマッチング法により画像の動きの方向および量を表す動きベクトルを検出する場合に適用可能な画像照合方法および装置に関する。
【０００２】
【従来の技術】
動きベクトルの一つの利用分野は、ディジタル画像データの予測符号化における動き補償である。一例として、動画の高能率符号化の国際的標準方式である、ＭＰＥＧ(Moving Picture Coding Experts Group) 方式が提案されている。このＭＰＥＧ方式は、ＤＣＴ(Discrete Cosine Transform) と動き補償予測符号化とを組み合わせたものである。
【０００３】
図１６は、動き補償予測符号化装置の一例を示す。図１６において、入力端子６１からのディジタルビデオデータが動きベクトル検出回路６２および減算回路６３に供給される。動きベクトル検出回路６２では、現フレームと参照フレーム（例えば時間的に前フレーム）との間の動きベクトルが検出される。この動きベクトルが動き補償回路６４に供給される。
【０００４】
フレームメモリ６５に蓄えられている画像が動き補償回路６４において動きベクトルに基づいて動き補償された後に、減算回路６３および加算回路６６に供給される。減算回路６３では、現フレームのビデオデータと動き補償回路６４からの前フレームの復号ビデオデータとが画素毎に減算される。減算回路６３からの差分データがＤＣＴ回路６７においてＤＣＴ変換される。ＤＣＴ回路６７からの係数データが量子化回路６８により再量子化される。量子化回路６８の出力データが出力端子６９に取り出されるとともに、逆量子化回路７０に供給される。
【０００５】
逆量子化回路７０とこれに接続された逆ＤＣＴ回路７１とは、ＤＣＴ回路６７および量子化回路６８と反対の処理を行うためのローカル復号回路を構成する。逆ＤＣＴ回路７１からの復号差分データが加算回路６６に供給される。加算回路６６の出力データがフレームメモリ６５を介して動き補償回路６４に供給される。動き補償回路６４からの前フレームの復号データが加算回路６６に供給されることで、復号データが形成され、この復号データがフレームメモリ６５に蓄えられる。
【０００６】
動きベクトル検出回路６２では、ブロックマッチング法により動きベクトルが検出される。これは、参照フレームの検査ブロックを所定の探索範囲内で移動し、現フレームの基準ブロックと最も合致しているブロックを検出することにより動きベクトルを求めるものである。従って、動きベクトルは、ブロック毎に求められる。なお、画面全体あるいは１画面を１／４に分割した領域のような比較的大きい領域の動きベクトルを求める場合もある（例えば特開昭６１−１０５１７８号公報参照）。
【０００７】
ブロックマッチング法では、図１７Ａに示すように、１枚の画像、例えば水平Ｈ画素、垂直Ｖラインの１フレームの画像が図１７Ｂに示すように、Ｐ画素×Ｑラインのブロックに細分化される。図１７Ｂの例では、Ｐ＝５、Ｑ＝５の例である。ｃがブロックの中心画素位置である。
【０００８】
図１８は、ｃを中心画素とする基準ブロックとｃ´を中心とする検査ブロックの位置関係を示している。ｃを中心画素とする基準ブロックは、現フレームの注目しているある基準ブロックであり、その画像と一致する参照フレームの検査ブロックが参照フレームにおいてｃ´を中心とするブロックの位置にあるものとしている。ブロックマッチング法では、探索範囲内において、基準ブロックと最も合致する検査ブロックを見出すことによって、動きベクトルを検出する。
【０００９】
図１８Ａの場合では、水平方向に−１画素、垂直方向に−１ライン、すなわち、（−１，−１）の動きベクトルが検出される。図１８Ｂでは、（−３，−３）の動きベクトルが検出され、図１８Ｃでは、（−２，＋１）の動きベクトルが検出される。動きベクトルは、現フレームの基準ブロック毎に求められる。動きベクトルの極性は、テレビジョンのラスター走査の方向と一致する方向を＋としている。
【００１０】
動きベクトルを探索する範囲を水平方向で±Ｓ画素、垂直方向で±Ｔラインとすると、基準ブロックは、その中心ｃに対して、水平に±Ｓ、垂直に±Ｔずれたところに中心ｃ´を有する検査ブロックと比較される必要がある。図１９は、現フレームのある基準ブロックの中心ｃの位置をＲとする時に、比較すべき参照フレームの（２Ｓ＋１）×（２Ｔ＋１）個の検査ブロックとの比較が必要なことを示している。すなわち、この図１９のます目の位置にｃ´が存在する検査ブロックの全てが比較対象である。図１９は、Ｓ＝４，Ｔ＝３とした例である。
【００１１】
探索範囲内の比較で得られた評価値（すなわち、フレーム差の絶対値和、このフレーム差の二乗和、あるいはフレーム差の絶対値のｎ乗和）の中で、最小値を検出することによって、動きベクトルが検出される。図１９の探索範囲は、検査ブロックの中心が位置する領域であり、検査ブロックの全体が含まれる探索範囲の大きさは、（２Ｓ＋Ｐ）×（２Ｔ＋Ｑ）となる。
【００１２】
図２０は、従来の動きベクトル検出装置の一例の構成を示す。図２０において、８１が現フレームの画像データの入力端子であり、この画像データが現フレームメモリ８３に蓄えられる。８２が参照フレームの画像データの入力端子であり、この画像データが参照フレームメモリ８４に蓄えられる。
【００１３】
現フレームメモリ８３および参照フレームメモリ８４の読出し／書込みは、コントローラ８５によって制御される。現フレームメモリ８３からは、現フレームの基準ブロックの画素データが読出され、参照フレームメモリ８４からは、参照フレームの検査ブロックの画素データが読出される。参照フレームメモリ８４と関連してアドレス移動回路８６が設けられる。コントローラ８５がアドレス移動回路８６を制御する結果、検査ブロックの中心位置が１画素ステップで、探索範囲内を移動される。
【００１４】
現フレームメモリ８３の出力と参照フレームメモリ８４の出力とが差分検出回路８７に供給され、１画素毎の差分が検出される。差分検出回路８７の出力が絶対値化回路８８で絶対値に変換され、この絶対値が累算回路８９に供給される。累算回路８９が１ブロックで発生した絶対値差分を累算し、その出力が評価値として判断回路９０に供給される。判断回路９０は、探索範囲内で検査ブロックを移動させた時にそれぞれ発生する差分の絶対値和から動きベクトルを検出する。すなわち、最小の差分の絶対値和を発生する検査ブロックの位置を動きベクトルとして検出する。
【００１５】
上述の従来のブロックマッチング法は、基準ブロックと検査ブロックとの間でフレーム差分の絶対値和を求める処理を探索範囲内で行う必要がある。上述の図１７、図１８、図１９の例では、（Ｐ×Ｑ）回の絶対値差分の累算を全ての探索点、すなわち，（２Ｓ＋１）×（２Ｔ＋１）回行う必要がある。この関係から、演算量は、（Ｐ×Ｑ）×（２Ｓ＋１）×（２Ｔ＋１）で表される。従って、上述のブロックマッチング法は、ハードウエアの規模が大きく、演算量が膨大であるという問題点があった。
【００１６】
より具体的な例として、図２２に示すように、Ｐ＝１６，Ｑ＝１６、Ｓ＝２，Ｔ＝２の例を考える。このＳおよびＴの数値は、説明および図示の簡単のために、非常に小さな値としており、実際には、より大きな探索範囲が設定される。図２１では、基準ブロックと（＋２，＋２）の移動量の検査ブロックとが描かれている。この具体例では、探索範囲を水平および垂直方向に±２としており、探索点が（５×５＝２５）である。
【００１７】
そして、ブロックマッチングのための演算量について考えると、（１６×１６）回の画素間の差分を求める減算と、その絶対値を得る減算と、全ての差分の絶対値を加算する演算とを一つの探索点について必要とする。さらに、この演算を２５個の全ての探索点について行う必要がある。従って、ブロックマッチング法における演算量は、照合画素数×探索点に依存すると考えることができ、この演算量が膨大となる。従来において、基準ブロック内の画素を一つの代表点画素とし、代表点データと検査ブロック内のデータとの差分を演算するものが提案されている（例えば特開昭６２−２５５８７号公報参照）。この方式は、ハードウエアの簡略化あるいは処理時間の短縮化をある程度達成することができるが、演算量の大幅な減少を達成することができない。
【００１８】
この対策として、探索方式を簡略化する手法と、照合方式を簡略化する手法が提案されている。探索を簡略化する方法としては、探索範囲で検査ブロックを移動する時に、最初のステップとして、数画素の間隔で検査ブロックを移動させることによって、大まかな動きベクトルを検出し、次のステップで、検出された位置の付近で、１画素間隔で検査ブロックを移動させることによって、最終的に動きベクトルを求める方法（２ステップ法）が知られている。ステップ数を３とした３ステップ法も考えられる。この方法によれば、フルサーチで必要とされた、全ての探索点において必要とされた演算を各ステップで検出された動きベクトルの周辺の探索点と対応する回数へ減少させることができる。
【００１９】
さらに、照合方式および探索方式の双方を簡略化する方法として、ブロック内の画素数を間引き（サブサンプリング）により減少させるものである。例えば図２２に示すように、（１６×１６）画素のブロックを水平および垂直方向に１／４の間引きを行ない、ブロック内の画素数を１／１６に減少させる。また、探索点は、４画素毎に存在する。これによって、照合画素数および探索点を少なくできる。
【００２０】
照合方式および探索方式の双方を簡略化する他の方法として、階層構造を採用するものが提案されている。一例として、原画像（第１階層と称する）と、第１階層からローパスフィルタおよび／またはサブサンプリングによって、水平および垂直方向で画素数が１／２に間引かれた第２階層と、さらに、第２階層をローパスフィルタおよび／またはサブサンプリングによって、水平および垂直方向で１／２に間引いた第３階層とからなる階層構造を規定する。
【００２１】
そして、第３階層に関してブロックマッチングを行ない、検出された最小値の位置に原点を移動して第２階層に関してブロックマッチングを行ない、検出された最小値の位置に原点を移動して、第１階層に関してブロックマッチングを行い、最終的に１画素ステップのブロックマッチングで動きベクトルを検出する。
【００２２】
照合方式および探索方式の双方を簡略化するさらに他の方法として、基準ブロックおよび検査ブロックを水平方向および垂直方向のそれぞれの方向で小ブロックに更に分割し、小ブロック毎に特徴量を抽出するものが提案されている。すなわち、基準ブロックおよび検査ブロックの間で、水平方向小ブロックの特徴量と垂直方向小ブロック特徴量とを別個に比較し、比較結果の絶対値をそれぞれ累算し、累算結果を加重平均したものをブロック間の比較結果として用いる。小ブロックの特徴量は、例えばその小ブロック内の画素データの累算結果である。この方法は、１ブロック内の全画素数に関して必要とされた演算を水平および垂直方向の小ブロックの数に減少することができる。
【００２３】
【発明が解決しようとする課題】
ブロックマッチングの上述したような種々の改良は、演算量を減少させることはできるが、誤検出が生じる欠点を有している。これは、簡略化の結果として、原画像の有する情報量の欠落が生じるからである。
【００２４】
より具体的に述べると、ブロック内の要素数（照合画素数）を減らすようにした照合方式の簡略化においては、ブロックの画像データのディテイルが失われ、その結果、誤検出が生じる。図２３に示すように、基準ブロックと検査ブロック（簡単のため、各ブロックが１次元ブロックとする）を照合する場合を考える。基準ブロックデータを４画素毎に平均化したものは、検査ブロックデータと同じ波形となり、元の二つのデータは、異なる波形であるにもかかわらず、比較の結果、両者が合致するものと判定され、誤検出が生じる。
【００２５】
この問題の一つの解決法を本願発明者は、提案している（特願平５−２４８８１３号参照）。この方法は、基準ブロックと検査ブロックとを比較する時に、定常成分と過渡成分とをそれぞれ各ブロックから抽出し、定常成分同士、過渡成分同士を比較することによって、誤検出を防止しようとするものである。図２４の例において、過渡成分の一例として、平均値に対する差分の絶対値を求めると、基準ブロックデータと検査ブロックデータとが大きく異なったものとなる。従って、過渡成分を参照することによって、誤検出を防止することができる。
【００２６】
探索点を減少することによって、探索を簡略化する方法では、大まかな動きベクトルを検出する時に、精度が粗いために、誤検出のおそれが生じる。照合方式および探索方式の簡略化を行う方法では、やはり、間引かれた画像あるいはローパスフィルタを通した画像に基づいて動きベクトルの検出する時に、誤検出のおそれがある。
【００２７】
さらに、探索点を減少させる時には、探索点の位相と画像の動きとの間に位相ずれが生じる。これを図２４を参照して説明する。図２４は、１次元ブロックについて４画素毎の探索点を設定した場合であり、原信号の波形を水平に、１画素、２画素、３画素および４画素移動した波形がそれぞれ示されている。基準ブロックと検査ブロックの切り出しが同一位相の場合では、静止と４画素の倍数の動きにおいて、両ブロックが合致し、これを検出できる。しかしながら、それ以外の動きは、検出することができない。
【００２８】
特に、変化が激しい画像の場合には、真の動きが３画素以下であっても、原点から４画素離れた探索点における差分の絶対値の累算値が非常に大きな値となるおそれがある。若し、他の探索点における差分の絶対値の累算値がこれより小さな時には、検出される動きが真のものとかけ離れたものとなる。
【００２９】
従って、この発明の目的は、演算量を減少でき、ハードウエアが簡単な特徴を備え、また、誤検出を防止でき、さらに、位相ずれの補償および検出精度の向上が可能な画像照合方法および装置を提供することにある。
【００３０】
【課題を解決するための手段】
請求項１に記載の発明は、第１の画像データを複数の基準ブロックへ分割し、基準ブロックをさらに複数の基準サブブロックへ分割するステップと、
第２の画像データを複数の検査ブロックへ分割し、検査ブロックをさらに複数の検査サブブロックへ分割するステップと、
基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出するステップと、
検査サブブロックについて、代表画素データとの比較に使用する画素データを選択するステップと、
検査サブブロック内の選択された画素データの値の最小値から最大値までの範囲を示す特徴量データを抽出するステップと、
代表画素データの値が特徴量データの示す範囲内に存在する場合に０となり、代表画素データの値が範囲内に存在しない場合に代表画素データの値と最大値または最小値との差分となる評価値を複数の検査サブブロックについてそれぞれ求め、求められた評価値を積算してブロック単位の評価値を生成するステップと、
ブロック単位の評価値の大小に基づいて第１および第２の画像データの部分的照合を行うステップとからなり、
代表画素データとの比較に使用する画素データを選択するステップは、
基準ブロックの複数の代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
検査ブロック内の複数の検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、第１の指示データと同一種類の値を示す第２の指示データを形成し、
第１および第２の指示データの差がしきい値以下の場合に、複数の検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合方法である。
【００３１】
請求項２に記載の発明は、第１の画像データを複数の基準ブロックへ分割し、基準ブロックをさらに複数の基準サブブロックへ分割する手段と、
第２の画像データを複数の検査ブロックへ分割し、検査ブロックをさらに複数の検査サブブロックへ分割する手段と、
基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出する手段と、
検査サブブロックについて、代表画素データとの比較に使用する画素データを選択する手段と、
検査サブブロック内の選択された画素データの値の最小値から最大値までの範囲を示す特徴量データを抽出する手段と、
代表画素データの値が特徴量データの示す範囲内に存在する場合に０となり、代表画素データの値が範囲内に存在しない場合に代表画素データの値と最大値または最小値との差分となる評価値を複数の検査サブブロックについてそれぞれ求め、求められた評価値を積算してブロック単位の評価値を生成する手段と、
ブロック単位の評価値の大小に基づいて第１および第２の画像データの部分的照合を行う手段とからなり、
代表画素データとの比較に使用する画素データを選択する手段は、
基準ブロックの複数の代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
検査ブロック内の複数の検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、第１の指示データと同一種類の値を示す第２の指示データを形成し、
第１および第２の指示データの差がしきい値以下の場合に、複数の検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合装置である。
【００３２】
請求項３に記載の発明は、第１の画像データをそれぞれが検査ブロックと同一の大きさの複数の基準ブロックへ分割し、基準ブロックをさらに複数の基準サブブロックへ分割するステップと、
第２の画像データを複数の基準ブロックと同一の大きさの検査ブロックへ分割すると共に、検査ブロックをさらに複数の検査サブブロックに分割し、検査サブブロックを各々所定画素数拡大した複数の修正検査サブブロックを構成するステップと、
基準サブブロック内の全画素の値の最小値から最大値までの範囲を示す第１の特徴量データを抽出するステップと、
基準サブブロックと対応する修正検査サブブロックについて、第１の特徴量データとの比較に使用する画素データを選択するステップと、
修正検査サブブロック内の選択された画素データの値の最小値から最大値までの範囲を示す第２の特徴量データを抽出するステップと、
第１の特徴量データの最小値および最大値のそれぞれが第２の特徴量データの最小値および最大値の範囲内に存在する場合に０となり、最小値および最大値のそれぞれが範囲内に存在しない場合に、最小値および最大値のそれぞれと、第２の特徴量データの最小値および最大値のそれぞれとの差分の加算値となる評価値を複数の修正検査サブブロックについてそれぞれ求め、求められた評価値を積算してブロック単位の評価値を生成するステップと、
ブロック単位の評価値の大小に基づいて第１および第２の画像データの部分的照合を行うステップとからなり、
第１の特徴量データとの比較に使用する画素データを選択するステップは、
基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出し、
基準ブロックの複数の代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
複数の修正検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、第１の指示データと同一種類の値を示す第２の指示データを形成し、
第１および第２の指示データの差がしきい値以下の場合に、複数の修正検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合方法である。
【００３３】
請求項４に記載の発明は、第１の画像データをそれぞれが検査ブロックと同一の大きさの複数の基準ブロックへ分割し、基準ブロックをさらに複数の基準サブブロックへ分割する手段と、
第２の画像データを複数の基準ブロックと同一の大きさの検査ブロックへ分割すると共に、検査ブロックをさらに複数の検査サブブロックに分割し、検査サブブロックを各々所定画素数拡大した複数の修正検査サブブロックを構成する手段と、
基準サブブロック内の全画素の値の最小値から最大値までの範囲を示す第１の特徴量データを抽出する手段と、
基準サブブロックと対応する修正検査サブブロックについて、第１の特徴量データとの比較に使用する画素データを選択する手段と、
修正検査サブブロック内の選択された画素データの値の最小値から最大値までの範囲を示す第２の特徴量データを抽出する手段と、
第１の特徴量データの最小値および最大値のそれぞれが第２の特徴量データの最小値および最大値の範囲内に存在する場合に０となり、最小値および最大値のそれぞれが範囲内に存在しない場合に、最小値および最大値のそれぞれと、第２の特徴量データの最小値および最大値のそれぞれとの差分の加算値となる評価値を複数の修正検査サブブロックについてそれぞれ求め、求められた評価値を積算してブロック単位の評価値を生成する手段と、
ブロック単位の評価値の大小に基づいて第１および第２の画像データの部分的照合を行う手段とからなり、
第１の特徴量データとの比較に使用する画素データを選択する手段は、
基準サブブロック内の所定の位置の画素データを代表画素データとしてそれぞれ抽出し、
基準ブロックの複数の代表画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つを示す第１の指示データを形成し、
複数の修正検査サブブロックの対応する位置の複数の画素データの値の平均値、最小値、最大値、ダイナミックレンジ、および標準偏差の少なくとも１つで、第１の指示データと同一種類の値を示す第２の指示データを形成し、
第１および第２の指示データの差がしきい値以下の場合に、複数の修正検査サブブロックの対応する位置の複数の画素データを選択することを特徴とする画像照合装置である。
【００３４】
【作用】
基準ブロックが複数の基準サブブロックへ分割され、各基準サブブロックの例えば中央位置の画素データを第１の代表画素データとして抽出する。第１の代表画素群を指示する第１の指示データとしての平均値が形成される。また、検査ブロックが複数の検査サブブロックへ分割され、各検査サブブロックの互いに対応する位置の画素群を指示する第２の指示データとしての平均値が各位置に関して形成される。これらの平均値が比較され、照合に使用する画素データが選択される。検査サブブロック毎に選択画素データの存在範囲を示す特徴量データ（ＭＡＸ，ＭＩＮ）が抽出される。基準サブブロックから抽出された第２の代表画素データがＭＡＸおよびＭＩＮの範囲に含まれるかどうかの比較がなされる。この比較結果に基づいて評価値が生成される。このように、演算量が低減でき、また、位相ずれの問題を解決することができる。
【００３５】
代表画素データと特徴量とを比較して、照合を行う他に、基準サブブロックと検査サブブロック間で、領域同士の照合を行うことができる。この場合にも、検査サブブロックの中で使用される画素が選択される。すなわち、基準サブブロックの例えば最大値ＭＡＸ１および最小値ＭＩＮ１を第１の特徴量データとして抽出し、検査サブブロックを位相補償のために拡大した修正検査ブロックから同様に、最大値ＭＡＸ２および最小値ＭＩＮ２を第２の特徴量データとして抽出し、第１および第２の特徴量データを比較する。ＭＡＸ２≧ＭＡＸ１で且つＭＩＮ１≧ＭＩＮ２の時には、Δ１＝０、Δ２＝０の評価値が生成される。ＭＡＸ１≧ＭＡＸ２の時は、Δ１＝ＭＡＸ１−ＭＡＸ２、Δ２＝０の評価値が生成される。ＭＩＮ２≧ＭＩＮ１の時には、Δ１＝０、Δ２＝ＭＩＮ２−ＭＩＮ１の評価値が生成される。このようにして、演算量を低減でき、位相補償を行うことができる。
【００３６】
【実施例】
以下、この発明を動きベクトル検出装置に対して適用した一実施例について図面を参照して説明する。図１は、一実施例のブロック図であり、図１において、１が現フレームの画像データの入力端子、２が参照フレームの画像データの入力端子、３が現フレームの画像データを蓄える現フレームメモリ、４が参照フレームの画像データを蓄える参照フレームメモリである。現フレームメモリ３および参照フレームの書込み／読出し動作がコントローラ５により制御される。さらに、参照フレームメモリ４と関連して設けられたアドレス移動回路６がコントローラ５によって制御され、これによって、参照フレーム内で検査ブロックが移動される。
【００３７】
現フレームメモリ３および参照フレームメモリ４に対してサブブロック化回路１４ａおよび１４ｂがそれぞれ接続される。サブブロック化回路１４ａおよび１４ｂがコントローラ５によって制御され、サブブロック化回路１４ａおよび１４ｂから基準サブブロックおよび検査サブブロックのデータが出力される。図２は、この一実施例のブロック構造を説明するためのもので、基準ブロックは、（３×３）画素のサブブロックを（２×３）に配列した構成とされている。検査ブロックも同様の構造である。
【００３８】
基準サブブロックのデータが代表値抽出回路７ａおよび平均化回路１５ａに供給される。代表値抽出回路７ａは、基準サブブロック毎に代表値を抽出する。代表値は、代表画素の値を意味し、例えば図２に示すように、各基準サブブロックの中央位置の画素の値ｘ1 〜ｘ6 である。これ以外に、基準サブブロックの異なる位置の画素の値、または基準サブブロックの最大値、最小値、極値を代表値として使用することができる。平均化回路１５ａは、代表画素群ｘ1 〜ｘ6 の平均値Ｘ（＝（ｘ1 ＋ｘ2 ＋ｘ3 ＋ｘ4 ＋ｘ5 ＋ｘ6 ）／６）を生成する。この平均値Ｘが第１の指示データである。
【００３９】
サブブロック化回路１４ｂからの検査サブブロックのデータが平均化回路１５ｂおよび候補画素選択回路１７に供給される。平均化回路１５ｂは、６個の検査サブブロックのそれぞれの対応する位置の画素データの平均値を形成する。図２に示すように、サブブロック内の左上コーナーから右下コーナーに向かう順序で、画素をａ，ｂ，ｃ，・・・，ｉの符号で区別し、６個のサブブロックの区別を１，２，３，・・・・，６の数字を添えて区別する。
【００４０】
平均化回路１５ｂは、６個の画素の位置のそれぞれについて下記の平均値を形成する。
Ａ＝（ａ1 ＋ａ2 ＋ａ3 ＋ａ4 ＋ａ5 ＋ａ6 ）／６
Ｂ＝（ｂ1 ＋ｂ2 ＋ｂ3 ＋ｂ4 ＋ｂ5 ＋ｂ6 ）／６
Ｃ＝（ｃ1 ＋ｃ2 ＋ｃ3 ＋ｃ4 ＋ｃ5 ＋ｃ6 ）／６
・・・・
・・・・
Ｉ＝（ｉ1 ＋ｉ2 ＋ｉ3 ＋ｉ4 ＋ｉ5 ＋ｉ6 ）／６
これらの平均値Ａ〜Ｉが第２の指示データである。
【００４１】
平均化回路１５ａおよび平均化回路１５ｂのそれぞれの平均値が比較回路１６に供給される。比較回路１６は、平均値Ｘと平均値Ａ〜Ｉとを比較する。例えばＸに対するＡ〜Ｉの差分の絶対値（｜Ｘ−Ａ｜，｜Ｘ−Ｂ｜，｜Ｘ−Ｃ｜，・・・・・，｜Ｘ−Ｉ｜）が計算され、これらの差分の絶対値としきい値とが比較される。しきい値より小の差分の絶対値を生じさせる画素群は、候補画素と決定される。比較回路１６の比較結果がコントローラ１８に供給され、コントローラ１８は、比較結果に応答して、サブブロック化回路１４ｂからの検査サブブロック内の候補画素データを選択的に出力する。
【００４２】
かかる候補画素の選択は、剛体仮定に基づいている。すなわち、基準ブロックが動く時は、基準ブロック内の全画素が平行移動する（回転を許さない）と仮定している。ブロックの大きさが小さいので、かかる仮定は、実際的である。言い換えると、代表画素データｘ1 〜ｘ6 の例えば１フレーム後の位置は、ａ1 〜ａ6 の位置、ｂ1 〜ｂ6 の位置、・・・・・、ｉ1 〜ｉ6 の中のいずれかの位置である。従って、代表画素データ群を表す平均値と比較して、かけ離れた平均値を呈するものは、剛体仮定に反するものとして、後述の照合の前に排除する。それによって、照合の精度を向上できる。なお、指示データとしては、平均値に限らず、最大値ＭＡＸ、最小値ＭＩＮ、ダイナミックレンジＤＲ（＝ＭＡＸ−ＭＩＮ）、標準偏差等を使用しても良い。
【００４３】
候補画素選択回路１７で選択された候補画素データが最大値、最小値（ＭＡＸ，ＭＩＮ）検出回路８に供給される。ＭＡＸ，ＭＩＮ検出回路８は、検査サブブロックの特徴量としての最大値ＭＡＸおよび最小値ＭＩＮを検出する。特徴量としては、ＭＡＸ，ＭＩＮおよびダイナミックレンジＤＲ（＝ＭＡＸ−ＭＩＮ）の内の二つの値を使用することができる。さらに、検査サブブロックの平均値Ａｖおよび標準偏差σを計算し、Ａｖ＋σとＡｖ−σとを特徴量として使用しても良い。
【００４４】
ブロックマッチングの対象としては、上述のような現フレームと参照フレーム（現フレームに対して時間的に前あるいは後のフレーム）に限られない。例えば２枚の静止画像間で動きベクトルを検出する場合、または解像度が異なる画像同士の間で動きベクトルを検出する場合に対しても、この発明を適用することができる。さらに、動きベクトルの検出に限らず、二つの静止画像間で照合をとる場合、例えば集合写真に相当する静止画像を参照画像とし、特定の人物の写真を注目画像とし、注目画像が参照画像中のどの位置に存在しているかを検出するような画像照合に対しても適用できる。この例では、参照画像の全体が探索範囲となる。
【００４５】
ＭＡＸ，ＭＩＮ検出回路８の一例を図３に示す。入力端子２１からは、候補画素選択回路１７で選択された検査サブブロックの画素データが供給される。この入力データがタイミング生成回路２２、選択回路２３および２４にそれぞれ供給される。タイミング生成回路２２は、画素データと同期したサンプルクロックおよび検査サブブロックの区切りを示すブロックタイミング信号を発生する。
【００４６】
選択回路２３は、二つの画素データの内のより大きな値の画素データを選択的に出力し、選択回路２４は、二つの画素データの内のより小さな値の画素データを選択的に出力する。選択回路２３の出力データがラッチ２５およびレジスタ２７に供給され、選択回路２４の出力データがラッチ２６およびレジスタ２８に供給される。レジスタ２７および２８の出力が選択回路２３および２４に入力される。ラッチ２５から出力端子２９にその検査サブブロックの候補画素の最大値ＭＡＸが取り出され、ラッチ２６から出力端子３０にその検査サブブロックの候補画素の最小値ＭＩＮが取り出される。
【００４７】
レジスタ２７は、一つの検査サブブロックの選択データが入力される前の初期状態では、ゼロにクリアされている。そして、選択回路２３の出力がレジスタ２７に取り込まれ、レジスタ２７の出力および入力画素データの内のより大きな値が選択回路２３によって選択されるので、次の画素データが到来する時には、以前の画素データの最大値がレジスタ２７に保持されている。そして、一つの検査サブブロックの選択画素データが入力された時に、選択回路２３がその検査サブブロックの最大値ＭＡＸを出力する。このＭＡＸがラッチ２５に取り込まれる。最小値ＭＩＮの検出も同様になされ、出力端子３０に検査サブブロックのＭＩＮが取り出される。
【００４８】
代表値と検出されたＭＡＸおよびＭＩＮは、比較回路９および評価値計算回路１０にそれぞれ供給される。比較回路９の比較結果がコントローラ１８に供給され、コントローラ１８が評価値計算回路１０を制御する。比較回路９および評価値計算回路１０の処理をソフトウェア処理で行う時のフローチャートが図４に示される。一つの基準サブブロックの代表値ｘとこれと対応する位置の一つの検査サブブロックの候補画素データの最大値ＭＡＸおよび最小値ＭＩＮについて説明する。比較処理が開始されると、ステップ３１において、ｘ＞ＭＡＸが調べられる。若し、この関係が成立する（Ｙ）時には、ステップ３２へ処理が移り、評価値Δ＝ｘ−ＭＡＸが生成される。
【００４９】
ステップ３１の結果が否定（Ｎ）の時には、ステップ３３において、ｘ＜ＭＩＮの関係が成立するかどうかが調べられる。これが成立する時には、Δ＝ＭＩＮ−ｘが生成される。ステップ３３における関係が成立しない時、すなわち、ＭＩＮ≦ｘ≦ＭＡＸの時には、Δ＝０（ステップ３５）とされる。このように生成された評価値Δが出力される（ステップ３６）。
【００５０】
図５は、比較回路９および評価値計算回路１０をハードウエアで構成した時のブロック図である。比較回路９には、基準サブブロックおよび対応検査サブブロックの代表値ｘ、ＭＡＸおよびＭＩＮが供給され、２ビットの比較出力が発生する。この比較出力が選択回路４１を制御する。選択回路４１の入力端子ａには、減算回路４２からのｘ−ＭＡＸが供給される。その入力端子ｂには、ゼロデータが供給される。その入力端子ｃには、減算回路４３からのＭＩＮ−ｘが供給される。
【００５１】
比較回路９の２ビットの出力は、ｘ＞ＭＡＸ、ｘ＜ＭＩＮ、ＭＩＮ≦ｘ≦ＭＡＸの３つの関係を指示するものであって、各関係に応じて入力端子ａ、ｂ、ｃが選択され、上述と同様の評価値Δが生成される。評価値計算回路１０で生成された評価値Δが出力端子４４を介して累算回路１９に供給され、累算回路１９の出力が評価値メモリ１１に格納される。
【００５２】
評価値Δは、図６に示すように、各基準サブブロックの代表値が各検査サブブロックの候補画素のＭＩＮおよびＭＡＸの間の範囲に含まれる時に、０であり、ＭＩＮより小さい時およびＭＡＸより大きい時には、次第に大きくなる値である。実際には、ノイズが存在するので、ノイズマージンを設定し、図６における破線のような変化を呈する評価値Δを形成しても良い。なお、図５の構成は、一例であって、ゲート回路あるいは２入力の選択回路の組合せ等によって、種々の構成が可能である。また、評価値としては、差分の絶対値、差分のｎ乗値等を使用しても良い。
【００５３】
上述の評価値は、基準サブブロックの代表画素と対応する位置の検査サブブロックについてそれぞれ計算される。従って、図７に示すように、６個のサブブロックと対応する６個の評価値Δ１〜Δ６が求まる。この評価値Δ１〜Δ６が累算回路１９によって累算される（すなわち、Δ１＋Δ２＋Δ３＋・・・＋Δ６）。そして、累算結果（総合評価値）が評価値メモリ１１に格納される。
【００５４】
図１に戻って説明すると、評価値メモリ１１への総合評価値の格納は、コントローラ５により制御される。そして、所定の探索範囲で総合評価値がそれぞれ求められ、総合評価値の中の最小値が最小値検出回路１２において検出される。最小値の存在する位置がその基準ブロックの動きベクトルである。
【００５５】
図８は、例えば±５の探索範囲（一点鎖線で示す）の一部を示す。基準ブロックの右下の頂点を基準として考え、３画素毎に目盛られた座標軸（ｘ，ｙ）が描かれている。なお、基準の点は、より好ましくは、ブロック内のより中心に近い点に設定される。例えば図８に示すような（＋５，＋５）の位置の検査ブロックが最小の総合評価値を生じさせる時には、（＋１５（＝５×３），＋１５（＝５×３））の動きベクトルが出力される。
【００５６】
上述の一実施例は、要約すると、基準サブブロックの代表画素と検査サブブロック（領域）間の照合をとるもので、検査サブブロックの候補画素の全てを代表する量として、例えば最大値ＭＡＸおよび最小値ＭＩＮを求めている。代表画素の値がこの間に存在しない場合には、基準サブブロックと検査サブブロックの照合の可能性はない。剛体仮定を導入することによって、照合の精度を向上できる。従来では、探索点を減少させる簡略化を行うと、位相ずれによって誤検出が生じる問題があった。この発明は、探索点を例えば３画素毎に減少させても、フルサーチと等価な処理、すなわち、位相ずれを生じない照合を行うことができる。
【００５７】
図９は、この発明が位相ずれを生じないことを説明するものである。簡単のために、ａ、ｂ、ｃの値をそれぞれ有する３画素からなる１次元ブロックを考える。破線は、３画素毎に描かれている。この１次元ブロックを基準ブロックとして考え、その中央位置の画素の値ｂが代表値である。図９では、基準ブロックが＋１画素の動き、−１画素の動き、＋２画素の動き、＋３画素の動き、＋４画素の動きがそれぞれ示されている。
【００５８】
この図９から分かるように、±１画素の動きの場合でも、代表値ｂが３画素の区切りの中に存在している。従って、±１画素の動きの場合でも、検査サブブロックとの照合がとれ、評価値Δが０となる。＋２画素、＋３画素、＋４画素の動きは、次の検査ブロックとの照合によって、検出することができる。従って、検査ブロックの区切りをオーバーラップさせる必要がない。従来の探索点の簡略化では、静止並びに探索点の間隔の倍数の動きしか正確に検出することができなかった。この発明は、かかる位相ずれを補償することができる。
【００５９】
次に、この発明の他の実施例について説明する。他の実施例では、サブブロック間の照合をとる時に、領域対領域で比較するものである。検査サブブロック内の候補画素の選択は、上述の一実施例と同様になされる。他の実施例の構成を示す図１０において、代表値抽出回路７、平均化回路１５ａ、１５ｂ、比較回路１６、候補画素選択回路１７は、上述の一実施例と同様である。
【００６０】
他の実施例のブロック構成を図１１に示す。基準サブブロックは、例えば（２×４）画素の大きさである。検査サブブロックは、基準サブブロックと同様に、（２×４）画素の２次元領域である。修正検査サブブロックは、後述のように、位相補償範囲の±１ラインおよび±２画素を検査ブロックに付加した領域である。図示しないが、基準および検査サブブロックを例えば（２×４）個並べたものがそれぞれ基準ブロックおよび検査ブロックとされる。
【００６１】
サブブロック化回路１４ａからの基準サブブロックの画素データが最大値，最小値（ＭＡＸ１，ＭＩＮ１）抽出回路７ａに供給される。ＭＡＸ１，ＭＩＮ１抽出回路７ａは、基準サブブロック毎に最大値ＭＡＸ１および最小値ＭＩＮ１を第１の特徴量として抽出する。第１の特徴量としては、ＭＡＸ１，ＭＩＮ１およびダイナミックレンジＤＲ１（＝ＭＡＸ１−ＭＩＮ１）の内の二つの値を使用することができる。さらに、第１の特徴量としては、これ以外に、基準サブブロックの平均値Ａｖ１および標準偏差σ１を計算し、Ａｖ１＋σ１とＡｖ１−σ１とを使用しても良い。
【００６２】
サブブロック化回路１４ｂからの修正検査サブブロックのデータが候補画素選択回路１７に供給され、選択された画素データが最大値、最小値（ＭＡＸ２，ＭＩＮ２）検出回路８に供給される。ＭＡＸ２，ＭＩＮ２検出回路８は、第２の特徴量としての最大値ＭＡＸ２および最小値ＭＩＮ２を検出する。第２の特徴量としては、ＭＡＸ２，ＭＩＮ２およびダイナミックレンジＤＲ２（＝ＭＡＸ２−ＭＩＮ２）の内の二つの値を使用することができる。さらに、修正検査サブブロックの平均値Ａｖ２および標準偏差σ２を計算し、Ａｖ＋σとＡｖ−σとを第２の特徴量として使用しても良い。
【００６３】
ＭＡＸ，ＭＩＮ検出回路７ｂおよび８は、上述したような図３と同様の構成とされている。そして、ＭＡＸ，ＭＩＮ検出回路７ｂおよび８のそれぞれによって、検出されたＭＡＸ１，ＭＩＮ１，ＭＡＸ２，ＭＩＮ２は、比較回路９および評価値計算回路１０にそれぞれ供給される。比較回路９および評価値計算回路１０の処理をソフトウェア処理で行う時のフローチャートが図１２に示される。
【００６４】
比較処理が開始されると、ステップ１３１において、ＭＡＸ１＞ＭＡＸ２が成立するかどうかが調べられる。若し、この関係が成立しない（Ｎ）時（すなわち、ＭＡＸ２≧ＭＡＸ１の時）には、ステップ１３２へ処理が移り、評価値Δ１＝０とされる。そして、次に、ＭＩＮ１＜ＭＩＮ２が成立するかどうかが調べられる（ステップ１３３）。若し、この関係が成立しない（Ｎ）時（すなわち、ＭＩＮ１≧ＭＩＮ２の時）には、ステップ１３４へ処理が移り、評価値Δ２＝０とされる。従って、評価値Δ１＝０、Δ２＝０（ステップ１３５ａ）である。これは、基準サブブロックの最小値ＭＩＮ１および最大値ＭＡＸ１が修正検査サブブロックＭＩＮ２および最大値ＭＡＸ２の範囲内に含まれ、基準サブブロックと検査サブブロックとの照合が成立したと判断されることを意味する。若し、ステップ１３３の結果が肯定の場合では、Δ１＝０、Δ２＝ＭＩＮ２−ＭＩＮ１の評価値が生成される（ステップ１３５ｂ）。
【００６５】
ステップ１３１の結果が肯定（Ｙ）の時には、ステップ１３６において、ＭＩＮ１＜ＭＩＮ２の関係が成立するかどうかが調べられる。これが成立しない時（すなわち、ＭＩＮ１≧ＭＩＮ２の時）には、Δ２＝０とされ（ステップ１３７）、Δ１＝ＭＡＸ１−ＭＡＸ２，Δ２＝０の評価値が生成される（ステップ１３５ｃ）。ステップ１３６の結果が肯定の時には、Δ１＝ＭＡＸ１−ＭＡＸ２，Δ２＝ＭＩＮ２−ＭＩＮ１の評価値が生成される（ステップ１３５ｄ）。
【００６６】
図１３は、比較回路９および評価値計算回路１０をハードウエアで構成した時のブロック図である。比較回路９には、基準サブブロックのＭＡＸ１およびＭＩＮ１と修正検査サブブロックのＭＡＸ２およびＭＩＮ２が供給され、二つの比較出力が発生する。これらの比較出力が選択回路１４１および１４２を制御する。選択回路１４１の入力端子ａには、減算回路１４５からのＭＡＸ１−ＭＡＸ２が供給され、その入力端子ｂには、ゼロデータが供給される。選択回路１４２の入力端子ａには、減算回路１４６からのＭＩＮ２−ＭＩＮ１が供給され、その入力端子ｂには、ゼロデータが供給される。
【００６７】
比較回路９の一方の出力は、ＭＡＸ１＞ＭＡＸ２の時には、選択回路１４１が入力端子ａ（すなわち、ＭＡＸ１−ＭＡＸ２）を選択するように制御し、ＭＡＸ１＜ＭＡＸ２の時には、選択回路１４１が入力端子ｂ（すなわち、ゼロデータ）を選択するように制御する。比較回路９の他方の出力は、ＭＩＮ１＜ＭＩＮ２の時には、選択回路１４２が入力端子ａ（すなわち、ＭＩＮ２−ＭＩＮ１）を選択するように制御し、ＭＩＮ１≧ＭＩＮ２の時には、選択回路１４２が入力端子ｂ（すなわち、、ゼロデータ）を選択するように制御する。選択回路１４１からの評価値Δ１と選択回路１４２からの評価値Δ２とが加算回路１４３に供給される。選択回路１４３からのΔ１＋Δ２の出力が出力端子１４４に取り出される。
【００６８】
評価値Δ１およびΔ２は、図１４に示すように変化する。評価値Δ１は、ＭＡＸ１がＭＡＸ２よりも小さい範囲では、０であり、ＭＡＸ２よりも大きくなるに従って、その値が大きくなる。また、評価値Δ２は、ＭＩＮ１がＭＩＮ２よりも大きい範囲では、０であり、ＭＩＮ２よりも小さくなるに従って、その値が大きくなる。実際には、ノイズが存在するので、ノイズマージンを設定し、図１４における破線のような変化を呈する評価値Δ１およびΔ２を形成しても良い。なお、図１３の構成は、一例であって、種々の構成が可能である。また、評価値としては、差分の絶対値、差分のｎ乗値等を使用しても良い。
【００６９】
上述の評価値は、基準サブブロックと対応する位置の検査サブブロックについてそれぞれ計算される。この評価値が累算回路１９によって、累算され、累算回路１９から総合評価値が発生する。この総合評価値が評価値メモリ１１に格納される。所定の探索範囲において、検査ブロックのそれぞれの位置で総合評価値が計算される。この総合評価値の中の最小値が最小値検出回路１２によって検出され、検出された最小値の位置と対応する動きベクトルが出力端子１３に取り出される。
【００７０】
他の実施例は、要約すると、基準サブブロックの領域と検査サブブロックの領域間の照合をとるもので、修正検査サブブロックの選択画素の存在範囲を表す量として、例えば最大値ＭＡＸ２および最小値ＭＩＮ２を求めている。基準サブブロックのＭＡＸ１およびＭＩＮ１がこの間に存在しない場合には、両者が照合しないと判断される。剛体仮定を導入して、候補画素を選択することによって、検出精度を向上できる。また、従来では、探索点を減少させる簡略化を行うと、位相ずれによって誤検出が生じる問題があった。この発明は、探索点を例えば数画素毎に減少させても、フルサーチと等価な処理、すなわち、位相ずれを生じない照合を行うことができる。
【００７１】
図１５は、この発明が位相ずれを生じないことを説明するものである。簡単のために、ａ、ｂ、ｃ、ｄの値をそれぞれ有する４画素からなる１次元ブロックを考える。破線は、４画素毎に描かれている。この１次元ブロックを基準ブロックとして考える。図１５では、基準ブロックが＋１画素の動き、＋２画素の動き、＋３画素の動き、＋４画素の動きがそれぞれ示されている。
【００７２】
この図１５から分かるように、領域同士を比較する時に、検査ブロックが基準ブロックと同じ大きさの場合では、＋１画素、＋２画素、＋３画素、＋４画素の動きの場合には、誤照合が発生する可能性がある。しかしながら、４画素の大きさの場合では、検査ブロックに対して、左右に２画素分の拡張領域を付加しているので、誤照合を防止できる。＋３画素および＋４画素の動きは、次の基準ブロックに関する照合によって、照合をとることができる。どの程度の幅を検査ブロックに対して付加するかは、ブロックの大きさによって変化する。従来の探索点の簡略化では、静止並びに探索点の間隔の倍数の動きしか正確に検出することができなかった。この発明は、かかる位相ずれを補償することができる。
【００７３】
この発明の具体的構成は、上述の一実施例および他の実施例の構成以外に種々のものが可能である。例えば過渡成分を考慮して簡略化による誤検出を防止する方式を併用しても良い。また、動きベクトルを求める時に、動きベクトルの精度を１画素ではなく、ハーフペル精度とするようにしても良い。
【００７４】
【発明の効果】
この発明は、探索点を簡略化するのと同様に、演算量および比較回数を大幅に減少することができる。これと共に、位相ずれによる誤検出を防止することができる。また、この発明は、照合の前処理として、剛体仮定に基づく候補画素の選択を行うので、検出精度を向上することができる。
【図面の簡単な説明】
【図１】この発明の一実施例の構成を示すブロック図である。
【図２】この発明の一実施例におけるブロックの構成を示す略線図である。
【図３】この発明の一実施例における最大値，最小値検出回路の一例のブロック図である。
【図４】代表画素の値と最大値，最小値の比較処理および評価値生成の処理を示すフローチャートである。
【図５】代表画素の値と最大値，最小値の比較回路および評価値生成回路の一例のブロック図である。
【図６】評価値の説明に用いる略線図である。
【図７】総合評価値の形成の説明に用いる略線図である。
【図８】この発明の一実施例の探索範囲の一部を示す略線図である。
【図９】この発明の一実施例による位相補償を説明するための略線図である。
【図１０】この発明の他の実施例のブロック図である。
【図１１】この発明の他の実施例のブロック構成を示す略線図である。
【図１２】この発明の他の実施例における評価値の生成を説明するためのフローチャートである。
【図１３】この発明の他の実施例における評価値の生成のための構成の一例のブロック図である。
【図１４】この発明の他の実施例における評価値の説明のための略線図である。
【図１５】この発明の他の実施例による位相補償を説明するための略線図である。
【図１６】この発明を適用することができる動き補償予測符号化装置の一例を示すブロック図である。
【図１７】従来のブロックマッチング法による動きベクトル検出方法の説明のための略線図である。
【図１８】従来のブロックマッチング法による動きベクトル検出方法の説明のための略線図である。
【図１９】従来のブロックマッチング法による動きベクトル検出方法における探索範囲の説明のための略線図である。
【図２０】従来のブロックマッチング法による動きベクトル検出装置の一例のブロック図である。
【図２１】従来のブロックマッチング法による動きベクトル検出をより具体的に説明するための略線図である。
【図２２】従来の間引き法によるブロックマッチングの説明のための略線図である。
【図２３】先に提案されている誤照合を防止する手法の説明のための略線図である。
【図２４】従来の簡略化されたブロックマッチング方式の問題点を説明するための略線図である。
【符号の説明】
３  現フレームメモリ
４  参照フレームメモリ
７  代表値抽出回路
８  最大値，最小値検出回路
９  比較回路
１０  評価値計算回路
１２  最小値検出回路
【図１】
0003908793.tif 000002
【図２】
0003908793.tif 000003
【図３】
0003908793.tif 000004
【図４】
0003908793.tif 000005
【図５】
0003908793.tif 000006
【図６】
0003908793.tif 000007
【図７】
0003908793.tif 000008
【図８】
0003908793.tif 000009
【図９】
0003908793.tif 000010
【図１０】
0003908793.tif 000011
【図１１】
0003908793.tif 000012
【図１５】
0003908793.tif 000013
【図１２】
0003908793.tif 000014
【図１３】
0003908793.tif 000015
【図１４】
0003908793.tif 000016
【図１６】
0003908793.tif 000017
【図２０】
0003908793.tif 000018
【図１７】
0003908793.tif 000019
【図１８】
0003908793.tif 000020
【図１９】
0003908793.tif 000021
【図２１】
0003908793.tif 000022
【図２２】
0003908793.tif 000023
【図２３】
0003908793.tif 000024
【図２４】
0003908793.tif 000025