JP3307467B2 - ラベリング方式およびラベリング回路 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、画像の各画素にラベ
ルを付けるラベリング方式およびラベリング回路に関
し、特に、画像に対し局所画像領域を走査させて各画素
に一時的ラベル（以後、仮ラベルと称す）を付加すると
ともに、仮ラベルの連結関係を記憶し、次いでこの連結
関係に基づいて各画素に最終ラベルを付加するラベリン
グ方式およびラベリング回路に関する。より特定的に
は、この発明は、二値画像の局所画像領域をラスタ走査
し、この局所画像領域の下段において検出されたランに
対して暫定的なラベルを付加し、このランが再度局所画
像領域の上段において検出されたときにこのランの各画
素に対する仮ラベルを決定するラベリング方式およびラ
ベリング回路に関する。またこの発明は、仮ラベルが付
された画像に対し仮ラベルの連結状態に従って連結した
同一領域に１つのラベルを順番に付加するラベリング方
式およびラベリング回路に関する。

【０００２】

【従来の技術】画像処理システムの１つに、認識対象の
形状を区別し、その識別された対象物の面積の計測また
は画面内に含まれる認識対象の個数の計算などを行な
う、視覚認識システムを用いる計測システムがある。

【０００３】図７３は、一般的な視覚認識システムを用
いた計測システムの構成の一例を示す図である。図７３
において、計測システムは、たとえばＩＴＶ（工業用テ
レビ）カメラで構成され、認識対象の画像情報を生成す
る視覚センサ９９０と、視覚センサ９９０からのアナロ
グ映像信号をデジタル映像信号に変換するＡ／Ｄ変換器
９９１と、このＡ／Ｄ変換器９９１からのデジタル映像
信号を所定のしきい値を用いてしきい値処理して二値画
像データを生成する二値化回路９９２と、この二値化回
路９９２からの二値画像の各画素にラベルを付けるラベ
リング回路９９３を含む。

【０００４】このラベリング回路９９３は、与えられた
画像データ系列から連結する領域を検出し、この連結領
域に固有のラベルを付して画像内の対象物を識別する。
計測回路９９４は、このラベリング回路９９３によりラ
ベルを付された画像に従って、画像内の対象物を識別
し、その面積の計測または個数の計算などの処理を実行
する。次に、この視覚センサ９９０ないしラベリング回
路９９３の動作について図７４を参照して簡単に説明す
る。

【０００５】視覚センサ９９０からはラスタ走査方式で
画面を走査したアナログ映像信号が出力される。この視
覚センサ９９０からのアナログ映像信号はＡ／Ｄ変換器
９９１によりデジタル映像信号に変換され、図７４
（ａ）に示すようなデジタル画像データが生成される。
図７４（ａ）においては比較的画像データの値の大きい
領域Ａ，ＢおよびＣを代表的に示す。

【０００６】二値化回路９９２はこのＡ／Ｄ変換器９９
１の出力をしきい値処理する。このしきい値処理によ
り、図７４（ｂ）に示すように、論理“１”の領域
Ａ′、Ｂ′およびＣ′（図７４（ａ）の領域Ａ、Ｂ、お
よびＢにそれぞれ対応する）の領域が生成される。残り
の画像領域は論理“０”となる。ラベル回路９９３はこ
の図７４（ｂ）に示す二値画像に対し連結領域Ａ′、
Ｂ′、およびＣ′を識別し、各連結領域に対しそれぞれ
固有のラベルを付ける。図７４（ｃ）においては領域
Ａ′、Ｂ′およびＣ′に対しラベル１、２、および３が
付された状態が一例として示される。

【０００７】このラベルが異なることは画像内において
対象物が異なるすなわち連結していない領域であること
を示している。計測回路９９４はこのラベルに従って同
一ラベルの領域を抽出してその面積の計算、個数の計算
などの処理を実行する。

【０００８】図７５はラベリング回路によるラベリング
の処理手順を概略的に示す図である。図７５（ａ）に示
すように、入力二値画像から、二値マスクに２４より局
所画像領域が抽出される。各抽出された局所画像領域を
単位としてラベリングが実行される。この二値マスク２
４としては、図７６に示すような２行３列に配置された
画素からなる局所画像領域を切取るマスクが利用され
る。図７６において、二値マスク２４は、上段２４ｂに
より３つの画素位置（ｉ−１，ｊ＋１）、（ｉ−１，
ｊ）および（ｉ−１，ｊ−１）に対応する二値画像デー
タＰ（ｉ−１，ｊ＋１）、Ｐ（ｉ−１，ｊ）、およびＰ
（ｉ−１，ｊ−１）を走査する。二値マスク２４の下段
２４ａは二値マスクの上段２４ｂが抽出する画素に隣接
する画素の画像データＰ（ｉ，ｊ＋１）、Ｐ（ｉ，
ｊ）、およびＰ（ｉ，ｊ−１）を抽出する。この二値マ
スク２４がラスタ走査方式に従って二値画像を走査す
る。

【０００９】この入力二値画像から二値マスク２４によ
り抽出された二値画像局所画像領域に対し、各連結され
た画素領域（ラン）を抽出し、この二値マスク内の近傍
画素データと既に処理が完了した近傍画素ラベルとを用
いて注目画素のラベルを決定する。この結果、図７５
（ｂ）に示すように各画素に対し仮ラベルが付された仮
ラベル画像が生成される。このとき、二値マスクにより
局所画像領域が抽出されて処理が行なわれているため、
同じ連結成分に対しても別々の異なるラベルが付される
場合が生じる。このため、ラベルの合流点（図７５
（ｂ）において丸印で示す）が存在するとき、この合流
点に隣接する連結成分のラベルの接続することを示す関
係を図７５（ｃ）に示すラベル関係テーブルに格納す
る。図７５（ｃ）においてはラベル２とラベル３が接続
関係にあり同一連結成分を構成し、ラベル３とラベル４
が同一連結成分の構成要素であり、またラベル５とラベ
ル６が同一の連結成分の構成要素であることを示す関係
が記憶された状態が示される。

【００１０】二値画像をすべて走査して各画素に対して
ラベル付けを行なった後、このラベル関係テーブルに格
納されたラベル接続関係に従って仮ラベル画像の各ラベ
ルを最終ラベルに変換して最終ラベル画像を生成する
（図７５（ｄ）参照）。このラベル関係テーブルを解析
して仮ラベル画像から最終ラベル画像を生成する処理は
統合処理と一般に呼ばれる。

【００１１】このような処理においては、できるだけリ
アルタイムで各画素のラベリングを行なうためにラベリ
ング回路はハードウェアで構成される。

【００１２】図７７は、従来の二値画像に対するラベリ
ングを行なうラベリング回路の構成を示す図である。こ
の図７７に示すラベリング回路の構成は、たとえば特開
平２−４８７７８号公報に示されている。

【００１３】図７７を参照して、ラベリング回路は、二
値画像データＩ１を受けて、図７６に示す２行３列の画
素に対応する二値画像データを生成するマスク構成部１
を含む。マスク構成部１は、入力二値画像データＩ１を
受ける３段のシフトレジスタ１１ａ、１１ｂ、および１
１ｃと、入力二値画像データＩ１を受ける１ビットライ
ンバッファ１０と、ラインバッファ１０の出力を受ける
３段のシフトレジスタ１１ｄ、１１ｅ、および１１ｆを
含む。１ビットラインバッファ１０は、入力二値画像デ
ータＩ１を１行分（ラスタ走査における１走査線）遅延
させる。シフトレジスタ１１ａ〜１１ｆの各々は、与え
られた二値画像データを１画素分（１クロック期間）遅
延させる。入力二値画像データＩ１は、既に二値化処理
されており、その値は“０”または“１”である。

【００１４】マスク構成部１から図７６に示す局所画像
領域の二値画像データ（以下、二値マスクと称す）が出
力される。説明の便宜のために、ここでいくつかの定義
を行なう：

【００１５】（ｉ） 注目画素：二値マスク２４におい
て下段２４ａの中央の画素。すなわち、図７６において
画面上の位置（ｉ，ｊ）の画素 （ii） 注目ランＲ１：注目画素が属するラン。

【００１６】(iii) 隣接ランＲ２：注目画素が第ｉ行
に存在するとき、第（ｉ−１）行において注目ランに隣
接するラン。

【００１７】（iv） 二値マスク２４の上段２４ｂが隣
接ランＲ２を走査し、下段２４ａが注目ランＲ１を走査
する。二値マスク２４は、二値画像をラスタ走査方式に
従って走査する。

【００１８】（ｖ） ランラベル：隣接ランに付された
ラベルのうちの代表的な１つのラベル。注目ランの暫定
的ラベルとなる。

【００１９】（iv） 連結ラベル：隣接ランが複数個存
在したときに第ｊ列以前（ラスタ走査において）に存在
した隣接ランのラベルのうち最も新しいラベル：ラベリ
ング回路はさらに、マスク構成部１からの二値マスク２
４に応答して注目ランＲ１の終端を検出するランラベル
記憶制御部６と、注目ラン終端検出時に発生されるライ
ト信号に応答してランラベルを記憶するランラベル記憶
部５と、二値マスク２４に応答して、隣接ランＲ２の始
端を検出してそのときのランラベルを格納する連結ラベ
ル記憶部７と、二値マスク２４とランラベル記憶部５の
記憶内容と連結ラベル記憶部７の記憶内容とに応答し
て、隣接ランを構成する各画素のラベルを決定して各画
素に仮ラベルを割付ける仮ラベル決定部２とを含む。

【００２０】ランラベル記憶部５は、ＦＩＦＯ（ファー
スト・イン・ファースト・アウト）型メモリの構成を備
え、記憶した順にその記憶内容を順次読出すことができ
る。このランラベル記憶部５は、ランラベル記憶制御部
６の制御の下に以下の機能を実現する。すなわち、ラン
ラベル記憶部５は、マスク構成部１から与えられる二値
マスク２４に応答して、隣接ランＲ２を検索し、この隣
接ランＲ２に対して付けられたランラベルのうち代表的
な１つのランラベルを記憶する。

【００２１】連結ラベル記憶部７は、二値マスク２４に
おいて、隣接ランＲ２および注目ランＲ１がともに途切
れたとき（Ｐ（ｉ−１，ｊ＋１）＝０かつＰ（ｉ，ｊ＋
１）＝０）には、その記憶内容を０にリセットする。

【００２２】仮ラベル決定部２は、二値マスク２４に応
答して隣接ランＲ２の始端を検出し、この始端検出時に
ランラベル記憶部５へ読出指示信号（リード信号）を与
えるランラベル読出制御部１２と、二値マスク２４とラ
ンラベル記憶部５の出力するランラベルと連結ラベル記
憶部７の出力する連結ラベルとに応答して、ランラベル
の正当性を検査し、この検査結果に従って隣接ランの各
画素の仮ラベルを決定するための制御信号を生成する仮
ラベル選択制御部１３と、新たな対象物出現時に使うべ
きラベルを生成し保持する新ラベルカウンタ１８と、ラ
ンラベル記憶部５からのランラベルと連結ラベル記憶部
７からの連結ラベルと新ラベルカウンタ１８からの新ラ
ベルのうちの１つを仮ラベル選択制御部１３からの制御
信号に応答して選択する仮ラベルセレクタ１４と、仮ラ
ベルセレクタ１４の出力を保持する仮ラベルレジスタ１
５を含む。

【００２３】新ラベルカウンタ１８は、その保持カウン
トが仮ラベルとして仮ラベルセレクタ１４により選択さ
れたとき、仮ラベル選択制御部１３によりそのカウント
値が１増分される。仮ラベルレジスタ１５は、ランラベ
ル記憶制御部６が、注目ランＲ１の始端を検出しかつ二
値マスク２４の上段２４ｂの二値画像データＰ（ｉ−
１，ｊ−１）、Ｐ（ｉ−１，ｊ）、およびＰ（ｉ−１，
ｊ＋１）がすべて０の状態を検出したときその保持内容
が“０”にリセットされる。仮ラベルレジスタ１５の保
持内容がランラベル記憶部５へ与えられる。仮ラベルセ
レクタ１４の出力する仮ラベルが連結ラベル記憶部７へ
与えられる。すなわち、連結ラベル記憶部７は、隣接ラ
ンＲ２の始端検出に応答して、この仮ラベルセレクタ１
４の出力するラベルを連結ラベルとしてラッチする。

【００２４】仮ラベル選択制御部１３は、隣接ランＲ２
の始端を検出したとき、連結ラベル記憶部７から与えら
れる連結ラベルとランラベル記憶部５からのランラベル
とに従って隣接ランＲ２を構成する各画素に対する仮ラ
ベルを決定するための選択信号を仮ラベルセレクタ１４
へ送出する。この仮ラベル選択制御部１３は以下の仮ラ
ベル決定論理に従って選択信号を発生する。

【００２５】（ｉ） ランラベル＝０かつ連結ラベル＝
０のとき：新ラベルカウンタ１８の内容を仮ラベルとし
て選択し、かつ新ラベルカウンタ１８のカウント値を増
分する。

【００２６】（ii） ランラベル＝０かつ連結ラベル≠
０のとき：連結ラベル記憶部７から与えられる連結ラベ
ルを仮ラベルとして選択する。

【００２７】(iii) ランラベル≠０かつ連結ラベル＝
０のとき：ランラベル記憶部５から与えられるランラベ
ルを仮ラベルとして選択する。

【００２８】（iv） ランラベル≠０かつ連結ラベル≠
０かつランラベル＝連結ラベルのとき：ランラベルおよ
び連結ラベルのどちらか一方（たとえばランラベル）を
仮ラベルとして選択する。

【００２９】（ｖ） ランラベル≠０かつ連結ラベル≠
０かつランラベル≠連結ラベルのとき：ランラベルおよ
び連結ラベルのどちらか一方（たとえば連結ラベル）を
仮ラベルとして選択する。このとき、連結ラベルおよび
ランラベルはともに同一対象物に対して付されているも
のであるため、この場合には、統合ラベル送出部３を介
して連結ラベルおよびランラベルが統合処理部４へ送出
される。統合処理部４ではこの連結ラベルおよびランラ
ベルに従ってラベル関係テーブルを生成する。

【００３０】仮ラベル決定部２はさらに、二値マスク２
４に応答して、隣接注目画素データＰ（ｉ−１，ｊ）の
値に従って固定値“０”または仮ラベルレジスタ１５の
出力の一方を選択する選択信号を発生する仮ラベル送出
制御部１７と、仮ラベル送出制御部１７からの選択信号
に応答して、固定値“０”と仮ラベルレジスタ１５の出
力する仮ラベルの一方を選択して出力する仮ラベル送出
部１６を含む。仮ラベル送出制御部１７は、隣接注目画
素データＰ（ｉ−１，ｊ）の値が１の場合には、仮ラベ
ルレジスタ１５の出力する仮ラベルを選択し、隣接注目
画素データＰ（ｉ−１，ｊ）の値が０の場合には、固定
値“０”を選択するように仮ラベル送出部１６の選択動
作を制御する。

【００３１】次に、ラベリング処理過程および主要構成
要素の状態を示す図７８ないし図８２を参照して、この
図７７に示すラベリング回路の動作について説明する。

【００３２】注目ランＲ１は、図７６に示す二値マスク
の下段２４ａにより走査され、隣接ランＲ２は二値マス
ク２４の上段２４ｂにより走査される。今、図７８
（Ａ）に示すような二値画像を考える。図７８（Ａ）に
おいて、「＊」は二値画像データの値が“１”の部分を
示し、「空白」部分は二値画像データの値が“０”の領
域を示す。また、Ｒ１１ないしＲ４２は、説明の便宜上
されるランの名前である。

【００３３】処理される二値画像は水平方向Ｎ画素（座
標ｊ＝０ないしＮ−１）、垂直方向にＭ画素（座標ｉ＝
０ないしＭ−１）の大きさを有し、ラベル付けされるべ
き対象物は二値のうち値１（図７８（Ａ）に示す「＊」
の部分）で表現され、その以外の部分が値０（図７８
（Ａ）における空白領域）で表わされている。またラン
に付されるラベルは１から始まるものとする。

【００３４】図７８（Ａ）に示す初期状態においては、
以下の初期設定が行なわれる。１ビットラインバッファ
１０は、１行分の画素データ（二値画像データ）を記憶
するシフトレジスタ段を備えており、各レジスタの内容
は０に設定される。新ラベルカウンタ１８のカウント値
は１に初期設定される。連結ラベル記憶部７の記憶内容
は０に設定され、仮ラベルレジスタ１５の記憶内容も０
に設定される。ランラベル記憶部５の記憶内容はすべて
クリアされており、何のランラベルも記憶していない。

【００３５】二値画像データＰ（ｉ，ｊ＋１）がマスク
構成部１へ入力されると、シフトレジスタ１１ａ〜１１
ｆは、それぞれ二値画像データＰ（ｉ，ｊ＋１）、Ｐ
（ｉ，ｊ）、Ｐ（ｉ，ｊ−１）、Ｐ（ｉ−１，ｊ＋
１）、Ｐ（ｉ−１，ｊ）、およびＰ（ｉ−１，ｊ−１）
を受け、次のクロックサイクルでその与えられた二値画
像データを出力する。これにより２行３列の二値マスク
２４が生成される。

【００３６】図７８（Ｂ）に示すように、二値マスク２
４が最初の注目ランＲ１１の始端を走査すると、ランラ
ベル記憶制御部６は、二値マスク２４の上段の二値画像
データがすべて０であることを確認して、仮ラベルレジ
スタ１５の保持値を０にリセットする。また、隣接注目
画素（０，４）の二値画像データＰ（０，４）は０であ
るため、仮ラベル送出部１６は、０を選択して出力す
る。

【００３７】図７８（Ｃ）に示すように、二値マスク２
４が注目ランＲ１１の終端に到達すると、ランラベル記
憶部５は仮ラベルレジスタ１５の出力を記憶する。第０
行において隣接ランが存在しなかったため、仮ラベルレ
ジスタ１５の保持値はリセット状態の０を維持してお
り、したがってランラベル記憶部５はこの０を記憶す
る。

【００３８】二値マスク２４がさらにシフトして、注目
ランＲ１２およびＲ１３を走査した場合においても、隣
接ランは存在しないため、注目ランＲ１１に行なわれた
動作と同様の動作が行なわれる。すなわち、第１行を二
値マスク２４の下段が走査し終った時点においては、ラ
ンラベル記憶部５には、ランＲ１１、Ｒ１２およびＲ１
３に対するランラベルとして、３個の０が記憶される。
このとき、また新ラベルカウンタ１８のカウント値は１
であり、また仮ラベルレジスタの保持値は０であり、連
結ラベル記憶部７の保持値も０である。

【００３９】図７９（Ａ）に示すように、二値マスク２
４が次の行（第１および第２行）を走査して最初の注目
ランＲ２１の始端を検出すると、先の行のときと同様の
動作が行なわれ、仮ラベルレジスタ１５のリセットが行
なわれる。

【００４０】図７９（Ｂ）に示すように、二値マスク２
４が右方向にシフトしていく過程で、隣接ランＲ１１の
始端が検出される。この隣接ランＲ１１の始端検出に応
答して、ランラベル記憶部５から、先に記憶されていた
ランＲ１１に付されたランラベル０がランラベル記憶制
御部６の制御の下に読出される。

【００４１】このとき、ランラベルおよび連結ラベルが
ともに０であるため、仮ラベル選択制御部１３は、第１
の条件に従って、新ラベルカウンタ１８の出力であるカ
ウント値１を選択する制御信号を発生する。仮ラベルセ
レクタ１４はこの新ラベルカウンタ１８のカウント１を
選択して出力する。新ラベルカウンタ１８はこのときま
た仮ラベル選択制御部１３の制御の下にそのカウント値
が１増分される。仮ラベルセレクタ１４から出力される
ラベル１は連結ラベル記憶部７および仮ラベルレジスタ
１５にラッチされる。これにより、隣接ランＲ１１に対
する仮ラベルが１と決定される。

【００４２】図７９（Ｃ）に示すように、さらに二値マ
スク２４が１画素右方向にシフトすると、隣接注目画素
（１，４）の二値画像データＰ（１，４）が１となるた
め、仮ラベル送出部１６は、この仮ラベルレジスタ１５
の出力であるラベル値１を選択して出力する。以降、二
値マスク２４の上段２４ｂの中央値の画素（隣接注目画
素）の二値画像データが１の間、仮ラベル送出部１６か
らはラベル値１が選択出力される。

【００４３】図８０（Ａ）に示すように、二値マスク２
４の注目画素が画素（２，６）に到達すると、二値マス
ク２４の右端の画素は上段および下段ともにデータ０で
あるため、連結ラベル記憶部７はリセットされる。

【００４４】図８０（Ｂ）に示すように、二値マスク２
４がさらに１画素右方向にシフトすると、注目ランＲ２
１の終端が検出される。ランラベル記憶部５は、この注
目ランＲ２１の終端検出に応答して、仮ラベルレジスタ
１５から出力されるラベル値１を記憶する。この時点に
おいては、ランラベル記憶部５は、ランＲ１２、Ｒ１３
に対する２個の０のランラベルと、ランＲ２１に対する
ランラベル１を記憶している。

【００４５】図８０（Ｃ）に示すように、二値マスク２
４が注目ランＲ２２および隣接ランＲ１２の始端に到達
すると、まず、ランラベル記憶部５からランＲ１２に対
するラベル値０が読出される。ランラベルおよび連結ラ
ベルがともに０であるため、仮ラベル選択の第１の条件
（ｉ）に従って、仮ラベルセレクタ１４は、新ラベルカ
ウンタ１８のカウント値２を仮ラベルとして選択する。
新ラベルカウンタ１８のカウント値はカウントアッブさ
れて３となる。この仮ラベルセレクタ１４により選択さ
れたラベル２が仮ラベルレジスタ１５および連結ラベル
記憶部７にラッチされる。

【００４６】二値マスク２４の隣接注目画素のデータが
１の間、仮ラベル送出部１６は、仮ラベルレジスタ１５
から出力されるラベル２を選択して出力する。

【００４７】図８１（Ａ）に示すように、二値マスク２
４が注目ランＲ２２の終端に到達すると、ランラベル記
憶部５は仮ラベルレジスタ１５から出力される仮ラベル
値２を記憶する。この時点において、ランラベル記憶部
５が記憶しているランラベルは、ランＲ１３に対するラ
ベル値０、ランＲ２１に対するラベル値１、およびラン
Ｒ２２に対するラベル値２となる。また、二値マスク２
４の右端の画素が上段および下段ともにデータ０となる
ため、連結ラベル記憶部７はリセットされ、その保持内
容は０となる。

【００４８】次いで二値マスク２４は注目ランＲ２３を
走査する。この場合の動作は、注目ランＲ１１、Ｒ１２
およびＲ１３に対して行なわれた動作と同様である。す
なわち注目ランＲ２３の始端において、仮ラベルレジス
タ１５および連結ラベル記憶部７にはデータ０がラッチ
される。図８１（Ｂ）に示すように、二値マスク２４が
注目ランＲ２３の終端に到達すると、ランラベル記憶部
５が仮ラベルレジスタ１５の出力データ０を記憶する。
この時点において、ランラベル記憶部５は、ランＲ１３
に対するランラベル０、ランＲ２１に対するランラベル
１、ランＲ２２に対するランラベル２、およびランＲ２
３に対するランラベル０の各データを記憶する連結ラベ
ル記憶部７は、二値マスク２４の右端の画素のデータ値
がともに０となった時点で０にリセットされている。

【００４９】二値マスク２４が、さらにシフトして、隣
接ランＲ１３を検出すると、隣接ランＲ１２に対して行
なわれた動作と同様にして、ランラベル記憶部５からラ
ンラベル０が読出される。仮ラベル選択の第１の条件
（ｉ）に従って、仮ラベルセレクタ１４は、新ラベルカ
ウンタ１８の出力であるカウント値３を仮ラベルとして
選択する。仮ラベルレジスタ１５および連結ラベル記憶
部７にこの仮ラベル３がラッチされる。新ラベルカウン
タ１８のカウント値は１カウントアップされて４とな
る。さらに仮ラベル送出部１６からは、この仮ラベルレ
ジスタ１５に格納された仮ラベル３が選択されて出力さ
れる。また、注目ランＲ２４の終端において仮ラベルレ
ジスタ１５から出力されるラベル値３がランラベルとし
てランラベル記憶部５に記憶される。

【００５０】二値マスク２４が次の行（第２および３
行）を走査し始めると、まず隣接ランＲ２１を検出す
る。これに応答して、ランラベル記憶部５からランラベ
ル１が読出される。仮ラベルセレクタ１４は、仮ラベル
選択の第３の条件（iii ）に従ってこのランラベル記憶
部５からのランラベル１を選択し、仮ラベルレジスタ１
５および連結ラベル記憶部７には、１がラッチされる。
二値マスク２４の隣接注目画素のデータが１の間は、仮
ラベル送出部１６からはラベル値１が仮ラベルとして選
択されて出力される。

【００５１】その後、二値マスク２４は注目ランＲ３１
を検出する。しかし、この注目ランＲ３１は、隣接ラン
Ｒ２１と接続しているため、また隣接ランＲ２１の終端
が検出されていないため、仮ラベルレジスタ１５、ラン
ラベル記憶部５および連結ラベル記憶部７はその内容を
変化させることはない。

【００５２】図８１（Ｃ）に示すように、二値マスク２
４が、隣接ランＲ２２の始端に到達すると、ランラベル
記憶部５から隣接ランＲ２２に対するランラベル２が読
出される。このとき、注目ランＲ３１が存在しており、
連結ラベル記憶部７の出力はラベル値１であり、互いに
連結する注目ランと隣接ランとが異なるラベルを持って
いることになる。この場合、仮ラベル選択の第５の条件
（ｖ）に従って、仮ラベルセレクタ１４は、ラベル値の
小さい方（ラベル値１）を選択し、仮ラベルレジスタ１
５および連結ラベル記憶部７はこのラベル値１をラッチ
する。また同じ対象物に対して異なるラベルが付けられ
ているため、統合ラベル送出部３は、仮ラベル選択制御
部１３の制御の下にラベル値１および２を統合処理部４
に出力する。統合処理部４は、このラベル１とラベル２
とが接続していることを記憶する。

【００５３】二値マスク２４が、隣接ランＲ２２を走査
している間、隣接注目画素のデータが１のとき、仮ラベ
ル送出部１６は、仮ラベルレジスタ１５から与えられる
ラベル値１を選択して出力する。

