JPH02183876A - 線図形変換方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （発明の属する技術分野） 本発明は、地図や図面などの画像をスキャナやＴＶカメ
ラなどを用いて得らるディジタルニ値画像を線幅１画素
の二値画像（以下、線図形という）に変換する方法に関
する。

（従来の技術） 従来、線図形の変換方法としては、線図形を背景から１
画素ずつ削る細線化方法が多く考案されているが、しか
し１分岐点の近傍において細線化された線幅が１画素に
ならないという問題があった。

そこで１本出願人の発明者は、細線化により得られた不
完全な線図形を、連結グラフに変換して。

その連結グラフ上で余分な辺を削除して線図形に変換す
る方法を提案した（特願昭６２−１７２８７５号）。

しかし、この方法でも細線化処理によって中心線を求め
ても中心線の交差部のいくつかにおいて。

線幅が１画素にならないという問題があった。このこと
は１画像上の特徴点を抽出して特徴点間の画素列を直線
に近似して線分のベクトル化などの線図形処理を困難に
している。

（発明の目的） 本発明は上記問題点を解決し細線化処理によって得られ
た不完全な線図形を連結グラフに変換して、この連結グ
ラフ上で余分な辺を削除して、完全な線図形に変換する
方法を提供することを目的とする。

（発明の枯成） （発明の特徴と従来技術との差異） 本発明はＥ記口的を達成するため、以下の手順で順次実
行することを最も主要な特徴とする。

（手順１）二値画像データを細線化して得られる中心線
画像の中心線上にある画素を節点、隣接している節点間
を辺とする連結グラフに変換する。

（手Ｍ　２　）手順ｌ又手順３（手Ｍ３から戻って場合
）によって得られたグラフから所定の第１の変換規則に
より斜めの辺を除去すること、この除去により得られた
グラフから、さらに所定の第２の変換規則から第４の変
換規則により水平及び垂直の辺を除去することとの２段
階の除去処理をグラフが変化しなくなるまで反復する。

（手ＩＲ３）手順２によって得られたグラフの中で、所
定の第５の変換規則から第９の変換規則によりグラフの
整形を行う。そして１本整形によるグラフが変化したな
らば、手順２に戻る。その他の場合には、処理を終了す
る。本整形の目的は、斜辺の交差点を節点上に移動する
ことにある。

従来技術とは１手順２及び手順３の各段階で変換規則を
増加させ、細線化により得られた不完全な線図形を、こ
こでの段階において連結グラフ上で余分な辺を削除して
、中心線の交差部における線幅が１画素になるようにし
た点が異なる。

（実施例） 以下、第１図ないし第８図の連結グラフへの変換処理を
説明する図及び第９図のハード構成図により説明する。

第１図は、前記の手順１で述べた連結グラフへの変換処
理を説明する図である。

すなわち、第１図（ａ）は、細線化されたディジタル２
値画像の例であり、値１の画素は図形の中心線上の画素
を、値０の画素は、それ以外の画素を表わす。

第１図（ｂ）は、値１の画素に黒丸で表わす節点を置き
、隣接する値１の画素の間に実線で示す辺を置いた連結
グラフである。

第１図かられかるように、細線化処理によって中心線を
求めても線の交差部では線幅は１画素にならない。この
ことは、ベクトル化、特徴点抽出など線図形処理を困難
なものにしている。第１図に示す不完全な線図形は、先
の発明（特願昭６２−１７２８７５号）を適用しても完
全な線図形に変換できない例でもある。

第２図は、手順２において斜めの辺を除去するために適
用される第１の変換規則を表わしている。

すなわち、第２図（ａ）では、黒丸で表わす節点の間に
実線で表わす辺１，２．３が存在し、かつ破線で表わす
辺４が存在しないならば１辺１を除去する。

第２図（ｂ）では、黒丸で表わす節点の間に実線で表わ
す辺１，２．３が存在し、かつ破線で表わす辺５が存在
しないならば１辺１を除去する。

但し、記載されていない節点及び辺は、存在しても存在
していなくともよい。例えば１辺４と辺５が交差すると
ころに節点が存在していてもよいし、辺１と対角線をな
す辺が存在してもよい。

さらに、第２図の部分グラフを９０”　、　１８０’２
７０°回転して得られる６つの変換規則も第１の変換規
則に加える。これらの規則により各部分グラフの置き換
えは、同時に行うことができるので並列処理に向くとい
う長所がある。

第３図（ａ）は１手順２において水平及び垂直の辺を除
去するために適用される第２の変換規則を表わしている
。

すなわち、黒丸で表わす節点の間に実線で表わす辺６，
７．８が存在し、かつ破線で表わす辺９゜１０が存在し
ないならば１辺６を除去する。

