(57)【要約】【課題】  描画オブジェクトの輪郭を示す複数のエッジのうちの１つのエッジを、エッジの座標に基づいて並べ替える際に、その１つのエッジを並び替えるためのエッジどうしの座標の比較が開始されるエッジを、その１つのエッジの座標に基づいて特定する。【解決手段】  描画オブジェクトの輪郭を示す複数のエッジのうちの１つのエッジを、エッジの座標に基づいて並べ替える際に、その１つのエッジを並び替えるためのエッジどうしの座標の比較が開始されるエッジを、その１つのエッジの座標に基づいて特定する。【選択図】  図５
2018063557.tif 000002
【特許請求の範囲】
【請求項１】
ページに含まれるオブジェクトをライン単位で描画する画像形成装置であって、
処理対象のラインに含まれるオブジェクトのエッジを、エッジどうしの座標を比較することで座標に関して昇順にソートするソート手段と、
前記ソート手段によって並べられたエッジに基づいてエッジ間の描画を行う描画手段と、
を有し、
前記ソート手段は、
前記処理対象のラインにおいて既にソートされている複数のエッジに対して当該処理対象のラインにおける別のエッジをソートするための座標の比較を、当該別のエッジの座標に基づいて特定される前記複数のエッジのうちの１つのエッジとの座標の比較から開始することを特徴とする画像形成装置。
【請求項２】
ページに含まれるオブジェクトをライン単位で描画する画像形成装置であって、
処理対象のラインに含まれるオブジェクトのエッジを座標に関して昇順に並べるソート処理を行うソート手段と、
前記ソート手段によって並べられたエッジに基づいて、エッジ間の描画を行う描画手段と、
を有し、
前記ソート手段は、
前記処理対象のラインを複数の区間に分割した区間ごとに、各区間に含まれる少なくとも１つのエッジと各区間を関連付けた情報を記憶でき、
前記処理対象のラインにおける１つのエッジの座標に対応する区間に関連付けられたエッジを、前記情報を用いて特定し、
当該１つのエッジの座標と、前記特定されたエッジの座標とを比較することで、当該１つのエッジに関しての前記ソート処理を行うことを特徴とする画像形成装置。
【請求項３】
前記情報は、前記ソート処理に対応して更新されることを特徴とする請求項２に記載の画像形成装置。
【請求項４】
前記情報は、各区間に含まれるエッジのうちで最後にアクセスされたエッジを特定するための情報であることを特徴とする請求項２に記載の画像形成装置。
【請求項５】
前記情報は、各区間に含まれる端のエッジを特定するための情報であることを特徴とする請求項２に記載の画像形成装置。
【請求項６】
前記区間は複数画素単位であることを特徴とする請求項２に記載の画像形成装置。
【請求項７】
前記区間は画素単位であることを特徴とする請求項２に記載の画像形成装置。
【請求項８】
ページに含まれるオブジェクトをライン単位で描画する方法であって、
処理対象のラインに含まれるオブジェクトのエッジを、エッジどうしの座標を比較することで座標に関して昇順にソートするソート工程と、
前記ソート工程によって並べられたエッジに基づいてエッジ間の描画を行う描画工程と、
を有し、
前記ソート工程は、
前記処理対象のラインにおいて既にソートされている複数のエッジに対して当該処理対象のラインにおける別のエッジをソートするための座標の比較を、当該別のエッジの座標に基づいて特定される前記複数のエッジのうちの１つのエッジとの座標の比較から開始することを特徴とする方法。
【請求項９】
ページに含まれるオブジェクトをライン単位で描画する方法であって、
処理対象のラインに含まれるオブジェクトのエッジを座標に関して昇順に並べるソート処理を行うソート工程と、
前記ソート工程によって並べられたエッジに基づいて、エッジ間の描画を行う描画工程と、
を有し、
前記ソート工程は、
前記処理対象のラインを複数の区間に分割した区間ごとに、各区間に含まれるエッジと各区間を関連付けた情報を記憶でき、
前記処理対象のラインにおける１つのエッジを、当該エッジの座標に対応する区間に関連付けられたエッジを、前記情報を用いて特定し、
当該１つのエッジの座標と、前記特定されたエッジの座標とを比較することで、当該１つのエッジに関しての前記ソート処理を行うことを特徴とする方法。
【請求項１０】
前記情報は、処理対象のラインが変わるたびに更新されることを特徴とする請求項９に記載の方法。
【請求項１１】
前記情報は、各区間に含まれるエッジのうちで最後にアクセスされたエッジを特定するための情報であることを特徴とする請求項９に記載の方法。
【請求項１２】
前記情報は、各区間に含まれる端のエッジを特定するための情報であることを特徴とする請求項９に記載の方法。
【請求項１３】
前記区間は複数画素単位であることを特徴とする請求項９に記載の方法。
【請求項１４】
前記区間は画素単位であることを特徴とする請求項９に記載の方法。
【請求項１５】
請求項９乃至１４の何れか１項に記載の方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像形成装置、方法、プログラムに関するものである。特に画像形成処理における描画オブジェクトのエッジの処理に関する。
【背景技術】
【０００２】
ページに含まれる描画オブジェクト（以下、オブジェクト）を描画する方法には様々な方法がある。特許文献１は、オブジェクトをページのライン単位で描画して、そのページのビットマップ画像を生成する方法を開示する。この方法は、処理対象のラインに現れるオブジェクトのエッジを座標に関して昇順に並べる。そして、それぞれのエッジ間の塗り（エッジ間の各画素の色）に寄与するオブジェクトを特定し、特定されたオブジェクトの塗りに基づいて決定された色をエッジ間の各画素の色とする。
【０００３】
上記のエッジを並べる処理（エッジソート処理）は、各エッジに対して、エッジのライン上の座標を計算し、エッジの座標どうしを比較することで座標の大小関係を判定し、座標が昇順となるように各エッジを並べる。例えば、ある１つのエッジを、すでに昇順に並べられている他の複数のエッジの中に追加するエッジソート処理は、その１つのエッジの座標と他のエッジの座標との比較を、他の複数エッジの中の最小座標を持つエッジから順に行う。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−２１６９６０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のエッジソート処理では、走査線上に大量のオブジェクトが存在する場合、エッジの座標どうしを比較する回数が膨大になってしまい、エッジソート処理に要する時間が膨大になってしまうことがある。例えば、最大座標を持つエッジを追加する際に、既に並べられている他のエッジのうちの最小座標を持つエッジから順にエッジ座標どうしの比較を行う場合を考える。この場合に、追加すべきエッジの座標は、他のエッジの全てのエッジの座標と比較されることになり、他のエッジの一部の座標のみと比較される場合よりも、エッジソート処理に時間がかかる。
【課題を解決するための手段】
【０００６】
本発明の画像形成装置は、ページに含まれるオブジェクトをライン単位で描画する画像形成装置であって、処理対象のラインに含まれるオブジェクトのエッジを、エッジどうしの座標を比較することで座標に関して昇順にソートするソート手段と、前記ソート手段によって並べられたエッジに基づいてエッジ間の描画を行う描画手段と、を有し、前記ソート手段は、前記処理対象のラインにおいて既にソートされている複数のエッジに対して当該処理対象のラインにおける別のエッジをソートするための座標の比較を、当該別のエッジの座標に基づいて特定される前記複数のエッジのうちの１つのエッジとの座標の比較から開始することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、オブジェクトのエッジのソート処理を高速に実現する事が可能となる。
【図面の簡単な説明】
【０００８】
【図１】本実施形態の画像形成装置のハードウェア構成を示す図。
【図２】画像形成装置のソフトウェア構成を示した図。
【図３】画像形成処理の詳細なフローを示す図。
【図４】エッジブロックテーブル及びエッジテーブルの概念図。
【図５】所定ライン時の、エッジブロックテーブルの概念図。
【図６】新規エッジ追加処理の詳細なフローを示す図。
【図７】分割領域ソート処理の詳細なフローを示す図。
【図８】エッジブロックテーブルを利用した分割領域ソート処理の説明図。
【図９】エッジブロックテーブルを利用した分割領域ソート処理の説明図。
【図１０】追加済みエッジソート処理の詳細なフローを示す図。
【図１１】エッジブロックテーブルを利用した追加済みエッジソート処理図。
【図１２】エッジブロックテーブル１、２及びエッジテーブルの概念図。
【図１３】エッジブロックテーブル１、２を利用した分割領域ソート処理の詳細を示すフロー図。
【発明を実施するための形態】
【０００９】
（第１の実施形態）
本実施形態のシステム構成の例を示す図である。本システムでは、ホストコンピュータ（パーソナルコンピュータやサーバーコンピューター）と画像形成装置（印刷機能を持つ装置、プリンター）１１０がＬＡＮ経由で接続する構成とする。
【００１０】
ユーザは、まずホストコンピュータ上で、印刷するページ情報を示すＰＤＬ（Ｐａｇｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ）で記述された印刷データ（ＰＤＬデータ）を生成し、画像形成装置１１０に転送する。画像形成装置１１０は、転送されたＰＤＬデータに基づき、印刷処理を行う。本画像形成装置は、ＭＦＰ（Ｍｕｌｔｉ  Ｆｕｎｃｔｉｏｎ  Ｐｅｒｉｐｈｅｒａｌ）、ＳＦＰ（Ｓｉｎｇｌｅ  Ｆｕｎｃｔｉｏｎ  Ｐｒｉｎｔｅｒ  ）のうち、いずれのプリンタであってもよい。また、画像処理装置は、ＭＦＰ、ＳＦＰ以外のプリンタであってもよい。
【００１１】
図１を用いて、本実施形態の画像形成装置１１０の詳細なハードウェア構成について説明する。図１において、画像形成装置１１０は、画像出力デバイスであるプリンタ部１１１を保持する。プリンタ部１１１は、電子写真方式やインクジェット方式などシートに画像を印刷できる方式であればよい。また、画像形成装置１１０は、ＬＡＮと接続することで、ＰＤＬデータやデバイス情報をＬＡＮ経由で入出力するための制御を行う。プリンタ部１１１はデバイスＩ／Ｆ２３２と結合され、画像形成装置１１０で生成された画像データに基づいて画像を紙などのシートに印刷する処理を行う。ＣＰＵ２２０は画像形成装置全体を制御するための中央処理部である。ＣＰＵ２２０は、１つまたは複数のプロセッサーで構成されているシングルコアＣＰＵでもマルチコアＣＰＵでも良い。ＲＡＭ２２２は、ＣＰＵ２２０が動作するためのシステムワークメモリである。例えば、ＲＡＭ２２２は、ＣＰＵ２２０がＰＤＬデータを中間データ（ディスプレイリスト）に変換する際のワークメモリとして用いられる。変換された中間データはＲＡＭ２２２に一時的に保持される。ＲＯＭ２２１はブートＲＯＭであり、システムのブートプログラムが格納されている。記憶装置２２３はハードディスクドライブであり、各種処理のためのシステムソフトウェア及び送信されたＰＤＬデータ、ビットマップデータを格納する構成である。
【００１２】
操作部Ｉ／Ｆ２２５は、各種メニューや印刷データ情報等を表示可能な表示画面を有する操作部１１３に対するインタフェース部であり、操作部１１３に対して操作画面データを出力する。また、操作部Ｉ／Ｆ２２５は、操作部１１３から操作者が入力した情報をＣＰＵ２２０に伝える役割をする。ネットワークＩ／Ｆ２２６は、ＬＡＮに接続して外部装置との間で情報の入出力を行う。以上のユニットがシステムバス２２７上に配置されている。イメージバスＩ／Ｆ２２８は、システムバス２２７と画像データを高速で転送する画像バス２３０と接続するためのインタフェースであり、データ構造を変換するバスブリッジである。
【００１３】
画像バス２３０上には、ＲＩＰ（ラスタイメージプロセッサー）２３１、デバイスＩ／Ｆ２３２が接続される。ＲＩＰ２３１は、ＣＰＵ２２０がＰＤＬデータから変換した中間データ（ディスプレイリスト）に基づいて、図３に示される画像形成処理（レンダリング処理）を行うことで、ビットマップデータを生成する。ＲＩＰ２３１は、ソフトウェア及びハードウェアのどちらで実現されても良い。つまり、ＲＩＰ２３１は、１つまたは複数のプロセッサーで構成されても、ＡＳＩＣなどの電子回路で構成されても、プロセッサーと電子回路との組合せで構成されても良い。本実施形態でＲＩＰ２３１は、１つまたは複数のプロセッサーが、ＲＩＰ２３１が備える不図示のメモリに格納されたソフトウェアプログラムを読み出すことで動作する。デバイスＩ／Ｆ２３２は、プリンタ部１１１と画像形成装置１１０とを接続し、画像データの同期系／非同期系の変換を行う。
【００１４】
＜画像形成装置におけるソフトウェア構成＞
図２は、本実施形態における画像形成装置１１０の、ソフトウェア構成を示した図である。
【００１５】
ＰＤＬデータ処理部（２０１）は、ネットワークＩ／Ｆ２２６で受信したＰＤＬデータを解釈することで、ページに含まれるオブジェクトの情報を取得し、取得されたオブジェクトの情報を中間データ生成部に渡す処理を行う。中間データ生成部（２０２）は、ＰＤＬデータ処理部（２０１）から渡されるオブジェクト情報を元に、画像形成処理（レンダリング処理）に利用する中間データ（２２０）を生成する。中間データには、各オブジェクトについて、輪郭形状を示す情報（エッジ）が含まれる。そして各エッジには、エッジに対応するオブジェクトの塗り（例えば、色やビットマップ）が関連付けられている。中間データにおいては、例えば赤い矩形オブジェクトは、その矩形の左右のエッジと、それらエッジに関連付けられる、そのエッジ間が赤色で塗られることを示す情報で表される。また中間データに含まれる各エッジは、ページ上の位置情報を持つ。中間データ（２２０）はＲＡＭ２２２に一時的に保持される。なおＰＤＬデータ処理部（２０１）および、中間データ生成部（２０２）は、ＣＰＵ２２０がＲＯＭ２２１に記憶されたプログラムを読み出して実行することで実現される。
【００１６】
画像形成処理部（２０３）は、中間データ（２２０）に基づいて、各ページのビットマップデータを生成する。画像形成処理部（２０３）は、図２に示すように画像形成に必要な各手段（２１０〜２１２）を保持する。各手段は、対応するプログラムを実行するそれぞれ別のプロセッサーであっても、１つのプロセッサーであっても良く、また、電子回路単独で実現されていても、電子回路とプロセッサーとの組合せで実現されていても良い。なお以下の追加済みエッジソート手段（２１０）および新規エッジ追加手段（２１１）は、ソート手段としてまとめられる。
【００１７】
追加済みエッジソート手段（２１０）は、ページ中の処理対象のライン（以下、走査線と呼ぶ）の画像形成処理を行う際に、中間データ（２２０）に基づいて、直前の走査線から引き続き処理対象の走査線上に現れるオブジェクトのエッジの座標を計算する。そして、それらエッジの座標が昇順に並ぶように走査線上のエッジをソートする。各エッジはエッジテーブル（２２２）によって管理され、ソート処理によって逐次更新されていく。
【００１８】
新規エッジ追加手段（２１１）は、処理対象の走査線についての画像形成処理を行う際に、中間データ（２２０）に基づいて、直前の走査線上には現れていないが、処理対象の走査線から新たに現れるオブジェクトのエッジを特定し、その座標を計算する。そして新規エッジ追加手段（２１１）は、この新規エッジの座標に基づいて、エッジテーブル（２２２）で管理されているエッジに対して、座標が昇順となるように新規エッジを追加する。
【００１９】
なお、以上の追加済みエッジソート手段（２１０）および新規エッジ追加手段（２１１）が、後述するエッジブロックテーブル（２２１）を用いてソート処理を行うのが本実施形態の特徴の１つである。ソート処理の詳細は後述する。
【００２０】
エッジ間描画手段（２１２）は、処理対象の走査線について、エッジテーブル（２２２）で管理されているエッジの情報に基づいて各オブジェクトを描画する。本実施形態では、エッジ間描画手段（２１２）は、処理対象の走査線について座標が昇順となるように並べられた、エッジテーブル（２２２）で管理されている各エッジを参照し、各エッジ間を塗りつぶす。具体的には、各エッジ間の色を各々のエッジに関連付けられている色の情報に基づいて決定し、その色でエッジ間を塗りつぶすことで、処理対象の走査線の描画処理を行う。以上がエッジ間描画処理である。このエッジ間描画処理は、公知の方法でよい。
【００２１】
本実施形態の特徴であるエッジブロックテーブル（２２１）およびエッジテーブル（２２２）については図４、５を用いて次で説明する。
【００２２】
＜エッジブロックテーブル（２２１）とエッジテーブルの（２２２）の概念図＞
エッジテーブル（２２２）は、図４に示されるような情報である。すなわち、処理対象の走査線に現れるオブジェクトのエッジをエッジＩＤによって管理し、エッジＩＤで示される各エッジは、以下の情報（エッジＩｎｆｏ）を持つ。この情報はエッジの走査線上の座標（Ｘ座標）（Ｃｕｒｒｅｎｔ＿Ｘ）、エッジの傾き（ＤＸ／ＤＹ）を割り当てて、Ｘ座標に関して前後に位置するエッジＩＤ（ｐｒｅｖ＿ｅｄｇｅ＿ｉｄ、ｎｅｘｔ＿ｅｄｇｅ＿ｉｄ）を含む。なおエッジのＸ座標とは処理対象の走査線上の座標のことであり、エッジの傾きとは処理対象の走査線を次の走査線に移した時にエッジの座標がＸ方向に幾ら変位するかを示す情報である。この情報によって、処理対象の走査線に現れる各オブジェクトのエッジは、Ｘ座標で昇順となるように繋がれた状態（リンクされた状態）で管理されている。例えば、エッジＩＤ１のｐｒｅｖ＿ｅｄｇｅ＿ｉｄが４、ｎｅｘｔ＿ｅｄｇｅ＿ｉｄが２であれば、エッジＩＤ１、２、４の３つのエッジ（エッジ１、２、４）は、エッジ４、エッジ１、エッジ２の順でＸ座標に関して昇順にリンクされていることになる。このように、複数のエッジがＸ座標に関して昇順にリンクされていることを、複数のエッジがＸ座標に関して昇順にソートされている、という。なおエッジテーブル（２２２）には、新規エッジ追加手段（２１１）が処理対象のラインに新たなオブジェクトが現れた場合に、そのオブジェクトに対応するエッジが新しいＩＤが付与されて追加される。
【００２３】
また、エッジブロックテーブル（２２１）は、図４に示されるような情報である。すなわち、ページが所定サイズの複数のブロック（領域あるいは区間）に分割された場合の各領域（区間）について、それぞれの分割領域の位置に対応する座標を有するエッジを特定する情報（エッジＩＤ）がエッジブロックテーブルに記憶可能である。つまり、エッジブロックテーブル（２２１）は、各分割領域と、その分割領域に含まれるエッジ（エッジＩＤ）とを関連付ける役割を果たす。例えば、ページ領域を左から右に向かって、各分割領域を分割領域１、２、３、４、５とした場合に、図４に示されるエッジブロックテーブル（２２１）は、分割領域１に含まれるエッジとしてエッジ６を特定する。同様に、分割領域２、３、５について、エッジ４、１、２がそれぞれ特定される。なお分割領域４については、含まれるエッジが存在しないため空き（Ｎｕｌｌ）となっている。なお、本実施形態では、１つの分割領域について、１つのエッジＩＤが関連付けられているが、１つの分割領域について複数のエッジＩＤが関連付けられていても良い。
【００２４】
図５は、ページ画像（５００）に対して処理対象のライン（５０１）を処理する際の、エッジブロックテーブル（２２１）の状態の概念図である。例えばページの分割サイズを２５６ピクセル（複数画素単位）とする場合、図５に示されるページ画像（５００）は分割領域１〜５（５０２〜５０６）に分割される。分割領域１は、座標０〜２５５の範囲に対応し、この範囲内の座標を持つエッジが関連付けられる。エッジブロックテーブル（２２１）はこの関連付け情報を保持するものである。同様に分割領域２、３、４、５のそれぞれは、座標２５６〜５１１、５１２〜７６７、７６８〜１０２３、１０２４〜１２７９のそれぞれの範囲に対応している。そしてエッジブロックテーブル（２２１）において、各分割領域には、対応する範囲内の座標を持つエッジが関連付けられる。
【００２５】
なお図５に示されるページ画像（５００）は、オブジェクト１〜５（５１１〜５１４）を含む。各オブジェクトは、中間データにおいて、エッジ（ＩＤ＝１〜８）（５２１〜５２８）で表現されている。この場合、エッジＩＤ５、６のエッジ（５２５）、（５２６）は、分割領域１（５０２）に含まれ、図５のエッジテーブル（２２２）で示すように走査線上で座標に関して昇順になるようリンク構造で管理される。そして、分割領域１（５０２）についてのエッジブロックテーブル（２２１）には、エッジＩＤ＝６のエッジ（５２６）が関連付けられて格納される。
【００２６】
本実施形態におけるエッジブロックテーブル（２２１）の各分割領域へのエッジの関連付けルールは、それぞれの分割領域において最後にアクセスされた（ソート処理された）エッジのＩＤが格納される。分割領域２、３、４、５に関しても同様である。なお、別の実施形態として、最後にアクセスされたエッジのＩＤではなく、各分割領域に含まれるエッジのうちで座標が最小のエッジ（つまり各分割領域で左端のエッジ）のＩＤを格納するようにしても良い。この場合、図５の例では、分割領域１、２、３、５に関連付けられるそれぞれのエッジはエッジＩＤ５、３、１、２となる。
【００２７】
以上のエッジブロックテーブル（２２１）およびエッジテーブル（２２２）は、ＲＩＰ２３１の不図示のメモリに格納され、ＲＩＰ２３１の追加済みエッジソート手段（２１０）および新規エッジ追加手段（２１１）のエッジソート処理において利用される。
【００２８】
＜画像形成装置における転送されたＰＤＬデータの印刷処理及びレンダリング処理の詳細＞
本実施形態における画像形成装置１１０上の、ＣＰＵ２２０によって実行される、ユーザが送信するＰＤＬデータの印刷処理の一連の処理を説明する。まずＣＰＵ２２０は、実行するためのプログラムをＲＯＭ２２１からＲＡＭ２２２へロードし、実行する。これにより、画像形成装置１１０はＣＰＵ２２０に対し、前述したＰＤＬデータの印刷処理の一連の処理を実行させることになる。まず、ＣＰＵ２２０は、ホストコンピュータから受信したＰＤＬデータを、記憶装置２２３に格納する。次にＣＰＵ２２０は、送信されたＰＤＬデータの解析処理を行う。次にＣＰＵ２２０は、解析したＰＤＬデータの解析情報を元に、ビットマップ画像の生成のために必要な中間データ（２２０）の生成処理を行う。次にＣＰＵ２２０は、前記生成した中間データ（２２０）に基づいて画像形成処理（レンダリング処理）を行い、ページ画像を表すビットマップデータを生成する。
【００２９】
図３は、本実施形態のＲＩＰ（２３１）によって行われる画像形成処理（レンダリング処理）の詳細なフローを示す図である。このフローチャートの処理Ｓ３０１〜Ｓ３０４は、処理対象の走査線ごとに繰返し行われる。
【００３０】
Ｓ３０１においてＲＩＰ（２３１）の追加済みエッジソート手段（２１０）は、エッジブロックテーブル（２２１）及びエッジテーブル（２２２）の情報を用いて、図１０に示される追加済みエッジソート処理を行う。追加済みエッジソート処理は、直前の走査線から引き続き現れているエッジ（つまりエッジテーブル（２２２）で既に管理されているエッジ）を、座標に関して昇順に並び変える処理である。
【００３１】
次に、Ｓ３０２においてＲＩＰ（２３１）の新規エッジ追加手段（２１１）は、中間データ（２２０）、エッジブロックテーブル（２２１）及びエッジテーブル（２２２）の情報を用いて、図６に示される新規エッジ追加処理を行う。
【００３２】
次に、Ｓ３０３においてＲＩＰ（２３１）のエッジ間描画手段（２１２）は、上述したエッジ間描画処理を行う。
【００３３】
次に、Ｓ３０４において、ＲＩＰ（２３１）のエッジ間描画手段（２１２）は、ページの全ての走査線について、エッジ間描画処理が行われたかを判定し、全ての走査線について処理が完了していれば（Ｓ３０５でＹｅｓ）、本フローチャートの処理を終了する。そうでなければ（Ｓ３０５でＮｏ）、エッジ間描画手段（２１２）は、次の走査線を処理対象として、追加済みエッジソート手段（２１０）および新規エッジ追加手段（２１１）に各処理を行わせる。このように、本実施形態の画像形成処理は、ページに含まれるオブジェクトを走査線ごとに（ライン単位で）描画する。
【００３４】
＜新規エッジ追加処理（Ｓ３０２）の詳細＞
図６は、本実施形態における図３で示した新規エッジ追加処理（Ｓ３０２）の詳細なフローを示す図である。本処理は、中間データ（２００）を参照して、処理対象の走査線から現れることになったオブジェクトのエッジを特定し、そのエッジをエッジテーブル（２２２）に、座標に関して昇順となるように追加する処理である。
【００３５】
まず、Ｓ６０１において新規エッジ追加手段（２１１）は、中間データを参照することで、処理対象の走査線上に追加が必要な新規のエッジが存在するか否かを判断する。新規のエッジが存在すると判断した場合、Ｓ６０２に進む。また新規のエッジが存在しないと判断した場合、本フローを終了する。
【００３６】
Ｓ６０２において新規エッジ追加手段（２１１）は、中間データ（２２０）から新規のエッジの位置情報を取得する。この位置情報は、新規追加するエッジの開始Ｘ座標と、各エッジの傾き情報を示すＤＸ／ＤＹである。そして新規エッジ追加手段（２１１）は、取得したエッジの開始Ｘ座標と、各エッジの傾き情報を示すＤＸ／ＤＹを該当するエッジＩＤの示すエッジテーブル（２２２）に格納する。なお、この開始Ｘ座標は、Ｃｕｒｒｅｎｔ＿Ｘに格納される。
【００３７】
次にＳ６０３において新規エッジ追加手段（２１１）は、新規エッジの処理対象の走査線における座標を、エッジテーブル（２２２）のＣｕｒｒｅｎｔ＿Ｘから取得する。
【００３８】
次にＳ６０４において新規エッジ追加手段（２１１）は、取得された座標の値と、エッジブロックテーブル（２２１）を用いて、図７に示される分割領域ソート処理を行う
そして処理はＳ６０１に戻る。
【００３９】
＜分割領域ソート処理（Ｓ６０４）の詳細＞
図７は、本実施形態における図６で示した分割領域ソート処理（Ｓ６０４）の詳細なフローを示す図である。また図８及び図９は、エッジブロックテーブル（２２１）を利用した分割領域ソート処理（Ｓ６０４）を説明する図である。
【００４０】
Ｓ７０１において新規エッジ追加手段は、（Ｓ６０３）で取得したエッジの座標の値に基づいて、その座標に対応する分割領域を特定する。例えば、図８で示すようにエッジＩＤ＝７のエッジ（５２７）を追加する場合、エッジ（５２７）のＸ座標が７００であるため、Ｘ座標範囲５１２〜７６７に対応する分割領域３（５０４）が特定される。すなわち、エッジ（５２７）が含まれるべき分割領域が特定される。同様にエッジＩＤ＝８のエッジ（５１８）については分割領域４（５０５）が特定される。
【００４１】
次にＳ７０２において、新規エッジ追加手段は、エッジブロックテーブル（２２１）を参照し、特定された分割領域に関連付けられているエッジが存在するかを判断する。例えば、エッジブロックテーブルの対応する分割領域のＩＤに関連付けられているエッジＩＤがあれば、関連付けられているエッジが存在すると判断され（Ｓ７０２でＹｅｓ）、新規エッジ追加手段は、Ｓ７０３においてその関連付けられているエッジを特定する。そうでなければ（Ｓ７０６）に進む。例えば図８の例では、エッジＩＤ＝７のエッジは分割領域３（５０４）に追加される判断され、エッジブロックテーブル（２２１）に基づいてエッジＩＤ＝１のエッジ（５２１）が特定される。
【００４２】
次にＳ７０４において新規エッジ追加手段は、エッジブロックテーブル（２２１）の分割領域３（５０４）に関連付けられるエッジＩＤを、現在処理しているエッジＩＤ（ＩＤ＝７）で更新する。
【００４３】
次にＳ７０５において新規エッジ追加手段は、特定されたエッジを起点にしたエッジテーブルの探索を行う。この探索は、エッジテーブルで管理されているエッジのリンク構造を、起点となるエッジから辿って行って、このリンク構造において新規エッジを追加する位置を探す処理である。つまり、ソート対象の新規エッジの座標と他のエッジの座標との比較が、起点となるエッジの座標との比較から開始される。言い換えると、１つのエッジをソートする際に、そのソート対象のエッジとの座標の比較が開始されるエッジが、ソート対象のエッジの座標に基づいて特定される。図８の例では、新規エッジ追加手段は、特定されたエッジ（５２１）の処理対象の走査線上の座標（Ｃｕｒｒｅｎｔ＿Ｘ）６００と、処理対象のエッジ（５２７）の処理対象の走査線上の座標（Ｃｕｒｒｅｎｔ＿Ｘ）７００と大小比較する。その結果、エッジ（５２７）は、エッジ（５２１）よりＸ座標に関して後方（エッジテーブルのリンク構造において後方）に位置する事が判断できる。そこで次に新規エッジ追加手段は、エッジ（５２１）のｎｅｘｔ＿ｅｄｇｅ＿ｉｄを参照して、エッジ（ＩＤ＝２のエッジ（５２２））を特定する。そして新規エッジ追加手段は、その特定されたエッジ（５２２）の処理対象の走査線上の座標（Ｃｕｒｒｅｎｔ＿Ｘ）１２００と、新規のエッジ（５２７）の座標７００）とを大小比較する。すると、新規のエッジ（５２７）は、エッジ（５２２）よりＸ座標に関して前方（エッジテーブルのリンク構造において前方）に位置すると判断できる。以上の処理によって、新規エッジ追加手段は、新規のエッジ（５２７）は、エッジ（５２１）とエッジ（５２２）との間に位置すると判断し、エッジテーブルで管理されるリンク構造を更新する。具体的には、新規エッジ追加手段は、エッジ（５２１）のｎｅｘｔ＿ｅｄｇｅ＿ｉｄを「ＩＤ＝２」から「ＩＤ＝７」に更新し、エッジ（５２７）のｐｒｅｖ＿ｅｄｇｅ＿ｉｄを「Ｎｕｌｌ」から「ＩＤ＝１」に更新する。また新規エッジ追加手段は、エッジ（５２７）のｎｅｘｔ＿ｅｄｇｅ＿ｉｄを「Ｎｕｌｌ」から「ＩＤ＝２」に更新し、エッジ（５２７）のｐｒｅｖ＿ｅｄｇｅ＿ｉｄを「ＩＤ＝１」から「ＩＤ＝７」に更新する。
【００４４】
一方、Ｓ７０６において新規エッジ追加手段は、エッジブロックテーブルの対応する分割領域に新規エッジのエッジＩＤを関連付ける。例えば図９の例では、ＩＤ＝８のエッジ（５２８）はＳ７０１において分割領域４に含まれると判定されて、エッジブロックテーブルの分割領域４にエッジＩＤ＝８が関連付けられる。
【００４５】
次にＳ７０７において新規エッジ追加手段は、エッジテーブルのリンク構造を探索し、新規エッジをどのエッジにリンクさせるかを決める。図９の例では、エッジ（５２８）は分割領域４（５０５）に含まれるエッジであった。そのため新規エッジ追加手段は、新規のエッジ（５２８）とリンクさせるエッジが存在すると考えられる分割領域３（５０４）にエッジブロックテーブルにおいて関連付けられているエッジが存在するか判断する。そして、エッジブロックテーブルの分割領域３にエッジ（５２７）が関連付けられているので、新規のエッジ（５２８）は分割領域３（５０４）に含まれるエッジとリンクされると判断し、Ｓ７０５と同様にエッジテーブルの探索と更新を行う。その結果、新規エッジ追加手段は、新規のエッジ（５２８）は、エッジ（５２７）とエッジ（５２２）との間に位置すると判断し、エッジ（５２７）、エッジ（５２８）、エッジ（５２２）の順でリンクされるように、エッジテーブルを更新する。
【００４６】
以上のように、新規エッジ追加手段は、新規エッジが含まれる分割領域に関連付けられたエッジをエッジブロックテーブルによって特定する。そして新規エッジ追加手段は、その特定されたエッジを起点にエッジテーブル（エッジのリンク構造）を順番に探索することで、新規エッジを追加するべき箇所を特定し、エッジテーブルを更新する。この処理により、エッジテーブル（エッジのリンク構造）を探索および更新を効率的に行うことができる。
【００４７】
＜追加済みエッジソート処理（Ｓ３０１）の詳細＞
図１０は、本実施形態における図３で示した追加済みエッジソート処理（Ｓ３０１）の詳細なフローを示す図である。本処理は、既にエッジテーブル（２２２）で管理されているエッジに関して、処理対象の走査線上での座標を算出し、算出された座標に基づいて、処理対象の走査線の各エッジを、座標に関して昇順に並び変える処理である。図１１は、エッジブロックテーブル（２２１）を利用した追加済みエッジソート処理（Ｓ３０１）を説明する図である。
【００４８】
Ｓ１００１において追加済みエッジソート手段は、エッジテーブルで既に管理されるエッジのうちで、未処理のエッジを取得する。例えば、図１１で示すように、エッジ（５２７）が取得された場合を以下で説明する。
【００４９】
Ｓ１００２において追加済みエッジソート手段は、取得されたエッジの処理対象の走査線上の座標の算出処理を行う。（Ｓ１００１）で取得されたエッジのＣｕｒｒｅｎｔＸに格納される座標は、処理対象の走査線の１つ前の走査線上のＸ座標で有るため、ここではＣｕｒｒｅｎｔＸにＤＸ／ＤＹの値を加算した値を、処理対象の走査線上の座標となる。
【００５０】
次にＳ１００３において追加済みエッジソート手段は、Ｃｕｒｒｅｎｔ＿Ｘの値（直前の走査線上の座標：前回の座標）と、算出した値（処理対象の走査線上の座標：今回の座標）とを比較する。両者が同じ値の場合は、処理対象のエッジについてはソート処理が不要であるため、（Ｓ１００６）に進む。そうでなければエッジのソート処理が必要なのでＳ１００４に進む。このＳ１００４の処理は前述したＳ６０４の処理と同様の処理を追加済みエッジソート手段が実行するものであるため、処理の詳細は割愛する。このＳ１００４の処理によって図１１の例では、エッジ（５２７）が含まれる分割領域３が特定され、その分割領域３とエッジブロックテーブルによって関連付けられているエッジを起点としてエッジテーブルの探索および更新が行われる。
【００５１】
次にＳ１００５において追加済みエッジソート手段は、前回の座標と今回の座標とを参照し、エッジが分割領域間を移動するかを判断する。前回の座標と今回の座標とが異なる分割領域に対応するものであれば、エッジが分割領域間を移動すると判断され処理はＳ１００６へ進み、そうでなければＳ１００７へ進む。図１１の例では、エッジ（５２７）は分割領域３（５０４）から分割領域２（５０３）に移動すると判断される。
【００５２】
Ｓ１００６において追加済みエッジソート手段は、エッジブロックテーブルを更新する。この更新は分割領域間を移動すると判定された処理対象エッジ（図１１の例ではエッジ７）のＩＤを、エッジブロックテーブルにおける、移動先の分割領域（図１１の例では分割領域２）に関連付ける。そしてこの更新は、処理対象エッジ（図１１の例ではエッジ７）のｎｅｘｔ＿ｅｄｇｅ＿ｉｄで示されるＩＤ（ＩＤ＝１）を、エッジブロックテーブルにおける、移動元の分割領域（図１１の例では分割領域３）に関連付ける。なお移動元と移動先の分割領域の前後関係がＸ座標に関して逆の場合、この更新は、処理対象エッジのｐｒｅｖ＿ｅｄｇｅ＿ｉｄで示されるＩＤを、エッジブロックテーブルにおける、移動元の分割領域に関連付ける。
【００５３】
そしてＳ１００７において追加済みエッジソート手段は、未処理のエッジがなければ処理を終了し（Ｓ１００７でＹｅｓ）、そうでなければＳ１００１へ処理を戻す。
【００５４】
以上説明したように、本実施形態の画像処理装置は、前述したページ画像を所定の分割領域に分割し、前記分割領域にそれぞれ属するエッジ情報を管理するエッジブロックテーブル（２２１）を利用したエッジの追加処理・ソート処理を可能とする。つまり、ソート対象のエッジとの座標の比較が開始されるエッジが、そのソート対象のエッジの座標に基づいて特定される。これにより画像形成処理の特に描画オブジェクトの輪郭を示すエッジの処理（特にエッジテーブルの探索および更新）を高速に実現する事ができる。
【００５５】
（第２の実施形態）
以下、第２の実施形態について説明する。
【００５６】
＜エッジブロックテーブル１（２２３）とエッジテーブル２の（２２４）の概念図）＞
図１２は、本実施形態における二つのエッジブロックテーブル１、２（２２３、２２４）及びエッジテーブルの（２２２）概念図である。第２の実施形態は、分割領域の分割サイズが異なる二つのエッジブロックテーブル１、２（２２３、２２４）を用いる。エッジブロックテーブル１（２２３）は前述した分割領域単位（つまり分割サイズが２５６ピクセル単位）のエッジＩＤの管理を行うテーブルである。役割としては、第１の実施形態のエッジブロックテーブル（２２１）と同様である。次に、エッジブロックテーブル２（２２４）はエッジの管理を座標単位（画素単位）で管理するテーブルである。例えば座標ＩＤ＝１２０（すなわちＸ座標＝１２０）にはエッジＩＤ＝５が関連付けられている。ここで注意されたいのは、Ｘ座標＝１２０に複数のエッジが位置していても良い、と言うことである。後述するように、座標単位でエッジを管理することで、新規エッジの追加や追加済みエッジのソートにおいて、第１の実施形態よりも効率的にエッジデータの探索範囲を絞ることができる。利用方法に関しては、図１３を用いて後述する。
【００５７】
＜第２の実施形態における、分割領域ソート処理（Ｓ６０４）の詳細を示すフロー図＞
図１３は、本実施形態における二つのエッジブロックテーブル１、２（２２３、２２４）を利用する第２の実施形態における、分割領域ソート処理（Ｓ６０４）の詳細を示すフロー図である。この処理が開始される前に第１の実施形態と同様に、処理対象のエッジの座標が取得されている。
【００５８】
新規エッジ追加手段は、まずＳ１３０１において、エッジブロックテーブル２（２２４）によって、取得された座標に対応する座標ＩＤに関連付けられているエッジが存在するか否かを判断する。存在する場合、処理はＳ１３０２に進む。そうでなければ処理はＳ７０１に進む。この処理は第１の実施形態のＳ７０１と同様の処理であり、このステップ以降の処理は、図７とほぼ同様である。違いは後述のＳ１３０３の処理だけである。
【００５９】
次にＳ１３０２において、（Ｓ１３０１）でエッジブロックテーブル２によって座標ＩＤに関連付けられているエッジを特定する。
【００６０】
次にＳ１３０３において新規エッジ追加手段は、処理対象のエッジ（新規のエッジ）を、エッジブロックテーブル１、２（２２３、２２４）の双方を更新する。新規エッジ追加手段は、エッジブロックテーブル２（２２４）を、処理対象のエッジの座標に対応する座標ＩＤにそのエッジを関連付けるように更新する。また、新規エッジ追加手段は、エッジブロックテーブル１（２２３）を、取得されたエッジの座標に対応する分割領域にそのエッジを関連付けるように更新する。
【００６１】
Ｓ１３０４において新規エッジ追加手段は、Ｓ１３０２で特定されたエッジを起点として、Ｓ７０５と同様にエッジテーブルの探索および更新を行う。
【００６２】
以上のように、座標単位のエッジブロックテーブルを利用することで、Ｓ１３０２〜Ｓ１３０４の処理によって効率的なエッジテーブルの探索および更新が可能となる。
【００６３】
（その他の実施形態）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【図１】
2018063557.tif 000003
【図２】
2018063557.tif 000004
【図３】
2018063557.tif 000005
【図４】
2018063557.tif 000006
【図５】
2018063557.tif 000007
【図６】
2018063557.tif 000008
【図７】
2018063557.tif 000009
【図８】
2018063557.tif 000010
【図９】
2018063557.tif 000011
【図１０】
2018063557.tif 000012
【図１１】
2018063557.tif 000013
【図１２】
2018063557.tif 000014
【図１３】
2018063557.tif 000015