JPH06101040B2 - ベクトルデ−タ境界追跡処理方式 - Google Patents

Description

【発明の詳細な説明】 〔発明の属する分野の説明〕 本発明は，地図や図面などの線画から，閉境界を自動抽
出する処理システムにおけるベクトルデータ境界追跡処
理方式に関するものである。

〔従来の技術の説明〕

従来，地図や図面を画像として計算機に入力して，閉境
界を抽出する方式として，入力されたディジタル画像か
ら画素を１つずつ追跡して閉境界を求めるもの（長尾監
訳，ディジタル画像処理，近代科学社,pp.353−359）
と，入力画像を，図形上にあり水平方向に連続する画素
の固まり（ランと呼ぶ）に変換してから，ランを１つず
つ追跡して閉境界を求めるもの（T.Pavlidis,Structur-
al Pattern Recognition,Springer-Verlag,pp.115−12
1）のみが考案されていた。

一方，地図や図面などの画像は，細線化して中心線イメ
ージデータを求め，その中心線イメージデータをベクト
ル化して，ベクトルデータに変換した後，自動認識処理
や会話処理を行うことが効率的であるため，ベクトルデ
ータに対する境界追跡方式が必要となるが，従来はこれ
に関する有効な方式がなかった。

〔発明の目的〕

本発明は，計算機に入力されたディジタル画像を細線化
して得られる中心線から，境界追跡に適したベクトルデ
ータを作成すると共に，そのベクトルデータ上で境界追
跡を行う手段を提供することを目的とする。

このような目的を達成するために，まず，中心線イメー
ジデータを以下のようにベクトル化する。

（ア）孤立点，端点，分岐点に加えて，孤立ループに属
する画素の中でラスタ走査により最初に検出される画素
（例えば,TV式のラスタ走査では，最上行の最左列にあ
る画素），及び端点と分岐点のいずれかである二つの画
素間を結ぶ中心線の画素列に属する画素の中でラスタ走
査により最初に検出される画素（例えば,TV式のラスタ
走査では，最上行の最左列にある画素）を特徴点と呼
び，特徴点をベクトルの節点にする。

（イ）二つの上記特徴点を結ぶ中心線の画素列を直線近
似してベクトル列に変換し，そのベクトル列を処理単位
（ブランチと呼ぶ）として，その一方の特徴点を開始特
徴点，他方の特徴点を終了特徴点としてベクトルデータ
の一部とする。

（ウ）各特徴点について，線図形上にある近傍画素の位
置と近傍画素が属するブランチの識別番号をベクトルデ
ータの一部とする。

次に，このベクトルデータの各ブランチに対して，開始
特徴点と終了特徴点が異なるブランチに対しては，開始
特徴点から終了特徴点の方向を正方向，その逆の方向を
逆方向と定義し，開始特徴点と終了特徴点が等しいブラ
ンチに対しては，開始特徴点かつ終了特徴点である特徴
点の近傍を，ラスタ走査において注目特徴点に到達した
とき既走査になっている近傍位置から反時計回り（又は
時計回り）に調べて，最初に該ブランチが存在する近傍
位置から出て，該ブランチが存在するもう一つの近傍位
置から至る方向を正方向，その逆の方向を逆方向と定義
し，各ブランチに対して正方向に追跡されたか否か（正
方向追跡済フラッグと呼ぶ）と，逆方向に追跡されたか
否か（逆方向追跡済フラッグと呼ぶ）を示すフラッグを
設け，以下の規制により一本の境界を追跡する。

（ａ）正方向追跡済フラッグが偽であるブランチを正方
向に追跡し，その正方向追跡済フラッグを真にする。

（ｂ）逆方向追跡済フラッグが偽であるブランチを逆方
向に追跡し，その逆方向追跡済フラッグを真にする。

（ｃ）注目ブランチB1が正方向に追跡されたならば,B1
の終了特徴点NEの近傍を,B1を正方向に追跡したとき特
徴点NEに入ってくる位置から反時計回り（又は時計回
り）に検査して２番目に検出されるブランチB2を新たな
注目ブランチとし，その追跡方向を特徴点NEから検出さ
れた位置へ出る方向にする。

（ｄ）注目ブランチB1が逆方向に追跡されたならば,B1
の開始特徴点NSの近傍を,B1を逆方向に追跡したとき特
徴点NSに入ってくる位置から反時計回り（又は時計回
り）に検査して２番目に検出されるブランチB2を新たな
注目ブランチとし，その追跡方向を特徴点NSから検出さ
れた位置へ出る方向にする。

（ｅ）注目ブランチの正方向追跡済フラッグと逆方向追
跡済フラッグの中で，その１つ前に追跡されたブランチ
の追跡方向から決まる方向のフラッグが偽であるなら
ば，追跡を終了する。

〔発明の構成および作用の説明〕

以下では，ラスタ走査としてTVラスタ走査を用いる場合
について説明する。

第２図は，画素（i,j）の近傍画素の位置に対する定義
を示す図である。各位置に対する番号の付け方は，各位
置に一意な番号を割り当てれば，どのような値でもよ
い。通常は，実現しやすいように，反時計回り（又は時
計回り）に１から８までの連続する整数を割り当てる。

