JPH07104955B2 - 線図形の整形方法 - Google Patents

Description

【発明の詳細な説明】 〔概要〕 屈曲点を種類分けし、対抗する屈曲点にお互いを打ち消
し合うような重みを付け、近傍における平均化処理を行
うことで細かな変動を消去し、線図形を整形する。

〔産業上の利用分野〕

本発明は、細線化処理され、分岐点や交差点を取り除い
た線図形の整形方法、特に屈曲点の抽出方式に関する。

文字、白地図、設計図面などの図形は線図形であるが、
これらを電子計算機のメモリに格納するには膨大なメモ
リ容量を必要とする。このため、ベクトル化と呼ばれる
処理によりデータ量を圧縮して格納する方法がとられ
る。これは線図形を、直線ならば端点の座標値のみで、
折線ならば端点と屈曲点の座標値のみで表現する処理で
ある。

ベクトル化処理には、細線化処理により線図形を幅１
（画素１個分の幅）の線にした後で行う場合と、原図形
に直接行う場合があるが、本発明は細線化された図形に
対して行う方法である。

細線化処理された図形では線部分の画素値は１で、周囲
は０、または線部分の画素値は０で、周囲は１である。
以下においては前者の場合のみについて説明するが、後
者の場合においても同様である。線部分を表す１の連続
性について２種類の定義があり、画像上の任意の３×３
の近傍の中心の画素の値が１である場合、上下左右４方
向の１のみが中心の１に連続していると考える４連結
と、斜め方向へも連結性を考える８連結である。例えば
第２図（ａ）は４連結の定義では細線であるが、８連結
の定義では細線ではない。第２図（ａ）を８連結で細線
化すると第２図（ｂ）あるいは第２図（ｃ）となる。以
下では連結性を８連結として説明するが、４連結の場合
も同様である。

細線における端点は、第３図に示す近傍パターンのいず
れかであり、入力画像の中でこれらのいずれかのパター
ンを持つ部分を探し、その中心の画素値として１を、そ
れ以外の場合には０を出力するような論理を組めば検出
することができる。このように近傍パターンを定義し、
そのパターンをもつ部分の中心の画素値として１または
０を、それ以外のパターンをもつ部分の中心の画素値と
して０または１を与える処理はハードウェア化が容易な
論理フィルタリングと言う処理として知られている。

同様に細線における分岐点は、第４図に示すパターン
で、交差点は第５図に示すパターンで与えられるため、
論理フィルタリングによりこれらを検出した画像を得
て、原画像と排他的論理和をとることにより、原画像か
ら分岐点と交差点を取り除き、本発明が入力する画像を
得ることができる。

〔従来の技術〕

屈曲点の検出方式としては、細線化２値画像中の線上の
各画素において、その近傍にある線上の画素との位置関
係から曲率を求め、曲率が急激に変化する画素の座標を
屈曲点とする方法がある。例えば線図形が第６図の如く
であれば、画素Ｐについて距離３の位置にある線上の画
素との関係から求めた角度θがあるイキ値以上であれば
Ｐを屈曲点とする方法である。

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

しかしこの方式ではある距離離れた画素値を参照する必
要があるため、メモリをランダム・アクセスする必要が
あり、ハードウェア化が困難であるため、処理速度が遅
い。

本発明は、ハードウェア化が容易なアルゴリズムであ
り、高速に屈曲点を検出できる。

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

本発明では屈曲点のパターンを種類分けし、点対称のパ
ターンの関係である対の屈曲点の画素にお互いを打ち消
し合うような正負の対抗する重みを付け、重み付けした
画像を、平均化することにより、直線部で近傍に現れる
ような対抗する重みをもつ点対称パターンの屈曲点同士
は互いの値が打ち消し合って検出されないようにし、曲
率が大きく変化する屈曲点のみが打ち消されずに検出さ
れるようにする。

以下図面で説明する。第７図は屈曲点のパターンであ
る。〜は135°の屈曲点で〜は90°の屈曲点で
ある。

第８図（１）、（２）は直線の線図形の例を表す。メモ
リに記憶させるため図形は正方格子上に量子化され、直
線は画素単位に見ると折線になる（第７図の屈曲点パタ
ーンとが現れている。）。第８図（１）は（２）よ
り傾斜が急で、傾斜が急なものほど１の繰り返しが短
い。

しかし第８図（１）、（２）の例においては各々の直線
の端点のみが重要であり、途中の屈曲点は意味を持たな
い。つまり第８図（１）、（２）における直線部には画
素単位に見ると多数の屈曲点が含まれているが、特に各
点が微細で多数ある場合、人間の眼には直線に見えるの
でこれらの屈曲点は検出する必要がない。両直線
（１）、（２）において途中の屈曲点は点対称パターン
関係にある１対のパターンからなっている。そこでこれ
ら途中の点対称パターン関係にある屈曲点として検出し
ないようにし、途中の直線部を省略すれば、これらの直
線は両端点の座標のみで表現することができる。

