JPH0444985B2

JPH0444985B2 -

Info

Publication number: JPH0444985B2
Application number: JP59200401A
Authority: JP
Inventors: Takanori Ninomya; Toshiaki Ichinose; Yasuo Nakagawa
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1984-09-27
Filing date: 1984-09-27
Publication date: 1992-07-23
Also published as: JPS6180376A

Description

【発明の詳細な説明】

〔発明の利用分野〕本発明は、検出された２値画像のパターン上に
複数の点を指定した場合に、それら点がパターン
によつて連結されているか否かを高速に検出する
ための連結関係検出装置に関するものである。〔発明の背景〕回路パターンの検査などでは、断線やシヨート
などの欠陥を検出するために回路パターンをリニ
アセンサ等で撮像してこれを二値化しした２値画
像を得、その特定の点の間が検出画像上のパター
ンによつて連結しているか否かをしらべることが
ある。このような２値画像のパターンの連結関係
を調べる方法としては、特公昭58−16217公報
「連結領域検出方法」や「連結領域のぬりつぶし
及び番号づけに関する一考察」（信学技報IE78−
９）に開示される方式が知られている。しかし、
これらの方式では、検出２値画像のパターン（値
が１または０の部分）のうち、すべての連結され
たパターン各々の分離抽出を目的としている。このため、例えば第３１図に示すような５個の
独立したパターン（各閉領域をレベル１のパター
ンとする）が２値画像の形で存在した時にはこれ
を上記の方法で処理するとラベルと呼ばれる番号
１〜５がすべてのパターンに付され、これらはテ
ーブル形式でメモリ上に格納される。しかし回路
パターンの断線等の検査のためにはこのようなす
べてのパターンの分離は必ずしも必要ではなく、
例えば第１図の×印を付けた３つの点相互間の連
結関係のみが検出できればよいという場合があ
り、このような場合にはラベル１，４，５は不要
である。また対象とするパターン全体が非常に複
雑なものである場合は、リニアセンサを用いて例
えば水平方向に１ラインづつ二値化画像を検出し
ながら同時に連続性も検出するという方法がとら
れる。この時には例えば第３２図に示したように
上方から水平な検出ラインで順次二値化画像を検
出しその連結性をしらべていくとすると、検出ラ
インl₁まで進んだ時点ではラベル１，２を付され
たパターンはまだ別のものと判定されている。こ
れが更に進んで検出ラインl₂まで来た時にはラベ
ル１，２をもつパターンが連結していることがわ
かるから、このことをメモリ上のテーブルに記憶
しておく必要がある。第３３図はそのテーブルの
構造を示す図で、各ラベル１，２に対応してアド
レス１，２（これは実際には相対アドレスと考え
てよい）が割当てられており、その内容のデータ
としては、ラベル１，２のパターンがまだ孤立し
ていると判断されている時はラベル１及び２がそ
のまま書込まれている。ところがこれらが連続し
たものであることが判ると、そのデータの小さい
方の値に書換えられる。第３３図はこの書換え後
の状態を示しており、ラベル１，２をもつパター
ンは、そのデータが同一なので連結していること
がわかる。そしてもし第３２図のようなパターン
が上方にｎ個に枝分れしていればｎ個のアドレス
をもつた第３３図のようなテーブルが必要とな
る。以上のように、従来方式を用いてリニアセンサ
などで二値画像を検出しながら、そのすべてのパ
ターの連結関係を抽出していく場合は、第３１図
で説明した二値画像上に存在する連結したパター
ンの数に等しい個数のラベルと、第３２図で説明
したような上方向に複数個枝分れしたパターンの
場合に余分に必要とするラベル（ｎ分岐のときｎ
−１個）とをすべて格納するだけのメモリ容量が
必要となる。しかるに検出対象とするパターンが
第３１図や第３２図のように単純なものでなく、
極めて複雑で大規模な回路パターン等の場合に
は、上記のような作業用のメモリ容量が非常に大
きくなるという不具合がある。〔発明の目的〕本発明の目的は、検出された二値画像のパター
ン上に外部より複数の点が指定された場合に、そ
れら点がパターンによつて連結されているか否か
メモリ容量を少なくして、しかも高速に検出し得
る連結関係検出装置を供するにある。〔発明の概要〕この目的のため本発明は、その連結関係を検出
すべき点の各々に相異る番号を付けてメモリ上の
アドレスに夫々対応づけ、ある点がいずれかのパ
ターン上に見出された時にはそのパターンのラベ
ルとしてその点の番号を付けて当該点対応のアド
レスへデータとして書込むとともに、同一パター
ンに相異るラベルが付された時にはこれらを予め
定められた方法によつて上記メモリ上でそのうち
の１つに書換え、かくして任意の２つの点はその
点対応のアドレスに格納されたラベルが同一の
時、かつその時のみ結合関係にあると判定すべく
なしたものである。具体的には二値画像信号を前
処理する画像入力部、画素変化アドレスを検出す
るコード変換部、画素変化アドレス間に指定され
た点が存するか否かを検出するグリツド番号割付
部、画素変化アドレスより隣接ライン上での連結
関係を検出するラベル付け処理部などより構成さ
れるが、画像入力部とコード変換部との間にはラ
インバツフアメモリを、また、コード変換部とグ
リツド番号割付部との間にはFIFOを、更にグリ
ツド番号割付部とラベル付け処理部との間にはラ
インテーブルメモリを介在させることによつてそ
れぞれの部分が並行処理動作し得るようになした
ものである。〔発明の実施例〕以下、本発明をその理論的背景を説明したうえ
で詳細に説明する。先ずその理論的背景であるが、例えば対象とす
るパターンが第２図に示す如くであつて、連結関
係をしらべたい点（以下グリツド点という）には
グリツド番号１〜６が付されているとする。リニアセンサ等によつて第２図上方のラインよ
り順次パターンの検出が行われていつたときまだ
１つもグリツド点が検出されていない状況では、
各パターンには第３図のように共通のラベル０が
付される。ここで「パターンにラベルを付ける」
ということは、メモリ内に検出されたパターン毎
のエリアを作成しておき、そのエリア内のラベル
らんにラベル記号（番号）を記入することを意味
し、その具体的方法は後述する。このパターン対
応の作業エリアとすぐ後で説明する連結テーブル
Ｔとは別のものである。さて上記のラベルは、０に限らずグリツド番号
にないものであれば何でもよく、これを仮想グリ
ツド番号と呼ぶが、以下では番号０を使うことに
する。次にさらに検出が進み、第４図に示す状況
になつた場合を考える。１つのパターンが２つに
分岐を始めているが、まだグリツド点は検出され
ていない。しかしこのままラベル０を付したまま
にしておくと、ラベル０がまだグリツド点が検出
されていない全パターンに共通のラベルであるた
め、後に分岐パターンにグリツド点が見出された
時にそれらと他のパターンとの区別ができなくな
る。そこでこのようにラベル０のパターンに分岐
が生じたときは、グリツド番号、仮想グリツド番
号にもなく、かつグリツド番号より常に大（又は
小）の番号（これを仮番号とよぶ）を仮ラベルと
して付す。ここではこの仮ラベルを７とする。さ
て、ここでグリツド点間の連結関係を記憶してお
くための連結テーブルＴについて述べる。連結テ
ーブルＴは、第５図に示すように、アドレスＡ(I)
の内容をデータＤ(I)とすると、グリツド点Ｉの属
するパターンにラベルＤ(I)が付されていることを
意味する。但しＩが仮番号の時はその仮番号Ｉを
つけたパターンのラベルがＤ(I)であることを意味
し、また、Ｄ(I)＝０はＩがグリツド点の時はその
グリツド点がまだ見出されていないことを意味
し、Ｉが仮番号の時はその仮番号がまだ使われて
いなことを意味する。第４図の時点ではどのグリ
ツド点Ｉ＝１〜６も見出されていないので第５図
のようにＤ(I)＝０，Ｉ＝１〜６であり、またＩ＝
７に対しては、この分岐したパターンはまだ他の
ラベルとは連結状態になく、自分自身に連結して
いるという意味でＤ(7)＝７とされている。次にさ
らに、検出が進み、第６図のようにはじめてグリ
ツド点１が検出されたとする。この時はグリツド
点１が発見されたがまだ他のラベルをもつたパタ
ーンとは連結関係にはないので、このパターンに
はラベル１を付け、更に連結テーブルＴ上でＤ(1)
＝１とする（第７図）。次に、さらにパターンの
検出が進み第８図のようにグリツド点２が発見さ
れたとする。この場合は点２が発見されたパター
ンのラベルを２としたうえで連結テーブルＴのア
ドレスＡ(2)のデータをＤ(2)＝２とする。この時点
では連結テーブルＴは第９図のようになつてい
る。しかしこの時はグリツド点２が見出されたパ
ターンにはすでに０以外のラベル７が付されてい
るので、これを１つのラベルに統一して１つのパ
ターンには１つのラベル付けが行われるようにす
る。このための一般的方法は、今同一パターンに
上記のように２つのラベルにα，βがついたとす
ると、連結テーブルＴでＤ（α）＝α₁をよみ出しα
＝α₁ならここで止めてα₀＝α₁とする。α≠ならＤ
（α₁）＝α₂をよみ出しα₁＝α₂ならα₀＝α₂とする。
そ
うでなければＤ（α₂）＝α₃をよみ出すという操作を
くり返すと、必ずＤ（αk）＝αkとなるαkがあるこ
とがテーブルＴの作成方法から保証されるので、
αk＝α₀とする。この操作はフローチヤートで第
１０図に示されている。この操作をβについても
実行しβ₀を求め、min（α₀，β₀）をこのパターン
のラベルとし（仮信号がグリツド番号より常に小
の時はmax（α₀，β₀）をとる）、更に連結テーブル
ＴのＤ（α），Ｄ（β）もこの値とする。今の場合
はラベル２，７に対し第９図からわかるようにα₀
＝２，β₀＝７であるからこのパターンにはラベル
２を付け、同時にテーブルＴのＤ(2)，Ｄ(7)も２と
する。この時の連結テーブルＴは第１１図のよう
になる。更にパターン検出が進み第１２図のよう
に、グリツド点３が発見されたとする。この場合
もグリツド点２が発見された場合と同様、分岐し
た右側のパターンにはラベル３がつけられ、かつ
Ｄ(3)＝３が書き込まれるが、このパターンには既
にラベル７が付いていたからラベルの統一化の処
理が行われる。この処理ではα＝３，β＝７であ
りＤ(3)＝３だからα₀＝α＝３となるが、β＝７に
対しては第１１図からＤ(7)＝２であるので続いて
第１０図で説明したようにＤ(2)がしらべられＤ(2)
＝２（第１１図）だからβ₀＝２、従つてα₀，β₀の
小さい方の２がグリツド点３を見出したパターン
にラベルとした付けられ、また連結テーブルＴの
Ｄ(3)も２とされる。この時のテーブルＴは第１３
図に示されている。さらに検出が進み、第１４図
のようにグリツド点４が発見されたとすると、こ
の場合はグリツド点２を発見した第８図の場合と
全く同様な規則で処理が行わわれ、グリツド点４
のあつたパターンのラベル及び連結テーブルＴの
Ｄ(4)の値はともに１とされる。第１５図はこの時
の連結テーブルＴを示している。続いてグリツド
点５，６の発見が第１６図のように行われるが、
この際の処理はグリツド点１の場合と全く同様で
あつて、それぞれのパターンにラベル５，６が付
けられ、かつ連結テーブルＴでＤ(5)＝５，Ｄ(6)＝
６とされる（第１７図）。さらに検出が進み、第
１８図のようにラベル５のパターンとラベル６の
パターンが合流したとしよう。この場合には、１
つのパターンにやはり２つのラベルα＝５，β＝
６が現れるので、第１０図で説明した方法により
α₀＝５，β₀＝６を求め、このうちの小さい方のラ
ベル５がこの合流したパターンにつけられ、また
Ｄ(6)＝５と書きかえられる（第１９図）。以上のようにして第２図のパターンに対して得
られた第１９図の連結テーブルＴは、任意の２つ
のグリツド点Ｉ，Ｊに対してＤ(I)＝Ｄ(J)ならそれ
らのグリツド点は連結ており、そうでなければ連
結してないことを示している。以上では、検出したパターンにラベルを付け
る、更にはそのラベルを書換えるという処理を常
に行つており、説明上はこれを図面上で表してき
たが、ここでこのパターンへのラベル付けの具体
的な方法を述べる。今ある走査時点ｔでリニアセンサ等により検出
した１ライン分の二値画像を第２０図のようであ
つたとする。但しパターンの部分は太線でレベル
１とし、これと検出ラインとの交線（太線）を左
から順にセグメントS₁ ^t，S₂ ^t，S₃ ^tと呼ぶ。更にこ
れらのセグメントの始点の座標をu₁ ^t＜u₂ ^t＜…と
し、終点の座標をv₁ ^t＜v₂ ^t＜…とすると、これら
は容易に検出可能であるから各セグメント対応の
先頭アドレスAPiをもつたラインテーブルLT１
が第２１図のように作れる。更にこのテーブル
LT１のラベルらんには初期値としてはすべて０
（仮想ラベル）をセツトしておき、例えば走査時
にグリツド点（これは予めその座標が外部より入
力され、グリツド点位置テーブルとして与えられ
ているとする）があるセグメントSi^t上に見つか
ればそのセグメントのラベルLi^tに当該グリツド
点の番号Ｎを書込む。むろんこの時は前述したよ
うに常に連結テーブルＴのＤ(N)もＮとする。他の
ラベル付け、書換え等もすべてこのラインテーブ
ルLT１上のラベルらんで行えばよいが、このよ
うなラインテーブルは１走査毎に１つづつ出来る
から、これらをすべて別々に格納しておいたので
はぼう大なメモリ容量になる。そこで本実施例で
は、時点ｔに於て作成れたラインテーブルLT１
と、１時点前のｔ−１に作成されたラインテーブ
ルLT０の２ライン分のメモリだけを用いる。勿
論このラインテーブルLT０も第２１図のテーブ
ルLT１と同様な構成であり、そのセグメント
S₁ ^t-1，S₂ ^t-1，…，始点u₁ ^t-1＜u₂ ^t-1＜…，終点を
v₁ ^t-1＜v₂ ^t-1＜…，ラベルをL₁ ^t-1，L₂ ^t-1…等とす
ると、ラインテーブルLT０，LT１の各セグメン
トSi^t-1とSj^t-1とが同一パターンに含まれるセグ
メントであるための必要十分条件は、両セグメン
トを同一ライン上に書いた時に重る部分があるこ
とであり、これは容易にわかるように vj^t≧ui^t-1かつvi^t-1≧uj^t ……………(1) である。従つてラインテーブルLT０，LT１を参
照し、式(1)を満すセグメントSi^t-1，Sj^tのすべて
の組について、これらは同一パターン上にあると
して第３図〜第１９図で説明ししたような処理を
順次行い、それが終了するとラインテーブルLT
１の内容をラインテーブルLT０にそつくり移し、
次の時点ｔ＋１でのラインの走査へ移り新しくラ
インテーブルLT１の内容を作成して上記のよう
な処理をくり返す。このようにすればパターンへ
のラベル付けの記憶管理は２ライン分のラインテ
ーブルLT０，LT１だけ用意すれば十分で、少な
いメモリ容量で作業ができる。また、グリツド点
間の連結関係を検出するにはグリツド数分のデー
タ領域は必ずしも確保しておかなければならず、
本実施例の連結テーブルＴでもそうなつている
が、更に作業用の仮ラベルに対応する部分、即ち
パターンに分岐が生じている場合での仮ラベルの
データ領域が余分に必要である。これは分岐があ
ればそれなりの数だけ必要だが、全体としては検
出画像上の独立した全パターンにラベルを付ける
従来方法に比べると、グリツド点に着目する本発
明では大幅に少ないメモリ容量でよいことにな
る。なお、もし、分岐のあるパターンの数が不想よ
り多く、仮ラベルのテーブルが足りなくなつた場
合には次のような方法で復旧が可能である。即ち
連結テーブルＴの仮番号のエリアに１ビツトのフ
ラグを設ける。これらのフラグは処理を始める前
の状態においてはすべて０に初期設定されてい
る。これが第４図のような分岐時に１つづつ使わ
れるとその使われた仮番号は、目下使用中である
ことを示すように対応フラグを１としておく。第
２２図はこのようなフラグをもつた連結テーブル
Ｔの例を示しており、仮番号５〜８がすべて使用
済である場合を示している。このような状態でま
た新しい分岐が生じて仮ラベルが必要になると、
まず連結テーブルＴをサーチし、各仮番号Ｊに対
しＪ＝αとして第１０図の処理を実行し、その結
果得られたα₀をＤ(J)の値とする。第２２図のＩ＝
５〜８にこれを実行すると、このＩに対してすべ
てα₀＝５が得られ、連結テーブルＴのデータらん
は第２３図のように書しなおされる。次にこのよ
うにして得た連結テーブルＴの仮番号をもつライ
ンテーブルLT０，LT１のセグメントに対するラ
ベルらんを今書き換えた連結テーブルＴのラベル
に書きなおす。例えばラインテーブルLT０又は
LT１のあるセグメントのラベルが６であつたと
すると、これは第２２図の結果から５に書換えら
れる。次に、このように処理された２つのライン
テーブルLT０，LT１のラベルをサーチし、仮ラ
ベル（ここでは５〜８）を探す。発見された仮ラ
ベル（ここでは５）のフラグには１を立て他のフ
ラグは０とする。この結果が第２３図のフラグの
らんに示されている。以上の処理で使用中の仮ラベルの数が４から１
へ減少し、再びフラグが０の仮ラベルを選ぶこと
によつて新たな仮ラベルの付与が可能になる。以
上の処理は、すでに処理し終つた領域で付与され
た仮ラベルのうち、以降の処理に関係のない仮ラ
ベル（今の例では６〜８）を再使用可能にするこ
とを意味する。さて、本発明による連結関係検出装置について
具体的に説明する。第１図はその一例での全体的
構成を示したものである。これによりその構成と
その動作の概要について説明すれば、画像検出装
置、例えばリニアセンサからのシリアルな二値画
像信号は画像入力部１、切替回路２を介しライン
バツフアメモリ３Ａ，３Ｂに交互に、しかもライ
ン単位に一時記憶されるようになつている。表１
は切替回路２の動作、即ち、ラインバツフアメモ
リ３Ａ，３Ｂの何れに画像入力部からの二値画像
信号が入力され、また、何れより二値画像信号が
読み出されるかをライン位置との関係で示したも
のである。

