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

Abstract

(57)【要約】 【目的】 処理速度が速く、余分なメモリを必要としな
い画像の連結成分抽出システムを提供する。 【構成】 処理すべき対象画像の情報は処理対象画像メ
モリ１に格納され、メモリ１から抽出された連結成分は
連結成分画像メモリ３に格納される。連結成分探索手段
２は、黒画素探索部４、隣接成分探索抽出部５及びスタ
ック６により構成されている。黒画素探索部４は、処理
対象画像メモリ１を初期アドレスから主走査方向に探索
して最初にぶつかる黒画素を検出し、この黒画素を最初
の着目範囲に設定する（第１の処理）。隣接成分探索抽
出部５は、着目範囲と結合関係にある線分を探索し、検
出された線分を処理対象画像メモリ１から消去し、連結
成分画像メモリ３に書き込む。検出された線分と副走査
方向に隣接する画素範囲は、次の着目範囲とされる。ス
タック６の内容は更新され、新たな着目範囲が書き込ま
れる。この処理は、線分が検出されなくなるまで繰り返
される（第２の処理）。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、パターン認識、文字
認識、画像解析等の各種画像処理において処理対象画像
の情報から画素の連結成分を抽出する画像の連結成分抽
出装置に関する。

【０００２】

【従来の技術】従来のこの種の連結成分抽出処理は、画
像メモリを主走査方向に探索し、検出された検出対象レ
ベルの画素（例えば黒画素）に順次ラベル付けを施して
いきながら、連結された部分でのラベルの同一性を確保
していくことにより、連結成分を抽出するものであっ
た。即ち、画像メモリを主走査方向に探索しながら、着
目した黒画素の４近傍又は８近傍に存在する黒画素を順
次検出していき、検出された黒画素に着目画素と同一の
ラベルを付していく。そして、異なるラベルを付された
複数の連結領域の連結が確認されたら、その時点でラベ
ルの統合処理、つまりラベルの付け替えが行われる。

【０００３】

【発明が解決しようとする課題】上述した従来の連結成
分抽出方法では、着目画素を中心とした近傍画素の連結
関係を確認するためのマスク処理を行う必要がある。し
かし、通常、２値画像を画像メモリに格納する場合、画
面上の主走査方向の８画素を１バイトの画像データとし
て格納することが多いため、ビット単位での処理を基本
とする上記方法では、着目画素と隣接する黒画素のメモ
リアドレス及びそのアドレスによって特定される１バイ
トの画像データ中のビット位置を特定するための演算が
複雑で、逐次処理の１ステップ毎に多量の計算時間を必
要とするという問題点がある。

【０００４】また、従来の連結成分処理方法では、画素
毎にラベル付けを行い、隣接画素のラベルの同一性を調
べていくので、１画面の総画素数にラベル用の数ビット
を掛けた容量のラベル用メモリが必要になる。しかも、
上記の方法では、ラベルの統合時にラベルの付け直し処
理を行なうため、ラベルの同一性を記憶するためのメモ
リも更に必要になるという問題点がある。

【０００５】この発明はこのような問題点を解決するた
めになされたもので、処理の高速化を図ることができ、
しかも余分なメモリを必要としない画像の連結成分抽出
装置を提供することを目的とする。

【０００６】

【課題を解決するための手段】この発明に係る画像の連
結成分抽出装置は、処理すべき対象画像の情報を記憶す
る第１の画像記憶手段と、前記第１の画像記憶手段から
抽出された連結成分を記憶する第２の画像記憶手段と、
前記第１の画像記憶手段を探索して前記対象画像の情報
の一部を検出し、この検出された画像情報に基づいて主
走査方向の最初の着目範囲を決定する第１の処理手段
と、前記第１の画像記憶手段に記憶された対象画像の情
報から前記着目範囲に少なくとも一部が含まれる主走査
方向に延びる線分を探索すると共に検出された線分を前
記第１の画像記憶手段から消去し前記第２の画像記憶手
段に書込む処理を、前記検出された線分と副走査方向に
隣接する範囲を次の着目範囲として前記着目範囲を順次
更新しながら、前記線分が検出されなくなるまで繰り返
す第２の処理手段とを具備したことを特徴とする。

【０００７】

