フィーチャー境界の結合
重なり合う第一、第二のフィーチャーの境界に基づいて結合フィーチャー境界を形成する方法は、第一、第二の重なり合うフィーチャーの境界を公知の形状の線セグメントに分け、上記線セグメントによって形成された交差点を同定し、上記交差点のパラメータ座標を計算し、上記パラメータ座標に基づいて交差点評価の順序を決定すること、を含む。この方法はさらに、上記決定された順序における第一交差点を形成する線セグメントに基づき、第一クロス積を演算し、上記第一クロス積の数学符号にしたがって、結合フィーチャー境界の第一パスを選択すること、を含む。この第一パスは第一交差点から上記決定された順序での第二交差点へと延びている。上記方法はさらに、上記順序での第二交差点を形成する線セグメントに基づき第二クロス積を演算し、この第二クロス積の数学符号にしたがって、第二交差点から延びる、結合フィーチャー境界の第二パスを選択すること、を含む。上記結合フィーチャー境界は、上記第一、第二の交差点と、上記第一、第二パスを定める、上記第一、第二のフィーチャー境界のうちの少なくとも一つの、部分を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理に用いられる機器および方法に関し、特に、複数の視野から得られた画像のフィーチャーの結合に用いられる機器および方法に関する。
【背景技術】
【０００２】
産業上の利用可能性
自動生産ラインにおいて、生産中の部品やその他の物の検査を助けるために、画像化技術（imaging technology）がしばしば用いられる。このような生産ラインで一般的に用いられる画像化技術としては、例えば、ビデオ画像、デジタル写真および／または他の公知のプロセスがある。通常、公知の画像化技術は、このような製品の画像をある視野内で取得するために用いられ、各画像が多数の幾何学的輪郭を含んでいることがある。このような輪郭は、例えば製造物の、機械加工した表面、穴、角、および／または他の公差の厳しい部分である。これらの公知技術においては、対象領域を示す画像を取得し、この画像に基づいて、撮影された領域の様相がこの製造物にとって許容範囲内に収まるか否かを判断する。例えば、このような画像化技術は、高速製造ラインにおいて、生産中の部品やその他の物を検査し、公差範囲を外れたり及び又は許容不可能な部品を却下（reject、排除）するための助けとして用いられる。
【０００３】
しかし、画像化の一部の適用例において、対象領域が画像化装置の視野よりも大きい場合がある。例えば、上記の製造物を検査及び／又は調査するために用いられるデジタルカメラ等の画像化装置は、視野が比較的小さいことがあり、この視野が、製造物の機械加工された表面全体の画像を捕捉するには小さ過ぎる場合がある。このような適用例においては、対象領域は一つの視野の境界を越えて、他の視野にまで延びることがある。
【０００４】
公知の画像化装置に関連した視野の限界を補うため、あるいは２つの隣接した画像の境界を越えて対象領域の位置決めを行うために、画像化装置は通常、検査対象物の複数の画像を複数の視野から捕えて、その後、デジタル結合ソフトウエア等の手段を用いて、画像の対応する部分または重なり合う部分（overlapping portions）を結合する。異なる視野の画像を結合するこの過程は、「画像縫合」と呼ばれることがある。しかし、公知の縫合技術を用いて異なる視野からの画像を結合する際に、かなりの不正確さが導入されかねない。加えて、このような方法は通常、コンピュータ及び／又はプロセッサの大容量の処理能力または速度を必要とし、運用の観点から極めて煩わしいものになりかねない。
【０００５】
例えば、先行技術のシステムによって得られた画像は通常、「二値」の画素ベースの画像である。このような画像は、オンまたはオフのスクリーン画素の集合によって構成される。先行技術のシステムにおいては、検査対象領域の複数の画素ベースの画像を取得し、そして、その領域全体を確実に捕らえるために、画像ごとに視野を重ね合わせる。例えば、対象領域の最初の画像を取得後、このようなシステムは第二の（隣接する）画像を取得する。このとき、この第二の画像の視野は、第一の画像の視野と重なり合っている。そして、第一の画像と第二の画像を、画素ごとに併合または「縫合」する。
【０００６】
しかし、現実世界では機械加工部品の各輪郭は明確な境界を有しているが、先行技術のシステムによって取得された、輪郭の第一の画素ベースの画像は、同じ輪郭の第二の（隣接する）画素ベースの画像とは、境界の寸法または形状が若干異なる場合がある。例えば、第一の輪郭画像において「オン」であった画素が第二の輪郭画像では「オフ」になることがある。このような２つの隣接する画像間における同一の輪郭の画素のばらつきは、数々の要因に起因し得る。これら要因としては、カメラの微小な回動、画素サイズの不完全な較正、不均一な照明および陰影の効果を含むが、これに限定されない。これら要因は、二値画像の一部の画素を、一方の画像ではオンにさせ、他方の画像ではオフにさせる。輪郭の結合画像を形成する際、先行技術の縫合方法は通常、整列（alignment）および補間（interpolation）の技術によって、２つの画像の対応する画素を結合させ、これらの不正確さを隠している。
【０００７】
残念ながら、公知の縫合法は時間がかかり、しかも、保存および分析に大量のコンピュータメモリを必要とする、潜在的に重い画像を作り出す。公知の縫合法に固有の不正確さは、その結果生成される結合画像が後で他の画像との比較分析に用いられる場合、雪だるま式にその影響が増大する可能性がある。公知の画像結合方法における画素ごとのばらつき、および厄介なメモリ条件は、製造ラインの効率を劇的に低下させかねず、一人以上のオペレータによる監視が必要となる場合がある。このような欠陥は、多くの高速製造環境においては、非常に高コストになりかねない。
【０００８】
２００６年１２月に、『コンピュータ・グラフィックスとコンピュータ・ビジョンの基礎と傾向』の２（１）で発表された「画像の位置合わせおよび縫合」という論文の中で、Szeliskiは従来の方法に関連した更なる問題、すなわち完全自動縫合の信頼性の欠如等について考察した。Szeliskiは、大きな外れ値を許容しつつ、同時に偽のフィーチャーのマッチングや繰り返しパターンのマッチングを避けることは難しいと、指摘した。もう一つ、よくある問題としてSzeliskiが記したのは、「視差」である。視差とは、二つの異なる視線に沿って見たときの、対象物の、見かけ上の変位または向きの違いである。Szeliskiが考察した縫合の欠点は、自動工業検査で用いられる既存の結合方法の正確性、信頼性および速度を、大きく制限するものである。Szeliskiは視差による画像のゆがみの修正に用いられる技法についても教示しているが、これらの修正技法は、ほとんどの高精度測定工程には適していない。
【０００９】
Vaidyanathan等に付与された米国特許第５，３７１，８１０号は、外周の点をＸ、Ｙのデカルト座標と８ビットの方向コード値を用いて登録する方法を開示している。Vaidyanathanはまた、外周の点の間の結合、接続関係を決定するために用いられる配列方法（sorting method、整列方法）も開示している。しかし、Vaidyanathanの外周の点を配列する方法は、複雑な画像結合の適用例においては、機能しない。なぜなら、閉じたフィーチャーの外周の二次元のＸ，Ｙ座標は、両方とも単調ではあり得ないからである。加えて、Vaidyanathanの方法は、同一のＸまたはＹ座標値を有する２つ以上の外周の点が含まれるという特別な状況にある場合には、すべての外周の点を配列することが出来ない。加えて、Vaidyanathanの方法の精密さは、画素の解像度に限定される。なぜなら、ここで教示されている方法および最終結果が、画素ベースだからである。
【００１０】
Beallに付与された米国特許第４，４９３，１０５号は、Vaidyanathan等の特許と類似の、点の配列方法を開示している。Beallの方法も、閉じたフィーチャーの外周の二次元のＸ，Ｙ座標が同時に単調にはなり得ないため、機能しない。Beallの方法もまた、方法とその最終結果が画素ベースであるため、画素の解像度に限定される。Beallでは、フィーチャーの結合については言及していないが、Beallで開示された方法は、いずれも単純な結合の事例しか扱っていない。Beallの方法は、複雑な結合状況、すなわち２つのフィーチャーが重なり合い、または２箇所以上で交差し、これにより複数の結合フィーチャーパス（combined feature paths）が作り出されるような状況では機能しない。加えて、VaidyanathanもBeallも、「単純な」フィーチャーと「穴」フィーチャーとを自動的に区別する方法については教示していない。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
したがって、本開示は、一つの視野よりも大きい二つ以上の画像またはフィーチャーを結合する際に遭遇する問題の解消を目的としている。本開示はまた、二つ以上のフィーチャーリストの結合に関連した困難の解消を目的としている。
【課題を解決するための手段】
【００１２】
本開示の一態様において、重なり合う第一、第二のフィーチャーの境界に基づいて結合フィーチャー境界を形成する方法は、第一、第二の重なり合うフィーチャーの境界を公知の形状の線セグメントに分け、上記２つのフィーチャーの線セグメントによって形成された交差点を同定し、上記交差点のパラメータ座標を計算し、上記パラメータ座標に基づいて交差点評価の順序を決定すること、を含む。この方法はさらに、上記決定された順序における第一交差点を形成する線セグメントに基づき、第一クロス積を演算し、この第一クロス積の数学符号にしたがって結合フィーチャー境界の第一パスを選択すること、を含む。この第一パスは第一交差点から上記決定された順序での第二交差点へと延びている。上記方法はさらに、上記順序での第二交差点を形成する線セグメントに基づき第二クロス積を演算し、この第二クロス積の数学符号にしたがって、第二交差点から延びる結合フィーチャー境界の第二パスを選択すること、を含む。上記結合フィーチャー境界は、上記第一、第二の交差点と、上記第一、第二パスを定める、上記第一、第二のフィーチャー境界のうちの少なくとも一つの、部分を含む。
【００１３】
本開示の態様では、第一、第二の重なり合うフィーチャーの境界に基づいて結合フィーチャー境界を形成する方法は、上記第一、第二のフィーチャー境界の交差によって形成される複数の交差点のパラメータ座標を演算し、上記複数の交差点を、それらのパラメータ座標にもとづいて配列順序に組織化し、各交差点での交差によって形成されたクロス積の数学符号を決定し、上記数学符号に基づいて複数の交差点の各々間での結合フィーチャー境界のパスを決定すること、を含む。この態様では、上記結合フィーチャー境界は、上記配列順序にしたがって配された複数の交差点の各々と、第一、第二のフィーチャー境界のうちの少なくとも１つの、部分を含む。この方法はさらに、上記結合フィーチャー境界によって画成された領域（area，面積）を演算し、上記演算された領域の数学符号に基づいてこの結合フィーチャー境界に関するフィーチャタイプを決定すること、を含む。
【００１４】
本開示のさらに他の態様では、結合フィーチャーリストを作る方法は、フィーチャーの第一、第二のリストを取得し、上記第二リストのフィーチャーの境界と重なる上記第一リストのフィーチャーの境界によって形成される、複数の交差点を同定し、上記の同定された交差点の各々のパラメータ座標を演算し、上記交差点の各々をそれぞれのパラメータ座標にしたがって配列し、配列された交差点を用いて複数の結合フィーチャー境界を形成すること、を含む。この方法はさらに、上記結合フィーチャー境界の各々を、結合フィーチャーリストに加え、上記結合フィーチャー境界を形成する各フィーチャーを、上記第一、第二リストから除去すること、を含む。
【００１５】
本開示のさらに他の態様では、第一、第二の重なり合うフィーチャー境界に基づいて結合フィーチャー境界を形成する方法は、上記の重なり合うフィーチャー境界によって形成される交差点の順序付けられたリストを生成し、第一の方向で上記第一フィーチャー境界に沿って延びるとともに上記順序付け交差点リストにおける第一交差点で終端する、上記結合フィーチャー境界の第一部分を形成し、上記第二フィーチャー境界を選択し、上記第一部分に接続される上記結合フィーチャー境界の第二部分を形成すること、を含む。この第二部分は、上記第一方向に上記第二フィーチャー境界に沿って延び上記順序付けられた交差点リストにおける第二交差点で終端する。
【図面の簡単な説明】
【００１６】
【図１】本開示の一実施例における、第一視野を示す。
【図２】本開示の一実施例における、第二視野を示す。
【図３】本開示の一実施例における、第二フィーチャーと重なり合う第一フィーチャーを示す。
【図４】図３の第一フィーチャーおよび第二フィーチャーに対応する複数の点を含む表１を示す。
【図５】図３の第一フィーチャーおよび第二フィーチャーに対応する複数の点を含む表２を示す。
【図６】図３の第一、第二フィーチャーの部分を含む結合フィーチャーを示す。
【図７】本開示の付加的な実施例における、第一フィーチャーと第二フィーチャーとを示す。
【図８】図７の第一、第二フィーチャーの部分を含む結合フィーチャーを示す。
【図９】本開示の実施例方法に対応するフローチャートを示す。
【図９ａ】図９のフローチャートの続きである。
【図１０】本開示の別の実施例における、第一視野を示す。
【図１１】図１０の実施例における、第二視野を示す。
【図１２】図１０の実施例における、結合フィーチャーを示す。
【図１３】本開示の付加的な実施例における、二つの重なり合うフィーチャーを示す。
【図１４】図１３の重なり合うフィーチャーから形成された結合フィーチャーを示す。
【発明を実施するための形態】
【００１７】
製造、組み立て、梱包、検査、監視および／またはその他のさまざまな製造プロセスにおいて、画像化装置および／またはコンピュータ支援描画ソフトウエアを利用して、製造物の一部分の画像を生成しおよび／または取得することができる。このような画像化装置（imaging devices）としては、カメラ、スキャナー、プローブ、輪郭センサおよび／または、測定、計算、検査または検出方法に基づいて物品の画像を取得または生成するように構成された他の装置等を含むが、それに限定されない。例えば、機械加工された部品のさまざまな部分が所望の公差限度の範囲内に収まるか否かを検出する過程を自動化する際に、製造ラインにおいて、上記装置を１つまたは複数利用して、生産された各部品の複数の画像を得ることが出来る。これらの画像は、検査プロセスにおける検査対象部品の１つまたは複数のフィーチャー（feature）を描き出す。本開示において以後一貫して用いられるように、「フィーチャー」という用語は、検査対象物の少なくとも一部において形成され、またはその一部によって形成されたあらゆる形状として定義することが出来る。このようなフィーチャーは、通常、当業者から「輪郭（contour）」と呼ばれる。このようなフィーチャーは、例えば、機械加工され及び／又は他の方法で作られた物品における、表面、角、半径、直径、穴、長さ、幅、高さ、及び／又は他のいかなる部分により、形成されていてもよい。加えて、このようなフィーチャーの画像は、二次元領域に投影することができる。フィーチャーの二次元画像は、通常、当業者から「ブロブ（blob）」と呼ばれている。ここに記す実施例方法を用いて、結合フィーチャー境界を決定し、及び／又は、結合フィーチャーのリストを作成することが出来る。
【００１８】
例えば、ある検査装置において、デジタルカメラを用いて、ある物品、例えばカムシャフトのような物品の一部分の複数の画像を取得し、そのシャフトの機械加工した部分が所望の公差レベル内に収まるか否かを判定することができる。しかし、このような実施例において、デジタルカメラには、このシャフトにおける機械加工されたフィーチャーのすべてを示す、シャフトの単一画像を取得する性能がない場合がある。あるいは、そのカメラによって得られた画像は、上記シャフト全体の合格を決定する臨界公差を有する、機械加工されたフィーチャーのうちの、一部しか表示できないかも知れない。その結果、そのカメラは、異なった視野におけるシャフトの複数の画像を得るように制御されるかも知れない。ある実施例においては、これらの画像が隣接する視野において取得され、少なくとも２つの隣接する画像の視野は重なり合うかも知れない。複数の画像に示された対応するフィーチャーを、ここに記す方法を用いて結合することが出来る。
【００１９】
図１および図２は、異なる、または隣接する視野において撮影されたカメラ画像の例を示す。例えば、図１に示す画像は、第一視野で撮影された機械加工部品の一部分を示し、図２に示す画像は、わずかに異なる、または隣接する視野で撮影された、同一の機械加工部品の一部分を示す。図１および図２に示すように、異なる視野は、１つまたは複数の単純フィーチャー（フィーチャー１〜５の番号を付す）の異なる部分を含んでいてよく、１つの視野が、隣接する視野に全体または一部が示されているフィーチャーの全体または一部を示していてよい。本明細書において、「単純フィーチャー」という用語は、その画像が、分析対象物品の部分の外側境界を表わすようなフィーチャー、と定義される。単純フィーチャーは、本開示において一貫して「フィーチャー」と呼ぶ。後述するように、単純フィーチャーは、その領域（area,面積）の数学符号がマイナスとなるフィーチャー（結合フィーチャー又はその他のフィーチャー）として識別される。
【００２０】
図１０および図１１も、隣接する視野で撮影された、カメラ画像の例を示す。対象フィーチャー（フィーチャー６）の第一部分を図１０に示し、同一フィーチャーの第二部分を、図１１に示す隣接画像に示す。フィーチャー６は、第一および第二の穴フィーチャーＨ１、Ｈ２を含み、穴フィーチャーＨ１の一部が図１０および図１１にそれぞれに示されている。加えて、フィーチャー６の境界と穴Ｈ１の境界は、図１０および図１１にまたがって延びている。本明細書においては、「穴フィーチャー」という言葉は、その画像が、分析対象物品の部分の外側境界内に完全に配置されるようなフィーチャーとして定義される。本開示の実施例においては、穴フィーチャーは単純フィーチャー内に配置することができる。穴フィーチャーは、本開示においては一貫して「穴」と呼ぶ。後述するように穴フィーチャーは、その領域の数学符号がプラスとなるようなフィーチャー（結合フィーチャー又はその他のフィーチャー）として識別される。図１２に示すように、フィーチャー６の隣接する画像同士およびこのフィーチャー６によって画成される穴Ｈ１、Ｈ２の隣接する画像同士を、本明細書に記す方法を用いて結合することが出来る。その結果生成された図１２の結合フィーチャー６は、図１０および図１１に示されたフィーチャーの部分的画像の全体領域を含んでいる。本開示の実施例方法は、結合フィーチャーを形成する際の、フィーチャーの境界及び／又は穴の境界のあらゆる不一致を正確に解消し、公知の画素縫合その他のフィーチャー結合方法の欠陥を避けている。
【００２１】
例えば、本開示のアルゴリズム及び／又は他のコントロールソフトウエアは、重なり合うフィーチャー画像を自動的に特定する。上記ソフトウエアは上記重なり合う画像を結合及び／又は一体化して、結合フィーチャー境界を形成し、また、上記結合フィーチャーの画像を形成及び／又は表示する。このプロセスにおいて、パラメータ座標を用いて、各フィーチャー及びそれによって画成される一切の穴を、それぞれ線セグメントの集合として定義する。これら線セグメントは別個の（distinct）端点（end points）を持っている。本明細書において、「パラメータ座標」とは、二次元または三次元空間における既知の曲線、パスまたは表面上の位置を一義的に表す、単一のパラメータである。曲線に沿った明確な位置は、一義的に一つのパラメータ座標に対応する。さらに、ここで述べるパラメータ座標は、単調関数であり、たとえば、インデックス関数、線形関数、非線形関数、対数関数、指数関数、逆関数、距離ベースのまたは比例の関数であってもよく、これらの関数が、フィーチャー境界に沿って単調に増加または単調に減少しさえすればよい。フィーチャー境界等の曲線上の位置を特定するために、二次元の画素ベースのデカルト座標ではなく、単一のパラメータを用いることによって、このような二次元座標の配列（sorting,整列）および結合に関連した曖昧さという問題が除去される。従って、本明細書で開示されるような結合方法におけるパラメータ座標の使用により、配列プロセスが非常に簡素化され、従来技術の方法に比べてロバスト性（robustness）および信頼性が大幅に向上する。
【００２２】
例えば、画素ベースの結合方法においては、はるかに大きなコンピュータ能力が要求され、しかも、二つの重なり合うフィーチャー画像の画素境界間に位置している交差点のようなフィーチャーの交差点を、同じくらい正確に特定することは出来ない。これらの欠点の一部は、画素ベースの画像に固有の限界に起因する。特に、画素ベースの画像は、画像が取得される特定の視野だけに適用される座標を用いて、有限な解像度（例えば、画像化装置に固有の画素解像度）のフィーチャーを表すことが出来るに過ぎない。第一視野に示されるフィーチャーに当てはまる座標は、画素ごとに見れば、第二の隣接した視野に示される同一のフィーチャーと、必ずしも位置が合っているわけではない。時間のかかる、複雑な、第一視野からの画像と第二視野からの画像の位置合わせが必要となり、さらに、Szeliskiが述べた光の不均一さと視差があることから、先行技術の方法を用いて、フィーチャーの二つの画像を正確に結合することは出来ない。事実、画素ベースの方法を用いて画像を結合する際に生じる寸法の不確かさは、機械加工の誤差と同程度、あるいは上回る場合もあり、信頼性の高い品質管理を困難にしている。
【００２３】
実施例において、本開示の画像化システムは、部分的に重なり合う隣接した視野における検査対象フィーチャーの画素ベースの画像を取得することによって、先行技術の欠点を解消する。そして、この画像化システムは、複数の既知の形状の独立した線セグメントを用いて、各フィーチャーの外周を、計算し及び／又は他の方法で定義する。実施例において、この線セグメントは直線セグメントであってよい。あるいは、この線セグメントは、当該技術分野で公知の他のいかなる形状であってもよい。例えば、曲線、円弧、スプライン等であるが、これに限定されない。このシステムは、まずデカルト座標における各線セグメントの端点を抽出し、それから、パラメータ座標のような単一のパラメータを用いて、その端点を定義する。このシステムは、これら端点を各フィーチャー境界に現れる順序（時計回り方向、反時計回り方向のいずれであっても）に配列（sort）し、これら端点のデカルト座標を用いて、それら線セグメントの交差点を計算する。このシステムはまた、各交差点を計算し、及び／又は各交差点をパラメータ座標に変換する。交差点をパラメータ座標で定義することにより、このシステムは、各交差点を正確かつ一意的に定義することが出来、画素ベースシステムが負う不明瞭性という問題を避けることが出来る。
【００２４】
各交差点のパラメータ座標が決まれば、交差点を登録し、そのパラメータ座標に従って配列することが出来る。そして、システムは交差点毎の交差する２つの線セグメント（ベルトル）のクロス積の符号を決定することによって、結合フィーチャー境界上の交差点からのパスを決定することが出来る。この計算は、例えば、ベクトル幾何学の右手のルールを含んでいてよい。配列された交差点および決定された結合フィーチャーパスを用いて、このシステムは、結合フィーチャーを形成することが出来る。このシステムはまた、各線セグメントの端点のパラメータ座標を単位ベースの実世界のデカルト座標（ミリメートルベースのＸ，Ｙデカルト座標等）に変換する。これらの単位ベースの座標から、ソフトウエアは、結合フィーチャー、ひいては分析対象の物品が、その物品の合格に必要な、所望の公差範囲内に収まるか否かを判断することが出来る。このシステムはまた、結合フィーチャーが単純フィーチャーか穴フィーチャーかを判定することが出来る。このような判定は、問題となる結合フィーチャーの領域（area）の数学符号に基づいて行うことが出来る。このシステムはまた、各結合フィーチャー境界の形成後にひずみ補正処理（distortion correction process）を行ってもよく、1つまたは複数の結合フィーチャーリストを作成してもよい。本開示方法の態様を以下に記し、本開示の実施例のより詳細な考察は、産業上の利用可能性の項に図９および図９ａを参照しながら、記す。
【００２５】
図３は、本開示の実施例による、第一フィーチャー（フィーチャー１）が第二フィーチャー（フィーチャー２）と重なり合う様子を示す。図３に示す実施例においては、２つの交差点(点ＰおよびＱ)でフィーチャー１がフィーチャー２と交差し、フィーチャー１とフィーチャー２の境界が、一連の順次配列された線セグメントによって成り立っている。各線セグメントはそれぞれ別個の（distinct）端点を有する。本開示の実施例方法においては、このようなフィーチャー境界の線セグメントの端点が、図３に矢印で記す時計回りに連結している。このような端点の時計回りの連結について、ここでは例として述べるが、付加的な実施例においては、このような端点は反時計回りに連結されていてもよいことが理解されよう。さらに、フィーチャーをたとえば、連結されるとともに別々の端点を持つ線セグメントの集合として定義するプロセスは、当該技術分野においては公知であることが理解される。したがって、このプロセスについては、ここでは詳述しない。
【００２６】
座標変換
連結されるとともに端点がデカルト座標で定義された線セグメントの集合として表現されたフィーチャー境界から、端点がパラメータ座標で定義された線セグメントを含む境界への変換例を、図３に示すフィーチャー１とフィーチャー２に関して説明することが出来る。初めに、図３に示された各端点をデカルト座標(xi,yi){i=0,1,2,…,N}を用いて表すことが出来、ここで、xiおよびyiは2倍精度（double precision）である。線セグメント上の点は以下の式で表すことが出来る。
｛(１−ｒ)ｘi+ｒｘi+1,(１−ｒ)ｙi＋ｒｙi+1｝(i=０,１,２…N−1；０.０≦ｒ＜１.０)
ここで、iはフィーチャー端点の整数インデックスであり、rは倍精度数（double precision number）である。(ｘ,ｙ)が(ｘi,ｙi)、(ｘi+1,ｙi+1)間のフィーチャー線セグメント上の、端点または交差点のような対象点であるとき、パラメータrは、点(ｘ,ｙ)から点(ｘi,ｙi)までの距離と点(ｘi+1,ｙi+1)から点(ｘi,ｙi)までの距離との比として表すことが出来る。その結果、ｒを等式ｒ＝(ｘ−ｘi)／(ｘi+1−ｘi)または等式ｒ＝(ｙ−ｙi)／(ｙi+1−ｙi)で表すことが出来る。ただし、関係する線セグメントがＸ軸に平行またはＹ軸に平行な場合、ゼロで割るという誤りとなるため、これは避ける必要がある。さらに、ｔ＝i＋ｒとすると、2倍精度の単純な一次元のパラメータ座標P(t)を算出して、フィーチャー上の任意の点を表すことが出来る。ここで、
P(t)={ｘt,ｙt}(０.０≦ｔ＜Ｎ)
パラメータ座標への変換によって、システムは、単一のパラメータ(t)のみを用いて、フィーチャー境界上の任意の点を一義的に定義することが出来る。したがって、フィーチャー境界上の全ての点の配列、検索および連結もまた、単一のパラメータによって行うことが出来る。
【００２７】
逆に、座標ｔの２つパラメータデカルト位置を、初めにtを以下の等式によってiおよびrに変換することによって、計算することが出来る。
ｘt=(１−ｒ)ｘi＋rｘi+1 (i=０,１,２…N−1；０.０≦ｒ＜１.０)および
ｙt=(１−ｒ)ｙi＋rｙi+1 (i=０,１,２…N−1；０.０≦ｒ＜１.０)
このように、パラメータ座標を実世界の単位ベースのデカルト座標に変換することが出来、逆も可能である。ここで述べた方法を、2倍精度またはそれ以上の精度で用いてもよいことが理解されよう。2倍精度は浮動小数点値を表すためのコンピュータナンバリング形式であり、このような形式は当該技術分野で公知であるため、この形式についてはここでは詳述しない。
【００２８】
点の登録（Point Registration）
図９および図９ａに関して、交差点の計算法の例を以下により詳細に述べる。２つの交差するフィーチャー線セグメントの交差点のパラメータ座標が定義されれば、交差点の座標を登録することが出来る。本文中において、「登録」という用語は記録(record)、保存(save)、および／またはその他の方法で、例えばデジタルコンピュータメモリのような記録可能な媒体に保存(store)することを意味する。図４，図５の表１，表２にそれぞれ示すように、交差点を登録することによって、システムは、例えばパラメータ座標、デカルト座標および対応するフィーチャーの識別子等の、点に関する情報を記録することが出来る。表１，表２において、各行は１つの交差点に関するすべての登録情報を示している。
【００２９】
点の配列（Point Sorting）
例えば、表１の列1は実施例フィーチャー＃１上に配置された各交差点のパラメータ座標をリスト表示し、列２は列1の各交差点に関連した、順序指数（順位指数）をリスト表示している。列２の指数は、対応する交差点が実施例フィーチャー＃１の境界に沿って例えば時計回り方向に現れる順番（１番目、２番目、３番目等）に基づいて割り当てられている。同様に、表１の列３は、実施例フィーチャー＃２上に配置された各交差点のパラメータ座標を記し、列４は列３の各交差点に関連し、フィーチャー＃２の境界線に沿う順番に基づいた、順位指数を記している。このように、表１の列２および列４は、それぞれ、列１および列３に記されたパラメータ座標の配列指数（配列指標）を含んでいる。
【００３０】
表２の列１−４は、表１の列１−４に対応している。しかし、表２は、実施例フィーチャー＃１、２が結合して、単一の結合フィーチャーを超える結合フィーチャーを形成するような、より複雑なフィーチャー結合を示している。このような状況においては、ソフトウエアは、一義的なフィーチャー識別子(１、１、２等)を用いて、各交差点が属する結合フィーチャーを定義する。このようなフィーチャー識別子は、各交差点について、表２の列５に記されている。
【００３１】
パラメータ座標を用いることで、ソフトウエアは、２つまたはそれ以上の重なり合うフィーチャー上の対象となる各点を、秩序だった方法で簡単、正確かつ一義的に配列することが出来る。特に、パラメータ座標は、単一のパラメータのみで、フィーチャー境界上の任意の位置を精確に表すだけでなく、当該境界上の点の順番をも精確に表すために用いることが出来る。換言すれば、当該境界上の始点から測定される、結合フィーチャー境界に沿った任意の点までの距離は、そのパラメータ座標の単調増加関数である。このように、結合フィーチャー境界上のすべての点をそのパラメータ座標に従って配列することにより、当該境界上のフィーチャー点の逐次リストが、デカルト座標を用いた方法において障害となる、冗長という問題無しに作成される。
【００３２】
例えば、フィーチャー境界上の２つのデカルト座標点、Ｐ１(Ｘ＝３，Ｙ＝７)とＰ２（Ｘ＝５，Ｙ＝２）を配列すると、２つの異なった配列が可能である。すなわち、Ｐ１Ｐ２（増加するＸ座標に基づく配列）、またはＰ２Ｐ１（増加するＹ座標に基づく配列）である。一方、Ｐ１とＰ２がパラメータ座標を用いて表される点であれば、各ｔ値は、単一の固有のパラメータ座標（Ｐ）を有する単一の固有の位置を与えるのみであろう。
【００３３】
パスの決定
ここで述べるパラメータ座標はまた、交差点の同定、位置づけを行った後、結合フィーチャーがどのパスを辿るか（すなわち、次の点または中間点のうち、どれを結合フィーチャーに含めるのか）を決定するために用いることができる。例えば、図７に示すように、実施例のフィーチャー１および２は複数の交差点（点ＮからＷとして示す）を有している。パスの決定はフィーチャー１および２の境界上で、外方向（outward direction）に行うことが出来、図８に示す結合フィーチャーの境界は各交差点を通過している。実施例においては、ソフトウエアは、この決定を、同定された交差点からの２つの外向きルート(outward routes)を形成する中間点ごとに行う。別の実施例においては、ソフトウエアは、同定された交差点までの２つの内向きルート(inward routes)を形成する、隣接する境界点（中間点）ごとにこの決定を行う。
【００３４】
図７の交差点Ｐを例にとれば、点Ｐへの２つの内向きルートを形成する中間点は、フィーチャー１の点Ａとフィーチャー２の点Ｂである。これらの点は、それぞれ線セグメントＡＰおよび線セグメントＢＰを形成し、時計回り方向に交差点Ｐに入るパスを定める。加えて、点Ｐからの２つの外向きルートを形成する２つの中間点は、フィーチャー２の点Ｃとフィーチャー１の点Ｄである。これらの点は、それぞれ線セグメントＰＣおよび線セグメントＰＤを形成し、交差点Ｐから出る時計回り方向のパスを定める。このように、ソフトウエアは、４つの可能なルート、すなわち、ＡＰＣ、ＡＰＤ、ＢＰＣ，ＢＰＤから、交差点Ｐを通る結合フィーチャーの境界を決定することが出来る。１つの実施例では、時計回り方向に横切るフィーチャー境界について、ベクトル幾何学の右手のルール（別名、クロス積のルール）を用いて、この決定を行うことが出来る。特に、右手のルールに従って、２つの外向きのルート（あるいは、交差点から離れる方向を向くベクトル）を分析する際には、クロス積の数学符号がマイナスの時、つまり、ＰＣ×ＰＤ ＜０（紙面に入るベクトルを形成）の時は、クロス積の左側の線セグメント（線セグメントＰＣ）を、その結果得られる結合フィーチャーに含まれるべきものとして選ぶ。代わりに、クロス積の数学符号がプラスの時、つまり、ＰＣ×ＰＤ ＞０の時は、線セグメントＰＤを、その結果得られる結合フィーチャーに含まれるべきものとして選ぶ。このルートＡＰＣを含む結合フィーチャーを図８に示す。この結合フィーチャーは、時計回りの方向に結合された点によって構成されている。上述のとおり、２つの交差するフィーチャーの境界点は、時計回り方向に結合してもよく、反時計回り方向に結合してもよい。また、ここに述べた方法およびプロセスに従って、ベクトル幾何学の左手のルール（上述の右手のルールに類似）を用いてもよく、交差するフィーチャーが時計回り方向に結合されるか反時計回り方向に結合されるか次第で、同一の結果が得られる。
【００３５】
穴フィーチャー
図１０から図１２に示すように、ある単純フィーチャーの２つの重なり合う画像を結合した時、その結果得られる結合フィーチャーが、１つまたは複数の穴フィーチャーを画成する場合があることも理解されよう。穴は、例えば、撮影された物品の欠陥の輪郭を示す場合がある。あるいは穴は、分析対象物の公差付きの部分及び／又は意味のある部分の輪郭を示す場合もある。これらの穴の外周の点は、親の単純フィーチャーの点とは逆の方向で連結されている。実施例においては、上述の方法を用いて、そうした穴の周囲、境界、および／または形状を定めることが出来る。これらの穴は、１）少なくとも１つの視野において完全に見える穴であってもよいし、２）２つの隣接する視野の対応する縁上に配置された穴であって、結合フィーチャーを形成するために修正する必要のある穴であってもよい。図１１の穴Ｈ２は、この第一のシナリオを表し、図１４の穴Ｈ３、Ｈ４はこの第二のシナリオを表している。穴Ｈ３、Ｈ４は、図１３に示すフィーチャー７とフィーチャー８を結合して形成されたものである。この結合フィーチャーにおける穴の位置および形状は、内向きと外向きのルートの隣接する点に関して上述したのと同一の方法を用いて、決定することが出来る。ある実施例においては、その計算した領域の数学符号がプラスであり、外周のすべての点が単純フィーチャーの点と逆の方向に連結されているという事実によって、穴を同定することが出来る。
【００３６】
２つの交差するフィーチャーを結合して、結合フィーチャー境界を形成した後、結合フィーチャーの一部を、本開示の１つまたは複数の表示装置によって表示してよい。上述の図面には示されていないが、このような表示装置は、例えば、ブラウン管、ＬＣＤディスプレイ、デジタルフラットスクリーンモニタ等の、当該技術分野で公知の画像表示装置であることが理解される。
【００３７】
本開示方法の例が図９および図９ａのフローチャート１００に示されている。他に指定のない限り、図９および図９ａに示された例示的フローチャート１００を、説明の便宜上、図３に示されたフィーチャー１およびフィーチャー２を参照して説明する。上述のとおり、ここで述べる方法は、様々な検査過程で利用でき、特に、製造部品または物品の一部の１つまたは複数の画像が、その製造物品が受容可能な許容レベル内に収まっているか否かの判断の一助として必要となるような検査過程に利用できる。許容レベルは寸法公差と、欠陥の数や大きさといった欠陥検出の許容範囲の両方を含むことが理解される。この技法はまた、分解して模倣したり、フィーチャーの画像から実際にＣＡＤファイルを作成したりするのにも利用出来る。このような画像は、例えば、鋳造、機械加工、製造、組み立て、検査および／または当該技術分野で公知のいかなる製造設備において撮影してもよい。ここに述べる方法および構造を非製造業に適用してもよく、構造、手書き文字、タイプされた文字および／またはその他の画像の、高速および／または自動で認識する必要がある場合に適用してよい。
【００３８】
ここで述べる方法例はまた、２つまたはそれ以上のフィーチャーリストから、単一の結合フィーチャーリストを作成するのに用いてよい。このようなフィーチャーリストは、さまざまなソースから入手できる。ここでは機械加工した部品の一部の繰り返し撮影によって得られたフィーチャーリストについて述べているが、このようなリストは、２つまたはそれ以上の異なる光設定の下で処理された単一の画像から取得してもよく、ＣＡＤファイルまたはその他の非画像ソースから取得してもよい。ここに述べる実施例の各々において、そのようなフィーチャーリストの評価を、反復的、非反復的、リアルタイム、および／またはその他の継続的方法で、追加的フィーチャーリストが取得された時に行う。これにより、各追加的フィーチャーリストが、反復的または非反復的に結合フィーチャーリストに統合され、更新された結合フィーチャーリストが作成される。このような結合フィーチャーリスト作成の一部として、２つまたはそれ以上の重なり合うフィーチャー画像を、ここに述べるプロセスを用いて結合することができる。
【００３９】
結合フィーチャーリスト作成方法の一例において、高速デジタルカメラのような画像化装置を制御して、機械加工した部品の一部の複数の画像が得られるようにする。取得された複数の画像の分析に際して、コントロールソフトウエアは定義、計算および／または他の方法でフィーチャーの第一リストを取得する（ステップ１０２）。それからソフトウエアは、第一リスト中の各フィーチャーおよびそれによって形成される穴の境界を、別々の線セグメントのターム（term）で、定義または計算する。このソフトウエアはまた、第一リスト中のフィーチャーを構成する各線セグメントの端点のパラメータ座標も計算する(ステップ１０４)。図９および図９ａに関する以下の記述は、概してパラメータ座標の使用に関するものであるが、追加的実施例においては、代わりに、単一のパラメータを用いて、二次元または三次元空間における曲線上の位置を一義的に決定する、他のいかなる座標システムを用いてもよい。
【００４０】
上述のとおり、ここに述べる画像は、例えば、複数のカメラ視野またはカメラアングル等の複数の視野から得られたものであってよく、そのような視野は重なり合っていてよい。さらに、本開示方法の実施例において取得されるフィーチャーリストは、例えば画像技術分野で公知のフィーチャーの位置決め方法（feature location methods）を用いて作成してよい。このようなフィーチャーの位置決めは、主としてソフトウエアベースであり、各視野において実行する。これらのフィーチャー位置付け手段は、サブピクセルの分解能を有することが多く、そのことは、ここに述べる実世界の単位ベースの座標法をさらに補完する。さらに別の実施例においては、フィーチャーリストをＣＡＤファイルその他の公知のソースから導入してもよい。
【００４１】
ステップ１０２でフィーチャーの第一リストを取得したら、ソフトウエアは画像化装置を制御して、フィーチャーの第二リストを取得し（ステップ１０６）、ソフトウエアは第二リストの各フィーチャーおよびそれによって形成された穴の境界を、別々の（discreat）線セグメントで定義または計算する。こうして、上でステップ１０２に関して述べたとおり、ソフトウエアは、第一および第二リストの各フィーチャーの境界を線セグメントに分割する。ソフトウエアはまた、第二リストの各フィーチャーおよびそれに関連した穴のそれぞれを構成する線セグメント端点のパラメータ座標を計算する（ステップ１０８）。ステップ１０４と１０８において、システムはまた、各フィーチャーに沿い時計回りまたは反時計回りの方向で出会った位置に従ってパラメータ座標を配列（sort、並べ替え）する。このようなパラメータ座標の配列は、例えば下記の処理に役立つ。すなわち、ステップ１５０において中間点を決定し、ステップ１５４において結合フィーチャー境界の外向きのパスに沿ってすべての部分を加え、及び／又は、各交差点において結合フィーチャーパスの方向を決定する。ある実施例においては、交差点評価の順序（sequence）は、各交差点の配列されたパラメータ座標に基づいて決定してもよい。
【００４２】
本開示の追加的実施例において２つより多い数のフィーチャーリストを取得してもよいことが理解され、結合フィーチャーリストの作成および／またはその他の方法で更新する際に、これら追加的フィーチャーリストのそれぞれを評価してよいことが理解される。１つの実施例においては、第一、第二リストを取得したら、ソフトウエアは、これら２つのフィーチャーリストを統合／およびまたは他の方法で結合し始める。このプロセスにおいては、ソフトウエアは第一リスト中の各フィーチャーを個別に検討して、第二リストの１つまたは複数のフィーチャーと重なっているか否かを決定する。第一リストの第一フィーチャーに関する分析が完了したら、第一リスト中の残りのフィーチャーそれぞれについてこの同じ分析を繰り返し、第一リストの各フィーチャーの、第二リストの各フィーチャーに対する分析を完了する。この分析の結果、ソフトウエアは撮影された部品の各フィーチャーを含む結合フィーチャーリストを作成する。その後、追加的フィーチャーリストが取得され、処理されたら、結合フィーチャーリストを改定および／またはその他の方法で更新する。
【００４３】
一般的に、ステップ１０２で取得された第一リストからの検査対象フィーチャーが、ステップ１０６で取得された第二リストからのいかなるフィーチャーとも重なり合わない場合は、第一リストからの検査対象フィーチャーを結合フィーチャーリストにコピーしてよい。しかし、第一リストからのフィーチャーが第二リストからのフィーチャーの１つまたは複数と重なり合う場合は、２つの重なり合うフィーチャーを結合して、この結合されたフィーチャーを結合フィーチャーリストに追加する。このプロセスを、例えば、２つまたはそれ以上のフィーチャーリストの分析が完了するまで繰り返す。
【００４４】
２つのフィーチャーの境界が重なり合うか否かを判定する際、ソフトウエアは、ステップ１０２で得られたフィーチャーの第一リストのフィーチャーのｘ範囲およびｙ範囲が、ステップ１０６（ステップ１１０）で得られたフィーチャーの第二リスト中におけるフィーチャーの、対応する、最小及び／又は最大のｘ範囲およびｙ範囲に重なり合うか否かを判定する。ステップ１１０で行われるこの判定は、分析対象の２つのフィーチャーが互いに交差する可能性が高いか否かを見るためのテストとして利用することが出来、この判定は、デカルト座標のｘおよびｙの最小値および／または最大値を用いて行ってよい。後述するように、最終的な交差の判定はステップ１３０で行われる。しかし、ステップ１１０で行われる判定はステップ１３０と重複するものではない。なぜなら、ステップ１１０は、重なり合わないフィーチャーを濾過して取り除き、これらを直接結合フィーチャーリストに加える役割を果たすからである。第一リストのいかなるフィーチャーのｘおよびｙの範囲も、対応する第二リストのフィーチャーのｘおよびｙの範囲と重なり合わない場合、ステップ１０２およびステップ１０６で得られたフィーチャーリストのすべてのフィーチャーを用いて、累積結合フィーチャーリストを作成する（ステップ１１２）。図９に示すように、システムはまた、他のフィーチャーリストが存在するか否かを判定する（ステップ１２０）。少なくとも、結合フィーチャーリストに含まれるフィーチャーの一部が、上述した１つまたは複数の表示装置に表示される（ステップ１１４）。
【００４５】
しかし、もし、ステップ１０２で得られた第一フィーチャーリスト中のいずれかのフィーチャーの、いずれかの最大および／または最小のｘおよびｙの範囲が、ステップ１０６で得られた第二フィーチャーリスト中のいずれかのフィーチャーの、対応する最大および／または最小のｘおよびｙの範囲と重なり合うときは、第一フィーチャーリストからフィーチャー（Ｆ１）を選択して、実施例のフィーチャー結合プロセスを行う。加えて、ステップ１０６で得られた第二フィーチャーリストから、第一フィーチャーリストからのフィーチャー（Ｆ１）と重なり合うフィーチャー（Ｆ２）を、分析のために選択する（ステップ１１６）。実施例においては、フィーチャーＦ１、Ｆ２の選択は自動的になされるようにしてもよく、あるいは、本開示の実施例において利用されるフィーチャー結合ソフトウエアによって行ってもよいことが理解される。あるいは、フィーチャー結合プロセスを実施するオペレータが、重なり合うフィーチャーＦ１、Ｆ２を、検査のために手動で選択してもよい。
【００４６】
第一および第二フィーチャーＦ１，Ｆ２の選択後、フィーチャーＦ１上の線セグメント（Ｌ１）およびフィーチャーＦ２上の線セグメント（Ｌ２）もまた選択することが出来る（ステップ１１８）。そして、ソフトウエアはフィーチャーＦ１、Ｆ２が互いに交差するか否かを判定する。図９には示されていないが、このプロセスの一部として、ソフトウエアは、選択した線セグメントＬ１が選択した線セグメントＬ２と平行および／または同一直線上にあるか否かを判定してもよい。線セグメントＬ１、Ｌ２が平行および／または同一直線上にある場合は、ソフトウエアはＬ２上にあるＬ１の端点を登録する。交差点、端点、および／または上述のフィーチャーのその他の部分は、メモリデバイスに登録してよいことが理解される。このメモリデバイスは、例えば、コンピュータやその他の公知のコントローラ、すなわち表示装置、画像化装置および／または本開示のソフトウエアと結合されたコントローラと、結合されている。
【００４７】
選択した線セグメントＬ１が選択した線セグメントＬ２と平行および／または同一直線上には存在しないとソフトウエアが判定すると、ソフトウエアは、フィーチャーＦ１の線セグメントＬ１がフィーチャーＦ２の線セグメントＬ２と交差するか否かを判定する（ステップ１３０）。線セグメントＬ１が線セグメントＬ２と交差しないときは、ソフトウエアは、前回評価したフィーチャーＦ２の線セグメント（Ｌ２）に時計回り方向に隣接する、フィーチャーＦ２の未評価の線セグメント（ＬＮ）が存在するか否かを判定する（ステップ１２６）。この分析は反時計回り方向に行ってもよいことが理解される。このような隣接線セグメントＬＮが、前回評価された線セグメントＬ２から時計回り方向に存在するときは、ソフトウエアは隣接する線セグメントＬＮを新しい線セグメントＬ２として選択し（ステップ１２８）、ソフトウエアはステップ１３０に戻る。ここで新しい線セグメントＬ２はフィーチャーＦ１の選択された線セグメントＬ１に関して評価される。
【００４８】
他方、前回評価された線セグメントＬ２に時計回りに隣接して配置された未評価の線セグメントＬＮが、フィーチャーＦ２にもう存在しない場合には、ソフトウエアは、前回評価されたフィーチャーＦ１の線セグメントＬ１に時計回りに隣接して配置された未評価の線セグメントＬＮがフィーチャーＦ１に存在するか否かを判定する（ステップ１３６）。そのような未評価の線セグメントＬＮがフィーチャーＦ１上に存在していなければ、ソフトウエアはステップ１４４に進む。しかし、そのような線セグメントＬＮがフィーチャーＦ１上に存在している場合には、ソフトウエアは、フィーチャーＦ１上の未評価の線セグメントＬＮを新しい線セグメントＬ１として選択し（ステップ１４０）、そして、ソフトウエアはステップ１３０に戻る。
【００４９】
引き続きステップ１３０を参照すると、フィーチャーＦ１の線セグメントＬ１がフィーチャーＦ２の線セグメントＬ２と交差する場合には、ソフトウエアは線セグメントＬ１，Ｌ２の交差点（Ｐｃ）を計算し、その交差点の座標をパラメータ座標に変換する（ステップ１４２）。図３に関して上述したとおり、フィーチャー１とフィーチャー２の交差点を点ＰおよびＱとして示す。
【００５０】
線セグメントＬ１，Ｌ２の端点のパラメータ座標が決まれば、線セグメントＬ１，Ｌ２の交差点Ｐｃの位置付け及び／又はこの交差点Ｐｃのパラメータ座標の計算のステップは、比較的簡単に行えることが理解されよう。Ｌ１とＬ２が平行でない場合、これら２つの線セグメントの交差点は、まず各線セグメントを標準的な幾何学の線の方程式（Ａ１ｘ+Ｂ１ｙ+Ｃ１＝０およびＡ２ｘ+Ｂ２ｙ+Ｃ２=０）で表すことによって、計算することが出来る。ソフトウエアは各線セグメントの既知の端点を用いて、各線方程式の係数Ａ，Ｂ，Ｃを計算する。このプロセスにより、２組の係数（Ａ１、Ｂ１、Ｃ１およびＡ２、Ｂ２，Ｃ２）が算出される。ソフトウエアはまた、これら２つの線が平行か否かを、以下の方程式によって変数を解くことにより、判定する。
Ｄ＝Ａ１Ｂ２−Ａ２Ｂ１
もしＤがゼロであれば、２つの線セグメントＬ１、Ｌ２は平行であり、Ｄがゼロでなければ、２つの線セグメントは互いに交差する。Ｄがゼロか否かの判定においては、小さなプラスの公差域△（例えば下記式１）をソフトウエアが定義する。
【数１】
Ｄが−△＜Ｄ＜△の条件を満たせば、ソフトウエアはＤがゼロに等しいと判定する。
【００５１】
線セグメントが平行でない（Ｄがゼロと等しくない）とき、それらの線セグメントを含む線は交差するが、線セグメント自体は交差しないことも考えられる。線が交差する点（ｘｃ、ｙｃ）のデカルト座標は、以下の等式を用いて計算することが出来る。
ｘＣ＝（Ｂ２Ｃ１−Ｂ１Ｃ２）／Ｄ
ｙＣ＝（Ａ１Ｃ２−Ａ２Ｃ１）／Ｄ
そして、交差点（ｘｃ、ｙｃ）が線セグメントＬ１、Ｌ２の両方の上に配置されているか否かを判定する必要がある。この判定は、線セグメントＬ１、Ｌ２の両方について、以下の条件式に従って、行うことが出来る。
Ｍｉｎ（ｘ１，ｘ２）≦ｘＣ≦Ｍａｘ（ｘ１，ｘ２）
Ｍｉｎ（ｙ１，ｙ２）≦ｙＣ≦Ｍａｘ（ｙ１，ｙ２）
上記の等式において、（ｘ１，ｘ２）と（ｙ１，ｙ２）は、線セグメントＬ１またはＬ２の２つの端点の座標である。点（ｘｃ、ｙｃ）が上の条件を満たすならば、ソフトウエアは、線セグメントＬ１、Ｌ２が交差点（ｘｃ、ｙｃ）で互いに交差すると結論を下す。そして、ソフトウエアは交差点（ｘｃ、ｙｃ）をパラメータ座標に変換し、交差点のパラメータ座標（Ｐｃ）が表１に示すように、登録される（ステップ１４３）。実施例においては、Ｆ１、Ｆ２の両方に対応する交差点のパラメータ座標が、ステップ１４３において登録される。しかし、上記の条件の１つが満たされない場合は、ソフトウエアは、ステップ１３０において線セグメントＬ１とＬ２は互いに交差しないと結論を下していたであろう。
【００５２】
交差点Ｐｃを登録すると、ソフトウエアはステップ１２６に進み、さらに未評価の線セグメント（Ｌｎ）があれば、その分析を行う。図９ａに示すように、フィーチャーＦ１とフィーチャーＦ２とのすべての交差点Ｐｃの計算が完了したら、ソフトウエアは、任意の所望の順序で交差点を配列する。例えば、ステップ１４４に示すように、すべての登録された交差点Ｐｃは、フィーチャーＦ１に沿って時計回り方向に移動するときに出会う順序に従って、配列することが出来る。このプロセスにおいて、ソフトウエアは、Ｆ１上で出会った順位に従って、各交差点に順序指数を割り当て、これら指数を、それぞれ登録する。同様に、ステップ１４６に示すように、ソフトウエアは、ステップ１４２で計算されたすべての交差点を、フィーチャーＦ２に沿って時計回り方向に移動するときに出会う順序に従って、配列する。このようにしてソフトウエアは、各交差点に順序指数を割り当て、これらの指数を登録する。上述したように、例示的順序指数を表１（図４）の列２および列４に示す。表１に示すように、各交差点Ｐｃは、配列された時、フィーチャーに固有の特異的な順序指数を有する。
【００５３】
図９ａに示すとおり、ソフトウエアはステップ１４７で、評価のために未評価の交差点Ｐｃｎを選択する。例えば、未評価の交差点Ｐｃｎを、ステップ１４３で登録された任意の交差点の中から選ぶことが出来る。実施例においては、ソフトウエアは配列された最初の交差点を選ぶ。ソフトウエアは各交差点に割り当てられたパラメータ座標に基づいて、交差点評価の順序（シーケンス）を決定してよいことが理解される。特に、ソフトウエアは、ステップ１４４または１４６で決定された配列順に基づいて、各交差点を順次評価してよい。
【００５４】
そして、ソフトウエアは、Ｐｃｎと等しい例示的参照点Ｐｒｅｆをセットし（ステップ１４８）、交差点Ｐｃｎから外向きのパス上における次の点および／または中間点Ｐｉを決定する（ステップ１５０）。実施例においては、中間点Ｐｉは選択された交差点Ｐｃｎに隣接する点である。ステップ１５０における中間点Ｐｉの決定により、交差点Ｐｃｎから、例えば時計回り方向に外向きの、結合フィーチャーＦｃの方向が決まる。例えば、図３を参照すると、交差点Ｐの座標が決まると、ソフトウエアは、交差点Ｐを結合フィーチャーＦｃの境界上の点として採取する。そして、ソフトウエアは、交差点Ｐから開始して、点Ｐからの結合フィーチャーＦｃの外向きのパス上の中間点Ｐｉとして、フィーチャー１の点Ａを含めるか、フィーチャー２の点Ｂを含めるかを決定する。点Ａ、Ｂは、交差点Ｐに隣接する線セグメント端点として選択される（ステップ１０４および１０８の線セグメント端点における配列によって決定される）。そして、ソフトウエアはステップ１５１において、交差点Ｐからの外向きのパスを決定する。さらに、図９ａには示されていないが、実施例において、ソフトウエアは、結合フィーチャーＦｃの内向きのパス上の中間点Ｐｉとして、フィーチャー１の点Ｅを含めるか、フィーチャー２の点Ｆを含めるかを決定してもよい。
【００５５】
ステップ１５０において、交差点Ｐｃからの外向きのパス上における中間点Ｐｉを決定するため、ソフトウエアは、例えば、２つのベクトル（ベクトルＰＡとベクトルＰＢ）ののクロス積の、少なくとも符号を計算する。ここで、
【数２】
引き続き図３を参照するが、ここで、仮想ベクトルＺのポイントが−Ｚの方向（すなわち、紙面に入る方向）を示す時、線セグメントＰＡによって定められるパスが、結合フィーチャーＦｃにおける交差点Ｐからの外向きのパスとして、ソフトウエアに選択される。さらに、点Ａが、結合フィーチャーＦｃ上に含むべき、交差点Ｐからの外向きのパス上の中間点Ｐｉとして、選択される。一方、ベクトルＺのポイントが＋Ｚの方向（すなわち、紙面から出る方向）を示す時は、線セグメントＰＢによって定められるパスが、交差点Ｐからの外向きのパスとして選択され、点Ｂが、結合フィーチャーＦｃ上に含むべき、交差点Ｐからの外向きのパス上の中間点Ｐｉとして、選択される。図３に示す実施例においては、上述のベクトルＺのクロス積方程式により、ベクトルＺが+Ｚの方向を示しているため、線セグメントＰＢによって定められたパスが、ソフトウエアによって選択される。
【００５６】
ソフトウエアは、外向きのパスおよび／または結合フィーチャーＦｃの方向を決定するにあたり、上記クロス積のルールに加えて、他の所定の結合ルールをいくつ用いてもよい。例えば、第一、第二のフィーチャーの分析を、時計回り方向ではなく反時計回り方向で行う場合、左手のルールを用いて、既知の交差点からの結合フィーチャーＦｃの外向きのパスを決定することが出来る。加えて、ステップ１５０で行われる決定は、第一フィーチャーの線セグメントが第二フィーチャーの線セグメントと重なり合う、または部分的に重なり合う場合（２つの線セグメントが同一線上で平行な場合）、および、第一フィーチャーの線セグメントが第二フィーチャーの線セグメントと逆の方向である場合には、第一フィーチャーの線セグメントの取消しおよび／または削除を含んでいてもよい。別の実施例においては、ステップ１５０においてソフトウエアは、計算された各交差点Ｐｃを、結合フィーチャーＦｃ上にある別の交差点と結合することが出来るか否かを判定してもよい。連続的な結合フィーチャーを形成するように連結できない交差点があれば、これらの交差点を削除して、結合フィーチャーの形成には使用しない。
【００５７】
追加的実施例においては、重なり合うフィーチャー境界の交差する線セグメントが平行でも同一直線上にもない場合に、ソフトウエアは、結合フィーチャー境界の決定にあたって、単一のベルトルクロス積（single vector cross product）のみを計算する。このような実施例において、ソフトウエアは、交差点の配列リストから第一交差点を選び取り、上述のように、ベクトルクロス積の符号を用いて、交差点からの外向きのパスを決める。この第一クロス積が計算され、第一交差点からの外向きの結合フィーチャー境界パスが決定されると、ソフトウエアは第二交差点に達するまで、このパスに沿い続ける。配列された第二の交差点への内向きの結合フィーチャー境界パス（すなわち、第一交差点からの外向きのパス）は既知であるので、ソフトウエアは、ただ単に、２つの重なり合うフィーチャーのうちの他方（すなわち、第二交差点への内向きの結合フィーチャー境界パスを定めないフィーチャー）によって定められたパスを選び取ることによって、第二交差点からの外向きのパスを選ぶ。ソフトウエアは、この外向きのパスを、より大きなパラメータ座標値を持つ線セグメント端点の方向または同じ方向（時計回り、または反時計回り）に選び取ってもよい。ソフトウエアは、再び第一交差点に到達するまで、このプロセスを繰り返す。このような実施例においては、システムは第一のクロス積を計算すれば、新たに交差点に出会う度にクロス積を計算する必要はない。この方法は、ソフトウエアが、重なり合うフィーチャー境界の一方の任意の点から開始し、その点が結合フィーチャー境界上にあるか否かが、ソフトウエアで未知であった場合に適用できる。
【００５８】
しかし、その開始点が結合フィーチャー境界上にあることがソフトウエアで既知であった場合は、ソフトウエアは、一切、クロス積を計算する必要はない。このような実施例においては、ソフトウエアは、その代わりに第一フィーチャーを第一方向（時計回り、または反時計回り）に横切り、フィーチャーを切換え、第二フィーチャーに沿って、第一方向に進み続ける。再び第一交差点に到達するまで、このプロセスを繰り返す。上述のとおり、この簡略化したプロセスは、重なり合うフィーチャー境界の交差する線セグメントが平行でも同一直線上にもない場合に、用いられる。
【００５９】
図９ａに示すとおり、ステップ１５２において、ソフトウエアは、ステップ１５１で決定された外向きのパス上にある、次の交差点(Ｐｎ+１）を決定する。この決定をするために、ソフトウエアは、ステップ１４４とステップ１４６に関して上述した、パラメータ座標の配列指数を用いる。例えば、表１に示すパラメータ座標の配列指数は、フィーチャー＃１またはフィーチャー＃２によって定められた外向きのパス上の次の交差点Ｐｎ+１を位置づけ及び／又は決定するために用いることが出来る。最初の交差点Ｐｃｎと外向きのパスが決定されたため、システムは、交差点Ｐｃｎと、交差点Ｐｃｎと次の交差点Ｐｎ+１との間の外向きのパス上に含まれる各線セグメントおよび対応する各線セグメント端点を、順番に、結合フィーチャーＦｃの境界に加える（ステップ１５４）。
【００６０】
そして、ソフトウエアは、次の交差点Ｐｎ+１がステップ１４８で選択した参照点Ｐｒｅｆと等しいか否かを決定する（ステップ１５６）。次の交差点Ｐｎ+１が参照点Ｐｒｅｆと異なるとき、システムは次の交差点Ｐｎ+１を新しい未評価の交差点Ｐｃｎとして選択し（ステップ１５８）、その決定をした後、ステップ１５０に進む。一方、次の交差点Ｐｎ+１がステップ１４８でセットされた参照点Ｐｒｅｆと同一であるとシステムが判定したときは、システムは、新しい結合フィーチャーＦｃが作成され、この結合フィーチャーＦｃの境界上のすべての点が記述（評価）されたと結論を下す。このような結論を下すに当たり、ソフトウエアは、結合フィーチャーＦｃのすべての登録された交差点に、固有のフィーチャー識別子を付ける（ステップ１６０）。結合フィーチャーＦｃ上のすべての交差点は、表２の列５に示す識別子から分かるように、同一の識別子を与えられる。このような識別子は、例えば、種類としてはアルファベットや数字であり、結合フィーチャー同士の識別に有用である。
【００６１】
ステップ１６０の一部として、点の群（グループ）が閉じたフィーチャーを形成しているか（すなわち、当該群の先頭の交差点が最後尾の交差点とつながっているか）を判定するために、点の各群の有効性を検証することが出来る。点の集合が先頭から最後尾まで（または最後尾から先頭まで）連結出来なかった場合、その集合は有効なフィーチャーを構成していない。点の集合が有効なフィーチャーを構成している場合には、そのフィーチャーの点の全体の結合方向をさらに検討すれば、そのフィーチャーが単純フィーチャーであるか穴であるかが判明する。この検討については、以下にさらに詳しく述べる。上述のフィーチャー結合法の結果、有効な結合フィーチャーの境界は、それ自体交差することなく、また他の有効なフィーチャーと交差することもない、閉じたパスである。
【００６２】
ソフトウエアが、有効な結合フィーチャーＦｃが形成されるとともに、結合フィーチャー境界沿いのすべての交差点に適切にフィーチャー識別子が付けられたと判定を下し、システムは、結合フィーチャーＦｃの境界の少なくとも一部を、単位ベースの実世界の座標に変換する（ステップ１６２）。実施例においてシステムは、結合フィーチャーＦｃの境界上に位置する交差点および線セグメントの少なくとも一部を、実世界の座標に変換する。上述のとおり、実世界の座標は、例えば、ミリメートル、インチ等のいかなる公知の長さの単位であってもよく、2倍精度以上の精度を有してもよい。
【００６３】
そして、システムは、実世界の座標を用いて、分析対象の物品が所望の公差範囲内にあるか否かを判定する（ステップ１６４）。上述のとおり、ここに開示する方法は、製造中または生産の物品を検査するために用いてよく、また、公差範囲外および／または他の理由で許容できない物品を却下する助けとなる。ステップ１６６に示すように、分析対象の物品が所定の公差範囲内にはないとき、システムは、オペレータ、中央プロセッサ、その他のコントローラに、分析対象の物品を却下する信号を送る。このような信号により、当該物品は、さらなる分析または機械加工を受けるべく、ラインから外される。物品が公差範囲内であれば、却下信号が送られた場合であっても、システムは結合フィーチャーＦｃが単純フィーチャーであるか否か、または穴フィーチャーであるか否かを判定する（ステップ１６８）。２つのフィーチャーが２つの交差点Ｐｃでのみ互いに交差するとき、結果として得られる結合フィーチャーＦｃは、単純フィーチャーでしかないであろう。しかし、２つのフィーチャーが２つより多い数の交差点Ｐｃで互いに交差するとき、結果として得られる結合フィーチャーＦｃは、その中にもう１つの穴フィーチャーを含んだ、単純フィーチャーである可能性がある。上述したように、穴フィーチャーは、結合フィーチャーの領域（area）の数学符号をチェックすることによって、発見出来る。この計算は、ステップ１６８の一部として行ってよい。
【００６４】
実施例においては、各結合フィーチャーの領域Ａを、以下の数式を用いて計算することが出来る。
【数３】
ここで、（Ｘｉ，Ｙｉ）はフィーチャー上のｉ番目の点の座標であり、ｉはフィーチャーの中の点の指数である。この指数はまた、結合フィーチャー上の点の連結順序（linking sequence）を示す。上記の等式によって計算された領域Ａの数式符号（プラスまたはマイナス）は、フィーチャー上の点が時計回りに結合されているか、反時計回りに結合されているか、に関する信頼性の高い指標を与える。上記の等式によって計算された結合フィーチャーの領域Ａの数式符号がマイナスであれば、対応するフィーチャーの点は時計回りに連結されている、すなわち、結合フィーチャーは単純フィーチャーである。上記の等式によって計算された結合フィーチャーの領域Ａの数式符号がプラスであれば、対応するフィーチャーの点は反時計回りに連結されている、すなわち、結合フィーチャーは確かに穴である。このように、ソフトウエアは、フィーチャーが単純フィーチャーであるか、穴であるかを、単純な計算によって、自動的に判定することが出来る。
【００６５】
穴フィーチャーが結合フィーチャーＦｃの内部にあるか否かを判定するために、穴フィーチャーの任意の点から、無限まで直線的な射線を引くことが出来る。この線が結合フィーチャーＦｃと奇数回交差するならば、穴フィーチャーはフィーチャーＦｃ内に存在する。この線が結合フィーチャーＦｃと偶数回交差するときは、穴フィーチャーはフィーチャーＦｃ内には存在しない。ソフトウエアはまた、単純フィーチャーが穴フィーチャー内に存在するか否かを、同じ方法を用いて判定することが出来る。さらに、単純フィーチャー内の穴フィーチャーの存在を判定するに当たって、ソフトウエアは親である単純フィーチャーおよび子である穴フィーチャーに、公知の任意の用語を用いて、ラベルを付してよい。この親／子決定および、対応する関係のラベル付けは、ステップ１７０で行う。
【００６６】
ステップ１７０の後、または、ソフトウエアが結合フィーチャーＦｃは穴ではないと判断した場合には、ソフトウエアは結合フィーチャーＦｃを結合フィーチャーリストに加える（ステップ１７２）。このような結合フィーチャーリストは、ステップ１１２に関して前述した。さらに、２つの例示的フィーチャー（Ｆ１およびＦ２）の結合の結果、複数の結合フィーチャーＦｃが生成されてもよいことが理解される。したがって、ステップ１７２において、完全で有効な結合フィーチャーＦｃが結合フィーチャーリストに加えられたとしても、その結合フィーチャー上に配置されていない付加的な交差点がステップ１４２で計算され、ステップ１４３で登録されている場合がある。このような付加的な交差点は、例えば、結合フィーチャーＦｃによって形成された１つまたは複数の穴に配置されているかも知れない。したがって、システムは、ステップ１４３で登録されたすべての交差点が評価されたか否かを判定する（ステップ１７４）。登録された交差点でまだ評価されていないものがあれば、システムは未評価の交差点の１つを新しい交差点Ｐｃｎとして選択し、ステップ１４８に戻る。このステップ１４８において、参照点Ｐｒｅｆが再びセットされる（ステップ１７６）。
【００６７】
しかし、もし、すべての登録された交差点が評価済みであれば、ソフトウエアはフィーチャーＦ１をフィーチャーの第一リストから削除し、またフィーチャーＦ２をフィーチャーの第二リストから削除する（ステップ１７８）。そして、ソフトウエアは、結合フィーチャーＦｃがステップ１０２で得られた第一リスト、またはステップ１０６（ステップ１８０）で得られた第二リストのフィーチャーと重なり合うか否かを判定する。この判定を行うために、ソフトウエアはステップ１１０に関して前述したのと類似のプロセスを採用してよい。ソフトウエアは、結合フィーチャーＦｃが第一、第二リストのいかなるフィーチャーにも重なり合っていないと判定した場合には、ステップ１１０に進む（ステップ１８４）。ステップ１１０に戻った時、ソフトウエアは、第一リストのフィーチャーと第二リストのフィーチャーで重なり合うものがあるか否かの判定を続ける。他方、ソフトウエアは、結合フィーチャーＦｃが第一リストまたは第二リストのフィーチャーと重なり合うと判定した場合には、結合フィーチャーＦｃを新しいフィーチャーＦ１として選択し、問題となっている重なり合うフィーチャーを新しいフィーチャーＦ２として選択する（ステップ１８２）。そして、ソフトウエアはステップ１１８に進み、交差判定のために、各フィーチャーの線セグメントを選択する。
【００６８】
本開示の実施例方法は、一般的に、図３に示すフィーチャー１，２（２つの点においてのみ交差する）に関して述べてきたが、同じ方法を、例えば図７に示す別の例示的フィーチャー１，２のような、多数の交差点において互いに交差する２つのフィーチャーに適用出来ることが理解される。また、システムは、上述のプロセスのいかなる時点においても、結合フィーチャーＦｃの外周上の点を、パラメータ座標から、実世界の単位ベースの座標に変換してよいことが理解される。ステップ１６２に関して述べたように、システムは、これら実世界の単位ベースの座標を用いて、結合フィーチャーおよび／または検査対象部品の寸法が所定の公差範囲内にあるか否かを判定することができる。システムは、この判定に基づいて、検査対象部品を却下（reject）することができる。
【００６９】
本明細書を検討することにより、当業者には、他の実施例が明白になるであろう。例えば、追加的実施例において、公知のフィルタリング技術または点を減らす技術（point reduction techniques）を利用して、フィーチャー画像を滑らかにし、および／またはフィーチャー画像中に含まれる点の数を減らすことが考えられる。本明細書および実施例は例示的なものに過ぎず、本発明の真の範囲は以下のクレームによって示される。
【技術分野】
【０００１】
本発明は画像処理に用いられる機器および方法に関し、特に、複数の視野から得られた画像のフィーチャーの結合に用いられる機器および方法に関する。
【背景技術】
【０００２】
産業上の利用可能性
自動生産ラインにおいて、生産中の部品やその他の物の検査を助けるために、画像化技術（imaging technology）がしばしば用いられる。このような生産ラインで一般的に用いられる画像化技術としては、例えば、ビデオ画像、デジタル写真および／または他の公知のプロセスがある。通常、公知の画像化技術は、このような製品の画像をある視野内で取得するために用いられ、各画像が多数の幾何学的輪郭を含んでいることがある。このような輪郭は、例えば製造物の、機械加工した表面、穴、角、および／または他の公差の厳しい部分である。これらの公知技術においては、対象領域を示す画像を取得し、この画像に基づいて、撮影された領域の様相がこの製造物にとって許容範囲内に収まるか否かを判断する。例えば、このような画像化技術は、高速製造ラインにおいて、生産中の部品やその他の物を検査し、公差範囲を外れたり及び又は許容不可能な部品を却下（reject、排除）するための助けとして用いられる。
【０００３】
しかし、画像化の一部の適用例において、対象領域が画像化装置の視野よりも大きい場合がある。例えば、上記の製造物を検査及び／又は調査するために用いられるデジタルカメラ等の画像化装置は、視野が比較的小さいことがあり、この視野が、製造物の機械加工された表面全体の画像を捕捉するには小さ過ぎる場合がある。このような適用例においては、対象領域は一つの視野の境界を越えて、他の視野にまで延びることがある。
【０００４】
公知の画像化装置に関連した視野の限界を補うため、あるいは２つの隣接した画像の境界を越えて対象領域の位置決めを行うために、画像化装置は通常、検査対象物の複数の画像を複数の視野から捕えて、その後、デジタル結合ソフトウエア等の手段を用いて、画像の対応する部分または重なり合う部分（overlapping portions）を結合する。異なる視野の画像を結合するこの過程は、「画像縫合」と呼ばれることがある。しかし、公知の縫合技術を用いて異なる視野からの画像を結合する際に、かなりの不正確さが導入されかねない。加えて、このような方法は通常、コンピュータ及び／又はプロセッサの大容量の処理能力または速度を必要とし、運用の観点から極めて煩わしいものになりかねない。
【０００５】
例えば、先行技術のシステムによって得られた画像は通常、「二値」の画素ベースの画像である。このような画像は、オンまたはオフのスクリーン画素の集合によって構成される。先行技術のシステムにおいては、検査対象領域の複数の画素ベースの画像を取得し、そして、その領域全体を確実に捕らえるために、画像ごとに視野を重ね合わせる。例えば、対象領域の最初の画像を取得後、このようなシステムは第二の（隣接する）画像を取得する。このとき、この第二の画像の視野は、第一の画像の視野と重なり合っている。そして、第一の画像と第二の画像を、画素ごとに併合または「縫合」する。
【０００６】
しかし、現実世界では機械加工部品の各輪郭は明確な境界を有しているが、先行技術のシステムによって取得された、輪郭の第一の画素ベースの画像は、同じ輪郭の第二の（隣接する）画素ベースの画像とは、境界の寸法または形状が若干異なる場合がある。例えば、第一の輪郭画像において「オン」であった画素が第二の輪郭画像では「オフ」になることがある。このような２つの隣接する画像間における同一の輪郭の画素のばらつきは、数々の要因に起因し得る。これら要因としては、カメラの微小な回動、画素サイズの不完全な較正、不均一な照明および陰影の効果を含むが、これに限定されない。これら要因は、二値画像の一部の画素を、一方の画像ではオンにさせ、他方の画像ではオフにさせる。輪郭の結合画像を形成する際、先行技術の縫合方法は通常、整列（alignment）および補間（interpolation）の技術によって、２つの画像の対応する画素を結合させ、これらの不正確さを隠している。
【０００７】
残念ながら、公知の縫合法は時間がかかり、しかも、保存および分析に大量のコンピュータメモリを必要とする、潜在的に重い画像を作り出す。公知の縫合法に固有の不正確さは、その結果生成される結合画像が後で他の画像との比較分析に用いられる場合、雪だるま式にその影響が増大する可能性がある。公知の画像結合方法における画素ごとのばらつき、および厄介なメモリ条件は、製造ラインの効率を劇的に低下させかねず、一人以上のオペレータによる監視が必要となる場合がある。このような欠陥は、多くの高速製造環境においては、非常に高コストになりかねない。
【０００８】
２００６年１２月に、『コンピュータ・グラフィックスとコンピュータ・ビジョンの基礎と傾向』の２（１）で発表された「画像の位置合わせおよび縫合」という論文の中で、Szeliskiは従来の方法に関連した更なる問題、すなわち完全自動縫合の信頼性の欠如等について考察した。Szeliskiは、大きな外れ値を許容しつつ、同時に偽のフィーチャーのマッチングや繰り返しパターンのマッチングを避けることは難しいと、指摘した。もう一つ、よくある問題としてSzeliskiが記したのは、「視差」である。視差とは、二つの異なる視線に沿って見たときの、対象物の、見かけ上の変位または向きの違いである。Szeliskiが考察した縫合の欠点は、自動工業検査で用いられる既存の結合方法の正確性、信頼性および速度を、大きく制限するものである。Szeliskiは視差による画像のゆがみの修正に用いられる技法についても教示しているが、これらの修正技法は、ほとんどの高精度測定工程には適していない。
【０００９】
Vaidyanathan等に付与された米国特許第５，３７１，８１０号は、外周の点をＸ、Ｙのデカルト座標と８ビットの方向コード値を用いて登録する方法を開示している。Vaidyanathanはまた、外周の点の間の結合、接続関係を決定するために用いられる配列方法（sorting method、整列方法）も開示している。しかし、Vaidyanathanの外周の点を配列する方法は、複雑な画像結合の適用例においては、機能しない。なぜなら、閉じたフィーチャーの外周の二次元のＸ，Ｙ座標は、両方とも単調ではあり得ないからである。加えて、Vaidyanathanの方法は、同一のＸまたはＹ座標値を有する２つ以上の外周の点が含まれるという特別な状況にある場合には、すべての外周の点を配列することが出来ない。加えて、Vaidyanathanの方法の精密さは、画素の解像度に限定される。なぜなら、ここで教示されている方法および最終結果が、画素ベースだからである。
【００１０】
Beallに付与された米国特許第４，４９３，１０５号は、Vaidyanathan等の特許と類似の、点の配列方法を開示している。Beallの方法も、閉じたフィーチャーの外周の二次元のＸ，Ｙ座標が同時に単調にはなり得ないため、機能しない。Beallの方法もまた、方法とその最終結果が画素ベースであるため、画素の解像度に限定される。Beallでは、フィーチャーの結合については言及していないが、Beallで開示された方法は、いずれも単純な結合の事例しか扱っていない。Beallの方法は、複雑な結合状況、すなわち２つのフィーチャーが重なり合い、または２箇所以上で交差し、これにより複数の結合フィーチャーパス（combined feature paths）が作り出されるような状況では機能しない。加えて、VaidyanathanもBeallも、「単純な」フィーチャーと「穴」フィーチャーとを自動的に区別する方法については教示していない。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
したがって、本開示は、一つの視野よりも大きい二つ以上の画像またはフィーチャーを結合する際に遭遇する問題の解消を目的としている。本開示はまた、二つ以上のフィーチャーリストの結合に関連した困難の解消を目的としている。
【課題を解決するための手段】
【００１２】
本開示の一態様において、重なり合う第一、第二のフィーチャーの境界に基づいて結合フィーチャー境界を形成する方法は、第一、第二の重なり合うフィーチャーの境界を公知の形状の線セグメントに分け、上記２つのフィーチャーの線セグメントによって形成された交差点を同定し、上記交差点のパラメータ座標を計算し、上記パラメータ座標に基づいて交差点評価の順序を決定すること、を含む。この方法はさらに、上記決定された順序における第一交差点を形成する線セグメントに基づき、第一クロス積を演算し、この第一クロス積の数学符号にしたがって結合フィーチャー境界の第一パスを選択すること、を含む。この第一パスは第一交差点から上記決定された順序での第二交差点へと延びている。上記方法はさらに、上記順序での第二交差点を形成する線セグメントに基づき第二クロス積を演算し、この第二クロス積の数学符号にしたがって、第二交差点から延びる結合フィーチャー境界の第二パスを選択すること、を含む。上記結合フィーチャー境界は、上記第一、第二の交差点と、上記第一、第二パスを定める、上記第一、第二のフィーチャー境界のうちの少なくとも一つの、部分を含む。
【００１３】
本開示の態様では、第一、第二の重なり合うフィーチャーの境界に基づいて結合フィーチャー境界を形成する方法は、上記第一、第二のフィーチャー境界の交差によって形成される複数の交差点のパラメータ座標を演算し、上記複数の交差点を、それらのパラメータ座標にもとづいて配列順序に組織化し、各交差点での交差によって形成されたクロス積の数学符号を決定し、上記数学符号に基づいて複数の交差点の各々間での結合フィーチャー境界のパスを決定すること、を含む。この態様では、上記結合フィーチャー境界は、上記配列順序にしたがって配された複数の交差点の各々と、第一、第二のフィーチャー境界のうちの少なくとも１つの、部分を含む。この方法はさらに、上記結合フィーチャー境界によって画成された領域（area，面積）を演算し、上記演算された領域の数学符号に基づいてこの結合フィーチャー境界に関するフィーチャタイプを決定すること、を含む。
【００１４】
本開示のさらに他の態様では、結合フィーチャーリストを作る方法は、フィーチャーの第一、第二のリストを取得し、上記第二リストのフィーチャーの境界と重なる上記第一リストのフィーチャーの境界によって形成される、複数の交差点を同定し、上記の同定された交差点の各々のパラメータ座標を演算し、上記交差点の各々をそれぞれのパラメータ座標にしたがって配列し、配列された交差点を用いて複数の結合フィーチャー境界を形成すること、を含む。この方法はさらに、上記結合フィーチャー境界の各々を、結合フィーチャーリストに加え、上記結合フィーチャー境界を形成する各フィーチャーを、上記第一、第二リストから除去すること、を含む。
【００１５】
本開示のさらに他の態様では、第一、第二の重なり合うフィーチャー境界に基づいて結合フィーチャー境界を形成する方法は、上記の重なり合うフィーチャー境界によって形成される交差点の順序付けられたリストを生成し、第一の方向で上記第一フィーチャー境界に沿って延びるとともに上記順序付け交差点リストにおける第一交差点で終端する、上記結合フィーチャー境界の第一部分を形成し、上記第二フィーチャー境界を選択し、上記第一部分に接続される上記結合フィーチャー境界の第二部分を形成すること、を含む。この第二部分は、上記第一方向に上記第二フィーチャー境界に沿って延び上記順序付けられた交差点リストにおける第二交差点で終端する。
【図面の簡単な説明】
【００１６】
【図１】本開示の一実施例における、第一視野を示す。
【図２】本開示の一実施例における、第二視野を示す。
【図３】本開示の一実施例における、第二フィーチャーと重なり合う第一フィーチャーを示す。
【図４】図３の第一フィーチャーおよび第二フィーチャーに対応する複数の点を含む表１を示す。
【図５】図３の第一フィーチャーおよび第二フィーチャーに対応する複数の点を含む表２を示す。
【図６】図３の第一、第二フィーチャーの部分を含む結合フィーチャーを示す。
【図７】本開示の付加的な実施例における、第一フィーチャーと第二フィーチャーとを示す。
【図８】図７の第一、第二フィーチャーの部分を含む結合フィーチャーを示す。
【図９】本開示の実施例方法に対応するフローチャートを示す。
【図９ａ】図９のフローチャートの続きである。
【図１０】本開示の別の実施例における、第一視野を示す。
【図１１】図１０の実施例における、第二視野を示す。
【図１２】図１０の実施例における、結合フィーチャーを示す。
【図１３】本開示の付加的な実施例における、二つの重なり合うフィーチャーを示す。
【図１４】図１３の重なり合うフィーチャーから形成された結合フィーチャーを示す。
【発明を実施するための形態】
【００１７】
製造、組み立て、梱包、検査、監視および／またはその他のさまざまな製造プロセスにおいて、画像化装置および／またはコンピュータ支援描画ソフトウエアを利用して、製造物の一部分の画像を生成しおよび／または取得することができる。このような画像化装置（imaging devices）としては、カメラ、スキャナー、プローブ、輪郭センサおよび／または、測定、計算、検査または検出方法に基づいて物品の画像を取得または生成するように構成された他の装置等を含むが、それに限定されない。例えば、機械加工された部品のさまざまな部分が所望の公差限度の範囲内に収まるか否かを検出する過程を自動化する際に、製造ラインにおいて、上記装置を１つまたは複数利用して、生産された各部品の複数の画像を得ることが出来る。これらの画像は、検査プロセスにおける検査対象部品の１つまたは複数のフィーチャー（feature）を描き出す。本開示において以後一貫して用いられるように、「フィーチャー」という用語は、検査対象物の少なくとも一部において形成され、またはその一部によって形成されたあらゆる形状として定義することが出来る。このようなフィーチャーは、通常、当業者から「輪郭（contour）」と呼ばれる。このようなフィーチャーは、例えば、機械加工され及び／又は他の方法で作られた物品における、表面、角、半径、直径、穴、長さ、幅、高さ、及び／又は他のいかなる部分により、形成されていてもよい。加えて、このようなフィーチャーの画像は、二次元領域に投影することができる。フィーチャーの二次元画像は、通常、当業者から「ブロブ（blob）」と呼ばれている。ここに記す実施例方法を用いて、結合フィーチャー境界を決定し、及び／又は、結合フィーチャーのリストを作成することが出来る。
【００１８】
例えば、ある検査装置において、デジタルカメラを用いて、ある物品、例えばカムシャフトのような物品の一部分の複数の画像を取得し、そのシャフトの機械加工した部分が所望の公差レベル内に収まるか否かを判定することができる。しかし、このような実施例において、デジタルカメラには、このシャフトにおける機械加工されたフィーチャーのすべてを示す、シャフトの単一画像を取得する性能がない場合がある。あるいは、そのカメラによって得られた画像は、上記シャフト全体の合格を決定する臨界公差を有する、機械加工されたフィーチャーのうちの、一部しか表示できないかも知れない。その結果、そのカメラは、異なった視野におけるシャフトの複数の画像を得るように制御されるかも知れない。ある実施例においては、これらの画像が隣接する視野において取得され、少なくとも２つの隣接する画像の視野は重なり合うかも知れない。複数の画像に示された対応するフィーチャーを、ここに記す方法を用いて結合することが出来る。
【００１９】
図１および図２は、異なる、または隣接する視野において撮影されたカメラ画像の例を示す。例えば、図１に示す画像は、第一視野で撮影された機械加工部品の一部分を示し、図２に示す画像は、わずかに異なる、または隣接する視野で撮影された、同一の機械加工部品の一部分を示す。図１および図２に示すように、異なる視野は、１つまたは複数の単純フィーチャー（フィーチャー１〜５の番号を付す）の異なる部分を含んでいてよく、１つの視野が、隣接する視野に全体または一部が示されているフィーチャーの全体または一部を示していてよい。本明細書において、「単純フィーチャー」という用語は、その画像が、分析対象物品の部分の外側境界を表わすようなフィーチャー、と定義される。単純フィーチャーは、本開示において一貫して「フィーチャー」と呼ぶ。後述するように、単純フィーチャーは、その領域（area,面積）の数学符号がマイナスとなるフィーチャー（結合フィーチャー又はその他のフィーチャー）として識別される。
【００２０】
図１０および図１１も、隣接する視野で撮影された、カメラ画像の例を示す。対象フィーチャー（フィーチャー６）の第一部分を図１０に示し、同一フィーチャーの第二部分を、図１１に示す隣接画像に示す。フィーチャー６は、第一および第二の穴フィーチャーＨ１、Ｈ２を含み、穴フィーチャーＨ１の一部が図１０および図１１にそれぞれに示されている。加えて、フィーチャー６の境界と穴Ｈ１の境界は、図１０および図１１にまたがって延びている。本明細書においては、「穴フィーチャー」という言葉は、その画像が、分析対象物品の部分の外側境界内に完全に配置されるようなフィーチャーとして定義される。本開示の実施例においては、穴フィーチャーは単純フィーチャー内に配置することができる。穴フィーチャーは、本開示においては一貫して「穴」と呼ぶ。後述するように穴フィーチャーは、その領域の数学符号がプラスとなるようなフィーチャー（結合フィーチャー又はその他のフィーチャー）として識別される。図１２に示すように、フィーチャー６の隣接する画像同士およびこのフィーチャー６によって画成される穴Ｈ１、Ｈ２の隣接する画像同士を、本明細書に記す方法を用いて結合することが出来る。その結果生成された図１２の結合フィーチャー６は、図１０および図１１に示されたフィーチャーの部分的画像の全体領域を含んでいる。本開示の実施例方法は、結合フィーチャーを形成する際の、フィーチャーの境界及び／又は穴の境界のあらゆる不一致を正確に解消し、公知の画素縫合その他のフィーチャー結合方法の欠陥を避けている。
【００２１】
例えば、本開示のアルゴリズム及び／又は他のコントロールソフトウエアは、重なり合うフィーチャー画像を自動的に特定する。上記ソフトウエアは上記重なり合う画像を結合及び／又は一体化して、結合フィーチャー境界を形成し、また、上記結合フィーチャーの画像を形成及び／又は表示する。このプロセスにおいて、パラメータ座標を用いて、各フィーチャー及びそれによって画成される一切の穴を、それぞれ線セグメントの集合として定義する。これら線セグメントは別個の（distinct）端点（end points）を持っている。本明細書において、「パラメータ座標」とは、二次元または三次元空間における既知の曲線、パスまたは表面上の位置を一義的に表す、単一のパラメータである。曲線に沿った明確な位置は、一義的に一つのパラメータ座標に対応する。さらに、ここで述べるパラメータ座標は、単調関数であり、たとえば、インデックス関数、線形関数、非線形関数、対数関数、指数関数、逆関数、距離ベースのまたは比例の関数であってもよく、これらの関数が、フィーチャー境界に沿って単調に増加または単調に減少しさえすればよい。フィーチャー境界等の曲線上の位置を特定するために、二次元の画素ベースのデカルト座標ではなく、単一のパラメータを用いることによって、このような二次元座標の配列（sorting,整列）および結合に関連した曖昧さという問題が除去される。従って、本明細書で開示されるような結合方法におけるパラメータ座標の使用により、配列プロセスが非常に簡素化され、従来技術の方法に比べてロバスト性（robustness）および信頼性が大幅に向上する。
【００２２】
例えば、画素ベースの結合方法においては、はるかに大きなコンピュータ能力が要求され、しかも、二つの重なり合うフィーチャー画像の画素境界間に位置している交差点のようなフィーチャーの交差点を、同じくらい正確に特定することは出来ない。これらの欠点の一部は、画素ベースの画像に固有の限界に起因する。特に、画素ベースの画像は、画像が取得される特定の視野だけに適用される座標を用いて、有限な解像度（例えば、画像化装置に固有の画素解像度）のフィーチャーを表すことが出来るに過ぎない。第一視野に示されるフィーチャーに当てはまる座標は、画素ごとに見れば、第二の隣接した視野に示される同一のフィーチャーと、必ずしも位置が合っているわけではない。時間のかかる、複雑な、第一視野からの画像と第二視野からの画像の位置合わせが必要となり、さらに、Szeliskiが述べた光の不均一さと視差があることから、先行技術の方法を用いて、フィーチャーの二つの画像を正確に結合することは出来ない。事実、画素ベースの方法を用いて画像を結合する際に生じる寸法の不確かさは、機械加工の誤差と同程度、あるいは上回る場合もあり、信頼性の高い品質管理を困難にしている。
【００２３】
実施例において、本開示の画像化システムは、部分的に重なり合う隣接した視野における検査対象フィーチャーの画素ベースの画像を取得することによって、先行技術の欠点を解消する。そして、この画像化システムは、複数の既知の形状の独立した線セグメントを用いて、各フィーチャーの外周を、計算し及び／又は他の方法で定義する。実施例において、この線セグメントは直線セグメントであってよい。あるいは、この線セグメントは、当該技術分野で公知の他のいかなる形状であってもよい。例えば、曲線、円弧、スプライン等であるが、これに限定されない。このシステムは、まずデカルト座標における各線セグメントの端点を抽出し、それから、パラメータ座標のような単一のパラメータを用いて、その端点を定義する。このシステムは、これら端点を各フィーチャー境界に現れる順序（時計回り方向、反時計回り方向のいずれであっても）に配列（sort）し、これら端点のデカルト座標を用いて、それら線セグメントの交差点を計算する。このシステムはまた、各交差点を計算し、及び／又は各交差点をパラメータ座標に変換する。交差点をパラメータ座標で定義することにより、このシステムは、各交差点を正確かつ一意的に定義することが出来、画素ベースシステムが負う不明瞭性という問題を避けることが出来る。
【００２４】
各交差点のパラメータ座標が決まれば、交差点を登録し、そのパラメータ座標に従って配列することが出来る。そして、システムは交差点毎の交差する２つの線セグメント（ベルトル）のクロス積の符号を決定することによって、結合フィーチャー境界上の交差点からのパスを決定することが出来る。この計算は、例えば、ベクトル幾何学の右手のルールを含んでいてよい。配列された交差点および決定された結合フィーチャーパスを用いて、このシステムは、結合フィーチャーを形成することが出来る。このシステムはまた、各線セグメントの端点のパラメータ座標を単位ベースの実世界のデカルト座標（ミリメートルベースのＸ，Ｙデカルト座標等）に変換する。これらの単位ベースの座標から、ソフトウエアは、結合フィーチャー、ひいては分析対象の物品が、その物品の合格に必要な、所望の公差範囲内に収まるか否かを判断することが出来る。このシステムはまた、結合フィーチャーが単純フィーチャーか穴フィーチャーかを判定することが出来る。このような判定は、問題となる結合フィーチャーの領域（area）の数学符号に基づいて行うことが出来る。このシステムはまた、各結合フィーチャー境界の形成後にひずみ補正処理（distortion correction process）を行ってもよく、1つまたは複数の結合フィーチャーリストを作成してもよい。本開示方法の態様を以下に記し、本開示の実施例のより詳細な考察は、産業上の利用可能性の項に図９および図９ａを参照しながら、記す。
【００２５】
図３は、本開示の実施例による、第一フィーチャー（フィーチャー１）が第二フィーチャー（フィーチャー２）と重なり合う様子を示す。図３に示す実施例においては、２つの交差点(点ＰおよびＱ)でフィーチャー１がフィーチャー２と交差し、フィーチャー１とフィーチャー２の境界が、一連の順次配列された線セグメントによって成り立っている。各線セグメントはそれぞれ別個の（distinct）端点を有する。本開示の実施例方法においては、このようなフィーチャー境界の線セグメントの端点が、図３に矢印で記す時計回りに連結している。このような端点の時計回りの連結について、ここでは例として述べるが、付加的な実施例においては、このような端点は反時計回りに連結されていてもよいことが理解されよう。さらに、フィーチャーをたとえば、連結されるとともに別々の端点を持つ線セグメントの集合として定義するプロセスは、当該技術分野においては公知であることが理解される。したがって、このプロセスについては、ここでは詳述しない。
【００２６】
座標変換
連結されるとともに端点がデカルト座標で定義された線セグメントの集合として表現されたフィーチャー境界から、端点がパラメータ座標で定義された線セグメントを含む境界への変換例を、図３に示すフィーチャー１とフィーチャー２に関して説明することが出来る。初めに、図３に示された各端点をデカルト座標(xi,yi){i=0,1,2,…,N}を用いて表すことが出来、ここで、xiおよびyiは2倍精度（double precision）である。線セグメント上の点は以下の式で表すことが出来る。
｛(１−ｒ)ｘi+ｒｘi+1,(１−ｒ)ｙi＋ｒｙi+1｝(i=０,１,２…N−1；０.０≦ｒ＜１.０)
ここで、iはフィーチャー端点の整数インデックスであり、rは倍精度数（double precision number）である。(ｘ,ｙ)が(ｘi,ｙi)、(ｘi+1,ｙi+1)間のフィーチャー線セグメント上の、端点または交差点のような対象点であるとき、パラメータrは、点(ｘ,ｙ)から点(ｘi,ｙi)までの距離と点(ｘi+1,ｙi+1)から点(ｘi,ｙi)までの距離との比として表すことが出来る。その結果、ｒを等式ｒ＝(ｘ−ｘi)／(ｘi+1−ｘi)または等式ｒ＝(ｙ−ｙi)／(ｙi+1−ｙi)で表すことが出来る。ただし、関係する線セグメントがＸ軸に平行またはＹ軸に平行な場合、ゼロで割るという誤りとなるため、これは避ける必要がある。さらに、ｔ＝i＋ｒとすると、2倍精度の単純な一次元のパラメータ座標P(t)を算出して、フィーチャー上の任意の点を表すことが出来る。ここで、
P(t)={ｘt,ｙt}(０.０≦ｔ＜Ｎ)
パラメータ座標への変換によって、システムは、単一のパラメータ(t)のみを用いて、フィーチャー境界上の任意の点を一義的に定義することが出来る。したがって、フィーチャー境界上の全ての点の配列、検索および連結もまた、単一のパラメータによって行うことが出来る。
【００２７】
逆に、座標ｔの２つパラメータデカルト位置を、初めにtを以下の等式によってiおよびrに変換することによって、計算することが出来る。
ｘt=(１−ｒ)ｘi＋rｘi+1 (i=０,１,２…N−1；０.０≦ｒ＜１.０)および
ｙt=(１−ｒ)ｙi＋rｙi+1 (i=０,１,２…N−1；０.０≦ｒ＜１.０)
このように、パラメータ座標を実世界の単位ベースのデカルト座標に変換することが出来、逆も可能である。ここで述べた方法を、2倍精度またはそれ以上の精度で用いてもよいことが理解されよう。2倍精度は浮動小数点値を表すためのコンピュータナンバリング形式であり、このような形式は当該技術分野で公知であるため、この形式についてはここでは詳述しない。
【００２８】
点の登録（Point Registration）
図９および図９ａに関して、交差点の計算法の例を以下により詳細に述べる。２つの交差するフィーチャー線セグメントの交差点のパラメータ座標が定義されれば、交差点の座標を登録することが出来る。本文中において、「登録」という用語は記録(record)、保存(save)、および／またはその他の方法で、例えばデジタルコンピュータメモリのような記録可能な媒体に保存(store)することを意味する。図４，図５の表１，表２にそれぞれ示すように、交差点を登録することによって、システムは、例えばパラメータ座標、デカルト座標および対応するフィーチャーの識別子等の、点に関する情報を記録することが出来る。表１，表２において、各行は１つの交差点に関するすべての登録情報を示している。
【００２９】
点の配列（Point Sorting）
例えば、表１の列1は実施例フィーチャー＃１上に配置された各交差点のパラメータ座標をリスト表示し、列２は列1の各交差点に関連した、順序指数（順位指数）をリスト表示している。列２の指数は、対応する交差点が実施例フィーチャー＃１の境界に沿って例えば時計回り方向に現れる順番（１番目、２番目、３番目等）に基づいて割り当てられている。同様に、表１の列３は、実施例フィーチャー＃２上に配置された各交差点のパラメータ座標を記し、列４は列３の各交差点に関連し、フィーチャー＃２の境界線に沿う順番に基づいた、順位指数を記している。このように、表１の列２および列４は、それぞれ、列１および列３に記されたパラメータ座標の配列指数（配列指標）を含んでいる。
【００３０】
表２の列１−４は、表１の列１−４に対応している。しかし、表２は、実施例フィーチャー＃１、２が結合して、単一の結合フィーチャーを超える結合フィーチャーを形成するような、より複雑なフィーチャー結合を示している。このような状況においては、ソフトウエアは、一義的なフィーチャー識別子(１、１、２等)を用いて、各交差点が属する結合フィーチャーを定義する。このようなフィーチャー識別子は、各交差点について、表２の列５に記されている。
【００３１】
パラメータ座標を用いることで、ソフトウエアは、２つまたはそれ以上の重なり合うフィーチャー上の対象となる各点を、秩序だった方法で簡単、正確かつ一義的に配列することが出来る。特に、パラメータ座標は、単一のパラメータのみで、フィーチャー境界上の任意の位置を精確に表すだけでなく、当該境界上の点の順番をも精確に表すために用いることが出来る。換言すれば、当該境界上の始点から測定される、結合フィーチャー境界に沿った任意の点までの距離は、そのパラメータ座標の単調増加関数である。このように、結合フィーチャー境界上のすべての点をそのパラメータ座標に従って配列することにより、当該境界上のフィーチャー点の逐次リストが、デカルト座標を用いた方法において障害となる、冗長という問題無しに作成される。
【００３２】
例えば、フィーチャー境界上の２つのデカルト座標点、Ｐ１(Ｘ＝３，Ｙ＝７)とＰ２（Ｘ＝５，Ｙ＝２）を配列すると、２つの異なった配列が可能である。すなわち、Ｐ１Ｐ２（増加するＸ座標に基づく配列）、またはＰ２Ｐ１（増加するＹ座標に基づく配列）である。一方、Ｐ１とＰ２がパラメータ座標を用いて表される点であれば、各ｔ値は、単一の固有のパラメータ座標（Ｐ）を有する単一の固有の位置を与えるのみであろう。
【００３３】
パスの決定
ここで述べるパラメータ座標はまた、交差点の同定、位置づけを行った後、結合フィーチャーがどのパスを辿るか（すなわち、次の点または中間点のうち、どれを結合フィーチャーに含めるのか）を決定するために用いることができる。例えば、図７に示すように、実施例のフィーチャー１および２は複数の交差点（点ＮからＷとして示す）を有している。パスの決定はフィーチャー１および２の境界上で、外方向（outward direction）に行うことが出来、図８に示す結合フィーチャーの境界は各交差点を通過している。実施例においては、ソフトウエアは、この決定を、同定された交差点からの２つの外向きルート(outward routes)を形成する中間点ごとに行う。別の実施例においては、ソフトウエアは、同定された交差点までの２つの内向きルート(inward routes)を形成する、隣接する境界点（中間点）ごとにこの決定を行う。
【００３４】
図７の交差点Ｐを例にとれば、点Ｐへの２つの内向きルートを形成する中間点は、フィーチャー１の点Ａとフィーチャー２の点Ｂである。これらの点は、それぞれ線セグメントＡＰおよび線セグメントＢＰを形成し、時計回り方向に交差点Ｐに入るパスを定める。加えて、点Ｐからの２つの外向きルートを形成する２つの中間点は、フィーチャー２の点Ｃとフィーチャー１の点Ｄである。これらの点は、それぞれ線セグメントＰＣおよび線セグメントＰＤを形成し、交差点Ｐから出る時計回り方向のパスを定める。このように、ソフトウエアは、４つの可能なルート、すなわち、ＡＰＣ、ＡＰＤ、ＢＰＣ，ＢＰＤから、交差点Ｐを通る結合フィーチャーの境界を決定することが出来る。１つの実施例では、時計回り方向に横切るフィーチャー境界について、ベクトル幾何学の右手のルール（別名、クロス積のルール）を用いて、この決定を行うことが出来る。特に、右手のルールに従って、２つの外向きのルート（あるいは、交差点から離れる方向を向くベクトル）を分析する際には、クロス積の数学符号がマイナスの時、つまり、ＰＣ×ＰＤ ＜０（紙面に入るベクトルを形成）の時は、クロス積の左側の線セグメント（線セグメントＰＣ）を、その結果得られる結合フィーチャーに含まれるべきものとして選ぶ。代わりに、クロス積の数学符号がプラスの時、つまり、ＰＣ×ＰＤ ＞０の時は、線セグメントＰＤを、その結果得られる結合フィーチャーに含まれるべきものとして選ぶ。このルートＡＰＣを含む結合フィーチャーを図８に示す。この結合フィーチャーは、時計回りの方向に結合された点によって構成されている。上述のとおり、２つの交差するフィーチャーの境界点は、時計回り方向に結合してもよく、反時計回り方向に結合してもよい。また、ここに述べた方法およびプロセスに従って、ベクトル幾何学の左手のルール（上述の右手のルールに類似）を用いてもよく、交差するフィーチャーが時計回り方向に結合されるか反時計回り方向に結合されるか次第で、同一の結果が得られる。
【００３５】
穴フィーチャー
図１０から図１２に示すように、ある単純フィーチャーの２つの重なり合う画像を結合した時、その結果得られる結合フィーチャーが、１つまたは複数の穴フィーチャーを画成する場合があることも理解されよう。穴は、例えば、撮影された物品の欠陥の輪郭を示す場合がある。あるいは穴は、分析対象物の公差付きの部分及び／又は意味のある部分の輪郭を示す場合もある。これらの穴の外周の点は、親の単純フィーチャーの点とは逆の方向で連結されている。実施例においては、上述の方法を用いて、そうした穴の周囲、境界、および／または形状を定めることが出来る。これらの穴は、１）少なくとも１つの視野において完全に見える穴であってもよいし、２）２つの隣接する視野の対応する縁上に配置された穴であって、結合フィーチャーを形成するために修正する必要のある穴であってもよい。図１１の穴Ｈ２は、この第一のシナリオを表し、図１４の穴Ｈ３、Ｈ４はこの第二のシナリオを表している。穴Ｈ３、Ｈ４は、図１３に示すフィーチャー７とフィーチャー８を結合して形成されたものである。この結合フィーチャーにおける穴の位置および形状は、内向きと外向きのルートの隣接する点に関して上述したのと同一の方法を用いて、決定することが出来る。ある実施例においては、その計算した領域の数学符号がプラスであり、外周のすべての点が単純フィーチャーの点と逆の方向に連結されているという事実によって、穴を同定することが出来る。
【００３６】
２つの交差するフィーチャーを結合して、結合フィーチャー境界を形成した後、結合フィーチャーの一部を、本開示の１つまたは複数の表示装置によって表示してよい。上述の図面には示されていないが、このような表示装置は、例えば、ブラウン管、ＬＣＤディスプレイ、デジタルフラットスクリーンモニタ等の、当該技術分野で公知の画像表示装置であることが理解される。
【００３７】
本開示方法の例が図９および図９ａのフローチャート１００に示されている。他に指定のない限り、図９および図９ａに示された例示的フローチャート１００を、説明の便宜上、図３に示されたフィーチャー１およびフィーチャー２を参照して説明する。上述のとおり、ここで述べる方法は、様々な検査過程で利用でき、特に、製造部品または物品の一部の１つまたは複数の画像が、その製造物品が受容可能な許容レベル内に収まっているか否かの判断の一助として必要となるような検査過程に利用できる。許容レベルは寸法公差と、欠陥の数や大きさといった欠陥検出の許容範囲の両方を含むことが理解される。この技法はまた、分解して模倣したり、フィーチャーの画像から実際にＣＡＤファイルを作成したりするのにも利用出来る。このような画像は、例えば、鋳造、機械加工、製造、組み立て、検査および／または当該技術分野で公知のいかなる製造設備において撮影してもよい。ここに述べる方法および構造を非製造業に適用してもよく、構造、手書き文字、タイプされた文字および／またはその他の画像の、高速および／または自動で認識する必要がある場合に適用してよい。
【００３８】
ここで述べる方法例はまた、２つまたはそれ以上のフィーチャーリストから、単一の結合フィーチャーリストを作成するのに用いてよい。このようなフィーチャーリストは、さまざまなソースから入手できる。ここでは機械加工した部品の一部の繰り返し撮影によって得られたフィーチャーリストについて述べているが、このようなリストは、２つまたはそれ以上の異なる光設定の下で処理された単一の画像から取得してもよく、ＣＡＤファイルまたはその他の非画像ソースから取得してもよい。ここに述べる実施例の各々において、そのようなフィーチャーリストの評価を、反復的、非反復的、リアルタイム、および／またはその他の継続的方法で、追加的フィーチャーリストが取得された時に行う。これにより、各追加的フィーチャーリストが、反復的または非反復的に結合フィーチャーリストに統合され、更新された結合フィーチャーリストが作成される。このような結合フィーチャーリスト作成の一部として、２つまたはそれ以上の重なり合うフィーチャー画像を、ここに述べるプロセスを用いて結合することができる。
【００３９】
結合フィーチャーリスト作成方法の一例において、高速デジタルカメラのような画像化装置を制御して、機械加工した部品の一部の複数の画像が得られるようにする。取得された複数の画像の分析に際して、コントロールソフトウエアは定義、計算および／または他の方法でフィーチャーの第一リストを取得する（ステップ１０２）。それからソフトウエアは、第一リスト中の各フィーチャーおよびそれによって形成される穴の境界を、別々の線セグメントのターム（term）で、定義または計算する。このソフトウエアはまた、第一リスト中のフィーチャーを構成する各線セグメントの端点のパラメータ座標も計算する(ステップ１０４)。図９および図９ａに関する以下の記述は、概してパラメータ座標の使用に関するものであるが、追加的実施例においては、代わりに、単一のパラメータを用いて、二次元または三次元空間における曲線上の位置を一義的に決定する、他のいかなる座標システムを用いてもよい。
【００４０】
上述のとおり、ここに述べる画像は、例えば、複数のカメラ視野またはカメラアングル等の複数の視野から得られたものであってよく、そのような視野は重なり合っていてよい。さらに、本開示方法の実施例において取得されるフィーチャーリストは、例えば画像技術分野で公知のフィーチャーの位置決め方法（feature location methods）を用いて作成してよい。このようなフィーチャーの位置決めは、主としてソフトウエアベースであり、各視野において実行する。これらのフィーチャー位置付け手段は、サブピクセルの分解能を有することが多く、そのことは、ここに述べる実世界の単位ベースの座標法をさらに補完する。さらに別の実施例においては、フィーチャーリストをＣＡＤファイルその他の公知のソースから導入してもよい。
【００４１】
ステップ１０２でフィーチャーの第一リストを取得したら、ソフトウエアは画像化装置を制御して、フィーチャーの第二リストを取得し（ステップ１０６）、ソフトウエアは第二リストの各フィーチャーおよびそれによって形成された穴の境界を、別々の（discreat）線セグメントで定義または計算する。こうして、上でステップ１０２に関して述べたとおり、ソフトウエアは、第一および第二リストの各フィーチャーの境界を線セグメントに分割する。ソフトウエアはまた、第二リストの各フィーチャーおよびそれに関連した穴のそれぞれを構成する線セグメント端点のパラメータ座標を計算する（ステップ１０８）。ステップ１０４と１０８において、システムはまた、各フィーチャーに沿い時計回りまたは反時計回りの方向で出会った位置に従ってパラメータ座標を配列（sort、並べ替え）する。このようなパラメータ座標の配列は、例えば下記の処理に役立つ。すなわち、ステップ１５０において中間点を決定し、ステップ１５４において結合フィーチャー境界の外向きのパスに沿ってすべての部分を加え、及び／又は、各交差点において結合フィーチャーパスの方向を決定する。ある実施例においては、交差点評価の順序（sequence）は、各交差点の配列されたパラメータ座標に基づいて決定してもよい。
【００４２】
本開示の追加的実施例において２つより多い数のフィーチャーリストを取得してもよいことが理解され、結合フィーチャーリストの作成および／またはその他の方法で更新する際に、これら追加的フィーチャーリストのそれぞれを評価してよいことが理解される。１つの実施例においては、第一、第二リストを取得したら、ソフトウエアは、これら２つのフィーチャーリストを統合／およびまたは他の方法で結合し始める。このプロセスにおいては、ソフトウエアは第一リスト中の各フィーチャーを個別に検討して、第二リストの１つまたは複数のフィーチャーと重なっているか否かを決定する。第一リストの第一フィーチャーに関する分析が完了したら、第一リスト中の残りのフィーチャーそれぞれについてこの同じ分析を繰り返し、第一リストの各フィーチャーの、第二リストの各フィーチャーに対する分析を完了する。この分析の結果、ソフトウエアは撮影された部品の各フィーチャーを含む結合フィーチャーリストを作成する。その後、追加的フィーチャーリストが取得され、処理されたら、結合フィーチャーリストを改定および／またはその他の方法で更新する。
【００４３】
一般的に、ステップ１０２で取得された第一リストからの検査対象フィーチャーが、ステップ１０６で取得された第二リストからのいかなるフィーチャーとも重なり合わない場合は、第一リストからの検査対象フィーチャーを結合フィーチャーリストにコピーしてよい。しかし、第一リストからのフィーチャーが第二リストからのフィーチャーの１つまたは複数と重なり合う場合は、２つの重なり合うフィーチャーを結合して、この結合されたフィーチャーを結合フィーチャーリストに追加する。このプロセスを、例えば、２つまたはそれ以上のフィーチャーリストの分析が完了するまで繰り返す。
【００４４】
２つのフィーチャーの境界が重なり合うか否かを判定する際、ソフトウエアは、ステップ１０２で得られたフィーチャーの第一リストのフィーチャーのｘ範囲およびｙ範囲が、ステップ１０６（ステップ１１０）で得られたフィーチャーの第二リスト中におけるフィーチャーの、対応する、最小及び／又は最大のｘ範囲およびｙ範囲に重なり合うか否かを判定する。ステップ１１０で行われるこの判定は、分析対象の２つのフィーチャーが互いに交差する可能性が高いか否かを見るためのテストとして利用することが出来、この判定は、デカルト座標のｘおよびｙの最小値および／または最大値を用いて行ってよい。後述するように、最終的な交差の判定はステップ１３０で行われる。しかし、ステップ１１０で行われる判定はステップ１３０と重複するものではない。なぜなら、ステップ１１０は、重なり合わないフィーチャーを濾過して取り除き、これらを直接結合フィーチャーリストに加える役割を果たすからである。第一リストのいかなるフィーチャーのｘおよびｙの範囲も、対応する第二リストのフィーチャーのｘおよびｙの範囲と重なり合わない場合、ステップ１０２およびステップ１０６で得られたフィーチャーリストのすべてのフィーチャーを用いて、累積結合フィーチャーリストを作成する（ステップ１１２）。図９に示すように、システムはまた、他のフィーチャーリストが存在するか否かを判定する（ステップ１２０）。少なくとも、結合フィーチャーリストに含まれるフィーチャーの一部が、上述した１つまたは複数の表示装置に表示される（ステップ１１４）。
【００４５】
しかし、もし、ステップ１０２で得られた第一フィーチャーリスト中のいずれかのフィーチャーの、いずれかの最大および／または最小のｘおよびｙの範囲が、ステップ１０６で得られた第二フィーチャーリスト中のいずれかのフィーチャーの、対応する最大および／または最小のｘおよびｙの範囲と重なり合うときは、第一フィーチャーリストからフィーチャー（Ｆ１）を選択して、実施例のフィーチャー結合プロセスを行う。加えて、ステップ１０６で得られた第二フィーチャーリストから、第一フィーチャーリストからのフィーチャー（Ｆ１）と重なり合うフィーチャー（Ｆ２）を、分析のために選択する（ステップ１１６）。実施例においては、フィーチャーＦ１、Ｆ２の選択は自動的になされるようにしてもよく、あるいは、本開示の実施例において利用されるフィーチャー結合ソフトウエアによって行ってもよいことが理解される。あるいは、フィーチャー結合プロセスを実施するオペレータが、重なり合うフィーチャーＦ１、Ｆ２を、検査のために手動で選択してもよい。
【００４６】
第一および第二フィーチャーＦ１，Ｆ２の選択後、フィーチャーＦ１上の線セグメント（Ｌ１）およびフィーチャーＦ２上の線セグメント（Ｌ２）もまた選択することが出来る（ステップ１１８）。そして、ソフトウエアはフィーチャーＦ１、Ｆ２が互いに交差するか否かを判定する。図９には示されていないが、このプロセスの一部として、ソフトウエアは、選択した線セグメントＬ１が選択した線セグメントＬ２と平行および／または同一直線上にあるか否かを判定してもよい。線セグメントＬ１、Ｌ２が平行および／または同一直線上にある場合は、ソフトウエアはＬ２上にあるＬ１の端点を登録する。交差点、端点、および／または上述のフィーチャーのその他の部分は、メモリデバイスに登録してよいことが理解される。このメモリデバイスは、例えば、コンピュータやその他の公知のコントローラ、すなわち表示装置、画像化装置および／または本開示のソフトウエアと結合されたコントローラと、結合されている。
【００４７】
選択した線セグメントＬ１が選択した線セグメントＬ２と平行および／または同一直線上には存在しないとソフトウエアが判定すると、ソフトウエアは、フィーチャーＦ１の線セグメントＬ１がフィーチャーＦ２の線セグメントＬ２と交差するか否かを判定する（ステップ１３０）。線セグメントＬ１が線セグメントＬ２と交差しないときは、ソフトウエアは、前回評価したフィーチャーＦ２の線セグメント（Ｌ２）に時計回り方向に隣接する、フィーチャーＦ２の未評価の線セグメント（ＬＮ）が存在するか否かを判定する（ステップ１２６）。この分析は反時計回り方向に行ってもよいことが理解される。このような隣接線セグメントＬＮが、前回評価された線セグメントＬ２から時計回り方向に存在するときは、ソフトウエアは隣接する線セグメントＬＮを新しい線セグメントＬ２として選択し（ステップ１２８）、ソフトウエアはステップ１３０に戻る。ここで新しい線セグメントＬ２はフィーチャーＦ１の選択された線セグメントＬ１に関して評価される。
【００４８】
他方、前回評価された線セグメントＬ２に時計回りに隣接して配置された未評価の線セグメントＬＮが、フィーチャーＦ２にもう存在しない場合には、ソフトウエアは、前回評価されたフィーチャーＦ１の線セグメントＬ１に時計回りに隣接して配置された未評価の線セグメントＬＮがフィーチャーＦ１に存在するか否かを判定する（ステップ１３６）。そのような未評価の線セグメントＬＮがフィーチャーＦ１上に存在していなければ、ソフトウエアはステップ１４４に進む。しかし、そのような線セグメントＬＮがフィーチャーＦ１上に存在している場合には、ソフトウエアは、フィーチャーＦ１上の未評価の線セグメントＬＮを新しい線セグメントＬ１として選択し（ステップ１４０）、そして、ソフトウエアはステップ１３０に戻る。
【００４９】
引き続きステップ１３０を参照すると、フィーチャーＦ１の線セグメントＬ１がフィーチャーＦ２の線セグメントＬ２と交差する場合には、ソフトウエアは線セグメントＬ１，Ｌ２の交差点（Ｐｃ）を計算し、その交差点の座標をパラメータ座標に変換する（ステップ１４２）。図３に関して上述したとおり、フィーチャー１とフィーチャー２の交差点を点ＰおよびＱとして示す。
【００５０】
線セグメントＬ１，Ｌ２の端点のパラメータ座標が決まれば、線セグメントＬ１，Ｌ２の交差点Ｐｃの位置付け及び／又はこの交差点Ｐｃのパラメータ座標の計算のステップは、比較的簡単に行えることが理解されよう。Ｌ１とＬ２が平行でない場合、これら２つの線セグメントの交差点は、まず各線セグメントを標準的な幾何学の線の方程式（Ａ１ｘ+Ｂ１ｙ+Ｃ１＝０およびＡ２ｘ+Ｂ２ｙ+Ｃ２=０）で表すことによって、計算することが出来る。ソフトウエアは各線セグメントの既知の端点を用いて、各線方程式の係数Ａ，Ｂ，Ｃを計算する。このプロセスにより、２組の係数（Ａ１、Ｂ１、Ｃ１およびＡ２、Ｂ２，Ｃ２）が算出される。ソフトウエアはまた、これら２つの線が平行か否かを、以下の方程式によって変数を解くことにより、判定する。
Ｄ＝Ａ１Ｂ２−Ａ２Ｂ１
もしＤがゼロであれば、２つの線セグメントＬ１、Ｌ２は平行であり、Ｄがゼロでなければ、２つの線セグメントは互いに交差する。Ｄがゼロか否かの判定においては、小さなプラスの公差域△（例えば下記式１）をソフトウエアが定義する。
【数１】
Ｄが−△＜Ｄ＜△の条件を満たせば、ソフトウエアはＤがゼロに等しいと判定する。
【００５１】
線セグメントが平行でない（Ｄがゼロと等しくない）とき、それらの線セグメントを含む線は交差するが、線セグメント自体は交差しないことも考えられる。線が交差する点（ｘｃ、ｙｃ）のデカルト座標は、以下の等式を用いて計算することが出来る。
ｘＣ＝（Ｂ２Ｃ１−Ｂ１Ｃ２）／Ｄ
ｙＣ＝（Ａ１Ｃ２−Ａ２Ｃ１）／Ｄ
そして、交差点（ｘｃ、ｙｃ）が線セグメントＬ１、Ｌ２の両方の上に配置されているか否かを判定する必要がある。この判定は、線セグメントＬ１、Ｌ２の両方について、以下の条件式に従って、行うことが出来る。
Ｍｉｎ（ｘ１，ｘ２）≦ｘＣ≦Ｍａｘ（ｘ１，ｘ２）
Ｍｉｎ（ｙ１，ｙ２）≦ｙＣ≦Ｍａｘ（ｙ１，ｙ２）
上記の等式において、（ｘ１，ｘ２）と（ｙ１，ｙ２）は、線セグメントＬ１またはＬ２の２つの端点の座標である。点（ｘｃ、ｙｃ）が上の条件を満たすならば、ソフトウエアは、線セグメントＬ１、Ｌ２が交差点（ｘｃ、ｙｃ）で互いに交差すると結論を下す。そして、ソフトウエアは交差点（ｘｃ、ｙｃ）をパラメータ座標に変換し、交差点のパラメータ座標（Ｐｃ）が表１に示すように、登録される（ステップ１４３）。実施例においては、Ｆ１、Ｆ２の両方に対応する交差点のパラメータ座標が、ステップ１４３において登録される。しかし、上記の条件の１つが満たされない場合は、ソフトウエアは、ステップ１３０において線セグメントＬ１とＬ２は互いに交差しないと結論を下していたであろう。
【００５２】
交差点Ｐｃを登録すると、ソフトウエアはステップ１２６に進み、さらに未評価の線セグメント（Ｌｎ）があれば、その分析を行う。図９ａに示すように、フィーチャーＦ１とフィーチャーＦ２とのすべての交差点Ｐｃの計算が完了したら、ソフトウエアは、任意の所望の順序で交差点を配列する。例えば、ステップ１４４に示すように、すべての登録された交差点Ｐｃは、フィーチャーＦ１に沿って時計回り方向に移動するときに出会う順序に従って、配列することが出来る。このプロセスにおいて、ソフトウエアは、Ｆ１上で出会った順位に従って、各交差点に順序指数を割り当て、これら指数を、それぞれ登録する。同様に、ステップ１４６に示すように、ソフトウエアは、ステップ１４２で計算されたすべての交差点を、フィーチャーＦ２に沿って時計回り方向に移動するときに出会う順序に従って、配列する。このようにしてソフトウエアは、各交差点に順序指数を割り当て、これらの指数を登録する。上述したように、例示的順序指数を表１（図４）の列２および列４に示す。表１に示すように、各交差点Ｐｃは、配列された時、フィーチャーに固有の特異的な順序指数を有する。
【００５３】
図９ａに示すとおり、ソフトウエアはステップ１４７で、評価のために未評価の交差点Ｐｃｎを選択する。例えば、未評価の交差点Ｐｃｎを、ステップ１４３で登録された任意の交差点の中から選ぶことが出来る。実施例においては、ソフトウエアは配列された最初の交差点を選ぶ。ソフトウエアは各交差点に割り当てられたパラメータ座標に基づいて、交差点評価の順序（シーケンス）を決定してよいことが理解される。特に、ソフトウエアは、ステップ１４４または１４６で決定された配列順に基づいて、各交差点を順次評価してよい。
【００５４】
そして、ソフトウエアは、Ｐｃｎと等しい例示的参照点Ｐｒｅｆをセットし（ステップ１４８）、交差点Ｐｃｎから外向きのパス上における次の点および／または中間点Ｐｉを決定する（ステップ１５０）。実施例においては、中間点Ｐｉは選択された交差点Ｐｃｎに隣接する点である。ステップ１５０における中間点Ｐｉの決定により、交差点Ｐｃｎから、例えば時計回り方向に外向きの、結合フィーチャーＦｃの方向が決まる。例えば、図３を参照すると、交差点Ｐの座標が決まると、ソフトウエアは、交差点Ｐを結合フィーチャーＦｃの境界上の点として採取する。そして、ソフトウエアは、交差点Ｐから開始して、点Ｐからの結合フィーチャーＦｃの外向きのパス上の中間点Ｐｉとして、フィーチャー１の点Ａを含めるか、フィーチャー２の点Ｂを含めるかを決定する。点Ａ、Ｂは、交差点Ｐに隣接する線セグメント端点として選択される（ステップ１０４および１０８の線セグメント端点における配列によって決定される）。そして、ソフトウエアはステップ１５１において、交差点Ｐからの外向きのパスを決定する。さらに、図９ａには示されていないが、実施例において、ソフトウエアは、結合フィーチャーＦｃの内向きのパス上の中間点Ｐｉとして、フィーチャー１の点Ｅを含めるか、フィーチャー２の点Ｆを含めるかを決定してもよい。
【００５５】
ステップ１５０において、交差点Ｐｃからの外向きのパス上における中間点Ｐｉを決定するため、ソフトウエアは、例えば、２つのベクトル（ベクトルＰＡとベクトルＰＢ）ののクロス積の、少なくとも符号を計算する。ここで、
【数２】
引き続き図３を参照するが、ここで、仮想ベクトルＺのポイントが−Ｚの方向（すなわち、紙面に入る方向）を示す時、線セグメントＰＡによって定められるパスが、結合フィーチャーＦｃにおける交差点Ｐからの外向きのパスとして、ソフトウエアに選択される。さらに、点Ａが、結合フィーチャーＦｃ上に含むべき、交差点Ｐからの外向きのパス上の中間点Ｐｉとして、選択される。一方、ベクトルＺのポイントが＋Ｚの方向（すなわち、紙面から出る方向）を示す時は、線セグメントＰＢによって定められるパスが、交差点Ｐからの外向きのパスとして選択され、点Ｂが、結合フィーチャーＦｃ上に含むべき、交差点Ｐからの外向きのパス上の中間点Ｐｉとして、選択される。図３に示す実施例においては、上述のベクトルＺのクロス積方程式により、ベクトルＺが+Ｚの方向を示しているため、線セグメントＰＢによって定められたパスが、ソフトウエアによって選択される。
【００５６】
ソフトウエアは、外向きのパスおよび／または結合フィーチャーＦｃの方向を決定するにあたり、上記クロス積のルールに加えて、他の所定の結合ルールをいくつ用いてもよい。例えば、第一、第二のフィーチャーの分析を、時計回り方向ではなく反時計回り方向で行う場合、左手のルールを用いて、既知の交差点からの結合フィーチャーＦｃの外向きのパスを決定することが出来る。加えて、ステップ１５０で行われる決定は、第一フィーチャーの線セグメントが第二フィーチャーの線セグメントと重なり合う、または部分的に重なり合う場合（２つの線セグメントが同一線上で平行な場合）、および、第一フィーチャーの線セグメントが第二フィーチャーの線セグメントと逆の方向である場合には、第一フィーチャーの線セグメントの取消しおよび／または削除を含んでいてもよい。別の実施例においては、ステップ１５０においてソフトウエアは、計算された各交差点Ｐｃを、結合フィーチャーＦｃ上にある別の交差点と結合することが出来るか否かを判定してもよい。連続的な結合フィーチャーを形成するように連結できない交差点があれば、これらの交差点を削除して、結合フィーチャーの形成には使用しない。
【００５７】
追加的実施例においては、重なり合うフィーチャー境界の交差する線セグメントが平行でも同一直線上にもない場合に、ソフトウエアは、結合フィーチャー境界の決定にあたって、単一のベルトルクロス積（single vector cross product）のみを計算する。このような実施例において、ソフトウエアは、交差点の配列リストから第一交差点を選び取り、上述のように、ベクトルクロス積の符号を用いて、交差点からの外向きのパスを決める。この第一クロス積が計算され、第一交差点からの外向きの結合フィーチャー境界パスが決定されると、ソフトウエアは第二交差点に達するまで、このパスに沿い続ける。配列された第二の交差点への内向きの結合フィーチャー境界パス（すなわち、第一交差点からの外向きのパス）は既知であるので、ソフトウエアは、ただ単に、２つの重なり合うフィーチャーのうちの他方（すなわち、第二交差点への内向きの結合フィーチャー境界パスを定めないフィーチャー）によって定められたパスを選び取ることによって、第二交差点からの外向きのパスを選ぶ。ソフトウエアは、この外向きのパスを、より大きなパラメータ座標値を持つ線セグメント端点の方向または同じ方向（時計回り、または反時計回り）に選び取ってもよい。ソフトウエアは、再び第一交差点に到達するまで、このプロセスを繰り返す。このような実施例においては、システムは第一のクロス積を計算すれば、新たに交差点に出会う度にクロス積を計算する必要はない。この方法は、ソフトウエアが、重なり合うフィーチャー境界の一方の任意の点から開始し、その点が結合フィーチャー境界上にあるか否かが、ソフトウエアで未知であった場合に適用できる。
【００５８】
しかし、その開始点が結合フィーチャー境界上にあることがソフトウエアで既知であった場合は、ソフトウエアは、一切、クロス積を計算する必要はない。このような実施例においては、ソフトウエアは、その代わりに第一フィーチャーを第一方向（時計回り、または反時計回り）に横切り、フィーチャーを切換え、第二フィーチャーに沿って、第一方向に進み続ける。再び第一交差点に到達するまで、このプロセスを繰り返す。上述のとおり、この簡略化したプロセスは、重なり合うフィーチャー境界の交差する線セグメントが平行でも同一直線上にもない場合に、用いられる。
【００５９】
図９ａに示すとおり、ステップ１５２において、ソフトウエアは、ステップ１５１で決定された外向きのパス上にある、次の交差点(Ｐｎ+１）を決定する。この決定をするために、ソフトウエアは、ステップ１４４とステップ１４６に関して上述した、パラメータ座標の配列指数を用いる。例えば、表１に示すパラメータ座標の配列指数は、フィーチャー＃１またはフィーチャー＃２によって定められた外向きのパス上の次の交差点Ｐｎ+１を位置づけ及び／又は決定するために用いることが出来る。最初の交差点Ｐｃｎと外向きのパスが決定されたため、システムは、交差点Ｐｃｎと、交差点Ｐｃｎと次の交差点Ｐｎ+１との間の外向きのパス上に含まれる各線セグメントおよび対応する各線セグメント端点を、順番に、結合フィーチャーＦｃの境界に加える（ステップ１５４）。
【００６０】
そして、ソフトウエアは、次の交差点Ｐｎ+１がステップ１４８で選択した参照点Ｐｒｅｆと等しいか否かを決定する（ステップ１５６）。次の交差点Ｐｎ+１が参照点Ｐｒｅｆと異なるとき、システムは次の交差点Ｐｎ+１を新しい未評価の交差点Ｐｃｎとして選択し（ステップ１５８）、その決定をした後、ステップ１５０に進む。一方、次の交差点Ｐｎ+１がステップ１４８でセットされた参照点Ｐｒｅｆと同一であるとシステムが判定したときは、システムは、新しい結合フィーチャーＦｃが作成され、この結合フィーチャーＦｃの境界上のすべての点が記述（評価）されたと結論を下す。このような結論を下すに当たり、ソフトウエアは、結合フィーチャーＦｃのすべての登録された交差点に、固有のフィーチャー識別子を付ける（ステップ１６０）。結合フィーチャーＦｃ上のすべての交差点は、表２の列５に示す識別子から分かるように、同一の識別子を与えられる。このような識別子は、例えば、種類としてはアルファベットや数字であり、結合フィーチャー同士の識別に有用である。
【００６１】
ステップ１６０の一部として、点の群（グループ）が閉じたフィーチャーを形成しているか（すなわち、当該群の先頭の交差点が最後尾の交差点とつながっているか）を判定するために、点の各群の有効性を検証することが出来る。点の集合が先頭から最後尾まで（または最後尾から先頭まで）連結出来なかった場合、その集合は有効なフィーチャーを構成していない。点の集合が有効なフィーチャーを構成している場合には、そのフィーチャーの点の全体の結合方向をさらに検討すれば、そのフィーチャーが単純フィーチャーであるか穴であるかが判明する。この検討については、以下にさらに詳しく述べる。上述のフィーチャー結合法の結果、有効な結合フィーチャーの境界は、それ自体交差することなく、また他の有効なフィーチャーと交差することもない、閉じたパスである。
【００６２】
ソフトウエアが、有効な結合フィーチャーＦｃが形成されるとともに、結合フィーチャー境界沿いのすべての交差点に適切にフィーチャー識別子が付けられたと判定を下し、システムは、結合フィーチャーＦｃの境界の少なくとも一部を、単位ベースの実世界の座標に変換する（ステップ１６２）。実施例においてシステムは、結合フィーチャーＦｃの境界上に位置する交差点および線セグメントの少なくとも一部を、実世界の座標に変換する。上述のとおり、実世界の座標は、例えば、ミリメートル、インチ等のいかなる公知の長さの単位であってもよく、2倍精度以上の精度を有してもよい。
【００６３】
そして、システムは、実世界の座標を用いて、分析対象の物品が所望の公差範囲内にあるか否かを判定する（ステップ１６４）。上述のとおり、ここに開示する方法は、製造中または生産の物品を検査するために用いてよく、また、公差範囲外および／または他の理由で許容できない物品を却下する助けとなる。ステップ１６６に示すように、分析対象の物品が所定の公差範囲内にはないとき、システムは、オペレータ、中央プロセッサ、その他のコントローラに、分析対象の物品を却下する信号を送る。このような信号により、当該物品は、さらなる分析または機械加工を受けるべく、ラインから外される。物品が公差範囲内であれば、却下信号が送られた場合であっても、システムは結合フィーチャーＦｃが単純フィーチャーであるか否か、または穴フィーチャーであるか否かを判定する（ステップ１６８）。２つのフィーチャーが２つの交差点Ｐｃでのみ互いに交差するとき、結果として得られる結合フィーチャーＦｃは、単純フィーチャーでしかないであろう。しかし、２つのフィーチャーが２つより多い数の交差点Ｐｃで互いに交差するとき、結果として得られる結合フィーチャーＦｃは、その中にもう１つの穴フィーチャーを含んだ、単純フィーチャーである可能性がある。上述したように、穴フィーチャーは、結合フィーチャーの領域（area）の数学符号をチェックすることによって、発見出来る。この計算は、ステップ１６８の一部として行ってよい。
【００６４】
実施例においては、各結合フィーチャーの領域Ａを、以下の数式を用いて計算することが出来る。
【数３】
ここで、（Ｘｉ，Ｙｉ）はフィーチャー上のｉ番目の点の座標であり、ｉはフィーチャーの中の点の指数である。この指数はまた、結合フィーチャー上の点の連結順序（linking sequence）を示す。上記の等式によって計算された領域Ａの数式符号（プラスまたはマイナス）は、フィーチャー上の点が時計回りに結合されているか、反時計回りに結合されているか、に関する信頼性の高い指標を与える。上記の等式によって計算された結合フィーチャーの領域Ａの数式符号がマイナスであれば、対応するフィーチャーの点は時計回りに連結されている、すなわち、結合フィーチャーは単純フィーチャーである。上記の等式によって計算された結合フィーチャーの領域Ａの数式符号がプラスであれば、対応するフィーチャーの点は反時計回りに連結されている、すなわち、結合フィーチャーは確かに穴である。このように、ソフトウエアは、フィーチャーが単純フィーチャーであるか、穴であるかを、単純な計算によって、自動的に判定することが出来る。
【００６５】
穴フィーチャーが結合フィーチャーＦｃの内部にあるか否かを判定するために、穴フィーチャーの任意の点から、無限まで直線的な射線を引くことが出来る。この線が結合フィーチャーＦｃと奇数回交差するならば、穴フィーチャーはフィーチャーＦｃ内に存在する。この線が結合フィーチャーＦｃと偶数回交差するときは、穴フィーチャーはフィーチャーＦｃ内には存在しない。ソフトウエアはまた、単純フィーチャーが穴フィーチャー内に存在するか否かを、同じ方法を用いて判定することが出来る。さらに、単純フィーチャー内の穴フィーチャーの存在を判定するに当たって、ソフトウエアは親である単純フィーチャーおよび子である穴フィーチャーに、公知の任意の用語を用いて、ラベルを付してよい。この親／子決定および、対応する関係のラベル付けは、ステップ１７０で行う。
【００６６】
ステップ１７０の後、または、ソフトウエアが結合フィーチャーＦｃは穴ではないと判断した場合には、ソフトウエアは結合フィーチャーＦｃを結合フィーチャーリストに加える（ステップ１７２）。このような結合フィーチャーリストは、ステップ１１２に関して前述した。さらに、２つの例示的フィーチャー（Ｆ１およびＦ２）の結合の結果、複数の結合フィーチャーＦｃが生成されてもよいことが理解される。したがって、ステップ１７２において、完全で有効な結合フィーチャーＦｃが結合フィーチャーリストに加えられたとしても、その結合フィーチャー上に配置されていない付加的な交差点がステップ１４２で計算され、ステップ１４３で登録されている場合がある。このような付加的な交差点は、例えば、結合フィーチャーＦｃによって形成された１つまたは複数の穴に配置されているかも知れない。したがって、システムは、ステップ１４３で登録されたすべての交差点が評価されたか否かを判定する（ステップ１７４）。登録された交差点でまだ評価されていないものがあれば、システムは未評価の交差点の１つを新しい交差点Ｐｃｎとして選択し、ステップ１４８に戻る。このステップ１４８において、参照点Ｐｒｅｆが再びセットされる（ステップ１７６）。
【００６７】
しかし、もし、すべての登録された交差点が評価済みであれば、ソフトウエアはフィーチャーＦ１をフィーチャーの第一リストから削除し、またフィーチャーＦ２をフィーチャーの第二リストから削除する（ステップ１７８）。そして、ソフトウエアは、結合フィーチャーＦｃがステップ１０２で得られた第一リスト、またはステップ１０６（ステップ１８０）で得られた第二リストのフィーチャーと重なり合うか否かを判定する。この判定を行うために、ソフトウエアはステップ１１０に関して前述したのと類似のプロセスを採用してよい。ソフトウエアは、結合フィーチャーＦｃが第一、第二リストのいかなるフィーチャーにも重なり合っていないと判定した場合には、ステップ１１０に進む（ステップ１８４）。ステップ１１０に戻った時、ソフトウエアは、第一リストのフィーチャーと第二リストのフィーチャーで重なり合うものがあるか否かの判定を続ける。他方、ソフトウエアは、結合フィーチャーＦｃが第一リストまたは第二リストのフィーチャーと重なり合うと判定した場合には、結合フィーチャーＦｃを新しいフィーチャーＦ１として選択し、問題となっている重なり合うフィーチャーを新しいフィーチャーＦ２として選択する（ステップ１８２）。そして、ソフトウエアはステップ１１８に進み、交差判定のために、各フィーチャーの線セグメントを選択する。
【００６８】
本開示の実施例方法は、一般的に、図３に示すフィーチャー１，２（２つの点においてのみ交差する）に関して述べてきたが、同じ方法を、例えば図７に示す別の例示的フィーチャー１，２のような、多数の交差点において互いに交差する２つのフィーチャーに適用出来ることが理解される。また、システムは、上述のプロセスのいかなる時点においても、結合フィーチャーＦｃの外周上の点を、パラメータ座標から、実世界の単位ベースの座標に変換してよいことが理解される。ステップ１６２に関して述べたように、システムは、これら実世界の単位ベースの座標を用いて、結合フィーチャーおよび／または検査対象部品の寸法が所定の公差範囲内にあるか否かを判定することができる。システムは、この判定に基づいて、検査対象部品を却下（reject）することができる。
【００６９】
本明細書を検討することにより、当業者には、他の実施例が明白になるであろう。例えば、追加的実施例において、公知のフィルタリング技術または点を減らす技術（point reduction techniques）を利用して、フィーチャー画像を滑らかにし、および／またはフィーチャー画像中に含まれる点の数を減らすことが考えられる。本明細書および実施例は例示的なものに過ぎず、本発明の真の範囲は以下のクレームによって示される。
【特許請求の範囲】
【請求項１】
第一、第二の重なり合うフィーチャーに基づいて結合フィーチャー境界を形成する方法であって、
上記第一、第二の重なり合うフィーチャーの境界を、既知の形状の線セグメントに分割し、
上記線セグメントによって形成された交差点を同定し、
上記交差点のパラメータ座標を演算し、このパラメータ座標に基づき、交差点評価の順序を決定し、
上記決定された順序における第一交差点を形成する線セグメントに基づき、第一クロス積を演算し、
上記第一クロス積の数学符号にしたがって結合フィーチャー境界の第一パスを選択し、この第一パスは第一交差点から上記決定された順序での第二交差点へと延びており、
上記順序での第二交差点を形成する線セグメントに基づき第二クロス積を演算し、
上記第二クロス積の数学符号にしたがって、第二交差点から延びる結合フィーチャー境界の第二パスを選択すること、を含み、
上記結合フィーチャー境界は、上記第一、第二の交差点と、上記第一、第二パスを定める、上記第一、第二のフィーチャー境界のうちの少なくとも一つの、部分を含むことを特徴とする方法。
【請求項２】
さらに、
上記第一フィーチャー境界において第一交差点に隣接する点を同定し、
上記第二フィーチャー境界において第一交差点に隣接する点を同定し、
上記第一フィーチャー境界の点と上記第二フィーチャー境界の点とのうちの一つを、上記結合フィーチャー境界の中間点として選択すること
を含む請求項１に記載の方法。
【請求項３】
さらに、上記第一、第二の交差点に、上記結合フィーチャー境界を示す識別子を付すこと、を含む請求項１に記載の方法。
【請求項４】
さらに、第一の方向で上記第一、第二のフィーチャー境界のうちの一つに現れる順序にしたがって、上記第一、第二の交差点を配列すること、を含む請求項１に記載の方法。
【請求項５】
さらに、上記第一、第二のフィーチャー境界のうちの一つに現れる上記順序を表す指数を上記第一、第二の交差点に付すこと、を含む請求項４に記載の方法。
【請求項６】
さらに、
上記結合フィーチャー境界によって画成される領域を演算し、この演算された領域の数学符号に基づいて、この結合フィーチャー境界を、単純フィーチャーか穴フィーチャーのいずれかに分類すること、を含む請求項１に記載の方法。
【請求項７】
さらに、
上記線セグメントの端点座標をパレメータ座標に変換し、この線セグメントの端点のパラメータ座標に基づき、どの線セグメントを上記結合フィーチャー境界に含めるのかを決定すること、を含む請求項１に記載の方法。
【請求項８】
さらに、
上記結合フィーチャー境界が第三のフィーチャー境界と重なるかを否かを決定すること、を含む請求項１に記載の方法。
【請求項９】
さらに、
第一、第二のフィーチャー境界が上記結合フィーチャー境界に含まれない交差点を形成するか否かを決定すること、を含む請求項１に記載の方法。
【請求項１０】
上記線セグメントが直線セグメントである請求項１に記載の方法。
【請求項１１】
さらに、上記結合フィーチャー境界を含む結合フィーチャーリストを形成すること、を含む請求項１に記載の方法。
【請求項１２】
第一、第二の重なり合うフィーチャーの境界に基づいて結合フィーチャー境界を形成する方法であって、
上記第一、第二のフィーチャー境界の交差によって形成される複数の交差点のパラメータ座標を演算し、
上記複数の交差点を、それらのパラメータ座標にもとづいて配列順序に組織化し、
各交差点での交差によって形成されたクロス積の数学符号を決定し、
上記数学符号に基づいて複数の交差点の各々間での結合フィーチャー境界のパスを決定し、この結合フィーチャー境界は、上記配列順序にしたがって配された複数の交差点の各々と、第一、第二のフィーチャー境界のうちの少なくとも１つの、部分を含み、
上記結合フィーチャー境界によって画成された領域を演算し、
上記演算された領域の数学符号に基づいて上記結合フィーチャー境界に関するフィーチャタイプを決定すること、
を含む方法。
【請求項１３】
さらに、上記結合フィーチャー境界の一部分を表示すること、を含む請求項１２に記載の方法。
【請求項１４】
上記第一、第二のフィーチャー境界が、製造された部品の公差を付された部分を含む請求項１２に記載の方法。
【請求項１５】
さらに、複数の交差点の各々に、上記第一フィーチャー境界でのそれぞれの交差点の位置に対応して、第一の順序指数を付与すること、を含む請求項１２に記載の方法。
【請求項１６】
さらに、複数の交差点の各々に、上記第二フィーチャー境界でのそれぞれの交差点の位置に対応して、第二の順序指数を付与すること、を含む請求項１２に記載の方法。
【請求項１７】
さらに、上記結合フィーチャー境界を他の結合フィーチャー境界と識別するための識別子を、上記複数の交差点の各々に付与すること、を含む請求項１６に記載の方法。
【請求項１８】
上記フィーチャータイプは、単純フィーチャーと穴フィーチャーの一つである請求項１２に記載の方法。
【請求項１９】
さらに、穴フィーチャが単純フィーチャの中にあるか否かを決定すること、を含む請求項１２に記載の方法。
【請求項２０】
さらに、上記結合フィーチャー境界の部分を、単位ベースの座標に変換すること、を含む請求項１２に記載の方法。
【請求項２１】
さらに、上記単位ベースの座標にもとづいて、上記結合フィーチャー境界の寸法が所定の交差範囲にあるか否かを決定すること、を含む請求項２０に記載の方法。
【請求項２２】
さらに、上記決定に基づいて製造された部品を排除すること、を含む請求項２１に記載の方法。
【請求項２３】
結合フィーチャーリストを作る方法において、
フィーチャーの第一、第二のリストを取得し、
上記第二リストのフィーチャーの境界と重なる上記第一リストのフィーチャーの境界によって形成される、複数の交差点を同定し、
上記の同定された交差点の各々のパラメータ座標を演算し、
上記交差点の各々をそれぞれのパラメータ座標にしたがって配列し、配列された交差点を用いて複数の結合フィーチャー境界を形成し、
上記結合フィーチャー境界の各々を、結合フィーチャーリストに加え、
上記結合フィーチャー境界を形成する各フィーチャーを、上記第一、第二リストから除去すること、
を含む方法。
【請求項２４】
さらに、上記結合フィーチャー境界が上記第一、第二リストのフィーチャーと重なるか否かを決定すること、を含む請求項２３に記載の方法。
【請求項２５】
第一、第二の重なり合うフィーチャー境界に基づいて結合フィーチャー境界を形成する方法であって、
上記の重なり合うフィーチャー境界によって形成される交差点の順序付けられたリストを生成し、
第一の方向で上記第一フィーチャー境界に沿って延びるとともに上記順序付け交差点リストにおける第一交差点で終端する、上記結合フィーチャー境界の第一部分を形成し、
上記第二フィーチャー境界を選択し、
上記第一部分に接続される、上記結合フィーチャー境界の第二部分を形成し、この第二部分は、上記第一方向に上記第二フィーチャー境界に沿って延び上記順序付けられた交差点リストにおける第二交差点で終端することを特徴とする方法。
【請求項２６】
さらに、上記第二交差点において第二部分に接続される、結合フィーチャー境界の残部を形成することを含み、この残部は、上記第一方向に上記第一フィーチャー境界に沿って延び上記第一部分の開始点で終了することを特徴とする請求項２５に記載の方法
【請求項２７】
上記交差点の順序付けリストは、各交差点のパラメータ座標に基づいて生成される請求項２５に記載の方法。
【請求項２８】
さらに、演算されたクロス積の数学符号に基づいて、上記第二フィーチャー境界を選択すること、を含む請求項２５に記載の方法。
【請求項１】
第一、第二の重なり合うフィーチャーに基づいて結合フィーチャー境界を形成する方法であって、
上記第一、第二の重なり合うフィーチャーの境界を、既知の形状の線セグメントに分割し、
上記線セグメントによって形成された交差点を同定し、
上記交差点のパラメータ座標を演算し、このパラメータ座標に基づき、交差点評価の順序を決定し、
上記決定された順序における第一交差点を形成する線セグメントに基づき、第一クロス積を演算し、
上記第一クロス積の数学符号にしたがって結合フィーチャー境界の第一パスを選択し、この第一パスは第一交差点から上記決定された順序での第二交差点へと延びており、
上記順序での第二交差点を形成する線セグメントに基づき第二クロス積を演算し、
上記第二クロス積の数学符号にしたがって、第二交差点から延びる結合フィーチャー境界の第二パスを選択すること、を含み、
上記結合フィーチャー境界は、上記第一、第二の交差点と、上記第一、第二パスを定める、上記第一、第二のフィーチャー境界のうちの少なくとも一つの、部分を含むことを特徴とする方法。
【請求項２】
さらに、
上記第一フィーチャー境界において第一交差点に隣接する点を同定し、
上記第二フィーチャー境界において第一交差点に隣接する点を同定し、
上記第一フィーチャー境界の点と上記第二フィーチャー境界の点とのうちの一つを、上記結合フィーチャー境界の中間点として選択すること
を含む請求項１に記載の方法。
【請求項３】
さらに、上記第一、第二の交差点に、上記結合フィーチャー境界を示す識別子を付すこと、を含む請求項１に記載の方法。
【請求項４】
さらに、第一の方向で上記第一、第二のフィーチャー境界のうちの一つに現れる順序にしたがって、上記第一、第二の交差点を配列すること、を含む請求項１に記載の方法。
【請求項５】
さらに、上記第一、第二のフィーチャー境界のうちの一つに現れる上記順序を表す指数を上記第一、第二の交差点に付すこと、を含む請求項４に記載の方法。
【請求項６】
さらに、
上記結合フィーチャー境界によって画成される領域を演算し、この演算された領域の数学符号に基づいて、この結合フィーチャー境界を、単純フィーチャーか穴フィーチャーのいずれかに分類すること、を含む請求項１に記載の方法。
【請求項７】
さらに、
上記線セグメントの端点座標をパレメータ座標に変換し、この線セグメントの端点のパラメータ座標に基づき、どの線セグメントを上記結合フィーチャー境界に含めるのかを決定すること、を含む請求項１に記載の方法。
【請求項８】
さらに、
上記結合フィーチャー境界が第三のフィーチャー境界と重なるかを否かを決定すること、を含む請求項１に記載の方法。
【請求項９】
さらに、
第一、第二のフィーチャー境界が上記結合フィーチャー境界に含まれない交差点を形成するか否かを決定すること、を含む請求項１に記載の方法。
【請求項１０】
上記線セグメントが直線セグメントである請求項１に記載の方法。
【請求項１１】
さらに、上記結合フィーチャー境界を含む結合フィーチャーリストを形成すること、を含む請求項１に記載の方法。
【請求項１２】
第一、第二の重なり合うフィーチャーの境界に基づいて結合フィーチャー境界を形成する方法であって、
上記第一、第二のフィーチャー境界の交差によって形成される複数の交差点のパラメータ座標を演算し、
上記複数の交差点を、それらのパラメータ座標にもとづいて配列順序に組織化し、
各交差点での交差によって形成されたクロス積の数学符号を決定し、
上記数学符号に基づいて複数の交差点の各々間での結合フィーチャー境界のパスを決定し、この結合フィーチャー境界は、上記配列順序にしたがって配された複数の交差点の各々と、第一、第二のフィーチャー境界のうちの少なくとも１つの、部分を含み、
上記結合フィーチャー境界によって画成された領域を演算し、
上記演算された領域の数学符号に基づいて上記結合フィーチャー境界に関するフィーチャタイプを決定すること、
を含む方法。
【請求項１３】
さらに、上記結合フィーチャー境界の一部分を表示すること、を含む請求項１２に記載の方法。
【請求項１４】
上記第一、第二のフィーチャー境界が、製造された部品の公差を付された部分を含む請求項１２に記載の方法。
【請求項１５】
さらに、複数の交差点の各々に、上記第一フィーチャー境界でのそれぞれの交差点の位置に対応して、第一の順序指数を付与すること、を含む請求項１２に記載の方法。
【請求項１６】
さらに、複数の交差点の各々に、上記第二フィーチャー境界でのそれぞれの交差点の位置に対応して、第二の順序指数を付与すること、を含む請求項１２に記載の方法。
【請求項１７】
さらに、上記結合フィーチャー境界を他の結合フィーチャー境界と識別するための識別子を、上記複数の交差点の各々に付与すること、を含む請求項１６に記載の方法。
【請求項１８】
上記フィーチャータイプは、単純フィーチャーと穴フィーチャーの一つである請求項１２に記載の方法。
【請求項１９】
さらに、穴フィーチャが単純フィーチャの中にあるか否かを決定すること、を含む請求項１２に記載の方法。
【請求項２０】
さらに、上記結合フィーチャー境界の部分を、単位ベースの座標に変換すること、を含む請求項１２に記載の方法。
【請求項２１】
さらに、上記単位ベースの座標にもとづいて、上記結合フィーチャー境界の寸法が所定の交差範囲にあるか否かを決定すること、を含む請求項２０に記載の方法。
【請求項２２】
さらに、上記決定に基づいて製造された部品を排除すること、を含む請求項２１に記載の方法。
【請求項２３】
結合フィーチャーリストを作る方法において、
フィーチャーの第一、第二のリストを取得し、
上記第二リストのフィーチャーの境界と重なる上記第一リストのフィーチャーの境界によって形成される、複数の交差点を同定し、
上記の同定された交差点の各々のパラメータ座標を演算し、
上記交差点の各々をそれぞれのパラメータ座標にしたがって配列し、配列された交差点を用いて複数の結合フィーチャー境界を形成し、
上記結合フィーチャー境界の各々を、結合フィーチャーリストに加え、
上記結合フィーチャー境界を形成する各フィーチャーを、上記第一、第二リストから除去すること、
を含む方法。
【請求項２４】
さらに、上記結合フィーチャー境界が上記第一、第二リストのフィーチャーと重なるか否かを決定すること、を含む請求項２３に記載の方法。
【請求項２５】
第一、第二の重なり合うフィーチャー境界に基づいて結合フィーチャー境界を形成する方法であって、
上記の重なり合うフィーチャー境界によって形成される交差点の順序付けられたリストを生成し、
第一の方向で上記第一フィーチャー境界に沿って延びるとともに上記順序付け交差点リストにおける第一交差点で終端する、上記結合フィーチャー境界の第一部分を形成し、
上記第二フィーチャー境界を選択し、
上記第一部分に接続される、上記結合フィーチャー境界の第二部分を形成し、この第二部分は、上記第一方向に上記第二フィーチャー境界に沿って延び上記順序付けられた交差点リストにおける第二交差点で終端することを特徴とする方法。
【請求項２６】
さらに、上記第二交差点において第二部分に接続される、結合フィーチャー境界の残部を形成することを含み、この残部は、上記第一方向に上記第一フィーチャー境界に沿って延び上記第一部分の開始点で終了することを特徴とする請求項２５に記載の方法
【請求項２７】
上記交差点の順序付けリストは、各交差点のパラメータ座標に基づいて生成される請求項２５に記載の方法。
【請求項２８】
さらに、演算されたクロス積の数学符号に基づいて、上記第二フィーチャー境界を選択すること、を含む請求項２５に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図９ａ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図９ａ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公表番号】特表２０１２−５０７０６７（Ｐ２０１２−５０７０６７Ａ）
【公表日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願番号】特願２０１１−５３３１５３（Ｐ２０１１−５３３１５３）
【出願日】平成２０年１２月１１日（２００８．１２．１１）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０８６３０９
【国際公開番号】ＷＯ２０１０／０５０９９６
【国際公開日】平成２２年５月６日（２０１０．５．６）
【出願人】（５０５３７７４３０）クオリティー ヴィジョン インターナショナル インコーポレイテッド (12)
【氏名又は名称原語表記】Ｑｕａｌｉｔｙ Ｖｉｓｉｏｎ Ｉｎｔｅｒｎａｔｉｏｎａｌ， Ｉｎｃ．
【Ｆターム（参考）】
【公表日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願日】平成２０年１２月１１日（２００８．１２．１１）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０８６３０９
【国際公開番号】ＷＯ２０１０／０５０９９６
【国際公開日】平成２２年５月６日（２０１０．５．６）
【出願人】（５０５３７７４３０）クオリティー ヴィジョン インターナショナル インコーポレイテッド (12)
【氏名又は名称原語表記】Ｑｕａｌｉｔｙ Ｖｉｓｉｏｎ Ｉｎｔｅｒｎａｔｉｏｎａｌ， Ｉｎｃ．
【Ｆターム（参考）】
[ Back to top ]