【表】この表１からも判るようにラインバツフアメモ
リ３Ａ，３Ｂからはまた切替回路２を介し交互に
１ライン前の二値画像信号がシリアルにコード変
換部４に読み出され、その二値画像信号からはラ
イン上におけるセグメントとその始点、終点のア
ドレス（座標位置）が検出されるものとなつてい
る。即ち、コード変換部４では二値画像信号が０
から１へ変化する時点でのアドレスをそのセグメ
ントの始点アドレスとして、また、この後初めて
１から０へ変化する時点でのアドレスを終点アド
レスとしてセグメントとその始点、終点のアドレ
スが検出されているものである。セグメント対応
の始点アドレスおよび終点アドレスは対となつ
て、セグメントが検出される度に一時蓄積用の
FIFO（First In First Out）５に順次書込される
が、FIFO５からは先入先出形式で始点アドレス
および終点アドレスが対としてグリツド番号割付
部６に読み出されるようになつている。グリツド
番号割付部６では始点アドレスおよび終点アドレ
スで規定されるセグメント上にグリツド点が存す
るか否かが検出されるが、グリツド点が存するか
否かはアクセス制御回路９を介する、グリツド点
位置テーブルメモリ１０からのグリツド点位置座
標を参照することによつて検出されるものとなつ
ている。この検出でグリツド点が存する場合はそ
のセグメントにはラベルが付されるが、ラベルは
始点アドレスおよび終点アドレスとともに切替回
路７を介しラインテーブルメモリ８Ａ〜８Ｃの何
れか１つに交互に書き込まれるものである。表２
は切替回路７の動作、即ち、ライン位置によつて
グリツド番号割付部６の出力がラインテーブルメ
モリ８Ａ〜８Ｃの何れに入力され、また、ラベル
付け処理部１４にはラインテーブルメモリ８Ａ〜
８Ｃの何れかからの読出出力が入力されるかを示
したものである。

