JP2552653B2 - 重畳図形分離方法 - Google Patents

Description

【発明の詳細な説明】 （発明の属する技術分野） 本発明は、地図や図面などの線画において、重畳して
いる図形を分離する方法に関するものである。

（従来の技術） 地図や図面などの線分で構成されている線画を画像と
して計算機に入力した場合に、画像処理の対象となる線
図形が、例えば道路を表わす線図形や家屋を表わす線図
形毎には区別されておらず混在したり、異なる種類の線
図形の構成する部分どうしが互いに重なったままになっ
ていることがある。このような線図形のままでは地図や
図形のデータベースとしては活用することができないの
で、入力された線図形の中から例えば、道路を表わす線
図形だけ、あるいは家屋を表わす線図形だけ等というよ
うに、それぞれを線図形単位に分離して抽出する必要が
生じてくる。そこで、入力された線図形の中から、背景
領域を囲む線図形をループ図形と呼ぶことにするが、こ
のループ図形を構成している部分が、他のループ図形の
構成部分でもある場合には、ループ図形どうしが重畳し
ているので、その重畳している構成部分を分離して抽出
するという処理を行う必要がある。ループ図形を抽出
し、その図形とその他の図形とが重畳している部分だけ
を抽出する従来方法として、ループ図形上にない線分か
らループ図形を通り、ループ図形上にない線分に至る直
線を抽出して、その直線上、かつループ図形上にある部
分を重畳部分とする方法（情報処理学会第31回全国大
会、6N−１）がある。

しかし、第１図に示すように、単調な折れ線とループ
図形が重畳した場合、重畳部分がループ図形上にない線
分間を結ぶ直線上にないために重畳部分を抽出できない
という問題があった。

第１図において、第１図（ａ）は入力図形、第１図
（ｂ）はループ図形以外の図形の従来方法による抽出結
果である。

図中、１はループ図形以外の図形で細い線で表わし、
２はループ図形とその他の図形の重畳部分で太い線で表
わし、３は分岐点で黒丸で表わす。

また、分岐点３の一部をP₁,P₂,…,P₆と表わし、線分
の部をL₁,L₂,…,L₁₂と表わす。

第１図に示す重畳は、地図中の建物を表わす線図形と
道路を表わす線図形の間で生じる。

すなわち、１つのループ図形は１つの建物を表わし、
建物がかたまって街区をなすとき、上記の重畳部は道路
の一方の側を表わしている。

従来方法では、ループ図形上にない線分がL₁とL₉だけ
しかなく、それらを結ぶ直線は存在しないため、上記の
重畳部分を抽出することができないという問題点があっ
た。

（発明の目的） 本発明は、従来方式の欠点を解決するために、１つの
ループ図形を１つずつ抽出し、注目している１つのルー
プ図形以外の線分から、注目ループ図形上を通って、注
目している１つのループ図形以外の線分に至る単調な折
れ線を抽出し、注目ループ図形の上でその折れ線上にあ
る部分を他の図形との重畳部分としたものである。

（発明の構成および作用） 第２図は、本発明の重畳図形分離方法を説明する図で
ある。

第２図において、第２図（ａ）は入力図形であり第１
図（ａ）と同じものである。

第２図（ｂ）はループ図形以外の図形の本発明による
抽出結果を示す。

本発明では、第１に１つのループ図形を抽出する。

この抽出方法の具体的な手順はイメージデータとベク
トルデータの両方に対して、参考文献“特願昭61−5050
9号”に詳細に記述されているので省略する。

例えば、ループ図形L₄・L₈・L₁₂・L₇が抽出されたと
する。

第２に、ループ図形L₄・L₈・L₁₂・L₇上にある分岐点
（分岐点とは接続する線分が３本以上ある点である。）
のうち、そのループ図形以外の他の図形上にある点をそ
の分岐点の近傍に有するものP₃、P₆が抽出される。な
お、点Ａと点Ｂが隣り合う場合、点Ａは点Ｂを近傍に持
つ、または点Ａは近傍点Ｂを持つ、という。

第３に、これらの分岐点の中から、注目ループ図形に
おいて隣り合う分岐点の対（P₃、P₆）が抽出される。

第４に、第２の過程において抽出された分岐点P₃、P₆
に接続し、かつ注目ループ図形L₄・L₈・L₁₂・L₇以外の
図形にある線分L₃、L₁₁が抽出される。

第５に、第３の過程において抽出した分岐点対の各々
について、次の処理を行う。一方の分岐点に接続する線
分から分岐点対の間にある線分列を通り、他方の分岐点
に接続する線分に至る折れ線の中に、単調な折れ線を構
成するものがあるならば、単調な折れ線上にあるループ
図形部分を他の図形が重畳する部分とする。

