(57)【要約】【課題】ライブラリのデータ量を抑えて、ライブラリに登録した参照パターンと同一又は類似の図形的特徴を有するマスクパターンを容易に検出することができる検出装置及びプログラムを提供する。【解決手段】半導体装置の製造に用いるフォトマスクを形成する複数のマスクパターンから、参照パターンと図形的特徴が一致又は類似するマスクパターンを検出する検出装置１０において、前記マスクパターン及び参照パターンから複数の図形的な特徴点を夫々抽出する抽出部４０と、抽出部４０が夫々抽出した特徴点各々に、特徴点の識別情報及び該特徴点と隣り合う特徴点とを結ぶ線分の方向情報を前記マスクパターン及び参照パターン別に付与する付与部５０と、付与部５０が前記マスクパターン及び参照パターン別に付与した特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する検出部６０とを備える。【選択図】図２
2014228801.tif 000002
【特許請求の範囲】
【請求項１】
半導体装置の製造に用いるフォトマスクを形成する複数のマスクパターンから、予め用意した参照パターンと図形的特徴が一致又は類似するマスクパターンを検出する検出装置において、
前記マスクパターン及び参照パターンから複数の図形的な特徴点を夫々抽出する抽出部と、
該抽出部が夫々抽出した特徴点各々に、特徴点の識別情報及び該特徴点と隣り合う特徴点とを結ぶ線分の方向情報を前記マスクパターン及び参照パターン別に付与する付与部と、
該付与部が前記マスクパターン及び参照パターン別に付与した特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する検出部と
を備える
検出装置。
【請求項２】
前記抽出部は、
前記マスクパターン及び参照パターンを、内角が優角である角部をなす二辺を該角部と対向する二辺まで各々延長した延長線で複数の平行四辺形に夫々分割する分割部と、
前記延長線を介して隣接する複数の平行四辺形の中心点同士を結ぶ複数の線分を前記マスクパターン及び参照パターンに夫々付与する線分付与部と、
前記分割部が夫々分割した複数の平行四辺形の中心点を前記特徴点として前記マスクパターン及び参照パターン別に抽出する中心点抽出部と、
該中心点抽出部が抽出した複数の特徴点から、前記線分付与部が付与した複数の線分の内、同一方向の二線分のみが隣接する点に対応する特徴点を間引いた特徴点各々を、前記マスクパターン及び参照パターン別に抽出する特徴点抽出部と
を有し、
前記付与部は、前記特徴点抽出部が抽出した特徴点各々に、前記線分付与部が該特徴点を一端点として付与した線分の方向情報及び該特徴点の識別情報を前記マスクパターン及び参照パターン別に付与する
請求項１に記載の検出装置。
【請求項３】
前記抽出部は、
前記マスクパターン及び参照パターンを、内角が優角である角部をなす二辺を該角部と対向する二辺まで各々延長した延長線で複数の平行四辺形に夫々分割する分割部と、
前記延長線を介して隣接する複数の平行四辺形の中心同士を結ぶ複数の線分を前記マスクパターン及び参照パターンに夫々付与する線分付与部と、
該線分付与部が夫々付与した複数の線分の両端点を前記特徴点として前記マスクパターン及び参照パターン別に抽出する両端点抽出部と、
該両端点抽出部が抽出した特徴点から、前記線分付与部が付与した複数の線分の内、同一方向の二線分のみが隣接する共有端点として該両端点抽出部により重複して抽出された特徴点を間引いた特徴点各々を、前記マスクパターン及び参照パターン別に抽出する特徴点抽出部と
を有し、
前記付与部は、前記特徴点抽出部が抽出した特徴点各々に、前記線分付与部が該特徴点を一端点として付与した線分の方向情報及び該特徴点の識別情報を前記マスクパターン及び参照パターン別に付与する
請求項１に記載の検出装置。
【請求項４】
前記抽出部は、前記特徴点抽出部が抽出した前記マスクパターンにおける複数の特徴点から、該複数の特徴点の数以下の数の特徴点を選択し、選択した特徴点を用いた新たなマスクパターンの作成に必要な特徴点の組合せを生成する生成部を有し、
前記特徴点抽出部は、前記生成部が生成した組合せ毎に、前記特徴点を間引いた残りの特徴点各々を前記マスクパターンの特徴点として再抽出し、
前記付与部は、前記特徴点抽出部が再抽出した特徴点各々の数が該特徴点抽出部により抽出された前記参照パターンの特徴点各々の数と等しい場合、再抽出した特徴点各々に、前記識別情報及び方向情報を前記組合せ毎に付与し、
前記検出部は、前記付与部が前記マスクパターンにおける各組合せ及び参照パターン別に付与した特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
請求項２又は請求項３に記載の検出装置。
【請求項５】
前記生成部は、前記マスクパターンにおける複数の特徴点から、該特徴点の数より１小さく、かつ前記特徴点抽出部が前記参照パターンから抽出した複数の特徴点の数以上の数の特徴点を選択し、選択した特徴点の一又は複数の組合せを生成する
請求項４に記載の検出装置。
【請求項６】
前記参照パターンが予め記憶された記憶部を備え、
前記抽出部は前記記憶部が記憶する参照パターンから複数の図形的な特徴点を抽出する  請求項１から請求項５までのいずれか一項に記載の検出装置。
【請求項７】
前記参照パターン並びに該参照パターンに対する前記分割部、線分付与部、中心点抽出部、特徴点抽出部及び付与部による処理の結果が予め記憶された記憶部と、
前記特徴点抽出部が抽出した前記マスクパターンにおける複数の特徴点から、該特徴点の数より１小さく、かつ前記記憶部に記憶された前記参照パターンにおける複数の特徴点の数以上の数の特徴点を選択し、選択した特徴点を用いた新たなマスクパターンの作成に必要な一又は複数の特徴点の組合せを生成する生成部と
を備え、
前記特徴点抽出部は、前記生成部が生成した組合せ毎に、前記特徴点を間引いた残りの特徴点各々を前記マスクパターンの特徴点として再抽出し、
前記付与部は、前記特徴点抽出部が再抽出した特徴点の数が前記記憶部に記憶された前記参照パターンの特徴点の数と等しい場合、再抽出した特徴点各々に、前記識別情報及び方向情報を前記組合せ毎に付与し、
前記検出部は、前記付与部が前記マスクパターンにおける各組合せに付与した特徴点各々の識別情報及び方向情報並びに前記記憶部に予め記憶された参照パターンにおける特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
請求項２又は請求項３に記載の検出装置。
【請求項８】
複数の参照パターンに一致又は類似する複数のマスクパターンを検出すべく、一の参照パターンの位置に対して他の参照パターンが包含される領域の位置情報を算出する算出部と、
該算出部が算出した領域の位置情報並びに前記付与部が前記一及び他の参照パターンに夫々付与した特徴点各々の識別情報及び方向情報を関連付ける関連付部と、
前記検出部が前記一の参照パターンにおける特徴点各々の識別情報及び方向情報と一致する識別情報及び方向情報の特徴点各々を有する一のマスクパターンを検出した場合、前記関連付部が関連付けた前記位置情報の領域と対応するマスクパターンの領域に他のマスクパターンの一部又は全部が含まれるか否かを判定する判定部と、
該判定部が含まれると判定した場合、前記マスクパターンの領域に含まれる他のマスクパターンの一部又は全部を抽出するパターン抽出部と
を備え、
前記抽出部は前記パターン抽出部が抽出した他のマスクパターンの一部又は全部から複数の特徴点を抽出し、
前記付与部は前記抽出部が他のマスクパターンの一部又は全部から抽出した特徴点各々に識別情報及び方向情報を付与し、
前記検出部は、前記付与部が他のマスクパターンの一部又は全部並びに他の参照パターンにおける特徴点各々に夫々付与した識別情報及び方向情報に基づいて、図形的特徴が前記他の参照パターンに一致又は類似する他のマスクパターンを検出する
請求項１から請求項７までのいずれか一項に記載の検出装置。
【請求項９】
記憶部を有するコンピュータに、半導体装置の製造に用いるフォトマスクを形成する複数のマスクパターンから、該記憶部に予め記憶された参照パターンと図形的特徴が一致又は類似するマスクパターンを検出する処理を実行させるプログラムにおいて、
前記マスクパターンから複数の図形的な特徴点を抽出し、
抽出した特徴点各々に、特徴点の識別情報及び該特徴点と隣り合う特徴点とを結ぶ線分の方向情報を前記マスクパターンに付与し、
前記マスクパターンに付与した特徴点各々の識別情報及び方向情報並びに前記記憶部に予め記憶された前記参照パターンの前記特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
処理をコンピュータに実行させるプログラム。
【請求項１０】
前記複数の図形的な特徴点を抽出する処理は、
前記マスクパターンを、内角が優角である角部をなす二辺を該角部と対向する二辺まで各々延長した延長線で複数の平行四辺形に夫々分割し、
前記延長線を介して隣接する複数の平行四辺形の中心点同士を結ぶ複数の線分を前記マスクパターンに付与し、
分割した複数の平行四辺形の中心点を前記特徴点として抽出し、
抽出した複数の特徴点から、付与した前記複数の線分の内、同一方向の二線分のみが隣接する点に対応する特徴点を間引いた特徴点各々を抽出し、
前記識別情報及び方向情報を付与する処理は、前記特徴点を間引いて抽出した特徴点各々に、該特徴点を一端点として付与した線分の方向情報及び該特徴点の識別情報を付与する
請求項９に記載のプログラム。
【請求項１１】
前記複数の図形的な特徴点を抽出する処理は、
前記特徴点を間引いて抽出した前記マスクパターンにおける複数の特徴点から、該複数の特徴点の数以下の数の特徴点を選択し、選択した特徴点を用いた新たなマスクパターンの作成に必要な特徴点の組合せを生成し、
生成した組合せ毎に、前記特徴点を間引いた残りの特徴点各々を前記マスクパターンの特徴点として再抽出し、
前記識別情報及び方向情報を付与する処理は、再抽出した特徴点各々の数が前記記憶部に予め記憶された参照パターンにおける特徴点各々の数と等しい場合、再抽出した前記特徴点各々に、前記識別情報及び方向情報を前記組合せ毎に付与し、
前記マスクパターンを検出する処理は、前記マスクパターンにおける各組合せに付与した特徴点各々の識別情報及び方向情報並びに前記記憶部に予め記憶された参照パターンにおける特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
請求項１０に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、ライブラリに登録された参照パターンと同一又は類似のマスクパターンを検出する検出装置及びプログラムに関する。
【背景技術】
【０００２】
半導体集積回路の微細化に伴い、マスクパターンをウエハに転写する精度の向上が求められている。フォトマスクの設計パターン（レイアウト）は、ＯＰＣ（Optical Proximity Correction近接効果補正）、ＲＥＴ（Resolution Enhancement Technologies超解像技術）等を考慮して補正される場合がある（例えば、特許文献１）。そして、補正後又は補正前の設計パターンに対してエラー箇所がないか検証が行われる。
【０００３】
そのために、後の工程で又はデバイスとして、問題となりそうな複数のエラーパターンを予めライブラリに登録する。そして、ライブラリに登録したエラーパターンと、設計パターンとのパターンマッチングを実行する。パターンマッチングの結果、エラーパターンと一致する設計パターンには、修正が施される。また、ライブラリに登録したエラーパターンに許容値を付加することで、エラーパターンに類似する設計パターンの検出も行われる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−１５９８０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、例えばＯＰＣ処理後の設計パターンを検証するためには、ＯＰＣの複雑さのために、ライブラリに登録する参照パターンの数を増大させる必要がある。また、エラーパターンに類似する設計パターンを検出する場合もライブラリに登録する参照パターンの数が増大する。上記いずれの場合も、ライブラリのデータ量は膨大となり、ライブラリを記憶するストレージの巨大化を招く。
【０００６】
本願の一観点は、ライブラリのデータ量を抑えて、ライブラリに登録した参照パターンと同一又は類似の図形的特徴を有するマスクパターンを容易に検出することができる検出装置及びプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本願の一観点は、半導体装置の製造に用いるフォトマスクを形成する複数のマスクパターンから、予め用意した参照パターンと図形的特徴が一致又は類似するマスクパターンを検出する検出装置において、前記マスクパターン及び参照パターンから複数の図形的な特徴点を夫々抽出する抽出部と、該抽出部が夫々抽出した特徴点各々に、特徴点の識別情報及び該特徴点と隣り合う特徴点とを結ぶ線分の方向情報を前記マスクパターン及び参照パターン別に付与する付与部と、該付与部が前記マスクパターン及び参照パターン別に付与した特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する検出部とを備える。
【発明の効果】
【０００８】
本願の一観点によれば、ライブラリのデータ量を抑えて、ライブラリに登録した参照パターンと同一又は類似の図形的特徴を有するマスクパターンを容易に検出することができる。
【図面の簡単な説明】
【０００９】
【図１】検出装置のハードウェア構成例を示すブロック図である。
【図２】検出装置の機能構成例を示す機能ブロック図である。
【図３】検出装置の機能構成例の詳細を示す機能ブロック図である。
【図４】図形の分割を示す説明図である。
【図５】線分変換の４類型を示す説明図である。
【図６】線分変換処理の一例を示す説明図である。
【図７】抽出された特徴点の一例を示す説明図である。
【図８】特徴情報付与処理の一例を示す説明図である。
【図９】線分変換処理、特徴点抽出処理及び特徴情報付与処理の手順の一例を示すフローチャートである。
【図１０】検証データに含まれるマスクパターンを線分変換した線分図形の一例を示す説明図である。
【図１１】特徴点の組合せの一例を示す説明図である。
【図１２】識別情報の再付与を示す説明図である。
【図１３】検出処理の手順の一例を示すフローチャートである。
【図１４】検出処理の手順の一例を示すフローチャートである。
【図１５】検出装置の機能構成例を示す機能ブロック図である。
【図１６】ライブラリデータ及び検証データに夫々含まれる複数の参照パターン及びマスクパターンを示す説明図である。
【図１７】第１図形に対応する線分図形と、検索領域とを示す説明図である。
【図１８】第３図形への検索領域の当てはめ及び検索領域に含まれる第４図形の抽出を示す説明図である。
【図１９】抽出した第４図形の線分図形及び特徴点を示す説明図である。
【図２０】複数の参照パターンが含まれたライブラリデータと整合する複数のマスクパターンを検出する処理の手順の一例を示すフローチャートである。
【図２１】複数の参照パターンが含まれたライブラリデータと整合する複数のマスクパターンを検出する処理の手順の一例を示すフローチャートである。
【図２２】複数の参照パターンが含まれたライブラリデータと整合する複数のマスクパターンを検出する処理の手順の一例を示すフローチャートである。
【図２３】検索領域の位置情報の他例を示す説明図である。
【発明を実施するための形態】
【００１０】
本実施の形態に係る検出装置（コンピュータ）を、その図面に基づいて説明する。本実施の形態に係る検出装置は、ライブラリに予め登録された参照パターンに一致又は類似するフォトマスクのマスクパターンをパターンマッチングにより検出する。検出対象となるマスクパターンは、ＯＰＣ補正等を施したパターン及び当該補正が施されていないパターンを含む。ライブラリに登録される参照パターンは、エラーパターン及びエラーパターン以外のパターンを含む。
【００１１】
実施の形態１
図１は、検出装置１０のハードウェア構成例を示すブロック図である。検出装置１０は、例えば汎用コンピュータ、ワークステーション、デスクトップ型ＰＣ（パーソナルコンピュータ）、ノートブック型ＰＣ等である。
検出装置１０は、ＣＰＵ（Central Processing Unit）（抽出部、回転反転部、分割部、線分付与部、両端点抽出部、中心点抽出部、特徴点抽出部、生成部、付与部、検出部、算出部、関連付部、判定部、パターン抽出部）１１を含む。また、検出装置１０は、ＲＯＭ（Read Only Memory）１２、ＲＡＭ（Random Access Memory）１３、ハードディスク（記憶部）１４、ディスクドライブ１５、表示部１６、操作部１７、タイマ１８及び通信部１９を含む。
【００１２】
ＣＰＵ１１は、ソフトウェアプログラムに記述された命令セットを実行するためのプロセッサである。ＣＰＵ１１は、検出装置１０の各構成部を制御する。ＣＰＵ１１は、ハードディスク１４に記憶されたプログラム１ＰをＲＡＭ１３に読み出し、ＲＡＭ１３に読み出したプログラム１Ｐを実行する。
【００１３】
ＲＯＭ１２は、例えば不揮発性の半導体メモリ又は半導体メモリ以外の読み出し専用記憶媒体である。ＲＯＭ１２は、検出装置１０の起動時にＣＰＵ１１が実行するＢＩＯＳ（Basic Input/Output System）、ファームウェア等を記憶している。
【００１４】
ＲＡＭ１３は、主記憶装置である。ＲＡＭ１３は、例えばＳＲＡＭ又はＤＲＡＭであり、ＣＰＵ１１が実行する処理の過程で必要な作業変数、データ等を一時的に記憶する。なお、ＲＡＭ１３の代わりにフラッシュメモリ、メモリカード等が用いられてもよい。
【００１５】
ハードディスク１４は、補助記憶装置である。ハードディスク１４は、大容量の情報の記憶が可能なフラッシュメモリ又はＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）、ＢＤ（Blu-ray Disc、登録商標）等の光ディスク１ｄで代替されてもよい。ハードディスク１４は、ＣＰＵ１１が実行するプログラム１Ｐ及びライブラリを記憶している。ライブラリは、設計されたフォトマスクのマスクパターンに対してパターンマッチングを行なうための参照パターンと、当該参照パターンから抽出された図形的特徴点に関する情報を符号化したデータとを格納するデータベースである。
【００１６】
ハードディスク１４は、検出装置１０の内部に取り付けられるものであっても、検出装置１０の外部に置かれるものであってもよい。例えば、ハードディスク１４に記憶されたライブラリは、外部のデータベースサーバに記憶されていてもよい。かかる場合、検出装置１０は、通信部１９を介して、外部のデータベースサーバにアクセスして、ライブラリの内容を取得する。
【００１７】
ディスクドライブ１５は、補助記憶装置である。ディスクドライブ１５は、外部の記憶媒体であるＣＤ、ＤＶＤ、ＢＤ等の光ディスク１ｄから情報を読み出し、光ディスク１ｄに情報を記録する。例えば、ＣＰＵ１１は、操作部１７からディスクドライブ１５に対する光ディスク１ｄの排出命令を受け付けた場合、ディスクドライブ１５の図示しないトレイを排出する。
【００１８】
表示部１６は、画像を表示する表示装置である。表示部１６は、例えば液晶ディスプレイ、有機ＥＬ（Electro Luminescence）ディスプレイ、ＣＲＴ（Cathode Ray Tube）ディスプレイ等の画面を有し、ＣＰＵ１１からの指示に従って、プログラム１Ｐに係る各種情報を表示する。
【００１９】
操作部１７は、ユーザが各種の入力を行うキーボード、マウス、電源スイッチ、ディスクドライブ１５から光ディスク１ｄを排出するための操作ボタン等の入力デバイスである。操作部１７は、ユーザによる操作に基づいて入力信号を生成する。生成された入力信号は、バス１ｂを介してＣＰＵ１１に送信される。
【００２０】
タイマ１８は、クロックを数えることで一定時間の経過を計時する装置である。タイマ１８は、計時した結果をＣＰＵ１１に出力する。
【００２１】
通信部１９は、有線又は無線通信のモデム、ＬＡＮ（Local Area Network）カード、ルータ、ＵＳＢ（Universal Serial Bus）端子、接続コネクタ等である。通信部１９は、ＬＡＮ、ＷＡＮ（Wide Area Network）、電話回線、衛星通信回線、インターネット等のネットワーク１Ｎと接続されている。
【００２２】
なお、ＣＰＵ１１は、ディスクドライブ１５を介して、プログラム１Ｐを光ディスク１ｄから読み込んでもよい。ＣＰＵ１１は、通信部１９を介して、プログラム１Ｐを外部の情報処理装置又は記憶装置から読み込んでもよい。さらに、プログラム１Ｐを記憶したフラッシュメモリ等の半導体メモリ１ｍが、検出装置１０内に実装されていてもよい。
【００２３】
図２は、検出装置１０の機能構成例を示す機能ブロック図である。検出装置１０の各機能部は、ハードディスク１４に記憶されたプログラム１Ｐと、ＣＰＵ１１、ＲＡＭ１３等のハードウェア資源とが協働して動作することにより実現される。
【００２４】
検出装置１０は、記憶部２０、入力部３０、抽出部４０、付与部５０、検出部６０及び出力部７０を含む。
記憶部２０は、ハードウェアのハードディスク１４に対応する機能部である。記憶部２０は、ライブラリ１ｌを記憶している。
【００２５】
入力部３０は、検証対象のデータを入力する機能部である。入力部３０は、ハードウェアの操作部１７又は通信部１９に対応し、検証対象であるマスクパターンのデータ（以下、検証データと呼ぶ）を外部から入力する。また、入力部３０は、ハードウェアのＣＰＵ１１にも対応し、記憶部２０に記憶されたライブラリ１ｌの内容（以下、ライブラリデータと呼ぶ）を入力する。検証データ及びライブラリデータは、夫々マスクパターン及び参照パターンを含む。
【００２６】
抽出部４０は、入力した検証データ及びライブラリデータに夫々含まれるマスクパターン及び参照パターンから、図形的な複数の特徴点を抽出する機能部である。
付与部５０は、抽出部４０が抽出した特徴点各々に識別情報と、特徴点から隣り合う特徴点へ向かう方向情報とを付与する機能部である。付与部５０は、マスクパターン及び参照パターン別に特徴点各々を区別し、特徴点各々に識別情報及び方向情報を付与する。
【００２７】
検出部６０は、付与部５０がマスクパターン及び参照パターン別に付与した特徴点各々の識別及び方向情報に基づいて、図形的特徴がライブラリデータの参照パターンに一致又は類似する検証データのマスクパターンを検出する機能部である。具体的には、検出部６０は、マスクパターンに基づく特徴点各々の識別情報及び方向情報と、参照パターンに基づく特徴点各々の識別情報及び方向情報とをパターンマッチングにより比較照合する。検出部６０は、マスクパターンに基づく特徴点各々の識別情報及び方向情報と、参照パターンに基づく特徴点各々の識別情報及び方向情報とが一致した場合、当該マスクパターンを検出する。
【００２８】
出力部７０は、検出装置１０が検出した結果を外部に出力する機能部である。出力部７０は、ハードウェアの表示部１６又は通信部１９に対応し、検出部６０が検出した検証データのマスクパターンを夫々画像又は情報として出力する。
【００２９】
なお、上述ではライブラリデータは、記憶部２０に記憶されていた。しかし、ライブラリデータは、通信部１９を介して、外部から検出装置１０に取り込まれてもよい。
また、上述では、記憶部２０のライブラリ１ｌには、マスクパターンと比較するための参照パターンのみが格納されていた。しかし、記憶部２０のライブラリ１ｌには、上記の各機能部の処理によりライブラリデータの参照パターンから求めた特徴点各々の識別情報及び方向情報が予め記憶されていてもよい。かかる場合、検出装置１０は、検証データのマスクパターンに係る特徴点各々の識別情報及び方向情報のみを求め、記憶部２０からライブラリデータの参照パターンに係る特徴点各々の識別情報及び方向情報を読み出す。検出装置１０は、求めた検証データのマスクパターンに係る特徴点各々の識別情報及び方向情報と、読み出したライブラリデータの参照パターンに係る特徴点各々の識別情報及び方向情報とを比較照合する。検出装置１０は、比較照合の結果に基づいて、図形的特徴がライブラリデータの参照パターンに一致又は類似する検証データのマスクパターンを検出する。
【００３０】
図３は、検出装置１０の機能構成例の詳細を示す機能ブロック図である。検出装置１０の各機能部は、ハードディスク１４に記憶されたプログラム１Ｐと、ＣＰＵ１１、ＲＡＭ１３等のハードウェア資源とが協働して動作することにより実現される。図３では、記憶部２０、入力部３０、検出部６０及び出力部７０を省略している。
【００３１】
抽出部４０は、回転反転部４１、分割部４２、線分付与部４３、両端点抽出部４４、中心点抽出部４５、特徴点抽出部４６及び生成部４７を含む。
回転反転部４１は、入力部３０が入力した検証データのマスクパターン又はライブラリデータの参照パターンを回転又はミラー反転させる機能部である。これにより、マスクパターンと、参照パターンとの配置方向が異なる場合であっても、図形的特徴が参照パターンと一致又は類似するマスクパターンを検出することができる。また、マスクパターンと、参照パターンとが例えば上下左右に反転した関係にあるために、マスクパターン及び参照パターンの形状的特徴が異なる場合であっても、図形的特徴が参照パターンと一致又は類似するマスクパターンを検出することができる。
【００３２】
なお、回転反転部４１がマスクパターン又は参照パターンを回転させる方向及び回転角度は、適宜選択されてよい。また、回転反転部４１がマスクパターン又は参照パターンをミラー反転させるミラー軸の方向は、適宜選択されてよい。
【００３３】
分割部４２は、検証データ及びライブライリデータ各々に含まれるマスクパターン及び参照パターンを複数の平行四辺形に夫々分割する機能部である。
【００３４】
線分付与部４３は、分割部４２が分割した平行四辺形の中心点と、当該平行四辺形が隣接する平行四辺形との境界線の中点とを結ぶ線分を、マスクパターン及び参照パターンに夫々付与する機能部である。
あるいは、線分付与部４３は、分割部４２が夫々分割した複数の平行四辺形の中心点同士を結ぶ複数の線分を、マスクパターン及び参照パターンに夫々付与する機能部である。
【００３５】
両端点抽出部４４は、線分付与部４３がマスクパターン及び参照パターンに夫々付与した線分の両端点を抽出する機能部である。
中心点抽出部４５は、分割部４２が夫々分割した複数の平行四辺形の中心点を、マスクパターン及び参照パターン別に抽出する機能部である。
【００３６】
なお、両端点抽出部４４及び中心点抽出部４５は、いずれか一方が機能すればよい。
両端点抽出部４４又は中心点抽出部４５が抽出した両端点又は中心点は、図形の特徴を代表する点と捉えて、本実施の形態において特徴点と呼ぶ点である。
【００３７】
特徴点抽出部４６は、線分付与部４３又は中心点抽出部４５が抽出した複数の両端点、中心点から、不必要な両端点又は中心点を間引き、間引いて残った両端点又は中心点各々を、特徴点として抽出する機能部である。不必要な両端点及び中心点とは、検証データ及びライブライリデータ各々に含まれるマスクパターン及び参照パターンの図形的特徴を符号化して表現した場合に、間引いても、間引かなくても検出装置１０の検出処理の精度と無関係な両端点及び中心点である。他方、不必要な両端点又は中心点を間引いた場合、マスクパターン及び参照パターンを符号化したデータのサイズはより小さくなり、検出装置１０の処理速度はより速くなる。
【００３８】
生成部４７は、マスクパターンから抽出した複数の特徴点の数と、参照パターンから抽出した特徴点の数とに応じて、マスクパターンの特徴点各々から、マスクパターンの特徴点の数以下の数の特徴点を選択する機能部である。ここで、生成部４７が選択する特徴点の数は複数通りがあり得る。生成部４７は、選択した特徴点の集合から構成される組合せを一又は複数生成する。
【００３９】
特徴点抽出部４６は、生成部４７が複数の特徴点から構成される一又は複数の組合せを生成した場合、組合せ毎に不必要な特徴点を再び間引き、間引いて残った特徴点を再抽出する。
付与部５０は、生成部４７が生成した組合せに係る複数の特徴点から、特徴点抽出部４６が不要な特徴点を間引いて再抽出した特徴点各々に識別情報及び方向情報を付与する。
また、付与部５０は、ライブラリデータの参照パターンから抽出した特徴点各々に識別情報及び方向情報を付与する。
【００４０】
次に、具体的な図形を例示して、検出装置１０の動作について説明する。
以下では、ライブラリ１ｌに、参照パターンから抽出した特徴点の識別情報及び方向情報を予め登録してから、参照パターンに一致又は類似するマスクパターンを検出する検出処理を実行する場合について説明する。
なお、ライブラリ１ｌは、参照パターンから抽出した特徴点の識別情報及び方向情報を予め記憶していなくてもよい。かかる場合、マスクパターン及び参照パターンから特徴点を夫々抽出する処理と、マスクパターン及び参照パターンから夫々抽出した特徴点に識別情報及び方向情報を付与する処理とは、同時並行に又は時間的に連続して実行されてもよい。
【００４１】
ＣＰＵ１１は、ライブラリ１ｌから１つの参照パターンを読み出す。ＣＰＵ１１は、読み出した参照パターンの図形を複数の平行四辺形に分割する。
図４は、図形の分割を示す説明図である。図４Ａは、Ｆ字状の図形の一例である。図４Ｂは、分割後の図形である。図４Ｂでは、分割後の平行四辺形各々を識別するために、平行四辺形各々にアルファベットが振ってある。なお、一般的に図形は平行四辺形に分割されるが、説明の便宜から以下では図形が矩形に分割される場合を例に挙げて説明する。
【００４２】
ＣＰＵ１１は、図形を図４Ｂのように分割するために、図形における内側の角部を探索する。ここで、内側の角部とは、内角が優角である角部である。あるいは、内側の角部とは、外角が劣角である角部である。
多角形の角は、２本の辺で構成されている。角の周囲は、２本の辺により内角と、外角との共役角に二分される。優角は、共役角のうち、大きい方の角である。共役角のうち、小さい方の角は劣角である。換言した場合、優角は１８０度より大きい角であり、劣角は１８０度より小さい角である。
【００４３】
ＣＰＵ１１は、例えば図４Ａの図形の場合、内角が優角である角部として、図４Ｂに黒丸で示した角部を探索する。ＣＰＵ１１は、探索した角部を構成する２辺を、当該角部が対向する図形の２辺まで夫々延長する。以下、２辺を夫々延長した線を延長線と呼ぶ。図形に延長線を引くことにより、図形は複数の平行四辺形に分割される。図４Ｂの場合、延長線により、Ｆ字状の図形はａ〜ｉで区別される９個の矩形に分割されている。
【００４４】
ＣＰＵ１１は、平行四辺形の中心から延長線の中点へ平行四辺形の一辺と平行な線分を引くことにより、処理対象の平行四辺形を線分に変換する。この処理を線分変換処理と呼ぶ。あるいは、ＣＰＵ１１は、平行四辺形の中心から延長線の中点へ平行四辺形の一辺と平行に引かれた線分を、処理対象の図形に付与するといってもよい。
平行四辺形が矩形である場合、線分変換処理は、矩形の中心から延長線の中点に垂線を降ろす処理に対応する。
【００４５】
図５は、線分変換の４類型を示す説明図である。図５において、斜線で示されている部分は、隣接する矩形部分を示している。図５において、太いドット線は延長線を示している。矩形の中心から延長線に垂線を引く類型には、矩形が４辺から構成されているため、４つの場合があり得る。図５Ａ、図５Ｂ、図５Ｃ及び図５Ｄは、中心から夫々右方、下方、左方及び上方へ引かれた線分を示している。
【００４６】
図６は、線分変換処理の一例を示す説明図である。図６は、図４Ｂにおけるｂの矩形を線分変換した様子を示している。ｂの矩形は、中心から夫々右方及び下方に引かれた２本の線分に変換される。
【００４７】
次に、ＣＰＵ１１は、線分変換処理により図形から変換された線分の両端点を、特徴点として抽出する。
図７は、抽出された特徴点の一例を示す説明図である。図７Ａは、線分変換処理により図４Ａに示した図形から変換された線分の端点群を示している。線分の端点群、すなわち特徴点群は、分割した矩形の中心点と、変換された線分及び延長線の交点とから構成されている。
【００４８】
ＣＰＵ１１は、後の段階で、抽出した特徴点に識別情報と、図形から変換された線分の方向に関する方向情報とを符号化して付与する。これにより、図形は抽象化され、より少ないデータ量でその形状を表現することができる。その場合、図形の特徴を表現する上で、必要でない特徴点がある。そこで、ＣＰＵ１１は、更にデータ量を減少させるべく、抽出した特徴点から不必要な特徴点を間引く処理を実行する。
【００４９】
図７Ｂは、不必要な特徴点の一例を示す説明図である。図７Ｂにおいて、不必要な特徴点には斜線が描かれている。不必要な特徴点は、線分変換処理により変換された線分のうち、隣接する同一方向の２線分のみの共有端点として、重複して抽出された端点である。図７Ｂの例では、不必要な特徴点は、左右方向又は上下方向における２本のみの隣接する線分の接続点に該当する。あるいは、図７の例では、不必要な特徴点は、上下方向又は左右方向の１本の線分のみにより特徴点が貫通されているように見える点である。
【００５０】
図７Ｃは、抽出した特徴点から不必要な特徴点を間引き、残った特徴点の一例を示す説明図である。不必要な特徴点を間引いた後の特徴点は、線分変換処理により図形から変換された線分から構成される線分図形における端点、頂点又は線分が交差する交差点である。
以下、不必要な特徴点を間引いて残った特徴点を抽出する処理を特徴点抽出処理と呼ぶ。
【００５１】
ＣＰＵ１１は、不必要な特徴点を間引いた後の特徴点各々に、識別情報を付与する。また、ＣＰＵ１１は、不必要な特徴点を間引いた後の特徴点各々に、線分変換処理により変換された線分を介して隣り合う特徴点へ向かう方向の情報を付与する。以下、特徴点各々に付与する識別情報及び方向情報を特徴情報と呼ぶ。また、特徴点各々に特徴情報を付与する処理を、特徴情報付与処理と呼ぶ。
【００５２】
図８は、特徴情報付与処理の一例を示す説明図である。図８は、特徴情報のうち、アラビア数字を識別情報として付与する例を示している。なお、識別情報がアラビア数字以外の記号でもよいことは勿論である。
特徴点各々にアラビア数字を付与する場合、付与に関する一定の規則を予め決定しておく。図８の場合、上側から下側に向かって、かつ右側から左側に向かって順にアラビア数字を特徴点に付与している。すなわち、右上ほど小さいアラビア数字が、左下ほど大きなアラビア数字が付与される。勿論、識別情報は他の規則に従って特徴点に付与されてもよい。
【００５３】
図８Ａは、図形が矩形に分割された場合における識別情報付与の一例である。線分変換処理に係る線分は、上下左右に延びている。左側の線分図形は、識別情報を付与する前の状態を示している。右側の線分図形は、特徴点各々の近傍に添え字として識別情報が付与された状態を示している。
【００５４】
図８Ｂは、図形が平行四辺形に分割された場合における識別情報付与の一例である。線分変換処理に係る線分は、上下左右に延びたものと、上下又は左右に対して斜めに延びたものとを含んでいる。左側の線分図形は、識別情報を付与する前の状態を示している。右側の線分図形は、特徴点各々の近傍に添え字として識別情報が付与された状態を示している。
【００５５】
方向情報は、起点の特徴点の識別情報、起点の特徴点から終点の特徴点へ延びる線分方向及び終点の特徴点の識別情報の列記である。方向は、地図における方位を示す東西南北に対応した記号で表示される。例えば、起点の特徴点から終点の特徴点へ延びる線分方向を示す記号は、以下の通りである。
上に延びる線分方向：Ｎ
右に延びる線分方向：Ｅ
左に延びる線分方向：Ｗ
下に延びる線分方向：Ｓ
斜め左下に延びる線分方向：ＷＳ
斜め右上に延びる線分方向：ＥＮ
斜め右下に延びる線分方向：ＥＳ
斜め左上に延びる線分方向：ＷＮ
なお、上記の方向表現は一例であって、上記以外の表記、記号あるいは符号でもよいことは勿論である。例えば、方向情報は、経度のように、０〜３６０度の角度で表記されてもよい。
【００５６】
上記の方向表現を用いた場合、図８Ａにおける特徴点各々の特徴情報は、次のようになる。参考として、左側に特徴点の識別情報も記す。
識別情報      特徴情報
１            １Ｗ２
２            ２Ｅ１，２Ｓ４
３            ３Ｗ４，３Ｓ５
４            ４Ｅ３，４Ｎ２，４Ｓ６
５            ５Ｎ３，５Ｗ６
６            ６Ｎ４，６Ｗ７，６Ｅ５，６Ｓ８
７            ７Ｅ６
８            ８Ｎ６
【００５７】
以下、各特徴点の後に識別情報のアラビア数字を付けることにより、特徴点各々を識別して表記する。
特徴点１に付与された例えば「１Ｗ２」は、特徴点１からＷ方向（左方向）の特徴点２へ向かう方向を意味する。
上記に示したように、１つの図形から抽出される複数の特徴点は、１つの組合せを構成し、１つの組合せを構成する特徴点各々に一又は複数の特徴情報が付与される。
【００５８】
特徴点が線分を介して複数の特徴点と隣り合っている場合、当該特徴点における特徴情報の数は、隣り合う特徴点の数と同じになる。例えば特徴点４は、特徴点２、特徴点３及び特徴点６の３点と隣り合っているので、特徴点４における特徴情報の数は３つである。あるいは、特徴点４における特徴情報の要素数は３つであるといってもよい。ある特徴点に付与される特徴情報の数が複数である場合、各特徴情報は例えばカンマ区切りで区切られる。
【００５９】
個々の特徴点の特徴情報は、特徴点毎に改行されている。これにより、視認性が向上する。また、ＣＰＵ１１が特徴情報を読み込む場合、改行記号により個々の特徴点に対応する特徴点情報の区別が容易になり、処理速度も速くなる。
【００６０】
図８Ｂにおける特徴点各々の特徴情報は、次のようになる。
識別情報      特徴情報
１            １ＷＳ２
２            ２Ｓ４，２ＥＮ１
３            ３Ｗ４，３Ｓ５
４            ４Ｎ２，４Ｅ３，４Ｓ６
５            ５Ｎ３，５Ｗ６
６            ６Ｎ４，６Ｅ５，６Ｗ７，６ＥＳ８
７            ７Ｅ６
８            ８ＷＮ６
【００６１】
ＣＰＵ１１は、ライブラリ１ｌから読み込んだ１つの参照パターンについて、特徴情報付与処理が終了した場合、付与した特徴情報を参照パターンの図形と対応付けてライブラリ１ｌに書き込む。
【００６２】
上述では、ＣＰＵ１１は、延長線の中点に位置する点も特徴点として抽出した。しかし、延長線上の特徴点は後に間引くことになる特徴点である。そこで、ＣＰＵ１１は、図形を複数の平行四辺形に分割した後、各平行四辺形の中心点のみを特徴点として抽出してもよい。かかる場合、線分変換処理は、延長線を介して隣接する平行四辺形の中心点同士を結ぶ複数の線分を抽出し、抽出した複数の線分を図形に付与する。
【００６３】
ＣＰＵ１１は、特徴点として抽出した複数の中心点のうち、同一方向の２本の線分のみが隣接する位置にある特徴点（中心点）を選択する。そして、ＣＰＵ１１は、抽出した複数の特徴点（中心点）から選択した特徴点を間引き、残った特徴点を図形の特徴点に決定する。
【００６４】
図９は、線分変換処理、特徴点抽出処理及び特徴情報付与処理の手順の一例を示すフローチャートである。
ＣＰＵ１１は、ライブラリ１ｌから１つの参照パターンを読み出す（ステップＳ１０１）。ＣＰＵ１１は、読み込んだ参照パターンにおける内側の角部を探索する（ステップＳ１０２）。ＣＰＵ１１は、探索した角部の対辺まで角部をなす２辺を夫々延長し、延長線を生成する（ステップＳ１０３）。ＣＰＵ１１は、ステップＳ１０２で探索した角部の数だけ、ステップＳ１０３の処理を繰り返す。ステップＳ１０３の終了段階で、参照パターンは複数の平行四辺形に分割される。
【００６５】
ＣＰＵ１１は、分割した平行四辺形の中心点から延長線の中点まで線分を引いて、平行四辺形を線分に変換する（ステップＳ１０４：線分変換処理）。ステップＳ１０４において、ＣＰＵ１１は、延長線を介して隣接する平行四辺形が複数ある場合、平行四辺形を複数の線分に変換する。ＣＰＵ１１は、変換した線分の両端点を特徴点として抽出する（ステップＳ１０５）。ＣＰＵ１１は、隣接する同一方向の２線分の端点として、重複して抽出した特徴点を間引く（ステップＳ１０６）。
【００６６】
ＣＰＵ１１は、一定の規則に従って特徴点各々に識別情報を付与する（ステップＳ１０７）。ＣＰＵ１１は、特徴点各々に方向情報を付与する（ステップＳ１０８）。ステップＳ１０８において、ＣＰＵ１１は、線分を介して隣り合う特徴点が複数ある場合、複数の方向情報を付与する。ＣＰＵ１１は、特徴点各々に付与した識別情報及び方向情報、すなわち特徴情報を符号化する（ステップＳ１０９）。ＣＰＵ１１は、読み出した参照パターンの図形に対応付けてライブラリ１ｌに特徴情報を書き込み（ステップＳ１１０）、処理を終了する。
【００６７】
検証データに含まれる１つのマスクパターンについて、仮に線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行したとする。かかる場合、１つの組合せの特徴点各々に特徴情報が付与される。特徴情報は、図形のサイズに関する情報を含まず、図形の特徴を代表する特徴点の方向情報を含む。そのため、参照パターンに係る特徴情報と、マスクパターンに係る特徴情報が一致しても、参照パターン及びマスクパターンのサイズは一致しない場合があり得る。その意味では、マスクパターンに線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行した場合、図形的特徴が参照パターンに一致するマスクパターンを検出する場合と、類似するマスクパターンを検出する場合とがあり得る。
【００６８】
ところで、検証データのマスクパターンの中には、ライブラリ１ｌに登録された参照パターンが部分的に含まれている可能性がある。また、検証の精度を上げるために、ライブラリ１ｌに登録されている参照パターンと完全一致する検証データのマスクパターンだけでなく、ライブラリ１ｌに登録されている参照パターンに類似する検証データのマスクパターンをより多く検出すべきである。
【００６９】
そこで、ＣＰＵ１１は、特徴点抽出処理を実行したマスクパターンの１つの組合せの特徴点各々に識別情報を付与した段階で、新たなマスクパターンを形成し得る特徴点の組合せを一又は複数生成する。ＣＰＵ１１は、生成した一又は複数の組合せ毎に、当該組合せに係る特徴点各々に識別情報を再付与し、かつ方向情報を付与する。そして、ＣＰＵ１１は、生成した組合せ毎に、検証データに係るマスクパターンの特徴点の特徴情報と、ライブラリデータに係る参照パターンの特徴点の特徴情報とを比較照合して、ライブラリデータに係る特徴情報と一致する特徴情報を有する組合せを検出する。
【００７０】
以下、マスクパターンについて、特徴点抽出処理による間引き処理後の特徴点各々に識別情報を付与した後の段階の処理を、より具体的に説明する。
ＣＰＵ１１は、検証データに含まれるマスクパターンの特徴点の数と、ライブラリデータに含まれる参照パターンの特徴点の数とを比較する。以下、「検証データに含まれるマスクパターンの特徴点の数」を検証特徴点数、「ライブラリデータに含まれる参照パターンの特徴点の数」をライブラリ特徴点数と呼ぶ。
【００７１】
ＣＰＵ１１は、検証特徴点数＜ライブラリ特徴点数である場合、処理を終了する。かかる場合、検証データに係る特徴情報と、ライブラリデータに係る特徴情報とが一致する可能性がないからである。ＣＰＵ１１は、ライブラリ１ｌから他の参照パターンを読み込み、特徴情報に基づく次のパターンマッチングに処理を移す。
【００７２】
ＣＰＵ１１は、検証特徴点数＝ライブラリ特徴点数である場合、検証データに係る特徴点各々に符号化された特徴情報を付与する。ＣＰＵ１１は、検証データに含まれるマスクパターンの特徴点の特徴情報と、ライブラリデータに含まれる参照パターンの特徴点の特徴情報とを比較照合して、一致した場合、当該マスクパターンを検出し、処理を終了する。
【００７３】
ＣＰＵ１１は、検証特徴点数＞ライブラリ特徴点数である場合、以下の処理を実行する。ＣＰＵ１１は、検証データに含まれる１つのマスクパターンに係る複数の特徴点から、「検証特徴点数−１」〜「ライブラリ特徴点数」の数の特徴点を選択する。ＣＰＵ１１は、選択した特徴点を用いて新たなマスクパターンが形成可能な特徴点の組合せを全て生成する。
【００７４】
図１０は、検証データに含まれるマスクパターンを線分変換した線分図形の一例を示す説明図である。図１０の線分図形には、特徴点抽出処理により抽出された、間引き処理後の特徴点も重畳して示されている。図１０の特徴点には、一定の規則に従って、識別情報のアラビア数字が付与されている。図１０における特徴点各々に仮に特徴情報を付与した場合、その特徴情報は次のようになる。
識別情報      特徴情報
１          １Ｗ２
２          ２Ｓ４，２Ｅ１
３          ３Ｓ５
４          ４Ｗ５
５          ５Ｎ３，５Ｅ４
６          ６Ｗ７，６Ｓ８
７          ７Ｎ４，７Ｅ６，７Ｓ９
８          ８Ｎ６，８Ｗ９
９          ９Ｎ７，９Ｅ８，９Ｗ１０，９Ｓ１２
１０          １０Ｅ９
１１          １１Ｗ１２
１２          １２Ｎ９，１２Ｅ１１，１２Ｗ１３，１２Ｓ１４
１３          １３Ｅ１２
１４          １４Ｎ１２
【００７５】
いま、図１０の線分図形に対応するマスクパターンが検証対象のマスクパターンであるものとする。また、ライブラリデータに含まれる参照パターンを線分変換した線分図形は、図８Ａと同一であるものとする。図１０の線分図形に係る特徴情報と、図８Ａの線分図形に係る特徴情報とを比較照合しても、一致しないことは明らかである。しかし、図１０の線分図形の一部に係る特徴情報と、図８Ａの線分図形に係る特徴情報とが一致する可能性がある。
【００７６】
図１０及び図８Ａの線分図形を例にした場合、検証特徴点数＝１４、ライブラリ特徴点数＝８となる。ＣＰＵ１１は、図１０における１４個の特徴点から１３〜８個の特徴点を夫々選択し、夫々選択した複数の特徴点で新たなマスクパターンを形成することができる特徴点の全組合せを生成する。
【００７７】
ＣＰＵ１１が機械的に選択可能な特徴点の組合せは、14Ｃ 8＋14Ｃ 9＋14Ｃ10＋14Ｃ11＋14Ｃ12＋14Ｃ13通りである。しかし、機械的に選択した特徴点の組合せの中には、複数のマスクパターンに分かれる特徴点の組合せがあり得る。換言した場合、１つのマスクパターンを形成しない特徴点の組合せが含まれている。そこで、ＣＰＵ１１は、新たな１つのマスクパターンを形成し得る特徴点の組合せを全て生成する。
【００７８】
例えば、図１０に示した１４個の特徴点から８個の特徴点を選択した組合せであって、かつ新たな１つのパターンを形成する特徴点の組合せの一例は以下のようになる。以下のＮｏは、組合せを区別するために説明の便宜上設けた番号である。
Ｎｏ                        特徴点
［０１］      １，  ２，  ３，  ４，  ５，  ６，  ７，  ８
［０２］      １，  ２，  ３，  ４，  ５，  ６，  ７，  ９
［０３］      １，  ２，  ３，  ４，  ５，  ７，  ９，１０
［０４］      １，  ２，  ３，  ４，  ５，  ７，  ９，１２
［０５］      １，  ２，  ６，  ７，  ８，  ９，１０，１２
［０６］      ２，  ７，  ９，１０，１１，１２，１３，１４
［０７］      ６，  ８，  ９，１０，１１，１２，１３，１４
［０８］      １，  ２，  ６，  ７，  ８，  ９，１０，１４
［０９］      ７，  ８，  ９，１０，１１，１２，１３，１４
［１０］      ４，  ７，  ８，  ９，１０，１１，１２，１３
・
・
・
【００７９】
図１１は、特徴点の組合せの一例を示す説明図である。図１１に示す各線分図形の左上に沿えた番号は、上記のＮｏに対応する。１４個の特徴点から８個の特徴点を選択した組合せであって、かつ新たな１つのパターンを形成する特徴点の組合せは、図１１に示した組合せ以外にもある。図１１は、組合せの一部を例示したものである。
【００８０】
ＣＰＵ１１は、１４個の特徴点から１３〜９個の特徴点を図１１と同様に夫々選択し、選択した特徴点の組合せのうち、新たな１つのマスクパターンを形成し得る組合せを生成する。ただし、ＣＰＵ１１は、選択した特徴点の個数（１３〜９個）がライブラリ特徴点数（８点）より大きい場合、不必要な特徴点を間引く処理を実行する。ＣＰＵ１１は、間引く処理を実行した結果、選択した特徴点の個数がライブラリ特徴点数（８点）と同数になる特徴点の組合せのみを生成した組合せから抽出する。これは、特徴情報に基づくパターンマッチングが、ライブラリ特徴点数と同数の特徴点を有する検証データのマスクパターンについてのみ、一致する可能性があるからである。
【００８１】
上述に従い、ＣＰＵ１１は、検証データに含まれる１つのマスクパターンから抽出した１つの組合せの特徴点各々から、ライブラリ特徴点数と同数の特徴点を有する新たな複数のマスクパターンに対応する組合せを抽出する。次に、ＣＰＵ１１は、パターンマッチングのために、特徴点の識別情報を改めて再付与する。例えば、ライブラリデータに係る図８Ａの線分図形の場合、特徴点は１〜８のアラビア数字で識別化されている。他方、検証データに係る例えば上記Ｎｏ＝［０５］の組合せの場合、９〜１２のアラビア数字で識別化された特徴点が含まれているため、このままでは特徴情報によるパターンマッチングができない。そこで、ＣＰＵ１１は、Ｎｏ＝［０５］の組合せの場合、１，２，６，７，８，９，１０，１２の識別情報を有する各特徴点に、一定の規則（例えば、上側／右側優先）に従って、１〜８を再付与する。
【００８２】
図１２は、識別情報の再付与を示す説明図である。図１２は、上記のＮｏ＝［０１］、［０２］、［０５］、［０７］、［０８］を識別情報再付与の例に挙げている。図１２の上段は再付与前の識別情報を、下段は再付与後の識別情報を示している。
【００８３】
ＣＰＵ１１は、各組合せの特徴点各々に識別情報を再付与した場合、更に方向情報を付与する。ＣＰＵ１１は、各組合せの特徴点各々に符号化した特徴情報を付与する。
なお、ＣＰＵ１１は、間引き処理後の特徴点各々に識別情報及び方向情報から構成される特徴情報を符号化して付与した後に、特徴点の組合せを生成してもよい。かかる場合、ＣＰＵ１１は、組合せ毎に、検証データに係る特徴情報に含まれる再付与前の識別情報を再付与後の識別情報で置換し、識別情報を更新する。
【００８４】
以下に、識別情報再付与後のＮｏ＝［０１］、［０２］、［０５］、［０７］、［０８］について、特徴情報を例示する。
［０１］                            ［０２］
１Ｗ２                              １Ｗ２
２Ｅ１，２Ｓ４                      ２Ｅ１，２Ｓ４
３Ｓ５                              ３Ｓ５
４Ｗ５，４Ｎ２，４Ｓ７              ４Ｗ５，４Ｎ２，４Ｓ７
５Ｎ３，５Ｅ４                      ５Ｎ３，５Ｅ４
６Ｗ７，６Ｓ８                      ６Ｗ７
７Ｅ６，７Ｎ４                      ７Ｅ６，７Ｎ４，７Ｓ８
８Ｎ６                              ８Ｎ７
【００８５】
［０５］                            ［０７］
１Ｗ２                              １Ｓ２
２Ｅ１，２Ｓ４                      ２Ｗ３，２Ｎ１
３Ｗ４，３Ｓ５                      ３Ｗ４，３Ｅ２，３Ｓ６
４Ｅ３，４Ｎ２，４Ｓ６              ４Ｅ３
５Ｎ３，５Ｗ６                      ５Ｗ６
６Ｎ４，６Ｗ７，６Ｅ５，６Ｓ８      ６Ｎ３，６Ｗ７，６Ｅ５，６Ｓ８
７Ｅ６                              ７Ｅ６
８Ｎ６                              ８Ｎ６
【００８６】
［０８］
１Ｗ２
２Ｅ１，２Ｓ４
３Ｗ４，３Ｓ５
４Ｅ３，４Ｎ２，４Ｓ６
５Ｎ３，５Ｗ６
６Ｎ４，６Ｗ７，６Ｅ５，６Ｓ８
７Ｅ６
８Ｎ６
【００８７】
ＣＰＵ１１は、検証データのマスクパターンに係る一又は複数の組合せの特徴情報と、ライブラリデータの参照パターンに係る特徴情報とを比較照合して、参照パターンに係る特徴情報と一致する特徴情報を有するマスクパターンの組合せを検出する。
例えば図１２に例示した５通りのマスクパターンの組合せに係る特徴情報と、図８Ａの線分図形に係る参照パターンの特徴情報とを比較照合した場合、Ｎｏ＝［０５］、［０８］の組合せに係る特徴情報がライブラリ１ｌに基づく参照パターンの特徴情報と一致する。そこで、ＣＰＵ１１は、Ｎｏ＝［０５］、［０８］の組合せを検出する。
【００８８】
図１３及び図１４は、検出処理の手順の一例を示すフローチャートである。図１３及び図１４における検証処理は、ライブラリ１ｌに基づいて、検証データに含まれる１つのマスクパターンを検証する処理である。他のマスクパターンの検証は、図１３及び図１４と同様の処理を繰り返すことにより実現される。
【００８９】
ＣＰＵ１１は、検証データを入力する（ステップＳ２０１）。ＣＰＵ１１は、入力した検証データから１つのマスクパターンを選択する（ステップＳ２０２）。ＣＰＵ１１は、選択したマスクパターンについて、線分変換処理及び特徴点抽出処理を実行する（ステップＳ２０３）。ステップＳ２０３の処理は、図９のステップＳ１０２〜ステップＳ１０６の処理と同様である。ＣＰＵ１１は、検証データに含まれるマスクパターンから抽出した特徴点に識別情報を付与する（ステップＳ２０４）。
【００９０】
ＣＰＵ１１は、ライブラリ１ｌに登録された１つの参照パターンに係る特徴点各々の特徴情報を読み出す（ステップＳ２０５）。ステップＳ２０５でＣＰＵ１１が読み出す特徴情報は、まだ読み出しが行なわれていない参照パターンに係る特徴情報である。ＣＰＵ１１は、読み出したライブラリデータに含まれる参照パターンの特徴点の数をカウントする（ステップＳ２０６）。すなわち、ＣＰＵ１１は、ライブラリ特徴点数をカウントする。ＣＰＵ１１は、検証データに含まれるマスクパターンから抽出した特徴点の数をカウントする（ステップＳ２０７）。すなわち、ＣＰＵ１１は、検証特徴点数をカウントする。
【００９１】
ＣＰＵ１１は、検証特徴点数＜ライブラリ特徴点数か否かを判定する（ステップＳ２０８）。ＣＰＵ１１は、検証特徴点数＜ライブラリ特徴点数であると判定した場合（ステップＳ２０８：ＹＥＳ）、ステップＳ２０５に処理を戻し、次の参照パターンに係る特徴点各々の特徴情報を読み出す。ＣＰＵ１１は、検証特徴点数＜ライブラリ特徴点数でないと判定した場合（ステップＳ２０８：ＮＯ）、検証特徴点数＝ライブラリ特徴点数か否かを判定する（ステップＳ２０９）。ＣＰＵ１１は、検証特徴点数＝ライブラリ特徴点数であると判定した場合（ステップＳ２０９：ＹＥＳ）、ステップＳ２１５へ処理を移行する。
【００９２】
ＣＰＵ１１は、検証特徴点数＝ライブラリ特徴点数でないと判定した場合（ステップＳ２０９：ＮＯ）、ステップＳ２０４で識別情報を付与した特徴点から「検証特徴点数−１」〜「ライブラリ特徴点数」の数の特徴点を夫々選択する（ステップＳ２１０）。ＣＰＵ１１は、夫々選択した特徴点を用いて新たな１つのマスクパターンを形成することができる特徴点の組合せを全て生成する（ステップＳ２１１）。ＣＰＵ１１は、生成した組合せ毎に、不必要な特徴点を間引く（ステップＳ２１２）。ＣＰＵ１１は、ステップＳ２１２の処理が終了した組合せにおける特徴点の数がライブラリ特徴点数に等しい組合せを抽出する（ステップＳ２１３）。
【００９３】
ＣＰＵ１１は、ステップＳ２１３で抽出した組合せの特徴点各々に、一定の規則に従って識別情報を再付与する（ステップＳ２１４）。ＣＰＵ１１は、ステップＳ２１３で抽出した組合せの特徴点各々に方向情報を付与する（ステップＳ２１５）。ステップＳ２１５において、ＣＰＵ１１は、ステップＳ２０９から処理を移行した場合、１つの組合せの特徴点各々に方向情報を付与する。ＣＰＵ１１は、組合せ毎に、特徴点各々に付与した識別情報及び方向情報、すなわち特徴情報を符号化する（ステップＳ２１６）。
【００９４】
ＣＰＵ１１は、組合せ毎に、ステップＳ２１６で求めたマスクパターンに係る識別情報と、ステップＳ２０５で読み出した参照パターンに係る識別情報とを比較照合する（ステップＳ２１７）。ＣＰＵ１１は、参照パターンに係る識別情報と一致する識別情報を有するマスクパターンの組合せを検出し（ステップＳ２１８）、処理を終了する。
【００９５】
検索装置１０によれば、ライブラリ１ｌのデータ量を抑えて、ライブラリ１ｌに登録した参照パターンと同一又は類似の図形的特徴を有するマスクパターンを容易に検出することができる。
検索装置１０は、参照パターンを特徴点に抽象化し、特徴点の識別情報及び方向情報のみを符号化する。そのため、検出装置１０は、ライブラリ１ｌに登録されるデータ量及びライブラリ１ｌの記憶領域の抑制を図ることができる。
識別情報及び方向情報から構成される特徴情報は、パターンの幅及び長さに依存しない図形的特徴である。そのため、検出装置１０は、特徴情報を用いたパターンマッチングにより、ライブラリ１ｌの参照パターンと同一又は類似するマスクパターンを容易に検出することができる。
検索装置１０は、マスクパターンに係る特徴点の数より少ない数の特徴点から選択した特徴点の組合せを検証対象として生成する。そのため、検出装置１０は、ライブラリ１ｌに登録された参照パターンと図形的に異なるマスクパターンでも、その中に含まれる特徴情報が同一であるパターン部分を検出することができる。
【００９６】
実施の形態２
実施の形態２は、ライブラリ１ｌに登録された複数の参照パターンと一致又は類似する検証データに含まれる複数のマスクパターンを検出する形態に関する。
なお、実施の形態２において、実施の形態１と同様である構成要素には同一の参照番号を付してその詳細な説明を省略する。
【００９７】
ライブラリ１ｌに登録された複数の参照パターンと、検証データに含まれる複数のマスクパターンとを特徴情報に基づいて比較照合するためには、個々の参照パターンの相対的な位置情報がライブラリ１ｌに登録されている必要がある。ＣＰＵ１１は、個々の参照パターンの相対的位置関係に基づいて、検証データに含まれる複数のマスクパターンの分布領域に、個々の参照パターンと比較照合の対象となるマスクパターンを検索する領域を設定する。複数のマスクパターンの分布領域に当該領域の設定が行なわれた場合、ＣＰＵ１１は、設定した領域内にマスクパターンがあるか否かを判定する。あるいは、ＣＰＵ１１は、設定した領域内からマスクパターンを検索する。ＣＰＵ１１は、設定した領域内にマスクパターンがあると判定した場合、当該マスクパターンに係る特徴情報と、ライブラリ１ｌに登録されている複数の参照パターンのうち、１つの参照パターンに係る特徴情報との比較照合を行う。
【００９８】
以下では、ライブラリデータに含まれる２つの参照パターンと一致又は類似する検証データに含まれた２つのマスクパターンを検出する場合について、説明する。３つ以上の上記参照パターン及びマスクパターンを扱う場合、以下に示す処理を３つ目以降の参照パターン及びマスクパターンに繰り返して適用することができる。
また、以下では、説明の便宜上、ライブラリデータに含まれる２つの参照パターンを夫々第１図形及び第２図形と呼ぶ。他方、検証データに含まれる２つのマスクパターンを夫々第３図形及び第４図形と呼ぶ。
【００９９】
図１５は、検出装置１０の機能構成例を示す機能ブロック図である。検出装置１０の各機能部は、ハードディスク１４に記憶されたプログラム１Ｐと、ＣＰＵ１１、ＲＡＭ１３等のハードウェア資源とが協働して動作することにより実現される。図１５では、出力部７０は省略されている。
【０１００】
検出装置１０は、算出部８０、関連付部９０、判定部１００及びパターン抽出部１１０を含む。
算出部８０は、ライブラリデータに係る第１図形の位置に対して第２図形が包含される領域の位置情報を算出する機能部である。以下、第２図形が包含される領域を検索領域と呼ぶ。
【０１０１】
関連付部９０は、算出部８０が算出した検索領域の位置情報と、付与部５０が第１図形及び第２図形に付与した特徴情報とを関連付ける機能部である。関連付部９０は、検索領域の位置情報を第１図形及び第２図形の特徴情報に関連付けて、記憶部２０内のライブラリ１ｌに記憶する。なお、検出装置１０は、ライブラリ１ｌにて、第２図形が包含される検索領域と、第２図形の特徴情報とを対にして管理する。
【０１０２】
判定部１００は、検出部６０が第１図形に係る特徴点各々の特徴情報と一致する特徴情報を有する第３図形を検出した場合、関連付部９０が関連付けた検索領域と対応する検証データに係る領域に第４図形が含まれるか否かを判定する機能部である。
【０１０３】
パターン抽出部１１０は、判定部１００の判定結果に応じて、検索領域に対応する検証データの領域に含まれる第４図形の一部又は全部を抽出する機能部である。パターン抽出部１１０は、抽出した第４図形の一部又は全部を入力部３０に与える。
【０１０４】
入力部３０は、パターン抽出部１１０から与えられた第４図形の一部又は全部を抽出部４０に与える。抽出部４０は、第４図形の一部又は全部から複数の特徴点を抽出する。付与部５０は、抽出部４０が第４図形の一部又は全部から抽出した特徴点各々に特徴情報を付与する。検出部６０は、第２図形に係る特徴点各々の特徴情報と、第４図形の一部又は全部に係る特徴点各々の特徴情報とが一致する場合、第４図形の一部又は全部を検出する。
【０１０５】
次に、具体的な図形を例示して、検出装置１０の動作について説明する。
図１６は、ライブラリデータ及び検証データに夫々含まれる複数の参照パターン及びマスクパターンを示す説明図である。図１６Ａは、第１図形１０ａ及び第２図形１０ｂの形状及び配置を示す説明図である。図１６Ｂは、第３図形１０ｃ及び第４図形１０ｄの形状及び配置を示す説明図である。
【０１０６】
第１図形１０ａは、Ｆ字状をなす。第２図形１０ｂは、第１図形１０ａの上部右方に位置し、横方向に延びたＬ字状をなす。第３図形１０ｃは、Ｆ字状をなす。第４図形１０ｄは、第３図形１０ｃの右方に位置し、第２図形１０ｂに類似する横方向に延びたＬ字状のパターンと、当該パターンの右端に接合されたＩ字状のパターンとを含む。
【０１０７】
ＣＰＵ１１は、一定の規則に従って、第１図形１０ａ、第２図形１０ｂ、第３図形１０ｃ及び第４図形１０ｄに夫々識別情報を付与する。説明の便宜上識別情報となるアルファベットを第１図形１０ａ、第２図形１０ｂ、第３図形１０ｃ及び第４図形１０ｄに、夫々既に付与した。しかし実際には、ＣＰＵ１１は、識別情報が必要となった段階で、例えば面積の大きい方から小さい方へ向かって、ライブラリ１ｌに登録された複数の参照パターンにアルファベット、アラビア数字等の識別情報を夫々付与する。あるいは、ＣＰＵ１１は、識別情報が必要となった段階で、例えば上側／右側優先規則に従って、ライブラリ１ｌに登録された複数の参照パターンに識別情報を夫々付与してもよい。同様に、ＣＰＵ１１は、検証データに含まれる複数のマスクパターンを受け付けた後の段階で、一定の規則に従って、受け付けた複数のマスクパターンに夫々識別情報を付与する。
以下では、ＣＰＵ１１は、面積の大きい方から小さい方へ向かって、ライブラリ１ｌに登録された複数の参照パターン及び検証データに含まれる複数のマスクパターンにアルファベットから構成される識別情報を夫々付与するものとする。
【０１０８】
まず、ライブラリ１ｌに登録されている第１図形１０ａ及び図Ｂ１０ｂの位置に基づいて、検索領域の位置情報を算出する処理を説明する。
図１７は、第１図形１０ａに対応する線分図形と、検索領域１０ｓとを示す説明図である。図１７では、検索領域１０ｓは、破線の矩形で示されている。検索領域１０ｓは、第２図形１０ｂを包含する領域の外縁を定めることができる図形ならば、どのような図形でもよく、例えば平行四辺形、円形、楕円形、不定形でもよい。以下では、検索領域１０ｓの形状が矩形状である場合を例に挙げて、実施の形態２を説明する。
【０１０９】
ＣＰＵ１１は、面積がより大きい第１図形１０ａに対して線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行し、生成した特徴情報を第１図形１０ａと対応付けてライブラリ１ｌに記憶する。第１図形１０ａの特徴点各々の特徴情報は、例えば次のようになる。
１Ｗ２
２Ｓ４，２Ｅ１
３Ｗ４
４Ｎ２，４Ｅ３，４Ｓ５
５Ｎ４
【０１１０】
ＣＰＵ１１は、第１図形１０ａから抽出した特徴点のうち、任意の１点を選択する。ここでは、ＣＰＵ１１は、第１図形１０ａから特徴点２を選択するものとする。                
【０１１１】
ＣＰＵ１１は、第１図形１０ａに含まれる特徴点２に対して、第２図形１０ｂが包含される検索領域１０ｓの位置情報を算出する。そのために、ＣＰＵ１１は、特徴点２が線分変換処理に係る線分を介して隣り合う特徴点１及び特徴点４に着目する。ＣＰＵ１１は、特徴点２から特徴点１へ向かう線分の方向及び長さ並びに特徴点２から特徴点４へ向かう線分の方向及び長さを用いて、特徴点２に対する矩形状の検索領域１０ｓの位置を符号化する。
【０１１２】
例えば、図１７において、検索領域１０ｓの横幅は、特徴点２と特徴点１との間隔の３．１倍である。また、図１７において、検索領域１０ｓの縦幅は、特徴点２と特徴点４との間隔の１倍である。そこで、検索領域１０ｓの位置情報は、特徴点２を頂点とする矩形の２辺で表現される。２辺のうち一辺は、特徴点２から右側に位置する特徴点１の方向へ、特徴点２と特徴点１との間隔の３．１倍の長さの線分である。２辺のうち他辺は、特徴点２から下側に位置する特徴点４の方向へ、特徴点２と特徴点４との間隔の１倍の長さの線分である。
【０１１３】
符号化した検索領域１０ｓの位置情報の一般的な表現は、例えば次のようになる。
［検索領域１０ｓの頂点となる特徴点の識別情報］，［検索領域１０ｓの一辺に対応する特徴点間の線分］［倍率フラグ］［一辺の長さを特徴点間距離の倍率で示した数値］
［検索領域１０ｓの頂点となる特徴点の識別情報］，［検索領域１０ｓの他辺に対応する特徴点間の線分］［倍率フラグ］［他辺の長さを特徴点間距離の倍率で示した数値］
【０１１４】
図１７の例における具体的な検索領域１０ｓの位置情報は、例えば次のようになる。
２，２Ｅ１Ｍ３．１
２，２Ｓ４Ｍ１
上記では、検索領域１０ｓの辺の方向は、特徴情報に含まれる特徴点各々の方向情報と同じ凡例で表現されている。また、Ｍは、倍率フラグである。倍率フラグの記号Ｍの後に、辺の長さを特徴点間距離の倍率で示した数値が記される。
【０１１５】
ＣＰＵ１１は、第２図形１０ｂに対して線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行し、生成した特徴情報を第２図形１０ｂと対応付けてライブラリ１ｌに記憶する。第２図形１０ｂの特徴点各々の特徴情報は、次のようになる。
１Ｓ３
２Ｗ３
３Ｎ１，３Ｅ２
【０１１６】
ＣＰＵ１１は、符号化した検索領域１０ｓの位置情報と、第１図形１０ａ及び第２図形１０ｂの特徴点各々の特徴情報とを関連付ける。ＣＰＵ１１は、ライブラリデータに３つ以上の参照パターンが含まれる場合、３つ目以降の参照パターンについても、符号化した検索領域１０ｓの位置情報と、第１図形１０ａ、第２図形１０ｂ及び３つ目以降の図形の特徴点各々の特徴情報とを夫々関連付ける。
【０１１７】
ここでの関連付けは、第２図形１０ｂが包含される検索領域１０ｓの位置情報と、第２図形１０ｂの特徴点各々の特徴情報とが対を構成することの情報が記憶部２０のライブラリ１ｌに記憶されることを含む。
なお、ＣＰＵ１１は、符号化した検索領域１０ｓの位置情報と、参照パターンに係る特徴情報とを対にして関連付ける場合、対を表わす符号を検索領域１０ｓの位置情報と、参照パターンに係る特徴情報とに付加してライブラリ１ｌに記憶してもよい。
【０１１８】
ＣＰＵ１１は、検証データに含まれる複数のマスクパターンを受け付ける。ＣＰＵ１１は、一定の規則に従って、検証データに含まれる複数のマスクパターンに夫々識別情報を付与する。その結果、例えば第３図形１０ｃ及び第４図形１０ｄは、識別情報に対応するアルファベットを用いることにより識別可能になる。
ＣＰＵ１１は、識別情報を付与した第３図形１０ｃ及び第４図形１０ｄを、必要に応じてユーザからの指示又は予め定められた手順により、回転又はミラー反転させる。
【０１１９】
ＣＰＵ１１は、第３図形１０ｃ及び第４図形１０ｄに対して線分変換処理及び特徴点抽出処理を夫々実行する。また、ＣＰＵ１１は、第３図形１０ｃ及び第４図形１０ｄの特徴点に基づいて、新たな複数のマスクパターンを形成し得る特徴点の組合せを生成する。ＣＰＵ１１は、生成した組合せから第１図形１０ａ又は第２図形１０ｂのライブラリ特徴点数と同数の特徴点を有する組合せを抽出する。この組合せに関する処理は、実施の形態１で説明した内容と同一である。ＣＰＵ１１は、抽出した組合せの特徴点各々に対して特徴情報付与処理を実行する。
【０１２０】
ＣＰＵ１１は、第３図形１０ｃ及び第４図形１０ｄに係る特徴点の組合せの中から、ライブラリデータに係る第１図形１０ａ又は第２図形１０ｂの特徴点各々の特徴情報と同一の特徴情報を有する組合せを抽出する。ここでは、第１図形１０ａの特徴点各々の特徴情報と、第３図形１０ｃに係る１つの組合せの特徴情報が一致し、ＣＰＵ１１は第３図形１０ｃを抽出するものとする。
【０１２１】
ＣＰＵ１１は、ライブラリ１ｌに検索領域１０ｓの位置情報が記憶されているか否かを判定する。ＣＰＵ１１は、ライブラリ１ｌに検索領域１０ｓの位置情報が記憶されていない場合、処理を終了する。他方、ＣＰＵ１１は、ライブラリ１ｌに検索領域１０ｓの位置情報が記憶されている場合、ライブラリ１ｌから検索領域１０ｓの位置情報を読み出す。ＣＰＵ１１は、読み出した検索領域１０ｓの位置情報を検証データに含まれるマスクパターンの第３図形１０ｃに当てはめて、検証データに含まれるマスクパターンの分布領域に検索領域１０ｓを設定する。
【０１２２】
図１８は、第３図形１０ｃへの検索領域１０ｓの当てはめ及び検索領域１０ｓに含まれる第４図形１０ｄの抽出を示す説明図である。図１８Ａは、第３図形１０ｃへの検索領域１０ｓの当てはめを示す説明図である。図１８Ｂは、検索領域１０ｓに含まれる第４図形１０ｄの抽出を示す説明図である。図１８において、検索領域１０ｓは、破線で示された矩形に対応する。
【０１２３】
ＣＰＵ１１は、第３図形１０ｃの特徴点２に、ライブラリ１ｌに登録された検索領域１０ｓの位置情報を設定する。ライブラリ１ｌに登録された検索領域１０ｓの位置情報は、以下のものであった。
２，２Ｅ１Ｍ３．１
２，２Ｓ４Ｍ１
上記の１、２、４は、夫々第１図形１０ａにおける特徴点１、特徴点２、特徴点４の識別情報に夫々対応する。ＣＰＵ１１は、第３図形１０ｃへの検索領域１０ｓの当てはめに際し、上記の１、２、４を第３図形１０ａにおける特徴点１、特徴点２、特徴点４の識別情報に夫々対応させる。
また、上記の２Ｅ１は、第１図形１０ａにおける特徴点２と特徴点１とを結ぶ線分の方向及び長さに対応している。ＣＰＵ１１は、第３図形１０ｃへの検索領域１０ｓの当てはめに際し、２Ｅ１を第３図形１０ｃにおける特徴点２と特徴点１とを結ぶ線分の方向及び長さに対応させる。
【０１２４】
同様にして、ＣＰＵ１１は、２Ｓ４を第３図形１０ｃにおける特徴点２と特徴点４とを結ぶ線分の方向及び長さに対応させる。このようにして、ＣＰＵ１１は、ライブラリ１ｌに登録された検索領域１０ｓの位置情報を検証データに含まれるマスクパターンの第３図形１０ｃに当てはめる。その結果が、図１８Ａに示す破線の矩形である。
【０１２５】
ＣＰＵ１１は、第４図形１０ｄを必要に応じてユーザからの指示又は予め定められた手順により、回転又はミラー反転させる。以下では、第４図形１０ｄを回転又はミラー反転しない場合について説明する。ＣＰＵ１１は、第３図形１０ｃに当てはめた検索領域１０ｓの中に、第４図形１０ｄが含まれるか否かを判定する。ＣＰＵ１１は、第３図形１０ｃに当てはめた検索領域１０ｓの中に、第４図形１０ｄが含まれないと判定した場合、処理を終了する。
【０１２６】
ＣＰＵ１１は、第３図形１０ｃに当てはめた検索領域１０ｓの中に、第４図形１０ｄが含まれると判定した場合、検索領域１０ｓから第４図形１０ｄを抽出する。ここで、第４図形１０ｄの全体が検索領域１０ｓの中に含まれる場合と、第４図形１０ｄの一部が検索領域１０ｓの中に含まれる場合とがある。図１８Ａは、検索領域１０ｓの中に第４図形１０ｄの一部が含まれる場合を例示している。図１８Ａの場合、ＣＰＵ１１は、第４図形１０ｄを検索領域１０ｓの周を構成する線で切り取り、検索領域１０ｓの中に含まれる第４図形１０ｄの左側の一部を抽出する。図１８Ｂは、その抽出結果を示している。
【０１２７】
ＣＰＵ１１は、抽出した第４図形１０ｄの一部又は全部に対して、線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行する。これらの処理の中には、新たな複数のマスクパターンを形成し得る特徴点の組合せの生成、不必要な特徴点の間引き及び第２図形１０ｂのライブラリ特徴点数と同数の特徴点を有する組合せの抽出が含まれる。
【０１２８】
ＣＰＵ１１は、生成及び抽出した組合せ毎に、組合せを構成する特徴点各々の特徴情報と、ライブラリ１ｌに登録した検索領域１０ｓと対をなす第２図形１０ｂの特徴点各々の特徴情報とを比較照合する。ＣＰＵ１１は、比較照合の結果、第２図形１０ｂの特徴点各々の特徴情報と一致する特徴情報を有する組合せがない場合、処理を終了する。ＣＰＵ１１は、第２図形１０ｂの特徴点各々の特徴情報と一致する特徴情報を有する組合せがある場合、当該組合せを検出して、処理を終了する。
【０１２９】
図１９は、抽出した第４図形１０ｄの線分図形及び特徴点を示す説明図である。図１９において、破線は抽出された第４図形１０ｄの一部を示している。図１９の例の場合、抽出された第４図形１０ｄの一部の特徴点各々に付与される特徴情報は、次のようになる。
１Ｓ３
２Ｗ３
３Ｎ１，３Ｅ２
【０１３０】
図１９に示した第４図形１０ｄの一部が有する特徴情報は、第２図形１０ｂの特徴情報と一致するので、ＣＰＵ１１は第４図形１０ｄの一部を検出して、処理を終了する。
【０１３１】
図２０、図２１及び図２２は、複数の参照パターンが含まれたライブラリデータと整合する複数のマスクパターンを検出する処理の手順の一例を示すフローチャートである。図２０、図２１及び図２２では、マスクパターンを回転又はミラー反転させる処理を省略している。ＣＰＵ１１は、複数の参照パターンと、複数のマスクパターンとを比較照合する場合、様々な参照パターン及びマスクパターンの組合せについて比較照合する。しかし、以下では、一の参照パターン及び一のマスクパターン並びに他の参照パターン及び他のマスクパターンの比較照合の場合に簡略化して処理の手順を説明する。
【０１３２】
ＣＰＵ１１は、ライブラリ１ｌからライブラリデータに含まれる複数の参照パターンを読み出す（ステップＳ３０１）。ＣＰＵ１１は、面積に応じて、読み出した参照パターンに識別情報を付与する（ステップＳ３０２）。ＣＰＵ１１は、一の参照パターンに対して、線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行する（ステップＳ３０３）。
【０１３３】
ＣＰＵ１１は、一の参照パターン及び他の参照パターンの位置関係から、他の参照パターンを包含する検索領域１０ｓの位置情報を算出する（ステップＳ３０４）。ＣＰＵ１１は、他の参照パターンに対して、線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行する（ステップＳ３０５）。ＣＰＵ１１は、一の参照パターンに係る特徴情報、検索領域１０ｓの位置情報及び他の参照パターンに係る特徴情報を関連付けてライブラリ１ｌに記憶する（ステップＳ３０６）。このとき、ＣＰＵ１１は、他の参照パターンを包含する検索領域１０ｓの位置情報と、他の参照パターンに係る特徴情報とが対であることを示す符号を、検索領域１０ｓの位置情報及び他の参照パターンに係る特徴情報に付加してもよい。
なお、ライブラリデータが複数の参照パターンを含む場合、３つ目以降の参照パターンについて、ステップＳ３０４〜ステップＳ３０６が繰り返される。
【０１３４】
ＣＰＵ１１は、検証データを入力する（ステップＳ３０７）。ＣＰＵ１１は、入力した検証データから複数のマスクパターンを選択する（ステップＳ３０８）。ＣＰＵ１１は、面積に応じて、選択した検証データに係る複数のマスクパターンに識別情報を付与する（ステップＳ３０９）。ＣＰＵ１１は、検証データに係る複数のマスクパターンに対して、線分変換処理及び特徴点抽出処理を夫々実行する（ステップＳ３１０）。ＣＰＵ１１は、検証データに係るマスクパターン毎に、抽出した特徴点各々に識別情報を付与する（ステップＳ３１１）。
【０１３５】
ＣＰＵ１１は、検証データに係るマスクパターン毎に、抽出した特徴点各々に基づいて、特徴点の組合せを複数生成する（ステップＳ３１２）。ステップＳ３１２において、ＣＰＵ１１は、生成した組合せからの特徴点の間引き、一の参照パターンのライブラリ特徴点数に等しい数の特徴点を有する組合せの抽出も行う。ＣＰＵ１１は、求めた各組合せの特徴点各々に識別情報を再付与する（ステップＳ３１３）。
【０１３６】
ＣＰＵ１１は、検証データに係る複数の組合せから、ライブラリデータに係る一の参照パターンの特徴点各々の特徴情報と一致する特徴情報を有する組合せがあるか否かを判定する（ステップＳ３１４）。ＣＰＵ１１は、検証データに係る複数の組合せから、ライブラリデータに係る一の参照パターンの特徴点各々の特徴情報と一致する特徴情報を有する組合せがないと判定した場合（ステップＳ３１４：ＮＯ）、処理を終了する。
ここでは、ライブラリデータに係る一の参照パターンの特徴点各々の特徴情報と一致する特徴情報を有し、かつ検証データに含まれる一のマスクパターンに係る特徴点各々の組合せが１つあるものとする。
なお、一致する組合せが複数ある場合、ＣＰＵ１１は一致する組合せの数だけ、以下の処理を繰り返す。
【０１３７】
ＣＰＵ１１は、検証データに係る複数の組合せから、ライブラリデータに係る一の参照パターンの特徴点各々の特徴情報と一致する特徴情報を有する組合せがあると判定した場合（ステップＳ３１４：ＹＥＳ）、次の処理を実行する。ＣＰＵ１１は、ライブラリ１ｌに検索領域１０ｓの位置情報が登録されているか否かを判定する（ステップＳ３１５）。ＣＰＵ１１は、ライブラリ１ｌに検索領域１０ｓの位置情報が登録されていないと判定した場合（ステップＳ３１５：ＮＯ）、処理を終了する。ＣＰＵ１１は、ライブラリ１ｌに検索領域１０ｓの位置情報が登録されていると判定した場合（ステップＳ３１５：ＹＥＳ）、ライブラリ１ｌから検索領域１０ｓの位置情報を読み出す（ステップＳ３１６）。
【０１３８】
ＣＰＵ１１は、読み出した検索領域１０ｓの位置情報を一のマスクパターンの特徴情報に当てはめて、検証データに含まれるマスクパターンの分布領域に検索領域１０ｓを設定する（ステップＳ３１７）。ＣＰＵ１１は、設定した検証データに係る検索領域１０ｓに、他のマスクパターンの一部又は全部が含まれるか否かを判定する（ステップＳ３１８）。ＣＰＵ１１は、設定した検証データに係る検索領域１０ｓに、他のマスクパターンの一部又は全部が含まれないと判定した場合（ステップＳ３１８：ＮＯ）、処理を終了する。ＣＰＵ１１は、設定した検証データに係る検索領域１０ｓに、他のマスクパターンの一部又は全部が含まれると判定した場合（ステップＳ３１８：ＹＥＳ）、検索領域１０ｓに含まれる他のマスクパターンの一部又は全部を抽出する（ステップＳ３１９）。
【０１３９】
ＣＰＵ１１は、抽出した他のマスクパターンの一部又は全部に対して、線分変換処理、特徴点抽出処理及び特徴情報付与処理を実行する（ステップＳ３２０）。ＣＰＵ１１は、抽出した他のマスクパターンの一部又は全部の特徴点各々に基づいて、特徴点の組合せを一又は複数生成する（ステップＳ３２１）。ステップＳ３２１において、ＣＰＵ１１は、生成した組合せからの特徴点の間引き、他の参照パターンのライブラリ特徴点数に等しい数の特徴点を有する組合せの抽出も行う。ＣＰＵ１１は、生成及び抽出した特徴点の組合せ毎に、特徴情報（識別情報及び方向情報）を付与する（ステップＳ３２２）。ＣＰＵ１１は、特徴情報を付与した組合せ毎に、ライブラリ１ｌに登録された他の参照パターンに係る特徴点各々の特徴情報と一致する特徴情報を有する組合せがあるか否かを判定する（ステップＳ３２３）。
【０１４０】
ＣＰＵ１１は、ライブラリ１ｌに登録された他の参照パターンに係る特徴点各々の特徴情報と一致する特徴情報を有する組合せがないと判定した場合（ステップＳ３２３：ＮＯ）、処理を終了する。ＣＰＵ１１は、ライブラリ１ｌに登録された他の参照パターンに係る特徴点各々の特徴情報と一致する特徴情報を有する組合せがあると判定した場合（ステップＳ３２３：ＹＥＳ）、あると判定した組合せを検出し（ステップＳ３２４）、処理を終了する。
【０１４１】
以下、上述とは異なる検索領域１０ｓの位置情報の表現について説明する。
上述では、検索領域１０ｓの位置情報を、第１図形１０ａの特徴点２を頂点とする矩形の２辺で表現した。しかし、第１図形１０ａの特徴点は、検索領域１０ｓの内部に位置してもよい。かかる場合、検索領域１０ｓの位置情報は、検索領域１０ｓの内部における第１図形１０ａの特徴点と、検索領域１０ｓの周上の点とを結ぶ線分の方向と長さとで表現される。
【０１４２】
図２３は、検索領域１０ｓの位置情報の他例を示す説明図である。図２３Ａは、第１図形１０ａに対応する線分図形と、検索領域１０ｓとを示す説明図である。図２３Ｂは、検索領域１０ｓの位置情報の他例の詳細を示す説明図である。図２３において、検索領域１０ｓは、破線の矩形で示されている。図２３Ａ及び図２３Ｂにおいて、検索領域１０ｓの縦幅をＡ、検索領域１０ｓの横幅をＢとする。
【０１４３】
ライブラリ１ｌには、第１図形１０ａ及び第２図形１０ｂが登録されているものとする。第１図形１０ａは、図１６Ａにおける第１図形１０ａと同一である。そのため、図２３における第１図形１０ａの線分図形は、図１７に示した第１図形１０ａの線分図形と同一である。他方、図２３における第２図形１０ｂは、図１６Ａにおける第２図形１０ｂと異なる。
【０１４４】
図２３における第２図形１０ｂは、Ｆ字状の第１図形１０ａの上部右側に位置する横長のＬ字状部分と、当該部分の略中央から下方に延びる曲尺状部分とを含む。曲尺状部分は、Ｌ字を反時計回りに９０度回転した形状に類似する。曲尺状部分は、横長のＬ字状部分の略中央から下方に延びる直線部分と、第１図形１０ａの右下方に位置する当該直線部分の下端から左側へ略直角に屈曲した底部をなす直線部分とを含む。第２図形１０ｂにおいて当該底部をなす直線部分は、第１図形１０ａの下方に位置する。
【０１４５】
第１図形１０ａの位置を基準にして第２図形１０ｂが包含される検索領域１０ｓの位置情報を算出するために、第１図形１０ａから抽出された特徴点の中から任意の１点を選択する。ここでは、第１図形１０ａの略中央に位置する特徴点４を、検索領域１０ｓの位置情報を算出するための基準点に選択するものとする。特徴点４は、図２３Ａ及び図２３Ｂに示すように、検索領域１０ｓの頂点ではなく、検索領域１０ｓの内部に位置する。そのため、特徴点４から隣り合う特徴点２、特徴点３及び特徴点５へ向かう線分の方向及び長さで、矩形をなす検索領域１０ｓの２辺の方向及び長さを表現することは好的ではない。
【０１４６】
特徴点４から検索領域１０ｓにて直交する２辺と夫々平行な２直線を引くことができる。当該２直線を夫々検索領域１０ｓの周で切断した２本の線分は、検索領域１０ｓの縦幅Ａ及び横幅Ｂ各々と同じ長さを有している。
【０１４７】
以下、上記２本の線分を夫々縦線分２０ｓ、横線分３０ｓと呼ぶ（図２３Ｂ参照）。特徴点４は、縦線分２０ｓと横線分３０ｓとが交差する交差点に対応する。また、特徴点４は、縦線分２０ｓの内分点であり、横線分３０ｓの内分点でもある。
【０１４８】
以下、特徴点４により縦線分２０ｓ及び横線分３０ｓが夫々内分された線分を線分ａ、線分ａ’線分ｂ、線分ｂ’と呼ぶ（図２３Ｂ参照）。線分ａ、線分ａ’、線分ｂ、線分ｂ’の長さを夫々ａ、ａ’、ｂ、ｂ’とした場合、Ａ、Ｂは夫々次のようになる。
Ａ＝ａ＋ａ’
Ｂ＝ｂ＋ｂ’
【０１４９】
いま、検索領域１０ｓの例えば横方向に着目する。
ｎ１、ｎ２、ｎ３、ｎ４を実数とした場合、第１図形１０ａの特徴点を用いて表した線分ｂ、ｂ’の長さは、夫々次のようになる。
ｂ  ＝特徴点１及び特徴点２の間の距離のｎ１倍
又は
ｂ  ＝特徴点３及び特徴点４の間の距離のｎ２倍
ｂ’＝特徴点１及び特徴点２の間の距離のｎ３倍
又は
ｂ’＝特徴点３及び特徴点４の間の距離のｎ４倍
【０１５０】
第１図形１０ａの特徴情報の表現を用いた場合、特徴点４から線分ｂ及び線分ｂ’へ向かう方向は、夫々次のようになる。
特徴点４から線分ｂへ向かう方向  ＝１Ｗ２又は３Ｗ４
特徴点４から線分ｂ’へ向かう方向＝２Ｅ１又は４Ｅ３
【０１５１】
従って、特徴点４を基準にして、第１図形１０ａの特徴情報の表現を用いて線分ｂ及び線分ｂ’の方向及び長さを表現した場合、線分ｂ及び線分ｂ’の方向及び長さは、夫々次のようになる。
線分ｂ  ＝特徴点４から１Ｗ２方向（左方向）へ向かう、特徴点１及び特徴点２の間の距離のｎ１倍の線分
又は
線分ｂ  ＝特徴点４から３Ｗ４方向（左方向）へ向かう、特徴点３及び特徴点４の間の距離のｎ２倍の線分
線分ｂ’＝特徴点４から２Ｅ１方向（右方向）へ向かう、特徴点１及び特徴点２の間の距離のｎ３倍の線分
又は
線分ｂ’＝特徴点４から４Ｅ３方向（右方向）へ向かう、特徴点３及び特徴点４の間の距離のｎ４倍の線分
【０１５２】
他方、検索領域１０ｓの例えば縦方向に着目し、特徴点４を基準にして、第１図形１０ａの特徴情報の表現を用いて線分ａ及び線分ａ’の方向及び長さを表現した場合、線分ａ及び線分ａ’の方向及び長さは、夫々次のようになる。ただし、ｎ５、ｎ６、ｎ７、ｎ８は、実数である。
線分ａ  ＝特徴点４から４Ｎ２方向（上方向）へ向かう、特徴点４及び特徴点２の間の距離のｎ５倍の線分
又は
線分ａ  ＝特徴点４から５Ｎ４方向（上方向）へ向かう、特徴点４及び特徴点５の間の距離のｎ６倍の線分
線分ａ’＝特徴点４から２Ｓ４方向（下方向）へ向かう、特徴点４及び特徴点２の間の距離のｎ７倍の線分
又は
線分ａ’＝特徴点４から４Ｓ５方向（下方向）へ向かう、特徴点４及び特徴点５の間の距離のｎ８倍の線分
【０１５３】
符号化した検索領域１０ｓの位置情報の他例の一般的な表現は、例えば次のようになる。
［頂点となる特徴点の識別情報］，［内分された線分の方向及び長さ］［倍率フラグ］［内分された線分の長さを特徴点間距離の倍率で示した数値］
【０１５４】
検索領域１０ｓの位置情報の他例を符号化して表現した場合、１つの具体例は、次のようになる。
４，４Ｎ２Ｍｎ５
４，４Ｓ５Ｍｎ８
４，３Ｗ４Ｍｎ２
４，４Ｅ３Ｍｎ４
【０１５５】
なお、検索領域１０ｓの位置情報は、座標で表現されてもよい。いま、図２３において、右方向をｘ軸方向、下方向をｙ軸方向とし、特徴点４の座標を（Ｘ１，Ｙ１）とする。
検索領域１０ｓの最小ｘ座標Ｘｍｉｎ、最大ｘ座標Ｘｍａｘ、最小ｙ座標Ｙｍｉｎ及び最大ｙ座標Ｙｍａｘの一例は、夫々次のようになる。
Ｘｍｉｎ＝Ｘ１−ｂ  ＝Ｘ１−（特徴点１及び特徴点２の間の距離×ｎ１）
Ｘｍａｘ＝Ｘ１＋ｂ’＝Ｘ１＋（特徴点２及び特徴点１の間の距離×ｎ３）
Ｙｍｉｎ＝Ｙ１−ａ  ＝Ｙ１−（特徴点４及び特徴点２の間の距離×ｎ５）
Ｙｍａｘ＝Ｙ１＋ａ’＝Ｙ１＋（特徴点４及び特徴点５の間の距離）×ｎ８）
【０１５６】
検出装置１０によれば、ライブラリ１ｌに登録された複数の参照パターンと一致又は類似する複数のマスクパターンを検出することができる。
単一図形ではなく、複数の参照パターンの組合せに一致又は類似する複数のマスクパターンを検出することにより、複数のマスクパターンに起因するエラー箇所を検出することができる。
【０１５７】
開示された実施の形態は、全ての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上述の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内での全ての変更が含まれることが意図される。
【０１５８】
また、各実施の形態で記載されている技術的特徴（構成要件）はお互いに組合せ可能であり、組み合わせすることにより、新しい技術的特徴を形成することができる。
【０１５９】
以上の実施の形態に関し、更に以下の付記を開示する。
【０１６０】
（付記１）
半導体装置の製造に用いるフォトマスクを形成する複数のマスクパターンから、予め用意した参照パターンと図形的特徴が一致又は類似するマスクパターンを検出する検出装置において、
前記マスクパターン及び参照パターンから複数の図形的な特徴点を夫々抽出する抽出部と、
該抽出部が夫々抽出した特徴点各々に、特徴点の識別情報及び該特徴点と隣り合う特徴点とを結ぶ線分の方向情報を前記マスクパターン及び参照パターン別に付与する付与部と、
該付与部が前記マスクパターン及び参照パターン別に付与した特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する検出部と
を備える
検出装置。
【０１６１】
（付記２）
前記抽出部は、
前記マスクパターン及び参照パターンを、内角が優角である角部をなす二辺を該角部と対向する二辺まで各々延長した延長線で複数の平行四辺形に夫々分割する分割部と、
前記延長線を介して隣接する複数の平行四辺形の中心点同士を結ぶ複数の線分を前記マスクパターン及び参照パターンに夫々付与する線分付与部と、
前記分割部が夫々分割した複数の平行四辺形の中心点を前記特徴点として前記マスクパターン及び参照パターン別に抽出する中心点抽出部と、
該中心点抽出部が抽出した複数の特徴点から、前記線分付与部が付与した複数の線分の内、同一方向の二線分のみが隣接する点に対応する特徴点を間引いた特徴点各々を、前記マスクパターン及び参照パターン別に抽出する特徴点抽出部と
を有し、
前記付与部は、前記特徴点抽出部が抽出した特徴点各々に、前記線分付与部が該特徴点を一端点として付与した線分の方向情報及び該特徴点の識別情報を前記マスクパターン及び参照パターン別に付与する
付記１に記載の検出装置。
【０１６２】
（付記３）
前記特徴点抽出部は、前記中心点抽出部が抽出した複数の特徴点から、前記線分付与部が付与した複数の線分から構成される線分図形にて端点、頂点又は該線分が交差する交差点を前記特徴点として抽出する
付記２に記載の検出装置。
【０１６３】
（付記４）
前記抽出部は、
前記マスクパターン及び参照パターンを、内角が優角である角部をなす二辺を該角部と対向する二辺まで各々延長した延長線で複数の平行四辺形に夫々分割する分割部と、
前記延長線を介して隣接する複数の平行四辺形の中心同士を結ぶ複数の線分を前記マスクパターン及び参照パターンに夫々付与する線分付与部と、
該線分付与部が夫々付与した複数の線分の両端点を前記特徴点として前記マスクパターン及び参照パターン別に抽出する両端点抽出部と、
該両端点抽出部が抽出した特徴点から、前記線分付与部が付与した複数の線分の内、同一方向の二線分のみが隣接する共有端点として該両端点抽出部により重複して抽出された特徴点を間引いた特徴点各々を、前記マスクパターン及び参照パターン別に抽出する特徴点抽出部と
を有し、
前記付与部は、前記特徴点抽出部が抽出した特徴点各々に、前記線分付与部が該特徴点を一端点として付与した線分の方向情報及び該特徴点の識別情報を前記マスクパターン及び参照パターン別に付与する
付記１に記載の検出装置。
【０１６４】
（付記５）
前記抽出部は、前記特徴点抽出部が抽出した前記マスクパターンにおける複数の特徴点から、該複数の特徴点の数以下の数の特徴点を選択し、選択した特徴点を用いた新たなマスクパターンの作成に必要な特徴点の組合せを生成する生成部を有し、
前記特徴点抽出部は、前記生成部が生成した組合せ毎に、前記特徴点を間引いた残りの特徴点各々を前記マスクパターンの特徴点として再抽出し、
前記付与部は、前記特徴点抽出部が再抽出した特徴点各々の数が該特徴点抽出部により抽出された前記参照パターンの特徴点各々の数と等しい場合、再抽出した特徴点各々に、前記識別情報及び方向情報を前記組合せ毎に付与し、
前記検出部は、前記付与部が前記マスクパターンにおける各組合せ及び参照パターン別に付与した特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
付記２から付記４までのいずれか一つに記載の検出装置。
【０１６５】
（付記６）
前記生成部は、前記マスクパターンにおける複数の特徴点から、該特徴点の数より１小さく、かつ前記特徴点抽出部が前記参照パターンから抽出した複数の特徴点の数以上の数の特徴点を選択し、選択した特徴点の一又は複数の組合せを生成する
付記５に記載の検出装置。
【０１６６】
（付記７）
前記参照パターンが予め記憶された記憶部を備え、
前記抽出部は前記記憶部が記憶する参照パターンから複数の図形的な特徴点を抽出する
付記１から付記６までのいずれか一つに記載の検出装置。
【０１６７】
（付記８）
前記参照パターン並びに該参照パターンに対する前記分割部、線分付与部、中心点抽出部、特徴点抽出部及び付与部による処理の結果が予め記憶された記憶部と、
前記特徴点抽出部が抽出した前記マスクパターンにおける複数の特徴点から、該特徴点の数より１小さく、かつ前記記憶部に記憶された前記参照パターンにおける複数の特徴点の数以上の数の特徴点を選択し、選択した特徴点を用いた新たなマスクパターンの作成に必要な一又は複数の特徴点の組合せを生成する生成部と
を備え、
前記特徴点抽出部は、前記生成部が生成した組合せ毎に、前記特徴点を間引いた残りの特徴点各々を前記マスクパターンの特徴点として再抽出し、
前記付与部は、前記特徴点抽出部が再抽出した特徴点の数が前記記憶部に記憶された前記参照パターンの特徴点の数と等しい場合、再抽出した特徴点各々に、前記識別情報及び方向情報を前記組合せ毎に付与し、
前記検出部は、前記付与部が前記マスクパターンにおける各組合せに付与した特徴点各々の識別情報及び方向情報並びに前記記憶部に予め記憶された参照パターンにおける特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
付記２又は付記４に記載の検出装置。
【０１６８】
（付記９）
前記マスクパターン及び参照パターンのいずれかを回転又はミラー反転させる回転反転部を備える
付記１から付記８までのいずれか一つに記載の検出装置。
【０１６９】
（付記１０）
複数の参照パターンに一致又は類似する複数のマスクパターンを検出すべく、一の参照パターンの位置に対して他の参照パターンが包含される領域の位置情報を算出する算出部と、
該算出部が算出した領域の位置情報並びに前記付与部が前記一及び他の参照パターンに夫々付与した特徴点各々の識別情報及び方向情報を関連付ける関連付部と、
前記検出部が前記一の参照パターンにおける特徴点各々の識別情報及び方向情報と一致する識別情報及び方向情報の特徴点各々を有する一のマスクパターンを検出した場合、前記関連付部が関連付けた前記位置情報の領域と対応するマスクパターンの領域に他のマスクパターンの一部又は全部が含まれるか否かを判定する判定部と、
該判定部が含まれると判定した場合、前記マスクパターンの領域に含まれる他のマスクパターンの一部又は全部を抽出するパターン抽出部と
を備え、
前記抽出部は前記パターン抽出部が抽出した他のマスクパターンの一部又は全部から複数の特徴点を抽出し、
前記付与部は前記抽出部が他のマスクパターンの一部又は全部から抽出した特徴点各々に識別情報及び方向情報を付与し、
前記検出部は、前記付与部が他のマスクパターンの一部又は全部並びに他の参照パターンにおける特徴点各々に夫々付与した識別情報及び方向情報に基づいて、図形的特徴が前記他の参照パターンに一致又は類似する他のマスクパターンを検出する
付記１から付記９までのいずれか一つに記載の検出装置。
【０１７０】
（付記１１）
前記算出部は前記一の参照パターンにおける任意の特徴点の位置、前記一の参照パターンにおける特徴点各々の識別情報及び方向情報並びに隣り合う特徴点間の距離に基づいて、前記領域の位置情報を算出する
付記１０に記載の検出装置。
【０１７１】
（付記１２）
記憶部を有するコンピュータに、半導体装置の製造に用いるフォトマスクを形成する複数のマスクパターンから、該記憶部に予め記憶された参照パターンと図形的特徴が一致又は類似するマスクパターンを検出する処理を実行させるプログラムにおいて、
前記マスクパターンから複数の図形的な特徴点を抽出し、
抽出した特徴点各々に、特徴点の識別情報及び該特徴点と隣り合う特徴点とを結ぶ線分の方向情報を前記マスクパターンに付与し、
前記マスクパターンに付与した特徴点各々の識別情報及び方向情報並びに前記記憶部に予め記憶された前記参照パターンの前記特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
処理をコンピュータに実行させるプログラム。
【０１７２】
（付記１３）
前記複数の図形的な特徴点を抽出する処理は、
前記マスクパターンを、内角が優角である角部をなす二辺を該角部と対向する二辺まで各々延長した延長線で複数の平行四辺形に夫々分割し、
前記延長線を介して隣接する複数の平行四辺形の中心点同士を結ぶ複数の線分を前記マスクパターンに付与し、
分割した複数の平行四辺形の中心点を前記特徴点として抽出し、
抽出した複数の特徴点から、付与した前記複数の線分の内、同一方向の二線分のみが隣接する点に対応する特徴点を間引いた特徴点各々を抽出し、
前記識別情報及び方向情報を付与する処理は、前記特徴点を間引いて抽出した特徴点各々に、該特徴点を一端点として付与した線分の方向情報及び該特徴点の識別情報を付与する
付記１２に記載のプログラム。
【０１７３】
（付記１４）
前記特徴点を間引きして特徴点各々を抽出する処理は、抽出した複数の特徴点から、付与した前記複数の線分から構成される線分図形にて端点、頂点又は該線分が交差する交差点を前記特徴点として抽出する
付記１３に記載のプログラム。
【０１７４】
（付記１５）
前記複数の図形的な特徴点を抽出する処理は、
前記特徴点を間引いて抽出した前記マスクパターンにおける複数の特徴点から、該複数の特徴点の数以下の数の特徴点を選択し、選択した特徴点を用いた新たなマスクパターンの作成に必要な特徴点の組合せを生成し、
生成した組合せ毎に、前記特徴点を間引いた残りの特徴点各々を前記マスクパターンの特徴点として再抽出し、
前記識別情報及び方向情報を付与する処理は、再抽出した特徴点各々の数が前記記憶部に予め記憶された参照パターンにおける特徴点各々の数と等しい場合、再抽出した前記特徴点各々に、前記識別情報及び方向情報を前記組合せ毎に付与し、
前記マスクパターンを検出する処理は、前記マスクパターンにおける各組合せに付与した特徴点各々の識別情報及び方向情報並びに前記記憶部に予め記憶された参照パターンにおける特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記参照パターンに一致又は類似するマスクパターンを検出する
付記１３又は付記１４に記載のプログラム。
【０１７５】
（付記１６）
前記組合せを生成する処理は、前記マスクパターンにおける複数の特徴点から、該特徴点の数より１小さく、かつ前記記憶部に予め記憶された参照パターンにおける複数の特徴点の数以上の特徴点を選択し、選択した特徴点の一又は複数の組合せを生成する
付記１５に記載のプログラム。
【０１７６】
（付記１７）
前記記憶部に予め記憶された複数の参照パターンに一致又は類似する複数のマスクパターンを検出すべく、一の参照パターンの位置に対して他の参照パターンが包含される領域の位置情報を予め算出し、
予め算出した領域の位置情報並びに前記一及び他の参照パターンに夫々付与した特徴点各々の識別情報及び方向情報を関連付けて前記記憶部に予め記憶し、
前記マスクパターンを検出する処理が前記記憶部に記憶された一の参照パターンにおける特徴点各々の識別情報及び方向情報と一致する識別情報及び方向情報の特徴点各々を有する一のマスクパターンを検出した場合、前記記憶部に予め関連付けて記憶した前記位置情報の領域と対応するマスクパターンの領域に他のマスクパターンの一部又は全部が含まれるか否かを判定し、
含まれると判定した場合、前記マスクパターンの領域に含まれる他のマスクパターンの一部又は全部を抽出し、
抽出した他のマスクパターンの一部又は全部から複数の特徴点を抽出し、
前記他のマスクパターンの一部又は全部から抽出した特徴点各々に識別情報及び方向情報を付与し、
前記他のマスクパターンの一部又は全部における特徴点各々の識別情報及び方向情報並びに前記記憶部に予め記憶された他の参照パターンにおける特徴点各々の識別情報及び方向情報に基づいて、図形的特徴が前記他の参照パターンに一致又は類似する他のマスクパターンを検出する
付記１２から付記１６までのいずれか一つに記載のプログラム。
【０１７７】
（付記１８）
前記領域の位置情報を算出する処理は、前記一の図形パターンにおける任意の特徴点の位置、前記一の参照パターンにおける特徴点各々の識別情報及び方向情報並びに隣り合う特徴点間の距離に基づいて、前記領域の位置情報を算出する
付記１７に記載のプログラム。
【０１７８】
（付記１９）
前記複数の図形的な特徴点を抽出する処理は、回転又はミラー反転させたマスクパターンから複数の図形的な特徴点を抽出する
付記１２から付記１８までのいずれか一つに記載のプログラム。
【符号の説明】
【０１７９】
１０    検出装置（コンピュータ）
１１    ＣＰＵ（抽出部、回転反転部、分割部、線分付与部、両端点抽出部、中心点抽出部、特徴点抽出部、生成部、付与部、検出部、算出部、関連付部、判定部、パターン抽出部）
１４    ハードディスク（記憶部）
４０    抽出部
４１    回転反転部
４２    分割部
４３    線分付与部
４４    両端点抽出部
４５    中心点抽出部
４６    特徴点抽出部
４７    生成部
５０    付与部
６０    検出部
８０    算出部
９０    関連付部
１００  判定部
１Ｐ    プログラム
１１０  パターン抽出部
１ｌ    ライブラリ
【図１】
2014228801.tif 000003
【図２】
2014228801.tif 000004
【図３】
2014228801.tif 000005
【図４】
2014228801.tif 000006
【図５】
2014228801.tif 000007
【図６】
2014228801.tif 000008
【図７】
2014228801.tif 000009
【図８】
2014228801.tif 000010
【図９】
2014228801.tif 000011
【図１０】
2014228801.tif 000012
【図１１】
2014228801.tif 000013
【図１２】
2014228801.tif 000014
【図１３】
2014228801.tif 000015
【図１４】
2014228801.tif 000016
【図１５】
2014228801.tif 000017
【図１６】
2014228801.tif 000018
【図１７】
2014228801.tif 000019
【図１８】
2014228801.tif 000020
【図１９】
2014228801.tif 000021
【図２０】
2014228801.tif 000022
【図２１】
2014228801.tif 000023
【図２２】
2014228801.tif 000024
【図２３】
2014228801.tif 000025