第３図は，特徴点を置く画素を説明する図である。図
中,1は線図形の中心線,2は背景,N1〜N8は特徴点を表
す。

第３図（ａ）において，四角により示した画素は，端点
と分岐点のいずれかである２つの特徴点間を結ぶ中心線
の画素列に属する画素の中で，最上行の最左列にある画
素を示す。また，第３図（ｂ）において，四角により示
した画素は，孤立ループの最上行の最左列にある画素を
示す。孤立点，端点，分岐点に加えて，このような画素
を特徴点とする。二つの特徴点間を直線近似等により複
数のベクトルに分解することにより，特徴点はベクトル
の節点（すなわち，開始節点又は終了節点）になる。こ
れにより，後述する手順により全てのベクトルの境界を
効率良く追跡することができる。

第４図及び第５図は，ベクトルデータの構造を示す図で
ある。第４図（ａ）は，中心線イメージデータにおける
特徴点の例を示している。第４図（ｂ）は，第４図
（ａ）に対する特徴点テーブルの構造を示している。

すなわち，特徴点番号が特徴点テーブルの要素の番号に
対応し，各要素には，特徴点のｘ−ｙ座標と，特徴点の
各近傍位置に接続するブランチの番号が格納されてい
る。接続するブランチの位置を示す番号は，第２図の近
傍位置を示す番号１から８に対応する。接続するブラン
チがない近傍位置には，値「０」を代入しておく。

第５図（ａ）は，ブランチの例を示している。第５図
（ｂ）と（ｃ）は，第５図（ａ）に対するブランチテー
ブルとベクトルテーブルの構造を示している。

ブランチは，第５図（ａ）に示すように，二つの特徴
点，例えば，特徴点N5とN6とを結ぶ曲線を直線近似する
ことによって得られる複数のベクトルからなる。第５図
（ｂ）に示すように，ブランチテーブルでは，ブランチ
番号がブランチテーブルの要素の番号に対応し，各要素
には，ブランチを抽出するときの追跡の出発点となる特
徴点（開始特徴点と呼ぶ）の番号，ブランチを抽出する
ときの追跡の終了点となる特徴点（終了特徴点と呼ぶ）
の番号，ブランチを開始特徴点から終了特徴点に向けて
追跡したとき最初に追跡されるベクトル（開始ベクトル
と呼ぶ）の番号，ブランチを開始特徴点から終了特徴点
に向けて追跡したとき最後に追跡されるベクトル（終了
ベクトルと呼ぶ）の番号，正方向追跡済フラッグ，逆方
向追跡済フラッグを格納している。但し，正方向追跡済
フラッグと逆方向追跡済フラッグとは，ベクトルデータ
の境界追跡を行うためだけに必要であり，ベクトルデー
タを構成する他の部分と切り離すこともできる。

第５図（ｃ）に示すように，ベクトルテーブルでは，ベ
クトル番号がベクトルテーブルの要素の番号に対応し，
各要素には，ベクトルが属するブランチと，ベクトルの
開始節点と終了節点が格納されている。第５図（ｃ）に
示すように，ベクトルは抽出された順にベクトルテーブ
ルに格納されるために，同じブランチに属するベクトル
は，ベクトルテーブル上において連続して現われる。

第５図に示されているベクトルデータを得るためのベク
トル比は，入力ディジタル画像を細線化して得られる画
像について，以下の手順1-1から手順1-2の手順を実行す
ることにより実現される。なお，細線化画像は，初期値
として，背景上にある画素の値を「０」，中心線上にあ
る画素の値を「１」とする。以下のベクトル化の後に
は，特徴点である画素の値は，特徴点番号に，その他の
中心線上の画素の値は，値「２」に順次置き換えられ
る。

［手順1-1］ 検出済みの特徴点の最大番号NNを「２」に，検出済みの
ブランチの最大番号BNを「０）に，検出済みのベクトル
の最大番号VNを「０」に初期設定する。但し,BNは注目
ブランチの番号にも等しい。

［手順1-2］ 細線化画像をTVラスタ走査して，孤立点と端点と分岐点
のいずれかであるか，又は値が「１」である画素（i,
j）を検出するたびに（すなわち，特徴点を検出するた
びに）,TV式ラスタ走査を中断して，特徴点（i,j）の近
傍から正の値をもつ画素をすべて抽出し，手順1-2-1か
ら手順1-2-3を実行してから,TV式ラスタ走査に戻る。

［手順1-2-1］ 特徴点（i,j）が孤立点ならば,NNの値を「１」だけ増や
し，特徴点（i,j）の値をNNの値に置き換え，特徴点テ
ーブルのNN番目に特徴点（i,j）の座標を格納し，特徴
点テーブルのNN番目のすべての接続ブランチを「０」に
設定し,TV式ラスタ走査に戻る。

［手順1-2-2］ 特徴点（i,j）の値が「１」ならば,NNの値を「１」だけ
増やし，特徴点（i,j）の値をNNの値に置き換え，特徴
点テーブルのNN番目に特徴点（i,j）の座標を格納し，
特徴点テーブルのNN番目のすべての接続ブランチを
「０」に設定し，注目ブランチの開始特徴点番号NSにNN
の値を代入する。特徴点（i,j）の値が「１」でなけれ
ば,NSに特徴点（i,j）の値を代入する。

