JPH0132549B2 - - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は物体の検査識別等に用いる視覚システ
ムの物体検出部分に関し、詳しくは二値化画像デ
ータ上の物体輪郭線を高速に検出する方法にかか
わる。

従来例の構成とその問題点 最近、米国や日本国内において物体の検査、識
別等に用いる汎用の視覚システム（ビジヨン・シ
ステム）が多数開発されている。これらシステム
において、物体形状を検査、識別する場合とられ
た方法は過去主として二種あつた。一つは、画像
データ上の領域点の統計的性質を用いる方法であ
る。例えば、面積、長径や短径、慣性モーメント
等の統計量を基準として識別する。二つ目は、物
体の特徴ある部分をテンプレート（基準画像）と
し、対象画像との間に相関演算を行ない、その相
関係数より基準画像に対応する画像の存否を得
て、これにより識別する方法である。

前者は輪郭形状を直接用いていないため、複雑
な形状の物体への適用は難しい。また、後者はテ
ンプレートの大きさや角度等に限定条件が派生し
汎用化が難しい。

いずれにせよ輪郭形状データを活用したもので
はない。何故なら輪郭線を検出する方法は通常、
計算機を用いプログラム・モードにて実行され、
これを大容量の画像データに適用した場合、処理
速度が遅くなる。

発明の目的 本発明はこのような問題点に対し、固定の輪郭
線探索表を用いて、探索手順を単純化し、これを
ハードウエア化することにより探索に要する処理
速度を向上させることを目的とする。

発明の構成 本発明は輪郭線検出方法は、画像入力装置より
入力した三次元物体の正射影二値化画像を記憶す
るステツプと、前記画像をフイルタ処理した画像
を記憶するステツプと、記憶した画像データを線
順次に走査することにより追跡すべき輪郭線の始
点を検出するステツプと、得られた始点に従つて
固定の輪郭線探索テーブルを用いさらに検出禁止
領域を書き込んだオーバレイ・メモリをアクセス
しながら輪郭線を追跡するステツプとからなり、
高速に輪郭線の検出を行なえるものである。

実施例の説明 一般的な輪郭線追跡手順は以下のようにまとめ
ることができる。

(1) 画像を系統的に走査して、検出基準を満たす
点（始点および終点）を探す。そのような点が
見つかると、それが参照点となる。

(2) 参照点の近傍を調べ、適切な追跡基準を適用
する。検出した点を新しい参照点とし、終端条
件を満たしていない場合は(2)へもどる。

(3) 系統的な走査が完了すると、このアルゴリズ
ムは終了する。

この手順で検出基準や追跡基準、終端条件を
種々変更することにより、さまざまな追跡アルゴ
リズムを構成することができる。

本発明で用いた手法は以下のものである。

(1) まず４端辺を切断する形状の場合について探
索始点を検出する。これは第２図ａのように、
画像メモリの４端辺上を右まわりに走査し、領
域外→領域内（〇→●）に変化する境界点（第
２図ａの矢印）を検出するもの。

(2) (1)で検出した始点を参照点とし、開始方向数
（検出方向数）を得て輪郭線探策（項(4)〜(6)参
照）を行なう。

(3) 輪郭線メモリ上に残された輪郭線（これらは
４端辺を切断しない）を第２図ｂのように線順
次に走査し探索始点を検出する。

(4) 得られた始点を参照点とし、開始方向数（検
出方向数）を得て追跡を開始する。

(5) 前参照点での検出方向数をｉとすると、ｉ−
３の方向より順次反時計まわりに探索し領域点
をさがす（第４図参照）。

(6) 検出した次の境界点座標をデータ列に加え、
これを新しい参照点とする。同時にこの点を輪
郭線用メモリから消去し、禁止領域用メモリに
書き込む。この点が既検出点（禁止領域用メモ
リ上の点）又は画像の４端辺に一致しないとき
は(5)へもどる。

(7) 一本の輪郭線について終了。次の輪郭線を求
める時は(3)へもどる。

(8) 終了。

（ただし、輪郭線メモリには、４近傍のフイル
タ処理にて入力画像より抽出した輪郭線が書きこ
んである。） ここで、この方法がすべての輪郭線を検出する
ことを示す。