【作用】この発明においては、第１の画像記憶手段を探
索して対象画像の情報の一部、例えば対象画像の一部を
なす画素を検出し、この検出された画素を最初の着目範
囲とする（第１の処理）。次に、この着目範囲に少なく
とも一部が含まれる主走査方向に延びる線分として上記
検出された画素を含む線分が第１の画像記憶手段から消
去され、第２の画像記憶手段に書き込まれる。続いて、
上記第１の画像記憶手段から消去された線分に対して副
走査方向に隣接する範囲を次の着目範囲とし、この着目
範囲に少なくとも一部が含まれる主走査方向に延びる線
分を探索する。この処理を、着目範囲を順次更新しなが
ら線分が探索されなくなるまで繰り返すと、前記第１の
処理で最初に検出された画像情報に連結する連結成分の
みが第１の画像処理手段から全て消去され、第２の画像
処理手段に書き込まれることになる（第２の処理）。

【０００８】この発明によれば、着目範囲も検出すべき
線分も共に主走査方向に延びる範囲及び線分であるた
め、例えばビットシフトとアンド処理のみで画像記憶手
段への高速アクセスが可能になり、着目画素の近傍画素
を探索するマスク処理に比べ、探索処理を極めて高速に
行なうことができる。また、従来の連結成分抽出方式で
は、１回の探索処理で複数の連結成分が同時に検出され
るため、連結成分の同一性を確保するためのラベル付け
が必要であったが、この発明によれば、１連の探索処理
では、１つの連結成分しか検出されず、しかも検出され
た１つの連結成分は、検出終了の時点で第１の画像記憶
手段から第２の画像記憶手段に移動しているので、ラベ
ル付けの必要がない。このため、第１の画像記憶手段の
他には、少なくとも第１の画像記憶手段と同容量の画像
記憶手段のみを備えれば足り、他に余分なメモリを必要
とすることがない。

【０００９】

【実施例】以下、添付の図面を参照してこの発明の実施
例について説明する。図１はこの発明の一実施例に係る
２値画像の連結成分抽出システムの構成を示す機能ブロ
ック図である。このシステムは、処理対象画像メモリ
１、連結成分探索手段２及び連結成分画像メモリ３から
構成されている。処理対象画像メモリ１は、処理すべき
２値画像の情報を記憶する第１の画像記憶手段である。
連結成分探索手段２は、処理対象画像メモリ１から黒画
素（データ“１”の画素）の連結成分を検出して処理対
象画像メモリ１から消去し、連結成分画像メモリ３に書
き替えるもので、ソフトウェア又はハードウェアにより
構成されている。連結成分画像メモリ３は、連結成分探
索手段２によって処理対象画像メモリ１から抽出された
連結成分を記憶する第２の画像記憶手段である。

【００１０】連結成分探索手段２は、黒画素探索部４、
隣接成分探索抽出部５及びスタック６により構成されて
いる。黒画素探索部４は、処理対象画像メモリ１を初期
アドレスから主走査方向に探索して最初にぶつかる黒画
素を検出し、この黒画素を最初の着目範囲に設定する
（第１の処理）。隣接成分探索抽出部５は、図２（ａ）
に示すように、着目範囲Ａに少なくとも一部が含まれる
主走査方向に延びる黒画素の線分Ｌ1 ，Ｌ2 （以下、こ
れを「着目範囲と結合関係にある線分」と述べる）を探
索し、検出された線分を処理対象画像メモリ１から消去
し、連結成分画像メモリ３に書き込む。次に、隣接成分
探索抽出部５は、検出された線分と副走査方向に隣接す
る画素範囲を次の着目範囲として上記の処理を実行す
る。例えば、図２（ｂ）に示すように、着目画素Ｐに対
して８近傍画素を連結範囲とする場合には、検出された
線分（ｘ1 ，ｙ）−（ｘ2 ，ｙ）に対して、これと副走
査方向（Ｙ方向）に隣接する矢印で示す範囲（ｘ1 −
１，ｙ−１）−（ｘ2 ＋１，ｙ−１）、（ｘ1 −１，ｙ
＋１）−（ｘ2 ＋１，ｙ＋１）が着目範囲となる。ま
た、図２（ｃ）に示すように、着目画素Ｐに対して４近
傍画素を連結範囲とする場合には、検出された線分（ｘ
1 ，ｙ）−（ｘ2 ，ｙ）に対して、これと副走査方向
（Ｙ方向）に隣接する矢印で示す範囲（ｘ1 ，ｙ−１）
−（ｘ2 ，ｙ−１）、（ｘ1 ，ｙ＋１）−（ｘ2 ，ｙ＋
１）が着目範囲となる。ここでは、前者の８近傍画素を
連結範囲とする場合について説明する。これらの着目範
囲が決定されると、スタック６の内容が更新され、新た
な着目範囲がスタック６に書き込まれる。この処理は、
線分が検出されなくなるまで繰り返される（第２の処
理）。

