JP3603589B2

JP3603589B2 - Image processing method and apparatus

Info

Publication number: JP3603589B2
Application number: JP07934698A
Authority: JP
Inventors: 正二三知久
Original assignee: Fuji Xerox Co Ltd; Fujifilm Business Innovation Corp
Current assignee: Fujifilm Business Innovation Corp
Priority date: 1998-03-26
Filing date: 1998-03-26
Publication date: 2004-12-22
Anticipated expiration: 2018-03-26
Also published as: JPH11282448A

Description

【０００１】
【発明の属する技術分野】
この発明は、画像処理方法および装置に関し、特に、文字デザイン情報をアウトライン情報で格納し、小サイズの文字出力時にドロップアウトを補正する画像処理方法および装置に関する。
【０００２】
【従来技術】
ページプリンタやディスプレイ等のビットマップスクリーンをベースとする出力装置では、画素が細かくなる、つまり、高解像度になるにしたがって、同じサイズの文字や図形を表示するために多くのデータが必要となる。特に、決まった輪郭をもつ文字情報においても、サイズ毎にビットマップデータを持つ必要があり効率が悪いものとなる、そのため、文字情報においてはサイズ毎にビットマップデータを持つのではなく、アウトライン情報を拡大または縮小してから文字の輪郭線の内部を塗り潰すことで文字を表示する方法が有利となる。
【０００３】
しかし、輪郭線内部を塗り潰す方法では小サイズの文字を出力（表示）する場合には、輪郭線の間隔が狭くなりすぎて塗り潰しに抜け（ドロップアウト）が発生することがある。このドロップアウトが生じる現象を回避するためには、大きく分けてアウトライン情報自体に小サイズ出力時の輪郭線変更情報を持たせる方法と、処理系にドロップアウト発生場所を検知させ修正を行う方法の２つがある。前者は一般に処理が速く文字のデザインの崩れもデータ作成段階で補正できるが、文字数が増えた場合にデータサイズが増大し、データ作成時の手間も増える。後者ではデータの変更の必要はないが、処理が遅くなり、前者の場合と比較して文字のデザインが崩れる場合もある。したがって、現在では前者と後者を組み合わせてしようするのが主流となっている。
【０００４】
なお、この発明は、上述の２つの方法のうち後者の方法に関するものであるため、後者の方法についてさらに説明する。
【０００５】
図１４に文字の輪郭線とその輪郭線から得られるビットマップを示す。同図に示すように文字を出力（表示）する場合には、出力しようとする文字の輪郭線の内側の画素を他の画素と反転させたビットマップを出力する。また、各画素は、図１５に示すように高さ１、幅１の正方形をしており、その４隅に整数座標値がくる。画素の座標は左下隅の座標値で表現し、これをピクセル座標と呼ぶことにする。また、図１６に示すように輪郭線の内側に画素の中心点がある場合、その画素は輪郭線の内側であると判断される。
【０００６】
次に、スキャンコンバージョンの一例を示す。この例においては、輪郭線の方向を考慮しないＥＶＥＮ−ＯＤＤルールと呼ばれる条件で輪郭線の内外を判定している。
【０００７】
ここで、図１７に示すようにｘ軸方向に画素の中心点を結んだ線を走査線または主走査線、ｙ軸方向に画素の中心点を結んだ線を副走査線と呼ぶことにする。輪郭線の内側を求める際には、図１８（ａ）に示すように輪郭線と走査線の交点を求め、交点とｙ座標が等しく、交点の右側にある画素（画素の中心点）のうち最も近い画素を選択する。この画素をエッジと呼ぶが、エッジは、例えば上記交点のｘ座標値の小数点第１位を四捨五入することで求めることができる。
【０００８】
さて、全ての輪郭線についてエッジを選択したら、図１８（ｂ）に示すように各走査線についてエッジに挟まれた画素を反転する。このとき、反転する画素の始点または終点となるエッジのうち、始点となる画素は反転させるが、終点となる画素は反転させない。
【０００９】
また、エッジを選択する段階でエッジが重なった場合、その重なりが偶数個であるあればそのエッジを削除する。この操作を実施しないと塗り潰しが正確に行われない。
なお、スキャンコンバージョンはドロップアウトが発生しない限り副走査線方向から実施しても同様の画像が得られる。
【００１０】
ところで、選択されたエッジの登録を最も単純に行うには図１９（ａ）に示すように実際のビットマップで画素を反転させればよい。しかし、文字のサイズが大きくなった場合や高解像度の場合には塗り潰しの段階で全ての画素を調べなければならないので、速度的に不利であり、単純な構造のために複雑なペイントルールが利用しにくく、輪郭線の方向等のエッジの情報をつけるとメモリ効率が悪くなるといった欠点がある。
【００１１】
そのため、図１９（ｂ）に示すように各走査線をリストで管理する方法がある。これは、選択したエッジをリストに登録していき、全てのエッジが登録されたところで各リストをソートし、塗り潰し過程ではこのリストからエッジを２つずつ取り出してこれを始点および終点とする。なお、このリストはエッジリストと呼ばれる。
【００１２】
ここで、図２０にドロップアウトの発生例を示す。
図２０（ａ）に示すように２つの輪郭線が隣接する画素の中心点の間を通った場合には、反転する画素が存在しないため、ドロップアウトが発生する。これは図２０（ｂ）に示すように２つの輪郭線の走査線との各交点から選択されるエッジが重なるために生じるもので、両輪郭線の間が輪郭線の外側であれば問題はないが、エッジの選択の段階では通常内側か外側かは判らない。このような画素はスキャンコンバージョンの際に削除することでドロップアウトを防止できる。他だし、このような画素はエッジとは別のビットマップまたはエッジリストに登録する必要がある。また、図２０（ｃ）は、輪郭線と走査線の交点から求めたエッジでは発見できないドロップアウトの例を示しており、この場合には副走査線方向からエッジを選択することでドロップアウトを発見できる。この例から判るように全てのドロップアウトを発見するには、走査線方向と副走査線方向の両方から実施する必要がある。
【００１３】
ドロップアウトの発生を防止、または抑制する技術としては、特開平８−８７６０２号公報で開示されている「アウトラインフォント描画装置」や特開平８−９５５４５号公報で開示されている「アウトラインフォント描画装置」等がある。
【００１４】
特開平８−８７６０２号公報記載の「アウトラインフォント描画装置」では、走査線方向と副走査線方向で各々スキャンコンバージョンを行い、別々のビットマップを作成し、両者を合成することでドロップアウトの無いビットマップ画像を得ている。しかし、このアウトラインフォント描画装置では、常に走査線方向と副走査線方向の両方向からスキャンコンバージョンを行っており、ドロップアウトの検出に要する時間が長くなるとともに、ドロップアウトが発生する可能性の低い文字または文字の一部分をスキャンコンバージョンする際には無駄な処理を行っていることになる。
【００１５】
また、特開平８−９５５４５号公報記載の「アウトラインフォント描画装置」では、通常は各画素の中心部に設定されるスキャンラインをずらしてスキャンコンバージョンを行い、これによりドロップアウトの発生を抑制している。ところが、スキャンラインをずらすことでドロップアウトの発生を抑制しているために、本来作成したい画像とは異なる画像ができる可能性があるとともに、スキャンラインの移動方向を輪郭線の方向から判断しているので塗り潰しのルールによっては適用できないものもある。
【００１６】
さて、図２１は、ドロップアウトの発生と検出の例を示しており、図２１（ａ）は走査線方向からのスキャンコンバージョンでドロップアウトが発生した例を、図２１（ｂ）は走査線方向からのドロップアウトの検出結果を、図２１（ｃ）は副走査線方向からのドロップアウトの検出結果を示している。このような場合には、図２１（ａ）、（ｂ）、（ｃ）の各画像を合成することで、図２１（ｄ）に示すような画素の抜け（ドロップアウト）の無い画像を得ることができる。
【００１７】
このような処理は、文字のサイズが十分大きく、ドロップアウトが発生しなければ輪郭線からのエッジの選択は走査線または副走査線方向のどちらか一方から実施すればよいが、文字のサイズが小さくドロップアウトを処理する必要がある場合は、両方向からエッジの選択を実施しなければならい。
【００１８】
【発明が解決しようとする課題】
上述のように、従来の画像処理装置では、一般に水平（主走査）方向および垂直（副走査）方向の両方向からスキャンコンバージョンを行い、エッジリストへエッジを登録している。ドロップアウトの補正を行う場合には、エッジリストに登録されているエッジを水平および垂直の両方向でソートが必要となり時間が掛かるうえ、両方向から得られた各エッジをエッジリストのまま合成するとさらに時間が掛かるため、ビットマップを使用して合成を行っていた。そのため、エッジリストを使用できる（エッジリストを直接入力して使用できる）出力装置を高速に使用できず、また、ビットマップの使用のために大量のメモリが必要であった。
【００１９】
そこで、この発明は、高速にエッジリストを作成でき、使用するメモリの容量を少なくすることのできる画像処理方法および装置を提供することを目的とする。
【００２０】
【課題を解決するための手段】
上述した目的を達成するため、請求項１の発明は、描画する文字の輪郭線を走査し、該走査を行う走査線と前記輪郭線との交点からエッジを順次選択してエッジリストに登録し、該エッジリストに基づいて前記エッジのうち所定のエッジ間の画素を反転することで文字を表現してビットマップ上に展開する画像処理方法において、走査を行う走査線と前記輪郭線との交点から選択したエッジを２進木構造のデータとして順次登録するとともに、該選択したエッジの座標値と同一の座標値のエッジが該２進木構造のデータに既に登録されている場合には、該同一の座標値のエッジを無効にして該選択したエッジをドロップアウトエッジとして登録し、該２進木構造のデータに基づいてエッジリストを作成することを特徴とする。
【００２１】
また、請求項２の発明は、請求項１の発明において、前記選択したエッジは、前記２進木構造の根または節点に現に登録されているエッジの座標値と前記選択したエッジの座標値との大小関係に基づいて決定される該２進木構造の節点に登録され、該２進木構造のデータに前記選択したエッジの座標値と同一の座標値のドロップアウトエッジが既に登録されている場合には、該ドロップアウトエッジの座標値が前記選択したエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録されることを特徴とする。
【００２２】
また、請求項３の発明は、請求項２の発明において、前記ドロップアウトエッジは、前記２進木構造のデータに該ドロップアウトエッジの座標値と同一の座標値のエッジが登録されていない場合には前記大小関係に基づいて決定される節点に登録され、前記ドロップアウトエッジの座標値と同一の座標値のエッジが既に登録されている場合には該ドロップアウトエッジの座標値が該登録されているエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録されることを特徴とする。
【００２３】
また、請求項４の発明は、請求項１乃至３のいずれかの発明において、前記エッジリストの作成は、前記２進木構造の根および節点に登録されているエッジの座標値を所定の順序で読み出すことで行うことを特徴とする。
【００２４】
また、請求項５の発明は、請求項１乃至４のいずれかの発明において、前記走査は、主走査方向と該主走査方向に直交する副走査方向から行い、前記主走査方向の走査から選択されたエッジを第１の２進木構造のデータに登録し、前記副走査方向の走査から選択されたエッジを第２の２進木構造のデータに登録するとともに、前記副走査方向の走査から選択されたエッジがドロップアウトエッジとして登録される場合には、該ドロップアウトエッジを前記第１の２進木構造のデータに登録することを特徴とする。
【００２５】
また、請求項６の発明は、描画する文字の輪郭線を走査し、該走査を行う走査線と前記輪郭線との交点からエッジを順次選択してエッジリストに登録し、該エッジリストに基づいて前記エッジのうち所定のエッジ間の画素を反転することで文字を表現してビットマップ上に展開する画像処理装置において、走査を行う走査線と前記輪郭線との交点から選択したエッジを２進木構造のデータとして順次登録するとともに、該選択したエッジの座標値と同一の座標値のエッジが該２進木構造のデータに既に登録されている場合には、該同一の座標値のエッジを無効にして該選択したエッジをドロップアウトエッジとして登録するエッジ登録手段と、前記エッジ登録手段により前記２進木構造のデータに登録されたエッジに基づいてエッジリストを生成するエッジリスト作成手段とを具備することを特徴とする。
【００２６】
また、請求項７の発明は、請求項６の発明において、前記エッジ登録手段は、選択した登録エッジを、該エッジの座標値と前記２進木構造の根または節点に現に登録されているエッジの座標値との大小関係に基づいて決定される節点に登録し、該２進木構造のデータに前記選択したエッジの座標値と同一の座標値のドロップアウトエッジが既に登録されている場合には、該ドロップアウトエッジの座標値が前記選択したエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に登録することを特徴とする。
【００２７】
また、請求項８の発明は、請求項７の発明において、前記エッジ登録手段は、前記２進木構造のデータに、登録するドロップアウトエッジの座標値と同一の座標値のエッジが登録されていない場合には前記大小関係に基づいて決定される節点に該ドロップアウトエッジを登録し、登録するドロップアウトエッジの座標値と同一の座標値のエッジが既に登録されている場合には該ドロップアウトエッジの座標値が前記登録するエッジの座標値よりも大きいと見做して前記大小関係に基づいて決定される節点に該ドロップアウトエッジを登録することを特徴とする。
【００２８】
また、請求項９の発明は、請求項６乃至８のいずれかの発明において、前記エッジリスト作成手段は、前記２進木構造の根および節点に登録されているエッジの座標値を所定の順序で読み出してエッジリストを作成することを特徴とする。
【００２９】
また、請求項１０の発明は、請求項６乃至９のいずれかの発明において、ドロップアウト判定手段をさらに具備するとともに、主走査方向と該主走査方向に直交する副走査方向から前記走査を行い、前記エッジ登録手段は、前記主走査方向の走査から選択されたエッジを第１の２進木構造のデータに登録し、前記副走査方向の走査から選択されたエッジを第２の２進木構造のデータに登録し、前記ドロップアウト判定手段は、前記副走査方向の走査から選択されたエッジが前記第２の２進木構造に既に登録されていた場合に、該選択されたエッジをドロップアウトエッジと判定して前記第１の２進木構造のデータに登録することを特徴とする。
【００３４】
【発明の実施の形態】
以下、この発明に係わる画像処理方法および装置の一実施例を添付図面を参照して詳細に説明する。
【００３５】
図１は、この発明に係わる画像処理装置の構成を示すブロック図である。
画像処理装置１０は、アウトライン情報の拡大縮小等の座標変換と曲線（輪郭線情報）を画素に応じて滑らかに見える大きさの直線に分割（複数の直線による近似）を行う座標変換手段１と、走査線および副走査線と輪郭線の交点を検出してエッジリストの作成およびドロップアウトの検出を行う交点・ドロップアウト検出手段２、エッジリストからビットマップを生成するビットマップ展開手段３を具備して構成される。また、交点・ドロップアウト検出手段２は、走査線と輪郭線の交点からエッジを選択して後述する２分探索木に登録するエッジ登録手段２ａと副走査線方向から選択されたエッジに基づいてドロップアウトを検出するドロップアウト検出手段２ｂ、エッジを登録した２分探索木に基づいてエッジリストを作成するエッジリスト作成手段２ｃを具備して構成される。
【００３６】
この画像処理装置１０は、実際には図２に示すようにＣＰＵ１１と、ＲＡＭ１２、ＲＯＭ１３、外部記憶装置１４、ビデオＩ／Ｆ（インタフェイス）１５、フレームバッファ１６、プリンタＩ／Ｆ（インタフェイス）１７を具備して構成される。
【００３７】
図１に示した座標変換手段１と交点・ドロップアウト検出手段２、ビットマップ展開手段３は、ＲＡＭ１２またはＲＯＭ１３に収められたプログラムによりＣＰＵ１１上で構成される。また、ＲＡＭ１２には上述のエッジリスト等が構成され、ＲＯＭ１３および外部記憶装置１４にはアウトラインフォントデータが格納されている。フレームバッファ１６は、ビットマップ展開手段３が展開したビットマップ画像を一時的に記憶し、この画像をビデオＩ／Ｆ１５に接続されたディスプレイ（不図示）またはプリンタＩ／Ｆ１７に接続されたページプリンタ（不図示）等の外部出力装置へ出力する。
【００３８】
次に、画像処理装置１０の動作について説明する。
画像処理装置１０では、エッジリストの作成に先立って、走査により選択されたエッジを２分探索木（２進木構造のデータ）に登録する。この２分探索木はエッジリスト１つに相当し、走査線方向と副走査線方向で各々走査線（副走査線）毎に２分探索木を用意する。
【００３９】
ここで、２分探索木へのエッジの登録のルールを説明する。
図３は、２分探索木の概念図である。
同図に示すように、根５０には節点５１−１、５１−２が接続され、根５０の左側の節点５１−１には根５０に登録されている値（１０）よりも小さい値（５）が登録されており、根５０の右側の節点５１−２には根５０に登録されている値よりも大きい値（１２）が登録されている。
【００４０】
また、節点５１−１（値５）には左側に小さい値（３）が登録された節点５２−１、右側に大きい値（７）が登録された節点５２−２が接続され、節点５１−２（値１２）には右側に大きい値（２０）が登録された節点５２−４が接続されている。
同様に、節点５２−１には節点５３−１が、節点５２−４には節点５３−７と節点５３−８が接続されている。
【００４１】
この根５０または節点５１−１乃至５３−８に登録されている値は、走査線方向から選択されたエッジを登録する２分探索木ではエッジのｘ座標値であり、副走査線方向から選択されたエッジを登録する２分探索木ではエッジのｙ座標値である。
【００４２】
ここで、新たに登録を行う場合、例えば、新たな値（８）を登録するときは、図４（ａ）に示すように、まず登録する値（８）と根５０の値（１０）を比較し、登録する値の方が小さければ、次に左側の節点５１−１の値（５）と比較する。この場合、登録する値（８）の方が大きいので、次に右側の節点５２−２の値（７）との比較を行う。この場合にも登録する値（８）の方が大きいので右側の節点との値を比較しようとするが、節点が存在しないため、ここに新たな節点５３−４を設定して値（８）を登録する。
【００４３】
さらに、値（１８）を登録しようとする場合には、同様の方法で図４（ｂ）に示すように、根５０と節点５１−２、５２−４、５３−７との比較を行って、新たな節点５４−１４に値（１８）を登録する。
【００４４】
また、登録しようとする値が既に登録されている場合、つまり、登録しようとするエッジと同一座標のエッジが既に登録されている場合、例えば、図５（ａ）に示すような２分探索木に値（１２）を登録しようとする場合には、節点５１−２に同じ値（１２）が登録されているので、これを図５（ｂ）に示すように無効な節点６１−２に設定し、さらにこの値をドロップアウトとして（走査線方向の）２分探索木に登録する。なお、登録しようとする値が無効な節点として登録されていた場合には、これを有効な節点に登録し直す。
【００４５】
図６は、２分探索木へのドロップアウトの登録およびドロップアウトが登録されている２分探索木へのエッジの登録のルールを示した図である。
２分探索木へのドロップアウトの登録とドロップアウトが登録されている２分探索木へのエッジの登録は、どちらの場合も同じ座標値のドロップアウト、エッジが登録されていない状態では、通常のエッジの登録と同様に行う。例えば、図６（ａ）に示す２分探索木にドロップアウト（値１３）を登録する場合には、図６（ｂ）に示すように節点５１−２の左側にドロップアウトを示す節点７２−３を設定して登録する。
【００４６】
また、登録しようとするドロップアウトと同じ座標のエッジが既に登録されている場合は、エッジの値よりもドロップアウトの値の方が大きいものと見做して登録を行う。例えば、図６（ｃ）に示す２分探索木にドロップアウト（値１２）を登録する場合には、節点６１−２に無効なエッジ（値１２）が登録されているため、ドロップアウト（値１２）は、図６（ｄ）に示すようにエッジ（値１２）よりも大きい値と見做され、節点５３−７の左側にドロップアウトを示す節点７４−１３を設定して登録される。同様に図６（ｅ）に示す２分探索木にドロップアウト（値３）を登録する場合には、節点５２−１にエッジ（値３）が登録されているため、ドロップアウト（値３）は、図６（ｆ）に示すようにエッジ（値３）よりも大きい値と見做され、節点５２−１の右側にドロップアウトを示す節点７３−２を設定して登録される。
【００４７】
同様に、エッジを登録しようとする場合に、同じ座標値のドロップアウトが既に登録されている場合は、エッジの値よりもドロップアウトの値の方が大きいものと見做して登録を行う。例えば、図６（ｇ）に示す２分探索木にエッジ（値７）を登録する場合には、節点７２−２にドロップアウト（値７）が登録されているため、エッジ（値７）は、図６（ｈ）に示すようにドロップアウト（値７）よりも小さい値と見做され、節点７２−２の左側にエッジを示す節点５３−３を設定して登録される。
【００４８】
このようにエッジとドロップアウトの値が同一であった場合に、エッジの値よりもドロップアウトの値の方が大きいものと見做すのは、後述する方法で２分探索木からエッジリストを作成すると値の小さい節点が先に処理されることに関係する。これは、ドロップアウトに対する処理が輪郭線の内側か外側かで異なるため、エッジリストにはドロップアウトよりも先にエッジが登録されると都合がよく、そのためにエッジの値をドロップアウトの値よりも小さい値と見做すことになる。
【００４９】
次に、図７乃至１１を参照して画像処理装置１０の動作を説明する。
図７乃至１１は、夫々画像処理装置１０の動作の流れを示すフローチャートである。
【００５０】
画像処理装置１０は、ＣＰＵ１１が図示しないインタフェース等を通じて図示しないＲＡＭ（またはＲＡＭ１２）上に貯えられた画像情報等を読み込む。画像情報が文字コードであればＲＯＭ１３または外部記憶装置１４からアウトラインフォントデータを読みだして画像生成プログラムの実行を開始する（図７、ステップ１０１）。
【００５１】
次に、ＣＰＵ１１は、ＲＡＭ１３上に走査線方向の２分探索木と副走査線方向の２分探索木、エッジリスト等を作成し、これらリストを初期化する（ステップ１０２）。続いて、ＣＰＵ１１は画像変換手段１を実行して、輪郭線（アウトライン）を出力したい大きさに座標変換し（ステップ１０３）、この輪郭線を短い複数の直線に分割する（曲線部は直線近似、ステップ１０４）。
【００５２】
輪郭線の分割が終了すると、ＣＰＵ１１は、交点・ドロップアウト検出手段２を実行して、エッジの選択と２分探索木への登録およびドロップアウトの検出を行い（ステップ１０５）、２分探索木からエッジリストの作成を行う（ステップ１０６）。なお、ステップ１０５および１０６の動作の詳細は後述する。
【００５３】
次に、ＣＰＵ１１は、ビットマップ展開手段３を実行して、エッジリストからビットマップを生成し（ステップ１０７）、フレームバッファ１６へ出力する（ステップ１０８）。
【００５４】
ここで、図示しない出力装置（ディスプレイやページプリンタ等）が、一定時間間隔またはＣＰＵ１１からの終了信号に応じてフレームバッファ１６を調べ、登録されているビットマップを出力することで画像処理装置１０は動作を終了する（ステップ１０９）。
【００５５】
次に、上述のステップ１０５におけるエッジの選択と２分探索木への登録およびドロップアウトの検出処理の詳細について説明する。
交点・ドロップアウト検出手段２は、まず、直線に分割された最初（予め設定した順序の最初であり、どのような順序でも良い）の輪郭線をセットし（図８、ステップ２０１）、走査線との交点（複数）を検出する（ステップ２０２）。続いて、検出された交点のｙ座標値の小数点以下を切り捨て、ｘ座標値の小数点以下を四捨五入してピクセル座標を取得する（ステップ２０３）。このピクセル座標は、交点とｙ座標が等しく、交点の右側にある画素（画素の中心点）のうち最も近い画素であるので、これをエッジとして走査線方向の２分探索木に順次登録する（ステップ２０４）。走査線方向の２分探索木への登録は、エッジ登録手段２ａを実行し、まず、最初のエッジをセットし（図９、ステップ３０１）、その座標値のｙ座標値から登録する２分探索木を選択する。次に、エッジを２分探索木へ上述のルールに従って登録する（ステップ３０２）。ここで、登録したエッジがドロップアウトであれば（ステップ３０３でＹＥＳ）、そのドロップアウト（の座標を）セットし（ステップ３０４）、２分探索木へ登録する（ステップ３０２）。
【００５６】
登録したエッジがドロップアウトでなければ（ステップ３０３でＮＯ）、これらの処理を最後のエッジを登録するまで（ステップ３０５でＮＯ）、次のエッジをセットして繰り返し（ステップ３０６）、最後のエッジを登録すると（ステップ３０５でＹＥＳ）、ステップ２０５（図８）へ進む。
【００５７】
次に、セットされている輪郭線と副走査線の交点を検出し（ステップ２０５）、検出された交点のｘ座標値の小数点以下を切り捨て、ｙ座標値の小数点以下を四捨五入してピクセル座標を取得し（ステップ２０６）、これをエッジとして副走査方向の２分探索木に順次登録する（ステップ２０７）。副走査線方向の２分探索木への登録は、走査線エッジリストへの登録は、ドロップアウト検出手段２ｂを実行し、まず、最初のエッジをセットし（図１０、ステップ４０１）、その座標値のｘ座標値から登録する２分探索木を選択する。次に、エッジを２分探索木へ上述のルールに従って登録する（ステップ４０２）。ここで、登録したエッジがドロップアウトであれば（ステップ４０３でＹＥＳ）、そのドロップアウトを走査線方向の２分探索木に登録する（ステップ４０４）。この登録はエッジ登録手段２ａが行い、登録の方法は上述した方法と同じであるので説明は省略する。
【００５８】
ドロップアウトを走査線方向の２分探索木に登録するか（ステップ４０４）、登録したエッジがドロップアウトでなければ（ステップ４０３でＮＯ）、これらの処理を最後のエッジを登録するまで（ステップ４０５でＮＯ）、次のエッジをセットして繰り返し（ステップ４０６）、最後のエッジを登録すると（ステップ４０５でＹＥＳ）、ステップ２０８（図８）へ進む。
【００５９】
これらの処理（ステップ２０２乃至２０７）は、最後の輪郭線に対する処理が終了するまでは（ステップ２０８でＮＯ）、次の輪郭線をセットして（ステップ２０９）、繰り返し、最後の輪郭線に対する処理が終了すると（ステップ２０８でＹＥＳ）、ステップ１０５（図７）の処理を終了して、ステップ１０６へ進む。
【００６０】
次に、上述のステップ１０６における２分探索木からエッジリストの作成処理の詳細について説明する。
交点・ドロップアウト検出手段２は、エッジリスト作成手段２ｃを実行し、まず、走査線方向の２分探索木の最初のエッジ（根に登録されているエッジまたはドロップアウト）をセットする（図１１、ステップ５０１）。ここで、根の左側に節点があればステップ５０２以下の処理を再帰呼び出しして行い（ステップ５０２）、再帰呼び出しを終了した場合や行わなかった場合には、現にセットされているものがドロップアウトであれば（ステップ５０３でＹＥＳ）、そのドロップアウトが輪郭線の外側であった場合に（図１２（ａ）に示すようにドロップアウトが輪郭線の内側であれば登録する必要がなく、図１２（ｂ）に示すようにドロップアウトが輪郭線の外側であれば登録の必要がある）、１画素分の始点および終点をエッジリストに登録し（ステップ５０４）、現にセットされているものがエッジであれば（ステップ５０３でＮＯ）、そのエッジが有効な場合にエッジリストに登録する（ステップ５０５）。次に、現在処理している根または節点の右側に節点があればステップ５０２以下の処理を再帰呼び出しして行い（ステップ５０６）、全ての再帰呼び出しを終了した場合や行わなかった場合には、エッジリストの作成処理を終了してステップ１０７（図７）に進む。
【００６１】
ここで、図１３を参照して実際の２分探索木で図１１に示したエッジリストの作成を行った場合の一例を説明する。
まず、根５０をセットすると（ステップ５０１）、根５０の左側には節点５１−１が存在するので再帰呼び出しを行う（ステップ５０２−０、−ｎは再帰呼び出しを行っている回数を示し、０は再帰呼び出しを行っていない状態のステップを示す）。
【００６２】
次に、セットされている節点５１−１の左側には節点５２−１が存在するため再び再帰呼び出しを行う（ステップ５０２−１）。
このように再帰呼び出しにより処理を行うと、節点５３−１に対してはステップ５０２−２で再帰呼び出しされたステップ５０４−３の処理が行われ、節点５２−１に対しては、ステップ５０４−３の処理の後でステップ５０２−２に戻り、ステップ５０４−２の処理が行われる。また、節点５２−２に対しては、ステップ５０４−２の処理の後でステップ５０２−１に戻り節点５１−１に対する処理（ステップ５０４−１）が行われた後で、ステップ５０６−１で呼び出されたステップ５０４−２の処理が行われる。
【００６３】
したがって、各処理は節点５３−１（値１）から節点５２−１（値３）、節点５１−１（値５）、節点５２−２（値７）、根５０（値１０）、節点５１−２（値１２）、節点５３−７（値１５）、節点５２−４（値２０）、節点５３−８（値２２）の順に行われ、ソートを行わなくとも昇順にエッジリストへの登録を行うことができる。
【００６４】
なお、上述の実施例では、エッジリストを走査線方向の２分探索木から作成した場合を示したが、当然のことながら上述の実施例の走査線方向と副走査線方向を入れ替えても同様の処理が可能である。
【００６５】
また、２分探索木へのエッジの登録ルールおよび２分探索木からのエッジリストの作成のルールは、上述の実施例のものに限らず、他のルールを適用できることを付記しておく。
【００６６】
【発明の効果】
以上説明したように、この発明によれば、走査により選択したエッジを２分探索木に登録するとともに、検出されたドロップアウトをもその２分探索木に登録し、２分探索木からエッジリストを作成するように構成したので、
エッジリストのソートが必要無く、２方向のビットマップを合成することによるドロップアウトの補正も行う必要がないので、使用するメモリ容量を低減し、高速に処理を行うことができる。
【図面の簡単な説明】
【図１】この発明に係わる画像処理装置の構成を示すブロック図。
【図２】画像処理装置１０の実際の構成を示すブロック図。
【図３】２分探索木の概念図。
【図４】新たな登録を行う場合のルールを示した図。
【図５】登録しようとする値が既に登録されている場合のルールを示した図。
【図６】２分探索木へのドロップアウトの登録およびドロップアウトが登録されている２分探索木へのエッジの登録のルールを示した図。
【図７】画像処理装置１０の動作の流れを示すフローチャート（１）。
【図８】画像処理装置１０の動作の流れを示すフローチャート（２）。
【図９】画像処理装置１０の動作の流れを示すフローチャート（３）。
【図１０】画像処理装置１０の動作の流れを示すフローチャート（４）。
【図１１】画像処理装置１０の動作の流れを示すフローチャート（５）。
【図１２】ドロップアウト登録の必要の有無を示した図。
【図１３】２分探索木で図１１に示したエッジリストの作成を行った場合の作成順序を示した図。
【図１４】文字の輪郭線とその輪郭線から得られるビットマップを示した図。
【図１５】画素の形状を示した図。
【図１６】各画素が輪郭線の内外のいずれかかを判定する方法を示した図。
【図１７】走査線および副走査線を示した図。
【図１８】文字の描画例を示した図。
【図１９】エッジの登録方法を示した図。
【図２０】ドロップアウトの発生例を示した図。
【図２１】ドロップアウトの発生と検出の例を示した図。
【符号の説明】
１座標変換手段
２交点・ドロップアウト検出手段
２ａエッジ登録手段
２ｂドロップアウト判定手段
２ｃエッジリスト作成手段
３ビットマップ展開手段
１０画像処理装置
１１ＣＰＵ
１２ＲＡＭ
１３ＲＯＭ
１４外部記憶装置
１５ビデオＩ／Ｆ（インタフェイス）
１６フレームバッファ
１７プリンタＩ／Ｆ（インタフェイス）
５０根
５１−１〜７４−１３節点[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to an image processing method and apparatus, and more particularly to an image processing method and apparatus that stores character design information as outline information and corrects dropout when outputting small-sized characters.
[0002]
[Prior art]
In an output device based on a bitmap screen, such as a page printer or a display, as the pixels become finer, that is, as the resolution increases, more data is required to display characters and graphics of the same size. In particular, even for character information having a fixed contour, it is necessary to have bitmap data for each size, which is inefficient. Therefore, character information does not have bitmap data for each size but outline information. A method of displaying a character by enlarging or reducing is followed by filling the inside of the outline of the character is advantageous.
[0003]
However, when a small-size character is output (displayed) in the method of filling the inside of the outline, the interval between the outlines may be too narrow and dropout may occur in the fill. In order to avoid this dropout phenomenon, there are two methods: outline information that has outline change information at the time of small size output in the outline information itself, and method of detecting and correcting the dropout occurrence location in the processing system. There are two. The former is generally faster in processing and can correct the destruction of the character design at the data creation stage. However, when the number of characters increases, the data size increases and the time and effort required for data creation also increase. In the latter case, the data does not need to be changed, but the processing is slower, and the character design may be distorted compared to the former case. Therefore, it is now mainstream to combine the former and the latter.
[0004]
Since the present invention relates to the latter method among the above two methods, the latter method will be further described.
[0005]
FIG. 14 shows an outline of a character and a bit map obtained from the outline. When a character is output (displayed) as shown in the figure, a bitmap is output in which pixels inside the outline of the character to be output are inverted with respect to other pixels. Each pixel is a square having a height of 1 and a width of 1, as shown in FIG. 15, and integer coordinate values come at the four corners. The coordinates of the pixel are represented by the coordinate value of the lower left corner, which will be referred to as pixel coordinates. When the center point of a pixel is inside the contour as shown in FIG. 16, the pixel is determined to be inside the contour.
[0006]
Next, an example of scan conversion will be described. In this example, the inside and outside of the outline are determined under a condition called an EVEN-ODD rule that does not consider the direction of the outline.
[0007]
Here, a line connecting the center points of the pixels in the x-axis direction as shown in FIG. 17 is called a scanning line or a main scanning line, and a line connecting the center points of the pixels in the y-axis direction is called a sub-scanning line. . When finding the inside of the contour, as shown in FIG. 18 (a), the intersection of the contour and the scanning line is determined, and the intersection and the y coordinate are equal, and among the pixels on the right side of the intersection (the center point of the pixel) Select the closest pixel. This pixel is called an edge, and the edge can be obtained by, for example, rounding off the first decimal place of the x coordinate value of the intersection.
[0008]
Now, when the edges are selected for all the contour lines, the pixels sandwiched between the edges are inverted for each scanning line as shown in FIG. At this time, of the edges serving as the start point or the end point of the pixel to be inverted, the pixel serving as the start point is inverted, but the pixel serving as the end point is not inverted.
[0009]
Further, when edges overlap at the stage of selecting an edge, if the overlap is an even number, the edge is deleted. Unless this operation is performed, the filling is not performed accurately.
Note that the same image can be obtained even if scan conversion is performed from the sub-scanning line direction unless dropout occurs.
[0010]
By the way, the simplest way to register the selected edge is to invert the pixel with the actual bitmap as shown in FIG. However, when the size of the character becomes large or at high resolution, all pixels must be examined at the filling stage, which is disadvantageous in terms of speed, and complicated painting rules are used due to the simple structure. It is disadvantageous that the memory efficiency is deteriorated if edge information such as the direction of a contour line is added.
[0011]
Therefore, there is a method of managing each scanning line in a list as shown in FIG. In this method, the selected edges are registered in a list, and when all the edges are registered, each list is sorted. In the filling process, two edges are extracted from the list, and these are set as a start point and an end point. This list is called an edge list.
[0012]
Here, FIG. 20 shows an example of the occurrence of dropout.
When two contour lines pass between the center points of adjacent pixels as shown in FIG. 20A, dropout occurs because there is no pixel to be inverted. This is because the edges selected from the respective intersections of the two outlines with the scanning line overlap as shown in FIG. 20B. If the space between the two outlines is outside the outline, the problem is raised. No, but it is not usually known at the edge selection stage whether it is inside or outside. Such pixels can be prevented from dropping out by deleting them during scan conversion. However, such pixels need to be registered in a bitmap or edge list different from the edge. FIG. 20C shows an example of a dropout that cannot be found from the edge obtained from the intersection between the contour and the scanning line. In this case, the dropout is selected by selecting an edge from the sub-scanning line direction. Can be found. As can be seen from this example, in order to find all the dropouts, it is necessary to execute from both the scanning line direction and the sub-scanning line direction.
[0013]
As a technique for preventing or suppressing the occurrence of dropout, an "outline font drawing apparatus" disclosed in JP-A-8-87602 and an "outline font drawing apparatus" disclosed in JP-A-8-95545 are disclosed. And so on.
[0014]
In the "outline font drawing apparatus" described in JP-A-8-87602, scan conversion is performed in the scanning line direction and the sub-scanning line direction, and separate bitmaps are created. I have a bitmap image. However, in this outline font drawing device, scan conversion is always performed from both the scanning line direction and the sub-scanning line direction, so that the time required for detecting a dropout becomes longer and characters that are less likely to cause a dropout are generated. Or, when a part of a character is scanned and converted, useless processing is performed.
[0015]
In the "outline font drawing apparatus" described in Japanese Patent Application Laid-Open No. 8-95545, scan conversion is usually performed by shifting a scan line set at the center of each pixel, thereby suppressing the occurrence of dropout. I have. However, since the occurrence of dropouts is suppressed by shifting the scan line, there is a possibility that an image different from the image originally desired may be created, and the moving direction of the scan line is determined from the direction of the outline. There are some rules that cannot be applied depending on the filling rules.
[0016]
FIG. 21 shows an example of occurrence and detection of dropout. FIG. 21A shows an example in which dropout occurs due to scan conversion from the scanning line direction, and FIG. FIG. 21C shows a detection result of a dropout from the sub-scanning line direction. In such a case, an image without pixel dropout as shown in FIG. 21D is obtained by combining the images in FIGS. 21A, 21B, and 21C. be able to.
[0017]
In such processing, if the size of the character is sufficiently large and no dropout occurs, the selection of the edge from the outline may be performed from either the scanning line or the sub-scanning line direction. If you need to handle small dropouts, you have to perform edge selection from both directions.
[0018]
[Problems to be solved by the invention]
As described above, in a conventional image processing apparatus, scan conversion is generally performed from both the horizontal (main scanning) direction and the vertical (sub-scanning) direction, and edges are registered in an edge list. When performing dropout correction, it is necessary to sort edges registered in the edge list in both the horizontal and vertical directions, which takes time. In addition, if edges obtained from both directions are combined as an edge list, it takes more time. Therefore, the synthesis was performed using the bitmap. Therefore, an output device that can use the edge list (the edge list can be directly input and used) cannot be used at high speed, and a large amount of memory is required for using the bitmap.
[0019]
Therefore, an object of the present invention is to provide an image processing method and apparatus capable of creating an edge list at high speed and reducing the capacity of a memory to be used.
[0020]
[Means for Solving the Problems]
In order to achieve the above object, the invention according to claim 1 scans a contour of a character to be drawn, sequentially selects edges from intersections of the scanning line to be scanned and the contour, and registers the edges in an edge list. In an image processing method in which a character is expressed by inverting pixels between predetermined edges among the edges based on the edge list and developed on a bitmap, an intersection between a scanning line to be scanned and the contour line Are sequentially registered as data of the binary tree structure, and if an edge having the same coordinate value as the coordinate value of the selected edge is already registered in the data of the binary tree structure, The method is characterized in that edges having the same coordinate value are invalidated, the selected edges are registered as dropout edges, and an edge list is created based on the binary tree structure data.
[0021]
Also, in the invention of claim 2, in the invention of claim 1, the selected edge is a coordinate value of an edge currently registered at a root or a node of the binary tree structure and a coordinate value of the selected edge. Are registered at the nodes of the binary tree structure determined based on the magnitude relation of. The dropout edge having the same coordinate value as the coordinate value of the selected edge is already registered in the data of the binary tree structure. In this case, the coordinate value of the dropout edge is regarded as being larger than the coordinate value of the selected edge, and is registered at a node determined based on the magnitude relation.
[0022]
Also, in the invention according to claim 3, in the invention according to claim 2, the drop-out edge is such that an edge having the same coordinate value as the coordinate value of the drop-out edge is not registered in the data of the binary tree structure. Is registered at a node determined based on the magnitude relationship, and when an edge having the same coordinate value as the coordinate value of the dropout edge is already registered , the coordinate value of the dropout edge is registered. And is registered as a node determined based on the magnitude relationship assuming that it is larger than the coordinate value of the edge.
[0023]
According to a fourth aspect of the present invention, in the invention according to any one of the first to third aspects, the creation of the edge list includes the step of determining the coordinate values of the edges registered at the roots and nodes of the binary tree structure in a predetermined order. It is characterized in that it is carried out by reading in.
[0024]
According to a fifth aspect of the present invention, in any one of the first to fourth aspects of the present invention, the scanning is performed in a main scanning direction and a sub-scanning direction orthogonal to the main scanning direction, and is selected from the scanning in the main scanning direction. The registered edge is registered in the data of the first binary tree structure, and the edge selected from the scan in the sub-scanning direction is registered in the data of the second binary tree structure. When the selected edge is registered as a dropout edge, the dropout edge is registered in the data of the first binary tree structure.
[0025]
According to a sixth aspect of the present invention, an outline of a character to be drawn is scanned, edges are sequentially selected from intersections between the scanning line to be scanned and the outline, and the edges are registered in an edge list. In an image processing apparatus that expresses a character by inverting pixels between predetermined edges among the edges, and develops it on a bit map, an edge selected from the intersection of a scanning line to be scanned and the contour line is represented by 2 If the edge having the same coordinate value as the coordinate value of the selected edge is already registered in the binary tree structure data, the edge having the same coordinate value is sequentially registered as the binary tree structure data. an edge registration means disabled to be registered as a drop-out edge edges that the select, an edge list based on the binary tree data registered edge of the structure by the edge registration means Characterized by comprising the edge list creation means for forming.
[0026]
According to a seventh aspect of the present invention, in the sixth aspect of the present invention, the edge registering means stores the selected registered edge in the coordinate value of the edge and the edge or node currently registered in the root or node of the binary tree structure. When a drop-out edge having the same coordinate value as the coordinate value of the selected edge is already registered in the binary tree structure data, the node is determined based on the magnitude relationship with the coordinate value of Is characterized in that the coordinate value of the dropout edge is considered to be larger than the coordinate value of the selected edge, and registered at a node determined based on the magnitude relationship.
[0027]
According to an eighth aspect of the present invention, in the invention of the seventh aspect, the edge registering means has registered in the data of the binary tree structure an edge having the same coordinate value as a coordinate value of a dropout edge to be registered. If not, the drop-out edge is registered at a node determined based on the magnitude relationship. If an edge having the same coordinate value as the coordinate value of the drop-out edge to be registered is already registered, the drop-out edge is registered. The dropout edge is registered at a node determined based on the magnitude relationship, assuming that the coordinate value of the edge is larger than the coordinate value of the edge to be registered.
[0028]
According to a ninth aspect of the present invention, in the invention according to any one of the sixth to eighth aspects, the edge list creating means determines a coordinate value of an edge registered in a root and a node of the binary tree structure in a predetermined order. To create an edge list.
[0029]
A tenth aspect of the present invention, according to any one of the sixth to ninth aspects, further comprises a drop-out determination unit, and performs the scanning from a main scanning direction and a sub-scanning direction orthogonal to the main scanning direction. The edge registering means registers an edge selected from the scanning in the main scanning direction in data having a first binary tree structure, and stores an edge selected from the scanning in the sub-scanning direction in a second binary tree. Registered in the data of the structure, the drop-out determination means drops the selected edge when the edge selected from the scan in the sub-scanning direction has already been registered in the second binary tree structure. It is characterized in that it is determined as an out-edge and registered in the data of the first binary tree structure.
[0034]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, an embodiment of an image processing method and apparatus according to the present invention will be described in detail with reference to the accompanying drawings.
[0035]
FIG. 1 is a block diagram showing a configuration of an image processing apparatus according to the present invention.
The image processing apparatus 10 includes a coordinate conversion unit 1 that performs coordinate conversion such as enlargement / reduction of outline information and divides a curve (contour line information) into straight lines of a size that can be seen smoothly according to pixels (approximation using a plurality of straight lines). An intersection / dropout detecting means 2 for creating an edge list and detecting a dropout by detecting an intersection of a scanning line and a sub-scanning line with a contour line; and a bitmap developing means 3 for generating a bitmap from the edge list. It is composed. Further, the intersection / dropout detection means 2 selects an edge from the intersection of the scanning line and the contour line, and registers the edge in a binary search tree described later, based on the edge selected from the sub-scanning line direction. It comprises a dropout detecting means 2b for detecting a dropout, and an edge list creating means 2c for creating an edge list based on a binary search tree in which edges are registered.
[0036]
As shown in FIG. 2, the image processing apparatus 10 actually includes a CPU 11, a RAM 12, a ROM 13, an external storage device 14, a video I / F (interface) 15, a frame buffer 16, and a printer I / F (interface). 17 is provided.
[0037]
The coordinate conversion means 1, the intersection / dropout detection means 2, and the bitmap development means 3 shown in FIG. 1 are configured on the CPU 11 by a program stored in the RAM 12 or the ROM 13. The RAM 12 stores the above-described edge list and the like, and the ROM 13 and the external storage device 14 store outline font data. The frame buffer 16 temporarily stores the bitmap image developed by the bitmap developing means 3 and stores the image in a display (not shown) connected to the video I / F 15 or a page printer connected to the printer I / F 17. (Not shown).
[0038]
Next, the operation of the image processing apparatus 10 will be described.
The image processing apparatus 10 registers an edge selected by scanning in a binary search tree (data of a binary tree structure) before creating an edge list. This binary search tree corresponds to one edge list, and a binary search tree is prepared for each scanning line (sub-scanning line) in the scanning line direction and the sub-scanning line direction.
[0039]
Here, a rule for registering an edge in the binary search tree will be described.
FIG. 3 is a conceptual diagram of a binary search tree.
As shown in the figure, nodes 51-1 and 51-2 are connected to the root 50, and the node 51-1 on the left of the root 50 has a value (10) smaller than the value (10) registered in the root 50. 5) is registered, and a value (12) larger than the value registered in the root 50 is registered in the node 51-2 on the right side of the root 50.
[0040]
A node 52-1 in which a small value (3) is registered on the left side and a node 52-2 in which a large value (7) is registered are connected to the node 51-1 (value 5). 2 (value 12) is connected to a node 52-4 in which a large value (20) is registered on the right side.
Similarly, the node 53-1 is connected to the node 53-1 and the node 52-4 is connected to the nodes 53-7 and 53-8.
[0041]
The value registered in the root 50 or the nodes 51-1 to 53-8 is the x coordinate value of the edge in the binary search tree for registering the edge selected from the scanning line direction, and is selected from the sub-scanning line direction. In the binary search tree for registering the set edge, it is the y coordinate value of the edge.
[0042]
Here, when newly registering, for example, when registering a new value (8), first, as shown in FIG. 4A, the value (8) to be registered and the value (10) of the root 50 are changed. If the value to be registered is smaller, the value is then compared with the value (5) of the left node 51-1. In this case, since the value (8) to be registered is larger, the value is compared with the value (7) of the node 52-2 on the right side. Also in this case, since the value (8) to be registered is larger, an attempt is made to compare the value with the right node. However, since no node exists, a new node 53-4 is set here and the value (8) is set. Register
[0043]
Further, when registering the value (18), the root 50 is compared with the nodes 51-2, 52-4, and 53-7 in the same manner as shown in FIG. , The value (18) is registered in the new node 54-14.
[0044]
If the value to be registered has already been registered, that is, if an edge having the same coordinates as the edge to be registered has already been registered, for example, a binary search tree as shown in FIG. When the value (12) is to be registered in the node 51-2, since the same value (12) is registered in the node 51-2, this is set to the invalid node 61-2 as shown in FIG. Then, this value is registered as a dropout in the binary search tree (in the scanning line direction). If the value to be registered has been registered as an invalid node, it is registered as a valid node again.
[0045]
FIG. 6 is a diagram showing rules for registering a dropout in the binary search tree and registering an edge in the binary search tree in which the dropout is registered.
The registration of a dropout in a binary search tree and the registration of an edge in a binary search tree in which a dropout is registered are usually performed in both cases when the dropout with the same coordinate value and the edge are not registered. Is performed in the same manner as the registration of the edge. For example, when registering a dropout (value 13) in the binary search tree shown in FIG. 6A, as shown in FIG. 6B, a node 72- indicating the dropout is located on the left side of the node 51-2. Set 3 and register.
[0046]
If an edge having the same coordinates as the dropout to be registered has already been registered, registration is performed by assuming that the value of the dropout is greater than the value of the edge. For example, when a dropout (value 12) is registered in the binary search tree shown in FIG. 6C, since an invalid edge (value 12) is registered at the node 61-2, the dropout (value 12) is registered. 12) is regarded as a value larger than the edge (value 12) as shown in FIG. 6D, and is registered by setting a node 74-13 indicating a dropout to the left of the node 53-7. Similarly, when dropout (value 3) is registered in the binary search tree shown in FIG. 6E, since the edge (value 3) is registered at the node 52-1, the dropout (value 3) is registered. Is regarded as a value larger than the edge (value 3) as shown in FIG. 6 (f), and is registered by setting a node 73-2 indicating a dropout to the right of the node 52-1.
[0047]
Similarly, when an edge is to be registered, if a dropout having the same coordinate value has already been registered, registration is performed on the assumption that the dropout value is larger than the edge value. For example, when the edge (value 7) is registered in the binary search tree shown in FIG. 6G, since the dropout (value 7) is registered at the node 72-2, the edge (value 7) is 6 (h), it is regarded as a value smaller than the dropout (value 7), and a node 53-3 indicating an edge is set and registered on the left side of the node 72-2.
[0048]
As described above, when the edge value and the dropout value are the same, it is considered that the dropout value is larger than the edge value because the edge list is obtained from the binary search tree by the method described later. This is related to the fact that nodes with smaller values are processed first. This is because the processing for dropouts is different depending on whether inside or outside the contour line, so it is convenient if edges are registered in the edge list before dropouts. Is also regarded as a small value.
[0049]
Next, the operation of the image processing apparatus 10 will be described with reference to FIGS.
7 to 11 are flowcharts showing the flow of the operation of the image processing apparatus 10, respectively.
[0050]
The image processing apparatus 10 reads image information and the like stored on a RAM (or RAM 12) not shown through an interface or the like not shown by the CPU 11. If the image information is character codes, outline font data is read from the ROM 13 or the external storage device 14 and the execution of the image generation program is started (FIG. 7, step 101).
[0051]
Next, the CPU 11 creates a binary search tree in the scanning line direction, a binary search tree in the sub-scanning line direction, an edge list, and the like on the RAM 13, and initializes these lists (step 102). Subsequently, the CPU 11 executes the image conversion means 1 to convert the coordinates of the outline (outline) into a size desired to be output (step 103), and divides the outline into a plurality of short straight lines (the curved portion is approximated by a straight line). , Step 104).
[0052]
When the division of the contour is completed, the CPU 11 executes the intersection / dropout detecting means 2 to select an edge, register it in the binary search tree, and detect a dropout (step 105). Then, an edge list is created (step 106). The details of the operations in steps 105 and 106 will be described later.
[0053]
Next, the CPU 11 executes the bitmap developing means 3 to generate a bitmap from the edge list (step 107) and outputs it to the frame buffer 16 (step 108).
[0054]
Here, an output device (not shown) (such as a display or a page printer) checks the frame buffer 16 at regular time intervals or in response to an end signal from the CPU 11 and outputs a registered bitmap, so that the image processing device 10 The operation ends (step 109).
[0055]
Next, details of the edge selection, the registration in the binary search tree, and the dropout detection processing in step 105 described above will be described.
The intersection / dropout detection means 2 first sets the first (first in a preset order, whichever order may be used) contour line divided into straight lines (FIG. 8, step 201), Is detected (step 202). Subsequently, the decimal point of the y coordinate value of the detected intersection is rounded down, and the decimal point of the x coordinate value is rounded to obtain pixel coordinates (step 203). Since the pixel coordinates are the same as the intersection point and the y coordinate and are the closest pixels among the pixels (center points of the pixels) on the right side of the intersection point, they are sequentially registered as edges in the binary search tree in the scanning line direction ( Step 204). For registration in the binary search tree in the scanning line direction, the edge registration means 2a is executed, and first, the first edge is set (step 301 in FIG. 9), and the binary search is registered from the y coordinate value of the coordinate value. Select a tree. Next, an edge is registered in the binary search tree according to the above-described rule (step 302). If the registered edge is a dropout (YES in step 303), the coordinates of the dropout are set (step 304) and registered in the binary search tree (step 302).
[0056]
If the registered edge is not a drop-out (NO in step 303), the next edge is set and repeated (step 306) until the last edge is registered (NO in step 305). Is registered (YES in step 305), the flow advances to step 205 (FIG. 8).
[0057]
Next, the intersection of the set contour line and the sub-scanning line is detected (step 205), the decimal point of the x coordinate value of the detected intersection is rounded down, and the decimal point of the y coordinate value is rounded off to calculate the pixel coordinate. It is acquired (step 206) and is sequentially registered as an edge in the binary search tree in the sub-scanning direction (step 207). To register in the binary search tree in the sub-scanning line direction, to register in the scanning line edge list, execute the dropout detection means 2b, first set the first edge (step 401 in FIG. 10), and set its coordinates. The binary search tree to be registered is selected from the x coordinate value of the value. Next, an edge is registered in the binary search tree according to the above-described rule (step 402). If the registered edge is a dropout (YES in step 403), the dropout is registered in a binary search tree in the scanning line direction (step 404). This registration is performed by the edge registration means 2a, and the registration method is the same as the above-described method, and therefore the description is omitted.
[0058]
If the dropout is registered in the binary search tree in the scanning line direction (step 404) or if the registered edge is not a dropout (NO in step 403), these processes are performed until the last edge is registered (step 405). NO), the next edge is set and repeated (step 406). When the last edge is registered (YES in step 405), the process proceeds to step 208 (FIG. 8).
[0059]
These processes (steps 202 to 207) are repeated until the next contour is set (NO in step 208) until the process for the last contour is completed (step 209). Is completed (YES in step 208), the process in step 105 (FIG. 7) is completed, and the flow advances to step 106.
[0060]
Next, details of the process of creating an edge list from the binary search tree in step 106 described above will be described.
The intersection / dropout detection means 2 executes the edge list creation means 2c, and first sets the first edge (edge or dropout registered at the root) of the binary search tree in the scanning line direction (FIG. 11). , Step 501). Here, if there is a node on the left side of the root, the processing after step 502 is recursively called (step 502). If the recursive call is completed or not performed, the currently set one is dropped out. If the dropout is outside the outline (YES in step 503), it is not necessary to register if the dropout is inside the outline as shown in FIG. If the dropout is outside the outline as shown in FIG. 12 (b), it is necessary to register it.) The start point and the end point for one pixel are registered in the edge list (step 504). If it is an edge (NO in step 503), if the edge is valid, it is registered in the edge list (step 505). Next, if there is a node on the right side of the currently processed root or node, the processing after step 502 is recursively called (step 506), and when all the recursive calls are completed or not performed, The process of creating the edge list ends, and the process proceeds to step 107 (FIG. 7).
[0061]
Here, an example in which the edge list shown in FIG. 11 is created with an actual binary search tree will be described with reference to FIG.
First, when the root 50 is set (step 501), a recursive call is performed because the node 51-1 exists on the left side of the root 50 (steps 502-0 and -n indicate the number of times the recursive call is performed; Indicates a step without a recursive call).
[0062]
Next, since the node 52-1 exists on the left side of the set node 51-1, a recursive call is performed again (step 502-1).
When the process is performed by the recursive call in this way, the process of the step 504-3 recursively called in the step 502-2 is performed on the node 53-1 and the process of the step 504-3 is performed on the node 52-1. After the process of Step 3, the process returns to Step 502-2, and the process of Step 504-2 is performed. For the node 52-2, the process returns to the step 502-1 after the process of the step 504-2, and the process for the node 51-1 (step 504-1) is performed. The process of the called step 504-2 is performed.
[0063]
Accordingly, each processing is performed from the nodes 53-1 (value 1) to the nodes 52-1 (value 3), the nodes 51-1 (value 5), the nodes 52-2 (value 7), the roots 50 (value 10), and the nodes 51-1 (value 10). -2 (value 12), node 53-7 (value 15), node 52-4 (value 20), node 53-8 (value 22), and are registered in the edge list in ascending order without sorting. It can be performed.
[0064]
In the above-described embodiment, the case where the edge list is created from the binary search tree in the scanning line direction has been described. Is possible.
[0065]
It should be noted that the rules for registering edges in the binary search tree and the rules for creating an edge list from the binary search tree are not limited to those in the above-described embodiment, and other rules can be applied.
[0066]
【The invention's effect】
As described above, according to the present invention, the edge selected by scanning is registered in the binary search tree, and the detected dropout is also registered in the binary search tree. Has been configured to create
Since it is not necessary to sort the edge list and to correct the dropout by synthesizing the bitmaps in two directions, the memory capacity to be used can be reduced and the processing can be performed at high speed.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of an image processing apparatus according to the present invention.
FIG. 2 is a block diagram illustrating an actual configuration of the image processing apparatus 10.
FIG. 3 is a conceptual diagram of a binary search tree.
FIG. 4 is a diagram showing rules for performing new registration.
FIG. 5 is a view showing a rule when a value to be registered has already been registered;
FIG. 6 is a diagram showing rules for registering a dropout in a binary search tree and registering an edge in a binary search tree in which the dropout is registered.
FIG. 7 is a flowchart (1) showing a flow of an operation of the image processing apparatus 10.
FIG. 8 is a flowchart (2) showing the flow of the operation of the image processing apparatus 10.
FIG. 9 is a flowchart (3) showing a flow of the operation of the image processing apparatus 10.
FIG. 10 is a flowchart (4) showing the flow of the operation of the image processing apparatus 10.
FIG. 11 is a flowchart (5) showing the flow of the operation of the image processing apparatus 10.
FIG. 12 is a diagram showing the necessity of dropout registration.
FIG. 13 is a diagram showing a creation order when the edge list shown in FIG. 11 is created using a binary search tree.
FIG. 14 is a diagram showing an outline of a character and a bitmap obtained from the outline.
FIG. 15 illustrates a shape of a pixel.
FIG. 16 is a diagram showing a method for determining whether each pixel is inside or outside a contour line.
FIG. 17 is a diagram showing a scanning line and a sub-scanning line.
FIG. 18 is a diagram illustrating a drawing example of a character.
FIG. 19 is a diagram showing an edge registration method.
FIG. 20 is a diagram showing an example of occurrence of dropout.
FIG. 21 is a diagram illustrating an example of occurrence and detection of dropout.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 Coordinate conversion means 2 Intersection / dropout detection means 2a Edge registration means 2b Dropout determination means 2c Edge list creation means 3 Bitmap development means 10 Image processing device 11 CPU
12 RAM
13 ROM
14 External storage device 15 Video I / F (interface)
16 Frame buffer 17 Printer I / F (interface)
50 Roots 51-1 to 74-13 Nodes

