JPH1011593A - 画像形成装置 - Google Patents

Abstract

(57)【要約】 【課題】 ページ記述言語を並列実行する際の描画要素
間の重なり検出を高速に行う。 【解決手段】 ジョブシーケンス作成手段１により分割
された画像描画命令を複数の描画手段２ａ，２ｂ・・・
にて並列に実行する一方、重なり判定手段３において描
画要素間の重なり判定をする。まず、領域分割手段４が
ある領域を互いに素な２つの部分に分割し、その境界の
直線の位置を値としたノードからなる木を構成して描画
要素の空間的配置を表現した木とする。木データ管理手
段５がその木の末端のノードに画像を登録する。木デー
タは描画領域が重ならない系列に分類された画像群から
構成される。重なり判定は、そのような木を探索し、新
たに与えられた描画要素が配置される分割領域から重な
り判定の対象となる描画要素が特定されて比較される。
ジョブ管理手段６は木データを基に描画手段２ａ，２ｂ
・・・の部分画素情報を取り出して、画像メモリ７で合
成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は画像形成装置に関
し、特に画像を記述する言語で表現された命令列を複数
の命令処理装置により並列に実行して画像情報を得るよ
うにした画像形成装置に関する。

【０００２】

【従来の技術】多数の利用者が共有しているサーバ型の
印刷装置は、多くのホスト装置からのプリント要求を受
け付けて、ページ記述言語で記述された印刷情報の解
釈、実行を行わなければならない。多くのホスト装置か
ら同時に利用される場合、印刷装置でのページ記述言語
で記述された印刷情報の解釈、実行が逐次的に行われ、
プリント要求をしてから結果を得るまでの待ち時間が長
くなるという問題があった。この状況は印刷解像度の増
大とともに深刻化してきている。

【０００３】そこで上記問題を解決し、画像形成を高速
に実行するために、並列的に描画命令の解釈実行を行う
技術が提案されている。例えば、ＰＣＴ／ＪＰ９１／０
０４５６号に開示された技術では、ネットワーク上に分
散した複数のコンピュータ上で印刷画面の形成処理を分
担するようにしている。ここでは、印刷画面をバンド状
あるいはメッシュ状に分割し、分割された領域の画像形
成を各コンピュータが担当することにより描画操作を複
数の処理として並列実行しているが、形成される画像の
重なりを許していないため、重ならない図形の描画操作
の系列への分割という前処理が必要となる。

【０００４】現在広く用いられているページ記述言語の
多くは、逐次実行を前提として設計されているため、こ
れを並列に実行するには、並列実行可能な部分を特定
し、複数のプロセッサに適切に割当てる処理が必要とな
る。このとき、ある部分画像形成命令の実行結果に上書
きするような画像形成命令がある場合には、それらの間
での重なりの順序を保存しなければ正しい最終画像が得
られない。

【０００５】上述の如き問題に対しては、次のような技
術が提案されている。特開平７−１０４９８７号公報に
開示された技術では、文書印刷プログラムにおける画像
操作手順を解析生成し、並列に描画実行できるか否かの
判定を、それまでに画像形成された画素と次の命令実行
により画像形成される画素との直接比較によって、並列
実行コードを生成するようにしている。

【０００６】

【発明が解決しようとする課題】逐次実行を前提として
設計されているページ記述言語を、高速画像形成のため
に並列に実行させる際には、描画要素の重なりの順序を
保存しなければ正しい最終画像が得られないため、重な
りを検出する処理が必要となる。

【０００７】しかしながら、上記従来の並列描画方式に
おいて、ある部分画像形成が他の画像形成と干渉しない
か、すなわち画像形成の順序によっては他の画像形成に
よる画像がその下にあるべき画像によって上書きされて
しまうか、あるいはその逆に他の画像形成による画像が
その上にあるべき画像を上書きしてしまうかの誤処理を
生じる可能性があるかどうかを判定する必要がある。こ
の重なり関係の判定は、一画面を構成する像内のすべて
の画像要素間について吟味する必要があり、画像要素数
の２乗に比例した処理時間がかかってしまう。そのた
め、画像要素を数百以上の細粒度に分割したときには重
なり判定のための前処理の負荷が非常に大きくなってし
まい、並列処理が元来に意図していた処理高速化の効果
を大きく損なうことになるという問題点があった。

【０００８】本発明はこのような点に鑑みてなされたも
のであり、ページ記述言語の並列実行のための描画要素
の重なり検出を高速に行うようにした画像形成装置を提
供することを目的とする。

【０００９】

【課題を解決するための手段】本発明では上記問題を解
決するために、ページ記述言語で記述された画像描画命
令を実行して画素情報を得るための画像形成装置におい
て、前記画像描画命令を前記画像描画命令の命令単位で
分割して複数の前記画像描画命令の命令ジョブからなる
ジョブシーケンスを作成するジョブシーケンス作成手段
と、前記ジョブシーケンス作成手段から前記命令ジョブ
を個々に受けてそれぞれ前記命令ジョブから画素情報を
展開する複数の描画手段と、前記命令ジョブを受けて命
令ジョブ間の実行時の描画領域の重なりの有無を判定す
る重なり判定手段と、前記重なり判定手段の判定結果に
応じ、描画平面を描画領域の重なりのない互いに素な部
分領域に分割する領域分割手段と、前記ジョブシーケン
スに従って前記領域分割手段の分割結果から互いに素な
部分領域の系列で前記画素情報を木構造に構成するとと
もに、前記重なり判定手段による重なり判定時に前記構
成された木が探索されて判定対象となる部分領域に属す
る命令ジョブが特定される木データ管理手段と、前記ジ
ョブシーケンス作成手段からの命令ジョブを前記複数の
描画手段に分配するとともに、前記木データ管理手段の
木データを参照して前記複数の描画手段で展開された部
分画素情報を取り出すジョブ管理手段と、前記描画平面
に対応する画素情報を保持するだけの領域を有し、前記
ジョブ管理手段によって前記複数の描画手段より取り出
された部分画素情報を書き込んで画像を合成する画像メ
モリとを備えていることを特徴とする画像形成装置が提
供される。

