JPS62143192A - 線図形処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、線図形処理装置、特に、図面等、線図形を主
体とし、かつ該線図形に文字、記号等の微細図形が該線
図形の直線部または屈曲点部において接触・交差してい
る二値画像から、該線図形を精度よく忠実に抽出し、こ
れをして地理データペースにおける地形図・住宅図の自
動入力、あるいは図面デー・タペースにおける各種図面
の自動入力等を効率よく行なわしめる線図形処理装置に
関するものである。

〔従来の技術〕

従来のこの種の装置を実現する方式としては、（イ）画
像データを画像メモリ上で細線化して得られる黒画素列
を直線近似する方式、 （ロ）線図形を境界線が平行な細長い黒画素領域とみな
し、該境界線対を用いて線図形を追跡・抽出する方式、 （ハ）図形の境界線追跡と境界線に沿った距離情報によ
り境界線の包囲関係と外接長方形を求め、線図形を抽出
する方式、 に）黒画素領域を追跡しながら追跡方向上で直線的に連
続する黒画素領域の長さおよび該追跡方向の直角方向の
黒画素数を求めることにより直線図形を抽出する方式、 等が発表されている。

この内、（イ）は画像メモリ上で画像データの構成要素
である各図形データに対し、細線化処理を施しているが
、このため交点の変化やヒゲの発生によって画質が劣化
し、線幅情報や面情報が欠如するため、線図形と微細図
形との区別がつかなくなシ、線図形全原画像に忠実に抽
出するには適していない。

これに対して（ロ）、（ハ）およびに）の各方式は細線
化処理を施さない方式であるが、この中で、（ロ）は境
界線追跡のみに基づいているため、線図形と微細図形を
分離することはできない。したがって、微細図形が線図
形に接触・交差しているような画像から線図形を抽出す
るには適していない。

（ハ）の方式は距離情報を用いているため、微細図形が
線図形に接触しているような場合には対処できる。しか
し、この場合も微細図形が線図形に交差しているような
場合には対処できない。

これに対して、に）の方式は図形を表わす黒画素領域上
に直線を当てはめているので、ｇ４ｔ１図形が線図形に
接触・交差している場合にも対処できるが、ただし、そ
れは微細図形が線図形の直線部において接触・交差して
いる場合のみであって、屈曲点部で接触・交差している
場合には抽出不可能となる。

さらに、一般の画像データにおいては比較的小さい同じ
一つの図形が例えば図面の種類によシ線図形として現れ
たり、微細図形として現れたシすることがしばしば生じ
、これに対処するためには図形のもつ意味内容を考慮し
た高次の処理が必要となる。しかしながら、上記の各方
式はいずれもそのままではこの問題に対処することはで
きない。

〔発明の目的〕

一般に、与えられた二値画像から線図形を抽出する場合
の条件（以下では抽出処理条件と呼ぶ）として、 （ａ）　　原画像に忠実に線図形が抽出できること、（
ｂ）　　ｅ線図形が線図形の直線部および屈曲点部のど
ちらにおいて接触・交差していても抽出処理が可能なこ
と、 （ｃ）原画像から線図形を抽出・分離した後の残された
微細図形はその形状が損なわれないこと１ （ｄ）　　必要に応じて図形要素がもつ意味内容に基づ
く高次の処理に対処できること、 を挙げることができる。上記の方式はこれらの抽出処理
条件を全て満たすようなものでないため、適用領域に自
ずと限界が生ずる。

本発明は、これらの条件を全て満たすことを目的として
いるが、具体的には、与えられた二値画像データの中の
各図形要素を、該図形要素に内接しかつ互いに隣接する
最大の正方形（最大正方形と呼ぶ、また、以下では単に
正方形と呼ぶこともある）の正方形データ列（チェイン
と呼ぶ）と、チェイ／とチェインとを連結しかつ該図形
に内接する最大正方形（コネクタと呼ぶ）とで構成され
る構造体として表現することにより、該二値画像データ
を一つの図形ファイルとしてファイル化し、これに基づ
いて図形のデータ記述を行ない、さらにこのデータ記述
上を直線追跡処理を施すことにより、上記難点を解決す
ることを目的としている。