なお、第３図（ａ）の部分グラフを９０’　、　１８０
’２７０°回転して得られる３つの変換規則も第２の変
換規則に加える。

第３図（ｂ）は、手順２において水平及び垂直の辺を除
去するために適用される第３の変換規則を表わしている
。

すなわち、黒丸で表わす節点の間に実線で表わす辺６，
７．８が存在し、かつ破線で表わす辺９゜１１が存在し
ないならば、辺６を除去する。

なお、第３図（ｂ）の部分グラフを９０’　、　１８０
’２７０”回転して得られる３つの変換規則も第３の変
換規則に加える。

第３図（ｃ）は１手順２において水平及び垂直の辺を除
去するために適用される第４の変換規則を表わしている
。

すなわち、黒丸で表わす節点の間に実線で表わす辺６，
７．８が存在し、かつ破線で表わす辺１０゜１２が存在
しないならば１辺６を除去する。

なお、第３図（ｅ）の部分グラフを９０’　、　１８０
゜２７０°回転して得られる３つの変換規則も第４の変
換規則に加える。

第２から第４の変換規則により各部分グラフを置き換え
ることは、同時に行うことができるので並列処理に向く
という長所がある。

手順２において、まず、第１の変換規則が適用され、次
に第２から第４の変換規則が適用される。

そして、グラフ変更されたならば、さらに第１の変換規
則を適用することと、第２から第４の変換規則を適用す
ることを再度順次実行する。

以下同様にして、グラフが変化しなくなるまで。

第１の変換規則を適用し、次に第２から第４の変換規則
を適用することを反復する。

第４図は、第１図（ｂ）に手順２を適用した例を示して
いる。

第４図（ａ）は、第１図（ｂ）に第１の変換規則を適用
した結果のグラフを示す。

第４図（ｂ）は、第４図（ａ）に第２から第４の変換規
則を適用した結果のグラフを示す。

以上の１回目の反復処理によりグラフは変化したので、
さらに第１の変換規則を適用する。

第４図（ｃ）は、第４図（ｂ）に第１の変換規則を適用
した結果のグラフを示す。

第４図（ｄ）は、第４図（ｃ）に第２から第４の変換規
則を適用した結果のグラフを示す。

以上の２回目の反復処理によりグラフは変化したので、
さらに３回目の反復処理を行うが、グラフは変化しない
ので４回目の反復には進まずに手順２を終了する。

なお、変換規則の適用手順を、第２から第４の変換規則
の適用、第１の変換規則の適用という順に変更してもよ
い。また、ｎ回目の反復において第２から第４の変換規
則によりグラフが変化せず、かつｎ＋１回目の反復処理
において第１の変換規則の適用によりグラフが変化しな
いならば、手順２を終了することができる。

第５図は１手順３で述べたグラフの整形処理を説明する
図である。

第５図（ａ）は１手順３において適用される第５の変換
規則を表わしている。すなわち、黒丸で表わす節点の間
に実線で表わす辺１３．１４が存在し。

かつ、破線で表わす辺１５．１６．１７．１８が存在し
ないとき１辺１４は除去され、辺１５と１６が追加され
る。

これにより、斜辺の交点が右下の節点に移動される。

移動先は右下の節点に限定されず、同図上の他の３つの
節点のいずれであってもよい。

同様にして、第５図（ｂ）から（ｅ）は、それぞれ手順
３において適用される第６の変換規則から第９の変換規
則を表わしている。これにより、斜辺の交点が４つの黒
丸で表わす節点のいずれかに移動される。

これらの規則により各部分グラフの置き換えは、同時に
行うことができるので並列処理に向くという長所がある
。

第６図は、手順３の適用例を示している。

第６図（ａ）は、第４図（ｄ）に手順３を実行して得ら
れるグラフを示す。

この整形処理によりグラフは変化したので１手順２と手
順３が再び実行される。

第６図（ｂ）は、第６図（ａ）に手順２を実行して得ら
れるグラフを示す。

第６図（Ｃ）は、第６図（ｂ）に手順３を実行して得ら
れるグラフを示す。

この整形処理によりグラフは変化したので手順２と手順
３が再び実行されるが、グラフは変化しない、従って、
第６図（ｃ）が本発明により得られる結果である。この
図かられかるように、ＩＩＡ幅１画素の完全な線図形が
得られている。

第７図（ａ）から（ｃ）は、第５図（ａ）に示す第５の
変換規則の代わりに用いることができる規則の例を示し
たものである。

第７図（ｄ）から（ｇ）は、それぞれ第６の変換規則か
ら第９の変換規則の代わりに用いることができる変換規
則の例を示したものである。

