JPS61208172A - 多角形内部領域塗漬装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔目次〕 概要 産業上の利用分野 従来の技術 発明が解決しようとする問題点 問題点を解決するための手段　（第１図）作用 実施例 （ａ）本発明の一実施例構成　（第２図〜第５図）偽）
本発明の動作　　　　　（第２図〜第７図）発明の効果 〔概要〕 本発明は、例えば屈曲点データより復元した、多角形の
輪郭線上に多角形の内部と外部が変化することを示す判
別点を定義して、その点を元に多角形の内部を塗潰すこ
とにより、比較的高速でかつ正確にパターンを塗潰すも
のである。

〔産業上の利用分野〕

本発明は図形処理装置に係り、特に屈曲点のリストとし
て与えられた多角形の内部を正確に塗潰す装置に関する
。

文字や図形のパターン情報をオリジナルな状態でメモリ
に保持することは情報量が大きく、したがって大容量の
メモリが必要となるので好ましくない。したがってこれ
を圧縮して保持することが行われている。

パターン情報の圧縮方式として、本特許出願人は屈曲点
のリストによりその輪郭情報を保持する方式を提案して
いる。これによればパターンの輪郭を多角形として復元
できるもののその内部を塗潰すことが必要になる。

多角形の内部を塗潰す必要性は、前記屈曲点リストによ
り復元されるもののみでなく、例えば折線情報としてパ
ターンを保持する場合でも必要である。

〔従来の技術〕

多角形の内部を塗潰す塗潰方式としては、種まき法、エ
ツジ・リスト法、エツジ・フラグ法等が行われている。

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

種まき法は、第８図（ａ）に示す如く、パターン内の一
定をとりこれより例えば水平方向および垂直方向に内部
を走査し、次にこの走査線を中心として垂直方向または
水平方向に内部を走査することを繰返す方法である。こ
の方法では種をまくためのデータがあらかじめ必要とな
る。また凹凸が多い複雑なものについてはこのようなと
ころまで正確に塗潰すために複雑な制御が必要となり効
率が悪い。

エツジ・リスト法は第８図（ｂｌに示す如く、パターン
を走査してそのパターンの輪郭を検出してどこからどこ
までがパターンの内であり、外であるのかという判断を
することが必要であるが、これが非常に複雑であり、そ
のため処理が繁雑である。

またエツジ・フラグ法は正確さに欠けるという問題点が
ある。

本発明の目的はこのような問題点を解決するため、多角
形の内部を、比較的高速でかつ正確に塗潰すことができ
る多角形内部領域塗潰装置を提供することである。

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

前記目的を達成するため、本発明では、第１図に示す如
く、例えば屈曲点情報により復元し、２次元のｘｙＸ座
標与えられた輪郭線上に、多角形の内部と外部とが変化
することを示す判別点（第１図の斜線パターン）を定義
し、この判別点間をｘ印の如く塗潰すものである。第１
図において輪郭線をパターンＰ１〜Ｐ１５で表わすとき
、各パターンの隣接点のＹ座標が異なるときこれを判別
点とする。また隣接点が水平方向に連続しているとき、
これを１つのグループとしてそのグループの両端に隣接
する各パターンの隣接点のＹ座標が異なるとき、このグ
ループの任意の１つ、例えばそのＸ座標の最小のものを
判別点とする。これにより、第１図の場合、斜線パター
ンＰ１、ＰＳ、Ｐ７、Ｐｕｓが判別点として定義され、
この間をＸ印の如く塗潰せば原パターンが復元できる。

ここでＰ１〜Ｐ３は水平方向に連続しているので１つの
グループとし、その両端の隣接パターンＰ１５とＰ４の
Ｙ座標が異なるのでＰ１〜Ｐ３のうちＸ座標の最小のＰ
ｌを判別点とする。Ｐ４はその両側の隣接点Ｐ３、ＰＳ
が同−Ｙ座標であるので判別点ではない。ＰＳ、Ｐ６は
１つのグループとなりその両側の隣接点Ｐ４、Ｐ７のＹ
座標が異なるのでＰＳを判別点とする。Ｐ７はその両側
の隣接点Ｐ６、ＰδのＹ座標が異なるので判別点となる
。またＰ８〜Ｐ１４はその両端のＰ７、Ｐ＋５のＹ座標
が同一のため判別点は存在しない。Ｐｌ５はその隣接点
Ｐ１、Ｐ、４のＹ座標が異なるため判別点と定義される
。