なお、図形のチェインとコネクタを該図形の心線と総称
する。したがうて、該図形ファイルは図形の心線講造体
とみなすことができる。すなわち、該図形ファイルは、
原画像データの幾何学的構造をチェインとコネクタとの
連結関係として表現しており、チェインデータは線図形
の各場所での線幅を、あるいは微細図形の面の情報を正
方形の辺の長さく辺長と呼ぶ）としてもっており、しか
も原画像を完全に再現するため、上記（ａ）〜（ｄ）の
それぞれの抽出処理条件を満たすような方式を構成する
のに容易に対処することができる。

〔実施例〕

第７図に本発明に係わる装置構成の実施例を示す。図面
等の与えられた二値画像データ／は図形ファイル操作部
３により予め図形の心線構造を記述した図形７フイルコ
としてファイル化され、以下、線図形抽出に係わる処理
はこの図形ファイルからチェインデータを順次読み出し
ながら処理されていくが、ここでは、先ず、処理の全体
的流れの眼要を述べておく。チェインデータ選択・読み
出し部≠により図形ファイル操作部３全介して固形ファ
イルコから取シ込まれたチェインデータは一旦チェイン
データ蓄積部よに蓄積された後、太さ分割処理部６によ
り／−）またはそれ以上の部分チェインデータに分割さ
れ、その分割点の正方形アドレス（チェインを構成する
各正方形は隣接関係に従ってｌ、２．・・・の順にアド
レスが付けられている）が正方形アドレス蓄積部７に蓄
積される。

蓄積部７上の分割点正方形アドレスおよびチェインデー
タ蓄積部！上のチェインデータで定まる部分チェイン（
分割部分チェイン）は折れ線近似処理部どにより折れ線
近似され、その屈曲点正方形アドレスが７と同じ構成の
正方形アドレス蓄積部／２に蓄積される。次いで、該各
分割部分チェインはその屈曲点正方形アドレスおよびそ
れに係わるコネクタとともに心線構造記述処理部１３に
より心線構造記述テーブル／ｌ’上に記述・登録される
。図形フフイルコ上のチェインデータの全てに対してこ
れらの一連の処理が終了すると、直線追跡処理部ｌ！が
起動し、心線構造記述テーブルｌ≠上の心線データを直
線追跡し、テーブル上で直線部分の抽出を行なう。この
処理が終了すると、線図形出力処理部／６が起動し、核
テーブル上の直線データ全探索し、必要に応じてファッ
クス出力装置あるいは図形表示装置等へ該直線データを
出力する。

以下、各処理部の機能についてその概要と実現法を説明
していく。

（７）図形ファイル操作部　一本操作部は、ディジタイ
ズされた二値図形の心線構造抽出法として提案されたＭ
ＵＭ法（Ｗａｋａｙａｍａ＋　Ｔ＋　’　Ｃｏｒｅ−Ｌ
ｉｎｅ　　Ｔｒａｃｉｎｇ　　人１ｇｏｒｉｔｈｍ　　
Ｂａ５ｅｄ　　ｏｎ　　ＭａｘｉｍａｌＳｑｕａｒｅＭ
ｏｖｉｎｇ＋　’　ＩＩＪＢ　Ｔｒａｎｓ、　ＰＡＭＩ
＋　Ｖｏｌ、　ＰＡＭＩ−＠、Ａ／（／９’ｆ２））　
で得られる心ｍｆ−タの表現形式を用いて、二値画像を
一つのファイル（図形ファイル）としてフフイル化し、
必要に応じてファイルから図形データを検索する。第２
図に心線データの抽出例を示す。

第２図ではＹ軸は下向きに取っである（以下同様）、ｉ
、２′Ａ中、・は図形に内接する最大正方形（の中心点
）を表わし、その連結は図形の心線を表わす。図形ファ
イルのデータ構成を＠３図に示す。第３図で（ａ）は第
２図の心タ一部分（・は最大正方形）を表わしている。