第９図は折線の例である。第９図においてはで示され
る画素を屈曲点とする折線と見るのが自然である。本発
明は第８図（１）、（２）に見られる直線上の屈曲点は
検出せず、第９図ののような屈曲点を検出するもので
ある。

第９図の折線屈曲部に現れる屈曲点を、直線上に現れ
る屈曲点と区別して検出するため、本発明では屈曲点の
パターンを種類分けし、点対称のパターンをもつ対の関
係にある屈曲点同士に正負の打ち消し合う重みを与え、
異なる種類の点対称パターンの屈曲点同士では重みを異
ならしめるようにするもので、たとえば次の如き重み付
けを行う。第７図〜の屈曲点のパターンでは中心の
画素の値として81を、〜に対しては、−81を、
に対しては162を、、に対しては−162を付ける。

第10図（１）は第８図（１）の直線に、第10図（２）は
第９図の折線に重み付けを行った結果である。第８図
（２）では左下から11と１が２個続き（第１列とす
る。）、次に右斜め上方に１段上がって11と１が２個続
く（第２列とする。）が、第10図（１）の左下端の−81
は上記第１列の右端の１に対応し（この右端の１は第７
図のパターンの中心の１に該当し、従って重みは−8
1。）、第10図（１）の次の81は上記第２列の左端の１
に対応する（この左端は第７図のパターンの中心に該
当し、従って重みは81。）。以下、同様である。

また第９図のは第７図のパターンの中心に該当し、
従って重みは162である。

さてこうして得られた画像に原画像である細線化２値画
像をマスクとして細線化２値画像の値１のあるところだ
け平均化処理を施し、第11図（１）、（２）を得る。

第11図（１）、（２）は次の平均化処理で得られるもの
である。第10図（１）の３×３の領域F1では右上端の画
素値の和は−81、残りの画素の値は０であるからF1内の
画素値の和は−81、これをF1内の画素数９で割ると−９
であり、これを第12図（１）に示すように、F1の中心P1
の画素値とする。第11図（１）の左下の−９はこのよう
にして得られる。同様に領域F2については、同領域内の
画素値の和は81−81＝０、従ってF2の中心P2の画素値は
０である。これは第11図（１）上記左下端の−９の右斜
め上方の０に該当する。このような平均化処理を、第８
図（１）で画素値が１の位置だけに行い、第８図（１）
で画素値が０の位置に０を割り付けていくと（原画像で
ある細線化２値画像でマスクすると言う意味。）、第10
図（１）から第11図（１）が得られる。また第10図
（２）の領域F3については、同領域内の画素値の和は−
81＋162−81＝０、従って第12図（２）に示すようにF3
の中心P3の画素値は０である。第11図（２）の２つの18
の中間の１行上の０はこうして得られる。以下同様にし
て平均化し、第９図でマスクすることで第10図（２）か
ら第11図（２）が得られる。このような（マスク付き）
平均化処理はハードウェア化が容易であり、現在広く用
いられている。

さらに第11図（１）、（２）に上記と同様の平均化処理
を施すことにより、第13図（１）、（２）を得る。

第13図（１）、（２）の画素の値は−２から４まで分布
しているが、そのうちその値が−２以上２以下のものに
は画素値０を、それ以外の画素には画素値１を割り付け
るような２直化処理により、真の屈曲点の画素にのみ１
が示される、第14図（１）、（２）を得る。このような
２値化処理もハードウェア化が容易で、現在広く用いら
れている。

第14図（１）、（２）に縮退化処理を施すことにより、
第15図（１）、（２）を得る。第８図（１）、第９図を
入力とした場合この処理は意味を持たないが、例えば第
16図（１）のような画像を入力とすると、第14図に相当
する画像は第16図（２）のようになり、屈曲点部分にノ
イズが生じる。縮退化処理は連続する画素値１を一点の
画素値１で代表させる処理で、やはり論理フィルタリン
グで構成できる。第16図（２）に縮退化処理を施すこと
により、第16図（３）が得られる。

第17図（１）、（２）は、第８図（１）、第９図から第
３図に示した端点のパターンを用いた論理フィルタリン
グによって端点を抽出した画像である。

第15図（１）と第17図（１）、第15図（２）と第17図
（２）の間でそれぞれORを取ることにより、第18図
（１）、（２）が得られる。即ち第８図（１）からは端
点のみが検出され、第９図からは端点と屈曲点が抽出さ
れている。

