JPH02153484A - 画像塗りつぶし装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、アウトラインフォントを生成する際、アウト
ラインフォントの輪郭内を塗シつぶす画像塗りつぶし装
置に関するものである。

従来の技術 以下、第１５図により、従来の画像塗りつぶし装置の原
理について説明する。従来の画像塗りつぶし装置では、
任意の閉領域は、第１５図（Ａ）の様に、あらかじめ画
像記憶装置に書き込まれる。

そして、この閉領域内の１つの画素が、塗りつぶし開始
点１５０１　（通常、シードという）として与えられる
。そして、塗りつぶしは、このシード１５旧を起点とし
て開始する。このシード１５０１から、１ライン横方向
に塗シつぶす際、シード１５０１の上下にある閉領域内
の点を次の塗りつぶし開始点１５０２として記憶する〔
第１５図（Ｂ）〕。

そして、シード１５０１から１ライン塗りつぶす。

この際、第１５図（Ｂ）の様な閉領域１５０３が発生す
ると、塗りつぶし開始点１５０２はこの閉領域１５０３
とは、別の閉領域になってしまう。このため閉領域１５
０３は、塗りつぶせなくなってしまう。

そこで、１ライン塗る前に、第１５図（Ａ）の黒丸で示
した点１５０４をスタックに積んでおく必要がある。こ
のようにして、ｌライン毎に塗りつぶして行くのが従来
の方式である。〔参考文献　日経エレクトロニクス　１
９８７．２．２３　Ｐ１５９〜Ｐ１６０”拡大、縮小、
回転”塗りつぶしを高速処理する描画プロセッサ〕 第１４図は、従来の画像塗りつぶし装置のブロック構成
を示したものである。第１４図において、１４０１は任
意の閉領域の輪郭の座標を発生する座標発生手段である
。この座標発生装置１４０１かも出力された画素の座標
は、１４０２の画像記憶手段に入力される。１４０５は
、画像記憶手段１４０２に記憶された画像情報を表示す
る画像表示手段である。１４０３は塗りつぶしを行う際
、第１５図（Ａ）の黒丸で示した画素１５０４を記録す
るスタック、１４０４はこれらの制御を行うプロセッサ
、１４０６はこれらをつなぐバスである。

発明が解決しようとする課題 しかしながら、第１４　図の画像塗りつぶし装置では、
あらかじめ、閉領域を構成する輪郭情報を画像記憶手段
１４０２に書き込む必要がある。そして、その後この輪
郭をたどりながら、塗りつぶしを行っていく。このため
、画像記憶手段１４０２に対するアクセス回数が多くな
り、輪郭を発生させて、さらに塗りつぶしを行い、画像
を表示するのに多くの時間を必要としていた。

本発明は上記課題に鑑み、閉領域を構成する座標が与え
られる度に、この閉領域を塗りつぶすだめのデータ構造
を作成していく。この結果、閉領域を構成する座標がす
べて与えられるのと同時に塗りつぶしの実行を可能にす
る。このため、閉領域の塗りつぶしをより高速に実行す
ることを可能にするものである。

課題を解決するための手段 本発明は、上記課題を解決するため、閉領域を構成する
画素の２次元座標のうち一方の座標値のそれぞれに対応
した小領域を持つ第１の座標記憶手段と、前記第１の座
標記憶手段の小領域によって指示された小領域を持ちこ
の小領域内に２次元座標の他の一方の座標値を記憶する
第２の座標記憶手段と、前記第２の座標記憶手段のうち
使用されていない領域を示す自由領域指示手段と、前記
第２の座標−記憶手段の小領域によって示された座標間
に直線を描画する直線描画手段とを設けたものである。

作　　　　用 本発明は、上記構成により、任意の閉領域を高速に塗り
つぶすものである。第１の座標記憶手段には、閉領域を
構成する座標の一方（たとえばＸ。

Ｘ座標系でいえばＸ座標）の各々の座標値に対する小領
域（これをパケットと呼ぶ）を持っている。

第２の座標記憶手段には、他の一方の座標（例えばＸ座
標）を記憶する小領域（これをセルと呼ぶ）が存在する
。このセルは、閉領域を構成する画素１つに対して、１
つ対応する。閉領域を構成する画素の座標が順に与えら
れるにしたがって、この２つのメモリ構造が構成される
。すなわち、同じＸ座標をもつ画素に対応するセルは、
第２の座標記憶手段内でＸ座標について昇順に並べられ
る。

そして、この最初のセルを、第１の座標記憶手段の対応
するパケットが指し示す。

