JPH11282448A - 画像処理方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】高速にエッジリストを作成でき、使用するメモ
リの容量を少なくすることのできる画像処理方法および
装置を提供する。 【解決手段】走査により選択したエッジをエッジ登録手
段（２ａ）が２分探索木に登録するとともに、ドロップ
アウト判定手段（２ｂ）が検出されたドロップアウトを
も前記２分探索木に登録し、エッジリスト作成手段（２
ｃ）が前記２分探索木からエッジを昇順または降順で取
得してエッジリストを作成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、画像処理方法お
よび装置に関し、特に、文字デザイン情報をアウトライ
ン情報で格納し、小サイズの文字出力時にドロップアウ
トを補正する画像処理方法および装置に関する。

【０００２】

【従来技術】ページプリンタやディスプレイ等のビット
マップスクリーンをベースとする出力装置では、画素が
細かくなる、つまり、高解像度になるにしたがって、同
じサイズの文字や図形を表示するために多くのデータが
必要となる。特に、決まった輪郭をもつ文字情報におい
ても、サイズ毎にビットマップデータを持つ必要があり
効率が悪いものとなる、そのため、文字情報においては
サイズ毎にビットマップデータを持つのではなく、アウ
トライン情報を拡大または縮小してから文字の輪郭線の
内部を塗り潰すことで文字を表示する方法が有利とな
る。

【０００３】しかし、輪郭線内部を塗り潰す方法では小
サイズの文字を出力（表示）する場合には、輪郭線の間
隔が狭くなりすぎて塗り潰しに抜け（ドロップアウト）
が発生することがある。このドロップアウトが生じる現
象を回避するためには、大きく分けてアウトライン情報
自体に小サイズ出力時の輪郭線変更情報を持たせる方法
と、処理系にドロップアウト発生場所を検知させ修正を
行う方法の２つがある。前者は一般に処理が速く文字の
デザインの崩れもデータ作成段階で補正できるが、文字
数が増えた場合にデータサイズが増大し、データ作成時
の手間も増える。後者ではデータの変更の必要はない
が、処理が遅くなり、前者の場合と比較して文字のデザ
インが崩れる場合もある。したがって、現在では前者と
後者を組み合わせてしようするのが主流となっている。

【０００４】なお、この発明は、上述の２つの方法のう
ち後者の方法に関するものであるため、後者の方法につ
いてさらに説明する。

【０００５】図１４に文字の輪郭線とその輪郭線から得
られるビットマップを示す。同図に示すように文字を出
力（表示）する場合には、出力しようとする文字の輪郭
線の内側の画素を他の画素と反転させたビットマップを
出力する。また、各画素は、図１５に示すように高さ
１、幅１の正方形をしており、その４隅に整数座標値が
くる。画素の座標は左下隅の座標値で表現し、これをピ
クセル座標と呼ぶことにする。また、図１６に示すよう
に輪郭線の内側に画素の中心点がある場合、その画素は
輪郭線の内側であると判断される。

【０００６】次に、スキャンコンバージョンの一例を示
す。この例においては、輪郭線の方向を考慮しないＥＶ
ＥＮ−ＯＤＤルールと呼ばれる条件で輪郭線の内外を判
定している。

【０００７】ここで、図１７に示すようにｘ軸方向に画
素の中心点を結んだ線を走査線または主走査線、ｙ軸方
向に画素の中心点を結んだ線を副走査線と呼ぶことにす
る。輪郭線の内側を求める際には、図１８（ａ）に示す
ように輪郭線と走査線の交点を求め、交点とｙ座標が等
しく、交点の右側にある画素（画素の中心点）のうち最
も近い画素を選択する。この画素をエッジと呼ぶが、エ
ッジは、例えば上記交点のｘ座標値の小数点第１位を四
捨五入することで求めることができる。

【０００８】さて、全ての輪郭線についてエッジを選択
したら、図１８（ｂ）に示すように各走査線についてエ
ッジに挟まれた画素を反転する。このとき、反転する画
素の始点または終点となるエッジのうち、始点となる画
素は反転させるが、終点となる画素は反転させない。

【０００９】また、エッジを選択する段階でエッジが重
なった場合、その重なりが偶数個であるあればそのエッ
ジを削除する。この操作を実施しないと塗り潰しが正確
に行われない。なお、スキャンコンバージョンはドロッ
プアウトが発生しない限り副走査線方向から実施しても
同様の画像が得られる。

【００１０】ところで、選択されたエッジの登録を最も
単純に行うには図１９（ａ）に示すように実際のビット
マップで画素を反転させればよい。しかし、文字のサイ
ズが大きくなった場合や高解像度の場合には塗り潰しの
段階で全ての画素を調べなければならないので、速度的
に不利であり、単純な構造のために複雑なペイントルー
ルが利用しにくく、輪郭線の方向等のエッジの情報をつ
けるとメモリ効率が悪くなるといった欠点がある。

【００１１】そのため、図１９（ｂ）に示すように各走
査線をリストで管理する方法がある。これは、選択した
エッジをリストに登録していき、全てのエッジが登録さ
れたところで各リストをソートし、塗り潰し過程ではこ
のリストからエッジを２つずつ取り出してこれを始点お
よび終点とする。なお、このリストはエッジリストと呼
ばれる。