【００５４】図８２（Ａ）に示すように、注目画素の二
値画像データがＰ（３，１０）となると、二値マスク２
４の右端画素は上段および下段ともに０となるため、連
結ラベル記憶部７は０にリセットされる。ランラベル記
憶部５は、注目ランＲ３１の終端において、仮ラベルレ
ジスタ１５から出力されるラベル値をランラベルとして
記憶する。

【００５５】図８２（Ｂ）に示すように、二値マスク２
４が、隣接ランＲ２３の始端に到達すると、ランラベル
記憶部５からランラベル０が読出される。連結ラベル記
憶部７から出力される連結ラベルは０であるため、仮ラ
ベル選択の第１の条件（ｉ）に従って、新ラベルカウン
タ１８の出力であるデータ４が仮ラベルレジスタ１５お
よび連結ラベル記憶部５にラッチされる。新ラベルカウ
ンタ１８のカウント値は５となる。

【００５６】隣接ランＲ２３に対して、仮ラベル送出部
１６は、仮ラベルレジスタ１５から出力されるラベル値
４を選択して出力する。隣接ランＲ２３の走査の途中に
おいて、注目ランＲ３２およびＲ３３が走査されると、
それぞれの終端において仮ラベルレジスタ１５から出力
されるラベル値４が注目ランＲ３２およびＲ３３それぞ
れに対するランラベルとしてランラベル記憶部５に記憶
される。

【００５７】二値マスク２４が、隣接ランＲ２４および
注目ランＲ３４を走査すると、隣接ランＲ１３に対して
行なわれた動作と全く同じ動作が行なわれる。この第２
行および第３行の走査が終了した時点では、ランラベル
記憶部５は、ランＲ３１に対するランラベル１、ランＲ
３２およびＲ３３それぞれに対するランラベル４、およ
びランＲ３４に対するランラベル３を記憶している。

【００５８】二値マスク２４が次の行（第３および４
行）の走査を始めて、隣接ランＲ３１および注目ランＲ
４１を走査する過程では、１行前の走査において隣接ラ
ンＲ２１（第２行の最初のラン）および注目ランＲ３１
に対して行なわれた動作と全く同じ動作が行なわれる。

【００５９】図８２（Ｃ）に示すように、二値マスク２
４が隣接ランＲ３２の始端に到達すると、ランラベル記
憶部５から隣接ランＲ３２に対するランラベル４が読出
される。このとき、連結ラベル記憶部７の出力は１であ
る。したがって、隣接ランＲ２２と注目ランＲ３１との
関係（図８２（Ａ）参照）と同様の関係となり、同一対
象物に対して異なるラベルが付けられている。このと
き、仮ラベル選択の第５の条件（ｖ）に従って、仮ラベ
ルレジスタ１５および連結ラベル記憶部７にはこのラベ
ル値の小さい方（１）がラッチされ、ラベル１とラベル
４とが接続していたことは統合処理部４に記憶される。
隣接ランＲ３２に対しては、仮ラベル送出部１６が仮ラ
ベルレジスタ１５の出力であるラベル値１を選択して出
力する。

【００６０】注目ランＲ４１の終端においては、ランラ
ベル記憶部５にランラベル１が記憶される。このとき、
二値マスク２４の右端の画素が上段および下段ともにデ
ータ０であり、ランがこの部分で途切れているため、連
結ラベル記憶部７は０にリセットされる。

【００６１】図８３（Ａ）に示すように、二値マスク２
４が隣接ランＲ３３の始端に到達すると、ランラベル記
憶部５から隣接ランＲ３３に対するランラベル４が読出
される。連結ラベル記憶部７の出力は０であるため、仮
ラベル選択の第３の条件（iii ）に従って、このランラ
ベル記憶部５からのランラベル４が仮ラベルセレクタ１
４により選択されて次いで仮ラベルレジスタ１５および
連結ラベル記憶部７にラッチされる。隣接ランＲ３３に
対しては、仮ラベル送出部１６からラベル値４が仮ラベ
ルとして出力される。

【００６２】図８３（Ｂ）に示すように、二値マスク２
４が隣接ランＲ３４の始端に到達すると、ランラベル記
憶部５から隣接ランＲ３４に対するランラベル３が読出
される。連結ラベル記憶部７の出力は４であり、同一対
象物に対して異なるラベルが付けられていることにな
る。この場合、仮ラベル選択の第５の条件（ｖ）に従っ
て、仮ラベルレジスタ１５および連結ラベル記憶部７に
は、このランラベルおよび連結ラベルのうちラベル値の
小さい方（ラベル値３）がラッチされ、一方、統合処理
部４は、このラベル３とラベル４が接続していたことを
記憶する。隣接ランＲ３４に対しては、仮ラベル送出部
１６から仮ラベルレジスタ１５の出力であるラベル値３
が選択されて仮ラベルとして出力される。注目ランＲ４
２の終端においては、ランラベル記憶部５に仮ラベルレ
ジスタ１５の出力であるラベル値３が記憶される。

【００６３】二値マスク２４が次の行（第４および第５
行）の走査を始めると、隣接ランとしてＲ４１およびＲ
４２が走査される。隣接ランＲ４１およびＲ４２の各々
の始端において、ランラベル記憶部５から対応してラン
ラベル１および３が読出される。連結ラベル記憶部７か
ら出力されるラベル値は、これらのラン始端検出時にお
いては０であるため、仮ラベル選択の第３の条件（iii
）に従ってランラベル記憶部５から出力されるランラ
ベルが選択される。この隣接ランＲ４１およびＲ４２に
属する各画素に対して、仮ラベル送出部１６が仮ラベル
レジスタ１５の出力を選択し、隣接ランＲ４１およびＲ
４２のランラベル１および３がそれぞれ仮ラベルとして
出力される。

【００６４】すべての走査が完了した時点で、図８３
（Ｃ）に示すように二値画像のランの各画素に仮ラベル
が付された仮ラベル画像が得られる。この仮ラベル画像
は、図示しない仮ラベルメモリに格納される（各画素に
対応して仮ラベル値が仮ラベルメモリに記憶される）。

【００６５】統合処理部４には、ラベル１とラベル２、
ラベル４とラベル１、およびラベル４とラベル３がそれ
ぞれ接続していることが記憶されている。統合処理部４
は、これらのラベルの接続関係を解析し、ラベル１を起
点としてラベル２、３および４が分岐していることを検
出しこれらのラベル２、３および４をラベル１に書換
え、図８４に示すような同一対象物に対し１つのラベル
が付されたラベル画像を作成する。

【００６６】図８３（Ｃ）に示す仮ラベル画像のラベル
の統合処理を行なって図８４に示すラベル画像を得るた
めには、仮ラベルの連結関係の解析が必要とされる。こ
の仮ラベルの連結関係の解析は複雑であり、通常ソフト
ウェアを用いて実行されるため、この解析に長時間が必
要となる。このため、ラベルの連結関係を記憶する連結
テーブルの作成に工夫をこらして、ラベル統合処理にお
いてこの解析に必要とされる処理時間を短縮することが
図られている。このような連結テーブル（ラベルの連結
関係を記憶するテーブル）の作成方法として、たとえば
「ラスタ走査型ラベリングの高速化手法」、電子情報通
信学会論文誌Ｖｏｌ．Ｊ７３−Ｄ−ＩＩ，Ｎｏ．１，第
３６頁ないし第４５頁、１９９０年１月発行において奥
山等が示している手法がある。この従来の連結テーブル
の作成手法について図８５を参照して説明する。

【００６７】ラベリングの初期状態においては、図８５
（Ａ）に示すように連結テーブルは、アドレス値とその
アドレスに格納されたデータとが等しい。１つの対象物
に異なるラベルが付けられていることが発覚すると（仮
ラベルの第５の選択条件（ｖ））、統合処理部４に、そ
の２つのラベルが出力される（図８１（Ｃ）、図８２
（Ｃ）、および図８３（Ｂ）の状態）。

【００６８】統合処理部４においては、この仮ラベル選
択の第５の条件に従って、選択されたラベル（仮ラベル
レジスタ１５および連結ラベル記憶部７へ出力されてラ
ッチされるラベル）が、他方の非選択のラベルをアドレ
スとして連結テーブルに書込まれる。すなわち、図８１
（Ｃ）に示す状態においては、連結ラベルが１であり、
ランラベルが２であり、このとき、仮ラベルとして連結
ラベルが選択されるため、連結テーブルにおいては、図
８５（Ｂ）に示すように、ランラベル２をアドレスとし
て、連結ラベル１が連結テーブルに書込まれる。

【００６９】同様に、図８５（Ｃ）に示すように、図８
２（Ｃ）の状態では、ランラベル４をアドレスとし、連
結ラベル１を書込データとして連結テーブルに対する書
込が行なわれる。また図８５（Ｄ）に示すように、図８
２（Ｂ）の状態では、ランラベル３が仮ラベルとして選
択されるため、連結ラベル４をアドレスとしてかつ、ラ
ンラベル３を書込データとして連結テーブルに対する書
込が行なわれる。

【００７０】この図８５（Ｄ）に示す連結テーブルをル
ックアップテーブルとして仮ラベル画像のリラベリング
（ラベルの付け直し）を実行すると、図８６に示すよう
なラベル画像が得られる。すなわち、図８５（Ｄ）に示
す連結テーブルにおいて、仮ラベル画像の各仮ラベルを
アドレスとして連結テーブルのデータを読出し、この読
出されたデータに従って仮ラベルの変換を行なう処理を
実行する。このとき、図８５（Ｄ）に示すように、仮ラ
ベル４はラベル３に変換されるが、仮ラベル３はラベル
３を維持するため、同一対象物に対して２つのラベルが
付されることになる。このような状態を避けるため、再
度ラベル画像の走査を行ない、画素間の接続を検出し、
接続される画素（連結画素）が異なるラベルを付されて
いる場合には、連結テーブルを再度変換してラベルの付
け直しを再度実行し、これにより最終的に図８４に示す
ラベル画像を得る。

【００７１】

【発明が解決しようとする課題】連結テーブルに対し
て、同一アドレスに複数回アクセスしてその内容の書換
えを行なうと、同一対象物に対し異なるラベルが付され
るいわゆる「ラベル分離」が発生する。たとえば、図８
５においては、連結テーブルのアドレス４が二度アクセ
スされて、その内容が４から１、次いで１から３へと変
化している。このため、ラベル３がラベル１と分離し、
ラベル３のランとラベル１のランとが接続しているとい
う情報が消滅する。ラベル４とラベル３との接続関係記
憶時にラベル４とラベル１との接続関係情報が消滅する
ためである。すなわち、従来のラベリング方式における
連結テーブル作成手法では、同一対象物に対して異なる
ラベル付けを行なう頻度が高くなり、この結果連結テー
ブルを解析して仮ラベルのリラベリング（ラベルの付け
直し）を行なうためのラベル統合処理の負荷が大きくな
り、処理性能が低下する。

【００７２】また、リラベリング処理においても、画素
間の連結を検査する必要があるため、その処理が複雑と
なる。すなわち、リラベリングを実行しながら同時に分
離ラベルの有無を検出し、分離ラベル検出時には再度リ
ラベリングを実行する必要がある。このとき、再度連結
テーブルへアクセスしてその内容を書換えるなどの処理
が必要とされ、その処理を高速で実行することができな
い。またこのようなリラベリング時における分離ラベル
の有無の検出およびこの検出結果に基づくリラベリング
の再実行などの複雑な処理をハードウェアで実現する場
合、その装置規模が大きくなる。また全体としてのラベ
リング処理性能が低下するという問題があった。

【００７３】また、連結テーブルを解析したとき、図８
５（ｄ）に示すようにラベル値０、１、および３は、ラ
ベル値が連続値となる、すなわち０、１、および２とな
るようにデータが変更される。このようにして、最終的
に仮ラベルと最終ラベルの関係を記述した形式のルック
アップテーブルである変換テーブルが作成される。この
変換テーブルを用いて、図７５に示すような仮ラベル画
像を走査し、生成された変換テーブルを用いて仮ラベル
値を最終ラベルに置換して図７５に示すような最終ラベ
ル画像を作成する。

【００７４】このような変換テーブルを作成する場合、
連結テーブルと変換テーブルと２つのテーブルが必要と
され、これらは大きな記憶領域を必要とするため、装置
規模が大きくなるという問題があった。

【００７５】それゆえ、この発明の目的は、同一対象物
に対して異なるラベルを割付ける頻度を抑制し、ラベル
の統合処理およびリラベリング処理の負荷を大幅に軽減
することのできるラベリング方式およびラベリング回路
を提供することである。

【００７６】この発明の他の目的は、統合処理における
ソフトウェアに印加される負荷を軽減し、高速でラベリ
ング処理を実行することのできるラベリング方式および
ラベリング回路を提供することである。

【００７７】この発明のさらに他の目的は、ハードウェ
ア量を低減することのできるラベリング方式およびラベ
リング回路を提供することである。

【００７８】

【００７９】

【００８０】

【００８１】

【００８２】

【００８３】

【００８４】

【００８５】

【００８６】請求項１に係るラベリング方法は、同一の
画像領域に複数のラベルが連結しているとき、これら複
数のラベルのうち最も小さいラベル値を以後の走査にお
いて伝搬させるべきラベルとして選択するステップと、
この選択されたラベル値をデータとし、非選択とされた
ラベル値をアドレスとしてテーブルに記憶するステップ
と、この選択および記憶ステップを繰返し実行して各画
像データに仮ラベルを割当てるステップと、テーブルの
第１のアドレス値とこの第１のテーブルのこの第１のア
ドレス位置に格納された第１のデータとの比較を行なう
ステップと、この比較結果が第１のアドレス値および第
１のデータの一致を示すとき、新しいラベル値をテーブ
ルの第１のアドレス位置へ書込むステップと、比較ステ
ップが第１のアドレス値と第１のデータとが異なること
を示すとき、第１のデータをアドレスとするテーブルの
記憶内容である第２のデータを、このテーブルの第１の
アドレス位置へ格納するステップと、これら比較および
書込ならびに格納ステップをテーブルの最小アドレス値
から順次繰返し実行するステップとを含む。

【００８７】請求項２に係るラベリング回路は、画像デ
ータ走査時において、同一画像領域に複数のラベルが連
結しているとき、最小のラベル値を書込データとし、非
選択とされたラベル値をアドレスとして記憶するラベル
記憶手段と、画像データに付されるラベルの最小のラベ
ル値を初期値として順次カウントアップ動作する第１の
カウンタ手段と、この第１のカウンタ手段の出力カウン
ト値をアドレスとしてラベル記憶手段の第１のデータを
読出し、この第１のデータと第１のカウンタの出力カウ
ント値とを比較する比較手段と、ラベルの最小値を初期
値としてカウントアップ動作する第２のカウンタ手段
と、比較手段の一致検出に応答して、第１のカウンタ手
段の出力カウント値をアドレスとし、第２のカウンタ手
段の出力カウント値をラベル記憶手段に記憶するととも
に、この記憶の後第２のカウンタ手段のカウント値を増
分する手段と、比較手段の不一致検出に応答して、第１
のデータをアドレスとするラベル記憶手段の第２のデー
タを、第１のカウンタ手段の出力カウント値をアドレス
としてラベル記憶手段へ記憶する手段とを含む。

【００８８】請求項３に係るラベリング方法は、局所画
像領域を画像データに対して走査させて、この走査時に
同一画像領域に対して複数のラベルが連結していると
き、ラベル値の最小値を以後の走査時に伝搬させるべき
ラベル値として採用するステップと、この採用されたラ
ベル値をデータとし、非選択されたラベル値をアドレス
としてテーブルに記憶するステップと、この走査に従っ
て各画像データに仮ラベルを割当てるステップと、テー
ブルの各記憶値に対し、対応のラベル値が既処理状態で
あるか未処理状態であるかを示すフラグを付加するステ
ップを含む。このフラグは初期状態においては未処理状
態に設定される。テーブルにおいては、ラベル値とフラ
グとが１つのデータを構成するように連結して格納され
る。

【００８９】請求項３に係るラベリング方法はさらに、
仮ラベル画像データの仮ラベルを入力し、該入力したラ
ベル値を第１のアドレスとしてテーブルから第１のデー
タを読出すステップと、この第１のデータのフラグを判
定するステップと、このフラグが既処理状態を示すと
き、第１のデータのラベル値を最終ラベル値として出力
するステップと、このフラグが未処理状態を示すとき、
第１のアドレス値と第１のデータのラベル値とを比較す
るステップと、この比較が等しいことを示すとき、新し
いラベル値と既処理状態を示すフラグとを有する第２の
データをテーブルの第１のアドレス位置に記憶させ、か
つこの新しいラベル値を最終ラベル値として出力するス
テップと、比較が両者が異なることを示すとき、テーブ
ルの第１のデータをアドレスとする位置に格納された第
２のデータを、テーブルの第１のアドレス位置に記憶さ
せるとともに、この第２のデータのラベル値を最終ラベ
ル値として出力するステップとを含む。

【００９０】請求項４に係るラベリング回路は、画像デ
ータの局所画像領域による走査時に同一画像領域に複数
のラベルが連結しているとき、最小のラベル値のラベル
を書込データとし、非選択のラベル値をアドレスとして
記憶するとともに各記憶データに対し既処理／未処理を
示すフラグをリンクさせて１つのデータとして記憶する
連結関係記憶手段を含む。最小のラベル値のラベルは以
後の走査において伝搬される。

【００９１】この請求項４に係るラベリング回路はさら
に、一時的ラベルが付された仮ラベル画像データを入力
し、該入力仮ラベル画像データのラベル値をアドレスと
して連結関係記憶手段から第１のデータを読出す第１の
読出手段と、この第１の読出手段から読出された第１の
データを記憶するレジスタ手段と、第１のデータをアド
レスとして連結関係記憶手段から第２のデータを読出す
第２の読出手段と、第１の読出手段により読出された第
１のデータのラベル値と入力仮ラベル画像データのラベ
ル値との一致／不一致を検出する比較手段と、仮ラベル
の最小値を初期値としてカウントアップ動作するカウン
タ手段と、このカウンタ手段のカウント値とレジスタ手
段に格納された第１のデータと第２のデータのいずれか
を選択して出力する選択手段と、比較手段の出力と第１
のデータのフラグとをデコードし、このデコード結果に
従ってカウンタ手段のカウントアップ動作および選択手
段の選択動作を制御するデコード手段を含む。

【００９２】このデコード手段は、フラグが既処理を示
すとき、レジスタ手段に格納された第１のデータを選択
手段により選択させる手段と、このフラグが未処理状態
を示しかつ一致検出手段出力が不一致を示すとき、第２
のデータを選択手段に選択させる手段と、フラグが未処
理状態を示しかつ一致検出手段の出力が一致を示すと
き、カウンタ手段の出力カウント値を選択手段に選択さ
せるとともにカウンタ手段のカウント値を更新する手段
を含む。

【００９３】請求項４に係るラベリング回路はさらに、
入力仮ラベル画像データのラベル値をアドレスとし、選
択手段が出力するデータをフラグを既処理状態に設定
し、連結関係記憶手段に書込む手段と、選択手段の出力
データを最終ラベル値として出力する手段とを備える。

【００９４】請求項５に係るラベリング回路は、請求項
４に係るラベリング回路がさらに、仮ラベル画像データ
が与えられるサイクルを規定するクロック信号を周波数
逓倍する手段と、この周波数逓倍されたクロック信号に
応答して第１および第２の読出手段、書込手段、デコー
ド手段、比較手段および選択手段の動作タイミングを決
定する制御手段を備える。

【００９５】

【００９６】

【００９７】

【００９８】

【００９９】

【０１００】

【０１０１】請求項１に係るラベリング方法において
は、連結テーブルの連結関係の解析が、そのアドレスと
記憶データとの比較に従って行なわれ、また連結テーブ
ルの記憶内容の書換によって実行されるため、統合処理
が単純となり、また変換テーブルが必要とされないた
め、記憶領域も低減される。

【０１０２】請求項２に係るラベリング回路において
は、構成要素としては、選択手段、第１および第２のカ
ウンタ手段、および一致検出手段などのハードウェアを
用いて連結テーブルの解析を実行するとともに、この統
合処理は、連結テーブルの書換によって実行しているた
めにソフトウェア処理の負担が軽減され、高速で統合処
理を実行することができるとともに、連結テーブルのみ
を用い、変換テーブルは必要とされないため、記憶領域
が低減される。

【０１０３】請求項３に係るラベリング方法において
は、仮ラベル画像データを入力し、この入力仮ラベル画
像データの仮ラベル値をアドレスとして連結テーブルへ
アクセスし、この連結テーブルデータのフラグおよびラ
ベル値と入力仮ラベル値とを検査し、この検査結果に従
って連結テーブルの書換を行なって連結テーブルの解析
を実行するとともに、同時に入力仮ラベル値を最終ラベ
ル値に変換して出力しているため、連結テーブル解析と
最終ラベリングとを同時に実行することができ、高速で
処理を実行することができるとともに、その処理内容が
単純となり、さらに変換テーブルが必要とされないた
め、記憶領域が低減される。

【０１０４】請求項４に係るラベリング回路において
は、入力仮ラベル画像データの仮ラベル値をアドレス入
力とし、この仮ラベル値と連結テーブルのフラグおよび
ラベル値とを検査して連結テーブルの書換を行なう連結
テーブル解析動作をハードウェアで実行するため、この
統合処理におけるソフトウェア処理の負担が軽減され高
速で処理を実行することができるとともに、入力仮ラベ
ル値が最終ラベル値に変換されるため、処理が高速とな
り、また変換テーブルも必要とされないため記憶領域が
低減される。

【０１０５】請求項５に係るラベリング回路において
は、入力仮ラベル画像データ入力サイクルを規定するク
ロック信号を周波数逓倍し、内部回路をこの周波数逓倍
されたクロック信号に従って駆動しているため、高速で
処理を正確なタイミングで実行することができる。

【０１０６】

【実施例】

（ｉ） 実施例１ この第１の実施例においては以下の条件が用いられる。

【０１０７】二値マスク：二値画像をラスタ走査して得
られる二値画像データ系列を入力とし、図７６に示す２
行３列の局所画像領域を二値マスクとして出力する。二
値マスクの上段２４ｂが隣接ランを走査し、二値マスク
２４の下段２４ａが注目ランを走査する。

【０１０８】連結ラベル：画素の連結性を判別するため
に用いられる連結ラベルは、以下の条件に従って決定さ
れる。

【０１０９】（ａ） 注目ランに複数の隣接ランが隣接
している場合、これらの隣接ランのランラベルのうち最
小のラベル値を連結ラベルとして用いる。

【０１１０】（ｂ） 注目ランが存在しない場合、また
は注目ランに隣接するランが存在しなかった場合、連結
ラベルは０とする。

【０１１１】連結テーブル：ラベルの連結関係を記述す
る連結テーブルの構成を図２に示す。異なるラベルを持
つ複数の隣接ランが注目ランを介して同一対象物であっ
たことが検出された場合には、大きい方のラベル値をア
ドレスとして小さいラベル値が連結テーブルに記述され
る。連結テーブルを参照することによりラベルの分岐先
をルックアップすることができる。連結テーブルは初期
状態においては図２に示すように、アドレスと記述内容
とが同一値を有する。連結テーブルが記述され場合（デ
ータの書込が行なわれた場合）、連結ラベルとこの連結
テーブルで参照されたラベル値のうち小さい方のラベル
値が連結ラベルとなる。

【０１１２】仮ラベルの決定：隣接ランの始端の非検出
時においては、仮ラベルは前画素での状態を保持する。
隣接ランの始端検出時においては以下に示す仮ラベル選
択のための５条件に従って仮ラベルが決定される。

【０１１３】（ａ） 第１条件：連結テーブルデータ＝
０かつ連結ラベル＝０の場合には、仮ラベルとして新し
いラベル値を発行する。

【０１１４】（ｂ） 第２条件：連結テーブルデータ＝
０かつ連結ラベル≠０の場合には、連結ラベルを仮ラベ
ルとする。

【０１１５】（ｃ） 第３条件：連結テーブルデータ≠
０かつ連結ラベル＝０の場合には、連結テーブルデータ
を仮ラベルとする。

【０１１６】（ｄ） 第４条件：連結テーブルデータ≠
０、連結ラベル≠０、かつ連結テーブルデータ＝連結ラ
ベルの場合、どちらか一方（たとえば連結テーブルデー
タ）を仮ラベルとする。

【０１１７】（ｅ） 第５条件：連結テーブルデータ≠
０、連結ラベル≠０、かつ連結テーブルデータ≠連結ラ
ベルの場合には、値の小さい方を仮ラベルとする。

【０１１８】図１は、この発明の第１の実施例であるラ
ベリング方式の処理手順を示すフロー図である。以下、
この図１を参照してこの発明の第１の実施例のラベリン
グ処理手順について説明する。

【０１１９】クロック信号に応答して、１画素の二値画
像データが入力される（ステップＳ０）。この画素デー
タ（二値画像データ）の入力に応答して、２行３列の二
値マスクが作成されて出力される（ステップＳ２）。

【０１２０】生成された二値マスクにおいて、その上段
ラン（隣接ラン）の始端が含まれているか否かの判断が
行なわれる（ステップＳ４）。二値マスクの上段のラン
すなわち隣接ランの始端が検出された場合、この上段の
ラン（隣接ラン）に関連するランラベルが読出される
（ステップＳ５）。この読出されたランラベルを用いて
連結テーブルを参照し、連結テーブルからデータが読出
される（ステップＳ７）。すなわち、読出されたランラ
ベルをアドレスとし、連結テーブルから対応のデータが
読出される。

【０１２１】次いで、仮ラベルの決定が行なわれる（ス
テップＳ８）。上段ラン（隣接ラン）の始端非検出時に
おいては前の画素の仮ラベルが維持される。隣接ランが
連続的に存在しているかまたは隣接ランが何ら存在しな
い状態に対応するためである。上段ラン（隣接ラン）の
始端検出時においては、読出されたランラベル値と連結
テーブルデータ値とを比較し、その比較結果に従って仮
ラベルが決定される。この仮ラベル決定のために前述の
仮ラベル選択の５条件が用いられる。

【０１２２】ステップＳ８における仮ラベルの決定の
後、ラベル付け対象画素、すなわち、隣接注目画素のデ
ータが１であるか否かの判別が行なわれる（ステップＳ
９）。隣接注目画素のデータが１の場合には、決定され
た仮ラベルが出力ラベル値（最終仮ラベル）として出力
される（ステップＳ１１）。隣接注目画素のデータが１
でないとき、すなわち０の場合には、固定データ０が出
力ラベル値として選択される（ステップＳ１３）。