このような構造は、閉領域を構成する画素の座標が与え
られるにつれてできあがっていく。従って、閉領域を構
成する画素の座標を発生し終えた時点で、このメモリ構
造はできあがっている。この閉領域を塗りつぶす際は、
第１の座標記憶手段のパケットを順にみていく。そして
、このパケットに第２の座標記憶手段を指すデータが記
憶されている場合は、第２の座標記憶手段を見る。そし
て、第２の座標記憶手段に記憶されたセルを最初から２
つずつ組にして行き、このセルに対応する画素を結ぶ直
線を発生させる。このようにして、任意の閉領域を塗り
つぶすものである。

実施例 第１図は、本発明の一実施例における画像塗りつぶし装
置のブロック構成図である。第１図において、１０１は
任意の閉領域を構成する画素の座標を発生する座標発生
装置、１０２は第１の座標記憶手段であり、この中には
、任意の閉領域の全てのＸ座標に対応するパケットがあ
る。１０３は第２の座標記憶手段であり、任意の閉領域
を構成する画素にそれぞれ対応するセルが存在している
。１０６は直線描画手段であり、第２の座標記憶手段に
記憶されたセルを初めから２つずつ組にし、このセルに
対応する座標間の直線を描画する。１０７はこの直線を
記憶する画像記憶手段、１０９はこれらを制御するプロ
セッサ、１１０はこれらのブロック間のデータを受は渡
すパスである。

以下、本発明に用いられるアウトラインフォントについ
て若干の説明した後、上記第１図のさらに詳細な各構成
と、その動作について説明する。

第１２図は、本発明に用いられるアウトラインフォント
を示したものである。アウトラインフォントは、このよ
うに、外側の閉曲線と、内側の閉曲線によって、構成さ
れている。この閉曲線は、直線、円弧、スプライン曲線
などで構成されている。そして、第１２図のＸ印で示し
たような箇所でつながっている。通常外側の閉曲線は、
時計回り、内側の閉曲線は反時計回りである。また、こ
れらの閉曲線は、互いに接することはあっても、交差す
ることはない。アウトラインフォントを描画する場合は
、外側の閉曲線と、内側の閉曲線を描画する。そして、
この内部を塗りつぶす。このように、アウトラインフォ
ントの輪郭情報は、−筆書きである 閉領域を構成する線分が、直線、円弧、スプライン関数
といった、関数で記述されている 閉曲線同士は、接することはあっても交差することはな
い。

という特徴を持つ。

第１３図は、本発明の詳細な説明したものである。第１
３図（Ａ）は前述の閉領域を示している。

この閉領域は、Ｘ座標の範囲がＹＯ〜Ｙ８、Ｘ座標がＸ
Ｏ〜Ｘ９である。このような座標の範囲を取る場合、第
１図に示した第１の座標記憶手段１０２は、ＹＯ〜Ｙ８
にそれぞれ対応したパケットと呼ばれる小領域を持つ。

このパケットには、第２の座標記憶手段１０３へのポイ
ンタを記憶する。また、第２の座標記憶手段１０３には
、閉領域を構成する画素の個数分のセルと呼ばれる小領
域が存在する。

第１３図（Ａ）で示した閉領域を構成する画素の座標が
、この画像塗りつぶし装置に人力されると、次のような
データ構造が、第１、第２の座標記憶手段１０２．１０
３の内部に構成される。第１３図（Ａ）の、画素１３０
１、画素１３０２、画素１３０３、画素１３０４を例に
取って説明する。第１３図（Ａ）の画素１３０１と画素
１３０２のＸ座標は共にＹ３である。

そこで、第１３図（Ｂ）では、第１の座標記憶手段１０
２の￥３に対応するパケットから、第２の画像記憶手段
１０３へのポインタが延びている。このポインタは、画
素１３０１に対応するセル１３０８を指している。画素
１３０２のＸ座標は、画素１３ｏ１のＸ座標より大きい
ので、画素１３ｏ２に対応するセル１３０９は、画素１
３０１に対応するセル１３ｏ８よりも右に位置する。画
素１３ｏ１に対応するセル１３０８と、画素１３０２に
対応するセル１３ｏ９は、お互いを左右のポインタで指
示しあっている。また、画素１３０３のＸ座標と画素１
３ｏ４のＸ座標も共にＹ４で等しい。そこで、同様に、
Ｙ４に対応するパケットから、画素１３ｏ３、画素１３
ｏ４に対応するセルへのポインタが延びている。画素１
３ｏ４に対応するセル１３１１は、画素１３０３に対応
するセル１３１０の右に位置している。また、画素１３
ｏ３は画素１３０１　（７）下に、画素１３ｏ２は、画
素１３０４　（７）上に位置する。そこで、これらの画
素に対応するセルは、これらの位置関係を反映するよう
に、お互いを指し示している。このような構造が、第１
３図（Ａ）に示した全ての画素について形成される。