【００１０】このような画像形成装置によれば、描画要
素の登録に際し、描画要素の空間的配置を表現するため
に、領域分割手段がある領域を互いに素な２つの部分に
分割し、木データ管理手段がその境界の直線を値とする
ノードからなる木を構成し、その木の末端のノードに画
像を登録する。重なり判定手段は、そのように構成され
た木を探索して、重なり判定の対象となる描画要素を特
定する。重なり判定の対象となる描画要素の探索には、
新たに与えられた描画要素が互いに素な２つの部分に分
割された直線のどちら側にあるかを判定していって、与
えられた描画要素が配置される部分領域に含まれる描画
要素を重なり判定の対象とする。重なり判定により、木
データは更新される。その木データによる重なり依存関
係に従ってジョブ管理手段が描画手段から展開された部
分画素情報を読み出し、画像メモリにて合成することに
より画像を形成する。

【００１１】

【発明の実施の形態】以下、本発明の実施の形態を図面
に基づいて説明する。図１は本発明の原理構成を示す図
である。本発明による画像形成装置は、画像描画命令を
受けて複数の画像描画命令の命令ジョブからなるジョブ
シーケンスを作成するジョブシーケンス作成手段１と、
個々の命令ジョブを実行する複数の描画手段２ａ，２
ｂ，２ｃ，・・・と、命令ジョブ間の実行時の描画領域
の重なり関係を判定する重なり判定手段３と、この重な
り判定手段３の判定結果に応じて描画平面を描画領域の
重なりのない互いに素な部分領域に分割する領域分割手
段４と、この領域分割手段４の分割結果から画素情報を
木構造にする木データ管理手段５と、命令ジョブの複数
の描画手段２ａ，２ｂ，２ｃ，・・・への割り当てや複
数の描画手段２ａ，２ｂ，２ｃ，・・・で展開された部
分画素情報の取り出しを行うジョブ管理手段６と、木デ
ータが表す重なり関係に従って取り出された部分画素情
報を書き込んで画像を合成する画像メモリ７とを備えて
いる。

【００１２】ジョブシーケンス作成手段１は、画像描画
命令をその命令単位で分割して命令ジョブの並びからな
るジョブシーケンスを作成する。ジョブ管理手段６は、
分割された命令ジョブを複数の描画手段２ａ，２ｂ，２
ｃ，・・・に適当に割り当て、複数の描画手段２ａ，２
ｂ，２ｃ，・・・を並列に駆動してそれぞれ描画命令を
実行させる。同時に、重なり判定手段３は、分割された
命令ジョブが実行時の描画領域と一つ手前の命令ジョブ
が実行時の描画領域との重なりの有無を判定する。この
とき、重なり判定手段３は、木データ管理手段５によっ
て構成された木を探索して判定対象となる部分領域に属
する命令ジョブを特定する。領域分割手段４は、重なり
判定手段３の判定結果に応じて、木データ管理手段５に
おける木データを更新するときに、描画平面を描画領域
の重なりのない互いに素な部分領域に分割して描画平面
の中で重なりのない領域との論理的な境界を設定してい
く。ジョブ管理手段６は、木データ管理手段５の木デー
タを参照することにより描画領域の重なり関係を考慮し
ながら複数の描画手段２ａ，２ｂ，２ｃ，・・・で展開
された部分画素情報を読み出し、これらを画像メモリ７
に書き込んで画像を合成する。

【００１３】したがって、描画要素の重なり検出に際
し、描画要素の空間的配置を表現するために、木データ
管理手段５では、領域分割手段４によってある領域を互
いに素な２つの部分に分割した直線を値とするノードか
らなる木を構成し、その木の末端のノードに形成画像を
登録するようにしている。重なり判定手段３は、そのよ
うに構成された木を探索するので、重なり判定の対象と
なる描画要素の特定が高速に行われれる。木データ管理
手段５での木の探索時には、重なり判定の対象となる描
画要素が互いに素な２つの部分に分割された直線のどち
ら側にあるかを判定し、重なり判定の対象となる描画要
素がないと判定された領域にある描画要素については重
なり判定の対象としないので、描画要素間の重なり判定
の数を少なくすることができ、全体の画像形成処理を高
速にすることができる。

【００１４】次に、本発明の第１の実施の形態を、ネッ
トワークにより粗結合された印刷システムに適用した場
合を例にして説明する。図２は本発明の画像形成装置を
適用した印刷システムの構成を示すブロック図である。
図示の画像形成装置１０は、ローカルエリアネットワー
ク２０を介してクライアント計算機３１，３２，３３，
・・・が結合され、また、処理結果を出力するためのプ
リントエンジン４０が結合されている。画像形成装置１
０は、ローカルエリアネットワーク２０に接続された命
令解析装置１１と、複数の図形描画部１２ａ，１２ｂ，
１２ｃ，１２ｄ，１２ｅ，・・・と、図形合成部１３
と、画像メモリ１４と、プリンタインタフェース１５と
が共有バス１６を介して結合されている。命令解析装置
１１は、字句解析部１１ａと、命令実行部１１ｂと、記
述分割部１１ｃと、重なり判定部１１ｄと、木データ管
理部１１ｅとから構成されている。

