(57)【要約】【課題】描画部が行う処理には、オブジェクト間の重なりを処理する為の処理が含まれるが、従来はその処理を考慮せずに処理時間予測を行っていたため精度が低かった。【解決手段】画像を所定サイズのブロックに分割し、オブジェクトの所在のばらつきを示す係数を算出し、その係数と、オブジェクト間の処理のコマンドの数と、コマンドの処理時間とを乗じて、オブジェクト間の重なりを処理するための時間とする。これを、オブジェクトを描画するコマンドの実行に要する予測時間を加えて、画像の描画のために要する処理時間の予想値とする。【選択図】図６
2016034721.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトを描画するコマンドと、オブジェクト間の重なりに関する処理のコマンドとを含むデータに基づいて、入力された画像データの描画に要する時間を予測する画像処理装置であって、
前記オブジェクトを描画するコマンドの数と該コマンドの処理に要する時間とに基づいて、オブジェクト描画処理の予測時間を計算する第１の計算手段と、
前記画像データを分割したブロックごとに、前記ブロックに少なくとも一部が含まれるオブジェクトの数を計数し、前記ブロックごとのオブジェクトの数のばらつきを示す係数を算出する係数算出手段と、
前記オブジェクト間の重なりに関する処理のコマンドの数と該コマンドの処理に要する時間と前記係数とから、オブジェクト間処理の予測時間を計算する第２の計算手段と、
前記オブジェクト描画処理の予測時間と前記オブジェクト間処理の予測時間とを加算して、前記画像データの描画に要する時間を算出する予測手段と
を有することを特徴とする画像処理装置。
【請求項２】
前記画像処理装置は複数のプロセッサを更に有し、それぞれのプロセッサに割り当てた処理を並列に実行し、
前記画像データの描画に要する時間を、前記処理毎にプロセッサごとに算出し、前記複数のプロセッサのうちで最も長い画像データの描画に要する時間を、前記画像処理装置による画像データの描画に要する時間として決定することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記画像データの描画に要する時間の算出を、１ページを単位として行うことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記オブジェクト間の重なりに関する処理のコマンドには、ピクセルの色値を決定するコンポジット処理のコマンドと、オブジェクトのエッジソートのコマンドと、オブジェクトのレベルソートのコマンドとを含むことを特徴とする請求項１乃至３のいずれか一項に記載の画像処理装置。
【請求項５】
前記係数算出手段は、前記ブロックごとのオブジェクトの数から標準偏差を求め、前記標準偏差の値に予め対応づけられた値を前記係数として算出することを特徴とする請求項１乃至４のいずれか一項に記載の画像処理装置。
【請求項６】
前記画像データはバンド単位に分割されて外部装置から入力され、
前記係数算出手段は、閾値を超えた数のオブジェクトを含むバンドを対象として前記係数を算出することを特徴とする請求項１乃至５のいずれか一項に記載の画像処理装置。
【請求項７】
前記ブロックのサイズは、前記画像データに含まれたオブジェクトのサイズの平均値に応じて決定されることを特徴とする請求項１乃至６のいずれか一項に記載の画像処理装置。
【請求項８】
前記ブロックのサイズは前記画像データとともに外部装置から入力されることを特徴とする請求項７に記載の画像処理装置。
【請求項９】
請求項１乃至８のいずれか一項に記載の画像処理装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
オブジェクトを描画するコマンドと、オブジェクト間の重なりに関する処理のコマンドとを含むデータに基づいて、画像処理装置により、入力された画像データの描画に要する時間を予測する処理時間予測方法であって、
オブジェクトを描画するコマンドの数と該コマンドの処理に要する時間とに基づいて、オブジェクト描画処理の予測時間を計算する第１の計算工程と、
前記画像データを分割したブロックごとに、前記ブロックに少なくとも一部が含まれるオブジェクトの数を計数し、前記ブロックごとのオブジェクトの数のばらつきを示す係数を算出する係数算出工程と、
前記オブジェクト間の重なりに関する処理のコマンドの数と該コマンドの処理に要する時間と前記係数とから、前記オブジェクト間処理の予測時間を計算する第２の計算工程と、
前記オブジェクト描画処理の予測時間と前記オブジェクト間処理の予測時間とを加算して、前記画像データの描画に要する時間を算出する予測工程と
を有することを特徴とする処理時間予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、描画部の処理時間の予測を行う技術に関するものである。
【背景技術】
【０００２】
画像形成装置は、外部装置から受信したＰＤＬ（ページ記述言語）データからＤＬ（ディスプレイリスト）と呼ばれる中間データを生成する生成部と、生成された中間データからビットマップ画像を生成する描画部とを含む。生成部の生成する中間データは、一般に複数の描画コマンドを含んでいる。描画部は描画コマンドを逐次処理する為、中間データに含まれる描画コマンド数が多いと、描画部で行われる処理の演算量が多くなり、長い処理時間がかかる。処理演算量が高い中間データを処理する場合、描画部は入力された中間データのコマンドを解釈しながら処理を正常に実行し続ける。しかし、ユーザーからみると印刷処理が失敗して止まっているのか動作中なのかが分からず、ユーザーはデータの印刷をあきらめて、その印刷ジョブをキャンセルしてしまうことがある。そこで、印刷前に描画部の処理時間を予測し、その予測された時間をユーザーに提示することはユーザーにとって便利である。
【０００３】
特許文献１に開示される技術は外部装置が生成したＰＤＬのコマンドに対応する処理時間を算出する係数とＰＤＬのコマンド数とをかけ合わせることにより処理時間の予測を行う。この方法は、独立したオブジェクトの処理にかかる時間を精度よく予測することが出来る。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−２１６３５９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
中間データのコマンド数から描画部の処理時間を予測する上で、スキャンライン毎に行われるオブジェクトのエッジの座標算出のように、個々の独立したオブジェクトの処理時間はコマンド数から精度が高い予測が出来る。
【０００６】
しかしながら描画部が行う処理には、オブジェクト間の重なりを処理する為のエッジソートやレベルソートなどの処理が含まれる。ここでいうエッジソートとは、算出されたエッジの座標を昇順に並べ替える処理であり、レベルソートとは、オブジェクトの重なり順を降順に並べ替える処理である。
【０００７】
特許文献１に開示される方法では、上記のエッジソートやレベルソートなどに代表されるオブジェクト間の重なりの処理（単にオブジェクト間に関する処理とも呼ぶ）が考慮されていないので、処理時間の予測精度が低くなることがある。
【０００８】
本発明は、このような事情に鑑みてなされたもので、オブジェクト間に関する処理を含む描画処理に要する時間を高精度に予測することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために本発明は以下の構成を有する。
【００１０】
オブジェクトを描画するコマンドと、オブジェクト間の重なりに関する処理のコマンドとを含むデータに基づいて、入力された画像データの描画に要する時間を予測する画像処理装置であって、
オブジェクトを描画するコマンドの数と該コマンドの処理に要する時間とに基づいて、オブジェクト描画処理の予測時間を計算する第１の計算手段と、
前記画像データを分割したブロックごとに、前記ブロックに少なくとも一部が含まれるオブジェクトの数を計数し、前記ブロックごとのオブジェクトの数のばらつきを示す係数を算出する係数算出手段と、
前記オブジェクト間の重なりに関する処理のコマンドの数と該コマンドの処理に要する時間と前記係数とから、前記オブジェクト間処理の予測時間を計算する第２の計算手段と、
前記オブジェクト描画処理の予測時間と前記オブジェクト間処理の予測時間とを加算して、前記画像データの描画に要する時間を算出する予測手段とを有する。
【発明の効果】
【００１１】
本発明によれば、オブジェクト間の処理を含む描画処理に要する時間を高精度に予測できるようになる。
【図面の簡単な説明】
【００１２】
【図１】実施形態におけるシステム構成の一例を示すハードブロック図
【図２】実施形態におけるシステム構成の一例を示すソフトブロック図
【図３】実施形態における描画処理部の処理時間予測方法を示す図
【図４】実施形態におけるコマンド数から予測が容易な処理と予想が困難な処理を示す図
【図５】実施形態におけるオブジェクトが存在する領域のカウント方法を示す図
【図６】実施形態における領域情報を元にした描画処理時間予測の処理フローを示す図
【図７】実施形態における所定のバンドのみの領域情報を元にした描画処理時間予測を示す図
【図８】実施形態における所定のバンドのみ領域情報を元にした描画処理時間予測処理フローを示す図
【図９】実施形態におけるオブジェクトサイズに応じた可変サイズ領域情報を元にした描画処理時間予測を示す図
【図１０】実施形態におけるオブジェクトサイズに応じた可変サイズ領域情報を元にした描画処理時間予測フローを示す図
【発明を実施するための形態】
【００１３】
以下、本発明を実施するための形態について図面を用いて説明する。
［実施例１］
＜用語の定義＞
ここで本実施形態における用語の定義について説明する。
【００１４】
ＤＬ（ディスプレイリスト）とは、各種ＰＤＬから変換され生成される、描画部が処理可能なフォーマットである。ディプレイリストには、インストラクションと呼ばれるどのオブジェクトをページ内のどの場所に書くかという描画命令と、各オブジェクトに紐付けられるエッジ情報、そのエッジ情報に紐づけられるレベル情報、そのレベル情報に紐付けられるフィル情報およびＲＯＰ情報が記載されている。１つのオブジェクトに関連するこれら描画命令および各情報を１つにまとめたものをコマンド（ＤＬコマンド）と呼ぶ。またＤＬは中間データとも呼ばれている。
【００１５】
次に、オブジェクト間に関する処理とは、ＰＤＬやＤＬに含まれる複数のオブジェクトがどのような関係で最終的に描画されるかを決定する為の処理である。オブジェクト間の重なりに関する処理ともいえる。例えばオブジェクトとオブジェクトとが重なる際、お互いのオブジェクトのエッジが所定のライン（主走査ライン）でクロスする場合、エッジのオーダー（所定のラインの先頭側（例えば左側）から表れるエッジの順番）を決定するエッジソート処理を行う。またどちらのオブジェクトが上に描画されるかを決定するレベルソート処理や、重なる部分がどのように塗られるかの情報（例えば上書き、透過、ＲＯＰ）を元にピクセルの色値を決定するコンポジット処理がある。なお透過処理では不透明度をパラメータとした重複部分の合成が、ＲＯＰ（ラスタ演算）処理では、論理和や論理積といった論理積による重複部分の合成が行われる。また、オブジェクト間に関する処理のＤＬコマンドはオブジェクトに関連しており、オブジェクト数に相当する数だけＤＬに含まれる。オブジェクトを描画する処理をオブジェクト描画処理とよび、オブジェクト間の重なり等の処理をオブジェクト間処理と呼ぶ。
【００１６】
＜コントローラーユニットのハード構成＞
図１は、本実施例における画像形成装置のコントロールユニット（コントローラ）の一構成例を示すハードウエアブロック図である。なお画像形成装置は画像処理を伴うことから画像処理装置と呼ぶこともある。コントロールユニット１００は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）  Ｎ１と接続することで、画像情報やデバイス情報をＬＡＮ  Ｎ１経由で入出力するための制御を行う。プリンタエンジン１１０は、デバイスＩ／Ｆ１０９に結合され、コントロールユニット１００で生成された描画データを紙などシートに印刷する処理を行う。ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０２はＭＦＰ全体の制御や、ＰＤＬデータからＤＬデータ（単にＤＬとも呼ぶ）を生成するための中央処理装置である。また、ここでコマンド数のカウントや後述するＲＩＰの処理時間の予測を行う。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１０３は、ＣＰＵ１０２が動作するためのシステムワークメモリであり、入力された画像データを一時記憶するための画像メモリでもある。さらに、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１０６はブートＲＯＭであり、システムのブートプログラムが格納されている。ＨＤＤ１０７はハードディスクドライブであり、各種処理のためのシステムソフトウェア及び入力された画像データを等格納する。ネットワークインタフェース１０４は、例えばＬＡＮカード等で実現され、ＬＡＮ  Ｎ１に接続して外部装置との間でＰＤＬなどの情報の入出力を行う。ラスタイメージプロセッサ（ＲＩＰ）１０８は、ＤＬすなわち中間データをイメージに展開する。ＵＩ１１１はＲＩＰの処理時間の予測結果を表示する。
【００１７】
＜コントローラーユニットのソフト構成＞
次に、図２は、本実施例におけるＭＦＰのコントロールユニット（コントローラ）２００の一構成例を示すソフトウエアブロック図である。図１の構成は、図1に示したハードウェア上で、特にＣＰＵ１０２によりプログラムを実行することで実現される。ＰＤＬ生成処理部２０１は、図１のネットワークＮ１を通じて接続されホストＰＣのドライバで、アプリケーションデータからＰＤＬデータを生成する。ＰＤＬ解釈部２０２ではＰＤＬ生成処理部２０１で生成されたＰＤＬデータ（以下単にＰＤＬとも呼ぶ。）を入力としてＰＤＬの解釈を行う。ＤＬ生成部２０３ではＰＤＬ解釈部２０２で解釈された情報を元にＰＤＬの中間言語であるＤＬの生成を行う。コマンド数カウント部２０４では、ＤＬ生成処理で作成したコマンド（ＤＬコマンド）をカウントし記録する処理を行う。描画処理予測部２０５ではカウントしたコマンド数を元に描画処理部の予測時間等、印刷処理全体の予測時間の算出を行う。ビットマップ生成部２０７では印刷解像度のＤＬや最適化されたＤＬを入力としてレンダリングを行い、ビットマップの生成を行う。ビットマップデータは二値とは限らず、複数の色成分の輝度あるいは濃度を多値で示したフルカラーデータを含む。ビットマップ生成部２０７は、ハードウェア資源としてＲＩＰ１０８を用いて実現される。予測結果表示部２０８では、描画処理予測部で算出した印刷処理全体の予測時間の表示を行う。
【００１８】
＜描画処理部の処理時間予測方法について＞
次に、図３を用いて、本実施例における描画処理部の処理時間予測方法について説明する。ＰＤＬデータ３０１は、ＰＤＬ生成処理部２０１で生成され、コントロールユニット２００に入力されたＰＤＬデータを表す。コマンド数３０２はＰＤＬデータ３０１をＰＤＬ解釈部２０２で解釈し、コマンド数カウント部２０４でカウントしたコマンド数を表す。
【００１９】
ビットマップ生成部２０７では、内部的に複数個のプロセッサがパイプラインを構成し並列処理を行っている。各プロセッサは各処理を行っており、例えばプロセッサＰＡは処理１から処理３を行っていることを表している。各処理の単位当たりの処理時間である処理係数は、処理のインストラクション数やプロセッサの周波数などから事前に決定しておく。決定した係数は、例えば描画処理予測部２０５に保持させる。
【００２０】
関連付け情報３０４は、中間データに含まれるコマンド（ＤＬコマンド）と描画部の処理との関連付けであり、例えば処理１はコマンドＡのコマンド数と関連することを表している。
【００２１】
予測値算出処理３０５は、描画処理部の処理時間を予測式に従って算出することを示している。描画処理予測部２０５が、カウントされたコマンド数３０２と、コマンドと処理との関連付け３０４と、事前に算出した処理係数とから対象処理の予測時間を算出する。対象プロセッサで実行される処理の処理時間の和が対象プロセッサによる処理の予測時間になる。ビットマップ生成部（描画処理部とも呼ぶ）２０７内部のプロセッサがパイプラインで並列動作している場合、全プロセッサの予測時間を算出し、その中で最も長い（ボトルネックとなりうる）予測時間がビットマップ生成部（描画処理部）２０７の予測時間となる。
【００２２】
＜コマンド数から予測が容易な処理と困難な処理について＞
次に、図４を用いて本実施例における、コマンド数から予測が容易な処理と予想が比較的困難な処理に関してそれぞれ説明する。この処理は、ハードウェア構成上はＲＩＰ処理部１０８で、ソフトウェア構成上はビットマップ生成部２０７で行われる処理になる。
【００２３】
エッジ座標算出処理４０１は、中間データのコマンド数から描画処理時間を予測する上で必要な処理であるエッジの座標算出を示している。エッジの座標算出は必ず１スキャンラインに１回行われるので、エッジの高さ（スキャンラインと直交するライン方向の長さ）とエッジの数とによりエッジの座標算出回数のカウントは容易に行える。エッジ座標算出処理４０１において、横方向の点線はスキャンライン（主走査ライン）であり、縦線および斜め線が例えばオブジェクトの輪郭線を示す。その輪郭線とスキャンラインとの交点がエッジとなる。図の例では、縦線からは（６，１０）、（６，１１）の２つのエッジが、斜め線からは（１０，１０）、（９，１１）、（８，１２）、（７，１３）の４つのエッジが算出される。そしてたとえばエッジ（６，１０）とエッジ（１０，１０）との間のように、一つのスキャンライン上の２つのエッジ間の領域をスパンと呼ぶ。スパンはたとえばスキャンライン上でオブジェクト内部や重複部などを示す領域となる。
【００２４】
ソート処理４０２は、描画処理時間を予測する上で考慮される処理であるレベルのソート処理を示している。レベルのソート処理はスキャンライン毎にエッジ間の閉領域であるスパン単位で処理され、最終的に描画されるオブジェクトを確定する為に行われる処理である。各レベルはレベル番号で示され、スパンのレベルは、スパンをレベル番号に従って降順ソートしたリストテーブルで管理されている。ソート処理４０２の左側は新たに挿入されるスパンの例で、右側はリストテーブルを表す。レベル番号順にスパンがソートされたリストテーブルに新たなスパンが追加される場合、挿入されるスパンのレベル番号とリストテーブルのレベル番号とを比較して、レベル番号が降順になる位置に追加される。その場合、リストを辿り始めるレベル番号やいくつのレベルがリストテーブルに積まれているか（言い換えれば該当スパンにおいて重なりあうオブジェクトの数）によって比較が行われる回数が変化するので、中間データのコマンド数からエッジ検出およびレベルソートの処理所要時間を算出することは難しい。
【００２５】
＜オブジェクトが存在する領域のカウント方法について＞
次に、図５を用いて本実施例におけるオブジェクトが存在する領域のカウント方法について説明する。この処理はコマンド数カウント部２０４で行われる処理になる。
【００２６】
領域５０１は描画領域を矩形のブロックに分割した例を示している。分割した矩形のサイズは、例えば６４×６４画素や１２８×１２８画素や３２×３２画素などになる。
【００２７】
図５のオブジェクト５０２はＰＤＬ解釈部２０２で処理され入力されてきたオブジェクトを示している。このオブジェクト５０２にはバウンディングボックスと呼ばれる、対象オブジェクトを取り囲む矩形領域が保持されている。オブジェクトのバウンディングボックスは、そのオブジェクトのＰＤＬコマンドから求めることができる。
【００２８】
入力されたオブジェクト５０２は、描画領域５０１の中央付近の６ブロックにまたがっている。また、このオブジェクト５０２のバウンディングボックスがかかる矩形領域は上から２つ目、左から２つ目のブロックと、上から４つ目、左から３つ目のブロックとを対角とする合計６つの矩形にかかっている。よって、この６つの矩形ブロックそれぞれについてオブジェクト数のカウントアップを行うことによって、ブロックごとのオブジェクト数をカウントすることが出来る。この例では、上記オブジェクトのバウンディングボックスが掛かる６ブロックのカウンタがそれぞれ１ずつ増分される。なお、本実施例でバウンディングボックスを用いているのは、オブジェクトの関わるブロックを簡易に特定することが可能だからである。そのため、バウンディングボックスを用いずに、オブジェクトの輪郭を正確に求めてそのオブジェクトの関わるブロックを特定しても良い。
【００２９】
カウント例５０４は上記要領で全てのオブジェクトに対するＰＤＬ解釈部２０２による処理が終了した際のブロックのカウントの例を示している。この例５０４では、例えば左上のブロックに関わるオブジェクトの個数が１０であるが、左から２つめ上から３つ目のブロックに関わるオブジェクトの個数は７０であることが示される。すなわちこの例５０４では、上下左右のブロックにはオブジェクトがあまり存在せず、真ん中付近にオブジェクトが多く存在することが分かる。
【００３０】
偏り係数算出処理５０５はブロックのカウントを元に偏り係数の算出の例を示している。まず各領域でカウントした値から標準偏差を算出する。図５のカウント例５０４では、計２０ブロックのそれぞれに関わるオブジェクトの個数から算出される標準偏差は、約１８．９である。次に、標準偏差の値に応じて各処理用の偏り係数を決定する。偏り係数はエッジソートやレベルソートなど処理によって異なる値が使用され、偏り係数は処理のインストラクション数やプロセッサの周波数などから算出される。例えば或る処理に対しては、算出された標準偏差が０以上１０未満の場合は偏り係数１、１０以上２０未満の場合は偏り係数２、２０以上３０未満の場合は偏り係数４、３０以上４０未満の場合は偏り係数６などと設定する。標準偏差を基に偏り係数を算出する理由は、１ページ内に同じ個数のオブジェクトが存在した場合、特定の領域に密集した（標準偏差は大きい）場合、ページ内に偏りなく均等に表れる（標準偏差は小さい）場合に比べて処理時間が多くかかることが分かっているためである。
【００３１】
＜領域情報を元にした描画処理時間予測の処理フローについて＞
次に、図６を用いて本実施例における領域情報を元にした描画処理時間予測の処理フローについて説明する。この処理は、図１のＲＡＭ１０３に処理実行するプログラムがロードされ、ＣＰＵ１０２上で動作することで実現される。そして各工程が、図２の機能ブロックのいずれかに相当する。以下の説明では各工程ではいずれかの機能ブロックが主体となるものとして説明する。
【００３２】
ステップ６００において領域情報を元にした描画処理時間予測の処理は開始される。次にステップ６０２においてコマンド数カウント部２０４は予測の対象となるＰＤＬデータとオブジェクト当りの係数６０１をＰＤＬ生成処理部２０１から受信しＲＡＭ１０３に格納し、ＰＤＬの描画領域をブロックに分割する処理を行う。係数６０１は、たとえばひとつのＰＤＬコマンドに対応する処理時間などである。ブロックの分割処理は＜オブジェクトが存在する領域のカウント方法について＞で説明した処理となる。すなわち、たとえばページを複数のブロックに分割する。ＰＤＬデータが複数のページにわたる場合には、各ページについて同様のブロック分けが用いられる。ステップ６０３においてＰＤＬ解釈部２０２はＰＤＬデータの解釈を行う。ＰＤＬ解釈部２０２はステップ６０４でＤＬコマンドを生成する。コマンド数カウント部２０４は、ステップ６０５で、生成されたＤＬコマンドがオブジェクト間に関する処理のコマンドか否かを判断する。オブジェクト間に関する処理のコマンドか否かは、そのＤＬコマンドの種類によって判断できる。たとえばレベル情報やＲＯＰ情報を伴うＤＬコマンドであれば、オブジェクト間に関する処理のコマンドであると判断できる。
【００３３】
ステップ６０５の判断がＹＥＳだった場合、コマンド数カウント部２０４はステップ６０６で、コマンド数のカウントアップと、オブジェクトが含まれるブロックにおけるオブジェクト数のカウントアップをする。コマンドごとに係数が異なる可能性があるため、コマンド数はコマンドの種類ごとに計数する。ブロックにおけるオブジェクト数のカウントアップ処理は＜オブジェクトが存在する領域のカウント方法について＞で説明した処理となる。すなわち、コマンド数のカウンタに１加算するとともに、処理対象のコマンドに係るオブジェクトの少なくとも一部（またはバウンディングボックス（外接矩形）の一部）が掛かるブロックのカウンタ値に１加算する。ステップ６０５の判断がＮｏだった場合、コマンド数カウント部２０４はステップ６０７でコマンド数のカウントアップを行う。コマンドごとに係数が異なる可能性があるため、コマンド数はコマンドの種類ごとに計数する。ＰＤＬ解釈部２０２はステップ６０８で１ページのコマンド生成処理が終了したか否かを判断する。
【００３４】
ステップ６０８の判断がＮＯだった場合、ステップ６０３へ分岐してＤＬコマンド生成を継続させる。ステップ６０８の判断がＹＥＳだった場合、ＰＤＬ解釈部２０２はステップ６０９において、処理終了したページのコマンド数と、ブロックごとのカウントされた値（ブロックカウント）をＲＡＭ１０３に保存する。ＰＤＬ解釈部２０２はステップ６１０で全ページのコマンド生成処理が終了したか否かを判断する。ステップ６１０の判断がＮＯだった場合、ステップ６０３に分岐してＤＬコマンド生成を継続させる。
【００３５】
ステップ６１０の判断がＹＥＳだった場合、ステップ６１１に進んで予測時間の算出処理を行う。算出処理では、ステップ６１１〜６１５のループにおいて、ビットマップ処理部２０７（すなわちＲＩＰ１０８）に含まれたプロセッサで実行する処理ごとの所要時間を予測する。各プロセッサには図３に示すように予め実行する処理が割り当てられており、関連付け情報３０４によってコマンドと実行する処理との対応付けが示されている。そこで、まず描画処理予測部２０５はステップ６１１において、一つのプロセッサに着目し、さらにその中の一つの処理に着目する。そして、着目処理の実行を伴うコマンドについて描画処理時間予測の為のコマンド数をロードし、またブロックごとのカウント値をロードする。そしてブロックごとのカウント値から偏り係数を算出する。
【００３６】
次に描画処理予測部２０５はステップ６１２においてこれから処理時間を予測する着目処理がオブジェクト間に関する処理か否かを判断する。オブジェクト間に関する処理か否かの判断は、処理時間を予測する上で、静的にコマンド数×係数で予測時間を求められる処理はオブジェクト間でない処理と判断し、描画処理時のその時々によってオブジェクト同士の関係によりコマンド数が変動する処理をオブジェクト間に関する処理と判断する。すなわち処理の種類に基づいて判断する。着目処理がいずれの処理であるかは、処理毎に予め分類しておき、処理の分類に係る情報を関連付け情報３０４などとともに保存しておけばよい。具体的には、エッジのソート処理、レベルのソート処理、ピクセルのコンポジット処理などがこのオブジェクト間に関する処理に該当する。
【００３７】
ステップ６１２がＹＥＳだった場合、描画処理予測部２０５はステップ６１３において、ブロックカウント値を元に算出した偏り係数と着目処理に対応するコマンド数と着目処理の処理係数を元に予測時間を算出する。たとえば、それらの値をすべて掛け合わせた積を予測時間とする。ステップ６１２がＮＯだった場合、描画処理予測部２０５はステップ６１４において、着目処理に対応したコマンド数と着目処理の処理係数を元に予測時間を算出する。たとえば、それらの値を掛け合わせた積を予測時間とする。描画処理予測部２０５はステップ６１５において、予測中のプロセッサの全処理の予測時間算出が済んでいるか否かを判断する。例えば、図３のビットマップ生成部２０７内のＰＡプロセッサの予測をしている場合、処理１、処理２、処理３の３つの予測が終わったか否かを判断する。
【００３８】
ステップ６１５がＮＯだった場合、ステップ６１１に飛び、着目プロセッサにより実行する他の処理を着目処理として処理の予測時間の算出を継続する。ステップ６１５がＹＥＳだった場合、描画処理予測部２０５はステップ６１６において各処理の予測時間の合計を算出し、その値を着目プロセッサの予測時間とし、保存する。描画処理予測部２０５はステップ６１７において描画処理部の全プロセッサの予測時間が算出済か否かを判断する。
【００３９】
ステップ６１７がＮＯだった場合、ステップ６１１に飛び、他のプロセッサを新たな着目プロセッサとして処理の予測時間の算出を継続する。ステップ６１７がＹＥＳだった場合、描画処理予測部２０５はステップ６１８において各プロセッサの予測時間により描画処理の予測時間を算出する。予測時間の算出は、パイプライン処理に関わる複数プロセッサそれぞれのＳ６１６で算出された予測時間のうち、最も長い予測時間（律速時間）を、描画処理の予測時間とする。この処理は、＜描画処理部の処理時間予測方法について＞で説明した予測値算出処理３０５になる。描画処理予測部２０５はステップ６１９において全ページの予測時間を算出済みか否かを判断する。
【００４０】
ステップ６１９がＮＯだった場合、ステップ６１１に飛び次のページについて処理時間の予測を継続させる。ステップ６１９がＹＥＳだった場合、ステップ６２０において領域情報を元にした描画処理時間予測の処理が終了する。
【００４１】
以上の構成及び手順により本実施形態の画像形成装置であるＭＦＰは、個々のオブジェクトのレンダリングのみならず、オブジェクトの重複に関する処理時間も併せて予測することができ、より精度の高い処理時間予測を実現できる。
【００４２】
なお、ステップ６０６ではオブジェクト間の処理に関するコマンドに係るオブジェクトの少なくとも一部が含まれるブロックに対応するカウンタをカウントアップしている。その代わりに、ステップ６０５において、着目コマンドにより描画されるオブジェクトが含まれるブロックのカウンタをカウントアップしてもよい。
【００４３】
［実施形態２］
＜所定のバンドのみ領域情報を元にした描画処理時間予測＞
次に、図７を用いて本実施例における所定のバンドのみ領域情報を元にした描画処理時間予測について説明する。この実施形態では、ＰＤＬ生成処理部２０１がバンド単位でオブジェクト数を数えるだけであるが、バンド単位で生成したＰＤＬデータをＭＦＰに送信するバンディング処理を行ってもよい。この予測時間の算出処理はＰＤＬ生成処理部２０１及びＭＦＰのＣＰＵ１０２により実現されるＰＤＬ解釈部２０２、ＤＬ生成部２０３およびコマンド数カウント部２０４、描画処理予測部２０５で行われる処理になる。
【００４４】
オブジェクト数カウンタ７０１は、ＰＤＬの描画領域に含まれるオブジェクト数がバンド単位で分割した領域に幾つ含まれているかをバンドごとに示す図になる。このオブジェクト数のカウントは、ＰＤＬ生成処理部２０１がＰＤＬを生成しながら行うものである。この例では、上下のそれぞれ２バンドに含まれるオブジェクト数が少ないが、真ん中のバンドには大量のオブジェクトが含まれていることが分かる。１バンドに含まれるスキャンライン数の例としては、３２、６４、１２８、２５６、５１２などになる。ただしバンディング処理を行う場合にはバンド幅が可変でもよい。ここでのオブジェクト数のカウントは、生成部のバウンディングボックスを元にしたカウントではなく、ＰＤＬ生成時に行われる簡易なカウントになる。
【００４５】
オブジェクト数カウンタ７０２は、閾値以上のオブジェクトが含まれているバンドを更にブロックに分割し、ブロックごとのオブジェクト数をカウントした例を示している。この例の場合、左右の端ブロックの含まれるオブジェクト数は少ないが、真ん中のブロックには多くのオブジェクトが含まれている。この例ではバンドは主走査方向に分割されてその高さがそのままブロックの高さになっているが、副走査方向（高さ方向）に分割してもよい。
【００４６】
＜所定のバンドのみ領域情報を元にした描画処理時間予測処理フロー＞
次に、図８を用いて本実施例における所定のバンドのみ領域情報を元にした描画処理時間予測処理フローについて説明する。この処理は、ステップ８０１〜８０８は図１のネットワークＮ１に接続されたホストＰＣで実行され、それ以降の処理はＭＦＰのＲＡＭ１０３に処理実行するプログラムがロードされ、ＣＰＵ１０２上で動作することで実行される。
【００４７】
ステップ８０１において所定バンドのみ領域情報を元にした描画処理時間予測の処理は開始される。次にステップ８０３においてＰＤＬ生成部２０１は、アプリデータや印刷情報データ８０２を元に描画領域をバンドに分割する処理を行う。ＰＤＬ生成部２０１はステップ８０４において先頭から順にアプリデータを解釈し、ステップ８０５で描画オブジェクト、すなわちオブジェクトを記述したＰＤＬデータを生成する。ＰＤＬ生成部２０１はステップ８０６において、生成した描画オブジェクトが含まれるバンドのオブジェクト数をカウントアップする。バンドのオブジェクトの数をカウントアップ処理は＜所定のバンドのみの領域情報を元にした描画処理時間予測＞で説明したカウント値７０１を生成する処理となる。ＰＤＬ生成部２０１はステップ８０７において入力データ全てのオブジェクトの生成が終了したか判断する。
【００４８】
ステップ８０７がＮＯだった場合、ステップ８０４に飛びアプリデータの解釈やバンドカウントアップを継続する。ステップ８０７がＹＥＳだった場合、ＰＤＬ生成部２０１はステップ８０８において、生成したＰＤＬデータやバンドごとのカウント値をコントローラ２００に送信する。ＰＤＬ解釈部２０２はステップ８０９においてステップ８０８で送信されたＰＤＬデータ、バンドカウント、ブロック化する際のバンドに含まれるオブジェクト数の閾値を受信する。ＰＤＬ解釈部２０２はステップ８１０において、先頭から順にバンドに着目し、着目した対象バンドのオブジェクト数がオブジェクト数の上限すなわち閾値を超えているか否かを判断する。
【００４９】
ステップ８１０がＹＥＳだった場合、ＰＤＬ解釈部２０２はステップ８１１において着目バンドをブロックに分割する。ステップ８１０がＮＯだった場合、８１１の処理は行わない。ＰＤＬ解釈部２０２はステップ８１２においてページ内の全てのバンドの判定が終了したか否かを判断する。ステップ８１２がＮＯだった場合、ステップ８１０に飛び、新たな着目ハンドのブロック分割の判断を継続する。ステップ８１２がＹＥＳだった場合、ＰＤＬ解釈部２０２はステップ８１３で入力された全データのＰＤＬ解釈を行う。
【００５０】
次にステップ８１４〜ステップ８１６を実行する。ステップ８１４〜ステップ８１６は、ＰＤＬデータに含まれた着目コマンドを対象として、すべてのコマンドに順次着目してコマンド毎に実行される。まずステップ８１４において、ＰＤＬ解釈部２０２およびコマンド数カウント部２０４はそれぞれ、着目コマンドがオブジェクト間に関する処理のコマンドで、かつ、当該コマンドに関するオブジェクトがステップ８１１でブロック化した領域に含まれるか否かを判断する。ステップ８１４がＹＥＳだった場合、画処理予測部２０５はステップ８１５において、コマンド数のカウントアップと、オブジェクトが含まれるブロックの、コマンド数のカウントアップをする。これは図６のステップ６０６と同じくオブジェクトのバウンディングボックスが掛かるブロックを、そのオブジェクトを含むブロックとして行われる。コマンド数は、実施形態１と同様にコマンドの種類ごとにカウントする。ブロックのコマンド数は種類ごとに分ける必要はない。ステップ８１４がＮＯだった場合、コマンド数カウント部２０４はステップ８１６においてコマンド数のカウントアップを行う。コマンド数は、実施形態１と同様にコマンドの種類ごとにカウントする。このようにして、ステップ８１５では、ブロック分けされた領域に限って、ブロック内のコマンド数が数えられる。コマンド数カウント部２０４はステップ８１７において、ブロックごとのコマンド数を基にして標準偏差を計算し、それを偏り係数に変換する。
【００５１】
ステップ８１８〜８２０は、プロセッサで実行する処理毎に着目して実行され、全ての処理を対象として、着目処理に関連づけられたコマンドごとに行われる。まず描画処理予測部２０５はステップ８１８において、着目した処理が、オブジェクト間に関するコマンドに関連付けられた処理であり、かつ、そのコマンドに係るオブジェクトがブロック化した領域のいずれかに含まれるか否かを判断する。ステップ８１８がＹＥＳだった場合、描画処理予測部２０５はステップ８１９において、ブロックごとのコマンド数を元に算出した偏り係数とコマンド数と処理単位当たりの係数とを元に予測時間を算出する。具体的には、たとえばこれらの数値の積を着目処理の所要時間の予測値とする。処理に関連づけられたコマンドが複数種類ある場合にはそれらの所要時間の和を予測値とする。ステップ８１８がＮＯだった場合、描画処理予測部２０５はステップ８２０において、コマンド数と処理単位当たりの係数を元に予測時間を算出する。具体的には、着目処理に対応付けられたコマンドごとのコマンド数にそれぞれの係数を乗じ、その値の総和を着目処理の所要時間の予測値とする。描画処理予測部２０５はステップ８２１において、各処理、各プロセッサの処理時間予測を元に描画部の処理時間予測を行う。具体的には、ステップ８１９，８２０で算出した処理毎の所要時間の予測値の、当該処理を実行するプロセッサごとの総和を計算する。そしてプロセッサごとの予測処理時間のうちの最大値を予測時間として採用する。なおこの処理時間の予測値はたとえばページ単位で行われる。ステップ８２２において特定のバンドのみ領域情報を元にした描画処理時間予測の処理が終了する。
【００５２】
以上のようにして、本実施形態のレンダリング処理に要する処理時間の予測ができる。本例では、実施形態１と同様にオブジェクトの重複のばらつきを示す係数により重み付けした、オブジェクトの重なり処理についても予測時間に含めることができ、より予測精度が向上する。加えて、オブジェクトの重なり処理をＰＤＬデータ全体について行わず、オブジェクト数が閾値よりも多く、処理時間全体に対する影響度が大きい領域についてオブジェクトの重なり処理の予測処理時間を予測時間に含めている。このため、計算量を減らしてより処理時間の短縮、予測処理の負担軽減を図ることができる。
【００５３】
［実施形態３］
＜オブジェクトサイズに応じた可変サイズ領域情報を元にした描画処理時間予測＞
次に、図９を用いて本実施例におけるオブジェクトサイズに応じた可変サイズ領域情報を元にした描画処理時間予測について説明する。この処理はＰＤＬ生成処理部２０１及びＣＰＵ１０２で実現されるＰＤＬ解釈部２０２およびコマンド数カウント部２０４等で行われる処理になる。
【００５４】
画像９０１と画像９０２は、描画領域に含まれる平均的なオブジェクトサイズに応じた領域を矩形のブロックに分割した際のブロックサイズの違いを表した例になる。画像９０１は画像９０２に比べ大きなサイズのオブジェクトを多く含む為、それに合わせて矩形のブロックサイズも大きくなっている。逆に画像９０２は画像９０１に比べ小さなサイズのオブジェクトが多い為、それに合わせて矩形のブロックサイズも小さくなっている。このように、オブジェクトの大きさに応じてブロックサイズを可変にすることにより、ブロックごとのオブジェクト数のカウントを行う処理負荷を減らしている。オブジェクトサイズは、ＰＤＬデータを生成する際、ＰＤＬ生成処理部２０１で記録され、ＰＤＬ生成処理部２０１で描画領域をブロックに分割する際に事前に決定されたオブジェクトサイズとブロックサイズとの関係から分割するブロックサイズを決定する。
【００５５】
＜オブジェクトサイズに応じた可変サイズ領域情報を元にした描画処理時間予測フロー＞
次に、図１０を用いて本実施例におけるオブジェクトサイズに応じた可変サイズ領域情報を元にした描画処理時間予測フローについて説明する。この処理は、図１のネットワークＮ１先のホストＰＣ上と、ＲＡＭ１０３に処理実行するプログラムがロードされ、ＣＰＵ１０２上で実行することで実現される。
【００５６】
ステップ１００１においてオブジェクトサイズに応じた可変サイズ領域情報を元にした描画処理時間予測処理フローの処理は開始される。ステップ１００３においてＰＤＬ生成部２０１はステップ１００２から入力したアプリデータを元にアプリデータの解釈を行い、ステップ１００４で描画オブジェクトを生成する。ＰＤＬ解釈部２０２はステップ１００５において、生成された描画オブジェクトのサイズの平均値を算出し保持する。なお、新たなオブジェクトが生成された場合には、そのオブジェクトのサイズを含むよう平均値を更新する。ＰＤＬ解釈部２０２はステップ１００６において、入力データ全てのオブジェクトの生成が終了したか判断する。
【００５７】
ステップ１００６がＮＯだった場合、ステップ８０４に飛びアプリデータの解釈や描画オブジェクトの平均サイズの算出を継続する。ステップ１００６がＹＥＳだった場合、ＰＤＬ解釈部２０２はステップ１００７において生成したＰＤＬデータや算出したオブジェクトサイズの平均値をコントローラ２００に送信する。
【００５８】
ＰＤＬ解釈部２０２はステップ１００８においてステップ１００７で送信されたＰＤＬデータ、描画オブジェクトの平均サイズを受信する。ＰＤＬ解釈部２０２はステップ１００８において、生成された描画オブジェクトのサイズの平均値を元にブロックサイズ決定する。ブロックサイズは、たとえば、平均サイズの描画オブジェクトが跨るブロック数が所定の数となるように決定される。例えば画像９０１では、平均サイズのオブジェクトは３×３ブロックに属するようにブロックサイズを決定する。後のステップは図６のステップ６０３以降と同様になる。
【００５９】
本実施形態により、ブロックサイズをオブジェクトのサイズに応じて決定できるために、ブロックごとのオブジェクト数のカウントを行う処理負荷を減らし、より迅速に処理時間を予測を行える。
【００６０】
［他の実施形態］
以上、様々な実施形態を詳述したが、本発明は、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。例えば、スキャナ、プリンタ、ＰＣ、複写機、複合機及びファクシミリ装置の如くである。
【００６１】
本発明は、前述した実施形態の各機能を実現するソフトウェアプログラムを、システム若しくは装置に対して直接または遠隔から供給し、そのシステム等に含まれるコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される。
従って、本発明の機能・処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、上記機能・処理を実現するためのコンピュータプログラム自体も本発明の一つである。
【００６２】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等、プログラムの形態を問わない。
【００６３】
プログラムを供給するための記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷなどがある。また、記録媒体としては、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ、ＤＶＤ−Ｒ）などもある。
【００６４】
また、プログラムは、クライアントコンピュータのブラウザを用いてインターネット／イントラネットのウェブサイトからダウンロードしてもよい。すなわち、該ウェブサイトから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードしてもよいのである。
【００６５】
また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるウェブサイトからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザーに対してダウンロードさせるＷＷＷサーバも、本発明の構成要件となる場合がある。
【００６６】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザーに配布してもよい。この場合、所定条件をクリアしたユーザーにのみ、インターネット／イントラネットを介してウェブサイトから暗号化を解く鍵情報をダウンロードさせ、その鍵情報で暗号化されたプログラムを復号して実行し、プログラムをコンピュータにインストールしてもよい。
【００６７】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現されてもよい。なお、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行ってもよい。もちろん、この場合も、前述した実施形態の機能が実現され得る。
【００６８】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれてもよい。そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ってもよい。このようにして、前述した実施形態の機能が実現されることもある。
【００６９】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。また１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００７０】
１００  コントロールユニット、１０２  ＣＰＵ、１０８  ＲＩＰ、１１０  プリンタエンジン
【図１】
2016034721.tif 000003
【図２】
2016034721.tif 000004
【図３】
2016034721.tif 000005
【図４】
2016034721.tif 000006
【図５】
2016034721.tif 000007
【図６】
2016034721.tif 000008
【図７】
2016034721.tif 000009
【図８】
2016034721.tif 000010
【図９】
2016034721.tif 000011
【図１０】
2016034721.tif 000012