【０１２３】このステップＳ９ないしステップＳ１３の
動作と並行して、ラベルに分岐が発生したか否かの判別
が行なわれる（ステップＳ１０）。このラベルの分岐発
生の有無は、仮ラベル決定ステップ（ステップＳ８）に
おいて仮ラベル選択の第５条件が用いられたか否かによ
り識別される（ステップＳ１０）。ラベルの分岐が発生
した場合には、大きい方の非選択ラベル値をアドレスと
し、小さい方の選択ラベル値を書込データとして連結テ
ーブルに対するデータの書込が行なわれる（ステップＳ
１２）。

【０１２４】次いで、二値マスクにおいて下段ラン（注
目ラン）の終端が検出されたか否かの判別が行なわれる
（ステップＳ１４）。下段ラン（注目ラン）の終端検出
時には、この下段ランのランラベルの書込が行なわれ
る。すなわち、そのときに発生されている仮ラベル（ス
テップＳ８において決定された仮ラベル）が下段ラン
（注目ラン）のためのランラベルとして記憶される（ス
テップＳ１６）。

【０１２５】次いで、二値マスクの右端の上段および下
段の画素のデータがともに０であるか否かの判別が行な
われる（ステップＳ１８）。二値マスクの上段および下
段の画素のデータがともに０の場合には、隣接ランおよ
び注目ランがともに途切れた状態であるため、連結ラベ
ルが０にリセットされる（ステップＳ２０）。二値マス
クの右端の上段および下段の画素のデータがともに０で
ない場合には、注目ランまたは隣接ランが存在している
ため、再びステップＳ０へ戻り、次の画素データの入力
が行なわれる。また、ステップＳ２０における連結ラベ
ルのリセットの後、またステップＳ０へ戻る。

【０１２６】この動作が二値画像の全画素の走査完了ま
で繰り返し実行される。次に、具体的処理動作について
説明する。

【０１２７】今、従来例との比較のために、図７８
（Ａ）に示す二値画像と同じ形状の対象物を備える二値
画像に対するラベリング処理について説明する。

【０１２８】図３に示すような初期状態においては、ま
だ注目ランの始端は検出されていない。このため、新ラ
ベルカウンタ、仮ラベルレジスタ、連結ラベル記憶およ
びランラベル記憶部の内容は初期状態を維持している。
ここで、従来例との比較を明確にするために、ランに対
する新しいラベルを生成するための新ラベルカウンタが
用いられており、また仮ラベルを生成する部分にはレジ
スタが設けられており、また連結ラベルおよびランラベ
ルはそれぞれ従来と同様の構成を備えているものと仮定
する。この状態において連結テーブルの内容も図２に示
すとおり、アドレスとそこに格納されているデータとは
同一の値である。

【０１２９】注目ランＲ１１、Ｒ１２、およびＲ１３の
始端検出時においては、隣接ランは存在しないため、ラ
ンラベルが０とされ、注目ランＲ１１、Ｒ１２およびＲ
１３の終端に応答してこのランラベル０がランラベル記
憶部に格納される。

【０１３０】図４において、注目ランＲ２１の始端検出
後、隣接ランの始端検出までは、隣接ランがまだ存在し
ないため、仮ラベルは０に設定されており、またランＲ
２１に対してはランラベルとして０が発生された状態と
なっている（まだランラベル記憶部への格納は行なわれ
ない）。

【０１３１】図５において、二値マスク２４が隣接ラン
Ｒ１１の始端を走査する。この隣接ランＲ１１は、注目
ランとして走査されたときに、ランラベル０が割当てら
れている。この隣接ランＲ１１の始端検出に応答して、
ランラベル０を読出し、読出したランラベル０をアドレ
スとして連結テーブルを参照する。連結テーブルのアド
レス０の位置にはデータ０が格納されている。したがっ
て、連結ラベルおよび連結テーブルデータがともに０で
あるため、仮ラベル選択の第１の条件に従って、隣接ラ
ンＲ１１は新しい対象物であると判断し、新しいラベル
（新ラベルカウンタの出力）を仮ラベルとして選択す
る。これに応答して新ラベルカウンタのカウント値が１
増分されて２となり、また連結ラベルはこの新しい仮ラ
ベルと同じ１となる。

【０１３２】ラベルの分岐は発生していないため、連結
テーブルの内容の変更はまだ行なわれない。

【０１３３】図６に示すように、二値マスク２４が１画
素右方向へシフトすると、隣接ランＲ１１は連続してお
り、仮ラベルレジスタから出力される仮ラベルは１を保
持する。隣接注目画素の出力ラベル値は１となる。

【０１３４】図７に示す状態において、二値マスク２４
の上段および下段の画素のデータがともに０となると、
連結ラベル記憶部に格納された連結ラベルが０にリセッ
トされる。また、隣接ランＲ１１および注目ランＲ２１
の終端は検出されていないため、新ラベルカウンタ、仮
ラベルレジスタおよびランラベル記憶部の内容は変化し
ない。

【０１３５】図８に示すように、二値マスク２４がさら
に１画素右方向にシフトすると、注目ランＲ２１および
隣接ランＲ１１の終端が検出される。注目ランＲ２１の
終端検出に応答して、仮ラベルレジスタから出力されて
いるラベル値１がこの注目ランＲ２１に対するランラベ
ルとしてランラベル記憶部に格納される。仮ラベルレジ
スタの出力するラベル値は１であるが、二値マスク２４
において、隣接注目画素のデータは０であるため、その
出力ラベル値は０である。

【０１３６】図９に示すように、二値マスク２４が隣接
ランＲ１２と注目ランＲ２２の始端に到達すると、まず
隣接ランＲ１２の始端が検出され、ランラベル記憶部か
らこの隣接ランＲ１２に付されたランラベルが読出され
る。隣接ランＲ１２に付されたランラベルは０であるた
め、この連結テーブルのアドレス０の内容が読出され
る。連結テーブルの内容は初期状態を維持しているた
め、連結テーブルデータは０である。したがって、また
仮ラベルの選択条件の第１条件に従って、新ラベルカウ
ンタのカウント値の２が仮ラベルとして選択され、連結
ラベル記憶部の格納データおよび仮ラベルレジスタの格
納データも２となる。新ラベルカウンタのラベル値が３
となる。

【０１３７】このとき、まだ隣接注目画素のデータは０
であるため、出力ラベル値は０である。注目ランＲ２２
の終端検出時に、ランラベル記憶部へこの注目ランＲ２
２に対するランラベル２が格納される。さらに、二値マ
スク２４が右方向にシフトし、注目ランＲ２３を走査す
ると、この注目ランＲ２３には隣接ランは存在しないた
め、連結ラベル記憶部に格納されたデータは、注目ラン
Ｒ２２および隣接ランＲ１２の終端時においてリセット
された０の状態となる。注目ランＲ２３の終端検出時に
このときの仮ラベルすなわちラベル値０がランラベル記
憶部に格納される。

【０１３８】次いで、注目ランＲ２４および隣接ランＲ
１３の走査時においては、隣接ランＲ１３のランラベル
３に従って連結テーブルデータ３が読出され、仮ラベル
の選択条件の第３条件に従って連結テーブルデータ３が
仮ラベルとして選択され、連結ラベル記憶部の格納デー
タも応じて３となる。注目ランＲ２４の終端検出に応答
して、ランラベル３がランラベル記憶部に格納される。

【０１３９】ランラベル記憶部の格納データは注目ラン
Ｒ２１、Ｒ２２、Ｒ２３およびＲ２４に対するラベル値
１、２、０、および３である。

【０１４０】図１０に示すように、ランＲ２１が隣接ラ
ンとして走査されると、このランＲ２１のランラベルが
ランラベル記憶部から読出される。このとき、連結ラベ
ル記憶部には０が格納されている（水平走査の帰線期間
においてリセットされる）。この隣接ランＲ２１の始端
検出に応答して、ランラベル記憶部から隣接ランＲ２１
が注目ランのときに付されたランラベル１が読出され
る。この読出されたランラベル１をアドレスとして連結
テーブルを参照すると、連結テーブルデータ１が読出さ
れる。連結ラベルが０であり、連結テーブルデータが１
であるため、仮ラベル選択の第３の条件に従って、仮ラ
ベルは１とされる。この仮ラベルレジスタに設定された
仮ラベル１はまた連結ラベル記憶部に格納され、連結ラ
ベルが１となる。これにより、ランＲ２１に付される仮
ラベルは図６４（Ｃ）に示す仮ラベル画像と同様とな
る。

【０１４１】図１１に示すように、二値マスク２４がラ
ンＲ２２を隣接ランとして走査すると、この隣接ランＲ
２２の始端検出に応答して、ランラベル記憶部からこの
隣接ランＲ２２のランラベル２が読出される。この読出
されたランラベル２をアドレスとして連結テーブルから
データを読出す。このとき連結テーブルから読出される
連結テーブルデータは２である。連結ラベル記憶部が保
持している連結ラベルは１である。この状態では、仮ラ
ベル選択の第５の条件に従って、ラベル値の小さい連結
ラベルが選択されて仮ラベル１が得られる。

【０１４２】このとき、連結ラベルとランラベルがそれ
ぞれ１および２となっており、同一対象物に対して異な
るラベルが付されている状態である。したがって、この
ときには、ラベルの分岐が発生しているため、非選択の
ランラベル２をアドレスとしかつ選択された連結ラベル
１を書込データとした書込が行なわれる。これにより、
図１２に示す連結テーブルの内容が得られる。仮ラベル
が１に設定され、連結ラベルが１となる。したがって、
隣接ランＲ２２に属する各画素に対してはラベル値１が
割付けられる（仮ラベル１が出力ラベル値として出力さ
れる）。

【０１４３】隣接ランＲ２３に対しては、隣接ランＲ１
１、Ｒ１２およびＲ１３に対して行なわれた動作と同様
の動作が行なわれる。すなわち、図１３に示すように、
まず隣接ランＲ２３の始端検出前においては、連結ラベ
ル記憶部の連結ラベルが０にリセットされる。隣接ラン
Ｒ２３の始端が検出されると、ランラベル記憶部からこ
の隣接ランＲ２３に付されたランラベル４が読出され
る。このランラベル４をアドレスとして連結テーブルを
参照すると、連結テーブルデータは４である。したがっ
て、仮ラベル選択の第３の条件に従って連結テーブルか
らのラベル値４が仮ラベルとして選択され、仮ラベルレ
ジスタ、および連結ラベル記憶部のデータが４に設定さ
れる。

【０１４４】次いで、隣接ランＲ２４の始端が検出され
ると、この隣接ランＲ２４のランラベル３が読出され
る。連結テーブルのアドレス３に格納されたデータは３
である。連結ラベルはこの隣接ラベルＲ２４の始端検出
前に０にリセットされている。したがって、この場合、
仮ラベル選択の第３の条件に従って、連結テーブルデー
タ３が仮ラベルとして選択され、仮ラベルおよび連結ラ
ベルがともに３となる。ラベルの分岐は発生していない
ため、連結テーブルの内容の変更は行なわれない。

【０１４５】隣接ランＲ３１に対しては、隣接ランＲ２
１に対して行なわれた動作と同様の動作が行なわれる。
すなわち隣接ランＲ３１の始端検出時において、ランラ
ベル記憶部からこの隣接ランＲ３１に付されたランラベ
ル１が読出される。連結テーブルのアドレス１にはデー
タ１が格納されている。連結ラベルはこのとき０であ
る。したがって、仮ラベル選択の第３の条件に従って、
連結テーブルデータ１が仮ラベルとして選択され、連結
ラベル記憶部にはデータ１が格納される。隣接ランＲ３
１の各画素に対しては仮ラベル１が付される。隣接ラン
Ｒ３１のランラベル１は、次の隣接ランＲ３２の始端が
検出されるまで保持される。

【０１４６】次いで、図１４に示すように、二値マスク
２４が隣接ランＲ３２の始端を検出すると、この始端検
出に応答してランラベル記憶部からこの隣接ランＲ３２
のランラベル４が読出される。応じて連結テーブルのア
ドレス４のデータ４が読出される。連結ラベルは、隣接
ランＲ３１のラベル値１が注目ランＲ４１を介して伝搬
されてきており、この値は１である。したがって、仮ラ
ベル選択の第５の条件に従って、値が小さい連結ラベル
１が仮ラベルとして選択される。このとき、ラベルの分
岐が発生していたので、連結テーブルのアドレス４のデ
ータ４が１に変更される。この状態を図１５に示す。

【０１４７】図１６に示すように二値マスク２４が隣接
ランＲ３３の始端を検出すると、この始端検出に応答し
て、ランラベル記憶部からこの隣接ランＲ３３のランラ
ベル４が読出される。このランラベル４を用いて、連結
テーブルを参照すると、図１５に示すように、隣接ラン
Ｒ３２で発生したラベルの分岐に伴って連結テーブルの
内容が変更されており、アドレス４の内容は１となって
いる。このとき、また、連結ラベルは、隣接ランＲ３２
および注目ランＲ４１の途切れに従って０にリセットさ
れており、連結ラベルは０である。したがって、仮ラベ
ル選択の第３の条件に従って、連結テーブルデータ１が
仮ラベルとして選択され、仮ラベルレジスタおよび連結
ラベル記憶部にはデータ１が格納される。この二値マス
ク２４が右方向へシフトすると、隣接ランＲ３３に属す
る２つの画素に対しては、出力ラベル値として仮ラベル
１が出力される。

【０１４８】図１７に示すように、二値マスク２４が隣
接ランＲ３４の始端を検出すると、ランラベル記憶部か
らこの隣接ランＲ３４に対するランラベル３が読出され
る。連結テーブルのアドレス３のデータは３である。連
結ラベルは、隣接ランＲ３３の処理時において１となっ
ている。したがって、仮ラベル選択の第５の条件に従っ
て、連結ラベル１が仮ラベルとして選択される。このと
きラベルの分岐が発生しているため、図１８に示すよう
に、連結テーブルのアドレス３の内容がデータ１に変更
される。

【０１４９】注目ランＲ４２の終端検出時において、そ
のときに発生されている仮ラベル１がこの注目ランＲ４
２のランラベルとしてランラベル記憶部に格納される。

【０１５０】図１９に示すように、二値マスク２４が隣
接ランＲ４１の始端を検出すると、ランラベル記憶部か
らこの隣接ラン４１に付されたランラベル１が読出され
る。連結テーブルのアドレス１に格納されたデータは１
であり、連結ラベルはこのときまだ０である。したがっ
て、仮ラベルの第３の選択条件に従って、連結テーブル
データ１が仮ラベルとして選択されるとともに連結ラベ
ルも１に変更される。これにより、隣接ランＲ４１の各
画素に対してラベル１が割付けられる。

【０１５１】隣接ランＲ４２に対しても同様の動作が行
なわれ、連結テーブルの参照を介してラベル値１が与え
られる。

【０１５２】最終的に１回のラスタ走査によって得られ
る仮ラベル画像は図２０に示すようになる。この図２０
に示す仮ラベル画像に対し図１８に示す連結テーブルを
用いてラベルの付け直し（リラベリング）を行なう。す
なわち、仮ラベルをアドレスとし、連結テーブルを参照
し、その連結テーブルデータで各仮ラベルを置換える。
これにより、仮ラベル２、３、および４はすべて１に変
換されるため、図２１に示すような二値画像が得られ
る。このとき、単に連結テーブルを参照して各ラベルを
その連結テーブルデータで置換しているだけである。何
ら連結テーブルにおける画素の接続関係の解析を行なっ
ていない。したがって、連結テーブルの解析を行なうこ
となくラベルの統合が実現され、１つの対象物に対し１
つのラベルのみが付された完全なラベル画像が得られ
る。

【０１５３】次に、異なる二値画像に対するラベル統合
処理動作について説明する。図２２に示すような二値画
像に対しラベリングを行なう。初期状態において、連結
テーブルは、図２３に示すように、アドレスと各アドレ
スに格納されたデータとは一致している。二値マスク２
４が二値画像の最左上端から走査を開始する。ランＲ１
１およびＲ１２が注目ランとして走査された場合、隣接
するラベリング済み隣接ランは存在しないため、各終端
においてランラベル０が与えられる。

【０１５４】ランＲ２１が注目ランとして検出される
と、応じてランＲ１１が隣接ランとして検出される。こ
の隣接ランＲ１１の検出に応答してランラベル０が読出
される。連結ラベルは０であるため、仮ラベル選択の第
１の条件に従って、この隣接ランＲ１１に対してラベル
１が仮ラベルとして付される。ランＲ２２が注目ランと
して走査されたとき、これに連結する隣接ランは存在し
ないため、この注目ランＲ２２に対してランラベル０が
与えられる。

【０１５５】ランＲ２３が注目ランとして走査されたと
き、ランＲ１２が隣接ランとして走査される。隣接ラン
Ｒ１２のランラベルは０であり、また連結ラベルも０で
ある（画素の途切れによりリセットされている）、仮ラ
ベル選択の第１の条件に従って、ラベルＲ１２に対して
は、新たなラベル２が付される。同様にして、ランＲ２
２およびＲ３２が隣接ランとして走査された場合には、
それぞれ仮ラベル３および４が付される。

【０１５６】二値マスク２４がランＲ３３を走査する
と、このランＲ３３に付されたランラベル３が読出され
る。このランラベル３を用いて連結テーブルを参照する
と、連結テーブルはまだその内容の変更を受けていない
ため、連結テーブルデータは３である。連結ラベルは０
であるため、仮ラベル選択の第３の条件に従って、この
隣接ランＲ３３の仮ラベルは３に決定され、また連結ラ
ベルも３となる。

【０１５７】次いで、図２４（Ａ）に示すように、二値
マスク２４が隣接ランＲ３４の始端を検出する。この隣
接ランＲ３４のランラベルとして、ランＲ１２（または
画素（二値画像データ）（１，１１））を起点としたラ
ベル値２が伝搬してきている。連結テーブルは初期状態
のままであるため、連結テーブルデータが２、連結ラベ
ルは３である。したがって、仮ラベル選択の第５の条件
に従って、ラベル値の小さい連結テーブルデータが仮ラ
ベルとして選択され、仮ラベル＝連結ラベル＝２とな
る。またラベルの分岐が発生しているため、このラベル
の分岐を連結テーブルに記述すると、図２４（Ｂ）に示
すように、連結テーブルのアドレス３のデータが２に変
更される。注目ランＲ４３の終端において、この仮ラベ
ル２が注目ランＲ４３のランラベルとして記憶される。

【０１５８】二値マスク２４が隣接ランＲ４２の始端を
検出すると、この隣接ランＲ４２のランラベルは４であ
り、連結テーブルデータは４、連結ラベルが０であるた
め、仮ラベル選択の第３の条件に従って仮ラベルおよび
連結ラベルはともに４となる。

【０１５９】次いで、図２５（Ａ）に示すように、二値
マスク２４が隣接ランＲ４３の始端を検出すると、これ
に応答して隣接ランＲ４３のランラベル２が読出され
る。連結テーブルのアドレス２のデータは２であるた
め、小さい方の連結テーブルデータ２が仮ラベルとして
選択され、連結ラベル４はまた２へ変更される。このと
きまたラベルの分岐が発生しているため、連結テーブル
のアドレス４のデータは、図２５（Ｂ）に示すように２
に変更される。注目ランＲ５２の終端において、この注
目ランＲ５２に対しランラベル２が与えられる。

【０１６０】二値マスク２４が隣接ランＲ５１の始端を
検出すると、この隣接ランＲ５１へは、ランＲ１１また
は（画素Ｐ（１，２））を起点としたラベル値１が伝搬
してきており、そのランラベルは１である。連結テーブ
ルデータが１、かつ連結ラベルは０であるため、したが
って、仮ラベルの選択の第３の条件に従って、仮ラベル
＝連結ラベル＝１となる。

【０１６１】図２６（Ａ）に示すように、二値マスク２
４が隣接ランＲ５２の始端を検出すると、この隣接ラン
Ｒ５２が注目ランであったときに付されたランラベル２
が読出される。連結テーブルのアドレス２のデータは２
であるため、連結テーブルデータが２、連結ラベルが１
であり、したがって、仮ラベル選択の第５の条件に従っ
て、仮ラベル＝連結ラベル＝１となる。このとき連結テ
ーブルは図２６（Ｂ）に示すように、アドレス２のデー
タが１に変更される。注目ランＲ６１の終端において、
仮ラベル１がこの注目ランＲ６１のランラベルとして記
憶される。隣接ランＲ５２に対しては、その終端が検出
されるまで、各画素に対して仮ラベル１が割付けられ
る。

【０１６２】ランＲ６１が隣接ランとして走査される
と、注目ランのときに与えられたランラベル１が仮ラベ
ルとして選択され（連結テーブルデータ＝１かつ連結ラ
ベル１）、このランＲ６１の各画素に対しては仮ラベル
１が割付けられる。

【０１６３】二値マスク２４の走査が終了した時点にお
ける仮ラベル画像における各画素のラベルは図２７に示
すようになる。すなわち、ランＲ１１、Ｒ２１、Ｒ３
１、Ｒ４１、Ｒ５１の各画素にはラベル１が付され、ラ
ンＲ１２、Ｒ２３、Ｒ３４およびＲ４３の各画素にはラ
ベル２が付され、ランＲ２２およびＲ３３の各画素には
ラベル３が付され、ランＲ３２およびＲ４２の各画素に
はラベル４が付され、ランＲ５２およびＲ６１の各画素
にはラベル１が付される。また連結テーブルの内容とし
ては、図２６（Ｂ）に示すように、アドレス０、１、
２、３、および４に対し、データ０、１、１、２および
２がそれぞれ格納されている。

【０１６４】この図２６（Ｂ）に示す連結テーブルの内
容を解析すると、仮ラベル２が仮ラベル１に連結し、仮
ラベル３が仮ラベル２に連結し、また仮ラベル４が仮ラ
ベル２に連結しているのは容易に識別することができ
る。すなわち、仮ラベル１ないし４は同一対象物に付さ
れた仮ラベルであり、この各仮ラベルが付された画素は
連結された同一対象物を構成することが容易に識別する
ことができる。したがって、この図２６（Ｂ）に示す連
結テーブルの内容においてはラベルの分離／分岐は何ら
発生していないため、容易にそのテーブル内容を解析し
て図２８に示すように、ラベル統合処理（テーブル解
析）においては、これらの仮ラベルをすべて１に変更す
ることが可能となる。

【０１６５】この図２８に示す連結テーブルをルックア
ップテーブルとして利用して図２７に示す仮ラベル画像
のラベルの付け直しを行なうと、図２９に示すように、
すべての画素に対してラベル値１を割当てることがで
き、１つの対象物に対し１つのラベルのみが付されたラ
ベリングの最終結果画像を容易に得ることができる。

【０１６６】以上のように、この発明の第１の実施例に
おけるラベリング方式においては、隣接ランの始端時に
生成されるランラベルを用いて連結テーブルを参照し、
そのときの連結ラベルと連結テーブルデータとに従って
仮ラベルを決定しているため、ラベル分岐が発生する頻
度を大幅に抑制することができ、容易に画素間の連結関
係を識別してリラベリングを行なうことが可能となる。

【０１６７】（ii） 第２の実施例 図３０はこの発明の第２の実施例であるラベリング回路
の具体的構成を示す図である。図３０において、ラベリ
ング回路は、二値画像をラスタ走査して得られる二値画
像データ系列を１画素ずつクロック信号に応答して入力
し、２行３列の二値マスクを生成するマスク構成部１
と、注目ランのランラベルを格納し、該注目ランが隣接
ラベルとして検出されたときに対応のランラベルを出力
するランラベル記憶部５と、隣接ランの始端検出時に仮
ラベルを連結ラベルとしてラッチする連結ラベル記憶部
７と、ランラベル記憶部５の書込を制御するランラベル
記憶制御部６と、ラベル分岐発生時に連結ラベルおよび
連結テーブルデータを選択的に出力する統合ラベル送出
部３と、この統合ラベル送出部３から与えられたラベル
値を連結テーブル内に格納する統合処理部４と、連結テ
ーブルデータと連結ラベルとに従って隣接ラベルの始端
検出時に仮ラベルを決定する仮ラベル決定部２を含む。

【０１６８】ランラベル記憶部５はＦＩＦＯ構成を備
え、その出力は統合ラベル送出部３へのみ与えられる。
ランラベル記憶制御部６は、注目ランの終端検出時に仮
ラベルをランラベル記憶部５へ書込む。また、注目ラン
の始端検出時において、二値マスク内の隣接行（上段）
の画素すべてのデータが０の場合には仮ラベルを０に設
定する。連結ラベル記憶部７は、隣接ランの始端検出に
応答して、決定された仮ラベルを連結ラベルとして格納
する。この連結ラベル記憶部７は、また二値マスク内に
おいて上段および下段の画素データがともに０となった
ときにリセットされる。連結レベル記憶部７が出力する
連結レベルはまた統合ラベル送出部３へ与えられる。

【０１６９】統合ラベル送出部３は、仮ラベル決定部２
に含まれる仮ラベル選択制御部１３からの制御信号に従
って統合処理部４に含まれる連結テーブルへのアクセス
（連結ラベルデータの書込および読出）を実行する。統
合処理部４はランラベル決定部２に含まれるランラベル
読出制御部１２からの読出制御信号に応答して、ランラ
ベル記憶部５から統合ラベル送出部３を介して与えられ
るランラベルをアドレスとして連結テーブルデータを読
出し、この読出した連結テーブルデータを仮ラベルセレ
クタ１４（仮データ決定部２に含まれる）および仮ラベ
ル選択制御部１３へ与える。

【０１７０】統合処理部４に含まれる連結テーブルはｎ
ビット・２ⁿ ワード構成となっており、その初期状態に
おいては、図２３に示すようにアドレス値と同じ値がデ
ータとして格納されている。

【０１７１】ランラベル読出制御部１２は、隣接ランの
始端を検出し、該隣接ランの始端検出時に読出指示信号
をランラベル記憶部５および統合処理部４へ与える。

【０１７２】仮ラベル選択制御部１３は、隣接ランの始
端検出時において、前述の仮ラベル選択の５条件に従っ
て仮ラベルを決定し、該決定結果に従った制御信号を仮
ラベルセレクタ１４へ与える。

【０１７３】仮ラベルセレクタ１４は、この仮ラベル選
択制御部１３からの制御信号に従って、連結ラベル記憶
部７からの連結ラベル、新ラベルカウンタ１８からのカ
ウント値および統合処理部４からの連結テーブルデータ
のいずれかを選択して仮ラベルレジスタ１５へ与える。
新ラベルカウンタ１８は、そのカウント値が仮ラベルと
して選択されたとき、仮ラベル選択制御部１３からの制
御信号に応答してそのカウント値が１増分される。新ラ
ベルカウンタ１８のカウント値が仮ラベルとして選択さ
れるのはラベル分岐発生時（仮ラベル選択の第５条件）
のときである。

