JPH01113880A - 画像の連結成分抽出装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は画像中の連結成分を抽出する装置に係り、特に
、文書画像のように多数の連結成分が密集した２値画像
において連結成分を高速にラベル付けするのに好適な連
結成分抽出装置に関する。

画像中で同じ値をもつ画素が互いに連結して一つの塊を
形成しているものは連結成分と呼ばれている。通常の２
値画像ではこのような連結成分が。

いくつか画像中に点在している。画像データ中で、同じ
連結成分に属する画素に同じラベル（名前または番号）
を割り当て、異なった連結成分に属する画素には異なっ
たラベルを割り当てるというラベリングは１個々の連結
成分の特徴を計測するために最初に行う重要な処理であ
る。このため、ラベリングは１文書画像中の文字抽出９
図面中の記号の認識、医用画像処理、工業用視覚等に広
く適用されている。

〔従来の技術〕

連結成分にラベリングを行う方法は、大別して次の３つ
がある。（１）注目点を探索し、そのまわりの隣接点に
ラベルを伝播していく方法。この方法については、例え
ば、テレビジョン学会誌第４０巻、１０号（１９８６年
）、第１０３１頁から第１０３９頁（花木真−１岩下正
雄、寺嶋廣克゛′画像処理の基本手法（ＩＩ）”）に論
じられている。（２）ラスタ走査に沿って隣接点にラベ
ルを付け、２種類以上のラベルが付けられる場合はこれ
らのラベルの同一性を記録し、再度のラスタ走査におい
てラベルの書き換えを行う方法。この方法は、技術評論
社″画像処理の基本技法″の第４４頁から第４９頁（１
９８６年）（長谷用純−９奥水大和、中山晶、横井茂樹
著）に論じられている。（３）成分の境界を求め、外側
の境界から内側に向かってラベルを付けていく方法。こ
の方法は、アカデミツクブレス社が出版したエイ・ロー
ゼンフェルド著のピクチャ　プロセシイング　バイ　コ
ンピュータ（１９６９年）の第１３６頁から第１３８頁
（Ａ　、　Ｒｏｓｅｎｆｅｌｄ　：　　”　Ｐ　ｉｃｔ
ｕｒｅＰｒｏｃｅｓｓｉｎｇ　ｂｙ　Ｃｏｍｐｕｔｅｒ
”Ａ　ｃａｄｅｍｉｃ　Ｐ　ｒｅｓｓ　。

ｐｐ、１３６−１３８　（１９６９）　）に論ぜられて
いる。

また、これらのラベリング方法を適用する画像のデータ
形成としては、通常の（ａ）画素データを用いるものと
、ランのように（ｂ）圧縮した画像を用いるものとがあ
る。特に、（ｂ）の方法はランを単位としてラベル付け
を行うため、（ａ）の画素を単位としたラベリング方法
と比較してより高速化が可能であり、また、ランを基に
したＭＨ符号などの圧縮符号化画像データとの変換が容
易である。このため、従来より、（ｂ）と（２）の方法
を組合せて、ラスタ走査に沿ってランにラベルを付け、
ラベルの同一性を控えておく方法が知られている。この
（ｂ）と（２）の方法を組合せた方法は、同じく、アカ
デミツクブレス社が出版したエイ・ローゼンフェルド著
のピクチャ　プロセシイング　バイ　コンピュータ（１
９６９年）の第１３６頁から第１３８頁（Ａ　、Ｒｏｓ
ｅｎｆｅｌｄ　：“Ｐｉｃｔｕｒｅ　Ｐｒｏｃｅｓｓｉ
ｎｇ　ｂｙ　Ｃｏｍｐｕｔｅｒ”Ａｃａｄｅｍｉｃ　Ｐ
ｒｅｓｓ、　ＰＰ、　１３６−１３８（１９６９））に
論ぜられている。

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

上記従来技術では、ラベリングを実行するに要する時間
が対象の画像が大画面になるにつれ、大幅に増大すると
いう点について配慮がされておらず、ラベリングの処理
に要する時間が非常に長くかかるという問題があった。

