JPH02208784A - 画像生成方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はスキャンコンバージョンによる画像生成方法に
係り、特に本来の画素を分割した副画素をスキャン単位
とし、かつ輪郭線内部の塗り潰しに階調のある画素を用
いたスキャンコンバージョンによる画像生成方法に関す
る。

〔従来の技術と発明が解決しようとする課題〕階調のあ
る画素を利用して画像の品質を向上させる手法はアンチ
・エイリアシング（ａｎｔｉ−ａｌｉａ−ｓｉ口ｇ）手
法として知られ、これにはポスト・フィルタリング（ｐ
ｏｓｔ−ｆｉｌｔａｒｉｎｇ）とブリ・フィルタリング
（ｐｒｅ−ｆｉｌｔｅｒｉｎｇ）の基本的な手法がある
。

ブリ・フィルタリングは一種のデジタル・ローパスフィ
ルタにより、生成した画像の不要成分をカットしてから
表示する手法である。この手法では、デジタルフィルタ
をフーリエ変換を利用して作成するが、その計算量が非
常に大きく長い時間がかかってしまい、任意の輪郭線に
囲まれた領域の塗り潰しに適用することは難しい。

他方、ポスト・フィルタリングは、画像出方装置の本来
の画素（物理的な画素）を仮想的な小さな画素（副画素
）に分割することにより１本来の解像度より高解像度で
画像を作り、階調を利用して目的の解像度に落とす手法
である。この手法は、原理的にはブリ・フィルタリング
より劣るが、スキャンコンバージ蕊ン法と組合わせるこ
とにより、任意の輪郭線で囲まれた部分も塗ることがで
きるという利点がある。

従来、このようなポスト・フィルタリング手法を適用し
たスキャンコンバージ１ンによって画像を生成する場合
、副画素をビットに対応させ１本来の画素分の副画素の
塊で処理し、各塊の中の“１”のビットを数えて最終的
に出力する画素の階調を求めるため、ビット単位の演算
が多く、これが処理の高速化を難しくしている。

本発明の目的は、このような問題点を解消できる両像生
成処理方法を提供することにある。

〔課題を解決するための手段〕

本発明は、上記目的を達成するため１本来の画素を分割
した副画素をスキャン単位とし、２次元の輪郭線の内部
の塗り潰しに階調のある画素を用いたスキャンコンバー
ジョンにおいて、輪郭線の線分の座標等の数値を１語中
に小数点を置いた仮想的な実数で表現し、かつ処理する
ことを特徴とする。

〔作　用］ このように線分の座標等の数値を仮想的な実数として扱
うため、実施例で詳細に説明するように、スキャンコン
バージョンにおける大部分の演算を効率的な整数演算に
よって行うことが可能となり、処理を高速化することが
できるとともに、処理時間の増加を招くことなく座標値
等を実数値に拡張でき自由度が増す。

〔実施例〕

以下、図面を用い、本発明の一実施例を説明する。

本発明の一実施例に係る画像生成装置は、第１図に示す
ように、行記憶装置１、スキャン行演算装！！２．スキ
ャン行記憶装置３、表示行演算装置４、表示行階調記憶
装置５．輝度演算装置６．および各演算装置による処理
の順序制御を行う順序制御装置より構成される。この装
置は、行記憶装Ｗｉｌ内のデータにより表現された２次
元の輪郭線（多角形）の内部を、副画素単位でスキャン
コンバートして階調のある画素で塗り潰し１表示行階調
記憶装置５に物理的な画素毎の階調データを得、この階
調データより輝度演算装置６で実際の輝度を演算してデ
イスプレィ装置（画像出力装置）へ出力するというもの
である。この処理の概略を第２図に示す。

次に第３図に示すような輪郭線の内部を塗り潰した画像
を生成する場合を例として、処理内容を詳細に説明する
。なお、第４図は第３図中の破線で囲まれた部分の拡大
図である。

スキャンコンバージョンは、スキャン行という仮想的な
行を移動し、スキャン行と輪郭線との交点を求め、輪郭
線の内側と判断した区域を塗り潰す手法であるが、ここ
では、スキャン行を上から下へ（Ｘ座標が増大する方向
へ）移動させるものとする（逆方向へ移動させてもよい
）。

