JPH0573693A

JPH0573693A - 輪郭塗り潰し方式

Info

Publication number: JPH0573693A
Application number: JP3236663A
Authority: JP
Inventors: Tomohiro Fukuoka; 智博福岡; Masayuki Okamoto; 雅之岡本
Original assignee: Fujitsu VLSI Ltd; Fujitsu Ltd
Current assignee: Fujitsu VLSI Ltd; Fujitsu Ltd
Priority date: 1991-09-17
Filing date: 1991-09-17
Publication date: 1993-03-26

Abstract

(57)【要約】【目的】本発明は輪郭塗り潰し方式に関し、ハードウ
ェア化が容易で、処理時間が短かく高速の塗り潰しが可
能なことを目的とする。【構成】画像生成領域１０内の全ての走査線を自然数
ｎドット毎の区間に等分割し、輪郭生成時に輪郭の変化
から画素の反転を開始する判別点を抽出したとき、各走
査線上の判別点が属するｎドットの区間だけで判別点以
降の画素を反転し、輪郭生成終了後、画像生成領域１０
全体を走査して、分割されたｎドットの区間毎に先行す
る区間の最後の画素が反転しているときに反転を行なっ
て輪郭内部を塗り潰す。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、図形描画、及びパター
ン生成等に用いられ、対象物の輪郭線から、対象物の内
部又は外部を塗り潰した画像を生成する処理を行う輪郭
塗り潰し方式に関する。

【０００２】近年、美しい文書が机上で手軽に得られる
ＤＴＰ（デスクトップパブリッシング）等の普及と、そ
れに伴うプリンタ、ディスプレイ等の出力装置の解像度
向上によって、高速な塗り潰しは必須の技術となってい
る。

【０００３】

【従来の技術】塗り潰しの方式としては様々なものが考
案されているが、従来は専用の塗り潰し装置によって塗
り潰しを実行するのではなく、ソフトウェアによって実
現されている場合が多い。

【０００４】これまで多くのシステムにおいて採用され
ていた塗り潰し方式として、スキャンラインコンバージ
ョンがある。この方式は予め全ての輪郭線をソーティン
グし、リストを作成し、作成されたソートリストの先頭
から順に図形の内外判定をして塗り潰すため、ソートリ
ストを作成するための領域が必要である。このソートリ
ストに割り当てられる領域は、輪郭線の構成要素数によ
って定まり、輪郭線が無限にある場合には無限の領域を
必要とするため、ハードウェア化には向いていなかっ
た。

【０００５】ハードウェア化に適した塗り潰し方式とし
てＥＶＥＮ／ＯＤＤルールがあげられる。この方式によ
れば、輪郭の構成要素数の影響を受ける事なく、高速な
塗り潰し装置を簡単に構成する事が出来る。

【０００６】

【発明が解決しようとする課題】従来のＥＶＥＮ／ＯＤ
Ｄを用いた塗り潰しでは、走査線の方向に１ドット幅の
図形を表現出来ないため、塗り潰しを行った画像に輪郭
線を上書きするという必要があった。これに対処するた
めに、画像生成領域の他に輪郭線を保存しておく領域を
設けるか、塗り潰し完了後に再度輪郭の描画を実行する
必要があった。また、ＥＶＥＮ／ＯＤＤルールを用いた
塗り潰し回路では、処理単位領域の先頭画素から最終画
素に向かって走査しながら順次対象物の内部であるか、
外部であるかを判断しながら画素を設定するため、処理
単位領域内の塗り潰しを実行するのに時間がかかる、と
いう問題があった。

【０００７】本発明は、上記の点に鑑みなされたもの
で、ハードウェア化が容易で、処理時間が短かく高速の
塗り潰しが可能な輪郭塗り潰し方式を提供することを目
的とする。

【０００８】

【課題を解決するための手段】図１（Ａ），（Ｂ）は本
発明の原理図を示す。

【０００９】図１（Ａ）において、輪郭線生成手段１１
は、輪郭情報に基づいて１画素ずつ輪郭線を生成する。

