ボール部品の認識方法及び装置
【課題】難認識で知られる非格子配置（ランダム配置）ＢＧＡに対して、強力な認識能力を発揮することが可能なボール部品の認識方法及び装置を提供する。
【解決手段】画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置を用いて、ボール部品を画像により認識する方法であって、画像からボール電極の座標を次々と抽出し、画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納し、経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力し、画像抽出電極座標と前記予測領域の包含を判定し、包含されると判定されたとき、節を追加して経路を成長させ、経路とボールパターンを照合する。
【解決手段】画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置を用いて、ボール部品を画像により認識する方法であって、画像からボール電極の座標を次々と抽出し、画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納し、経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力し、画像抽出電極座標と前記予測領域の包含を判定し、包含されると判定されたとき、節を追加して経路を成長させ、経路とボールパターンを照合する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ボール部品の認識方法及び装置に係り、特に、電子部品の表面実装装置における画像によるボール電極部品（ＢＧＡ）の認識に用いるのに好適な、ＢＧＡの中でも、特に、難認識で知られる非格子配置（ランダム配置）ＢＧＡに対して強力な認識能力を発揮することが可能なボール部品の認識方法及び装置に関する。
【背景技術】
【０００２】
電子部品の表面実装装置において、電子部品は部品供給装置（フィーダ）から供給され、吸着ノズルにより吸着されて回路基板に実装される。吸着ノズルは、必ずしも正しい姿勢で電子部品を吸着するとは限らないので、通常ＣＣＤカメラ等により吸着部品が撮像されて部品認識が行なわれ、正しい姿勢で吸着されていない場合には、認識結果に基づき位置補正や傾き補正等が行なわれている。
【０００３】
図１に格子配置ＢＧＡの一例を示す。現在、市場のほとんどのＢＧＡは格子配列である。図１において、実線の円１５は、電極であるところの半田ボールである。ボールは、縦×横＝４×５の格子位置に整列している。破線の円１６は、欠けボール（存在しないボール）である。格子配列であるから、各ボールの位置は、例えば左上角の仮想ボール１７を（０，０）とする縦方向の位置指標０，１，・・・と横方向の位置指標０，１，・・・で指定できる。
【０００４】
部品認識のために適当なボールを選び、その中心座標に原点を置くＵＶ座標系（部品座標系）を貼ることが多い。このときＵ方向のピッチＰｕとＶ方向のピッチＰｖが与えられる。
【０００５】
図中ＦＢ（False Ball）は偽電極である。偽電極は、画像による認識のときに結果としてボールとして誤認識される異物の総称である。それは、パッケージ１８の一部であったり、ボール間を走る配線パターンの形状であったりなど様々である。偽電極があると認識に支障が出ることが多いが、偽電極の混入は予測困難である。当然ながら認識すべきボールパターンの定義に偽電極は含まれていない。
【０００６】
図２に、非格子配置ＢＧＡの一例を示す。電極の座標は乱れた位置にある。市場では少数派であるが、このような非格子配置ＢＧＡが存在し、その認識が困難であり、問題になりつつある。
【０００７】
この非格子配置ＢＧＡにおいても、認識のために部品の適当な位置を選び、そこに原点を置くＵＶ座標系を貼る。各ボールの位置はＵＶ座標系で記述される。ボールの定義順は任意である。この例では、１０個のボールが指標０，１，・・・，９で示す順に定義されている。
【０００８】
なお、格子、非格子いずれの型においても、ＢＧＡの電極数は数個（５〜６個）から多いものでは２０００個を越えるものまである。
【０００９】
図３に部品認識の必要性を示す。電子部品実装装置（チップマウンタとも称する）のカメラにより撮像された入力画像１（白黒濃淡画像）があり、この中にＢＧＡ部品２の腹側（基板側）が映っている。部品を吸着するノズルが部品の背中を吸着するとき、位置ずれと回転ずれが入ることは避けられない。
【００１０】
この部品が、基板の上の決められた位置に決められた角度で正しく載せられるためには、部品に貼り付けた座標系（ＵＶ座標系）の原点座標と傾きが、画像の座標系（ＸＹ座標系）で精度良く記述される必要がある。即ち、そのデータが分かれば位置補正と角度補正が可能となる。
【００１１】
そのためには、ＵＶ座標系において、ボールの中心座標を持って定義されるボールパターンについて、各ボール電極の中心座標がＸＹ座標で獲得されることが必要である。なお、画像においてボールパターン全体が十分に含まれるような探索領域３は予め分かっているものとする。
【００１２】
従来の方式は、例えば特許文献１に見ることができる。図３において、特許文献１の方式では、最初にボールパターンの角の（正確には角付近の任意の）ボール６を抽出し、それを元に残りのボールを抽出することが特徴である。そのために小窓と呼ぶ独特の手法を用いている。
【００１３】
小窓によるボール電極の中心座標の抽出方法については、特許文献２に詳しく記述されている。それによると、小窓は画像に被せる小さな円形領域であり、その中にボールの全体が完全に入っているとき、ボール電極の中心座標を抽出する。小窓の大きさはボールの直径から決まる。
【００１４】
小窓を最初は部品２の角方向の探索領域３の隅４の位置に置き、小窓の中にボール像が存在するかどうかを調べる。存在しなければ左又は下に少しずらした位置で調べる。この探索は、規則正しく角から三角形状に広がるように行なう。そして、探索位置が小窓５の位置に来たとき、ボール電極６の中心座標が抽出される。
【００１５】
最初に抽出されるボールは、必ずしもボール６とは限らない。例えばボール８かもしれない。そのため、予め入力ボールパターンを調べて、角を中心とした数個の電極を選んで候補電極としている。それにより最初に抽出されたボールが真の電極ならば、候補電極のどれかであることが高い確率で保証されるとしている。
【００１６】
候補電極個々を中心として、周りの電極を画像から順次抽出し、観察された電極の配置とボールパターンを照合する。抽出電極の個数が増えてゆくに連れて、真の候補電極以外は矛盾が生じて消滅する。
【００１７】
もし唯一つになるまで生き残った候補電極があれば、それが最初の抽出電極であったと結論する。即ち、このとき既にボールパターンの角を中心とした数多くの定義電極について、個々の電極から画像抽出電極への写像がある。これを基にＵＶ座標系からＸＹ座標系への精度の良い座標変換式を生成する。
【００１８】
ボールパターンの残りの定義電極がもしあれば、生成された座標変換式で画像位置を予測した後、小窓を使って抽出する。部品に偽電極７があるときは、小窓により最初に抽出される電極は、この偽電極であるかもしれない。その場合、全ての候補が消滅して、偽電極の排除が行なわれる。
【００１９】
即ち、基準位置、例えば左下角から最も遠い電極（７）を偽電極と見做して抹消し、その残りの電極集合のうちで左下角から最も遠い電極（６）を新たに最初の電極と見做して処理を続行する。偽電極排除を行なう限界回数は、ボールパターンの電極数等から適当に定めている。
【００２０】
【特許文献１】特開２００１−２８４９００号公報
【特許文献２】特開２０００−２３２２９９号公報
【発明の開示】
【発明が解決しようとする課題】
【００２１】
しかしながら、上記の従来技術は、次のような問題点を有する。
【００２２】
（１）偽電極対策が完全でなく、偽電極に弱い。
【００２３】
まず、偽電極の個数に強く依存して認識時間がかかる。即ち、角付近に偽電極が多いと、最初の偽電極を抹消しても次に選ばれる電極が又偽電極であり、その次も又偽電極であり、・・・と続くことがある。その場合、真の電極に至るまでに長い時間がかかる。しかし、部品実装装置には搭載タクトがあり、一定の時間内に認識しなければならない。偽電極の個数に強く依存して認識時間がかかっていては、搭載タクトに間に合わなくなる恐れがある。従って、偽電極の個数に強く依存しないような方式が望まれる。
【００２４】
次に、電極間内の相対位置関係が微妙にずれると、真の電極が偽電極と見做されることがあり、その排除を防止できない。そして、真の電極が抹消されてしまうと、それ以降の照合が難しくなり、認識できなくなる。即ち、ある真の電極（図３の電極６）から出発した場合、周辺電極の抽出中に偽電極（図３の電極１０）が紛れ込むこともあるし、正しい電極であるが、その位置がずれて抽出される（実質的に偽電極と同じ）こともある。その結果、位置関係が狂い、候補電極全てが消滅することが起きる。このとき、左下角から最も遠い電極として、出発点である真の電極（図３の電極６）が偽電極と見做されて抹消されるが、これを防ぐことができない。従って、抽出電極を抹消することなく認識する方式が望まれる。
【００２５】
（２）使い勝手が悪い。即ち、部品の中にはサイズの大きいものがあり、カメラの視野に入り切らないことがある。
【００２６】
このとき敢えて従来方式で認識しようとすれば、図４に例示する如く、ノズル１１で部品２を吸着した後、カメラの視野を部品２の角の方向にオフセット移動し撮像する。次に撮像した部品の部分画像（角部が映っている）１２で認識する必要がある。
【００２７】
しかし、このとき認識において使うことのできるボールパターン（電極の個数）が小さすぎて、位置決め認識できないことがある。
【００２８】
即ち、画像による認識が安定して行なわれるためには、部品２が吸着ノズル１１により吸着されるときに必ず発生する位置のずれと角度のずれに拘わらず、如何なるときにも必ず含まれるような最大のボールパターンが必要で、それが大きいほど良いことは言うまでもない。
【００２９】
一般にボールパターンの大きさは、角部認識の場合、部分画像２のフレームから部品２の一部が外れるので小さくなり、中央部認識の場合、部品２が必ず部分画像１２のフレーム内に入るので大きいと言える。何故ならば、吸着ノズルは部品の中央部を吸着するからである。即ち、吸着角度のずれによる位置ずれは、ノズル中心から遠いほど大きくなる。従って、部品の角部にこだわらず、部品の任意の部分を使って認識できることが望ましい。
【００３０】
（３）部品認識の時間のばらつきが大きい。即ち、図３において、ボールパターンは探索領域３の何処にでも位置し得る。角のボール６の探索に関して、それが画像の角４に近いときは、より早く見つかり、全体の認識時間も小さいが、逆に画像の角４から遠いときは、より遅く見つかり、全体の認識時間が大きい。更に、例え部品の中心位置が同じでも、部品の角度が異なれば、同じ理由により認識時間に大きな差が出ることになる。従って、認識時間のばらつきが小さいことが望ましい。
【００３１】
本発明は、前記従来の問題点を解決するべくなされたもので、非格子配置のＢＧＡであっても、高精度且つ迅速な位置認識を可能とすることを課題とする。
【課題を解決するための手段】
【００３２】
本発明は、画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置を用いて、ボール部品を画像により認識する方法であって、画像からボール電極の座標を次々と抽出し、画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納し、経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力し、画像抽出電極座標と前記予測領域の包含を判定し、包含されると判定されたとき、節を追加して経路を成長させ、経路とボールパターンを照合することにより、前記課題を解決したものである。
【００３３】
又、前記ボール電極の座標を、ボール電極の中心座標とし、前記経路の節を、画像抽出電極座標とボールパターン定義電極位置指標を結合したデータとし、前記経路の大きさ即ち節の数を使ってボールパターンとの一致を判定するようにしたものである。
【００３４】
又、前記経路の大きさが、所定の一致判定数Ｈ（Ｈは１≦Ｈ≦Ｐである整数、Ｐはボールパターンの電極個数）以上のとき、認識成功即ちボールパターンの完全一致とみなすようにしたものである。
【００３５】
又、前記画像の中に座標Λを定め、この座標Λから概ね近い順に電極を抽出し、ボールパターンにおいて経路が踏んでいない残りＰ−Ｎ個（Ｐはボールパターンの電極個数、Ｎは経路の節数）の定義電極の各電極の画像予測領域を生成し、既存経路Γがあり、Γが成長してΓ’となりうるとき、Γを保存したまま新たにΓ’を生成して登録し、１つの画像抽出電極があるとき、ボールパターン個々の定義電極と結合した大きさ１の経路を生成して登録するようにしたものである。
【００３６】
本発明は、又、ボール部品を画像により認識するための、画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置において、画像からボール電極の座標を次々と抽出する手段と、画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納する手段と、経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力する手段と、画像抽出電極座標と前記予測領域の包含を判定する手段と、包含されると判定されたとき、節を追加して経路を成長させる手段と、経路とボールパターンを照合する手段と、を備えたことを特徴とするボール部品の認識装置を提供するものである。
【発明の効果】
【００３７】
本発明は、偽電極に極めて強く、偽電極があっても認識時間がかかり過ぎることが無い。
【００３８】
即ち、本発明においては、画像から抽出した電極は、経路表に記録されることはあっても抹消されることはない。即ち、常に新しく入った電極とのパターン一致判定処理が行なわれ、過去に入ったかもしれない偽電極には関知しない。そのため、抹消そのものが不要となる。
【００３９】
又、偽電極があると、全く無いに比べて認識時間は大きくなるが、それは、偽電極を含んだ経路が成長するためである（大きさ１を含む）。しかし、偽電極を含んだ経路は早い段階で成長が止まるので、原理的に認識時間に大きな影響は与えない。
【００４０】
又、電極の抹消を行なわないので、正しい電極が抹消されることがない。これにより、正しい電極から始まる経路が必ず生成され、それは成長し、最後に大きさが一致判定数Ｈに達して認識が成功する。従って、少なくとも偽電極の存在が直接の原因で認識が失敗することはない。
【００４１】
又、本発明においては、与えるボールパターンは、部品のボール集合の全部でもよいし、任意の一部でも良く、使い勝手が良い。何故ならば、与えられたボールパターンの各電極は画像の中にあり、Λ中心の探索の過程で何時かは必ず画像から抽出される。その結果、パターンの完全一致、即ち認識が成功する。従来方式のときに問題となった、カメラの視野に入り切らないほど大きい部品の場合は、ボールパターンとして、部品中央部の電極を定義し、部品を吸着した後、通常の撮像、即ちカメラの視野中心とノズル中心を一致させて撮像し（部品の中央部が映っている）、次に、撮像した画像で部品認識すればよい。従って、従来方式で煩わしかったオフセット移動と角部のボールパターン作成が不要となる。
【００４２】
更に、部品認識の認識時間はほぼ一定であり、ばらつきが小さい。部品の全ての電極をボールパターンとして定義した場合を想定すると、画像の中に設けた探索領域のほぼ中央にボールパターンが映っているはずである。認識時間は、電極抽出時間と経路表照合時間の和である。
【００４３】
例えば探索の中心Λを探索領域の中央に設定すると、電極抽出を開始して、直ぐに最初の電極を抽出する。２番目以降の電極も同じである。
【００４４】
１番目を抽出するための処理時間、２番目を抽出するための処理時間、・・・これらは画像により一定ではない。しかしパターンの完全な一致を確認できるＨ個について、そのＨ番目までの総和時間（電極抽出時間）を考えると、これは統計的にほぼ一定となる。
【００４５】
一方、経路表の照合における処理時間は、１番目に要する処理時間、２番目に要する処理時間、・・・これらは、どの電極が先にするかで一定ではない。しかし、Ｈ番目までの総和時間（経路表照合時間）を考えれば、これも統計的にほぼ一定となる。
【００４６】
更に、認識のロジックに柔軟性があり、難認識条件に強いので、非格子配置ＢＧＡ部品を確実に認識できる。即ち、真の電極について、その映りが悪い、あるいは位置がずれている等の理由で、予測した位置で画像抽出できないことが起こる。このとき、ボールパターンの電極個数Ｐが一致判定数Ｈより十分に大きければ、１個の電極が抽出されないことは大きな問題ではない。何故ならば、Ｐ個のうちのＨ個が抽出され、そのＨ個がボールパターンの部分グラフと一致すればボールパターンの完全なる一致と見做すロジックだからである。
【００４７】
なお、本発明は、非格子配置ＢＧＡだけでなく、格子配置ＢＧＡにも適用できる。即ち、格子配置の場合、適当な電極にＵＶ座標系を設けて、個々の電極を座標（ｕ，ｖ）で記述すれば、非格子配置ＢＧＡの認識の一つとして扱うことができる。
【発明を実施するための最良の形態】
【００４８】
以下図面を参照して、本発明の実施形態を詳細に説明する。
【００４９】
図５に、本発明を実施するための部品認識装置の基本的な構成を示す。この部品認識装置は、主に、画像入力部１００と、ボールパターン認識部１１０と、部品認識部１２０と、制御部１３０とから構成される。
【００５０】
前記制御部１３０は、全体を制御する。即ち、次のＢＧＡ部品を選び、その部品データを生成し、画像を取り込み、画像による部品認識を行ない、その認識データにより装置を駆動する。
【００５１】
前記画像入力部１００は、吸着ノズルにより吸着されたＢＧＡ部品を撮像して、画像メモリ（図示省略）に取り込む。
【００５２】
前記部品認識部１２０は、画像による部品認識を行なう。即ち、渡された部品データと画像により、ＸＹ座標系におけるＵＶ座標系の位置と傾きを出力するまでの一連の作業を行なう。即ち、一般に部品は１個でも、図６に例示する如く、認識すべきボールパターンは１個以上（図６では３個）あり、それらの全パターン（図６では右上角のパターンＰ１、左下角のパターンＰ２、周囲を除く中央のパターンＰ３）が同時に渡される。部品認識部１２０は、渡されたパターンのうち、まず最も大きなボールパターン、即ち電極数が最も多いボールパターン（図６ではＰ３）を選ぶ。次に、選んだボールパターンを画像と共にボールパターン認識部１１０に送り、そこで認識させる。そして、最初のパターンＰ３から、ＸＹ座標系におけるＵＶ座標系の原点位置と傾きを出力する。
【００５３】
次に、存在すれば２番目以降のボールパターンＰ１、Ｐ２を同様にボールパターン認識部１１０に送り、今度は予測により電極を認識させ、以降これを繰り返す。
【００５４】
一方、ボールパターン認識部１１０は、与えられた１個のボールパターンについて、入力画像の中で認識する。各ボール電極の中心座標を画像から抽出した後、呼び出した部品認識部１２０に返す。
【００５５】
次に、図７を参照して、本発明に係るボールパターン認識部１１０の動作の概要を説明する。なお、ステップ番号は、後出図８の詳細図に対応させている。
【００５６】
まず、ステップＳ１で、ボールパターンの大きさＰ（＝電極数）から一致判定数Ｈを決める（１≦Ｈ≦Ｐ）。
【００５７】
次に、ステップＳ２で、画像の探索領域の中に適当な座標を探索中心座標Λとして１点定める。
【００５８】
次に、ステップＳ４で、その座標Λに近い順に画像から次々と電極を抽出する。
【００５９】
次に、ステップＳ７で、抽出と同時にボールパターンとの照合を行なう。即ち、ボールパターンの個々の電極を出発点とし、ボールパターン自身の電極を結んでできる部分経路（生成経路）が表の形で既にあるものとする（最初は０個）。生成経路は、あれば、その大きさ（＝電極数）は１から始まる。
【００６０】
画像から電極が抽出される度に表中の生成経路を順に巡る。ある生成経路に今回の抽出電極を付加したものが再びボールパターンの部分経路と一致するなら、その元の経路を複写した後、抽出電極を付加した新しい生成経路を作り、経路表に登録する。
【００６１】
一方、ボールパターン個々の電極と、抽出した１個の電極を結合した大きさ１の生成経路Ｐ個は無条件に登録される。
【００６２】
電極の抽出を続けると、生成経路の大きさがＨに等しくなって、ステップＳ２１の判定条件が成立することがある。このとき認識は成功であり、ステップＳ２２で、この生成経路を出力する。
【００６３】
図２のＢＧＡを使って具体的に説明する。ボールパターンの大きさはＰ＝１０である（ボール指標０〜９）。一致判定数Ｈは、ここではＨ＝１０となる（後述）。
【００６４】
図３において、画像探索領域３の中に座標Λを定める。Λは、ボールパターンの近くにあれば何処でも良い（後述）。
【００６５】
座標Λに近い順に画像から次々と電極を抽出する。例えば電極ａ、ｂ、ｃ、ｄ、・・・の順に抽出される。
【００６６】
生成経路は最初０個である。
【００６７】
電極ａが抽出されたとき、大きさ１の生成経路が１０個できる。それらはボールパターンの各定義電極と座標ａを結合したものである。
【００６８】
次の電極ｂは偽電極であるが、この時点では判らない。電極ａと電極ｂの位置関係（距離と角度）を満足する生成経路として、図２における電極９と電極１を結ぶ大きさ２の生成経路が新たに登録されるかもしれない。このときの距離誤差と角度誤差については後述する。
【００６９】
一方、電極ｂ単独の大きさ１の生成経路も１０個できる。それらはボールパターンの各定義電極と座標ｂを結合したものである。
【００７０】
次の電極ｃ以下でも同じことを繰り返す。
【００７１】
図８に最終結果を示す。電極ａから始まり実線矢印で繋がる黒丸ａ、ｂ、ｃ、ｄ、・・・、ｋ、ｍは抽出電極である（この場合、図３の電極７は抽出されないまま終了する）。
【００７２】
電極ｍに対する処理が終了した時点で登録されている生成経路を調べてみると、その中に電極ａから始まり点線矢印で繋がる（点線が無いものは実線）大きさ１０＝Ｈの経路（ａ，６）、（ｃ，０）、（ｄ，１）、・・・、（ｋ，４）、（ｍ，５）がある。
【００７３】
この事実により認識は成功であり、この生成経路を出力して終了する。以上が認識の一例である。
【００７４】
図９に、ボールパターン認識部１１０における処理の流れ図の詳細を示す。
【００７５】
以下、図１０にボールパターンを示す簡単なＢＧＡを使って、図９の各ステップの処理を詳しく説明する。このＢＧＡは３個の電極（位置指標０、１、２）からなり、図１１にその部品画像を示す。ボールパターンの電極ａ、ｃ、ｅと共に、偽電極ｂ、ｄも映っている。
【００７６】
（１）ステップＳ１
定義パターンの電極数Ｐを３とし、一致判定数ＨをＰ以下の整数とする。Ｈは照合の高速化のために設けた数で、ボールパターンＰ個のうち画像抽出電極Ｈ個が一致したとき、パターン全体の完全なる一致であると見做すことができる数である。ＨはＰの関数であり、実施例では、経験に基づいて、Ｈ＝ｍａｘ｛２０，Ｐ／８｝とした（整数）。但し、ＨはＰを超えない。
【００７７】
即ち、パターン全体の一致の信頼性に関して、小さいパターン（Ｐ≦１６０）までは、一定数（Ｈ＝２０）が一致すれば十分であるとした。一方、大きいパターン（Ｐ＞１６０）に対しては、その一定比率（Ｐ／８）が一致すれば十分であるとした。従って、この例ではＨ＝３となる。
【００７８】
（２）ステップＳ２
メモリに経路表を確保し、経路登録個数Ｋを０にする。図１２に経路表を示す。図１２（ａ）にはＫ＝３個の経路が登録されている。経路表はメモリアドレスを要素とする配列であり、各要素には経路の先頭アドレスが書き込まれる。経路表の大きさ、即ちメモリアドレス登録個数の容量としては、積Ｐ×Ｈの値を基に決めると良い。実施例では、経験に基づいて、経路表の大きさ＝４×Ｐ×Ｈ＋１００とした。ここで係数４はＰが大きいときの安全係数であり、加算数１００はＰが小さいときに偽電極が多いときの対策である。従って、この例では、経路表の大きさ＝４×３×３＋１００＝１３６（個）となる。
【００７９】
（３）ステップＳ３
探索中心座標Λを決める。Λは、画像中任意の座標でよい。実施例では、画像探索領域の中心座標とした。
【００８０】
（４）ステップＳ４
探索中心座標Λから近い順に、画像から電極を抽出する。抽出は電極が枯渇するまで続ける。図１３に電極の探索経路を示す。この同心円、即ち探索円に沿って電極を探す。Λを中心とする半径Ｒ０の円があり、これは最初の探索円である。δは探索円の半径の増分である。Ｒ０とδは、ボール電極を画像から抽出する方法により異なる。
【００８１】
画像からボール電極を抽出する方法は種々あるが、本発明においては、どの方法を使っても良い。
【００８２】
図１４は、その１つの方法を示す。この場合、ボール直径をφ（＝２ｒ）とすれば、例えばＲ０＝２φ、δ＝φ／６（経験式）とすればよい。
【００８３】
図１４において、暗い背景に明るく映っているボール電極２０の中心座標２１を抽出したい。一般にボール電極には配線パターン２２があり、ボールと同じような輝度で映っている。円２３、円２４、・・・は探索円である。画素明度に関してある閾値が与えられているものとする。円の軌道上の画素明度の変化を調べると、円２４の座標２５において明度の変化（閾値に関して低→高）がある。この座標における明度勾配ベクトル（例えば暗い方から明るい方へ向かうベクトル）２７を得る。
【００８４】
ｒ＝φ／２は定義電極の半径である。座標２５から明度勾配ベクトル２７方向に距離ｒの座標２８を記録しておく。この座標は、電極中心座標の一つの候補である。
【００８５】
次に、円２４の座標２６において、再び明度の変化（閾値に関して高→低）がある。上と同様に１つの候補座標を記録する。
【００８６】
探索円を１周するまで同じことを繰返し、更に次の探索円でも同じことを繰り返す。
【００８７】
電極の座標計算は、探索円を一定の本数ずつまとめた探索帯毎に行なう。探索帯の本数は、δ＝φ／６により、ボール当り平均６本走るので、それより大きい適当な数、例えば１０本とすれば良い。
【００８８】
探索帯１個分の探索円発生が終了したとき、その内部の電極個々の中心には候補座標が集まっていることが期待できる。
【００８９】
画像を適当にブロック分割し（例えば辺の長さ＝０．５φの正方形）、今回の探索帯に接触するブロック（例えばブロック２９）内の候補座標を数える。一定個数（例えば６個）以上であれば、その点列の重心座標を円の中心座標として出力する。このときブロック同士の境界が円の中心付近を通過するときは、結合して数える等の処置を行なう。
【００９０】
探索帯内部の電極抽出が終了したら、電極をΛから近い順に並べ替え、先頭から順に出力する。
【００９１】
以下、探索帯の発生と、その探索円の発生と、電極の抽出とを繰り返す。
【００９２】
なお、この方式では、初期半径Ｒ０の円内にある電極、特に、その中心を偶然Λに置くような電極の抽出を必ず行なう。もしあれば、この電極が最初に出力されるべきである。
【００９３】
即ち、図１４において、円３０は初期半径Ｒ０の円であるとする。この円の周が、長さδで分割されるように、Λからこの円に放射線分、即ち、線分３１、線分３２、・・・を１周するまで引く。
【００９４】
各放射線分について、探索円のとき行なったと同じ処理を行なう。これにより、初期半径Ｒ０の円内にある電極を抽出できる。
【００９５】
図１５に電極抽出の別の方法を示す。この場合、ボール直径をφとすれば、例えばＲ０＝０、δ＝φ／３（経験式）とすることができる。
【００９６】
最初はΛの１点、以下は半径をδずつ増分した探索円、その探索円の周を更に周長δで分割する各点において、小窓抽出と呼ばれる以下の処理を行なう。
【００９７】
図１５において、座標３５が画像上指定された座標、即ちΛ若しくは探索円の分割点である。円３６は、座標３５を中心とする半径φ（直径＝２φ）の円であり、これを小窓と呼ぶ。
【００９８】
小窓の中に偶然入っている、暗い背景に明るく映っているボール電極２０の中心座標２１を抽出したい。一般にボール電極には配線パターン２２があり、ボールと同じような輝度で映っている。小窓による方法は、特に配線パターンの存在に強いのが特徴で、図のように２本程度までなら問題ない。
【００９９】
画素明度に関して、ある閾値が与えられているものとする。小窓内部の画素明度を２値化すれば、２値化電極像の外周を矢印３８の方向に進み、１周して元の位置に戻る閉路が得られる（閉路は小窓の外には出ず、小窓の経路３９、経路３４を通る）。
【０１００】
得られた閉路上に、円周上の弦の候補である弦ＡＡ’、ＢＢ’をとる。それぞれ安定した経路上に発生していること、直径になるべく近いこと、互いに直交に近いこと・・・等の諸条件を満たす。このとき、それぞれの弦の垂直二等分線の交点を、円の中心座標２１として出力する。
【０１０１】
探索円を１周する間に小窓から出力された電極座標をΛから近い順に並べ替え、先頭から順に出力する。
【０１０２】
図１１の例において、出力順はａ→ｂ→ｃ→ｄ→ｅとする。
【０１０３】
（５）ステップＳ５
抽出電極の画像座標をｚとする。即ち最初の座標はｚ＝ａである。
【０１０４】
（６）ステップＳ６
今回の抽出座標により新たに発生する生成経路の数を初期化する。即ち新規発生経路数Ｇを０にする。そして、経路の読出し位置を経路表の先頭に位置決めする。
【０１０５】
（７）ステップＳ７
Ｋ回繰り返される。しかし、今、Ｋ＝０なので、Ｓ７以降をスキップしてＳ１９に飛ぶ。
【０１０６】
（８）ステップＳ１９
Ｋ＋ＧをＫに入れる。今、Ｋ＝０、Ｇ＝０であるので、Ｋは０のまま変わらない。
【０１０７】
（９）ステップＳ２０
図１６は、経路を構成する節（ノード）に置くメモリ構造である。節の先頭に次の節のメモリアドレスを入れる。もし次の節が無い場合、終りを示す０を入れておく。
【０１０８】
節には画像抽出座標（ｘ，ｙ）と定義電極指標ｉを格納し、両者が結合していることを示す。ここでは、経路表の末尾にＰ個の節（ｚ，０）、（ｚ，１）、・・・、（ｚ，Ｐ−１）を付加し、Ｋ＋ＰをＫとする。今、ｚ＝ａであるから、節（ａ，０）、（ａ，１）、（ａ，２）を付加し、Ｋ＋Ｐ→Ｋ即ちＫ＝３となる。
【０１０９】
図１２の（ａ）に、ステップ２０の処理終了後の経路表（Ｋ＝３）のメモリイメージを示す。
【０１１０】
図１６は、抽出電極と、それによる生成経路（ルートとも称する）と、累積経路数を示したものである。電極ａの欄に、生成された３つの経路のグラフイメージを見ることができる。
【０１１１】
（１０）ステップＳ２１
ここでパターンの完全一致を調べる。即ち新たに付加された経路の中に、その大きさ（＝節の数）がＨに等しいものがあるかどうかを調べる。今新たに付加された経路（３個）の大きさは、いずれも１であるので、Ｈ（＝３）に等しくない。従って、ステップＳ４に戻る。
【０１１２】
（１１）ステップＳ４
次の抽出電極はｂである。ｂは偽電極であるが、今は分からない。
【０１１３】
（１２）ステップＳ５
抽出電極の画像座標ｚ＝ｂである。
【０１１４】
（１３）ステップＳ６
新規発生経路数Ｇを０にする。そして、経路（現在Ｋ＝３個登録済み）の読出し位置を、経路表の先頭に位置決めする。
【０１１５】
（１４）ステップＳ７
Ｋ＝３回繰り返される。経路表の読出し位置の示す経路Гを取り出す。最初のГ＝（ａ，０）である。
【０１１６】
（１５）ステップＳ８
Г＝（ａ，０）の節数＝１をＮにセットする（Ｎ＝１）。
【０１１７】
（１６）ステップＳ９
Ｐ−Ｎ＝２を不足電極数Ｒにセットする（Ｒ＝２）。この数は、ボールパターンにおいてГが持っていない電極の数、即ち認識電極の不足数である。
【０１１８】
（１７）ステップＳ１０
定義ボールパターンについて、Гの位置指標の示す電極を除いた電極（Ｒ個）の個々を、その位置指標と定義座標の組を要素として集合Ｓに集める。今、Г＝（ａ，０）の位置指標＝０、従って集合Ｓは、Ｓ＝｛（位置指標＝１，その定義座標），（位置指標＝２，その定義座標）｝となる。
【０１１９】
（１８）ステップＳ１１
集合Ｓの読出し位置を最初の要素に位置決めする。
【０１２０】
（１９）ステップＳ１２
Ｒ＝２回繰り返される。集合Ｓの読出し位置から次の要素を読み出す。最初の要素はＥ＝（位置指標＝１，その定義座標）である。
【０１２１】
（２０）ステップＳ１３
要素Ｅの位置指標＝１を変数ｉにセットする（ｉ＝１）。
【０１２２】
（２１）ステップＳ１４
要素Ｅの定義指標に関する画像予測領域Ｄを生成する。但し、処理はＮ（＝Гの節数）によって異なる。今、Ｎ＝１、従ってＮ＝１点からの位置予測を行なう。
【０１２３】
図１８の（ａ）は、Ｎ＝１点からの位置予測の原理を示す。電極４５は画像から抽出された電極である。この１個の電極だけで他の電極４６の位置（画像座標）を予測する。各電極には定義電極の位置指標が貼り付いている。従って、その定義座標を参照できる。
【０１２４】
電極４６の画像座標は、定義座標系における電極４５→電極４６ベクトルを、そのままの傾きで画像座標系に移した座標（予測の中心座標）として得られる。
【０１２５】
部品がノズルに吸着されるとき回転のずれが生じる。その最大角度は±ωとして与えられるものとする。一般にω＝３０°設定すれば十分である。
【０１２６】
一方、予測には誤差εがある。実施例では、経験に基づいてε＝φ／２とした。実施例では、予測する距離（電極４５と電極４６の距離）によらず誤差εは一定としたが、勿論可変としても良い。
【０１２７】
破線で示す円弧型の領域４７が画像予測領域である。即ち、電極４６の抽出座標は、この領域に入ることが必要である。Г＝（ａ，０）を使ってＥの位置座標＝１を予測する場合、Ｎ＝１点からの位置予測の原理に従うと、図１１の円弧型領域Ｄ１がＥの予測領域となる。
【０１２８】
（２２）ステップＳ１５
座標ｚが予測領域に含まれるかどうかを検査する。図１１において、ｚ＝ｂはＤ１の外であり含まれないので不合格であり、ステップＳ１２に戻る。
【０１２９】
（２３）ステップＳ１２
次の要素はＥ＝（位置座標＝２，その定義座標）である。説明は省略するが、結局ステップＳ１５において不合格となり、ステップＳ１２に戻る。
【０１３０】
（２４）ステップＳ１２
次の要素が無くなったので、ステップＳ７に戻る。
【０１３１】
（２５）ステップＳ７
次のГ＝（ａ，１）である。この場合も同様に処理を行なうと、結局何も発生せず、ステップＳ７に戻る。
【０１３２】
（２６）ステップＳ７
次のГ＝（ａ，２）である。この場合、処理が進んだステップＳ１４において、集合Ｓの要素Ｅ＝（位置座標＝ｉ＝１，その定義座標）の画像予測領域を作ることになる。Ｎ＝１点からの位置予測の原理に従うと、図１１の円弧型領域Ｄ２がＥの予測領域となる。
【０１３３】
（２７）ステップＳ１７
ｚ＝ｂはＤ２に含まれるので合格である。
【０１３４】
（２８）ステップＳ１６
Гを複写してГ’を作る。即ち、Г’＝（ａ，２）となる。
【０１３５】
（２９）ステップＳ１７
Г’の末尾に節（ｚ，ｉ）を付加する。即ち、Г’＝（ａ，２）（ｂ，１）となる。
【０１３６】
（３０）ステップＳ１８
Г’を経路表の末尾に追加する。Ｇ＝０は１加算されてＧ＝１となる。
【０１３７】
図１２の（ｂ）に、電極ｂの処理終了後の経路表（Ｋ＝７）のメモリイメージを示す。図１７の電極ｂの欄に、生成された４つの経路のグラフイメージを見ることができる。
【０１３８】
この後ステップＳ４に戻り、電極ｃ、電極ｄの順に各ステップの処理が実行される。
【０１３９】
電極ｃ以降は、ステップＳ１４において、Ｎ＝１に加えてＮ≧２点による位置予測が行なわれる。何故ならば、既に経路表に大きさ２の経路（ａ，２）（ｂ，１）が存在するからである。
【０１４０】
図１８の（ｂ）は、Ｎ＝２点からの位置予測の原理を示す。電極５０、電極５１は、画像から抽出された電極である。これら２個の電極５０、５１で、他の電極５２の位置（画像座標）を予測する。各電極には定義電極の位置座標が貼り付いている。従って、その定義座標を参照できる。
【０１４１】
角度θは、定義座標系電極５０→電極５１ベクトルから、定義座標系電極５０→電極５２ベクトルへの開き角度である。
【０１４２】
距離αを画像座標系電極５０−電極５１の距離、距離βを画像座標系電極５０−電極５２の距離とすれば、β＝ρ×αとして求めることができる。但し、ρは定義座標系における長さの比率であり、ρ＝｛（定義座標系電極５０−電極５２の距離）／（定義座標系電極５０−電極５１の距離）｝である。
【０１４３】
画像座標系において開き角度θ、長さβの座標が予測中心座標５３である。破線で示すように、この座標を中心とする誤差半径εの円内の領域が予測領域５４である。即ち、電極５２の抽出座標は、この領域に入ることが必要である。
【０１４４】
図１８の（ｃ）は、Ｎ≧３点からの位置予測の原理を示す。電極５５、電極５６、・・・、電極５７は、画像から抽出された３個以上の電極である。これらＮ個の電極で、他の電極の位置（画像座標）を予測する。
【０１４５】
まず先頭の２個の座標、即ち電極５５と電極５６を使って、Ｎ＝２点からの位置予測の原理を適用すると、１つの予測中心座標５８が得られる。
【０１４６】
次に位置を１つずつずらして、電極５６と、その次の電極に対して、Ｎ＝２点からの位置予測の原理を適用すると、更に１つの予測中心座標が得られる。
【０１４７】
これを繰り返すと、予測中心座標の集合が得られる。その重心座標が予測中心座標５９である。破線で示すように、この座標を中心とする誤差半径εの円内の領域が予測領域である。即ち予測を受けた電極の中心座標は、この領域に入ることが必要である。
【０１４８】
電極ｃと電極ｄの各ステップの説明は省略する。
【０１４９】
図１７の電極ｃ及び電極ｄ欄に、生成された経路のグラフイメージを見ることができる。この中に経路（ａ，２）（ｃ，１）があるが、これは目的とする認識経路の一部である。
【０１５０】
この後ステップＳ４に戻り、次に電極ｅが抽出される。抽出電極ｅのとき、途中を省略するが、経路表のГ＝（ａ，２）（ｃ，１）から予測される定義電極指標＝０の予測領域に抽出座標ｅが入るので合格となる。従って新たな経路Г＝（ａ，２）（ｃ，１）（ｅ，０）が登録される。
【０１５１】
（３１）ステップＳ２１
新たに付加された経路の中に、その大きさＨ＝３のものがある。即ち経路Г’＝（ａ，２）（ｃ，１）（ｅ，０）である。
【０１５２】
（３２）ステップＳ２２
一般に、見つかった経路Г’は、なおＰ−Ｈ個の電極が未抽出である。未抽出の電極があれば、画像から抽出する。今の場合、Ｐ−Ｈ＝０であるから未抽出電極は無い。最終的に経路と同じ形で呼び出し側に出力する。即ち経路（ａ，２）（ｃ，１）（ｅ，０）を出力して、認識成功で終了する。
【０１５３】
なお、経路は必ずしも順調に成長しない。例えば画像に対して間違ったボールパターンを与えても成長しないし、実際の画像と大きく異なる電極データ（直径等）を与えても成長しないし、不鮮明な画像を与えても成長しない・・・等、状況は様々である。
【０１５４】
経路が成長しないとステップＳ４を繰返し、遂には画像から抽出する電極は枯渇する。このときはステップＳ２３にいく。
【０１５５】
（３３）ステップＳ２３
認識失敗でリターンする。
【０１５６】
以上がボールパターン認識部１１０の処理である。
【０１５７】
さて、実施例では、経路の中に大きさ＝Ｈ個のものを見つけた時点で認識成功とし、直ちにリターンした（ステップＳ２１）。これは、普通にランダムなボールパターンの場合問題ないが、逆に格子配置のパターンで、しかもΛをボールパターン像の中央部に置いた場合、どの電極から始まる経路も順調に成長するため、経路の中に大きさ＝Ｈ個のものが多数見つかることになり、どれか１つに決めることはできない。
【０１５８】
このような部品を認識する場合は、ステップＳ２１で、経路の中に、大きさ＝Ｈ個以上で、最大数のものが唯一つ見つかったか判定するように変更する。
【０１５９】
経路の中に大きさ＝Ｈ個以上のものが複数見つかった場合、そのまま認識処理を続行する。つまり、ステップＳ４を繰り返す。
【０１６０】
格子配列の場合、抽出電極の個数が増えていくと共に探索円が大きくなり、ボールパターンの特徴的な部分（辺、角、空洞）付近の電極を抽出し始める。これに伴い、経路の成長は最早一様に順調ではなくなり、遂には経路の大きさが最大のものが唯一つになる。この瞬間を捉えて、認識成功とすればよい。
【０１６１】
なお、前記実施形態では、画像からの電極抽出にΛ中心の同心円を使った（ステップＳ３、Ｓ４）。しかし、これを他の形状に変えることもできる。例えば正方形、長方形、楕円等類似の形状に変えることもできるし、螺旋の渦巻き形状に変えることもできる。即ち、Λを中心に距離が増減しながらも徐々に遠ざかれば、如何なる形状を使っても良い。その場合も、効果はほとんど変わらない。
【０１６２】
又、前記実施形態では、画像からの電極抽出において、１回の単位で複数の電極が抽出されたとき、Λから近い順に並べ替えて出力した（ステップＳ４）。しかし、並べ替える必要はなく、抽出した順に出力してもよい。その場合も効果はほとんどは変わらない。
【０１６３】
又、前記実施形態では、画像からの電極抽出において、探索の中心Λを設けた（ステップＳ３）。しかし、これを設ける必要は無い。即ち、画像の電極は実は如何なる順序で抽出され、且つ如何なる順序で出力されてもよい。その場合、若干認識能力が落ちる。
【０１６４】
何故ならば、抽出電極は定義ボールパターンの電極（Ｐ個）のいずれでも有り得るという仮定において照合され、登録されるからである。従って、定義ボールパターンの任意の電極から始まる任意の電極系列でも認識が成功する。
【０１６５】
又、前記実施形態では、画像から抽出した電極の処理の最後に、ボールパターン各電極と結合した大きさ１の経路として経路表に登録するとき、必ずＰ個登録した（ステップＳ２０）。しかし、Ｐ個である必要は無い。即ち、探索領域の中にはボールパターンが存在し得る最大領域がある（ノズルの吸着可能領域、位置ずれ、角度ずれ、それぞれの最大又は最小値を参照して計算により定めることができる）。そのことは、ボールパターンを構成する各電極についてみれば、画像の中に自己電極が存在し得る領域（専有領域）が決まっていることを意味する。そこで、ステップＳ２０において抽出した電極を経路表に登録するとき、抽出した電極の画像座標が、結合しようとする定義電極の占有領域に含まれているかどうかを調べる。もし含まれているならば登録し、含まれていなければ登録しない。このようにしても、後の照合に問題は生じない。これにより、毎回の登録個数をＰ以下とすることができるので、経路表全体の登録個数が少なくなり、メモリ消費量が少なくなると共に、全体の処理時間も小さくなるので好都合である。
【図面の簡単な説明】
【０１６６】
【図１】本発明の適用対象の１つである格子配置ＢＧＡの一例を示す図
【図２】同じく非格子配置ＢＧＡの一例を示す図
【図３】部品認識の必要性を説明するための図
【図４】従来の問題点を説明するための図
【図５】本発明が適用される部品認識装置の全体構成を示すブロック図
【図６】前記部品認識装置における処理対象画像の例を示す図
【図７】本発明の実施形態における処理手順の概要を示す流れ図
【図８】本発明による処理手順の最終結果の一例を示す図
【図９】前記実施形態のボールパターン認識部の処理手順の詳細を示す流れ図
【図１０】処理手順を説明するための簡単なＢＧＡの配置例を示す図
【図１１】図９の部品画像を示す図
【図１２】経路表の例を示す図
【図１３】前記処理手順における電極の探索経路の一例を示す図
【図１４】画像からボール電極を抽出する方法の一例を示す図
【図１５】別の方法を示す図
【図１６】経路を構成する節（ノード）におけるメモリ構造の一例を示す図
【図１７】抽出電極とそれによる生成経路と累積経路数を示す図
【図１８】位置予測の原理を示す図
【符号の説明】
【０１６７】
１…入力画像
２…ＢＧＡ部品
３…探索領域
１００…画像入力部
１１０…ボールパターン認識部
１２０…部品認識部
１３０…制御部
Ｈ…一致判定数
Ｐ…電極個数
Ｋ…経路登録個数
【技術分野】
【０００１】
本発明は、ボール部品の認識方法及び装置に係り、特に、電子部品の表面実装装置における画像によるボール電極部品（ＢＧＡ）の認識に用いるのに好適な、ＢＧＡの中でも、特に、難認識で知られる非格子配置（ランダム配置）ＢＧＡに対して強力な認識能力を発揮することが可能なボール部品の認識方法及び装置に関する。
【背景技術】
【０００２】
電子部品の表面実装装置において、電子部品は部品供給装置（フィーダ）から供給され、吸着ノズルにより吸着されて回路基板に実装される。吸着ノズルは、必ずしも正しい姿勢で電子部品を吸着するとは限らないので、通常ＣＣＤカメラ等により吸着部品が撮像されて部品認識が行なわれ、正しい姿勢で吸着されていない場合には、認識結果に基づき位置補正や傾き補正等が行なわれている。
【０００３】
図１に格子配置ＢＧＡの一例を示す。現在、市場のほとんどのＢＧＡは格子配列である。図１において、実線の円１５は、電極であるところの半田ボールである。ボールは、縦×横＝４×５の格子位置に整列している。破線の円１６は、欠けボール（存在しないボール）である。格子配列であるから、各ボールの位置は、例えば左上角の仮想ボール１７を（０，０）とする縦方向の位置指標０，１，・・・と横方向の位置指標０，１，・・・で指定できる。
【０００４】
部品認識のために適当なボールを選び、その中心座標に原点を置くＵＶ座標系（部品座標系）を貼ることが多い。このときＵ方向のピッチＰｕとＶ方向のピッチＰｖが与えられる。
【０００５】
図中ＦＢ（False Ball）は偽電極である。偽電極は、画像による認識のときに結果としてボールとして誤認識される異物の総称である。それは、パッケージ１８の一部であったり、ボール間を走る配線パターンの形状であったりなど様々である。偽電極があると認識に支障が出ることが多いが、偽電極の混入は予測困難である。当然ながら認識すべきボールパターンの定義に偽電極は含まれていない。
【０００６】
図２に、非格子配置ＢＧＡの一例を示す。電極の座標は乱れた位置にある。市場では少数派であるが、このような非格子配置ＢＧＡが存在し、その認識が困難であり、問題になりつつある。
【０００７】
この非格子配置ＢＧＡにおいても、認識のために部品の適当な位置を選び、そこに原点を置くＵＶ座標系を貼る。各ボールの位置はＵＶ座標系で記述される。ボールの定義順は任意である。この例では、１０個のボールが指標０，１，・・・，９で示す順に定義されている。
【０００８】
なお、格子、非格子いずれの型においても、ＢＧＡの電極数は数個（５〜６個）から多いものでは２０００個を越えるものまである。
【０００９】
図３に部品認識の必要性を示す。電子部品実装装置（チップマウンタとも称する）のカメラにより撮像された入力画像１（白黒濃淡画像）があり、この中にＢＧＡ部品２の腹側（基板側）が映っている。部品を吸着するノズルが部品の背中を吸着するとき、位置ずれと回転ずれが入ることは避けられない。
【００１０】
この部品が、基板の上の決められた位置に決められた角度で正しく載せられるためには、部品に貼り付けた座標系（ＵＶ座標系）の原点座標と傾きが、画像の座標系（ＸＹ座標系）で精度良く記述される必要がある。即ち、そのデータが分かれば位置補正と角度補正が可能となる。
【００１１】
そのためには、ＵＶ座標系において、ボールの中心座標を持って定義されるボールパターンについて、各ボール電極の中心座標がＸＹ座標で獲得されることが必要である。なお、画像においてボールパターン全体が十分に含まれるような探索領域３は予め分かっているものとする。
【００１２】
従来の方式は、例えば特許文献１に見ることができる。図３において、特許文献１の方式では、最初にボールパターンの角の（正確には角付近の任意の）ボール６を抽出し、それを元に残りのボールを抽出することが特徴である。そのために小窓と呼ぶ独特の手法を用いている。
【００１３】
小窓によるボール電極の中心座標の抽出方法については、特許文献２に詳しく記述されている。それによると、小窓は画像に被せる小さな円形領域であり、その中にボールの全体が完全に入っているとき、ボール電極の中心座標を抽出する。小窓の大きさはボールの直径から決まる。
【００１４】
小窓を最初は部品２の角方向の探索領域３の隅４の位置に置き、小窓の中にボール像が存在するかどうかを調べる。存在しなければ左又は下に少しずらした位置で調べる。この探索は、規則正しく角から三角形状に広がるように行なう。そして、探索位置が小窓５の位置に来たとき、ボール電極６の中心座標が抽出される。
【００１５】
最初に抽出されるボールは、必ずしもボール６とは限らない。例えばボール８かもしれない。そのため、予め入力ボールパターンを調べて、角を中心とした数個の電極を選んで候補電極としている。それにより最初に抽出されたボールが真の電極ならば、候補電極のどれかであることが高い確率で保証されるとしている。
【００１６】
候補電極個々を中心として、周りの電極を画像から順次抽出し、観察された電極の配置とボールパターンを照合する。抽出電極の個数が増えてゆくに連れて、真の候補電極以外は矛盾が生じて消滅する。
【００１７】
もし唯一つになるまで生き残った候補電極があれば、それが最初の抽出電極であったと結論する。即ち、このとき既にボールパターンの角を中心とした数多くの定義電極について、個々の電極から画像抽出電極への写像がある。これを基にＵＶ座標系からＸＹ座標系への精度の良い座標変換式を生成する。
【００１８】
ボールパターンの残りの定義電極がもしあれば、生成された座標変換式で画像位置を予測した後、小窓を使って抽出する。部品に偽電極７があるときは、小窓により最初に抽出される電極は、この偽電極であるかもしれない。その場合、全ての候補が消滅して、偽電極の排除が行なわれる。
【００１９】
即ち、基準位置、例えば左下角から最も遠い電極（７）を偽電極と見做して抹消し、その残りの電極集合のうちで左下角から最も遠い電極（６）を新たに最初の電極と見做して処理を続行する。偽電極排除を行なう限界回数は、ボールパターンの電極数等から適当に定めている。
【００２０】
【特許文献１】特開２００１−２８４９００号公報
【特許文献２】特開２０００−２３２２９９号公報
【発明の開示】
【発明が解決しようとする課題】
【００２１】
しかしながら、上記の従来技術は、次のような問題点を有する。
【００２２】
（１）偽電極対策が完全でなく、偽電極に弱い。
【００２３】
まず、偽電極の個数に強く依存して認識時間がかかる。即ち、角付近に偽電極が多いと、最初の偽電極を抹消しても次に選ばれる電極が又偽電極であり、その次も又偽電極であり、・・・と続くことがある。その場合、真の電極に至るまでに長い時間がかかる。しかし、部品実装装置には搭載タクトがあり、一定の時間内に認識しなければならない。偽電極の個数に強く依存して認識時間がかかっていては、搭載タクトに間に合わなくなる恐れがある。従って、偽電極の個数に強く依存しないような方式が望まれる。
【００２４】
次に、電極間内の相対位置関係が微妙にずれると、真の電極が偽電極と見做されることがあり、その排除を防止できない。そして、真の電極が抹消されてしまうと、それ以降の照合が難しくなり、認識できなくなる。即ち、ある真の電極（図３の電極６）から出発した場合、周辺電極の抽出中に偽電極（図３の電極１０）が紛れ込むこともあるし、正しい電極であるが、その位置がずれて抽出される（実質的に偽電極と同じ）こともある。その結果、位置関係が狂い、候補電極全てが消滅することが起きる。このとき、左下角から最も遠い電極として、出発点である真の電極（図３の電極６）が偽電極と見做されて抹消されるが、これを防ぐことができない。従って、抽出電極を抹消することなく認識する方式が望まれる。
【００２５】
（２）使い勝手が悪い。即ち、部品の中にはサイズの大きいものがあり、カメラの視野に入り切らないことがある。
【００２６】
このとき敢えて従来方式で認識しようとすれば、図４に例示する如く、ノズル１１で部品２を吸着した後、カメラの視野を部品２の角の方向にオフセット移動し撮像する。次に撮像した部品の部分画像（角部が映っている）１２で認識する必要がある。
【００２７】
しかし、このとき認識において使うことのできるボールパターン（電極の個数）が小さすぎて、位置決め認識できないことがある。
【００２８】
即ち、画像による認識が安定して行なわれるためには、部品２が吸着ノズル１１により吸着されるときに必ず発生する位置のずれと角度のずれに拘わらず、如何なるときにも必ず含まれるような最大のボールパターンが必要で、それが大きいほど良いことは言うまでもない。
【００２９】
一般にボールパターンの大きさは、角部認識の場合、部分画像２のフレームから部品２の一部が外れるので小さくなり、中央部認識の場合、部品２が必ず部分画像１２のフレーム内に入るので大きいと言える。何故ならば、吸着ノズルは部品の中央部を吸着するからである。即ち、吸着角度のずれによる位置ずれは、ノズル中心から遠いほど大きくなる。従って、部品の角部にこだわらず、部品の任意の部分を使って認識できることが望ましい。
【００３０】
（３）部品認識の時間のばらつきが大きい。即ち、図３において、ボールパターンは探索領域３の何処にでも位置し得る。角のボール６の探索に関して、それが画像の角４に近いときは、より早く見つかり、全体の認識時間も小さいが、逆に画像の角４から遠いときは、より遅く見つかり、全体の認識時間が大きい。更に、例え部品の中心位置が同じでも、部品の角度が異なれば、同じ理由により認識時間に大きな差が出ることになる。従って、認識時間のばらつきが小さいことが望ましい。
【００３１】
本発明は、前記従来の問題点を解決するべくなされたもので、非格子配置のＢＧＡであっても、高精度且つ迅速な位置認識を可能とすることを課題とする。
【課題を解決するための手段】
【００３２】
本発明は、画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置を用いて、ボール部品を画像により認識する方法であって、画像からボール電極の座標を次々と抽出し、画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納し、経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力し、画像抽出電極座標と前記予測領域の包含を判定し、包含されると判定されたとき、節を追加して経路を成長させ、経路とボールパターンを照合することにより、前記課題を解決したものである。
【００３３】
又、前記ボール電極の座標を、ボール電極の中心座標とし、前記経路の節を、画像抽出電極座標とボールパターン定義電極位置指標を結合したデータとし、前記経路の大きさ即ち節の数を使ってボールパターンとの一致を判定するようにしたものである。
【００３４】
又、前記経路の大きさが、所定の一致判定数Ｈ（Ｈは１≦Ｈ≦Ｐである整数、Ｐはボールパターンの電極個数）以上のとき、認識成功即ちボールパターンの完全一致とみなすようにしたものである。
【００３５】
又、前記画像の中に座標Λを定め、この座標Λから概ね近い順に電極を抽出し、ボールパターンにおいて経路が踏んでいない残りＰ−Ｎ個（Ｐはボールパターンの電極個数、Ｎは経路の節数）の定義電極の各電極の画像予測領域を生成し、既存経路Γがあり、Γが成長してΓ’となりうるとき、Γを保存したまま新たにΓ’を生成して登録し、１つの画像抽出電極があるとき、ボールパターン個々の定義電極と結合した大きさ１の経路を生成して登録するようにしたものである。
【００３６】
本発明は、又、ボール部品を画像により認識するための、画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置において、画像からボール電極の座標を次々と抽出する手段と、画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納する手段と、経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力する手段と、画像抽出電極座標と前記予測領域の包含を判定する手段と、包含されると判定されたとき、節を追加して経路を成長させる手段と、経路とボールパターンを照合する手段と、を備えたことを特徴とするボール部品の認識装置を提供するものである。
【発明の効果】
【００３７】
本発明は、偽電極に極めて強く、偽電極があっても認識時間がかかり過ぎることが無い。
【００３８】
即ち、本発明においては、画像から抽出した電極は、経路表に記録されることはあっても抹消されることはない。即ち、常に新しく入った電極とのパターン一致判定処理が行なわれ、過去に入ったかもしれない偽電極には関知しない。そのため、抹消そのものが不要となる。
【００３９】
又、偽電極があると、全く無いに比べて認識時間は大きくなるが、それは、偽電極を含んだ経路が成長するためである（大きさ１を含む）。しかし、偽電極を含んだ経路は早い段階で成長が止まるので、原理的に認識時間に大きな影響は与えない。
【００４０】
又、電極の抹消を行なわないので、正しい電極が抹消されることがない。これにより、正しい電極から始まる経路が必ず生成され、それは成長し、最後に大きさが一致判定数Ｈに達して認識が成功する。従って、少なくとも偽電極の存在が直接の原因で認識が失敗することはない。
【００４１】
又、本発明においては、与えるボールパターンは、部品のボール集合の全部でもよいし、任意の一部でも良く、使い勝手が良い。何故ならば、与えられたボールパターンの各電極は画像の中にあり、Λ中心の探索の過程で何時かは必ず画像から抽出される。その結果、パターンの完全一致、即ち認識が成功する。従来方式のときに問題となった、カメラの視野に入り切らないほど大きい部品の場合は、ボールパターンとして、部品中央部の電極を定義し、部品を吸着した後、通常の撮像、即ちカメラの視野中心とノズル中心を一致させて撮像し（部品の中央部が映っている）、次に、撮像した画像で部品認識すればよい。従って、従来方式で煩わしかったオフセット移動と角部のボールパターン作成が不要となる。
【００４２】
更に、部品認識の認識時間はほぼ一定であり、ばらつきが小さい。部品の全ての電極をボールパターンとして定義した場合を想定すると、画像の中に設けた探索領域のほぼ中央にボールパターンが映っているはずである。認識時間は、電極抽出時間と経路表照合時間の和である。
【００４３】
例えば探索の中心Λを探索領域の中央に設定すると、電極抽出を開始して、直ぐに最初の電極を抽出する。２番目以降の電極も同じである。
【００４４】
１番目を抽出するための処理時間、２番目を抽出するための処理時間、・・・これらは画像により一定ではない。しかしパターンの完全な一致を確認できるＨ個について、そのＨ番目までの総和時間（電極抽出時間）を考えると、これは統計的にほぼ一定となる。
【００４５】
一方、経路表の照合における処理時間は、１番目に要する処理時間、２番目に要する処理時間、・・・これらは、どの電極が先にするかで一定ではない。しかし、Ｈ番目までの総和時間（経路表照合時間）を考えれば、これも統計的にほぼ一定となる。
【００４６】
更に、認識のロジックに柔軟性があり、難認識条件に強いので、非格子配置ＢＧＡ部品を確実に認識できる。即ち、真の電極について、その映りが悪い、あるいは位置がずれている等の理由で、予測した位置で画像抽出できないことが起こる。このとき、ボールパターンの電極個数Ｐが一致判定数Ｈより十分に大きければ、１個の電極が抽出されないことは大きな問題ではない。何故ならば、Ｐ個のうちのＨ個が抽出され、そのＨ個がボールパターンの部分グラフと一致すればボールパターンの完全なる一致と見做すロジックだからである。
【００４７】
なお、本発明は、非格子配置ＢＧＡだけでなく、格子配置ＢＧＡにも適用できる。即ち、格子配置の場合、適当な電極にＵＶ座標系を設けて、個々の電極を座標（ｕ，ｖ）で記述すれば、非格子配置ＢＧＡの認識の一つとして扱うことができる。
【発明を実施するための最良の形態】
【００４８】
以下図面を参照して、本発明の実施形態を詳細に説明する。
【００４９】
図５に、本発明を実施するための部品認識装置の基本的な構成を示す。この部品認識装置は、主に、画像入力部１００と、ボールパターン認識部１１０と、部品認識部１２０と、制御部１３０とから構成される。
【００５０】
前記制御部１３０は、全体を制御する。即ち、次のＢＧＡ部品を選び、その部品データを生成し、画像を取り込み、画像による部品認識を行ない、その認識データにより装置を駆動する。
【００５１】
前記画像入力部１００は、吸着ノズルにより吸着されたＢＧＡ部品を撮像して、画像メモリ（図示省略）に取り込む。
【００５２】
前記部品認識部１２０は、画像による部品認識を行なう。即ち、渡された部品データと画像により、ＸＹ座標系におけるＵＶ座標系の位置と傾きを出力するまでの一連の作業を行なう。即ち、一般に部品は１個でも、図６に例示する如く、認識すべきボールパターンは１個以上（図６では３個）あり、それらの全パターン（図６では右上角のパターンＰ１、左下角のパターンＰ２、周囲を除く中央のパターンＰ３）が同時に渡される。部品認識部１２０は、渡されたパターンのうち、まず最も大きなボールパターン、即ち電極数が最も多いボールパターン（図６ではＰ３）を選ぶ。次に、選んだボールパターンを画像と共にボールパターン認識部１１０に送り、そこで認識させる。そして、最初のパターンＰ３から、ＸＹ座標系におけるＵＶ座標系の原点位置と傾きを出力する。
【００５３】
次に、存在すれば２番目以降のボールパターンＰ１、Ｐ２を同様にボールパターン認識部１１０に送り、今度は予測により電極を認識させ、以降これを繰り返す。
【００５４】
一方、ボールパターン認識部１１０は、与えられた１個のボールパターンについて、入力画像の中で認識する。各ボール電極の中心座標を画像から抽出した後、呼び出した部品認識部１２０に返す。
【００５５】
次に、図７を参照して、本発明に係るボールパターン認識部１１０の動作の概要を説明する。なお、ステップ番号は、後出図８の詳細図に対応させている。
【００５６】
まず、ステップＳ１で、ボールパターンの大きさＰ（＝電極数）から一致判定数Ｈを決める（１≦Ｈ≦Ｐ）。
【００５７】
次に、ステップＳ２で、画像の探索領域の中に適当な座標を探索中心座標Λとして１点定める。
【００５８】
次に、ステップＳ４で、その座標Λに近い順に画像から次々と電極を抽出する。
【００５９】
次に、ステップＳ７で、抽出と同時にボールパターンとの照合を行なう。即ち、ボールパターンの個々の電極を出発点とし、ボールパターン自身の電極を結んでできる部分経路（生成経路）が表の形で既にあるものとする（最初は０個）。生成経路は、あれば、その大きさ（＝電極数）は１から始まる。
【００６０】
画像から電極が抽出される度に表中の生成経路を順に巡る。ある生成経路に今回の抽出電極を付加したものが再びボールパターンの部分経路と一致するなら、その元の経路を複写した後、抽出電極を付加した新しい生成経路を作り、経路表に登録する。
【００６１】
一方、ボールパターン個々の電極と、抽出した１個の電極を結合した大きさ１の生成経路Ｐ個は無条件に登録される。
【００６２】
電極の抽出を続けると、生成経路の大きさがＨに等しくなって、ステップＳ２１の判定条件が成立することがある。このとき認識は成功であり、ステップＳ２２で、この生成経路を出力する。
【００６３】
図２のＢＧＡを使って具体的に説明する。ボールパターンの大きさはＰ＝１０である（ボール指標０〜９）。一致判定数Ｈは、ここではＨ＝１０となる（後述）。
【００６４】
図３において、画像探索領域３の中に座標Λを定める。Λは、ボールパターンの近くにあれば何処でも良い（後述）。
【００６５】
座標Λに近い順に画像から次々と電極を抽出する。例えば電極ａ、ｂ、ｃ、ｄ、・・・の順に抽出される。
【００６６】
生成経路は最初０個である。
【００６７】
電極ａが抽出されたとき、大きさ１の生成経路が１０個できる。それらはボールパターンの各定義電極と座標ａを結合したものである。
【００６８】
次の電極ｂは偽電極であるが、この時点では判らない。電極ａと電極ｂの位置関係（距離と角度）を満足する生成経路として、図２における電極９と電極１を結ぶ大きさ２の生成経路が新たに登録されるかもしれない。このときの距離誤差と角度誤差については後述する。
【００６９】
一方、電極ｂ単独の大きさ１の生成経路も１０個できる。それらはボールパターンの各定義電極と座標ｂを結合したものである。
【００７０】
次の電極ｃ以下でも同じことを繰り返す。
【００７１】
図８に最終結果を示す。電極ａから始まり実線矢印で繋がる黒丸ａ、ｂ、ｃ、ｄ、・・・、ｋ、ｍは抽出電極である（この場合、図３の電極７は抽出されないまま終了する）。
【００７２】
電極ｍに対する処理が終了した時点で登録されている生成経路を調べてみると、その中に電極ａから始まり点線矢印で繋がる（点線が無いものは実線）大きさ１０＝Ｈの経路（ａ，６）、（ｃ，０）、（ｄ，１）、・・・、（ｋ，４）、（ｍ，５）がある。
【００７３】
この事実により認識は成功であり、この生成経路を出力して終了する。以上が認識の一例である。
【００７４】
図９に、ボールパターン認識部１１０における処理の流れ図の詳細を示す。
【００７５】
以下、図１０にボールパターンを示す簡単なＢＧＡを使って、図９の各ステップの処理を詳しく説明する。このＢＧＡは３個の電極（位置指標０、１、２）からなり、図１１にその部品画像を示す。ボールパターンの電極ａ、ｃ、ｅと共に、偽電極ｂ、ｄも映っている。
【００７６】
（１）ステップＳ１
定義パターンの電極数Ｐを３とし、一致判定数ＨをＰ以下の整数とする。Ｈは照合の高速化のために設けた数で、ボールパターンＰ個のうち画像抽出電極Ｈ個が一致したとき、パターン全体の完全なる一致であると見做すことができる数である。ＨはＰの関数であり、実施例では、経験に基づいて、Ｈ＝ｍａｘ｛２０，Ｐ／８｝とした（整数）。但し、ＨはＰを超えない。
【００７７】
即ち、パターン全体の一致の信頼性に関して、小さいパターン（Ｐ≦１６０）までは、一定数（Ｈ＝２０）が一致すれば十分であるとした。一方、大きいパターン（Ｐ＞１６０）に対しては、その一定比率（Ｐ／８）が一致すれば十分であるとした。従って、この例ではＨ＝３となる。
【００７８】
（２）ステップＳ２
メモリに経路表を確保し、経路登録個数Ｋを０にする。図１２に経路表を示す。図１２（ａ）にはＫ＝３個の経路が登録されている。経路表はメモリアドレスを要素とする配列であり、各要素には経路の先頭アドレスが書き込まれる。経路表の大きさ、即ちメモリアドレス登録個数の容量としては、積Ｐ×Ｈの値を基に決めると良い。実施例では、経験に基づいて、経路表の大きさ＝４×Ｐ×Ｈ＋１００とした。ここで係数４はＰが大きいときの安全係数であり、加算数１００はＰが小さいときに偽電極が多いときの対策である。従って、この例では、経路表の大きさ＝４×３×３＋１００＝１３６（個）となる。
【００７９】
（３）ステップＳ３
探索中心座標Λを決める。Λは、画像中任意の座標でよい。実施例では、画像探索領域の中心座標とした。
【００８０】
（４）ステップＳ４
探索中心座標Λから近い順に、画像から電極を抽出する。抽出は電極が枯渇するまで続ける。図１３に電極の探索経路を示す。この同心円、即ち探索円に沿って電極を探す。Λを中心とする半径Ｒ０の円があり、これは最初の探索円である。δは探索円の半径の増分である。Ｒ０とδは、ボール電極を画像から抽出する方法により異なる。
【００８１】
画像からボール電極を抽出する方法は種々あるが、本発明においては、どの方法を使っても良い。
【００８２】
図１４は、その１つの方法を示す。この場合、ボール直径をφ（＝２ｒ）とすれば、例えばＲ０＝２φ、δ＝φ／６（経験式）とすればよい。
【００８３】
図１４において、暗い背景に明るく映っているボール電極２０の中心座標２１を抽出したい。一般にボール電極には配線パターン２２があり、ボールと同じような輝度で映っている。円２３、円２４、・・・は探索円である。画素明度に関してある閾値が与えられているものとする。円の軌道上の画素明度の変化を調べると、円２４の座標２５において明度の変化（閾値に関して低→高）がある。この座標における明度勾配ベクトル（例えば暗い方から明るい方へ向かうベクトル）２７を得る。
【００８４】
ｒ＝φ／２は定義電極の半径である。座標２５から明度勾配ベクトル２７方向に距離ｒの座標２８を記録しておく。この座標は、電極中心座標の一つの候補である。
【００８５】
次に、円２４の座標２６において、再び明度の変化（閾値に関して高→低）がある。上と同様に１つの候補座標を記録する。
【００８６】
探索円を１周するまで同じことを繰返し、更に次の探索円でも同じことを繰り返す。
【００８７】
電極の座標計算は、探索円を一定の本数ずつまとめた探索帯毎に行なう。探索帯の本数は、δ＝φ／６により、ボール当り平均６本走るので、それより大きい適当な数、例えば１０本とすれば良い。
【００８８】
探索帯１個分の探索円発生が終了したとき、その内部の電極個々の中心には候補座標が集まっていることが期待できる。
【００８９】
画像を適当にブロック分割し（例えば辺の長さ＝０．５φの正方形）、今回の探索帯に接触するブロック（例えばブロック２９）内の候補座標を数える。一定個数（例えば６個）以上であれば、その点列の重心座標を円の中心座標として出力する。このときブロック同士の境界が円の中心付近を通過するときは、結合して数える等の処置を行なう。
【００９０】
探索帯内部の電極抽出が終了したら、電極をΛから近い順に並べ替え、先頭から順に出力する。
【００９１】
以下、探索帯の発生と、その探索円の発生と、電極の抽出とを繰り返す。
【００９２】
なお、この方式では、初期半径Ｒ０の円内にある電極、特に、その中心を偶然Λに置くような電極の抽出を必ず行なう。もしあれば、この電極が最初に出力されるべきである。
【００９３】
即ち、図１４において、円３０は初期半径Ｒ０の円であるとする。この円の周が、長さδで分割されるように、Λからこの円に放射線分、即ち、線分３１、線分３２、・・・を１周するまで引く。
【００９４】
各放射線分について、探索円のとき行なったと同じ処理を行なう。これにより、初期半径Ｒ０の円内にある電極を抽出できる。
【００９５】
図１５に電極抽出の別の方法を示す。この場合、ボール直径をφとすれば、例えばＲ０＝０、δ＝φ／３（経験式）とすることができる。
【００９６】
最初はΛの１点、以下は半径をδずつ増分した探索円、その探索円の周を更に周長δで分割する各点において、小窓抽出と呼ばれる以下の処理を行なう。
【００９７】
図１５において、座標３５が画像上指定された座標、即ちΛ若しくは探索円の分割点である。円３６は、座標３５を中心とする半径φ（直径＝２φ）の円であり、これを小窓と呼ぶ。
【００９８】
小窓の中に偶然入っている、暗い背景に明るく映っているボール電極２０の中心座標２１を抽出したい。一般にボール電極には配線パターン２２があり、ボールと同じような輝度で映っている。小窓による方法は、特に配線パターンの存在に強いのが特徴で、図のように２本程度までなら問題ない。
【００９９】
画素明度に関して、ある閾値が与えられているものとする。小窓内部の画素明度を２値化すれば、２値化電極像の外周を矢印３８の方向に進み、１周して元の位置に戻る閉路が得られる（閉路は小窓の外には出ず、小窓の経路３９、経路３４を通る）。
【０１００】
得られた閉路上に、円周上の弦の候補である弦ＡＡ’、ＢＢ’をとる。それぞれ安定した経路上に発生していること、直径になるべく近いこと、互いに直交に近いこと・・・等の諸条件を満たす。このとき、それぞれの弦の垂直二等分線の交点を、円の中心座標２１として出力する。
【０１０１】
探索円を１周する間に小窓から出力された電極座標をΛから近い順に並べ替え、先頭から順に出力する。
【０１０２】
図１１の例において、出力順はａ→ｂ→ｃ→ｄ→ｅとする。
【０１０３】
（５）ステップＳ５
抽出電極の画像座標をｚとする。即ち最初の座標はｚ＝ａである。
【０１０４】
（６）ステップＳ６
今回の抽出座標により新たに発生する生成経路の数を初期化する。即ち新規発生経路数Ｇを０にする。そして、経路の読出し位置を経路表の先頭に位置決めする。
【０１０５】
（７）ステップＳ７
Ｋ回繰り返される。しかし、今、Ｋ＝０なので、Ｓ７以降をスキップしてＳ１９に飛ぶ。
【０１０６】
（８）ステップＳ１９
Ｋ＋ＧをＫに入れる。今、Ｋ＝０、Ｇ＝０であるので、Ｋは０のまま変わらない。
【０１０７】
（９）ステップＳ２０
図１６は、経路を構成する節（ノード）に置くメモリ構造である。節の先頭に次の節のメモリアドレスを入れる。もし次の節が無い場合、終りを示す０を入れておく。
【０１０８】
節には画像抽出座標（ｘ，ｙ）と定義電極指標ｉを格納し、両者が結合していることを示す。ここでは、経路表の末尾にＰ個の節（ｚ，０）、（ｚ，１）、・・・、（ｚ，Ｐ−１）を付加し、Ｋ＋ＰをＫとする。今、ｚ＝ａであるから、節（ａ，０）、（ａ，１）、（ａ，２）を付加し、Ｋ＋Ｐ→Ｋ即ちＫ＝３となる。
【０１０９】
図１２の（ａ）に、ステップ２０の処理終了後の経路表（Ｋ＝３）のメモリイメージを示す。
【０１１０】
図１６は、抽出電極と、それによる生成経路（ルートとも称する）と、累積経路数を示したものである。電極ａの欄に、生成された３つの経路のグラフイメージを見ることができる。
【０１１１】
（１０）ステップＳ２１
ここでパターンの完全一致を調べる。即ち新たに付加された経路の中に、その大きさ（＝節の数）がＨに等しいものがあるかどうかを調べる。今新たに付加された経路（３個）の大きさは、いずれも１であるので、Ｈ（＝３）に等しくない。従って、ステップＳ４に戻る。
【０１１２】
（１１）ステップＳ４
次の抽出電極はｂである。ｂは偽電極であるが、今は分からない。
【０１１３】
（１２）ステップＳ５
抽出電極の画像座標ｚ＝ｂである。
【０１１４】
（１３）ステップＳ６
新規発生経路数Ｇを０にする。そして、経路（現在Ｋ＝３個登録済み）の読出し位置を、経路表の先頭に位置決めする。
【０１１５】
（１４）ステップＳ７
Ｋ＝３回繰り返される。経路表の読出し位置の示す経路Гを取り出す。最初のГ＝（ａ，０）である。
【０１１６】
（１５）ステップＳ８
Г＝（ａ，０）の節数＝１をＮにセットする（Ｎ＝１）。
【０１１７】
（１６）ステップＳ９
Ｐ−Ｎ＝２を不足電極数Ｒにセットする（Ｒ＝２）。この数は、ボールパターンにおいてГが持っていない電極の数、即ち認識電極の不足数である。
【０１１８】
（１７）ステップＳ１０
定義ボールパターンについて、Гの位置指標の示す電極を除いた電極（Ｒ個）の個々を、その位置指標と定義座標の組を要素として集合Ｓに集める。今、Г＝（ａ，０）の位置指標＝０、従って集合Ｓは、Ｓ＝｛（位置指標＝１，その定義座標），（位置指標＝２，その定義座標）｝となる。
【０１１９】
（１８）ステップＳ１１
集合Ｓの読出し位置を最初の要素に位置決めする。
【０１２０】
（１９）ステップＳ１２
Ｒ＝２回繰り返される。集合Ｓの読出し位置から次の要素を読み出す。最初の要素はＥ＝（位置指標＝１，その定義座標）である。
【０１２１】
（２０）ステップＳ１３
要素Ｅの位置指標＝１を変数ｉにセットする（ｉ＝１）。
【０１２２】
（２１）ステップＳ１４
要素Ｅの定義指標に関する画像予測領域Ｄを生成する。但し、処理はＮ（＝Гの節数）によって異なる。今、Ｎ＝１、従ってＮ＝１点からの位置予測を行なう。
【０１２３】
図１８の（ａ）は、Ｎ＝１点からの位置予測の原理を示す。電極４５は画像から抽出された電極である。この１個の電極だけで他の電極４６の位置（画像座標）を予測する。各電極には定義電極の位置指標が貼り付いている。従って、その定義座標を参照できる。
【０１２４】
電極４６の画像座標は、定義座標系における電極４５→電極４６ベクトルを、そのままの傾きで画像座標系に移した座標（予測の中心座標）として得られる。
【０１２５】
部品がノズルに吸着されるとき回転のずれが生じる。その最大角度は±ωとして与えられるものとする。一般にω＝３０°設定すれば十分である。
【０１２６】
一方、予測には誤差εがある。実施例では、経験に基づいてε＝φ／２とした。実施例では、予測する距離（電極４５と電極４６の距離）によらず誤差εは一定としたが、勿論可変としても良い。
【０１２７】
破線で示す円弧型の領域４７が画像予測領域である。即ち、電極４６の抽出座標は、この領域に入ることが必要である。Г＝（ａ，０）を使ってＥの位置座標＝１を予測する場合、Ｎ＝１点からの位置予測の原理に従うと、図１１の円弧型領域Ｄ１がＥの予測領域となる。
【０１２８】
（２２）ステップＳ１５
座標ｚが予測領域に含まれるかどうかを検査する。図１１において、ｚ＝ｂはＤ１の外であり含まれないので不合格であり、ステップＳ１２に戻る。
【０１２９】
（２３）ステップＳ１２
次の要素はＥ＝（位置座標＝２，その定義座標）である。説明は省略するが、結局ステップＳ１５において不合格となり、ステップＳ１２に戻る。
【０１３０】
（２４）ステップＳ１２
次の要素が無くなったので、ステップＳ７に戻る。
【０１３１】
（２５）ステップＳ７
次のГ＝（ａ，１）である。この場合も同様に処理を行なうと、結局何も発生せず、ステップＳ７に戻る。
【０１３２】
（２６）ステップＳ７
次のГ＝（ａ，２）である。この場合、処理が進んだステップＳ１４において、集合Ｓの要素Ｅ＝（位置座標＝ｉ＝１，その定義座標）の画像予測領域を作ることになる。Ｎ＝１点からの位置予測の原理に従うと、図１１の円弧型領域Ｄ２がＥの予測領域となる。
【０１３３】
（２７）ステップＳ１７
ｚ＝ｂはＤ２に含まれるので合格である。
【０１３４】
（２８）ステップＳ１６
Гを複写してГ’を作る。即ち、Г’＝（ａ，２）となる。
【０１３５】
（２９）ステップＳ１７
Г’の末尾に節（ｚ，ｉ）を付加する。即ち、Г’＝（ａ，２）（ｂ，１）となる。
【０１３６】
（３０）ステップＳ１８
Г’を経路表の末尾に追加する。Ｇ＝０は１加算されてＧ＝１となる。
【０１３７】
図１２の（ｂ）に、電極ｂの処理終了後の経路表（Ｋ＝７）のメモリイメージを示す。図１７の電極ｂの欄に、生成された４つの経路のグラフイメージを見ることができる。
【０１３８】
この後ステップＳ４に戻り、電極ｃ、電極ｄの順に各ステップの処理が実行される。
【０１３９】
電極ｃ以降は、ステップＳ１４において、Ｎ＝１に加えてＮ≧２点による位置予測が行なわれる。何故ならば、既に経路表に大きさ２の経路（ａ，２）（ｂ，１）が存在するからである。
【０１４０】
図１８の（ｂ）は、Ｎ＝２点からの位置予測の原理を示す。電極５０、電極５１は、画像から抽出された電極である。これら２個の電極５０、５１で、他の電極５２の位置（画像座標）を予測する。各電極には定義電極の位置座標が貼り付いている。従って、その定義座標を参照できる。
【０１４１】
角度θは、定義座標系電極５０→電極５１ベクトルから、定義座標系電極５０→電極５２ベクトルへの開き角度である。
【０１４２】
距離αを画像座標系電極５０−電極５１の距離、距離βを画像座標系電極５０−電極５２の距離とすれば、β＝ρ×αとして求めることができる。但し、ρは定義座標系における長さの比率であり、ρ＝｛（定義座標系電極５０−電極５２の距離）／（定義座標系電極５０−電極５１の距離）｝である。
【０１４３】
画像座標系において開き角度θ、長さβの座標が予測中心座標５３である。破線で示すように、この座標を中心とする誤差半径εの円内の領域が予測領域５４である。即ち、電極５２の抽出座標は、この領域に入ることが必要である。
【０１４４】
図１８の（ｃ）は、Ｎ≧３点からの位置予測の原理を示す。電極５５、電極５６、・・・、電極５７は、画像から抽出された３個以上の電極である。これらＮ個の電極で、他の電極の位置（画像座標）を予測する。
【０１４５】
まず先頭の２個の座標、即ち電極５５と電極５６を使って、Ｎ＝２点からの位置予測の原理を適用すると、１つの予測中心座標５８が得られる。
【０１４６】
次に位置を１つずつずらして、電極５６と、その次の電極に対して、Ｎ＝２点からの位置予測の原理を適用すると、更に１つの予測中心座標が得られる。
【０１４７】
これを繰り返すと、予測中心座標の集合が得られる。その重心座標が予測中心座標５９である。破線で示すように、この座標を中心とする誤差半径εの円内の領域が予測領域である。即ち予測を受けた電極の中心座標は、この領域に入ることが必要である。
【０１４８】
電極ｃと電極ｄの各ステップの説明は省略する。
【０１４９】
図１７の電極ｃ及び電極ｄ欄に、生成された経路のグラフイメージを見ることができる。この中に経路（ａ，２）（ｃ，１）があるが、これは目的とする認識経路の一部である。
【０１５０】
この後ステップＳ４に戻り、次に電極ｅが抽出される。抽出電極ｅのとき、途中を省略するが、経路表のГ＝（ａ，２）（ｃ，１）から予測される定義電極指標＝０の予測領域に抽出座標ｅが入るので合格となる。従って新たな経路Г＝（ａ，２）（ｃ，１）（ｅ，０）が登録される。
【０１５１】
（３１）ステップＳ２１
新たに付加された経路の中に、その大きさＨ＝３のものがある。即ち経路Г’＝（ａ，２）（ｃ，１）（ｅ，０）である。
【０１５２】
（３２）ステップＳ２２
一般に、見つかった経路Г’は、なおＰ−Ｈ個の電極が未抽出である。未抽出の電極があれば、画像から抽出する。今の場合、Ｐ−Ｈ＝０であるから未抽出電極は無い。最終的に経路と同じ形で呼び出し側に出力する。即ち経路（ａ，２）（ｃ，１）（ｅ，０）を出力して、認識成功で終了する。
【０１５３】
なお、経路は必ずしも順調に成長しない。例えば画像に対して間違ったボールパターンを与えても成長しないし、実際の画像と大きく異なる電極データ（直径等）を与えても成長しないし、不鮮明な画像を与えても成長しない・・・等、状況は様々である。
【０１５４】
経路が成長しないとステップＳ４を繰返し、遂には画像から抽出する電極は枯渇する。このときはステップＳ２３にいく。
【０１５５】
（３３）ステップＳ２３
認識失敗でリターンする。
【０１５６】
以上がボールパターン認識部１１０の処理である。
【０１５７】
さて、実施例では、経路の中に大きさ＝Ｈ個のものを見つけた時点で認識成功とし、直ちにリターンした（ステップＳ２１）。これは、普通にランダムなボールパターンの場合問題ないが、逆に格子配置のパターンで、しかもΛをボールパターン像の中央部に置いた場合、どの電極から始まる経路も順調に成長するため、経路の中に大きさ＝Ｈ個のものが多数見つかることになり、どれか１つに決めることはできない。
【０１５８】
このような部品を認識する場合は、ステップＳ２１で、経路の中に、大きさ＝Ｈ個以上で、最大数のものが唯一つ見つかったか判定するように変更する。
【０１５９】
経路の中に大きさ＝Ｈ個以上のものが複数見つかった場合、そのまま認識処理を続行する。つまり、ステップＳ４を繰り返す。
【０１６０】
格子配列の場合、抽出電極の個数が増えていくと共に探索円が大きくなり、ボールパターンの特徴的な部分（辺、角、空洞）付近の電極を抽出し始める。これに伴い、経路の成長は最早一様に順調ではなくなり、遂には経路の大きさが最大のものが唯一つになる。この瞬間を捉えて、認識成功とすればよい。
【０１６１】
なお、前記実施形態では、画像からの電極抽出にΛ中心の同心円を使った（ステップＳ３、Ｓ４）。しかし、これを他の形状に変えることもできる。例えば正方形、長方形、楕円等類似の形状に変えることもできるし、螺旋の渦巻き形状に変えることもできる。即ち、Λを中心に距離が増減しながらも徐々に遠ざかれば、如何なる形状を使っても良い。その場合も、効果はほとんど変わらない。
【０１６２】
又、前記実施形態では、画像からの電極抽出において、１回の単位で複数の電極が抽出されたとき、Λから近い順に並べ替えて出力した（ステップＳ４）。しかし、並べ替える必要はなく、抽出した順に出力してもよい。その場合も効果はほとんどは変わらない。
【０１６３】
又、前記実施形態では、画像からの電極抽出において、探索の中心Λを設けた（ステップＳ３）。しかし、これを設ける必要は無い。即ち、画像の電極は実は如何なる順序で抽出され、且つ如何なる順序で出力されてもよい。その場合、若干認識能力が落ちる。
【０１６４】
何故ならば、抽出電極は定義ボールパターンの電極（Ｐ個）のいずれでも有り得るという仮定において照合され、登録されるからである。従って、定義ボールパターンの任意の電極から始まる任意の電極系列でも認識が成功する。
【０１６５】
又、前記実施形態では、画像から抽出した電極の処理の最後に、ボールパターン各電極と結合した大きさ１の経路として経路表に登録するとき、必ずＰ個登録した（ステップＳ２０）。しかし、Ｐ個である必要は無い。即ち、探索領域の中にはボールパターンが存在し得る最大領域がある（ノズルの吸着可能領域、位置ずれ、角度ずれ、それぞれの最大又は最小値を参照して計算により定めることができる）。そのことは、ボールパターンを構成する各電極についてみれば、画像の中に自己電極が存在し得る領域（専有領域）が決まっていることを意味する。そこで、ステップＳ２０において抽出した電極を経路表に登録するとき、抽出した電極の画像座標が、結合しようとする定義電極の占有領域に含まれているかどうかを調べる。もし含まれているならば登録し、含まれていなければ登録しない。このようにしても、後の照合に問題は生じない。これにより、毎回の登録個数をＰ以下とすることができるので、経路表全体の登録個数が少なくなり、メモリ消費量が少なくなると共に、全体の処理時間も小さくなるので好都合である。
【図面の簡単な説明】
【０１６６】
【図１】本発明の適用対象の１つである格子配置ＢＧＡの一例を示す図
【図２】同じく非格子配置ＢＧＡの一例を示す図
【図３】部品認識の必要性を説明するための図
【図４】従来の問題点を説明するための図
【図５】本発明が適用される部品認識装置の全体構成を示すブロック図
【図６】前記部品認識装置における処理対象画像の例を示す図
【図７】本発明の実施形態における処理手順の概要を示す流れ図
【図８】本発明による処理手順の最終結果の一例を示す図
【図９】前記実施形態のボールパターン認識部の処理手順の詳細を示す流れ図
【図１０】処理手順を説明するための簡単なＢＧＡの配置例を示す図
【図１１】図９の部品画像を示す図
【図１２】経路表の例を示す図
【図１３】前記処理手順における電極の探索経路の一例を示す図
【図１４】画像からボール電極を抽出する方法の一例を示す図
【図１５】別の方法を示す図
【図１６】経路を構成する節（ノード）におけるメモリ構造の一例を示す図
【図１７】抽出電極とそれによる生成経路と累積経路数を示す図
【図１８】位置予測の原理を示す図
【符号の説明】
【０１６７】
１…入力画像
２…ＢＧＡ部品
３…探索領域
１００…画像入力部
１１０…ボールパターン認識部
１２０…部品認識部
１３０…制御部
Ｈ…一致判定数
Ｐ…電極個数
Ｋ…経路登録個数
【特許請求の範囲】
【請求項１】
画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置を用いて、ボール部品を画像により認識する方法であって、
画像からボール電極の座標を次々と抽出し、
画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納し、
経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力し、
画像抽出電極座標と前記予測領域の包含を判定し、
包含されると判定されたとき、節を追加して経路を成長させ、
経路とボールパターンを照合することを特徴とするボール部品の認識方法。
【請求項２】
前記ボール電極の座標が、ボール電極の中心座標であり、
前記経路の節が、画像抽出電極座標とボールパターン定義電極位置指標を結合したデータであり、
前記経路の大きさ即ち節の数を使ってボールパターンとの一致を判定することを特徴とする請求項１に記載のボール部品の認識方法。
【請求項３】
前記経路の大きさが、所定の一致判定数Ｈ（Ｈは１≦Ｈ≦Ｐである整数、Ｐはボールパターンの電極個数）以上のとき、認識成功即ちボールパターンの完全一致とみなすことを特徴とする請求項２に記載のボール部品の認識方法。
【請求項４】
前記画像の中に座標Λを定め、
この座標Λから概ね近い順に電極を抽出し、
ボールパターンにおいて経路が踏んでいない残りＰ−Ｎ個（Ｐはボールパターンの電極個数、Ｎは経路の節数）の定義電極の各電極の画像予測領域を生成し、
既存経路Γがあり、Γが成長してΓ’となりうるとき、Γを保存したまま新たにΓ’を生成して登録し、
１つの画像抽出電極があるとき、ボールパターン個々の定義電極と結合した大きさ１の経路を生成して登録することを特徴とする請求項１乃至３のいずれかに記載のボール部品の認識方法。
【請求項５】
ボール部品を画像により認識するための、画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置において、
画像からボール電極の座標を次々と抽出する手段と、
画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納する手段と、
経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力する手段と、
画像抽出電極座標と前記予測領域の包含を判定する手段と、
包含されると判定されたとき、節を追加して経路を成長させる手段と、
経路とボールパターンを照合する手段と、
を備えたことを特徴とするボール部品の認識装置。
【請求項１】
画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置を用いて、ボール部品を画像により認識する方法であって、
画像からボール電極の座標を次々と抽出し、
画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納し、
経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力し、
画像抽出電極座標と前記予測領域の包含を判定し、
包含されると判定されたとき、節を追加して経路を成長させ、
経路とボールパターンを照合することを特徴とするボール部品の認識方法。
【請求項２】
前記ボール電極の座標が、ボール電極の中心座標であり、
前記経路の節が、画像抽出電極座標とボールパターン定義電極位置指標を結合したデータであり、
前記経路の大きさ即ち節の数を使ってボールパターンとの一致を判定することを特徴とする請求項１に記載のボール部品の認識方法。
【請求項３】
前記経路の大きさが、所定の一致判定数Ｈ（Ｈは１≦Ｈ≦Ｐである整数、Ｐはボールパターンの電極個数）以上のとき、認識成功即ちボールパターンの完全一致とみなすことを特徴とする請求項２に記載のボール部品の認識方法。
【請求項４】
前記画像の中に座標Λを定め、
この座標Λから概ね近い順に電極を抽出し、
ボールパターンにおいて経路が踏んでいない残りＰ−Ｎ個（Ｐはボールパターンの電極個数、Ｎは経路の節数）の定義電極の各電極の画像予測領域を生成し、
既存経路Γがあり、Γが成長してΓ’となりうるとき、Γを保存したまま新たにΓ’を生成して登録し、
１つの画像抽出電極があるとき、ボールパターン個々の定義電極と結合した大きさ１の経路を生成して登録することを特徴とする請求項１乃至３のいずれかに記載のボール部品の認識方法。
【請求項５】
ボール部品を画像により認識するための、画像入力部と、ボールパターン認識部と、部品認識部と、制御部とから構成される部品認識装置において、
画像からボール電極の座標を次々と抽出する手段と、
画像抽出電極とボールパターン定義電極を結合したデータを節とするグラフでなる経路を生成して格納する手段と、
経路を入力として、ボールパターン定義電極について画像上に存在予測領域を出力する手段と、
画像抽出電極座標と前記予測領域の包含を判定する手段と、
包含されると判定されたとき、節を追加して経路を成長させる手段と、
経路とボールパターンを照合する手段と、
を備えたことを特徴とするボール部品の認識装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００７−２６６１０７（Ｐ２００７−２６６１０７Ａ）
【公開日】平成１９年１０月１１日（２００７．１０．１１）
【国際特許分類】
【出願番号】特願２００６−８６１４５（Ｐ２００６−８６１４５）
【出願日】平成１８年３月２７日（２００６．３．２７）
【出願人】（０００００３３９９）ＪＵＫＩ株式会社 (1,557)
【Ｆターム（参考）】
【公開日】平成１９年１０月１１日（２００７．１０．１１）
【国際特許分類】
【出願日】平成１８年３月２７日（２００６．３．２７）
【出願人】（０００００３３９９）ＪＵＫＩ株式会社 (1,557)
【Ｆターム（参考）】
[ Back to top ]