JPH01295377A - ラベリング処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、２値化された２次元画像に対してラベリング
処理を行なうラベリング処理装置に関するものである。

（従来の技術） 従来、ラベリング処理は逐次処理の典型とされ、中央処
理装置（ＣＰＵ）により予じめ設定されたプログラムに
したがって実行されている。すなわち、従来はソフトウ
ェアで実行されている。白、黒の信号（ここでは白を「
０」とし、黒を「１」とする）で２値化されて２次元画
像メモリに記憶されている２次元画面の順次の画素を読
み出し、例えば「１」の画素を検索して適当な番号（一
般的には順序番号）を付け、さらにその近傍に信号レベ
ルが「１」の画素があるかどうかを調べ、「１」の画素
があれば連続したパターンであると判断して同じラベリ
ング番号を付け、近傍にラベリング番号を付けていない
「１」の画素がなくなったら次の「１」の画素を検索し
て前に付けたラベリング番号より１つ大きいラベリング
番号を付けるという作業を「１」の画素全てに番号を付
は終るまで繰り返すようにしている。このようなＣＰＵ
によりソフトウェアでラベリング処理しているのは、２
次元画面上の画素配列順に沿ってラベリング番号を付け
ていくと、本来同一のラベリング番号を付けるべき連続
したパターンに２つ以上の異なる番号が付けられてしま
う可能性があり、実時間処理には不向きであるためであ
る。

（発明が解決しようとする課題） 上述したように従来のラベリング処理はＣＰＵによるソ
フトウェアにより行なっていたが、ＣＰＵがプログラム
を読み出して解析する時間や判断する時間といったオー
バーヘッドに加え、成る画素の近傍の画素の情報を一度
に読み出したり書き込んだりすることが本質的にできな
いという、所謂フォノ・ノイマン・栄トルネックなどの
問題があるため、ラベリングに多大の時間を要し高速性
が要求される用途には適用し難いという欠点があった。

本発明は、上述した従来の欠点を除去し、ハードウェア
によって高速応答性を有するラベリング処理を行なうこ
とができ、従来技術の欠点のために適用することができ
なかった用途においてもラベリング処理を適用すること
ができるラベリング処理装置を提供することを目的とす
るものである。

（課題を解決するための手段） 本発明のラベリング処理装置は、それぞれ２値化された
信号レベルを有する多数の画素から構成される２次元画
面を記憶する２次元画像メモリから画素を順次に読み出
してラベリング処理する装置において、 前記２次元画像メモリから画素を順次に読み出すととも
にこの画素を遅延して今回ラベリング番号を付けようと
する画素と当該画素の近傍の複数の画素とを同時に出力
する画像読み出し回路と、この画像読み出し回路から出
力される当該画素およびその近傍の複数の画素の信号レ
ベルおよびこれら複数の近傍画素に既に付けられている
ラベリング番号とに基づいて当該画素に付けるべきラベ
リング番号を出力するとともに前記複数の近傍の画素に
付けられているラベリング番号が異なるときにはこれら
のラベリング番号が１つの連続したパターンに属するこ
とを表わす統合情報を出力するラベリング処理回路と、 このラベリング処理回路から出力されるラベリング番号
を遅延して前記の複数の近傍画素のラベリング番号を同
時に出力して前記ラベリング処理回路に供給するラベリ
ング番号遅延回路とを具えることを特徴とするものであ
る。

（作　用） 本発明によるラベリング処理装置は、２次元画面上の画
素配列順に沿ってラベリング番号を付して出力するとと
もに本来同一のラベリン番号が付されるべき画素に異な
るラベリング番号が付されて出力される場合には、これ
らの異なる番号が同一の連続したパターンに属するもの
であることを指示する統合情報を別個に出力するように
構成したものである。このような本発明のラベリング処
理装置によればパイプライン構造を有するハードウェア
で実時間の処理が可能となり、したがってきわめて高速
の応答特性を実現することができる。

