JPH08194816A

JPH08194816A - 線分近似方法および線分近似方式

Info

Publication number: JPH08194816A
Application number: JP505595A
Authority: JP
Inventors: Naoya Nakanishi; 直哉中西
Original assignee: PESUPU PUROSU KK
Current assignee: PESUPU PUROSU KK
Priority date: 1995-01-17
Filing date: 1995-01-17
Publication date: 1996-07-30

Abstract

(57)【要約】【目的】ドットイメージの輪郭から、直線アウトライ
ンフォントを短時間で生成できる線分近似方法を提供す
る。【構成】ドットイメージの輪郭を線分近似する方法に
おいて、原ドットイメージの輪郭を固定長線分で高精度
に分割し、基準線分と隣接線分の角度を算出し、算出し
た角度を評価し、基準線分と隣接線分を直線近似できる
と評価した場合は、基準線分と隣接線分のベクトル和を
求めベクトル線分を発生させて、ベクトル線分を基準線
分とし、基準線分と隣接線分を直線近似できないと評価
した場合は、隣接線分を基準線分とし、ドットイメージ
の分割点の最終点に至るまで繰り返すことを特徴とする
ドットイメージデータの輪郭の線分近似方法。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、文字や図形等のドット
イメージデータの輪郭情報を可変長線分近似する方法お
よび方式に関するものである。

【０００２】

【従来の技術】近年パーソナルコンピュータのデバイス
が発達し、高解像度の表示装置および印刷装置の普及に
より、文字や図形は高品位のアウトラインフォントによ
って出力されるようになっている。

【０００３】ドットイメージデータの曲線部分を近似し
てアウトラインフォントを生成する方法として、曲線近
似方法と直線近似方法が知られている。

【０００４】曲線近似方法は、ドットイメージデータの
輪郭形状のうち、直線部分は線分で、また曲線部分につ
いては、これを近似する円弧あるいは数学上よく知られ
た多項式曲線、スプライン曲線、ベジェ曲線などで近似
する方法であり、輪郭形状の曲線部分を滑らかに近似す
ることができるため、曲線部分の品質が要求される用
途、特に文字イメージの表現などに広く応用されている
方法であるが、曲線部分を再びドットイメージに復元す
る際には、一般に線分の部分に比べて、超越関数演算を
含む多量の計算を実行しなければならず、ドットイメー
ジの再現に多大の処理負担がかかるため、長い処理時間
を有する。また、これを専用ハードウェアで実現しよう
とした場合、回路構造的にも専用アーキテクチャ化が困
難であり、高速処理に対する回路設計上の工夫の余地が
少なく、ただ計算速度の高速化に期待するしかないとう
いう欠点がある。

【０００５】一方、直線近似方法として、従来から図６
に示すような方法が知られている。すなわち、図６に示
すように輪郭点列上の特定の区間の始点と終点を結ぶ線
分（粗近似固定長線分）と、その区間における輪郭点列
の各座標点との距離を計算し、その最大誤差を与える点
を終点とすることを繰り返し、最大誤差がある一定の許
容値を超えなくなったときの終点を求め、得られた終点
と始点を結ぶ線分を輪郭当該区間の近似直線とし、これ
を輪郭全体にわたって繰り返すことにより線分近似を行
う方法である。

【０００６】

【発明が解決しようとする課題】しかしながら、従来の
直線近似方法は、輪郭を構成するすべての点、またはア
ルゴリズムの工夫により一部の点を選択して、粗近似固
定長線分との距離を計算しなければならず、多量の計算
処理を必要とする。特に計算内容は、輪郭点と粗近似固
定長線分との距離を求めねばならず、コンピュータ処理
上負荷の大きな２乗あるいは平方根処理を必要としてい
た。

【０００７】一書体当り７，０００〜１２，０００の文
字にもおよぶ日本語の文字において、ドットイメージの
文字データから直線アウトライン文字データを生成する
ための従来の直線近似方法でも、膨大な処理時間を要す
るという問題点があった。

【０００８】本発明の課題は、処理時間を大幅に短縮で
きるドットイメージの文字データから直線アウトライン
文字データを生成するための線分近似方法およびその方
式を提供することにある。

【０００９】

【課題を解決するための手段】本発明者は、上記課題を
解決すべく鋭意研究を重ねた結果、まず十分過ぎる精度
を持った固定長の線分でドットイメージの輪郭を分割
し、隣接する固定長線分同士の角度を評価し、その評価
により線分のベクトル和を取ることにより可変長の線分
近似を得る方法により上記課題が解決できることを見い
だし、本発明を完成するに至った。

