JPS6326784A

JPS6326784A - 画像連結処理装置

Info

Publication number: JPS6326784A
Application number: JP61171083A
Authority: JP
Inventors: Masato Suda; 正人須田
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1986-07-21
Filing date: 1986-07-21
Publication date: 1988-02-04

Abstract

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

Description

【発明の詳細な説明】［発明の目的］（産業上の利用分野）この発明は、二値画像の連結成分を検出する画像連結処
理装置に関する。

〈従来の技術）文字認識における文字の切出しや画像計測の分野におい
て、従来よりラベリング回路が用いられている。このラ
ベリング回路は、画像データから連結成分を抽出し、連
結成分毎に一つのラベル番号を付与するもので、例えば
第８図に示すように構成されている。

即ち、ラインバッファ１には二値化された１ライン前の
画像データ（“１”、”Ｏ”）とこれに対応する各画素
のラベルが格納される。そして、着目画素Ｐの画像デー
タをフリップフロップ回路２（Ｐ）に格納し、この着目
画素Ｐに対して左上、上及び左に隣接する各隣接画素Ａ
、Ｂ、Ｃの画像データとラベル番号とをラッチ回路３，
４．５に格納する。これらフリップフロップ回路２及び
ラッチ回路３〜５に画像データが格納されると、これら
４ピツトの画像データによって着目画素と隣接画素との
連結の有無及びその連結する画素の位置が分るので、こ
れをＲＯＭ　６のアドレスとじて与える。ＲＯＭ６は、
着目画素Ｐが隣）妾画素Ａ。

Ｂ、Ｃのいずれか一つと連結している場合には、連結し
ている隣接画素のラベル番号をマルチプレクサ７を介し
て選択する。また、もし、連結画素がない場合には、新
たに付与するラベル番号が格納されている白ラベルカウ
ンタ８又は黒ラベルカウンタ９の値を選択する。この結
果、連結成分に同一のラベル番号が付与され、連結処理
部１ｏに入力される。連結処理部１ｏでは、ラベル番号
の連結を並列又はバイブライン処理することによって処
理の高速化が図られている。

しかしながら、上述した従来の画像連結処理装置にあっ
ては、ラベル番号を選択するマルチプレクサ７の使用Ｉ
Ｃの数をラベル番号のビット数分だけ必要とする。この
ため、対象画面中に非常に数多くの連結成分が存在する
場合には、極めて多くのＩＣを用いるマルチプレクサを
必要とした。

また、連結処理部において並列処理、パイプライン処理
を行なうためにも、多くのレジスタを必要とした。この
ため、従来の画像処理装置にあっては対中とする画面の
画素数の増加に伴って回路規模が増大するという欠点が
あった。

（発明が解決しようとする問題点）このように、従来の画像連結処理装置にあっては、特に
連結成分の多い画像の処理を行なう場合、回路規模の増
大が避けられず、装置の小形１ヒ、低価格化を損うとい
う問題があった。

この発明は、このような問題を解決すべくなされたもの
で、回路規模の縮小が図れ、装置の小形化、低価格化に
寄与し得る画像連結処理装置を提供することを目的とす
る。

［発明の構成〕（問題点を解決するための手段）本発明は、以下のように構成された画像連結処理装置に
おいて、特に選択手段の構成に特徴がある。

即ち、本発明に係る画像連結処理装置には、まず第１乃
至第３の保持手段が備えられている。第１の保持手段は
着目画素の二値画像データを保持する。第２の保持手段
は上記着目画素に隣接する近傍画素の二圃画像データ及
びそのラベル番号を保持する。第３の保持手段は新たに
付与するラベル番号を保持する。そして、前記第１及び
第２の保持手段で保持された二値画像データを元に前記
着目画素と近傍画素との連結を連結検出手段で検出し、
該連結検出手段の検出結果に基づいて前記第２及び第３
の保持手段から着目画素に付与するラベル番号を選択手
段で選択するようにした画像連結処理装置における上記
選択手段が、前記第２及び第３の保持手段の出力を入力
とするワイヤードオア回路で構成され、前記連結検出手
段の検出結果に基づき前記第２及び第３の保持手段から
のラベル番号出力を択一的に入力するものである。

（作用）。

第２及び第３の保持手段に保持されたラベル番号は、連
結検出手段からのデータに基づき、あるタイミングでワ
イヤードオア回路に択一的に入力される。したがって、
ワイヤードオア回路の出力を、そのまま選択されたラベ
ル番号として以後使用することができる。この場合、連
結成分が非常に多くても回路規模が増加することは殆ど
ない。

