画像形成装置及び画像形成方法ならびに画像形成方法を実行するプログラム
【課題】 レンダリングのエッジ処理において、ページ内に大量のエッジが存在するデータを処理する場合、エッジ情報をロードした時点でＣＰＵキャッシュに格納される。
しかし、他のエッジをロードしているとＣＰＵキャッシュから溢れ、次にエッジ情報を用いてエッジ処理を行う際、メインメモリから情報をロードするので処理に時間がかかってしまう課題がある。
【解決手段】 これまでは、１スキャンライン分のエッジ情報を保持し処理していたのを、２つ以上のブロックに分割しそれぞれのブロックでエッジ情報を保持し処理することにより、近接するエッジが近接するメモリ上に保持される可能性が高くになる。その結果、キャッシュにミスヒット率が低下し処理速度の向上をはかることが出来る。
しかし、他のエッジをロードしているとＣＰＵキャッシュから溢れ、次にエッジ情報を用いてエッジ処理を行う際、メインメモリから情報をロードするので処理に時間がかかってしまう課題がある。
【解決手段】 これまでは、１スキャンライン分のエッジ情報を保持し処理していたのを、２つ以上のブロックに分割しそれぞれのブロックでエッジ情報を保持し処理することにより、近接するエッジが近接するメモリ上に保持される可能性が高くになる。その結果、キャッシュにミスヒット率が低下し処理速度の向上をはかることが出来る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディスプレイリストのエッジ処理制御方法を有する画像形成装置及び画像形成方法ならびに画像形成方法を実行するプログラムに関するものである。
【背景技術】
【０００２】
従来、ホストコンピュータ上で実行される描画アプリケーションを用いて生成された描画データをプリンタで印刷する場合、ホストコンピュータは描画データをＰＤＬ（Ｐａｇｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｌａｎｇｕａｇｅ）と呼ばれる印刷データの形式でプリンタへ送信する。ＰＤＬには描画データにおける、文字、グラフィック、イメージ等を印刷する際に必要となる印刷情報が含まれている。
【０００３】
ＰＤＬを受信したプリンタは、ＰＤＬの解析を行いＤＬ（Ｄｉｓｐｌａｙ Ｌｉｓｔ）と呼ばれる中間データに変換し、中間データに基づいてレンダリング処理を行う。レンダリング処理の方法は幾つか存在するが、例えば、特許文献１では印刷データを主走査方向に１ライン毎に読み込みレンダリングを行うスキャンラインレンダリングという方法がある。スキャンラインレンダリングは、ページ内に描画するオブジェクトとオブジェクト、またはオブジェクトと背景の境目を指すエッジに関する情報を基にレンダリングを行う。スキャンラインレンダリングを行うためには、１ライン分のエッジ情報をメモリにロードする必要となる。
【０００４】
１ライン分のエッジ情報をメモリにロードするとは、図４（ａ）の太線に示すように処理中のスキャンラインにおけるページ幅（Ｘ＝０〜４０００）に現れるエッジ情報の全てを１つのメモリ領域に保持することである。この状態をメモリ上で格納した場合、図５（ａ）に示すようになり、点線で囲んだ透過な矩形領域がＣＰＵのキャッシュ有効領域となる。エッジ情報は、アドレス番号が０ｘ７８２０００００から０ｘ７８Ｂ０００００のどこかのメモリ領域内に格納されることを示している。
【０００５】
このように、スキャンラインレンダリング処理を行う場合エッジ情報のロードを行う他に、エッジのリンクソート及びエッジとエッジ間の距離を算出する差分抽出処理を行うことになる。上述の処理を高速に行うためには、ＣＰＵのキャッシュ内にエッジ情報をロードした際に、次に処理するエッジの情報がキャッシュ内のエッジ情報領域内に格納されている状態が理想である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−１３７８２５
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、近年、アプリケーションの描画能力向上に伴い、エッジ数が多いデータが増えてきており、レンダリングにおけるエッジ処理に時間がかかることが問題になっている。
【０００８】
この問題に対し特許文献１の発明では、エッジ処理を１ライン毎に行っているためエッジ数が多いデータに対してキャッシュミスヒットと呼ばれる現象が起こる可能性がある。キャッシュミスヒットは、キャッシュ内にエッジ情報が存在しないためエッジ情報が格納されている領域からロードしなくてはいけない。このためレンダリング処理を高速に行うことはできない。
【課題を解決するための手段】
【０００９】
上記課題を解決するための本発明の画像形成装置は、描画データに基づいて１ライン毎にレンダリングする画像形成装置において、レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶し、前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートすることを特徴とする。
【発明の効果】
【００１０】
エッジ数が多い複雑なデータの場合においても、ＣＰＵのキャッシュミスヒットを削減でき高速にエッジ処理することを可能にする。
【図面の簡単な説明】
【００１１】
【図１】実施形態における各機器のコントロールユニットの構成例を示すブロック図
【図２】実施形態におけるシステム構成の一例を示す図
【図３】実施形態におけるコントローラソフトウェアの構成の一例を示すブロック図
【図４】実施形態におけるページ内のブロック分割の一例を示す図
【図５】実施形態におけるエッジ情報のメモリ配置の一例を示す図
【図６】実施形態におけるスキャンライン毎のエッジ処理の一例を示す図
【図７】実施形態におけるエッジ処理を含んだレンダリング処理の一例を示すフロー図
【図８】実施形態におけるブロックのカバー範囲変更の一例を示す図
【図９】実施形態におけるブロックの分割の一例を示す図
【図１０】実施形態におけるブロックの結合の一例を示す図
【図１１】実施形態におけるエッジのブロック間移動とリンクのソートの一例を示す図
【発明を実施するための形態】
【００１２】
以下、本発明を実施するための最良の形態について図面を用いて説明する。
【実施例１】
【００１３】
＜コントローラユニットの構成＞
図１は、本実施形態におけるＭＦＰ（Ｍｕｌｔｉ Ｆｕｎｃｔｉｏｎ Ｐｅｒｉｐｈｅｒａｌ）のコントロールユニットの構成を示すブロック図である。図１において、コントロールユニット２００は、画像入力デバイスであるスキャナ２０１や画像出力デバイスであるプリンタエンジン２０２と接続し、画像データの読み取りやプリント出力のための制御を行う。また、コントロールユニット２００は、ＬＡＮ Ｎ１や公衆回線２０４と接続することで、画像情報やデバイス情報をＬＡＮ Ｎ１経由で入出力するための制御を行う。プリンタエンジン２０２は２１７のデバイスＩ／Ｆと結合され、コントローラユニット２００で生成された描画データを紙に出力する処理を行う。
【００１４】
システムバス２１３には、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）２０５、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）２０６、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）２０７、ＨＤＤ（Ｈａｒｄ Ｄｉｓｃ Ｄｒｉｖｅ）２０８、操作部Ｉ／Ｆ２０９、ネットワークＩ／Ｆ２１１、モデム２１２、イメージパスＩ／Ｆ２１４が接続されている。ＣＰＵ２０５はＭＦＰ全体を制御するための中央処理装置である。ＲＡＭ２０６は、ＣＰＵ２０５が動作するためのシステムワークメモリであり、入力された画像データを一時記憶するための画像メモリでもある。さらに、ＲＯＭ２０７はブートＲＯＭであり、システムのブートプログラムが格納されている。ＨＤＤ２０８はハードディスクドライブであり、各種処理のためのシステムソフトウェア及び入力された画像データを等格納する。操作部Ｉ／Ｆ２０９は、画像データ等を表示可能な表示画面を有する操作部２１０に対するインタフェース部であり、操作部２１０に対して操作画面データを出力する。また、操作部Ｉ／Ｆ２０９は、操作部２１０から操作者が入力した情報をＣＰＵ２０５に伝える役割をする。ネットワークＩ／Ｆ２１１は、例えばＬＡＮカード等で実現され、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）Ｎ１に接続して外部装置との間で情報の入出力を行う。モデム２１２は公衆回線２０４に接続し、外部装置との間で情報の入出力を行う。以上のユニットがシステムバス２１３上に配置されている。イメージバスＩ／Ｆ２１４は、システムバス２１３と画像データを高速で転送する画像バス２１５とを接続するためのインタフェースであり、データ構造を変換するバスブリッジである。
【００１５】
画像バス２１５上には、ラスタイメージプロセッサ２１６、デバイスＩ／Ｆ２１７、スキャナ画像処理部２１８、プリンタ画像処理部２１９、画像編集用画像処理部２２０、カラーマネージメントモジュール２３０が接続されている。
【００１６】
ＲＩＰ（Ｒａｓｔｅｒ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｏｒ）２１６は、ＰＤＬデータや後述するベクトルデータをイメージデータとして展開する。デバイスＩ／Ｆ部２１７は、スキャナ２０１及びプリンタエンジン２０２とコントロール２００とを接続し、画像データの同期系／非同期系の変換を行う。
【００１７】
また、スキャナ画像処理部２１８は、スキャナ２０１から入力した画像データに対して、補正、加工、編集等の各種画像処理を行う。プリンタ画像処理部２１９は、プリント出力する画像データに対して、プリンタエンジンに応じた補正及び解像度変換等の処理を行う。画像編集用画像処理２２０は、画像データの回転や、画像データの圧縮伸長処理等の各種画像処理を行う。ＣＭＭ２３０は、画像データに対して、プロファイルやキャリブレーションデータに基づいた、色変換処理（色空間変換処理ともいう）を施す専用ハードウェアモジュールである。プロファイルとは、機器に依存した色空間で表現したカラー画像データを機器に依存しない色空間（例えばＬａｂなど）に変換するための関数のような情報である。キャリブレーションデータとは、カラー複合機３におけるスキャナ部２０１やプリンタエンジン２０２の色再現特性を修正するためのデータである。
【００１８】
次に、プリンタエンジン２０２の一例である１Ｄカラー系ＭＦＰ（Ｍｕｌｔｉ Ｆｕｎｃｔｉｏｎ Ｐｅｒｉｐｈｅｒａｌ：マルチファンクション周辺機器）の構成について説明する。
【００１９】
１Ｄカラー系ＭＦＰは、スキャナ部、レーザ露光部、感光ドラム、作像部、定着部、給紙／搬送部及び、これらを制御する不図示のプリンタ制御部から構成される。
【００２０】
スキャナ部は、原稿台に置かれた原稿に対して、照明を当てて原稿画像を光学的に読み取り、その像を電気信号に変換して画像データを作成する工程である。
【００２１】
レーザ露光部は、前記画像データに応じて変調されたレーザ光などの光線を等角速度で回転する回転多面鏡（ポリゴンミラー）に入射させ、反射走査光として感光ドラムに照射する。
【００２２】
作像部は、感光ドラムを回転駆動し、帯電器によって帯電させ、前記レーザ露光部によって感光ドラム上に形成された潜像をトナーによって現像化し、そのトナー像をシートに転写する。その際に転写されずに感光ドラム上に残った微小トナーを回収するといった一連の電子写真プロセスを実行して作像する。その際、シートが転写ベルトの所定位置に巻きつき、４回転する間に、マゼンタ（Ｍ）、シアン（Ｃ）、イエロー（Ｙ）、ブラック（Ｋ）のトナーを持つそれぞれの現像ユニット（現像ステーション）が入れ替わりで順次前述の電子写真プロセスを繰り返し実行する。４回転の後、４色のフルカラートナー像を転写されたシートは、転写ドラムを離れ、定着部へ搬送される。
【００２３】
定着部は、ローラやベルトの組み合わせによって構成され、ハロゲンヒータなどの熱源を内蔵し、前記作像部によってトナー像が転写されたシート上のトナーを、熱と圧力によって溶解、定着させる。
【００２４】
給紙／搬送部は、シートカセットやペーパーデッキに代表されるシート収納庫を一つ以上持っており、前記プリンタ制御部の指示に応じてシート収納庫に収納された複数のシートの中から一枚分離し、作像部・定着部へ搬送する。シートは作像部の転写ドラムに巻きつけられ、４回転した後に定着部へ搬送される。４回転する間に前述のＹＭＣＫ各色のトナー像がシートに転写される。また、シートの両面に画像形成する場合は、定着部を通過したシートを再度作像部へ搬送する搬送経路を通るように制御する。
【００２５】
プリンタ制御部は、ＭＦＰ全体を制御するＭＦＰ制御部と通信して、その指示に応じて制御を実行すると共に、前述のスキャナ、レーザ露光、作像、定着、給紙／搬送の各部の状態を管理しながら、全体が調和を保って円滑に動作できるよう指示を行う。
【００２６】
＜システム構成＞
次に、画像処理システムの構成について詳細に説明する。図２は、本実施形態に係る画像処理システムの全体構成を示すブロック図である。図２において、画像処理システムは、互いにＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）Ｎ１等を介して接続された、ＭＦＰ１、ＭＦＰ２、ＭＦＰ３で構成されている。
【００２７】
各ＭＦＰはそれぞれＨＤＤＨ１、Ｈ２、Ｈ３を具備している。ＭＦＰに搭載されているプリンタエンジン（以降、エンジン）の解像度はＭＦＰ毎に異なっており、ＭＦＰ１とＭＦＰ３は６００ｄｐｉ、ＭＦＰ２は１２００ｄｐｉである。また、ＭＦＰに搭載されているレンダラ（ラスタライザ）の種類もＭＦＰ毎に異なっており、ＭＦＰ１とＭＦＰ２のレンダラは同種（図中には「Ｒａ」と図示）、ＭＦＰ３だけ異なる種類（「Ｒｂ」と図示）である。一般にレンダラはＡＳＩＣなどのハードウェアで構成されるため、異なる種類のレンダラは異なる種類の描画命令群を処理することができない。この描画命令群を一般にディスプレイリストと呼ぶ。ディスプレイリストはハードウェアで処理可能なインストラクション（命令）であり、複雑な描画記述を持つベクタデータからソフトウェアで生成されるものであり、解像度に依存している。
【００２８】
ＭＦＰ１、ＭＦＰ２、ＭＦＰ３は、ネットワークプロトコルを使用して互いに通信することができる。なお、ＬＡＮ Ｎ１上に接続されるこれらのＭＦＰは上記のような物理的な配置に限定されなくても良い。また、ＬＡＮ Ｎ１上にはＭＦＰ以外の機器（例えばＰＣ、各種サーバ、プリンタなど）が接続されていても良い。
【００２９】
＜コントローラソフトウェア構成＞
次に、ＭＦＰの動作を制御するコントローラソフトウェアについて詳細に説明する。図３は、コントローラソフトウェアの構成を示すブロック図である。
プリンタインターフェイス４００は、外部との入出力のための手段である。プロトコル制御部４０１は、ネットワークプロトコルを解析・送信することによって外部との通信を行う手段である。
【００３０】
ＰＤＬデータ解析部４０２は、ＰＤＬデータを解析し、より処理しやすい形式のディスプレイリストに変換する手段である。ＰＤＬデータ解析部４０２において生成されたディスプレイリストはデータ描画部４０３に渡されて処理される。データ描画部４０３は上記ディスプレイリストをビットマップデータに展開するものであり、展開されたビットマップデータはページメモリ４０４に逐次描画されて行く。ＰＤＬデータ解析部４０２及びデータ描画部４０３は、ＲＯＭに格納されたプログラムを用いてＣＰＵにより実行されることで実現される。
【００３１】
ページメモリ４０４はレンダラが展開するビットマップデータを一次的に保持する揮発性のメモリである。
【００３２】
パネル入出力制御部は操作パネルからの入出力を制御するものである。
ドキュメント記憶部４０６はデータファイルを記憶する手段であり、ハードディスク等の二次記憶装置によって実現される。
スキャン制御部４０７はスキャナから入力した画像データに対して、補正、加工、編集などの各種処理を行う。
【００３３】
印刷制御部４０８は、ページメモリ４０４の内容をビデオ信号に変換処理し、プリンタエンジン部４０９へ画像転送を行う。プリンタエンジン部１４００は受け取ったビデオ信号を記録紙に永久可視画像形成するための印刷機構部である。
【００３４】
＜エッジ情報保持方法＞
本発明のエッジ情報の保持方法について、図５を用いて詳細に説明する。
メモリ領域は、入力されたディスプレイリストに確保されている場合や、ある固定領域に保持されている場合などが考えられる。メモリ領域のサイズは、ディスプレイリスト内に含まれるエッジ数を元に算出される場合や、ＭＦＰ全体で使用可能なメモリサイズのうち、レンダリング処理に使用可能なサイズがあらかじめ設定される。
【００３５】
エッジ数を元に算出される具体的なサイズとしては、１スキャンラインで最大ロードされるエッジ数に１つのエッジサイズをかけた値となる。１つのエッジサイズはエッジによって異なるが、最大でも１つのエッジ当たり約６０バイトとなるので、１スキャンラインに含まれる最大エッジ数が５００個だった場合、約３０ｋｂｙｔｅとなる。
【００３６】
本発明は、図４（ｂ）の二つの太線に示すように、ページ幅をＸ＝０〜２０００までとＸ＝２００１〜４０００までの二つのブロックに分割し、処理中のスキャンラインにおける各ブロック内に現れるエッジ情報をそれぞれの領域に保持し処理を行うことを特徴とする。
【００３７】
これをメモリ上ではどのようにデータが格納されるかを示した図が図５（ｂ）になり、点線で囲んだ透過な矩形領域がキャッシュ有効領域の例である。ページ幅がＸ＝０〜２０００に現れるエッジは、０ｘ７８００００００から０ｘ７８６０００００のアドレスが連続した領域に格納される。また、ページ幅がＸ＝２００１〜４０００に現れるエッジは、０ｘ７８６０００００から０ｘ７８Ｂ０００００のアドレスが連続した領域に格納されることを示している。
【００３８】
メモリ領域の分割方法としては、各ブロックに含まれるエッジ数が同じと仮定して、単純にブロックの個数分に分割する方法が考えられる。また、ブロックが２つの場合、一つ目のブロックに含まれるエッジ情報はメモリの先頭アドレスから、二つ目のブロックに含まれるエッジ情報は最終アドレスから使用する方法も考えられる。
【００３９】
隣り合うエッジが格納されているブロックが１つの場合、図５（ａ）に示すように０ｘ００８０００００番地分離れる可能性があったが、二つのブロックの場合は、図５（ｂ）に示すように最悪でも０ｘ００４０００００番地離れるのにとどまる。その為、キャッシュ効率のよいエッジ処理を行うことが可能になる。
【００４０】
＜レンダリングにおけるエッジ処理とは＞
ここでレンダリングにおけるエッジ処理について図６を用いて説明する。
【００４１】
まずエッジとは、ページ内に描画するオブジェクトとオブジェクト、またはオブジェクトと背景の境目を指す。
【００４２】
エッジ処理とは、メモリ上へのエッジ情報のロード、処理中のスキャンラインにおけるＸ座標の算出、処理中のエッジと隣のエッジ間の距離の算出、エッジが現れる順番を保持するリンクの更新、エッジ情報の削除の５つが大きな処理となる。
【００４３】
また、エッジ情報は、図６の右下の四角内にかかれるような項目が含まれる。
図６のエッジ処理を説明する図には、三角形と四角形のオブジェクトが書かれており、先ほど述べたように、領域はブロック１とブロック２の二つの領域に分割されている。
【００４４】
エッジ処理はページの上から下に向かってスキャンライン毎に処理を行っていくが、まずページの先頭から三角形の頂点が現れるまではエッジが存在しないので何も行わない。
【００４５】
三角形がページの右側に現れるスキャンライン（図６の「１、２追加」部分）を処理した場合、エッジ１の情報とエッジ２の情報がブロック２のメモリ上にロードされる。
【００４６】
ここでエッジ情報のメモリロードについて説明する。ディスプレイリストには、エッジの開始座標が記されているので、この開始座標、ブロック１が含まれる座標、ブロック２が含まれる座標を元にどのブロックにエッジがロードするか判断する。また、エッジ１が左、エッジ２が右にあるので、エッジは１→２の順にリンクされる。
【００４７】
処理を進めていくと、エッジ１がブロック２の領域からブロック１領域へ移動する（図６の「１ブロック移動」部分）のでエッジ１が属している領域情報をブロック２からブロック１へ変更する。
【００４８】
次に、四角形がブロック１とブロック２にまたがって現れるスキャンライン（図６の３、４追加」部分）を処理した場合、エッジ３の情報をブロック１のメモリ上に、エッジ４をブロック２のメモリ上に追加する。この場合、エッジ３がエッジ１の左側にあるので、ブロック１のエッジは３→１、ブロック２のエッジは４→２の順にリンクされる。
【００４９】
次に三角形がなくなるスキャンライン（図６の「１、２削除」部分）を処理した場合、エッジ１とエッジ２が消滅するので、エッジ１の情報とエッジ２の情報をメモリ上から削除する。
【００５０】
次に四角形がなくなるスキャンライン（図６の「３、４削除」部分）を処理した場合、エッジ３とエッジ４が消滅するので、エッジ３の情報とエッジ４の情報をメモリ上から削除する。
【００５１】
エッジ３、エッジ４が削除されたスキャンラインからページの一番下のスキャンラインまではエッジが現れないのでエッジ処理は行われない。
【００５２】
また本処理において、各ブロックを分割する境目をエッジとして扱い、ブロック１に含まれるエッジリストの最後とブロック２に含まれるエッジリストの先頭に新たなエッジを追加して処理を行っても構わない。
【００５３】
以上がレンダリングにおける基本的なエッジ処理の流れになる。
【００５４】
＜データ処理フロー＞
次に、図７を使って本特許におけるレンダリング処理を行うプログラムのフローについて説明する。このプログラムは、図１の２０５のＲＡＭにロードされ、２０５のＣＰＵ上で動作する。
【００５５】
Ｓ７０１は本処理の開始を示す。Ｓ７０２において、本処理におけるブロックの個数、カバー範囲を決める為の情報と、処理を行うディスプレイリストを入力する。
【００５６】
次にＳ７０３において、ブロック個数やカバー範囲の初期値を決定する。Ｓ７０４はスキャンラインのループ端になり、１スキャンライン処理する毎にＳ７２４からこのループ端に戻り、処理するスキャンラインがページの最終スキャンラインまでこのループが繰り返される。
【００５７】
Ｓ７０５は処理を行うブロックのループ端になり、１ブロックに含まれるエッジ処理が終了する毎にＳ７２２からこのループ単に戻り、処理するブロックがページに一番右側のブロックまでこのループが繰り返される。
【００５８】
Ｓ７０６において、処理を行うディスプレイリストの解釈を行う。Ｓ７０７において、Ｓ７０６の結果、処理中のブロックにおいて、エッジの追加、またはエッジの削除があるか判断する。Ｓ７０７の結果がＮＯの場合Ｓ７１５の処理を行う。Ｓ７０７の結果がＹＥＳの場合、Ｓ７０８において、エッジのロード処理、または削除処理を行い、ブロックに関するパラメータの更新を行う。
【００５９】
Ｓ７０９において、ブロックに関するパラメータのうちブロック間のエッジ数の偏りがＳ７０３で決定した閾値より大きいか判断する。Ｓ７０９の結果がＮＯだった場合、Ｓ７１１の処理を行う。Ｓ７０９の結果がＹＥＳだった場合、Ｓ７１０において、各ブロックに含まれるエッジ数の偏りが等しくなるようにブロックがカバーする範囲を変更し、ブロック間のエッジ数の偏り値を更新する。この処理の詳細は後述する＜ブロックのカバー範囲変更＞で説明する。
【００６０】
Ｓ７１１において、ブロック内のエッジ数がＳ７０３で決定した上限より大きいか判断する。Ｓ７１１の結果がＮＯだった場合、Ｓ７１３の処理を行う。Ｓ７１１の結果がＹＥＳだった場合、Ｓ７１２において、ブロックの分割処理を行い１ブロックに含まれるエッジ数の削減を行う。この処理の詳細は＜ブロックの分割＞で説明する。
【００６１】
次にＳ７１３において、ブロック内のエッジ数がＳ７０３で決定した下限より小さいか判断する。Ｓ７１３がＮＯだった場合Ｓ７１５の処理を行う。Ｓ７１３の結果がＹＥＳだった場合、Ｓ７１４において、ブロックの結合処理を行い１ブロックに含まれるエッジ数の最適化を行う。この処理の詳細は＜ブロックの結合＞で説明する。
【００６２】
次にＳ７１５において、処理中のブロックに含まれる全てのエッジに対して、次のスキャンラインにおけるＸ座標の算出を行い、エッジ同士が交差する場合、リンクの入れ替え（リンクソート）を行う。
ここで、エッジダーティーとフリーフォールという概念について説明する。処理を行うスキャンラインにおいて、エッジの追加ｏｒ削除がない、かつ、エッジの交差がないスキャンラインをフリーフォールのスキャンラインといい、それ以外のスキャンラインをエッジダーティーのスキャンラインという。つまりＳ７０７からＳ７１３の処理はエッジダーティー時のみ行われる処理である。
【００６３】
次にＳ７１６においてＳ７１５の結果、属するブロックが変わるエッジがあった場合、元のブロックのリンクから切り離し、移動先のブロックのリンクに追加する。この際、移動元、移動先それぞれのブロックに関してリンクの並び替え処理を行う。この処理の詳細は＜エッジのブロック間移動＞で説明する。
【００６４】
Ｓ７１８において、エッジ処理が終わった描画データの上下関係を判断し、描画するオブジェクトを選択するレベル処理を行う。次にＳ７１９において、Ｓ７１８で選択されたオブジェクトの塗り情報を生成するフィル生成処理を行い、Ｓ７２０でオブジェクト同士の重ね合わせであるコンポジット処理を行う。
【００６５】
Ｓ７２１において、処理を行うブロックを現在のブロックから一つ右のブロックへ移動する。Ｓ７２２はＳ７０５に対応するブロックに関するループ端になる。処理中のスキャンラインにおける全ブロックの処理が終了したら、Ｓ７２３において処理を行うスキャンラインを現在のスキャンラインから一つ下のスキャンラインに移動する。Ｓ７２４はＳ７０４に対応するスキャンラインに関するループ端になる。全スキャンラインに対する処理が終了したらＳ７２５でレンダリング処理を終了する。
【００６６】
＜ブロックのカバー範囲変更＞
ここで図８を用いて「データ処理フロー」のＳ７０９、Ｓ７１０で説明した、ブロックのカバー範囲変更についての詳細を述べる。
【００６７】
ｄ８０１は図４（ｂ）で述べたようにＸ＝０〜２０００、Ｘ＝２００１〜４０００までの二つのブロック（ブロック１、ブロック２）に分割して処理している。ｄ８０２に示すようにＹ＝０〜２０００まではブロック１、ブロック２共に同じ位の数のエッジが現れている。
【００６８】
どの位の割合でブロックにエッジが含まれるかを示す例として、ｄ８０２の表「偏り値」を説明する。「偏り値」が１だとブロック間でエッジ数がちょうど等分、１より少ないと他のブロックに比べてエッジ数が少ない、１より多いと他のブロックに比べてエッジ数が多いことを示す。「偏り値」算出方法の一例としては、
（ブロック内のエッジ数×ブロック数）／スキャンライン内の総ブロック数
で計算することが出来る。この場合偏り値は、０から２の間のいずれかの値がとられることになる。
【００６９】
次にｄ８０３に示すように、点線部の２００１スキャンライン目のブロック２には、家の屋根のエッジが大量に現れる。
【００７０】
ｄ８０４に示すようにエッジ数はブロック１が１０個に対し、ブロック２が４９０個となり、それぞれの偏り値はブロック１が０．０４に対し、ブロック２が１．９６となる。よって、「データ処理フロー」のＳ７０３で設定した閾値例（１．３）を越えたのでブロックのカバー範囲を変更する処理を行う。
【００７１】
その結果、ｄ８０５に示すように、ブロックのカバーする範囲をエッジ数が少ないブロック１を広げ、エッジ数が多いブロック２を狭める範囲の変動処理を行う。詳細はｄ８０６に示すように、Ｘ＝０〜３３００までがブロック１、Ｘ＝３３０１〜４０００までがブロック２とすると、各ブロックに含まれるエッジ数がちょうど半分ずつの２５０個ずつとなり、また、偏り値もそれぞれ１となりエッジ数が均等になる。
【００７２】
＜ブロックの分割＞
次に図９を用いて「データ処理フロー」のＳ７１２で説明した、ブロックの分割についての詳細を述べる。
【００７３】
ｄ９０１は＜ブロックのカバー範囲変更＞で述べたようにＹ＝０〜２０００まではＸ＝０〜２０００、Ｘ＝２００１〜４０００の二つのブロックで処理をしていた。また、Ｙ＝２００１〜５０００までは、Ｘ＝０〜３３００、Ｘ＝３３０１〜４０００までの二つのブロックに分割して処理していた。Ｙ＝０〜５０００までの各ブロック内に現れるエッジ数はｄ９０２に示すように最大でも３００個だった。
【００７４】
次にｄ９０３に示されるように、点線部の５００１スキャンライン目のブロック２には、木の葉っぱのエッジが大量現れる。その個数はｄ９０４に示されるように、６００個で、「データ処理フロー」のＳ７０３で設定した１ブロックに含まれる最大個数例（５００個）を越えるのでブロック２はブロック２とブロック３に分割される。
【００７５】
その結果、ｄ９０４に示すように、各ブロックのエッジ数は、ブロック１は２８０個、ブロック２は２５０個、ブロック３は３５０個となり、いずれも１ブロックの上限である５００個を下回った。もし１度分割しても上限を下回らない場合、再度ブロックの分割を行う。
【００７６】
＜ブロックの結合＞
次に図１０を用いて「データ処理フロー」のＳ７１４で説明した、ブロックの結合についての詳細を述べる。
【００７７】
ｄ１００１の点線部分は＜ブロックの分割＞で述べたようにＹ＝５０００〜６５００まではＸ＝０〜２０００、Ｘ＝３３０１〜３６５０、Ｘ＝３６５１〜４０００までの三つのブロックで処理をしていた。ｄ１００２に示すようにエッジ数、偏り値はＳ７０３で決定した閾値より小さかった。
【００７８】
次にｄ１００３に示されるように、点線部の６５０１スキャンライン目のブロック１、ブロック２、ブロック３は家や木の葉っぱのエッジが削除される。その個数はｄ１００４に示されるように、ブロック１は１５個、ブロック２は１０個、ブロック３は１０個であった。この数は「データ処理フロー」のＳ７０３で設定した１ブロックに含まれる最小個数（１２個）を下回るのでブロック２とブロック３はブロック２として結合される。
【００７９】
その結果、ｄ１００６に示すように、各ブロックのエッジ数は、ブロック１は１５個、ブロック２は２０個となり、いずれも１ブロックの下限である１２個を上回った。もし１度結合しても下限を上回らない場合、再度ブロックの結合を行う。
【００８０】
＜エッジのブロック間移動＞
次に図１１を用いて「データ処理フロー」のＳ７１６で説明した、エッジのブロック間移動に伴うソートについての詳細を述べる。
【００８１】
ｄ１１０１は描画されるページの例を示している。エッジ１、２を持つグレーの矩形がブロック１に、エッジ３、４を持つグラデーションの円と、エッジ５、６を持つ網点の三角形がブロック２に含まれている。
【００８２】
ｄ１１０２には着目スキャンラインにおけるエッジのリンクを示している。
【００８３】
まずＹ＝１０００ライン目におけるエッジリンクは、ブロック１はエッジ１が左側に、エッジ２が右側にあるので、１→２の順にリンクされる。同様にブロック２は左からエッジ３、５、６、４の順に現れるので、３→５→６→４の順にリンクされる。次のスキャンラインＹ＝１００１ライン目のＸ座標を計算したところ、エッジ５の座標がＸ＝１８００になったので、エッジ５はブロック２から１へ移動することがわかる。そこで、エッジ５はブロック２のリンクから切り離しブロック１のリンクにつなげ、Ｘ座標順にリンクをソートすると、１→５→２の順のリンクになる。また、ブロック２はエッジ５が抜けたので、エッジ３とエッジ６をリンクした結果、３→６→４の順のリンクになる。
【００８４】
エッジがブロック間を移動した場合、メモリ上にロードされているエッジ情報がブロック１からブロック２の領域にコピーされる場合と、エッジ情報はコピーされずにリンクのみが更新される場合の二通りが考えられる。
【００８５】
前者はコピーを行う処理時間がかかるが、その後のエッジ処理においてはキャッシュ上で処理できるという点が上げられる。一方、後者はコピーを行わないのでその時間はかからないが、その後のエッジ処理においてはキャッシュ上で処理されない点が上げられる。どちらの方法が効率的かはエッジデータの長さや種類に依存する。
【００８６】
このように、ページ内でエッジ数の偏りがあった場合も、領域を可変することにより安定した速度で処理を行うことが可能になる。
【００８７】
（他の実施形態）
以上、様々な実施形態を詳述したが、本発明は、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。例えば、スキャナ、プリンタ、ＰＣ、複写機、複合機及びファクシミリ装置の如くである。
【００８８】
本発明は、前述した実施形態の各機能を実現するソフトウェアプログラムを、システム若しくは装置に対して直接または遠隔から供給し、そのシステム等に含まれるコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される。
【００８９】
従って、本発明の機能・処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、上記機能・処理を実現するためのコンピュータプログラム自体も本発明の一つである。
【００９０】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等、プログラムの形態を問わない。
【００９１】
プログラムを供給するための記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷなどがある。また、記録媒体としては、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ、ＤＶＤ−Ｒ）などもある。
【００９２】
また、プログラムは、クライアントコンピュータのブラウザを用いてインターネット／イントラネットのウェブサイトからダウンロードしてもよい。すなわち、該ウェブサイトから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードしてもよいのである。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるウェブサイトからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明の構成要件となる場合がある。
【００９３】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布してもよい。この場合、所定条件をクリアしたユーザにのみ、インターネット／イントラネットを介してウェブサイトから暗号化を解く鍵情報をダウンロードさせ、その鍵情報で暗号化されたプログラムを復号して実行し、プログラムをコンピュータにインストールしてもよい。
【００９４】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現されてもよい。なお、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行ってもよい。もちろん、この場合も、前述した実施形態の機能が実現され得る。
【００９５】
また、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれてもよい。そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ってもよい。このようにして、前述した実施形態の機能が実現されることもある。
【００９６】
さらに、実施例１の領域分割をブロック毎としたが、１ライン毎に領域を分割しても良い。この場合、エッジ数がより多い描画データに対して有効である。
【符号の説明】
【００９７】
２００ コントロールユニット
２０１ スキャナ
２０２ プリンタエンジン
２１０ 操作部
３０１ ジョブコントロール処理
４００ プロトコル制御部
４０１ ベクタデータ生成部
４０２ ＰＤＬデータ解析部
４０３ データ描画部
４０４ ページメモリ
４０５ パネル入出力制御部
４０６ ドキュメント記憶部
４０７ スキャン制御部
４０８ 出力制御部
４０９ プリンタエンジン部
【技術分野】
【０００１】
本発明は、ディスプレイリストのエッジ処理制御方法を有する画像形成装置及び画像形成方法ならびに画像形成方法を実行するプログラムに関するものである。
【背景技術】
【０００２】
従来、ホストコンピュータ上で実行される描画アプリケーションを用いて生成された描画データをプリンタで印刷する場合、ホストコンピュータは描画データをＰＤＬ（Ｐａｇｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｌａｎｇｕａｇｅ）と呼ばれる印刷データの形式でプリンタへ送信する。ＰＤＬには描画データにおける、文字、グラフィック、イメージ等を印刷する際に必要となる印刷情報が含まれている。
【０００３】
ＰＤＬを受信したプリンタは、ＰＤＬの解析を行いＤＬ（Ｄｉｓｐｌａｙ Ｌｉｓｔ）と呼ばれる中間データに変換し、中間データに基づいてレンダリング処理を行う。レンダリング処理の方法は幾つか存在するが、例えば、特許文献１では印刷データを主走査方向に１ライン毎に読み込みレンダリングを行うスキャンラインレンダリングという方法がある。スキャンラインレンダリングは、ページ内に描画するオブジェクトとオブジェクト、またはオブジェクトと背景の境目を指すエッジに関する情報を基にレンダリングを行う。スキャンラインレンダリングを行うためには、１ライン分のエッジ情報をメモリにロードする必要となる。
【０００４】
１ライン分のエッジ情報をメモリにロードするとは、図４（ａ）の太線に示すように処理中のスキャンラインにおけるページ幅（Ｘ＝０〜４０００）に現れるエッジ情報の全てを１つのメモリ領域に保持することである。この状態をメモリ上で格納した場合、図５（ａ）に示すようになり、点線で囲んだ透過な矩形領域がＣＰＵのキャッシュ有効領域となる。エッジ情報は、アドレス番号が０ｘ７８２０００００から０ｘ７８Ｂ０００００のどこかのメモリ領域内に格納されることを示している。
【０００５】
このように、スキャンラインレンダリング処理を行う場合エッジ情報のロードを行う他に、エッジのリンクソート及びエッジとエッジ間の距離を算出する差分抽出処理を行うことになる。上述の処理を高速に行うためには、ＣＰＵのキャッシュ内にエッジ情報をロードした際に、次に処理するエッジの情報がキャッシュ内のエッジ情報領域内に格納されている状態が理想である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−１３７８２５
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、近年、アプリケーションの描画能力向上に伴い、エッジ数が多いデータが増えてきており、レンダリングにおけるエッジ処理に時間がかかることが問題になっている。
【０００８】
この問題に対し特許文献１の発明では、エッジ処理を１ライン毎に行っているためエッジ数が多いデータに対してキャッシュミスヒットと呼ばれる現象が起こる可能性がある。キャッシュミスヒットは、キャッシュ内にエッジ情報が存在しないためエッジ情報が格納されている領域からロードしなくてはいけない。このためレンダリング処理を高速に行うことはできない。
【課題を解決するための手段】
【０００９】
上記課題を解決するための本発明の画像形成装置は、描画データに基づいて１ライン毎にレンダリングする画像形成装置において、レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶し、前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートすることを特徴とする。
【発明の効果】
【００１０】
エッジ数が多い複雑なデータの場合においても、ＣＰＵのキャッシュミスヒットを削減でき高速にエッジ処理することを可能にする。
【図面の簡単な説明】
【００１１】
【図１】実施形態における各機器のコントロールユニットの構成例を示すブロック図
【図２】実施形態におけるシステム構成の一例を示す図
【図３】実施形態におけるコントローラソフトウェアの構成の一例を示すブロック図
【図４】実施形態におけるページ内のブロック分割の一例を示す図
【図５】実施形態におけるエッジ情報のメモリ配置の一例を示す図
【図６】実施形態におけるスキャンライン毎のエッジ処理の一例を示す図
【図７】実施形態におけるエッジ処理を含んだレンダリング処理の一例を示すフロー図
【図８】実施形態におけるブロックのカバー範囲変更の一例を示す図
【図９】実施形態におけるブロックの分割の一例を示す図
【図１０】実施形態におけるブロックの結合の一例を示す図
【図１１】実施形態におけるエッジのブロック間移動とリンクのソートの一例を示す図
【発明を実施するための形態】
【００１２】
以下、本発明を実施するための最良の形態について図面を用いて説明する。
【実施例１】
【００１３】
＜コントローラユニットの構成＞
図１は、本実施形態におけるＭＦＰ（Ｍｕｌｔｉ Ｆｕｎｃｔｉｏｎ Ｐｅｒｉｐｈｅｒａｌ）のコントロールユニットの構成を示すブロック図である。図１において、コントロールユニット２００は、画像入力デバイスであるスキャナ２０１や画像出力デバイスであるプリンタエンジン２０２と接続し、画像データの読み取りやプリント出力のための制御を行う。また、コントロールユニット２００は、ＬＡＮ Ｎ１や公衆回線２０４と接続することで、画像情報やデバイス情報をＬＡＮ Ｎ１経由で入出力するための制御を行う。プリンタエンジン２０２は２１７のデバイスＩ／Ｆと結合され、コントローラユニット２００で生成された描画データを紙に出力する処理を行う。
【００１４】
システムバス２１３には、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）２０５、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）２０６、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）２０７、ＨＤＤ（Ｈａｒｄ Ｄｉｓｃ Ｄｒｉｖｅ）２０８、操作部Ｉ／Ｆ２０９、ネットワークＩ／Ｆ２１１、モデム２１２、イメージパスＩ／Ｆ２１４が接続されている。ＣＰＵ２０５はＭＦＰ全体を制御するための中央処理装置である。ＲＡＭ２０６は、ＣＰＵ２０５が動作するためのシステムワークメモリであり、入力された画像データを一時記憶するための画像メモリでもある。さらに、ＲＯＭ２０７はブートＲＯＭであり、システムのブートプログラムが格納されている。ＨＤＤ２０８はハードディスクドライブであり、各種処理のためのシステムソフトウェア及び入力された画像データを等格納する。操作部Ｉ／Ｆ２０９は、画像データ等を表示可能な表示画面を有する操作部２１０に対するインタフェース部であり、操作部２１０に対して操作画面データを出力する。また、操作部Ｉ／Ｆ２０９は、操作部２１０から操作者が入力した情報をＣＰＵ２０５に伝える役割をする。ネットワークＩ／Ｆ２１１は、例えばＬＡＮカード等で実現され、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）Ｎ１に接続して外部装置との間で情報の入出力を行う。モデム２１２は公衆回線２０４に接続し、外部装置との間で情報の入出力を行う。以上のユニットがシステムバス２１３上に配置されている。イメージバスＩ／Ｆ２１４は、システムバス２１３と画像データを高速で転送する画像バス２１５とを接続するためのインタフェースであり、データ構造を変換するバスブリッジである。
【００１５】
画像バス２１５上には、ラスタイメージプロセッサ２１６、デバイスＩ／Ｆ２１７、スキャナ画像処理部２１８、プリンタ画像処理部２１９、画像編集用画像処理部２２０、カラーマネージメントモジュール２３０が接続されている。
【００１６】
ＲＩＰ（Ｒａｓｔｅｒ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｏｒ）２１６は、ＰＤＬデータや後述するベクトルデータをイメージデータとして展開する。デバイスＩ／Ｆ部２１７は、スキャナ２０１及びプリンタエンジン２０２とコントロール２００とを接続し、画像データの同期系／非同期系の変換を行う。
【００１７】
また、スキャナ画像処理部２１８は、スキャナ２０１から入力した画像データに対して、補正、加工、編集等の各種画像処理を行う。プリンタ画像処理部２１９は、プリント出力する画像データに対して、プリンタエンジンに応じた補正及び解像度変換等の処理を行う。画像編集用画像処理２２０は、画像データの回転や、画像データの圧縮伸長処理等の各種画像処理を行う。ＣＭＭ２３０は、画像データに対して、プロファイルやキャリブレーションデータに基づいた、色変換処理（色空間変換処理ともいう）を施す専用ハードウェアモジュールである。プロファイルとは、機器に依存した色空間で表現したカラー画像データを機器に依存しない色空間（例えばＬａｂなど）に変換するための関数のような情報である。キャリブレーションデータとは、カラー複合機３におけるスキャナ部２０１やプリンタエンジン２０２の色再現特性を修正するためのデータである。
【００１８】
次に、プリンタエンジン２０２の一例である１Ｄカラー系ＭＦＰ（Ｍｕｌｔｉ Ｆｕｎｃｔｉｏｎ Ｐｅｒｉｐｈｅｒａｌ：マルチファンクション周辺機器）の構成について説明する。
【００１９】
１Ｄカラー系ＭＦＰは、スキャナ部、レーザ露光部、感光ドラム、作像部、定着部、給紙／搬送部及び、これらを制御する不図示のプリンタ制御部から構成される。
【００２０】
スキャナ部は、原稿台に置かれた原稿に対して、照明を当てて原稿画像を光学的に読み取り、その像を電気信号に変換して画像データを作成する工程である。
【００２１】
レーザ露光部は、前記画像データに応じて変調されたレーザ光などの光線を等角速度で回転する回転多面鏡（ポリゴンミラー）に入射させ、反射走査光として感光ドラムに照射する。
【００２２】
作像部は、感光ドラムを回転駆動し、帯電器によって帯電させ、前記レーザ露光部によって感光ドラム上に形成された潜像をトナーによって現像化し、そのトナー像をシートに転写する。その際に転写されずに感光ドラム上に残った微小トナーを回収するといった一連の電子写真プロセスを実行して作像する。その際、シートが転写ベルトの所定位置に巻きつき、４回転する間に、マゼンタ（Ｍ）、シアン（Ｃ）、イエロー（Ｙ）、ブラック（Ｋ）のトナーを持つそれぞれの現像ユニット（現像ステーション）が入れ替わりで順次前述の電子写真プロセスを繰り返し実行する。４回転の後、４色のフルカラートナー像を転写されたシートは、転写ドラムを離れ、定着部へ搬送される。
【００２３】
定着部は、ローラやベルトの組み合わせによって構成され、ハロゲンヒータなどの熱源を内蔵し、前記作像部によってトナー像が転写されたシート上のトナーを、熱と圧力によって溶解、定着させる。
【００２４】
給紙／搬送部は、シートカセットやペーパーデッキに代表されるシート収納庫を一つ以上持っており、前記プリンタ制御部の指示に応じてシート収納庫に収納された複数のシートの中から一枚分離し、作像部・定着部へ搬送する。シートは作像部の転写ドラムに巻きつけられ、４回転した後に定着部へ搬送される。４回転する間に前述のＹＭＣＫ各色のトナー像がシートに転写される。また、シートの両面に画像形成する場合は、定着部を通過したシートを再度作像部へ搬送する搬送経路を通るように制御する。
【００２５】
プリンタ制御部は、ＭＦＰ全体を制御するＭＦＰ制御部と通信して、その指示に応じて制御を実行すると共に、前述のスキャナ、レーザ露光、作像、定着、給紙／搬送の各部の状態を管理しながら、全体が調和を保って円滑に動作できるよう指示を行う。
【００２６】
＜システム構成＞
次に、画像処理システムの構成について詳細に説明する。図２は、本実施形態に係る画像処理システムの全体構成を示すブロック図である。図２において、画像処理システムは、互いにＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）Ｎ１等を介して接続された、ＭＦＰ１、ＭＦＰ２、ＭＦＰ３で構成されている。
【００２７】
各ＭＦＰはそれぞれＨＤＤＨ１、Ｈ２、Ｈ３を具備している。ＭＦＰに搭載されているプリンタエンジン（以降、エンジン）の解像度はＭＦＰ毎に異なっており、ＭＦＰ１とＭＦＰ３は６００ｄｐｉ、ＭＦＰ２は１２００ｄｐｉである。また、ＭＦＰに搭載されているレンダラ（ラスタライザ）の種類もＭＦＰ毎に異なっており、ＭＦＰ１とＭＦＰ２のレンダラは同種（図中には「Ｒａ」と図示）、ＭＦＰ３だけ異なる種類（「Ｒｂ」と図示）である。一般にレンダラはＡＳＩＣなどのハードウェアで構成されるため、異なる種類のレンダラは異なる種類の描画命令群を処理することができない。この描画命令群を一般にディスプレイリストと呼ぶ。ディスプレイリストはハードウェアで処理可能なインストラクション（命令）であり、複雑な描画記述を持つベクタデータからソフトウェアで生成されるものであり、解像度に依存している。
【００２８】
ＭＦＰ１、ＭＦＰ２、ＭＦＰ３は、ネットワークプロトコルを使用して互いに通信することができる。なお、ＬＡＮ Ｎ１上に接続されるこれらのＭＦＰは上記のような物理的な配置に限定されなくても良い。また、ＬＡＮ Ｎ１上にはＭＦＰ以外の機器（例えばＰＣ、各種サーバ、プリンタなど）が接続されていても良い。
【００２９】
＜コントローラソフトウェア構成＞
次に、ＭＦＰの動作を制御するコントローラソフトウェアについて詳細に説明する。図３は、コントローラソフトウェアの構成を示すブロック図である。
プリンタインターフェイス４００は、外部との入出力のための手段である。プロトコル制御部４０１は、ネットワークプロトコルを解析・送信することによって外部との通信を行う手段である。
【００３０】
ＰＤＬデータ解析部４０２は、ＰＤＬデータを解析し、より処理しやすい形式のディスプレイリストに変換する手段である。ＰＤＬデータ解析部４０２において生成されたディスプレイリストはデータ描画部４０３に渡されて処理される。データ描画部４０３は上記ディスプレイリストをビットマップデータに展開するものであり、展開されたビットマップデータはページメモリ４０４に逐次描画されて行く。ＰＤＬデータ解析部４０２及びデータ描画部４０３は、ＲＯＭに格納されたプログラムを用いてＣＰＵにより実行されることで実現される。
【００３１】
ページメモリ４０４はレンダラが展開するビットマップデータを一次的に保持する揮発性のメモリである。
【００３２】
パネル入出力制御部は操作パネルからの入出力を制御するものである。
ドキュメント記憶部４０６はデータファイルを記憶する手段であり、ハードディスク等の二次記憶装置によって実現される。
スキャン制御部４０７はスキャナから入力した画像データに対して、補正、加工、編集などの各種処理を行う。
【００３３】
印刷制御部４０８は、ページメモリ４０４の内容をビデオ信号に変換処理し、プリンタエンジン部４０９へ画像転送を行う。プリンタエンジン部１４００は受け取ったビデオ信号を記録紙に永久可視画像形成するための印刷機構部である。
【００３４】
＜エッジ情報保持方法＞
本発明のエッジ情報の保持方法について、図５を用いて詳細に説明する。
メモリ領域は、入力されたディスプレイリストに確保されている場合や、ある固定領域に保持されている場合などが考えられる。メモリ領域のサイズは、ディスプレイリスト内に含まれるエッジ数を元に算出される場合や、ＭＦＰ全体で使用可能なメモリサイズのうち、レンダリング処理に使用可能なサイズがあらかじめ設定される。
【００３５】
エッジ数を元に算出される具体的なサイズとしては、１スキャンラインで最大ロードされるエッジ数に１つのエッジサイズをかけた値となる。１つのエッジサイズはエッジによって異なるが、最大でも１つのエッジ当たり約６０バイトとなるので、１スキャンラインに含まれる最大エッジ数が５００個だった場合、約３０ｋｂｙｔｅとなる。
【００３６】
本発明は、図４（ｂ）の二つの太線に示すように、ページ幅をＸ＝０〜２０００までとＸ＝２００１〜４０００までの二つのブロックに分割し、処理中のスキャンラインにおける各ブロック内に現れるエッジ情報をそれぞれの領域に保持し処理を行うことを特徴とする。
【００３７】
これをメモリ上ではどのようにデータが格納されるかを示した図が図５（ｂ）になり、点線で囲んだ透過な矩形領域がキャッシュ有効領域の例である。ページ幅がＸ＝０〜２０００に現れるエッジは、０ｘ７８００００００から０ｘ７８６０００００のアドレスが連続した領域に格納される。また、ページ幅がＸ＝２００１〜４０００に現れるエッジは、０ｘ７８６０００００から０ｘ７８Ｂ０００００のアドレスが連続した領域に格納されることを示している。
【００３８】
メモリ領域の分割方法としては、各ブロックに含まれるエッジ数が同じと仮定して、単純にブロックの個数分に分割する方法が考えられる。また、ブロックが２つの場合、一つ目のブロックに含まれるエッジ情報はメモリの先頭アドレスから、二つ目のブロックに含まれるエッジ情報は最終アドレスから使用する方法も考えられる。
【００３９】
隣り合うエッジが格納されているブロックが１つの場合、図５（ａ）に示すように０ｘ００８０００００番地分離れる可能性があったが、二つのブロックの場合は、図５（ｂ）に示すように最悪でも０ｘ００４０００００番地離れるのにとどまる。その為、キャッシュ効率のよいエッジ処理を行うことが可能になる。
【００４０】
＜レンダリングにおけるエッジ処理とは＞
ここでレンダリングにおけるエッジ処理について図６を用いて説明する。
【００４１】
まずエッジとは、ページ内に描画するオブジェクトとオブジェクト、またはオブジェクトと背景の境目を指す。
【００４２】
エッジ処理とは、メモリ上へのエッジ情報のロード、処理中のスキャンラインにおけるＸ座標の算出、処理中のエッジと隣のエッジ間の距離の算出、エッジが現れる順番を保持するリンクの更新、エッジ情報の削除の５つが大きな処理となる。
【００４３】
また、エッジ情報は、図６の右下の四角内にかかれるような項目が含まれる。
図６のエッジ処理を説明する図には、三角形と四角形のオブジェクトが書かれており、先ほど述べたように、領域はブロック１とブロック２の二つの領域に分割されている。
【００４４】
エッジ処理はページの上から下に向かってスキャンライン毎に処理を行っていくが、まずページの先頭から三角形の頂点が現れるまではエッジが存在しないので何も行わない。
【００４５】
三角形がページの右側に現れるスキャンライン（図６の「１、２追加」部分）を処理した場合、エッジ１の情報とエッジ２の情報がブロック２のメモリ上にロードされる。
【００４６】
ここでエッジ情報のメモリロードについて説明する。ディスプレイリストには、エッジの開始座標が記されているので、この開始座標、ブロック１が含まれる座標、ブロック２が含まれる座標を元にどのブロックにエッジがロードするか判断する。また、エッジ１が左、エッジ２が右にあるので、エッジは１→２の順にリンクされる。
【００４７】
処理を進めていくと、エッジ１がブロック２の領域からブロック１領域へ移動する（図６の「１ブロック移動」部分）のでエッジ１が属している領域情報をブロック２からブロック１へ変更する。
【００４８】
次に、四角形がブロック１とブロック２にまたがって現れるスキャンライン（図６の３、４追加」部分）を処理した場合、エッジ３の情報をブロック１のメモリ上に、エッジ４をブロック２のメモリ上に追加する。この場合、エッジ３がエッジ１の左側にあるので、ブロック１のエッジは３→１、ブロック２のエッジは４→２の順にリンクされる。
【００４９】
次に三角形がなくなるスキャンライン（図６の「１、２削除」部分）を処理した場合、エッジ１とエッジ２が消滅するので、エッジ１の情報とエッジ２の情報をメモリ上から削除する。
【００５０】
次に四角形がなくなるスキャンライン（図６の「３、４削除」部分）を処理した場合、エッジ３とエッジ４が消滅するので、エッジ３の情報とエッジ４の情報をメモリ上から削除する。
【００５１】
エッジ３、エッジ４が削除されたスキャンラインからページの一番下のスキャンラインまではエッジが現れないのでエッジ処理は行われない。
【００５２】
また本処理において、各ブロックを分割する境目をエッジとして扱い、ブロック１に含まれるエッジリストの最後とブロック２に含まれるエッジリストの先頭に新たなエッジを追加して処理を行っても構わない。
【００５３】
以上がレンダリングにおける基本的なエッジ処理の流れになる。
【００５４】
＜データ処理フロー＞
次に、図７を使って本特許におけるレンダリング処理を行うプログラムのフローについて説明する。このプログラムは、図１の２０５のＲＡＭにロードされ、２０５のＣＰＵ上で動作する。
【００５５】
Ｓ７０１は本処理の開始を示す。Ｓ７０２において、本処理におけるブロックの個数、カバー範囲を決める為の情報と、処理を行うディスプレイリストを入力する。
【００５６】
次にＳ７０３において、ブロック個数やカバー範囲の初期値を決定する。Ｓ７０４はスキャンラインのループ端になり、１スキャンライン処理する毎にＳ７２４からこのループ端に戻り、処理するスキャンラインがページの最終スキャンラインまでこのループが繰り返される。
【００５７】
Ｓ７０５は処理を行うブロックのループ端になり、１ブロックに含まれるエッジ処理が終了する毎にＳ７２２からこのループ単に戻り、処理するブロックがページに一番右側のブロックまでこのループが繰り返される。
【００５８】
Ｓ７０６において、処理を行うディスプレイリストの解釈を行う。Ｓ７０７において、Ｓ７０６の結果、処理中のブロックにおいて、エッジの追加、またはエッジの削除があるか判断する。Ｓ７０７の結果がＮＯの場合Ｓ７１５の処理を行う。Ｓ７０７の結果がＹＥＳの場合、Ｓ７０８において、エッジのロード処理、または削除処理を行い、ブロックに関するパラメータの更新を行う。
【００５９】
Ｓ７０９において、ブロックに関するパラメータのうちブロック間のエッジ数の偏りがＳ７０３で決定した閾値より大きいか判断する。Ｓ７０９の結果がＮＯだった場合、Ｓ７１１の処理を行う。Ｓ７０９の結果がＹＥＳだった場合、Ｓ７１０において、各ブロックに含まれるエッジ数の偏りが等しくなるようにブロックがカバーする範囲を変更し、ブロック間のエッジ数の偏り値を更新する。この処理の詳細は後述する＜ブロックのカバー範囲変更＞で説明する。
【００６０】
Ｓ７１１において、ブロック内のエッジ数がＳ７０３で決定した上限より大きいか判断する。Ｓ７１１の結果がＮＯだった場合、Ｓ７１３の処理を行う。Ｓ７１１の結果がＹＥＳだった場合、Ｓ７１２において、ブロックの分割処理を行い１ブロックに含まれるエッジ数の削減を行う。この処理の詳細は＜ブロックの分割＞で説明する。
【００６１】
次にＳ７１３において、ブロック内のエッジ数がＳ７０３で決定した下限より小さいか判断する。Ｓ７１３がＮＯだった場合Ｓ７１５の処理を行う。Ｓ７１３の結果がＹＥＳだった場合、Ｓ７１４において、ブロックの結合処理を行い１ブロックに含まれるエッジ数の最適化を行う。この処理の詳細は＜ブロックの結合＞で説明する。
【００６２】
次にＳ７１５において、処理中のブロックに含まれる全てのエッジに対して、次のスキャンラインにおけるＸ座標の算出を行い、エッジ同士が交差する場合、リンクの入れ替え（リンクソート）を行う。
ここで、エッジダーティーとフリーフォールという概念について説明する。処理を行うスキャンラインにおいて、エッジの追加ｏｒ削除がない、かつ、エッジの交差がないスキャンラインをフリーフォールのスキャンラインといい、それ以外のスキャンラインをエッジダーティーのスキャンラインという。つまりＳ７０７からＳ７１３の処理はエッジダーティー時のみ行われる処理である。
【００６３】
次にＳ７１６においてＳ７１５の結果、属するブロックが変わるエッジがあった場合、元のブロックのリンクから切り離し、移動先のブロックのリンクに追加する。この際、移動元、移動先それぞれのブロックに関してリンクの並び替え処理を行う。この処理の詳細は＜エッジのブロック間移動＞で説明する。
【００６４】
Ｓ７１８において、エッジ処理が終わった描画データの上下関係を判断し、描画するオブジェクトを選択するレベル処理を行う。次にＳ７１９において、Ｓ７１８で選択されたオブジェクトの塗り情報を生成するフィル生成処理を行い、Ｓ７２０でオブジェクト同士の重ね合わせであるコンポジット処理を行う。
【００６５】
Ｓ７２１において、処理を行うブロックを現在のブロックから一つ右のブロックへ移動する。Ｓ７２２はＳ７０５に対応するブロックに関するループ端になる。処理中のスキャンラインにおける全ブロックの処理が終了したら、Ｓ７２３において処理を行うスキャンラインを現在のスキャンラインから一つ下のスキャンラインに移動する。Ｓ７２４はＳ７０４に対応するスキャンラインに関するループ端になる。全スキャンラインに対する処理が終了したらＳ７２５でレンダリング処理を終了する。
【００６６】
＜ブロックのカバー範囲変更＞
ここで図８を用いて「データ処理フロー」のＳ７０９、Ｓ７１０で説明した、ブロックのカバー範囲変更についての詳細を述べる。
【００６７】
ｄ８０１は図４（ｂ）で述べたようにＸ＝０〜２０００、Ｘ＝２００１〜４０００までの二つのブロック（ブロック１、ブロック２）に分割して処理している。ｄ８０２に示すようにＹ＝０〜２０００まではブロック１、ブロック２共に同じ位の数のエッジが現れている。
【００６８】
どの位の割合でブロックにエッジが含まれるかを示す例として、ｄ８０２の表「偏り値」を説明する。「偏り値」が１だとブロック間でエッジ数がちょうど等分、１より少ないと他のブロックに比べてエッジ数が少ない、１より多いと他のブロックに比べてエッジ数が多いことを示す。「偏り値」算出方法の一例としては、
（ブロック内のエッジ数×ブロック数）／スキャンライン内の総ブロック数
で計算することが出来る。この場合偏り値は、０から２の間のいずれかの値がとられることになる。
【００６９】
次にｄ８０３に示すように、点線部の２００１スキャンライン目のブロック２には、家の屋根のエッジが大量に現れる。
【００７０】
ｄ８０４に示すようにエッジ数はブロック１が１０個に対し、ブロック２が４９０個となり、それぞれの偏り値はブロック１が０．０４に対し、ブロック２が１．９６となる。よって、「データ処理フロー」のＳ７０３で設定した閾値例（１．３）を越えたのでブロックのカバー範囲を変更する処理を行う。
【００７１】
その結果、ｄ８０５に示すように、ブロックのカバーする範囲をエッジ数が少ないブロック１を広げ、エッジ数が多いブロック２を狭める範囲の変動処理を行う。詳細はｄ８０６に示すように、Ｘ＝０〜３３００までがブロック１、Ｘ＝３３０１〜４０００までがブロック２とすると、各ブロックに含まれるエッジ数がちょうど半分ずつの２５０個ずつとなり、また、偏り値もそれぞれ１となりエッジ数が均等になる。
【００７２】
＜ブロックの分割＞
次に図９を用いて「データ処理フロー」のＳ７１２で説明した、ブロックの分割についての詳細を述べる。
【００７３】
ｄ９０１は＜ブロックのカバー範囲変更＞で述べたようにＹ＝０〜２０００まではＸ＝０〜２０００、Ｘ＝２００１〜４０００の二つのブロックで処理をしていた。また、Ｙ＝２００１〜５０００までは、Ｘ＝０〜３３００、Ｘ＝３３０１〜４０００までの二つのブロックに分割して処理していた。Ｙ＝０〜５０００までの各ブロック内に現れるエッジ数はｄ９０２に示すように最大でも３００個だった。
【００７４】
次にｄ９０３に示されるように、点線部の５００１スキャンライン目のブロック２には、木の葉っぱのエッジが大量現れる。その個数はｄ９０４に示されるように、６００個で、「データ処理フロー」のＳ７０３で設定した１ブロックに含まれる最大個数例（５００個）を越えるのでブロック２はブロック２とブロック３に分割される。
【００７５】
その結果、ｄ９０４に示すように、各ブロックのエッジ数は、ブロック１は２８０個、ブロック２は２５０個、ブロック３は３５０個となり、いずれも１ブロックの上限である５００個を下回った。もし１度分割しても上限を下回らない場合、再度ブロックの分割を行う。
【００７６】
＜ブロックの結合＞
次に図１０を用いて「データ処理フロー」のＳ７１４で説明した、ブロックの結合についての詳細を述べる。
【００７７】
ｄ１００１の点線部分は＜ブロックの分割＞で述べたようにＹ＝５０００〜６５００まではＸ＝０〜２０００、Ｘ＝３３０１〜３６５０、Ｘ＝３６５１〜４０００までの三つのブロックで処理をしていた。ｄ１００２に示すようにエッジ数、偏り値はＳ７０３で決定した閾値より小さかった。
【００７８】
次にｄ１００３に示されるように、点線部の６５０１スキャンライン目のブロック１、ブロック２、ブロック３は家や木の葉っぱのエッジが削除される。その個数はｄ１００４に示されるように、ブロック１は１５個、ブロック２は１０個、ブロック３は１０個であった。この数は「データ処理フロー」のＳ７０３で設定した１ブロックに含まれる最小個数（１２個）を下回るのでブロック２とブロック３はブロック２として結合される。
【００７９】
その結果、ｄ１００６に示すように、各ブロックのエッジ数は、ブロック１は１５個、ブロック２は２０個となり、いずれも１ブロックの下限である１２個を上回った。もし１度結合しても下限を上回らない場合、再度ブロックの結合を行う。
【００８０】
＜エッジのブロック間移動＞
次に図１１を用いて「データ処理フロー」のＳ７１６で説明した、エッジのブロック間移動に伴うソートについての詳細を述べる。
【００８１】
ｄ１１０１は描画されるページの例を示している。エッジ１、２を持つグレーの矩形がブロック１に、エッジ３、４を持つグラデーションの円と、エッジ５、６を持つ網点の三角形がブロック２に含まれている。
【００８２】
ｄ１１０２には着目スキャンラインにおけるエッジのリンクを示している。
【００８３】
まずＹ＝１０００ライン目におけるエッジリンクは、ブロック１はエッジ１が左側に、エッジ２が右側にあるので、１→２の順にリンクされる。同様にブロック２は左からエッジ３、５、６、４の順に現れるので、３→５→６→４の順にリンクされる。次のスキャンラインＹ＝１００１ライン目のＸ座標を計算したところ、エッジ５の座標がＸ＝１８００になったので、エッジ５はブロック２から１へ移動することがわかる。そこで、エッジ５はブロック２のリンクから切り離しブロック１のリンクにつなげ、Ｘ座標順にリンクをソートすると、１→５→２の順のリンクになる。また、ブロック２はエッジ５が抜けたので、エッジ３とエッジ６をリンクした結果、３→６→４の順のリンクになる。
【００８４】
エッジがブロック間を移動した場合、メモリ上にロードされているエッジ情報がブロック１からブロック２の領域にコピーされる場合と、エッジ情報はコピーされずにリンクのみが更新される場合の二通りが考えられる。
【００８５】
前者はコピーを行う処理時間がかかるが、その後のエッジ処理においてはキャッシュ上で処理できるという点が上げられる。一方、後者はコピーを行わないのでその時間はかからないが、その後のエッジ処理においてはキャッシュ上で処理されない点が上げられる。どちらの方法が効率的かはエッジデータの長さや種類に依存する。
【００８６】
このように、ページ内でエッジ数の偏りがあった場合も、領域を可変することにより安定した速度で処理を行うことが可能になる。
【００８７】
（他の実施形態）
以上、様々な実施形態を詳述したが、本発明は、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。例えば、スキャナ、プリンタ、ＰＣ、複写機、複合機及びファクシミリ装置の如くである。
【００８８】
本発明は、前述した実施形態の各機能を実現するソフトウェアプログラムを、システム若しくは装置に対して直接または遠隔から供給し、そのシステム等に含まれるコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される。
【００８９】
従って、本発明の機能・処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、上記機能・処理を実現するためのコンピュータプログラム自体も本発明の一つである。
【００９０】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等、プログラムの形態を問わない。
【００９１】
プログラムを供給するための記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷなどがある。また、記録媒体としては、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ、ＤＶＤ−Ｒ）などもある。
【００９２】
また、プログラムは、クライアントコンピュータのブラウザを用いてインターネット／イントラネットのウェブサイトからダウンロードしてもよい。すなわち、該ウェブサイトから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードしてもよいのである。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるウェブサイトからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明の構成要件となる場合がある。
【００９３】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布してもよい。この場合、所定条件をクリアしたユーザにのみ、インターネット／イントラネットを介してウェブサイトから暗号化を解く鍵情報をダウンロードさせ、その鍵情報で暗号化されたプログラムを復号して実行し、プログラムをコンピュータにインストールしてもよい。
【００９４】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現されてもよい。なお、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行ってもよい。もちろん、この場合も、前述した実施形態の機能が実現され得る。
【００９５】
また、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれてもよい。そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ってもよい。このようにして、前述した実施形態の機能が実現されることもある。
【００９６】
さらに、実施例１の領域分割をブロック毎としたが、１ライン毎に領域を分割しても良い。この場合、エッジ数がより多い描画データに対して有効である。
【符号の説明】
【００９７】
２００ コントロールユニット
２０１ スキャナ
２０２ プリンタエンジン
２１０ 操作部
３０１ ジョブコントロール処理
４００ プロトコル制御部
４０１ ベクタデータ生成部
４０２ ＰＤＬデータ解析部
４０３ データ描画部
４０４ ページメモリ
４０５ パネル入出力制御部
４０６ ドキュメント記憶部
４０７ スキャン制御部
４０８ 出力制御部
４０９ プリンタエンジン部
【特許請求の範囲】
【請求項１】
描画データに基づいて１ライン毎にレンダリングする画像形成装置において、
レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶する記憶手段と、
前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートするソート手段と、
を有する画像形成装置。
【請求項２】
前記領域の範囲は変動することを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記分割された領域は、１ライン毎またはブロック毎に分割された領域であることを特徴とする請求項１または２に記載の画像形成装置。
【請求項４】
前記分割された領域は、１ラインにおける夫々の領域のエッジ数が均等になるように分割された領域であることを特徴とする請求項１乃至３に記載の画像形成装置。
【請求項５】
前記１ラインにおける夫々の領域のエッジ情報はアドレスが連続したメモリ領域に記憶されていることを特徴とする請求項１乃至４に記載の画像形成装置。
【請求項６】
前記レンダリング処理を行う１ラインにおける分割された領域内のエッジ数が上限より大きい場合は領域を増加し、前記記憶手段は増加された領域に現れるエッジ情報を記憶し、前記ソート手段は増やされた領域に現れるエッジ情報をソートすることを特徴とする請求項１乃至５に記載の画像形成装置。
【請求項７】
前記レンダリング処理を行う１ラインにおける分割された領域内のエッジ数が下限より小さい場合は領域を減らし、レンダリングを行う１ラインにおける領域に現れるエッジ情報を記憶し、前記ソート手段は領域に現れるエッジ情報をソートすることを特徴とする請求項１乃至６に記載の画像形成装置。
【請求項８】
描画データに基づいて１ライン毎にレンダリングする画像形成方法において、
レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶する記憶工程と、
前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートするソート工程と、
を含む画像形成方法。
【請求項９】
描画データに基づいて１ライン毎にレンダリングする画像形成方法において、
レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶する記憶工程と、
前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートするソート工程と、
を含む画像形成方法を実行するためのプログラム。
【請求項１】
描画データに基づいて１ライン毎にレンダリングする画像形成装置において、
レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶する記憶手段と、
前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートするソート手段と、
を有する画像形成装置。
【請求項２】
前記領域の範囲は変動することを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記分割された領域は、１ライン毎またはブロック毎に分割された領域であることを特徴とする請求項１または２に記載の画像形成装置。
【請求項４】
前記分割された領域は、１ラインにおける夫々の領域のエッジ数が均等になるように分割された領域であることを特徴とする請求項１乃至３に記載の画像形成装置。
【請求項５】
前記１ラインにおける夫々の領域のエッジ情報はアドレスが連続したメモリ領域に記憶されていることを特徴とする請求項１乃至４に記載の画像形成装置。
【請求項６】
前記レンダリング処理を行う１ラインにおける分割された領域内のエッジ数が上限より大きい場合は領域を増加し、前記記憶手段は増加された領域に現れるエッジ情報を記憶し、前記ソート手段は増やされた領域に現れるエッジ情報をソートすることを特徴とする請求項１乃至５に記載の画像形成装置。
【請求項７】
前記レンダリング処理を行う１ラインにおける分割された領域内のエッジ数が下限より小さい場合は領域を減らし、レンダリングを行う１ラインにおける領域に現れるエッジ情報を記憶し、前記ソート手段は領域に現れるエッジ情報をソートすることを特徴とする請求項１乃至６に記載の画像形成装置。
【請求項８】
描画データに基づいて１ライン毎にレンダリングする画像形成方法において、
レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶する記憶工程と、
前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートするソート工程と、
を含む画像形成方法。
【請求項９】
描画データに基づいて１ライン毎にレンダリングする画像形成方法において、
レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報を記憶する記憶工程と、
前記レンダリングを行う１ラインにおける分割された領域に現れるエッジ情報をソートするソート工程と、
を含む画像形成方法を実行するためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−７９４（Ｐ２０１１−７９４Ａ）
【公開日】平成２３年１月６日（２０１１．１．６）
【国際特許分類】
【出願番号】特願２００９−１４５４５０（Ｐ２００９−１４５４５０）
【出願日】平成２１年６月１８日（２００９．６．１８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２３年１月６日（２０１１．１．６）
【国際特許分類】
【出願日】平成２１年６月１８日（２００９．６．１８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]