（実施例） 第１図は本発明によるラベリング処理装置の基本的構成
を示すブロック図である。本発明のラベリング処理装置
は、それぞれ白または黒の２値化された信号レベルを有
する多数の画素から構成される２次元画面を記憶する２
次元画像メモリ１から順次の画素信号を読み出してラベ
リング処理を行なうものであり、２次元画像メモリ１か
ら画素を順次に読み出すとともにこの画素を遅延して今
回ラベリング番号を付けようとする画素（画素Ｅとする
）とこの画素の近傍の複数の画素（例えば８近傍の場合
には４つの画素Ａ−Ｄとする）とを同時に出力する画像
読み出し回路２と、この画像読み出し回路から出力され
る複数の画素Ａ−Ｅの信号レベルおよび近傍の複数の画
素Ａ−Ｄに既に付けられているラベリング番号ＬＡ〜し
。とに基づいて当該画素にラベリング番号Ｌ６を付ける
とともに複数の近傍の画素Ａ−Ｄに付けられているラベ
リング番号ＬＡ〜し。が異なるときには、これらのラベ
リング番号が１つの連続したパターンに属するものであ
ることを表わす統合情報ＴＩを当該画素のラベリング番
号と併せて出力するラベリング処理回路３と、このラベ
リング処理回路３から順次に出力されるラベリング番号
し、を遅延して複数の近傍の画素のラベリング番号ＬＡ
−Ｌ、を同時に出力してラベリング処理回路３に供給す
るラベリング番号遅延回路４とを具えるものである。

ラベリング処理回路３は画像読み出し回路２から同時に
供給される画素Ａ−Ｅの信号レベルおよびラベリング番
号遅延回路４から供給される画素Ａ〜Ｄに対して既に付
けられたラベリング番号ＬＡ〜Ｌｏから当該画素Ｅにラ
ベリング番号ＬＥを付けるとともに統合情報ＴＩを作成
する。この場合、当該画素Ｅの近傍に既にラベリング番
号が付けられている画素が複数ある場合には、当該画素
にはそれらのラベリング番号のいずれかと同じ番号を付
け、統合情報としては、これらのラベリング番号が同一
の連続したパターンに属するものであることを表わす情
報とする。例えば当該画素Ｅが黒で、近傍の画素ＢとＤ
が黒でこれらにラベリング番号し、およびし。がそれぞ
れ付けられている場合には、当該画素のラベリング番号
をり。とじ、統合情報としてはし、＝し、を出力するよ
うにする。

第２図は第１図に示す２次元画像メモリ１に記憶されて
いる２値化された２次元画面を示すものである。本例で
は８近傍のラベリングオペレータを用いて、８近傍の画
素に同−若しくは同一と看做せる番号を付けるものとす
る。第２図に示すように、２次元画面中には、太実線で
示すように複数の独立したパターンＰＩ、　Ｐ２．　Ｐ
３・・・が存在しているものとする。破線は各画素の境
界を示しており、パターン内の画素の信号レベルとして
は、例えば黒で論理値「ｌ」が与えられ、パターン以外
の背景は白で論理値「０」が与えられているものとする
。このような２次元画像はメモリのｍｘｎの記憶位置に
記憶されており、これらの画素ｆｌｒ＋＋ｐ＋□・・・
ｆｌ＋ｎ；　ｐ２１１１）２□、・・・ｐ２ａ　；　ｐ
ａｌ＋　ｐｓ２・・・ｐｌ、を１頃次に読み出してラベ
リング処理を行なうものである。

