JPS63316186A

JPS63316186A - 画像デ−タのラベリング方式

Info

Publication number: JPS63316186A
Application number: JP62150298A
Authority: JP
Inventors: Masahiko Sato; 雅彦佐藤; Tsugito Maruyama; 次人丸山
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1987-06-18
Filing date: 1987-06-18
Publication date: 1988-12-23

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔概　要〕画像中の連続した画素による同一領域を検出して同一ラ
ベルを付す画像データのラベリング方式であって、高速
にラベル付けし得るように、入力された２値画像データ
について初期ラベル付けをした後、該ラベル付けされた
データについて特有の接続関係マスクを適用して接続関
係を検出し、接続関係が検出された場合ラベルの更新を
行ない、上記接続関係検出およびラベル更新を新たな接
続関係が検出されなくなるまで反復して行なわせるよう
にしたものである。特に、接続関係検出およびラベル更
新を画像処理装置のビデオレートで行なわせるようにし
たものである。

〔産業上の利用分野〕

本発明は画像データのラベリング方式に関するものであ
り、さらに詳しく述べると、画像処理装置等とのオンラ
インリアルタイム動作が可能な画像データの高速ラベリ
ング方式に関する。

本発明の画像のラベリング方式は、例えばＩＣパターン
を走査した画像データに基いて自動的にＩＣパターン検
査を行う場合、又は磁気ディスク面を走査した画像デー
タに基いて自動的に磁気ディスク面の塗り漏れの検出を
行う場合等、画像データ処理の一部に用いられる。

〔従来の技術、および発明が解決しようとする問題点〕

画像データのラベリングとは、画像平面に分布した画像
データの固まり或いは連続性を検出して、それら画像パ
ターンの固まり毎に番号付け（ラベリング）を行うもの
である。このようにラベリングされたデータを用いるこ
とにより、原画像データの固まりをパターン（ラベリン
グ）化し画像データの検査等を有効かつ迅速に行うこと
が可能となる。

従来のラベリング方式としては、「繰り返し」型ラベリ
ング方式と「クラスタリング」型ラベリング方式とが知
られている。

繰り返し型ラベリング方式を第１４図（ａ）〜（ｄ）を
参照して述べる。先ず第１４図（ａ）に図示の如く、２
値化され２次元マトリクス状に画素に対応してメモリ内
に配設されたデータ（データがある部分を＊で示す）に
ついて六方向について走査を行ない初期ラベリングを行
う。このラベリングについて述べると、１行目の最初の
＊をまずラベル“ｌ”とし、同じ行の離れた第２番目の
＊について“２”とする。次の２行目の＊は走査方向に
おいて連続性がないので“３”とする。その次の列のデ
ータは上記１行目の同じ列“ｌ”とラベル付けされたも
のと連続性があるので“ｌ”とされる。同じ行の第３〜
５行目のデータはそれぞれ“１”にラベル付けされたも
のと連続しているので同じく“ｌ”とラベル付けされる
。以下同様に行うことにより、第１４図（ｂ）に図示の
初期ラベル付け結果が得られる。

次いで第１４図（ａ）のＡ方向とは９０’ずれたＢ方向
について、進行方向に対して隣接し、すでに処理された
ものに対して連続性をチェックすると共に、第１４図（
ｂ）に得られた初期ラベル付け結果について更新を行う
。例えば、右側から２列目第４行目のラベル付け“６”
に該当するものは、先行する右側１列目、第４行目のラ
ベル付け“４”と連続するので、少ないラベル番号の“
４”に更新される。同じ右側から２列目、第５行目のラ
ベル“６”は上の行が“４”にラベル更新されたものと
連続するので“４”に更新される。

他のラベル“５”、“３”も同様にしてそれぞれ“１”
にラベル更新される。その結果が第１４図（ｃ）に示さ
れる。このラベル更新において、ラベルは大きい番号か
ら小さい番号にのみ更新されるようにしている。

更に第１４図（ａ）のＣ方向について連続性チェックを
行うと第１４図（ｄ）の如くラベル更新され、同様にＤ
方向についても第１４図（ｅ）の如くラベル更新される
。これにより、第１４図（ａ）のパターンは“１”と４
″の２つのパターンにラベル付けされることになる。