【０１７４】仮ラベルレジスタ１５は、この仮ラベルセ
レクタ１４の出力するラベル値を仮ラベルとしてラッチ
する。仮ラベルレジスタ１５はまた、ランラベル記憶制
御部６が注目ラン始端を検出しかつこの二値マスクの上
段の画素データがすべて０のとき０にリセットされる。
仮ラベルレジスタ１５の出力する仮ラベルは仮ラベル送
出部１６へ与えられる。仮ラベル送出部１６は、仮ラベ
ルレジスタ１５からの仮ラベルと固定値０の一方を仮ラ
ベル送出制御部１７の制御の下に選択して出力ラベル値
を生成して出力する。この仮ラベル送出部１６から出力
されるラベル値が図示しない仮ラベル画像メモリに格納
される。

【０１７５】仮ラベル送出制御部１７は、ラベル付対象
画素である隣接注目画素のデータ値に従って仮ラベルレ
ジスタ１５の出力する仮ラベルと固定値０の一方を指定
する信号を仮ラベル送出部１６へ与える。次に動作につ
いて説明する。

【０１７６】二値画像データＰ（ｉ，ｊ＋１）が入力さ
れると、次のクロックサイクルで、二値画像データＰ
（ｉ，ｊ＋１）、Ｐ（ｉ，ｊ）、Ｐ（ｉ，ｊ−１）、Ｐ
（ｉ−１，ｊ＋１）、Ｐ（ｉ−１，ｊ）、およびＰ（ｉ
−１，ｊ−１）の２行２列の局所画像領域からなる二値
マスクがマスク構成部１から出力される。ランラベル読
出制御部１２は、この二値マスクを受け、隣接ランの始
端（Ｐ（ｉ−１，ｊ）＝０かつＰ（ｉ−１，ｊ＋１）＝
１）を検出すると、読出制御信号をランラベル記憶部５
および統合処理部４へ与える。

【０１７７】ランラベル記憶部５は、ＦＩＦＯ構成であ
るため、記憶しているデータのうちのまだ読出されてい
ないもののうち一番最初に記憶したランラベルデータを
統合ラベル送出部３に出力する。統合ラベル送出部３
は、このときまだ仮ラベル選択制御部１３からは書込指
示信号が与えられていないため、このランラベル記憶部
５から与えられたランラベルをアドレスとして統合処理
部４へ与える。統合処理部４は、この統合ラベル送出部
３から与えられたランラベルをアドレスとして内部の連
結テーブルをアクセスし、データを読出し、該読出した
データを仮ラベル選択制御部１３へ伝達する。

【０１７８】仮ラベル選択制御部１３は、連結ラベル記
憶部７が出力する連結ラベル（ｎビット）とこの統合処
理部４から伝達された連結テーブルデータ（ｎビット）
とを受け、その値および大小関係を検査する。仮ラベル
選択制御部１３は、この検査結果により、仮ラベル選択
の５条件のうちのいずれが適用されるべきかを決定し、
仮ラベルとして選択すべきラベルを選択するための制御
信号を仮ラベルセレクタ１４へ与える。

【０１７９】仮ラベル選択制御部１３は、仮ラベル選択
の第５条件に該当した場合には、ラベル分岐が発生して
いるため、統合処理部４に渡すべきデータの選択を行な
うための制御信号を統合ラベル送出部３へ出力する。

【０１８０】統合ラベル送出部３へは、この仮ラベル選
択制御部１３へ与えられた連結ラベルと連結テーブルデ
ータとが与えられている。統合ラベル送出部３は、この
仮ラベル選択制御部１３からの選択制御信号に従って、
仮ラベルとして選択されたラベル値を書込データとし、
非選択のラベル値をアドレスとして統合処理部４へ転送
し、連結テーブルに対するデータの書込を行なう。すな
わち、連結テーブルデータの方が連結ラベルより大きい
場合には、連結テーブルデータがアドレス、連結ラベル
が書込データとされ、逆に、連結ラベルが連結テーブル
データより大きい場合には、連結ラベルがアドレス、連
結テーブルデータが書込データとして連結テーブルへの
書込が行なわれる。

【０１８１】仮ラベルセレクタ１４は、この仮ラベル選
択制御部１３からの選択制御信号に従って、連結ラベル
記憶部７からの連結ラベル、新ラベルカウンタ１８から
の新ラベルおよび連結テーブルデータのうちのいずれか
を選択して仮ラベルレジスタ１５へ伝達する。仮ラベル
セレクタ１４の出力データが確定し、かつラベル分岐発
生時において統合処理部４に含まれる連結テーブルへの
データ書込が完了した後、連結ラベル記憶部７は、この
仮ラベルセレクタ１４が出力する仮ラベルをラッチし出
力する。これにより、ラベル分岐発生時においても確実
に連結ラベルの変更を行なうことができる。連結テーブ
ルの変更には、変更前の連結ラベルを用いるためであ
る。

【０１８２】仮ラベル送出制御部１７は、隣接注目画素
（Ｐ（ｉ−１，ｊ））の値に従って、仮ラベルレジスタ
１５の出力する仮ラベルおよび固定値０の一方を選択す
る信号を仮ラベル送出部１６へ与える。仮ラベル送出部
１６は、この仮ラベル送出制御部１７からの送出制御信
号に従って出力ラベル値を選択して出力する。

【０１８３】ランラベル記憶制御部６は注目ランの終端
（Ｐ（ｉ，ｊ−１）＝１かつＰ（ｉ，ｊ）＝０）を検出
すると、書込指示信号をランラベル記憶部５へ与える。
ランラベル記憶部５は、この書込指示信号に従って仮ラ
ベルレジスタ１５が出力する仮ラベルを格納する。これ
によりこの注目ランに対するランラベルが格納される。

【０１８４】上述のような回路構成で二値画像に対しラ
ベリングを行なうことにより、同一対象物に対し異なる
ラベルを付けるラベル分岐の発生頻度が大幅に減少し、
ラベル統合処理において仮ラベル画像を必要とすること
なく連結テーブルのみを用いてラベルの連結関係を検出
することができ高速でラベル統合処理を実行することが
できる。次に各部の構成について説明する。

【０１８５】図３１は、図３０に示すランラベル記憶制
御部６の構成の一例を示す図である。図３１において、
ランラベル記憶制御部６は、二値画像データＰ（ｉ，
ｊ）と二値画像データＰ（ｉ，ｊ−１）とを受ける２入
力ゲート回路６１と、二値画像データＰ（ｉ，ｊ）、Ｐ
（ｉ−１，ｊ＋１）、Ｐ（ｉ−１，ｊ）、およびＰ（ｉ
−１，ｊ−１）を受ける４入力ゲート回路６２を含む。

【０１８６】ゲート回路６１は、二値画像データＰ
（ｉ，ｊ）が０でありかつ二値画像データＰ（ｉ，ｊ−
１）が１のときに“１”の信号を出力する。このゲート
回路６１の出力はランラベル記憶部５へ書込指示信号
（ライト信号）として与えられる。ここで、二値画像デ
ータ０および１をそれぞれ論理０および１に対応させて
いる。

【０１８７】ゲート回路６２は、二値画像データＰ
（ｉ，ｊ）が１でありかつ二値画像データＰ（ｉ−１，
ｊ＋１）、Ｐ（ｉ−１，ｊ）およびＰ（ｉ−１，ｊ−
１）が全て０のときに論理１のリセット信号を発生す
る。このゲート回路６２からのリセット信号が仮ラベル
レジスタ１５へ与えられる。

【０１８８】この構成により、注目ランの終端検出時に
ランラベル記憶部へのランラベル記憶が行なわれ、また
注目画素に対し隣接ランが存在しない場合には、仮ラベ
ルレジスタを０にリセットして、隣接注目画素（ラベル
付け対象画素）のラベルを０に設定することができる。

【０１８９】図３２は図３０に示すランラベル読出制御
部の構成の一例を示す図である。図３２において、ラン
ラベル読出制御部１２は、二値画像データＰ（ｉ−１，
ｊ）およびＰ（ｉ−１，ｊ＋１）を受ける２入力ゲート
回路１２０を含む。ゲート回路１２０は、二値画像デー
タＰ（ｉ−１，ｊ）が０でありかつ二値画像データＰ
（ｉ−１，ｊ＋１）が１のときにリード信号を１とす
る。このゲート回路１２０からのリード信号はランラベ
ル記憶部５へ与えられる。これにより、隣接ランの始端
検出時にこの隣接ランのランラベルをランラベル記憶部
から読出すことができまた統合処理部の連結テーブルの
データを読出すことができる。

【０１９０】図３３は図３０に示す連結ラベル記憶部の
構成の一例を示す図である。図３３において、連結ラベ
ル記憶部７は、二値画像データＰ（ｉ，ｊ＋１）および
Ｐ（ｉ−１，ｊ＋１）を受ける２入力ゲート回路７１
と、二値画像データＰ（ｉ−１，ｊ）およびＰ（ｉ−
１，ｊ＋１）を受ける２入力ゲート回路７２と、ゲート
回路７２の出力を所定時間遅延させる遅延回路７３と、
遅延回路７３の出力に応答して仮ラベルセレクタが出力
する仮ラベルをラッチしかつゲート回路７１の出力に応
答してその内容がリセットされるラッチ回路７０を含
む。

【０１９１】ゲート回路７１は、二値画像データＰ
（ｉ，ｊ＋１）およびＰ（ｉ−１，ｊ＋１）がともに０
のときに１の信号を発生する。これにより、ラッチ回路
７０は二値マスクにおいて上段および下段の画素がとも
に０となったときにリセットされ、注目ランおよび隣接
ランの途切れ部において連結ラベルを０に設定すること
ができ、連結ラベルの伝搬を防止することができる。

【０１９２】ゲート回路７２は、二値画像データＰ（ｉ
−１，ｊ）が０でありかつ二値画像データＰ（ｉ−１，
ｊ＋１）が１のときに１の信号を出力する。遅延回路７
３は、仮ラベルセレクタ出力が確定した後にラッチ動作
を行なうために設けられる。すなわち、仮ラベル選択の
５条件に従って仮ラベルが決定されるが、この仮ラベル
の決定後に連結ラベルの値も決定される。この決定され
た仮ラベルを連結ラベルとして確実にラッチするために
遅延回路７３が設けられる。隣接ランの始端検出時に確
実に正確なランラベルを保持することでがきる。

【０１９３】図３４は、図３０に示す仮ラベル送出制御
部１７の構成を示す図である。図３４において、仮ラベ
ル送出制御部１７は、二値画像データＰ（ｉ−１，ｊ）
を受ける２段の縦続接続されたインバータ回路１７１お
よび１７２を含む。インバータ回路１７１から制御信号
φＢが発生され、インバータ回路１７２から制御信号φ
Ａが発生される。このインバータ回路１７１および１７
２は遅延機能をも備えており、仮ラベルセレクタにより
仮ラベルが決定し、かつ仮ラベルレジスタ１５において
仮ラベルが格納された後に仮ラベル送出部１６が仮ラベ
ルを選択して出力するようなタイミングで制御信号φＡ
およびφＢを発生する。

【０１９４】図３５は、図３０に示す仮ラベル送出部１
６の構成を示す図である。図３５においては、仮ラベル
送出部１６の構成のうち１ビットに関連する構成を示
す。図３５に示す構成がｎビット並列に設けられる。図
３５において、仮ラベル送出部１６は、図３４に示す仮
ラベル送出制御部１７から与えられる制御信号φＡおよ
びφＢに応答して選択的にイネーブル状態とされる３状
態バッファ１６１および１６２を含む。３状態バッファ
１６１はデータビット０を受け、３状態バッファ１６２
は仮ラベルレジスタ１５から与えられる仮ラベルを受け
る。制御信号φＡが０でありかつ制御信号φＢが１のと
き、３状態バッファ１６１がイネーブル状態とされる。
制御信号φＡが１でありかつ制御信号φＢが０のときに
３状態バッファ１６２がイネーブル状態とされる。３状
態バッファ１６１および１６２は、ディスエーブル状態
のときには出力ハイインピーダンス状態となる。

【０１９５】この図３５に示すような仮ラベル送出部１
６を利用することにより、隣接注目画素の値に従って仮
ラベルデータまたは固定データの一方を選択的に出力す
ることができる。この図３５に示す３状態バッファ１６
１および１６２は、ＣＭＯＳトランスミッションゲート
などの構成要素で置換えてもよい。

【０１９６】図３６は、図３０に示す統合処理部４に含
まれる連結テーブルの構成を示す図である。図３６にお
いて、連結テーブルはランダムなシーケンスでデータの
書込および読出を行なうことができるＲＡＭ（ランダム
・アクセス・メモリ）４１を備える。このＲＡＭ４１
は、ｎビット幅のアドレス入力ＡＤＤと、ｎビット幅の
データ入力ＤＡＴと、リードおよびライト指示信号を各
々受けるリード入力ＯＥおよびライト入力／ＷＥを含
む。リードおよびライト入力ＯＥおよび／ＷＥは、１お
よび０の信号が各々与えられたときにデータ読出状態お
よびデータ書込状態となる。このＲＡＭ４１は、データ
の書込および読出を行なうことのできるメモリであれば
よく、レジスタファイル、ＤＲＡＭ（ダイナミック型・
ランダム・アクセス・メモリ）およびＳＲＡＭ（スタテ
ィック・ランダム・アクセス・メモリ）などの任意のメ
モリを用いるこどかできる。ＲＡＭ４１の初期設定時に
おいては、アドレス値と各アドレスに格納されるデータ
とは等しい。この初期設定のためには、図示しないｎビ
ットのカウンタを利用し、このカウンタ出力をアドレス
入力ＡＤＤおよびデータ入力ＤＡＴへ与え、順次カウン
ト値をインクリメントすることによりデータの書込が行
なわれる。

【０１９７】統合処理部４は、この連結テーブルすなわ
ちＲＡＭ４１の内容を読出しそのテーブル解析を行なっ
て仮ラベル画像のラベル統合処理を行なう処理装置を含
んでいる。しかしながら、この部分は図面には示してい
ない。

【０１９８】図３７は、図３０に示す統合ラベル送出部
の構成の一例およびその論理を一覧にして示す図であ
る。図３７（Ａ）において、統合ラベル送出部３は、後
に説明する制御信号φ０およびφ１（仮ラベル選択制御
部１３から与えられる）を受ける２入力ゲート回路３
１、３２および３３と、制御信号φ１を反転するインバ
ータ回路３４と、ゲート回路３１の出力に応答してラン
ラベルデータを連結テーブルのアドレスバス上へ伝達す
るスイッチング要素３５と、ゲート回路３２の出力に応
答して連結ラベルデータをアドレスバスＡＤＤ上へ伝達
するスイッチング要素３６と、ゲート回路３３の出力に
応答して連結テーブルデータをアドレスバスＡＤＤ上へ
伝達するスイッチング要素３７と、ゲート回路３３の出
力に応答して、連結ラベルデータを連結テーブルのデー
タバス（データ入力）ＤＡＴへ伝達するスイッチング要
素３８と、ゲート回路３２の出力に応答して連結テーブ
ルデータをデータバスＤＡＴ上へ伝達するスイッチング
要素３９を含む。

【０１９９】ゲート回路３１は、制御信号φ０およびφ
１がともに０のときに１の信号を出力する。ゲート回路
３２は、制御信号φ１が１であり、制御信号φ０が０の
ときに１の信号を出力する。ゲート回路３３は制御信号
φ０およびφ１がともに１のときに１の信号を出力す
る。インバータ回路３４の出力／φ１は連結テーブル
（ＲＡＭ４１）の書込指示入力（／ＷＥ）へ与えられ
る。

【０２００】スイッチング要素３５〜３９はそれぞれｎ
チャネルＭＯＳトランジスタで構成されるように示さ
れ、“１”の信号が制御電極に与えられたときに導通状
態となる。次にその動作を図３７（Ｂ）を参照して説明
する。

【０２０１】制御信号φ１およびφ０がともに０のとき
には、ゲート回路３１の出力が１となり、スイッチング
要素３５が導通して、ランラベルがアドレスバスＡＤＤ
上へ伝達される。このとき、図３０に示すランラベル読
出制御部１２からリード信号がＲＡＭ４１の出力イネー
ブル入力ＯＥへ与えられ、このランラベルをアドレスし
たデータの読出が行なわれる。このとき、スイッチング
要素３６〜３９は、ゲート回路３２および３３の出力が
０であるため、非導通状態である。

【０２０２】制御信号φ１が１でありかつ前記信号φ０
が０のときには、ゲート回路３２の出力が１となる。こ
の状態では、スイッチング要素３６および３９が導通状
態となり、連結ラベルデータがアドレスバスＡＤＤ上へ
与えられ、連結テーブルデータがデータバスＤＡＴ上へ
伝達される。インバータ回路３４から発生される制御信
号／φ１が０となり、ＲＡＭ４１のライトイネーブル入
力／ＷＥは活性状態となり、ＲＡＭ４１が書込状態とな
る。これにより、連結ラベルデータをアドレスとし、連
結テーブルデータを書込データとしたデータの書込が行
なわれ、連結テーブルの内容の変更が行なわれる。

【０２０３】制御信号φ１およびφ０がともに１の場合
には、ゲート回路３３の出力が１となり、スイッチング
要素３７および３８が導通状態となる。この状態では、
連結テーブルデータがアドレスバスＡＤＤ上へ伝達さ
れ、連結ラベルデータがデータバスＤＡＴ上へ伝達され
る。このときまた制御信号／φ１が０であるため、連結
テーブルデータをアドレスとし、連結ラベルを書込デー
タとするデータの書込が連結テーブル（ＲＡＭ４１）に
対して実行される。

【０２０４】制御信号φ１が０であり、制御信号φ１が
１の場合には、ゲート回路３１、３２および３３の出力
が０となり、スイッチング要素３５〜３９はすべて非導
通状態となり、アドレスバスＡＤＤおよびデータバスＤ
ＡＴはハイインピーダンス状態（Ｚ）となる。

【０２０５】上述のような構成により、ラベル分岐が発
生したとき（仮ラベル選択の第５条件が成立したと
き）、小さい方のラベル値を書込データとし、大きい方
のラベル値をアドレスとするデータの書込を連結テーブ
ル（ＲＡＭ４１）に対して行なうことができる。

【０２０６】なお図３７（Ａ）に示すスイッチング要素
３５〜３９は、ＣＭＯＳトランスミッションゲート、ま
たは３状態バッファで置換えられてもよい。

【０２０７】図３８は図３０に示す仮ラベル選択制御部
の構成の一例を示す図である。図３８において、仮ラベ
ル選択制御部１３は、二値画像データＰ（ｉ−１，ｊ）
およびＰ（ｉ−１，ｊ＋１）を受ける２入力ゲート回路
１３０を含む。ゲート回路１３０は、二値画像データＰ
（ｉ−１，ｊ）が０でありかつＰ（ｉ−１，ｊ＋１）が
１のときに１の信号を出力する。すなわち、ゲート回路
１３０は隣接ランの始端を検出する。このゲート回路１
３０の出力が１となると仮ラベル選択制御部１３はイネ
ーブル状態とされ、以下に説明する各構成要素が動作可
能状態となる。

【０２０８】仮ラベル選択制御部１３はさらに、連結ラ
ベルと固定データ０の一致を検出する一致検出回路１３
７ａと、連結テーブルデータと固定データ０の一致を検
出する一致検出回路１３７ｂと、一致検出回路１３７ａ
および１３７ｂの出力を受ける２入力ゲート回路１３１
と、連結テーブルデータと固定データ０の一致を検出す
る一致検出回路１３７ｃと、連結ラベルデータと固定デ
ータ０の不一致を検出する不一致検出回路１３８ａと、
一致検出回路１３７ｃの出力と不一致検出回路１３８ａ
の出力を受ける２入力ゲート回路１３２と、連結テーブ
ルデータと固定データ０の不一致を検出する不一致検出
回路１３８ｂと、連結ラベルデータと固定データ０との
一致を検出する一致検出回路１３７ｄと、不一致検出回
路１３８ｂの出力と一致検出回路１３７ｄの出力を受け
る２入力ゲート回路１３３を含む。

【０２０９】一致検出回路１３７ａ〜１３７ｄは、その
両入力のデータ値が一致した場合に１の信号を出力す
る。不一致検出回路１３８ａおよび１３８ｂは、その両
入力に与えられたデータが不一致の場合に１の信号を出
力する。ゲート回路１３１〜１３３はその両入力がとも
に１のときに１の信号を出力する。ゲート回路１３１か
ら新ラベルカウンタを選択するための制御信号φＣ１が
発生され、ゲート回路１３２から連結ラベルを選択する
ための制御信号φＣ２が発生され、ゲート回路１３３か
ら連結ラベルデータを選択するための制御信号φＣ３が
発生される。

【０２１０】すなわち、ゲート回路１３１は、仮ラベル
選択の第１の条件（連結ラベル＝連結テーブルデータ＝
０）が成立したときに制御信号φＣ１を１とする。

【０２１１】ゲート回路１３２は、仮ラベル選択の第２
条件（連結テーブルデータ＝０かつ連結ラベルデータ≠
０）が成立したときに制御信号φＣ２を１とする。ゲー
ト回路１３３は、仮ラベル決定の第３条件（連結テーブ
ルデータ≠０かつ連結レベル＝０）が成立したときに制
御信号φＣ３を１とする。

【０２１２】仮ラベル選択制御部１３はさらに、連結ラ
ベルと連結テーブルデータの一致を検出する一致検出回
路１３７ｅと、連結テーブルデータと固定データの不一
致を検出する不一致検出回路１３８ｃと、連結ラベルデ
ータと固定データ０の不一致を検出する不一致検出回路
１３８ｄと、一致検出回路１３７ｅ、不一致検出回路１
３８ｃおよび１３８ｄの各出力を受ける３入力ゲート回
路１３４と、連結ラベルと連結テーブルデータの不一致
を検出する不一致検出回路１３８ｅと、連結テーブルデ
ータと固定データ０との不一致を検出する不一致検出回
路１３８ｆと、連結ラベルと固定データ０の不一致を検
出する不一致検出回路１３８ｇと、不一致検出回路１３
８ｅ、１３８ｆおよび１３８ｇの各出力を受ける３入力
ゲート回路１３５と、ゲート回路１３５の出力に応答し
て活性化され、連結ラベルと連結テーブルデータの大小
を比較する比較器１３６を含む。

【０２１３】一致検出回路１３７ｅはその与えられたデ
ータ値が一致すると１の信号を出力する。不一致検出回
路１３８ｃ〜１３８ｇの各々は、それぞれ与えられたデ
ータが不一致の場合には１の信号を出力する。ゲート回
路１３４および１３５は、それぞれ、与えれらる３入力
がともに１のときに１の信号を出力する。比較器１３６
は、連結テーブルデータの値が連結ラベルの値よりも大
きいときに１の信号を出力する。

【０２１４】ゲート回路１３４は、仮ラベル決定の第４
の条件（連結テーブルデータ≠０、連結ラベル≠０かつ
連結テーブルデータ＝連結ラベル）が成立したときに制
御信号φＣ４を１とする。この仮ラベル決定の第４の条
件が成立した場合には、連結テーブルデータと連結ラベ
ルの一方が選択されるが、図３８においては、連結テー
ブルデータが選択されるように示される。

【０２１５】ゲート回路１３５は、仮ラベル決定の第５
の条件（連結テーブルデータ≠０、連結ラベル≠０、か
つ連結テーブルデータ≠連結ラベル）が成立したときに
制御信号φＣ５を１とする。比較回路１３６はこのとき
活性化され、比較動作を行ない、連結テーブルデータが
連結ラベルよりも大きい場合には制御信号φＣ５′を１
とし、そうでない場合には制御信号φＣ５′を０とす
る。この制御信号φＣ５およびφＣ５′が図３７に示す
制御信号φ１およびφ０として統合ラベル送出部３へ与
えられる。ここで、図３７（Ｂ）においては、制御信号
（φ１，φ０）が（０，１）のとき、統合ラベル送出部
３は出力ハイインピーダンス状態となるように示されて
いる。この状態では、図３８に示す比較回路１３６は不
動作状態（ディスエーブル状態）である。したがって、
比較回路１３６は、ディスエーブル状態ではその出力φ
Ｃ５′を１にプルアップする。

【０２１６】図３８に示す構成は、仮ラベル決定の５条
件の各条件に対応して構成要素が設けられている。いく
つかの構成要素は同一の動作を行なっており、これらの
構成要素を共有することにより構成要素数の少ない効率
的な回路が実現される。

【０２１７】図３９は、図３０に示す仮ラベルセレクタ
の具体的構成の一例を示す図である。図３９において、
仮ラベルセレクタ１４は、制御信号φＣ５（φ１）およ
びφＣ５′（φ０）を受ける２入力ゲート回路１４１
と、ゲート回路１４１の出力と制御信号φＣ３、φＣ４
とを受けるゲート回路１４２と、制御信号φＣ５（φ
１）およびφＣ５′（φ０）を受ける２入力ゲート回路
１４３と、ゲート回路１４３の出力と制御信号φＣ２を
受けるゲート回路１４４と、ゲート回路１４２の出力に
応答して導通して連結テーブルデータを通過させるスイ
ッチング要素１４６と、制御信号φＣ１に応答して導通
して新ラベルカウンタの出力を通過させるスイッチング
要素１４７と、ゲート回路１４４の出力に応答して導通
して連結ラベルを通過させるスイッチング要素１４８を
含む。

【０２１８】ゲート回路１４１は、制御信号φＣ５（φ
１）が１でありかつ制御信号φＣ５′（φ０）が０のと
きに１の信号を出力する。ゲート回路１４２はゲート回
路１４１の出力、制御信号φＣ３、および制御信号φＣ
４のいずれか１つが１となったときに１の信号を出力す
る。スイッチング要素１４６は、ゲート回路１４２の出
力が１のときに導通する。すなわち、仮ラベル決定の第
３ないし第５の条件のいずれかが成立したときには連結
テーブルデータが選択されて仮ラベルとして仮ラベルレ
ジスタへ伝達される。

【０２１９】スイッチング要素１４７は制御信号φＣ１
が１のとき導通する。すなわち、仮ラベル決定の第１の
条件が成立したときには新ラベルカウンタの出力が仮ラ
ベルとして選択されて仮ラベルレジスタへ伝達される。

