画像処理装置及び画像処理方法
【課題】図形の輪郭からエッジデータを生成するレンダリング処理に係るデータ処理を、入力された図形に応じて処理手順（アルゴリズム）を適切に切り替えて行えるようにする。
【解決手段】入力された図形（オブジェクト）を図形種別判定処理により単純図形系と複雑図形系とに分類し、単純図形系についてはタイル処理によるエッジ検出処理を行い、複雑図形系についてはスキャンラインによるエッジ検出処理を行うように、図形の分類に応じて処理手順を適切に切り替えて、レンダリング処理に係るエッジ情報を生成できるようにする。
【解決手段】入力された図形（オブジェクト）を図形種別判定処理により単純図形系と複雑図形系とに分類し、単純図形系についてはタイル処理によるエッジ検出処理を行い、複雑図形系についてはスキャンラインによるエッジ検出処理を行うように、図形の分類に応じて処理手順を適切に切り替えて、レンダリング処理に係るエッジ情報を生成できるようにする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理方法に関し、特にレンダリング処理等に適用可能なエッジ情報生成に係る画像処理技術に関する。
【背景技術】
【０００２】
従来から図形を描画するために図形が持つ座標情報等から図形の輪郭情報（エッジ情報とも呼ぶ）を抽出し、該輪郭情報に基づいて画像を形成するレンダリング手法は一般に広く利用されている（例えば、特許文献１、特許文献２、特許文献３、特許文献４）。また、輪郭情報は直線で表現されるが該直線を表現するための手法としてＤＤＡ（Digital Differential Analyzer）アルゴリズムが知られている（非特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平０４−１７０６８６号公報
【特許文献２】特開平０８−７２３１７号公報
【特許文献３】特開２００５−２６７２９０号公報
【特許文献４】特開２００７−１２２１８８号公報
【非特許文献】
【０００４】
【非特許文献１】David Rogers, "Procedural Elements for Computer Graphics", McGraw-Hill Education
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、レンダリング処理において常に高速に描画処理が実行できることは重要な要件であるが、実際にレンダリング処理に要する時間は、図形の種類や数に依存して変化するためこれを実現することは容易ではない。従来のレンダリング処理では図形の種類によらずデータ処理を行うための手続き（アルゴリズム）は固定されており、レンダリング処理の高速化という観点では不十分な構造であった。
本発明は、このような事情に鑑みてなされたものであり、入力された図形に応じてアルゴリズムを適切に切り替え、レンダリング処理に係るデータ処理を行えるようにすることを目的とする。
【課題を解決するための手段】
【０００６】
本発明の画像処理装置は、レンダリング処理を行う画像処理装置であって、オブジェクトの情報を入力する入力手段と、前記入力手段より入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類手段と、前記分類手段により分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理手段とを有することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、入力されたオブジェクトの情報に基づいて処理手順を切り替えることで、オブジェクトに応じた適切な処理手順で処理を行ってエッジ情報を生成することができる。これにより、オブジェクトに応じた適切な処理手順でレンダリング処理に係るデータ処理を実行することができ、レンダリング処理の高速化を実現することができる。
【図面の簡単な説明】
【０００８】
【図１】レンダリング処理の一例を示すフローチャートである。
【図２】スキャンラインによるエッジ情報抽出処理を説明するための図である。
【図３】エッジ情報抽出処理の詳細を示すフローチャートである。
【図４】プリントジョブにおけるデータ処理時間の変化の一例を示す図である。
【図５】本発明の一実施形態に係る画像処理装置の構成例を示す図である。
【図６】本実施形態に係る画像処理装置の動作例を示すフローチャートである。
【図７】第１の実施例におけるタイルベースのエッジ検出処理を説明するための図である。
【図８】第１の実施例におけるエッジ情報抽出処理を示すフローチャートである。
【図９】第１の実施例におけるエッジ情報を格納したデータ構造体を示す図である。
【図１０】第２の実施例における図形種識別情報を説明するための図である。
【図１１】第２の実施例におけるエッジ情報抽出処理の流れを示す図である。
【図１２】第２の実施例における図形（ＩＤ−２系）の例を示す図である。
【図１３】第２の実施例におけるエッジ情報抽出処理の一例を示すフローチャートである。
【図１４】第２の実施例における図形（ＩＤ−３系）の例を示す図である。
【図１５】第２の実施例におけるエッジ情報抽出処理の一例を示すフローチャートである。
【図１６】第２の実施例を適用した場合の処理時間の一例を示す図である。
【図１７】各アルゴリズムでのエッジ情報抽出処理の速度特性を示す図である。
【図１８】第３の実施例における特性データベースに格納するデータ例を示す図である。
【図１９】プリントシステムの構成例を示す図である。
【図２０】第３の実施例における図形種解析等の処理を説明するための図である。
【図２１】第３の実施例における区間幅拡張を説明するための図である。
【図２２】第３の実施例における図形種解析等の処理の一例を示すフローチャートである。
【図２３】第３の実施例における区間幅内にあるオブジェクトを説明する図である。
【図２４】第３の実施例におけるエッジ情報抽出処理の流れを示す図である。
【図２５】本実施形態における画像処理装置を実現可能なコンピュータ機能を示す図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を図面に基づいて説明する。
まず、レンダリング処理について説明する。
図１は、レンダリング処理の一例を示すフローチャートであり、図形入力からエッジ情報を抽出する様子を示している。図示のようにレンダリング処理を行うレンダリング処理部（レンダラー）に入力される図形の種類は多様に存在している。図１に示す処理では、入力された図形の座標情報等からエッジ検出処理によりエッジ（輪郭）を検出して、図形を構成する線情報（エッジ情報）を生成する。例えば、図２は三角形の図形からエッジを抽出する様子を示しており、三角形に対してスキャンライン（水平線）が交差している状態であって、矢印で示すように２つのエッジが検出されている例を示している。この処理の概要を簡単に述べると、まず、入力された図形データをＹ方向にソートして、次にソートされた図形データに順次アクセスしＸ座標のデータ列を集める。このときに、Ｘ座標値の小さいものから大きいものへ昇順にデータがアクセスできるようにデータの参照テーブル等を作成する。画像を形成するための処理では、Ｘ方向スキャンを水平方向へ走らせ、これを縦方向（Ｙ方向）へと繰り返すことで該図形のエッジ情報を抽出していく。
【００１０】
図３は、入力された図形の座標情報等からエッジ情報を抽出する処理の詳細を説明したフローチャートである。処理を開始すると、レンダリング処理部は、まず、ステップＳ１１にて、入力されたデータをＹ方向にソートしデータを格納して、次にステップＳ１２にて、スキャンラインのＹ方向へのループ処理を開始する。ステップＳ１３にて、レンダリング処理部は、現在のスキャンラインにかかる図形データを拾い出し、かつ、スキャンライン上に存在するエッジ情報（カレントのエッジデータリスト）を更新する必要があるかないかを判断する。判断の結果、更新の必要がなければステップＳ１７へ進み、更新の必要があればステップＳ１４へ進む。ステップＳ１４にて、レンダリング処理部は、カレントのエッジデータリストに対するエッジの追加又は削除の判断を行う。新たに図形の輪郭にスキャンラインがかかった場合等、エッジを追加する場合には、レンダリング処理部は、ステップＳ１５にて追加すべきデータをＸ方向へ昇順となるように追加する。ここで追加されたデータはノードと呼ばれ、それぞれがリスト上に連結される。一方、図形の輪郭からスキャンラインが外れた場合にはステップＳ１６に進み、レンダリング処理部は、エッジデータリストから該当するエッジデータを適宜、削除する。
【００１１】
ステップＳ１７より、レンダリング処理部は、現在のスキャンラインにおけるＸ方向のエッジ情報を抽出するためのループ処理を行う。ステップＳ１８にて、レンダリング処理部は、エッジデータリスト上の各ノードに順次アクセスしていく。エッジの情報はカレント（Ｙ値）のスキャンラインにおけるデータ値（ＤＡ値）を線分の傾き等の情報から更新するよう構成されており、該データの更新処理はステップＳ１９にて実行される。続いて、レンダリング処理部は、ステップＳ２０にて、Ｘ方向のループ処理のためのカウンタ減算処理を行い、ステップＳ２１にてＸ方向ループ処理の終了の有無を判定する。判定の結果、Ｘ方向ループ処理を終了しない場合にはステップＳ１７へ戻り、Ｘ方向ループ処理を終了する場合にはステップＳ２２へ進む。そして、レンダリング処理部は、ステップＳ２２にてＹ方向ループ処理の終了の有無を判定し、終了しない場合にはステップＳ１２へ戻り、終了する場合には処理を終了する。
【００１２】
このようにステップＳ１７からステップＳ２１まではＸ方向のループ処理であり、またステップＳ１２からステップＳ２２まではＹ方向のループ処理であり、これら二重のループ処理によって平面上の図形の輪郭情報（エッジ情報）を抽出する。
【００１３】
図４は、前述したレンダリング処理を含むプリントジョブにおけるデータ処理時間の変化の一例を示したグラフである。図４において、縦軸は処理時間（ミリ秒）を示しており、横軸はプリントジョブのページを示している。図４に示す例では、１ページ目は処理を完了するために約４００ミリ秒かかっており、２ページ目は約５５０ミリ秒の時間を消費する。図４において、三角点で変化している線グラフはジョブに含まれる単純図形の数（相対値）を示しており、丸点で変化している線グラフは、単純図形以外（便宜上、ここでは複雑図形と呼ぶことにする）の数（相対値）を示している。複数ページにわたるプリントジョブを分析すると、矩形や三角など単純な図形が含まれている場合と、それ以外の複雑な図形（多角形等）が含まれている場合とでデータ処理の時間に違いがあることが図４から読み取れる。
【００１４】
ここで、一般的にプリントジョブには単純図形がより多く含まれる傾向があるので、プリント処理の平均時間を向上させるためには、単純図形を如何に効率良く高速に処理できるかということが重要である。しかし、前述したレンダリング処理では図１に示したように図形の種類によらずデータ処理を行うための処理手順（アルゴリズム）は固定されている。そこで、本実施形態では、入力された図形（入力オブジェクト）の種類に応じてデータの処理手順（アルゴリズム）を切り替えて、レンダリング処理に係るエッジ情報生成処理を行う。
【００１５】
図５は、本発明の一実施形態に係る画像処理装置の構成例を示すブロック図である。本実施形態に係る画像処理装置は、図形データを処理するレンダリング処理を行う画像処理装置であって、入力部１１、分類部１２、及びエッジ抽出処理部１３を有し、入力オブジェクトの座標情報等に基づいて図形の輪郭情報であるエッジ情報を生成する。入力部１１より入力された図形（入力オブジェクト）は、分類部１２での図形種別判定処理により例えば単純図形（第１の図形種）又は複雑図形（第２の図形種）に分類される。エッジ抽出処理部１３は、エッジ検出処理部１４及びエッジ情報生成部１５を有し、分類部１２で分類した結果に応じてエッジトレースアルゴリズムを切り替えてエッジ検出を行いエッジ情報を生成する。例えば、エッジ検出処理部１４は、単純図形（第１の図形種）と分類されたオブジェクトについてはタイル処理による（タイルベースの）エッジ検出処理を行い、複雑図形（第２の図形種）については前述したスキャンラインによるエッジ検出処理を行う。エッジ情報生成部１５は、エッジ検出処理部１４での処理結果に基づいてエッジ情報を生成する。
【００１６】
図６は、本実施形態に係る画像処理装置の動作例を示すフローチャートであり、図形入力からエッジ情報を抽出する様子を示している。まず、分類部１２は、図形種別判定処理を行い、入力部１１より入力された図形（入力オブジェクト）を単純図形（第１の図形種）と、それ以外の複雑図形（第２の図形種）とに切り分ける（ｐ１１）。そして、エッジ抽出処理部１３のエッジ検出処理部１４は、複雑図形に対しては前述したスキャンラインによるエッジ検出処理を行い（ｐ１２）、単純図形に対してはタイル処理によるエッジ検出処理を行う（ｐ１３）。これらのエッジ検出処理の処理結果に基づいて、エッジ抽出処理部１３のエッジ情報生成部１５は、入力オブジェクトに係るエッジ情報を生成する。
【００１７】
このように本実施形態に係る画像処理装置では、入力された図形（オブジェクト）に応じて処理手順を切り替えてエッジ検出を行い、その処理結果に基づいてエッジ情報を生成する。これにより、入力された図形に応じた適切な処理手順でレンダリング処理に係るデータ処理を行うことができ、レンダリング処理の高速化を図ることができる。
【００１８】
以下、本実施形態におけるタイル処理によるエッジ検出処理について説明する。なお、以下の説明では、各タイルは１６×１６のピクセル（画素）で構成されているものとする。
【００１９】
（第１の実施例）
以下、タイル処理によるエッジ検出処理の第１の実施例について説明する。
図７は、第１の実施例におけるタイル処理によるエッジ検出処理の概要を説明するための図である。図７に示すような点ＡＢＣを頂点とする三角形を考えると、該三角形の外郭の領域は図示した縦のタイル（図中左端の１から１０までの番号が振られているタイル）の範囲に含まれる。三角形の辺の数は３つであるので、エッジ抽出処理部１３は、各辺毎にエッジ情報を抽出する処理を行う。図７に示した例では、点Ａから点Ｂまでの辺ＡＢに対しては、２つの点Ａ及び点Ｂがそれぞれ含まれるタイルを除いた１１個のタイルにおいて、エッジ情報の抽出がそれぞれ行われる。該１１個のタイルでは、各矩形領域（タイル）において点Ａと点Ｂとを結ぶ直線（辺ＡＢ）の一つだけがかかっている状態である。つまり、タイルを構成する矩形の４つの辺のいずれかが、点Ａと点Ｂとを結ぶ直線と交差している。このとき、タイルと、点Ａ及び点Ｂを結ぶ直線との交点は２点となる。第１の実施例では、エッジ抽出処理部１３は、この２点（２つの交点）の座標データに基づいてエッジ情報（エッジデータ）を生成する。なお、図７中の三角形を構成するその他の二辺、つまり、点Ａと点Ｃとを結ぶ辺ＡＣ及び点Ｂと点Ｃとを結ぶ辺ＢＣのそれぞれについてもエッジ抽出処理を行うが、その手順は辺ＡＢに対する処理と同様である。また、頂点の位置や辺の角度によっては、２つの辺（例えば、辺ＡＢと辺ＡＣ）が同一タイルにかかる場合もあり得るが、その場合でも各辺におけるエッジ抽出処理はそれぞれ別に進められ適宜マージされる。
【００２０】
図８は、第１の実施例におけるエッジ情報抽出処理の一例を示すフローチャートである。処理を開始すると、エッジ抽出処理部１３は、まずステップＳ７１にて、図形（オブジェクト）の数だけループ処理を行うよう設定する。なお、本実施例で対象とする図形は、図形を構成する辺の数が３又は４である図形（すなわち、三角形又は四角形）のみであり、分類部１２での処理により他の図形とは切り分けがなされているものとする。ステップＳ７２にて、エッジ抽出処理部１３は、エッジ抽出処理を行うある１つのオブジェクトのパス数（辺数３又は４）だけループ処理を行うように設定する。ステップＳ７３にて、エッジ抽出処理部１３は、レンダリング空間における対象のパス（辺）におけるタイル（対象のパスがかかるタイル）の数を計算により求め、そのタイルの数だけループ処理を行うよう設定する。ステップＳ７４にて、エッジ抽出処理部１３は、対象のパスとタイルを構成する辺とが交差する２点のデータの組み合わせからデータベースを検索して一意にデータを入手することで、レンダリング空間の各タイルにおけるエッジ情報（エッジデータ）を取得する。なお、このデータベースについては後述する。ステップＳ７５にて、エッジ抽出処理部１３は、ステップＳ７４において取得したエッジ情報をタイル上のデータとして登録（セット）する。ステップＳ７４及びステップＳ７５の処理を対象のパス（辺）におけるタイルの数だけ繰り返す。そして、ステップＳ７６、及びステップＳ７７により必要な回数分のループ処理を行うことで、エッジ抽出処理部１３は、該当するすべての図形（オブジェクト）のエッジ情報を抽出する。
【００２１】
以上、説明したように図８に示したフローチャートに沿って処理を行うと、図形毎に独立して（外接矩形のユニットで）タイルデータが生成されていく。タイルデータが生成されるタイル群は、相当数が生成されると適時マージ（合成）される。タイルデータが生成されたタイルをマージする際には、ページをバンド（例えば１バンド＝１６０ラインの固定幅）の単位で区切る。そして、ページ上部のバンドからページ下部へむけて、処理が必要なバンド（この時点でタイルが存在するバンドのみが処理の対象）を選択しながら順次処理を進める。合成処理を開始した時点で生成されているタイルを対象に、各バンドにかかるタイルを適宜、選択しながら合成処理を行う。最終的には１ページ分のすべてのオブジェクトが処理され、不図示のスプーラー（一時保存領域）へ全タイルデータがストアされる。該ストアされた１ページ分のタイルデータには、図形の輪郭情報（エッジ情報）や描画色等が記録されており、これら情報を適時参照しながらビデオフレーム等へ描画処理（ピクセル出力）を行うよう構成されている。該描画処理は不図示のピクセル展開処理部で実行される。
【００２２】
図９は、図８に示したステップＳ７４において参照するデータベースを説明するための図である。前述したように本実施例において、タイルは１６×１６ピクセルを前提としており、１６×１６ピクセルのタイルを考えると、この矩形を横切る直線のパターンは有限であって、そのパターンは矩形の辺と直線との交点の組み合わせパターンですべて表現できる。例えば、矩形を横切る直線の例の一つとしてタイル矩形の左上側に斜め４５度で小さく横切る直線を考える（該直線は図示のように３つのピクセルで表現される）。図９（Ａ）は、この様子を表しており、タイルの左上側のみを図示している。タイルを横切る辺は、図９（Ａ）において左下の点から右上に向けて貫通している状態とも言える。この例の場合には、左下の交点の座標は（３，１）、右上の交点の座標は（１，３）となっている。
【００２３】
このとき、タイルの内部のエッジは、スキャンライン（水平方向）の単位で考えると、３つのエッジ（境界）が存在していることになる。これをタイル内部データの表現として、タイル最左上の点を基準点とするオフセット値で表すこととする。図９（Ａ）に示す例では、右側に記載されている「＋２」という値がオフセット値を示している。次のスキャンラインにおけるエッジデータは、前のスキャンラインでのエッジデータ（ここでは＋２の位置）に対する相対的な値（相対オフセット値）として示す。図上、左側にエッジが存在する場合にはマイナスの値をとり、右側にエッジが存在する場合にはプラスの値をとるように定義する。図９（Ａ）に示した例では、それぞれ左側にエッジが存在しているので「−１」、「−１」というデータ列になる。
【００２４】
タイルを横切る直線のパターンは有限であり、縦１６×横１６ピクセルのタイルの場合、交差する直線とタイルを構成する矩形の辺との交点の組み合わせ（２交点の場合の数）は、２９４４（＝１６×（１６＋１５＋１５）×４）通りの組み合わせが存在する。本実施例ではエッジ情報を保持するデータベースは、図９（Ｂ）に示すように構成される。図９（Ｂ）に示すエントリーテーブルは、１６×１６ピクセルのタイルにおいて、タイルに交差する直線とタイルを構成する矩形の辺との交点の組み合わせに対応し、２９９４個のエントリを持っている。該エントリーテーブルから先には、それぞれの場合に応じたエッジ情報を格納した配列テーブルがあり、該エントリーテーブルを経由してエッジ情報を得ることができるようになっている。該エッジ情報は図９（Ａ）で述べたオフセット値を集めたデータ列で表現されている。
【００２５】
以上説明したように、第１の実施例では、図形を構成する辺数が３又は４である単純図形である場合には、タイル処理によるエッジ検出処理を行う。具体的には、エッジ抽出処理部１３は、入力された図形を構成する辺をタイル上の座標におき、次にタイルを構成する矩形辺と交差する点を求める。そして、求めた交差する点の座標データの組み合わせに基づいて、該当するエッジ情報を格納したデータベースから検索して取得することでエッジ情報を生成する。これにより、エッジ情報を生成する際の演算量を効率良く抑制することができるようになり、処理速度を効果的に向上させることができる。
【００２６】
（第２の実施例）
次に、第２の実施例について説明する。
前述した第１の実施例では、分類部１２での図形種別判定処理により入力された図形（入力オブジェクト）が、何であるかを検査し、その結果、図形が三角形又は四角形である場合にタイル処理によるエッジ抽出処理を行っていた。第２の実施例では、図形オブジェクトの個々に対して図形の種類を表す「図形種識別情報」を付加するようにして、星型等、その他の図形（但し、直線で構成される図形）に対してもタイル処理によるエッジ抽出処理を行えるようにする。さらには、図形の特性（例えば対称性等の特性）を利用することで処理の高速化を図れるものについては個別に処理手続き（アルゴリズム）を用意し、それぞれの図形に応じた最善の処理手順によってエッジ情報の生成を行う。
【００２７】
図１０に示すように図形等を扱うアプリケーションソフトウェアでは、プルダウンメニュー等からドキュメントに挿入する図形種（図形の種類、例えば三角形、四角形、台形、平行四辺形等）を選択できるようになっている。アプリケーション側から各図形に対して図形の種類を表す「図形種識別情報」を割り当てられるよう構成することで、印刷プリントジョブの中にある図形のデータそれぞれに対して該図形種識別情報を付加する。図１０に示す例では、図形種識別情報として、三角形にＩＤ−１が割り当てられ、同様に、星型にＩＤ−２、回転された十字型の多角形にＩＤ−３がそれぞれ割り当てられている。
【００２８】
図１１は、第２の実施例におけるエッジ情報抽出処理の流れを示す図である。まず、エッジ抽出処理部１３は、オブジェクト（図形）が入力されると不図示のカウンタにより入力されたオブジェクト（図形）の総数Ｎを積算する。そして、エッジ抽出処理部１３は、オブジェクト（図形）が入力されると逐次、又は１ページ内（又は所定の処理単位内）の図形すべての入力が完了した時点で、積算された総数Ｎと予め設定された閾値Ｔ１を比較する（ｐ１１１１）。比較の結果、オブジェクト総数Ｎが閾値Ｔ１より大きい場合（Ｎ＞Ｔ１）には、エッジ抽出処理部１３は、前述のスキャンラインによるエッジ検出処理（図２参照）を行い、エッジ情報を生成する。
【００２９】
一方、オブジェクト総数Ｎが閾値Ｔ１以下である場合（Ｎ≦Ｔ１）には、エッジ抽出処理部１３は、各オブジェクト（図形）に付加されている図形種識別情報に応じて処理手法を切り替えてタイル処理によるエッジ検出処理を行い、エッジ情報を生成する。例えば、図形種識別情報がＩＤ−１である場合には、エッジ抽出処理部１３は、三角形に対する処理を行い、第１の実施例のような処理手順でエッジ情報抽出処理を行う。また、例えば図形種識別情報としてＩＤ−２が付与されている図形の場合（本実施例中の例では星型の場合等）には、エッジ抽出処理部１３は、三角形の場合とは別の処理手順でエッジ情報抽出処理を行う。図形種識別情報としてＩＤ−２が付与されている図形に対する処理手続き（アルゴリズム）は、水平軸又は垂直軸に関して対称性を有する図形に適しているものであり、その処理の詳細は後述する。また、例えば図形種識別情報としてＩＤ−３が付与されている図形の場合（回転や変形が施されている多角形等）には、エッジ抽出処理部１３は、三角形（ＩＤ−１系）や対称性を持つ図形（ＩＤ−２系）の場合とは異なる処理手順でエッジ情報抽出処理を行う。図形種識別情報としてＩＤ−３が付与されている図形に対する処理手続き（アルゴリズム）の詳細は後述する。
【００３０】
以下、第２の実施例での、図形種識別情報としてＩＤ−２が付与されている図形に係るエッジ情報抽出処理について説明する。
図１２は、図形種識別情報としてＩＤ−２が付与されている図形の一例を示しており、ここでは星型を一例として示している。星型の図形は、縦の中心軸に対して左右の形（輪郭）が線対称となっている。このように図形が線対称であり、かつ、対称軸が水平又は垂直である場合には、まず対称軸で分割した一方の側の輪郭に対してのみエッジ情報抽出処理を行う。そして対称軸に関して他方の側の輪郭に対しては、一方の側に対するエッジ情報抽出処理で得られたエッジデータを反転することで残りのエッジデータを生成することができる。この処理を効率的に実行するためにはレンダリング処理で用いるタイルの境界線と図形の対称軸とを一致させておく必要がある。本来、描画するオブジェクトはレンダリングする座標位置が指定されており、またレンダリング座標とタイルの位置関係は独立に決められているため、図形の対称軸とタイルの境界は一般的に一致しない。これを一致させるため、本実施例では一時的に図形の座標位置を相対座標空間上に移しエッジ情報抽出処理を実行した後にオリジナルの座標に再度移動させるよう構成している。
【００３１】
図１３は、第２の実施例における図形種識別情報としてＩＤ−２が付与されている図形に係るエッジ情報抽出処理の一例を示すフローチャートである。
エッジ抽出処理部１３は、ステップＳ１３０にて入力された図形の座標データを、ステップＳ１３１にて相対座標空間での座標データに変換する。相対座標空間は、前述したように、対象とする図形の中心軸（星型の場合は図１２において矢印で指す中央のライン）とタイルの境界線とが合致するように構成した座標空間である。例えば、図形の中心軸と外郭線とが交差する点（星型であれば例えば図中の最上にある頂点）を、タイルを構成する矩形の４つの頂点の内のいずれか一つ（図中のタイル境界を示す縦線と横線がクロスする十字の中心）に合致させるようにした座標空間である。次に、エッジ抽出処理部１３は、ステップＳ１３２にて、対象とする図形を取り囲む矩形領域を生成し、ステップＳ１３３にて、該矩形領域が包含されるように該矩形領域を含む領域に対してタイルを配置する。対象とする図形を構成する辺（セグメントと呼ぶ）のうち、中心軸で分割した一方の側のセグメントに対してエッジ検出の処理を行うので、エッジ抽出処理部１３は、ステップＳ１３４にて対象の辺の数をカウントする（セグメントの総数を数えてセットする）。エッジ抽出処理部１３は、ステップＳ１３５にてループ処理を開始して、ステップＳ１３６にて対象の辺に関するエッジ情報を抽出する。ステップＳ１３４において設定した対象の辺の数だけ、このループ処理を行うことにより、エッジ抽出処理部１３は、順次対象の辺に関するエッジ情報を抽出する。なお、ステップＳ１３６の処理では、第１の実施例における処理と同様にして、各辺がタイル境界を横切る交点の情報からエッジ情報を生成する。前述した一連のループ処理後は、中心軸で分割した図形の一方の側のセグメントについてエッジ情報の抽出が完了している状態である。エッジ抽出処理部１３は、ステップＳ１３７にて、一方の側のエッジ情報に基づいて中心軸に対して他方の側のエッジ情報を生成した後、ステップＳ１３８にて、対象とする図形のエッジ情報を絶対座標系（もとの座標位置）に戻し処理を完了する。
【００３２】
以下、第２の実施例での、図形種識別情報としてＩＤ−３が付与されている図形に係るエッジ情報抽出処理について説明する。
図１４は、図形種識別情報としてＩＤ−３が付与されている図形の一例を示しており、ここでは回転された星型を一例として示している。星型の図形は、対称性を持つ図形であるが、図１４に示すように回転された場合には対称軸も回転するため、図形の対称軸とタイル境界に係る縦又は横のラインとは一致しなくなる。このため、前述した図形種識別情報としてＩＤ−２が付与されている図形に対する処理のように、対称軸について一方の側のエッジデータを反転して他方の側のエッジデータを生成するという処理は実行できない。よって、図形種識別情報としてＩＤ−３が付与されている図形である場合には、エッジ抽出処理部１３は、図形を構成する輪郭（エッジ）すべてのエッジ情報の生成を順次行う。具体的には、図形のエッジを抽出するために図形の座標位置を相対座標空間上へマッピングしてエッジ情報抽出処理を実行した後にオリジナルの座標に再度移動させる。相対座標空間上へのマッピングでは、対象とする図形（本例では回転した星型）を取り囲み、かつ相対座標空間における水平軸に平行な辺及び垂直軸に平行な辺からなる外接矩形を作成する。そして、該外接矩形の左上の頂点を、タイルを構成する矩形の４つの頂点の内のいずれか一つ（タイル境界を示す縦線と横線がクロスする十字の中心）に合致させる。
【００３３】
図１５は、第２の実施例における図形種識別情報としてＩＤ−３が付与されている図形に係るエッジ情報抽出処理の一例を示すフローチャートである。
エッジ抽出処理部１３は、ステップＳ１４０にて入力された図形の座標データを、ステップＳ１４１にて相対座標空間での座標データに変換する。相対座標空間は、タイルで構成されており、前述したように図形に外接する相対座標空間の水平軸に平行な辺及び垂直軸に平行な辺を持つ矩形における左上の頂点を、タイル境界を示す縦線と横線がクロスするいずれかの点に合致させるようにした座標空間である。次に、エッジ抽出処理部１３は、ステップＳ１４２にて、対象とする図形を取り囲む矩形領域を生成し、ステップＳ１４３にて、該矩形領域が包含されるように該矩形領域を含む領域に対してタイルを配置する。続いて、エッジ抽出処理部１３は、ステップＳ１４４にて、対象とする図形を構成する辺（セグメントと呼ぶ）の数をカウントする（セグメントの総数を数えてセットする）。エッジ抽出処理部１３は、ステップＳ１４５にてループ処理を開始して、ステップＳ１４６にて対象の辺に関するエッジ情報を抽出する。このループ処理を行うことにより、エッジ抽出処理部１３は、順次対象の辺に関するエッジ情報を抽出する。ステップＳ１４５において設定した対象の辺の数だけ、このループ処理を行うことにより、エッジ抽出処理部１３は、順次対象の辺に関するエッジ情報を抽出する。なお、ステップＳ１４６の処理では、第１の実施例における処理と同様にして、各辺がタイル境界を横切る交点の情報からエッジ情報を生成する。最後に、エッジ抽出処理部１３は、ステップＳ１３７にて、対象とする図形のエッジ情報を絶対座標系（もとの座標位置）に戻し処理を完了する。
【００３４】
図１６は、第２の実施例を適用した場合のプリントジョブにおける各ページの処理時間の分布の一例を示したグラフである。図１６において、横軸はジョブページ（１から１６ページまで）を示しており、縦軸はそれぞれのページにおける処理時間（ミリ秒）を示している。図中、各折線データが、エッジ処理時間の変化を示している。実線はスキャンラインによるエッジ検出処理のみで処理を実行した場合の処理時間を示しており、ジョブ全体を通しての平均処理速度は１７０ミリ秒である。一方、点線は入力された図形のうち三角形に対してのみタイル処理によるエッジ検出処理を行い、その他についてはスキャンラインによるエッジ検出処理を実施した場合の処理時間を示している。図中に示される点線より明らかなように、２ページ、４ページ、８ページ、１２ページの処理で高速化が実現されており、またジョブ全体を通しての平均処理速度は１６５ミリ秒である。さらに、破線は入力された図形のうち三角形（ＩＤ−１系の図形）や星型等（ＩＤ−２系の対称図形）に対してタイル処理によるエッジ検出処理を行い、その他についてはスキャンラインによるエッジ検出処理を実施した場合の処理時間を示している。図中に示される破線より明らかなように、８ページ、１２ページ、１３ページ、１６ページの処理でさらなる高速化が実現されており、またジョブ全体を通しての平均処理速度は１６０ミリ秒である。
【００３５】
以上説明したように、第２の実施例では、ジョブに含まれる多種多様な図形に対して、それぞれ最適な処理手法を用意し、図形に応じて適切に切り替えて各処理を実行することにより全体のスループットを向上させることができる。
【００３６】
（第３の実施例）
前述したように、第１の実施例や第２の実施例のような処理を適用することで、エッジ情報生成処理に関する処理の高速化を実現することができる。いずれの場合にも処理の高速化の手段としてタイル処理によるエッジ検出処理を用いているが、これらの結果は、前述した例のようにオブジェクトの数が少ないという条件下で得られると考えられる。逆に、オブジェクトの数が極めて多い場合には、スキャンラインによるエッジ検出処理に比べてタイル処理によるエッジ検出処理の方が遅くなる場合があると考えられる。また、プリントジョブを生成する際に、アプリケーションソフト側が、各オブジェクトに対する図形種判定のための図形種識別情報の付与に対応できないケースも生じ得る。
【００３７】
そこで、第３の実施例では、オブジェクトの数に応じて変化する各アルゴリズムにおける速度（処理時間）の変化特性を、特性情報等を記録する特性データベース（特性ＤＢ）へ記録しておく。例えば、各アルゴリズム（スキャンライン系とタイルベース系）における速度の変化特性（例えば処理速度が逆転するオブェクト数の情報等）を特性ＤＢへ記録しておく。そして、該特性ＤＢに記録されている情報に基づいて処理の切り替えを行うようにする。また、アプリケーションソフト側が図形種識別情報を付加しない場合でも、プリンタドライバ側で図形データを解析して適宜図形種識別情報を付加できるようにする。
【００３８】
図１７は、各アルゴリズムでのエッジ情報抽出処理の速度特性を示したグラフであり、横軸がオブジェクト数を示しており、縦軸が処理時間を示している。スキャンライン系処理及びタイルベース系処理のいずれの場合にもオブジェクトの数が増えると、それに伴って処理時間が増加するという傾向がある。図１７において、（ａ）はスキャンライン系処理での特性を示しており、（ｂ）はタイルベース系処理（前述した第１の実施例におけるエッジ検出処理）の特性を示している。また、（ｃ）はスキャンライン系処理とタイルベース系処理との両方を使ったハイブリッド系の処理での特性を示している。以下、図１７に示す各グラフ特性の違いについて詳細に述べる。
【００３９】
図１７（ａ）に示されるように、スキャンライン系処理では、領域Ａ（オブジェクト数が少ない領域）では処理速度が遅い。しかし、オブジェクト数が増えてくると領域Ｂ（オブジェクト数が多い領域）では、オブジェクト数の増加に対する処理速度の低下が抑制される特性がある。これは、一つのスキャンライン上に多くの図形がかかってくるようなケースでは、ループ処理の効率が向上すること等が影響していると考えられる。一方で、図１７（ｂ）に示されるように、タイルベース系処理では、領域Ａ（オブジェクト数が少ない領域）では処理速度が速いが、オブジェクト数が増えてくると領域Ｂ（オブジェクト数が多い領域）では、処理速度の低下が顕著となってくる。これはタイルベース系処理では、各オブジェクトに対して独立に処理を行っているため、図形の数に比例して処理ステップ数が増加すること等が影響していると考えられる。
【００４０】
以上述べたように、スキャンライン系処理とタイルベース系処理とはそれぞれの領域において、逆の特性を有している。スキャンライン系処理及びタイルベース系処理の特性を調べて処理速度が逆転するオブジェクト数を取得し、そのオブジェクト数で処理を切り替えるようにすることで、互いの長所を引き出すことができる。図１７（ｃ）は、領域Ａではタイルベース系処理で処理を行い、領域Ｂではスキャンライン系処理で処理を行うように、分岐点（処理速度が逆転するオブジェクト数）にて処理を切り替える場合の特性を示したものである。
【００４１】
なお、オブジェクト数に応じた処理速度（処理時間）の変化特性は、各処理手順（アルゴリズム）に依存しているために各処理手順毎に特性を把握しなくてはならない。第２の実施例でいえば、図形種識別情報としてＩＤ−２が付与されている図形と、ＩＤ−３が付与されている図形との特性は、個々に違う特性を持っており、特にスキャンライン系のエッジ検出処理と速度が逆転するポイント（分岐点）は個々異なっている。
【００４２】
また、図形の大きさ等も処理時間の特性に影響を与える。第１の実施例では、図８の説明で述べたように図形毎にタイルデータが順に生成されていき、タイルデータが生成されるタイル群は、相当数が生成されると適時マージ（合成）されるよう構成されている。これらを処理する際にはページを固定の区間幅（バンド幅：例えば１バンド＝１６０ライン）の処理単位で区切って処理を進めている。第１の実施例における前提としては、多くの図形が固定の区間幅（例えば１６０ライン）の中に収まることを前提としていたが、指定される図形のサイズには制限がなく平均サイズが予め設定した区間幅を超えることも考えられる。図形のサイズが大きくなると特にスキャンラインによるエッジ検出処理特性に影響が出てくる。これはエッジ検出処理の特性（分岐点の変化）に影響を与える大きな要因の一つとなる。このことから本発明のより好適な実施態様としては図形サイズの違いも考慮した構成とすることが望ましい。第３の実施例では、２つの区間幅（１６０ライン、３２０ライン）を用意して、図形の平均サイズに応じて区間幅を適宜切り替えるようにする。
【００４３】
したがって、第３の実施例においてエッジ情報抽出処理における特性は、図１８に示すように、アルゴリズムの種類（本実施例では３種類）、及び図形の大きさ（本実施例では２種類）のそれぞれを掛け合わせた組み合わせ（合計６種類）の特性を測定する。そして、測定により得られた該特性に係る関連情報を特性ＤＢに格納しておき、格納されている情報に基づいて処理の切り替えを行う。図１８は、第３の実施例で用いる特性ＤＢに格納される特性データ（６種類）を説明するための図である。
【００４４】
図１９は、プリンタドライバを含めたプリントシステムの構成例を示すブロック図である。図１９においては、要素的特徴のみを示している。第３の実施例の説明における冒頭で述べたように、本例ではアプリケーションソフト側が図形種識別情報を付加しない場合でも、図形種に応じた処理の切り替えに対応できるようにプリンタドライバ側にて図形種解析処理を実行可能としている。図形の簡単なものは座標点の構成、位置関係からある程度の分類が可能である。なお、図形種解析処理を行うことにより処理時間は若干増加すると考えられるが、プリンタドライバは高速なホストＰＣ側で行われるためプリントシステム全体のスループットを考慮するとメリットは存在する。
【００４５】
各処理手順（アルゴリズム）における速度の変化特性に係る情報が格納される特性ＤＢ１９４は、プリンタドライバ１９１のモジュール内に存在している。アプリケーションから印刷が開始されると、プリンタドライバ１９１は、図形データ生成部１９２の出力情報を基にプリントジョブの生成を開始する。同時に、図形種解析部１９３は、各オブジェクトの図形種の解析処理を開始するとともに、該解析処理と平行して特性ＤＢ１９４にアクセスして各オブジェクト（図形）に対し図形種識別情報を付加していく。ここで図形種識別情報としてＩＤ−１が付与された図形は、第１の実施例で説明したようなタイルベースのエッジ情報抽出処理が割り当てられることとなる。また、図形種識別情報としてＩＤ−２が付与された図形は、第２の実施例で説明した図１３に示したような処理手順でのタイルベースのエッジ情報抽出処理が割り当てられることとなる。さらに、図形種識別情報としてＩＤ−３が付与された図形は、第２の実施例で説明した図１５に示したような処理手順でのタイルベースのエッジ情報抽出処理が割り当てられることとなる。
【００４６】
前述したＩＤ−１、ＩＤ−２、ＩＤ−３の図形種識別情報は、ＰＤＬ（ページ記述言語）データ内の（各オブジェクト毎に割り当てられている）拡張情報領域を適宜拡張して格納される。なお、ＰＤＬデータ内のオブジェクトに対してはデフォルトでは拡張情報は存在していない状態であり、該拡張情報がない図形等に関してはスキャンラインによるエッジ情報抽出処理が実行されることとなる。
【００４７】
以上のように、プリンタドライバ１９１からは適宜図形種識別情報が付加されたＰＤＬデータが生成され、該ＰＤＬデータはプリントスプーラー等の機能部１９５を経由してプリンタ装置１９６に転送される。プリンタ装置１９６では、ＰＤＬ解析部１９７がデータの解析処理を行い、ＰＤＬデータ中、図形等のオブジェクトに対しては画像形成処理が起動されて、その処理において図形のエッジ情報が生成される。このとき、ＰＤＬ解析部１９７及び機能部１９８は、各オブジェクトに対して拡張情報の有無を確認する。その結果、拡張情報が存在する場合は、その中に格納されている図形種識別情報（ＩＤ−１，ＩＤ−２，ＩＤ−３のいずれかであるか）を読み取り、読み取った図形種識別情報に基づいて、実行すべきエッジ抽出処理の選択を行う。そして、選択されたエッジ抽出処理に応じてエッジ抽出処理部１９９により処理が実行される。プリンタ装置１９６のコントローラは抽出されたエッジ情報に基づきイメージを生成し、プリンタ装置１９６のプリントエンジンは、生成されたイメージに基づき用紙にプリントを行う。
【００４８】
以下、図２０〜図２４を参照して、第３の実施例における各図形に関するその他の処理について説明する。
図２０は、第３の実施例における図形種解析等の処理を説明するための図である。図２０に示すように、プリンタドライバ内ではＧＤＩ（グラフィックスインターフェース）からの描画命令に基づいてＰＤＬの生成が行われる。その過程で図形種解析処理が行われて、図形に係る統計情報が取得される。この統計情報は、区間（ページ上の各バンド）毎に集計され、各区間における図形種別の個数及びその平均サイズ等が含まれる。ページにおける描画区間の幅は、図２１に示すようにデフォルトでは１６０ラインとしているが、大きな図形が特定バンドに多く存在し該図形サイズの平均サイズが１６０ライン分よりも大きくなる場合には区間幅を拡張するよう構成されている。第３の実施例では、区間幅を拡張した場合のサイズを３２０ラインとしている。また、図形種毎に平均サイズを測定するため、各区間幅に関する情報は図形種毎に独立して管理する。図２０に示した例で説明すると、あるジョブを解析した時の統計情報として、ＩＤ−１系のオブジェクト数が５２００個、ＩＤ−２系のオブジェクト数が３２００個、ＩＤ−３系のオブジェクト数が２１００個、その他が６２００個という情報が取得されたとする。区間幅を各ＩＤ毎にみると、ＩＤ−２とＩＤ−３において一部区間拡張がされている。例えば、ＩＤ−２系に係る統計情報において、ある区間（バンド）において１３００個のオブジェクトが存在し、かつ、該オブジェクト（図形）の平均サイズが２４２であると、該区間については区間拡張を行い、区間幅は３２０ラインとされる。特性ＤＢに対するＩＤ−２系の特性（分岐点の情報＝特性ＤＢでは閾値Ｔｘ）の問い合わせのために平均サイズの情報も利用する。図２０に示した例での特性ＤＢでは、ＩＤ−２系の特性において区間幅３２０ラインの場合の閾値は２４００と記録されている。したがって、該区間幅３２０ラインに分布しているＩＤ−２系の図形についてエッジ情報抽出処理を行う場合には、第２の実施例で説明したようなタイルベースのエッジ情報抽出処理を実行すべきことが判明する。
【００４９】
図２２は、第３の実施例における図形種解析等の処理の一例を示すフローチャートである。ステップＳ２２１は、図形種の解析処理のエントリであり、このステップＳ２２１では、初期化処理等が行われる。ステップＳ２２２にて、オブジェクトリストが生成され、ＰＤＬの情報を受けてグラフィックスにおけるパス情報、座標値、又はテキストコード等、各オブジェクトデータの蓄積が行われる。ステップＳ２２３にて、処理単位（処理ページ）におけるオブジェクト数Ｎの積算（総数のカウント）が行われる。ステップＳ２２４にて、オブジェクト数Ｎと閾値Ｓとが比較される。比較の結果、オブジェクト数Ｎが閾値Ｓより多ければステップＳ２３１へ分岐し、スキャンラインによるエッジ抽出処理を実行した後に呼び出し側モジュールへ復帰する。一方、オブジェクト数Ｎが閾値Ｓ以下であればステップＳ２２５へ分岐し、ステップＳ２２５にて、詳細調査の処理が開始される。ステップＳ２２６にて、各区間の検査が行われる。ステップＳ２２７では該当する区間（つまり、問題がありそうな区間＝オブジェクトが沢山存在する区間（バンド）等を意味する）において存在する図形のそれぞれにおいて平均のオブジェクトサイズを計算する。個々のオブジェクトサイズの例としては外接矩形の長辺の長さ等である。また、ある区間における平均オブジェクトサイズとは、図形のオブジェクトサイズの平均値である。次に、ステップＳ２２８にて、各バンドに対して該区域内に存在する図形オブジェクトの平均サイズが算出される。該区域内に存在する図形オブジェクトの算出方法に関しては図２３を用いて後述する。ステップＳ２２９にて、算出された平均オブジェクトサイズと閾値Ｔｘが比較され、平均オブジェクトサイズが閾値Ｔｘより大きい場合にはステップＳ２３０へ分岐し、該当部分の区間幅を拡張する。ここで、閾値Ｔｘは、例えば特性ＤＢより取得される。一方、ステップＳ２２９での比較の結果、平均オブジェクトのサイズが閾値Ｔｘ以下の場合には、区間幅の拡張は行わずに呼び出し側モジュールへ復帰する。
【００５０】
図２３は、区間幅が拡張された場合の様子を説明するための図である。図中、区間１１は現検査対象区間となっている区間である。区間１１は、図にあるように上ラインと下ラインに挟まれた区間であって、その幅は初期値として１６０ラインで定義されていている。この例では、この区間に関係している図形のサイズの平均を計算した結果、平均サイズが幅１６０ラインを超えることが判明したため、区間１１の幅を拡張して３２０ラインとしている。このとき、区間１２は区間１１によってオーバーライドされる。この結果、該ページにおける区間の定義は、区間１、２、…１０、１１、１３となる。なお、図中、検査の対象となるオブジェクトは、区間１１内に存在する図形、及び区間１１における下ラインにかかっている図形である。区間１１における上ラインに掛かっている図形は検査の対象外としている。この定義（ルール）に従って、ページ上の各区間における平均オブジェクトサイズを一意に算出する。
【００５１】
図２４は、第３の実施例におけるエッジ情報抽出処理の流れを示す図である。まず、エッジ抽出処理部１３は、オブジェクト（図形）が入力されると不図示のカウンタにより１ページ内のオブジェクト（図形）の総数Ｎをカウントする。そして、エッジ抽出処理部１３は、カウントされた総数Ｎと予め設定された閾値Ｔ１とを比較する。その結果、ページ内に存在するオブジェクト数Ｎが閾値Ｔ１より多いと判断した場合には、エッジ抽出処理部１３は、エッジ情報生成処理として、スキャンラインによるエッジ検出処理（図２参照）を行い、エッジ情報を生成する。
【００５２】
一方、ページ内に存在するオブジェクト数Ｎが閾値Ｔ１以下であると判断した場合には、エッジ抽出処理部１３は、各オブジェクト（図形）に付加されている図形種識別情報に基づいて処理手法を切り替えてエッジ検出処理を行い、エッジ情報を生成する。第３の実施例では、図形種識別情報は拡張情報として各オブジェクト毎に設定されている。エッジ抽出処理部１３は、各オブジェクトに対して拡張情報の有無を検査し、拡張情報が無い場合はデフォルトの処理（スキャンラインによるエッジ検出処理）を行い、エッジ情報を生成する。一方、拡張情報が存在する場合には、エッジ抽出処理部１３は、記録されている図形種識別情報を参照して処理手法を切り替える。例えば、図形種識別情報がＩＤ−１である場合には、エッジ抽出処理部１３は、三角形に対する処理を行い、第１の実施例のような処理手順でエッジ情報抽出処理を行う。また、例えば図形種識別情報としてＩＤ−２が付与されている図形（水平又は垂直方向に対称性がある図形）の場合には、エッジ抽出処理部１３は、第２の実施例で説明したＩＤ−２系の処理手順でエッジ情報抽出処理を行う。また、例えば図形種識別情報としてＩＤ−３が付与されている図形（回転や変形が施されている多角形等）の場合には、エッジ抽出処理部１３は、第２の実施例で説明したＩＤ−３系の処理手順でエッジ情報抽出処理を行う。なお、拡張情報が存在してもオブジェクト数が特性ＤＢの閾値Ｔｘより多い場合には、デフォルトの処理（スキャンラインによるエッジ検出処理）を行い、エッジ情報を生成する。
【００５３】
（その他の実施例）
第３の実施例では、特性ＤＢをプリンタドライバ側に設けるようにしているが、プリンタ装置側に設けるようにしても良い。また、予め測定したデータをスタティックに持つだけに限らず、プリンタ装置側の実行処理時間を適宜測定し、特性ＤＢに格納するデータを更新するようにしても良い。
さらにはプリンタ装置側とドライバ装置側で同じ特性ＤＢ（同期した特性ＤＢ）を持つように相互に通信し、ステータスの確認やデータの転送を行うように構成しても良い。本実施例によれば図形種の違いを判定するために用いる図形種識別情報を定義しているが、アプリケーション側で該情報を付与しても良いし、プリンタドライバ側で該情報を付与しても良い。図形種識別情報の種類と対応するエッジ抽出処理の手続きの整合性をとるために、アプリケーション、プリンタドライバ、及びプリンタ装置の間で、予め定められた通信プロトコルによって適宜情報の伝達（又は通信等）を行うよう構成しても良い。
前述の各構成において、プリントジョブ生成の際にプリンタ毎に適したＩＤ情報を付加し、プリンタ機種が変更になった場合でも、適切なＩＤ情報に切り替えられるように、付加するＩＤ情報とプリンタ機種の対応を内部で管理する機構を持つようにしても良い。
【００５４】
（本発明の他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【００５５】
例えば、本実施形態に示した画像処理装置は、図２５に示すようなコンピュータ機能７００を有し、そのＣＰＵ７０１により本実施形態での動作が実施される。
コンピュータ機能７００は、図２５に示すように、ＣＰＵ７０１と、ＲＯＭ７０２と、ＲＡＭ７０３とを備える。また、操作部（ＣＯＮＳ）７０９のコントローラ（ＣＯＮＳＣ）７０５と、ＣＲＴやＬＣＤ等の表示部としてのディスプレイ（ＤＩＳＰ）７１０のディスプレイコントローラ（ＤＩＳＰＣ）７０６とを備える。さらに、ハードディスク（ＨＤ）７１１、及びフレキシブルディスク等の記憶デバイス（ＳＴＤ）７１２のコントローラ（ＤＣＯＮＴ）７０７と、ネットワークインタフェースカード（ＮＩＣ）７０８とを備える。それら機能部７０１、７０２、７０３、７０５、７０６、７０７、７０８は、システムバス７０４を介して互いに通信可能に接続された構成としている。
ＣＰＵ７０１は、ＲＯＭ７０２又はＨＤ７１１に記憶されたソフトウェア、又はＳＴＤ７１２より供給されるソフトウェアを実行することで、システムバス７０４に接続された各構成部を総括的に制御する。すなわち、ＣＰＵ７０１は、前述したような動作を行うための処理プログラムを、ＲＯＭ７０２、ＨＤ７１１、又はＳＴＤ７１２から読み出して実行することで、本実施形態での動作を実現するための制御を行う。ＲＡＭ７０３は、ＣＰＵ７０１の主メモリ又はワークエリア等として機能する。
ＣＯＮＳＣ７０５は、ＣＯＮＳ７０９からの指示入力を制御する。ＤＩＳＰＣ７０６は、ＤＩＳＰ７１０の表示を制御する。ＤＣＯＮＴ７０７は、ブートプログラム、種々のアプリケーション、ユーザファイル、ネットワーク管理プログラム、及び本実施形態における前記処理プログラム等を記憶するＨＤ７１１及びＳＴＤ７１２とのアクセスを制御する。ＮＩＣ７０８はネットワーク７１３上の他の装置と双方向にデータをやりとりする。
【００５６】
なお、前記実施形態は、何れも本発明を実施するにあたっての具体化のほんの一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【産業上の利用可能性】
【００５７】
本発明はプリンタ装置、又はディスプレイ等の表示装置、画像出力デバイスなどに利用することができる。
【符号の説明】
【００５８】
１１…入力部、１２…分類部、１３…エッジ抽出処理部、１４…エッジ検出処理部、１５…エッジ情報生成部
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理方法に関し、特にレンダリング処理等に適用可能なエッジ情報生成に係る画像処理技術に関する。
【背景技術】
【０００２】
従来から図形を描画するために図形が持つ座標情報等から図形の輪郭情報（エッジ情報とも呼ぶ）を抽出し、該輪郭情報に基づいて画像を形成するレンダリング手法は一般に広く利用されている（例えば、特許文献１、特許文献２、特許文献３、特許文献４）。また、輪郭情報は直線で表現されるが該直線を表現するための手法としてＤＤＡ（Digital Differential Analyzer）アルゴリズムが知られている（非特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平０４−１７０６８６号公報
【特許文献２】特開平０８−７２３１７号公報
【特許文献３】特開２００５−２６７２９０号公報
【特許文献４】特開２００７−１２２１８８号公報
【非特許文献】
【０００４】
【非特許文献１】David Rogers, "Procedural Elements for Computer Graphics", McGraw-Hill Education
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、レンダリング処理において常に高速に描画処理が実行できることは重要な要件であるが、実際にレンダリング処理に要する時間は、図形の種類や数に依存して変化するためこれを実現することは容易ではない。従来のレンダリング処理では図形の種類によらずデータ処理を行うための手続き（アルゴリズム）は固定されており、レンダリング処理の高速化という観点では不十分な構造であった。
本発明は、このような事情に鑑みてなされたものであり、入力された図形に応じてアルゴリズムを適切に切り替え、レンダリング処理に係るデータ処理を行えるようにすることを目的とする。
【課題を解決するための手段】
【０００６】
本発明の画像処理装置は、レンダリング処理を行う画像処理装置であって、オブジェクトの情報を入力する入力手段と、前記入力手段より入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類手段と、前記分類手段により分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理手段とを有することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、入力されたオブジェクトの情報に基づいて処理手順を切り替えることで、オブジェクトに応じた適切な処理手順で処理を行ってエッジ情報を生成することができる。これにより、オブジェクトに応じた適切な処理手順でレンダリング処理に係るデータ処理を実行することができ、レンダリング処理の高速化を実現することができる。
【図面の簡単な説明】
【０００８】
【図１】レンダリング処理の一例を示すフローチャートである。
【図２】スキャンラインによるエッジ情報抽出処理を説明するための図である。
【図３】エッジ情報抽出処理の詳細を示すフローチャートである。
【図４】プリントジョブにおけるデータ処理時間の変化の一例を示す図である。
【図５】本発明の一実施形態に係る画像処理装置の構成例を示す図である。
【図６】本実施形態に係る画像処理装置の動作例を示すフローチャートである。
【図７】第１の実施例におけるタイルベースのエッジ検出処理を説明するための図である。
【図８】第１の実施例におけるエッジ情報抽出処理を示すフローチャートである。
【図９】第１の実施例におけるエッジ情報を格納したデータ構造体を示す図である。
【図１０】第２の実施例における図形種識別情報を説明するための図である。
【図１１】第２の実施例におけるエッジ情報抽出処理の流れを示す図である。
【図１２】第２の実施例における図形（ＩＤ−２系）の例を示す図である。
【図１３】第２の実施例におけるエッジ情報抽出処理の一例を示すフローチャートである。
【図１４】第２の実施例における図形（ＩＤ−３系）の例を示す図である。
【図１５】第２の実施例におけるエッジ情報抽出処理の一例を示すフローチャートである。
【図１６】第２の実施例を適用した場合の処理時間の一例を示す図である。
【図１７】各アルゴリズムでのエッジ情報抽出処理の速度特性を示す図である。
【図１８】第３の実施例における特性データベースに格納するデータ例を示す図である。
【図１９】プリントシステムの構成例を示す図である。
【図２０】第３の実施例における図形種解析等の処理を説明するための図である。
【図２１】第３の実施例における区間幅拡張を説明するための図である。
【図２２】第３の実施例における図形種解析等の処理の一例を示すフローチャートである。
【図２３】第３の実施例における区間幅内にあるオブジェクトを説明する図である。
【図２４】第３の実施例におけるエッジ情報抽出処理の流れを示す図である。
【図２５】本実施形態における画像処理装置を実現可能なコンピュータ機能を示す図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を図面に基づいて説明する。
まず、レンダリング処理について説明する。
図１は、レンダリング処理の一例を示すフローチャートであり、図形入力からエッジ情報を抽出する様子を示している。図示のようにレンダリング処理を行うレンダリング処理部（レンダラー）に入力される図形の種類は多様に存在している。図１に示す処理では、入力された図形の座標情報等からエッジ検出処理によりエッジ（輪郭）を検出して、図形を構成する線情報（エッジ情報）を生成する。例えば、図２は三角形の図形からエッジを抽出する様子を示しており、三角形に対してスキャンライン（水平線）が交差している状態であって、矢印で示すように２つのエッジが検出されている例を示している。この処理の概要を簡単に述べると、まず、入力された図形データをＹ方向にソートして、次にソートされた図形データに順次アクセスしＸ座標のデータ列を集める。このときに、Ｘ座標値の小さいものから大きいものへ昇順にデータがアクセスできるようにデータの参照テーブル等を作成する。画像を形成するための処理では、Ｘ方向スキャンを水平方向へ走らせ、これを縦方向（Ｙ方向）へと繰り返すことで該図形のエッジ情報を抽出していく。
【００１０】
図３は、入力された図形の座標情報等からエッジ情報を抽出する処理の詳細を説明したフローチャートである。処理を開始すると、レンダリング処理部は、まず、ステップＳ１１にて、入力されたデータをＹ方向にソートしデータを格納して、次にステップＳ１２にて、スキャンラインのＹ方向へのループ処理を開始する。ステップＳ１３にて、レンダリング処理部は、現在のスキャンラインにかかる図形データを拾い出し、かつ、スキャンライン上に存在するエッジ情報（カレントのエッジデータリスト）を更新する必要があるかないかを判断する。判断の結果、更新の必要がなければステップＳ１７へ進み、更新の必要があればステップＳ１４へ進む。ステップＳ１４にて、レンダリング処理部は、カレントのエッジデータリストに対するエッジの追加又は削除の判断を行う。新たに図形の輪郭にスキャンラインがかかった場合等、エッジを追加する場合には、レンダリング処理部は、ステップＳ１５にて追加すべきデータをＸ方向へ昇順となるように追加する。ここで追加されたデータはノードと呼ばれ、それぞれがリスト上に連結される。一方、図形の輪郭からスキャンラインが外れた場合にはステップＳ１６に進み、レンダリング処理部は、エッジデータリストから該当するエッジデータを適宜、削除する。
【００１１】
ステップＳ１７より、レンダリング処理部は、現在のスキャンラインにおけるＸ方向のエッジ情報を抽出するためのループ処理を行う。ステップＳ１８にて、レンダリング処理部は、エッジデータリスト上の各ノードに順次アクセスしていく。エッジの情報はカレント（Ｙ値）のスキャンラインにおけるデータ値（ＤＡ値）を線分の傾き等の情報から更新するよう構成されており、該データの更新処理はステップＳ１９にて実行される。続いて、レンダリング処理部は、ステップＳ２０にて、Ｘ方向のループ処理のためのカウンタ減算処理を行い、ステップＳ２１にてＸ方向ループ処理の終了の有無を判定する。判定の結果、Ｘ方向ループ処理を終了しない場合にはステップＳ１７へ戻り、Ｘ方向ループ処理を終了する場合にはステップＳ２２へ進む。そして、レンダリング処理部は、ステップＳ２２にてＹ方向ループ処理の終了の有無を判定し、終了しない場合にはステップＳ１２へ戻り、終了する場合には処理を終了する。
【００１２】
このようにステップＳ１７からステップＳ２１まではＸ方向のループ処理であり、またステップＳ１２からステップＳ２２まではＹ方向のループ処理であり、これら二重のループ処理によって平面上の図形の輪郭情報（エッジ情報）を抽出する。
【００１３】
図４は、前述したレンダリング処理を含むプリントジョブにおけるデータ処理時間の変化の一例を示したグラフである。図４において、縦軸は処理時間（ミリ秒）を示しており、横軸はプリントジョブのページを示している。図４に示す例では、１ページ目は処理を完了するために約４００ミリ秒かかっており、２ページ目は約５５０ミリ秒の時間を消費する。図４において、三角点で変化している線グラフはジョブに含まれる単純図形の数（相対値）を示しており、丸点で変化している線グラフは、単純図形以外（便宜上、ここでは複雑図形と呼ぶことにする）の数（相対値）を示している。複数ページにわたるプリントジョブを分析すると、矩形や三角など単純な図形が含まれている場合と、それ以外の複雑な図形（多角形等）が含まれている場合とでデータ処理の時間に違いがあることが図４から読み取れる。
【００１４】
ここで、一般的にプリントジョブには単純図形がより多く含まれる傾向があるので、プリント処理の平均時間を向上させるためには、単純図形を如何に効率良く高速に処理できるかということが重要である。しかし、前述したレンダリング処理では図１に示したように図形の種類によらずデータ処理を行うための処理手順（アルゴリズム）は固定されている。そこで、本実施形態では、入力された図形（入力オブジェクト）の種類に応じてデータの処理手順（アルゴリズム）を切り替えて、レンダリング処理に係るエッジ情報生成処理を行う。
【００１５】
図５は、本発明の一実施形態に係る画像処理装置の構成例を示すブロック図である。本実施形態に係る画像処理装置は、図形データを処理するレンダリング処理を行う画像処理装置であって、入力部１１、分類部１２、及びエッジ抽出処理部１３を有し、入力オブジェクトの座標情報等に基づいて図形の輪郭情報であるエッジ情報を生成する。入力部１１より入力された図形（入力オブジェクト）は、分類部１２での図形種別判定処理により例えば単純図形（第１の図形種）又は複雑図形（第２の図形種）に分類される。エッジ抽出処理部１３は、エッジ検出処理部１４及びエッジ情報生成部１５を有し、分類部１２で分類した結果に応じてエッジトレースアルゴリズムを切り替えてエッジ検出を行いエッジ情報を生成する。例えば、エッジ検出処理部１４は、単純図形（第１の図形種）と分類されたオブジェクトについてはタイル処理による（タイルベースの）エッジ検出処理を行い、複雑図形（第２の図形種）については前述したスキャンラインによるエッジ検出処理を行う。エッジ情報生成部１５は、エッジ検出処理部１４での処理結果に基づいてエッジ情報を生成する。
【００１６】
図６は、本実施形態に係る画像処理装置の動作例を示すフローチャートであり、図形入力からエッジ情報を抽出する様子を示している。まず、分類部１２は、図形種別判定処理を行い、入力部１１より入力された図形（入力オブジェクト）を単純図形（第１の図形種）と、それ以外の複雑図形（第２の図形種）とに切り分ける（ｐ１１）。そして、エッジ抽出処理部１３のエッジ検出処理部１４は、複雑図形に対しては前述したスキャンラインによるエッジ検出処理を行い（ｐ１２）、単純図形に対してはタイル処理によるエッジ検出処理を行う（ｐ１３）。これらのエッジ検出処理の処理結果に基づいて、エッジ抽出処理部１３のエッジ情報生成部１５は、入力オブジェクトに係るエッジ情報を生成する。
【００１７】
このように本実施形態に係る画像処理装置では、入力された図形（オブジェクト）に応じて処理手順を切り替えてエッジ検出を行い、その処理結果に基づいてエッジ情報を生成する。これにより、入力された図形に応じた適切な処理手順でレンダリング処理に係るデータ処理を行うことができ、レンダリング処理の高速化を図ることができる。
【００１８】
以下、本実施形態におけるタイル処理によるエッジ検出処理について説明する。なお、以下の説明では、各タイルは１６×１６のピクセル（画素）で構成されているものとする。
【００１９】
（第１の実施例）
以下、タイル処理によるエッジ検出処理の第１の実施例について説明する。
図７は、第１の実施例におけるタイル処理によるエッジ検出処理の概要を説明するための図である。図７に示すような点ＡＢＣを頂点とする三角形を考えると、該三角形の外郭の領域は図示した縦のタイル（図中左端の１から１０までの番号が振られているタイル）の範囲に含まれる。三角形の辺の数は３つであるので、エッジ抽出処理部１３は、各辺毎にエッジ情報を抽出する処理を行う。図７に示した例では、点Ａから点Ｂまでの辺ＡＢに対しては、２つの点Ａ及び点Ｂがそれぞれ含まれるタイルを除いた１１個のタイルにおいて、エッジ情報の抽出がそれぞれ行われる。該１１個のタイルでは、各矩形領域（タイル）において点Ａと点Ｂとを結ぶ直線（辺ＡＢ）の一つだけがかかっている状態である。つまり、タイルを構成する矩形の４つの辺のいずれかが、点Ａと点Ｂとを結ぶ直線と交差している。このとき、タイルと、点Ａ及び点Ｂを結ぶ直線との交点は２点となる。第１の実施例では、エッジ抽出処理部１３は、この２点（２つの交点）の座標データに基づいてエッジ情報（エッジデータ）を生成する。なお、図７中の三角形を構成するその他の二辺、つまり、点Ａと点Ｃとを結ぶ辺ＡＣ及び点Ｂと点Ｃとを結ぶ辺ＢＣのそれぞれについてもエッジ抽出処理を行うが、その手順は辺ＡＢに対する処理と同様である。また、頂点の位置や辺の角度によっては、２つの辺（例えば、辺ＡＢと辺ＡＣ）が同一タイルにかかる場合もあり得るが、その場合でも各辺におけるエッジ抽出処理はそれぞれ別に進められ適宜マージされる。
【００２０】
図８は、第１の実施例におけるエッジ情報抽出処理の一例を示すフローチャートである。処理を開始すると、エッジ抽出処理部１３は、まずステップＳ７１にて、図形（オブジェクト）の数だけループ処理を行うよう設定する。なお、本実施例で対象とする図形は、図形を構成する辺の数が３又は４である図形（すなわち、三角形又は四角形）のみであり、分類部１２での処理により他の図形とは切り分けがなされているものとする。ステップＳ７２にて、エッジ抽出処理部１３は、エッジ抽出処理を行うある１つのオブジェクトのパス数（辺数３又は４）だけループ処理を行うように設定する。ステップＳ７３にて、エッジ抽出処理部１３は、レンダリング空間における対象のパス（辺）におけるタイル（対象のパスがかかるタイル）の数を計算により求め、そのタイルの数だけループ処理を行うよう設定する。ステップＳ７４にて、エッジ抽出処理部１３は、対象のパスとタイルを構成する辺とが交差する２点のデータの組み合わせからデータベースを検索して一意にデータを入手することで、レンダリング空間の各タイルにおけるエッジ情報（エッジデータ）を取得する。なお、このデータベースについては後述する。ステップＳ７５にて、エッジ抽出処理部１３は、ステップＳ７４において取得したエッジ情報をタイル上のデータとして登録（セット）する。ステップＳ７４及びステップＳ７５の処理を対象のパス（辺）におけるタイルの数だけ繰り返す。そして、ステップＳ７６、及びステップＳ７７により必要な回数分のループ処理を行うことで、エッジ抽出処理部１３は、該当するすべての図形（オブジェクト）のエッジ情報を抽出する。
【００２１】
以上、説明したように図８に示したフローチャートに沿って処理を行うと、図形毎に独立して（外接矩形のユニットで）タイルデータが生成されていく。タイルデータが生成されるタイル群は、相当数が生成されると適時マージ（合成）される。タイルデータが生成されたタイルをマージする際には、ページをバンド（例えば１バンド＝１６０ラインの固定幅）の単位で区切る。そして、ページ上部のバンドからページ下部へむけて、処理が必要なバンド（この時点でタイルが存在するバンドのみが処理の対象）を選択しながら順次処理を進める。合成処理を開始した時点で生成されているタイルを対象に、各バンドにかかるタイルを適宜、選択しながら合成処理を行う。最終的には１ページ分のすべてのオブジェクトが処理され、不図示のスプーラー（一時保存領域）へ全タイルデータがストアされる。該ストアされた１ページ分のタイルデータには、図形の輪郭情報（エッジ情報）や描画色等が記録されており、これら情報を適時参照しながらビデオフレーム等へ描画処理（ピクセル出力）を行うよう構成されている。該描画処理は不図示のピクセル展開処理部で実行される。
【００２２】
図９は、図８に示したステップＳ７４において参照するデータベースを説明するための図である。前述したように本実施例において、タイルは１６×１６ピクセルを前提としており、１６×１６ピクセルのタイルを考えると、この矩形を横切る直線のパターンは有限であって、そのパターンは矩形の辺と直線との交点の組み合わせパターンですべて表現できる。例えば、矩形を横切る直線の例の一つとしてタイル矩形の左上側に斜め４５度で小さく横切る直線を考える（該直線は図示のように３つのピクセルで表現される）。図９（Ａ）は、この様子を表しており、タイルの左上側のみを図示している。タイルを横切る辺は、図９（Ａ）において左下の点から右上に向けて貫通している状態とも言える。この例の場合には、左下の交点の座標は（３，１）、右上の交点の座標は（１，３）となっている。
【００２３】
このとき、タイルの内部のエッジは、スキャンライン（水平方向）の単位で考えると、３つのエッジ（境界）が存在していることになる。これをタイル内部データの表現として、タイル最左上の点を基準点とするオフセット値で表すこととする。図９（Ａ）に示す例では、右側に記載されている「＋２」という値がオフセット値を示している。次のスキャンラインにおけるエッジデータは、前のスキャンラインでのエッジデータ（ここでは＋２の位置）に対する相対的な値（相対オフセット値）として示す。図上、左側にエッジが存在する場合にはマイナスの値をとり、右側にエッジが存在する場合にはプラスの値をとるように定義する。図９（Ａ）に示した例では、それぞれ左側にエッジが存在しているので「−１」、「−１」というデータ列になる。
【００２４】
タイルを横切る直線のパターンは有限であり、縦１６×横１６ピクセルのタイルの場合、交差する直線とタイルを構成する矩形の辺との交点の組み合わせ（２交点の場合の数）は、２９４４（＝１６×（１６＋１５＋１５）×４）通りの組み合わせが存在する。本実施例ではエッジ情報を保持するデータベースは、図９（Ｂ）に示すように構成される。図９（Ｂ）に示すエントリーテーブルは、１６×１６ピクセルのタイルにおいて、タイルに交差する直線とタイルを構成する矩形の辺との交点の組み合わせに対応し、２９９４個のエントリを持っている。該エントリーテーブルから先には、それぞれの場合に応じたエッジ情報を格納した配列テーブルがあり、該エントリーテーブルを経由してエッジ情報を得ることができるようになっている。該エッジ情報は図９（Ａ）で述べたオフセット値を集めたデータ列で表現されている。
【００２５】
以上説明したように、第１の実施例では、図形を構成する辺数が３又は４である単純図形である場合には、タイル処理によるエッジ検出処理を行う。具体的には、エッジ抽出処理部１３は、入力された図形を構成する辺をタイル上の座標におき、次にタイルを構成する矩形辺と交差する点を求める。そして、求めた交差する点の座標データの組み合わせに基づいて、該当するエッジ情報を格納したデータベースから検索して取得することでエッジ情報を生成する。これにより、エッジ情報を生成する際の演算量を効率良く抑制することができるようになり、処理速度を効果的に向上させることができる。
【００２６】
（第２の実施例）
次に、第２の実施例について説明する。
前述した第１の実施例では、分類部１２での図形種別判定処理により入力された図形（入力オブジェクト）が、何であるかを検査し、その結果、図形が三角形又は四角形である場合にタイル処理によるエッジ抽出処理を行っていた。第２の実施例では、図形オブジェクトの個々に対して図形の種類を表す「図形種識別情報」を付加するようにして、星型等、その他の図形（但し、直線で構成される図形）に対してもタイル処理によるエッジ抽出処理を行えるようにする。さらには、図形の特性（例えば対称性等の特性）を利用することで処理の高速化を図れるものについては個別に処理手続き（アルゴリズム）を用意し、それぞれの図形に応じた最善の処理手順によってエッジ情報の生成を行う。
【００２７】
図１０に示すように図形等を扱うアプリケーションソフトウェアでは、プルダウンメニュー等からドキュメントに挿入する図形種（図形の種類、例えば三角形、四角形、台形、平行四辺形等）を選択できるようになっている。アプリケーション側から各図形に対して図形の種類を表す「図形種識別情報」を割り当てられるよう構成することで、印刷プリントジョブの中にある図形のデータそれぞれに対して該図形種識別情報を付加する。図１０に示す例では、図形種識別情報として、三角形にＩＤ−１が割り当てられ、同様に、星型にＩＤ−２、回転された十字型の多角形にＩＤ−３がそれぞれ割り当てられている。
【００２８】
図１１は、第２の実施例におけるエッジ情報抽出処理の流れを示す図である。まず、エッジ抽出処理部１３は、オブジェクト（図形）が入力されると不図示のカウンタにより入力されたオブジェクト（図形）の総数Ｎを積算する。そして、エッジ抽出処理部１３は、オブジェクト（図形）が入力されると逐次、又は１ページ内（又は所定の処理単位内）の図形すべての入力が完了した時点で、積算された総数Ｎと予め設定された閾値Ｔ１を比較する（ｐ１１１１）。比較の結果、オブジェクト総数Ｎが閾値Ｔ１より大きい場合（Ｎ＞Ｔ１）には、エッジ抽出処理部１３は、前述のスキャンラインによるエッジ検出処理（図２参照）を行い、エッジ情報を生成する。
【００２９】
一方、オブジェクト総数Ｎが閾値Ｔ１以下である場合（Ｎ≦Ｔ１）には、エッジ抽出処理部１３は、各オブジェクト（図形）に付加されている図形種識別情報に応じて処理手法を切り替えてタイル処理によるエッジ検出処理を行い、エッジ情報を生成する。例えば、図形種識別情報がＩＤ−１である場合には、エッジ抽出処理部１３は、三角形に対する処理を行い、第１の実施例のような処理手順でエッジ情報抽出処理を行う。また、例えば図形種識別情報としてＩＤ−２が付与されている図形の場合（本実施例中の例では星型の場合等）には、エッジ抽出処理部１３は、三角形の場合とは別の処理手順でエッジ情報抽出処理を行う。図形種識別情報としてＩＤ−２が付与されている図形に対する処理手続き（アルゴリズム）は、水平軸又は垂直軸に関して対称性を有する図形に適しているものであり、その処理の詳細は後述する。また、例えば図形種識別情報としてＩＤ−３が付与されている図形の場合（回転や変形が施されている多角形等）には、エッジ抽出処理部１３は、三角形（ＩＤ−１系）や対称性を持つ図形（ＩＤ−２系）の場合とは異なる処理手順でエッジ情報抽出処理を行う。図形種識別情報としてＩＤ−３が付与されている図形に対する処理手続き（アルゴリズム）の詳細は後述する。
【００３０】
以下、第２の実施例での、図形種識別情報としてＩＤ−２が付与されている図形に係るエッジ情報抽出処理について説明する。
図１２は、図形種識別情報としてＩＤ−２が付与されている図形の一例を示しており、ここでは星型を一例として示している。星型の図形は、縦の中心軸に対して左右の形（輪郭）が線対称となっている。このように図形が線対称であり、かつ、対称軸が水平又は垂直である場合には、まず対称軸で分割した一方の側の輪郭に対してのみエッジ情報抽出処理を行う。そして対称軸に関して他方の側の輪郭に対しては、一方の側に対するエッジ情報抽出処理で得られたエッジデータを反転することで残りのエッジデータを生成することができる。この処理を効率的に実行するためにはレンダリング処理で用いるタイルの境界線と図形の対称軸とを一致させておく必要がある。本来、描画するオブジェクトはレンダリングする座標位置が指定されており、またレンダリング座標とタイルの位置関係は独立に決められているため、図形の対称軸とタイルの境界は一般的に一致しない。これを一致させるため、本実施例では一時的に図形の座標位置を相対座標空間上に移しエッジ情報抽出処理を実行した後にオリジナルの座標に再度移動させるよう構成している。
【００３１】
図１３は、第２の実施例における図形種識別情報としてＩＤ−２が付与されている図形に係るエッジ情報抽出処理の一例を示すフローチャートである。
エッジ抽出処理部１３は、ステップＳ１３０にて入力された図形の座標データを、ステップＳ１３１にて相対座標空間での座標データに変換する。相対座標空間は、前述したように、対象とする図形の中心軸（星型の場合は図１２において矢印で指す中央のライン）とタイルの境界線とが合致するように構成した座標空間である。例えば、図形の中心軸と外郭線とが交差する点（星型であれば例えば図中の最上にある頂点）を、タイルを構成する矩形の４つの頂点の内のいずれか一つ（図中のタイル境界を示す縦線と横線がクロスする十字の中心）に合致させるようにした座標空間である。次に、エッジ抽出処理部１３は、ステップＳ１３２にて、対象とする図形を取り囲む矩形領域を生成し、ステップＳ１３３にて、該矩形領域が包含されるように該矩形領域を含む領域に対してタイルを配置する。対象とする図形を構成する辺（セグメントと呼ぶ）のうち、中心軸で分割した一方の側のセグメントに対してエッジ検出の処理を行うので、エッジ抽出処理部１３は、ステップＳ１３４にて対象の辺の数をカウントする（セグメントの総数を数えてセットする）。エッジ抽出処理部１３は、ステップＳ１３５にてループ処理を開始して、ステップＳ１３６にて対象の辺に関するエッジ情報を抽出する。ステップＳ１３４において設定した対象の辺の数だけ、このループ処理を行うことにより、エッジ抽出処理部１３は、順次対象の辺に関するエッジ情報を抽出する。なお、ステップＳ１３６の処理では、第１の実施例における処理と同様にして、各辺がタイル境界を横切る交点の情報からエッジ情報を生成する。前述した一連のループ処理後は、中心軸で分割した図形の一方の側のセグメントについてエッジ情報の抽出が完了している状態である。エッジ抽出処理部１３は、ステップＳ１３７にて、一方の側のエッジ情報に基づいて中心軸に対して他方の側のエッジ情報を生成した後、ステップＳ１３８にて、対象とする図形のエッジ情報を絶対座標系（もとの座標位置）に戻し処理を完了する。
【００３２】
以下、第２の実施例での、図形種識別情報としてＩＤ−３が付与されている図形に係るエッジ情報抽出処理について説明する。
図１４は、図形種識別情報としてＩＤ−３が付与されている図形の一例を示しており、ここでは回転された星型を一例として示している。星型の図形は、対称性を持つ図形であるが、図１４に示すように回転された場合には対称軸も回転するため、図形の対称軸とタイル境界に係る縦又は横のラインとは一致しなくなる。このため、前述した図形種識別情報としてＩＤ−２が付与されている図形に対する処理のように、対称軸について一方の側のエッジデータを反転して他方の側のエッジデータを生成するという処理は実行できない。よって、図形種識別情報としてＩＤ−３が付与されている図形である場合には、エッジ抽出処理部１３は、図形を構成する輪郭（エッジ）すべてのエッジ情報の生成を順次行う。具体的には、図形のエッジを抽出するために図形の座標位置を相対座標空間上へマッピングしてエッジ情報抽出処理を実行した後にオリジナルの座標に再度移動させる。相対座標空間上へのマッピングでは、対象とする図形（本例では回転した星型）を取り囲み、かつ相対座標空間における水平軸に平行な辺及び垂直軸に平行な辺からなる外接矩形を作成する。そして、該外接矩形の左上の頂点を、タイルを構成する矩形の４つの頂点の内のいずれか一つ（タイル境界を示す縦線と横線がクロスする十字の中心）に合致させる。
【００３３】
図１５は、第２の実施例における図形種識別情報としてＩＤ−３が付与されている図形に係るエッジ情報抽出処理の一例を示すフローチャートである。
エッジ抽出処理部１３は、ステップＳ１４０にて入力された図形の座標データを、ステップＳ１４１にて相対座標空間での座標データに変換する。相対座標空間は、タイルで構成されており、前述したように図形に外接する相対座標空間の水平軸に平行な辺及び垂直軸に平行な辺を持つ矩形における左上の頂点を、タイル境界を示す縦線と横線がクロスするいずれかの点に合致させるようにした座標空間である。次に、エッジ抽出処理部１３は、ステップＳ１４２にて、対象とする図形を取り囲む矩形領域を生成し、ステップＳ１４３にて、該矩形領域が包含されるように該矩形領域を含む領域に対してタイルを配置する。続いて、エッジ抽出処理部１３は、ステップＳ１４４にて、対象とする図形を構成する辺（セグメントと呼ぶ）の数をカウントする（セグメントの総数を数えてセットする）。エッジ抽出処理部１３は、ステップＳ１４５にてループ処理を開始して、ステップＳ１４６にて対象の辺に関するエッジ情報を抽出する。このループ処理を行うことにより、エッジ抽出処理部１３は、順次対象の辺に関するエッジ情報を抽出する。ステップＳ１４５において設定した対象の辺の数だけ、このループ処理を行うことにより、エッジ抽出処理部１３は、順次対象の辺に関するエッジ情報を抽出する。なお、ステップＳ１４６の処理では、第１の実施例における処理と同様にして、各辺がタイル境界を横切る交点の情報からエッジ情報を生成する。最後に、エッジ抽出処理部１３は、ステップＳ１３７にて、対象とする図形のエッジ情報を絶対座標系（もとの座標位置）に戻し処理を完了する。
【００３４】
図１６は、第２の実施例を適用した場合のプリントジョブにおける各ページの処理時間の分布の一例を示したグラフである。図１６において、横軸はジョブページ（１から１６ページまで）を示しており、縦軸はそれぞれのページにおける処理時間（ミリ秒）を示している。図中、各折線データが、エッジ処理時間の変化を示している。実線はスキャンラインによるエッジ検出処理のみで処理を実行した場合の処理時間を示しており、ジョブ全体を通しての平均処理速度は１７０ミリ秒である。一方、点線は入力された図形のうち三角形に対してのみタイル処理によるエッジ検出処理を行い、その他についてはスキャンラインによるエッジ検出処理を実施した場合の処理時間を示している。図中に示される点線より明らかなように、２ページ、４ページ、８ページ、１２ページの処理で高速化が実現されており、またジョブ全体を通しての平均処理速度は１６５ミリ秒である。さらに、破線は入力された図形のうち三角形（ＩＤ−１系の図形）や星型等（ＩＤ−２系の対称図形）に対してタイル処理によるエッジ検出処理を行い、その他についてはスキャンラインによるエッジ検出処理を実施した場合の処理時間を示している。図中に示される破線より明らかなように、８ページ、１２ページ、１３ページ、１６ページの処理でさらなる高速化が実現されており、またジョブ全体を通しての平均処理速度は１６０ミリ秒である。
【００３５】
以上説明したように、第２の実施例では、ジョブに含まれる多種多様な図形に対して、それぞれ最適な処理手法を用意し、図形に応じて適切に切り替えて各処理を実行することにより全体のスループットを向上させることができる。
【００３６】
（第３の実施例）
前述したように、第１の実施例や第２の実施例のような処理を適用することで、エッジ情報生成処理に関する処理の高速化を実現することができる。いずれの場合にも処理の高速化の手段としてタイル処理によるエッジ検出処理を用いているが、これらの結果は、前述した例のようにオブジェクトの数が少ないという条件下で得られると考えられる。逆に、オブジェクトの数が極めて多い場合には、スキャンラインによるエッジ検出処理に比べてタイル処理によるエッジ検出処理の方が遅くなる場合があると考えられる。また、プリントジョブを生成する際に、アプリケーションソフト側が、各オブジェクトに対する図形種判定のための図形種識別情報の付与に対応できないケースも生じ得る。
【００３７】
そこで、第３の実施例では、オブジェクトの数に応じて変化する各アルゴリズムにおける速度（処理時間）の変化特性を、特性情報等を記録する特性データベース（特性ＤＢ）へ記録しておく。例えば、各アルゴリズム（スキャンライン系とタイルベース系）における速度の変化特性（例えば処理速度が逆転するオブェクト数の情報等）を特性ＤＢへ記録しておく。そして、該特性ＤＢに記録されている情報に基づいて処理の切り替えを行うようにする。また、アプリケーションソフト側が図形種識別情報を付加しない場合でも、プリンタドライバ側で図形データを解析して適宜図形種識別情報を付加できるようにする。
【００３８】
図１７は、各アルゴリズムでのエッジ情報抽出処理の速度特性を示したグラフであり、横軸がオブジェクト数を示しており、縦軸が処理時間を示している。スキャンライン系処理及びタイルベース系処理のいずれの場合にもオブジェクトの数が増えると、それに伴って処理時間が増加するという傾向がある。図１７において、（ａ）はスキャンライン系処理での特性を示しており、（ｂ）はタイルベース系処理（前述した第１の実施例におけるエッジ検出処理）の特性を示している。また、（ｃ）はスキャンライン系処理とタイルベース系処理との両方を使ったハイブリッド系の処理での特性を示している。以下、図１７に示す各グラフ特性の違いについて詳細に述べる。
【００３９】
図１７（ａ）に示されるように、スキャンライン系処理では、領域Ａ（オブジェクト数が少ない領域）では処理速度が遅い。しかし、オブジェクト数が増えてくると領域Ｂ（オブジェクト数が多い領域）では、オブジェクト数の増加に対する処理速度の低下が抑制される特性がある。これは、一つのスキャンライン上に多くの図形がかかってくるようなケースでは、ループ処理の効率が向上すること等が影響していると考えられる。一方で、図１７（ｂ）に示されるように、タイルベース系処理では、領域Ａ（オブジェクト数が少ない領域）では処理速度が速いが、オブジェクト数が増えてくると領域Ｂ（オブジェクト数が多い領域）では、処理速度の低下が顕著となってくる。これはタイルベース系処理では、各オブジェクトに対して独立に処理を行っているため、図形の数に比例して処理ステップ数が増加すること等が影響していると考えられる。
【００４０】
以上述べたように、スキャンライン系処理とタイルベース系処理とはそれぞれの領域において、逆の特性を有している。スキャンライン系処理及びタイルベース系処理の特性を調べて処理速度が逆転するオブジェクト数を取得し、そのオブジェクト数で処理を切り替えるようにすることで、互いの長所を引き出すことができる。図１７（ｃ）は、領域Ａではタイルベース系処理で処理を行い、領域Ｂではスキャンライン系処理で処理を行うように、分岐点（処理速度が逆転するオブジェクト数）にて処理を切り替える場合の特性を示したものである。
【００４１】
なお、オブジェクト数に応じた処理速度（処理時間）の変化特性は、各処理手順（アルゴリズム）に依存しているために各処理手順毎に特性を把握しなくてはならない。第２の実施例でいえば、図形種識別情報としてＩＤ−２が付与されている図形と、ＩＤ−３が付与されている図形との特性は、個々に違う特性を持っており、特にスキャンライン系のエッジ検出処理と速度が逆転するポイント（分岐点）は個々異なっている。
【００４２】
また、図形の大きさ等も処理時間の特性に影響を与える。第１の実施例では、図８の説明で述べたように図形毎にタイルデータが順に生成されていき、タイルデータが生成されるタイル群は、相当数が生成されると適時マージ（合成）されるよう構成されている。これらを処理する際にはページを固定の区間幅（バンド幅：例えば１バンド＝１６０ライン）の処理単位で区切って処理を進めている。第１の実施例における前提としては、多くの図形が固定の区間幅（例えば１６０ライン）の中に収まることを前提としていたが、指定される図形のサイズには制限がなく平均サイズが予め設定した区間幅を超えることも考えられる。図形のサイズが大きくなると特にスキャンラインによるエッジ検出処理特性に影響が出てくる。これはエッジ検出処理の特性（分岐点の変化）に影響を与える大きな要因の一つとなる。このことから本発明のより好適な実施態様としては図形サイズの違いも考慮した構成とすることが望ましい。第３の実施例では、２つの区間幅（１６０ライン、３２０ライン）を用意して、図形の平均サイズに応じて区間幅を適宜切り替えるようにする。
【００４３】
したがって、第３の実施例においてエッジ情報抽出処理における特性は、図１８に示すように、アルゴリズムの種類（本実施例では３種類）、及び図形の大きさ（本実施例では２種類）のそれぞれを掛け合わせた組み合わせ（合計６種類）の特性を測定する。そして、測定により得られた該特性に係る関連情報を特性ＤＢに格納しておき、格納されている情報に基づいて処理の切り替えを行う。図１８は、第３の実施例で用いる特性ＤＢに格納される特性データ（６種類）を説明するための図である。
【００４４】
図１９は、プリンタドライバを含めたプリントシステムの構成例を示すブロック図である。図１９においては、要素的特徴のみを示している。第３の実施例の説明における冒頭で述べたように、本例ではアプリケーションソフト側が図形種識別情報を付加しない場合でも、図形種に応じた処理の切り替えに対応できるようにプリンタドライバ側にて図形種解析処理を実行可能としている。図形の簡単なものは座標点の構成、位置関係からある程度の分類が可能である。なお、図形種解析処理を行うことにより処理時間は若干増加すると考えられるが、プリンタドライバは高速なホストＰＣ側で行われるためプリントシステム全体のスループットを考慮するとメリットは存在する。
【００４５】
各処理手順（アルゴリズム）における速度の変化特性に係る情報が格納される特性ＤＢ１９４は、プリンタドライバ１９１のモジュール内に存在している。アプリケーションから印刷が開始されると、プリンタドライバ１９１は、図形データ生成部１９２の出力情報を基にプリントジョブの生成を開始する。同時に、図形種解析部１９３は、各オブジェクトの図形種の解析処理を開始するとともに、該解析処理と平行して特性ＤＢ１９４にアクセスして各オブジェクト（図形）に対し図形種識別情報を付加していく。ここで図形種識別情報としてＩＤ−１が付与された図形は、第１の実施例で説明したようなタイルベースのエッジ情報抽出処理が割り当てられることとなる。また、図形種識別情報としてＩＤ−２が付与された図形は、第２の実施例で説明した図１３に示したような処理手順でのタイルベースのエッジ情報抽出処理が割り当てられることとなる。さらに、図形種識別情報としてＩＤ−３が付与された図形は、第２の実施例で説明した図１５に示したような処理手順でのタイルベースのエッジ情報抽出処理が割り当てられることとなる。
【００４６】
前述したＩＤ−１、ＩＤ−２、ＩＤ−３の図形種識別情報は、ＰＤＬ（ページ記述言語）データ内の（各オブジェクト毎に割り当てられている）拡張情報領域を適宜拡張して格納される。なお、ＰＤＬデータ内のオブジェクトに対してはデフォルトでは拡張情報は存在していない状態であり、該拡張情報がない図形等に関してはスキャンラインによるエッジ情報抽出処理が実行されることとなる。
【００４７】
以上のように、プリンタドライバ１９１からは適宜図形種識別情報が付加されたＰＤＬデータが生成され、該ＰＤＬデータはプリントスプーラー等の機能部１９５を経由してプリンタ装置１９６に転送される。プリンタ装置１９６では、ＰＤＬ解析部１９７がデータの解析処理を行い、ＰＤＬデータ中、図形等のオブジェクトに対しては画像形成処理が起動されて、その処理において図形のエッジ情報が生成される。このとき、ＰＤＬ解析部１９７及び機能部１９８は、各オブジェクトに対して拡張情報の有無を確認する。その結果、拡張情報が存在する場合は、その中に格納されている図形種識別情報（ＩＤ−１，ＩＤ−２，ＩＤ−３のいずれかであるか）を読み取り、読み取った図形種識別情報に基づいて、実行すべきエッジ抽出処理の選択を行う。そして、選択されたエッジ抽出処理に応じてエッジ抽出処理部１９９により処理が実行される。プリンタ装置１９６のコントローラは抽出されたエッジ情報に基づきイメージを生成し、プリンタ装置１９６のプリントエンジンは、生成されたイメージに基づき用紙にプリントを行う。
【００４８】
以下、図２０〜図２４を参照して、第３の実施例における各図形に関するその他の処理について説明する。
図２０は、第３の実施例における図形種解析等の処理を説明するための図である。図２０に示すように、プリンタドライバ内ではＧＤＩ（グラフィックスインターフェース）からの描画命令に基づいてＰＤＬの生成が行われる。その過程で図形種解析処理が行われて、図形に係る統計情報が取得される。この統計情報は、区間（ページ上の各バンド）毎に集計され、各区間における図形種別の個数及びその平均サイズ等が含まれる。ページにおける描画区間の幅は、図２１に示すようにデフォルトでは１６０ラインとしているが、大きな図形が特定バンドに多く存在し該図形サイズの平均サイズが１６０ライン分よりも大きくなる場合には区間幅を拡張するよう構成されている。第３の実施例では、区間幅を拡張した場合のサイズを３２０ラインとしている。また、図形種毎に平均サイズを測定するため、各区間幅に関する情報は図形種毎に独立して管理する。図２０に示した例で説明すると、あるジョブを解析した時の統計情報として、ＩＤ−１系のオブジェクト数が５２００個、ＩＤ−２系のオブジェクト数が３２００個、ＩＤ−３系のオブジェクト数が２１００個、その他が６２００個という情報が取得されたとする。区間幅を各ＩＤ毎にみると、ＩＤ−２とＩＤ−３において一部区間拡張がされている。例えば、ＩＤ−２系に係る統計情報において、ある区間（バンド）において１３００個のオブジェクトが存在し、かつ、該オブジェクト（図形）の平均サイズが２４２であると、該区間については区間拡張を行い、区間幅は３２０ラインとされる。特性ＤＢに対するＩＤ−２系の特性（分岐点の情報＝特性ＤＢでは閾値Ｔｘ）の問い合わせのために平均サイズの情報も利用する。図２０に示した例での特性ＤＢでは、ＩＤ−２系の特性において区間幅３２０ラインの場合の閾値は２４００と記録されている。したがって、該区間幅３２０ラインに分布しているＩＤ−２系の図形についてエッジ情報抽出処理を行う場合には、第２の実施例で説明したようなタイルベースのエッジ情報抽出処理を実行すべきことが判明する。
【００４９】
図２２は、第３の実施例における図形種解析等の処理の一例を示すフローチャートである。ステップＳ２２１は、図形種の解析処理のエントリであり、このステップＳ２２１では、初期化処理等が行われる。ステップＳ２２２にて、オブジェクトリストが生成され、ＰＤＬの情報を受けてグラフィックスにおけるパス情報、座標値、又はテキストコード等、各オブジェクトデータの蓄積が行われる。ステップＳ２２３にて、処理単位（処理ページ）におけるオブジェクト数Ｎの積算（総数のカウント）が行われる。ステップＳ２２４にて、オブジェクト数Ｎと閾値Ｓとが比較される。比較の結果、オブジェクト数Ｎが閾値Ｓより多ければステップＳ２３１へ分岐し、スキャンラインによるエッジ抽出処理を実行した後に呼び出し側モジュールへ復帰する。一方、オブジェクト数Ｎが閾値Ｓ以下であればステップＳ２２５へ分岐し、ステップＳ２２５にて、詳細調査の処理が開始される。ステップＳ２２６にて、各区間の検査が行われる。ステップＳ２２７では該当する区間（つまり、問題がありそうな区間＝オブジェクトが沢山存在する区間（バンド）等を意味する）において存在する図形のそれぞれにおいて平均のオブジェクトサイズを計算する。個々のオブジェクトサイズの例としては外接矩形の長辺の長さ等である。また、ある区間における平均オブジェクトサイズとは、図形のオブジェクトサイズの平均値である。次に、ステップＳ２２８にて、各バンドに対して該区域内に存在する図形オブジェクトの平均サイズが算出される。該区域内に存在する図形オブジェクトの算出方法に関しては図２３を用いて後述する。ステップＳ２２９にて、算出された平均オブジェクトサイズと閾値Ｔｘが比較され、平均オブジェクトサイズが閾値Ｔｘより大きい場合にはステップＳ２３０へ分岐し、該当部分の区間幅を拡張する。ここで、閾値Ｔｘは、例えば特性ＤＢより取得される。一方、ステップＳ２２９での比較の結果、平均オブジェクトのサイズが閾値Ｔｘ以下の場合には、区間幅の拡張は行わずに呼び出し側モジュールへ復帰する。
【００５０】
図２３は、区間幅が拡張された場合の様子を説明するための図である。図中、区間１１は現検査対象区間となっている区間である。区間１１は、図にあるように上ラインと下ラインに挟まれた区間であって、その幅は初期値として１６０ラインで定義されていている。この例では、この区間に関係している図形のサイズの平均を計算した結果、平均サイズが幅１６０ラインを超えることが判明したため、区間１１の幅を拡張して３２０ラインとしている。このとき、区間１２は区間１１によってオーバーライドされる。この結果、該ページにおける区間の定義は、区間１、２、…１０、１１、１３となる。なお、図中、検査の対象となるオブジェクトは、区間１１内に存在する図形、及び区間１１における下ラインにかかっている図形である。区間１１における上ラインに掛かっている図形は検査の対象外としている。この定義（ルール）に従って、ページ上の各区間における平均オブジェクトサイズを一意に算出する。
【００５１】
図２４は、第３の実施例におけるエッジ情報抽出処理の流れを示す図である。まず、エッジ抽出処理部１３は、オブジェクト（図形）が入力されると不図示のカウンタにより１ページ内のオブジェクト（図形）の総数Ｎをカウントする。そして、エッジ抽出処理部１３は、カウントされた総数Ｎと予め設定された閾値Ｔ１とを比較する。その結果、ページ内に存在するオブジェクト数Ｎが閾値Ｔ１より多いと判断した場合には、エッジ抽出処理部１３は、エッジ情報生成処理として、スキャンラインによるエッジ検出処理（図２参照）を行い、エッジ情報を生成する。
【００５２】
一方、ページ内に存在するオブジェクト数Ｎが閾値Ｔ１以下であると判断した場合には、エッジ抽出処理部１３は、各オブジェクト（図形）に付加されている図形種識別情報に基づいて処理手法を切り替えてエッジ検出処理を行い、エッジ情報を生成する。第３の実施例では、図形種識別情報は拡張情報として各オブジェクト毎に設定されている。エッジ抽出処理部１３は、各オブジェクトに対して拡張情報の有無を検査し、拡張情報が無い場合はデフォルトの処理（スキャンラインによるエッジ検出処理）を行い、エッジ情報を生成する。一方、拡張情報が存在する場合には、エッジ抽出処理部１３は、記録されている図形種識別情報を参照して処理手法を切り替える。例えば、図形種識別情報がＩＤ−１である場合には、エッジ抽出処理部１３は、三角形に対する処理を行い、第１の実施例のような処理手順でエッジ情報抽出処理を行う。また、例えば図形種識別情報としてＩＤ−２が付与されている図形（水平又は垂直方向に対称性がある図形）の場合には、エッジ抽出処理部１３は、第２の実施例で説明したＩＤ−２系の処理手順でエッジ情報抽出処理を行う。また、例えば図形種識別情報としてＩＤ−３が付与されている図形（回転や変形が施されている多角形等）の場合には、エッジ抽出処理部１３は、第２の実施例で説明したＩＤ−３系の処理手順でエッジ情報抽出処理を行う。なお、拡張情報が存在してもオブジェクト数が特性ＤＢの閾値Ｔｘより多い場合には、デフォルトの処理（スキャンラインによるエッジ検出処理）を行い、エッジ情報を生成する。
【００５３】
（その他の実施例）
第３の実施例では、特性ＤＢをプリンタドライバ側に設けるようにしているが、プリンタ装置側に設けるようにしても良い。また、予め測定したデータをスタティックに持つだけに限らず、プリンタ装置側の実行処理時間を適宜測定し、特性ＤＢに格納するデータを更新するようにしても良い。
さらにはプリンタ装置側とドライバ装置側で同じ特性ＤＢ（同期した特性ＤＢ）を持つように相互に通信し、ステータスの確認やデータの転送を行うように構成しても良い。本実施例によれば図形種の違いを判定するために用いる図形種識別情報を定義しているが、アプリケーション側で該情報を付与しても良いし、プリンタドライバ側で該情報を付与しても良い。図形種識別情報の種類と対応するエッジ抽出処理の手続きの整合性をとるために、アプリケーション、プリンタドライバ、及びプリンタ装置の間で、予め定められた通信プロトコルによって適宜情報の伝達（又は通信等）を行うよう構成しても良い。
前述の各構成において、プリントジョブ生成の際にプリンタ毎に適したＩＤ情報を付加し、プリンタ機種が変更になった場合でも、適切なＩＤ情報に切り替えられるように、付加するＩＤ情報とプリンタ機種の対応を内部で管理する機構を持つようにしても良い。
【００５４】
（本発明の他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【００５５】
例えば、本実施形態に示した画像処理装置は、図２５に示すようなコンピュータ機能７００を有し、そのＣＰＵ７０１により本実施形態での動作が実施される。
コンピュータ機能７００は、図２５に示すように、ＣＰＵ７０１と、ＲＯＭ７０２と、ＲＡＭ７０３とを備える。また、操作部（ＣＯＮＳ）７０９のコントローラ（ＣＯＮＳＣ）７０５と、ＣＲＴやＬＣＤ等の表示部としてのディスプレイ（ＤＩＳＰ）７１０のディスプレイコントローラ（ＤＩＳＰＣ）７０６とを備える。さらに、ハードディスク（ＨＤ）７１１、及びフレキシブルディスク等の記憶デバイス（ＳＴＤ）７１２のコントローラ（ＤＣＯＮＴ）７０７と、ネットワークインタフェースカード（ＮＩＣ）７０８とを備える。それら機能部７０１、７０２、７０３、７０５、７０６、７０７、７０８は、システムバス７０４を介して互いに通信可能に接続された構成としている。
ＣＰＵ７０１は、ＲＯＭ７０２又はＨＤ７１１に記憶されたソフトウェア、又はＳＴＤ７１２より供給されるソフトウェアを実行することで、システムバス７０４に接続された各構成部を総括的に制御する。すなわち、ＣＰＵ７０１は、前述したような動作を行うための処理プログラムを、ＲＯＭ７０２、ＨＤ７１１、又はＳＴＤ７１２から読み出して実行することで、本実施形態での動作を実現するための制御を行う。ＲＡＭ７０３は、ＣＰＵ７０１の主メモリ又はワークエリア等として機能する。
ＣＯＮＳＣ７０５は、ＣＯＮＳ７０９からの指示入力を制御する。ＤＩＳＰＣ７０６は、ＤＩＳＰ７１０の表示を制御する。ＤＣＯＮＴ７０７は、ブートプログラム、種々のアプリケーション、ユーザファイル、ネットワーク管理プログラム、及び本実施形態における前記処理プログラム等を記憶するＨＤ７１１及びＳＴＤ７１２とのアクセスを制御する。ＮＩＣ７０８はネットワーク７１３上の他の装置と双方向にデータをやりとりする。
【００５６】
なお、前記実施形態は、何れも本発明を実施するにあたっての具体化のほんの一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【産業上の利用可能性】
【００５７】
本発明はプリンタ装置、又はディスプレイ等の表示装置、画像出力デバイスなどに利用することができる。
【符号の説明】
【００５８】
１１…入力部、１２…分類部、１３…エッジ抽出処理部、１４…エッジ検出処理部、１５…エッジ情報生成部
【特許請求の範囲】
【請求項１】
レンダリング処理を行う画像処理装置であって、
オブジェクトの情報を入力する入力手段と、
前記入力手段より入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類手段と、
前記分類手段により分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理手段とを有することを特徴とする画像処理装置。
【請求項２】
前記処理手段は、前記分類手段により分類された図形種に応じた処理手順でエッジ検出を行うエッジ検出処理手段と、
前記エッジ検出処理手段での処理結果に基づいて、前記エッジ情報を生成するエッジ情報生成手段とを有することを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記分類手段は、入力されるオブジェクトの情報に基づいて、前記オブジェクトの図形種を第１の図形種又は第２の図形種に分類し、
前記処理手段は、前記第１の図形種に分類されたオブジェクトについてはタイル処理によるエッジ検出を行って前記エッジ情報を生成し、前記第２の図形種に分類されたオブジェクトについてはスキャンラインによるエッジ検出を行って前記エッジ情報を生成することを特徴とする請求項１又は２記載の画像処理装置。
【請求項４】
前記タイル処理によるエッジ検出では、レンダリング空間におけるタイルの位置を特定し、特定されたそれぞれのタイルにて前記オブジェクトの辺との交点を算出し、算出された交点の情報に基づき前記エッジ情報を、予め計算しておいたデータベースから検索してエッジ情報を生成することを特徴とする請求項３記載の画像処理装置。
【請求項５】
前記分類手段は、入力されるオブジェクトの情報に基づいて、前記オブジェクトの辺の数が３又は４である場合には、当該オブジェクトを第１の図形種に分類することを特徴とする請求項３又は４記載の画像処理装置。
【請求項６】
前記分類手段は、入力されるオブジェクトの情報に基づいて、前記オブジェクトが対称図形である場合には、当該オブジェクトを第１の図形種に分類することを特徴とする請求項３〜５の何れか１項に記載の画像処理装置。
【請求項７】
前記処理手段は、処理単位内の前記オブジェクトの数が予め定めた閾値より多い場合には、前記分類手段により分類された図形種にかかわらず、スキャンラインによるエッジ検出を行って前記エッジ情報を生成することを特徴とする請求項１〜６の何れか１項に記載の画像処理装置。
【請求項８】
請求項１〜７の何れか１項に記載の画像処理装置を有し、
プリントジョブを生成する際に、前記オブジェクトの図形種に関する情報を付加することを特徴とするプリントシステム。
【請求項９】
レンダリング処理を行う画像処理方法であって、
オブジェクトの情報を入力する入力工程と、
前記入力工程にて入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類工程と、
前記分類工程にて分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理工程とを有することを特徴とする画像処理方法。
【請求項１０】
レンダリング処理に係る画像処理をコンピュータに実行させるためのプログラムであって、
オブジェクトの情報を入力する入力ステップと、
前記入力ステップにて入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類ステップと、
前記分類ステップにて分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理ステップとをコンピュータに実行させるためのプログラム。
【請求項１】
レンダリング処理を行う画像処理装置であって、
オブジェクトの情報を入力する入力手段と、
前記入力手段より入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類手段と、
前記分類手段により分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理手段とを有することを特徴とする画像処理装置。
【請求項２】
前記処理手段は、前記分類手段により分類された図形種に応じた処理手順でエッジ検出を行うエッジ検出処理手段と、
前記エッジ検出処理手段での処理結果に基づいて、前記エッジ情報を生成するエッジ情報生成手段とを有することを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記分類手段は、入力されるオブジェクトの情報に基づいて、前記オブジェクトの図形種を第１の図形種又は第２の図形種に分類し、
前記処理手段は、前記第１の図形種に分類されたオブジェクトについてはタイル処理によるエッジ検出を行って前記エッジ情報を生成し、前記第２の図形種に分類されたオブジェクトについてはスキャンラインによるエッジ検出を行って前記エッジ情報を生成することを特徴とする請求項１又は２記載の画像処理装置。
【請求項４】
前記タイル処理によるエッジ検出では、レンダリング空間におけるタイルの位置を特定し、特定されたそれぞれのタイルにて前記オブジェクトの辺との交点を算出し、算出された交点の情報に基づき前記エッジ情報を、予め計算しておいたデータベースから検索してエッジ情報を生成することを特徴とする請求項３記載の画像処理装置。
【請求項５】
前記分類手段は、入力されるオブジェクトの情報に基づいて、前記オブジェクトの辺の数が３又は４である場合には、当該オブジェクトを第１の図形種に分類することを特徴とする請求項３又は４記載の画像処理装置。
【請求項６】
前記分類手段は、入力されるオブジェクトの情報に基づいて、前記オブジェクトが対称図形である場合には、当該オブジェクトを第１の図形種に分類することを特徴とする請求項３〜５の何れか１項に記載の画像処理装置。
【請求項７】
前記処理手段は、処理単位内の前記オブジェクトの数が予め定めた閾値より多い場合には、前記分類手段により分類された図形種にかかわらず、スキャンラインによるエッジ検出を行って前記エッジ情報を生成することを特徴とする請求項１〜６の何れか１項に記載の画像処理装置。
【請求項８】
請求項１〜７の何れか１項に記載の画像処理装置を有し、
プリントジョブを生成する際に、前記オブジェクトの図形種に関する情報を付加することを特徴とするプリントシステム。
【請求項９】
レンダリング処理を行う画像処理方法であって、
オブジェクトの情報を入力する入力工程と、
前記入力工程にて入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類工程と、
前記分類工程にて分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理工程とを有することを特徴とする画像処理方法。
【請求項１０】
レンダリング処理に係る画像処理をコンピュータに実行させるためのプログラムであって、
オブジェクトの情報を入力する入力ステップと、
前記入力ステップにて入力されたオブジェクトの情報に基づいて、前記オブジェクトの図形種を分類する分類ステップと、
前記分類ステップにて分類された図形種に応じて処理手順を切り替え、前記レンダリング処理に係るエッジ情報を生成する処理ステップとをコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【公開番号】特開２０１１−３４１３９（Ｐ２０１１−３４１３９Ａ）
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願番号】特願２００９−１７６９２８（Ｐ２００９−１７６９２８）
【出願日】平成２１年７月２９日（２００９．７．２９）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願日】平成２１年７月２９日（２００９．７．２９）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]