JPH0434670A - 画像処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ｃ発明の目的］ （産業上の利用分野） 本発明は、２値画像における図形のラベリングと上記図
形の包含関係の抽出を効率的に行うことのできる画像処
理装置に関する。

（従来の技術） ２値画像中の図形を認識処理する場合、例えば連続する
黒画素の繋がり領域を図形部分として検出することが重
要である。また検出された複数の図形間の包含関係を正
しく判断することが重要である。

従来、２値画像における図形部分を検出する為の処理と
しては、専らラベリング処理が用いられている。このラ
ベリング処理は、画像メモリに格納された２値画像をラ
スク走査し、画素毎に隣接点との間でのラベル付けの条
件判定を行いながら、各画素に順次ラベルを付与するこ
とによりなされる。この際、適宜ラベルの統合処理等の
ラベルの書き換えが行われ、連続する１つの連結黒画素
領域には１つのラベルが付与されるようにラベル付けの
制御が行われる。

しかして従来、この種のラベリング処理は、般的には専
用ハードウェアを用いて行われる。然し乍ら、専用ハー
ドウェアを用いる場合は、その処理速度が速いもののコ
ストが掛ると云、う欠点がある。反面、ソフトウェアを
用いてラベリング処理を行う場合は、その処理時間が非
常に長くなると云う問題があった。

またこのような従来のラベリング処理を実行する場合、
ラベリングされた図形の包含関係を同時に検出していく
ことはできない。この為、ラベリング処理が行われた後
、改めてそのラベリング結果に基づいて複数の図形間の
包含関係を調べると云う処理が必要であった。これ故、
その処理には多大な時間を要した。

（発明が解決しようとする課１ｉ） このように従来の画像処理技術にあっては、２値画像を
ラベリング処理して図形を検出しながら図形の包含関係
を調べることができず、結局、その処理に多大な時間を
必要とすると云う問題があった。

本発明はこのような事情を考慮してなされたもので、そ
の目的とするところは、２値画像に対するラベリング処
理と図形の包含関係の判定処理とをソフトウェア的に簡
易に、効率的に行うことのできる画像処理装置を提供す
ることにある。

［発明の構成］ （課題を解決するための手段） 本発明に係る画像処理装置は、２値画像における画素の
連なりで構成されるランの始点と終点の座標を求め、こ
の座標情報に所定の属性記録用項目を付加してテーブル
として記憶し、このテーブルを用いて前記２値画像にお
ける図形の輪郭線を追跡する為の変化点移動用ポインタ
を生成し、この変化点移動用ポインタに従って前記図形
の輪郭線を追跡しながら図形のラベリングと図形の包含
関係の抽出をソフトウェア的に高速に実行するようにし
たことを特徴とするものである。

（作　用） 本発明によれば、２値画像における画素の連なりで構成
されるランの始点と終点の座標情報と所定の属性記録用
項目とを格納したテーブルを準備し、このテーブルを用
いて変化点移動用ポインタを生成して前記２値画像にお
ける図形の輪郭線を追跡して図形のラベリング処理を行
うので、特殊な画像メモリを用意して２値画像の画素を
順次アクセスすることなく１．その処理をソフトウェア
的に簡易に、且つ高速に実行することができる。

また図形の輪郭線の隣接関係をランという媒体から前記
テーブル上で高速に検索することができるので、上述し
たラベリング処理と同時に図形の包含関係も抽出してい
くことができる。

（実施例） 以下、′図面を参照して本発明に係る画像処理装置の一
実施例につき説明する。

第１図は実施例装置における画像処理手続きの概念を示
す図で、第２図は実施例装置の概略的な構成を示すブロ
ック図である。

この実施例装置は、概略的には処理対象とする図面を光
学的に読取り入力し、ライン走査された２値画像データ
として取り込むスキャナ１１このスキャナ１から入力さ
れた２値画像の各ラインにおける画素の連なりで構成さ
れるランの始点と終点の座標を求めて後述する第４図に
示すようなテーブルを作成するエンコーダ２、このエン
コーダ２にて作成されたテーブルを用いて図形の輪郭線
追跡の為のポインタを作成し、このポインタに従って前
記２値画像における図形の輪郭線を追跡してラベリング
処理と図形の包含関係の検出を行うプロセッサ３．およ
びこのプロセッサ３にて求められた図形のラベリング結
果、および図形の包含関係の情報を格納する記憶装置４
とにより構成される。