以上の如く、繰り返し型ラベリングは、第１４図（ａ）
の画像データ配列について順次９０’ずつ方向を変えて
い（のであるが、このように方向を変えるに伴って、画
像メモリへのアクセスするアドレスを複雑な計算により
生成しなければならず、注目画素およびそれに隣接する
画素のアドレス発生回路が非常に複雑になるという問題
を有している。

次にクラスタリング型ラベリングについて述べる。第１
５図に図示の如（、初期ラベル付けおよび接続関係検出
部９１において、入力画像データに対し、初期ラベル付
けおよびラベルの接続関係の検出を同時に行う。次に接
続関係整理部９２において重複しているラベルの接続関
係を整理する。

クラスタリング部９３では整理された接続関係に基づい
て初期ラベルの分類を行い、各領域に属するすべての初
期ラベルを検出する。最後にラベル更新部９４において
はクラスタリングの結果に基づいて初期ラベルの更新を
行う。このクラスタリング型ラベリングにおいては、接
続関係整理部９２、クラスタリング部９３の処理をソフ
トウェア的に処理すると非常に時間がか＼す、リアルタ
イム化が実現できない。一方ハードウエアで実現する場
合には多くのメモリを必要とし、また複雑な処理に伴っ
て回路構成が複雑となり、規模が大きくなる等の欠点が
ある。

画像処理上、上記ラベリングは画像処理装置のビデオレ
ートに同期して実時間（リアルタイム）で行なわれるこ
とが好ましいのであるが、上記いずれ鼻の場合において
も、時間がか＼る上、処理が複雑になっており、ビデオ
レートに追従して処理できないという問題に遭遇してい
る。

そこで、ビデオレートで迅速にリアルタイム動作可能か
つ回路構成が簡単な画像データのラベリング方式が要望
されている。

〔問題点を解決するための手段〕

本発明の画像データのラベリング方式は原理ブロック図
を第１図に示すように、２次元マトリクス状に配設され
た画素に対応して入力される入力画像データＳＩＮに対
し１つのデータ処理方向においてすでにラベリングされ
た隣接画像データとの連続性を検出するための初期ラベ
ル付けマスク１００を用いて初期的なラベル付けを行う
初期ラベル付け手段１、該ラベル、付けされたデータに
ついて注目画素を基準としてその隣接する画素に対して
回転対称性を有する接続関係マスク２００を用いて接続
関係を検出する手段２、および、該接続関係検出手段で
検出された接続関係についてラベル付けデータのラベル
更新を行うラベル更新手段３から成る。

〔作　用〕

入力２値画像に対し、初期ラベル付け手段１が初期ラベ
ル付けマスク１００を用いてラベル付けを行う。接続関
係検出手段２が接続関係検出マスク２００を使用し、異
なったラベルの接続を調べ、この情報を接続テーブルに
格納する。この情報によりラベル更新手段３がラベルの
更新を行う。このときの接続関係検出時におけるラベル
変換ルールは注目画素のラベルの値が回転対称関係にあ
る４つの近傍画素のラベルの最大値よりも小さい場合は
、注目画素のラベルを、その最大のラベルへ置き換える
。接続の検出が無（なるまで接続関係検出手段３および
これに連動してラベル更新手段３が反復して動作する。

本発明は、上述のマスクを用いると共にこのようにラベ
リングの処理を、分類、接続関係検出、ラベル更新と区
分けして単純化し、接続関係検出とラベル更新をくり返
すようにしている。

接続関係検出とラベル更新はビデオレートに同期して反
復され得る。

〔実施例〕

先ず、コンピュータを用いた実施例について述べる。第
２図の本発明の実施例の画像データのラベリング方式は
、コンピュータ内のプログラム記憶部（図示せず）およ
びＣＰＵ　（図示せず）により、初期ラベル付け部１ａ
、接続関係検出部２ａ、ラベル更新部３ａおよび処理終
了判定部３ａにより実現される。