ここで、単調な折れ線とは、その折れ線上のすべての
分岐点において、分岐点に入ってくる線分と、出ていく
線分とのなす角度が、予め与えられたθ（例えば、５
゜）以内にあるものとする。

注目ループ図形L₄・L₈・L₁₂・L₇に対して、まず、分
岐点対（P₃,P₆）を選択して、２つの折れ線L₃・L₄・L₈
・L₁₂・L₁₁と、L₃・L₇・L₁₁の中に単調な折れ線がある
かを調べる。

L₃・L₄・L₈・L₁₂・L₁₁は、分岐点P₃における２つの線
分L₃とL₄との角度と、分岐点P₆における２つの線分L₁₂
とL₁₁との角度が共にθ以内であるために、単調な折れ
線と判定される。

線分L₄とL₈との角度及び線分L₈とL₁₂との角度はθ以
内ではないが、線分L₄とL₈との間の点は分岐点ではな
く、線分L₈とL₁₂との間の点も分岐点ではないので、そ
れらの角度は問題にしない。そこで、折れ線L₃・L₄・L₈
・L₁₂・L₁₁は単調な折れ線と判定されている。

曲線L₃・L₇・L₁₁は、分岐点P₃における２つの線分L₃
とL₇との角度と、分岐点P₆における２つの線分L₇とL₁₁
との角度がθ以内にないため、単調でない曲線と判定さ
れる。

従って、単調な折れ線L₃・L₄・L₈・L₁₂・L₁₁とループ
図形L₄・L₈・L₁₂・L₇との共通部分である線分L₄,L₈,L₁₂
が重畳部分となる。

次に、残りの分岐点対について同様な処理を行う。注
目ループ図形L₄・L₈・L₁₂・L₇に対しては（P₃,P₆）以外
の分岐点対がないため、第５の過程を終了する。次に、
注目ループ図形としてL₃・L₇・L₁₁・L₆が抽出される。
この注目ループの分岐点対として、対（P₂,P₃）、（P₃,
P₆）、（P₆,P₅）、（P₅,P₂）が抽出される。対（P₂,
P₃）に対して、折れ線L₂・L₃・L₄が抽出され、線分L₂と
L₃との角度及び線分L₃とL₄との角度がともにθ以内であ
るので、折れ線L₂・L₃・L₄は単調な折れ線と判定され
る。対（P₃,P₆）に対して、折れ線L₄,L₇,L₁₂が抽出さ
れ、線分L₄とL₇との角度がθ以内でないので、折れ線
L₄,L₇,L₁₂は単調な折れ線ではないと判定される。対（P
₆,P₅）に対して、折れ線L₁₂・L₁₁・L₁₀が抽出され、線
分L₁₂とL₁₁との角度及び線分L₁₁とL₁₀との角度がともに
θ以内であるので、折れ線L₁₂・L₁₁・L₁₀は単調な折れ
線と判定される。対（P₅,P₂）に対して、折れ線がL₁₀・
L₆・L₂が抽出され、線分L₁₀とL₆との角度がθ以内でな
いので、折れ線L₁₀・L₆・L₂は単調な折れ線ではないと
判定される。従って、ループ図形L₃・L₇・L₁₁・L₆と単
調な折れ線L₂・L₃・L₄との共通部分である線分L₃と、ル
ープ図形L₃・L₇・L₁₁・L₆と単調な折れ線L₁₂・L₁₁・L₁₀
との共通部分である線分L₁₁とが重畳部分として抽出さ
れる。以下同様に、１つずつループ図形を抽出して、上
記の手順を繰り返し適用する。

これにより、第２図に示すように、本発明は、第１図
に示した従来方式の問題点を解決する。

第３図は、本発明をイメージデータに対して適用する
例を説明する図である。

第３図において、４は画像メモリ部、５は細線化部、
６は重畳イメージ図形分離部、７は制御部である。

画像メモリ部４は、地図や図面などをディジタル画像
として蓄積する部分で、第３図には記載されていない外
部からディジタル画像が供給される。

細線化部５は、画像メモリ部４に蓄積されているディ
ジタル画像に含まれる線図形を幅１画素の中心線に変換
して、中心線上にある画素の値を１に、その他の画素の
値を０に変換した細線化画像を画像メモリ部４に格納す
る。

細線化の方法については、幾つかの方法が知られてい
る（電子通信学会，技術研究報告,PRL75−66など）が、
それらのいずれでもよい。