この読み出し方法としては、一定の周期を有するタロツ
クに同期して読み出すが、読み出しの順番は、最初に左
上隅の画素ｐ１１、次に１つ右側の画素ｐｌ□、すなわ
ち水平方向に１クロック進んだ画素、次にまた１つ右側
の画素ｐＩ３　というように１クロツク毎に水平方向に
左から右へ読み出し、第１ラインの画素を全て読み出し
たら、第２ラインの左側の画ｆｌ”　ｐ２１すなわち、
最初に読み出した画素Ｉ）＋＋　より垂直方向に１画素
分進んだ画素を読み出し、次にその１つ右側の画素ｐ２
２を読み出し、以下同様にｍ行ｎ列の画素を順次に読み
出していく。このようにして読み出した順次の画素の信
号レベルが「１」であるか「０」であるかを判別し、「
１」の画素についてラベリング番号を付けていく。この
ラベリング処理には通常のようにラベリングオペレータ
を用いる。このラベリングオペレータは例えば第３薗に
示すような３Ｘ３画素のマトリックスから構成されてお
り、ラベリング番号を付けようとする画素すなわち注目
している画素をＥとし既にラベリング処理が施された画
素Ａ〜Ｄの４画素を取り込むようなものである。ここで
画素Ｅが「１」の場合には、Ａ−Ｄの画素に「１」のも
のがあるか否かを判別し、「１」がある場合には当該画
素Ｅはその画素と連結しているものとしてその画素に既
に付けられているラベリング番号と同じラベリン番号を
付け、画素Ａ−Ｄに「１」のものがない場合には当該画
素は新たな独立パターンであると判断し、最後に付けた
ラベリング番号の次の番号を付ける。このようなラベリ
ングオペレータを用いて第２図に示す２次元画面をラベ
リング処理した結果を第２図の各画素にラベリング番号
１，２・・・を付けて示す。ここでパタ−ンＰ、は最初
に現われるパターンであり、その形状から全画素に同一
のラベリング番号「１」が付けられるが、パターンＰ２
はその上辺が凹んでいるので２個の別々のパターンと判
定され、２つのラベリング番号「２」および「３」が付
けられることになる。また、第３のパターンＰ３の全画
素には同一のラベリング番号「４」が付けられることに
なる。ここで第２のパターンＰ２の画素ｐをラベリング
処理するとき、ラベリングオペレータの画素はＢおよび
Ｄに「２１」が現われるのでこれらは連続したパターン
であることがわかるが、画素Ｂには「３」、画素ｒ　Ｄ
　Ｊには「２」のラベリング番号が既に付けられている
。実時間でのラベリングを行なうためには既に付けたラ
ベリング番号を変更することはできないので、当該画素
ｐにはいずれか一方のラベリング番号、第２図では「２
」を付け、同時にラベリング番号「２」が付けられたパ
ターンとラベリング番号「３」が付けられたパターンと
は連続したパターンであることを表わす統合情報「２＝
３」を出力するようにする。このようにしてラベリング
番号とラベリング番号相互の関連を表わす統合情報とを
ハードウェアにより実時間で出力することができる。

ラベリング処理回路３において上述したようなラベリン
グ処理を行なうには、次のようなアルゴリズムにしたが
ってハードウェアを構築すればよい。

規則１：Ｅが「０」のとき、ラベリング番号「０」を付
ける。

規則２：Ｅが「１」で、かつＡ、　　Ｂ、　Ｃ，Ｄがい
ずれも「０」のときは、それまで付 けたラベリング番号の最大値よりも１ つ大きい番号を付ける。ただしＥが最 初に現れた「１」画素であるときはラ ベリング番号「１」を付ける。

規則３：Ｅが「１」画素でかつＡ、　　Ｂ、　Ｃ，Ｄの
いずれか１つだけが「１」画素のと きは、この「１」画素に付けられてい るラベリング番号と同じ番号を付ける。

規則４：Ｅが「１」画素で、かつＡ、　　Ｂ、　Ｃ。

Ｄの内「工」画素が複数あるときは、 これらの「１」画素に付けられている ラベリング番号のいずれかの番号を付 けるとともにこれらの１画素に付けら れているラベリング番号の全てが同一 パターンに属することを表わす統合情 報を出力する。

メモリ１から読み出した順次の画素を上述した規則にし
たがって動作するラベリング処理回路３に通すことによ
り実時間でラベリング処理を行なうことができ、出力端
子５および６にラベリング番号ＬＥ　Ｊｓよび統合情報
ＴＩがそれぞれ出力されることになる。本発明によるラ
ベリング処理装置によれば、独立パターンには必らずし
も順序番号が付けられないが、ラベリング番号と統合情
報とから次工程において必要な処理を施すことができる
。

例えば２次元画面中の独立パターンの個数をカウントし
たい場合には、ラベリング番号の最大値と統合情報とか
ら容易に求めることができる。すなわち、第２図に示し
た例ではラベリング番号の最大値は「４」で統合情報か
らラベリング番号ｒ２ｊと「３」は連続したパターンに
属するものであることが示されているので独立パターン
の個数は４−１＝３として簡単に求めることができる。