また、（ｂ）と（２）の方法を組合せたラスタ走査に沿
ってランにラベルを付け、ラベルの同一性を控えておく
方法においても、ラベルの同一性を記録し、分類してお
く必要があり、また、再度ラスタ走査を行いラベルの付
け換えを行う必要があるため、処理が煩雑となるという
間層があった。

本発明の目的は、このラベリングに要する処理時間を短
縮し、高速化することにある。

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

上記目的は、（ｂ）と（１）の組合せに属する方法にお
いて、ラベルを近傍のランに伝播させながらラベリング
を行う際に、連結性検定の対象であるランをブロックを
基にして限定することにより達成される０本発明は、ラ
ンに付けたラベルを伝播させることにより高速にラベリ
ングを行うものであり、ラベルの同一性を記録すること
及び再度ラスタ走査を行うことは不要である。

〔作用〕

本発明は、ランを単位としてラベルをつけるものであり
、隣接するランにラベルを伝播させていく方法において
、予めランを短冊状のブロックに分類しておく。それに
よって、連結性の判定を行ウランをこのブロックを基に
限定することができるようになるので、連結性の判定回
数を削減し高速化を図ることができる。

〔実施例〕

以下、本発明の一実施例を第１図により説明する。この
図は、装置構成を示す図である。画像入力装置１００は
、イメージスキャナ或はテレビジョンカメラなど光電変
換装置から構成されており。

ディジタル画像を入力する。ラン符号部１０１は、ディ
ジタル画像をラン符号に変換する。一方、ラン復号化部
１０３では、ラン符号を画素で構成されているディジタ
ル画像に変換する。画像出力装！！１０４は、デイスプ
レィ装置或はイメージプリンタから構成されており、ラ
ベルを付けられた画素の塊である連結成分を表示又は印
刷する。計算機１０２は、各部に符号化データを伝送す
るとともに、処理に必要なパラメータを設定し、各部の
動作を制御する。ラン符号化データメモリ部１０５には
、ランの始点座標、終点座標などのデータが格納されて
いる。また、ラベルメモリ部１０６には、それぞれのラ
ンに対して付加されたラベルの値がラベリング処理によ
って格納される。

ブロック分類テーブルメモリ部１０７には、画像を短冊
状のブロックに分割し、各ブロックに始点座標が属する
ランの内、一番左側にあるランをそのブロックに登録し
ている。このテーブルメモリには、ラベリング処理の前
に、予め、上述のランを登録しておく。ラベル付け処理
部１０８は、ラン符号化データメモリ１０５及びブロッ
ク分類テーブルメモリ部１０７のデータを用いてラベル
付けを行い、その結果をラベルメモリ部１０６に格納す
る。

従来から知られているラスク走査型うンラベリング法５
画素データに対するラスク走査型画素うベリング法をラ
ンデータに適用できるように改良したものである。手順
は、先ず、■ランデータに対してラスク走査を行ないな
がらランを順次、敢行では、一つのランを注目ランとし
て、前行のランと位置を比べる。もし■−（ａ）注目ラ
ンが前行のどのランとも隣接していなければ、新しいラ
ベルをこの注目ランに付けて、前述のラスク走査に戻る
。また、もし、■−（ｂ）注目ランが前行のちょうど１
つのランに隣接しているなら、そのランのラベルと同じ
ラベルをこの注目ランに付けて、前述のラスク走査に戻
る。さらに、もし■−（Ｃ）注目ランが前行の２つ以上
のランに隣接しているなら、その中で最も前に付けられ
た古いラベルを注目ランにつけるが、この時、これらの
ラベルはすべて同一成分に属する旨を控えに記録してお
く、前述のラスク走査に戻る。最後に。

■ラスク走査を終了した後１本来なら１つの連結成分と
して同一のラベルを付けるべきランのラベルの付けなお
しを行うため、前述■−（ｃ）のラベルの同一性の記録
を分類して等してラベルの集まりを決定し、これに基づ
いて、再度、ラスク走査を行いながら、ラベルの書き換
えを行い、すべてのラベルが書き換えられたならば終了
する。この手続きでは、■、■の過程は図形のランの次
数だけの反復の処理となり、処理時間が短縮される。