〔作用〕

判別点を簡単に判定できるのみならず、多角形の内部を
高速かつ正確に塗潰すことができる。

〔実施例〕

本発明の一実施例を第２図〜第６図にもとづき説明する
。

（ａ１本発明の一実施例構成 第２図は本発明の一実施例構成図、第３図はその輪郭復
元部の動作説明図、第４図は判別点の定義、第５図は本
発明の詳細な説明図、第６図は判別点定義部の動作説明
図、第７図は塗潰部の動作説明図である。

第２図において１は屈曲点データ保持部、２は輪郭復元
部、３は判別点定義部、４は塗潰部、５は多角形データ
出力部である。

屈曲点データ保持部１は原パターンの輪郭を復元するた
めにその屈曲点データを保持するものである。

輪郭復元部２は与えられた屈曲点データに基づき隣接す
る屈曲点間に直線を発生させ、これにより多角形の原バ
ター゛ンを復元させるものである。

この直線発生手段は周知のものが使用できるが、−例と
してＤＤＡ　（Ｄｉｇｉｔａｌ　Ｄｉｆｆｅｒｅｎｔｉ
ａｌ　Ａｎａｌｙｚｅｒ　　：デイジタル微分解析機）
を使用する例について第３図により説明する。第３図（
ａｌに示す如く、Ｐ、（Ｘｌ、Ｙ＋）とＲ２（Ｘ２、Ｙ
２）間に直線を引くとき、第１ステツプとして、始点を
（Ｘｌ、Ｙ＋）にプロットし、この直線の角度をφとす
るとき、係数０１　＝ｃｏｓ　φ、係数Ｇｚ−ｓｉｎφ
を求めスタート点（Ｘ、Ｙ）の座標をｘ＝ｘ　１、Ｙ＝
Ｙ　１にセットする。そして初期値としてＸ座標レジス
タＲ１、Ｙ座標レジスタＲ２に次のデータを記入する。

Ｒ１＝　Ｘ　１＋　０．５−−−−−−−（ｔ）Ｒｚ　
＝　Ｙ　１＋０．５−−−−−−−＜２）第２ステツプ
としてＸ座標レジスタＲ１の値に前記ｃｏｓ　φを加え
、Ｙ座標レジスタＲ２の値に前記ｓｉｎφを加える。こ
れは第３図においてスタート点Ｐ１よりＲ２の方に単位
長ａだけ直線を引いたときのＸ座標およびＸ座標を示す
、ところでメモリにセットされるデータは通常整数単位
であるので、前記加算後の値の整数部分１１、Ｉ２だけ
を取り出す。なお第４図の第２ステツプでｉｎｔ　　（
Ｒｔ）はレジスタＲ１より整数部分のみを取り出すこと
を示し、ｉｎｔ　　（Ｒ２）はレジスタＲ２より整数部
分のみを取り出すことを示す。ここでｉｎｔは小数点以
下を切り捨てる関数を示す、・第３ステツプとして、前
記第２ステツプで得た整数１１が第１ステツプのＸｌと
異なるか、または整数Ｉ２が第１ステツプのＹｌと異な
るときにはＸ−１１、Ｙ−Ｉ２としてこれらを（Ｘ、Ｙ
）にプロットする。このようなことをＸ−Ｘｚ、Ｙ＝Ｙ
２になるまで繰返す。このようにして、第３図にＯ印で
示す如きＰｌ、２２間の直線のデータが得られる。

判別点定義部３は輪郭線部分が判別点か否かを判定して
これを輪郭線上に定義するものである。

ここで判別点とは多角形の内部と外部とが変化すること
を示すものであり、その定義を第４図面の簡単な説明す
る。

