(57)【特許請求の範囲】
【請求項１】
描画する文字の輪郭線を走査し、該走査を行う走査線と前記輪郭線との交点からエッジを順次選択してエッジリストに登録し、該エッジリストに基づいて前記エッジのうち所定のエッジ間の画素を反転することで文字を表現してビットマップ上に展開する画像処理方法において、
走査を行う走査線と前記輪郭線との交点から選択したエッジを２進木構造のデータとして順次登録するとともに、該選択したエッジの座標値と同一の座標値のエッジが該２進木構造のデータに既に登録されている場合には、該同一の座標値のエッジを無効にして該選択したエッジをドロップアウトエッジとして登録し、該２進木構造のデータに基づいてエッジリストを作成することを特徴とする画像処理方法。
【請求項２】
前記選択したエッジは、前記２進木構造の根または節点に現に登録されているエッジの座標値と前記選択したエッジの座標値との大小関係に基づいて決定される該２進木構造の節点に登録され、該２進木構造のデータに前記選択したエッジの座標値と同一の座標値のドロップアウトエッジが既に登録されている場合には、該ドロップアウトエッジの座標値が前記選択したエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録されることを特徴とする請求項１記載の画像処理方法。
【請求項３】
前記ドロップアウトエッジは、前記２進木構造のデータに該ドロップアウトエッジの座標値と同一の座標値のエッジが登録されていない場合には前記大小関係に基づいて決定される節点に登録され、前記ドロップアウトエッジの座標値と同一の座標値のエッジが既に登録されている場合には該ドロップアウトエッジの座標値が該登録されているエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録されることを特徴とする請求項２記載の画像処理方法。
【請求項４】
前記エッジリストの作成は、前記２進木構造の根および節点に登録されているエッジの座標値を所定の順序で読み出すことで行うことを特徴とする請求項１乃至３のいずれかに記載の画像処理方法。
【請求項５】
前記走査は、主走査方向と該主走査方向に直交する副走査方向から行い、前記主走査方向の走査から選択されたエッジを第１の２進木構造のデータに登録し、前記副走査方向の走査から選択されたエッジを第２の２進木構造のデータに登録するとともに、前記副走査方向の走査から選択されたエッジがドロップアウトエッジとして登録される場合には、該ドロップアウトエッジを前記第１の２進木構造のデータに登録することを特徴とする請求項１乃至４のいずれかに記載の画像処理方法。
【請求項６】
描画する文字の輪郭線を走査し、該走査を行う走査線と前記輪郭線との交点からエッジを順次選択してエッジリストに登録し、該エッジリストに基づいて前記エッジのうち所定のエッジ間の画素を反転することで文字を表現してビットマップ上に展開する画像処理装置において、
走査を行う走査線と前記輪郭線との交点から選択したエッジを２進木構造のデータとして順次登録するとともに、該選択したエッジの座標値と同一の座標値のエッジが該２進木構造のデータに既に登録されている場合には、該同一の座標値のエッジを無効にして該選択したエッジをドロップアウトエッジとして登録するエッジ登録手段と、
前記エッジ登録手段により前記２進木構造のデータに登録されたエッジに基づいてエッジリストを生成するエッジリスト作成手段と
を具備することを特徴とする画像処理装置。
【請求項７】
前記エッジ登録手段は、
選択した登録エッジを、該エッジの座標値と前記２進木構造の根または節点に現に登録されているエッジの座標値との大小関係に基づいて決定される節点に登録し、該２進木構造のデータに前記選択したエッジの座標値と同一の座標値のドロップアウトエッジが既に登録されている場合には、該ドロップアウトエッジの座標値が前記選択したエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録することを特徴とする請求項６記載の画像処理装置。
【請求項８】
前記エッジ登録手段は、
前記２進木構造のデータに、登録するドロップアウトエッジの座標値と同一の座標値のエッジが登録されていない場合には前記大小関係に基づいて決定される節点に該ドロップアウトエッジを登録し、登録するドロップアウトエッジの座標値と同一の座標値のエッジが既に登録されている場合には該ドロップアウトエッジの座標値が前記登録するエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に該ドロップアウトエッジを登録することを特徴とする請求項７記載の画像処理装置。
【請求項９】
前記エッジリスト作成手段は、
前記２進木構造の根および節点に登録されているエッジの座標値を所定の順序で読み出してエッジリストを作成することを特徴とする請求項６乃至８のいずれかに記載の画像処理装置。
【請求項１０】
ドロップアウト判定手段をさらに具備するとともに、
主走査方向と該主走査方向に直交する副走査方向から前記走査を行い、
前記エッジ登録手段は、前記主走査方向の走査から選択されたエッジを第１の２進木構造のデータに登録し、前記副走査方向の走査から選択されたエッジを第２の２進木構造のデータに登録し、
前記ドロップアウト判定手段は、前記副走査方向の走査から選択されたエッジが前記第２の２進木構造に既に登録されていた場合に、該選択されたエッジをドロップアウトエッジと判定して前記第１の２進木構造のデータに登録すること
を特徴とする請求項６乃至９のいずれかに記載の画像処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、画像処理方法および装置に関し、特に、文字デザイン情報をアウトライン情報で格納し、小サイズの文字出力時にドロップアウトを補正する画像処理方法および装置に関する。
【０００２】
【従来技術】
ページプリンタやディスプレイ等のビットマップスクリーンをベースとする出力装置では、画素が細かくなる、つまり、高解像度になるにしたがって、同じサイズの文字や図形を表示するために多くのデータが必要となる。特に、決まった輪郭をもつ文字情報においても、サイズ毎にビットマップデータを持つ必要があり効率が悪いものとなる、そのため、文字情報においてはサイズ毎にビットマップデータを持つのではなく、アウトライン情報を拡大または縮小してから文字の輪郭線の内部を塗り潰すことで文字を表示する方法が有利となる。
【０００３】
しかし、輪郭線内部を塗り潰す方法では小サイズの文字を出力（表示）する場合には、輪郭線の間隔が狭くなりすぎて塗り潰しに抜け（ドロップアウト）が発生することがある。このドロップアウトが生じる現象を回避するためには、大きく分けてアウトライン情報自体に小サイズ出力時の輪郭線変更情報を持たせる方法と、処理系にドロップアウト発生場所を検知させ修正を行う方法の２つがある。前者は一般に処理が速く文字のデザインの崩れもデータ作成段階で補正できるが、文字数が増えた場合にデータサイズが増大し、データ作成時の手間も増える。後者ではデータの変更の必要はないが、処理が遅くなり、前者の場合と比較して文字のデザインが崩れる場合もある。したがって、現在では前者と後者を組み合わせてしようするのが主流となっている。
【０００４】
なお、この発明は、上述の２つの方法のうち後者の方法に関するものであるため、後者の方法についてさらに説明する。
【０００５】
図１４に文字の輪郭線とその輪郭線から得られるビットマップを示す。同図に示すように文字を出力（表示）する場合には、出力しようとする文字の輪郭線の内側の画素を他の画素と反転させたビットマップを出力する。また、各画素は、図１５に示すように高さ１、幅１の正方形をしており、その４隅に整数座標値がくる。画素の座標は左下隅の座標値で表現し、これをピクセル座標と呼ぶことにする。また、図１６に示すように輪郭線の内側に画素の中心点がある場合、その画素は輪郭線の内側であると判断される。
【０００６】
次に、スキャンコンバージョンの一例を示す。この例においては、輪郭線の方向を考慮しないＥＶＥＮ−ＯＤＤルールと呼ばれる条件で輪郭線の内外を判定している。
【０００７】
ここで、図１７に示すようにｘ軸方向に画素の中心点を結んだ線を走査線または主走査線、ｙ軸方向に画素の中心点を結んだ線を副走査線と呼ぶことにする。輪郭線の内側を求める際には、図１８（ａ）に示すように輪郭線と走査線の交点を求め、交点とｙ座標が等しく、交点の右側にある画素（画素の中心点）のうち最も近い画素を選択する。この画素をエッジと呼ぶが、エッジは、例えば上記交点のｘ座標値の小数点第１位を四捨五入することで求めることができる。
【０００８】
さて、全ての輪郭線についてエッジを選択したら、図１８（ｂ）に示すように各走査線についてエッジに挟まれた画素を反転する。このとき、反転する画素の始点または終点となるエッジのうち、始点となる画素は反転させるが、終点となる画素は反転させない。
【０００９】
また、エッジを選択する段階でエッジが重なった場合、その重なりが偶数個であるあればそのエッジを削除する。この操作を実施しないと塗り潰しが正確に行われない。
なお、スキャンコンバージョンはドロップアウトが発生しない限り副走査線方向から実施しても同様の画像が得られる。
【００１０】
ところで、選択されたエッジの登録を最も単純に行うには図１９（ａ）に示すように実際のビットマップで画素を反転させればよい。しかし、文字のサイズが大きくなった場合や高解像度の場合には塗り潰しの段階で全ての画素を調べなければならないので、速度的に不利であり、単純な構造のために複雑なペイントルールが利用しにくく、輪郭線の方向等のエッジの情報をつけるとメモリ効率が悪くなるといった欠点がある。
【００１１】
そのため、図１９（ｂ）に示すように各走査線をリストで管理する方法がある。これは、選択したエッジをリストに登録していき、全てのエッジが登録されたところで各リストをソートし、塗り潰し過程ではこのリストからエッジを２つずつ取り出してこれを始点および終点とする。なお、このリストはエッジリストと呼ばれる。
【００１２】
ここで、図２０にドロップアウトの発生例を示す。
図２０（ａ）に示すように２つの輪郭線が隣接する画素の中心点の間を通った場合には、反転する画素が存在しないため、ドロップアウトが発生する。これは図２０（ｂ）に示すように２つの輪郭線の走査線との各交点から選択されるエッジが重なるために生じるもので、両輪郭線の間が輪郭線の外側であれば問題はないが、エッジの選択の段階では通常内側か外側かは判らない。このような画素はスキャンコンバージョンの際に削除することでドロップアウトを防止できる。他だし、このような画素はエッジとは別のビットマップまたはエッジリストに登録する必要がある。また、図２０（ｃ）は、輪郭線と走査線の交点から求めたエッジでは発見できないドロップアウトの例を示しており、この場合には副走査線方向からエッジを選択することでドロップアウトを発見できる。この例から判るように全てのドロップアウトを発見するには、走査線方向と副走査線方向の両方から実施する必要がある。
【００１３】
ドロップアウトの発生を防止、または抑制する技術としては、特開平８−８７６０２号公報で開示されている「アウトラインフォント描画装置」や特開平８−９５５４５号公報で開示されている「アウトラインフォント描画装置」等がある。
【００１４】
特開平８−８７６０２号公報記載の「アウトラインフォント描画装置」では、走査線方向と副走査線方向で各々スキャンコンバージョンを行い、別々のビットマップを作成し、両者を合成することでドロップアウトの無いビットマップ画像を得ている。しかし、このアウトラインフォント描画装置では、常に走査線方向と副走査線方向の両方向からスキャンコンバージョンを行っており、ドロップアウトの検出に要する時間が長くなるとともに、ドロップアウトが発生する可能性の低い文字または文字の一部分をスキャンコンバージョンする際には無駄な処理を行っていることになる。
【００１５】
また、特開平８−９５５４５号公報記載の「アウトラインフォント描画装置」では、通常は各画素の中心部に設定されるスキャンラインをずらしてスキャンコンバージョンを行い、これによりドロップアウトの発生を抑制している。ところが、スキャンラインをずらすことでドロップアウトの発生を抑制しているために、本来作成したい画像とは異なる画像ができる可能性があるとともに、スキャンラインの移動方向を輪郭線の方向から判断しているので塗り潰しのルールによっては適用できないものもある。
【００１６】
さて、図２１は、ドロップアウトの発生と検出の例を示しており、図２１（ａ）は走査線方向からのスキャンコンバージョンでドロップアウトが発生した例を、図２１（ｂ）は走査線方向からのドロップアウトの検出結果を、図２１（ｃ）は副走査線方向からのドロップアウトの検出結果を示している。このような場合には、図２１（ａ）、（ｂ）、（ｃ）の各画像を合成することで、図２１（ｄ）に示すような画素の抜け（ドロップアウト）の無い画像を得ることができる。
【００１７】
このような処理は、文字のサイズが十分大きく、ドロップアウトが発生しなければ輪郭線からのエッジの選択は走査線または副走査線方向のどちらか一方から実施すればよいが、文字のサイズが小さくドロップアウトを処理する必要がある場合は、両方向からエッジの選択を実施しなければならい。
【００１８】
【発明が解決しようとする課題】
上述のように、従来の画像処理装置では、一般に水平（主走査）方向および垂直（副走査）方向の両方向からスキャンコンバージョンを行い、エッジリストへエッジを登録している。ドロップアウトの補正を行う場合には、エッジリストに登録されているエッジを水平および垂直の両方向でソートが必要となり時間が掛かるうえ、両方向から得られた各エッジをエッジリストのまま合成するとさらに時間が掛かるため、ビットマップを使用して合成を行っていた。そのため、エッジリストを使用できる（エッジリストを直接入力して使用できる）出力装置を高速に使用できず、また、ビットマップの使用のために大量のメモリが必要であった。
【００１９】
そこで、この発明は、高速にエッジリストを作成でき、使用するメモリの容量を少なくすることのできる画像処理方法および装置を提供することを目的とする。
【００２０】
【課題を解決するための手段】
上述した目的を達成するため、請求項１の発明は、描画する文字の輪郭線を走査し、該走査を行う走査線と前記輪郭線との交点からエッジを順次選択してエッジリストに登録し、該エッジリストに基づいて前記エッジのうち所定のエッジ間の画素を反転することで文字を表現してビットマップ上に展開する画像処理方法において、走査を行う走査線と前記輪郭線との交点から選択したエッジを２進木構造のデータとして順次登録するとともに、該選択したエッジの座標値と同一の座標値のエッジが該２進木構造のデータに既に登録されている場合には、該同一の座標値のエッジを無効にして該選択したエッジをドロップアウトエッジとして登録し、該２進木構造のデータに基づいてエッジリストを作成することを特徴とする。
【００２１】
また、請求項２の発明は、請求項１の発明において、前記選択したエッジは、前記２進木構造の根または節点に現に登録されているエッジの座標値と前記選択したエッジの座標値との大小関係に基づいて決定される該２進木構造の節点に登録され、該２進木構造のデータに前記選択したエッジの座標値と同一の座標値のドロップアウトエッジが既に登録されている場合には、該ドロップアウトエッジの座標値が前記選択したエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録されることを特徴とする。
【００２２】
また、請求項３の発明は、請求項２の発明において、前記ドロップアウトエッジは、前記２進木構造のデータに該ドロップアウトエッジの座標値と同一の座標値のエッジが登録されていない場合には前記大小関係に基づいて決定される節点に登録され、前記ドロップアウトエッジの座標値と同一の座標値のエッジが既に登録されている場合には該ドロップアウトエッジの座標値が該登録されているエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録されることを特徴とする。
【００２３】
また、請求項４の発明は、請求項１乃至３のいずれかの発明において、前記エッジリストの作成は、前記２進木構造の根および節点に登録されているエッジの座標値を所定の順序で読み出すことで行うことを特徴とする。
【００２４】
また、請求項５の発明は、請求項１乃至４のいずれかの発明において、前記走査は、主走査方向と該主走査方向に直交する副走査方向から行い、前記主走査方向の走査から選択されたエッジを第１の２進木構造のデータに登録し、前記副走査方向の走査から選択されたエッジを第２の２進木構造のデータに登録するとともに、前記副走査方向の走査から選択されたエッジがドロップアウトエッジとして登録される場合には、該ドロップアウトエッジを前記第１の２進木構造のデータに登録することを特徴とする。
【００２５】
また、請求項６の発明は、描画する文字の輪郭線を走査し、該走査を行う走査線と前記輪郭線との交点からエッジを順次選択してエッジリストに登録し、該エッジリストに基づいて前記エッジのうち所定のエッジ間の画素を反転することで文字を表現してビットマップ上に展開する画像処理装置において、走査を行う走査線と前記輪郭線との交点から選択したエッジを２進木構造のデータとして順次登録するとともに、該選択したエッジの座標値と同一の座標値のエッジが該２進木構造のデータに既に登録されている場合には、該同一の座標値のエッジを無効にして該選択したエッジをドロップアウトエッジとして登録するエッジ登録手段と、前記エッジ登録手段により前記２進木構造のデータに登録されたエッジに基づいてエッジリストを生成するエッジリスト作成手段とを具備することを特徴とする。
【００２６】
また、請求項７の発明は、請求項６の発明において、前記エッジ登録手段は、選択した登録エッジを、該エッジの座標値と前記２進木構造の根または節点に現に登録されているエッジの座標値との大小関係に基づいて決定される節点に登録し、該２進木構造のデータに前記選択したエッジの座標値と同一の座標値のドロップアウトエッジが既に登録されている場合には、該ドロップアウトエッジの座標値が前記選択したエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録することを特徴とする。
【００２７】
また、請求項８の発明は、請求項７の発明において、前記エッジ登録手段は、前記２進木構造のデータに、登録するドロップアウトエッジの座標値と同一の座標値のエッジが登録されていない場合には前記大小関係に基づいて決定される節点に該ドロップアウトエッジを登録し、登録するドロップアウトエッジの座標値と同一の座標値のエッジが既に登録されている場合には該ドロップアウトエッジの座標値が前記登録するエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に該ドロップアウトエッジを登録することを特徴とする。
【００２８】
また、請求項９の発明は、請求項６乃至８のいずれかの発明において、前記エッジリスト作成手段は、前記２進木構造の根および節点に登録されているエッジの座標値を所定の順序で読み出してエッジリストを作成することを特徴とする。
【００２９】
また、請求項１０の発明は、請求項６乃至９のいずれかの発明において、ドロップアウト判定手段をさらに具備するとともに、主走査方向と該主走査方向に直交する副走査方向から前記走査を行い、前記エッジ登録手段は、前記主走査方向の走査から選択されたエッジを第１の２進木構造のデータに登録し、前記副走査方向の走査から選択されたエッジを第２の２進木構造のデータに登録し、前記ドロップアウト判定手段は、前記副走査方向の走査から選択されたエッジが前記第２の２進木構造に既に登録されていた場合に、該選択されたエッジをドロップアウトエッジと判定して前記第１の２進木構造のデータに登録することを特徴とする。
【００３４】
【発明の実施の形態】
以下、この発明に係わる画像処理方法および装置の一実施例を添付図面を参照して詳細に説明する。
【００３５】
図１は、この発明に係わる画像処理装置の構成を示すブロック図である。
画像処理装置１０は、アウトライン情報の拡大縮小等の座標変換と曲線（輪郭線情報）を画素に応じて滑らかに見える大きさの直線に分割（複数の直線による近似）を行う座標変換手段１と、走査線および副走査線と輪郭線の交点を検出してエッジリストの作成およびドロップアウトの検出を行う交点・ドロップアウト検出手段２、エッジリストからビットマップを生成するビットマップ展開手段３を具備して構成される。また、交点・ドロップアウト検出手段２は、走査線と輪郭線の交点からエッジを選択して後述する２分探索木に登録するエッジ登録手段２ａと副走査線方向から選択されたエッジに基づいてドロップアウトを検出するドロップアウト検出手段２ｂ、エッジを登録した２分探索木に基づいてエッジリストを作成するエッジリスト作成手段２ｃを具備して構成される。
【００３６】
この画像処理装置１０は、実際には図２に示すようにＣＰＵ１１と、ＲＡＭ１２、ＲＯＭ１３、外部記憶装置１４、ビデオＩ／Ｆ（インタフェイス）１５、フレームバッファ１６、プリンタＩ／Ｆ（インタフェイス）１７を具備して構成される。
【００３７】
図１に示した座標変換手段１と交点・ドロップアウト検出手段２、ビットマップ展開手段３は、ＲＡＭ１２またはＲＯＭ１３に収められたプログラムによりＣＰＵ１１上で構成される。また、ＲＡＭ１２には上述のエッジリスト等が構成され、ＲＯＭ１３および外部記憶装置１４にはアウトラインフォントデータが格納されている。フレームバッファ１６は、ビットマップ展開手段３が展開したビットマップ画像を一時的に記憶し、この画像をビデオＩ／Ｆ１５に接続されたディスプレイ（不図示）またはプリンタＩ／Ｆ１７に接続されたページプリンタ（不図示）等の外部出力装置へ出力する。
【００３８】
次に、画像処理装置１０の動作について説明する。
画像処理装置１０では、エッジリストの作成に先立って、走査により選択されたエッジを２分探索木（２進木構造のデータ）に登録する。この２分探索木はエッジリスト１つに相当し、走査線方向と副走査線方向で各々走査線（副走査線）毎に２分探索木を用意する。
【００３９】
ここで、２分探索木へのエッジの登録のルールを説明する。
図３は、２分探索木の概念図である。
同図に示すように、根５０には節点５１−１、５１−２が接続され、根５０の左側の節点５１−１には根５０に登録されている値（１０）よりも小さい値（５）が登録されており、根５０の右側の節点５１−２には根５０に登録されている値よりも大きい値（１２）が登録されている。
【００４０】
また、節点５１−１（値５）には左側に小さい値（３）が登録された節点５２−１、右側に大きい値（７）が登録された節点５２−２が接続され、節点５１−２（値１２）には右側に大きい値（２０）が登録された節点５２−４が接続されている。
同様に、節点５２−１には節点５３−１が、節点５２−４には節点５３−７と節点５３−８が接続されている。
【００４１】
この根５０または節点５１−１乃至５３−８に登録されている値は、走査線方向から選択されたエッジを登録する２分探索木ではエッジのｘ座標値であり、副走査線方向から選択されたエッジを登録する２分探索木ではエッジのｙ座標値である。
【００４２】
ここで、新たに登録を行う場合、例えば、新たな値（８）を登録するときは、図４（ａ）に示すように、まず登録する値（８）と根５０の値（１０）を比較し、登録する値の方が小さければ、次に左側の節点５１−１の値（５）と比較する。この場合、登録する値（８）の方が大きいので、次に右側の節点５２−２の値（７）との比較を行う。この場合にも登録する値（８）の方が大きいので右側の節点との値を比較しようとするが、節点が存在しないため、ここに新たな節点５３−４を設定して値（８）を登録する。
【００４３】
さらに、値（１８）を登録しようとする場合には、同様の方法で図４（ｂ）に示すように、根５０と節点５１−２、５２−４、５３−７との比較を行って、新たな節点５４−１４に値（１８）を登録する。
【００４４】
また、登録しようとする値が既に登録されている場合、つまり、登録しようとするエッジと同一座標のエッジが既に登録されている場合、例えば、図５（ａ）に示すような２分探索木に値（１２）を登録しようとする場合には、節点５１−２に同じ値（１２）が登録されているので、これを図５（ｂ）に示すように無効な節点６１−２に設定し、さらにこの値をドロップアウトとして（走査線方向の）２分探索木に登録する。なお、登録しようとする値が無効な節点として登録されていた場合には、これを有効な節点に登録し直す。
【００４５】
図６は、２分探索木へのドロップアウトの登録およびドロップアウトが登録されている２分探索木へのエッジの登録のルールを示した図である。
２分探索木へのドロップアウトの登録とドロップアウトが登録されている２分探索木へのエッジの登録は、どちらの場合も同じ座標値のドロップアウト、エッジが登録されていない状態では、通常のエッジの登録と同様に行う。例えば、図６（ａ）に示す２分探索木にドロップアウト（値１３）を登録する場合には、図６（ｂ）に示すように節点５１−２の左側にドロップアウトを示す節点７２−３を設定して登録する。
【００４６】
また、登録しようとするドロップアウトと同じ座標のエッジが既に登録されている場合は、エッジの値よりもドロップアウトの値の方が大きいものと見做して登録を行う。例えば、図６（ｃ）に示す２分探索木にドロップアウト（値１２）を登録する場合には、節点６１−２に無効なエッジ（値１２）が登録されているため、ドロップアウト（値１２）は、図６（ｄ）に示すようにエッジ（値１２）よりも大きい値と見做され、節点５３−７の左側にドロップアウトを示す節点７４−１３を設定して登録される。同様に図６（ｅ）に示す２分探索木にドロップアウト（値３）を登録する場合には、節点５２−１にエッジ（値３）が登録されているため、ドロップアウト（値３）は、図６（ｆ）に示すようにエッジ（値３）よりも大きい値と見做され、節点５２−１の右側にドロップアウトを示す節点７３−２を設定して登録される。
【００４７】
同様に、エッジを登録しようとする場合に、同じ座標値のドロップアウトが既に登録されている場合は、エッジの値よりもドロップアウトの値の方が大きいものと見做して登録を行う。例えば、図６（ｇ）に示す２分探索木にエッジ（値７）を登録する場合には、節点７２−２にドロップアウト（値７）が登録されているため、エッジ（値７）は、図６（ｈ）に示すようにドロップアウト（値７）よりも小さい値と見做され、節点７２−２の左側にエッジを示す節点５３−３を設定して登録される。
【００４８】
このようにエッジとドロップアウトの値が同一であった場合に、エッジの値よりもドロップアウトの値の方が大きいものと見做すのは、後述する方法で２分探索木からエッジリストを作成すると値の小さい節点が先に処理されることに関係する。これは、ドロップアウトに対する処理が輪郭線の内側か外側かで異なるため、エッジリストにはドロップアウトよりも先にエッジが登録されると都合がよく、そのためにエッジの値をドロップアウトの値よりも小さい値と見做すことになる。
【００４９】
次に、図７乃至１１を参照して画像処理装置１０の動作を説明する。
図７乃至１１は、夫々画像処理装置１０の動作の流れを示すフローチャートである。
【００５０】
画像処理装置１０は、ＣＰＵ１１が図示しないインタフェース等を通じて図示しないＲＡＭ（またはＲＡＭ１２）上に貯えられた画像情報等を読み込む。画像情報が文字コードであればＲＯＭ１３または外部記憶装置１４からアウトラインフォントデータを読みだして画像生成プログラムの実行を開始する（図７、ステップ１０１）。
【００５１】
次に、ＣＰＵ１１は、ＲＡＭ１３上に走査線方向の２分探索木と副走査線方向の２分探索木、エッジリスト等を作成し、これらリストを初期化する（ステップ１０２）。続いて、ＣＰＵ１１は画像変換手段１を実行して、輪郭線（アウトライン）を出力したい大きさに座標変換し（ステップ１０３）、この輪郭線を短い複数の直線に分割する（曲線部は直線近似、ステップ１０４）。
【００５２】
輪郭線の分割が終了すると、ＣＰＵ１１は、交点・ドロップアウト検出手段２を実行して、エッジの選択と２分探索木への登録およびドロップアウトの検出を行い（ステップ１０５）、２分探索木からエッジリストの作成を行う（ステップ１０６）。なお、ステップ１０５および１０６の動作の詳細は後述する。
【００５３】
次に、ＣＰＵ１１は、ビットマップ展開手段３を実行して、エッジリストからビットマップを生成し（ステップ１０７）、フレームバッファ１６へ出力する（ステップ１０８）。
【００５４】
ここで、図示しない出力装置（ディスプレイやページプリンタ等）が、一定時間間隔またはＣＰＵ１１からの終了信号に応じてフレームバッファ１６を調べ、登録されているビットマップを出力することで画像処理装置１０は動作を終了する（ステップ１０９）。
【００５５】
次に、上述のステップ１０５におけるエッジの選択と２分探索木への登録およびドロップアウトの検出処理の詳細について説明する。
交点・ドロップアウト検出手段２は、まず、直線に分割された最初（予め設定した順序の最初であり、どのような順序でも良い）の輪郭線をセットし（図８、ステップ２０１）、走査線との交点（複数）を検出する（ステップ２０２）。続いて、検出された交点のｙ座標値の小数点以下を切り捨て、ｘ座標値の小数点以下を四捨五入してピクセル座標を取得する（ステップ２０３）。このピクセル座標は、交点とｙ座標が等しく、交点の右側にある画素（画素の中心点）のうち最も近い画素であるので、これをエッジとして走査線方向の２分探索木に順次登録する（ステップ２０４）。走査線方向の２分探索木への登録は、エッジ登録手段２ａを実行し、まず、最初のエッジをセットし（図９、ステップ３０１）、その座標値のｙ座標値から登録する２分探索木を選択する。次に、エッジを２分探索木へ上述のルールに従って登録する（ステップ３０２）。ここで、登録したエッジがドロップアウトであれば（ステップ３０３でＹＥＳ）、そのドロップアウト（の座標を）セットし（ステップ３０４）、２分探索木へ登録する（ステップ３０２）。
【００５６】
登録したエッジがドロップアウトでなければ（ステップ３０３でＮＯ）、これらの処理を最後のエッジを登録するまで（ステップ３０５でＮＯ）、次のエッジをセットして繰り返し（ステップ３０６）、最後のエッジを登録すると（ステップ３０５でＹＥＳ）、ステップ２０５（図８）へ進む。
【００５７】
次に、セットされている輪郭線と副走査線の交点を検出し（ステップ２０５）、検出された交点のｘ座標値の小数点以下を切り捨て、ｙ座標値の小数点以下を四捨五入してピクセル座標を取得し（ステップ２０６）、これをエッジとして副走査方向の２分探索木に順次登録する（ステップ２０７）。副走査線方向の２分探索木への登録は、走査線エッジリストへの登録は、ドロップアウト検出手段２ｂを実行し、まず、最初のエッジをセットし（図１０、ステップ４０１）、その座標値のｘ座標値から登録する２分探索木を選択する。次に、エッジを２分探索木へ上述のルールに従って登録する（ステップ４０２）。ここで、登録したエッジがドロップアウトであれば（ステップ４０３でＹＥＳ）、そのドロップアウトを走査線方向の２分探索木に登録する（ステップ４０４）。この登録はエッジ登録手段２ａが行い、登録の方法は上述した方法と同じであるので説明は省略する。
【００５８】
ドロップアウトを走査線方向の２分探索木に登録するか（ステップ４０４）、登録したエッジがドロップアウトでなければ（ステップ４０３でＮＯ）、これらの処理を最後のエッジを登録するまで（ステップ４０５でＮＯ）、次のエッジをセットして繰り返し（ステップ４０６）、最後のエッジを登録すると（ステップ４０５でＹＥＳ）、ステップ２０８（図８）へ進む。
【００５９】
これらの処理（ステップ２０２乃至２０７）は、最後の輪郭線に対する処理が終了するまでは（ステップ２０８でＮＯ）、次の輪郭線をセットして（ステップ２０９）、繰り返し、最後の輪郭線に対する処理が終了すると（ステップ２０８でＹＥＳ）、ステップ１０５（図７）の処理を終了して、ステップ１０６へ進む。
【００６０】
次に、上述のステップ１０６における２分探索木からエッジリストの作成処理の詳細について説明する。
交点・ドロップアウト検出手段２は、エッジリスト作成手段２ｃを実行し、まず、走査線方向の２分探索木の最初のエッジ（根に登録されているエッジまたはドロップアウト）をセットする（図１１、ステップ５０１）。ここで、根の左側に節点があればステップ５０２以下の処理を再帰呼び出しして行い（ステップ５０２）、再帰呼び出しを終了した場合や行わなかった場合には、現にセットされているものがドロップアウトであれば（ステップ５０３でＹＥＳ）、そのドロップアウトが輪郭線の外側であった場合に（図１２（ａ）に示すようにドロップアウトが輪郭線の内側であれば登録する必要がなく、図１２（ｂ）に示すようにドロップアウトが輪郭線の外側であれば登録の必要がある）、１画素分の始点および終点をエッジリストに登録し（ステップ５０４）、現にセットされているものがエッジであれば（ステップ５０３でＮＯ）、そのエッジが有効な場合にエッジリストに登録する（ステップ５０５）。次に、現在処理している根または節点の右側に節点があればステップ５０２以下の処理を再帰呼び出しして行い（ステップ５０６）、全ての再帰呼び出しを終了した場合や行わなかった場合には、エッジリストの作成処理を終了してステップ１０７（図７）に進む。
【００６１】
ここで、図１３を参照して実際の２分探索木で図１１に示したエッジリストの作成を行った場合の一例を説明する。
まず、根５０をセットすると（ステップ５０１）、根５０の左側には節点５１−１が存在するので再帰呼び出しを行う（ステップ５０２−０、−ｎは再帰呼び出しを行っている回数を示し、０は再帰呼び出しを行っていない状態のステップを示す）。
【００６２】
次に、セットされている節点５１−１の左側には節点５２−１が存在するため再び再帰呼び出しを行う（ステップ５０２−１）。
このように再帰呼び出しにより処理を行うと、節点５３−１に対してはステップ５０２−２で再帰呼び出しされたステップ５０４−３の処理が行われ、節点５２−１に対しては、ステップ５０４−３の処理の後でステップ５０２−２に戻り、ステップ５０４−２の処理が行われる。また、節点５２−２に対しては、ステップ５０４−２の処理の後でステップ５０２−１に戻り節点５１−１に対する処理（ステップ５０４−１）が行われた後で、ステップ５０６−１で呼び出されたステップ５０４−２の処理が行われる。
【００６３】
したがって、各処理は節点５３−１（値１）から節点５２−１（値３）、節点５１−１（値５）、節点５２−２（値７）、根５０（値１０）、節点５１−２（値１２）、節点５３−７（値１５）、節点５２−４（値２０）、節点５３−８（値２２）の順に行われ、ソートを行わなくとも昇順にエッジリストへの登録を行うことができる。
【００６４】
なお、上述の実施例では、エッジリストを走査線方向の２分探索木から作成した場合を示したが、当然のことながら上述の実施例の走査線方向と副走査線方向を入れ替えても同様の処理が可能である。
【００６５】
また、２分探索木へのエッジの登録ルールおよび２分探索木からのエッジリストの作成のルールは、上述の実施例のものに限らず、他のルールを適用できることを付記しておく。
【００６６】
【発明の効果】
以上説明したように、この発明によれば、走査により選択したエッジを２分探索木に登録するとともに、検出されたドロップアウトをもその２分探索木に登録し、２分探索木からエッジリストを作成するように構成したので、
エッジリストのソートが必要無く、２方向のビットマップを合成することによるドロップアウトの補正も行う必要がないので、使用するメモリ容量を低減し、高速に処理を行うことができる。
【図面の簡単な説明】
【図１】この発明に係わる画像処理装置の構成を示すブロック図。
【図２】画像処理装置１０の実際の構成を示すブロック図。
【図３】２分探索木の概念図。
【図４】新たな登録を行う場合のルールを示した図。
【図５】登録しようとする値が既に登録されている場合のルールを示した図。
【図６】２分探索木へのドロップアウトの登録およびドロップアウトが登録されている２分探索木へのエッジの登録のルールを示した図。
【図７】画像処理装置１０の動作の流れを示すフローチャート（１）。
【図８】画像処理装置１０の動作の流れを示すフローチャート（２）。
【図９】画像処理装置１０の動作の流れを示すフローチャート（３）。
【図１０】画像処理装置１０の動作の流れを示すフローチャート（４）。
【図１１】画像処理装置１０の動作の流れを示すフローチャート（５）。
【図１２】ドロップアウト登録の必要の有無を示した図。
【図１３】２分探索木で図１１に示したエッジリストの作成を行った場合の作成順序を示した図。
【図１４】文字の輪郭線とその輪郭線から得られるビットマップを示した図。
【図１５】画素の形状を示した図。
【図１６】各画素が輪郭線の内外のいずれかかを判定する方法を示した図。
【図１７】走査線および副走査線を示した図。
【図１８】文字の描画例を示した図。
【図１９】エッジの登録方法を示した図。
【図２０】ドロップアウトの発生例を示した図。
【図２１】ドロップアウトの発生と検出の例を示した図。
【符号の説明】
１    座標変換手段
２    交点・ドロップアウト検出手段
２ａ    エッジ登録手段
２ｂ    ドロップアウト判定手段
２ｃ    エッジリスト作成手段
３    ビットマップ展開手段
１０    画像処理装置
１１    ＣＰＵ
１２    ＲＡＭ
１３    ＲＯＭ
１４    外部記憶装置
１５    ビデオＩ／Ｆ（インタフェイス）
１６    フレームバッファ
１７    プリンタＩ／Ｆ（インタフェイス）
５０    根
５１−１〜７４−１３    節点
【図１】
0003603589.tif 000002
【図２】
0003603589.tif 000003
【図３】
0003603589.tif 000004
【図４】
0003603589.tif 000005
【図５】
0003603589.tif 000006
【図６】
0003603589.tif 000007
【図７】
0003603589.tif 000008
【図８】
0003603589.tif 000009
【図９】
0003603589.tif 000010
【図１０】
0003603589.tif 000011
【図１１】
0003603589.tif 000012
【図１２】
0003603589.tif 000013
【図１３】
0003603589.tif 000014
【図１４】
0003603589.tif 000015
【図１５】
0003603589.tif 000016
【図１６】
0003603589.tif 000017
【図１７】
0003603589.tif 000018
【図１８】
0003603589.tif 000019
【図１９】
0003603589.tif 000020
【図２０】
0003603589.tif 000021
【図２１】
0003603589.tif 000022