(57)【要約】      （修正有）【課題】多量の文字オブジェクトやグラフィックスオブジェクトを含む電子データを高速にレダリング処理することが可能な画像形成技術の提供。【解決手段】画像形成装置は、受信された電子データに含まれるオブジェクトのアウトラインを示すエッジ情報と、アウトライン内部を塗りつぶすか否かを制御するフィル情報と、電子データを構成している各ページの画像形成を制御するための制御情報と、を含むディスプレイリストを生成する生成部と、ページ内のオブジェクトを１ラインごとにレンダリング処理するときに、エッジ情報に基づいてオブジェクトと１ラインとの交点を求め、オブジェクトのエッジの位置を抽出するエッジ位置抽出部と、抽出されたエッジのデータ量と、制御情報の解析により予測されるページにおけるエッジのデータ量とに基づいて、エッジ位置抽出部によるエッジの抽出を所定のデータ量の範囲内に制御するための閾値を設定する設定部とを備える。【選択図】図１
2010280084.tif 000002
【特許請求の範囲】
【請求項１】
電子ドキュメントを受信する受信手段と、
前記受信手段により受信された前記電子ドキュメントに含まれるオブジェクトのアウトラインを示すエッジ情報と、前記オブジェクトのアウトライン内部を塗りつぶすか否かを制御するためのフィル情報と、前記電子ドキュメントを構成している各ページの画像形成を制御するための制御情報と、を含むディスプレイリストを生成する生成手段と、
前記電子ドキュメントのページ内のオブジェクトを１ラインごとにスキャンラインレンダリング処理するときに、前記エッジ情報に基づいて前記オブジェクトと前記１ラインとの交点を求め、前記１ライン上における前記オブジェクトのエッジの位置を抽出するエッジ位置抽出手段と、
前記エッジ位置抽出手段で抽出された前記エッジのデータ量と、前記制御情報の解析により予測される前記ページにおけるエッジのデータ量とに基づいて、前記エッジ位置抽出手段による前記エッジの抽出を所定のデータ量の範囲内に制御するための閾値を設定する設定手段と、を備え、
前記エッジ位置抽出手段で抽出された前記エッジの数が、前記設定手段で設定された前記閾値以上になった場合に、前記エッジ位置抽出手段は、前記オブジェクトを囲む矩形領域を設定し、前記矩形領域と前記１ラインとの交点から、前記１ライン上における前記オブジェクトのエッジを抽出することを特徴とする画像形成装置。
【請求項２】
前記エッジ位置抽出手段により抽出された前記エッジの間をスパンとして抽出するスパン抽出手段と、
前記フィル情報に基づいて、前記スパン抽出手段により抽出された前記スパンの塗りつぶしを制御する塗りつぶし制御手段と、を更に備えることを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記設定手段は、前記エッジ位置抽出手段により抽出された前記エッジの情報を格納する格納手段で格納可能な残容量に応じて、前記閾値の設定を制御することを特徴とする請求項１に記載の画像形成装置。
【請求項４】
前記エッジ位置抽出手段で抽出された前記エッジの情報が前記格納手段に格納されることにより前記残容量が減少すると、前記設定手段は前記残容量の減少に基づき前記閾値の設定を更新することを特徴とする請求項３に記載の画像形成装置。
【請求項５】
前記スパン抽出手段は、前記フィル情報により求められる前記オブジェクトと重なる背景との合成を示す合成情報と、前記エッジの間のスパンと、を含むスパンデータを生成することを特徴とする請求項２に記載の画像形成装置。
【請求項６】
前記エッジ位置抽出手段が、前記オブジェクトを囲む矩形領域を設定し、前記矩形領域と前記１ラインとの交点から、前記１ライン上における前記オブジェクトのエッジの位置を抽出した場合、
前記塗りつぶし制御手段は、前記スパン抽出手段により抽出された前記スパンに対して、前記塗りつぶし制御手段は、前記スパンデータに含まれる、前記合成情報に基づき、前記スパンの塗りつぶしを制御することを特徴とする請求項５に記載の画像形成装置。
【請求項７】
受信手段が、電子ドキュメントを受信する受信工程と、
生成手段が、前記受信工程により受信された前記電子ドキュメントに含まれるオブジェクトのアウトラインを示すエッジ情報と、前記オブジェクトのアウトライン内部を塗りつぶすか否かを制御するためのフィル情報と、前記電子ドキュメントを構成している各ページの画像形成を制御するための制御情報と、を含むディスプレイリストを生成する生成工程と、
前記電子ドキュメントのページ内のオブジェクトを１ラインごとにスキャンラインレンダリング処理するときに、エッジ位置抽出手段が、前記エッジ情報に基づいて前記オブジェクトと前記１ラインとの交点を求め、前記１ライン上における前記オブジェクトのエッジの位置を抽出するエッジ位置抽出工程と、
設定手段が、前記エッジ位置抽出工程で抽出された前記エッジのデータ量と、前記制御情報の解析により予測される前記ページにおけるエッジのデータ量とに基づいて、前記エッジ位置抽出工程による前記エッジの抽出を所定のデータ量の範囲内に制御するための閾値を設定する設定工程と、を有し、
前記エッジ位置抽出工程で抽出された前記エッジの数が、前記設定工程で設定された前記閾値以上になった場合に、前記エッジ位置抽出工程は、前記オブジェクトを囲む矩形領域を設定し、前記矩形領域と前記１ラインとの交点から、前記１ライン上における前記オブジェクトのエッジを抽出することを特徴とする画像形成装置の制御方法。
【請求項８】
スパン抽出手段が、前記エッジ位置抽出工程により抽出された前記エッジの間をスパンとして抽出するスパン抽出工程と、
塗りつぶし制御手段が、前記フィル情報に基づいて、前記スパン抽出工程により抽出された前記スパンの塗りつぶしを制御する塗りつぶし制御工程と、を更に有することを特徴とする請求項７に記載の画像形成装置の制御方法。
【請求項９】
前記設定工程は、前記エッジ位置抽出工程により抽出された前記エッジの情報を格納する格納手段で格納可能な残容量に応じて、前記閾値の設定を制御することを特徴とする請求項８に記載の画像形成装置の制御方法。
【請求項１０】
前記エッジ位置抽出工程で抽出された前記エッジの情報が前記格納手段に格納されることにより前記残容量が減少すると、前記設定工程は前記残容量の減少に基づき前記閾値の設定を更新することを特徴とする請求項９に記載の画像形成装置の制御方法。
【請求項１１】
前記スパン抽出工程は、前記フィル情報により求められる前記オブジェクトと重なる背景との合成を示す合成情報と、前記エッジの間のスパンと、を含むスパンデータを生成することを特徴とする請求項９に記載の画像形成装置の制御方法。
【請求項１２】
前記エッジ位置抽出工程が、前記オブジェクトを囲む矩形領域を設定し、前記矩形領域と前記１ラインとの交点から、前記１ライン上における前記オブジェクトのエッジの位置を抽出した場合、
前記スパン抽出工程により抽出された前記スパンに対して、前記塗りつぶし制御工程は、前記スパンデータに含まれる前記合成情報に基づき、前記スパンの塗りつぶしを制御することを特徴とする請求項１１に記載の画像形成装置の制御方法。
【請求項１３】
請求項８乃至１２のいずれか１項に記載の画像形成装置の制御方法をコンピュータに実行させるためのプログラム。
【請求項１４】
１ラインに含まれるエッジ数が閾値を超えたか判定し、閾値を超えないと判定された場合はオブジェクトのアウトラインのエッジ情報を抽出し、閾値を超えたと判定された場合はオブジェクトのバウンディングボックスのエッジ情報を抽出する第1のプロセッサと、
オブジェクトのアウトラインのエッジ情報が抽出された場合、背景との比較を行なうことなく描画し、オブジェクトのバウンディングボックスのエッジ情報が抽出された場合、背景との比較を行いながら描画を行う第2のプロセッサとを備えることを特徴とする画像形成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像形成技術に関するものである。
【背景技術】
【０００２】
複数の画像オブジェクト（例えば、文字やイメージやグラフィック）で構成されている電子ドキュメントやＰＤＬデータから画像を形成する処理がある。スキャンラインレンダラが画像を形成する処理を実行する場合、スキャンラインレンダラは電子ドキュメントやＰＤＬデータを解析し、スキャンラインレンダラで処理が可能なディスプレイリストを生成する。そして、スキャンラインレンダラはディスプレイリストを解析し、形成した画像をページメモリに格納していく。スキャンラインレンダラのディスプレイリストには、電子ドキュメント等に含まれる各画像オブジェクトと各画像オブジェクトの左右のアウトラインがエッジ情報として保持される。
【０００３】
スキャンラインレンダラは、その後、ページ内の１ラインに注目し、各画像オブジェクトと注目しているラインとの交差点Ｘ座標を抽出する（エッジリスト）。スキャンラインレンダラは、スキャンラインとして１行を左から右に描画していくものとし、ページの左端のＸ座標を最小として、抽出されたエッジリストの交差点Ｘ座標をソートする。スキャンラインレンダラは、ソートされたエッジリストからＸ座標の小さい方から順番に交差点と交差点の区間（以下、「スパン」と記述）の長さΔＸを抽出するとともに、スパンの左端の交差点を開始点として設定する。スキャンラインレンダラは抽出された開始点とΔＸとを用いて、所定のページメモリにスパンを描画する。スパンにはオブジェクトの内容により、文字やイメージやグラフィックスが描画される。
【０００４】
スキャンラインレンダラの中にはエッジ情報として２値ビットマップを登録できるものがある。２値ビットマップで登録されるエッジ情報とは、主に文字オブジェクト（ビットマップフォント）である。エッジ情報として２値ビットマップが登録された場合、スキャンラインレンダラは２値ビットマップ内部の図柄のアウトラインを抽出しエッジ情報とする。スキャンラインレンダラは２値ビットマップから抽出された、エッジ情報と注目されるページの1ラインとの交差点をエッジリストに登録する。このとき問題となるのが、帳票データなどの文字オブジェクトが多量に含まれる電子ドキュメントやＰＤＬデータの場合や、文字オブジェクト以外にもグラフィックスオブジェクトなどを多く含む場合である。スキャンラインレンダラにより実行されるエッジリストの生成およびソートに時間がかかり画像形成速度が低下してしまうという問題点がある。例えば、特許文献１には、エッジリストの生成やソートを行う回路を複数備え、それぞれの処理を並列に行う手法が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−１５７１４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら上記手法を実現するためには、専用のハードウェアを作成するか、ＣＰＵを複数持つ必要があり、作成工数やコストが高くなってしまうという問題点がある。また、近年、コンフィグラブルプロセッサなどを用いたCPUのマルチプロセッサ構成でコストダウンしながら処理速度を維持するものがある。その場合、コンフィグラブルプロセッサの各プロセッサは特定の処理にある程度特化させて処理速度を出すことによりコストダウンを行うが、すべての処理を高速処理することはできない。特定の処理にある程度特化させても、コストダウンするためにはハードウェアのような高速性は求められない。
【課題を解決するための手段】
【０００７】
上記の課題を鑑み、本発明は、多量の文字オブジェクトやグラフィックスオブジェクトを含む電子ドキュメントやＰＤＬデータを高速にレダリング処理することが可能な画像形成技術の提供を目的とする。
【０００８】
上記の目的を達成する本発明にかかる画像形成装置は、電子ドキュメントを受信する受信手段と、
前記受信手段により受信された前記電子ドキュメントに含まれるオブジェクトのアウトラインを示すエッジ情報と、前記オブジェクトのアウトライン内部を塗りつぶすか否かを制御するためのフィル情報と、前記電子ドキュメントを構成している各ページの画像形成を制御するための制御情報と、を含むディスプレイリストを生成する生成手段と、
前記電子ドキュメントのページ内のオブジェクトを１ラインごとにスキャンラインレンダリング処理するときに、前記エッジ情報に基づいて前記オブジェクトと前記１ラインとの交点を求め、前記１ライン上における前記オブジェクトのエッジの位置を抽出するエッジ位置抽出手段と、
前記エッジ位置抽出手段で抽出された前記エッジのデータ量と、前記制御情報の解析により予測される前記ページにおけるエッジのデータ量とに基づいて、前記エッジ位置抽出手段による前記エッジの抽出を所定のデータ量の範囲内に制御するための閾値を設定する設定手段と、を備え、
前記エッジ位置抽出手段で抽出された前記エッジの数が、前記設定手段で設定された前記閾値以上になった場合に、前記エッジ位置抽出手段は、前記オブジェクトを囲む矩形領域を設定し、前記矩形領域と前記１ラインとの交点から、前記１ライン上における前記オブジェクトのエッジを抽出することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、多量の文字オブジェクトやグラフィックスオブジェクトを含む電子ドキュメントやＰＤＬデータを高速にレダリング処理することが可能になる。
【図面の簡単な説明】
【００１０】
【図１】画像形成装置の概略的な構成を示すブロック図。
【図２】ディスプレイリストの構成例を説明する図。
【図３】エッジリストの作成処理を説明する図。
【図４】２値ビットマップからのエッジリスト抽出処理を説明する図。
【図５】エッジリストのソート処理を説明する図。
【図６】スパンデータの生成処理を説明する図。
【図７】スパンの塗りつぶし処理を説明する図。
【図８】２値ビットマップのエッジ情報からエッジ位置を抽出する処理を説明する図。
【図９】２値ビットマップのバウンディングボックスとラインとの交差位置をエッジ位置として抽出する処理を説明する図。
【図１０】ディスプレイリストの書き換え処理を説明する図。
【図１１】スパンデータ生成処理の変更について説明する図。
【図１２】スパンの塗りつぶし処理を説明する図。
【図１３】エッジリストへのアクセス例を示す図。
【図１４】プロセッサBとＲＡＭの構成例を示す図。
【図１５】エッジリストに対するアクセスサイクルの変化を説明する図。
【図１６】プロセッサBの処理の流れを説明するフローチャート。
【図１７】コンフィグラブルプロセッサでのシステム構成例を説明する図。
【図１８】ディスプレイリスト構成を例示する図。
【図１９】レンダリング処理部の処理を説明する図。
【図２０】レンダリング処理部の処理を説明する図。
【図２１】レンダリング処理部の処理を説明する図。
【発明を実施するための形態】
【００１１】
（第１実施形態）
図１の参照により、本実施形態にかかる画像形成装置の構成を説明する。画像形成装置101は、入力部102により入力された電子ドキュメントやPDLデータの画像形成を行う。入力部102は、例えば、ネットワークからのデータ受信やUSBメモリなどとの接続によりデータを画像形成装置に入力することが可能である。画像形成装置101は、３つのCPU（プロセッサA、B、C）とRAMと、ROMと、ハードディスク（以下、「HDD」という。）等を有する。入力部102から入力されたデータは、外部インターフェース103を介して、データ生成部104に入力される。データ生成部104は、入力されたデータを解析し、レンダリング処理部用のデータ（ディスプレイリスト105）を生成する。３つのプロセッサのうち、プロセッサAは、外部インターフェース103の処理と、データ生成部104の実行に用いられる。残りの２つのプロセッサB、Cはデータ生成部104で生成されたディスプレイリスト105から実際のページイメージ120を形成するレンダリング処理部109による処理を実行するために用いられる。レンダリング処理部109は、電子ドキュメントやPDLファイル等のページ内のオブジェクトを１ラインごとにスキャンラインレンダリング処理することが可能である。
【００１２】
３つのプロセッサA、B、Cの実行により処理される各データはROM、RAM、HDDのいずれかの記憶手段に記憶され、各プロセッサが個別に読みだして、所定の処理を実行する。尚、記憶手段としては、USBメモリのような外部接続メモリであっても良い。記憶手段には、本発明の実施形態に係る画像形成装置の制御方法をコンピュータに実行させるためのプログラムが格納されている。
【００１３】
データ生成部104が生成するディスプレイリスト105にはインストラクション106、エッジ情報107、フィル情報108が含まれる。インストラクション106にはページ全体の制御情報が含まれる。エッジ情報107にはオブジェクトのアウトライン情報が含まれる。フィル情報108にはオブジェクトのアウトライン内部を塗りつぶすか否かを制御するための情報が含まれる。ディスプレイリスト105は、例えば、RAM、ROM、HDDなどの記憶手段に格納される。
【００１４】
レンダリング処理部109は、ディスプレイリスト105のデータを読み込んで電子ドキュメントのページイメージを形成する。レンダリング処理部109のプロセッサB（第1のプロセッサ）は、エッジリスト115の生成と、スパンデータ123の生成（抽出）とを行うために、ディスプレイリスト解釈部111からスパン抽出処理部117までの処理の実行を制御する。プロセッサC（第2のプロセッサ）は、プロセッサBにより抽出されたスパンデータ123を読み込みページイメージを生成するスパン塗りつぶし処理部119の処理の実行を制御する。プロセッサBとプロセッサCとは並列に動作し、スパンデータ123を受け渡すことによりパイプライン処理を行う。
【００１５】
プロセッサB（第1のプロセッサ）の制御により以下の処理が実行される。ディスプレイリスト解釈部111がインストラクション106に含まれているページ全体の画像形成を制御するための制御情報の解釈を行い、ラインごとにエッジ位置抽出処理部112を呼びだす。エッジ位置抽出処理部112は、エッジ情報に基づいてオブジェクトと１ラインとの交点を求め、１ライン上におけるオブジェクトのエッジの位置を抽出してエッジリスト115を生成する。エッジ位置抽出処理部112によって生成されたエッジリスト115には、エッジ位置のデータがランダムに並んで格納されているため、エッジ位置ソート処理部116によってソートされる。エッジ位置ソート処理部116は、例えば、ページの左端のＸ座標を最小として、エッジ位置のデータをソートする。ソートされたエッジリスト115のデータは、スパン抽出処理部117によって読み込まれる。スパン抽出処理部117は、それぞれのエッジ位置の間をスパンとして抽出し、スパンデータ123を生成する。
【００１６】
電子ドキュメントやPDLデータ内に含まれるオブジェクト数が多いと、ページに含まれるオブジェクトのアウトラインも膨大となる。そして、エッジ位置抽出処理部112、エッジ位置ソート処理部116、及びスパン抽出処理部117の処理が増大し処理速度が低下する。
【００１７】
エッジリスト数閾値判定処理部113は、抽出されたエッジのデータ量と、制御情報の解析により予測されるページ内におけるエッジのデータ量とに基づいて、エッジの抽出を所定のデータ量の範囲内に制御するための閾値を設定する。エッジリスト数閾値判定処理部113は、抽出されたエッジの情報（エッジリスト）を格納するメモリにおいて格納可能な残容量に応じて、閾値の設定を制御することが可能である。例えば、抽出されたエッジリストがメモリに格納されることによりメモリの残容量が減少すると、エッジリスト数閾値判定処理部113は残容量の減少に基づき閾値の設定を更新する。エッジリスト数閾値判定処理部113が、生成されたエッジリスト数（エッジのデータ量）を監視し、処理速度が低下するエッジリスト数（閾値リスト数）を越えた場合に、エッジ位置抽出処理部112にエッジリストの生成を抑制するように指示する。エッジ位置抽出処理部112は、エッジリスト115の生成を抑制して画像形成できるようにエッジ情報107とフィル情報108とを書き替える。その後、エッジ位置抽出処理部112は、エッジ情報107とフィル情報108とを書き替えた後に、画像形成をするためのエッジリスト115の生成を行う。
【００１８】
プロセッサＣ（第2のプロセッサ）の制御の下に以下の処理が実行される。スパン塗りつぶし処理部119は、スパンデータ123を読み込み、スパンデータ123に基づいてページイメージ120を生成する。ページイメージ120は、例えば、RAM、HDDの記憶手段に格納される。フィル情報108が単純な単色の塗りつぶしのような場合、スパンデータ123にその情報が記載されているので、スパン塗りつぶし処理部119は、フィル情報108にアクセスする必要は無い。しかしながら、イメージオブジェクトの場合はフィル情報108にアクセスし、イメージオブジェクトの実体を取得する。レンダリング処理部109の１ページ分の処理が終了すると、ページイメージ120は印刷エンジン121によって処理され、実際の用紙上に画像形成の結果122が出力される。
【００１９】
ディスプレイリスト105に含まれるエッジ情報107にはページに含まれるすべてのエッジ情報が含まれる。エッジ位置抽出処理部112が１つのラインに注目してエッジ位置を抽出するときにはページに含まれるすべてのエッジ情報を使用するわけではなく、その一部を使用する。使用中のエッジ情報124にエッジ位置抽出処理部112は現在使用しているエッジ情報を保存しておく。
【００２０】
図2を用いて図1のディスプレイリスト105の詳細な構成について説明する。画像形成結果219は、ページ開始命令201からフィルの種類218までによりディスプレイリストが表現している画像形成の結果を示すものである。ページ開始命令201からページ終了命令213まではインストラクション106（図１）に対応するデータである。インストラクション106は、ページ開始命令201、ページ終了命令213のような制御命令、ページ幅203、ページ高さ204等のページ全体のサイズ情報、エッジのロード及び描画開始命令205からエッジ情報212により示される画像形成情報を含む。エッジのロードおよび描画開始命令205は、画像形成結果219に含まれる部分画像222の画像形成を指示するデータで、描画高さ206は1250ラインである。画像形成結果219の部分画像222にはオブジェクトが存在しないため、追加エッジ情報数207は「０」である。本実施形態におけるレンダリング処理では、エッジ情報が存在しない区間は下地色202に従って塗りつぶすものとする。
【００２１】
次のエッジのロードおよび描画開始命令208は、画像形成結果219に含まれる部分画像223の画像形成を指示するデータで、「三角形」で「灰色」に塗りつぶされたグラフィックス220が存在している。三角形であるので左右のエッジ情報が存在し、追加エッジ情報数は2個存在する。追加される２つのエッジ情報209は、それぞれエッジ情報１、エッジ情報２に格納される。エッジ情報１とエッジ情報２とに対応している情報はエッジ情報214ａ、214ｂに含まれる。エッジ情報１とエッジ情報２とは、使用中のエッジ情報124に登録される。
【００２２】
「三角形」の左側に対応しているエッジ情報214ａには「灰色」のフィル情報216が関連付けられ、「三角形」の右側に対応しているエッジ情報214ｂには「透過」のフィル情報218が関連付けられている。レンダリング処理を行うときにページの左側から順番に処理を行い、「三角形」の左側のエッジ位置を越えた時点で「灰色」に塗り始め、右側のエッジ位置を越えた時点で「灰色」を塗るのを止めて、「透過」により背景色を塗るように判断するためである。ここで、背景色とは下に別のオブジェクトが無ければ下地となり下地色202を塗り、下に別のオブジェクトがあればそのオブジェクトの色を塗ることである。
【００２３】
画像形成結果219に含まれる部分画像223には、「H」の「黒い」文字220が存在している。そのため、エッジ情報210には、「黒い」文字220に対応したエッジ情報3が格納されている。エッジ情報3には、２値ビットマップのエッジ情報215が関連付けられている。２値ビットマップのエッジ情報215におけるポインタを介して２値ビットマップの実体230に関連付けられている。エッジ情報215には、２値ビットマップ230内部の図形のアウトライン内を塗りつぶすフィル情報217が指定される。本実施形態におけるレンダリング処理では、２値ビットマップ230内部の図形のアウトライン外に関しては「透過」として扱うこととする。
【００２４】
画像形成結果219に含まれる部分画像224では、三角形のグラフィックス220の描画を行う必要がなくなる。そのため、インストラクションには、削除エッジ情報数211と、どのエッジ情報を使用中のエッジ情報124から削除するかを指定する情報212と、が含まれる。ここでは、使用中のエッジ情報124からエッジ情報１とエッジ情報２とが削除される。
【００２５】
同様に、画像形成結果219に含まれる部分画像225では、「H」の「黒い」文字220の描画を行う必要もなくなるため、使用中のエッジ情報124からエッジ情報3が削除される。
【００２６】
図3を用いてエッジ位置抽出処理部112がグラフィックスのエッジ情報からエッジリストを作成する処理を説明する。エッジ位置抽出処理部112は、ライン310と三角形301のアウトラインが交差する左位置311と右位置312とをエッジリストに追加する。三角形301の左エッジ情報は三角形の頂点座標のX座標302（=1750）から、Y軸方向に１移動するたびに傾き303に従いX座標を「−1」する傾き303を持ったエッジ情報である。
【００２７】
Ｙ軸方向の移動量を「750」とした場合に、ライン310と三角形301のアウトラインとの交差する左側のエッジ位置は式306（ｘ = -y + 1750 = -750 ＋ 1750 = 1000）により求められる。エッジ位置抽出処理部112は、ここで求められた左側のエッジ位置座標「1000」をエッジリスト308に追加する。
【００２８】
三角形301の右エッジ情報は三角形の頂点座標のX座標304（=1750）から、Y軸方向に１移動するたびに傾き305に従いX座標を「＋1」する傾き303を持ったエッジ情報である。Ｙ軸方向の移動量を「750」とした場合に、ライン310と三角形301のアウトラインとの交差する右側のエッジ位置は式307（ｘ = y + 1750 = 750 ＋ 1750 = 2500）により求められる。エッジ位置抽出処理部112は、ここで求められた左側のエッジ位置座標「2500」をエッジリスト309に追加する。また、エッジリスト308とエッジリスト309とには、エッジ情報と関連逗けられているフィル情報にアクセスするための情報（フィル情報＝１、フィル情報＝３）とが含まれている。これは、スパン抽出処理部117（図１）で、エッジリストとフィル情報の関係が解らないと、スパンの中をどのように塗りつぶすか解らなくなってしまうことを防ぐためである。
【００２９】
図4を用いてエッジ位置抽出処理部112が２値ビットマップのエッジ情報からエッジリストを作成する処理を説明する。2値ビットマップ411の左上端401のX座標＝1350を原点とする。エッジ位置抽出処理部112は、２値ビットマップ411を走査し、2値ビットマップ411のビットが「0」から「1」、もしくは「1」から「0」に変化する座標をエッジリストとして抽出する。
【００３０】
402では「0」が100ピクセル続いた後「1」が発見できるので、エッジリスト407にエッジ位置＝1450(1350＋100)を書き込む。同様に403、404、405と２値ビットマップ411を走査し、エッジリスト408、409、410にエッジ位置を追加する。406の２値ビットマップ411の走査により、２値ビットマップ411の右端に到達するので、このラインにおける２値ビットマップ411からのエッジリストの抽出を終了する。２値ビットマップ411から抽出されたエッジリストにはエッジ情報と関連づけられているフィル情報をアクセスするための情報412（フィル情報＝2、3等）を含む。これは図１に含まれるスパン抽出処理部117で、エッジリストとフィル情報の関係が解らないと、スパンの中をどのように塗りつぶすか解らなくなってしまうことを防ぐためである。
【００３１】
図5を用いてエッジ位置抽出処理部112によって生成されたエッジリスト115を、エッジ位置ソート処理部116がX座標位置の小さい順番にソートする動作を説明する。画像形成結果501を出力する場合を想定する。１つのライン502の描画開始時にエッジ位置抽出処理部112は、三角形506の左右エッジ位置みが登録されたエッジリスト503に、「H」の２値ビットマップ内部の図形のアウトラインとの交差点の座標情報504を追加する。交差点の座標情報504をエッジリスト503に追加した時点ではX座標位置がランダムに並んでいるので、エッジ位置ソート処理部116はX座標位置が小さい順番に並ぶようなエッジリスト505にソートしなおす。
【００３２】
エッジリスト505に含まれている、フィル情報にアクセスするための情報508は、２値ビットマップ内部のアウトライン外のエッジで、背景または下地を透過する必要がある。ここでは三角形のオブジェクトの内部になるので、三角形の内部と同じフィル情報を参照するように、エッジ位置ソート処理部116はフィル情報を「3」から「1」に書き替える。
【００３３】
図6を用いて、ソート後のエッジリスト（図５）とフィル情報とを用いて、スパン抽出処理部117がスパンデータ123を生成する処理を説明する。画像形成結果601を出力する場合を想定する。１つのライン602の左端点と三角形613との交点までの区間603に関して、スパン抽出処理部117は、ページの左端であるX座標＝０と、ソートされたエッジリスト607のX座標＝300からスパンデータ611を生成する。スパンデータ611の描画開始位置はX座標＝０であり、スパン（区間）の長さは300ピクセルであり、画像形成するオブジェクトは無いのでインストラクションに記載された下地615をそのまま描画する。
【００３４】
区間604に関して、スパン抽出処理部117はライン602と三角形613の左端との交差点のエッジリスト607と、ライン602と２値ビットマップ614の最初の交差点であるエッジリスト608とからスパンデータ612を生成する。スパンデータ612において、エッジリスト607の座標の終点が描画開始X座標を300となる。スパンの長さはエッジリスト608の座標からエッジリスト607の座標を引いた値となる。また、フィル情報610がスパンデータ612に設定される。
【００３５】
次に、プロセッサＣの制御により実行されるスパン塗りつぶし処理部119の処理を、図７を用いて説明する。画像形成結果701は、オブジェクトが、すべてが上書き（COPYPEN：背景のオブジェクトが前景のオブジェクトに完全に隠される）される場合を例示している。スパン塗りつぶし処理部119は、スパンデータ702に記載されている描画開始位置（描画X座標：X=1000）と、スパンの長さ（=1000）とを取得し、ページイメージ705のスパンを描画する位置を特定する。また、スパン塗りつぶし処理部119は、特定したスパンの位置をスパンデータ702に含まれるフィル情報により色情報を取得し（S７０３）、メモリへの書き出しを行い（S704）で塗りつぶしを行う。
【００３６】
描画形成結果707はオブジェクトが、すべて上書きで無く背景との重なりの描画（α演算）を必要とした例を示す。この場合、スパン塗りつぶし処理部119は、スパンデータ708から、背景になる色を取得する（S709）。そして、スパンの長さ分を持つバッファ711に暫定的に書き込む（S710）。
【００３７】
その後、前景になるフィル情報から色と、前景を透過して示す割合（α情報）を取得する（S712）。そして、背景をバッファ711から読み出し前景とピクセルごとにα演算を行う（S713）。そして、その結果をページイメージ715の所定のスパン位置716に書き込む（S714）。
【００３８】
プロセッサCの処理負荷は、ページ内のオブジェクトがすべて上書きで指定されている場合は軽くなり、オブジェクトの背景色を意識する必要があり、かつオブジェクト同士の重なりが多い場合は処理が重くなる。単純に黒文字がページ内に多く含まれるような帳票データを考えた場合、プロセッサBで行われる２値ビットマップからエッジリストを抽出しスパンデータを作成する処理は非常に時間がかかる。その半面、プロセッサCは２値ビットマップ内部の図形のアウトライン内部を黒で塗りつぶす処理となり比較的簡単な処理になる。そのためプロセッサCに比べてプロセッサBの処理が非常に重くなり、マルチCPUの構成を活かせずにレンダリング処理部の速度が低下してしまう。
【００３９】
次に、エッジリスト数閾値判定処理部113によるエッジリスト数の生成を抑制するように指示された後の処理を説明する。この処理は、上述のような処理負荷の偏りを解消し、マルチCPUの構成を活かしてレンダリング処理を高速化することが可能である。
【００４０】
図８の参照によりエッジ位置抽出処理部112がエッジリスト数閾値判定処理部113から、エッジリスト数の生成（増加）を抑制するように指示された後に、２値ビットマップのエッジ情報からエッジ位置を抽出する処理を説明する。エッジ位置抽出処理部112はエッジリスト数を削減するために以下の処理を実行する。エッジ位置抽出処理部112は、２値ビットマップ内の図形のアウトラインとラインの交差位置をエッジ位置として抽出するのではなく、まず、２値ビットマップのオブジェクトを囲む矩形領域（以下、「バウンディングボックス」という）を設定する。そして、２値ビットマップのバウンディングボックス801とライン804との交差位置802および803をエッジ位置として抽出する。その結果、エッジ位置抽出処理部112はエッジリスト805およびエッジリスト806を抽出する。
【００４１】
図９の参照により、２値ビットマップのバウンディングボックスとラインとの交差位置をエッジ位置として抽出した時の効果を説明する。画像形成結果901の１つのライン902における、エッジ位置抽出処理部112のエッジリスト作成の様子を以下に示す。
【００４２】
903はエッジ位置抽出処理部112が２値ビットマップ内部の図形のアウトラインとライン902との交差位置をエッジ位置として抽出した例である。この場合は４つのエッジリストを生成する必要がある。これに対して904はエッジ位置抽出処理部112が２値ビットマップのバウンディングボックスとライン902との交差位置をエッジ位置として抽出した例である。この場合、２つのエッジリストを生成する必要がある。
【００４３】
このように「H」という２値ビットマップ内部の図形の形状が簡単なものでも、エッジ位置情報903は、エッジ位置情報904に対して２倍のデータ量となる。例えば、漢字の「難」であれば、エッジ位置抽出処理部112が２値ビットマップ内部の図形のアウトラインとラインの交差位置をエッジ位置として抽出する場合、最大で１２のエッジリストを生成する必要がある。これに対して、エッジ位置抽出処理部112が２値ビットマップのバウンディングボックスとライン902との交差位置をエッジ位置として抽出した場合、左右に１つずつ、常に２つのエッジリストを生成すれば良い。このように、２値ビットマップのバウンディングボックスとライン902との交差位置をエッジ位置として抽出した場合、抽出すべきエッジ位置のデータの量を削減することが可能になる。
【００４４】
図１０を参照して、エッジ位置抽出処理部112が２値ビットマップのバウンディングボックスとラインとの交差位置をエッジ位置として抽出した場合に、エッジ情報107とフィル情報108とを書き替える処理について説明する。
【００４５】
エッジ位置抽出処理部112が２値ビットマップのバウンディングボックスとラインとの交差位置をエッジ位置として抽出した場合、スパン塗りつぶし処理部119で行われる２点のエッジ間の塗りつぶしは２値ビットマップで塗る必要がある。そのために、書き換え処理が実行される。エッジ情報1002は、文字「H」1001の２値ビットマップ内部の図形のアウトラインとラインの交差位置をエッジ位置として抽出するように指示するものである。エッジ位置抽出処理部112は、２値ビットマップのバウンディングボックスとラインとの交差位置をエッジ位置として抽出するように指示するエッジ情報1005に書き替える。
【００４６】
エッジ情報1005において、エッジ位置抽出処理部112は、エッジの種類1003をバウンディングボックスに設定する。また、エッジ位置抽出処理部112は、エッジ情報1002の２値ビットマップへのポインタが書かれていた部分を２値ビットマップのバウンディングボックス幅1006に書き替える。
【００４７】
エッジ位置抽出処理部112は、開始X座標1004とバウンディングボックス幅1006から容易にバウンディングボックスとラインとの交差位置を求めることができる。エッジ位置抽出処理部112は、バウンディングボックスの左端とラインとの交差するエッジ位置を開始X座標1004とする。そして、エッジ位置抽出処理部112は、開始X座標1004にバウンディングボックス幅1006を加算した座標を、バウンディングボックスの右端とラインとの交差するエッジ位置とする。エッジ位置抽出処理部112はフィル種類がイメージであることを示すフィル情報1009を新規に作成する。そして、エッジ位置抽出処理部112は、フィル情報1009との関連性を示す情報をエッジリスト1005に含まれるフィル情報への関連性を保持するデータ（フィル情報＝４）をエッジ情報1005に追加する。
【００４８】
図11を用いて、２値ビットマップのバウンディングボックスとラインとの交差位置がエッジ位置として抽出された場合、スパン抽出処理部117で行われるスパンデータ生成処理の変更について説明する。
【００４９】
スパン抽出処理部117がスパン1101に対するスパンデータに文字「H」のフィル情報108のみを含めてスパン塗りつぶし処理部119に送ってしまうと、文字「H」のみが塗りつぶされるので1102のように背面の三角形が画像形成されない。スパン抽出処理部117はフィル情報のROPが背面にあるオブジェクトを利用する情報（ROP=COPYPEN）であるか否かを判定する。ROPが背面にあるオブジェクトを利用する情報であった場合、スパン抽出処理部117はスパンデータには三角形の「灰色（RGB=100,100,100）」のフィル情報1105も含めてスパン塗りつぶし処理部119に送る。
【００５０】
図12を用いて２値ビットマップのバウンディングボックスとラインとの交差位置をエッジ位置として抽出された場合、スパン塗りつぶし処理部119で行われる上記２点のエッジ位置間の塗りつぶし処理について説明する。図11を用いて説明したようにスパン抽出処理部117により生成されるデータには背景である「灰色(RGB=100,100,100)」のフィル情報と、前景である文字「H」の２値ビットマップのフィル情報を含んでいる。
【００５１】
スパン塗りつぶし処理部119は、背景である「灰色(RGB=100,100,100)」のフィル情報を取得する(S1202)。そして、スパン塗りつぶし処理部119は、スパンの長さ分のバッファ1204のすべてのピクセルを「灰色(RGB=100,100,100)」に書き替える(S1203)。
【００５２】
その後、スパン塗りつぶし処理部119は、文字「H」の２値ビットマップから１ピクセルずつ取り出し（S1205）、バッファ1204からも同様に１ピクセル取り出す（S1206）。そして、スパン塗りつぶし処理部119は、取り出した２つピクセルを、スパンデータ1201の中に含まれる前景と背景とを合成するための合成情報（ここではOR演算、ROP=MERGEPEN）に従って合成を行う(S1206)。スパン塗りつぶし処理部119は、合成結果をページイメージ1208内の所定のスパン位置1209に書き出す(S1207)。エッジ位置抽出処理部112が２値ビットマップのバウンディングボックスとラインとの交差位置をエッジ位置として抽出することにより、エッジリスト量が削減されプロセッサBの処理負荷を軽減することができる。本実施形態によれば、処理負荷が均等化されマルチCPUを活かすことが可能となり、レンダリング処理部109の処理速度が向上する。
【００５３】
次に図13から図15の参照により、エッジリスト数閾値判定処理部113で保持するエッジリスト数の閾値の例について説明する。エッジリスト1301は、プロセセッサBの制御の下に実行される、エッジリスト作成処理1302と、エッジリストのソート処理1303と、エッジリストからスパンデータを作成するための作成処理1304と、の最低3回、アクセスされる。プロセッサBとRAM1404との構成が図14に示される構成の場合、プロセッサBはエッジリストをキャッシュメモリ1403またはRAM1404から演算回路1402に取得する。プロセッサBの演算回路1402からキャッシュメモリ1403へのアクセスには1Cycle、演算回路1402からRAM1404へのアクセスには30Cycleかかるものとする。この構成でエッジリストが全てキャッシュメモリ1403に収まる容量の場合、プロセッサBに含まれる演算回路1402は高速にエッジリスト1301（図13）へのアクセスができるため高速に処理することが出来る。エッジリスト1301がキャッシュメモリ1403に全て格納されるため、演算回路1402は高速にエッジリスト1301にアクセスできる。そのため、エッジリスト1301が作成された作成処理1302以降のソート処理1303およびスパンデータ作成処理1304の時には、エッジリスト1301をキャッシュメモリ1403から取得すれば良い。
【００５４】
一方、エッジリスト1301がキャッシュメモリ1403に収まらない容量の場合、プロセッサBに含まれる演算回路1402は、RAM1404にアクセスしエッジリスト1301を取得するため高速に処理することが出来ない。
【００５５】
図15（a）のエッジリスト1501には250個のデータが格納されており、エッジリストの容量は1Kbyteである。これに対して図１５（ｂ）のエッジリスト1502には500個のデータが格納されており、エッジリストの容量は2Kbyteである。エッジリスト1501はキャッシュメモリ1302に収まるが、エッジリスト1502はキャッシュメモリ1302に収まらない。
【００５６】
キャッシュメモリ1403のキャッシュラインサイズが40byte、バス1405が１回のアクセスで通信できる最大のデータ量を32bitとする。また、演算回路1402からエッジリスト1301へのアクセスが1エッジリストごとの4byte（32bit）だとする。キャッシュラインサイズが40byteである場合、演算回路1402から1個目のエッジリストのアクセス（4byte）で、RAM1404から40byte分がキャッシュメモリ1403に格納される。その後、演算回路1402からの9個（36byte）のエッジリストのアドレスはキャッシュメモリ1403から行える。キャッシュメモリ1403にエッジリストが格納されていない場合、演算回路1402からRAM1404にあるエッジリスト1501（サイズが250個で1Kbyte）へのアクセスは975cycle（25×30＋225×1=975）となる。
【００５７】
キャッシュメモリ1403にエッジリストのデータがすべて入っている場合、演算回路1402からキャッシュメモリ1403にあるエッジリスト1501（エッジリストのサイズが250個で1Kbyte）は250cycleとなる。エッジリストのデータのソート、スパンデータの作成において、演算回路1402からキャッシュメモリ1403にあるエッジリスト1501へのアクセスは、それぞれ250cycleとなる。つまり250個のエッジリスト1501をプロセッサBが取得するためには1475Cycle（975＋250＋250=1475Cycle）のアクセスが必要となる。
【００５８】
次にキャッシュメモリ1403にエッジリストが格納されていない場合、演算回路1402からRAM1404にあるエッジリスト1502（サイズが500個で2Kbyte）へのアクセスは1950cycle（50×30＋450×1=1950）となる。エッジリスト1502はキャッシュメモリ1403に収まらないので、500個のエッジリスト1502をプロセッサBが取得するためには5850Cycle（1950＋1950＋1950=5850）のアクセスが必要となる。エッジリスト1502のデータ量はエッジリスト1501のデータ量の２倍である。しかしながら、データ取得のために必要とされるアクセスのサイクル数の比較により、プロセセッサBがエッジリスト1502のデータを取得するための時間はエッジリスト1501のデータの取得時間に比べて、約４倍の時間を要する。
【００５９】
この様にエッジリストに格納されるデータ量が増えてプロセッサBに搭載のキャッシュメモリ1403に収まらなくなると、プロセッサBの処理速度がさらに低下することが予測される。そのため、エッジリスト数閾値判定処理部113はキャッシュメモリ1403にエッジリストが収まるように、例えば、キャッシュメモリの半分の容量のエッジリストが作成されたデータ量を閾値とすることが可能である。ページ全体の制御情報を含むインストラクション106の解析により、その後、追加されるエッジ情報の数（データ量）を求めることができる。キャッシュメモリ1403の空き容量と、今後、追加されるエッジ情報の数との比較によりエッジリスト数閾値判定処理部113は、エッジリスト総数を制御するための閾値を任意に設定することも可能である。例えば、図１５（ｃ）のテーブル1503ように追加するエッジ情報が100個あり、現状までに70個のエッジリストを作成した時点（作成済）で、テーブル1504に示すようにエッジリストの個数が190個であるとする。キャッシュメモリ1403に格納できるエッジリストの個数が250とすると、この後に作成するエッジリストは60個以下でなくてはならない。エッジ情報の１つに対してエッジリストは最低2個作成される。
【００６０】
例えば、２値ビットマップ内部の図形のアウトラインとラインの交差点をエッジリストとして作成する方法では、エッジ情報の１つから2個以上のエッジリストが作成される可能性がある。２値ビットマップのバウンディングボックスとラインの交差点をエッジリストとして作成する方法ではエッジリストは必ず２個の作成で済む。従って、残りのエッジ情報が30個とすると、残りのエッジ情報の１つから作成されるエッジリストは全て２個ずつ作成されれば、この後に作成するエッジリストは60個以下に収まることになる。作成済のエッジリストが70個に達した段階で２値ビットマップ内部の図形のアウトラインとラインの交差点をエッジリストとする方法から２値ビットマップのバウンディングボックスとラインの交差点をエッジリストとすれば良い。
【００６１】
図16のフローチャートを参照して、プロセッサBで行われる１ページのレンダリング処理の流れについて説明する。プロセッサBはROM、RAM、HDDのいずれかの記憶手段に記憶されプログラムを読みだして、図16の処理を実行する。エッジリスト数閾値判定処理部113はページ処理の開始時に、作成済みのエッジリスト数を初期化（０）し、２値ビットマップからのエッジ抽出方法を切り替える閾値を設定する（S1601）。このフローチャートの処理において、閾値は固定の値としROM内に存在する初期値か、ユーザが画像形成装置のユーザーインターフェースを操作して所定のRAM領域に値を書き込んだものを設定するような構成とする。
【００６２】
エッジ位置抽出処理部112は２値ビットマップがエッジ情報として指定された場合のエッジ位置抽出方法を「２値ビットマップ内部の図形とラインとの交差点をエッジ位置として抽出する」に設定する(S1602)。そして、ディスプレイリスト解釈部111はディスプレイリスト105を読み込み、ディスプレイリスト105のインストラクション106に含まれる電子ドキュメントを構成している各ページの画像形成を制御するための制御情報を解釈する(S1603)。ディスプレイリスト解釈部111がインストラクション106を解釈した結果、ページ終了を意味するディスプレイリストであった場合（S1604-Yes）、処理はステップS1650に進められる。そして、ディスプレイリスト解釈処理部111は１ページのレンダリングを終了する(S1650)。
【００６３】
ステップS1604の判定において、ディスプレイリスト解釈部111がインストラクション106を解釈した結果、ページ終了でないディスプレイリストであった場合（S1604-No）、処理はステップS1605に進められる。ディスプレイリスト解釈部111がディスプレイリスト105を解釈した結果、エッジ情報の削除を意味するディスプレイリストであった場合（S1605−Yes）、処理はステップS1606に進められる。
【００６４】
ディスプレイリスト解釈部111は、エッジ位置抽出処理部112にエッジ情報の削除処理の実行を指示する。この指示を受けて、エッジ位置抽出処理部112はディスプレイリスト105に含まれるインストラクション106から削除するエッジ情報を取得する(S1606)。そして、エッジ位置抽出処理部112は、使用中のエッジ情報124とエッジリスト115とから該当するエッジ情報を削除する(S1607)。エッジ位置抽出処理部112は削除したエッジリスト数をエッジリスト閾値判定処理部113に伝え、エッジリスト閾値判定処理部113は作成済みエッジリスト数を更新する(S1608)。そして、処理はステップS1603に戻され、同様の処理が繰り返される。
【００６５】
一方、ステップS1605の判定で、ディスプレイリスト解釈部111がエッジ情報の削除を意味しないディスプレイリストであった場合（S1605−No）、処理はステップS1609に進められる。ディスプレイリスト解釈処理部111はディスプレイリスト105を解釈した結果、エッジのロードおよび描画開始を指示するもので無い場合（S1609-No）、ページ高さ、ページ幅の設定を各処理部にその情報を通知する(S1610)。
【００６６】
ディスプレイリスト解釈処理部111はディスプレイリスト105を解釈した結果、エッジのロードおよび描画開始を指示するものであった場合（S1609-Yes）、処理はステップS1611に進められる。ディスプレイリスト解釈処理部111は、エッジ位置抽出処理部112にエッジ情報の追加と画像形成の実行開始を指示する。この通知を受けて、エッジ位置抽出処理部112は画像形成するライン数を取得し(S1611)、エッジ位置抽出処理部112はディスプレイリスト105に含まれるインストラクション106から追加するエッジ情報数を取得する（S1612）。エッジ位置抽出処理部112はディスプレイリスト105に含まれるインストラクション106から追加するエッジ情報を取得し、使用中のエッジ情報124に追加する(S1613)。
【００６７】
エッジ位置抽出処理部112は使用中のエッジ情報124から追加されたエッジ情報を参照し、どのエッジ位置の抽出が２値ビットマップからの抽出処理で行うかを判定する(S1614)。エッジ位置抽出方法が２値ビットマップからの抽出でない場合（S1614−No）、エッジ位置抽出処理部112は指定されている方法でエッジ位置を抽出しエッジリストを作成する(S1615a)。エッジ位置抽出処理部112はステップS1615aで作成されたエッジ数をエッジリスト閾値判定処理部113に伝え、エッジリスト閾値判定処理部113は作成済みエッジリスト数を更新する(S1615b)。そして、処理をステップS1613に戻し、同様の処理を繰り返す。
【００６８】
一方、ステップS1614の判定において、エッジ抽出方法が２値ビットマップからの抽出であった場合（S1614-Yes）、処理はステップS1616に進められる。エッジ位置抽出処理部112はエッジリスト閾値判定処理部113に２値ビットマップからS1617とS1618のどちらの方法で抽出すべきかを問い合わせる。
【００６９】
ステップS1616において、エッジリスト閾値判定処理部113は作成済みエッジリスト数と閾値とを比較する。作成済みのエッジリスト数が閾値より少ない場合、処理はステップS1617に進められる。エッジリスト閾値判定処理部113はエッジ位置抽出処理部112に「２値ビットマップ内部の図形とラインとの交差点をエッジ位置として抽出する」ように指示する。この指示を受けて、エッジ位置抽出処理部112は、２値ビットマップ内部の図形とラインとの交差点をエッジ位置として抽出し、エッジリストを作成する(S1617)。
【００７０】
S1616の判定で、作成済みのエッジリスト数が閾値以上の場合に、エッジリスト閾値判定処理部113はエッジ位置抽出処理部112に「２値ビットマップのバウンディングボックスとラインとの交差点をエッジ位置として抽出する」ように指示する。エッジ位置抽出処理部112はその指示に従い、２値ビットマップのバウンディングボックスとラインとの交差点をエッジ位置として抽出し、エッジリストを作成する(S1618)。
【００７１】
ステップS1617およびS1618でエッジ位置抽出処理部112が作成したエッジリストはすでに作成済みのエッジリストに追加される(S1619)。ステップS1620において、エッジ位置抽出処理部112はディスプレイリスト105のインストラクション106の中での指示で追加されたエッジ情報の処理が全て終了したか否かを判定する。エッジ位置抽出処理部112は、エッジ情報の追加処理が終了していないと判定した場合、処理をステップS1613に戻し、同様の処理が繰り返される。一方、エッジ位置抽出処理部112は、エッジ情報の追加処理が終了した判定した場合、処理はステップS1621に進められる。
【００７２】
ステップS1621において、エッジ位置抽出処理部112はエッジ位置ソート処理部116にエッジリストのソートを指示し、エッジ位置ソート処理部116はエッジリストを参照しソートを実行する（S1621）。ソートが終了するとエッジ位置ソート処理部116はスパン抽出処理部114にスパンデータの生成を指示し、スパン抽出処理部114はスパンデータを生成し(S1622)、スパンデータをプロセッサCに転送する(S1623)。
【００７３】
スパン抽出処理部114はエッジリストのすべての処理を実行したら（S1624-Yes）、エッジ位置抽出処理部112に処理の終了を返す。一方、ステップS1624の判定で、スパン抽出処理部114はエッジリストのすべての処理を実行していないと判定した場合、処理をステップS1626に進める。エッジ位置抽出処理部112は、１ライン分の処理の終了に従い、ステップS1611で取得したライン数の更新を行う（S1626）。
【００７４】
エッジ位置抽出処理部112は、使用中のエッジ情報124の全てのエッジ情報を参照する。抽出されたエッジが２値ビットマップからの抽出でない場合（S1627-No）、エッジ位置抽出処理部112は、指定されている方法でエッジ位置を抽出しエッジリストを作成する(S1628)。エッジ位置抽出処理部112はステップS1628で作成されたエッジ数をエッジリスト閾値判定処理部113に伝え、エッジリスト閾値判定処理部113は作成済みエッジリスト数を更新する(S1629)。そして、処理をステップS1621に戻し、同様の処理を繰り返す。
【００７５】
一方、S1627の判定において、エッジ抽出方法が２値ビットマップからの抽出であった場合（S1627-Yes）、処理はステップS1630に進められる。エッジ位置抽出処理部112はエッジリスト閾値判定処理部113に２値ビットマップからS1631とS1632のどちらの方法で抽出すべきかを問い合わせる。
【００７６】
ステップS1630において、エッジリスト閾値判定処理部113は作成済みエッジリスト数と閾値とを比較する。作成済みのエッジリスト数が閾値より少ない場合、処理はステップS1631に進められる。エッジリスト閾値判定処理部113はエッジ位置抽出処理部112に「２値ビットマップ内部の図形とラインとの交差点をエッジ位置として抽出する」ように指示する。この指示を受けて、エッジ位置抽出処理部112は、２値ビットマップ内部の図形とラインとの交差点をエッジ位置として抽出し、エッジリストを作成する(S1631)
一方、S1630の判定で、作成済みのエッジリスト数が閾値以上の場合に、エッジリスト閾値判定処理部113はエッジ位置抽出処理部112に「２値ビットマップのバウンディングボックスとラインとの交差点をエッジ位置として抽出する」ように指示する。エッジ位置抽出処理部112はその指示に従い、２値ビットマップのバウンディングボックスとラインとの交差点をエッジ位置として抽出し、エッジリストを作成する(S1632)。
【００７７】
ステップS1631およびS1632でエッジ位置抽出処理部112が作成したエッジリストはすでに作成済みのエッジリストに追加、更新または削除される(S1633)。ここで追加または更新または削除するのは２値ビットマップ内の図形のアウトラインとラインの交差した部分をエッジ位置として抽出する場合、２値ビットマップ内でアウトラインが新たに出現したり、消えたりするためである。
【００７８】
ステップS1634において、エッジ位置抽出処理部112で使用中のエッジ情報124に含まれるエッジ情報のエッジリストの追加または更新または削除を全て終了したか否かが判定される。処理が終了した場合に（S1634-Yes）、処理はステップS1621に戻され、エッジリストのソート処理が実行される。ステップS1634の判定で、処理が終了していないと判定される場合に（S1634-No）、処理はステップS1627に戻され、S1627以降の処理が繰り返される。
【００７９】
図17を用いてコンフィグラブルプロセッサを用いた構成のシステム構成例を説明する。バス1710上に物理インターフェース1704、ROM1705、RAM1706、HDD1707、エンジン1708のほかに、1701から1703の3のCPUが接続されている。汎用のCPU1701は、外部インターフェースや電子ドキュメントやPDLデータの処理を行う。電子ドキュメントやPDLデータには様々なデータが含まれるので、キャッシュメモリ容量や動作クロックが高く、コストは高いが様々な処理を高速に実行できるCPUが求められる。コンフィグラブルプロセッサ1702は図１のプロセッサBに相当する。プロセッサBではエッジリストの処理のみを行えば良いので、おもにメモリアクセスが中心になるため、プロセセッサ内部の演算能力が低くて良いため動作クロックは低めで、特別な演算回路なども搭載する必要はない。上述してきたようにプロセッサBは同じメモリにアクセスすることが多いのでキャッシュメモリをある程度大きめな構成にしておけば、コストを抑えながら速度向上することが出来る。
【００８０】
コンフィグラブルプロセッサ1703は図１のプロセッサCに相当する。プロセッサCではスパンを順番に塗りつぶしていくため、同じメモリをアクセスすることが少なくキャッシュメモリの有効性が低いためキャッシュメモリの容量を少なくて良い。プロセッサCではROPやα演算などのプロセッサ内部の処理が多くなるので、ROPやα演算などを行う演算回路をコンフィグラブルプロセッサ内に搭載しておくことによりコストを抑えながら速度を向上することができる。
【００８１】
コンフィグラブルプロセッサ1702と1703とは特定の処理に特化して作成されている。このため、コンフィグラブルプロセッサ1703でエッジリスト処理を行い、コンフィグラブルプロセッサ1702で、背面にあるオブジェクトの描画処理を行うようにする負荷分散では高速化できない。本実施形態ではコンフィグラブルプロセッサ1702と1703とで行う処理を変えずに、処理負荷のみを変更できるためコンフィグラブルプロセッサで構成するシステムに適している。本実施形態によれば、多量の文字オブジェクトやグラフィックスオブジェクトを含む電子ドキュメントやＰＤＬデータを高速にレダリング処理することが可能な画像形成技術の提供が可能になる。
【００８２】
（第２実施形態）
第１実施形態ではレンダリング処理部109のエッジリスト数閾値判定処理部113が設定した閾値に基づき、２値ビットマップからのエッジ位置の抽出方法を切り替える方法について説明した。エッジ位置の抽出方法の切り替えは、この例に限定されず、例えば、ディスプレイリストを作成するときに電子ドキュメントおよびPDLデータ生成部で切り替えを判断しても良い。
【００８３】
図18に示すようにページ1801内に「A」という文字と「難」という文字がある電子ドキュメントやPDLデータが画像形成装置で処理される場合を想定する。レンダリング処理部109でのエッジリスト作成量を減らすためには、アウトラインが簡単な「A」はエッジ位置を抽出するが、アウトラインが複雑な「難」はエッジ位置の抽出を行わなければ良い。電子ドキュメントおよびPDLデータを処理することが可能なデータ生成部104がディスプレイリストを生成するとき、データ生成部104は、「A」を1802で示すようなエッジ情報として作成する。データ生成部104は、「難」を1803に示すように２値ビットマップのアウトラインをエッジ情報として登録し、1804に示すように２値ビットマップのフィル情報を作成する。データ生成部104で各文字のアウトラインの複雑さの判定は、２値ビットマップを実際に走査して判定する方法がある。
【００８４】
データ生成部104で２値ビットマップを実際に走査して判定すると、処理が遅くなる場合は、電子ドキュメントやPDLデータに文字コードが付属していれば、１バイト文字と２バイト文字で判定する。また、各文字コードに対応したアウトラインの複雑さ（抽出される最大のエッジリスト数）などのデータベースをあらかじめROMやHDD上に保持しておく方法が考えられる。
【００８５】
図19から図21の参照により、レンダリング処理部109の処理と実施形態の効果を具体的に説明する。図19のプロセッサ1902とプロセッサ1903とは図１のプロセッサBとプロセッサCとに対応する。プロセッサ1902はディスプレイリスト1901を読み込み、２値ビットマップのエッジデータから、２値ビットマップ内部の図形のアウトライン情報1903(エッジリストおよびスパンデータ)を抽出する。プロセッサ1904は、プロセッサ1902が抽出したアウトライン情報1903を読み込み、アウトライン内部を塗りつぶす処理を行い実際の画像1905を生成する。1906に示すような2値ビットマップのエッジデータを多量に含む帳票データの画像形成を行う場合、1907に示すようにプロセッサ1902のアウトライン情報1903の処理負荷が多く、プロセッサ1904の処理負荷は少ない。
【００８６】
図２０において、2001は、図１９のプロセッサ1902が全ての２値ビットマップに対して、内部の図形のアウトラインをアウトライン情報1903として抽出する処理例を示している。2002では、図１９のプロセッサ1902が、１部の２値ビットマップに対して内部の図形のアウトラインをアウトライン情報1903として抽出する（2005）。そして、エッジリスト数の閾値を越えた２値ビットマップに対しては、プロセッサ1902がバウンディングボックスをアウトライン情報1903として抽出する(2006)本発明の実施形態の例である。
【００８７】
2002のようにプロセッサ1902がアウトライン情報を抽出することにより、プロセッサ1902の処理負荷は、2004に示すように処理時間（0.5秒）が軽減される。2002に示すようにプロセッサ1902がアウトライン情報を抽出した場合において、プロセッサ1904が２値ビットマップの背景になる画像と合成を行わない場合、背景画像が欠けてしまうという画像不正（図21の2101）が発生する。そのためプロセッサ1904は背景になる画像との合成を行い、2102に示すように背景画像が欠けてしまうのを防ぐ。
【００８８】
プロセッサ1904の処理負荷は背景との合成を行うため2103に示すように増加する。プロセッサ1902とプロセッサ1904とをパイプライン動作させた場合、どちらかの処理が遅い方の処理時間がレンダリング処理部109の処理時間となる。例えば、2002のようにプロセッサ1902がアウトライン情報を抽出することにより、プロセッサ1902の処理負荷は、0.6秒となる（図20）。２値ビットマップのエッジデータを多く含む帳票データ1906（図19）を処理する場合を想定する。この場合、プロセッサ1902に処理負荷が偏り、2104（図21）に示すようにレンダリング処理部109の処理時間は1.1秒となり、処理時間は0.6秒から1.1秒まで遅くなる。本発明の実施形態を適用すると、２値ビットマップのエッジデータを多く含む帳票データ1906を処理する場合、プロセッサ1902の処理負荷が軽減され、処理時間は1.1秒から0.75秒まで軽減される。一方、プロセッサ1904の処理負荷は、処理時間として0.6秒から0.75秒まで増加する。プロセッサ1902とプロセッサ1904との処理負荷が分散され、レンダリング処理部109の処理時間は2104に示す処理時間1.1秒から0.75秒まで短縮化される。
【００８９】
本実施形態によれば、多量の文字オブジェクトやグラフィックスオブジェクトを含む電子ドキュメントやＰＤＬデータを高速にレダリング処理することが可能な画像形成技術の提供が可能になる。
【図１】
2010280084.tif 000003
【図３】
2010280084.tif 000004
【図４】
2010280084.tif 000005
【図５】
2010280084.tif 000006
【図６】
2010280084.tif 000007
【図９】
2010280084.tif 000008
【図１１】
2010280084.tif 000009
【図１２】
2010280084.tif 000010
【図１３】
2010280084.tif 000011
【図１４】
2010280084.tif 000012
【図１５】
2010280084.tif 000013
【図１６】
2010280084.tif 000014
【図１７】
2010280084.tif 000015
【図１８】
2010280084.tif 000016
【図１９】
2010280084.tif 000017
【図２０】
2010280084.tif 000018
【図２１】
2010280084.tif 000019
【図２】
2010280084.tif 000020
【図７】
2010280084.tif 000021
【図８】
2010280084.tif 000022
【図１０】
2010280084.tif 000023