(57)【要約】文字の圧縮のためのシステム（図１）、方法、コンピュータプログラムプロダクトが提供される。最初に、文字が受信され、その後（ステップ１０４ で）文字の数学的表示が文字の圧縮品質の所望レベルに基づいて選択される（ステップ１０２ ）。このような文字はその後、選択された数学的表示を使用して表され（ステップ１０６ ）、それによって文字の数学的表示は圧縮される（ステップ１０８ ）。【選択図】図１
2004516496.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）文字を受信し、
（ｂ）文字の圧縮品質の所望レベルに基づいて文字の数学的表示を選択し、その数学的表示はパラメータで表される曲線、有理関数および／または多項式を含むグループから選択され、
（ｃ）選択された数学的表示を使用して文字を表し、
（ｄ）文字の数学的表示を圧縮するステップを含んでいる文字の圧縮方法。
【請求項２】
前記多項式は２の累乗の指数を含んでいる請求項１記載の方法。
【請求項３】
文字の部分の幅は、曲線と、その曲線に対して垂直な距離を示す２つの関数とを含む数学的表示により表される請求項１記載の方法。
【請求項４】
（ａ）文字を受信するためのコンピュータコードと、
（ｂ）文字の圧縮品質の所望レベルに基づいて文字の数学的表示を選択し、その数学的表示はパラメータで表される曲線、有理関数および／または多項式を含むグループから選択されるコンピュータコードと、
（ｃ）選択された数学的表示を使用して文字を表すコンピュータコードと、
（ｄ）文字の数学的表示を圧縮するコンピュータコードとを含んでいる文字を圧縮するためのコンピュータプログラムプロダクト。
【請求項５】
前記多項式は２の累乗の指数を含んでいる請求項４記載のコンピュータプログラムプロダクト。
【請求項６】
文字の部分の幅は、曲線と、その曲線に対して垂直な距離を示す２つの関数とを含む数学的表示により表される請求項４記載のコンピュータプログラムプロダクト。
【請求項７】
（ａ）文字を受信する論理装置と、
（ｂ）文字の圧縮品質の所望レベルに基づいて文字の数学的表示を選択し、その数学的表示はパラメータで表される曲線、有理関数および／または多項式を含むグループから選択されている論理装置と、
（ｃ）選択された数学的表示を使用して文字を表す論理装置と、
（ｄ）文字の数学的表示を圧縮する論理装置とを具備している文字の圧縮システム。
【請求項８】
前記多項式は２の累乗の指数を含んでいる請求項７記載のシステム。
【請求項９】
文字部分の幅は、曲線と、その曲線に対して垂直な距離を示す２つの関数とを含む数学的表示により表される請求項７記載のシステム。
【請求項１０】
（ａ）文字を受信し、
（ｂ）文字の圧縮品質の所望レベルと文字に関連するフォントに基づいて文字の数学的表示を選択し、その数学的表示は式ｘ（ｔ）＝半径＊（１−ｔ２ ）／（１＋ｔ２ ）とｙ（ｔ）＝２＊半径＊ｔ／（１＋ｔ２ ）により記述されるパラメータで表される曲線、有理関数およびｆｎ，ｋ （ｔ）＝ｎ！ｔｋ （１−ｔ）ｎ−ｋ ／［ｋ！（ｎ−ｋ）！］を含んでいる多項式を含むグループから選択され、
（ｃ）選択された数学的表示を使用して文字を表し、その文字の部分の幅は、曲線と、その曲線に対して垂直な距離を示す２つの関数とを含む数学的表示により表され、
（ｄ）文字の数学的表示を圧縮し、
（ｅ）文字の１つの１点を読取り、
（ｆ）パラメータの数を読取り、
（ｇ）パラメータを読取り、
（ｈ）パラメータに基づいて１曲線を描き、
（ｉ）インジケータビットを読取り、
（ｊ）上記ステップ（ｅ）−（ｉ）の少なくとも１つを反復し、インジケータビットに基づいてゼロではない巻数ルールを使用して曲線を塗つぶすステップを含んでいる文字の圧縮方法。
【請求項１１】
（ａ）文字の所望の圧縮に基づいて複数の文字の数学的表示を選択し、その数学的表示は有理関数および多項式を含むグループから選択され、
（ｂ）選択された数学的表示を使用して文字を表し、
（ｃ）文字の数学的表示を圧縮するステップを含んでいる文字の圧縮方法。
【請求項１２】
前記多項式は２の累乗の指数を含んでいる請求項１１記載の方法。
【請求項１３】
文字の部分の幅は、曲線と、その曲線に対して垂直な距離を示す２つの関数とを含む数学的表示により表される請求項１１記載の方法。
【請求項１４】
（ａ）文字の所望の圧縮に基づいて複数の文字の数学的表示を選択し、その数学的表示はパラメータで表される曲線および多項式を含むグループから選択され、
（ｂ）選択された数学的表示を使用して文字を表し、
（ｃ）文字の数学的表示を圧縮するステップを含んでいる文字の圧縮方法。
【請求項１５】
（ａ）文字の所望の圧縮に基づいて複数の文字の数学的表示を選択し、その数学的表示はパラメータで表される曲線および有理関数を含むグループから選択され、
（ｂ）選択された数学的表示を使用して文字を表し、
（ｃ）文字の数学的表示を圧縮するステップを含んでいる文字の圧縮方法。
【請求項１６】
（ａ）複数の文字を受信し、
（ｂ）文字の圧縮品質の所望レベルを識別し、
（ｃ）文字に関連するフォントを識別し、
（ｄ）文字の圧縮品質の所望レベルおよび文字に関連するフォントに基づいて文字の数学的表示を選択し、
（ｅ）選択された数学的表示を使用して文字を表し、
（ｆ）文字の数学的表示を圧縮するステップを含んでいる文字の圧縮方法。
【請求項１７】
（ａ）文字の所望の圧縮に基づいて複数の文字の数学的表示を選択し、その数学的表示はパラメータで表される曲線と有理関数の少なくとも一方を含むグループから選択され、
（ｂ）選択された数学的表示を使用して文字を表し、
（ｃ）文字の数学的表示を圧縮するステップを含んでいる文字の圧縮方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的にイメージデータの処理に関し、特に２次元曲線イメージデータを圧縮するイメージデータ処理方法に関する。
【０００２】
【従来の技術】
イメージ処理の分野では、２次元曲線イメージ、即ちフォント文字は通常複数のセグメントに分解され、ベクトルは各セグメントに対応して割当てられる。したがって、曲線はそのセグメントにそれぞれ対応する複数のベクトルにより表される。このような方法では、曲線が大きい曲率を有するか複雑であるとき、多数のベクトルが必要とされる。それに関連して、処理される情報は増加され、これは伝送またはメモリでの記憶を困難にする。
【０００３】
フォントに対して数学的なフォーマットを使用する動機は文字のさらにコンパクトな記述を実現することである。文字に適合された新しいタイプの数学的オブジェクトを導入することにより、記述を記憶するのに必要なデータ量は減少される。選択されたプリミティブは文字自体の典型的な形状に基づいて種々のフォントファミリで異なる。
【０００４】
圧縮は２つの理由で行われる。第１の理由は個々の文字スクリプトが多数の類似点を有し、これらの類似点は種々の種類の領域または種々の種類の線のいずれかについての数学的基礎を選択することにより利用される。基礎自体は静的ではなく、そのエレメントに適用される数学的変形を有することができる。これらの変形は、伸長、拡大、縮小、屈折を含むがこれらに限定されない。変形自体は有限であり、幾つかのパラメータを使用してコード化される。
【０００５】
圧縮が行われる第２の理由は、領域または線の有限セットがツルータイプ（ＴｒｕｅＴｙｐｅ）およびポストスクリプト（ＰｏｓｔＳｃｒｉｐｔ）の両者により使用されるＢスプラインのような任意の接続の選択よりも曲線に良好に適するので、領域または線の個々のセットは（ＴｒｕｅＴｙｐｅまたはＰｏｓｔＳｃｒｉｐｔのように）アウトラインを接続する一連のドットを行うよりもコンパクトな方法でそれぞれの曲線を示すためである。
【０００６】
【発明が解決しようとする課題】
それ故、文字圧縮中に最適の方法で数学的表示を利用できるシステムが必要とされている。
【０００７】
【課題を解決するための手段】
文字の圧縮のためのシステム、方法、コンピュータプログラムプロダクトが提供される。最初に、文字が受信され、その後文字の数学的表示が文字の圧縮品質の所望レベルに基づいて選択される。このような文字はその後、選択された数学的表示を使用して表され、それによって文字の数学的表示は圧縮される。
【０００８】
本発明の１実施形態では、数学的表示はパラメータ化された曲線、有理関数および／または多項式を含んでいる。このような多項式は２の累乗の指数を含んでいる。さらに文字部分の幅は、曲線と、その曲線に対して垂直な距離を示す２つの関数を含む数学的表示により表されてもよい。
【０００９】
【発明の実施の形態】
図１は文字の圧縮方法１００ を示している。このような文字はアルファベット、。数字または任意のタイプのテキスト文字の形態を取ることができる。圧縮は文字の効率的な記憶および／または伝送の目的、或いは任意の他の所望の目的のためである。
【００１０】
最初に、動作１０２ で、文字が受信される。その後文字の数学的表示が文字の圧縮品質の所望レベルに基づいて選択される。動作１０４ を参照する。この選択はマニュアルまたはチャート等を使用した自動選択である。例えば、ある数学的表示は予め定められたレベルの品質に関連してもよい。１つの選択肢として、異なるフォントはある数学的表示を使用してより良好な品質で圧縮されることができるので、このような数学的表示もまた圧縮される文字フォントのタイプの関数として選択されてもよい。この設計により、所望のレベルの品質を与える数学的表示が選択されることができ、それによって品質とサイズとの妥協を可能にする。このような文字はその後、選択された数学的表示を使用して表され、それによって文字の数学的表示は圧縮される。
【００１１】
１つの選択肢として、数学的表示はパラメータ化される曲線、有理関数および／または多項式を含んでもよい。このような多項式は２の累乗の指数を含んでいる。さらに文字の部分の幅は、曲線と、その曲線に対して垂直な距離を示す２つの関数を含む数学的表示により表されてもよい。これらについてさらに詳細に以下説明する。
【００１２】
図２は前述の図１の方法１００ が実行されている代表的なハードウェア環境を示している。このような図面はマイクロプロセッサのような中央処理装置２１０ 、システムバス２１２ により相互接続される多数の他の装置を有する好ましい実施形態にしたがったワークステーションの典型的なハードウェア構造を示している。
【００１３】
図２で示されているワークステーションはランダムアクセスメモリ（ＲＡＭ）２１４ 、読取り専用メモリ（ＲＯＭ）２１６ 、ディスク記憶装置２２０ 等の周辺装置をバス２１２ へ接続するＩ／Ｏアダプタ２１８ 、キーボード２２４ とマウス２２６ とスピーカ２２８ とマイクロホン２３２ および／またはタッチスクリーン（図示せず）のようなその他のユーザインターフェース装置をバス２１２ へ接続するユーザインターフェースアダプタ２２２ 、ワークステーションを通信ネットワーク２３５ （例えばデータ処理ネットワーク）へ接続する通信アダプタ２３４ 、バス２１２ をディスプレイ装置２３８ へ接続するディスプレイアダプタ２３６ を含んでいる。
【００１４】
ワークステーションはマイクロソフトウィンドウズＮＴまたはウィンドウズ／９５オペレーティングシステム（ＯＳ）、ＩＢＭ  ＯＳ／２オペレーティングシステム、ＭＡＣ  ＯＳまたはＵＮＩＸオペレーティングシステムのようなオペレーティングシステムに存在する。好ましい実施形態は前述した以外のプラットフォームおよびオペレーティングシステムでも実行されてもよいことが認識されるであろう。好ましい実施形態はオブジェクト指向プログラミング方法と共に、ＪＡＶＡ，Ｃおよび／またはＣ＋＋言語またはその他のプログラミング言語を使用して書かれてもよい。オブジェクト指向プログラミング（ＯＯＰ）は複雑なアプリケーションを開発するための使用が増加している。
【００１５】
本発明は特定の数学的表示を選択することによって品質に関して圧縮を調節することができる。適切な数の曲線に必要な品質に応じて、適切な数学的基本は有限セットの変形が同様に選択されてもよい。ユーザは品質と寸法と妥協を行うことができる。
【００１６】
この手順で使用されることのできる１つの数学的表示はパラメータ化された曲線である。パラメータ化された曲線は実数（通常は閉じた間隔）のサブセットから平面へのマッピングである。このようなパラメータ化は２つの実数値の関数ｘ（ｔ）とｙ（ｔ）を使用して行われる。計算を容易にするため、ｘ（ｔ）とｙ（ｔ）に使用される関数のセットを、迅速に評価されることができる多項式のような関数に限定するとよい。有理関数（多項式の商）もまたこれに関しては有用である。広い範囲の曲線がこのようにして記述されることができる。例えば表１は完全な円の式を示している。
表１
ｘ（ｔ）＝Ｒ（１−ｔ２ ）／（１＋ｔ２ ）
ｙ（ｔ）＝２Ｒｔ／（１＋ｔ２ ）
これはｘ２ ＋ｙ２ を計算することにより証明されることができる。これらの関数は円の他のパラメータ表示で使用される平方根、正弦、余弦によりさらに迅速に評価されることができる。整数の数学を使用するときでも、半径Ｒは１よりも大きい数であり、座標ｘとｙはグリフをラスター化するときともかく整数値に丸められなければならないので、これらの公式は便利である。
【００１７】
広範囲の曲線が多項式だけを使用してパラメータで表されることができる。これを行う１方法が図２で示されている関数を使用することである。
【００１８】
表２
ｆｎ，ｋ （ｔ）＝ｎ！ｔｋ （１−ｔ）ｎ−ｋ ／［ｋ！（ｎ−ｋ）！］
これらの関数はこれらが整数ｎの固定値について整数ｋで合計されるとき、その結果が定数の関数１であるという特性を有する。ｋの合計範囲は０乃至ｎである。さらに、これらの各関数はオープンインターバル（０，１）で明白に正である。これらの関数を有効にするのは、これらがそれぞれインターバル（０，１）で単一の局部化された最大値を有し、それによってこれらは曲線の１つの小さい領域でパラメータ表示された曲線の形状を調節するために使用されることができることである。
【００１９】
最大値ｆｎ，ｋ （ｔ）の位置はゼロに等しいｔに関して第１の導関数を設定し、ｔを解くことにより基本的な計算を使用して発見されることができる。その結果はｔ＝ｋ／ｎである。この点でのｆｎ，ｋ （ｔ）値を知ることも重要である。その結果は階乗関数のスターリング近似を使用して評価するためにさらに高速である形に変換されることができる。この結論として、先に規定した関数ｆｎ，ｋ （ｔ）が２πｋ（ｎ−ｋ）／ｎの平方根により乗算されるならば、結果的な関数はその最大値および局部化に関して同一の特性を有するだけでなく、その最大値において１にほぼ等しい値を仮定する。この正規化特性は幾つかのケースでこれらの関数の実行を容易にする。例えばパラメータ化された曲線は表３の式により規定されてもよい。
表３
ｘ（ｔ）＝Ｆ４，０ （ｔ）−Ｆ４，２ （ｔ）
ｙ（ｔ）＝Ｆ４，１ （ｔ）−Ｆ４，３ （ｔ）
このような規定により、結果は円に似ているが、多項式だけが使用される。ここで符号Ｆｎ，ｋ （ｔ）は前述のｆｎ，ｋ （ｔ）の正規化されたバージョンを示すために使用されている。多項式はネストされた構造によりこれらを書込むことによって迅速に評価されることができ、それによってわずか数回の乗算と加算が必要とされるだけである。またｆｎ，ｋ （ｔ）の多項式は反復的に生成されるか、形式ｔｋ ／ｋ！の表を作成することにより生成されることができる。累乗ｔは平方を反復することにより発見されることができるので、計算が迅速である他の多項式は２の累乗である指数を有する多項式である。
【００２０】
このようにして、かなり複雑な曲線が種々の次数の多項式を使用して作成されることができる。実際には、高次数の多項式の記憶が必要な情報を記憶するのに必要なスペースに関して正当であるか否かが決定されなければならない。
【００２１】
多項式の別の利点はタンジェントベクトルを決定することが容易であることである。タンジェントベクトルは導関数（ｘ（ｔ），ｙ（ｔ））により与えられる。多項式の場合、これは再び多項式により与えられ、関与する係数はｔｎ の導関数がｎｔｎ−１ である事実を使用して容易に決定されることができる。代わりに、数字の導関数も可能である。この場合、（ｘ（ｔ），ｙ（ｔ））の導関数は小さい値のΔｔにおいて［（ｘ（ｔ＋Δｔ），ｙ（ｔ＋Δｔ））−（ｘ（ｔ），ｙ（ｔ））］／Δｔにより近似されることができる。
【００２２】
タンジェントベクトルを知ることにより幾つかの使用法を有する。このような使用法の１つはデータの大きな圧縮がそのエッジとその幅の一方に関するストロークの記述を記憶することによって可能であることである。両方のエッジについての情報を記憶するために、エッジは２つのパラメータ化されたパス、即ち可変の実数の全部で４つの実数値の関数の記憶を必要とする。幅はただ１つの実数値の関数であるので、パラメータ化されたパスではなくこれを記憶することが有効である。さらに、幅はしばしばパラメータのゆっくりと変化する関数であり、それ故その記述は少ない量のデータで実現されることができる。
【００２３】
幅についての情報を使用するために、曲線に対する垂直ベクトルを知る必要がある。これは曲線に直交する単位ベクトルである。曲線の２つのサイドに対応してこのベクトルには２つの可能な選択肢が存在する。垂直ベクトルの選択はタンジェントベクトルを９０度回転し、それを正規化することにより得られることができる。このような回転は２×２マトリックス（（０，−１），（１，０））による乗算によって実行されることができる。これは一方の符号の変更によりタンジェントベクトルのｘ座標とｙ座標のスワッピングを生じさせる。
【００２４】
タンジェントベクトルと同一の長さを有し、タンジェントベクトルの長さを知ることにより最適なレートでパスに沿ってステップすることを可能にするので、結果的なベクトルの正規化プロセスもまた有効である。このような最適なレートはステップ当り約１画素またはそれより僅かに少なく、それによってアウトラインはギャップなしに生成される。垂直ベクトルが外方向を指向している鋭角的な湾曲の場合、その先端が曲線よりも速く移動するので注意をしなければならない。ギャップは直線のセグメントで塗りつぶされる。
【００２５】
本発明の選択的な拡張は表示されない曲線に関するストロークと、基準曲線に垂直な距離の特定に使用される２つの関数を記述することである。これらの２つの関数はストロークのエッジの位置を規定する。これらは基準曲線に関してエッジの横方向オフセットを与える。この方法はエッジ自体のパラメータ化が困難である場合（例えばこれらばバンプまたは他の特性を含んでいる場合）に有効である。
【００２６】
図３は本発明の１実施形態にしたがってフォーマット方法のフロー図を示している。アウトライン、すなわち輪郭は種々のプリミティブを使用して規定されてもよいことに注意すべきである。これらのプリミティブは制御点またはその他のパラメータを使用して特定されてもよい。このようにアウトラインの一部の記述に含まれるデータのセットは全て図面の“パラメータ”のヘッディングの下に来る。例えばプリミティブの１つはアラビア文字記号で生じる低い屈曲したストロークである。その後パラメータはこの部分の輪郭を規定する３または４の数字であり、最初に曲線上の開始点を与える。
【００２７】
図３で示されているように、曲線上の１点は最初に動作３００ で読取られる。その後、動作３０２ で示されているように複数のパラメータが読取られる。その後全てのパラメータが動作３０４ で読取られる。これはその後曲線が描かれることを可能にする（動作３０６ を参照）。
【００２８】
曲線が一度描かれると、インジケータビットが読取られる。動作３０８ を参照する。ビットが“１”であるならば、プロセスは動作３００ にループバックし、曲線上の別の点が読取られる。しかしながら、ビットが“０”であるならば、プロセスは標準的なゼロではない巻数ルールを使用して塗りつぶされる曲線により終了する（動作３１０ を参照）。
【００２９】
動作３１０ でさらに多くの情報が説明される。本発明はゼロではない巻数により規定される多角形の表示を可能にする。この方法の利点は多角形がそれらの境界だけで表示されることができ、多数の多角形はそれらがオーバーラップしてもフレームバッファ中に含まれることができることである。境界により規定される多数の形状とゼロではない巻数がフレームバッファ中に共に存在できる。多数のオブジェクトは通常の方法の場合のように、それらの領域ではなく周囲に比例するコストで入力されることができる。全ての内部の塗りつぶしはフレームバッファがイメージされるとき単一のステップで実行されることができる。しかしながら、ゼロではない巻数により多角形を規定することは一般的ではない。ほとんどのグラフィックシステムは奇数の巻数により多角形の内部を規定する。インタープレスおよびポストスクリプト等のページ記述言語は奇数およびゼロではない巻数との両方の規定をサポートする。勿論、提案された方式はゼロではない巻数規定だけをサポートした新しいグラフィックシステムと共に使用されるが、より通常のシステムを構成するのに有効であるならば、奇数からゼロではない巻数へ変換する方法の規定が必要とされる。本発明の例示的なアプリケーションにおける情報がさらに多いときには、ＧＬＯＢＡＬＴＹＰＥ、産業で実在するフォント圧縮プロダクトを付加的に参照することができる。
【００３０】
図４乃至２０はゼロではない巻数ルールを使用する例示的なシステムを示している。現代のコンピュータグラフィックはフレームバッファに基づいている。フレームバッファは構成されるイメージの内部の表示を与える。イメージは色の付いたスポットまたは画素のラスターパターンとして表示される。フレームバッファはディスプレイの各スポットに対するデータエントリに区画されたメモリのブロックであり、通常ラスターにしたがって組織される。画素に対応するフレームバッファ素子中のデータはその画素の色を示している。フレームバッファとラスターグラフィックの開発により、（多角形のような）固体の領域が記述されイメージされる。しかし多角形を表示するために、通常、最初に規定された表示（通常は境界を形成するラインセグメントが得られる頂点のリスト）からフレームバッファにより必要とされるフォーマット（多角形により囲まれる画素のセット）へ変換しなければならない。これはラスター化または走査変換と呼ばれ、幾つかの方法が試みられている。
【００３１】
（フラッドフィルまたはシードフィルと呼ばれる）１つの方法は、背景以外の幾つかの色を使用してフレームバッファ中の多角形の境界を描写する。その後、多角形内であることが知られている幾つかの点（シード）で開始し、その技術は図４で示されているように境界に到達するまで近傍画素の色を変更することにより領域を成長する。この技術はオーバーラップする多角形を累積するために使用されることができるが、隔離された領域へアクセスするために多数のシードを必要とする。シード点を見つけることは困難であり労力がかかる。
【００３２】
別のアルゴリズムセットはパリティ技術と呼ばれる。ラスターが左から右へ走査されるならば、多角形はその左および右の境界を描くことにより構成されることができる（各走査線上の最も左の点と最も右の点の間の塗りつぶされる領域）。境界を含む領域はその後走査され、エッジはこれらが横切られるとき表示される。奇数のエッジが１つの画素に到達するように交差されるならば、画素は多角形の外であり、図５で示されているように色を付けられない。この技術はシード点を必要としないが、多数のオーバーラップする多角形を処理するには２つのフレームバッファ（または各画素に対して少なくとも３つの可能な状態を有する１つのバッファ）を必要とする。この技術は境界を描いて所定の多角形に対して内部にある画素を決定するための１つのバッファと、複合イメージを実際に累積するための第２のフレームバッファを使用する。第１のバッファは各多角形構造間でクリアされなければならないことに注意する必要がある。
【００３３】
第３のセットの技術は順序付けされたエッジリストに基づいている。これはパリティ構成に関連するが、境界を描くために第２のフレームバッファを必要としない。代わりに境界コンポーネントの解析的な記述が記憶される。境界は境界と走査ラインの交差点が容易に計算されるように１つの形態で表示されなければならない。境界は通常直線のエッジセグメントに分解され、これらは最小の走査線の終点により走査線の順序に分類される。その後、各走査線について、エッジとの交差点が計算され、走査内におけるそれらの順序に分類される。これらの点はその後、その走査線に対する内部画素の境界として使用される。パリティアルゴリズムのように、奇数の境界点が図６に示されているように到達するように交差されるならば、走査線上の画素は内部であると考慮される。この技術が第２のフレームバッファを必要としないが、走査ライン数に関して単調であり走査線の順序で発生されることができるるエッジ記述を有する領域に限定される。これはまた多角形のエッジセグメントを分解し分類する処理オーバーヘッドを必要とする。
【００３４】
一般的に、従来技術で開示された全ての塗りつぶしアルゴリズムは奇数の巻数による多角形の内部の規定に基づいている。１つの点に対する巻数はその点が多角形の境界をトレースするのに旋回される回数である。奇数の境界が到達するために交差される場合に内部である点を規定することは、奇数の巻数を有するとして内部点を規定することに等しい。しかしながら多角形の内部に対する別の規定も存在する。ゼロではない巻数を有するか、正の巻数が規定として使用されることができるならば、点は内部として規定されることができる。インタープレスおよびポストスクリプトのようなページ記述言語はゼロではない巻数と奇数の巻数との両規定をサポートする。
【００３５】
多角形が自己交差または幾つかの多角形がオーパーラップするとき代わりの定義は異なる結果を生む。２つの多角形の境界が奇数巻数の交差により規定されるとき、両者に共通の領域のパリティは図７のａで示されているように奇数から偶数にフリップする。したがって、２度塗つぶされる代わりに、共通の領域は全く塗つぶされない。これはパリティ技術が個々に各多角形を個別にラスター化しなければならず、第２のフレームバッファがイメージを累積する必要がある理由である。
【００３６】
正の巻数が使用されるならば、オーバーラップする内部は単にさらに大きい巻数を有し、図７のｂで示されているように依然として塗りつぶされた状態である。したがって多角形が正の巻数により規定されるならば、それらの幾つかの境界は集収され、それらの内部は走査線を通じて単一の掃引で塗りつぶされる。順序付けされたエッジリストの方法をゼロではない巻数により規定される多角形に適合することは多角形の境界を反時計回りにトレースするときエッジに沿って上または下に移動するか否かに基づいて方向数−１または＋１を各エッジに与えることを含んでいる。走査線に沿ってステップし、境界との交差点を示すとき、交差されるエッジの方向の数が付加される。この総数は図８で示されているように現在の点の巻数である。
【００３７】
それ故、本発明の目的はグラフィックイメージをラスター化する新しく簡単な方法を提供することである。本発明の別の目的は、ラスター化の時間依存がそれらの領域ではなく描かれたオブジェクトの周囲に比例するシステムを提供し、ハードウェアによりサポートされることができ高速度のイメージ生成において大きな利点を提供できる方法を与えることである。本発明の別の目的は正の巻数の境界が描かれることができる任意の形態をラスター化することを可能にすることである。本発明のさらに別の利点は以下の説明で明白になり、本発明を特徴付ける特徴は、この明細書の一部に付加しそれを形成する特許請求の範囲で特別に指摘されている。
【００３８】
本発明によれば、正の巻数により規定される多角形の境界はパリティラスター化技術と類似して順序つけされたエッジリストに記憶されるのではなくフレームバッファ中に直接描かれる。これはエッジリスト技術のオーバーヘッドを分解し分類する必要を除去し、境界中で使用される曲線のタイプとそれらを生成するために使用される方法におけるフレキシブル性をさらに可能にする。
【００３９】
正の巻数の多角形の単色の塗りつぶしを処理するためフレームバッファを一般化するために、各画素は３つの状態（背景、ダウン、アップ）を有することを可能にされる。これは記憶媒体の２つのビットを各画素へ割当てることにより最も容易に行われる。多角形の境界はもとの画素値（背景）を上または下に変更することにより、反時計回りに発生され、フレームバッファへ入力された。パリティアルゴリズムにおけるように、左および右のエッジだけが図９に示されているように入力される（水平の走向は図示されていない）。アップおよびダウン状態は方向数に対応する。
【００４０】
エッジが低い走査線から高い走査線へ発生されるならば、アップ状態が記憶され、ダウン方向で発生されるならば、ダウン状態が記憶される。全ての多角形の境界がラスター化ステップの前に入力されることができる。このステップはフレームバッファのディスプレイと共に実行される。ラスター化段では、パリティアルゴリズムにおけるように走査線によりラスター走査線をステップする。１走査線では、巻数はゼロに初期化され、各画素は検査される。値がダウンであるならば、巻数はインクリメントされる。値がアップであるならば、巻数はデクリメントされる。正の巻数を有する全ての画素は陰影を付けられる。
【００４１】
この点まで、この方法は２以上のエッジが図１０で示されているように一致する点で問題を有する。これらの点で巻数は全てのエッジによる総合的な増加または減少を反映するように変更されるべきであるが、２つの状態、アップおよびダウンが−１または１だけの変更を可能にするだけである。この問題を解決する進展は衝突する境界の画素値がイメージに深刻な損傷を与えずに空間的にオフセットされることができることを実現することである。ダウン状態が入力されるとき、画素は最初にチェックされる。その値が背景であるならば、ダウン状態が入力される。値がアップであるならば、２つのエッジのインクリメントおよびデクリメントが取消され、値の背景が入力される。値が既にダウンであるならば、次の画素が右であることが考慮され、計算が反復される。したがって一連の衝突するダウンエッジは右へ伝播する一連のダウン入力を生じる。一連の終了時に、巻数は補正される。アップ方向のエッジの描写は画素が既にアップ値を有するとき左への画素がチェックされることを除いて同様に処理される。
【００４２】
この方式が完全にエラーをもたないわけではない。行中の２つのダウン画素は図１１で示されているように別々の画素を通過するか両者とも左側の画素を通過する２つのダウン方向の線から生じる。２つのケースを弁別することはできない。アップ方向の線が左の点を通じて描かれるならば、左または右のダウン画素が消去されるべきであるか否かをすることはできない。しかしながら、このようなエラーは衝突シリーズの領域で局部化され、アップおよびダウンラインの両者が存在する場合のみ生じることに注意する。
【００４３】
このような衝突が生じることができる１つの共通の状態は幾つかの多角形が共通のエッジにクリップされるクリッピング領域に沿っている状態である。これらのケースでは、アップ値が一連のダウン画素と衝突するとき、一連の最も右の画素を消去することが最良である。同様に、ダウン画素が一連のアップ画素と衝突するとき、最も左の画素が消去されるべきである。この方法はクリッピング領域の収縮を防止する。
【００４４】
以下は前述の手順を実行するアルゴリズムである。
Ａ．拡張されたフレームバッファの全ての点を背景に設定する。
Ｂ．全ての多角形の境界を入力する。
１．左および右境界に対する画素座標を生成する多角形境界を囲って反時計回りにステップする。
２．ダウン方向のエッジ上の各画素に対して、ＳｔｏｒｅＤｏｗｎＰｏｉｎｔを呼出す。アップ方向のエッジ上の各画素に対して、ＳｔｏｒｅＵｐＰｏｉｎｔを呼出す。
Ｃ．イメージを表示する。
１．各走査線に対して、
・巻数を０に設定する。
・走査線上の画素をステップする。
・画素が値ダウンを有するならば、巻数をインクリメントする。
・画素が値アップを有するならば、巻数をデクリメントする。
・巻数が正であるならば、陰影として画素を表示し、そうでなければ陰影がないとして表示する。
【００４５】
したがって、拡張されたフレームバッファでは、各画素は３つの可能な状態、すなわち背景、アップ、ダウンを有する。以下の２つの手順によりフレームバッファに点が入力される。
ＳｔｏｒｅＤｏｗｎＰｏｉｎｔ
画素値が記憶されるまで反復する。
・現在の画素値が背景ならば、値ダウンを記憶する。
・現在の画素値がダウンならば、右方の次の画素へステップする。
・現在の画素値がアップならば、
・左方の次の画素値がアップでないならば、背景の値を記憶する。
・そうでなければ左方の次の画素へステップする。
ＳｔｏｒｅＵｐＰｏｉｎｔ
画素値が記憶されるまで反復する。
・現在の画素値が背景ならば、値アップを記憶する。
・現在の画素値がアップならば、左方の次の画素へステップする。
・現在の画素値がダウンならば、
・右方の次の画素値がダウンでないならば、背景の値を記憶する。
・そうでなければ右方の次の画素へステップする。
【００４６】
これはグラフィックイメージをラスター化する新しい、簡単な方法である。正の巻数境界が描かれることができる任意の形態をラスター化することができる。境界の解析的形態を有し走査順序で描くことを必要とせず、またその極点で分解することを必要としない。ラスター化の時間依存はそれらの領域ではなく描かれたオブジェクトの周囲に比例する。この方法はハードウェアによりサポートされることができ、高速度のイメージ生成において大きな利点を与えることができる。
【００４７】
本発明によれば、ページのスタートにおいて、フレームバッファは背景値のみを含むようにクリアされる。左および右のエッジに沿って画素の状態を変化することにより多角形がフレームバッファに入力される。ダウン方向に描かれたエッジはダウン状態に設定され、アップ方向に描かれたエッジはアップ状態に設定される。イメージするとき、バッファは一度に走査線を横切って掃引される（左から右へ）。各走査線のスタートにおいて、巻数はゼロに設定される。ダウン画素に遭遇すると、巻数はインクリメントされ、アップ画素に遭遇すると、デクリメントされる。正（またはゼロではない）巻数に対応する画素は陰影を付けられる。アルゴリズムは幾つかのエッジが同じ画素と交差する衝突を処理する。方式は変更が入力されることができる画素を見付けるために空間的に左から右へ移動する。アップ状態とダウン状態の衝突は２つの状態を消去させる。ダウン状態の衝突はダウン画素のチェーンを右へ伝播させ、アップ状態の衝突は左へ伝播させる。この方式についての問題は、１つの境界のエッジがそれを通過するか、または幾つかのエッジが近傍を通過するために、局部化されたエラーが画素が設定されるか否かについての曖昧さから生じる。
【００４８】
前述のジレンマに対する解決策は付加的な画素状態と付加的なコンピュータ処理を必要とする。しかしながら、これは各画素における巻数の変化を正確に表し、それ故にエラーはない。特に巻数の変化を正確に表すため、２つの付加的な状態が規定される。その状態は左および右の括弧“（“，”）”によりラベルを付けられる。それ故、フレームバッファ中の各画素は５つの状態を取ることができなくてはならない。これらの新しい状態は画素の巻数変化を明確に定めるために使用される。
【００４９】
画素が最初に境界エッジ（例えばダウン方向エッジ）に存在することが発見されたとき、３つの画素はフレームバッファ中で変更される。エッジが通過する画素は左の括弧状態“（”を得る。右の次の画素はダウン状態“ｄ”でマークされ、右方向の第２の画素は右の括弧状態“）”を得る（図１２参照）。第２のダウン方向のエッジが画素を通過するならば、第２のダウン状態は括弧間に挿入される。右の括弧は付加的な状態に適合するため１つの画素にわたってシフトする（図１３参照）。
【００５０】
アップ方向のエッジがダウン方向のエッジと同一の画素を通過するならば、アップおよびダウン状態の両者を括弧間に含むことができ、またはリストを減少または除去するようにダウン状態でアップ状態を消去できる（図１４参照）。画素に影響を与えるアップおよびダウン状態は括弧で囲まれ、左の括弧は境界エッジ画素を示している。付加的な状態が付加されるとき、リストは右へ成長する。右側の幾つかの画素に属す別のリストに遭遇するならば、この第２のリストをスキップし、右へ成長し続ける（図１５参照）。
【００５１】
エッジが最初に１つの画素を通過するが、その画素が左の画素のリストの一部として既に背景ではない値を有するならば、この初期リストの値は新しいリストに対する余地を作るために３画素だけ右にシフトされる（図１６参照）。前述したように、リストが右側で遭遇されると、それをスキップし、それを超えて変位し続ける。
【００５２】
この方式では、エッジのマーキングはエッジが通過する各画素について背景からリスト構造まで３つまでの画素を変更することを必要とする。したがって非常に密集したピクチャは長いリストを生成することができ、これは常に右側へ成長する。フレームバッファのエッジを超えて成長するリストの問題は、それを次の走査線の左側に単にワープさせることにより処理されることができる。これは多くの場合、フレームバッファメモリが組織される方法であり、フレームバッファのエッジで特別な処理は必要とされない。イメージング装置の解像度を増加するとき、このエンコードに有効な空間は２乗で増加し、一方処理されるエッジ画素数は線形にしか増加しないことに注意する。
【００５３】
各画素が付加的な状態を可能にされているならば、状態リストの長さは減少されることができる。図１７で示されている９個の状態では、リストは走査線を通過する各エッジに対して１つの走査線で変更されている１つの画素だけで構成されることができる（図１８参照）。単一の画素のアップおよびダウン状態が常に取消しならば、リストは全てアップ状態または全てダウン状態のいずれかを含む。この仮定では、図１９で示されているように１つの画素を通る取消されていない境界エッジ数に比例する長さでリストを表すために７つの状態のみが必要とされる。
【００５４】
ここで、リストの第１の画素はそれがアップまたはダウンエッジのリストであるか否かを示し、そのリストの残りの画素に対してでは、“ｘ”と“ｘ）”は存在するエッジの数をカウントする（図２０参照）。２進コンピュータシステムでは、単位画素当り４ではなく３のビットしか必要としないので、必要とする状態が８よりも少ないという利点がある。
【００５５】
リストの長さをさらに減少することはさらに状態を付加することにより実現されることができる。例えばリストの状態の２、４または８インスタンスを表す状態を付加する。しかしながら、２つの状態（アップおよびダウン）を０および１に単に再度規定し、その後２進数としての画素の巻数の変化をエンコードすることにより新しい状態なしに実現されることができる。例えば、５つのダウン方向のラインが１つの画素を通過するならば、巻数の変化は＋５である。リスト（ｄｄｄｄｄ）を使用する代わりに、これはリスト（０１０１）により表される。先頭の０は数の符号を設定する。
【００５６】
通常、イメージコンポーネントの境界は交差またはオーバーラップがほとんどなく広く分散される。したがって、このようなエンコード方式は必要とされないことが予測される。低い解像度で同じ画素に該当するエッジ近辺は高解像度では別々の画素にマップされることができるので、オーバーラップの可能性は解像度の増加によって若干少なくなる。しかしながら、合成−グラフィックイメージでは、画素のエッジは単に近いのではなく同一である傾向があり、この場合には、解像度の増加は役立たない。オーバーラップするエッジを生成する傾向の多い１つの動作はクリッピングである。幾つかのオブジェクトがクリッピング境界でオーバーラップする場合には、これらは全てその境界にクリップされ、境界に沿ってオーバーラップするエッジを有する。しかしながらこれらのエッジのオーバーラップの度合いは通常小さいオブジェクトのオーバーラップの度合いと同程度である。
【００５７】
以下、前述したような基本的な５状態のフレームバッファエンコードを処理するためのアルゴリズムのサンプル構成を説明する。その手順はＣプログラミング言語でコード化される。
【００５８】
拡張されたフレームバッファに入力されるオブジェクトは後に除去または消去されることができることに注意すべきである。また、方式は単なる線でなく逐次的に生成されることができる任意の境界の形状で作用することに注意すべきである。
【００５９】
第１の２つのルーチンは所定の画素のリストへの値の挿入を処理する。リストが今まで存在していなければ、リストが生成される。作業の大きさはＡｄｄＥｎｔｒｙ手順により行われ、この手順は単一のアップ、ダウン、右括弧または左括弧値を１つの画素のリスト中に挿入し、必要なときに先の値を右へシフトする。ＥｎｔｅｒＶａｌｕｅ手順はリストが存在しない場合にエッジ値（アップまたはダウン）を有するリストを作成するためにＡｄｄＥｎｔｒｙを使用し、または存在するリストへその値を付加する。このサンプル構造はリスト中でアップおよびダウンエッジを取消そうとしない。
【数１】
2004516496.tif 000003
【００６０】
ＥｎｔｅｒＶａｌｕｅ手順の目的は、リストが画素で存在するか否かに応じて３つのコード（新しいリスト）または１つのコード（リスト拡張）のいずれかを入力することである。
【数２】
2004516496.tif 000004
【００６１】
ＤｉｓｐｌａｙＦｒａｍｅ手順は拡張されたフレームバッファからイメージを構成する。Ｓｈａｄｅの呼出しは１つの画素に陰影を付けるハードウェアの動作を表している。
【数３】
2004516496.tif 000005
【００６２】
この方式では、“フレーム−バッファ”内のアップおよびダウン状態の順序および位置はイメージされる画素に直接対応しないことに注意すべきである。巻数の変化（およびそれによる陰影の変化）を示す状態は括弧および他のリストにより変位される。ＤｉｓｐｌａｙＦｒａｍｅ手順は実質的な巻数の変化を決定するために各画素のリスト構造を走査する。表示中の画素の反復するアクセスはサンプルアルゴリズムのバリエーションを使用することによって防止されることができる。このアイディアはディスプレイ走査で使用される方向と反対方向にリストを成長させることである。その後、ディスプレイ走査中、最初にリストの末尾に遭遇し、それに続いて全てのリストエレメント、最後にリストの最初に遭遇し、それもそのリストが属す画素をマークする。この方法では、１つの画素に到達するときに、その画素の巻数の変化が知られる。同時に幾つかのリストの中間にあるので、１スタックのような補助データ構造は種々のリストの明細集計を維持するためにＤｉｓｐｌａｙＦｒａｍｅ手順により必要とされる。以下はこの方法に対するＤｉｓｐｌａｙＦｒａｍｅ手順の１例である。リストは走査線を横切ってワープしないことが仮定される。
【数４】
2004516496.tif 000006
【００６３】
種々の実施形態を前述したが、これらは本発明を限定するものではなく、単なる例示として示されていることに注意すべきである。したがって、好ましい実施形態の技術的範囲は前述の任意の例示的な実施形態によって限定されるべきではなく、以下の特許請求の範囲の記載および均等物にしたがってのみ限定される。
【図面の簡単な説明】
【図１】
本発明の１実施形態にしたがった文字圧縮方法を示したフロー図。
【図２】
図１の方法が実行されている代表的なハードウェア環境を示した図。
【図３】
本発明の１実施形態にしたがってフォーマット方法を示したフロー図。
【図４】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図５】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図６】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図７】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図８】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図９】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１０】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１１】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１２】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１３】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１４】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１５】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１６】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１７】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１８】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１９】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図２０】
ゼロではない巻数ルールを使用する例示的なシステムを示した図。
【図１】
2004516496.tif 000007
【図２】
2004516496.tif 000008
【図３】
2004516496.tif 000009
【図４】
2004516496.tif 000010
【図５】
2004516496.tif 000011
【図６】
2004516496.tif 000012
【図７】
2004516496.tif 000013
【図８】
2004516496.tif 000014
【図９】
2004516496.tif 000015
【図１０】
2004516496.tif 000016
【図１１】
2004516496.tif 000017
【図１２】
2004516496.tif 000018
【図１３】
2004516496.tif 000019
【図１４】
2004516496.tif 000020
【図１５】
2004516496.tif 000021
【図１６】
2004516496.tif 000022
【図１７】
2004516496.tif 000023
【図１８】
2004516496.tif 000024
【図１９】
2004516496.tif 000025
【図２０】
2004516496.tif 000026
【国際公開パンフレット】
2004516496.tif 000027
2004516496.tif 000028
2004516496.tif 000029
2004516496.tif 000030
2004516496.tif 000031
2004516496.tif 000032
2004516496.tif 000033
2004516496.tif 000034
2004516496.tif 000035
2004516496.tif 000036
2004516496.tif 000037
2004516496.tif 000038
2004516496.tif 000039
2004516496.tif 000040
2004516496.tif 000041
2004516496.tif 000042
2004516496.tif 000043
2004516496.tif 000044
2004516496.tif 000045
2004516496.tif 000046
2004516496.tif 000047
2004516496.tif 000048
2004516496.tif 000049
2004516496.tif 000050
2004516496.tif 000051
2004516496.tif 000052
2004516496.tif 000053
2004516496.tif 000054
2004516496.tif 000055
2004516496.tif 000056
2004516496.tif 000057
2004516496.tif 000058
2004516496.tif 000059
2004516496.tif 000060
2004516496.tif 000061
2004516496.tif 000062
2004516496.tif 000063
2004516496.tif 000064
2004516496.tif 000065
2004516496.tif 000066
2004516496.tif 000067
【国際調査報告】
2004516496.tif 000068