JPS6376086A - 輪郭ベクトルからのパタ−ン復元方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概　　要］ 文字パターンやシンボルパターンを輪郭ベクトルのデー
タとして保持していて、必要に応じて該データから元の
トンドパターンを復元する技術については、従来、エツ
ジ・リスト法やエツジ・フラグ法およびその他の幾通り
かの方法が知られているが、処理が複雑であったり、正
確さに欠けたり、あるいは必要なメモリ量が多いなどの
問題点を有していた６本発明はこのような従来の問題点
を解決するため、与えられた輪郭ベクトル列からパター
ンの内部と外部が変化することを示す判別点を生成し、
該判別点を用いて元の文字パターンやシンボルパターン
を復元することにより、Ｎ潔な処理で正確なパターンの
復元が可能であると共に、パターンメモ」Ｊを必要とし
ないかあるいは従来より少量のメモリ量で実現すること
の出来る輪郭ベクトルデータからのパターン復元方式に
ついて開示している。

［産業上の利用分野］ 本発明は、電算写植機やワープロ、パソコン等、記憶容
量を削減するために、文字パターンやシンボルパターン
を輪郭ベクトルで表現しておき、必要に応じて、元のド
ツトパターンを復元し、出力するという分野や、コンピ
ュータグラフィクス等のベクトルで表現された図形の内
部を塗り潰す処理を必要とする分野などにおいて、与え
られたパターンの輪郭ベクトル列、即ち、屈曲点列から
そのパターンの内部を塗り潰すことによって元パターン
を復元する方式に関するものである。

［従来の技術］ 従来のパターン復元方式、あるいは、塗り潰し方式とし
てエツジ・リスト法やエツジ・フラグ法等の方式があっ
た。

これらの方式の内エツジ・リスト法は、パターンを走査
してそのパターンの輪郭を検出してどこからどこまでが
パターンの内であり、外であるのかという判断をするこ
とが必要であるが、これが非常に複雑であり、そのため
処理が繁雑であると言う問題点があった。

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

そのため、比較的高速で、かつ、正確にパターンを塗り
潰すことの可能な手段として、例えば本出願人の出願に
係る「多角形内部領域塗潰装置（特願昭６０−０４８８
９６号）」等が提案されている。

［発明が解決しようとする問題点］ 上述した従来のパターン復元方式の内「多角形内部領域
塗潰装置」による方式は、屈曲点データより復元した、
多角形の輪郭線上に多角形の内部と外部が変化すること
を示す判別点を定義して、その点を元に、比較的高速で
かつ正確にパターンを塗り潰すことが可能なものである
が、輪郭線データを格納するためのメモリと判別点デー
タを格納するためのメモリが別個に必要であるため、パ
ターンのサイズに応じたビット数の２倍の記憶容量を持
つパターンメモリが必要であるから、使用出来るメモリ
容量に制限のある場合には使用出来ないと言う問題点が
あった。

本発明はこのような従来の問題点に鑑み、パターンメモ
リを必要としないかあるいは少量のパターンメモリによ
って、文字パターンやシンボルパターンの復元や塗り潰
しが可能であると共に、簡潔な処理で正確なバタ゛−ン
復元を行なうことの出来る輪郭ベクトルデータからのパ
ターン復元手段を提供することを目的としている。

［問題点を解決するための手段］ 本発明によれば、上述の目的は前記特許請求の範囲に記
載のとおり、与えられたパターンの輪郭ベクトル列から
輪郭線を復元する手段と、輪郭ベクトルからパターンの
内部と外部が変化することを示す判別点を生成する手段
と、判別点に基づいてパターン内部を塗り潰す手段とを
備え、まず、判別点を生成して、判別点間を塗り潰した
後に、輪郭線を復元することにより、パターンを復元す
るパターンメモリを削減できる輪郭ベクトルからのパタ
ーン復元方式、あるいは、与えられたパターンの輪郭ベ
クトル列からパターンの内部と外部が変化する点である
ことを示す判別点を生成する手段と、判別点を保持する
手段と、その判別点に基づいてパターンの黒ランベクト
ルを生成する手段とを備えて構成したことを特徴とする
パターン復元方式により達成される。