【００１０】反転画素指示手段１２は、生成された輪郭
線の変化から判別点を抽出し、判別点が属するｎドット
の区間を画像生成領域１０から選択し、選択したｎドッ
トの区間のｉ番目に判別点があるとき、ｉ番目以降の
（ｎ−ｉ＋１）個の画素の反転を指示する。

【００１１】第１の画素反転手段１３は、輪郭線生成時
に反転画素指示手段１２の反転指示に基づき画像生成領
域１０から選択したｎドットの区間を反転する。

【００１２】画素反転情報保持手段１４は、輪郭生成終
了後、画像生成領域１０を走査して得たあるｎドットの
区間の最後の画素を次のｎドットの区間の画素反転情報
として保持する。

【００１３】第２の画素反転手段１５は、輪郭生成終了
後、画像生成領域１０を走査して得られ画素反転情報保
持手段１４に保持された画素反転情報に基づきｎドット
の区間を反転する。

【００１４】図１（Ｂ）において、第３の画素反転手段
１６は、輪郭線生成時には反転画素指示手段１２の反転
指示に基づき、輪郭生成終了後は該画素反転情報保持手
段１４に保持された画素反転情報に基づき画素生成領域
１０のｎドットの区間を反転する。

【００１５】

【作用】本発明においては、輪郭を生成し、かつ、輪郭
を走査しながら画素の反転を行なうことで記憶容量が少
なくて済みハードウェア化を容易に行なうことができ、
また画像生成領域の各走査線をｎドットの区間に分割し
て各ｎドットの区間単位で塗り潰しを行なうため、無駄
な塗り潰しを繰り返すことがなく塗り潰しに要する時間
が短くて済む。

【００１６】

【実施例】図２は、本発明の一実施例のブロック図を示
す。

【００１７】本実施例において、画像生成領域は３２×
３２ドットのメモリを用いる。また、処理単位は８ビッ
ト（８画素）として、画像生成領域の横方向３２ドット
を８ドット毎に分けて処理を行なう。

【００１８】図２において、３１は入力された輪郭情報
から輪郭の生成を行う輪郭生成部であり、ＤＤＡ（ディ
ジタル微分解析器）等を用いて輪郭の生成を実行する。
判別点抽出部３２は生成された輪郭から判別点の抽出を
行う。マスクパターン発生部３３は抽出された判別点か
ら反転画素を指示するマスクパターンを生成する。３４
は画素の反転を行う反転処理部である。３５は画像生成
領域を走査する場合の走査アドレス発生を行う。３６は
画像生成領域となる画像メモリである。３７は画像メモ
リのアドレスを選択するセレクタである。

【００１９】以下に実施例の動作を説明する。

【００２０】輪郭生成部３１は輪郭情報（輪郭の頂点座
標）が入力されると、ＤＤＡにより直線補間を行なって
１画素づつ輪郭の生成を行なっていく。この時、生成さ
れた輪郭データは、輪郭の座標値（Ｘ，Ｙ）である。

【００２１】３２は生成された輪郭から判別点の抽出を
行う。

【００２２】輪郭点から判別点を決定し、判別点間を埋
めるソフト処理で輪郭内塗り潰しを行なう方式を本出願
人は先に特開昭６３−３０５４７８等で提案している。
この概要を図３で説明すると（ａ）は原図形であり、こ
の原図形の輪郭を抽出すると同図（ｂ）になる。この輪
郭図形の各画素（各ドット）を同図（ｃ）のように左廻
りに辿り、所定の論理でドットの発生／消去を行なうと
同図（ｄ）が得られる。この図の２重丸で示したドット
がここでは判別点と呼ぶものであり、横方向（塗り潰し
の際の走査方向）では各２つだけしかない。

【００２３】判別点の設定容量を下表に示す。この表で
は当該画素に判別点を設定しない、は当該画素に判
別点を設定する、は当該画素の右側に判別点を設定す
る、は当該画素、および、当該画素の右側の両方に判
別点を設定する、である。