しかしてこのように構成される本装置において前記プロ
セッサ３は、第１図にその処理手続きの流れを示すよう
に、先ずエンコーダ２を起動して２値画像における画素
の連なりで構成されるランの始点と終点の座標を求め、
この座標情報に従って第４図に示すような座標値と各種
属性項目とからなるテーブルを作成する（ステップＡ）
。そしてこのテーブルに従って前記２値画像における図
形の輪郭線追跡の為のポインタを作成しくステップＢ）
、このポインタを用いて前記テーブル上で輪郭線追跡を
行いながら前記２値画像に対するラベリング処理、およ
び図形の包含関係の検出処理を同時に実行する（ステッ
プＣ）。

このような処理手続きを更に詳しく説明すると、例えば
第３図に示すような２値画像が与えられた場合、エンコ
ーダ２にて次のようにして画素の連なりを示すランの始
点および終点の検出が行われる。即ち、エンコーダ２は
、第３図に例示する２値画像の斜線部（黒画素）で示す
図形５の部分に関し、各走査ライン毎に斜線部の画素の
連なりを示すランの始点６と終点７の座標をそれぞれ検
出する。これらの始点６および終点７は、各ラインにお
いてその画素情報が白から黒に、或いは黒がら白に変化
している点であり、これらを総称して変化点と称される
。

しかしてエンコーダ２は、上述した如く求められるラン
の始点および終点の座標情報に従い、例えば第４図に示
すような、上記ランの変化点の座標、および画像処理に
必要な情報を書き込む領域（属性項目）を確保したテー
ブルを作成する。尚、このテーブルの作成を前記プロセ
ッサ３にて行うことも可能であり、また上述したエンコ
ーダ２での処理機能を含めてプロセッサ３での処理とし
て実現するようにしても良い。

第４図に示すように上記テーブルには、走査ライン（Ｙ
座標）毎に検出されるランの変化点にそれぞれ対応して
、前記ランの変化点（始点６．終点７）の座標（Ｘ座標
）を格納する項目［Ｘ座標］８、図形の輪郭追跡の為の
変化点の移動を示すポインタを格納する項目［ポインタ
］９、輪郭追跡時に追跡済みの情報や輪郭の種類の情報
を格納する項目［追跡フラグ］１０、ラベルの番号を記
録する為の項目［ラベル番号］　ＩＩ、図形の包含関係
を記録する為の項目［親番号］　１２が設定されている
。

しかしてこのテーブルには前記各ラインから検出される
ランの変化点のＸ座標が行単位に順に記録される。この
際、第０ライン目は仮想的にランが１つもない状態を設
定しておく。またテーブルの奇数行目にはランの始点６
についての情報が前記各項目に亘って記録され、更に偶
数行目には前記ランの始点６と対をなす終点７について
の情報が前記各項目に亘って記録される。そしてこのテ
ーブルの各ラインの終わりには、無限延に長さ［１］の
ランが存在すると想定して十分大きな変化点の座標を書
き込んでおき、処理過程における当該ラインのランの終
端を示すフラグの代わりとする。また１つの走査う゛イ
ンにおける終端の変化点の情報については、）ｌ！４図
に示すようにラベル番号［０］を初期情報として設定し
ておく。即ち、画像上の全ての図形は、ラベル番号０が
ついた図形に包含されているとして初期設定しておく。

このようにして作成されるテーブルの情報に従い、前記
プロセッサ３は前記２値画像における図形の輪郭線を次
のようにして追跡し、図形に対するラベリング処理と、
図形の包含関係の検出処理とを同時に実行する。

さて上述したテーブルを用いた輪郭線の追跡は、例えば
第５図にその処理概念を示すように、前述した各ランの
変化点が輪郭線上のどのランの変化点と、繋がっている
かのリンク関係を求め、このリンク関係に従って次に移
動すべきランの変化点の番号を前記テーブルのポインタ
の項目に順次記録していくことによってなされる。

上記リンク関係は、例えば第６図に示すように上下に隣
接する２ラインに注目し、Ｘ方向に変化点が出現する順
番に変化点の対を決定することにより求められる。この
変化点の対は、その連結関係を４連結とした場合と８連
結とした場合とで若干具なる。具体的には変化点の境界
線が等しい位置にあるような場合、４連結の場合には第
７図（ａ）（ｂ）に示すように境界線の手前側の変化点
が対として求められ、また８連結の場合には第８図（ａ
）（ｂ）に示すように境界線の奥側の変化点が対として
求められる。

しかしてポインタの向きは上記′変化点の対の形により
一意に決定される。即ち、ポインタの向きは、第９図（
ａ）〜（ｊ）に示すように変化点の対の形に対応して全
部で１０通りある。このようなポインタを示す矢印の尾
にあたる変化点の前記テーブルのポインタの項目に上記
矢印の先の変化点の番号を記憶することで前記リンク関
係の記述が行われる。このような処理を全てのラインに
ついて行うことにより、例えば前述した第５図に示すよ
うな図形の輪郭線を示すリンク関係が全ての変化点につ
いて求められる。

