(57)【要約】      （修正有）【課題】比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理装置等を提供する。【解決手段】決定された位置補正量で、比較元領域の位置を補正する。補正された比較元領域と比較先領域を指定された数に分割する。分割ブロック毎に、比較元領域と比較先領域の特徴量を算出する。複数の位置をずらした後の類似距離を、両者が重複する重複領域内の各ブロックの特徴量に基づいて算出する。算出した類似距離の内、最小の類似距離に対する位置ずらしパターンと、ブロックのサイズに基づき次回の位置補正量を算出する。位置補正量が算出される毎に、前回の類似比較における分割数を増加させたブロック分割数を指定して、上記処理を再帰的に実行する再帰処理を実行する。位置補正量が算出される毎に、再帰処理を終了するか否か判定し、終了する場合、その時点の前記位置補正量を、比較元領域の位置補正量とする。【選択図】  図２
2006065407.tif 000002
【特許請求の範囲】
【請求項１】
比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理装置であって、
前記比較元画像と前記比較先画像間で比較する比較領域として、比較元比較領域と比較先比較領域を決定する決定手段と、
前記比較領域を分割するブロック分割数を指定する指定手段と、
決定された位置補正量で、前記比較元比較領域の位置を補正する補正手段と、
前記指定手段で指定されたブロック分割数で、前記補正手段で補正された比較元比較領域と前記比較先比較領域それぞれを複数ブロックに分割する分割手段と、
前記分割手段で分割されたブロック毎に、前記補正手段で補正された比較元比較領域と前記比較先比較領域の特徴量を算出する特徴量算出手段と、
前記補正手段で補正された比較元比較領域と前記比較先比較領域間の類似比較を、その比較元比較領域の位置をずらして行うための複数種類の位置ずらしパターンを記憶する記憶手段と、
前記複数種類の位置ずらしパターンそれぞれを使用して、その位置をずらした後の前記補正手段で補正された比較元比較領域と前記比較先比較領域間の類似距離を、両者が重複する重複領域内の各ブロックの特徴量に基づいて算出する類似距離算出手段と、
前記類似距離算出手段で算出した類似距離の内、最小の類似距離に対する位置ずらしパターンと、前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する位置補正量算出手段と、
前記位置補正量算出手段によって位置補正量が算出される毎に、前回の前記類似比較におけるブロック分割数を増加させたブロック分割数を前記指定手段によって指定して、前記補正手段から前記位置補正量算出手段までの各手段を再帰的に実行する再帰処理を実行手段と、
前記位置補正量算出手段によって位置補正量が算出される毎に、前記再帰処理を終了するか否かを判定する判定手段と、
前記判定手段の判定の結果、前記再帰処理を終了する場合、その時点の前記位置補正量を、前記比較元比較領域の最終的な位置補正量として確定する確定手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記補正手段による補正を行う前の段階で、前記決定手段で決定した前記比較元比較領域と前記比較先比較領域間のサイズが異なる場合、そのサイズが等しくなるように、少なくとも一方の比較領域を変倍する変倍手段を更に備える
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記確定手段で確定した位置補正量に基づいて、前記比較元比較領域と前記比較先比較領域間の差分情報を生成する生成手段を更に備える
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記補正手段による補正を行う前の段階で、前記決定手段で決定した前記比較元比較領域と前記比較先比較領域間の特徴量レベルが異なる場合、その特徴量レベルが等しくなるように、少なくとも一方の比較領域の特徴量レベルを変換するレベル変換手段を更に備える
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記特徴量算出手段は、
前記比較元比較領域と前記比較先比較領域の両者がカラー画像である場合、前記分割手段で分割されたブロック毎に、そのカラー画像中の各カラーチャネルの平均を前記特徴量として算出し、
前記比較元比較領域と前記比較先比較領域の一方がカラー画像で他方がグレースケール画像、あるいは両者がグレースケール画像である場合は、前記分割手段で分割されたブロック毎に、その画像の平均輝度を前記特徴量として算出し、
前記比較元比較領域と前記比較先比較領域の少なくとも一方が２値画像である場合、前記分割手段で分割されたブロック毎に、その２値画像の２値の過半をしめるものを特徴量として算出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記生成手段は、
前記比較元比較領域と前記比較先比較領域の両者がカラー画像である場合、前記確定手段で確定した位置補正量に基づいて、カラー画像に関する前記差分情報を生成し、
前記比較元比較領域と前記比較先比較領域の一方がカラー画像で他方がグレースケール画像、あるいは両者がグレースケール画像である場合は、前記確定手段で確定した位置補正量に基づいて、グレースケール画像に関する前記差分情報を生成し、
前記比較元比較領域と前記比較先比較領域の少なくとも一方が２値画像である場合、前記確定手段で確定した位置補正量に基づいて、２値画像に関する前記差分情報を生成する
ことを特徴とする請求項３に記載の画像処理装置。
【請求項７】
前記補正手段による補正を行う前の段階で、前記決定手段で決定した前記比較元比較領域と前記比較先比較領域間のサイズが異なる場合、そのサイズが等しくなるように、少なくとも一方の比較領域を変倍する変倍手段を更に備え、
前記生成手段は、前記確定手段で確定した位置補正量に基づいて、前記変倍手段による変倍後の前記比較元比較領域及び前記比較先比較領域間の差分情報を生成する
ことを特徴とする請求項６に記載の画像処理装置。
【請求項８】
前記複数種類の位置ずらしパターンで規定される位置ずらし方向は、水平２方向、鉛直２方向、不動の１方向の計５方向である
ことを特徴とする請求項１に記載の画像処理装置。
【請求項９】
前記複数種類の位置ずらしパターンで規定される位置ずらし方向は、水平２方向、鉛直２方向、斜め４方向、不動の１の計９方向である
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１０】
前記指定手段は、前回の前記類似比較におけるブロック分割数に対して所定定数を乗じることで、該ブロック分割数よりも大きいブロック分割数を算出するブロック分割数算出手段を備え、
前記実行手段は、前記ブロック分割数算出手段で算出したブロック分割数が上限ブロック分割数を越えない限り、前記位置補正量算出手段によって位置補正量が算出される毎に、前記ブロック分割数算出手段で算出したブロック分割数を新たなブロック分割数として更新する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１１】
前記位置補正量算出手段は、
前記類似距離算出手段で算出した類似距離の内、前記最小の類似距離の第一定数倍以内に収まる２番目に小さい類似距離が存在する場合、これらの類似距離に対する位置ずらしパターンと前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出し、
前記第一定数倍以内に収まる２番目に小さい類似距離が存在しない場合、前記最小の類似距離に対する位置ずらしパターンと前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１２】
前記指定手段は、前記ブロック分割数として、前記比較領域を水平方向に分割する水平ブロック分割数と鉛直方向に分割する鉛直ブロック分割数を指定し、
前記位置補正量算出手段は、前記水平方向に対応する横方向成分と前記鉛直方向に対応する縦方向成分からなる前記位置補正量を算出するものであり、
前回の前記類似比較における前記水平ブロック分割数に対して所定定数を乗じて得られる水平ブロック分割数が上限水平ブロック分割数を越えている場合、前記位置補正量の縦方向成分を、前記位置ずらしパターンの縦方向成分に前記鉛直ブロック分割数を乗じた値に設定し、該位置補正量の横方向成分を、該位置ずらしパターンの横方向成分の値に設定し、
前回の前記類似比較における前記鉛直ブロック分割数に対して所定定数を乗じて得られる鉛直ブロック分割数が上限鉛直ブロック分割数を越えている場合、前記位置補正量の縦方向成分を、前記位置ずらしパターンの縦方向成分の値に設定し、該位置補正量の横方向成分を、該位置ずらしパターンの横方向成分に前記水平ブロック分割数を乗じた値に設定し、
前回の前記類似比較における前記水平ブロック分割数に対して所定定数を乗じて得られる水平ブロック分割数が上限水平ブロック分割数を越えていて、かつ前記鉛直ブロック分割数に対して所定定数を乗じて得られる鉛直ブロック分割数が上限鉛直ブロック分割数を越えている場合、前記位置補正量の縦方向成分を、前記位置ずらしパターンの縦方向成分に前記鉛直ブロック分割数を乗じた値に設定し、該位置補正量の横方向成分を、該位置ずらしパターンの横方向成分に前記水平ブロック分割数を乗じた値に設定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１３】
前記判定手段は、前記指定手段で指定されたブロック分割数が上限ブロック分割数になった後の前記再帰処理の処理回数に基づいて、前記再帰処理を終了するか否かを判定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１４】
前記判定手段は、前記指定手段で指定されたブロック分割数が上限ブロック分割数になった後の前記再帰処理の処理回数と、判定時の前記位置補正量に基づいて、前記再帰処理を終了するか否かを判定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１５】
前記判定手段は、前記再帰処理の処理回数と、判定時の前記位置補正量、前記ブロック分割数及び前記最小の類似距離に基づいて、前記再帰処理を終了するか否かを判定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１６】
前記指定手段が指定するブロック分割数の上限ブロック分割数は、前記比較領域のサイズである
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１７】
前記指定手段は、前回の前記類似比較におけるブロック分割数に対して所定定数を乗じることで、該ブロック分割数よりも大きいブロック分割数を算出するブロック分割数算出手段を備え、
前記所定定数は、１．０〜２．０の間の値である
ことを特徴とする請求項１に記載の画像処理装置。
【請求項１８】
前記生成手段は、前記差分情報を、前記比較元比較領域と前記比較先比較領域間の対応する画素同士の差分画素値、前記画素同士の差分絶対画素値の累積値を比較領域内の画素数で割った値、あるいは前記比較元比較領域と前記比較先比較領域それぞれのサイズに換算した座標情報、あるいはそれらの組み合わせに基づいて生成する
ことを特徴とする請求項３に記載の画像処理装置。
【請求項１９】
前記生成手段は、前記比較元比較領域と前記比較先比較領域間の対応する画素同士の差分画素値の内、所定閾値以上の差分画素値を取得する取得手段と、
前記取得手段で取得した差分画素値を量子化する量子化手段とを備え、
前記比較元比較領域において、前記量子化手段の各量子化レベルに属する差分画素値を持つ画素を、各量子化レベル毎に異なる色で表示する画像を前記差分情報として生成する
ことを特徴とする請求項３に記載の画像処理装置。
【請求項２０】
前記生成手段は、前記比較元比較領域と前記比較先比較領域間の対応する画素同士の差分画素値の内、所定閾値以上の差分画素値を取得する取得手段とを備え、
前記比較元比較領域において、前記取得手段で取得した差分画素値に対応する画素を、所定色で表示する画像を前記差分情報として生成する
ことを特徴とする請求項３に記載の画像処理装置。
【請求項２１】
前記所定閾値は、０を含む正の値である
ことを特徴とする請求項１９または請求項２０に記載の画像処理装置。
【請求項２２】
比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理方法であって、
前記比較元画像と前記比較先画像間で比較する比較領域として、比較元比較領域と比較先比較領域を決定する決定工程と、
前記比較領域を分割するブロック分割数を指定する指定工程と、
決定された位置補正量で、前記比較元比較領域の位置を補正する補正工程と、
前記指定工程で指定されたブロック分割数で、前記補正工程で補正された比較元比較領域と前記比較先比較領域それぞれを複数ブロックに分割する分割工程と、
前記分割工程で分割されたブロック毎に、前記補正工程で補正された比較元比較領域と前記比較先比較領域の特徴量を算出する特徴量算出工程と、
前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似比較を、その比較元比較領域の位置をずらして行うための複数種類の位置ずらしパターンそれぞれを使用して、その位置をずらした後の前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似距離を、両者が重複する重複領域内の各ブロックの特徴量に基づいて算出する類似距離算出工程と、
前記類似距離算出工程で算出した類似距離の内、最小の類似距離に対する位置ずらしパターンと、前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する位置補正量算出工程と、
前記位置補正量算出工程によって位置補正量が算出される毎に、前回の前記類似比較におけるブロック分割数を増加させたブロック分割数を前記指定工程によって指定して、前記補正工程から前記位置補正量算出工程までの各工程を再帰的に実行する再帰処理を実行工程と、
前記位置補正量算出工程によって位置補正量が算出される毎に、前記再帰処理を終了するか否かを判定する判定工程と、
前記判定工程の判定の結果、前記再帰処理を終了する場合、その時点の前記位置補正量を、前記比較元比較領域の最終的な位置補正量として確定する確定工程と
を備えることを特徴とする画像処理方法。
【請求項２３】
比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理を実現するプログラムであって、
前記比較元画像と前記比較先画像間で比較する比較領域として、比較元比較領域と比較先比較領域を決定する決定工程のプログラムコードと、
前記比較領域を分割するブロック分割数を指定する指定工程のプログラムコードと、
決定された位置補正量で、前記比較元比較領域の位置を補正する補正工程のプログラムコードと、
前記指定工程で指定されたブロック分割数で、前記補正工程で補正された比較元比較領域と前記比較先比較領域それぞれを複数ブロックに分割する分割工程のプログラムコードと、
前記分割工程で分割されたブロック毎に、前記補正工程で補正された比較元比較領域と前記比較先比較領域の特徴量を算出する特徴量算出工程のプログラムコードと、
前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似比較を、その比較元比較領域の位置をずらして行うための複数種類の位置ずらしパターンそれぞれを使用して、その位置をずらした後の前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似距離を、両者が重複する重複領域内の各ブロックの特徴量に基づいて算出する類似距離算出工程のプログラムコードと、
前記類似距離算出工程で算出した類似距離の内、最小の類似距離に対する位置ずらしパターンと、前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する位置補正量算出工程のプログラムコードと、
前記位置補正量算出工程によって位置補正量が算出される毎に、前回の前記類似比較におけるブロック分割数を増加させたブロック分割数を前記指定工程によって指定して、前記補正工程から前記位置補正量算出工程までの各工程を再帰的に実行する再帰処理を実行工程のプログラムコードと、
前記位置補正量算出工程によって位置補正量が算出される毎に、前記再帰処理を終了するか否かを判定する判定工程のプログラムコードと、
前記判定工程の判定の結果、前記再帰処理を終了する場合、その時点の前記位置補正量を、前記比較元比較領域の最終的な位置補正量として確定する確定工程のプログラムコードと
を備えることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理装置及びその方法、プログラムに関するものである。
【背景技術】
【０００２】
連続的に入力される検査対象画像と参照画像とを比較して欠陥検出を行うパターン検査に関する従来技術としては、特許文献１や特許文献２が知られている。
【０００３】
特許文献１では、検査対象画像である画像信号から取得したＮ×Ｎ画素の画像信号と、メモリに記憶された参照画像である画像信号から取得したＮ×Ｎ画素の画像信号との間で、水平及び垂直方向に１画素づつあらかじめ指定した最大画素数Ｍまでシフトさせながら画像信号間の差分画像信号を算出する。さらに、加算回路でその差分画像信号の絶対値加算を行い、最小値検出回路で最小となる値を検出することにより、パターンエッジでの差異を小さくし、欠陥部のみを検出する。
【０００４】
また、特許文献２では、様々な微細なパターンが混在する被検査物から連続的に検出される電子線画像信号を基に、複数の段階（画素数で広い領域の段階と画素数で狭い領域の段階と）で位置合わせをすることによって、高精度なサブピクセル単位での位置合わせ不良を低減することによって、正規の微細なパターンの誤検出頻度を低減すると共に微細なパターン上に生じた微細な欠陥を見落としすることなく正確に検査する。
【特許文献１】特開平５−２３２０３８号公報
【特許文献２】特開２００１−２２９３５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１では、シフト範囲が広い場合には、計算コストが非常に高くなり、また、Ｎ×Ｎ画素のブロックの精度でしか、画像信号間の差異がわからないという欠点があった。
【０００６】
また、特許文献２においては、荒い解像度で位置ずらしマッチングを行い、合致度の高さとその連続性から次の解像度における位置ずらし範囲を制限して高速化と高精度化を両立している。
【０００７】
しかしながら、画素数の多い分割ブロックとする初期マッチングの段階では、画素単位のステップで、分割ブロックの位置をずらしながらマッチングを行う。そのため、ブロックサイズに近い位置ずれに対して耐性のあるマッチングを行うとすれば、広い領域のブロックの画素サイズが数十〜数百とすれば、その二乗オーダーの比較処理をこの段階で行わなければならない。この位置ずらしによるマッチングの距離の極を考慮して、次段の詳細マッチングでより制限された範囲で位置ずらしを行い詳細マッチングを行い、その差異を検出する。この場合、精度は高くなるものの、計算コストは膨大なものとなり、高速な検索は望めない。
【０００８】
本発明は上記の課題を解決するためになされたものであり、高精度にかつ効率的に、比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定することができる画像処理装置及びその方法、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の目的を達成するための本発明による画像処理装置は以下の構成を備える。即ち、
比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理装置であって、
前記比較元画像と前記比較先画像間で比較する比較領域として、比較元比較領域と比較先比較領域を決定する決定手段と、
前記比較領域を分割するブロック分割数を指定する指定手段と、
決定された位置補正量で、前記比較元比較領域の位置を補正する補正手段と、
前記指定手段で指定されたブロック分割数で、前記補正手段で補正された比較元比較領域と前記比較先比較領域それぞれを複数ブロックに分割する分割手段と、
前記分割手段で分割されたブロック毎に、前記補正手段で補正された比較元比較領域と前記比較先比較領域の特徴量を算出する特徴量算出手段と、
前記補正手段で補正された比較元比較領域と前記比較先比較領域間の類似比較を、その比較元比較領域の位置をずらして行うための複数種類の位置ずらしパターンを記憶する記憶手段と、
前記複数種類の位置ずらしパターンそれぞれを使用して、その位置をずらした後の前記補正手段で補正された比較元比較領域と前記比較先比較領域間の類似距離を、両者が重複する重複領域内の各ブロックの特徴量に基づいて算出する類似距離算出手段と、
前記類似距離算出手段で算出した類似距離の内、最小の類似距離に対する位置ずらしパターンと、前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する位置補正量算出手段と、
前記位置補正量算出手段によって位置補正量が算出される毎に、前回の前記類似比較におけるブロック分割数を増加させたブロック分割数を前記指定手段によって指定して、前記補正手段から前記位置補正量算出手段までの各手段を再帰的に実行する再帰処理を実行手段と、
前記位置補正量算出手段によって位置補正量が算出される毎に、前記再帰処理を終了するか否かを判定する判定手段と、
前記判定手段の判定の結果、前記再帰処理を終了する場合、その時点の前記位置補正量を、前記比較元比較領域の最終的な位置補正量として確定する確定手段と
を備える。
【００１０】
また、好ましくは、前記補正手段による補正を行う前の段階で、前記決定手段で決定した前記比較元比較領域と前記比較先比較領域間のサイズが異なる場合、そのサイズが等しくなるように、少なくとも一方の比較領域を変倍する変倍手段を更に備える。
【００１１】
また、好ましくは、前記確定手段で確定した位置補正量に基づいて、前記比較元比較領域と前記比較先比較領域間の差分情報を生成する生成手段を更に備える。
【００１２】
また、好ましくは、前記補正手段による補正を行う前の段階で、前記決定手段で決定した前記比較元比較領域と前記比較先比較領域間の特徴量レベルが異なる場合、その特徴量レベルが等しくなるように、少なくとも一方の比較領域の特徴量レベルを変換するレベル変換手段を更に備える。
【００１３】
また、好ましくは、前記特徴量算出手段は、
前記比較元比較領域と前記比較先比較領域の両者がカラー画像である場合、前記分割手段で分割されたブロック毎に、そのカラー画像中の各カラーチャネルの平均を前記特徴量として算出し、
前記比較元比較領域と前記比較先比較領域の一方がカラー画像で他方がグレースケール画像、あるいは両者がグレースケール画像である場合は、前記分割手段で分割されたブロック毎に、その画像の平均輝度を前記特徴量として算出し、
前記比較元比較領域と前記比較先比較領域の少なくとも一方が２値画像である場合、前記分割手段で分割されたブロック毎に、その２値画像の２値の過半をしめるものを特徴量として算出する。
【００１４】
また、好ましくは、前記生成手段は、
前記比較元比較領域と前記比較先比較領域の両者がカラー画像である場合、前記確定手段で確定した位置補正量に基づいて、カラー画像に関する前記差分情報を生成し、
前記比較元比較領域と前記比較先比較領域の一方がカラー画像で他方がグレースケール画像、あるいは両者がグレースケール画像である場合は、前記確定手段で確定した位置補正量に基づいて、グレースケール画像に関する前記差分情報を生成し、
前記比較元比較領域と前記比較先比較領域の少なくとも一方が２値画像である場合、前記確定手段で確定した位置補正量に基づいて、２値画像に関する前記差分情報を生成する。
【００１５】
また、好ましくは、前記補正手段による補正を行う前の段階で、前記決定手段で決定した前記比較元比較領域と前記比較先比較領域間のサイズが異なる場合、そのサイズが等しくなるように、少なくとも一方の比較領域を変倍する変倍手段を更に備え、
前記生成手段は、前記確定手段で確定した位置補正量に基づいて、前記変倍手段による変倍後の前記比較元比較領域及び前記比較先比較領域間の差分情報を生成する。
【００１６】
また、好ましくは、前記複数種類の位置ずらしパターンで規定される位置ずらし方向は、水平２方向、鉛直２方向、不動の１方向の計５方向である。
【００１７】
また、好ましくは、前記複数種類の位置ずらしパターンで規定される位置ずらし方向は、水平２方向、鉛直２方向、斜め４方向、不動の１の計９方向である。
【００１８】
また、好ましくは、前記指定手段は、前回の前記類似比較におけるブロック分割数に対して所定定数を乗じることで、該ブロック分割数よりも大きいブロック分割数を算出するブロック分割数算出手段を備え、
前記実行手段は、前記ブロック分割数算出手段で算出したブロック分割数が上限ブロック分割数を越えない限り、前記位置補正量算出手段によって位置補正量が算出される毎に、前記ブロック分割数算出手段で算出したブロック分割数を新たなブロック分割数として更新する。
【００１９】
また、好ましくは、前記位置補正量算出手段は、
前記類似距離算出手段で算出した類似距離の内、前記最小の類似距離の第一定数倍以内に収まる２番目に小さい類似距離が存在する場合、これらの類似距離に対する位置ずらしパターンと前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出し、
前記第一定数倍以内に収まる２番目に小さい類似距離が存在しない場合、前記最小の類似距離に対する位置ずらしパターンと前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する。
【００２０】
また、好ましくは、前記指定手段は、前記ブロック分割数として、前記比較領域を水平方向に分割する水平ブロック分割数と鉛直方向に分割する鉛直ブロック分割数を指定し、
前記位置補正量算出手段は、前記水平方向に対応する横方向成分と前記鉛直方向に対応する縦方向成分からなる前記位置補正量を算出するものであり、
前回の前記類似比較における前記水平ブロック分割数に対して所定定数を乗じて得られる水平ブロック分割数が上限水平ブロック分割数を越えている場合、前記位置補正量の縦方向成分を、前記位置ずらしパターンの縦方向成分に前記鉛直ブロック分割数を乗じた値に設定し、該位置補正量の横方向成分を、該位置ずらしパターンの横方向成分の値に設定し、
前回の前記類似比較における前記鉛直ブロック分割数に対して所定定数を乗じて得られる鉛直ブロック分割数が上限鉛直ブロック分割数を越えている場合、前記位置補正量の縦方向成分を、前記位置ずらしパターンの縦方向成分の値に設定し、該位置補正量の横方向成分を、該位置ずらしパターンの横方向成分に前記水平ブロック分割数を乗じた値に設定し、
前回の前記類似比較における前記水平ブロック分割数に対して所定定数を乗じて得られる水平ブロック分割数が上限水平ブロック分割数を越えていて、かつ前記鉛直ブロック分割数に対して所定定数を乗じて得られる鉛直ブロック分割数が上限鉛直ブロック分割数を越えている場合、前記位置補正量の縦方向成分を、前記位置ずらしパターンの縦方向成分に前記鉛直ブロック分割数を乗じた値に設定し、該位置補正量の横方向成分を、該位置ずらしパターンの横方向成分に前記水平ブロック分割数を乗じた値に設定する。
【００２１】
また、好ましくは、前記判定手段は、前記指定手段で指定されたブロック分割数が上限ブロック分割数になった後の前記再帰処理の処理回数に基づいて、前記再帰処理を終了するか否かを判定する。
【００２２】
また、好ましくは、前記判定手段は、前記指定手段で指定されたブロック分割数が上限ブロック分割数になった後の前記再帰処理の処理回数と、判定時の前記位置補正量に基づいて、前記再帰処理を終了するか否かを判定する。
【００２３】
また、好ましくは、前記判定手段は、前記再帰処理の処理回数と、判定時の前記位置補正量、前記ブロック分割数及び前記最小の類似距離に基づいて、前記再帰処理を終了するか否かを判定する。
【００２４】
また、好ましくは、前記指定手段が指定するブロック分割数の上限ブロック分割数は、前記比較領域のサイズである。
【００２５】
また、好ましくは、前記指定手段は、前回の前記類似比較におけるブロック分割数に対して所定定数を乗じることで、該ブロック分割数よりも大きいブロック分割数を算出するブロック分割数算出手段を備え、
前記所定定数は、１．０〜２．０の間の値である。
【００２６】
また、好ましくは、前記生成手段は、前記差分情報を、前記比較元比較領域と前記比較先比較領域間の対応する画素同士の差分画素値、前記画素同士の差分絶対画素値の累積値を比較領域内の画素数で割った値、あるいは前記比較元比較領域と前記比較先比較領域それぞれのサイズに換算した座標情報、あるいはそれらの組み合わせに基づいて生成する。
【００２７】
また、好ましくは、前記生成手段は、前記比較元比較領域と前記比較先比較領域間の対応する画素同士の差分画素値の内、所定閾値以上の差分画素値を取得する取得手段と、
前記取得手段で取得した差分画素値を量子化する量子化手段とを備え、
前記比較元比較領域において、前記量子化手段の各量子化レベルに属する差分画素値を持つ画素を、各量子化レベル毎に異なる色で表示する画像を前記差分情報として生成する。
【００２８】
また、好ましくは、前記生成手段は、前記比較元比較領域と前記比較先比較領域間の対応する画素同士の差分画素値の内、所定閾値以上の差分画素値を取得する取得手段とを備え、
前記比較元比較領域において、前記取得手段で取得した差分画素値に対応する画素を、所定色で表示する画像を前記差分情報として生成する。
【００２９】
また、好ましくは、前記所定閾値は、０を含む正の値である。
【００３０】
上記の目的を達成するための本発明による画像処理方法は以下の構成を備える。即ち、
比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理方法であって、
前記比較元画像と前記比較先画像間で比較する比較領域として、比較元比較領域と比較先比較領域を決定する決定工程と、
前記比較領域を分割するブロック分割数を指定する指定工程と、
決定された位置補正量で、前記比較元比較領域の位置を補正する補正工程と、
前記指定工程で指定されたブロック分割数で、前記補正工程で補正された比較元比較領域と前記比較先比較領域それぞれを複数ブロックに分割する分割工程と、
前記分割工程で分割されたブロック毎に、前記補正工程で補正された比較元比較領域と前記比較先比較領域の特徴量を算出する特徴量算出工程と、
前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似比較を、その比較元比較領域の位置をずらして行うための複数種類の位置ずらしパターンそれぞれを使用して、その位置をずらした後の前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似距離を、両者が重複する重複領域内の各ブロックの特徴量に基づいて算出する類似距離算出工程と、
前記類似距離算出工程で算出した類似距離の内、最小の類似距離に対する位置ずらしパターンと、前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する位置補正量算出工程と、
前記位置補正量算出工程によって位置補正量が算出される毎に、前回の前記類似比較におけるブロック分割数を増加させたブロック分割数を前記指定工程によって指定して、前記補正工程から前記位置補正量算出工程までの各工程を再帰的に実行する再帰処理を実行工程と、
前記位置補正量算出工程によって位置補正量が算出される毎に、前記再帰処理を終了するか否かを判定する判定工程と、
前記判定工程の判定の結果、前記再帰処理を終了する場合、その時点の前記位置補正量を、前記比較元比較領域の最終的な位置補正量として確定する確定工程と
を備える。
【００３１】
上記の目的を達成するための本発明によるプログラムは以下の構成を備える。即ち、
比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定する画像処理を実現するプログラムであって、
前記比較元画像と前記比較先画像間で比較する比較領域として、比較元比較領域と比較先比較領域を決定する決定工程のプログラムコードと、
前記比較領域を分割するブロック分割数を指定する指定工程のプログラムコードと、
決定された位置補正量で、前記比較元比較領域の位置を補正する補正工程のプログラムコードと、
前記指定工程で指定されたブロック分割数で、前記補正工程で補正された比較元比較領域と前記比較先比較領域それぞれを複数ブロックに分割する分割工程のプログラムコードと、
前記分割工程で分割されたブロック毎に、前記補正工程で補正された比較元比較領域と前記比較先比較領域の特徴量を算出する特徴量算出工程のプログラムコードと、
前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似比較を、その比較元比較領域の位置をずらして行うための複数種類の位置ずらしパターンそれぞれを使用して、その位置をずらした後の前記補正工程で補正された比較元比較領域と前記比較先比較領域間の類似距離を、両者が重複する重複領域内の各ブロックの特徴量に基づいて算出する類似距離算出工程のプログラムコードと、
前記類似距離算出工程で算出した類似距離の内、最小の類似距離に対する位置ずらしパターンと、前記ブロックのサイズに基づいて、次回の前記類似比較を行う際の前記比較元比較領域の位置を補正するための位置補正量を算出する位置補正量算出工程のプログラムコードと、
前記位置補正量算出工程によって位置補正量が算出される毎に、前回の前記類似比較におけるブロック分割数を増加させたブロック分割数を前記指定工程によって指定して、前記補正工程から前記位置補正量算出工程までの各工程を再帰的に実行する再帰処理を実行工程のプログラムコードと、
前記位置補正量算出工程によって位置補正量が算出される毎に、前記再帰処理を終了するか否かを判定する判定工程のプログラムコードと、
前記判定工程の判定の結果、前記再帰処理を終了する場合、その時点の前記位置補正量を、前記比較元比較領域の最終的な位置補正量として確定する確定工程のプログラムコードと
を備える。
【発明の効果】
【００３２】
本発明によれば、高精度にかつ効率的に、比較元画像と比較先画像間の類似比較を行うための比較領域の位置を決定することができる画像処理装置及びその方法、プログラムを提供できる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明の実施の形態について図面を用いて詳細に説明する。
【００３４】
＜装置構成＞
図１は本発明の実施形態の画像処理装置の構成例を示す図である。
【００３５】
図１において、１０１はＣＰＵであり、本実施形態の画像処理（あるいは画像検索処理）における各種演算・制御を実行する。１０２はＲＯＭであり、本画像処理装置の起動時に実行するブートプログラムや各種の固定データを格納する。
【００３６】
１０３はＲＡＭであり、ＣＰＵ１０１が処理するための制御プログラムを格納すると共に、ＣＰＵ１０１が各種制御を実行する際の作業領域を提供する。例えば、ＲＡＭ１０３は、その記憶領域に、本発明の画像処理を行うプログラムである比較判定モジュール１０３ａの他、比較元画像、比較先画像、スケーリング画像や、各種処理を行うための作業領域、処理に関する処理情報（処理用パラメータ、各種カウンタ値、閾値等）を記憶している。
【００３７】
１０４はキーボード、１０５はマウスであり、ユーザによる処理モード指定等の各種入力操作環境を提供する。１０６は外部記憶装置であり、ハードディスクやフロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ等で構成される。１０７はネットワークインタフェースを有するＮＩＣ（ネットワークインタフェースコントローラ）であり、ネットワーク上の各機器との通信を可能とする。
【００３８】
１０８は表示装置であり、ＬＣＤやＣＲＴ等で構成される。１０９は外部機器（例えば、画像入力装置１１０）を接続するためのインタフェース（Ｉ／Ｆ）である。１１０は画像入力装置であり、イメージスキャナやデジタルカメラ等で構成される。また、１１１は本画像処理装置の各種構成要素を相互に接続するバスである。
【００３９】
尚、比較元画像や比較先画像は、ＲＡＭ１０３以外に、外部記憶装置に記憶されていても良く、更には、ネットワーク上の外部機器あるいは画像入力装置１１０から取得されても良い。
【００４０】
次に、本実施形態の画像処理装置の処理概要について、図２を用いて説明する。
【００４１】
図２は本発明の実施形態の画像処理装置の処理概要を示すフローチャートである。
【００４２】
まず、ステップＳ２０１において、画像入力元（例えば、外部記憶装置１０６や画像入力装置１１０等）からメモリ（例えば、ＲＡＭ１０３）へ比較元画像と比較先画像を、それぞれ読み込む。
【００４３】
次に、ステップＳ２０２において、比較元画像と比較先画像間の比較領域として、比較元比較領域及び比較先比較領域を決定する。尚、この比較領域は、ユーザによって手動で決定しても良いし、画像処理装置が自動で決定するようにしても良い。
【００４４】
自動で決定する場合には、比較元画像と比較先画像それぞれに対して水平方向及び鉛直方向に輝度値を射影したヒストグラムを作成し、その輝度ヒストグラムの分布から、比較対象のオブジェクトの最外接矩形を取得する。この例を図３に示す。そして、この輝度ヒストグラムを閾値処理し、水平方向及び鉛直方向に閾値以上のヒストグラム区間を決定して、オブジェクトの最外接矩形を取得する。本実施形態では、この最外接矩形で規定される矩形領域を比較領域（比較範囲）として決定する。
【００４５】
次に、ステップＳ２０３において、比較元画像と比較先画像間の相似比を算出し、この相似比に基づいて、比較元画像が大きければ比較元画像に縮小処理を施して新たな比較元画像を生成し、その比較領域の座標情報も縮小処理に合わせて補正する。
【００４６】
一方、比較先画像が大きければ比較先画像に縮小処理を施して新たな比較先画像を生成し、その比較領域の座標情報も縮小処理に合わせて補正する。
【００４７】
ここで、比較元画像と比較先画像それぞれの比較領域のサイズを厳密に合わせる処理は、非常に重要である。これは、後述する比較領域のブロック分割では、比較領域を縦横複数のグリッドにブロック分割を行うが、この比較領域のサイズが異なるとブロック分割数で縦横サイズを割って１ブロックあたりのサイズを得る際に発生する剰余が異なる。
【００４８】
ここで、図４に、比較元画像と比較先画像間の比較領域の相似比が１：２の場合の剰余例を示すが、剰余の値が異なるため、比較元画像と比較先画像に同じ条件で剰余をブロックに割り振れない。そのため、このような場合には、補正位置を算出する処理の精度に大きく悪影響を与えることになる。
【００４９】
従って、比較元画像及び比較先画像を同じサイズに縮小することにより、比較先画像と比較元画像間で同じ剰余を発生させ対等な関係にすることができ、ブロック分割時の剰余が非常に悪い影響を与える問題を回避することが可能となる。
【００５０】
この縮小処理によって、比較領域のサイズは、比較元画像と比較先画像で同じサイズとなる。ここで、比較領域のサイズの内、横サイズ（横画素数）をＩｍｇＨ、比較領域の縦サイズ（縦画素数）をＩｍｇＶとする。
【００５１】
次に、ステップＳ２０４において、比較対象画像間の特徴量レベル（色数及び階調数）を特徴量レベルの低い方へ合わせるレベル変換処理を実行する。
【００５２】
具体的には、比較対象画像（比較元画像と比較先画像）の双方がカラー画像である場合、あるいは２つともグレースケール画像である場合、あるいは２つとも２値画像である場合には変換を行わない。
【００５３】
あるいは、比較対象画像がカラー画像とグレースケール画像の組み合わせである場合、カラー画像の方をグレースケール画像へ変換する。更に、あるいは、比較対象画像のいずれか片方が２値画像である場合、他方を２値画像へ変換する。
【００５４】
これにより、比較対象画像の特徴量レベル（色数及び階調数）を特徴量レベルの低い方へ合わせることが可能となる。
【００５５】
次に、ステップＳ２０５において、比較処理の初期値を設定する。
【００５６】
具体的には、比較領域の横画素数ＩｍｇＨより小さい水平方向の上限ブロック分割数Ｄｈ＿Ｍを設定し、比較領域の縦画素数ＩｍｇＶより小さい鉛直方向の上限ブロック分割数Ｄｖ＿Ｍを設定する。
【００５７】
また、水平方向及び鉛直方向における初期値ブロック分割数（Ｖｈ，Ｖｖ）には、比較領域の縦横画素数より十分小さな値を設定するが、余りに小さいと、これを利用した後述する再帰処理回数が増え、処理時間が掛かることになる。逆に、大きすぎて、比較領域を分割した１ブロックの範囲に位置ずれ量が収まらないと、原理的に位置ずれ補正処理が収束できない恐れがある。
【００５８】
従って、比較領域の精度を予測し、その誤差がブロックサイズに十分収まるような初期値ブロック分割数を設定することが好ましい。
【００５９】
また、次の比較処理に用いるブロック分割数を、現在のブロック分割数に第二定数βを乗じた値とし、処理を繰り返す毎に高い精度の位置補正値に更新してゆくが、この第二定数βは、１．０よりは大きく２．０程度を上限、好ましくは２．０に設定すると良い。
【００６０】
尚、第二定数βに小さな値を用いる程、位置補正処理の収束がより安全になるが、再帰処理回数が増え処理に時間が掛かるため、用途や目的に応じて、所望の値を設定すれば良い。
【００６１】
ステップＳ２０６において、初期化処理を実行する。
【００６２】
具体的には、Ｘ（横）方向及びＹ（縦）方向に関する位置補正量（Ｃｘ，Ｃｙ）を０に初期化し、比較領域の縦横の画素数を縦横ブロック分割数として比較処理を行った回数カウンタＫｍも０に初期化し、更に、ブロック分割数（Ｖｈ，Ｖｖ）がそれぞれ上限ブロック分割数（Ｄｈ＿Ｍ，Ｄｖ＿Ｍ）に達したことを示すフラグＦＳｈ及びフラグＦＳｖも０に初期化する。
【００６３】
ステップＳ２０７において、ステップＳ２０８〜ステップＳ２１６の再帰処理の終了条件を満足しているか否かを判定する。この終了条件とは、再帰処理回数の制御を行うためのものであるが、これの詳細については後述する。終了条件を満足している場合（ステップＳ２０７でＹＥＳ）、ステップＳ２１７に進む。一方、終了条件を満足していない場合（ステップＳ２０７でＮＯ）、ステップＳ２０８に進む。
【００６４】
ステップＳ２０８において、位置補正量（Ｃｘ，Ｃｙ）とブロック分割数（Ｖｈ，Ｖｖ）を指定し、複数種類のブロックずらしパターンを用いる比較処理を行い、次の比較処理で用いる位置補正量（Ｃｘ，Ｃｙ）と最小の類似距離Ｄｍｉｎを算出する。
【００６５】
ここで、ステップＳ２０８の比較処理の詳細について、図５を用いて説明する。
【００６６】
図５は本発明の実施形態の比較処理の詳細を示すフローチャートである。
【００６７】
ステップＳ５０１において、指定された位置補正量（Ｃｘ，Ｃｙ）で、比較元画像の比較領域の位置を補正して、その比較領域を指定されたブロック分割数（Ｖｈ，Ｖｖ）でブロック分割する。また、比較先画像の比較領域を指定されたブロック分割数（Ｖｈ，Ｖｖ）でブロック分割する。
【００６８】
尚、位置補正量（Ｃｘ，Ｃｙ）を適用する画像は、比較元画像あるいは比較先画像のどちらでも良いが、本実施形態では、比較元画像に位置補正量（Ｃｘ，Ｃｙ）を適用して位置補正を行う例で説明する。
【００６９】
ステップＳ５０２において、ブロック分割された比較領域の各ブロックの平均特徴量を算出する。
【００７０】
この算出は、比較対象画像の双方がカラー画像である場合には、カラー画像中の各カラーチャンネルの平均を平均特徴量とする。また、比較対象画像がカラー画像とグレースケール画像の組み合わせ、あるいは２つともグレースケール画像である場合には、画像中の平均輝度を平均特徴量とする。更に、比較対象画像のいずれか片方が２値画像である場合には、ブロック内の２値の過半を占める値を平均特徴量とする。
【００７１】
これにより、２つの画像の種類が異なっても、情報量の低い方に合わせて平均特徴量を算出して、両者を比較することが可能となる。
【００７２】
ステップＳ５０３において、位置ずらしパターンｉを示すカウンタｉを１に初期化する。ステップＳ５０４において、カウンタｉの値が９以下であるか否かを判定する。カウンタｉの値が９以下である場合（ステップＳ５０４でＹＥＳ）、ステップＳ５０５に進む。一方、カウンタｉの値が９より大きい場合（ステップＳ５０４でＮＯ）、ステップＳ５０８に進む。
【００７３】
尚、このステップＳ５０４の判定は、予め用意された位置ずらしパターンのそれぞれを用いた、類似比較処理の完了の是非を判定するものである。特に、本実施形態では、９種類（９方向）の位置ずらしパターンの例を説明するが、これに限定されず、任意の数（例えば、５方向）の位置ずらしパターンを使用することが可能である。
【００７４】
ここで、位置ずらしパターンの一例について、図６を用いて説明する。
【００７５】
図６は本発明の実施形態の位置ずらしパターンの一例を示す図である。
【００７６】
図６では、９個の位置ずらしパターンを示している。図６の場合は、位置ずらしパターン１〜９が、カウンタｉの値に応じて選択されることになる。
【００７７】
また、図６では、各位置ずらしパターンにおける位置ずらし方向（位置補正量）として、その単位ベクトルＶ（ｉ）＝（ｘi，ｙi）で示されている。ここで、通常、単位ベクトルとは本来、大きさ１のベクトルを示すが、位置ずらしパターン６〜９の単位ベクトルＶ（６）〜Ｖ（９）は、位置ずらしパターン２〜５の単位ベクトルＶ（２）〜Ｖ（５）を用いて合成された大きさが１ではない単位ベクトル（√２）ではあるが、説明の便宜上、位置ずらしパターン６〜９に関しても単位ベクトルと言う表現を用いる。
【００７８】
図６において、例えば、位置ずらしパターン１は、位置補正量Ｖ（１）＝（０，０）となっている。つまり、この場合は、Ｘ方向及びＹ方向への実質的な位置ずらしは発生しない。また、例えば、位置ずらしパターン９は、位置補正量Ｖ（９）＝（１，−１）となっている。この場合は、Ｘ方向へ「１」、Ｙ方向へ「−１」、比較領域の位置ずらしを行うことになる。具体的には、図７に示すように、比較元画像の比較領域の位置ずらしを行う。
【００７９】
図５の説明に戻る。
【００８０】
ステップＳ５０５において、処理対象の位置ずらしパターンｉで類似比較処理を行う。
【００８１】
具体的には、位置ずらしパターンｉによる、比較元画像の比較領域の位置ずらし後の比較元画像と比較先画像の重複部分の特徴量の差異の絶対値をブロック単位で算出し、各ブロックの差異の絶対値を累積加算する。
【００８２】
そして、この累積加算値を重複部分のブロック数で割り、１ブロックあたりの平均差異Ｄｉｆｆ（ｉ）を類似距離（類似度）として算出する。そして、これまでのｉ回の類似比較処理における類似距離（類似度）、即ち、１ブロックあたりの平均差異Ｄｉｆｆ（ｉ）の最小となる上位２位までを決定する。ここで、類似距離は、平均差異Ｄｉｆｆ（ｉ）を示すものであるので、類似距離が小さい程、類似度が高いことになる。つまり、最小の類似距離は、最高位の類似度と言い換えることができる。
【００８３】
次に、ステップＳ５０７において、カウンタｉを１インクリメントして、次の位置ずらしパターンを選択するために、ステップＳ５０４に戻る。そして、ステップＳ５０４において、カウンタｉの値が９より大きい場合（ステップＳ５０４でＮＯ）、即ち、全ての位置ずらしパターンを選択して、各位置ずらしパターンによる類似比較処理が終了した場合、ステップＳ５０８へ進む。
【００８４】
ステップＳ５０８において、ステップＳ５０６の処理によって決定された類似距離の内、最小（第１位）の類似距離を第一定数αでα倍して、これを、第２位の類似距離となる位置ずらしパターンを有効にするか否かを判定するための閾値ＴＨ１に設定する。
【００８５】
尚、定数αに関しては、１.２前後が好ましいという結果が、本発明者による実験により得られている。
【００８６】
ステップＳ５０９において、第２位の類似距離が閾値ＴＨ１未満であるか否かを判定する。閾値ＴＨ１以上である場合（ステップＳ５０９でＮＯ）、ステップＳ５１０において、最小（第１位）の類似距離となる、第１位の位置ずらしパターンｐ１と、フラグＦＳｈ及びＦＳｖから、位置補正量（Ｃｘ，Ｃｙ）を算出する。
【００８７】
ここで、位置補正量（Ｃｘ，Ｃｙ）は、以下の式（１）で算出する。
【００８８】
−−−−−          式（１）          −−−−−
Ｉｆ（ＦＳｈ≠１）
Ｃｘ  ＝  ＩｍｇＨ  ／  Ｖｈ  ＊  Ｖ（ｐ１，  ｘ）
Ｅｌｓｅ
Ｃｘ  ＝    Ｖ（ｐ１，  ｘ）
Ｉｆ（ＦＳｖ≠１）
Ｃｙ  ＝    ＩｍｇＶ  ／  Ｖｖ  ＊  Ｖ（ｐ１，  ｙ）
Ｅｌｓｅ
Ｃｙ  ＝    Ｖ（ｐ１，  ｙ）
Ｖ（ｉ，ｘ）：位置ずらしパターンｉの単位ベクトルＶ（ｉ）のｘ成分
Ｖ（ｉ，ｙ）：位置ずらしパターンｉの単位ベクトルＶ（ｉ）のｙ成分
−−−−−−−−−−−−−−−−−−−−−−−−−
式（１）において、ＩｍｇＨ／Ｖｈの項は分割ブロックの横サイズ（横画素数）を、ＩｍｇＶ／Ｖｖの項は分割ブロックの縦サイズ（縦画素数）を意味する。また、フラグＦＳｈ及びフラグＦＳｖが立っている（ＦＳｈ＝１、ＦＳｖ＝１）場合には、それぞれ水平及び鉛直方向のブロック分割数が上限ブロック分割数に達しているため、単位ベクトルの水平方向及び鉛直方向成分をそのまま使用する。
【００８９】
一方、ステップＳ５０９において、第２位の類似距離が閾値ＴＨ１未満である場合（ステップＳ５０９でＹＥＳ）、ステップＳ５１１において、最小（第１位）の類似距離となる第１位の位置ずらしパターンｐ１と、２番目（第２位）に小さい類似距離となる第２位の位置ずらしパターンｐ２と、フラグＦＳｈ及びＦＳｖから、位置補正量（Ｃｘ，Ｃｙ）を算出する。
【００９０】
ここで、位置補正量（Ｃｘ，Ｃｙ）は、以下の式（２）で算出する。
【００９１】
−−−−−          式（２）          −−−−−
Ｉｆ（ＦＳｈ≠１）
Ｃｘ＝ＩｍｇＨ／Ｖｈ＊（Ｖ（ｐ１，ｘ）＋Ｖ（ｐ２，ｘ））／２
Ｅｌｓｅ
Ｃｘ＝（Ｖ（ｐ１，ｘ）＋Ｖ（ｐ２，ｘ））／２
Ｉｆ（ＦＳｖ≠１）
Ｃｙ＝ＩｍｇＶ／Ｖｖ＊（Ｖ（ｐ１，ｙ）＋Ｖ（ｐ２，ｙ））／２
Ｅｌｓｅ
Ｃｙ＝（Ｖ（ｐ１，ｙ）＋Ｖ（ｐ２，ｙ））／２
Ｖ（ｉ，ｘ）：位置ずらしパターンｉの単位ベクトルＶ（ｉ）のｘ成分
Ｖ（ｉ，ｙ）：位置ずらしパターンｉの単位ベクトルＶ（ｉ）のｙ成分
−−−−−−−−−−−−−−−−−−−−−−−−−
式（２）において、ＩｍｇＨ／Ｖｈの項は分割ブロックの横サイズ（横画素数）を、ＩｍｇＶ／Ｖｖの項は分割ブロック縦サイズ（縦画素数）を意味する。また、式（２）において、（Ｖ（ｐ１，ｘ）＋Ｖ（ｐ２，ｘ））／２、及び（Ｖ（ｐ１，ｙ）＋Ｖ（ｐ２，ｙ））／２の項は、２つの位置ずらしパターンの単位ベクトルの平均ベクトルを意味する。更に、フラグＦＳｈ及びフラグＦＳｖが立っている場合には、それぞれ水平および鉛直方向のブロック分割数が上限ブロック分割数に達しているため、平均ベクトルの水平方向及び鉛直方向成分をそのまま使用する。
【００９２】
ここで、平均ベクトルとは、例えば、第１位の位置ずらしパターンがＶ（３）で、第２位の位置ずらしパターンがＶ（６）であるとすると、図８のようになる。
【００９３】
尚、ここで、仮に、５個の位置ずらしパターンを使用する場合、例えば、位置ずらしパターン６のようなブロックの対角成分の大きさの位置ずれ補正を行おうとしても、水平の位置ずらしパターン２及び鉛直方向の位置ずらしパターン３の平均をとると、その方向は位置ずらしパターン６と同じでも大きさが１／２になり、位置補正量の上限が低くなる。そのため、図６に示すような、９個の位置ずらしパターンを用いることが好ましい。
【００９４】
そして、ステップＳ５１２において、位置補正量（Ｃｘ，Ｃｙ）と第１位の類似距離Ｄｍｉｎを出力する。
【００９５】
図２の説明に戻る。
【００９６】
ステップＳ２０８の比較処理の終了後、ステップＳ２０９からステップＳ２１６にかけて、現在のブロック分割数をβ倍して、次の再帰処理におけるブロック分割数を算出する一連の処理を行う。
【００９７】
まず、ステップＳ２０９において、現在の水平方向及び鉛直方向のブロック分割数（Ｖｈ，Ｖｖ）をβ倍したものが、ともに上限ブロック分割数（Ｄｈ＿Ｍ，Ｄｖ＿Ｍ）を超えているか否かを判定する。上限ブロック分割数（Ｄｈ＿Ｍ，Ｄｖ＿Ｍ）を超えている場合（ステップＳ２０９でＹＥＳ）、ステップＳ２１０において、水平方向及び鉛直方向のブロック分割数（Ｖｈ，Ｖｖ）を上限ブロック分割数（Ｄｈ＿Ｍ，Ｄｖ＿Ｍ）に設定し、更に、ブロック分割数（Ｖｈ，Ｖｖ）がそれぞれ上限ブロック分割数（Ｄｈ＿Ｍ，Ｄｖ＿Ｍ）に達したことを示すフラグＦＳｈ及びＦＳｖを１に設定してフラグを立てる。更に、ステップＳ２１１において、ブロック分割数を上限ブロック分割数として処理を行う回数カウンタＫｍを１インクリメントして、ステップＳ２０７へ戻る。
【００９８】
一方、ステップＳ２０９において、現在の水平方向及び鉛直方向のブロック分割数（Ｖｈ，Ｖｖ）をβ倍したものが、ともに上限ブロック分割数（Ｄｈ＿Ｍ，Ｄｖ＿Ｍ）を超えていない場合（ステップＳ２０９でＮＯ）、ステップＳ２１２において、現在の水平のブロック分割数Ｖｈをβ倍したものが、水平方向の上限ブロック分割数Ｄｈ＿Ｍを越えているか否かを判定する。
【００９９】
水平方向の上限ブロック分割数Ｄｈ＿Ｍを超えている場合（ステップＳ２１２でＹＥＳ）、ステップＳ２１３において、水平方向のブロック分割数Ｖｈを水平方向の上限ブロック分割数Ｄｈ＿Ｍに設定し、現在の鉛直方向のブロック分割数Ｖｖをβ倍したものを新たな鉛直方向のブロック分割数Ｖｖに設定し、フラグＦＳｈを１に設定してフラグを立てる。その後、ステップＳ２０７へ戻る。
【０１００】
一方、水平方向の上限ブロック分割数Ｄｈ＿Ｍを超えていない場合（ステップＳ２１２でＮＯ）、ステップＳ２１４において、現在の鉛直方向のブロック分割数Ｖｖをβ倍したものが鉛直方向の上限ブロック分割数Ｄｖ＿Ｍを超えているか否かを判定する。鉛直方向の上限ブロック分割数Ｄｖ＿Ｍを超えている場合（ステップＳ２１４でＹＥＳ）、ステップＳ２１５において、鉛直方向のブロック分割数Ｖｖを鉛直方向の上限ブロック分割数Ｄｖ＿Ｍに設定し、現在の水平方向のブロック分割数Ｖｈをβ倍したものを新たな水平方向のブロック分割数Ｖｈに設定し、ＦＳｖを１に設定してフラグを立てる。その後、ステップＳ２０７へ戻る。
【０１０１】
一方、鉛直方向の上限ブロック分割数Ｄｖ＿Ｍを超えていない場合（ステップＳ２１４でＮＯ）、ステップＳ２１６において、現在の水平方向及び鉛直方向のブロック分割数（Ｖｈ，Ｖｖ）をβ倍したものを、新たに次の再帰処理のブロック分割数（Ｖｈ，Ｖｖ）に設定して、ステップＳ２０７へ戻る。
【０１０２】
そして、ステップＳ２０７において、再帰処理の終了条件を満足するか否かを判定する。満足しない場合（ステップＳ２０７でＮＯ）、新たな終了条件で、ステップＳ２０８以降の再帰処理を実行する。一方、満足する場合（ステップＳ２０７でＹＥＳ）、ステップＳ２１７において、最新の位置補正量（Ｃｘ，Ｃｙ）を比較元画像の比較領域へ反映して、比較元画像の比較領域の位置補正を実行して、最終的な位置補正を終了する。
【０１０３】
そして、ステップＳ２１８において、差分画像生成処理を実行する。そして、得られる差分画像は、例えば、表示装置１０８に表示される。
【０１０４】
この差分画像生成処理は、最適に位置補正を行った１対の比較対象画像間における比較領域内の差分情報（差分画像）を取得して、この差分画像の内、予め決められた閾値以上の画素値を有する画素の位置を記憶する。そして、比較元画像がカラーであればグレースケールへ変換し、グレースケール画像上に、閾値以上の画素を所定色（例えば、赤等の目立つ色）でオーバーレイ表示するものである。
【０１０５】
以下、このステップＳ２１８の差分画像生成処理の詳細について、図９を用いて説明する。
【０１０６】
図９は本発明の実施形態の差分画像生成処理の詳細を示すフローチャートである。
【０１０７】
ステップＳ９０１において、比較先画像の比較領域における画素値から比較元画像の比較領域における対応する画素値の差分値を算出し、その差分値が正の値のものだけを比較先画像の比較領域内の座標と対にして、メモリに記憶する。
【０１０８】
ここで、正の値の画像とするのは、基準画像である比較元画像のグレースケール表示を行い、その上に比較先画像には存在するが基準画像には存在しない欠陥画素を強調して表示を行うためである。
【０１０９】
ステップＳ９０２において、差分値をＱｍａｘ段階で量子化するための差分量子化テーブルと、各量子化段階に属する画素の表示色情報（設定）を読み込む。
【０１１０】
尚、カラー情報で差分画像を生成する場合と、グレースケール情報で差分画像を生成する場合とでは、差分量子化テーブルは異なるので、処理対象の画像に応じて、適切な差分量子化テーブルに切り替えて読み込む。
【０１１１】
また、表示色情報に関しては、混同が起きないように、例えば、量子化ステップが３つの場合には、
（Ｒ，Ｇ，Ｂ）＝（２５５，０，０），（０，２５５，０），（０，０，２５５）
のようにして、色相が異なる識別し易い色を選択し、この場合では、誤差が少ない場合には青、やや多い場合には緑、非常に異なる場合には赤というように、差分値に応じた差異を色で表現することが可能となる。
【０１１２】
ステップＳ９０３において、表示に用いる下限量子化レベルＱｍｉｎを指定する。ここで、この下限量子化レベルＱｍｉｎは、これをＱｍａｘと設定すれば著しく差分が大きな差分値だけを、所定色（例えば、赤）で表示することになる。
【０１１３】
ステップＳ９０４において、下限量子化レベルＱｍｉｎ以上の各量子化レベルに属する差分値を持つ画素の座標と、それらの座標を量子化レベルと対にして記憶する。ステップＳ９０５において、比較元画像をグレースケール画像で表示する。
【０１１４】
ステップＳ９０６において、処理中の量子化ステップｉをＱｍｉｎに初期化する。ステップＳ９０７において、量子化ステップｉが最大量（量子化ステップＱｍａｘ）以下であるか否かを判定する。
【０１１５】
量子化ステップｉが最大量（量子化ステップＱｍａｘ）以下である場合（ステップＳ９０７でＹＥＳ）、ステップＳ９０８において、グレースケール画像上に、量子化レベルｉに対応する座標に、量子化レベルに対応した表示色で点をプロットする。そして、ステップＳ９０９において、量子化レベルｉを１インクリメントし、次の量子化レベルに進める。
【０１１６】
一方、量子化ステップｉが最大量（量子化ステップＱｍａｘ）より大きい場合（ステップＳ９０７でＮＯ）、即ち、すべての量子化ステップｉに対する処理が終了したら、処理を終了する。
【０１１７】
この図９の処理によって、基準となる比較元画像からの比較先画像の差異を、正しい位置あわせを行った上で、直感的に判りやすくその差に応じた色で、その差異を容易に視認することが可能となる。
【０１１８】
さて、ステップＳ２０７における終了条件の判定処理に関しては、様々な方法が考えられる。以下、この判定処理のいくつかの例について、以下に説明する。
【０１１９】
図１０は本発明の実施形態の判定処理の詳細の一例を示すフローチャートである。
【０１２０】
まず、ステップＳ１００１において、ブロック分割数を比較領域のサイズとして処理を行う回数カウンタＫｍの値を読み込む。ステップＳ１００２において、ブロック分割数を比較領域サイズとして処理を行う制限回数の閾値Ｋｍ＿ＭＡＸを読み込む。
【０１２１】
ステップＳ１００３において、ＫｍがＫｍ＿ＭＡＸ以下であるか否かを判定する。ＫｍがＫｍ＿ＭＡＸ以下である場合（ステップＳ１００３でＹＥＳ）、ステップＳ１００４において、終了条件を満足しないと判定する。一方、ＫｍがＫｍ＿ＭＡＸ以下でない場合（ステップＳ１００３でＮＯ）、ステップＳ１００５において、終了条件を満足すると判定する。
【０１２２】
以上の処理によって、仮に、Ｋｍが０の段階で、位置補正処理が正しい値の近傍で収束していない状況でも、Ｋｍがある程度の大きさになるまで、ブロック分割数を比較領域サイズとする比較元画像と比較先画像（比較元比較領域と比較先比較領域）間の比較処理（図５）がその位置を微調整（補正）しながら再帰的に繰り返されるように制御することができる。これにより、Ｋｍが０より大きい段階では１ブロック１画素での位置補正も１画素単位の９方向で微調整を何度か行えるので、正しい位置補正量に収束させることを補償することが可能となる。
【０１２３】
次に、図１０の応用例について、図１１を用いて説明する。この図１１は、図１０の処理の効率性をより向上することが可能となる。
【０１２４】
図１１は本発明の実施形態の判定処理の詳細の一例を示すフローチャートである。
【０１２５】
ステップＳ１１０１において、Ｋｍおよび次の処理の位置補正量（Ｃｘ，Ｃｙ）を読み込む。ステップＳ１１０２において、ブロック分割数を比較領域のサイズとして処理を行う制限回数の閾値Ｋｍ＿ＭＡＸを読み込む。
【０１２６】
ステップＳ１１０３において、ＫｍがＫｍ＿ＭＡＸより大きいか否かを判定する。ＫｍがＫｍ＿ＭＡＸより大きい場合（ステップＳ１１０３でＹＥＳ）、ステップＳ１１０４において、終了条件を満足すると判定する。一方、ＫｍがＫｍ＿ＭＡＸ以下である場合（ステップＳ１１０５でＮＯ）、ステップＳ１１０５において、位置補正量（Ｃｘ，Ｃｙ）の水平成分と鉛直成分が共に０であり、かつＫｍが０でない（ブロック分割数を比較領域のサイズとして処理を行う段階まできている）か否かを判定する。
【０１２７】
ともに０である場合（ステップＳ１１０５でＹＥＳ）、ステップＳ１１０４において、終了条件を満足すると判定する。一方、ともに０でない場合（ステップＳ１１０５でＮＯ）、ステップＳ１１０６において、終了条件を満足しないと判定する。
【０１２８】
尚、位置補正量（Ｃｘ，Ｃｙ）の水平成分と鉛直成分が共に０となった時点で、その後も位置補正量（Ｃｘ，Ｃｙ）の水平成分と鉛直成分が共に０が続くことが原理から判っているため、図１１では、その性質を用いて処理を中断する構成となっている。
【０１２９】
次に、図１１の更なる応用例について、図１２を用いて説明する。図１２では、ブロック分割数を比較領域のサイズとして処理を行う段階まできていない状態でも、予め定められたブロック分割数に達していて、かつ最小となる類似距離が定められた閾値以下の場合に、再帰処理を終了する構成を、図１１の構成に加えたものである。
【０１３０】
図１２は本発明の実施形態の判定処理の詳細の一例を示すフローチャートである。
【０１３１】
ステップＳ１２０１において、Ｋｍおよび次の処理の位置補正量（Ｃｘ，Ｃｙ）を読み込み、更に、次の処理のブロック分割数（Ｖｈ，Ｖｖ）および最新の類似距離Ｄｍｉｎを読み込む。ステップＳ１２０２において、処理を停止可能な最低限の横ブロック分割数閾値ＶｈＴＨと縦ブロック分割数閾値ＶｖＴＨおよび、処理の停止を許可する類似距離閾値ＤｍｉｎＴＨを読み込み、更にブロック分割数を比較領域のサイズとして処理を行う制限回数の閾値Ｋｍ＿ＭＡＸを読み込む。
【０１３２】
次に、ステップＳ１２０３において、ＫｍがＫｍ＿ＭＡＸより大きいか否かを判定する。ＫｍがＫｍ＿ＭＡＸより大きい場合（ステップＳ１２０３でＹＥＳ）、ステップＳ１２０４において、終了条件を満足すると判定する。一方、ＫｍがＫｍ＿ＭＡＸ以下である場合（ステップＳ１２０３でＮＯ）、ステップＳ１２０５において、Ｋｍ＝０であるか否かを判定する。
【０１３３】
Ｋｍ＝０でない場合（ステップＳ１２０５でＮＯ）、ステップＳ１２０６において、位置補正量（Ｃｘ，Ｃｙ）の水平成分と鉛直成分が共に０である否かを判定する。ともに０である場合（ステップＳ１２０６でＹＥＳ）、ステップＳ１２０４において、終了条件を満足すると判定する。一方、共に０でない場合（ステップＳ１２０６でＮＯ）、ステップＳ１２０９において、最新の類似距離Ｄｍｉｎが類似距離閾値ＤｍｉｎＴＨ以下であるか否かを判定する。
【０１３４】
類似距離Ｄｍｉｎが類似距離閾値ＤｍｉｎＴＨ以下である場合（ステップＳ１２０９でＹＥＳ）、ステップＳ１２０４において、終了条件を満足すると判定する。一方、類似距離Ｄｍｉｎが類似距離閾値ＤｍｉｎＴＨより大きい場合（ステップＳ１２０９でＮＯ）、終了条件を満足しないと判定する。
【０１３５】
他方、ステップＳ１２０５において、Ｋｍ＝０である場合（ステップＳ１２０５でＹＥＳ）、ステップＳ１２０７において、水平方向及び鉛直方向のブロック分割数（Ｖｈ，Ｖｖ）がともに、処理を停止可能な最低限の横ブロック分割数閾値ＶｈＴＨと縦ブロック分割数閾値ＶｖＴＨ以上であるか否かを判定する。
【０１３６】
横ブロック分割数閾値ＶｈＴＨと縦ブロック分割数閾値ＶｖＴＨ未満である場合（ステップＳ１２０７でＮＯ）、ステップＳ１２０８において、終了条件を満足しないと判定する。一方、横ブロック分割数閾値ＶｈＴＨと縦ブロック分割数閾値ＶｖＴＨ以上である場合（ステップＳ１２０７でＹＥＳ）、ステップＳ１２０９に進む。
【０１３７】
従来技術では、荒い解像度で細かく位置ずらしマッチングを行い合致度の高さとその連続性から次の解像度における位置ずらし範囲を制限して高速化と高精度化を図っていた。
【０１３８】
これに対し、以上説明した実施形態では、位置ずれ補正を高精度に実現できるため、比較領域に対し、１つの解像度・階層において過度な位置ずらしマッチングを行わず、順次解析解像度を上げて、次の高い解析解像度による（前回解像度の補正）より正確な位置ずれ補正を行うと共に、位置ずれ補正値（位置補正量）の値を解像度に反比例して暫時減少させるため、解像度増加過程で位置ずれ補正値を収束させることが可能となり、従来技術に比べて、高精度な位置ずれ補正能力と高速性の両立を実現することができる。
【０１３９】
以下、本発明の特徴的な構成についてまとめると、以下のようになる。
【０１４０】
比較対象画像となる２つの画像を入力し、比較対象の２画像の比較対象領域（比較元比較領域及び比較先比較領域）を決定し、その比較領域を、指定されたブロック分割数（水平（横）方向及び鉛直（縦）方向のブロック分割数）で複数のブロックに分割する。次に、各ブロックに対して、比較領域の特徴量を算出する。比較領域の類似比較を、比較元比較了以の位置をずらして行うための複数種類の位置ずらしパターンそれぞれによって、その位置をずらし後の比較元比較領域と比較先比較領域間の類似距離を、算出した特徴量に基づいて算出する。
【０１４１】
次に、算出した類似距離の内、最小の類似距離に対する位置ずらしパターン（あるいは、その位置ずらしパターンと、最小の累積距離から得られる閾値以内に収まる２番目に小さい累積距離に対する位置ずらしパターン）と、分割されたブロックのサイズに基づいて、次回の類似比較を行う際の比較元比較領域の位置を補正する位置補正量を算出する。
【０１４２】
位置補正量が算出される毎に、前回の類似比較におけるブロック分割数よりも大きいブロック分割数を指定して、上記の処理を再帰的に実行する再帰処理を実行するとともに、位置補正量が算出される毎に、その再帰処理を終了するか否かを判定する。そして、判定の結果、再帰処理を終了する場合、その時点の位置補正量を、比較元比較領域の最終的な位置補正量として確定する。
【０１４３】
これにより、最適な位置補正量で比較元比較領域を位置補正した上で、比較先比較領域との比較を行うことができ、比較元比較領域と比較先比較領域間の差異情報（例えば、差分画像）を生成することが可能となる。
【０１４４】
ここで、比較元比較領域と比較先比較領域間のサイズが異なる場合には、ブロック分割の性質上、ブロック分割を行う前の段階で比較領域のサイズを同一（等価）にする等価処理を施しておくことが好ましい。それには、比較元画像と比較先画像間の相似比を算出し、その算出した相似比に基づいて、比較元比較領域と比較先比較領域と両者のサイズが等しくなるように、比較元比較領域と比較先比較領域の少なくとも一方を変倍（拡大／縮小）する。そして、変倍後の比較元比較領域と比較先比較領域を用いて類似比較を行うことで、厳密な類似比較を行うことができる。
【０１４５】
また、比較対象領域間の色数や階調数等の特徴量レベルが異なる場合には、同一の特徴量レベルで類似比較を行うことが好ましい。それには、特徴量の算出の前の段階で、比較対象領域間の特徴量レベルが異なる場合には、比較対象領域がカラー画像とグレースケール画像である場合は、カラー画像の方をグレースケール画像へ変換し、このグレースケール画像を特徴量算出用画像として記憶する。また、比較対象領域の少なくとも一方が２値画像である場合は、一方を２値画像へ変換し、この２値画像を特徴量算出用画像として記憶する。そして、比較対象領域の特徴量の算出時には、記憶したブロック特徴量算出用画像を用いる。
【０１４６】
また、比較対象領域間の位置合わせ処理の速度を稼ぐため、上記の処理に加えて、比較対象領域の双方がカラー画像である場合は、両者をグレースケール画像に変換し、そのグレースケール画像を特徴量算出用画像として記憶しても良い。
【０１４７】
また、ブロック毎の特徴量の算出においては、比較対象領域の双方がカラー画像である場合には、そのカラー画像の各カラーチャンネルの平均を特徴量とする。また、比較対象領域がカラー画像とグレースケール画像あるいは双方がグレースケール画像である場合は、平均輝度を特徴量とする。更に、比較対象領域の少なくとも一方が２値画像である場合は、ブロック内の２値の過半を占めるものを特徴量とする。このように構成することで、比較対象領域間の特徴量レベルの差異を吸収することが可能となる。
【０１４８】
また、比較対象領域間の差異情報の生成においては、比較対象領域の双方がカラー画像である場合は、カラー情報における差分情報を生成する。また、比較対象領域の双方がグレースケール画像あるいは一方がカラー画像で他方がグレースケール画像である場合は、グレースケール情報における差分情報を生成する。更に、比較対象領域の少なくとも一方が２値画像である場合は、２値情報における差分情報を生成する。
【０１４９】
もちろん、比較領域のサイズの等価処理を行った場合には、等価処理後の比較対象領域から差異情報を生成する。
【０１５０】
また、類似距離の算出においては、位置ずらしパターンで規定されるブロック単位の位置ずらし方向は、水平２方向、鉛直２方向、不動の１方向の計５方向を最小限とする。但し、再帰処理で、ブロック分割数を増加させながら詳細な位置補正を正確に行うための処理の収束性を安全に図るのであれば、水平２方向、鉛直２方向、斜め方向４方向、不動の１方向の計９方向とすることが好ましい。
【０１５１】
ブロック分割数の増加においては、縦方向のブロック分割数を増加させ、これが縦方向の所定の上限ブロック分割数を超えないように、そのブロック分割数の増加を制限する飽和処理を行う。同様に、横方向のブロック分割数を増加させ、これが横方向の所定の上限ブロック分割数を超えないように、そのブロック分割数の増加を制限する飽和処理を行う。ここで、縦方向及び横方向のブロック分割数を増加させた数が、縦方向及び横方向の上限ブロック分割数を超えない場合には、飽和処理を行わないで、その増加させてブロック分割数を新たに比較対象領域に適用するブロック分割数として更新する。
【０１５２】
位置補正量の算出においては、最小の類似距離の第一定数倍以内に収まる２番目に小さい累積距離となる位置ずらし方向が存在する場合は、類似距離が最小となる位置ずらし方向との平均による方向ベクトルを取得する。一方、最小の類似距離の第一定数倍以内に収まる２番目に小さい累積距離となる位置ずらし方向が存在しない場合は、最小の類似距離の方向ベクトルを取得する。
【０１５３】
そして、縦方向のブロック分割数を増加させ、これが縦方向の所定の上限ブロック分割数で飽和処理を行った場合には、位置補正量となる補正方向ベクトルの縦方向成分は、取得した方向ベクトルの縦方向成分の値に設定し、補正方向ベクトルの横方向成分は、横方向のブロック分割数に取得した方向ベクトルの横方向成分へ乗じた値を設定する。
【０１５４】
また、横方向のブロック数を増加させ、これが横方向の所定の上限ブロック分割数で飽和処理を行った場合には、位置補正量となる補正方向ベクトルの横方向成分は、取得した方向ベクトルの横方向成分の値に設定し、補正方向ベクトルの縦方向成分は、縦方向のブロック分割数を取得した方向ベクトルの縦方向成分へ乗じた値に設定する。
【０１５５】
更に、縦方向及び横方向のブロック分割数を増加させ、これらがそれぞれ縦方向及び横方向の上限ブロック分割数で飽和処理を行わなかった場合には、位置補正量となる補正方向ベクトルの縦方向及び横方法成分は、縦方向及び横方向のブロック分割数に取得した方向ベクトルの縦方向及び横方向成分それぞれ乗じた値に設定する。
【０１５６】
再帰処理の終了条件の１つには、図１０で示したように、縦方向及び横方向のブロック分割数がそれぞれ縦方向及び横方向の所定の上限ブロック分割数である状態で、所定回数分の再帰処理で実行された場合とする方法があるが、図１１で示したように、所定回数の再帰処理を行う間に、位置補正量が０となれば、位置補正が収束しているので、その時点再帰処理を終了する構成としても良い。更に、図１２で示したように、縦方向及び横方向のブロック分割数がそれぞれ縦方向及び横方向の所定の上限ブロック分割数に達し、かつその時点の類似距離の最小値が所定閾値を下回った時点で、再帰処理を終了する構成としても良い。
【０１５７】
縦方向及び横方向の上限ブロック分割数は、通常、それぞれ比較対象領域の縦方向及び横方向のサイズとすれば良いが、画像の劣化等がある場合には、平滑化作用を期待して、縦方向及び横方向サイズの整数分の一として、例えば、２画素×２画素が１つのブロックとなるブロック分割数を指定するようにしても良い。
【０１５８】
次回の類似比較におけるブロック分割数の指定は、現在のブロック分割数に定数を乗じて得ることが簡易な方法であり、この定数は、１.０より大きく望むべくは２.０程度、大きくとも３.０を超えない値を上限とする。これは、定数が大きすぎる場合には、位置補正処理が収束しづらくなるからである。
【０１５９】
差異情報の生成においては、比較対象領域のサイズの等価処理後の双方がカラー画像である場合は、カラー情報における差分情報を生成する。また、双方がグレースケール画像である場合、あるいは一方がカラー画像で他方がグレースケール画像である場合には、グレースケール情報における差分情報を生成する。更に、少なくとも一方が２値画像である場合は、２値情報における差分情報を生成する。
【０１６０】
また、差異情報とは、位置ずれ補正後の比較対象領域内の対応する画素の差分画素値や差分画素値の統計情報や差分画素値の量子化情報が挙げられる。あるいは、位置ずれ補正後の比較対象領域内の対応する画素の差分画素値の累積画素値を比較対象領域内の総画素数で割った値、即ち、１画素あたりに希釈した差異指標である。あるいは、比較対象領域のサイズの等価処理前の比較元画像と比較先画像のサイズに換算した比較対象領域の座標情報として、本発明の処理を正確な位置合わせを前提とした後工程のための前処理としても良い。更に、これらの任意の組み合わせを、差異情報としても良い。
【０１６１】
また、差分情報の生成においては、位置ずれ補正後の比較元比較領域内及び比較先比較領域内の対応する画素の差分画素値を算出して、これが所定閾値以上となる画素を判定して、該当する差分画素値を複数の量子化ステップで量子化し、その量子化レベルと位置を対にして記憶する。そして、比較元画像がカラーである場合は、グレースケール画像に変換しておき、差異を表示する量子化レベル下限を指定して、そのグレースケール画像上に量子化レベル下限以上の画素をその量子化レベル毎に異なる色で表示することにより、比較対象領域間の差異を直感的に掴むことが可能となる。
【０１６２】
また、簡易には、位置ずれ補正後の比較元比較領域内及び比較先比較領域内の対応する画素の差分画素値を算出して、これが所定閾値以上となる画素及びその位置を記憶する。そして、比較元画像がカラーである場合は、グレースケール画像へ変換し、そのグレースケール画像上に差分画素値が所定閾値以上の画素を所定色（目立つ色、例えば、赤）で表示することにより、簡便な処理で比較対象領域間の差異を直感的に掴むことが可能となる。
【０１６３】
ここで、所定閾値を、０を含む正の値とすることにより、比較元画像からの比較先画像の差異のみを所定色（目立つ色）で表示することが可能となる。
【０１６４】
また、比較元画像を基準とするのではなく、比較先画像を基準とした場合に、両者の差異情報の表示にも同様のことを実現することができる。この場合には、先の説明において、表示するグレースケール画像を比較先画像とし、位置ずれ補正後の比較元比較領域と比較先比較領域間の対応する画素同士の差分情報は、比較元比較領域内の画素値からこれに対応する比較先画像比較領域内の画素値の差分を算出すれば良い。
【０１６５】
＜他の実施形態＞
上記実施形態においては、比較元画像と比較先画像間の比較領域の相似比を算出して、比較領域の大きい画像の全体を相似比に基づき縮小処理するとともに、その比較領域の座標情報も縮小処理することで、比較元画像と比較先画像間の比較領域のサイズを合わせる例について示したが、これに限定されない。
【０１６６】
例えば、比較領域の小さい画像の全体を相似に基づき拡大処理するとともに、その比較領域の座標も拡大処理することで、比較元画像と比較先画像間の比較領域のサイズを合わせる構成としても良い。但し、この場合の拡大処理に関しては、単純な線形補間法などではなく、アフィン変換等の画質劣化の少ない方法を用いることが寛容である。
【０１６７】
つまり、本実施形態では、比較元画像と比較先画像間の比較領域のサイズの一方を変倍（拡大／縮小）することで、両者間の比較領域のサイズを合わせる。また、比較元画像と比較先画像間の比較領域のサイズの一方ではなく、比較元画像と比較先画像それぞれの比較領域が等しくなるのであれば、両者を適宜変倍するようにしても良い。
【０１６８】
また、上記実施形態においては、比較元画像と比較先画像間の特徴量レベル（色数および階調数）を特徴量レベルの低い方へ合わせて変換する例について示したが、当然、高速化のために無条件で低い特徴量レベル（色数および階調数）に両画像を変換する構成としても良い。
【０１６９】
例えば、比較元画像と比較先画像がともにカラー画像の場合には、３チャンネルの情報を処理しなければならないが、両者をグレースケール画像に変換した場合には１チャンネルの情報となり、概算で比較処理コストは１／３に減じることが可能となる。
【０１７０】
更に、上記実施形態においては、差分画像生成処理による差分画像の表示に関して、複数の量子化レベルで差異のある画素色を異ならせて、オーバーレイ表示する例について示したが、当然、単純に、位置ずれ補正後の比較元画像の比較領域内および比較先画像の比較領域内の対応する２画素の差分画素値を算出して、これらの内、予め決められた閾値以上のものをその位置に対応させて記憶し、比較元画像がカラーであればグレースケール画像へ変換し、グレースケール画像上に、差分画素値が予め決められた閾値以上の画素を所定色で表示することにより、差異を直感的に判るような表示を構成とすることもできる。
【０１７１】
また、差分画像の表示に関して、上述のような画像情報ではなく、比較処理画像の比較領域内の画素差分累積値を比較領域内の画素数で割った値を、位置画素あたりの差異の期待値として表示しても良く、もちろん両者を合わせて表示する、更に画像表示において、より視認性を高めるために、比較領域を矩形で囲む、ブリンク表示にする等の複合的な表示形態を採用して表示する構成としても良い。
【０１７２】
以上、実施形態例を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能であり、具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【０１７３】
尚、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラム（実施形態では図に示すフローチャートに対応したプログラム）を、システムあるいは装置に直接あるいは遠隔から供給し、そのシステムあるいは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される場合を含む。
【０１７４】
従って、本発明の機能処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。
【０１７５】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であっても良い。
【０１７６】
プログラムを供給するための記録媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）などがある。
【０１７７】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、該ホームページから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードすることによっても供給できる。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。
【０１７８】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせ、その鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【０１７９】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行ない、その処理によっても前述した実施形態の機能が実現され得る。
【０１８０】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【０１８１】
【図１】本発明の実施形態の画像処理装置の構成例を示す図である。
【図２】本発明の実施形態の画像処理装置の処理概要を示すフローチャートである。
【図３】本発明の実施形態の比較領域の決定方法を説明するための図である。
【図４】本発明の実施形態のブロック分割の注意点を説明するための図である。
【図５】本発明の実施形態の比較処理の詳細を示すフローチャートである。
【図６】本発明の実施形態の位置ずらしパターンの一例を示す図である。
【図７】本発明の実施形態の位置ずらしの一例を示す図である。
【図８】本発明の実施形態の位置補正量の算出方法を説明するための図である。
【図９】本発明の実施形態の差分画像生成処理の詳細を示すフローチャートである。
【図１０】本発明の実施形態の判定処理の詳細の一例を示すフローチャートである。
【図１１】本発明の実施形態の判定処理の詳細の一例を示すフローチャートである。
【図１２】本発明の実施形態の判定処理の詳細の一例を示すフローチャートである。
【符号の説明】
【０１８２】
１０１  ＣＰＵ
１０２  ＲＯＭ
１０３  ＲＡＭ
１０４  キーボード
１０５  マウス
１０６  外部記憶装置
１０７  ＮＩＣ
１０８  表示装置
１０９  Ｉ／Ｆ
１１０  画像入力装置
【図１】
2006065407.tif 000003
【図２】
2006065407.tif 000004
【図３】
2006065407.tif 000005
【図４】
2006065407.tif 000006
【図５】
2006065407.tif 000007
【図６】
2006065407.tif 000008
【図７】
2006065407.tif 000009
【図８】
2006065407.tif 000010
【図９】
2006065407.tif 000011
【図１０】
2006065407.tif 000012
【図１１】
2006065407.tif 000013
【図１２】
2006065407.tif 000014