第１３図（Ａ）の閉領域を塗りつぶす場合は、第１の画
像記憶手段１０２のパケットを上から順にみていく。こ
れらのパケットから、第２の画像記憶手段１０３のセル
へのポインタが延びている場合は、このポインタをたど
る。そして、初めから２つずつ区切って行き、それらの
セルに対応する画素の直線を発生させる。このようにし
て、閉領域の塗りつぶしが行われる。このように、任意
の閉領域を構成する座標が発生されるに伴って、第１、
第２の座標記憶手段１０２　、１０３の内部構造を作っ
ておけば、閉領域を構成する座標の発生が終了した時点
で、即座にこの閉領域の塗りつぶしを開始することが可
能である。

第２図は、第１図の第１の座標記憶手段１０２と、第２
の座標記憶手段１０３のを示したものである。

第１の座標記憶手段１０２は、描画する閉領域のＸ座標
に対応する個数分のパケット２０Ｉと呼ばれる小領域を
持つ。第２の座標記憶手段１０３は、セル２０３と呼ば
れる区画に分割されている。このセル２０３は、閉領域
を構成する画素のＸ座標が与えられるに伴って、一つず
つ使用されていく。使用された領域は、使用済み領域２
０５となる。使用されていない領域は、自由領域２０６
である。この領域の境を自由領域指示手段１０４が指し
示している。

第３図は、第２の座標記憶手段１０３のセルの内部を示
したものである。５つの部分に分かれており、それぞれ
、前向きポインタ３０１、下向きポインタ３０２、Ｘ座
標３０３、上向きポインタ３０４、後向きポインタ３０
５である。

第４図は、第２の座標記憶手段１０３と、第１の座標記
憶手段１０２の関連を示したものである。第１の座標記
憶手段１０２のパケット４０１からは、第２の座標記憶
手段１０３のセルへ４０２のポインタがのびている。第
２の座標記憶手段１０３の各セル間では、前後左右のポ
インタが相互に張られている。

第５図は、第１の座標記憶手段１０２の内部構成を示し
たものである。第５図（Ａ）の様に、アウトラインフォ
ントのＸ座標の範囲がＹＯからＹｎまでであるとする。

この場合は、第１の座標記憶手段１０２には、Ｙｏから
Ｙｎまでの座標に対応するパケット５０１が用意される
。

第６図、第７図、第８図は、一つの閉領域を構成する画
素の座標が、この画像塗りつぶし装置に入力された場合
の第１の座標記憶手段１０２と、第２の座標記憶手段１
０３の内部構造が生成される様子を示したものである。

閉領域は６０１に示しである。第６図（Ａ）は、閉領域
の最初の１画素６０２の座標が入力されたところを示し
ている。最初に、第２の座標記憶手段１０３のセルが１
つ確保され、この画素６０２のＸ座標が書き込まれる。

次に、追ノｐｆ 画素なので、追加位置記憶手段群イには、何も記憶され
ていない。そこで、第１の座標記憶手段１０２内の、こ
の画素６０２のＸ座標に対応するパケットを見る。この
対応するパケットに、いま確保した第２の座標記憶手段
１０３のセル６０４へのポインタを記入する。追加位置
記憶手段１０５は、新たに追加したセルを指している左
側のものを指し示す様にする。この場合は、第１の座標
記憶手段１０２のこのセルを指すパケット６０４を指す
ようにする。

第６図（Ｂ）は、閉領域を構成する２つめの画素６０６
の座標が画像塗りつぶし装置に入力されたところを示し
ている。同様に、第１の座標記憶手段１０２のセルが１
つ確保される。このセル６０７には、このセル６０７に
対応する画素６０６のＸ座標が記入ｔｐｓ される。次に、追加位置記憶手段中をみる。現在、追加
位置記憶手段１０５は、第１の座標記憶手段１０２を指
している。そして、このパケットに対応するＸ座標は、
今回追加するセル６０７に対応する画素のＸ座標よりも
小さい。そこで、追加位置記憶手段１０５の指すパケッ
トの一つ上のパケットを見る。ここには、まだ何も記憶
されていないので、このパケットから、新たに追加した
セル６０５へのポインタが張られる。最後に、第２の座
標記憶手段１０３内の２つのセル同士でポインタが張ら
れる。即ち、最初のセル６０８の上向きポインタは、２
番目のセル６０７を指し、２番目のセル６０７の下向き
ポインタは、最初のセル６０８を指す。また、追加位置
記憶手段１０５は、新しいセルを指すパケットを指す。