【００１２】ここで、図２０にドロップアウトの発生例
を示す。図２０（ａ）に示すように２つの輪郭線が隣接
する画素の中心点の間を通った場合には、反転する画素
が存在しないため、ドロップアウトが発生する。これは
図２０（ｂ）に示すように２つの輪郭線の走査線との各
交点から選択されるエッジが重なるために生じるもの
で、両輪郭線の間が輪郭線の外側であれば問題はない
が、エッジの選択の段階では通常内側か外側かは判らな
い。このような画素はスキャンコンバージョンの際に削
除することでドロップアウトを防止できる。他だし、こ
のような画素はエッジとは別のビットマップまたはエッ
ジリストに登録する必要がある。また、図２０（ｃ）
は、輪郭線と走査線の交点から求めたエッジでは発見で
きないドロップアウトの例を示しており、この場合には
副走査線方向からエッジを選択することでドロップアウ
トを発見できる。この例から判るように全てのドロップ
アウトを発見するには、走査線方向と副走査線方向の両
方から実施する必要がある。

【００１３】ドロップアウトの発生を防止、または抑制
する技術としては、特開平８−８７６０２号公報で開示
されている「アウトラインフォント描画装置」や特開平
８−９５５４５号公報で開示されている「アウトライン
フォント描画装置」等がある。

【００１４】特開平８−８７６０２号公報記載の「アウ
トラインフォント描画装置」では、走査線方向と副走査
線方向で各々スキャンコンバージョンを行い、別々のビ
ットマップを作成し、両者を合成することでドロップア
ウトの無いビットマップ画像を得ている。しかし、この
アウトラインフォント描画装置では、常に走査線方向と
副走査線方向の両方向からスキャンコンバージョンを行
っており、ドロップアウトの検出に要する時間が長くな
るとともに、ドロップアウトが発生する可能性の低い文
字または文字の一部分をスキャンコンバージョンする際
には無駄な処理を行っていることになる。

【００１５】また、特開平８−９５５４５号公報記載の
「アウトラインフォント描画装置」では、通常は各画素
の中心部に設定されるスキャンラインをずらしてスキャ
ンコンバージョンを行い、これによりドロップアウトの
発生を抑制している。ところが、スキャンラインをずら
すことでドロップアウトの発生を抑制しているために、
本来作成したい画像とは異なる画像ができる可能性があ
るとともに、スキャンラインの移動方向を輪郭線の方向
から判断しているので塗り潰しのルールによっては適用
できないものもある。

【００１６】さて、図２１は、ドロップアウトの発生と
検出の例を示しており、図２１（ａ）は走査線方向から
のスキャンコンバージョンでドロップアウトが発生した
例を、図２１（ｂ）は走査線方向からのドロップアウト
の検出結果を、図２１（ｃ）は副走査線方向からのドロ
ップアウトの検出結果を示している。このような場合に
は、図２１（ａ）、（ｂ）、（ｃ）の各画像を合成する
ことで、図２１（ｄ）に示すような画素の抜け（ドロッ
プアウト）の無い画像を得ることができる。

【００１７】このような処理は、文字のサイズが十分大
きく、ドロップアウトが発生しなければ輪郭線からのエ
ッジの選択は走査線または副走査線方向のどちらか一方
から実施すればよいが、文字のサイズが小さくドロップ
アウトを処理する必要がある場合は、両方向からエッジ
の選択を実施しなければならい。

【００１８】

【発明が解決しようとする課題】上述のように、従来の
画像処理装置では、一般に水平（主走査）方向および垂
直（副走査）方向の両方向からスキャンコンバージョン
を行い、エッジリストへエッジを登録している。ドロッ
プアウトの補正を行う場合には、エッジリストに登録さ
れているエッジを水平および垂直の両方向でソートが必
要となり時間が掛かるうえ、両方向から得られた各エッ
ジをエッジリストのまま合成するとさらに時間が掛かる
ため、ビットマップを使用して合成を行っていた。その
ため、エッジリストを使用できる（エッジリストを直接
入力して使用できる）出力装置を高速に使用できず、ま
た、ビットマップの使用のために大量のメモリが必要で
あった。

【００１９】そこで、この発明は、高速にエッジリスト
を作成でき、使用するメモリの容量を少なくすることの
できる画像処理方法および装置を提供することを目的と
する。

【００２０】

【課題を解決するための手段】上述した目的を達成する
ため、請求項１の発明では、描画する文字の輪郭線を走
査し、該走査を行う走査線と前記輪郭線との交点からエ
ッジを順次選択してエッジリストに登録し、該エッジリ
ストに基づいて前記エッジのうち所定のエッジ間の画素
を反転することで文字を表現してビットマップ上に展開
する画像処理方法において、走査を行う走査線と前記輪
郭線との交点から選択したエッジを２進木構造のデータ
として順次登録し、該２進木構造のデータに基づいてエ
ッジリストを作成することを特徴とする。

【００２１】また、請求項２の発明では、請求項１の発
明において、前記２進木構造のデータへのエッジの登録
は、該２進木構造の根または節点に現に登録されている
エッジの座標値と前記登録する座標値との大小関係に基
づいて決定される節点に登録することを特徴とする。

