JP2641237B2 - 円形物体認識方法 - Google Patents

Description

【発明の詳細な説明】 概要 ２次元波動方程式を用いた円形物体認識方法に関し、 複数のフレームメモリを設けて演算速度の高速化を図
った円形物体認識方法を提供することを目的とし、 円形物体もしくはこれに類似した物体の画像を２次元
濃淡値として演算装置に入力し、該濃淡値を初期値とす
る２次元波動方程式を解かせ、該方程式の解における振
幅の極値により円形物体の中心位置を確認させる円形物
体認識方法において、少なくとも２個のフレームメモ
リ、すなわち第１フレームメモリ及び第２フレームメモ
リを設け、第１フレームメモリに所定時間後の画像の２
次元濃淡値を保持させ、第２フレームメモリに該２次元
濃淡値の時間微分値を保持させるように構成し、ステッ
プ１で原画像の２次元濃淡値を第１フレームメモリに書
き込むと共に第２フレームメモリに０を代入し、ステッ
プ２で第１フレームメモリに保持されている画像のラプ
ラシアンを求めて、これを第２フレームメモリの内容に
加算した結果を第２フレームメモリに書き込み、ステッ
プ３で第２フレームメモリの内容に１未満の所定数を乗
じて、この値を第１フレームメモリの内容に加算した結
果を第１フレームメモリに書き込み、上記ステップ２及
びステップ３を反復して所定の閾値以上の第１フレーム
メモリのx,yアドレスから円形物体の中心位置を求める
と共に、反復回数から円形物体の半径を求めるように構
成する。

産業上の利用分野 本発明は２次元波動方程式を用いた円形物体認識方法
に関する。

機械産業における物体の視覚認識の対象として円形の
占める割合は多い。旋盤、フライス盤の作業の大部分は
円の形成であり、ボルト、リベットの締結は丸穴に対し
て行われる。また、電子部品の搭載に広く用いられるプ
リント板の端子部は、リング状になっているものが多
い。プリント配線で形成されるので各端子部の位置は既
知であるが、若干の位置ずれが生じるのは避けられない
ことなので、自動ボンディングに際しては端子部の中心
位置を求め、正確なボンディングが行われるようにする
ことが望まれる。ロボットを導入した生産設備では、上
流側工程で作られ搬送されてくる部品をロボットが１つ
ずつ取り上げて加工機械へ装着したり、あるいは下流側
工程へのコンベアへ移す等の操作をしているが、この際
も部品位置、形状を正しく認識することが必要である。
円形物体の認識に際し、測定すべき量は円の中心位置座
標と半径である。

従来の技術 円形物体の認識方法は種々提案されているが、従来の
方法の多くは輪郭を抽出して重心及び周の長さを計算す
るため、輪郭線が途切れたときに閉ループとしてトレー
スできず、重心及び周長が計算できなくなるという欠点
があった。この途切れが微小であればその間を埋める技
術が知られているが、大きい部分が欠けると難しい場合
が多い。

この欠点は反射光を用いて濃淡画像を処理する時特に問
題となる。

そこで、背景や表面の模様、ノイズに惑わされない認
識方法として、一様な処理、マクロ的手法の有効性が指
摘されている。画像の周囲から波動を発生させて骨格線
を抽出する方法もその１例である。

同様の発想で円形物体の外周を水面上の波になぞら
え、外周から伝播した波動が一定時間後に中心に集まり
ピークができることを利用して、その中心位置を求める
図形認識方法が特開昭58−51387号に開示されている。

この公開公報に開示された図形認識方法においては、
円形物体の認識に波動方程式を用いているが、波動方程
式は次のような観点から用いられている。例えば、円形
の洗面器に水をはり、縁に衝撃を与えると周囲から発生
した波が中心に向かって伝わり、所定時間後に中心にピ
ークを生ずるであろう。そこで、円形物体の周囲を水面
上の円形に囲まれた部分と見做し、計算器内部で波の動
きをシミュレートすれば、同様にピークを生ずるはずで
ある。ピークの位置が分かれば円形の中心位置を知るこ
とができ、半径においてはピークに到達するまでの時間
から求めることができる。