【００１０】すなわち、本発明は、ドットイメージの輪
郭を線分近似する方法において、原ドットイメージの輪
郭を固定長線分で高精度に分割し、基準線分と隣接線分
の角度を算出し、算出した角度を評価し、基準線分と隣
接線分を直線近似できると評価した場合は、基準線分と
隣接線分のベクトル和を求めベクトル線分を発生させ
て、ベクトル線分を基準線分とし、基準線分と隣接線分
を直線近似できないと評価した場合は、隣接線分を基準
線分とし、ドットイメージの分割点の最終点に至るまで
繰り返すことを特徴とするドットイメージデータの輪郭
の線分近似方法、およびドットイメージの輪郭を線分近
似する方式において、原ドットイメージの輪郭を固定長
線分で高精度に分割する輪郭分割部と、基準線分と隣接
線分の角度を算出する角度算出部と、角度算出部により
算出された角度を評価する角度評価部と、基準線分と隣
接線分のベクトル和を求めベクトル線分を発生させるベ
クトル合成部とを備え、基準線分と隣接線分を直線近似
できると評価した場合は、基準線分と隣接線分のベクト
ル和を求めベクトル線分を発生させてベクトル線分を基
準線分とし、基準線分と隣接線分を直線近似できないと
評価した場合は、隣接線分を基準線分とし、ドットイメ
ージの分割点の最終点に至るまで繰り返すように構成し
たことを特徴とするドットイメージデータの輪郭の線分
近似方式に関するものである。

【００１１】なお、本発明における基準線分とは、角度
を算出するための基準となる線分であり、隣接線分と
は、基準線分に隣接する線分で、近似処理の施されてい
ない固定長線分をいうものとする。

【００１２】本発明の線分近似方法の原理について、図
１〜図３を用いて説明する。

【００１３】図１に示すように、ドットイメージの輪郭
を内接または外接する形で、固定長線分で高精度に分割
する。本発明の分割における高精度とは、固定長線分の
近似誤差が、従来の線分近似方法の場合に比べて十分高
い精度に設定するすることをいう。

【００１４】例えば、従来の線分近似方式では、固定長
の線分でおおまかに近似しておき、後に誤差距離の評価
を行って、予め設定されていた許容誤差より誤差距離が
大きな箇所においては、順次分割していくために、当初
の分割前の固定長線分が最大の長さを持つ近似線分とな
るために、これをあまり短く設定してしまうと、緩やか
な曲線部分における近似線分の本数が著しく増大する不
都合が生じるためかなり長めに設定しておく必要があ
る。一方、本発明によれば、予め設定されている許容誤
差よりはるかに小さな角度誤差しか与えない程細分化さ
れた近似線分を発生し、これらについて角度評価を行っ
て、その累積角度誤差が許容誤差を超える寸前まで、順
次連結併合していくという逆の方法であるため、本来的
に当初の固定線分近似精度は従来法に比べて極めて小さ
く選択しておく必要がある。またいくら小さく設定して
も、カーブが緩やかな箇所においては、後述するよう
に、いくらでも連結しておけるために、極めて広い範囲
にわたる長さの線分を発生することができ、最終的なデ
ータの冗長性を著しく低減することができる。すなわ
ち、固定長近似線分の長さを従来方法よりかなり短めに
設定する。

【００１５】このようにして、発生した固定長線分列
は、すでに当該ドットイメージの輪郭を再現するのに十
分すぎる精度をもっているが、輪郭形状の緩慢な曲線部
または直線部においては、極めて冗長度の高いものとな
り、データ量が膨大なものとなる点で好ましくない。

【００１６】そこで、本発明では、連続する２本の固定
長線分の角度を算出し、角度評価部により評価し、評価
の結果によってベクトル合成部にてこれらのベクトル和
を取った１本の可変長近似線分に合成することにより、
データ量の低減を図るものである。

【００１７】連続する２本の固定長線分の角度の角度、
すなわち、基準線分と隣接線分の角度を算出する方法
は、図２に示したように、基準線分の延長線と隣接線分
の角度θを算出してもよく、基準線分と隣接線分の角度
θ’を算出してもよい。

【００１８】角度θ、θ’を算出する方法は、特に限定
されないが、例えばθを算出する場合は、（１）式によ
り、θ’を算出する場合は、（２）式により求めればよ
い。

【００１９】

【数１】

【００２０】角度を計算する方法は、上記（１）式、
（２）式のように逆三角関数を用いる以外にも、各種の
公知な代数計算による近似計算処理を行ってもよい。

