JPH11134507A - 線分抽出処理方法 - Google Patents

Abstract

(57)【要約】 【課題】 本発明は、高速かつ信頼性の高い手法を提供
し、各種図面データのベクトル化や画像からの直線検出
処理後のベクトル化などに利用可能にすることを目的と
している。 【解決手段】 図形の輪郭線に位置する白画素の夫々に
ついて当該白画素に隣接する画素の状況を隣接画素テー
ブルにまとめ、当該個々の白画素からみて上・下・左・
右のいずれかの方向に存在する黒画素が連続している領
域を抽出し、当該領域が対となっている範囲から上記図
形を構成する中心線を生成するようにしている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ラスタデータか
ら、線分の交差点、分岐点、端点、屈折点等を検出し、
線分をベクトルデータに自動変換する方法であって、図
面を電子化するための自動入力用ツールや、画像から線
分特徴抽出後のベクトル化処理手法などとして利用する
線分抽出処理方法に関する。

【０００２】

【従来の技術】従来、ラスタデータに対して、線分の交
差点、分岐点などを表すパタンを順次比較し検出する手
法などがあるが、雑音や歪みなどの大きいデータの場
合、交差点付近などの局所的な部分の比較では正確な検
出が困難であった。

【０００３】

【発明が解決しようとする課題】上述で述べたように、
局所的なパタン比較では歪みや雑音に大きく影響を受
け、信頼性に欠ける。また、パタン比較をラスタデータ
全面に対して順次行っているので処理量が非常に大き
い。

【０００４】本発明は、上記問題を解決することによ
り、高速かつ信頼性の高い手法を提供し、各種図面デー
タのベクトル化や画像からの直線検出処理後のベクトル
化などに利用可能にすることを目的としている。

【０００５】

【課題を解決するための手段】線分を表す画素を追跡す
る際、軌跡を表す座標列とともに、各追跡画素の隣接画
素の情報を記録する。この隣接画素情報に基づいて、各
交差点や分岐点、端点で区切られた線分を求め、該線分
情報から各交差点や分岐点等を求める。この手法では、
ラスタデータ上の処理を線分の輪郭追跡のみとして計算
量を抑えることができた。また、交差点等の探索は、線
分の位置、傾き情報などを用いることでより安定な検出
を可能にした。

【０００６】

【発明の実施の形態】本発明は、線分を表すラスタデー
タから線分をベクトルデータとして自動認識する手法と
して利用可能である。以下は建築用平面図から線分を自
動認識する処理に適用した実施例である。

【０００７】図１は本発明の処理手順を示す。図中の符
号１は輪郭追跡処理、２は輪郭線分抽出処理、３は中心
線抽出処理、４は特徴点検出処理を表している。輪郭追
跡処理１では、線分の輪郭画素を追跡し、その座標列を
獲得するとともに、各輪郭画素に隣接する上下左右４方
向の画素に関し、白画素であるか黒画素であるかをチェ
ックし、その情報を獲得している。輪郭線分抽出処理２
では、該輪郭追跡処理１で得られた情報を基に、輪郭線
の中から線分を抽出している。

【０００８】中心線抽出処理３では、該輪郭線分抽出処
理２で求めた輪郭領域の線分から対になる線分を検出
し、両線分に挟まれた中間位置に中心線を求めている。
特徴点検出処理４では、該中心線抽出処理３で求めた中
心線情報から、交差点、分岐点などの特徴点を求めてい
る。

【０００９】輪郭追跡処理１について説明する。輪郭追
跡処理は、例えば図２に示すように、線を表す黒画素に
沿って白画素上を順に追跡する処理である。本例では画
素の追跡は８近傍（次点は隣接する８画素から選ばれ
る）で行っている。

【００１０】以下に具体例を説明する。イメージ上の線
分をベクタライズするために、イメージの輪郭点情報を
取得する。輪郭点のトレースは、白画素トレース（黒領
域との境界線の外側の白画素）とする。