この認識方法の強みは、円の一部が欠けていたり、複
数の円が互いに重なっていてもよいことである。ピーク
が生じる理由は円周上で同時に発生した波動が中心点に
おいては全て同位相で強め合うからであるが、円が一部
で欠けていても残った円弧が充分な長さを持っていれ
ば、そこから発生した波についてはやはり同位相で強め
合うことには違いがないからである。表面上の模様やノ
イズについてはそれらが円形でない限り発生する波の位
相はランダムで大きなピークを生ずることがなく、本来
円周から発生する波とは独立で干渉することはない。

発明が解決しようとする課題 上述した公開公報に記載の図形認識方法は、表面上の
模様やノイズ等に干渉されることがなく円形物体の中心
位置及び半径を正確に求めることができるという利点が
あるが、その演算に時間を要するという問題があった。

本発明はこのような点に鑑みてなされたものであり、
その目的とするところは、複数のフレームメモリを設け
て演算速度の高速化を図った円形物体認識方法を提供す
ることである。

課題を解決するための手段 第１図に本発明の原理フローチャートを示す。

本発明では少なくとも２個のフレームメモリを使用す
る。すなわち第１フレームメモリＡ及び第２フレームメ
モリＶを設け、第１フレームメモリＡに所定時間後の画
像の２次元濃淡値を保持させ、第２フレームメモリＶに
該２次元濃淡値の時間微分値を保持させる。

ステップ１で原画像の２次元濃淡値Ａ（x,y,0）を第
１フレームメモリＡに書き込むと共に第２フレームメモ
リＶに０を代入し、さらに近似回数を示すカウンタｎを
１に設定する。ステップ２で第１フレームメモリＡに保
持されている画像のラプラシアンΔＡを求めて、これを
第２フレームメモリＶの内容に加算した結果を第２フレ
ームメモリＶに書き込む。次いでステップ３では、第２
フレームメモリＶの内容に１未満の所定数、例えば1/8
を乗じて、この値を第１フレームメモリＡの内容に加算
した結果を第１フレームメモリＡに書き込む。

ステップ４においては、所定の閾値Ｓ以上の第１フレ
ームメモリのアドレスx,y及びｎの値を検出し、これら
をピークテーブルに書き出す。ステップ５でカウンタｎ
の値を１つインクリメントし、ステップ６ではｎが 画素以上であるか否かを判断する。ここでＲは見つけよ
うとする円の最大半径であり、１近似サイクルで波は 画素だけ進むものとする。ステップ６において否定判定
の場合には、ステップ２〜５を反復し、肯定判定の場合
には本ルーチンを終了する。

この処理ルーチンにより、所定の閾値Ｓ以上の第１フ
レームメモリＡのx,yアドレスから円形物体の中心位置
を求めると共に、反復回数から円形物体の半径を求め
る。

作用 本発明では、濃淡画像の輝度を水平・垂直方向の座標
x,y及び時刻ｔの三変数関数と見做す。これをＡ（x,y,
t）と書き、時刻t_oに入力した１フレームの画像Ａ（x,
y,t_o）を初期値として２次元の波動方程式 但しａは波の速度 を解くようにする。境界条件は画像フレームの周辺上
（正方形）で常にＡ（x,y,t）＝０とする。これを物理
的にみると、正方形の周辺を固定された弾性膜の状態を
記述する方程式と同じである。

（１）式を差分方程式に直して逐次的に解くため、新
たな変数 を導入し一階の連立方程式とする。

即ち、１式をＶ（x,y,t）を用いて書き直すと次のよ
うになる。

（２）式を差分近似式に置き換えると次のようにな
る。

Ｖ（x,y,t＋δt/2） Ｖ（x,y,t−δt/2）＋a²δｔΔＡ（x,y,t） Ａ（x,y,t＋δｔ） Ａ（x,y,t）＋δtV（x,y,t＋δt/2） ……（３） （３）式を解くアルゴリズムは以下で与えられる。

ステップ1:V＝0,A＝Ａ（０） ステップ2:V←Ｖ＋a²δｔΔＡ ステップ3:A←Ａ＋δtV ステップ4:ステップ２へ戻る 上述したアルゴリズムでa²δ＝1,δｔ＝1/8としたも
のが第１図に示した本発明の原理フローチャートであ
り、この演算は例えば特開昭62−137669号に開示されて
いるような汎用の局所並列型画像プロセッサを使用して
効率的に実行することができる。