【００１１】次に、上記のように構成された連結成分抽
出システムの動作について説明する。図３は連結成分抽
出処理のメインフローチャート、図４は同処理における
隣接成分探索抽出処理のフローチャート、図５〜図８は
本装置の動作を説明するためメモリ１，３の内容を模式
的に示す図である。

【００１２】先ず、処理の開始点（ｘ，ｙ）が（０，
０）に設定される（Ｓ１）。続いて、黒画素探索部４が
起動され、黒画素探索処理が実行される（Ｓ２）。この
処理により、図５（ａ）に示すように、処理対象画像メ
モリ１がアドレス（０，０）から主走査方向（Ｘ方向）
探索され、最初にぶつかる黒画素（ｘ* ，ｙ* ）［この
例では（２，２）］が検出される。この処理で黒画素が
検出されなかったら、連結成分抽出処理は終了する（Ｓ
３）。黒画素探索処理で黒画素が検出されたら、この黒
画素（２，２）−（２，２）を最初の着目範囲として設
定する（Ｓ４）。

【００１３】次に、隣接成分探索抽出部５が起動され、
隣接成分抽出処理が実行される（Ｓ５）。この処理で
は、図４に示すように、先ず着目線分と結合関係にある
黒画素線分がラスタ走査により探索される（Ｓ１１）。
図５（ｂ）の例では、着目範囲Ａが（２，２）−（２，
２）であるから、（２，２）を含む画像データのみを探
索すればよい。ここで、線分が検出されない場合には
（Ｓ１２）、スタック６に積まれている他の着目範囲に
ついて同様の処理がなされ、更に線分検出がなされない
と一連の連結成分が全て抽出されたものとして処理が終
了する（Ｓ１７）。この例では、処理対象画像メモリ１
に、線分（２，２）−（３，２）が格納されているの
で、この線分が検出されることになる。線分が検出され
たら、図５（ｂ）に示すように、検出された線分が処理
対象メモリ１から消去され（Ｓ１３）、その位置関係が
保たれたまま連結成分画像メモリ３に書き込まれる（Ｓ
１４）。スタック６に積まれた他の着目範囲についても
探索が終了したら、検出された線分と副走査方向に隣接
する範囲を次の着目範囲として同様の処理を実行する
（Ｓ１５）。図５（ｃ）の例では、線分（２，２）−
（３，２）と隣接する画素範囲（１，１）−（４，
１）、（１，３）−（４，３）が次の着目範囲としてス
タック６に格納される（Ｓ１６）。

【００１４】次の着目範囲について上記と同様に結合関
係にある黒画素線分をラスタ走査により探索すると、図
５（ｃ）に示すように、線分（３，３）−（６，３）が
検出されるので、この線分も処理対象メモリ１から消去
され、位置関係が保たれたまま連結成分画像メモリ３に
書き込まれる。このような処理を繰り返すと、図６
（ａ），（ｂ），（ｃ）及び図７に示すように、１つの
連結成分を構成する全ての線分が処理対象画像メモリ１
から消去され、連結成分画像メモリ３に書き込まれる。
図７のように、線分が検出されなくなると、隣接成分探
索抽出処理が終了する（Ｓ１２，Ｓ１７）。そこで、必
要に応じて連結成分画像メモリ３に移された連結成分に
ついて、その抽出された図形をおおう矩形内の画像に対
して、たとえば文字認識などの処理を施し（Ｓ６）、連
結成分画像メモリ３の内容をクリアして（Ｓ７）、次の
開始点を黒画素検出点（ｘ* ，ｙ* ）に変更し（Ｓ
８）、再度黒画素探索処理を実行する（Ｓ２）。これに
より、図８に示すように、次の連結成分が抽出される。