【００２４】

【表１】

【００２５】参照する画素に対して、その１つ前の画素
からの移動方法を、先行する移動方向とし、参照する画
素に対して、その１つ後の画素への移動方向を、追従す
る移動方向とし、参照する画素に対して、どのように判
別点を設定すべきかが、その交差する処理となる。処理
としては、〜の４通りであり、判別点ｊ₁，ｊ₁₁，
……はこの表のルールで設定される。

【００２６】この図３（ｄ）で、走査とテレビスキャン
（左から右、上から下）として、最初の判別点で塗り潰
し開始（最初の判別点は塗り潰す）、次の判別点で塗り
潰し終了（次の判別点は塗り潰さない、塗り潰すのはそ
の１つ前まで）とすると、図３（ａ）の原図形が得られ
る。

【００２７】判別点が抽出されると、判別点抽出部３２
は、この判別点が属する処理単位（ワード）を画像メモ
リから選択するためのアドレスを発生する。判別点の座
標値（Ｘ，Ｙ）は夫々５ビットで表わされ、Ｙ座標を上
位５ビットとし、Ｘ座標の上位２ビットを下位２ビット
とする７ビットが上記選択のためのアドレスとしてセレ
クタ３７に供給される。

【００２８】例えば、判別点の座標値：（１４，２０）
であれば、Ｙ座標Ｘ座標 “１０１００” “０１１１０” であるため、アドレスは１０１０００１となる。アドレ
スが決定されると、対応する画像メモリ３６の内容（判
別点の属するワード）が読み出される。

【００２９】画像メモリ３６に入力されるアドレスは、
セレクタＳ１で３２によって発生されたアドレスと３５
によって発生されたアドレスから、どちらか一方を選択
して用いられる。この選択は輪郭線生成中であれば判別
点抽出部３２が示すアドレスを、輪郭生成中でない場合
には、走査アドレス発生部３５の示すアドレスを選択す
るものとする。

【００３０】また、判別点抽出部３２で得た判別点のＸ
座標の下位３ビットは、マスクパターン発生部３３に渡
される。マスクパターン発生部３３では受け取った値を
基に、ＰＬＡを用いて反転画素を指示する。マスクパタ
ーンを生成して反転処理部２４に渡す。マスクパターン
の生成ルールは図４に示す通りである。図４では黒丸が
値“１”で反転する画素、白丸が値“０”で反転しない
画素を示している。

【００３１】画像メモリ３６から読み取られた画像情報
３４に取り込まれて、マスクパターンに指示される画素
の反転が行われる。反転処理部３４は、図５，図６に示
す如き構成である。

【００３２】図５は輪郭描画実行中（ＤＲＡＷＩＮＧ）
中に用いられる第１の画素反転回路である。第１の画素
反転回路は、イクスクルーシブオア回路（ＸＯＲ）４０
₁〜４０〜_nが各ビット（画素）毎に割り当てられてお
り、各画素に対する反転指示として輪郭の変化から抽出
される判別点に応じて生成されたマスクパターンがＸＯ
Ｒ４０₁〜４０_nに入力される画像メモリ３６から読み
出された画素情報もそれぞれ対応するＸＯＲ４０₁〜４
０_nに入力されており、反転指示と各画素の情報との排
他的論理和をとる事で画素の反転を実行する。

【００３３】図６は輪郭抽出でないとき、つまり反転処
理中に用いられる第２の画素反転回路である。第２の画
素反転回路は、ＸＯＲが４２₁〜４２_nが各ビット（画
素）毎に割り当てられており、各画素に対する反転指示
として、前方画素の画素情報を保持している。ラッチ回
路４３の出力がＸＯＲに入力される。画像メモリ３６か
ら読み出された画素情報もそれぞれ対応するＸＯＲ４２
₁〜４２_nに入力されており、反転指示との排他的論理
和をとる事で、画素の反転が行われる。また、画素反転
情報を保持するラッチ回路４３には最終画素の画素情報
（ＬＳＢ側のＸＯＲ４２_nの出力）が保持される。