【００２２】また、請求項３の発明では、請求項１の発
明において、前記２進木構造のデータへのエッジの登録
は、該２進木構造のデータに前記登録するエッジの座標
値と同一の座標値のエッジが既に登録されている場合に
は、該同一の座標値のエッジを無効にするとともに、前
記登録するエッジをドロップアウトエッジとして登録す
ることを特徴とする。

【００２３】また、請求項４の発明では、請求項２の発
明において、前記２進木構造のデータへのエッジの登録
は、該２進木構造のデータに前記登録するエッジの座標
値と同一の座標値のドロップアウトエッジが既に登録さ
れている場合には、該ドロップアウトエッジの座標値が
前記登録するエッジの座標値よりも大きいと見做して前
記大小関係に基づいて決定される節点に登録することを
特徴とする。

【００２４】また、請求項５の発明では、請求項３の発
明において、前記ドロップアウトエッジの登録は、前記
２進木構造のデータに前記ドロップアウトエッジの座標
値と同一の座標値のエッジが登録されていない場合には
前記大小関係に基づいて決定される節点に登録し、前記
ドロップアウトエッジの座標値と同一の座標値のエッジ
が既に登録されてる場合には該ドロップアウトエッジの
座標値が前記登録するエッジの座標値よりも大きいと見
做して前記大小関係に基づいて決定される節点に登録す
ることを特徴とする。

【００２５】また、請求項６の発明では、請求項１乃至
５のいずれかの発明において、前記エッジリストの作成
は、前記２進木構造の根および節点に登録されているエ
ッジの座標値を所定の順序で読み出すことで行うことを
特徴とする。

【００２６】また、請求項７の発明では、請求項３乃至
６のいずれかの発明において、前記走査は、主走査方向
と該主走査方向に直交する副走査方向から行い、前記主
走査方向の走査から選択されたエッジを第１の２進木構
造のデータに登録し、前記副走査方向の走査から選択さ
れたエッジを第２の２進木構造のデータに登録するとと
もに、前記副走査方向の走査から選択されたエッジがド
ロップアウトエッジとして登録される場合には、該ドロ
ップアウトエッジを前記第１の２進木構造のデータに登
録することを特徴とする。

【００２７】また、請求項８の発明では、描画する文字
の輪郭線を走査し、該走査を行う走査線と前記輪郭線と
の交点からエッジを順次選択してエッジリストに登録
し、該エッジリストに基づいて前記エッジのうち所定の
エッジ間の画素を反転することで文字を表現してビット
マップ上に展開する画像処理装置において、走査を行う
走査線と前記輪郭線との交点から選択したエッジを２進
木構造のデータとして順次登録するエッジ登録手段と、
前記エッジ登録手段により前記２進木構造のデータに登
録されたエッジに基づいてエッジリストを生成するエッ
ジリスト作成手段とを具備することを特徴とする。

【００２８】また、請求項９の発明では、請求項８の発
明において、前記エッジ登録手段は、登録するエッジ
を、該登録するエッジの座標値と前記２進木構造の根ま
たは節点に現に登録されているエッジの座標値との大小
関係に基づいて決定される節点に登録することを特徴と
する。

【００２９】また、請求項１０の発明では、請求項８の
発明において、前記エッジ登録手段は、前記２進木構造
のデータに登録するエッジの座標値と同一の座標値のエ
ッジが既に登録されている場合には、該同一の座標値の
エッジを無効にするとともに、前記登録するエッジをド
ロップアウトエッジとして登録することを特徴とする。

【００３０】また、請求項１１の発明では、請求項９の
発明において、前記エッジ登録手段は、前記２進木構造
のデータに登録するエッジの座標値と同一の座標値のド
ロップアウトエッジが既に登録されている場合には、該
ドロップアウトエッジの座標値が前記登録するエッジの
座標値よりも大きいと見做して前記大小関係に基づいて
決定される節点に登録することを特徴とする。

【００３１】また、請求項１２の発明では、請求項１０
の発明において、前記エッジ登録手段は、前記２進木構
造のデータに登録するドロップアウトエッジの座標値と
同一の座標値のエッジが登録されていない場合には前記
大小関係に基づいて決定される節点に登録し、前記ドロ
ップアウトエッジの座標値と同一の座標値のエッジが既
に登録されてる場合には該ドロップアウトエッジの座標
値が前記登録するエッジの座標値よりも大きいと見做し
て前記大小関係に基づいて決定される節点に登録するこ
とを特徴とする。

【００３２】また、請求項１３の発明では、請求項８乃
至１２のいずれかの発明において、前記エッジリスト作
成手段は、前記２進木構造の根および節点に登録されて
いるエッジの座標値を所定の順序で読み出してエッジリ
ストを作成することを特徴とする。

【００３３】また、請求項１４の発明では、請求項１０
乃至１３のいずれかの発明において、ドロップアウト判
定手段をさらに具備するとともに、主走査方向と該主走
査方向に直交する副走査方向から前記走査を行い、前記
エッジ登録手段は、前記主走査方向の走査から選択され
たエッジを第１の２進木構造のデータに登録し、前記副
走査方向の走査から選択されたエッジを第２の２進木構
造のデータに登録し、前記ドロップアウト判定手段は、
前記副走査方向の走査から選択されたエッジが前記第２
の２進木構造に既に登録されていた場合に、該選択され
たエッジをドロップアウトエッジと判定して前記第１の
２進木構造のデータに登録することを特徴とする。