（実施例）以下、本発明の一実施例について説明する。

第１図は本発明の一実施例に係る画像処理装置の構成を
示す図である。

このｉ置は、画素連結の有無、その方向などを検出する
連結成分抽出部２１と、検出された連結成分のラベルを
統合・整理する連結処理部２２とに大別される。

連結成分抽出部Ｌ１は次のように構成される。

即ち、制御回路３０は、この装置の処理タイミングを指
示する回路で、第２図に示すようなＰ１〜Ｐ４　、Ｗ１
〜Ｗ４の４サイクルの時分割パルスを出力する。

ラインバッファ３１は、−走査前の二値画像データ（゛
０パ、“１°′のデータ）と、各画像データのラベル番
号とを対にして格納するもので、アンド回路３２を介し
て読出しのイネーブル状態が設定される。尚、ここでは
、黒画素に対してラベル番号を付加するものとし、白画
素についてはラベル番号が付与されないものとする。

着目画素Ｐの二値化面（象データは、第１の保持手段で
あるフリップフロップ（以下ｒＦＦｊと呼ぶ）３３に格
納される。この着目画素Ｐの左上、上及び左に隣接する
各隣接画素Ａ、Ｂ、Ｃの二値画像データ及びラベル番号
は、第２の保持手段であるラッチ回路３４．３５．３６
にそれぞれ保持される。ＦＦ３３及びラッチ回路３４．
３５は、Ｗｌのタイミングで保持され、ラッチ回路３６
はこれよりも前のＷ４の時点で保持される。

これらＦＦ３３．ラッチ回路３４，３５．３６に保持さ
れた計４ビットの二値画像データは、連結検出手段であ
るＲＯＭ３７の下位アドレスＡＯ〜Ａ３として与えられ
ている。また、このＲＯＭ３７の上位アへレスＡ４−八
〇には、Ｐ２〜Ｐ４の時分割パルスが与えられている。

したがって、ＲＯＭ３７には、Ｐ２〜Ｐ４にかけて異な
るアドレスが与えられ、これに応じて異なるデータＤＯ
〜Ｄ８を出力する。このデータＤＯ〜Ｄ８は、後述する
各カウンタのカウントパルス、ゲートのイネーブルパル
ス、メモリのライトパルスなどに使用される。

ＲＯＭ３７のｏｏ　、ｏｉ端子には、第３の保持手段で
ある黒ラベルカウンタ（以下、ｒＮＮＨＪと呼ぶ）３８
および白ラベルカウンタ（以下、ｒＮＮＬＪと呼ぶ）３
つが接続されている。　ＮＮＨ３８には次のようなラベ
ル番号が保持されている。即ち、着目画素が黒で隣接画
素が全て白の場合、着目画素Ｐには連結成分の始点を示
すものとして新たなラベル番号を付与する必要があるが
、上記ＮＮＨ３８には、この新たに付与すべきラベル番
号が格納されている。一方、ＮＮＬ３９には、白画素の
新たなラベル番号が格納されるが、この黒画素のみにラ
ベル番号を付与する場合には使用しない。

これらＮＮＨ３８，ＮＮＬ３９は、ＲＯＭ３７のデータ
Ｄｏ、Ｄ＋の変化によってカウント動作を行ない、その
出力は通常はハイインピーダンス状態で、データＤ７．
Ｄ８の“′０″出力によってイネーブル状態となりラベ
ルバス４１に出力される。また、３つのラッチ回路３４
〜３６からの出力は、３ステートゲート４２，４３．４
４を各別に介して上記ラベルバス４１に与えられている
。

これら３つのゲート４２〜４４も、その出力は通常はハ
イインピーダンス状態であり、ＲＯＭ３７の０２　、Ｄ
３　、Ｄ４出力がｏ　”になるとイネーブル状態となる
。つまり、これらＮＮＨ３８゜ＮＮＬ３９及びゲート４
２〜４４は、ラベルバス４１に対してワイヤードオア接
続されており、このワイヤードオア接続と上記イネーブ
ルパルスとによってラベルの選択手段が構成されている
。このラベルバス４１へ出力されるラベル番号は、Ｗ４
のタイミングでラインバッファ３１、ラッチ回路３６及
び連結処理部２２の連結テーブルに入力される。

連結処理部２２は、制御カウンタ５１と、２つのメモリ
５２．５３と、連結ラベル統合部５４と、連結テーブル
５５とで構成されている。

２つのメモリ５２．５３は、着目画素Ｐに隣接画素Ｃ，
Ｂが連結されていて、かつ隣Ｉｇ：画素Ｂ。