まずヨコ方向に走査するものとして、検出され
る始点付近の輪郭形状は第５図の如く二種類あ
る。これに対し他方向の走査により得られる形状
は他に各々三種類あるが第５図にて代表して支障
ない。そして開始方向数を第５図ａの場合７、ｂ
の場合も７とする。

この場合次の参照点との位置関係を第５図ａの
ものを第６図に、ｂのものを第７図に示した。こ
のように第６図の場合、方向４より探索を開始す
れば次の参照点が検出できる。同じように第７図
の場合も検出できる。

次に輪郭線上での検出を考える。第８図のよう
に前参照点より６の方向には検出された場合、現
参照点から見て３の方向は必ず背景点となる。ま
た、これより時計まわりの方向に次の検出点は存
在しないとして支障ない。従つて３の方向より反
時計まわりに探索すれば次の参照点が検出でき
る。

以上より帰納して、本手法を用いればすべての
輪郭線を検出できることがわかる。

この結果８近傍探索の手順は単純なものとな
る。これを第９図には説明する。

参照点の８近傍の画素データを方向数にあわせ
方向１〜方向８のデータとする。第９図の方向１
〜８はこれに対応する。図の表（以下探索表と呼
ぶ）の内容は、〇が背景点、●が領域点を示すビ
ツト・パターンとなる。最下段の数字は次の参照
点への方向数を示し、方向１〜８のビツト・パタ
ーンで表を参照することにより得られる。例えば
前方向数が５であれば、現参照点から見て方向２
は必ず背景点となる。次に２〓８〓１の順で最初
の領域点を得る方向が次の参照点への方向数であ
る。

このように前方向数にあわせ探索表を８種用意
すれば、８近傍点の画素データ検出と表の参照の
みで輪郭点の検出ができる。

また、画像メモリに重ねる形でビツト・プレー
ンとなるオーバレイ・メモリを用意し、ここに終
点および探索禁止領域を書き込んでおく。これを
８近傍点の画素データ検出と同時に検出し、次の
参照点が終点又は禁止領域に達したかをチエツク
する。

このように本発明は、探索表および終端条件を
書き込んだオーバレイ・メモリと、４近傍のフイ
ルタ処理にて抽出した輪郭線を書き込んだ輪郭線
用メモリを用い、従来プログラム制御で行なわれ
ていた輪郭点追跡をランダムロジツクによるハー
ドウエアにて実現可能とし、あわせて高速処理を
実現したことに特徴を有するものである。

第１図は本発明を実施するための装置の概要を
示す図である。図において１０１は画像入力部で
ある。画像入力部１０１より入力された三次元物
体の正射影二値化画像は画像記憶部１０２に記憶
される。１０２は画像メモリとこれに重ねたオー
バレイ・メモリ、および４近傍のフイルタ回路と
二値化回路、輪郭線用メモリにより構成される。
１０８は探索開始点検出部である。第２図ａのよ
うに４端辺上の探索開始点の検出と、第２図ｂの
ように端辺以外の部分の探索開始点の検出を１０
７を介し、画像記憶部１０２を用いて行なう。制
御部１０７はこのデータをもとに輪郭線の始点と
開始方向数を各々アドレス算出部１０５と輪郭点
探索部１０４へ送り、DMA部１０３よりの終端
点情報により追跡を終了する。終了後、他の輪郭
線検出のため、探索開始点検出部１０８へ制御を
移す。

DMA部１０３は参照点又は始点の周囲８近傍
点を画像記憶部１０２よりアクセスする。同時に
参照点座標に関し、輪郭線用メモリ上のデータを
消去し、オーバレイ・メモリにデータを書き込
む。さらにアクセスしたデータを輪郭点探索部１
０４へ送り、このオーバレイ・データを一旦記憶
する。輪郭部探索部１０４にて検出された次の参
照点への方向数と前記記憶データを比較し終端情
報を検出する。終端の場合は従端情報を制御部へ
送る。