重畳イメージ図形分離部６は、画像メモリ部４に蓄積
されている細線化画像からループ図形を抽出し、ループ
図形が他の図形と重畳している部分を抽出して、ループ
図形上にあり、かつ他の図形と重畳していない部分を画
像メモリ部４に蓄積されている細線化画像上で値２の画
素に変換する。

制御部７は、画像メモリ部４にディジタル画像が入力
されたとき、細線化部５を動作させ、その後に重畳イメ
ージ図形分離部６を動作させるように全体を制御する部
分である。

第４図は、第３図の構成要素である重畳イメージ図形
分離部６をさらに説明する図である。

この重畳イメージ図形分離部６が、本発明の第１の実
施例である。

第４図において、61はループ図形抽出部、62はループ
図形メモリ部、63は分岐点対抽出部、64は線分抽出部、
65は単調折れ線軸出部、66は制御部である。

ループ図形抽出部61は、画像メモリ部４に蓄積されて
いる細線化画像からループ図形を１つずつ点列（すなわ
ち、画素の座標列）として抽出し、ループ図形メモリ部
62に格納する（第１の過程）。

ループ図形メモリ部62は、ループ図形を１つずつ点列
として蓄積する。

分岐点対抽出部63は、１つのループ図形をなす点列を
ループ図形メモリ部62から入力して、画像メモリ部４に
蓄積されている細線化画像において、そのループ図形以
外の図形上にある近傍点（近傍画素）を持つ分岐点を抽
出する（第２の過程）。これらの分岐点の中から、注目
ループ図形上において隣り合う分岐点対を抽出する。
（第３の過程） 線分抽出部64は、分岐点対抽出部63から１つのループ
図形をなす点列と、分岐点対とを入力して、入力された
分岐点に接続し、かつ注目ループ図形以外の図形上にあ
る線分を抽出する。（第４の過程） 具体的には、分岐点から注目ループ図形以外の図形上
にある点を１つずつ追跡して、追跡された点列が直線に
近似できなくなったとき追跡を停止して、得られた点列
を１つの線分とする。

点列が直線に近似できるか否かを検査する方法は幾つ
か知られている（昭和59年度電子通信学会総合全国大会
1252など）が、そのいずれでもよい。

単調折れ線抽出部65は、線分抽出部64から１つのルー
プ図形をなす点列と、分岐点対と、分岐点に接続する線
分とを入力し、以下の処理を行う。（第５の過程） まず、前記ループ図形をなす点列を直線近似して線分
列に変換する。但し、分岐点のところでは必ず線分に分
割する。

次に、分岐点対の各々について、一方の分岐点に接続
する線分から分岐点対の間にある線分列を通り、他方の
分岐点に接続する線分に至る折れ線の中に単調な曲線が
あるならば、分岐点対の間にある線分列を他の図形が重
畳する部分として、そのループ図形上にあり、かつ他の
図形と重畳していない部分を画像メモリ部４に蓄積され
ている細線化画像上で値２の画素に変換する。

制御部66は、ループ図形抽出部61、分岐点対抽出部6
3、線分抽出部64、単調折れ線抽出部65の順に動作する
ように、ループ図形抽出部61から単調折れ線抽出部65を
制御する部分である。

第５図は、本発明をベクトルデータに対して適用する
例を説明する図である。

第５図において、画像メモリ部４と細線化部５は第３
図のものと同じである。８はベクトル化部、９はベクト
ルメモリ部、10は重畳ベクトル図形分離部、11は制御部
である。

ベクトル化部８は、画像メモリ部４に蓄積されている
細線化画像の分岐点及び端点を抽出し、それらの２点の
間の点列を直線近似して線分列に分割し、分岐点及び端
点の座標と、線分の両端の画素の座標をベクトルメモリ
部９に格納する。

直線近似の方法は、幾つかの方法が知られている（昭
和59年度電子通信学会総合全国大会1252など）が、それ
らのいずれでもよい。

ベクトルメモリ部９は、ベクトル化部８より出力され
るベクトルデータを蓄積する部分である。

重畳ベクトル図形分離部10は、ベクトルメモリ部９に
蓄積されているベクトルデータからループ図形を抽出
し、ループ図形が他の図形と重畳している部分を抽出し
て、ループ図形上にあり、かつ他の図形と重畳していな
い線分をベクトルメモリ部９に格納する部分である。

本発明の第２の実施例である重畳ベクトル図形分離部
10の詳細な構成は、第４図に示した重畳イメージ図形分
離部の構成と基本的には同じである。但し、細線化画像
の代りに、それをベクトル化したデータを用いるため各
構成要素の機能は以下のようになる。

