JPH07104941B2

JPH07104941B2 - ラベリング方法

Info

Publication number: JPH07104941B2
Application number: JP63026390A
Authority: JP
Inventors: 伸治林
Original assignee: Fuji Electric Co Ltd
Current assignee: Fuji Electric Co Ltd
Priority date: 1988-02-06
Filing date: 1988-02-06
Publication date: 1995-11-13
Anticipated expiration: 2010-11-13
Also published as: JPH01201783A

Description

【発明の詳細な説明】（産業上の利用分野）本発明はラベリング方法にかかり、詳しくは、２値画像
を用いた解析や計測等の前処理作業として、「１−画
素」（画素ありを示す論理“1"の画素）が複数連結され
てなる多数の連結成分に対して、それぞれ固有の連続し
たラベル値を高速で付与できるようにしたラベリング方
法に関する。

（従来の技術）従来、この種のラベリング方法としては、第４図に示す
ものが知られている。

すなわち、同図において、100は「１−画素」及び「０
−画素」（背景を示す論理“0"の画素）からなる２値画
像であり、ラベリングに際しては、まず、２値画像100
を画面の左上から矢印201で示されるようにラスタ走査
していき、ラベルが付けられていない「１−画素」を検
出するとこの画素に未使用のラベル値、例えば「１」を
付ける。そして、この画素を中心として、上下左右の４
方向に連続している４連結または上下左右及び斜めの８
方向に連続している８連結の「１−画素」を、矢印202
で示される近傍走査により探索して同一のラベル値を付
ける。

更に、これらの連結画素を中心とした４連結または８連
結の「１−画素」にも同一のラベル値を付ける処理を繰
返し、連結されている「１−画素」がなくなったときに
１つの連結成分301に対するラベリングを終了する。

こうして連結成分301に対するラベリングが終了する
と、再び２値画像100のラスタ走査を続行し、まだラベ
ルの付いていない「１−画素」を検出したならば新たな
ラベル値「２」を付けて連結成分302につき前記同様の
処理を行う。以上の処理を残りの連結成分303について
も繰り返すことにより、２値画像100全体のラスタ走査
を終了した時点で一連のラベリング処理を完了するもの
である。

しかるにこの方式では、「１−画素」を検出してから４
連結または８連結している別の「１−画素」を検出する
ために、１つの画素について４回または８回の画素値の
読み込みが必要になり、メモリへのアクセス数が多いこ
とから処理に多くの時間を必要としていた。

一方、２値画像の走査回数を減らすために、第５図に示
すようなラベリング方法が提案されている。この方式で
は、まず、２値画像100Aをラスタ走査してラベルの付い
ていない「１−画素」を検出すると、隣接点を調べる。
そして、すべての隣接点にまだラベルが付いていない場
合には新たなラベル値を付け、「０−画素」以外で同一
のラベル値が付いていればそれと同一のラベル値を付
け、２種類以上の異なったラベル値が付いていればその
中で一番若いラベル値を付けると共に、これらは同一の
連結成分のものであることを記憶しておく。

同様の処理を続けて２値画像100A全体の走査が終了した
ならば、再度ラスタ走査を行い、同一の連結成分である
ことを示すラベル値をその連結成分の中で最も若いラベ
ル値に変更することにより、ラベリング処理を完了する
ものである。

なお、第５図において、301A,302A,303Aはそれぞれ同一
の連結成分を示しており、このうち連結成分301Aについ
ては、再度のラスタ走査の結果、一部のラベル値「２」
がこの連結成分301A内で最も若いラベル値「１」に変更
されている。

（発明が解決しようとする課題）しかしながらこの方法にあっては、第５図の変更後にお
ける連結成分301A,302A,303Aから明らかなように、ラベ
ル値が飛び飛びになる場合があり、後の画像解析等の処
理に際してどのようなラベルが幾つあるかを認識しなく
てはならない制約を生じる。

また、走査の過程において、同一の連結成分に含まれる
にも拘らず複数のラベルを使用するため、ラベル値の絶
対数が少なくなり、ラベル付けする連結成分の個数、換
言すればラベリングの対象となる２値画像が制約されて
しまうという問題があり、かかる課題の解決が要請され
ていた。