ラベル付け対象となる画像データは、第３図に図示の如
く、画素対応にマトリクス状に配設されており、Ｉ）＋
＋　、　０１２　、・・・、　ＤＩ１２５６　　＋　Ｄ
２＋　＋・・・。

Ｄ２５６１１１・・・＋　Ｄ　ＺＳ６＋　ｚｓｂＯ順で
画像メモリ５から入力データＳＩＮと読み出されるもの
とする。初期ラベル付マスク１００は、第４図に図示の
如く、注目画像Ｘ、例えば第３図のデータＤ２□に対し
、第３図において左から右、上から下へとデータ処理さ
れる方向において、隣接するすでに初期ラベル付けされ
た画素Ａ、Ｂ、Ｃ，Ｄにおける画像データＤｔ＋　＋　
Ｄｌｌ　＋　Ｄｌｚ　＋　Ｄｌｌに対して接続関係を検
出するものである。

先ず初期ラベル付動作について述べる。

初期ラベル付け部１ａにおいては入力２値画像データＳ
ＩＨに対し、初期ラベル付マスク１００を第３図の画面
左上から右下へラスター走査し、第５図に図示の論理表
に基づき、初期ラベルを付与する。第４図の初期ラベル
付マスク１００の動作は、注目画素Ｘの画素が“０”の
場合は何もせず（第５図優先２）、注目画素のみ“１”
で他は“Ｏ”の場合は、その画素にラベルＬ（初期値ｌ
）を付与し、第６図に図示の如く接続テーブルｌｌａへ
、ラベルＬをアドレスとして格納する。次にラベルＬを
＋１更新する。（第５図優先２）。次に注目画素Ｘにデ
ータがある場合、近傍画素についてＡ−Ｂ→Ｃ−４Ｄの
順で調べた時、その中にラベルがあれば、注目画素Ｘに
最初に検出されたラベルを付与する（第５図優先３）。

以下同様に行う。

初期ラベルはマスク１００を第７図（ａ）の入力２値画
像に対し適用して初期ラベリングをさせた結果がラベル
付画面用メモリｌｌｂに第７図（ｂ）に図示の如く記憶
され、作成された接続テーブル１１ａの内容を第７図（
ｃ）に示す。

次に接続関係検出およびラベル更新の動作について述べ
る。

接続関係検出部２ａにおいては、第７図（ｂ）に図示の
初期ラベル付けされたデータメモリｌｌｂの内容に第８
図に図示の接続関係検出マスク２００を適用する事によ
り、各ラベルの接続関係を検出する。接続関係検出マス
ク２００は注目画素Ｘに対し回転対象位置の隣接画素Ｃ
，Ｄ、Ｈ，Ｇについて接続関係をヰ★出するのに用いる
ものである。このマスクの形状は、注目画素についてそ
の隣接画素との接続関係を検出するに際して、種々の接
続関係を検出する場合について検討し、ラベリングに矛
盾が生ぜず、しかも短時間でラベリングが可能な点から
定めたものである。ラベリングの矛盾とは、ある注目画
素によるラベリングと他の隣接する画素を注目画素を基
準としてラベリングした場合、異なるラベリングされ、
収束しないような場合をいう。接続関係検出マスク２０
０は、回転対象画素について接続関係を検出し、か＼る
ラベリングの矛盾を防止している。

接続関係検出マスク２００を通用した接続関係検出の動
作は、第９図に示すように、注目画素Ｘ又は近傍画素Ｃ
，Ｄ、Ｇ、Ｈが無い場合は何もしない（第９図、優先１
．２）。次に注目画素Ｘにラベルがあり、近傍画素Ｃ，
Ｄ、Ｇ、Ｈのラベルの最大の大きさのラベルよりも注目
画素Ｘのラベルが小さい場合、接続テーブルｌｌａの注
目画素Ｘにその最大のラベルを書き込む（Ｃ、Ｄ　、　
Ｈ、Ｇのラベルの最小のラベルより、Ｘのラベルが大き
い場合としてもよい）。この接続テーブルｌｌａは、ラ
ベルをその内容へ置き替える情報を表わすものである。

