(57)【特許請求の範囲】
【請求項１】
文字・図形を示す輪郭線の情報をビットマップに展開する文字・図形処理装置において、前記輪郭線の情報を構成するセグメントと前記ビットマップの画素の配列方向に平行な走査線との交点からエッジを検出する走査変換手段と、該走査変換手段が出力するエッジの座標を走査線ごとにリストとして登録するエッジリスト登録手段と、前記リストに前記エッジリスト登録手段で登録した前記エッジの座標を走査線ごとにソートするエッジリスト生成手段と、該エッジリスト生成手段によってソートされたリストをもとに２つのエッジの座標が同じである場合にドロップアウトが発生するエッジを検出して補正処理を行うとともに該補正処理により生じた凹状部をセグメントに沿って補正する補正処理を行う形状補正手段と、前記エッジリスト生成手段によってソートされたリストをもとにビットマップに展開するエッジリスト展開手段を有することを特徴とする文字・図形処理装置。
【請求項２】
前記走査変換手段は、エッジの検出とともに走査線とセグメントとが直交するか否かを判定し、前記エッジリスト登録手段は、前記走査変換手段が走査線とセグメントとが直交すると判定した場合に該セグメントと走査線との交点のエッジの座標を順次リンクさせ、前記形状補正手段は、前記ドロップアウトが発生するエッジを検出したとき、該エッジの座標からリンクされているエッジの座標が存在する場合に該リンクをたどって得られるエッジの座標について補正処理を行うことを特徴とする請求項１に記載の文字・図形処理装置。
【請求項３】
前記形状補正手段は、前記補正処理としてビットマップに補正対象の画素を書き込むことを特徴とする請求項１または請求項２に記載の文字・図形処理装置。
【請求項４】
前記形状補正手段は、前記エッジリスト生成手段が１走査線について前記エッジの座標をソートするごとに補正処理を行うことを特徴とする請求項１ないし請求項３のいずれか１項に記載の文字・図形処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文字・図形を示す輪郭線の情報をビットマップに展開する文字・図形処理装置に関するものである。
【０００２】
【従来の技術】
ページプリンタ、ディスプレイ等のビットマップスクリーンをベースとする出力装置では、解像度が向上するにしたがって、同じサイズの文字・図形パターンを出力するために、より多くのビットマップデータが必要となる。さらに各種のサイズの文字・図形パターンの出力に対応するためには、それぞれのサイズ毎にビットマップデータを保持しなければならず、効率が悪くなる。そこで、特に文字のように決まった輪郭をもつパターンについては、基本となるパターンの輪郭線を、複数の直線セグメントや曲線セグメントによって構成される輪郭線の情報（アウトライン情報）として保持し、所望のサイズに拡大縮小してから輪郭線の内部を塗りつぶす方法を利用し、メモリ効率を向上させている。
【０００３】
この、輪郭線の内部を塗りつぶす方法を利用して文字・図形パターンを描画する処理について、以下に簡単に説明する。図７は、輪郭線と、その輪郭線から得られるビットマップの一例の説明図である。図７において、制御点（○に×印で示す）の間を結ぶ太線が輪郭線の情報を構成する各セグメントである。図７に示した文字「Ａ」は、１１個の直線セグメントで構成されている。このような輪郭線の情報に基づいて、その輪郭線の内部に存在する画素を例えば反転させることによって、図７においてハッチングで示したような文字「Ａ」のビットマップを得るものである。
【０００４】
図８は、輪郭線の内部の画素であるか否かを判定する一方法の説明図である。上述のように輪郭線の内部に存在する画素を例えば反転させるためには、各画素について、輪郭線の内部か否かを判定する必要がある。その判定方法の一つとして、ここでは、各画素の中心位置が輪郭線の内部か否かを判定する。すなわち、矩形で示した各画素の中心位置（図中の○）が、輪郭線（図中、○に×印で示した制御点を結ぶ太線）で囲まれた内部に存在するか否かを判断すればよい。このような判定方法によって、図８においてハッチングを施して示した画素（矩形）が、輪郭線の内部であると判定される。これらの画素を例えば反転することによって、文字や図形のビットマップを得ることができる。
【０００５】
基本的には上述のようにして、輪郭線の情報に基づいて、その内部の画素を例えば反転して塗りつぶし処理を行う。実際に、このような塗りつぶし処理を行う方法には、代表的な方法としてスキャンコンバージョン法がある。図９は、スキャンコンバージョン法による塗りつぶし処理の説明図である。ここでは、輪郭線の延在する方向（ストローク方向）を考慮しないＥＶＥＮ−ＯＤＤルールと呼ばれる条件で輪郭線の内外を判定する例について説明する。
【０００６】
いま、図９（Ａ）に太線で示すような輪郭線の情報が与えられたとする。ここで、ビットマップの画素の配列方向のうち、一方の配列方向を走査方向とする。ここでは、図中の左右方向を走査方向とする。もちろん、図中の上下方向を走査方向としてもよい。
【０００７】
そして、走査方向に平行で、各画素の中心点を結ぶ複数の走査線と、輪郭線との交点の座標を求める。図９では、交点を●によって示し、各画素の中心を○によって示している。さらに、ここでは交点の図中右側において最も近い位置に中心を有する画素を得る。この画素をエッジと呼び、塗りつぶし範囲の始点、終点となる。図９（Ａ）ではエッジの画素にハッチングを施して示している。この例では走査線を図中の左右方向に設定しているので、左右方向の輪郭線上では輪郭線と走査線とが交点を持たないため、エッジが現れない。
【０００８】
次に、ルールに従ってペイント処理を行う。ＥＶＥＮ−ＯＤＤルールでは、走査線との交点を一方の端から数えて奇数番目から、偶数番目までが塗りつぶし範囲となる。上述のように、エッジを交点の右側に取った場合には、左端から数えて奇数番目のエッジが始点、偶数番目のエッジが終点となる。図９（Ｂ）に示すように、このルールに従って走査方向に沿って画素を調べて行き、奇数エッジから偶数エッジまでの画素を反転する。ここで、偶数エッジ自身は輪郭線の外側となるので、偶数エッジの左の画素までが塗りつぶし範囲であることに注意する。また、エッジが偶数個重なった場合は、エッジを消すことで正しく塗りつぶすことができる。
【０００９】
図９（Ｂ）に示した例では、三角で示した画素が始点となり、逆三角で示した画素が終点となる。そのため、ハッチングを施した画素が反転されることになる。
【００１０】
図１０は、スキャンコンバージョン法による塗りつぶし処理の具体例の説明図である。図７で示した文字「Ａ」の場合について、図９で説明したスキャンコンバージョン法により塗りつぶし処理を行った場合の例を示している。図１０（Ａ）に太線で示すような輪郭線の情報が与えられると、各輪郭線と各走査線との交点から、図１０（Ａ）にハッチングを施して示したエッジが求められる。ここで、走査方向の左側から奇数番目のエッジ（三角で示す）が始点、偶数番目のエッジ（逆三角で示す）が終点となる。
【００１１】
このようにして求められたエッジの情報をもとに、始点の画素から終点の画素の手前の画素までを反転することにより、図１０（Ｂ）に示すようなビットマップを得ることができる。文字「Ａ」では上半分の内部が抜けているが、この方法によればこのような白く抜ける部分についても正確に表現することができる。
【００１２】
上述の輪郭線の内部を塗りつぶす方法を利用して小サイズのパターンを出力しようとすると、塗りつぶしに抜け（ドロップアウト）が発生する場合がある。この原因は、輪郭線の間隔が狭くなりすぎて、輪郭線の間に中心点を持つ画素が存在しない場合に発生する。言い換えると、隣接する画素の中心点間を複数の輪郭線が貫く場合に発生する。
【００１３】
図１１は、ドロップアウトの一例の説明図である。例えば図１１（Ａ）に示すように、水平に並んだ画素の中心点間を複数の輪郭線が貫いた場合に、破線で示す画素が塗りつぶされず、図形が途切れたように見えてしまう。この原因は、図１１に示す２本の輪郭線と走査線との交点から得られるエッジが同じ画素となってしまうことによる。すなわち、図１１（Ｂ）に示すように、中央の画素においては、塗りつぶし領域の始点であり終点でもある。上述のように、ペイント処理を正常に実施するためには、偶数個重なったエッジを消去する。そのため、図１１（Ｂ）に示す中央の画素はエッジが消去され、塗りつぶしは行われない。このようにしてドロップアウトが発生してしまう。
【００１４】
上述のようにエッジが重なっている部分にドロップアウトが発生することから、逆にエッジを抽出する段階で２つのエッジが重なっていることを検出すれば、ドロップアウトが発生することを予測できる。しかし前述したように、ペイント処理を正常に実施するためには、この重なっているエッジを削除しなければならないので、ペイント処理とは別にドロップアウトの補正処理を行うことになる。
【００１５】
図１２は、ドロップアウトの別の例の説明図である。図１２では、垂直方向に隣接する画素の中心点間を、複数の輪郭線が貫く場合に発生するドロップアウトを示している。この例では、各走査線と輪郭線との交点から得られるエッジに従って塗りつぶす領域が、隣接する走査線において連続しない。すなわち、エッジは図１２（Ｂ）に示すように得られるが、このエッジに従って塗りつぶされる画素は、図１２（Ａ）においてハッチングを施した画素である。このように、隣接する走査線間で塗りつぶす領域が離れてしまうため、破線で囲んだ箇所において図形が途切れたように見えてしまう。
【００１６】
この図１２に示す例では、図１１に示す例のように走査方向から調べても重なったエッジは発見できず、図１１に示す場合と同様の方法ではドロップアウトの発生は予測できない。このような場合には、図１２（Ｃ）に示すように、走査線を図中の上下方向に設定すると、図１１に示す例と同様にして、ドロップアウトの発生を予測することが可能になる。
【００１７】
以上のように、ドロップアウトを全て発見するためには、図中の左右方向と上下方向の両方向からエッジを検出する必要がある。但し、ペイント処理は、水平及び垂直のどちらからでも結果が同じなので、一方で検出したエッジに対してのみ実施すればよい。
【００１８】
図１３は、ドロップアウトの補正を含むスキャンコンバージョン法による塗りつぶし処理の具体例の説明図である。ここでは小さい文字「０」をビットマップ展開する例を示している。２つの曲線セグメントによって挟まれた部分を塗りつぶすことによって、小さい文字「０」を出力できる。
【００１９】
この例において、図中の左右方向（または上下方向）を走査方向として得られたエッジを用いてペイント処理を行うことによって、図１３（Ａ）にハッチングを施して示す画素が塗りつぶされる。輪郭線間隔の狭い部分でドロップアウトが発生していることが判る。
【００２０】
次に、図１１において説明したように、走査方向のエッジの重なりを調べると、図１３（Ｂ）にハッチングを施して示した画素がドロップアウトしていることが発見できる。また、図１２において説明したように、走査方向を変更（例えば図中の左右方向から上下方向に変更）してエッジの重なりを調べると、図１３（Ｃ）にハッチングを施して示した画素がドロップアウトしていることが発見できる。図１３（Ａ）、（Ｂ）、（Ｃ）の各画像を合成することによって、図１３（Ｄ）に示すようにドロップアウトのない図形（文字「０」）を得ることができる。なお、図１３では図１３（Ａ）、（Ｂ）、（Ｃ）の各ビットマップ画像を別々に示しているが、例えば１枚のビットマップに図１３（Ｂ）、（Ｃ）に示す両方向の走査方向におけるドロップアウトする画素を書き込んでもよい。また、図１３（Ａ）、（Ｂ）、（Ｃ）の各画像を１枚のビットマップに書き込むように構成してもかまわない。
【００２１】
ところで、輪郭線と走査線との交点により選択されたエッジを、もっとも単純に記録しておくには、上述の各例において示したように、ビットマップ上で画素を反転させておけばよい。この場合、ペイント処理で全ての画素を調べることによって、上述のような塗りつぶしを行うことができる。しかし、文字のサイズが大きくなった場合や高解像度の場合には、ビットマップの画素数も非常に多くなる。このように画素数が多くなると、ペイント処理で全ての画素を調べる処理は非常に重くなる。また、ビットマップのためのメモリ量も大きくなる。例えば縦横ｎ倍のビットマップを作成するためにはｎの２乗倍のメモリが必要となる。さらに、ドロップアウト処理にビットマップがもう１枚必要であったり、単純なデータ構造のためにＥＶＥＮ−ＯＤＤルール以外のもっと複雑なペイントルールが利用しにくい、などの欠点がある。
【００２２】
そこで、エッジの座標を走査線毎にリストにし、リストから隣接するエッジの座標を２つずつ取り出して塗りつぶし範囲とする、エッジリストと呼ばれる方法がある。例えば特開平５−２２４６５３号公報に記載されている文字出力装置では、セグメントと走査線の交点のＸ座標、Ｙ座標を組にしてリストに登録し、このリストをもとにペイント処理を行っている。
【００２３】
図１４は、エッジリストを用いたスキャンコンバージョン法による塗りつぶし処理の具体例の説明図である。図１４（Ａ）は、輪郭線と画素との関係の一例を示した拡大図である。ここでは、走査線Ｓ１，Ｓ２における画素の塗りつぶし処理を考える。また、太線で示した▲１▼〜▲５▼が輪郭線のセグメントであり、この順番で格納されているとする。
【００２４】
まず、各セグメントは順次呼び出され、走査線との交点を検出する。例えばセグメント▲１▼は、走査線Ｓ１及び走査線Ｓ２と●で示した位置で交差する。この●の座標を、それぞれの走査線のリストに加えて行く。すなわち、図１４（Ｂ）に示すように、走査線Ｓ１のリストに、セグメント▲１▼と走査線Ｓ１の交点の座標としてＰ１（▲１▼）を格納する。同様に、走査線Ｓ２のリストに、セグメント▲１▼と走査線Ｓ２の交点の座標としてＰ２（▲１▼）を格納する。このような処理を、各セグメント▲２▼〜▲５▼についても行う。これによって、図１４（Ｂ）に示すようなリストが得られる。ここでは、上述の文献のようにＸ、Ｙ座標を格納するほか、走査線Ｓ１によって一方の座標値が分かっているので、他方の座標値のみを格納してもよい。
【００２５】
このようにしてすべてのセグメントについて、走査線との交点の座標をリストに登録したら、走査線毎に登録されている座標をソートする。ここでは左から右への順でソートすると、図１４（Ｂ）に示すリストは、図１４（Ｃ）に示すようにソートされる。
【００２６】
ソート後、図１４（Ｄ）に示すように先頭からペアでセグメントと走査線の交点の座標を取り出す。ペアの座標のうち、先の座標に対応するエッジが塗りつぶし処理の始点、後の座標に対応するエッジが塗りつぶし処理の終点となる。始点から終点までの画素を反転することによって塗りつぶし処理を行うことができる。なお、上述のように終点の画素は反転しない。
【００２７】
このようなペイント処理によって、図１４（Ｅ）にハッチングで示す画素が反転され、走査線Ｓ１，Ｓ２における塗りつぶし処理が終了する。なお、図１４ではセグメントと走査線との交点の座標をリストに登録する例を示しているが、例えば交点の座標に対応するエッジの座標を登録してもよい。
【００２８】
エッジリストでは、エッジの情報をビットマップ上に持たないので、ドロップアウトする画素についてはペイント処理を施しているビットマップに直接描画すればよい。また、エッジ間を塗りつぶすためにビットマップをすべて読み出す必要がなく、また、ビットマップ上で偶数エッジを消去するなどのエッジ情報を操作する必要も無い。そのため、ワークエリアのメモリにビットマップを持つ必要がなく、最終的な出力先であるフレームバッファに直接書き込むことによってペイント処理を実行してかまわない。
【００２９】
上述のようなエッジリストを用いた塗りつぶし処理においても、エッジリストから取り出した２つの座標に対応するエッジが同じであれば、ドロップアウトが発生すると判定できるので、ドロップアウトに対する処理を行うことができる。また、上述のようなエッジリストを、直交する２方向の走査線について別々に作成し、それぞれのエッジリストからドロップアウトを検出することも考えられている。
【００３０】
上述のように、輪郭線の間隔が狭くなりすぎて塗りつぶしに抜け（ドロップアウト）が発生する場合、この現象を回避するためにスキャンコンバージョンの過程でドロップアウトの発生個所を検知し、修正を行う。しかし、輪郭線の１セグメントの中でドロップアウト部分とそうでない部分とが存在した場合、ドロップアウトでない部分に凹形状が現れるという不具合がある。
【００３１】
図１５は、ドロップアウト処理による不具合の一例の説明図である。図１５（Ａ）では、文字「１」を描画した例を示している。文字「１」のセリフ部分において、Ｐ１およびＰ３はドロップアウト処理によって塗りつぶされるが、Ｐ２は塗りつぶされず、凹形状が現れている。このような現象は、図１５に示す文字「１」のセリフ部分に限らず、文字「Ｔ」の上部等、水平部分と垂直部分が交わる個所で顕著である。この凹形状は、その形状が鳥の足のように見えることから、この個所を「鳥足」と呼んでいる。
【００３２】
図１５（Ｂ）には図１５（Ａ）の鳥足発生部分を拡大して示している。輪郭線を構成するセグメントのうち、図中の左右方向に延在する水平セグメントＬ１、Ｌ２、Ｌ３は、図中の上下方向の走査線に対して交点をもつ。このとき、エッジとなる画素Ｐ１、Ｐ２、Ｐ３のうち、Ｐ１，Ｐ３についてはドロップアウトが検出され、ドロップアウト処理によって塗りつぶされる。しかし、Ｐ２は単なる終端のエッジとなるためドロップアウトとは判定されない。例えば図中の上下方向に走査線を設定した場合には、Ｐ２の１つ上の画素までが塗りつぶし範囲となり、Ｐ２は塗りつぶされない。また、例えば図中の左右方向に走査線を設定した場合には、Ｐ１〜Ｐ３の何れもエッジとはならない。そのため、図中の左右方向及び上下方向の両方に走査方向を設定したとしても、Ｐ２については塗りつぶされない。そのため、図１５（Ａ）に示すような凹形状の「鳥足」が現れる。
【００３３】
従来の技術では、上述のようなドロップアウト部分の補正処理は行っているが、「鳥足」の発生を防ぐことはできなかった。
【００３４】
【発明が解決しようとする課題】
本発明は、上述した事情に鑑みてなされたもので、文字・図形を示す輪郭線の情報をビットマップに展開する際に発生していた凹形状の「鳥足」を補正し、良好な文字・図形を再現可能な文字・図形処理装置を提供することを目的とするものである。
【００３５】
【課題を解決するための手段】
本発明は、エッジリストを用いて輪郭線の情報をビットマップに展開する際に、つのエッジの座標が同じである場合にドロップアウトが発生するエッジを検出して補正処理を行うとともに、その補正処理により生じた凹状部をセグメントに沿って補正する補正処理を行うものである。より具体的には、エッジリストの作成時に、エッジの検出とともに走査線とセグメントとが直交するか否かを判定し、走査線とセグメントとが直交すると判定した場合には、そのセグメントと走査線との交点のエッジの座標を順次リンクさせておく。そして、ドロップアウトの補正処理時に、ドロップアウトが発生するエッジを検出したとき、そのエッジの座標からリンクされているエッジの座標が存在する場合には、そのリンクをたどって得られるエッジの座標について補正処理を行う。
【００３６】
これによって、輪郭線の１セグメントの中でドロップアウト部分とそうでない部分とが存在した場合でも、ドロップアウト部分からセグメントに沿って補正処理を行うため、「鳥足」と呼ばれるような凹形状は補正され、「鳥足」がビットマップ上に現れることはない。そのため、輪郭線の情報から良好に文字・図形をビットマップ展開することができる。
【００３７】
【発明の実施の形態】
図１は、本発明の文字・図形処理装置の実施の一形態を示す概略構成図である。図中、１は走査変換部、２はエッジリスト登録部、３はエッジリスト生成部、４は形状補正部、５はエッジリスト展開部、６は輪郭線情報、７はエッジリスト、８はビットマップである。
【００３８】
走査変換部１は、指定された文字や図形の輪郭線情報６を取り出し、記録されている順に輪郭線を構成するセグメントを読み出し、セグメントと走査線の交点を計算し、交点の座標からエッジを求める。そして、順次、エッジリスト登録部２にエッジの情報を渡す。この時、セグメントが走査線に対して垂直であれば、エッジリスト登録部２にリンクを作成するように指示する。全てのエッジを登録したら、エッジリスト生成部３を呼び出す。なお、文字や図形の大きさを変更するための拡大縮小処理など、各種の変換処理を予め行っておいてもよい。また、曲線セグメントについては、処理の効率化のため、分割して直線セグメントによって近似してもよい。
【００３９】
エッジリスト登録部２は、エッジリスト７として走査線毎に用意されたリストに、走査変換部１から出力されたエッジの情報を、リンク情報とともに、順次、登録する。リストにエッジの情報として登録する要素は、登録するエッジの座標と、このエッジとリンクする次のエッジを格納した場所（例えばリストでの配列番号やメモリアドレス等）の、最低、２つの情報を格納している構造体である。走査変換部１からリンクを作成する指示があった場合は、登録したエッジの情報中の次のエッジを格納した場所として、同じセグメントについて次の走査線で登録するエッジの情報の場所を登録する。指示が無い場合は、リンクに終端番号（例えば−１など、特定の値）を代入する。
【００４０】
エッジリスト生成部３は、エッジリスト７をエッジの座標で走査線毎にソートし、１本の走査線についてリストのソートが終了するごとに形状補正部４を呼び出し、そのソートされたリストを渡す。
【００４１】
形状補正部４は、エッジリスト生成部３から渡された１走査線分のリストを検査し、エッジがドロップアウトの可能性があるか否かを判断する。そして、ドロップアウトの可能性があれば、ドロップアウト用のビットマップ８に登録し、通常のエッジであればエッジリスト展開部５を呼び出す。ドロップアウトの可能性があると判断されたエッジにリンクがある場合は、リンクを追跡し、そのエッジもドロップアウト用のビットマップ８に登録する。
【００４２】
エッジリスト展開部５は、形状補正部４が出力したエッジ間を、ビットマップ８上に展開する。
【００４３】
なお、既に述べたように、ドロップアウトの検出は、ビットマップの画素が配列されている２方向（以下の説明では便宜上、水平方向および垂直方向とする）について行う必要がある。そのため、走査変換部１，エッジリスト登録部２，エッジリスト生成部３，形状補正部４は、水平方向の走査線と垂直方向の走査線の２つの場合についてそれぞれ処理を行う。また、エッジリスト展開部５については、いずれかの方向の走査線について処理を行えばよいので、２回の処理のうち１回目（または２回目）の実行時のみ呼び出される。
【００４４】
図２は、本発明の文字・図形処理装置の実施の一形態における動作の一例を示すフローチャートである。例えば外部より輪郭線情報６が入力されたり、あるいはコード情報が入力され、コード情報に従って例えば内部のＲＯＭや外部記憶装置から輪郭線情報６を読み出し、ビットマップに展開すべき文字・図形の輪郭線情報６が与えられると、文字・図形処理装置の動作を開始する。上述のように、補正処理のために異なる走査方向によって２回の処理を行う。
【００４５】
まずビットマップ８を初期化し、１度目の処理を開始する。走査変換部１は、与えられた輪郭線情報６に対し、必要に応じて、出力したいサイズに座標変換するなど各種の変換処理を行う。また、画素のサイズから曲線セグメントは分割数を決め、短い直線セグメントに分割しておく。さらに、エッジリスト７を初期化しておく。
【００４６】
Ｓ２１において、走査変換部１は、与えられた輪郭線情報６を構成するすべてのセグメントについて、各走査線との交点に対応するエッジを順次求める。エッジリスト登録部２は、走査変換部１で求めたエッジの情報を、エッジリスト７に順次登録してゆく。このとき、走査変換部１は、セグメントが走査線に対して垂直であるか否かを判定し、走査線に対して垂直なセグメントについてはエッジリスト登録部２にリンクの作成を指示する。この指示に従って、エッジリスト登録部２は、走査線に対して垂直なセグメントについて、走査線毎に登録されるエッジをリンクで順次接続してゆく。
【００４７】
輪郭線情報６を構成するすべてのセグメントについて、エッジを求めてエッジリスト７に格納した後、走査線毎にエッジリスト生成部３、形状補正部４、エッジリスト展開部５の処理を行う。まずＳ２２において、最初の走査線に設定し、Ｓ２３において全走査線について処理を終了したか否かを判定した後、Ｓ２４において、エッジリスト生成部３は１走査線分のエッジのリストをソートする。そして、ソートされたエッジのリストの最初からエッジの情報を取り出せるように初期化しておく。なお、エッジは２つをペアとし、始点及び終点として処理する。
【００４８】
Ｓ２５において、１走査線分のリスト中のエッジについて、すべて処理し終えたか否かを判定し、未処理のエッジが残っている場合にはＳ２６に進む。
【００４９】
Ｓ２６では、形状補正部４においてドロップアウトの判定を行う。すなわち、１走査線分のリストからエッジを２つ取り出したとき、その座標が同じであればドロップアウトが発生するものと判定できる。ドロップアウトが発生しなければ、Ｓ２７において、エッジリスト展開部５は、取り出したエッジ間のビットマップ８を反転し、塗りつぶす。このとき、終点となるエッジについては反転しない。また、ドロップアウトが発生していればＳ３０に進み、形状補正部４はドロップアウトの補正処理と、そのドロップアウトの補正処理に伴う「鳥足」の発生を防止する補正処理を行う。
【００５０】
その後、この２つのエッジを処理済とし、Ｓ２８において次の２つのエッジを取り出し、Ｓ２５へ戻る。このように２つのエッジ毎に処理を行って行き、１走査線のリストに格納されているすべてのエッジについて処理を終えると、Ｓ２５でこれを検出し、Ｓ２９において次の走査線へ処理を移してＳ２３に戻る。なお、エッジは２つをペアとして処理するので、エッジが１つだけ残る場合が発生しても、１走査線について処理を終了したものとして扱う。
【００５１】
このようにして、順次、走査線毎の処理を行ってゆき、すべての走査線についての処理を終えると、これをＳ２３で検出し、１回目の処理を終了する。次に、走査方向を変更して２回目の処理を行う。２回目の処理では、エッジリスト展開部５による塗りつぶしの処理、すなわち、Ｓ２７における処理を行わない。その他の処理は１回目と同様の処理である。２回の処理を終えると、輪郭線情報６をビットマップ８に展開する処理を終了する。
【００５２】
図３は、本発明の文字・図形処理装置の実施の一形態においてドロップアウトが発生する場合の動作の一例を示すフローチャートである。この処理は、図２のＳ２６においてドロップアウトが発生すると判定された場合に実行される。Ｓ３０においてドロップアウトが発生すると判定されたエッジの情報を取得し、Ｓ３１において、そのエッジについて、ビットマップ８に登録する。
【００５３】
さらに、ドロップアウトが発生すると判定されたエッジが、走査線に垂直なセグメントに含まれていた場合には、そのセグメント上の各画素について補正処理を行う。このとき、エッジに含まれるリンクをたどることによって、走査線に垂直なセグメント上の画素を取得することができる。
【００５４】
Ｓ３２において、ドロップアウトの判定を行った際に用いた２つのエッジの両方について、リンクが終端であるか否かを判定する。両方とも終端であれば、このドロップアウト時の補正処理を終了する。
【００５５】
少なくともいずれかのリンクが終端でなければ、Ｓ３３において、始点となるエッジのリンクの有無を確認する。リンクが終端でなければ、Ｓ３４において、リンク先の次の走査線におけるエッジを取得し、このエッジのリンクを終端に変更する。同様に、Ｓ３５において、終点となるエッジのリンクの有無を確認する。リンクが終端でなければ、Ｓ３６において、リンク先の次の走査線におけるエッジを取得し、このエッジのリンクを終端に変更する。Ｓ３７において補正処理における処理対象の走査線を次に進め、Ｓ３１に戻ってＳ３４，Ｓ３６で取得したエッジについてビットマップ８に登録する。以後、Ｓ３４，Ｓ３６で取得したエッジを処理対象として、Ｓ３２以降の処理を繰り返す。
【００５６】
このような繰り返し処理によって、走査線に垂直なセグメントに対応するエッジを追跡し、順次、ビットマップ８に登録して行く。２つのセグメントが終端に達すると、対応するエッジのリンクが終端となる。これをＳ３２で検出し、補正処理を終了してＳ２８へ戻り、ドロップアウトが発生すると判定された２つのエッジについての処理を終了する。
【００５７】
上述の動作の一例を、具体例を用いながら説明する。図４は、本発明の文字・図形処理装置の実施の一形態における動作の一例において遷移するエッジリストの状態の一例を示す説明図、図５は、同じくビットマップの状態を示す説明図である。ここでは図１５に示したような文字「１」の下のセリフ部における例を考える。図１５（Ｂ）と同様の例を図５（Ａ）に示している。記号は図１５と同様である。図５（Ａ）に示すように、図中の上下方向を走査方向とし、走査線に垂直な２本のセグメント（セグメントＬ１とＬ２、および、セグメントＬ３とＬ２）が、上下に隣接する画素の中心間に存在するものとする。
【００５８】
図５（Ａ）に太線で示されている輪郭線情報６が渡された場合に、Ｓ２１においてエッジリスト登録部２が生成するエッジリスト７を図４（Ａ）に示している。すなわち、セグメントＬ１については、走査線Ｓ１，Ｓ２，Ｓ３と交差するので、それぞれの交点に対応するエッジＰ１（Ｌ１）、Ｐ２（Ｌ１）、Ｐ３（Ｌ１）が、それぞれの走査線毎に登録される。このとき、セグメントＬ１は走査線と垂直であるので、リンクによるエッジの連結を行う。すなわち、エッジＰ１（Ｌ１）のリンク先としてエッジＰ２（Ｌ１）の格納位置がエッジリスト７に格納される。また、エッジＰ２（Ｌ１）のリンク先としてエッジＰ３（Ｌ１）の格納位置がエッジリスト７に格納される。図４では、このリンクを矢線で示している。なお、エッジＰ３（Ｌ１）については、リンク先は終端となる。
【００５９】
また、セグメントＬ２は走査線Ｓ１と交差するので、走査線Ｓ１とセグメントＬ２の交点に対応するエッジＰ１（Ｌ２）が、走査線Ｓ１に対応するリストに登録される。同様に、セグメントＬ３は走査線Ｓ３と交差するので、走査線Ｓ３とセグメントＬ３の交点に対応するエッジＰ３（Ｌ３）が、走査線Ｓ３に対応するリストに登録される。なお、これらのエッジについても、セグメントＬ２，Ｌ３の追跡を行うが、セグメントＬ２，Ｌ３は次の走査線まで達しておらず、次のエッジが存在しないので、リンクは終端となる。
【００６０】
このようにして、図４（Ａ）に示すように作成されたエッジリスト７は、Ｓ２４においてエッジリスト生成部３が走査線毎にエッジをソートする。まず走査線Ｓ１について登録されているエッジをソートすると、図４（Ｂ）に示すように同じエッジを示すＰ１（Ｌ１）とＰ１（Ｌ２）が並ぶことになる。ソートされたエッジを先頭から２つずつ処理して行くが、通常はこのエッジＰ１（Ｌ１）とＰ１（Ｌ２）が同時に処理対象となる。
【００６１】
Ｓ２６においてドロップアウトの判定を行うと、エッジＰ１（Ｌ１）とＰ１（Ｌ２）は同じ位置を示しているので、ドロップアウトの可能性があると判定される。そのため、まずＳ３１において、このドロップアウトの可能性があると判定されたエッジＰ１（Ｌ１）（＝Ｐ１（Ｌ２））についてビットマップ８に登録する。これにより、図５（Ｂ）にハッチングを施して示したように、ドロップアウトの補正が行われる。
【００６２】
さらに、エッジＰ１（Ｌ１）にはリンク先が格納されている。そのため、リンクの追跡処理を行う。Ｓ３４またはＳ３６のいずれかにおいてリンク先のエッジＰ２（Ｌ１）を取り出し、エッジＰ１（Ｌ１）のリンク先を終端とする。そしてＳ３１において、エッジＰ２（Ｌ１）についてビットマップ８に登録する。さらにエッジＰ２（Ｌ１）にもリンク先が格納されている。そのため、リンク先のエッジＰ３（Ｌ１）を取り出し、エッジＰ２（Ｌ１）のリンク先を終端とし、エッジＰ３（Ｌ１）についてビットマップ８に登録する。なお、エッジＰ３（Ｌ１）のリンク先は終端であるので、これ以上の追跡処理は行わない。
【００６３】
このようにしてリンク先を追跡し、ビットマップ８に登録することによって、図５（Ｃ）にハッチングを施して示すように、文字「１」の下のセリフ部が補正処理される。なお、エッジリスト７においては、上述の追跡処理後はリンク先が終端に変更されるので、図４（Ｃ）に示すように、セグメントＬ１によるリンク（矢線）は消去されている。
【００６４】
なお、ソートされたリストから取り出した２つのエッジから、ドロップアウトが発生しないと判定された場合には、Ｓ２７でビットマップ８に対してエッジ間の画素を塗りつぶす処理を実施する。
【００６５】
このようにして走査線Ｓ１に対応するリストに登録されているエッジについて、それぞれ２個ずつ処理して行く。走査線Ｓ１における処理が終了したら、図４（Ｄ）に示すように、次の走査線Ｓ２に対応するリストに登録されているエッジについての処理を行う。走査線Ｓ２については、リスト中にエッジＰ２（Ｌ１）が登録されている。このエッジは、他のエッジ（文字「１」の上部のエッジ）とともに取り出される。ドロップアウトは発生しないので、エッジＰ２（Ｌ１）を終点として塗りつぶし処理が行われる。この処理ではエッジＰ２（Ｌ１）は塗りつぶされない。しかし、上述のエッジＰ１（Ｌ１）からのリンクの追跡による補正処理によって、エッジＰ２（Ｌ１）は塗りつぶされる。なお、エッジＰ２（Ｌ１）についてはドロップアウトが発生しないと判断されているので、形状補正部４による補正処理は行われない。
【００６６】
走査線Ｓ２の処理が終了したら、次の走査線Ｓ３について処理を行う。走査線Ｓ３についてソートを行うと、エッジリスト７は図４（Ｅ）に示すようになる。走査線Ｓ３には、同じ位置のエッジＰ３（Ｌ１）、Ｐ３（Ｌ３）が存在する。そのためドロップアウトが発生すると判断され、エッジＰ３（Ｌ１）（＝Ｐ３（Ｌ３））について、ビットマップ８に登録される。この画素はエッジＰ１（Ｌ１）からリンクをたどって補正処理を行った際に既に登録されているので、画素としては何ら変わらない。
【００６７】
このようにして、図５（Ｄ）にハッチングで示す画素が塗りつぶされる。図１５（Ａ）に示したように、従来は文字「１」の下のセリフ部に凹状部である「鳥足」が発生していたが、本発明の文字・図形処理装置によれば、図５（Ｄ）に示すように「鳥足」は発生しておらず、良好な文字にビットマップ展開されていることが分かる。
【００６８】
なお、図４，図５では、図中の上下方向を走査方向として処理を行った例を示した。垂直方向の輪郭線については、図中の左右方向を走査方向として処理を行うことによって、同様にドロップアウトの補正及び「鳥足」の補正処理を行うことができる。始点から終点までの塗りつぶし処理は、いずれか一方の処理中に行うのみでよい。
【００６９】
図６は、本発明の文字・図形処理装置の実施の一形態を実現するための構成例を示すブロック図である。図中、１１はＣＰＵ、１２はＲＡＭ、１３はＲＯＭ、１４は外部記憶装置、１５はビデオインタフェース、１６はフレームバッファ、１７はプリンタインタフェースである。ＲＯＭ１３またはＲＡＭ１２には、ＣＰＵ１１が動作するためのプログラムが格納されている。ＣＰＵ１１は、このＲＯＭ１３またはＲＡＭ１２に格納されているプログラムに従って動作し、走査変換部１、エッジリスト登録部２、エッジリスト生成部３、形状補正部４、エッジリスト展開部５の機能を実行する。なお、プログラムは外部記憶装置１４に記憶されており、ＲＡＭ１２に読み出された後にＣＰＵ１１が実行する場合もある。
【００７０】
ＲＡＭ１２には、ＣＰＵ１１で実行されるプログラムのほか、ＣＰＵ１１によるエッジリスト登録部２及びエッジリスト生成部３の機能を実行することで生成されるエッジリスト７を記憶する。また、同じく形状補正部４やエッジリスト展開部５の機能を実行する際に用いられるビットマップ８を記憶する。その他、ＣＰＵ１１が実行する際に作業用としても用いられる。
【００７１】
ＲＯＭ１３には、ＣＰＵ１１で実行されるプログラムのほか、フォントの情報として輪郭線の情報を保持しておくことができる。
【００７２】
外部記憶装置１４は、例えばハードディスクやＣＤ−ＲＯＭ、ＭＯ、ＦＤ、さらにはＳＲＡＭやＲＯＭなど、デジタル情報が記憶できる記憶媒体で構成され、ＣＰＵ１１で実行されるプログラムのほか、各種のデータが格納される。格納されるデータの一つとして、例えば文字や図形の輪郭線の情報をフォントファイルとして格納しておくことができる。
【００７３】
ビデオインタフェース１５は、例えばＣＲＴなどの表示装置に接続され、表示装置に表示信号を送出して各種の表示を行うことができる。例えば本発明の文字・図形処理装置の機能を用いてビットマップに展開した文字や図形を表示させることができる。同様に、プリンタインタフェース１７は、プリンタなどの記録装置に接続され、記録装置に記録データを送出することによって記録用紙などにデータを記録することができる。例えば本発明の文字・図形処理装置の機能を用いてビットマップに展開した文字や図形を記録することができる。
【００７４】
フレームバッファ１６は、例えばビデオインタフェース１５に接続される表示装置の１画面以上、あるいはプリンタインタフェース１７に接続される記録装置における１バンドあるいは１ページ以上のビットマップを有している。例えばＣＰＵ１１が形状補正部４やエッジリスト展開部５の機能を実行する際に、ビットマップ８として直接書き込んだり、あるいは、一旦、ＲＡＭ１２内に展開した後にこのフレームバッファ１６に転送してもよい。
【００７５】
このような構成において、外部から輪郭線の情報が直接入力される場合には、ＣＰＵ１１が図１に示す各構成の機能を実行してＲＡＭ１２にビットマップ展開する。また、文字コードなどで入力される場合には、ＲＯＭ１３や外部記憶装置１４から文字コードに対応する輪郭線の情報を読み出し、ビットマップ展開する。なお、輪郭線の情報に対し、例えば指定された文字や図形の大きさに応じて拡大縮小を行ったり、その他各種の変形処理などを行ってから、本発明の文字・図形処理装置の機能を実行させてもよい。また、輪郭線の情報をもとにビットマップ展開する処理は、上述のように補正処理のために走査方向を変えて２回行い、そのうちの１回において塗りつぶし処理を行う。
【００７６】
ＲＡＭ１２に展開されたビットマップは、フレームバッファ１６の所定の位置に転送される。そして、１画面あるいは１ページなど、所定の単位のビットマップ画像が完成した時点で、あるいは一定の時間間隔で、例えばビデオインタフェース１５を介して表示装置に転送し、画像を表示させたり、あるいは、プリンタインタフェース１７を介して記録装置に転送し、記録用紙などに画像を記録することができる。また、フレームバッファ１６の内容を外部記録装置１４に格納したり、あるいは外部に出力することも可能である。
【００７７】
上述の説明ではビットマップ８をＲＡＭ１２上に設け、展開処理後にフレームバッファ１６に転送する例を示したが、本発明の文字・図形処理装置においてはビットマップを読み出すことはないので、フレームバッファ１６に対して直接、書き込むように構成することも可能である。この場合、必要となるメモリ量をさらに減らすことができる。
【００７８】
上述の実施の形態では、ドロップアウトの補正処理によって現れる凹状部（鳥足）の補正処理を、エッジリスト中に設けておいたリンクをたどることによって行った。本発明はこれに限られるものではなく、例えばドロップアウト処理を行った座標によって次以降の走査線におけるエッジを順次検索するように構成したり、あるいは、エッジにセグメントを対応付けておき、ドロップアウト処理を行ったエッジに対応するセグメントを読み出して直線の描画を別途行うなど、形状補正部４において凹状部（鳥足）を補正するための各種の方法を適用することが可能である。
【発明の効果】
以上の説明から明らかなように、本発明によれば、輪郭線の情報をビットマップ展開する際に、ドロップアウトを補正するとともに、ドロップアウトの補正処理によって従来発生していた「鳥足」と呼ばれる凹状部についても補正することができる。これによって、例えば小サイズや低解像度での文字や図形の出力時においても、良好な形状でビットマップを出力することができるという効果がある。
【図面の簡単な説明】
【図１】  本発明の文字・図形処理装置の実施の一形態を示す概略構成図である。
【図２】  本発明の文字・図形処理装置の実施の一形態における動作の一例を示すフローチャートである。
【図３】  本発明の文字・図形処理装置の実施の一形態においてドロップアウトが発生する場合の動作の一例を示すフローチャートである。
【図４】  本発明の文字・図形処理装置の実施の一形態における動作の一例において遷移するエッジリストの状態の一例を示す説明図である。
【図５】  本発明の文字・図形処理装置の実施の一形態における動作の一例において遷移するビットマップの状態を示す説明図である。
【図６】  本発明の文字・図形処理装置の実施の一形態を実現するための構成例を示すブロック図である。
【図７】  輪郭線と、その輪郭線から得られるビットマップの一例の説明図である。
【図８】  輪郭線の内部の画素であるか否かを判定する一方法の説明図である。
【図９】  スキャンコンバージョン法による塗りつぶし処理の説明図である。
【図１０】  スキャンコンバージョン法による塗りつぶし処理の具体例の説明図である。
【図１１】  ドロップアウトの一例の説明図である。
【図１２】  ドロップアウトの別の例の説明図である。
【図１３】  ドロップアウトの補正を含むスキャンコンバージョン法による塗りつぶし処理の具体例の説明図である。
【図１４】  エッジリストを用いたスキャンコンバージョン法による塗りつぶし処理の具体例の説明図である。
【図１５】  ドロップアウト処理による不具合の一例の説明図である。
【符号の説明】
１…走査変換部、２…エッジリスト登録部、３…エッジリスト生成部、４…形状補正部、５…エッジリスト展開部、６…輪郭線情報、７…エッジリスト、８…ビットマップ、１１…ＣＰＵ、１２…ＲＡＭ、１３…ＲＯＭ、１４…外部記憶装置、１５…ビデオインタフェース、１６…フレームバッファ、１７…プリンタインタフェース。
【図１】
0003879804.tif 000002
【図２】
0003879804.tif 000003
【図３】
0003879804.tif 000004
【図４】
0003879804.tif 000005
【図５】
0003879804.tif 000006
【図６】
0003879804.tif 000007
【図７】
0003879804.tif 000008
【図８】
0003879804.tif 000009
【図９】
0003879804.tif 000010
【図１０】
0003879804.tif 000011
【図１１】
0003879804.tif 000012
【図１２】
0003879804.tif 000013
【図１３】
0003879804.tif 000014
【図１４】
0003879804.tif 000015
【図１５】
0003879804.tif 000016