〔発明の効果〕

以上説明したように本発明による場合は、画像
入力部、コード変換部、グリツド番号割付部、ラ
ベル付け処理部に分割し、これらが並行に動作す
るようにし、これらの間のデータの授受はバツフ
アメモリを介して行なうようになしたものである
から、連結テーブルメモリのメモリ容量少なくし
て処理を高速に行なえるという効果がある。

【図面の簡単な説明】

第１図は、本発明による連結関係検出装置の一
例での全体的構成を示す図、第２図，第３図，第
４図，第５図，第６図，第７図，第８図，第９
図，第１０図，第１１図，第１２図，第１３図，
第１４図，第１５図，第１６図，第１７図，第１
８図，第１９図，第２０図，第２１図，第２２
図，第２３図は、本発明に係る連結関係検出方法
を説明するための図、第２４図は、本発明に係る
グリツド点位置テーブルメモリ上でのグリツド点
位置座標とこれに対するグリツド番号の格納フオ
ーマツトを示す図、第２５図は、FIFOに代わる
ンバツフアメモリおよび切替回路よりなる回路を
示す図、第２６図は、連結テーブルメモリへのア
クセス制御方法を説明するための図、第２７図，
第２８図，第２９図，第３０図は、それぞれ画像
入力部、コード変換部、グリツド点番号割付部、
ラベル付け処理部の一例での構成を示す図、第３
１図，第３２図、第３３図は、これまでの連結関
係検出方法を説明するための図である。１…画像入力部、２，７…切替回路、３Ａ，３
Ｂ…ラインバツフアメモリ、４…コード変換部、
５…FIFO、６…グリツド番号割付部、８Ａ，８
Ｂ，８Ｃ…ラインテーブルメモリ、１０…グリツ
ド点位置テーブルメモリ、１２…連結テーブルメ
モリ、１４…ラベル付け処理部。