Ｃのラベル番号が異なる場合、着目画素Ｐにいずれのラ
ベル番号を付与すべきかを決定するため、−次的に両隣
多画素Ｂ、Ｃのラベル番号を保持しておくもので、例え
ば隣接画素Ｃのラベル番号が第１のメモリ５２に格納さ
れ、隣接画素Ｂのラベル番号が第２のメモリ５３に格納
される。　　゛連結ラベル統合部５４は、これら２つの
メモリ５２．５３に格納された同一アドレスの異なるラ
ベル番号を統合し連結テーブル５５に格納するものであ
る。なお、制御カウンタ５１は、これらメモリ５２．５
３及び連結ラベル統合部５４のアドレスを制御するカウ
ンタである。

以上のように構成された画像連結装置において、着目画
素Ｐとその隣接画素Ａ、Ｂ、Ｃが第３図のｄ１〜ｄ１６
の各場合、着目画素Ｐに次のようなラベル番号が付与さ
れる。

即ち、先ず、ｄｉ　、ｄ２．ｄ３．ｄ５．ｄ６゜ｄ１２
．ｄ１３及び（ｊ１５のケースは、着目画素が”０°′
（白）であるから、ラベル番号は付与されない。

ｄｉ、ｄ１４のケースは、着目画素Ｐは隣接画素Ｂ、Ｃ
が白であるから、連結成分の始点とされる。

なお、ｄ１４では隣接画素Ａとはいわゆる「４連拮」で
あるため、この場合には離れていると見なされる。この
ため、着目画素ＰにはＮＮＨ３８に保持された新たなラ
ベル番号が付与される。

ｄ７　、　ｄｌｏ、　ｄｉ６の場合には、着目画素Ｐが
隣接画素Ｃと連結しているので、ラッチ回路３６内のラ
ベル番号が付与される。

Ｃ１８，ｄｌｌの場合には、着目画素Ｐが隣接画素Ｂと
連結されているので、ラッチ回路３５に保持されたラベ
ル番号が付与される。

ｄ９の場合には、着目画素Ｐが隣接画素Ｂと隣接画素Ｃ
とに連結されており、しかもこれら隣接画素Ｂ、Ｃのラ
ベル番号が異なる場合が考えられる。したがって、この
場合には、隣接画素Ｃのラベル番号を仮に付与しておく
とともに、前述したようにメモリ５２．５３にそれぞれ
隣接画素Ｃ１Ｂのラベル番号を保持し、後の統合処理に
供する。

第４図は二値画像データの一例を示す図である。

このような画像が入力された場合、ラスタスキャンによ
って暫く第３図ｄ１５のパターンを検出し、第４図（ａ
）の０１の時点においてｄｉのパターンを検出する。こ
の時点ではラッチ回路３６には既に′Ｏ″の二値画像デ
ータ及びラベル番号が格納されている。Ｐｌのパルスで
ラインバッファ３１は読出しイネーブル状態となり、Ｗ
ｌのパルスで着目画素Ｐの二値画像データがＦＦ３３に
格納され、隣接画素Ａ、Ｂの二値画像データ及びラベル
番号がラッチ回路３４．３５に格納される。

Ｐ２パルスがＲＯＭ３７に入力されると、ＲＯＭ３７の
アドレスは、第５図の第１段に示すように（０１１００
１０）となる。その時、ＲＯＭ３７のデータは、開開に
示すように＜　１１１１１１１００　）となる。

Ｐ３パルスがＲＯＭ３７に入力されると、ＲＯＭ３７の
アドレスは、同図の第２段に示すように（１０１００１
０）となる。その時、ＲＯＭ３７のデータは、同道に示
すように（１１１１１１１０１）となる。

この結果、データの再下位ビットＯＯが“′１″゛に立
上がるので、ＮＮＨ３８がカウントアツプする。

Ｐ４パルスがＲＯＭ　３７に入力されると、ＲＯＭ３７
のアドレスは、同図の第３段に示すように（１１０００
１０）となる。その時、ＲＯＭ３７のデータは、同道に
示すように（０１１１１１１００）となる。

この結果、最上位ピットＤ８が゛ｏパに変化するので、
ＮＮＨ３８はイネーブル状態となってラベルバス４１に
出力される。この時、続いてＷ４パルスがラインバッフ
ァ３１．ラッチ回路３６及び連結テーブル５５に与えら
れるので、これらに着目画素ＰのラベルとしてＮＮＨ３
８の内容が格納される。以上の手順は、ｅ２．ｅ３．ｅ
５についても同様である。