［手順1-2-3］ 特徴点（i,j）の近傍にあり正の値をもつ画素の各々に
ついて，第２図に示した近傍位置を表わす値が小さい順
に次の処理を行う。注目近傍画素（i_K，j_k）が位置KSに
あるとき，特徴点テーブルのNS番目の位置KSの接続ベク
トルの値が「０」であるか否かを検査して，「０」であ
るならば手順1-2-3-1から手順1-2-3-6を行う。

［手順1-2-3-1］ 画素（i_K，j_k）から，端点と分岐点のいずれかである，
又は「３」以上の値をもつという条件（すなわち，特徴
点であるという条件）を満たす特徴点（r,s）が検出さ
れるまで，正の値をもつ画素を追跡する。追跡におい
て，注目画素から次の注目画素を検出する方法は，注目
画素の近傍にあり，かつ中心線上にある画素の中で，一
つ前の注目画素と異なる画素を次の注目画素にするとい
うものである。追跡された画素において，端点と分岐点
のいずれでもなく，かつその値が「１」であるもの（す
なわち，特徴点でないもの）を値「２」にする。

［手順1-2-3-2］ 手順1-2-3-1で得られた，二つの特徴点（i,j）と（r,
s）との間の画素列を直線近似して，第五図（ｃ）に示
すようにベクトルテーブルに登録し，登録されたベクト
ルの本数だけVNの値を増やす。

［手順1-2-3-3］ 特徴点（r,s）の値が「１」ならば,NNの値を「１」だけ
増やし，特徴点（r,s）の値をNNに置き換え，特徴点テ
ーブルのNN番目に特徴点（r,s）の座標を格納し，特徴
点テーブルのNN番目のすべての接続ブランチを「０」に
設定し，注目ブランチの終了特徴点番号NEにNNの値を代
入する。特徴点（r,s）の値が「１」でなければ,NEに特
徴点（r,s）の値を代入する。

［手順1-2-3-4］ BNの値を「１」だけ増やし，ブランチテーブルのBN番目
に，開始特徴点をNS,終了特徴点をNEとするブランチを
登録する。

［手順1-2-3-5］ 特徴点NSのKS番目の接続ブランチを注目ブランチBNにす
る。

［手順1-2-3-6］ 手順1-2-3-1において，特徴点（r,s）の一つ前に追跡さ
れた画素の特徴点（r,s）に対する位置KEを求め，特徴
点NEのKE番目の接続ブランチを注目ブランチBNにする。

第６図は，上記のベクトルデータに対して，ベクトルの
境界を追跡する原理を説明するための例を示している。
第６図（ａ）から（ｃ）は，開始特徴点と終了特徴点と
が等しいブランチが存在しない場合である。この場合，
以下のように追跡は実行される。

まず，第６図（ａ）のように，追跡を開始するブランチ
B1と特徴点N1からN2への追跡方向が与えられたとき，ブ
ランチB1を注目ブランチ，特徴点N2を注目特徴点とす
る。次に，ブランチB1を特徴点N1からN2へ，すなわち，
注目特徴点に入ってくる方向に追跡したとする。

次に，第６図（ｂ）に示すように，特徴点N2に接続する
ブランチを，特徴点N2にブランチB1が入ってきた近傍位
置から第２図に示した順に調べて，第２番目に検出され
るブランチB2を次の注目ブランチとする。ブランチB2の
特徴点の中で，特徴点N2と異なる特徴点N3を新たな注目
特徴点とする。

次に，ブランチB2を特徴点N2からN3へ追跡したとする。
以下同様にして，第６図（ｃ）のように追跡を進め，再
びブランチB1を特徴点N1から特徴点N2へ追跡しようとし
たとき１本の境界追跡を終了する。

第６図（ｄ）から（ｇ）は，開始特徴点と終了特徴点と
が等しいブランチB5が存在する場合である。この場合，
以下のように追跡は実行される。

まず，第６図（ｄ）のように，追跡を開始するブランチ
B4と特徴点N5からN6への追跡方向が与えられたとき，ブ
ランチB4を注目ブランチ，特徴点N6を注目特徴点とす
る。次に，ブランチB4を特徴点N5からN6へ追跡したとす
る。

次に，第６図（ｅ）に示すように，特徴点N6に接続する
ブランチを，特徴点N6にブランチB4が入ってきた近傍位
置から第２図に示した順に調べて，第２番目に検出され
るブランチB5を次の注目ブランチとする。ブランチB5の
開始特徴点と終了特徴点は等しいので，ブランチB5が検
出された位置から特徴点N6を出て，もうひとつの近傍位
置に入るようにブランチB5を追跡したとする。

次に，第６図（ｆ）に示すように，特徴点N6に接続する
ブランチを，特徴点N6にブランチB5が入ってきた近傍位
置から第２図に示した順に調べて，第２番目に検出され
るブランチB4を次の注目ブランチとする。ブランチB4の
特徴点の中で，特徴点N6と異なる特徴点N5を新たな注目
特徴点とする。