【０２２０】ゲート回路１４３は、制御信号φＣ５（φ
１）およびφＣ５′（φ０）がともに１のときに１の信
号を出力する。ゲート回路１４４はゲート回路１４３の
出力と制御信号φＣ２の一方が１のときに１の信号を出
力する。スイッチング要素１４８はこのゲート回路１４
４の出力が１のときに導通する。したがって、連結ラベ
ルは仮ラベル決定の第２の条件または第５の条件が成立
したときに選択される。

【０２２１】仮ラベル決定の第５の条件成立時におい
て、連結テーブルデータと連結ラベルのいずれが選択さ
れるかは、制御信号φＣ５（φ１）およびφＣ５′（φ
０）の値により決定される。連結テーブルデータの値が
連結ラベルの値よりも大きい場合には制御信号φＣ５′
（φ０）が１となり、連結ラベルがスイッチング要素１
４８を介して仮ラベルとして仮ラベルレジスタへ伝達さ
れる。連結テーブルデータが連結ラベルよりも小さい場
合には、制御信号φＣ５′（φ０）が０となるため、連
結テーブルデータがスイッチング要素１４６を介して仮
ラベルとして仮ラベルレジスタへ伝達される。

【０２２２】この図３９に示す構成において、ゲート回
路１４１〜１４４は仮ラベル選択制御部１３に含まれて
もよい。

【０２２３】この図３１ないし図３９に示す回路の構成
は単なる一例であり、同じ論理を実現する回路構成であ
ればいずれの回路構成が用いられてもよい。

【０２２４】新ラベルカウンタ１８は、単に制御信号φ
ＣＡ１に応答してそのカウント値がインクリメントされ
るため、通常の２進ｎビットカウンタを用いて構成する
ことができる。また仮ラベルレジスタ１５は、通常のリ
セット機能付ラッチ回路で構成され、仮ラベルセレクタ
１４の出力確定後その出力をラッチする。

【０２２５】以上のように、この第２の実施例に従え
ば、隣接ランの始端検出時において連結テーブルを参照
し、該参照された連結テーブルデータと連結ラベルとに
従って、仮ラベルを決定しかつラベル分岐発生時には連
結テーブルの内容を変更しているため、ラベル分岐の発
生を大幅に抑制することができ、テーブル解析における
負荷が大幅に低減され、高速で仮ラベルのリラベリング
を行なうことができる。

【０２２６】(iii) 第３実施例 図４０はこの発明の第３の実施例であるラベリング回路
の構成を示す図である。図４０に示すラベリング回路
は、マスク構成部１が２行２列の局所画像領域からなる
二値マスクを生成する点が第２の実施例のラベリング回
路と異なっている。他の回路の機能は第２の実施例に示
すものと同様であり、対応する部分には同一の参照番号
を付す。

【０２２７】マスク構成部１は、入力二値画像データ
（Ｉ１）を１行分遅延させる１ビットラインバッファ１
０と、入力二値画像データを１画素分遅延させる１ビッ
トレジスタ１１ａと、１ビットレジスタ１１ａの出力を
さらに１画素分遅延させる１ビットレジスタ１１ｂと、
１ビットラインバッファ１０の出力を１画素分遅延させ
る１ビットレジスタ１１ｄと、１ビットレジスタ１１ｄ
の出力を１画素分遅延させる１ビットレジスタ１１ｅを
含む。この１ビットレジスタ１１ａ、１１ｂ、１１ｄ、
および１１ｅの出力により二値マスクが生成される。し
たがって、生成される二値マスクは図４１に示すよう
に、二値画像データＰ（ｉ，ｊ）、Ｐ（ｉ，ｊ−１）、
Ｐ（ｉ−１，ｊ）およびＰ（ｉ−１，ｊ−１）を含む。

【０２２８】注目ランおよび隣接ランは二値マスク２５
の下段および上段によりそれぞれ走査される。注目ラン
の始端はＰ（ｉ，ｊ−１）＝０かつＰ（ｉ，ｊ）＝１の
条件により検出される。注目ランの終端はＰ（ｉ，ｊ−
１）＝１かつＰ（ｉ，ｊ）＝０の条件により検出され
る。

【０２２９】隣接ランの始端は同様にして、Ｐ（ｉ−
１，ｊ−１）＝０かつＰ（ｉ−１，ｊ）＝１の条件によ
り検出される。隣接ランおよび注目ランの途切れは、Ｐ
（ｉ，ｊ）＝Ｐ（ｉ−１，ｊ）＝０の条件により検出さ
れる。この検出条件のみが異なるだけであり、仮ラベル
決定に際して用いられる５条件は第２の実施例における
ものと同じである。次に動作について説明する。

【０２３０】初期状態においては、新ラベルカウンタの
カウント値は１、仮ラベルレジスタの保持データは０、
連結ラベル記憶部の保持データは０に初期設定される。
ランラベル記憶部には何のランラベルも記憶されていな
い。

【０２３１】今図４２に示すように、二値マスク２５が
注目ランＲ１１の始端を検出すると、ランラベル記憶制
御部６が仮ラベルレジスタ１５を０にリセットする。注
目画素Ｐ（１，４）以外に１の画素が存在しないためで
ある。ランラベル記憶部５には、ランラベルが何も格納
されていないため、連結テーブルへのアクセスは何ら行
なわれない。

【０２３２】図４３に示すように、二値マスク２５が注
目ランＲ１１の終端に到達すると、この注目ランＲ１１
の終端検出に応答して、仮ラベルレジスタ１５の出力が
ランラベル記憶部５に格納される。注目ランＲ１１に
は、何ら隣接ランは存在しなかったため、仮ラベルレジ
スタ１５の出力するデータ０がこの注目ランＲ１１に対
するランラベルとしてランラベル記憶部５に格納され
る。

【０２３３】二値マスク２５が注目ランＲ１２およびＲ
１３を順次走査するが、注目ランＲ１１の場合と同様に
して、これらの注目ランＲ１２およびＲ１３に対しそれ
ぞれランラベル０が割付けられてランラベル記憶部５に
格納される。この行の走査完了時においては、ランラベ
ル記憶部には、ランＲ１１、Ｒ１２、およびＲ１３に対
するランラベル０がそれぞれ順次格納されている。

【０２３４】図４４に示すように、二値マスク２５が次
の行を走査し、注目ランＲ２１の始端を検出すると、こ
の場合においても二値マスク２５の上段の画素がすべて
０であるため、仮ラベルレジスタは０にリセットされ、
連結ラベル記憶部７の出力する連結ラベルも０を維持す
る。

【０２３５】図４５に示すように、二値マスク２５が隣
接ランＲ１１の始端を検出すると、ランラベル記憶制御
部６の制御の下にランラベル記憶部５からランラベル０
が読出されまたランラベル読出制御部１２から読出指示
信号（リード信号）が統合処理部４に与えられる。統合
処理部４はこのリード信号に応答して統合ラベル送出部
３を介して与えられたランラベルをアドレスとして連結
テーブルの内容を読出す。連結テーブルのアドレス０に
格納されたデータは初期状態にあり、０である。

【０２３６】仮ラベル選択制御部１３は、連結ラベル記
憶部７からの連結ラベル０と統合処理部４から与えられ
る連結テーブルデータ０とを受け、仮ラベル決定の第１
の条件に従って新ラベルカウンタ１８が出力するカウン
ト値１を仮ラベルとして決定する。仮ラベルセレクタ１
４がこの仮ラベル選択制御部１３からの決定結果に従っ
て新ラベルカウンタ１８の出力カウント値を選択して仮
ラベルレジスタ１５へ伝達する。これにより仮ラベルレ
ジスタ１５の保持値は１となる。新ラベルカウンタ１８
はこの第１の条件成立に従って、そのカウント値が１カ
ウントアップされて２となる。連結ラベル記憶部７は、
この仮ラベルセレクタ１４から出力されるデータ１をラ
ッチし、連結ラベル１を出力する。

【０２３７】図４６に示すように、二値マスク２５が１
画素右方向にシフトすると、二値マスク２５の左上画素
のデータは１である。仮ラベルレジスタ１５が出力する
データは１であり、仮ラベル送出制御部１７は、この仮
ラベルレジスタ１５の出力を選択する制御信号を仮ラベ
ル送出部１６へ与える。仮ラベル送出部１６はこの仮ラ
ベル送出制御部１７からの選択制御信号に従って仮ラベ
ルレジスタ１５の出力するデータを仮ラベルとして選択
して出力する。これにより画素Ｐ（１，４）に対して仮
ラベル１が割付けられる。

【０２３８】二値マスク２５がさらに２画素右方向にシ
フトすると、その右端の上段および下段の画素データは
ともに０となる。これにより、連結ラベル記憶部７は注
目ランおよび隣接ランの途切れを検出する。隣接ランの
終端検出に従って、仮ラベルレジスタ１５の出力するラ
ベル値１がランラベル記憶部１に格納され、また連結ラ
ベル記憶部の出力する連結ラベルは０にリセットされ
る。

【０２３９】二値マスク２５がさらに右方向にシフト
し、図４７に示す位置に到達すると、注目ランＲ２２お
よび隣接ランＲ１２の始端が同時に検出される。隣接ラ
ンＲ１２の始端検出に応答して、ランラベル記憶部５か
らこの隣接ランＲ１２に関連するランラベル０が読出さ
れる。この読出されたランラベル０をアドレスとして、
統合処理部４に含まれる連結テーブルからデータが読出
される。連結テーブルのアドレス０には、データ０が格
納されており、また連結ラベル記憶部７が出力する連結
ラベルは０であるため、仮ラベル決定の第１の条件に従
って、新ラベルカウンタ１８が出力するカウント値２が
仮ラベルとして選択される。この仮ラベル２はまた連結
ラベル記憶部７へ与えられ、連結ラベルが０から２へ変
化する。新ラベルカウンタ１８のカウント値は１カウン
トアップされ、３となる。この隣接ランＲ１２の各画素
に対しては、ラベル２が出力される。

【０２４０】注目ランＲ２２の終端が検出されると、ラ
ンラベル記憶制御部６の制御の下に、この仮ラベル２が
注目ランＲ２２に対するランラベルとしてランラベル記
憶部５に格納される。

【０２４１】注目ランＲ２３が走査されると、この注目
ランＲ２３に連結するランは存在しないため、この注目
ランＲ２３の終端検出時において、ランラベル０がラン
ラベル記憶部５に格納される（仮ラベルレジスタ１５が
０にリセットされている）。

【０２４２】隣接ランＲ１３および注目ランＲ２４に対
しては、ランＲ１２およびＲ２２の場合と同様の動作が
行なわれ、注目ランＲ２４に対してランラベル３が割付
けられてランラベル記憶部５に格納されるとともに、隣
接ランＲ１３の各画素に対しては、仮ラベル３が出力さ
れる。

【０２４３】図４８に示すように、二値マスク２５が次
の行（第２および第３行）を走査し始めると、まず、隣
接ランＲ２１の始端が検出される。隣接ランＲ２１のラ
ンラベルは１であり、連結テーブルは依然初期状態を維
持しているため、連結テーブルデータは１である。連結
ラベル０がであるため、仮ラベル選択制御部１３は、仮
ラベル決定の第３の条件に従って、連結テーブルデータ
１を仮ラベルおよび連結ラベルとして選択する。このラ
ベル値１が、隣接ランＲ２１の各画素に対する仮ラベル
として選択されて出力される。

【０２４４】二値マスク２５が、注目ランＲ３１を検出
すると、この注目ランＲ３１に対しては連結ラベル記憶
部７がそのラベル値１を保持し続けるため、連結ラベル
値１がこの注目ランＲ３１の各画素に対して伝搬され
る。

【０２４５】二値マスク２５が隣接ランＲ２２の始端を
検出すると、ランラベル記憶部５から、この隣接ランＲ
２２に対するランラベル２が読出される。連結テーブル
は依然初期状態を維持しているため、読出される連結テ
ーブルデータは２である。連結ラベルが１、連結テーブ
ルデータが２であるため、仮ラベル選択制御部１３は、
仮ラベル選択の第５の条件に従って、ラベルの小さな連
結ラベル１を仮ラベルと決定する。この仮ラベル選択制
御部１３の制御の下に、この仮ラベルセレクタ１４が、
連結ラベル記憶部７からの連結ラベル１を仮ラベルとし
て選択して、仮ラベルレジスタ１５へ伝達する。

【０２４６】このときまた、仮ラベル決定の第５の条件
が成立したため、ラベルの分岐が発生しており、連結テ
ーブルのアドレス２のデータは１に変更される。このと
きの連結テーブルの状態は図１２に示すものと同じであ
る。

【０２４７】隣接ランＲ２２に属する画素に対して仮ラ
ベル値１が与えられて出力される。注目ランＲ３１の終
端検出時に、仮ラベルレジスタ１５が出力するランラベ
ル１がランラベル記憶部５に格納される。

【０２４８】図４９に示すように、二値マスク２５が隣
接ランＲ２３の始端を検出すると、この隣接ランＲ２３
のランラベル０がランラベル記憶部５から読出される。
連結ラベルは、注目ランおよび隣接ランの途切れに応答
して０にリセットされており、０である。一方、連結テ
ーブルのアドレス０にはデータ０が格納されている。し
たがってこの場合、仮ラベル選択の第１条件に従って、
新ラベルカウンタ１８のカウント値４が仮ラベルとして
選択され、仮ラベルおよび連結ラベルがともに４とな
る。隣接ランＲ２３の構成画素に対しては仮ラベル４が
割付けられて出力される。

【０２４９】一方、注目ランＲ３２およびＲ３３に対し
ては、それぞれの終端検出時において、仮ラベル４がラ
ンラベルとしてランラベル記憶部５に格納される。

【０２５０】隣接ランＲ２４に対しては、その上段のラ
ンＲ１３のラベルが伝搬され、また連結テーブルのアド
レス３のデータも３であるため、仮ラベル選択の第３の
条件に従って、ラベル３が与えられる。

【０２５１】二値マスク２５がさらに次の行（第３およ
び第４行）を走査すると、まず隣接ランＲ３１の始端が
検出される。この始端検出に応答して、ランラベルおよ
び連結テーブルが検索され、ランラベル１および連結テ
ーブルデータ１が得られる。連結ラベルが０であるた
め、仮ラベル決定の第３の条件に従って、仮ラベル＝連
結ラベル＝１が得られる。この決定された連結ラベル１
は、注目ランＲ４１に伝搬する。

【０２５２】二値マスク２５が図５０に示すように、隣
接ランＲ３２の始端を検出すると、対応のランラベル４
に従って、連結テーブルからデータ４が読出される。連
結ラベルが１であり、連結テーブルデータが４であるた
め、仮ラベル決定の第５の条件に従って、仮ラベル＝連
結ラベル＝１となる。同一対象物に異なるラベルが割付
けられているため、連結テーブルの内容が変更され、連
結テーブルのアドレス４に格納されるデータは１とな
る。このときの連結テーブルの内容は図１５に示すもの
と同じになる。隣接ランＲ３２に属する画素に対しては
仮ラベル値１が与えられる。注目ランＲ４１の終端検出
時に、ランラベル１がランラベル記憶部５に格納され
る。

【０２５３】二値マスク２５が図５１に示すように隣接
ランＲ３３の始端を検出すると、再びランラベル記憶部
５からランラベル４が読出され、連結テーブルからアド
レス４のデータが読出される。連結テーブルのアドレス
４のデータは先に隣接ランＲ３２の検出に従ってデータ
１に変更されている。連結ラベルは０であるため、仮ラ
ベル選択の第３の条件に従って、隣接ランＲ３３の各画
素に対しては仮ラベル１が選択され、仮ラベル＝連結ラ
ベル＝１となる。隣接ランＲ３３に属する各画素に対し
ては仮ラベル値１が与えられる。

【０２５４】図５２に示すように、二値マスク２５が隣
接ランＲ３４の始端を検出すると、ランラベル記憶部５
からランラベル３が読出される。連結テーブルのアドレ
ス３にはデータ３が格納されている。このとき連結ラベ
ル記憶部７は、隣接ランＲ３３から注目ランＲ４２を介
して伝搬される連結ラベル１を格納している。したがっ
て、仮ラベル選択の第５条件に従って、仮ラベルおよび
連結ラベルがともに１となる。このとき、またラベルの
分岐が発生していたため、連結テーブルのアドレス３の
データは１に変更される。この結果、連結テーブルは図
１８に示すものと同じとなる。

【０２５５】注目ランＲ４２の終端検出に従って、この
注目ランＲ４２に対するランラベル１がランラベル記憶
部５に格納される。

【０２５６】二値マスク２５が最終行の走査を行なう
と、隣接ランＲ４１およびＲ４２にはラベル１が与えら
れ、各画素に対し、仮ラベル１が割付けられる。この結
果得られる仮ラベル画像は図２０に示すものと同じであ
る。この最終的に得られる仮ラベル画像および連結テー
ブルの内容は図１８および図２０に示すものと同じであ
るため、この連結テーブルのみを用いてラベル統合処理
を行なうことができる。すなわち、ラベル２、３および
４をそれぞれ付されたランはラベル１を付されたラン
（あるいは画素）と連結していることが解析される。し
たがって、ラベル統合処理をすることなく、ラベル統合
処理結果が連結テーブル内に格納されている。

【０２５７】この統合処理が終了した連結テーブルを用
いて仮ラベル画像のラベルの付け直しを行なうと、図２
１に示すものと同じラベリング画像が得られる。

【０２５８】上述のように、２行２列の二値マスクを用
いて二値画像のラベルを行なっても、第１および第２の
実施例と全く同様に、ラベルの統合処理の負荷が大幅に
軽減されるラベリング回路が得られる。また、二値マス
クは２行２列の画素からなる局所画像領域を抽出するだ
けであり、装置規模を大幅に低減することができる。

【０２５９】なおこの第３の実施例におけるラベル回路
の各構成要素の構成は、第２の実施例において用いられ
たものと同様の構成で実現することができる。単に隣接
ランの始端および注目ランの終端および始端検出時にお
いて利用される二値画像データの画素位置が異なるだけ
である。他の制御回路の構成は全く同様の構成を利用す
ることができる。

【０２６０】（iv） 第４実施例 図５３はこの発明の第４の実施例であるラベリング回路
の構成を示す図である。図５３に示すラベリング回路は
図３０に示すラベリング回路の構成に加え、さらに位相
同期回路１９を含む。位相同期回路１９は、外部クロッ
ク信号ＣＬＫＩを周波数逓倍して内部クロック信号ＣＬ
Ｋを発生する。外部クロック信号ＣＬＫＩは、マスク構
成部１へ与えられる二値画像データの入力周波数と同一
の周波数を備える。マスク構成部１へは、外部クロック
信号ＣＬＫＩに同期して二値画像データが与えられる。
マスク構成部はこの外部クロック信号ＣＬＫＩに同期し
て外部からの二値画像データを取込み、二値マスクを生
成して出力する。仮マスク決定部２、統合ラベル送出部
３、統合処理部４、ランラベル記憶部６、ランラベル記
憶部５および連結ラベル記憶部７などの各構成要素はこ
の位相同期回路９からの内部クロック信号ＣＬＫに同期
して動作する。

【０２６１】図５４は位相同期回路の構成および動作を
示す図である。図５４（Ａ）において、位相同期回路１
９は、与えられた信号の周波数を定数分の１に分周する
分周器２３と、外部クロック信号ＣＬＫＩと分周器２３
からの分周クロック信号との位相を比較する位相比較器
２０と、位相比較器２０からの位相差信号の低域成分の
みを通過させる低域フィルタ２１と、低域フィルタ２１
の出力に従って内部クロック信号ＣＬＫを生成する電圧
制御発振器２２を含む。電圧制御発振器２２の出力する
クロック信号ＣＬＫは分周器２３へ与えられる。次に動
作について簡単に説明する。

【０２６２】位相比較器２０は、外部からのクロック信
号ＣＬＫＩと、分周器２３からのクロック信号ＣＬＫが
定数分の１に分周されたクロック信号との位相差を検出
し、その位相差に相当する出力信号を生成する。低域フ
ィルタ２１は、この位相比較器２０からの位相差信号に
含まれる高調波成分および雑音を除去し、電圧制御発振
器２２の発振動作を制御する電圧を生成する。電圧制御
発振器２２は、この低域フィルタ２１から与えられる信
号電圧に比例した周波数のクロック信号ＣＬＫを生成す
る。このクロック信号ＣＬＫは分周器２３により分周さ
れ、周波数が低減されて位相比較器２０へ与えられる。
この電圧制御発振器２２の出力を分周器２３により分周
し、位相比較器２０へ与えることにより、１つの帰還ル
ープが形成される。

【０２６３】位相同期回路１９は、外部からのクロック
信号ＣＬＫＩに同期しかつ周波数が定数倍であるクロッ
ク信号ＣＬＫを生成する。図５４（Ｂ）には、外部クロ
ック信号ＣＬＫＩの周波数が５倍に逓倍されてクロック
信号ＣＬＫが生成される際の波形図を示す。

【０２６４】位相同期回路の初期状態においては、外部
クロック信号ＣＬＫＩとクロック信号ＣＬＫとは位相は
異なっており、またこのクロック信号ＣＬＫの周波数も
所望の周波数とは異なる。

【０２６５】電圧制御発振器２２の出力信号を分周器２
３を介して位相比較器２０へフィードバックして位相差
を検出し、その位相差を電圧に置換して電圧制御発振器
２２が生成するクロック信号の周波数を変化させる。こ
の動作をフィードバックループにより収束させることに
より、電圧制御発振器２２から生成されるクロック信号
ＣＬＫは安定に図５４（Ｂ）に示すように所望の周波数
を有しかつ外部クロック信号ＣＬＫＩに位相同期した信
号となる。

【０２６６】一方、ラベリング回路が実行する処理は、
図１の処理プログラムに示されるように複数のステップ
を含む。各ステップがクロック信号ＣＬＫに従って、パ
イプライン的に実行される。したがって、１画素のデー
タの入力に対し必要な複数の処理は外部クロックＣＬＫ
Ｉの１サイクル内で確実に処理実行される。仮ラベル送
出部１６から仮ラベルがラベル付対象画素（隣接注目画
素：二値マスク２４の上段中央の画素）のデータの１お
よび０に従って内部で決定された仮ラベルまたは固定デ
ータ０が出力される。この出力仮ラベル値は外部クロッ
ク信号ＣＬＫＩと同一周波数で変化する。

【０２６７】図１に示す処理フロー図において、上段ラ
ンすなわち隣接ランの始端が検出された場合には、ラン
ラベル記憶部５からランラベルが読出され、統合処理部
４に含まれる連結テーブルの内容が参照される。この参
照された連結テーブルデータと連結ラベル記憶部７が出
力する連結ラベルとを用いて仮ラベルを決定する。仮ラ
ベルが決定されたとき、ラベルの分岐が発生したことが
判明すれば、連結テーブルの内容を書換える必要があ
る。このとき変更前の連結ラベルを用いる必要がある。
連結ラベル記憶部７には最終的には決定された仮ラベル
と同一のデータ値が格納される。すなわち連結ラベル＝
仮ラベルという動作が行なわれる。したがってこのとき
ラベルの分岐発生時において、連結ラベル記憶部７のデ
ータラッチを連結テーブルへのデータ書込後に行なう必
要がある。このとき内部クロック信号ＣＬＫを用いれば
確実に処理をパイプライン化することができるため、デ
ータの書込および読出においてタイミングのずれが生じ
ることなく確実に処理を実行することができる。

【０２６８】このとき、統合処理部４において、隣接ラ
ン始端検出時において、連結ラベル記憶部７が出力する
連結ラベルをラッチするラッチ回路が設けられており、
このラッチ回路にラッチされた連結ラベルを用いて連結
テーブルの変更を行なう構成も用いることができる。こ
のときには、連結ラベル記憶部７は、仮ラベルセレクタ
１４の出力する仮ラベルが確定した時点で仮ラベルをラ
ッチすることができ、連結テーブルの変更と並行して連
結ラベル＝仮ラベルとする処理を行なうことができる。

【０２６９】また連結テーブルへデータを書込む場合に
は、ランラベル読出制御部１２が出力するリード信号
（出力イネーブル信号）は不活性状態となっている必要
がある。したがって、連結テーブルのデータの読出およ
びデータの書込をもこのような位相同期回路１９からの
クロック信号ＣＬＫを用いることにより確実にパイプラ
イン的に実行することができ、タイミング調整のための
遅延回路を用いることなく容易に処理を実行することが
できる。

【０２７０】またこのような内部クロック信号ＣＬＫを
用いることにより、図１に示す処理フロー図における判
別ブロックにおいて、分岐発生の部分にかかわらず、各
判別ブロックの次の処理ブロックの動作タイミングを同
一タイミングに設定することができ、二値マスクが抽出
する局所画像領域におけるランの状態にかかわらず、常
に同一タイミングで同一の処理を行なうことができ、確
実に外部クロック信号ＣＬＫＩの１クロックサイクル内
で処理を実行することができる。

【０２７１】このようなパイプライン処理の実行は、図
示しないクロックカウンタを用いて位相同期回路１９が
発生するクロック信号ＣＬＫをカウントしこのカウント
値に従って各回路を活性化する構成とすることにより容
易に実現することができる。仮ラベル送出部１６が確定
した仮ラベルを出力するタイミングは外部からの二値画
像データの入力タイミングと同一であってもよく、また
異なっていてもよい。同一の周波数で二値画像データの
入力と仮ラベルの出力とが行なわれればよい。

【０２７２】以上のように、この第４の実施例に従え
ば、２行３列の二値画像データからなる二値マスクを処
理するラベリング回路において、外部クロック信号を周
波数逓倍したクロック信号により各構成要素を動作させ
ているため、１画素の入力に対して必要なラベリング処
理動作を確実に外部クロック信号の１サイクル期間内で
処理することができる。このときまた内部構成要素をパ
イプライン態様で駆動することができるため、高速かつ
確実にラベリング処理を実行することができる。

【０２７３】（ｖ） 第５実施例 図５５はこの発明の第５の実施例であるラベリング回路
の構成を示す図である。この図５５に示すラベリング回
路は、図４０に示すラベリング回路の構成に加え、さら
に位相同期回路１９を含む。この位相同期回路１９は、
図５３に示すものと同様の構成を備え、外部クロック信
号ＣＬＫＩに位相同期しかつ周波数逓倍されたクロック
信号ＣＬＫを発生する。この位相同期回路１９からのク
ロック信号ＣＬＫに従って、ラベリング回路内の各構成
要素がパイプライン態様で動作する。この図５５に示す
回路構成の動作を簡単に説明する。