以上の処理により前記テーブルに輪郭線追跡の為のポイ
ンタが、前述したリンク関係に従って求められ、ポイン
タを辿ることにより輪郭線を追跡することが可能となる
。

このテーブルを用いた輪郭線追跡による図形のラベリン
グ処理と、図形の包含関係の抽Ｗ処理に先立って、これ
らの処理を行う上での重要な用語を次のように定義する
。

第１０図に示すように、例えば輪郭線を閉じた弧の中心
方向に図形を持ち、反時計回りに追跡される輪郭線をこ
こでは［外輪郭線］１３と定義する。

また閉じた弧の中心方向に背景を持ち、時計回りに追跡
される輪郭線をここでは［内輪郭線］１４と定義する。

更に成る注目する変化点から左側に走査したとき、最初
にぶつかる輪郭線をその変化点の［左隣接輪郭線］１５
として定義する。

尚、前記テーブルにおける［追跡フラグコの項目１０は
、輪郭線を追跡に伴って追跡済みのフラグを順次量てる
為の項目であり、追跡前には［０］のフラグが立てられ
ている。そして輪郭線追跡が行われたとき、上記［追跡
フラグ］の項目１０にはその輪郭線の種類を示す情報（
外輪郭線、内輪郭線）が順に記録される。このようにし
て［追跡フラグ］の項目１０に記録される輪郭線の種別
を示す情報（外輪郭線、内輪郭線）は、変化点が含まれ
る輪郭線の識別に用いられる。

また前記テーブルの［ラベル番号］の項目１１に記録さ
れる番号は、１つの外輪郭線１３と０個以上の内輪郭線
１４とを持つ図形に固有な番号として付与される。この
番号がラベリング処理された図形のラベル番号となり、
変化点が含まれる図形の識別に用いられる。更に前記テ
ーブルの［親番号］の項目１２には、成る図形を包含す
る別の図形のラベル番号が記録される。この親番号は、
変化点が含まれる図形を包含している他の図形を識別す
る為に用いられる。

ここで前記テーブルのポインタに従う図形の輪郭線追跡
と、この輪郭線追跡に伴う図形のラベリング処理および
図形の包含関係の検出処理について具体的に説明する。

この処理は、先ず前述した第４図に示すようなテーブル
の先頭から未追跡の変化点を調べることから開始される
。テーブルにおいて、その先頭から未追跡の変化点を調
べる処理は、２値画像をラスク走査して変化点を探索す
る処理に相当する。

しかして未追跡の変化点が見出されたら、前記テーブル
の［ポインタ］の項目９に記述された情報（輪郭線追跡
用ポインタ）を利用して上記未追跡の変化点（追跡開始
点１６）から次の変化点への追跡を開始し、この変化点
の追跡処理を前記追跡開始点１６に戻ってくるまで実行
することで輪郭線を追跡する。この際、後述するような
条件に従って前記テーブルの変化点の各項目に必要な情
報を逐次記録していく。

具体的には前記テーブルの［ラベル番号］の項目１１に
対しては、追跡される変化点の行、およびその変化点を
含むランのもう一方の変化点の行ををそれぞれ特定し、
これらの各行の［ラベル番号コの項目１１に、次のよう
な条件に従って決定されるラベル番号をそれぞれ記入す
る。

即ち、前記開始点１Ｂがランの始点６ならば、最新のラ
ベル番号に［１コを足した番号、つまり新しい番号を［
ラベル番号コの項目１１に記録する。

また開始点１Ｂがランの終点７ならば、そのランの始点
６のラベル番号を前記［ラベル番号］の項目１１に記録
する。

この条件に示されるｒランの始点６のラベル番号をその
まま［ラベル番号］の項目１１に記録する」と云う処理
は、前記開始点１６の左隣接輪郭線１５を含む図形のラ
ベル番号を継承することを意味する。

即ち、開始点１６がランの始点６である場合には、その
変化点（開始点１Ｂ）が外輪郭線１３上にあることを意
味し、新しい図形領域の輪郭線を追跡することになる。

従ってこの場合には、その変化点（始点６）、およびこ
の変化点を含むランのもう一方の変化点（終点７）の各
［ラベル番号］の項目１１にそれぞれ新しいラベル番号
を記録し、新たなラベリング領域とする。