次に，ブランチB4を特徴点N6からN5へ追跡したとする。
同様にして，ブランチB4を特徴点N5から特徴点N6へ追跡
しようとしたとき，既にこの方向は追跡済みであるた
め,1本の境界追跡を終了する。

さらに，第６図（ｄ）の図形では，穴を形成する境界に
ついても，ブランチB5から同様に第６図（ｇ）のように
追跡される。

この原理を用いて１本の境界を抽出することは，以下の
手順2-1から手順2-7の手順を実行することにより実現さ
れる。結果は，ブランチとその追跡方向のリストとして
出力される。

［手順2-1］ 注目ブランチBCに追跡を開始するブランチBSを代入す
る。

［手順2-2］ 追跡を開始するブランチBSを正方向に追跡するならば，
手順2-2-1から手順2-2-2を実行して，追跡を開始するブ
ランチBSを逆方向に追跡するならば，手順2-2-3から手
順2-2-4を実行する。

［手順2-2-1］ 注目特徴点NCをBSの終了特徴点とする ［手順2-2-2］ ブランチBSの開始特徴点と終了特徴点とが等しいなら
ば,BSの終了特徴点の接続ブランチを近傍位置１から近
傍位置８まで順次調べて，最初にBSが現われる近傍位置
をKNとする。

［手順2-2-3］ 注目特徴点NCをBSの開始特徴点とする。

［手順2-2-4］ ブランチBSの開始特徴点と終了特徴点とが等しいなら
ば,BSの開始特徴点の接続ブランチを近傍位置１から近
傍位置８まで順次調べて,BSが２回目に現われる近傍位
置をKNに代入する。

［手順2-3］ 次の４つの場合に分ける。

（ｉ）ブランチBCの終了特徴点と開始特徴点とが異な
り，かつ特徴点NCがブランチBCの終了特徴点である。

（ii）ブランチBCの終了特徴点と開始特徴点とが異な
り，かつ特徴点NCがブランチBCの開始特徴点である （iii）ブランチBCの終了特徴点と開始特徴点とが等し
く，かつ特徴点NCの接続ブランチを近傍位置１から近傍
位置８に調べたとき，最初にBCが現われる近傍位置がKN
に等しい。

（iv）ブランチBCの終了特徴点と開始特徴点とが等し
く，かつ特徴点NCの接続ブランチを近傍位置１から近傍
位置８に調べたとき,BCが２回目に現われる近傍位置がK
Nに等しい。

上記（ｉ）と（iii）の場合には，ブランチBCの正方向
追跡済フラッグが真であるならば，処理を終了する。そ
うでなければ,BCと値“正方向”を出力して，ブランチB
Cの正方向追跡済フラッグを真にする（ii）と（iv）の
場合には，ブランチBCの逆方向追跡済フラッグが真であ
るならば，処理を終了する。そうでなければ,BCと値
“逆方向”を出力して，ブランチBCの逆方向追跡済フラ
ッグを真にする。

［手順2-4］ ブランチBCの終了特徴点と開始特徴点とが異なるなら
ば，特徴点NCの接続ブランチからBCを検出し，その近傍
位置をKCとする。その他の場合，特徴点NCの接続ブラン
チからBCを検出し，近傍位置KN＋１から近傍位置KN＋７
へ調べたとき，最初にBCが現われる近傍位置をKCとす
る。但し，近傍位置９から15は，それぞれ近傍位置１か
ら７に等しいとする。

［手順2-5］ 注目特徴点NCの接続ブランチを近傍位置KC＋１から近傍
位置KC＋８へ順次調べ，最初に検出されるブランチを新
たなBCにする。その近傍位置をKN（９以上のとき８を引
く）とする。但し，近傍位置９から16は，それぞれ近傍
位置１から８に等しいとする。

［手順2-6］ ブランチBCの開始特徴点と終了特徴点とが異なるなら
ば,NCに等しくない特徴点を新たなNCにする。

［手順2-7］ 手順2-3へ制御を移す。

上記の手順2-1から手順2-7を使って,1枚の画像に対する
ベクトルデータから全ての境界を追跡するためには，ま
ず，ブランチテーブルのすべての正方向追跡済フラッグ
とすべての逆方向追跡済フラッグを偽にする。そして，
ブランチテーブルを正順に調べて，正方向追跡済フラッ
グ又は逆方向追跡済フラッグが偽であるブランチBSを検
出したならば，追跡済みでない方向にブランチBSから１
本の境界の追跡を開始する。BSが両方向に未追跡なら
ば，まず,BSを正方向に追跡して１本の境界を追跡す
る。そして，その結果,BSの逆方向済フラッグが偽のま
まならば,BSを逆方向に追跡して１本の境界を追跡す
る。