本発明は上記課題を解決するために提案されたもので、
その目的とするところは、少ない走査回数で多数の連結
成分に対し固有のラベル値を連続して付与できるように
し、上述したような種々の制約もなく、一連の画像処理
作業の効率を大幅に高めることができるラベリング方法
を提供することにある。

（課題を解決するための手段）上記目的を達成するため、本発明は、画像用メモリ内の
画素の有無に応じた「１−画素」及び「０−画素」から
なる２値画像データを前記画像用メモリの最上位ビット
に配し、画面のラスタ走査により前記最上位ビットに基
づいて「１−画素」と検出された点を始点として記憶す
ると共に、この始点を含みかつこの始点に連続する「１
−画素」からなる現走査行の連結成分を検出し、前記画
像用メモリの残りの下位ビットを使用して前記連結成分
に同一のラベル値を付与して各点の最上位ビットをゼロ
クリアし、次いで、現走査行の上段の行及び下段の行の
それぞれにつきラスタ走査を行ない、前記連結成分と同
一の水平方向のポインタにより示される範囲内で「１−
画素」と検出された点を始点として記憶し、この始点を
含みかつこの始点に連続する「１−画素」からなる各行
の連結成分を検出して前記ラベル値と同一のラベル値を
付与すると共に各点の最上位ビットをゼロクリアし、上
記の処理を始点がなくなるまで実行して一群の連結成分
のラベル付けを行ない、この一群の連結成分のラベル付
けが終了するたびにラベル値を順次連続する値に更新し
ていくものである。

（作用）まず、画像用メモリの最上位ビットに基づいてラスタ走
査により「１−画素」と検出された点を連結成分の始点
として記憶しておく。次に、この始点を含みかつこの始
点に連続する「１−画素」からなる現走査行の連結成分
を検出し、画像用メモリの残りの下位ビットを使用して
これらの連結成分に同一のラベル値を付与して各点の最
上位ビットをゼロクリアする。このゼロクリアにより、
一度「１−画素」として検出された点が再度検出されな
いようにする。次いで、現走査行の上段の行及び下段の
行のそれぞれにつきラスタ走査を行ない、前記連結成分
と同一の水平方向のポインタにより示される範囲内で
「１−画素」と検出された点を始点として記憶する。そ
して、この始点を含みかつこの始点に連続する「１−画
素」からなる各行の連結成分を検出して前記ラベル値と
同一のラベル値を付与すると共に各点の最上位ビットを
ゼロクリアする。

以上の処理を始点がなくなるまで実行して一群の連結成
分のラベル付けを行ない、この一群の連結成分のラベル
付けが終了するたびにラベル値を順次連続する値に更新
していく。

すなわち本発明では、画面の１回のラスタ走査の過程で
始点が検出されると、その始点を含む連結成分を検出し
て当該連結成分に同一のラベル値を付与し、その後、ラ
ベル値を連続する値に更新したうえ画面のラスタ走査を
続行していくことにより他の連結成分を検出し、前記同
様の要領でラベル付けを行なっていく。

これにより、各連結成分には連続かつ固有のラベル値が
それぞれ付与されることになる。

（実施例）以下、図に沿って本発明の一実施例を説明する。

まず、第１図に示すように、ラベリングの対象となる２
値画像10が複数の連結成分31A,31B,31Cを有しているも
のとして、この２値画像10に対するラベリング処理を第
２図及び第３図を参照しつつ以下に詳述する。

始めに、例えば16ビットの画像用メモリに格納された
「１−画素」及び「０−画素」からなる２値画像10のデ
ータを、同一のメモリの最上位ビットに転送する（第３
図ステップS1）。次に、第１図の矢印21で示す如く、画
面の左上からラスタ走査を開始して画素値を順次読み込
んでいき、「１−画素」の点、すなわち最上位ビットが
“0"でない点を見つける（同S2,S3）。この間、最上位
ビットが“0"である「０−画素」の点が検出される限り
は、後述するように水平方向ないし垂直方向のポインタ
を更新し（同S12）、かつ画面全体を終了したか否かの
判断を行う（同S13）。