【００１５】なお、命令解析装置１１の字句解析部１１
ａ、命令実行部１１ｂおよび記述分割部１１ｃは図１に
示すジョブシーケンス作成手段１に対応し、命令解析装
置１１の重なり判定部１１ｄは重なり判定手段３に対応
し、命令解析装置１１の木データ管理部１１ｅは木デー
タ管理手段５に対応し、重なり判定部１１ｄおよび木デ
ータ管理部１１ｅの機能の一部が領域分割手段４に対応
し、複数の図形描画部１２ａ，１２ｂ，１２ｃ，１２
ｄ，１２ｅ，・・・は描画手段２ａ，２ｂ，２ｃ，・・
・に対応し、図形合成部１３はジョブ管理手段６に対応
し、そして、画像メモリ１４は画像メモリ７に対応す
る。

【００１６】本発明による画像形成装置１０において、
クライアント計算機３１，３２，３３，・・・で作成さ
れた印刷ジョブはローカルエリアネットワーク２０を介
して命令解析装置１１に送られる。命令解析装置１１で
は、受け取った印刷ジョブの内容を字句解析部１１ａに
よって解析する。命令実行部１１ｂでは、印刷ジョブを
内部形式に順次変換する。続いて、字句解析部１１ａに
よる解析の結果、部分図形の描画命令が検知されると、
記述分割部１１ｃはその部分図形の描画命令を単一の部
分図形あるいは複数の部分図形の系列に分割する。記述
分割部１１ｃの出力は分割された結果の部分図形の記述
の並びであり、これは並列に動作可能であってローカル
バッファを有する図形描画部１２ａ，１２ｂ，１２ｃ，
１２ｄ，１２ｅ，・・・のいずれかに送られ、その図形
描画部１２ａ，１２ｂ，１２ｃ，１２ｄ，１２ｅ，・・
・において部分図形の描画が行われる。

【００１７】また、記述分割部１１ｃの出力は同時に重
なり判定部１１ｄに送られ、それまでに生成された部分
図形との重なりがあるかどうかの判定が行われる。重な
り判定部１１ｄの出力は木データ管理部１１ｅに送ら
れ、ここで木構造を用いた表現で管理される。図形合成
部１３は木データ管理部１１ｅの保持する木データによ
って表現された部分図形の間の重なり関係の情報を参照
しながら、図形描画部１２ａ，１２ｂ，１２ｃ，１２
ｄ，１２ｅ，・・・で描画されてそれぞれのローカルバ
ッファに保持されている図形データを適宜読み出し、１
ページ分の描画平面に対応する画像メモリ１４に送る。
画像メモリ１４では、送られた図形データを合成して、
１ページ分の画像を生成する。こうして生成された画像
メモリ１４の内容はプリンタインタフェース１５を介し
てプリントエンジン４０に送られ、印刷出力される。

【００１８】次に、画像形成装置１０に入力される印刷
ジョブの具体的な例を参照して動作の詳細な説明をす
る。図３はクライアントが作成した画面の一例を示す図
である。図示の作図例によれば、任意のクライアント計
算機において、任意の画像編集ソフトウェアを使用し
て、最初に四角の図形Ｆ１が作成され、その上に重ねて
黒丸の図形Ｆ２が作成され、図形Ｆ２を完全に包含する
形で白抜きの大きな円の図形Ｆ３が作成される。次に、
図形Ｆ１を一部包含する形で三角形の図形Ｆ４が作成さ
れ、さらに、黒丸の図形Ｆ５と、これを包含する白抜き
の円の図形Ｆ６が作成されている。

【００１９】画像編集ソフトウェアを利用して作成され
た図形Ｆ１〜Ｆ６の情報は、クライアント計算機にイン
ストールされた、たとえば、プリンタドライバが生成す
るＰＤＬプログラムとして画像形成装置１０の命令解析
装置１１に送信される。このような図形Ｆ１〜Ｆ６を描
画する描画命令列は以下のように記述される。

【００２０】図４は命令解析装置における解析の例を示
す図である。図４の（Ａ）は画像形成装置１０の命令解
析装置１１に入力された描画命令列のリストを示してい
る。このリストによれば、図形Ｆ１〜Ｆ６に対応する図
形描画命令５１〜５６が図形Ｆ１，Ｆ２，Ｆ３，Ｆ４，
Ｆ５およびＦ６の順に記述されている。

【００２１】命令解析装置１１の字句解析部１１ａで
は、入力された描画命令列を１文字ずつ読み込んで解析
し、命令実行部１１ｂにおいて、解析された図形描画命
令の内容、たとえば図形の種類、座標値、大きさなどの
パラメータを内部形式に変換する。続いて、記述分割部
１１ｃにおいては、描画命令列から実際に描画する図形
の種類を表す命令を検出する。具体的には、図４の
（Ｂ）のリスト中に下線で示したように、塗りつぶしの
四角の図形描画命令である「ｒｅｃｔｆｉｌｌ」、円弧
の塗りつぶしの図形描画命令である「ｆｉｌｌ」、およ
び輪郭に沿った線の図形描画命令である「ｓｔｒｏｋ
ｅ」を検出する。これらの輪郭描画命令または塗りつぶ
し命令が検出されると、その時点で、記述分割部１１ｃ
はそれまでに解析された命令列が一つの図形を定義して
いると判断して、ここで、ジョブとして分割する。すな
わち、図４の（Ｃ）に示したように、図形描画命令５１
〜５６に対応した６つの部分図形記述に分割される。

【００２２】このようにして分割された部分図形記述
は、図形描画部１２ａ，１２ｂ，１２ｃ，１２ｄ，１２
ｅ，・・・の内、それぞれ別の図形描画部に送られ、そ
こで図形描画命令が実行されて、画素情報に展開され
る。図形描画部の割り当ては、図形合成部１３によって
現在あいている図形描画部に対して順次行われる。この
分割された部分図形記述は図形描画部への送信と同時
に、重なり判定部１１ｄに送られる。

