(57)【要約】少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入して少なくとも１つのソース画像を符号化するための画像符号化方法であって、少なくとも１つの分割レベルｎ（最初の分割レベルを除く）において、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される関数の基底により表される画像係数のみが供給され、これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記関数が選ばれることにより、ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにする。
2004537887.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入して少なくとも１つのソース画像を符号化するための方法であって、
少なくとも１つの分割レベルｎ（最初の分割レベルは除く）には、
Ｖn-1を分割レベルｎ−１に付随する空間とし、
Ｗn-1をＶn-1に直交する空間としたときに、
【数１】
2004537887.tif 000040
となるような画像の数学的表現空間Ｖnが付随し、
空間Ｖnには、第１に区分的アファイン関数φnの基底と、第２に、
空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
空間Ｗn-1のプレウェーブレット関数ψn-1の基底から成る２つの直交する基底の組み合わせによって形成される基底とが付随し、
分割レベルｎ（最初の分割レベルを除く）においては、前記プレウェーブレット関数の基底により表される画像係数のみが供給され、
これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記プレウェーブレット関数が選ばれることにより、前記ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにしたものである画像符号化方法。
【請求項２】
全ての分割レベル（最初の分割レベルは除く）において、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される前記プレウェーブレット関数の基底により表された画像係数のみが供給されることを特徴とする請求項１に記載の画像符号化方法。
【請求項３】
前記プレウェーブレット関数は互いに直交するウェーブレット関数であることを特徴とする請求項１または２に記載の画像符号化方法。
【請求項４】
前記プレウェーブレット関数の各関数は、それぞれの関数の基準頂点近傍に位置する当該メッシュの予め指定された数の頂点に制限された狭いサポートを有することを特徴とする請求項１乃至３のいずれかに記載の画像符号化方法。
【請求項５】
前記プレウェーブレット関数は１次元的であることを特徴とする請求項１から４のいずれかに記載の画像符号化方法。
【請求項６】
前記プレウェーブレット関数の各関数は、有利には、該プレウェーブレット関数が割り当てられる当該メッシュにおける新たな頂点を支点とする少なくとも１つの辺の当該メッシュにおける位置を考慮して決められることを特徴とする請求項５に記載の画像符号化方法。
【請求項７】
基底φi(p+1)は、Ｖi(p)を分割レベルｐのメッシュにおける頂点ｊに隣接する頂点の集合としたときに、
【数２】
2004537887.tif 000041
を使って得られることを特徴とする請求項１から６のいずれかに記載の画像符号化方法。
【請求項８】
前記プレウェーブレット関数は多次元的であることを特徴とする請求項１から４のいずれかに記載の画像符号化方法。
【請求項９】
前記プレウェーブレット関数はボックス・スプライン型関数であることを特徴とする請求項８に記載の画像符号化方法。
【請求項１０】
メッシュ分割レベルｎにおける前記画像係数の決定は、Ｘを前記ソース画像α(p)の近似の座標ベクトルとし、Ｗ(p-1)を空間Ｖp-1の基底（φi(p-1)）から空間Ｗp-1のプレウェーブレット関数の基底への変換行列とし、Ｖ(p-1)を空間Ｖp-1の行列としたとき、
【数３】
2004537887.tif 000042
とすれば、
【数４】
2004537887.tif 000043
で定義される線形システムを解くことに基づくことを特徴とする請求項１から９のいずれかに記載の画像符号化方法。
【請求項１１】
前記線形システムを解くのに「スパース行列」型または「プロフィル行列」型のアルゴリズムを実行することを特徴とする請求項１０に記載の画像符号化方法。
【請求項１２】
所定の画像構造に対して基準関数φn及びψnの基底を決定するための準備段階と、
前記所定の画像構造を有する任意の画像に対して前記基準関数φn及びψnの基底を組織的に使用する画像符号化段階と
を含むことを特徴とする請求項１から１１のいずれかに記載の画像符号化方法。
【請求項１３】
前記準備段階において、基準関数φn及びψnの基底の少なくとも２つの集合を決定し、それぞれの集合が特定の所定画像構造に対応するものであることを特徴とする請求項１２に記載の画像符号化方法。
【請求項１４】
少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルｎに対応する階層型メッシュを導入してソース画像を階層的に符号化するための関数の基底を構成するための方法であって、
少なくとも１つの所定の画像構造に対して、少なくとも１つの分割レベルｎ（最初の分割レベルは除く）には、
・Ｖn-1を分割レベルｎ−１に付随する空間とし、
・Ｗn-1をＶn-1に直交する空間としたときに、
【数５】
2004537887.tif 000044
となるような画像の数学的表現空間Ｖnが付随し、
空間Ｖnには、第１に区分的アファイン関数φnの基底と、第２に、
・空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
・空間Ｗn-1のプレウェーブレット関数ψn-1の基底から成る２つの直交する基底の組み合わせによって形成される基底とが付随し、
前記画像構造を有する任意の画像に対して画像係数をこれらの基底により表すことが可能であり、分割レベルｎに対して最適化された再現画質により前記ソース画像を表現する再現画像を作り出せるようにしたことを特徴とする方法。
【請求項１５】
請求項１から１４のいずれかに記載された基底の符号化及び／または構成のための方法を実行する画像符号器。
【請求項１６】
少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入して少なくとも１つのソース画像を符号化するための符号器であって、
少なくとも１つの分割レベルｎ（最初の分割レベルは除く）には、
・Ｖn-1を分割レベルｎ−１に付随する空間とし、
・Ｗn-1をＶn-1に直交する空間としたときに、
【数６】
2004537887.tif 000045
となるような画像の数学的表現空間Ｖnが付随し、
空間Ｖnには、第１に区分的アファイン関数φnの基底と、第２に、
・空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
・空間Ｗn-1のプレウェーブレット関数ψn-1の基底から成る２つの直交する基底の組み合わせによって形成される基底とが付随し、
分割レベルｎ（最初の分割レベルを除く）においては、前記プレウェーブレット関数の基底により表される画像係数のみが関連付けられ、
これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記プレウェーブレット関数が選ばれることにより、前記ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにしたことを特徴とする画像符号器。
【請求項１７】
全ての分割レベル（最初の分割レベルは除く）において、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される前記プレウェーブレット関数の基底により表された画像係数のみが供給されることを特徴とする請求項１６に記載の画像符号器。
【請求項１８】
請求項１から１４のいずれかに記載された基底の符号化方法及び／または基底の構成方法に基づいて符号化された画像を復号するための画像復号方法。
【請求項１９】
少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入することにより得られる画像係数の形で符号化された画像を復号するための方法であって、
符号化の段階において、少なくとも１つの分割レベルｎ（最初の分割レベルは除く）には、
・Ｖn-1を分割レベルｎ−１に付随する空間とし、
・Ｗn-1をＶn-1に直交する空間としたときに、
【数７】
2004537887.tif 000046
となるような画像の数学的表現空間Ｖnが付随し、
同じく前記符号化の段階において空間Ｖnには、第１に区分的アファイン関数φnの基底と、第２に、
・空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
・空間Ｗn-1のプレウェーブレット関数ψn-1の基底とから成る２つの直交する基底の組み合わせによって形成される基底も付随し、
前記符号化の段階においては、分割レベルｎ（最初の分割レベルを除く）には前記プレウェーブレット関数の基底により表される画像係数のみが更に関連付けられ、
これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるよう前記プレウェーブレット関数が選ばれることにより、前記ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質により作り出せるようにしたものである画像復号方法。
【請求項２０】
全ての分割レベル（最初の分割レベルは除く）には、前記プレウェーブレット関数の基底により表された画像係数のみが関連付けられることを特徴とする請求項１９に記載の画像復号方法。
【請求項２１】
前記符号化の方法は請求項１から１３のいずれかに記載された符号化方法であり、当該復号方法は、
少なくとも１つの所定の画像構造に対する基準関数の基底を受信及び／または記憶するための準備段階と、
復号される画像の画像構造に対応する基準関数の基底を使用する画像復号段階と
を含むことを特徴とする請求項１９または２０に記載の画像復号方法。
【請求項２２】
請求項１９から２１のいずれかに記載された復号方法を実行することを特徴とする符号化された画像を復号するための画像復号器。
【請求項２３】
少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入することにより得られる画像係数の形で符号化された画像を復号するための復号器であって、
符号化の段階において、少なくとも１つの分割レベルｎ（最初の分割レベルは除く）には、
・Ｖn-1を分割レベルｎ−１に付随する空間とし、
・Ｗn-1をＶn-1に直交する空間としたときに、
【数８】
2004537887.tif 000047
となるような画像の数学的表現空間Ｖnが付随し、
同じく前記符号化の段階において空間Ｖnには、第１に区分的アファイン関数φnの基底と、かつ第２に、
・空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
・空間Ｗn-1のプレウェーブレット関数ψn-1の基底から成る２つの直交する基底の組み合わせによって形成される基底とが付随し、
前記符号化の段階においては更に、分割レベルｎ（最初の分割レベルを除く）には前記プレウェーブレット関数の基底により表される画像係数のみが関連付けられ、
これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記プレウェーブレット関数が選ばれることにより、前記ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにした、ことを特徴とする画像復号器。
【請求項２４】
全ての分割レベル（最初の分割レベルは除く）には、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される関数の基底により表される画像係数のみが供給されることを特徴とする請求項２３に記載の画像復号器。
【請求項２５】
請求項１から１４のいずれかに記載された符号化方法及び／または請求項１９から２１のいずれかに記載された復号方法を実行するためのプログラム命令を含むことを特徴とする、画像を符号化及び／または復号するためのコンピュータプログラム。
【請求項２６】
少なくとも１つの所定の画像構造に対する基準関数基底の少なくとも１つの集合を表すデータを含む第１部分と、前記基準関数基底のいくつかの集合中のある集合を用いて符号化された少なくとも２つの画像を表すデータを含む第２部分とを含むことを特徴とする画像データ信号。
【請求項２７】
前記第１部分は、別個の画像構造に対応する基準関数基底の少なくとも２つの集合を含み、前記第２部分の各画像は、前記基準関数基底のいくつかの集合からある集合を選択することを可能にする情報を含むことを特徴とする請求項２６に記載の画像データ信号。
【請求項２８】
前記第１部分及び／または前記第２部分のデータは画像を段階的に再現及び／または所定レベルの画質により再現することができるよう編成されることを特徴とする請求項２６または２７に記載の画像データ信号。
【請求項２９】
請求項２６から２８のいずれかに記載された画像データ信号であって、
前記画像は、少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入した方法に基づいて符号化されており、
前記基準関数は、前記画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように選ばれており、
前記画像の符号化の段階においてあらゆる分割レベルｎ（最初の分割レベルは除く）には、
・Ｖn-1を分割レベルｎ−１に付随する空間とし、
・Ｗn-1をＶn-1に直交する空間としたときに、
【数９】
2004537887.tif 000048
となるような画像の数学的表現空間Ｖnが付随し、
空間Ｖnには、第１に区分的アファイン関数φnの基底と、第２に、
・空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
・空間Ｗn-1のプレウェーブレット関数ψn-1の基底から成る２つの直交する基底の組み合わせによって形成される基底とが付随し、
前記符号化の段階においては、分割レベルｎ（最初の分割レベルを除く）には前記プレウェーブレット関数の基底により表された画像係数のみが更に関連付けられ、
これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記プレウェーブレット関数が選ばれることにより、当該ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質により作り出せるようにしたことを特徴とする画像データ信号。
【請求項３０】
請求項１から１３のいずれかに記載された符号化方法及び／または請求項１９から２１のいずれかに記載された復号方法を、固定画像の符号化に適用する用途。
【請求項３１】
請求項１から１３のいずれかに記載された符号化方法及び／または請求項１９から２１のいずれかに記載された復号方法を、動画ストリームの画像内符号化及び／または復号に適用する用途。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像符号化（encoding of images）の技術、特に画像を伝送または保存するための画像符号化の技術に関する。より具体的には、本発明は、入れ子（あるいはネスト化された）メッシュ（nested meshes）の階層を導入した階層符号化（hierarchical encoding）の改良技術に関する。
【背景技術】
【０００２】
入れ子メッシュ型アプローチは既に多くの研究の対象になっている。ビデオ画像符号化の場合におけるものについては、例えば、（読みやすくするために、ここでの記述において引用される文献は最後の補遺３にまとめられている）文献［７］に説明がなされている。
【０００３】
メッシュは、本来的には、位相を定める頂点（vertices）及び有向面（oriented faces）の集合により規定される（図１を参照）。このようなメッシュは、例えば、幾何学的な限られた複雑さの中で３次元オブジェクトをモデリングするためのコンピュータ・グラフィックスにおいて使用される。
【０００４】
メッシュＭの近似とは、そのメッシュＭよりも幾何学的な複雑さが低くメッシュＭの幾何学的性質に可能な限り近いメッシュＭ’を見つけることである。
【０００５】
有利には、メッシュＭ’は、各入れ子メッシュがそれぞれの詳細レベルまたは階層レベルに対応する一連の入れ子メッシュから成り、それにより画像を段階的に再現して符号化を単純化することができるようになっている。
【０００６】
各階層レベルにおいて、メッシュの節点値（nodal value）は再現の二乗誤差を最小化するよう最適化される。そして、これらの節点値は数量化され符号化される。この種の方法は、効率的な圧縮率を実現し、視覚上の劣化を制限する。この視覚上の劣化とは、ここでは人間の目にとってより不快でないスムージング効果に対応するものである。これはメッシュによる近似法によって得られる再現面（reconstructed surfaces）の連続性に関する良い特性に関係している。
【０００７】
さらには、この枠組みはビデオ用途に良く適していることが分かっている。実際、三角形メッシュ（triangular meshes）は動き推定にとってより柔軟性に富んでおり効果的であることが分かる。
【０００８】
しかしながら、本発明者は、この圧縮技術が最適状態には及ばないという欠陥を被ることを観測している。実際、各レベルに使用される基底は冗長性がある。
【０００９】
さらに、この入れ子メッシュ技術によれば、最初に粗いレベルにおいて、そして徐々に微細化したレベルにおいて、（画像の拡張性のある伝送によって）段階的な再現が可能となる。しかしながら、古典的な技術によれば、このアプローチは最適化されることはなく、実際、それぞれのレベル（最後のレベルは除く）において得られる画質（クォリティ）は最適ではない。
【００１０】
ウェーブレットを導入したフィルタリング操作から得られるサブバンド間相関の利用に基づく画像圧縮技術も知られている。これらの技術は高性能圧縮率を可能にする［４］［５］。
【００１１】
しかしながら、非常に低いビットレートのみが有効な用途にとっては、それらの方法は特に輪郭に沿った振動効果の形で視覚上のかなりの劣化を与えることがわかっている。
【００１２】
さらには、使用されるウェーブレット基底は１次元的なウェーブレットのテンソル積として構築される。このため、ある一定の方向については有利だが、ある決まった構造を表現する能力に限界が生じる。サブバンドによる画像符号化の方法に特有なこれらの欠点から、入れ子にした三角形メッシュに基づく画像の表現が好ましいことが導かれる。
【００１３】
文献［１］において、E.Quak氏は、辺（ridges）上に条件を与える際にそれぞれのメッシュレベルに相補的なウェーブレットの基底を関連付けて両方の技術を同時に使用することを提案している。このようにして、彼は三角形メッシュ上のプレウェーブレットの陽な（explicit）基底を構築している。この技術は、領域の３Ｄデジタルモデルの表現及び圧縮を目的としている。
【００１４】
このQuak氏の方法は、補遺１により詳細に説明されている。
【００１５】
補遺２において、入れ子メッシュの階層に基づく符号化方法の操作の一般原理と概要を復習する。
【００１６】
この補遺２に記述された既知の方法は有効だが一定の限界を有する。
【００１７】
特に、この方法の１つの欠点は、文献［７］に明らかにされているように、関数φi(p)が関数φi(p-1)によって生成されるベクトル空間Ｖp-1と直交しないという事実にある。このことは直交変換基底を使用する変換の場合よりもエネルギーの集中が効率的でないことを意味する。
【００１８】
さらには、このことにより異なるレベルの解像度が同居する問題が生じる。このため、細分化したゾーンと細分化していないゾーンとの境界に或る頂点が存在するときには両方の解像度に対してその頂点の最適値を選ぶことは不可能である。実際、この種の頂点について、最適化レベルの１つのレベルの値を１つを選んでもこのレベルの細分化に対応する領域以外では最適な再現は実現されない。
【００１９】
さらに、表現がこのように最適状態に及ばないことは拡張性ある符号化スキームのコンテクストにおける欠点でもある。実際、それは中間のビットレートに対して最適な再現画質を実現するために使用することはできない。
【発明の開示】
【発明が解決しようとする課題】
【００２０】
そこで本発明の目標は、特に従来技術に伴うこれらの欠点を克服することにある。
【００２１】
より具体的には、本発明の目標は、拡張性ある画像符号化技術と、それに対応する復号技術で各再現レベルにおいて最適な再現画質を得ることが可能なものを実現することにある。
【００２２】
本発明のもう１つの目標は、再現レベル毎に、制限されたビットレートを必要とするこの種の符号化及び復号技術を実現することにある。
【００２３】
本発明の更なる目標は、同じ構造（同じサイズと同じ基準メッシュ）を持つ複数の画像の効率的な処理を可能にする復号化及び復号技術を実現することにある。
【００２４】
本発明の更にもう１つの目標は、このようにして符号化された画像を伝送及び記憶するために必要なビットレートを最適化することを可能にするデータ及び信号の構造を実現することにある。
【課題を解決するための手段】
【００２５】
これらの目標並びにここで以下より明らかとなる他の目標は、少なくとも２つの入れ子空間（nested space）を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュ（hierarchical mesh）を導入して少なくとも１つのソース画像を符号化するための方法（メッシュ符号化）によって達成される。
【００２６】
本発明によれば、少なくとも１つの分割レベルｎ（最初の分割レベルを除く）において、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される関数の基底（base）で表される画像係数（image coefficinets）のみが供給され、これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記関数が選ばれることにより、前記ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにすることを特徴とする。
【００２７】
有利には、全ての分割レベル（最初の分割レベルは除く）において、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される関数の基底により表される画像係数のみが供給される。
【００２８】
有利には、分割レベルｎ（最初の分割レベルは除く）には、
・Ｖn-1を分割レベルｎ−１に付随する空間とし、
・Ｗn-1をＶn-1に直交する空間としたときに、
【数１】
2004537887.tif 000003
となるような画像の数学的表現空間Ｖnが付随し、
そして、空間Ｖnには、第１に区分的アファイン関数（piecewise affine functions）φnの基底と、第２に、
・空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
・空間Ｗn-1のプレウェーブレット関数（pre-waveles）ψn-1の基底から成る２つの直交する基底の組み合わせによって形成される基底とが付随し、前記画像係数はこれらの基底により表される。
【００２９】
言い替えると、細分化したメッシュの係数を送る段階は、細分化していない（１つ前の分割レベルの）メッシュの係数を考慮してそれに細分化したメッシュの新たな節点（またはノード）に割り当てられた係数を送ることが加わることに置き換わる。新たな節点を処理することによって、それ以前の分割レベルの係数の状態（ポジション）を最適化して各レベルで最適になるようにすることも可能となる。
【００３０】
このような方法の利点は、係数の値の改善された統計的分布にあり、それにより符号化のコストを減らすことが可能となる。最小限の細分化された頂点から始まる係数の１回の伝送によって、この新規の方法はこのレベルの解像度に対してこれらの最適係数から画像の第１表現を実行できるようにする。これとは対照的に、これまでに知られている方法では、最初の係数はこれらの頂点の値でメッシュの最高レベルの細分化に対して最適化されたものに対応する（そのため、最適状態には及ばない）。
【００３１】
好ましくは、前記プレウェーブレット関数は、互いに直交するウェーブレット関数である。
【００３２】
前記プレウェーブレット関数の各関数は、それぞれの関数の基準頂点近傍に位置する当該メッシュの予め指定された数の頂点に制限された狭いサポートを有する。
【００３３】
本発明の第１の実施方式によれば、前記プレウェーブレット関数は１次元的である。この場合には、前記プレウェーブレット関数の各関数は、有利には、該プレウェーブレット関数が割り当てられる当該メッシュの新たな頂点を支点とする少なくとも１つの辺（ridge）の当該メッシュにおける位置を考慮して決められる。
【００３４】
従って、基底φi(p+1)は、Ｖi(p)を分割レベルＰのメッシュにおける頂点ｊに隣接する頂点の集合としたときに、
【数２】
2004537887.tif 000004
を使って得られる。
【００３５】
本発明の別の具現化によれば、前記プレウェーブレット関数は多次元的である。特に、それらは「ボックス・スプライン（box spline）」型関数でありうる。
【００３６】
有利には、メッシュ分割レベルｎにおける前記画像係数の決定は、
Ｘを前記ソース画像α(p)の近似の座標ベクトルとし、Ｗ(p-1)を空間Ｖp-1の基底（φi(p-1)）から空間Ｗp-1のプレウェーブレット関数の基底への変換行列（matrix of passage）とし、Ｖ(p-1)を空間Ｖp-1の行列としたとき、
【数３】
2004537887.tif 000005
とすれば、
【数４】
2004537887.tif 000006
で定義される線形システムを解くことに基づくことを特徴とする。
【００３７】
このアプローチは、前記線形システムを解くのに特に「スパース（疎らな）行列（sparse matrix）」型または「プロフィル行列（profile matrix）」型のアルゴリズムを実行するとかなり効果的である。
【００３８】
本発明の有利な特徴として、本発明の符号化方法は、
所定の画像構造に対して基準関数φn及びψnの基底を決定するための準備段階と、
前記所定の画像構造を有する任意の画像に対して前記基準関数φn及びψnの基底を組織的に使用する画像符号化段階とを含む。
【００３９】
これにより、特に同じタイプの画像の集合の符号化が簡略化される。
【００４０】
有利には、前記準備段階において、基準関数φn及びψnの基底の少なくとも２つの集合により、それぞれの集合が特定の所定画像構造に対応するものが決定される。
【００４１】
本発明は、少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルｎに対応する階層型メッシュを導入してソース画像を階層的に符号化するための関数の基底を構成するための方法にも関係する。本発明によれば、少なくとも１つの所定の画像構造に対して、少なくとも１つの分割レベルｎにおいて、好ましくは全ての分割レベル（最初の分割レベルは除く）は、
・Ｖn-1を分割レベルｎ−１に付随する空間とし、
・Ｗn-1をＶn-1に直交する空間としたときに、
【数５】
2004537887.tif 000007
となるような画像の数学的表現空間Ｖnを有し、
空間Ｖnには、第１に区分的アファイン関数φnの基底と、第２に、
・空間Ｖn-1の区分的アファイン関数φn-1の基底、及び、
・空間Ｗn-1のプレウェーブレット関数ψn-1の基底から成る２つの直交する基底の組み合わせによって形成される基底が付随し、
前記画像構造を有する任意の画像に対して画像係数をこれらの基底により表すことが可能であり、分割レベルｎに対して最適化された再現画質で前記ソース画像を表現する再現画像を作り出すことができるようにする。
【００４２】
本発明は、ここで既に述べた符号化及び／または基底の構成のためのいずれかの方法を実行する画像符号器にも関係している。
【００４３】
また本発明は、少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入して少なくとも１つのソース画像を符号化するための符号器にも関係している。本発明によれば、少なくとも１つの分割レベルｎ（最初の分割レベルを除く）には、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される関数の基底により表される画像係数のみが関連付けられ、これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記関数が選ばれることにより、前記ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにする。
【００４４】
本発明は、ここで既に述べた符号化及び／または基底の構成のためのいずれかの方法を用いて符号化された画像を復号するための方法にも関係している。
【００４５】
本発明によるこの種の復号方法は、少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入することにより得られる画像係数の形で符号化された画像を復号する。前記符号化の段階において少なくとも１つの分割レベルｎ（最初の分割レベルを除く）には、１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される関数の基底により表される画像係数のみが関連付けられ、これらの画像係数が１つ前の分割レベルｎ−１に対する既に伝送された情報を分割レベルｎに対して最適化することができるように前記関数が選ばれることにより、当該ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにする。
【００４６】
有利には、本発明によるこの種の復号方法は、
・少なくとも１つの所定の画像構造に対する基準関数（reference functions）の基底を受信及び／または記憶するための準備段階と、
・復号される画像の画像構造に対応する基準関数の基底を使用する画像復号段階と
を含む。
【００４７】
この場合もこれにより処理作業が簡略化され、一連の画像に対して伝送されるデータのクォリティが制限される。
【００４８】
本発明は、ここで上述した復号方法を実行する符号化された画像の復号器にも関係している。
【００４９】
また、本発明は、ここで上述した符号化方法及び／または復号方法を実行するためのプログラム命令を含むことを特徴とする、画像を符号化及び／または復号するためのコンピュータプログラムにも関係している。
【００５０】
本発明は、少なくとも１つの所定の画像構造に対する基準関数基底の少なくとも１つの集合を表すデータを含む第１部分と、前記基準関数基底のいくつかの集合中のある集合用いて符号化された少なくとも２つの画像を表すデータを含む第２部分とを含むことを特徴とする画像データ信号（image data signal）にも関係している。
【００５１】
有利には、前記第１部分は別個の画像構造に対応する基準関数基底の少なくとも２つの集合を含み、前記第２部分の各画像は前記基準関数基底のいくつかの集合からある集合を選択することを可能にする情報を含む。
【００５２】
好ましくは、前記第１部分及び／または前記第２部分のデータは、画像を段階的に再現及び／または所定レベルの画質で再現することができるように編成される。
【００５３】
本発明の好ましい特徴として、前記画像は、少なくとも２つの入れ子空間を画定しており各入れ子空間がメッシュのそれぞれの分割レベルに対応する階層型メッシュを導入した方法に基づいて符号化され、前記基準関数は、前記画像係数が分割レベルｎに対して、その１つ前の分割レベルｎ−１に対して既に伝送された情報を最適化することができるように選ばれ、前記画像の符号化は、あらゆる分割レベルｎ（最初の分割レベルを除く）に、その１つ前の分割レベルｎ−１に対応する空間に直交する空間において定義される関数の基底により表される画像係数のみを関連付けて、ソース画像を表現する再現画像を分割レベルｎに対して最適化された再現画質で作り出せるようにする。
【００５４】
本発明は、多くの分野、特に固定画像の符号化と動画ストリームの画像内符号化（encoding of intra images）に適用することが可能である。
【００５５】
本発明の他の特徴と利点は、本発明の以下の好ましい実施の態様の説明においてより明らかとなる。またその説明においては図面が参照される。ただし、あくまでもその説明は例示目的として行われるものであって、本発明はそこに与えられた例には限定されない。
【発明を実施するための最良の形態】
【００５６】
本発明は、特に、相補的な基底（complementary bases）の直交性に基づいた特定のウェーブレット（wavelets）またはプレウェーブレット（pre-wavelets）を基にしている。
【００５７】
本発明をボックス・スプライン型（box-spline type）ウェーブレットに適用することも同様に考えることができる［２］。前者はその重要な係数があまり多くない三角形メッシュ上のプレウェーブレットである。後者のボックス・スプライン型ウェーブレットもメッシュから構築され、１次元ウェーブレット基底のテンソル積に基づいて２次元ウェーブレットを構成する手段を代表する。
【００５８】
提案される方法は、文献［７］で開発されたメッシュ符号化に関するそれ以前の方法の改良である。この提案される方法は、固定画像の符号化に関係するが、ビデオ圧縮の枠組みにおける画像内符号化（encoding of intra images）、特に曲面（あるいは表面）内近似（approximation of intra surface）と動き間予測（estimation of inter movement）を同時にするメッシュを使用した符号化作業にも適用することができる。
【００５９】
そのため、このアプローチは、一般的に画像の伝送と記憶に適用することができる。
【００６０】
この方法が使用できる用途としては、
・テレビ会議関連用途と、
・分散型ネットワーク上における自然画像の段階的伝送と、
・メッシュに基づく圧縮スキームにおける画像内符号化とＶＯＰへの適用
などが挙げられる。
【００６１】
図３に本発明の一般原理の概略図を示す。
【００６２】
それ自体すでに知られているタイプの入れ子メッシュで、それぞれの空間Ｖnがそのメッシュのそれぞれのレベル（階層）に対応する複数の空間を画定するものを議論することにする（３１１）。
【００６３】
これらの空間のそれぞれに対して直交する基底が探し求められる（３１２）が、この技法については下記に詳述される。そこから符号化行列（encoding matirices）が導き出され（３１３）、それによりメッシュのレベル毎に最適化された画像係数を決めることが可能となる。
【００６４】
これらの作業は、画像のコンテンツとは無関係であることに注意しなければならない。またそれらは使用されるメッシュと直結している。そのため、複数の画像が同一のメッシュに関連するという条件で、その複数の画像に使用することができる符号化及び復号の行列を生成する準備段階３１が有利に作用する。
【００６５】
次に、符号化段階３２が提供される。この段階３２は、直交する基底の計算に戻ることなく何回も繰り返す（３２１）ことができる。このため、行列が一度だけ計算されている比較的にシンプルな有効な方法が存在する。
【００６６】
特に固定画像またはビデオストリームのイントラ画像（intra images）等のそれぞれの受信されたソース画像（３２２）に対して、メッシュの各レベルに対応する画像係数が行列を用いて計算され（３２３）、このようにして得られた係数は伝送または記憶される（３２４）。
【００６７】
復号作業３３は上述した作業を逆に行う。この復号作業に対しては有効な復号行列が存在する。これらの行列は最終的にメモリに保存されるか、または、復号器を初期化するために、例えばビデオストリームの開始部分において受信される（３３１）。
【００６８】
符号化された係数が受信されると（３３２）、復号器は段階的に各画像を求められるレベルの画質にまで再現する（３３３）。
【００６９】
同じ基底をいくつかの画像に使用することができるという事実から、図５に示されるような有利な信号構造の規定が可能となる。
【００７０】
この信号は、一度だけ決定された関数の基底を含む第１の初期設定部分５１と、前記基底を用いて決められた係数を含む第２の画像データ部分５２とから構成される。このことから、第１部分５１はシーケンスの開始部分で一度だけ伝送されるのでビットレートが小さくなる。
【００７１】
画像数と同数の関数基底５１１、５１２．．．のいくつかの集合が存在するとき、これらの画像の識別システムが提供される。各画像または画像列に対して、あるいは変更が必要なときだけに、使用されるべき関数基底の集合を指示する識別子５２１１が画像のデータ５２１のプレアンブルとして伝送される。
【００７２】
部分５１と５２に対して別個の伝送ストリームを設計することができる。部分５２に対しては少なくとも２つのストリーム、例えば、最初の１つのストリームは「粗さ（coarse）」の１つ以上のレベルに対応するものであり他のいくつかのストリームはより微細なレベルに対応するものを設計することができる。必要性とビットレート及び／または利用できる手段に応じて、使用されるストリームが選ばれる。
【００７３】
最初の部分５１は、（例えばＣＤ−ＲＯＭの形式で）端末に一度だけ知られることも可能である。この場合には部分５２だけが伝送されるので、このことは非常に低いビットレートに対応する。
【００７４】
もちろん、同じ原理は、このようにして符号化された画像を記憶するデータ媒体にも適用することが可能である。
【００７５】
次に、本発明の実施態様についてより詳細に説明する。
【００７６】
１．新たな係数の定義
ここでは、利用可能な入れ子空間（nested spaces）Ｖ0，Ｖ1，．．．，Ｖnであって入れ子メッシュ（nested meshes）にも関連するものが存在していると考えることにする。これらの空間の次元は議論されるメッシュの頂点数に対応する。各空間Ｖpに対し、利用できる基底φi(p)でその各関数が頂点ｉに一意的に付随するものが存在すると仮定する。一般に、本発明は各三角形への制限が多項式である関数の基底を使用する。
【００７７】
ここに記述する一例として、簡単化の目的のために空間Ｖnがメッシュの各分割レベルに付随すると考えることにする。本発明はもちろん入れ子空間Ｖm〜Ｖlがメッシュの分割レベルｍ〜ｌ（ｍとｌは任意の整数）に逐次に付随する場合に適用することもできる。例えば、この文書で以下に記述される本発明の原理は、入れ子空間Ｖ3〜Ｖ12に付随するメッシュの分割レベル３〜１２だけに実施できる。
【００７８】
補遺２に提示されたアファイン基底（affine base）は、議論される多項式が１次多項式であるような特別な場合であって、つまりそこでは演算が作用するベクトル空間は大域的に連続な区分的アファイン関数に限定される。多重解像度の特性を使用するために、次のようなタイプの細分化方程式（refinement equation）によって或る１つのレベルから別のレベルに結ばれた基底が探し求められる。
【数６】
2004537887.tif 000008
【００７９】
メッシュ階層を通じて、我々はそのそれぞれの空間が与えられた表現と画像画質に対応する一連の入れ子空間を有する。ここでは空間ＶnとＶn+1が利用できるとすると、
【数７】
2004537887.tif 000009
となるような空間Ｗnの基底が探し求められる（記号丸＋は２つのベクトル空間の直和を表す）。その結果、画像Ｉの近似に対して次のように書くことができることが知られている。
【数８】
2004537887.tif 000010
ここで、上付き添字ｐは異なる解像度の集合を示し、ＮpはＷpの次元を表す。
【００８０】
関数ψ(p)iは、空間Ｗpの基底を構成するように選ばれる。さらに、ｄｉｍＷp＝ｄｉｍＶp+1−ｄｉｍＶpであって、この関係は、関数ψ(p)iの数が解像度ｐの新たな頂点の数に等しいことを示している。Ｗpの基底関数は新たな頂点と１対１に対応する。
【００８１】
これらの関数は、プレウェーブレット（pre-wavelets）と呼ばれている。同じレベルの基底関数が互いに直交する特別な場合にそれらはウェーブレット（wavelets）と呼ばれる。
【００８２】
事実上、この方法を適用する際に遭遇する障害は、基底（ψ(p)i）であってその基底関数が基準頂点（reference vertex）に隣接する可能な限り最小限の三角形の数である有限数に限られるサポート（support）を持つものを提示する難しさにある。このため、最初の基底を任意に直交化することに限るのは不可能である。本発明が適用できる実例を次のセクションに示す。
【００８３】
画像の近似分割が一旦利用可能になると、得られた係数は古典的な方法に従って符号化することができる。この場合には、２つの連続するレベルの解像度間の直交性によって差分符号化（Differential encoding）が無効になることに注意する。つまり、得られた係数は直接に数量化され、算術符号器（arithmetic encoder）を用いて符号化される。
【００８４】
２．新たな係数の実際の計算
説明を簡単にするために、単純に２つの連続する空間Ｖ0とＶ1を有する場合についてその計算を詳細に説明することにする。まず空間Ｗ0の基底が求められる。この基底の各関数（ψ(0)i）は、空間Ｖ1に属し、
【数９】
2004537887.tif 000011
であるので、以下のような係数ｗijが存在することが分かる。
【数１０】
2004537887.tif 000012
【００８５】
アルゴリズムの第１段階は行列Ｗ(0)＝（ｗij）を決めることである。
【００８６】
実際、この行列は空間Ｖ1の基底（φi(1)）から空間Ｗ0のプレウェーブレットの基底への変換行列を構成する。これらの計算は画像のコンテンツには依らず、事実上、メッシュの形と選ばれた基底のタイプだけに依ることに注意する。そのため、事前の計算を古典的に使用されるメッシュに対して行うことができる。この事前計算はプレウェーブレットが構築される仕方に依る。サブセクション５．４とセクション６にこのような構成の実例を示す。同様に、Ｗ（ｐ）はレベルｐ及びレベルｐ＋１に対する同じ行列を表す。
【００８７】
先行する変換行列に基づいて係数の有効な計算を説明する。与えられた画像に対して解像度のレベルｐが存在する場合には、次のような表式が得られる。
【数１１】
2004537887.tif 000013
【００８８】
レベル毎に数７式の係数に対応する係数（β(p)i）を計算することが可能である。実際には、次の関係を得る。
（１０）Ｖ(p-1)α(p-1)＝α(p)
（１１）Ｗ(p-1)β(p-1)＝α(p)
【００８９】
そのため、望ましい係数を得るために次の線形システム（linear system）を解けば十分である。
【数１２】
2004537887.tif 000014
として、
（１２）Ａ(p-1)Ｘ＝α(p)
【００９０】
ベクトルＸは、新たな基底における画像の近似の座標によって形成される。
【００９１】
このような線形システムを解く有効な方法の間に、逐次代入法を含む異なる方法が区別されてよい。本発明は、それよりスパース行列（sparse matirices）の性質を利用することに基づく解法に向けられたものである。当然のことながら、対応する行列がプロフィル行列の使用を通じた計算時間の点から受容できる複雑さを可能にするのに十分なほど疎ら（sparse）である限りにおいてのみこの方法は実用上適用可能である。
【００９２】
この正確な場合において、この性質は使用されるプレウェーブレットのサポートを十分小さな数の頂点に制限することに対応する。線形システムに対するこれらの解法は第１の可能性を提供する。しかしながら、計算時間を短縮して線形システム全体の陽な解決が避けられる他の解決法も存在する場合がある。
【００９３】
メッシュ上におけるプレウェーブレットの基底を提示することができる方法を示すために２、３の例を使用することにする。
【００９４】
３．１  基底の決定
ここで、以下に、アファイン有限ラグランジェ要素関数に基づくプレウェーブレットの例を紹介する。メッシュの頂点ｉの周りのｋディスクＤi,k(p)はレベルｐのメッシュのｋ個より少ない辺で形成される経路によって結ばれる頂点の集合として定義される（図３を参照）。ここでは、単純にプレウェーブレットの基底をＷp上に（φ(p+1)i）を直交射影してサポートが頂点ｉについてのｋディスクに制限されたものとして求める。ここで、ｉは、レベルｐには存在しなかったレベルｐ＋１の節点の集合を表す。関数（ψ(p)i）はレベルｐに属する頂点でレベルｐ−１には存在していなかったものに対応するｉの値に対して次のように表される。
【数１３】
2004537887.tif 000015
【００９５】
行列Ｑ＝（ｑij）の係数を決めるために、ψ(p)iはＶpと直交しなければならない。この直交条件は次のように書かれる。
【数１４】
2004537887.tif 000016
あるいは次のようにも（新たな頂点ｉと古い頂点ｋに対して）書かれる。
【数１５】
2004537887.tif 000017
細分化方程式を通じて、Ｖp+1の関数としての表現Ｖpが分かる。そのことからＱは同じレベルの関数のスカラー積のみに依存する線形システムの解であることが結論される。これらのスカラー積は三角形の大きさ（measurement）に基づいて計算することができる［６］。
【００９６】
我々は今や行列Ｗの係数を細分化方程式（４）を使用して次式によって導き出せる立場にある。
【数１６】
2004537887.tif 000018
以下のサブセクションにおいて画像の計算と符号化に有用な手続が説明される。
【００９７】
３．２  計算及び符号化
２つのメッシュレベルが存在する画像を符号化することを想定しよう。アルゴリズムの最初の段階において、文献［７］に記述された方法がアファイン有限要素φ(p)i（ｉはレベル１の頂点集合を表す）に基づいて節点値の最適化を実行するために使用される。数３式（補遺２）によって与えられる分割はこのようにして得られる。
【００９８】
数２式（補遺２）によって定義される平均二乗誤差を最小化することは、結局のところプロフィル法［７］によって解かれる線形システムを解くことになることを思い起こしたい。この線形システムは次のように書かれる。
【数１７】
2004537887.tif 000019
【００９９】
従って、画素値Ｉ（ｘ，ｙ）によって指定される画像を議論することにする。Ｅの最小化を実行するが、その中のΩは画像の画素集合でＶpは解像度レベルｐを有する頂点集合である。Ｅの最小値は次のＮp個の方程式で得られる。
【数１８】
2004537887.tif 000020
【０１００】
与えられた頂点ｎに対して、Ｓ（ｎ）は関数φ（ｐ）ｎのサポートとして書かれ、次のようなＮp個の方程式を得る。
【数１９】
2004537887.tif 000021
【０１０１】
従って、線形システムＡｘ＝Ｂを解く必要がある。ここで、行列ＡとベクトルＢは、ＡとＢが０に設定された後に次のように計算される。
【０１０２】
ｉ＝１，．．．，ＮT（議論されるメッシュの三角形数）に対して
Ｔiにおける（ｘ，ｙ）に対して（三角形Ｔiの画素の走査）
ｊ＝１〜３に対して（Ｔiの頂点）
ｆj＝φm(j)（ｘ，ｙ）を計算する、ｍ（ｊ）はＴiのｊ番目の頂点の添字
（ｋ＝１〜３、ｊ＝１〜３）に対して（注：（ｋ，ｊ）が実行されたなら（ｊ，ｋ）は実行されない）
Ａm(k),m(j)＝Ａm(k),m(j)＋ｆk＊ｆj
（ｊ＝１〜３）に対して
Ｂm(j)＝Ｂm(j)＋ｆj＊Ｉ（ｘ，ｙ）
ｊについて終了
ｉについて終了
アルゴリズム１：節点値の最適化
【０１０３】
行列Ａは正定値対称行列であり多数のゼロ値を有するので、線形システムはプロフィル法（profile method）によって解かれる。
【０１０４】
今や係数αを自由に使えるので、プレウェーブレットに基づいて係数を決定することにする。数１５式から、Ｐ＝ｐに対する数７式の形の分割を可能にする線形システムが導き出される。２つのレベル間の移行、すなわち、
【数２０】
2004537887.tif 000022
と書くことから
【数２１】
2004537887.tif 000023
と書くことへの移行について述べたい。
【０１０５】
各段階ごとに線形システムＣｘ＝αを解くことに努める。行列Ｃの係数は統合（synthesis）の係数である。行列Ｃの係数は０に設定される。いまの場合には、行列Ｃは数４式と数１３式を使用して決められる。最初に、数１３式の係数ｑijを計算するために使用されるアルゴリズムが与えられる。この目的のために、数１４式から線形システムＤｑ＝Ｅが導き出される。
【０１０６】
説明を簡単にするために、ｋディスクはここではメッシュ全体に等しいと考える。行列ＤとＥは０に設定される。
Ｅlk＝＜φl(p)，φk(p)＞
Ｂli＝＜φl(p)，φi(P+1)＞
である。
【０１０７】
同じレベルに属する全ての三角形が同じ面積を有するメッシュが選ばれた場合、これまでの係数がそれにより簡単に計算できる次のような関係が得られる。
ｉ≠ｊに対して、
【数２２】
2004537887.tif 000024
ｉ＝ｊに対して、
【数２３】
2004537887.tif 000025
【０１０８】
この新たな線形システムは同様に十分に疎らな（sparse）行列を有するシステムであって、このため適応型方法の利用が可能となる。しかしながら、行列は正定値対称行列ではないので、プロフィル法を適用するために線形システムＣｘ＝αは均等なシステムｔＣＣｘ＝ｔＣαで置き換えられる。このようにして対応する行列が真に正定値対称行列（Ｃは実際に逆を持つ）である線形システムが得られる。このシステムはより疎らでないが、対応する行列は同様に受容可能な特徴（プロフィル）を有する。
【０１０９】
３以上のレベルのメッシュが利用できるとき、上述したプロセスが反復される。全てのレベルの解像度、すなわち数７式の係数α(0)iとβ(p)i、に対してこの分割が有効だとすると、スカラー数量化が実行され、対応する数量化された値は細分化された三角形の木における選ばれた頂点に送られる。
【０１１０】
復号段階は、このときは行列Ｃの逆ではなく直接、行列Ｃを用いて係数を統合することによって実行される。これにより、単純補間による画像のトータルな再現を実現することがそれにより可能な係数が与えられる。
【０１１１】
４．第２の実施例
ここでは本発明のもう１つの用途として固定画像の符号化スキームを紹介する。補遺１に記述された辺型プレウェーブレット（ridge-based pre-wavelets）がここでは使用される。節点値の最適化段階は最初の実施例と共通である。
【０１１２】
この場合において、ウェーブレット係数は同じように線形システムＣｘ＝αを解くことを通じて係数が計算される。行列Ｃの係数を計算するために、次のようなアルゴリズムが適用される。
【０１１３】
ｉ＝１，．．．，Ｎpに対して
Ｃii＝１
メッシュにおけるｉに隣接するｊに対して、
Ｃij＝１
ｊについて終了
ｉについて終了
ｉ＝Ｎp＋１，．．．，Ｎp＋1に対して
Ｃii＝Ｕ、これは対応する辺ｉの位置によって決定される
Ｃij≠０、これは前のサブセクションにおいて決められた場合について計算される
ｉについて終了
アルゴリズム２：変換行列（matrix of passage）Ｃの充填法
【０１１４】
この方法は、縁での実行を想定していないことに注意する。実際には、プレウェーブレットの構成法は任意の境界のあるメッシュに対して可能な異なる配位を考慮している。
【０１１５】
５．  「ボックス・スプライン（box splines）」の適用
５．１  方法説明
この方法は、ウェーブレットまたはプレウェーブレットの他のタイプの構成にも適用することができる。多重解像度が構築される入れ子メッシュからウェーブレットの陽な表現を構成することも可能である。多次元ウェーブレット基底の一般的構成法は、文献［３］において開発された。テンソル積によって構築されるウェーブレットと比較したときにこのようなウェーブレットを使用する価値は基本関数が多次元的な枠組みにより適するという事実にある。
【０１１６】
文献［２］は、この原理を再び採用し、さらに、コンパクトサポートを持ちこのため実用上直接に使用できるプレウェーブレットの基底を決めることを可能にする方法を与える。ここではボックス・スプライン型ウェーブレット演算においてこの分割を適用することが提案されている。
【０１１７】
５．２  アルゴリズム
例示的なボックス・スプライン関数は文献［２］に与えられている。基本関数の陽な係数がここに与えられている。故に、上述したように、変換行列Ｗを導出することが可能で、それにより対応するウェーブレット係数を決めることができる。このアルゴリズムは正確に次のように書かれる。例えば、係数は文献［２］で説明された例から直接導き出される場合がある。
【０１１８】
［補遺１］
或る辺（ridge）がメッシュの２つの三角形の境界を画定する場合、その辺は内辺（internal ridge）と言う。そうでない場合にはその辺は外辺（external ridge）と言う。辺が内辺になる場合としては、その２つの頂点が内部的な場合（ａ）と、その２つの頂点の一方が外部的でもう一方が内部的な場合（ｂ）と、その２つの頂点が外部的な場合（ｃ）があり、それ以外の場合（ｄ）には辺それ自体は外辺になる。図２Ａ〜２Ｄにこれらの異なる場合をそれぞれ具体的に示す。この種の表現基底は、使用されるサポートのサイズが小さいおかげで多重解像度（multiresolution）に適合して使用するのが簡単であるという利点がある。
【０１１９】
これらの異なる場合におけるQuak氏のプレウェーブレット（pre-wavelets）の陽な表現を復習する。最初の場合（ａ）を議論しよう。ｕを議論される新たな頂点とし、ａ1とａ2を２つの頂点とし、ｓとｔをメッシレベル（階層）１における（ａ1及びａ2）それぞれの結合手の数とすると、可能なプレウェーブレットψu(0)は以下のように書かれる。
【数２４】
2004537887.tif 000026
ｂiはａ1と繋がっておりｕとは異なる頂点であり、ｃiはａ2と繋がっておりｕとは異なる頂点である。与えられた頂点ａに対して、ここでの関数φaは対応するメッシュの頂点ａに付随するアファイン有限要素（affine finite element）を表す。
【０１２０】
係数はこの場合には次のように表現される。
【数２５】
2004537887.tif 000027
ここで、
【数２６】
2004537887.tif 000028
【０１２１】
第２の場合には、辺の両端の１つはメッシュの外部頂点であると想定される。このとき、ｓ1はａ1に隣接しており議論される辺の左側に位置する頂点の数を表し、ｓ2はａ1に隣接しており議論される辺の右側に位置する頂点の数を表す。対応する係数はそれぞれＢ1i及びＢ2iと書かれる。このとき、係数に関して次のような表現を得る。
【数２７】
2004537887.tif 000029
【０１２２】
第３の場合には同じ記法が使用されるが、ｔについても、ｂ1に隣接しており議論される辺の左側に位置する頂点の数ｔ1とｂ1に隣接しており議論される辺の右側に位置する頂点の数ｔ2を区別する。
【数２８】
2004537887.tif 000030
【０１２３】
最後に、外辺の場合である最後の場合において次式を得る。
【数２９】
2004537887.tif 000031
【０１２４】
全ての場合において、最も微細なレベルのアファイン関数の基底に基づく新たな頂点に対応するプレウェーブレットの表現が存在する。
【０１２５】
［補遺２］
１．曲面の近似
問題を簡単にするために画像をグレースケール（輝度）で議論することにする。カラー（chrominance band）についても同様な方法が適用できる。画像はパラメトリック曲面の分割表現と考えてよい。ここではこの曲面のメッシュによる表現により興味がある。
【０１２６】
ここでは利用可能なメッシュは画像の全領域を覆う任意の不特定メッシュであると仮定する。頂点を中心とするラグランジュ基底関数（Lagrange base functios）Ｃ0が使用される。このとき画像Ｉの近似Ｉ∧は次のように表される。
【数３０】
2004537887.tif 000032
この式の中でＮはメッシュの頂点数を表す。またφiは頂点ｉ上で値１を採るアファイン関数であって、ｉがその頂点である三角形の中の１つの三角形の１点における値はその頂点ｉに関連するこの点の重心座標に等しいものである。故に、その頂点の１つが頂点ｉである三角形面の外側ではこの関数の値はゼロである。係数αiは画像のサポート上で次式で与えられる平均二乗誤差を最小化するように計算される。
【数３１】
2004537887.tif 000033
【０１２７】
２．メッシュの階層
本方法は入れ子状の三角形メッシュ（nested triangular meshes）の階層（hierarchy）を使用する。最初に、１つの利用可能な三角形メッシュが存在するとする。次にメッシュの分割ルールが適用される。例えばメッシュの各辺の中心に新たな頂点を挿入することによって次のメッシュを得ることが可能である。
【０１２８】
この場合、各三角形は４つの新たな三角形に分割される。画像のこのような表し方はそれぞれの近似が所定の解像度に対応する画像の有効な逐次近似を実現するために使用される。この階層は再現の平均二乗誤差が或る所定の閾値を上回る三角形のみを再分割することに利用される。この閾値の値は望ましい再現画質を部分的に決める。このようにして、この階層の分割木（tree of decomposition）が得られる。この木は符号器に伝達されなければならならず、どの三角形が再分割された三角形であるかを復号器が特定することができるようにする。
【０１２９】
３．係数の符号化
全ての場合において、基本レベル（階層の最も粗いレベル）に対する値が伝達される。実際、これらの値は画像の最小限の再現に必要である。レベル０において次式を得る。
【数３２】
2004537887.tif 000034
レベル１では次の様に書くことができる。
【数３３】
2004537887.tif 000035
ここで最初のＮ0個の頂点はレベル１のメッシュの頂点に対応する頂点であるが既にレベル０のメッシュに存在したものである。二番目の項に現れるＮ1−Ｎ0個の頂点はレベル０では存在しなかったレベル１での頂点に対応する。任意の不特定レベルｐでは、以下のような表式を利用することができる。
【数３４】
2004537887.tif 000036
【０１３０】
最初の総和項は解像度レベルｐのＮp個の頂点に対応し、二番目の総和項はレベルｐ＋１に挿入されている新たな頂点に対応する。最初のＮp個の頂点に対して次式が与えられる。
【数３５】
2004537887.tif 000037
ここでＶi(p)はメッシュｐの頂点ｉに隣接する頂点の集合を表す。
【０１３１】
画像の表現は故に次のような差分形で表すことができる。
【数３６】
2004537887.tif 000038
【０１３２】
４．考察
このようにして得られた係数を均一化するために、最初のレベルの係数の平均値がこれらの係数から差し引かれる。この表し方により、画像における直近の画素間の統計的相関に関係する空間的冗長性を利用することが可能となる。圧縮はこれらの係数を数量化（quantification）して次いで適応型算術符号化（adaptive arithmetic encoding）をして実行される。さらには、適応型細分化段階において選ばれた三角形のどれにも属さない係数は符号化されない。実際、三角形を細分化しないことはこの三角形内のより微細な解像度に対応する頂点の係数が補間済みの値であると考えるということになる。このことは係数δi(p)に０を割り当てることに等しい。
【０１３３】
５．方法の価値
以上のことから本方法によれば、入れ子状の規則正しいメッシュの階層を使用することにより固定画像を符号化するためのシンプルなスキームを得ることが可能となる。このことによって、有効な圧縮率を実現することが可能となる。さらには、このような符号化スキームは係数のスカラー伝送（scalar transmission）に良く適する。
【０１３４】
［補遺３］
参考文献
【表１】
2004537887.tif 000039
【図面の簡単な説明】
【０１３５】
【図１】ポイントＰの座標の決め方を説明するための概略図である。
【図２】図２Ａ〜図２Ｄは、補遺１に議論されたQuak氏のアプローチに基づくメッシュにおける辺の異なったポジションを示した概略図である。
【図３】本発明の実施の一態様の一般原理を説明するための概略ブロックである。
【図４】本発明の実施の一例においてプレウェーブレット関数を計算するために考慮されるｋディスクを示した概略図である。
【図５】図３に示された一般原理を利用した信号の構造を例示した概略図である。
【図１】
2004537887.tif 000049
【図２】
2004537887.tif 000050
【図３】
2004537887.tif 000051
【図４】
2004537887.tif 000052
【図５】
2004537887.tif 000053
【国際公開パンフレット】
2004537887.tif 000054
2004537887.tif 000055
2004537887.tif 000056
2004537887.tif 000057
2004537887.tif 000058
2004537887.tif 000059
2004537887.tif 000060
2004537887.tif 000061
2004537887.tif 000062
2004537887.tif 000063
2004537887.tif 000064
2004537887.tif 000065
2004537887.tif 000066
2004537887.tif 000067
2004537887.tif 000068
2004537887.tif 000069
2004537887.tif 000070
2004537887.tif 000071
2004537887.tif 000072
2004537887.tif 000073
2004537887.tif 000074
2004537887.tif 000075
2004537887.tif 000076
2004537887.tif 000077
2004537887.tif 000078
2004537887.tif 000079
2004537887.tif 000080
2004537887.tif 000081
2004537887.tif 000082
2004537887.tif 000083
2004537887.tif 000084
2004537887.tif 000085
2004537887.tif 000086
2004537887.tif 000087
2004537887.tif 000088
2004537887.tif 000089
2004537887.tif 000090
2004537887.tif 000091
2004537887.tif 000092
2004537887.tif 000093
2004537887.tif 000094
2004537887.tif 000095
2004537887.tif 000096
2004537887.tif 000097
【国際調査報告】
2004537887.tif 000098
2004537887.tif 000099
2004537887.tif 000100
2004537887.tif 000101
2004537887.tif 000102
2004537887.tif 000103
2004537887.tif 000104
2004537887.tif 000105