Claims

【特許請求の範囲】

１順次シリアルに入力されるライン対応の二値
画像信号各々に含まれる画素に対し書込アドレス
を発生する画像入力部と、該入力部からの二値画
像信号をライン更新の度に交互に一時記憶すると
ともに、前ライン対応の二値画像信号がライン更
新の度に交互に読み出される２面のラインバツフ
アメモリと、該メモリに対する読出アドレスを発
生するとともに、該メモリから読み出された二値
画像信号より０から１、１から０への画素変化ア
ドレスを検出するコード変換部と、上記画像入力
部、ラインバツフアメモリおよびコード変換部の
間に介在され、二値画像信号のラインバツフアメ
モリへの一時記憶、該メモリからの読出を切替制
御する切替回路と、上記コード変換部からの０か
ら１、１から０への画素変化アドレスを対として
一時記憶するFIFOと、外部から指定される複数
の点の位置アドレスが予め記憶されるグリツド点
位置テーブルメモリと、上記FIFOからの対とし
ての画素変化アドレス間に指定された点が存する
か否かを上記グリツド点位置テーブルメモリを参
照して検出し、対としての画素変化アドレスにラ
ベルを所定に付すグリツド番号割付部と、該割付
部からの対としての画素変化アドレスと該アドレ
スに付されたラベルを交互に一時記憶するととも
に、前ラインおよび前々ライン対応の対としての
画素変化アドレスと該アドレスに付されたラベル
が交互に読み出される３面のラインテーブルメモ
リと、該メモリからの対としての画素変化アドレ
スにもとづき隣接ライン上での連結関係を検出し
たうえラベルを所定に変更するラベル付け処理部
と、上記グリツド番号割付部、ラインテーブルメ
モリおよびラベル付け処理部の間に介在され、対
としての画素変化アドレスと該アドレスに付され
たラベルのラインテーブルメモリへの一時記憶、
該メモリからの読出を切替制御する切替回路と、
上記複数の点対応のラベルが上記グリツド番号割
付部およびラベル付け処理部によつて更新可とし
て記憶される連結テーブルメモリとからなる構成
を特徴とする連結関係検出装置。