【００２３】以下では、２つの図形の重なりをそれらの
外接矩形を用いて判定するものとする。ただし本発明に
おいては、この判定を外接矩形を用いた方法に限定する
ものではなく、例えば凸包のように対象図形を包含する
ような多角形や、対象図形を包含するような任意の図形
を用いてもよい。また、図形の境界だけを用いても、内
部を含む領域を用いて判定を行ってもよい。

【００２４】図形の外接矩形は、命令実行部１１ｂにお
いて、内部表現生成の際にｘ座標値およびｙ座標値の最
大値および最小値を保存するなどの方法により、容易に
求めることができる。

【００２５】まず、２つの外接矩形の重なりを判定する
方法について説明する。図５は外接矩形を用いた重なり
判定手続きの原理を示すフローチャートである。ここ
で、２つの図形の外接矩形を数値の４つ組で表すものと
し、それぞれの数値はその矩形の左上の点と右下の点と
のｘ座標およびｙ座標の値を表すものとする。

【００２６】したがって、最初に、２つの外接矩形の左
上の点のｘ座標およびｙ座標の最大値を変数Ｌｘ，Ｌｙ
および右下の点のｘ座標およびｙ座標の最小値を変数Ｈ
ｘ，Ｈｙにそれぞれセットする（ステップＳ１）。続い
て、２つの外接矩形のｘ座標およびｙ座標に関する変数
の比較を行う（ステップＳ２）。すなわち、Ｌｘ＜Ｈｘ
であり、かつＬｙ＜Ｈｙであるか否かを判定し、両方を
満足するならば、重なりありと判定して終了する。ま
た、両方の比較を満足しなければ、重なりなしと判定し
て終了する。

【００２７】この重なりの有無の判定は、２つの外接矩
形が与えられた場合に、以下の理由によって可能にな
る。矩形領域のある軸への正射影を考えると、これは幅
をもった値の範囲を形成する。２つの範囲が重なる場合
は、重なり領域の端は、２つの範囲の左側境界のうち右
側にあるものと右側境界のうち左側にあるものとであ
り、これらが左から右へこの順に現れる。２つの範囲が
重ならない場合には、これらの出現順序が逆になる。図
５の重なり判定手続きはこのような性質を利用してい
る。

【００２８】上述の重なり判定手続きを利用して、木デ
ータ管理部１１ｅにおいて既に生成されている木データ
と新たに入力された図形の外接矩形との重なり判定を行
う手続きを以下に説明する。

【００２９】図６は重なり判定を行う手続きのフローチ
ャートを示す図である。この重なり判定手続きでは、ま
ず、入力図形の外接矩形を生成し（ステップＳ１１）、
既に生成された図形の系列を表現する木を探索し（ステ
ップＳ１２）、重なり判定を行う（ステップＳ１３）。
この重なり判定は、図５に示した手続きを用いて行う。
木の探索手続きについては後述する。

【００３０】ステップＳ１３での重なり判定において、
重なりが検出されれば、新しい木を生成してその図形を
登録し（ステップＳ１４）、終了する。重なり判定にお
いて、重なりが検出されなかった場合には、現在の木に
ノードを生成してその図形を登録し、次の探索に備える
（ステップＳ１５）。

【００３１】図形の木への登録は次のようにして行われ
る。まず、その図形の属する領域を特定する。これは重
なり検出のための探索で既に行われている。次いで、そ
の領域を今回与えられた図形と既に木に登録されている
図形とが属する領域に分割する直線を決定し、この直線
の座標値を値として持つようなノードを生成する。そし
て、このノードの枝に分割された部分領域をそれぞれ割
り当てる。このようにして生成したノードを木に加える
ことで、新たな分割領域が定義され、そこに図形が追加
登録される。

【００３２】領域を分割する直線のそれぞれは、水平線
もしくは垂直線のいずれかである。水平線および垂直線
は２つの図形の間であれば、どこでもよいが、本実施の
形態では、配置可能な位置のうちでそれぞれ最も上およ
び最も左に配置されるものとしている。

【００３３】このような配置手続きを用いることによっ
て、重ならない図形の系列はその空間的配置を反映した
木構造によって表現される。この木に登録された図形と
新たに与えられた図形との重なり判定を行うには、その
図形が配置される領域を特定し、そこに含まれる図形と
の間でのみ重なり判定を行えばよい。このため、木に登
録されたすべての図形を調べる必要がなく、重なり判定
処理の負荷が大幅に軽減される。

【００３４】次に、領域を特定するために木を探索する
手続きについて説明する。図７は木の探索手続きを示す
フローチャートである。図７の手続きでは、まず木のノ
ードが持つ直線と与えられた図形の外接矩形との配置関
係を調べ、境界線は垂直かどうかを判定する（ステップ
Ｓ２１）。ここで、領域を分割する直線が垂直線なら
ば、与えられた図形の外接矩形の左上の点のｘ座標をＢ
ｌに、右下の点のｘ座標をＢｕにセットする（ステップ
Ｓ２２）。もし、ステップＳ２１の判定において、領域
を分割する直線が水平線ならば、与えられた図形の外接
矩形の左上の点のｙ座標をＢｌに、右下の点のｙ座標を
Ｂｕにセットする（ステップＳ２３）。次に、先にセッ
トされたＢｌおよびＢｕの値と境界線の値とを比較す
る。まず、境界線のｘまたはｙ座標値がＢｌおよびＢｕ
のｘまたはｙ座標値の間にあるかどうかを判定し（ステ
ップＳ２４）、Ｂｌ＜境界線＜Ｂｕならば、与えられた
図形の外接矩形はノードが持つ直線と交わっていると判
定し、ノードから出る両方の枝を再帰的に探索する（ス
テップＳ２５）。また、境界線とＢｕとの位置関係が判
定され（ステップＳ２６）、境界線≧Ｂｕであれば、与
えられた図形の外接矩形はノードが持つ垂直線の左側ま
たは水平線の上側にあると判定され、それに対応する枝
を再帰的に探索する（ステップＳ２７）。最後に、境界
線とＢｌとの位置関係が判定され（ステップＳ２８）、
境界線≦Ｂｌであれば、与えられた図形の外接矩形はノ
ードが持つ垂直線の右側または水平線の下側にあると判
定され、それに対応する枝を再帰的に探索する（ステッ
プＳ２９）。このようにして、与えられた図形の外接矩
形がノードが持つ直線と交わっている場合には、ノード
から出る両方の枝を再帰的に探索し、与えられた図形の
外接矩形がノードが持つ直線のいずれかの側にあれば、
それに対応する枝を再帰的に探索する。いずれの場合も
末端のノード、すなわち部分図形に到達すると探索は終
了する。