Claims

A contour line of a character to be drawn is scanned, edges are sequentially selected from intersections of the scanning line to be scanned and the contour line, and registered in an edge list. In an image processing method in which characters are expressed by inverting the pixels of
Edges selected from the intersection of the scanning line to be scanned and the contour are sequentially registered as binary tree structure data, and an edge having the same coordinate value as that of the selected edge is defined as a binary tree structure. If the data is already registered in the data, invalidating the edge having the same coordinate value, registering the selected edge as a dropout edge, and creating an edge list based on the binary tree structure data An image processing method comprising:

The selected edge is a node of the binary tree structure determined based on a magnitude relationship between a coordinate value of an edge currently registered at a root or a node of the binary tree structure and a coordinate value of the selected edge. If the drop-out edge having the same coordinate value as the coordinate value of the selected edge has already been registered in the data of the binary tree structure, the coordinate value of the drop-out edge is stored in the selected edge. 2. The image processing method according to claim 1, wherein the coordinate value is regarded as being larger than the coordinate value and registered at a node determined based on the magnitude relation.

The dropout edge is registered at a node determined based on the magnitude relationship if an edge having the same coordinate value as the coordinate value of the dropout edge is not registered in the binary tree structure data, If an edge having the same coordinate value as the coordinate value of the dropout edge has already been registered , the coordinate value of the dropout edge is considered to be larger than the coordinate value of the registered edge, and 3. The image processing method according to claim 2, wherein the image is registered at a node determined based on the relationship.

