階層方式でグラフィックスパスシーケンスを符号化及び復号化する方法
【課題】部分復号化及び復号化中の漸進的なレンダリングを可能にするように階層形式でパスを符号化する方法を提供する。
【解決手段】パスは、各々が描画の元の部分に対応する元の描画コマンドの元のシーケンスから構成される。符号化方法は、縮小シーケンスを取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップＥ２３０と、縮小シーケンスを符号化縮小シーケンスに符号化するステップＥ２５０と、縮小シーケンスと元のシーケンスとの間の差分を表す復元情報セットを符号化するステップＥ２６０とを備える。
【解決手段】パスは、各々が描画の元の部分に対応する元の描画コマンドの元のシーケンスから構成される。符号化方法は、縮小シーケンスを取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップＥ２３０と、縮小シーケンスを符号化縮小シーケンスに符号化するステップＥ２５０と、縮小シーケンスと元のシーケンスとの間の差分を表す復元情報セットを符号化するステップＥ２６０とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部分復号化及び復号化中の漸進的なレンダリングを可能にするように階層形式でグラフィックスパスを符号化する方法に関する。
【背景技術】
【０００２】
一般にグラフィックスパスは、ＳＶＧ（「スケーラブルベクターグラフィックス」を意味する）、ＤｒａｗＭＬ又はMicrosoft Silverlight（登録商標）等のグラフィックス記述言語でグラフィック、図形、又は画像を表す。説明する目的で、以下の説明はＳＶＧ規格に注目する。
【０００３】
周知の方法では、ＳＶＧ規格は、ベクトルグラフィックス描画を記述するためにＸＭＬ名前空間として使用可能なスタイル付け可能なグラフィックスに対するＸＭＬ文法である。
【０００４】
ベクトルを使用する方法により、ＳＶＧ画像は精度を損なうことなく任意の所定の解像度でレンダリング可能である。
【０００５】
ＳＶＧは、ＸＭＬ構文を使用して、幾何学的形状、変換、色又はアニメーションを記述する要素及び属性の集合を規定する。例えばＸＭＬ要素は、描画コマンドを規定してもよく、コマンドと関連するパラメータ属性又は座標を含んでもよい。
【０００６】
ＳＶＧにより可能な単純な幾何学的形状は、矩形、円、楕円、線及び多角形である。
【０００７】
より複雑な形状は、特別なツール、すなわちＳＶＧパス及び対応するＸＭＬ要素＜path d="..."＞を使用して描画されてもよい。
【０００８】
ＳＶＧパスは、形状の輪郭を表し、座標（点を規定する）及び半径又は弧フラグ等の描画コマンド及び関連する引数のシーケンスとして書かれる。シーケンスは、線、ベジェ曲線及び／又は弧のような連続した描画部分（各描画部分がコマンドに対応する）から複雑な幾何学的形状を記述する。
【０００９】
形状の輪郭を規定するパスは、ＸＭＬ要素の属性「d」で書かれ、絶対座標又は相対座標を使用して書かれる。相対座標は、パスの先行座標に基づいて書かれる。
【００１０】
描画コマンドは、文字により規定される。大文字は絶対座標の使用を指定し、小文字は相対座標に対応する。大文字及び小文字の双方を使用することにより、絶対座標及び相対座標は同一パス内で併用される。
【００１１】
一例として、以下の２つのパスは同一の複雑な幾何学的形状を表す。第１のパスが絶対座標を含む一方で、第２のパスは相対座標から成る。
【００１２】
M 14.0, 70.9 L14.0, 55.0 L 2.0, 71.0 L14.0, 70.9 Z
m 14.0, 70.9 l 0.0, -15.9 l-12, 16.0 l12.0, -0.1 z
「M」又は「m」は、考慮する新しい幾何学的点を規定する「move-to」描画コマンドである。
【００１３】
「L」又は「l」は、線の終点を指定する線コマンドである。
【００１４】
「Z」は、closepathコマンドであり、パスの最後に処理された点と最初の点との間の直線によりパスの輪郭を閉じる。
【００１５】
「C」又は「c」コマンドは、３次曲線を規定する。「c」コマンドは、図１に示すように６つのパラメータ値を必要とする。(x1, y1)は第１の制御点であり、(x2, y2)は第２の制御点であり、(x, y)は曲線の終点である。曲線の始点は先行コマンドの終点(xe, ye)である。
【００１６】
ＳＶＧ曲線コマンドは、「S／s」平滑化３次曲線コマンド、「Q／q」又は「T／t」２次ベジェコマンド又は「A／a」楕円弧コマンドを更に含む。
【００１７】
本発明は、ＳＶＧタイプのＸＭＬを使用する文書の符号化に関する。
【００１８】
ＸＭＬが文書の構造を記述するための詳細な構文を有するため、ＸＭＬに対する特定の符号化機構は、元のＸＭＬ文書を容易に再構築する能力を維持しつつ、より効率的な形式でＸＭＬ文書の内容を符号化するために調査された。
【００１９】
Fast Inforset形式及びEfficient XML Interchange（ＥＸＩ）形式を含むバイナリＸＭＬ形式が開発された。
【００２０】
これらの２つの形式は、指標テーブルを使用して、内容又は構造的要素の全体ではなく反復内容又は構造的要素の新たな発生頻度を関連する指標で符号化する。ＸＭＬ文書を符号化するためのビットは節約される。一般に、その節約の殆どは構造的情報によるものである。
【００２１】
バイナリＸＭＬ形式がＳＶＧ文書を符号化するために使用可能である一方で、それらの形式の殆どがそのような符号化に圧縮されて適応されない。
【００２２】
これは、ＳＶＧ文書が内容部分と比較して小さな構造的情報の部分を含むためである。
【００２３】
また、これは、大きなＳＶＧ内容が繰り返されることが殆どなく、整数又は浮動小数点等の単純なデータタイプに対する周知のバイナリＸＭＬ符号化の効率が利用されない複雑なタイプのものであるためである。その大きな内容は、例えば単純なグラフィックスコマンドを座標又は値（整数及び浮動小数点の双方）のリストと混合するグラフィックスパスである。
【００２４】
従って、ＳＶＧ文書に対するいくつかの特別なバイナリＸＭＬ符号化形式が開発された。
【００２５】
特に米国特許第６，６２４，７６９号公報から、ＳＶＧパスシーケンスの描画コマンド及び関連する整数の引数を別個に符号化する方法が周知である。
【００２６】
第１に、コマンドはグラフィックスパスにおいて使用されるコマンドのみによるハフマンのような符号により符号化される。従って、使用される符号の数（すなわち、ビット数）は減少される。
【００２７】
第２に、その特許のＳＶＧプロファイルが移動電話専用であるため整数のみである引数は、グラフィックスパスに含まれる任意の引数の符号化を可能にする最小のビット数を使用してバイナリ形式で符号化される。引数は、２つのカテゴリ、すなわち絶対大文字コマンドに属する引数及び相対小文字コマンドに属する引数に分割される。
【００２８】
引数のカテゴリ毎に、そのカテゴリの全ての引数の符号化を可能にする最小のビット数が計算される。その後、各引数は、そのカテゴリに依存して複数のビットを使用して符号化される。
【００２９】
この形式は、あるカテゴリの引数又はコマンドを符号化するのに必要とされる最小数にビット数を調整することにより、ＳＶＧ文書の効率的な圧縮を提供する。
【００３０】
更に米国特許出願公開第２００８／０６３，１１４号明細書から、ＳＶＧ文書の符号化を対象とする簡易シーン記述（ＬＡＳｅＲ）バイナリＸＭＬ形式が周知である。
【００３１】
この出願によると、ＳＶＧパスシーケンスの符号化は、引数を符号化するために２つの方法のうちより適切な方を使用する。
【００３２】
第１の方法は、第１のビット長を使用して最初の２つの引数を符号化し、２つの他のビット長を使用して残りの全ての引数を相対引数として符号化しようとする。第１のビット長は、最初の２つの引数の符号化を可能にする最短のビット長である。２つの他のビット長は同様に算出される。すなわち、第１の他のビット長は、全ての相対的な横座標の符号化を可能にする最短のビット長であり、第２の他のビット長は、全ての相対的な縦座標の符号化を可能にする最短のビット長である。
【００３３】
第２の方法は、第１のビット長を使用して最初の２つの引数を符号化し、指数ゴロム（exponential-Golomb）符号化を使用して全ての更なる引数を相対引数として符号化しようとする。
【００３４】
しかし、これらの２つの出願において開示される解決策はいくつかの欠点を有する。
【００３５】
特に、符号化ＳＶＧ描画のレンダリングは、完全な画像を描画及び表示するためにＳＶＧパスの全ての情報の復号化を必要とする。
【００３６】
ＳＶＧ画像をサムネイル又は小さなレンダリングサイズにレンダリングするために、一般にデータパスの精度が高すぎるため、符号化ＳＶＧデータの処理は時間を浪費する。
【００３７】
従って、適切な圧縮性能を維持しつつ、部分復号化及び／又は漸進的なレンダリング用のＳＶＧ文書等のグラフィックス文書を符号化する方法を提供する必要がある。
【００３８】
ＳＶＧ文書用の別の特定のバイナリＸＭＬ形式は、Expway（www.mitre.org／news／events／xml4bin／pdf／thienot_binary.pdf, slides 53-56）により提示されて開示される。
【００３９】
開示される方法は、座標値の線形量子化を実行し、より少ないビット数、例えば７〜９ビットにわたり後者を符号化する。この提示の例示的な図により示されるように、方法は、パスデータ及びレンダリングされた描画の精度を激減する。
【００４０】
この方法もいくつかの欠点を有する。
【００４１】
Expwayの方法は、元の画像のフル解像度の回復を可能にしない不可逆的圧縮である。
【発明の概要】
【発明が解決しようとする課題】
【００４２】
部分復号化又は漸進的なレンダリングを可能にするグラフィックスパス符号化を有するのが望ましい。
【課題を解決するための手段】
【００４３】
そのために、本発明の目的は、グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンスを含むパスを符号化する方法であって、
−縮小シーケンスを取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップと、
−前記縮小シーケンスを符号化縮小シーケンスに符号化するステップと、
−縮小シーケンスと元のシーケンスとの間の差分（変換の結果として得られる）を表す復元情報セットを符号化するステップとを有する。
【００４４】
この方法は、元のシーケンスを幾何学的に近似する別の「縮小」シーケンスによりパスシーケンスを置換する。
【００４５】
この縮小シーケンスは、対応する画像の低解像度又は小さいサイズのレンダリングを提供するために復号化する際に使用されてもよい。
【００４６】
更に、復号化の時により高い解像度レンダリング又はフル解像度レンダリングが取得されてもよいように、縮小シーケンスから元のシーケンスを復元できるようにする補助「復元」情報セットが符号化される。
【００４７】
従って、方法は可逆的復元又はほぼ可逆的復元を可能にしてもよい。
【００４８】
本発明に係る方法により、画像レンダリングは低解像度レイヤを取得するために元のパスを部分的に復号化することにより取得されてもよい。
【００４９】
更に、漸進的なレンダリングは、より高い解像度レンダリング又はフル解像度レンダリングに向けてレンダリングを向上するために補助情報セット（より高い解像度レイヤ）を更に復号化することにより取得されてもよい。
【００５０】
復号化されたデータの品質が良いほど、レンダリングされた画像の解像度は良い。
【００５１】
後述するように、幾何学的近似は、より少ないビット数又は引数が符号化されることを要求するより単純な描画コマンドを取得するために選択されてもよい。結果として得られる「縮小」パスシーケンスの長さは縮小される。
【００５２】
従って、方法により、低解像度レンダリングを提供するための処理時間が短縮される。基本レイヤのより高速なレンダリングが取得されてもよい。
【００５３】
上述したように、本発明は、図形を表すパスを提供する任意のグラフィックス記述言語に適する。これは、ＳＶＧ規格、並びにＤｒａｗＭＬ及びMicrosoft Silverlightの勧告に例示的に関連する。
【００５４】
本発明の１つの態様によると、描画コマンドは、座標等の描画コマンドタイプ及び引数を含み、前記近似描画コマンドは前記元の描画コマンドより少ない引数を含む。縮小シーケンスのサイズは、低解像度画像のより適切な圧縮及び変換のために激減されてもよい。復号化側において、より高速なレンダリングはより少ないメモリを使用して取得される。
【００５５】
特に近似描画コマンドの少なくとも１つの引数は、元の描画コマンドの引数から算出される。これは、特定の制御点を必要とする２次曲線コマンドを近似する例であってもよい。例えば「近似」引数は、３次ベジェ曲線描画コマンドの元の制御点引数の重心であってもよい。重心の使用は、３次／２次近似に対して適応されており、元の３次パラメータのコンパクトで単純で高速な計算を可能にする。
【００５６】
本発明の別の態様によると、縮小シーケンス内の元の描画コマンドの変換に対応する近似描画コマンドは、近似点描画コマンド、近似線描画コマンド及び近似２次曲線コマンドのうちの１つである。これらの近似コマンドは、殆ど引数を必要としないため効率的な符号化を提供し、より高速なレンダリングを含むコマンドであるため復号器側で高速な画像レンダリングを提供する。
【００５７】
特に幾何学的近似は、ＳＶＧ３次ベジェ曲線コマンドを前記近似点、線又は２次曲線コマンドのうちの１つに変換する。この変換は、ＳＶＧ３次ベジェ曲線コマンドが約６個の引数を必要とし且つ提案された近似コマンドが０、２及び４個の引数をそれぞれ必要とするため、最も効率的な変換である。
【００５８】
別の特定の特徴によると、変換するステップは、元の描画コマンドに対応する描画と近似描画コマンドに対応する描画との間の距離を算出することと、計算した距離を少なくとも１つの閾値と比較することとを含む。この状況において、変換は、近似変換を適用するために潜在的なレンダリング歪み又は変更を基準として直接考慮する。均一にレンダリングされた画像は、画像内の歪みの小さな変化に伴って取得される。
【００５９】
そのような閾値は、復号器において予想されるレンダリング解像度に基づいて計算されてもよい。複数の解像度レイヤを生成するために複数の近似が繰り返し実行されてもよいため、各々が予想された解像度に対応する複数の閾値が使用されてもよい。
【００６０】
特に元の３次曲線コマンドが曲線の各端点に制御ベクトルを含む場合、前記距離は、２つの端点により生成される線に対する垂直線上の２つの制御ベクトルの正射影ノルムを含む。
【００６１】
正射影は、容易に算出される。効率的な指示は、対応する描画が大きく湾曲するか否かに関して取得される。ノルムが大きい程、描画はより大きく湾曲する。従って、近似は、ノルムが閾値と比較して十分に小さい場合に行なわれる。
【００６２】
本発明の１つの特徴によると、前記復元情報セットは：
−種々の近似描画コマンドタイプに変換された元の描画コマンドタイプと、
−近似描画コマンドに保持されていない元の描画コマンドの引数及び／又は元の描画コマンドの引数から計算され且つ近似描画コマンドに保持されていない引数の検索を可能にする引数とを含む。
【００６３】
この復元情報セットにより、元のデータの復元（可逆的圧縮）が可能になる。元のデータを復元情報セット及び縮小シーケンスに分割することにより、データは種々の解像度レイヤに符号化されてもよい。
【００６４】
本発明の別の特徴によると、符号化方法は、幾何学的近似に従う近似変換を含む元のシーケンスの複数の反復変換を含み、
最後の変換の結果として得られる縮小シーケンスが符号化され、変換の復元情報セットのうちの少なくとも１つが符号化される。
【００６５】
「反復変換」は、１つの変換の結果として得られるシーケンスが次の変換の入力であることを意味するものとして理解される。複数の符号化レイヤが取得され、復号化側における種々の解像度レンダリング可能性を可能にする。漸進的なレンダリングが可能である。
【００６６】
特に復元情報セットの各々が符号化される。可逆的符号化が取得される。
【００６７】
しかし、制限された数の復元情報セットが符号化されてもよく、それにより不可逆的符号化が提供される。制限された数は、利用可能なネットワーク帯域幅等の動的な条件に基づいて判定されてもよい。この提供により、補助復元情報セットの前に最も重要な情報がまず送出される。
【００６８】
特定の特徴によると、前記近似変換の前の変換は、元のパスシーケンスを全ての絶対値又は全ての相対値に書き換えることを含む。パスシーケンス中の座標は、より適切な符号化に対してより均一である。
【００６９】
あるいは、又は組み合わせて、前記近似変換の前の変換は、より少ない引数を有する同等の描画コマンドにより描画コマンドを置換することにより元のパスシーケンスを書き換えることを含む。このように、シーケンスの長さは縮小される。
【００７０】
処理する更に単純なパスシーケンスが取得される。近似変換と同様に、書き換えられたシーケンスから元のパスシーケンスを復元できるようにする差分を含む復元情報セットが生成されても良い（その後、格納及び符号化される）。
【００７１】
別の特定の特徴によると、前記近似変換の前の変換は、サブサンプリングシーケンス及びサブサンプリングシーケンスから元のシーケンス又は書き換えられたシーケンスの復元を可能にするスーパーサンプリング情報を含む復元情報セットを取得するために、元のシーケンス又は書き換えられたシーケンスをサブサンプリングするステップを含む。この提供により、近似変換は、制限された数の可能なデータに対して実行され、それらのデータは制限されたビット数にわたり処理される。このように、処理は容易になる。
【００７２】
別の特定の特徴によると、各変換ステップは、先入れ後出し（ＦＩＬＯ）メモリに復元情報セットを格納することを含む。従って、復元セットが生成された順序と逆の順序で復元セットを符号化することは単純化される。符号化する際のそのような逆の順序により、復号化側における高速且つ効率的な漸進的な画像レンダリングは可能になる。
【００７３】
特定の一実施形態によると、複数の復元情報セット及び最終的な縮小シーケンスを取得するために、いくつかの近似変換が縮小シーケンスに対して繰り返され、
複数の復元情報セット及び最終的な縮小シーケンスは、種々の画像解像度の複数の符号化レイヤを生成するために符号化される。
【００７４】
本発明の別の態様によると、前記縮小シーケンスは、任意の復元情報セットの前に最初に符号化される。これにより、復号化側において低解像度レンダリングが迅速に取得可能であることが保証される。特に復元情報セットは、生成された順序と逆の順序でセットを符号化するように、上述のＦＩＬＯメモリから検索されてもよい。
【００７５】
本発明の別の態様によると、縮小シーケンスは、前記縮小シーケンス内のコマンドの引数に対応する値のシーケンスを含み、
縮小シーケンスの第１の座標の値は絶対値として線形符号化され、他方の座標の値はシーケンス内の先行座標の値に対して符号化される。
【００７６】
一般に相対値が絶対値より小さいため、縮小シーケンスのよりコンパクトな符号化表現が取得されてもよい。
【００７７】
特定の特徴によると、復元情報セット内の座標の値はそのセット内及び先行符号化縮小シーケンス又は復元情報セット内の先行座標の値に対して符号化される。ここでも、この提供により、復元セットのよりコンパクトな符号化表現が取得されてもよい。
【００７８】
更に本発明は、グラフィックス記述言語で図形を表す符号化データを復号化する方法であって：
−近似描画コマンドのグラフィックスパスシーケンスを取得するために符号化データから第１のシーケンスを受信し且つ復号化するステップと、
−符号化データの新しいレイヤが復号化される必要があるかを判定するステップと、
−肯定的な判定の場合に、
・ 符号化データから新しいレイヤに対応する情報セットを受信及び復号化し、
・ アップグレードされたパスシーケンスを取得するために、復号化情報セットに基づいて復号化グラフィックスパスシーケンスの少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換するステップとから成る方法に関する。
【００７９】
符号化方法と関連して、変換は一般により複雑な描画を提供する幾何学的変換である。
【００８０】
本発明の１つの態様によると、情報セットを受信及び復号化するステップ及び変換するステップは、符号化データの新しいレイヤが復号化される必要がある限り前記アップグレードされたパスシーケンスに対して繰り返される。元のパスシーケンスを漸進的に復元するための各レイヤの漸進的な復号化が達成される。
【００８１】
１つの特徴によると、方法は、アップグレードされたパスシーケンスに対応するレンダリング描画を平滑化するために予測を使用して前記アップグレードされたパスシーケンスを後処理することを更に含む。そのような後処理は、復号化される必要がある更なるレイヤがない場合（すなわち、否定的な判定の場合）に行なわれる。このように、視覚的により快適なレンダリングが達成される。
【００８２】
一実施形態によると、方法は、否定的な判定である場合、
−変換シーケンスを取得するために、少なくとも１つの近似描画コマンドを前記グラフィックス記述言語のパス描画コマンドに変換するか又は前記近似描画コマンドを除去することと、
−変換シーケンスに基づいて画像をレンダリングすることとを含む。
【００８３】
特に前記近似描画コマンドの除去は、前記近似描画コマンドが点コマンドに対応する場合に実行される。
【００８４】
これに対応し、本発明は、グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンスを含むパスを符号化する装置であって：
−縮小シーケンスを取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換する変換手段と、
−前記縮小シーケンスを符号化縮小シーケンスに符号化し且つ縮小シーケンスと元のシーケンスとの間の差分を表す復元情報セットを符号化する符号化手段とを具備する装置に関する。
【００８５】
オプションとして、装置は上述した符号化方法の特徴に関連する手段を含んでもよい。
【００８６】
これに関連して、本発明は、グラフィックス記述言語で図形を表す符号化データを復号化する装置であって：
−近似描画コマンドのグラフィックスパスシーケンスを取得するために、符号化データから第１のシーケンスを受信する受信手段及び前記第１のシーケンスを復号化する復号化手段と、
−符号化データの新しいレイヤが復号化される必要があるかを判定する判定手段と、
−肯定的な判定の場合に、符号化データから新しいレイヤに対応する情報セットを受信及び復号化する手段と、
−アップグレードされたパスシーケンスを取得するために、復号化情報セットに基づいて復号化グラフィックスパスシーケンスの少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換する変換手段とを具備する装置に関する。
【００８７】
オプションとして、装置は上述の復号化方法の特徴に関連する手段を含んでもよい。
【００８８】
コンピュータシステムにより読み出し可能である情報記憶手段は、コンピュータシステムによりロード及び実行された時に本発明に係る符号化又は復号化方法を実現するように構成されるコンピュータプログラムの命令を含む。
【００８９】
マイクロプロセッサにより読み出し可能なコンピュータプログラムは、マイクロプロセッサによりロード及び実行された時に本発明に係る符号化又は復号化方法を実現するように構成されるソフトウェアコードの部分を含む。
【００９０】
コンピュータプログラム及び情報記憶手段は、それらが実現する方法と同様の特徴及び利点を有する。
【図面の簡単な説明】
【００９１】
本発明の追加の利点及び特徴は、添付の図面を参照し、単なる例として示される以下の説明を読むことにより明らかとなるだろう。
【図１】図１は、ＳＶＧ規格に従って３次曲線コマンドのパラメータ化を示す図である。
【図２】図２は、ＳＶＧパスシーケンスを含むＳＶＧ文書の例示的な抜粋を示す図である。
【図３】図３は、本発明に係る符号化方法の一般的なステップを示すフローチャートである。
【図４】図４は、本発明に係る符号化方法の詳細な一実施形態を示すフローチャートである。
【図４ａ】図４ａは、本発明に従う縮小データセット及び復元セットの構築、並びにその符号化を示す図である。
【図５】図５は、図４の処理において実現される座標値の絶対表現に対するサブサンプリングを示すフローチャートである。
【図６】図６は、図１に示すような３次曲線に対する例示的な近似処理を示すフローチャートである。
【図７】図７は、本発明に係る復号化処理を示すフローチャートである。
【図８】図８は、本発明に係る方法の一実現例に対して適応される情報処理装置の特定のハードウェア構成を概略的に示す図である。
【発明を実施するための形態】
【００９２】
最初に、図２に示す例示的なＳＶＧ文書１に基づいて本発明を説明する。
【００９３】
ＳＶＧ文書１は、「path」タイプのＳＶＧ要素を含む。その属性「d」は元のパスシーケンス１０を規定する。
【００９４】
パスは、「C」描画コマンドにより規定される７つの３次ベジェ曲線からなる閉曲線である。最後の「z」コマンドは、「M」コマンドにおいて第１の点のセットを含む描画を閉じる。
【００９５】
本発明によると、このＳＶＧパスの符号化は、
−縮小シーケンスを取得するために描画の対応する元の部分（ＳＶＧパスにより表される図形の一部分）の幾何学的近似に従って、少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップと、
−前記縮小シーケンスを符号化縮小シーケンスに符号化するステップと、
−縮小シーケンスと元のシーケンスとの間の差分を表す復元情報セットを符号化するステップとを含む。
【００９６】
符号器は、図２のパスシーケンスを構文解析し、整数、各々がタイプ（又は名前）及び整数値（コマンド毎の整数値の数はＳＶＧ規格により規定される）を有するコマンドのリスト、並びに引数の値、ここでは座標のみ（横座標及び縦座標の対）を処理するように１０，０００の変倍因子を判定する。
【００９７】
構文解析された情報は以下の通りである。
【００９８】
−パラメータ：変倍因子＝１０，０００
−コマンドタイプシーケンス：MCCCCCCCz
−値シーケンス：1657142, 3809336, 1540972, 3121730, 1671473, 2680800, 1857142, 2295050, 2160130, 1825486, 2516866, 1872163, 2904285, 1923621, 2904285, 1913621, 2914285, 1913621, 2914285, 1903621, 2914285, 1903621, 2924285, 1903621, 2924285, 1903621, 3353836, 2072530, 3773967, 2236000, 3914285, 2609336, 3948959, 3146579, 4274470, 3351436, 3828571, 4437907, 3003143, 5074644, 1724985, 6172611, 1657142, 3809336
符号化する値を減少することを目的とする第１のステップにおいて、符号器は、データセットに対してサブサンプリング変換を適用する。２つのデータセット、すなわちサブサンプリングデータ及びサブサンプリング値からもとの値の復元を可能にするスーパーサンプリングデータが取得される。
【００９９】
サブサンプリング変換は、例えば変倍因子に従って規定される。
【０１００】
本発明の例において、１２ビットのサブサンプリングが使用される。しかし、読みやすくするために、ベース１０のサブサンプリングを仮定し、取得される第１のサンプリングデータセットは、Set A (11): 165, 380, 154, 312, 167, 268, 185, 229, 216, 182, 253, 187, 290, 192, 290, 191, 291, 191, 291, 190, 291, 190, 292, 190, 292, 190, 335, 207, 377, 223, 391, 260, 394, 314, 427, 335, 382, 443, 300, 507, 172, 617, 165, 380である。
【０１０１】
第２のデータセットは、Set B (12): 7142, 9336, 972, 1730, 1473, 800, 7142, 5050, 130, 5486, 6866, 2163, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 3836, 2530, 3967, 6000, 4285, 9336, 8959, 6579, 4470, 1436, 8571, 7907, 3143, 4644, 4985, 2611, 7142, 9336である。
【０１０２】
第１のステップは、元のパスシーケンス１０の第１の近似（コマンドシーケンス＋Set A 11）を提供する。
【０１０３】
描画コマンドをより単純なコマンドに変換することを目的とする第２のステップにおいて、符号器は、コマンド「C」により規定される３次ベジェ曲線が線として近似されるか又は他の単純なコマンドであるかをテストする。
【０１０４】
３次ベジェ曲線と近似線（曲線の２つの端点により規定される）との間の数学的距離が算出され、近似決定に対する主な基準としての役割を果たす。以下の表１は、そのような計算の結果を一覧表示し、後で規定されるような２つの距離（図６の説明を参照）は曲線毎に算出されている。
【０１０５】
【表１】
【０１０６】
本発明において使用される近似コマンドは、ＳＶＧ描画コマンド又は拡張描画コマンドであってもよい。更に、特定の「点」コマンド（「aP」）は、開始点に非常に近接する終点に対応する近似コマンドを指定するために使用されてもよい。
【０１０７】
尚、元のコマンドを置換するのに使用される近似コマンドは、より少ない引数を必要とする。すなわち、点コマンドは座標を必要とせず、線コマンドは１つの座標（すなわち、横座標及び縦座標）を必要とし、２次曲線コマンドは２つの座標を必要とし、その一方で元の３次ベジェ曲線「C」コマンドは３つの座標を必要とする。
【０１０８】
表に示すように、距離が十分に短い場合、曲線は線として近似される。距離がほぼゼロである場合、曲線の終点は、曲線が点として近似されるように開始点に非常に近接する。距離がほぼゼロでない場合、曲線は２次曲線として近似される。「点」コマンドは引数を有さない。
【０１０９】
上記テーブルの近似方法のセットに従って、２つのデータ（又は情報）セットはSet A 11から生成される。
【０１１０】
−近似の後に結果として得られる引数を含む第１のセット、すなわちSet A1(13)。線として近似された曲線の端部の座標を含み、点として近似された曲線に対しては座標を含まず、２次曲線として近似されたコマンドに対して２つの座標を含む（例えば重心である元の曲線コマンドの２つの元の制御点から算出されてもよく且つ以下に下線を引いた太字で示される曲線の端部の座標及び制御点）：
【０１１１】
【数１】
【０１１２】
−Set A1において選択されなかった全ての座標及び以下に下線を引いた太字で示される２次曲線として近似された各曲線に対する１つの制御点の座標を含む第２のセット、すなわちSet A2(14)（第２の元の制御点を検索する為に、上記の重心と共に用いても良い）：
【０１１３】
【数２】
【０１１４】
同時に、コマンドタイプの変換に関する情報はメモリに格納されてもよい。例えば第１の「C」コマンドタイプは「aL」線コマンドタイプにより置換されているか、あるいは第３の「C」コマンドタイプは「aP」線コマンドタイプにより置換されている。例えば、近似コマンドタイプシーケンスMaLaLaPaPaLaLaQzは、元のシーケンスMCCCCCCCzに加えて格納されてもよい。
【０１１５】
この第２のステップに従って、結果として、Set A1、Set A2及びSet Bが近似コマンドタイプシーケンスにより生成された。Set A1は、元のシーケンスと比較して少ないデータを含むが、最も重要なデータを保持する。そのデータは、近似コマンドタイプシーケンスと組み合わせると、近似ＳＶＧパスに対応する。
【０１１６】
Set A1 + A2により、ＳＶＧパスの中間サイズの解像度のバージョンの復元が可能になる。例において、全ての近似コマンドタイプが元の「C」コマンドタイプに対応する一方で、必要に応じて、後述するように、元のタイプが近似タイプから検索される方法を指定する情報の追加の項目はSet A2と関連付けられてもよい。
【０１１７】
Set A1 + A2 + Bにより、ＳＶＧパスのフル解像度レンダリングが可能になる。
【０１１８】
第３のステップにおいて、変倍因子等の符号化パラメータが符号化される。次に、取得された情報セットは、階層符号化方式を使用して符号化される。これは、低解像度の情報セット（ここでは、Set A1）が最初に符号化され、その後このセットに付加される情報（Set A2）がより高い解像度の符号化画像を取得するために符号化され、これは全てのセット（A1、A2及びB）が符号化されるまで継続する。
【０１１９】
例えば、コマンドタイプが最初に符号化される。ここで、２つの実現例が使用されてもよい。
【０１２０】
−全てのコマンドタイプがSet A1の前に直接符号化される（「近似された線、曲線」のような拡張タイプを含む。
【０１２１】
−コマンドタイプの符号化は、２つの部分、すなわちSet A1の符号化の前及び後に分割される。Set A1が制約されるコマンドタイプのセット（点、線、２次曲線、移動、閉じる）を使用するため、これらの制約されるコマンドタイプはSet A1の前に符号化される。例えば、シーケンスMaLaLaPaPaLaLaQzが最初に符号化される。Set A1の符号化後、コマンドタイプの変換に関する情報であり、制約されるセットから元のＳＶＧコマンドセットにする必要がある情報は符号化される（点は何になってもよく、線は曲線になってもよく、２次曲線は３次曲線になってもよい）。例えば、シーケンスMCCCCCCCzが符号化される。
【０１２２】
しかし、元のコマンドの復元を可能にするこの情報の任意の他の表現が使用されてもよい。
【０１２３】
引数（ここでは座標）が処理される。最初にSet A1を符号化し、次にSet A2及びBを符号化する。
【０１２４】
Set A1の各座標は、相対的なSet A1: 165, 380, 20, -151, 105, -37, 101, -30, -9, 183, -24, 119, -71, -182を取得するために、最初に先行する座標に対して算出される。
【０１２５】
同様に、Set A2の値は、Set A1及びSet A2から最も近接する既に符号化された値に従って算出される。その結果、相対的なSet A2: -11, -68, 13, -44, 31, -47, -37, -5, 37, 4, 1, -1, 0, -1, 0, 0, 1, 0, 0, 0, 43, 17, 42, 18, 3, 54, 31, 21, -7, 64が得られる。
【０１２６】
この例から分かるように、相対値は絶対値より小さい傾向がある。これにより、潜在的によりコンパクトな符号化表現が可能になる。
【０１２７】
相対的なSet A1は、残りの値とは非常に異なる大きさを有するために線形符号化される最初の２つの値を除いて、指数ゴロム符号化方式を使用して符号化される。
【０１２８】
指数ゴロム符号は、パラメータkによりパラメータ化されるユニバーサル符号のタイプであり、任意の大きさの整数の符号化を可能にする。符号は、以下のように実現される。
【０１２９】
１）整数Iが正である場合、J=2*Iを算出する。そうでない場合、J=1-2*Iを算出する。
【０１３０】
２）（2^kにより除算されるJ）のバイナリ表現のビットサイズと同数の０ビットを書く。
【０１３１】
３）「1」ビットを書く。
【０１３２】
４）Jのバイナリ表現の最後のkビットを書く。
【０１３３】
指数ゴロム符号のパラメータkは、幾何学的分布パラメータの標準的な推定により推定される。以下の例において、kは７に設定される。
【０１３４】
Set A1は、近似コマンドタイプシーケンスと共に図２の図中符号１３により示される基本レイヤセットを形成する。
【０１３５】
同様に、相対的なSet A2の全体は、例えば５に等しいパラメータkにより指数ゴロム符号化方式を使用して符号化される。
【０１３６】
Set A2は、元のコマンドタイプシーケンス（又は近似タイプからの元のコマンドタイプの復元を可能にする任意の他の情報）と共に図２の図中符号１４により示される復元高解像度レイヤセットを形成する。
【０１３７】
Set Bの全ての値がサブサンプリングパラメータの２乗により制限されるため、Set Bは、線形符号化を使用して符号化される。
【０１３８】
Set Bは、図２の図中符号１２により示される復元フル解像度レイヤセットを形成する。
【０１３９】
本明細書において、ＳＶＧ文書１のパス要素の符号化を説明した。他の要素の符号化は、従来技術の方法により実行される。
【０１４０】
同様に、本発明は複数のパスを含むＳＶＧ文書にも適用される。そのような場合、幾何学的変換を適用するステップ及び変換された縮小シーケンスを符号化するステップが各パスに適用される。従って、文書に対応する符号化データの第１のレイヤが形成される。次に、パス毎に生成される復元情報セットが符号化され、補助レイヤを作成する。このように、階層復号化が容易にされる。
【０１４１】
次に、そのような符号化ＳＶＧ文書の復号化、特に符号化ＳＶＧパス要素の復号化について簡単に説明する。
【０１４２】
そのような復号化方法は、
−近似描画コマンドのＳＶＧパスシーケンスを取得するために符号化ＳＶＧデータから第１のシーケンスを受信及び復号化することと、
−符号化データの新しいレイヤが復号化される必要があるかを判定することと、
−判定が肯定的である場合、符号化ＳＶＧデータから新しいレイヤに対応する情報セットを受信及び復号化することと、
−アップグレードされたパスシーケンスを取得するために、復号化情報セットに基づいて復号化シーケンスの少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換することとを含む。
【０１４３】
更に詳細に考慮すると、復号器は、変倍因子及び選択された符号化オプションを指定する任意のフラグ等のパラメータを復号化し、その後、オプション１（最初に全てのコマンドタイプ情報を取得する）に従うか又はオプション２（レイヤ毎にコマンドタイプを段階的に取得する）を使用してコマンドタイプを復号化することにより開始する。
【０１４４】
基本レイヤ（又は低解像度レイヤ）の復号化は、初期座標を線形復号化することにより開始する。基本レイヤは、指数ゴロム技術を使用して全ての基本レイヤの値を復号化する。このレイヤの復号化の終了時、復号器は相対的なSet A1全体を復号化しており、元のSet A1を復元できる。
【０１４５】
処理時間又はデータの不足により阻止される場合、あるいは低解像度のみが予想される場合、復号器はこの段階において復号化を停止することを決定できる。この場合、新しいレイヤを復号化する上記判定が否定的である場合、処理は、
−少なくとも１つの近似描画コマンドをＳＶＧパス描画コマンドに変換するか又は変換シーケンスを取得するために前記近似描画コマンドを除去することと、
−変換シーケンスに基づいてＳＶＧ画像をレンダリングすることとを含む。
【０１４６】
この点に関して、復号器は以下のように復号化データを更新する必要がある。
【０１４７】
−復号化シーケンスMaLaLaPaPaLaLaQzの近似点「aP」は、データから削除されるか、又は長さがゼロの曲線に変換される。
【０１４８】
−近似線「aL」は、例えばＳＶＧ「L」コマンドを使用して標準的なＳＶＧ線に変換される。近似された２次曲線「aQ」は、標準的なＳＶＧ２次曲線「Q」コマンドに変換される。
【０１４９】
−値は、個々にスーパーサンプリングされるか又は元の値の大きさを回復するためにグローバル変倍因子を使用してスーパーサンプリングされる。
【０１５０】
−レンダリングの高度化に関連して後述されるようにレンダリング品質を向上するために、追加の後処理が実行される。
【０１５１】
復号器が復号化を継続することを決定した場合、復号器は符号化文書における次の符号化レイヤ１４（中間解像度レイヤ又は高解像度レイヤ）を復号化する。
【０１５２】
符号化オプションに依存して、復号器は、例えばシーケンスMCCCCCCCzである追加のコマンドタイプ情報を復号化してもよい。その後復号器は、相対的なSet A2を取得するために指数ゴロム符号化された値を復号化する。
【０１５３】
値のSet A2は復元され、Set Aのサブサンプリングされた元のＳＶＧ座標の算出が可能になる。
【０１５４】
Set Aの解像度が十分である場合、復号器は復号化を停止する。復号器は、例えばグローバル変倍因子を使用して復号化値のスーパーサンプリングを実行する。コマンドタイプシーケンスMCCCCCCCz及びSet Aの値により、従来の方法による高解像度レンダリングが可能になる。
【０１５５】
レンダリング品質を向上するために、追加の後処理が実行可能である。
【０１５６】
ＳＶＧパスのフル解像度が望ましい場合、復号器は継続してSet Bの値（上位レイヤ又はフル解像度レイヤ１２）を復号化する。
【０１５７】
後者は、Set Aから元のＳＶＧパス値を直接復元することを可能にする。
【０１５８】
尚、この段階において、メモリ消費を低減するために最適化技術が使用されてもよい。基本レイヤのみが復号化される場合、メモリの割当てはSet A1の値の正確な数に低減される。これに対して、追加のレイヤが復号化される場合、単一の値バッファが割り当てられ、復号化中に漸進的に満たされる。
【０１５９】
上記例から、本発明を実現する符号器は、レイヤ１２、１３、１４を結合することによりデータセットの品質が向上されることを可能にする最終的なデータセット及びいくつかの追加のデータセットを与える元のＳＶＧパスに対していくつかの連続変換を適用することが分かる。それらの変換のうちの１つは、一般により少ない引数を有し、従ってパスの低解像度レンダリングを認識するために値の数を減少する近似変換である。
【０１６０】
レンダリングするのが非常に高速なコマンドのみ、殆どの場合は点コマンド（この場合、ＳＶＧコマンドは処理されない）又は線コマンドを使用することによりレンダリング処理を更に容易にしてもよい。
【０１６１】
更に、圧縮全体が最適な利用可能なＳＶＧコーデックとほぼ同等に適切なままであるように、特定の連続した変換及び特定の符号化が縮小データセット及び全ての補助データ（又は復元情報セット）に対して提供される。
【０１６２】
復号化側において、復号器は、予想されるレンダリング品質、データの可用性、処理能力又はメモリパワーに基づいて符号化セットの一部を選択的に復号化してもよい。復号器は、低解像度レンダリングを含む部分復号化、並びに復号化処理中にパスレンダリングをリフレッシュする場合は漸進的なレンダリングを提供してもよい。
【０１６３】
本発明の一実施形態について、図３〜図７を参照して説明する。
【０１６４】
図３は、本発明に係る符号化方法の一実施形態の一般的なステップを示すフローチャートである。
【０１６５】
符号化方法は、以下に例示的に詳細を示すような順序付けされた変換のセットを使用する。
【０１６６】
それらの変換の各々は、入力データから２つのデータセット、すなわち縮小データセット及び復元情報セットを生成する。
【０１６７】
縮小データセットは、入力データの近似である。これは、より小さい固有のサイズを有し且つ／又は効率的な符号化に適する。一般に、ＳＶＧパスシーケンスを考慮すると、縮小データ又は縮小シーケンスセットは、コマンドタイプのリスト（一般に、変換の出力における可能なタイプの数は入力より少ない）及び一般に整数として格納される値のリストを含む。
【０１６８】
復元情報セットは、縮小データセットから元のデータセットを算出するために逆変換により使用される。復元情報セットは、縮小データセット及び値（整数として格納される）又は追加の情報（特定のコマンドが絶対的であるか又は相対的であるか等）セットのコマンド毎に使用されるべき逆変換を表す情報セットを含んでもよい。全ての値は、周知の最大値を有する整数として格納されてもよい。
【０１６９】
符号器は、ＳＶＧパスに変換のセットを繰り返し適用する。
【０１７０】
各変換に対して、符号器は復元情報セットを格納し、縮小データセットを次の変換への入力として使用する。
【０１７１】
最後の変換が完了した後、符号器は最初に最終的な縮小データセットを符号化する。
【０１７２】
符号器のセットアップ（可逆的圧縮、符号化ファイルの対象サイズ等）に依存して、符号器は変換により生成された復元情報セットの一部を更に符号化してもよい。
【０１７３】
全ての復元情報セットが符号化される場合、符号化は可逆的である。従って、生成されたレイヤは(n+1)個存在する。nは変換の数である。
【０１７４】
そのような符号化の場合、図３を参照すると、処理はステップＥ１００において符号化するＳＶＧパスデータセット（又はシーケンス）を検索することにより開始する。
【０１７５】
ステップＥ１１０において、変換がデータセットに適用される必要があるかがチェックされる。
【０１７６】
変換がデータセットに適用される必要がある場合、ステップＥ１２０において変換が適用される。変換は、ステップＥ１１０の次の繰り返しに対する新しいデータセットとなる縮小データセットを生成する。変換は、幾何学的近似に従ってデータセットの元の描画コマンドを近似描画コマンドに変換することを含む。対応する復元情報セットは、ＦＩＬＯ（先入れ後出し）スタックに格納される。
【０１７７】
全ての変換が適用された（ステップＥ１１０の出口「ｎｏ」）場合、ステップＥ１３０において、縮小データセット又は縮小シーケンスである最終的なデータセットが符号化される。
【０１７８】
その後、ＦＩＬＯスタックに格納される一部の復元情報セット又は各復元情報セットは、順次符号化され、符号化後にスタックから除去され（ステップＥ１４０及びステップＥ１５０）、処理は終了する（ステップＥ１６０）。
【０１７９】
結果として得られる符号化文書において、第１のレイヤ（又は基本レイヤ）は縮小データであり、他のレイヤは、変換により生成された各復元情報セットであり、生成された順序と逆の順序で格納される。
【０１８０】
不可逆的圧縮が許可される場合、符号化処理は、全てのスタック項目が符号化される前（例えば、所定の数のスタック項目の符号化の後又は最小誤り距離のような基準が満たされた時）に停止してもよい。
【０１８１】
効率的な符号化を提供するために、本発明の１つの変換は、後で更に詳細に説明するようにＳＶＧコマンドを近似コマンドに変換する近似変換である。
【０１８２】
書き換え変換及び／又は量子化変換等の他の変換は、殆どの場合に有用であるが、種々の例において、例えばデータが既に低解像度データである場合においてオプションであってもよい。
【０１８３】
図４を参照して、本発明に係る符号化方法の詳細な一実施形態を説明する。本実施形態において、符号器は以下の順番で３つの変換を適用する。
【０１８４】
−ＳＶＧパスを全ての絶対値又は全ての相対値に変換するＳＶＧパスを簡略化するための書き換え変換
−データを低解像度データ及び高解像度データに分割するための量子化又はサブサンプリング変換であり、一般には線形変換
−低解像度データを２つの追加のレイヤ、すなわち更に低い解像度のデータセット及び復元（更に高い解像度に対する）情報セットに分割するための近似変換
図４の第１のステップＥ２００において、符号化するＳＶＧパス２０が取得される。
【０１８５】
ステップＥ２１０において、オプションとしてパスデータは書き換えられ、より簡略化され且つ同等にレンダリングされるＳＶＧパスのバージョンを得る。２つの書き換え動作は、組み合わせて実行されてもよく又はいずれか一方が実行されてもよい。
【０１８６】
第１の書き換え動作は、ＳＶＧパスシーケンスの全ての値を相対値のみ又は絶対値のみに書き換えることに関係する。
【０１８７】
例えば全ての座標の値を相対値として書き換える場合、このステップは、大文字のコマンドタイプ名を小文字のコマンドタイプ名で置換することにより、例えば「C」を「c」にすることにより、最初にコマンドタイプ名を更新することを含む。
【０１８８】
第２に、全ての絶対座標は、それらの絶対座標及びＳＶＧパスの先行座標から算出される相対座標により置換される。例えばパス「M 100 100 L 200 150 L 100 150 L 100 100」は、相対パス「m 100 100 l 100 50 l -100 0 l 0 -50」により置換される。
【０１８９】
これは、使用されるコマンド数を減少するという第１の利点を有する。更に一般に、相対座標の値は対応する絶対座標の値より小さい。また、全ての座標がより均一である。
【０１９０】
尚、ＳＶＧ仕様書によると、第１のパスコマンドが相対パスコマンドである場合、絶対コマンドとして解釈される。これにより、前処理ステップは、全てのコマンド、最初のコマンドであっても書き換えが行なえる。
【０１９１】
第２の書き換え動作は、パス中の各コマンドに対して最適なコマンド形式を使用することである。いくつかのコマンドは、特定の例に対してショートカットを有する。例えば「lineto」コマンドは、線が水平（又は垂直）である場合に「horizontal-lineto」（又は「vertical-lineto」）ショートカットを有する。この書き換え方式を適用することにより、コマンド「l 5 0」は、情報がより少ない同等のコマンド「h 5」により置換される。従って、同等のコマンドは同一の図の結果を生成するコマンドとして理解される。
【０１９２】
各例に対して最も固有のコマンドを使用することにより、元のパス中の引数の数が減少される。
【０１９３】
このステップＥ２１０の書き換え変換は、書き換えられたＳＶＧパス２１及び書き換えられた形式から元の形式にすることを可能にする復元情報２２を生成する。それらのパス及び情報は、次の処理ステップのためにメモリに格納される。一般にこの追加の情報は、相対的であるか又は絶対的であるかを指定する各コマンドに対するブール値から構成されてもよい。h又はvコマンドの場合、元々hコマンドであるか、vコマンドであるか又はlコマンドであるかを指定できる。
【０１９４】
算術符号化技術又は同様の技術は、この種のデータを圧縮するために使用されてもよい。効率的な一実現例において、全ての値は絶対値として書き換えられ、パスデータサブサンプリング変換を容易にする。
【０１９５】
ステップＥ２１０に続き、ステップＥ２２０において、書き換えられたパス値はサブサンプリングされる。そのために、上述したように、ＳＶＧパスは構文解析され、パラメータ、コマンドタイプシーケンス（全てのパスコマンドのセット）及び引数値を別個に一覧表示するように再構成される。
【０１９６】
図５は、座標値の絶対表現に対するサブサンプリングを示す。より効率的にするために、上述したように、ステップＥ２１０において座標の値のみがサブサンプリングされる。半径又は軸等の他の引数は実際には符号化される。しかし、特定の一実施形態において、これらの他の引数もサブサンプリングされてもよい。
【０１９７】
実質的な視覚的なアーチファクトをもたらす付加的な丸め雑音を含まないようにするために、絶対表現が使用される。
【０１９８】
サブサンプリングパラメータを仮定すると（ステップＥ３００）、処理する値が存在する限り（ステップＥ３１０）、ステップＥ３２０において、その絶対値が検索される（又は相対値として利用可能である場合は算出される）。
【０１９９】
ステップＥ３３０において、この絶対値は、サブサンプリング因子に従って量子化され、絶対サブサンプリング値を得る。
【０２００】
サブサンプリング値から元の値を得ることを可能にするスーパーサンプリング情報（これは、実際には元の値とサブサンプリング値又は量子化値との間の差分である）は、ステップＥ３４０において算出及び格納される。相対サブサンプリング値は、ステップＥ３５０において算出及び格納される。
【０２０１】
処理される必要がある値が更に存在しない場合、処理はステップＥ３６０において終了する。
【０２０２】
ステップＥ２２０の結果として、全ての値のセットが２つのセット、すなわちコマンドタイプシーケンスと組み合わされる場合に低解像度データセット２３及びスーパーサンプリング情報２４に対応するサブサンプリングされた相対座標値又は絶対座標値に分割される。後者、すなわち復元情報セットにより、低解像度から元の値又は元の値に非常に近い値を得ることが可能になる。
【０２０３】
更なるセットが予想される場合、同一の処理が繰り返される。
【０２０４】
ステップＥ２２０に続き、ステップＥ２３０において、パスコマンドはそれらのタイプ及び値に従って近似される。
【０２０５】
本発明の一実施形態において、図６を参照すると、分類はコマンドを３つの潜在的な「近似」タイプ、すなわち点、線及び２次曲線として近似することから成る。
【０２０６】
これらの３つの潜在的な「近似」コマンドタイプのうちの１つにおける図１に示す３次曲線の近似について以下に説明する。
【０２０７】
本発明はこの近似に限定されないことが理解される。説明するために、任意のＳＶＧコマンドは、より少ない引数を使用するＳＶＧコマンド又は点近似コマンドに近似されてもよい。例えば、線コマンドは点コマンドに近似され、２次曲線コマンドは線又は点コマンドに近似され、弧曲線コマンドは２次曲線、線又は点コマンドに近似される。
【０２０８】
しかし、コマンドタイプ「M／m」及び「Z／z」は近似されず、ステップＥ２３０の結果として得られる近似コマンドタイプを一覧表示することを目的とする近似コマンドタイプシーケンスに追加される。
【０２０９】
点、線又は２次曲線等のより単純なコマンドへの３次ベジェ曲線コマンドの幾何学的近似に戻ると、この近似は以下のことを可能にする。
【０２１０】
−近似コマンドの値の数を減少する。
【０２１１】
−近似コマンドのレンダリングを簡略化する。
【０２１２】
理解されるように、近似された点は、形状の輪郭が同一の点に残っているため、値符号化を必要としない。線は２つの値（１つの座標）の符号化を必要とし、２次曲線は４つの値の符号化を必要とする。
【０２１３】
尚、点、線及び２次曲線のレンダリングは、復号器側において一般的な３次曲線と比較して高速である。一般に、点はレンダリングされる必要がない。線のレンダリングは２次曲線より高速であり、２次曲線のレンダリングは３次曲線より高速である。この近似処理は、滑らかな３次曲線として３次曲線を近似するように容易に拡張可能であり、これにより座標値の数を６から４に減少する。
【０２１４】
パスの各コマンドの近似処理は、そのコマンドを検索することによりステップＥ４００において開始する。
【０２１５】
ステップＥ４１０において、コマンドが線として近似されるかが判定される。このテストは、以下のように種々の方法で実現可能である。
【０２１６】
第１の方法において、最初に元のコマンド曲線の任意の点と近似曲線（線、２次曲線、滑らかな３次曲線）との間の最大距離が算出される。この距離は、所定の閾値と比較され、どの近似が最適な近似であるのかを判定する。
【０２１７】
３次曲線からその近似線までの距離は、線(x-xe, y-ye)に対する垂直線上のベクトル(x-x2, y-y2)及びベクトル(x1-xe, y1-ye)の正射影ノルムとして推定される。これらのノルムは、ベクトル(x1-xe, y1-ye)（(x-x2, y-y2)）とベクトル(x-xe, y-ye)との間のベクトル積から算出される。表１は、ベクトル(x1-xe, y1-ye)に対して算出された距離（距離１）及びベクトル(x-x2, y-y2)に対して算出された距離（距離２）の結果を示す。
【０２１８】
これらの２つの距離が認識されると、例えば上記表に示すように、例えば双方の距離が所定閾値を下回る場合、コマンドは線として近似される。計算を制限するために、一般に閾値には、パスに対して許容される最大偏差が選択される。
【０２１９】
上記距離に対する別の基準、例えば(x1-xe, y1y-e)、(x2-x1, y2-y1)及び(x-x2, y-y2)の符号化と比較して(x-xe, y-ye)、(x1-xe, y1-ye)及び(x-x2, y-y2)を符号化することにより引き起こされる潜在的な圧縮損失が使用可能である。
【０２２０】
コマンドが線として近似可能である（ステップＥ４１０において出口「ｙｅｓ」）の場合、ステップＥ４２０において、コマンドが引数のより適切な圧縮を行なえる点として近似可能であるかがテストされる。
【０２２１】
このテストＥ４２０は、ベクトル(x1, y1)、(x, y)及び／又は(x-x2, y-y2)のノルムのサイズに基づく。
【０２２２】
これらのノルムが所定の閾値を下回る場合、ステップＥ４３０において、コマンドは点として近似される。これは、近似点コマンド「aP」が近似コマンドタイプシーケンスに追加されることを意味する。更に全ての３つの座標(x1, y1)、(x2, y2)及び(x, y)は復元情報セットに入れられ、このコマンドの値は縮小データセットに保持されない。
【０２２３】
ステップＥ４２０において否定的な応答の場合、ステップＥ４４０においてコマンドは線として近似される。そのような場合、近似線コマンド「aL」は近似コマンドタイプシーケンスに追加され、(x, y)座標のみが縮小データセットに保持され、(x1, y1)及び(x2, y2)座標は復元情報セットに入れられる。
【０２２４】
あるいは、ステップＥ４５０において、３次曲線コマンド「C」は簡略化されたベジェ曲線として、一般には２次曲線として近似される。
【０２２５】
そのような場合、２次曲線に対する特定の制御点が算出される。座標(x1, y1)及び(x2, y2)の重心(xm, ym)は、十分に適切なレンダリング近似であり、グローバル圧縮に関しても適切であるため選択される。(xm, ym)及び(x, y)は縮小データセットに追加され、近似２次曲線コマンド「aQ」は近似コマンドタイプシーケンスに追加される。
【０２２６】
次に、x1又はx2及びy1又はy2は、(x, y)への(xm, ym)の近似に基づいて復元情報セットに追加される。重心が曲線の開始点に近接する場合、x1及びy1が選択される。重心が(x, y)に近接する場合、x2及びy2が選択される。
【０２２７】
いくつかの曲線が滑らかな３次曲線として近似可能であり、この場合、(x2, y2)値のみが縮小データセットに保持される。
【０２２８】
ステップＥ４６０において、結果として得られる近似コマンドタイプ及び選択された値を格納する。
【０２２９】
ステップＥ４７０において、選択されない値及び近似前の元のコマンドタイプに関する情報は、復元情報セットに共に格納される。
【０２３０】
これらのステップの結果、２つのデータセットが構築される。
【０２３１】
−制限されたコマンドタイプセット及び値の小さなセットを有する近似コマンドを含む縮小データセット２５。このデータセットは、基本レイヤにおいて符号化されたデータである。
【０２３２】
−近似データ（縮小データセット２５の）から元のデータを得ることを可能にする復元情報セット２６。一般に、この復元情報セットは、元のコマンドタイプ及び除去された値を含み、第２のレイヤにおいて符号化される。
【０２３３】
実際には、３次曲線「C」コマンドは線として近似される場合が多い。これは、６つの引数値から２つの引数値に減少される場合が多いことを意味する。
【０２３４】
図４ａは、種々のデータセット２０〜２６が逐次的に生成される方法を示す。
【０２３５】
図３に戻ると、ステップＥ２３０の次にステップＥ２４０が続き、方法の符号化部分を開始する。
【０２３６】
ステップＥ２４０において、最初に符号化パラメータを書く。
【０２３７】
これらの符号化パラメータは、変倍因子、使用されるサブサンプリング比、特定の内部符号化パラメータ（ハフマンテーブルＩＤ、指数ゴロムパラメータ等）を含んでもよい。
【０２３８】
ステップＥ２５０において、ステップＥ２３０からの縮小データセット２５は基本符号化レイヤ２５’として符号化される。
【０２３９】
基本レイヤのデータは、コマンドタイプ（線、曲線等）のセット２５’ａ及び値のセット２５’ｂ（上記例においてはSet A1）を含む。
【０２４０】
基本レイヤにおけるコマンドタイプは、ＳＶＧコマンドタイプより小さいコマンドタイプのセットである。これらのコマンドは、例えば事前定義済みハフマンテーブルを使用するハフマン符号化である一般的な可逆的圧縮技術を使用して符号化される。
【０２４１】
一般に、近似線は２次曲線より一般的である。近似点は、サブサンプリングに大きく依存する。
【０２４２】
従って、いくつかのハフマンテーブルが規定され、最適なテーブルが符号器により選択される。
【０２４３】
他の技術（算術符号化、予測部分マッチング等）も使用可能である。
【０２４４】
近似コマンドの符号化に従って、座標値が符号化される。
【０２４５】
これらの値は、互いに対して符号化される。これらの値は、一連のx値及びy値として考えられる。指数ゴロム符号化を使用して、値xnは値xn-1に関連して符号化され、値ynはyn-1に従って符号化される。この符号化は、パラメータkを入力とする。このパラメータは、値の幾何学的分布に基づいて算出される。値セットが既にサブサンプリングされているため、最適な値kは、一般にゼロに近い値であり、多くの場合ゼロに等しい。
【０２４６】
x0及びy0は、任意の値をとることができるため線形符号化される。
【０２４７】
指数ゴロム符号の値kがゼロでない場合、符号化値は２つのストリームに分割されてもよい。第１のストリームは上位情報（すなわち、2kで除算される値）を含み、第２のストリームは下位情報（すなわち、値のバイナリ表現の最後のkビット）を含む。
【０２４８】
ステップＥ２５０に続き、オプションのステップＥ２６０において、近似値２５からサブサンプリング値２３を得ることを可能にする復元情報セット２６が符号化される（符号化部分２６’が取得される）。これは、相対値による指数ゴロム符号化を使用する上述したようなSet A2の符号化に対応する。
【０２４９】
サブサンプリングされた復元データ２６は、コマンドタイプを復元するのに必要な情報及び近似処理が実行される前の値の双方を含む必要がある。
【０２５０】
このデータを処理する時に基本レイヤが既に復号化されているため、近似コマンドタイプは認識されている。この近似コマンドタイプは、利用可能なコマンドセットを制限するために使用される。
【０２５１】
例えば、近似２次曲線は、線ではなく２次曲線又は３次曲線のみをもたらす可能性がある。元のコマンドタイプは、ハフマン符号化を使用して近似コマンドタイプに従って符号化される。コマンドタイプの符号化部分２６’ａが取得される。他の技術（算術符号化、予測部分マッチング等）も使用可能である。
【０２５２】
元の座標値は、基本レイヤの座標値に従って符号化される。点の場合、全ての元の値は、基本レイヤの値に対して行なわれたように、一般にゼロであるパラメータkにより指数ゴロム符号化を使用して符号化される。値の符号化部分２６’ｂが取得される。
【０２５３】
線として近似された曲線に対して、(x1, y1)及び(x2, y2)が符号化される。(x1-xe, y1-ye)は、小さい必要があるため指数ゴロム符号化を使用して直接符号化され、(x-x2, y-y2)は、(x2, y2)が既に認識されている(x, y)に近接する必要があるため、指数ゴロム符号化を使用して符号化される。
【０２５４】
近似２次曲線の場合、(x1, y1)(x2, y2)の重心(xm, ym)が認識されているため、(x1, y1)又は(x2, y2)のみが符号化され、残りの座標は(xm, ym)から算出される。指数ゴロム符号化を使用して最小である可能性がある値を符号化するために、以下のアルゴリズムが使用される。
【０２５５】
−(xm, ym)が(x, y)より(0, 0)に近接する場合、指数ゴロムを使用して(x1, y1)を符号化する。
【０２５６】
−(xm, ym)が(0, 0)より(x, y)に近接する場合、指数ゴロムを使用して(x-x2, y-y2)を符号化する。
【０２５７】
ステップＥ２６０の後、ステップＥ２７０において、スーパーサンプリング情報２４（上記例においてはSet B）がオプションとして符号化され、元の書き換えられたパスデータ２１の復元を可能にする。符号化スーパーサンプリング情報部分２４’は、符号化文書３０において取得される。
【０２５８】
スーパーサンプリング情報は、あるコマンドタイプ情報を含んでもよく、その場合、データ復元情報に対して使用されるような符号化技術が使用される。
【０２５９】
あるいは、スーパーサンプリング情報は、２つの技術、すなわち指数ゴロム及び線形符号化の組合せにより符号化可能である。指数ゴロム符号化は、特にスーパーサンプリング情報が１画素より大きい情報を含む場合、スーパーサンプリング情報の前の値がゼロである時に使用される。
【０２６０】
あるいは、スーパーサンプリング情報が束縛値（2n、nはサブサンプリング因子である）を有する整数から成るため、線形符号化が使用可能である。
【０２６１】
スーパーサンプリング情報量が大きい場合、例えば符号化値が２５６より大きい場合、このスーパーサンプリング情報はいくつかのサブレイヤに分割される。
【０２６２】
符号化処理は、ステップＥ２８０に継続し、オプションとして復元に対する書き換え情報２２は、元のパスシーケンスの忠実な復元を可能にするように部分２２’に符号化される。
【０２６３】
符号化処理のこれらのオプションのステップにより、符号化ＳＶＧ文書のサイズを縮小できる。従って、特に送信ネットワーク帯域幅が小さい場合又は記憶容量が小さい場合、符号化ＳＶＧ文書の送信はより効率的になる。
【０２６４】
図４ａは、符号化ＳＶＧパスに対応する連続する符号化部分２５’、２６’、２４’、２２’を含む結果として得られる符号化ＳＶＧ文書３０の部分を示す。図示するように符号化部分を順序付けることにより、基本レイヤが最初に符号化ストリームにあるため、復号器は実行中に画像を復号化してもよい。従って、実行中の漸進的なレンダリングが可能である。
【０２６５】
ＳＶＧ文書がいくつかのパスを含む場合、最初にパス毎に符号化された基本レイヤ及びその後パス毎の後続するレイヤを復号化することにより、漸進的な復号化は文書全体に対して達成されてもよい。
【０２６６】
図７を参照して復号化側を考慮すると、復号器は、復号化する所定の符号化ＳＶＧパス３０を検索することによりステップＥ５００において開始する。
【０２６７】
このデータは、全ての符号化レイヤ２５’、２６’、２４’、２２’を含んでもよく、あるいは復号化開始時にそれらの一部のみを含んでもよい。
【０２６８】
復号器は、ステップＥ５１０において符号化パラメータ（サブサンプリング、変倍因子等）を抽出する。
【０２６９】
ステップＥ５２０において、復号器は予想されるレンダリング品質又は予想される表示解像度に従って復号化するレイヤを選択する。
【０２７０】
例えばサムネイルのみが要求される場合、最低限の復号化が実行される。その一方で、ＳＶＧ文書のフル解像度表現が予想される場合、全てのデータが復号化されるべきである。
【０２７１】
ステップＥ５３０及びＥ５４０は、文書３０の部分２５’に対応する基本レイヤの復号化を実行する。各レイヤの復号化は、各レイヤの符号化に関して対称的である。
【０２７２】
基本レイヤの復号化は、基本レイヤのコマンドタイプ２５’ａを復号化することによりステップＥ５３０で開始する。
【０２７３】
復号器は、コマンドに基づいて、適切な指数ゴロムパラメータを仮定してステップＥ５４０において基本レイヤの値２５’ｂを復号化する。これは、各近似コマンドタイプが事前定義済みの数の引数を有するためである。
【０２７４】
ＳＶＧ復号器が基本レイヤの直後に復号化を停止することを認識している場合、ＳＶＧ復号器は、制限された値（点に対する値はなく、各線に対しては２つの値があり、各２次曲線に対しては４つの値がある）に対してのみ配列を割り当てることを決定してもよい。あるいは、次のレイヤ（復元レイヤ２６’、スーパーサンプリングレイヤ２４’及び書き換えレイヤ２２’）で復号化される値を格納するための十分なメモリが割り当てられてもよい。
【０２７５】
第１の例は、潜在的に実質的なメモリ消費の低減を可能にする。
【０２７６】
更に線及び２次曲線のみがレンダリングされるため、レンダリング処理はより高速である。
【０２７７】
基本レイヤのデータを直接レンダリングするために、データのスーパーサンプリングはサブサンプリングパラメータに従って実行される。例えばこれは、変倍因子をサブサンプリングパラメータの２乗と乗算することにより行なわれる。
【０２７８】
復号化処理の時点で、復号器はユーザに対してＳＶＧ画像を予備表示するためにＳＶＧパスの低解像度バージョンをレンダリングしてもよい。そのような場合、表示を可能にするための後処理は後述するように実行されてもよい。これにより、データ全体が復号化される前に予備表現をユーザに提供できる。
【０２７９】
復号器は、パスの全体の品質を向上する必要がある限り復号化を継続する。
【０２８０】
ステップＥ５５０において、復号器は、復号化する追加のレイヤが存在するか及びそれを復号化すべきかをチェックする。
【０２８１】
追加のレイヤが存在し且つそれを復号化すべきである場合、ステップＥ５６０において復号器は追加のレイヤを復号化する。
【０２８２】
復号化する第１の追加のレイヤは、復元レイヤ２６’であってもよい。その復号化は、基本レイヤにおいて符号化されていないコマンド値２６’ｂ及びコマンドタイプを更新／詳述するための情報２６’ａを復号化することから成る。
【０２８３】
このステップ中、レイヤ２６’の復号化データはステップＥ５３０及びＥ５４０の復号化データと組み合わされ、サブサンプリングデータ２３、すなわちアップグレードされたパスデータセットを復元する。
【０２８４】
他のレイヤ２４’及び２２’は、逐次的に復号化され、書き換えパスシーケンス２１及び元のＳＶＧパスシーケンス２０を逐次的に復元してもよい。
【０２８５】
ここでも、レイヤが復号化される度、表示はアップグレードされたパスデータ２３、２１及び２０により漸進的に更新されてもよい。ユーザは、ＳＶＧ画像を表示する前に全てのレイヤが復号化されるのを待つのよりはるかに速くフィードバックを提供される。
【０２８６】
復号器はステップＥ５５０に戻る。
【０２８７】
全ての要求されるレイヤが復号化されると、ステップＥ５７０において復号器はデータを後処理する。
【０２８８】
この後処理は、パスデータの変倍であってもよく又はデータのスーパーサンプリングであってもよい。
【０２８９】
最後に、復号化ＳＶＧパスデータが取得され、ステップＥ５８０において例えば表示するために使用される。
【０２９０】
尚、近似コマンドタイプを含むレイヤのレンダリングに対して、ＳＶＧコマンドタイプでないそれらのタイプは、ＳＶＧ復号器に準拠するように変換される必要がある。例えば「L」ＳＶＧコマンドへの「aL」コマンドの変換である。「aP」コマンドは除去され、「aQ」コマンドは「Q」ＳＶＧコマンドに変換される。
【０２９１】
本発明の一実施形態において、基本レイヤのレンダリングは、変換の性質を考慮する特定の技術により実質的に向上されてもよい。これらの技術がある処理時間及び処理能力を消費するにも関わらず、データの読み出しがデータの処理より遅い場合、一般に帯域幅が小さい場合又はボリュームが大きい場合に特に適する。
【０２９２】
これらの技術は以下により構成されてもよい。
【０２９３】
−平滑化を線に適用することによる線形／３次予測。視覚的により快適なレンダリングが容易に達成される。
【０２９４】
−２次制御点の自動射影に加えて平滑化変換が適用される２次／３次予測。
【０２９５】
上記から、本発明がＳＶＧパスに対して効率的な符号化方法を提供することが示される。
【０２９６】
−ＳＶＧパスの階層符号化及び復号化を可能にし、その結果、部分復号化及び漸進的なレンダリングを可能にする。
【０２９７】
−圧縮に関して最適な利用可能なコーデックとほぼ同等に適切な可逆的圧縮。
【０２９８】
図８を参照して、本発明に係る方法の一実現例に適応された情報処理装置の特定のハードウェア構成の例として説明をする。
【０２９９】
本発明を実現する情報処理装置は、例えば種々の周辺装置に接続されるマイクロコンピュータ４０、ワークステーション、パーソナルアシスタント又は移動電話である。本発明の更に別の実施形態によると、情報処理装置は、ネットワークへの接続を可能にする通信インタフェースを備えるカメラの形態をとる。
【０３００】
情報処理装置に接続される周辺装置は、例えば入出力グラフィックスカード（不図示）に接続され且つ情報処理装置にマルチメディアデータを供給するデジタルカメラ６０又はスキャナ、あるいは画像を取得又は格納する任意の他の手段を含む。
【０３０１】
装置４０は、通信バス４１を含み、通信バス４１には、
−例えばマイクロプロセッサの形態をとる中央処理装置ＣＰＵ４２と、
−本発明に係る方法の実現を可能にするために実行されるプログラムを含んでもよい読み出し専用メモリ４３と、
−装置４０の電源投入後に、本発明のプログラムの実行可能コード、並びに本発明の実現に必要な変数及びパラメータを記録するように構成されるレジスタを含むランダムアクセスメモリ４４と、
−キーボード４６、あるいは例えばマウス４７又は光学スタイラスであるポインティングデバイス等の任意の他の手段を使用して本発明に係るプログラムと対話してもよいユーザとのグラフィカルインタフェースの役割を果たし且つ／又はデータを表示する画面４５と、
本発明の実現例に基づいて使用又は生成されるデータに加えて本発明のプログラムを含むことができるハードディスク４８又はコンパクトフラッシュカード等の記憶メモリと、
−外部ディスク７０を受け入れ且つ本発明に従って処理されたか又は処理されるデータに対して読み出し／書き込みを行なうように構成される光ディスクドライブ４９又は取り外し可能データ記憶媒体に対する別のリーダと、
−電気通信ネットワーク８０に接続され且つデジタルデータを送信及び受信するように構成される通信インタフェース５０とが接続される。
【０３０２】
通信バス４１は、装置４０に含まれるか又は装置４０に接続される種々の要素間の通信及び相互運用を可能にする。バス４１の表現は限定されず、特に中央処理装置４２は、装置４０の任意の要素に命令を直接通信してもよく又は装置４０の別の要素を使用して通信してもよい。
【０３０３】
外部ディスク７０は、書き換え可能又は書き換え不可能なコンパクトディスク（ＣＤ−ＲＯＭ）、ＺＩＰディスク又はメモリカード等の任意の情報記憶媒体であってもよい。一般に、マイクロコンピュータ又はマイクロプロセッサにより読み出し可能であり、情報処理装置に組み込まれるか又は組み込まれず且つ取り外し可能であってもよい情報記憶手段は、実行されることにより本発明に係る方法の実現を可能にする１つ以上のプログラムを格納するように構成される。
【０３０４】
情報処理装置が本発明を実現することを可能にする実行可能コードは、上述したように、読み出し専用メモリ４３、ハードディスク４８又は外部ディスク７０等の取り外し可能デジタル媒体に同等に適切に格納される。一変形例によると、プログラムの実行可能コードは、電気通信ネットワーク８０の仲介により、すなわちインタフェース５０を介して受信され、実行前に装置４０の記憶手段のうちの１つ（ハードディスク４８等）に格納される。
【０３０５】
中央処理装置４２は、本発明の１つ又は複数のプログラムのソフトウェアコードの命令又は一部の実行を制御及び指示する。ソフトウェアコードの命令又は一部は上述の記憶手段のうちの１つに格納される。装置４０の電源投入時、例えばハードディスク４８又は読み出し専用メモリ４３である不揮発性メモリに格納される１つ又は複数のプログラムは、本発明の１つ又は複数のプログラムの実行可能コードを含むランダムアクセスメモリ４４、並びに本発明の実現に必要とされる変数及びパラメータを格納するためのレジスタに転送される。
【０３０６】
尚、本発明を実現するか又は本発明を組み込む装置は、プログラムされた装置の形態で実現されてもよい。例えばそのような装置は、特定用途向け集積回路（ＡＳＩＣ）に固定形式でコンピュータプログラムのコードを含んでもよい。
【０３０７】
本明細書で説明する装置及び特に中央処理装置４２は、図３〜図７に関連して説明した処理動作の全て又は一部を実現し、本発明の各方法を実現し且つ本発明の各装置を構成してもよい。
【０３０８】
先の例は、本発明の単なる実施形態であり、本発明はそれらに限定されない。
【０３０９】
特に、詳細な説明が固有の近似変換（ステップＥ２３０）を示すが、そのような変換のいくつかは結果として得られる縮小データセット２５に対して繰り返されてもよい。これにより、更に多くのレイヤを生成してもよく、特定のディスプレイ又はレンダリング装置に対する最適なレンダリングを取得するために復号器に対してより多くの解像度の選択肢が生成されてもよい。
【０３１０】
そのような場合、いくつかの近似変換は、ステップＥ２３０で使用される閾値に関して異なり、特定の近似描画コマンドを考慮してもよい。最初に高解像度レイヤ及び対応する復元情報セットを生成するために小さな値が使用されてもよく、その後、低解像度レイヤを生成するためにより大きな値が使用されてもよい。
【０３１１】
あるいは、近似コマンドセットは、繰り返しが進むのに伴って変更及び縮小されてもよい。
【０３１２】
別の態様によると、１つのＳＶＧパスの階層符号化を説明したが、一般にＳＶＧ文書の符号化はいくつかのパスの符号化を含む。本発明は、ＳＶＧ文書全体がレイヤとして符号化されるように容易に拡張可能である。
【０３１３】
そのような場合、ＳＶＧ文書が一般に符号化される。ＳＶＧパスデータは、基本レイヤの情報のみを含む。文書のＳＶＧパスの連結された第２のレイヤは符号化文書の最後に挿入され、その後、第３のレイヤが第２のレイヤの後に挿入される。
【０３１４】
この階層技術に基づいて、符号化パラメータを注意深く選択することにより、レイヤは適切なサイズで構築される。第１のレイヤは非常に小さなメモリ量を有し、更なるレイヤは、同等のサイズを有するか、サイズが徐々に増加する。これにより、ＳＶＧデータ送信及び漸進的なレンダリングの管理が更に容易になる。
【技術分野】
【０００１】
本発明は、部分復号化及び復号化中の漸進的なレンダリングを可能にするように階層形式でグラフィックスパスを符号化する方法に関する。
【背景技術】
【０００２】
一般にグラフィックスパスは、ＳＶＧ（「スケーラブルベクターグラフィックス」を意味する）、ＤｒａｗＭＬ又はMicrosoft Silverlight（登録商標）等のグラフィックス記述言語でグラフィック、図形、又は画像を表す。説明する目的で、以下の説明はＳＶＧ規格に注目する。
【０００３】
周知の方法では、ＳＶＧ規格は、ベクトルグラフィックス描画を記述するためにＸＭＬ名前空間として使用可能なスタイル付け可能なグラフィックスに対するＸＭＬ文法である。
【０００４】
ベクトルを使用する方法により、ＳＶＧ画像は精度を損なうことなく任意の所定の解像度でレンダリング可能である。
【０００５】
ＳＶＧは、ＸＭＬ構文を使用して、幾何学的形状、変換、色又はアニメーションを記述する要素及び属性の集合を規定する。例えばＸＭＬ要素は、描画コマンドを規定してもよく、コマンドと関連するパラメータ属性又は座標を含んでもよい。
【０００６】
ＳＶＧにより可能な単純な幾何学的形状は、矩形、円、楕円、線及び多角形である。
【０００７】
より複雑な形状は、特別なツール、すなわちＳＶＧパス及び対応するＸＭＬ要素＜path d="..."＞を使用して描画されてもよい。
【０００８】
ＳＶＧパスは、形状の輪郭を表し、座標（点を規定する）及び半径又は弧フラグ等の描画コマンド及び関連する引数のシーケンスとして書かれる。シーケンスは、線、ベジェ曲線及び／又は弧のような連続した描画部分（各描画部分がコマンドに対応する）から複雑な幾何学的形状を記述する。
【０００９】
形状の輪郭を規定するパスは、ＸＭＬ要素の属性「d」で書かれ、絶対座標又は相対座標を使用して書かれる。相対座標は、パスの先行座標に基づいて書かれる。
【００１０】
描画コマンドは、文字により規定される。大文字は絶対座標の使用を指定し、小文字は相対座標に対応する。大文字及び小文字の双方を使用することにより、絶対座標及び相対座標は同一パス内で併用される。
【００１１】
一例として、以下の２つのパスは同一の複雑な幾何学的形状を表す。第１のパスが絶対座標を含む一方で、第２のパスは相対座標から成る。
【００１２】
M 14.0, 70.9 L14.0, 55.0 L 2.0, 71.0 L14.0, 70.9 Z
m 14.0, 70.9 l 0.0, -15.9 l-12, 16.0 l12.0, -0.1 z
「M」又は「m」は、考慮する新しい幾何学的点を規定する「move-to」描画コマンドである。
【００１３】
「L」又は「l」は、線の終点を指定する線コマンドである。
【００１４】
「Z」は、closepathコマンドであり、パスの最後に処理された点と最初の点との間の直線によりパスの輪郭を閉じる。
【００１５】
「C」又は「c」コマンドは、３次曲線を規定する。「c」コマンドは、図１に示すように６つのパラメータ値を必要とする。(x1, y1)は第１の制御点であり、(x2, y2)は第２の制御点であり、(x, y)は曲線の終点である。曲線の始点は先行コマンドの終点(xe, ye)である。
【００１６】
ＳＶＧ曲線コマンドは、「S／s」平滑化３次曲線コマンド、「Q／q」又は「T／t」２次ベジェコマンド又は「A／a」楕円弧コマンドを更に含む。
【００１７】
本発明は、ＳＶＧタイプのＸＭＬを使用する文書の符号化に関する。
【００１８】
ＸＭＬが文書の構造を記述するための詳細な構文を有するため、ＸＭＬに対する特定の符号化機構は、元のＸＭＬ文書を容易に再構築する能力を維持しつつ、より効率的な形式でＸＭＬ文書の内容を符号化するために調査された。
【００１９】
Fast Inforset形式及びEfficient XML Interchange（ＥＸＩ）形式を含むバイナリＸＭＬ形式が開発された。
【００２０】
これらの２つの形式は、指標テーブルを使用して、内容又は構造的要素の全体ではなく反復内容又は構造的要素の新たな発生頻度を関連する指標で符号化する。ＸＭＬ文書を符号化するためのビットは節約される。一般に、その節約の殆どは構造的情報によるものである。
【００２１】
バイナリＸＭＬ形式がＳＶＧ文書を符号化するために使用可能である一方で、それらの形式の殆どがそのような符号化に圧縮されて適応されない。
【００２２】
これは、ＳＶＧ文書が内容部分と比較して小さな構造的情報の部分を含むためである。
【００２３】
また、これは、大きなＳＶＧ内容が繰り返されることが殆どなく、整数又は浮動小数点等の単純なデータタイプに対する周知のバイナリＸＭＬ符号化の効率が利用されない複雑なタイプのものであるためである。その大きな内容は、例えば単純なグラフィックスコマンドを座標又は値（整数及び浮動小数点の双方）のリストと混合するグラフィックスパスである。
【００２４】
従って、ＳＶＧ文書に対するいくつかの特別なバイナリＸＭＬ符号化形式が開発された。
【００２５】
特に米国特許第６，６２４，７６９号公報から、ＳＶＧパスシーケンスの描画コマンド及び関連する整数の引数を別個に符号化する方法が周知である。
【００２６】
第１に、コマンドはグラフィックスパスにおいて使用されるコマンドのみによるハフマンのような符号により符号化される。従って、使用される符号の数（すなわち、ビット数）は減少される。
【００２７】
第２に、その特許のＳＶＧプロファイルが移動電話専用であるため整数のみである引数は、グラフィックスパスに含まれる任意の引数の符号化を可能にする最小のビット数を使用してバイナリ形式で符号化される。引数は、２つのカテゴリ、すなわち絶対大文字コマンドに属する引数及び相対小文字コマンドに属する引数に分割される。
【００２８】
引数のカテゴリ毎に、そのカテゴリの全ての引数の符号化を可能にする最小のビット数が計算される。その後、各引数は、そのカテゴリに依存して複数のビットを使用して符号化される。
【００２９】
この形式は、あるカテゴリの引数又はコマンドを符号化するのに必要とされる最小数にビット数を調整することにより、ＳＶＧ文書の効率的な圧縮を提供する。
【００３０】
更に米国特許出願公開第２００８／０６３，１１４号明細書から、ＳＶＧ文書の符号化を対象とする簡易シーン記述（ＬＡＳｅＲ）バイナリＸＭＬ形式が周知である。
【００３１】
この出願によると、ＳＶＧパスシーケンスの符号化は、引数を符号化するために２つの方法のうちより適切な方を使用する。
【００３２】
第１の方法は、第１のビット長を使用して最初の２つの引数を符号化し、２つの他のビット長を使用して残りの全ての引数を相対引数として符号化しようとする。第１のビット長は、最初の２つの引数の符号化を可能にする最短のビット長である。２つの他のビット長は同様に算出される。すなわち、第１の他のビット長は、全ての相対的な横座標の符号化を可能にする最短のビット長であり、第２の他のビット長は、全ての相対的な縦座標の符号化を可能にする最短のビット長である。
【００３３】
第２の方法は、第１のビット長を使用して最初の２つの引数を符号化し、指数ゴロム（exponential-Golomb）符号化を使用して全ての更なる引数を相対引数として符号化しようとする。
【００３４】
しかし、これらの２つの出願において開示される解決策はいくつかの欠点を有する。
【００３５】
特に、符号化ＳＶＧ描画のレンダリングは、完全な画像を描画及び表示するためにＳＶＧパスの全ての情報の復号化を必要とする。
【００３６】
ＳＶＧ画像をサムネイル又は小さなレンダリングサイズにレンダリングするために、一般にデータパスの精度が高すぎるため、符号化ＳＶＧデータの処理は時間を浪費する。
【００３７】
従って、適切な圧縮性能を維持しつつ、部分復号化及び／又は漸進的なレンダリング用のＳＶＧ文書等のグラフィックス文書を符号化する方法を提供する必要がある。
【００３８】
ＳＶＧ文書用の別の特定のバイナリＸＭＬ形式は、Expway（www.mitre.org／news／events／xml4bin／pdf／thienot_binary.pdf, slides 53-56）により提示されて開示される。
【００３９】
開示される方法は、座標値の線形量子化を実行し、より少ないビット数、例えば７〜９ビットにわたり後者を符号化する。この提示の例示的な図により示されるように、方法は、パスデータ及びレンダリングされた描画の精度を激減する。
【００４０】
この方法もいくつかの欠点を有する。
【００４１】
Expwayの方法は、元の画像のフル解像度の回復を可能にしない不可逆的圧縮である。
【発明の概要】
【発明が解決しようとする課題】
【００４２】
部分復号化又は漸進的なレンダリングを可能にするグラフィックスパス符号化を有するのが望ましい。
【課題を解決するための手段】
【００４３】
そのために、本発明の目的は、グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンスを含むパスを符号化する方法であって、
−縮小シーケンスを取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップと、
−前記縮小シーケンスを符号化縮小シーケンスに符号化するステップと、
−縮小シーケンスと元のシーケンスとの間の差分（変換の結果として得られる）を表す復元情報セットを符号化するステップとを有する。
【００４４】
この方法は、元のシーケンスを幾何学的に近似する別の「縮小」シーケンスによりパスシーケンスを置換する。
【００４５】
この縮小シーケンスは、対応する画像の低解像度又は小さいサイズのレンダリングを提供するために復号化する際に使用されてもよい。
【００４６】
更に、復号化の時により高い解像度レンダリング又はフル解像度レンダリングが取得されてもよいように、縮小シーケンスから元のシーケンスを復元できるようにする補助「復元」情報セットが符号化される。
【００４７】
従って、方法は可逆的復元又はほぼ可逆的復元を可能にしてもよい。
【００４８】
本発明に係る方法により、画像レンダリングは低解像度レイヤを取得するために元のパスを部分的に復号化することにより取得されてもよい。
【００４９】
更に、漸進的なレンダリングは、より高い解像度レンダリング又はフル解像度レンダリングに向けてレンダリングを向上するために補助情報セット（より高い解像度レイヤ）を更に復号化することにより取得されてもよい。
【００５０】
復号化されたデータの品質が良いほど、レンダリングされた画像の解像度は良い。
【００５１】
後述するように、幾何学的近似は、より少ないビット数又は引数が符号化されることを要求するより単純な描画コマンドを取得するために選択されてもよい。結果として得られる「縮小」パスシーケンスの長さは縮小される。
【００５２】
従って、方法により、低解像度レンダリングを提供するための処理時間が短縮される。基本レイヤのより高速なレンダリングが取得されてもよい。
【００５３】
上述したように、本発明は、図形を表すパスを提供する任意のグラフィックス記述言語に適する。これは、ＳＶＧ規格、並びにＤｒａｗＭＬ及びMicrosoft Silverlightの勧告に例示的に関連する。
【００５４】
本発明の１つの態様によると、描画コマンドは、座標等の描画コマンドタイプ及び引数を含み、前記近似描画コマンドは前記元の描画コマンドより少ない引数を含む。縮小シーケンスのサイズは、低解像度画像のより適切な圧縮及び変換のために激減されてもよい。復号化側において、より高速なレンダリングはより少ないメモリを使用して取得される。
【００５５】
特に近似描画コマンドの少なくとも１つの引数は、元の描画コマンドの引数から算出される。これは、特定の制御点を必要とする２次曲線コマンドを近似する例であってもよい。例えば「近似」引数は、３次ベジェ曲線描画コマンドの元の制御点引数の重心であってもよい。重心の使用は、３次／２次近似に対して適応されており、元の３次パラメータのコンパクトで単純で高速な計算を可能にする。
【００５６】
本発明の別の態様によると、縮小シーケンス内の元の描画コマンドの変換に対応する近似描画コマンドは、近似点描画コマンド、近似線描画コマンド及び近似２次曲線コマンドのうちの１つである。これらの近似コマンドは、殆ど引数を必要としないため効率的な符号化を提供し、より高速なレンダリングを含むコマンドであるため復号器側で高速な画像レンダリングを提供する。
【００５７】
特に幾何学的近似は、ＳＶＧ３次ベジェ曲線コマンドを前記近似点、線又は２次曲線コマンドのうちの１つに変換する。この変換は、ＳＶＧ３次ベジェ曲線コマンドが約６個の引数を必要とし且つ提案された近似コマンドが０、２及び４個の引数をそれぞれ必要とするため、最も効率的な変換である。
【００５８】
別の特定の特徴によると、変換するステップは、元の描画コマンドに対応する描画と近似描画コマンドに対応する描画との間の距離を算出することと、計算した距離を少なくとも１つの閾値と比較することとを含む。この状況において、変換は、近似変換を適用するために潜在的なレンダリング歪み又は変更を基準として直接考慮する。均一にレンダリングされた画像は、画像内の歪みの小さな変化に伴って取得される。
【００５９】
そのような閾値は、復号器において予想されるレンダリング解像度に基づいて計算されてもよい。複数の解像度レイヤを生成するために複数の近似が繰り返し実行されてもよいため、各々が予想された解像度に対応する複数の閾値が使用されてもよい。
【００６０】
特に元の３次曲線コマンドが曲線の各端点に制御ベクトルを含む場合、前記距離は、２つの端点により生成される線に対する垂直線上の２つの制御ベクトルの正射影ノルムを含む。
【００６１】
正射影は、容易に算出される。効率的な指示は、対応する描画が大きく湾曲するか否かに関して取得される。ノルムが大きい程、描画はより大きく湾曲する。従って、近似は、ノルムが閾値と比較して十分に小さい場合に行なわれる。
【００６２】
本発明の１つの特徴によると、前記復元情報セットは：
−種々の近似描画コマンドタイプに変換された元の描画コマンドタイプと、
−近似描画コマンドに保持されていない元の描画コマンドの引数及び／又は元の描画コマンドの引数から計算され且つ近似描画コマンドに保持されていない引数の検索を可能にする引数とを含む。
【００６３】
この復元情報セットにより、元のデータの復元（可逆的圧縮）が可能になる。元のデータを復元情報セット及び縮小シーケンスに分割することにより、データは種々の解像度レイヤに符号化されてもよい。
【００６４】
本発明の別の特徴によると、符号化方法は、幾何学的近似に従う近似変換を含む元のシーケンスの複数の反復変換を含み、
最後の変換の結果として得られる縮小シーケンスが符号化され、変換の復元情報セットのうちの少なくとも１つが符号化される。
【００６５】
「反復変換」は、１つの変換の結果として得られるシーケンスが次の変換の入力であることを意味するものとして理解される。複数の符号化レイヤが取得され、復号化側における種々の解像度レンダリング可能性を可能にする。漸進的なレンダリングが可能である。
【００６６】
特に復元情報セットの各々が符号化される。可逆的符号化が取得される。
【００６７】
しかし、制限された数の復元情報セットが符号化されてもよく、それにより不可逆的符号化が提供される。制限された数は、利用可能なネットワーク帯域幅等の動的な条件に基づいて判定されてもよい。この提供により、補助復元情報セットの前に最も重要な情報がまず送出される。
【００６８】
特定の特徴によると、前記近似変換の前の変換は、元のパスシーケンスを全ての絶対値又は全ての相対値に書き換えることを含む。パスシーケンス中の座標は、より適切な符号化に対してより均一である。
【００６９】
あるいは、又は組み合わせて、前記近似変換の前の変換は、より少ない引数を有する同等の描画コマンドにより描画コマンドを置換することにより元のパスシーケンスを書き換えることを含む。このように、シーケンスの長さは縮小される。
【００７０】
処理する更に単純なパスシーケンスが取得される。近似変換と同様に、書き換えられたシーケンスから元のパスシーケンスを復元できるようにする差分を含む復元情報セットが生成されても良い（その後、格納及び符号化される）。
【００７１】
別の特定の特徴によると、前記近似変換の前の変換は、サブサンプリングシーケンス及びサブサンプリングシーケンスから元のシーケンス又は書き換えられたシーケンスの復元を可能にするスーパーサンプリング情報を含む復元情報セットを取得するために、元のシーケンス又は書き換えられたシーケンスをサブサンプリングするステップを含む。この提供により、近似変換は、制限された数の可能なデータに対して実行され、それらのデータは制限されたビット数にわたり処理される。このように、処理は容易になる。
【００７２】
別の特定の特徴によると、各変換ステップは、先入れ後出し（ＦＩＬＯ）メモリに復元情報セットを格納することを含む。従って、復元セットが生成された順序と逆の順序で復元セットを符号化することは単純化される。符号化する際のそのような逆の順序により、復号化側における高速且つ効率的な漸進的な画像レンダリングは可能になる。
【００７３】
特定の一実施形態によると、複数の復元情報セット及び最終的な縮小シーケンスを取得するために、いくつかの近似変換が縮小シーケンスに対して繰り返され、
複数の復元情報セット及び最終的な縮小シーケンスは、種々の画像解像度の複数の符号化レイヤを生成するために符号化される。
【００７４】
本発明の別の態様によると、前記縮小シーケンスは、任意の復元情報セットの前に最初に符号化される。これにより、復号化側において低解像度レンダリングが迅速に取得可能であることが保証される。特に復元情報セットは、生成された順序と逆の順序でセットを符号化するように、上述のＦＩＬＯメモリから検索されてもよい。
【００７５】
本発明の別の態様によると、縮小シーケンスは、前記縮小シーケンス内のコマンドの引数に対応する値のシーケンスを含み、
縮小シーケンスの第１の座標の値は絶対値として線形符号化され、他方の座標の値はシーケンス内の先行座標の値に対して符号化される。
【００７６】
一般に相対値が絶対値より小さいため、縮小シーケンスのよりコンパクトな符号化表現が取得されてもよい。
【００７７】
特定の特徴によると、復元情報セット内の座標の値はそのセット内及び先行符号化縮小シーケンス又は復元情報セット内の先行座標の値に対して符号化される。ここでも、この提供により、復元セットのよりコンパクトな符号化表現が取得されてもよい。
【００７８】
更に本発明は、グラフィックス記述言語で図形を表す符号化データを復号化する方法であって：
−近似描画コマンドのグラフィックスパスシーケンスを取得するために符号化データから第１のシーケンスを受信し且つ復号化するステップと、
−符号化データの新しいレイヤが復号化される必要があるかを判定するステップと、
−肯定的な判定の場合に、
・ 符号化データから新しいレイヤに対応する情報セットを受信及び復号化し、
・ アップグレードされたパスシーケンスを取得するために、復号化情報セットに基づいて復号化グラフィックスパスシーケンスの少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換するステップとから成る方法に関する。
【００７９】
符号化方法と関連して、変換は一般により複雑な描画を提供する幾何学的変換である。
【００８０】
本発明の１つの態様によると、情報セットを受信及び復号化するステップ及び変換するステップは、符号化データの新しいレイヤが復号化される必要がある限り前記アップグレードされたパスシーケンスに対して繰り返される。元のパスシーケンスを漸進的に復元するための各レイヤの漸進的な復号化が達成される。
【００８１】
１つの特徴によると、方法は、アップグレードされたパスシーケンスに対応するレンダリング描画を平滑化するために予測を使用して前記アップグレードされたパスシーケンスを後処理することを更に含む。そのような後処理は、復号化される必要がある更なるレイヤがない場合（すなわち、否定的な判定の場合）に行なわれる。このように、視覚的により快適なレンダリングが達成される。
【００８２】
一実施形態によると、方法は、否定的な判定である場合、
−変換シーケンスを取得するために、少なくとも１つの近似描画コマンドを前記グラフィックス記述言語のパス描画コマンドに変換するか又は前記近似描画コマンドを除去することと、
−変換シーケンスに基づいて画像をレンダリングすることとを含む。
【００８３】
特に前記近似描画コマンドの除去は、前記近似描画コマンドが点コマンドに対応する場合に実行される。
【００８４】
これに対応し、本発明は、グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンスを含むパスを符号化する装置であって：
−縮小シーケンスを取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換する変換手段と、
−前記縮小シーケンスを符号化縮小シーケンスに符号化し且つ縮小シーケンスと元のシーケンスとの間の差分を表す復元情報セットを符号化する符号化手段とを具備する装置に関する。
【００８５】
オプションとして、装置は上述した符号化方法の特徴に関連する手段を含んでもよい。
【００８６】
これに関連して、本発明は、グラフィックス記述言語で図形を表す符号化データを復号化する装置であって：
−近似描画コマンドのグラフィックスパスシーケンスを取得するために、符号化データから第１のシーケンスを受信する受信手段及び前記第１のシーケンスを復号化する復号化手段と、
−符号化データの新しいレイヤが復号化される必要があるかを判定する判定手段と、
−肯定的な判定の場合に、符号化データから新しいレイヤに対応する情報セットを受信及び復号化する手段と、
−アップグレードされたパスシーケンスを取得するために、復号化情報セットに基づいて復号化グラフィックスパスシーケンスの少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換する変換手段とを具備する装置に関する。
【００８７】
オプションとして、装置は上述の復号化方法の特徴に関連する手段を含んでもよい。
【００８８】
コンピュータシステムにより読み出し可能である情報記憶手段は、コンピュータシステムによりロード及び実行された時に本発明に係る符号化又は復号化方法を実現するように構成されるコンピュータプログラムの命令を含む。
【００８９】
マイクロプロセッサにより読み出し可能なコンピュータプログラムは、マイクロプロセッサによりロード及び実行された時に本発明に係る符号化又は復号化方法を実現するように構成されるソフトウェアコードの部分を含む。
【００９０】
コンピュータプログラム及び情報記憶手段は、それらが実現する方法と同様の特徴及び利点を有する。
【図面の簡単な説明】
【００９１】
本発明の追加の利点及び特徴は、添付の図面を参照し、単なる例として示される以下の説明を読むことにより明らかとなるだろう。
【図１】図１は、ＳＶＧ規格に従って３次曲線コマンドのパラメータ化を示す図である。
【図２】図２は、ＳＶＧパスシーケンスを含むＳＶＧ文書の例示的な抜粋を示す図である。
【図３】図３は、本発明に係る符号化方法の一般的なステップを示すフローチャートである。
【図４】図４は、本発明に係る符号化方法の詳細な一実施形態を示すフローチャートである。
【図４ａ】図４ａは、本発明に従う縮小データセット及び復元セットの構築、並びにその符号化を示す図である。
【図５】図５は、図４の処理において実現される座標値の絶対表現に対するサブサンプリングを示すフローチャートである。
【図６】図６は、図１に示すような３次曲線に対する例示的な近似処理を示すフローチャートである。
【図７】図７は、本発明に係る復号化処理を示すフローチャートである。
【図８】図８は、本発明に係る方法の一実現例に対して適応される情報処理装置の特定のハードウェア構成を概略的に示す図である。
【発明を実施するための形態】
【００９２】
最初に、図２に示す例示的なＳＶＧ文書１に基づいて本発明を説明する。
【００９３】
ＳＶＧ文書１は、「path」タイプのＳＶＧ要素を含む。その属性「d」は元のパスシーケンス１０を規定する。
【００９４】
パスは、「C」描画コマンドにより規定される７つの３次ベジェ曲線からなる閉曲線である。最後の「z」コマンドは、「M」コマンドにおいて第１の点のセットを含む描画を閉じる。
【００９５】
本発明によると、このＳＶＧパスの符号化は、
−縮小シーケンスを取得するために描画の対応する元の部分（ＳＶＧパスにより表される図形の一部分）の幾何学的近似に従って、少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップと、
−前記縮小シーケンスを符号化縮小シーケンスに符号化するステップと、
−縮小シーケンスと元のシーケンスとの間の差分を表す復元情報セットを符号化するステップとを含む。
【００９６】
符号器は、図２のパスシーケンスを構文解析し、整数、各々がタイプ（又は名前）及び整数値（コマンド毎の整数値の数はＳＶＧ規格により規定される）を有するコマンドのリスト、並びに引数の値、ここでは座標のみ（横座標及び縦座標の対）を処理するように１０，０００の変倍因子を判定する。
【００９７】
構文解析された情報は以下の通りである。
【００９８】
−パラメータ：変倍因子＝１０，０００
−コマンドタイプシーケンス：MCCCCCCCz
−値シーケンス：1657142, 3809336, 1540972, 3121730, 1671473, 2680800, 1857142, 2295050, 2160130, 1825486, 2516866, 1872163, 2904285, 1923621, 2904285, 1913621, 2914285, 1913621, 2914285, 1903621, 2914285, 1903621, 2924285, 1903621, 2924285, 1903621, 3353836, 2072530, 3773967, 2236000, 3914285, 2609336, 3948959, 3146579, 4274470, 3351436, 3828571, 4437907, 3003143, 5074644, 1724985, 6172611, 1657142, 3809336
符号化する値を減少することを目的とする第１のステップにおいて、符号器は、データセットに対してサブサンプリング変換を適用する。２つのデータセット、すなわちサブサンプリングデータ及びサブサンプリング値からもとの値の復元を可能にするスーパーサンプリングデータが取得される。
【００９９】
サブサンプリング変換は、例えば変倍因子に従って規定される。
【０１００】
本発明の例において、１２ビットのサブサンプリングが使用される。しかし、読みやすくするために、ベース１０のサブサンプリングを仮定し、取得される第１のサンプリングデータセットは、Set A (11): 165, 380, 154, 312, 167, 268, 185, 229, 216, 182, 253, 187, 290, 192, 290, 191, 291, 191, 291, 190, 291, 190, 292, 190, 292, 190, 335, 207, 377, 223, 391, 260, 394, 314, 427, 335, 382, 443, 300, 507, 172, 617, 165, 380である。
【０１０１】
第２のデータセットは、Set B (12): 7142, 9336, 972, 1730, 1473, 800, 7142, 5050, 130, 5486, 6866, 2163, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 4285, 3621, 3836, 2530, 3967, 6000, 4285, 9336, 8959, 6579, 4470, 1436, 8571, 7907, 3143, 4644, 4985, 2611, 7142, 9336である。
【０１０２】
第１のステップは、元のパスシーケンス１０の第１の近似（コマンドシーケンス＋Set A 11）を提供する。
【０１０３】
描画コマンドをより単純なコマンドに変換することを目的とする第２のステップにおいて、符号器は、コマンド「C」により規定される３次ベジェ曲線が線として近似されるか又は他の単純なコマンドであるかをテストする。
【０１０４】
３次ベジェ曲線と近似線（曲線の２つの端点により規定される）との間の数学的距離が算出され、近似決定に対する主な基準としての役割を果たす。以下の表１は、そのような計算の結果を一覧表示し、後で規定されるような２つの距離（図６の説明を参照）は曲線毎に算出されている。
【０１０５】
【表１】
【０１０６】
本発明において使用される近似コマンドは、ＳＶＧ描画コマンド又は拡張描画コマンドであってもよい。更に、特定の「点」コマンド（「aP」）は、開始点に非常に近接する終点に対応する近似コマンドを指定するために使用されてもよい。
【０１０７】
尚、元のコマンドを置換するのに使用される近似コマンドは、より少ない引数を必要とする。すなわち、点コマンドは座標を必要とせず、線コマンドは１つの座標（すなわち、横座標及び縦座標）を必要とし、２次曲線コマンドは２つの座標を必要とし、その一方で元の３次ベジェ曲線「C」コマンドは３つの座標を必要とする。
【０１０８】
表に示すように、距離が十分に短い場合、曲線は線として近似される。距離がほぼゼロである場合、曲線の終点は、曲線が点として近似されるように開始点に非常に近接する。距離がほぼゼロでない場合、曲線は２次曲線として近似される。「点」コマンドは引数を有さない。
【０１０９】
上記テーブルの近似方法のセットに従って、２つのデータ（又は情報）セットはSet A 11から生成される。
【０１１０】
−近似の後に結果として得られる引数を含む第１のセット、すなわちSet A1(13)。線として近似された曲線の端部の座標を含み、点として近似された曲線に対しては座標を含まず、２次曲線として近似されたコマンドに対して２つの座標を含む（例えば重心である元の曲線コマンドの２つの元の制御点から算出されてもよく且つ以下に下線を引いた太字で示される曲線の端部の座標及び制御点）：
【０１１１】
【数１】
【０１１２】
−Set A1において選択されなかった全ての座標及び以下に下線を引いた太字で示される２次曲線として近似された各曲線に対する１つの制御点の座標を含む第２のセット、すなわちSet A2(14)（第２の元の制御点を検索する為に、上記の重心と共に用いても良い）：
【０１１３】
【数２】
【０１１４】
同時に、コマンドタイプの変換に関する情報はメモリに格納されてもよい。例えば第１の「C」コマンドタイプは「aL」線コマンドタイプにより置換されているか、あるいは第３の「C」コマンドタイプは「aP」線コマンドタイプにより置換されている。例えば、近似コマンドタイプシーケンスMaLaLaPaPaLaLaQzは、元のシーケンスMCCCCCCCzに加えて格納されてもよい。
【０１１５】
この第２のステップに従って、結果として、Set A1、Set A2及びSet Bが近似コマンドタイプシーケンスにより生成された。Set A1は、元のシーケンスと比較して少ないデータを含むが、最も重要なデータを保持する。そのデータは、近似コマンドタイプシーケンスと組み合わせると、近似ＳＶＧパスに対応する。
【０１１６】
Set A1 + A2により、ＳＶＧパスの中間サイズの解像度のバージョンの復元が可能になる。例において、全ての近似コマンドタイプが元の「C」コマンドタイプに対応する一方で、必要に応じて、後述するように、元のタイプが近似タイプから検索される方法を指定する情報の追加の項目はSet A2と関連付けられてもよい。
【０１１７】
Set A1 + A2 + Bにより、ＳＶＧパスのフル解像度レンダリングが可能になる。
【０１１８】
第３のステップにおいて、変倍因子等の符号化パラメータが符号化される。次に、取得された情報セットは、階層符号化方式を使用して符号化される。これは、低解像度の情報セット（ここでは、Set A1）が最初に符号化され、その後このセットに付加される情報（Set A2）がより高い解像度の符号化画像を取得するために符号化され、これは全てのセット（A1、A2及びB）が符号化されるまで継続する。
【０１１９】
例えば、コマンドタイプが最初に符号化される。ここで、２つの実現例が使用されてもよい。
【０１２０】
−全てのコマンドタイプがSet A1の前に直接符号化される（「近似された線、曲線」のような拡張タイプを含む。
【０１２１】
−コマンドタイプの符号化は、２つの部分、すなわちSet A1の符号化の前及び後に分割される。Set A1が制約されるコマンドタイプのセット（点、線、２次曲線、移動、閉じる）を使用するため、これらの制約されるコマンドタイプはSet A1の前に符号化される。例えば、シーケンスMaLaLaPaPaLaLaQzが最初に符号化される。Set A1の符号化後、コマンドタイプの変換に関する情報であり、制約されるセットから元のＳＶＧコマンドセットにする必要がある情報は符号化される（点は何になってもよく、線は曲線になってもよく、２次曲線は３次曲線になってもよい）。例えば、シーケンスMCCCCCCCzが符号化される。
【０１２２】
しかし、元のコマンドの復元を可能にするこの情報の任意の他の表現が使用されてもよい。
【０１２３】
引数（ここでは座標）が処理される。最初にSet A1を符号化し、次にSet A2及びBを符号化する。
【０１２４】
Set A1の各座標は、相対的なSet A1: 165, 380, 20, -151, 105, -37, 101, -30, -9, 183, -24, 119, -71, -182を取得するために、最初に先行する座標に対して算出される。
【０１２５】
同様に、Set A2の値は、Set A1及びSet A2から最も近接する既に符号化された値に従って算出される。その結果、相対的なSet A2: -11, -68, 13, -44, 31, -47, -37, -5, 37, 4, 1, -1, 0, -1, 0, 0, 1, 0, 0, 0, 43, 17, 42, 18, 3, 54, 31, 21, -7, 64が得られる。
【０１２６】
この例から分かるように、相対値は絶対値より小さい傾向がある。これにより、潜在的によりコンパクトな符号化表現が可能になる。
【０１２７】
相対的なSet A1は、残りの値とは非常に異なる大きさを有するために線形符号化される最初の２つの値を除いて、指数ゴロム符号化方式を使用して符号化される。
【０１２８】
指数ゴロム符号は、パラメータkによりパラメータ化されるユニバーサル符号のタイプであり、任意の大きさの整数の符号化を可能にする。符号は、以下のように実現される。
【０１２９】
１）整数Iが正である場合、J=2*Iを算出する。そうでない場合、J=1-2*Iを算出する。
【０１３０】
２）（2^kにより除算されるJ）のバイナリ表現のビットサイズと同数の０ビットを書く。
【０１３１】
３）「1」ビットを書く。
【０１３２】
４）Jのバイナリ表現の最後のkビットを書く。
【０１３３】
指数ゴロム符号のパラメータkは、幾何学的分布パラメータの標準的な推定により推定される。以下の例において、kは７に設定される。
【０１３４】
Set A1は、近似コマンドタイプシーケンスと共に図２の図中符号１３により示される基本レイヤセットを形成する。
【０１３５】
同様に、相対的なSet A2の全体は、例えば５に等しいパラメータkにより指数ゴロム符号化方式を使用して符号化される。
【０１３６】
Set A2は、元のコマンドタイプシーケンス（又は近似タイプからの元のコマンドタイプの復元を可能にする任意の他の情報）と共に図２の図中符号１４により示される復元高解像度レイヤセットを形成する。
【０１３７】
Set Bの全ての値がサブサンプリングパラメータの２乗により制限されるため、Set Bは、線形符号化を使用して符号化される。
【０１３８】
Set Bは、図２の図中符号１２により示される復元フル解像度レイヤセットを形成する。
【０１３９】
本明細書において、ＳＶＧ文書１のパス要素の符号化を説明した。他の要素の符号化は、従来技術の方法により実行される。
【０１４０】
同様に、本発明は複数のパスを含むＳＶＧ文書にも適用される。そのような場合、幾何学的変換を適用するステップ及び変換された縮小シーケンスを符号化するステップが各パスに適用される。従って、文書に対応する符号化データの第１のレイヤが形成される。次に、パス毎に生成される復元情報セットが符号化され、補助レイヤを作成する。このように、階層復号化が容易にされる。
【０１４１】
次に、そのような符号化ＳＶＧ文書の復号化、特に符号化ＳＶＧパス要素の復号化について簡単に説明する。
【０１４２】
そのような復号化方法は、
−近似描画コマンドのＳＶＧパスシーケンスを取得するために符号化ＳＶＧデータから第１のシーケンスを受信及び復号化することと、
−符号化データの新しいレイヤが復号化される必要があるかを判定することと、
−判定が肯定的である場合、符号化ＳＶＧデータから新しいレイヤに対応する情報セットを受信及び復号化することと、
−アップグレードされたパスシーケンスを取得するために、復号化情報セットに基づいて復号化シーケンスの少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換することとを含む。
【０１４３】
更に詳細に考慮すると、復号器は、変倍因子及び選択された符号化オプションを指定する任意のフラグ等のパラメータを復号化し、その後、オプション１（最初に全てのコマンドタイプ情報を取得する）に従うか又はオプション２（レイヤ毎にコマンドタイプを段階的に取得する）を使用してコマンドタイプを復号化することにより開始する。
【０１４４】
基本レイヤ（又は低解像度レイヤ）の復号化は、初期座標を線形復号化することにより開始する。基本レイヤは、指数ゴロム技術を使用して全ての基本レイヤの値を復号化する。このレイヤの復号化の終了時、復号器は相対的なSet A1全体を復号化しており、元のSet A1を復元できる。
【０１４５】
処理時間又はデータの不足により阻止される場合、あるいは低解像度のみが予想される場合、復号器はこの段階において復号化を停止することを決定できる。この場合、新しいレイヤを復号化する上記判定が否定的である場合、処理は、
−少なくとも１つの近似描画コマンドをＳＶＧパス描画コマンドに変換するか又は変換シーケンスを取得するために前記近似描画コマンドを除去することと、
−変換シーケンスに基づいてＳＶＧ画像をレンダリングすることとを含む。
【０１４６】
この点に関して、復号器は以下のように復号化データを更新する必要がある。
【０１４７】
−復号化シーケンスMaLaLaPaPaLaLaQzの近似点「aP」は、データから削除されるか、又は長さがゼロの曲線に変換される。
【０１４８】
−近似線「aL」は、例えばＳＶＧ「L」コマンドを使用して標準的なＳＶＧ線に変換される。近似された２次曲線「aQ」は、標準的なＳＶＧ２次曲線「Q」コマンドに変換される。
【０１４９】
−値は、個々にスーパーサンプリングされるか又は元の値の大きさを回復するためにグローバル変倍因子を使用してスーパーサンプリングされる。
【０１５０】
−レンダリングの高度化に関連して後述されるようにレンダリング品質を向上するために、追加の後処理が実行される。
【０１５１】
復号器が復号化を継続することを決定した場合、復号器は符号化文書における次の符号化レイヤ１４（中間解像度レイヤ又は高解像度レイヤ）を復号化する。
【０１５２】
符号化オプションに依存して、復号器は、例えばシーケンスMCCCCCCCzである追加のコマンドタイプ情報を復号化してもよい。その後復号器は、相対的なSet A2を取得するために指数ゴロム符号化された値を復号化する。
【０１５３】
値のSet A2は復元され、Set Aのサブサンプリングされた元のＳＶＧ座標の算出が可能になる。
【０１５４】
Set Aの解像度が十分である場合、復号器は復号化を停止する。復号器は、例えばグローバル変倍因子を使用して復号化値のスーパーサンプリングを実行する。コマンドタイプシーケンスMCCCCCCCz及びSet Aの値により、従来の方法による高解像度レンダリングが可能になる。
【０１５５】
レンダリング品質を向上するために、追加の後処理が実行可能である。
【０１５６】
ＳＶＧパスのフル解像度が望ましい場合、復号器は継続してSet Bの値（上位レイヤ又はフル解像度レイヤ１２）を復号化する。
【０１５７】
後者は、Set Aから元のＳＶＧパス値を直接復元することを可能にする。
【０１５８】
尚、この段階において、メモリ消費を低減するために最適化技術が使用されてもよい。基本レイヤのみが復号化される場合、メモリの割当てはSet A1の値の正確な数に低減される。これに対して、追加のレイヤが復号化される場合、単一の値バッファが割り当てられ、復号化中に漸進的に満たされる。
【０１５９】
上記例から、本発明を実現する符号器は、レイヤ１２、１３、１４を結合することによりデータセットの品質が向上されることを可能にする最終的なデータセット及びいくつかの追加のデータセットを与える元のＳＶＧパスに対していくつかの連続変換を適用することが分かる。それらの変換のうちの１つは、一般により少ない引数を有し、従ってパスの低解像度レンダリングを認識するために値の数を減少する近似変換である。
【０１６０】
レンダリングするのが非常に高速なコマンドのみ、殆どの場合は点コマンド（この場合、ＳＶＧコマンドは処理されない）又は線コマンドを使用することによりレンダリング処理を更に容易にしてもよい。
【０１６１】
更に、圧縮全体が最適な利用可能なＳＶＧコーデックとほぼ同等に適切なままであるように、特定の連続した変換及び特定の符号化が縮小データセット及び全ての補助データ（又は復元情報セット）に対して提供される。
【０１６２】
復号化側において、復号器は、予想されるレンダリング品質、データの可用性、処理能力又はメモリパワーに基づいて符号化セットの一部を選択的に復号化してもよい。復号器は、低解像度レンダリングを含む部分復号化、並びに復号化処理中にパスレンダリングをリフレッシュする場合は漸進的なレンダリングを提供してもよい。
【０１６３】
本発明の一実施形態について、図３〜図７を参照して説明する。
【０１６４】
図３は、本発明に係る符号化方法の一実施形態の一般的なステップを示すフローチャートである。
【０１６５】
符号化方法は、以下に例示的に詳細を示すような順序付けされた変換のセットを使用する。
【０１６６】
それらの変換の各々は、入力データから２つのデータセット、すなわち縮小データセット及び復元情報セットを生成する。
【０１６７】
縮小データセットは、入力データの近似である。これは、より小さい固有のサイズを有し且つ／又は効率的な符号化に適する。一般に、ＳＶＧパスシーケンスを考慮すると、縮小データ又は縮小シーケンスセットは、コマンドタイプのリスト（一般に、変換の出力における可能なタイプの数は入力より少ない）及び一般に整数として格納される値のリストを含む。
【０１６８】
復元情報セットは、縮小データセットから元のデータセットを算出するために逆変換により使用される。復元情報セットは、縮小データセット及び値（整数として格納される）又は追加の情報（特定のコマンドが絶対的であるか又は相対的であるか等）セットのコマンド毎に使用されるべき逆変換を表す情報セットを含んでもよい。全ての値は、周知の最大値を有する整数として格納されてもよい。
【０１６９】
符号器は、ＳＶＧパスに変換のセットを繰り返し適用する。
【０１７０】
各変換に対して、符号器は復元情報セットを格納し、縮小データセットを次の変換への入力として使用する。
【０１７１】
最後の変換が完了した後、符号器は最初に最終的な縮小データセットを符号化する。
【０１７２】
符号器のセットアップ（可逆的圧縮、符号化ファイルの対象サイズ等）に依存して、符号器は変換により生成された復元情報セットの一部を更に符号化してもよい。
【０１７３】
全ての復元情報セットが符号化される場合、符号化は可逆的である。従って、生成されたレイヤは(n+1)個存在する。nは変換の数である。
【０１７４】
そのような符号化の場合、図３を参照すると、処理はステップＥ１００において符号化するＳＶＧパスデータセット（又はシーケンス）を検索することにより開始する。
【０１７５】
ステップＥ１１０において、変換がデータセットに適用される必要があるかがチェックされる。
【０１７６】
変換がデータセットに適用される必要がある場合、ステップＥ１２０において変換が適用される。変換は、ステップＥ１１０の次の繰り返しに対する新しいデータセットとなる縮小データセットを生成する。変換は、幾何学的近似に従ってデータセットの元の描画コマンドを近似描画コマンドに変換することを含む。対応する復元情報セットは、ＦＩＬＯ（先入れ後出し）スタックに格納される。
【０１７７】
全ての変換が適用された（ステップＥ１１０の出口「ｎｏ」）場合、ステップＥ１３０において、縮小データセット又は縮小シーケンスである最終的なデータセットが符号化される。
【０１７８】
その後、ＦＩＬＯスタックに格納される一部の復元情報セット又は各復元情報セットは、順次符号化され、符号化後にスタックから除去され（ステップＥ１４０及びステップＥ１５０）、処理は終了する（ステップＥ１６０）。
【０１７９】
結果として得られる符号化文書において、第１のレイヤ（又は基本レイヤ）は縮小データであり、他のレイヤは、変換により生成された各復元情報セットであり、生成された順序と逆の順序で格納される。
【０１８０】
不可逆的圧縮が許可される場合、符号化処理は、全てのスタック項目が符号化される前（例えば、所定の数のスタック項目の符号化の後又は最小誤り距離のような基準が満たされた時）に停止してもよい。
【０１８１】
効率的な符号化を提供するために、本発明の１つの変換は、後で更に詳細に説明するようにＳＶＧコマンドを近似コマンドに変換する近似変換である。
【０１８２】
書き換え変換及び／又は量子化変換等の他の変換は、殆どの場合に有用であるが、種々の例において、例えばデータが既に低解像度データである場合においてオプションであってもよい。
【０１８３】
図４を参照して、本発明に係る符号化方法の詳細な一実施形態を説明する。本実施形態において、符号器は以下の順番で３つの変換を適用する。
【０１８４】
−ＳＶＧパスを全ての絶対値又は全ての相対値に変換するＳＶＧパスを簡略化するための書き換え変換
−データを低解像度データ及び高解像度データに分割するための量子化又はサブサンプリング変換であり、一般には線形変換
−低解像度データを２つの追加のレイヤ、すなわち更に低い解像度のデータセット及び復元（更に高い解像度に対する）情報セットに分割するための近似変換
図４の第１のステップＥ２００において、符号化するＳＶＧパス２０が取得される。
【０１８５】
ステップＥ２１０において、オプションとしてパスデータは書き換えられ、より簡略化され且つ同等にレンダリングされるＳＶＧパスのバージョンを得る。２つの書き換え動作は、組み合わせて実行されてもよく又はいずれか一方が実行されてもよい。
【０１８６】
第１の書き換え動作は、ＳＶＧパスシーケンスの全ての値を相対値のみ又は絶対値のみに書き換えることに関係する。
【０１８７】
例えば全ての座標の値を相対値として書き換える場合、このステップは、大文字のコマンドタイプ名を小文字のコマンドタイプ名で置換することにより、例えば「C」を「c」にすることにより、最初にコマンドタイプ名を更新することを含む。
【０１８８】
第２に、全ての絶対座標は、それらの絶対座標及びＳＶＧパスの先行座標から算出される相対座標により置換される。例えばパス「M 100 100 L 200 150 L 100 150 L 100 100」は、相対パス「m 100 100 l 100 50 l -100 0 l 0 -50」により置換される。
【０１８９】
これは、使用されるコマンド数を減少するという第１の利点を有する。更に一般に、相対座標の値は対応する絶対座標の値より小さい。また、全ての座標がより均一である。
【０１９０】
尚、ＳＶＧ仕様書によると、第１のパスコマンドが相対パスコマンドである場合、絶対コマンドとして解釈される。これにより、前処理ステップは、全てのコマンド、最初のコマンドであっても書き換えが行なえる。
【０１９１】
第２の書き換え動作は、パス中の各コマンドに対して最適なコマンド形式を使用することである。いくつかのコマンドは、特定の例に対してショートカットを有する。例えば「lineto」コマンドは、線が水平（又は垂直）である場合に「horizontal-lineto」（又は「vertical-lineto」）ショートカットを有する。この書き換え方式を適用することにより、コマンド「l 5 0」は、情報がより少ない同等のコマンド「h 5」により置換される。従って、同等のコマンドは同一の図の結果を生成するコマンドとして理解される。
【０１９２】
各例に対して最も固有のコマンドを使用することにより、元のパス中の引数の数が減少される。
【０１９３】
このステップＥ２１０の書き換え変換は、書き換えられたＳＶＧパス２１及び書き換えられた形式から元の形式にすることを可能にする復元情報２２を生成する。それらのパス及び情報は、次の処理ステップのためにメモリに格納される。一般にこの追加の情報は、相対的であるか又は絶対的であるかを指定する各コマンドに対するブール値から構成されてもよい。h又はvコマンドの場合、元々hコマンドであるか、vコマンドであるか又はlコマンドであるかを指定できる。
【０１９４】
算術符号化技術又は同様の技術は、この種のデータを圧縮するために使用されてもよい。効率的な一実現例において、全ての値は絶対値として書き換えられ、パスデータサブサンプリング変換を容易にする。
【０１９５】
ステップＥ２１０に続き、ステップＥ２２０において、書き換えられたパス値はサブサンプリングされる。そのために、上述したように、ＳＶＧパスは構文解析され、パラメータ、コマンドタイプシーケンス（全てのパスコマンドのセット）及び引数値を別個に一覧表示するように再構成される。
【０１９６】
図５は、座標値の絶対表現に対するサブサンプリングを示す。より効率的にするために、上述したように、ステップＥ２１０において座標の値のみがサブサンプリングされる。半径又は軸等の他の引数は実際には符号化される。しかし、特定の一実施形態において、これらの他の引数もサブサンプリングされてもよい。
【０１９７】
実質的な視覚的なアーチファクトをもたらす付加的な丸め雑音を含まないようにするために、絶対表現が使用される。
【０１９８】
サブサンプリングパラメータを仮定すると（ステップＥ３００）、処理する値が存在する限り（ステップＥ３１０）、ステップＥ３２０において、その絶対値が検索される（又は相対値として利用可能である場合は算出される）。
【０１９９】
ステップＥ３３０において、この絶対値は、サブサンプリング因子に従って量子化され、絶対サブサンプリング値を得る。
【０２００】
サブサンプリング値から元の値を得ることを可能にするスーパーサンプリング情報（これは、実際には元の値とサブサンプリング値又は量子化値との間の差分である）は、ステップＥ３４０において算出及び格納される。相対サブサンプリング値は、ステップＥ３５０において算出及び格納される。
【０２０１】
処理される必要がある値が更に存在しない場合、処理はステップＥ３６０において終了する。
【０２０２】
ステップＥ２２０の結果として、全ての値のセットが２つのセット、すなわちコマンドタイプシーケンスと組み合わされる場合に低解像度データセット２３及びスーパーサンプリング情報２４に対応するサブサンプリングされた相対座標値又は絶対座標値に分割される。後者、すなわち復元情報セットにより、低解像度から元の値又は元の値に非常に近い値を得ることが可能になる。
【０２０３】
更なるセットが予想される場合、同一の処理が繰り返される。
【０２０４】
ステップＥ２２０に続き、ステップＥ２３０において、パスコマンドはそれらのタイプ及び値に従って近似される。
【０２０５】
本発明の一実施形態において、図６を参照すると、分類はコマンドを３つの潜在的な「近似」タイプ、すなわち点、線及び２次曲線として近似することから成る。
【０２０６】
これらの３つの潜在的な「近似」コマンドタイプのうちの１つにおける図１に示す３次曲線の近似について以下に説明する。
【０２０７】
本発明はこの近似に限定されないことが理解される。説明するために、任意のＳＶＧコマンドは、より少ない引数を使用するＳＶＧコマンド又は点近似コマンドに近似されてもよい。例えば、線コマンドは点コマンドに近似され、２次曲線コマンドは線又は点コマンドに近似され、弧曲線コマンドは２次曲線、線又は点コマンドに近似される。
【０２０８】
しかし、コマンドタイプ「M／m」及び「Z／z」は近似されず、ステップＥ２３０の結果として得られる近似コマンドタイプを一覧表示することを目的とする近似コマンドタイプシーケンスに追加される。
【０２０９】
点、線又は２次曲線等のより単純なコマンドへの３次ベジェ曲線コマンドの幾何学的近似に戻ると、この近似は以下のことを可能にする。
【０２１０】
−近似コマンドの値の数を減少する。
【０２１１】
−近似コマンドのレンダリングを簡略化する。
【０２１２】
理解されるように、近似された点は、形状の輪郭が同一の点に残っているため、値符号化を必要としない。線は２つの値（１つの座標）の符号化を必要とし、２次曲線は４つの値の符号化を必要とする。
【０２１３】
尚、点、線及び２次曲線のレンダリングは、復号器側において一般的な３次曲線と比較して高速である。一般に、点はレンダリングされる必要がない。線のレンダリングは２次曲線より高速であり、２次曲線のレンダリングは３次曲線より高速である。この近似処理は、滑らかな３次曲線として３次曲線を近似するように容易に拡張可能であり、これにより座標値の数を６から４に減少する。
【０２１４】
パスの各コマンドの近似処理は、そのコマンドを検索することによりステップＥ４００において開始する。
【０２１５】
ステップＥ４１０において、コマンドが線として近似されるかが判定される。このテストは、以下のように種々の方法で実現可能である。
【０２１６】
第１の方法において、最初に元のコマンド曲線の任意の点と近似曲線（線、２次曲線、滑らかな３次曲線）との間の最大距離が算出される。この距離は、所定の閾値と比較され、どの近似が最適な近似であるのかを判定する。
【０２１７】
３次曲線からその近似線までの距離は、線(x-xe, y-ye)に対する垂直線上のベクトル(x-x2, y-y2)及びベクトル(x1-xe, y1-ye)の正射影ノルムとして推定される。これらのノルムは、ベクトル(x1-xe, y1-ye)（(x-x2, y-y2)）とベクトル(x-xe, y-ye)との間のベクトル積から算出される。表１は、ベクトル(x1-xe, y1-ye)に対して算出された距離（距離１）及びベクトル(x-x2, y-y2)に対して算出された距離（距離２）の結果を示す。
【０２１８】
これらの２つの距離が認識されると、例えば上記表に示すように、例えば双方の距離が所定閾値を下回る場合、コマンドは線として近似される。計算を制限するために、一般に閾値には、パスに対して許容される最大偏差が選択される。
【０２１９】
上記距離に対する別の基準、例えば(x1-xe, y1y-e)、(x2-x1, y2-y1)及び(x-x2, y-y2)の符号化と比較して(x-xe, y-ye)、(x1-xe, y1-ye)及び(x-x2, y-y2)を符号化することにより引き起こされる潜在的な圧縮損失が使用可能である。
【０２２０】
コマンドが線として近似可能である（ステップＥ４１０において出口「ｙｅｓ」）の場合、ステップＥ４２０において、コマンドが引数のより適切な圧縮を行なえる点として近似可能であるかがテストされる。
【０２２１】
このテストＥ４２０は、ベクトル(x1, y1)、(x, y)及び／又は(x-x2, y-y2)のノルムのサイズに基づく。
【０２２２】
これらのノルムが所定の閾値を下回る場合、ステップＥ４３０において、コマンドは点として近似される。これは、近似点コマンド「aP」が近似コマンドタイプシーケンスに追加されることを意味する。更に全ての３つの座標(x1, y1)、(x2, y2)及び(x, y)は復元情報セットに入れられ、このコマンドの値は縮小データセットに保持されない。
【０２２３】
ステップＥ４２０において否定的な応答の場合、ステップＥ４４０においてコマンドは線として近似される。そのような場合、近似線コマンド「aL」は近似コマンドタイプシーケンスに追加され、(x, y)座標のみが縮小データセットに保持され、(x1, y1)及び(x2, y2)座標は復元情報セットに入れられる。
【０２２４】
あるいは、ステップＥ４５０において、３次曲線コマンド「C」は簡略化されたベジェ曲線として、一般には２次曲線として近似される。
【０２２５】
そのような場合、２次曲線に対する特定の制御点が算出される。座標(x1, y1)及び(x2, y2)の重心(xm, ym)は、十分に適切なレンダリング近似であり、グローバル圧縮に関しても適切であるため選択される。(xm, ym)及び(x, y)は縮小データセットに追加され、近似２次曲線コマンド「aQ」は近似コマンドタイプシーケンスに追加される。
【０２２６】
次に、x1又はx2及びy1又はy2は、(x, y)への(xm, ym)の近似に基づいて復元情報セットに追加される。重心が曲線の開始点に近接する場合、x1及びy1が選択される。重心が(x, y)に近接する場合、x2及びy2が選択される。
【０２２７】
いくつかの曲線が滑らかな３次曲線として近似可能であり、この場合、(x2, y2)値のみが縮小データセットに保持される。
【０２２８】
ステップＥ４６０において、結果として得られる近似コマンドタイプ及び選択された値を格納する。
【０２２９】
ステップＥ４７０において、選択されない値及び近似前の元のコマンドタイプに関する情報は、復元情報セットに共に格納される。
【０２３０】
これらのステップの結果、２つのデータセットが構築される。
【０２３１】
−制限されたコマンドタイプセット及び値の小さなセットを有する近似コマンドを含む縮小データセット２５。このデータセットは、基本レイヤにおいて符号化されたデータである。
【０２３２】
−近似データ（縮小データセット２５の）から元のデータを得ることを可能にする復元情報セット２６。一般に、この復元情報セットは、元のコマンドタイプ及び除去された値を含み、第２のレイヤにおいて符号化される。
【０２３３】
実際には、３次曲線「C」コマンドは線として近似される場合が多い。これは、６つの引数値から２つの引数値に減少される場合が多いことを意味する。
【０２３４】
図４ａは、種々のデータセット２０〜２６が逐次的に生成される方法を示す。
【０２３５】
図３に戻ると、ステップＥ２３０の次にステップＥ２４０が続き、方法の符号化部分を開始する。
【０２３６】
ステップＥ２４０において、最初に符号化パラメータを書く。
【０２３７】
これらの符号化パラメータは、変倍因子、使用されるサブサンプリング比、特定の内部符号化パラメータ（ハフマンテーブルＩＤ、指数ゴロムパラメータ等）を含んでもよい。
【０２３８】
ステップＥ２５０において、ステップＥ２３０からの縮小データセット２５は基本符号化レイヤ２５’として符号化される。
【０２３９】
基本レイヤのデータは、コマンドタイプ（線、曲線等）のセット２５’ａ及び値のセット２５’ｂ（上記例においてはSet A1）を含む。
【０２４０】
基本レイヤにおけるコマンドタイプは、ＳＶＧコマンドタイプより小さいコマンドタイプのセットである。これらのコマンドは、例えば事前定義済みハフマンテーブルを使用するハフマン符号化である一般的な可逆的圧縮技術を使用して符号化される。
【０２４１】
一般に、近似線は２次曲線より一般的である。近似点は、サブサンプリングに大きく依存する。
【０２４２】
従って、いくつかのハフマンテーブルが規定され、最適なテーブルが符号器により選択される。
【０２４３】
他の技術（算術符号化、予測部分マッチング等）も使用可能である。
【０２４４】
近似コマンドの符号化に従って、座標値が符号化される。
【０２４５】
これらの値は、互いに対して符号化される。これらの値は、一連のx値及びy値として考えられる。指数ゴロム符号化を使用して、値xnは値xn-1に関連して符号化され、値ynはyn-1に従って符号化される。この符号化は、パラメータkを入力とする。このパラメータは、値の幾何学的分布に基づいて算出される。値セットが既にサブサンプリングされているため、最適な値kは、一般にゼロに近い値であり、多くの場合ゼロに等しい。
【０２４６】
x0及びy0は、任意の値をとることができるため線形符号化される。
【０２４７】
指数ゴロム符号の値kがゼロでない場合、符号化値は２つのストリームに分割されてもよい。第１のストリームは上位情報（すなわち、2kで除算される値）を含み、第２のストリームは下位情報（すなわち、値のバイナリ表現の最後のkビット）を含む。
【０２４８】
ステップＥ２５０に続き、オプションのステップＥ２６０において、近似値２５からサブサンプリング値２３を得ることを可能にする復元情報セット２６が符号化される（符号化部分２６’が取得される）。これは、相対値による指数ゴロム符号化を使用する上述したようなSet A2の符号化に対応する。
【０２４９】
サブサンプリングされた復元データ２６は、コマンドタイプを復元するのに必要な情報及び近似処理が実行される前の値の双方を含む必要がある。
【０２５０】
このデータを処理する時に基本レイヤが既に復号化されているため、近似コマンドタイプは認識されている。この近似コマンドタイプは、利用可能なコマンドセットを制限するために使用される。
【０２５１】
例えば、近似２次曲線は、線ではなく２次曲線又は３次曲線のみをもたらす可能性がある。元のコマンドタイプは、ハフマン符号化を使用して近似コマンドタイプに従って符号化される。コマンドタイプの符号化部分２６’ａが取得される。他の技術（算術符号化、予測部分マッチング等）も使用可能である。
【０２５２】
元の座標値は、基本レイヤの座標値に従って符号化される。点の場合、全ての元の値は、基本レイヤの値に対して行なわれたように、一般にゼロであるパラメータkにより指数ゴロム符号化を使用して符号化される。値の符号化部分２６’ｂが取得される。
【０２５３】
線として近似された曲線に対して、(x1, y1)及び(x2, y2)が符号化される。(x1-xe, y1-ye)は、小さい必要があるため指数ゴロム符号化を使用して直接符号化され、(x-x2, y-y2)は、(x2, y2)が既に認識されている(x, y)に近接する必要があるため、指数ゴロム符号化を使用して符号化される。
【０２５４】
近似２次曲線の場合、(x1, y1)(x2, y2)の重心(xm, ym)が認識されているため、(x1, y1)又は(x2, y2)のみが符号化され、残りの座標は(xm, ym)から算出される。指数ゴロム符号化を使用して最小である可能性がある値を符号化するために、以下のアルゴリズムが使用される。
【０２５５】
−(xm, ym)が(x, y)より(0, 0)に近接する場合、指数ゴロムを使用して(x1, y1)を符号化する。
【０２５６】
−(xm, ym)が(0, 0)より(x, y)に近接する場合、指数ゴロムを使用して(x-x2, y-y2)を符号化する。
【０２５７】
ステップＥ２６０の後、ステップＥ２７０において、スーパーサンプリング情報２４（上記例においてはSet B）がオプションとして符号化され、元の書き換えられたパスデータ２１の復元を可能にする。符号化スーパーサンプリング情報部分２４’は、符号化文書３０において取得される。
【０２５８】
スーパーサンプリング情報は、あるコマンドタイプ情報を含んでもよく、その場合、データ復元情報に対して使用されるような符号化技術が使用される。
【０２５９】
あるいは、スーパーサンプリング情報は、２つの技術、すなわち指数ゴロム及び線形符号化の組合せにより符号化可能である。指数ゴロム符号化は、特にスーパーサンプリング情報が１画素より大きい情報を含む場合、スーパーサンプリング情報の前の値がゼロである時に使用される。
【０２６０】
あるいは、スーパーサンプリング情報が束縛値（2n、nはサブサンプリング因子である）を有する整数から成るため、線形符号化が使用可能である。
【０２６１】
スーパーサンプリング情報量が大きい場合、例えば符号化値が２５６より大きい場合、このスーパーサンプリング情報はいくつかのサブレイヤに分割される。
【０２６２】
符号化処理は、ステップＥ２８０に継続し、オプションとして復元に対する書き換え情報２２は、元のパスシーケンスの忠実な復元を可能にするように部分２２’に符号化される。
【０２６３】
符号化処理のこれらのオプションのステップにより、符号化ＳＶＧ文書のサイズを縮小できる。従って、特に送信ネットワーク帯域幅が小さい場合又は記憶容量が小さい場合、符号化ＳＶＧ文書の送信はより効率的になる。
【０２６４】
図４ａは、符号化ＳＶＧパスに対応する連続する符号化部分２５’、２６’、２４’、２２’を含む結果として得られる符号化ＳＶＧ文書３０の部分を示す。図示するように符号化部分を順序付けることにより、基本レイヤが最初に符号化ストリームにあるため、復号器は実行中に画像を復号化してもよい。従って、実行中の漸進的なレンダリングが可能である。
【０２６５】
ＳＶＧ文書がいくつかのパスを含む場合、最初にパス毎に符号化された基本レイヤ及びその後パス毎の後続するレイヤを復号化することにより、漸進的な復号化は文書全体に対して達成されてもよい。
【０２６６】
図７を参照して復号化側を考慮すると、復号器は、復号化する所定の符号化ＳＶＧパス３０を検索することによりステップＥ５００において開始する。
【０２６７】
このデータは、全ての符号化レイヤ２５’、２６’、２４’、２２’を含んでもよく、あるいは復号化開始時にそれらの一部のみを含んでもよい。
【０２６８】
復号器は、ステップＥ５１０において符号化パラメータ（サブサンプリング、変倍因子等）を抽出する。
【０２６９】
ステップＥ５２０において、復号器は予想されるレンダリング品質又は予想される表示解像度に従って復号化するレイヤを選択する。
【０２７０】
例えばサムネイルのみが要求される場合、最低限の復号化が実行される。その一方で、ＳＶＧ文書のフル解像度表現が予想される場合、全てのデータが復号化されるべきである。
【０２７１】
ステップＥ５３０及びＥ５４０は、文書３０の部分２５’に対応する基本レイヤの復号化を実行する。各レイヤの復号化は、各レイヤの符号化に関して対称的である。
【０２７２】
基本レイヤの復号化は、基本レイヤのコマンドタイプ２５’ａを復号化することによりステップＥ５３０で開始する。
【０２７３】
復号器は、コマンドに基づいて、適切な指数ゴロムパラメータを仮定してステップＥ５４０において基本レイヤの値２５’ｂを復号化する。これは、各近似コマンドタイプが事前定義済みの数の引数を有するためである。
【０２７４】
ＳＶＧ復号器が基本レイヤの直後に復号化を停止することを認識している場合、ＳＶＧ復号器は、制限された値（点に対する値はなく、各線に対しては２つの値があり、各２次曲線に対しては４つの値がある）に対してのみ配列を割り当てることを決定してもよい。あるいは、次のレイヤ（復元レイヤ２６’、スーパーサンプリングレイヤ２４’及び書き換えレイヤ２２’）で復号化される値を格納するための十分なメモリが割り当てられてもよい。
【０２７５】
第１の例は、潜在的に実質的なメモリ消費の低減を可能にする。
【０２７６】
更に線及び２次曲線のみがレンダリングされるため、レンダリング処理はより高速である。
【０２７７】
基本レイヤのデータを直接レンダリングするために、データのスーパーサンプリングはサブサンプリングパラメータに従って実行される。例えばこれは、変倍因子をサブサンプリングパラメータの２乗と乗算することにより行なわれる。
【０２７８】
復号化処理の時点で、復号器はユーザに対してＳＶＧ画像を予備表示するためにＳＶＧパスの低解像度バージョンをレンダリングしてもよい。そのような場合、表示を可能にするための後処理は後述するように実行されてもよい。これにより、データ全体が復号化される前に予備表現をユーザに提供できる。
【０２７９】
復号器は、パスの全体の品質を向上する必要がある限り復号化を継続する。
【０２８０】
ステップＥ５５０において、復号器は、復号化する追加のレイヤが存在するか及びそれを復号化すべきかをチェックする。
【０２８１】
追加のレイヤが存在し且つそれを復号化すべきである場合、ステップＥ５６０において復号器は追加のレイヤを復号化する。
【０２８２】
復号化する第１の追加のレイヤは、復元レイヤ２６’であってもよい。その復号化は、基本レイヤにおいて符号化されていないコマンド値２６’ｂ及びコマンドタイプを更新／詳述するための情報２６’ａを復号化することから成る。
【０２８３】
このステップ中、レイヤ２６’の復号化データはステップＥ５３０及びＥ５４０の復号化データと組み合わされ、サブサンプリングデータ２３、すなわちアップグレードされたパスデータセットを復元する。
【０２８４】
他のレイヤ２４’及び２２’は、逐次的に復号化され、書き換えパスシーケンス２１及び元のＳＶＧパスシーケンス２０を逐次的に復元してもよい。
【０２８５】
ここでも、レイヤが復号化される度、表示はアップグレードされたパスデータ２３、２１及び２０により漸進的に更新されてもよい。ユーザは、ＳＶＧ画像を表示する前に全てのレイヤが復号化されるのを待つのよりはるかに速くフィードバックを提供される。
【０２８６】
復号器はステップＥ５５０に戻る。
【０２８７】
全ての要求されるレイヤが復号化されると、ステップＥ５７０において復号器はデータを後処理する。
【０２８８】
この後処理は、パスデータの変倍であってもよく又はデータのスーパーサンプリングであってもよい。
【０２８９】
最後に、復号化ＳＶＧパスデータが取得され、ステップＥ５８０において例えば表示するために使用される。
【０２９０】
尚、近似コマンドタイプを含むレイヤのレンダリングに対して、ＳＶＧコマンドタイプでないそれらのタイプは、ＳＶＧ復号器に準拠するように変換される必要がある。例えば「L」ＳＶＧコマンドへの「aL」コマンドの変換である。「aP」コマンドは除去され、「aQ」コマンドは「Q」ＳＶＧコマンドに変換される。
【０２９１】
本発明の一実施形態において、基本レイヤのレンダリングは、変換の性質を考慮する特定の技術により実質的に向上されてもよい。これらの技術がある処理時間及び処理能力を消費するにも関わらず、データの読み出しがデータの処理より遅い場合、一般に帯域幅が小さい場合又はボリュームが大きい場合に特に適する。
【０２９２】
これらの技術は以下により構成されてもよい。
【０２９３】
−平滑化を線に適用することによる線形／３次予測。視覚的により快適なレンダリングが容易に達成される。
【０２９４】
−２次制御点の自動射影に加えて平滑化変換が適用される２次／３次予測。
【０２９５】
上記から、本発明がＳＶＧパスに対して効率的な符号化方法を提供することが示される。
【０２９６】
−ＳＶＧパスの階層符号化及び復号化を可能にし、その結果、部分復号化及び漸進的なレンダリングを可能にする。
【０２９７】
−圧縮に関して最適な利用可能なコーデックとほぼ同等に適切な可逆的圧縮。
【０２９８】
図８を参照して、本発明に係る方法の一実現例に適応された情報処理装置の特定のハードウェア構成の例として説明をする。
【０２９９】
本発明を実現する情報処理装置は、例えば種々の周辺装置に接続されるマイクロコンピュータ４０、ワークステーション、パーソナルアシスタント又は移動電話である。本発明の更に別の実施形態によると、情報処理装置は、ネットワークへの接続を可能にする通信インタフェースを備えるカメラの形態をとる。
【０３００】
情報処理装置に接続される周辺装置は、例えば入出力グラフィックスカード（不図示）に接続され且つ情報処理装置にマルチメディアデータを供給するデジタルカメラ６０又はスキャナ、あるいは画像を取得又は格納する任意の他の手段を含む。
【０３０１】
装置４０は、通信バス４１を含み、通信バス４１には、
−例えばマイクロプロセッサの形態をとる中央処理装置ＣＰＵ４２と、
−本発明に係る方法の実現を可能にするために実行されるプログラムを含んでもよい読み出し専用メモリ４３と、
−装置４０の電源投入後に、本発明のプログラムの実行可能コード、並びに本発明の実現に必要な変数及びパラメータを記録するように構成されるレジスタを含むランダムアクセスメモリ４４と、
−キーボード４６、あるいは例えばマウス４７又は光学スタイラスであるポインティングデバイス等の任意の他の手段を使用して本発明に係るプログラムと対話してもよいユーザとのグラフィカルインタフェースの役割を果たし且つ／又はデータを表示する画面４５と、
本発明の実現例に基づいて使用又は生成されるデータに加えて本発明のプログラムを含むことができるハードディスク４８又はコンパクトフラッシュカード等の記憶メモリと、
−外部ディスク７０を受け入れ且つ本発明に従って処理されたか又は処理されるデータに対して読み出し／書き込みを行なうように構成される光ディスクドライブ４９又は取り外し可能データ記憶媒体に対する別のリーダと、
−電気通信ネットワーク８０に接続され且つデジタルデータを送信及び受信するように構成される通信インタフェース５０とが接続される。
【０３０２】
通信バス４１は、装置４０に含まれるか又は装置４０に接続される種々の要素間の通信及び相互運用を可能にする。バス４１の表現は限定されず、特に中央処理装置４２は、装置４０の任意の要素に命令を直接通信してもよく又は装置４０の別の要素を使用して通信してもよい。
【０３０３】
外部ディスク７０は、書き換え可能又は書き換え不可能なコンパクトディスク（ＣＤ−ＲＯＭ）、ＺＩＰディスク又はメモリカード等の任意の情報記憶媒体であってもよい。一般に、マイクロコンピュータ又はマイクロプロセッサにより読み出し可能であり、情報処理装置に組み込まれるか又は組み込まれず且つ取り外し可能であってもよい情報記憶手段は、実行されることにより本発明に係る方法の実現を可能にする１つ以上のプログラムを格納するように構成される。
【０３０４】
情報処理装置が本発明を実現することを可能にする実行可能コードは、上述したように、読み出し専用メモリ４３、ハードディスク４８又は外部ディスク７０等の取り外し可能デジタル媒体に同等に適切に格納される。一変形例によると、プログラムの実行可能コードは、電気通信ネットワーク８０の仲介により、すなわちインタフェース５０を介して受信され、実行前に装置４０の記憶手段のうちの１つ（ハードディスク４８等）に格納される。
【０３０５】
中央処理装置４２は、本発明の１つ又は複数のプログラムのソフトウェアコードの命令又は一部の実行を制御及び指示する。ソフトウェアコードの命令又は一部は上述の記憶手段のうちの１つに格納される。装置４０の電源投入時、例えばハードディスク４８又は読み出し専用メモリ４３である不揮発性メモリに格納される１つ又は複数のプログラムは、本発明の１つ又は複数のプログラムの実行可能コードを含むランダムアクセスメモリ４４、並びに本発明の実現に必要とされる変数及びパラメータを格納するためのレジスタに転送される。
【０３０６】
尚、本発明を実現するか又は本発明を組み込む装置は、プログラムされた装置の形態で実現されてもよい。例えばそのような装置は、特定用途向け集積回路（ＡＳＩＣ）に固定形式でコンピュータプログラムのコードを含んでもよい。
【０３０７】
本明細書で説明する装置及び特に中央処理装置４２は、図３〜図７に関連して説明した処理動作の全て又は一部を実現し、本発明の各方法を実現し且つ本発明の各装置を構成してもよい。
【０３０８】
先の例は、本発明の単なる実施形態であり、本発明はそれらに限定されない。
【０３０９】
特に、詳細な説明が固有の近似変換（ステップＥ２３０）を示すが、そのような変換のいくつかは結果として得られる縮小データセット２５に対して繰り返されてもよい。これにより、更に多くのレイヤを生成してもよく、特定のディスプレイ又はレンダリング装置に対する最適なレンダリングを取得するために復号器に対してより多くの解像度の選択肢が生成されてもよい。
【０３１０】
そのような場合、いくつかの近似変換は、ステップＥ２３０で使用される閾値に関して異なり、特定の近似描画コマンドを考慮してもよい。最初に高解像度レイヤ及び対応する復元情報セットを生成するために小さな値が使用されてもよく、その後、低解像度レイヤを生成するためにより大きな値が使用されてもよい。
【０３１１】
あるいは、近似コマンドセットは、繰り返しが進むのに伴って変更及び縮小されてもよい。
【０３１２】
別の態様によると、１つのＳＶＧパスの階層符号化を説明したが、一般にＳＶＧ文書の符号化はいくつかのパスの符号化を含む。本発明は、ＳＶＧ文書全体がレイヤとして符号化されるように容易に拡張可能である。
【０３１３】
そのような場合、ＳＶＧ文書が一般に符号化される。ＳＶＧパスデータは、基本レイヤの情報のみを含む。文書のＳＶＧパスの連結された第２のレイヤは符号化文書の最後に挿入され、その後、第３のレイヤが第２のレイヤの後に挿入される。
【０３１４】
この階層技術に基づいて、符号化パラメータを注意深く選択することにより、レイヤは適切なサイズで構築される。第１のレイヤは非常に小さなメモリ量を有し、更なるレイヤは、同等のサイズを有するか、サイズが徐々に増加する。これにより、ＳＶＧデータ送信及び漸進的なレンダリングの管理が更に容易になる。
【特許請求の範囲】
【請求項１】
グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンス（２０、２３）を含むパス（１）を符号化する方法であって、
−縮小シーケンス（２５）を取得するために、描画の対応する元の部分の幾何学的近似に従って、少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップ（Ｅ１２０、Ｅ２３０、Ｅ４３０、Ｅ４４０、Ｅ４５０）と、
−前記縮小シーケンス（２５）を符号化縮小シーケンスに符号化するステップ（Ｅ１３０、Ｅ２５０）と、
−前記縮小シーケンス（２５）と前記元のシーケンス（２０、２３）との間の差分を表す復元情報セット（２６）を符号化するステップ（Ｅ１５０、Ｅ２６０）と
を備えることを特徴とする方法。
【請求項２】
描画コマンドは、描画コマンドタイプ及び引数を含み、前記近似描画コマンドは前記元の描画コマンドより少ない引数を含むことを特徴とする請求項１記載の方法。
【請求項３】
前記変換するステップ（Ｅ１２０、Ｅ２３０、Ｅ４３０、Ｅ４４０、Ｅ４５０）は、前記元の描画コマンドに対応する前記描画と前記近似描画コマンドに対応する前記描画との間の距離を計算することと、前記計算した距離を少なくとも１つの閾値と比較することとを含むことを特徴とする請求項１又は２記載の方法。
【請求項４】
前記復元情報セット（２６、２６’）は、
−各々が種々の近似描画コマンドタイプに変換される前記元の描画コマンドタイプ（２６’ａ）と、
−前記近似描画コマンドに保持されていない前記元の描画コマンドの引数（２６’）及び／又は前記元の描画コマンドの前記引数から計算され且つ前記近似描画コマンドに保持されていない引数の検索を可能にする引数（２６’）と
を備えることを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
幾何学的近似に従う近似変換（Ｅ２３０）を含む前記元のシーケンスの複数の反復変換（Ｅ２１０、Ｅ２２０、Ｅ２３０）を含み、
前記最後の変換（Ｅ２３０）の結果として得られる前記縮小シーケンス（２５）が符号化され（Ｅ２５０）、前記変換の前記復元情報セット（２２、２４、２６）のうちの少なくとも１つが符号化される（Ｅ２６０、Ｅ２７０、Ｅ２８０）ことを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
前記復元情報セット（２２、２４、２６）の各々が符号化されることを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
前記近似変換（Ｅ２３０）の前の変換は、描画コマンドをより少ない引数を有する同等の描画コマンドにより置換することにより前記元のパスシーケンス（２０）を書き換えること（Ｅ２１０）を含むことを特徴とする請求項５又は６記載の方法。
【請求項８】
前記近似変換（Ｅ２３０）の前の変換は、サブサンプリングシーケンス（２３）及び前記サブサンプリングシーケンスから前記元のシーケンス又は前記書き換えられたシーケンスの復元を可能にする前記スーパーサンプリング情報を含む前記復元情報セット（２４）を取得するために、前記元のシーケンス（２０）又は前記書き換えられたシーケンス（２１）をサブサンプリングするステップ（Ｅ２２０）を含むことを特徴とする請求項５乃至７のいずれか１項に記載の方法。
【請求項９】
前記縮小シーケンス（２５）は、任意の復元情報セット（２２、２４、２６）の前に最初に符号化されることを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記縮小シーケンス（２５）は、前記縮小シーケンス内の前記コマンドの引数に対応する値のシーケンスを含み、
前記縮小シーケンスの第１の座標の値は絶対値として線形符号化され、他方の座標の値は前記シーケンス内の先行座標の値に対して符号化されることを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
グラフィックス記述言語で図形を表す符号化データ（３０）を復号化する方法であって、
−近似描画コマンドのグラフィックスパスシーケンス（２５）を取得するために前記符号化データ（３０）から第１のシーケンス（２５’）を受信し（Ｅ５００）且つ復号化する（Ｅ５３０、Ｅ５４０）ステップと、
・ 符号化データの新しいレイヤが復号化される必要があるかを判定するステップ（Ｅ５５０）と、
−肯定的な判定の場合に、
・ 前記符号化データ（３０）から新しいレイヤに対応する情報セット（２６’、２４’、２２’）を受信及び復号化し（Ｅ５６０）、
・ アップグレードされたパスシーケンス（２３、２１、２０）を取得するために、前記復号化情報セット（２６、２４、２２）に基づいて前記復号化グラフィックスパスシーケンス（２５）の少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換するステップと
を備えることを特徴とする方法。
【請求項１２】
情報セット（２６’、２４’、２２’）を受信及び復号化するステップ（Ｅ５６０）及び変換するステップは、符号化データの新しいレイヤが復号化される必要がある限り前記アップグレードされたパスシーケンスに対して繰り返されることを特徴とする請求項１１記載の復号化方法。
【請求項１３】
否定的な判定（Ｅ５５０）である場合、
−変換シーケンスを取得するために、少なくとも１つの近似描画コマンドを前記グラフィックス記述言語のパス描画コマンドに変換するか又は前記近似描画コマンドを除去することと、
−前記変換シーケンスに基づいて画像をレンダリングすることと
を備えることを特徴とする請求項１１又は１２記載の復号化方法。
【請求項１４】
前記近似描画コマンドの前記除去は、前記近似描画コマンドが点コマンドに対応する場合に実行されることを特徴とする請求項１３記載の復号化方法。
【請求項１５】
グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンス（２０、２３）を含むパス（１）を符号化する装置であって、
−縮小シーケンス（２５）を取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換する変換手段と、
−前記縮小シーケンス（２５）を符号化縮小シーケンスに符号化し且つ前記縮小シーケンス（２５）と前記元のシーケンス（２０、２３）との間の差分を表す復元情報セット（２６）を符号化する符号化手段と
を備えることを特徴とする装置。
【請求項１６】
グラフィックス記述言語で図形を表す符号化データ（３０）を復号化する装置であって、
−近似描画コマンドのグラフィックスパスシーケンス（２５）を取得するために、前記符号化データ（３０）から第１のシーケンス（２５’）を受信する受信手段及び前記第１のシーケンス（２５’）を復号化する復号化手段と、
−符号化データの新しいレイヤが復号化される必要があるかを判定する判定手段と、
−肯定的な判定の場合に、前記符号化データ（３０）から新しいレイヤに対応する情報セット（２６’、２４’、２２’）を受信及び復号化する手段と、
−アップグレードされたパスシーケンス（２３、２１、２０）を取得するために、前記復号化情報セット（２６、２４、２２）に基づいて前記復号化グラフィックスパスシーケンス（２５）の少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換する変換手段と
を備えることを特徴とする装置。
【請求項１７】
コンピュータシステムにより読み出し可能であり、前記コンピュータシステムによりロード及び実行された時に請求項１乃至１４のいずれか１項に記載の方法を実現するように構成されるコンピュータプログラムの命令を含む情報記憶手段。
【請求項１８】
マイクロプロセッサにより読み出し可能であり、前記マイクロプロセッサによりロード及び実行された時に請求項１乃至１４のいずれか１項に記載の方法を実現するように構成されるソフトウェアコードの部分を含むコンピュータプログラム。
【請求項１】
グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンス（２０、２３）を含むパス（１）を符号化する方法であって、
−縮小シーケンス（２５）を取得するために、描画の対応する元の部分の幾何学的近似に従って、少なくとも１つの元の描画コマンドを近似描画コマンドに変換するステップ（Ｅ１２０、Ｅ２３０、Ｅ４３０、Ｅ４４０、Ｅ４５０）と、
−前記縮小シーケンス（２５）を符号化縮小シーケンスに符号化するステップ（Ｅ１３０、Ｅ２５０）と、
−前記縮小シーケンス（２５）と前記元のシーケンス（２０、２３）との間の差分を表す復元情報セット（２６）を符号化するステップ（Ｅ１５０、Ｅ２６０）と
を備えることを特徴とする方法。
【請求項２】
描画コマンドは、描画コマンドタイプ及び引数を含み、前記近似描画コマンドは前記元の描画コマンドより少ない引数を含むことを特徴とする請求項１記載の方法。
【請求項３】
前記変換するステップ（Ｅ１２０、Ｅ２３０、Ｅ４３０、Ｅ４４０、Ｅ４５０）は、前記元の描画コマンドに対応する前記描画と前記近似描画コマンドに対応する前記描画との間の距離を計算することと、前記計算した距離を少なくとも１つの閾値と比較することとを含むことを特徴とする請求項１又は２記載の方法。
【請求項４】
前記復元情報セット（２６、２６’）は、
−各々が種々の近似描画コマンドタイプに変換される前記元の描画コマンドタイプ（２６’ａ）と、
−前記近似描画コマンドに保持されていない前記元の描画コマンドの引数（２６’）及び／又は前記元の描画コマンドの前記引数から計算され且つ前記近似描画コマンドに保持されていない引数の検索を可能にする引数（２６’）と
を備えることを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
幾何学的近似に従う近似変換（Ｅ２３０）を含む前記元のシーケンスの複数の反復変換（Ｅ２１０、Ｅ２２０、Ｅ２３０）を含み、
前記最後の変換（Ｅ２３０）の結果として得られる前記縮小シーケンス（２５）が符号化され（Ｅ２５０）、前記変換の前記復元情報セット（２２、２４、２６）のうちの少なくとも１つが符号化される（Ｅ２６０、Ｅ２７０、Ｅ２８０）ことを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
前記復元情報セット（２２、２４、２６）の各々が符号化されることを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
前記近似変換（Ｅ２３０）の前の変換は、描画コマンドをより少ない引数を有する同等の描画コマンドにより置換することにより前記元のパスシーケンス（２０）を書き換えること（Ｅ２１０）を含むことを特徴とする請求項５又は６記載の方法。
【請求項８】
前記近似変換（Ｅ２３０）の前の変換は、サブサンプリングシーケンス（２３）及び前記サブサンプリングシーケンスから前記元のシーケンス又は前記書き換えられたシーケンスの復元を可能にする前記スーパーサンプリング情報を含む前記復元情報セット（２４）を取得するために、前記元のシーケンス（２０）又は前記書き換えられたシーケンス（２１）をサブサンプリングするステップ（Ｅ２２０）を含むことを特徴とする請求項５乃至７のいずれか１項に記載の方法。
【請求項９】
前記縮小シーケンス（２５）は、任意の復元情報セット（２２、２４、２６）の前に最初に符号化されることを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記縮小シーケンス（２５）は、前記縮小シーケンス内の前記コマンドの引数に対応する値のシーケンスを含み、
前記縮小シーケンスの第１の座標の値は絶対値として線形符号化され、他方の座標の値は前記シーケンス内の先行座標の値に対して符号化されることを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
グラフィックス記述言語で図形を表す符号化データ（３０）を復号化する方法であって、
−近似描画コマンドのグラフィックスパスシーケンス（２５）を取得するために前記符号化データ（３０）から第１のシーケンス（２５’）を受信し（Ｅ５００）且つ復号化する（Ｅ５３０、Ｅ５４０）ステップと、
・ 符号化データの新しいレイヤが復号化される必要があるかを判定するステップ（Ｅ５５０）と、
−肯定的な判定の場合に、
・ 前記符号化データ（３０）から新しいレイヤに対応する情報セット（２６’、２４’、２２’）を受信及び復号化し（Ｅ５６０）、
・ アップグレードされたパスシーケンス（２３、２１、２０）を取得するために、前記復号化情報セット（２６、２４、２２）に基づいて前記復号化グラフィックスパスシーケンス（２５）の少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換するステップと
を備えることを特徴とする方法。
【請求項１２】
情報セット（２６’、２４’、２２’）を受信及び復号化するステップ（Ｅ５６０）及び変換するステップは、符号化データの新しいレイヤが復号化される必要がある限り前記アップグレードされたパスシーケンスに対して繰り返されることを特徴とする請求項１１記載の復号化方法。
【請求項１３】
否定的な判定（Ｅ５５０）である場合、
−変換シーケンスを取得するために、少なくとも１つの近似描画コマンドを前記グラフィックス記述言語のパス描画コマンドに変換するか又は前記近似描画コマンドを除去することと、
−前記変換シーケンスに基づいて画像をレンダリングすることと
を備えることを特徴とする請求項１１又は１２記載の復号化方法。
【請求項１４】
前記近似描画コマンドの前記除去は、前記近似描画コマンドが点コマンドに対応する場合に実行されることを特徴とする請求項１３記載の復号化方法。
【請求項１５】
グラフィックス記述言語で図形を表し且つ各々が描画の元の部分に対応する元の描画コマンドの元のシーケンス（２０、２３）を含むパス（１）を符号化する装置であって、
−縮小シーケンス（２５）を取得するために描画の対応する元の部分の幾何学的近似に従って少なくとも１つの元の描画コマンドを近似描画コマンドに変換する変換手段と、
−前記縮小シーケンス（２５）を符号化縮小シーケンスに符号化し且つ前記縮小シーケンス（２５）と前記元のシーケンス（２０、２３）との間の差分を表す復元情報セット（２６）を符号化する符号化手段と
を備えることを特徴とする装置。
【請求項１６】
グラフィックス記述言語で図形を表す符号化データ（３０）を復号化する装置であって、
−近似描画コマンドのグラフィックスパスシーケンス（２５）を取得するために、前記符号化データ（３０）から第１のシーケンス（２５’）を受信する受信手段及び前記第１のシーケンス（２５’）を復号化する復号化手段と、
−符号化データの新しいレイヤが復号化される必要があるかを判定する判定手段と、
−肯定的な判定の場合に、前記符号化データ（３０）から新しいレイヤに対応する情報セット（２６’、２４’、２２’）を受信及び復号化する手段と、
−アップグレードされたパスシーケンス（２３、２１、２０）を取得するために、前記復号化情報セット（２６、２４、２２）に基づいて前記復号化グラフィックスパスシーケンス（２５）の少なくとも１つの近似描画コマンドをアップグレードされた描画コマンドに変換する変換手段と
を備えることを特徴とする装置。
【請求項１７】
コンピュータシステムにより読み出し可能であり、前記コンピュータシステムによりロード及び実行された時に請求項１乃至１４のいずれか１項に記載の方法を実現するように構成されるコンピュータプログラムの命令を含む情報記憶手段。
【請求項１８】
マイクロプロセッサにより読み出し可能であり、前記マイクロプロセッサによりロード及び実行された時に請求項１乃至１４のいずれか１項に記載の方法を実現するように構成されるソフトウェアコードの部分を含むコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図４ａ】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図４ａ】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−４４１３４（Ｐ２０１１−４４１３４Ａ）
【公開日】平成２３年３月３日（２０１１．３．３）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−１３８６２９（Ｐ２０１０−１３８６２９）
【出願日】平成２２年６月１７日（２０１０．６．１７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．コンパクトフラッシュ
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２３年３月３日（２０１１．３．３）
【国際特許分類】
【出願番号】特願２０１０−１３８６２９（Ｐ２０１０−１３８６２９）
【出願日】平成２２年６月１７日（２０１０．６．１７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．コンパクトフラッシュ
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]