また成る独立パターンの重心位置を求めたい場合、例え
ばパターンＰ２の重心位置を求めた場合には、このパタ
ーンＰ２の画素にはラベリング番号「２」と「３」が付
けられていることが統合情報で示されているから、ラベ
リング番号「２」と「３」が付けられている画素を読み
出して来て、重心位置を求めればよい。

第４図は本発明によるラベリング処理装置の一実施例の
構成を示すものである。入力端子７には、第１図に示す
２次元画像メモリ１から順次に読み出される画素Ｅが供
給され、この画素は画像読み出し回路２０１部分を構成
する遅延回路２人に供給する。この遅延回路２人には１
画素分すなわち１クロツタ分１０（Ｄはクロックの周期
）の遅延を与える遅延回路８〜１０と、水平ライン上の
画素数から１を減算した画素数分すなわち（ｎ−１）Ｄ
の遅延を与える遅延回路１４とを具えている。入力端子
７に供給される画素Ｅを全く遅延しないでライン２１に
供給するとともにＩＯ遅延回路８に通して１画素分遅延
してライン２２に供給する。さらに人力信号Ｅは（ｎ−
１）Ｄ遅延回路１４にも通してライン２３に（ｎ−１＞
Ｄだけ遅延した信号を供給するようにする。この信号は
さらにＩＯ遅延回路９および１０に順次に通し、ライン
２４および２５にさらにＩＯおよび２Ｄだけ遅延した信
号を供給するようにする。

このように構成すると、入力端子７に当該画素Ｅが供給
されるときに、ライン２１〜２５にはそれぞれ画素Ｅ、
　　Ｄ、　Ｃ，ＢおよびＡが同時に出力されることにな
る。これらの画素Ａ−Ｅをラベリング処理回路３に設け
たラベリング番号選択論理回路１６に同時に供給する。

この論理回路１６は上述した規則１〜４にしたがって動
作し、当該画素已に付けるラベリング番号し、および統
合情報ＴＩとして出力するラベリング番号を有する画素
の位置を示す符号をライン２７に供給するとともに上記
の規則１および２が適用される場合に、最初のラベリン
グ番号を示す信号またはそれまでに付けた最大のラベリ
ング番号をインクリメントして更新すべきことを示す信
号をライン２６に供給する。このような機能を有するラ
ベリング番号選択論理回路１６はプライオリティエンｊ
−ダを用いれば容易に実現することができる。

上述したライン２６に現われるインクリメント指示信号
は、最大のラベリング番号を保持するとともにこれを更
新することができる計算回路１７に供給する。この計算
回路１７は初期化時には「１」にセットされ、ライン２
６にラベリング番号更新信号が現われる度に１つずつイ
ンクリメントした値Ｎをライン２９に出力するものであ
り、カウンタで構成することができる。ラベリング処理
回路３にはさらに入力画素の信号レベルが「０」のとき
に付けられるラベリング番号Ｚを保持し、出力ライン２
８に供給する零コード回路１８を設ける。このラベリン
グ番号は「０」であるから、零コード回路１８は単にラ
イン２８をグラウンドに接続する回路で構成することが
できる。ライン２７．２８および２９はラベリング番号
選択回路１９に接続する。この選択回路１９には他に画
素Ａ−Ｄに既に付けられているラベリング番号ＬＡ””
’　Ｌｏをラベリング番号遅延回路４から同時に供給す
る。このラベリング番号選択回路１９は６つの人力Ｚ、
　Ｎ、　ＬＡ−Ｌ、の中から、ライン２７を介してラベ
リング番号選択回路１６から供給されるラベリング番号
選択符号により指示されるラベリング番号を選択し、こ
れを当該画素Ｅのラベリング番号しゃ　としてライン３
０に出力するものである。このようにして出力ライン３
０に出力されるラベリング番号り、はラベリング番号遅
延回路４に供給する。このラベリング番号遅延回路４は
画素遅延回路２Ａと同様の構成を有しており、３個のＩ
Ｏ遅延回路１１〜１３と１個の（ｎ−１）Ｄ遅延回路１
５とを具えており、ライン３１〜３４に複数の近傍画素
り、Ｃ，Ｂ、Ａのラベリング番号Ｌｏ、　Ｌｃ。

