画像形成装置および方法
【課題】オブジェクトのレンダリングを高速に実行する。
【解決手段】グラフィックオブジェクトのレンダリングを実行する際には、着目グラフィックオブジェクトを読み（Ｓ８１２）、それをライン単位でレンダリングして、展開したラインのドットイメージデータを、フレームバッファの対応位置のドットイメージデータと、指定された演算により合成する（Ｓ８１４）。グラフィックオブジェクトのライン毎の展開は、まず先頭のラインであればライン全体のピクセルを書き出し（Ｓ８０３）、第２ライン以降であれば、注目ラインとその力全ラインとの間で相違する差分ピクセルについて、そのドットイメージデータを更新する。
【解決手段】グラフィックオブジェクトのレンダリングを実行する際には、着目グラフィックオブジェクトを読み（Ｓ８１２）、それをライン単位でレンダリングして、展開したラインのドットイメージデータを、フレームバッファの対応位置のドットイメージデータと、指定された演算により合成する（Ｓ８１４）。グラフィックオブジェクトのライン毎の展開は、まず先頭のラインであればライン全体のピクセルを書き出し（Ｓ８０３）、第２ライン以降であれば、注目ラインとその力全ラインとの間で相違する差分ピクセルについて、そのドットイメージデータを更新する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、たとえば高解像度画像等の画像特性を用いて画像形成処理を実行する画像形成装置及び画像形成方法ならびに画像形成方法を実行するプログラムに関するものである。
【背景技術】
【０００２】
従来、ページプリンタにてラスタライズ処理を実行するものとして、ペインターズ・アルゴリズム（Ｐａｉｎｔｅｒ'ｓ ａｌｏｇｏｒｉｔｈｍ）がある。ペインターズ・アルゴリズムは、描画するグラフィック・オブジェクト群の相互位置関係を予め調査し、最も奥に描画されるグラフィックス・オブジェクトからフレーム・ストアに描画する。
【０００３】
ペインターズ・アルゴリズムには２つの問題点がある。第１の問題点は、フレーム・ストア内の全ての画素へのランダムアクセスが発生する可能性があるため、予めアクセスされるフレーム・ストアの微小領域を特定することができないので、ラスタライズ処理の時間が、全てのグラフィックス・オブジェクトを構成する画素数と、フレーム・ストアが置かれるメモリの物理的な転送速度で決まる転送時間の積に制限されることである。第２の問題点は、グラフィックス・オブジェクト同士で重なりがある場合、奥のグラフィックス・オブジェクトはそれより手前のグラフィックス・オブジェクトで上塗りされるため、上塗りされた領域のラスタライズが時間的に無駄になることである。
【０００４】
ペインターズ・アルゴリズムのこの２つの問題を軽減するための一つの方法が、フレーム・ストアを帯状に分割し、グラフィックス・オブジェクトも予め帯状に分割するバンディングである。バンディングでは、予めアクセスされるメモリが、分断された帯状の領域（バンド領域）に限定されるので、例えばキャッシュ・メモリを装備することにより、フレーム・ストア全体にアクセスするのに比べて、キャッシュ・ヒットする確立を高めることが出来る。このために、全てのグラフィックス・オブジェクトを構成する画素数と、フレーム・ストアが置かれるメモリの物理的な転送速度で決まる転送時間の積に制限されることがなくなる。しかし、一般的にバンディングでは、フレーム・ストアを数個から数十個に分割するため、キャッシュ・ヒット率を劇的に改善するには至らない。また、やはり上書の問題は依然こうむる。
【０００５】
一方ペインターズ・アルゴリズムの問題であるオブジェクトの上書を発生させない方法（これを第２の方法と呼ぶ。）も考案されている。そのような方法の一例には、以下の手順でオブジェクトのレンダリングが行われる。フレーム・ストアに形成される画像はラスタ走査順で作られる。各ラスタラインと各オブジェクトの交点の座標が求められる。その交点座標の間の各画素について、当該ラインに含まれるグラフィクスオブジェクトのレベル（重なり合うグラフィックス・オブジェクトの奥行き方向の相互位置関係を示す情報）と、グラフィクスオブジェクトの色の情報とに基づいて、描画すべきオブジェクトが判定され、判定の結果決定されたオブジェクトに対応する色で交点間が描画される。これをライン毎にグラフィクスオブジェクトとの交点を更新しつつ行う（特開２０００−１３７８２５号公報参照）。
【特許文献１】特開２０００−１３７８２５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来の技術は高解像度の画像特性を生かしたものではない。すなわち、高解像度画像では、画像中の任意の画素とその近傍の画素とでは同じ色値になる可能性が高い（この性質を空間的局所性と呼ぶ）。これは画像に含まれるオブジェクトが一定の広がりを持っているためであり、高解像度になればひとつのオブジェクトを構成する画素数が増加するために、より空間的局所性が強く表れるためである。このため任意のフレーム・ストア中の任意のラインの任意の画素と、それに続くライン中の対応する画素（すなわちラインの端からの位置が同一の画素）は同じ色値をもつ可能性が高い。従来の方法では、ライン毎に独立した処理を行っているため、たとえ連続するラインで、色値に差分がある画素が小数、もしくはない場合でも、色値に差分のない画素に対しても前のラインで行った処理を繰り返す必要があり、時間的な無駄が発生していた。
【０００７】
また、上述したペインターズアルゴリズムではフレーム・ストアへのアクセスがランダムになり、第２の方法ではアクセスはシーケンシャルになる。フレーム・ストアへのアクセスがランダムな場合、従来の技術ではアクセスされる可能性がある画素がフレーム・ストア全体、もしくはバンド領域になるため、メモリキャッシュの効果は望めないか、あるいは効果は低い。一方、第２の方法では、描画前に重なり合うグラフィックス・オブジェクトの奥行き方向の相互位置関係から、フレーム・ストアに転送する色値を判定する必要がある。この判定処理は負荷が高く、また、フレーム・ストアの任意の画素は一度のみアクセスされるので、メモリキャッシュは本質的に意味をなさない。このためメモリキャッシュを有効的に利用することが出来ないという問題があった。
【０００８】
本発明は上記従来例に鑑みてなされたもので、オブジェクトで構成された画像を形成する際に、直前のラインにおいて対応する画素の値が同一の場合には当該画素を描画せずに直前のラインにおける画素値を用い、同一ではない画素について新たに画素値を生成することで、高速に画像形成処理を行う画像形成装置および方法を提供することを目的とする。
【０００９】
さらに、フレーム・ストアへのアクセスの局所性が顕著になり、キャッシュを有効的に利用でき、高速に画像形成処理を行う画像形成装置および方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述目的を達成するために本発明は以下の構成を有する。
【００１１】
フレームメモリにグラフィックスオブジェクトを描画する画像形成装置であって、
グラフィックスオブジェクトのスキャンラインごとのドットイメージデータを保存するラインメモリと、
前記ラインメモリに保存されたスキャンラインとその直後の着目スキャンラインにおいて対応する画素の値が異なる差分画素の位置を決定する決定手段と、
前記ラインメモリに保存されたドットイメージデータのうち、前記決定手段により決定された差分画素の値を、前記着目ラインにおける画素の値に更新する差分更新手段と、
前記ラインメモリのドットイメージデータを、前記着目スキャンラインに相当する前記フレームメモリの位置に合成する合成手段とを備える。
【発明の効果】
【００１２】
本発明によれば、グラフィクスオブジェクトで構成された画像をラスタライズする際に、直前のラインにおいて対応する画素の値が同一の場合には当該ピクセルを描画せずに直前のラインにおける画素値を用い、同一ではない画素について新たに画素値を生成することで、高速に画像形成処理を行うことができる。
【００１３】
さらに、グラフィクスオブジェクトのラスタライズの際に、ドットイメージデータを格納したメモリへのアクセスの局所性が顕著になり、キャッシュを有効的に利用でき、高速に画像形成処理を行うことができる。
【発明を実施するための最良の形態】
【００１４】
［実施形態１］
＜画像形成装置の構成＞
本発明の一実施形態について図を用いて説明する。図２は本実施形態にかかる画像形成装置としてのプリンタの構成を概略的に表す図である。図２のホストコンピュータ２０１は、プリンタドライバ２０２を備えている。プリンタコントローラ２０３は、Ｉ／Ｆ２０４と、解釈部２０５と、描画部２０６と、バッファ２０７と、転送部２０８と、記憶部２０９と、ビデオ転送部２１０と、画像処理部２１１と、論理演算部２１２を備え、プリンタエンジン２１３と一体となってプリンタを構成する。Ｉ／Ｆ２０４は、上記プリンタドライバ２０２と接続され、記憶部２０９は、Ｉ／Ｆ２０４と解釈部２０５と描画部２０６とＤＭＡ２０８とビデオ転送部２１０と画像処理部２１１と接続され、バッファ２０７は、描画部２０６と転送部２０８と接続され、転送部２０８は論理演算部２１２と接続され、また描画部２０６と論理演算部２１２と接続されている。図２のプリンタエンジン２１３は、上記ビデオ転送部２１０と接続されている。なお、解釈部２０５、描画部２０６、画像処理部２１１、論理演算部２１２は、プリンタコントローラ２０３の有するＣＰＵにより所定のプログラムを実行することで実現できる。
【００１５】
また、バッファ２０７には、本実施形態では、グラフィックオブジェクトをラスタライズする際に使用されるラインメモリ（ラインバッファ）が含まれる。記憶部２０９には、１ページ分のイメージデータを保存するためのフレームメモリ（フレームバッファ）とが含まれる。なお、フレームメモリは、バンディングを行う際には、バンド単位のイメージデータを格納するために使用され、複数のバンドに相当するメモリ領域が確保される、また、ページ単位でイメージデータを保持することもできる。ラインメモリとフレームメモリは別々のメモリデバイスとして提供されるのが望ましいが、同一のメモリに設けられても良い。
【００１６】
ホストコンピュータ２０１上では図示しない様々なアプリケーションソフトウェアが動作する。これらのアプリケーションは、印刷が指示されると、印刷するビットマップ画像を生成するに必要な情報をプリンタドライバ２０２に供給する。プリンタドライバ２０２では、受信した画像を形成するに必要な情報をプリントデータ、例えばＰＤＬデータに変換し、プリンタコントローラ２０３に備えられたＩ／Ｆ２０４に伝送する。
【００１７】
プリンタコントローラから伝送されたプリントデータは、記憶部２０９、例えばメモリ、に一旦保持される。解釈部２０５は、記憶部２０９に保持されたプリントデータの解釈を行い、描画部２０６が解釈可能な中間コードに変換し、この中間コードを再び記憶部２０９に格納する。中間コードの詳細は図３を参照して後述する。描画部２０５は、記憶部２０９に保持された中間コードを読み出し、図８Ａ〜８Ｃ等を参照して後述する方法で、最終的に紙面に出力するビットマップ画像（ドットイメージデータ）の一部を生成し、これをバッファ２０７に格納する。転送部２０８は、バッファに格納されビットマップ画像の一部を論理演算部２１２に伝送する。ここで注意すべきは、バッファ２０７に格納されたビットマップ画像の一部は、転送部２０８により転送されても、バッファ２０７の内容は保持されることである。論理演算部２１２は、伝送されたビットマップ画像の一部を、描画部２０６の指示に従い、必要に応じて記憶部２０９に格納されたビットマップ画像を参照して論理演算を行い、記憶部２０９にビットマップ画像を転送する。
【００１８】
上述の処理を繰り返すことによって、記憶部２０９に紙面一面分の画像が形成されると、画像処理部２１１は、記憶部２０８に格納された紙面一面分の画像（１ページ分の画像）に対して、例えばディザ処理等を行い、再び記憶部２０９に格納する。ビデオ転送部２１０は、記憶部２０９に蓄えられた紙面一面分の画像処理されたビットマップ画像を、プリンタエンジン２１２に伝送する。プリンタエンジン２１２は、伝送されたビットマップ画像に従いを記憶媒体、例えば紙、にプリントする。なお、本実施形態においてはバッファ２０７に形成されるビットマップは、１ピクセル（画素とも言う。）あたりそれぞれ８ビットのＲ、Ｇ、Ｂの色値から構成されるものとする。
【００１９】
＜中間コード＞
続いて解釈部２０５で生成される中間コードについて説明する。中間コードは少なくとも一つ以上のグラフィックス・オブジェクトを保持し、これらを複数持つことにより様々な図形が最終的に記憶媒体に出力されるビットマップを表現する。図３は解釈部２０５にて生成される中間コードに含まれるグラフィックス・オブジェクトのデータ構造の一例である。３０２は位置情報であり、グラフィックス・オブジェクトが描画されるビットマップ上での位置を表す。３０３はＡｒｅａ（エリア）情報であり、主にクリップ領域や単純矩形を表す。３０４はＭａｓｋ（マスク）情報であり、主にグラフィックス・オブジェクトの形状をあらわす。３０５はＢＧ（バックグラウンド）情報であり、主に塗りつぶしパターンを表す。３０６はＧｒａｙ（グレイ）情報であり、主に塗りつぶされる色やラスタ情報を表す。３０１は、Ａｒｅａ情報及びＭａｓｋ情報及びＢＧ情報及びＧｒａｙ情報等（これらをまとめて部らフィックスオブジェクトの要素情報と呼ぶ。）に基づいて描画されるグラフィックスオブジェクトと、グラフィックス・オブジェクトが描画されるディスティネーションとの論理演算を行うためのパラメータである。なおグラフィックス・オブジェクトの形状によっては、これら全ての要素情報が必要ない場合もあるが、その場合には、例えばグラフィックス・オブジェクトに含まれる情報を別に持つことで、必要ない情報をもたないようなデータ構造にしても良いし、必要ない情報についてはＮＵＬＬ値を持つようにしても良い。
【００２０】
図４は図３で説明したグラフィックス・オブジェクトの各要素情報の関係の一例を示す図である。グラフィックス・オブジェクトが紙面に描画される位置及び範囲は、位置情報３０２及びＡｒｅａ情報３０３で決定される。上述のように決定された位置及び範囲内で塗りつぶされる候補のピクセルはＭａｓｋ情報３０４で求まり、上述のように決定された塗りつぶされる候補のピクセルはＢＧ情報３０５によって塗りつぶされないピクセルがマスクされ、最終的に塗りつぶされるピクセルが決定する。上述のように決定された塗りつぶされるピクセルの色値は、Ｇｒａｙ情報３０６によって決定される。なお、図４ではＧｒａｙ情報が単色である場合を図示しているが、Ｇｒａｙ情報がラスタの場合（すなわち単色ではない場合）には、上述のように決定された最終的に塗りつぶされるピクセルに相当するＧｒａｙ情報３０６の色値をディスティネーションに書き込むことで、Ｇｒａｙ情報３０６がラスタの場合にも対応できる。なおこれら全てが必ず必要というわけではない。位置と範囲を定義するための位置情報３０２及びＡｒｅａ情報３０３と、色を定義するためのＧｒａｙ情報３０６またはＢＧ情報３０５だけでもグラフィックスオブジェクトを定義することができる。
【００２１】
図５は、図３の各情報が持ちうるデータの例を示した表であり、Ａｒｅａ情報は矩形もしくはトラペゾイド（台形）もしくはランレングスもしくは二値ビットマップとして表現され、Ｍａｓｋ情報は矩形もしくはトラペゾイドもしくはランレングスもしくは二値ビットマップとして表現し、ＢＧ情報はパターンもしくは単色もしくはイメージとして表現し、Ｇｒａｙ情報はパターンもしくは単色もしくはイメージとして表現することを表す。
【００２２】
図６は、図３で説明したグラフィックス・オブジェクトを構成する各要素情報のデータ構造の一例を示した図である。図５に従うと、Ａｒｅａ情報３０３及びＭａｓｋ情報３０４はコード６０１のような構造になる。コード６０１は、Ａｒｅａ情報３０４及びＭａｓｋ情報３０４が、位置情報３０２からのオフセットのＸ座標を示すオフセットＸと、位置情報３０２からのオフセットのＹ座標を示すオフセットＹと、描画するグラフィックス・オブジェクトの形状に適したデータ形式６０２のうちの一つから構成されていることを表す。また、ＢＧ情報５０３及びＧｒａｙ情報５０４は、コード６０３のような構造になる。コード６０３は、ＢＧ情報５０３及びＧｒａｙ情報５０４が、位置情報３０２からのオフセットのＸ座標を示すオフセットＸと、位置情報３０２からのオフセットのＹ座標を示すオフセットＹと、描画するグラフィックス・オブジェクトの形状に適したデータ形式６０４のうちの一つから構成されていることを表す。なお、二値ビットマップ６０２ｄ、及びパターン６０４ａ、及びイメージ６０４ｄの実データ、すなわちビットマップもしくは圧縮コードはグラフィックス・オブジェクトの内部に格納されている必要はない。中間コード自体にはそれを指し示すポインタやＩＤが含まれ、実データはグラフィックス・オブジェクトの外部に保持されていても良い。各要素情報が何を表しているかは、たとえば識別コードにより示される。たとえば、「矩形」や「トラペゾイド」「ランレングス」「二値ビットマップ」それぞれにコードが割り当てられており、それがＡｒｅａ情報やＭａｓｋ情報の所定の位置に埋め込まれていれば、内容を識別可能である。
【００２３】
図６に示した個々のパラメータについて説明する。矩形６０２ａは幅と高さをパラメータとして有し、幅はスキャンライン方向、高さはそれに直交する方向についての長さを示す情報である。トラペゾイド６０２ｂは、高さと左開始位置と右開始位置と左スロープと、右スロープとをパラメータとして有する。左開始位置は、上辺の左端の位置を、位置情報５０１で定義された位置からオフセットＸ，Ｙずらした位置を基点として、Ｘ方向（スキャンライン方向）へのオフセットで表す。右開始位置は、上辺の右端の位置を同様に表す。左スロープは、左辺の傾きを、隣接するスキャンライン間における左辺相当のピクセルのずれ量をピクセル数で表した値とも考えることができる。右スロープも右辺について同様である。
【００２４】
ランレングス６０２ｃは、高さと、左位置及びランの繰返しをパラメータとして有する。高さは最終的にレンダリングされるオブジェクトの高さ（例えばライン数）を表している。レンダリングされるパターンは、各ラインにおける左位置と、その左位置を基点とするランとで構成される。本実施形態では、ランは１ラインに１つとしている。したがって、２組目以降の左位置及びランの組は、２ライン目以降にそれぞれ相当する。
【００２５】
二値ビットマップ６０２では、横方向の拡大率Ｘ、縦方向の拡大率Ｙ、オフセットＸ，Ｙ、二値ビットマップ（または圧縮コード）をパラメータとして有する。拡大率は各方向について、二値ビットマップを拡大する率を示す。
【００２６】
パターン６０４ａおよびイメージ６０４ｃは、二値ビットマップ６０２ｄと同様のパラメータを有する。単色６０４ｂは、色を示す値のみを有する。
【００２７】
図７は、上述したグラフィックス・オブジェクトの簡単な例である。７０２はグラフィックス・オブジェクトを表す中間コードであり、７０１は中間コード７０２によって描画されるビットマップ画像である。本例のグラフィックス・オブジェクトは、Ａｒｅａ情報とＧｒａｙ情報とでグラフィックス・オブジェクトの形状および色を指定できるので、図７の例では未使用のＭａｓｋ情報及びＢＧ情報にはＮＵＬＬが指定されている。また、このグラフィックス・オブジェクトを表すためにＡｒｅａ情報６０１をトラペゾイド６０２ｂにしている。また、本例のグラフィックス・オブジェクトは、色値０ｘ００００００によって塗りつぶされるため、Ｇｒａｙ情報６０４ｂとして０ｘ００００００を指定している。また本例では、ディスティネーションに上書をするので、ＲＯＰ情報としてディスティネーションへの上書を示す"Ｓ"を指定している。
【００２８】
図７の例では、グラフィックスオブジェクトの中間コード７０２には、位置情報として（１０，３０）、Ａｒｅａ情報として「トラペゾイド」、Ｇｒａｙ情報として単色が指定されている。Ｍａｓｋ情報とＢＧ情報はともにＮＵＬＬであり、未使用である。トラペゾイド６０２ｂのパラメータは、先頭の２つの"０"はオフセットであり、形状自体は「２０，１０，１０，−１／２，１／２」で表される。先頭から、高さ、左開始位置、右開始位置、左スロープ、右スロープとなる。左開始位置、右開始位置は、位置情報５０１で示される位置からのＸ方向についての相対位置である。図７ではともに１０であり、いずれも開始位置（１０，３０）をＸ方向について１０加算した位置（２０，３０）となって一致する。左スロープ、右スロープは、それぞれ台形の左辺と右辺の傾きを、１ラインでずれるピクセルの数で示す。図７では左スロープは−１／２であり、あるスキャンラインにおける左辺に相当するピクセル位置に対して、その直下のスキャンラインでは、左辺の位置は左に２分の１ピクセルずれることを示している（符号は方向を示す）。右辺も同様であるが、符号が＋であるので、ずれの方向は右方向となる。実際にこの台形（左開始点と右開始点とが一致しているので三角形となる。）をレンダリングする際には、２分の１ピクセルのずれは表現できないので、２スキャンライン毎に１ピクセルずつ左あるいは右に左辺あるいは右辺の位置をずらすことになる。図７のグラフィックスオブジェクト７０１はレンダリングされた例を示している。
【００２９】
＜描画部２０６の動作（図８Ａ−図８Ｃ）＞
図８Ａ−図８Ｃは、描画部２０６の動作を説明するフローチャートである。本例では、バッファ２０７はオブジェクトをラスタライズしたビットマップデータをスキャンライン単位で格納する。そのため、相異なるスキャンラインについても、対応する位置のピクセルは同じメモリロケーションに格納される。たとえば、画像上で同一のカラムに属するピクセルは、バッファ２０７においては同一のロケーション（すなわち同一アドレスのセル）に格納される。また、上述した中間コードは、たとえば１ページごとに記憶部２０９に格納されている。
【００３０】
図８Ａ（ａ）において、描画部２０６は、処理対象となっているページに含まれる未処理のグラフィックスオブジェクトの有無を判定する（Ｓ８１１）。未処理のグラフィックスオブジェクトがあれば、グラフィックス・オブジェクト単位で記憶部２０９から中間コードを読み出す（Ｓ８１２）。描画部２０６は、読み出したグラフィックスオブジェクト（着目グラフィクスオブジェクト）をラスタライズ（展開）して、展開されたビットマップデータをバッファ２０７に格納する（Ｓ８１３）。バッファ２０７に格納されたグラフィックス・オブジェクトの１スキャン・ラインは、転送部２０８により読み出され、論理演算部２１２に転送される。論理演算部２１２では、図８のＳ８０２にて設定された情報に従い、必要であれば記憶部２０９から、転送部２０８から転送されたスキャン・ラインを格納するアドレスに既に保持されている、上記スキャン・ラインに相当する色値を読み出し、論理演算を施し、記憶部２０９に格納する。すなわち、ラスタライズされたビットマップデータはＲＯＰ情報に従って記憶部２０９のフレームバッファに合成される（Ｓ８１４）。
【００３１】
ステップＳ８１２で読み込んだグラフィックスオブジェクトの展開を終えたか判定し（Ｓ８１５）、終えていないならステップＳ８１３に戻って展開処理を続ける。すなわち、転送部２０８により、バッファ２０７のスキャン・ラインが読み出されると、描画部２０６は続くスキャン・ラインを上述した方法でバッファ２０７に形成する。上述した処理をグラフィックス・オブジェクトのすべてのスキャン・ラインに対して行うことで、記憶部２０９にグラフィックス・オブジェクトのビットマップが形成される。着目グラフィクスオブジェクトの展開を終えたならステップＳ８１１に戻る。
【００３２】
図８Ａ（ｂ）にステップＳ８１３の詳細を示す。描画部２０６は、まずバッファ２０７に描画するスキャン・ラインが、読み出されたグラフィックス・オブジェクトの最初のスキャン・ラインか否か検査する（Ｓ８０１）。最初のスキャン・ラインである場合には、論理描画部２１２が転送部２０８から受信したビットマップ画像を記憶部２０９に伝送するための情報、本実施形態においてはアドレスや論理演算パラメータを論理描画部に設定する（Ｓ８０２）。このほか、ステップＳ８０４で参照する変数パラメータ等の初期化もここで行う。たとえば、後述するスキャンライン番号や差分バッファなどの初期化や、グラフィックオブジェクトがトラペゾイドの場合に参照される左エッジ座標、右エッジ座標変数等である。左エッジ座標、右エッジ座標は、トラペゾイドのパラメータの左開始点、右開始点に相当する値に初期化される。
【００３３】
続いてバッファ２０７にグラフィックス・オブジェクトの最初のスキャン・ラインを構成する全てのピクセルを出力する（Ｓ８０３）。ステップＳ８０１にて最初のスキャン・ラインではないと判断された場合には、直前にバッファ２０７に出力したスキャン・ラインと、今回出力するスキャン・ライン（着目スキャンライン）で、互いに相当するピクセル（同位置にあるピクセル）のうち差分があるピクセルを求める（Ｓ８０４）。続いてステップＳ８０４にて求められた差分があるピクセルについてその値を出力する（Ｓ８０５）。ここで、バッファ２０７には、着目スキャン・ラインの直前のスキャン・ラインのラスタ情報（ドットイメージデータ）が残っている。そのため、差分のあるピクセルのみを出力するだけで、着目スキャン・ラインの完全なラスタ情報がバッファ２０７に保持される。ピクセル値は、Ｇｒａｙ情報やＢＧ情報で与えられる値である。本実施形態では、Ｇｒａｙ情報やＢＧ情報がイメージやパターンの場合には、１ラインの全画素が差分ピクセルとされるために、この場合は実質的にはステップＳ８０３と同じ処理となる。したがって差分のあるピクセルのみを出力するのは、Ｇｒａｙ情報やＢＧ情報が単色の場合であるから、出力される値はＧｒａｙ情報やＢＧ情報で与えられる値そのものでよい。
【００３４】
以上説明したように、描画部２０６は中間コードからビットマップ画像の一部、本実施形態においてはグラフィックス・オブジェクトの１スキャン・ライン、を生成する。
【００３５】
図８Ｂ−図８Ｃは、ステップＳ８０４の詳細を示すフローチャートである。実行主体は描画部２０６である。なおこのフローチャートでは差分バッファなるメモリ領域を用いている。差分バッファは記憶部２０９に設けられた領域で、差分ピクセルがあればその位置を示す情報を、なければその旨を示す情報を保存するために使用される。着目スキャンラインの番号（先頭を０とする）は、記憶部２０９などに保存されて参照される。これを着目スキャンライン番号と呼ぶことにし、以下の説明でも必要に応じて参照する。
【００３６】
まず、Ｇｒａｙ情報５０４およびＢＧ情報５０３がいずれもＮＵＬＬではなく、かつ、いずれも単色であるか判定する（Ｓ８２３）。ＮＵＬＬではなくしかも単色でなければ、パターンかイメージである。これらは、色値の分布がパターンあるいはイメージで定義されている情報であって、隣接するライン間の対応するピクセル同士を比較しなければ差分ピクセルを決定できない。そこで、Ｇｒａｙ情報５０４およびＢＧ情報５０３がともに単色でなければ、ステップＳ８２７で、差分バッファに、注目ラインの全ピクセルを記録する（たとえば全ピクセルが差分ピクセルであることを示す情報を記録すればよい）。なお、Ｇｒａｙ情報５０４またはＢＧ情報５０３の値のいずれかが未定義（ＮＵＬＬ）の場合には、ＮＵＬＬではない方の情報に限って判断の対象とする。
【００３７】
ステップＳ８２３でＹＥＳと判定された場合には、Ｇｒａｙ情報５０４およびＢＧ情報５０３は、ＮＵＬＬか単色かのいずれかである。その場合には、Ｍａｓｋ情報５０２があるか、すなわちＮＵＬＬではないか判定する（Ｓ８２４）。Ｍａｓｋ情報５０２がＮＵＬＬであれば、Ａｒｅａ情報５０１が「矩形」６０２ａであるか判定する（Ｓ８２５）。ステップＳ８２５において「矩形」６０２ａと判定された場合には、差分バッファに差分ピクセルはない旨を記録する（Ｓ８２８）。これは、矩形では最初のラインから最終ラインまで描かれるピクセルは同一であるからである。なお、本実施の形態では、オフセットが０の場合を説明したので、差分を計算する必要がないが、たとえばオフセットＹ＝１、高さ３の矩形を描画する場合は、スキャンラインが０から始まるとすると、１ライン（矩形の上辺）と４ライン（矩形の底辺の次のライン）とに差分が発生し、上辺や底辺の部分を差分ピクセル位置とする。
【００３８】
一方、ステップＳ８２５においてＡｒｅａ情報５０１は矩形ではないと判定された場合、Ａｒｅａ情報５０１が「トラペゾイド」（台形）６０２ｂであるか判定する（Ｓ８２９）トラペゾイドであれば、ステップＳ８０２で初期化された左エッジ座標変数、右エッジ座標変数に、左スロープおよび右スロープの値をそれぞれ加算する（Ｓ８３１）。そして左エッジ座標変数と右エッジ座標変数それぞれの整数部に値の変化があったか判定する（Ｓ８３２）。このためにはステップＳ８３１で加算する直前の値を一時的に記憶しておけばよい。いずれかに変化があったなら、着目スキャンラインとその直前のスキャンラインとの間で、レンダリングされるべきピクセルが変化したということなので、それら変数の整数部に相当する位置を、差分バッファに差分ピクセルの位置として記録する（Ｓ８３３）。いずれも変化しなければエッジの位置に変化はないとして、ステップＳ８２８に分岐する。なお、前記変数の変化が増加であるか、減少であるかにより差分ピクセルの位置は異なる。増加の場合には、増加後の値それぞれが差分ピクセルに相当する。たとえば５から７に増加すれば、増加後の６，７が差分ピクセルである。減少の場合には、減少前の値が差分ピクセルに相当する。たとえば７から５に減少すれば、減少前の６，７が差分ピクセルである。このようにして差分ピクセルの位置が決定される。
【００３９】
一方ステップＳ８２９においてＡｒｅａ情報がトラペゾイドではないと判定された場合には、Ａｒｅａ情報がランレングスであるか判定する（Ｓ８３４）。ランレングスであれば、着目スキャンラインと直前のスキャンラインとのランの開始位置（左位置）および終了位置（左位置とランの長さとから決定される。）の位置のずれに基づいて、ずれた位置（ずれた分の全て）が差分ピクセルの位置として差分バッファに記録される（Ｓ８３５）。なお、本実施の形態では、オフセットが０の場合を説明したが、たとえばオフセットＹ＝１、高さ３の台形を描画する場合は、スキャンラインが０から始まるとすると、１ライン（台形の上辺）と４ライン（台形の底辺の次のライン）とに差分が発生し、上辺や底辺の部分を差分ピクセル位置とする。
【００４０】
ステップＳ８３４でランレングスではないと判定された場合、オブジェクトは二値ビットマップである。その場合、拡大率Ｙのパラメータを参照して、２以上の変倍率が指定されているか判定する（Ｓ８３６）。指定されていなければステップＳ８２７に分岐して、差分バッファに全画素を差分ピクセルとする旨の情報を記録する。２倍以上の変倍率が指定されていれば、着目スキャンラインが複製されるラインであるか判定する（Ｓ８３７）。たとえば拡大率が２倍であれば、偶数番目のラインはその直前のラインの複製となる。その場合にはステップＳ８２８に分岐して、差分ピクセルはないことを示す情報を差分バッファに保存する（Ｓ８２８）。複製ラインでなければ、着目スキャンラインのビットマップと、その直前のスキャンラインのビットマップの差分ピクセルを決定する（Ｓ８３８）。差分ピクセルは、着目スキャンラインのビットマップ（二値ビットマップのパラメータから獲得する。）と、その直前のスキャンライン（バッファ２０７に保存されている。）との排他的論理和を計算し、結果が０以外のピクセルが差分ピクセルである。もちろん計算はピクセルの位置を対応付けて行われる。差分ピクセルの位置が差分バッファに記録される。なお、このときＡｒｅａ情報を拡大してから差分を検査しなくともよい。例えばバッファ２０７の値を用いずに、Ａｒｅａ情報の二値ビットマップの連続するスキャン・ラインを表す数値で排他的論理和を取り、この計算結果を拡大率で乗じ、この結果ビットがＯＮになっている箇所に相当するピクセルが差分があるピクセルと判定することもできる。
【００４１】
ステップＳ８３７での複製ラインか否かの判定は、拡大率Ｙを変数Ｎとし、着目グラフィックオブジェクトにおける着目スキャンライン番号を変数ｎ（先頭ラインを０とする。）であるとした場合、以下のように行える。すなわち、スキャンライン番号ｎの拡大率Ｎを法とする剰余が０であるかを判定し、０でなければ複製ラインと判定することができる。これは、縦方向の拡大はラインの複製により実現されるからである。
【００４２】
さて、ステップＳ８２５〜ステップＳ８３７まではステップＳ８２４においてＭａｓｋ情報があると判定された場合には、図８Ｃに示すステップＳ８４１に分岐する。ステップＳ８４１〜Ｓ８５４までは、図８ＢのステップＳ８２５〜Ｓ８３８までと、Ａｒｅａ情報をＭａｓｋ情報に置き換えた点を除いてそれぞれ同一の処理を行っている。そこでそれぞれの説明は省略する。図８Ｃでは、その最後に、ステップＳ８５５で、Ａｒｅａ情報で定義される領域の外部に相当する位置の差分ピクセルを差分バッファから削除する。これは、Ｍａｓｋ情報で定義される領域内であっても、Ａｒｅａ情報で定義される領域外となるピクセルも存在し得るためである。
【００４３】
＜レンダリングの具体例１＞
続いて具体例を挙げて本実施形態の画像形成装置を説明する。本例においては、図７で示したグラフィックス・オブジェクトを表す中間コードが記憶部２０９に格納され、このグラフィックス・オブジェクトを描画部２０６にて描画する際の動作について詳細に説明する。
【００４４】
描画部２０６は、記憶部２０９に格納されたグラフィックス・オブジェクトを表す中間コードを読み込む。描画部２０６は、中間コードに記載されているＲＯＰ情報３０１及び位置情報３０２を読み出し、更に読み出された中間コードにＡｒｅａ情報３０３及びＭａｓｋ情報３０４及びＢＧ情報３０５及びＧｒａｙ情報３０６が設定されているか、すなわちＮＵＬＬ値ではないか、を検査する。この結果と中間コードに記載されているＲＯＰ情報３０１から、ディスティネーションとの論理演算パラメータを決定し、上述のように決定されたディスティネーションとの論理演算パラメータと、位置情報３０２を、論理演算部２１２に転送する。
【００４５】
続いて、描画部２０６は、ＮＵＬＬ値ではない中間コードに記載されている情報をもとに、グラフィックス・オブジェクトの最初のスキャン・ラインをバッファ２０７に書き出す。このときバッファ２０７に書き出すスキャン・ラインは、バッファ２０７の先頭から、後述する論理演算部２１２にて計算される記憶部２０９のアドレスに転送したときに、スキャン・ラインが正しく記憶部２０９に転送されるように形成される。本例においては、Ｍａｓｋ情報及びＢＧ情報がＮＵＬＬであるため、Ａｒｅａ情報から、トラペゾイドを構成する右エッジのＸ座標と左エッジのＸ座標を計算し、また、グラフィックス・オブジェクトの右エッジで最大となるＸ座標を計算して、ラスタ情報を、Ｇｒａｙ情報、すなわち単色（本例では０ｘ００００００）、に従ってバッファ２０７に書き出す。すなわち、本例では、右エッジの最大のＸ座標は２０となり、最初のスキャン・ラインでの左エッジのＸ座標は１０となり、右エッジのＸ座標は１０となるため、バッファ２０７の０から９及１１から１９は白に相当する色値、例えば０ｘｆｆｆｆｆｆ書き出し、バッファ２０７の１０には０ｘ００００００を書き出す。なお、本例においては、トラペゾイドの右エッジ座標の最大値を描画部２０６にて計算するようにしているが、中間コード中に予めグラフィックス・オブジェクトの最小及び最大の座標を記載しておいても良い。
【００４６】
続いて、転送部２０８は、バッファ２０７に書き出されたサイズに相当するラスタを読み出し、論理演算部２１２に転送する。論理演算部２１１は、描画部２０６から予め転送された論理演算パラメータを調査（すなわちどの論理演算パラメータであるか判別）し、記憶部２０９に既に格納されているラスタ情報を読み出す必要があるか否かを検査する。上記判断で、ラスタ情報（ビットマップの列）を読み出すと判断された場合には、描画部２０６から予め転送されていた位置情報から、ラスタ情報を読み出す記憶部２０９のアドレスを求め、該アドレスからラスタ情報を読み出し、これと、転送部２０８から転送されたラスタ情報を論理演算し、上記アドレスに、論理演算した結果のラスタ情報を格納する。たとえば記憶部２０９において、紙面一面の（１ページの）ビットマップを保持する場合には、フレーム・バッファが記憶部２０９に保持されることになる。その場合、上記ラスタ情報を読み出す記憶部２０９のアドレスは、フレーム・バッファの先頭アドレスに位置情報を加算することで計算される。また、記憶部２０９において、紙面を帯状に分割したバンドのビットマップを保持する場合には、バンド・バッファが記憶部２０９に保持されることになる。その場合には、バンド・バッファの先頭アドレスに、位置情報を加算することで上記アドレスを求めることができる。本例においては、論理演算パラメータとして"Ｓ"を指定しているので、記憶部２０９から既に格納されているラスタ情報を読み出す必要がなく、転送部２０８から転送されたラスタ情報を、記憶部２０９の上記アドレスに転送する。
【００４７】
記憶部２０９への格納が終了すると、論理演算部２１２は、続くスキャン・ラインの転送に備えて、上述したアドレスを更新する。転送部２０８によるバッファ２０７からラスタを読み出しが完了すると、描画部２０６は続くスキャン・ラインをバッファ２０７に形成するが、このとき描画部２０６は、前のスキャン・ラインと続くスキャン・ラインのそれぞれ相当するピクセルで差分があるピクセルのみの更新を行う（図８Ｂ，８Ｃ参照）。すなわち、中間コードに格納されている全ての情報について、前のスキャン・ラインと続くスキャン・ラインのそれぞれ対応するピクセルに相当するピクセルで、差分があるピクセルを決定し、上記のように決定されたピクセルに相当するバッファ２０７に格納されたピクセルを塗りつぶす。本例においては、前のスキャン・ラインと続くスキャン・ラインのそれぞれ相当するピクセルで、差分がある情報はＡｒｅａ情報のみである。Ａｒｅａ情報の差分があるピクセルは、前のスキャン・ラインでの右エッジ座標と左エッジ座標と、右スロープと左スロープから判断する。本例において、エッジ座標がピクセルをまたぐ場合には、左エッジについては、エッジ座標がピクセルの中心座標より小さい場合には、概ピクセルはグラフィックス・オブジェクトの内側にあるように判断してピクセル生成を行う。右エッジについては、エッジの座標がピクセルの中心座標を超える場合に、概ピクセルはグラフィックス・オブジェクトの内側にあるようにピクセル生成を行う。そのため、第二スキャン・ラインでの左エッジ座標は１０、右エッジ座標は１０となり、差分があるピクセルがない。そのため、バッファ２０７は前スキャン・ラインのラスタ情報を保持したままとなり、このラスタ情報が転送部２０７に転送され、上述した最初のスキャン・ラインと同様に、論理演算部２１２に転送された後、記憶部２０９に格納される。
【００４８】
続いて第三のスキャン・ラインを、上述した方法と同様に、バッファ２０７に形成する。本例では、第三スキャン・ラインでの左エッジ座標と右エッジ座標はそれぞれ、９、１１となる。第二のスキャン・ラインと第三のスキャン・ラインのそれぞれ相当するピクセルで、バッファ２０７での座標９と座標１１のピクセルに差分が発生する。よって描画部２０６は、左から９番目と１１番目のピクセルを、まず白に相当する色値、例えば０ｘｆｆｆｆｆｆで塗りつぶし、続いてトラペゾイドのエッジ間にあるピクセルをＧｒａｙ情報、すなわち０ｘ００００００、で塗りつぶす。白に相当する色値で塗りつぶす理由は、左エッジにおいてエッジの成長方向が右である場合と、右エッジにおいてエッジの成長方向が左である場合に対応するためである。あらかじめエッジが右エッジなのか、左エッジなのかを検査しておき、左エッジでエッジの成長方向が左の場合と、右エッジでエッジの成長方向が右である場合には、白に相当する色値で塗りつぶす処理を省略してもよい。以上で説明した処理をグラフィックス・オブジェクトの高さ、本例においてはトラペゾイドの高さである２０、で繰り返すことにより、記憶部２０９に描画部２０６で読み込んだ中間コードに相当するグラフィックス・オブジェクトのビットマップが形成される。
【００４９】
図９は、上述したグラフィックス・オブジェクトの形成を図示したものであり、９０１はグラフィックス・オブジェクトの先頭のスキャン・ラインから８ライン分を示した図であり、９０２及至９０９はスキャン・ライン毎に塗りつぶす必要があるピクセルを図示したものである。９０２は先頭のスキャン・ラインであるため、すべてのピクセルを塗りつぶす必要がある。９０３及び９０５及び９０７及び９０９には差分のピクセルがないため、これに相当するスキャン・ラインでは、描画部２０６はバッファ２０７に書き出しを行わない。スキャン・ライン９０４，９０６，９０８については、描画部２０６は、塗りつぶされているピクセルのみピクセルの書き出しを行う。図９においては、２０×８＝１６０ピクセルが図示されているが、この方法によって、２６ピクセルの塗りつぶしでビットマップが生成できることになる。
【００５０】
＜レンダリングの具体例２＞
続いて図１０に示されるグラフィックス・オブジェクトを描画部２０６で形成する場合について説明する。１００１は、矩形１００３と、矩形１００３上にビットマップ・フォント１００２が重なるビットマップであり、ビットマップ・フォント１００２を現す中間コードは１００４のようになる。なおビットマップ・フォント１００２の色値は、矩形１００３のそれぞれ対応するピクセルの色値と排他的論理和を計算して色値が決定される。なお、矩形１００３のグラフィックス・オブジェクトを示す中間コード及びその描画方法は、上述の説明で容易に理解できるため説明しない。１００４では、ＲＯＰ情報は、Ａｒｅａ情報はクリップであり、対応するディスティネーションの各ピクセルの色値と排他的論理和を計算して色を決定することを示す"ＤＰＳｏｘ"であり、位置情報は、該グラフィックス・オブジェクトが紙面のＸ座標１０、Ｙ座標３０に書き出されることを示し、Ａｒｅａ情報は幅２０、高さ２０の矩形であり、Ｍａｓｋ情報は二値ビットマップであり、ＢＧ情報はＮＵＬＬ値であり、Ｇｒａｙ情報は単色である。なおフォントの場合、フォント・キャッシュにフォントを構成するビットマップを格納する場合があり、本実施形態でも中間コードにはフォント・キャッシュのＩＤを示す数値を中間コードに格納し、フォントを構成するビットマップはフォント・キャッシュに格納され、フォント・キャッシュには１００５に示す二値ビットマップが格納されている。なお二値ビットマップのそれぞれのスキャン・ラインの右側に記載されている数値は、該スキャン・ラインを数値で表したものであり、スキャン・ラインあたり１６ビットで表現されていることを示す。また、Ｍａｓｋ情報の二値ビットマップはオフセットにＸ，Ｙともに０が指定されている。これは１００３に示すビットマップの左上の座標（０、０）からビットマップを形成することを示す。またＭａｓｋ情報の二値ビットマップは拡大率Ｘ，Ｙともに２が指定されている。これは１００３に示すビットマップを縦及び横方向に２倍してビットマップを形成することを示す。
【００５１】
中間コード１００４が描画部２０６に読み込まれると、描画部２０６は１００４で示す中間コードが示すグラフィックス・オブジェクトとディスティネーションとの論理関係を判定する。本例において、グラフィックス・オブジェクトとディスティネーションとの論理関係は、グラフィックス・オブジェクトとディスティネーションの各ピクセルで排他的論理和をとるようにＲＯＰ情報で指定されているため、グラフィックス・オブジェクトとディスティネーションとの論理関係は、排他的論理和を示す"Ｘ"となる。上述のように求められた論理関係と位置情報は論理演算部２１２に伝送される。続いて描画部２０６は中間コードに含まれる情報を読み取り、グラフィックス・オブジェクトの最初のスキャン・ラインをバッファ２０７に書き出す。本例において、Ａｒｅａ情報はクリップであるので、クリップに含まれないピクセルは白に相当する色値、例えば０ｘｆｆｆｆｆｆを書き出す。クリップに含まれるピクセルで且つＭａｓｋ情報の対応するビットがオンのピクセルは、Ｇｒａｙ情報に従った色値、すなわち０ｘ００００００を書き出す。本例では、二値ビットマップの拡大率Ｘに２が指定されているので、バッファ２０７の０から５及び８から１９は白に相当する色値、すなわち０ｘｆｆｆｆｆｆで塗りつぶされ、６から７はＧｒａｙ情報に相当する色値、すなわち０ｘ００００００で塗りつぶされる。
【００５２】
続いて、上記バッファ２０７に格納されたラスタ情報は転送部２０８に読み出され、論理演算部２１２に伝送される。論理演算部２１２では、予め描画部２０６よりディスティネーションとの論理演算パラメータとして"Ｘ"が指定されているので、記憶部２０９の概ラスタ情報の転送先から色値を読み出し、これと概ラスタ情報の排他的論理和を計算し、再び記憶部２０９に格納する。転送部２０８よりバッファ２０７に格納されているラスタ情報が読み出されると、続くスキャン・ラインをバッファ２０７に形成する。本例においては、Ａｒｅａ情報及びＧｒａｙ情報は、グラフィックス・オブジェクトの先頭のスキャン・ラインから終端のスキャン・ラインまで変化はなく、また、Ｍａｓｋ情報ではＹの拡大率として２が指定されているので、このグラフィックス・オブジェクトの偶数番目のスキャン・ライン（すなわち図８Ｃで説明したｎ ｍｏｄ Ｎ≠０となるスキャンライン）では上のスキャン・ラインのそれぞれ相当するピクセルで色値に差分がない。このため、偶数番目のスキャン・ラインにおいては、バッファ２０７の内容に変更がないまま、転送部２０８にラスタ情報を転送することになる。
【００５３】
先頭及び偶数のスキャン・ライン以外については、Ｍａｓｋ情報のスキャン・ライン間の差分を検査し、差分のあるピクセルに相当するバッファ２０７のピクセルに対して塗りつぶしを行う。このときＭａｓｋ情報を拡大してから差分を検査する必要はなく、Ｍａｓｋ情報を、例えばＭａｓｋ情報の二値ビットマップの連続するスキャン・ラインを表す数値で排他的論理和を取り、この計算結果を拡大率で乗じ、この結果ビットがＯＮになっている箇所に相当するピクセルが差分があるピクセルと判定すればよい。
【００５４】
以上の処理をグラフィックス・オブジェクトの終端のスキャン・ラインまで繰り返すことにより、中間コード１００４が表すグラフィックス・オブジェクトが記憶部２０９に形成されることになる。
【００５５】
図１１は、中間コード１００４のＭａｓｋ情報の、連続するスキャン・ラインでそれぞれに相当するピクセルで差分があるピクセルを図示したものであり、１１０１は、Ａｒｅａ情報を適用したＭａｓｋ情報、１１０２及至１１１１は差分情報を示す。ただし、先頭のスキャン・ライン（１１０２）においては、全てのピクセルで差分があるとしている。この差分があるピクセルは、上述したように、連続するスキャン・ラインで排他的論理和をとることで判定可能である。具体的には、最初のスキャン・ラインと、続くスキャン・ラインのそれぞれ相当するピクセルで差分のあるピクセルは、隣接するラインの対応ピクセルの排他的論理和（ＸＯＲで表す。）、たとえば（０ｘ１０００）ＸＯＲ（０ｘ１１００）＝０ｘ０１００にて求めることが出来る。なお、本例においては、二値ビットマップの幅が１６ビットであるが、これより大きい幅を持つビットマップでも、先頭から、例えば３２ビット単位や１６ビット単位で、排他的論理和を計算することで、差分情報を上述した手法と同じ手法で求めることができる。
【００５６】
図１２は、中間コード１００４のＭａｓｋ情報を拡大したときの状態を図示し、１２０１は拡大する前の二値ビットマップ、１２０２はピクセルを拡大する方法を説明する図、１２０３は１２０１を拡大した二値ビットマップを示す。縦及び横方向に２倍拡大する際には、１２０２に示すように、任意の１ピクセルが縦及び横方向に二つずつ並ぶようにピクセルを生成すれば拡大することができる。
【００５７】
＜レンダリングの具体例３＞
続いて図１３に示すグラフィックス・オブジェクトを表す中間コードを描画部２０６で形成する場合について説明する。１３０１は、生成されるビットマップであり、１３０２は中間コードであり、Ａｒｅａ情報としてクリップとしての矩形、Ｍａｓｋ情報及びＢＧ情報はなく、Ｇｒａｙ情報としてイメージを持ち、イメージは１３０３に示されるようなビットマップである。Ｇｒａｙ情報やＢＧ情報がビットマップである場合には、ビットマップの連続するスキャン・ラインでそれぞれ相当するピクセルで差分がある位置を予め計算するのは負荷が高い。このため、本実施形態ではＧｒａｙ情報やＢＧ情報がビットマップである場合には、全てのピクセルで差分があるものとみなす。すなわち、バッファ２０７には、イメージを、必要に応じてＸ方向に拡大しながら、出力することになる。Ｙ方向の拡大については、前述したように、Ｙ方向の拡大率に応じて、バッファ２０７への書き出しを行うもしくは行わないを選択的に制御することで実現できる。このように、中間コードの属性に応じて差分を求める方法を切り替えることにより、差分を求めるのが難しい、もしくは負荷が高い場合も柔軟に対応が可能になる。
【００５８】
なお、本発明において、バッファ２０７と記憶部２０９は別のデバイスであることが望ましいが、同じデバイスであっても本発明が適用できる。また、本実施形態では形成するビットマップのピクセルはＲＧＢ２４ビットであったが、ピクセルが他の色表現、例えばＣＭＹＫ形式やＹＣＣ形式やモノクロ形式であっても良いことはいうまでもない。
【００５９】
以上の様にして、本実施形態によれば、グラフィックオブジェクトをライン単位でレンダリングする際に、一定の条件のもとで、隣接ライン間において相異なる値を持つ対応画素（差分ピクセル）に限って再レンダリングすることで、レンダリング処理の効率化を実現している。一方、ＢＧ情報やＧｒａｙ情報がイメージやパターンといった色値の内包的定義を含むグラフィックオブジェクトについては、描画対象のスキャンライン全体を差分ピクセルとみなして再レンダリングしている。こうすることで、差分ピクセル（の位置）を決定するための処理の負荷が大きくなる可能性が高い場合には、差分のピクセルを決定する処理を省いて効率的なレンダリング処理を実現できる。
【００６０】
［実施形態２］
続いて、本発明に係る別の実施形態について説明する。なお、本実施形態において、実施形態１で説明したものについては説明を省略する。また、本発明に直接関連しない構成要素は図からも省略している。
【００６１】
描画部２０６での画像形成方式で、処理速度的に難があるグラフィックス・オブジェクト、例えばＹ方向の拡大率が１であるイメージ等、ではバッファ２０７に画像を形成した上で記憶部２０９に転送するため、実施形態１の方法でレンダリング（描画とも言う。）を行うと従来の描画方式より処理速度が遅くなる場合がある。このため、グラフィックス・オブジェクト毎に従来の描画方式と、本発明に係る描画方式を切り替える方法が望まれる。第２の実施形態ではこれを実現する構成について説明する。
【００６２】
図１４は、上記要望を満たす、従来の描画方式と本発明の描画方式を切り替えるプリンタコントローラの一例を表す図である。１４０１はプリンタコントローラであり、第一の実施形態で説明した２０３に相当する。１４０１は、第一の実施形態で説明した描画部２０６であり、図８Ａ（ｂ）−図８Ｃの手順でグラフィックスオブジェクトをレンダリングする。このほかバッファ２０７、転送部２０８、論理描画部２１２、記憶部２０９があり、また、図示しないが、図２におけるＩ／Ｆ２０４、解釈部２０５、画像処理部２１１、ビデオ転送部２１０も具有する。１４０３は従来の描画部であり、グラフィックオブジェクトのレンダリングを従来の手順で行う。この手順ではたとえばオブジェクトの全画素の値をラスタ順で決定する。１４０２は記憶部２０９に保持されている中間コードに従って、中間コードを描画部２０６もしくは描画部１４０３に振り分ける。描画部１３０３は記憶部２０９と接続されている。
【００６３】
第一の実施形態で説明した中間コードは、従来の描画方式における中間コードと互換性を保つ。このため、判断部１４０２にて、グラフィックス・オブジェクトの属性に従って、描画部１４０３もしくは描画部２０６に中間コードを転送することで、従来の描画方式と、本発明に係る描画方式を切り替える。判断部１４０２は、例えば、Ｇｒａｙ情報がイメージであり、且つＹ方向の拡大率が１ならば描画部１４０３に読み込んだ中間コードを転送し、従来の手順でレンダリング処理を行う。一方、Ｇｒａｙ情報がイメージであり、且つＹ方向の拡大率が１以外ならば描画部２０６に中間コードを転送し、描画部２０６により第１実施形態のの図８Ａ（ｂ）−図８Ｃに係るレンダリング処理を行う。
【００６４】
この判断は図８Ａ（ａ）のステップＳ８１２の直後に行われ、着目グラフィックスオブジェクトに関して、そのＧｒａｙ情報がイメージであり、且つＹ方向の拡大率が１ならば、ステップＳ８１３に分岐し、そうでなければ、従来の手順で着目グラフィックオブジェクトをレンダリングする。このように中間コードの属性に従って描画方式を切り替えることで、処理速度をより向上させたプリンタコントローラを実現することが可能になる。
【００６５】
［実施形態３］
続いて、本発明の第３の実施形態について図を用いて説明する。図２１は本実施形態の画像形成方法を実施するためのプリンタコントローラの概念図である。２１０１はプリンタコントローラ、２１０２は図示しない外部ホストからプリントデータを受信し記憶部２１０７に保存するＩ／Ｆ、２１０３は上記記憶部２１０７に保存されたプリントデータを解釈して、後述する中間コードを生成し記憶部２１０７に保存する解釈部、２１０４は上記記憶部２１０７に保存された中間コードを読み取ってスキャン・ライン毎にバッファ２１０５に画像を形成する描画部、２１０５は少なくとも形成されるビットマップのスキャン・ラインが保持できるバッファ、２１０６はバッファ２１０５に形成されたスキャン・ライン画像を記憶部２１０７に伝送するＤＭＡ、２１０７は、たとえばメモリである、記憶部であり、２１０８は記憶部２１０７に格納されたビットマップに、画像処理を行う画像処理部であり、２１０９は図示しないプリンタエンジンに、画像処理部２１０８にて画像処理を行った画像を転送するビデオ転送部である。記憶部２１０７はＩ／Ｆ２１０２及び解釈部２１０３及び描画部２１０４及びＤＭＡ２１０６及び画像処理部２１０８及びビデオ転送部２１０９と接続され、バッファ２１０５は描画部２１０４及びＤＭＡ２１０６と接続される。
【００６６】
続いて、本実施形態における画像形成方法について、図を用いて説明する。図示しないホストコンピュータから伝送されたプリントデータは、Ｉ／Ｆ２１０２にて記憶部２１０７に保存される。記憶部２１０７に保存されたプリントデータは解釈部２１０３にて、図１６のフローチャートに従って解釈され、中間コードに変換される。解釈部２１０３の動作については後述する。なお、プリントデータは複数のグラフィックス・オブジェクトから構成される。通常グラフィックス・オブジェクトは、描画するビットマップの奥に配置するものから順に転送される。本実施形態においては、記憶部２１０７に保存されるプリントデータは、描画するビットマップの奥行き方向の順番を保って保存されるものとする。解釈部２１０３でプリントデータから変換された中間コードは記憶部２１０７に保存される。上述のように記憶部２１０７に保存された中間コードは、描画部２１０４に読み込まれ、中間コードに従って描画部２１０４はバッファ２１０５に、スキャン・ラインのラスタを形成する。描画部２１０４の動作については後述する。上述のようにバッファ２１０５に形成されたスキャン・ラインのラスタは、ＤＭＡ２１０６によって記憶部２１０７の予め設定されていたアドレスに転送される。ＤＭＡ２１０６にて転送が終了すると、ＤＭＡは続くスキャン・ラインの転送に備え、記憶部２１０７の転送先アドレスを、例えば転送したラスタサイズ分アドレスをインクリメントすることにより、更新する。また、ＤＭＡ２１０６にてバッファ２１０５のラスタが読み込まれても、バッファ２１０５はそのラスタ情報を保持するようにする。ＤＭＡ２１０６でラスタの転送が終了すると、描画部２１０４は続くスキャン・ラインをバッファ２１０５に形成する。以下、記憶部２１０７に形成するビットマップの全スキャン・ラインに対して上述した処理を繰り返すことにより、記憶部２１０７には、１面分のビットマップが形成される。記憶部２１０７にビットマップが形成されると、画像処理部２１０８は、図示しないプリンタ・エンジンに転送が行えるように画像データのフォーマット変換を行い、変換しビットマップを記憶部２１０７に格納する。ビデオ転送部２１０９は、画像処理部にて変換されたビットマップを読取り、外部の図示しないプリンタ・エンジンにビットマップを転送し、プリンタ・エンジンは、受信したビットマップを、紙面に印字する。
【００６７】
なお、本実施形態では、記憶部２１０７に１面（１ページ）分の画像を形成したが、紙面を帯状に分割した領域毎に処理を行ってもよく、この場合、記憶部２１０７にはバンドバッファを用意すればよく、またＤＭＡ２１０６は、予め定められたバンド高さ分のラスタを記憶部２１０７に転送したのち、転送先のアドレスを初期化すればよい。
【００６８】
＜中間コードの形式＞
続いて、解釈部２１０３にてプリントデータから変換される中間コードを構成する要素の一例を図１５に示す。以下、中間コードを構成する要素を差分リストと呼ぶ。図１５において１５０１は、連続する２つのスキャン・ラインにおいてそれぞれに相当するピクセルで差分があるピクセルのＸ座標であり、１５０２は連続して差分があるピクセルの個数である。１５０３は差分のあるピクセルを塗りつぶすグラフィックス・オブジェクトのリストであり、１５０４は同一のスキャン・ラインに存在するほかの位置での差分リストを指し示すポインタである。なお、グラフィックス・オブジェクトのリストには、塗りつぶしを行わないことを示すパラメータを指定することができ、これは、例えばグラフィックス・オブジェクトの最後のスキャン・ラインの次のスキャン・ラインにおいて、該グラフィックス・オブジェクトで描画されたピクセルを消去するために利用される。また差分リストはスキャン・ライン毎に形成され、差分のないスキャン・ラインについては、ＮＵＬＬが指定されることになる。
【００６９】
＜中間コードの生成手順＞
図１６において、解釈部２１０３は、記憶部２１０７に保存されたプリントデータに、未処理のグラフィックスオブジェクトがあるか判定し（Ｓ１６０１）、あればそのグラフィックスオブジェクトを、グラフィックス・オブジェクト単位で読み込む（Ｓ１６０２）。もし処理すべきグラフィックス・オブジェクトがないと判断した場合には、解釈処理を終了する。続いて、グラフィックス・オブジェクトの先頭のスキャン・ラインから順に着目し、着目スキャンラインが最終スキャンラインか判定する（Ｓ１６０３）。この判定はたとえばオブジェクトのパラメータに含まれる「高さ」パラメータと着目スキャンライン番号とを比較することで実現できる。
【００７０】
最後のスキャンラインでなければ、着目スキャンラインとその直前のスキャン・ラインとでそれぞれ対応するピクセルで差分があるピクセルを検索する（Ｓ１６０４）。なおステップＳ１６０４では、差分のあるピクセルのＸ方向の開始位置、及び連続して差分があるピクセル数が検索される。もし差分のあるピクセルが見つかった場合には、例えば図１７に示すフローチャートに従って、それまでに作成された差分リストを更新、もしくは新規に差分リストを作成する（Ｓ１６０５）。その後ステップＳ１６０４に戻り、グラフィックス・オブジェクトの処理中のスキャン・ライン上にある全ての差分ピクセルに対してＳ１６０５を繰り返す。ステップＳ１６０４で処理すべき差分情報がない場合には、処理中のグラフィックス・オブジェクトのスキャン・ラインを次のスキャン・ラインに進め（Ｓ１６０６）、グラフィックス・オブジェクトの全てのスキャン・ラインについて上述した処理を繰り返す。グラフィックス・オブジェクトの全てのスキャン・ラインで差分ピクセルの処理が終了すると、処理が終了したグラフィックス・オブジェクトを、後述の差分リストの更新のために、処理が終了したグラフィックス・オブジェクト・リストの最後尾に追加し（Ｓ１６０７）、ステップＳ１６０１に戻り、続くグラフィックス・オブジェクトに対して上述した処理を繰り返す。
【００７１】
続いてステップＳ１６０５にて、差分リストを更新、もしくは新規に作成する方法の一例を図１７のフローチャートを用いて説明する。まず図１６のステップＳ１６０４にて検索された差分のあるピクセルを含む差分リストがすでに記憶部２１０７に存在するかを調べる（Ｓ１７０１）。ここで見つからなかった場合には、新規に差分リストを作成し、ステップＳ１６０４にて検索された差分があるピクセル上に描画するグラフィックス・オブジェクトを、図１６のステップＳ１６０７で作成済みの処理済グラフィックス・オブジェクト・リストの先頭から検索し、差分リストのグラフィックス・オブジェクト・リスト１５０３に登録し、今回作成した差分リストを処理対象として選択する（Ｓ１７０７）。その後、今回入力されたグラフィックス・オブジェクト（着目グラフィックスオブジェクト）を差分リストのグラフィックス・オブジェクト・リストに追加し（Ｓ１７０８）、処理を終了する。
【００７２】
一方、ステップＳ１７０１にて、ステップＳ１６０４にて検索された差分のあるピクセルを含む差分リストがすでに記憶部２１０７に存在する場合には、該差分リストを処理対象として選択する（Ｓ１７０２）。続いて、選択された差分リストと、図１６のＳ１６０４にて検索された差分のあるピクセルの開始座標及び幅が等しいかを検査（判定）する（Ｓ１７０３）。等しい場合には、選択されている差分リストのグラフィックス・オブジェクト・リストの後方に今回入力されたグラフィックス・オブジェクトを追加して処理を終了する（Ｓ１７０８）。
【００７３】
ステップＳ１７０３にて、等しくないと判定された場合は、選択されている差分リストを、今回入力された差分があるピクセルを含むものと含まないものに分割し、今回の差分が含まれる差分リストを選択しなおす（Ｓ１７０４）。続いて、選択されている差分リストのグラフィックス・オブジェクト・リストの後方に今回入力されたグラフィックス・オブジェクトを追加する（Ｓ１７０５）。続いて、選択されている差分リストに記載されている位置情報が、今回入力された差分があるピクセルを完全に包含するか、すなわち選択されている差分リストの開始位置及び幅が今回入力されたそれと等しいか、を検査し（Ｓ１７０６）、等しい場合には処理を終了し、等しくない場合には、選択されている差分リストに含まれない差分があるピクセルを新規に差分リストとして登録する（Ｓ１７０７）。Ｓ１７０７以降の処理は上記にてすでに説明したとおりである。
【００７４】
図１８は、上述した差分リストの更新を良く表す図である。１８０１は既に登録されている差分の情報の一例であり、先頭から差分ピクセルの位置、その長さ、オブジェクト識別子を含む。１８０２は既登録差分情報１８０１を図示したものであり、１８０３は新規に入力される差分の情報の一例であり、１８０４は新規差分情報１８０３を図示したものである。既登録差分情報１８０１の差分の情報は、１８０５に示すような差分リストとして登録されている。新規差分情報１８０３が入力されると、新規差分情報１８０３で表現される差分があるピクセルは差分リスト１８０５の領域と一部重なっているので、差分リスト１８０５を、新規差分情報１８０３で表現される差分があるピクセルを含むものと含まないものとで２つに分割する。含まれるほうのグラフィックス・オブジェクト・リストに、新規差分情報１８０３に対応するグラフィックス・オブジェクトを追加する。すなわち、差分リスト１８０５において座標"Ｐ"から座標"Ｐ＋２"まで（すなわち位置Ｐ、長さ３）は、新規差分情報１８０３で表現される差分があるピクセルを含み、座標"Ｐ＋３"から座標"Ｐ＋６"まで（すなわち位置Ｐ＋３、長さ４）は含まないため、差分リスト１８０６に示すような、位置Ｐ、長さ３の差分ピクセルに対応する差分リストと、位置Ｐ＋３、長さ４の差分ピクセルに対応する差分リストの２つの差分リストに分割されることになる。一方、新規差分リスト１８０３で表現される差分があるピクセルにおいて、座標"Ｐ−２"から座標"Ｐ−１"までは、差分リストに含まれていない。そこで、図１８の差分リスト１８０７に示すように、含まれない差分があるピクセルを表す差分リスト（位置Ｐ−２、長さ２）を新規に作成して、差分リストに連結する。
【００７５】
以上の手順により、中間コードとして、直前のスキャンラインとの間における差分ピクセルのランとそのランに対応するオブジェクトを示すリスト（差分リスト）が、スキャンライン毎に作成される。作成された中間コードは記憶部２１０７に記録される。なお、図１９の例には記載されていないが、各差分リストはスキャンライン毎に生成されるために、差分リストがどのスキャンラインに対応するかを示す対応ライン識別子も差分リストには、例えばその先頭に含まれている。
【００７６】
＜スキャンラインの生成＞
続いて、描画部２１０４にて、バッファ２１０５に着目スキャン・ラインを形成する方法について図２０のフローチャートを用いて説明する。図２０の手順は、フレームメモリにおいて、差分リストで示されるスキャンラインに着目して処理が行われる。
【００７７】
上記で説明したように、記憶部２１０７には、スキャン・ライン毎に差分リストが記憶部２１０７に格納される。描画部２１０４は、形成するスキャン・ラインの先頭の差分リストを記憶部２１０７から読み出す（Ｓ２００１）。続いて、読み込んだ差分リストがＮＵＬＬであるか否かを検査し（Ｓ２００２）、ＮＵＬＬである場合には処理対象のスキャンライン（着目スキャンライン）には差分がないと判断し、スキャン・ラインの形成を終了する。ステップＳ２００２で差分リストがＮＵＬＬでない場合には、該差分リストで表現される差分のあるピクセルに相当するバッファ２１０５のアドレスに、白に相当する色値、例えば０ｘｆｆｆｆｆｆを書き出す（Ｓ２００３）。続いて、差分リストのグラフィックス・オブジェクト・リストの先頭のグラフィックス・オブジェクトを選択し（Ｓ２００４）、選択されているグラフィックス・オブジェクトに従って差分があるピクセルに相当するバッファ２１０５のアドレスに色値を書き出す（Ｓ２００５）。続いて、差分リストのグラフィックス・オブジェクト・リストの次のグラフィックス・オブジェクトがあるか否かを検査し（Ｓ２００８）、ある場合には次のグラフィックス・オブジェクトを選択し（Ｓ２００７）、ステップＳ２００５以降を繰り返す。ステップＳ２００８で続くグラフィックス・オブジェクトがない場合には、ステップＳ２００１に戻り上述した処理を繰り返す。なお、ステップＳ２００５にて色値を書き出す際には、グラフィックス・オブジェクト内で定義されている論理演算に従う。また、着目スキャンラインがフレームの先頭ラインの場合には、その全ピクセルが差分ピクセルであるとして差分リストに登録しておけばよい。
【００７８】
この手順によって、ライン毎にその差分リストに基づいて、差分ピクセルの位置に対応するオブジェクトのピクセルを補填することで、スキャンライン単位のレンダリングが実現できる。しかも、差分ピクセルのみの描画で十分でありレンダリング時間の短縮を図ることができる。
【００７９】
図１９は、図１の画像に対応する差分リストの一例を示す。図１の画像はにおいて、１０４は形成されるビットマップ、１０５及び１０６はビットマップ１０４上にあるグラフィックス・オブジェクトＡ，Ｂであり、オブジェクト１０６はオブジェクト１０５より奥に描画される。拡大図１０１は１０４の座標（Ｍ，Ｎ）を基準として２０ピクセル平方を拡大した図である。１０２は１０５のエッジであり、１０３は１０６のエッジである。１０１において、枠が太くなっているピクセルは、上スキャン・ラインと、それぞれ相当するピクセルで、差分があるピクセルを示す。第（Ｍ＋１０）ラインの差分リストを、符号１９０６に示す。拡大図１０１で分かるように、位置（Ｎ＋６）と位置（Ｎ＋９）においてそれぞれ１ピクセルずつ差分ピクセルとなる。そして、その２ピクセルとも、奥からオブジェクトＡ、オブジェクトＢの順で重複している。したがって、オブジェクトリストには、位置（Ｎ＋６）から１ピクセルについて、オブジェクトＡ、オブジェクトＢの順でグラフィックオブジェクトリストが生成されており、位置（Ｎ＋９）から１ピクセルについても同様である。
【００８０】
逆に、この図１９の差分リストから、位置と長さに該当するオブジェクトのピクセルがその直前のスキャンラインのドットイメージ上に書き込まれて、図１の画像が形成される。
【００８１】
なお、本実施形態においては、差分のあるピクセルに描画するグラフィックス・オブジェクトを全てグラフィックス・オブジェクト・リストに追加したが、グラフィックス・オブジェクト・リストに含まれるグラフィックス・オブジェクトの論理演算パラメータが上書を示す場合、そのグラフィックス・オブジェクトより前に連結されているグラフィックス・オブジェクトをリストから削除してもよい。
【００８２】
なお、本発明において、バッファ２０７と記憶部２０９は別のデバイスであることが望ましいが、同じデバイスであっても本発明が適用できる。
【００８３】
［実施形態４］
続いて、本発明に係る別の実施形態について説明する。なお、本実施形態において、既に説明したものについては説明を省略する。本実施形態でのプリンタ・コントローラは、実施形態３の図２１のプリンタコントローラと等しく、記憶部２１０７に保存される中間コードは、実施形態１で説明した中間コードとする。以下記憶部２１０７に中間コードが保存された状態からの動作について説明する。
【００８４】
図２２は本実施形態での画像形成方法を説明するためのフローチャートである。まず描画部２１０４は、着目スキャンラインを格納するバッファ２１０５を初期化する。また、処理中のスキャン・ラインを表すパラメータ"Ｎ"を０に初期化する（Ｓ２２０１）。続いて、記憶部２１０７に保存されている中間コードから、スキャン・ラインが"Ｎ"から始まる中間コードを検索し"リスト１"に追加する。このとき作成されるリスト１では、中間コードを描画する順番を、例えば双方向リンクリストで中間コードを描画順番で連結することにより、保つものとする。また、"Ｎ"が２以上の場合、最終のスキャン・ラインが"Ｎ−２"のグラフィックスオブジェクトの中間コードをリストから削除する（Ｓ２２０２）。これは、中間コードが表すグラフィックス・オブジェクトの最後のスキャンラインの次のスキャン・ラインで該グラフィックス・オブジェクトで描画されたピクセルを消去する必要があることに起因する。
【００８５】
続いて、"リスト１"の先頭の中間コードを記憶部２１０７に用意したパラメータ"Ｏ（オー）"に設定する（Ｓ２２０３）。たとえばパラメータＯとして"リスト１"の先頭の中間コードそのものを記録しても良いし、そこに至るポインタやインデックスを記録すればよい。続いてパラメータ"Ｏ"を検査し、中間コードが選択されているか（記録されているか）を判定する（Ｓ２２０４）。中間コードが選択されている場合、パラメータ"Ｏ"で選択されている中間コードの、着目スキャン・ライン"Ｎ"とその直前のスキャン・ライン"Ｎ−１"でそれぞれに相当するピクセルで差分があるピクセルを検索する（Ｓ２２０５）。
【００８６】
ステップＳ２２０５の検索の結果、差分のあるピクセルがあるか判定し（Ｓ２２０６）、あると判断された場合には、バッファ２１０５において、差分があるピクセルを、白に相当する色値、例えば０ｘｆｆｆｆｆｆで塗りつぶす。また、"リスト１"とは別のリストである"リスト２"を初期化し、"リスト１"から、スキャン・ライン"Ｎ"で描画される中間コードを順次検索し、"リスト２"に順次連結する。また"リスト２"の先頭の中間コードをパラメータ"Ｏ'"に設定する（Ｓ２２０７）。続いて、パラメータ"Ｏ'"に中間コードが選択されているかを検査する（Ｓ２２０８）。選択されている場合には、"Ｏ'"で選択されている中間コードに対応するオブジェクトが、ステップＳ２２０６で検索された差分があるピクセルを塗りつぶすか否かを検査する（Ｓ２２０９）。塗りつぶすと判定された場合には、パラメータ"Ｏ'"で選択されている中間コードで定義された色値で、ステップＳ２２０６で検索されたピクセルを塗りつぶし（Ｓ２２１０）、パラメータ"Ｏ'"を"リスト２"の次の中間コードに設定し（Ｓ２２１１）、ステップＳ２２０８からの処理を繰り返す。
【００８７】
一方ステップＳ２２０９にて、パラメータ"Ｏ'"で選択されている中間コードに対応するオブジェクトはステップＳ２２０６で検索された差分があるピクセルを塗りつぶさないと判定された場合には、ステップＳ２２１１に進む。
【００８８】
また、ステップＳ２２０８にてパラメータ"Ｏ'"で中間コードが選択されていない場合は、パラメータ"Ｏ"を"リスト２"の次の中間コードに設定し（Ｓ２２１２）、ステップＳ２２０４に進む。
【００８９】
また、ステップＳ２２０６にて差分のあるピクセルがないと判定された場合には、ステップＳ２２１２に進む。
【００９０】
また、ステップＳ２２０４にて"Ｏ"で中間コードが選択されていない場合には、バッファ２１０５のラスタ情報を、ＤＭＡ２１０６にて記憶部２１０７に伝送し、"Ｎ"に１を加えて、次のスキャン・ラインの処理に備える（Ｓ２２１３）。ここで、ＤＭＡ２１０６にてバッファのラスタ情報が記憶部２１０７に伝送されても、バッファ２１０５のラスタ情報は保持する。続いて"Ｎ"が形成するビットマップの最終のスキャン・ラインであるか否かを検査し（Ｓ２２１４）、最終のスキャン・ラインでない場合には、ステップＳ２２０２に進み、上述した処理を繰り返す。また、ステップＳ２２１４にて最終スキャン・ラインであると判定されると描画処理を終了する。なお、ステップＳ２２０８では、パラメータ"Ｎ"が中間コードが示すグラフィックス・オブジェクトの最後のスキャンラインの次のスキャンラインを示す場合には、最後のスキャンラインで描画されるピクセルが差分があるピクセルになる。
【００９１】
なお、本発明において、バッファ２０７と記憶部２０９は別のデバイスであることが望ましいが、同じデバイスであっても本発明が適用できる。
【００９２】
以上の手順によって、従来と互換性のある中間コードを用いて、すなわち従来の中間コードを生成するプログラムを流用しつつ、スキャンライン毎にその差分ピクセルについて描画することで、レンダリング処理の速度の向上を実現した画像形成装置を提供できる。
【００９３】
［実施形態５］
本発明に係る第５の実施形態について説明する。なお、本実施形態において、実施形態４で説明したものについては説明を省略する。
【００９４】
図２３は、本実施形態を説明するための図であり、図２３０１はプリンタ・コントローラであり、描画選択部２３０２及び第一の描画部２１０３及び第二の描画部２３０３と、記憶部２１０７と、図示しないＩ／Ｆと、解釈部と、バッファと、ＤＭＡと、画像処理部と、ビデオ転送部を具備する。なお第一の描画部２１０３及び記憶部２１０７及びＩ／Ｆ及び解釈部及びバッファ及びＤＭＡ及び画像処理部及びビデオ転送部は実施形態４で説明したものと同じであるため説明は省く。
【００９５】
本実施形態にかかる画像形成方法は、高解像度の画像の特性、すなわち連続したスキャン・ラインでそれぞれに相当するピクセルで差分が発生するピクセルは少ないこと、を利用した画像形成方法であるため、低解像度の画像に対しては効果が小さいか、もしくは従来の方式より遅くなる可能性を含んでいる。そのため、描画選択部２３０２は出力するビットマップの解像度から、第１の描画部２１０３もしくは従来の描画方式である第２の描画部２１０４を選択し、解像度に応じて描画部を選択できるようにしている。すなわち、解像度が一定解像度以上であれば第４の実施形態に係る描画部２１０３により描画処理を行い、一定解像度よりも低ければ描画部２１０４により描画処理を行う。なお、記憶部２１０７に記憶される中間コードは、実施形態２で説明したように、従来の描画方式における中間コードと互換性を保つことは既に説明した。
【００９６】
この様に構成することで、解像の高低にかかわらず高い描画性能を維持することができる。
【００９７】
なお、実施形態２乃至５について、差分の判定は実施形態１と同様に、たとえば矩形や台形、ランレングス、ビットマップ等の種類に応じて行うことができる。実施形態３では、差分の判定は従来の中間コードではなく、ホストコンピュータから受信した印刷データに基づいて行うことになるが、オブジェクトの記述は基本的に同一なので、実施形態３においても実施形態１と同様の方法で差分を判定できる。
【図面の簡単な説明】
【００９８】
【図１】グラフィックス・オブジェクトの連続するスキャン・ラインでそれぞれ対応するピクセルで差分があるピクセルの一例を示す図である。
【図２】本発明に係る第１実施形態のプリンタコントローラの概念図の一例である。
【図３】本発明に係る第１実施形態の中間コードの一例である。
【図４】図３の中間コードに含まれる情報の関係の一例を示す図である。
【図５】図３の中間コードに含まれる情報の種別の一例を示す図である。
【図６】図３の中間コードに含まれる情報の一例である。
【図７】本発明に係る第１実施形態の中間コードの一例を示す図である。
【図８Ａ】本発明の第１実施形態の画像形成処理の一例を説明するためのフローチャートである。
【図８Ｂ】本発明の第１実施形態の画像形成処理の一例を説明するためのフローチャートである。
【図８Ｃ】本発明の第１実施形態の画像形成処理の一例を説明するためのフローチャートである。
【図９】グラフィックス・オブジェクトの連続するスキャン・ラインでそれぞれ対応するピクセルで差分があるピクセルの一例を示す図である。
【図１０】本発明に係る第１実施形態の中間コードの一例を示す図である。
【図１１】グラフィックス・オブジェクトの連続するスキャン・ラインでそれぞれ対応するピクセルで差分があるピクセルの一例を示す図である。
【図１２】本発明に係るビットマップ画像の拡大を説明するための図である。
【図１３】本発明に係る第１実施形態の中間コードの一例を示す図である。
【図１４】本発明に係る第２実施形態のプリンタコントローラの概念図の一例である。
【図１５】本発明に係る第３実施形態の中間コードの一例である。
【図１６】本発明に係る第３実施形態の中間コードの一例を作成する処理を説明するためのフローチャートである。
【図１７】本発明に係る第３実施形態の中間コードを更新する処理を説明するためのフローチャートである。
【図１８】本発明に係る第３実施形態の中間コードを更新する処理を説明するための中間コードの一例である。
【図１９】第３実施形態の図１に示す差分があるピクセルを表現する中間コードの例である。
【図２０】本発明に係る第３実施形態の画像形成処理を説明するためのフローチャートである。
【図２１】本発明に係る第３実施形態のプリンタコントローラの概念図の一例である。
【図２２】本発明に係る第４実施形態の画像形成処理を説明するためのフローチャートである。
【図２３】本発明に係る第５実施形態のプリンタコントローラの概念図の一例である。
【符号の説明】
【００９９】
２０５、２１０３ 解釈部
２０６、１４０３、２１０４、２３０３ 描画部
２０７、２１０５ バッファ
２０８ 転送部
２０９、２１０７ 記憶部
１４０２ 判断部
２１０６ ＤＭＡ
２３０２ 描画選択部
【技術分野】
【０００１】
本発明は、たとえば高解像度画像等の画像特性を用いて画像形成処理を実行する画像形成装置及び画像形成方法ならびに画像形成方法を実行するプログラムに関するものである。
【背景技術】
【０００２】
従来、ページプリンタにてラスタライズ処理を実行するものとして、ペインターズ・アルゴリズム（Ｐａｉｎｔｅｒ'ｓ ａｌｏｇｏｒｉｔｈｍ）がある。ペインターズ・アルゴリズムは、描画するグラフィック・オブジェクト群の相互位置関係を予め調査し、最も奥に描画されるグラフィックス・オブジェクトからフレーム・ストアに描画する。
【０００３】
ペインターズ・アルゴリズムには２つの問題点がある。第１の問題点は、フレーム・ストア内の全ての画素へのランダムアクセスが発生する可能性があるため、予めアクセスされるフレーム・ストアの微小領域を特定することができないので、ラスタライズ処理の時間が、全てのグラフィックス・オブジェクトを構成する画素数と、フレーム・ストアが置かれるメモリの物理的な転送速度で決まる転送時間の積に制限されることである。第２の問題点は、グラフィックス・オブジェクト同士で重なりがある場合、奥のグラフィックス・オブジェクトはそれより手前のグラフィックス・オブジェクトで上塗りされるため、上塗りされた領域のラスタライズが時間的に無駄になることである。
【０００４】
ペインターズ・アルゴリズムのこの２つの問題を軽減するための一つの方法が、フレーム・ストアを帯状に分割し、グラフィックス・オブジェクトも予め帯状に分割するバンディングである。バンディングでは、予めアクセスされるメモリが、分断された帯状の領域（バンド領域）に限定されるので、例えばキャッシュ・メモリを装備することにより、フレーム・ストア全体にアクセスするのに比べて、キャッシュ・ヒットする確立を高めることが出来る。このために、全てのグラフィックス・オブジェクトを構成する画素数と、フレーム・ストアが置かれるメモリの物理的な転送速度で決まる転送時間の積に制限されることがなくなる。しかし、一般的にバンディングでは、フレーム・ストアを数個から数十個に分割するため、キャッシュ・ヒット率を劇的に改善するには至らない。また、やはり上書の問題は依然こうむる。
【０００５】
一方ペインターズ・アルゴリズムの問題であるオブジェクトの上書を発生させない方法（これを第２の方法と呼ぶ。）も考案されている。そのような方法の一例には、以下の手順でオブジェクトのレンダリングが行われる。フレーム・ストアに形成される画像はラスタ走査順で作られる。各ラスタラインと各オブジェクトの交点の座標が求められる。その交点座標の間の各画素について、当該ラインに含まれるグラフィクスオブジェクトのレベル（重なり合うグラフィックス・オブジェクトの奥行き方向の相互位置関係を示す情報）と、グラフィクスオブジェクトの色の情報とに基づいて、描画すべきオブジェクトが判定され、判定の結果決定されたオブジェクトに対応する色で交点間が描画される。これをライン毎にグラフィクスオブジェクトとの交点を更新しつつ行う（特開２０００−１３７８２５号公報参照）。
【特許文献１】特開２０００−１３７８２５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来の技術は高解像度の画像特性を生かしたものではない。すなわち、高解像度画像では、画像中の任意の画素とその近傍の画素とでは同じ色値になる可能性が高い（この性質を空間的局所性と呼ぶ）。これは画像に含まれるオブジェクトが一定の広がりを持っているためであり、高解像度になればひとつのオブジェクトを構成する画素数が増加するために、より空間的局所性が強く表れるためである。このため任意のフレーム・ストア中の任意のラインの任意の画素と、それに続くライン中の対応する画素（すなわちラインの端からの位置が同一の画素）は同じ色値をもつ可能性が高い。従来の方法では、ライン毎に独立した処理を行っているため、たとえ連続するラインで、色値に差分がある画素が小数、もしくはない場合でも、色値に差分のない画素に対しても前のラインで行った処理を繰り返す必要があり、時間的な無駄が発生していた。
【０００７】
また、上述したペインターズアルゴリズムではフレーム・ストアへのアクセスがランダムになり、第２の方法ではアクセスはシーケンシャルになる。フレーム・ストアへのアクセスがランダムな場合、従来の技術ではアクセスされる可能性がある画素がフレーム・ストア全体、もしくはバンド領域になるため、メモリキャッシュの効果は望めないか、あるいは効果は低い。一方、第２の方法では、描画前に重なり合うグラフィックス・オブジェクトの奥行き方向の相互位置関係から、フレーム・ストアに転送する色値を判定する必要がある。この判定処理は負荷が高く、また、フレーム・ストアの任意の画素は一度のみアクセスされるので、メモリキャッシュは本質的に意味をなさない。このためメモリキャッシュを有効的に利用することが出来ないという問題があった。
【０００８】
本発明は上記従来例に鑑みてなされたもので、オブジェクトで構成された画像を形成する際に、直前のラインにおいて対応する画素の値が同一の場合には当該画素を描画せずに直前のラインにおける画素値を用い、同一ではない画素について新たに画素値を生成することで、高速に画像形成処理を行う画像形成装置および方法を提供することを目的とする。
【０００９】
さらに、フレーム・ストアへのアクセスの局所性が顕著になり、キャッシュを有効的に利用でき、高速に画像形成処理を行う画像形成装置および方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述目的を達成するために本発明は以下の構成を有する。
【００１１】
フレームメモリにグラフィックスオブジェクトを描画する画像形成装置であって、
グラフィックスオブジェクトのスキャンラインごとのドットイメージデータを保存するラインメモリと、
前記ラインメモリに保存されたスキャンラインとその直後の着目スキャンラインにおいて対応する画素の値が異なる差分画素の位置を決定する決定手段と、
前記ラインメモリに保存されたドットイメージデータのうち、前記決定手段により決定された差分画素の値を、前記着目ラインにおける画素の値に更新する差分更新手段と、
前記ラインメモリのドットイメージデータを、前記着目スキャンラインに相当する前記フレームメモリの位置に合成する合成手段とを備える。
【発明の効果】
【００１２】
本発明によれば、グラフィクスオブジェクトで構成された画像をラスタライズする際に、直前のラインにおいて対応する画素の値が同一の場合には当該ピクセルを描画せずに直前のラインにおける画素値を用い、同一ではない画素について新たに画素値を生成することで、高速に画像形成処理を行うことができる。
【００１３】
さらに、グラフィクスオブジェクトのラスタライズの際に、ドットイメージデータを格納したメモリへのアクセスの局所性が顕著になり、キャッシュを有効的に利用でき、高速に画像形成処理を行うことができる。
【発明を実施するための最良の形態】
【００１４】
［実施形態１］
＜画像形成装置の構成＞
本発明の一実施形態について図を用いて説明する。図２は本実施形態にかかる画像形成装置としてのプリンタの構成を概略的に表す図である。図２のホストコンピュータ２０１は、プリンタドライバ２０２を備えている。プリンタコントローラ２０３は、Ｉ／Ｆ２０４と、解釈部２０５と、描画部２０６と、バッファ２０７と、転送部２０８と、記憶部２０９と、ビデオ転送部２１０と、画像処理部２１１と、論理演算部２１２を備え、プリンタエンジン２１３と一体となってプリンタを構成する。Ｉ／Ｆ２０４は、上記プリンタドライバ２０２と接続され、記憶部２０９は、Ｉ／Ｆ２０４と解釈部２０５と描画部２０６とＤＭＡ２０８とビデオ転送部２１０と画像処理部２１１と接続され、バッファ２０７は、描画部２０６と転送部２０８と接続され、転送部２０８は論理演算部２１２と接続され、また描画部２０６と論理演算部２１２と接続されている。図２のプリンタエンジン２１３は、上記ビデオ転送部２１０と接続されている。なお、解釈部２０５、描画部２０６、画像処理部２１１、論理演算部２１２は、プリンタコントローラ２０３の有するＣＰＵにより所定のプログラムを実行することで実現できる。
【００１５】
また、バッファ２０７には、本実施形態では、グラフィックオブジェクトをラスタライズする際に使用されるラインメモリ（ラインバッファ）が含まれる。記憶部２０９には、１ページ分のイメージデータを保存するためのフレームメモリ（フレームバッファ）とが含まれる。なお、フレームメモリは、バンディングを行う際には、バンド単位のイメージデータを格納するために使用され、複数のバンドに相当するメモリ領域が確保される、また、ページ単位でイメージデータを保持することもできる。ラインメモリとフレームメモリは別々のメモリデバイスとして提供されるのが望ましいが、同一のメモリに設けられても良い。
【００１６】
ホストコンピュータ２０１上では図示しない様々なアプリケーションソフトウェアが動作する。これらのアプリケーションは、印刷が指示されると、印刷するビットマップ画像を生成するに必要な情報をプリンタドライバ２０２に供給する。プリンタドライバ２０２では、受信した画像を形成するに必要な情報をプリントデータ、例えばＰＤＬデータに変換し、プリンタコントローラ２０３に備えられたＩ／Ｆ２０４に伝送する。
【００１７】
プリンタコントローラから伝送されたプリントデータは、記憶部２０９、例えばメモリ、に一旦保持される。解釈部２０５は、記憶部２０９に保持されたプリントデータの解釈を行い、描画部２０６が解釈可能な中間コードに変換し、この中間コードを再び記憶部２０９に格納する。中間コードの詳細は図３を参照して後述する。描画部２０５は、記憶部２０９に保持された中間コードを読み出し、図８Ａ〜８Ｃ等を参照して後述する方法で、最終的に紙面に出力するビットマップ画像（ドットイメージデータ）の一部を生成し、これをバッファ２０７に格納する。転送部２０８は、バッファに格納されビットマップ画像の一部を論理演算部２１２に伝送する。ここで注意すべきは、バッファ２０７に格納されたビットマップ画像の一部は、転送部２０８により転送されても、バッファ２０７の内容は保持されることである。論理演算部２１２は、伝送されたビットマップ画像の一部を、描画部２０６の指示に従い、必要に応じて記憶部２０９に格納されたビットマップ画像を参照して論理演算を行い、記憶部２０９にビットマップ画像を転送する。
【００１８】
上述の処理を繰り返すことによって、記憶部２０９に紙面一面分の画像が形成されると、画像処理部２１１は、記憶部２０８に格納された紙面一面分の画像（１ページ分の画像）に対して、例えばディザ処理等を行い、再び記憶部２０９に格納する。ビデオ転送部２１０は、記憶部２０９に蓄えられた紙面一面分の画像処理されたビットマップ画像を、プリンタエンジン２１２に伝送する。プリンタエンジン２１２は、伝送されたビットマップ画像に従いを記憶媒体、例えば紙、にプリントする。なお、本実施形態においてはバッファ２０７に形成されるビットマップは、１ピクセル（画素とも言う。）あたりそれぞれ８ビットのＲ、Ｇ、Ｂの色値から構成されるものとする。
【００１９】
＜中間コード＞
続いて解釈部２０５で生成される中間コードについて説明する。中間コードは少なくとも一つ以上のグラフィックス・オブジェクトを保持し、これらを複数持つことにより様々な図形が最終的に記憶媒体に出力されるビットマップを表現する。図３は解釈部２０５にて生成される中間コードに含まれるグラフィックス・オブジェクトのデータ構造の一例である。３０２は位置情報であり、グラフィックス・オブジェクトが描画されるビットマップ上での位置を表す。３０３はＡｒｅａ（エリア）情報であり、主にクリップ領域や単純矩形を表す。３０４はＭａｓｋ（マスク）情報であり、主にグラフィックス・オブジェクトの形状をあらわす。３０５はＢＧ（バックグラウンド）情報であり、主に塗りつぶしパターンを表す。３０６はＧｒａｙ（グレイ）情報であり、主に塗りつぶされる色やラスタ情報を表す。３０１は、Ａｒｅａ情報及びＭａｓｋ情報及びＢＧ情報及びＧｒａｙ情報等（これらをまとめて部らフィックスオブジェクトの要素情報と呼ぶ。）に基づいて描画されるグラフィックスオブジェクトと、グラフィックス・オブジェクトが描画されるディスティネーションとの論理演算を行うためのパラメータである。なおグラフィックス・オブジェクトの形状によっては、これら全ての要素情報が必要ない場合もあるが、その場合には、例えばグラフィックス・オブジェクトに含まれる情報を別に持つことで、必要ない情報をもたないようなデータ構造にしても良いし、必要ない情報についてはＮＵＬＬ値を持つようにしても良い。
【００２０】
図４は図３で説明したグラフィックス・オブジェクトの各要素情報の関係の一例を示す図である。グラフィックス・オブジェクトが紙面に描画される位置及び範囲は、位置情報３０２及びＡｒｅａ情報３０３で決定される。上述のように決定された位置及び範囲内で塗りつぶされる候補のピクセルはＭａｓｋ情報３０４で求まり、上述のように決定された塗りつぶされる候補のピクセルはＢＧ情報３０５によって塗りつぶされないピクセルがマスクされ、最終的に塗りつぶされるピクセルが決定する。上述のように決定された塗りつぶされるピクセルの色値は、Ｇｒａｙ情報３０６によって決定される。なお、図４ではＧｒａｙ情報が単色である場合を図示しているが、Ｇｒａｙ情報がラスタの場合（すなわち単色ではない場合）には、上述のように決定された最終的に塗りつぶされるピクセルに相当するＧｒａｙ情報３０６の色値をディスティネーションに書き込むことで、Ｇｒａｙ情報３０６がラスタの場合にも対応できる。なおこれら全てが必ず必要というわけではない。位置と範囲を定義するための位置情報３０２及びＡｒｅａ情報３０３と、色を定義するためのＧｒａｙ情報３０６またはＢＧ情報３０５だけでもグラフィックスオブジェクトを定義することができる。
【００２１】
図５は、図３の各情報が持ちうるデータの例を示した表であり、Ａｒｅａ情報は矩形もしくはトラペゾイド（台形）もしくはランレングスもしくは二値ビットマップとして表現され、Ｍａｓｋ情報は矩形もしくはトラペゾイドもしくはランレングスもしくは二値ビットマップとして表現し、ＢＧ情報はパターンもしくは単色もしくはイメージとして表現し、Ｇｒａｙ情報はパターンもしくは単色もしくはイメージとして表現することを表す。
【００２２】
図６は、図３で説明したグラフィックス・オブジェクトを構成する各要素情報のデータ構造の一例を示した図である。図５に従うと、Ａｒｅａ情報３０３及びＭａｓｋ情報３０４はコード６０１のような構造になる。コード６０１は、Ａｒｅａ情報３０４及びＭａｓｋ情報３０４が、位置情報３０２からのオフセットのＸ座標を示すオフセットＸと、位置情報３０２からのオフセットのＹ座標を示すオフセットＹと、描画するグラフィックス・オブジェクトの形状に適したデータ形式６０２のうちの一つから構成されていることを表す。また、ＢＧ情報５０３及びＧｒａｙ情報５０４は、コード６０３のような構造になる。コード６０３は、ＢＧ情報５０３及びＧｒａｙ情報５０４が、位置情報３０２からのオフセットのＸ座標を示すオフセットＸと、位置情報３０２からのオフセットのＹ座標を示すオフセットＹと、描画するグラフィックス・オブジェクトの形状に適したデータ形式６０４のうちの一つから構成されていることを表す。なお、二値ビットマップ６０２ｄ、及びパターン６０４ａ、及びイメージ６０４ｄの実データ、すなわちビットマップもしくは圧縮コードはグラフィックス・オブジェクトの内部に格納されている必要はない。中間コード自体にはそれを指し示すポインタやＩＤが含まれ、実データはグラフィックス・オブジェクトの外部に保持されていても良い。各要素情報が何を表しているかは、たとえば識別コードにより示される。たとえば、「矩形」や「トラペゾイド」「ランレングス」「二値ビットマップ」それぞれにコードが割り当てられており、それがＡｒｅａ情報やＭａｓｋ情報の所定の位置に埋め込まれていれば、内容を識別可能である。
【００２３】
図６に示した個々のパラメータについて説明する。矩形６０２ａは幅と高さをパラメータとして有し、幅はスキャンライン方向、高さはそれに直交する方向についての長さを示す情報である。トラペゾイド６０２ｂは、高さと左開始位置と右開始位置と左スロープと、右スロープとをパラメータとして有する。左開始位置は、上辺の左端の位置を、位置情報５０１で定義された位置からオフセットＸ，Ｙずらした位置を基点として、Ｘ方向（スキャンライン方向）へのオフセットで表す。右開始位置は、上辺の右端の位置を同様に表す。左スロープは、左辺の傾きを、隣接するスキャンライン間における左辺相当のピクセルのずれ量をピクセル数で表した値とも考えることができる。右スロープも右辺について同様である。
【００２４】
ランレングス６０２ｃは、高さと、左位置及びランの繰返しをパラメータとして有する。高さは最終的にレンダリングされるオブジェクトの高さ（例えばライン数）を表している。レンダリングされるパターンは、各ラインにおける左位置と、その左位置を基点とするランとで構成される。本実施形態では、ランは１ラインに１つとしている。したがって、２組目以降の左位置及びランの組は、２ライン目以降にそれぞれ相当する。
【００２５】
二値ビットマップ６０２では、横方向の拡大率Ｘ、縦方向の拡大率Ｙ、オフセットＸ，Ｙ、二値ビットマップ（または圧縮コード）をパラメータとして有する。拡大率は各方向について、二値ビットマップを拡大する率を示す。
【００２６】
パターン６０４ａおよびイメージ６０４ｃは、二値ビットマップ６０２ｄと同様のパラメータを有する。単色６０４ｂは、色を示す値のみを有する。
【００２７】
図７は、上述したグラフィックス・オブジェクトの簡単な例である。７０２はグラフィックス・オブジェクトを表す中間コードであり、７０１は中間コード７０２によって描画されるビットマップ画像である。本例のグラフィックス・オブジェクトは、Ａｒｅａ情報とＧｒａｙ情報とでグラフィックス・オブジェクトの形状および色を指定できるので、図７の例では未使用のＭａｓｋ情報及びＢＧ情報にはＮＵＬＬが指定されている。また、このグラフィックス・オブジェクトを表すためにＡｒｅａ情報６０１をトラペゾイド６０２ｂにしている。また、本例のグラフィックス・オブジェクトは、色値０ｘ００００００によって塗りつぶされるため、Ｇｒａｙ情報６０４ｂとして０ｘ００００００を指定している。また本例では、ディスティネーションに上書をするので、ＲＯＰ情報としてディスティネーションへの上書を示す"Ｓ"を指定している。
【００２８】
図７の例では、グラフィックスオブジェクトの中間コード７０２には、位置情報として（１０，３０）、Ａｒｅａ情報として「トラペゾイド」、Ｇｒａｙ情報として単色が指定されている。Ｍａｓｋ情報とＢＧ情報はともにＮＵＬＬであり、未使用である。トラペゾイド６０２ｂのパラメータは、先頭の２つの"０"はオフセットであり、形状自体は「２０，１０，１０，−１／２，１／２」で表される。先頭から、高さ、左開始位置、右開始位置、左スロープ、右スロープとなる。左開始位置、右開始位置は、位置情報５０１で示される位置からのＸ方向についての相対位置である。図７ではともに１０であり、いずれも開始位置（１０，３０）をＸ方向について１０加算した位置（２０，３０）となって一致する。左スロープ、右スロープは、それぞれ台形の左辺と右辺の傾きを、１ラインでずれるピクセルの数で示す。図７では左スロープは−１／２であり、あるスキャンラインにおける左辺に相当するピクセル位置に対して、その直下のスキャンラインでは、左辺の位置は左に２分の１ピクセルずれることを示している（符号は方向を示す）。右辺も同様であるが、符号が＋であるので、ずれの方向は右方向となる。実際にこの台形（左開始点と右開始点とが一致しているので三角形となる。）をレンダリングする際には、２分の１ピクセルのずれは表現できないので、２スキャンライン毎に１ピクセルずつ左あるいは右に左辺あるいは右辺の位置をずらすことになる。図７のグラフィックスオブジェクト７０１はレンダリングされた例を示している。
【００２９】
＜描画部２０６の動作（図８Ａ−図８Ｃ）＞
図８Ａ−図８Ｃは、描画部２０６の動作を説明するフローチャートである。本例では、バッファ２０７はオブジェクトをラスタライズしたビットマップデータをスキャンライン単位で格納する。そのため、相異なるスキャンラインについても、対応する位置のピクセルは同じメモリロケーションに格納される。たとえば、画像上で同一のカラムに属するピクセルは、バッファ２０７においては同一のロケーション（すなわち同一アドレスのセル）に格納される。また、上述した中間コードは、たとえば１ページごとに記憶部２０９に格納されている。
【００３０】
図８Ａ（ａ）において、描画部２０６は、処理対象となっているページに含まれる未処理のグラフィックスオブジェクトの有無を判定する（Ｓ８１１）。未処理のグラフィックスオブジェクトがあれば、グラフィックス・オブジェクト単位で記憶部２０９から中間コードを読み出す（Ｓ８１２）。描画部２０６は、読み出したグラフィックスオブジェクト（着目グラフィクスオブジェクト）をラスタライズ（展開）して、展開されたビットマップデータをバッファ２０７に格納する（Ｓ８１３）。バッファ２０７に格納されたグラフィックス・オブジェクトの１スキャン・ラインは、転送部２０８により読み出され、論理演算部２１２に転送される。論理演算部２１２では、図８のＳ８０２にて設定された情報に従い、必要であれば記憶部２０９から、転送部２０８から転送されたスキャン・ラインを格納するアドレスに既に保持されている、上記スキャン・ラインに相当する色値を読み出し、論理演算を施し、記憶部２０９に格納する。すなわち、ラスタライズされたビットマップデータはＲＯＰ情報に従って記憶部２０９のフレームバッファに合成される（Ｓ８１４）。
【００３１】
ステップＳ８１２で読み込んだグラフィックスオブジェクトの展開を終えたか判定し（Ｓ８１５）、終えていないならステップＳ８１３に戻って展開処理を続ける。すなわち、転送部２０８により、バッファ２０７のスキャン・ラインが読み出されると、描画部２０６は続くスキャン・ラインを上述した方法でバッファ２０７に形成する。上述した処理をグラフィックス・オブジェクトのすべてのスキャン・ラインに対して行うことで、記憶部２０９にグラフィックス・オブジェクトのビットマップが形成される。着目グラフィクスオブジェクトの展開を終えたならステップＳ８１１に戻る。
【００３２】
図８Ａ（ｂ）にステップＳ８１３の詳細を示す。描画部２０６は、まずバッファ２０７に描画するスキャン・ラインが、読み出されたグラフィックス・オブジェクトの最初のスキャン・ラインか否か検査する（Ｓ８０１）。最初のスキャン・ラインである場合には、論理描画部２１２が転送部２０８から受信したビットマップ画像を記憶部２０９に伝送するための情報、本実施形態においてはアドレスや論理演算パラメータを論理描画部に設定する（Ｓ８０２）。このほか、ステップＳ８０４で参照する変数パラメータ等の初期化もここで行う。たとえば、後述するスキャンライン番号や差分バッファなどの初期化や、グラフィックオブジェクトがトラペゾイドの場合に参照される左エッジ座標、右エッジ座標変数等である。左エッジ座標、右エッジ座標は、トラペゾイドのパラメータの左開始点、右開始点に相当する値に初期化される。
【００３３】
続いてバッファ２０７にグラフィックス・オブジェクトの最初のスキャン・ラインを構成する全てのピクセルを出力する（Ｓ８０３）。ステップＳ８０１にて最初のスキャン・ラインではないと判断された場合には、直前にバッファ２０７に出力したスキャン・ラインと、今回出力するスキャン・ライン（着目スキャンライン）で、互いに相当するピクセル（同位置にあるピクセル）のうち差分があるピクセルを求める（Ｓ８０４）。続いてステップＳ８０４にて求められた差分があるピクセルについてその値を出力する（Ｓ８０５）。ここで、バッファ２０７には、着目スキャン・ラインの直前のスキャン・ラインのラスタ情報（ドットイメージデータ）が残っている。そのため、差分のあるピクセルのみを出力するだけで、着目スキャン・ラインの完全なラスタ情報がバッファ２０７に保持される。ピクセル値は、Ｇｒａｙ情報やＢＧ情報で与えられる値である。本実施形態では、Ｇｒａｙ情報やＢＧ情報がイメージやパターンの場合には、１ラインの全画素が差分ピクセルとされるために、この場合は実質的にはステップＳ８０３と同じ処理となる。したがって差分のあるピクセルのみを出力するのは、Ｇｒａｙ情報やＢＧ情報が単色の場合であるから、出力される値はＧｒａｙ情報やＢＧ情報で与えられる値そのものでよい。
【００３４】
以上説明したように、描画部２０６は中間コードからビットマップ画像の一部、本実施形態においてはグラフィックス・オブジェクトの１スキャン・ライン、を生成する。
【００３５】
図８Ｂ−図８Ｃは、ステップＳ８０４の詳細を示すフローチャートである。実行主体は描画部２０６である。なおこのフローチャートでは差分バッファなるメモリ領域を用いている。差分バッファは記憶部２０９に設けられた領域で、差分ピクセルがあればその位置を示す情報を、なければその旨を示す情報を保存するために使用される。着目スキャンラインの番号（先頭を０とする）は、記憶部２０９などに保存されて参照される。これを着目スキャンライン番号と呼ぶことにし、以下の説明でも必要に応じて参照する。
【００３６】
まず、Ｇｒａｙ情報５０４およびＢＧ情報５０３がいずれもＮＵＬＬではなく、かつ、いずれも単色であるか判定する（Ｓ８２３）。ＮＵＬＬではなくしかも単色でなければ、パターンかイメージである。これらは、色値の分布がパターンあるいはイメージで定義されている情報であって、隣接するライン間の対応するピクセル同士を比較しなければ差分ピクセルを決定できない。そこで、Ｇｒａｙ情報５０４およびＢＧ情報５０３がともに単色でなければ、ステップＳ８２７で、差分バッファに、注目ラインの全ピクセルを記録する（たとえば全ピクセルが差分ピクセルであることを示す情報を記録すればよい）。なお、Ｇｒａｙ情報５０４またはＢＧ情報５０３の値のいずれかが未定義（ＮＵＬＬ）の場合には、ＮＵＬＬではない方の情報に限って判断の対象とする。
【００３７】
ステップＳ８２３でＹＥＳと判定された場合には、Ｇｒａｙ情報５０４およびＢＧ情報５０３は、ＮＵＬＬか単色かのいずれかである。その場合には、Ｍａｓｋ情報５０２があるか、すなわちＮＵＬＬではないか判定する（Ｓ８２４）。Ｍａｓｋ情報５０２がＮＵＬＬであれば、Ａｒｅａ情報５０１が「矩形」６０２ａであるか判定する（Ｓ８２５）。ステップＳ８２５において「矩形」６０２ａと判定された場合には、差分バッファに差分ピクセルはない旨を記録する（Ｓ８２８）。これは、矩形では最初のラインから最終ラインまで描かれるピクセルは同一であるからである。なお、本実施の形態では、オフセットが０の場合を説明したので、差分を計算する必要がないが、たとえばオフセットＹ＝１、高さ３の矩形を描画する場合は、スキャンラインが０から始まるとすると、１ライン（矩形の上辺）と４ライン（矩形の底辺の次のライン）とに差分が発生し、上辺や底辺の部分を差分ピクセル位置とする。
【００３８】
一方、ステップＳ８２５においてＡｒｅａ情報５０１は矩形ではないと判定された場合、Ａｒｅａ情報５０１が「トラペゾイド」（台形）６０２ｂであるか判定する（Ｓ８２９）トラペゾイドであれば、ステップＳ８０２で初期化された左エッジ座標変数、右エッジ座標変数に、左スロープおよび右スロープの値をそれぞれ加算する（Ｓ８３１）。そして左エッジ座標変数と右エッジ座標変数それぞれの整数部に値の変化があったか判定する（Ｓ８３２）。このためにはステップＳ８３１で加算する直前の値を一時的に記憶しておけばよい。いずれかに変化があったなら、着目スキャンラインとその直前のスキャンラインとの間で、レンダリングされるべきピクセルが変化したということなので、それら変数の整数部に相当する位置を、差分バッファに差分ピクセルの位置として記録する（Ｓ８３３）。いずれも変化しなければエッジの位置に変化はないとして、ステップＳ８２８に分岐する。なお、前記変数の変化が増加であるか、減少であるかにより差分ピクセルの位置は異なる。増加の場合には、増加後の値それぞれが差分ピクセルに相当する。たとえば５から７に増加すれば、増加後の６，７が差分ピクセルである。減少の場合には、減少前の値が差分ピクセルに相当する。たとえば７から５に減少すれば、減少前の６，７が差分ピクセルである。このようにして差分ピクセルの位置が決定される。
【００３９】
一方ステップＳ８２９においてＡｒｅａ情報がトラペゾイドではないと判定された場合には、Ａｒｅａ情報がランレングスであるか判定する（Ｓ８３４）。ランレングスであれば、着目スキャンラインと直前のスキャンラインとのランの開始位置（左位置）および終了位置（左位置とランの長さとから決定される。）の位置のずれに基づいて、ずれた位置（ずれた分の全て）が差分ピクセルの位置として差分バッファに記録される（Ｓ８３５）。なお、本実施の形態では、オフセットが０の場合を説明したが、たとえばオフセットＹ＝１、高さ３の台形を描画する場合は、スキャンラインが０から始まるとすると、１ライン（台形の上辺）と４ライン（台形の底辺の次のライン）とに差分が発生し、上辺や底辺の部分を差分ピクセル位置とする。
【００４０】
ステップＳ８３４でランレングスではないと判定された場合、オブジェクトは二値ビットマップである。その場合、拡大率Ｙのパラメータを参照して、２以上の変倍率が指定されているか判定する（Ｓ８３６）。指定されていなければステップＳ８２７に分岐して、差分バッファに全画素を差分ピクセルとする旨の情報を記録する。２倍以上の変倍率が指定されていれば、着目スキャンラインが複製されるラインであるか判定する（Ｓ８３７）。たとえば拡大率が２倍であれば、偶数番目のラインはその直前のラインの複製となる。その場合にはステップＳ８２８に分岐して、差分ピクセルはないことを示す情報を差分バッファに保存する（Ｓ８２８）。複製ラインでなければ、着目スキャンラインのビットマップと、その直前のスキャンラインのビットマップの差分ピクセルを決定する（Ｓ８３８）。差分ピクセルは、着目スキャンラインのビットマップ（二値ビットマップのパラメータから獲得する。）と、その直前のスキャンライン（バッファ２０７に保存されている。）との排他的論理和を計算し、結果が０以外のピクセルが差分ピクセルである。もちろん計算はピクセルの位置を対応付けて行われる。差分ピクセルの位置が差分バッファに記録される。なお、このときＡｒｅａ情報を拡大してから差分を検査しなくともよい。例えばバッファ２０７の値を用いずに、Ａｒｅａ情報の二値ビットマップの連続するスキャン・ラインを表す数値で排他的論理和を取り、この計算結果を拡大率で乗じ、この結果ビットがＯＮになっている箇所に相当するピクセルが差分があるピクセルと判定することもできる。
【００４１】
ステップＳ８３７での複製ラインか否かの判定は、拡大率Ｙを変数Ｎとし、着目グラフィックオブジェクトにおける着目スキャンライン番号を変数ｎ（先頭ラインを０とする。）であるとした場合、以下のように行える。すなわち、スキャンライン番号ｎの拡大率Ｎを法とする剰余が０であるかを判定し、０でなければ複製ラインと判定することができる。これは、縦方向の拡大はラインの複製により実現されるからである。
【００４２】
さて、ステップＳ８２５〜ステップＳ８３７まではステップＳ８２４においてＭａｓｋ情報があると判定された場合には、図８Ｃに示すステップＳ８４１に分岐する。ステップＳ８４１〜Ｓ８５４までは、図８ＢのステップＳ８２５〜Ｓ８３８までと、Ａｒｅａ情報をＭａｓｋ情報に置き換えた点を除いてそれぞれ同一の処理を行っている。そこでそれぞれの説明は省略する。図８Ｃでは、その最後に、ステップＳ８５５で、Ａｒｅａ情報で定義される領域の外部に相当する位置の差分ピクセルを差分バッファから削除する。これは、Ｍａｓｋ情報で定義される領域内であっても、Ａｒｅａ情報で定義される領域外となるピクセルも存在し得るためである。
【００４３】
＜レンダリングの具体例１＞
続いて具体例を挙げて本実施形態の画像形成装置を説明する。本例においては、図７で示したグラフィックス・オブジェクトを表す中間コードが記憶部２０９に格納され、このグラフィックス・オブジェクトを描画部２０６にて描画する際の動作について詳細に説明する。
【００４４】
描画部２０６は、記憶部２０９に格納されたグラフィックス・オブジェクトを表す中間コードを読み込む。描画部２０６は、中間コードに記載されているＲＯＰ情報３０１及び位置情報３０２を読み出し、更に読み出された中間コードにＡｒｅａ情報３０３及びＭａｓｋ情報３０４及びＢＧ情報３０５及びＧｒａｙ情報３０６が設定されているか、すなわちＮＵＬＬ値ではないか、を検査する。この結果と中間コードに記載されているＲＯＰ情報３０１から、ディスティネーションとの論理演算パラメータを決定し、上述のように決定されたディスティネーションとの論理演算パラメータと、位置情報３０２を、論理演算部２１２に転送する。
【００４５】
続いて、描画部２０６は、ＮＵＬＬ値ではない中間コードに記載されている情報をもとに、グラフィックス・オブジェクトの最初のスキャン・ラインをバッファ２０７に書き出す。このときバッファ２０７に書き出すスキャン・ラインは、バッファ２０７の先頭から、後述する論理演算部２１２にて計算される記憶部２０９のアドレスに転送したときに、スキャン・ラインが正しく記憶部２０９に転送されるように形成される。本例においては、Ｍａｓｋ情報及びＢＧ情報がＮＵＬＬであるため、Ａｒｅａ情報から、トラペゾイドを構成する右エッジのＸ座標と左エッジのＸ座標を計算し、また、グラフィックス・オブジェクトの右エッジで最大となるＸ座標を計算して、ラスタ情報を、Ｇｒａｙ情報、すなわち単色（本例では０ｘ００００００）、に従ってバッファ２０７に書き出す。すなわち、本例では、右エッジの最大のＸ座標は２０となり、最初のスキャン・ラインでの左エッジのＸ座標は１０となり、右エッジのＸ座標は１０となるため、バッファ２０７の０から９及１１から１９は白に相当する色値、例えば０ｘｆｆｆｆｆｆ書き出し、バッファ２０７の１０には０ｘ００００００を書き出す。なお、本例においては、トラペゾイドの右エッジ座標の最大値を描画部２０６にて計算するようにしているが、中間コード中に予めグラフィックス・オブジェクトの最小及び最大の座標を記載しておいても良い。
【００４６】
続いて、転送部２０８は、バッファ２０７に書き出されたサイズに相当するラスタを読み出し、論理演算部２１２に転送する。論理演算部２１１は、描画部２０６から予め転送された論理演算パラメータを調査（すなわちどの論理演算パラメータであるか判別）し、記憶部２０９に既に格納されているラスタ情報を読み出す必要があるか否かを検査する。上記判断で、ラスタ情報（ビットマップの列）を読み出すと判断された場合には、描画部２０６から予め転送されていた位置情報から、ラスタ情報を読み出す記憶部２０９のアドレスを求め、該アドレスからラスタ情報を読み出し、これと、転送部２０８から転送されたラスタ情報を論理演算し、上記アドレスに、論理演算した結果のラスタ情報を格納する。たとえば記憶部２０９において、紙面一面の（１ページの）ビットマップを保持する場合には、フレーム・バッファが記憶部２０９に保持されることになる。その場合、上記ラスタ情報を読み出す記憶部２０９のアドレスは、フレーム・バッファの先頭アドレスに位置情報を加算することで計算される。また、記憶部２０９において、紙面を帯状に分割したバンドのビットマップを保持する場合には、バンド・バッファが記憶部２０９に保持されることになる。その場合には、バンド・バッファの先頭アドレスに、位置情報を加算することで上記アドレスを求めることができる。本例においては、論理演算パラメータとして"Ｓ"を指定しているので、記憶部２０９から既に格納されているラスタ情報を読み出す必要がなく、転送部２０８から転送されたラスタ情報を、記憶部２０９の上記アドレスに転送する。
【００４７】
記憶部２０９への格納が終了すると、論理演算部２１２は、続くスキャン・ラインの転送に備えて、上述したアドレスを更新する。転送部２０８によるバッファ２０７からラスタを読み出しが完了すると、描画部２０６は続くスキャン・ラインをバッファ２０７に形成するが、このとき描画部２０６は、前のスキャン・ラインと続くスキャン・ラインのそれぞれ相当するピクセルで差分があるピクセルのみの更新を行う（図８Ｂ，８Ｃ参照）。すなわち、中間コードに格納されている全ての情報について、前のスキャン・ラインと続くスキャン・ラインのそれぞれ対応するピクセルに相当するピクセルで、差分があるピクセルを決定し、上記のように決定されたピクセルに相当するバッファ２０７に格納されたピクセルを塗りつぶす。本例においては、前のスキャン・ラインと続くスキャン・ラインのそれぞれ相当するピクセルで、差分がある情報はＡｒｅａ情報のみである。Ａｒｅａ情報の差分があるピクセルは、前のスキャン・ラインでの右エッジ座標と左エッジ座標と、右スロープと左スロープから判断する。本例において、エッジ座標がピクセルをまたぐ場合には、左エッジについては、エッジ座標がピクセルの中心座標より小さい場合には、概ピクセルはグラフィックス・オブジェクトの内側にあるように判断してピクセル生成を行う。右エッジについては、エッジの座標がピクセルの中心座標を超える場合に、概ピクセルはグラフィックス・オブジェクトの内側にあるようにピクセル生成を行う。そのため、第二スキャン・ラインでの左エッジ座標は１０、右エッジ座標は１０となり、差分があるピクセルがない。そのため、バッファ２０７は前スキャン・ラインのラスタ情報を保持したままとなり、このラスタ情報が転送部２０７に転送され、上述した最初のスキャン・ラインと同様に、論理演算部２１２に転送された後、記憶部２０９に格納される。
【００４８】
続いて第三のスキャン・ラインを、上述した方法と同様に、バッファ２０７に形成する。本例では、第三スキャン・ラインでの左エッジ座標と右エッジ座標はそれぞれ、９、１１となる。第二のスキャン・ラインと第三のスキャン・ラインのそれぞれ相当するピクセルで、バッファ２０７での座標９と座標１１のピクセルに差分が発生する。よって描画部２０６は、左から９番目と１１番目のピクセルを、まず白に相当する色値、例えば０ｘｆｆｆｆｆｆで塗りつぶし、続いてトラペゾイドのエッジ間にあるピクセルをＧｒａｙ情報、すなわち０ｘ００００００、で塗りつぶす。白に相当する色値で塗りつぶす理由は、左エッジにおいてエッジの成長方向が右である場合と、右エッジにおいてエッジの成長方向が左である場合に対応するためである。あらかじめエッジが右エッジなのか、左エッジなのかを検査しておき、左エッジでエッジの成長方向が左の場合と、右エッジでエッジの成長方向が右である場合には、白に相当する色値で塗りつぶす処理を省略してもよい。以上で説明した処理をグラフィックス・オブジェクトの高さ、本例においてはトラペゾイドの高さである２０、で繰り返すことにより、記憶部２０９に描画部２０６で読み込んだ中間コードに相当するグラフィックス・オブジェクトのビットマップが形成される。
【００４９】
図９は、上述したグラフィックス・オブジェクトの形成を図示したものであり、９０１はグラフィックス・オブジェクトの先頭のスキャン・ラインから８ライン分を示した図であり、９０２及至９０９はスキャン・ライン毎に塗りつぶす必要があるピクセルを図示したものである。９０２は先頭のスキャン・ラインであるため、すべてのピクセルを塗りつぶす必要がある。９０３及び９０５及び９０７及び９０９には差分のピクセルがないため、これに相当するスキャン・ラインでは、描画部２０６はバッファ２０７に書き出しを行わない。スキャン・ライン９０４，９０６，９０８については、描画部２０６は、塗りつぶされているピクセルのみピクセルの書き出しを行う。図９においては、２０×８＝１６０ピクセルが図示されているが、この方法によって、２６ピクセルの塗りつぶしでビットマップが生成できることになる。
【００５０】
＜レンダリングの具体例２＞
続いて図１０に示されるグラフィックス・オブジェクトを描画部２０６で形成する場合について説明する。１００１は、矩形１００３と、矩形１００３上にビットマップ・フォント１００２が重なるビットマップであり、ビットマップ・フォント１００２を現す中間コードは１００４のようになる。なおビットマップ・フォント１００２の色値は、矩形１００３のそれぞれ対応するピクセルの色値と排他的論理和を計算して色値が決定される。なお、矩形１００３のグラフィックス・オブジェクトを示す中間コード及びその描画方法は、上述の説明で容易に理解できるため説明しない。１００４では、ＲＯＰ情報は、Ａｒｅａ情報はクリップであり、対応するディスティネーションの各ピクセルの色値と排他的論理和を計算して色を決定することを示す"ＤＰＳｏｘ"であり、位置情報は、該グラフィックス・オブジェクトが紙面のＸ座標１０、Ｙ座標３０に書き出されることを示し、Ａｒｅａ情報は幅２０、高さ２０の矩形であり、Ｍａｓｋ情報は二値ビットマップであり、ＢＧ情報はＮＵＬＬ値であり、Ｇｒａｙ情報は単色である。なおフォントの場合、フォント・キャッシュにフォントを構成するビットマップを格納する場合があり、本実施形態でも中間コードにはフォント・キャッシュのＩＤを示す数値を中間コードに格納し、フォントを構成するビットマップはフォント・キャッシュに格納され、フォント・キャッシュには１００５に示す二値ビットマップが格納されている。なお二値ビットマップのそれぞれのスキャン・ラインの右側に記載されている数値は、該スキャン・ラインを数値で表したものであり、スキャン・ラインあたり１６ビットで表現されていることを示す。また、Ｍａｓｋ情報の二値ビットマップはオフセットにＸ，Ｙともに０が指定されている。これは１００３に示すビットマップの左上の座標（０、０）からビットマップを形成することを示す。またＭａｓｋ情報の二値ビットマップは拡大率Ｘ，Ｙともに２が指定されている。これは１００３に示すビットマップを縦及び横方向に２倍してビットマップを形成することを示す。
【００５１】
中間コード１００４が描画部２０６に読み込まれると、描画部２０６は１００４で示す中間コードが示すグラフィックス・オブジェクトとディスティネーションとの論理関係を判定する。本例において、グラフィックス・オブジェクトとディスティネーションとの論理関係は、グラフィックス・オブジェクトとディスティネーションの各ピクセルで排他的論理和をとるようにＲＯＰ情報で指定されているため、グラフィックス・オブジェクトとディスティネーションとの論理関係は、排他的論理和を示す"Ｘ"となる。上述のように求められた論理関係と位置情報は論理演算部２１２に伝送される。続いて描画部２０６は中間コードに含まれる情報を読み取り、グラフィックス・オブジェクトの最初のスキャン・ラインをバッファ２０７に書き出す。本例において、Ａｒｅａ情報はクリップであるので、クリップに含まれないピクセルは白に相当する色値、例えば０ｘｆｆｆｆｆｆを書き出す。クリップに含まれるピクセルで且つＭａｓｋ情報の対応するビットがオンのピクセルは、Ｇｒａｙ情報に従った色値、すなわち０ｘ００００００を書き出す。本例では、二値ビットマップの拡大率Ｘに２が指定されているので、バッファ２０７の０から５及び８から１９は白に相当する色値、すなわち０ｘｆｆｆｆｆｆで塗りつぶされ、６から７はＧｒａｙ情報に相当する色値、すなわち０ｘ００００００で塗りつぶされる。
【００５２】
続いて、上記バッファ２０７に格納されたラスタ情報は転送部２０８に読み出され、論理演算部２１２に伝送される。論理演算部２１２では、予め描画部２０６よりディスティネーションとの論理演算パラメータとして"Ｘ"が指定されているので、記憶部２０９の概ラスタ情報の転送先から色値を読み出し、これと概ラスタ情報の排他的論理和を計算し、再び記憶部２０９に格納する。転送部２０８よりバッファ２０７に格納されているラスタ情報が読み出されると、続くスキャン・ラインをバッファ２０７に形成する。本例においては、Ａｒｅａ情報及びＧｒａｙ情報は、グラフィックス・オブジェクトの先頭のスキャン・ラインから終端のスキャン・ラインまで変化はなく、また、Ｍａｓｋ情報ではＹの拡大率として２が指定されているので、このグラフィックス・オブジェクトの偶数番目のスキャン・ライン（すなわち図８Ｃで説明したｎ ｍｏｄ Ｎ≠０となるスキャンライン）では上のスキャン・ラインのそれぞれ相当するピクセルで色値に差分がない。このため、偶数番目のスキャン・ラインにおいては、バッファ２０７の内容に変更がないまま、転送部２０８にラスタ情報を転送することになる。
【００５３】
先頭及び偶数のスキャン・ライン以外については、Ｍａｓｋ情報のスキャン・ライン間の差分を検査し、差分のあるピクセルに相当するバッファ２０７のピクセルに対して塗りつぶしを行う。このときＭａｓｋ情報を拡大してから差分を検査する必要はなく、Ｍａｓｋ情報を、例えばＭａｓｋ情報の二値ビットマップの連続するスキャン・ラインを表す数値で排他的論理和を取り、この計算結果を拡大率で乗じ、この結果ビットがＯＮになっている箇所に相当するピクセルが差分があるピクセルと判定すればよい。
【００５４】
以上の処理をグラフィックス・オブジェクトの終端のスキャン・ラインまで繰り返すことにより、中間コード１００４が表すグラフィックス・オブジェクトが記憶部２０９に形成されることになる。
【００５５】
図１１は、中間コード１００４のＭａｓｋ情報の、連続するスキャン・ラインでそれぞれに相当するピクセルで差分があるピクセルを図示したものであり、１１０１は、Ａｒｅａ情報を適用したＭａｓｋ情報、１１０２及至１１１１は差分情報を示す。ただし、先頭のスキャン・ライン（１１０２）においては、全てのピクセルで差分があるとしている。この差分があるピクセルは、上述したように、連続するスキャン・ラインで排他的論理和をとることで判定可能である。具体的には、最初のスキャン・ラインと、続くスキャン・ラインのそれぞれ相当するピクセルで差分のあるピクセルは、隣接するラインの対応ピクセルの排他的論理和（ＸＯＲで表す。）、たとえば（０ｘ１０００）ＸＯＲ（０ｘ１１００）＝０ｘ０１００にて求めることが出来る。なお、本例においては、二値ビットマップの幅が１６ビットであるが、これより大きい幅を持つビットマップでも、先頭から、例えば３２ビット単位や１６ビット単位で、排他的論理和を計算することで、差分情報を上述した手法と同じ手法で求めることができる。
【００５６】
図１２は、中間コード１００４のＭａｓｋ情報を拡大したときの状態を図示し、１２０１は拡大する前の二値ビットマップ、１２０２はピクセルを拡大する方法を説明する図、１２０３は１２０１を拡大した二値ビットマップを示す。縦及び横方向に２倍拡大する際には、１２０２に示すように、任意の１ピクセルが縦及び横方向に二つずつ並ぶようにピクセルを生成すれば拡大することができる。
【００５７】
＜レンダリングの具体例３＞
続いて図１３に示すグラフィックス・オブジェクトを表す中間コードを描画部２０６で形成する場合について説明する。１３０１は、生成されるビットマップであり、１３０２は中間コードであり、Ａｒｅａ情報としてクリップとしての矩形、Ｍａｓｋ情報及びＢＧ情報はなく、Ｇｒａｙ情報としてイメージを持ち、イメージは１３０３に示されるようなビットマップである。Ｇｒａｙ情報やＢＧ情報がビットマップである場合には、ビットマップの連続するスキャン・ラインでそれぞれ相当するピクセルで差分がある位置を予め計算するのは負荷が高い。このため、本実施形態ではＧｒａｙ情報やＢＧ情報がビットマップである場合には、全てのピクセルで差分があるものとみなす。すなわち、バッファ２０７には、イメージを、必要に応じてＸ方向に拡大しながら、出力することになる。Ｙ方向の拡大については、前述したように、Ｙ方向の拡大率に応じて、バッファ２０７への書き出しを行うもしくは行わないを選択的に制御することで実現できる。このように、中間コードの属性に応じて差分を求める方法を切り替えることにより、差分を求めるのが難しい、もしくは負荷が高い場合も柔軟に対応が可能になる。
【００５８】
なお、本発明において、バッファ２０７と記憶部２０９は別のデバイスであることが望ましいが、同じデバイスであっても本発明が適用できる。また、本実施形態では形成するビットマップのピクセルはＲＧＢ２４ビットであったが、ピクセルが他の色表現、例えばＣＭＹＫ形式やＹＣＣ形式やモノクロ形式であっても良いことはいうまでもない。
【００５９】
以上の様にして、本実施形態によれば、グラフィックオブジェクトをライン単位でレンダリングする際に、一定の条件のもとで、隣接ライン間において相異なる値を持つ対応画素（差分ピクセル）に限って再レンダリングすることで、レンダリング処理の効率化を実現している。一方、ＢＧ情報やＧｒａｙ情報がイメージやパターンといった色値の内包的定義を含むグラフィックオブジェクトについては、描画対象のスキャンライン全体を差分ピクセルとみなして再レンダリングしている。こうすることで、差分ピクセル（の位置）を決定するための処理の負荷が大きくなる可能性が高い場合には、差分のピクセルを決定する処理を省いて効率的なレンダリング処理を実現できる。
【００６０】
［実施形態２］
続いて、本発明に係る別の実施形態について説明する。なお、本実施形態において、実施形態１で説明したものについては説明を省略する。また、本発明に直接関連しない構成要素は図からも省略している。
【００６１】
描画部２０６での画像形成方式で、処理速度的に難があるグラフィックス・オブジェクト、例えばＹ方向の拡大率が１であるイメージ等、ではバッファ２０７に画像を形成した上で記憶部２０９に転送するため、実施形態１の方法でレンダリング（描画とも言う。）を行うと従来の描画方式より処理速度が遅くなる場合がある。このため、グラフィックス・オブジェクト毎に従来の描画方式と、本発明に係る描画方式を切り替える方法が望まれる。第２の実施形態ではこれを実現する構成について説明する。
【００６２】
図１４は、上記要望を満たす、従来の描画方式と本発明の描画方式を切り替えるプリンタコントローラの一例を表す図である。１４０１はプリンタコントローラであり、第一の実施形態で説明した２０３に相当する。１４０１は、第一の実施形態で説明した描画部２０６であり、図８Ａ（ｂ）−図８Ｃの手順でグラフィックスオブジェクトをレンダリングする。このほかバッファ２０７、転送部２０８、論理描画部２１２、記憶部２０９があり、また、図示しないが、図２におけるＩ／Ｆ２０４、解釈部２０５、画像処理部２１１、ビデオ転送部２１０も具有する。１４０３は従来の描画部であり、グラフィックオブジェクトのレンダリングを従来の手順で行う。この手順ではたとえばオブジェクトの全画素の値をラスタ順で決定する。１４０２は記憶部２０９に保持されている中間コードに従って、中間コードを描画部２０６もしくは描画部１４０３に振り分ける。描画部１３０３は記憶部２０９と接続されている。
【００６３】
第一の実施形態で説明した中間コードは、従来の描画方式における中間コードと互換性を保つ。このため、判断部１４０２にて、グラフィックス・オブジェクトの属性に従って、描画部１４０３もしくは描画部２０６に中間コードを転送することで、従来の描画方式と、本発明に係る描画方式を切り替える。判断部１４０２は、例えば、Ｇｒａｙ情報がイメージであり、且つＹ方向の拡大率が１ならば描画部１４０３に読み込んだ中間コードを転送し、従来の手順でレンダリング処理を行う。一方、Ｇｒａｙ情報がイメージであり、且つＹ方向の拡大率が１以外ならば描画部２０６に中間コードを転送し、描画部２０６により第１実施形態のの図８Ａ（ｂ）−図８Ｃに係るレンダリング処理を行う。
【００６４】
この判断は図８Ａ（ａ）のステップＳ８１２の直後に行われ、着目グラフィックスオブジェクトに関して、そのＧｒａｙ情報がイメージであり、且つＹ方向の拡大率が１ならば、ステップＳ８１３に分岐し、そうでなければ、従来の手順で着目グラフィックオブジェクトをレンダリングする。このように中間コードの属性に従って描画方式を切り替えることで、処理速度をより向上させたプリンタコントローラを実現することが可能になる。
【００６５】
［実施形態３］
続いて、本発明の第３の実施形態について図を用いて説明する。図２１は本実施形態の画像形成方法を実施するためのプリンタコントローラの概念図である。２１０１はプリンタコントローラ、２１０２は図示しない外部ホストからプリントデータを受信し記憶部２１０７に保存するＩ／Ｆ、２１０３は上記記憶部２１０７に保存されたプリントデータを解釈して、後述する中間コードを生成し記憶部２１０７に保存する解釈部、２１０４は上記記憶部２１０７に保存された中間コードを読み取ってスキャン・ライン毎にバッファ２１０５に画像を形成する描画部、２１０５は少なくとも形成されるビットマップのスキャン・ラインが保持できるバッファ、２１０６はバッファ２１０５に形成されたスキャン・ライン画像を記憶部２１０７に伝送するＤＭＡ、２１０７は、たとえばメモリである、記憶部であり、２１０８は記憶部２１０７に格納されたビットマップに、画像処理を行う画像処理部であり、２１０９は図示しないプリンタエンジンに、画像処理部２１０８にて画像処理を行った画像を転送するビデオ転送部である。記憶部２１０７はＩ／Ｆ２１０２及び解釈部２１０３及び描画部２１０４及びＤＭＡ２１０６及び画像処理部２１０８及びビデオ転送部２１０９と接続され、バッファ２１０５は描画部２１０４及びＤＭＡ２１０６と接続される。
【００６６】
続いて、本実施形態における画像形成方法について、図を用いて説明する。図示しないホストコンピュータから伝送されたプリントデータは、Ｉ／Ｆ２１０２にて記憶部２１０７に保存される。記憶部２１０７に保存されたプリントデータは解釈部２１０３にて、図１６のフローチャートに従って解釈され、中間コードに変換される。解釈部２１０３の動作については後述する。なお、プリントデータは複数のグラフィックス・オブジェクトから構成される。通常グラフィックス・オブジェクトは、描画するビットマップの奥に配置するものから順に転送される。本実施形態においては、記憶部２１０７に保存されるプリントデータは、描画するビットマップの奥行き方向の順番を保って保存されるものとする。解釈部２１０３でプリントデータから変換された中間コードは記憶部２１０７に保存される。上述のように記憶部２１０７に保存された中間コードは、描画部２１０４に読み込まれ、中間コードに従って描画部２１０４はバッファ２１０５に、スキャン・ラインのラスタを形成する。描画部２１０４の動作については後述する。上述のようにバッファ２１０５に形成されたスキャン・ラインのラスタは、ＤＭＡ２１０６によって記憶部２１０７の予め設定されていたアドレスに転送される。ＤＭＡ２１０６にて転送が終了すると、ＤＭＡは続くスキャン・ラインの転送に備え、記憶部２１０７の転送先アドレスを、例えば転送したラスタサイズ分アドレスをインクリメントすることにより、更新する。また、ＤＭＡ２１０６にてバッファ２１０５のラスタが読み込まれても、バッファ２１０５はそのラスタ情報を保持するようにする。ＤＭＡ２１０６でラスタの転送が終了すると、描画部２１０４は続くスキャン・ラインをバッファ２１０５に形成する。以下、記憶部２１０７に形成するビットマップの全スキャン・ラインに対して上述した処理を繰り返すことにより、記憶部２１０７には、１面分のビットマップが形成される。記憶部２１０７にビットマップが形成されると、画像処理部２１０８は、図示しないプリンタ・エンジンに転送が行えるように画像データのフォーマット変換を行い、変換しビットマップを記憶部２１０７に格納する。ビデオ転送部２１０９は、画像処理部にて変換されたビットマップを読取り、外部の図示しないプリンタ・エンジンにビットマップを転送し、プリンタ・エンジンは、受信したビットマップを、紙面に印字する。
【００６７】
なお、本実施形態では、記憶部２１０７に１面（１ページ）分の画像を形成したが、紙面を帯状に分割した領域毎に処理を行ってもよく、この場合、記憶部２１０７にはバンドバッファを用意すればよく、またＤＭＡ２１０６は、予め定められたバンド高さ分のラスタを記憶部２１０７に転送したのち、転送先のアドレスを初期化すればよい。
【００６８】
＜中間コードの形式＞
続いて、解釈部２１０３にてプリントデータから変換される中間コードを構成する要素の一例を図１５に示す。以下、中間コードを構成する要素を差分リストと呼ぶ。図１５において１５０１は、連続する２つのスキャン・ラインにおいてそれぞれに相当するピクセルで差分があるピクセルのＸ座標であり、１５０２は連続して差分があるピクセルの個数である。１５０３は差分のあるピクセルを塗りつぶすグラフィックス・オブジェクトのリストであり、１５０４は同一のスキャン・ラインに存在するほかの位置での差分リストを指し示すポインタである。なお、グラフィックス・オブジェクトのリストには、塗りつぶしを行わないことを示すパラメータを指定することができ、これは、例えばグラフィックス・オブジェクトの最後のスキャン・ラインの次のスキャン・ラインにおいて、該グラフィックス・オブジェクトで描画されたピクセルを消去するために利用される。また差分リストはスキャン・ライン毎に形成され、差分のないスキャン・ラインについては、ＮＵＬＬが指定されることになる。
【００６９】
＜中間コードの生成手順＞
図１６において、解釈部２１０３は、記憶部２１０７に保存されたプリントデータに、未処理のグラフィックスオブジェクトがあるか判定し（Ｓ１６０１）、あればそのグラフィックスオブジェクトを、グラフィックス・オブジェクト単位で読み込む（Ｓ１６０２）。もし処理すべきグラフィックス・オブジェクトがないと判断した場合には、解釈処理を終了する。続いて、グラフィックス・オブジェクトの先頭のスキャン・ラインから順に着目し、着目スキャンラインが最終スキャンラインか判定する（Ｓ１６０３）。この判定はたとえばオブジェクトのパラメータに含まれる「高さ」パラメータと着目スキャンライン番号とを比較することで実現できる。
【００７０】
最後のスキャンラインでなければ、着目スキャンラインとその直前のスキャン・ラインとでそれぞれ対応するピクセルで差分があるピクセルを検索する（Ｓ１６０４）。なおステップＳ１６０４では、差分のあるピクセルのＸ方向の開始位置、及び連続して差分があるピクセル数が検索される。もし差分のあるピクセルが見つかった場合には、例えば図１７に示すフローチャートに従って、それまでに作成された差分リストを更新、もしくは新規に差分リストを作成する（Ｓ１６０５）。その後ステップＳ１６０４に戻り、グラフィックス・オブジェクトの処理中のスキャン・ライン上にある全ての差分ピクセルに対してＳ１６０５を繰り返す。ステップＳ１６０４で処理すべき差分情報がない場合には、処理中のグラフィックス・オブジェクトのスキャン・ラインを次のスキャン・ラインに進め（Ｓ１６０６）、グラフィックス・オブジェクトの全てのスキャン・ラインについて上述した処理を繰り返す。グラフィックス・オブジェクトの全てのスキャン・ラインで差分ピクセルの処理が終了すると、処理が終了したグラフィックス・オブジェクトを、後述の差分リストの更新のために、処理が終了したグラフィックス・オブジェクト・リストの最後尾に追加し（Ｓ１６０７）、ステップＳ１６０１に戻り、続くグラフィックス・オブジェクトに対して上述した処理を繰り返す。
【００７１】
続いてステップＳ１６０５にて、差分リストを更新、もしくは新規に作成する方法の一例を図１７のフローチャートを用いて説明する。まず図１６のステップＳ１６０４にて検索された差分のあるピクセルを含む差分リストがすでに記憶部２１０７に存在するかを調べる（Ｓ１７０１）。ここで見つからなかった場合には、新規に差分リストを作成し、ステップＳ１６０４にて検索された差分があるピクセル上に描画するグラフィックス・オブジェクトを、図１６のステップＳ１６０７で作成済みの処理済グラフィックス・オブジェクト・リストの先頭から検索し、差分リストのグラフィックス・オブジェクト・リスト１５０３に登録し、今回作成した差分リストを処理対象として選択する（Ｓ１７０７）。その後、今回入力されたグラフィックス・オブジェクト（着目グラフィックスオブジェクト）を差分リストのグラフィックス・オブジェクト・リストに追加し（Ｓ１７０８）、処理を終了する。
【００７２】
一方、ステップＳ１７０１にて、ステップＳ１６０４にて検索された差分のあるピクセルを含む差分リストがすでに記憶部２１０７に存在する場合には、該差分リストを処理対象として選択する（Ｓ１７０２）。続いて、選択された差分リストと、図１６のＳ１６０４にて検索された差分のあるピクセルの開始座標及び幅が等しいかを検査（判定）する（Ｓ１７０３）。等しい場合には、選択されている差分リストのグラフィックス・オブジェクト・リストの後方に今回入力されたグラフィックス・オブジェクトを追加して処理を終了する（Ｓ１７０８）。
【００７３】
ステップＳ１７０３にて、等しくないと判定された場合は、選択されている差分リストを、今回入力された差分があるピクセルを含むものと含まないものに分割し、今回の差分が含まれる差分リストを選択しなおす（Ｓ１７０４）。続いて、選択されている差分リストのグラフィックス・オブジェクト・リストの後方に今回入力されたグラフィックス・オブジェクトを追加する（Ｓ１７０５）。続いて、選択されている差分リストに記載されている位置情報が、今回入力された差分があるピクセルを完全に包含するか、すなわち選択されている差分リストの開始位置及び幅が今回入力されたそれと等しいか、を検査し（Ｓ１７０６）、等しい場合には処理を終了し、等しくない場合には、選択されている差分リストに含まれない差分があるピクセルを新規に差分リストとして登録する（Ｓ１７０７）。Ｓ１７０７以降の処理は上記にてすでに説明したとおりである。
【００７４】
図１８は、上述した差分リストの更新を良く表す図である。１８０１は既に登録されている差分の情報の一例であり、先頭から差分ピクセルの位置、その長さ、オブジェクト識別子を含む。１８０２は既登録差分情報１８０１を図示したものであり、１８０３は新規に入力される差分の情報の一例であり、１８０４は新規差分情報１８０３を図示したものである。既登録差分情報１８０１の差分の情報は、１８０５に示すような差分リストとして登録されている。新規差分情報１８０３が入力されると、新規差分情報１８０３で表現される差分があるピクセルは差分リスト１８０５の領域と一部重なっているので、差分リスト１８０５を、新規差分情報１８０３で表現される差分があるピクセルを含むものと含まないものとで２つに分割する。含まれるほうのグラフィックス・オブジェクト・リストに、新規差分情報１８０３に対応するグラフィックス・オブジェクトを追加する。すなわち、差分リスト１８０５において座標"Ｐ"から座標"Ｐ＋２"まで（すなわち位置Ｐ、長さ３）は、新規差分情報１８０３で表現される差分があるピクセルを含み、座標"Ｐ＋３"から座標"Ｐ＋６"まで（すなわち位置Ｐ＋３、長さ４）は含まないため、差分リスト１８０６に示すような、位置Ｐ、長さ３の差分ピクセルに対応する差分リストと、位置Ｐ＋３、長さ４の差分ピクセルに対応する差分リストの２つの差分リストに分割されることになる。一方、新規差分リスト１８０３で表現される差分があるピクセルにおいて、座標"Ｐ−２"から座標"Ｐ−１"までは、差分リストに含まれていない。そこで、図１８の差分リスト１８０７に示すように、含まれない差分があるピクセルを表す差分リスト（位置Ｐ−２、長さ２）を新規に作成して、差分リストに連結する。
【００７５】
以上の手順により、中間コードとして、直前のスキャンラインとの間における差分ピクセルのランとそのランに対応するオブジェクトを示すリスト（差分リスト）が、スキャンライン毎に作成される。作成された中間コードは記憶部２１０７に記録される。なお、図１９の例には記載されていないが、各差分リストはスキャンライン毎に生成されるために、差分リストがどのスキャンラインに対応するかを示す対応ライン識別子も差分リストには、例えばその先頭に含まれている。
【００７６】
＜スキャンラインの生成＞
続いて、描画部２１０４にて、バッファ２１０５に着目スキャン・ラインを形成する方法について図２０のフローチャートを用いて説明する。図２０の手順は、フレームメモリにおいて、差分リストで示されるスキャンラインに着目して処理が行われる。
【００７７】
上記で説明したように、記憶部２１０７には、スキャン・ライン毎に差分リストが記憶部２１０７に格納される。描画部２１０４は、形成するスキャン・ラインの先頭の差分リストを記憶部２１０７から読み出す（Ｓ２００１）。続いて、読み込んだ差分リストがＮＵＬＬであるか否かを検査し（Ｓ２００２）、ＮＵＬＬである場合には処理対象のスキャンライン（着目スキャンライン）には差分がないと判断し、スキャン・ラインの形成を終了する。ステップＳ２００２で差分リストがＮＵＬＬでない場合には、該差分リストで表現される差分のあるピクセルに相当するバッファ２１０５のアドレスに、白に相当する色値、例えば０ｘｆｆｆｆｆｆを書き出す（Ｓ２００３）。続いて、差分リストのグラフィックス・オブジェクト・リストの先頭のグラフィックス・オブジェクトを選択し（Ｓ２００４）、選択されているグラフィックス・オブジェクトに従って差分があるピクセルに相当するバッファ２１０５のアドレスに色値を書き出す（Ｓ２００５）。続いて、差分リストのグラフィックス・オブジェクト・リストの次のグラフィックス・オブジェクトがあるか否かを検査し（Ｓ２００８）、ある場合には次のグラフィックス・オブジェクトを選択し（Ｓ２００７）、ステップＳ２００５以降を繰り返す。ステップＳ２００８で続くグラフィックス・オブジェクトがない場合には、ステップＳ２００１に戻り上述した処理を繰り返す。なお、ステップＳ２００５にて色値を書き出す際には、グラフィックス・オブジェクト内で定義されている論理演算に従う。また、着目スキャンラインがフレームの先頭ラインの場合には、その全ピクセルが差分ピクセルであるとして差分リストに登録しておけばよい。
【００７８】
この手順によって、ライン毎にその差分リストに基づいて、差分ピクセルの位置に対応するオブジェクトのピクセルを補填することで、スキャンライン単位のレンダリングが実現できる。しかも、差分ピクセルのみの描画で十分でありレンダリング時間の短縮を図ることができる。
【００７９】
図１９は、図１の画像に対応する差分リストの一例を示す。図１の画像はにおいて、１０４は形成されるビットマップ、１０５及び１０６はビットマップ１０４上にあるグラフィックス・オブジェクトＡ，Ｂであり、オブジェクト１０６はオブジェクト１０５より奥に描画される。拡大図１０１は１０４の座標（Ｍ，Ｎ）を基準として２０ピクセル平方を拡大した図である。１０２は１０５のエッジであり、１０３は１０６のエッジである。１０１において、枠が太くなっているピクセルは、上スキャン・ラインと、それぞれ相当するピクセルで、差分があるピクセルを示す。第（Ｍ＋１０）ラインの差分リストを、符号１９０６に示す。拡大図１０１で分かるように、位置（Ｎ＋６）と位置（Ｎ＋９）においてそれぞれ１ピクセルずつ差分ピクセルとなる。そして、その２ピクセルとも、奥からオブジェクトＡ、オブジェクトＢの順で重複している。したがって、オブジェクトリストには、位置（Ｎ＋６）から１ピクセルについて、オブジェクトＡ、オブジェクトＢの順でグラフィックオブジェクトリストが生成されており、位置（Ｎ＋９）から１ピクセルについても同様である。
【００８０】
逆に、この図１９の差分リストから、位置と長さに該当するオブジェクトのピクセルがその直前のスキャンラインのドットイメージ上に書き込まれて、図１の画像が形成される。
【００８１】
なお、本実施形態においては、差分のあるピクセルに描画するグラフィックス・オブジェクトを全てグラフィックス・オブジェクト・リストに追加したが、グラフィックス・オブジェクト・リストに含まれるグラフィックス・オブジェクトの論理演算パラメータが上書を示す場合、そのグラフィックス・オブジェクトより前に連結されているグラフィックス・オブジェクトをリストから削除してもよい。
【００８２】
なお、本発明において、バッファ２０７と記憶部２０９は別のデバイスであることが望ましいが、同じデバイスであっても本発明が適用できる。
【００８３】
［実施形態４］
続いて、本発明に係る別の実施形態について説明する。なお、本実施形態において、既に説明したものについては説明を省略する。本実施形態でのプリンタ・コントローラは、実施形態３の図２１のプリンタコントローラと等しく、記憶部２１０７に保存される中間コードは、実施形態１で説明した中間コードとする。以下記憶部２１０７に中間コードが保存された状態からの動作について説明する。
【００８４】
図２２は本実施形態での画像形成方法を説明するためのフローチャートである。まず描画部２１０４は、着目スキャンラインを格納するバッファ２１０５を初期化する。また、処理中のスキャン・ラインを表すパラメータ"Ｎ"を０に初期化する（Ｓ２２０１）。続いて、記憶部２１０７に保存されている中間コードから、スキャン・ラインが"Ｎ"から始まる中間コードを検索し"リスト１"に追加する。このとき作成されるリスト１では、中間コードを描画する順番を、例えば双方向リンクリストで中間コードを描画順番で連結することにより、保つものとする。また、"Ｎ"が２以上の場合、最終のスキャン・ラインが"Ｎ−２"のグラフィックスオブジェクトの中間コードをリストから削除する（Ｓ２２０２）。これは、中間コードが表すグラフィックス・オブジェクトの最後のスキャンラインの次のスキャン・ラインで該グラフィックス・オブジェクトで描画されたピクセルを消去する必要があることに起因する。
【００８５】
続いて、"リスト１"の先頭の中間コードを記憶部２１０７に用意したパラメータ"Ｏ（オー）"に設定する（Ｓ２２０３）。たとえばパラメータＯとして"リスト１"の先頭の中間コードそのものを記録しても良いし、そこに至るポインタやインデックスを記録すればよい。続いてパラメータ"Ｏ"を検査し、中間コードが選択されているか（記録されているか）を判定する（Ｓ２２０４）。中間コードが選択されている場合、パラメータ"Ｏ"で選択されている中間コードの、着目スキャン・ライン"Ｎ"とその直前のスキャン・ライン"Ｎ−１"でそれぞれに相当するピクセルで差分があるピクセルを検索する（Ｓ２２０５）。
【００８６】
ステップＳ２２０５の検索の結果、差分のあるピクセルがあるか判定し（Ｓ２２０６）、あると判断された場合には、バッファ２１０５において、差分があるピクセルを、白に相当する色値、例えば０ｘｆｆｆｆｆｆで塗りつぶす。また、"リスト１"とは別のリストである"リスト２"を初期化し、"リスト１"から、スキャン・ライン"Ｎ"で描画される中間コードを順次検索し、"リスト２"に順次連結する。また"リスト２"の先頭の中間コードをパラメータ"Ｏ'"に設定する（Ｓ２２０７）。続いて、パラメータ"Ｏ'"に中間コードが選択されているかを検査する（Ｓ２２０８）。選択されている場合には、"Ｏ'"で選択されている中間コードに対応するオブジェクトが、ステップＳ２２０６で検索された差分があるピクセルを塗りつぶすか否かを検査する（Ｓ２２０９）。塗りつぶすと判定された場合には、パラメータ"Ｏ'"で選択されている中間コードで定義された色値で、ステップＳ２２０６で検索されたピクセルを塗りつぶし（Ｓ２２１０）、パラメータ"Ｏ'"を"リスト２"の次の中間コードに設定し（Ｓ２２１１）、ステップＳ２２０８からの処理を繰り返す。
【００８７】
一方ステップＳ２２０９にて、パラメータ"Ｏ'"で選択されている中間コードに対応するオブジェクトはステップＳ２２０６で検索された差分があるピクセルを塗りつぶさないと判定された場合には、ステップＳ２２１１に進む。
【００８８】
また、ステップＳ２２０８にてパラメータ"Ｏ'"で中間コードが選択されていない場合は、パラメータ"Ｏ"を"リスト２"の次の中間コードに設定し（Ｓ２２１２）、ステップＳ２２０４に進む。
【００８９】
また、ステップＳ２２０６にて差分のあるピクセルがないと判定された場合には、ステップＳ２２１２に進む。
【００９０】
また、ステップＳ２２０４にて"Ｏ"で中間コードが選択されていない場合には、バッファ２１０５のラスタ情報を、ＤＭＡ２１０６にて記憶部２１０７に伝送し、"Ｎ"に１を加えて、次のスキャン・ラインの処理に備える（Ｓ２２１３）。ここで、ＤＭＡ２１０６にてバッファのラスタ情報が記憶部２１０７に伝送されても、バッファ２１０５のラスタ情報は保持する。続いて"Ｎ"が形成するビットマップの最終のスキャン・ラインであるか否かを検査し（Ｓ２２１４）、最終のスキャン・ラインでない場合には、ステップＳ２２０２に進み、上述した処理を繰り返す。また、ステップＳ２２１４にて最終スキャン・ラインであると判定されると描画処理を終了する。なお、ステップＳ２２０８では、パラメータ"Ｎ"が中間コードが示すグラフィックス・オブジェクトの最後のスキャンラインの次のスキャンラインを示す場合には、最後のスキャンラインで描画されるピクセルが差分があるピクセルになる。
【００９１】
なお、本発明において、バッファ２０７と記憶部２０９は別のデバイスであることが望ましいが、同じデバイスであっても本発明が適用できる。
【００９２】
以上の手順によって、従来と互換性のある中間コードを用いて、すなわち従来の中間コードを生成するプログラムを流用しつつ、スキャンライン毎にその差分ピクセルについて描画することで、レンダリング処理の速度の向上を実現した画像形成装置を提供できる。
【００９３】
［実施形態５］
本発明に係る第５の実施形態について説明する。なお、本実施形態において、実施形態４で説明したものについては説明を省略する。
【００９４】
図２３は、本実施形態を説明するための図であり、図２３０１はプリンタ・コントローラであり、描画選択部２３０２及び第一の描画部２１０３及び第二の描画部２３０３と、記憶部２１０７と、図示しないＩ／Ｆと、解釈部と、バッファと、ＤＭＡと、画像処理部と、ビデオ転送部を具備する。なお第一の描画部２１０３及び記憶部２１０７及びＩ／Ｆ及び解釈部及びバッファ及びＤＭＡ及び画像処理部及びビデオ転送部は実施形態４で説明したものと同じであるため説明は省く。
【００９５】
本実施形態にかかる画像形成方法は、高解像度の画像の特性、すなわち連続したスキャン・ラインでそれぞれに相当するピクセルで差分が発生するピクセルは少ないこと、を利用した画像形成方法であるため、低解像度の画像に対しては効果が小さいか、もしくは従来の方式より遅くなる可能性を含んでいる。そのため、描画選択部２３０２は出力するビットマップの解像度から、第１の描画部２１０３もしくは従来の描画方式である第２の描画部２１０４を選択し、解像度に応じて描画部を選択できるようにしている。すなわち、解像度が一定解像度以上であれば第４の実施形態に係る描画部２１０３により描画処理を行い、一定解像度よりも低ければ描画部２１０４により描画処理を行う。なお、記憶部２１０７に記憶される中間コードは、実施形態２で説明したように、従来の描画方式における中間コードと互換性を保つことは既に説明した。
【００９６】
この様に構成することで、解像の高低にかかわらず高い描画性能を維持することができる。
【００９７】
なお、実施形態２乃至５について、差分の判定は実施形態１と同様に、たとえば矩形や台形、ランレングス、ビットマップ等の種類に応じて行うことができる。実施形態３では、差分の判定は従来の中間コードではなく、ホストコンピュータから受信した印刷データに基づいて行うことになるが、オブジェクトの記述は基本的に同一なので、実施形態３においても実施形態１と同様の方法で差分を判定できる。
【図面の簡単な説明】
【００９８】
【図１】グラフィックス・オブジェクトの連続するスキャン・ラインでそれぞれ対応するピクセルで差分があるピクセルの一例を示す図である。
【図２】本発明に係る第１実施形態のプリンタコントローラの概念図の一例である。
【図３】本発明に係る第１実施形態の中間コードの一例である。
【図４】図３の中間コードに含まれる情報の関係の一例を示す図である。
【図５】図３の中間コードに含まれる情報の種別の一例を示す図である。
【図６】図３の中間コードに含まれる情報の一例である。
【図７】本発明に係る第１実施形態の中間コードの一例を示す図である。
【図８Ａ】本発明の第１実施形態の画像形成処理の一例を説明するためのフローチャートである。
【図８Ｂ】本発明の第１実施形態の画像形成処理の一例を説明するためのフローチャートである。
【図８Ｃ】本発明の第１実施形態の画像形成処理の一例を説明するためのフローチャートである。
【図９】グラフィックス・オブジェクトの連続するスキャン・ラインでそれぞれ対応するピクセルで差分があるピクセルの一例を示す図である。
【図１０】本発明に係る第１実施形態の中間コードの一例を示す図である。
【図１１】グラフィックス・オブジェクトの連続するスキャン・ラインでそれぞれ対応するピクセルで差分があるピクセルの一例を示す図である。
【図１２】本発明に係るビットマップ画像の拡大を説明するための図である。
【図１３】本発明に係る第１実施形態の中間コードの一例を示す図である。
【図１４】本発明に係る第２実施形態のプリンタコントローラの概念図の一例である。
【図１５】本発明に係る第３実施形態の中間コードの一例である。
【図１６】本発明に係る第３実施形態の中間コードの一例を作成する処理を説明するためのフローチャートである。
【図１７】本発明に係る第３実施形態の中間コードを更新する処理を説明するためのフローチャートである。
【図１８】本発明に係る第３実施形態の中間コードを更新する処理を説明するための中間コードの一例である。
【図１９】第３実施形態の図１に示す差分があるピクセルを表現する中間コードの例である。
【図２０】本発明に係る第３実施形態の画像形成処理を説明するためのフローチャートである。
【図２１】本発明に係る第３実施形態のプリンタコントローラの概念図の一例である。
【図２２】本発明に係る第４実施形態の画像形成処理を説明するためのフローチャートである。
【図２３】本発明に係る第５実施形態のプリンタコントローラの概念図の一例である。
【符号の説明】
【００９９】
２０５、２１０３ 解釈部
２０６、１４０３、２１０４、２３０３ 描画部
２０７、２１０５ バッファ
２０８ 転送部
２０９、２１０７ 記憶部
１４０２ 判断部
２１０６ ＤＭＡ
２３０２ 描画選択部
【特許請求の範囲】
【請求項１】
フレームメモリにグラフィックスオブジェクトを描画する画像形成装置であって、
グラフィックスオブジェクトのスキャンラインごとのドットイメージデータを保存するラインメモリと、
前記ラインメモリに保存されたスキャンラインとその直後の着目スキャンラインにおいて対応する画素の値が異なる差分画素の位置を決定する決定手段と、
前記ラインメモリに保存されたドットイメージデータのうち、前記決定手段により決定された差分画素の値を、前記着目ラインにおける画素の値に更新する差分更新手段と
を備えることを特徴とする画像形成装置。
【請求項２】
前記ラインメモリのドットイメージデータを、前記着目スキャンラインに相当する前記フレームメモリの位置に合成する合成手段を更に備えることを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記決定手段は、単色のグラフィクスオブジェクトについては、その輪郭を構成する画素がライン間において移動した際の、移動後または移動前の位置を、前記差分画素の位置として決定することを特徴とする請求項１または２に記載の画像形成装置。
【請求項４】
前記グラフィクスオブジェクトが矩形形状の場合には、前記決定手段は、差分画素は存在しないものと決定することを特徴とする請求項１乃至３のいずれか１項に記載の画像形成装置。
【請求項５】
前記グラフィクスオブジェクトが台形形状の場合には、前記決定手段は、１ラインあたりの左辺および右辺の傾きを示す値をライン毎に積算して、その積算値の変化が少なくとも１画素の変化に相当する場合に、当該ラインにおける前記積算値に相当する位置を前記差分画素として決定することを特徴とする請求項１乃至３のいずれか１項に記載の画像形成装置。
【請求項６】
前記グラフィクスオブジェクトがランレングスの場合には、前記決定手段は、前記着目スキャンラインとその直前のスキャンラインのランの開始位置と終端位置とを比較して、ずれている場合にそのずれた位置を前記差分画素として決定することを特徴とする請求項１乃至３のいずれか１項に記載の画像形成装置。
【請求項７】
前記グラフィクスオブジェクトが元形状に対して縦方向に変倍される場合、元形状の種類にかかわらず、前記着目スキャンラインが、変倍率を法として０番目のラインであればスキャンラインの全画素の位置を差分画素として決定し、それ以外のラインの場合には、差分画素は存在しないものと決定することを特徴とする請求項１乃至６のいずれか１項に記載の画像形成装置。
【請求項８】
前記グラフィクスオブジェクトの種類にかかわらず、単色ではないグラフィクスオブジェクトについては、すべての着目スキャンラインにおいて、スキャンラインの全画素の位置を差分画素として決定することを特徴とする請求項１乃至７のいずれか１項に記載の画像形成装置。
【請求項９】
前記差分更新手段によりグラフィックオブジェクトごとのドットイメージデータをスキャンライン毎に作成して前記合成手段により前記フレームメモリに合成し、当該フレームメモリに含まれるべきすべてのグラフィックオブジェクトについてそのドットイメージのフレームメモリへの合成を行うことを特徴とする請求項２に記載の画像形成装置。
【請求項１０】
着目スキャンラインを、その直前のスキャンラインとの差分画素の位置及び長さと、その位置に描画されるグラフィックオブジェクトの識別子とで定義した中間コードを、入力画像データから生成する中間コード生成手段を更に備え、
前記決定手段は、前記中間コードに応じて差分画素の位置を決定することを特徴とする請求項１に記載の画像形成装置。
【請求項１１】
着目スキャンラインを、その直前のスキャンラインとの差分画素の位置及び長さと、その位置に描画されるグラフィックオブジェクトの識別子とで定義した中間コードを、入力画像データから生成する中間コード生成手段を更に備え、
前記決定手段は、前記中間コードに応じて差分画素の位置を決定することを特徴とする請求項１に記載の画像形成装置。
【請求項１２】
前記決定手段は、着目スキャンライン毎に、そのスキャンライン上にあるグラフィックオブジェクトのリストを作成する作成手段と、作成したリストに基づいて着目スキャンラインとその直前のスキャンラインとの差分画素を決定し、
前記差分更新手段は、前記リストに属するグラフィックオブジェクトで与えられる前記差分画素の値を、前記ラインメモリの相当位置に記録することを特徴とする請求項１に記載の画像形成装置。
【請求項１３】
前記フレームメモリは、１ページ相当のドットイメージデータを格納することを特徴とする請求項１乃至８のいずれか１項に記載の画像形成装置。
【請求項１４】
前記フレームメモリは、１バンド相当のドットイメージデータを格納することを特徴とする請求項１乃至８のいずれか１項に記載の画像形成装置。
【請求項１５】
前記１画像中のすべてのグラフィックオブジェクトについてそのドットイメージのフレームメモリへの合成を行った後、前記フレームメモリのドットイメージデータを、印刷媒体上に画像として形成することを特徴とする請求項９乃至１４のいずれか１項に記載の画像形成装置。
【請求項１６】
フレームメモリにグラフィックスオブジェクトを描画するための画像形成方法であって、
ラインメモリに保存された、グラフィックスオブジェクトのスキャンラインとその直後の着目スキャンラインにおいて対応する画素の値が異なる差分画素の位置を決定する決定工程と、
前記ラインメモリに保存されたドットイメージデータのうち、前記決定工程により決定された差分画素の値を、前記着目ラインにおける画素の値に更新する差分更新工程と、
前記ラインメモリのドットイメージデータを、前記着目スキャンラインに相当する前記フレームメモリの位置に合成する合成工程と
を備えることを特徴とする画像形成方法。
【請求項１７】
請求項１乃至１５のいずれか１項に記載の画像形成装置をコンピュータにより実現するためのプログラム。
【請求項１】
フレームメモリにグラフィックスオブジェクトを描画する画像形成装置であって、
グラフィックスオブジェクトのスキャンラインごとのドットイメージデータを保存するラインメモリと、
前記ラインメモリに保存されたスキャンラインとその直後の着目スキャンラインにおいて対応する画素の値が異なる差分画素の位置を決定する決定手段と、
前記ラインメモリに保存されたドットイメージデータのうち、前記決定手段により決定された差分画素の値を、前記着目ラインにおける画素の値に更新する差分更新手段と
を備えることを特徴とする画像形成装置。
【請求項２】
前記ラインメモリのドットイメージデータを、前記着目スキャンラインに相当する前記フレームメモリの位置に合成する合成手段を更に備えることを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記決定手段は、単色のグラフィクスオブジェクトについては、その輪郭を構成する画素がライン間において移動した際の、移動後または移動前の位置を、前記差分画素の位置として決定することを特徴とする請求項１または２に記載の画像形成装置。
【請求項４】
前記グラフィクスオブジェクトが矩形形状の場合には、前記決定手段は、差分画素は存在しないものと決定することを特徴とする請求項１乃至３のいずれか１項に記載の画像形成装置。
【請求項５】
前記グラフィクスオブジェクトが台形形状の場合には、前記決定手段は、１ラインあたりの左辺および右辺の傾きを示す値をライン毎に積算して、その積算値の変化が少なくとも１画素の変化に相当する場合に、当該ラインにおける前記積算値に相当する位置を前記差分画素として決定することを特徴とする請求項１乃至３のいずれか１項に記載の画像形成装置。
【請求項６】
前記グラフィクスオブジェクトがランレングスの場合には、前記決定手段は、前記着目スキャンラインとその直前のスキャンラインのランの開始位置と終端位置とを比較して、ずれている場合にそのずれた位置を前記差分画素として決定することを特徴とする請求項１乃至３のいずれか１項に記載の画像形成装置。
【請求項７】
前記グラフィクスオブジェクトが元形状に対して縦方向に変倍される場合、元形状の種類にかかわらず、前記着目スキャンラインが、変倍率を法として０番目のラインであればスキャンラインの全画素の位置を差分画素として決定し、それ以外のラインの場合には、差分画素は存在しないものと決定することを特徴とする請求項１乃至６のいずれか１項に記載の画像形成装置。
【請求項８】
前記グラフィクスオブジェクトの種類にかかわらず、単色ではないグラフィクスオブジェクトについては、すべての着目スキャンラインにおいて、スキャンラインの全画素の位置を差分画素として決定することを特徴とする請求項１乃至７のいずれか１項に記載の画像形成装置。
【請求項９】
前記差分更新手段によりグラフィックオブジェクトごとのドットイメージデータをスキャンライン毎に作成して前記合成手段により前記フレームメモリに合成し、当該フレームメモリに含まれるべきすべてのグラフィックオブジェクトについてそのドットイメージのフレームメモリへの合成を行うことを特徴とする請求項２に記載の画像形成装置。
【請求項１０】
着目スキャンラインを、その直前のスキャンラインとの差分画素の位置及び長さと、その位置に描画されるグラフィックオブジェクトの識別子とで定義した中間コードを、入力画像データから生成する中間コード生成手段を更に備え、
前記決定手段は、前記中間コードに応じて差分画素の位置を決定することを特徴とする請求項１に記載の画像形成装置。
【請求項１１】
着目スキャンラインを、その直前のスキャンラインとの差分画素の位置及び長さと、その位置に描画されるグラフィックオブジェクトの識別子とで定義した中間コードを、入力画像データから生成する中間コード生成手段を更に備え、
前記決定手段は、前記中間コードに応じて差分画素の位置を決定することを特徴とする請求項１に記載の画像形成装置。
【請求項１２】
前記決定手段は、着目スキャンライン毎に、そのスキャンライン上にあるグラフィックオブジェクトのリストを作成する作成手段と、作成したリストに基づいて着目スキャンラインとその直前のスキャンラインとの差分画素を決定し、
前記差分更新手段は、前記リストに属するグラフィックオブジェクトで与えられる前記差分画素の値を、前記ラインメモリの相当位置に記録することを特徴とする請求項１に記載の画像形成装置。
【請求項１３】
前記フレームメモリは、１ページ相当のドットイメージデータを格納することを特徴とする請求項１乃至８のいずれか１項に記載の画像形成装置。
【請求項１４】
前記フレームメモリは、１バンド相当のドットイメージデータを格納することを特徴とする請求項１乃至８のいずれか１項に記載の画像形成装置。
【請求項１５】
前記１画像中のすべてのグラフィックオブジェクトについてそのドットイメージのフレームメモリへの合成を行った後、前記フレームメモリのドットイメージデータを、印刷媒体上に画像として形成することを特徴とする請求項９乃至１４のいずれか１項に記載の画像形成装置。
【請求項１６】
フレームメモリにグラフィックスオブジェクトを描画するための画像形成方法であって、
ラインメモリに保存された、グラフィックスオブジェクトのスキャンラインとその直後の着目スキャンラインにおいて対応する画素の値が異なる差分画素の位置を決定する決定工程と、
前記ラインメモリに保存されたドットイメージデータのうち、前記決定工程により決定された差分画素の値を、前記着目ラインにおける画素の値に更新する差分更新工程と、
前記ラインメモリのドットイメージデータを、前記着目スキャンラインに相当する前記フレームメモリの位置に合成する合成工程と
を備えることを特徴とする画像形成方法。
【請求項１７】
請求項１乃至１５のいずれか１項に記載の画像形成装置をコンピュータにより実現するためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２００６−７２８３４（Ｐ２００６−７２８３４Ａ）
【公開日】平成１８年３月１６日（２００６．３．１６）
【国際特許分類】
【出願番号】特願２００４−２５７４２１（Ｐ２００４−２５７４２１）
【出願日】平成１６年９月３日（２００４．９．３）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成１８年３月１６日（２００６．３．１６）
【国際特許分類】
【出願日】平成１６年９月３日（２００４．９．３）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]