第６図（Ｃ）は、更に２つの画素６１１の座標が与えら
れたところを示している。新たに２つのセル６１２が、
第１の座標記憶手段１０２から割り当てられている。こ
れらのセルの間には、上下のポインタが張られている。

また、追加位置記憶手段ｍは、最後に追加したセルを指
すパケットを指している。

第７図は、与えられた画素が前の画素の横方向のもので
ある場合を示している。この画素７０３のＸ座標は、追
加位置記憶手段１０５の指すパケットのＸ座標と同じで
ある。そこで、このパケットが指し示すセルフ０１のＸ
座標と、新しいセルフ０２のＸ座標を比較する。この例
では、新しいセルフ０２のＸ座標の方が太きい。そこで
、この新しいセルフ０２は、セルフ０１の右側につなが
れる。そして、セルフ０１とセルフ０２の間に左右のポ
インタが張られる。即ち、セルフ０１右向きポインタは
セルフ０２を指し、セルフ０２の左向きポインタはセル
フ０１を指す。追加位置記憶手段１０５は、セルフ０１
を指す。

第８図は、一つの閉領域８０１を構成する画素の座標が
すべて与えられたところを示している。このように、各
セルの上下左右を指すポインタは、それぞれの対応する
画素の位置関係に合わせて、上下左右に位置するセルを
指す。

第９図は、１つの閉領域９０１を構成する画素の座標が
与えられた後、その内容に存在する他の閉領域９０２の
画素の座標が与えられた場合を示している。この場合も
最初に、第２の座標記憶手段１０３の１つのセル９０４
を確保する。このセルに９０４は、いま与えられた画素
９０３のＸ座標が書き込まれる。次に、追加位置記憶手
段１０５の指すセルまたはパケットを見る。このセルま
たはパケットのＸ座標が、新しく発生したセル９０４の
Ｘ座標と等しい場合は、新しいセル９０４は追加位置記
憶手段１０５の指すセルの左右方向のどこかに追加すれ
ばよい。そこで、この左右方向のセルのＸ座標を検査し
、新しいセル９０４のＸ座標が昇順の位置となる場所に
新しいセルを追加する。この場合は、第９図のようにポ
インタ９０５を一旦切り、新しいポインタ９０６をつな
ぐ。

また、追加位置記憶手段１０５の指すセルまたはパケッ
トのＸ座標と、新しい１ｍ１素９０３のＸ座標が異なる
場合は、追加位置記憶手段１０５は見ない。

この場合は、第１の座標記憶手段１０２の新しい画素９
０３のＸ座標に対応するパケットから、新しいセル９０
４を追加する位置を求める。

このようにして、一つの閉領域９０１の内部に存在する
他の閉領域９０３の画素の座標が次々と与えられるに従
って、それぞれの画素に対応するセルが、第２の画像記
憶手段１０３に作られていく。このようにして、第１０
　図の様な第１の座標記憶手段１０２、第２の座標記憶
手段１０３の構造が形成される。

このようにして第１、第２の座標記憶手段１０２゜１０
３の構成が決定すれば、内部の塗りつぶしは容易である
。即ち、Ｙｉ標を小さい方から順に増加させていく。こ
のＸ座標に対応する第１の座標記憶手段１０２のパケッ
トを見る。パケットに第２の座標記憶手段１０３へのポ
インタが記述されている場合は、それを見る。そして、
１番目と２番目、３番目と４番目というように、２つず
つセルを組にする。その後、これら２つのセルに対応す
る画素を結ぶ直組を描画すれば、閉領域の塗りつぶしは
完成する。

以上のような、画像の塗りつぶしでは、次のような間頭
が発生する。すなわち、この方式では、同じＸ座標を持
つＸ座標を先頭から２つずつ組にしてそのあいだを塗り
つぶす。この結果、第１１図（Ａ）の様に、１画素１１
０２だけ飛び出している図形の場合は、この画素に対応
するセルの隣に、別のセルが存在しないため、不具合が
発生する。

また、第１１図（Ｂ）、第１１図（Ｃ）の様に、水平方
向に、奇数個の画素がある場合も問題となる。

これらの問題に対する本発明の解決方法を述べる。

第２の座標記憶手段１０３に、セルを追加する際には、
追加位置記憶手段１０５の指すセルまたはバゲットのＹ
座標（画素１１０１に対応するセルを指している）と、
次の画素１１０３のＹ座標を比較する。そして、これら
のＹ座標が等しい場合は、この画素１１０２に対応する
セルは、第２の画像記憶手段１０３には、追加しない。