【０２７４】入力二値画像データＩ１が入力される周波
数と同一周波数を有するクロック信号ＣＬＫＩが位相同
期回路１９へ与えられる。入力二値画像データはこの外
部クロック信号ＣＬＫＩに同期してマスク構成部１へ与
えられてもよい。外部クロック信号ＣＬＫＩの定数倍の
周波数を有しかつ外部クロック信号ＣＬＫＩの位相同期
したクロック信号ＣＬＫに従ってラベル回路の各構成要
素が動作する。

【０２７５】外部クロック信号ＣＬＫＩの各サイクルご
とに外部から二値画像データがマスク構成部１へ与えら
れる。マスク構成部１は、水平方向２画素、垂直方向２
画素の２行２列の局所画像領域を抽出する二値マスク２
５を生成する。仮マスク決定部に含まれる各制御部１
２、１３、ランラベル記憶制御部６および連結ラベル記
憶部７はこの二値マスク２５をデコードして必要な処理
を実行する。このとき各回路の構成要素が位相同期回路
１９から生成される周波数逓倍されたクロック信号ＣＬ
Ｋに従って動作することにより、１画素入力に対し必要
な複数の処理（図１に示す処理ステップ）を外部クロッ
ク信号ＣＬＫＩの１サイクル内で確実に実行することが
できる。

【０２７６】仮ラベル送出部１６からは、ラベル付対象
画素（二値マスク２５の上段左側の画素）のデータに従
って、決定された仮ラベルまたは固定データ０の一方が
出力される。この仮ラベル送出部１６から出力される出
力仮ラベルは、外部クロック信号ＣＬＫＩと同一周波数
で変化する。出力仮ラベルが出力されるタイミングは外
部クロック信号ＣＬＫＩと同期していなくてもよい。

【０２７７】隣接ランの始端検出時における連結テーブ
ルの参照および分岐ラベル発生時における連結ラベルの
内容変更および連結ラベルの変更などの処理はすべて位
相同期回路１９からのクロック信号ＣＬＫに同期して実
行される。このように周波数逓倍されたクロック信号Ｃ
ＬＫを用いて構成要素を動作させることにより、たとえ
ば図３３に示すような連結ラベル記憶部の構成において
遅延回路７３を設ける必要がなく、確実に処理を実行す
ることができる。また、統合処理部４に含まれる連結テ
ーブルへのリード／ライトの動作を確実にパイプライン
的に時分割多重して実行することができ、確実なラベリ
ング処理を行なうことができる。

【０２７８】ここで、先に図３６に示す連結テーブルの
構成において、ＲＡＭ４１は、出力イネーブル入力ＯＥ
とライトイネーブル入力／ＷＥとが別々に設けられてい
る。これは、同一ピンに与えられる構成であってもよ
い。ランラベル読出制御部１２が与えるリード信号の発
生と仮ラベル選択制御部１３の制御の下に統合ラベル送
出部３を介して行なわれる連結テーブルへのデータ書込
とは明らかに時間的に異なっており、この連結テーブル
へのリードおよびライトは時分割的に実行されるためで
ある。このとき位相同期回路１９からのクロック信号Ｃ
ＬＫを用いることにより、ランラベル読出制御部１２か
らのリード信号を不活性状態とした後に統合ラベル送出
部３から連結テーブルへライト信号を与えることができ
る。このようなタイミング調整は、クロック信号ＣＬＫ
を用いることにより容易に実現することができる。

【０２７９】以上のように、この第５の実施例に従え
ば、２行２列の局所画像領域を抽出する二値マスクを用
いて装置規模を低減するとともに、各構成要素を位相同
期回路１９からの周波数逓倍されたクロック信号ＣＬＫ
を用いて動作させることにより、確実に１画素入力の１
サイクル期間内で１つの二値マスクに対して必要とされ
る複数のラベリング処理ステップをすべて実行すること
ができるため、仮ラベル付を高速かつ確実に行なうこと
ができる。

【０２８０】なお、上記実施例１ないし５においては、
二値マスクとして２行２列および２行３列の場合がそれ
ぞれ説明されているが、この二値マスクの構成はこれに
限定されず、複数行複数列の局所画像領域が抽出される
構成であればよい。

【０２８１】また２行３列の画素からなる二値マスクの
場合、隣接ランの始端はＰ（ｉ−１，ｊ）＝０かつＰ
（ｉ−１，ｊ＋１）＝１の条件により検出されており、
これにより注目画素走査に対し隣接ランの始端を先読み
することができるため、ラベル付対象画素（隣接注目画
素）に対し確実に仮ラベルを正確に付すことができる。

【０２８２】（ｖｉ） 第６実施例 上述の第１ないし第５の実施例においては、画像データ
の仮ラベルの連結関係を示す連結テーブルの作成につい
て説明した。以下に、この連結テーブルの解析を行な
い、仮ラベル画像データに対し最終ラベリングを行なう
手法について説明する。

【０２８３】以下に説明する連結テーブル解析のための
ラベリング方式および回路は、前述の第１ないし第５の
実施例のラベリング回路およびラベリング方法と組合わ
せて用いることができる。また、図７５に示すような構
成にも適用されることができる。すなわち、以下に述べ
る連結テーブル解析手法は、以下のステップを含むラベ
リング方式に適用することができる：（ａ）画像データ
を局所画像領域単位で走査する、（ｂ）同一画像領域に
対し複数のラベルが連結している場合には、ラベル値の
小さい方を以後の走査において伝搬させるラベル値とし
て採用する、（ｃ）この採用されたラベル値を書込デー
タとし、非選択とされたラベル値をアドレスとしてテー
ブルに書込み、これにより仮ラベルの連結関係を記憶す
る、（ｄ）走査された画像データに対しては仮ラベルが
割当てられ、この仮ラベルがテーブルの解析結果に従っ
て最終ラベルに変換される。

【０２８４】したがって、以下の説明においては、第１
ないし第５の実施例と切り離し、連結テーブルの解析手
法について説明する。

【０２８５】今、図５６に示すような仮ラベル画像１０
０を、図５７に示す最終ラベル画像１０１に変換する手
法について説明する。図５６において、仮ラベル画像１
００は、領域Ｉ、ＩＩ、およびＩＩＩを含む。領域Ｉに
は、仮ラベル１が割当てられており、領域ＩＩには、仮
ラベル２、３、および４が連結されており、領域ＩＩＩ
には、仮ラベル５および６が割当てられている。連結テ
ーブルには、図５８に示すように、各仮ラベルの連結関
係が記憶されている。すなわち、図５８に示すように、
連結テーブルにおいてはアドレス１、２、３、４、５お
よび６それぞれに対し、仮ラベルデータ１、２、３、４
および５が記憶されている。

【０２８６】アドレスは、仮ラベル画像１００における
各仮ラベルを示し、データは、この仮ラベルの連結先を
示している。たとえばアドレス４のデータ３は、仮ラベ
ル画像１００において、仮ラベル４は、仮ラベル３に連
結していることを示している。この図５８に示す連結テ
ーブルを解析して、仮レベルの連結関係を統合し、かつ
ラベル値を順次小さい値から付加することにより、図５
７に示すような領域Ｉ、ＩＩ、およびＩＩＩに対しそれ
ぞれ最終ラベル１、２、および３が付された最終ラベル
画像を得る。

【０２８７】図５９は、この発明の第６の実施例である
ラベリング方法を示す動作フロー図である。以下、この
第６の実施例であるラベリング手法について図５８に示
す連結テーブルを用いて連結テーブルを解析する処理動
作について説明する。

【０２８８】この第６の実施例におけるラベリング手法
においては、仮ラベル値を発生するための仮ラベルカウ
ンタと、最終ラベル値を発生するための最終ラベルカウ
ンタとが用いられる。仮ラベル付けは、最小ラベル値を
１として開始される。仮ラベルカウンタから最初に連結
テーブルへ与えられるカウント値は１として処理が開始
される。この場合、仮ラベルカウンタの初期設定はカウ
ント値０に設定される。また、同一領域（連結領域：た
とえば図５６の仮ラベル画像１００における領域Ｉ）に
１つだけ割当てられる最終ラベルも１から順に付けられ
る。この場合も、最終ラベルカウンタの初期値が０に設
定される（ステップＳ１００）。

【０２８９】まずステップＳ１０２において仮ラベルカ
ウンタの更新が行なわれる。初期状態においては、仮ラ
ベルカウンタの初期値が０であるため、この仮ラベルカ
ウンタのカウント値はｉ＝１となる。この仮ラベルカウ
ンタのカウント値ｉ＝１をアドレスとして連結テーブル
の内容Ｍ（ｉ）を読出す（ステップＳ１０４）。

【０２９０】図６０（Ａ）に示すように、連結テーブル
のアドレス１の位置にはデータ１が格納されている。こ
の仮ラベルから与えられたカウント値すなわち連結テー
ブルのアドレス値ｉと連結テーブルから読出されたデー
タＭ（ｉ）の一致／不一致を検出する（ステップＳ１０
６）。今、両者はともに１であり、等しいため、最終ラ
ベルカウンタのカウント値の更新が行なわれる。最終ラ
ベルカウンタの初期値が０であるため、ｊ＝１となる
（ステップＳ１０８）。この最終ラベルカウンタの更新
値ｊを連結テーブルのアドレスｉの位置に書込む（Ｍ
（ｉ）＝ｊ）。

【０２９１】ステップＳ１０６において、仮ラベルカウ
ンタのカウント値ｉと連結テーブルから読出されたデー
タＭ（ｉ）とが不一致の場合、この連結テーブルから読
出されたデータＭ（ｉ）をアドレスとして連結テーブル
からデータを読出す。この読出データをＭ（Ｍ（ｉ））
で示す（ステップＳ１１２）。次いでこの連結テーブル
から読出されたデータＭ（Ｍ（ｉ））を連結テーブルの
アドレスｉの位置に書込む（ステップＳ１１４）。

【０２９２】すなわち連結テーブルにおいては、アドレ
スは仮ラベルを示し、データはこの仮ラベルの連結先を
示している。アドレスとデータが不一致の状態は、その
仮ラベルは別の仮ラベルに連結していることを示してい
る。したがって連結先の仮ラベルの連結先を新たに書込
んでおけば、この仮ラベルの連結先が決定される。

【０２９３】連結テーブルのアドレスとその格納データ
が一致している場合には、この仮ラベルは自身にのみ連
結していることを示す。したがってこのとき仮ラベルカ
ウンタのカウント値を書込んでおけば、仮ラベル値を小
さな値に変更することができる。次に具体的な動作につ
いて説明する。

【０２９４】図６０および図６１は、図５８に示す連結
テーブルの解析動作を示す図である。以下、図６０およ
び図６１を参照してこの発明の第６の実施例であるラベ
リング方式について説明する。

【０２９５】図６０（Ａ）に示すように、まず仮ラベル
カウンタのカウント値が１に設定される。この仮ラベル
カウンタのカウント値１をアドレスとして連結テーブル
へアクセスする。連結テーブルにおいてはアドレス１に
はデータ１が格納されている。この場合、アドレス値と
データとが一致しているため、最終ラベルカウンタのカ
ウント値が初期値の０から１に更新され、このカウント
値１を連結テーブルのアドレス１の位置に書込む。

【０２９６】次いで仮ラベルカウンタのカウント値が１
更新されて２となる。図６０（Ｂ）に示すように、連結
テーブルのアドレス２のうちにはデータ２が格納されて
いる。この場合も、最終ラベルカウンタのカウント値が
更新され、そのカウント値２が連結テーブルのアドレス
２の位置に書込まれる。

【０２９７】次に図６０（Ｃ）に示すように、仮ラベル
カウンタのカウント値３に従って連結テーブルへアクセ
スすると、連結テーブルのアドレス３の位置にはデータ
２が格納されている。連結テーブルのアドレスと格納デ
ータは不一致である。この場合、仮ラベル値３が付され
ている領域は、仮ラベル値２が付されている領域と連結
していることを示している。これは、仮ラベル付け動作
において、図５６に示すように、局所画像領域内に異な
るラベルが連結していることが判明したとき、ラベル値
の小さい方が以後の仮ラベル付け用のラベル値として採
用され、かつこの両者が連結していることを記述するた
めに、非選択とされたラベル値３をアドレスとして連結
先ラベル値２を連結テーブルに記憶した結果である。こ
の処理動作においては、連結テーブルの記憶データがそ
の対応のアドレス値よりも大きな値をとることはない。

【０２９８】また、連結テーブルのアドレスとデータと
が異なっている場合、データすなわち連結した２つの仮
ラベルのうち、採用された仮ラベルがさらに他の仮ラベ
ルに連結する場合が生じる。この場合においても、本実
施例における連結テーブル解析では、仮ラベル値の最小
値から順に大きな値を処理する（仮ラベルカウンタは初
期値からカウントアップ動作をしている）ので連結テー
ブルのアドレスとその格納データが不一致の場合、その
格納データに対応する連結テーブルのアドレスについて
は解析が既に終了している。したがって、連結テーブル
を最大２回読出すことにより、正確な最終ラベルが得ら
れる。

【０２９９】連結テーブルのアドレス３のデータ２を再
びアドレスとして連結テーブルからデータを読出す。連
結テーブルのアドレス２にはデータ２が格納されてい
る。このデータ２は、仮ラベル３の最終ラベルを表わし
ている。このデータ２を仮ラベル３の連結先として連結
テーブルのアドレス３の位置に書込む。これにより仮ラ
ベル３に対する解析が終了し、次の仮ラベルの処理に移
る。

【０３００】図６０（Ｄ）に示すように、仮ラベルカウ
ンタのカウント値が１インクリメントされて４となる。
連結テーブルのアドレス４にはデータ３が格納されてい
る。この場合においても連結テーブルのアドレス値とそ
の格納データは不一致である。この場合には、この格納
データ３をアドレスとして連結テーブルの格納データを
読出し、その読出したデータ２を連結テーブルのアドレ
ス４の位置に書込む。これにより、連結テーブルのアド
レス４の格納データは３から２に変更される。最終ラベ
ルカウンタのカウント値は変更されず２を維持する。

【０３０１】次いで、図６１（Ａ）に示すように、仮ラ
ベルカウンタのカウント値を１増分して５とする。連結
テーブルのアドレス５にはデータ５が格納されている。
この場合、連結テーブルのアドレス値とデータが一致し
ているため、最終ラベルカウンタのカウント値が１増分
され、この最終ラベルカウンタのカウント値が連結テー
ブルのアドレス５の位置に書込まれる。これにより、最
終ラベルを順次最小値１から連続的に増加させることが
できる。

【０３０２】次いで図６１（Ｂ）に示すように仮ラベル
カウンタのカウント値を１増分して６とする。連結テー
ブルのアドレス６の位置にはデータ５が格納されてい
る。アドレス値とデータが異なるため、仮ラベル３およ
び４の処理と同様にして、もう一度その格納データ５を
アドレスとして連結テーブルからデータを読出す。この
読出したデータ３を連結テーブルのアドレス６の位置に
格納する。これにより仮ラベル６に対する処理が終了す
る。

【０３０３】上述の一連の動作による連結テーブルの解
析結果、図６１（Ｃ）に示す連結テーブルが得られる。
この連結テーブルを用いて図５６に示す仮ラベル画像１
００のラベル変換を実行すれば、図５７に示す最終ラベ
ル画像を得ることができる。すなわちこの連結テーブル
を仮ラベル画像を最終ラベル画像へ変換するためのルッ
クアップテーブルとして利用することができる。変換テ
ーブルを連結テーブルと別に設ける必要はなくなり記憶
領域を低減することができる。

【０３０４】（ｖｉｉ） 第７の実施例 この第６の実施例のラベリング処理は、ソフトウェアを
用いて実行されてもよい。高速化の観点からはハードウ
ェアを用いるのが好ましい。この図５９に示す処理動作
を実現するためのハードウェア構成を図６２に示す。

【０３０５】図６２において、連結テーブル解析用回路
は、仮ラベルの連結関係をテーブル形態で記憶する連結
テーブル１０２と、仮ラベル値ＴＲを発生する仮ラベル
カウンタ１０１と、仮ラベルカウンタ１０１からのカウ
ント値ＴＲと連結テーブルから読出されたデータＲＤの
一方を選択的に通過させる選択回路１０５ａと、仮ラベ
ルカウンタ１０１からのカウント値ＴＲと、連結テーブ
ル１０２から読出されたデータＲＤとの一致／不一致を
検出する一致検出器１０３と、一致検出器１０３の一致
検出に応答してカウントアップ動作する最終ラベルカウ
ンタ１０４と、この最終ラベルカウンタ１０４のカウン
ト値ＦＬと連結テーブル１０２から読出されたデータＲ
Ｄの一方を選択する選択回路１０５ｂを含む。

【０３０６】選択回路１０５ｂの出力は、連結テーブル
１０２に対する書込データＷＤとして信号線１１５上に
伝達される。タイミングコントローラ１２０は、各回路
の動作タイミングを決定するとともに、連結テーブル１
０２における読出／書込動作、選択回路１０５ａにおけ
る選択動作の切換、一致検出器１０３の一致検出タイミ
ング、および選択回路１０５ｂにおける選択出力タイミ
ングを決定する。

【０３０７】仮ラベルカウンタ１０１および最終ラベル
カウンタ１０４は、その初期値が１に設定されている。
次に動作について説明する。

【０３０８】まず、図６２および図６３を参照して、連
結テーブルのアドレスと格納データとが等しい場合の動
作について説明する。

【０３０９】仮ラベルカウンタ１０１から、信号線１１
０上にカウント値ＴＲ（ｉ）が出力される。選択回路１
０５ａは、まずこの仮ラベルカウンタ１０１からのカウ
ント値ＴＲ（ｉ）を選択して連結テーブル１０２へ与え
る。連結テーブル１０２は、この選択回路１０５ａから
信号線１１１上に与えられたカウント値ＴＲ（ｉ）をア
ドレスとしてその格納データＲＤ（ｉ）を読出信号線１
１２上に伝達する。

【０３１０】一致検出器１０３は、この仮ラベルカウン
タ１０１のカウント値ＴＲ（ｉ）と連結テーブル１０２
から信号線１１２上に読出されたデータＲＤ（ｉ）の一
致／不一致を検出する。今、両者が等しい（ＴＲ（ｉ）
＝ＲＤ（ｉ））ため、一致検出器１０３は、一致を示す
信号を信号線１１３上に出力する。図６３においては、
この一致を示す信号をハイレベルの信号で示す。この一
致検出器１０３から信号線１１３上に与えられた一致検
出信号に応答して、選択回路１０５ｂは最終ラベルカウ
ンタ１０４のカウント値ＦＬ（ｋ）を選択して信号線１
１５上に与える。

【０３１１】この一致検出器１０３における一致検出動
作と並行して、選択回路１０５ａは、また信号線１１２
上に与えられた読出データＲＤ（ｉ）を選択して信号線
１１１上に与える。連結テーブル１０２からは、この信
号線１１１上に与えられたデータＲＤ（ｉ）をアドレス
としてその記憶内容を信号線１１２上に読出す。

【０３１２】次いで、選択回路１０５ａは、仮ラベルカ
ウンタ１０１から信号線１１０上に与えられたカウント
値ＴＲ（ｉ）を選択して信号線１１１上に伝達する。選
択回路１０５ｂは、最終ラベルカウンタ１０４が出力す
るカウント値ＦＬ（ｋ）を選択して書込データＷＤとし
て書込データ信号線１１５上に伝達している。連結テー
ブル１０２は、このとき、仮ラベルカウンタ１０１のカ
ウント値ＴＲ（ｉ）をアドレスとして、選択回路１０５
ｂから出力された最終ラベルカウンタ１０４のカウント
値ＦＬ（ｋ）を書込む。この書込動作と並行して、最終
ラベルカウンタ１０４のカウント値ＦＬ（ｋ）が１増分
されてＦＬ（ｋ＋１）となる。

【０３１３】なお図６３に示す信号波形図においては一
致検出器１０３の出力はこの仮ラベルカウンタ１０１の
カウント値ＴＲ（ｉ）に対する処理動作期間中一致検出
状態となっている。これは所定の期間のみ一致検出状態
となる信号が用いられてもよい。また、選択回路１０５
ｂは、一致検出信号に応答して最終ラベルカウンタ１０
４のカウント値ＦＬ（ｋ）を選択する状態となるのでは
なく、連結テーブル１０２に対するデータ書込動作時に
おいて選択回路１０５ｂの出力が確定状態となるタイミ
ングが利用されてもよい。これらの動作タイミングはタ
イミングコントローラ１２０により、適応なタイミング
に設定される。

【０３１４】次に、図６２および図６４を参照して、連
結テーブル１０２におけるアドレスと格納データが不一
致の場合の動作について説明する。

【０３１５】まず、仮ラベルカウンタ１０１からは信号
線１１０上にカウント値ＴＲ（ｉ）が出力される。選択
回路１０５ａは仮ラベルカウンタ１０１からのカウント
値ＴＲ（ｉ）を選択して信号線１１１上に与える。連結
テーブル１０２からは信号線１１２上に読出データＲＤ
（ｊ）が読出される。一致検出器１０３は、この信号線
１１２上の読出データＲＤ（ｊ）と仮ラベルカウンタ１
０１から信号線１１０上に与えられたカウント値ＴＲ
（ｉ）を比較する。今、両者は不一致（ＴＲ（ｉ）≠Ｒ
Ｄ（ｊ））であるため、一致検出器１０３の出力は不一
致検出状態となる（図６４においてはローレベルの信号
で示す）。この状態では最終ラベルカウンタ１０４のカ
ウント値は変更されない。選択回路１０５ｂは、この状
態においては一致検出器１０３から信号線１１３上に与
えられた不一致検出信号に応答して連結テーブル１０２
から信号線１１２上に読出されたデータを選択する状態
となる。

【０３１６】この一致検出器１０３における一致検出動
作と並行して、選択回路１０５ａは、連結テーブル１０
２から信号線１１２上に読出されたデータＲＤ（ｊ）を
選択して信号線１１１上に与える。連結テーブル１０２
は、この信号線１１１上に与えられたデータＲＤ（ｊ）
をアドレスとして対応の記憶データＲＤ（ｍ）を読出し
信号線１１２上に与える。

【０３１７】この２回目の読出動作の後、選択回路１０
５ａは再び仮ラベルカウンタ１０１からの出力カウント
値ＴＲ（ｉ）を選択して信号線１１１上に与える。選択
回路１０５ｂは、信号線１１２上に与えられたデータＲ
Ｄ（ｍ）を選択して信号線１１５上に与えている。この
状態においては連結テーブル１０２は、信号線１１１上
に与えられた仮ラベルカウンタ１０１の出力カウント値
ＴＲ（ｉ）をアドレスとして、信号線１１５上に与えら
れた書込データＷＤ（ｍ）（＝ＲＤ（ｍ））を書込む。

【０３１８】なお図６２に示す構成において、最終ラベ
ルカウンタ１０４の初期値は１に設定されている状態を
示している。この最終ラベルカウンタ１０４のカウント
値が０に初期設定される場合には、図６３において破線
の信号で示すように、一致検出に応答してそのカウント
値が増分される構成が用いられる。また、図６４に示す
信号波形図においては、選択回路１０５ｂは、連結テー
ブル１０２から読出されたデータＲＤ（ｊ）を出力して
いる。選択回路１０５ｂは、後の出力は、２回目の読出
動作時において確定状態となる構成が利用されてもよ
い。

【０３１９】次に、この図６２に示す回路の動作につい
て、連結テーブル１０２が図５８（Ｃ）に示す状態の場
合について説明する。

【０３２０】仮ラベルカウンタ１０１からはカウント値
１が出力される（ＴＲ（１））。選択回路１０５ａは、
この仮ラベルカウンタ１０１からのカウント値ＴＲ
（１）を選択して信号線１１１上に与える。連結テーブ
ル１０２からは、アドレス１からデータ１（ＲＤ
（１））が読出されて信号線１１２上に出力される。一
致検出器１０３は、この仮ラベルカウンタ１０１のカウ
ント値ＴＲ（１）と連結テーブル１０２から読出された
データ（ＲＤ（１））とを比較する。両者はともに１で
あるため、一致検出器１０３からは信号線１１３上に一
致検出信号が出力される。この信号線１１３上の一致検
出信号に従って選択回路１０５ｂは最終ラベルカウンタ
１０４から信号線１１４上に出力されたカウント値ＦＬ
を選択する状態となる。最終ラベルカウンタ１０４は初
期値が１に設定されている（ＦＬ＝ＦＬ（１））。

【０３２１】この一致検出器１０３における一致検出動
作と並行して、信号線１１２上の読出データＲＤ（１）
が選択回路１０５ａにより選択されて信号線１１１上に
伝達される。連結テーブル１０２から再び信号線１１２
上にデータＲＤ（１）が読出される。

【０３２２】この読出動作の後、選択回路１０５ａは再
び仮ラベルカウンタ１０１のカウント値ＴＲ（１）を選
択して信号線１１１上に与える。連結テーブル１０２に
おいては、この信号線１１１上のカウント値ＴＲ（１）
をアドレスとして、信号線１１５上に与えられた最終ラ
ベルカウンタのカウント値ＦＬ（１）を書込データとし
て書込む。これにより、連結テーブル１０２において
は、アドレス１の位置にデータ１が書込まれる。最終ラ
ベルカウンタ１０４は、この書込動作と並行してそのカ
ウント値が１から２に増分される（ＦＬ（１）がＦＬ
（２）に更新される）。以上の処理で、仮ラベル１に対
する処理が完了する。

【０３２３】仮ラベル値２に対する動作も仮ラベル値１
と同様にして実行される。最終ラベルカウンタ１０４の
カウント値が選択されかつ更新されて３（＝ＦＬ
（３））となる。連結テーブル１０２においては、アド
レス２の位置に最終ラベル値２が書込まれる。

【０３２４】仮ラベル値３に対しては、連結テーブル１
０２に対する１度目のアクセスは、仮ラベル１および２
と同様である。しかしその後の処理が異なる。連結テー
ブル１０２のアドレス３から読出されたデータは２であ
る。この場合、一致検出器１０３は、仮ラベルカウンタ
１０１から出力されるカウント値３（ＴＲ（３））と連
結テーブル１０２から読出されたデータ２（ＲＤ
（２））とを比較する。この場合、不一致検出が一致検
出器１０３により行なわれる。この一致検出器１０３に
おける一致検出動作と並行して、選択回路１０５ａが、
信号線１１２上に与えられたデータＲＤ（２）を選択し
て信号線１１１上に与える。連結テーブル１０２におい
ては、アドレス２の格納データ２が読出され、信号線１
１２上に与えられる。最終ラベルカウンタ１０４のカウ
ント値は更新されない。選択回路１０５ｂは、一致検出
器１１３からの不一致検出に従って、この信号線１１２
上の読出データＲＤ（２）を選択している。