なお，特徴点をベクトルの節点にする効果として，境界
追跡を開始するブランチBSを検出したとき，簡単に該ブ
ランチから追跡される境界が穴を形成する境界か否かを
判定できる。すなわち，ブランチBSの正方向追跡済フラ
ッグと逆方向追跡済フラッグが両方とも偽であるなら
ば，ブランチBSを正方向に追跡を開始して得られる境界
は，穴を形成していない境界であると判定できる。ま
た，ブランチBSの正方向追跡済フラッグが真であり，か
つ逆方向追跡済フラッグが偽であるならば，ブランチBS
を逆方向に追跡を開始して得られる境界は，穴を形成し
ている境界であると判定できる。

第１図は，本発明の一実施例を説明する図である。

第１図（ａ）において,100はCPUおよびメモリからなる
処理装置,3は画像メモリ部,4は細線化部,5はベクトル化
部,6はテーブルメモリ部,7は境界追跡部,8は境界メモリ
部,9は制御部である。

画像メモリ部３は，地図や図面などをディジタル画像と
して蓄積する部分で，第１図には記載されていない外部
からディジタル画像が供給される。細線化部４は，画像
メモリ部３に蓄積されているディジタル画像に含まれる
線図形を幅が「１」となる画素の中心線に変換して，中
心線上にある画素の値を「１」に，その他の画素の値を
「０」に変換した細線化画像を，画像メモリ部３に格納
する。細線化の方法については，いくつかの方法が知ら
れている（電子通信学会,PRL75−66など）が，それらの
いずれでもよい。

ベクトル化部５は，画像メモリ部３に蓄積されている細
線化画像を第５図に示したベクトルデータに変換して，
テーブルメモリ部６に出力する部分である。テーブルメ
モリ部６は，第５図に示したベクトルデータを蓄積する
部分である。テーブルメモリ部６は，第１図には記載さ
れていない外部へベクトルデータを供給することも行
う。

境界追跡部７は，テーブルメモリ部６に蓄積されている
ベクトルデータを用いて，中心線の境界を追跡し，各境
界を追跡順に並べられたブランチ列と，それらの追跡方
向として，境界メモリ部８に書き込む。境界メモリ部８
は，各境界をブランチ列と，それらの追跡方向として蓄
積する部分である。境界メモリ部８は，第１図には記載
されていない外部へ境界を供給することも行う。外部で
は，境界メモリ部８から供給されるブランチ列と，それ
らの追跡方向と，テーブルメモリ部６から供給される各
ブランチを構成するベクトルとから，境界を構成するベ
クトル列，境界を構成するブランチ列などの応用に応じ
た情報を受け取ることができる。

制御部９は，画像メモリ部３に蓄積されている線図形イ
メージデータを，中心線イメージデータに変換し，中心
線イメージデータをベクトルデータに変換して，ベクト
ルデータの全境界を追跡するように全体を制御する部分
である。これらの動作は，以下のとおりである。

まず，制御部９の指示により，細線化部４は，画像メモ
リ部３に蓄積されている線図形を細線化画像に変換し
て，画像メモリ部３に格納する。次に，制御部９の指示
により，ベクトル化部５は，画像メモリ部３に蓄積され
ている細線化画像に対して上記手順1-1から手順1-2を実
行して，第５図に示したベクトルデータに変換して，テ
ーブルメモリ部６に格納する。最後に，制御部９の指示
により，境界追跡部７は，テーブルメモリ部６に蓄積さ
れているベクトルデータより手順2-1から手順2-7を用い
て全境界を追跡して，各境界に対してブランチ列と，そ
れらの追跡方向とを境界メモリ部８に格納する。

第１図（ｂ）は，第１図（ａ）に示されているベクトル
化部５をさらに説明するための図である。51は画像走査
部,52は画素追跡部,53は特徴点登録部,54はブランチ登
録部,55は直線近似部,56は接続関係登録部,57は接続関
係参照部,58はベクトル化制御部である。

画像走査部51は，画像メモリ部３に蓄積されている細線
化画像を，ベクトル化制御部58から与えられた座標から
TV式にラスタ走査して，走査された画素（i,j）が孤立
点と端点と分岐点のいずれかである又は値が「１」であ
るという（すなわち，特徴点であるという）条件を満た
すとき，画素（i,j）の近傍から正の値をもつ画素をす
べて抽出して，それらの近傍画素の座標と画素（i,j）
の座標とを，ベクトル化制御部58に出力する。

画素追跡部52は，画像メモリ部３に蓄積されている細線
化画像において，与えられた座標の画素から，手順1-2-
3-1を実行して，追跡された画素列の座標列を出力す
る。

特徴点登録部53は，検出済みの特徴点の最大番号NNと画
素（i,j）の座標とを，ベクトル化制御部58から入力
し，更新されたNNと画素（i,j）の特徴点番号を出力す
る。特徴点登録部53は，まず，画像メモリ部３に蓄積さ
れている細線化画像から画素（i,j）の値を求める。次
に，画素（i,j）の値が「１」ならば,NNの値を「１」だ
け増やし,NNに代入してベクトル化制御部58に出力し，
細線化画像上の画素（i,j）の値をNNに置き換え，テー
ブルメモリ部６に蓄積されている特徴点テーブルのNN番
目に，画素（i,j）の座標を格納し，特徴点テーブルのN
N番目のすべての接続ブランチを「０」に設定し,NNの値
を画素（i,j）の特徴点番号として，ベクトル化制御部5
8に出力する。画素（i,j）の値が「１」でなければ，画
素（i,j）の値を画素（i,j）の特徴点番号として，ベク
トル化制御部58に出力する。

