JPH0520792B2 - - Google Patents

Description

【発明の詳細な説明】 〔概要〕 画像情報を構成する各画素の連結領域のラベル
付け方式であつて、入力した画像情報に対して、
異なる接続関係が連続して発生しないように、暫
定ラベルを付加することにより、接続関係整理部
に入力される接続関係の頻度が低減され、更に以
前に検出された接続関係の履歴を保持し、これを
参照することにより、重複した接続関係の中で最
初に検出された接続関係のみを出力することによ
り、演算量が削減され、高速なラベル付けが可能
となる。

〔産業上の利用分野〕

本発明は、画像情報を構成する各画素の連結領
域のラベル付けを高速に実行するラベル付け方式
に関する。

例えば、医療用の画像を鮮明な画像として認識
するための画像処理装置が実用化されている。こ
の画像処理装置における処理の中に画像情報を二
値化した画像の画素値が“１”である画素集合を
連結領域毎に区分け・分割し、各連結領域内各画
素に対して異なる整数を割当てるラベル付け処理
過程がある。

このラベル付け処理は画像処理装置の中にあつ
ても、その処理に長時間を要するため、効率的に
しかも短時間にラベル付け処理を行う方式の実用
化が望まれていた。

〔従来の技術〕

第７図は従来例を説明するブロツク図、第８図
は領域のラベル付け処理を説明する図、第９図は
従来例の暫定ラベル付けの動作を説明する図、第
１０図は従来の暫定ラベル付け結果状況を説明す
る図、第１１図は従来の接続関係整理の動作を説
明する図、第１２図はクラスタリング部の動作を
説明する図をそれぞれ示す。

第８図は連結領域のラベル付け処理の例を示
す。第８図Ａは処理前の画像であり、白地（レベ
ル“０”）の部分が背景、斜線の部分（レベル
“１”）がラベル付けの対象となる領域であり、第
８図Ｂはラベル付け処理により各領域に固有のラ
ベル（本例の場合、１、２、３）が付加され、各
領域が区別される。

第７図は上記ラベル付け処理を行うブロツク図
の従来例を示す。本ブロツク図は、 画像を走査
して得られるビデオ信号に対して、 各画素に順次暫定ラベルを付けると共に、既に
付加されている近傍の暫定ラベルとの接続関係を
検出する暫定ラベル付け回路１と、 検出された接続関係の重複部分を整理する接続
関係整理回路２と、 暫定ラベルのクラス分け結果を用いて暫定ラベ
ルを更新するラベル更新部３と、 整理された接続関係に基いて暫定ラベルのクラ
ス分けを行うクラスタリング部４から構成されて
いる。

暫定ラベル付け回路１は第９図Ａに示すよう
に、入力される画像上に相対Ｌ型（Ｌ字の左右対
象を反対にしたものの）のウインドを設定し、
この相対Ｌ型のウインドで走査し、第９図Ｂに
示すラベルの発生及び延長、第９図Ｃに示す隣接
したラベルの接続関係の検出を行う。

相対Ｌ型のウインドで走査する方向は第９図
Ａで示す矢印方向であり、同時に走査する画素を
ａ，ｂ，ｃとする。尚、右方向の画素数はｉ画
素、下方向の画素数はｊ画素とする。

ラベルの発生及び延長の論理としては第９図Ｂ
に示すように、例えば同時に入力される画素ａ〜
ｃの内、画素ａ，ｂは不定レベル（＊印で示す）、
画素ｃが“０”レベベルの時はｃ＝０として注目
画素を送出するように動作する。

又、画素ａ，ｂが“０”レベル、画素ｃが
“０”以外のレベル（NZで示す）の時はｃ＝Ｌ
（但し、Ｌ＝Ｌ＋１でＬは暫定ラベル（初期値
１））とし、ラベルの発生のための演算を行う。

更に、画素ａが“０”レベル、画素ｂ，ｃが
“NZ”レベルの時は、ｃ＝ｂとしラベルの延長の
ための演算を行い、画素ａ，ｂ，ｃが“NZ”レ
ベルの時は、ｃ＝Min（ａ，ｂ）としラベルの延
長のための演算を行う。

第９図Ｃは、各画素ａ，ｂ，ｃ間の接続関係を
検出するための条件を示すもので、例えば画素
ａ，ｂが不定レベルで、画素ｃが“０”又は
“NZ”レベルの時は接続関係関数Fc＝０となり、
画素ｃに対するラベルの接続関係が無いものと判
定する。

又、各画素ａ，ｂ，ｃ共に“NZ”レベルの時
は接続関係関数Fc＝１、（ａ，ｂ）を暫定ラベル
付け回路１は出力し、画素ｃに対して画素ａ，ｂ
が接続されていることを検出する。