例に挙げた輪郭線を構成する線分はすべて直線であるが
、スキャン行を移動した時に次の点を求め得るならば曲
線でも構わない、また、輪郭線の全線分は始点と終点の
座標が整数値となっているが、整数値に限られない０輪
郭線の線分はすべてＸ座標が小さい方の端点を始点、他
の端点を終点とした向きのものとするが、逆にしてもよ
い（ただし、全線分を同じ向きにする）。

このような輪郭線の線分のデータは、始点のＸ座標が小
さい順にソートされて行記憶装置１に格納される。この
線分のデータとしては、始点のＸ座標、終点までの高さ
、始点のＸ座標、スキャン行が副画素の高さ分移動した
ときのＸ座標の増分（または減分）が少なくとも含まれ
る。

ここでは、１６階調の出力が可能なデイスプレィ装置ｉ
！（画像出力装ｍｌ）を仮定しているので、デイスプレ
ィ装置における本来の画素（物理的な画素）を４×４の
副画素に分割する。−船釣には画像出力装置の階調がＮ
の場合、ｒ（Ｎ」　（％／’Ｎを下回らない最小の整数
）をｎとすると、物理的な１画素をｎＸｎの副画素に分
割すればよい。

このような副画素がスキャン行の移動単位（スキャン単
位）となる、すなわち、物理的な１行が仮想的にｎ本の
行としてスキャンされる（第４図参照）。

ここでは、ｎ＝４であるから、第３図に示した輪郭線を
構成する線分■、・・・、■は行記憶装置１に第５図の
ように格納される。

行記憶装置ｉ！１内の線分の各データは、従来は整数ま
たは浮動小数点の型式で表現されたが、ここでは、第７
図に示すように、１語中の中間に仮想的な小数点を置き
、小数点の左側を整数部、右側を小数部とした仮想的な
実数として、線分の座標値等のデータが表現され、また
処理される１語の左端ビットは符号ビットとし、負の数
は整数と同じ２の補数で表現する。スキャン行記憶装置
３内のデータも同一表現である。

なお、ここでは小数点の語の中間に置いたが、−船釣に
は整数部がｌｏｇｉ　Ｎビット以上となる位置に小数点
を置けばよい（Ｎデイスプレィ装置の階調）。

このような数値の表現形式にすると、加減算は通常の整
数演算で可能であり、浮動小数点演算に比較して演算時
間を短縮でき、座標値を整数に限定した場合と比べても
演算時間は増加しない０乗除算は整数演算より時間がか
かるが、浮動小数点より演算時間が短かくなる。ただし
、このような乗除算の回数は加減算に比べ非常に少ない
ため、その時間を無視してよい、したがって、本発明に
よれば、演算時間を増加させずに、座標値を実数値に拡
張できる。

このような輪郭線のデータが行記憶装置１に格納された
とし、処理を順に説明する。

まず、スキャン行演算装置２においてスキャン行のＸ座
標を初期設定し、また表示行演算装置４において表示行
階調記憶装置５をクリアする（第２図の処理１．２）。

次にスキャン行演算装置２は、始点のＸ座標が現在のス
キャン行のＸ座標と等しいすべての線分の高さ、Ｘ座標
、増分のデータを行記憶装置１よリスキャン行記憶装置
３へ移し、スキャン行記憶装置３内のデータをＸ座標が
小さい順に並べ換える（第２図の処理３．４）。

第３図の輪郭線の場合、現在のスキャン行のＸ座標がｌ
Ｏであるとすると、スキャン行記憶装置３の記憶内容は
第６図（ａ）のようになる。

このような内容のスキャン行記憶装置３のＸ座標のデー
タをスキャン行演算装置１２で調べ、現在のスキャン行
における塗り潰し区間の開始点と終了点のＸ座標を調べ
（処理６）１表示行演算装置４で塗り潰し区間の塗り潰
しの処理を表示行階調記憶装置１５に対して行い（処理
４から処理１０）、この処理を完了すると（処理５で判
定）、スキャン行演算装置２でスキャン行のＸ座標を副
画素の高さ（ここでは０．２５）だけ増加させる、すな
わち副画素単位でスキヤン行を移動させる（処理１１）
、そして、スキャン行演算装置１２でスキャン行記憶装
［３に記憶されている高さのデータを０．２５だけ減ら
し、　Ｘ座標のデータに増分を加え、また高さのデータ
がＯとなった線分のデータをスキャン行記憶装置３より
削除する（処理１２゜１３）、スキャン行が物理的な行
の境界まで移動すると、スキャン行演算装置ｉ１１！２
で現在のスキャン行と始点のＸ座標が一致する線分のデ
ータを行記憶装置ｌｌよりスキャン行記憶装置３へ移し
、スキャン行記憶装［３内の線分のデータをＸ座標値が
小さい順にソートする（処理３．４）。