第２図において、先のステップS3により現走査行L₁にお
いて「１−画素」の点P_1Sが検出されたならば、この点
を始点として記憶しておき（同S4）、この始点を取り出
すと共に（同S5）、そこから第１図の矢印22で示す如
く、右方向に「０−画素」の点が現れるまで走査を行
い、現走査行L₁で最後に見つけた「１−画素」の点P_1E
を終点とする（同S7）。このとき、前記始点P_1Sは初め
て見つかった始点であるため、ステップS6に示される判
断は省略されるか、あるいは、現走査行L₁の上下の行に
他の始点がある可能性があるため、判断結果は否とな
る。

次に、始点P_1Sから終点P_1Eまでに同一のラベル値、例え
ば「１」を付ける（同S8）。このとき、ラベル値は15ビ
ットにて表現されるが、書き込みは16ビットで行い、最
上位ビットをゼロクリアする。すなわち、一度ラベル付
けをした点の最上位ビットは常に“0"となるようにし、
この点が再び「１−画素」として検出されないようにし
ている。

次いで、今回走査した現走査行L₁の上段の行L₂につい
て、同一の水平方向のポインタにて示される始点P_2S′
から終点P_2E′まで（８連結画素を探索する場合には始
点P_2S′の１つ左から終点P_2E′の１つ右まで）の画素値
を読み込み、最初に「０−画素」から変化した「１−画
素」の点P_21Sを次の始点として記憶する（同S9）。

ここで、前回ラベル付けした行L₁につき、その始点をｆ
（i_S,j）、終点をｆ（i_E,j）（i:水平方向のポインタ,
j:垂直方向のポインタであり、i_S≦i_E）とすると、上段
の行L₂における探索の始点はｆ（i_S,j−１）、終点はｆ
（i_E,j−１）、（８連結画素を探索する場合には、始点
はｆ（i_S−1,j−１）、終点はｆ（i_E＋1,j−１））とな
る。そして、上段の行L₂における次の始点ｆ（i,j−
１）としては、ｆ（ｉ−1,j−１）が“0"であり、かつ
ｆ（i,j−１）が“1"である点（なお、i_S≦ｉ≦i_E）と
なる。すなわち、行L₂において、始点P_2S′から終点
P_2E′までの間の「１−画素」の点のうち、隣合う左の
点が「０−画素」である点P_21Sが次の始点となる。

また、第２図のように上段の行L₂における探索の始点P
_2S′が「１−画素」の点である場合には、この点P_2S′
の左側に「１−画素」の点が連続している可能性がある
ため、点P_2S′から左方向に走査を行うことにより「１
−画素」の点を順次始点候補点P_22S″とし、最後に見つ
けた「１−画素」の点（「０−画素」に隣接している
点）P_22Sを更にその次の始点として記憶する（同S9）。

同様の方法により、下段の行L₃についても始点P_31S,P
_32Sを見つけ、これらを記憶しておく（同S10）。

次に、上述のようにして記憶した始点を一つづつ取り出
し（同S5）、始点がなくなったかの判断（同S6）を行っ
た後、行L₁について行ったのと同様に、右方向に「０−
画素」の点が現れるまで走査を行って終点を見つけると
共に、これらの始点−終点間の複数の「１−画素」の点
に行L₁と同一のラベルを付ける（同S7,S8）。

そして、例えば行L₂についてのラベル付けが終わったな
らば、この行L₂の上下の行に対して新たに始点の探索を
行う（同S9,S10）わけであるが、行L₂の下段の行、すわ
なち行L₁については先にラベル付けが行われていて最上
位ビットが“0"であるから、始点の探索は実質的に行L₂
の上段の行についてのみ実行される。同様にして、行L₃
における始点の探索は行L₃の下段の行に対してのみ実行
される。

こうして、残っている始点がなくなったら、１つの連結
成分、例えば、第１図における連結成分31Aに対するラ
ベル付けが終了したことになる（同S6）。