Ｌｓ、　ＬＡを同時に出力するように構成する。これら
のライン３１〜３４に現われるラベリング番号しＤ〜Ｌ
Ａは統合情報出力回路２０にも同時に供給する。

この統合情報出力回路２０にはラベリング番号選択論理
回路１６から出力され、統合情報として出力すべきラベ
リング番号を指示する符号をライン２７を介して供給す
る。じたがって統合情報出力回路２０は、ラベリング番
号ＬＡ　””Ｌｏの中から同一のパターンに属する複数
のラベリング番号を選択し、これを出力ライン３５に統
合情報として出力する。この統合情報出力回路２０は、
出力すべき統合情報の形式により種々の構成を採ること
ができるが、最も単純なものはライン２７に現われる符
号に基づいて上記の規則４が適用されたことを識別し、
その場合にだけＬＡ＋ＬＢ　、［、ｃ　、１．ｏをその
まま出力するゲート回路を以って構成することができる
。

本発明は上述した実施例にのみ限定されるものではなく
種々の変更や変形が可能である。例えば上述した実施例
ではラベリングオペレータとして８近傍のものを用いた
が４近傍等の他のラベリングオペレータを用いることも
できる。例えば４近傍を採用するときは、第３図におい
て、画素ＡおよびＣを除けばよい。また、ラベリング処
理回路は第４図に示した構成に限定されるものではなく
、同じ機能を果すものであればどのような構成とするこ
ともできる。

（発明の効果） 上述したように、本発明のラベリング処理装置では、出
力情報をラベリング番号とラベリング番号相互の関係を
表わす統合情報とに分割したため、パイプライン構造を
用いたハードウェアで実現することができ、従来ソフト
ウェアに依っていたため非常に長い処理時間を要してい
たラベリング処理をきわめて高速に実行できるようにな
った。したがって、いままで時間的制約から適用できな
かった分野にもラベリング処理を適用できるようになり
画像処理技術の一層の発展に寄与できる効果がある。

【図面の簡単な説明】

第１図は本発明のラベリング処理装置の基本的構成を示
すブロック図、 第２図および第３図は同じくその動作を説明するための
線図、 第４図は本発明によるラベリング処理装置の一実施例の
構成を示すブロック図である。 Ｐ１〜Ｐ３・・・独立パターン ｐｌｚ−ｐｌＩ、、、ｐ、Ａ−Ｂ・・・画素ＬＡ−ＬＥ
・・・ラベリング番号 ＴＩ・・・統合情報　　　　　１・・・２次元画像メモ
リ２・・・画像読み出し回路　２Ａ・・・画素遅延回路
３・・・ラベリング処理回路 ４・・・ラベリング番号遅延回路 １６・・・ラベリング番号選択論理回路１７・・・計算
回路 １９・・・ラベリング番号選択回路 ２０・・・統合情報出力回路

Claims (1)

1. 【特許請求の範囲】 １、それぞれ２値化された信号レベルを有する多数の画
   素から構成される２次元画面を記憶する２次元画像メモ
   リから画素を順次に読み出してラベリング処理する装置
   において、 前記２次元画像メモリから画素を順次に読 み出すとともにこの画素を遅延して今回ラベリング番号
   を付けようとする画素と当該画素の近傍の複数の画素と
   を同時に出力する画像読み出し回路と、 この画像読み出し回路から出力される当該 画素およびその近傍の複数の画素の信号レベルおよびこ
   れら複数の近傍画素に既に付けられているラベリング番
   号とに基づいて当該画素に付けるべきラベリング番号を
   出力するとともに前記複数の近傍の画素に付けられてい
   るラベリング番号が異なるときにはこれらのラベリング
   番号が１つの連続したパターンに属することを表わす統
   合情報を出力するラベリング処理回路と、 このラベリング処理回路から出力されるラ ベリング番号を遅延して前記の複数の近傍画素のラベリ
   ング番号を同時に出力して前記ラベリング処理回路に供
   給するラベリング番号遅延回路とを具えることを特徴と
   するラベリング処理装置。