しかしながら、この方法では、ラスク走査型画素うベリ
ング法と同様、■の過程において、ラベルの同一性を記
録し、分類しておく必要があり、また、再度ラスク走査
を行い、ラベルの付け換えを行う必要があるため、処理
が煩雑となる。

それに対して２本発明の一実施例は、ランを単位として
ラベルを伝播させていくものである。その処理過程は、
大きく、ランデータで表現した圧縮２値画像に対するラ
ンの探索過程を伝播過程からなる。先ず、探索過程では
、■ラベルが割り当てられていないランをラスク走査に
沿って探索する。そして、■該当するランが見つかった
ら、そのランにまだ使われていないラベルの値を割り当
てる。次に、伝播過程に移り、■このランに連結してい
るすべてのランを探して、各ランに同じラベルを割り当
てる。この時、上下の走査線上の連結しているランに次
々に虫が喰うように、ラベルを伝播させていく。もはや
伝播するランがなくなった時、該当するランに連結した
ランはすべて求まったことになる。連結したランすべて
にラベルを割り当てたら、探索過程に戻り、さらにラン
データのラスク走査を続けて、再びラベルが割り当　　
゛てられていないランを探し、再び伝播過程に移る。

このように、探索■、■と伝播■を繰返し、ランデータ
全体を探索し終わるまで続ける手法である。

この方法を伝播型ランラベリング法と呼ぶ。この方法で
は、前述の従来から知られているラスク走査型うンラベ
リング法のようなラベルの同一性を記録すること及び再
度ラスク走査を行うことは不要である。この伝播型ラン
ラベリング法の全体手順を第２図に示す。第２図に示し
た伝播型ランラベリング法の手順は、先ず、ステップ２
００でラベルの値を初期化する。ラベルの値として整数
を用いると、ラベリング処理が完了した時点でのラベル
の値が画像中の連結成分の個数に相当することになる。

ステップ２０１では、画像に対するラスク走査が終了す
るまで、ステップ２０２以下の処理を繰り返す。ステッ
プ２０２では、注目するランにラベルが付いているかど
うかの判定を行い、もしラベルが付いていればステップ
２０１に戻すラスタ走査を続けるが、もしラベルが付い
ていなければ、ステップ２０３に移り、注目ランにラベ
ルを付けるとともに、ステップ２０４で注目ランに連続
するすべてのランにラベルを付ける。そして、ステップ
２０５でラベルの値を更新し、ステップ２０１に戻る。

これらの手順の内、ステップ２０４の注目ランに連結す
るすべてのランにラベルを付ける手順の詳細手順を第３
図（ｂ）に示す。

ステップ３００では、先ず、ラベルの伝播の用いる伝播
光テーブルを空にし、また、ステップ３０１では伝播光
テーブルを空にする。そして、ステップ３０２で、注目
ランを伝播光テーブルに登録し、ステップ３０３でこの
伝播光テーブルが空になるまで、ステップ３０４以下の
処理を繰り返す、ステップ３０４では、同じく、伝播光
テーブルが空になるまで、ステップ３０７以下の処理を
繰り返す。ステップ３０７では、伝播光テーブルから一
つランを取り出す。このランを伝播光ランと呼ぶ。ステ
ップ３０８では、この取り出した伝播光ランを伝播光テ
ーブルから削除する。ステップ３０９では、伝播光ラン
の走査線の下行及び上行に隣接する走査線を求め、ステ
ップ３１０でこれら隣接走査線が尽きるまで、ステップ
３１１゜３１２の処理を行う。ステップ３１１では、隣
接走査線にあるランが尽きるまで、ステップ３１２の処
理を行う。ステップ３１２では、伝播光ランに連結する
ランの抽出、ラベル付け、伝播光テーブルへの格納を行
う。これらのステップの内、ステップ３１２の詳細手順
を、同図（ｅ）に示す。

ステップ３２０では、隣接線上のランはラベル付けされ
ているかどうかの判定を行い、もしラベルが付けられて
いなければ、ステップ３２１で該当ランの始点座標が伝
播光ランと比較して連結性を満たしているかどうかを判
定し、もし連結性を満たしていれば、ステップ３２２で
終点座標が連結性を満たしているかどうかの判定を行い
、もし連結性を満たしていればステップ３２３・に移る
。ステップ３２３で隣接走査線上の当該ランにラベルを
付けるとともに、ステップ３２４で伝播光テーブルに当
該ランを格納する。