また前記輪郭線追跡の開始点１Ｂがランの終点７である
場合には、その変化点（開始点１Ｂ）が内輪郭線１４上
にあることを意味する。しかしてこの内輪郭線１４の追
跡時には、その対となる外輪郭線１３については、必ず
その追跡処理が既に済んでおり、その［ラベル番号］の
項目１１には必ずラベル番号が付与されている。従って
この場合には、変化点を含むランのもう一方の変化点（
始点６）が前記テーブルにおける当該変化点の行の前後
いづれかの行に存在する。故に、もう一方の変化点（始
点６）を容易に検索することが可能であり、このランの
一方の変化点（始点６）の［ラベル番号コの項目１１に
記載されているラベル番号をそのまま、当該変化点の［
ラベル番号］の項目１１に記載する。

このようにして順次追跡される変化点の各［ラベル番号
コの項目１１に、上述した如く定まるラベル番号を順次
記録していくことにより、図形に対するラベリング処理
が実行される。

一方、前記テーブルの［新番号］の項目１２に対しては
、追跡される変化点の行、およびその変化点を含むラン
のもう一方の変化点の行ををそれぞれ特定し、これらの
各行の［親番号コの項目１２に、次のような条件に従っ
て決定されるラベル番号をそれぞれ記入する。

即ち、［親番号コの項目１２には、開始点１６がランの
始点６である時、次のような条件で決定する新番号（ラ
ベル番号）を記録する。開始点１６がランの終点７であ
る場合には、新番号の記録は行わない。

即ち、新番号は、開始点１Ｇの左隣接輪郭線１５が内輪
郭線１４である場合には、上記開始点１Ｂを含む外輪郭
線１３が形成する図形が上記左隣接輪郭線１５（内輪郭
線１４）で示される図形に包含されていることを意味す
る。従ってこの場合には、前記内輪郭線１４を含む図形
のラベル番号を上記開始点１６を含む外輪郭線Ｉ３が形
成する図形の新番号、つまりその変化点についての新番
号の情報とする。

また開始点１Ｂの左隣接輪郭線１５が外輪郭線１３であ
る場合には、上記開始点１６を含む外輪郭線１３が形成
する図形か、上記左隣接輪郭線１５（外輪郭線１３）を
含む図形と独立に存在することを意味する。

従ってこの場合には、前記開始点１Ｂを含む外輪郭線１
３が形成する図形についての新番号、つまりその変化点
についての新番号を、上記左隣接輪郭線１５（外輪郭線
１３）を含む図形の新番号（ラベル番号）と同じにする
。

尚、上述したようにして求められる左隣接輪郭線１５の
ラベル番号および新番号は、当該輪郭線の追跡時には既
に追跡処理が終了した輪郭線についての情報として必ず
求められているものである。

このような処理を、前記テーブルに記述される変化点の
情報について、その最後尾までの未追跡の変化点の全て
に亘って繰り返し実行する。そして各変化点について前
述した各項目の情報をそれぞれ調べ終わったとき、その
処理を終了する。この結果、前記テーブルの項目情報か
ら、例えばランの始点８についてのラベル番号１１に従
うことにより、第１１図に示すようなラベリング処理結
果を求めることが可能となる。また前記テーブルの、例
えばランの始点Ｂについてのラベル番号１１と親書号１
２とに従うことにより、包含する図形を親とし、包含さ
れる図形を子供として、例えば第１２図に示すような木
構造のリストを作成することができ、このリストにて図
形の包含関係を記述することが可能となる。

尚、図形の包含関係については、例えば第１３図に示す
ようなリスト構造をポインタを用いてリンクさせて記述
するようにしても良い。この場合、ラベリングされた図
形は同一ラベル番号１１を持つランから容易に再現する
ことができる。また上述した包含関係の検出の手法を拡
張することにより、輪郭線間の包含関係も検出すること
ができる。

かくして本発明によれば、２値画像における画素の連な
りで構成されるランの始点と終点の情報から、前述した
テーブルを用いたポインタの制御による輪郭線の追跡処
理によって前記２値画像における図形のラベリング処理
と図形の包含関係の検出処理とを一括して効率良く実行
することができる。つまりラン表現された２値画像情報
に対して、そのままラベリング処理と図形の包含関係の
検出処理とを行うことができる。しかも特殊な画像メモ
リを用いることなく、テーブルに対する処理制御だけで
ソフトウェア的に簡易にラベリング処理を実行し、同時
に図形の包含関係を検出することができる。従ってその
処理効率が非常に高く簡易に２値画像に対する図形処理
を実行することを可能とする等の実用上多大なる効果が
奏せられる。