【００３４】また、反転処理部３４は図７に示す如く単
一の第３の画素反転回路で構成する事も出来る。

【００３５】この場合の画素反転回路は、ＸＯＲが４５
₁〜４５_nの各ビット（画素）毎に割り当てられてお
り、各画素に対する反転指示として、セレクタ４６によ
りマスクパターン発生部３３で発生されたマスクパター
ンと画素反転情報として前方画素の画素情報を保持して
いる。ラッチ回路４７の出力から一方を選択したもの
が、対応するＸＯＲ４５₁〜４５_nに入力される。セレ
クタ４６は、輪郭描画実行中（ＤＲＡＷＩＮＧ）にはマ
スクパターンを、そうでなければラッチ回路４７の出力
を反転指示として選択する。画像メモリ３６から読み出
された画像情報もそれぞれ対応するＸＯＲ４５₁〜４５
_nに入力されており、反転指示との排他的論理和をとる
事で、画素の反転が行われる。また、画素反転情報を保
持するラッチ回路４７には最終画素の画素情報（ＬＳＢ
側のＸＯＲ４５_nの出力）が保持される。

【００３６】図８（Ａ），（Ｂ），（Ｃ）夫々は輪郭描
画実行中におけるマスクパターン、画像メモリ出力、反
転された画素パターン夫々を示す。

【００３７】ここで、図９に黒丸で示す如き画像の輪郭
情報が与えられた場合、点ａを開始点として時計回りに
処理を進行させ、図１０に二重丸で示す判別点を抽出す
る。開始点ａよりｂ点まで輪郭生成が進行したとき図１
１に示す状態となる。

【００３８】輪郭の生成が点ｂまで進行すると、図１０
における判別点ｆが抽出される。判別点ｆの座標値は、
（１１，６）であるから、判別点の属するワードを選択
するアドレス（００１１００１）が決定され、判別点ｆ
を含むワードの内容が画像メモリ３６より読み出され
る。読み出された画像情報は図１５（Ａ）である。

【００３９】Ｘ座標下位３ビットにより図１５（Ｂ）に
示すマスクパターンが生成される。マスクパターンによ
り示される画素の反転が実行され、図１５（Ｃ）に示す
画像が再び画像メモリ３６に書き込まれる。

【００４０】次に、輪郭線の生成が座標ｃまで進行した
場合の処理を説明する。

【００４１】輪郭の生成がｃまで進行すると、図１１に
おける判別点ｇが抽出される。判別点ｇの座標値は、
（１４，６）であるから、判別点の属するワードを選択
するアドレス（００１１００１）が決定される。これ
は、座標ｆを含むワードと同一ワードである事から画像
メモリ３６から読み出された図１６（Ａ）に示す画像
は、先程反転処理を実行した図１５（Ｃ）に示す結果と
同一である。

【００４２】Ｘ座標下位３ビットにより図１６（Ｂ）に
示すマスクパターンが生成される。マスクパターンによ
り示される画素の反転が実行され、図１６（Ｃ）に示す
画像が再び画像メモリ３６に書き込まれる。

【００４３】この後、輪郭生成が点ｄまで進行したとき
の画像は図１２に示す状態となり、輪郭生成が点ｅまで
進行したときの画像は図１３に示す状態となり、輪郭生
成が終了した時点での画像は図１４に示す状態となる。

【００４４】輪郭線の生成が終了した後に、画像領域全
体を走査しながら画像メモリ３６から読み出された画素
の反転を行う。輪郭の描画は終了しているので、画像メ
モリ３６に対するアドレスとしては、図２の走査アドレ
ス発生部３５が示すものが用いられる。また、反転処理
部３４においては、ラッチ回路４３又は４７に保持され
ている画素反転情報を反転指示として用いて、画素反転
が行われる。