【００１１】図３は外輪郭トレースの開始点と内輪郭ト
レースの開始点とを説明する図である。図において「未
トレース白点」とある点がトレースの開始点となる点で
ある。即ち、外輪郭トレースの開始点の場合において
は、白である未トレース点が見出された際に、「当該点
の上が白点でありかつ斜め右上が白点でありかつ右が黒
点であったとした場合に」当該白である未トレース点を
外輪郭トレース開始点とする。同様に、内輪郭トレース
の開始点の場合においては、白である未トレース点が見
出された際に、「当該点の上が黒でありかつ斜め左上が
白でありかつ左が白である場合に」当該白である未トレ
ース点を内輪郭トレース開始点とする。

【００１２】図４（ａ）と図４（ｂ）とは現在の着目点
からみて次のどの位置の白点にトレースを移行するか
（次トレース点の決定）を説明する図である。図４
（ａ）は、図４（ｂ）に示す「次トレース点の決定条
件」についての図の読み方を説明している。図中の「記
号の意味」は、黒四角は黒点、白四角は白点、数字つき
白丸は前トレース点、白丸は現在の着目点、菱形は白で
も黒でもよい点を図で示している。また「トレース方向
の一覧」は、現在の着目点（白丸）からみての方向を図
で示したものであり、例えば左上方向の点を「１」とし
て示している。そして「図の説明」は、着目点（白丸）
が置かれている状況の下で「次点決定条件」で表される
如きパターンが存在している場合に「次トレース点」で
表される位置「７」を次トレース点として決定し、トレ
ースをその点に移行することを表している。

【００１３】図４（ｂ）においては、前トレース点の位
置にもとづいて４つの場合分けが与えられており、夫々
の場合毎に６個のパターンが示されている。例えば、前
トレース点が「１」か「２」かの位置であったとして現
在の着目点（白丸）が置かれている状況が「上が黒で、
右上が白で、右が白で、右下と下と左下とが任意である
場合」には、図４（ａ）に示す「７」の位置に存在する
白点にトレースを移行するようにする。次トレース点
は、着目点（白丸）の周囲に存在する黒点に対して「右
回り」にみて決定されていると考えてもよい。

【００１４】イメージの左上からラスタ走査を行い、図
３に示す開始点の条件を満たす点をトレース開始点とす
る。次トレースの決定は、着目点に対して図４に示す条
件でおこなう。上記の条件に基づいて輪郭追跡し、その
際に、各追跡画素に隣接する画素情報も記録する。図５
（ａ）は線分を表す黒画素に対して、それに隣接する白
画素（Ａ，Ｂ，Ｃ，Ｄ，Ｅ... ）を図４の条件の下で追
跡したことを表す図である。図５（ａ）は図示の白画素
αから白画素βをへて白画素Ａに至ったものとしてい
る。言うまでもなく開始点に戻ったらトレースは終りと
なる。図５（ｂ）には、軌跡を表す画素Ａ，Ｂ，Ｃ，
Ｄ，Ｅの夫々に対して上下左右の４方向に隣接する画素
を表しているが、本処理ではこのように軌跡の各画素に
隣接する４方向の画素について、白／黒のどちらの画素
であるのかを記録する。その結果を図５（ｃ）に示すよ
うに、軌跡順に画素の座標と、その隣接画素情報として
隣接画素テーブルの形で格納するのである。

【００１５】輪郭線分抽出処理について説明する。輪郭
追跡処理で求めた４方向の隣接画素情報に対して以下の
処理をする。ある方向、例えば上方向の画素情報に着目
する（図６）。該画素情報を軌跡順にチェックし、黒画
素が連続している領域を抽出する。具体的にはｍ画素の
抜けは許し、ｎ画素以上黒画素が連続している領域を検
出している。本処理例ではｍ＝１、ｎ＝５として連続領
域を求めた。