【００３４】

【発明の実施の形態】以下、この発明に係わる画像処理
方法および装置の一実施例を添付図面を参照して詳細に
説明する。

【００３５】図１は、この発明に係わる画像処理装置の
構成を示すブロック図である。画像処理装置１０は、ア
ウトライン情報の拡大縮小等の座標変換と曲線（輪郭線
情報）を画素に応じて滑らかに見える大きさの直線に分
割（複数の直線による近似）を行う座標変換手段１と、
走査線および副走査線と輪郭線の交点を検出してエッジ
リストの作成およびドロップアウトの検出を行う交点・
ドロップアウト検出手段２、エッジリストからビットマ
ップを生成するビットマップ展開手段３を具備して構成
される。また、交点・ドロップアウト検出手段２は、走
査線と輪郭線の交点からエッジを選択して後述する２分
探索木に登録するエッジ登録手段２ａと副走査線方向か
ら選択されたエッジに基づいてドロップアウトを検出す
るドロップアウト検出手段２ｂ、エッジを登録した２分
探索木に基づいてエッジリストを作成するエッジリスト
作成手段２ｃを具備して構成される。

【００３６】この画像処理装置１０は、実際には図２に
示すようにＣＰＵ１１と、ＲＡＭ１２、ＲＯＭ１３、外
部記憶装置１４、ビデオＩ／Ｆ（インタフェイス）１
５、フレームバッファ１６、プリンタＩ／Ｆ（インタフ
ェイス）１７を具備して構成される。

【００３７】図１に示した座標変換手段１と交点・ドロ
ップアウト検出手段２、ビットマップ展開手段３は、Ｒ
ＡＭ１２またはＲＯＭ１３に収められたプログラムによ
りＣＰＵ１１上で構成される。また、ＲＡＭ１２には上
述のエッジリスト等が構成され、ＲＯＭ１３および外部
記憶装置１４にはアウトラインフォントデータが格納さ
れている。フレームバッファ１６は、ビットマップ展開
手段３が展開したビットマップ画像を一時的に記憶し、
この画像をビデオＩ／Ｆ１５に接続されたディスプレイ
（不図示）またはプリンタＩ／Ｆ１７に接続されたペー
ジプリンタ（不図示）等の外部出力装置へ出力する。

【００３８】次に、画像処理装置１０の動作について説
明する。画像処理装置１０では、エッジリストの作成に
先立って、走査により選択されたエッジを２分探索木
（２進木構造のデータ）に登録する。この２分探索木は
エッジリスト１つに相当し、走査線方向と副走査線方向
で各々走査線（副走査線）毎に２分探索木を用意する。

【００３９】ここで、２分探索木へのエッジの登録のル
ールを説明する。図３は、２分探索木の概念図である。
同図に示すように、根５０には節点５１−１、５１−２
が接続され、根５０の左側の節点５１−１には根５０に
登録されている値（１０）よりも小さい値（５）が登録
されており、根５０の右側の節点５１−２には根５０に
登録されている値よりも大きい値（１２）が登録されて
いる。

【００４０】また、節点５１−１（値５）には左側に小
さい値（３）が登録された節点５２−１、右側に大きい
値（７）が登録された節点５２−２が接続され、節点５
１−２（値１２）には右側に大きい値（２０）が登録さ
れた節点５２−４が接続されている。同様に、節点５２
−１には節点５３−１が、節点５２−４には節点５３−
７と節点５３−８が接続されている。

【００４１】この根５０または節点５１−１乃至５３−
８に登録されている値は、走査線方向から選択されたエ
ッジを登録する２分探索木ではエッジのｘ座標値であ
り、副走査線方向から選択されたエッジを登録する２分
探索木ではエッジのｙ座標値である。

【００４２】ここで、新たに登録を行う場合、例えば、
新たな値（８）を登録するときは、図４（ａ）に示すよ
うに、まず登録する値（８）と根５０の値（１０）を比
較し、登録する値の方が小さければ、次に左側の節点５
１−１の値（５）と比較する。この場合、登録する値
（８）の方が大きいので、次に右側の節点５２−２の値
（７）との比較を行う。この場合にも登録する値（８）
の方が大きいので右側の節点との値を比較しようとする
が、節点が存在しないため、ここに新たな節点５３−４
を設定して値（８）を登録する。

【００４３】さらに、値（１８）を登録しようとする場
合には、同様の方法で図４（ｂ）に示すように、根５０
と節点５１−２、５２−４、５３−７との比較を行っ
て、新たな節点５４−１４に値（１８）を登録する。

【００４４】また、登録しようとする値が既に登録され
ている場合、つまり、登録しようとするエッジと同一座
標のエッジが既に登録されている場合、例えば、図５
（ａ）に示すような２分探索木に値（１２）を登録しよ
うとする場合には、節点５１−２に同じ値（１２）が登
録されているので、これを図５（ｂ）に示すように無効
な節点６１−２に設定し、さらにこの値をドロップアウ
トとして（走査線方向の）２分探索木に登録する。な
お、登録しようとする値が無効な節点として登録されて
いた場合には、これを有効な節点に登録し直す。