【００２１】角度評価部にはあらかじめ、角度の種類に
応じて許容値を設定しておき、この許容値と算出した角
度を比較評価する。許容値は、角度が基準線分の延長線
と隣接線分との角度θか、基準線分と隣接線分の角度
θ’かによって、異なる。例えば、許容値を以下のよう
に、（１）基準線分の延長線と隣接線分との角度θの場合の
許容値：１度〜１２度（２）基準線分と隣接線分の角度θ’の場合の許容値：
１７９度〜１６８度の範囲内で任意に設定し、許容値の種類により、以下の
ように評価すればよい。

【００２２】すなわち、算出する角度が基準線分の延長
線と隣接線分の角度θである場合は、角度θが許容値よ
り小さいときは、基準線分と隣接線分が直線近似できる
と評価し、ベクトル合成部で基準線分と隣接線分のベク
トル和をとり、角度θが許容値を超える場合は、基準線
分と隣接線分が直線近似できないと評価し、隣接線分を
基準線分と設定する。

【００２３】算出する角度が基準線分と隣接線分の角度
θ’である場合は、角度θ’が許容値よりθ’が大きい
ときは、基準線分と隣接線分が直線近似できると評価
し、ベクトル合成部で基準線分と隣接線分のベクトル和
をとり、角度θ’が許容値を超えない場合は、基準線分
と隣接線分が直線近似できないと評価し、隣接線分を基
準線分と設定する。

【００２４】図３により、角度の算出法が基準線分の延
長線と隣接線分の角度θを求める場合の、３本の固定長
線分を近似する方法を例示する。

【００２５】まず、図３（ａ）に示したように、基準線
分Ｌ₁とそれに隣接する隣接線分Ｌ₂の角度θ₁を求め、
θ₁が許容値より小さい場合は、図３（ｂ）に示したよ
うに、基準線分Ｌ₁と隣接線分Ｌ₂のベクトル和を取り、
ベクトル線分Ｌ_1-2を生成する。次に、図３（ｃ）に示
したようにベクトル線分Ｌ_1-2を基準線分とし、それに
隣接する隣接線分Ｌ₃との角度θ₂を求め、θ₂が許容値
より小さい場合は、図３（ｄ）に示したように、ベクト
ル線分Ｌ_1-2と隣接線分Ｌ₃とのベクトル和を取り、ベク
トル線分Ｌ_1-3を生成する。これらの動作を近似が終了
するまで繰り返すことにより、ドットイメージの輪郭を
可変長線分で近似することができる。

【００２６】もし、連続した固定長近似線分の角度θ_n
が許容値より小さい場合は、ベクトル合成により１本の
近似線分に合成され続けることになる。

【００２７】なお、ベクトル合成部でベクトル合成を行
うには、図２に示したように、単純にＶ＋ｖ＝（Ｘ＋
ｘ，Ｙ＋ｙ）を実行すればよい。

【００２８】

【実施例】以下、実施例により本発明をより詳細に説明
する。

【００２９】図４は、本発明の線分近似方式の一例を示
すブロック図である。

【００３０】１は、原ドットイメージの輪郭を固定長線
分で高精度に分割する輪郭分割部であり、２は基準線分
と隣接線分の角度を算出する角度算出部であり、３は角
度算出部により算出された角度を評価する角度評価部で
あり、４は基準線分と隣接線分の角度が許容値を超える
場合に基準線分と隣接線分のベクトル和を求めベクトル
線分を発生させるベクトル合成部である。

【００３１】輪郭分割部１は、原ドットイメージデータ
を、輪郭線上の各点から、半径＝固定長線分の円周と輪
郭線の交点を求めることによって、輪郭線の凸部（凹
部）における内接（外接）多角形を構成することにより
固定長線分で高精度に分割する。角度算出部２は、基準
線分と隣接線分の角度を、前記（１）式または（２）式
により算出する。角度評価部４には、上述した範囲内に
予め許容値を設定しておく。算出した角度が（１）式の
θの場合は、上記許容値よりθが小さいときは、ベクト
ル合成部４で基準線分と隣接線分のベクトル和を取り、
算出した角度が（２）式のθ’の場合は、上記許容値よ
りθ’が大きいときに、ベクトル合成部４で基準線分と
隣接線分のベクトル和を取ればよい。

【００３２】ベクトル合成部４は、基準線分と隣接線分
のベクトル和を取り、ベクトル線分を生成する。