ブランチ登録部54は，ベクトル化制御部58からブランチ
の開始特徴点番号NS,終了特徴点番号NE,検出済みのブラ
ンチの最大番号BNを与えられ，手順1-2-3-4を実行し，
更新されたBNの値をベクトル化制御部58に出力する。

直線近似部55に対しては，画素列の座標列と検出済みの
ベクトルの最大番号VNがベクトル化制御部58から与えら
れ，手順1-2-3-2を実行して，更新されたVNをベクトル
化制御部58に出力する。直線近似の方法は，いくつかの
方法が知られている（例えば，昭和59年度電子通信学会
総合全国大会1252など）が，それらのいずれでもよい。

接続関係登録部56は，ベクトル化制御部58から特徴点番
号，接続ブランチの位置，ブランチ番号を入力し，テー
ブルメモリ部６に蓄積されている特徴点テーブルの該特
徴点の該位置の接続ブランチに，該ブランチ番号を代入
する。

接続関係参照部57は，ベクトル化制御部58から特徴点番
号と接続ブランチの位置を入力し，テーブルメモリ部６
に蓄積されている特徴点テーブルの該特徴点の該位置の
接続ブランチの値が「０」であるか否かを，ベクトル化
制御部58に出力する。

ベクトル化制御部58は，検出済みの特徴点の最大番号N
N,検出済みのブランチの最大番号BN,検出済みのベクト
ルの最大番号VN,注目ブランチBNの開始特徴点番号NS,注
目ブランチBNの終了特徴点番号NE,開始特徴点NSにおけ
る注目ブランチBNの接続位置KS,終了特徴点番号NEにお
ける注目ブランチBNの接続位置KEを記憶し，画像メモリ
部３に蓄積されている細線化画像をベクトルデータに変
換して，テーブルメモリ部６に格納するように全体を制
御する。

ベクトル化制御部58は，手順1-1から手順1-2に従い，各
部を以下のように動作させる。まず，ベクトル化制御部
58は手順1-1を実行する。次に，ベクトル化制御部58
は，画像走査部51に細線化画像の左上角の画素の座標を
与え，孤立点と端点と分岐点のいずれかである又は値が
「１」である画素を（i,j）とし，画素（i,j）の近傍に
ありかつ正の値を持つ画素を得る。そして，手順1-2-1
から手順1-2-3を実行させる。これらの処理が終了した
とき,TV式のラスタ走査順において画素（i,j）の次に走
査される画素を画像走査部51に与え，孤立点と端点と分
岐点のいずれかである又は値が「１」である画素を（i,
j）とし，画素（i,j）の近傍にありかつ正の値をもつ画
素を得る。そして，手順1-2-1から手順1-2-3を実行させ
る。以下同様にして処理を進め，ラスタ走査が１回終了
したとき，すべての処理を終了する。

手順1-2-1から手順1-2-3は，ベクトル化制御部58によ
り，以下のように制御される。まず，画素（i,j）の近
傍に正の値を持つ近傍画素が存在しないならば（すなわ
ち，孤立点ならば），画素（i,j）の座標と検出済みの
特徴点の最大番号NNを特徴点登録部53に与え，ラスタ走
査に戻ることにより，手順1-2-1を実行させる。正の値
を持つ近傍画素が存在するならば，手順1-2-2に進み，
画素（i,j）に座標と検出済みの特徴点の最大番号NNを
特徴点登録部53に与え，画素（i,j）の特徴点番号を得
て，注目ブランチの開始特徴点番号NSに代入する。次
に，画素（i,j）の近傍にあり正の値を持つ近傍の各々
について，第２図に示した近傍位置を表わす値が小さい
ものから順に，画素（i,j）に対する第２図に示す位置K
Sと画素（i,j）の特徴点番号NSとを，接続関係参照部57
に与える。そして，特徴点テーブルのNS番目の位置KSの
接続ブランチの値が「０」であるという出力を得たもの
について，手順1-2-3-1から手順1-2-3-6を実行する。

手順1-2-3-1から手順1-2-3-6は，ベクトル化制御部58に
より以下のように制御される。画素（i,j）の近傍にあ
り正の値を持つ注目画素を（i_K，j_K）とする。まず，画
素（i_K，j_K）の座標を画素追跡部52に与え，手順1-2-3-
1を実行させて，画素列の座標列を得る。次に，検出済
みのベクトルの最大番号VNと手順1-2-3-1で得られた画
素列の座標列とを直線近似部55に与え，手順1-2-3-2を
実行させて，更新されたVNを得る。次に，手順1-2-3-1
において最後に追跡された画素（r,s）の座標と検出済
みの特徴点の最大番号NNとを特徴点登録部53に与え，手
順1-2-3-3を実行させて，画素（r,s）の特徴点番号を得
て，注目ブランチの終了特徴点番号NEに代入する。次
に，検出済みのブランチの最大番号BN,特徴点番号NS,特
徴点番号NEをブランチ登録部54に与え，手順1-2-3-4を
実行させ，新しいBNの値を得て，注目ブランチ番号とす
る。次に，特徴点番号NS,接続位置KS,ブランチ番号BNを
接続関係登録部56に与え，手順1-2-3-5を実行させる。
最後に，画素（r,s）の一つ前に追跡された画素の画素
（r,s）に対する近傍位置を接続位置KEに代入し，特徴
点番号NE,接続位置KE,ブランチ番号BNを接続関係登録部
56に与え，手順1-2-3-6を実行させる。