次に、第４図（ａ）のｅ４の状態を検出した場合に、は
、上記と同様Ｐ１の時点でＦＦ３３及びラッチ回路３４
〜３６内にそれぞれデータが保持され、Ｐ２パルスがＲ
ＯＭ３７に入力されると、ＲＯＭ３７のアドレスは、第
５図の第４段に示すように（０４１１０１０）となる。

その時、ＲＯＭ　３７のデータは、同道に示すように（
１１１１１１１００）である。Ｐ３パルスがＲＯＭ１３
７に入力されると、ＲＯＭ３７のアドレスは、同図の第
５段に示すよウニ（１０１１０１０）　トナル。ソノ時
、ＲＯＭ３７のデータは変わらず、同国に示すように（１１１１１１１１０）を維持する。Ｐ４パルスがＲＯ
Ｍ３７に入力されると、ＲＯＭ３７のアドレスは、同図
の第６段に示すように（１１０１０１０）となる。

その時、ＲＯＭ３７のデータは、同国に示すよ）に（１
１１１１１０００）となる。この結果、データＤ２が“
０パに変化するので、ゲート４２はイネーブル状態とな
ってラベルバス４１にラッチ回路３５に保持されたラベ
ル番号が出力される。この時、続いてＷ４パルスがライ
ンバッファ３１．ラッチ回路３６及び連結テーブル５５
に与えられるので、これらに着目画素Ｐのラベルとして
隣接画素Ｂのラベル番号が格納される。

同様にｅ６．ｅ７のパターンを検出した場合には、Ｐ２
パルスがＲＯＭ３７に入力されると、ＲＯＭ３７のアド
レスは、第５図の第７段に示すように（０１１１０１１
）となる。その時、ＲＯＭ３７のデータは、同国に示す
ように（１１０１１１０１１）である。このため、ゲー
ト４２がイネーブル状態となってラッチ回路３５の内容
がラベルバス４１に出力され１、メモリ５３に記憶され
る。Ｐ３パルスがＲＯＭ３７に入力されると、ＲＯＭ３
７のアドレスは、同図の第８段に示すように（１０４１
０１１）となる。その時、ＲＯＭ３７のデータは、同国
に示すように（１１１０１０１１１）となる。この結果
、ゲート４３はイネーブル状態となり、ラッチ回路３６
の内のラベル番号がラベルバス４１に出力され、メモリ
５２に保持される。Ｐ４パルスがＲＯＭ３７に入力され
ると、ＲＯＭ３７のアドレスは、同図の第９段に示すよ
うに（１１０１０１１）となる。その時、ＲＯＭ３７の
データは、同国に示すように（１１１１１０１１１’）
となる。この結果、ラッチ回路３６に保持されたラベル
番号のラベルバス４１上への出力が維持されるので、続
く〜ｖ４パルスによって上記ラベル番号がラインバッフ
ァ３１゜ラッチ回路３６及び連結テーブル５５に与えら
れる。

このような操作が続けられると、連結テーブル５５には
第４図（ｂ）に示すようなラベル番号が保持される。

この状態では同一の連結成分に１．２．４の異なるラベ
ル番号が付与されているので、これを同一のラベル番号
に統一する必要がある。そこで、以下の操作によって、
これら連結成分のラベル統合処理が行われる。

まず、メモリ５２の内容は第６図中ｆ１に、メモリ５３
の内容は同図ｆ２に示される通りであり、これらは共に
同一の連結成分に付与されたラベル番号を意味している
。一方、連結テーブル５５には、同図ｆ３に示すような
４つのラベル番号が格納されている。舶述した２つのメ
モリ５２．５３のデータは、ラベル統合部５４で比較さ
れ、ラベル番号の小さい方に統合される。この時、ｆ３
のアドレス２と４の連結が失われないように、−時的に
アドレス４の内容であった２′′を保存し、再度アドレ
ス４の内容°“１′′とアドレス２の内容゛２′とを比
較して、アドレス２に１″を愚込む。この結果、最終的
には同図ｆ４に示すように連結テーブル５５の内容は統
合され、かつ並び変えられて“１″と３″とになる。

以上の手順でラベル番号は求まるが、一般的な画像計測
においては、上記画像連結処理に加え、各連結成分の始
点、終点のｘ、ｙ座標、これらの面積等を知る必要があ
る。この場合には、例えば第７図に示すように、連結処
理回路６１で求められた各ラベルをカタログ作成回路６
２に与える。