その後、ラベル値を、「１」に連続する値である「２」
に更新し、かつ水平方向及び垂直方向のポインタを更新
して（同S11,S12）ラスタ走査を続行し、別の連結成分
を構成する「１−画素」の点を見つけたならば再び前述
の方法でその連結成分に対してラベル付けを行う（同S2
〜S12）。以上の処理を繰返しながら、画面ラスタ走査
が画面の右下に達した時点で、連結成分31A,31B,31Cを
有する一画面のラベル処理が完了するものである（同S1
3）。

この実施例によれば、16ビットの画像用メモリのうち15
ビットを使用して各連結成分にラベ付けを行うため、ラ
ベル値「０」を除外すれば、2¹⁵−１＝32767個のラベル
値を同数の連結成分に付与することができる。勿論、画
像用メモリのビット数をより多くすれば、更に多数の連
結成分に対して、それぞれ固有の連続したラベル値を付
与することが可能となる。

（発明の効果）以上のように本発明によれば、画像用メモリの最上位ビ
ットに２値画像データを配し、前記メモリの残りのビッ
トをラベル値に使用すると共に、画面のラスタ走査及び
連結成分内の走査を組み合わせて各連結成分に連続した
異なるラベル値を付与していくものであるため、２値画
像を構成する多数の連結成分に対して、ラベル値が飛び
飛びになったり不連続になることなくラベリングを行な
える利点がある。

更に、各連結成分において、ラベル付けを終えた各点の
最上位ビットをゼロクリアすることにより、ラベル付け
を終えた行の上下にある行について始点を探索する際
に、ラベル付けが済んでいる行を重複して探索する無駄
を省くことができ、ラベリング処理の高速化を図ること
ができる。

加えて、本発明では画面の１回のラスタ走査の過程にお
ける連結成分の走査の際にラベル値が付けられ、同一連
結成分内のラベル値が異なることはない。従って、第５
図に示した従来技術のように、１回のラスタ走査時に付
与された同一連結成分内の異なるラベル値を同一値に統
一するために、再度ラスタ走査を行なう必要がない。こ
のため、２値画像による計測や解析等に先立ち、ラベリ
ングによる連結成分の分類等の前処理作業を容易かつ高
速に行うことができ、２値画像を用いた一連の計測、解
析作業の負担を軽減して作業能率の大幅な向上を図るこ
とができる等の効果を有する。

【図面の簡単な説明】

第１図ないし第３図は本発明の一実施例を示すもので、
第１図はラベリングの対象となる２値画像の説明図、第
２図は現走査行及び上下の走査行における始点、終点等
の説明図、第３図はこの実施例の作用を説明するための
フローチヤート、第４図及び第５図は従来例を説明する
ための２値画像の説明図である。 10……２値画像、31A,31B,31C……連結成分 L₁,L₂,L₃……走査行 P_1S,P_21S,P_22S,P_31S,P_32S……始点 P_1E……終点

Claims

【特許請求の範囲】

【請求項１】画像用メモリ内の画素の有無に応じた「１
−画素」及び「０−画素」からなる２値画像データを前
記画像用メモリの最上位ビットに配し、画面のラスタ走
査により前記最上位ビットに基づいて「１−画素」と検
出された点を始点として記憶すると共に、この始点を含
みかつこの始点に連続する「１−画素」からなる現走査
行の連結成分を検出し、前記画像用メモリの残りの下位
ビットを使用して前記連結成分に同一のラベル値を付与
して各点の最上位ビットをゼロクリアし、次いで、現走
査行の上段の行及び下段の行のそれぞれにつきラスタ走
査を行ない、前記連結成分と同一の水平方向のポインタ
により示される範囲内で「１−画素」と検出された点を
始点として記憶し、この始点を含みかつこの始点に連続
する「１−画素」からなる各行の連結成分を検出して前
記ラベル値と同一のラベル値を付与すると共に各点の最
上位ビットをゼロクリアし、上記の処理を始点がなくな
るまで実行して一群の連結成分のラベル付けを行ない、
この一群の連結成分のラベル付けが終了するたびにラベ
ル値を順次連続する値に更新していくことを特徴とする
ラベリング方法。