先に付けた重み、81、−81、162、−162は２回平均化処
理を施した後、値が残るように９の２乗である81を基本
となる数とし、２つの屈曲点の種類を表すためその２倍
の数を採用したことにより決定されたものである。２値
化に用いたイキ値は基本数を81としたため結果の値が直
線とみなされる部分で−２以上２以下の範囲であるため
決定される。重みとイキ値に以上に示した数の倍数を用
いても、正の数のみで扱えるようにおのおのの数に162
を加えても同様に処理できる。

また線部分の画素値を０、周囲を１で表す場合には、最
初の重み付けのパターンとして０と１を反転したものを
用い、２値化の結果に０と１が反転した結果が得られる
ようにし、縮退化処理におけるパターンとして０と１を
反転したものを用いれば良い。

平均化処理の範囲を拡張する場合には、以上と同様な考
え方で２値化のイキ値を決定すれば良い。

４連結の場合は第19図に示す屈曲点パターンを用いれば
良い。（〜と重みの対応は、８連結と同様であ
る。）また縮退化、端点検出にも４連結用のものを用い
る必要がある。

〔作用〕

このように屈曲点の種類に従って重み付けし、斜めの直
線において生じる屈曲部からの屈曲点の抽出を避け、折
線の屈曲点のみを抽出することができる。

〔実施例〕

第１図は本発明の実施例装置の構成を示す。

第１図の線図形整形回路ブロック図においてａは画像メ
モリであり、ここに第８図（１）、第９図の如き細線化
２値画像を格納する。

ｂ〜ｅは論理フィルタリング回路で、第７図〜を論
理フィルタリング回路ｂが、同〜を同ｃが、同、
を同ｄが、同、を同ｅが検出すると１を、それ以
外では０を出力する。

ｆ〜ｉは濃度変換回路であり、ｂ〜ｅの出力が１のとき
81、−81、162、−162の重みを付ける。

ｊ〜１は画素間演算回路であり、ｆ〜ｉの出力を足し合
わせた画像を作成する。処理１後は、第10図（１）、
（２）が得られる。

ｍ、ｎは平均化フィルタリング回路でこれらの出力とし
て第13図（１）、（２）を得る。

ｏは２値化回路であり、ｐは縮退化回路である。ｏとｐ
の処理結果として第15図（１）、（２）を得る。

ｑは第３図のパターンを用いた論理フィルタリングによ
る端点検出回路であり、ａの画像メモリの細線化２値画
像から端点のみを検出する。

ｒは遅延回路でｂ〜ｅからｏまでの遅延と、ｑとｒの遅
延を合わせるように、遅延時間が設定される。

ｓは画素間演算回路であり、ｏの出力とｒの出力の論理
和をとる。

ｔは画像メモリで処理結果が格納される。

この処理はパイプライン方式で実現できるため、画像メ
モリｔはなくとも良い。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば正確な
屈曲点検出が可能で、またハードウェア化が容易なため
線図形の整形を高速に行うことができる。

【図面の簡単な説明】

第１図は本発明の実施例を示すブロック図、 第２図は細線の定義を説明する図、 第３図は８連結の端点のパターン図、 第４図は８連結の分岐点のパターン図、 第５図は８連結の交差点のパターン図、 第６図は従来の方法を説明する図、 第７図は８連結の屈曲点のパターン図、 第８図は８連結の直線の例、 第９図は８連結の折線の例、 第10図は重み付けをした例、 第11図は平均化を行った例、 第12図は平均化処理の説明図、 第13図は２回目の平均化を行った例、 第14図は２値化の例、 第15図は縮退化の例、 第16図は縮退化の効果がある場合の例、 第17図は端点検出の例、 第18図は処理結果の例、 第19図は４連結の屈曲点のパターン図である。

Claims (1)

【特許請求の範囲】
1. 【請求項１】細線化２値線画像の屈曲点をパターンによ
   り種類分けして、点対称のパターン関係にある対の屈曲
   点の画素にお互いを打ち消し合うような正負の値をもつ
   対抗する重みを付け、かつ異なる種類の点対称パターン
   をもつ屈曲点の間では異なる重みを付け、 この重み付けされた画像に対して、入力である細線化２
   値画像をマスクとして注目画素の近傍における平均化処
   理を画像全体について二重に繰り返して施し、その結果
   について先の重みから屈曲点の画素のみが検出されるよ
   うに決定される閾値によって２値化し、さらにその結果
   について連続する画素値をもつ複数の画素を画素値１を
   もつ１点の画素で代表させる縮退化処理を施すことによ
   り、細線化２値画像から真の屈曲点のみを抽出すること
   を特徴とする線図形の整形方法。