(57)【要約】【課題】画像同士の位置合わせや重ね合わせをのために使用するテンプレートパターンを、見本画像の中から切り出したパターンから選択する方法において、いくつかあるテンプレート候補のうち、最適なものを自動的に判断する方法および装置を提供することを課題とする。【解決方法】見本画像から切出したサンプルパターンの（Ｉ，Ｊ）成分が０か１かに応じて「０行列」または「１行列」の（Ｉ，Ｊ）成分の値を１増すことによって、サンプルパターンのパターン要素の出現度合を示す１行列および０行列を作成し、様々なサンプルパターンの重要度をこの１行列、０行列に従って所定の計算式により求めることにより重要度を決定し、重要度最大のサンプルパターンをテンプレートパターンとして決める方法により課題を解決する。【選択図】  図５
2004246448.tif 000002
【特許請求の範囲】
【請求項１】
画像同士の位置合わせや重ね合せを行うために、画像から位置合わせを行う特徴的な部分をテンプレートパターンとして特定して抽出するテンプレートパターンの選択方法であって、
パターン照合ウインドウのサイズおよびテンプレート候補の探査間隔を指定する第１のステップ、
対象画像データを指定された前記探査間隔で、指定された前記パターン照合ウインドウサイズで切出して繰返し読込み、切出した画像データを２値化して得られるサンプルパターンの（Ｉ，Ｊ）成分が０ならば、前記パターン照合ウインドウサイズに応じて定義される「０行列」の（Ｉ，Ｊ）成分の値を１増し、パターン照合ウインドウの（Ｉ，Ｊ）成分が１ならば、前記パターン照合ウインドウサイズに応じて定義される「１行列」の（Ｉ，Ｊ）成分の値を１増することにより、対象画像についての１行列および０行列を作成する第２のステップ、
得られた１行列および０行列のデータに基づき所定の計算方法により対象画像についてのサンプルパターン毎の重要度を計算し、最も重要度が高いサンプルパターンをテンプレートパターンとして決定する第３のステップ、
を順に実行することにより最適なテンプレートパターンを選択する方法。
【請求項２】
前記第３のステップにおいて、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列の（Ｉ，Ｊ）成分の値の逆数を、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列の（Ｉ，Ｊ）成分の値の逆数をとり、全ての（Ｉ，Ｊ）成分に対応するこの値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定する請求項１に記載のテンプレートパターンの選択方法。
【請求項３】
前記第３のステップにおいて、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列の（Ｉ，Ｊ）成分の値の逆数をｍ乗した値をとり、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列の（Ｉ，Ｊ）成分の値の逆数をｍ乗した値をとり、全ての（Ｉ，Ｊ）成分に対応するこの値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定する請求項１に記載のテンプレートパターンの選択方法。但しｍは任意に定めた数とする。
【請求項４】
前記第３のステップにおいて、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列の（Ｉ，Ｊ）成分の値を、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列の（Ｉ，Ｊ）成分の値をとりこれをｋとおく時、全ての（Ｉ，Ｊ）成分に対応する  −ｌｏｇ２（ｋ／Ｎ）の値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定する請求項１に記載のテンプレートパターンの選択方法。但しＮはカウントしたサンプルパターンの数とする。
【請求項５】
画像同士の位置合わせや重ね合せを行うために、画像から位置合わせを行う特徴的な部分をテンプレートパターンとして特定して抽出するテンプレート自動選択装置であって、パターン照合ウインドウのサイズおよびテンプレート候補の探査間隔を指定する入力手段と、対象画像データを記憶する画像データ記憶部と、前記パターン照合ウインドウサイズに従って定義される「１行列」および「０行列」の成分の値をそれぞれの行列の（Ｉ，Ｊ）成分に応じたアドレスに記録する１行列記憶部および０行列記憶部と、前記画像データ記憶部に収納されている対象画像データを指定された前記探査間隔で、指定された前記パターン照合ウインドウサイズで切出して繰返し読込み、切出した画像データを２値化して得たサンプルパターンの（Ｉ，Ｊ）成分が０ならば、前記０行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスの値を１増し、パターン照合ウインドウの（Ｉ，Ｊ）成分が１ならば、前記１行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスの値を１増することにより、対象画像についての１行列および０行列を作成する１行列０行列作成手段と、得られた１行列および０行列のデータに基づき計算される対象画像についてのサンプルパターン毎の重要度から最適なテンプレートパターンを決定するテンプレート選択手段と、選択したテンプレートパターンを記憶するテンプレート記憶部と、を具備して構成されることを特徴とするテンプレート自動選択装置。
【請求項６】
前記テンプレート選択手段は、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスに記録された値の逆数を、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスに記録された値の逆数をとり、全ての（Ｉ，Ｊ）成分に対応するこの値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定する請求項５に記載のテンプレート自動選択装置。
【請求項７】
前記テンプレート選択手段は、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスに記録された値の逆数をｍ乗した値を、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスに記録された値の逆数をｍ乗した値をとり、全ての（Ｉ，Ｊ）成分に対応するこの値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定する請求項５に記載のテンプレート自動選択装置。但しｍは任意に定めた数とする。
【請求項８】
前記テンプレート選択手段は、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスに記録された値を、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスに記録された値をとりこれをｋとおく時、全ての（Ｉ，Ｊ）成分に対応する  −ｌｏｇ２（ｋ／Ｎ）の値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定する請求項５に記載のテンプレート自動選択装置。但しＮはカウントしたサンプルパターンの数とする。
【請求項９】
コンピュータに組込むことにより、コンピュータを請求項５から請求項８に記載のいずれかのテンプレート自動選択装置として動作させる一連の命令を記述したコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータで作成された複数の画像データの位置合わせ、重ね合わせ等の処理を行うためのパターンマッチングにおいて、対象画像から最適と思われるテンプレートを選択する際に有効な方法に関するものである。
【０００２】
【従来の技術】
一般にパターンマッチングを行うために必要なテンプレートの選択は、オペレータが手動で行っていた。
【０００３】
【発明が解決しようとする課題】
そこで、本発明では対象画像から自動的に最適なテンプレートを切り出す方法を提供することを課題とする。
【０００４】
【課題を解決するための手段】
課題を解決するための第１の発明は、画像同士の位置合わせや重ね合せをを行うために、見本とする画像から位置合わせを行うための特徴的な部分をテンプレートパターンとして特定して抽出するテンプレートパターンの選択方法であって、
パターン照合ウインドウのサイズおよびテンプレート候補の探査間隔を指定する第１のステップ、
対象画像データを指定された前記探査間隔で、指定された前記パターン照合ウインドウサイズで切出して繰返し読込み、切出した画像データを２値化して得られるサンプルパターンの（Ｉ，Ｊ）成分が０ならば、前記パターン照合ウインドウサイズに応じて定義される「０行列」の（Ｉ，Ｊ）成分の値を１増し、パターン照合ウインドウの（Ｉ，Ｊ）成分が１ならば、前記パターン照合ウインドウサイズに応じて定義される「１行列」の（Ｉ，Ｊ）成分の値を１増することにより、対象画像についての１行列および０行列を作成する第２のステップ、
得られた１行列および０行列のデータに基づき所定の計算方法により対象画像についてのサンプルパターン毎の重要度を計算し、最も重要度が高いサンプルパターンをテンプレートパターンとして決定する第３のステップ、
を順に実行することにより最適なテンプレートパターンを選択する方法である。
【０００５】
ここでサンプルパターン毎の重要度とは、そのパターンが他のサンプルパターンのどれとも似ていない度合、すなわち希少なパターン要素を有している度合を示す指標である。ありふれたパターン要素を含んだサンプルパターンは、テンプレートとして用いた時、位置合わせや重ね合せの間違いを生じ易いためテンプレートパターンとしては相応しくないからである。図２は、良いテンプレートパターンとそうでないパターンを説明する図である。左側の１０×１０画素の２値画像に対して、２×２の照合ウインドウを使う時、テンプレートパターンとして何が最適化を説明するものである。右側に示す４種類のサンプルパターン（イ）〜（ニ）のうち、パターン（イ）がテンプレートパターンとして最適であるとしている。それは、左側の２値画像においてパターン（イ）が出現する位置はただ一通りしかないからである。逆に例えばパターン（ニ）をテンプレートとして用いると、そのパターンと一致するパターンは左側の２値画像において多数箇所あるので位置合わせができない。
【０００６】
前記第３のステップの重要度の計算式は幾つかのバリエーションがあり、どれを用いてもよい。例えば、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列の（Ｉ，Ｊ）成分の値の逆数を、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列の（Ｉ，Ｊ）成分の値の逆数をとり、全ての（Ｉ，Ｊ）成分に対応するこの値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定してもよい。
【０００７】
あるいは、前記第３のステップにおいて、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列の（Ｉ，Ｊ）成分の値の逆数をｍ乗した値をとり、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列の（Ｉ，Ｊ）成分の値の逆数をｍ乗した値をとり、全ての（Ｉ，Ｊ）成分に対応するこの値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定してもよい。但しｍは任意に定めた数とする。
【０００８】
あるいは、前記第３のステップにおいて、サンプルパターンの（Ｉ，Ｊ）成分が０ならば０行列の（Ｉ，Ｊ）成分の値を、サンプルパターンの（Ｉ，Ｊ）成分が１ならば１行列の（Ｉ，Ｊ）成分の値をとりこれをｋとおく時、全ての（Ｉ，Ｊ）成分に対応する  −ｌｏｇ２（ｋ／Ｎ）の値の総和を計算することによりそのサンプルパターンの重要度を決定し、最大の重要度を与えるサンプルパターンを、求めるテンプレートパターンとして決定してもよい。但しＮはカウントしたサンプルパターンの数とする。
【０００９】
課題を解決するための第２の発明は、画像同士の位置合わせや重ね合せを行うために、画像から位置合わせを行う特徴的な部分をテンプレートパターンとして特定して抽出するための第１の発明にかかる方法を利用したテンプレート自動選択装置であって、パターン照合ウインドウのサイズおよびテンプレート候補の探査間隔を指定する入力手段と、対象画像データを記憶する画像データ記憶部と、前記パターン照合ウインドウサイズに従って定義される「１行列」および「０行列」の成分の値をそれぞれの行列の（Ｉ，Ｊ）成分に応じたアドレスに記録する１行列記憶部および０行列記憶部と、前記画像データ記憶部に収納されている対象画像データを指定された前記探査間隔で、指定された前記パターン照合ウインドウサイズで切出して繰返し読込み、切出した画像データを２値化して得たサンプルパターンの（Ｉ，Ｊ）成分が０ならば、前記０行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスの値を１増し、パターン照合ウインドウの（Ｉ，Ｊ）成分が１ならば、前記１行列記憶部の（Ｉ，Ｊ）成分に応じたアドレスの値を１増すことにより、対象画像についての１行列および０行列を作成する１行列０行列作成手段と、得られた１行列および０行列のデータに基づき計算される対象画像についてのサンプルパターン毎の重要度から最適なテンプレートパターンを決定するテンプレート選択手段と、選択したテンプレートパターンを記憶するテンプレート記憶部と、を具備して構成されることを特徴とするテンプレート自動選択装置である。
【００１０】
前記テンプレート選択手段は、サンプルパターン毎の重要度を計算する機能を、第１の発明に係るテンプレート選択方法において利用可能な重要度の計算方法のいずれかを用いて構成することができる。
【００１１】
課題を解決するための第３の発明は、コンピュータに組込むことにより、コンピュータを第２の発明に係るテンプレート自動選択装置として動作させる一連の命令を記述したコンピュータプログラムである。
【００１２】
【発明の実施の形態】
以下、添付図面を参照しつつ、本発明の実施の形態を説明してゆく。図１は、本発明の方法の概略を説明するフローチャートである。以下、図１に沿って本発明の選択方法の手順を説明するが、適宜理解し易いように具体例を説明する他の図をも参照して説明する。
【００１３】
まず、対象画像に対して、位置合わせや重ね合せをデジタル的に行うための、対象画像の部分と照合させるテンプレートのサイズ、すなわち、パターン照合のためのウインドウのサイズ（画素数）を決定する（Ｓ１）。ここでは高さをＨ（画素）、幅をＷ（画素）としておく。次に、対象画像の中から、どれくらいの間隔で、対象画像の部分をテンプレートパターンの候補としてのサンプルとするかを決める探査間隔（縦方向、横方向）を決定する（Ｓ２）。一般的にこの間隔は、Ｈ（Ｗ）の１／１０からＨ（Ｗ）と等しい画素数とする。
【００１４】
パターン照合のためのウインドウサイズと探査間隔が求まれば、実際に、対象画像からウインドウサイズ単位で探査間隔ごとに画像を切出し、その画像のパターンの１つ１つを最終的に選定されるテンプレートパターンの候補として、最適なものを選択する処理を進めてゆくことになるが、その前にウインドウサイズと等しいサイズのＨ行Ｗ列の２つの行列「０行列」「１行列」を表す記憶領域を確保し、それらの行列の成分値を０（零）に初期化しておく（Ｓ３）。
【００１５】
まず、対象画像から、その初期位置から照合ウインドウサイズで切取られる画像データを読み出し、これを２値化する。これが１つのテンプレートパターンのサンプルである（Ｓ４）。サンプルパターンはＨ行Ｗ列の２値の行列と考えることができる。そこで、この行列の（ｉ、ｊ）成分が１ならば、１行列の（ｉ、ｊ）成分の値に１加え、この行列の（ｉ、ｊ）成分が０ならば、０行列の（ｉ、ｊ）成分の値に１を加える（Ｓ５）。ステップＳ４、Ｓ５を対象画像データから探査間隔ずつずらして得られる全てのサンプルパターンに対して繰り返す（Ｓ６、Ｓ７）。その結果、対象画像データについての「０行列」「１行列」が得られる。サンプルパターンをカウントする回数をＮとすると「０行列」の（ｉ、ｊ）と「１行列」の（ｉ、ｊ）の和は必ずＮになるという関係がある。
【００１６】
次に、得られた「０行列」「１行列」を用いて、サンプルパターンの中から最も適したものをテンプレートパターンとして選択する。そのために、各サンプルパターンごとに「０行列」「１行列」を用いて、所定の計算式により重要度を計算する（Ｓ８）。テンプレートに相応しいのは、他のサンプルパターンのどれとも似ていない、希少なパターンを持ったものであるという考え方に基づき、各サンプルパターンについて、それがどれだけ希少なパターンかを示す重要度を計算する。
【００１７】
図３に簡単な具体例を示す。図３で（Ａ）は対象画像を示す。（Ｂ）は対象画像を２値化した結果の２値データである。（Ｃ）は、照合ウインドウサイズを２画素×２画素、探査間隔を縦横ともに２画素とした場合の、全てのサンプルパターンを示している。この例の場合、Ｎ＝２５となる。（Ｄ）は、サンプルパターンの出現頻度を示している。図４は、図３（Ｄ）から得られる０行列および１行列を示したものである。照合ウインドウサイズが２画素×２画素なので０行列および１行列も２画素×２画素のサイズである。１行列の（１、１）成分は７となっているが、これは上記ステップＳ４の照合ウインドウにおいて（１、１）成分が１となるサンプルパターンが計７回あったからである。また、０行列の（２、２）成分は２５となっているが、これは上記ステップＳ４の照合ウインドウにおいて（２、２）成分が０となるサンプルパターンが計２５回、すなわち全てのサンプルパターンにおいて（２、２）成分が０であったからである。
【００１８】
図５及び図６は、上記ステップＳ６の重要度の計算法を示している。図５は、サンプルパターンが図４に示す（イ）の場合の重要度の計算方法を示している。すなわち、サンプルパターン（イ）の（ｉ，ｊ）成分が１なら１行列の（ｉ，ｊ）成分の値をとりこれをｋとし、あるいは、サンプルパターン（イ）の（ｉ，ｊ）成分が０なら０行列の（ｉ，ｊ）成分の値をとりこれをｋとし、（１／ｋ）の２乗を２×２の成分全てで加えた値をパターン（イ）の重要度とするのである。
【００１９】
図６は、図４に示す４つのサンプルパターン（イ）（ロ）（ハ）（ニ）それぞれの重要度の計算式を示したものである。パターン（ニ）の重要度が最小になっている。これは（ニ）は最も出現頻度が高かったので、引用する０行列の成分の値が皆比較的大きな数値であったからである。つまりありふれたパターンでは重要度は小さく計算されるのである。逆にパターン（イ）の重要度はこの４パターンの中では最大となっている。（イ）は１回しか出現しなかったため、引用する０行列または１行列の成分の値が皆比較的小さな数値であったからである。このようにして出現したサンプルパターンごとに重要度を計算し、そのうち最大の重要度を与えるもの、この例の場合では（イ）をテンプレートパターンとして選択すればよい。
【００２０】
図１のフローチャートに戻る。以上のようにして最適なテンプレートパターンが選定できたら、そのパターンデータを記憶装置に記憶する、または表示装置あるいはプリンターに出力する等してテンプレートを出力する（Ｓ９）。
【００２１】
上記重要度の計算式には幾つかのバリエーションがある。図５及び図６の例では、（１／ｋ）の２乗を２×２の成分全てで加えた値を重要度としたが、一般には（１／ｋ）のｍ乗の値を照合ウインドウの成分全てに渡って加えた値により重要度を求めてもよい。ここでｍは任意に定めた数とする。例えばｍ＝１ならばｋの逆数の総和をとることになる。図５及び図６の例は、ｍ＝２の場合である。あるいは重要度＝サンプルパターンのＥｎｔｒｏｐｙ（シャノンが定義した情報量）と定義して−ｌｏｇ（ｋ／Ｎ）を照合ウインドウの成分全てに渡って加えた値としてもよい。ここで対数の底は２とし、Ｎはサンプルパターンのカウント数である。
【００２２】
図７は、上記本発明の方法に基づいて構成したテンプレート自動選択装置１の全体構成図を示したものである。入力手段１１は、照合ウインドウサイズ、パターンの探査間隔をキーボード等の入力装置１９から受付けて記憶する。画像データ記憶部２０には対象画像データが格納された記憶装置である。１行列０行列作成手段１２は、画像データ記憶部２０から対象画像データを照合ウインドウのサイズで順次切出し、図１のフローチャートにおけるステップＳ３〜Ｓ７までの処理を行う。１行列記憶部２１、０行列記憶部２２は、それぞれ、１行列および０行列のデータを格納するメモリ領域である。テンプレート選択手段１３は図１のフローチャートにおけるステップＳ８の処理を行い、最終的に選択されたテンプレートパターンをテンプレート記憶部２３に記録する。出力表示手段１４は、テンプレート記憶部２３に記録されているテンプレートパターンを表示器１８に表示させる。
【００２３】
テンプレート自動選択装置１は、入力装置１９、表示器１８またはプリンタ、画像データを収納できる外部記憶装置を備えたコンピュータに、図１の処理フローを実現するためのＣＰＵに対する命令を記述したプログラムを組込むことで実現することができる。１行列０行列作成手段１２、テンプレート選択手段１３は、そのようなコンピュータプログラムの関数副プログラムなどとして実現可能である。なお、元になる対象画像データは予め２値データ化した上で画像データ記憶部２０に格納しておいてもよいし、階調画像データのまま画像データ記憶部２０に格納しておき、１行列０行列作成手段１２がウインドウサイズ出切り出して処理をする際に２値化するという方式で実現してもよい。
【００２４】
テンプレート選択手段１３は、サンプルパターンの重要度の算出方法について、図５及び図６の例に示したように、（１／ｋ）の２乗を照合ウインドウの成分全てに渡って加えた値を重要度としてもよいし、（１／ｋ）のｍ乗の値を照合ウインドウの成分全てに渡って加えた値により重要度を求めてもよい。ここでｍは任意に定めた数とする。あるいは重要度＝サンプルパターンのＥｎｔｒｏｐｙと定義して−ｌｏｇ（ｋ／Ｎ）を照合ウインドウの成分全てに渡って加えた値としてもよい。ここで対数の底は２とし、Ｎはサンプルパターンのカウント数である。
【００２５】
【発明の効果】
以上、詳しく説明したように本発明に係るテンプレートの選択方法およびこれを利用したテンプレート自動選択装置によれば、何らかの目的で、デジタル画像処理的手段により、見本とする対象画像とそれに類似または同一の画像を重ね合せるときに必要なテンプレートパターンを、見本とする対象画像から自動的に選択することが可能となるといういう顕著な効果を奏する。
【図面の簡単な説明】
【図１】本発明の方法の概略を説明するフローチャートである。
【図２】良いテンプレートパターンとそうでないパターンを説明する図である。
【図３】具体例により本発明の方法の実施例を説明するための図である。
【図４】具体例により本発明の方法の実施例を説明するための図である。
【図５】具体例により重要度の計算例を説明する図である。
【図６】具体例により重要度の計算結果例を示した図である。
【図７】テンプレート自動選択装置１の全体構成図である。
【符号の説明】
１          テンプレート自動選択装置
１１      入力手段
１２      １行列０行列作成手段
１３      テンプレート選択手段
１４      出力表示手段
１８      表示装置
１９      入力装置
２０      画像データ記憶部
２１      １行列記憶部
２２      ０行列記憶部
２３      テンプレート記憶部
【図１】
2004246448.tif 000003
【図２】
2004246448.tif 000004
【図３】
2004246448.tif 000005
【図４】
2004246448.tif 000006
【図５】
2004246448.tif 000007
【図６】
2004246448.tif 000008
【図７】
2004246448.tif 000009