各ラベルの始点、終点のｘ、ｙ座標及び面積は、走査時
にカタログ作成回路６２と二次元カウンタ６３とで計測
され、連結ラベル統合部５４に同期して比較、加算、並
び変えの処理がなされる。連結統合された画像のｘ、ｙ
！標の最小直（！！８点）、及び最大値（終点）、そし
て面積値は、カタログ作成回路６２の内部のメモリに蓄
えられる。

以上のように本実施例によれば、選択手段としてワイヤ
ードオア回路を採用しているので、選択手段の回路構成
の簡単化を図ることができる。しかも、この実施例では
１つの処理を４つのサイクルの時分割処理によって行な
っているので、連結処理部では並列９８理を行なう必要
がない、しだがって、これによっても回路構成の簡単化
が図れる。

なお、上述した実施例では、３つのラッチ回路の出力に
それぞれ３ステートゲートを配したが、イネーブル端子
付きのラッチ回路な用いれば、ＲＯＭのアドレス入力部
にアドレスラッチを設けておけば、各ゲートを省略でき
るので、さらに構成の簡単化を図ることができる。

また、以上の説明では、黒画素の連結を調べたが、白画
素のＭ語処理も、ＮＮＬを用いて同様に行なうことがで
きる。また、抽出する画素は２×３画素でも同様に４サ
イクルの連結処理は可能である。さらには走査方向も横
方向に限定されるものではなく、縦方向に走査するよう
にしても良い。

［発明の効果コ以上述べたように、本発明によれば、選択回路としてワ
イヤードオア回路を用い、着目画素に付与するラベル番
号を、連結検出手段の出力データによって択一的に選択
し、これを上記ワイヤードオア回路の入力に与えている
ので、選択回路の構成が簡略化でき、小形化、低価格化
の図れる画像連結処理装置を提供することができる。

【図面の簡単な説明】

第１図は本発明の一実施例に係る画像連結処理装置の構
成を示す回路図、第２図は同装置における制御パルスを
示すタイミング図、第３図は同装置における入カバター
ンの態様を示す図、第４図は同装置への入カニ圃画像の
例を示す図、第５図は同装置におけるＲＯＭの内容を示
す図、第６図は同装置における連結処理部の作用を説明
するため図、第７図は同装置の使用例を示すブロック図
、第８図は従来の面間処理装置の構成を示すブロック図
である。１．３１・・・ラインバッファ、２．３３・・・フリッ
プフロップ回路、３〜５，３４〜３６・・・ラッチ回路
、６．３７・・・ＲＯＭ、７・・・マルチプレクサ、８
゜２９・・・白ラベルカウンタ、９，３８・・・黒ラベ
ルカウンタ、１０．２２・・・連結処理部、２１・・・
連結成分抽出部、３０・・・制御回路、４２〜４４・・
・３ステートゲート。出願人代理人　弁理士　鈴江武彦第３図　− 第２図第４図第６図

Claims

【特許請求の範囲】

（１）着目画素の二値画像データを保持する第１の保持
手段と、上記着目画素に隣接する近傍画素の二値画像デ
ータ及びそのラベル番号を保持する第２の保持手段と、
新たに付与するラベル番号を保持する第３の保持手段と
、前記第１及び第２の保持手段で保持された二値画像デ
ータを元に前記着目画素と近傍画素との連結を検出する
連結検出手段と、該連結検出手段の検出結果に基づいて
前記第２及び第３の保持手段から着目画素に付与するラ
ベル番号を選択する選択手段とを具備した画像連結処理
装置において、前記選択手段は、前記第２及び第３の保持手段の出力を
入力とするワイヤードオア回路で構成され、前記連結検
出手段の検出結果に基づき前記第２及び第３の保持手段
からのラベル番号出力を択一的に入力するものであるこ
とを特徴とする画像連結処理装置。
（２）前記選択手段は、前記第２の保持手段に保持され
た近傍画素のうち異なるラベル番号を持つ複数の近傍画
素が前記着目画素に同時に連結することを前記連結検出
手段が検出した場合、前記連結検出手段の検出結果に基
づいて上記連結する複数のラベル番号を時分割入力する
ものであることを特徴とする特許請求の範囲第１項記載
の画像連結処理装置。
（３）前記第１及び第２の保持手段に二値画像データを
格納する第１のタイミング、前記連結する複数のラベル
番号を時分割入力する第２及び第３のタイミング、及び
前記着目画素にラベル番号を付与する第４のタイミング
の順に時分割処理されることを特徴とする特許請求の範
囲第２項記載の画像連結処理装置。