図形の心線において隣り合う２つの最大正方形は互いに
ＭＳＭ隣接すると言う。第３図のように心線は、その分
岐点の幾何学的形状によりチェインと呼ばれる互いにＭ
ＳＭ隣接した最大正方形の順序列（０／、０．２等）と
、チェインとチェインを連結するＪ／、Ｊ２等の最大正
方形（これをコネクタと呼ぶ）に分解することができる
０図形ファイルでの心線データは同図（ｂ）に示すよう
にチェインとコネクタとの間の連結関係によって線形表
現される。この場合、ファイル内での各チェインおよび
コネクタは該ファイル上でアドレス（チェインアドレス
、コネクタアドレス）が付けられ、これらのデータはそ
のアドレスを与えることによって読み出される。なお、
本図形ファイル操作部は１文献［着出、”ＭＳＭ心線デ
ータを用いた図形操作、′　情処学会研資、０Ｖ２７−
．２（／り１３）Ｊに示す方法を応用して実現される。

（イ）　チェインデータ選択・読み出し部　−本処理部
は上記（７）項記載の図形ファイル内のデータをチェイ
ンアドレスを与えることによりファイルの先頭から１′
、Ａ次読み出していくが、最初は、初期設定信号により
チェインアドレスを初期設定し、最初のチェインデータ
をトヱみ出す。その後は心線構造記述処理部／３・つ）
多丁信号を受は取ることによりチェインアドレスを進め
、そのアドレスでチェインデータを読み出す。読み出さ
れたデータはチェインデータ蓄積部ｊに蓄積される。

一般１・こチェインＯは、その定義から、互いにＭ　Ｓ
　Ｍ隣接する最大正方形Ｓｉ　（ｉ＝／、　２．・・・
。

口）の列 ０＝ＣＳ／、　Ｓｊ、　・＝、　Ｓｎ　］　　　　　（
１）として表現することができる、１ここで、ｎをチェ
イン０の長さ、ｉ　ｆ　Ｏにおける正方形Ｓ１のアドレ
ス（正方形アドレス）と呼ぶ。また、０を構成する正方
形Ｓｉは Ｓｉ＝［（ｘｉ、　ｙｉ）、　Ａｔ　〕（ｉｆ）（ｘｉ
、ｙｉ）：正方形の左上頂点座標ｔｉ：正方形の辺長（
＝０．へコ・・・）と記述することができる。このとき
、考えられるチェインの長さの最大値をＭとするならば
、チェインデータ蓄積部まはそれぞれがｘｉ＋　ｙＬ　
ｔｉを蓄積する長さＭのＦＩＦＯ型のレジヌタｊ−／、
ターλ・ｊ−３の３本で構成されることとなる。

（つ）太さ分割処理部　−本処理部はチェインデータ蓄
積部ｊに蓄積されているチェインをその太さによって細
い部分と太い部分に分割する。

いま、チェインＣ上の正方形アドレス１に対する辺長１
４の数列を Ｌ（４＝　ＣＬ／　、　ｔｉ、・・・、ム〕０１ｉ）と
し、これをチェインＣの辺長数列と呼ぶものとする。辺
長数列はＯの線幅を与えるものである。このとき、第４
図（ａ）に示す線図形〔１つのチェインＣとして表現さ
れているとする〕に対して、横軸に正方形アドレスを、
縦軸に辺長をと９、その辺長数列をプロットすれば、第
≠図（ｂ）のようになろう。０を辺長数列により細い部
分と太い部分に分割するならば、その分割点はアドレス
ａｊ＋　ａ４’＋　ａｊおよびａ６で示される正方形（
の中心）が妥当である　このようにチェインをその辺長
数列によって１つまたはそれ以上のチェインに分割する
ことをチェインを太さ分割すると言う。

したがって、本分割処理部はチェイン蓄積部ｊ内の辺長
数列レジスタｊ−３から順次ＰＩＦＯ形式で値を読み出
しながら、１つ前のデータと値を比較し、下に述べる本
処理部の実施例の方法で分割点が見つかればその正方形
アドレスを出力し、正方形アドレス蓄積部７（ＦＩＦＯ
型レジスし〕に蓄積していくものである。本処理部は処
理部弘からの読み出し終了信号の受信によって起動がか
かる。

本処理部の実施例を第５図に示す。コントローラ６−／
は、辺長数列レジスタｊ−３から正方形辺長の値を順次
読み出すためのアドレスレジスタ６−２を初期設定し、
以降は後述の処理回路６−７乙〜６−コｌの終了信号を
受信することにより／づつ増加する。さらにレジスタ６
−２の内容’１ＦＩＦ’ｏ型レジスタター３に送り、そ
れで指定される正方形辺長値をレジスタ６−３に読み出
す。四辺要領は遅延回路ｇ−＋の保持するｌ動作前の辺
長値と差分が取られ、差分レジスタ乙−夕に出される。