【００３５】以上の結果、命令シーケンスは重ならない
図形の系列に分割される。同時に、それぞれの部分図形
は、スケジューリングを行うことなく、図形描画部１２
ａ，１２ｂ，１２ｃ，１２ｄ，１２ｅ，・・・に送られ
て描画され、ローカルバッファに保持されている。個々
の描画結果は、図形合成部１３によってローカルバッフ
ァより読み出され、画像メモリ１４の内容と合成し、す
なわち画像メモリ１４の内容を上書きする。

【００３６】このとき、重なりの順序を正しく再現する
には、次のようにすればよい。すなわち、ある部分図形
の描画結果を画像メモリ１４の内容に合成する際には、
その図形が属する木データよりも以前に生成された木デ
ータに属する図形で合成されていないものが残っていな
いことを調べればよい。ある図形と同じ木データに属す
る別の図形は残っていても構わない。これは、一つの木
データには重ならない図形の系列が登録されているた
め、これらの図形の間で合成の順序を変更しても重なり
関係には影響がないためである。

【００３７】以上の手続きを図３の描画例に適用した場
合の重なり判定部１１ｄおよび木データ管理部１１ｅの
動作について説明する。ここでは、分割された図形記述
は同時に図形描画部１２ａ，１２ｂ，１２ｃ，１２ｄ，
１２ｅ，・・・のいずれかに送られ描画されており、ま
た、描画された図形は、図形合成部１３によって適宜読
み出され、画像メモリ１４に合成されているとする。

【００３８】図８は重なり判定対象の図形の位置関係を
示す図、図９は重なり判定後の木構造を示す図である。
重なり判定部１１ｄでは、入力された図形Ｆ１に関する
記述５１（図４）から外接矩形ＢＢ１（２５０，２０
０，３７５，２２５）が得られ、図形Ｆ２に関する記述
５２から外接矩形ＢＢ２（３２５，１８７．５，３５
０，２１２．５）が得られる。図５の重なり判定手続き
を適用することにより、外接矩形ＢＢ１と外接矩形ＢＢ
２とは重なりありと判定される。

【００３９】図形Ｆ１および図形Ｆ２は、重なりが検出
されたので、それぞれ異なる木に登録される。すなわ
ち、図形Ｆ１は木Ｔ１の下に登録され、図形Ｆ２は木Ｔ
２の下に登録され、これらは木データ管理部１１ｅで管
理される。また、図形Ｆ１と図形Ｆ２に対応する記述は
それぞれたとえば図形描画部１２ａおよび１２ｂに送ら
れ、描画される。

【００４０】図１０は重なり判定対象の図形の位置関係
を示す図、図１１は重なり判定後の木構造を示す図であ
る。次に、図形Ｆ２および図形Ｆ３に対する重なり判定
が行われる。図形Ｆ３の外接矩形は図形Ｆ３に関する記
述５３から外接矩形ＢＢ３（３００，１００，４５０，
２５０）が得られる。外接矩形ＢＢ２および外接矩形Ｂ
Ｂ３から図形Ｆ２および図形Ｆ３は重なりありと判定さ
れる。重なりが検出されたので、図形Ｆ３は、上の場合
と同様に、図形Ｆ２と異なる木Ｔ３に登録される。ま
た、図形Ｆ３に対応する記述５３はたとえば図形描画部
１２ｃが割り当てられて、ここで描画される。

【００４１】図１２は重なり判定対象の図形の位置関係
を示す図、図１３は重なり判定後の木構造を示す図であ
る。次に、図形Ｆ３および図形Ｆ４に対する重なり判定
が行われる。図形Ｆ４の外接矩形は図形Ｆ４に関する記
述５４から外接矩形ＢＢ４（１５０，１５０，２７３，
２５０）が得られる。外接矩形ＢＢ３および外接矩形Ｂ
Ｂ４から図形Ｆ３および図形Ｆ４の外接矩形が重ならな
いことが検出される。したがって、この図形Ｆ４は図形
Ｆ３を含む木Ｔ３に登録されることになる。この木Ｔ３
への登録に際しては、それぞれの矩形を含む互いに素な
２つの領域へ空間を分割する直線６１（図１２）を値と
して持つノードＮ１が木Ｔ３の下に生成される。このノ
ードＮ１からの枝は、直線６１によって分割された領域
に対応し、枝の先にそれぞれの図形が登録される。この
場合は、直線６１のｘ＝２７５を値として持つノードＮ
１が生成され、このノードＮ１は領域ｘ＜２７５および
領域ｘ＞２７５に対応する枝を持ち、それぞれの枝の先
に図形Ｆ４および図形Ｆ３が登録され、図１３に示すよ
うな木が構成される。また、図形Ｆ４に対応する記述５
４はたとえば図形描画部１２ｄに送られ描画される。

