曲線物体輪郭線の特徴評価方法及び装置
【課題】画像から曲線物体の輪郭線を抽出し、その特徴を的確に評価する。
【解決手段】画像から曲線物体の輪郭線を抽出し、その特徴を評価する際に、特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求め、該多重度に応じた評価値を用いる。ここで、前記多重度を用いて、輪郭線の山の特徴を評価することができる。更に、輪郭線上にランダムに発生させた不定点に応じた評価値を加えることができる。又、不定点の評価値の最大値が、山の評価値の最小値よりも小さくなるようにすることができる。
【解決手段】画像から曲線物体の輪郭線を抽出し、その特徴を評価する際に、特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求め、該多重度に応じた評価値を用いる。ここで、前記多重度を用いて、輪郭線の山の特徴を評価することができる。更に、輪郭線上にランダムに発生させた不定点に応じた評価値を加えることができる。又、不定点の評価値の最大値が、山の評価値の最小値よりも小さくなるようにすることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、曲線物体輪郭線の特徴評価方法及び装置に係り、特に、電子部品の表面実装装置等において、部品の位置決め等に用いるのに好適な、画像から曲線物体の輪郭線を抽出し、その特徴、特に、窪みや突起を評価する際に用いるのに好適な、曲線物体輪郭線の特徴評価方法及び装置に関する。
【背景技術】
【０００２】
画像を使った解析、位置決め、欠陥検査、判別、意味理解等の画像認識において、認識対象の輪郭線は重要である。そこで、輪郭線から直線や円弧等の抽象データを取出し、それらを使って認識を行なうことが広く行なわれている。
【０００３】
例えば特許文献１では、輪郭線を方向コード（０〜７）で記述し、曲線の変化を計算し、更にそれを平均化したものを生成し、これを基に窪みや突起を検出している。
【０００４】
又、特許文献２では、輪郭線の接線方向について、変化率（曲率）を監視し、その符号と大きさにより、凸曲線セグメント、凹曲線セグメント、及び直線分セグメントを抽出している。
【０００５】
又、特許文献３では、輪郭線を任意の長さに分解した初期状態から始め、誤差が基準値を越えれば短くし、誤差が基準値以下なら長くするという、単純な繰り返しにより、直線と円弧を抽出している。このとき、修正する際の増減値を、前回の増減値の１／２に設定することが特徴であり、２分探索に似た高速な収束を効果としている。
【０００６】
更に、特許文献４では、渦巻き状に広がる巻貝を用いて部品の輪郭線を抽出し、輪郭線上の部品特徴を求めることが記載されている。
【０００７】
【特許文献１】特公平１−３０１８３号公報
【特許文献２】特開平３−２５０３８０号公報
【特許文献３】特許第３８８３９９３号公報
【特許文献４】特開２００１−２５１０９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術は、いずれも、窪みや突起の先端である座標１点と、その接線方向が出力されるだけであり、形が良く大きな窪みや突起と、逆に形が悪い又は小さい窪みや突起を区別することができなかった。
【０００９】
即ち、図１において、従来技術でも、物体１の窪み３、及び、突起２、４、５、６、７、８を抽出することはできる。しかし、この物体１を認識するときに最も使いたい特徴は、形が良く大きな窪みや突起であるところの窪み３と、突起２、４、５、８であり、逆に使いたくない特徴は、形が悪い又は小さい窪みや突起であるところの突起６、７である。しかし従来技術では、その区別のための情報が出力されていない。使うべきものと捨てるべきものを区別するためには、そのための評価値を出力することが必要である。
【００１０】
なお、突起６と７がいつでも不要とは限らない。図２に例示する如く、円に相似な物体１´があり、その外周に現われる唯一の変化が突起６や７であった場合、これらは重要な位置決め情報となる。即ち、要不要は相対的なものであり、問題の評価値は、円形状の場合、突起６や７の評価値が最も高くなる必要がある。しかしながら従来は、このような評価値を適切に決定することができなかった。
【００１１】
本発明は、前記従来の問題点を解消するべくなされたもので、輪郭線の特徴を適切に評価できるようにすることを課題とする。
【課題を解決するための手段】
【００１２】
本発明は、画像から曲線物体の輪郭線を抽出し、その特徴を評価する際に、特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求め、該多重度に応じた評価値を用いるようにして、前記課題を解決したものである。
【００１３】
ここで、前記多重度を用いて、輪郭線の窪みや突起（山と総称する）の特徴を評価することができる。
【００１４】
更に、輪郭線上にランダムに発生させた不定点に応じた評価値を加えることができる。
【００１５】
又、前記不定点の評価値の最大値が、山の評価値の最小値よりも小さくなるようにすることができる。
【００１６】
本発明は、又、画像から曲線物体の輪郭線を抽出し、その特徴を評価する曲線物体輪郭線の特徴評価装置において、特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求める手段と、該多重度に応じた評価値を求める手段と、を備えたことを特徴とする曲線物体輪郭線の特徴評価装置を提供するものである。
【発明の効果】
【００１７】
本発明によれば、曲線物体の輪郭線の特徴の正しい評価値を得ることができる。特に、多重度は、山の深さ（高さ）と形の良さを適切に表わすことができる。
【００１８】
更に、確固たる特徴である多重度に応じた評価値に、不定の特徴である不定点に応じた評価値を加えることによって、外周に殆ど特徴が無いような曲線物体でも認識が可能となる。
【発明を実施するための最良の形態】
【００１９】
以下図面を参照して、本発明の実施形態を詳細に説明する。
【００２０】
図３は、本発明を実施するための図形特徴データ抽出装置の主要部のブロック構成を示す図である。
【００２１】
本実施形態は、例えば照明１００により照明される物体１をテレビカメラ１０２で撮影して入力する画像入力部１０４と、画像から物体の輪郭線を抽出するための画像輪郭線抽出部１０６と、輪郭線から物体の特徴データを抽出するための図形特徴データ抽出部１１０及び物体特徴データのデータベース１１２と、前記画像輪郭線抽出部１０６で抽出された輪郭線からＲemark（窪みや突起）を全て見つけて出力するＲ発生部１２０と、該Ｒ発生部１２０から出力された個々のＲに要不要の評価値νを埋め込むＲ評価部１２２と、前記輪郭線から不定点（Ｔransient）を出力するＴ発生部１２４と、該Ｔ発生部１２４から出力された個々のＴに要不要の評価値νを埋め込むＴ評価部１２６と、全体を制御して、次の物体を撮像し、物体の特徴データを抽出し、物体特徴データのデータベース１１２に出力する制御部１３０とを主に備えている。
【００２２】
以下、実施例を詳しく記述する。
【００２３】
本発明は、輪郭線から良いＲと良いＴを出力するための方法に関するものである。
【００２４】
図１において、Ｒとは、Ｒemark即ち窪みや突起であり、窪み３、突起２、４、５、６、７、８のことである。
【００２５】
Ｔとは、Ｔransient即ち不定点（ランダム点）であり、Ｒの個数が不足したときに、周上にランダムに発生させる不定点９のことである。
【００２６】
図４（ａ）に輪郭線の構造を示す。輪郭線は折れ線であって、進行方向３０の向きに進む頂点座標３１の列である。各頂点でその近傍頂点列３２を均すことにより接線方向３３を得ることができる。
【００２７】
まず最初に、全ての輪郭線に長さの評価値ζをつけておく。ζは０〜１の値を持ち、輪郭線の長さλが大きいほどζも大きい。
【００２８】
図５において、認識しようとする物体の輪郭線１は最も長く（λ＝ＭＡＸ）、外部の異物の輪郭線１３は次に長く、認識物体の内部のキズや模様等の輪郭線１２は最も短い（λ＝ＭＩＮ）。
【００２９】
図６（ａ）に、λとζのグラフ（関数）の例を示す。この関数は、λ＝ＭＡＸのときζ＝１、λ＝ＭＩＮのときζ＝Ｃ１とする。Ｃ１は正の定数で任意値でよいが、例えばＣ１＝０．１とすることができる。
【００３０】
関数はλの増加関数なら適当でよい。実施例では、座標（ＭＩＮ，Ｃ１）で底を持ち、中央点７０を通るような２次関数を設定した。なおグラフ後半の中央点７０から座標（ＭＡＸ，１）までのグラフは、前半の１８０°回転である。
【００３１】
この評価関数によると、図５の輪郭線１のζ＝１．０、輪郭線１２のζ＝０．１、輪郭線１３のζ＝０．２（例えば）となり、ほど良い評価結果を得ている。
【００３２】
次にＲを発生させる。
【００３３】
図７（ａ）にＲの構造を示す。Ｒは座標と輪郭線の接線方向を持つ。又、その総合評価値（＝要不要の度合い）ν（０．５〜１．０）を持つ。他のデータはνを生成するための材料である。
【００３４】
図４に本実施例で出力するＲの目標とする座標を示す。図４（ａ）は直線で挟まれた形状である。この場合、交点に最も近い頂点３４の近傍がＲの目標とする座標である。図４（ｂ）は曲線形状であり、しかも周長においてミクロ的にもマクロ的にも左右対称の場合である。この場合、左右対称の中心線（図示しない）との交点に最も近い頂点４０の近傍がＲの目標とする座標である。図４（ｃ）は直線と曲線で挟まれた形状であり、ミクロ的には左右対称、マクロ的には左右非対称の場合の代表例である。この場合、座標４３と座標４５の中間座標、たとえば座標４４がＲの目標とする座標である。ここで、座標４３はミクロの範囲で得たＲ座標、座標４５はマクロの範囲で得たＲ座標である。
【００３５】
図８はＲ発生部１２０の処理手順を示す流れ図であり、以下この流れに従って順に説明する。
【００３６】
ステップＳ１で、周長Γの列（Γ１、Γ２、・・・）を大きい順に用意する。Γは物体サイズから適当に決めれば良い。
【００３７】
ステップＳ２で、最初のΓ１に位置付ける。Ｒ生成個数ｋを０とする。
【００３８】
ステップＳ３で、次の周長Γがある限り以下の処理を続ける。全てのΓを処理すると終了する。
【００３９】
ステップＳ４で、最初の輪郭線に位置付ける。
【００４０】
ステップＳ５で、区間の始点Ｓ（図９のＳ０）を輪郭線の始点に置く。
【００４１】
ステップＳ６で、次の輪郭線がある限り続ける以下の処理を続ける。全ての輪郭線を処理したらステップＳ３に戻る。
【００４２】
ステップＳ７で、状態遷移のフラグｓｔａｔｅをＯＦＦ（最良山を持っていない）にする。山とは窪み／突起の総称である。
【００４３】
ステップＳ８で、Ｓが輪郭線の終点に達するまで以下の処理を続ける。但し、これは輪郭線が閉じた（＝１周する）ときに必要な処理であって、開いたときは、終点からΓ戻った地点まで到達したら中断してよい。
【００４４】
ステップＳ９で、山検出フラグｍｎｔをＯＦＦ（山ではない）にする。
【００４５】
ステップＳ１０で、Ｓからの周長が初めてΓ以上となる頂点Ｅを探す。即ち、図９において、現在のΓ＝Γ１、現在のＳ＝Ｓ０であり、Ｓから始めて頂点間の距離を積算し続けると、Γ１に等しいか超える頂点Ｅ０に達する。このＳ０からＥ０までを現在区間と呼ぶことにする。
【００４６】
ステップＳ１１で、山形状の事前検査を行なう。これは以下の検査がある。
【００４７】
（１）現在区間の頂点数（Ｓ０とＥ０を除く）が十分多いこと。これは、例えば定数＝３以上とすることができる。但し、定数は任意である。
【００４８】
（２）ヒゲを除くため、開口部の距離Ｓ０Ｅ０がある程度大きいこと。これは、例えば０．２×Γ１以上とすることができる。但し、定数は任意である。
【００４９】
（３）現在区間の頂点（Ｓ０とＥ０を除く）が全て、直線Ｓ０Ｅ０のどちらか一方の側に偏在していること。
【００５０】
（４）現在区間の深さＭ０Ｇ０が十分に大きいこと。これは、例えば０．２×Γ１以上とすることができる。但し、定数は任意である。
【００５１】
Ｍ０は次のように求める。即ち、現在区間の周長をγとするとき（γ≧Γ１）、Ｓ０からの周長を測り、γ／２の地点を求めてこれをＭ０とする。従って、Ｍ０は一般に頂点と頂点の間に落ちるので、線形補間により正確な座標を求めることが重要である。Ｇ０はＳ０Ｅ０の中心である。
【００５２】
以上全ての事前検査を合格したら、次のステップＳ１３に行く。いずれかが不合格ならステップＳ１７に行く。
【００５３】
ステップＳ１３で、交差角度検査を行なう。これはＳ０Ｅ０とＭ０Ｇ０が直交（＝９０°）に近いことを要求する。これは、｜ｃｏｓθ｜≦Ｄ１で判定する。例えば、Ｄ１＝ｃｏｓ８０°とする。但し、定数は任意である。
【００５４】
ステップＳ１４で、左右対称検査を行なう。これは中心線Ｍ０Ｇ０に対して、Ｓ０、Ｅ０の接線方向であるそれぞれβｓ、βｅが同じ角度に開いていることを要求するものである。
【００５５】
演算は次のように行なう。ベクトルＭ０Ｇ０の方向余弦を（ｃｏｓα、ｓｉｎα）とする。Ｓ０の近傍を適当に均すことで、図の向きの接線方向βｓを得ることができる。βｅについても同様である。いずれも方向余弦の形で求めておく。
【００５６】
φｓ＝βｓ−α、φｅ＝βｅ−α、を計算する。
【００５７】
次に、φ＝φｓ＋φｅを計算する。もし、完全な左右対称ならφ＝０°＝（１，０）となる。従ってこの検査では、これは｜ｓｉｎφ｜≦Ｄ２で判定する。例えば、Ｄ２＝ｓｉｎ１０°とする。但し、定数は任意である。
【００５８】
ステップＳ１５で、現在山の評価値ｅ＝｜ｓｉｎθ｜｜ｃｏｓφ｜を計算する。ｅは０〜１の値を持ち、直交に近いほど、左右対称に近いほど１に近付く。１に近いほど良い山である。ｅは山の連続があるとき、最も良い山を見つけるために使われる。
【００５９】
ステップＳ１６で、ｍｎｔをＯＮにする。これは山が一つ見つかったことを示す。
【００６０】
ステップＳ１７で、状態遷移フラグｓｔａｔｅを見る。
【００６１】
ステップＳ１８で、ｍｎｔがＯＮであり、最良山を持っていない場合、ここが山であれば、ステップＳ１９で、最良山に現在山を複写して、最良山の候補とする。即ち、見つかれば直ちに出力するわけではない。ｓｔａｔｅにＯＮをセットする。
【００６２】
ステップＳ２０で、ｍｎｔがＯＦＦであり、最良山を持っている場合、ここが山で無ければ、ここで初めて出力できるので、ステップＳ２１で、最良山をＲとして出力する。ｓｔａｔｅにＯＦＦをセットし、再び山が無い状態とする。
【００６３】
以下、最良山をＲとして出力するときの処理を説明する。
【００６４】
図９において、最良山が仮に区間Ｓ０Ｅ０のものとする。ここで、先に現在区間の記述に使ったＳ０Ｅ０と同じ名称を使うので、混同しないように注意する。
【００６５】
（１）直線Ｓ０Ｅ０と距離が最も大きい頂点Ｐ０を探す。複数あるときはその始端と終端の中央付近の同最大距離の頂点とすればよい。
【００６６】
（２）Ｐ０からＳ０Ｅ０に垂線を降ろし、その足をＨ０とする。
【００６７】
（３）Ｈ０Ｐ０（長さｈ）上、中央付近（例えば、ｈ／４〜（３／４）ｈ内）に、適当な広がりで、Ｈ０からＰ０に向かって、例えば４等分して５個の点列を発生させる。但し、これの位置を決める定数は適当で良い。
【００６８】
（４）各発生点からＨ０Ｐ０に直交（従ってＳ０Ｅ０に平行）する直線を引く（例えば直線５０）。
【００６９】
（５）その直線５０と現在区間のＳ０側、Ｅ０側それぞれの交点５１、５２を求める。
【００７０】
（６）交点間の中点５３を出力する。以上を５本分繰り返す。
【００７１】
（７）５個の中点列から最小２乗近似直線５４を引く。
【００７２】
（８）Ｐ０からその直線５４に垂線を降ろし、その垂線の足をｚ０とする。ｚ０がこの山の出力座標Ｑ１である。
【００７３】
（９）ｚ０における山の接線方向τ０は、ベクトルＨ０Ｐ０を±９０°回転した方向から作る。図９は現在区間が反時計回りであるから、＋９０°回転する（もし時計回りであるなら、−９０°回転する）。
【００７４】
これにより、山の出力Ｑを得ることができる。即ちＱ＝（座標ｚ０、接線方向τ０）である。図１０において、各Γ毎にＱが出力されることに注意する。即ち、Γ１からＱ１、Γ２からＱ２、・・・とΓ５からのＱ５まで続く。
【００７５】
Ｑ１も含めて全ての出力Ｑは、既に登録されている個々のＲのε近傍に入っているかどうかの検査を行なう。これはむやみにＲの個数を増やさないためである。ここでεは適当に定めれば良く、例えば物体長の０．１倍とする。
【００７６】
ここでは１回目のＱ１は登録されるものとする。実際、周りに山が無いからである。登録されたＱのことをＲと呼ぶ。
【００７７】
Ｒのζに現在の輪郭線のζを複写する。
【００７８】
ＲのγにＱ１の区間長γ（Ｓ０からＥ０までの実際の長さ）を複写する。このγは以降の処理で変更してはならない。
【００７９】
又、Ｒの多重度と呼ぶｍを１にする。
【００８０】
Ｒの個数ｋを一つ増やす。
【００８１】
２回目のＱ２はＲのε近傍に入っているので、Ｑ２は登録しない。その代わりＲの修正を行なう役目を持つ。
【００８２】
即ち、図１１において、Ｑ１（＝Ｒ）、Ｑ２の座標をそれぞれｑ１、ｑ２、接線方向（方向余弦）をそれぞれω１、ω２とする。
【００８３】
新座標ｑ´は、ｑ１、ｑ２をΓ２：Γ１に内分して得る。
【００８４】
新接線方向ω´は、ω１、ω２を同じくΓ２：Γ１に内分して得る。このときのやり方としては、開き角度δを求め、δは０°に近いことを利用し（実際ほとんど２°未満である）、ｓｉｎδ（符号付）をΓ２：Γ１に内分すれば良い。即ち、修正角度β（図には無い）のｓｉｎβ＝（Γ２／（Γ１＋Γ２））ｓｉｎδであり、従ってｃｏｓβ＝√（１−ｓｉｎβの２乗）とする。ω´はω１をβ回転したものである。
【００８５】
以上の座標修正、角度修正は非常に重要である。この修正により、Ｒの座標と接線方向を安定することができる。
【００８６】
最後に、Ｒの多重度ｍを一つ上げて２とする。これでＱ２による修正が完了した。
【００８７】
同じことを引き続くＱ３以降でも繰り返す。最終のＱ５まで繰り返したとき、このＲの多重度ｍは５になっている。
【００８８】
多重度の役割については後述する。
【００８９】
ステップＳ２２で、最良山を持っている場合、ここが山であれば、山が連続したことになる。従って、ステップＳ２２で、最良山と現在山で良い方の山を選ぶ。即ち、ステップＳ２３で、現在山の評価値の方が高ければ、最良山に現在山を複写する。もし同じか低ければ何もしない。
【００９０】
ステップＳ２４で、現在山があってもなくてもＳ０を周長δ１移動し、次はＳ１から始める。但し、δ１は頂点位置変位で、例えばδ１＝１（一つずつ移動）とする。但し、この定数は任意である。
【００９１】
以下は新しいＳ１でステップ８から同じことを繰り返す。
【００９２】
なお、ステップＳ２１において、注意すべきは円又は同相の、即ち特徴の無いところから山を出力しないようにすることである。
【００９３】
即ち、図１２において、既に中点で示すところの山Ｍ０が出力されてＲとなっているものとする（直前のＲ）。
【００９４】
その後、山Ｍ１の出力をしようとするが、形状がほとんど直前のＲと同じであることが分かる。
【００９５】
即ち、例えば開口部ＳＥの距離が同じであり、ＭからＳＥまでの距離が同じであり、更にＭ０、Ｍ１それぞれの接線方向βｓ、βｅの相対的な方向が同じであるときは、同じ山であると結論してよい。
【００９６】
このようなときは、山Ｍ１を出力しないことは勿論、直前Ｒそのものも出力リストから抹消する。
【００９７】
ステップＳ３で全てのΓで処理が終了したらＲ発生が終了する。
【００９８】
Ｒ発生が終了したら、次に、Ｒ評価部１２２でＲの評価を行なう。
【００９９】
図６（ｂ）に多重度ｍの評価関数ωの一例を示す。
【０１００】
まず、生成されたＲの集合で、そのｍについて、最大値（ＭＡＸ）と最小値（ＭＩＮ）を得る。図１３は生成されたＲの集合の多重度（Ｍで示す）を示す。ＭＡＸ＝５、ＭＩＮ＝１である。
【０１０１】
特徴として、図１４に例示する如く、より好ましいところの形が良く大きな山には大きな多重度が出力されていること、逆に、形が悪い、あるいは小さい山には小さな多重度が出力されていることに注意する。
【０１０２】
図６（ｂ）に戻って、Ｒのそれぞれに多重度ｍが記入されているから、そのｍで図の関数値ωを得る。ここで使う関数は、図６（ａ）のζ評価のときのものと同じような規則で作ればよい。定数Ｃ２は適当でよく、例えばＣ２＝０．２とすることができる。
【０１０３】
次に図６（ｃ）に長さγの評価関数ψを示す。生成されたＲの集合で、そのγについて、最大値（ＭＡＸ）と最小値（ＭＩＮ）を得る。
【０１０４】
Ｒのそれぞれに長さγが記入されているから、そのγで図の関数値ψを得る。ここで使う関数は図６（ａ）のζ評価のときのものと同じような規則で作ればよい。定数Ｃ３は適当でよく、例えばＣ３＝０．２とすることができる。
【０１０５】
次に、Ｒのそれぞれに、形と大きさの評価値ηをセットする。Ｒのηは、
η＝多重度評価値×長さ評価値＝ω×ψ
である。
【０１０６】
次にＲのそれぞれに、総合評価値νをセットする。Ｒのνは、
ν＝０．５＋０．５ζη
である。この式によると、νは０．５〜１．０の値を持ち、輪郭線の評価値ζが大きく、形と大きさの評価値ηが大きいほど大きい。
【０１０７】
図５で、黒丸はＲであることを示し、そのν値を示している。特徴として、好ましい地点のＲほど大きなνが出力されていることに注意する（Ｒの最小値が０．５であることに注意）。
【０１０８】
特に図１３において、多重度ではＲ６３とＲ６４は共にｍ＝４であり区別できないが、図２ではそれぞれν＝０．９、ν＝０．６と大きく差がついていることに注意する。これは輪郭線の評価値ζの働きによるものである。
【０１０９】
図１５に、出力されたＲを示す。Ｒを物体認識で使う場合には、例えば三角形Ｒ１Ｒ２Ｒ９の形状を学習して記録し、認識のとき同じ形が現われるかどうかを調べればよい。
【０１１０】
図では１２個のＲが出力されているが、この数では必ずしも十分でないことがある。用途によっては外周に関する情報が欲しい場合がある。
【０１１１】
例えば、外周部にランダムに配置される点Ｔは、数が多ければ認識の情報に使うことができる。
【０１１２】
図７（ｂ）に、Ｔの構造を記述する。
【０１１３】
Ｔは座標と輪郭線の接線方向を持つ。又その総合評価値（＝要不要の度合い）ν（０〜０．５）を持つ。
【０１１４】
例えば、三角形Ｒ２Ｒ８Ｔ３を学習したとする。認識においては別画像であるから一般に異なる場所、例えばＴｘに発生する。
【０１１５】
しかし三角形Ｒ１Ｒ８Ｔｘは学習三角形Ｒ２Ｒ８Ｔ３と良く似ているので、学習物体の可能性として出力することができる。
【０１１６】
Ｔが必要か否かはＲの個数ｋに従うのが良い。図１６は、Ｔの必要個数Ｎｔの生成関数である。これも図６（ａ）のζ生成関数と同じ原理でつくることができる（上下を反対にする）。Ｒの十分個数ＲＥは適当でよく、例えばＲＥ＝２５とすることができる。関数はｋ＝ＲＥでＮｔ＝０を出力する、即ちＴは不要である。一方ｋ＝０ではＴＳ個を出力する。ＴＳはＴだけで認識できるための必要個数であり、物体のサイズその他から決めればよい。例えば定数ＴＳ＝８０を割り当てても良い。
【０１１７】
Ｔの発生は至って単純である。即ち、図１５において、各輪郭線の始点にまず発生し、予め計算しておいた距離毎に周を進み、そこに発生する。但しＲのε近傍に入っているときは発生しない。
【０１１８】
Ｔが進む距離は、輪郭線集合全体の距離をＮｔで除した商から決めればよい。
【０１１９】
Ｔのζは輪郭線の評価値の複写である。
【０１２０】
Ｔのνは、ν＝０．５ζとする。これにより輪郭線が最大評価値ζ＝１のときでもν＝０．５となり、Ｒの最小値以下となるので両者を差別する上で都合が良い。
【０１２１】
図５に最終的に出力されたＲとＴを示す。黒丸がＲであり、白丸がＴである。図には書かれていないが、それぞれ輪郭線の接線方向を持つ。ν値は分かり易さのために小数点以下１桁とした。
【０１２２】
これによると、明らかに特徴で使いたいところはνが非常に高く、逆に使いたくない特徴は低い。特に、内部の雑音１２のνは低く、又、外部の雑音１３のνも低いことに注目する。
【０１２３】
このようにして、Ｒ（窪み／突起）の正しい評価値νを得ることができる。νは優れた指針であり、認識対象で、しかも強い特徴ほど大きなνとなって現われる。
【０１２４】
即ち、
ν＝０．５＋０．５ζη
＝０．５＋０．５ζ（λ）ω（ｍ）ψ（γ）
とすると、ζ（λ）は母体輪郭線の長さλが大きいほど大きい。ω（ｍ）は多重度ｍが大きいほど大きい。ψ（γ）は周の長さγが大きいほど大きい。以上により、ν値は３項全てが大きいときのみ大きくなるのであって、これはＲの正しい評価値となっている。
【０１２５】
特に、図６（ａ）、（ｂ）、（ｃ）に示すとおり、ζ（λ）、ω（ｍ）、ψ（γ）は、それぞれλ、ｍ、γの値の範囲（ＭＡＸとＭＩＮ）に従う関数であることに注意する。即ち評価値が高いか低いかは、その集合のＭＡＸ値とＭＩＮ値による。
【０１２６】
例えば図６（ｂ）において多重度ｍの評価値ω（ｍ）はｍの範囲による。即ち先に言及したが、図２に例示した如く、円形物体１´があって、その円周上にわずかに窪み／突起６、７がある場合、それらの多重度が例えばｍ＝１とｍ＝２だけのときがある。その場合、ＭＡＸ＝２、ＭＩＮ＝１であり、ｍ＝２を得たものは最大評価値ω＝１となる。これは、その窪み／突起の多重度の正しい評価値である。
【０１２７】
ここで、多重度ｍは窪み／突起の深さ（高さ）と形の良さを表わす指標である。
【０１２８】
即ち、図１４において、（ａ）、（ｂ）、（ｃ）は、いずれも同じ開口長ｅを持つ窪み（突起）である。しかし、図のように多重度はそれぞれ異なっている。（ｂ）の多重度が（ａ）に較べて小さいのは深さ（高さ）が小さいからであり、（ｃ）の多重度が（ａ）に較べて小さいのは先端部の形が悪いからである。
【０１２９】
このように、多重度ｍの値は窪み（突起）が深いほど（高いほど）、又形が良いほど大きいのでＲの評価の一つとして有効である。
【０１３０】
又、Ｒ単独、又はＲとＴの組合せで認識を行なうことができる。その際に、それぞれの評価値νは優れた指針であり、良いＲ又は良いＴだけを取り出して最高の集合をつくることができる。これにより、外周に殆ど特徴が無いような曲線物体でも認識が可能になる。
【０１３１】
なお、実施例では評価値生成関数として、２次関数を使ったが、単調に増加あるいは減少する関数であれば何でも良い。極端な例として直線でも良い。その場合でも効果は殆ど変わらない。
【０１３２】
又、実施例では多重度ｍで評価できる輪郭線の特徴としてＲ（窪み／突起）を用いた。しかし、Ｒ以外にも存在する。例えば、Ｌ（直線）やＣ（円）等がその例である。
【０１３３】
図１７の（ａ）は輪郭線の直線部（Ｌ）が長さの異なるΓ（図示しない）で抽出されたものである。このときにも、使われたΓの長さが５個なら、ｍ＝５とすればよい。（ｂ）に示すように、凹凸の激しい区間があり、長い距離で見れば直線として検出可能で、逆に短い距離では検出不可能であるような場合、図のように３個の長さだけで検出されたので、多重度ｍ＝３である。
【０１３４】
図１８は、輪郭線の円弧部（Ｃ）の長さが異なるΓ（図示しない）で抽出されたものである。このときも、使われたΓの長さが５個なら、ｍ＝５とすればよい。
【０１３５】
このように多重度は輪郭線から抽出されるあらゆる特徴形状に存在するのであって、その特徴形状の大きさと、形の良さを表わす尺度となり得る。
【図面の簡単な説明】
【０１３６】
【図１】曲線物体の形状の一例を示す図
【図２】円形物体の一例を示す図
【図３】本発明を実施するための図形特徴データ抽出装置の主要部構成を示すブロック図
【図４】Ｒの目標座標を示す図
【図５】本発明による評価値の付与例を示す図
【図６】本発明で用いる評価関数の例を示す図
【図７】同じくＲとＴの構造を示す図
【図８】同じくＲ発生の処理手順を示す流れ図
【図９】同じく実施例の処理方法を説明するための図
【図１０】同じく処理方法を説明するための図
【図１１】同じく処理方法を説明するための図
【図１２】同じく処理方法を説明するための図
【図１３】同じく処理方法を説明するための図
【図１４】本発明の多重度を示す図
【図１５】実施例の処理方法を説明するための図
【図１６】同じくＴの必要個数Ｎｔの生成関数の例を示す図
【図１７】輪郭線の直線部の抽出例を示す図
【図１８】輪郭線の円弧部の抽出例を示す図
【符号の説明】
【０１３７】
１、１´、１２、１３…輪郭線
１０４…画像入力部
１０６…画像輪郭線抽出部
１１０…図形特徴データ抽出部
１１２…図形特徴データデータベース
１２０…Ｒ発生部
１２２…Ｒ評価部
１２４…Ｔ発生部
１２６…Ｔ評価部
１３０…制御部
【技術分野】
【０００１】
本発明は、曲線物体輪郭線の特徴評価方法及び装置に係り、特に、電子部品の表面実装装置等において、部品の位置決め等に用いるのに好適な、画像から曲線物体の輪郭線を抽出し、その特徴、特に、窪みや突起を評価する際に用いるのに好適な、曲線物体輪郭線の特徴評価方法及び装置に関する。
【背景技術】
【０００２】
画像を使った解析、位置決め、欠陥検査、判別、意味理解等の画像認識において、認識対象の輪郭線は重要である。そこで、輪郭線から直線や円弧等の抽象データを取出し、それらを使って認識を行なうことが広く行なわれている。
【０００３】
例えば特許文献１では、輪郭線を方向コード（０〜７）で記述し、曲線の変化を計算し、更にそれを平均化したものを生成し、これを基に窪みや突起を検出している。
【０００４】
又、特許文献２では、輪郭線の接線方向について、変化率（曲率）を監視し、その符号と大きさにより、凸曲線セグメント、凹曲線セグメント、及び直線分セグメントを抽出している。
【０００５】
又、特許文献３では、輪郭線を任意の長さに分解した初期状態から始め、誤差が基準値を越えれば短くし、誤差が基準値以下なら長くするという、単純な繰り返しにより、直線と円弧を抽出している。このとき、修正する際の増減値を、前回の増減値の１／２に設定することが特徴であり、２分探索に似た高速な収束を効果としている。
【０００６】
更に、特許文献４では、渦巻き状に広がる巻貝を用いて部品の輪郭線を抽出し、輪郭線上の部品特徴を求めることが記載されている。
【０００７】
【特許文献１】特公平１−３０１８３号公報
【特許文献２】特開平３−２５０３８０号公報
【特許文献３】特許第３８８３９９３号公報
【特許文献４】特開２００１−２５１０９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術は、いずれも、窪みや突起の先端である座標１点と、その接線方向が出力されるだけであり、形が良く大きな窪みや突起と、逆に形が悪い又は小さい窪みや突起を区別することができなかった。
【０００９】
即ち、図１において、従来技術でも、物体１の窪み３、及び、突起２、４、５、６、７、８を抽出することはできる。しかし、この物体１を認識するときに最も使いたい特徴は、形が良く大きな窪みや突起であるところの窪み３と、突起２、４、５、８であり、逆に使いたくない特徴は、形が悪い又は小さい窪みや突起であるところの突起６、７である。しかし従来技術では、その区別のための情報が出力されていない。使うべきものと捨てるべきものを区別するためには、そのための評価値を出力することが必要である。
【００１０】
なお、突起６と７がいつでも不要とは限らない。図２に例示する如く、円に相似な物体１´があり、その外周に現われる唯一の変化が突起６や７であった場合、これらは重要な位置決め情報となる。即ち、要不要は相対的なものであり、問題の評価値は、円形状の場合、突起６や７の評価値が最も高くなる必要がある。しかしながら従来は、このような評価値を適切に決定することができなかった。
【００１１】
本発明は、前記従来の問題点を解消するべくなされたもので、輪郭線の特徴を適切に評価できるようにすることを課題とする。
【課題を解決するための手段】
【００１２】
本発明は、画像から曲線物体の輪郭線を抽出し、その特徴を評価する際に、特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求め、該多重度に応じた評価値を用いるようにして、前記課題を解決したものである。
【００１３】
ここで、前記多重度を用いて、輪郭線の窪みや突起（山と総称する）の特徴を評価することができる。
【００１４】
更に、輪郭線上にランダムに発生させた不定点に応じた評価値を加えることができる。
【００１５】
又、前記不定点の評価値の最大値が、山の評価値の最小値よりも小さくなるようにすることができる。
【００１６】
本発明は、又、画像から曲線物体の輪郭線を抽出し、その特徴を評価する曲線物体輪郭線の特徴評価装置において、特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求める手段と、該多重度に応じた評価値を求める手段と、を備えたことを特徴とする曲線物体輪郭線の特徴評価装置を提供するものである。
【発明の効果】
【００１７】
本発明によれば、曲線物体の輪郭線の特徴の正しい評価値を得ることができる。特に、多重度は、山の深さ（高さ）と形の良さを適切に表わすことができる。
【００１８】
更に、確固たる特徴である多重度に応じた評価値に、不定の特徴である不定点に応じた評価値を加えることによって、外周に殆ど特徴が無いような曲線物体でも認識が可能となる。
【発明を実施するための最良の形態】
【００１９】
以下図面を参照して、本発明の実施形態を詳細に説明する。
【００２０】
図３は、本発明を実施するための図形特徴データ抽出装置の主要部のブロック構成を示す図である。
【００２１】
本実施形態は、例えば照明１００により照明される物体１をテレビカメラ１０２で撮影して入力する画像入力部１０４と、画像から物体の輪郭線を抽出するための画像輪郭線抽出部１０６と、輪郭線から物体の特徴データを抽出するための図形特徴データ抽出部１１０及び物体特徴データのデータベース１１２と、前記画像輪郭線抽出部１０６で抽出された輪郭線からＲemark（窪みや突起）を全て見つけて出力するＲ発生部１２０と、該Ｒ発生部１２０から出力された個々のＲに要不要の評価値νを埋め込むＲ評価部１２２と、前記輪郭線から不定点（Ｔransient）を出力するＴ発生部１２４と、該Ｔ発生部１２４から出力された個々のＴに要不要の評価値νを埋め込むＴ評価部１２６と、全体を制御して、次の物体を撮像し、物体の特徴データを抽出し、物体特徴データのデータベース１１２に出力する制御部１３０とを主に備えている。
【００２２】
以下、実施例を詳しく記述する。
【００２３】
本発明は、輪郭線から良いＲと良いＴを出力するための方法に関するものである。
【００２４】
図１において、Ｒとは、Ｒemark即ち窪みや突起であり、窪み３、突起２、４、５、６、７、８のことである。
【００２５】
Ｔとは、Ｔransient即ち不定点（ランダム点）であり、Ｒの個数が不足したときに、周上にランダムに発生させる不定点９のことである。
【００２６】
図４（ａ）に輪郭線の構造を示す。輪郭線は折れ線であって、進行方向３０の向きに進む頂点座標３１の列である。各頂点でその近傍頂点列３２を均すことにより接線方向３３を得ることができる。
【００２７】
まず最初に、全ての輪郭線に長さの評価値ζをつけておく。ζは０〜１の値を持ち、輪郭線の長さλが大きいほどζも大きい。
【００２８】
図５において、認識しようとする物体の輪郭線１は最も長く（λ＝ＭＡＸ）、外部の異物の輪郭線１３は次に長く、認識物体の内部のキズや模様等の輪郭線１２は最も短い（λ＝ＭＩＮ）。
【００２９】
図６（ａ）に、λとζのグラフ（関数）の例を示す。この関数は、λ＝ＭＡＸのときζ＝１、λ＝ＭＩＮのときζ＝Ｃ１とする。Ｃ１は正の定数で任意値でよいが、例えばＣ１＝０．１とすることができる。
【００３０】
関数はλの増加関数なら適当でよい。実施例では、座標（ＭＩＮ，Ｃ１）で底を持ち、中央点７０を通るような２次関数を設定した。なおグラフ後半の中央点７０から座標（ＭＡＸ，１）までのグラフは、前半の１８０°回転である。
【００３１】
この評価関数によると、図５の輪郭線１のζ＝１．０、輪郭線１２のζ＝０．１、輪郭線１３のζ＝０．２（例えば）となり、ほど良い評価結果を得ている。
【００３２】
次にＲを発生させる。
【００３３】
図７（ａ）にＲの構造を示す。Ｒは座標と輪郭線の接線方向を持つ。又、その総合評価値（＝要不要の度合い）ν（０．５〜１．０）を持つ。他のデータはνを生成するための材料である。
【００３４】
図４に本実施例で出力するＲの目標とする座標を示す。図４（ａ）は直線で挟まれた形状である。この場合、交点に最も近い頂点３４の近傍がＲの目標とする座標である。図４（ｂ）は曲線形状であり、しかも周長においてミクロ的にもマクロ的にも左右対称の場合である。この場合、左右対称の中心線（図示しない）との交点に最も近い頂点４０の近傍がＲの目標とする座標である。図４（ｃ）は直線と曲線で挟まれた形状であり、ミクロ的には左右対称、マクロ的には左右非対称の場合の代表例である。この場合、座標４３と座標４５の中間座標、たとえば座標４４がＲの目標とする座標である。ここで、座標４３はミクロの範囲で得たＲ座標、座標４５はマクロの範囲で得たＲ座標である。
【００３５】
図８はＲ発生部１２０の処理手順を示す流れ図であり、以下この流れに従って順に説明する。
【００３６】
ステップＳ１で、周長Γの列（Γ１、Γ２、・・・）を大きい順に用意する。Γは物体サイズから適当に決めれば良い。
【００３７】
ステップＳ２で、最初のΓ１に位置付ける。Ｒ生成個数ｋを０とする。
【００３８】
ステップＳ３で、次の周長Γがある限り以下の処理を続ける。全てのΓを処理すると終了する。
【００３９】
ステップＳ４で、最初の輪郭線に位置付ける。
【００４０】
ステップＳ５で、区間の始点Ｓ（図９のＳ０）を輪郭線の始点に置く。
【００４１】
ステップＳ６で、次の輪郭線がある限り続ける以下の処理を続ける。全ての輪郭線を処理したらステップＳ３に戻る。
【００４２】
ステップＳ７で、状態遷移のフラグｓｔａｔｅをＯＦＦ（最良山を持っていない）にする。山とは窪み／突起の総称である。
【００４３】
ステップＳ８で、Ｓが輪郭線の終点に達するまで以下の処理を続ける。但し、これは輪郭線が閉じた（＝１周する）ときに必要な処理であって、開いたときは、終点からΓ戻った地点まで到達したら中断してよい。
【００４４】
ステップＳ９で、山検出フラグｍｎｔをＯＦＦ（山ではない）にする。
【００４５】
ステップＳ１０で、Ｓからの周長が初めてΓ以上となる頂点Ｅを探す。即ち、図９において、現在のΓ＝Γ１、現在のＳ＝Ｓ０であり、Ｓから始めて頂点間の距離を積算し続けると、Γ１に等しいか超える頂点Ｅ０に達する。このＳ０からＥ０までを現在区間と呼ぶことにする。
【００４６】
ステップＳ１１で、山形状の事前検査を行なう。これは以下の検査がある。
【００４７】
（１）現在区間の頂点数（Ｓ０とＥ０を除く）が十分多いこと。これは、例えば定数＝３以上とすることができる。但し、定数は任意である。
【００４８】
（２）ヒゲを除くため、開口部の距離Ｓ０Ｅ０がある程度大きいこと。これは、例えば０．２×Γ１以上とすることができる。但し、定数は任意である。
【００４９】
（３）現在区間の頂点（Ｓ０とＥ０を除く）が全て、直線Ｓ０Ｅ０のどちらか一方の側に偏在していること。
【００５０】
（４）現在区間の深さＭ０Ｇ０が十分に大きいこと。これは、例えば０．２×Γ１以上とすることができる。但し、定数は任意である。
【００５１】
Ｍ０は次のように求める。即ち、現在区間の周長をγとするとき（γ≧Γ１）、Ｓ０からの周長を測り、γ／２の地点を求めてこれをＭ０とする。従って、Ｍ０は一般に頂点と頂点の間に落ちるので、線形補間により正確な座標を求めることが重要である。Ｇ０はＳ０Ｅ０の中心である。
【００５２】
以上全ての事前検査を合格したら、次のステップＳ１３に行く。いずれかが不合格ならステップＳ１７に行く。
【００５３】
ステップＳ１３で、交差角度検査を行なう。これはＳ０Ｅ０とＭ０Ｇ０が直交（＝９０°）に近いことを要求する。これは、｜ｃｏｓθ｜≦Ｄ１で判定する。例えば、Ｄ１＝ｃｏｓ８０°とする。但し、定数は任意である。
【００５４】
ステップＳ１４で、左右対称検査を行なう。これは中心線Ｍ０Ｇ０に対して、Ｓ０、Ｅ０の接線方向であるそれぞれβｓ、βｅが同じ角度に開いていることを要求するものである。
【００５５】
演算は次のように行なう。ベクトルＭ０Ｇ０の方向余弦を（ｃｏｓα、ｓｉｎα）とする。Ｓ０の近傍を適当に均すことで、図の向きの接線方向βｓを得ることができる。βｅについても同様である。いずれも方向余弦の形で求めておく。
【００５６】
φｓ＝βｓ−α、φｅ＝βｅ−α、を計算する。
【００５７】
次に、φ＝φｓ＋φｅを計算する。もし、完全な左右対称ならφ＝０°＝（１，０）となる。従ってこの検査では、これは｜ｓｉｎφ｜≦Ｄ２で判定する。例えば、Ｄ２＝ｓｉｎ１０°とする。但し、定数は任意である。
【００５８】
ステップＳ１５で、現在山の評価値ｅ＝｜ｓｉｎθ｜｜ｃｏｓφ｜を計算する。ｅは０〜１の値を持ち、直交に近いほど、左右対称に近いほど１に近付く。１に近いほど良い山である。ｅは山の連続があるとき、最も良い山を見つけるために使われる。
【００５９】
ステップＳ１６で、ｍｎｔをＯＮにする。これは山が一つ見つかったことを示す。
【００６０】
ステップＳ１７で、状態遷移フラグｓｔａｔｅを見る。
【００６１】
ステップＳ１８で、ｍｎｔがＯＮであり、最良山を持っていない場合、ここが山であれば、ステップＳ１９で、最良山に現在山を複写して、最良山の候補とする。即ち、見つかれば直ちに出力するわけではない。ｓｔａｔｅにＯＮをセットする。
【００６２】
ステップＳ２０で、ｍｎｔがＯＦＦであり、最良山を持っている場合、ここが山で無ければ、ここで初めて出力できるので、ステップＳ２１で、最良山をＲとして出力する。ｓｔａｔｅにＯＦＦをセットし、再び山が無い状態とする。
【００６３】
以下、最良山をＲとして出力するときの処理を説明する。
【００６４】
図９において、最良山が仮に区間Ｓ０Ｅ０のものとする。ここで、先に現在区間の記述に使ったＳ０Ｅ０と同じ名称を使うので、混同しないように注意する。
【００６５】
（１）直線Ｓ０Ｅ０と距離が最も大きい頂点Ｐ０を探す。複数あるときはその始端と終端の中央付近の同最大距離の頂点とすればよい。
【００６６】
（２）Ｐ０からＳ０Ｅ０に垂線を降ろし、その足をＨ０とする。
【００６７】
（３）Ｈ０Ｐ０（長さｈ）上、中央付近（例えば、ｈ／４〜（３／４）ｈ内）に、適当な広がりで、Ｈ０からＰ０に向かって、例えば４等分して５個の点列を発生させる。但し、これの位置を決める定数は適当で良い。
【００６８】
（４）各発生点からＨ０Ｐ０に直交（従ってＳ０Ｅ０に平行）する直線を引く（例えば直線５０）。
【００６９】
（５）その直線５０と現在区間のＳ０側、Ｅ０側それぞれの交点５１、５２を求める。
【００７０】
（６）交点間の中点５３を出力する。以上を５本分繰り返す。
【００７１】
（７）５個の中点列から最小２乗近似直線５４を引く。
【００７２】
（８）Ｐ０からその直線５４に垂線を降ろし、その垂線の足をｚ０とする。ｚ０がこの山の出力座標Ｑ１である。
【００７３】
（９）ｚ０における山の接線方向τ０は、ベクトルＨ０Ｐ０を±９０°回転した方向から作る。図９は現在区間が反時計回りであるから、＋９０°回転する（もし時計回りであるなら、−９０°回転する）。
【００７４】
これにより、山の出力Ｑを得ることができる。即ちＱ＝（座標ｚ０、接線方向τ０）である。図１０において、各Γ毎にＱが出力されることに注意する。即ち、Γ１からＱ１、Γ２からＱ２、・・・とΓ５からのＱ５まで続く。
【００７５】
Ｑ１も含めて全ての出力Ｑは、既に登録されている個々のＲのε近傍に入っているかどうかの検査を行なう。これはむやみにＲの個数を増やさないためである。ここでεは適当に定めれば良く、例えば物体長の０．１倍とする。
【００７６】
ここでは１回目のＱ１は登録されるものとする。実際、周りに山が無いからである。登録されたＱのことをＲと呼ぶ。
【００７７】
Ｒのζに現在の輪郭線のζを複写する。
【００７８】
ＲのγにＱ１の区間長γ（Ｓ０からＥ０までの実際の長さ）を複写する。このγは以降の処理で変更してはならない。
【００７９】
又、Ｒの多重度と呼ぶｍを１にする。
【００８０】
Ｒの個数ｋを一つ増やす。
【００８１】
２回目のＱ２はＲのε近傍に入っているので、Ｑ２は登録しない。その代わりＲの修正を行なう役目を持つ。
【００８２】
即ち、図１１において、Ｑ１（＝Ｒ）、Ｑ２の座標をそれぞれｑ１、ｑ２、接線方向（方向余弦）をそれぞれω１、ω２とする。
【００８３】
新座標ｑ´は、ｑ１、ｑ２をΓ２：Γ１に内分して得る。
【００８４】
新接線方向ω´は、ω１、ω２を同じくΓ２：Γ１に内分して得る。このときのやり方としては、開き角度δを求め、δは０°に近いことを利用し（実際ほとんど２°未満である）、ｓｉｎδ（符号付）をΓ２：Γ１に内分すれば良い。即ち、修正角度β（図には無い）のｓｉｎβ＝（Γ２／（Γ１＋Γ２））ｓｉｎδであり、従ってｃｏｓβ＝√（１−ｓｉｎβの２乗）とする。ω´はω１をβ回転したものである。
【００８５】
以上の座標修正、角度修正は非常に重要である。この修正により、Ｒの座標と接線方向を安定することができる。
【００８６】
最後に、Ｒの多重度ｍを一つ上げて２とする。これでＱ２による修正が完了した。
【００８７】
同じことを引き続くＱ３以降でも繰り返す。最終のＱ５まで繰り返したとき、このＲの多重度ｍは５になっている。
【００８８】
多重度の役割については後述する。
【００８９】
ステップＳ２２で、最良山を持っている場合、ここが山であれば、山が連続したことになる。従って、ステップＳ２２で、最良山と現在山で良い方の山を選ぶ。即ち、ステップＳ２３で、現在山の評価値の方が高ければ、最良山に現在山を複写する。もし同じか低ければ何もしない。
【００９０】
ステップＳ２４で、現在山があってもなくてもＳ０を周長δ１移動し、次はＳ１から始める。但し、δ１は頂点位置変位で、例えばδ１＝１（一つずつ移動）とする。但し、この定数は任意である。
【００９１】
以下は新しいＳ１でステップ８から同じことを繰り返す。
【００９２】
なお、ステップＳ２１において、注意すべきは円又は同相の、即ち特徴の無いところから山を出力しないようにすることである。
【００９３】
即ち、図１２において、既に中点で示すところの山Ｍ０が出力されてＲとなっているものとする（直前のＲ）。
【００９４】
その後、山Ｍ１の出力をしようとするが、形状がほとんど直前のＲと同じであることが分かる。
【００９５】
即ち、例えば開口部ＳＥの距離が同じであり、ＭからＳＥまでの距離が同じであり、更にＭ０、Ｍ１それぞれの接線方向βｓ、βｅの相対的な方向が同じであるときは、同じ山であると結論してよい。
【００９６】
このようなときは、山Ｍ１を出力しないことは勿論、直前Ｒそのものも出力リストから抹消する。
【００９７】
ステップＳ３で全てのΓで処理が終了したらＲ発生が終了する。
【００９８】
Ｒ発生が終了したら、次に、Ｒ評価部１２２でＲの評価を行なう。
【００９９】
図６（ｂ）に多重度ｍの評価関数ωの一例を示す。
【０１００】
まず、生成されたＲの集合で、そのｍについて、最大値（ＭＡＸ）と最小値（ＭＩＮ）を得る。図１３は生成されたＲの集合の多重度（Ｍで示す）を示す。ＭＡＸ＝５、ＭＩＮ＝１である。
【０１０１】
特徴として、図１４に例示する如く、より好ましいところの形が良く大きな山には大きな多重度が出力されていること、逆に、形が悪い、あるいは小さい山には小さな多重度が出力されていることに注意する。
【０１０２】
図６（ｂ）に戻って、Ｒのそれぞれに多重度ｍが記入されているから、そのｍで図の関数値ωを得る。ここで使う関数は、図６（ａ）のζ評価のときのものと同じような規則で作ればよい。定数Ｃ２は適当でよく、例えばＣ２＝０．２とすることができる。
【０１０３】
次に図６（ｃ）に長さγの評価関数ψを示す。生成されたＲの集合で、そのγについて、最大値（ＭＡＸ）と最小値（ＭＩＮ）を得る。
【０１０４】
Ｒのそれぞれに長さγが記入されているから、そのγで図の関数値ψを得る。ここで使う関数は図６（ａ）のζ評価のときのものと同じような規則で作ればよい。定数Ｃ３は適当でよく、例えばＣ３＝０．２とすることができる。
【０１０５】
次に、Ｒのそれぞれに、形と大きさの評価値ηをセットする。Ｒのηは、
η＝多重度評価値×長さ評価値＝ω×ψ
である。
【０１０６】
次にＲのそれぞれに、総合評価値νをセットする。Ｒのνは、
ν＝０．５＋０．５ζη
である。この式によると、νは０．５〜１．０の値を持ち、輪郭線の評価値ζが大きく、形と大きさの評価値ηが大きいほど大きい。
【０１０７】
図５で、黒丸はＲであることを示し、そのν値を示している。特徴として、好ましい地点のＲほど大きなνが出力されていることに注意する（Ｒの最小値が０．５であることに注意）。
【０１０８】
特に図１３において、多重度ではＲ６３とＲ６４は共にｍ＝４であり区別できないが、図２ではそれぞれν＝０．９、ν＝０．６と大きく差がついていることに注意する。これは輪郭線の評価値ζの働きによるものである。
【０１０９】
図１５に、出力されたＲを示す。Ｒを物体認識で使う場合には、例えば三角形Ｒ１Ｒ２Ｒ９の形状を学習して記録し、認識のとき同じ形が現われるかどうかを調べればよい。
【０１１０】
図では１２個のＲが出力されているが、この数では必ずしも十分でないことがある。用途によっては外周に関する情報が欲しい場合がある。
【０１１１】
例えば、外周部にランダムに配置される点Ｔは、数が多ければ認識の情報に使うことができる。
【０１１２】
図７（ｂ）に、Ｔの構造を記述する。
【０１１３】
Ｔは座標と輪郭線の接線方向を持つ。又その総合評価値（＝要不要の度合い）ν（０〜０．５）を持つ。
【０１１４】
例えば、三角形Ｒ２Ｒ８Ｔ３を学習したとする。認識においては別画像であるから一般に異なる場所、例えばＴｘに発生する。
【０１１５】
しかし三角形Ｒ１Ｒ８Ｔｘは学習三角形Ｒ２Ｒ８Ｔ３と良く似ているので、学習物体の可能性として出力することができる。
【０１１６】
Ｔが必要か否かはＲの個数ｋに従うのが良い。図１６は、Ｔの必要個数Ｎｔの生成関数である。これも図６（ａ）のζ生成関数と同じ原理でつくることができる（上下を反対にする）。Ｒの十分個数ＲＥは適当でよく、例えばＲＥ＝２５とすることができる。関数はｋ＝ＲＥでＮｔ＝０を出力する、即ちＴは不要である。一方ｋ＝０ではＴＳ個を出力する。ＴＳはＴだけで認識できるための必要個数であり、物体のサイズその他から決めればよい。例えば定数ＴＳ＝８０を割り当てても良い。
【０１１７】
Ｔの発生は至って単純である。即ち、図１５において、各輪郭線の始点にまず発生し、予め計算しておいた距離毎に周を進み、そこに発生する。但しＲのε近傍に入っているときは発生しない。
【０１１８】
Ｔが進む距離は、輪郭線集合全体の距離をＮｔで除した商から決めればよい。
【０１１９】
Ｔのζは輪郭線の評価値の複写である。
【０１２０】
Ｔのνは、ν＝０．５ζとする。これにより輪郭線が最大評価値ζ＝１のときでもν＝０．５となり、Ｒの最小値以下となるので両者を差別する上で都合が良い。
【０１２１】
図５に最終的に出力されたＲとＴを示す。黒丸がＲであり、白丸がＴである。図には書かれていないが、それぞれ輪郭線の接線方向を持つ。ν値は分かり易さのために小数点以下１桁とした。
【０１２２】
これによると、明らかに特徴で使いたいところはνが非常に高く、逆に使いたくない特徴は低い。特に、内部の雑音１２のνは低く、又、外部の雑音１３のνも低いことに注目する。
【０１２３】
このようにして、Ｒ（窪み／突起）の正しい評価値νを得ることができる。νは優れた指針であり、認識対象で、しかも強い特徴ほど大きなνとなって現われる。
【０１２４】
即ち、
ν＝０．５＋０．５ζη
＝０．５＋０．５ζ（λ）ω（ｍ）ψ（γ）
とすると、ζ（λ）は母体輪郭線の長さλが大きいほど大きい。ω（ｍ）は多重度ｍが大きいほど大きい。ψ（γ）は周の長さγが大きいほど大きい。以上により、ν値は３項全てが大きいときのみ大きくなるのであって、これはＲの正しい評価値となっている。
【０１２５】
特に、図６（ａ）、（ｂ）、（ｃ）に示すとおり、ζ（λ）、ω（ｍ）、ψ（γ）は、それぞれλ、ｍ、γの値の範囲（ＭＡＸとＭＩＮ）に従う関数であることに注意する。即ち評価値が高いか低いかは、その集合のＭＡＸ値とＭＩＮ値による。
【０１２６】
例えば図６（ｂ）において多重度ｍの評価値ω（ｍ）はｍの範囲による。即ち先に言及したが、図２に例示した如く、円形物体１´があって、その円周上にわずかに窪み／突起６、７がある場合、それらの多重度が例えばｍ＝１とｍ＝２だけのときがある。その場合、ＭＡＸ＝２、ＭＩＮ＝１であり、ｍ＝２を得たものは最大評価値ω＝１となる。これは、その窪み／突起の多重度の正しい評価値である。
【０１２７】
ここで、多重度ｍは窪み／突起の深さ（高さ）と形の良さを表わす指標である。
【０１２８】
即ち、図１４において、（ａ）、（ｂ）、（ｃ）は、いずれも同じ開口長ｅを持つ窪み（突起）である。しかし、図のように多重度はそれぞれ異なっている。（ｂ）の多重度が（ａ）に較べて小さいのは深さ（高さ）が小さいからであり、（ｃ）の多重度が（ａ）に較べて小さいのは先端部の形が悪いからである。
【０１２９】
このように、多重度ｍの値は窪み（突起）が深いほど（高いほど）、又形が良いほど大きいのでＲの評価の一つとして有効である。
【０１３０】
又、Ｒ単独、又はＲとＴの組合せで認識を行なうことができる。その際に、それぞれの評価値νは優れた指針であり、良いＲ又は良いＴだけを取り出して最高の集合をつくることができる。これにより、外周に殆ど特徴が無いような曲線物体でも認識が可能になる。
【０１３１】
なお、実施例では評価値生成関数として、２次関数を使ったが、単調に増加あるいは減少する関数であれば何でも良い。極端な例として直線でも良い。その場合でも効果は殆ど変わらない。
【０１３２】
又、実施例では多重度ｍで評価できる輪郭線の特徴としてＲ（窪み／突起）を用いた。しかし、Ｒ以外にも存在する。例えば、Ｌ（直線）やＣ（円）等がその例である。
【０１３３】
図１７の（ａ）は輪郭線の直線部（Ｌ）が長さの異なるΓ（図示しない）で抽出されたものである。このときにも、使われたΓの長さが５個なら、ｍ＝５とすればよい。（ｂ）に示すように、凹凸の激しい区間があり、長い距離で見れば直線として検出可能で、逆に短い距離では検出不可能であるような場合、図のように３個の長さだけで検出されたので、多重度ｍ＝３である。
【０１３４】
図１８は、輪郭線の円弧部（Ｃ）の長さが異なるΓ（図示しない）で抽出されたものである。このときも、使われたΓの長さが５個なら、ｍ＝５とすればよい。
【０１３５】
このように多重度は輪郭線から抽出されるあらゆる特徴形状に存在するのであって、その特徴形状の大きさと、形の良さを表わす尺度となり得る。
【図面の簡単な説明】
【０１３６】
【図１】曲線物体の形状の一例を示す図
【図２】円形物体の一例を示す図
【図３】本発明を実施するための図形特徴データ抽出装置の主要部構成を示すブロック図
【図４】Ｒの目標座標を示す図
【図５】本発明による評価値の付与例を示す図
【図６】本発明で用いる評価関数の例を示す図
【図７】同じくＲとＴの構造を示す図
【図８】同じくＲ発生の処理手順を示す流れ図
【図９】同じく実施例の処理方法を説明するための図
【図１０】同じく処理方法を説明するための図
【図１１】同じく処理方法を説明するための図
【図１２】同じく処理方法を説明するための図
【図１３】同じく処理方法を説明するための図
【図１４】本発明の多重度を示す図
【図１５】実施例の処理方法を説明するための図
【図１６】同じくＴの必要個数Ｎｔの生成関数の例を示す図
【図１７】輪郭線の直線部の抽出例を示す図
【図１８】輪郭線の円弧部の抽出例を示す図
【符号の説明】
【０１３７】
１、１´、１２、１３…輪郭線
１０４…画像入力部
１０６…画像輪郭線抽出部
１１０…図形特徴データ抽出部
１１２…図形特徴データデータベース
１２０…Ｒ発生部
１２２…Ｒ評価部
１２４…Ｔ発生部
１２６…Ｔ評価部
１３０…制御部
【特許請求の範囲】
【請求項１】
画像から曲線物体の輪郭線を抽出し、その特徴を評価する際に、
特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求め、
該多重度に応じた評価値を用いることを特徴とする曲線物体輪郭線の特徴評価方法。
【請求項２】
前記多重度を用いて、輪郭線の山の特徴を評価することを特徴とする請求項１に記載の曲線物体輪郭線の特徴評価方法。
【請求項３】
請求項１又は２において、更に、輪郭線上にランダムに発生させた不定点に応じた評価値を加えることを特徴とする曲線物体輪郭線の特徴評価方法。
【請求項４】
前記不定点の評価値の最大値が、山の評価値の最小値よりも小さくなるようにしたことを特徴とする請求項３に記載の曲線物体輪郭線の特徴評価方法。
【請求項５】
画像から曲線物体の輪郭線を抽出し、その特徴を評価する曲線物体輪郭線の特徴評価装置において、
特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求める手段と、
該多重度に応じた評価値を求める手段と、
を備えたことを特徴とする曲線物体輪郭線の特徴評価装置。
【請求項１】
画像から曲線物体の輪郭線を抽出し、その特徴を評価する際に、
特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求め、
該多重度に応じた評価値を用いることを特徴とする曲線物体輪郭線の特徴評価方法。
【請求項２】
前記多重度を用いて、輪郭線の山の特徴を評価することを特徴とする請求項１に記載の曲線物体輪郭線の特徴評価方法。
【請求項３】
請求項１又は２において、更に、輪郭線上にランダムに発生させた不定点に応じた評価値を加えることを特徴とする曲線物体輪郭線の特徴評価方法。
【請求項４】
前記不定点の評価値の最大値が、山の評価値の最小値よりも小さくなるようにしたことを特徴とする請求項３に記載の曲線物体輪郭線の特徴評価方法。
【請求項５】
画像から曲線物体の輪郭線を抽出し、その特徴を評価する曲線物体輪郭線の特徴評価装置において、
特徴を含む設定区間を、特徴に向けて順次せばめて行った際に、特徴が再び検出された時のくり返し検出数である多重度を求める手段と、
該多重度に応じた評価値を求める手段と、
を備えたことを特徴とする曲線物体輪郭線の特徴評価装置。
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１】
【公開番号】特開２００９−１６３３８３（Ｐ２００９−１６３３８３Ａ）
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願番号】特願２００７−３４０６５８（Ｐ２００７−３４０６５８）
【出願日】平成１９年１２月２８日（２００７．１２．２８）
【出願人】（０００００３３９９）ＪＵＫＩ株式会社 (1,557)
【Ｆターム（参考）】
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願日】平成１９年１２月２８日（２００７．１２．２８）
【出願人】（０００００３３９９）ＪＵＫＩ株式会社 (1,557)
【Ｆターム（参考）】
[ Back to top ]