【００４５】図６は、２分探索木へのドロップアウトの
登録およびドロップアウトが登録されている２分探索木
へのエッジの登録のルールを示した図である。２分探索
木へのドロップアウトの登録とドロップアウトが登録さ
れている２分探索木へのエッジの登録は、どちらの場合
も同じ座標値のドロップアウト、エッジが登録されてい
ない状態では、通常のエッジの登録と同様に行う。例え
ば、図６（ａ）に示す２分探索木にドロップアウト（値
１３）を登録する場合には、図６（ｂ）に示すように節
点５１−２の左側にドロップアウトを示す節点７２−３
を設定して登録する。

【００４６】また、登録しようとするドロップアウトと
同じ座標のエッジが既に登録されている場合は、エッジ
の値よりもドロップアウトの値の方が大きいものと見做
して登録を行う。例えば、図６（ｃ）に示す２分探索木
にドロップアウト（値１２）を登録する場合には、節点
６１−２に無効なエッジ（値１２）が登録されているた
め、ドロップアウト（値１２）は、図６（ｄ）に示すよ
うにエッジ（値１２）よりも大きい値と見做され、節点
５３−７の左側にドロップアウトを示す節点７４−１３
を設定して登録される。同様に図６（ｅ）に示す２分探
索木にドロップアウト（値３）を登録する場合には、節
点５２−１にエッジ（値３）が登録されているため、ド
ロップアウト（値３）は、図６（ｆ）に示すようにエッ
ジ（値３）よりも大きい値と見做され、節点５２−１の
右側にドロップアウトを示す節点７３−２を設定して登
録される。

【００４７】同様に、エッジを登録しようとする場合
に、同じ座標値のドロップアウトが既に登録されている
場合は、エッジの値よりもドロップアウトの値の方が大
きいものと見做して登録を行う。例えば、図６（ｇ）に
示す２分探索木にエッジ（値７）を登録する場合には、
節点７２−２にドロップアウト（値７）が登録されてい
るため、エッジ（値７）は、図６（ｈ）に示すようにド
ロップアウト（値７）よりも小さい値と見做され、節点
７２−２の左側にエッジを示す節点５３−３を設定して
登録される。

【００４８】このようにエッジとドロップアウトの値が
同一であった場合に、エッジの値よりもドロップアウト
の値の方が大きいものと見做すのは、後述する方法で２
分探索木からエッジリストを作成すると値の小さい節点
が先に処理されることに関係する。これは、ドロップア
ウトに対する処理が輪郭線の内側か外側かで異なるた
め、エッジリストにはドロップアウトよりも先にエッジ
が登録されると都合がよく、そのためにエッジの値をド
ロップアウトの値よりも小さい値と見做すことになる。

【００４９】次に、図７乃至１１を参照して画像処理装
置１０の動作を説明する。図７乃至１１は、夫々画像処
理装置１０の動作の流れを示すフローチャートである。

【００５０】画像処理装置１０は、ＣＰＵ１１が図示し
ないインタフェース等を通じて図示しないＲＡＭ（また
はＲＡＭ１２）上に貯えられた画像情報等を読み込む。
画像情報が文字コードであればＲＯＭ１３または外部記
憶装置１４からアウトラインフォントデータを読みだし
て画像生成プログラムの実行を開始する（図７、ステッ
プ１０１）。

【００５１】次に、ＣＰＵ１１は、ＲＡＭ１３上に走査
線方向の２分探索木と副走査線方向の２分探索木、エッ
ジリスト等を作成し、これらリストを初期化する（ステ
ップ１０２）。続いて、ＣＰＵ１１は画像変換手段１を
実行して、輪郭線（アウトライン）を出力したい大きさ
に座標変換し（ステップ１０３）、この輪郭線を短い複
数の直線に分割する（曲線部は直線近似、ステップ１０
４）。

【００５２】輪郭線の分割が終了すると、ＣＰＵ１１
は、交点・ドロップアウト検出手段２を実行して、エッ
ジの選択と２分探索木への登録およびドロップアウトの
検出を行い（ステップ１０５）、２分探索木からエッジ
リストの作成を行う（ステップ１０６）。なお、ステッ
プ１０５および１０６の動作の詳細は後述する。

【００５３】次に、ＣＰＵ１１は、ビットマップ展開手
段３を実行して、エッジリストからビットマップを生成
し（ステップ１０７）、フレームバッファ１６へ出力す
る（ステップ１０８）。

【００５４】ここで、図示しない出力装置（ディスプレ
イやページプリンタ等）が、一定時間間隔またはＣＰＵ
１１からの終了信号に応じてフレームバッファ１６を調
べ、登録されているビットマップを出力することで画像
処理装置１０は動作を終了する（ステップ１０９）。