【００４２】図１４は重なり判定対象の図形の位置関係
を示す図、図１５は重なり判定後の木構造を示す図であ
る。次に、図形Ｆ５に対する重なり判定が、上述の図形
Ｆ３および図形Ｆ４から構成される木Ｔ３を対象に行わ
れる。図形Ｆ５に対する外接矩形ＢＢ５（１３７．５，
１１２．５，１６２．５，１３７．５）はｘ＜２７５の
領域にあるので、対応する枝をたどりｘ＝２７５の左側
の図形Ｆ４に到達し、これが図形Ｆ５に対する重なり判
定対象の図形となる。図形Ｆ５および図形Ｆ４に対する
重なり判定の結果、これらの図形Ｆ４およびＦ５は重な
らないことが検出される。これによって、図形Ｆ５はこ
の木Ｔ３に登録されているすべての図形と重ならないこ
とが判明し、直線６２のｙ＝１３７．５を値とするノー
ドＮ２が生成され、その下に図形Ｆ４および図形Ｆ５が
登録される。登録後は、木Ｔ３が図１５に示すように変
化する。また、図形Ｆ５に対応する記述５５はたとえば
図形描画部１２ｅに送られ、図形Ｆ５が描画される。

【００４３】図１６は重なり判定対象の図形の位置関係
を示す図、図１７は重なり判定後の木構造を示す図であ
る。次に、図形Ｆ６に対する重なり判定が行なわれる。
まず、図形Ｆ６に対する外接矩形ＢＢ６（１００，１０
０，２００，２００）が求められる。木Ｔ３の探索にお
いて、ｘ＜２７５の枝をたどると、ｙ＝１３７．５の直
線６２と外接矩形ＢＢ６とが交わることが分かる。この
とき、このノードＮ２の両側の枝をたどり重なり判定を
行うのであるが、たとえばｙ＜１３７．５をたどり、図
形Ｆ５との重なり判定を行うと重なりが検出されるた
め、これ以上の木の探索は不要となる。この結果、図形
Ｆ６は木Ｔ３と異なる新たな木Ｔ４に登録される。ま
た、図形Ｆ６に対応する記述５６は、たとえば図形描画
部１２ａで既に図形Ｆ１の描画が終了して図形合成部１
３により画像メモリ１４に上書きされている場合には、
図形描画部１２ａに送られ、ここで図形Ｆ６が描画され
る。

【００４４】以上の結果、図３の図形群は、図形Ｆ１を
含む木Ｔ１、図形Ｆ２を含む木Ｔ２、図形Ｆ３、図形Ｆ
４および図形Ｆ５を含む木Ｔ３、図形Ｆ６を含む木Ｔ４
の４つの木に分解される。これらの図形を画像メモリに
合成する際には、次のような順序で行えばよい。まず、
木Ｔ１に登録された図形Ｆ１の画像メモリ１４への合成
の完了を待って、木Ｔ２に登録された図形Ｆ２の画像メ
モリ１４への合成を行う。次いで、木Ｔ２に登録された
図形Ｆ２の画像メモリ１４への合成の完了を待って、木
Ｔ３に登録された図形Ｆ３、図形Ｆ４および図形Ｆ５の
画像メモリ１４への合成を行う。このとき、同一の木に
登録された図形は互いに重なり関係がないので、図形Ｆ
３、図形Ｆ４および図形Ｆ５の合成の順序は任意でよ
く、図形描画部による描画が完了した順に合成すればよ
い。次に、木Ｔ３に登録された図形Ｆ３、図形Ｆ４およ
び図形Ｆ５のすべての図形の画像メモリ１４への合成の
完了を待って、木Ｔ４に登録された図形Ｆ６の画像メモ
リ１４への合成を行う。以上の合成の結果、重なりの順
序を正しく反映した最終画像が画像メモリ１４上に作成
されることになる。

【００４５】プリンタインタフェース１５は、こうして
得られた画像メモリ１４上の最終画像をプリントエンジ
ン４０に送り、プリントエンジン４０にて最終画像の印
字が行われ、図３に示した図形の印字が完了する。

【００４６】次に、本発明の第２の実施の形態を、ネッ
トワークにより粗結合された印刷システムに適用した場
合を例にして説明する。図１８は本発明の画像形成装置
を適用した印刷システムの別の構成を示すブロック図で
ある。図示の画像形成装置１０は、ローカルエリアネッ
トワーク２０を介してクライアント計算機３１，３２，
３３，・・・が結合され、また、処理結果を出力するた
めのプリントエンジン４０が結合されている。画像形成
装置１０は、ローカルエリアネットワーク２０に接続さ
れた命令解析装置１１と、複数の図形描画部１２ａ，１
２ｂ，１２ｃ，１２ｄ，１２ｅ，・・・と、図形合成部
１３と、画像メモリ１４と、プリンタインタフェース１
５とが共有バス１６を介して結合されている。命令解析
装置１１は、字句解析部１１ａと、命令実行部１１ｂ
と、記述分割部１１ｃと、重なり判定部１１ｄと、木デ
ータ管理部１１ｅと、テンプレートデータ記憶部１１ｆ
とから構成されている。すなわち、この第２の実施の形
態では、図２に示した構成にテンプレートデータ記憶部
１１ｆが追加されている。

【００４７】本発明による画像形成装置１０において、
クライアント計算機３１，３２，３３，・・・で作成さ
れた印刷ジョブはローカルエリアネットワーク２０を介
して命令解析装置１１に送られる。命令解析装置１１で
は、受け取った印刷ジョブの内容を字句解析部１１ａに
よって解析する。命令実行部１１ｂでは、印刷ジョブを
内部形式に順次変換する。続いて、字句解析部１１ａに
よる解析の結果、部分図形の描画命令が検知されると、
記述分割部１１ｃはその部分図形の描画命令を単一の部
分図形あるいは複数の部分図形の系列に分割する。記述
分割部１１ｃの出力は分割された結果の部分図形の記述
の並びであり、これは並列に動作可能であってローカル
バッファを有する図形描画部１２ａ，１２ｂ，１２ｃ，
１２ｄ，１２ｅ，・・・のいずれかに送られ、その図形
描画部１２ａ，１２ｂ，１２ｃ，１２ｄ，１２ｅ，・・
・において部分図形の描画が行われる。

