(57)【特許請求の範囲】
【請求項１】
周期性のある模様が含まれる第１の画像と該第１の画像の比較対象となる第２の画像とを対応づける対応点を探索する対応点探索装置における対応点探索方法であって、
前記第１の画像を分割した複数のブロックからなる分割画像と前記第２の画像との類似度を画素値として持つ複数のブロックからなる類似度画像を生成する類似度画像生成工程と、
前記類似度画像生成工程により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定工程と、
前記探索範囲算定工程により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込工程と、
前記探索範囲絞込工程により絞り込まれた探索範囲に基づいて、前記第１の画像を分割した各ブロックのブロック中心の位置に対応する前記第２の画像上の対応点の位置を特定する対応点特定工程と
を含んだことを特徴とする対応点探索方法。
【請求項２】
前記類似度画像生成工程により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、各ブロックを処理する優先度を算定する優先度算定工程と、前記優先度算定工程により算定された優先度を優先度記憶部に格納する格納工程とをさらに含み、
前記探索範囲絞込工程は、
前記優先度記憶部に記憶された優先度に基づいて、前記制約範囲を隣接ブロックに対して伝搬処理するブロックの処理順序を決定する
ことを特徴とする請求項１に記載の対応点探索方法。
【請求項３】
前記類似度画像生成工程は、
前記第１の画像を複数のブロックに分割処理する分割処理工程と、
前記分割処理工程により分割処理された各ブロックと前記第２の画像との類似度をそれぞれ算定する類似度算定工程と
を含んだことを特徴とする請求項１又は２に記載の対応点探索方法。
【請求項４】
前記分割処理工程は、各ブロック内での歪みが１画素に納まるサイズからなる複数のブロックに前記第１の画像を分割処理し、
前記探索範囲絞込工程は、前記探索範囲算定工程により算定された探索範囲に対して周囲１画素加えた範囲を制約範囲とする
ことを特徴とする請求項３に記載の対応点探索方法。
【請求項５】
前記類似度算定工程は、各ブロックをテンプレートとし、該テンプレートを前記第２の画像の中心位置から所定の画素数分ずれた第１の位置に前記ブロックをテンプレートとして適用した場合に得られる類似度を類似度画像の前記第１の位置に対応する画素の画素値とし、その後このテンプレートを前記第２の画像の所定の範囲内に順次ずらしマッチングして、順次類似度を算定することを特徴とする請求項３に記載の対応点探索方法。
【請求項６】
前記探索範囲算定工程は、
前記探索範囲算定工程により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えて制約範囲を算定する制約範囲算定工程と、
前記制約範囲算定工程により算定された制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理する第１の伝搬処理工程と、
前記隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新する探索範囲更新処理工程と、
前記探索範囲更新処理工程により更新処理した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する第２の伝搬処理工程と
を含んだことを特徴とする請求項１〜５のいずれか一つに記載の対応点探索方法。
【請求項７】
周期性のある模様が含まれる第１の波形と該第１の波形の比較対象となる第２の波形とを対応づける対応点を探索する対応点探索装置における対応点探索方法であって、
前記第１の波形を分割した複数のブロックからなる分割波形と前記第２の波形との類似度を画素値として持つ複数のブロックからなる類似度波形を生成する類似度波形生成工程と、
前記類似度波形生成工程により生成された前記類似度波形を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定工程と、
前記探索範囲算定工程により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込工程と、
前記探索範囲絞込工程により絞り込まれた探索範囲に基づいて、前記第１の波形を分割した各ブロックのブロック中心の位置に対応する前記第２の波形上の対応点の位置を特定する対応点特定工程と
を含んだことを特徴とする対応点探索方法。
【請求項８】
周期性のある模様が含まれる第１の画像と該第１の画像の比較対象となる第２の画像とを対応づける対応点を探索する対応点探索装置であって、
前記第１の画像を分割した複数のブロックからなる分割画像を記憶する記憶手段と、
前記記憶手段に記憶した分割画像と前記第２の画像との類似度を画素値として持つ複数のブロックからなる類似度画像を生成する類似度画像生成手段と、
前記類似度画像生成手段により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定手段と、
前記探索範囲算定手段により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込手段と、
前記探索範囲絞込手段により絞り込まれた探索範囲に基づいて、前記第１の画像を分割した各ブロックのブロック中心の位置に対応する前記第２の画像上の対応点の位置を特定する対応点特定手段と
を備えたことを特徴とする対応点探索装置。
【請求項９】
周期性のある模様が含まれる第１の画像と該第１の画像の比較対象となる第２の画像とを対応づける対応点を探索する対応点探索装置で実行する対応点探索プログラムであって、
前記第１の画像を分割した複数のブロックからなる分割画像と前記第２の画像との類似度を画素値として持つ複数のブロックからなる類似度画像を生成する類似度画像生成手順と、
前記類似度画像生成手順により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定手順と、
前記探索範囲算定手順により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込手順と、
前記探索範囲絞込手順により絞り込まれた探索範囲に基づいて、前記第１の画像を分割した各ブロックのブロック中心の位置に対応する前記第２の画像上の対応点の位置を特定する対応点特定手順と
をコンピュータに実行させる対応点探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、入力画像と該入力画像の比較対象となる参照画像とを対応づける対応点を探索する対応点探索方法、対応点探索装置および対応点探索プログラムに関し、特に、周期性のある模様が含まれる画像間の対応付けをおこなう際に、正しい対応点を高速かつ効率良く取得することができる対応点探索方法、対応点探索装置および対応点探索プログラムに関する。
【背景技術】
【０００２】
従来、スキャナなどの画像入力装置から入力された入力画像をあらかじめ登録した参照画像と照合する際に、両画像の対応点を探索して画像間の対応付けをおこなう技術が知られている。
【０００３】
例えば、特許文献１には、参照画像と入力画像をそれぞれ分割処理して参照部分画像および入力部分画像を作成し、参照部分画像と入力部分画像の類似度を求めた類似度画像を作成し、注目類似度画像の注目画素の画素値に、隣接類似度画像の注目画素近傍の最大画素値を加算する処理を、注目画素を変えながら順次行って対応点を決定する技術が開示されている。この特許文献１によれば、局所解に陥りにくい安定した対応付け結果を高速かつ効率良く取得することが可能となる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００４−５４６８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、周期性のある模様が入力画像及び参照画像内に含まれる場合には、該入力画像及び参照画像の量子化誤差等の要因によって、正しい位置の類似度よりも周期ずれが生じた位置の類似度が大きくなってしまい、正しい対応点が求まらないという問題がある。
【０００６】
このため、周期性のある模様が画像内に含まれる場合に、いかにして正しい対応点を求めるかが重要な課題となっている。
【０００７】
本発明は、上述した従来技術による問題点を解消するためになされたものであり、周期性のある模様が含まれる画像間の対応付けを行う際に、正しい対応点を高速かつ効率良く取得することができる対応点探索方法、対応点探索装置および対応点探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するため、本発明は、周期性のある模様が含まれる第１の画像と該第１の画像の比較対象となる第２の画像とを対応づける対応点を探索する対応点探索装置における対応点探索方法であって、前記第１の画像を分割した複数のブロックからなる分割画像と前記第２の画像との類似度を画素値として持つ複数のブロックからなる類似度画像を生成する類似度画像生成工程と、前記類似度画像生成工程により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定工程と、前記探索範囲算定工程により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込工程と、前記探索範囲絞込工程により絞り込まれた探索範囲に基づいて、前記第１の画像を分割した各ブロックのブロック中心の位置に対応する前記第２の画像上の対応点の位置を特定する対応点特定工程とを含んだことを特徴とする。
【０００９】
また、本発明は、上記の発明において、前記類似度画像生成工程により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、各ブロックを処理する優先度を算定する優先度算定工程と、前記優先度算定工程により算定された優先度を優先度記憶部に格納する格納工程とをさらに含み、前記探索範囲絞込工程は、前記優先度記憶部に記憶された優先度に基づいて、前記制約範囲を隣接ブロックに対して伝搬処理するブロックの処理順序を決定することを特徴とする。
【００１０】
また、本発明は、上記の発明において、前記類似度画像生成工程は、前記第１の画像を複数のブロックに分割処理する分割処理工程と、前記分割処理工程により分割処理された各ブロックと前記第２の画像との類似度をそれぞれ算定する類似度算定工程とを含んだことを特徴とする。
【００１１】
また、本発明は、上記の発明において、前記分割処理工程は、各ブロック内での歪みが１画素に納まるサイズからなる複数のブロックに前記第１の画像を分割処理し、前記探索範囲絞込工程は、前記探索範囲算定工程により算定された探索範囲に対して周囲１画素加えた範囲を制約範囲とすることを特徴とする。
【００１２】
また、本発明は、上記の発明において、前記類似度算定工程は、各ブロックをテンプレートとし、該テンプレートを前記第２の画像の中心位置から所定の画素数分ずれた第１の位置に前記ブロックをテンプレートとして適用した場合に得られる類似度を類似度画像の前記第１の位置に対応する画素の画素値とし、その後このテンプレートを前記第２の画像の所定の範囲内に順次ずらしマッチングして、順次類似度を算定することを特徴とする。
【００１３】
また、本発明は、上記の発明において、前記探索範囲算定工程は、前記探索範囲算定工程により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えて制約範囲を算定する制約範囲算定工程と、前記制約範囲算定工程により算定された制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理する第１の伝搬処理工程と、前記隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新する探索範囲更新処理工程と、前記探索範囲更新処理工程により更新処理した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する第２の伝搬処理工程とを含んだことを特徴とする。
【００１４】
また、本発明は、周期性のある模様が含まれる第１の波形と該第１の波形の比較対象となる第２の波形とを対応づける対応点を探索する対応点探索装置における対応点探索方法であって、前記第１の波形を分割した複数のブロックからなる分割波形と前記第２の波形との類似度を画素値として持つ複数のブロックからなる類似度波形を生成する類似度波形生成工程と、前記類似度波形生成工程により生成された前記類似度波形を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定工程と、前記探索範囲算定工程により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込工程と、前記探索範囲絞込工程により絞り込まれた探索範囲に基づいて、前記第１の波形を分割した各ブロックのブロック中心の位置に対応する前記第２の波形上の対応点の位置を特定する対応点特定工程とを含んだことを特徴とする。
【００１５】
また、本発明は、周期性のある模様が含まれる第１の画像と該第１の画像の比較対象となる第２の画像とを対応づける対応点を探索する対応点探索装置であって、前記第１の画像を分割した複数のブロックからなる分割画像を記憶する記憶手段と、前記記憶手段に記憶した分割画像と前記第２の画像との類似度を画素値として持つ複数のブロックからなる類似度画像を生成する類似度画像生成手段と、前記類似度画像生成手段により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定手段と、前記探索範囲算定手段により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込手段と、前記探索範囲絞込手段により絞り込まれた探索範囲に基づいて、前記第１の画像を分割した各ブロックのブロック中心の位置に対応する前記第２の画像上の対応点の位置を特定する対応点特定手段とを備えたことを特徴とする。
【００１６】
また、本発明は、周期性のある模様が含まれる第１の画像と該第１の画像の比較対象となる第２の画像とを対応づける対応点を探索する対応点探索装置で実行する対応点探索プログラムであって、前記第１の画像を分割した複数のブロックからなる分割画像と前記第２の画像との類似度を画素値として持つ複数のブロックからなる類似度画像を生成する類似度画像生成手順と、前記類似度画像生成手順により生成された前記類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定する探索範囲算定手順と、前記探索範囲算定手順により算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて前記探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、前記探索範囲を絞り込む探索範囲絞込手順と、前記探索範囲絞込手順により絞り込まれた探索範囲に基づいて、前記第１の画像を分割した各ブロックのブロック中心の位置に対応する前記第２の画像上の対応点の位置を特定する対応点特定手順とをコンピュータに実行させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、第１の画像を分割した複数のブロックからなる分割画像と第２の画像との類似度を画素値として持つ複数のブロックからなる類似度画像を生成し、生成された類似度画像を形成する各ブロックに含まれる類似度のうちの所定の閾値を超える類似度に基づいて、対応点が存在し得る探索範囲をそれぞれ算定し、算定された探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を自ブロックに隣接する隣接ブロックに対して伝搬処理するとともに、隣接ブロックより伝搬処理された制約範囲を用いて探索範囲を更新しつつ該更新した探索範囲に対してブロック間の対応点の差異の許容量を加えた制約範囲を隣接する隣接ブロックに対して伝搬処理する処理を繰り返して、探索範囲を絞り込み、絞り込まれた探索範囲に基づいて、第１の画像を分割した各ブロックのブロック中心の位置に対応する第２の画像上の対応点の位置を特定するよう構成したので、周期性のある模様が含まれるから安定して対応点を求めることができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、本実施例１に係る対応点探索装置の構成を示す機能ブロック図である。
【図２】図２は、本実施例１で用いる参照画像および入力画像の一例を示す図である。
【図３】図３は、参照部分画像の一例を示す図である。
【図４】図４は、類似度画像の作成概念を説明するための説明図である。
【図５】図５は、図１に示した探索範囲絞込処理部の構成を示す機能ブロック図である。
【図６】図６は、優先度データの一例を示す図である。
【図７】図７は、図１に示した探索範囲絞込処理部による探索範囲の絞込処理の概念を説明するための説明図である。
【図８】図８は、参照画像の分割から参照部分画像の格納までの処理手順を示すフローチャートである。
【図９】図９は、制約範囲の伝搬処理までの処理手順を示すフローチャートである。
【図１０】図１０は、探索範囲の絞り込みの処理手順を示すフローチャートである。
【図１１】図１１は、参照画像、入力画像及び類似度画像の他の例を示す図である。
【図１２】図１２は、本実施例２に係る対応点探索装置の構成を示す機能ブロック図である。
【図１３】図１３は、参照波形、入力波形及び類似度グラフの一例を示す図である。
【図１４】図１４は、探索範囲絞込処理部による探索範囲の絞込処理の概念を説明するための説明図である。
【発明を実施するための形態】
【００１９】
以下に、添付図面を参照して、本発明に係る対応点探索方法、対応点探索装置および対応点探索プログラムの好適な実施例を詳細に説明する。なお、以下に示す実施例１では画像を処理対象とした場合を示し、実施例２では波形を処理対象とした場合を示すこととする。
【実施例１】
【００２０】
図１は、本実施例１に係る対応点探索装置１の構成を示す機能ブロック図である。同図に示す対応点探索装置１は、あらかじめ入力された参照画像を分割して複数の参照部分画像を生成しておき、入力画像が入力された場合に、各参照部分画像の中心位置に対応する入力画像上の対応点を探索する装置である。
【００２１】
従来技術のように周期性のある模様を考慮した処理を行っていない場合には、本来の正しい位置の類似度よりも周期ずれが生じた位置の類似度が大きくなってしまい、正しい対応点が正確に求まらない。このため、本対応点探索装置１では、周期性のある模様が入力画像及び参照画像内に含まれる場合であっても、正しい対応点を高速かつ効率良く取得できるように構成している。
【００２２】
具体的には、対応点探索装置１では、入力画像及び参照画像内に複数の縦線が周期性のある模様として含まれている場合に、各画像の中央付近のブロックでは周期ずれの無い対応点を求めることが難しいが、各画像の端部のブロックでは周期ずれの無い対応点を求めやすい点を考慮し、探索範囲を隣接するブロックに伝搬処理することで、正確かつ効率的に対応点を求めている。
【００２３】
具体的には、図１に示すように、この対応点探索装置１は、画像入力部１０と、分割処理部１１と、記憶部１２と、類似度画像生成処理部１３と、探索範囲絞込処理部１４と、対応点決定処理部１５とを有する。ここでは説明の便宜上その詳細な説明を省略するが、参照画像を登録する場合には、図示しないディップスイッチ等で参照画像の登録処理を行う登録モードを選択し、入力画像の対応点を求める場合には、図示しないディップスイッチ等で対応点の探索を行う処理モードを選択することになる。
【００２４】
また、この対応点探索装置１は、コンピュータの構成要素であるＣＰＵ及びメモリ等により実現することができ、具体的には、上記画像入力部１０、分割処理部１１、類似度画像生成処理部１３、探索範囲絞込処理部１４及び対応点決定処理部１５に対応するプログラムを不揮発性メモリ等に記憶しておき、電源投入時にかかるプログラムをＣＰＵ上に読み込んで実行することにより、上記の各機能部を実現することができる。
【００２５】
画像入力部１０は、参照画像および入力画像を入力する入力部である。具体的には、光学的に原稿を読み取って画像を取得するスキャナや、ネットワークから画像を取得するインターフェース部や、二次記憶装置から画像を読み出す読み出し部が該当する。登録モードで参照画像を入力した場合には、この参照画像を分割処理部１１に出力し、処理モードで入力画像を入力した場合には、この入力画像を類似度画像生成処理部１３に出力する。
【００２６】
図２（ａ）には１００×１００画素からなる参照画像２１の一例を示しており、図２（ｂ）には１００×１００画素からなる入力画像２２の一例を示している。ここでは、周期性のある模様として縦線が両画像に含まれている場合を示している。なお、この入力画像２２は、対応点の探索対象となる画像であって、歪みや変形を伴うものであっても良い。これに対して、参照画像２１は、入力画像２２の比較の対象となる画像であり、歪みなどを伴わないものであることが望ましい。
【００２７】
分割処理部１１は、画像入力部１０により入力された参照画像を参照部分画像に分割する処理部である。分割処理部１１によって分割された参照部分画像は、記憶部１２に格納される。図３は、図２（ａ）に示した参照画像２１の分割結果の一例を示す図であり、同図に示すように、ここでは１００×１００画素の参照画像２１を２５×２５画素からなる１６個の参照部分画像２１ａに分割処理した場合を示している。
【００２８】
ここで、この分割処理部１１では、各参照部分画像内での歪みが高々１画素に納まるようなサイズに分割処理する。このように、歪みが１画素に納まるようにするためには、参照部分画像の１辺を想定される最大歪の逆数にすればよい。例えば４％の局所歪に対応するためには、１／０．０４＝２５画素を１辺とする参照部分画像に分割することになる。これにより、隣り合う参照部分画像２１ａ間では対応点の差異の許容量は±１画素という仮定の下に処理を行うことができる。
【００２９】
記憶部１２は、ハードディスク装置及び不揮発性メモリ等の記憶デバイスであり、その内部に参照部分画像２１ａ、探索範囲データ１２ｂ、制約範囲データ１２ｃ及び優先度データ１２ｄを記憶する。参照部分画像２１ａは、すでに説明した通り参照画像２１を分割処理した部分画像である。
【００３０】
探索範囲データ１２ｂは、類似度画像の各ブロック内の対応点が存在し得る範囲である探索範囲を示すデータであり、制約範囲データ１２ｃは、類似度画像の隣接するブロックに伝搬処理させる制約範囲を示すデータであり探索範囲に基づいて算定される。この探索範囲及び制約範囲は、共に対応点の位置の範囲を規定するものであり、探索範囲が処理過程で絞り込まれた範囲を示すデータであるのに対して、制約範囲は、類似度画像から計算される対応点が存在する可能性のある範囲（仮説）を意味する。かかる探索範囲は、その初期値があらかじめ付与されており、制約範囲の伝搬及び適用により絞り込まれていくことになる。
【００３１】
なお、本実施例１では、各参照画像内での歪みが高々１画素に納まるようなサイズに分割処理しているので、探索範囲の左右に１画素加算した範囲が制約範囲データ１２ｃとなる。優先度データ１２ｄは、類似度画像の各ブロックの処理順序である優先度としてブロックＩＤを保持するデータである。かかる探索範囲、制約範囲及び優先度についての詳細な説明については後述する。
【００３２】
類似度画像生成処理部１３は、入力画像と参照部分画像の間の類似度を算定して、該類似度を画素値として持つ類似度画像を生成する処理部である。類似度画像は、その一辺が探索範囲（初期値）となる画像であり、対応点の移動量に対応する類似度が画素値となる。例えば、図４に示すように、探索範囲の初期値が縦（ｙ軸）横（ｘ軸）ともに±２０画素である場合には、各軸が−２０〜２０までの値を持つ類似度画像が作成されることになる。この際、移動量ｘ、ｙの時の類似度が類似度画像２３の座標(ｘ, ｙ)にプロットされる。この類似度には、例えばエッジ画像による一般化ハフ変換、正規化相関、画素値の自乗誤差などを用いることができる。
【００３３】
例えば、図４において、入力画像２２の初期対応点から左に２０画素、上に２０画素ずらした位置に参照部分画像２１ａの中心位置をテンプレートとして重ねて類似度を算定し、算定した類似度を類似度画像２３の左上端の画素の画素値とする。その後、このテンプレートをずらしながら類似度を順次求め、入力画像２２の初期対応点から右に２０画素、下に２０画素ずらした位置での類似度を求めた時点で該参照部分画像２１ａに対応する類似度画像のブロックが完成する。本実施例１では、１６個の参照部分画像２１ａが存在するため、図４に示すように、各参照部分画像２１ａに対応する１６個のブロックからなる類似度画像２３が生成されることになる。なお、この場合における類似度画像２３の各ブロックの大きさは、４１×４１（＝２０×２＋１）画素となる。
【００３４】
図１の説明に戻り、探索範囲絞込処理部１４は、類似度画像の各ブロックにおける探索範囲の絞り込みを行う処理部である。図５に示すように、かかる探索範囲絞込処理部１４は、制約範囲算定部１４ａと、優先度算定部１４ｂと、制約範囲適用部１４ｃと、制約範囲伝搬部１４ｄと、絞込処理部１４ｅとを有する。
【００３５】
制約範囲算定部１４ａは、類似度画像の各ブロックにおける類似度を示す画素値のうち所定のしきい値以上の画素値を持つ画素位置の範囲を制約範囲とする。例えば、類似度として一般化ハフ変換を用いた場合には、最も大きな画素値となるピーク値のＮ％以上の値をしきい値とすることができる。また、類似度として正規化相関を用いた場合には、類似度の値が−１〜＋１の範囲の値となるためこの点を考慮してしきい値を決定する。さらに、類似度として画素値の自乗誤差を用いた場合には、画素値が最も小さなピークを考慮してしきい値を設定する必要がある。
【００３６】
優先度算定部１４ｂは、制約範囲を適用する順序を決定するための優先度を算定する処理部である。例えば、類似度として一般化ハフ変換を用いた場合には、最も大きな画素値となるピーク値が大きな順に優先度を算定することができる。また、類似度として正規化相関を用いた場合や画素値の自乗誤差を用いた場合には、各参照部分画像の画素値の分散を用いて優先度を算定することができる。これにより、図６に示すように、制約範囲を適用するブロックのブロックＩＤが記憶部１２内の優先度データ１２ｄに格納されることになる。同図の場合には、図４に示したブロック２３ａ、ブロック２３ｃ、ブロック２３ｄ、ブロック２３ｂの順にブロックＩＤを優先度データ１２ｄに格納し、この順序で処理する場合を示している。
【００３７】
制約範囲適用部１４ｃは、類似度画像２３の注目するブロックに対して制約範囲を適用する処理部である。具体的には、制約範囲を新たな探索範囲とする。このようにして探索範囲が絞り込まれる。
【００３８】
制約範囲伝搬部１４ｄは、類似度画像の隣接するブロックに対して制約範囲を伝搬する処理部である。かかる制約範囲の伝搬を行う理由は、探索範囲が変化することに起因して、「類似度画像の隣接するブロック間では対応点の差異が±１画素である」という仮定を満たさなくなるおそれがあるからである。具体的には、制約範囲すなわち探索範囲を周囲１画素拡張して新たな制約範囲を生成し、生成した制約範囲を隣接するブロックに対して伝搬処理することになる。
【００３９】
絞込処理部１４ｅは、制約範囲算定部１４ａにより生成された制約範囲並びに隣接するブロックから伝搬処理された制約範囲に基づいて、探索範囲の絞り込みを行う処理部である。具体的には、制約範囲適用部１４ｃにより適用済みの探索範囲と近接するブロックから伝搬処理された制約範囲の重なっている範囲を算定し、これを新たな探索範囲とする。なお、所定のしきい値以上となる類似度すなわちピーク値が新たな探索範囲に入っていない場合には、新たな探索範囲の中で制約範囲を再算定し、必要に応じて優先度についても再算定する。さらに、新たな探索範囲を１画素拡張して制約範囲を求め、求めた制約範囲を隣接するブロックに伝播処理する。伝搬処理する方向は、このブロックが最初のブロックから遠ざかる方向のみでよい。例えば、右側のブロックから制約範囲の伝搬を受け付けた場合には、左側のブロックにのみ制約範囲を伝搬処理すれば良い。ただし、新たな探策範囲が元の探索範囲と比べて変更がない場合には、伝搬処理せずに終了する。このように、制約範囲の伝搬処理を繰り返すことで、周囲のブロックの探索範囲も絞り込まれることになる。
【００４０】
対応点決定処理部１５は、探索範囲の絞り込みが終了した後に、該絞り込まれた探索範囲を用いて対応点を決定する処理部である。最終的な対応点の決定は、上記の方法から制約範囲の算定方法を変更し再度処理することで行う。制約範囲の計算方法の変更とは、ピーク値が１点のみの場合はその点を制約範囲とし、複数ある場合はそれらの座標値の平均に最も近い１点を制約範囲とすることを意味する。制約範囲がただ１点を示すようにすることにより、対応点が１点決定できる。
【００４１】
次に、図１に示した探索範囲絞込処理部１４の処理概念について説明する。図７は、図１に示した探索範囲絞込処理部１４による探索範囲の絞込処理の概念を説明するための説明図である。ここでは説明の便宜上、類似度画像２３の４つのブロック２３ａ〜２３ｄのみを対象とし、探索範囲を横方向のみとする場合を示すこととする。
【００４２】
同図（ａ）に示すように、初期状態においては、類似度画像２３の４つのブロック２３ａ〜２３ｄの探索範囲は、横方向の全範囲となる。
【００４３】
ここで、図７（ｂ）に示すように、図６に示した優先度データ１２ｄにしたがってブロック２３ａを最初の処理対象として制約範囲を算定する。ブロック２３ａの類似度のうちのしきい値以上のものを考慮すると、図中に示す制約範囲３１が得られる。このため、この制約範囲３１を新たな探索範囲として適用するとともに、この探索範囲を左右１画素拡張した制約範囲３２を隣接するブロック２３ｂに伝搬処理する。これにより、ブロック２３ｂの図示した制約範囲３２が特定されるため、この制約範囲３２を新たな探索範囲として適用する。
【００４４】
その後、この探索範囲を左右１画素拡張した制約範囲３３を隣接するブロック２３ｃに伝搬処理し、この制約範囲３３をブロック２３ｃの新たな探索範囲として適用する。同様に、この探索範囲を左右１画素拡張した制約範囲３４を隣接するブロック２３ｄに伝搬処理し、この制約範囲３４をブロック２３ｄの新たな探索範囲として適用する。以上の一連の処理によって、各ブロック２３ａ〜２３ｄの探索範囲がそれぞれ絞り込まれることになる。
【００４５】
次に、図６に示した優先度データ１２ｄにしたがってブロック２３ｃを処理対象として制約範囲を算定し、図中に示す制約範囲３５が得られる。このため、この制約範囲３５を新たな探索範囲として適用するとともに、この探索範囲を左右１画素拡張した制約範囲３６を隣接するブロック２３ｂ及び２３ｄに伝搬処理する。これにより、ブロック２３ｂ及び２３ｄの図示した制約範囲３６が特定されるため、この制約範囲３６を新たな探索範囲として適用する。この時点で、図中に示したようにブロック２３ｄの探索範囲が確定する。ブロック２３ｄの所定のしきい値を超える類似度のうち、制約範囲３４及び３６を満たす類似度は一点しか存在しないからである。
【００４６】
同様に、図６に示した優先度データ１２ｄにしたがってブロック２３ｄを処理対象として制約範囲を算定しつつ制約範囲を伝搬処理し、またブロック２３ｂを処理対象として制約範囲を算定しつつ制約範囲を伝搬処理することで、各ブロックの探索範囲を絞り込むことができる。
【００４７】
次に、図１に示した対応点探索装置１による参照画像の分割から参照部分画像の格納までの処理手順について説明する。図８は、図１に示した対応点探索装置１による参照画像の分割から参照部分画像の格納までの処理手順を示すフローチャートである。ここでは、図示しないディップスイッチ等で参照画像の登録処理を行う登録モードが選択されているものとする。
【００４８】
同図に示すように、画像入力部１０から参照画像を入力すると（ステップＳ１０１）、分割処理部１１がこの参照画像を分割処理して（ステップＳ１０２）、その結果を記憶部１２内に参照部分画像２１ａとして格納する（ステップＳ１０３）。具体的には、この分割処理部１１では、分割された各参照画像内での歪みが１画素に納まるようなサイズに参照画像を分割処理することになる。
【００４９】
次に、図１に示した対応点探索装置１による制約範囲の伝搬処理までの処理手順について説明する。図９は、図１に示した対応点探索装置１による制約範囲の伝搬処理までの処理手順を示すフローチャートである。ここでは、図示しないディップスイッチ等で対応点の探索を行う処理モードが選択されているものとする。
【００５０】
同図に示すように、画像入力部１０が入力画像を入力すると（ステップＳ２０１）、類似度画像生成処理部１３が入力画像と記憶部１２に記憶した参照部分画像２１ａとの間の類似度画像を生成する（ステップＳ２０２）。
【００５１】
その後、探索範囲絞込処理部１４が、類似度画像の各ブロックについて制約範囲を算定するとともに（ステップＳ２０３）、各ブロックの優先度を算定し（ステップＳ２０４）、該ブロックＩＤを優先度として優先度データ１２ｄに登録する（ステップＳ２０５）。
【００５２】
そして、記憶部１２の優先度データ１２ｄから最初の処理対象となるブロックを特定し（ステップＳ２０６）、制約範囲を適用して探索範囲を特定する（ステップＳ２０７）。その後、この探索範囲の周囲に１画素加算して制約範囲を算定し（ステップＳ２０８）、算定した制約範囲を隣接するブロックに伝搬処理する（ステップＳ２０９）。上記ステップＳ２０６〜Ｓ２０９の処理を優先度データ１２ｄ内の処理対象ブロックが存在する間繰り返し（ステップＳ２１０；Ｙｅｓ）、優先度データ１２ｄ内の処理対象ブロックがなくなった時点で（ステップＳ２１０；Ｎｏ）、処理を終了する。
【００５３】
次に、図１に示した対応点探索装置１による探索範囲の絞り込みの処理手順について説明する。図１０は、図１に示した対応点探索装置１による探索範囲の絞り込みの処理手順を示すフローチャートである。
【００５４】
同図に示すように、探索範囲絞込処理部１４は、あるブロックの絞込処理を行う際に、このブロックに隣接する他のブロックから制約範囲が伝搬処理されたならば（ステップＳ３０１；Ｙｅｓ）、他のブロックから伝搬された制約範囲を適用して探索範囲を更新する（ステップＳ３０２）。
【００５５】
その後、この探索範囲の周囲１画素を拡張した制約範囲を隣接する他のブロックに伝搬処理し（ステップＳ３０３）、制約範囲を再度算定する（ステップＳ３０４）。なお、他のブロックから制約範囲が伝搬されない場合には（ステップＳ３０１；Ｎｏ）、そのままステップＳ３０４に移行する。
【００５６】
その結果、算定された制約範囲が前制約範囲から変化している場合には（ステップＳ３０５；Ｙｅｓ）、優先度を再度算定し（ステップＳ３０６）、記憶部１２の優先度データ１２ｄにブロックＩＤが登録済みの場合には（ステップＳ３０７；Ｙｅｓ）、優先度データ１２ｄから該当するブロックＩＤを削除して（ステップＳ３０８）、再度算定した優先度を優先度データ１２ｄに登録する（ステップＳ３０９）。なお、算定された制約範囲が前制約範囲から変化していない場合には（ステップＳ３０５；Ｎｏ）、そのまま処理を終了する。また、記憶部１２の優先度データ１２ｄにブロックＩＤが未登録である場合には（ステップＳ３０７；Ｎｏ）、ステップＳ３０９に移行する。
【００５７】
上述してきたように、本実施例１では、画像入力部１０により入力した参照画像を分割処理部１１で分割した参照部分画像２１ａを記憶部１２に記憶しておき、画像入力部１０により入力画像を入力したならば、類似度画像生成処理部１３により該入力画像と参照部分画像２１ａの類似度画像を生成し、探索範囲絞込処理部１４によって順次探索範囲を絞り込み、対応点決定処理部１５により絞り込まれた探索範囲を用いて対応点を決定するよう構成したので、周期性のある模様が含まれる画像間の対応付けをおこなう際に、正しい対応点を高速かつ効率良く取得することができる。
【００５８】
なお、上記実施例１では、参照画像を参照部分画像に分割して入力画像との間の類似度画像を生成する場合を示したが、本発明はこれに限定されるものではなく、入力画像を入力部分画像に分割して参照画像との間の類似度を生成するよう構成することもできる。
【００５９】
また、上記実施例１では、周期性のある縦線の模様が画像に含まれ、横軸方向の対応点を求める場合を示したが、同様にして周期性のある横線の模様が画像に含まれ、縦軸方向の対応点を求めることもできる。例えば、図１１（ａ）に示す参照画像４１及び図１１（ｂ）に示す入力画像４２が存在する場合には、図１１（ｃ）に示す類似度画像４３を生成し、この類似度画像４３を用いて同様の探索範囲絞込処理を行うことで、縦軸方向の対応点を求めることが可能となる。なお、縦軸及び横軸の両方向の対応点を求めることもでき、斜線を含む対応点を求めることもできる。また、探索範囲の絞り込みを、制約範囲の計算時のしきい値を段階的に厳しくしながら複数回実行することで、より周期ずれを起こしにくい対応付けを行うことも可能である。
【００６０】
さらに、上記実施例１では、探索範囲を用いて対応点を決定することとしたが、本発明はこれに限定されるものではなく、対応点を決定する際に、特開２００４−５４６８２号公報に開示される技術などを用いて、隣接するブロックの類似度の情報を累積加算することで、安定した対応付けを行うように拡張することもできる。具体的には、（１）入力画像をブロックに分割した入力部分画像と参照画像を分割した参照部分画像との間の類似度を示す類似度画像を作成する。（２）類似度画像のピーク値が一定値以上のブロックに対しピーク値が高いブロック順に、ピーク値を基準としたしきい値を設け、しきい値以上の範囲をそのブロックの対応する類似度画像の探索範囲とし、隣接するブロックに伝播し、各ブロックの探索範囲を絞込む。（３）対応点決定段階では、各類似度画像における絞り込まれた探索範囲内の画素値を、垂直方向および水平方向に再帰的に累積加算を繰り返しながら各類似度画像を更新する。（４）類似度画像のピーク値が高いブロック順に、ピーク値を取る１点のみを探索範囲とし、隣接するブロックに伝播する。最終的に探索範囲が1点となり、この位置を入力部分画像上での対応点として決定する。このように、従来よりも大局的な最適化をおこなうことで、ローカルミニマムに陥り難くなり、また累積加算を繰り返す最適化の微調整により対応付けの精度が高くなり、さらに並列分散処理が可能になるのでハードウエア化が容易となる。
【実施例２】
【００６１】
ところで、上記実施例１では、画像を処理対象とする場合を示したが、本発明はこれに限定されるものではなく「波形」を処理対象とする場合に本発明を適用することもできる。画像処理分野でもヒストグラムの対応付けなど「波形」の対応付けは有用である。このため、本実施例２では、入力波形と参照波形の対応点を探索する場合を示すこととする。
【００６２】
図１２は、本実施例２に係る対応点探索装置５０の構成を示す機能ブロック図である。同図に示す対応点探索装置５０は、あらかじめ入力された参照波形を分割して複数の参照部分波形を生成しておき、入力波形が入力された場合に、各参照部分波形の中心位置に対応する入力波形上の対応点を探索する装置である。なお、図１に示す機能部と同様の処理を行う機能部については同一符号を付すこととして、その詳細な説明を省略する。
【００６３】
図１２に示す波形入力部５１は、図１３（ａ）に示す参照波形および入力波形を入力する入力部である。この参照波形及び入力波形は、周期性のある信号を含んでおり、横軸が時間を示し縦軸が信号値を示している。参照部分波形５２は、分割処理部１１により参照波形を分割された波形である。類似度グラフ生成処理部５３は、入力波形と参照部分波形の間の類似度を算定して、該類似度を縦軸とした類似度グラフを生成する処理部であり、図示したように分割された各参照部分波形に対応する対応点を入力波形の探索範囲から絞り込む。
【００６４】
次に、図１３を用いて探索範囲絞込処理部１４が行う制約範囲の算定について説明する。図１３（ｂ）に示すように、類似度グラフの各ブロック６１〜６４について、その類似度が所定のしきい値を超える座標位置の範囲を制約範囲とする。例えば、ブロック６１の場合には、３つの類似度のピークのうちの左２つのピークがしきい値を超えているため、この２つのピークの範囲が制約範囲となる。同様に、ブロック６２の場合には、３つの類似度のピーク全てがしきい値を超えているため、３つのピークの範囲が制約範囲となる。
【００６５】
次に、図１４を用いて探索範囲絞込処理部１４が行う探索範囲の絞込処理について説明する。ここでは、優先度データ１２ｄ内に、ブロック６１、ブロック６４、ブロック６２、ブロック６３の順序でブロックＩＤが格納されているものとする。
【００６６】
まず、ブロック６１が最初の処理対象となるため、該ブロック６１の制約範囲を適用し、該制約範囲を新たな探索範囲とする。そして、この探索範囲を拡張して新たな制約範囲を算定し、算定した制約範囲をブロック６２に伝搬処理する。ブロック６２を処理する際に、この制約範囲を適用して探索範囲を特定し、該探索範囲を拡張して新たな制約範囲を算定し、算定した制約範囲をブロック６３に伝搬処理する。同様に、ブロック６３を処理する際に、この制約範囲を適用して探索範囲を特定し、該探索範囲を拡張して新たな制約範囲を算定し、算定した制約範囲をブロック６４に伝搬処理する。
【００６７】
その結果、ブロック６４においては、３つのピークのうちの真ん中に位置するピークのみが新たな探索範囲に所在するため、このピークの位置を探索範囲として確定する。その後、同様にしてブロック６４から順次制約範囲を隣接するブロックに伝搬処理する。これにより、ブロック６２においては、３つのピークのうちの真ん中に位置するピークのみが全ての探索範囲内に所在するため、このピークの位置を探索範囲として確定する。
【００６８】
その後、ブロック６２を処理する際に、制約範囲を隣接するブロック６１及び６３に伝搬し、これによりブロック６１及び６３の制約範囲が確定する。なお、ブロック６３においては、制約範囲に変化がないため、伝搬処理を停止している。
【００６９】
上述してきたように、本実施例２によれば、波形入力部５１により入力した参照波形を分割処理部１１で分割した参照部分波形５２を記憶部１２に記憶しておき、波形入力部５１により入力波形を入力したならば、類似度グラフ生成処理部５３により該入力波形と参照部分波形５２の類似度グラフを生成し、探索範囲絞込処理部１４によって順次探索範囲を絞り込み、対応点決定処理部１５により絞り込まれた探索範囲を用いて対応点を決定するよう構成したので、周期性のある信号が含まれる波形間の対応付けをおこなう際に、正しい対応点を高速かつ効率良く取得することができる。
【産業上の利用可能性】
【００７０】
以上のように、本発明に係る対応点探索方法、対応点探索装置および対応点探索プログラムは、周期性のある模様が含まれる画像間の対応付けを行う場合に適している。
【符号の説明】
【００７１】
１    対応点探索装置
１０    画像入力部
１１    分割処理部
１２    記憶部
１２ｂ    探索範囲データ
１２ｃ    制約範囲データ
１２ｄ    優先度データ
１３    類似度画像生成処理部
１４    探索範囲絞込処理部
１４ａ    制約範囲算定部
１４ｂ    優先度算定部
１４ｃ    制約範囲適用部
１４ｄ    制約範囲伝搬部
１４ｅ    絞込処理部
１５    対応点決定処理部
２１    参照画像
２１ａ    参照部分画像
２２    入力画像
２３    類似度画像
【図１】
0005856888.tif 000002
【図２】
0005856888.tif 000003
【図３】
0005856888.tif 000004
【図４】
0005856888.tif 000005
【図５】
0005856888.tif 000006
【図６】
0005856888.tif 000007
【図７】
0005856888.tif 000008
【図８】
0005856888.tif 000009
【図９】
0005856888.tif 000010
【図１０】
0005856888.tif 000011
【図１１】
0005856888.tif 000012
【図１２】
0005856888.tif 000013
【図１３】
0005856888.tif 000014
【図１４】
0005856888.tif 000015