また、この時にラベルの接続が検出された事を示すフラ
グＦＬＡＧを設定する。以上の接続関係ネ食出処理を第
７図（ｂ）に図示の如き内容の画面メモリｌｌｂに対し
て行ない、これにより書き替えられた接続テーブルｌｌ
ａの内容を第７図（ｅ）に示す。次に、処理終了判定部
４においては、接続関係検出部２ａにおいて、ラベルの
接続が検出された事を示すフラグＦＬＡＧを調べ、それ
が設定されていなければ、ラベル付け処理が完了したも
のとして終了する。設定されていれば（１）次のラベル
の更新を行う。

ラベル更新３ａにおいては、第７図（ｅ）の接続テーブ
ルｌｌａに基づき、ラベル付けされた画面メモ１月１ａ
のラベルを書き替える。これは、第７図（ｅ）に図示の
如く画面メモリｌｌｂの内容を１画素づつ左上より走査
し、画素にラベルがあればそのラベルＬを接続テーブル
の内容に書き替える。

次にふたたび接続関係検出処理を行う。この処理を画面
メモリｌｌｂの内容に対して行った結果を第７図（ｄ）
に示す。また、第７図（ｄ）のラベルに対し、接続関係
検出処理を行うと接続関係は検出されず、フラグも設定
されない。よって、これにより原画像データをラベルに
て分離する事ができる。

以上の如くラベリング処理の内容を分離し、各処理を単
純化、特に接続関係検出処理とラベル更新を分離すると
共に反復処理可能とすること、および適切に規定された
接続関係マスク２００を用い接続関係検出の無矛盾およ
び効率化を図ることにより、接続関係検出処理とラベル
更新は、画像処理装置のビデオレートに同期して動作可
能となる。

また全体の処理速度も向上する。

次にハードウェアを用いて実現した実施例について述べ
る。

第１図の初期ラベル付手段１の実施例としての初期ラベ
ル付回路ｌＯを第１０図に示す。

第１０図の初期ラベル付回路１０は、入力画像データＳ
０を入力する８ビツトフリツプフロツプ（Ｆ　Ｆ）回路
１１、シフトバッファ１２、それぞれ８ビツトのＦＦ回
路１３　、１４、ＲＱ？＋　１５、カウンタ１６．８ビ
ツトＦＦ回路１７、マルチプレクサ１８および８ピッ１
−ＦＦ回路１９が図示の如く接続されて成る。入力画像
データＳＩＮは前述同様第３図に図示の如く、２次元マ
トリクス状に画像メモリ　（図示せず）に記憶されてお
り順次、データＤ　ＩＩ　＋　Ｄ　ＩＩ　＋・・・＋　
Ｄ　ＩＩ　２５６　　＋　Ｄ　２＋　ｌ　　＋・・・の
如く読み出される。入力画像データＳＩＮは８ビツトで
′濃淡画像処理、しきい値処理を適用し、“０”又は“
２５５′の２値画像データにされている。この実施例に
おいては、「２の補数」表現を用いており、“０”の場
合が“１ｏｏｏｏｏｏｏ”、“２５５”の場合が“０１
１１１１１１”の２進数で表現されている。

第４図に初期ラベル付マスクを示す。このマスクは上述
の実施例におけるものと同様であり、第３図の配列に対
応させて考えた場合、注目画素Ｘに対し、すでにラベル
付けされた隣接する上の行の画素Ｂ、Ｃ，Ｄと同じ行の
すでにラベル付けされた隣接する画素Ａについて初期ラ
ベル付けをするに当ってその連続性をチェックするため
のものである。

ＦＦ回路１１、シフトバッファ１２、ＦＦ回路１３　、
１４は、第３図の図示の画像データが順次読み出された
場合、注目画素Ｘに対し第４図の図示の隣接画素Ａ、Ｂ
、Ｃ，ＤのデータがＲＯＭ　１５に印加されるように接
続されている。ＲＯＭ　１５はその人力ＸＳ、ＡＳ〜Ｂ
Ｓにデータが印加された場合、第１１図に図示の論理で
出力５ｏ−３２を出力するようにプログラム化されてい
る。第１１図において、＊は、注目画素Ｘのデータ７丁
が“０”のときは、初期ラベル付マスクは行なわず、隣
接データは無関係であることを示す。他の場合において
も、＊がつけられ、隣接データは無関係な場合がある。