4. The edge list is created by reading out coordinate values of edges registered at the roots and nodes of the binary tree structure in a predetermined order. Image processing method.

The scanning is performed in a main scanning direction and a sub-scanning direction orthogonal to the main scanning direction, and an edge selected from the scanning in the main scanning direction is registered in data of a first binary tree structure. Is registered in the data of the second binary tree structure, and when the edge selected from the scan in the sub-scanning direction is registered as a drop-out edge, the drop-out edge is registered. The image processing method according to claim 1, wherein the image data is registered in the data having the first binary tree structure.

A contour line of a character to be drawn is scanned, edges are sequentially selected from intersections of the scanning line to be scanned and the contour line, and registered in an edge list. In an image processing device that expresses a character by inverting the pixels of and develops it on a bitmap,
Edges selected from the intersection of the scanning line to be scanned and the contour are sequentially registered as binary tree structure data, and an edge having the same coordinate value as that of the selected edge is defined as a binary tree structure. Edge registration means for invalidating the edge having the same coordinate value and registering the selected edge as a dropout edge, if the data is already registered in the data;
An image processing apparatus comprising: an edge list creating unit that creates an edge list based on edges registered in the binary tree structure data by the edge registering unit.

The edge registration means,
The selected registered edge is registered at a node determined based on the magnitude relationship between the coordinate value of the edge and the coordinate value of the edge currently registered at the root or the node of the binary tree structure, and the binary tree is registered. If a dropout edge having the same coordinate value as the selected edge is already registered in the structure data, it is determined that the coordinate value of the dropout edge is larger than the coordinate value of the selected edge. 7. The image processing apparatus according to claim 6, wherein the registration is performed as a node determined based on the magnitude relation.

The edge registration means,
If an edge having the same coordinate value as the coordinate value of the dropout edge to be registered is not registered in the binary tree structure data, the dropout edge is registered at a node determined based on the magnitude relation. If an edge having the same coordinate value as the coordinate value of the dropout edge to be registered is already registered, it is considered that the coordinate value of the dropout edge is larger than the coordinate value of the edge to be registered. 8. The image processing apparatus according to claim 7, wherein the dropout edge is registered at a node determined based on the relationship.

The edge list creation means,
9. The image processing apparatus according to claim 6, wherein coordinate values of edges registered at roots and nodes of the binary tree structure are read in a predetermined order to create an edge list.

In addition to a drop-out determination unit,
Perform the scanning from a main scanning direction and a sub-scanning direction orthogonal to the main scanning direction,
The edge registration means registers an edge selected from the scan in the main scanning direction in data of a first binary tree structure, and stores an edge selected from the scan in the sub-scanning direction in a second binary tree structure. Register in the data of
The drop-out determining means determines that the selected edge is a drop-out edge when the edge selected from the scan in the sub-scanning direction is already registered in the second binary tree structure. 10. The image processing apparatus according to claim 6, wherein the image data is registered in data having a first binary tree structure.