第４図は、本実施例によるラベルの伝播過程を説明する
図である。図中（ａ）は図形が分岐している場合の伝播
の例を示すもので、先ずラン４００にラベルが付けられ
、次いで、ラン４００に連結するラン４０１に同一のラ
ベルが付けられる。このラン４０１にはラン４０２，４
０３゜４０４の三つのランが連結しており、それぞれに
も同一のラベルが付けられる。そして、次いで、例えば
ラン４０４に連結しているラン４０５にラベルが付けら
れることになる。同じく、図中（ｂ）は図形が空孔をも
ち分岐した部分が融合した場合の伝播の例を示している
。先ず、ラン４１０にラベルが付けられ、それに連結し
ているラン４１１に同一ラベルが付けられる。そして、
ラン４１１に連結しているラン４１２，４１６にも同一
のラベルが付けられる。そして、それぞれ連結してい４
１４に連結しているため、このラン４１５にも同一のラ
ベルが付けられる。一方、ラン４１８にもラン４１５に
連結しているが、すでに、ラン４１５にはラベルが付け
られているため、ラン４１８からの伝播によってはラベ
ルが付けられない。次いで、ラン４１５に連結している
ラン４１９．４２１にラベルが付けられ、それらの連結
しているラン４２０，４２２にもラベルが付けられる。

同じく１図中（ｃ）は、上下行の走査線への伝播の例で
あり、先ず、ラン４３０にラベルがつけられると、順次
、ラン４３１，４３２゜４３３．４３４にも同一のラベ
ルが付けられる。

ラン４３４には、下行のラン４３５と上行のラン４３６
が連結しており、それぞれラン４３５゜４３６に同一の
ラベルが付けられる。そして、下方向へは、ラン４３７
，４３８と順欠ラベルが付けられ、また、上方向へは、
ラン４３９，４４０゜４４１と順次ラベルが付けられる
。

一つのランは、第５図に示すように、始点座標５０２と
終点座標５０８、および次のランの始点座標と終点座標
が格納されている番地（次ラン番地）５０９で表わす。

ある一つのランについて始点座標、終点座標１次ラン番
地が、それぞれ始点座標テーブル５０１．終点座標テー
ブル５０２゜次ラン番地テーブル５０３のある番地５０
６に格納される。一つのランに関する上述のデータは、
ランに対応して設定されているある同一の番地において
、これらのテーブルをアクセスすることにより得られる
。さらに、ランがどの走査線に属しているかを示すため
に、各走査線の第一番目のランのデータ（始点座標、終
点座標、及び次ラン番地）が格納されている番地を格納
するために、ライン先頭番地テーブル５００を設けてい
る。このライン先頭番地テーブルは、走査線の位置を表
わすライン番地５０４をアドレスとして、その内容おけ
る次ラン番地は零値に設定している。また。

ライン先頭番地テーブルに関しても、ある走査線上にラ
ンが存在しなＮ１場合に、このラインに対応したライン
先頭番地テーブルの内容を零値としている。

ラン符号のデータ長に関しては、ライン先頭番地テーブ
ル５００と次ラン番地テーブル５０３は４バイト長であ
る。これは、ランの個数によって決定されるものである
が、例えばＣＣＩＴＴの標準原稿ではランの個数は数万
個であり、４バイト長で充分である。また、始点座標テ
ーブル５０１と終点座標テーブル５０２は２バイト長と
する。

これによって、走査線密度１６本／ｒｎｙａとして。

ＡＯ判で１３４５６ｘ１９０２４画素、８０判で１６４
８０Ｘ２３２９６画素となるが、これらを２バイトで充
分表現することができる。

本発明の別の実施例としては、上述の伝播型？ンラベリ
ングをさらに高速に行う実施例を説明する。これは、予
め１画像を短冊状のブロックに分割し、このブロックに
属するランを登録しておく。

がらラベリングを行う際に、連結性検定の対象であるラ
ンをブロックを基にして限定することによ。

