(57)【特許請求の範囲】
【請求項１】
ライン特徴を包含するシーンの画像データを受け取るビジョンシステムプロセッサと、ラインファインダと、を備え、
上記ビジョンシステムプロセッサはエッジポイント抽出装置を有し、前記エッジポイント抽出装置は、
（ａ）画像データから勾配ベクトル場を計算し、
（ｂ）勾配ベクトル場を複数の勾配投影サブ区域に投影し、
（ｃ）投影された勾配データに基づき勾配投影サブ区域のそれぞれにおいて複数のエッジポイントを検出するものであり、
上記ラインファインダは画像から抽出されたエッジポイントと一致している複数のラインを生成するものである、
取得した画像内のライン特徴を検出するためのシステム。
【請求項２】
上記ラインファインダは、ＲＡＮＳＡＣに基づくプロセスを操作してインライアエッジポイントを新しいラインにフィッティングし、事前に定義されたラインを基準にしてアウトライアエッジポイントから反復的にラインを定義することを含む、請求項１に記載のシステム。
【請求項３】
上記勾配ベクトル場の投影は、１以上の特徴若しくはライン特徴の予想される向きに応答して設定された方向に沿って向けられている、請求項１に記載のシステム。
【請求項４】
上記勾配ベクトル場の投影は、ガウスカーネルに基づいて粒度を定義する、請求項１に記載のシステム。
【請求項５】
上記エッジポイント抽出装置は、勾配投影サブ区域の各々で複数の勾配最大値を検出するように配置されており、勾配最大値はそれぞれ複数のエッジポイントの一部として特定されて、位置ベクトルと勾配ベクトルによって記述される、請求項１に記載のシステム。
【請求項６】
上記ラインファインダは、少なくとも１つの前記エッジポイントの少なくとも１つの候補ラインからの距離と、少なくとも１つの前記エッジポイントの勾配方向と少なくとも１つの候補ラインの通常の方向との間の角度差に基づくメトリックを計算することによって、複数の抽出された前記エッジポイントの少なくとも１つのエッジポイントと、検出された前記複数のラインの少なくとも１つの候補ラインとの間の整合性を決定するように配置されている、請求項１に記載のシステム。
【請求項７】
上記画像データは、複数のカメラから取得された複数の画像からのデータを含み、上記画像は共通座標空間に変換される、請求項１に記載のシステム。
【請求項８】
更に、前記画像データを平滑化する平滑化カーネルを備える請求項１に記載のシステム。
【請求項９】
上記平滑化カーネルは、ガウスカーネルを包含する、請求項８に記載のシステム。
【請求項１０】
上記エッジポイントは、絶対コントラストと、画像データの平均強度に基づいて正規化したコントラストと、によって定義された閾値に基づいて選択される、請求項１に記載のシステム。
【請求項１１】
上記ラインファインダは、誤った向きを補正するために、検出された前記複数のラインから平行線又は交差線の部分を表す複数の抽出された前記エッジポイントのうち少なくとも一部のエッジポイントを交換するように配置されている、請求項１に記載のシステム。
【請求項１２】
上記ラインファインダは、検出された前記複数のラインから極性変化を有するラインを特定するように配置されている、請求項１に記載のシステム。
【請求項１３】
上記特定されるラインは、複数の抽出されたエッジポイントにおける勾配値に基づいて検出された複数のラインのライン特徴における混合極性によって定義されたラインである、請求項１２に記載のシステム。
【請求項１４】
ビジョンシステムプロセッサでシーンの画像データを受け取るステップであって、前記データはライン特徴を含む前記ステップと、
画像データから勾配ベクトル場を計算するステップと、
勾配ベクトル場を複数の勾配投影サブ区域に投影するステップと、
投影された勾配データに基づいて勾配投影サブ区域のそれぞれにおいて複数のエッジポイントを検出するステップと、
画像から抽出されたエッジポイントと一致している複数のラインを生成するステップと、
を有する、取得した画像内のライン特徴を検出するための方法。
【請求項１５】
更に、ＲＡＮＳＡＣに基づくプロセスを適用してインライアエッジポイントを新しいラインにフィッティングすることを有し、事前に定義されたラインを基準にしてアウトライアエッジポイントから反復的にラインを定義することを有する、請求項１４に記載の方法。
【請求項１６】
前記勾配ベクトル場の投影は、１以上の特徴若しくはライン特徴の予想される向きに応答して設定された方向に沿って向けられている、請求項１４に記載の方法。
【請求項１７】
前記勾配ベクトル場の投影は、１Ｄガウスカーネルに基づいて粒度を定義する、請求項１４に記載の方法。
【請求項１８】
更に、勾配投影サブ区域の各々で複数の勾配最大値を検出することを有し、勾配最大値はそれぞれ複数の前記エッジポイントの一部として特定され、位置ベクトルと勾配ベクトルによって記述される、請求項１４に記載の方法。
【請求項１９】
更に、少なくとも１つの前記エッジポイントの少なくとも１つの候補ラインからの距離と、少なくとも１つの前記エッジポイントの勾配方向と少なくとも１つの候補ラインの通常の方向との間の角度差に基づくメトリックを計算することによって、複数の抽出された前記エッジポイントの少なくとも１つのエッジポイントと検出された前記複数のラインの少なくとも１つの候補ラインとの間の整合性を決定することを有する、請求項１４に記載の方法。
【請求項２０】
前記画像データは複数のカメラから取得され共通座標空間に変換された複数の画像からのデータを含む、請求項１４に記載の方法。
【請求項２１】
更に、平滑化カーネルを用いて前記画像データを平滑化することを有する、請求項１４に記載の方法。
【請求項２２】
更に、エッジポイント絶対コントラストと、画像データの平均強度に基づいて正規化したコントラストとによって定義された閾値に基づいて選択することを有する、請求項１４に記載の方法。
【請求項２３】
更に、（ａ）誤った向きを補正するために平行線又は交差線の部分を表すエッジポイントを交換すること、及び（ｂ）前記エッジポイントにおける勾配値に基づいて、前記ライン内の混合極性を含むライン特徴の極性変化を有するラインを特定することの、少なくとも１つを有する、請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は２０１５年２月１１日に出願された同時係属米国特許仮出願第６２／２４９９１８号「ビジョンシステムでラインを検出するためのシステム及び方法」の利益を主張するものであり、その教示内容は参照により本明細書に組み込まれる。
【０００２】
記述分野
本発明はマシンビジョンシステム、より具体的には取得した画像内のライン特徴を検出するビジョンシステムツールに関する。
【背景技術】
【０００３】
マシンビジョンシステム（本明細書中では単に「ビジョンシステム」とも呼ぶ）は、製造、物流及び産業における多様なタスクに使用されている。そのようなタスクは表面および部品の検査、組立工程における対象物のアライメント、パターン及びＩＤコードの読取り、及び視覚データが取得されてその後のプロセスに使用するために解釈されるその他の操作を含んでいてもよい。ビジョンシステムは典型的には１台以上のカメラを用いて興味のある物体又は対象を含むシーンの画像を取得する。物体／対象は静止し、または相対運動をしてよい。運動はロボットで部品を操作する場合のように、ビジョンシステムによって得られる情報で制御することもできる。
【０００４】
ビジョンシステムの共通のタスクは、画像内のライン特徴を検出して特徴付けることである。そのようなライン特徴を特定して解析するために多様なツールが用いられる。典型的には、これらのツールは画像の部分で生じる明確なコントラスト差に依拠している。このコントラスト差、例えばキャリパツールを用いて解析して、コントラスト差のある画像内の個々のポイントがライン状の特徴に集合できるか決定する。できると決定した場合は、画像内でラインが特定される。特に、エッジポイントを検出するツールと、ラインをポイントにフィッティングするツールは互いに独立に動作する。これにより処理オーバーヘッドが増えて信頼性が低下する。画像が複数のラインを含む場合、そのようなツールはそれらを正確に特定する能力が制限されよう。更に、画像内のシングルラインを検出するために設計されたツールは、画像内で類似の向きと極性をもつ複数のラインが密集している場合は使用するのに問題があろう。
【発明の概要】
【０００５】
本発明は先行技術の短所を、複数のラインを効率的且つ正確に特定して特徴付けることを可能にする、画像内のライン特徴を検出するためのシステム及び方法を提供することによって克服する。最初に、プロセスは各画像箇所における勾配場のｘ成分とｙ成分を計算し、勾配場を複数のサブ区域に投影し、各サブ区域内で複数の勾配極値を検出して、関連する位置と勾配を有する複数のエッジポイントを生み出す。次に、プロセスは２つのエッジポイントを反復的に選択し、それらのエッジポイントにモデルラインをフィッティングし、それらのエッジポイントの勾配がモデルラインと一致したら、位置と勾配がモデルラインと一致しているインライアポイントの完全なセットを計算する。最大のインライアカウントを有する候補ラインがライン結果として保存され、残りのセットのアウトライアポイントが導出される。次いでプロセスはこのセット及び後続のアウトライアセットにラインフィッティング操作を反復的に適用して複数のライン結果を検出する。ラインフィッティングプロセスは網羅的であるか、またはランダムサンプルコンセンサス（ＲＡＮＳＡＣ）に基づいてもよい。
【０００６】
例示的な実施形態によれば、取得した画像内のライン特徴を検出するためのシステムが提供される。ビジョンシステムプロセッサは、ライン特徴を包含するシーンの画像データを受け取る。エッジポイント抽出装置は、画像データから強度勾配画像を生成し、強度勾配画像に基づいてエッジポイントを検出する。次いでラインファインダはエッジポイントにおける強度勾配に基づいてエッジポイントを１以上のラインにフィッティングする。例示的に、ラインファインダはＲＡＮＳＡＣに基づくプロセスを操作してインライアエッジポイントを新しいラインにフィッティングし、これは事前に定義されたラインを基準にしてアウトライアエッジポイントから反復的にラインを定義することを含む。エッジポイント抽出装置は、強度勾配画像のライン特徴を含む区域勾配場の投影を実行する。例示的に、勾配場の投影は、１以上の特徴若しくはライン特徴の予想される向きに応答して設定された方向に沿って向けられており、勾配場の投影はガウスカーネルに基づいて粒度を定義できる。例示的に、画像データは複数のカメラから取得されて共通座標空間に変換された複数の画像からのデータを含んでいてもよい。画像データは平滑化（重み付け）カーネルを用いて平滑化されることもでき、平滑化カーネルは１Ｄガウスカーネル又は他の重み付け関数を含んでいてもよい。エッジポイントは絶対コントラストと、画像データの平均強度に基づいて正規化したコントラストとによって定義された閾値が選択され得る。例示的に、ラインファインダは、不正確な向きを補正するために平行線又は交差線の部分を表すエッジポイントを交換するように、及び／又はエッジポイントにおける勾配値に基づいてライン内の混合極性を含むライン特徴の極性変化を有するラインを特定するように構成及び配置されている。また、例示的に、エッジポイント抽出装置は勾配投影サブ区域の各々で複数の勾配最大値を検出するように配置されている。これらの勾配最大値はそれぞれ複数のエッジポイントの一部として特定ができ、位置ベクトルと勾配ベクトルによって記述され得る。加えてラインファインダは、メトリックを計算することによって複数の抽出されたエッジポイントの少なくとも１つのエッジポイントと、検出された複数のラインの少なくとも１つの候補ラインとの間の整合性を決定するように配置され得る。このメトリックは少なくとも１つのエッジポイントの候補ラインからの距離、及びエッジポイントの勾配方向と候補ラインの通常の方向との間の角度差に基づいていてもよい。
【０００７】
以下に本発明を図面を参照して説明する。
【図面の簡単な説明】
【０００８】
【図１】例示的な実施形態による、複数のエッジ特徴を含む物体の画像を取得する模範的なビジョンシステム構成及びエッジ検出ツール／モジュールを含むビジョンシステムプロセッサの図である。
【０００９】
【図２】例示的な実施形態による、取得した画像からエッジポイントを抽出してラインを検出するためのシステム及び方法の全体を示す図である。
【００１０】
【図３】図２のシステム及び方法による、エッジポイント抽出手順のフローチャートである。
【００１１】
【図４】図３のエッジポイント抽出手順の一部である、エッジ特徴を含む画像の区域に場を投影する図である。
【００１２】
【図５】図３のエッジポイント抽出手順で使用する画像を平滑化するために、ガウスカーネルを画像に適用することを示す図である。
【００１３】
【図６】図３のエッジポイント抽出手順で使用する投影を平滑化するためのガウスカーネルの適用を含む場の投影の図である。
【００１４】
【図７】ガウスカーネルの適用とエッジポイントに対する絶対及び正規化したコントラスト閾値の計算を含む、図３のエッジポイント抽出手順の概観を示す図である。
【００１５】
【図８】十分な絶対コントラスト閾値と正規化したコントラスト閾値を有するエッジポイントに対して適格化されたコントラストの区域を示す図である。
【００１６】
【図９】例示的な実施形態による、模範的なＲＡＮＳＡＣを用いる、図３で検出されたエッジポイントに基づくライン検出手順のフローチャートである。
【００１７】
【図１０】密集した平行線特徴に対するエッジポイントの不正確なアライメントと正確なアライメントを示す図である。
【図１１】密集した平行線特徴に対するエッジポイントの不正確なアライメントと正確なアライメントを示す図である。
【００１８】
【図１２】それぞれ例示的なシステム及び方法のラインファインダによって解像され得る、交差線特徴に対するエッジポイントの正確なアライメントと不正確なアライメントエッジポイントを示す図である。
【図１３】それぞれ例示的なシステム及び方法のラインファインダによって解像され得る、交差線特徴に対するエッジポイントの正確なアライメントと不正確なアライメントエッジポイントを示す図である。
【００１９】
【図１４】例示的なシステム及び方法のラインファインダによって解像され得る、明から暗極性、暗から明極性、明から暗若しくは暗から明極性、又は混合極性を示す図である。
【図１５】例示的なシステム及び方法のラインファインダによって解像され得る、明から暗極性、暗から明極性、明から暗若しくは暗から明極性、又は混合極性を示す図である。
【図１６】例示的なシステム及び方法のラインファインダによって解像され得る、明から暗極性、暗から明極性、明から暗若しくは暗から明極性、又は混合極性を示す図である。
【図１７】例示的なシステム及び方法のラインファインダによって解像され得る、明から暗極性、暗から明極性、明から暗若しくは暗から明極性、又は混合極性を示す図である。
【００２０】
【図１８】ユーザ定義マスクを考慮して検出されたラインに対するカバレージスコアの修正を示す図である。
【発明を実施するための形態】
【００２１】
例示的な実施形態に従って使用できる模範的なビジョンシステム構成１００が、図１に示されている。システム１００は少なくとも１台のビジョンシステムカメラ１１０を含み、１台以上の追加の随意のカメラ１１２（仮想線で示す）。例示的なカメラ１１０、１１２は、画像センサ（又はイメージャ）Ｓと、画像フレームを取得してビジョンシステムプロセス（プロセッサ）１３０に伝送する関連エレクトロニクスを含み、ビジョンシステムプロセス（プロセッサ）１３０はスタンドアローンプロセッサ及び／又はコンピューティングデバイス１４０として例示され得る。カメラ１１０（及び１１２）は検査中の物体１５０を包含するシーンに焦点を当てた適当なレンズ／光学系１１６を含んでいてもよい。カメラ１１０（及び１１２）は、画像取得プロセスに従って作動する内部及び／又は外部照明器（図示せず）を含んでいてもよい。コンピューティングデバイス１４０は、例示的な実施形態に従って画像データを保存及び操作できる任意の容認可能なプロセッサベースのシステムであってよい。例えばコンピューティングデバイス１４０は、ＰＣ（図示の例）、サーバー、ラップトップ、タブレット、スマートフォン又は他の類似のデバイスを含んでいてもよい。コンピューティングデバイス１４０は、適当な端末装置、例えばカメラと相互接続するバスベースの画像キャプチャカードを含んでいてもよい。代替的な実施形態において、ビジョンプロセッサは部分的又は完全にカメラ本体それ自体の中に含まれることができ、画像データを共有及び処理する他のＰＣ、サーバー及び／又はカメラベースのプロセッサとネットワーキングできる。コンピューティングデバイス１４０は随意に適当なディスプレイ１４２を含み、これはビジョンシステムプロセス（プロセッサ）１３０内に設けられたビジョンシステムツール及びプロセッサ１３２に従って作動できる適当なグラフィカルユーザインタフェース（ＧＵＩ）をサポートすることができる。種々の実施形態でディスプレイは省くことができ及び／又はセットアップとサービス機能のためにのみ提供できることに留意されたい。ビジョンシステムツールは、物体の検査において使用することが認められる任意の容認可能なソフトウェア及び／又はハードウェアパッケージ、例えば米国マサチューセッツ州ネイティック市のコグネックス株式会社から市販されているものの一部であってよい。コンピューティングデバイスは、例えばキーボード１４４及びマウス１４６、並びにディスプレイ１４２内部のタッチスクリーンを含め関連するユーザインタフェース（ＵＩ）コンポーネントも含んでいてもよい。
【００２２】
カメラ１１０（及び１１２）は、シーン内部に位置する物体１５０の一部又は全部を撮像する。各カメラは光学軸ＯＡを定義し、それを中心に光学系１１６、焦点距離などに基づいて視野が確定される。物体１５０はそれぞれ異なる方向に配置された複数のエッジ１５２、１５４を含む。例えば物体のエッジはスマートフォン本体内に組み付けられたカバーガラスのエッジを含んでよい。例示的に、カメラは物体全体又は特定の箇所（例えばガラスが本体と交わるコーナ）を撮像できる。（共通）座標空間は、物体、１台のカメラ又は他の基準点（例えば物体１５０を載せている可動ステージ）を基準に確定できる。図示されているように、座標空間は軸１５８によって表される。これらの軸は例示的に直交するｘ軸、ｙ軸及びｚ軸、並びにｘ−ｙ面上のｚ軸を中心とする回Θｚを定義する。
【００２３】
例示的な実施形態に従い、ビジョンシステムプロセス１３０は集合的にビジョンシステムツール／プロセス１３２のセットを含む１以上のアプリケーション／プロセス（コンピューティングデバイス１４０上で実行）と相互作用する。これらのツールは、画像データを解像するために使用される多様な慣用的及び特殊なアプリケーション−例えば取得した画像データを所定の（例えば共通）座標系に変換するために使用できる多様な較正ツール及びアフィン変換ツールを含んでいてもよい。画像グレースケール強度データを所定の閾値に基づいて二値画像に転換するツールも含めることができる。同様に、隣接した画像ピクセル（及びサブピクセル）の間の強度の勾配（コントラスト）を解析するツールを設けることができる。
【００２４】
ビジョンシステムプロセス（プロセッサ）１３０は、例示的な実施形態に従い取得した画像内で複数のラインの位置を特定するライン検出プロセス、ツール又はモジュール１３を含む。ここで図２を参照する例示的な実施形態に従うライン検出手順２００の概観を図示する。手順２００は２つの主要部分からなる。入力画像２１０がプロセッサに提供される。図示されているように、画像は１対の交差するエッジ２１２及び２１４を含む。これらは上述した物体１５０のコーナ区域を表すことができる。エッジポイント抽出装置２２０は、入力画像２１０を処理して、それぞれエッジ２１２及び２１４に沿って存在するエッジポイント２３２及び２３４を含む候補エッジポイントのセット２３０を得る。エッジポイント２３２、２３４、及びそれらに関連するデータ（例えば以下に説明する強度勾配情報）が再帰的ラインファインダ２４０に提供され、これは選択されたエッジポイントで一連の反復プロセスを実行する。反復プロセスの目標は、他の検出されたエッジポイントを候補ライン特徴にフィッティングすることを試みることである。ライン検出プロセス２４０の結果、図示されているようにライン２５２及び２５４が検出される。これらの結果は情報を使用する他の下流のプロセス２６０−例えばアライメントプロセス、ロボット操作、検査、ＩＤ読取り、部品／表面検査などに提供され得る。
【００２５】
一実施形態に従う、エッジポイントを抽出するための手順を説明した図３を参照する。検出されるべきエッジ特徴を有する物体又は表面を含んでいるシーンの１以上の画像が取得される（ステップ３１０）。画像は単一のカメラ又は複数のカメラによって抽出できる。いずれの場合も、ステップ３２０で画像ピクセルは、（随意に）適当な較正パラメータによって新しい座標空間及び／又は共通座標空間に変換され得る。このステップは以下に説明するように画像の平滑化も含んでいてもよい。複数のカメラがシーンの不連続区域を撮像する−例えばより大きい物体のコーナ区域に焦点を当てる−実施形態において、共通座標空間はカメラ視野の間の空の区域を占めることができる。以下に説明するように、そのような視野の間に延びるライン（例えば２つの検出されたコーナ区域を接続する物体エッジ）は、例示的な実施形態のシステム及び方法によって例示的な実施形態のシステム及び方法によって外挿できる。ステップ３３０で、ラインを検出するために必要とされるエッジポイントは、適当な座標空間においてエッジポイント抽出装置によって勾配場の投影を用いて画像から抽出される。勾配値は最初に各ピクセルについて計算されて、ｘ勾配成分とｙ勾配成分に対して画像を生成する。画像は更に勾配場を多数のキャリパ状区域に投影することによって処理される。強度値を投影する慣用的キャリパツールとは異なり、実施形態に従い勾配場を投影することによって、勾配の向きを保存でき、以下に説明するようにこれが後続のライン検出プロセスを容易にする。
【００２６】
ステップ３４０で、図４の線図も参照して、候補エッジ特徴を含んでいる画像の部分（キャリパ状区域）４００は（複数の投影４１０、４２０、４３０によって表された）勾配場の投影を受け、サーチ方向（矢印ＳＤ）で（近似的に）予想されるエッジの向きにわたってサーチされ、投影は直交投影方向（矢印ＰＤ）で区域４００にわたって繰り返される。各投影（例えば投影４２０）に対してエッジは投影と関連した勾配場４４０における極大値として現れる。概して、エッジと関連した投影の内部の一連のエッジポイントは、エッジの延在方向に対して直角に強度勾配（ベクトル５５２、５５４）を示す。以下に説明するように、ユーザは予想されるラインの向きに基づいて投影方向を定義できる。代替として、これは既定のメカニズム又は他のメカニズム−例えば画像内の特徴の解析によって提供されてよい。
【００２７】
上述した勾配投影ステップには２つの粒度パラメータが包含されている。勾配場計算の前に、ユーザは異方性ガウスカーネルを用いて画像を平滑化することを選択できる。第１の粒度はこのガウス平滑化カーネルのサイズを決定する。図５の線図５００に示されているように、近似的なサイズのガウスカーネル（例えば大きい５１２、中位５１４、小さい５１６）を適用して画像２１０を平滑化する。それゆえ第１の粒度パラメータは、場計算の前に等方性ガウス平滑化カーネルのサイズを決定する。
【００２８】
これにより勾配場計算の後で、慣用的なキャリパツールにおける統一的な重み付けではなく、ガウス重み付けされた投影がプロセスによって実行される。従って第２の粒度パラメータは、場の投影中に使用される１次元（１Ｄ）ガウスカーネルのサイズを決定し、図６に示されているように区域６００はガウス平滑化カーネル６１０、６２０、６３０を受ける。典型的な操作の間、ユーザは（ＧＵＩを用いて）画像に重ね合わされたすべての抽出されたエッジを検証し、次いで検出されるべきラインに沿って抽出されたエッジの数が十分と思われるまで粒度とコントラスト閾値を調整する一方で、画像内のバックグラウンドノイズに起因するエッジの過度な数を回避する。換言すれば、このステップにより信号雑音比を画像特徴に対して最適化することが可能になる。この調整は、種々の実施形態でシステムにより既定値を用いて自動的に実行することもできる。ガウス重み付け関数は、（例えば）一様な重み付けを含む、投影を重み付けするための多様な方策の１つであることに留意されたい。
【００２９】
勾配場の抽出及び投影の全体の流れが、図７の線図７００に図示されている。２つの粒度パラメータ、等方性ガウスカーネル７１０及び１Ｄガウスカーネル７２０が、全体図７００の各半分に示されている。図示されているように、各々の取得された画像２１０は平滑化及びデシメーション７３０を受ける。次いで結果として生じる画像７４０は、上述したように勾配場の計算７５０を経て、２つの勾配画像７５２及び７５４を生成する。これらの勾配画像はｇｘ及びｇｙとも表現され、それぞれ共通座標空間における２本の直交軸を表す。２つの勾配画像に加えて、強度画像７５６は典型的には平滑化、デシメーション及びに投影プロセス７６０（１Ｄガウスカーネル７２０に基づいてガウス重み付けされた投影７７０を用いる）を受けることに留意されたい。なぜなら、処理された強度情報は、以下に説明する実施形態に従って正規化したコントラストを計算するためにも使用されるからである。その結果は、勾配画像７７２（ｇｘ）、７７４（ｇｙ）及び強度画像７７６の投影プロフィルである。
【００３０】
手順３００（図３）のステップ３５０も参照して、次にｘ勾配画像とｙ勾配画像の１Ｄ投影プロフィルを結合することによって適格化されたエッジポイントが抽出される。このことは生のコントラスト計算７８０と、強度画像に基づいて正規化したコントラスト計算７９０を用いて達成される。より具体的には、それぞれ閾値を超える生の投影された勾配の大きさと正規化した投影された勾配の大きさのいずれも有する局所的なピークは、次の例示的な式に従い後続のライン検出のための候補エッジポイントと見なされる。
（ｇｘ２＋ｇｙ２）１／２＞ＴＡＢＳ
（ｇｘ２＋ｇｙ２）１／２／Ｉ＞ＴＮＯＲＭ
ここで、ｇｘ及びｇｙはそれぞれピクセル箇所におけるｘ勾配投影とｙ勾配投影の値、Ｉは強度、ＴＡＢは生の投影された勾配の大きさに対する絶対コントラスト閾値、及びＴＮＯＲＭは強度正規化した投影された勾配の大きさに対する正規化したコントラスト閾値である。
【００３１】
特に、ポイントはその絶対コントラストと正規化したコントラストがいずれもそれぞれの閾値を超える場合のみ候補エッジポイントと見なされる。このことは正規化したコントラスト閾値ＴＮＯＲＭに対するコントラスト閾値ＴＡＢＳの模範的なグラフ８００において、右上の象限８１０によって示されている。二重の閾値（絶対及び正規化）を用いることは、典型的に絶対コントラスト閾値を使用する既存の方策とは全体として異なる。二重コントラスト閾値の利点は、例を挙げるとある画像がいずれも興味のあるエッジを含む暗い強度区域と明るい強度区域の両方を含む場合に明確である。画像の暗い区域でエッジを検出するためには、低いコントラスト閾値を設定することが望ましい。しかしながらそのような低いコントラストを設定すると、その結果として画像の明るい部分で誤ったエッジを検出する可能性がある。反対に、画像の明るい区域で誤ったエッジを検出するのを避けるためには、高いコントラスト閾値を設定することが望ましい。しかしながら高いコントラストを設定すると、システムは画像の暗い区域でエッジを適切に検出できないかもしれない。伝統的な絶対コントラスト閾値に加えて、第２の正規化したコントラスト閾値を用いることによって、システムは暗い区域と明るい区域の両方で適切にエッジを検出することができ、画像の明るい区域で誤ったエッジを検出するのを避けることができる。それゆえ該当するエッジの検出を可能にする一方で誤ったエッジを回避することにより、避けながら、二重コントラスト閾値の使用は全体プロセスの後続のライン検出段階の速度と堅牢性を最大化するのに役立つ。
【００３２】
更に手順ステップ３５０（図３）を参照すると、すべてのエッジポイントが抽出されたら、後続のラインファインダが作動するために都合の良いデータ構造で再現され保存される。例えば次のタプルに留意されたい。
ｐ＝（ｘ，ｙ，ｇｘ，ｇｙ，ｇｍ，ｇｏ，Ｉ，ｇｍ／Ｉ，ｍ，ｎ）
ここで、（ｘ，ｙ）はエッジポイントの箇所、（ｇｘ，ｇｙ）はそれぞれｘ勾配投影及びｙ勾配投影の値、（ｇｍ，ｇｏ）は（ｇｘ，ｇｙ）から計算された勾配の大きさと向き、Ｉはエッジポイント箇所における強度、ｇｍ／Ｉは勾配の大きさｇｍを強度Ｉで除算することによって得られる強度正規化したコントラスト、ｍは画像インデックス、及びｎは投影区域インデックスである。標準キャリパツールにおけるようなエッジポイントの箇所は、精度を向上させるために補間できる。
【００３３】
エッジポイント抽出プロセスは一般的に場の投影を、予想されるライン角度と実質的に一致する単一方向で行うように作動することに留意されたい。それゆえツールはこの角度にあるエッジに対して最も敏感であり、その感度は他の角度にあるエッジに対して徐々に減少し、減少率は場の投影の長さを間接的に決定する粒度の設定に依存する。結果として角度範囲はユーザによって指定されることを条件に、プロセスは角度が予想されるライン角度「に近い」ラインを検出することに制限される。プロセスは直交していないラインを検出するように適合されているが、種々の実施形態において直交方向を含む複数の方向（全方向ライン検出）で投影を実行することによって３６０度全体の任意の角度のラインを検出できるように一般化されることが想定されている。
【００３４】
手順３００（図３）のステップ３６０を参照すると、例示的な実施形態に従い閾値を超えるエッジポイント候補がラインファインダに提供される。例を挙げると、ラインファインダは再帰的に作動し、（例えば）ランダムサンプルコンセンサス（ＲＡＮＳＡＣ）ベースの技術を採用する。図９におけるライン検出手順９００も参照する。ステップ９１０において、ユーザは１つの画像内で予想されるラインの最大数を、予想される角度、角度誤差、距離誤差及び（例示的に）最小カバレージスコア（以下に一般に定義）と共に（例えば）ＧＵＩによって指定する。これらのパラメータは、次のプロセスを操作するためにラインファインダによって使用される。画像の各サブ区域に対するラインはＲＡＮＳＡＣラインファインダを再帰的に実行して、ある段階からのエッジポイントアウトライアが次の段階に対する入力ポイントとなることによって検出される。こうしてステップ９２０において、手順９００は、エッジ検出プロセスにおいて極値として特定されたエッジポイントのグループ部分である１対のエッジポイントを選択する。手順９００は、モデルラインと（選択された誤差範囲内で）一致している勾配値のマッチングに基づいて、モデルラインを選択されたエッジポイントにフィッティングすることを試みる。ステップ９２４ではステップ９２２からの１以上のライン候補が戻される。各ライン検出段階は候補ライン、そのインライア及びアウトライアを戻す。戻されたラインは、ライン候補と一致する位置と勾配を有するインライアエッジポイントが計算される（ステップ９２６）。ステップ９２８では、最大のインライアカウントを有する候補ラインが特定される。上述したライン検出段階（ステップ９２０−９２８）は、ＲＡＮＳＡＣ反復の許容された最大数に達すると終了する（決定ステップ９３０）。各ライン検出段階内部の反復の最大数は、内部計算されたアウトライアの最悪比率とユーザによって指定された保証レベルを用いて自動的に計算される。各ライン検出段階は、ユーザ指定のフィッティング誤差、幾何学的制限及び極性を条件に、キャンプチャーされたエッジポイントの最大数を有するラインをそのすべての反復から戻す。各エッジポイントは１本のラインのインライアリストのみに割り当てることができ、各ラインは各投影区域からたかだか１つのエッジポイントのみ含むことが許される。エッジポイントの勾配の向きはその位置と共に、候補ラインのインライアリストに含まれるべきか決定するために使用される。具体的には、エッジポイントは候補ラインの角度と一致する勾配の向きを有するべきである。
【００３５】
決定ステップ９３０では、より多くの反復が許可されて、最良インライア候補からのアウトライア（ステップ９４０）を、ＲＡＮＳＡＣプロセス（ステップ９２０）がライン候補の検出に使用するために戻すことを決定する。
【００３６】
各ＲＡＮＳＡＣ反復において、異なる投影区域に属する２つのエッジポイントがランダムに選択され、それらの２つのポイントにラインがフィッティングされる。結果として生じる候補ラインは更に、その角度がポイント対の両エッジの勾配角度と一致するか、及びラインの角度がユーザによって指定された不確かさの範囲と一致するかについてのみ検討される。概して、エッジポイント勾配方向は通常直角であるが、ユーザ設定の角度誤差だけ異なることが許容される。候補ラインがこれらの初期テストに合格したら、次いでインライアエッジポイントの数が評価され、さもなければ新しいＲＡＮＳＡＣ反復が開始される。エッジポイントは、ユーザによって指定された勾配角度と距離誤差に基づいて、その勾配の方向と位置がラインと一致する場合のみ候補ラインのインライアと見なされる。
【００３７】
ＲＡＮＳＡＣ反復が最大数に達したら（決定ステップ９３０）、検出された最良のライン候補のインライアは、（例えば）最小二乗回帰又は他の受け入れ可能な近似法を用いて改善されたラインのフィッティングが行われ、インライアエッジポイントのセットが再評価され、これらのステップを最大Ｎ回（例えば３回以上）、インライアの数がそれ以上増加又は減少しなくなるまで繰り返す（ステップ９６０）。これはステップ９７０で検出されたラインとして出力されるラインである。
【００３８】
決定ステップ９８０は、（（例えば）更にサブ区域又は他の基準をサーチすることによって）より多くのラインが検出されるべきか決定し、そうであればプロセスはステップ９２０にループバックして新しいセットのエッジポイントで作動する（ステップ９８２）。ポイントが使い尽くされるか、又は最大数反復カウントに達したら、手順９００はステップ９９０で（複数の画像内で）検出されたラインのセットを戻す。
【００３９】
マルチラインファインダは、２本のラインが検査区域内で互いに交差する場合に、既存の結果の最終調整を実行するように適合されている。図１０及び図１１に一般的に示されているように、密集した平行線１０１０及び１０２０に対しては、ＲＡＮＳＡＣ手順の統計的正確に起因して時々誤ったライン結果（即ち図１０）が得られることがある。しかしながらそのようなエラーが発生したら、インライアポイントグループの交換（図１１のグループ１１１０における矢印１１２０）は時々カバレージスコアが増加してフィッティング残余が減少した正しいラインの位置を特定することができる。ポイント交換は、図示されているように画像が密集した平行線を含んでいる場合は極めて効果的である。反対に、画像が図１２及び図１３に図示されているように実際に互いに交差するライン１２１０及び１２２０を包含する場合、カバレージスコアはポイント交換の後で減らされ（図１２のグループ１２４０における矢印１２３０）、交換の前に得られた最初の結果は、交差線を首尾よく検出するプロセスにより保存される。
【００４０】
ＲＡＮＳＡＣ手順は、ラインファインダがポイントをラインにフィッティングできる多様な技術の１つであることに留意されたい。代替的な実施形態において、候補ポイントはそれらの間の変位セットに従って選択でき、或いは画像は（例えば）網羅的サーチ技術を用いて処理できる。従って、本明細書中で用いられているようにＲＡＮＳＡＣ技術への参照は、広く多様な類似のポイントフィッティング技術を含むものと解するべきである。
【００４１】
このシステム及び方法の追加の機能を設けることができる。これらは混合極性に対するサポート、投影区域幅の自動計算、多視点ライン検出のサポート、及び歪みのない入力画像により光学歪みを除去できるようにすることを含む。これらの機能について以下に説明する。
【００４２】
更に図１４−図１６の例を参照すると、例示的な実施形態のライン検出システム及び方法は、一般に検出されたエッジ間のコントラストに対して（それぞれ）標準的な明から暗、暗から明及び択一極性設定をサポートする。加えてこのシステム及び方法は明から暗と暗から明の両特徴が同一のラインに現れる混合極性設定（図１７）もサポートできる。全４種類の設定のライン検出結果が次の図に示されている。例示的な実施形態において、システム及び方法は、反対極性のエッジポイントを包含する１本のラインの検出を可能にする混合極性設定を含んでいてもよい。これは、１本のラインのすべてのエッジポイントがいずれかの極性であるが１つの極性に限られている慣用的な「択一」極性設定とは異なる。混合極性設定は、幾つかある応用の中でも（例えば）較正プレートの明暗格子縞に用いられると有利であり得る。
【００４３】
ユーザは、ライン検出の改善されたシフト不変を選択できる。そのような場合に、エッジポイント抽出装置は結果の安定性を改善するために実質的にオーバーラップした投影区域を使用する。これらの区域がオーバーラップしていないと、対象としているピクセルは画像がシフトしたとき投影区域の外に出る可能性があり、その結果としてライン検出結果におけるシフト不変が乏しいものとなる。オーバーラップした投影区域は、対象としているピクセルが投影区域によって連続的にカバーされることを保証する。オーバーラップした投影区域が使用された場合、増分計算を可能な低レベル最適化と共に実行できる。
【００４４】
ユーザは、取得した画像及び／又は撮像された表面の特定部分をライン特徴の解析から除外するマスクを設けることができる。これは表面が興味のない既知のライン特徴（例えば他のメカニズムによって解析されるバーコード、テキスト、及びラインを検出しようとするタスクと密接な関係がないその他の構造）を含む場合に望ましいことがある。従ってエッジポイント抽出装置は、画像内の「無関係」区域はマスクアウトでき「関係」区域はマスクインされる画像マスキングをサポートできる。そのようなマスキングが起きたら、例示的に検出されたラインのカバレージスコアはマスク内に入るエッジポイントの数に従って再重み付される。
【００４５】
図１８の模範的な画像区域１８００を参照すると、画像マスクが存在する場合のカバレージスコアと、そのようなカバレージスコアに及ぼす画像マスキングの効果を示す。エッジポイント抽出装置は、画像内の「無関係」区域をマスクアウトできる画像マスキングをサポートする。図示されているように、検出されたライン１８１０は（「関係」マスク区域１８２０に基づき）関係エッジポイントによって特徴付けられる。そのような関係エッジポイントは、ライン１８１０に対する関係エッジポイントインライア１８３０と、ライン１８１０に対する無関係エッジポイントアウトライア１８４０からなる。ライン１８１０上の無関係エッジポイント１８５０は、この例で示されているようにマスクの関係区域１８２０の間にあり、たとえインライアとしてライン上にあってもカバレージスコア計算に含まれていない。ライン１８１０に沿ったエッジポイントに対する潜在的箇所１８６０も、図示のように決定されている。これらの潜在的箇所は、検出されたポイントの間隔に基づいて予測できる間隔で既知のポイントの間に位置決めされている。例示的に、検出されたラインのカバレージスコアは、マスク内に入るエッジポイントの数に従って再重み付される。これによりカバレージスコアは、次の通り修正される。
カバレージスコア  ＝  ラインに対する関係エッジポイントインライアの数／（ラインに対する関係エッジポイントインライアの数＋ラインに対する関係エッジポイントアウトライア＋関係エッジポイントの潜在的箇所の数）。
【００４６】
本明細書に記載したシステム及び方法に従うライン検出プロセスを実行した後で、検出されたラインはユーザが（（例えば）ＧＵＩによって）指定する分類基準に基づいて種々の方法で分類できる。ユーザは、内部分類手段、例えばインライアカバレージスコア、強度又はコントラストから選択できる。ユーザは内部分類手段、例えば符号付き距離又は相対角度からも選択できる。外部分類手段を用いる場合、ユーザは検出されたラインの外部分類手段を計算するための参照ラインセグメントを指定できる。
【００４７】
一般的に上述したように、このシステム及び方法は多視野角（ＭＦＯＶ）オーバーロードを含むことができ、異なる視野からの画像のベクトルをプロセスに入れることができる。画像はすべて較正に基づいて共通クライアント座標空間にあるべきである。上記のように、この機能性は、複数のカメラを使って単一の部品の部分領域をキャプチャーする応用シナリオにおいて極めて有益であり得る。エッジポイントは勾配情報を保持するので、視野におけるギャップの間に投影されるライン特徴は、（両ＦＯＶにおける勾配が各ＦＯＶで与えられたラインの向き及びアライメントに匹敵するとき）依然として解像され得る。
【００４８】
特に、システム及び方法は、非直線ひずみを取り除いてひずみが重大でないことを保証するために、歪みの除去を要求しない（即ち画像が歪んでいないことを要求しない）（歪みのない画像を可能にする）。画像が歪んでいなければ、システム及び方法は依然として候補エッジポイントを検出し、非線形変換を通してポイント位置と勾配ベクトルをマッピングできる。
【００４９】
システム、及び方法及び種々の代替実施形態／改良に従って提供されるラインファインダは、多様な条件の下で多数のライン特徴を決定するための効果的且つ堅牢なツールであることは明らかであろう。概して、ライン特徴を検出するために使用する場合にシステム及び方法は画像内に検出されるべきラインの最大数に特別制限はない。記憶装置と計算時間のみが検出できるラインの数に実用的な制限を課すであろう。
【００５０】
以上、本発明の例示的な実施形態を詳細に説明した。本発明の精神と範囲を逸脱することなく種々の改変及び追加を行うことができる。上述した種々の実施形態の各々の特徴は、関連する新しい実施形態において多数の特徴の組み合わせを提供するのに適する限り、別の記載された実施形態の特徴と組み合わされてよい。更に、上に本発明の装置と方法の多数の別個の実施形態を記したが、ここに記載されたものは本発明の原理の応用を例示したものに過ぎない。例えば本明細書中で使用される「プロセス」及び／又は「プロセッサ」という言葉は広く電子ハードウェア及び／又はソフトウェアをベースとする多様な機能及びコンポーネント（代替として機能的「モジュール」又は「エレメント」と呼ぶことがある）を含むものと解釈されるべきである。更に、図示されたプロセス又はプロセッサは他のプロセス及び／又はプロセッサと組み合わせ、又は種々のサブプロセス又はサブプロセッサに分割されてよい。そのようなサブプロセス及び／又はサブプロセッサは、本明細書に記載された実施形態に従って多様に組み合わせることができる。同様に、本明細書中の何らかの機能、プロセス及び／又はプロセッサは、プログラム命令の非一時的コンピュータ可読媒体からなる電子ハードウェア、ソフトウェア、或いはハードウェアとソフトウェアの組合せを用いて実施できることが明確に想定されている。更に、本明細書で使用される様々な方向及び／又は向きを表わす用語、例えば、「垂直」、「水平」、「上」、「下」、「底部」、「頂部」、「側部」、「前部」、「後部」、「左」、「右」およびこれに類するものは、相対的な表現法として用いられているに過ぎず、重力の作用方向など固定した座標系を基準とした絶対的な向きを表わすものではない。従ってこの記述は例示としてのみ受け取られるべきであり、本発明の範囲を別途制限することを意味するものではない。加えて、与えられた測定、値又は特徴に関して「実質的に」又は「近似的に」という言葉が用いられている場合、それは所期の結果を達成するための通常の操作範囲内にある量を指しているが、システムに許容された誤差の範囲内の固有の不正確さや誤りに起因するある程度のばらつきを含む（例えば１−５パーセント）。従ってこの説明は例示の方法によるものであり、本発明の範囲を別途制限することを意味するものではない。
【００５１】
特許請求の範囲
【図１】
0006463593.tif 000002
【図２】
0006463593.tif 000003
【図３】
0006463593.tif 000004
【図４】
0006463593.tif 000005
【図５】
0006463593.tif 000006
【図６】
0006463593.tif 000007
【図７】
0006463593.tif 000008
【図８】
0006463593.tif 000009
【図９】
0006463593.tif 000010
【図１０】
0006463593.tif 000011
【図１１】
0006463593.tif 000012
【図１２】
0006463593.tif 000013
【図１３】
0006463593.tif 000014
【図１４】
0006463593.tif 000015
【図１５】
0006463593.tif 000016
【図１６】
0006463593.tif 000017
【図１７】
0006463593.tif 000018
【図１８】
0006463593.tif 000019