第１０図は上記方法による処理例に基づく暫定
ラベル付け結果（第１０図Ａに示す）と検出され
た接続関係（第１０図Ｂに示す）を示す。これよ
り明らかなように、上記方法で処理した場合、異
なる接続関係が連続して生起（例えば、暫定ラベ
ル１と６、１と５、１と４等、以後これを1/6，
１／５，1/4，……等と表示する）する可能性があ
る。

第１１図Ａは暫定ラベル付け処理後の画像を示
す。接続関係整理回路２は暫定ラベル付け回路１
で検出された接続関係の重複部分を整理するもの
である。この重複した接続関係を整理する方法と
しては、従来は例えば工業技術院で提案されてい
る三角メモリ法（特許公報58−16217）を用いて
処理されている。

この三角メモリ法は第１１図Ｂに示すように、
例えばメモリの横方向と縦方向に暫定ラベル番号
（本例では１〜８）を付加し、横方向と縦方向の
座標点（例えば、1/2）が接続関係有りの場合は
‘1'を立て、無しの場合は‘0'として重複した接
続関係を入力する。前記メモリに重複した接続関
係を入力した後、メモリ全体を読出すことによ
り、接続関係を整理した結果が出力されることに
なる。

第１２図はクラスタリング部４の動作を説明す
る図で、接続関係整理回路２で整理された、例え
ば第１２図Ａに示すような接続関係を入力し、そ
れぞれの連結領域に属する全ての暫定ラベルを検
出する。即ち、第１２図Ａに示す整理された接続
関係から第１２図Ｂに示す直接接続テーブルを作
成する。

例えば、暫定ラベル“１”と接続されている暫
定ラベルは第１２図Ｂのテーブルから“３”，
“２”，“５”となる。又、暫定ラベル“８”と直
接接続されている暫定ラベルは“６”，“７”とな
る。この直接接続テーブルは、各暫定ラベルと直
接に接続している暫定ラベルをまとめたものであ
る。

次に、直接接続テーブルの内容に基づき、暫定
ラベルを追跡し、ラベルのクラスタ化を行う。こ
の処理は第１２図Ｃに示すように暫定ラベルの接
続関係をグラフ表現しした場合にグラフの辺を追
跡することに相当し、第１２図Ｄに暫定ラベルの
追跡結果を示す。

ラベル更新部３では、クラスタリング部４の出
力に基づいて暫定ラベルを更新する。第１１図Ａ
の画像の例では、暫定ラベル１、２、３、５を
“１”に暫定ラベル４、６、７、８を“２”に変
換することにより、各領域に一対一に対応したラ
ベル付けが行われる。

〔発明が解決しようとする問題点〕

上述の方法で暫定ラベル付けを行う際に、注目
画素（本例では画素ｃの部分）の上隣の画素（本
例では画素ａ）と左隣の画素（本例では画素ｂ）
に共に暫定ラベルが付加されている場合、上隣の
画素の暫定ラベルを注目画素にする方法と、上隣
と左隣の２つの画素の最小値（第９図Ｂで示す
例）を出力する方法がある。

これらの方法では暫定ラベルの接続関係が画素
毎に、しかも異なる接続関係が連続して生起する
ため、その処理に長時間を要する。

又、暫定ラベル付け回路１で検出された重複し
た接続関係を整理する場合、重複した接続関係を
メモリ（図示してない）に入力した後に、メモリ
（図示してない）全体を読出す必要があるために、
最大暫定ラベルの２乗に比例する演算時間を必要
とする等の問題点がある。

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

第１図は本発明の原理ブロツク図を示す。

本原理ブロツク図は第７図で説明したラベル更
新部３、クラスタリング部４と、 画像の走査方向で右下でしかも注目画素の上隣
の画素と左隣の画素に共に暫定ラベルが付加され
ている場合、左隣の画素に付加された暫定ラベル
を優先して注目画素として出力するラベル付加回
路１１と、同一の接続関係が連続して検出された
場合に接続関係を１回のみ出力し、他を抑御する
抑制回路１２とを有する暫定ラベル付け部５と、 画像内で検出された接続関係の履歴を保持する
ラベル接続テーブルと、ラベル接続テーブルを参
照し、重複した接続関係のうち最初に検出された
もののみを出力する接続関係制限手段と、整理さ
れた接続関係を保持し、これに基づいてラベル接
続テーブルの初期化を行う初期化手段とを有する
接続関係整理部６とから構成されている。

〔作用〕