第１図は本発明の原理を示すブロック図であって、（ａ
）は特許請求の範囲第（１）”Ｊｊに対応するものであ
り、（ｂ）は特許請求の範囲第（２）項に対応するもの
である。

第１図（ａ）、（ｂ）において、入力となる輪郭ベクト
ル列は与えられたパターンの輪郭ベクトル表現であって
、例えばＤＤＡ等のａ　ｈｓ発生手段を用いてドツトパ
ターンの輪郭をベクトル化した順序性を有する屈曲点列
として蓄積されたデータである。

第１図（ａ）において、１はこれらの輪郭ベクトル列（
屈曲点列）に基づいて、パターンメモリ上にパターンの
内部と外部が変化することを示す判別点を生成する判別
点生成手段である。

２は判別点間塗り潰し手段であり、判別点生成手段１に
よってパターンメモリ上に生成された判別点間を塗り潰
す手段である。３は輪郭ベクトル列に基づいて、パター
ンの輪！Ｉｓ　４ｍをパターンメモリ上に復元する輪郭
線復元手段である。

第１図（ｂ）において、４はこれらの輪郭ベクトル列（
屈曲点列）に基づいて、パターンの内部と外部が変化す
ることを示す判別点を生成する判別点生成手段である。

５は判別点保持手段であり、これは、パターンメモリで
あっても、判別点の座標点テーブルの形であっても構わ
ない、６はパターンの黒ランのベクトル化手段であり、
判別点保持手段５によって保持されている判別点から、
パターンの黒うンベクトルを生成するものである。黒ラ
ンベクトル化手段６は、判別点保持手段５の実現形態に
依存するが、判別点保持手段５がパターンメモリ上に判
別点を保持するならば、そのパターンメモリをサーチす
ることによって、黒ランベクトルを生成する手段であり
、判別点保持手段５が座標点テーブルの形であれば、そ
の座標点テーブルをサーチし、黒ランベクトルを生成す
る手段である。６は、生成された黒ランベクトルに基づ
いて、実際に黒ランを発生し、パターンを復元するパタ
ーン復元手段である。

［作　　用］ 第１図（ａ）に示した構成においては、輪郭ベクトル列
で与えられたパターンの内部を高速に、正確に、且つ、
パターンのサイズに対応したビット数のパターンメモリ
を必要とするだけで、塗り潰す／復元することができる
。

才た、第１［ｆｆｌ　（ｂ）に示した構成のものにおい
ては、輪郭ベクトル列で与えられたパターンから黒ラン
のベクトルを正確に生成できるので、パターンメモリの
有無にかかわらず、元パターンを復元することができる
。また、拡大／縮小パターンを生成する際にも、一旦、
輪郭ベクトルを拡大／縮小変換した後、黒ランのベクト
ル化を行えば、ランレングス符号化の拡大／Ｉ小等で必
要な走査線間の補間といった処理が不必要であり、拡大
／１ｉＦ小パターンの生成にも、本発明は非常に有効と
なる。

［実　施　例］ 第２図は本発明の一実施例を示すブロック図である。こ
の図において、８は与えられたパターンの輪郭ベクトル
列を格納するメモリである。

まず、判別点生成回路９は、輪郭ベクトル列を読み出し
、パターンの内部と外部が変化することを示す判別点を
生成してパターンメモＩＪ１２に書き込む９判別点の生
成は下記のステップＩ〜ステップ■のように行なわれる
。

第３図（ａ）〜（ｄ）に各種の場合の判別点の生成の例
を示す、第３図において、・は判別点を表わしている。

くステップ■〉 屈曲点列間を補関し、輪郭点の座標値を発生しながら、
Ｙ座標が等しい連続する点列（水平部）を抽出する。屈
曲点の補間には、２点間の直線発生手段があれ：ボ充分
である０例えば、後述するＤＤＡ（ディジタル微分解析
機：　　Ｄｉｇｉｔａｌ　　Ｄｉｆｆｅｒｅｎｔｉａｌ
Ａｎａｌｙｚｅｒ）を用いる。

〈ステップ■〉 水平部に連結する前後の点のＹ座標が異なる場合、水平
部の一点を判別点として生成する０等しい場合は判別点
を生成しない。