マルチプレクサ１８には注目画素Ｘ、ラベル付けされた
その隣接画素Ａ−Ｄ、および、カウンタ１６およびＦＦ
回路１７を介して新しいラベルＬが印加されており、Ｒ
ＯＭ　１５の出力５Ｏ−３２の組合せにより、第１１図
に図示の表に従って、これら人力のうちの１つを注目画
素Ｘに対してラベル付けしだ値ＸとしてＦＦ回路１９に
選択出力する。

このラベル付け値Ｘはシフトバッファ１２に記憶され、
関連する隣接ラベルとして用いられる。

ここでＲＯＭ　１５のアドレスとして、画素Ｘ、Ａ。

Ｂ、Ｃ，Ｄのデータの最上位ビットを割り合でるものと
する。また、ＤＡ　、Ｄ＠　、Ｄｃ　　、Ｄｏは既に初
期ラベル付けされたラベルデータである。ＤＡはＸを次
のクロックでラッチしたデータ、ＤＤはＮ−２クロツク
遅延させたデータ、Ｄｃは（Ｎ−１）クロック遅延させ
たデータ、Ｄ、はＮクロック遅延させたデータである。

Ｌは新しいラベルであり、ＦＦ回路１７とカウンタ１６
により生成し初期値は“０”とする。このカウンタ１６
のクロックＣＫとしてはＲＯＭ　１５からの出力データ
を用いる。

以上から初期ラベル付の演算は、前述の第５図の演算論
理表に示されるものと同様となる。このようにしてラベ
ル付けされたデータは前述のラベル付け画面メモリｌｌ
ｂと同等のメモリに記録される。

次に接続関係検出手段２の実施例の接続関係検出回路２
０を第１２図に示す。接続関係検出回路２０は、ＦＦ回
路２１〜３３、ラインバッファ４１　、４２、比較回路
５１〜５４、マルチプレクサ６１〜６４、ＲＡＭ　７１
が図示の如く接続されている。接続関係検出マスク２０
０は前述の第８図に図のものと同様である。

第１２図におけるＦＦ回路２１〜２３、ラインバッファ
４１、ＦＦ回路２４　、２５、およびラインバッファ４
２、ＦＦ回路２６　、２７は、第８図の接続関係マスク
２００に対応して注目画素のデータＸがＦＦ回路２５か
ら出力され、隣接する画素Ｇ、Ｈ，Ｄ、ＣがそれぞれＦ
Ｆ回路２２　、２３　、２６　、２７から出力されるよ
うに接続されている。

このようにして取り出されたデータＤ、、Ｄ。

およびり、、Ｄ、を比較器５１　、５２でそれぞれ比較
し、マルチプレクサ６１　、６２のセレクト（ＳＥＬ）
信号とし、大きい方のデータを選び出し、おのおのＣＤ
　、ＧＨとする。次にこのＣＤ　、ＧＨを比較器５３で
比較し、大きい値のデータを選択し、これを最大値ＭＡ
Ｘとする。最後にこの最大値ＭＡＸと注目画素にあたる
Ｘとを比較器５４で比較し、大きい値をＤｙとしてマル
チプレクサ６４から出力する。このときＭＡＸ＞Ｄ、の
場合は、比較器５４のセレクト信号により、ＦＦ回路３
１がラッチされ、接続関係検出フラグＦＬＡＧを設車す
る。

このフラグはＦＦ回路３３において１フレームの間保持
される。接続テーブルであるＲＡＭ　７１へは、ＤＸの
ラベルデータをＲＡＭ　７１のアドレス（ＡＤＲ）　と
し、マルチプレクサ６４よりの出力データＤｙを書き込
む。

上記処理は前述の実施例と同様、接続テーブルの内容が
第７図（Ｃ）に示される。