第１図（ｃ）は，第１図（ａ）に示されている境界追跡
部７をさらに説明するための図である。71はフラッグ初
期設定部,72はブランチ検出部,73は追跡初期設定部,74
はフラッグ設定部,75は追跡済近傍位置設定部,76は注目
ブランチ設定部,77は注目特徴点設定部,78は境界追跡制
御部である。

フラッグ初期設定部71は，テーブルメモリ部６に蓄積さ
れているブランチテーブルのすべてのブランチの正方向
追跡済フラッグと逆方向追跡済フラッグとを偽にする。
ブランチ検出部72は，境界追跡制御部78より与えられる
ブランチ番号から正順に，テーブルメモリ部６に蓄積さ
れているブランチテーブルを調べ，正方向追跡済フラッ
グ又は逆方向追跡済フラッグが偽であるブランチBSを検
出したならば，ブランチBSとその偽である方向を出力す
る。但し，正方向と逆方向が共に偽であるならば，正方
向を境界追跡制御部78に出力する。

追跡初期設定部73は，境界追跡制御部78から，追跡を開
始するブランチBSとその追跡方向を与えられ，テーブル
メモリ部６に蓄積されているベクトルデータを参照し
て，手順2-1と手順2-2を順次実行し，注目ブランチBC,
注目特徴点NC,ブランチBCが，特徴点NCより出ていく近
傍位置KNを境界追跡制御部78に出力する。

フラッグ設定部74は，注目ブランチBC,注目特徴点NC,ブ
ランチBCが，特徴点NCから出ていく近傍位置KNを，境界
追跡制御部78から与え，テーブルメモリ部６に蓄積され
ているベクトルデータに対して参照及び書き込みを行な
い，手順2-3を実行し，追跡されたブランチBCと，その
追跡方向と,1本の境界追跡が終了したか否かとを境界追
跡制御部78に出力する。

追跡済近傍位置設定部75は，境界追跡制御部78から注目
ブランチBC,注目特徴点NC,ブランチBCが，特徴点NCより
出ていく近傍位置KNを，境界追跡制御部78から与えら
れ，テーブルメモリ部６に蓄積されているベクトルデー
タを参照して，手順2-4を実行し，注目ブランチBCが注
目特徴点NCに入ってくる近傍位置KCを，境界追跡制御部
78に出力する。注目ブランチ設定部76は，注目特徴点NC
と，注目ブランチBCが特徴点NCに入ってくる近傍位置KC
を，境界追跡制御部78から与え，テーブルメモリ部６に
蓄積されているベクトルデータを参照して，手順2-5を
実行し，新たな注目ブランチBCとし，ブランチBCが特徴
点NCから出ていく近傍位置をKNに代入して，境界追跡制
御部78に出力する。

注目特徴点設定部77は，注目ブランチBCと注目特徴点NC
を境界追跡制御部78から与え，テーブルメモリ部６に蓄
積されているベクトルデータを参照して，手順2-6を実
行し，新たな注目特徴点NCとして境界追跡制御部78に出
力する。

境界追跡制御部78は,1本の境界のブランチ列，それらの
ブランチの追跡方向，追跡を開始したブランチBS,ブラ
ンチBSの追跡方向，注目ブランチBC,注目特徴点NC,ブラ
ンチBCが特徴点NCから出ていく近傍位置KN,ブランチBC
が特徴点NCに入ってくる近傍位置KCを記憶し，テーブル
メモリ部６に蓄積されているベクトルデータから全ての
境界を追跡して，各境界をブランチ列とそれらの追跡方
向として，境界メモリ部８に出力するように，全体を以
下のように制御する。

まず，フラッグ初期設定部71を動作させる。次に,BSを
値「３」に設定し，ブランチ検出部72を動作させ，追跡
を開始するBSとその追跡方向とを得る。次に,BSとその
追跡方向を追跡初期設定部73に与え，注目特徴点NC,注
目ブランチBC,ブランチBCが特徴点NCから出ていく近傍
位置KNを得る。次に，フラッグ設定部74,追跡済近傍位
置設定部75,注目ブランチ設定部76,注目特徴点設定部77
を順次動作させ，注目ブランチBC,注目特徴点NC,ブラン
チBCが特徴点NCから出ていく近傍位置KN,ブランチが特
徴点NCに入ってくる近傍位置KCを更新しながら，フラッ
グ設定部74から追跡されたブランチBCとその追跡方向と
を得ることを反復する。

