(57)【特許請求の範囲】
【請求項１】
モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否か検査し、同条件を満たした曲線データを略閉曲線データとすることを特徴とする閉曲線抽出方法。
【請求項２】
請求項１に記載の閉曲線抽出方法において、略閉曲線データの始点と終点との間を補完して完全閉曲線データを得ることを特徴とする閉曲線抽出方法。
【請求項３】
モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との位置関係が所定の条件を満たすか否かを検査し、同条件を満たした曲線データを完全閉曲線データとすること、同条件を満たさない曲線データについては始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否かを検査し、同条件を満たした曲線データを略閉曲線データとすること、略閉曲線データから始点と終点との間を補完して完全閉曲線データを得ることを特徴とする閉曲線抽出方法。
【請求項４】
モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、切断候補点から近似直線におろした垂線と当該近似直線との交点に対応する原曲線上の点を直線切断候補点とするとき、切断候補点と直線切断候補点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点と直線切断候補点とのうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出すること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否か検査し、同条件を満たした曲線データを略閉曲線データとすることを特徴とする閉曲線抽出方法。
【請求項５】
請求項４に記載の閉曲線抽出方法において、切断候補点を基準として近似直線を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする閉曲線抽出方法。
【請求項６】
請求項４に記載の閉曲線抽出方法において、近似直線を基準として切断候補点を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする閉曲線抽出方法。
【請求項７】
請求項５に記載の閉曲線抽出方法と、請求項６に記載の閉曲線抽出方法とを併用することを特徴とする閉曲線抽出方法。
【請求項８】
モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなることを特徴とする閉曲線抽出方法と、
請求項４から７のいずれかに記載の閉曲線抽出方法とを併用することを特徴とする閉曲線抽出方法。
【請求項９】
請求項４から８の何れかに記載の閉曲線抽出方法において、略閉曲線データの始点と終点との間を補完して完全閉曲線データを得ることを特徴とする閉曲線抽出方法。
【請求項１０】
モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、切断候補点から近似直線におろした垂線と当該近似直線との交点に対応する原曲線上の点を直線切断候補点とするとき、切断候補点と直線切断候補点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点と直線切断候補点とのうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出すること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との位置関係が所定の条件を満たすか否かを検査し、同条件を満たした曲線データを完全閉曲線データとすること、同条件を満たさない曲線データについては始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否かを検査し、同条件を満たした曲線データを略閉曲線データとすること、略閉曲線データから始点と終点との間を補完して完全閉曲線データを得ることを特徴とする閉曲線抽出方法。
【請求項１１】
請求項１０に記載の閉曲線抽出方法において、切断候補点を基準として近似直線を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする閉曲線抽出方法。
【請求項１２】
請求項１０に記載の閉曲線抽出方法において、近似直線を基準として切断候補点を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする閉曲線抽出方法。
【請求項１３】
請求項１１に記載の閉曲線抽出方法と、請求項１２に記載の閉曲線抽出方法とを併用することを特徴とする閉曲線抽出方法。
【請求項１４】
モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなることを特徴とする閉曲線抽出方法と、
請求項１０から１３のいずれかに記載の閉曲線抽出方法とを併用することを特徴とする閉曲線抽出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は閉曲線抽出方法と切断候補点データ作成方法並びにそれらの装置に関し、特に、いわゆる物体認識処理におけるモデルベーストマッチング法の特徴マッチングに適した特徴要素の抽出に有用なものである
【０００２】
【従来の技術】
モデルベーストマッチング法を用いた物体認識処理では、物体を構成する直線、円弧といった幾何学的特徴データ（特徴要素）の集合であるモデルと、画像から抽出した対象物の特徴要素とを比較して、対象物の認識を行う。この比較は、対象物を構成する直線、円弧、円を特徴要素として抽出し、これら対象物の特徴要素のモデルの特徴要素に対する相関（特徴マッチング）をとることにより行われる。
【０００３】
特徴要素の抽出としては、画像データに微分空間フィルタ等の鮮鋭化処理を施すことによりエッジ部分を強調した画像データ（エッジ画像データ）を作成し、これからエッジ画素が連なってなるエッジ線分データ（エッジチェーン）を抽出することにより行われる。
【０００４】
しかし、上記特徴要素のうち、円特徴を抽出することは、実際には非常に難しい。その理由は、「円」は正面から見れば円形であっても、対象物が斜めに傾いていたり、画像中心から離れた位置にある場合などでは、見掛け上「楕円」になるためである。
【０００５】
そこで発明者は、「円」よりも幾何学的な制約が少ない「閉曲線」を特徴要素として用いることが、物体認識には有利であると考えた。
【０００６】
【発明が解決しようとする課題】
しかし、従来のエッジチェーン抽出方法では「曲線」のエッジチェーンを抽出することはできるが、図５６に示す完全な閉曲線１００もしくは略閉曲線１０１と、他の単なる開曲線１１０〜１１２とを区別することはできない。
【０００７】
ここで、略閉曲線とは、完全閉曲線ではないが、もう数ピクセルで始点Ｐｓと終点Ｐｅ間が埋まって閉曲線となるような曲線を言う。また、本明細書では完全閉曲線と略閉曲線を、特に区別する必要がない限り、閉曲線と総称する。
【０００８】
上記に鑑み本発明の課題は、エッジチェーン等の曲線データから完全閉曲線データあるいは略閉曲線データを他と区別して抽出することである。
【０００９】
また、略閉曲線データを抽出した場合は、これを完全閉曲線化することを、本発明の更なる課題とする。
【００１０】
次に、図５７に示す曲線１２０，１２１のように、完全閉曲線もしくは略閉曲線となる部分１０２を曲線上に持っているが、端部に髭のような部分１２２が付いているため、始点Ｐｓと終点Ｐｅとの間が離れているエッジチェーンがある。
髭部分１２２は、実際の画像データでは照明の加減や方向など環境条件の影響によるノイズがあり、また対象物自体の汚れや傷などによるノイズがあるため、本来は閉曲線あるいは略閉曲線であるべきものに付いてしまうと考えられる。
【００１１】
このような髭部分１２２が付いている曲線１２０，１２１をそのまま用いて特徴マッチングを行うと、髭部分１２２のためにマッチング性能が著しく低下する。
【００１２】
そこで、端部に髭部分がノイズとして付いているエッジチェーン等の曲線データから、ノイズを除去した安定な完全閉曲線データもしくは略閉曲線データを抽出することを、本発明の他の課題とする。
【００１３】
更に、図５８に示す曲線１３０，１３１のように、それ自身が完全閉曲線もしくは略閉曲線であっても、途中に大きな歪が生じて波打ったような部分１３２を含むエッジチェーンがある。波部分１３２も、実際の画像データでは照明の加減や方向などの環境条件の影響によるノイズがあり、また対象物自体の汚れや傷などによるノイズがあるために、本来は滑らかな閉曲線あるいは略閉曲線であるべきものに付いてしまうと考えられる。
【００１４】
このような波部分１３２が付いている完全曲線１３０もしくは略閉曲線１３１をそのまま用いて特徴マッチングを行うと、波部分１３２のためにマッチング性能が著しく低下する。従って、髭部分１２２がある場合と同様、間違ったマッチング結果が出る可能性が多く、最終的な物体認識の候補に多くの誤認識結果を含む原因となる。
【００１５】
そこで、途中に波部分をノイズとして含むエッジチェーン等の曲線データからノイズが少ない完全閉曲線データあるいは略閉曲線データを抽出することを、本発明の更に他の課題とする。
【００１６】
【課題を解決するための手段】
第１発明の閉曲線抽出方法は、モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否か検査し、同条件を満たした曲線データを略閉曲線データとすることを特徴とする。
また、第２発明の閉曲線抽出方法は、第１発明の閉曲線抽出方法において、略閉曲線データの始点と終点との間を補完して完全閉曲線データを得ることを特徴とする。
また、第３発明の閉曲線抽出方法は、モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との位置関係が所定の条件を満たすか否かを検査し、同条件を満たした曲線データを完全閉曲線データとすること、同条件を満たさない曲線データについては始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否かを検査し、同条件を満たした曲線データを略閉曲線データとすること、略閉曲線データから始点と終点との間を補完して完全閉曲線データを得ることを特徴とする。
また、第４発明の閉曲線抽出方法は、モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、切断候補点から近似直線におろした垂線と当該近似直線との交点に対応する原曲線上の点を直線切断候補点とするとき、切断候補点と直線切断候補点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点と直線切断候補点とのうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出すること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否か検査し、同条件を満たした曲線データを略閉曲線データとすることを特徴とする。
また、第５発明の閉曲線抽出方法は、第４発明の閉曲線抽出方法において、切断候補点を基準として近似直線を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする。
また、第６発明の閉曲線抽出方法は、第４発明の閉曲線抽出方法において、近似直線を基準として切断候補点を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする。
また、第７発明の閉曲線抽出方法は、第５発明の閉曲線抽出方法と、第６発明の閉曲線抽出方法とを併用することを特徴とする。
また、第８発明の閉曲線抽出方法は、モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなることを特徴とする閉曲線抽出方法と、
第４発明から第７発明のいずれかの閉曲線抽出方法とを併用することを特徴とする。
また、第９発明の閉曲線抽出方法は、第４発明から第８発明の何れかの閉曲線抽出方法において、略閉曲線データの始点と終点との間を補完して完全閉曲線データを得ることを特徴とする。
また、第１０発明の閉曲線抽出方法は、モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、切断候補点から近似直線におろした垂線と当該近似直線との交点に対応する原曲線上の点を直線切断候補点とするとき、切断候補点と直線切断候補点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点と直線切断候補点とのうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出すること、
検出した２点を始点及び終点とする曲線データについて、始点と終点との位置関係が所定の条件を満たすか否かを検査し、同条件を満たした曲線データを完全閉曲線データとすること、同条件を満たさない曲線データについては始点と終点との間の距離及び曲線に外接する長方形の対角線の長さが、これら始終点間の距離と対角線の長さとの比を指標とする所定の条件を満たすか否かを検査し、同条件を満たした曲線データを略閉曲線データとすること、略閉曲線データから始点と終点との間を補完して完全閉曲線データを得ることを特徴とする。
また、第１１発明の閉曲線抽出方法は、第１０発明の閉曲線抽出方法において、切断候補点を基準として近似直線を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする。
また、第１２発明の閉曲線抽出方法は、第１０発明の閉曲線抽出方法において、近似直線を基準として切断候補点を更新することにより、検出手段により、切断候補点との距離が予め設定した許容距離以下の直線切断候補点を探索して、互いに近傍に位置する２点を検出することを特徴とする。
また、第１３発明の閉曲線抽出方法は、第１１発明の閉曲線抽出方法と、第１２発明の閉曲線抽出方法とを併用することを特徴とする。
また、第１４発明の閉曲線抽出方法は、モデルベーストマッチング法により物体認識処理を行う際に用いる特徴マッチングに適した特徴要素を抽出する方法であって、
近似処理手段により、原曲線データを直線と円弧の連なりに近似するステップ、
検出手段により、近似線の各端点に対応する原曲線上の点を切断候補点とし、且つ、２つの切断候補点で区切られる原曲線上の部分を連続区間とし、且つ、連続区間両端の切断候補点のうち原曲線両端の一端側を切断始点、他端側を切断終点とするとき、一の連続区間の切断始点と他の連続区間の切断終点との間の距離の計算と、計算で得た距離と予め設定した許容距離との比較により切断候補点のうちで互いに近傍に位置する２点を検出するステップ、及び、
抽出手段により、検出した２点を始点及び終点とする曲線データを特徴要素として原曲線データから抽出するステップからなることを特徴とする閉曲線抽出方法と、
第１０発明から第１３発明のいずれかの閉曲線抽出方法とを併用することを特徴とする。
【００２４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を、その数例について説明する。
【００２５】
＜第１実施例＞
図２（Ａ），（Ｂ）に、完全閉曲線とそうでない曲線の各エッジチェーンの様子を示す。完全閉曲線の場合は図２（Ａ）に示すように始点Ｐｓを中心とする周囲１ピクセル以下の範囲に終点Ｐｅが存在するが、そうでない曲線（略閉曲線を含む開曲線）の場合は始点Ｐｓを中心とする周囲１ピクセル以下の範囲から外れた所に終点Ｐｅが位置する。この点に着目すると、始点と終点間の位置関係が所定の条件を満すか否かを検査することにより、対象とする曲線データが完全閉曲線データであるか否かを判断することができる。つまり、完全閉曲線データを他と区別して抽出することができる。
【００２６】
具体的な一例をあげると、同図２に示すように対象曲線データ１についてＵＶ直交座標系を設定し、始点Ｐｓの座標（Ｕｓ，Ｖｓ）と終点Ｐｅの座標（Ｕｅ，Ｖｅ）とから、これらの位置関係が次の式（１）と式（２）を同時に満たすか否かを検査することにより、曲線データ１が完全閉曲線データか否かを判断する。
なお、直交座標系をどのように設定するかは自由であるが、Ｕ軸を画面上の水平右方向にとり、Ｖ軸を垂直下方向にとるのが視覚的に判り易くて良い。ＵＶ各軸の単位は１ピクセルである。
【００２７】
【数１】
Ｕｓ−１≦Ｕｅ≦Ｕｓ＋１                              …式（１）
【００２８】
【数２】
Ｖｓ−１≦Ｖｅ≦Ｖｓ＋１                              …式（２）
【００２９】
上記の両式（１）（２）が示す条件がともに満たされる場合は対象とした曲線データが完全閉曲線データであり、少なくとも１つが満たされない場合は完全閉曲線データではなく、略閉曲線データか、あるいは単なる開曲線データである。
【００３０】
従って、略閉曲線か単なる開曲線かの区別は、始点と終点との位置関係だけでは決まらない。
【００３１】
そこで略閉曲線について考えるに、図３（Ａ）に例示する曲線は略閉曲線と呼ぶことに異論はないが、始点Ｐｓと終点Ｐｅとの間の距離が図３（Ａ）と同じ大きさであっても、図３（Ｂ）に例示するように全体が小さい曲線は略閉曲線とは呼べない。また、全体の大きさが図３（Ａ）と同じであっても、図３（Ｃ）に例示するように始点Ｐｓと終点Ｐｅとの間の距離が大きい曲線も略閉曲線とは呼べない。従って、略閉曲線かそうでない単なる開曲線かは、始終点間の距離と、その曲線の幾何学的条件との相対関係で判断する必要がある。
【００３２】
このような相対関係は、始点と終点との間の距離と、曲線に外接する長方形の対角線の長さとの比を指標として所定の条件が満たされるか否かにより検査することができる。
【００３３】
具体的な一例をあげると、略閉曲線データか否かの判断に際して、図４に示すように曲線に外接する長方形として、簡単のためにＵ軸とＶ軸にそれぞれ平行な辺を有する長方形７を考える。
【００３４】
つまり、対象曲線データ１について、ＵＶ直交座標系における始点Ｐｓ（Ｕｓ，Ｖｓ）と終点Ｐｅ（Ｕｅ，Ｖｅ）との間の距離ｄと、Ｕ軸及びＶ軸に平行な長方形７で曲線を囲んだ時の同長方形７の対角線の長さＬとを用い、これらｄとＬが次式（３）を満たすか否かを検査する。ここで、式（３）中の値ａは、略閉曲線であると判断することができる許容範囲のしきい値を表わすための始終点間の距離と対角線の長さとの比であり、予め実験等により設定する。なお、ａ＞０，ｄ＞０，Ｌ＞０としている。
【００３５】
【数３】
ｄ＜ａ・Ｌ                                            …式（３）
【００３６】
上述したｄは次式（４）で示され、Ｌは次式（５）で示される。但し、図４に示すように、対角線の両端点の座標として、座標原点に近い方を（Ｕｍｉｎ，Ｖｍｉｎ）、遠い方を（Ｕｍａｘ，Ｖｍａｘ）としている。
【００３７】
【数４】
ｄ＝（（Ｕｅ−Ｕｓ）2 ＋（（Ｖｅ−Ｖｓ）2)1/2         …式（４）
【００３８】
【数５】
0003695442.tif 000002
【００３９】
ここで、略閉曲線か否かの判断には、本来ならば式（３）を用いれば良いのだが、計算コストを考えると、式（４）及び式（５）中の１／２乗の演算が不要になるように、式（３）の両辺を２乗した次式（６）を用いるのが望ましい。
【００４０】
【数６】
ｄ2 ＜ａ2 ・Ｌ2                                       …式（６）
【００４１】
上式（６）または前式（３）が表わす条件が満たされる場合は対象曲線データ１は略閉曲線データであり、満たされない場合は単なる開曲線データであり、これによって略閉曲線データを他と区別して抽出することができる。
【００４２】
略閉曲線データを抽出した場合、曲線全体の大きさに対して始点と終点間の距離が十分小さいことから、略閉曲線データをそのままモデルとの特徴マッチングに用いても、完全閉曲線データに比べてマッチング性能の低下は殆どない。
【００４３】
しかし、略閉曲線データの始点と終点との間を、何らかの方法により補完して完全閉曲線化しておくと、特徴マッチングでの取扱いが簡単になることがある。
【００４４】
このような完全閉曲線化への補完の具体例をあげると、図５に示すように、略閉曲線データ４の始点Ｐｓと終点Ｐｅとの間を直線８で補完する方法が簡単で良い。
【００４５】
このように直線補完は例えば始点Ｐｓと終点Ｐｅとを通る直線により達成することができる。
【００４６】
（具体的処理例）
次に、図１に示すフローチャートにより具体的処理例を説明する。図１において、曲線データを１つあるいは複数入力すると（ステップＳ１）、１つを対象とし（ステップＳ２）、まずステップＳ３にて、対象曲線データの始点と終点との位置関係が前式（１）及び（２）を満足するか否かを検査することにより、完全閉曲線データか否かを判断する。
【００４７】
完全閉曲線データであれば、そのデータを保存し（ステップＳ４）、ステップＳ７に進む。完全閉曲線データでなければ、ステップＳ５にて、対象曲線データの始点と終点との間の距離と曲線に外接する長方形の対角線の長さとが、前式（６）または（３）を満足するか否かを検査することにより、略閉曲線データか単なる開曲線データかを判断する。
【００４８】
略開曲線データであれば、ステップＳ６にて始点と終点との間を直線で補完し、完全閉曲線化してデータを保存し（ステップＳ４）、ステップＳ７に進む。略閉曲線データでない場合もステップＳ７に進む。
【００４９】
ステップＳ７に進んだ場合は、未処理の曲線データが残っていれば、ステップＳ２に戻って対象曲線データを更新し、上述したステップＳ３以降の手順を繰り返えす。更新すべき曲線データが何もなければ、処理を終了する（ステップＳ８）。
【００５０】
（装置構成例）
図６を参照して閉曲線抽出装置の構成例を説明する。図６に示す装置１０は完全閉曲線抽出部１１と、略閉曲線抽出部１２と、補完部１３からなっている。
【００５１】
完全閉曲線抽出部１１は曲線データ１を入力すると、それの始点と終点との位置関係が前式（１）及び（２）が示す条件を満たすか否かを検査し、満たすものを完全閉曲線データ２と判断し、満たさないものを非完全閉曲線（開曲線）データ３と判断して、２種類に分離する。
【００５２】
略閉曲線抽出部１２は開曲線データ３を完全閉曲線抽出部１１から入力し、始点と終点との間の距離と曲線に外接する長方形の対角線の長さとの相対関係が前式（６）または（３）の条件を満たすか否か検査し、満たすものを略閉曲線データ４と判断し、満たさないものを単なる開曲線データ６と判断して、２種類に分離する。
【００５３】
補完部１３は略閉曲線データ４を略閉曲線抽出部１２から入力し、その始点と終点との間を直線で結んで補完し、完全閉曲線データ５とする。
【００５４】
なお、閉曲線抽出装置１０としては、ＣＰＵを用い、図１等に示した手法をソフトウェアに展開することによりＣＰＵを動作させるように構成することができる。
【００５５】
＜第２実施例＞
上述の第１実施例の手法では、図７（Ａ）に例示するような曲線上に略閉曲線もしくは完全閉曲線となり得る部分２１を持つ曲線データ２０であっても、髭部分２２が付いているために始点Ｐｓと終点Ｐｅが離れている場合は単なる開曲線として判断することになる。
【００５６】
このような曲線データ２０については狭まっている部分（狭部）２３を境目にして略閉曲線もしくは完全閉曲線となり得る部分２１だけを切り取れば、この部分２１を特徴マッチングに用いることによりマッチング性能が向上するはずである。
【００５７】
この切り取りには曲線上で狭まっている部分（狭部）２３を検出する必要があるが、基本的には曲線データの曲線を構成する点（位置情報を持っている）を、総当りで検査することで実現することができる。しかし、曲線が大きい場合には点数が多くなるから検査回数が膨大なものとなる。
【００５８】
そこで、図７（Ｂ）に例示するように、原曲線データ２０を最小自乗法等を用いて直線及び円弧の連なり３０に近似すると、原曲線上の狭部２３のような曲線上で大きな変化のある部分を、近似に用いた直線（以下、近似直線と呼ぶ）や、近似に用いた円弧（以下、近似円弧と呼ぶ）などの近似線３１の端点の対として検出することができる。
【００５９】
即ち、基本的な考え方は、或る２つの端点が互いに近傍に位置すれば、これらの２点は原曲線上の狭部に相当することになり、これらの２点を基に完全閉曲線または略閉曲線となる部分を切断して取り出せば良いのである。どの程度が近傍かは適宜定めれば良い。なお、互いに近傍に位置する２点は必ずしも端点どうしの必要はなく、端点と近似直線上の点であっても良い。
【００６０】
そこで、原曲線上の狭部を検出するに当っては、原曲線に対して後述の如く切断候補点、連続区間、切断始点、切断終点、連続区間が直線で近似されたものか円弧で近似されたものかの区別、という切断候補点データを作成しておくと都合が良い。
【００６１】
ここで、切断候補点とは、基本的には近似線の各端点に対応した原曲線上の点であり、原曲線から完全閉曲線あるいは略閉曲線を切り出すための基本的な候補である。
【００６２】
連続区間とは２つの切断候補点で区切られる原曲線上の部分である。切断始点とは図８に示すように、連続区間２４の両側の切断候補点のうち、始点側の点２５を言う。また切断終点とは連続区間２４の終点側の点２６を言う。なお、始点側か終点側かは、原曲線の両端２点のどちらを始点とし、どちらを終点とするかにより適宜決めれば良いことである。
【００６３】
（切断候補点データ作成装置の構成例）
図９に、切断候補点データを作成する装置の構成例を示す。この切断候補点データ作成装置４０は近似処理部４１と、端点データ抽出部４２と、データ設定部４３から構成されている。
【００６４】
近似処理部４１は図７に示したように原曲線データ２０を直線及び円弧の連なり３０に近似する処理を行うものである。端点データ抽出部４２は、このような近似処理の結果４１Ａから、各近似線の端点データ（位置情報）４２Ａを抽出するものである。データ設定部４３は、端点データ４２Ａと近似処理結果４１Ａと原曲線データ２０から、原曲線上の切断候補点、連続区間、連続区間が直線で近似されたものか円弧で近似されたものかの区別、切断始点と切断終点の区別を、必要データとして設定する。
【００６５】
先に少し触れたが、互いに近傍に位置する２点とは、近似線の端点どうしに限らず、端点と近似直線上の点であっても良いことから、上述した切断候補点データを用いることにより、後述の如く、狭部をなす互いに近傍に位置する２点の検出には幾つかの手法が考えられる。
【００６６】
（切断候補点どうしによる狭部の検出）
２つの切断候補点の間の距離を計算し、得られた距離が狭まっていると判断するに足りる許容距離Ｌ1 の範囲内にあれば、これらを互いに近傍に位置する２点として検出することができる。図１０に例示する点データＰｂａｓｅ，Ｐを用いれば、この条件は次式（７）で示される。
【００６７】
【数７】
((Ｕ−Ｕｂａｓｅ)2＋（Ｖ−Ｖｂａｓｅ)2)1/2＜Ｌ1         …式（７）
【００６８】
ここで、Ｐｂａｓｅは検査の基準とする切断候補点であり、その座標を（Ｕｂａｓｅ，Ｖｂａｓｅ）で表わす。Ｐは検査の対象となる切断候補点であり、その座標を（Ｕ，Ｖ）で表わす。なお、式（７）の両辺を２乗した式を条件として用いてもよい。
【００６９】
（切断候補点と直線による狭部の検出）
切断候補点どうしでは狭部を検出することができない場合でも、図１１に示すように、１つの切断候補点Ｐと、近似直線に対応する連続区間即ち直線連続区間上の中間点Ｐ1 とによる狭部が存在することがある。
【００７０】
そこで、切断候補点から近似直線におろした垂線と当該近似直線との交点に対応する原曲線（直線連続区間）上の点を直線切断候補点として、切断候補点と直線切断候補点との距離を計算し、得られた距離が狭まっていると判断するに足りる許容距離Ｌ1 の範囲内にあれば、これらを互いに近傍に位置する２点と検出する。図１１に例示する点データＰ，Ｐ1 を用いると、この条件は次式（８）で示される。この場合も、式（８）の両辺を２乗した式を条件に用いることができる。
【００７１】
【数８】
((Ｕ1 −Ｕ)2＋（Ｖ1 −Ｖ)2)1/2＜Ｌ1                   …式（８）
【００７２】
ここで、Ｐは切断候補点であり、その座標を（Ｕ，Ｖ）で表わす。Ｐ1 は直線切断候補点、即ち切断候補点Ｐから近似直線へ降ろした垂線と同近似直線との交点に対応する原曲線２０上の点であり、その座標を（Ｕ1 ，Ｖ1 ）で表わす。
【００７３】
なお、切断候補点と直線とによる狭部の検出には、後述の如く、▲１▼切断候補点を基準にして近似直線を更新することにより該当する直線切断候補点を順次探索する場合と、▲２▼近似直線を基準にして切断候補点を更新することにより該当する直線切断候補点を順次探索する場合、との２種類がある。
【００７４】
（切断候補点どうしの狭部検出による閉曲線抽出）
次に、図１２〜図２０を参照して、切断候補点どうしの狭部検出による閉曲線抽出の例を説明する。
【００７５】
図１２は本例の閉曲線抽出方法のフローチャートを示し、ステップＳ１１〜Ｓ２４からなる。
【００７６】
予め対象とする原曲線データを最小自乗法等により直線と円弧の連なりに近似する。そして、前述した如く近似で得られる端点データから、切断候補点、連続区間、切断始点、切断終点なる各データを作成し、後述の如く利用する。
【００７７】
（Ｉ）まず、対象とする原曲線上に、図１３に×印で例示するように、切断候補点を設定する（ステップＳ１１）。なお、図１３中の符号１〜９は連続区間を示しており、数字の小さいものほど始点側の連続区間とする。
【００７８】
（II）ここで、２つの連続区間を区別するために、「tail（テール）」と「head（ヘッド）」という識別用語を導入し、図１４に示すように、原曲線２０上の始めの連続区間を「tail」に設定する（ステップＳ１２）。これは初期データ設定である。
【００７９】
(III）また、同図１４に示すように、「tail」の次の連続区間を「head」に設定する（ステップＳ１３）。
【００８０】
（IV）「head」に設定する連続区間が存在するか否かを判定し（ステップＳ１４）、図１９の如く存在しない場合は処理を終了し（ステップＳ２４）、存在する場合は次のステップＳ１５に移る。
【００８１】
（Ｖ）ステップＳ１５では、「tail」の連続区間の切断始点と「head」の連続区間の切断終点とが狭部をなすか否かを前式（７）により検査する。
【００８２】
（VI）狭部であれば、その時の「tail」の連続区間の切断始点から「head」の連続区間の切断終点までの区間を、閉曲線候補データとして原曲線データから抽出する（ステップＳ１６）。その区間の例を図１６に符号２７で示す。
【００８３】
(VII）狭部でなければ、ステップＳ２２に移る。これについては後で述べる。
【００８４】
(VIII) 閉曲線候補データについては、ステップＳ１７にて、閉曲線データか否かを検査する。ここでは、先に第１実施例で説明した手法により検査する。即ち、閉曲線候補データの始点と終点との位置関係が前述の式（１）及び式（２）を満たすか否かを検査することにより、完全閉曲線データか否かを判断する。また、図１７に示すように、完全閉曲線データでない場合は、その始終点の距離ｄと外接長方形７の対角線の長さＬとが前述の式（３）または式（６）を満たすか否かを検査することにより、略閉曲線データか否かを判断する。更に、略閉曲線データであれば、必要に応じて、その始終点間を例えば直線で補完して完全閉曲線データとする。
【００８５】
（IX）ステップＳ１７にて閉曲線データと判断されたもの（完全閉曲線データ、略閉曲線データ）は、そのデータを保存する（ステップＳ１８）。また、原曲線が更に続くか否かを判断し（ステップＳ１９）、続かなければ処理を終了する（ステップＳ２４）。原曲線がまだ続く場合は、別の閉曲線候補を探すため、「tail」を今までの「head」の次の連続区間に設定し直し（ステップＳ２０）、ステップＳ１３に進んで前記(III）項から手順を繰り返えす。
【００８６】
（Ｘ）ステップＳ１７の検査で閉曲線候補データが単なる開曲線であると判った場合は、そのデータをクリアし（ステップＳ２１）、ステップＳ２２に移る。
【００８７】
（XI）ステップＳ２２では、「head」の連続区間が最後のものか否かを判定する。最後の連続区間であれば、狭部探索を続けるためにステップＳ２０に移り、「tail」の連続区間を現在のものから、図１８に示すように次の連続区間に設定し直し、ステップＳ１３に進んで前記(III）項から手順を繰り返えす。「head」が最後の連続区間でなければ、同じく狭部探索を続けるために、今度は「head」の連続区間を現在のものから、図１５に示すように次の連続区間に設定し（ステップＳ２３）、ステップＳ１４に進んで前記（IV）項の手順から繰り返えす。
【００８８】
ここで、図２０を参照して、切断候補点どうしにより互いに近傍に位置する２点（狭部）を検出する装置（狭部検出装置と呼ぶ）の構成例を説明する。図２０に示す狭部検出装置５０は距離計算部５１と、データ比較部５２からなっている。距離計算部５１は基準とした切断候補点（切断始点）と対象とする切断候補点（切断終点）との間の距離を、例えば前述の式（７）の左辺の計算により求める。データ比較部５２は計算した距離のデータを予め設定した許容距離Ｌ1 と比較し、同式（７）が満たされるか否かを判定し、その結果５３を出力する。式（７）が満たされれば（Ｙes）、２点が互いに近傍に位置して、狭部になっている。
【００８９】
（切断候補点と直線間での狭部検出による閉曲線抽出：その１）
次に、図２１〜図２７を参照して、切断候補点を基準として近似直線を更新することにより同点と狭部をなす直線切断候補点を探索する場合の閉曲線抽出手法例を説明する。
【００９０】
図２１は本例の閉曲線抽出方法のフローチャートを示し、Ｓ３１〜Ｓ４３のステップからなる。
【００９１】
予め対象とする原曲線データを最小自乗法等により直線と円弧の連なりに近似する。そして、前述した如く近似で得られる端点データから、切断候補点、連続区間、連続区間が直線近似のものか円弧近似のものか、切断始点、これら各データを作成し、後述の如く利用する。
【００９２】
（Ｉ）まず、対象とする原曲線に、図２２に×印で示すように、切断候補点を設定する（ステップＳ３１）。図２２中の符号１〜６は連続区間を示しており、数字の小さいものほど始点側の連続区間とする。
【００９３】
（II）本例でも連続区間を区別するために「tail（テール）」と「head（ヘッド）」なる識別用語を導入し、図２３に例示するように、原曲線２０上の始めの連続区間を「tail」に設定する（ステップＳ３２）。これは初期データ設定である。「tail」に設定対象の連続区間は近似直線に対応するもの（直線連続区間）と、近似円弧に対応する（円弧連続区間）の両方である。
【００９４】
(III）また、図２３に例示するように、「tail」の次の直線連続区間を「head」に設定する（ステップＳ３３）。
【００９５】
（IV）「head」に設定する直線連続区間が存在するか否かを判定し（ステップＳ３４）、図２７に示す如く存在しない場合は処理を終了し（ステップＳ４３）、存在する場合は次のステップＳ３５に移る。
【００９６】
（Ｖ）ステップＳ３５では、「tail」の連続区間の切断始点と、「head」の直線連続区間上の直線切断候補点とが狭部になっているか否かを、前式（８）により検査する。この検査で狭部になっていると判定した直線切断候補点を、直線切断点と呼ぶことにする。
【００９７】
（VI）狭部になっていれば、その時の「tail」の切断始点から「head」の直線切断点までの区間を、閉曲線候補データとして原曲線データから抽出する（ステップＳ３６）。その区間の例を、図２５に符号２７で示す。図中、２５は切断始点、２８は直線切断点を示す。
【００９８】
狭部が検出された時の「head」の直線切断候補点即ち直線切断点は、新たな切断候補点として切断候補点データ作成装置（図９参照）により追加設定しておく。その理由は、同じ原曲線上に別の閉曲線候補が存在する可能があるので、別の狭部を検出するのに利用するためである。
【００９９】
(VII）狭部が検出されなければ、ステップＳ４１に移る。これについては後で述べる。
【０１００】
(VIII）閉曲線候補データについては、ステップＳ３７にて、これが本当に閉曲線データであるか否かを検査する。ここでは、先に第１実施例で説明した手法により検査する。即ち、閉曲線候補データの始点と終点（切断始点と直線切断点）との位置関係が前述の式（１）及び式（２）を満たすか否かにより、閉曲線候補データが完全閉曲線データか否かを検査する。また、図２６に示すように、完全閉曲線データでない場合は、閉曲線候補の始点２５と終点２８との間の距離ｄとその外接長方形７の対角線の長さＬとが前述の式（３）または式（６）を満たすか否かにより、閉曲線データ候補が略閉曲線データか否かを検査する。更に、略閉曲線データであれば、必要に応じて、その始終点２５，２８間を補完して完全閉曲線データにする。
【０１０１】
（IX）ステップＳ３７の検査で閉曲線と判定されたデータ（完全閉曲線または略閉曲線データ）は、保存しておく（ステップＳ３８）。また、別の閉曲線候補を探すために、図２７に示すように、「tail」を先の「head」のうちで直線切断点（新たな切断候補点）２８で区切られた後半の連続区間２９に進め（ステップＳ３９）、前記(III）項から手順を繰り返えす。
【０１０２】
（Ｘ）ステップＳ３７の検査で閉曲線候補データが単なる開曲線であると判った場合は、そのデータをクリアし（ステップＳ４０）、ステップＳ４１に移る。
【０１０３】
（XI）ステップＳ４１では「head」の連続区間が最後の直線連続区間であるか否かを判定する。最後の直線連続区間であれば、切断始点を更新して狭部探索を続けるために、ステップＳ３９に移り、「tail」の連続区間を現在のものから次の連続区間に設定し直した後、ステップＳ３３に進んで前記(III）項から手順を繰り返えす。最後の直線連続区間でなければ、同じ切断始点のままで狭部探索を続けることができるので、図２４の如く「head」の直線連続区間を現在のものから次の直線連続区間に設定し直し（ステップＳ４２）、ステップＳ３４に進んで前記（IV）項から手順を繰り返えす。
【０１０４】
（切断候補点と直線間での狭部検出による閉曲線抽出：その２）
次に、図２８〜図３５を参照して、近似直線を基準として切断候補点を更新することにより同点と狭部をなす直線切断候補点を探索する場合の閉曲線抽出手法例を説明する。
【０１０５】
図２８は本例の閉曲線抽出方法のフローチャートを示し、Ｓ５１〜Ｓ６４のステップからなる。
【０１０６】
予め対象とする原曲線データを最小自乗法等により直線と円弧の連なりに近似する。そして、前述した如く近似で得られる端点データから、切断候補点、連続区間、連続区間が直線近似のものか円弧近似のものか、切断終点、これら各データを作成し、後述の如く利用する。
【０１０７】
（Ｉ）まず、対象とする原曲線に、図２９に×印で示すように、切断候補点を設定する（ステップＳ５１）。図２９中の符号１〜７は連続区間を示しており、数字の小さいものほど始点側の連続区間とする。
【０１０８】
（II）本例では、連続区間を区別するために「tail（テール）」と「head（ヘッド）」なる識別用語を導入するが、図３０に例示するように、原曲線２０上の始めの直線連続区間を「tail」に設定する（ステップＳ５２）。
【０１０９】
(III）また、図３０に例示するように、「tail」の次の連続区間を「head」に設定する（ステップＳ５３）。これは初期データ設定である。「head」に設定対象の連続区間は直線連続区間と円弧連続区間の両方である。
【０１１０】
（IV）「head」に設定する連続区間が存在するか否かを判定し（ステップＳ５４）、図３５に示す如く存在しない場合は処理を終了し（ステップＳ６４）、存在する場合は次のステップＳ５５に移る。
【０１１１】
（Ｖ）ステップＳ５５では、「tail」の直線連続区間の直線切断候補点と、「head」の連続区間の切断終点とが狭部になっているか否かを、前式（８）により検査する。この検査で狭部になっていると判定した直線切断候補点を、直線切断点と呼ぶことにする。
【０１１２】
（VI）狭部になっていれば、その時の「tail」の直線切断点から「head」の切断終点までの区間を、閉曲線候補データとして抽出する（ステップＳ５６）。その区間の例を、図３２に符号２７で示す。図中、２６は切断終点、２８は直線切断点を示す。
【０１１３】
(VII）狭部が検出されなければ、ステップＳ６１に移る。これについては後で述べる。
【０１１４】
(VIII）閉曲線候補データについては、ステップＳ５７にて、これが本当に閉曲線データであるか否かを検査する。ここでは、先に第１実施例で説明した手法により検査する。即ち、閉曲線候補データの始点と終点（直線切断点と切断終点）との位置関係が前述の式（１）及び式（２）を満たすか否かにより、閉曲線候補データが完全閉曲線データか否かを検査する。また、図３３に示すように、完全閉曲線データでない場合は、閉曲線候補の始点２８と終点２６との間の距離ｄとその外接長方形７の対角線の長さＬとが前述の式（３）または式（６）を満たすか否かにより、閉曲線データ候補が略閉曲線データか否かを検査する。更に、略閉曲線データであれば、必要に応じて、その始終点２８，２６間を補完して完全閉曲線データにする。
【０１１５】
（IX）ステップＳ５７の検査で閉曲線と判定されたデータ（完全閉曲線または略閉曲線データ）は、保存しておく（ステップＳ５８）。また、原曲線が更に続いているか否かを判定し（ステップＳ５９）、図３５に示すように原曲線がそれ以上続かなければ処理を終了する（ステップＳ６４）。原曲線が更に続く場合は、別の閉曲線候補を探すために、図３４に示すように、「tail」を先の「head」の次の直線連続区間に進め（ステップＳ６０）、前記(III）項から手順を繰り返えす。
【０１１６】
（Ｘ）ステップＳ５７の検査で閉曲線候補データが単なる開曲線であると判った場合は、そのデータをクリアし（ステップＳ６１）、ステップＳ６２に移る。
【０１１７】
（XI）ステップＳ６２では「head」の連続区間が最後であるか否かを判定する。最後であれば、直線連続区間を更新して狭部探索を続けるために、ステップＳ６０に移り、「tail」の直線連続区間を現在のものから次の直線連続区間に設定し直した後、ステップＳ５３に進んで前記(III）項から手順を繰り返えす。「head」が最後の連続区間でなければ、同じ直線連続区間のままで狭部探索を続けることができるので、図３１に示すように「head」の連続区間を現在のものから次の連続区間に設定し（ステップＳ６３）、ステップＳ５４に進んで前記（IV）項から手順を繰り返えす。
【０１１８】
（狭部検出装置の構成）
ここで、図３６を参照して、切断候補点と直線により互いに近傍に位置する２点を検出する装置（狭部検出装置）の構成例を示す。図３６に示す狭部検出装置５５は距離計算部５６と、データ比較部５７からなっている。距離計算部５６は、切断候補点のデータ及び近似直線のデータを用いて、切断候補点と直線切断候補点との間の距離を、例えば前述の式（８）の左辺の計算により求める。データ比較部５７は計算で得た距離のデータを予め設定した許容距離Ｌ1 と比較し、同式（８）が満たされたか否かを判定し、その結果５８を出力する。満たされれば、切断候補点と直線切断候補点が互いに近傍に位置して狭部になっており、距離計算部５６から直線切断点データ５９を出力する。
【０１１９】
（３種類の狭部検出法を併用した閉曲線抽出）
上述した各狭部検出法による閉曲線抽出を個別に行っても良いが、実際の曲線から閉曲線部分を抽出する場合には、これら３種類の狭部検出法を組み合せた処理を行うのが最も適当である。その例を、図３７〜図３８により説明する。
【０１２０】
図３７は本例の閉曲線抽出方法のメインフローチャートを示し、Ｓ７１〜Ｓ８４のステップからなる。また、図３７中のステップＳ７５の詳細（ステップＳ７５−１〜Ｓ７５−３）を図３８に示す。
【０１２１】
予め対象となる原曲線データを直線及び円弧の連なりに近似する。そして、前述した如く近似で得られる端点データから、切断候補点、連続区間、連続区間が直線で近似されたものか否かの区別、切断始点、切断終点の各データを作成し、これらを狭部検出に利用する。
【０１２２】
（Ｉ）まず、対象とする原曲線上に切断候補点を設定する（ステップＳ７１）。
【０１２３】
（II）次に、原曲線上の始めの連続区間を「tail」に設定する（ステップＳ７２）。
【０１２４】
(III）「tail」と設定した連続区間の次の連続区間を「head」に設定する（ステップＳ７３）。
【０１２５】
（IV）「head」を設定することができなければ、処理を終了する（ステップＳ７４，Ｓ８４）。
【０１２６】
（Ｖ）次に、ステップＳ７５で狭部検出を行う。これには、下記３つの手順（Ｖ−１）〜（Ｖ−３）があり、図３８を参照して説明する。
【０１２７】
（Ｖ−１）まず、ステップＳ７５−１にて、「tail」の切断始点と「head」の切断終点とが狭部になっているか否かを前述の式（７）により検査する。
【０１２８】
（Ｖ−２）ステップＳ７５−１の検査で狭部でないことが判ったら、次のステップＳ７５−２にて、「head」に直線連続区間が設定されていれば「tail」の切断始点と「head」の直線連続区間の直線切断候補点とが狭部になっているか否かを前述の式（８）により検査する。但し、「head」と設定した連続区間が直線連続区間でなければ、このステップＳ７５−２の検査では否定的結果（Ｎｏ）を出すものとする。
【０１２９】
（Ｖ−３）ステップＳ７５−２の検査で狭部ではないことが判ったら、次のステップＳ７５−３にて、「tail」に直線連続区間が設定されていれば「tail」の直線連続区間の直線切断候補点と「head」の切断終点とが狭部になっているか否かを前述の式（８）により検査する。但し、この場合は、「tail」と設定した連続区間が直線連続区間でなければ、このステップＳ７５−３の検査では否定的結果（Ｎｏ）を出すものとする。
【０１３０】
（VI）次にメインフローのステップＳ７６では、ステップＳ７５−１〜Ｓ７５−３の肯定的検査結果（Ｙes）に応じて、下記（VI−１）〜（VI−３）の処理を行う。
【０１３１】
（VI−１）ステップＳ７５−１の検査で「tail」の切断始点と「head」の切断終点とが狭部になっていると判定した場合は、その時の切断始点から切断終点までの区間を、閉曲線候補データとして原曲線データから抽出する。
【０１３２】
（VI−２）ステップＳ７５−２の検査で「tail」の切断始点と「head」の直線切断候補点とが狭部になっていると判定した場合は、その時の切断始点から直線切断点までの区間を、閉曲線候補データとして抽出する。また、この時の「head」の直線切断点を新たに切断候補点として追加設定しておく。
【０１３３】
（VI−３）ステップＳ７５−３の検査で「tail」の直線切断候補点と「head」の切断終点とが狭部になっていると判定した場合は、その時の直線切断点から切断終点までの区間を、閉曲線候補データから抽出する。この場合も、この時の直線切断点を新たな切断候補点として追加設定する。
【０１３４】
(VII）ステップＳ７５の検査で狭部が検出できない場合は、ステップＳ８２に移る。
【０１３５】
(VIII）閉曲線候補データについて、ステップＳ７７にて、これが本当に閉曲線データであるか否かを検査する。即ち、対象とする閉曲線候補データの始点と終点（切断始点と切断終点、あるいは切断始点と直線切断点、あるいは直線切断点と切断終点）との位置関係が前述の式（１）及び式（２）を満たすか否かにより、完全閉曲線データか否かを検査する。また、完全閉曲線データでなければ、閉曲線候補データの始点と終点との距離を、その外接長方形の対角線の長さとが前述の式（６）または（３）を満たすか否かにより、略閉曲線データか否かを検査する。更に、略閉曲線データであれば、その始終点間を補完して完全閉曲線データにする。
【０１３６】
（IX）ステップＳ７７の検査で閉曲線と判断されたものについて、そのデータを保存する（ステップＳ７８）。そして、原曲線がまだ続いているか否かを、「tail」に設定する候補（現在の「head」の次の連続区間）が存在するか否かにより判定し（ステップＳ７９）、まだ続いていれば「tail」を現在の連続区間から、「head」の次の連続区間に設定し直し（ステップＳ８０）、ステップＳ７３に進んで前記(III）項から手順を繰り返えす。原曲線が続いていなければ処理を終了する（ステップＳ８４）。
【０１３７】
（Ｘ）ステップＳ７７の検査で閉曲線候補データが単なる開曲線であり、完全閉曲線でも略閉曲線でもないと判った場合は、そのデータをクリアし（ステップＳ８１）、ステップＳ８２に移る。
【０１３８】
（XI）ステップＳ８２では現在の「head」の連続区間が最後のものか否かを判定する。「head」が最後の連続区間であれば、ステップＳ８０で「tail」の連続区間を現在のものからその次の連続区間に設定し直し、ステップＳ７３に進んで前記(III）項から手順を繰り返えす。「head」が最後の連続区間でない場合は、ステップＳ８３にて「head」の連続区間を現在のものからその次の連続区間に設定し直し、ステップＳ７４に進んで前記（IV）項から手順を繰り返えす。
【０１３９】
（装置構成例）
次に、図３９を参照して閉曲線抽出装置の構成例を説明する。図３９に示す装置６０は、切断候補点データ作成部６１と、狭部検出部６２と、閉曲線候補抽出部６３と、閉曲線検査部６４と、閉曲線データ保存部６５からなっている。
【０１４０】
図３９における切断候補点データ作成部６１は図９に示した切断候補点データ作成装置４０と同じ構成のものであり、図９を参照すれば、近似処理部４１と、端点データ抽出部４２と、データ設定部４３から構成される。また各部の機能を説明すれば、近似処理部４１は原曲線データ２０を直線及び円弧の連なりに近似し、端点データ抽出部４２は近似処理結果４１Ａから近似線の端点データ（位置情報）４２Ａを抽出する。更にデータ設定部４３は端点データ４２Ａと近似処理結果４１Ａと原曲線データ２０から、原曲線上の切断候補点、連続区間、連続区間が直線で近似されたものか否かの区別、切断始点、切断終点の各データ４４を設定する。この場合、切断候補点には後述の如く直線切断点も含まれる。
【０１４１】
図３９における狭部検出部６２は図２０に示した切断候補点どうしによる狭部を検出する装置５０と、図３６に示した切断候補点と直線切断候補点による狭部を検出する装置５５との双方の機能を持つ。従って同狭部検出部６２は距離計算部とデータ比較部から構成されるが、そのうち距離計測部は切断候補点データ４４を用いて、前式（７）左辺による切断候補点どうしの距離の計算を行うだけでなく、前式（８）左辺による切断候補点と直線切断候補点との距離の計算を行い、更に、切断候補点と直線切断候補点とが狭部になっている場合にはその時の直線切断点のデータ５９を新たな切断候補点として切断候補点データ作成部６１に与える。データ比較部は計算で得た距離データを許容距離と比較し、式（７）または式（８）が満たされるか否かにより狭部を検出する。
【０１４２】
閉曲線候補抽出部６３は狭部検出部６２の検出結果５３（図２０参照），５８（図３６参照）に基づき、切断候補点データ４４から、切断始点と切断終点、切断始点と直線切断点、直線切断点と切断終点いずれかの対を始点及び終点とする閉曲線候補データ６６を抽出する。なお、切断候補点データ４４は原曲線データ２０と同じ曲線を表わしている。
【０１４３】
閉曲線検査部６４は閉曲線候補データ６６について、前述の式（１）及び式（２）により完全閉曲線か否かを検査し、更に前述の式（３）または式（６）により略閉曲線か否かを検査する。また、必要に応じて、略閉曲線を直線補完して完全閉曲線にする。
【０１４４】
閉曲線データ保存部６５は閉曲線検査部６４の検査結果６７に基づいて、閉曲線候補データ６６のうち完全閉曲線あるいは略閉曲線と判定されたもの、あるいは直線補完により得た完全閉曲線を、閉曲線データとして保存する。
【０１４５】
＜第３実施例＞
以上説明した第２実施例の手法では、図４０（Ａ），（Ｂ）に示すように髭部分２２が付いている原曲線データ２０から、髭部分を切り離した閉曲線データ７０，７１を抽出することができたが、曲線途中にノイズのため波打ち部分７２があれば残ってしまう。この部分７２は第１実施例の手法でも残る。
【０１４６】
このような波打ち部分７２が閉曲線データ７１に存在すると、その程度によっては特徴マッチングの性能が低下するので、特徴マッチングに適したノイズの少ない閉曲線データを抽出することが望ましい。
【０１４７】
そこで、第１実施例あるいは第２実施例の手法により得られた、図４０に符号７０，７１で示すような略閉曲線データ及び完全閉曲線データを、改めて閉曲線データ候補と呼ぶこととし、これら閉曲線データ候補の幾何学的形状を検査することにより、特徴マッチングに適さないものを排除して、良好なマッチング性能が得られるものだけを閉曲線データとして抽出する。
【０１４８】
以下、図４１〜図５５を参照して第３実施例に係る閉曲線抽出技術を説明する。
【０１４９】
図４１は本例の閉曲線抽出方法のフローチャートを示し、Ｓ９１〜Ｓ９５のステップからなっている。
【０１５０】
図４１において、まず検査すべき閉曲線データ候補を設定し（ステップＳ９１）、その曲線の幾何学的形状が詳細は後述するが特徴マッチングに適しているか否かを検査し（ステップＳ９２）、特徴マッチングに適しているものだけを、閉曲線データとして保存し（ステップＳ９３）、適していなければ排除する。そして、まだ別の閉曲線データ候補が存在しているか否かを調べ（ステップＳ９４）、存在していればステップＳ９１に戻ってその閉曲線データ候補を次の検査対象に設定し、形状検査を行う。閉曲線データ候補が残っていなければ処理を終了する（ステップＳ９５）。
【０１５１】
幾何学的形状検査には、曲線の周囲長を検査する方法と、曲線を直線と円弧の連なりに近似した時の近似円弧の中心角を検査する方法と、曲線形状が凸形状か否かを検査する方法と、曲線が星形状か否かを検査する方法とが考えられる。以下これらの詳細を説明する。
【０１５２】
（曲線周囲長の検査）
対象物の撮像画から閉曲線を抽出した場合、画像全体の大きさに比べて閉曲線の周囲長が十分小さければ、その閉曲線には特徴マッチングに悪影響を及ぼすノイズが殆ど入っていないと考えることができる。例えば、画面全体の画素数が５１２×５１２ピクセルであった場合、完全閉曲線もしくは略閉曲線のうち、その曲線を構成する点の数が１００ピクセル以下程度のものでは、周囲長が十分小さい故に、特徴マッチングに影響を及ぼすようなノイズがデータ内に入ることは殆どない。
【０１５３】
そこで、閉曲線データ候補の曲線周囲長を検査し、許容長さ以下であれば、特徴マッチングに適した閉曲線データであると判断し、これをそのまま抽出する。
【０１５４】
より具体的には、閉曲線データ候補の曲線を構成する点の数を許容点数と比較することにより、許容点数以下のものを閉曲線データとする。ここで、許容長さあるいは許容点数は、画像全体あるいは画面全体の画素数に比べて十分小さい値であり、実験等により作業者等が予め設定しておく。
【０１５５】
（装置構成例）
図４２に、曲線周囲長の検査を適用した閉曲線抽出装置の構成例を示す。この閉曲線抽出装置８０は形状検査部８１と、データ保存部８２からなっている。形状検査部８１は閉曲線データ候補７３の周囲長を、その曲線を構成する点の数として求め、得られた点数を設定値Ｎと比較することにより形状を検査し、その検査結果をデータ保存部８２に与える。データ保存部８２は点数が設定値Ｎ以下の閉曲線データ候補のみを特徴マッチングに適した閉曲線データとして保存する。
【０１５６】
（近似円弧中心角の検査）
次に、図４３に示すように、閉曲線データ候補７３を最小自乗法等により直線と円弧の連なり７４に近似した場合を考える。このとき得られる近似円弧のうち、図４４に示すように、その中心角θが例えば３３０°程度以上のもの７５が存在すれば、閉曲線データ候補７３のうちその近似円弧７５に相当する部分７６は非常に円に近い「略円形状」と考えることができる。つまり、この部分７６はノイズが非常に少ない特徴マッチングに適した曲線部分と考えることができる。この考え方は、「円」が機械加工においてドリル等であけた穴として、工業製品の対くに存在することから、妥当であると言える。
【０１５７】
そこで、図４４に示すように閉曲線データ候補７３を直線と円弧の連なりに近似した時に得られる近似円弧７５の中心角θを検査することにより、閉曲線データ候補全体が略円形状になる場合はもちろんこれを閉曲線データとしてそのまま抽出し、また部分的に略円形状が存在する場合はその部分７６のみを閉曲線データとして抽出する。
【０１５８】
近似円弧の中心角を調べるには、図４３（Ｂ）に×印で示すように、形状検査点として幾何学的形状検査のための代表的な点を曲線上に設定し、これを用いると都合が良い。形状検査点としては、閉曲線データ候補７３を最小自乗法等を用いて直線と円弧の連なり７４に近似した場合の近似直線の両端の点と、近似円弧の両端の点及び中点とが基本である。なお、形状検査点の位置データは近似に用いた直線、円弧自体のデータとしている。
【０１５９】
図４５を参照して形状検査点のうち近似円弧の両端点と中点を用いて近似円弧の中心角を検査する手法の例を説明する。図４５において、近似円弧７５上の３個の形状検査点（近似円弧の両端点と中点）の位置データを用いて周知の数学手法により円周角φを計算し、この計算結果を基に中心角（図４４（Ｂ）のθ）を計算し、予め設定しておいた中心角の許容角度と比較する。中心角が許容中心角度以上であれば、近似円弧７５に対応する原曲線上の部分（図４４（Ａ）の７６）が閉曲線であり、これを閉曲線データ候補から抽出する。許容角度は実験等により作業者等が設定する。なお、中心角θと円周角φとの関係はθ＝３６０°−２φである。
【０１６０】
ところで、近似円弧の検査を行うためには、理論的には中心角か円周角のどちらか一方を計算するだけで良いが、円弧のデータとして考えた場合は「中心角」を扱う方が一般的に便利である。つまり、始めに円周角を計算し、そのデータから中心角を計算して、中心角のデータから閉曲線の検査を行うのが、取扱いが便利であるためである。言い換えると、中心角も円周角もこれを求める手法は「２つの直線のなす角」として計算するので中心角を直接求めるような手順を採っても理論的には良いのだが、計算機による演算では、計算機上の技術的な問題のために円周角を求めてから中心角を求める方が簡単になる。即ち、「２つの直線のなす角」を計算するにはアークコサイン（ａｒｃｃｏｓまたはｃｏｓ-1）を用いるのだが、計算機上でのアークコサインの範囲が０〜１８０度であるのに対し、中心角の範囲は０〜３６０度、円周角の範囲は０〜１８０度となることから、アークコサインを用いる計算では先ず円周角を求め、これから中心角を求めるのが妥当であると考えられる。
【０１６１】
以上のことより、中心角の代りに、閉曲線データ候補を直線と円弧の連なりに近似したときに得られる近似円弧の円周角φの大きさを検査し、閉曲線データ候補のうち許容円周角度以下の近似円弧に対応する部分を、特徴マッチングに適した閉曲線データとして抽出する方法を採用することも可能である。
【０１６２】
（装置構成例）
図４６に、近似円弧中心角の検査を適用した閉曲線抽出装置の構成例を示す。
この例の閉曲線抽出装置８５は近似処理部８６と、円周角計算部８７と、中心角比較部８８と、データ保存部８９からなっており、円周角計算部８７と中心角比較部８８が近似円弧中心角の検査部を構成している。
【０１６３】
近似処理部８６は閉曲線データ候補７３を直線と円弧の連なり７４に近似する処理を行うものであり、図９に示した切断候補点データ作成装置４０中の近似処理部４１と兼用することができる。従って、閉曲線データ候補７３が第２実施例の如く原曲線を最小自乗法等により直線と円弧の連なりに近似する処理を利用して得られたものである場合は、この時の近似処理結果を再度利用できるので、近似処理部８６を閉曲線抽出装置８５から除外できる。
【０１６４】
円周角計算部８７は近似処理結果から形状検査点を設定し、各近似円弧毎にそれの３個の形状検査点（両端点と中点）の位置データを用いて円周角φを計算する。中心角比較部８８は円周角φから中心角（３６０°−２φ）を計算し、設定値θ0 と比較することにより形状検査をし、その結果をデータ保存部８９に与える。
【０１６５】
データ保存部８９は閉曲線データ候補７３のうち、中心角が設定値θ0 以上の近似円弧に相当する部分のみを特徴マッチングに適した閉曲線データとして保存する。
【０１６６】
なお、近似円弧の円周角の大きさを検査する場合は、中心角比較部８８の代りに円周角比較部を用い、この円周角比較部により円周角φを設定値と比較することにより形状検査を行い、その結果をデータ保存部８９に与える。また、データ保存部８９は閉曲線データ候補７３のうち、円周角が設定値以下の近似円弧に相当する部分のみを特徴マッチングに適した閉曲線データとして保存する。
【０１６７】
（凸形状の検査）
次は、凸形状か否かの検査により閉曲線データ候補から閉曲線データを抽出する手法について説明する。
【０１６８】
一般に機械加工でワークに作られる穴の殆どは「円形状」であるが、穴が存在する面が撮影用カメラに対して傾いている状態では、入力画像から得られる穴の形状は「楕円」となり、また照明等の影響によっては本来は「円」もしくは「楕円」となるものが多少歪んでしまい、本来の形状にならないことが多い。
【０１６９】
しかしながら、「バリにより穴の一部が塞がる」ことや、「背景が対象物体と同系色のために穴の存在がはっきりしない」こと等の大きなノイズがない限り、対象物体の平面上に明けた穴は、「凸形状」という幾何学的特徴を持つことが非常に多い。
【０１７０】
そこで、閉曲線データ候補が凸形状か否かを検査し、凸形状である場合には、閉曲線データ候補を閉曲線データとしてそのまま抽出する。
【０１７１】
凸形状か否かの検査には、前述した形状検査点（閉曲線データ候補を最小自乗法等により直線と円弧の連なりに近似した場合の近似直線の両端点と、近似円弧の両端点及び中点）を利用すると便利である。即ち、連続した３つの形状検査点毎に、始終点側のうち一方側の形状検査点から中間の形状検査点へのベクトルと、一方側の形状検査点から他方側の形状検査点へのベクトルを考えて両ベクトルの外積をとると、凸形状の曲線であれば外積の方向即ち符号は常に同じになり、凸形状でなければ途中で符号（方向）が変化する。従って、外積の符号あるいは方向が変化しなければ凸形状であり、閉曲線データとして抽出することができる。
【０１７２】
以下、図４７〜図４９により、形状検査点を用いた凸形状検査の具体例を説明する。
【０１７３】
予め、図４７〜図４８に×印で示すように、閉曲線データ候補点７３に、それの近似処理結果に基づいて形状検査点を設定しておく。
【０１７４】
図４９は凸形状検査例のフローチャートを示し、Ｓ１００〜Ｓ１０９のステップからなる。なお、本例ではステップＳ１００，Ｓ１０８から判るように検査フラグとしてflagを導入し、検査により凸形状でないと判明した段階で検査フラグflagをＹesからＮｏにリセットするものとしている。
【０１７５】
（Ｉ）まず、検査フラグflagをＹesに設定し、形状検査点の最初例えば始点側の点を、点０と設定する（ステップＳ１００）。
【０１７６】
（II）次に、点０に続く２つの形状検査点を近い順に点１，点２と設定する（ステップＳ１０１）。
【０１７７】
(III）この時、３つ目の形状検査点２が設定できたか否か判定し、設定できない場合は処理を終了し（ステップＳ１０９）、設定できたならばステップＳ１０３に進む。
【０１７８】
（IV）ステップＳ１０３では、まず点０から点１へのベクトルを求めてこれをＶ1 * と設定し、また点０から点２へのベクトルを求めてこれをＶ2 * として設定する。
【０１７９】
（Ｖ）またステップＳ１０３では、両ベクトルの外積Ｖ1 * ×Ｖ2 * を計算し、その方向（符号）を求める。ここまでの様子を、図４７（Ａ），図４８（Ａ）に示す。
【０１８０】
（VI）次に、ステップＳ１０４で点０が形状検査点の始点か否かを判定し、始点であればステップＳ１０５に進み、そうでなければステップＳ１０６に進む。
【０１８１】
(VII）点０が形状検査点の始点であれば、外積Ｖ1 * ×Ｖ2 * の方向が初めて得られたので、その符号を初期方向として設定し（ステップＳ１０５）、ステップＳ１０７に進む。
【０１８２】
(VIII）点０が形状検査点の始点でなければ、既に初期方向が設定されているので、初期設定方向と今回求めた外積の方向とを比較し、一致すればステップＳ１０７に進み、不一致であればステップＳ１０８に進む。
【０１８３】
（IX）ステップＳ１０７では、図４７（Ｂ），図４８（Ｂ）に示すように点０を今までの点１に設定し直し、ステップＳ１０１に戻って前記（II）項から手順を繰り返えす。その結果、図４７の場合は同図（Ｃ）に示すように外積Ｖ1 * ×Ｖ2 * の方向が最後まで初期方向と同じなので、この閉曲線データ候補７３は凸形状と判定される。
【０１８４】
（Ｘ）ステップＳ１０８では検査フラグflagをＮｏにリセットし、検査処理を終了する。図４８の場合は、同図（Ｃ）に示すように外積Ｖ1 * ×Ｖ2 * の方向が途中で初期設定方向から変化するので、凸形状ではないと判定される。
【０１８５】
（装置構成例）
図５０に、凸形状検査を適用した閉曲線抽出装置の構成例を示す。この閉曲線抽出装置９０は近似処理部９１と、凸形状検査部９２と、データ保存部９３からなっている。
【０１８６】
近似処理部９１は閉曲線データ候補７３を直線と円弧を含む近似線の連なり７４に近似する処理を行うものであり、図９に示した切断候補点データ作成装置４０中の近似処理部４１と兼用することができる。従って、閉曲線データ候補７３が第２実施例の如く原曲線を最小自乗法等により直線と円弧の連なりに近似する処理を利用して得られたものである場合は、この時の近似処理結果を再度利用できるので、近似処理部９１を閉曲線抽出装置９０から除外できる。
【０１８７】
形状検査部９２は近似処理結果から形状検査点を設定し、３個の連続した形状検査点毎に図４９に示した手順でベクトル外積Ｖ1 * ×Ｖ2 * を求め、その方向に変化が無いか否かを調べることにより凸形状検査をし、結果をデータ保存部９３に与える。
【０１８８】
データ保存部９３は閉曲線データ候補７３のうち、凸形状であると判定されたもののみを、特徴マッチングに適した閉曲線データとして保存する。
【０１８９】
（星形状の検査）
次に、星形状か否かの検査により閉曲線データ候補から閉曲線データを抽出する手法について説明する。
【０１９０】
先に述べた凸形状の検査による閉曲線抽出手法では、照明や汚れ等の影響で「穴」の形状が更に歪んでいると、凸形状と判定することができない場合がある。
【０１９１】
この歪があまりにも大きくなるとその閉曲線データは特徴マッチングに適さないが、「凸形状」には至らないまでも以下に述べる「星形状」の範囲内にあるならば、特徴マッチングに使用することができる。
【０１９２】
ここで、「星形状」とは、図５１（Ａ）に示すように曲線の重心Ｇとその曲線の外周上の或る一点Ｐとを結んだ直線が外周上の他の点と交わらないような性質を持つ形状を言う。図５１（Ｂ）の場合は交点があるので星形状ではない。
【０１９３】
従って、閉曲線データ候補が星形状であるか否かを検査し、星形状である場合には閉曲線データとして抽出することができる。
【０１９４】
星形状か否かの検査にも、前述した形状検査点（近似直線の両端点と、近似円弧の両端点及び中点）を利用すると便利である。この場合、連続した２つの形状検査点毎に、重心から始終点側のうち一方側の形状検査点へのベクトルと、重心から他方側の形状検査点へのベクトルとを考えて両ベクトルの外積をとると、星形状の曲線であれば外積の方向即ち符号は常に同じになり、星形状でなければ途中で符号（方向）が変化する。従って、外積の符号あるいは方向が変化しなければ星形状であり、閉曲線データとしてそのまま抽出することができる。
【０１９５】
以下、図５２〜図５４により、形状検査点を用いた星形状検査の具体例を説明する。
【０１９６】
予め、図５２〜図５３に×印で示すように、閉曲線データ候補点７３に、それの近似処理結果に基づいて形状検査点を設定しておく。
【０１９７】
図５４は星形状検査例のフローチャートを示し、Ｓ１１１〜Ｓ１２１のステップからなる。なお、本例ではステップＳ１１２，Ｓ１２０から判るように検査フラグとしてflagを導入し、検査により星形状でないと判明した段階で検査フラグflagをＹesからＮｏにリセットするものとしている。
【０１９８】
（Ｉ）まず、閉曲線データ候補７３の重心位置Ｇを求める（ステップＳ１１１）。
【０１９９】
（II）次に、検査フラグflagをＹesに設定し、形状検査点の最初例えば始点側の点を、点１と設定する（ステップＳ１１２）。
【０２００】
(III）次に、点１に続く形状検査点を点２と設定する（ステップＳ１１３）。
【０２０１】
（IV）この時、２つ目の形状検査点２が設定できたか否か判定し（ステップＳ１１４）、設定できない場合は処理を終了し（ステップＳ１２１）、設定できたならばステップＳ１１５に進む。
【０２０２】
（Ｖ）ステップＳ１１５では、重心Ｇから点１へのベクトルを求めてこれをＶ1 * と設定し、また重心Ｇから点２へのベクトルを求めてこれをＶ2 * として設定する。
【０２０３】
（VI）またステップＳ１１５では、両ベクトルの外積Ｖ1 * ×Ｖ2 * を計算し、その方向（符号）を求める。ここまでの様子を、図５２（Ａ），図５３（Ａ）に示す。
【０２０４】
(VII）次に、ステップＳ１１６で点１が形状検査点の始点か否かを判定し、始点であればステップＳ１１７に進み、そうでなければステップＳ１１８に進む。
【０２０５】
(VIII）点１が形状検査点の始点であれば、外積Ｖ1 * ×Ｖ2 * の方向が初めて得られたので、その符号を初期方向として設定し（ステップＳ１１７）、ステップＳ１１９に進む。
【０２０６】
（IX）点１が形状検査点の始点でなければ、既に初期方向が設定されているので、初期設定方向と今回求めた外積の方向とを比較し、一致すればステップＳ１１９に進み、不一致であればステップＳ１２０に進む。
【０２０７】
（Ｘ）ステップＳ１１９では、図５２（Ｂ），図５３（Ｂ）に示すように点１を今までの点２に設定し直し、ステップＳ１１３に戻って前記(III）項から手順を繰り返えす。その結果、図５２の場合は同図（Ｃ）に示すように外積Ｖ1 * ×Ｖ2 * の方向が最後まで初期方向と同じなので、この閉曲線データ候補７３は星形状と判定される。
【０２０８】
（XI）ステップＳ１２０では検査フラグflagをＮｏにリセットし、検査処理を終了する。図５３の場合は、同図（Ｃ）に示すように外積Ｖ1 * ×Ｖ2 * の方向が途中で初期設定方向から変化するので、星形状ではないと判定される。
【０２０９】
（装置構成例）
図５５に、星形状検査を適用した閉曲線抽出装置の構成例を示す。この閉曲線抽出装置９５は近似処理部９６と、星形状検査部９７と、データ保存部９８からなっている。
【０２１０】
近似処理部９６は閉曲線データ候補７３を直線と円弧の連なり７４に近似する処理を行うものであり、図９に示した切断候補点データ作成装置４０中の近似処理部４１と兼用することができる。従って、閉曲線データ候補７３が第２実施例の如く原曲線を最小自乗法等により直線と円弧の連なりに近似する処理を利用して得られたものである場合は、この時の近似処理結果を再度利用できるので、近似処理部９６を閉曲線抽出装置９５から除外できる。
【０２１１】
形状検査部９７は近似処理結果から形状検査点を設定し、重心と２個の連続した形状検査点毎に図５４に示した手順でベクトル外積Ｖ1 * ×Ｖ2 * を求め、その方向に変化が無いか否かを調べることにより星形状検査をし、結果をデータ保存部９８に与える。
【０２１２】
データ保存部９８は閉曲線データ候補７３のうち、星形状であると判定されたもののみを、特徴マッチングに適した閉曲線データとして保存する。
【０２１３】
（形状検査の組み合せ）
上述した如く曲線周囲長、近似円弧中心角、凸形状、星形状にそれぞれ着目した各種類の形状検査のいずれか１つを用いて閉曲線データ候補７３から閉曲線データを抽出することができるが、そのうちの２つ以上を組み合せて、例えばいずれかの形状検査に合格したものを閉曲線データとして抽出しても良い。このように２種類以上を組み合せることにより、閉曲線データ候補から特徴マッチングに適した閉曲線データを殆ど漏れなく抽出することができるようになる。
【０２１５】
【発明の効果】
本発明によれば、端部にノイズとして髭部分が付いている曲線データから、ノイズを除去した安定な完全閉曲線データもしくは略閉曲線データを抽出することができる。これにより、照明の加減や方向などの環境条件の影響、あるいは対象物体自体の汚れや傷等によりノイズがある場合でも、閉曲線データを安定に抽出することができ、実際の広範囲な作業状態における頑健で安定した特徴マッチングに大いに寄与する。
【図面の簡単な説明】
【図１】本発明の第１実施例に係る閉曲線抽出方法の手順を示すフローチャート。
【図２】完全閉曲線とそうでない曲線との例を示す図。
【図３】略閉曲線とそうでない単なる開曲線との例を示す図。
【図４】略閉曲線か否かの検査における外接長方形の設定例を示す図。
【図５】補完の例を示す図。
【図６】閉曲線抽出装置の構成例を示す図。
【図７】本発明の第２実施例に関し、原曲線データに対する直線と円弧による近似の例を示す図。
【図８】連続区間と切断始点、切断終点との関係を示す図。
【図９】切断候補点データ作成装置の構成例を示す図。
【図１０】切断候補点どうしによる狭部検出の例を示す図。
【図１１】切断候補点と直線による狭部検出の例を示す図。
【図１２】切断候補点どうしによる狭部検出を適用した閉曲線抽出方法の手順例を示す図。
【図１３】切断候補点の設定例を示す図。
【図１４】「tail」と「head」の初期データ設定例を示す図。
【図１５】対象区間探索処理例を示す図。
【図１６】閉曲線候補の検出例を示す図。
【図１７】略閉曲線検査処理の例を示す図。
【図１８】「tail」と「head」の初期データ再設定例を示す図。
【図１９】処理終了状態の例を示す図。
【図２０】閉曲線抽出装置の構成例を示す図。
【図２１】切断候補点を基準とした場合の切断候補点と直線切断候補点による狭部検出を適用した閉曲線抽出方法の手順例を示すフローチャート。
【図２２】切断候補点の設定例を示す図。
【図２３】「tail」と「head」の初期データ設定例を示す図。
【図２４】対象区間探索処理例を示す図。
【図２５】閉曲線候補の検出例を示す図。
【図２６】略閉曲線検査処理の例を示す図。
【図２７】処理終了状態の例を示す図。
【図２８】近似直線を基準とした場合の切断候補点と直線切断候補点による狭部検出を適用した閉曲線抽出方法の手順例を示すフローチャート。
【図２９】切断候補点の設定例を示す図。
【図３０】「tail」と「head」の初期データ設定例を示す図。
【図３１】対象区間探索処理例を示す図。
【図３２】閉曲線候補の検出例を示す図。
【図３３】略閉曲線検査処理の例を示す図。
【図３４】「tail」と「head」の初期データ再設定例を示す図。
【図３５】処理終了状態の例を示す図。
【図３６】閉曲線抽出装置の構成例を示す図。
【図３７】切断候補点どうしによる狭部検出と、切断候補点と直線による狭部検出とを組合せて適用した閉曲線抽出方法の手順例を示すフローチャート。
【図３８】図３８中のステップ７５の詳細を示すフローチャート。
【図３９】閉曲線抽出装置の構成例を示す図。
【図４０】原曲線上の一部分から閉曲線を抽出した例を示す図。
【図４１】本発明の第３実施例に係る閉曲線抽出方法の手順例を示す図。
【図４２】曲線周囲長による形状検査を適用した閉曲線抽出装置の構成例を示す図。
【図４３】形状検査点の設定例を示す図。
【図４４】中心角の大きな円弧の抽出例を示す図。
【図４５】円弧の円周角の検出例を示す図。
【図４６】円弧中心角検査を適用した閉曲線抽出装置の構成例を示す図。
【図４７】凸形状検査処理の例を示す図。
【図４８】凹部分が検出される例を示す図。
【図４９】凸形状検査処理の手順例を示すフローチャート。
【図５０】凸形状検査を適用した閉曲線抽出装置の構成例を示す図。
【図５１】星形状とそうでない曲線の例を示す図。
【図５２】星形状検査処理の例を示す図。
【図５３】非星形状曲線が検出される例を示す図。
【図５４】星形状検査処理の手順例を示すフローチャート。
【図５５】星形状検査を適用した閉曲線抽出装置の構成例を示す図。
【図５６】各種曲線の例を示す図。
【図５７】髭の付いた閉曲線の例を示す図。
【図５８】波打った閉曲線の例を示す図。
【符号の説明】
１  対象曲線データ
２  完全閉曲線データ
３  非完全閉曲線データ
４  略閉曲線データ
５  補完で得た完全閉曲線データ
６  単なる開曲線データ
７  長方形
８  直線
１０  閉曲線抽出装置
１１  完全閉曲線抽出部
１２  略閉曲線抽出部
１３  補完部
２０  原曲線データ
２１  一部分
２２  髭部分
２３  狭部
２４  連続区間
２５  切断始点
２６  切断終点
２７  閉曲線候補データ
２８  直線切断点
２９  連続区間（後半）
３０  近似線の連なり
３１  近似線
４０  切断候補点データ作成装置
４１  近似処理部
４２  端点データ抽出部
４３  データ設定部
５０  狭部検出装置
５１  距離計算部
５２  データ比較部
５３  検出結果
５５  狭部検出装置
５６  距離計算部
５７  データ比較部
５８  検出結果
５９  直線切断点データ
６０  閉曲線抽出装置
６１  切断候補点データ作成部
６２  狭部検出部
６３  閉曲線候補抽出部
６４  閉曲線検査部
６５  閉曲線データ保存部
６６  閉曲線候補データ
６７  検査結果
７０，７１  閉曲線データ
７２  波打ち部分
７３  閉曲線データ候補
７４  直線と円弧の連なり
７５  近似円弧
７６  原曲線のうち近似円弧に相当した部分
８０  閉曲線抽出装置
８１  形状検査部
８２  データ保存部
８５  閉曲線抽出装置
８６  近似処理部
８７  円周角計算部
８８  中心角比較部
８９  データ保存部
９０  閉曲線抽出装置
９１  近似処理部
９２  凸形状検査部
９３  データ保存部
９５  閉曲線抽出装置
９６  近似処理部
９７  星形状検査部
９８  データ保存部
【図１】
0003695442.tif 000003
【図２】
0003695442.tif 000004
【図３】
0003695442.tif 000005
【図４】
0003695442.tif 000006
【図５】
0003695442.tif 000007
【図６】
0003695442.tif 000008
【図７】
0003695442.tif 000009
【図８】
0003695442.tif 000010
【図９】
0003695442.tif 000011
【図１０】
0003695442.tif 000012
【図１１】
0003695442.tif 000013
【図１２】
0003695442.tif 000014
【図１３】
0003695442.tif 000015
【図１４】
0003695442.tif 000016
【図１５】
0003695442.tif 000017
【図１６】
0003695442.tif 000018
【図１７】
0003695442.tif 000019
【図１８】
0003695442.tif 000020
【図１９】
0003695442.tif 000021
【図２０】
0003695442.tif 000022
【図２１】
0003695442.tif 000023
【図２２】
0003695442.tif 000024
【図２３】
0003695442.tif 000025
【図２４】
0003695442.tif 000026
【図２５】
0003695442.tif 000027
【図２６】
0003695442.tif 000028
【図２７】
0003695442.tif 000029
【図２８】
0003695442.tif 000030
【図２９】
0003695442.tif 000031
【図３０】
0003695442.tif 000032
【図３１】
0003695442.tif 000033
【図３２】
0003695442.tif 000034
【図３３】
0003695442.tif 000035
【図３４】
0003695442.tif 000036
【図３５】
0003695442.tif 000037
【図３６】
0003695442.tif 000038
【図３７】
0003695442.tif 000039
【図３８】
0003695442.tif 000040
【図３９】
0003695442.tif 000041
【図４０】
0003695442.tif 000042
【図４１】
0003695442.tif 000043
【図４２】
0003695442.tif 000044
【図４３】
0003695442.tif 000045
【図４４】
0003695442.tif 000046
【図４５】
0003695442.tif 000047
【図４６】
0003695442.tif 000048
【図４７】
0003695442.tif 000049
【図４８】
0003695442.tif 000050
【図４９】
0003695442.tif 000051
【図５０】
0003695442.tif 000052
【図５１】
0003695442.tif 000053
【図５２】
0003695442.tif 000054
【図５３】
0003695442.tif 000055
【図５４】
0003695442.tif 000056
【図５５】
0003695442.tif 000057
【図５６】
0003695442.tif 000058
【図５７】
0003695442.tif 000059
【図５８】
0003695442.tif 000060