【００１６】その結果、図６のＡ’〜Ｂ’までの☆マー
クの軌跡と、Ｃ’〜Ｄ’までの☆マークの軌跡が連続領
域として抽出された。この抜けを許す画素数ｍと、連続
画素数ｎに関しては、線分の歪みの程度や、線分の傾き
の最小単位が何度の図面であるのかなどの条件により、
変化させて対応する。その数値の決定方法は、サンプル
図面に対して最も適当な結果を出す値を人が判断しチュ
ーニングする方法や、線分の歪みをどの程度まで許す図
面であるのかなどの条件により、自動的に決定する方法
など、図面や適応例に応じて対応する。

【００１７】図６では上方向に黒がある所を探がす処理
を行った例を示しているが、同様に、下方向に黒がある
所、左方向に黒がある所、右方向に黒がある所の如く、
上下左右の各方向毎に処理を行った後、抽出された各領
域を重ねる。この時、他の方向の連続領域と重ならない
部分と、上と右、上と左、下と右、下と左の各方向画素
の重なる部分とをそれぞれ分離する。この結果、上、
下、左、右、上と右、上と左、下と右、下と左の８種類
の連続領域が求められる。図７の実施例では、上、下、
左、右、上＆右（上方向連続領域かつ右方向連続領
域）、下＆左の６種類の連続領域に分離されている。図
７においては、上＆左、下＆右は出現していない。

【００１８】中心線抽出処理について説明する。本処理
は図８に示すように、上記で求めた連続領域の中から対
になるもの同士を、例えば下方向連続領域と上方向連続
領域との対となっている所を見つけ、その連続領域で挟
まれた中間位置に線分候補となる中心線を求める。また
この際、線分の太さ情報も獲得する。対になる連続領域
とは線分を構成する向かい合う輪郭線のことである。こ
の対になる連続領域は、上方向の連続領域に対しては、
必ず下方向の中に存在すると考える。同様に左には右、
上と右には下と左、上と左には下と右という組み合わせ
で探索する。このように探索領域を制限することで、計
算量が減るとともに、図９で示すような分岐点や交差点
付近の中心線位置のずれる可能性の大きい部分を除外で
きる。図９においては、従来の手法によって中心線を求
めて当該中心線の交差点を求めた場合に図示「従来手
法」で示すように中心線の交差点の位置が本来の位置ｐ
よりもずれることがあったが、「本手法」で示すように
位置ずれが生じ難いことを表している。

【００１９】具体的に対となる連続領域の探索例を以下
に示す。上方向の連続領域について、その始終点リスト
を構築する。次に下方向の連続領域の始終点から下方向
の連続領域の傾きを求め、当該下方向の連続領域の始終
点それぞれから当該傾きに対して垂直方向に探索してゆ
き上方向の連続領域があるかどうかを調べる。上記の垂
直方向に探索してゆく範囲は、初めて白画素が現れるま
で、もしくは図面中の最大線分幅を基に求めた一定値以
内までとする。

【００２０】上方向の連続領域が存在した場合、当該上
方向の連続領域の始終点リストの対応する位置に下方向
の連続領域の始終点情報をあわせて登録する。また探索
開始点から探索終了位置までの距離を線分の太さ情報と
して確保しておく。上下両方向の始終点を登録したリス
トの中から例えば右方向に探してゆき、図８に示すよう
に、上方向の連続領域の始点の次に下方向の連続領域の
始点が存在するような場合には、重なる部分を見つけ
て、その中間位置に中心線を生成する。同様の処理を対
応する連続領域毎に行う。

【００２１】特徴点検出処理について説明する。本処理
では、交差点、分岐点などの特徴点を求めるために、ま
ず、先に生成した中心線を、同一特徴点を形成するもの
毎に分類している。その後で特徴点位置を確定する。具
体的な処理を、図１０に示す特徴点に関して説明する。

