(57)【要約】【課題】任意の輪郭線を有する物体であっても、信頼性よく、しかも頑健な形状認識を可能にする。【解決手段】撮像された物体の画像の輪郭線上の点が検出され、該輪郭線が検出された各点Ｑ0Ｑ1．．．．．Ｑnを頂点として直線で結んだ折れ線として抽出される。２頂点を結ぶ直線Ｑ0Ｑnが予め定められた分解長さΓ（ａ＋ａ）となる区間を検査区間として、この検査区間を複数に分割して得られる各区間（ａ）で折れ線図形の面積Σ0、Σ1が計算される。そして、計算された面積に基づいてその検査区間での折れ線図形が直線、円弧あるいは擬似円弧などの基本図形として出力される。このような構成では、基本図形が高精度で抽出でき、擬似円弧を含む基本図形を用いたパターンマッチングによる物体の認識精度を向上させることができる。また、分解長さΓを変えることにより、物体の特徴量を増加させて頑健な物体認識を行うことができる。【選択図】図７
2008084237.tif 000002
【特許請求の範囲】
【請求項１】
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出する物体の輪郭線抽出方法であって、
折れ線の２頂点を結ぶ距離が予め定められた長さとなる区間を検査区間として、この検査区間を複数に分割して得られる各区間で折れ線図形の面積を計算し、
計算された面積に基づいて前記検査区間での折れ線図形を分類し、
前記検査区間での折れ線を前記分類された図形として出力することを特徴とする物体の輪郭線抽出方法。
【請求項２】
分割された前半と後半の区間での面積の和の絶対値を所定の値と比較することにより前記検査区間での折れ線が直線として分類できるかどうかを判定することを特徴とする請求項１に記載の物体の輪郭線抽出方法。
【請求項３】
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出する物体の輪郭線抽出装置であって、
折れ線の２頂点を結ぶ距離が予め定められた長さとなる区間を検査区間として、この検査区間を複数に分割して得られる各区間で折れ線図形の面積を計算する計算手段と、
計算された面積に基づいて前記検査区間での折れ線図形を分類する分類手段と、
前記検査区間での折れ線を前記分類された図形として出力する出力手段と、
を有することを特徴とする物体の輪郭線抽出装置。
【請求項４】
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出し、抽出した輪郭線を物体の学習輪郭線と照合して物体を認識する物体認識方法であって、
輪郭線を構成する折れ線の２頂点を結ぶ距離が所定長さとなる区間並びに該所定長さを変化させて得られる区間の各区間ごとに各区間での折れ線図形を基本図形として出力し、
出力された各基本図形から基本図形の組み合わせ集合を生成し、
前記生成された基本図形の組み合わせ集合と、予め学習された物体の基本図形の組み合わせ集合とを照合することにより物体を認識することを特徴とする物体認識方法。
【請求項５】
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出し、抽出した輪郭線を物体の学習輪郭線と照合して物体を認識する物体認識装置であって、
輪郭線を構成する折れ線の２頂点を結ぶ距離が所定長さとなる区間並びに該所定長さを変化させて得られる区間の各区間ごとに各区間での折れ線図形を基本図形として出力する出力手段と、
出力された各基本図形から基本図形の組み合わせ集合を生成する生成手段とを備え、
前記生成された基本図形の組み合わせ集合と、予め学習された物体の基本図形の組み合わせ集合とを照合することにより物体を認識することを特徴とする物体認識装置。
【請求項６】
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出し、抽出した輪郭線を物体の学習輪郭線と照合して物体を認識する物体認識方法であって、
輪郭線を構成する折れ線の２頂点を結ぶ距離が所定長さとなる区間ごとに各区間での折れ線図形を擬似円弧を含む基本図形として出力し、
出力された基本図形から基本図形の組み合わせを生成し、
前記生成された基本図形の組み合わせの相対的位置関係を物体の特徴データとして記述し、
前記基本図形の組み合わせと、その組み合わせの特徴データに対応する特徴データをもつ予め学習された基本図形の組み合わせとを順次照合することにより物体を認識することを特徴とする物体認識方法。
【請求項７】
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出し、抽出した輪郭線を物体の学習輪郭線と照合して物体を認識する物体認識装置であって、
輪郭線を構成する折れ線の２頂点を結ぶ距離が所定長さとなる区間ごとに各区間での折れ線図形を擬似円弧を含む基本図形として出力する出力手段と、
出力された基本図形から基本図形の組み合わせを生成する生成手段とを有し、
前記生成された基本図形の組み合わせの相対的位置関係を物体の特徴データとして記述し、
前記基本図形の組み合わせと、その組み合わせの特徴データに対応する特徴データをもつ予め学習された基本図形の組み合わせとを順次照合することにより物体を認識することを特徴とする物体認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出する物体の輪郭線抽出方法および装置、並びにこの抽出された輪郭線を学習した輪郭線と照合してパターンマッチングにより物体の位置、姿勢、形状などを認識する物体認識方法および装置に関する。
【背景技術】
【０００２】
従来から、認識すべき物体をＣＣＤカメラなどで撮像し、撮像された物体の画像を処理して物体の輪郭線を抽出し、その輪郭線を使用して物体の位置、姿勢、形状を認識することが行われている。図１と図２は輪郭線を使った画像による物体認識の例を示すものである。
【０００３】
図１は物体の学習場面を示すものであって、認識すべき物体２が不図示のカメラにより撮像され、画像処理装置に入力された画像１が入力画像として図示されている。認識物体２には固有の座標系であるところのＵＶ座標系が張り付いている。学習では物体の輪郭線３を抽出し、そこから特徴を抽出し、学習データ、つまり物体のモデルデータ（参照データ）として記憶する。このとき学習データはＵＶ座標系で記述される。
【０００４】
図２は物体の認識場面を示すものであって、画像内に認識すべき物体がある。画像内の輪郭線を抽出し、そこから特徴を抽出したのち図１で記憶した学習データの特徴と照合する。認識の出力結果は画像の座標系であるＸＹ座標系における、ＵＶ座標系の倍率、角度および平行移動量（Ｘ，Ｙ）である。
【０００５】
上述した物体の認識において、まず画像から輪郭線が抽出されるが、輪郭線を抽出する方法に関しては種々のアルゴリズムが知られている。
【０００６】
例えば、特許文献１には、画像の各点で明度の変化方向を示すところの勾配ベクトルを計算し、輪郭線は勾配ベクトルの大きさが最も大きい位置にあると仮定して、大きい勾配ベクトルを追跡して輪郭線を抽出する方法が記載されている。
【０００７】
また、特許文献２には、画像を細線化する処理、すなわち幅が２画素以上の線を幅が１画素の線にする技術により中心線の軌跡を追跡し画像の輪郭線を抽出する方法が記載されており、この方法は、特に物体が線画のときに有効な方法である。
【０００８】
また、特許文献３には、例えば図１において符号４で示すような巻貝と呼ぶ渦巻き状の図形を画像内に多数発生させ、渦巻きごとに内部を通過する輪郭線を獲得し、その後画像全体で合体して輪郭線を抽出する方法が記載されている。
【０００９】
その他にも種々輪郭線を抽出する方法が知られているが、いずれの方法でも、一般に画像からは何本かの輪郭線が抽出され、抽出された輪郭線は図１の点列５で示すように複数の座標の点列を結ぶ直線、すなわち折れ線として記述される。
【００１０】
そして、抽出した輪郭線から得られるパターンと認識用のパターンとのパターンマッチングにより物体認識が行われる。このとき、パターンマッチングの中でも、幾何学的パターンマッチングは最も洗練された方式のひとつである。これは輪郭線同士を直接照合するのではなく、輪郭線をいったん直線部、円弧部などの幾何学図形（基本図形）に分解し、物体を幾何学図形の集合として学習し、同時に認識に使うものである。
【００１１】
そのため、与えられた輪郭線から直線部や円弧部を検出する方法がこれまで数多く提案されてきており、特許文献４に記載された直線部の検出では、例えば、図３において頂点Ｐ0から出発し、現在頂点Ｐnまで来たとき、頂点Ｐ0とＰnを結ぶ直線への頂点Ｐ0からＰnの各頂点からの距離の最大距離２１が許容値以内であればＰ0Ｐnが依然直線部であるとして、最大距離を監視する方法が用いられている。
【００１２】
また、特許文献６に記載された直線部の検出では、例えば図３において適当な辺２２から出発し、その両端の頂点について、差し違いに反対側の頂点と結んだ線分との距離２３と２４に着目し、その小さい方の側の頂点をその方向にひとつ進めることを繰り返して行い、いずれの距離も許容値以内であれば依然直線部であるとして最大および最小距離を監視する方法が用いられている。
【００１３】
また、特許文献７には、例えば図３において頂点Ｐ0から出発し、現在頂点Ｐnまで来たとき、所与の規則で決められる中間の頂点２５を次の限界頂点と呼び、Ｐ0と限界頂点を結ぶ直線（図示しない）を境界として限界角度領域２６を設けて次のＰn+1の判定を行い、もしＰn+1がこの領域を超えた場合、Ｐ0から限界頂点２５までを直線部として出力する角度監視方法が記載されている。
【００１４】
一方、輪郭線から円弧部を検出方法として、先の特許文献１には、図３においてＰ0から出発し、ベクトル２７の開き角度２８（近傍点列をならした接線方向から測る）が一定であるかぎり頂点を進め、ベクトル列の角度変化を監視する方法が記載されている。
【００１５】
また、特許文献５には、例えば図３においてＰ0からＰnまでの頂点列を、あらかじめ記憶している半径の異なる何個かの円弧パターン列（図示しない）と比較するもので、円弧と判定されればその中心と半径を即座に求めることができる方法が記載されている。
【００１６】
一方、直線や円弧を使った幾何学的パターンマッチングの方法も数多く提案されており、例えば先にあげた特許文献１には、直線、円弧、楕円、双曲線、放物線、および四角形を基本図形として採用し、これらの集合から取り出した組み合わせについて幾何学的関係を抽出し、学習モデルと照合を行って、ある組み合わせが一致したら、ただちに全体が一致するかどうかの照合に移行する方法が示されている。このパターンマッチングのために必要な莫大な計算量を得るために、特許文献１ではニューラル・ネットワークが用いられている。
【００１７】
また、先にあげた特許文献６による方法では、対象物体を輪郭線が直線の物体に限定し、直線だけを基本図形として採用し、空間的に連続するすなわちひとつながりの３本の直線分が学習モデルと一致したら、直線分の範囲をその前後に徐々に広げて照合を行っている。
【００１８】
更に、特許文献８では、対象物体を輪郭線のほとんどを直線の物体に限定し、直線だけを基本図形として採用し、輪郭線上の各点について、その接線方向から決まる局所座標系を設け、その座標系で記述した他の点群からハフ変換により直線群を生成し、その中から適当に選んだ複数個の組み合わせの幾何学的位置関係をハッシュ関数の入力としてマッチングを行う幾何学的ハッシング技術が用いられている。
【特許文献１】特許第２８８５８２３号
【特許文献２】特開平５−２５０４０９
【特許文献３】特開２００１−２５１０９７
【特許文献４】特開昭６２−３２５８４
【特許文献５】特開昭６２−３８９９０
【特許文献６】特開昭６３−１４３６８１
【特許文献７】特開平１−２３１１８３
【特許文献８】特開２００５−１７４０６２
【発明の開示】
【発明が解決しようとする課題】
【００１９】
上述したように、幾何学的パターンマッチングによる物体認識には、抽出した輪郭線から直線、円弧を検出し基本図形に分解することが行われる。しかしながら、従来では、直線や円弧の検出方法に問題がある。
【００２０】
まず、第一に輪郭線の緩やかな円弧または円弧状の区間が誤って直線として検出されるという欠点がある。たとえば図１における区間６は実際は緩やかな円弧状の区間であるが、従来方式ではここを直線として検出しやすい。また、図３において、Ｐ0Ｐn間は円弧状の区間であって明らかに直線ではない。しかしながら、特許文献４、６、７に記載された方法では、いずれも設定した許容値が大きいときこの区間が直線部として認められることになる。一方で、この許容値をむやみに小さくするわけにはいかない。なぜならば一般に輪郭線として抽出された座標列には必ず量子化誤差が入っているので、もともと点列はジグザグであり、さらに輪郭線自体が不明瞭のときはその変動がいっそう激しくなるからである。従って、直線部を安定して検出できるためには一定の大きさの許容値が必要である。
【００２１】
第二に、輪郭線のある区間が明らかに直線状であるが、その起伏が激しいとき、直線として検出されないという欠点がある。たとえば図４（ａ）において、Ｐ0Ｐn間は起伏が激しいが明らかに直線部であるが、特許文献４、６、７の方法では、いずれも設定した許容値が小さいときこの区間が直線部として認識されない。このとき、この許容値をむやみに大きくするわけにはいかない。なぜならば大きくすればするほど今度は円弧などの非直線形状を直線と誤認してしまうからである。
【００２２】
以上、第一と第二として述べた直線検出に関する欠点は共通して、直線との誤差量を頂点局所の距離または角度だけで判定していること、言い換えれば誤差の瞬間量だけを測っていることに起因している。
【００２３】
第三に、従来の方法では、輪郭線の非円弧の区間が誤って円弧として検出されるという欠点がある。たとえば放物線の部分弧が円弧ではないことは明白であるが、これは円弧として誤認しやすい。例えば、特許文献１の方法では、頂点ごとにベクトルの開き角度を検査するだけであるから、緩やかに変化する曲線の場合、いずれの角度も合格してしまうことになり誤認識してしまうので問題である。
【００２４】
第四に、輪郭線の円弧の区間が円弧として検出されないという欠点がある。たとえば図１の区間７は実際は円弧であるが、従来ではここを円弧として検出できないことがある。すなわち、もしこの区間の起伏が激しいとき、特許文献５による方法では、テンプレート円弧との誤差が許容値を超えてしまうかもしれないので、少しの起伏あるいは突発的な異常点があっても中心軌跡が円弧であれば円弧として抽出できることが望ましい。
【００２５】
以上、第三と第四として述べた円弧検出に関する欠点は、直線検出の場合と同様な欠点である。
【００２６】
また、第五の問題点として、輪郭線の緩やかな円弧または円弧状の区間がそのままの形状として検出されないという、輪郭線の表現力上の欠点がある。この問題は第一および第三として述べた問題の裏返しでもある。
【００２７】
たとえば、図１における区間６は実際は緩やかな円弧もしくは円弧状の区間である。しかし従来方式のことごとくがこの区間を正確に表現できないという問題がある。区間６を直線と認識すると、それは明らかに誤りであり、のちの照合に問題が生じる恐れがある。一方円弧と認識すると、直線と認識するよりは好ましいが、ほとんど直線に近い区間を内部でどのように円弧として表現するかが問題となる。すなわち半径の極めて大きな円があるとき、その一部である円弧の情報から、もとの円の中心と半径を正確に求めることは難しいのであって、仮に数学的に演算し得たとしても誤差を大量に含んでいるはずであり、その結果、のちの照合で誤認識となってしまう。従って、輪郭線の緩やかな区間は、直線でも円弧でもなくて、形状そのままの形で、例えばスプライン曲線で表現することが望ましい。
【００２８】
第六に、一般の物体すなわち輪郭線が直線だけでなく、任意の曲線も交えて構成される物体の輪郭線について、従来の直線と円だけでは不十分であるという問題がある。すなわち図１はまさにそのような任意曲線物体の例であり、確かに直線と円だけでは記述しきれない輪郭線をもった物体である。しかし、むやみに長い任意の区間（たとえばＰ1〜Ｐ2）をスプライン曲線で表現したところで得るものは少なく、図１に示す物体は、その形状が複雑すぎて他の図形との関係を記述することが困難な物体である。従って、例えば図９に示すように、抽出された輪郭線が直線Ｐ0Ｐnの左右いずれか一方に張り出した緩やかな弧である場合、円弧とは別に、円弧に類似の、しかし新しい形状概念が必要になる。
【００２９】
最後に、第七の問題としてパターンマッチングに関した問題がある。これは、幾何学的パターンマッチングの根幹に関わる問題である。すなわち画像による物体認識の現場においては、認識画像の中に学習時の物体像がそのまま同じ条件で出現するとは限らない。すなわちサイズが大きく変化、たとえば２．０倍〜０．５倍もの範囲で、前触れもなく変化した物体を認識しなければならないことがある（サイズ変動）。あるいは形状の一部が変形した物体（たとえば図２の位置１０、１１）を認識しなければならないことがある（一部変形）。あるいは物体の一部が他の物体（図２の１２）により隠された状況で認識しなければならないことがある（一部隠蔽）。
【００３０】
これらの障害は同時に起こりうるので、認識の頑健性（ロバスト性）を高めることが必要であることは言うまでもないが、認識の頑健性の観点から見ると、従来の方式は特にサイズ変動に対して弱いという問題がある。
【００３１】
すなわち、特許文献１の方法ではサイズ変動の対策がなく、たとえば学習時には円弧（図１の円弧７）の場合、大きいサイズの物体を認識するときは、図２に示したように直線１３として検出されるかもしれず、その場合照合はできないことになる。
【００３２】
また、特許文献６の方法では直線だけを使うので、サイズ変動の問題は緩和されているものの、学習時のサイズに対して認識時のサイズが小さいときに問題が発生する。例えば、学習時には直線２本（図２を学習画像として直線１４）であるが、認識時には直線１本（図１を認識画像として直線８）として検出されるかもしれず、その場合連続する直線の順序が崩れ照合が困難になる。
【００３３】
一方、特許文献８はすべてに頑健で優れた方式であるが、対象物体を輪郭線のほとんどが直線の物体に限定していることが問題である。公知の幾何学的ハッシングは本質的にサイズ変動、一部変形と一部隠蔽に強い特徴をもつので、対象を任意の曲線形状に拡大することが求められる。
【００３４】
本発明は、以上の問題点を解決するためになされたもので、任意の輪郭線を有する物体であっても、信頼性よく、しかも頑健な形状認識を可能にする物体の輪郭線抽出方法および装置、並びにこれを用いた物体認識方法および装置を提供することを課題とする。
【課題を解決するための手段】
【００３５】
本発明（請求項１、３）は、
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出する物体の輪郭線抽出方法および装置であって、
折れ線の２頂点を結ぶ距離が予め定められた長さとなる区間を検査区間として、この検査区間を複数に分割して得られる各区間で折れ線図形の面積を計算すること、
計算された面積に基づいて前記検査区間での折れ線図形を分類すること、
前記検査区間での折れ線を前記分類された図形として出力することを特徴とする。
【００３６】
また、本発明（請求項４、５）は、
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出し、抽出した輪郭線を物体の学習輪郭線と照合して物体を認識する物体認識方法および装置であって、
輪郭線を構成する折れ線の２頂点を結ぶ距離が所定長さとなる区間並びに該所定長さを変化させて得られる区間の各区間ごとに各区間での折れ線図形を基本図形として出力すること、
出力された各基本図形から基本図形の組み合わせ集合を生成すること、
前記生成された基本図形の組み合わせ集合と、予め学習された物体の基本図形の組み合わせ集合とを照合することにより物体を認識することを特徴とする。
【００３７】
また、本発明（請求項６、７）は、
撮像された物体の画像の輪郭線上の点を検出し、該輪郭線を検出された各点を頂点として直線で結んだ折れ線として抽出し、抽出した輪郭線を物体の学習輪郭線と照合して物体を認識する物体認識方法および装置であって、
輪郭線を構成する折れ線の２頂点を結ぶ距離が所定長さとなる区間ごとに各区間での折れ線図形を擬似円弧を含む基本図形として出力すること、
出力された基本図形から基本図形の組み合わせを生成すること、
前記生成された基本図形の組み合わせの相対的位置関係を物体の特徴データとして記述すること、
前記基本図形の組み合わせと、その組み合わせの特徴データに対応する特徴データをもつ予め学習された基本図形の組み合わせとを順次照合することにより物体を認識することを特徴とする。
【発明の効果】
【００３８】
本発明では、折れ線の２頂点を結ぶ距離が予め定められた長さ（折れ線分解長）となる区間を検査区間として、この検査区間での折れ線図形の面積を、検査区間を複数に分割して得られる各区間で計算し、計算された面積に基づいて前記検査区間での折れ線図形を分類するようにしているので、基本図形である直線、円弧などの基本図形を高精度で抽出することができる。
【００３９】
また、本発明では、スプライン曲線として記述できる擬似円弧が基本図形として抽出でき、この擬似円弧が、他の直線、円弧などの基本図形との位置関係を記述しやすい性質を持っているので、擬似円弧を含む基本図形を用いた幾何学的パターンマッチングの精度を向上させることができる。
【００４０】
また、本発明では、折れ線分解長Γを種々に変化させて物体の特徴を抽出しているので、特徴の情報量が多くなり、物体の認識時のサイズ変動が大きい場合でも、高精度なパターンマッチングを行うことができる。
【発明を実施するための最良の形態】
【００４１】
以下、図面に示す実施例に基づいて本発明を詳細に説明する。
【実施例】
【００４２】
＜全体の構成＞
図５は本発明の一実施例を示す物体認識装置の構成を示すブロック図である。
【００４３】
同図において、制御部１００は本発明により物体を学習並びに認識するときの全体を制御するもので、物体を撮像し、物体モデルのデータベースの中からひとつを選び、その物体モデルと撮像された物体の画像を照合して物体認識を行い、その認識データにより装置を駆動するときの流れを制御する。
【００４４】
画像入力部１０１は、照明光源１０３により照明された物体１０４をテレビカメラ、ＣＣＤカメラなどの撮像装置１０２により撮像し、その撮像された画像を画像入力部１０１内の画像メモリ（不図示）に取り込む。
【００４５】
物体学習部１０５は、撮像された物体の画像から学習データを生成し物体モデルのデータベース１０７に格納する。
【００４６】
物体認識部１０６は、認識すべき物体の画像と、データベースに格納されている学習物体の画像とを照合（パターンマッチング）し、物体の認識、つまり物体の位置、形状、姿勢などを検出する。
【００４７】
画像輪郭線抽出部１０８は、撮像された画像から点列として構成される輪郭線を抽出し輪郭線の集合を生成する。
【００４８】
折れ線分解部１０９は、画像輪郭線抽出部１０８で抽出された複数の頂点列を結ぶ１本の折れ線を、与えられた折れ線分解長により分解する。
【００４９】
面積計算回路１１０は輪郭線（折れ線）を入力として定められた数種の図形の面積計算を実行する。
【００５０】
３図形選択部１１１は図形の集合から３個の図形の組み合わせを選び出す。
【００５１】
３図形分類・特徴量抽出部１１２は３個の図形の配置の型を分類し、その特徴パラメータを生成する。
【００５２】
スプライン曲線発生回路１１３は平面の点列を滑らかに結ぶ曲線の補間点列を発生する。
【００５３】
ハッシュ関数回路１１４は特徴パラメータを入力としてハッシュ表への指標（インデクス）を生成する。
【００５４】
上述した構成で、認識すべき物体が図１に示されたような物体２である場合、画像入力部１０１は物体２を撮像し、その画像を画像メモリに格納する。画像輪郭線抽出部１０８は画像メモリに格納された物体２の画像を処理して物体２の輪郭線３を抽出する。この輪郭線の抽出には、特許文献１〜３に記載されているような方法を用いることができ、輪郭線は、物体の画像処理により物体の輪郭線上の点（以下、頂点という）が抽出され、抽出された各頂点を直線で結ぶ折れ線として抽出される。
【００５５】
＜折れ線の分解＞
折れ線分解部１０９は、画像輪郭線抽出部１０８で抽出された輪郭線を構成する折れ線を、図６に示す流れに沿って分解する。
【００５６】
今、画像輪郭線抽出部１０８で抽出された輪郭線が、図３に示したような頂点Ｐ0、．．．．Ｐn+1の各点を直線で結ぶ折れ線として記述されるものとする。
【００５７】
折れ線分解部１０９は、現在点Ｐcを折れ線頂点の先頭に合わせ（ステップＳ１）、ステップＳ２で、現在点Ｐcが折れ線の頂点であるかどうかが判断され、折れ線の頂点と判断されれば、以下の処理が行われる。
【００５８】
ステップＳ３では、現在点Ｐcから頂点を先に進めて、直線距離が折れ線分解長Γ以上となる最初の頂点Ｐeを探す。折れ線分解長Γは、２つの頂点の直線距離で、その直線距離以上となると、一つの折れ線とすることを断念する長さで、図１の右側に示したように、物体に応じてΓ0、Γ1、、等が予め定められる。また、後述するように、この折れ線分解長Γは、分解長Γとなる２頂点間の折れ線図形を調べるための検査区間となる。
【００５９】
図３において、現在点ＰcはＰ0にあるので、Ｐ0＝Ｐcであり、Ｐcからの直線距離が最初にΓ以上となる頂点Ｐn（Ｐ0からｎ番目の頂点）がＰeであるので、Ｐn＝Ｐeとなる。そして、図７に示したように、Ｐ0を原点とし、Ｐ0Ｐnの方向を主軸とする直交座標系（ΨΩ座標系）を張る。Ｐ0が原点Ｑ0＝（０，０）に対応し、ＰnがＱnに対応している。座標列Ｑ1、Ｑ2、．．はもとの座標列Ｐ1、Ｐ2、．．をΨΩ座標系に変換したものである。λはサンプリング間隔であり、所定の値、たとえば経験的には、λ＝１画素のサイズ（ピクセルレート）に設定される。なお、図７の折れ線の形状は説明の都合上図３の折れ線の形状とは異なっている。この折れ線の形状は、同様に他の図においても説明の都合上それぞれ相違して表現されている。
【００６０】
ステップＳ６では、面積計算回路１１０により以下の面積計算が実行される。
【００６１】
今、図７においてａ＝Ｑn／２とすれば、前半区間を、ｋ＝ａ／λ（整数）により、ｋ等分し、面積Σ0＝λ（ｑ1 +ｑ2 + ．．．+ qk）を求める。ここで各ｑiは頂点座標の補間値であって、符号付である。符号は、頂点が直線Ｑ0Ｑnより上に位置する場合には正の符号を、また下に位置する場合には逆符号とする。補間は qkで示すように、座標ＱiＱjを比例配分した座標Ｚを求めればよい。
【００６２】
次に後半区間を前半と同じ数すなわちｋ等分し、面積Σ1＝λ（ｑk +ｑk+1+ ．．．+ q2k-1）を求める。このとき中央値ｑkに係る面積が、面積Σ0、Σ1のどちらにも現れるが、各頂点を結ぶ図形全体の面積＝Σ0＋Σ１であり、ここで、重なったｑkに関する面積１個分を取り除かないようにする。
【００６３】
次に、図８に示したように、Ｑ0とＺを結んで新しい主軸を設定し、この部分弧について、面積Σ00、Σ01を求める。求め方はΣ0、Σ１のときと全く同じである。同様に、ＺとＱnを結んで新しい主軸を設定し、面積Σ10、Σ11、を求める。
【００６４】
このようにして求められた面積から、分解長Γで分解された折れ線の図形、すなわち検査区間での折れ線図形の種別が判定される。ステップＳ７〜Ｓ１０は直線（Ｌ）であるかどうかの判定ロジックである。
【００６５】
まず直線であるためには分解長Γとなっている２頂点（Ｐ0Ｐe）間の折れ線部分とその２頂点を結ぶ直線が形成する図形全体の符号付面積であるΣ0＋Σ１について、｜Σ0＋Σ１｜≦σ１（ステップＳ８）であることが必要である。ただしσ１は定数である。σ１が小さいほど直線の度合いが増す。σ１は適当な値でよいが、本実施例においては直線を認識のための基本図形として使うので、可能な限り真の直線を出力すべく、σ１＝３＊（δの２乗）とした。ただしδは図１の輪郭線２の抽出された点列５の平均間隔である。またこの式の係数３は経験値である。
【００６６】
ここでσ１が検出区間の長さに依存しない量であることに付言しておく。すなわち図４（ａ）に示すように真の直線であるかぎり、検出区間がいくら長くても｜Σ0＋Σ１｜は大きくならないはずである。
【００６７】
次に、直線であるためには、｜Σ00＋Σ01｜≦σ１、かつ｜Σ10＋Σ11｜≦σ１、であることが必要である（ステップＳ８、Ｓ９）。
【００６８】
たとえば、図１０には直線として出力できる折れ線が図示されており、同図においてＰ0Ｐnを結ぶ直線４４の中点での中間線４０の補間座標Ｐzの高さをｂとする。ステップＳ７での｜Σ0＋Σ１｜≦σ１により、頂点列はすでに中間線４０を境に前後の面積が釣り合っている状態である。さらに、今回の｜Σ00＋Σ01｜≦σ１の条件により、Ｐ0Ｐzを結ぶ直線４２についてもその中間線４３を境に同じ状況である。同様に、｜Σ10＋Σ11｜≦σ１により後半でもおなじ状況である。
【００６９】
また、図４の（ａ）、（ｂ）に示す図形も上記３個の面積条件を満たしている。従ってこれらは直線である。特に図４（ｂ）のように周期的に振動する区間を直線として生成できるのも上記面積による判定方式の利点である。
【００７０】
以上、ステップＳ７〜Ｓ９での３個の面積条件を満足したならば、頂点Ｐ0Ｐnの検査区間での折れ線図形は直線であると判定して直線４４を出力する（ステップＳ１０）。
【００７１】
続く、ステップＳ１１〜Ｓ２３は円弧（Ｃ）と擬似円弧（Ｒ）の判定ロジックである。円弧も擬似円弧も途中のステップＳ１７までは共通である。
【００７２】
ステップＳ１１は、図９において、軸Ｐ0Ｐnに関して、左側あるいは右側に大きく偏った頂点列を要求するものである。すなわち、図８で示すように主軸の両側に振られた頂点列Ｑ0Ｑnはここで排除される。輪郭線が滑らかな凸形状の場合、面積の符号は折れ線の頂点列が進む方向で決まる。すなわち図９の区間Ｐ0Ｐnは滑らかな凸形状であるが、図９で示す矢印の向きの場合、Σ0、Σ１、Σ00、Σ01、Σ10、Σ11、のすべてが正である。矢印と逆方向に進む場合、Σ0、Σ１、Σ00、Σ01、Σ10、Σ11のすべてが負である。従って検査区間の折れ線が擬似円弧と判定するためには、（Σ0×Σ１）の符号が正であることが必要である。
【００７３】
ステップＳ１２は、区間Ｐ0Ｐnの前半の弧と後半の弧がともに局所面積条件を満たすことを要求している。例えば、図９において頂点Ｐ0とＰnを結ぶ直線の中点Ｈ0に立てた垂線と弧との交点をＴ0とし、またＰ0、Ｐnにそれぞれ立てた垂線と、Ｔ0を通る直線Ｈ0Ｔ0に対する垂直線との交点をそれぞれＡ0、Ｂ0として、前半の区間Ｐ0Ｈ0での弧Ｐ0Ｔ0について、その面積｜Σ0｜が三角形Ｐ0Ｈ0Ｔ0より大きく、かつ長方形Ｐ0Ｈ0Ｔ0Ａ0より小さいとき、その弧が局所面積条件を満たしているという。後半の区間Ｈ0Ｐnでの弧Ｔ0Ｐnについても、その面積｜Σ1｜は三角形ＰnＨ0Ｔ0より大きく、かつ長方形ＰnＨ0Ｔ0Ｂ0より小さいので、その弧は局所面積条件を満たしている。しかし、例えば、同図で弧Ｐ0´Ｐnは局所面積条件を満たさない例である。
【００７４】
以降のステップＳ１３〜Ｓ１６までは、前半の弧の２分の１弧、後半の弧の２分の１弧、のいずれについても、弧が凸形状であり、かつ局所面積条件を満たすことを要求している。
【００７５】
次に、ステップＳ１７において｜Σ0｜と｜Σ１｜の大きさを比較してほぼ等しいかどうかが判定される。判定方法は、ζ＝ＭＩＮ｛｜Σ0｜，｜Σ１｜｝／ＭＡＸ｛｜Σ0｜，｜Σ１｜｝を計算し、たとえばζ≧０．９５ならば等しいと判定する。
【００７６】
続く、ステップＳ１８においてｂ／ａの大きさを判定する。ここで、ｂは図１１に示すように、直線Ｐ0Ｐnの中点に立てた垂線と折れ線との交点をＰzとして該中点とＰzとを結ぶ直線距離であり、直線ＰoＰnと直線Ｐ0Ｐzがなす角度をαとしてｂ／ａ＝ｔａｎαである。この値ｂ／ａが小さいときは従来技術で問題となっていた、いわゆる緩やかな円弧である。ｂ／ａ＜α１のとき弧Ｐ0Ｐnを擬似円弧として出力する。定数α１は適当に決めてよいが、たとえばα１＝０．０３５（α＝2度）とする。なお、擬似円弧の記述方式については後述する。ここで擬似円弧を出力したならばステップＳ２４に行く。
【００７７】
続くステップＳ２０において、弧Ｐ0Ｐnが円弧であるかどうかが判定される。図１１において、Ｐ0Ｐnを通過する円４５を描くことができる。この円の弦の長さが２ａ、弦の高さがｂであるならば、弦Ｐ0Ｐnが切り取る円の面積の半分であるΛは、
【００７８】
【数１】
2008084237.tif 000003
【００７９】
ただし、
【００８０】
【数２】
2008084237.tif 000004
【００８１】
である。
【００８２】
従って、｜Σ0｜（＝｜Σ１｜）とΛの大きさを比較してほぼ等しいかどうかを判定する。判定方法はζ＝ＭＩＮ｛｜Σ0｜，Λ｝／ＭＡＸ｛｜Σ0｜，Λ｝を計算し、たとえばζ≧０．９５ならば等しいと判定する。等しいと判定されたときは弧Ｐ0Ｐnを円弧（Ｃ）として出力する。このとき付加する円の中心ＯはＰzから半径Ｒの位置にあるので簡単に求めることができる。ここで円弧を出力したらステップＳ２４に行く。
【００８３】
もし等しくないと判定されたときは弧Ｐ0Ｐnを擬似円弧として出力する。擬似円弧の記述については後述する。ここで擬似円弧を出力したらステップＳ２４に行く。
【００８４】
ステップＳ１７で否定の判断があった場合には、ステップＳ２３において擬似円弧（Ｒ）を出力する。このステップの処理は、擬似円弧の出力すべてに共通であり、以前のステップにおける擬似円弧出力においても行われる処理である。
【００８５】
各ステップＳ１９、Ｓ２２、Ｓ２３で行われる擬似円弧（Ｒ）は、以下のようにして出力される。図１２において擬似円弧とは５点すなわちＰ0、前半傾斜線５４の中間補間点５１、Ｐz、後半傾斜線５５の中間補間点５２、およびＰnを通過する区分的に滑らかなスプライン曲線５７である。ただし矢印で示すように、各頂点の接線ベクトルが指定される。接線ベクトルの作り方はたとえばＰ0の接線ベクトル５３であればＰ0の前後2点を加えた区間５６から適当につくられるベクトルとすればよい。なお、スプライン曲線５７は、スプライン曲線発生回路１１３（図５）を用いて生成される。
【００８６】
図１３において、平面座標Ｒ０、Ｒ１を通り、Ｒ0で接線方向Ｖ0（平面ベクトル）、Ｒ1で接線方向Ｖ1であるような曲線はスプライン曲線と呼ばれ、パラメータｔの３次式Ｐ（ｔ）のものは以下の式となる。
【００８７】
【数３】
2008084237.tif 000005
【００８８】
ここでＰ（ｔ）は位置ベクトルであり、ｔ＝０のときＰ(0)＝Ｒ0、ｔ＝１のときＰ(1)＝Ｒ1、となる。従ってｔの適当な微小増分τを決め、ｔ＝０、τ、２τ、．．．、１の各値でＰ（ｔ）を計算し、発生点列をつなぐと滑らかな曲線が得られる。τの値は適当で良い。たとえば図１のδ並みの補間点列を得たいのであれば、τ＝δ／（距離Ｒ０Ｒ１）とすればよい。
【００８９】
従って実施例においては擬似円弧は、前述５個の頂点を順に結ぶ４個のスプライン曲線からなる。
【００９０】
ところで、擬似円弧は条件を満たせば曲線のどこにでも発生することができる。パターンマッチングにおいて擬似円弧を使うときは、擬似円弧の抽出区間に注意する必要がある。すなわち、擬似円弧には学習時の抽出区間があり、認識時にその同じ抽出区間から抽出することができればマッチングの点で最善であることは言うまでもない。しかし、それは原理的に不可能である。なぜならば認識すべき画像において認識物体の位置が不明であり、輪郭線を定めて抽出区間の始点または長さを決めることはできないからである。
【００９１】
それでも学習時と認識時の抽出区間を可能な限り合わせるために、擬似円弧には前述の座標に関する記述データだけでなく、形状値すなわち「形」を表す数値を付加しておく。認識の際に、ある抽出区間から取り出した擬似円弧の形状値を測定し、その形状値が学習時のものと一致するなら採用し、一致しないなら捨てることにすると、学習時と認識時の抽出区間が一致している可能性が高い。
【００９２】
この形状値は２つある。図１２において弦（長さ２ａ）、前半面積Σ0および後半面積Σ１がある。
【００９３】
このとき、
総面積比    π0＝（｜Σ0｜＋｜Σ１｜）／（４×ａの２乗）
前半面積比  π1＝｜Σ0｜／（｜Σ0｜＋｜Σ１｜）
が得られる。ここで、総面積比π0は、弦を１辺とする正方形の面積に対する弧の面積の比率であり、前半面積比π1は、弧の面積に対する前半面積の比率である。どのような形状のときに、π0、π1がどうなるかの関係が図１４に一例として図示されている。
【００９４】
続いて、ステップＳ２４において、今回の検査区間ＰcＰeにおいて出力があったか否かにかかわらず、現在点ＰcをΔ進める。ただしΔは頂点数の変位を表す整数で、図１５に示すように抽出区間が重なり合えば適当な数でよい。たとえばΓ／４の長さに相当する数とすればよい。
【００９５】
その後再びステップＳ２に戻り、以下同じことを繰り返す。
【００９６】
以上のような処理により、折れ線の２頂点を結ぶ直線が予め定められた分解長Γとなる検査区間が順次設定され、各検査区間での折れ線部分の図形が、直線（Ｌ）、円弧（Ｃ）、あるいは擬似円弧（Ｒ）として順次出力される。
【００９７】
＜物体の学習＞
次に、物体学習部１０５において行われる処理の流れを図１６に従って説明する。
【００９８】
物体学習部１０５は与えられた学習画像（物体のモデル画像）から輪郭線を抽出し、その輪郭線から物体の特徴データを抽出し、学習データ（参照データ）として出力する。
【００９９】
まず、ステップＴ１において、認識すべき物体がカメラ１０２によりモデル画像として撮像され、画像入力部１０１に取り込まれた後、画像輪郭線抽出部１０８により、モデル画像から輪郭線が抽出される。輪郭線の抽出は、折れ線分解のときにも説明したように、特許文献１〜３などに記載の公知の方法が用いられる。抽出された輪郭線は、輪郭線上の検出点を頂点として直線で結んだ折れ線として、図１に示したように、ＵＶ座標系で記述される。ここで、折れ線は平均的な頂点間隔δで構成されているものとする。
【０１００】
ステップＴ２では、学習ＬＲＣ集合が初期化される。学習ＬＲＣ集合は、上述した図６の処理により生成された折れ線の基本図形である直線（Ｌ）、擬似円弧（Ｒ）、円弧（Ｃ）の格納場所であり、格納数を０個にセットする。
【０１０１】
このとき、図１に示したように、折れ線分解長Γを変えるようにしている。折れ線分解長Γを変えると、分解される図形の数と種類が変る。変化させる折れ線分解長Γの個数と値は適当でよいが、物体のサイズをＳとすればたとえば、Γ0＝Ｓ／１０、Γ1＝Ｓ／８、Γ2＝Ｓ／６、Γ3＝Ｓ／４、の４個を準備する。
【０１０２】
このように、折れ線分解長Γを順に変え、それぞれの折れ線分解長Γについて、折れ線集合の１本１本について分解を行う。生成された基本図形は学習ＬＲＣ集合に格納する。このとき図形の種別ごとに格納する必要はない。
【０１０３】
以上が、ステップＴ３〜Ｔ５の処理であり、この処理が終了すると、ステップＴ６でハッシュ表が初期化される。図１８に示すようにハッシュ表（Ｈａｓｈ  Ｔａｂｌｅ）はメモリであり、物体の特徴パラメータ（後述）等を格納要素とする配列である。この配列の全体を０クリアする。
【０１０４】
図１９は図１の物体２において生成された基本図形を示すもので、学習ＬＲＣ集合に格納されている図形が太線７０、．．で図示されている。折れ線分解長Γが変化した結果、円弧７０、円弧７１、直線７２に見るように同じ場所でも輪郭線が何重にも分割されて表現されている。
【０１０５】
図５の３図形選択部１１１は、学習ＬＲＣ集合からすべての異なる３個の図形を選び出し、それらの相対的な位置関係を調べて、特徴としてハッシュ表に書き込む（ステップＴ７〜Ｔ９）。
【０１０６】
例えば、図１９において、選択された３個の図形が直線７３、擬似円弧７４、円弧７５であるとする。これらの図形は、それぞれ互いに離れた図形であり位置関係が明瞭でないので、これらの図形を以下の規則で延長する。
【０１０７】
（１）直線は無限に延長し、無限直線７６として扱う。
【０１０８】
（２）擬似円弧は有限に延長し、擬似円弧有限延長７７として扱う。すなわち図１３において、擬似円弧の始点側に接線ベクトルＶ０の方向に、長さＥの直線を接続する。このＥは適当に決めてよいが、例えば、擬似円弧の全長（図１２の距離Ｐ0Ｐn）を目安に、例えばＥ＝（距離Ｐ0Ｐn）／２とする。ただしこの式の係数２は経験値である。擬似円弧の終点側でも同様に長さＥの直線を接続する。このようにして擬似円弧を延長する。
【０１０９】
（３）円弧は円７８として扱う。
【０１１０】
このようにして、直線７３、擬似円弧７４、円弧７５は延長図形７６、７７、７８として延長されるが、これらの延長図形の位置関係をみると、図１９において仮想空間８０が構成されることがわかる。この場合の仮想空間とはＬとＲが分割する４つの領域のなかで、円Ｃの中心が入る領域であり、さらにＬとＲの交点座標８１近傍の空間を意味する。
【０１１１】
ここで擬似円弧Ｒについて、他の図形（Ｌ、Ｒ、Ｃ）との交点の求め方を説明する。図１３において、擬似円弧６１およびその延長６２がある。擬似円弧６１については前述した通り、スプライン関数により分割点６０の列として出力されるから、隣接２点を結ぶ直線分として演算することにより、たとえば他の図形６３との交点６４を求めることが容易にできる。また、このとき交点におけるそれぞれの接線６５、６６を求めることができ、従って交差角度φを求めることができる。一方、延長６２の部分については、これは直線であるから、たとえば他の図形６７との交点６８を求めることは容易である。
【０１１２】
次に、図１９に戻って、図１９の仮想空間８０における距離ｈ１、ｈ２を求める。角度φも前述の通り得られている。ηは円の半径である。
【０１１３】
それぞれ３つの図形Ｌ、Ｒ、Ｃの配置は物体の特徴となる。これらの配置状態が将来物体認識の過程で参照できるためには、３つの図形Ｌ、Ｒ、Ｃの位置関係が相対的に記述されている必要がある。
【０１１４】
図２０はＬ、Ｒ、Ｃの３種類の図形から重複を許して３個取り出すときの計１０個の組み合わせ、
ＬＬＬ  ＬＬＲ  ＬＲＲ  ＲＲＲ  ＬＬＣ  ＬＣＣ  ＣＣＣ  ＲＲＣ  ＲＣＣ  ＬＲＣ
の分類表であって、実施例で採用しているところの相対的記述方法すなわち各パラメータの測り方を示している。ただしこれは１例であって、この記述方法に限るものではないことに注意する。
【０１１５】
この分類表によると、上述した図形７６、７７、７８の組み合わせは（１０）ＬＲＣに記載されている。それによると、円の半径ηを１に換算し、その尺度で距離を記述（ｄ１、ｄ２）することになっている。角度θ、距離ｄ１、ｄ２は適当な精度で量子化された値である。たとえば、角度は度単位、距離は０．０１単位などとする。
【０１１６】
従って、図１８に示したように、ＬＲＣ（図形７３、７４、７５ないしは図形７６、７７、７８）の採集データ８５は、特徴データ８６に変換される。この特徴データをハッシュ関数８７（図５のハッシュ関数回路１１４）に入力するとハッシュ表の位置指標であるところの整数８８を返すことになっている。その位置に特徴データ８６を書き込むとこの特徴（図形７３、７４、７５）１個分の処理が終了する。
【０１１７】
なお、上述した３図形の分類、特徴量（特徴データ）の生成（ステップＴ８）は、図５の３図形分類・特徴量抽出部１１２において行われる。
【０１１８】
ハッシュ関数については、生成される整数がハッシュ表指標空間の中にランダムに散らばるようなものが良いとされ、その性質を持つものならなんでもよい。本実施例では、入力型コード、入力角度、入力距離のそれぞれに１０００を掛けて整数を作り、さらにそれらの２乗和を求め、その値をハッシュ表の大きさＭで割ったときの余り（０、１、．．．、Ｍ−１）として求めている。
【０１１９】
このようにして１個の特徴データが書き込まれたので、ステップＴ７に戻り同じことを繰り返す。これは異なる３個がすべて取り出されるまで繰り返す。
【０１２０】
続いて、ステップＴ１０において学習ＬＲＣ集合とハッシュ表を外部の物体モデルデータベース１０７（図５）に出力して学習を終了する。
【０１２１】
＜物体の認識＞
次に、物体認識の流れを説明する。
【０１２２】
認識すべき物体がカメラ１０２により撮像され、その撮像された物体の画像が図２に図示されている。画像輪郭線抽出部１０８により認識すべき物体の画像から輪郭線が抽出される。物体認識部１０６は、その輪郭線から物体の特徴データを抽出し、学習モデルと照合して、物体を認識する。この処理の詳細な流れが、図１７に図示されている。
【０１２３】
ステップＵ１において、認識すべき物体の画像から画像輪郭線抽出部１０８により輪郭線が抽出される。抽出は物体学習時と同じ仕様で抽出すればよい。
【０１２４】
ステップＵ２では、認識ＬＲＣ集合が初期化される。学習時と同様に格納数を０個にセットする。
【０１２５】
ステップＵ３〜Ｕ５では、抽出された輪郭線の折れ線が分解長Γで分解される。このとき折れ線分解長Γの個数と値は適当でよいが、実施例では入力画像のサイズをＨｓ（図示しない）とすれば、たとえば、Γ0＝Ｈｓ／２０、Γ１＝Ｈｓ／１０、Γ２＝Ｈｓ／４、の３個を準備する。
【０１２６】
これは、先の学習における物体のサイズＳが数値としては判っているが、今の認識画像での大きさは、サイズ変動などで全く不明であり、画像のサイズを頼りに折れ線分解長Γを求めるのが妥当であるからである。
【０１２７】
折れ線分解長Γを順に段階的に変え、それぞれの折れ線分解長Γについて、折れ線分解部１０９により折れ線集合の１本１本について折れ線を、基本図形Ｌ、Ｒ、Ｃとして生成する。生成された図形の組み合わせは認識ＬＲＣ集合に格納される。
【０１２８】
本実施例では物体の認識に幾何学的ハッシングを採用しており、この幾何学的ハッシングでは、ある図形の組み合わせについてハッシュ表で適合、すなわち学習モデルと一致したとき、まずその組み合わせの主張する倍率、回転、平行移動を計算し、次に、（１）それらを軸とするパラメータ空間（図２１）において１票を投じ、最後にまとめるというやり方と、（２）学習ＬＲＣ集合の全図形を、主張する座標系で変換し、認識ＬＲＣ集合と直接照合するやり方、の２種類が存在する。
【０１２９】
それぞれ長短があるが、一般に一部変形と一部被覆が激しいときは（１）の方法が有利であるので、本実施例では（１）の方法をとることにする。
【０１３０】
そこで、図２１で示すところの、倍率・回転・平行移動投票空間を初期化する。すなわち投票数を０にしクリアする（ステップＵ６）。
【０１３１】
図２は認識すべき画像を示しているが、この図２において、認識ＬＲＣ集合に格納されている図形の一部を図形１３、１４、．．で示す。特に、隠蔽物１２自身の輪郭線から図形１７が抽出されていること、また隠蔽物１２により図１の区間６が図２では２つの図形１５、１６に分割されていることに注意する。
【０１３２】
さらに折れ線分解長Γを変えたことで、図形１８に見るように同じ場所でも輪郭線が何重にも分割されて表現されている状況は学習時と同じである。
【０１３３】
３図形選択部１１１、３図形分類・特徴量抽出部１１２は、認識ＬＲＣ集合からすべての異なる３個の図形を選び出し、学習時と全く同様にそれらの相対的な位置関係を調べて、特徴データを生成する（ステップＵ７、Ｕ８）。
【０１３４】
上記の生成された特徴データをハッシュ関数８７に入力すると指標位置が返される。ハッシュ表におけるその位置のデータを読み出す（ステップＵ９）。ハッシュ表のデータと今回生成した特徴データを較べる。もし異なれば、この特徴データは学習されていない特徴データであるので、無視する。一致した場合、この特徴データは学習されている特徴データであり、座標変換に寄与できる。
【０１３５】
すなわちまずハッシュ表の読み出しデータから学習ＬＲＣ集合の図形を検索することができるのでそれを読み出す。図１８で言えば、学習ＬＲＣ集合のデータ８５が入手できる（ＵＶ座標系）。
【０１３６】
一方生成した特徴データの方も認識ＬＲＣ集合の対応するデータがある（ＸＹ座標系）。従ってＵＶ座標系からＸＹ座標系への対応、すなわち倍率ｓと回転θと平行移動（Ｔｘ，Ｔｙ）のそれぞれを下記の式に従って算出できる。
【０１３７】
【数４】
2008084237.tif 000006
【０１３８】
算出したデータを適当に離散化したのち（ｓ´，θ´、Ｔx´，Ｔy´）、図２１の座標変換式投票空間（四次元空間）に１票を投じる、すなわち空間の１点（黒の正方形で示す）が記録される。
【０１３９】
すべての図形の組み合わせについて処理が終了した時点で、目的とするＵＶ座標系からＸＹ座標系への初期座標変換式Φが出力される（ステップＵ１０）。これにより粗い写像を得ることができる。すなわち投票空間において、ある半径の球（４次元球）を移動し、その球内に存在する点が最も多いときの球の中心座標が出力される。その位置が、図２１で実線の円で示されている。
【０１４０】
最後に座標変換式Φを出力して物体認識を終了する。
【０１４１】
＜効果＞
以上説明したように、本発明では、直線の抽出能力が極めて高い。すなわち従来技術で問題であったところの、輪郭線の緩やかな円弧または円弧状の区間が誤って直線として検出されるという欠点と、輪郭線のある区間が明らかに直線状であるが、その起伏が激しいとき、直線として検出されないという欠点と、が同時に解決されている。
【０１４２】
これは、検査区間で種々の弧の面積を求めているからである。弧が直線から逸脱すればするほど大きな面積として検出できるから、直線とそれ以外のものを容易に分離できる。また輪郭線に多少の起伏と突発的な異常点があっても面積としては平均化されるので影響が少ない。
【０１４３】
さらに上記の副次的な効果として、輪郭線が大域的には直線ではあるが局所的には波状であるときに直線として検出できるという効果がある。すなわち輪郭線が正弦波のごとく規則正しい周期の波状である場合（図４の（ｂ））、始点と終点が波の周期に一致した場合、波の振幅に関係なく直線と認識される。これは実施例が面積だけを検査し、高さを検査しないことによる効果である。
【０１４４】
また、円弧の抽出能力が極めて高い、という効果も得られる。すなわち輪郭線の非円弧の区間が誤って円弧として検出されるという欠点と、輪郭線の円弧の区間が円弧として検出されないという欠点と、が同時に解決されている。
【０１４５】
これは、上述したように、弧の面積を求めているかである。円弧固有の左右対称性を面積から検査でき、また円弧固有の面積を検査するから、円弧の信頼度が高くなる。また輪郭線に多少の起伏と突発的な異常点があっても面積としては平均化されるので影響が少ない。
【０１４６】
また、本発明では、曲線物体の認識能力が高い、という効果が得られる。これは、従来の直線、円弧、．．．と並ぶ新しい基本図形として、擬似円弧を導入したからである。すなわち擬似円弧は曲線物体の輪郭線の部分弧を、従来の円弧などよりも正しく表現できる。しかも他の基本図形との位置関係を記述しやすい性質を持っているので幾何学的パターンマッチングで使用可能である。
【０１４７】
さらに、本発明では、サイズ変動に対する認識の頑健性が極めて高い。これは、折れ線分解長Γを導入したからである。すなわち学習において、学習画像から折れ線分解長Γをいろいろ変えて特徴を抽出しているので、従来方式よりも特徴の情報量が多い。従って認識において、サイズの変動が大きい場合でも、認識画像から適当な折れ線分解長Γを使って得た特徴が学習特徴のどれかと一致する確率が高いからである。
【０１４８】
＜他の実施例＞
なお、上述した実施例では、折れ線から基本図形を生成するために検査区間においてΣ0、Σ１、Σ00、Σ01、Σ10、Σ11の６個の面積を求めたが（図８）、この数を増やしてもよい。すなわちΣ00で言えば、面積Σ00を求めた区間をさらに２分割して、その２分割された各分割区間での面積Σ000、Σ001を求めてもよい。他の面積も同様である。その場合流れ図の上では実施例と同じ処理が複写されて加わるだけである。面積の数を増やした場合も同様な効果を得ることができる。
【０１４９】
また、上述した実施例では、折れ線の検査区間での面積を求めるとき、検査区間を２分割することを繰り返したが（図８）、２分割に限るものではなく、各段階を任意の分割数で構成してもよい。その場合でも同様な効果を得ることができる。
【０１５０】
また、上述した実施例で、検査区間を２分割し（等分割、あるいは非等分割）、前半区間の折れ線図形の面積と後半区間の折れ線図形の各面積に基づいて検査区間での折れ線図形を直線、円弧、擬似円弧の基本図形に分類するようにしてもよい。
【０１５１】
また、上述した実施例では物体の学習または認識において、擬似円弧を延長するとき直線を使ったが（図１３）、直線に限るものではなく、直線状に伸びて解析可能な形状ならなんでもよい。たとえば接続点での曲率を持つ円弧もしくはその近似折れ線、などでもよい。その場合でも同様な効果を得ることができる。
【０１５２】
また、上述した実施例では物体の学習または認識において、異なる３個の基本図形の組み合わせ集合を得たが（ステップＴ７、Ｕ７）、２個の基本図形の組み合わせ集合とするなど複数個の基本図形の組み合わせ集合を生成するようにしてもよく、その場合でも同様な効果を得ることができる。
【０１５３】
また、上述した実施例では物体の学習または認識において、ＬＲＣ集合からすべての組み合わせを得たが（ステップＴ７、Ｕ７）、すべてである必要はなく、その場合でも同様な効果を得ることができる。
【図面の簡単な説明】
【０１５４】
【図１】物体の学習のとき撮像された物体の画像を示す説明図である。
【図２】物体の認識のとき撮像された物体の画像を示す説明図である。
【図３】抽出された輪郭線上の点を結んで得られる折れ線を示す説明図である。
【図４】検査区間での折れ線を直線として認識する例を示す説明図である。
【図５】物体の学習並びに認識を行う構成を示すブロック図である。
【図６】抽出された折れ線を分解する流れを示すフローチャートである。
【図７】検査区間での折れ線の面積の求め方を説明する説明図である。
【図８】検査区間の細分化された各区間での折れ線の面積の求め方を説明する説明図である。
【図９】検査区間での弧の局所面積条件を説明する説明図である。
【図１０】検査区間での折れ線図形が直線として出力されるときの折れ線図形の説明図である。
【図１１】検査区間での折れ線図形が円弧又は擬似円弧として出力されるときの折れ線図形の説明図である。
【図１２】検査区間での折れ線図形が擬似円弧として出力されるときの擬似円弧の記述の方法を説明する説明図である。
【図１３】図形がスプライン曲線であることを説明する説明図である。
【図１４】擬似円弧の種々の形状値を説明する説明図である。
【図１５】折れ線分解を進める状態を説明した説明図である。
【図１６】物体の学習の流れを示すフローチャートである。
【図１７】物体の認識の流れを示すフローチャートである。
【図１８】ハッシュ関数を用いて図形集合を検索する状態を説明する説明図である。
【図１９】物体の輪郭線から生成された種々の基本図形を示した説明図である。
【図２０】基本図形の組み合わせのパターン並びにその位置関係を示した分類図である。
【図２１】マッチングが取れたときに座標変換式投票空間に票を順次投票していく状態を説明した説明図である。
【符号の説明】
【０１５５】
１    入力画像
２    物体
３    輪郭線
５    頂点列
１００  制御部
１０１  画像入力部
１０２  撮像装置
１０３  照明光源
１０４  物体
１０５  物体学習部
１０６  物体認識部
１０７  物体モデルデータベース
１０８  画像輪郭線抽出部
１０９  折れ線分解部
１１０  面積計算回路
１１１  ３図形選択部
１１２  ３図形分類・特徴量抽出部
１１３  スプライン曲線発生回路
１１４  ハッシュ関数回路
【図１】
2008084237.tif 000007
【図２】
2008084237.tif 000008
【図３】
2008084237.tif 000009
【図４】
2008084237.tif 000010
【図５】
2008084237.tif 000011
【図６】
2008084237.tif 000012
【図７】
2008084237.tif 000013
【図８】
2008084237.tif 000014
【図９】
2008084237.tif 000015
【図１０】
2008084237.tif 000016
【図１１】
2008084237.tif 000017
【図１２】
2008084237.tif 000018
【図１３】
2008084237.tif 000019
【図１４】
2008084237.tif 000020
【図１５】
2008084237.tif 000021
【図１６】
2008084237.tif 000022
【図１７】
2008084237.tif 000023
【図１８】
2008084237.tif 000024
【図１９】
2008084237.tif 000025
【図２０】
2008084237.tif 000026
【図２１】
2008084237.tif 000027