尚、本発明は上述した実施例に限定されるものではない
。例えば図形の包含関係を検出することのみならず、同
様にして輪郭線間の包含関係を検出することも可能であ
る。この場合には、前述した第４図に示した構造のテー
ブルにおいて前述したラベル番号に代えて輪郭線番号を
生成し、親番号には包含される図形ではなく輪郭線の番
号を記録するようにすれば良い。その他、本発明はその
要旨を逸脱しない範囲で種々変形して実施することがで
きる。

［発明の効果］ 以上説明したように本発明によれば、ソフトウェア的な
手法により高速度に２値画像における図形のラベリング
処理と図形の包含関係の検出処理とを行うことができる
。しかも２値画像をランデータとして取扱いながら、効
率良くその処理を実行することができる。従って従来の
画像処理のように特別なハードウェアを用いる必要がな
く安価に画像処理を行うことができ、また汎用計算機を
用いた場合であっても十分速い処理速度で画像処理が行
える。特に地図における等高線の包含関係等を検出する
場合でも、高速にその処理を行うことができる等の実用
上多大なる効果が奏せられる。

【図面の簡単な説明】

図は本発明の一実施例に係る画像処理装置について示す
もので、第１図は実施例装置における概略的な画像処理
の手順を示す図、第２図は実施例装置の概略的な構成を
示すブロック図、第３図は２値画像の画素イメージの例
を示す図、第４図は実施例装置で用いられるテーブルの
構造を示す図、第５図は輪郭線と変化点のリンクを説明
する為の図、第６図は２ライン間の変化点の対を示す図
、第７図および第８図は４連結と８連結とにおける変化
点の対の違いを示す図、第９図は変化点対のポインタの
向きの種類を示す図、第１０図は実施例装置における画
像処理での用語の定義を示す図、第１１図はラベリング
された図形の例を示す図、第１２図は図形の包含関係を
本構造で表した図、第１３図はリスト構造をポインタを
用いてリンクさせて図形の包含関係を記述する例を示す
図である。 ｌ・・・スキャナ（２値画像の入力手段）、２・・・エ
ンコーダ（２値画像からのランの始点・終点の検出手段
）、３・・・プロセッサ（画像処理手段）、４・・・記
憶装置、Ａ・・・テーブルの作成処理、Ｂ・・・輪郭線
追跡の為のポインタ生成処理、Ｃ・・・輪郭線追跡によ
るラベリンク処理および図形の包含関係検出処理。

Claims (5)

【特許請求の範囲】
1. （１）２値画像における画素の連なりで構成されるラン
   の始点と終点の座標をそれぞれ求める手段と、この座標
   情報に所定の属性記録用項目を付加してテーブルに登録
   する手段と、このテーブルを用いて前記２値画像におけ
   る図形の輪郭線を追跡する為の変化点移動用ポインタを
   生成する手段と、この変化点移動用ポインタを用いて前
   記図形の輪郭線を追跡しながら前記図形のラベリングお
   よび図形の包含関係の抽出を行う手段とを具備したこと
   を特徴とする画像処理装置。
2. （２）属性記録用項目は、輪郭線追跡の為の変化点移動
   用ポインタ項目、図形のラベル番用項目、包含される図
   形のラベル番号を格納する親番号用項目、および輪郭情
   報用項目からなることを特徴とする請求項（１）に記載
   の画像処理装置。
3. （３）変化点移動用ポインタは、隣接する２ラインのラ
   ンの変化点の対を２値画像の走査方向における出現順に
   求めて生成され、この対をなす変化点のパターンに応じ
   て前記変化点移動用ポインタの向きを決定することを特
   徴とする請求項（１）に記載の画像処理装置。
4. （４）図形のラベリングは、輪郭線追跡時の開始点がラ
   ンの始点である時には新しいラベル番号を上記輪郭線追
   跡時の変化点を含むランのラベル番号項目に記録し、前
   記開始点がランの終点である時には当該ランのラベル番
   号を前記輪郭線追跡時の変化点を含むランのラベル項目
   に記録して行われることを特徴とする請求項（１）に記
   載の画像処理装置。
5. （５）図形の包含関係の抽出は、輪郭線追跡時の開始点
   がランの始点である時に行われ、同じラインの１つ手前
   の変化点を含む輪郭線追跡の向きが上記開始点を含む輪
   郭線追跡の向きと等しい時には、前記１つ手前の変化点
   を含む図形を包含する図形のラベル番号を親番号項目に
   記録し、輪郭線追跡の向きが等しくない時には、前記１
   つの前の変化点を含む図形のラベル番号を前記親番号項
   目に記録して行われることを特徴とする請求項（１）に
   記載の画像処理装置。