同差分値、および遅延回路乙−７で保持されるｌ動作前
の差分値は判定回路を一タおよびｔ−ｉｏによりそれぞ
れ正・Ｏ・負の値が判定され、それぞれの組合せにより
処理回路６−／ｊ−Ａ−λ／が起動する。これに係わる
レジスタとしてｔ−１ｔ−ｔ−ｔ≠が用意されている。

レジスタｔ−／／は辺長数列レジスタター３における辺
長値の変化点（アドレス）をもつレジスタである。レジ
スタ６−１２は同じ値の辺長が連続した場合の個数を数
えるカウンタである。レジスタ６−１３はレジスタ６−
１２の内容と比較の対象となる定数を、およびレジスタ
６−／≠は、ｌ動作前の辺長値乙−６と必要に応じてＪ
′−３から読み出された辺長値との差の絶対値と比較の
対象となる定数をそれぞれ保持するものである。処理回
路Ａ　−／！はレジスタ６−１２の内容をｌだけ増加さ
せる、処理回路６−７６はレジスタ６−／λをリセット
（値／に）する。処理回路６−１７はレジスタ６−７２
と６−１３との内容を比較し、前者が犬ならばレジスタ
乙−２の内容をレジスタ６−ｌ／に転送する。

しかる後にレジスタ乙−／！ヲリセントする。

処Ｊ＋（！回路＆−／♂は、レジスタ乙−／／　の内容
全アドレスとして読み吊したレジスタｒ−３の値とｌ動
作前の辺長値乙−６との差の絶対値を求め、同絶対値が
レジスタＡ−／≠内の値以下ならばレジスタ！、−３の
内容をレジスタ６−　／／に転送する。そうでないなら
ば、レジスタ６−１２と６−１３とを比較し、前者が犬
ならばレジスタ乙−２の内容から６−７２の内容を減じ
たものを、後者が犬ならばレジスタ６−２の内容を、太
さ分割点正方形アドレスとし、正方形アドレス蓄積部７
に転送する。同様にして処理回路乙−／り〜ｚ−−／は
これらのレジスタ間で値の比較や転送を行ない、辺長値
の変化点アドレスは必要に応じて正方形アドレス蓄積部
７に出力される。

に）折れ線近似処理部　−本処理部はチェイン中心ｆｆ
ＩＡ算出部りと折れ線近似部／／全その下位処理部とし
て含む。太さ分割処理部乙により分割された個々の部分
チェイン（以下では単にチェインと呼ぶ）の中心線を中
心線算出部りで算出し、その中心点列を座標点列でｌ積
部ｌＯに蓄積する１次いで、核中心心データを処〕ノ１
１部／／で折れ線近似し、その屈曲点に対応する正方形
アドレスを正方斤５アドレス堤績部／−に蓄積する。

いま、上記（＋）および（１１）の式で表記されるチェ
イン０に対して、Ｃ上の正方形Ｓｉの中心点Ｐｉ １’ｉ　＝　（ｘｉ　＋ｔｉ／２　、　　ｙｉ　＋　ｌ
ｉ／、り　　　ＩＩＶ）の列Ｌ　（０） Ｌ（０）＝　Ｃ）’／、　Ｐコ、　・・、　Ｐｎ　）　
　　　Ｍを考え、これをチェインＣの中心線と呼ぶ。

また、チェインＣの中心線（ｖ）に対して、点Ｑｉ（ｉ
＝／、コ、・・・、ｎ−ｌ）をコ点ＰｉとＰｉ十／の中
間点とするとき、点列 Ｌ’（０）＝　ＣＱ／、　Ｃ２，−、Ｑｍ〕＆０を曲線
Ｌ（０）の平滑化曲線と呼ぶ。

チェイン０の中心線Ｌ（０）を平滑化し、それを通常の
手法、こより近れ線近似し、両端を含めたその屈曲点の
正方形アドレスｔａＯ（＝／）。

ａ／＋　−＋　ａｋ　（＝ｎ　）　（ｋは近似線分の数
）としたときくｗＪｌ、図）、これをチェインＣの折れ
線近似と呼ぶ。第７図（ａ）の場合、太さ分割された部
分チェインの一つＣｌは屈曲点アドレスｆ　ａｏ（＝／
Ｌ　ａ／＋　ａｊ＋　ａＪ＋　ａ≠（＝ｎ／）とする折
れ線近似として表現される。

