JPH07104930B2 - 折線化処理方法 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、折線化処理方法に関し、特に、CAD（設計支
援計算機）装置等の画像処理装置において、図面データ
の点列画像データを折線データに変換して、折線化する
折線化処理方法に関するものである。

〔従来の技術〕

CAD装置において、線画図面をデジタイズして、図面デ
ータの処理を行う場合、種々の線分の混在した図面から
種々の形状を抽出し，線の図形要素への分類が行われ
る。この時の画像処理の前処理として、線画図面をスキ
ャナーで点列画像データとして入力した後に、点列画像
データを折線データに変換し、折線化する折線化処理が
行われる。そして、折線化処理により図形を折線近似し
て、図形要素の分類処理が行われる。

点列画像データを折線データに変換して、折線化する折
線化処理の一つの手法として、例えば、第６図に示すよ
うに、図形から点列画像データの画素列ｂ（ｍ）が与え
られると、この画素列ｂ（ｍ）のｉ番目とｊ番目の２つ
の着目画素ｂ（ｉ）およびｂ（ｊ）によって区切られる
区間の画素列の中で、画素ｂ（ｉ）とｂ（ｊ）を結ぶ直
線との距離ｄが最も遠く、かつ一定距離以上である画素
ｂ（ｋ）を折線構成点として抽出して折線化する手法が
ある。

〔発明が解決しようとする問題点〕

しかしながら、前述の折線化処理の手法により折線構成
点を抽出して折線化して、図形を折線近似する場合にお
いて、点列画像データである画素列の中から、折線構成
点として、最適な画素を抽出するようにしているが、デ
ジタルノイズにより画素自体の座標が変動しているた
め、図形の屈曲部において折線は変形を起こし易く、安
定な折線近似の折線データが得られていないという問題
点があった。

本発明は、前記問題点を解決するためになされたもので
ある。

本発明の目的は、画像処理装置において、折線化処理す
る場合に画像の屈曲部に対して変形の少ない折線化処理
を行う折線化処理方法を提供することにある。

〔問題点を解決するための手段〕

上記目的を達成するため、本発明においては、点列画像
データから、点列画像データ中の任意の２つの画像構成
点を着目構成点とし、該着目構成点によって区切られる
区間の画像構成点の中で、該着目構成点を結ぶ直線との
距離が最大の画像構成点で、かつ前記距離が一定距離以
上である画像構成点を仮折線構成点として抽出して仮折
線化し、仮折線化して得られた仮折線構成点のデータ中
の隣り合う２つの仮折線構成点で区切られる区間を着目
区間とし、着目区間の中の点列画像データの画像構成点
の数が第１の所定数と第２の所定数の和の２倍以上の一
定数以上である場合、着目区間の端部のそれぞれの仮折
線構成点について仮折線構成点から区間内側方向に第１
の所定数の画像構成点だけ離れた位置から第２の所定数
の画像構成点を抽出して、該第２の所定数の画像構成点
の平均座標値を求め、それぞれの平均座標値を結ぶ直線
を区間の最適直線データとし、着目区間の中の点列画像
データの画像構成点の数が前記一定数未満である場合、
着目区間端部の仮折線構成点を結ぶ直線を区間の最適直
線データとして、隣り合う最適直線データの交わる点を
折線構成点として折線化する。

〔作用〕

前記手段によれば、点列画像データから、まず、仮折線
構成点を抽出して、点列画像データを仮折線化する。こ
の仮折線構成点は、点列画像データ中の任意の２つの画
像構成点を着目構成点とし、該着目構成点によって区切
られる区間の画像構成点の中で、該着目構成点を結ぶ直
線との距離が最大の画像構成点で、かつ前記距離が一定
距離以上である画像構成点を仮折線構成点として抽出す
る。これにより、仮折線構成点の付近に真に最適な折線
構成点があることが分かる。

次に、最適な折線構成点を決定するため、前記仮折線構
成点のデータ中の隣り合う２つの仮折線構成点で区切ら
れる区間を着目区間とし、着目区間の中の点列画像デー
タの画像構成点の数を調べ、画像構成点の数が十分多い
場合、つまり、着目区間が１本の直線として整形できる
場合に、これを着目区間の中の点列画像データの画像構
成点の数が第１の所定数と第２の所定数の和の２倍以上
の一定数以上であることにより判定して、この場合、着
目区間の端部のそれぞれの仮折線構成点について仮折線
構成点から区間内側方向に第１の所定数の画像構成点だ
け離れた位置から第２の所定数の画像構成点を抽出し
て、該第２の所定数の画像構成点の平均座標値を求め、
それぞれの平均座標値を結ぶ直線を区間の最適直線デー
タとする。着目区間の中の点列画像データの画像構成点
の数が一定数未満である場合、着目区間端部の仮折線構
成点を結ぶ直線を区間の最適直線データとする。そし
て、この最適直線データから隣り合う最適直線データを
延長して交わる点を折線構成点として折線化する。