【００３３】図５は、本発明の一実施例を示すフローチ
ャートである。なお、基準線分と隣接線分から求める角
度は、前記（１）式により算出されるものである。

【００３４】Ｓ１：ドットイメージの輪郭を固定長線分
で高精度に分割する。分割する方法は、原ドットイメー
ジデータを、輪郭線上の各点から、半径＝固定長線分の
円周と輪郭線の交点を求めることによって、輪郭線の凸
部（凹部）における内接（外接）多角形を構成すること
により固定長線分で高精度に分割する方法により行えば
よい。

【００３５】Ｓ２：基準線分と隣接線分の角度θを、前
記（１）式により算出する。

【００３６】Ｓ３：算出したθと予め設定された許容値
を比較する。

【００３７】Ｓ４：θが許容値より大きい場合は、隣接
隣接線分を基準線分とし、Ｓ７へジャンプする。

【００３８】Ｓ５：θが許容値より小さい場合は、基準
線分と隣接線分のベクトル和を合成する。

【００３９】Ｓ６：合成されたベクトル線分を基準線分
とする。

【００４０】Ｓ７：線分近似が終了したどうかを判定す
る。終了判定としては、例えば本発明方法によれば、輪
郭形状の近似線分のｘ成分とｙ成分の合成を累積してゆ
けば、終点においては必ず両者とも０になることから、
これを以て１輪郭分の線分近似の終了を判定する等の方
法による。線分近似がまだ終了していない場合は、Ｓ２
へもどり、線分近似が終了している場合は、プログラム
エンドとなる。

【００４１】

【発明の効果】本発明の方法および方式により、以下の
ような優れた効果が得られる。

【００４２】（１）高速な誤差評価による高速線分近似
ができるので、従来膨大な時間を要していたドットイメ
ージから直線アウトラインフォントの生成が、極めて短
時間に行えるようになる。

【００４３】（２）近似線分の長さのレンジが原理的に
広い（長い方にはいくらでも伸びられる）ため、従来の
線分近似方法に比して、極めて高効率のデータ圧縮効果
が得られる。

【００４４】（３）近似線分の長さのレンジが原理的に
広いため、実用的な再現拡大率の範囲において、曲線近
似に劣らないドット復元品質が保証される。

【００４５】（４）角度計算式において、数学的に豊富
な近似掲載方法があり、逆三角関数を計算する必要がか
ならずしもなく、単純な代数計算で更に高速化が可能と
なる。

【００４６】（５）ドット復元計算時において、曲線近
似方法に比べて極めて高速な処理が可能となる。

【図面の簡単な説明】

【図１】基準線分と隣接線分の角度の説明図。

【図２】ドットイメージの輪郭を固定長線分で分割する
説明図。

【図３】（ａ），（ｂ），（ｃ），（ｄ）は、基準線分
と隣接線分のベクトル和を合成する説明図。

【図４】本発明の一実施例を示すブロック図。

【図５】本発明の一実施例を示すフローチャート。

【図６】従来の、直線近似方法の説明図。

【符号の説明】

１輪郭分割部２角度算出部３角度評価部４ベクトル合成部

Claims

【特許請求の範囲】

【請求項１】ドットイメージの輪郭を線分近似する方
法において、原ドットイメージの輪郭を固定長線分で高
精度に分割し、基準線分と隣接線分の角度を算出し、算
出した角度を評価し、基準線分と隣接線分を直線近似で
きると評価した場合は、基準線分と隣接線分のベクトル
和を求めベクトル線分を発生させて、ベクトル線分を基
準線分とし、基準線分と隣接線分を直線近似できないと
評価した場合は、隣接線分を基準線分とし、ドットイメ
ージの分割点の最終点に至るまで繰り返すことを特徴と
するドットイメージデータの輪郭の線分近似方法。
【請求項２】ドットイメージの輪郭を線分近似する方
式において、原ドットイメージの輪郭を固定長線分で高
精度に分割する輪郭分割部と、基準線分と隣接線分の角
度を算出する角度算出部と、角度算出部により算出され
た角度を評価する角度評価部と、基準線分と隣接線分の
ベクトル和を求めベクトル線分を発生させるベクトル合
成部とを備え、基準線分と隣接線分を直線近似できると
評価した場合は、基準線分と隣接線分のベクトル和を求
めベクトル線分を発生させてベクトル線分を基準線分と
し、基準線分と隣接線分を直線近似できないと評価した
場合は、隣接線分を基準線分とし、ドットイメージの分
割点の最終点に至るまで繰り返すように構成したことを
特徴とするドットイメージデータの輪郭の線分近似方
式。