第１ステツプとして復元した輪郭線を追跡し、Ｙ座標が
等しい連続する点列（水平部）を選出する。例えば第４
図（ａ）において、輪郭線Ｐ１〜Ｐ６をたどり、Ｐ２〜
Ｐ５の水平点列を選出する。第２ステツプとして、水平
部に連続する前後の点のＹ座標が異なる場合、水平部の
一点を判別点とする。等しい場合は判別点としない。例
えば第４図（ａ）では、水平部Ｐ２〜Ｐ５に連続する前
後の点Ｐ１、Ｒ６のＹ座標が異なるので水平部Ｐ２〜Ｐ
５の一点を判別点として黒丸で定義する。この場合には
、水平部Ｐ２〜Ｐ５のＸ座標の小さい左端の点を判別点
としたものであるが、判別点はＲ２に限定されるもので
はない。しかし第４図（ｂｌでは水平部Ｐ２〜Ｐｓに連
結する前後の点のＹ座標が同一のため、Ｐ２〜Ｐ５に判
別点は存在しない。なお水平部とは複数の点で構成され
るものに限らず１つの点でも水平部である。なお第４図
（Ｃ）では点Ｐ２が判別点であるが、第４図（ｄｌの点
Ｐ２は判別点ではない。

また判別点は排他的論理和で定義する。つまり、第４図
（６１で説明するように判別点にすべき点が既に判別点
の場合はその点を判別点から普通の点に戻す。例えば第
４図（ｅ）において点Ｐ２を判定するとき、まず上向き
矢印によりＰｌの前後の点Ｐ１、Ｐ３のＹ座標を比較し
てこのＰｌを判別点と定義する。次に下向きの矢印によ
りＰｌの前後の点Ｐ４、ＰｌのＹ座標を比較してこのＰ
ｌを判別点と定義するが、このときＰｌは先の上向き矢
印のルートで判別点と定義されているので、前記の論理
にもとづきこれを普通の点に戻す。第４図、第５図にお
けるΔ印は一度判別点と定義されたものが再度判別点と
定義されることにより普通の点に戻った点を示している
。なお、第４図（８）においてＰｌはＰｌとともに直線
部を形成しその頂点であるが、この直線状の頂点のとき
にはＰｌをＰｌの前後の点として処理するのでＰｌは判
別点ではない。

塗潰部４は前記判別点定義部３で定義された輪郭線上の
判別点間を塗潰すための処理を行うものである。例えば
第５図（ａ）の如き、多角形の輪郭線が存在し、これに
より同ｃｂ＞の黒丸に示す判別点が定義されたとき、同
（Ｃ）の二重光に示す如く判別点間を塗潰し、原パター
ンを復元させるものである。

多角形データ出力部５は、第５図（Ｃ）に示す如き塗潰
された復元パターンを保持し、必要に応じてこれを出力
するものである。

（ｂ１本発明の動作 本発明は■輪郭線の復元処理、■判別点処理、■塗潰処
理という３つの技術を主にしている。

イ、このうち■については前記（ａ）の輪郭復元部２に
ついて第３図にもとづき説明したので省略し、■、■に
って説明し、その後に全体の動作について説明する。

■０判別点処理 この判別点処理は判別点定義部３において行われるもの
であり、これについて第６図のフローチャートにより説
明する。ここで多角形の塗潰を行うメモリの横方向をＸ
軸、縦方向をＹ軸とし、メモリには初期値として零があ
たえられているとする。そしてメモリ内の点（ＸｉＳＹ
ｉ）の値をＭ（Ｘｉ、Ｙｉ）と表現し、メモリ上で輪郭
線上の判別点を２、普通の点を１で表わす処理を行う。

また輪郭線の復元によってできた点列を（Ｐｌ、Ｐ　２
−Ｐ　ｎ　）点Ｐｉの座標を（Ｘｉ、Ｙｉ）とする。

■まず、水平部の始まりを見つける必要があるがメモリ
中の輪郭線パターンの１つ、例えば第１図のＰｌを抽出
し、これをｉｍｎ＋ｌとお（。なお、スタート点はどこ
でもよいが、ここでは輪郭線の始点Ｐ１をスタート点と
している。もし１番目の点をスタート点とするならばｉ
−ｎ＋１をｉ−ｊとし、Ｙ　ｉ　＋Ｙ　１をＹｉｙ＆Ｙ
ｊにする必要がある。ここでｎは輪郭線の点列の個数で
あり、第°１図の例ではｎ＝１５である。尚このｎは輪
郭復元の際に発生した点の数を数えることにより求めら
れる。