これにより、この折線構成点は、点列画像データの中の
画像構成点で最もデジタルノイズの影響を受け易い屈曲
部の仮折線構成点付近を避け、仮折線構成点で区切られ
る区間の最適直線を求め、それぞれの最適直線データを
延長して、隣り合う２区間の最適直線が交わる点を折線
構成点としているので、図形を折線近似するため折線化
処理する場合、図形の屈曲部でのデジタルノイズによる
変形が少ない折線近似ができる。

〔実施例〕

以下、本発明の一実施例を図面を用いて具体的に説明す
る。

第１図は、本発明の一実施例にかかる画像処理装置の構
成を示すブロック図である。この画像処理装置は、画像
を入力する画像入力装置10、各種の処理を実行する中央
処理装置20、中央処理装置20での処理に必要なプログラ
ムを格納するプログラムメモリ30、画像入力装置10から
入力する画像データの点列画像データ41を格納する画像
メモリ40、仮折線データ51と区間最適直線データ52およ
び折線データ53を格納するデータメモリ50,折線データ5
3を表示するための表示装置60から構成されている。

プログラムメモリ30には、点列画像データ41を仮折線化
するための仮折線化プログラム31と、仮折線データ51か
ら仮折線データの線分区間の区間最適直線データ52を求
め、折線データ53を得るための折線化プログラム32が格
納されている。中央処理装置20は、プログラムメモリ30
の仮折線化プログラム31に基いて画像メモリ40の点列画
像データメモリ41を処理し、データメモリ50に仮折線デ
ータ51を格納する。次に、中央処理装置20は、プログラ
ムメモリ30の折線化プログラム32に基いて画像メモリ40
の点列画像データ41とデータメモリ50の仮折線データ51
から仮折線構成点で区切られる区間毎に最適直線データ
52を求め、該最適直線データ52から折線データ53を求め
てデータメモリ50に格納する。そして、中央処理装置20
は、表示装置60に処理結果の折線データ53を表示する。

第２図は、仮折線化処理の処理フローを示すフローチャ
ートである。また、第３図は、仮折線化処理の動作を説
明するための説明図である。まず、第３図を参照しつ
つ、第２図に従って、仮折線処理を説明する。

いま、画像メモリ40に点列画素の点列画像データ41があ
るものとする。中央処理装置20では画像メモリ40から点
列画像データ41を読込み、仮折線化の処理を行う。ま
ず、ステップ101において、点列画素の点列画像データ
を読込み、次にステップ102で、点列画像データを適当
な区間に分割して分割区間を構成する。各々の分割区間
に対して、以下のステップ103からの処理で仮折線化の
処理を行う。

ステップ103で、処理すべき分割区間（例えば、第３図
においては、区間分割点S1と区間分割点S2で分割される
分割区間）と、その間の画像構成点を得て、次にステッ
プ104において、画像構成点の内、分割区間の両端点の
間を結ぶ直線に対して最も距離のある点Ｐと、この直線
と点Ｐとの距離ｄを求める（例えば、第３図において
は、点P1と距離d1とを求める）。次にステップ105に進
み、ステップ104で求めた距離ｄが一定距離ε以上であ
るか否かを判定する。この距離ｄが一定距離ε以上であ
る場合、ステップ106に進み、点Ｐを仮折線構成点とし
て格納する。そして、次にステップ107で、点Ｐにより
当該分割区間を更に２つの分割区間に分ける。そして、
ステップ103に戻り、分けた各々の分割区間に対して
も、ステップ103からの仮折線化の処理を繰返し行い、
仮折線構成点を抽出して格納する（例えば、第３図にお
いては、点P1と距離d1,点P2と距離d2,点P3と距離d3を順
次に求め、点P1,点P2,点P3を仮折線構成点として抽出し
て格納する）。一方、ステップ105において、距離ｄが
一定距離ε未満である場合には、点Ｐを仮折線構成点と
はしないので、ステップ108に進み、ステップ108で全て
の分割区間について仮折線化の処理が終了したか否か判
定する。仮折線化の処理（仮折線構成点の抽出の処理）
が行われていない分割区間が残っている場合には、ステ
ップ103に戻り、この仮折線化の処理を繰り返し行う。
一方、全ての分割区間について仮折線化が終了している
場合、ステップ109に進み、ステップ102において最初に
点列画像データを適当な区間に分割した際の区間分割点
（例えば、第３図では、点S1,点S2,点S3,・・・）が、
仮折線構成点であるか否かの判定処理を行う。