【００２２】中心線１の生成には軌跡Ｂを利用してい
る。そこで、端点１を生成した軌跡Ｂ上の画素から、中
心線１の輪郭ではない方向に軌跡上を「他の中心線の輪
郭となる画素」まで探索する。本例では中心線２の輪郭
となる画素が見つかるので、この時点で中心線１の端点
１と中心線２の端点２とが同一特徴点で接続することが
わかる。同様に中心線２を生成したもう一方の軌跡Ｃか
ら、中心線２が中心線３と接続することがわかる。この
処理を繰り返し、中心線１〜４により１つの特徴点が形
成されることがわかる。上記処理を全ての中心線の端点
に対して行い、全ての特徴点の接続関係を求める。

【００２３】特徴点の位置の確定方法は、端点を延長
し、最もお互いが接近する位置としたり、長い中心線の
位置から優先的に確定させる方法、水平垂直方向の線分
を優先的に考えて位置を確定する方法等、様々な方法が
考えられる。

【００２４】以下に、水平垂直方向の線分位置を優先的
に利用する例を記す。中心線のなす角度が一定許容値内
で水平／垂直であるものを選出する。その中で、同一特
徴点をもつ線分を連続する線分として判定する。連続す
る線分を判定した後、それが水平線の場合はｙ座標を、
垂直線の場合はｘ座標の平均値を新しい座標として、該
線分の座標値を修正する。この時、座標を修正する対象
となる線分は、単一線分のみで、接続する線分が２本以
上ある場合（二重線等）は、連続する線分の終了とし、
座標修正の対象から除外する。この座標値修正処理を図
１１に示す。図１１の中央の図において点線で囲った単
一線について座標修正が行われ、図１１の下方の図のよ
うにｙ座標が修正された図となる。

【００２５】次に、水平垂直線の座標修正が終了した線
分に対して、特徴点での接続処理を行う（図１２）。線
分を強制的に延長して接続させる。水平と垂直線分が存
在する特徴点では、それぞれの線分を延長した座標での
交差点位置とし、水平線分のみを延長した場合または垂
直線分のみを延長した場合は、中点の平均座標とする。
同一グループ内に、水平垂直線分と斜線とが混在する場
合（図１３）には、斜線の端点は水平垂直線分の交差点
座標とする。この時、水平垂直線分に２本以上の平行な
線が存在する場合には交差点座標が複数となるため、斜
線の端点座標は、水平垂直線分端点の平均座標とする。
また、同一グループ内に水平線または垂直線が１本だけ
存在する場合には、端点が決定されていないので斜線の
座標はその線分との交差点とする。この時当該水平線ま
たは垂直線の端点も交差点座標へ変更する。特徴点が、
斜線のみで構成されている場合（図１４）には、それぞ
れ、２本づつ組み合わせた場合の交差点座標を候補とし
て登録する。この時、線分の開き角が１８０度に近い場
合は例外として、その中点座標とする。最終的に、候補
として登録された座標の平均値を取り新たな座標とす
る。

【００２６】なお、本発明は上述の線分抽出処理方法を
実行するプログラムが記憶媒体上に格納されている当該
記憶媒体を含むものである。

【００２７】

【発明の効果】以上説明した如く、本発明によれば、図
形の輪郭を内・外から追跡してゆき、着目する白画素か
らみて上または下または右または左に存在する黒画素が
連続している連続領域を調べ、対となって存在する２つ
の連続領域の中間に中心線を生成させるようにしている
ことから、局所的な歪みや雑音の影響を受けることが少
なく、かつ交差点や分岐点などの特徴点を安定して決定
することができる。

【図面の簡単な説明】

【図１】本発明の処理フローを示す図である。

【図２】輪郭追跡を示す図である。

【図３】トレース開始点の設定を示す図である。

【図４】次トレース点の決定を示す図である。

【図５】輪郭追跡時の隣接画素データ収集を示す図であ
る。

【図６】上方向の画素を示す図である。

【図７】方向別の連続領域を示す図である。

【図８】対になる連続領域と中心線を示す図である。

