(57)【要約】【課題】レイアウトパターンの類似性を適切に評価できるようにする。【解決手段】プロセッサ２は、半導体集積回路の設計データ１１に含まれるレイアウトパターン１２ｐ１〜１２ｐｎのそれぞれの第１の端点、第１の交点または第１の屈曲部に、生成位置の第１の種類情報が割り当てられた第１の特徴点（たとえば、特徴点１３ａ〜１３ｆ）を生成し、抽出対象パターン１５の第２の端点、第２の交点または第２の屈曲部に予め生成されている、生成位置の第２の種類情報が割り当てられた第２の特徴点（図１の例では特徴点１６ａ〜１６ｅ）と第１の特徴点とを比較し、第２の特徴点に対応する第１の特徴点（図１の例では特徴点１３ａ，１３ｂ，１３ｄ〜１３ｆ）をもつレイアウトパターン１２ｐ１を、複数のレイアウトパターン１２ｐ１〜１２ｐｎから抽出する。【選択図】図１
2016201006.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサが、半導体集積回路の設計データに含まれる複数のレイアウトパターンのそれぞれの第１の端点、第１の交点または第１の屈曲部に、生成位置の第１の種類情報が割り当てられた第１の特徴点を生成し、
前記プロセッサが、抽出対象パターンの第２の端点、第２の交点または第２の屈曲部に予め生成されている、生成位置の第２の種類情報が割り当てられた第２の特徴点と前記第１の特徴点とを比較し、
前記プロセッサが、前記第２の特徴点に対応する前記第１の特徴点をもつレイアウトパターンを、前記複数のレイアウトパターンから抽出する、
ことを特徴とするレイアウトパターン抽出方法。
【請求項２】
前記抽出対象パターンの前記第２の特徴点には、前記第１の特徴点と対応しているか否かの判定基準の重み値が割り当てられていることを特徴とする請求項１に記載のレイアウトパターン抽出方法。
【請求項３】
ホットスポットに近い前記第２の特徴点ほど、大きい前記重み値が割り当てられていることを特徴とする請求項２に記載のレイアウトパターン抽出方法。
【請求項４】
前記プロセッサは、前記複数のレイアウトパターンの各コーナ間を一方向で結ぶ複数のベクトルを生成し、生成した前記複数のベクトルの方向に基づき、前記第１の端点、前記第１の交点または前記第１の屈曲部を検出することを特徴とする請求項１乃至３の何れか一項に記載のレイアウトパターン抽出方法。
【請求項５】
前記プロセッサは、同様の性質をもつ複数の他の抽出対象パターンを選択し、前記複数の他の抽出対象パターンのそれぞれにおいて、第３の端点、第３の交点または第３の屈曲部に、生成位置の第３の種類情報が割り当てられた第３の特徴点を生成し、前記複数の他の抽出対象パターン間で、所定の領域内にある前記第３の特徴点同士をマージして、１つの前記第２の特徴点を生成し、前記領域内にある前記第３の特徴点の位置と前記第３の種類情報に基づき、前記重み値を決定することを特徴とする請求項２に記載のレイアウトパターン抽出方法。
【請求項６】
前記プロセッサは、前記複数のレイアウトパターンの第１のコーナと第２のコーナ間の距離と閾値とを比較し、前記距離が前記閾値以下のとき、前記第１のコーナと前記第２のコーナ間を結ぶベクトルを、前記第１の端点、前記第２の交点または前記第１の屈曲部の検出に用いる前記複数のベクトルから除外する、ことを特徴とする請求項４に記載のレイアウトパターン抽出方法。
【請求項７】
半導体集積回路の設計データに含まれる複数のレイアウトパターンのそれぞれの第１の端点、第１の交点または第１の屈曲部に、生成位置の第１の種類情報が割り当てられた第１の特徴点を生成する特徴点生成部と、
抽出対象パターンの第２の端点、第２の交点または第２の屈曲部に予め生成されている、生成位置の第２の種類情報が割り当てられた第２の特徴点と前記第１の特徴点とを比較する比較部と、
前記第２の特徴点に対応する前記第１の特徴点をもつレイアウトパターンを、前記複数のレイアウトパターンから抽出する抽出部と、
を有することを特徴とするレイアウトパターン抽出装置。
【請求項８】
半導体集積回路の設計データに含まれる複数のレイアウトパターンのそれぞれの第１の端点、第１の交点または第１の屈曲部に、生成位置の第１の種類情報が割り当てられた第１の特徴点を生成し、
抽出対象パターンの第２の端点、第２の交点または第２の屈曲部に予め生成されている、生成位置の第２の種類情報が割り当てられた第２の特徴点と前記第１の特徴点とを比較し、
前記第２の特徴点に対応する前記第１の特徴点をもつレイアウトパターンを、前記複数のレイアウトパターンから抽出する、
処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レイアウトパターン抽出方法、レイアウトパターン抽出装置及びプログラムに関する。
【背景技術】
【０００２】
半導体集積回路の設計データには、セルや配線パターン、トランジスタのゲートパターンなど複数の図形パターン（以下レイアウトパターンという）が含まれる。従来、これら複数のレイアウトパターンから、マスク転写時のプロセスマージン不足などにより断線やショートなどの不良が予測される箇所（ホットスポット）が発生するレイアウトパターンを予め抽出することが行われている。
【０００３】
たとえば、レイアウトパターンの辺の長さ、複数のレイアウトパターン間の間隔、頂点の位置に基づきパターンマッチング技術によりレイアウトパターンの識別が行われ、目的のレイアウトパターンの抽出が行われる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−９４２３７号公報
【特許文献２】特開平９−１９２１０６号公報
【特許文献３】特開平６−２８８７３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、辺の長さや頂点の位置が異なるレイアウトパターンを、類似パターンとして抽出することは、従来の手法では困難であった。そのため、たとえば、辺の長さや頂点の位置が異なるものの同様のホットスポットが生じるようなレイアウトパターンを類似パターンとして分類することができず、レイアウトパターンの類似性を適切に評価できないという問題があった。
【０００６】
したがって、レイアウトパターンの類似性を適切に評価可能にすることが課題である。
【課題を解決するための手段】
【０００７】
発明の一観点によれば、プロセッサが、半導体集積回路の設計データに含まれる複数のレイアウトパターンのそれぞれの第１の端点、第１の交点または第１の屈曲部に、生成位置の第１の種類情報が割り当てられた第１の特徴点を生成し、前記プロセッサが、抽出対象パターンの第２の端点、第２の交点または第２の屈曲部に予め生成されている、生成位置の第２の種類情報が割り当てられた第２の特徴点と前記第１の特徴点とを比較し、前記プロセッサが、前記第２の特徴点に対応する前記第１の特徴点をもつレイアウトパターンを、前記複数のレイアウトパターンから抽出するレイアウトパターン抽出方法が提供される。
【０００８】
また、発明の一観点によれば、半導体集積回路の設計データに含まれる複数のレイアウトパターンのそれぞれの第１の端点、第１の交点または第１の屈曲部に、生成位置の第１の種類情報が割り当てられた第１の特徴点を生成する特徴点生成部と、抽出対象パターンの第２の端点、第２の交点または第２の屈曲部に予め生成されている、生成位置の第２の種類情報が割り当てられた第２の特徴点と前記第１の特徴点とを比較する比較部と、前記第２の特徴点に対応する前記第１の特徴点をもつレイアウトパターンを、前記複数のレイアウトパターンから抽出する抽出部と、を有するレイアウトパターン抽出装置が提供される。
【０００９】
また、発明の一観点によれば、半導体集積回路の設計データに含まれる複数のレイアウトパターンのそれぞれの第１の端点、第１の交点または第１の屈曲部に、生成位置の第１の種類情報が割り当てられた第１の特徴点を生成し、抽出対象パターンの第２の端点、第２の交点または第２の屈曲部に予め生成されている、生成位置の第２の種類情報が割り当てられた第２の特徴点と前記第１の特徴点とを比較し、前記第２の特徴点に対応する前記第１の特徴点をもつレイアウトパターンを、前記複数のレイアウトパターンから抽出する、処理をコンピュータに実行させるプログラムが提供される。
【発明の効果】
【００１０】
開示のレイアウトパターン抽出方法、レイアウトパターン抽出装置及びプログラムによれば、レイアウトパターンの類似性を比較的適切に評価できるようになる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態のレイアウトパターン抽出方法及びレイアウトパターン抽出装置の一例を示す図である。
【図２】第１の実施の形態のレイアウトパターン抽出装置の一例の機能ブロック図である。
【図３】第２の実施の形態のレイアウトパターン抽出装置の一例を示す図である。
【図４】第２の実施の形態のレイアウトパターン抽出方法の一例の処理の流れを示すフローチャートである。
【図５】端点に生成される特徴点の一例を示す図である。
【図６】Ｌ字状の屈曲部に生成される特徴点の一例を示す図である。
【図７】Ｔ字状の屈曲部に生成される特徴点の一例を示す図である。
【図８】交点に生成される特徴点の一例を示す図である。
【図９】段差部分に生成される特徴点の一例を示す図である。
【図１０】抽出対象パターンの特徴点と重み値の設定例を示す図である。
【図１１】特徴点が生成されたレイアウトパターンの一例を示す図である。
【図１２】特徴点が生成されたレイアウトパターンの他の例を示す図である。
【図１３】抽出対象パターンの一例を示す図である。
【図１４】コーナ座標情報の一例を示す図である。
【図１５】図形ベクトルの一例を示す図である。
【図１６】生成された図形ベクトル情報の一例を示す図である。
【図１７】特徴ベクトル情報の一例を示す図である。
【図１８】特徴ベクトル変換情報の一例を示す図である。
【図１９】特徴点と単位ベクトルの生成例を示す図である。
【図２０】抽出対象パターンと同様の特性をもつレイアウトパターンの一例を示す図である。
【図２１】抽出対象パターンと同様の特性をもつレイアウトパターンの他の例を示す図である。
【図２２】ライブラリ作成処理の一例の流れを示すフローチャートである。
【図２３】サーチエリアの設定例を示す図である。
【図２４】マージ対象の特徴点の一例を示す図である。
【図２５】マージ処理で得られた特徴点とその特徴点に割り当てられる情報の一例を示す図である。
【図２６】ライブラリへの特徴点の登録例を示す図である。
【図２７】レイアウトパターンの抽出結果の一例を示す画面表示例である。
【図２８】第３の実施の形態のレイアウトパターン抽出方法の一例の処理の流れを示すフローチャートである。
【図２９】連続した３つの図形ベクトルの一例を示す図である。
【図３０】ＯＰＣ後のレイアウトパターンの抽出結果の一例を示す画面表示例である。
【発明を実施するための形態】
【００１２】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
（第１の実施の形態）
図１は、第１の実施の形態のレイアウトパターン抽出方法及びレイアウトパターン抽出装置の一例を示す図である。
【００１３】
また、図２は、第１の実施の形態のレイアウトパターン抽出装置の一例の機能ブロック図である。
レイアウトパターン抽出装置１は、たとえば、コンピュータであり、プロセッサ２と記憶部３を有している。プロセッサ２は、記憶部３に記憶されているデータ及びプログラムに基づき、図２に示すような、特徴点生成部２ａ、比較部２ｂ、抽出部２ｃの機能を実現する。記憶部３は、プロセッサ２が実行するプログラムや、半導体集積回路の設計データ１１やライブラリ１４などの各種データを記憶する。
【００１４】
設計データ１１には、半導体集積回路の配線パターン、ゲートパターン、セルパターンなどの複数のレイアウトパターン１２ｐ１〜１２ｐｎが含まれている。
ライブラリ１４には、抽出対象パターン１５が含まれている。本実施の形態のレイアウトパターン抽出方法では、抽出対象パターン１５に類似するものが、複数のレイアウトパターン１２ｐ１〜１２ｐから抽出される。なお、抽出対象パターン１５は複数あってもよい。
【００１５】
以下、上記のようなレイアウトパターン抽出装置１を用いたレイアウトパターン抽出方法の一例を、図１、図２を用いて説明する。
特徴点生成部２ａは、半導体集積回路の設計データ１１に含まれる複数のレイアウトパターン１２ｐ１〜１２ｐｎのそれぞれの端点、交点または屈曲部に、生成位置の種類を示す種類情報が割り当てられた特徴点を生成する（ステップＳ１）。なお、端点、交点または屈曲部に生成される特徴点には、設計データ１１から得られる、位置を示す座標情報も割り当てられていることはいうまでもない。
【００１６】
端点は、レイアウトパターンの先端の点であり、たとえば、先端における隣接する２つのコーナ（頂点）の中点として定義される。図１に示すレイアウトパターン１２ｐ１では、特徴点１３ａ，１３ｂ，１３ｃ，１３ｄが、端点に生成されたものである。
【００１７】
屈曲部はレイアウトパターンが折れ曲がっている箇所であり、図１に示すレイアウトパターン１２ｐ１では、特徴点１３ｅ，１３ｆが、屈曲部に生成されたものである（特徴点１３ｆは、Ｔ字状の屈曲部に生成されている）。
【００１８】
交点はレイアウトパターンが交差している箇所である（図８参照）。
端点、屈曲部及び交点は、レイアウトパターンの各コーナ間を一方向（たとえば、時計回りまたは反時計回り）で結ぶ複数のベクトルの方向に基づき検出されるが、その説明は後述する。
【００１９】
種類情報は、特徴点の生成位置の種類、つまり、生成位置が、端点、交点または屈曲部であるかを示す情報である。種類情報には、特徴点の生成位置が屈曲部の場合は、たとえば、Ｔ字状の屈曲部か、Ｌ字状の屈曲部か、などの曲がり方の情報も含む。また、特徴点の生成位置が、特徴点１３ａ，１３ｂのように上向きに伸びるパターンの先端の端点にあるのか、特徴点１３ｄのように下向きに伸びるパターンの先端の端点にあるのかを示す方向情報を種類情報が含んでいてもよい。屈曲部に生成される特徴点に割り当てる種類情報についても、屈曲部の曲がり方向に関する情報を含んでいてもよい。この方向に関する情報は、各特徴点を始点とする単位ベクトルの向きとして表現される。単位ベクトルの生成方法については後述する。
【００２０】
次に、比較部２ｂは、たとえば、ライブラリ１４に登録されている抽出対象パターン１５の端点、交点または屈曲部に予め生成されていて、上記のような種類情報が割り当てられている特徴点と、ステップＳ１の処理で生成した特徴点とを比較する（ステップＳ２）。
【００２１】
そして、抽出部２ｃは、抽出対象パターン１５の特徴点に対応する特徴点をもつレイアウトパターンを、複数のレイアウトパターン１２ｐ１〜１２ｐｎから抽出する（ステップＳ３）。
【００２２】
たとえば、抽出対象パターン１５では、端点に特徴点１６ａ，１６ｂ，１６ｃが生成されており、屈曲部に特徴点１６ｄ，１６ｅが生成されている。レイアウトパターン１２ｐ１は、抽出対象パターン１５の特徴点１６ａ〜１６ｅに対応した（たとえば、位置（座標）や生成位置の種類が一致している）特徴点１３ａ，１３ｂ，１３ｄ〜１３ｆを有しているため、抽出される。
【００２３】
なお、レイアウトパターン１２ｐ１の特徴点１３ｆと、抽出対象パターン１５の特徴点１６ｅは、曲がり方の異なる屈曲部に生成されているため種類情報が異なるが、上記の例では、位置が同じであるため対応している（一致している）ものとしている。しかし、抽出部２ｃは、位置が同じでも種類情報が異なっている場合には、両特徴点は対応していないものと判定して、その特徴点を有するレイアウトパターンについては抽出対象としないようにしてもよい。
【００２４】
また、抽出対象パターンの各特徴点には、レイアウトパターンの特徴点と対応（一致）するか否かの判定基準の厳しさを示す複数の重み値の何れかが割り当てられていてもよい。たとえば、抽出対象パターンにおいて、ホットスポットの近くに生成されている特徴点ほど厳しい判定基準を示す重み値が割り当てられるようにしてもよい。
【００２５】
また、回転や反転したときに抽出対象パターンの特徴点と位置が一致する特徴点をもつようなレイアウトパターンについても抽出されるようにしてもよい。
以上のようなレイアウトパターン抽出方法によれば、設計データから抽出対象パターンと類似するものを抽出する際、抽出対象パターンと対応する端点や屈曲部などに生成された特徴点をもつレイアウトパターンが抽出される。このため、辺の長さや頂点が異なるレイアウトパターンでも抽出対象となる。これにより、頂点や辺の長さは異なるが、同様の性質をもつ（たとえば、同様のホットスポットが発生する）レイアウトパターンを抽出し、分類でき、レイアウトパターンの類似性を適切に評価できるようになる。
【００２６】
また、特徴点を用いて比較が行われるため、元のレイアウトパターンの図形情報から検索するよりも、高速に検索、分類が可能である。
（第２の実施の形態）
以下、第２の実施の形態のレイアウトパターン抽出方法及びレイアウトパターン抽出装置の一例を示す。
【００２７】
図３は、第２の実施の形態のレイアウトパターン抽出装置の一例を示す図である。
レイアウトパターン抽出装置は、たとえば、コンピュータ２０であり、プロセッサ２１によって装置全体が制御されている。プロセッサ２１には、バス２９を介してＲＡＭ（Random Access Memory）２２と複数の周辺機器が接続されている。プロセッサ２１は、マルチプロセッサであってもよい。プロセッサ２１は、たとえばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、またはＰＬＤ（Programmable Logic Device）である。またプロセッサ２１は、ＣＰＵ、ＭＰＵ、ＤＳＰ、ＡＳＩＣ、ＰＬＤのうちの２以上の要素の組み合わせであってもよい。
【００２８】
ＲＡＭ２２は、コンピュータ２０の主記憶装置として使用される。ＲＡＭ２２には、プロセッサ２１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ２２には、プロセッサ２１による処理に必要な各種データが格納される。
【００２９】
バス２９に接続されている周辺機器としては、ＨＤＤ（Hard Disk Drive）２３、グラフィック処理装置２４、入力インタフェース２５、光学ドライブ装置２６、機器接続インタフェース２７及びネットワークインタフェース２８がある。
【００３０】
ＨＤＤ２３は、内蔵したディスクに対して、磁気的にデータの書き込み及び読み出しを行う。ＨＤＤ２３は、コンピュータ２０の補助記憶装置として使用される。ＨＤＤ２３には、ＯＳのプログラム、アプリケーションプログラム、及び各種データが格納される。なお、補助記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００３１】
グラフィック処理装置２４には、モニタ２４ａが接続されている。グラフィック処理装置２４は、プロセッサ２１からの命令にしたがって、画像をモニタ２４ａの画面に表示させる。モニタ２４ａとしては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００３２】
入力インタフェース２５には、キーボード２５ａとマウス２５ｂとが接続されている。入力インタフェース２５は、キーボード２５ａやマウス２５ｂから送られてくる信号をプロセッサ２１に送信する。なお、マウス２５ｂは、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００３３】
光学ドライブ装置２６は、レーザ光などを利用して、光ディスク２６ａに記録されたデータの読み取りを行う。光ディスク２６ａは、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２６ａには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００３４】
機器接続インタフェース２７は、コンピュータ２０に周辺機器を接続するための通信インタフェースである。たとえば機器接続インタフェース２７には、メモリ装置２７ａやメモリリーダライタ２７ｂを接続することができる。メモリ装置２７ａは、機器接続インタフェース２７との通信機能を搭載した記録媒体である。メモリリーダライタ２７ｂは、メモリカード２７ｃへのデータの書き込み、またはメモリカード２７ｃからのデータの読み出しを行う装置である。メモリカード２７ｃは、カード型の記録媒体である。
【００３５】
ネットワークインタフェース２８は、ネットワーク２８ａに接続されている。ネットワークインタフェース２８は、ネットワーク２８ａを介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００３６】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお、図１に示した第１の実施の形態のレイアウトパターン抽出装置１も、図３に示したコンピュータ２０と同様のハードウェアにより実現することができる。
【００３７】
コンピュータ２０は、たとえばコンピュータ読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施の形態の処理機能を実現する。コンピュータ２０に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。たとえば、コンピュータ２０に実行させるプログラムをＨＤＤ２３に格納しておくことができる。プロセッサ２１は、ＨＤＤ２３内のプログラムの少なくとも一部をＲＡＭ２２にロードし、プログラムを実行する。またコンピュータ２０に実行させるプログラムを、光ディスク２６ａ、メモリ装置２７ａ、メモリカード２７ｃなどの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、たとえばプロセッサ２１からの制御により、ＨＤＤ２３にインストールされた後、実行可能となる。またプロセッサ２１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００３８】
（レイアウトパターン抽出方法の一例）
図４は、第２の実施の形態のレイアウトパターン抽出方法の一例の処理の流れを示すフローチャートである。
【００３９】
コンピュータ２０において、プロセッサ２１は、ＨＤＤ２３に格納されたプログラムを読み出してＲＡＭ２２上に展開して、たとえば、図４に示すような各ステップの処理を実行する。
【００４０】
レイアウトパターン抽出処理が開始すると、プロセッサ２１は、まず、たとえば、ＨＤＤ２３に記憶された設計データやライブラリなどの各種データを読み込む（ステップＳ１０）。
【００４１】
そして、プロセッサ２１は、設計データに含まれる複数のレイアウトパターンのそれぞれにおいて、特徴点を生成する（ステップＳ１１）。
以下特徴点の生成例を説明する。
【００４２】
（特徴点の生成例）
図５は、端点に生成される特徴点の一例を示す図である。
プロセッサ２１は、レイアウトパターン３０の隣接するコーナ間を一方向で結ぶベクトル（以下図形ベクトルと呼ぶ）３１ａ，３１ｂ，３１ｃを生成する。図５の例では、図形ベクトル３１ａ，３１ｃの方向が逆向きである。そのため、プロセッサ２１は、このような方向関係の図形ベクトル３１ａ，３１ｃがある箇所に、２つのコーナがあると認識する。
【００４３】
そしてそのコーナ間の距離が所定の閾値よりも短い場合、プロセッサ２１は、２つのコーナの中点を端点と判定し、その端点に特徴点３２を生成する。また、プロセッサ２１は、図形ベクトル３１ｃと同じ向きで、特徴点３２を始点とする単位ベクトル３３を発生する。
【００４４】
図６は、Ｌ字状の屈曲部に生成される特徴点の一例を示す図である。
図６のレイアウトパターン３５では、図形ベクトル３６ａ，３６ｂ，３６ｃ，３６ｄが生成されている。ここで、図形ベクトル３６ａ，３６ｄは方向が逆向きであり、図形ベクトル３６ｂ，３６ｃも方向が逆向きである。このような方向関係の図形ベクトル３６ａ〜３６ｄがある場合、プロセッサ２１は、Ｌ字状の内側のコーナと外側のコーナの距離が所定の閾値よりも短い場合、両コーナの中点に特徴点３７を生成する。また、プロセッサ２１は、特徴点３７から内側のコーナに向けて単位ベクトル３８を発生する。
【００４５】
図７は、Ｔ字状の屈曲部に生成される特徴点の一例を示す図である。
図７のレイアウトパターン４０では、図形ベクトル４１ａ，４１ｂ，４１ｃ，４１ｄが生成されている。ここで、図形ベクトル４１ａ，４１ｄは方向が下向きであり、図形ベクトル４１ｂは左向き、図形ベクトル４１ｃは方向が右向きである。このような方向関係の図形ベクトル４１ａ〜４１ｄがある場合、プロセッサ２１は、Ｔ字状の内側の２つのコーナの距離が所定の閾値よりも短い場合、両コーナの中点に特徴点４２を生成する。また、プロセッサ２１は、図形ベクトル４１ｂと同じ方向で、特徴点４２から単位ベクトル４３を発生する。
【００４６】
図８は、交点に生成される特徴点の一例を示す図である。なお、交点は、十字状の屈曲部ということもできる。
図８のレイアウトパターン４５では、図形ベクトル４６ａ，４６ｂ，４６ｃ，４６ｄ，４６ｅ，４６ｆ，４６ｇ，４６ｈが生成されている。ここで、図形ベクトル４６ａ〜４６ｈの方向関係やコーナ間の距離より、プロセッサ２１は、４つのＴ字状の屈曲部があると認識し、特徴点４７ａ，４７ｂ，４７ｃ，４７ｄと単位ベクトル４８ａ，４８ｂ，４８ｃ，４８ｄを生成する。
【００４７】
さらにプロセッサ２１は、Ｔ字状の屈曲部に生成された４つの特徴点４７ａ〜４７ｄが、所定の広さの領域内に集合している場合には、特徴点４７ａ〜４７ｄを十字に結ぶ線の交点に特徴点４９を生成する。特徴点４９の生成後は、特徴点４７ａ〜４７ｄについては削除してもよい。
【００４８】
図９は、段差部分に生成される特徴点の一例を示す図である。
図９のレイアウトパターン５０では、図形ベクトル５１ａ，５１ｂ，５１ｃ，５１ｄ，５１ｅ，５１ｆ，５１ｇが生成されている。これらの図形ベクトル５１ａ〜５１ｇの方向関係より、図９に示すような段差部分は、１つのＬ字状の屈曲部と２つのＴ字状の屈曲部の組み合わせと判定される。そのため、前述の処理により２つのＴ字状の屈曲部には、特徴点５２ａ，５２ｂと単位ベクトル５３ａ，５３ｂが生成され、Ｌ字状の屈曲部には特徴点５２ｃと単位ベクトル５３ｃが生成される。
【００４９】
以上のように生成された特徴点には、座標と、生成位置の種類情報が割り当てられている。種類情報には、たとえば、特徴点が、端点、Ｌ字状の屈曲部、Ｔ字状の屈曲部、交点のどこに生成されているかを示す情報と、単位ベクトルの向きの情報を含む。
【００５０】
ステップＳ１１の処理が終わると、プロセッサ２１は、ライブラリに登録されている抽出対象パターンの特徴点と、ステップＳ１１の処理で生成したレイアウトパターンの特徴点との比較処理を行う。
【００５１】
以下の説明では、抽出対象パターンの各特徴点には、１００，５０，８０の何れかの重み値が割り当てられているものとする。重み値は、レイアウトパターンの特徴点と一致するか否かの判定基準の厳しさを示すものであり、値が大きいほど、判定基準は厳しい。たとえば、抽出対象パターンにおいて、ホットスポットの近くに生成された特徴点ほど、大きい重み値が割り当てられている。
【００５２】
図１０は、抽出対象パターンの特徴点と重み値の設定例を示す図である。
抽出対象パターン６０には、２つの端点に特徴点６１ａ，６１ｂが生成されており、２つのＬ字型の屈曲部に特徴点６１ｃ，６１ｄが生成されている。また、各特徴点６１ａ〜６１ｄを始点とした単位ベクトル６２ａ，６２ｂ，６２ｃ，６２ｄが生成されている。
【００５３】
各特徴点６１ａ〜６１ｄには、座標、種類情報、重み値が割り当てられている。
特徴点６１ａには、情報（ｘ１，ｙ１，Ｉ，下，５０）が割り当てられている。“ｘ１”，“ｙ１”は、ｘ座標の値とｙ座標の値を示し、“Ｉ”は端点に生成された特徴点であることを示している。また“下”は、単位ベクトル６２ａの向きであり、“５０”は重み値を示している。
【００５４】
特徴点６１ｂには、情報（０，ｙ２，Ｉ，上，８０）が割り当てられている。“０”，“ｙ２”は、ｘ座標の値とｙ座標の値を示し、“Ｉ”は端点に生成された特徴点であることを示している。また“上”は、単位ベクトル６２ｂの向きであり、“８０”は重み値を示している。
【００５５】
特徴点６１ｃには、情報（ｘ１，０，Ｌ，右上，１００）が割り当てられている。“ｘ１”，“０”は、ｘ座標の値とｙ座標の値を示し、“Ｌ”はＬ字状の屈曲部に生成された特徴点であることを示している。また“右上”は、単位ベクトル６２ｃの向きであり、“１００”は重み値を示している。
【００５６】
特徴点６１ｄには、情報（０，０，Ｌ，左下，１００）が割り当てられている。“０”，“０”は、ｘ座標の値とｙ座標の値を示し、“Ｌ”はＬ字状の屈曲部に生成された特徴点であることを示している。また“左下”は、単位ベクトル６２ｄの向きであり、“１００”は重み値を示している。
【００５７】
なお、上記の例では、端点またはＬ字状の屈曲部に生成される特徴点に割り当てられる種類情報を“Ｉ”、“Ｌ”としたが、交点またはＴ字状の屈曲部に生成される特徴点に割り当てられる種類情報については、たとえば、“Ｘ”、“Ｔ”などとする。
【００５８】
このような抽出対象パターン６０からマスクパターンを生成する場合、ホットスポット６３が発生するものとする。上記の例では、ホットスポット６３に比較的近い特徴点６１ｃ，６１ｄには、重み値として１００が設定されている。そして、たとえば、特徴点６１ａには、重み値として５０、特徴点６１ｂには、重み値として８０が設定されている。
【００５９】
なお、各特徴点６１ａ〜６１ｄの座標は、ホットスポット６３を原点（０，０）として割り当てられていてもよい。
プロセッサ２１は、各レイアウトパターンに対して、抽出対象パターンにおける重み値が１００の特徴点と一致する箇所（特徴点）があるか否かを判定する（ステップＳ１２）。
【００６０】
以下、図１０に示した抽出対象パターン６０の類似パターンを抽出する例を説明する。
たとえば、プロセッサ２１は、設計データ（レイアウトデータ）を探索して、図１０に示したような重み値が１００の特徴点６１ｄの種類情報と一致する特徴点をもつレイアウトパターンを探す。このとき、プロセッサ２１は、抽出対象パターン６０を、たとえば、抽出対象パターン６０の重心を中心にして回転させたり、反転させたりしてもよい。その場合、特徴点６１ａ〜６１ｄの座標や種類情報（単位ベクトルの方向）は変わる。
【００６１】
図１１は、特徴点が生成されたレイアウトパターンの一例を示す図である。
図１１に示すようなレイアウトパターン７０では、前述した手法により、２つの端点とＬ字状の屈曲部に特徴点７１ａ，７１ｂ，７１ｃが生成されており、さらに、各特徴点７１ａ〜７１ｃを始点とした単位ベクトル７２ａ，７２ｂ，７２ｃが生成されている。
【００６２】
たとえば、特徴点７１ｃの種類情報が、図１０の抽出対象パターン６０の特徴点６１ｄの種類情報と一致する場合、プロセッサ２１は、特徴点７１ｃの座標を、特徴点６１ｄの座標（０，０）に合わせる。
【００６３】
そして、プロセッサ２１は、検索エリア８０を設定して、検索エリア８０内のレイアウトパターン７０の他の特徴点７１ａ，７１ｂの座標も、特徴点７１ｃを原点とした座標に変更する。たとえば、検索エリア８０は、抽出対象パターン６０の大きさに基づいて設定される。図１１には、特徴点７１ｃを原点とした座標に変換後の、特徴点７１ａ〜７１ｃに割り当てられた情報の一例が示されている。
【００６４】
特徴点７１ａには、情報（０，ｙ２，Ｉ，上）が割り当てられている。特徴点７１ｂには、情報（ｘ１，０，Ｉ，右）が割り当てられている。特徴点７１ｃには、情報（０，０，Ｌ，左下）が割り当てられている。
【００６５】
さらに、図１０に示した抽出対象パターン６０には、重み値が１００の特徴点がもう１つあるため（特徴点６１ｃ）、プロセッサ２１は、検索エリア８０内に、特徴点６１ｃの座標及び種類情報と一致する特徴点があるか否かを判定する。図１１の例では、レイアウトパターン７０の特徴点７１ｂは、特徴点６１ｃの座標と一致するが、特徴点７１ｂは端点に生成されたものであるため、種類情報が異なる。そのため、このようなレイアウトパターン７０は、抽出されず処理が終了される。なお、特徴点６１ｄの種類情報と一致する特徴点をもつレイアウトパターンが他にある場合には上記と同様の処理が行われる。
【００６６】
なお、座標が一致するか否かは、完全に一致していなくても、所定の範囲内であれば一致していると判定されるようにしてもよい（以下も同じである）。
図１２は、特徴点が生成されたレイアウトパターンの他の例を示す図である。
【００６７】
図１２に示すような間隙を有するレイアウトパターン７５では、前述した手法により、３つの端点と２つのＬ字状の屈曲部に特徴点７６ａ，７６ｂ，７６ｃ，７６ｄ，７６ｅが生成されている。さらに、各特徴点７６ａ〜７６ｅを始点とした単位ベクトル７７ａ，７７ｂ，７７ｃ，７７ｄ，７７ｅが生成されている。
【００６８】
たとえば、特徴点７６ｅの種類情報が、図１０の抽出対象パターン６０の特徴点６１ｄの種類情報と一致する場合、プロセッサ２１は、特徴点７６ｅの座標を、特徴点６１ｄの座標（０，０）に合わせる。そして、プロセッサ２１は、検索エリア８０ａを設定して、検索エリア８０ａ内のレイアウトパターン７５の他の特徴点７６ａ，７６ｂ，７６ｃ，７６ｄの座標も、特徴点７６ｅを原点とした座標に変更する。図１２には、特徴点７６ｅを原点とした座標に変換後の、特徴点７６ａ〜７６ｅに割り当てられた情報の一例が示されている。
【００６９】
特徴点７６ａには情報（ｘ１，ｙ４，Ｉ，上）、特徴点７６ｂには情報（ｘ１，ｙ３，Ｉ，下）、特徴点７６ｃには情報（０，ｙ２，Ｉ，上）、特徴点７６ｄには情報（ｘ１，０，Ｌ，右上）、特徴点７６ｅには情報（０，０，Ｌ，左下）が割り当てられている。
【００７０】
図１２の例のレイアウトパターン７５では、抽出対象パターン６０の重み値が１００の特徴点６１ｃと座標、種類情報とも一致する特徴点７６ｄが存在する。
このように、抽出対象パターン６０の重み値が１００の全ての特徴点６１ｃ，６１ｄと座標及び種類情報が一致する特徴点を有するレイアウトパターン（たとえば、図１２のレイアウトパターン７５）が存在すると、ステップＳ１３の処理が行われる。
【００７１】
ステップＳ１３の処理では、プロセッサ２１は、たとえば、図１２に示したレイアウトパターン７５に対して、さらに、抽出対象パターン６０における重み値が８０の特徴点６１ｂと一致する箇所（特徴点）があるか否かを判定する。
【００７２】
重み値が８０の特徴点６１ｂに対して比較される特徴点は、種類情報が同じであれば、特徴点６１ｂとｘ座標またはｙ座標の何れかの値が異なっても一致していると判定される。つまり、一致するか否かの判定基準が、重み値が１００の場合よりも緩い。なお、ｘ座標またはｙ座標の値が予め設定された範囲以上異なっている場合には、一方の座標の値が一致していても、両特徴点は一致しないと判定されるようにしてもよい。
【００７３】
図１２のレイアウトパターン７５では、座標も種類情報も特徴点６１ｂと一致する特徴点７６ｃが存在する。このような場合、ステップＳ１４の処理が行われる。なお、重み値が８０の特徴点６１ｂと一致する特徴点がないレイアウトパターンに対しては抽出対象とされず、処理が終了される。
【００７４】
ステップＳ１４の処理では、プロセッサ２１は、たとえば、図１２に示したレイアウトパターン７５に対して、さらに、抽出対象パターン６０における重み値が５０の特徴点６１ａと一致する箇所（特徴点）があるか否かを判定する。
【００７５】
重み値が５０の特徴点６１ａに対して比較される特徴点は、種類情報が異なっていても、特徴点６１ａとｘ座標またはｙ座標の何れかの値が同じであれば一致していると判定される。なお、ｘ座標またはｙ座標の値が予め設定された範囲以上異なっている場合には、一方の座標の値が一致していても、両特徴点は一致しないと判定されるようにしてもよい。
【００７６】
図１２のレイアウトパターン７５では、ｘ座標の値が特徴点６１ａと一致する特徴点７６ａ，７６ｂが存在する。
このように、重み値が割り当てられた抽出対象パターン６０の各特徴点６１ａ〜６１ｄと一致する特徴点７６ａ〜７６ｅを有するレイアウトパターン７５がある場合には、ステップＳ１５の処理が行われる。
【００７７】
なお、重み値が５０の特徴点６１ａと一致する特徴点がないレイアウトパターンに対しては抽出対象とされず、処理が終了される。
ステップＳ１５の処理では、プロセッサ２１は、検索エリア８０ａ内のレイアウトパターン７５を抽出する。
【００７８】
以下、ライブラリへの抽出対象パターンの登録例を説明する。
（抽出対象パターンの登録例）
以下、ライブラリが、図３に示したようなレイアウトパターン抽出装置（コンピュータ２０）によって生成されるものとして説明する。なお、ライブラリは、他のコンピュータによって作成されるようにしてもよい。
【００７９】
図１３は、抽出対象パターンの一例を示す図である。
プロセッサ２１は、たとえば、図１３に示すようなセル９１ａ，９１ｂを含む抽出対象パターン９０をライブラリに登録する場合、まず、抽出対象パターン９０の各コーナの座標を示すコーナ座標情報を生成する。図１３の例では、セル９１ａは、コーナａ〜ｌを有しており、セル９１ｂは、コーナＡ〜Ｈを有している。たとえば、プロセッサ２１は、あるコーナの座標を原点として他のコーナの座標を設定する。なお、ホットスポットの位置を原点として、各コーナの座標が設定されるようにしてもよい。
【００８０】
図１４は、コーナ座標情報の一例を示す図である。
コーナ座標情報９３には、セル９１ａ，９１ｂのコーナａ〜ｌ，Ａ〜Ｈのｘ座標とｙ座標が示されている。“Ｃｅｌｌ＝ＡＡＡ”、“Ｃｅｌｌ＝ＢＢＢ”は、セル９１ａ，９１ｂのセル名が“ＡＡＡ”、“ＢＢＢ”であることを示している。
【００８１】
次にプロセッサ２１は、図１４に示したようなコーナ座標情報９３に基づき、セル９１ａ，９１ｂにおいて前述した図形ベクトルを示す図形ベクトル情報を生成する。
図１５は、図形ベクトルの一例を示す図である。
【００８２】
図１５では、図１３に示した抽出対象パターン９０の領域９２の部分に発生された図形ベクトルの例が示されている。以下では、図形ベクトルを各コーナの符号を用いて表記する。たとえば、コーナＡを始点とするコーナＡ，Ｂ間の図形ベクトルは、図形ベクトルＡＢと表記する。
【００８３】
図１６は、生成された図形ベクトル情報の一例を示す図である。
図形ベクトル情報９４は、図形ベクトルの方向ごとに分類されている。抽出対象パターン９０のセル９１ａ（セル名は“ＡＡＡ”）では、図形ベクトルａｂ，ｃｄ，ｇｈは下向き、図形ベクトルｂｃ，ｆｇ，ｈｉ，ｊｋは右向きである。また、図形ベクトルｅｆ，ｉｊ，ｋｌは上向き、図形ベクトルｌａは左向きである。セル９１ｂ（セル名は“ＢＢＢ”）では、図形ベクトルＡＢ，ＥＦは下向き、図形ベクトルＢＣは右向き、図形ベクトルＣＤ，ＧＨは上向き、図形ベクトルＤＥ，ＦＧ，ＨＡは左向きである。
【００８４】
そして、プロセッサ２１は、各図形ベクトルから抽出対象パターン９０の各部の形状を認識する。以下の説明では、形状はＩ字、Ｌ字、Ｔ字の３つに分類されるものとする。プロセッサ２１は、形状の分類にあたって、以下に示すような特徴ベクトル情報を参照する。
【００８５】
図１７は、特徴ベクトル情報の一例を示す図である。
特徴ベクトル情報９５には、（１）Ｉ字、（２）Ｌ字、（３）Ｔ字と分類する図形ベクトルのグル―プの例が示されている。
【００８６】
たとえば、下向きの図形ベクトルと、右向きの図形ベクトルと、上向きの図形ベクトルが連続して発生する部分は、Ｉ字と分類される。また、下向きの図形ベクトルと、右向きの図形ベクトルと、上向きの図形ベクトルと、左向きの図形ベクトルが近接して発生する部分はＬ字と認識される。また、右向きの図形ベクトルと、下向きの図形ベクトルと、上向きの図形ベクトルと、右向きの図形ベクトルが近接して発生する部分はＴ字と認識される。
【００８７】
プロセッサ２１は、図１６に示した図形ベクトル情報９４を、上記のような特徴ベクトル情報９５に基づき３つの形状に分類し、たとえば、以下のような特徴ベクトル変換情報を生成する。
【００８８】
図１８は、特徴ベクトル変換情報の一例を示す図である。
特徴ベクトル変換情報９６は、Ｉ字、Ｔ字、Ｌ字と分類された部分の図形ベクトルが示されている。
【００８９】
たとえば、図１５に示した抽出対象パターン９０のセル９１ａに対して発生する図形ベクトルｇｈ，ｈｉ，ｉｊの方向は、下向き、右向き、上向きの関係があるので、Ｉ字と認識される。また、セル９１ａに対して発生する図形ベクトルｆｇ，ｇｈ，ｉｊ，ｊｋの方向は、右向き、下向き、上向き、右向きの関係があるので、Ｔ字と認識される。また、セル９１ｂに対して発生する図形ベクトルＡＢ，ＢＣ，ＧＨ，ＦＧの方向は、下向き、右向き、上向き、左向きの関係があるので、Ｌ字と認識される。
【００９０】
なお、“ｗ＝ｈｉ”は、Ｉ字状の部分の幅、“ｗ＝ｇｊ”はＴ字状の屈曲部の幅、“ｗ＝ＧＢ”は、Ｌ字状の屈曲部分のコーナ間の距離を示している。なお、この幅ｗは、レイアウトパターンにおいて、形状を判定するときの閾値として用いることができる。また、図１８において、“Ｉ１”、“Ｔ１”、“Ｌ１”は、各形状に分類された部分の番号を示している。
【００９１】
そして、プロセッサ２１は、各形状に分類された部分において、図５〜７で示したような手法を用いて、特徴点と単位ベクトルを生成する。
図１９は、特徴点と単位ベクトルの生成例を示す図である。
【００９２】
セル９１ａにおいて、Ｉ字状の部分の端点に特徴点９７ａ、Ｔ字状の屈曲部に特徴点９７ｂが生成されている。また、セル９１ｂにおいて、Ｉ字状の部分の端点に特徴点９７ｃ，９７ｄ、Ｌ字状の屈曲部に特徴点９７ｅ，９７ｆが生成されている。さらに各特徴点９７ａ〜９７ｆを始点とする単位ベクトル９８ａ，９８ｂ，９８ｃ，９８ｄ，９８ｅ，９８ｆが生成されている。
【００９３】
前述したように、抽出対象パターン９０の特徴点９７ａ〜９７ｆには、重み値が割り当てられる。同様の特性（たとえば、同様の位置にホットスポットが生じる）をもつレイアウトパターンを抽出したい場合、その特性に関係性の高い特徴点には、その特性に関係性の低い特徴点よりも大きな重み値が割り当てられる。
【００９４】
たとえば、図１９に示すような抽出対象パターン９０には、ホットスポット９９がある。同様の位置にホットスポット９９が生じるレイアウトパターンとして以下のようなものがある。
【００９５】
図２０は、抽出対象パターンと同様の特性をもつレイアウトパターンの一例を示す図である。
レイアウトパターン１００は、セル１０１ａ，１０１ｂを有し、抽出対象パターン９０と同様の位置にホットスポット１０２が生じている。セル１０１ａについては、抽出対象パターン９０のセル９１ａの形状と同じであり、セル１０１ａ，１０１ｂの位置関係も、抽出対象パターン９０のセル９１ａ，９１ｂの位置関係と同様である。
【００９６】
図２１は、抽出対象パターンと同様の特性をもつレイアウトパターンの他の例を示す図である。
レイアウトパターン１０５は、セル１０６ａ，１０６ｂ，１０６ｃを有し、抽出対象パターン９０と同様の位置にホットスポット１０７が生じている。セル１０６ａについては、抽出対象パターン９０のセル９１ａの形状と同じであり、セル１０６ａに対する１０６ｂ，１０６ｃの位置関係には、抽出対象パターン９０のセル９１ａ，９１ｂの位置関係と類似している。
【００９７】
このようなレイアウトパターン１００，１０５を抽出対象パターン９０と同じ分類として抽出するために、形状が共通するセル９１ａの特徴点９７ａ，９７ｂには、たとえば、重み値＝１００が割り当てられる。一方、抽出対象パターン９０のセル９１ｂが２つのＬ字状の屈曲部を有しているのに対して、レイアウトパターン１００のセル１０１ｂは、１つのＬ字状の屈曲部と１つのＴ字状の屈曲部を有している。そのため、特徴点９７ｅには、ホットスポット９９からの距離も考慮して、比較的大きい重み値（たとえば、８０）が割り当てられ、特徴点９７ｆにはそれより小さい重み値（たとえば、５０）が割り当てられる。また、ホットスポット９９からの距離が遠い特徴点については重み値を割り当てず、ライブラリへの登録対象から除外するようにしてもよい。
【００９８】
上記のような重み値の割り当てについては、たとえば、設計者が手動で行ってもよいが、プロセッサ２１が同様の特性をもつレイアウトパターンの各特徴点をマージして、その位置関係などから自動的に行うようにしてもよい。
【００９９】
以下、プロセッサ２１による重み付け処理を含むライブラリ作成処理の一例を説明する。
図２２は、ライブラリ作成処理の一例の流れを示すフローチャートである。
【０１００】
まず、プロセッサ２１は、たとえば、ＨＤＤ２３に予め格納されている複数の抽出対象パターンの中から、同様の性質をもち同じ分類としたい抽出対象パターンを選択する（ステップＳ２０）。そして、プロセッサ２１は、上記のような手法により、各抽出対象パターンにおいて、座標や種類情報が割り当てられた特徴点や単位ベクトルを生成する（ステップＳ２１）。ステップＳ２１の処理では、プロセッサ２１は、各抽出対象パターンから、ホットスポットの位置座標も抽出する。
【０１０１】
さらに、プロセッサ２１は、複数の抽出対象パターンから、代表パターンを選択する（ステップＳ２２）。たとえば、図１９に示した抽出対象パターン９０のほか、レイアウトパターン１００，１０５も抽出対象パターンとしたとき、プロセッサ２１は、たとえば、抽出対象パターン９０を代表パターンとする。
【０１０２】
その後、プロセッサ２１は、選択した代表パターンの各特徴点を中心とした所定の領域（以下サーチエリアという）を設定する（ステップＳ２３）。サーチエリアは、特徴点をマージする範囲を規定するものである。
【０１０３】
図２３は、サーチエリアの設定例を示す図である。
図２３では、図１９に示した抽出対象パターン９０の特徴点９７ａ〜９７ｆのそれぞれを中心としたサーチエリア１１０ａ，１１０ｂ，１１０ｃ，１１０ｄ，１１０ｅ，１１０ｆが設定されている。サーチエリア１１０ａ〜１１０ｆは、互いに重ならないように設定されており、たとえば、ホットスポット９９との距離が近いほど狭い。
【０１０４】
ステップＳ２３の処理後、プロセッサ２１は、複数の抽出対象パターンの特徴点を重ね合わせたときに、各サーチエリアに含まれる特徴点をマージする（ステップＳ２４）。
図２４は、マージ対象の特徴点の一例を示す図である。
【０１０５】
サーチエリア１１０ａには、抽出対象パターン９０の特徴点９７ａと同一座標で、抽出対象パターンとして選択されたレイアウトパターン１００，１０５のＩ字状の部分の端点に生成された特徴点１１５ａ，１１６ａが存在する。また、サーチエリア１１０ｂには、抽出対象パターン９０の特徴点９７ｂと同一座標で、上記レイアウトパターン１００，１０５のＴ字状の屈曲部に生成された特徴点１１５ｂ，１１６ｂが存在する。
【０１０６】
サーチエリア１１０ｃには、抽出対象パターン９０の特徴点９７ｃとｙ座標の値は同じで、ｘ座標の値は異なる、上記レイアウトパターン１００，１０５のＩ字状の部分の端点に生成された特徴点１１５ｃ，１１６ｃが存在する。サーチエリア１１０ｄには、抽出対象パターン９０の特徴点９７ｄとｙ座標の値は同じで、ｘ座標の値は異なる、上記レイアウトパターン１００，１０５のＩ字状の部分の端点に生成された特徴点１１５ｄ，１１６ｄが存在する。
【０１０７】
サーチエリア１１０ｅには、抽出対象パターン９０の特徴点９７ｅとｙ座標の値は同じで、ｘ座標の値は異なる、上記レイアウトパターン１００，１０５のＬ字状の屈曲部に生成された特徴点１１５ｆ，１１６ｇが存在する。
【０１０８】
サーチエリア１１０ｆには、抽出対象パターン９０の特徴点９７ｆとｙ座標の値は同じで、ｘ座標の値は異なる、上記レイアウトパターン１００のＴ字状の屈曲部に生成された特徴点１１５ｇと、レイアウトパターン１０５のＬ字状の屈曲部に生成された特徴点１１６ｈが存在する。
【０１０９】
レイアウトパターン１００の右下のＩ字状の部分の端点に生成された特徴点１１５ｅは、どのサーチエリア１１０ａ〜１１０ｆにも含まれない。レイアウトパターン１０５のセル１０６ｂ，１０６ｃの一方のＩ字状の部分の端点に生成された特徴点１１６ｅ，１１６ｆも、どのサーチエリア１１０ａ〜１１０ｆにも含まれない。
【０１１０】
なお、図２４には、特徴点９７ａ〜９７ｆを始点とした単位ベクトル９８ａ〜９８ｆ、特徴点１１５ａ〜１１５ｇを始点とした単位ベクトル１１７ａ，１１７ｂ，１１７ｃ，１１７ｄ，１１７ｆ，１１７ｇが示されている。また、特徴点１１６ａ〜１１６ｈを始点とした単位ベクトル１１８ａ，１１８ｂ，１１８ｃ，１１８ｄ，１１８ｅ，１１８ｆ，１１８ｇ，１１８ｈが示されている。
【０１１１】
各サーチエリア１１０ａ〜１１０ｆにおいて、複数の特徴点は１つの特徴点にマージされる。
ステップＳ２４の処理後、プロセッサ２１は、マージ処理で得られた特徴点の種類情報を決定する（ステップＳ２５）。ステップＳ２５の処理では、プロセッサ２１は、各サーチエリア１１０ａ〜１１０ｆにおいて、最も多い種類情報（生成位置の種類と単位ベクトルの向き）を、マージ処理で得られた特徴点の種類情報とする。
【０１１２】
たとえば、サーチエリア１１０ｅでは、Ｌ字状の屈曲部に生成され、単位ベクトル９８ｅ，１１７ｆ，１１８ｇの向きが右上となる特徴点９７ｅ，１１５ｆ，１１６ｇの数が、最も多い。そのため、これらの特徴点９７ｅ，１１５ｆ，１１６ｇの種類情報が採用される。
【０１１３】
さらに、プロセッサ２１は、マージ処理で得られた特徴点の座標を決定する（ステップＳ２６）。ステップＳ２６の処理では、たとえば、プロセッサ２１は、各サーチエリア１１０ａ〜１１０ｆに複数の特徴点が含まれている場合に、それらの特徴点の重心を、マージ処理で得られた特徴点の座標とする。
【０１１４】
その後、プロセッサ２１は、マージ処理で得られた特徴点の重み値を決定する（ステップＳ２７）。
たとえば、あるサーチエリアに含まれる各特徴点の座標が同じであり、かつ、種類情報も同じであれば、そのサーチエリアのマージ処理で得られた特徴点には、重み値として、１００が割り当てられる。
【０１１５】
また、サーチエリアに含まれる各特徴点のｘ座標またはｙ座標の値の一方が一致し、他方が異なっており、種類情報については一致しているときには、そのサーチエリアのマージ処理で得られた特徴点には、重み値として、８０が割り当てられる。
【０１１６】
また、サーチエリアに含まれる各特徴点のｘ座標またはｙ座標の値の一方が一致し、他方が異なっており、種類情報については異なっているときには、そのサーチエリアのマージ処理で得られた特徴点には、重み値として、５０が割り当てられる。
【０１１７】
なお、サーチエリアに含まれる各特徴点のｘ座標及びｙ座標の値が一致し、種類情報については異なっている場合や、サーチエリアに含まれる各特徴点のｘ座標及びｙ座標の値が異なり、種類情報についても異なる場合にも、９０や１０などの重み値が割り当てられるようにしてもよい。
【０１１８】
上記のような基準で重み値を割り当てる場合、図２４の例では、サーチエリア１１０ａ，１１０ｂにおいてマージ処理で得られた特徴点には、重み値として１００が割り当てられる。また、サーチエリア１１０ｃ，１１０ｄ，１１０ｅにおいてマージ処理で得られた特徴点には、重み値として８０が割り当てられる。サーチエリア１１０ｆにおいてマージ処理で得られた特徴点には、重み値として５０が割り当てられる。
【０１１９】
図２５は、マージ処理で得られた特徴点とその特徴点に割り当てられる情報の一例を示す図である。
特徴点１２０ａ，１２０ｂ，１２０ｃ，１２０ｄ，１２０ｅ，１２０ｆは、各サーチエリア１１０ａ〜１１０ｆにおいてマージ処理によって得られた特徴点である。また、特徴点１２０ａ〜１２０ｆのそれぞれを始点とした単位ベクトル１２１ａ，１２１ｂ，１２１ｃ，１２１ｄ，１２１ｅ，１２１ｆが図示されている。
【０１２０】
特徴点１２０ａ〜１２０ｆのそれぞれには、上記の処理によって決定された情報が割り当てられている。たとえば、特徴点１２０ａには、情報（Ｘ０，Ｙ０，Ｉ，上，１００）が割り当てられている。“Ｘ０”，“Ｙ０”は、ｘ座標の値とｙ座標の値を示し、“Ｉ”は端点に生成された特徴点であることを示している。また“上”は、単位ベクトル１２１ａの向きであり、“１００”は重み値を示している。
【０１２１】
プロセッサ２１は、その後、上記のようなマージ処理で得られた特徴点とその特徴点に割り当てられる情報を、ライブラリに登録する（ステップＳ２８）。
図２６は、ライブラリへの特徴点の登録例を示す図である。
【０１２２】
ライブラリ１２５には、マージ処理で得られた各特徴点に割り当てられた情報が登録される。図２６には、図２５に示した特徴点１２０ａ〜１２０ｆに割り当てられた情報の登録例が示されている。
【０１２３】
ライブラリ１２５において、“特徴：Ｉ１，Ｉ２，Ｉ３，Ｌ１，Ｌ２，Ｔ１”のＩ１〜Ｉ３は、端点に生成された特徴点１２０ａ，１２０ｃ，１２０ｄを示しており、Ｌ１，Ｌ２はＬ字状の屈曲部に生成された特徴点１２０ｅ，１２０ｆを示している。また、Ｔ１は、Ｔ字状の屈曲部に生成された特徴点１２０ｂを示している。そして、各特徴点１２０ａ〜１２０ｆに割り当てられた情報として、座標、重み値、向き（単位ベクトル１２１ａ〜１２１ｆの向き）がライブラリ１２５に登録されている。なお、図２６の例では、各特徴点１２０ａ〜１２０ｆを始点とする単位ベクトル１２１ａ〜１２１ｆの向きは、１から８の番号で表されている。１は左上、２は上、３は右上、４は右、５は右下、６は下、７は左下、８は左を示している。
【０１２４】
このようなライブラリ１２５は、たとえば、ＨＤＤ２３に記憶される。
なお、図２２の各処理ステップの順序は、上記の例には限定されず、たとえば、ステップＳ２５〜Ｓ２７の処理などは適宜入れ替えてもよい。
【０１２５】
以上のようなライブラリ１２５を用いて、図４に示したレイアウトパターン抽出方法が行われることによって、図１９に示した抽出対象パターン９０のほか、同様の性質をもつ図２０、図２１のようなレイアウトパターン１００，１０５についても抽出可能となる。
【０１２６】
図２７は、レイアウトパターンの抽出結果の一例を示す画面表示例である。
画面１３０は、たとえば、図３に示したモニタ２４ａに表示されるものである。画面１３０には、抽出対象パターン１３１に対応するレイアウトパターンの抽出結果の一例が示されている。抽出対象パターン１３１は、Ｌ字状の屈曲部に生成された特徴点１３２ａ、Ｔ字状の屈曲部に生成された特徴点１３２ｂ、端点に生成された特徴点１３２ｃ、Ｌ字状の屈曲部に生成された特徴点１３２ｄを有する。さらに、各特徴点１３２ａ〜１３２ｄを始点とした単位ベクトル１３３ａ，１３３ｂ，１３３ｃ，１３３ｄが表示されている。また、各特徴点１３２ａ〜１３２ｄに割り当てられた情報（ライブラリに登録されている情報）が表示されている。なお、“領域：ＸＹ”は、図１１などに示した検索エリアの大きさを示している。
【０１２７】
画面１３０には、さらに、上記のような抽出対象パターン１３１の特徴点１３２ａ〜１３２ｄと対応する特徴点をもつレイアウトパターンの抽出結果が表示されている。図２７には、設計データ（レイアウトデータ）１３５に含まれる複数のレイアウトパターンから、６つのレイアウトパターン１３６ａ，１３６ｂ，１３６ｃ，１３６ｄ，１３６ｅ，１３６ｆが抽出された例が示されている。このとき、プロセッサ２１は、モニタ２４ａに、抽出結果として６つマッチした旨を表示させたり、抽出箇所を強調表示させたりするようにしてもよい。
【０１２８】
以上のようなレイアウトパターン抽出方法によれば、第１の実施の形態のレイアウトパターン抽出方法と同様の効果が得られる。
さらに、本実施の形態のレイアウトパターン抽出方法では、抽出対象パターンの特徴点に重み値が割り当てられている。そして、重み値の大きい特徴点ほど、レイアウトパターンの特徴点と一致するか否かの基準が厳しく、重み値の小さい特徴点ほど、その基準が緩くなっている。これによって、同様の特性（たとえば、同様の位置にホットスポットが生じる）をもつレイアウトパターンを抽出したい場合、その特性に関係性の高い特徴点の優先度を上げ、その特性に関係性の低い特徴点の優先度を下げることができる。そのため、特性に応じた類似パターンの抽出が可能となる。
【０１２９】
なお、上記の例では重み値は３つの値としたが、２つまたは、４つ以上としてもよい。
（第３の実施の形態）
以下、ＯＰＣ後のレイアウトパターンを抽出する方法を、第３の実施の形態のレイアウトパターン抽出方法として説明する。
【０１３０】
ＯＰＣ後のレイアウトパターンは、コーナが多いため、特徴点が多数発生する。そのため、所定の閾値よりも小さい段差部分は、特徴点の発生の際に考慮しないようにすることで、特徴点の数を減らすことができる。ＯＰＣ後のレイアウトパターンを抽出する際、プロセッサ２１は、たとえば、図４のステップＳ１０とステップＳ１１の処理の間に以下のような処理を行う。
【０１３１】
図２８は、第３の実施の形態のレイアウトパターン抽出方法の一例の処理の流れを示すフローチャートである。
プロセッサ２１は、図４のステップＳ１０の処理と同様にデータ読み込み（ステップＳ３０）を行うと、設計データに含まれる複数のレイアウトパターンにおいて、図形ベクトルを発生させ、連続した３つの図形ベクトルを抽出する（ステップＳ３１）。
【０１３２】
図２９は、連続した３つの図形ベクトルの一例を示す図である。
レイアウトパターン１４１は、ＯＰＣ後のものであって、複数の微小な段差が生じている。図１５などに示した図形ベクトルの生成方法を用いて、プロセッサ２１は、レイアウトパターン１４１の各コーナ間に図形ベクトルを生成する。ステップＳ３１の処理では、連続した３つの図形ベクトルが抽出される。たとえば、図２９の例では、図形ベクトル１４２ａ，１４２ｂ，１４２ｃは、連続した３つの図形ベクトルであるため抽出される。
【０１３３】
次に、プロセッサ２１は、連続した３つの図形ベクトルのうち、１，３番目の図形ベクトルの向きが同じか否かを判定する（ステップＳ３２）。
１，３番目の図形ベクトルの向きが同じでないときには、ステップＳ３５の処理（特徴点生成）が行われる。１，３番目の図形ベクトルの向きが同じであるときには、プロセッサ２１は、２番目の図形ベクトルのスカラー量（コーナ間の距離）が、所定の閾値以下であるか否かを判定する（ステップＳ３３）。
【０１３４】
図２９の例では、連続する３つの図形ベクトル１４２ａ，１４２ｂ，１４２ｃのうち、１番目の図形ベクトル１４２ａと３番目の図形ベクトル１４２ｃの向きは共に左向きであり同じであるため、ステップＳ３３の処理が行われる。
【０１３５】
ステップＳ３３の処理において、２番目の図形ベクトルのスカラー量が閾値よりも大きいときには、ステップＳ３５の処理が行われる。２番目の図形ベクトルのスカラー量が閾値以下であるときには、プロセッサ２１は、その図形ベクトルの始点と終点のコーナ座標を書き出し、計算対象外コーナ情報１４０を生成する（ステップＳ３４）。計算対象外コーナ情報１４０には、２番目の図形ベクトルの始点と終点のコーナ座標が含まれる。
【０１３６】
図２９の例では、２番目の図形ベクトル１４２ｂのスカラー量ｌａは、所定の閾値ｌｔｈ以下となっているため、ステップＳ３４の処理が行われる。なお、閾値は、たとえば、ＯＰＣによって生じる段差の大きさの範囲や、計算負荷を考慮して予め決められている。閾値を大きくすると、生成される特徴点の数を減らせるが、あまり大きくしすぎると、ＯＰＣ起因で発生する特徴点ではない特徴点についても削除される可能性があるためである。
【０１３７】
ステップＳ３４の処理では、たとえば、図２９の例では、図形ベクトル１４２ｂの始点であるコーナ１４３ａの座標（Ｘａ，Ｙａ）と、図形ベクトル１４２ｂの終点であるコーナ１４３ｂの座標（Ｘａ，Ｙｂ）が書き出される。その後ステップＳ３５の処理が行われる。
【０１３８】
ステップＳ３５の処理は、図４に示したステップＳ１１の処理とほぼ同様であるが、プロセッサ２１は、計算対象外コーナ情報１４０に含まれる座標の組（たとえば、上記の（Ｘａ，Ｙａ）と（Ｘａ，Ｙｂ））を、特徴点を求めるための計算には用いない。つまり、このような座標の組による図形ベクトルは、特徴点を求める際に用いる図形ベクトルから除外され、ＯＰＣ起因で発生する段差に基づく特徴点の数を減らすことができる。
【０１３９】
ステップＳ３６の処理は、図４に示したステップＳ１２の処理と同じである。ステップＳ３６の処理で、抽出対象パターンの重み値が１００の特徴点と一致する箇所がないと判定されたときには、抽出処理が終了する。ステップＳ３６の処理で、抽出対象パターンの重み値が１００の特徴点と一致する箇所があると判定されたときには、ステップＳ３７の処理が行われる。ステップＳ３７の処理では、プロセッサ２１は、抽出対象パターンの重み値が３０の特徴点と一致する箇所があるか否かを判定する。
【０１４０】
重み値が３０の特徴点と比較されるレイアウトパターンの特徴点は、種類情報が同じであり、かつ、座標が、重み値が３０の特徴点のｘ座標及びｙ座標に対して所定の範囲内であるときに、一致していると判定される。
【０１４１】
設計データ上のレイアウトパターンでは、上下または左右に２点ある特徴点が同じｘ座標またはｙ座標であっても、ＯＰＣ後のレイアウトパターンでは、同じ座標にならない場合があるため、このような比較的緩い判定基準が設けられる。なお、上記の所定の範囲は、たとえば、ＯＰＣ起因で発生する段差の大きさなどに基づき予め設定されている。
【０１４２】
ステップＳ３７の処理で、抽出対象パターンの重み値が３０の特徴点と一致する箇所がないと判定されたときには、抽出処理が終了する。ステップＳ３７の処理で、抽出対象パターンの重み値が３０の特徴点と一致する箇所があると判定されたときには、ステップＳ３８の処理が行われる。
【０１４３】
ステップＳ３８の処理は、図４に示したステップＳ１５の処理と同じであり、検索エリア内のレイアウトパターンが抽出される。
図３０は、ＯＰＣ後のレイアウトパターンの抽出結果の一例を示す画面表示例である。
【０１４４】
画面１５０は、たとえば、図３に示したモニタ２４ａに表示されるものである。画面１５０には、抽出対象パターン１５１に対応するレイアウトパターンの抽出結果の一例が示されている。抽出対象パターン１５１は、Ｌ字状の屈曲部に生成された特徴点１５２ａ、端点に生成された特徴点１５２ｂ、Ｌ字状の屈曲部に生成された特徴点１５２ｃを有する。さらに、各特徴点１５２ａ〜１５２ｃを始点とした単位ベクトル１５３ａ，１５３ｂ，１５３ｃが表示されている。また、各特徴点１５２ａ〜１５２ｃに割り当てられた情報（ライブラリに登録されている情報）が表示されている。
【０１４５】
画面１５０には、さらに、上記のような抽出対象パターン１５１の特徴点１５２ａ〜１５２ｃと対応する特徴点をもつレイアウトパターンの抽出結果が表示されている。図３０には、設計データ（レイアウトデータ）１５５に含まれる複数のレイアウトパターンから、レイアウトパターン１５６が抽出された例が示されている。
【０１４６】
レイアウトパターン１５６は、特徴点１５７ａ，１５７ｂ，１５７ｃ，１５７ｄ，１５７ｅを有する。また、図３０では、特徴点１５７ａ〜１５７ｅを始点とする単位ベクトル１５８ａ，１５８ｂ，１５８ｃ，１５８ｄ，１５８ｅが表示されている。特徴点１５７ａ〜１５７ｅのうち、たとえば、特徴点１５７ａ，１５７ｃ，１５７ｅが、抽出対象パターン１５１の特徴点１５２ａ，１５２ｂ，１５２ｃと一致すると判定され、このレイアウトパターン１５６が抽出される。
【０１４７】
以上のような第３の実施の形態のレイアウトパターン抽出方法によれば、第２の実施の形態のレイアウトパターン抽出方法と同様の効果が得られる。
また、ＯＰＣによって生じる微小な段差のコーナ座標間を結ぶ図形ベクトルは、特徴点の生成に用いられる図形ベクトルからは除外されるため、特徴点が多数発生することを抑制できる。
【０１４８】
以上、実施の形態に基づき、本発明のレイアウトパターン抽出方法、レイアウトパターン抽出装置及びプログラムの一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１４９】
１  レイアウトパターン抽出装置（コンピュータ）
２  プロセッサ
２ａ  特徴点生成部
２ｂ  比較部
２ｃ  抽出部
３  記憶部
１１  設計データ
１２ｐ１〜１２ｐｎ  レイアウトパターン
１３ａ〜１３ｆ，１６ａ〜１６ｅ  特徴点
１４  ライブラリ
１５  抽出対象パターン
【図１】
2016201006.tif 000003
【図２】
2016201006.tif 000004
【図３】
2016201006.tif 000005
【図４】
2016201006.tif 000006
【図５】
2016201006.tif 000007
【図６】
2016201006.tif 000008
【図７】
2016201006.tif 000009
【図８】
2016201006.tif 000010
【図９】
2016201006.tif 000011
【図１０】
2016201006.tif 000012
【図１１】
2016201006.tif 000013
【図１２】
2016201006.tif 000014
【図１３】
2016201006.tif 000015
【図１４】
2016201006.tif 000016
【図１５】
2016201006.tif 000017
【図１６】
2016201006.tif 000018
【図１７】
2016201006.tif 000019
【図１８】
2016201006.tif 000020
【図１９】
2016201006.tif 000021
【図２０】
2016201006.tif 000022
【図２１】
2016201006.tif 000023
【図２２】
2016201006.tif 000024
【図２３】
2016201006.tif 000025
【図２４】
2016201006.tif 000026
【図２５】
2016201006.tif 000027
【図２６】
2016201006.tif 000028
【図２７】
2016201006.tif 000029
【図２８】
2016201006.tif 000030
【図２９】
2016201006.tif 000031
【図３０】
2016201006.tif 000032