ステップ109においては、区間分割点とその前後点を読
み込む（例えば、第３図において、区間分割点S2と、そ
の前点P1および後点P4とを読み込む）。次にステップ11
0で、前後点を結ぶ直線と区間分割点との距離ｄを求め
る（例えば、第３図において、区間分割点S2と直線との
距離m1を求める）。次にステップ111において、求めた
距離ｄが前記一定距離ε以上であるか否か判定する。距
離ｄが一定距離ε以上である場合には、ステップ112に
進み、当該区間分割点（例えば点S2）を仮折線構成点と
して格納して、ステップ113に進む。一方、ステップ111
で、距離ｄが一定距離ε未満である場合、当該区間分割
点は仮折線構成点とせず、ステップ113に進み、全ての
区間分割点について仮折線構成点の判定が終了したか否
かを判定する。仮折線構成点の判定の行われていない区
間分割点が残っている場合、ステップ109に戻って、こ
の仮折線構成点の判定の処理を繰り返し行う。一方、全
ての区間分割点について仮折線構成点の判定が終了して
いる場合、仮折線化処理を終了する。

なお、ステップ102の点列画像データを適当な区間に分
割する処理において、点列画像データの端点は、当然に
区間分割点となっており、しかも仮折線構成点となって
いるので、ステップ102〜ステップ113の仮折線構成点の
判定の処理を行うまでもなく、例えばステップ102にお
いて、端点は折線構成点として格納する。

このようにして、画像メモリ40の点列画像データ41に対
して、仮折線化プログラム31により仮折線化処理を行
い、仮折線データ51を生成して、データメモリ50に格納
する。

次に、このようにして求めた仮折線データ51から折線化
プログラム32により折線データ53を生成する処理を行
う。

第４図は、仮折線データから折線データを求める処理の
処理フローを示すフローチャートである。また、第５図
は、仮折線から折線を求める処理の動作を説明するため
の説明図である。第５図を参照しつつ、第４図に従って
折線化処理を説明する。

画像メモリ40には点列画像データ41があり、データメモ
リ50には、仮折線化プログラム31により仮折線化処理を
行い生成された仮折線データ51が格納されている。中央
処理装置20は、画像メモリ40の点列画像データ41とデー
タメモリ50の仮折線データ51を読込み、折線化の処理を
行う。まず、ステップ201において、仮折線構成点で区
切られる点列画像データのｉ番目の区間に着目し、その
着目する区間ｉに対応する２つの仮折線構成点P1,P2を
取り出す。この着目区間に対して、ステップ202で、区
間ｉ内にある点列画像データの画像構成点の数が一定数
以上であるか否かを判定する。この一定数は、後述する
ように、着目区間が１本の直線として整形できる場合の
判定のための基準を与える。つまり、この一定数が、着
目区間の中の点列画像データの画像構成点の数が第１の
所定数ｎと第２の所定数ｍの和の２倍以上の十分に多い
数であることを判定することにより、着目区間が１本の
直線として整形できる場合の条件を満たすことを保証す
る。

そして、この画像構成点の数が一定数以上である場合
に、ステップ203に進み、区間ｉに対応する２つの仮折
線構成点P1,P2の各々について、区間ｉの内側方向にｎ
個（第１の所定数）だけ画像構成点を進めた点からｍ個
（第２の所定数）の点列の画像構成点Si（１）〜Si
（ｍ）およびEi（１）〜Ei（ｍ）を、この区間ｉの最適
直線liを得るデータのサンプルとして抽出する。そし
て、ステップ204で、点列画像データの画像構成点Si
（１）〜Si（ｍ）およびEi（１）〜Ei（ｍ）の座標値か
ら、その平均座標SiおよびEiを求め、次のステップ205
で、平均座標SiおよびEiを通る直線liを求め、区間ｉの
最適直線データとして、データメモリ50に格納する。次
にステップ207に進み、処理対象の区間ｉを次の区間ｉ
＋１に更新する。

一方、ステップ202において、区間ｉ内にある点列画像
データの画像構成点の数が前記一定数未満である場合、
ステップ206に進み、２つの仮折線構成点を通る直線li
を求め、この直線データを区間ｉの最適直線データとし
て、データメモリ50に格納する。そしてステップ207
で、処理対象の区間ｉを次の区間ｉ＋１に更新する。