り処理時間を短縮、高速化する方法である。なお。

この高速化手法をラスク走査型うンラベリング法に適用
し、高速化を図ることも可能である。

ここでは、前述した伝播型ランラベリング法を高速化す
るための二つの手法を述べる。その方法を、開始ラン指
定法、終了ラン判定法９次ラン変更法とそれぞれ呼ぶ。

先ず、開始ラン指定法では、走査線に沿って順番に並ん
でいるランに対して。

隣接関係の検定を開始するランを予め設定する。

このため、第６図に示すように、画像６００において、
走査線を一定の横幅をもつ短冊状のブロック６１０，６
１１，６１２，６１３に分割する。

そして、各ブロックにおいて、始点がブロックに含まれ
るランのなかで、一番左端にあるランの番地を予め登録
する。例えば、６０１で示した走査線番号１の上にあり
、６０２で示したブロック番□号１にあるブロックには
ラン６０４が登録される。

また、同じ走査線番号で６１１で示したブロック番号２
のブロックにはラン６０５が登録される。

なお、ブロックにランが含まれない場合は、そのブロッ
クの左にあるブロックに登録されているランを登録する
。従って、例えば、６０１で示した走査線番号ｌの走査
線上のブロック番号６１２のブロックでは、ラン６０５
が登録される。開始ラン指定法を適用した伝播型ランラ
ベリング法では。

ラベリングの伝播過程において隣接関係を調べる際、該
当するランの始点が含まれるブロックを算出し、そのブ
ロックの一つ左側にあるブロックに登録されたランを隣
接間の検定を開始するランとする。

前述した伝播型ランラベリング法を高速化するための二
つ目の手法、即ち終了ラン判定法では、同じく、走査線
に沿って順番に並んでいるランに対して、隣接関係の検
定を行っている途中において、あるラン以降にあるラン
に対する隣接関係の検定を走査線の途中で打ち切る。こ
のため、該当するランと走査線に並んだ対象ランとの隣
接関係を調べる前に、該当ランの終点座標と対象ランの
始点座標の大小関係を比較し、もし、対象ランの始点が
該当ランの終点より右方にあれば、隣接関係の検定を打
切り、それ以降の対象ランとの隣接関係は調べない。第
７図は終了ラン判定の説明図である。注目ランフ００に
対して、下行のランフ０３．７０４，７０５，７０６，
７０７゜７０９と隣接関係を検定することになるが、注
目ランの終点座標ｘｅ０７０２と各ランの始点座標Ｘ８
　１　、　　ｘｓ２．　　ｘｓ３．　　ｘｓ　　４　ｔ
　　Ｘ８５゜ＸＳＢの大小関係を比較する。ランフ０７
の始点座標ｘｓ６７０８は、注目ランフ００の終点座標
Ｘｆｌｏ７０２よりも大きいため、このランフ０７より
右方にあるランフ０９は隣接関係を調べる必要がないた
め、この隣接関係の検定を途中で打ち切ることができ、
高速化がはかれる。

三番目の高速化手法として次ラン変更法がある。

この手法では、徂播型ランラベリング法において、ラン
の探索過程のおよび伝播過程■で、すでにラベルを付け
られたランに対しては、それ以降の探索及び伝播過程を
行わないようにする。このために１次に述べるようにラ
ベル付けされたランの直前のランの次ランを変更し、ラ
ベル付けされたランを処理対象から削除する。即ち、ラ
ベルを付けたランに対して、その直前のランの次ラン番
地の内容として、ラベル付けされたランの直後のランの
番地を設定し、それ以降のラベリングでは、この変更し
た次ラン番地テーブルを使用する。第８−結するラン８
０１にラベルを付ける前後の次ラン；：の゛変更の様子
を説明する。図中（ａ）のラン、８・０１に対するラベ
ル付け前では、ラン８０２の、　１ 次′ランがラン８０１であり、さらに、ラン８０１の次
ランがラン８０３である。それに対して１図中（ｂ）に
示すように、ラベル付け後は、ラン８０２の次ランがラ
ン８０３になるよう変更する。

