(57)【要約】      （修正有）【課題】関心領域（ＲＯＩ）を有するマスク行列を設けることと、マスク行列内で複数の関心点を位置付けることによってモデルに基づく光学的近接効果補正を実行する方法、およびそのような方法を実行するプログラム記憶装置を提供すること。【解決手段】位置付けられた関心点を表す複数の頂点を有する第１ポリゴン２００を計算し、その後、その頂点とＲＯＩ１００の間の空間的関係を判定する。第１ポリゴンの頂点を、ＲＯＩの境界およびその中にピンニングし、ＲＯＩ上に第２ポリゴン３００を形成する。この処理を、第１ポリゴンのすべての頂点について繰り返し、第２ポリゴンがＲＯＩ上に縮約されるようにする。この縮約された第２ポリゴンを使用して、光学的近接効果を補正する。【選択図】図８
2005165282.tif 000002
【特許請求の範囲】
【請求項１】
境界と共に関心領域（ＲＯＩ）を有するマスク行列を設けるステップと、
前記マスク行列内で複数の関心点を位置付けるステップと、
前記位置付けられた複数の関心点を表す複数の頂点を有する第１の単一ループ有限幾何形状を決定するステップと、
光学的近接効果の補正をするために、前記第１の単一ループ有限幾何形状を前記関心領域上に縮約するステップと
を含むモデルに基づく光学的近接効果補正を実施する方法。
【請求項２】
前記第１の単一ループ有限幾何形状を縮約する前記ステップが、少なくとも前記関心領域の外にある前記第１の単一ループ有限幾何形状の頂点を前記関心領域の前記境界にピンニングすることによって、前記関心領域上に縮約された第２の単一ループ有限幾何形状を形成する、請求項１に記載の方法。
【請求項３】
前記第１の単一ループ有限幾何形状および前記第２の単一ループ有限幾何形状が、同一の有限幾何形状を有する、請求項２に記載の方法。
【請求項４】
前記第１の単一ループ有限幾何形状および前記第２の単一ループ有限幾何形状が、異なる有限幾何形状を有する、請求項２に記載の方法。
【請求項５】
前記第１の単一ループ有限幾何形状および前記第２の単一ループ有限幾何形状が、同一の個数の頂点を有する、請求項２に記載の方法。
【請求項６】
前記第１の単一ループ有限幾何形状および前記第２の単一ループ有限幾何形状が、異なる個数の頂点を有する、請求項２に記載の方法。
【請求項７】
前記第１の単一ループ有限幾何形状を決定する前記ステップが、前記複数の関心点と前記関心領域との間の相関に基づいて前記第１の単一ループ有限幾何形状を計算することを含む、請求項２に記載の方法。
【請求項８】
前記第１の単一ループ有限幾何形状の第１頂点を位置付けるステップと、
前記第１の単一ループ有限幾何形状の第２頂点を位置付けるステップと、
前記関心領域に関する前記行列内の前記第１頂点および前記第２頂点の位置を決定するステップと
をさらに含む、請求項２に記載の方法。
【請求項９】
前記第１頂点および前記第２頂点が、互いに隣接し、それぞれが、前記マスク行列内の前記複数の関心点の隣接する第１関心点および第２関心点を表す、請求項８に記載の方法。
【請求項１０】
前記位置が、前記関心領域内の前記第１頂点および前記第２頂点の両方を含み、前記方法が、さらに、
前記第１頂点を、前記関心領域内の前記第２の単一ループ有限幾何形状の第１頂点に割り当てるステップと、
前記第１の単一ループ有限幾何形状のすべての頂点について前記ステップを繰り返すステップと
をさらに含む、請求項８に記載の方法。
【請求項１１】
前記位置が、前記関心領域内にある前記第１頂点および前記関心領域の外にある前記第２頂点を含み、前記方法が、
前記第２頂点を前記関心領域の前記境界との交差の最も近い点にピンニングするステップと、
前記第１頂点を前記関心領域内の前記第２の単一ループ有限幾何形状の第１頂点に割り当てるステップと、
前記ピンニングされた第２頂点を前記関心領域内の前記第２の単一ループ有限幾何形状の第２頂点に割り当てるステップと、
前記第１の単一ループ有限幾何形状のすべての頂点について前記ステップを繰り返すステップと
をさらに含む、請求項８に記載の方法。
【請求項１２】
前記位置が、前記関心領域の外にある前記第１頂点および前記関心領域内にある前記第２頂点を含み、前記方法が、
前記第１頂点を前記関心領域の前記境界との交差の最も近い点にピンニングするステップと、
前記ピンニングされた第１頂点を前記関心領域内の前記第２の単一ループ有限幾何形状の第１頂点に割り当てるステップと、
前記第１の単一ループ有限幾何形状のすべての頂点について前記ステップを繰り返すステップと
をさらに含む、請求項８に記載の方法。
【請求項１３】
前記位置が、前記関心領域の外にある前記第１頂点および前記第２頂点の両方を含み、前記方法が、
前記第１頂点の前記位置がある前記マスク行列の領域を決定するステップと、
前記第１頂点を、前記第１頂点がある前記マスク行列の前記領域に基づいて、前記関心領域の前記境界にピンニングするステップであって、
前記第１頂点が、前記関心領域の角に隣接する領域内にある場合に、前記第１頂点を、前記関心領域の最も近い角にピンニングし、
前記第１頂点が、前記関心領域の側方辺（稜線）に隣接する領域内にある場合に、前記第１頂点を、前記関心領域の最も近い側方辺にピンニングする
ステップと
前記第１の単一ループ有限幾何形状のすべての頂点について前記ステップを繰り返すステップと
をさらに含む、請求項８に記載の方法。
【請求項１４】
前記第１頂点および前記第２頂点を結ぶ前記第１の単一ループ有限幾何形状の側方辺を位置付けるステップと、
前記側方辺が２つのピンニングされた点で前記関心領域と交差するかどうかを判定するステップと
をさらに含む、請求項１３に記載の方法。
【請求項１５】
前記側方辺が２つの点で前記関心領域と交差すると判定され、前記方法が、
前記２つのピンニングされた点の第１点を、前記関心領域内の前記第２の単一ループ有限幾何形状の第１頂点に割り当てるステップと、
前記２つのピンニングされた点の第２点を、前記関心領域内の前記第２の単一ループ有限幾何形状の第２頂点に割り当てるステップと
をさらに含む、請求項１４に記載の方法。
【請求項１６】
前記側方辺が、２つの点で前記関心領域と交差しないと判定され、前記方法が、前記第１頂点および前記第２頂点が、前記マスク行列の同一領域内にあるかどうかを判定することをさらに含む、請求項１４に記載の方法。
【請求項１７】
前記第１頂点および前記第２頂点が、同一の領域内にある場合に、前記第１の単一ループ有限幾何形状のすべての頂点について前記ステップを繰り返す前記ステップに進むステップと、
前記第１頂点および前記第２頂点が、同一の領域内にない場合に、前記第１頂点および前記第２頂点が、前記マスク行列の隣接領域内にあるかどうかを判定するステップと
をさらに含む、請求項１６に記載の方法。
【請求項１８】
前記第１頂点および前記第２頂点が、前記マスク行列の隣接領域内にある場合に、前記第１の単一ループ有限幾何形状のすべての頂点について前記ステップを繰り返す前記ステップに進むステップと、
前記第１頂点および前記第２頂点が、前記マスク行列の隣接領域内にない場合に、前記第１頂点および前記第２頂点が、前記マスク行列の隣接する領域内にないかどうかを判定するステップと
をさらに含む、請求項１７に記載の方法。
【請求項１９】
前記第１頂点および前記第２頂点が、前記マスク行列の隣接する領域にないのではないと判定される場合に、エラーに起因して前記方法を停止するステップと、
前記第１頂点および前記第２頂点が、前記マスク行列の隣接する領域にないと判定される場合に、前記第１頂点および前記第２頂点を結ぶ前記側方辺が、前記関心領域の外にあり、前記方法が、
前記関心領域の前記境界の、前記第１頂点および前記第２頂点を結ぶ前記側方辺に関して最も近い角に、追加頂点を追加するステップと
をさらに含む、請求項１８に記載の方法。
【請求項２０】
境界と共に関心領域を有するマスク行列を設けるステップと、
前記マスク行列内で複数の関心点を位置付けるステップと、
前記位置付けされた複数の関心点を表す複数の頂点を有する第１の単一ループ・ポリゴンを計算するステップと、
前記第１の単一ループ・ポリゴンの前記複数の頂点の選択された１つを前記関心領域の前記境界にピンニングして、前記関心領域上で第２の単一ループ・ポリゴンを形成するステップであって、前記複数の頂点の前記選択された１つが、前記複数の頂点の前記選択された１つと前記関心領域との空間的関係に基づいて前記関心領域にピンニングされるステップと、
前記第２の単一ループ・ポリゴンを使用して光学的近接効果を補正するステップと
を含むモデルに基づく光学的近接効果補正を実施する方法。
【請求項２１】
前記位置付けされた複数の関心点が、前記第１の単一ループ・ポリゴンの前記複数の頂点が前記マスク行列内のポリゴンのグループのすべての頂点を表すように、ポリゴンの前記グループを表す、請求項２０に記載の方法。
【請求項２２】
前記複数の頂点の選択された１つをピンニングする前記ステップが、
前記第１の単一ループ・ポリゴンの第１および第２の隣接する頂点を位置付けることと、
前記関心領域に関する前記行列内の前記第１頂点および前記第２頂点のそれぞれの位置を決定することと、
前記第１頂点および前記第２頂点の両方の前記位置が前記関心領域内にある時に、前記第１頂点を前記第２の単一ループ・ポリゴンの第１頂点に割り当てることと
を含む、請求項２０に記載の方法。
【請求項２３】
前記位置が、前記関心領域内にある前記第１頂点および前記関心領域の外にある前記第２頂点を含み、前記方法が、
前記第２頂点を前記関心領域の前記境界との交差の最も近い点にピンニングするステップと、
前記第１頂点を前記第２の単一ループ・ポリゴンの第１頂点に割り当てるステップと、
前記ピンニングされた第２頂点を前記第２の単一ループ・ポリゴンの第２頂点に割り当てるステップと
をさらに含む、請求項２２に記載の方法。
【請求項２４】
前記位置が、前記関心領域の外にある前記第１頂点および前記関心領域内にある前記第２頂点を含み、前記方法が、
前記第１頂点を前記関心領域の前記境界との交差の最も近い点にピンニングするステップと、
前記第１頂点を前記第２の単一ループ・ポリゴンの第１頂点に割り当てるステップと
をさらに含む、請求項２３に記載の方法。
【請求項２５】
前記位置が、前記関心領域の外にある前記第１頂点および前記第２頂点の両方を含み、前記方法が、
前記第１頂点の前記位置がある前記マスク行列の領域を決定するステップと、
前記第１頂点を、前記第１頂点がある前記マスク行列の前記領域に基づいて、前記関心領域の前記境界にピンニングするステップであって、
前記第１頂点が、前記関心領域の角に隣接する領域内にある場合に、前記第１頂点を、前記関心領域の最も近い角にピンニングし、
前記第１頂点が、前記関心領域の側方辺に隣接する領域内にある場合に、前記第１頂点を、前記関心領域の最も近い側方辺にピンニングする
ステップと、
前記第１頂点および前記第２頂点を結ぶ前記第１の単一ループ・ポリゴンの側方辺を位置付けるステップと、
前記側方辺が２点で前記関心領域と交差するかどうかを判定するステップと
をさらに含む、請求項２４に記載の方法。
【請求項２６】
前記側方辺が２つの点で前記関心領域と交差すると判定され、前記方法が、
前記２つのピンニングされた点の第１点を、前記関心領域上の前記第２の単一ループ・ポリゴンの第１頂点に割り当てるステップと、
前記２つのピンニングされた点の第２点を、前記関心領域上の前記第２の単一ループ・ポリゴンの第２頂点に割り当てるステップと
をさらに含む、請求項２５に記載の方法。
【請求項２７】
前記側方辺が、２つの点で前記関心領域と交差しないと判定され、前記方法が、前記第１頂点および前記第２頂点が、前記マスク行列の同一領域内にあるかどうかを判定するステップと、
前記第１頂点および前記第２頂点が、同一の領域内にある場合に、
前記第１の単一ループ・ポリゴンの第３頂点を位置付けるステップと、
前記第１の単一ループ・ポリゴンの前記第２頂点および前記第３頂点について前記ステップを繰り返すステップと、
前記第１頂点および前記第２頂点が、同一の領域内にない場合に、
前記第１頂点および前記第２頂点が、前記マスク行列の隣接領域にあるかどうかを判定するステップと
をさらに含む、請求項２６に記載の方法。
【請求項２８】
ａ）前記第１頂点および前記第２頂点が、前記マスク行列の隣接領域内にあると判定される場合に、前記第１の単一ループ・ポリゴンの前記第２頂点および前記第３頂点に進み、前記ステップを繰り返すステップと、
ｂ）前記第１頂点および前記第２頂点が、前記マスク行列の隣接領域内にないと判定される場合に、前記第１頂点および前記第２頂点が実際に前記マスク行列の隣接領域にないかどうかを判定し、
ｉ）前記第１頂点および前記第２頂点が、前記マスク行列の隣接領域にないのではないと判定される場合に、エラーに起因して前記方法を停止し、
ｉｉ）前記第１頂点および前記第２頂点が、実際に前記マスク行列の隣接領域にないと判定される場合に、前記第１頂点および前記第２頂点を結ぶ前記側方辺が、前記関心領域の外にあり、前記方法が、さらに、
前記関心領域の前記境界の角で前記第２の単一ループ・ポリゴンに追加頂点を追加するステップであって、前記角が、前記側方辺に最も近い角である、ステップと
からなるステップの群から選択されたステップをさらに含む、請求項２７に記載の方法。
【請求項２９】
前記第２の単一ループ・ポリゴンが前記関心領域内の前記境界上で縮約されるように、前記第１の単一ループ・ポリゴンのすべての頂点について前記ステップを繰り返すことをさらに含む、請求項２８に記載の方法。
【請求項３０】
マシンによって読取可能であり、モデルに基づく光学的近接効果補正を実施する方法ステップを実行するためにマシンによって実行可能な命令のプログラムを確実に実施するプログラム記憶装置であって、前記方法ステップが、
境界と共に関心領域を有するマスク行列を設けることと、
前記マスク行列内で複数の関心点を位置付けることと、
前記位置付けられた複数の関心点を表す複数の頂点を有する第１の単一ループ有限幾何形状を決定することと、
光学的近接効果を補正するために、前記第１の単一ループ有限幾何形状を前記関心領域上に縮約することと
を含む、プログラム記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に光リソグラフィの分野に関し、具体的には、光リソグラフィのためのモデルに基づく光学的近接効果補正（ＯＰＣ：Optical Proximity Correction）で使用される、元のポリゴンの新しい頂点の形成し、その頂点の関心領域（ＲＯＩ：Regionof Interest）へのピンニング（pinning）を行うポリゴン・ピンニング（polygon pinning）方法に関する。
【背景技術】
【０００２】
半導体デバイスの製造において、フォトリソグラフィとも称する光マイクロリソグラフィ処理が、一般に、所望の回路パターンを半導体ウェハ上でできる限り良好に転写（複製）する（duplicate）ことを必要とする。この所望の回路パターンは、フォトマスクと呼ぶテンプレート上の不透明領域および完全にまたは部分的に透明な領域として表される。フォトマスク上のパターンが、次に露光システムによる光学的結像（opticalimaging）によって、フォトレジストを被覆したウェハ上に投影される。
【０００３】
空間像シミュレータ（aerial image simulator）は、投影光学系によって生成される画像を計算するものであり、集積回路製造に関する光リソグラフィの最新技術を分析し、改善する貴重なツールであることが実証されている。これらのシミュレーションは、位相シフト・マスク（ＰＳＭ：PhaseShifting Mask）、光学的近接効果補正（ＯＰＣ：Optical Proximity Correction）などの高度なマスク設計および投影光学系の設計に応用分野を見出してきた。空間像のモデリングは、半導体製造の非常に重要な構成要素である。現在のリソグラフィ・ツールでは、部分的にコヒーレントな照明が使用されるので、そのようなモデリングは、基本的なパターン以外のすべてについて大量の計算が行われる。マスクによって生成される空間像すなわち、投影光学系の結像面での光強度は、現像されたフォトレジスト構造がマスク設計をどれほど良好に転写するかを左右するので、マイクロリソグラフィにおいて極めて重要な量である。
【０００４】
ＯＰＣソフトウェアでは、画像強度が、通常は、プロセスの物理的特性を記述する特定のカーネル（kernel）関数を有する双一次（bilinear）変換によって計算される。これは、ホプキンス（Hopkin）の積分に対応する光学的カーネルまたはレジスト効果を含む複合カーネルによって達成することができる。たとえば、短距離効果に関して、双一次変換を、ＳＯＣＳ（Sumof Coherent Sources；コヒーレント源の和）法によって単純な線形コンボリューション（convolution；重畳積分）の和に最適に変形することができるが、中距離効果または他の非光学効果に関して、双一次変換を、マスク・パターンと強度カーネルの間の線形コンボリューションに変形することができる。
【０００５】
超長距離効果に関して、課題をさらに変形して、粗いグリッドによってマスクを表すことができ、ここで、各画素は、そのグリッド正方形内の構造体（feature）の平均パターン密度である。粗いグリッドとインコヒーレント・カーネルの間のコンボリューションは、たとえば、高速フーリエ変換（ＦＦＴ）が同時にすべての画素のコンボリューションを生成できるので、ＦＦＴを介して、または同一の効果をもたらすより新しくより高速の方法によって、非常にすばやく行うことができる。
【０００６】
しかし、短距離および中距離は、個々のポリゴンに対処する必要に起因して時間がかかる可能性があるクリティカルな部分である。短距離効果および中距離効果の計算の通常の実行（practice）に、有限で許容可能なサイズのテーブルにストアされる基本構成要素セクタのコンボリューションのルックアップ・テーブルを準備するある実用的な仮定によってカーネルを空間的に切り捨てることが含まれる。
【０００７】
上述の従来技術のコンボリューション技法は、一般に、セクタに基づく（sector-based）アルゴリズムまたは辺に基づく（edge-based）アルゴリズムのいずれかを使用してポリゴン（polygon）構造体に対して実行される。このセクタに基づくアルゴリズムは、さまざまな角度でセクタを使用して計算することができるが、このセクタに基づくアルゴリズムを用いると、セクタに対するコンボリューションを、ベース画像として事前に計算し、テーブルまたは行列（matrix）にストアできるようになる。たとえば、セクタに基づくＯＰＣエンジンの従来のやり方（practice）に、ポリゴンを、９０°の角度（図１に図示）または４５°の角度（図２および３に図示）のいずれかのセクタの集合に分解することを含めることができる。しかし、従来のセクタに基づくＯＰＣ計算は、しばしば、時間がかかり、かなりの量のメモリを必要とする。というのは、計算が、正方形の関心領域（ＲＯＩ）１０内のセクタごとに実行され、その後、後の使用のためにテーブル（行列）にストアされるからである。
【０００８】
上記に加えて、セクタに基づくＯＰＣ計算は、ある長距離カーネルに対して精度不足もこうむる。すなわち、従来、マスク・ポリゴンが分解される解放された（unbound）セクタに対する画像カーネルを分析的に表すことを試みる時の発散（divergence）の問題に部分的に帰することができる光学的近接効果補正計算で、数学的問題が生じる。
【０００９】
たとえば、図１に、正方形ＲＯＩ１０の内部のさまざまな計算された点「Ｘ０」のさまざまな９０°セクタのルックアップ・テーブル値を示す。厳密に水平または垂直である辺を有するセクタについて、テーブル・ルック・アップ区域（カーネル・サポート区域）は、光路長（ＯＤ）の２倍の辺を有する正方形である。ＲＯＩ内部の任意の点「Ｘ０」において、テーブル値は、直線の輪郭線２０のいずれかに沿って一定である。しかし、ＲＯＩ１０の外部にある任意の点「Ｘ０」３０において、図のように、輪郭線２０が、水平方向または垂直方向のいずれかでＲＯＩの外に延長され、そのような点「Ｘ０」３０のコンボリューション値は、同一の輪郭線に沿ったＲＯＩの境界では、点「Ｘ０＊」３０’が採用される。この処理を、一般にコンティニュエーション（continuation）と称する。
【００１０】
さらに図１に関して、ＲＯＩ内にある各点または頂点のすべてのコンボリューション寄与が、事前に計算され、行列にストアされる。ポリゴンに寄与しない、ＲＯＩの外部の他のすべての点、たとえば、ＲＯＩの左および下の境界を超えた点について、そのような点のコンボリューション値は、０に等しい。次に、カーネルを伴うポリゴンのコンボリューションが、ＲＯＩ内にあり、寄与する事前に計算されストアされたセクタのそれぞれの寄与を合計することによって計算される。
【００１１】
従来のセクタに基づくＯＰＣ計算のもう１つの例では、図２および３に、４５°セクタのルックアップ・テーブル値を示す。図からわかるように、４５°の角度のセクタについて、上半分で継続される輪郭線が、垂直ではなく、横にスキュー（skew）され、それぞれが上側領域で４５°の傾斜を有し、輪郭線に沿って一定の値を有する。この横にスキューされた輪郭線が、オルソ４５設計（ortho-45design）に適用可能である。
【００１２】
したがって、点「Ｘ０」３０が、ＲＯＩ１０上にある時に、値は、ＲＯＩの境界にあり、同一の横にスキューされた輪郭線に沿った点「Ｘ０＊」３０’が採用される。同様に、ＲＯＩ内のすべての点「Ｘ０」で、テーブル値は、横にスキューされた４５°セクタのいずれか１つに沿って一定である。各４５°セクタの頂点でのコンボリューションが、ＲＯＩ内のすべての点「Ｘ０」について、計算され、行列にストアされる。図３のＲＯＩ１０の外部にあるすべての点「Ｘ０」のルックアップを簡単にするために、テーブル・ルックアップ区域の上半分が、４５°輪郭線と同一の横方向でスキューされる。
【００１３】
しかし、それを行う際の短所が、図３で矢印によって示されているように、スキューされたＲＯＩ１０’の頂点に関する半径の外にある任意の点が、事前に計算される行列の外にあり、したがって、ポリゴンのコンボリューションに寄与を一切追加しないことである。したがって、従来のやり方は、（１−１／√２）×ＲＯＩの距離だけスキューされたＲＯＩ１０’をテーブルの４つのすべての辺でこの量だけ延長して、拡張されたＲＯＩ１５を提供することである。これによって、明らかにより大きいルックアップ・テーブルすなわちＲＯＩ１５が作られ、これについて、各４５°セクタに沿った点「Ｘ０」でのコンボリューション寄与を、事前に計算し、行列にストアしなければならない。より大きいルックアップ・テーブルＲＯＩ１５は、それをストアするためにより増大したメモリを必要とすることのほかに、ＲＯＩ１５内のポリゴンの寄与するコンボリューション頂点のすべてを計算するのにさらに多くの時間およびメモリを必要とするので、望ましくない。さらに、スキューされたルックアップ・テーブルを、その後に、コンピュータに実装するために正方形の行列に変換しなければならず、そこで、すべての頂点に関する座標変換が必要になるので、この手法は望ましくない。
【００１４】
ポリゴン・クロッピング（polygon cropping）手順も、元のポリゴンの頂点の複数ポリゴン表現を形成するのに使用され、これによって、これら複数の新しいポリゴンのそれぞれの頂点が、その後、ＲＯＩにピンニングされる。そのような方法の１つを、交差法（intersectionmethod）と称する。これには、アルゴリズムＣ＝Ａ∪Ｂ（ただし、形状Ａはポリゴン、形状ＢはＲＯＩ、交差Ｃは複数の新しいより小さいポリゴンの世代）を使用して、元のポリゴンの複数のクロッピングされたポリゴンを生成することが含まれる。残念ながら、ポリゴンの多数のレベルおよびさまざまなデータ構造ならびに複雑な階層が作成されるので、これによって、かなりの量のメモリを必要とする多数の割振りステップが手順に導入されると同時に、これらの複数のポリゴンを生成する際の大量の数値的オーバーヘッドおよびトポロジ（形状）オーバーヘッドを伴う。その結果、クロッピング手順は、通常は全チップ補正が必要なので、処理時間でのかなりの量のオーバーヘッドも必要とする。一般的なクロッピング手順のもう１つの短所は、元のポリゴンの頂点を表す新しい複数のポリゴンの形成での数値誤差に起因して、元のポリゴンの極性を変更することにつながるチップ・トポロジの形状変更の結果として、手順に数値的不安定性がしばしば導入されることである。
【００１５】
その結果、当技術分野には、光リソグラフィの光学的近接効果補正に使用される、ＲＯＩ内のポリゴンをコンボリューションする改善された方法を提供する必要がある。
【００１６】
本発明は、モデルに基づくＯＰＣ計算で使用される独自のアルゴリズムによって、正確に、効率的に、簡単に、かつコスト効率のよい形で、ＲＯＩ内に位置付けられたポリゴンの新しい頂点を作成し、そのような頂点をＲＯＩにピンニングする、改善されたポリゴン・ピンニング方法を提供することによって、従来技術の上記の問題および不足な所を克服する。
【特許文献１】米国特許出願第１０／６９４４６６号
【特許文献２】米国特許出願第１０／６９４４６５号
【特許文献３】米国特許出願第１０／６９４３３９号
【特許文献４】米国特許出願第１０／６９４２９９号
【発明の開示】
【発明が解決しようとする課題】
【００１７】
従来技術の問題および不十分な所を念頭において、本発明の目的は、ＯＰＣ計算に使用される独自のアルゴリズムを使用して、ＲＯＩ内に位置付けされた（locate）ポリゴンの新しい頂点を作成し、これを縮約する（collaps）ことによってそのような頂点をＲＯＩにピンニングする、改善されたポリゴン・ピンニング方法を提供することである。
【００１８】
本発明のもう１つの目的は、正確に、効率的に、簡単に、かつコスト効率のよい形で、関心領域（ＲＯＩ）内のポリゴンをコンボリューションするポリゴン・ピンニング方法を提供することである。
【００１９】
本発明のもう１つの目的は、セクタに基づくＯＰＣ計算でのデータ構造の数および数値オーバーヘッドを減らすポリゴン・ピンニング方法を提供することである。
【００２０】
本発明のもう１つの目的は、ＲＯＩ内のポリゴンをコンボリューションする速度を増やすことによって計算時間を節約するポリゴン・ピンニング方法を提供することである。
【００２１】
本発明のもう１つの目的は、ＯＰＣ計算のポリゴン・コンボリューション計算を実行するのに必要なメモリの量を減らすポリゴン・ピンニング方法を提供することである。
【００２２】
本発明のもう１つの目的は、ＲＯＩ内に位置付けられるポリゴンを表す頂点を有する多数のより小さなポリゴンの生成を避けるポリゴン・ピンニング方法を提供することである。
【００２３】
本発明のもう１つの目的は、ＯＰＣ計算の数値的安定性を改善するポリゴン・ピンニング方法を提供することである。
【００２４】
本発明の他の目的および長所は、部分的には明白であり、部分的には本明細書から明白になる。
【課題を解決するための手段】
【００２５】
当業者には明らかな上記その他の目的は、第１の態様でモデルに基づく光学的近接効果補正を実施する方法を対象とする本発明で達成される。この方法には、境界と共に関心領域（ＲＯＩ）を有するマスク行列（mask matrix）を設けることが含まれる。複数の関心点（point of interest）が、マスク行列内に位置付けられ、次に、第１の単一ループ有限幾何形状（finitegeometrical shape）が、位置付けられた複数の関心点を表す複数の頂点を有するように決定される。この第１の単一ループ有限幾何形状を、ＲＯＩ上に縮約（collapse）して、光学的近接効果を補正する。それを行う際に、第２の縮約された単一ループ有限幾何形状を、ＲＯＩの外部にある第１の単一ループ有限幾何形状の頂点をＲＯＩの境界にピンニングすることによって、ＲＯＩ上で形成する。
【００２６】
この態様によれば、第１および第２の単一ループ有限幾何形状を、同一のまたは異なる有限幾何形状を有するものとすることができ、同一のまたは異なる数の頂点を有するものとすることができる。第１の単一ループ有限幾何形状は、複数の関心点とＲＯＩの間の相関に基づいて計算されることが好ましい。
【００２７】
計算された第１の単一ループ有限幾何形状の縮約のステップにおいて、そのようなループの第１および第２の隣接する頂点を位置付け、次に、これらの頂点の位置を、ＲＯＩに関して行列内で判定する。それを行う際に、この第１および第２の頂点の位置がＲＯＩ内である場合に、そのような頂点の第１頂点を、ＲＯＩ内の第２の単一ループ有限幾何形状の第１頂点に割り当て、その後、この処理を、第１の単一ループ有限幾何形状の残りのすべての頂点について繰り返す。
【００２８】
その代わりに、第１頂点がＲＯＩ内にあり、第２頂点がＲＯＩの外にある場合に、第２頂点を、ＲＯＩの境界との交差（intersection）に最も近い点にピンニングする。第１頂点を、次に前記ＲＯＩ内の前記第２の単一ループ有限幾何形状の第１頂点に割り当て、第２のピンニングされた頂点を、ＲＯＩ内の第２の単一ループ有限幾何形状の第２頂点に割り当てる。次にこの処理を、第１の単一ループ有限幾何形状の残りのすべての頂点について繰り返す。
【００２９】
その代わりに、第１頂点がＲＯＩの外、第２頂点がＲＯＩ内にある場合に、第１頂点を、ＲＯＩの境界との交差に最も近い点にピンニングする。第１のピンニングされた頂点を、ＲＯＩ内の第２の単一ループ有限幾何形状の第１頂点に割り当て、次に、この処理を、第１の単一ループ有限幾何形状の残りのすべての頂点について繰り返す。
【００３０】
第１頂点および第２頂点の位置が、両方ともＲＯＩの外にある場合に、第１頂点があるマスク行列の領域を決定し、その後、それがあるマスク行列の領域に基づいてＲＯＩの境界に第１頂点をピンニングする。具体的に言うと、第１頂点が、ＲＯＩの角（corner）に隣接する領域内にある場合に、第１頂点を、ＲＯＩの最も近い角（コーナー）にピンニングする。しかし、第１頂点が、ＲＯＩの側方辺（lateraledge）に隣接する領域にある場合に、第１頂点を、ＲＯＩの最も近い側方辺にピンニングする。その後、この処理を、第１の単一ループ有限幾何形状の残りのすべての頂点について繰り返す。
【００３１】
第１頂点が、ＲＯＩの角または側方辺にピンニングされたならば、第１頂点と第２頂点をつなぐ第１の単一ループ有限幾何形状の側方辺を位置付け、そのような結ぶ辺が２つのピンニングされた点でＲＯＩと交差するかどうかを判定する。側方辺が２つのピンニングされた点でＲＯＩと交差すると判定される場合に、そのような点のうち第１の点を、第２の単一ループ有限幾何形状の第１頂点に割り当て、そのような点のうち第２の点を、第２の単一ループ有限幾何形状の第２頂点に割り当てる。
【００３２】
その代わりに、側方辺が２つのピンニングされた点でＲＯＩと交差しないと判定される場合には、第１頂点および第２頂点が、マスク行列の同一領域内にあるかどうかを判定する。それを行う際に、第１頂点と第２頂点が同一の領域にある場合に、第１の単一ループ有限幾何形状の残りのすべての頂点について、この処理を繰り返す。第１頂点と第２頂点が同一の領域内にないと判定される場合には、第１頂点と第２頂点が、マスク行列の隣接領域にあるかどうかを判定しなければならない。第１頂点と第２頂点が、マスク行列の隣接領域内にある場合には、残りのすべての頂点についてこの処理を繰り返す。しかし、第１頂点と第２頂点が隣接領域内にない場合には、第１頂点と第２頂点がマスク行列の隣接領域内に実際にないかどうかを判定しなければならない。この判定によって、第１頂点と第２頂点がマスク行列の隣接する領域にないのではないという結果がもたらされる場合に、処理は、計算のエラーに起因して停止される。第１頂点と第２頂点が実際にマスク行列の隣接領域にないと判定される場合には、そのような第１頂点と第２頂点を結ぶ側方辺は、ＲＯＩの外に存在しなければならない。したがって、追加の頂点を、ＲＯＩの境界で、第１頂点と第２頂点を結ぶ側方辺に関してそのＲＯＩの近い角に追加する。
【００３３】
第２の態様で、本発明は、境界と共に関心領域（ＲＯＩ）を有するマスク行列を設けることと、マスク行列内で複数の関心点を位置付けることによってモデルに基づく光学的近接効果補正を実行する方法を対象とする。位置付けられた複数の関心点を表す複数の頂点を有する第１の単一ループ・ポリゴンを、計算し、複数の頂点のうちの選択された頂点を、ＲＯＩの境界にピンニングして、ＲＯＩ上の第２の単一ループ・ポリゴンを形成する。複数の頂点のうちのこれらの選択された頂点を、上述したように、ＲＯＩに関する空間的関係に基づいて、ＲＯＩにピンニングする。次に、光学的近接効果を、この第２の単一ループ・ポリゴンを使用して補正する。
【００３４】
この態様では、位置付けられた複数の関心点が、マスク行列内のポリゴンのグループを表し、第１の単一ループ・ポリゴンの複数の頂点が、ポリゴンのグループのすべての頂点を表す。本発明の第２の態様のピンニング・ステップを、第１の単一ループ・ポリゴンのすべての頂点について繰り返し、第２の単一ループ・ポリゴンが、ＲＯＩの境界およびその内部に縮約されるようにする。
【００３５】
第３の態様で、本発明は、モデルに基づく光学的近接効果補正を実行する方法ステップを実行するためにマシンによって実行可能な命令のプログラムを確実に実施する、マシンによって可読のプログラム記憶装置を対象とする。この方法ステップには、境界と共にＲＯＩを有するマスク行列を設けることと、マスク行列内の複数の関心点を位置付けることが含まれる。位置付けられた複数の関心点を表す複数の頂点を有する第１の単一ループ有限幾何形状を決定し、第１の単一ループ有限幾何形状を、ＲＯＩ上で縮約して、光学的近接効果を補正する。
【００３６】
本発明の特徴は、新規であると考えられ、本発明の特性を表す要素は、請求項に具体的に示されている。図面は、例示のみのものであり、原寸通りに描かれてはいない。しかし、本発明自体は、編成および動作の方法の両方に関して、添付図面と共に以下の詳細な説明を参照することによって最もよく理解することができる。
【発明を実施するための最良の形態】
【００３７】
本発明の実施形態の説明において、図面の図１から図１０を参照するが、図面では、同じ符号が同じ要素（feature）を指す。
【００３８】
本発明は、モデルに基づくシミュレーションによる関心領域（ＲＯＩ）を有する行列内の有限幾何形状を当初に位置付ける、モデルに基づく光学的近接効果補正を対象とする。前述のモデルに基づく光学的近接効果補正（ＯＰＣ）は、フォトレジストを被覆されたウェハ上への正確な投射のために、所望の回路パターンを有するフォトマスク上の任意のひずみに対して、最終的な補正のために光リソグラフィで使用される。
【００３９】
本発明が、すべての有限幾何形状と共に使用するのに適することを理解されたい。好ましい実施形態では、有限幾何形状が、ポリゴンである。設計におけるポリゴンは、通常は、頂点および対応するシーケンス（sequence）の組によって定義され、たとえば、規約（convention）によって、順方向に進む辺（forward movingedge）の左側を、必ずポリゴンの内側とすることができる。本発明によれば、ポリゴンは、規則的または不規則、凸または凹、あるいはこの組合せとすることができる。さらに、ポリゴンに、三角形、四辺形（正方形、長方形、平行四辺形）、５角形、６角形、７角形、８角形、９角形、１０角形など含む任意の形状を含めることができる。
【００４０】
本発明は、モデルに基づくＯＰＣで使用される改善されたアルゴリズムおよびポリゴン・ピンニング方法を提供する。当初に、モデルに基づくシミュレーションには、ポリゴンまたはポリゴンのグループの頂点を表すものなど、有限形状を表す複数の関心点を位置付けることが含まれる。これらの点は、関心領域を含むモデルに基づくマスク行列内にあるものとすることができる。
【００４１】
これらの位置付けられたポリゴンのコンボリューション寄与を合計するために、本発明の効率的なポリゴン・ピンニング方法およびアルゴリズムでは、行列内の複数の位置付けられた関心点を表す頂点を有する単一の閉ループ・ポリゴンが、そのような位置付けられた点が行列内の単一ポリゴンまたはポリゴンのグループのどちらを表していても、計算される。位置付けられた点が、行列内のポリゴンを表す場合に、本発明の計算された閉ループ・ポリゴンは、そのようなポリゴンのすべてを組み合わせたものよりかなり大きい。
【００４２】
本発明によれば、計算された単一の閉ループ・ポリゴンが、ＲＯＩの境界またはＲＯＩ内あるいはその両方に縮約（collapse）され、第２の（すなわち縮約された）単一閉ループ・ポリゴンが形成され、この第２の単一閉ループ・ポリゴンは、行列内の元の位置付けられた関心点（頂点）を表す頂点を有する。この縮約されたポリゴンは、ＲＯＩの外にある位置付けられた関心点をＲＯＩの境界およびＲＯＩ内にピンニングすることによってＲＯＩに縮約され、縮約されたポリゴンのすべての頂点が、ＲＯＩの境界およびＲＯＩ内に存在するようになる。この縮約されたポリゴンが、フォトマスク上の任意のひずみの最終的な補正のために、位置付けられた関心点のコンボリューション寄与の後続の合計に使用される。
【００４３】
図面を参照すると、本発明のこの単一ループ・ポリゴンおよび処理フローは、図４および５に示された流れ図の以下の説明によってよりよく理解されるが、この図で、丸の中の文字は、流れ図の他方の部分との接続を示す。
【００４４】
ステップ１０００  開始。処理を開始する。
【００４５】
ステップ１００５  新ポリゴンＳ、頂点ｊ＝１。本発明の新しい縮約された単一ループ・ポリゴン「Ｓ」は、ｊ＝１の頂点を有する。
【００４６】
ステップ１０１０  旧ポリゴンＰ、頂点ｋ＝１。行列内の元の計算されたポリゴン「Ｐ」は、ｋ＝１の頂点を有する。
【００４７】
ステップ１０１５  Ｋ＝Ｎｖｅｒｔｅｘ（Ｎ頂点）か。ポリゴン「Ｐ」の最後の頂点すなわち点に達したか。そうである場合には、ステップ１０２０に進み、処理を終了する。そうでない場合には、ステップ１０１３に進み、処理を継続する。
【００４８】
ステップ１０２０  終了。処理を終了する。
【００４９】
ステップ１０１３  ポリゴン「Ｐ」の２つの隣接する頂点すなわち点、言いかえれば、頂点ＰｋおよびＰｋ＋１を位置付ける。ステップ１０２５に継続する。
【００５０】
ステップ１０２５  ＰｋおよびＰｋ＋１はＲＯＩ内にあるか。ポリゴン「Ｐ」の２つの隣接する頂点ＰｋおよびＰｋ＋１の両方がＲＯＩにあるか。そうである場合には、ステップ１０３０に進む。そうでない場合には、ステップ１０４０に進む。
【００５１】
ステップ１０３０  Ｓｊ＝Ｐｋ。ＰｋをＳｊに割り当てる。ステップ１０３５に継続する。
【００５２】
ステップ１０３５  ｊ＝ｊ＋１。ポリゴンＰの次の頂点に進む。ステップ２０５０に継続する。
【００５３】
ステップ１０４０  ＰｋがＲＯＩ内、Ｐｋ＋１がＲＯＩ外か。ポリゴン「Ｐ」の頂点ＰｋがＲＯＩ内にあり、ポリゴン「Ｐ」の頂点Ｐｋ＋１がＲＯＩの外になるか。そうである場合にはステップ１０４５に進む。そうでない場合にはステップ１０５５に進む。
【００５４】
ステップ１０４５  Ｐｋ＋１を、ＲＯＩの境界との最も近い交差点Ｐ’ｋ＋１にピンニングする。ステップ１０５０に継続する。
【００５５】
ステップ１０５０  Ｓｊ＝Ｐｋ、Ｓｊ＋１＝Ｐ’ｋ＋１、ｊ＝ｊ＋２。ステップ２０５０に継続する。
【００５６】
ステップ１０５５  ＰｋがＲＯＩ外、Ｐｋ＋１がＲＯＩ内か。ポリゴン「Ｐ」の頂点ＰｋがＲＯＩの外であり、ポリゴン「Ｐ」の頂点Ｐｋ＋１がＲＯＩの中か。そうである場合にはステップ１０６０に進む。そうでない場合にはステップ１０７０に進む。
【００５７】
ステップ１０６０  Ｐｋを、ＲＯＩ境界との最も近い交差点Ｐ’ｋに「ピンニング（Pin）」する。ステップ１０６５に継続する。
【００５８】
ステップ１０６５  Ｓｊ＝Ｐｋ’、ｊ＝ｊ＋１。Ｐ’ｋをＳｊに割り当て、次に、ステップ２０５０に継続することによってポリゴン「Ｐ」の次の頂点に進む。
【００５９】
ステップ１０７０  ＰｋおよびＰｋ＋１の両方がＲＯＩの外か。元のポリゴン「Ｐ」の頂点ＰｋおよびＰｋ＋１の両方が、ＲＯＩの外にあるか。そうである場合にはステップ１０７５に進む。そうでない場合にはステップ１０９５に進む。
【００６０】
ステップ１０７５  Ｐｋは領域［１、３、５、７］内にあるか。元のポリゴン「Ｐ」の頂点Ｐｋが、行列の領域１、３、５、または７の中にあるか。そうである場合にはステップ１０８０に進む。そうでない場合にはステップ１０８５に進む。
【００６１】
ステップ１０８０  ＰｋをＲＯＩの最も近い角にＣｏｒｎｅｒ＿ｐｉｎし、Ｓｊ＝角、ｊ＝ｊ＋１。Ｐｋは、行列の領域１、３、５、または７のいずれかにあり、したがって、Ｐｋを、ＲＯＩの最も近い角にピンニングする（図１０参照）。ステップ２００５に継続する。
【００６２】
ステップ１０８５  Ｐｋは領域［２、４、６、８］内にあるか。元のポリゴン「Ｐ」の頂点Ｐｋが、行列の領域２、４、６、または８の中にあるか。そうである場合にはステップ１０９０に進む。そうでない場合にはステップ１０９５に進む。
【００６３】
ステップ１０９０  ＰｋをＲＯＩの最も近い辺にＯｒｔｈｏ＿ｐｉｎし、Ｓｊ＝交差、ｊ＝ｊ＋１。Ｐｋは、行列の領域２、４、６、または８のいずれかにあり、したがって、Ｐｋを、境界辺に直交する方向で最も近いＲＯＩ境界にピンニングする（図１０参照）。ステップ２００５に継続する。
【００６４】
ステップ１０９５  エラー。計算にエラーがある。ステップ２０００に進み、処理を終了する。
【００６５】
ステップ２０００  終了。処理を終了する。
【００６６】
ステップ２００５  ＰｋおよびＰｋ＋１は、２つの点Ｑ１およびＱ２でＲＯＩと交差するか。頂点ＰｋおよびＰｋ＋１を結ぶポリゴンＰの稜線（lateral edge；側方辺）が、２つの点すなわちＱ１およびＱ２でＲＯＩと交差するか（図７参照。図７では、頂点Ｐ８およびＰ９に関するポリゴンＰの稜線２０３が、２つの点Ｑ１およびＱ２でＲＯＩ（０）と交差する）。そうである場合にはステップ２０１０に進む。そうでない場合にはステップ２０１５に進む。
【００６７】
ステップ２０１０  Ｓｊ＝Ｑ１、Ｓｊ＋１＝Ｑ２、ｊ＝ｊ＋２。Ｑ１をＳｊに割り当て、Ｑ２をＳｊ＋１に割り当て、Ｓの頂点インデックスを２増分する。ステップ２０５０に進む。
【００６８】
ステップ２０１５  ＰｋとＰｋ＋１が同一領域にあるか。頂点ＰｋおよびＰｋ＋１が、マスク行列の同一領域にあるか。そうである場合にはステップ２０５０に進む。そうでない場合にはステップ２０２０に進む。
【００６９】
ステップ２０２０  ＰｋとＰｋ＋１が直接に隣接するか。頂点ＰｋおよびＰｋ＋１が、マスク行列の同一領域内にない場合に、互いに少なくとも１つの辺を共用する（ＲＯＩ辺を除く）、行列の直接隣接する領域内にあるか。そうである場合にはステップ２０５０に進む。そうでない場合にはステップ２０２５に進む。
【００７０】
ステップ２０２５  ＰｋとＰｋ＋１が直接に隣接「しない」か。頂点ＰｋおよびＰｋ＋１が、マスク行列の直接に隣接する領域内に「ない」か。そうである場合にはステップ２０４０に進む。そうでない場合にはステップ２０３０に進む。
【００７１】
ステップ２０３０  エラー。計算にエラーがある。ステップ２０３５に進み、処理を終了する。
【００７２】
ステップ２０３５  終了。処理を終了する。
【００７３】
ステップ２０４０  Ａｄｄ＿ｃｏｒｎｅｒ（Ｐｋ、Ｐｋ＋１)。頂点ＰｋおよびＰｋ＋１のセクタ交差が、ＲＯＩの外にある（図１０のセクタ・セグメント［３、４］、［７、８］、［８、９］を参照）場合に、ＲＯＩの角で頂点を追加し、ｊ＝ｊ＋１。ステップ２０５０に継続する。
【００７４】
ステップ２０５０  ｋ＝ｋ＋１。ポリゴン「Ｐ」の次の頂点に進む。ステップ１０１５に継続する。
【００７５】
好ましい実施形態では、本発明の単一ループ・ポリゴンおよび上記の処理フローを、本発明の下記の擬似コード（pseudo-code）・ピンニング・アルゴリズムによって最もよく表すことができる。
For k=1 to Num_vertex-1
If Pkが内およびPk+1が内
Sj=Pk, j=j+1
Else If Pkが内およびPk+1が外
Pk+1を最も近い交差Pk+1'にピンニングする
Sj=Pk,
Sj+1=交差, j=j+2
Else If Pkが外およびPk+1が内
Pkを最も近い交差Pk'にピンニングする
Sj=Pk', j=j+1
Else ifが外およびPk+1が外
If Pkが領域[1,3,5,7]内
Sj=corner_pin (Pk), j=j+1
Else if Pkが領域[2,4,6,8]内
Sj=ortho_pin (Pk), j=j+1
If Pk, Pk+1が２点Q1,Q2でROIと交差する
Sj=Q1,
Sj+1=Q2, j=j+2
Else if PkおよびPk+1が同一領域内
動作なし
Else if PkおよびPk+1が直接に隣接
動作なし
Else if PkおよびPk+1が直接に隣接する領域にない
Sj=add_corner (Pk,Pk+1), j=j+1
Elseエラー
Else
エラー
End
END
【００７６】
本発明の長所は、このプロセス・フローおよびピンニング・アルゴリズムによって、同時に複数の点に対する任意の角度のセクタから大きい単一ループ・ポリゴンを計算できるようになることである。このポリゴンは、縮約されたポリゴンのコンボリューション寄与の後続の合計のために、その頂点をピンニングすることによってＲＯＩに縮約され、縮約されたポリゴンは、元の位置付けられた関心点すなわち、マスク行列内の位置付けられた有限幾何形状の頂点を表す。
【００７７】
図６から９を参照すると、この処理フローおよびピンニング・アルゴリズムが、所定の数の領域または分割（division）を有するマスク行列５０内の、参照符号Ｐ１からＰ１６のさまざまな点のさまざまな９０°セクタについて示されている。たとえば、図６からわかるように、マスク空間またはマスク行列５０は、領域（０）から領域（８）までの９つの領域に分割される。しかし、本発明が、マスクの９つの領域への分割に制限されず、所望のフォトマスク上のひずみの最終的な補正に必要な任意の個数のマスク分割と共に使用できることを諒解されたい。さらに、マスク分割が、四辺形として示されているが、マスクを、当技術分野で既知であり、使用されているように、任意の有限幾何分割に分割できることも諒解されたい。
【００７８】
図７からわかるように、領域（０）から領域（８）を有するマスク空間が、破線の図を介して示されている。本発明のモデルに基づくＯＰＣ技法の対象区域は、符号１００によって示される領域（０）であり、この領域を、関心領域「ＲＯＩ」と称する。当初に、ポリゴンなどの少なくとも１つの有限幾何形状またはその代わりに複数の有限幾何形状（ポリゴン）を、マスク行列５０内に位置付けられる。それを行う際に、複数の関心点、たとえばＰ１からＰ１６が位置付けられ、これによって、これらの点が、すべての位置付けられた有限幾何形状のすべての頂点を表す。図７からわかるように、これらの点の一部が、ＲＯＩ１００内にあり（たとえば、Ｐ２、Ｐ６、およびＰ７）、他の点は、ＲＯＩの外にある（たとえば、Ｐ１、Ｐ３、Ｐ４、Ｐ５、およびＰ８からＰ１６）。ＲＯＩの外にある点は、マスク行列５０のさまざまな他の領域内にある。たとえば、図７からわかるように、点Ｐ１５およびＰ１６は、領域１内にあり、点Ｐ１およびＰ３は、領域２内にある。
【００７９】
マスク行列内の複数の点Ｐ１からＰ１６を使用して、任意の有限幾何形状を有する大きい単一ループ・ポリゴン「Ｐ」２００が、本発明のピンニング・アルゴリズムを使用して計算される。それを行う際に、ポリゴン「Ｐ」２００の有限幾何形状は、複数の位置付けられた関心点すなわちＰ１からＰ１６を表す複数の頂点を有し、これによって、ポリゴン「Ｐ」２００の各頂点が、そのような点の少なくとも１つを表す。マスク行列の、関心点を有しない領域は、ポリゴンのコンボリューションに寄与しない。たとえば、図７からわかるように、領域（７）および（８）は、その中に点を有しておらず、したがって、ポリゴン２００は、この領域に拡張されず、領域（７）および（８）からの後続の寄与がなくなる。
【００８０】
大きい単一ループ・ポリゴン「Ｐ」２００を計算し、形成したならば、図８および９に示されているように、これをＲＯＩ１００の境界上で縮約する。ポリゴン「Ｐ」２００を縮約する際に、ポリゴン「Ｐ」２００を、ＲＯＩの表面に、またはＲＯＩ（０）１００の境界上およびその中にコンボリューションを行い、新しいポリゴン「Ｓ」３００を形成する。この縮約されたポリゴン「Ｓ」３００は、ＲＯＩ１００の境界またはその中あるいはその両方に沿って形成され、元のポリゴン「Ｐ」２００と同一の有限幾何形状を有する場合とそうでない場合がある。さらに、元のポリゴン「Ｐ」２００および縮約されたポリゴン「Ｓ」３００は、頂点の数が同一の場合と異なる場合がある。たとえば、図８および９に示されているように、ポリゴン「Ｓ」３００は、頂点１’から８’、８”、および９’から１６’（１７個の頂点）を有するものとして図示され、これらの頂点は、ポリゴン「Ｐ」２００の頂点Ｐ１からＰ１６（１６個の頂点）を表す。それを行う際に、前にＲＯＩの外にあったすべての頂点が、ＲＯＩの境界上に縮約され、前にＲＯＩ内にあったすべての頂点は、変更されない。
【００８１】
ポリゴン「Ｓ」３００は、ＲＯＩ１００の外にあるすべての位置付けられた点をＲＯＩ（０）の境界およびその中にピンニングすることによって縮約される。それを行う際に、本発明の重要な特徴は、元々はＲＯＩ１００の外にあった点が、新しいポリゴン「Ｓ」３００内で一緒にマージされるかオーバーラップすると同時に、本発明の閉じた単一ループ・ポリゴン構造体が維持されることである。
【００８２】
しかし、本発明の理解を簡単にするために、元々ＲＯＩ（０）１００内にあったＰ２、Ｐ６、およびＰ７を除くすべての点が、新しいポリゴン「Ｓ」３００内でＲＯＩ境界にピンニングされ、単に、縮約されたポリゴン「Ｓ」３００の単一の閉ループ構造体を示すために、図８および９で別々の点として図示されている。元のＲＯＩ外の任意の点のピンニングとポリゴン「Ｓ」３００の単一閉ループ構造体が、本発明に必須である。というのは、これによって、大きい閉ループ・ポリゴン２００をＲＯＩ内のより小さいポリゴンに分割する必要がなくなり、したがって、大きい閉ループ・ポリゴン２００内に含まれる階層およびデータが有利に保存されるからである。これによって、つまり処理オーバーヘッドが減ることによって数値的安定性が大幅に高まる。
【００８３】
計算されたポリゴン「Ｐ」のすべての頂点をＲＯＩの境界およびその中にピンニングしたならば、縮約された閉ループ単一ループ・ポリゴン「Ｓ」３００が形成される。それを行う際に、縮約されたポリゴンで、元のポリゴン「Ｐ」２００の頂点の数が保存されない場合がある、すなわち、頂点Ｐ１からＰ１６が維持されない。新しい縮約されたポリゴン「Ｓ」３００は、元の大きいポリゴン「Ｐ」２００の頂点の数「Ｐ＃」と比較して、より多数の頂点「Ｐ＃’」を有する場合があり、あるいはその代わりにより少数の頂点を有する場合がある。すなわち、本発明の上の擬似コードに関して、元の計算された大きい単一ループ・ポリゴン「Ｐ」は、頂点Ｐｋを有し、ここで、ｋ＝１、２、３、．．．Ｎｖｅｒｔｅｘ（Ｎ頂点）であり、縮約された単一ループ・ポリゴン「Ｓ」は、頂点Ｓｋを有し、ここで、ｋ＝１、２、３、．．．Ｎ’ｖｅｒｔｅｘであり、ＰｋおよびＳｋは、同一または異なるものとすることができる。図８および９を参照すると、縮約されたポリゴン「Ｓ」３００は、元の大きいポリゴン「Ｐ」２００より多数の頂点を有する。具体的に言うと、ポリゴン「Ｐ」２００の頂点Ｐ８が、２つの異なる位置８’および８”でＲＯＩ境界にピンニングされている。これは、コンボリューションに関して、ＰｋのＲＯＩ内にある部分が変更されないままになることを保証するのに必須である。
【００８４】
カーネル（kernel）を用いる縮約されたポリゴン「Ｓ」３００のコンボリューションを実行して、所望の結果を得ることができる。これは、ＲＯＩ（０）内またはその境界上のものだけの各９０°セクタからの寄与を合計することによって達成することができる。ＲＯＩ（０）１００の外にある点は、ポリゴンにコンボリューション寄与を追加しない。
【００８５】
図１０を参照すると、本発明の処理フローおよびピンニング・アルゴリズムが、マスク行列５０内のさまざまな点Ｐ１からＰ８の４５°セクタについて示されている。再び、マスク行列５０は、領域（０）から（８）を有し、領域（０）が、関心領域（ＲＯＩ）である。図からわかるように、関心点Ｐ１からＰ９のすべてが、マスク行列５０内に配置されている。大きい単一ループ・ポリゴン５００が、本発明に従って計算されて、そのような位置付けられた関心点Ｐ１からＰ９のすべてを表す。それを行う際に、この単一ループ・ポリゴン５００の頂点が、関心点Ｐ１からＰ９を表し、これによって、そのような頂点の選択された１つ、頂点Ｐ３、Ｐ４、およびＰ８などが、４５°セクタにある。各４５°セクタに関して、そのセクタのＲＯＩ（０）との交差が、ＲＯＩ（０）の外にあると判定される場合に、頂点が、ＲＯＩの角に追加される。
【００８６】
長所は、ＯＰＣに関するこの方法およびアルゴリズムによって、特にポリゴンの稜線からそのポリゴンの次の稜線へ、辺ごとにポリゴンが分析されることである。これは、４５°セクタを有するポリゴンに特に有用である。本質的な特徴は、４５°ラインによって、頂点のピンニングによってＲＯＩの境界およびその中に大きいポリゴン５００が縮約された後でも傾斜（slope）が維持されると同時に、本発明の単一ループ・ポリゴン構造体が維持されることである。ピンニングされた頂点は、図１０では、ＲＯＩ（０）の境界に沿った円として示されている。４５°セクタに関する本発明のもう１つの長所は、スキューされたテーブルの必要がなくなることである。
【００８７】
本発明のすべての態様で、ＯＰＣで使用されるこのピンニング方法およびアルゴリズムによって、カーネルを空間的に切り捨てる必要があるのではなく、マスクを（２×ＲＯＩ）２のサイズの正方形に切り捨てる、米国特許出願第１０／６９４４６６号で開示された三角形コンボリューションの使用も容易になることである。すなわち、本発明のテーブル・メモリ・サイズを、４５°セクタについても（２×ＲＯＩ）２以内に減らすことができる（スキューされたテーブルをなくすことによる利益）。
【００８８】
前述の説明に鑑みて、本発明は、従来のカーネル切捨手法（kerneltruncation approach）に対して余分な複雑さを導入しない。本発明のピンニング・アルゴリズムは、複数の点のコンボリューションをＲＯＩ内のポリゴンの単一の検索で実行できるようにするアルゴリズムを提供することによるコンボリューション処理の高速化という長所を提供する。本発明の重要な特徴は、ゼロ（０）幅のセグメントを有することができる新しい縮約されたポリゴン「Ｓ」が形成されると同時に、単一閉ループ・ポリゴンが維持されることである。すなわち、上で述べたように、ＲＯＩ内のオーバーラップする任意の辺が、本発明の縮約された単一閉ループ・ポリゴンの完成に基づいてセクタのコンボリューションを打ち消される。さらに、本発明の方法およびアルゴリズムは、追加の頂点（８”）が、縮約されたポリゴン「Ｓ」の結果としてＲＯＩに追加された後であっても、元の計算されたポリゴン「Ｐ」の極性が維持されるという長所を有する。
【００８９】
さらに、本発明では、有利なことに、部分的にＲＯＩ内にあり、位置付けられたポリゴンを表す複数のより小さいポリゴン（従来のクロッピング・モデルに基づくＯＰＣ技法では一般的である）の必要がなく、これが作成されない。本発明によれば、当初に位置付けられた関心点のすべてが、ピンニングされて、ＲＯＩ（０）の境界上またはその中に存在するようになる。それを行う際に、本発明は、かなりの量の処理時間および計算時間を節約すると同時に、従来のＯＰＣ技法に関連する処理ステップ、トポロジ的オーバーヘッド、および数値的不安定性を大幅に減らす、効率的なＯＰＣ計算を提供する。本発明のＯＰＣ技法およびアルゴリズムに必要なメモリの量も、大幅に減る。というのは、本発明で、テーブル・ルックアップを展開する（expand）ためのより小さいポリゴン（より大きいポリゴンを分割することから導出される）のグループの階層に関する記帳（book-keeping）を維持するという時間がかかり単調で退屈な作業の必要がなくなり、スキューされたテーブルまたはテーブル・ルックアップ中の座標変換の必要がなくなり、テーブル・ルックアップ内の継続規約（continuationconvention）の必要がなくなるからである。
【００９０】
この方法は、マシンによって読取可能であり、方法ステップのそれぞれを実行するためにマシンによって実行可能な命令のプログラムを確実に実施するプログラム記憶装置にストアされたコンピュータ・プログラム記録媒体を介して実施することができる。本発明のプログラム記憶装置は、光学特性、磁気特性、または電子回路あるいはこれらの組合せを使用して本発明の方法ステップを実行するマシンの構成要素として考案し、作り、使用することができる。プログラム記憶装置には、磁気ディスケット、磁気テープ、光ディスク、読取専用メモリ（ＲＯＭ）、フレキシブル・ディスク、半導体チップ、および類似物が含まれるが、これに制限はされない。既知のソース・コード内のコンピュータ可読プログラム・コード手段を使用して、上で説明した方法をコンピュータでの使用のために変換することができる。
【００９１】
本発明を、特定の好ましい実施形態と共に詳細に説明したが、多数の代替形態、修正形態、および変形形態が、前述の説明に鑑みて当業者に明白であることは明らかである。したがって、添付請求項は、本発明の真の範囲および趣旨に含まれる、そのような代替形態、修正形態、および変形形態のすべてを含むことが企図されている。
【図面の簡単な説明】
【００９２】
【図１】セクタのコンボリューションをテーブルにストアされた基本画像として事前に計算できるようにするために、ポリゴンを９０°角度のセクタの集合に分解するセクタに基づくＯＰＣエンジンを示す、従来技術の概略図である。
【図２】セクタのコンボリューションをテーブルにストアされた基本画像として事前に計算できるようにするために、ポリゴンを４５°角度のセクタの集合に分解するセクタに基づくＯＰＣエンジンを示す、もう１つの従来技術の概略図である。
【図３】テーブル・ルック・アップ区域を、あるｘ０値を含むように関心領域に類似する形でスキューしなければならないことを示す。図２の従来技術を示す概略図である。
【図４】本発明を実施する際に使用される好ましいステップを示す流れ図である。
【図５】本発明を実施する際に使用される好ましいステップを示す流れ図である。
【図６】セクタに基づくＯＰＣについて、図３に示された処理フローで使用される、関心領域を含む複数の領域を有するマスク行列のモデルを示す、本発明の概略図である。
【図７】関心点を位置付け、図６の行列内の位置付けられた関心点を表す複数の頂点を有する９０°セクタの大きい単一ループ・ポリゴンを計算するステップを示す、本発明の概略図である。
【図８】ＲＯＩ内およびその境界への図７の大きい単一ループ・ポリゴンの縮約のステップを示す、本発明の概略図である。
【図９】ＲＯＩ内およびその境界にある図８の新しい縮約された単一ループ・ポリゴンを示す、本発明の概略図である。
【図１０】関心点を位置付け、図６の行列内で位置付けられた関心点を表す複数の頂点を有する４５°セクタの大きい単一ループ・ポリゴンを計算するステップを示す、本発明の概略図である。
【符号の説明】
【００９３】
１０  関心領域、ＲＯＩ
１０’  スキューされたＲＯＩ
１５  拡張されたＲＯＩ
２０  輪郭線
３０  点「Ｘ０」
３０’  点「Ｘ０＊」
５０  マスク行列
１００  ＲＯＩ
２００  単一ループ・ポリゴン「Ｐ」
２０３  稜線（側方辺）
３００  新しいポリゴン「Ｓ」
５００  単一ループ・ポリゴン
【図１】
2005165282.tif 000003
【図２】
2005165282.tif 000004
【図３】
2005165282.tif 000005
【図４】
2005165282.tif 000006
【図５】
2005165282.tif 000007
【図６】
2005165282.tif 000008
【図７】
2005165282.tif 000009
【図８】
2005165282.tif 000010
【図９】
2005165282.tif 000011
【図１０】
2005165282.tif 000012