【図９】従来手法との中心線比較を示す図である。

【図１０】軌跡と中心線を示す図である。

【図１１】水平垂直線分の座標修正を示す図である。

【図１２】水平垂直線分の接続を示す図である。

【図１３】水平垂直線分を含む斜線の接続を示す図であ
る。

【図１４】斜線のみの接続を示す図である。

【符号の説明】

１：輪郭追跡処理 ２：輪郭線分抽出処理 ３：中心線抽出処理 ４：特徴点検出処理

Claims (5)

【特許請求の範囲】
1. 【請求項１】 図形の輪郭を利用して当該図形を構成す
   る線分を抽出する線分抽出処理方法において、 与えられた図形の黒画素に接する白画素を追跡して、当
   該個々の白画素について当該白画素の周辺のどの画素が
   白画素でありかつどの画素が黒画素であるかを隣接画素
   テーブルとして格納し、 当該隣接画素テーブルの内容にもとづいて、上方向に存
   在している黒画素が連続している白画素群からなる上方
   向の連続領域と、下方向に存在している黒画素が連続し
   ている白画素群からなる下方向の連続領域と、左方向に
   存在している黒画素が連続している白画素群からなる左
   方向の連続領域と、右方向に存在している黒画素が連続
   している白画素群からなる右方向の連続領域とを抽出す
   るようにし、 下方向の連続領域と対になる上方向の連続領域を見出し
   て両者の中間に中心線を形成させ、かつ右方向の連続領
   域と対になる左方向の連続領域を見出して両者の中間に
   中心線を形成させるようにしたことを特徴とする線分抽
   出処理方法。
2. 【請求項２】 上記形成された夫々の中心線に関する情
   報にもとづいて、交差点および分岐点を含む特徴点を検
   出するために、 当該形成された夫々の中心線の始点座標および／または
   終点座標にもとづいて、同一の特徴点を形成するであろ
   う中心線群を個々の特徴点毎にグループにまとめ、 次いでグループにまとめられた中心線群を連結して、当
   該連結部分に夫々の特徴点が存在するものと決定するよ
   うにしたことを特徴とする請求項１記載の線分抽出処理
   方法。
3. 【請求項３】 上記中心線群を連結して特徴点を決定す
   るに当たって、当該中心線群のうちの予め定めたパター
   ンの中心線に優先順位を与え、当該優先順位を与えられ
   た中心線上の点あるいは当該中心線の延長上の点を上記
   特徴点の存在位置を決定するに当たって、他中心線にく
   らべて優先して、当該特徴点の存在位置として仮決定す
   るようにしたことを特徴とする請求項２記載の線分抽出
   処理方法。
4. 【請求項４】 上記優先順位を与えられた中心線が、水
   平垂直方向の交差線分であることを特徴とする請求項３
   記載の線分抽出処理方法。
5. 【請求項５】 図形の輪郭を利用して当該図形を構成す
   る線分を抽出する線分抽出処理方法を格納した記憶媒体
   において、 与えられた図形の黒画素に接する白画素を追跡して、当
   該個々の白画素について当該白画素の周辺のどの画素が
   白画素でありかつどの画素が黒画素であるかを隣接画素
   テーブルとして格納し、 当該隣接画素テーブルの内容にもとづいて、上方向に存
   在している黒画素が連続している白画素群からなる上方
   向の連続領域と、下方向に存在している黒画素が連続し
   ている白画素群からなる下方向の連続領域と、左方向に
   存在している黒画素が連続している白画素群からなる左
   方向の連続領域と、右方向に存在している黒画素が連続
   している白画素群からなる右方向の連続領域とを抽出す
   るようにし、 下方向の連続領域と対になる上方向の連続領域を見出し
   て両者の中間に中心線を形成させ、かつ右方向の連続領
   域と対になる左方向の連続領域を見出して両者の中間に
   中心線を形成させるようにした線分抽出処理方法が格納
   されていることを特徴とする記憶媒体。