このように、ラベル付けされたラン８０１に対しては、
その前のラン８０２の次ランが変更されているため、以
降のラベリング処理では、再びアクセスする必要がなく
、従って、高速化が実現できる。但し、この方法では１
次ランを変更するため、次ラン番地テーブル及びライン
先頭番地テーブルを処理の途中で変更する処理が必要で
ある。また、ラベリング終了後、これらのテーブルの値
が変更されるため、予め、これらのテーブルの内容を保
存しておく必要がある。

先に述べた単純伝播型ランラベリング法に対して、開始
ラン指定法、終了ラン判定法２次ラン変更法のすべてを
適用したラベリング法を、ブロック分類に基づく伝播型
ランラベリングと呼ぶ。このｉ方法は、ランを単位とし
てラベルを伝播させてい良際、ランの隣接関係を調べる
対象となるランを限定し、処理時間を短くしたものであ
る。その”ｂ理過程は、先ず、■ブロックごとに連結性
の検゛、定を開始するランを予め登録する。そして、そ
の：蜂、探索過程と伝播過程を行う。この時、探索過程
では、■ラベルが割り当てられていないランをラスク走
査に沿って探索する。そして、■該当するランが見つか
ったら、そのランにまだ使われていないラベルの値を割
り当て、このランの直前のランの次ランを変更する。次
に、伝播過程に移り、■このランに連結しているすべて
のランを探して、各ランに同じラベルを割り当てる。こ
の時、上下の走査線上の連結しているランに次々に虫が
喰うように、ラベルを伝播させていくが、連結性を検定
する対象となるランをブロックに登録されている開始ラ
ンから初め、さらに、終了ラン判定により走査線の途中
でこの連結性検定を打ち切る。また、ラベルを付けたラ
ンの直前のランの次ランを変更する。もはや伝播するラ
ンがなくなった時、該当するランに連結したランはすべ
て求まったことになる。連結したランすべてにラベルを
割り当てたら、探索過程に戻り、さらにランデータのラ
スク走査を続けて、再びラベルが割り当てられていない
ランを探し、再び伝播過程に移る。このように、探索■
、■と伝播■を繰返し、ランデータ全体を探索し終わる
まで続ける手法である。

この手法の全体手順を第９図に示す。ステップ９００で
は、連結性判定の開始するランをブロックごとに分類し
てブロック分類テーブルに登録する。このブロック分類
テーブルは、ライン番号とブロック番号によりアクセス
でき、その内容はランのデータが格納されている番地で
ある。ステップ９０１では、ラベルの初期化を行う。そ
して。

ステップ９０２でラスク走査が終了するまで、ステップ
９０３以下の処理を繰り返す、ステップ９０３では、注
目ランにラベルが付いているかどうかの判定を行い、も
し注目ランにラベルが付いていない場合は、ステップ９
０４に移る。ステップ９０４では、注目ランにラベルを
付け、さらに、ステップ９０５で注目ランに連結するす
べてのランにラベルを付ける。ステップ９０６では、注
目ランの直前のランの次ランを変更し、ステップ９０７
では、ラベルの値を更新する。これらステップ９０４，
９０５，９０６，９０７の処理が終了すると、ステップ
９０２に再び戻り、一連の処理するすべてのランのラベ
ル付け手順を示す。先°゛ずステップ１０００では伝播
元テーブルを空にする。そして、ステップ１００１で、
伝播先テーブルも空にする１次いで、ステップ１００２
で注目ランを伝播元テーブルに登録し、ステップ１００
３で伝播元テーブルが空になるまでステップ１００４以
下の処理を繰り返す、ステップ１００４では、伝播元テ
ーブルが空になるまでステップ１００５以下の処理を行
い、ステップ１０１１で伝播先テーブルの内容を伝播元
テーブルに移し、ステップ１０１２で伝播先テーブルを
空にし、ステップ１００３に戻る。ステップ１００５で
は、伝播元から一つランを取り出す。