【０３２５】選択回路１０５ａは、仮ラベルカウンタ１
０１からのカウント値３をアドレスとして選択して信号
線１１１上に与える。したがって連結テーブル１０２の
アドレス３の位置にデータ２が書込まれる。

【０３２６】仮ラベル値４に対しても、仮ラベル値３と
同様の処理が実行され、連結テーブル１０２のアドレス
４の位置に最終ラベル値２が書込まれる。この段階にお
いて、最終ラベルカウンタ４は、最終ラベル値３を保存
している。

【０３２７】仮ラベルカウンタ１０１のカウント値が１
増分されて仮ラベル値５に対する解析が開始される。こ
の場合、仮ラベル値１および２の場合と同様にして、一
致検出器３において一致が検出される。この場合、最終
ラベルカウンタ１０４のカウント値は３であり、連結テ
ーブル１０２のアドレス５の位置にはデータ３が書込ま
れる。最終ラベルカウンタ１０４のカウント値が３から
４に増分される。

【０３２８】仮ラベル値６に対しては、仮ラベル値３お
よび４と同様の処理が実行される。連結テーブル１０２
から読出されたデータは５である。このデータ５をアド
レスとして連結テーブル１０２からデータが再び読出さ
れる。このときに読出されたデータは３であり、このデ
ータ３が最終ラベルとして選択される。これにより、連
結テーブル１０２のアドレス６の位置にデータ３が書込
まれる。この結果、図６１（Ｃ）に示す記憶内容を備え
る連結テーブルが実現される。したがって、この連結テ
ーブル１０２を用いて、図５６に示す仮ラベル画像を順
次走査してラベル変換を実行すれば図５７に示す最終ラ
ベル画像を得ることができる。この図６２に示す場合、
連結テーブルの解析および統合処理は、すべてハードウ
ェアを用いて実行されている。これにより、高速で処理
を実行することができる。また記憶手段としては連結テ
ーブル以外用いられていないため、その装置規模も低減
することができる。

【０３２９】（ｖｉｉｉ） 第８の実施例 図６５はこの発明の第８の実施例において用いられる連
結テーブルのデータ構造を示す図である。図６５に示す
ように、連結テーブルのデータ構造は、ラベル値と１ビ
ットの解析フラグを１つの単位として備える。この解析
フラグは、最上位ビット位置に付け加えられる。この１
ビットの解析フラグは、連結テーブル解析処理動作時に
おいて、関連のラベル値が既処理であるか未処理である
かを示すために用いられる。仮ラベル付け動作時におい
て、この部分は利用されない。連結テーブル解析処理動
作初期時において、この解析フラグは未処理を示す状態
にセットされる。

【０３３０】図６６は、この発明の第８の実施例である
連結テーブル解析処理の動作を示すフロー図である。以
下、図６６を参照してこの発明の第８の実施例である連
結テーブル解析処理動作について説明する。

【０３３１】連結テーブルにおいては、データは最上位
ビット位置に解析フラグを格納し下位ビット位置にラベ
ル値を格納している。仮ラベル処理動作前の初期状態に
おいては、解析フラグ部分は未処理状態を示す値“０”
に設定されており、連結テーブルの各アドレス位置に
は、そのアドレス値に等しい値がラベル値として格納さ
れている。仮ラベル処理終了後においてもこの連結テー
ブルにおける解析フラグ部分の値は“０”であり、下位
ビット位置には、図５８に一例を示すように、連結先ラ
ベルが格納されている。

【０３３２】また、この第８の実施例においても、仮ラ
ベルを発生するため仮ラベルカウンタと、最終ラベル値
を発生するための最終ラベルカウンタが用いられる。ま
ず最終ラベルカウンタのカウント値が初期値として
“０”に設定される（ステップＳ２００）。次いで、仮
ラベル画像をラスタ走査し、このラスタ走査により得ら
れた仮ラベル値ｉを入力する（ステップＳ２０２）。

【０３３３】この仮ラベル値ｉをアドレスとして連結テ
ーブルからデータＭ（ｉ）を読出す（ステップＳ２０
４）。この読出データＭ（ｉ）は解析フラグを含んでい
る。この解析フラグが既処理状態を示しているか未処理
状態を示しているかを判定する（ステップＳ２０６）。

【０３３４】解析フラグが既処理状態を示している場
合、この仮ラベルについては既に解析が終了しているた
め、連結テーブルから読出されたデータＭ（ｉ）のラベ
ル値部分が最終ラベルとして出力される（ステップＳ２
０８）。

【０３３５】ステップＳ２０６において、解析フラグが
未処理状態を示している場合、仮ラベル値ｉと連結テー
ブルから読出されたデータＭ（ｉ）のラベル値との比較
が行なわれる（ステップＳ２１０）。仮ラベル値ｉと読
出データＭ（ｉ）のラベル値とが一致しているとき、最
終ラベルカウンタのカウント値が更新される（ステップ
Ｓ２１２）。この更新された最終ラベルカウンタのカウ
ント値ｊを、解析フラグを既処理状態にセットした状態
（制御コード）で連結テーブルのアドレス（ｉ）の位置
に書込む（ステップＳ２１４）。この書込動作と並行し
て、最終ラベルカウンタの出力するカウント値ｊを最終
ラベル値として出力する（ステップＳ２１６）。

【０３３６】ステップＳ２１０において、不一致と判定
された場合、読出データＭ（ｉ）をアドレスとして連結
テーブルから新たなデータＭ（Ｍ（ｉ））が読出される
（ステップＳ２１８）。次いで仮ラベル値ｉをアドレス
としてこの読出されたデータＭ（Ｍ（ｉ））を連結テー
ブルに書込む。このとき解析フラグは既処理状態を示す
値“１”に変更される（制御コードの変更として図６６
において示す）。これによりステップＳ２２０が完了す
る。

【０３３７】この連結テーブルへの書込と並行して、連
結テーブルから読出されたデータＭ（Ｍ（ｉ））のラベ
ル値部分が最終ラベル値として出力される（ステップＳ
２２２２）。

【０３３８】この一連の動作により、仮ラベル値ｉに対
する処理が完了すると、次の仮ラベル画像データの仮ラ
ベル値に対する処理が繰返し実行される。

【０３３９】すなわち、この図６６に示す処理動作にお
いては、先の第６の実施例の場合と異なり、仮ラベルカ
ウンタに代えて、仮ラベル画像を走査して得られた仮ラ
ベル値を入力し、この仮ラベル値を最終ラベル値に変換
して出力している。すなわち連結テーブルの解析と最終
ラベリング処理が同時に実行される。ここで、最終ラベ
リング処理とは、仮ラベル画像をラスタ走査して得られ
る仮ラベル値を入力として最終ラベル値に変換して出力
する処理を示す。次に、図５６ないし図５８を参照して
具体的処理動作について説明する。

【０３４０】連結テーブルには、図５８に示すデータが
各アドレスに格納されているとする。各データに対して
は、解析フラグが未処理状態を示す“０”として付され
ている。

【０３４１】今図５６に示す仮ラベル画像１００をラス
タ走査しすると、最初に現われる仮ラベル付けされた画
素２２４ａが出現する。この画素２２４ａの仮ラベル値
は１である。この値１をアドレスとして連結テーブルを
アクセスすると、解析フラグは０であり、連結テーブル
解析未処理状態を示している。この場合、入力仮ラベル
値１と連結テーブルデータのラベル値１との比較が実行
される。この場合、両者は１であり、一致しているた
め、最終ラベルカウンタのカウント値が更新されて１と
なる。この最終ラベルカウンタの更新されたカウント値
１と既処理状態を示す値“１”に変更された解析フラグ
とがリンクされたデータが連結テーブルの仮ラベル値１
をアドレスとする部分に書込まれる。また最終ラベルと
して、最終ラベルカウンタのカウント値１が出力され
る。

【０３４２】次に、仮ラベル画素１００の走査が１画素
右にシフトし、画素２２４ｂに対する処理が実行され
る。画素２２４ｂの仮ラベル値は１である。この仮ラベ
ル値１をアドレスとして連結テーブルをアクセスする。
連結テーブルのアドレス１の格納データは、既に画素２
２４ａに対する処理で最終ラベル値が決定しているた
め、その解析フラグは１である。したがって、この場
合、連結テーブルに対するデータ書込は実行されない。
連結テーブルから読出されたラベル値１が最終ラベル値
として出力される。画素２２４ｃに対しても全く同様の
処理が実行され、最終ラベル値１が出力される。

【０３４３】すなわち、一度解析されて解析フラグが１
になったデータを格納しているアドレス値に等しい仮ラ
ベル値に対しては、その格納データのラベル値部分が最
終ラベルとして出力される。続いて、仮ラベル画像２０
０における画素２２４ｄの仮ラベル値２に対しては、画
素２２４ａの場合と同様にして、最終ラベルカウンタの
カウント値が更新され、その値が２とされる。この更新
されたカウント値２が最終ラベル値として出力される。
この出力動作と並行して、解析フラグが１に設定され
て、最終ラベルカウンタのカウント値の２とリンクされ
たデータが連結テーブルの入力仮ラベル値２をアドレス
とする位置に書込まれる。

【０３４４】さらに走査が進み、画素２２４ｅに対する
処理が実行される。画素２２４ｅの仮ラベル値は３であ
る。連結テーブルのアドレス３はまだアクセスされてい
ない。したがってこのアドレス３の格納データに含まれ
る解析フラグは“０”である。したがってこの場合、仮
ラベル値３に対するテーブル解析が必要とされる。そこ
で、入力仮ラベル値３と連結テーブルから読出されたデ
ータのラベル値部分とが比較される。連結テーブルから
読出されたデータは２であり、入力仮ラベル値と連結テ
ーブルデータのラベル値とが異なっていることが検出さ
れる。連結テーブルデータの２は、仮ラベル値３の連結
先を表わしている。

【０３４５】この連結テーブルデータ２をアドレスとし
て連結テーブルを再びアクセスすると、既処理ラベルで
ある仮ラベル値２の最終ラベル値２が読出される。この
最終ラベル値２が仮ラベル値３の最終ラベルである。連
結テーブルに対しては、アドレス３の位置に最終ラベル
２と既処理状態を示す値１に変更されたフラグとがリン
クされたデータが書込まれる。解析フラグが変更された
ために、以後の走査で仮ラベル値３を入力すると無条件
に最終ラベル値２が出力される。

【０３４６】仮ラベル画像１００の画素２２４ｆ、２２
４ｇおよび２２４ｈの仮ラベルの変換処理は、それぞれ
各仮ラベル値がラスタ走査の過程で初めて現われる場合
の処理が実行される。この場合、連結テーブルから読出
されるデータの解析フラグ部分は、未処理状態を示して
いる。したがってこれらの画素２２４ｆ、２２４ｇおよ
び２２４ｈに対しては、画素２２４ａ、２２４ｄおよび
２２４ｅの場合と同様に、連結テーブルの解析、内容の
変更、および最終ラベル値の出力が実行される。

【０３４７】図５６に示す仮ラベル画像１００における
残りの画素については、既に連結テーブル解析が実行さ
れているため、連結テーブルから読出されたデータのラ
ベル値部分がそのまま最終ラベル値として出力される。
これにより、図６１（Ｃ）に示す連結テーブルが得られ
るとともに、図５７に示す最終ラベル画像１０１を得る
ことができる。

【０３４８】この第８の実施例においては、連結テーブ
ルの解析および統合処理と、最終ラベリング処理が同時
に実行されているため、高速でラベリング処理を実行す
ることが可能となる。

【０３４９】（ｉｘ） 第９の実施例 図６７は、この第８の実施例に示す処理動作をハードウ
ェアで実現するための構成を示す図である。図６７にお
いて、図６２に示す構成と対応する部分には同様の参照
番号を付す。この図６７に示す構成においては、連結テ
ーブル１０２に対するアドレスを生成するための選択回
路１０５ａに対しては、仮ラベル画素を走査している得
られる仮ラベル値ＴＬがその一方入力に与えられ、他方
入力には連結テーブル１０２から信号線１１２上に読出
されるデータＲＤが与えられる。この図６７に示す構成
においては、新たにデコーダ１０７およびレジスタ１０
６および最終ラベル値を出力するための出力回路１１９
が設けられる。また選択回路１０５ｂは、３入力１出力
の構成とされる。

【０３５０】デコーダ１０７は、一致検出器１０３から
信号線１１３上に与えられる信号と、連結テーブル１０
２から信号線１１２上に与えられた読出データの１ビッ
トの解析フラグをデコードし、そのデコード結果に従っ
て最終ラベルカウンタ１０４のカウントアップ動作およ
び選択回路１０５ｂの選択動作を制御する信号を発生す
る。デコーダ１０７のデコード動作は以下のとおりであ
る。

【０３５１】（ｉ） 解析フラグが“１”のとき：レジ
スタ１０６の格納データを選択する信号を信号線１１７
ｂに出力する。最終ラベルカウンタ１０４のカウントア
ップは禁止する。

【０３５２】（ｉｉ） 解析フラグが“０”でかつ一致
検出器１０３の出力が一致検出のとき：最終ラベルカウ
ンタ１０４の出力の選択させる信号を信号線１１７ｂに
出力し、次いで最終ラベルカウンタ１０４のカウント値
の更新のための信号を信号線１１７ａに出力する。

【０３５３】（ｉｉｉ） 解析フラグが“０”かつ一致
検出器１０３出力が不一致検出のとき：信号線１１２上
の信号を選択する信号を信号線１１７ｂに出力しかつ最
終ラベルカウンタ１０４のカウントアップを禁止する。

【０３５４】レジスタ１０６は、連結テーブル１０２か
ら信号線１１２上に１回目の読出動作において読出され
たデータＲＤを格納する。

【０３５５】選択回路１０５ｂは、最終ラベルカウンタ
１０４から信号線１１４上に与えられる最終ラベル値Ｆ
Ｌと、レジスタ１０６に格納されたデータＲＥと、連結
テーブル１０２から２回目の読出サイクルにおいて読出
されたデータとを受け、その１つをデコーダ１０７から
信号線１１７ｂ上に与えられた制御信号に従って選択し
て連結テーブル１０２へ信号線１１５を介して与えると
ともに出力回路１１９へ与える。出力回路１１９は、こ
の選択回路１０５ｂから与えられたデータのうちラベル
値に対応する部分を最終ラベル値として出力する。この
選択回路１０５ｂはまた、デコーダ１１７ｂの制御の下
に解析フラグを処理済みの“１”の値に設定して出力す
る。このとき、選択回路１０５ｂは、最終ラベルカウン
タ１０４からのカウント値ＦＬに既処理状態を示す解析
フラグを付加して出力する構成が用いられてもよい。ま
た、最終ラベルカウンタ１０４のカウント値としてはそ
の最上位ビットが常時“０”に設定されたカウント値が
利用されてもよい。書込データ用信号線１１５の最上位
ビット位置がデータ書込時“１”に設定されればよい。
次にこの図６７に示す回路の動作をその動作波形図であ
る図６８ないし図７０を参照して説明する。

【０３５６】また、図６７および図６８を参照して、入
力仮ラベル値が既処理状態の場合の動作について説明す
る。信号線１１０上に仮ラベル値ＴＬ（ｉ）が与えられ
ると、まず選択回路１０５ａはこの仮ラベル値ＴＬ
（ｉ）を選択して連結テーブル１０２へ与える。連結テ
ーブル１０２においては、この仮ラベル値ＴＬ（ｉ）を
アドレスとしてデータの読出が実行される。連結テーブ
ル１０２から読出されたデータＲＤ（ｎ）に含まれる解
析フラグが既処理状態を示す“１”のとき、デコーダ１
０７は、最終ラベルカウンタ１０４のカウント値を維持
させる信号を信号線１１７ａ上に与えるとともに、選択
回路１０５ｂに対しレジスタ１０６に格納されたデータ
ＲＥを選択する信号を信号線１１７ｂ上に与える。レジ
スタ１０６においては、連結テーブル１０２から読出さ
れたデータＲＤ（ｎ）が格納されている。この選択回路
１０５ｂにおいて選択された信号は出力回路１１９へ与
えられる。出力回路１１９は、適当なタイミングでこの
選択回路１０５ｂから与えられたラベル値ＲＥ（ｎ）を
最終ラベル値として出力する。

【０３５７】選択回路１０５ａは、所定のタイミングで
連結テーブル１０２から読出されるデータＲＤ（ｎ）を
選択して信号線１１１へ与え、データＲＤ（Ｐ）を読出
し、次いで入力仮ラベル値ＴＬ（ｉ）を選択して信号線
１１１へ与える。連結テーブル１０２においては、この
仮ラベル値ＴＬ（ｉ）をアドレスとして、選択回路１０
５ｂから出力されたデータＲＥ（ｎ）が書込データＷＤ
として書込まれる。これらの２回目の読出動作およびデ
ータ書込動作は解析フラグが“１”の場合特に必要では
ない。単に解析フラグが“０”の未処理状態を示す場合
の動作との並列性を保つために、図６８においては、選
択回路１０５ａが順次所定のタイミングで選択動作を実
行し、連結テーブル１０２に対する読出動作および書込
動作が実行されるように示される。

【０３５８】次に、図６７および図６９を参照して、連
結テーブル１０２から読出されたデータに含まれる解析
フラグが未処理状態を示す“０”のときの動作について
説明する。まず、図６７および図６９を参照して、連結
テーブルのアドレスと格納データのラベルとの値が等し
い場合の動作について説明する。

【０３５９】まず、入力仮ラベル値ＴＬ（ｉ）が選択回
路１０５ａにより選択されて信号線１１１を介して連結
テーブル１０２へ与えられる。連結テーブル１０２は、
この入力仮ラベル値ＴＬ（ｉ）をアドレスとしてデータ
を読出し、読出データＲＤ（ｉ）を信号線１１２上に伝
達する。この信号線１１２上に与えられたデータＲＤ
（ｉ）はレジスタ１０６に格納される。このレジスタ１
０６へのデータ格納動作と並行して、一致検出器１０３
においては、信号線１１２上に読出されたデータＲＤ
（ｉ）のラベル値と入力仮ラベル値ＴＬ（ｉ）の一致／
不一致が検出される。今、ＴＬ（ｉ）＝ＲＤ（ｉ）であ
るため、一致検出器１０３からは信号線１１３上に一致
検出信号が出力される。またこの信号線１１２上に読出
されたデータＲＤ（ｉ）の解析フラグが信号線１１６を
介してデコーダ１０７へ与えられる。デコーダ１０７
は、この一致検出器１０３からの一致検出信号に応答し
て、選択回路１０５ｂに対し、最終ラベルカウンタ１０
４のカウント値を選択させる信号を出力する。またデコ
ーダ１０７は、最終ラベルカウンタ１０４のカウント値
を所定のタイミングで更新させる。最終ラベルカウンタ
１０４の初期値は“１”に設定されている。選択回路１
０５ｂはこの最終ラベルカウンタ１０４の出力するカウ
ント値ＦＬ（ｋ）を選択して出力回路１１９および信号
線１１５上に与える。

【０３６０】一方、デコーダ１０７におけるデコード動
作と並行して、選択回路１０５ａは、連結テーブルから
読出されたデータＲＤ（ｉ）を選択して連結テーブル１
０２へ与える。連結テーブル１０２においては、このデ
ータＲＤ（ｉ）をアドレスとしてその記憶内容が読出さ
れ、選択回路１０５ｂへ与えられる。この２回目に読出
されたデータＲＤ（ｉ）はレジスタ１０６には格納され
ない。

【０３６１】選択回路１０５ｂからは最終ラベルカウン
タ１０４の更新前のカウント値ＦＬ（ｋ）と既処理状態
を示す解析フラグ（“１”）とがリンクされて信号線１
１５上に与えられている。選択回路１０５ａが再び入力
仮ラベル値ＴＬ（ｉ）を選択して連結テーブル１０２へ
与えると、連結テーブル１０２は、この入力仮ラベル値
ＴＬ（ｉ）をアドレスとして、信号線１１５上に与えら
れたデータＦＬ（ｋ）および解析フラグ“１”をリンク
して格納する。

【０３６２】この書込動作と並行してデコーダ１０７か
らの信号線１１７ａ上に与えられた信号に従って最終ラ
ベルカウンタ１０４のカウント値が１増分されてＦＬ
（ｋ＋１）となる。

【０３６３】出力回路１１９からは、所定の適当なタイ
ミングで選択回路１０５ｂから与えられたデータのうち
解析フラグを除く部分すなわち最終ラベルカウンタのカ
ウント値ＦＬ（ｋ）が最終ラベル値として出力される。

【０３６４】次に、図６７および図７０を参照して、解
析フラグが“０”であり、また連結テーブルのアドレス
と格納データのラベル値とが不一致の場合の動作につい
て説明する。

【０３６５】まず入力仮ラベル値ＴＬ（ｉ）が入力され
る。選択回路１０５ａがこの入力仮ラベル値ＴＬ（ｉ）
を選択して連結テーブル１０２へ与える。連結テーブル
１０２においては、アドレスＴＬ（ｉ）に格納されたデ
ータＲＤ（ｊ）が読出されて信号線１１２上に出力され
る。この信号線１１２上に与えられたデータＲＤ（ｊ）
はレジスタ１０６に格納される。

【０３６６】このレジスタ１０６への格納動作と並行し
て、一致検出器１０３においては、読出データＲＤ
（ｊ）と入力仮ラベル値ＴＬ（ｉ）の一致／不一致の検
出が実行される。この場合、一致検出器１０３は、信号
線１１３上に不一致検出信号を与える。

【０３６７】デコーダ１０７は、信号線１１２上に与え
られたデータＲＤ（ｊ）の解析フラグを信号線１１６へ
介して与える。デコーダ１０７は、解析フラグが未処理
状態を示す“０”であり、一致検出器１０３が不一致検
出を示しているときには、最終ラベルカウンタ１０４の
カウントアップ動作を禁止するとともに、選択回路１０
５ｂに対し、信号線１１２上のデータを選択する状態に
設定する制御信号を信号線１１７ｂを介して与える。

【０３６８】このデコーダ１０７におけるデコード動作
と並行して、選択回路１０５ａは、連結テーブル１０２
から読出されたデータＲＤ（ｊ）を選択して信号線１１
１上に与える。連結テーブル１０２においては、このデ
ータＲＤ（ｊ）をアドレスとしてデータ読出動作が行な
われ、対応のデータＲＤ（ｍ）が信号線１１２を介して
選択回路１０５ｂへ与えられる。選択回路１０５ｂは、
この信号線１１２を介して与えられたデータＲＤ（ｍ）
の解析フラグを既処理状態を示す“１”に変更して信号
線１１５上に与える。

【０３６９】この選択回路１０５ｂから信号線１１５上
に書込データＲＤ（ｍ）が与えられるのと並行して、選
択回路１０５ａが入力仮ラベル値ＴＬ（ｉ）を選択して
連結テーブル１０２へ与える。連結テーブル１０２にお
いては、入力仮ラベル値ＴＬ（ｉ）をアドレスとして、
信号線１１５上に与えられたデータＲＤ（ｍ）を書込デ
ータとする書込動作が実行される。

【０３７０】なお、図７０に示す構成においては、選択
回路１０５ｂは、解析フラグが有効状態となって一致検
出器１０３の出力が確定した後、デコーダ１０７の出力
に従って、信号線１１２を選択する状態に設定されてい
る。このため、選択回路１０５ｂからは、まずデータＲ
Ｄ（ｊ）が出力され、続いてデータＲＤ（ｍ）が出力さ
れた状態が示される。出力回路１１９からは、これに応
じて最終ラベル値としてデータＲＤ（ｊ）およびＲＤ
（ｍ）が出力される状態が示される。データＲＤ（ｍ）
のみが有効である。この選択回路１０５ｂおよび出力回
路１１９の出力確定タイミングは、連結テーブル１０２
に対しデータを書込むタイミングより前に確定していれ
ばよく、適当なタイミングに設定されればよい。

【０３７１】次に、この図６７に示す回路の動作を、図
５６に示す仮ラベル画像を参照して説明する。連結テー
ブル１０２の状態は、図５８に示す状態と同一であると
する。各データに対しては、解析フラグが付加されてい
る。これらの解析フラグはすべて未処理状態を示す
“０”である。まず、仮ラベル画像１００をラスタ走査
していく過程で、最初に画素２２４ａが検出される。こ
の画素２２４ａの仮ラベル値は“１”である。この入力
仮ラベル値“１”は選択回路１０５ａにより選択されて
連結テーブル１０２へ与えられる。連結テーブル１０２
からは、アドレス１に格納されたデータが読出される。
この連結テーブル１０２から読出されるデータＲＤ
（１）は、レジスタ１０６に一時的に記憶される。デー
タＲＤ（１）のラベル値部分は選択回路１０５ａおよび
一致検出器１０３に与えられる。データＲＤ（１）の最
上位ビットである解析フラグはデコーダ１０７へ与えら
れる。読出されたデータＲＤ（１）のラベル値は“１”
のであり、解析フラグは未処理状態を示す“０”であ
る。一致検出器１０３は、この場合、入力仮ラベル値Ｔ
Ｌ（１）と連結テーブルデータのＲＤ（１）のラベル値
が等しいというコードをデコーダ１０７へ信号線１１３
を介して与える。デコーダ１０７は、この解析フラグと
ラベル値の比較結果とから最終ラベルとして新しいラベ
ル値すなわち最終ラベルカウンタ１０４のカウント値を
出力するための信号を発生し、信号線１１７ａおよび１
１７ｂを介して最終ラベルカウンタ１０４および選択回
路１０５ｂへ与える。

【０３７２】このデコーダ１０７のデコード動作と並行
して、選択回路１０５ａは、読出されたデータＲＤ
（１）のラベル値を選択して連結テーブル１０２へ与え
る。連結テーブル１０２において、このデータＲＤ
（１）のラベル値をアドレスとしてデータの再読出しを
実行する。この再び読出されたデータＲＤ（１）はレジ
スタ１０６には格納されず、選択回路１０５ｂへ与えら
れる。

【０３７３】最終ラベルカウンタ１０４のカウント値
は、仮ラベルの最小値１に初期設定されている。選択回
路１０５ｂは、このデコーダ１０７から信号線１１７ｂ
を介して与えられる制御信号に応答して、最終ラベルカ
ウンタ１０４が保持するカウント値ＦＬ（１）を選択し
て出力する。この選択回路１０５ｂから出力されるデー
タは、連結テーブル１０２のデータ構造を備える。この
選択回路１０５ｂの出力に含まれる解析フラグは既処理
状態を示す値“１”に設定される。出力回路１１９は、
このデータのうちラベル値１のみを選択して出力する。
最終ラベルカウンタ１０４は、選択回路１０５ｂにおけ
る選択動作の完了の後、そのカウント値が１カウントア
ップされ、２となる。