例えば、第１１図（Ｂ）においては、次のようにする。

現在の画素が、画素１１０５であるとする。

この際、追加位置記憶手段１０５の指すセルまたはパケ
ット（画素１１０４を指している）のＹ座標と、次の画
素１１０６のＹ座標が等しいので、現在の画素１１０５
に対応するセルは、第２の座標記憶手段１０３には追加
されない。現在の画素が、画素１１ｏ７になったとき初
めて、次の画素が画素１１０８になり、画素１１０６に
対応するセルは、第２の座標記憶手段１０３に追加され
る。このようにすることによシ、第１１図（Ａ）、（Ｂ
）、（Ｃ）の画素の内、斜線で示した画素に対応するセ
ルは、追加されない。

このように、本装置では、輪郭を構成する画素の座標生
成が終わると同時に、塗りつぶしを開始することが可能
であり、その効果は大きい。

なお、本実施例では、新しいセルを追加するとき、追加
位置記憶手段１０５を最初にみた。このようにすること
により、新しいセルの追加位置を早く知ることが可能で
ある。

しかし、新しいセルを追加する都度、第１の座標記憶手
段１０２を参照する。そして、新しいセルのＹ座標に対
応するパケットから、第２の座標記憶手段１０３をたぐ
る。そして、最後に、第２の座標記憶手段１０３内の新
しいセルを追加する位置を知る。このようにすれば、追
加位置記憶手段１０５は必要としない。このようにして
も、閉領域を構成する画素の座標を発生し終わったとき
すぐに、塗りつぶしを開始することが可能である。

発明の効果 本発明は以上のように、閉領域を構成する座標が与えら
れる度に、この閉領域を塗シっぷすためのデータ構造を
作成し、この結果、閉領域を構成する座標がすべて与え
られるのと同時に塗りつぶしの実行を実施するだめ、閉
領域の塗りつぶしをより高速に実行することができる。

【図面の簡単な説明】

第１図は本発明の一実施例における画像塗りつぶし装置
のブロック結線図、第２図〜第１１図、及び第１３図は
同装置の要部である第１１第２の座標記憶手段の記憶状
態を示す概念図、第１２図は同装置で用いるアウトライ
ンフォントを示す図、第１４図は従来の画像塗りつぶし
装置のブロック結線図、第１５図は同画像塗りつぶし装
置の動作を示す概念図である。 １０１・・・座標発生手段、１０２・・・第１の座標記
憶手段、１０３・・・第２の座標記憶手段、１０４・・
・自由領域指示手段、１０５・・・追加位置記憶手段、
１０６・・・直線描画手段、１０７・・・画像記憶手段
、１０８・・・プロセッサ、１０９・・・バス。 第１図 代理人の氏名　弁理士　粟　野　重　孝　ほか１名第 図 Ｕ１第２０癌硯記憔鍛 第５図 （△） Ｘ。 （Ｂ） 第２０Ｑ座標記惰チ没 第 図 ヒＪし 第 図 １０２第１の昆標記憔引変 第６図 （八） 第 図 第 図 εδ１閉頼城 ：ｔｏｓｍｖｍａａ＝己１号役 第 図 １０ｊ見２の／笠４朕６已′導テ将七 第 図 第 図 第 図 （Ａ） 第 図 第 図 （Ｂ）

Claims (2)

【特許請求の範囲】
1. （１）閉領域を構成する画素の２次元座標のうち一方の
   座標値のそれぞれに対応した小領域を持つ第１の座標記
   憶手段と、前記第１の座標記憶手段の小領域によって指
   示された小領域を持ちこの小領域内に２次元座標の他の
   一方の座標値を記憶する第２の座標記憶手段と、前記第
   ２の座標記憶手段のうち使用されていない領域を示す自
   由領域指示手段と、前記第２の座標記憶手段の小領域に
   よって示された座標間に直線を描画する直線描画手段に
   より構成される画像塗りつぶし装置。
2. （２）閉領域を構成する画素の２次元座標のうち一方の
   座標値のそれぞれに対応した小領域を持つ第１の座標記
   憶手段と、前記第１の座標記憶手段の小領域によって指
   示された小領域を持ちこの小領域内に２次元座標の他の
   一方の座標値を記憶する第２の座標記憶手段と、第２の
   座標記憶手段の小領域の１つを指示する追加位置記憶手
   段と、前記第２の座標記憶手段のうち使用されていない
   領域を示す自由領域指示手段と、前記第２の座標記憶手
   段の小領域によって示された座標間に直線を描画する直
   線描画手段により構成される画像塗りつぶし装置。