このランを伝播元ランと呼ぶ、ステップ１００６では、
取り出したランを伝播元テーブルから削除する。そして
、ステップ１００７で伝播元ランの走査線の下及び上に
隣接する走査線を求める。また、ステップ１００８では
、伝播元ランの属するブロックを算出し、ステップ１０
０９で、隣接走査線において連結性の判定を開始するラ
ンを上述゛委ツブ１０１３を繰り返す、ステップ１０１
３では、開始ランから始まる隣接走査線上のランが尽き
るまで、ステップ１０１４以下の処理を行う。

ステップ１０１４では、隣接線上のランの始点が伝播元
ランの終点より右方にあるかどう、かの判定を行い、も
し、右方にあれば、ステップ１０１５に示すように、処
理を打切り、ステップ１０１０に戻る。一方、隣接線上
のランの始点が伝播元ランの終点より右方にあれば、ス
テップ１０１６において伝播元ランに連結するランの抽
出、レベル付け、伝播先テーブルへの格納を行う。図中
（ｂ）は、ステップ１０１６の詳細手順であり、先ず、
ステップ１０２０で隣接走査線上のランはラベル付けさ
れているかどうかの判定を行い、もしラベル付けされて
いなければ、ステップ１０２１に移り、始点座標が伝播
元ランとの連結性を満たしているかどうかの判定を行う
。そして、もし、連結性を満たしている場合は、ステッ
プ１０２２に移す、終点座標が連結性を満たしているか
どうかの’ｌ：０２４で伝播先テーブルに当該ランを格
納し。

゛餐テップ１０２５で当該ランの直前のランの次ラレ番
地として当該ランの直後のランを設定する。

なお、この方法では、ラベルの同一性を記録すること及
び再度ラスク走査を行うことは不要である。

但し、前処理として、ランを予めブロックに分類してお
くことが必要である。また、処理の途中で次ランを変更
するので、次ラン番地テーブル及び、ライン先頭番地テ
ーブルが変更を受ける。そのため、前処理として、予め
この二つのテーブルの内容を保存しでおく必要がある。

これらの前処理の内、第１４図にランをブロックに予め
分類する手順を示す。ステップ１４００で走査線が終了
するまで、ステップ１４０１以下の処理を繰り返す。

先ず、ステップ１４０１では、注目ランをライン先頭番
地テーブルから読み出す。そして、ステップ１４０２で
前回のブロック番号を記憶しておくバッファを初期化す
る。ここでは、簡単のため、このバッファを前回ブロッ
ク番号と呼ぶ、ステツー□噛 、零値である間、ステップ１４０５以下の処理を行Ｊ°
う。先ず、ステップ１４０５で、注目ランの始点１、゛ ；座標を読み出す。そして、ステップ１４０６で注目ラ
ンの該当するブロック番号を算出する。この番号を注目
ブロック番号と呼ぶ。次いで、ステップ１４０７でブロ
ック分類テーブルに注目ランの番地を格納する。ステッ
プ１４０８では、ブロック番号ｊが前回ブロック番号の
内容の次のブロック番号δ値から、注目ブロック番号の
前のブロック番号まで順次、値を変更しながらステップ
１４０９の処理を行う。ステップ１４０９では、ブロッ
ク分類テーブルのブロック番号ｊの場所に。

前回ランの番地を設定する。ステップ１４１Ｏでは、前
回ブロック番号に注目ブロック番号を設定し、ステップ
１４１１で、前回ラン番地として注目ランの番地を設定
し、さらに、注目ランの次ランを新たな注目ランに設定
する。この手順から分かるように、ブロック分類テーブ
ルにラン番地を格納する必要があり、ブロックの横幅が
小さくなり、ブロックの個数が増えると、ブロック分類
に要する時間が増大する。

第１１図は、ラン符号化データメモリ部１０５の構成を
示す図である。始点座標メモリ１１００１には各ランの
始点座標が格納されている。また、終点座標メモリー１
０１には、同じく各ランの終点座標が格納されている。

次ランアドレスメモリＩ −”１１０２には、各ランの直右のランの番地が格納さ
れている。また、先頭ランアドレスメモリー１０３には
、各走査線上の最左端のランの番地が格納されている。

これらのメモリは、ラベル付け処理部１０８からアクセ
スすることができる。

また、計算機１０２からもこれらのメモリに対してアク
セスできる。