第８図は、本発明の方法の収束をはやめるために１手順
３において実行される変換規則に加える第１Ｏの変換規
則と第１１の変換規則を示している。

第８図（ａ）は、黒丸で表わされる４つの節点の間に実
線で表わされる辺１９．２０．２１．２３が存在し。

かつ破線で表わされる辺２２．２４が存在しないならば
１辺１９．２０を削除し、辺２２を追加するという第１
Ｏの変換規則を表わしている。

第８図（ｂ）は、黒丸で表わされる４つの節点の間に実
線で表わされる辺１９．２０．２２．２４が存在し、か
つ破線で表わされる辺２１．２３が存在しないならば１
辺１９．２０を削除し１辺２１を追加するという第１１
の変換規則を表わしている。

第８図（ｅ）と（ｄ）は、それぞれ第１０と第１１の変
換規則のかわりに用いることができる変換規則を表わし
ている。

第１０と第１１の変換規則を加えると、反復回数が減る
が、結果の形状がやや不自然になる。

第９図は本発明方法を実施するハード構成の一実施例図
である。

第９図において、１００はＣＰＵ及びメモリからなる処
理装置、　ｌｏｔは画像メモリ部、１０２は細線化部、
１０３はグラフ変換部、１０４はグラフメモリ部、１０
５は辺除去処理部、１０６は整形処理部、１０７は制御
部である。

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

細線化部１０２は、画像メモリ部１０１に蓄積されてい
るディジタル画像を中心線に変換して、第１図（ａ）に
示すよう中心線上にある画素の値を「１」に、その他の
画素の値を「０」に変換した中心線画像を、画像メモリ
部１０１に格納する。

細線化の方法については、いくつかの方法が知られてい
る（Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ　Ｖｏｌ
、２０．　Ｎｏ、３゜ｐｐ、２９７−３０７など）が、
それらのいずれでもよい。

グラフ変換部１０３は、画像メモリ部１０１に蓄積され
ている中心線画像に対して前記の手順１を行い。

結果として得られるグラフをグラフメモリ部１０４に書
き込む部分である。

グラフメモリ部１０４は、グラフ変換部１０３、辺除去
処理部１０５．　’３１形処理部１０６の入力または（
及び）出力となるグラフを記憶する部分である。

辺除去処理部１０５は、グラフメモリ部１０４に蓄積さ
れているグラフに対して前記の手順２を行い、グラフの
一部の辺をグラフメモリ部１０４から除去する部分であ
る。

整形処理部１０６は、グラフメモリ部１０４に蓄積され
ているグラフに対して前記の手順３を行い、グラフの一
部の辺をグラフメモリ部１０４から除去することと、グ
ラフメモリ部１０４に蓄積されているグラフにいくつか
の辺を追加することを行う部分である。

制御部１０７は１画像メモリ部ｌｏｔに蓄積されている
ディジタル画素に前記の手順１を実行し、グラフが変化
しなくなるまで手順２と手順３を順次実行することを反
復し、完全な線図形を表わすグラフに変換してグラフメ
モリ部１０４に格納するように全体を制御する部分であ
る。これらの動作は、以下のとおりである。

まず、制御部１０７の指示により、細線化部１０２は画
像メモリ部１０１に蓄積されている画像を中心線画像に
変換して、画像メモリ部１０１に格納する。

次に、制御部１０７の指示により、グラフ変換部１０３
は、画像メモリ部１０１に蓄積されている中心線画像に
対して前記の手順１を実行して、第１図（ｂ）に示した
連結グラフに変換して、グラフメモリ部１０４に格納す
る。

次に、制御部１０７の指示により１辺除去処理部１０５
は、グラフメモリ部１０４に蓄積されているグラフに対
して前記の手順２を実行して、第２図と第３図に示した
第１ないし第４の変換規則で部分グラフの変換を行い、
グラフメモリ部１０４に蓄積されているグラフを変更す
る。

次に５制御部１０７の指示により、整形処理部１０６は
、グラフメモリ部１０４に蓄積されているグラフに対し
て前記の手順３を実行して、第５図に示した第５ないし
第９の変換規則で部分グラフの変換を行い、グラフメモ
リ部１０４に蓄積されているグラフを変更する。

制御部１０７は、整形処理部１０６によりグラフが変更
されなくなるまで１辺除去処理部１０５と整形処理部１
０６に順次上記の動作を指示する。

（発明の効果） 以上説明したように、本発明により得られた連結グラフ
を基に線図形の画素間の連結性をみると。

線幅１画素の完全な線図形が得られる。

この完全な線図形を用いて、特徴点抽出、ベクトル化な
どの処理を行うことにより、従来に比べて、コンパクト
で良い形状の結果が得られる。