第７図に折れ線近似処理部の実施例を示す。

正方形アドレス蓄積部７上の隣り合うアドレス対を７か
ら読み出し、その区間内の正方形データをチェインデー
タ蓄積部！より順次読み出し、それぞれの正方形データ
ｆｘレジスタター／％　　ｙレジスタター２、ｔレジス
タター３に格納する。これらのデータからは中心点算出
回路により正方形の中心点が求められ、レジスタター！
に格納される。次いで該中心点データと遅延回路ター２
の保持する／動作前の中心点データは平均化回路ターフ
により平均されて両者の中間点が座標点列蓄積部１０に
格納される。！、内の対応する全ての正方形が処理され
ると　１０内の点列データは折れ線近似回路／／によシ
折れ線近似され、その屈曲点正方形アドレスが正方形ア
ドレス蓄積部／２に格納される。回路／／は具体的には
・点列の両端点でできる直線と点列上の他の点との間の
距離を用いることにより、容易に実現できる・ （イ）心線構造記述処理部　一本処理部は図形ファイル
上の心線構造データを各心線の連結関係、折れ線近似処
理による屈曲点正方形アドレス、チェインの太さの平均
値等により一つのテーブル（心線構造記述テーブルと呼
ぶ）として表現するものである。

いま、第に図（ａ）に示す図形を考える。これは図形フ
ァイル２上ではＯ／、０２．−自　Ｃｌの６つのチェイ
ンとＪ／およびＪ、２の一つのコネクタで構成されてい
る。ここで、個々のチェインを太さ分割すると例えばチ
ェインＣ／ばＣｌ／、Ｏ／、２およびＣ１３の３つの部
分チェインに太さ分割され、その他はそのま才であるが
、これらの間の連結関係（心線構造）を形式的に陽に表
現すれば第ｒ図（ｂ）のようになる。第ｒ図では便宜上
線図形の幅も表現している。この場合、例えばチェイン
Ｃ／３゜０２、ＯＪはコネクタＪ／を介して、また、チ
ェインＣ／ｌと０／２は太さ分割によって、隣接してい
ると言う。さらに、両者を総称して単にチェインが隣接
していると言うこともある。心線構造記述テーブルはこ
れらのチェインやコネクタとその間の関係を一つのデー
タ構造として表現したものである。本記述テーブルは原
画像の幾何学的柵造１記述したものであり、これにより
複雑な処理が可能となる。

第り図は第ｒ図（ｂ）に対する心線構造記述テーブルの
実施例を示しだものである。第９図中、１４Ｌ−ｉはチ
ェインデータに係わるもの、／！、ｔ−ｊはコネクタデ
ータに係わるものである。／４ｔ−／において、欄Ｔは
チェインの平均の太さを、ＮＰ−ＴおよびＮＰ−Ｂはチ
ェインの先頭および末尾（（おいて連結するチェインま
タハコネクタへのポインタを表わしている（チェインを
構成する正方形において、正方形アドレスが最小の正方
形が存在するチェイン上の端の部分を該チェインの先頭
部、そのもう一方の端の部分を該チェインの末尾と呼ぶ
）。０は連結するものがないことを、負値はチェインへ
の連結を、正値はコネクタへの連結を表わし、Ｏ以外の
値の絶対値はそれぞれに応じたテーブル内のエンドＩＪ
−への値（ボイ／り）を示している。欄ＦＰは図形ファ
イル上の各心線要素へのポインタである。

これによってさらに細かい処理が可能となる。

欄ＴＬ−ＴおよびＴＬ−Ｂは後述の直線追跡処理部で書
き込まれるリンクデータである。欄ＳＡは折れ線近似に
よる屈曲点正方形アドレスである。それぞれの欄内のデ
ータはｇ、ｒ図の図形に関する記述例である。

（へ））直線追跡処理部　一本処理部は、図形ファイル
λ上のチェインデータの全てに対して上記一連の処理が
終了すると起動がかけられ・心線梠造記述テーブル上で
直線追跡処理を行なう。具体的には、コネクタを介しで
あるいは太さ分割によって隣接しているチェイン間の隣
接点（コネクタまたは太さ分割点）における直線として
の連続性（直線連続性）を順次検査していくことにより
行なわれる。このような追跡処理を以下では直線追跡処
理と呼ぶ。