したがって、スキャン行のＸ座標が１１まで増加すると
スキャン行記憶装置３の内容は第６図（ｂ）のようにな
る、スキャン行のＸ座標が１２まで増加すると、スキャ
ン行記憶装置３の内容は第６図（ｏ）のようになり、高
さのデータが０となった線分（第３図の■、■）のデー
タがスキャン行記憶装［３より削除された後、線分゛（
第３図の■、■）のデータがスキャン行記憶装置３に追
加され、ソートされることにより、スキャン行記憶装置
Ｅ３の内容は第６図（ｄ）のようになる。

処理６における塗り潰しの区間の検出は、スキャン行記
憶装置３内のＸ座標を記憶順に調べることによって行う
１例えば、ｙ＝１のスキャン行においては、第６図（ｂ
）より明らかなように、Ｘ；１１の点からｘ＝１２．６
の点までの区間と。

ｘ＝１９の点からｘ＝２０．６の点までの区間とを塗り
潰せばよいことが分かる。

このような区間の塗り潰しは１表示行階調記憶装置５内
の対応する記憶値に必要な値を足すことによって行ねれ
る。したがって、スキャン行が移動するにつれて１表示
行階調記憶装置５の内容は順次変化することになる。第
４図に示した輪郭線の場合、表示行階調記憶装置５の記
憶内容はスキャン行の移動により第８図に示すように順
次変化する。

さて、第４図から明らかなように、ｙ＝＝１ｏ。

２５のスキャン行においては、ｘ；１１の画素の１個の
副画素およびｘ＝１２の画素の１個の副画素を塗るべき
であるので、第８図（ｂ）に示すように、表示行階調記
憶装置！５におけるｘ＝１１とｘ＝１２に対応する位置
の記憶装置に１をそれぞれ足す、同様にｙ＝１０．５の
スキャン行では。

ｘ＝１１の画素の２個の副画素とｘ＝１２の１個の副画
素を塗るべきであるので、第８図（ｃ）に示すよう−に
、表示行階調記憶装置５のｘ＝１１に対応した位置の記
憶値に２を足し、ｘ＝１２に対応した位置の記憶値に１
を足す。

このような足す数とそれを足す位置は、スキャン行記憶
装置３内のＸ座標値が前述のように語中に仮想の小数点
を置いた仮想の実数データとして表現されているため、
次のように簡単に求めることができる。

物理的な画素のＸ方向およびｙ方向の分割数ｎを前述の
ように２のべき乗にすると（ここではｎ＝４）、表示行
階調記憶装［５の数を足す位置はＸ座標データの整数部
より分かる０足す数は、Ｘ座標データの小数点から右の
ｌｏｇ、　ｎビット（ここではｎ＝４であるから２ビツ
ト）より分かる。

例えば、第４図の輪郭線の場合、ｙ＝１０．２５のスキ
ャン行では、塗り始めの点のＸ座標は１１．７５、塗り
終りの点のＸ座標は１２．１８７５であり（これは処理
１６で検出される）、これらのデータの語は第９図の（
ａ）と（ｂ）のようになっている０表示行階調記憶装置
５における塗り潰しの開始位置は、第９図（ａ）に示し
た語の整数部が１１（１０進）であるからｘ＝１１の位
置となり、そこに足す数は、小数点の右２ビツトが３（
１０進）であるのでＬ　（＝ｎ−３）である（ここでは
ｎ＝４）、また、表示行階調記憶装置５における塗り潰
しの終了位置は、第９図（ｂ）に示した語の整数部が１
２（１０進）であるのでｘ＝１２の位置であり、足す数
は小数点の右２ビツトが０（１０進）であるので１であ
る。

以上説明した表示行階調記憶装置５上の塗り潰しの開始
位置と終了位置を求める処理が第２図の処理７である。

また、足す数を求めて表示行階調記憶装［５の該当デー
タに足す処理が第２図の処理８から処理１０である。

ここで、ｘｔｆｌｌｌデータの小数点から右側のｌｏｇ
。