次に、ステップ208で区間最適直線を求めていない区間
があるか否かを判定する。区間最適直線を求めていない
区間があれば、ステップ201に戻り、区間最適直線を求
めていない区間について、ステップ201からの区間最適
直線を求める処理を繰返し行う。一方、全ての区間につ
いて区間最適直線が求められている場合には、ステップ
209に進む。ステップ209では、データメモリ50に格納し
た区間最適直線データ52から隣り合う２つの区間の区間
最適直線liおよびli＋１を取り出し、次のステップ210
で、取り出した区間最適直線liおよびli＋１の交点Piを
求めて、折線構成点としてデータメモリ50に格納する。
次に、ステップ211において、全ての隣り合う区間に対
応して折線構成点を求めたか否かを判定する。求めてい
ない折線構成点がある場合、ステップ209に戻って、ス
テップ209,ステップ210の処理を行い、折線構成点を求
めていない隣り合う区間に対応する折線構成点を求める
処理を繰返す。一方、全ての隣り合う区間に対応する折
線構成点が求められた場合、折線化処理を終了する。

以上、説明したように、この実施例によれば、点列画像
データ41と仮折線データ51を用いて、隣り合う２つの仮
折線構成点で区切られる区間内の画像構成点のサンプル
データから、その区間の画像構成点の点列画像が示す方
向の直線を区間最適直線として求めた後、隣り合う２つ
の区間最適直線の交点を折線構成点とする。このような
処理により、図形を折線近似する折線データを求めるの
で、図形の屈曲部においてデジタルノイズによる変形が
少ない折線近似ができる。

以上、本発明を実施例にもとづき具体的に説明したが、
本発明は、前記実施例に限定されるものではなく、その
要旨を逸脱しない範囲において種々変更可能であること
は言うまでもない。

〔発明の効果〕

以上、説明したように、本発明によれば、画像処理装置
において、点列画像データを折線化処理する場合、通常
の折線化処理で求めた折線構成点を仮折線構成点とし、
隣り合う２つの仮折線構成点で区切られる区間毎に区間
内の画像構成点の点列画像の点列が示す方向の直線を区
間最適直線として求めた後、隣り合う２つの区間最適直
線の交点を折線構成点とするため、図形の屈曲部におい
てデジタルノイズによる変形が少ない折線近似が行える
という効果がある。

【図面の簡単な説明】

第１図は、本発明の一実施例にかかる画像処理装置の構
成を示すブロック図、 第２図は、仮折線化処理の処理フローを示すフローチャ
ート、 第３図は、仮折線化処理の動作を説明するための説明
図、 第４図は、仮折線データから折線を求める折線化処理の
処理フローを示すフローチャート、 第５図は、仮折線データから折線を求める処理の動作を
説明するための説明図、 第６図は、従来における画素列から折線を求める折線化
処理の例を説明するための説明図である。 図中、10……画像入力装置、20……中央処理装置、30…
…プログラムメモリ、40……画像メモリ、50……データ
メモリ、60……表示装置。

Claims (1)

【特許請求の範囲】
1. 【請求項１】画像を入力する手段と、点列画像データを
   格納する手段と、仮折線データを格納する手段と、区間
   最適直線データを格納する手段と、折線データを格納す
   る手段を備えた画像処理装置において、 点列画像データから、点列画像データの中の任意の２つ
   の画像構成点を着目構成点とし、該着目構成点によって
   区切られる区間の画像構成点の中で、該着目構成点を結
   ぶ直線との距離が最大の画像構成点で、かつ前記距離が
   一定距離以上である画像構成点を仮折線構成点として抽
   出して仮折線化し、 仮折線化して得られた仮折線構成点のデータ中の隣り合
   う２つの仮折線構成点で区切られる区間を着目区間と
   し、着目区間の中の点列画像データの画像構成点の数が
   第１の所定数と第２の所定数の和の２倍以上の一定数以
   上である場合、着目区間の端部のそれぞれの仮折線構成
   点について仮折線構成点から区間内側方向に第１の所定
   数の画像構成点だけ離れた位置から第２の所定数の画像
   構成点を抽出して、該第２の所定数の画像構成点の平均
   座標値を求め、それぞれの平均座標値を結ぶ直線を区間
   の最適直線データとし、 着目区間の中の点列画像データの画像構成点の数が前記
   一定数未満である場合、着目区間端部の仮折線構成点を
   結ぶ直線を区間の最適直線データとし、隣り合う最適直
   線データを延長して交わる点を折線構成点として折線化
   することを特徴とする折線化処理方法。