【００４８】また、記述分割部１１ｃの出力は同時に重
なり判定部１１ｄに送られ、それまでに生成された部分
図形との重なりがあるかどうかの判定が行われる。重な
り判定部１１ｄの出力は木データ管理部１１ｅに送ら
れ、ここで木構造を用いた表現で管理される。このと
き、木データ管理部１１ｅはテンプレートデータ記憶部
１１ｆにあらかじめ記憶されている木データを、上述の
木構造を用いた表現のテンプレートとして用いる。この
テンプレートはあらかじめ定められた領域分割を表して
おり、そのノードにはページの部分領域が対応する。し
たがって、このノード以下には定められた部分領域に属
する図形記述が登録される。

【００４９】図形合成部１３は木データ管理部１１ｅの
保持する木データによって表現された部分図形の間の重
なり関係の情報を参照しながら、図形描画部１２ａ，１
２ｂ，１２ｃ，１２ｄ，１２ｅ，・・・で描画され、ロ
ーカルバッファに保持されている図形データを適宜読み
出し、１ページ分の描画平面に対応する画像メモリ１４
に送る。画像メモリ１４では、送られた図形データを合
成して、１ページ分の画像を生成する。こうして生成さ
れた画像メモリ１４の内容はプリンタインタフェース１
５を介してプリントエンジン４０に送られ印刷される。

【００５０】ここで、字句解析部１１ａ、命令実行部１
１ｂ、記述分割部１１ｃおよび重なり判定部１１ｄの動
作については、図２に示した第１の実施の形態と同様で
あるため、説明を省略する。字句解析部１１ａ、命令実
行部１１ｂ、記述分割部１１ｃおよび重なり判定部１１
ｄの動作の結果、命令シーケンスは重ならない図形の系
列に分割され、木データ管理部１１ｅの保持する木デー
タに登録される。この登録される木データとしてはテン
プレートデータ記憶部１１ｆに記憶されているテンプレ
ートが使用される。このテンプレートについて以下に説
明する。

【００５１】図１９はテンプレートを用いた木データの
構成方法を示す説明図である。図１９において、画像メ
モリ１４が部分図形を合成する描画平面７１が示されて
いる。この描画平面７１は図示の例では４つの部分領域
７１ａ，７１ｂ，７１ｃ，７１ｄに分割されている。こ
れらの領域分割に対応する空間配置の木構造があらかじ
めテンプレート８１として生成され、テンプレートデー
タ記憶部１１ｆに保持されている。したがって、木デー
タ管理部１１ｅが図形を登録するときには、あらかじめ
定められた領域分割を表すテンプレート８１をテンプレ
ートデータ記憶部１１ｆから読み出し、その図形が含ま
れる部分領域に対応する木の枝に登録することになる。
また、ある特定の部分領域に属する図形群を取り出す操
作は、その部分領域に対応する木の探索によって容易に
実現することができる。

【００５２】このとき、テンプレート８１が表す分割さ
れた部分領域を水平な帯状に定義し、画像メモリ１４を
この帯の幅に相当する容量に限定すれば、インクジェッ
トプリンタなどに好適なバンドバッファを用いた画像形
成装置を容易に構成することが可能となり、バンド内で
は並列に描画が行われるため高速な処理を実現すること
ができる。

【００５３】また、あらかじめ定められた領域分割を表
すテンプレート８１を利用した場合の別の実施の形態と
して、図１９に示したように、分割されたページの部分
領域７１ａ，７１ｂ，７１ｃ，７１ｄのそれぞれに属す
る図形群を、たとえば図示のようにメッシュの形態で結
合された図形描画処理用の複数の並列プロセッサ９１
ａ，９１ｂ，９１ｃ，９１ｄに割り当てるようにするこ
とができる。これは、複数のプロセッサがメッシュやト
ーラスなどの形態で結合された超並列アーキテクチャ計
算機上で画像形成装置を構成する際に、プロセッサの結
合形態を反映してページを分割し処理させる場合に特に
好適であり、高速な処理を実現することが可能となる。

【００５４】

【発明の効果】以上説明したように本発明では、画像描
画命令を分割するジョブシーケンス作成手段と、重なり
判定手段と、領域分割手段と、木データ管理手段とを有
する命令解析装置を備えたことにより、重ならない図形
に対しては、描画が終了した順に図形の合成を行うよう
にすることによって、負荷の高い図形描画を待つことな
く合成が可能となり、全体の高速な動作が可能となる。
また、描画順序に依存性のある図形系列を容易に特定す
ることができるため、依存性解析に基づくスケジューリ
ングなども可能となり、描画システムの動作効率の向上
に寄与する。

【００５５】さらに、重なり判定の対象となる図形を図
形群の絞り込みにより特定することで、互いに重なりの
ある描画要素の検出を効率的に遂行し、重なり判定後直
ちに合成処理に移ることができるため、複雑なスケジュ
ーリングを行うことなく並列描画処理を実現することが
可能となる。

【図面の簡単な説明】

【図１】本発明の原理構成を示す図である。

【図２】本発明の画像形成装置を適用した印刷システム
の構成を示すブロック図である。

【図３】クライアントが作成した画面の一例を示す図で
ある。

【図４】命令解析装置における解析の例を示す図であ
る。

【図５】外接矩形を用いた重なり判定手続きの原理を示
すフローチャートである。

【図６】重なり判定を行う手続きのフローチャートを示
す図である。

【図７】木の探索手続きを示すフローチャートである。

【図８】重なり判定対象の図形の位置関係を示す図（そ
の１）である。

【図９】重なり判定後の木構造を示す図（その１）であ
る。