【００４５】１つの走査線の先頭ワードを処理する場
合、画素反転情報が初期化される。画像領域の走査を実
行するために、走査アドレス発生部３５は走査線にそっ
て順にアドレスを発生して行き、読み出された画像メモ
リ３６の内容に対して、画素反転情報に従った反転処理
を行う。ここで反転処理された結果が、塗り潰し終了後
の画素情報となる。塗り潰しが終了したワードは、再び
画像メモリ３６に書き込まれるか、又は塗り潰し装置の
出力として外部より読み出される。

【００４６】１ワードの処理が終了した時点で、終了し
たワードの最終画素（ＬＳＢ側）の画素情報を、新たな
画素反転情報としてラッチ回路４３又は４７に保持す
る。ただし、先に述べた様に、走査線の先頭ワードを処
理する場合にはラッチ回路４３又は４７を初期化して
おく必要がある。以上の処理を画像領域全体に対して施
す事で、最終的な画像を得ることが出来る。

【００４７】図１４のＺ−Ｚで示した走査線に対する処
理を以下に説明する。（１）走査線の先頭ワードの処理をするため、ラッチ回
路４３を初期化する。（２）図１７（Ａ）に示す如く走査アドレス（００１１
１００）が発生され、対応する画像メモリ３６の内容が
読み出される。（３）画素反転情報に従って反転処理が行われる。この
場合、画素反転情報は初期化されているので、全ての画
素は反転されない。（４）最終画素の画素情報‘０’を画素反転情報として
ラッチ回路４３にラッチする。（５）図１７（Ｂ）に示す如く走査アドレス（００１１
１０１）が発生され、対応する画像メモリ３６の内容が
読み出される。（６）画素反転情報に従って反転処理が行われる。この
場合、画素反転情報は‘０’であるので全ての画素は反
転されない。（７）最終画素の画素情報‘０’を、画素反転情報とし
てラッチ回路４３にラッチする。（８）図１７（Ｃ）に示す如く走査アドレス（００１１
１１０）が発生され、対応する画像メモリ３６の内容が
読み出される。（９）画素反転情報に従って反転処理が行われる。この
場合、画素反転情報は‘０’であるので全ての画素は反
転されない。（１０）最終画素の画素情報‘１’を、画素反転情報と
してラッチ回路４３にラッチする。（１１）図１７（Ｄ）に示す如く、走査アドレス（００
１１１１１）が発生され、対応する画像メモリ３６の内
容が読み出される。（１２）画素反転情報に従って反転処理が行われる。こ
の場合、画素反転情報は‘１’であるので全ての画素は
反転される。（１３）１つの走査線の処理を終了したので、次の走査
線に対する処理を行うためにラッチ回路４３を初期化す
る。

【００４８】以上の様に構成した回路を用いる事で、輪
郭内部を塗り潰した画像を得る事が出来る。図１８は、
塗り潰しが完了した図形である。

【００４９】このように、輪郭を生成し、かつ、輪部を
走査しながら画素の反転を行なうことで記憶容量が少な
くて済みハードウェア化を容易に行なうことができ、画
素の反転処理のみで塗り潰しが実行可能であり、回路規
模の縮小に効果がある。また画像生成領域の各走査線を
ｎドットの区間に分割して各ｎドットの区間単位で塗り
潰しを行なうため、従来の塗り潰し回路の様に、ワード
内先頭画素から最終画素までをスキャンしながら塗り潰
しを行う必要がないため、無駄な塗り潰しを繰り返すこ
とがなく塗り潰しに要する時間が短かくて済み、高速処
理が実現できる。

【００５０】さらに、判別点の抽出を行う事で、走査方
向に１ドット幅の図形を表現する事が可能で、塗り潰し
を行った画像に輪郭線を上書きする必要がない。

【００５１】

【発明の効果】上述の如く、本発明の輪郭塗り潰し方式
によればハードウェア化が容易で、処理時間が短かく高
速の塗り潰しが可能となり、実用上きわめて有用であ
る。

【図面の簡単な説明】

【図１】本発明の原理図である。

【図２】本発明方式の一実施例のブロック図である。