輪郭点探索部１０４はDMA部より得た８近傍
点データと一旦記憶した前方向数により次の参照
点（輪郭点）への方向数を探索表より読み出す。
探索表はROMで構成され、入力データは前方向
数の3bitと８近傍点データの8bitの合計11bitがア
ドレスとして与えられ、これにより次の方向数
3bitとエラー情報1bitの合計4bitが読み出される。
エラー情報は８近傍点が全て“１”又は全て
“０”、方向ｉ−３が“１”の時、“１”を出力す
るよう書き込んでおく。読み出された方向数はア
ドレス算出部１０５へ、エラー情報は制御部１０
７へ送られる。

アドレス算出部１０５は輪郭点探索部１０４に
て得られた方向数に従つてアドレスをＸ、Ｙ方向
に各々増減させ、次の参照点アドレスを算出す
る。得られた次の参照点アドレスをDMA部１０
３へ送り、また検出した方向数とともに、輪郭デ
ータ記憶部１０６へ送り記憶する。

第１０図はDMA部および輪郭点探索部、アド
レス算出部の具体的な実施例を示す図である。ま
ず制御部より始点アドレスがバツフア〔２〕１０
０７へ、開始方向数がバツフア〔１〕１００４へ
送られる。バツフアのアドレスに従いメモリー・
アクセス回路１００１は８近傍データをアクセス
し、探索表１００３および比較回路１００２へ送
る。同時にバツフアのアドレスに従い、輪郭線用
メモリ３０３上のデータを消去し、オーバレイ・
メモリ３０５にデータを書きこむ。比較回路へ送
られたオーバレイ・データは一旦記憶される。探
索表より次の方向数が得られ、これはバツフア
〔１〕と演算テーブル１００５、輪郭データ記憶
部へ送られる。バツフア〔１〕の方向数に従い、
先に記憶した比較回路の該当bitを比較し、終端
情報を得る。演算テーブルには各方向に対する
Ｘ、Ｙ方向の増減値が書き込まれており、これを
演算回路へ送り次の参照点アドレスが算出され
る。演算結果は輪郭データ記憶部とバツフア
〔２〕へ送られる。

また以上の方法を第１１図に示したような、画
像メモリ１１０２、CPU１１０３、および一時
記憶１１０４による構成の装置により実施するこ
ともできる。この場合CPUの動作順序は第１２
図に示したものとなる。

発明の効果 このように本発明は、探索表および終端条件を
書き込んだオーバレイ・メモリと、４近傍のフイ
ルタ処理にて抽出した輪郭線を書き込んだ輪郭線
用メモリを用い、従来プログラム制御で行なわれ
ていた輪郭点追跡をランダム・ロジツクによるハ
ードウエアにて実現可能とし、あわせて高速処理
を実現する方法である。

【図面の簡単な説明】

第１図は本発明を実施するための装置の概要を
示すブロツク図、第２図ａ，ｂは探索開始点の検
出方法を示す図、第３図は画像記憶部の具体的な
実施例を示すブロツク図、第４図は方向数と探索
順序を説明する図、第５図は検出された始点付近
の輪郭形状を示す図、第６図は開いた図形におい
て始点とその隣接点の位置関係を示す図、第７図
は閉じた図形において始点とその隣接点の位置関
係を示す図、第８図は一般に輪郭線上での隣接点
との位置関係を示す図、第９図は前方向数が５の
時の探索表を示す図、第１０図はDMA部および
輪郭点探索部、アドレス算出部の具体的な実施例
を示すブロツク図、第１１図および第１２図は本
発明の他の実施例を説明するための図である。 １０１……画像入力部、１０２……画像記憶
部、１０３……DMA部、１０４……輪郭部探索
部、１０５……アドレス算出部、１０６……輪郭
データ記憶部、１０７……制御部。

Claims (1)

【特許請求の範囲】
1. １ 画像入力装置より入力した三次元物体の正射
   影二値化画像を記憶するステツプと、前記画像を
   フイルタ処理した画像を記憶するステツプと、記
   憶した画像データを線順次に走査することにより
   追跡すべき輪郭線の始点を検出するステツプと、
   得られた始点に従つて固定の輪郭線探索テーブル
   を用いさらに検出禁止領域を書き込んだオーバレ
   イ・メモリをアクセスしながら輪郭線を追跡する
   ステツプとで構成されることを特徴とする輪郭線
   検出方法。