【図１０】重なり判定対象の図形の位置関係を示す図
（その２）である。

【図１１】重なり判定後の木構造を示す図（その２）で
ある。

【図１２】重なり判定対象の図形の位置関係を示す図
（その３）である。

【図１３】重なり判定後の木構造を示す図（その３）で
ある。

【図１４】重なり判定対象の図形の位置関係を示す図
（その４）である。

【図１５】重なり判定後の木構造を示す図（その４）で
ある。

【図１６】重なり判定対象の図形の位置関係を示す図
（その５）である。

【図１７】重なり判定後の木構造を示す図（その５）で
ある。

【図１８】本発明の画像形成装置を適用した印刷システ
ムの別の構成を示すブロック図である。

【図１９】テンプレートを用いた木データの構成方法を
示す説明図である。

【符号の説明】

１ ジョブシーケンス作成手段 ２ａ，２ｂ，２ｃ 描画手段 ３ 重なり判定手段 ４ 領域分割手段 ５ 木データ管理手段 ６ ジョブ管理手段 ７ 画像メモリ １０ 画像形成装置 １１ 命令解析装置 １１ａ 字句解析部 １１ｂ 命令実行部 １１ｃ 記述分割部 １１ｄ 重なり判定部 １１ｅ 木データ管理部 １１ｆ テンプレートデータ記憶部 １２ａ，１２ｂ，１２ｃ，１２ｄ，１２ｅ 図形描画部 １３ 図形合成部 １４ 画像メモリ １５ プリンタインタフェース １６ 共有バス ２０ ローカルエリアネットワーク ３１，３２，３３ クライアント計算機 ４０ プリントエンジン

Claims (6)

【特許請求の範囲】
1. 【請求項１】 ページ記述言語で記述された画像描画命
   令を実行して画素情報を得るための画像形成装置におい
   て、 前記画像描画命令を前記画像描画命令の命令単位で分割
   して複数の前記画像描画命令の命令ジョブからなるジョ
   ブシーケンスを作成するジョブシーケンス作成手段と、 前記ジョブシーケンス作成手段から前記命令ジョブを個
   々に受けてそれぞれ前記命令ジョブから画素情報を展開
   する複数の描画手段と、 前記命令ジョブを受けて命令ジョブ間の実行時の描画領
   域の重なりの有無を判定する重なり判定手段と、 前記重なり判定手段の判定結果に応じ、描画平面を描画
   領域の重なりのない互いに素な部分領域に分割する領域
   分割手段と、 前記ジョブシーケンスに従って前記領域分割手段の分割
   結果から互いに素な部分領域の系列で前記画素情報を木
   構造に構成するとともに、前記重なり判定手段による重
   なり判定時には前記構成された木が探索されて判定対象
   となる部分領域に属する命令ジョブが特定される木デー
   タ管理手段と、 前記ジョブシーケンス作成手段からの命令ジョブを前記
   複数の描画手段に分配するとともに、前記木データ管理
   手段の木データを参照して前記複数の描画手段で展開さ
   れた部分画素情報を取り出すジョブ管理手段と、 前記描画平面に対応する画素情報を保持するだけの領域
   を有し、前記ジョブ管理手段によって前記複数の描画手
   段より取り出された部分画素情報を書き込んで画像を合
   成する画像メモリと、 を備えていることを特徴とする画像形成装置。
2. 【請求項２】 前記領域分割手段は、前記描画平面を水
   平線または垂直線のいずれかにより互いに素な部分領域
   に分割することを特徴とする請求項１に記載の画像形成
   装置。
3. 【請求項３】 前記領域分割手段は、前記描画平面を水
   平線によって複数の帯状の領域に分割することを特徴と
   する請求項１に記載の画像形成装置。
4. 【請求項４】 前記描画平面を複数の固定された部分領
   域群に分割して木データを表現した木データテンプレー
   トを記憶し、前記木データ管理手段による前記木データ
   の構成の際には前記木データテンプレートの下に木デー
   タを追加していくようにした木データテンプレート記憶
   手段をさらに備えていることを特徴とする請求項１に記
   載の画像形成装置。
5. 【請求項５】 ページ記述言語で記述された画像描画命
   令を並列に実行して画像情報を得る画像形成装置内にて
   前記画像描画命令の干渉関係を解析する命令解析装置に
   おいて、 前記画像描画命令を前記画像描画命令の命令単位で分割
   して複数の前記画像描画命令の命令ジョブからなるジョ
   ブシーケンスを作成するジョブシーケンス作成手段と、 前記命令ジョブを受けて命令ジョブ間の実行時の描画領
   域の重なりの有無を判定する重なり判定手段と、 前記判定手段の判定結果に応じ、描画平面を描画領域の
   重なりのない互いに素な部分領域に分割する領域分割手
   段と、 前記ジョブシーケンスに従って前記領域分割手段の分割
   結果から互いに素な部分領域の系列で前記画素情報を木
   構造に構成するとともに、前記重なり判定手段による重
   なり判定時に前記構成された木が探索されて判定対象と
   なる部分領域に属する命令ジョブが特定される木データ
   管理手段と、 を備えていることを特徴とする命令解析装置。
6. 【請求項６】 ページ記述言語で記述された画像描画命
   令を実行して画素情報を得る画像形成方法において、 前記画像描画命令を前記画像描画命令の命令単位で分割
   して複数の前記画像描画命令の命令ジョブからなるジョ
   ブシーケンスを作成し、 分割された前記画像描画命令を個々に並列に実行して各
   画素情報を並列に展開しながら、前記命令ジョブ間の実
   行時の描画領域の重なり関係を解析し、 前記描画領域の重なり関係の解析結果を参照して前記並
   列に展開された各画素情報の合成順序を動的に決定し、 決定された合成順序に従って前記画素情報を合成して画
   像を形成する、 ことからなる画像形成方法。