ｎビットをＭ（Ｘ座標）午μし、整数部をＩ　（Ｘ座標
）と表す、また、表示行階調記憶装置５の対応する位置
をＬ　［ｉ］と表現する。

処理８で工（開始座標）と工（終了座標）が比較され、
等しいときには処理９へ、等しくないときには処理１０
が実行される。

処理９においては、Ｌ［Ｉ（開始座標）〕の位置の記憶
値に、Ｍ（終了座標）　−Ｍ　（開始座標）を足°す。

処理１０においては、 ａ）Ｌ（Ｉ（開始座標）］の位置の記憶値にｎ−Ｍ（開
始座標）を足す。

ｂ）　　Ｌ［Ｉ（［始座ｍ）＜ｉ＜Ｉ（終了座１１）〕
の各位置に記憶値に、それぞれｎを足す。

ｃ）Ｌ［Ｉ（終了座標）］の位置の記憶値にＭ（終了座
標）＋１を足す。

なお、Ｘ座標データよりＭ（Ｘ座標）とＩ　（Ｘ座標）
を取り出す操作は簡単な演算であり、それに要する時間
はわずかである。

さて、１本の物理的な行に対する以上の処理が済み、ス
キャン行のｙ座標が物理的な行の境界を越えると（これ
は処理１４で判定）、輝度演算装置１ｉ６は表示行階調
記憶装置５内のデータより当該行の各画素の輝度Ｂを次
式によって算出しデイスプレィ装置（画像出力装置）へ
出力する（処理１５）。

ｎ＝−（ＩＸＮ＋　　（Ａ−Ｉ）ＸＣ）／Ａここで、Ｉ
は表示行階調記憶装ｗ５の対応する記憶値、Ａ　＝　ｎ
　Ｘ　ｎ　、　Ｎはデイスプレィ装置（画像出力装Ｗ１
）の階調、Ｃはデイスプレィ装置に出力済みの当該画素
の階調である。

この演算も整数演算であるから、高速に実行できる。

なお、中間調で塗りたい場合、Ｎの値を変更すればよい
、また、カラー画像の場合、Ｒ（赤）Ｇ（緑）−Ｂ（青
）、Ｃ（シアン）・Ｍ（マゼンタ）・Ｙ（黄）、または
Ｃ−Ｍ−Ｙ−Ｋ　（黒）等の各色について同様の処理に
よって輝度を求めればよい。

ここまではスキャン行をｙ方向へ移動させたが、Ｘ方向
へ移動させてもよい。この場合、以上の説明中のｘ、ｙ
を入れ替えた内容となる。

また、第１図に示した各記憶装置および各演算装置はそ
れぞれ物理的には一つの装置であってもよい。

〔発明の効果〕

以上説明したように、本発明によれば、塗り潰し区間の
決定および階調算出のための演算を効率のよい整数演算
によって行うことができるので、従来よりも高速な画素
生成処理が可能である。

【図面の簡単な説明】

第１図は本発明の一実施例に係る画像生成装置の概略ブ
ロック図、第２図は処理の概略フローチャート、第３図
は輪郭線の例を示す図、第４図は第３図の破線で囲まれ
た部分の拡大図、第５図は行記憶装置の記憶内容を示す
図、第６図はスキャン行記憶装置の記憶内容とその変化
の様子を示す図、第７図はＸ座標等の数値の表現形式を
示す図、第８図は表示行階調記憶装置の記憶内容とその
変化の様子を示す図、第９図はＸ座標データ例を示す図
である。 １・・・行記憶装置、　２・・・スキャン行演算装置、
３・・・スキャン行記憶装置。 ４・・・表示行演算装置、 ５・・・表示行階調記憶装置、　６・・・輝度演算装置
、７・・・順序制御装置。 第５ 図 第７ 図 区０００１００００００コχ工１０．５１１１１ＱＩＱ
＋１００００ｆ口て＝−１０，５第０図 （ｂン （リ 一１〕タヒｊ→キト、イＪ【１２ （ｄ） ｊ九林値１２ （す

Claims (1)

【特許請求の範囲】
1. （１）本来の画素を分割した副画素をスキャン単位とし
   、２次元の輪郭線の内部の塗り潰しに階調のある画素を
   用いたスキャンコンバージヨンによって画像を生成する
   方法において、輪郭線を構成する線分の座標等の数値を
   、語中に小数点を置いた仮想的な実数で表現し処理する
   ことを特徴とする画像生成方法。