【０３７４】選択回路１０５ａは、再び入力仮ラベル値
ＴＬ（１）を選択して信号線１１１上に与える。連結テ
ーブル１０２は、この信号線１１１上に与えられた入力
仮ラベル値ＴＬ（１）を書込アドレスとし、信号線１１
５上に与えられたデータＦＬ１）と解析フラグ
（“１”）とを書込データＷＤとして書込む。

【０３７５】上述のように、１つの入力仮ラベルに対し
て、（ａ）仮ラベル値入力、（ｂ）連結テーブルからの
データの読出、（ｃ）一致検出、デコード動作および読
出データのラベル値による連結テーブルからの再読出、
（ｄ）選択回路１０５ｂによる選択出力、（ｅ）連結テ
ーブル１０２へのデータの書込、の５つのステップが必
要とされる。

【０３７６】次にラスタ走査が１画素右にシフトし、図
５６に示す仮ラベル画像１００に含まれる画素２２４ｂ
の仮ラベル値１が入力される。連結テーブル１０２か
ら、アドレス１のデータが読出される。この読出された
データＲＤ（１）は、画素２２４ａに対する連結テーブ
ル解析フラグが既処理状態を示す“１”であり、ラベル
値が“１”の構成を備える。デコーダ１０７は、この解
析フラグの値“１”に従って、連結テーブルから最初に
読出されたデータを格納するレジスタ１０６の出力を選
択する信号を信号線１１７ｂを介して選択回路１０５ｂ
へ与える。これにより、出力回路１１９からは、最終ラ
ベル値１が出力される。

【０３７７】画素２２４ｃおよび以後のラスタ走査で入
力仮ラベル値が“１”の場合には、画素２２４ｂに対す
る処理と同様の処理が実行される。

【０３７８】画素２２４ｄに対する仮ラベル値２が入力
されると、この仮ラベル値２は初めて処理されるラベル
値である。このとき、入力仮ラベル値２と連結テーブル
のアドレス２の格納データのラベル値２とが等しいた
め、画素２２４ａと全く同じ処理が実行される。最終ラ
ベル値２が出力される。連結テーブル１０２のアドレス
２の位置に解析フラグ１およびラベル値２のデータが書
込まれる。また、最終ラベルカウンタ１０４は、その値
が更新されて３となる。

【０３７９】仮ラベル画像１００の走査が進み、画素２
２４ｅの仮ラベル値３が入力されると、対応して連結テ
ーブル１０２から読出されたデータの解析フラグが０で
あり、また対応するラベル値は２であり、入力仮ラベル
値と異なっている。すなわち、入力仮ラベル値３は、そ
の値よりも小さい仮ラベル２に連結していることが検出
される。この仮ラベル値３と直接連結している仮ラベル
値２を媒体として、間接的に連結している仮ラベル値を
連結テーブル１０２から検出する必要がある。この検出
動作が２度目の連結テーブル読出動作に対応する。連結
テーブルから２度目に読出されたデータは、１度目の読
出データのラベル値２をアドレスとして読出されたデー
タである。アドレス２の格納データの解析フラグは既処
理状態を示す“１”である。すなわち、このアドレス２
に対応する仮ラベル値２の解析処理は、既に画素２２４
ｄに対する処理で終了している。したがって、このラベ
ル値２が仮ラベル値３の最終ラベル値となる。デコーダ
１０７は、選択回路１０５ｂに対し、連結テーブルから
２回目に読出されたデータを選択して出力する信号を信
号線１１７ｂを介して与える。出力回路１１９は、この
選択回路１０５ｂから与えられたデータのうちラベル値
部分２を最終ラベル値として出力する。連結テーブル１
０２のアドレス３の位置には、解析フラグ１、ラベル値
２のデータが書込まれる。

【０３８０】画素２２４ｆ、２２４ｇ、および２２４ｈ
の入力仮ラベル値に対する処理は、それぞれ各仮ラベル
値がラスタ走査の過程で初めて現われる場合である。こ
れらの画素の入力仮ラベル値に対応して、連結テーブル
１０２から読出されるデータに含まれる解析フラグは未
処理状態を示している。したがってこれらの画素２２４
ｆ、２２４ｇおよび２２４ｈに対しては、画素２２４
ａ、２２４ｄおよび２２４ｅと同様の連結テーブルの解
析、変更および最終ラベル値の出力が実行される。

【０３８１】残りの画素については、既に連結テーブル
解析が実行されているため、連結テーブルから最初に読
出されたデータがそのまま最終ラベルとして出力され
る。したがって、この処理の結果図５７に示すような最
終ラベル画像を得ることができ、また連結テーブル１０
２の状態は図６１（Ｃ）に示す状態となっている。

【０３８２】上述のように、連結テーブルの解析ととも
に、仮ラベル値の最終ラベルへの変換をハードウェアを
用いて実行することにより、高速でラベリング処理を実
行することができる。また、記憶装置としては、連結テ
ーブルのみが用いられているため、装置規模を小さくす
ることができる。

【０３８３】（ｘ） 第１０実施例 図７１はこの発明の第１０の実施例であるラベリング回
路の構成を示す図である。この図７１に示す構成の要部
は図６７に示すラベリング回路の構成と同様である。図
７１に示す構成においては、外部クロック信号を周波数
逓倍する周波数逓倍回路１３０が設けられている。この
周波数逓倍回路１３０からの出力するクロック信号がタ
イミングコントローラ１２０へ与えられる。この周波数
逓倍回路１２０へ与えられる外部クロックは、仮ラベル
値入力のサイクルを規定する信号である。仮ラベル値か
らなる仮ラベル画像が画像メモリなどの記憶手段に格納
されており、この仮ラベル画像記憶手段から順次外部ク
ロック信号に従って仮ラベル値読出されてこの回路へ与
えられる。この仮ラベル値の入力サイクルを規定する外
部クロック信号を周波数逓倍して内部回路の動作タイミ
ングを決定する信号を生成する。これにより、正確なタ
イミングでかつ高速で処理を実行することができる。

【０３８４】すなわち、１つの仮ラベル入力に対して、
連結テーブル解析および最終ラベリングの同時並列処理
に必要とされるのは前述のごとく以下の５ステップを含
む：（ａ）仮ラベル値の入力、（ｂ）連結テーブルのデ
ータの読出、（ｃ）一致検出の後デコードおよび連結テ
ーブルからの読出データのラベル値による再読出、
（ｄ）選択回路による最終ラベル値の選択および出力、
（ｅ）連結テーブルへの最終ラベル値の書込：これらの
５ステップがそれぞれ１クロックサイクルで処理される
とすると、仮ラベル値データは５クロックサイクルに対
し１回の割合で入力されればよい。

【０３８５】周波数逓倍回路１３０は、仮ラベル画像を
走査して画素を読出す周波数に等しい周波数を備える外
部クロック信号を入力とし、そのクロックと位相が同期
しかつ周波数が５倍とされた内部クロック信号を生成す
る。内部タイミングコントローラ１２０は、この周波数
を逓倍回路１３０からの内部クロックに従って所定の各
回路の動作タイミングを決定する信号を発生する。した
がって、この場合、外部クロックに同期して動作する回
路と比べて５倍の速さでこの図７１に示す内部回路が動
作する。

【０３８６】この場合、図７２に示すように、内部クロ
ックの各クロックサイクルにおいて５つの処理ステップ
（ａ）〜（ｅ）がそれぞれ実行される。各回路の処理動
作がパイプライン化されるため、高速で処理を実行する
ことができる。内部回路をクロック信号に同期して動作
をさせる場合、適当な位置にクロックに応答して動作す
るラッチ回路が設けられておればよい。

【０３８７】この図７１に示す回路の動作は、周波数逓
倍回路を除けば図６７に示す回路と同じであり、単にそ
の処理周波数が異なっているだけであり、処理結果は全
く同様である。

【０３８８】周波数逓倍回路１３０としては、図５４に
示す回路構成を利用することができる。

【０３８９】

【０３９０】

【０３９１】

【０３９２】

【０３９３】

【０３９４】

【０３９５】

【０３９６】

【０３９７】請求項１に係る発明に従えば、連結テーブ
ル解析用連結テーブルのアドレスとその格納データとの
比較結果に従って連結テーブルの書換を行なうことによ
り実行するため、その処理が単純となるとともに、変換
テーブルが必要とされずに記憶領域も低減され、装置規
模が低減される。

【０３９８】請求項２に係る発明に従えば、連結テーブ
ルのアドレスと格納データとの比較結果に従って連結テ
ーブルの書換をハードウェアで行なって連結テーブル解
析を実行しているため、ソフトウェア処理の負担が軽減
され高速にラベリング処理を実行することができるとと
もに、変換テーブルが必要とされず、記憶領域も低減さ
れる。

【０３９９】請求項３に係る発明に従えば、仮ラベル画
像を走査して得られる仮ラベル値を連結テーブルに対す
るアドレス入力とし、この入力アドレスと連結テーブル
データに含まれる解析フラグおよびラベル値を検査して
連結テーブルの書換を行なうことにより連結テーブルの
解析を実行するとともに、仮ラベル値の最終ラベルへの
変換をも実行するため、ラベリング処理が単純化される
とともに高速となるとともに、変換テーブルが必要とさ
れず、記憶領域も低減される。

【０４００】請求項４に係る発明に従えば、仮ラベル画
像を走査して得られる仮ラベル値を連結テーブルに対す
るアドレス入力として用い、この連結テーブルのアドレ
スと連結テーブルの格納データの解析フラグおよびラベ
ル値を検査して連結テーブルの書換によって連結テーブ
ルの解析を行なうとともに、最終ラベリング動作をもす
べてハードウェアを用いて実行するため、ソフトウェア
処理の負担が軽減されて高速に処理を実行することがで
きるとともに、記憶領域も低減することができる。

【０４０１】請求項５に係る発明に従えば、請求項４に
おけるハードウェアの動作を、仮ラベル値入力サイクル
を規定する外部クロック信号を周波数逓倍して内部回路
の動作タイミングを規定しているため、内部回路をパイ
プライン化することができ、高速で処理を実行すること
ができる。

【図面の簡単な説明】

【図１】この発明の第１の実施例であるラベリング方式
の処理手順を示すフロー図である。

【図２】この発明の第１の実施例において利用される連
結テーブルの内容の初期状態を示す図である。

【図３】この発明の第１の実施例における二値マスクの
走査時における二値画像の態様を示す図である。

【図４】第１の実施例におけるラベリング方式における
二値マスクの走査時における二値画像の態様を示す図で
ある。

【図５】第１の実施例における二値マスクの走査時にお
ける二値画像の態様を示す図である。

【図６】第１の実施例における二値マスクの走査時にお
ける二値画像の態様を示す図である。

【図７】第１の実施例における二値マスクの走査時にお
ける二値画像の態様を示す図である。

【図８】第１の実施例における二値マスクの走査時にお
ける二値画像の態様を示す図である。

【図９】第１の実施例における二値マスクの走査時にお
ける二値画像の態様を示す図である。

【図１０】第１の実施例における二値マスクの走査時に
おける二値画像の態様を示す図である。

【図１１】第１の実施例における二値マスクの走査時に
おける二値画像の態様を示す図である。

【図１２】図１１に示す二値マスク走査時における連結
テーブルの内容を示す図である。

【図１３】第１の実施例における第２行および第３行走
査完了時における二値画像の各画素のラベルの分布を示
す図である。

【図１４】第１の実施例における二値マスク走査時にお
ける二値画像の態様を示す図である。

【図１５】図１４に示す二値マスク走査時における連結
テーブルの内容を示す図である。

【図１６】第１の実施例における二値マスク走査時にお
ける二値画像の態様を示す図である。

【図１７】第１の実施例における二値マスク走査時にお
ける二値画像の態様を示す図である。

【図１８】図１７に示す二値マスクの走査時における連
結テーブルの内容を示す図である。

【図１９】第１の実施例における二値マスク走査時にお
ける二値画像の態様を示す図である。

【図２０】第１の実施例における二値マスク走査完了時
における仮ラベル画像の態様を示す図である。

【図２１】ラベル統合処理完了後におけるリラベリング
された二値画像のラベルの分布を示す図である。

【図２２】第１の実施例であるラベリング方式が適用さ
れる他の二値画像の態様を示す図である。

【図２３】図２２に示す他の二値画像に対するラベリン
グ処理において用いられる連結テーブルの内容を示す図
である。

【図２４】二値マスク走査時における他の二値画像の態
様およびそのときの連結テーブルの内容を示す図であ
る。

【図２５】他の二値画像の二値マスク走査時における態
様およびそのときの連結テーブルの内容を示す図であ
る。

【図２６】他の二値画像に対する二値マスク走査時にお
ける態様およびそのときの連結テーブルの内容を示す図
である。

【図２７】他の二値画像における二値マスク走査完了時
におけるラベルの分布を示す図である。

【図２８】他の二値画像に対する二値マスク走査完了時
における連結テーブルの内容を示す図である。

【図２９】図２８に示す連結テーブルを用いてリラベリ
ングを行なった際の二値画像の態様を示す図である。

【図３０】この発明の第２の実施例であるラベリング回
路の全体の構成を示す図である。

【図３１】図３０に示すランラベル記憶制御部の構成の
一例を示す図である。

【図３２】図３０に示すランラベル読出制御部の具体的
構成の一例を示す図である。

【図３３】図３０に示す連結ラベル記憶部の具体的構成
の一例を示す図である。

【図３４】図３０に示す仮ラベル送出制御部の具体的構
成の一例を示す図である。

【図３５】図３０に示す仮ラベル送出部の具体的構成の
一例を示す図である。

【図３６】図３０に示す統合処理部に含まれる連結テー
ブルの具体的構成の一例を示す図である。

【図３７】図３０に示す統合ラベル送出部の具体的構成
およびその論理を示す図である。

【図３８】図３０に示す仮ラベル選択制御部の具体的構
成の一例を示す図である。

【図３９】図３０に示す仮ラベルセレクタの具体的構成
の一例を示す図である。

【図４０】この発明の第３の実施例であるラベリング回
路の全体の構成を示す図である。

【図４１】第３の実施例であるラベリング回路が生成す
る二値マスクの構成を示す図である。

【図４２】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図４３】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図４４】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図４５】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図４６】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図４７】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図４８】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図４９】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図５０】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図５１】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図５２】第３の実施例であるラベリング回路の動作時
における二値画像の態様を示す図である。

【図５３】この発明の第４の実施例であるラベリング回
路の全体の構成を示す図である。

【図５４】図５３に示す位相同期回路の具体的構成およ
びその動作波形を示す図である。

【図５５】この発明の第５の実施例であるラベリング回
路の全体の構成を示す図である。

【図５６】第６の実施例において用いられる仮ラベル画
像を示す図である。

【図５７】図５６の仮ラベル画像から得られる最終ラベ
ル画像を示す図である。

【図５８】この発明の第６の実施例において用いられる
仮ラベル付加処理後の連結テーブルの状態を示す図であ
る。

【図５９】この発明の第６の実施例であるラベリング方
法の動作を示すフロー図である。

【図６０】この発明の第６の実施例であるラベリング方
法の動作を説明するための図である。

【図６１】この発明の第６の実施例であるラベリング方
法の動作を説明するための図である。

【図６２】この発明の第７の実施例であるラベリング回
路の構成を概略的に示す図である。

【図６３】図６２に示すラベリング回路の動作を示す信
号波形図である。

【図６４】図６２に示すラベリング回路の動作を示す信
号波形図である。

【図６５】この発明の第８の実施例において用いられる
連結テーブルのデータ構造を示す図である。

【図６６】この発明の第８の実施例であるラベリング方
法の動作を示すフロー図である。

【図６７】この発明の第９の実施例であるラベリング回
路の構成を概略的に示す図である。

【図６８】図６７に示すラベリング回路の動作を示す信
号波形図である。

【図６９】図６７に示すラベリング回路の動作を示す信
号波形図である。

【図７０】図６７に示すラベリング回路の動作を示す信
号波形図である。

【図７１】この発明の第１０の実施例であるラベリング
回路の構成を示す図である。

【図７２】図７１に示すラベリング回路の動作態様を説
明するための図である。

【図７３】一般的なラベリング処理を伴う視覚認識シス
テムの構成を示す図である。

【図７４】二値化処理およびラベリング処理を説明する
ための図である。

【図７５】ラベリング処理を説明するための図である。

【図７６】ラベリング処理時において用いられる局所画
像領域を抽出するための二値マスクの構成を示す図であ
る。

【図７７】従来のラベリング回路の全体の構成を示すで
ある。

【図７８】従来のラベリング回路の動作を示すために用
いられる二値画像の態様を示す図である。

【図７９】従来のラベリング回路の動作時における二値
画像の態様を示す図である。

【図８０】従来のラベリング回路の動作時における二値
画像の態様を示す図である。

【図８１】従来のラベリング回路の動作時における二値
画像の態様を示す図である。

【図８２】従来のラベリング回路の動作時における二値
画像の態様を示す図である。

【図８３】従来のラベリング回路の動作時における二値
画像の態様を示す図である。

【図８４】ラベリング処理の結果得られるラベル付けさ
れた画像の態様を示す図である。

【図８５】従来のラベル統合処理に用いられる連結テー
ブルの内容を示す図である。

【図８６】従来のラベリング方式による連結テーブルを
用いてラベル統合処理を行なったときに得られるラベル
付けされた画像の態様を示す図である。

【符号の説明】

１ マスク構成部 ２ 仮マスク決定部 ３ 統合ラベル送出部 ４ 統合処理部 ５ ランラベル記憶部 ６ ランラベル記憶制御部 ７ 連結ラベル記憶部 １０ １ビットラインバッファ １１ａ〜１１ｆ １ビットレジスタ １２ ランラベル読出制御部 １３ 仮ラベル選択制御部 １４ 仮ラベルセレクタ １６ 仮ラベル送出部 １８ 新ラベルカウンタ １９ 位相同期回路 １０１ 仮ラベルカウンタ １０２ 連結テーブル １０３ 一致検出器 １０４ 最終ラベルカウンタ １０５ａ，１０５ｂ 選択回路 １０６ レジスタ １０７ デコーダ １１９ 出力回路 １２０ タイミングコントローラ １３０ 周波数逓倍回路

フロントページの続き (56)参考文献 特開 平２−48778（ＪＰ，Ａ) 特開 昭62−9478（ＪＰ，Ａ) 特開 昭62−122388（ＪＰ，Ａ) 特開 昭63−102458（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06T 7/00 - 7/60

Claims (5)

(57)【特許請求の範囲】
1. 【請求項１】 局所画像領域により画像データを走査し
   て各画像データにラベルを付加するラベリング方法であ
   って、 （ａ） 同一の画像領域に複数のラベルが連結している
   とき前記複数のラベルのうちの最も小さいラベル値を以
   後の走査において伝搬させるべきラベルとして選択する
   ステップと、 （ｂ） 前記選択されたラベル値をデータとし、非選択
   とされたラベル値をアドレスとしてテーブルの形態で記
   憶するステップと、 （ｃ） 前記ステップ（ａ）および（ｂ）を繰返し実行
   し、各画像データに一時的ラベルを割当てるステップ
   と、 （ｄ） 前記テーブルの第１のアドレス値と前記第１の
   アドレスに格納された第１のデータとの比較を行なうス
   テップと、 （ｅ） 前記比較ステップ（ｄ）の比較結果が、前記第
   １のアドレス値と前記第１のデータとが等しいことを示
   すとき、新しいラベル値を前記第１のアドレスの格納内
   容として前記テーブルへ書込むステップと、 （ｆ） 前記比較ステップ（ｄ）の比較結果が前記第１
   のアドレス値と前記第１のデータとが異なることを示す
   とき、前記第１のデータをアドレスとして前記テーブル
   に記憶された第２のデータを前記テーブルの前記第１の
   アドレスへ格納するステップと、 （ｇ） 前記ステップ（ｃ）の完了後、前記ステップ
   （ｄ）ないし（ｆ）を前記テーブルの最小のアドレス値
   から順次繰返し実行するステップとを含む、ラベリング
   方法。
2. 【請求項２】 局所画像領域により画像データを走査
   し、各画像データにラベルを付加するためのラベリング
   回路であって、 前記走査時に、同一画像領域に複数のラベルが連結して
   いるとき、前記複数のラベルのうち最小のラベル値をデ
   ータとし、非選択のラベル値をアドレスとして記憶する
   ラベル記憶手段と、 前記ラベルの最小のラベル値を初期値として順次カウン
   トアップ動作する第１のカウンタ手段と、 前記第１のカウンタ手段の出力カウント値をアドレスと
   して前記ラベル記憶手段の第１のデータを読出し、前記
   第１のデータと前記第１のカウンタ手段の出力カウント
   値とを比較する比較手段と、 前記ラベルの最小値を初期値としてカウントアップ動作
   する第２のカウンタ手段と、 前記比較手段の一致検出に応答して、前記第１のカウン
   タ手段の出力のカウント値をアドレスとして前記第２の
   カウンタ手段の出力カウント値を前記ラベル記憶手段に
   記憶するとともに前記第２のカウンタ手段のカウント値
   を増分する手段と、 前記比較手段の不一致検出に応答して、前記ラベル記憶
   手段の前記第１のデータをアドレスとする位置に記憶さ
   れた第２のデータを、前記第１のカウンタ手段の出力カ
   ウント値をアドレスとして前記ラベル記憶手段へ記憶す
   る手段とを含む、ラベリング回路。
3. 【請求項３】 画像データに対して局所画像領域を走査
   して、各画像データにラベルを付加するラベリング方法
   であって、 前記走査において、同一画像領域に対し複数のラベルが
   連結している場合には、前記複数のラベルのうちラベル
   値の小さいラベルを以後の走査において伝搬させるラベ
   ル値として採用し、各画像データに対し一時的ラベルを
   付加するステップと、 前記採用されたラベル値をデータとしかつ非選択のラベ
   ル値をアドレスとしてテーブルに書込むステップと、 前記テーブルの記憶データそれぞれに対し、初期状態に
   おいて未処理状態を示す状態に設定されるフラグを付加
   するステップと、 前記一時的ラベルが付された画像データを走査し、該画
   像データに付されたラベルを第１のアドレスとして前記
   テーブルからラベル値およびフラグを含む第１のデータ
   を読出すステップと、 前記第１のデータのフラグが既処理状態を示すとき、前
   記第１のデータのラベル値を最終ラベル値として出力す
   るステップと、 前記第１のデータのフラグが未処理状態を示すとき、前
   記第１のデータのラベル値と前記第１のアドレス値とを
   比較するステップと、 前記比較ステップにおいて等しいことが示されたとき、
   新しいラベル値と既処理状態を示すフラグとが連結され
   た第２のデータを前記テーブルの前記第１のアドレス位
   置に記憶しかつ前記新しいラベル値を最終ラベル値とし
   て出力するステップと、 前記比較ステップにおいて異なることが示されたとき、
   前記テーブルの前記第１のデータをアドレスとする位置
   に格納された第２のデータを前記テーブルの前記第１の
   アドレス位置に記憶するとともに前記第２のデータのラ
   ベル値を最終ラベル値として出力するステップとを備え
   る、ラベリング方法。
4. 【請求項４】 画像データに対し局所画像領域を走査
   し、各画像データに一時的ラベルを付加して生成された
   一時的ラベル画像から最終ラベル画像を生成するための
   ラベリング回路であって、 前記走査時に、同一画像領域に複数のラベルが連結して
   いるとき、最小のラベル値を書込データとし、非選択の
   ラベル値をアドレスとして記憶するとともに、各記憶デ
   ータに対し既処理／未処理を示すフラグをリンクさせて
   １つのデータとして記憶する連結関係記憶手段を備え、
   前記最小値のラベルは以後の走査により伝搬され、 前記一時的ラベル画像データを入力し、該入力一時的ラ
   ベル画像データのラベル値をアドレスとして、前記連結
   関係記憶手段から第１のデータを読出す第１の読出手段
   と、 前記第１の読出手段から読出された前記第１のデータを
   記憶するレジスタ手段と、 前記第１のデータをアドレスとし、前記連結関係記憶手
   段から第２のデータを読出す第２の読出手段と、 前記第１の読出手段により読出された第１のデータのラ
   ベル値と前記入力一時的ラベル画像データのラベル値と
   の一致／不一致を検出するための比較手段と、 前記一時的ラベルの最小値を初期値としてカウントアッ
   プ動作するカウンタ手段と、 前記カウンタ手段のカウント値と前記レジスタ手段の格
   納する第１のデータと前記第２のデータのいずれかを選
   択して出力する選択手段と、 前記比較手段の出力と前記第１のデータのフラグとをデ
   コードし、該デコード結果に従って前記カウンタ手段の
   カウントアップ動作および前記選択手段の選択動作を制
   御する信号を発生するデコード手段とを含み、前記デコ
   ード手段は（ｉ）前記フラグが既処理状態を示すとき前
   記選択手段に対し前記レジスタ手段に格納された第１の
   データを選択させるための制御信号を発生する手段と、
   （ｉｉ）前記フラグが未処理状態を示しかつ前記一致検
   出手段の出力が不一致を示すとき、前記選択手段に対し
   前記第２のデータを選択させるための制御信号を出力す
   る手段と、（ｉｉｉ）前記フラグが未処理状態を示しか
   つ前記一致検出手段の出力が一致を示すとき、前記選択
   手段に対し前記カウンタ手段の出力カウント値を選択さ
   せるための制御信号を出力するとともに前記選択手段の
   選択動作の後前記カウンタ手段のカウント値を更新する
   制御信号を出力する手段とを含み、 前記入力一時的ラベル画像データのラベル値をアドレス
   とし、前記選択手段が出力するデータを対応のフラグを
   既処理状態に設定して前記連結関係記憶手段に書込む手
   段と、 前記選択手段の出力データのラベル値を最終ラベル値と
   して出力する手段とを備える、ラベリング回路。
5. 【請求項５】 前記一時的ラベル画像データが与えられ
   るサイクルを指定するクロック信号を周波数逓倍する周
   波数逓倍手段と、 前記周波数逓倍手段が出力するクロック信号に応答し
   て、前記第１および第２の読出手段、前記比較手段、前
   記デコード手段、前記選択手段、前記書込手段、および
   前記出力手段の動作のタイミングを規定する制御手段と
   をさらに備える、請求項４記載のラベリング回路。