ラベル更新手段３の実施例としてのラベル更新回路３を
第１３図に示す。この回路は前記の処理の結果、生成さ
れた接続テーブルメモリ７１によりラベル付け画面メモ
１月１ｂのラベルの書き替えを行う。入力されたラベル
データをＲＡＭ　７１のアドレスとして、ＲＡＭ　７１
からデータを読み出す。これを読み出したラベル付け画
面メモリｌｌｂの位置へ書き込むことによりラベルの更
新を行う。

上記の接続関係検出処理およびラベルの更新は、新たな
接続関係が検出されなくなるまで反復して行なわれる。

また、この反復動作は画像処理装置のビデオレートで行
う。

〔発明の効果〕

以上に述べたように本発明によれば、２値画像データの
ラベリングを効率よく高速で行うことができる。

また本発明によれば画像処理装置のビデオレートに同期
して処理することができ、画像処理装置とリアルタイム
動作可能となる。

【図面の簡単な説明】

第１図は本発明の画像データのラベリング方式の原理ブ
ロック図、第２図は本発明の実施例の画像データのラベリング方式
の構成図、第３図は本発明の実施例の画像データ配列図、第４図は
本発明の初期ラベル付マスクの説明図、第５図は本発明
のラベル付演算論理を示す図、第６図は本発明の実施例
の接続テーブル図、第７図（ａ）〜（ｅ）は本発明の実
施例の動作を示す図、第８図は本発明の接続関係検出マスクの説明図、第９図
は本発明の実施例の接続関係の事理を説明する図、第１０図は本発明の実施例の初期ラベル付回路図、第１１図は第１０回期期ラベル付回路の動作説明図、第１２図は本発明の実施例の接続関係検出回路図、第１３図は本発明の実施例のラベル更新回路図、第１４
図は従来の繰り返し型ラベリングを説明する図、第１５図は従来のクラスタ型ラベリングを説明する図、
である。（符号の説明）１・・・初期ラベル付手段、２・・・接続関係検出手段
、３・・・ラベル更新手段、　　１ａ・・・初期ラベル
付部、２ａ・・・接続関係検出部、３ａ・・・ラベル更
新部、４・・・終了処理判定部、　５・・・画像メモリ
、１１ａ・・・接続テーブル、１１ｂ・・・ラベル付画面メモリ、１００・・・初期ラベル付マスク、２００・・・接続関係検出マスク。

Claims

【特許請求の範囲】１、２次元マトリクス状に配設され得る画素における２
値画像データ（Ｓ＿Ｉ＿Ｎ）について、注目画素を基準
としてその隣接する画像データの接続をデータ処理方向
に沿って検出するよう規定された初期ラベル付けマスク
（１００）を適用し、データ処理方向に沿って、つなが
りのある画像データを同じラベル付けする初期ラベル付
け手段（１）、ラベル付けされたデータについて、注目
画素を基準としてその隣接する画素のうち回転対称関係
にあるものに対して接続関係を検出するように規定され
た接続関係マスク（２００）を適用し、１つのデータ処
理方向に沿って前記２値画像データの２次元状接続関係
を検出する手段（２）、および、該接続関係検出手段に
より新たな接続関係が見出された場合前記ラベル付けデ
ータのラベルを更新する手段（３）を具備し、新たな接続関係が見出されなくなるまで、前
記接続関係検出手段および前記ラベル更新手段を反復動
作させることを特徴とする、画像データのラベリング方
式。２、前記接続関係検出手段および前記ラベル更新手段が
前記画像データを処理するビデオ装置のビデオレートで
動作することを特徴とする、特許請求の範囲第１項に記
載の画像データのラベリング方式。３、前記接続関係検出マスク（２００）が、注目画素（
Ｘ）、該注目画素の１行前画素（Ｃ）、該画素の次列の
画素（Ｄ）、注目画素の次の行画素（Ｇ）および該画素
の１列前画素（Ｈ）のデータの接続関係を検出するよう
規定されたことを特徴とする、特許請求の範囲第１項又
は第２項に記載の画像データのラベリング方式。