また、判別点は排他的論理和で生成する。

即ち、判別点とすべき点が既に判別点てある場合は、そ
の判別点を判別点とはしない。

以上の処理によって判別点を生成しながら、判別点生成
回路９は、判別点をパターンメモリ１２に書き込む、そ
の際、屈曲点列により補関された輪郭点はパターンメモ
ＩＪ１２には書き込まない。

次に、判別点間塗り潰し回路１０において、パターンメ
モリ１２を読み出し、以下のステップＩ−Ｖにより判別
点間を塗り潰す（第４図参照）、パターンメモリのサイ
ズを（Ｘｍｉｎ、　Ｙｍｉｎ）〜（Ｘｍａｘ、　Ｙｉａ
ｘ）とする。

〈ステップＩ　＞　　Ｙ　＝Ｙｍｉｎ。

〈ステップＩＩ　＞　　ＦＬＧ　−０，Ｘ　−Ｙｍｉｎ
。

〈ステップ■〉　もし、（Ｘ、Ｙ）が判別点ならば、Ｆ
ＬＧ　−１−ＦＬＧ。

（Ｘ、Ｙ）が判別点でなく、 且つ、ＦＬＧ−１ならば、 （Ｘ、Ｙ）を塗る。

くステップｉｖ＞　　ｘ−ｘ＋ｔ もし　Ｘ≦Ｘ＋＊ａｘならば、 くステップ■〉へ。

くステップ■〉　Ｙ凛Ｙ＋１ もし　Ｙ≦Ｙｍａｘならば、 くステップ■〉へ、 Ｙ＞Ｘｍａｘならば、終了。

次に、輪郭線復元回路１１において、再び、輪郭ベクト
ル列が読み出され、屈曲点間の輪郭点を補関する。捕間
には、判別点生成回路９で用いる２点間を結ぶ直線発生
手段を利用し、例えば、Ｉ）ＤＡにより下記に示すステ
ップ■〜■の手順によって処理する。

くステップＩ＞　　Ｃ；１−ｅｏｓ（φ）Ｇ　２　＝ｓ
ｉｎ（φ） −Ｘｉ Ｙ肩ＹＩ Ｒ１−Ｘ　１　＋　０．５ Ｒ２−Ｙ　１　＋　０．５ くステップｎ＞　　Ｒ１富Ｒ１＋ＧＩ Ｒ２冒Ｒ２＋Ｇ２ くステップｍ〉　もし１ｎｔ（Ｒ１）≠Ｘ　または１ｎ
ｔ（Ｒ２）≠Ｙ　のとき、 Ｘ　−３ｎｔ（Ｒ１） Ｙ　＝　１ｎｔ（Ｒ２） 座標（Ｘ、Ｙ）に点を発生す る。

〈ステップ■〉　点（Ｘ、Ｙ）が点（Ｘ２．Ｙ２）に等
しくなければ、〈ステラ プ■〉へ。

そうでなければ、終了。

但し、ｉｎｔは小数点以下を切り捨てる関数である。

上述の処理により輪郭線を復元し、パターンメモリ１２
に書き込むと、パターンメモリ１２上に元パターンが復
元される。

第４図は上述したパターンの復元処理の例について説明
する図で、（ａ）は輪郭ベクトル列を、（ｂ）は該輪郭
ベクトル列からの判別点の生成を、（Ｃ）は判別点間の
塗り潰しを、（ｄ）は輪郭線の復元について示している
０図中、口は屈曲点、・は判別点、Δは判別点が戻った
点、Ｏは判別点間の塗り潰しで塗られた点、◎は輪郭線
復元で復元された点を表わしている。

第５図は本発明の他の実施例を示すブロック図である。

この図において、１３は与えられたパターンの輪郭ベク
トル列を格納するメモリである。

まず、判別点生成回路１４は、輪郭ベクトル列１３を読
み出し、パターンの内部と外部が変化することを示す判
別点を生成して判別点保持メモリ１７に書き込む０判別
点の生成は下記に示すステップエ〜■によって行なわれ
る。

また、第６図（ａ）〜（ｇ）に判別点生成の例を説明し
ている。同図において・は判別点、ムは判別点が多種に
生成される点を表わしている。