一般に心線構造記述テーブル上でのチェインは７個以上
の線分の連結（折れ線）として表現されている。この場
合、チェイン上での線分はその追跡方向を考慮すればそ
れぞれがベクトル（追跡ベクトル）とみなすことができ
る。したがってデータ何造上を直線追跡するということ
は、それぞれが互いに異なるチェイン上（の端）に存在
して、かつ、互いに（始点と終点とが）コネクタを介し
てまたは太さ分割によって隣接し合うベクトルの直線と
しての連続性を、調べ、もし両追跡ベクトルが直線を成
すならば、対応するチェインデータ間に該テーブル上で
リンクを張ることである。なお、チェインｏｌある方向
に追跡した場合のに番目の折れ線構成ベクトル２　ｖ　
＜　ｃ。

ｋ）と表記するものとする。

いま、第ｇ図において図形を心線構造記述テーブル上で
左から追跡してきてチェイン０／／に達したとする。こ
の場合、ベクトルＶ（０／／、ｌとベクトルＶ　（０１
２，／）との間の直線連続性が次のバラグラフで説明す
る追跡ベクトルの直線連続性の検査法によシ調べられる
。同様にしてベクトルＶ　（０１２，／）とＶ（０／Ｊ
、／）との間の直線連続性が調べられる。さらに直線追
跡が進んでチェインＯ１３に達したとする。この場合　
コネクタＪ／を介してベクトルＶＣＯ／３．／）と直線
連続するようなベクトルをもつチェインをＪｌの近傍か
ら選択する。この場合Ｃ３が選択される。以下このよう
にして直線追跡が行なわれる。チェイン間の直線連続性
の記述は上述のようにチェイン間にリンクを張ることで
行なわれるが、その具体的方法を第り図により説明する
。

第り図のテーブル１ｔＡ−ｉ上の欄ＴＩ、　Ｔ　および
ＴＬＢこれに係わるものであり、ＴＬ−Ｔはチェイ／の
先頭部でのリンク情報を・ＴＬ　Ｂ　　はチェインの末
尾でのリンク情報を表わすのに用いられる。チェインＣ
Ｉとチェイン０２との間に直線連続性が存在するならば
、ＣＩのＴＬ−’Ｉ’またはＴＩ、−Ｂの欄（どちらの
欄かはチェインの直線連続性の成り立つ部分（先頭・末
尾）による）Ｋは、その直線連続性が太さ分割点上で成
り立つならば／の値を、コネクタを介して成り立つなら
ばそのコネクタの欄ＮＢＲ内でのチェインＣ２の番号を
記入する。なお、各コネクタに対して、その上１ｔ２本
の追跡ベクトルが通過する場合はその交点が計算され、
萬性（コネクタ通過点）として登録される。

次に、追跡ベクトルの直線連続性の検査法について述べ
る。直線追跡においては先ず追跡開始のためのベクトル
が初期設定される。

このベクトル（直線追跡ベクトル）は本節で述べる直線
連続性の検査の進行に従ってその先頭が順次直線の追跡
方向に伸びていく。いま、ある時点における直線追跡ベ
クトルＶ’（Ｖ　＝　　Ｐｔ　　Ｐｈ とする（　Ｐｔ、　Ｐｈ　ｋそれぞれ追跡ベクトルの末
尾、先頭と呼ぶ）。この場合、次に追跡すべきベクトル
としてベクトルＶ′ ｖ’　＝　　ｐｔ’　ｐｈ’ 全考えたとき、一つのベクトルがほぼ一直線に並び、か
つ、ｖ′ヲ表わす部分チェインＣ′が追跡開始チェイン
０に比べて太くないならば、この直線追跡ベクトル■は
成長してｖ　＝　ｐｔ　　ｐｈ’ となる（第１０図（ａ））。次にＣ′が太い場合を考え
る。この場合、Ｃ′が長いときは直線追跡はこれで修了
するが、第１Ｏ図（ｂ）のように短いときは追跡ベクト
ル■はこのままにしておき、さらにその先のチェイン（
ベクトル）の追跡に移る。ここでその先の追跡ベクトル
Ｖ′ ｖ′＝　円’　Ｉ’ｈ’ が存在して、しかも例えば第１Ｏ図（ｌ〕）のように細
いならば、直線追跡ベクトルＶは成長して ｖ　＝　　ｐｔ　ｐｈ’ となる。また、第１Ｏ図（Ｃ）のように次に隣接するチ
ェイン（ベクトル）が存在しなければ、直線追跡ベクト
ルＶは成長して Ｖ＝）’ｔｏ。