第１図の原理フローチャートにおいて、ステップ２及
びステップ３では各フレームメモリの内容全体について
演算を行うことを意味し、それぞれのステップに要する
時間は１フレーム周期すなわち約33msである。ステップ
２及びステップ３の繰り返しを１近似サイクルと呼ぶと
き、第ｎ近似サイクル進んだ時点で第１フレームメモリ
ＡはＡ（x,y,t＋ｎΔｔ）を保持する。ステップ２及び
ステップ３においては、１フレーム周期内にフレームメ
モリの内容全体についての演算を行うことが必要なため
本処理ルーチンを実行するためには高速の画像プロセッ
サを一般的に必要とし、ステップ４におけるピークテー
ブルは第２図に示すようになっており、このピークテー
ブルから円の中心の座標x,y及びその半径を容易に求め
ることができる。

実 施 例 第１図のフローチャートは本発明の原理を示したもの
であるが、ある種の画像プロセッサでは第１図の処理フ
ローを実行できないことがある。例えば、ステップ２で
第２フレームメモリＶから読み出したデータにラプラシ
アンΔＡを加えて同じフレームメモリＶに書き込んでい
るが、１フレーム周期内でこれを行うことは一般に難し
い。サンプリング周期内でメモリ素子のリードとライト
を切り換える必要があるからである。各フレームメモリ
は１フレーム周期内では常にリード状態かライト状態に
なっているほうが制御しやすく回路も簡単になる。

また、プロセッサによっては第１図のステップ２のよ
うに１枚のフレームメモリにラプラシアンをかけながら
他のフレームメモリと加算することができないかもしれ
ない。つまり、単純なフレーム加算の機能しかないかも
しれない。このような単純な機能しかないプロセッサ上
で本発明を実行するには作業メモリの数を増やし第３図
の処理フローのようにすればよい。

すなわち本実施例においては、フレームメモリＡ及び
フレームメモリＶに加えて２枚の作業メモリW₁,W₂を追
加する。ステップ11において、フレームメモリＡに原画
像の２次元濃淡値を書き込むと共に、フレームメモリＶ
に０を代入する。さらに近似回数を示すカウンタｎを１
に設定する。次いでステップ12に進みラプラシアン画像
ΔＡを作業フレームメモリW₁に書き込み、作業フレーム
メモリW₁から読み出したデータにフレームメモリＶの内
容を加えて作業フレームメモリW₂に書き込むと共に、作
業フレームメモリW₂から読み出したデータをフレームメ
モリＶに書き込む。ステップ12においては、上述した各
演算を逐次的に行うため、３フレーム周期の時間が必要
である。次いでステップ13において、フレームメモリＶ
から読み出したデータに1/8を乗じて作業フレームメモ
リW₁に書き込み、作業フレームメモリW₁から読み出した
データとフレームメモリＡから読み出したデータとを加
えて作業フレームメモリW₂に書き込むと共に、作業フレ
ームメモリW₂のデータをフレームメモリＡに書き込む。
ステップ13においても上述した各演算に１フレーム周期
を要するため、全体で３フレーム周期を要する。ステッ
プ12は第１図のフローチャートのステップ２と同等の演
算を行ってあり、ステップ13は第１図のステップ３と同
等の演算を行っている。

次いでステップ14に進んで、所定の閾値Ｓ以上となる
フレームメモリＡのアドレスx,y及びｎの値を第２図に
示すようなピークテーブルに書き出す。ステップ15では
カウンタｎを１つインクリメントし、ステップ16におい
てｎが 画素以上か否かを判断し、否定判定の場合にはステップ
12〜15を繰り返し、肯定判定の場合には本処理ルーチン
を終了する。上述したように本実施例においては４枚の
フレームメモリを使用し、１回の近似に要する時間は６
フレーム周期である。

より多くの作業メモリを使用することにより、第３図
の実施例より短時間で演算を実行するようにすることも
できる。第４図は５枚のフレームメモリを使用した本発
明の実施例を示している。