くステップＩ〉 屈曲点列間を補関し、輪郭点の座標値を発生しながら、
Ｙ座標が等しい連続する点列（水平部）を抽出する。屈
曲点の補間には、２点間の直線発生手段があれば充分で
ある０例えば、ＤＤＡ　（ディジタル微分解折機：　　
Ｄｉｇｉｔａｌ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ａｎａｌ
ｙｚｅｒ）を用いる。

くステップ■〉 水平部に連結する前後の点のＹ座標が異なる場合、水平
部の一点を判別点として生成する。

判別点の生成個所は、屈曲点列の保持の仕方に依存する
が、例えば、屈曲点列がパターン輪郭の時計廻り方向に
順序付けられて保持されているとすると、第６図（ａ）
。

（ｂ）に示す位置に生成する。

水平部に連結する前後の点のＹ座標が等しい場合、部ち
、水平部が極大、極小点になっている場合には、第６図
（Ｃ）、（ｄ）に示すように、その水平部の両端点に判
別点を生成する。

但し、第６図（ｅ）、（ｆ）（ｇ）に示すように、判別
点が多重に生成された場合、即ち、判別点とすべき点が
既に判別点である場合は、偶数回生成された場合には、
２重に、奇数回生成された場合には、１つとして扱う。

以上の処理によって判別点を生成しながら、判別点生成
回路１４は、判別点を判別点保持メモリ１７に書き込む
。

判別点保持メモリ１７は、二次元状のパターンメモリで
も、座標点テーブル（例えば、第１表に示す形式の座標
点テーブル）でも構わない。

パターンメモリの場合は、通常の判別点と２重に生成さ
れた判別点とを区別するために２ビツト／１点のメモリ
が必要である。一方、座標点テーブルの場合は、判別点
が生成される度毎に判別点座標をテーブルに書き込めば
よい。

次に、黒ランベクトル生成回路１５において、判別点保
持メモリ１７から判別点情報を読み出し、パターンの黒
ランベクトルが生成される（第７図参照）８判別点保持
メモリ１７がパターンメモリであれば、パターンメモリ
を水平方向にサーチし、判別間を結ぶ黒ランベクトルを
生成する（第７図参照）。その時、通常の判別点と二重
に生成された判別点を区別しなければならないが、二重
に生成された判別点に対しては、その点からその点まで
の黒ランベクトルを生成する。黒ランベクトルを生成す
る必要がない場合には、パターンメモリ上の判別点間を
水平方向に塗り潰してやれば、元パターンを復元できる
。一方、判別点保持メモリ１７として、・座標点テーブ
ルを使用する場合は、垂直方向（Ｙ方向）の同−事標単
位（第１表の行単位）で、水平方向くＸ方向）座標順に
判別点座標のソーティングを実行する。ソーティングの
後、２組毎に判別点座標値を取り出し、それらを黒ラン
ベクトルの始点、終点とすることによって、黒ランベク
トルを生成する。

このようにして、黒ランベクトル生成回路１５から、１
ラスター毎の黒ランベクトルが生成されるので、パター
ン、復元回路１６では、単に生成された黒ランベクトル
間に黒ランを発生することによって、パターンが復元さ
れる。

第７図は上述したパターンの復元の例について説明する
図で（ａ）は輪郭ベクトル列の例を、（ｂ）は＜ａ＞に
示した輪郭ベクトルについての判別点の生成を、（ｃ）
は黒ランベクトルの生成を、（ｄ）はパターンの復元を
示しており、口は屈曲点、・は判別点、ムは判別点が二
重に生成された点、○は黒ランベクトルによって塗られ
た点を表わしている。

第　　　　　１　　　　　表 ［発明の効果］ 近年、文字のディジタル処理技術の導入が進み、今やＯ
Ａ機器や電算写植システムなどでは、文字品質そのもの
が問われる時代になっている。

このようなシステム、或いは、機器には膨大な数の文字
パターンが要求れれるため、それらを格納しておくため
の膨大な記憶容量が必要となる。これを解決するため、
文字パターンを輪郭ベクトル表現によって圧縮しておき
、必要に応じて元パターンを復元する手段が必要とされ
る。