となる。ここに、Ｐｏは点Ｐｈ’からベクトルＶに下ろ
した垂線の足である。

（至）線図形出力処理部　一本処理部は心線構造記述テ
ーブル／≠上に記述されたチェインおよび該チェインと
直線連続するチェインを一つの線図形（折れ線近似を表
わす座標点列として表現されている）として取シだし、
このようにして取υだされる線図形を統合して外部記憶
装！あるいはファックス出力装置・図形表示装置等に出
力するものであり、本処理部の起動は直線追跡処理部の
終了信号によりかけられる。

〔発明の効果〕

以上説明したように、本発明によれば、従来の技術では
全て′（ｉ７ｓたすことのできなかった前述の諸条件（
二値画像から線図形を抽出する場合の条件）、すなわち （ａ）　　原画像に忠実に線図形が抽出できること、（
ｂ）　　微細図形が線図形の直線部および屈曲点部のど
ちらにおいて接触・交差していても抽出処理が可能なこ
と、 （ｃ）原画像から線図形全抽出・分離した後の残された
微細図形はその形状が損なわれないこと・ （ｄ）　　必要に応じて図形要素がもつ意味内容に基づ
く高次の処理に対処できること、 を全て満たすことが可能となる。

第１１図は本装置により二値画像から線図形の抽出処理
を行なった例であって、同図（ａ）は原画像、（ｂ）は
直線抽出の処理結果である。第１１図から分かるように
、文字　記号等が線図形に屈曲点部分で接触・交差して
いる場合でも直線が忠実に抽出されているのが分かる。

なお、これらの線分の連結関係は全て心線構造記述テー
ブルに記述されているので、必要ならばより上位のデー
タ処理部を構成し、これに該心線イ４造記述テーブルを
接続することも可能となる

【図面の簡単な説明】

第１図は本発明の一実施例（装置構成図）を示している
。 第２図は心線抽出例を示している。 第３図は図形ファイル構成の概念図であり、（ａ）は最
大正方形の連結関係によるグルーピング、（１））は心
線データの線形化表現である９ 第Ｖ図はチェインの太さによる分割を説明しており　、
（ａ）は線図形の例（１つのチェインとして表現される
とする）　、　（ｂ）はチェイン（、）の辺長数列のグ
ラフ表示を示している。 第５図は太さ分割処理部の実施例を示している。 第６図はチェインの折れ線近似の説明図である。 第７因は折れ線近似処理部の実施例を示しているＯ 第２図は線図形の構造表現の説明図であり、（ａ）は図
形の例、（ｂ）は図形（ａ）の心線構造表現の概念図で
ある。 第り図は心線構造記述テーブルの実施例（第２図（ｂ）
に対応させた場合）である。 第１Ｏ図は追跡ベクトルの直線連続性の検査法の説明図
である。 第１１図は本装置による線図形抽出処理の例であり、（
ａ）は原画像＋７Ｌ＋！９−２千怜Ｈ−２８４→を（ｂ
）は直線の抽出処理結果を示している。 ｌ・・・図面等（二値画像データ）、２・・・図形ファ
イル、３・・・図形ファイル撮部、弘・・・チェインデ
ータ選択・読み出し部、！・・・チェインデータ蓄積部
、！−／・・・座標点列データ（Ｘ座標）全格納するＦ
ＩＦＯ型レジスタ、ｊ−２・・座標点列データ（Ｘ座標
）を格納するＦＩＦＯ型レジスタ、ｊ−３・・・正方形
辺長数列データを格納するＦＩＩ”０型レジスタ、６・
・・太さ分割処理部、Ａ−／・・・コントローラ。 乙−！・・・アドレスカウンタ、６−３・・・辺長値レ
ジスタ、６−弘・・・加算器、６−よ・・・差分レジス
タ、ｔ−６・・・遅延回路、６−７・・・差分レジスタ
、２−タ・・・判定回路、ｔ−ｉｏ・・・判定回路、６
〜／ｌ・・・変化点レジスタ、６−１２・・・同値数カ
ウンタ、６−１３・・・定叡値レジスタ、６−ｌ≠・・
・定数値レジスタ、Ａ−／！−１．−２１・・・処理回
路、７・・・正方形アドレス蓄積部、？・・・折れ線近
似処理部、？・・・チェイン中心＃７算出部、ター／、
？−，２，９−３・・・Ｘ＋　ｙ＋ｔＴｈ格納するレジ
スタ、ター≠・・中心点算出回路、ターｊ・・・座標点
格納レジスタ、デー６・・・遅延回路、ターフ・・・中
間点算出回路、１０−座標点列蓄積部、／／・・・折れ
線近似部、／２・・・正方形アドレス蓄積部、／３・・
・心線構造記述処理部、ｌ≠・・・心線構造記述テーブ
ル、ｉｓ・・・直線追跡処理部、／ｌ、・・・線図形出
力処理部。