【図３】判別点を説明するための図である。

【図４】マスクパターン発生ルールを示す図である。

【図５】第１の反転処理部の構成図である。

【図６】第２の反転処理部の構成図である。

【図７】反転処理部の変形例の構成図である。

【図８】画素反転を説明するための図である。

【図９】輪郭線を示す図である。

【図１０】判別点を示す図である。

【図１１】本発明方式を説明するための図である。

【図１２】本発明方式を説明するための図である。

【図１３】本発明方式を説明するための図である。

【図１４】本発明方式を説明するための図である。

【図１５】判別点ｆ抽出時の反転処理を示す図である。

【図１６】判別点ｇ抽出時の反転処理を示す図である。

【図１７】画像領域走査を説明するための図である。

【図１８】塗り潰し画像を示す図である。

【符号の説明】

１０画像生成領域１１輪郭線生成手段１２反転画素指示手段１３第１の画素反転手段１４画素反転情報保持手段１５第２の画素反転手段１６第３の画素反転手段

Claims

【特許請求の範囲】

【請求項１】輪郭情報に基づいて画像生成領域に描画
される輪郭線の内部を塗り潰す輪郭塗り潰し方式であっ
て、該画像生成領域内の全ての走査線を自然数ｎドット毎の
区間に等分割し、輪郭生成時に輪郭の変化から画素の反転を開始する判別
点を抽出したとき、各走査線上の該判別点が属するｎド
ットの区間だけで該判別点以降の画素を反転し、輪郭生成終了後、該画像生成領域全体を走査して、分割
されたｎドットの区間毎に先行する区間の最後の画素が
反転しているときに反転を行なって輪郭内部を塗り潰す
ことを特徴とする輪郭塗り潰し方式。
【請求項２】請求項１記載の輪郭塗り潰し方式におい
て、輪郭情報に基づいて１画素ずつ輪郭線を生成する輪郭線
生成手段（１１）と、生成された輪郭線の変化から判別
点を抽出し、該判別点が属するｎドットの区間を画像生
成領域（１０）から選択し、選択したｎドットの区間の
ｉ番目に判別点があるとき、ｉ番目以降の（ｎ−ｉ＋
１）個の画素の反転を指示する反転画素指示手段（１
２）と、輪郭線生成時に該反転画素指示手段の反転指示に基づき
該画像生成領域（１０）から選択したｎドットの区間を
反転する第１の画素反転手段（１３）と、輪郭生成終了後、該画像生成領域を走査して得たあるｎ
ドットの区間の最後の画素を次のｎドットの区間の画素
反転情報として保持する画素反転情報保持手段（１４）
と、輪郭生成終了後、該画像生成領域を走査して前方の区間
の最終画素より得られ該画素反転情報保持手段に保持さ
れた画素反転情報に基づきｎドットの区間を反転する第
２の画素反転手段（１５）とを有することを特徴とする
請求項１記載の輪郭塗り潰し方式。
【請求項３】請求項１記載の輪郭塗り潰し方式におい
て、輪郭情報に基づいて１画素ずつ輪郭線を生成する輪郭線
生成手段（１１）と、生成された輪郭線の変化から判別点を抽出し、該判別点
が属するｎドットの区間を画像生成領域（１０）から選
択し、選択したｎドットの区間のｉ番目に判別点がある
とき、ｉ番目以降の（ｎ−ｉ＋１）個の画素の反転を指
示する反転画素指示手段（１２）と、輪郭生成終了後、該画像生成領域を走査して得たあるｎ
ドットの区間の最後の画素を次のｎドットの区間の画素
反転情報として保持する画素反転情報保持手段（１４）
と、輪郭線生成時には該反転画素指示手段の反転指示に基づ
き、輪郭生成終了後は該画素反転情報保持手段に保持さ
れた画素反転情報に基づき該画素生成領域のｎドットの
区間を反転する第３の画素反転手段（１６）とを有する
ことを特徴とする請求項１記載の輪郭塗り潰し方式。