また、コンピュータグラフィクスなどの分野においても
、ベクトルデータで与えた図形内部に色塗りを施すよう
な機能が必要とされる。

このような要求に対し本発明によれば、特許請求の範囲
第（Ｉ）項記載の手段によって、与えられた輪郭ベクト
ル列から元パターンの内部を高速に、正確に、塗り潰す
ことができ、しかも、パターンのサイズに対応したビッ
ト数のパターンメモリを必要とするだけで、元パターン
を復元できる。

また、特許請求の範囲第（２）項記載の手段によれば、
与えられた輪郭ベクトル列から元パターンの黒ランのベ
クトルを正確に且つ高速に生成できるので、パターンメ
モリの有無にかかわらず、元パターンを復元することが
できる。

また、拡大／縮小パターンを生成する際にも、輪郭ベク
トル列を拡大／縮小変換した後、黒ランベクトルを生成
すれば、ラレングス符号化されたパターンの拡大／縮小
等で必要な走査量の補間といった処理が不要となる。

【図面の簡単な説明】

第１図は本発明の原理を示すブロック図、第２図は本発
明の一実施例を示すブロック図、第３図は判別点の生成
の例を示す図、第４図はパターンの復元処理を説明する
図、第５図は本発明の他の実施例を示すブロック図、第
６図は判別点の生成の例を示す図、第７図はパターンの
復元の例について説明する図である。 １．４・・・・・・・・・判別点生成手段、２・・・・
・・・・・判別点間塗り潰し手段、３・・・・・・・・
・輪郭線復元手段、５・・・・・・・・・判別点保持手
段、６・・・・・・・・・黒ランベクトル生成手段、７
・・・・・・・・・パターン復元手段、８．１３・・・
・・・・・・輪郭ベクトル列格納メモリ、９．１４・・
・・・・・・・判別点生成回路、１０・・・・・・・・
・判別点間塗り潰し回路、　　１１・・・・・・・・・
輪郭線復元［１ｉ１１．１２・・・・・・パターンメモ
リ、１５・・・・・・・・・黒ランベクトル生成回路、
１６・・・・・・パターン復元回路、１７・・・・・・
判別点保持メモリ代理人　弁理士　井　桁　貞　− （ａ）　　　　　　　　　　　　　　　　　　　（Ｃ）
ｏ　　　　　ｏ＝ｂｏ　　　　　ｏ　　　　　　　　　
ｏ−＞。 ｏｏｏｏ　　　　　　　ｏｏｏｏ　　　　　　　　　ｏ
ｏ　　　　ｏ。 （ｂ）　　’　　　　　　　　　　　　　ｃｄ）判ア１
永、の生成の砂ト示す図 第　３　図 ｒ輪郭ベクトル列ｊ　　　　　　１判別免切生威」１判
別熱間の遠り違し」　　　　　１奇郭謀の復元」パター
ンＯＡ笈元処理を銭帆すろ図 茅　４　図 本発明の他の炙施伊区示すブロック図 第６　口 判別２そ、の生成の秒Ｉ庖示す図 第６　図 ｒ阜倉郭ベクトル列、　　　　　　１割算１蕉の主成。 θ裏うシベクトルの眩」′パターンの復元」パターンの
１元の例１ニー）７・て説朗寸ろ図第　７　図

Claims (2)

【特許請求の範囲】
1. （１）与えられたパターンの輪郭ベクトル列からパター
   ンの内部と外部が変化することを示す判別点を生成する
   手段（１）と、 判別点に基づいてパターン内部を塗り潰す手段（２）と
   、 前記輪郭ベクトル列からパターンの輪郭線を復元する手
   段（３）とを備え、 判別点を生成して判別点間を塗り潰した後に輪郭線を復
   元することによりパターンを復元することを特徴とする
   輪郭ベクトルからのパターン復元方式。
2. （２）与えられたパターンの輪郭ベクトル列からパター
   ンの内部と外部が変化する点であることを示す判別点を
   生成する手段（４）と、 判別点を保持する手段（５）と、 その判別点に基づいてパターンの黒ランベクトルを生成
   する手段（６）とを備えて構成したことを特徴とするパ
   ターン復元方式。