反復の終了は，フラッグ設定部74から１本の境界追跡の
終了が通知されたときである。次に，得られたブランチ
列とそれらの追跡方向を１本の境界として境界メモリ部
８に出力する。以下同様に，ブランチ検出部72にBSを与
え，新たなBSとその追跡方向を得るたびに，上記の１本
の境界追跡を実行して，ブランチ検出部72から追跡でき
るブランチがないことが通知されたとき処理を終了す
る。

〔効果の説明〕 以上説明したように，本発明によれば，ベクトル化の際
に特徴点に接続するブランチを簡単な処理によって求め
ておくことにより、線図形の中心線画像に関するベクト
ルデータ上において境界を追跡することが可能になり，
しかも効率良く実行できるようになる。

【図面の簡単な説明】

第１図は本発明の一実施例を説明する図，第２図は近傍
画素の位置の定義を示す図，第３図はベクトルデータの
特徴点を説明する図，第４図及び第５図はベクトルデー
タの構造を示す図，第６図はベクトルの境界を追跡する
原理を例により説明する図である。 １……線図形の中心線,2……背景,3……画像メモリ部,4
……細線化部,5……ベクトル化部,6……テーブルメモリ
部,7……境界追跡部,8……境界メモリ部,9……制御部,5
1……画像走査部,52……画素追跡部,53……特徴点登録
部,54……ブランチ登録部,55……直線近似部,56……接
続関係登録部,57……接続関係参照部,58……ベクトル化
制御部,71……フラッグ初期設定部,72……ブランチ検出
部,73……追跡初期設定部,74……フラッグ設定部,75…
…追跡済近傍位置設定部,76……注目ブランチ設定部,77
……注目特徴点設定部,78……境界追跡制御部,100……
処理装置。

Claims (1)

【特許請求の範囲】
1. 【請求項１】中央処理装置とメモリとを備え，線画情報
   から閉領域を自動抽出する処理システムにおけるベクト
   ルデータ境界追跡処理方式であって， （Ａ）二値線図形データを細線化して得られる中心線イ
   メージデータを， （A1）中心線上にある画素の中から，近傍画素が全て背
   景上にある画素である孤立点，近傍画素の一つだけが線
   図形の中心線上にある画素である端点，近傍画素の三つ
   以上が線図形の中心線上にある画素である分岐点に加え
   て，上記孤立点と上記端点と上記分岐点のいずれも含ま
   ない連結成分である孤立ループに属する画素の中でラス
   タ走査により最初に検出される画素，及び上記端点か上
   記分岐点のいずれかである二つの特徴点を結ぶ中心線の
   画素列に属する画素の中でラスタ走査により最初に検出
   される画素の少なくとも五種類の画素を特徴点とし，該
   特徴点をベクトルの節点として扱う手段と， （A2）二つの上記特徴点を結ぶ中心線の画素列を直線近
   似してベクトル列に変換し，そのベクトル列を処理単位
   のブランチとして，その一方の特徴点を開始特徴点，他
   方の特徴点を終了特徴点としてベクトルデータの一部と
   して記憶する手段と， （A3）上記特徴点の各々について，線図形上にある近傍
   画素の位置と近傍画素が属するブランチの識別番号をベ
   クトルデータの一部として記憶する手段と を有し，ベクトルデータに変換するベクトル化部を備
   え， （Ｂ）かつ上記変換によって得られたベクトルデータに
   対して， （B1）開始特徴点と終了特徴点とが異なるブランチ及び
   開始特徴点と終了特徴点とが等しいブランチに対して定
   められた方向の正方向および逆方向に関する追跡履歴を
   示す正方向追跡済フラッグ及び逆方向追跡済フラッグの
   状態を記憶する手段と， （B2）上記正方向追跡済フラッグが偽であるブランチを
   正方向に追跡し，該正方向追跡済フラッグを真に設定す
   る手段と， （B3）上記逆方向追跡済フラッグが偽であるブランチを
   逆方向に追跡し，該逆方向追跡済フラッグを真に設定す
   る手段と， （B4）注目ブランチが正方向に追跡されたならば，該注
   目ブランチの終了特徴点の近傍を，該注目ブランチを正
   方向に追跡したとき当該終了特徴点に入ってくる位置か
   ら反時計回り又は時計回りに検査して第２番目に検出さ
   れるブランチを新たな注目ブランチとし，該第２の注目
   ブランチの追跡方向を当該終了特徴点から検出された位
   置へ出る方向にして追跡を行う手段と， （B5）注目ブランチが逆方向に追跡されたならば，該注
   目ブランチの開始特徴点の近傍を，該注目ブランチを逆
   方向に追跡したとき当該開始特徴点に入ってくる位置か
   ら反時計回り又は時計回りに検査して第２番目に検出さ
   れるブランチを新たな注目ブランチとし，該第２の注目
   ブランチの追跡方向を当該開始特徴点から検出された位
   置へ出る方向にして追跡を行う手段と， （B6）注目ブランチの上記正方向追跡済フラッグ及び上
   記逆方向追跡済フラッグの中で，その一つ前に追跡され
   たブランチの追跡方向から決まる方向のフラッグが偽で
   あるならば、追跡を終了する制御手段と を有し，境界を追跡する境界追跡部を備えたことを特徴
   とするベクトルデータ境界追跡処理方式。