■次にパターンを逆方向に１つバックして追跡し、その
とき、１＝ｉ−１（有頂のｉは■によりｎ＋１であり、
結局これはｎ＋１−１−ｎ）となる。このときのパター
ンＰｉのＹ座標Ｙｉと■のパターンのＹ座標を比較する
。この場合ＰｉはＰｌ５でありＹｌ＋ｙｌのためｙｅｓ
のルートへ行きｉ−ｎ＋１つまり最初のパターンにもど
る。尚、Ｙｌとは始点Ｐ１のＹ座標である。このときｉ
はｎ＋１のためｉ＞ｎとなり、したがって最初のパター
ンＰ１がスタート点となる。もしＹ　ｉ　＝　Ｙ　１な
らばつまりＹ座標が同一であれば、ｎｏのルートにより
更に１つパターンをバックしてさかのぼりそのＹ座標を
比較する。このようにしてＹｉΦＹ１の点つまり水平部
分の端点を検出する。そしてこれを水平部分の始点ｉと
し、ポインタＰにＰ＝ｉとして設定する。

■この水平部分の始点ＰをポインタＫに設定する。

■ポインタＫに設定された水平部分の始点を−１したｂ
−に−１を設定する。もしｂが１より小さいとき、この
ｂ−ｎとおく。これが水平部分の１つ前のパターンとな
る。

■ところで輪郭線のパターンの値Ｍ（Ｘｐ、、Ｙｐ）は
最初０でありこれが判別点ならばＭ（ＸｐＳＹｐ）＝２
、判別点でなければＭ　（Ｘｐ、　Ｙｐ）−１とする処
理を第６図右側のフローで行う。

つまりメモリに輪郭パターンを書き込む。最初は輪郭線
のパターンの値Ｍ−０であるので、これを１とする。こ
のようにして Ｍ　（Ｘｐ、、Ｙｐ）＝１となる。

０次に輪郭線を１つ順方向にたどりｐ＝１からｐ＝２つ
まりＰｌをチェックする。このとき２〉１５ではないの
でＰｌのＹ座標と前記■で保持されたＰｋつまりＰｌの
Ｙ座標が比較されるが両者は同一なのでＹｐ！ｖＹｋは
ｎｏとなり、前記■にもどりＰｌに１が記入される。こ
のようにしてＰ３についても１が記入される。

■ところでＰ４ではＹｐ’１−Ｙｋとなる。このときこ
のＰ４のＹ座標Ｙｐと前記■のｂ−に−１つまりＰｌ５
のＹ座標Ｙｂとは、Ｙｐ〜ｐｂでありしかも前記■のに
−ＰつまりＰｌの点のＭは前記■によりＭ−１であるが
今度は２となり、判別点として定義される。

■このような処理が輪郭線にそって順次進められ、ｐ−
ｔつまり始点に戻るまで行われる。これにより第１図の
ような輪郭線では斜線部分がＭ−２、白丸部分がＭ＝１
と記入されることになる。

■、塗塗潰処理 この塗潰処理は、塗潰部４において行われるものである
。これを第７図のフローチャートにより説明する。ここ
で輪郭線の格納されているメモリの大きさをＳＸＳとす
る。

■メモリのＹ座標の値Ｙを１に設定する。そしてパター
ンの内部、外部を示すフラグＦを零に初期設定する。つ
まりＦ＝Ｏの場合、外部を示し、Ｆ＝１の場合内部を示
す。それからＸ座標の値Ｘを１に設定する。このように
して指定された座標（１，１）の前記Ｍ値が２か否かを
チェックする。

Ｍ＝２でなければＦ−１か否かをチェックするが、最初
はＦ＝０なのでＸ座標を＋１して右方向にチェックポイ
ントを移動する。この移動点がメモリ領域Ｓ内ならばそ
の移動点のＭ−２か否か、またＦ＝１か否かをチェック
する。いずれもｎｏならば更にＸ座標を＋１して同様の
チェックを行う。

このようにして同−Ｙ軸上を順次水平方向に走査する。

