(57)【要約】【課題】  ベクターエッジからスキャンラインエッジに変換する箇所を最適に判断し、データサイズの増大を抑えること。【解決手段】  複数の画像オブジェクト（例えば文字やイメージやグラフィック）で構成されている電子ドキュメントおよびＰＤＬデータを受信し、画像を形成する画像形成装置において、ベクターエッジで構成されるディスプレイリストを生成する手段を備え、描画処理の速度の妨げになるラインを抽出する処理を備え、抽出されたラインのみスキャンラインエッジに変換する。【選択図】  図１
2009101519.tif 000002
【特許請求の範囲】
【請求項１】
複数の画像オブジェクト（文字やイメージやグラフィック）で構成されている電子ドキュメントおよびＰＤＬデータを受信し、画像を形成する画像形成装置において、ベクターエッジで構成されるディスプレイリストを生成する手段を備え、描画処理の速度の妨げになるラインを抽出する処理を備え、抽出されたラインのみスキャンラインエッジに変換することを特徴とする画像形成装置。
【請求項２】
請求項１に記載の画像形成装置を搭載する画像形成システム。
【請求項３】
請求項１に記載の画像形成装置において、抽出されるラインは各バンドの先頭ラインまたはエッジの追加が多いラインであることを特徴とする画像形成装置。
【請求項４】
請求項１に記載の画像形成装置において、ベクターエッジで構成されるディスプレイリストを生成する処理と描画処理の速度の妨げになるライン抽出とベクターエッジからスキャンラインエッジへの変換処理と描画処理は複数プロセッサまたはハードウェアによって並列に処理することを特徴とする画像形成装置。
【請求項５】
ホストコンピュータ上のプリンタドライバがディスプレイリストを生成し、画像形成装置に送信する画像形成システムにおいて、描画の処理の妨げになるラインを抽出する処理およびベクターエッジからスキャンラインエッジへの変換はホストコンピュータ上で行われることを特徴とする画像形成システム。
【請求項６】
複数のプロセッサまたはハードウェアは、画像形成装置上に構成されるものだけではなく、ネットワークで接続されたホストコンピュータの装置上のプロセッサまたはハードウェアでもよいことを特徴とする画像形成システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パーソナルコンピュータや画像形成装置などの情報処理システムにおける画像処理において、エッジリストデータの効率的な保持手法とマルチプロセッサ環境における高速化手法に関するものである。
【背景技術】
【０００２】
複数の画像オブジェクト（例えば文字やイメージやグラフィック）で構成されている電子ドキュメントおよびＰＤＬデータから画像形成する処理がある。
【０００３】
画像形成装置は画像オブジェクトのアウトラインを抽出することにより、画像を形成する範囲を決定し、描画処理を行う。
【０００４】
抽出されたアウトラインはエッジと呼称される。
【０００５】
画像オブジェクトのアウトラインを表現する方法として、図２に示すようにベクターエッジ２０２とスキャンエッジ２０３の２つの方法がある。
【０００６】
ベクターエッジ２０２とスキャンエッジ２０３はどちらも２０１のエッジを表現している。
【０００７】
ベクターエッジ２０２は一般的に開始座標、線分の傾き、高さで表現するため、データサイズが小さいが、描画処理を行う際にラインごとに座標位置算出を行わなくてはならないため処理負荷がかかる。
【０００８】
逆にスキャンエッジ２０３は一般的にラインごとの座標位置を記述しておくため、データサイズは大きいが、描画処理を行う際にラインごとに座標点算出を行う必要がなく処理負荷は少ない。
【０００９】
描画処理部の高速化のために、ベクターエッジをバンド単位に分割し、描画処理が遅くなると予測されるバンドのベクターエッジをスキャンラインエッジに変換する方法が特開2002-244643号公報に開示されている。
【００１０】
しかしながら上記従来例では全てのバンドが遅いと予測されると、全てのバンドにあるベクターエッジがスキャンラインエッジに変換されてしまい、データサイズが増大するという問題点がある。
【特許文献１】特開2002-244643号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来例では全てのバンドが遅いと予測されると、全てのバンドにあるベクターエッジがスキャンラインエッジに変換されてしまい、データサイズが増大するという問題点がある。
【００１２】
本発明では上記問題点に鑑み、ベクターエッジからスキャンラインエッジに変換する箇所を最適に判断し、データサイズの増大を抑えることを課題とする。
【課題を解決するための手段】
【００１３】
複数の画像オブジェクト（例えば文字やイメージやグラフィック）で構成されている電子ドキュメントおよびＰＤＬデータを受信し、画像を形成する画像形成装置において、ベクターエッジで構成されるディスプレイリストを生成する手段を備え、描画処理の速度の妨げになるラインを抽出する処理を備え、抽出されたラインのみスキャンラインエッジに変換することを特徴とする。
【００１４】
抽出されるラインは各バンドの先頭ラインまたはエッジの追加が多いラインであることを特徴とする。
【００１５】
ベクターエッジで構成されるディスプレイリストを生成する処理と描画処理の速度の妨げになるライン抽出とベクターエッジからスキャンラインエッジへの変換処理と描画処理は複数プロセッサまたはハードウェアによって並列に処理することを特徴とする。
【００１６】
ホストコンピュータ上のプリンタドライバがディスプレイリストを生成し、画像形成装置に送信するシステムにおいては、描画の処理の妨げになるラインを抽出する処理およびベクターエッジからスキャンラインエッジへの変換はホストコンピュータ上で行われることを特徴とする。
【００１７】
複数のプロセッサまたはハードウェアは、画像形成装置上に構成されるものだけではなく、ネットワークで接続されたホストコンピュータ等の装置上のプロセッサまたはハードウェアでもよいことを特徴とする。
【発明の効果】
【００１８】
データサイズ量の増大を抑制しながら、描画処理の速度を構造することが出来る。
【発明を実施するための最良の形態】
【００１９】
次に、本発明の詳細を実施例の記述に従って説明する。
【実施例１】
【００２０】
図１は、本発明の画像形成装置の第１の実施の形態を示すブロック図である。
【００２１】
ＰＤＬデータのデコード処理部１０１は複数の画像オブジェクト（例えば文字やイメージやグラフィック）で構成されている電子ドキュメントおよびＰＤＬデータを解釈し、ベクターデータ生成処理部に渡す。
【００２２】
ベクターデータ生成処理部１０２は画像オブジェクトのアウトラインを抽出する。
【００２３】
抽出されたアウトラインはディスプレイリスト化処理部１０３へ渡され、第１のディスプレイリスト１１０にベクターエッジリストとして形成される。
【００２４】
スキャンラインエッジ化判断処理部１０４は第１のディスプレイリスト１１０を解析し、スキャンライン化すべきラインを判断する。
【００２５】
スキャンライン化判断処理部１０４によってスキャンライン化すべきと判断されたラインはスキャンラインエッジ化処理部１０５によってスキャンラインエッジ化され、第２のディスプレイリスト１１１に格納される。
【００２６】
第１の描画処理部１０６および第２の描画処理部１０７は第１のディスプレイリスト１１０および第２のディスプレイリスト１１１を解釈しバンドごとの描画処理を並列に実行する。
【００２７】
描画結果はビデオ出力回路１０８に渡され、エンジン１０９で実際の印刷媒体上に画像形成される。
【００２８】
図３を用いてスキャンラインエッジ化されるべきラインの第１の実施例を説明する。
【００２９】
また、本実施例では画像形成される左上を座標原点とし、縦方向にＹ軸、横方向にＸ軸として説明する。
【００３０】
スキャンライン単位の描画処理を行う場合、新たなベクターエッジが追加さえるラインでは処理が遅くなる。
【００３１】
３０１および３０３のそれぞれの両端のエッジが既存のベクターエッジであり、３０２および３０４のそれぞれの両端のエッジが新たに追加されるベクターエッジである。
【００３２】
描画処理部３１１では現在描画するラインのＹ軸位置と交差する全てのベクターエッジのＸ座標のスキャンラインエッジリスト３１５および３１６を内部的に保持する。
【００３３】
新たなベクターエッジ３０２および３０４が追加されると、内部エッジリストへの追加処理部３１５が１ページ分のベクターエッジ３１０から必要なベクターエッジを抽出する。
【００３４】
抽出したベクターエッジからＸ座標を算出して第１の内部エッジリスト３１５に追加する。
【００３５】
内部エッジリスト３１５はＸ軸でソートされていない状態なので、内部エッジリストのソート処理部３１３は、内部エッジリストのＸ軸ソートを行い第２の内部エッジリスト３１６へ格納する。
【００３６】
第２のエッジリスト３１３はスキャンライン描画処理部３１４により、画像形成されスキャンライン描画結果３１７に格納される。
【００３７】
このように新たなベクターエッジが追加された場合、描画処理に時間が多くかかる。
【００３８】
図４を用いて新たなベクターエッジの追加が発生せずＸ座標の更新のみであった場合について説明する。
【００３９】
４０１、４０２、４０３、４０４のそれぞれの両端のエッジが全て既存のベクターエッジであった場合、そのラインは内部エッジリストのＸ座標の更新のみが必要となる。
【００４０】
Ｘ座標の更新のみであった場合、内部エッジリストのＸ座標更新処理部４１２は１ページ分のベクターエッジリスト４１１を参照しながら、第1の内部エッジリスト４１４のＸ座標を更新し、第２の内部エッジリスト４１３に格納する。
【００４１】
第２のエッジリスト４１５はスキャンライン描画処理部４１３により、画像形成されスキャンライン描画結果４１６に格納される。
【００４２】
既存のベクターエッジのみであった場合、図３で説明した新たなベクターエッジが追加された場合に比べて処理は少なくて済む。
【００４３】
図５を用いてベクターエッジが不要となった場合について説明する。
【００４４】
５０１および５０２のそれぞれの両端のベクターエッジは不要となる場合、５１０の処理部は１ページ分のベクターエッジリスト５１１を参照しながら、内部エッジ５１４のＸ座標更新処理と不要となったエッジの削除を行う。
【００４５】
Ｘ座標の更新と削除結果は第２の内部エッジリスト５１５に格納される。
【００４６】
第２のエッジリスト５１５はスキャンライン描画処理部５１３により、画像形成されスキャンライン描画結果５１６に格納される。
【００４７】
エッジの削除はＸ座標の更新を行おうとしたときに、ベクターエッジに次のラインの情報がなかったため無効とすると考えれば、Ｘ座標の更新と同等の処理として考えられる。
【００４８】
よって、ベクターエッジが不要となった場合は、図４を用いて説明したベクターエッジの更新のみが存在した場合と同等な描画処理速度となる。
【００４９】
上述してきたように、スキャンライン化すべきラインとはベクターエッジの追加が発生したラインである。
【００５０】
図６および図７でベクターエッジの追加が発生する条件について説明する。
【００５１】
図６はページをバンドに分割した様子を示している。
【００５２】
図１の第１の描画処理部１０６と第２の描画処理部１０７で並列処理する方法としてバンド単位に並列処理する方法がある。
【００５３】
バンドとしてあつかう場合、２バンド目の先頭ライン６０３においては全てのベクターエッジが新たなベクターエッジ追加となる。
【００５４】
６０４、６０５、６０６、６０７のそれぞれの両端のエッジのＸ座標はスキャンラインエッジ６０２にされ第２のディスプレイリスト６００として格納される。
【００５５】
スキャンラインエッジリスト７０２はベクターエッジ７０１と関連付けられており、次のライン以降のそれぞれのＸ座標の更新はベクターエッジ７０１を参照することにより行われる。
【００５６】
図７はベクターエッジのＹ軸上で最上位位置が１ラインに集中しているケースを示す。
【００５７】
ベクターエッジの追加が行われた全てのラインに対して、スキャンラインエッジを追加するのは無駄である。
【００５８】
ベクターエッジの追加が集中しているラインに対してのみスキャンラインエッジの作成を行えばよい。
【００５９】
７０３および７０４はベクターエッジの追加が集中しているラインであるので、スキャンラインエッジリストを作成し、７０１および７０２へ第２のディスプレイリストとして格納する。
【００６０】
図１の第１の描画処理部１０６と第２の描画処理部１０７でバンド単位に並列処理する方法をとる場合、バンドごとの描画処理時間が大きくことなっていると、並列処理のスケジューリングが難しくなる。
【００６１】
片一方の処理部が速く終わりすぎてしまうと並列化の効果が得られないため、偏らないように並列化する必要があるためである。
【００６２】
各バンドの描画処理時間が大きくことなっていると、偏りを補正するのが難しくなる。
【００６３】
エッジの追加が多いバンドほど、スキャンラインエッジ化するラインを多く設定することにより各バンドの描画時間が平均化し、並列化処理のスケジューリングを容易にすることが出来る。
【００６４】
図８を用いてマルチプロセッサ構成への適用方法について説明する。
【００６５】
画像形成装置８０１に４つのプロセッサが搭載されている場合、８０２第１のディスプレイリスト生成までを１プロセッサで処理する。
【００６６】
８０３の第２のディスプレイリスト制裁までを１プロセッサで処理し、８０４および８０５の描画処理をそれぞれ１プロセッサで処理する。
【００６７】
それぞれを並列で処理することにより高速な画像形成装置を構築することが出来る。
【００６８】
次にマルチプロセッサがネットワーク上に接続された別の装置上に存在する場合について説明する。
【００６９】
８１１はホストコンピュータで８１２および８１３のディスプレイリスト生成処理はホストコンピュータ上のマルチプロセッサで処理する。
【００７０】
８０４および８０５の描画処理を画像形成装置上のマルチプロセッサで処理する。
【００７１】
一般的に低コストな画像形成装置ではホストコンピュータ上の処理能力向上が高いため、こちらの構成の方が好適である。
【００７２】
また、用紙上に直ぐに画像形成せず、描画処理結果を蓄積するような場合においては、描画処理を別々の画像形成装置で行うような構成があっても良い。
【図面の簡単な説明】
【００７３】
【図１】処理全体の流れを示すフロー図。
【図２】ベクターエッジとスキャンエッジの具体例。
【図３】エッジの追加処理を示す図。
【図４】エッジの更新処理を示す図。
【図５】エッジの削除処理を示す図。
【図６】ページ内でエッジ追加が多い場所の具体例。
【図７】ページ内のバンド境界を示す図。
【図８】マルチプロセッサ構成を説明した図。
【図１】
2009101519.tif 000003
【図２】
2009101519.tif 000004
【図３】
2009101519.tif 000005
【図４】
2009101519.tif 000006
【図５】
2009101519.tif 000007
【図６】
2009101519.tif 000008
【図７】
2009101519.tif 000009
【図８】
2009101519.tif 000010