入力した画像情報の暫定ラベル付けにおいて、
異なる接続関係が連続して発生しないようラベル
付加手段にて暫定ラベルを付加すると共に、同一
の接続関係が連続して検出された場合には、その
接続関係は１回のみ出力し、更に接続関係整理部
においては、以前に検出された接続関係の履歴を
保持し、これを参照することにより、重複した接
続関係のうち最初に検出された接続関係のみを出
力するように制限することにより、接続関係整理
部に入力される接続関係の頻度が低減されると共
に、接続関係整理部の演算量が削減され、高速な
ラベル付けが可能となる。

〔実施例〕

以下本発明の要旨を第１図〜第６図に示す実施
例により具体的に説明する。

第２図は本発明の実施例である接続関係整理部
を説明するブロツク図、第３図は本発明の実施例
における暫定ラベル付けを説明する図、第４図は
本発明の実施例における暫定ラベル付けの動作を
説明する図、第５図は本発明の実施例における暫
定ラベル付け結果と接続関係を説明する図、第６
図は本発明の実施例における接続関係整理部の動
作を説明するブロツク図をそれぞれ示す。尚、全
図を通じて同一符号は同一対象物を示す。

次に、本実施例に基づくラベル付け動作を説明
する。尚、本実施例の動作説明においては、ラベ
ル更新部３及びクラスタリング部４の動作は第７
図の説明と同一のため省略である。

第１図のラベル付加回路１１、抑制回路１２を
備えた暫定ラベル付け部５は第３図に示すごとく
前述の相対Ｌ型ウインドで画像を矢印方向へ走
査する。この時、注目画素（画素ｃに相当する部
分）に出力する暫定ラベルの値としては、左隣の
画素ｂを出力することにより、異なる接続関係が
連続して発生しないようにする。

即ち、ラベルの発生と延長の論理としては、第
３図Ｂに示すように同時に走査し入力する画素
ａ，ｂ，ｃの内、画素ａ，ｂが不定（＊印で示
す）で画素ｃが“０”レベルの時はｃ＝０でラベ
ルの発生処理を延長処理もなく、画素ａ，ｂが
“０”、画素ｃが“０”以外のレベル（“NZ”で示
す）の時は、ラベルの発生処理がある。

又、画素ｂ，ｃが“NZ”、画素ａが“０”レベ
ルの時はｃ＝ｂ、画素ａ，ｃが“NZ”、画素ｂが
“０”レベルの時はｃ＝ａ、画素ａ，ｂ，ｃ共に
“NZ”の場合はｃ＝ｂとなり、いずれの場合もラ
ベルの延長処理が有りとなる。

尚、第３図Ｂに示すウインドの動作とラベル
の発生の有無及びラベルの延長の有無を関係動作
の詳細を第４図に示す。

次に、接続関係の検出と連続した同一接続関係
の出力抑制の関係を第３図Ｃに示す。即ち、画素
ａ，ｂが不定で画素ｃが“０”レベルの時、画素
ａが不定、画素ｂが“０”、画素ｃが“NZ”の
時、画素ａが“０”、画素ｂ，ｃが“NZ”の時は
いずれも直前の接続関係が不定でラベルの接続関
係無し（Fc＝０）として出力される。

次に、画素ａ，ｂ，ｃ共に“NZ”の時で直前
の接続関係がａ，ｂの場合はFc＝０で出力を抑
制し、直前の接続関係がａ，ｂ以外の場合はFc
＝１でａ，ｂを出力する。

上述のようにして処理した暫定ラベル付けの結
果と接続関係を第５図に示す。即ち、これによれ
ば同一の接続関係は連続して発生するが、異なる
接続関係が連続して発生することはない。

又、同一の接続関係は第３図Ｃの論理で抑制さ
れる（第５図Ｂの“×”印で示す部分）ので、接
続関係の発生を大幅に削減することが出来る。

次に、第２図は本実施例における接続関係整理
部６の詳細ブロツクを示す。即ち、本実施例の接
続関係整理部６は、ラベル接続テーブル２３、接
続関係制限回路２４及びマルチプレクサ（以下
MPXと称する）２１とメモリ２２からなる初期
化回路２５とから構成されている。

ラベル接続テーブル２３はラベルの接続関係を
保持するための２次元１ビツトメモリであり、接
続関係が入力されると対応するアドレスに「１」
が書込まれる。

接続関係制限回路２４はラベル接続テーブル２
３が“０”、即ち入力された接続関係が始めて出
現した時のみ、その接続関係を出力する。初期化
回路２５は出力された接続関係をメモリ２２で保
持し、この内容に従つてラベル接続テーブル２３
を初期化する。