■このようにして第７図（ｂ）における輪郭線ＰのＰＱ
に到達したとき、これが判別点つまりＭ＝２であり、そ
れまでのフラグがＦ＝０であれば、つまり輪郭線の外側
から到達した場合であればフラグをＦ−１−ＦつまりＦ
−１とする。そしてＸ座標を＋１する。これがまた前記
Ｓを越えずメモリ領域内のとき、その移動先のＭ値をチ
ェックしＭ−２でなく、しかもＦ−１のとき（つまりＰ
Ｑから右側の場合フラグはＦ＝１である）そのＭ値をＭ
＝１とする。このようにして判別点ＰＲまではＦ＝１．
Ｍ＝１となる。

■しかしＸが順次＋１されて判別点ＰＲに達してＭ−２
を検出したとき、Ｆ＝　１−Ｆ、つまりこのときＦ−１
のためＦ＝Ｏにセットする。つまりＰＱからＰＲが塗ら
れることになる。

■さらにＸを＋１してゆきＸ＝Ｘ＋　１のイ直がＳを越
えたとき、Ｙを＋１して、次はＹ＝２の座標について前
記処理を行う。そしてこのような処理をＹ＋１がＳを越
えるまで行うことになる。このようにして輪郭線内の空
間は、第１図にＸ印で示す如く塗潰すことができる。

口、次に本発明の全体の動作を第２図により説明する。

■図示省略したＴＶカメラの如き画像入力部より入力さ
れた例えば文字パターン、又は図形パターンより本出願
人が別出願で提案した手法により得た屈曲点データが屈
曲点データ保持部１に保持されているので、これを順次
出力する。

■輪郭復元部２は前記屈曲点データ保持部１から順次送
出される屈曲点データにもとづきその屈曲点間の直線を
出力する。これにより原パターンの多角形の輪郭が復元
される。

■判別点定義部３は、前記輪郭復元部２により復元され
た多角形を、前記ｌにより輪郭線のうち判別点を定義す
る。

■これにもとづき、塗潰部４は前記■によりパターン内
部を正確に塗潰し、原パターンの多角形が復元される。

■このようにして復元された多角形が多角形データ出力
部５から出力される。

なお前記説明では屈曲点データにより多角形を［元した
例について説明したが、勿論本発明はこれのみに限定さ
れるものではなく、ベクトル情報により復元した多角形
の内部を塗潰すこともできる。ただしベクトルが原パタ
ーンの輪郭線の順番を保存していることが必要である。

〔発明の効果〕

本発明によれば輪郭線を多角形で復元したものを、この
輪郭線上に多角形の内部と外部が変化することを示す判
別点を定義し、この判別点にもとづき多角形の内部を塗
潰すようにしたので、その内部を比較的高速に、しかも
正確に塗潰すことができる。

これにより屈曲点のリストで与えられた多角形の内部を
高速にかつ正確に塗潰すことができるので、パターンを
輪郭線のデータだけから復元することが可能となり、パ
ターンの情報量を圧縮するのに役立つものとなる。

【図面の簡単な説明】

第１図は本発明の詳細な説明図、 第２図は本発明の一実施例構成図、 第３図は輪郭復元部の動作説明図、 第４図は判別点の定義説明図、 第５図は塗潰状態説明図、 第６図は判別点定義部の動作説明図、 第７図は塗潰部の動作説明図、 第８図は従来の塗潰方法説明図である。 図中、１・−屈曲点データ保持部 ２−・輪郭復元部 ３−判別点定義部 ４−・−塗潰部 ５・−・多角形データ出力部

Claims (1)

1. 【特許請求の範囲】 　２次元のＸＹ座標で与えられた図形の輪郭線の各点を
   順々に追跡してＹ座標が等しい連続する点列を選出し、
   該選出された点列に追跡順が隣接する両側の点のＹ座標
   が異なるとき、該点列のうちの任意の点を判別点として
   定義すると共に、再度判別点として定義される点は判別
   点としない判別点定義部と、 前記判別点を定義する処理が施された図形をＹ方向に走
   査して奇数番目と偶数番目の判別点を検出し、該奇数番
   目と偶数番目の判別点間を塗潰す塗潰部と、 を具備してなることを特徴とする多角形内部領域塗潰装
   置。