【００５５】次に、上述のステップ１０５におけるエッ
ジの選択と２分探索木への登録およびドロップアウトの
検出処理の詳細について説明する。交点・ドロップアウ
ト検出手段２は、まず、直線に分割された最初（予め設
定した順序の最初であり、どのような順序でも良い）の
輪郭線をセットし（図８、ステップ２０１）、走査線と
の交点（複数）を検出する（ステップ２０２）。続い
て、検出された交点のｙ座標値の小数点以下を切り捨
て、ｘ座標値の小数点以下を四捨五入してピクセル座標
を取得する（ステップ２０３）。このピクセル座標は、
交点とｙ座標が等しく、交点の右側にある画素（画素の
中心点）のうち最も近い画素であるので、これをエッジ
として走査線方向の２分探索木に順次登録する（ステッ
プ２０４）。走査線方向の２分探索木への登録は、エッ
ジ登録手段２ａを実行し、まず、最初のエッジをセット
し（図９、ステップ３０１）、その座標値のｙ座標値か
ら登録する２分探索木を選択する。次に、エッジを２分
探索木へ上述のルールに従って登録する（ステップ３０
２）。ここで、登録したエッジがドロップアウトであれ
ば（ステップ３０３でＹＥＳ）、そのドロップアウト
（の座標を）セットし（ステップ３０４）、２分探索木
へ登録する（ステップ３０２）。

【００５６】登録したエッジがドロップアウトでなけれ
ば（ステップ３０３でＮＯ）、これらの処理を最後のエ
ッジを登録するまで（ステップ３０５でＮＯ）、次のエ
ッジをセットして繰り返し（ステップ３０６）、最後の
エッジを登録すると（ステップ３０５でＹＥＳ）、ステ
ップ２０５（図８）へ進む。

【００５７】次に、セットされている輪郭線と副走査線
の交点を検出し（ステップ２０５）、検出された交点の
ｘ座標値の小数点以下を切り捨て、ｙ座標値の小数点以
下を四捨五入してピクセル座標を取得し（ステップ２０
６）、これをエッジとして副走査方向の２分探索木に順
次登録する（ステップ２０７）。副走査線方向の２分探
索木への登録は、走査線エッジリストへの登録は、ドロ
ップアウト検出手段２ｂを実行し、まず、最初のエッジ
をセットし（図１０、ステップ４０１）、その座標値の
ｘ座標値から登録する２分探索木を選択する。次に、エ
ッジを２分探索木へ上述のルールに従って登録する（ス
テップ４０２）。ここで、登録したエッジがドロップア
ウトであれば（ステップ４０３でＹＥＳ）、そのドロッ
プアウトを走査線方向の２分探索木に登録する（ステッ
プ４０４）。この登録はエッジ登録手段２ａが行い、登
録の方法は上述した方法と同じであるので説明は省略す
る。

【００５８】ドロップアウトを走査線方向の２分探索木
に登録するか（ステップ４０４）、登録したエッジがド
ロップアウトでなければ（ステップ４０３でＮＯ）、こ
れらの処理を最後のエッジを登録するまで（ステップ４
０５でＮＯ）、次のエッジをセットして繰り返し（ステ
ップ４０６）、最後のエッジを登録すると（ステップ４
０５でＹＥＳ）、ステップ２０８（図８）へ進む。

【００５９】これらの処理（ステップ２０２乃至２０
７）は、最後の輪郭線に対する処理が終了するまでは
（ステップ２０８でＮＯ）、次の輪郭線をセットして
（ステップ２０９）、繰り返し、最後の輪郭線に対する
処理が終了すると（ステップ２０８でＹＥＳ）、ステッ
プ１０５（図７）の処理を終了して、ステップ１０６へ
進む。

【００６０】次に、上述のステップ１０６における２分
探索木からエッジリストの作成処理の詳細について説明
する。交点・ドロップアウト検出手段２は、エッジリス
ト作成手段２ｃを実行し、まず、走査線方向の２分探索
木の最初のエッジ（根に登録されているエッジまたはド
ロップアウト）をセットする（図１１、ステップ５０
１）。ここで、根の左側に節点があればステップ５０２
以下の処理を再帰呼び出しして行い（ステップ５０
２）、再帰呼び出しを終了した場合や行わなかった場合
には、現にセットされているものがドロップアウトであ
れば（ステップ５０３でＹＥＳ）、そのドロップアウト
が輪郭線の外側であった場合に（図１２（ａ）に示すよ
うにドロップアウトが輪郭線の内側であれば登録する必
要がなく、図１２（ｂ）に示すようにドロップアウトが
輪郭線の外側であれば登録の必要がある）、１画素分の
始点および終点をエッジリストに登録し（ステップ５０
４）、現にセットされているものがエッジであれば（ス
テップ５０３でＮＯ）、そのエッジが有効な場合にエッ
ジリストに登録する（ステップ５０５）。次に、現在処
理している根または節点の右側に節点があればステップ
５０２以下の処理を再帰呼び出しして行い（ステップ５
０６）、全ての再帰呼び出しを終了した場合や行わなか
った場合には、エッジリストの作成処理を終了してステ
ップ１０７（図７）に進む。

【００６１】ここで、図１３を参照して実際の２分探索
木で図１１に示したエッジリストの作成を行った場合の
一例を説明する。まず、根５０をセットすると（ステッ
プ５０１）、根５０の左側には節点５１−１が存在する
ので再帰呼び出しを行う（ステップ５０２−０、−ｎは
再帰呼び出しを行っている回数を示し、０は再帰呼び出
しを行っていない状態のステップを示す）。

