(57)【要約】      （修正有）【課題】画像形成処理にかかるパイプラインが深く並列性の高い処理ユニットのソフトウェア資産を流用しつつ、分岐命令による処理速度の低下に対処する。【解決手段】パイプライン方式の処理ユニットにおいて、画像形成処理特有の描画種情報に関連付けられる属性情報を基に、画像形成処理中の分岐命令に続く処理を予測し、分岐アドレスを確定する前に、分岐命令と並行的に分岐先の命令を、各処理ユニットにおいて投機的に実行することで処理時間を短縮する。【選択図】図１
2011197951.tif 000002
【特許請求の範囲】
【請求項１】
命令の投機的実行および条件分岐命令の予測分岐アドレスを当該条件分岐命令の実行に先立って得るための分岐予測命令の実行ができる処理ユニットにより、処理対象の画像データの領域の特性を条件として分岐する条件分岐命令を実行することで前記条件に応じた画像処理を実行させる画像処理装置であって、
前記処理ユニットは、
前記条件分岐命令に先だって処理対象の画像データの領域の属性を示す論理値を用いて前記条件分岐命令による予測分岐アドレスを決定し、
前記分岐予測命令を実行して前記予測分岐アドレスを獲得し、前記条件分岐命令の後には、前記予測分岐アドレスの命令を投機的に実行する
ことを特徴とする画像処理装置。
【請求項２】
前記処理ユニットはパイプライン方式の処理ユニットであり、
前記投機的実行は、前記条件分岐命令による分岐アドレスが確定する前に、当該条件分岐命令と並行して当該条件分岐命令の分岐先の命令を実行することであることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記画像処理は前記領域の圧縮処理であり、
前記特性は、前記領域がモノクロームか否かであり、
前記属性は、前記領域に含まれるオブジェクトの種類として少なくともイメージ属性、グラフィック属性、文字属性を表す論理値を含み、
前記予測分岐アドレスは、前記属性に対応する論理値と、当該属性に対応する圧縮処理プログラムのアドレスとの乗算により決定されることを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
前記画像処理は前記領域の圧縮処理であり、
前記特性は、前記領域の色のパターンであり、
前記属性は、前記領域に含まれるオブジェクトの種類として少なくともイメージ属性、グラフィック属性、文字属性を表す論理値を含み、
前記予測分岐アドレスは、前記属性に対応する論理値を、当該属性に対応する圧縮処理プログラムのアドレスに乗じて決定されることを特徴とする請求項１または２に記載の画像処理装置。
【請求項５】
前記画像処理は前記領域の変換処理であり、
前記特性および前記属性は、前記領域に含まれるオブジェクトの種類を表す論理値であり、
前記予測分岐アドレスは、前記属性に対応する論理値を、当該属性に対応する圧縮処理プログラムのアドレスに乗じて決定されることを特徴とする請求項１または２に記載の画像処理装置。
【請求項６】
並列して実行が可能な複数の処理ユニットにより、処理対象の画像データの領域の特性を条件として当該条件に応じた画像処理を実行させる画像処理装置であって、
前記複数の処理ユニットのひとつは、
前記条件を判定する条件分岐命令に先だって、処理対象の画像データの領域の属性に対応づけた画像処理のための命令のアドレスを、前記条件分岐命令による予測分岐アドレスとして決定し、
他の処理ユニットにより、前記予測分岐アドレスから命令を実行させる
ことを特徴とする画像処理装置。
【請求項７】
処理対象の画像データの領域の特性を条件として当該条件に応じた画像処理を実行する画像処理装置であって、
前記条件を判定する条件分岐命令に先だって、処理対象の画像データの領域の属性に対応づけた画像処理のための命令のアドレスを、前記条件分岐命令による予測分岐アドレスとして決定し、
前記予測分岐アドレスから命令を投機的に実行する
ことを特徴とする画像処理装置。
【請求項８】
命令の投機的実行および条件分岐命令の予測分岐アドレスを当該条件分岐命令の実行に先立って得るための分岐予測命令の実行ができる処理ユニットにより、処理対象の画像データの領域の特性を条件として分岐する条件分岐命令を実行することで前記条件に応じた画像処理を実行する画像処理方法であって、
前記条件分岐命令に先だって処理対象の画像データの領域の属性を示す論理値を用いて前記条件分岐命令による予測分岐アドレスを決定する工程と、
前記分岐予測命令を実行して前記予測分岐アドレスを獲得し、前記条件分岐命令の後には、前記予測分岐アドレスの命令を投機的に実行する工程と
を含むことを特徴とする画像処理方法。
【請求項９】
並列して実行が可能な複数の処理ユニットにより、処理対象の画像データの領域の特性を条件として当該条件に応じた画像処理を実行する画像処理方法であって、
前記複数の処理ユニットのひとつが、
前記条件を判定する条件分岐命令に先だって、処理対象の画像データの領域の属性に対応づけた画像処理のための命令のアドレスを、前記条件分岐命令による予測分岐アドレスとして決定する工程と、
他の処理ユニットにより、前記予測分岐アドレスから命令を実行させる工程と
を含むことを特徴とする画像処理方法。
【請求項１０】
画像処理装置により、処理対象の画像データの領域の特性を条件として当該条件に応じた画像処理を実行する画像処理方法であって、
前記画像処理装置の決定手段が、前記条件を判定する条件分岐命令に先だって、処理対象の画像データの領域の属性に対応づけた画像処理のための命令のアドレスを、前記条件分岐命令による予測分岐アドレスとして決定する決定工程と、
前記画像処理装置の実行手段が、前記予測分岐アドレスから命令を投機的に実行する実行工程と
を含むことを特徴とする画像処理方法。
【請求項１１】
命令の投機的実行および条件分岐命令の予測分岐アドレスを当該条件分岐命令の実行に先立って得るための分岐予測命令の実行ができる処理ユニットにより、処理対象の画像データの領域の特性を条件として分岐する条件分岐命令を実行することで前記条件に応じた画像処理を実行するためのプログラムであって、
前記条件分岐命令に先だって処理対象の画像データの領域の属性を示す論理値を用いて前記条件分岐命令による予測分岐アドレスを決定する工程と、
前記分岐予測命令を実行して前記予測分岐アドレスを獲得し、前記条件分岐命令の後には、前記予測分岐アドレスの命令を投機的に実行する工程と
を前記処理ユニットにより実行させるためのプログラム。
【請求項１２】
並列して実行が可能な複数の処理ユニットにより、処理対象の画像データの領域の特性を条件として当該条件に応じた画像処理を実行するためのプログラムであって、
前記複数の処理ユニットのひとつが、
前記条件を判定する条件分岐命令に先だって、処理対象の画像データの領域の属性に対応づけた画像処理のための命令のアドレスを、前記条件分岐命令による予測分岐アドレスとして決定する工程と、
他の処理ユニットにより、前記予測分岐アドレスから命令を実行させる工程と
を前記処理ユニットにより実行させるためのプログラム。
【請求項１３】
処理ユニットにより、処理対象の画像データの領域の特性を条件として当該条件に応じた画像処理を実行するためのプログラムであって、
前記条件を判定する条件分岐命令に先だって、処理対象の画像データの領域の属性に対応づけた画像処理のための命令のアドレスを、前記条件分岐命令による予測分岐アドレスとして決定する決定工程と、
前記予測分岐アドレスから命令を投機的に実行する実行工程と
を前記処理ユニットにより実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理方法に関し、特にレンダリングおよび画像処理の高速化技術に関する。
【背景技術】
【０００２】
パーソナルコンピュータなどの情報処理装置で生成されたＰＤＬデータを受け取った画像形成装置は、その内部の処置装置或いは汎用プロセッサによりＰＤＬデータを解釈しレンダリング処理してラスタイメージデータを生成する。さらに前記処置装置或いは汎用プロセッサはラスタイメージデータに必要に応じて画像処理を施し、そのデータを画像形成装置内の印刷エンジンに転送する。印刷エンジンは、ラスタイメージデータを用紙などの印刷媒体の上に可視化した画像を形成する。
【０００３】
これら汎用プロセッサは、一般的には処理性能を高めるためにパイプライン構造を採用したパイプラインプロセッサである。パイプラインプロセッサでは、プロセッササイクル毎に命令がフェッチされ、複数の命令の実行が並列に進む。そのために、分岐命令による分岐の有無が決定するのは、分岐命令に後続する命令の実行が始まった後であり、現在実行している命令が実際の分岐先と異なることもあり得る。その場合には、分岐先からあらためて命令を実行する必要があり、現在行っている命令の実行は分岐命令まで遡って無駄な処理となる。このいわゆる分岐ペナルティが処理性能を劣化させるため、従来の汎用プロセッサは、できるだけ高い確率で分岐の有無を予測する分岐予測機能を備えている。
【０００４】
この汎用プロセッサに対して、画像形成装置の性能をより向上させるべく、複数のプロセッサを搭載することで演算処理の並列性を高めたアーキテクチャを持つプロセッサが製品化されている（例えば非特許文献２、非特許文献３、非特許文献４等を参照）。これら複数のプロセッサにより並列実行を行い、一方のプロセッサで行った処理の結果を他のプロセッサが利用するなどして、処理の高速化が実現できる。この並列的なプロセッサは従来の汎用プロセッサと比較して分岐予測機能が貧弱（すなわち低精度）であるという弱点を持つ。そのため、並列実行した結果が、確定した条件分岐の結果、利用できないものであると、あらためて処理をし直すこととなり、並列処理による高速処理を享受できない。そこで、ソフトウェアによる最適化処理を行うことで、速度向上が図られてきた。たとえば分岐のヒント命令を使うことでパフォーマンスを向上させることが試みられている（例えば非特許文献１等を参照）。
【０００５】
また分岐命令による処理速度低下という問題に対して、専用ハードウェアを用いた解決手法も提案されている（例えば特許文献１等参照）。また他の対策として、画像処理にかかる分岐命令そのものを排除あるいは低減することによって分岐命令による処理速度低下という問題を解決する手法も提案されている（例えば特許文献２等参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１１−２０３１３５号公報
【特許文献２】特開２００３−２５６８２号公報
【非特許文献】
【０００７】
【非特許文献１】International Business Machines Corporation, Sony Computer Entertainment Inc., Toshiba Corporation、「ＳＰＵアセンブリ言語の仕様  Ｖｅｒｓｉｏｎ１．４」第１４−１５ページ、［ｏｎｌｉｎｅ］、２００６年１０月１１日、ソニーコンピュータエンターテイメント株式会社、［平成２１年９月２９日検索］、インターネット(URL:http://cell.scei.co.jp/pdf/SPU=_Assembly_Language_v14_j.pdf)
【非特許文献２】International Business Machines Corporation, Sony Computer Entertainment Inc., Toshiba Corporation、「Ｃｅｌｌ  Ｂｒｏａｄｂａｎｄ  ＥｎｇｉｎｅTMアーキテクチャ  Ｖｅｒｓｉｏｎ１．０１」、［ｏｎｌｉｎｅ］、２００６年１０月３日、ソニーコンピュータエンターテイメント株式会社、［平成２１年９月２９日検索］、インターネット(URL:http://cell.scei.co.jp/pdf/CBE_Architecture_v101_j.pdf)
【非特許文献３】KHRONOS GROUP、「OpenCL PDF Overview」、２００９年８月、ＫＨＲＯＮＯＳ  ＧＲＯＵＰ、［平成２１年９月２９日検索］、インターネット(URL:http://www.khronos.org/developers/libraly/overview/opencl_overview.pdf)
【非特許文献４】Tom R. Halfhill、「Parallel Processing With CUDA」、２００８年１月２８日、Microprocessor Report、［平成２１年９月２９日検索］、インターネット(URL:http://www.nvidia.com/docs/IO/55972/220401_Reprint.pdf)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
分岐に伴う処理能力の低下については、上述したように並列的なプロセッサでは特に著しく、有効な対策をしなければ、その処理能力の高さが損なわれてしまう。
【０００９】
そこで上述の専用ハードウェアを用いて分岐命令による処理速度の低下に対処すると、まさに専用ハードウェアが必要であるということ自体が問題となる。すなわち、コストの増大や回路規模の増加、またそれに伴う故障等の増加が問題となる。
【００１０】
また、画像処理にかかる分岐命令そのものを排除あるいは低減することで対照すると、画像処理のアルゴリズムの変更および再コーディングが必要となるという問題がある。すなわち、従来のソフトウェア資産を利用できず、労力やコストが増大し、プログラムの瑕疵の発生も懸念される。
【００１１】
これらを避けるため、ソフトウェアで分岐予測を行う場合、プロセッサの処理性能を劣化させないためには高い確率で分岐を予測するアルゴリズムを実装する必要がある。即ち、上述した並列的なプロセッサで画像形成に係る処理を行う場合、分岐を高確率で予測しなければ画像形成にかかる処理の速度が低下するという課題があった。
【００１２】
本発明は上記従来例に鑑みて成されたもので、既存のハードウェアおよび画像形成処理のソフトウェア資産を流用しつつ、パイプライン処理における分岐命令に伴う処理速度の低下という課題を解決することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために本発明は以下の構成を備える。
【００１４】
命令の投機的実行および条件分岐命令の分岐アドレスを当該条件分岐命令の実行に先立って得るための分岐予測命令の実行をできる処理ユニットにより、処理対象の画像データの領域の特性を条件として分岐する条件分岐命令を実行することで前記条件に応じた画像処理を実行させる画像処理装置であって、
前記処理ユニットは、
前記条件分岐命令に先だって画像データの処理対象の領域の属性を示す論理値を用いて前記条件分岐命令による予測分岐アドレスを決定し、
前記分岐予測命令を実行して前記予測分岐アドレスを獲得し、前記条件分岐命令の後には、前記予測分岐アドレスの命令を投機的に実行する。
【発明の効果】
【００１５】
本発明によれば、専用ハードウェアを必要とせず、既存ハードウェアを使用し、且つ既存の画像形成処理ソフトウェアを流用しつつ、分岐命令による速度低下という課題を解決できる。
【図面の簡単な説明】
【００１６】
【図１】情報処理装置と画像形成装置の構成を説明する図である。
【図２】本発明にかかるＰＤＬデータおよび中間データを説明する図である。
【図３】本発明にかかる画像形成にかかる処理を説明する図である。
【図４】本発明にかかる画像形成処理にかかる処理を説明する図である。
【図５】本発明にかかる印刷データおよび属性データを説明する図である。
【図６】本発明にかかる中間データを処理して印刷データを生成する処理を説明する図である。
【図７】第一実施形態にかかるラスタイメージデータを圧縮する処理を説明する図である。
【図８】本発明にかかるラスタイメージデータを圧縮する処理中の分岐予測を説明する図である。
【図９】本発明にかかる画像形成される印刷データ及び分割された属性データを説明する図である。
【図１０】本発明にかかるラスタイメージデータに対する画像処理を説明する図である。
【図１１】第ニ実施形態にかかるラスタイメージデータを圧縮する処理を説明する図である。
【図１２】第二実施形態にかかるラスタイメージデータを圧縮する処理中の投機実行の処理手順を説明する図である。
【図１３】第三実施形態にかかる２×２画素ブロックでとりうる色の組み合わせを示す図である。
【図１４】第三実施形態にかかる２×２画素ブロックでとりうる色の組み合わせを示すパターンフラグの一例を示す図である。
【図１５】第三実施形態にかかるラスタイメージデータを圧縮する処理を説明する図である。
【発明を実施するための形態】
【００１７】
［第一実施形態］
＜画像形成装置の構成＞
図１（Ａ）は本発明の一実施形態に係る画像形成装置１２と画像形成装置１２に接続された情報処理装置１１の構成を示すブロック図である。図１（Ａ）において、情報処理装置１１はＰＣやパーソナルコンピュータ、ワークステーションなどの情報処理装置である。情報処理装置１１はＰＤＬデータ１００を生成することが出来る。さらに情報処理装置１１はネットワークやＵＳＢに代表されるインターフェースを経由してＰＤＬデータ１００を含むデータを情報処理装置１１の外部の画像形成装置に転送することが出来る。
【００１８】
ＰＤＬデータ１００は図２（Ａ）に示すように、描画データ１００−１と印刷制御データ１００−２とを含むことが出来る。描画データ１００−１は、画像形成処理部１２−３で解釈でき、可視的な画像として描画出来るデータを含む。また印刷制御データ１００−２は、ＰＤＬデータ１００をどのような方法で画像形成すればよいかを含む情報を含む。印刷制御データ１００−２例えば、紙のサイズや、紙の種類などの印刷設定のほか、製本処理の方法などを含む後処理のための設定を含むことが出来る。
【００１９】
次に、本発明の処理が行われる画像形成装置１２について説明する。図１（Ａ）の画像形成装置１２は、プリンタや複合機など、用紙等の印刷媒体上への画像形成機能を有する装置であり、ＰＤＬデータ１００に代表される印刷データを基に、印刷媒体に可視像を形成することが出来る。
【００２０】
図１（Ｂ）は画像形成装置１２が持つ画像形成処理部１２−３の構成を図示している。なお画像形成処理部１２−３を単に画像処理部あるいは画像処理装置と称することもある。画像形成処理部１２−３は、ＣＰＵに代表される汎用処理部である汎用プロセッサ１２−３−０を持つ。この汎用プロセッサ１２−３−０は、画像形成処理部１２−３内のほかの構成要素を制御することが出来る。以下、その画像形成処理部１２−３内のほかの構成要素について述べる。
【００２１】
処理ユニット１２−３−１，処理ユニット１２−３−２，処理ユニット１２−３−３及び処理ユニット１２−３−４（以下、まとめて「処理部」あるいは「処理ユニット」と略す）はそれぞれ、汎用プロセッサ１２−３−０から制御可能なプロセッサである。処理ユニットは本例では４つであるが、１以上であれば本実施形態に係る発明を適用可能である。各処理ユニットは、パイプライン構成を有しており、また並列に命令を実行することができる。実行される命令は同一であっても同一でなくてもいずれでもよいが、画像処理の場合には、同一の命令を異なるデータに対して実行することで特に処理時間を短縮できる。各処理ユニットは、汎用プロセッサ１２−３−０の制御の下で、ＰＤＬデータ１００の解析処理や、中間データからラスタイメージデータを生成するレンダリング処理及びラスタイメージデータへの画像処理等を行うことが出来る。
【００２２】
さらに、各処理ユニットは、それぞれローカルメモリ１２−３−１−１、１２−３−２−２、１２−３−２−３、１２−３−２−４（以下まとめて「ローカルメモリと略す。）を持つ。これらのローカルメモリには、少なくともそれぞれの処理ユニットが実行可能な命令群を保存することが出来る。即ち、例えば汎用プロセッサ１２−３−０は処理ユニット１２−３−１、１２−３−２、１２−３−３、１２−３−４を制御し、ローカルメモリ１２−３−１−１、１２−３−２−２、１２−３−２−３、１２−３−２−４に保存される命令群を選択することが出来る。これによって、汎用プロセッサ１２−３−０はそれぞれの処理ユニットが実行可能な命令セットを決定することが出来る。処理中のデータをローカルメモリに格納してもよい。
【００２３】
各処理ユニットが実行可能な命令セットには分岐予測命令が含まれている。分岐予測命令は、当該分岐予測命令の後の分岐命令における分岐先の確定に先行して、分岐先についてのヒント情報を処理ユニットに与えるための命令である。逆に言えば、処理ユニットがヒント情報を獲得するための情報である。なお条件分岐命令では条件に応じて分岐する場合と分岐しない場合とがあるが、本実施形態では便宜的に分岐しない場合も含めて分岐と呼ぶ。また、条件分岐命令に続けてフェッチされる命令のアドレスを分岐アドレスあるいは分岐先と呼ぶことにする。
【００２４】
さて処理ユニットは、当該分岐命令の後、分岐予測命令で生成したヒント情報に従った分岐アドレスの命令をフェッチし、そのオペランドの読み出し或いはさらに命令の実行を行う。ここでの分岐先は実際の条件分岐命令により確定する分岐先と異なる場合もあるため、特に予測分岐先あるいは予測分岐アドレスと呼び、分岐予測に基づく命令の実行を投機的実行と呼ぶことにする。前述の通り、投機的実行では命令の実行はされず、命令の読み出しや命令とオペランドの読み出しのみの場合もあり得るが、本実施形態でいう投機的実行にはこれらの場合も含む。
【００２５】
分岐予測命令は、当該分岐命令からの分岐先のアドレス相対値と当該分岐命令のアドレスとをオペランドとしており、これらのオペランドがヒント情報として処理ユニットに与えられる。ヒント情報は処理ユニットによる分岐先の投機的実行のために用いられる情報であり、本実施形態では分岐命令に対する相対アドレスで示した予測分岐アドレスである。もちろんヒント情報としてはその他の情報もあり得る。たとえば分岐の有無を示すフラグで示したり、分岐先アドレスをその他のアドレッシングモードで示すこともできる。
【００２６】
いずれにしても、分岐予測命令で与えられたヒント情報から、処理ユニット１２−３−１，１２−３−２，１２−３−３，１２−３−４は分岐命令の分岐先が確定する前に、予測分岐先の命令を得て投機的実行しておくことができる。たとえば非特許文献２に記載されたＣｅｌｌＢ．Ｅ．では、この分岐予測命令ｈｂｒ，ｈｂｒｐ，ｈｂｒａ，ｈｂｒｒという命令が用意されている。いずれも、与えられたオペランドからヒント情報を生成するものである。
【００２７】
メモリコントローラ１２−３−５はメインメモリ１２−３−６及びＲＯＭ１２−３−９へのインターフェースである。メモリコントローラ１２−３−５はメインメモリ１２−３−６とのデータの読み込み及び書き込みを可能ならしめる。また、メモリコントローラ１２−３−５はＲＯＭ１２−３−９からのデータの読み込みを可能ならしめる。
【００２８】
本実施形態の画像形成装置では、ラスタイメージデータに対する画像処理の単位は例えば８×８画素など、一定サイズのタイルと呼ばれるブロックである。画像処理はタイルを単位として行われ、またデータの引き渡しもタイルを単位として行われる。タイル単位の画像処理は複数の処理ユニットで並列に実行される。ラスタイメージデータはタイル単位でメインメモリ１２−３−６に保存され、各処理ユニット間で転送される。限られたバスやメモリの帯域幅を効率的に利用するために、転送時にはタイルは圧縮される。たとえば各処理ユニットが異なる画像処理をタイル単位で順番に実行する場合、各処理ユニットで処理されたタイルは圧縮され、例えばメインメモリ１２−３−６を経由して次の処理を行う処理ユニットに渡される。
【００２９】
ＩＯコントローラ１２−３−８は画像形成処理部（１２−３−１、１２−３−２、１２−３−３、１２−３−４）外の装置とのインターフェースである。即ち、ＩＯコントローラ１２−３−８は画像形成処理部（１２−３−１、１２−３−２、１２−３−３、１２−３−４）外の装置とのデータの交換を可能たらしめる。
【００３０】
ローカルバス１２−３−７は、汎用プロセッサ１２−３−０、処理ユニット１２−３−１，１２−３−２，１２−３−３、１２−３−４、メモリーコントローラ１２−３−５、ＩＯコントローラ１２−３−８を接続する。即ち、ローカルバス１２−３−７はこれら接続した装置間でデータの交換を可能ならしめる。
【００３１】
以上説明した構成で画像形成処理部１２−３はＰＤＬデータ１００を元に印刷データを生成する。
【００３２】
＜画像形成処理＞
次に、画像形成装置１２の印刷媒体に可視像を形成するための、画像形成に係る処理を説明する。図３は、画像形成装置１２が行う画像形成に係る処理のフロー図である。先ず、ｓ１０でネットワークＩＦ部１２−１が情報処理装置１１からＰＤＬデータ１００（図２（Ａ）参照）を得る。ネットワークＩＦ部１２−１はＩＥＥＥ８０２．３に代表される手法で他装置と通信を行うことで、ＰＤＬデータ１００を得ることが出来る。また、このｓ１０の処理はＵＳＢＩＦ部１２−２など他の通信インターフェースや媒体を介してＰＤＬデータ１００を得てもよい。このほかにも画像形成装置１２をＩＥＥＥ１３９４ａやＲＳ−２３２Ｃ乃至ＩＥＥＥ１２８４に準拠したインターフェースを介して他装置と接続することで、ＰＤＬデータ１００を得ても本発明は実施可能である。
【００３３】
画像形成装置１２が、例えば情報処理装置１１等から得たＰＤＬデータ１００は、次に画像形成装置１２内の画像形成処理部１２−３に渡される（ｓ１２）。画像形成処理部１２−３は、このＰＤＬデータ１００をもとに印刷データ１０２（図４参照）を生成する（ｓ１４）。次にｓ１６で、画像形成処理部１２−３から印刷エンジン１２−４へ印刷データ１０２が渡される。印刷データ１０２は、図５に示すように、ラスタイメージデータ１０２−１と、印刷エンジン制御データ１０２−２とを含む。印刷エンジン１２−４は得た印刷データ１０２をもとに画像形成を行い、印刷媒体上に可視像を形成する。
【００３４】
次に図３の画像形成処理手順の中で、画像形成処理部１２−３内で行われる処理ｓ１４について図４を参照してより詳細に説明する。
【００３５】
先ず、汎用プロセッサ１２−３−０はＰＤＬデータ１００（図２（Ａ）参照）の解釈処理を行い、中間データ１０１（図２（Ｂ）参照）を生成する（ｓ１４−０）。ＰＤＬデータ１００には複数の種類がある。例えばＡｄｏｂｅＳｙｓｔｅｍｓ，ＩｎｃｏｒｐｏｒａｔｅｄのＡｄｏｂｅ（登録商標）ＰＤＦやＰｏｓｔＳｃｒｉｐｔ（登録商標）、キヤノン株式会社のＬＩＰＳ（登録商標）などが知られている。汎用プロセッサ１２−３−０は、例えばＲＯＭ１２−３−９に格納されたプログラムを実行することで、これらＰＤＬデータ１００を解釈し、ＰＤＬとは独立した共通のデータ形式である中間データ１０１を生成する。
【００３６】
図２（Ｂ）はこの中間データ１０１を説明した図である。中間データ１０１は分割された中間データ１０１−１を持つ。分割された中間データとは、画像が空間的に分割されているということであり、たとえばラスタイメージデータの主走査方向に沿った境界でいわゆるバンドに分割されている。また、中間データ１０１は印刷制御中間データ１０１−２を持つ。分割された中間データ１０１−１はさらに、イメージデータ１０１−１−１、グラフィックデータ１０１−１−２、文字データ１０１−１−３、属性情報１０１−１−４を持つ。印刷制御中間データ１０１−２は、少なくとも印刷制御データ１００−２をもとに生成されるデータである。印刷制御データ１００−２は少なくとも、画像形成すべき印刷媒体の大きさや（例えば用紙サイズと呼ばれるもの）、製本処理の方法を示す情報などを含むことが出来る。属性情報１０１−１−４は、例えばデータの種類（本例ではイメージ、グラフィック、文字）の別を領域毎に示す。
【００３７】
次に、この中間データ１０１をもとに印刷データを生成する、図４のステップｓ１４−１で実行されるレンダリング処理について図６を参照して説明する。図６の各ステップはすべて処理ユニット１２−３−１〜１２−３−４の少なくともいずれかで実行されるので、各ステップの実行主体はすべて同一の処理ユニットである。
【００３８】
まず、ｓ１４−１−１で処理ユニットが、汎用プロセッサ１２−３−０によって生成された中間データ１０１中の分割された中間データを読み込む。次に、ｓ１４−１−２で処理ユニットが、読み込んだ分割された中間データ１０１に基づき、分割されたラスタデータ１０２−１−１を生成する。次に、ｓ１４−１−３で処理ユニットが、読み込んだ分割された中間データ１０１に基づき、分割された属性データ１０２−１−２を生成する。属性データは、たとえば分割されたラスタイメージデータに含まれるオブジェクトの種類を示すデータである。本例では、少なくとも各分割されたラスタイメージデータ（これを分割領域とも呼ぶ）ごとに、イメージ属性、グラフィック属性、文字属性を、それぞれ１，２，３ビット目の独立したビットで表現される。
【００３９】
なお属性データは画素毎に有していることが望ましい。その場合には画素毎に、それがどの属性のオブジェクトを構成する画素なのかが示されることになる。この様にしておくと、ラスタイメージデータを後述する単位に分割しても、その分割単位に含まれるオブジェクトの種類を正確に示すことができる。
【００４０】
次に、ｓ１４−１−４で処理ユニットが、分割されたラスタイメージデータと分割された属性データ１０２−１−２に基づき、分割されたラスタイメージデータを圧縮する。ｓ１４−１−５では、中間データ１０１を構成する分割された中間データ１０１−１全てについてラスタイメージデータを生成したか判定する。終了していればｓ１４−１−６で印刷制御中間データ１０１−２に基づいて印刷エンジン制御データ１０２−２を生成する。以上で印刷データの生成が完了する。生成されたデータは、生成される都度メインメモリ１２−３−６に保存される。
【００４１】
＜本実施形態の手法による圧縮処理＞
次に、属性データについて図９を用いながら説明する。図９（Ａ）に示すように、印刷媒体１０００に形成される画像は、複数種類の属性を持つ場合がある。すなわち本実施形態では、図９（Ｂ）に示すように属性データ１０２−１−２は以下の三種類の属性に分類される。
１．イメージ属性１０２−１−２−１
２．グラフィック属性１０２−１−２−２
３．文字属性１０２−１−２−３。
【００４２】
この属性の少なくともいずれかを、印刷データ１０２は分割された属性データ１０２−１−２として持つ。この分割された属性データ１０２−１−２は分割されたラスタイメージデータ１０２−１−１が持つ属性を示す。より具体的には、分割された属性データ１０２−１−２は、１ビット目が１であれば分割されたラスタイメージデータ１０２−１−１がイメージ属性を持つことを示す。同様に、２ビット目が１であれば、分割されたラスタイメージデータ１０２−１−１がグラフィック属性を持つことを示す。同様に３ビット目が１であれば、分割されたラスタイメージデータ１０２−１−１が文字属性を持つことを示す。分割されたラスタイメージデータ１０２−１−１中に異なる属性を持つオブジェクトが含まれることを示すために、分割された属性データ１０２−１−２は、複数のビットが同時に１であることもある。
【００４３】
このような属性情報と対になった分割されたラスタイメージデータ１０２−１−１に対して圧縮処理ｓ１４−１−４を行う処理の詳細を図７に示す。
【００４４】
図７において、処理ユニットはｓ１４−１−４−１で、分割されたラスタイメージデータ１０２−１−１のうち圧縮処理が完了していないデータがあるかどうかを調べる。もし、この分岐条件が真であるならば、処理ユニットはｓ１４−１−４−２を実行する。もしこの分岐条件が偽であるならば、処理ユニットは本圧縮処理ｓ１４−１−４を終了する。
【００４５】
次に処理ユニットはｓ１４−１−４−２で、本圧縮処理を終了していない分割されたラスタイメージデータ１０２−１−１の一部を例えばメインメモリ１２−３−６や、他の処理ユニット、汎用プロセッサ１２−３−０等から受け取る。分割されたラスタイメージデータ１０２−１−１の一部とは、本実施形態では１０００−３や１０００−４に示すような８×８画素の小領域のデータすなわちタイルを示す。もちろんタイルが８×８画素のサイズではなく、それ以外の領域の形状やサイズであったとしても本発明を実施できる。
【００４６】
次に処理ユニットはｓ１４−１−４−３で、ステップｓ１４−１−４−２で受け取ったタイルに対応する、分割された属性データ１０２−１−２の一部を受け取る。分割された属性データ１０２−１−２の一部とは、本実施形態ではタイル中に存在するオブジェクトの属性すなわちオブジェクトの種類を示す。本実施形態ではタイルに対応する属性をタイル属性と呼ぶ場合もある。また処理対象であるものをとくに「着目」と呼ぶ。たとえば処理対象のタイルは着目タイル、処理対象のタイル属性は着目タイル属性と呼ぶことにする。
【００４７】
処理ユニットはｓ１４−１−４−４で、分割された属性データ１０２−１−２の一部すなわち着目タイル属性から、予測分岐アドレスを生成する。そしてそのアドレスとステップｓ１４−１−４−５の分岐命令のアドレスをオペランドとして分岐予測命令を実行する。こうすることで、生成された予測分岐アドレスがヒント情報として処理ユニットに与えられる。処理ユニットはヒント情報に基づいて、ｓ１４−１−４−５の分岐命令による予測分岐先をの命令をフェッチし、投機的な実行を開始する。この処理の詳細は図８で説明する。
【００４８】
次に処理ユニットはｓ１４−１−４−５で、着目タイルの特性、この場合には着目タイルに含まれる色数が二色以下か否かを判断する。もしこの分岐条件が真であるならば、処理ユニットはｓ１４−１−４−６に進む。もしこの分岐条件が偽であるならば、処理ユニットはｓ１４−１−４−７に進む。ｓ１４−１−４−６は色数が少ない画像に対する圧縮処理プログラムの先頭アドレスである。ｓ１４−１−４−７は色数が多い画像に対する圧縮処理プログラムの先頭アドレスである。処理ユニットはｓ１４−１−４−６で、分割されたラスタイメージデータ１０２−１−１の一部分に対して、色数が少ない画像に対する圧縮を行う。色数が少ない画像に対する圧縮とはたとえば、ＪＰＥＧ−ＬＳ圧縮などがあげられる。また処理ユニットでｓ１４−１−４−７で、分割されたラスタイメージデータ１０２−１−１の一部分に対して、色数が多い画像に対する圧縮を行う。色数が多い画像に対する圧縮とはたとえば、ＪＰＥＧ圧縮などがあげられる。
【００４９】
ｓ１４−１−４−６またはｓ１４−１−４−７の処理が終了すると、処理ユニットは再びｓ１４−１−４−１に進み、分割されたラスタイメージデータ１０２−１−１中に未処理データがあるか判断する。
【００５０】
ここで注意すべきは、処理ユニットは図７の処理をパイプライン方式で実行しているという点である。ｓ１４−１−４−５の条件分岐は、たとえばタイルの色数を数えた後、その色数を収めたアドレスやレジスタ等をパラメータとして、その値が２以下であるか否か判定し、判定結果に応じて分岐する条件分岐命令を処理ユニットが実行することで実現される。そのため、ｓ１４−１−４−５を実現する条件分岐命令に引き続いて、ｓ１４−１−４−６の処理の命令あるいはｓ１４−１−４−７の処理の命令が処理ユニットにフェッチされてパイプライン処理が続行されている。そのためもし実際の分岐命令後の実行アドレスと投機的に実行しているアドレスとが一致しなければ、分岐のペナルティを被ることになる。そこでステップｓ１４−１−４では、分岐先を予測し、分岐先を投機的に実行する。
【００５１】
＜分岐予測のヒント情報生成方法＞
次に、ステップｓ１４−１−４−４で行われる属性データの一部を受け取り、それに基づき分岐予測ヒントを生成する処理について、図８を用いながらより詳しく以下に述べる。
【００５２】
まず、処理ユニットで行われるｓ１４−１−４−４の処理をより詳細に説明する。本実施形態では以下のような形式の分岐予測命令で処理ユニットに分岐予測のヒント情報を与えることができる。
分岐予測命令コード  分岐命令からの分岐先のアドレス相対値，分岐命令のアドレス。
【００５３】
すなわち、分岐予測命令のオペランドとして当該命令を実行した処理ユニットに、分岐命令からの分岐先のアドレス相対値，分岐命令のアドレスという二つのパラメータが与えられる。処理ユニットはこの二つのパラメータから、分岐予測命令のあとにある、アドレスで指定された分岐命令のヒント情報、たとえば予測分岐アドレスを得ることができる。得られたヒント情報から、処理ユニットは分岐命令の分岐先が確定する前に、予測分岐先の命令を投機的実行する。
【００５４】
ここで、本実施形態では、分岐予測命令の実行に先立って、図８のステップＳ８０１により、予測分岐アドレスを求める。より具体的には、処理ユニットは、分岐命令からの相対的な予測分岐アドレスを以下のように求める。なお或る命令からの相対的なアドレス（相対アドレス）は、アドレスの順に当該命令およびオペランドの並びの直後にある命令のアドレスを０として表現する。
相対的な予測分岐アドレス＝分割された属性データの１ビット目×分岐先の相対アドレス。
【００５５】
ここで分岐先の相対アドレスとは、分岐アドレスの予測の対象となる条件分岐命令に対して、その直後にある命令ではなく、分岐する側の命令の相対アドレスである。また分割された属性データの１ビット目とは、圧縮処理の対象となっているタイルのイメージ属性を示す。すなわち、当該タイルにイメージオブジェクトが含まれていれば１、いなければ０となる。なおここで重要なことは、予測分岐アドレスは分岐命令を用いずに単純な計算式で求められていることである（上式では乗算の積）。なお上式では分岐先は０または分岐先の相対アドレスのいずれかが予測分岐アドレスとして得られる。もしも相対アドレスが０以外の分岐先が複数ある場合には、分岐先毎に項をたてればよい。すなわち、分岐アドレスを、そのアドレスに分岐する条件を示す論理値と乗算し、それを各条件の項として加算することで、予測分岐アドレスが得られる。
【００５６】
このため、分割された属性データ１０２−１−２の１ビット目が１の場合、予測分岐アドレスは、分岐先の相対アドレスとなり、逆に０の場合に予測分岐アドレスは０となる。すなわち、イメージ属性を有する場合に、この予測分岐アドレスが、ステップＳ８０２において、分岐予測命令のオペランドの一つである「分岐命令からの分岐先のアドレス相対値」として処理ユニットに引き渡される。処理ユニットは、分岐命令の完了すなわち分岐アドレスの確定を待たずに分岐命令の次に続く命令の実行、少なくともフェッチを開始する（Ｓ８３１）。ステップＳ８３１で示した手順は一つの命令の実行ではなく、ステップｓ１４−１−４−５（ステップＳ８１２）の後に引き続いて実行される命令のフェッチを行うための処理ユニット内部における手順である。
【００５７】
次にステップｓ１４−１−４−５が、ステップＳ８１１，８１２という二段階で実行される。ステップＳ８１１では処理ユニットは分割されたラスタイメージデータに含まれる色数を計算する。計算の対象は、処理対象のタイルであり、本実施形態では８×８画素の色数を計算すればよい。ステップＳ８１２では、その数えた色数が二色以下か否か判定する。二色以下であればステップｓ１４−１−４−６を、二色を越えていればステップｓ１４−１−４−７を実行する。
【００５８】
このとき、ステップＳ８０２の分岐予測命令のオペラントとした予測分岐アドレスと、ステップＳ８１２における確定した分岐アドレスとが一致していればパイプラインは滞ることがない。しかし一致していなければ、投機的実行は無駄になり、確定した分岐アドレスからあらためて実行を行うこととなる。ステップＳ８０１で予測分岐アドレスを求めた計算式とステップＳ８１２の分岐条件とを対比すると、処理対象の分割されたラスタイメージデータがイメージ属性を持つことと、処理対象のタイルの色数が二色を越えていることとの間に高い相関性があれば、確定した分岐アドレスと予測分岐アドレスとが一致する確率は高い。すなわち分岐のペナルティは小さくなる。
【００５９】
このような分岐予測を行うことは以下のような背景がある。すなわち、多くの場合、分割されたラスタイメージデータ１０２−１−１中にイメージ属性のオブジェクトがあると、二色より多い数の色が、分割されたラスタイメージデータ１０２−１−１中に存在する。逆に、イメージ属性のオブジェクトがなければ、二色以下すなわちモノクロームであることが多い。そして、モノクロームとそうでないイメージデータとで、適した圧縮手順は異なるため、モノクロームの場合とそうでない場合とで条件分岐が生じる。よって、このイメージ属性によって、後のｓ１４−１−４−５の条件分岐を予測することができる。このような理由のために図８の処理が行われている。
【００６０】
なお、パイプラインが非常に深いと、ステップｓ１４−１−４−４で分岐先予測を行っているときにステップｓ１４−１−４−５の以降の命令がフェッチされ、ｓ１４−１−４−６あるいはｓ１４−１−４−７の処理の実行が開始されていることもあるかもしれない。この対策のために、分岐予測命令が完了する前に対象となる分岐命令直後の命令がフェッチされないよう、命令の間隔を予め十分離しておく必要がある。
【００６１】
上述したように本実施形態にかかる発明によると、画像形成処理特有の属性情報を用いることで、分岐予測のヒント情報を処理ユニットに与えることができる。これによって、画像形成処理にかかる画像圧縮処理中の分岐命令による速度低下を抑制し、処理速度を速くすることができる。
【００６２】
本発明はパイプライン処理に限らず、たとえば命令を先読みする場合など、分岐命令による分岐先の確定前に、分岐後の命令のフェッチをするプロセッサに対して適用することができる。
【００６３】
また分岐後に実行される処理も圧縮とは限らず、属性に応じた分岐先が予測可能な処理について適用することができる。
【００６４】
また分岐予測の基準も画像データの属性とは限らず、他の性質を利用することも可能である。
【００６５】
［第二実施形態］
第一実施形態では分岐命令とそれに続く画像圧縮処理に対する分岐予測命令の実施例を示した。しかし本発明は分岐命令とそれに続く画像圧縮処理のみに適用されるものではない。本実施形態では、複数の処理ユニットにより並列的に投機的実行を行う場合の例を示す。以下に図表を用いながら別の実施形態を説明する。なお、上記圧縮処理以外は第一実施形態の処理にしたがい実施可能であるため記載を省略する。
【００６６】
＜本実施形態の手法による圧縮処理＞
第一実施形態と同様に、図９（Ａ）が示すように紙に代表される媒体１０００には複数種類の属性を持った画像が形成される。すなわち本実施形態では、図９（Ｂ）が示すように属性情報は以下の三種類の属性に分類される。
１．イメージ属性１０２−１−２−１
２．グラフィック属性１０２−１−２−２
３．文字属性１０２−１−２−３。
【００６７】
このような属性情報と対になった分割されたラスタイメージデータ１０２−１−１に対して圧縮処理ｓ１４−１−４"を行う処理を図１１を参照しながら以下に説明する。本実施形態では、第一実施形態と相違する点について説明し、共通の事項については説明を省略する。本実施形態では装置の構成は第一実施形態と共通であり、処理も図６は共通である。ただし図６のステップｓ１４−１−４が本実施形態では図１１のｓ１４−１−４"に置き換えられる。
【００６８】
まず、処理ユニット１２−３−１，１２−３−２，１２−３−３，１２−３−４（以下単に処理ユニットと呼ぶ。）は、ｓ１４−１−４"−１で、分割されたラスタイメージデータ１０２−１−１のうち圧縮処理をしていないデータがあるかどうかを調べる。もし、この分岐条件が真であるならば、処理ユニットはｓ１４−１−４"−２に進む。もしこの分岐条件が偽であるならば、処理ユニットは本圧縮処理ｓ１４−１−４を終了する。
【００６９】
次に処理ユニットはｓ１４−１−４"−２で、本圧縮処理を終了していない分割されたラスタイメージデータ１０２−１−１の一部を受け取る。分割されたラスタイメージデータ１０２−１−１の一部とは、本実施例では１０００−３や１０００−４に示すような８×８画素の小領域のデータすなわちタイルを示す。もちろん８×８画素のサイズではなく、それ以外の領域の形状やサイズであったとしても、本発明を実施できることはいうまでもない。
【００７０】
次に処理ユニットはｓ１４−１−４"−３で、同様に本圧縮処理を終了していない分割されたラスタイメージデータ１０２−１−１の一部に対応する、分割された属性データ１０２−１−２の一部を受け取る。分割された属性データ１０２−１−２の一部とは、本実施形態では１０００−３や１０００−４に示すような８×８画素の小領域（タイル）の中に存在する属性の種類を示す。もちろん対象の分割されたラスタイメージデータ１０２−１−１が８×８画素のサイズではなく、それ以外の領域の形状やサイズであったとしても、本発明を実施できることは言うまでもない。
【００７１】
次に処理ユニットはｓ１４−１−４"−４で、分割された属性データ１０２−１−２の一部に基づいて、後に続く圧縮処理を投機的に実行する。ここでいう投機的実行は、パイプライン処理による先読み的な実行を指すのではなく、複数の処理ユニットによる並列的に実行を指す。すなわち、色数に応じた圧縮処理を、図６の手順を実行する処理ユニットとは違う処理ユニットにより実行させる。ただしこの場合、投機的実行に係る処理では、現在進行している処理の確定した結果を用いることはできない。そのため、投機的実行の対象となる処理は、現在進行している処理の確定した結果を必要としない処理となろう。
【００７２】
次に処理ユニットはｓ１４−１−４"−５で、分割されたラスタイメージデータ１０２−１−１の特性、すなわち含まれる色数が二色以下かそれ以上かを判断する。もしこの分岐条件が真であるならば、処理ユニットはｓ１４−１−４"−６に進む。もしこの分岐条件が偽であるならば、処理ユニットはｓ１４−１−４"−７に進む。ｓ１４−１−４"−６は色数が少ない画像データのための圧縮処理プログラムであり、ｓ１４−１−４"−７は色数が多い画像データのための圧縮処理プログラムである。
【００７３】
次に処理ユニットはｓ１４−１−４"−６で、分割されたラスタイメージデータ１０２−１−１の一部分に対して、色数が少ない画像に対する圧縮を行う。色数が少ない画像に対する圧縮とはたとえば、ＪＰＥＧ−ＬＳ圧縮などがあげられる。また処理ユニットはｓ１４−１−４"−７では、分割されたラスタイメージデータ１０２−１−１の一部分に対して、色数が多い画像に対する圧縮を行う。色数が多い画像に対する圧縮とはたとえば、ＪＰＥＧ圧縮などがあげられる。
【００７４】
ステップｓ１４−１−４−６及び、ステップｓ１４−１−４"−７の処理が終了すると、処理ユニット（１２−３−１，１２−３−２，１２−３−３及び１２−３−４）は再びｓ１４−１−４−１に進み、分割されたラスタイメージデータ１０２−１−１中に未処理データがあるか判断する。なおステップｓ１４−１−４−６及び、ステップｓ１４−１−４"−７の処理は、単純な圧縮処理ではなく、投機的実行の結果に応じて処理は変更される。以下、その詳細を説明する。
【００７５】
＜投機的実行の処理方法＞
次に、ｓ１４−１−４−４からｓ１４−１−４"−７で行われる、属性データの一部を受け取り、それに基づき分岐予測を行って分岐先処理の投機的実行を行う処理について、図１２を用いながらより詳しく以下に述べる。
【００７６】
まず、処理ユニットで行われるｓ１４−１−４"−４の処理をより詳細に説明する。第一実施形態と同様に、属性データの一部を基に、分岐命令のあとに行われる処理すなわち予測分岐アドレスは予測することができる。処理ユニットはこの予測をもとにして、後に続く圧縮処理を他の処理ユニット（第二の処理ユニット）により並列に実行させる（Ｓ１２０１）。すなわち、第二の処理ユニットは、属性データの一部がイメージ属性を示していれば、色数が多い画像に対する圧縮を投機的に実行し、属性データの一部がイメージ属性を示していなければ、色数が少ない画像に対する圧縮を投機的に実行する（Ｓ１２１１）。このとき予測された圧縮方式はどちらであるか記憶される。
【００７７】
このような計算をするには以下のような背景がある。すなわち、多くの場合、分割されたラスタイメージデータ１０２−１−１中にイメージ属性が示す描画があると、二色以上の色がその分割されたラスタイメージデータ１０２−１−１中に存在する。よって、このイメージ属性によって、後のｓ１４−１−４−５の分岐条件を予測することができる。
また、上述したように、画像形成処理装置１２−３は複数個の処理ユニット１２−３−１，１２−３−２，１２−３−３，１２−３−４を持つ（図１（Ｂ））。すなわち、複数持つ処理ユニット１２−３−１，１２−３−２，１２−３−３，１２−３−４を使い投機的に並行処理を行うことで、後に続く分岐命令の確定を待たずに、処理を終えることができる。
【００７８】
ステップｓ１２０２，１２０３は図８のステップ８１１，８１２と同様の処理である。
【００７９】
ステップＳ１２０４では、ステップＳ１２１１で開始した投機的実行の結果があるか判定する。ここでいう投機的実行の結果とは、該当する方法で圧縮された画像データである。すなわち、ステップＳ１２０４では二色以下の画像データに対する処理が行われるので、ステップＳ１２１１で二色以下の画像データに対する圧縮手順で圧縮された画像データがあれば判定結果は肯定である。もし圧縮画像データがあっても二色より色数が多い画像データに対する圧縮手順で圧縮されているなら投機的実行の結果はないものと判定される。この判定はステップＳ１２０１で記憶された圧縮方式に基づいて実行できる。投機的実行の結果がないと判定された場合、あらためて該当する手順で圧縮を行う。また「結果がある」ことの判定は、たとえば投機的実行に係る処理の完了時に、当該処理が完了したことを示すフラグをセットすることなどで実現できる。もちろん処理結果であるデータの保存先も予め定めておくか、あるいは引き渡される。
【００８０】
上述したように本発明によると、画像形成処理特有の属性情報を用いることで、分岐命令に続く圧縮処理を投機的に実行することができる。これによって、画像形成処理にかかる画像圧縮処理中の分岐命令による速度低下を抑制し、処理速度を速くすることができる。
【００８１】
ステップＳ１２０６では、ステップＳ１２１１で開始した投機的実行の結果があるか判定する。ここでいう投機的実行の結果とは、該当する方法で圧縮された画像データである。すなわち、ステップＳ１２０６では二色より色数の多い画像データに対する処理が行われるので、ステップＳ１２１１で二色より色数の多い画像データに対する圧縮手順で圧縮された画像データがあれば判定結果は肯定である。もし圧縮画像データがあっても二色以下の画像データに対する圧縮手順で圧縮されているなら投機的実行の結果はないものと判定される。この判定はステップＳ１２０１で記憶された圧縮方式に基づいて実行できる。投機的実行の結果がないと判定された場合、あらためて該当する手順で圧縮を行う。
【００８２】
上述したように本発明によると、画像形成処理特有の属性情報を用いることで、分岐命令に続く圧縮処理を投機的に実行することができる。これによって、画像形成処理にかかる画像圧縮処理中の分岐命令による速度低下を抑制し、処理速度を速くすることができる。
【００８３】
［第三実施形態］
第一実施形態及び第二実施形態では、８×８ピクセル単位での画像圧縮処理に対する分岐予測処理の実施例を示した。しかし本発明はこの一定のピクセル単位にのみ適用されるものではない。上述してきた実施例とは別のピクセル単位の圧縮処理にかかる実施例を以下に図表を用いながら説明する。
【００８４】
なお、上記圧縮処理以外は第一実施形態及び第二実施形態の処理にしたがい実施可能であるため記載を省略する。
【００８５】
＜本実施形態の手法による圧縮処理＞
まず分割されたラスタイメージデータ１０２−１−１から２×２画素のブロックを抽出し、そのブロック単位でデータの圧縮を行う。
【００８６】
処理の説明の前に、２×２の４画素データ中に占める色数に応じてその組み合わせの場合の数を考える。画素数が４画素なので、そこに占める色数は最大４色になり、ブロック内でたかだか１〜４色の組み合わせしか存在しない。それら４色のパターンのとりうる組み合わせの場合の数を図１３を使って説明する。
【００８７】
まずブロック内が１色の場合、４画素が同色で構成されている事になるので、その組み合わせは１通りである。
【００８８】
次にブロック内が２色の場合を考える。２色が４画素内へレイアウトされる場合の数は、左上の画素を第１色、他方を第２色として考えると、左上以外残りの３画素へ第１色もしくは第２色が入るので、４画素同色の場合を除くと、全部で７通りの組み合わせが考えられる。
【００８９】
次にブロック内が３色の場合を考える。３色が４画素内へレイアウトされる場合の数は、３色のうち１色だけ２度使われる場合の数と言い換える事が可能で、４画素の座標のうち、２画素が同じ色になる場合の数を求めればよい。つまり３色の場合の数は、４つの座標から２つの座標を取る組み合わせとなり、全部で６通りとなる。
【００９０】
最後にブロック内が４色の場合は１色の場合と同様１パターンしか存在しない。
【００９１】
これら１〜４色すべての場合の数を合計すると全部で１５通りのパターンが考えられる。これらすべてのパターンを識別するためにフラグを付与する事を考えると、データ量としては４ビット必要となる。図示すると図１４のようになり、以降このフラグをパターンフラグと呼ぶ。
【００９２】
上述のように２×２画素の取りうる組み合わせを踏まえて、処理ユニット１２−３−１，１２−３−２，１２−３−３，１２−３−４にて行われる処理フローを図１５を用いて説明する。入力としては、例えばＲＧＢそれぞれ８ビットの２５６階調を持っており、またデータとしては８ビットデータの点順次で１画素あたり２４ビット画像として説明を行う。
【００９３】
まず、上述した実施形態同様に、まず、処理ユニットはｓ１４−１−４"'−１で、分割されたラスタイメージデータ１０２−１−１のうち圧縮処理をしていないデータがあるかどうかを調べる。もし、この分岐条件が真であるならば、処理ユニットはｓ１４−１−４"'−２に進む。もしこの分岐条件が偽であるならば、処理ユニット（１２−３−１，１２−３−２，１２−３−３，及び１２−３−４）は本圧縮処理ｓ１４−１−４を終了する。
【００９４】
次に処理ユニットはｓ１４−１−４"'−２で、本圧縮処理を終了していない分割されたラスタイメージデータ１０２−１−１の一部を受け取る。分割されたラスタイメージデータ１０２−１−１の一部とは、上述した２×２画素の小領域のデータを示す。
【００９５】
次に処理ユニットはｓ１４−１−４"'−３で、同様に本圧縮処理を終了していない分割されたラスタイメージデータ１０２−１−１の一部に対応する、分割された属性データ１０２−１−２の一部を受け取る。
【００９６】
次に処理ユニットはｓ１４−１−４"'−４で、２×２ブロック内全ての２画素の組み合わせに対して２４ビットのコンペアを取る。すなわちビットごとに比較する。このコンペアを取った結果、全ビット一致していた場合１を、不一致の場合０を出力する。２×２画素内の左上から右上、左下、右下の順に画素に１、２、３、４と番号を付すると、２画素の組は、１−２、１−３、１−４、２−３、２−４、３−４の全部で６通りある。そのため６回コンペアを取る必要があり、結果は６ビット出力される。例えば全画素同色の場合には、全てのコンペア結果が１を出力し、逆に４画素全てバラバラの画素値を持っている場合には、全てのコンペア結果が０を出力する。前述の通り、４画素で色の一致から出現しうるパターン数は１５通りなので、その６ビットのコンペア結果を４ビットのパターンフラグへ変換することが可能であり、その変換を行う（ｓ１４−１−４"'−５）。
【００９７】
次に処理ユニットはｓ１４−１−４"'−６で、前記４ビットのパターンフラグへ変換ののち、４画素内で出現した色数および色データを抽出する。パターンフラグから、左上を第１色とした場合の第２色以降がどの位置にあるか求める事が出来る。
【００９８】
次に処理ユニットはｓ１４−１−４"'−７で、分割された属性データ１０２−１−２の一部から、分岐予測命令の２つのオペランドを生成し、分岐予測命令を実行して処理ユニットに対してヒント情報を与える。オペランドについては＜投機的実行の処理方法＞で説明する。続く処理については、図１４も合わせて参照しながら説明を行う。
【００９９】
図１４に示すように、例えば４画素内が１色で構成されていることが確定した場合には、２色目以降は存在しない。そこで着目領域の特性すなわち４画素内が１色で構成されているか判定し（ｓ１４−１−４"'−８）、そうであればパターンフラグ４ビットと１色目の２４ビットを出力する（ｓ１４−１−４"'−９）。また４画素内が２色で構成されていることが確定した場合（ｓ１４−１−４"'−１０）には、その２色目の座標をパターンフラグより算出し、パターンフラグ４ビットと２色分の画素値４８ビットを出力する（ｓ１４−１−４"'−１１）。３色、４色の場合も同様である（ｓ１４−１−４"'−１２，ｓ１４−１−４"'−１３及びｓ１４−１−４"'−１４）。このときブロック内の座標（左上から右上、左下、右下の順に１、２、３、４）順にこれまで出現していなかった色データを記憶する。ステップｓ１４−１−４"'−９，１４−１−４"'−１１，１４−１−４"'−１３，１４−１−４"'−１４はそれぞれの特性に適した画像圧縮プログラムということができる。
【０１００】
このように、２×２画素のブロック内の４色９６ビットの入力データを４ビットのパターンフラグとそこに存在する色数だけ画素値を出力することで、比較的簡単な処理で出力データ量を削減することが可能になる。また色の配置を示すパターンフラグを参照することで、そのブロック内の色数を特定することが可能になる。
【０１０１】
なお、上記条件分岐命令（ｓ１４−１−４"'−８，ｓ１４−１−４"'−１０及びｓ１４−１−４"'−１２）では先のｓ１４−１−４−７で生成した分岐予測のヒント情報に基づき、条件分岐が実行される。すなわち、ｓ１４−１−４−７で生成された分岐予測のヒント情報が示すアドレス値から投機的な実行を開始する。これは第一の実施形態と同様である。
【０１０２】
ｓ１４−１−４−９、乃至ｓ１４−１−４−１１、乃至ｓ１４−１−４"'−１３乃至ｓ１４−１−４"'−１４のいずれかの処理が終了すると、処理ユニットは再びｓ１４−１−４"'−１に進み、分割されたラスタイメージデータ１０２−１−１中に未処理データがあるか判断する。
【０１０３】
このように上記処理を全ての分割されたラスタイメージデータ１０２−１−１に対して行うことで、印刷データ１０２の圧縮が完了する。
【０１０４】
＜投機的実行の処理方法＞
次に、上記ｓ１４−１−４"'−７で行われる属性データの一部を受け取り、それに基づき分岐予測のヒント情報を生成する処理について、詳しく以下に述べる。第一実施形態と同様に、分割された属性データ１０２−１−２は以下の属性を持つことができる。
１．イメージ属性１０２−１−２−１
２．グラフィック属性１０２−１−２−２
３．文字属性１０２−１−２−３。
【０１０５】
これら属性の情報から、処理ユニットは、以下に続く分岐命令（ｓ１４−１−４"'−８，ｓ１４−１−４"'−１０及びｓ１４−１−４"'−１２）の後に続くパターンフラグにかかる処理（ｓ１４−１−４−９、ｓ１４−１−４−１１、ｓ１４−１−４"'−１３、ｓ１４−１−４"'−１４）のいずれの処理を実行すべきか予測することができる。すなわち本実施形態では、以下のように分岐予測命令を実行する。
【０１０６】
注目した分割されたラスタイメージデータの２×２の領域に、イメージ属性１０１−１−２−１を含まないのであれば、ｓ１４−１−４"'−８の処理へのアドレス値を分岐予測として処理ユニットに与える。すなわち、処理対象の２×２領域にイメージ属性が含まれなければ、分岐予測命令のオペランドである分岐命令のアドレスとしてステップｓ１４−１−４"'−８の条件分岐命令のアドレスを設定する。また、分岐予測命令のオペランドである予測分岐アドレスとして、ｓ１４−１−４"'−８の条件分岐命令に対するステップｓ１４−１−４"'−９の命令の相対アドレスを設定する。これらオペランドで分岐予測命令を実行する。
【０１０７】
なお予測分岐アドレスの決定は条件分岐命令を用いずに単純な算術或いは論理演算で求めることが望ましい。さもなくば予測分岐アドレスを求めるために条件分岐命令が実行されてしまうためである。そこで上記処理は、単純な演算で実現される。たとえば「イメージ属性１０１−１−２−１を含まない」ことは、論理的には属性データの１ビット目の反転値により示される。そこで「処理対象の２×２領域にイメージ属性が含まれなければ、分岐予測命令のオペランドである予測分岐アドレスとして、ｓ１４−１−４"'−８の条件分岐命令に対するステップｓ１４−１−４"'−９の命令の相対アドレスを設定する」ことは以下の式で実現される。
予測分岐アドレス＝（イメージ属性１０１−１−２−１の１ビット目の反転値）×（ｓ１４−１−４"'−９の命令のアドレス値）。
【０１０８】
以上は、文字属性１０１−１−２−３乃至グラフィック属性１０１−１−２−２のみを持つ領域の多くは一色のみ持つという画像形成処理特有の特徴に依存している。
【０１０９】
上述したように本発明によると、画像形成処理特有の属性情報を用いることで、分岐命令に続く圧縮処理のパターンフラグ決定を投機的に実行することができる。これによって、画像形成処理にかかる画像圧縮処理中の分岐命令による速度低下を抑制し、処理速度を速くすることができる。
【０１１０】
なおイメージ属性も含めて、含まれるオブジェクト属性が１種類の場合には、４画素が同一の色である可能性が高い。そこで、注目した分割されたラスタイメージデータの２×２の領域に対応する属性が、１ビットのみ１である場合には、上述したようにｓ１４−１−４"'−９を予測分岐先として分岐予測命令を実行しても良い。
【０１１１】
以上のように、本実施形態による圧縮手順に対しても、分岐予測がヒットする率を高め、処理効率を高めることができる。
【０１１２】
［第四実施形態］
第一実施形態、第二実施形態、及び第三実施形態では、分岐命令とそれに続く画像圧縮処理に対する分岐予測命令、及び投機的実行処理による実施例を示した。しかし本発明は分岐命令とそれに続く画像圧縮処理のみに適用されるものではない。
【０１１３】
より具体的には、分岐命令とそれに続く画像圧縮処理だけではなく、分岐命令とそれに続く画像変換処理においても本発明を実施できる。図１０は、本発明に基づき、分岐命令とそれに続く画像変換処理における実施形態を示している。
【０１１４】
この実施形態では、第一実施形態同様に、まず、処理ユニット１２−３−１，１２−３−２，１２−３−３，１２−３−４（以下単に処理ユニットと呼ぶ）はｓ１４−１−４'−１で、分割されたラスタイメージデータ１０２−１−１のうち変換処理をしていないデータがあるかどうかを調べる。もし、この分岐条件が真であるならば、処理ユニットはｓ１４−１−４'−２に進む。もしこの分岐条件が偽であるならば、処理ユニットは本変換処理ｓ１４−１−４'を終了する。
【０１１５】
次に処理ユニットはｓ１４−１−４'−２で、本変換処理を終了していない分割されたラスタイメージデータ１０２−１−１の一部を受け取る。分割されたラスタイメージデータ１０２−１−１の一部とは、本実施形態では１０００−３や１０００−４に示すような１画素のデータを示す。もちろん１画素のサイズではなく、それ以外の領域の形状やサイズであったとしても、本発明を実施できることは言うまでもない。
【０１１６】
次に処理ユニットはｓ１４−１−４'−３で、同様に本変換処理を終了していない分割されたラスタイメージデータ１０２−１−１の一部に対応する、分割された属性データ１０２−１−２の一部を受け取る。
【０１１７】
次に処理ユニットはｓ１４−１−４'−４で、分割された属性データ１０２−１−２の一部から、後に続く分岐命令のヒント情報を処理ユニットに与える。すなわち分岐予測命令を実行する。ここで分岐予測命令のオペランドは次のように決定される。まず処理対象の画素の属性を判定し、文字属性であれば、分岐命令アドレスとしてｓ１４−１−４'−５の分岐命令のアドレスを、予測分岐アドレスとしてｓ１４−１−４'−６の命令の相対アドレスをオペランドとして分岐予測命令を実行する。また処理対象の画素の属性に応じて、グラフィック属性であれば、分岐命令アドレスとしてｓ１４−１−４'−５の分岐命令のアドレスを、予測分岐アドレスとしてｓ１４−１−４'−７の命令の相対アドレスをオペランドとして分岐予測命令を実行する。さらにもうひとつ、分岐命令アドレスとしてｓ１４−１−４'−７の分岐命令のアドレスを、予測分岐アドレスとしてｓ１４−１−４'−８の命令の相対アドレスをオペランドとした分岐予測命令も実行する。また処理対象の画素の属性に応じて、イメージ属性であれば、分岐命令アドレスとしてｓ１４−１−４'−５の分岐命令のアドレスを、予測分岐アドレスとしてｓ１４−１−４'−７の命令の相対アドレスをオペランドとして分岐予測命令を実行する。さらにもうひとつ、分岐命令アドレスとしてｓ１４−１−４'−７の分岐命令のアドレスを、予測分岐アドレスとしてｓ１４−１−４'−９の命令の相対アドレスをオペランドとした分岐予測命令も実行する。
【０１１８】
なお予測分岐アドレスの決定は条件分岐命令を用いずに単純な算術演算や論理演算で求めることが望ましい。さもなくば予測分岐アドレスを求めるために条件分岐命令が実行されてしまうためである。そこで上記処理は、単純な演算処理で実現される。たとえば「文字属性であること」ことは、論理的には属性データの３ビット目の値により示される。そこで「文字属性であれば、分岐命令アドレスとしてｓ１４−１−４'−５の分岐命令のアドレスを、予測分岐アドレスとしてｓ１４−１−４'−６の命令の相対アドレスをオペランドと」することは以下の式で実現される。
ｓ１４−１−４'−５の分岐命令の予測分岐アドレス＝（属性データ１０２−１−２の３ビット目の値）×（ｓ１４−１−４'−６の命令のアドレス値）。
ｓ１４−１−４'−７の分岐命令の予測分岐アドレス＝（属性データ１０２−１−２の２ビット目の値）×（ｓ１４−１−４'−８の命令のアドレス値）。
【０１１９】
ただし、ｓ１４−１−４'−５の分岐命令に対する相対アドレス０の命令はｓ１４−１−４'−７であり、１４−１−４'−７の分岐命令に対する相対アドレス０の命令はｓ１４−１−４'−９であるものとする。
【０１２０】
この後、実際にｓ１４−１−４'−５を実行して処理対象の領域の特性を判定する。すなわちその属性が文字属性か判定する。文字属性であれば分岐アドレスはｓ１４−１−４'−６に確定し、そこを先頭アドレスとする画像処理プログラムを実行する。
【０１２１】
文字属性でなければｓ１４−１−４'−７を実行して処理対象の領域の属性がグラフィック属性か判定する。グラフィック属性であれば分岐アドレスはｓ１４−１−４'−８に確定し、そこを先頭アドレスとする画像処理プログラムを実行する。一方グラフィック属性でなければ分岐アドレスはｓ１４−１−４'−９に確定し、そこを先頭アドレスとする画像処理プログラムを実行する。
【０１２２】
なおｓ１４−１−４'−６の処理の例としてはたとえばエッジの尖鋭化処理、ｓ１４−１−４'−８の処理の例としてはたとえば輪郭の平滑化処理、ｓ１４−１−４'−９の処理の例としてはたとえば濃度の平坦化処理などがあろう。
【０１２３】
以上のように、本実施形態によれば、圧縮に限らず、画像処理一般についても、分岐予測殿精度を高めて処理効率を向上させることができる。
【０１２４】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2011197951.tif 000003
【図２】
2011197951.tif 000004
【図３】
2011197951.tif 000005
【図４】
2011197951.tif 000006
【図５】
2011197951.tif 000007
【図６】
2011197951.tif 000008
【図７】
2011197951.tif 000009
【図８】
2011197951.tif 000010
【図１０】
2011197951.tif 000011
【図１１】
2011197951.tif 000012
【図１２】
2011197951.tif 000013
【図１３】
2011197951.tif 000014
【図１４】
2011197951.tif 000015
【図１５】
2011197951.tif 000016
【図９】
2011197951.tif 000017