第４図において、まずステップ21でフレームメモリA
_evenに原画像の２次元濃淡値を書き込むと共にフレーム
メモリV_evenに０に代入する。さらに近似回数を示すカ
ウンタｎを１に設定する。ステップ22では、フレームメ
モリA_evenのラプラシアン画像ΔA_evenをフレームメモリ
Ｗに書き込むと共に、フレームメモリＷから読み出した
データとフレームメモリV_evenから読み出したデータと
を加えてフレームメモリV_oddに書き込む。ステップ23に
おいては、フレームメモリV_oddから読み出したデータに
1/8を乗じてフレームメモリV_evenに書き込むと共に、フ
レームメモリA_evenから読み出したデータにフレームメ
モリV_evenから読み出したデータを加えてフレームメモ
リA_oddに書き込む。ステップ22及びステップ23におい
て、各々の演算を行うのに１フレーム周期を必要とする
ため、ステップ22及びステップ23を実行するためにはそ
れぞれ２フレーム周期の時間が必要である。ステップ22
は第１図のフローチャートのステップ２と同等な演算を
実行しており、ステップ23は第１のステップ３と同等な
演算を実行している。

次いでステップ24に進んで、フレームメモリA_oddが所
定の閾値Ｓ以上となるアドレスx,y及びｎの値を第２図
に示すようなピークテーブルに書き出す。ステップ22〜
ステップ24で奇数番目の近似サイクルを実行しているこ
とになる。

ステップ25でカウンタｎを１つインクリメントして、
ステップ26〜ステップ28に進み、偶数番目の近似サイク
ルを実行する。ステップ26〜ステップ28はステップ22〜
ステップ24のevenをoddに換え、oddをevenに換えて全く
同様な処理を実行している。

ステップ29でカウンタｎの値をさらに１つインクルメ
ントしてから、ステップ30に進んでｎが 画素以上か否かを判断し、否定判定の場合にはステップ
22からの処理を反復実行し、肯定判定の場合には本処理
ルーチンを終了する。本実施例においては５枚のフレー
ムメモリを使用したことにより、４フレーム周期の時間
で演算を実行することができる。

第５図は本発明の演算を実行するのに適した画像処理
プロセッサの構成例であり、特に第４図に示した実施例
の演算処理に適している。同図において、10₀〜10₄はフ
レームメモリであり、フレームメモリが５個設けられて
いる。各フレームメモリは双方向バスバッファ12を介し
て８ビットのビデオバス14に接続されている。16は空間
フィルタであり、ラインバッファ18、ラプラシアン処理
部20及びスケーリング回路22を含んでいる。24は加算回
路であり、この加算回路24と空間フィルタ16とは破線で
示すように内部バスでパイプライン結合されている。26
はA/D変換及びD/A変換を行う変換回路である。

発明の効果 本発明は以上詳述したように構成したので、円形物体
の認識を正確且つ高速に実行できるという効果を奏す
る。

【図面の簡単な説明】

第１図は本発明の原理フローチャート、 第２図はピークテーブルの模式図、 第３図は本発明実施例のフローチャート、 第４図は本発明の他の実施例のフローチャート、 第５図は本発明に適用可能な画像処理プロセッサの概略
構成図である。 10₀〜10₄……フレームメモリ、 12……双方向バスバッファ、 14……ビデオバス、16……空間フィルタ、 24……加算回路。

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】円形物体もしくはこれに類似した物体の画
   像を２次元濃淡値として演算装置に入力し、該濃淡値を
   初期値とする２次元波動方程式を解かせ、該方程式の解
   における振幅の極値により円形物体の中心位置を確認さ
   せる円形物体認識方法において、 少なくとも２個のフレームメモリ、すなわち第１フレー
   ムメモリ及び第２フレームメモリを設け、 第１フレームメモリに入力された画像の２次元濃淡値を
   保持させ、第２フレームメモリに該２次元濃淡値の時間
   微分値を保持させるように構成し、 ステップ１で原画像の２次元濃淡値を第１フレームメモ
   リに書き込むと共に第２フレームメモリに０を代入し、 ステップ２で第１フレームメモリに保持されている画像
   のラプラシアンを求めて、該ラプラシアンと第２フレー
   ムメモリの内容との和を第２フレームメモリに書き込
   み、 ステップ３で第２フレームメモリの内容に１未満の所定
   数を乗じて、該乗算により得られた値と第１フレームメ
   モリの内容との和を第１フレームメモリに書き込み、 上記ステップ２及びステップ３を反復して実行して、所
   定の閾値以上の第１フレームメモリのx,yアドレスから
   円形物体の中心位置を求めると共に、反復回数から円形
   物体の半径を求めることを特徴とする円形物体認識方
   法。