画像形成装置
【課題】 画像形成装置において、複数図形の組み合わせによって包含される図形のデータを効率的に削除することによって、出力の高速化を可能とする。
【解決手段】 所定のデータを解析し、図形データとその領域データとを抽出するＰＤＬ解析部１２と、抽出された一以上の図形データ及びその領域データをディスプレイリストとして順次作成するディスプレイリスト作成部１４と、先に抽出された図形の領域が、後に抽出された複数の図形の領域に包含される場合に、前記先に抽出された図形のディスプレイリストを削除するディスプレイリスト削除部１５と、前記ディスプレイリストを構成する図形データに基づき画像形成データを出力するページラスタライズ部１６と、からなる構成としてある。
【解決手段】 所定のデータを解析し、図形データとその領域データとを抽出するＰＤＬ解析部１２と、抽出された一以上の図形データ及びその領域データをディスプレイリストとして順次作成するディスプレイリスト作成部１４と、先に抽出された図形の領域が、後に抽出された複数の図形の領域に包含される場合に、前記先に抽出された図形のディスプレイリストを削除するディスプレイリスト削除部１５と、前記ディスプレイリストを構成する図形データに基づき画像形成データを出力するページラスタライズ部１６と、からなる構成としてある。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像形成装置に関し、より詳しくは、描画処理時間を効果的に短縮化できる画像形成装置に関する。
【背景技術】
【０００２】
従来から、画像処理技術に関する様々な研究が継続的にすすめられており、その一つとしてプリンタやスキャナ等、画像形成装置の高速処理技術の研究が行われてきた。
特に、近年では、出力のカラー化や多階調化等により、取り扱うデータ処理量が大幅に増加しており、画像処理の更なる高速化が求められている。
【０００３】
このため、中間リストの記憶領域を減少させてビットマップ化速度の向上を目的とした画像処理装置が提案されている（例えば、特許文献１）。
この画像処理装置によれば、図１４に示すように、先に描画される第一の図形７０１の描画領域が、後に描画される第二の図形７０２の描画領域に包含される場合には、中間リストから第一の図形７０１のデータを削除し、高速化を図るようにしている。
また、第一の図形の描画領域と第二の図形の描画領域とが重なっている場合には、第一の図形からその重なり部分を削除することによっても高速化を図るようにしている。
【０００４】
【特許文献１】特開２００１−８８３６７号公報（第１頁、第１図）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、以上のような従来提案されているに画像処理装置おいては、第一の図形が後の一の図形によって包含される場合には直接的に第一の図形データを削除することができるが、第一の図形が後の複数の図形によって包含される場合には第一の図形データが直接的には削除されず、複数の重なり部分をその数分削除することによって始めて第一の図形データの全部を削除することができる。
したがって、第一の図形が多数の図形によって包含される場合には、データ削除に要する処理数が大幅に増加するため、かえって処理の渋滞を招くこととなり、問題となっていた。
【０００６】
本発明は、以上のような従来の技術が有する問題を解決するために提案されたものであり、複数図形の組み合わせによって包含される図形のデータを効率的に削除することによって、出力の高速化を図ることが可能な画像形成装置の提供を目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明の画像形成装置は、請求項１に記載するように、所定のデータを解析し、図形データとその領域データとを抽出するデータ抽出手段と、抽出された一以上の前記図形データ及びその領域データを順次格納するディスプレイリストと、先に格納された図形の領域が、後に格納された一の図形の領域に包含される場合に、前記先に格納された図形のデータを前記ディスプレイリストから削除する包含図形削除手段と、前記ディスプレイリストに格納されている図形データに基づき画像形成データを出力する出力手段と、前記ディスプレイリストにおいて、先に格納された第一の図形の領域と後に格納された第二の図形の領域との重複領域を検出する重複領域検出手段と、前記第一の図形の領域を、前記重複領域を削除した領域に変更する領域変更手段と、前記包含図形削除手段は、前記領域変更手段によって変更された前記第一の図形の領域が、後に格納された前記第二の図形以外の図形の領域に包含される場合に、前記第一の図形データを前記ディスプレイリストから削除する構成としてある。
【０００８】
このような構成からなる本発明の画像形成装置によれば、描画対象となる図形相互の重複領域を求め、元の図形の領域からその重複領域を削除することとしてある。
そして、重複領域が削除された図形の領域を基準とし、この基準領域が他の図形に包含されている場合には係る図形を削除し、不要な描画データの削除を行うようにしている。
したがって、結果的には、従来のように一の図形が他の一の図形のみによって包含される場合に限らず、複数図形の組み合わせによって包含される場合でも係る図形データを削除できるようになる。
また、図形データの削除に至るプロセスが、領域データのみを基準として制御する簡易なものとなっているため、処理にかかる負担を大幅に抑えることが可能となる。このため、不要な図形データを効果的に削除でき、画像処理の効率化及び処理速度の向上を図ることができる。
【０００９】
また、本発明の画像形成装置は、請求項２に記載するように、前記領域データにもとづき、図形の最大矩形領域を算出する最大矩形領域算出手段と、前記領域データにもとづき、図形のバウンディングボックス領域を算出するバウンディングボックス領域算出手段とを備え、前記重複領域検出手段は、前記ディスプレイリストにおいて、先に格納された第一の図形のバウンディングボックス領域と後に格納された第二の図形の最大矩形領域との重複領域を検出し、前記領域変更手段は、前記第一の図形のバウンディングボックス領域を、前記重複領域を削除した領域に変更し、前記包含図形削除手段は、前記領域変更手段によって変更された第一の図形のバウンディングボックス領域が、後に格納された第二の図形以外の図形の最大矩形領域に包含される場合に、前記第一の図形のデータを前記ディスプレイリストから削除する構成としてある。
【００１０】
このような構成からなる本発明の画像形成装置によれば、前述の最大矩形領域とバウンディングボックス領域を求め、これらを図形の領域とみなして各処理を行うようにしている。
具体的には、描画対象となる第一図形のバウンディングボックス領域と第二図形の最大矩形領域との重複領域を求め、第一図形のバウンディングボックス領域からその重複領域を削除することとしてある。
そして、重複領域が削除された後のバウンディングボックス領域を基準とし、この基準領域が他の図形の最大矩形領域に包含されている場合には係る図形を削除し、不要な描画データの削除を行うようにしている。
したがって、描画対象が複雑な図形であっても、近似する単純な矩形領域に置き換えることによって、演算処理にかかる負担を大幅に抑えることができるので、図形相互の包含の有無を容易に判定することができる。
これにより、画像処理をさらに効率化し、高速化させることができる。
【００１１】
また、本発明の画像形成装置は、請求項３に記載するように、前記領域データは、少なくとも所定の座標データによって構成されるようにしてある。
【００１２】
このような構成からなる本発明の画像形成装置によれば、描画対象となる図形の領域を座標データにもとづき抽出することができるため、迅速に図形位置を認識することが可能となる。
これにより、より効率的で高速な処理が行えるようになる。
特に、バウンディングボックス領域及び最大矩形領域の算出、図形相互の包含・重複の検出、領域データの変更処理など、様々な演算処理にも迅速かつ容易に対応することが可能である。
【００１３】
また、本発明の画像形成装置は、請求項４に記載するように、出力単位となるページフレームを一定基準にもとづき分割し、複数のバンド領域を生成するバンド領域生成手段を、備え、前記データ抽出手段は、所定のデータを解析し、図形データとその領域データとをバンド領域毎に抽出し、前記ディスプレイリストは、抽出された一以上の前記図形データ及びその領域データをバンド領域毎に順次格納する構成としてある。
【００１４】
このような構成からなる本発明の画像形成装置によれば、描画対象となる図形が展開されるページフレームを分割し、複数のバンド領域とし、バンド領域毎に本発明の画像処理を行ういわゆるバンド処理（又はバンディング処理）を併用して適用することが可能となる。
このため、ページ単位での出力完了を待たずに、バンド領域単位で順次画像形成データを出力することができるため、メモリの節約のみならず、ファーストプリント時間の短縮等、より高速化を図ることができる。
【発明の効果】
【００１５】
本発明の画像形成装置によれば、描画対象となる複数図形の組み合わせによって包含される不要な図形データを簡易な制御プロセスにもとづいて削除し、画像処理速度を効果的に向上させることができる。
特に、図形の最大矩形領域、バウンディングボックス領域を用いて、処理の簡素化を図り、また、バンド処理を併用することによって、さらに高速化を図ることが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明に係る画像形成装置の好ましい実施形態について図１〜図１３を参照して説明する。
ここで、以下に示す本実施形態の画像形成装置は、プログラム（ソフトウェア）の命令によりコンピュータで実行される処理，手段，機能によって実現される。プログラムは、コンピュータの各構成要素に指令を送り、以下に示すような所定の処理・機能を行わせる。すなわち、本実施形態の画像形成装置における各処理・手段は、プログラムとコンピュータとが協働した具体的手段によって実現される。
なお、プログラムの全部又は一部は、例えば、磁気ディスク，光ディスク，半導体メモリ，その他任意のコンピュータで読取り可能な記録媒体により提供され、記録媒体から読み出されたプログラムがコンピュータにインストールされて実行される。また、プログラムは、記録媒体を介さず、通信回線を通じて直接にコンピュータにロードし実行することもできる。
【００１７】
［第一実施形態］
まず、図１〜図４を参照して、本発明に係る画像形成装置の第一実施形態であるページプリンタについて説明する。
図１は、本実施形態に係るページプリンタにおける描画処理の原理を説明するための説明図であり、図２は、本実施形態に係るページプリンタに用いるディスプレイリストを説明するための説明図である。
【００１８】
本実施形態のページプリンタにおいては、まず、図１（ａ）に示すように、受信した印刷データから対象となる図形１０１が抽出されたものとする。
続けて、図形１０１を部分的に覆う形状の図形１０２が抽出されたものとする（図１（ｂ））。
最後に、図形１０３が抽出され、結果、図形１０１が、図形１０２と図形１０３によって完全に隠れる状態となっている（図１（ｃ））。
【００１９】
このため、図形１０１は実際の出力画像に反映されないにも関わらず、一般的なページプリンタの内部処理においては描画処理の対象のままとなっている。
本実施形態に係るページプリンタは、このように、図形１０２や図形１０３との相互の関係においては包含関係がなく、重複関係にある場合であっても、図形１０２と図形１０３が合わさることによって図形１０１が包含される場合には、図形１０１をディスプレイリストから削除し、処理の効率化と高速化を図るものである。
【００２０】
ここで、ディスプレイリストとは、プリンタの描画機能において、受信した印刷データをラスタライズする前に一旦単純な図形に分割して中間コードを作成し、記憶しておくためのデータテーブルであり、図形描画に必要な位置座標、幅、高さなどのデータをもつものである。
ディスプレイリストの記憶方法としては、受信した描画データを順次リスト構造でつなぐ方法が通常的に採られている。したがって、リスト上、前のデータは古く、後につながれているデータほど新しいことを意味している。
【００２１】
つまり、ページ平面上においてある図形の位置が他の図形の領域にすべて包含されて隠れてしまう場合には、後から描画する図形は前の図形の上に描画されることとなるが、この場合、前の図形は描画する必要はないので、削除することによって描画処理の無駄を省くことができる。
例えば、図２（ａ）のようにディスプレイリストがつながっているとき、ディスプレイリストとしてｎ番目につながれた図形２０２がｎ＋１番目以降の図形によってすべて包含される場合には、図２（ｂ）に示すように、図形２０２を削除することによって不要なデータ処理を省くことができる。
【００２２】
次に、本発明の第一実施形態に係るページプリンタの構成と仕組みについて図３及び図４を参照しながら説明する。
図３は、本実施形態に係るページプリンタの基本的な構成を示したブロック図である。
プリントデータ受信記憶部１１は、図示しないホストコンピュータ等から受信した印刷データをメモリ等の記憶媒体にバッファリングするものである。
ＰＤＬ解析部１２は、受信した印刷データをエミュレータによって解析し、しかるべき処理を施す。具体的には、データ抽出手段により、印刷データから描画対象となる図形データとその座標データを抽出する。
ディスプレイリスト作成部１３は、効率よくページラスタライズするために、簡易な形に分割した図形をディスプレイリストとして順次作成し格納するものである。
【００２３】
ディスプレイリスト情報修正部１４は、ディスプレイリストにおいて、ある図形が他の図形に重なるときにこれを検出し（重複領域検出手段）、下になる図形の重なり部分を取り除くように図形の座標データを修正するものである（領域変更手段）。
例えば、図４（ａ）に示すように、まず描画対象となる図形１０１があり、その矩形領域を示す座標データとして、頂点Ａ（ｘ１，ｙ１）と頂点Ｂ（ｘ２，ｙ２）が抽出されたものとする。
ここで、図４（ｂ）に示すように、図形１０１の一部が重なる図形１０２が抽出された場合には、ディスプレイリスト情報修正部１４は、もとの図形１０１の座標データのうち、頂点Ａ（ｘ１，ｙ１）を頂点Ｃ（ｘ１’，ｙ１’）に変更する。
【００２４】
ディスプレイリスト削除部１５は、ディスプレイリスト情報修正部１４による座標データの修正にも対応しており、ある図形が他の一の図形によって完全に隠れる状態とみなされる場合には、描画する必要はないと判断し、ディスプレイリストから係る図形データを削除するものである（包含図形削除手段）。
つまり、前述した例の場合においては、頂点Ｃ（ｘ１’，ｙ１’）及び頂点Ｂ（ｘ２，ｙ２）からなる領域１１１が他の図形によって隠れるような場合には、もとの図形１０１のデータをディスプレイリストから削除することとしている。
ページラスタライズ部１６は、ディスプレイリスト作成部１３によって作成され、または、ディスプレイリスト削除部１５によって不要な図形データが削除された後にディスプレイリストに格納されてある図形データをビットマップ化して出力するものである（出力手段）。
【００２５】
以上説明したように、本実施形態のページプリンタによれば、各図形の重なりを検出し、座標データ（領域データ）を変更することによって、複数の図形によって隠れる図形のデータを削除するようにしてある。
つまり、各図形が相対的には部分的に重複するにすぎない関係であっても、対象となる図形が他の複数図形の組み合わせによって包含される場合には描画対象から除外するように制御している。
【００２６】
このため、無駄な描画対象データを極力削除でき、描画処理の速度を向上させることが可能となる。
加えて、制御プロセスが簡単な仕組みとなっているため、処理負担が少なく、また、既存の装置においても必要最低限の改造等を行うことによって本実施形態に係るページプリンタを実現することが可能である。
したがって、処理効率の向上とともに高速化が図られ、汎用性・拡張性に優れた画像形成装置を容易に実現し、提供することができる。
【００２７】
［第二実施形態］
次に、本発明の画像形成装置の第二実施形態に係るページプリンタについて図５乃至図１２を参照しながら説明を行う。
図５は、本発明の第二実施形態に係るページプリンタにおける描画処理の原理を説明するための説明図であり、図６は、本実施形態に係るページプリンタにおいて用いる最大矩形領域を説明するための説明図である。
本実施形態では、バウンディングボックス領域及び最大矩形領域を図形領域として取り扱い、必要な制御を行うこととしている。
そこで、まず、バウンディングボックス領域と最大矩形領域について説明を行う。
【００２８】
バウンディングボックス領域とは、図５（ａ）左図に示すように、図形３０１に外接する最小の矩形領域３０２をいい、対象となる図形を包含する最小のボックスをいう。
一方、最大矩形領域とは、図５（ａ）右図に示すように、図形３０３に内接する最大の矩形領域３０４をいい、換言すると、図形の２つの平行な辺とそれらの辺に垂直な線によってできる矩形領域をいう。
【００２９】
最大矩形領域の実際の求め方としては、まず、水平方向に平行な２辺があるかどうかを調べる。例えば、図６に示す図形の場合には、頂点１乃至頂点４の各座標を調べて、ｙ座標の値で等しい２点があるかどうかで平行な辺の有無が判別できる。
具体的には、頂点１のｙ座標値と等しい頂点を検索すると、頂点４が該当するため、水平な辺として辺（頂点１−頂点４）が抽出される。また同様にして辺（頂点２−頂点３）が抽出される。
次に、上述のようにして抽出された各辺が、その辺の各頂点からの垂線と相互に交わるかどうかを判定し、交わる場合の交点（交点５、交点６）を検出する。
このようにして、頂点２−頂点３−交点５−交点６からなる最大矩形領域（図６斜線部）を求めることができる。
【００３０】
なお、最大矩形領域に関しては、図５（ｃ）に示すとおり対象となる図形が台形の場合には最大矩形領域を求めるが、内側に矩形部分をもたない図形に関しては内接する矩形は求めず、本実施形態における最大矩形領域の対象外とする。
すなわち、水平方向もしくは垂直方向に平行な２つの線（辺）をもたない図形や２つの平行な線（辺）に垂直な線によって矩形を作り出せない図形は、最大矩形領域は求めず、例えば、図５（ｄ）のように平行な２辺を含む矩形ができない図形や、図５（ｅ）のように1辺が０（ゼロ）の三角形（ｂ）の図形についても最大矩形領域を求める対象外としている。
これは、実際の処理においては、事前に行う分割の仕方によって係る図形の発生を抑えることが可能であり、仮に発生したとしてもその誤差はわずかであり、高速化等のメリットを勘案すると、品質等に関するデメリットは極めて少ないものとなるからである。
【００３１】
このようにして求めたバウンディングボックス領域と最大矩形領域の位置情報は、予めメモリ等に記憶しておき、矩形図形以外の台形の重なりを検出するために用いる。
具体的には、現在作成しているディスプレイリストの図形がもつ最大矩形領域に対して、以前に作成しているディスプレイリストのバウンディングボックス領域が重なっているか否かを判定する。
【００３２】
例えば、図５（ｂ）に示すように三角形３０１のバウンディングボックス領域３０２と、台形３０３のもつ最大矩形領域３０４の重なりを判定し、重なる場合には、バウンディングボックス領域の頂点Ｂ（ｘ２，ｙ２）を頂点Ｄ（ｘ２’，ｙ２’）に変更する。
そして、この頂点Ａ（ｘ１，ｙ１）及び頂点Ｄ（ｘ２’，ｙ２’）からなる矩形領域が他の図形に包含される場合には、ディスプレイリストから図形３０１のデータを削除することとしている。
【００３３】
このように、バウンディングボックス領域及び最大矩形領域を用いた制御を行う事により、結果的に、複数図形の組み合わせによって隠れる図形の無駄な描画処理を省き、処理速度の向上を図ることが可能となる。
また、単純な矩形に置き換えて各種制御を行うことにより、かかる計算量を大幅に削減し、演算処理等にかかる負担を低減することができる。
【００３４】
次に、本実施形態に係るページプリンタの動作手順について図７乃至図１２を用いて説明する。
図７及び図８は、本実施形態に係るページプリンタの動作手順を示したフローチャートであり、図９乃至図１２は、本実施形態のページプリンタにおける動作手順を具体的に説明するための説明図である。
なお、ここで述べる動作手順は、本実施形態のページプリンタが、図９（ａ）に示す星形図形５０１を最初に受信した後、図９（ｂ）に示す最大矩形領域５０２とする図形を受信し、さらにその後図９（ｃ）に示す最大矩形領域５０３とする図形を抽出し、結果、星形図形５０１が最大矩形領域５０２及び５０３によって完全に隠れるケースを典型例として所々説明を行う。
【００３５】
図７に示すように、まず、ページプリンタは、ホストコンピュータ等の情報処理装置から印刷データを受信し（Ａ１）、印刷データに記述してあるエミュレーションの描画命令を解釈する（Ａ２）。
次に、抽出された図形の位置決定や大きさ・変形などの変換処理を行った後、ディスプレイリストを作成し、メモリ上に記憶する（Ａ３）。
具体的には、図１０に示すように、対象となる元の図形５０１を分割し、図形５１１乃至図形５１５からなる複数の単純な図形（描画プリミティブ）に展開する。つまり、パスの各々の頂点（区切り点）を基準にして水平方向に分割する。
【００３６】
ここで、現在処理している図形が混色や透過などの要素を含まない図形のコピー命令か否かを判定する（Ａ４）。本実施形態の特徴である包含図形削除手段や重複領域検出手段等は、塗りつぶし図形を対象としているからである。
ステップＡ４の結果、対象図形については混色等を含まないコピー命令であると判定された場合（Ａ４ ＹＥＳ）、ディスプレイリストがもつ図形の領域データ（座標データ等）からその図形のバウンディングボックス領域を算出し（バウンディングボックス領域算出手段）、ディスプレイリストの情報に追加して記憶する（Ａ５）。
【００３７】
具体的には、図１１に示すように、図１０における図形５１１乃至図形５１５の各図形についてバウンディングボックス領域５２１乃至５２５を算出し、後から描画される図形（最大矩形領域）との重なりの判定対象とする。
一方、すべての対象図形についてステップＡ４の判定を行い、透過や混色を含むコピー命令の対象と判定された図形（Ａ４ ＮＯ）については、そのままラスタライズ処理を行う（図８ Ａ１３）。
【００３８】
次に、ディスプレイリストの図形がもつ最大矩形領域Ｒを最大矩形領域算出手段により算出する（Ａ６）。
ここで、最大矩形領域Ｒの値が０（ゼロ）か、否かを判定する（Ａ７）。
ステップＡ７の結果、最大矩形領域Ｒの値が０（ゼロ）でないとき（Ａ７ ＮＯ）、つまり、対象となる図形が矩形か台形であるときは、図８に示すステップＡ８乃至ステップＡ１２の処理を、ディスプレイリストの先頭ｎ＝０に格納された図形から始め、ディスプレイリストの数分繰り返す（ループ２）。
一方、ディスプレイリストのすべてについてステップＡ７の判定を行った結果、図形の最大矩形領域Ｒの値が０（ゼロ）であると判定された図形（Ａ７ ＹＥＳ）については、そのままラスタライズ処理を行う（図８ Ａ１３）。
【００３９】
ステップＡ８では、いま作成したディスプレイリストの図形の最大矩形領域Ｒと、以前に作成したｎ番目のディスプレイリストの図形のバウンディングボックス領域Ｂｎとの比較処理を行う。
まず、最大矩形領域Ｒとバウンディングボックス領域Ｂｎが重なっているかどうかを判定する（Ａ９）。なお、これらの領域が相互に重なっていないとき（ステップＡ９ ＮＯ）は、次のディスプレイリストの図形（ｎ＋１番目の図形）の判定を行うこととし、以前作成したすべての図形について順次ステップＡ９の判定を行う。
【００４０】
ステップＡ９の結果、以前作成したバウンディングボックス領域と現在処理中の図形の最大矩形領域Ｒとの重なりが検出された場合（Ａ９ ＹＥＳ）には、次に、最大矩形領域Ｒがバウンディングボックス領域を完全に包含しているか否かを判定する（Ａ１０）。
ステップＡ１０の結果、最大矩形領域Ｒが、バウンディングボックス領域を完全に包含している場合（Ａ１０ ＹＥＳ）には、ｎ番目のディスプレイリストの図形をメモリ上から削除する（Ａ１１）。
一方、ステップＡ１０の結果、最大矩形領域Ｒがバウンディングボックス領域を完全に包含しておらず、部分的に重なっている場合（Ａ１０ ＮＯ）には、ｎ番目のディスプレイリストのバウンディングボックス領域Ｂｎの頂点座標データを修正する（Ａ１２）。
【００４１】
具体的には、図１１に示す各バウンディングボックス領域５２１乃至５２５と最大矩形領域５０２について各々ステップＡ９及びステップＡ１０の判定処理を行う。
その結果、バウンディングボックス領域５２５は、最大矩形領域５０２に完全に包含されているので図形５１５はディスプレイリストから削除される。
また、バウンディングボックス領域５２１乃至５２４は、最大矩形領域５０２に完全に包含されておらず、一部が重なるので、それぞれ頂点座標を修正し、５３１乃至５３４のようにバウンディングボックス領域を変更する。
【００４２】
そして、図９（ｃ）に示すように、新たに最大矩形領域５０３が認識された場合には、バウンディングボックス領域５３１乃至５３４はこの最大矩形領域５０３にすべて包含されることとなるため、原図形である図形５１１乃至図形５１４のデータはディスプレイリストから削除されることとなる。
【００４３】
以上のように、ディスプレイリストにある全ての図形について、ループ１及びループ２に示された所定の手順を繰り返し実施することによって、ディスプレイリスト上からは不要な図形データが削除されるため、ディスプレイリスト上にある実質的に必要な図形のみがラスタライズされビットマップ出力されることとなる（Ａ１３）。
【００４４】
以上説明したように、本実施形態のページプリンタによれば、ディスプレイリスト上にある図形の最大矩形領域やバウンディングボックス領域を求め、これらの領域が部分的に重なる場合には、バウンディングボックス領域を変更した上で、他の図形との包含関係の有無を検出するようにしている。
そして、変更後のバウンディングボックス領域が他の図形の最大矩形領域に包含される場合には、そのバウンディングボックスの元となる図形のデータを削除するように制御している。
【００４５】
これにより、上述した第一実施形態と同様の効果が発揮されるだけでなく、複雑な図形についても容易かつ柔軟に対応することが可能となる。
また、対象となる図形の領域を単純な矩形領域に置き換えて、各種制御を行うようにしているため、演算処理等の負担を大幅に抑えることができる。
したがって、プログラムやＣＰＵ等を極めてシンプルな構成にすることができるとともに、信頼性の高いページプリンタを実現することができる。
【００４６】
［第三実施形態］
次に、本発明の画像形成装置の第三実施形態に係るページプリンタについて図１３を参照しながら説明を行う。
本実施形態に係るページプリンタは、メモリ使用量を考慮してページをバンドに区切って（バンド領域生成手段）、一定のバンド領域単位に描画するいわゆるバンド処理を行うことも可能である。
バンド処理においては、バンド領域内での図形の包含関係や重複関係などを考慮する必要があるが、特に問題は発生せず、むしろ、より効率よく画像処理を行うことができる。
【００４７】
例えば、図１３（ａ）のように、３つの矩形があり、矩形６０１が最も上に描画され、次に矩形６０２が描画され、最も下に位置する図形は矩形６０３であるとする。
この場合、ページ全体からみると３つの図形は一部が重なるのみで、包含関係は存在していない。したがって、そのままでは、包含図形削除手段による方法では、重複部分の図形データは削除できない。
しかし、図１３（ｂ）に示すように、バンド領域単位で見ると、ｂａｎｄ（Ｎ）内の矩形６１３は、矩形６１１と矩形６１２によって包含されているため、描画対象とはみなされず、ディスプレイリストから削除するように制御することができる。
【００４８】
なお、バンド処理において、ディスプレイリストはバンド毎に管理されているので図１３（ａ）に示す矩形６０３の全体が削除されることはない。
このように、本実施形態のページプリンタでは、ページへの直接描画処理（ＦＵＬＬ−ＶＲＡＭ）又はバンド処理の如何に関わらず適用することが可能となっている。
【００４９】
以上説明したように、本実施形態のページプリンタによれば、第一実施形態や第二実施形態と同様の効果が発揮されるだけでなく、バンド処理を採用することによって、さらに効率よく描画処理を行うことができる。
また、ページへの直接描画処理（ＦＵＬＬ−ＶＲＡＭ）やバンド処理のいずれの処理手段にも対応できるため、プリンタの性能、出力図形の種類、ユーザが求める品質等に柔軟に対応することが可能である。
【００５０】
以上、本発明の画像形成装置について、好ましい実施形態を示して説明したが、本発明にかかる画像形成装置は、上述した実施形態にのみ限定されるものではなく、本発明の範囲で種々の変更実施が可能であることは言うまでもない。
例えば、本発明の画像形成装置は、ページプリンタのみならず、コピー機やファクシミリ、スキャナ等といった他の画像形成装置、複合装置であってもよい。
【産業上の利用可能性】
【００５１】
本発明は、ページプリンタ等のプリンタや、コピー機、複合機等の画像形成装置やネットワークプリンタ等の画像形成システムに好適に利用することができる。
【図面の簡単な説明】
【００５２】
【図１】本発明の画像形成装置の第一実施形態に係るページプリンタの原理を説明するための説明図である。
【図２】本発明の画像形成装置の第一実施形態に係るページプリンタに用いるディスプレイリストを説明するための説明図である。
【図３】本発明の画像形成装置の第一実施形態に係るページプリンタの基本的な構成を示したブロック図である。
【図４】本発明の画像形成装置の第一実施形態に係るページプリンタの基本的な仕組みを説明するための説明図である。
【図５】本発明の画像形成装置の第二実施形態に係るページプリンタの原理を説明するための説明図である。
【図６】本発明の画像形成装置の第二実施形態に係るページプリンタにおいて用いる最大矩形領域を説明するための説明図である。
【図７】本発明の画像形成装置の第二実施形態に係るページプリンタの動作手順の前段を示したフローチャートである。
【図８】本発明の画像形成装置の第二実施形態に係るページプリンタの動作手順の後段を示したフローチャートである。
【図９】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第一の説明図である。
【図１０】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第二の説明図である。
【図１１】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第三の説明図である。
【図１２】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第四の説明図である。
【図１３】本発明の画像形成装置の第三実施形態に係るページプリンタにおいてバンド処理を説明するための説明図である。
【図１４】従来の画像形成装置における中間リスト画像の削除原理を示す説明図である。
【符号の説明】
【００５３】
１１ プリントデータ受信記憶部
１２ ＰＤＬ解析部
１３ ディスプレイリスト作成部
１４ ディスプレイリスト情報修正部
１５ ディスプレイリスト削除部
１６ ページラスタライズ部
【技術分野】
【０００１】
本発明は、画像形成装置に関し、より詳しくは、描画処理時間を効果的に短縮化できる画像形成装置に関する。
【背景技術】
【０００２】
従来から、画像処理技術に関する様々な研究が継続的にすすめられており、その一つとしてプリンタやスキャナ等、画像形成装置の高速処理技術の研究が行われてきた。
特に、近年では、出力のカラー化や多階調化等により、取り扱うデータ処理量が大幅に増加しており、画像処理の更なる高速化が求められている。
【０００３】
このため、中間リストの記憶領域を減少させてビットマップ化速度の向上を目的とした画像処理装置が提案されている（例えば、特許文献１）。
この画像処理装置によれば、図１４に示すように、先に描画される第一の図形７０１の描画領域が、後に描画される第二の図形７０２の描画領域に包含される場合には、中間リストから第一の図形７０１のデータを削除し、高速化を図るようにしている。
また、第一の図形の描画領域と第二の図形の描画領域とが重なっている場合には、第一の図形からその重なり部分を削除することによっても高速化を図るようにしている。
【０００４】
【特許文献１】特開２００１−８８３６７号公報（第１頁、第１図）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、以上のような従来提案されているに画像処理装置おいては、第一の図形が後の一の図形によって包含される場合には直接的に第一の図形データを削除することができるが、第一の図形が後の複数の図形によって包含される場合には第一の図形データが直接的には削除されず、複数の重なり部分をその数分削除することによって始めて第一の図形データの全部を削除することができる。
したがって、第一の図形が多数の図形によって包含される場合には、データ削除に要する処理数が大幅に増加するため、かえって処理の渋滞を招くこととなり、問題となっていた。
【０００６】
本発明は、以上のような従来の技術が有する問題を解決するために提案されたものであり、複数図形の組み合わせによって包含される図形のデータを効率的に削除することによって、出力の高速化を図ることが可能な画像形成装置の提供を目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明の画像形成装置は、請求項１に記載するように、所定のデータを解析し、図形データとその領域データとを抽出するデータ抽出手段と、抽出された一以上の前記図形データ及びその領域データを順次格納するディスプレイリストと、先に格納された図形の領域が、後に格納された一の図形の領域に包含される場合に、前記先に格納された図形のデータを前記ディスプレイリストから削除する包含図形削除手段と、前記ディスプレイリストに格納されている図形データに基づき画像形成データを出力する出力手段と、前記ディスプレイリストにおいて、先に格納された第一の図形の領域と後に格納された第二の図形の領域との重複領域を検出する重複領域検出手段と、前記第一の図形の領域を、前記重複領域を削除した領域に変更する領域変更手段と、前記包含図形削除手段は、前記領域変更手段によって変更された前記第一の図形の領域が、後に格納された前記第二の図形以外の図形の領域に包含される場合に、前記第一の図形データを前記ディスプレイリストから削除する構成としてある。
【０００８】
このような構成からなる本発明の画像形成装置によれば、描画対象となる図形相互の重複領域を求め、元の図形の領域からその重複領域を削除することとしてある。
そして、重複領域が削除された図形の領域を基準とし、この基準領域が他の図形に包含されている場合には係る図形を削除し、不要な描画データの削除を行うようにしている。
したがって、結果的には、従来のように一の図形が他の一の図形のみによって包含される場合に限らず、複数図形の組み合わせによって包含される場合でも係る図形データを削除できるようになる。
また、図形データの削除に至るプロセスが、領域データのみを基準として制御する簡易なものとなっているため、処理にかかる負担を大幅に抑えることが可能となる。このため、不要な図形データを効果的に削除でき、画像処理の効率化及び処理速度の向上を図ることができる。
【０００９】
また、本発明の画像形成装置は、請求項２に記載するように、前記領域データにもとづき、図形の最大矩形領域を算出する最大矩形領域算出手段と、前記領域データにもとづき、図形のバウンディングボックス領域を算出するバウンディングボックス領域算出手段とを備え、前記重複領域検出手段は、前記ディスプレイリストにおいて、先に格納された第一の図形のバウンディングボックス領域と後に格納された第二の図形の最大矩形領域との重複領域を検出し、前記領域変更手段は、前記第一の図形のバウンディングボックス領域を、前記重複領域を削除した領域に変更し、前記包含図形削除手段は、前記領域変更手段によって変更された第一の図形のバウンディングボックス領域が、後に格納された第二の図形以外の図形の最大矩形領域に包含される場合に、前記第一の図形のデータを前記ディスプレイリストから削除する構成としてある。
【００１０】
このような構成からなる本発明の画像形成装置によれば、前述の最大矩形領域とバウンディングボックス領域を求め、これらを図形の領域とみなして各処理を行うようにしている。
具体的には、描画対象となる第一図形のバウンディングボックス領域と第二図形の最大矩形領域との重複領域を求め、第一図形のバウンディングボックス領域からその重複領域を削除することとしてある。
そして、重複領域が削除された後のバウンディングボックス領域を基準とし、この基準領域が他の図形の最大矩形領域に包含されている場合には係る図形を削除し、不要な描画データの削除を行うようにしている。
したがって、描画対象が複雑な図形であっても、近似する単純な矩形領域に置き換えることによって、演算処理にかかる負担を大幅に抑えることができるので、図形相互の包含の有無を容易に判定することができる。
これにより、画像処理をさらに効率化し、高速化させることができる。
【００１１】
また、本発明の画像形成装置は、請求項３に記載するように、前記領域データは、少なくとも所定の座標データによって構成されるようにしてある。
【００１２】
このような構成からなる本発明の画像形成装置によれば、描画対象となる図形の領域を座標データにもとづき抽出することができるため、迅速に図形位置を認識することが可能となる。
これにより、より効率的で高速な処理が行えるようになる。
特に、バウンディングボックス領域及び最大矩形領域の算出、図形相互の包含・重複の検出、領域データの変更処理など、様々な演算処理にも迅速かつ容易に対応することが可能である。
【００１３】
また、本発明の画像形成装置は、請求項４に記載するように、出力単位となるページフレームを一定基準にもとづき分割し、複数のバンド領域を生成するバンド領域生成手段を、備え、前記データ抽出手段は、所定のデータを解析し、図形データとその領域データとをバンド領域毎に抽出し、前記ディスプレイリストは、抽出された一以上の前記図形データ及びその領域データをバンド領域毎に順次格納する構成としてある。
【００１４】
このような構成からなる本発明の画像形成装置によれば、描画対象となる図形が展開されるページフレームを分割し、複数のバンド領域とし、バンド領域毎に本発明の画像処理を行ういわゆるバンド処理（又はバンディング処理）を併用して適用することが可能となる。
このため、ページ単位での出力完了を待たずに、バンド領域単位で順次画像形成データを出力することができるため、メモリの節約のみならず、ファーストプリント時間の短縮等、より高速化を図ることができる。
【発明の効果】
【００１５】
本発明の画像形成装置によれば、描画対象となる複数図形の組み合わせによって包含される不要な図形データを簡易な制御プロセスにもとづいて削除し、画像処理速度を効果的に向上させることができる。
特に、図形の最大矩形領域、バウンディングボックス領域を用いて、処理の簡素化を図り、また、バンド処理を併用することによって、さらに高速化を図ることが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明に係る画像形成装置の好ましい実施形態について図１〜図１３を参照して説明する。
ここで、以下に示す本実施形態の画像形成装置は、プログラム（ソフトウェア）の命令によりコンピュータで実行される処理，手段，機能によって実現される。プログラムは、コンピュータの各構成要素に指令を送り、以下に示すような所定の処理・機能を行わせる。すなわち、本実施形態の画像形成装置における各処理・手段は、プログラムとコンピュータとが協働した具体的手段によって実現される。
なお、プログラムの全部又は一部は、例えば、磁気ディスク，光ディスク，半導体メモリ，その他任意のコンピュータで読取り可能な記録媒体により提供され、記録媒体から読み出されたプログラムがコンピュータにインストールされて実行される。また、プログラムは、記録媒体を介さず、通信回線を通じて直接にコンピュータにロードし実行することもできる。
【００１７】
［第一実施形態］
まず、図１〜図４を参照して、本発明に係る画像形成装置の第一実施形態であるページプリンタについて説明する。
図１は、本実施形態に係るページプリンタにおける描画処理の原理を説明するための説明図であり、図２は、本実施形態に係るページプリンタに用いるディスプレイリストを説明するための説明図である。
【００１８】
本実施形態のページプリンタにおいては、まず、図１（ａ）に示すように、受信した印刷データから対象となる図形１０１が抽出されたものとする。
続けて、図形１０１を部分的に覆う形状の図形１０２が抽出されたものとする（図１（ｂ））。
最後に、図形１０３が抽出され、結果、図形１０１が、図形１０２と図形１０３によって完全に隠れる状態となっている（図１（ｃ））。
【００１９】
このため、図形１０１は実際の出力画像に反映されないにも関わらず、一般的なページプリンタの内部処理においては描画処理の対象のままとなっている。
本実施形態に係るページプリンタは、このように、図形１０２や図形１０３との相互の関係においては包含関係がなく、重複関係にある場合であっても、図形１０２と図形１０３が合わさることによって図形１０１が包含される場合には、図形１０１をディスプレイリストから削除し、処理の効率化と高速化を図るものである。
【００２０】
ここで、ディスプレイリストとは、プリンタの描画機能において、受信した印刷データをラスタライズする前に一旦単純な図形に分割して中間コードを作成し、記憶しておくためのデータテーブルであり、図形描画に必要な位置座標、幅、高さなどのデータをもつものである。
ディスプレイリストの記憶方法としては、受信した描画データを順次リスト構造でつなぐ方法が通常的に採られている。したがって、リスト上、前のデータは古く、後につながれているデータほど新しいことを意味している。
【００２１】
つまり、ページ平面上においてある図形の位置が他の図形の領域にすべて包含されて隠れてしまう場合には、後から描画する図形は前の図形の上に描画されることとなるが、この場合、前の図形は描画する必要はないので、削除することによって描画処理の無駄を省くことができる。
例えば、図２（ａ）のようにディスプレイリストがつながっているとき、ディスプレイリストとしてｎ番目につながれた図形２０２がｎ＋１番目以降の図形によってすべて包含される場合には、図２（ｂ）に示すように、図形２０２を削除することによって不要なデータ処理を省くことができる。
【００２２】
次に、本発明の第一実施形態に係るページプリンタの構成と仕組みについて図３及び図４を参照しながら説明する。
図３は、本実施形態に係るページプリンタの基本的な構成を示したブロック図である。
プリントデータ受信記憶部１１は、図示しないホストコンピュータ等から受信した印刷データをメモリ等の記憶媒体にバッファリングするものである。
ＰＤＬ解析部１２は、受信した印刷データをエミュレータによって解析し、しかるべき処理を施す。具体的には、データ抽出手段により、印刷データから描画対象となる図形データとその座標データを抽出する。
ディスプレイリスト作成部１３は、効率よくページラスタライズするために、簡易な形に分割した図形をディスプレイリストとして順次作成し格納するものである。
【００２３】
ディスプレイリスト情報修正部１４は、ディスプレイリストにおいて、ある図形が他の図形に重なるときにこれを検出し（重複領域検出手段）、下になる図形の重なり部分を取り除くように図形の座標データを修正するものである（領域変更手段）。
例えば、図４（ａ）に示すように、まず描画対象となる図形１０１があり、その矩形領域を示す座標データとして、頂点Ａ（ｘ１，ｙ１）と頂点Ｂ（ｘ２，ｙ２）が抽出されたものとする。
ここで、図４（ｂ）に示すように、図形１０１の一部が重なる図形１０２が抽出された場合には、ディスプレイリスト情報修正部１４は、もとの図形１０１の座標データのうち、頂点Ａ（ｘ１，ｙ１）を頂点Ｃ（ｘ１’，ｙ１’）に変更する。
【００２４】
ディスプレイリスト削除部１５は、ディスプレイリスト情報修正部１４による座標データの修正にも対応しており、ある図形が他の一の図形によって完全に隠れる状態とみなされる場合には、描画する必要はないと判断し、ディスプレイリストから係る図形データを削除するものである（包含図形削除手段）。
つまり、前述した例の場合においては、頂点Ｃ（ｘ１’，ｙ１’）及び頂点Ｂ（ｘ２，ｙ２）からなる領域１１１が他の図形によって隠れるような場合には、もとの図形１０１のデータをディスプレイリストから削除することとしている。
ページラスタライズ部１６は、ディスプレイリスト作成部１３によって作成され、または、ディスプレイリスト削除部１５によって不要な図形データが削除された後にディスプレイリストに格納されてある図形データをビットマップ化して出力するものである（出力手段）。
【００２５】
以上説明したように、本実施形態のページプリンタによれば、各図形の重なりを検出し、座標データ（領域データ）を変更することによって、複数の図形によって隠れる図形のデータを削除するようにしてある。
つまり、各図形が相対的には部分的に重複するにすぎない関係であっても、対象となる図形が他の複数図形の組み合わせによって包含される場合には描画対象から除外するように制御している。
【００２６】
このため、無駄な描画対象データを極力削除でき、描画処理の速度を向上させることが可能となる。
加えて、制御プロセスが簡単な仕組みとなっているため、処理負担が少なく、また、既存の装置においても必要最低限の改造等を行うことによって本実施形態に係るページプリンタを実現することが可能である。
したがって、処理効率の向上とともに高速化が図られ、汎用性・拡張性に優れた画像形成装置を容易に実現し、提供することができる。
【００２７】
［第二実施形態］
次に、本発明の画像形成装置の第二実施形態に係るページプリンタについて図５乃至図１２を参照しながら説明を行う。
図５は、本発明の第二実施形態に係るページプリンタにおける描画処理の原理を説明するための説明図であり、図６は、本実施形態に係るページプリンタにおいて用いる最大矩形領域を説明するための説明図である。
本実施形態では、バウンディングボックス領域及び最大矩形領域を図形領域として取り扱い、必要な制御を行うこととしている。
そこで、まず、バウンディングボックス領域と最大矩形領域について説明を行う。
【００２８】
バウンディングボックス領域とは、図５（ａ）左図に示すように、図形３０１に外接する最小の矩形領域３０２をいい、対象となる図形を包含する最小のボックスをいう。
一方、最大矩形領域とは、図５（ａ）右図に示すように、図形３０３に内接する最大の矩形領域３０４をいい、換言すると、図形の２つの平行な辺とそれらの辺に垂直な線によってできる矩形領域をいう。
【００２９】
最大矩形領域の実際の求め方としては、まず、水平方向に平行な２辺があるかどうかを調べる。例えば、図６に示す図形の場合には、頂点１乃至頂点４の各座標を調べて、ｙ座標の値で等しい２点があるかどうかで平行な辺の有無が判別できる。
具体的には、頂点１のｙ座標値と等しい頂点を検索すると、頂点４が該当するため、水平な辺として辺（頂点１−頂点４）が抽出される。また同様にして辺（頂点２−頂点３）が抽出される。
次に、上述のようにして抽出された各辺が、その辺の各頂点からの垂線と相互に交わるかどうかを判定し、交わる場合の交点（交点５、交点６）を検出する。
このようにして、頂点２−頂点３−交点５−交点６からなる最大矩形領域（図６斜線部）を求めることができる。
【００３０】
なお、最大矩形領域に関しては、図５（ｃ）に示すとおり対象となる図形が台形の場合には最大矩形領域を求めるが、内側に矩形部分をもたない図形に関しては内接する矩形は求めず、本実施形態における最大矩形領域の対象外とする。
すなわち、水平方向もしくは垂直方向に平行な２つの線（辺）をもたない図形や２つの平行な線（辺）に垂直な線によって矩形を作り出せない図形は、最大矩形領域は求めず、例えば、図５（ｄ）のように平行な２辺を含む矩形ができない図形や、図５（ｅ）のように1辺が０（ゼロ）の三角形（ｂ）の図形についても最大矩形領域を求める対象外としている。
これは、実際の処理においては、事前に行う分割の仕方によって係る図形の発生を抑えることが可能であり、仮に発生したとしてもその誤差はわずかであり、高速化等のメリットを勘案すると、品質等に関するデメリットは極めて少ないものとなるからである。
【００３１】
このようにして求めたバウンディングボックス領域と最大矩形領域の位置情報は、予めメモリ等に記憶しておき、矩形図形以外の台形の重なりを検出するために用いる。
具体的には、現在作成しているディスプレイリストの図形がもつ最大矩形領域に対して、以前に作成しているディスプレイリストのバウンディングボックス領域が重なっているか否かを判定する。
【００３２】
例えば、図５（ｂ）に示すように三角形３０１のバウンディングボックス領域３０２と、台形３０３のもつ最大矩形領域３０４の重なりを判定し、重なる場合には、バウンディングボックス領域の頂点Ｂ（ｘ２，ｙ２）を頂点Ｄ（ｘ２’，ｙ２’）に変更する。
そして、この頂点Ａ（ｘ１，ｙ１）及び頂点Ｄ（ｘ２’，ｙ２’）からなる矩形領域が他の図形に包含される場合には、ディスプレイリストから図形３０１のデータを削除することとしている。
【００３３】
このように、バウンディングボックス領域及び最大矩形領域を用いた制御を行う事により、結果的に、複数図形の組み合わせによって隠れる図形の無駄な描画処理を省き、処理速度の向上を図ることが可能となる。
また、単純な矩形に置き換えて各種制御を行うことにより、かかる計算量を大幅に削減し、演算処理等にかかる負担を低減することができる。
【００３４】
次に、本実施形態に係るページプリンタの動作手順について図７乃至図１２を用いて説明する。
図７及び図８は、本実施形態に係るページプリンタの動作手順を示したフローチャートであり、図９乃至図１２は、本実施形態のページプリンタにおける動作手順を具体的に説明するための説明図である。
なお、ここで述べる動作手順は、本実施形態のページプリンタが、図９（ａ）に示す星形図形５０１を最初に受信した後、図９（ｂ）に示す最大矩形領域５０２とする図形を受信し、さらにその後図９（ｃ）に示す最大矩形領域５０３とする図形を抽出し、結果、星形図形５０１が最大矩形領域５０２及び５０３によって完全に隠れるケースを典型例として所々説明を行う。
【００３５】
図７に示すように、まず、ページプリンタは、ホストコンピュータ等の情報処理装置から印刷データを受信し（Ａ１）、印刷データに記述してあるエミュレーションの描画命令を解釈する（Ａ２）。
次に、抽出された図形の位置決定や大きさ・変形などの変換処理を行った後、ディスプレイリストを作成し、メモリ上に記憶する（Ａ３）。
具体的には、図１０に示すように、対象となる元の図形５０１を分割し、図形５１１乃至図形５１５からなる複数の単純な図形（描画プリミティブ）に展開する。つまり、パスの各々の頂点（区切り点）を基準にして水平方向に分割する。
【００３６】
ここで、現在処理している図形が混色や透過などの要素を含まない図形のコピー命令か否かを判定する（Ａ４）。本実施形態の特徴である包含図形削除手段や重複領域検出手段等は、塗りつぶし図形を対象としているからである。
ステップＡ４の結果、対象図形については混色等を含まないコピー命令であると判定された場合（Ａ４ ＹＥＳ）、ディスプレイリストがもつ図形の領域データ（座標データ等）からその図形のバウンディングボックス領域を算出し（バウンディングボックス領域算出手段）、ディスプレイリストの情報に追加して記憶する（Ａ５）。
【００３７】
具体的には、図１１に示すように、図１０における図形５１１乃至図形５１５の各図形についてバウンディングボックス領域５２１乃至５２５を算出し、後から描画される図形（最大矩形領域）との重なりの判定対象とする。
一方、すべての対象図形についてステップＡ４の判定を行い、透過や混色を含むコピー命令の対象と判定された図形（Ａ４ ＮＯ）については、そのままラスタライズ処理を行う（図８ Ａ１３）。
【００３８】
次に、ディスプレイリストの図形がもつ最大矩形領域Ｒを最大矩形領域算出手段により算出する（Ａ６）。
ここで、最大矩形領域Ｒの値が０（ゼロ）か、否かを判定する（Ａ７）。
ステップＡ７の結果、最大矩形領域Ｒの値が０（ゼロ）でないとき（Ａ７ ＮＯ）、つまり、対象となる図形が矩形か台形であるときは、図８に示すステップＡ８乃至ステップＡ１２の処理を、ディスプレイリストの先頭ｎ＝０に格納された図形から始め、ディスプレイリストの数分繰り返す（ループ２）。
一方、ディスプレイリストのすべてについてステップＡ７の判定を行った結果、図形の最大矩形領域Ｒの値が０（ゼロ）であると判定された図形（Ａ７ ＹＥＳ）については、そのままラスタライズ処理を行う（図８ Ａ１３）。
【００３９】
ステップＡ８では、いま作成したディスプレイリストの図形の最大矩形領域Ｒと、以前に作成したｎ番目のディスプレイリストの図形のバウンディングボックス領域Ｂｎとの比較処理を行う。
まず、最大矩形領域Ｒとバウンディングボックス領域Ｂｎが重なっているかどうかを判定する（Ａ９）。なお、これらの領域が相互に重なっていないとき（ステップＡ９ ＮＯ）は、次のディスプレイリストの図形（ｎ＋１番目の図形）の判定を行うこととし、以前作成したすべての図形について順次ステップＡ９の判定を行う。
【００４０】
ステップＡ９の結果、以前作成したバウンディングボックス領域と現在処理中の図形の最大矩形領域Ｒとの重なりが検出された場合（Ａ９ ＹＥＳ）には、次に、最大矩形領域Ｒがバウンディングボックス領域を完全に包含しているか否かを判定する（Ａ１０）。
ステップＡ１０の結果、最大矩形領域Ｒが、バウンディングボックス領域を完全に包含している場合（Ａ１０ ＹＥＳ）には、ｎ番目のディスプレイリストの図形をメモリ上から削除する（Ａ１１）。
一方、ステップＡ１０の結果、最大矩形領域Ｒがバウンディングボックス領域を完全に包含しておらず、部分的に重なっている場合（Ａ１０ ＮＯ）には、ｎ番目のディスプレイリストのバウンディングボックス領域Ｂｎの頂点座標データを修正する（Ａ１２）。
【００４１】
具体的には、図１１に示す各バウンディングボックス領域５２１乃至５２５と最大矩形領域５０２について各々ステップＡ９及びステップＡ１０の判定処理を行う。
その結果、バウンディングボックス領域５２５は、最大矩形領域５０２に完全に包含されているので図形５１５はディスプレイリストから削除される。
また、バウンディングボックス領域５２１乃至５２４は、最大矩形領域５０２に完全に包含されておらず、一部が重なるので、それぞれ頂点座標を修正し、５３１乃至５３４のようにバウンディングボックス領域を変更する。
【００４２】
そして、図９（ｃ）に示すように、新たに最大矩形領域５０３が認識された場合には、バウンディングボックス領域５３１乃至５３４はこの最大矩形領域５０３にすべて包含されることとなるため、原図形である図形５１１乃至図形５１４のデータはディスプレイリストから削除されることとなる。
【００４３】
以上のように、ディスプレイリストにある全ての図形について、ループ１及びループ２に示された所定の手順を繰り返し実施することによって、ディスプレイリスト上からは不要な図形データが削除されるため、ディスプレイリスト上にある実質的に必要な図形のみがラスタライズされビットマップ出力されることとなる（Ａ１３）。
【００４４】
以上説明したように、本実施形態のページプリンタによれば、ディスプレイリスト上にある図形の最大矩形領域やバウンディングボックス領域を求め、これらの領域が部分的に重なる場合には、バウンディングボックス領域を変更した上で、他の図形との包含関係の有無を検出するようにしている。
そして、変更後のバウンディングボックス領域が他の図形の最大矩形領域に包含される場合には、そのバウンディングボックスの元となる図形のデータを削除するように制御している。
【００４５】
これにより、上述した第一実施形態と同様の効果が発揮されるだけでなく、複雑な図形についても容易かつ柔軟に対応することが可能となる。
また、対象となる図形の領域を単純な矩形領域に置き換えて、各種制御を行うようにしているため、演算処理等の負担を大幅に抑えることができる。
したがって、プログラムやＣＰＵ等を極めてシンプルな構成にすることができるとともに、信頼性の高いページプリンタを実現することができる。
【００４６】
［第三実施形態］
次に、本発明の画像形成装置の第三実施形態に係るページプリンタについて図１３を参照しながら説明を行う。
本実施形態に係るページプリンタは、メモリ使用量を考慮してページをバンドに区切って（バンド領域生成手段）、一定のバンド領域単位に描画するいわゆるバンド処理を行うことも可能である。
バンド処理においては、バンド領域内での図形の包含関係や重複関係などを考慮する必要があるが、特に問題は発生せず、むしろ、より効率よく画像処理を行うことができる。
【００４７】
例えば、図１３（ａ）のように、３つの矩形があり、矩形６０１が最も上に描画され、次に矩形６０２が描画され、最も下に位置する図形は矩形６０３であるとする。
この場合、ページ全体からみると３つの図形は一部が重なるのみで、包含関係は存在していない。したがって、そのままでは、包含図形削除手段による方法では、重複部分の図形データは削除できない。
しかし、図１３（ｂ）に示すように、バンド領域単位で見ると、ｂａｎｄ（Ｎ）内の矩形６１３は、矩形６１１と矩形６１２によって包含されているため、描画対象とはみなされず、ディスプレイリストから削除するように制御することができる。
【００４８】
なお、バンド処理において、ディスプレイリストはバンド毎に管理されているので図１３（ａ）に示す矩形６０３の全体が削除されることはない。
このように、本実施形態のページプリンタでは、ページへの直接描画処理（ＦＵＬＬ−ＶＲＡＭ）又はバンド処理の如何に関わらず適用することが可能となっている。
【００４９】
以上説明したように、本実施形態のページプリンタによれば、第一実施形態や第二実施形態と同様の効果が発揮されるだけでなく、バンド処理を採用することによって、さらに効率よく描画処理を行うことができる。
また、ページへの直接描画処理（ＦＵＬＬ−ＶＲＡＭ）やバンド処理のいずれの処理手段にも対応できるため、プリンタの性能、出力図形の種類、ユーザが求める品質等に柔軟に対応することが可能である。
【００５０】
以上、本発明の画像形成装置について、好ましい実施形態を示して説明したが、本発明にかかる画像形成装置は、上述した実施形態にのみ限定されるものではなく、本発明の範囲で種々の変更実施が可能であることは言うまでもない。
例えば、本発明の画像形成装置は、ページプリンタのみならず、コピー機やファクシミリ、スキャナ等といった他の画像形成装置、複合装置であってもよい。
【産業上の利用可能性】
【００５１】
本発明は、ページプリンタ等のプリンタや、コピー機、複合機等の画像形成装置やネットワークプリンタ等の画像形成システムに好適に利用することができる。
【図面の簡単な説明】
【００５２】
【図１】本発明の画像形成装置の第一実施形態に係るページプリンタの原理を説明するための説明図である。
【図２】本発明の画像形成装置の第一実施形態に係るページプリンタに用いるディスプレイリストを説明するための説明図である。
【図３】本発明の画像形成装置の第一実施形態に係るページプリンタの基本的な構成を示したブロック図である。
【図４】本発明の画像形成装置の第一実施形態に係るページプリンタの基本的な仕組みを説明するための説明図である。
【図５】本発明の画像形成装置の第二実施形態に係るページプリンタの原理を説明するための説明図である。
【図６】本発明の画像形成装置の第二実施形態に係るページプリンタにおいて用いる最大矩形領域を説明するための説明図である。
【図７】本発明の画像形成装置の第二実施形態に係るページプリンタの動作手順の前段を示したフローチャートである。
【図８】本発明の画像形成装置の第二実施形態に係るページプリンタの動作手順の後段を示したフローチャートである。
【図９】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第一の説明図である。
【図１０】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第二の説明図である。
【図１１】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第三の説明図である。
【図１２】本発明の画像形成装置の第二実施形態に係るページプリンタにおける動作手順を具体的に説明するための第四の説明図である。
【図１３】本発明の画像形成装置の第三実施形態に係るページプリンタにおいてバンド処理を説明するための説明図である。
【図１４】従来の画像形成装置における中間リスト画像の削除原理を示す説明図である。
【符号の説明】
【００５３】
１１ プリントデータ受信記憶部
１２ ＰＤＬ解析部
１３ ディスプレイリスト作成部
１４ ディスプレイリスト情報修正部
１５ ディスプレイリスト削除部
１６ ページラスタライズ部
【特許請求の範囲】
【請求項１】
所定のデータを解析し、図形データとその領域データとを抽出するデータ抽出手段と、
抽出された一以上の前記図形データ及びその領域データを順次格納するディスプレイリストと、
前記ディスプレイリストに先に格納された図形の領域が、後に格納された一の図形の領域に包含される場合に、前記先に格納された図形のデータを前記ディスプレイリストから削除する包含図形削除手段と、
前記ディスプレイリストに格納されている図形データに基づき画像形成データを出力する出力手段と、
前記ディスプレイリストにおいて、先に格納された第一の図形の領域と後に格納された第二の図形の領域との重複領域を検出する重複領域検出手段と、
前記第一の図形の領域を、前記重複領域を削除した領域に変更する領域変更手段と、を備え、
前記包含図形削除手段は、
前記領域変更手段によって変更された前記第一の図形の領域が、後に格納された前記第二の図形以外の図形の領域に包含される場合に、前記第一の図形データを前記ディスプレイリストから削除することを特徴とする画像形成装置。
【請求項２】
前記領域データにもとづき、図形の最大矩形領域を算出する最大矩形領域算出手段と、
前記領域データにもとづき、図形のバウンディングボックス領域を算出するバウンディングボックス領域算出手段と、を備え、
前記重複領域検出手段は、前記ディスプレイリストにおいて、先に格納された第一の図形のバウンディングボックス領域と後に格納された第二の図形の最大矩形領域との重複領域を検出し、
前記領域変更手段は、前記第一の図形のバウンディングボックス領域を、前記重複領域を削除した領域に変更し、
前記包含図形削除手段は、前記領域変更手段によって変更された第一の図形のバウンディングボックス領域が、後に格納された第二の図形以外の図形の最大矩形領域に包含される場合に、前記第一の図形のデータを前記ディスプレイリストから削除することを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記領域データは、少なくとも所定の座標データによって構成されることを特徴とする請求項１又は２に記載の画像形成装置。
【請求項４】
出力単位となるページフレームを一定基準にもとづき分割し、複数のバンド領域を生成するバンド領域生成手段を、備え、
前記データ抽出手段は、所定のデータを解析し、図形データとその領域データとをバンド領域毎に抽出し、
前記ディスプレイリストは、抽出された一以上の前記図形データ及びその領域データをバンド領域毎に順次格納することを特徴とする請求項１乃至３のいずれか一項記載の画像形成装置。
【請求項１】
所定のデータを解析し、図形データとその領域データとを抽出するデータ抽出手段と、
抽出された一以上の前記図形データ及びその領域データを順次格納するディスプレイリストと、
前記ディスプレイリストに先に格納された図形の領域が、後に格納された一の図形の領域に包含される場合に、前記先に格納された図形のデータを前記ディスプレイリストから削除する包含図形削除手段と、
前記ディスプレイリストに格納されている図形データに基づき画像形成データを出力する出力手段と、
前記ディスプレイリストにおいて、先に格納された第一の図形の領域と後に格納された第二の図形の領域との重複領域を検出する重複領域検出手段と、
前記第一の図形の領域を、前記重複領域を削除した領域に変更する領域変更手段と、を備え、
前記包含図形削除手段は、
前記領域変更手段によって変更された前記第一の図形の領域が、後に格納された前記第二の図形以外の図形の領域に包含される場合に、前記第一の図形データを前記ディスプレイリストから削除することを特徴とする画像形成装置。
【請求項２】
前記領域データにもとづき、図形の最大矩形領域を算出する最大矩形領域算出手段と、
前記領域データにもとづき、図形のバウンディングボックス領域を算出するバウンディングボックス領域算出手段と、を備え、
前記重複領域検出手段は、前記ディスプレイリストにおいて、先に格納された第一の図形のバウンディングボックス領域と後に格納された第二の図形の最大矩形領域との重複領域を検出し、
前記領域変更手段は、前記第一の図形のバウンディングボックス領域を、前記重複領域を削除した領域に変更し、
前記包含図形削除手段は、前記領域変更手段によって変更された第一の図形のバウンディングボックス領域が、後に格納された第二の図形以外の図形の最大矩形領域に包含される場合に、前記第一の図形のデータを前記ディスプレイリストから削除することを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記領域データは、少なくとも所定の座標データによって構成されることを特徴とする請求項１又は２に記載の画像形成装置。
【請求項４】
出力単位となるページフレームを一定基準にもとづき分割し、複数のバンド領域を生成するバンド領域生成手段を、備え、
前記データ抽出手段は、所定のデータを解析し、図形データとその領域データとをバンド領域毎に抽出し、
前記ディスプレイリストは、抽出された一以上の前記図形データ及びその領域データをバンド領域毎に順次格納することを特徴とする請求項１乃至３のいずれか一項記載の画像形成装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００８−１０７９７０（Ｐ２００８−１０７９７０Ａ）
【公開日】平成２０年５月８日（２００８．５．８）
【国際特許分類】
【出願番号】特願２００６−２８８６７２（Ｐ２００６−２８８６７２）
【出願日】平成１８年１０月２４日（２００６．１０．２４）
【出願人】（０００００６１５０）京セラミタ株式会社 (13,173)
【Ｆターム（参考）】
【公開日】平成２０年５月８日（２００８．５．８）
【国際特許分類】
【出願日】平成１８年１０月２４日（２００６．１０．２４）
【出願人】（０００００６１５０）京セラミタ株式会社 (13,173)
【Ｆターム（参考）】
[ Back to top ]