(57)【要約】【課題】  本発明は、画像処理のための方法及び装置、特に、画像をセグメント化する方法及び装置を提供することを目的とする。【解決手段】  一実施形態に従った方法は、実行時にビットマップを作成する描画コマンドシーケンスに関し、それに対応する解析を実行する段階（101）、及びこの描画コマンドシーケンスに対応する解析に基づいて、一組の画像セグメントを生成する段階（102）を有する。【選択図】図１
2008059590.tif 000002
【特許請求の範囲】
【請求項１】
実行時にビットマップを作成する描画コマンドシーケンスに対応する解析を実行する段階；及び
描画コマンドシーケンスに対応する解析に基づいて、一組の画像セグメントを生成する段階；
を有する方法。
【請求項２】
複数の画像セグメントの各々に対して符号化方法を選択する段階；及び
一組の符号化された画像セグメントを作成するために、選択された符号化方法を用いて複数の画像セグメントの各々を符号化する段階；
を更に有する請求項１に記載の方法。
【請求項３】
符号化方法を選択する段階は復号化資源の利用可能性に基づく、請求項２に記載の方法。
【請求項４】
符号化方法を選択する段階は達成可能な圧縮量に基づく、請求項２に記載の方法。
【請求項５】
描画コマンドシーケンスに対応する解析を実行する段階は：
描画コマンドシーケンスの各描画コマンドが順々に検査されるように、描画コマンドの各々をグループに分類する段階；並びに
描画コマンド毎に、
該描画コマンドがシーケンス内の直前の描画コマンドと同一グループにある場合には、該描画コマンドの結果を、存在している第１の図面の電子版に付加する段階、及び
該描画コマンドがシーケンス内の直前の描画コマンドと同一グループにない場合には、第１の図面を保存し、且つ該描画コマンドの結果を用いて第２の図面の電子版を作成する段階であり、第１及び第２の図面の電子版が画像セグメントである、作成段階；
を有する、請求項１に記載の方法。
【請求項６】
描画コマンドシーケンスに対応する解析を実行する段階は：
描画コマンドシーケンスの各描画コマンドが順々に検査されるように、描画コマンドの各々をグループに分類する段階；
１つ以上の描画コマンドから成る第１のグループ用の第１のビットマップを生成する段階；
第１のグループ内の全ての描画コマンドが解析されたとき、第１のビットマップを保存する段階；及び
１つ以上の描画コマンドから成る第２のグループ用の第２のビットマップを生成する段階；
を有する、請求項１に記載の方法。
【請求項７】
第２のグループ内の全ての描画コマンドが解析されたとき、第２のビットマップを保存する段階；
を更に有する請求項６に記載の方法。
【請求項８】
第１及び第２のビットマップを有する複合画像ファイルを書き込む段階；
を更に有する請求項７に記載の方法。
【請求項９】
描画コマンドシーケンスに対応する解析を実行する段階は：
組み合わさって画像を形成する複数の領域の各々への各描画コマンドの幾何学的な影響を決定する段階であり、複数の画像セグメントの各々は前記複数の領域の内の１つの画像データに相当する、決定段階；及び
複数の画像セグメントの各々に対して、それが関連する領域の画像データに基づいて符号化法を選択する段階；
を有する、請求項１に記載の方法。
【請求項１０】
各描画コマンドの前記幾何学的な影響は、該描画コマンドに関連する色を含む、請求項９に記載の方法。
【請求項１１】
複数の画像セグメントの各々に対して、それが関連する領域の画像データに基づいて符号化法を選択する段階は、全ての描画コマンドの前記複数の領域に対する幾何学的な影響が決定された後の、該関連する領域内の色の数に基づく、請求項９に記載の方法。
【請求項１２】
描画コマンドシーケンスに対応する解析を実行する段階は：
描画コマンド毎に、
該描画コマンドの結果によって生成される色のリストを決定する段階、
該描画コマンドの結果によって交わられるタイルのリストを決定する段階、
該描画コマンドの結果によって交わられるタイルのリスト内の各タイルにタグ付けするように前記色のリストを付加する段階、及び
該描画コマンドの結果によって交わられるタイルのリスト内のタイルに結果ビットを複製する段階；並びに
複数の画像セグメントの各々に対して、それが関連する領域の画像データに基づいて符号化法を選択する段階；
を有する、請求項１に記載の方法。
【請求項１３】
描画コマンドシーケンスに対応する解析を実行する段階は：
描画コマンド毎に、
該描画コマンドによって生成される色のリストを決定する段階、
該描画コマンドの実行結果を包囲する境界ボックスを決定する段階、
該描画コマンドに関連するタイルビットマップを作成する段階、及び
前記色のリストを用いてタイルビットマップをタグ付けすることを含めて、該描画コマンドの実行により得られるビットを、該描画コマンドによって影響を受けるビットマップに複製する段階；
を有する、請求項１に記載の方法。
【請求項１４】
前記ビットマップが既存タイルの境界と交わるかどうかを決定する段階；及び
前記ビットマップが既存タイルの境界と交わる場合に、既存タイル群を重なり合わないサブタイル群にセグメント化する段階；
を更に有する請求項１３に記載の方法。
【請求項１５】
各タイルビットマップをタグ内の色の数に基づいて符号化する段階；
タイルビットマップ群に対応する符号化されたデータを有する複合画像ファイルを書き込む段階；
を更に有する請求項１３に記載の方法。
【請求項１６】
命令を格納する１つ以上のコンピュータ可読媒体を有する装置であって、該命令は、システムによる実行時にシステムに：
実行時にビットマップを作成する描画コマンドシーケンスに対応する解析を実行する段階；及び
描画コマンドシーケンスに対応する解析に基づいて、一組の画像セグメントを生成する段階；
を有する方法を実行させる、装置。
【請求項１７】
前記方法は：
複数の画像セグメントの各々に対して符号化方法を選択する段階；及び
一組の符号化された画像セグメントを作成するために、選択された符号化方法を用いて複数の画像セグメントの各々を符号化する段階；
を更に有する、請求項１６に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像のセグメント化の分野に関し、より具体的には、本発明は描画コマンドを別の表現に変換することに関する。
【背景技術】
【０００２】
標準的な文書レンダリングシステムは、しばしば、目標とする表現でマークがどのように配置されるべきかを指定するためにページ記述言語を用いている。プリンタの場合の目標とする表現は、紙面にトナーを置くためにマーキングエンジンによって使用され得るビットマップである。プロッタの場合の目標とする表現は、紙面にインクを載せるロボットペンへの一連の命令である。ＰＤＦレンダラーの場合、ページ記述言語は、後に他のレンダリングプログラムによって使用可能な一連の描画コマンドに翻訳される。
【０００３】
このようなページ記述言語は大きくは、ラスタと描画システムという２つのカテゴリーに分類される。ラスタはこれら２つの内で遙かに単純で、行と列とに配列される一組の画素値から成り、画素値は色モデルに従ってページ上に書き込まれる。描画システムはより複雑であり、例えば直線や曲線の描画、色の充填、座標変換、及びラスタの配置など、様々な種類の画像化処理を可能にする。従って、描画システムは一般に、ラスタページ記述の上位集合である。しかしながら、描画システムはまた、解像度及びサイズが選定されるとラスタ記述に変換されることが可能である。
【０００４】
描画システムは、同一の画素を異なる値で上書きする描画コマンドを含むことがある。このような相反するコマンドを最終的なページ画像ラスタにおいて解消するために様々なアルゴリズムが選択されることができる。これらのモデルの内で最も一般的且つ直観的なものは、最も近くに出された描画コマンドの結果を適当な画素値として使用する所謂“ペインターズ（painter’s）アルゴリズム”である。例えば、同一の画像内に３本の直線が描画される場合、直線が交差する位置にある画素に対して画素値が何になるかを、最も新しく引かれた直線の色が指示することになる。僅かに拡張されたペインターズアルゴリズムは、コマンドによって描画される各画素に、画素データに関する透明度を指し示す“アルファ”値を割り当てることを含んでいる。50％のアルファ値は以前の画素値と新たな画素値とを用い、それらの数学的な混合によって構成される色を作り出す。
【０００５】
ＪＰＭは、ラスタ成分と非常に単純な描画システムとの双方を含む画像フォーマットである。ＪＰＭ描画システムは、配置、拡大縮小、及び要素のマスキングを可能にする。これは、上述の描画システムのように、配置される画像のアルファ混合を含んでいる。
【０００６】
混合ラスタコンテンツ文書の画像セグメント化の分野にはかなりの先行技術が存在している。これらは走査画像から機能するセグメントに限られている。描画コマンドの複雑なリストを与えられた平面的なマップを構築することが特許文献１にて開示されている。しかしながら、従来の技術は複雑な領域を平坦化することによってラスタライザを高速化するために用いられている。
【特許文献１】米国特許出願公開第２００５／０１１６９６３号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、画像処理のための方法及び装置、特に、画像をセグメント化する方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一実施形態に係る方法は、実行時にビットマップを作成する描画コマンドシーケンスに対応する解析を実行する段階、及び描画コマンドシーケンスに対応する解析に基づいて、一組の画像セグメントを生成する段階を有する。
【発明を実施するための最良の形態】
【０００９】
本発明は、様々な実施形態を含む以下の詳細な説明と添付の図面とから更に完全に理解されるであろう。しかしながら、これら詳細な説明及び図面は、単に説明及び理解のためのものであり、本発明を具体的な実施形態に限定するものとして解されるべきではない。
【００１０】
本発明の実施形態は、描画コマンド（例えば、ページ記述言語）を別の表現に変換する技術を含んでいる。一実施形態において、描画コマンドは一層と効率的なＪＰＭ画像に変換される。一実施形態において、この変換は描画コマンドの幾何学な範囲に基づく。他の一実施形態においては、この変換は描画コマンドシーケンス及び描画演算子に基づく。何れの場合にも、描画コマンドの実行時に作成されるビットマップに基づいて決定が為される。これらの場合、ビットマップは描画コマンドの実行結果である。
【００１１】
なお、以下において、用語“命令”、“操作”を伴う“コマンド”は相互に入れ替え可能に使用される。
【００１２】
以下の記載において、本発明のより完全な説明を提供するために数多くの詳細事項が説明される。しかしながら、当業者に明らかなように、本発明はこれらの具体的な詳細事項を用いずに実施されてもよい。また、本発明を不明瞭にしないよう、周知の構造及び装置はブロック図の形態で示し、詳細には示さないこととする。
【００１３】
以下の詳細な説明の幾つかの部分は、コンピュータメモリ内でのデータビットの処理のアルゴリズム及び記号表現により提示される。これらアルゴリズムの記載及び表現は、データ処理分野の当業者が自身の仕事の実体を他の当業者に最も効果的に伝えるために用いる手段である。アルゴリズムは、ここでは、そして一般的に、所望の結果を生じさせる首尾一貫した一連のステップであると考えられる。これらのステップは物理量の物理的な操作を必要とするものである。通常、必ずしもではないが、これらの量は、保存され、転送され、結合され、比較され、そしてその他の方法で操作されることが可能な電気信号又は磁気信号の形態である。時々、主に一般的な用法上の理由で、これらの信号をビット、値、要素、記号、文字、用語、数字などと呼ぶと都合がよいことが分かっている。
【００１４】
しかしながら、これら及び同様の用語の全ては、適当な物理量に関連付けられるべきものであり、単にこれらの量に付けられた便利な呼び名であることに留意すべきである。特に断らない限り、以下の説明から明らかなように、この詳細な説明の全体を通して、例えば“処理する”、“計算する”、“算出する”、“決定する”、又は“表示する”等の用語を用いる説明は、コンピュータシステムのレジスタ及びメモリ内の物理（電子的）量として表されたデータを操作して、コンピュータのシステムメモリ若しくはレジスタ又はその他の情報記憶、伝送又は表示装置内の物理量として同様に表された他のデータに変換するコンピュータシステム又は同様の電子計算機の動作及び処理を参照するものであると認められるものである。
【００１５】
本発明はまた、ここでの操作を実行する装置に関する。この装置は必要とされる目的のために特別に構築されていてもよいし、あるいはコンピュータに記憶されたコンピュータプログラムによって選択的に作動又は再設定される汎用コンピュータを有していてもよい。このコンピュータプログラムはコンピュータ可読記憶媒体に格納されていてもよい。コンピュータ可読記憶媒体は、例えば、これらに限られないが、フロッピー(登録商標)ディスク、光ディスク、ＣＤ−ＲＯＭ及び磁気光学ディスクを含む任意の種類のディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気若しくは光カード、又は電子的な命令を格納するのに適し且つ各々がコンピュータシステムバスに結合された任意の種類の媒体などである。
【００１６】
ここで提示されるアルゴリズム及び表示は、如何なる特定のコンピュータ又はその他の装置にも本質的に関連付けられるものではない。ここでの教示に従ったプログラムを用いて様々な汎用システムが使用されてもよいし、あるいは必要とされる方法ステップを実行する、より専用化された装置を構築する方が好都合であってもよい。多様なこれらシステムに必要とされる構造については以下にて説明される。さらに、本発明は特定のプログラム言語に関連させずに説明される。認識されるように、多様なプログラム言語が、ここに記載される本発明の教示を実践するために使用され得る。
【００１７】
機械可読媒体には、機械（例えば、コンピュータ）により読み取り可能な形態で情報を記憶又は伝送する如何なる機構も含まれる。例えば、機械可読媒体には、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、又は電気的、光学的、音響的若しくはその他の形態の伝播信号（例えば、搬送波、赤外線信号、デジタル信号など）等が含まれる。
【００１８】
先ず、本発明を概説する。本発明の実施形態は描画コマンドを別の表現（例えば、ＪＰＭ画像表現）に変換する。一実施形態において、描画コマンドはページ記述言語の一部である。一実施形態においては、例えばアドビシステム社のポストスクリプト（PostScript）言語などの高度な描画システムを有するページ記述言語が使用され、ページ記述言語はＪＰＭ画像表現、又は何らかの他の混合ラスタコンテンツフォーマットに変換される。例えば、ＰＤＦは、単に画像配置以外の如何なる描画コマンドをも排除することによって、混合ラスタ表現として使用可能である。
【００１９】
一実施形態において、描画言語は時間的に順序付けられた一連の描画命令タプル（操作）に分解可能である。この一連の描画命令タプルは、操作コード（オペコード）を含んでおり、操作を明確にする１つ以上の更なるオペランドを含んでいてもよい。例えば、アドビシステム社のポストスクリプト言語は、スプライン曲線（直線はこの中の小集団である）を描き、スプライン曲線を色で塗りつぶし、ラスタ画像を配置し、そしてテキストを描く演算子を有している。“フィルレクト（fillrect）”演算子はページ上での長方形の位置及び範囲を指定するオペランドを受理する。いったん命令群に分解されると、これらの命令群は新たな表現を生成するために使用され得る。
【００２０】
一実施形態において、画像表現はＪＰＭであるように選択される。ＪＰＭ文書は任意の複雑度を有することができるが、何れかの特定のラスタ位置（x，y）の画素値を選定することの複雑度はｎ次の操作である。ただし、ｎはその位置と重なり合う範囲を有する画像の数である。故に、如何なる所与の領域においても正確な値を与え、且つ最小数のビットマップを使用する画像表現を選択すると効率的である。
【００２１】
他の一実施形態においては、良好な一組のコンポーネント画像表現を選択する助けとするため、描画コマンドの語義が使用される。
【００２２】
一組のコンポーネント画像表現が選択されると、それらは個々に符号化される。一部の画像符号化アルゴリズムは或る一定種類の画像に関して、より小さい画像歪みを伴いながら一層良好な圧縮をもたらすという事実を利用するため、本発明の一実施形態はコンポーネント画像表現ごとに符号化アルゴリズムを選択する。例えば、ＪＢＩＧ圧縮法は２つの明度のみを有する画像に関して優れた結果をもたらす。故に、画像セグメントが２つの明度のみを有する場合には、その画像セグメントを符号化するためにＪＢＩＧ又はＪＢＩＧ２圧縮法が選択され得る。同様に、ＪＰＥＧ２０００は連続的な色調の画像に関して優れた結果をもたらす。故に、画像セグメントが連続的な色調の画像である場合には、その画像セグメントを符号化するためにＪＰＥＧ２０００圧縮法が選択され得る。
【００２３】
適当な数の画像が適当な画像符号化とともに選択される。一実施形態において、各々が最良の利用可能な符号化を用いて、最小数のビットマップが示される。
【００２４】
図１は、描画コマンドシーケンスを操作し、新たな表現を生成する処理の一実施形態を示すフロー図である。この処理は、ハードウェア（回路、専用ロジック等）、ソフトウェア（例えば、汎用コンピュータシステム又は専用マシン上で実行される）、又はこれら双方の組み合わせを有する処理ロジックによって実行される。
【００２５】
図１を参照するに、この処理は、実行時に画像を作成する描画コマンドのシーケンスに対応する解析を行うことによって開始する（処理ブロック101）。描画コマンドシーケンスの解析を行った後、処理ロジックは描画コマンドシーケンスに対応する解析に基づいて一組の画像セグメント（例えば、ビットマップ）を生成する（処理ブロック102）。一実施形態において、この一組の画像セグメントの生成は描画コマンド自体の解析に基づく。他の一実施形態においては、この一組の画像セグメントの生成は描画コマンドシーケンスの結果に基づく。
【００２６】
画像セグメントの生成後、処理ロジックは各画像セグメントに対して符号化方法を選択する（処理ブロック103）。一実施形態において、この符号化方法の選択は描画コマンド自体の解析に基づく。他の一実施形態においては、この符号化方法の選択は描画コマンドシーケンスの結果に基づく。更に他の一実施形態においては、この符号化方法の選択は復号化資源の利用可能性に基づく。より更に他の一実施形態においては、この符号化方法の選択は達成可能な圧縮量に基づく。
【００２７】
符号化方法の選択後、処理ロジックは各画像セグメントを選択された符号化方法を用いて符号化し、一組の符号化された画像セグメントを作成する（処理ブロック104）。
【００２８】
符号化されると、一実施形態において、処理ロジックは符号化されたデータを有する複合画像ファイルを書き込む（処理ブロック105）。一実施形態において、この複合画像ファイルはＪＰＭファイルである。他の一実施形態においては、この複合画像ファイルはＰＤＦファイルである。
【００２９】
一実施形態において、処理ロジックは描画コマンドシーケンスに対応する解析を以下のように実行する。すなわち、シーケンス内の各コマンドが順々に検査されるように各コマンドをグループ分けし、その後、コマンド毎にその結果を、そのコマンドがシーケンス内の直前のコマンドと同一グループにある場合には、存在している１つの図面（例えば、ビットマップ）の電子版に付加し、また、そのコマンドがシーケンス内の直前のコマンドと同一グループにない場合には、その図面を保存し且つそのコマンドの結果を用いて別の１つの図面（例えば、ビットマップ）の電子版を作成することによって実行する。この場合、これらの図面の電子版が画像セグメントである。
【００３０】
他の一実施形態においては、処理ロジックは描画コマンドシーケンスに対応する解析を以下のように実行する。すなわち、シーケンス内の各コマンドが（順々に）検査されるように各コマンドをグループ分けし、第１のグループの１つ以上の描画コマンド用の第１のビットマップを生成し、第１のグループ内の全ての描画コマンドが解析されたときに第１のビットマップを保存し、そして第２のグループの１つ以上の描画コマンド用の第２のビットマップを生成することによって実行する。この場合、一実施形態において、この処理は更に、第２のグループ内の全ての描画コマンドが解析された後に第２のビットマップを保存することを含む。
【００３１】
更に他の一実施形態においては、処理ロジックは描画コマンドシーケンスに対応する解析を、組み合わさって画像を形成する複数の領域（例えば、長方形のタイル）の各々に対する各描画コマンドの幾何学的な影響を決定することによって実行する。この場合、各画像セグメントは１つの領域の画像データに相当する。一実施形態において、上記の幾何学的な影響は、その描画コマンドに関連する色を含む。また、この場合、各画像セグメントに使用する符号化法の選択は、それが関連する領域の画像データに基づく。一実施形態において、この選択は、全ての描画コマンドの幾何学的な影響が領域群に対して決定された後の、その領域内の色の数に基づく。
【００３２】
更に他の一実施形態においては、処理ロジックは描画コマンドシーケンスに対応する解析を、描画コマンド毎に以下の操作を行うことによって実行する。すなわち、各描画コマンドの結果によって生成される色のリストを決定し、その描画コマンドの結果によって交わられるタイルのリストを決定し、その描画コマンドの結果によって交わられるタイルのリスト内の各タイルをタグ付けするように上記の色のリストを加え、そして、その描画コマンドの結果によって交わられるタイルのリスト内のタイル群に結果ビットを複製することによって実行する。この実施形態においては、各画像セグメントに使用する符号化方法の選択は、それが関連する領域の画像データに基づく。
【００３３】
更に他の一実施形態においては、処理ロジックは描画コマンドシーケンスに対応する解析を、描画コマンド毎に以下の操作を行うことによって実行する。すなわち、各描画コマンドの結果によって生成される色のリストを決定し、その描画コマンドを実行した結果を包囲する境界ボックスを決定し、その描画コマンドに関連するタイルビットマップを作成し、そして、上記の色のリストを用いてタイルビットマップをタグ付けすることを含めて、その描画コマンドの実行により得られるビットを、その描画コマンドによって影響を受けるビットマップに複製することによって実行する。タイルは後にその種類を特定できるようにタグ付けされる。一実施形態において、影響を受ける全てのタイルがタグ付けされる。空（エンプティ）タイルビットは空タイルを指定するために使用され得る。空タイルを指し示す空タイルビットを有するタイルはタグ付けされる必要はない。
【００３４】
符号化が実行されない代替的な一実施形態においては、処理ロジックは、処理の一部として生成された画像セグメント（例えば、ビットマップ）を用いて複合画像ファイルを書き込んでもよい。
【００３５】
一実施形態において、処理ロジックが描画コマンドの解析を実行した後、使用する符号化技術の選択が行われる。図２は、描画コマンドシーケンスを操作する処理の他の一実施形態を示すフロー図である。この処理は、ハードウェア（回路、専用ロジック等）、ソフトウェア（例えば、汎用コンピュータシステム又は専用マシン上で実行される）、又はこれら双方の組み合わせを有する処理ロジックによって実行される。
【００３６】
図２を参照するに、この処理は、処理ロジックが描画コマンドのシーケンスに対応する解析を行うことによって開始する（処理ブロック201）。そして、処理ロジックは描画コマンドシーケンスに対応する解析に基づいて、複数の画像セグメントの各々に関する符号化を選択する（処理ブロック202）。一実施形態において、各画像セグメントに関する符号化を選択することは、何れの符号化が最良の圧縮をもたらすかに基づく。他の一実施形態においては、各画像セグメントに関する符号化を選択することは、その画像セグメントによって表される領域における、描画コマンドシーケンスの各々の影響に基づく。
【００３７】
上述のように、命令のストリーム（例えば、描画コマンドシーケンス）を読み込んで、別のフォーマット（例えば、ＪＰＭフォーマット）にビットマップを積み上げる処理には、幾つかの異なる実施形態が存在する。１つのこのようなアルゴリズムは時間的なセグメント化を用い、その他のアルゴリズムは様々な形態の幾何学的なセグメント化を用いる。以下にて、これらの各々について更に詳細に説明する。
【００３８】
順序アルゴリズムについて説明する。一実施形態において、逐次処理を用い、逐次的な操作シーケンスによって図面がセグメント化される。一実施形態において、操作群は種類に基づいてクラスに分割される。単純な一組のクラスが一実施形態において選択される。“テキスト描画”操作、“画像配置”操作、“状態設定”、及び“一般描画”操作のクラスが定義される。一実施形態において、これらのクラスは操作コードに関して定義される。他の一実施形態においては、操作コードとオペランドのデータタイプとの双方が用いられる。議論のため、操作はクラスに分割され得ることに留意すべきである。一実施形態において、実際の操作を含まない“空値（以下、NULL）”操作クラスが各ページの先頭と末尾に暗黙のうちに挿入される。この“NULL”操作は、セグメント化アルゴリズムを既知の状態（例えば、開始）が存在する位置で同期化させることを可能にする。
【００３９】
時間的処理においては、処理ロジックは、正確な最終画像に組立可能な一連の重なり合った画像を生成する。操作シーケンス内の或る１つの操作が調べられるとき、先行する操作とは操作クラスが相違すると常に、新たな画像／マスク対が生成される。相違が検出されると、如何なる既存の画像／マスク対も終了させられ、最終画像に足し合わされる。そして、新たな操作に基づく新たな画像／マスク対が作成される。
【００４０】
図３は逐次的セグメント化処理の一実施形態を示すフロー図である。この処理は、ハードウェア（回路、専用ロジック等）、ソフトウェア（例えば、汎用コンピュータシステム又は専用マシン上で実行される）、又はこれら双方の組み合わせを有する処理ロジックによって実行される。
【００４１】
図３を参照するに、この処理は、処理ロジックが何らかの描画コマンドが残っているかどうかを決定することによって開始する（処理ブロック301）。残っていれば、処理ロジックは描画コマンドを読み出し（処理ブロック302）、コマンドを分類する（処理ブロック303）。処理ロジックはまた、新たなカテゴリーに属するコマンドであるかどうかを検査する（処理ブロック304）。そうであれば、処理ロジックは既存のビットマップを保存し（処理ブロック305）、新たなビットマップを作成し（処理ブロック306）、レンダリングされたコマンド結果を現在のビットマップに足し合わせる（処理ブロック307）。コマンドが新たなカテゴリーのものでない場合には、処理ロジックは直接的に処理ブロック307へと移行する。レンダリングされたコマンド結果を現在のビットマップに足し合わせた後、処理は処理ブロック301へと移行し、処理が繰り返される。
【００４２】
描画コマンドが残っていない場合、処理ロジックは如何なる既存のビットマップをも保存し（処理ブロック308）、複合画像ファイル（例えば、ＪＰＭファイル、ＰＤＦファイル）を書き込む（処理ブロック309）。その後、処理は終了する。
【００４３】
逐次セグメント化処理を用いる一例は、以下の操作を用いて次のように与えられる：
NULL
半径100の円を100，100に描画
テキスト“ａｂｃ”を100，100に描画
テキスト“ｄｅｆ”を100，120に描画
描画色を“赤”に設定
テキスト“ｇｈｉ”を100，140に描画
画像“ｍｙｉｍａｇｅ”を300，300に描画
NULL
【表１】
2008059590.tif 000003
【００４４】
上記にて与えられた一組の操作に時間的処理を適用することは、表１のようにセグメント化された４つの画像／マスク対を生成する。
【００４５】
続いて、グリッドに基づく幾何学的アルゴリズムについて説明する。グリッドに基づく幾何学的処理の一実施形態においては、操作ストリームを検査し、個々の画素値が個々の画像タイルの何処に書き込まれるかを決定することによって、一組のタイル画像が作り出される。
【００４６】
上述のように、命令ストリーム内の操作群がクラス群にセグメント化される。一実施形態において、クラスは操作によって描画される画素の色に基づく。操作のクラスは操作によって作成される全ての画素値の組である。一実施形態において、操作のクラスは、上述の例における“描画色設定”操作の場合と同様に、先行する操作群に依存する。この場合、白黒画像は画素値の組（0，1）を有するかもしれず、カラー画像はその画像クラス内に画素値の長いリスト（1，28，29，123，・・・）を有するかもしれない。
【００４７】
最終的なラスタは或る一定の幅と高さとを有するタイル群に分割される。一実施形態において、タイル群は規則的なグリッドを形成する。一実施形態において、各タイルは自身に割り当てられたクラスを有し、このクラスもまた一組の画素値である。新たなページが始まると、各タイルのクラスは空（エンプティ）の画素値の組を用いて初期化される。各々の操作が処理されるとき、その操作に影響を及ぼし得るタイル群が計算される。このようなタイル毎に、タイルのクラスが自身の現在のクラスと操作のクラスとの結合に基づいて計算される。
【００４８】
画像の符号化時、タイルのクラスに基づいてタイルの符号化法が選択される。一実施形態において、２色のみを含むクラスを有するタイルに対してＪＢＩＧ符号化が選択され、エンプティの組であるクラスを有するタイルに対しては符号化される画像はなく、そして、３色以上を含むクラスを有するタイルに対してはＪＰＥＧ２０００が符号化のために選択される。また、他の一実施形態においては、クラス群の１つが連続的な色調の画像と相互に関係を有する場合、ＪＰＥＧ２０００が符号化のために選択される。更に他の一実施形態においては、ＪＰＥＧが符号化のために選択される。
【００４９】
図４は、グリッドに基づく幾何学的セグメント化処理の一実施形態を示すフロー図である。この処理は、ハードウェア（回路、専用ロジック等）、ソフトウェア（例えば、汎用コンピュータシステム又は専用マシン上で実行される）、又はこれら双方の組み合わせを有する処理ロジックによって実行される。
【００５０】
図４を参照するに、この処理は、処理ロジックが複数の画像タイルビットマップを作り出すことによって開始する（処理ブロック401）。そして、処理ロジックは何らかの描画コマンドが残っているかどうかを決定する（処理ブロック402）。残っていれば、処理ロジックは描画コマンドを読み出し（処理ブロック403）、コマンド結果によって生成される色のリストを決定し（処理ブロック404）、コマンド結果によって交わられるタイル（すなわち、その結果に影響を受けるタイル）のリストを決定し（処理ブロック405）、交わられるタイル群の各々のタグに色のリストを追加し（処理ブロック406）、そして、そのコマンド結果によるビット群を、影響を受けるタイルビットマップに複製する（処理ブロック407）。結果は描画コマンドを実行することによって得られる。その後、処理は処理ブロック402へと移行し、処理が繰り返される。
【００５１】
描画コマンドが残っていない場合、処理ロジックは各タイルビットマップをタグ内の色の数に基づいて符号化し（処理ブロック408）、複合画像ファイルを書き込む（処理ブロック409）。その後、処理は終了する。
【００５２】
続いて、自由形式の幾何学的セグメント化アルゴリズムについて説明する。描画コマンドシーケンスを別の表現に変換する処理の他の一実施形態は、幾何学的なセグメント化を用いる。この場合、最終的なラスタは様々なサイズのタイル群を有するものとして扱われる。上述のグリッドに基づく幾何学的技法においてのように、操作のクラス群が画素値に基づいて計算される。
【００５３】
描画操作は順番に処理される。第１の操作が検査されるとき、長方形のタイルが作成される。長方形タイルの範囲は操作の境界ボックスによって定義される。このタイルは操作のクラスと同一のクラスに割り当てられる。
【００５４】
全ての後続操作に対して、その操作のクラス及び見込みタイルが計算される。場合により、この見込みタイルと交わる境界ボックスを有する既存のタイル群が検出される。重なり領域毎に、既存タイルのクラスと見込みタイルのクラスとの結合が計算される。新たなクラスが既存タイルのクラスと異なる場合、既存タイルと見込みタイルとの重なりの詳細に応じて、既存タイルは多数のタイルに分割される。一実施形態において、既存タイルは２乃至５個のタイルに分割される。一実施形態において、既存タイルが分割されるタイルの数は、２つの長方形領域の交わりによって作り出される交わりのない新たな長方形セグメントの数に基づく。この２つの長方形領域の交わりによって作り出される交わりのない新たな長方形セグメントの数は、これらの領域の交わり方によって決定される。図７のＡ乃至Ｄは交わりの例を示している。図７のＡ乃至Ｄを参照するに、互いに直交する斜線で示された２つの長方形が、交差斜線で示された交差部で交わっている。図示されるように、これらにより（取るに足らない完全に重なることは無視して）、２乃至５個の交わりのない新たな長方形セグメントが作り出される。各タイルはそのタイル内に含まれる色の集合に基づいて新たなクラスに割り当てられる。この集合が見込みタイルのクラスと異なる場合、見込みタイル自体が多数（例えば、２乃至５個）の新たな見込みタイルに分割される。新たな見込みタイルの各々は、その他のタイル群との重なりに関して検査される。既存タイル群は重なり合うことが許されていないので、見込みタイル群について、以前に重なりを検査されている既存タイル群に対して再検査する必要はない。なお、１対１のマッピングは常に新たなタイルを必要とするわけではない。
【００５５】
グリッドに基づく方法を用いた場合のように、全ての描画操作を処理した後、所与のタイルに関する符号化法がそのタイルのクラスに含まれる色の数に基づいて選択される。
【００５６】
図５は、自由形式の幾何学的セグメント化処理の一実施形態を示すフロー図である。この処理は、ハードウェア（回路、専用ロジック等）、ソフトウェア（例えば、汎用コンピュータシステム又は専用マシン上で実行される）、又はこれら双方の組み合わせを有する処理ロジックによって実行される。
【００５７】
図５を参照するに、この処理は、処理ロジックが何らかの描画コマンドが残っているかどうかを決定することによって開始する（処理ブロック501）。残っていれば、処理ロジックは描画コマンドを読み出し（処理ブロック502）、その描画コマンドの実行結果によって生成される色のリストを決定し（処理ブロック503）、そのコマンド結果の境界ボックスを（そのビットマップの広がり範囲を用いて）決定し（処理ブロック504）、そして、そのコマンド結果に対応するタイルビットマップを作成する（処理ブロック505）。
【００５８】
次に、処理ロジックは、このタイルビットマップが既存タイルの境界と交わるかどうかを検査する（処理ロジック506）。交わる場合、処理ロジックは既存タイルを重なり合わないサブタイル群にセグメント化し（処理ブロック511）、処理は処理ブロック507へと移行する。交わらない場合には、処理ロジックは直接的に処理ブロック507へと移行する。
【００５９】
処理ブロック507にて、処理ロジックは、その描画コマンドの結果に対応するビット群を、影響を受けるタイルビットマップに複製し、タイルビットマップに付随するタグを色のリストを用いて設定する（処理ブロック507）。そして、処理ロジックは処理ブロック501へと移行する。
【００６０】
描画コマンドが残っていない場合、処理ロジックは各タイルビットマップをタグ内の色の数に基づいて符号化し（処理ブロック508）、タイルビットマップ群に対応する符号化データを用いて複合画像ファイル（例えば、ＪＰＭファイル、ＰＤＦファイル等）を書き込む（処理ブロック509）。その後、処理は終了する。
【００６１】
続いて、代わりとなるアルゴリズムについて説明する。描画コマンドによってセグメント化を実行するアルゴリズムの変形である他の一実施形態が用いられてもよい。この技法は以下の通りである。第１に、コマンドの種類によって各コマンドがクラス分けされる。そして、クラス毎にページサイズのビットマップ及びマスクが作成される。（アルファ混合が必要な場合、マスクは多重ビットであってもよい。他の一実施形態においては、個々のマスクは最終段階まで作成されない。各画素に関する各クラスのビットマップからの最終的な寄与に関する一般的な計算が、個々のマスクを置き換える。違いはメモリ内でアレイがアドレスされる方法に帰着する。）故に、全ての描画コマンドが順番に実行される。また、画素値は描画コマンド毎に正しいクラスのビットマップに置かれ、影響を受ける画素毎に全てのクラスの全てのマスクが更新される。（このマスキングは、何れの画素が変更され、何れがふさがれるかを決定するための描画コマンドの順序付けを置き換える。）
続いて、２つ以上のアルゴリズムの組み合わせについて説明する。上述の技法の全ては様々に組み合わされることが可能である。例えば、好適に構築された命令ストリームは、時間的にセグメント化されると、最終的な画像に影響しないが多数の不必要な画像コンポーネントを生成するように操作クラスを変更することによって、著しく劣悪な結果を有し得る。組み合わされた自由形式セグメント化及び時間的セグメント化は失われた効率のほぼ全てを回復することができる。一実施形態において、時間的セグメント化によって作成された画像セットが用いられ、自由形式の幾何学的セグメント化が画像部分上で実行されて、各画像を画像配置描画コマンドとして扱う。
【００６２】
他の一例として、幾何学的セグメント化は、符号化スキームが異なる種類の歪みアーチファクトを持ち込む場合、セグメント境界に気になるエッジ効果をもたらすことがある。一実施形態において、時間的セグメント化は、小さい重なりが復号化効率を少々犠牲にして視覚的明瞭性を保持する場合、インスタンスを選び出す助けとなる情報を生成する。
【００６３】
続いて、コンピュータシステムの一例について説明する。図６は、ここに記載された操作の１つ以上を実行し得る典型的なコンピュータシステムを示すブロック図である。図６を参照するに、コンピュータシステム600は、典型的なクライアント又はサーバコンピュータシステムを有していてもよい。コンピュータシステム600は、情報を伝達する通信機構又はバス611、及びバス611と結合された情報を処理するためのプロセッサ612を有している。プロセッサ612はマイクロプロセッサを含むが、例えばペンティアム（登録商標）、パワーＰＣ（登録商標）等のマイクロプロセッサに限定されない。
【００６４】
システム600は更に、情報とプロセッサ612によって実行される命令とを記憶するための、バス611に結合されたランダムアクセスメモリ（ＲＡＭ）又はその他のダイナミック型記憶装置604（主メモリと称される）を有している。主メモリ604はまた、プロセッサ612による命令の実行時に、一時的な変数又はその他の中間情報を記憶するために用いられてもよい。
【００６５】
コンピュータシステム600はまた、プロセッサ612用の静的な情報及び命令を記憶するための、バス611に結合された読み出し専用メモリ（ＲＯＭ）及び／又はその他のスタティック型記憶装置606と、例えば磁気若しくは光ディスク及びその対応するディスクドライブ等のデータ記憶装置607とを有している。データ記憶装置607は情報及び命令を格納するためにバス611に結合されている。
【００６６】
コンピュータシステム600は更に、コンピュータユーザに情報を表示するための、バス611に結合された、例えば陰極線管（ＣＲＴ）又は液晶ディスプレー（ＬＣＤ）等の表示装置621を有していてもよい。また、情報及びコマンド選択をプロセッサ612に伝達するために、英数字及びその他のキーを含む文字・数字入力装置622がバス611に結合されていてもよい。更なるユーザ入力装置は、方向情報及びコマンド選択をプロセッサ612に伝達し、カーソル動作をディスプレー621上で制御するためにバス611に結合された、例えばマウス、トラックボール、トラックパッド、スタイラス・ペン、又はカーソル方向キー等のカーソル制御装置623である。
【００６７】
バス611に結合され得る他の装置は、例えば紙若しくはフィルム等の媒体、又は同様の種類の媒体に情報を印すために使用され得るハードコピー装置624である。バス611に結合され得る他の装置は、電話又は掌サイズのパーム装置と通信する有線／無線通信手段625である。
【００６８】
なお、システム600及び付随するハードウェアの構成要素の何れか又は全てが本発明において用いられてもよい。しかしながら、認識され得るように、この他のコンピュータシステムの構成がこれらの装置の一部又は全てを含んでいてもよい。
【００６９】
以上の説明を読んだ当業者には本発明の数多くの変更及び改変が明らかになることは疑いのないことであるが、説明図によって示され、説明された如何なる特定の実施形態も限定的に解されるものでないことは理解されるべきである。故に、様々な実施形態の詳細事項への参照は、本発明に本質的な特徴のみを列挙している請求項の範囲を限定するものではない。
【図面の簡単な説明】
【００７０】
【図１】描画コマンドシーケンスを操作する処理の一実施形態を示すフロー図である。
【図２】描画コマンドシーケンスを操作する処理の他の一実施形態を示すフロー図である。
【図３】逐次的セグメント化処理の一実施形態を示すフロー図である。
【図４】グリッドに基づく幾何学的セグメント化処理の一実施形態を示すフロー図である。
【図５】自由形式の幾何学的セグメント化処理の一実施形態を示すフロー図である。
【図６】ここに記載された操作の１つ以上を実行し得るコンピュータシステムの一例を示すブロック図である。
【図７】２つの長方形の間の交わりの例を示す図である。
【符号の説明】
【００７１】
101乃至105  …  段階
201乃至209  …  段階
301乃至310  …  段階
401乃至410  …  段階
501乃至511  …  段階
600  …  コンピュータシステム
604  …  主メモリ
606  …  スタティックメモリ
607  …  大容量記憶メモリ
611  …  バス
612  …  プロセッサ
620  …  外部ネットワークインターフェース
621  …  ディスプレー
622  …  キーボード
623  …  カーソル制御装置
624  …  ハードコピー装置
【図１】
2008059590.tif 000004
【図２】
2008059590.tif 000005
【図３】
2008059590.tif 000006
【図４】
2008059590.tif 000007
【図５】
2008059590.tif 000008
【図６】
2008059590.tif 000009
【図７】
2008059590.tif 000010