【００６２】次に、セットされている節点５１−１の左
側には節点５２−１が存在するため再び再帰呼び出しを
行う（ステップ５０２−１）。このように再帰呼び出し
により処理を行うと、節点５３−１に対してはステップ
５０２−２で再帰呼び出しされたステップ５０４−３の
処理が行われ、節点５２−１に対しては、ステップ５０
４−３の処理の後でステップ５０２−２に戻り、ステッ
プ５０４−２の処理が行われる。また、節点５２−２に
対しては、ステップ５０４−２の処理の後でステップ５
０２−１に戻り節点５１−１に対する処理（ステップ５
０４−１）が行われた後で、ステップ５０６−１で呼び
出されたステップ５０４−２の処理が行われる。

【００６３】したがって、各処理は節点５３−１（値
１）から節点５２−１（値３）、節点５１−１（値
５）、節点５２−２（値７）、根５０（値１０）、節点
５１−２（値１２）、節点５３−７（値１５）、節点５
２−４（値２０）、節点５３−８（値２２）の順に行わ
れ、ソートを行わなくとも昇順にエッジリストへの登録
を行うことができる。

【００６４】なお、上述の実施例では、エッジリストを
走査線方向の２分探索木から作成した場合を示したが、
当然のことながら上述の実施例の走査線方向と副走査線
方向を入れ替えても同様の処理が可能である。

【００６５】また、２分探索木へのエッジの登録ルール
および２分探索木からのエッジリストの作成のルール
は、上述の実施例のものに限らず、他のルールを適用で
きることを付記しておく。

【００６６】

【発明の効果】以上説明したように、この発明によれ
ば、走査により選択したエッジを２分探索木に登録する
とともに、検出されたドロップアウトをもその２分探索
木に登録し、２分探索木からエッジリストを作成するよ
うに構成したので、エッジリストのソートが必要無く、
２方向のビットマップを合成することによるドロップア
ウトの補正も行う必要がないので、使用するメモリ容量
を低減し、高速に処理を行うことができる。

【図面の簡単な説明】

【図１】この発明に係わる画像処理装置の構成を示すブ
ロック図。

【図２】画像処理装置１０の実際の構成を示すブロック
図。

【図３】２分探索木の概念図。

【図４】新たな登録を行う場合のルールを示した図。

【図５】登録しようとする値が既に登録されている場合
のルールを示した図。

【図６】２分探索木へのドロップアウトの登録およびド
ロップアウトが登録されている２分探索木へのエッジの
登録のルールを示した図。

【図７】画像処理装置１０の動作の流れを示すフローチ
ャート（１）。

【図８】画像処理装置１０の動作の流れを示すフローチ
ャート（２）。

【図９】画像処理装置１０の動作の流れを示すフローチ
ャート（３）。

【図１０】画像処理装置１０の動作の流れを示すフロー
チャート（４）。

【図１１】画像処理装置１０の動作の流れを示すフロー
チャート（５）。

【図１２】ドロップアウト登録の必要の有無を示した
図。

【図１３】２分探索木で図１１に示したエッジリストの
作成を行った場合の作成順序を示した図。

【図１４】文字の輪郭線とその輪郭線から得られるビッ
トマップを示した図。

【図１５】画素の形状を示した図。

【図１６】各画素が輪郭線の内外のいずれかかを判定す
る方法を示した図。

【図１７】走査線および副走査線を示した図。

【図１８】文字の描画例を示した図。

【図１９】エッジの登録方法を示した図。

【図２０】ドロップアウトの発生例を示した図。

【図２１】ドロップアウトの発生と検出の例を示した
図。

【符号の説明】

１ 座標変換手段 ２ 交点・ドロップアウト検出手段 ２ａ エッジ登録手段 ２ｂ ドロップアウト判定手段 ２ｃ エッジリスト作成手段 ３ ビットマップ展開手段 １０ 画像処理装置 １１ ＣＰＵ １２ ＲＡＭ １３ ＲＯＭ １４ 外部記憶装置 １５ ビデオＩ／Ｆ（インタフェイス） １６ フレームバッファ １７ プリンタＩ／Ｆ（インタフェイス） ５０ 根 ５１−１〜７４−１３ 節点

Claims (14)

【特許請求の範囲】
1. 【請求項１】 描画する文字の輪郭線を走査し、該走査
   を行う走査線と前記輪郭線との交点からエッジを順次選
   択してエッジリストに登録し、該エッジリストに基づい
   て前記エッジのうち所定のエッジ間の画素を反転するこ
   とで文字を表現してビットマップ上に展開する画像処理
   方法において、 走査を行う走査線と前記輪郭線との交点から選択したエ
   ッジを２進木構造のデータとして順次登録し、該２進木
   構造のデータに基づいてエッジリストを作成することを
   特徴とする画像処理方法。
2. 【請求項２】 前記２進木構造のデータへのエッジの登
   録は、 該２進木構造の根または節点に現に登録されているエッ
   ジの座標値と前記登録する座標値との大小関係に基づい
   て決定される節点に登録することを特徴とする請求項１
   記載の画像処理方法。
3. 【請求項３】 前記２進木構造のデータへのエッジの登
   録は、 該２進木構造のデータに前記登録するエッジの座標値と
   同一の座標値のエッジが既に登録されている場合には、
   該同一の座標値のエッジを無効にするとともに、前記登
   録するエッジをドロップアウトエッジとして登録するこ
   とを特徴とする請求項１記載の画像処理方法。