Claims (4)

【特許請求の範囲】
1. （１）線図形および文字・記号（微細図形と呼ぶ）で構
   成される二値画像データ中から該線図形を追跡・抽出し
   、折れ線近似する線図形処理装置において、 （ａ）該二値画像に含まれる各図形要素の心線データ（
   該図形要素に内接する最大の正方 形（最大正方形と呼ぶ）の列（チェインと 呼ぶ）と、チェインとチェインとを連結し かつ図形に内接する最大正方形（コネクタ と呼ぶ）、およびそれらの間の連結関係を 表現する構造体（心線構造と呼ぶ）に関す るデータ）を記述することにより、該二値 画像を予め一つの図形ファイルとしてファ イル化し、該図形ファイルから心線データ を必要に応じて読み出す図形ファイル操作 部と、 （ｂ）該図形ファイル操作部を介して図形ファイルから
   チェインデータを選択し、読み出 すチェインデータ選択・読み出し部と、 （ｃ）該選択・読み出し部によって取り込まれたチェイ
   ンデータを、該チェインデータを 構成している正方形の辺長データに基づい て、太さ毎に部分データに分割する太さ分 割処理部と、 （ｄ）該太さ分割処理部により分割された該チェインの
   各部分のデータ（部分チェインデ ータと呼ぶ）を折れ線近似する折れ線近似 処理部と、 （ｅ）該太さ分割処理部で得られる各部分チェインデー
   タに係わる心線構造を、該折れ線 近似処理部で得られるデータに基づいて、 テーブル（心線構造記述テーブルと呼ぶ） として記述する心線構造記述処理部と、 （ｆ）該心線構造記述処理部により記述される心線構造
   記述テーブル上のチェインデータ を該テーブル上のポインタを辿ることによ り追跡し、該チェインデータと隣接するチ ェインデータが一本の直線として連続する （直線連続すると言う）かどうかを判定し、直線連続す
   る場合には該二つのチェインデ ータ間に該テーブル上でリンクを張る直線 追跡処理部と、 （ｇ）該直線追跡処理部により直線追跡された該心線構
   造記述テーブルから、該テーブル 上でリンクを張られたチェインデータは直 線として連続することを利用して、線図形 データを折れ線近似を表わす点列として出 力する線図形出力処理部、 とから構成されることを特徴とする線図形処理装置。
2. （２）太さ分割処理部において、各図形要素のチェイン
   データを、該チェインを構成する各正方形の辺長のデー
   タ列により、太い部分と細い部分へ分割することを特徴
   とする特許請求の範囲第１項記載の線図形処理装置。
3. （３）折れ線近似処理部において、各図形要素のチェイ
   ンの中心線を該チェインを構成する各正方形の中心点の
   データ列として算出し、該データ列（座標点列）を線分
   の連結として近似することにより、該チェインデータを
   折れ線近似することを特徴とする特許請求の範囲第１項
   記載の線図形処理装置。
4. （４）直線追跡処理部において、上記心線構造記述テー
   ブル上の二つのチェインデータが直線連続するかどうか
   の判定をチェインの太さ情報を用いて行うことを特徴と
   する特許請求の範囲第１項記載の線図形処理装置。