即ち、ラベル接続テーブル２３は処理に先立つ
て図示されないMPUによつてその内容はクリア
されている。この場合は２次元1bitのラベル接続
テーブル２３の全アドレスに対して０を書き込む
処理が行なわれる。

一方、処理の実行中には画像データの無効期間
（帰線期間）内にクリアする必要があるが、全ア
ドレスに対して０を書き込む処理では、帰線期間
内に処理を終了することができない。

このため、接続関係を格納するメモリ２２を用
意して、ラベル付け処理実行中はメモリ２２は整
理された接続関係を蓄積し、帰線期間中にMPX
２１を切り換えてメモリ２２よりラベル接続テー
ブル２３へ前フレームにおいて１になつたアドレ
ス（接続関係）を入力し、そのアドレスの値を０
に戻すことでラベル接続テーブル２３をクリアし
ている。

このように構成されている接続関係整理部６は
暫定ラベル付け部５で検出された接続関係の重複
部分を整理する。

即ち、第６図Ａに示す画像を暫定ラベル付け後
の画像とすると、暫定ラベル付け部５で検出され
る接続関係は第６図Ｂに示すようになる。この図
において、“×”印が暫定ラベル付け部５で抑制
された接続関係であり、下線を付した部分が接続
関係の重複部分である。尚、第６図Ｃは重複部分
を整理した時の出力を示す。

〔発明の効果〕

以上のような本発明によれば、暫定ラベル付け
で検出される接続関係が大幅に削減出来、接続関
係検出の時間が短縮され、更に暫定ラベルの接続
関係の重複部分を削減出来るので連結領域のラベ
ル付け処理を高速に実行出来ると言う効果があ
る。

【図面の簡単な説明】

第１図は本発明の原理ブロツク図、第２図は本
発明の実施例である接続関係整理部を説明するブ
ロツク図、第３図は本発明の実施例における暫定
ラベル付けを説明する図、第４図は本発明の実施
例における暫定ラベル付けの動作を説明する図、
第５図は本発明の実施例における暫定ラベル付け
結果と接続関係を説明する図、第６図は本発明の
実施例における接続関係整理部の動作を説明する
ブロツク図、第７図は従来例を説明するブロツク
図、第８図は領域のラベル付け処理を説明する
図、第９図は従来例の暫定ラベル付け動作状況を
説明する図、第１０図は従来の暫定ラベル付け結
果状況を説明する図、第１１図は従来の接続関係
整理の動作を説明する図、第１２図はクラスタリ
ング部の動作を説明する図、をそれぞれ示す。 図において、１は暫定ラベル付け回路、２は接
続関係整理回路、３はラベル更新部、４はクラス
タリング部、５は暫定ラベル付け部、６は接続関
係整理部、１１はラベル付加回路、１２は抑制回
路、２１はMPX、２２はメモリ、２３はラベル
接続テーブル、２４は接続関係制限回路、２５は
初期化回路、をそれぞれ示す。

Claims (1)

1. 【特許請求の範囲】 １ 画像を走査して得られるビデオ信号に対し
   て、前記画像を構成する各画素を所定走査方法で
   走査し、順次暫定ラベルを付けると共に、既に付
   加されている近傍の暫定ラベルとの接続関係を検
   出する暫定ラベル付け部５と、 前記暫定ラベル付け部５で検出された接続関係
   の重複部分を整理する接続関係整理部６と、 接続された接続関係に基づいて行われた暫定ラ
   ベルのクラス分け結果を用いて暫定ラベルを更新
   するラベル更新部３等を備えてなる連結領域のラ
   ベル付け回路において、 前記暫定ラベル付け部５内に、該画像の走査方
   向が右下で、注目画素の上隣の画素と左隣の画素
   と共に暫定ラベルが付加されている場合に、該左
   隣の画素に付加された暫定ラベルを優先して注目
   画素に出力するラベル付加手段１１と、 同一の接続関係が連続して検出された場合に、
   接続関係を１回のみ出力し、他を抑制する抑制手
   段１２と、 前記接続関係整理部６内に、該画像内で検出さ
   れた接続関係の履歴を保持する保持手段と、 前記保持手段を参照し、重複した接続関係の
   内、最初に検出されたもののみを出力する接続関
   係制限手段とを設け、 前記ラベル付加手段１１にて、入力した該画像
   の暫定ラベル付けで、所定手順に基づきラベルを
   付加して得る連続して発生する同一の接続関係
   は、前記接続関係整理部６に対して１回のみ送出
   するように前記抑制手段１２で抑制し、 更に、前記保持手段に、以前に検査された接続
   関係の履歴を保持させ、この内容を参照して、重
   複した接続関係の内、最初に検出された接続関係
   のみを出力するように制御することを特徴とする
   ラベル付け回路。