4. 【請求項４】 前記２進木構造のデータへのエッジの登
   録は、 該２進木構造のデータに前記登録するエッジの座標値と
   同一の座標値のドロップアウトエッジが既に登録されて
   いる場合には、該ドロップアウトエッジの座標値が前記
   登録するエッジの座標値よりも大きいと見做して前記大
   小関係に基づいて決定される節点に登録することを特徴
   とする請求項２記載の画像処理方法。
5. 【請求項５】 前記ドロップアウトエッジの登録は、 前記２進木構造のデータに前記ドロップアウトエッジの
   座標値と同一の座標値のエッジが登録されていない場合
   には前記大小関係に基づいて決定される節点に登録し、
   前記ドロップアウトエッジの座標値と同一の座標値のエ
   ッジが既に登録されてる場合には該ドロップアウトエッ
   ジの座標値が前記登録するエッジの座標値よりも大きい
   と見做して前記大小関係に基づいて決定される節点に登
   録することを特徴とする請求項３記載の画像処理方法。
6. 【請求項６】 前記エッジリストの作成は、 前記２進木構造の根および節点に登録されているエッジ
   の座標値を所定の順序で読み出すことで行うことを特徴
   とする請求項１乃至５のいずれかに記載の画像処理方
   法。
7. 【請求項７】 前記走査は、 主走査方向と該主走査方向に直交する副走査方向から行
   い、前記主走査方向の走査から選択されたエッジを第１
   の２進木構造のデータに登録し、前記副走査方向の走査
   から選択されたエッジを第２の２進木構造のデータに登
   録するとともに、前記副走査方向の走査から選択された
   エッジがドロップアウトエッジとして登録される場合に
   は、該ドロップアウトエッジを前記第１の２進木構造の
   データに登録することを特徴とする請求項３乃至６のい
   ずれかに記載の画像処理方法。
8. 【請求項８】 描画する文字の輪郭線を走査し、該走査
   を行う走査線と前記輪郭線との交点からエッジを順次選
   択してエッジリストに登録し、該エッジリストに基づい
   て前記エッジのうち所定のエッジ間の画素を反転するこ
   とで文字を表現してビットマップ上に展開する画像処理
   装置において、 走査を行う走査線と前記輪郭線との交点から選択したエ
   ッジを２進木構造のデータとして順次登録するエッジ登
   録手段と、 前記エッジ登録手段により前記２進木構造のデータに登
   録されたエッジに基づいてエッジリストを生成するエッ
   ジリスト作成手段とを具備することを特徴とする画像処
   理装置。
9. 【請求項９】 前記エッジ登録手段は、 登録するエッジを、該登録するエッジの座標値と前記２
   進木構造の根または節点に現に登録されているエッジの
   座標値との大小関係に基づいて決定される節点に登録す
   ることを特徴とする請求項８記載の画像処理装置。
10. 【請求項１０】 前記エッジ登録手段は、 前記２進木構造のデータに登録するエッジの座標値と同
    一の座標値のエッジが既に登録されている場合には、該
    同一の座標値のエッジを無効にするとともに、前記登録
    するエッジをドロップアウトエッジとして登録すること
    を特徴とする請求項８記載の画像処理装置。
11. 【請求項１１】 前記エッジ登録手段は、 前記２進木構造のデータに登録するエッジの座標値と同
    一の座標値のドロップアウトエッジが既に登録されてい
    る場合には、該ドロップアウトエッジの座標値が前記登
    録するエッジの座標値よりも大きいと見做して前記大小
    関係に基づいて決定される節点に登録することを特徴と
    する請求項９記載の画像処理装置。
12. 【請求項１２】 前記エッジ登録手段は、 前記２進木構造のデータに登録するドロップアウトエッ
    ジの座標値と同一の座標値のエッジが登録されていない
    場合には前記大小関係に基づいて決定される節点に登録
    し、前記ドロップアウトエッジの座標値と同一の座標値
    のエッジが既に登録されてる場合には該ドロップアウト
    エッジの座標値が前記登録するエッジの座標値よりも大
    きいと見做して前記大小関係に基づいて決定される節点
    に登録することを特徴とする請求項１０記載の画像処理
    装置。
13. 【請求項１３】 前記エッジリスト作成手段は、 前記２進木構造の根および節点に登録されているエッジ
    の座標値を所定の順序で読み出してエッジリストを作成
    することを特徴とする請求項８乃至１２のいずれかに記
    載の画像処理方法。
14. 【請求項１４】 ドロップアウト判定手段をさらに具備
    するとともに、 主走査方向と該主走査方向に直交する副走査方向から前
    記走査を行い、 前記エッジ登録手段は、前記主走査方向の走査から選択
    されたエッジを第１の２進木構造のデータに登録し、前
    記副走査方向の走査から選択されたエッジを第２の２進
    木構造のデータに登録し、 前記ドロップアウト判定手段は、前記副走査方向の走査
    から選択されたエッジが前記第２の２進木構造に既に登
    録されていた場合に、該選択されたエッジをドロップア
    ウトエッジと判定して前記第１の２進木構造のデータに
    登録することを特徴とする請求項１０乃至１３のいずれ
    かに記載の画像処理装置。