【００１５】なお、画像メモリ１，３の１つのアドレス
に８ビット（８画素）分が１バイトの画像データとして
格納されている場合には、以上の処理における画像メモ
リヘのアクセスは、次のように行なえば良い。即ち、図
９に示すように、着目範囲を（ｘ1 ，ｙ）−（ｘ2 ，
ｙ）とすると、処理対象画像メモリ１に対して（ｘ1 ，
ｙ）→（ｘ2 ，ｙ）の走査を行いながら画素値を調べて
いく。現在注目している画素を指すピクセルポインタ
は、例えば次の２つの変数で実現することができる。 （１）Byte Pointer：ピクセルポインタのあるバイトを
指すポインタ （２）And Bit ：ピクセルポインタの指すピクセルのみ
１，他は０の８ビットの数 図９の例では、初期設定時、Byte Pointer，And Bit が
それぞれ次のように設定される。 Byte Pointer＝Ｐ，And Bit ＝00100000 これらのポインタは（ｘ1 ，ｙ）の値より設定可能であ
る。着目範囲の走査のため、ピクセルポインタを１つ右
へ進めるためのアルゴリズムは次のようになる。 if（And Bit ＆ 1）（And Bit が00000001のとき） Byte Pointerをインクリメント And Bit ＝10000000 else And Bit を右シフト このような走査を行いながら、Byte Pointerの指すバイ
ト値とAnd Bit とのアンドをとることにより、ピクセル
ポインタの指す画素値を調べていく。そして、アンド結
果（画素値）が“１”である画素を着目範囲と結合関係
にある線分の一部であるとして連結成分画像メモリ３に
書き込む。これにより高速処理が実現できる。

【００１６】このように、この実施例に係るシステムに
よれば、主走査方向に延びる着目範囲と、主走査方向に
延びる黒画素線分との結合関係を調べるようにしている
ので、画像メモリ１への高速アクセスが極めて容易であ
り、高速処理が可能である。また、この装置によれば、
１連の探索処理で検出される連結成分は１つであり、か
つ検出された連結成分は処理対象画像メモリ１から連結
成分画像メモリ３に移されるため、探索過程で連結成分
のラベル付けを行なう必要がない。このため、連結成分
画像メモリ３は、処理対象画像メモリ１と同様の容量だ
けを持てばよい。

【００１７】なお、以上の実施例では、２値画像の黒画
素連結成分を抽出したが、多値画像の特定のレベルの画
素の連結成分を抽出する場合にも本発明を適用可能であ
る。また、第１の処理手段は、対象画像の情報の一部を
検出するものであれば、対象画像のどの部分を最初に検
出してもよい。また、検出される画像情報は、画素のみ
ならず主走査方向に延びる線分であってもよい。

【００１８】

【発明の効果】以上述べたように、この発明によれば、
着目範囲及び検出すべき線分が共に主走査方向に延びる
範囲及び線分であるため、画像記憶手段への高速アクセ
スが極めて簡単になる。このため、探索処理の高速化を
図ることが可能になる。また、この発明によれば、１連
の探索処理では、１つの連結成分しか検出されず、しか
も検出された１つの連結成分は、検出終了の時点で第１
の画像記憶手段から第２の画像記憶手段に移動している
ので、探索途中でラベル付けを行なう必要がない。この
ため、第１の画像記憶手段の他には、少なくとも第１の
画像記憶手段と同容量の第２の画像記憶手段を必要とす
るだけとなり、他に余分なメモリを必要としないという
効果を奏する。

【図面の簡単な説明】

【図１】 この発明の一実施例に係る２値画像の連結成
分抽出システムの機能ブロック図である。

【図２】 同システムにおける隣接成分探索抽出部の機
能を説明するための図である。

【図３】 同システムにおける連結成分抽出処理のメイ
ンフローチャートである。

【図４】 同処理における隣接成分探索抽出処理のフロ
ーチャートである。

【図５】 同システムの動作を説明するための図であ
る。

【図６】 同システムの動作を説明するための図であ
る。

【図７】 同システムの動作を説明するための図であ
る。

【図８】 同システムの動作を説明するための図であ
る。

【図９】 同システムの動作を説明するための図であ
る。

【符号の説明】

１…処理対象画像メモリ、２…連結成分探索手段、３…
連結成分画像メモリ、４…黒画素探索部、５…隣接成分
探索抽出部、６…スタック。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 処理すべき対象画像の情報を記憶する第
   １の画像記憶手段と、 前記第１の画像記憶手段から抽出された連結成分を記憶
   する第２の画像記憶手段と、 前記第１の画像記憶手段を探索して前記対象画像の情報
   の一部を検出し、この検出された画像情報に基づいて主
   走査方向の最初の着目範囲を決定する第１の処理手段
   と、 前記第１の画像記憶手段に記憶された対象画像の情報か
   ら前記着目範囲に少なくとも一部が含まれる主走査方向
   に延びる線分を探索すると共に検出された線分を前記第
   １の画像記憶手段から消去し前記第２の画像記憶手段に
   書込む処理を、前記検出された線分と副走査方向に隣接
   する範囲を次の着目範囲として前記着目範囲を順次更新
   しながら、前記線分が検出されなくなるまで繰り返す第
   ２の処理手段とを具備したことを特徴とする画像の連結
   成分抽出装置。