ループ図形抽出部61は、ベクトルメモリ部９に蓄積さ
れているベクトルデータからループ図形を１つずつ線分
列として抽出し、ループ図形メモリ部62に格納する。

ループ図形メモリ部62は、ループ図形を１つずつ線分
列として蓄積する。

分岐点対抽出部63は、１つのループ図形をなす線分列
をループ図形抽出部61から入力して、ベクトルメモリ部
９に蓄積されているベクトルデータにおいて、前記ルー
プ図形以外の図形上にある線分が接続している分岐点を
抽出し、これらの分岐点の中から、注目ループ図形上に
おいて隣り合う分岐点対を抽出する。

線分抽出部64は、分岐点対抽出部63から１つのループ
図形をなす線分列と、分岐点対とを入力して、入力され
た分岐点に接続し、かつ注目ループ図形以外の図形上に
ある線分を抽出する。

単調折れ線抽出部65は、線分抽出部64から１つのルー
プ図形をなす線分列と、分岐点対と、分岐点に接続する
線分とを入力して、分岐点対の各々について、一方の分
岐点に接続する線分から分岐点対の間にある線分列を通
り、他方の分岐点に接続する線分に至る曲線の中に単調
な折れ線があるならば、分岐点対の間にある線分列を他
の図形が重畳する部分として、ループ図形上にありかつ
他の図形と重畳していない部分の線分列をベクトルメモ
リ部９に出力する。

制御部11は、画像メモリ部４にディジタル画像が入力
されたとき、細線化部５、ベクトル化部８、重畳ベクト
ル図形分離部10の順に動作させるように全体を制御する
部分である。

なお、ループ図形は、かすれや途切れにより閉じてい
なくても、論理的に１つのループ図形と判定できるもの
であれば構わない。

（発明の効果） 以上述べたように、本発明は、ループ図形と他の図形
が重畳する部分を、ループ図形上にない線分間を結ぶ直
線上にない部分も含めて抽出できるため、従来方式より
も抽出洩れが少ないという効果が得られる。

【図面の簡単な説明】

第１図は従来方式の重畳図形分離方法の欠点を示す図、
第２図は本発明の重畳図形分離方法を説明する図、第３
図は本発明をイメージデータに対して適用する例を説明
する図、第４図は本発明の一実施例を説明する図、第５
図は本発明をベクトルデータに対して適用する例を説明
する図である。 １……ループ図形以外の図形、 ２……ループ図形とその他の図形の重畳部分、 ３……分岐点、４……画像メモリ部、 ５……細線化部、 ６……重畳イメージ図形分離部、 ７……制御部、８……ベクトル化部、 ９……ベクトルメモリ部、 10……重畳ベクトル図形分離部、11……制御部、 61……ループ図形抽出部、 62……ループ図形メモリ部、 63……分岐点対抽出部、64……線分抽出部、 65……単調折れ線抽出部、66……制御部。

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】地図や図形が、イメージデータあるいはベ
   クトルデータとして計算機に入力され、前記計算機内の
   メモリに蓄積された図形データから、１つの背景領域を
   囲むループ図形を抽出し、そのループ図形の構成部分が
   前記ループ図形以外の図形の構成部分でもある場合、す
   なわち重畳している場合に、その重畳した構成部分を分
   離して抽出する方法であって、 前記イメージデータあるいはベクトルデータからループ
   図形を抽出する第１の過程と、 該ループ図形を構成する前記イメージデータあるいはベ
   クトルデータから、前記ループ図形以外の図形上の点を
   近傍に持つものを分岐点として抽出する第２の過程と、 前記第２の過程により得られた複数の分岐点の中から隣
   り合う分岐点対を抽出する第３の過程と、 前記第２の過程により得られた分岐点に接続し、かつ、
   前記ループ図形以外の図形上の線分を、前記イメージデ
   ータあるいはベクトルデータから直線近似により求める
   第４の過程と、 前記第１の過程で得られたループ図形を前記第３の過程
   により得られた分岐点対に基づき直線近似して線分列に
   変換し、 分岐点対の各々について、分岐点対の一方の分岐点に接
   続する前記第４の過程により得られた線分から分岐点対
   の間にあるループ図形上の線分列を通り、分岐点対の他
   方の分岐点に接続する前記第４の過程により得られた線
   分に至る折れ線の中に単調な折れ線があるか否かを検査
   し、単調な折れ線があるならば、注目ループ図形上で、
   単調な折れ線上にある線分列をループ図形以外の図形と
   重畳する構成部分とする第５の過程と、 を有することを特徴とする重畳図形分離方法。