第１２図は、ブロック分類テーブルメモリ部１０７の構
成であり、ブロック分類テーブル１２００は、走査線の
位置を示すライン番号アドレスデータ１２０１とブロッ
ク番号アドレスデータ１２０２の二つのアドレスにより
アクセスできる二次元のメモリ構成になっている。これ
らのアドレスデータはラベル付け処理部１０８から出力
される。また、このブロック分類テーブル１２００の入
力データ１２０３と出力データ１２０４は同じくラベル
付け処理部１０８がら送°−られまた受は取られる。

第１３図は、ラベル付け処理部１０８の構成を示す図で
ある。座標比較部１３００はランの始点１３０２、伝播
元ライン番号テーブル１３０３゜伝播光ラン番地テーブ
ル１３０４．伝播先ライン番号テーブル１３０５の動作
を制御するとともに、ラン符号化データメモリ部１０５
．ラベルメモリ部１０６．ブロック分類テーブルメモリ
部１０７へのアドレスデータ及び入出力データを制御す
る。

伝播元ラン番地テーブル１３０２には、ラベルを伝播さ
せるソース側のランの番地がラベリング処理に従って格
納される。また、伝播元ライン番号テーブル１３０３に
は、対応するランが存在する走査線の番号が同じくラベ
リング処理に従って格納される。一方、伝播元ラン番地
テーブル１３０４には、伝播元のランに連結しラベルが
新たに付けられたランの番地が格納される。また。

伝播元ライン番号テーブル１３０５には、対応する伝播
元のランの存在する走査線の番号が格納さ、れている。

゛〔発明の効果〕 −・本発明によれば、従来の画素データに対するう、、
、、鵞リング方法と比較して、処理の対象となる画素；
、、）＞ じの個数よりランの個数が一桁すくないため、ラベｌ〕
ングに要する時間がほぼ一桁短くて済み、処理の高速化
がはかれる。さらに、ランの隣接関係を調べる対象のラ
ンを短冊状のブロックに存在するラン限定しているため
、隣接関係の検定回数が削減でき、−層の高速化が実現
できる。また、従来のランデータに対するラスク走査型
のラベリングのようなラベルの同一性を記録する必要は
なく、また再度ラスク走査を行いラベルの付替を行う必
要がなく処理が単純となる。

【図面の簡単な説明】

第１図は本発明の実施例の装置構成を示す図、第２図は
伝播型ランラベリング法の手順を示す図、第３図は第２
図のステップの詳細手順を示す図、第４図はラベルの伝
播過程を説明する図、第５図はランデータの表現形式を
示す図、第６図は開始ラン指定法を説明する図、第７図
は終了ラン判定の説明図、第８図は次ラン変更法を説明
する図、第９図は本発明の実施例の手順を示す図、第１
０図は第９図のステップの詳細手順を示す図、第１１図
はラン符号化データメモリ部の構成を示す図、第１２図
はテーブルメモリ部の構成を示す図、第１３図はラベル
付け処理部の構成を示す図、第一１４図はランのブロッ
ク分類の手順を示す図である。 ５、符号の説明 １０５・・・ラン符号化データメモリ部、１０６・・・
ラベルメモリ部、１０７・・・ブロック分類テーブルメ
モリ部、１０８・・・レベル付け処理部、５００・・・
ライン先頭番地テーブル、５０１・・・始点座標テーブ
ル、５０２・・・終点座標テーブル、５０３・・・次ラ
ン番地テーブル、６０１・・・走査線番号、６０２・・
・ブロック番号、７０２・・・終点座標、７０８・・・
始点座標、１１００・・・始点座標メモリ。

Claims (1)

【特許請求の範囲】
1. 画像の入力手段と符号化手段と表示手段とよりなる画像
   情報処理装置において、画像ランに対してラベルを伝播
   させる手段と、ランを短冊状のブロックに分類する手段
   と、当該ブロックに登録したランを基にラン同士の隣接
   関係を判定する手段と、隣接関係の判定を行う処理を走
   査線に沿った途中のランで打ち切る手段と、ランに対す
   るラベル付け処理の途中でラベル付けされたランは以後
   の処理対象から削除する手段とを設けたことを特徴とす
   る画像の連結成分抽出装置。