【図面の簡単な説明】

第１図は手順１で述べたグラフへの変換処理を説明する
図、第２図は第１の変換規則を説明する図、第３図は第
２から第４の変換規則を説明する図、第４図は手順２で
述べた辺除去処理を説明する図、第５図は第５から第９
の変換規則を説明する図、第６図は手順３で述べたグラ
フ整形処理を説明する図、第７図は第５から第９の変換
規則の代わりに用いることができる規則の例を説明する
図、第８図は手順３に追加して実行できる第１０と第１
１の変換規則を説明する図、第９図は本発明のハード構
成の一実施例図である。 １〜２４・・・辺、１００・・・処理装置、１０１・・
・画像メモリ部、１０２・・・細線化部。 １０３・・・グラフ変換部、１０４・・・グラフメモリ
部、１０５・・・辺除去処理部、１０６・・・整形処理
部、１０７・・・制御部。 特許出願人　日本電信電話株式会社

Claims (2)

【特許請求の範囲】
1. （１）二値画像を線図形に変換するにあたり、（Ａ）第
   １の過程は、前記二値画像を細線化して得られる中心線
   画像の中心線上にある画素を節点、該節点が隣接してい
   る節点間を辺とする連結グラフに変換して記憶すること
   、 （Ｂ）第２の過程は、前記第１の過程により得られたグ
   ラフから、 ３つの節点及び辺１、２、３が存在し、かつ辺４または
   辺５が存在しないという条件を満足する部分グラフから
   辺１を除去する第１の変換規則と、第１の変換規則の部
   分グラフ及び削除する辺を９０°ずつ３回転して得られ
   る３つの変換規則を加えた４つの変換規則により、斜め
   の辺を除去することと、 この除去により得られたグラフから、 さらに、４つの節点及び辺６、７、８が存在し、かつ、
   辺９、１０が存在しないという条件を満足する部分グラ
   フから辺６を除去する第２の変換規則と、 ４つの節点及び辺６、７、８が存在し、かつ、辺９、１
   １が存在しないという条件を満足する部分グラフから辺
   ６を除去する第３の変換規則と、４つの節点及び辺６、
   ７、８が存在し、かつ、辺１０、１２が存在しないとい
   う条件を満足する部分グラフから辺６を除去する第４の
   変換規則と、第２、第３、第４の変換規則の部分グラフ
   及び削除する辺を９０°ずつ３回転して得られる９つの
   規則を加えた１２の規則により水平及び垂直の辺を削除
   することの２段階の除去処理をグラフが変化しなくなる
   まで反復すること、 （Ｃ）第３の過程は、前記第２の過程により得られたグ
   ラフの中で、 ４つの節点及び辺１３、１４が存在し、かつ、辺１５、
   １６、１７、１８が存在しないという条件を満足する部
   分グラフに対して辺１４を除去し、辺１５、１６を追加
   する第５の変換規則と、 ４つの節点及び辺１３、１４、１７が存在し、かつ、辺
   １５、１６、１８が存在しないという条件を満足する部
   分グラフに対して辺１３を除去し、辺１８を追加する第
   ６の変換規則と、 ４つの節点及び辺１３、１４、１５が存在し、かつ、辺
   １６、１７、１８が存在しないという条件を満足する部
   分グラフに対して辺１４を除去し、辺１６を追加する第
   ７の変換規則と、 ４つの節点及び辺１３、１４、１６が存在し、かつ、辺
   １５、１７、１８が存在しないという条件を満足する部
   分グラフに対して辺１４を除去し、辺１５を追加する第
   ８の変換規則と、 ４つの節点及び辺１３、１４、１８が存在し、かつ、辺
   １５、１６、１７が存在しないという条件を満足する部
   分グラフに対して辺１３を除去し、辺１５を追加する第
   ９の変換規則と、 により連結グラフの整形を行い、該連結グラフが変更さ
   れたとき前記第２の過程に戻り、それ以外のときは連結
   グラフを記憶のために出力すること。 を特徴とする線図形変換方法。
2. （２）前記請求項（１）記載の第３の過程において、４
   つの節点及び辺１９、２０、２１、２３が存在し、かつ
   、辺２２、２４が存在しないという条件を満足する部分
   グラフに対して辺１９、２０を除去し、辺２２を追加す
   る第１０の変換規則と、 ４つの節点及び辺１９、２０、２２、２４が存在し、か
   つ、辺２１、２３が存在しないという条件を満足する部
   分グラフに対して辺１９、２０を除去し、辺２１を追加
   する第１１の変換規則と、 で変換することを特徴とする請求項（１）記載の線図形
   変換方法。