３次元メッシュネットワークの圧縮およびコーディング
【課題】静止画または動画をビットレートを削減してコーディングする方法を提供する。
【解決手段】デジタル画像をコード化し、前記画像を表現するビットストリームを生成し、ビットストリームの長さは所望の表現の品質に依存する方法において、コード化される画像領域に、メッシュピークが前記画像のピクセルである複数のネストメッシュを含む階層メッシングを規定し、前記階層メッシングの各メッシュに対して、コード化される画像と、該メッシュが属するネストメッシングのピークから得られる補間画像との間の輝度変数を決定し、輝度変数が閾値変数より大きいメッシュのピークの位置、輝度およびクロミナンスの値をビットストリーム位置に挿入する。
【解決手段】デジタル画像をコード化し、前記画像を表現するビットストリームを生成し、ビットストリームの長さは所望の表現の品質に依存する方法において、コード化される画像領域に、メッシュピークが前記画像のピクセルである複数のネストメッシュを含む階層メッシングを規定し、前記階層メッシングの各メッシュに対して、コード化される画像と、該メッシュが属するネストメッシングのピークから得られる補間画像との間の輝度変数を決定し、輝度変数が閾値変数より大きいメッシュのピークの位置、輝度およびクロミナンスの値をビットストリーム位置に挿入する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビットレートの削減（圧縮）による静止画または動画のコーディング分野に関する。
【背景技術】
【０００２】
画像を圧縮する技術は従来、デジタル画像信号を伝送または記憶するためにデジタル画像信号のビットレートを削減するために用いられている。第１の応用において提案されるコーディング法は特に、低いビットレートの伝送およびビットレートの保証が全くない伝送、例えばＩＰプロトコル（インターネットプロトコル）によって行われる伝送に適合している。
【０００３】
静止画または動画をビットレートを削減してコーディングする方法は多数あり、最もよく知られている方法は規格、例えばＩＳＯ-ＪＰＥＧまたはＩＳＯ-ＭＰＥＧとなった方法である。
【０００４】
これらのコーディング法は静止画（ＪＰＥＧ）では画像内の空間的冗長性、隣接する点と点との相関および細部に対する目の感度の低さを利用し、動画（ＭＰＥＧ）では連続する画像間の時間的冗長性を利用する一般的な圧縮原理を用いている。
【０００５】
この種の方法ではまず、画像の複数のブロックに離散コサイン変換（ＤＣＴ）を適用するか、または画像全体にウェーブレット変換を適用して画像を変換する。次に、得られた信号を量子化して信号のとりうる値の数を制限し、次に、量子化した信号の統計的冗長性を用いるエントロピーコーディングを用いてコード化し、伝送または記憶されるデータの量を減少させる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、これらの従来の方法には主として画像の内容およびそれらの純粋にデジタル的な性格を考慮しない方法の使用によって生じるいくつかの制限がある：
・離散コサイン変換の場合に画像の輪郭近くに現れるブロック効果に起因するリンギング、これらのリンギングは低いビットレートのウェーブレットの場合にも現れる；
・これらの方法は動画（ＭＰＥＧ）の場合には２つの画像間の動きの補償を決定したり、合成画像を自然の背景に合成するのに従来用いられる幾何学的処理（相似変換等）に十分に適合していない。
【０００７】
さらに、画像の空間的領域において直接作用する方法もあり、この方法は画像に特有のピクセルを直接選択して画像の各色彩成分を特徴付ける光度測定表面を生成し、画像の残りのピクセルを画像に特有のピクセルを補間して得ることから構成される。
【０００８】
幾何学的処理に関係する多くの可能性が提供されているが、これらの方法はやはり圧縮に関して全くあてにならないということがわかっている。さらに、これらの方法はウェーブレットによるコーディングを用いる場合とは違って、画像の複雑さおよび画像の所望の画質に適合したデータの量をコーディング終了時に得ることができない。特に、これらの方法は特にビットレートが低い場合に、許容可能な画質を有する画像を得ることができない。
【０００９】
さらに、「Progressive coding of 3-D graphic models」（IEEEの会報、1998年6月、第86版、第6号、1052-1053頁）という文献に記載されているように複数のネストメッシングからなる階層メッシングを用いるコーディング法がある。この方法は近傍基準に基づくもので、近傍と同一平面上の重要ではない辺と、近傍とはかなり異なる視覚的に重要な辺とを区別する。位置の値は辺の属性としてコード化される。コーディング法の終了時のビットの数を制限するために、メッシングの構造データおよびメッシングのトップの属性はテーブルを参照してコード化される。本発明の一目的は上記の欠点を減らす別のコーディング法を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の目的は、デジタル画像をコード化し、前記デジタル画像を表す２進信号列を生成する方法において、２進信号列の長さが画像の所望の画質の関数であり、
ａ）コード化される画像領域に、メッシュトップが前記デジタル画像のピクセルである複数のネストメッシングからなる階層メッシングを規定し、
ｂ）前記階層メッシングの各メッシュ毎に、コード化される画像と、当該メッシュが属するネストメッシングのトップから得られる補間画像との間の輝度差を決定し、
ｃ）前記輝度差が閾値偏差より大きいメッシュのトップの位置、輝度およびクロミナンスの値を２進信号列に導入する
ステップを含むことを特徴とする方法にある。
【００１１】
階層メッシングはより粗いベースを用いるメッシングのメッシュを規則的かつ連続的に細分化して得られるのが好ましい。
メッシュのトップのクロミナンス値、輝度値および位置の値をより容易に処理するために、本発明の方法は前記階層メッシングと組み合わされるツリー構造を生成するステップをさらに含むのが有利である。
【００１２】
本発明の一実施例では、ステップｃ）は数回繰り返され、閾値偏差がだんだん小さくなり、各繰り返しにおいてビットのグループが生成され、画像の画質が向上する。
【００１３】
２進信号列のサイズを減らすためにまず、２進信号列に導入される値を量子化および圧縮処理する。
【００１４】
最後に、別の実施例では、多重メッシングのトップの位置および対応するクロミナンスおよび輝度の値を最適化し、２進信号列の表現の画質をさらに高めることもできる。
【図面の簡単な説明】
【００１５】
【図１Ａ】３つのレベルの多重メッシングを示す。
【図１Ｂ】１つの三角形T1の４つの低いレベルの三角形への細分化を示す。
【図２】図１Ｂの三角形T1と組み合わされたツリー部分を示す。
【図３】多重メッシングと組み合わされたツリー構造を示す。
【図４】２進信号列に導入されるツリーの部分を示す。
【図５】量子化の後に２進信号列に導入される差分値の決定を示す。
【図６】算術圧縮処理を示す。
【図７】メッシングレベルのトップの位置の最適化およびより高いメッシングレベルでのその伝播を示す。
【図８Ａ】対角線反転処理が除外される場合を示す。
【図８Ｂ】対角線反転処理が可能な場合を示す。
【発明を実施するための形態】
【００１６】
本発明の他の特性および利点は、添付図面を参照して下記の詳細な説明を読めば明らかになるであろう。
【実施例】
【００１７】
以下の説明では、コード化される画像のピクセルが横座標xおよび縦座標yによって空間内に指定されると考える。輝度成分Yおよび２つの色彩成分UおよびVが各ピクセルと組み合わされている。成分Y、UおよびVの代わりに比色成分RVB、HSVを用いることも可能である。
【００１８】
本発明の方法の第１ステップa)ではまず、コード化される画像領域に、複数のネストメッシングを含む１つの階層メッシングが定義される。前記メッシングのメッシュのトップはコード化される画像のピクセルである。この階層メッシングは例えばより粗いベースメッシングのメッシュを規則的に連続して細分化することによって得られる。前記メッシングと組み合わされるツリーのノードと混同しないように、メッシング「ノード」という用語は使用しない点に注意しなくてはならない。
【００１９】
３個のネストメッシュを含む三角形階層メッシュの例が図１Ａに図示されている。このメッシュは、10個のメッシュと８個のメッシュトップを有する。
【００２０】
図１Ａの太い実線で表されたベースメッシングはそのメッシュトップの規則的なスタガー分布を示している。規則的なトポロジーによって三角形を画像上にうまく配置することができる。このトポロジーは演繹的にコード化される画像の内容が知られていないときに最も適している。このベースメッシングで規定された三角形はレベル０の三角形に対応する。
【００２１】
図１Ａのメッシングの例では、レベル０の三角形は４個の同一の三角形、レベル１に細分化される。この細分化は図の細い実線で示されている。
【００２２】
図１Ｂには、親の三角形T1がより高いレベルの４個の子の三角形T11、T12、T13、T14に細分化されるのが示されている。
【００２３】
最後に、レベル１の三角形は４個の三角形、レベル２に細分化される。この新たな細分化は図１Ａの破線で表されている。この階層メッシングによって高い精度を有する、したがってネストメッシングの数に比例して向上する画質を有する画像を表すことができよう。各ネストメッシングは階層メッシングの１つのメッシングレベルに対応する。
【００２４】
あるメッシュトップは複数のメッシングレベルに属し、これは例えば画像の左上側ピクセルが３つのメッシングレベルに対して１つの三角形の頂点を構成する場合である。一方では、各三角形は唯一のメッシングレベル（唯一のネストメッシング）にリンクされる。メッシングの各トップは画像のマークに１つの位置を有し、輝度YおよびクロミナンスU、V情報の中心である。
【００２５】
生成されたメッシングによって、メッシングレベルで単一の三角形を画像の各ピクセルと組み合わせることができる。画像のピクセルの輝度およびクロミナンスの値の近似値は組み合わされる三角形の頂点の対応する値から補間することによって得ることができる。
【００２６】
本明細書で用いる補間モデルはラグランジュモデルである。これは以下の式で定義される細分基底関数を含む：
【００２７】
【数１】
（ここで、eは頂点i、j、kを有する三角形である）
【００２８】
座標(x，y)の点をpおよび点pの補間された輝度VYおよびクロミナンスVUおよびVVの値を含むベクトル
【００２９】
【数２】
で示す場合、ベクトル
【００３０】
【数３】
は以下の式で定義される：
【００３１】
【数４】
【００３２】
本発明（細分補間）の場合は、値Ψie(x，y)、Ψje(x，y)およびΨke(x，y)は三角形eにおける点pの重心座標を表す。これらの座標は以下の式で表される：
【００３３】
【数５】
Ψje(x，y)およびΨke(x，y)は式Ψie(x，y)において指数i、j、kを環状に置換して得られる。
【００３４】
メッシングステップ終了時に、ツリー構造を前記階層メッシングと組み合わせて構成し、メッシュトップの値を処理するのが有利である。ツリーはメッシングレベル（またはネストメッシング）の数と同じ数のレベルを有する。ツリーの各レベルは対応するメッシングレベルにおける三角形の数と同じ数のノードを有する。ツリーの各ノードは階層メッシングの単一の三角形に関連する。したがって、三角形T1およびその４個の子の三角形T11、T12、T13、T14に関連するツリーの部分は図２に示されている。三角形T1が多重メッシングのレベルnに属する場合は、ツリーのレベルnに対応する１つのノードおよび、各ノードが子の三角形T11、T12、T13、T14の１つに関連するレベルn+1に対応する４つの子のノードが形成される。
【００３５】
三角形T1、T11、T12、T13およびT14の頂点はそれぞれABC、AEF、BEG、FGCおよびEFGである。三角形T1に関連するノードは点A、BまたはCの１つを頂点として有する他の三角形と、頂点A、BおよびCの位置、輝度およびクロミナンスの値を共有し、冗長値を記憶しないようにする。同様に、点E、F、Gの値は三角形T11、T12、T13、T14に関連するノードに分布される。
【００３６】
階層メッシングの全ての三角形に対して１つのノードが同じ方法で形成される場合は、図３に示すように１つのツリーが得られ、このツリーのルートはベースメッシングの三角形の数と同じ数の複数のノードを含んでいる。
【００３７】
ツリーが構成されると、残るは画像の２進信号列の代表に導入されるツリーのデータを決定することである。この決定は画像の所望の画質に依存する。この決定を実施するためには、ステップｂ）にしたがって階層メッシングの各三角形に対して、コード化される画像と、そのメッシュが属するネストメッシングのトップから得られる補間画像との間の輝度差を計算する。
【００３８】
ステップｃ）では、次にこの輝度差を各三角形に対する閾値偏差と比較する。閾値偏差の値は画像の所望の画質に依存する。次に、輝度差が閾値偏差より大きい三角形に関連するツリーの部分を２進信号列に導入する。
【００３９】
実際には、決定は以下のように実施される：ツリーの各ノードに対して、対応する三角形の輝度差を計算し、次にこのノードと組み合わされる三角形の輝度差が閾値偏差より小さいか、大きいかに応じて値０または１をそれらに加える。図４はこのステップを示している。最初に、２進信号列に導入されるツリーの部分をデコーダによって再構成することを可能にするシーケンス、すなわちシーケンス11101110000000011が２進信号列に導入され、次に上記シーケンスにおいて１を有するノードに含まれる値が２進信号列に導入される。
【００４０】
この方法の過程で閾値が減少し、コーディングを段階的に進行させることができるのが有利である。したがって、好ましい実施例では、ステップｃ）は、閾値偏差をだんだん小さくして、数回繰り返され、各繰り返しにおいて、画像の画質を向上させるためにビットの追加のグループが生成される。冗長度の全くない最終２進信号列を構築するために、基準テーブルが用いられ、このテーブルではノードの値が既にビット列に導入されたか否かを示す値０または１がツリーの各ノードと組み合わされる。テーブルの値はノードの値がビット列に導入されると更新される。したがって、閾値偏差が減少するとき、ビット列に導入されることが求められるノード値が既にそこにはないことを確かめるための検査が行われる。これによって、閾値偏差の低減に対応するツリーの追加部分のみをビット列に導入することができる。
【００４１】
したがって、高画質の画像が要求されないときは、最も高い閾値偏差で得られた２進信号列の第１の部分のみを利用することができる。ある程度の画質の画像を得るためには、２進信号列のより大きな部分を利用する必要があろう。
【００４２】
改良実施例では、トップの値を２進信号列に導入する前に量子化および圧縮して２進信号列のサイズを制限することができる。量子化は不均一になるように選択するのが好ましい。量子化は例えば輝度値（それぞれクロミナンスおよび位置）の統計分布を利用することができる。このために、処理される画像の輝度値のヒストグラム（グレーのレベル）をモデル化する。このヒストグラムは一般にほとんど拡張されず、一般化されたガウスと同化させることができる。平均値および標準差を計算し、不規則な区間の数を固定した後で、各区間Iiに対して最適な量子化値Viを計算する。この値は基準Dを最小化して得られる。この基準Dは以下の式で定義される：
【００４３】
【数６】
（ここで、p(x)は一般化されたガウスで得られた点xの周辺確率密度を示し、Lは不規則な区間の数である）。
【００４４】
量子化ステップの最後に、量子化差分値にデータ圧縮処理を行い、２進信号列の長さを制限する。圧縮は本発明の場合は最良の圧縮率を有する算術および適応コーダによって実施されるのが有利である。
【００４５】
算術コーディング（または算術圧縮）の一般法則は以下の通り：記号で形成される各メッセージは０〜１の実数の区間で表される。記号の出現の可能性が高ければ高いほど、その画像区間は大きくなる。算術コーディングはPascal Plumeによる「Data Compression」（出版元：Eyrolles）pp 111-168という文献に詳細に説明されている。
【００４６】
さらに、適応コーディングは圧縮ステップ中に記号のコーディングを、その出現頻度にしたがって徐々に適合させることで構成されている。したがって、記号が圧縮開始時に５ビットでコード化される場合は、圧縮の別のステップで、この同じ記号をその出現頻度が高いか、低いかに応じて１または８ビットでコード化することができる。圧縮のどの時点においても、最も頻度の高い記号が最低の数のビットでコード化される。当然、この方法では圧縮を実施するコーダの部分および解凍を実施するデコーダの部分が並行にかつ均一に機能する必要がある。この種のコーディングでは、コーダおよびデコーダは全ての記号が同程度に確からしい所定の統計テーブルから始まる。圧縮中に徐々に、コーダはテーブルを更新する。実際には、デコーダは解凍中にそのテーブルを用いて同じことを行う。更新するアルゴリズムがコーダおよびデコーダで同一である限り、この種のコーディングは完全に機能するので、統計テーブルを伝送する必要がない。
【００４７】
輝度、クロミナンスおよび位置の値の統計分布は互いに異なるので、これらの値は別々にコード化するのが好ましい。また、これらの3つの値のタイプを別々に処理するために適応算術コーダが備えられている。
【００４８】
２進信号列のサイズを減らすために、一改良実施例では、ベースメッシングを除いて、ネストメッシングのメッシュトップの正確な輝度、クロミナンスおよび位置の差分値以外の値を２進信号列に導入しないことが決められている。各差分値は、コード化される画像の対応する正確な値と、より低いレベルのネスト階層メッシングの隣接するトップの対応する正確な値から得られる補間値との間の差を表す。
【００４９】
図５には差分値を決定する実施例が示されている。この図には三角形、レベル０が示され、その頂点A、B、Cはそれぞれ輝度値が210、150および132である。この三角形は４個の同一のレベル１の三角形に細分化され、３個の新しい頂点E、FおよびGが現れ、それぞれレベル０の三角形の辺AB、ACおよびBCの中間に位置している。頂点E、FおよびGの輝度値はそれぞれ182、170および143である。頂点E、FおよびGの輝度値を隣接する頂点の値を補間することによって計算する場合は、値180、171および141が得られる。２進信号列に導入した値はこの場合、正確な値と補間値との間の差に対応して+2、-1および+2である。しかし、これらの値は事前に量子化されており、とりうる値の数が制限されるので、次のデータ圧縮処理の性能が高まる。
【００５０】
さらに、量子化誤差が累積しないように、低いレベルの量子化値から差分値の計算を行う。
【００５１】
好ましい一実施例では、メッシング（トップの位置および値Y、U、V）はさらにそれらのコーディングポテンシャルをできるだけ完全に利用するように画像の内容に適合している。この適合は3つのレベルで行うことができる：
【００５２】
・メッシングのトップの位置の最適化：ノードの位置は画像を局所的に表現するそれらの効果にしたがって変更される；
・メッシングのトップの輝度およびクロミナンスの値の最適化：値Y、U、Vは元の画像をできるだけ完全に表現するように最適化される；
・メッシングのトポロジーの最適化：メッシングのトポロジーは対角線反転処理を用いて画像を局所的に表現するメッシングの能力をさらに高めることによって変更される。
【００５３】
先に選択したメッシング構造は規則的な構造を有する。したがって、その内容に不一致があり、特に均一領域と、トップでより高い密度を必要とするテクスチャ領域とを混合する画像を表現するのに適合しないようにみえることがある。メッシングのトップの位置を最適化することによって、メッシングトップの集中をそれを必要とするトップの領域に移動させることができよう。
【００５４】
この最適化の最も早い視覚的効果はメッシングのトップが一緒に画像の物体の物理的輪郭へ向かって運ばれることによって示される。
【００５５】
この処理はベースメッシングに対応するレベル（レベル０）から始まるレベルごとに実施される。レベル０での最適化の結果を次にレベルn+1に伝送し、レベルｎのトップの新しい位置からレベルn+1の追加トップの位置が得られる。各レベルでの位置の最適化およびツリーの各種レベルへのその伝播は図７に示されている。
【００５６】
位置の最適化はコード化される画像と補間された画像との間の輝度差に対応する基準Ｅを最小化して実施される。Ｅを計算するためには、座標(x，y，z)でz=Y（輝度成分）の
【００５７】
【数７】
の点qを考慮する。基準Ｅは以下の式で定義される：
【００５８】
【数８】
【００５９】
ここで、Fはqが元の画像の点qから形成される表面と、補間された画像の点qから形成される表面との間にある場合は値が１であり、それ以外の場合は値が０の特性関数である。
【００６０】
差Ｅの最小化は適応ステップ傾斜降下アルゴリズムを用いて実施される。この最小化には
【００６１】
【数９】
（ここでＥは最小である、すなわち∇Ｅ（X）＝０）
の点のベクトルXを探すことが含まれる。
【００６２】
要するに、この最小化は以下の非線形方程式システムを解く点にある：
【００６３】
【数１０】
【００６４】
このシステムはニュートン法によって直接解くことができる。しかし、この方法は、繰り返しの開始点が解からあまりに遠いときには集束しないことがある。また、繰り返し処理を用いて、Ｅの局所的最適へ向かって集束する一組の中間位置q1，q2を生成するのが好ましい。
【００６５】
この種の繰り返し処理は以下のように行われる：トップSoの最適位置を決定するために、その開始位置qSoから始め、この点でＥの勾配を計算する。∇Ｅ（qSo）がＥの最大増加方向を示すとき、量α0は反対方向に移動し、トップS0は新しい位置を有する。
【００６６】
【数１１】
繰り返し処理によって中間位置q2、q3、…qkが生成され、
【００６７】
【数１２】
になる。
【００６８】
適応ステップαkは集束を加速するように選択されるのが有利である。適応ステップ傾斜降下法は差Ｅが増加（減少）するときに、ステップαkを減少（増加）させることで構成されているが、αk∈［αmin,αmax］を目指すステップにサイズの制約がみられる。連続する差Ｅ間の差が最小閾値偏差より低いときに最終位置qn＝qSoが得られる。同様に、メッシングの残りのトップの最適位置が計算される。
【００６９】
既に述べたように、差Ｅは実際の画像に対して計算される。改良例では、メッシングレベルで「頻繁な」内容に関して類似している特定の基準画像Iに対して各メッシングレベルで差Ｅが計算される。したがって、ベースメッシング（レベル０）は画像の低い頻度のアスペクトのみを表すので、このレベルのトップの位置を最適化するのに用いる基準画像も低い頻度の「頻繁な」内容を有する。この基準画像は実際の画像をフィルタリングして得られる。
【００７０】
同様に、各メッシングレベルには「頻繁な」内容が該メッシングに適合した基準画像が組み合わされる。最高のメッシングレベルに組み合わされるこの基準画像は実際の画像に対応する（フィルタリングなし）。これらの基準画像を生成するために、無限パルスレスポンスハーフバンドローパスフィルタの近似値が用いられる：
【００７１】
【数１３】
（ここで、Lは二段抽出ファクタである）。
【００７２】
したがって、値Ｅを計算するために各メッシングレベルで異なる基準画像が用いられる。
【００７３】
メッシングトップと組み合わされる輝度およびクロミナンスの値の最適化によって本発明の方法の別の可能な改良が与えられる。
【００７４】
値Y、U、Vの最適化は最少誤差二乗法によって行われ、画像の領域Ωで以下の式で定義される基準Ｅを最小化することから成る：
【００７５】
【数１４】
【００７６】
（ここで、
・Snは前記階層メッシングの指数トップnであり、
・Mは前記階層メッシングのトップの合計数であり、
・I（x，y）はコード化される画像の座標(x，y)のピクセルの輝度値（それぞれクロミナンス値UまたはV）を表し、
・ΨSnはトップSnと組み合わされる補間関数であり、
・V（Sn）はトップSnと組み合わされる最適化輝度値（それぞれクロミナンス）である）。
【００７７】
この式が演繹される場合、最適化値はM個の式の以下の線形システムを解いてて得られる：
【００７８】
【数１５】
【００７９】
関数ΨSmのコンパクト支持関数によって、式のこのシステムは以下の式で表すこともできる：
【００８０】
【数１６】
【００８１】
（ここで、
・supp(Sm)はトップまたは頂点がSmである三角形またはメッシュを示し、
・ver(e)は三角形eのトップを示す）。
【００８２】
方程式の上記のシステムを解くことは
ＡＸ＝Ｂ
（ここで、
・Ａは規定された正の対称行列であり、
・Ｘはｍ∈［１．．Ｍ］を有する最適化値Ｖ（Ｓm）の列行列であり、
・Ｂはシステム（１）の右の項の値の列行列である）
のタイプの行列システムを解くことと同じである。
【００８３】
行列Ａは正として規定された対称行列であるので、行列Ａは唯一のＡ＝ＬＤＬ t因数分解を有し、Ｌは単位対角線を有するより低い三角行列を示し、Ｄは全ての対角係数が厳密に正である対角行列を示す。さらに隣接する行列Ａの調整は単位値を有する。
【００８４】
ＬおよびＤの係数の決定は行列のより低い三角部分に位置した係数を識別して行うことができる：
【００８５】
【数１７】
さらに、以下の式が得られる：
【００８６】
【数１８】
【００８７】
【数１９】
次に、最適化値のマトリクスXの項を以下の式で求める：
【００８８】
【数２０】
【００８９】
一改良実施例では、Ａの分解中にメモリサイズを制限するためにＡＸ＝Ｂシステムを分解するのにプロフィール法を用いることができる。プロフィール法はテーブルＭ×Ｍの形での従来の行列の表現の代わりに、２つのベクトルの形での表現を用いる。実際には、行列Ａは中空である（多くのゼロを有する）ので、従来の形でのその表現は不適当である。
【００９０】
最近の改良例では、メッシングのトポロジーを改良することもできる。実際には、メッシングの局所的構造は画像の特定の特性に適合していない。適合する階層メッシングが得られるまでメッシングを細分することは可能であるが、対角線反転処理を実施する方が簡単であることはわかる。
【００９１】
この対角線反転処理は最後のメッシングレベルで実施され、この処理は変更したメッシングが画像を再構築するためにより良い画質を与える場合は、前記メッシングレベルの２個の隣接する三角形で形成される凸状不等辺四辺形において対角線を反転させることから成る。
【００９２】
この対角線反転処理は凸状不等辺四辺形にのみ関与するものである。図８Ａには対角線反転処理が可能でない非凸状の不等辺四辺形の例が示されている。
【００９３】
図８Ｂには２個の三角形T1とT2とで形成される凸状不等辺四辺形Qでの対角線反転処理が示されている。この処理は２個の三角形T1とT2とに共通する辺を表す対角線を反転させることから成る。反転後、不等辺四辺形Qは２個の新しい三角形T1およびT2を含む。
【００９４】
トポロジーを最適化する処理は次に下記ステップを含む：
・最高のメッシングレベルの２個の隣接する三角形T1、T2で形成される各凸状不等辺四辺形Qで輝度差Ｅを計算し、この輝度差はT1およびT2の輝度差の合計の合計に等しい、Ｅ(Q)＝Ｅ(T1)+Ｅ(T2)、
・２個の三角形T1とT2とに共通する辺を表す対角線を反転させて２個の新しい三角形T1およびT2を形成し、
・新しい三角形T1およびT2の輝度差を計算し、Ｅ(Q)＝Ｅ(T1)+Ｅ(T2)を加え、
・輝度差の合計が最低である２個の三角形を保持する。
【技術分野】
【０００１】
本発明は、ビットレートの削減（圧縮）による静止画または動画のコーディング分野に関する。
【背景技術】
【０００２】
画像を圧縮する技術は従来、デジタル画像信号を伝送または記憶するためにデジタル画像信号のビットレートを削減するために用いられている。第１の応用において提案されるコーディング法は特に、低いビットレートの伝送およびビットレートの保証が全くない伝送、例えばＩＰプロトコル（インターネットプロトコル）によって行われる伝送に適合している。
【０００３】
静止画または動画をビットレートを削減してコーディングする方法は多数あり、最もよく知られている方法は規格、例えばＩＳＯ-ＪＰＥＧまたはＩＳＯ-ＭＰＥＧとなった方法である。
【０００４】
これらのコーディング法は静止画（ＪＰＥＧ）では画像内の空間的冗長性、隣接する点と点との相関および細部に対する目の感度の低さを利用し、動画（ＭＰＥＧ）では連続する画像間の時間的冗長性を利用する一般的な圧縮原理を用いている。
【０００５】
この種の方法ではまず、画像の複数のブロックに離散コサイン変換（ＤＣＴ）を適用するか、または画像全体にウェーブレット変換を適用して画像を変換する。次に、得られた信号を量子化して信号のとりうる値の数を制限し、次に、量子化した信号の統計的冗長性を用いるエントロピーコーディングを用いてコード化し、伝送または記憶されるデータの量を減少させる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、これらの従来の方法には主として画像の内容およびそれらの純粋にデジタル的な性格を考慮しない方法の使用によって生じるいくつかの制限がある：
・離散コサイン変換の場合に画像の輪郭近くに現れるブロック効果に起因するリンギング、これらのリンギングは低いビットレートのウェーブレットの場合にも現れる；
・これらの方法は動画（ＭＰＥＧ）の場合には２つの画像間の動きの補償を決定したり、合成画像を自然の背景に合成するのに従来用いられる幾何学的処理（相似変換等）に十分に適合していない。
【０００７】
さらに、画像の空間的領域において直接作用する方法もあり、この方法は画像に特有のピクセルを直接選択して画像の各色彩成分を特徴付ける光度測定表面を生成し、画像の残りのピクセルを画像に特有のピクセルを補間して得ることから構成される。
【０００８】
幾何学的処理に関係する多くの可能性が提供されているが、これらの方法はやはり圧縮に関して全くあてにならないということがわかっている。さらに、これらの方法はウェーブレットによるコーディングを用いる場合とは違って、画像の複雑さおよび画像の所望の画質に適合したデータの量をコーディング終了時に得ることができない。特に、これらの方法は特にビットレートが低い場合に、許容可能な画質を有する画像を得ることができない。
【０００９】
さらに、「Progressive coding of 3-D graphic models」（IEEEの会報、1998年6月、第86版、第6号、1052-1053頁）という文献に記載されているように複数のネストメッシングからなる階層メッシングを用いるコーディング法がある。この方法は近傍基準に基づくもので、近傍と同一平面上の重要ではない辺と、近傍とはかなり異なる視覚的に重要な辺とを区別する。位置の値は辺の属性としてコード化される。コーディング法の終了時のビットの数を制限するために、メッシングの構造データおよびメッシングのトップの属性はテーブルを参照してコード化される。本発明の一目的は上記の欠点を減らす別のコーディング法を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の目的は、デジタル画像をコード化し、前記デジタル画像を表す２進信号列を生成する方法において、２進信号列の長さが画像の所望の画質の関数であり、
ａ）コード化される画像領域に、メッシュトップが前記デジタル画像のピクセルである複数のネストメッシングからなる階層メッシングを規定し、
ｂ）前記階層メッシングの各メッシュ毎に、コード化される画像と、当該メッシュが属するネストメッシングのトップから得られる補間画像との間の輝度差を決定し、
ｃ）前記輝度差が閾値偏差より大きいメッシュのトップの位置、輝度およびクロミナンスの値を２進信号列に導入する
ステップを含むことを特徴とする方法にある。
【００１１】
階層メッシングはより粗いベースを用いるメッシングのメッシュを規則的かつ連続的に細分化して得られるのが好ましい。
メッシュのトップのクロミナンス値、輝度値および位置の値をより容易に処理するために、本発明の方法は前記階層メッシングと組み合わされるツリー構造を生成するステップをさらに含むのが有利である。
【００１２】
本発明の一実施例では、ステップｃ）は数回繰り返され、閾値偏差がだんだん小さくなり、各繰り返しにおいてビットのグループが生成され、画像の画質が向上する。
【００１３】
２進信号列のサイズを減らすためにまず、２進信号列に導入される値を量子化および圧縮処理する。
【００１４】
最後に、別の実施例では、多重メッシングのトップの位置および対応するクロミナンスおよび輝度の値を最適化し、２進信号列の表現の画質をさらに高めることもできる。
【図面の簡単な説明】
【００１５】
【図１Ａ】３つのレベルの多重メッシングを示す。
【図１Ｂ】１つの三角形T1の４つの低いレベルの三角形への細分化を示す。
【図２】図１Ｂの三角形T1と組み合わされたツリー部分を示す。
【図３】多重メッシングと組み合わされたツリー構造を示す。
【図４】２進信号列に導入されるツリーの部分を示す。
【図５】量子化の後に２進信号列に導入される差分値の決定を示す。
【図６】算術圧縮処理を示す。
【図７】メッシングレベルのトップの位置の最適化およびより高いメッシングレベルでのその伝播を示す。
【図８Ａ】対角線反転処理が除外される場合を示す。
【図８Ｂ】対角線反転処理が可能な場合を示す。
【発明を実施するための形態】
【００１６】
本発明の他の特性および利点は、添付図面を参照して下記の詳細な説明を読めば明らかになるであろう。
【実施例】
【００１７】
以下の説明では、コード化される画像のピクセルが横座標xおよび縦座標yによって空間内に指定されると考える。輝度成分Yおよび２つの色彩成分UおよびVが各ピクセルと組み合わされている。成分Y、UおよびVの代わりに比色成分RVB、HSVを用いることも可能である。
【００１８】
本発明の方法の第１ステップa)ではまず、コード化される画像領域に、複数のネストメッシングを含む１つの階層メッシングが定義される。前記メッシングのメッシュのトップはコード化される画像のピクセルである。この階層メッシングは例えばより粗いベースメッシングのメッシュを規則的に連続して細分化することによって得られる。前記メッシングと組み合わされるツリーのノードと混同しないように、メッシング「ノード」という用語は使用しない点に注意しなくてはならない。
【００１９】
３個のネストメッシュを含む三角形階層メッシュの例が図１Ａに図示されている。このメッシュは、10個のメッシュと８個のメッシュトップを有する。
【００２０】
図１Ａの太い実線で表されたベースメッシングはそのメッシュトップの規則的なスタガー分布を示している。規則的なトポロジーによって三角形を画像上にうまく配置することができる。このトポロジーは演繹的にコード化される画像の内容が知られていないときに最も適している。このベースメッシングで規定された三角形はレベル０の三角形に対応する。
【００２１】
図１Ａのメッシングの例では、レベル０の三角形は４個の同一の三角形、レベル１に細分化される。この細分化は図の細い実線で示されている。
【００２２】
図１Ｂには、親の三角形T1がより高いレベルの４個の子の三角形T11、T12、T13、T14に細分化されるのが示されている。
【００２３】
最後に、レベル１の三角形は４個の三角形、レベル２に細分化される。この新たな細分化は図１Ａの破線で表されている。この階層メッシングによって高い精度を有する、したがってネストメッシングの数に比例して向上する画質を有する画像を表すことができよう。各ネストメッシングは階層メッシングの１つのメッシングレベルに対応する。
【００２４】
あるメッシュトップは複数のメッシングレベルに属し、これは例えば画像の左上側ピクセルが３つのメッシングレベルに対して１つの三角形の頂点を構成する場合である。一方では、各三角形は唯一のメッシングレベル（唯一のネストメッシング）にリンクされる。メッシングの各トップは画像のマークに１つの位置を有し、輝度YおよびクロミナンスU、V情報の中心である。
【００２５】
生成されたメッシングによって、メッシングレベルで単一の三角形を画像の各ピクセルと組み合わせることができる。画像のピクセルの輝度およびクロミナンスの値の近似値は組み合わされる三角形の頂点の対応する値から補間することによって得ることができる。
【００２６】
本明細書で用いる補間モデルはラグランジュモデルである。これは以下の式で定義される細分基底関数を含む：
【００２７】
【数１】
（ここで、eは頂点i、j、kを有する三角形である）
【００２８】
座標(x，y)の点をpおよび点pの補間された輝度VYおよびクロミナンスVUおよびVVの値を含むベクトル
【００２９】
【数２】
で示す場合、ベクトル
【００３０】
【数３】
は以下の式で定義される：
【００３１】
【数４】
【００３２】
本発明（細分補間）の場合は、値Ψie(x，y)、Ψje(x，y)およびΨke(x，y)は三角形eにおける点pの重心座標を表す。これらの座標は以下の式で表される：
【００３３】
【数５】
Ψje(x，y)およびΨke(x，y)は式Ψie(x，y)において指数i、j、kを環状に置換して得られる。
【００３４】
メッシングステップ終了時に、ツリー構造を前記階層メッシングと組み合わせて構成し、メッシュトップの値を処理するのが有利である。ツリーはメッシングレベル（またはネストメッシング）の数と同じ数のレベルを有する。ツリーの各レベルは対応するメッシングレベルにおける三角形の数と同じ数のノードを有する。ツリーの各ノードは階層メッシングの単一の三角形に関連する。したがって、三角形T1およびその４個の子の三角形T11、T12、T13、T14に関連するツリーの部分は図２に示されている。三角形T1が多重メッシングのレベルnに属する場合は、ツリーのレベルnに対応する１つのノードおよび、各ノードが子の三角形T11、T12、T13、T14の１つに関連するレベルn+1に対応する４つの子のノードが形成される。
【００３５】
三角形T1、T11、T12、T13およびT14の頂点はそれぞれABC、AEF、BEG、FGCおよびEFGである。三角形T1に関連するノードは点A、BまたはCの１つを頂点として有する他の三角形と、頂点A、BおよびCの位置、輝度およびクロミナンスの値を共有し、冗長値を記憶しないようにする。同様に、点E、F、Gの値は三角形T11、T12、T13、T14に関連するノードに分布される。
【００３６】
階層メッシングの全ての三角形に対して１つのノードが同じ方法で形成される場合は、図３に示すように１つのツリーが得られ、このツリーのルートはベースメッシングの三角形の数と同じ数の複数のノードを含んでいる。
【００３７】
ツリーが構成されると、残るは画像の２進信号列の代表に導入されるツリーのデータを決定することである。この決定は画像の所望の画質に依存する。この決定を実施するためには、ステップｂ）にしたがって階層メッシングの各三角形に対して、コード化される画像と、そのメッシュが属するネストメッシングのトップから得られる補間画像との間の輝度差を計算する。
【００３８】
ステップｃ）では、次にこの輝度差を各三角形に対する閾値偏差と比較する。閾値偏差の値は画像の所望の画質に依存する。次に、輝度差が閾値偏差より大きい三角形に関連するツリーの部分を２進信号列に導入する。
【００３９】
実際には、決定は以下のように実施される：ツリーの各ノードに対して、対応する三角形の輝度差を計算し、次にこのノードと組み合わされる三角形の輝度差が閾値偏差より小さいか、大きいかに応じて値０または１をそれらに加える。図４はこのステップを示している。最初に、２進信号列に導入されるツリーの部分をデコーダによって再構成することを可能にするシーケンス、すなわちシーケンス11101110000000011が２進信号列に導入され、次に上記シーケンスにおいて１を有するノードに含まれる値が２進信号列に導入される。
【００４０】
この方法の過程で閾値が減少し、コーディングを段階的に進行させることができるのが有利である。したがって、好ましい実施例では、ステップｃ）は、閾値偏差をだんだん小さくして、数回繰り返され、各繰り返しにおいて、画像の画質を向上させるためにビットの追加のグループが生成される。冗長度の全くない最終２進信号列を構築するために、基準テーブルが用いられ、このテーブルではノードの値が既にビット列に導入されたか否かを示す値０または１がツリーの各ノードと組み合わされる。テーブルの値はノードの値がビット列に導入されると更新される。したがって、閾値偏差が減少するとき、ビット列に導入されることが求められるノード値が既にそこにはないことを確かめるための検査が行われる。これによって、閾値偏差の低減に対応するツリーの追加部分のみをビット列に導入することができる。
【００４１】
したがって、高画質の画像が要求されないときは、最も高い閾値偏差で得られた２進信号列の第１の部分のみを利用することができる。ある程度の画質の画像を得るためには、２進信号列のより大きな部分を利用する必要があろう。
【００４２】
改良実施例では、トップの値を２進信号列に導入する前に量子化および圧縮して２進信号列のサイズを制限することができる。量子化は不均一になるように選択するのが好ましい。量子化は例えば輝度値（それぞれクロミナンスおよび位置）の統計分布を利用することができる。このために、処理される画像の輝度値のヒストグラム（グレーのレベル）をモデル化する。このヒストグラムは一般にほとんど拡張されず、一般化されたガウスと同化させることができる。平均値および標準差を計算し、不規則な区間の数を固定した後で、各区間Iiに対して最適な量子化値Viを計算する。この値は基準Dを最小化して得られる。この基準Dは以下の式で定義される：
【００４３】
【数６】
（ここで、p(x)は一般化されたガウスで得られた点xの周辺確率密度を示し、Lは不規則な区間の数である）。
【００４４】
量子化ステップの最後に、量子化差分値にデータ圧縮処理を行い、２進信号列の長さを制限する。圧縮は本発明の場合は最良の圧縮率を有する算術および適応コーダによって実施されるのが有利である。
【００４５】
算術コーディング（または算術圧縮）の一般法則は以下の通り：記号で形成される各メッセージは０〜１の実数の区間で表される。記号の出現の可能性が高ければ高いほど、その画像区間は大きくなる。算術コーディングはPascal Plumeによる「Data Compression」（出版元：Eyrolles）pp 111-168という文献に詳細に説明されている。
【００４６】
さらに、適応コーディングは圧縮ステップ中に記号のコーディングを、その出現頻度にしたがって徐々に適合させることで構成されている。したがって、記号が圧縮開始時に５ビットでコード化される場合は、圧縮の別のステップで、この同じ記号をその出現頻度が高いか、低いかに応じて１または８ビットでコード化することができる。圧縮のどの時点においても、最も頻度の高い記号が最低の数のビットでコード化される。当然、この方法では圧縮を実施するコーダの部分および解凍を実施するデコーダの部分が並行にかつ均一に機能する必要がある。この種のコーディングでは、コーダおよびデコーダは全ての記号が同程度に確からしい所定の統計テーブルから始まる。圧縮中に徐々に、コーダはテーブルを更新する。実際には、デコーダは解凍中にそのテーブルを用いて同じことを行う。更新するアルゴリズムがコーダおよびデコーダで同一である限り、この種のコーディングは完全に機能するので、統計テーブルを伝送する必要がない。
【００４７】
輝度、クロミナンスおよび位置の値の統計分布は互いに異なるので、これらの値は別々にコード化するのが好ましい。また、これらの3つの値のタイプを別々に処理するために適応算術コーダが備えられている。
【００４８】
２進信号列のサイズを減らすために、一改良実施例では、ベースメッシングを除いて、ネストメッシングのメッシュトップの正確な輝度、クロミナンスおよび位置の差分値以外の値を２進信号列に導入しないことが決められている。各差分値は、コード化される画像の対応する正確な値と、より低いレベルのネスト階層メッシングの隣接するトップの対応する正確な値から得られる補間値との間の差を表す。
【００４９】
図５には差分値を決定する実施例が示されている。この図には三角形、レベル０が示され、その頂点A、B、Cはそれぞれ輝度値が210、150および132である。この三角形は４個の同一のレベル１の三角形に細分化され、３個の新しい頂点E、FおよびGが現れ、それぞれレベル０の三角形の辺AB、ACおよびBCの中間に位置している。頂点E、FおよびGの輝度値はそれぞれ182、170および143である。頂点E、FおよびGの輝度値を隣接する頂点の値を補間することによって計算する場合は、値180、171および141が得られる。２進信号列に導入した値はこの場合、正確な値と補間値との間の差に対応して+2、-1および+2である。しかし、これらの値は事前に量子化されており、とりうる値の数が制限されるので、次のデータ圧縮処理の性能が高まる。
【００５０】
さらに、量子化誤差が累積しないように、低いレベルの量子化値から差分値の計算を行う。
【００５１】
好ましい一実施例では、メッシング（トップの位置および値Y、U、V）はさらにそれらのコーディングポテンシャルをできるだけ完全に利用するように画像の内容に適合している。この適合は3つのレベルで行うことができる：
【００５２】
・メッシングのトップの位置の最適化：ノードの位置は画像を局所的に表現するそれらの効果にしたがって変更される；
・メッシングのトップの輝度およびクロミナンスの値の最適化：値Y、U、Vは元の画像をできるだけ完全に表現するように最適化される；
・メッシングのトポロジーの最適化：メッシングのトポロジーは対角線反転処理を用いて画像を局所的に表現するメッシングの能力をさらに高めることによって変更される。
【００５３】
先に選択したメッシング構造は規則的な構造を有する。したがって、その内容に不一致があり、特に均一領域と、トップでより高い密度を必要とするテクスチャ領域とを混合する画像を表現するのに適合しないようにみえることがある。メッシングのトップの位置を最適化することによって、メッシングトップの集中をそれを必要とするトップの領域に移動させることができよう。
【００５４】
この最適化の最も早い視覚的効果はメッシングのトップが一緒に画像の物体の物理的輪郭へ向かって運ばれることによって示される。
【００５５】
この処理はベースメッシングに対応するレベル（レベル０）から始まるレベルごとに実施される。レベル０での最適化の結果を次にレベルn+1に伝送し、レベルｎのトップの新しい位置からレベルn+1の追加トップの位置が得られる。各レベルでの位置の最適化およびツリーの各種レベルへのその伝播は図７に示されている。
【００５６】
位置の最適化はコード化される画像と補間された画像との間の輝度差に対応する基準Ｅを最小化して実施される。Ｅを計算するためには、座標(x，y，z)でz=Y（輝度成分）の
【００５７】
【数７】
の点qを考慮する。基準Ｅは以下の式で定義される：
【００５８】
【数８】
【００５９】
ここで、Fはqが元の画像の点qから形成される表面と、補間された画像の点qから形成される表面との間にある場合は値が１であり、それ以外の場合は値が０の特性関数である。
【００６０】
差Ｅの最小化は適応ステップ傾斜降下アルゴリズムを用いて実施される。この最小化には
【００６１】
【数９】
（ここでＥは最小である、すなわち∇Ｅ（X）＝０）
の点のベクトルXを探すことが含まれる。
【００６２】
要するに、この最小化は以下の非線形方程式システムを解く点にある：
【００６３】
【数１０】
【００６４】
このシステムはニュートン法によって直接解くことができる。しかし、この方法は、繰り返しの開始点が解からあまりに遠いときには集束しないことがある。また、繰り返し処理を用いて、Ｅの局所的最適へ向かって集束する一組の中間位置q1，q2を生成するのが好ましい。
【００６５】
この種の繰り返し処理は以下のように行われる：トップSoの最適位置を決定するために、その開始位置qSoから始め、この点でＥの勾配を計算する。∇Ｅ（qSo）がＥの最大増加方向を示すとき、量α0は反対方向に移動し、トップS0は新しい位置を有する。
【００６６】
【数１１】
繰り返し処理によって中間位置q2、q3、…qkが生成され、
【００６７】
【数１２】
になる。
【００６８】
適応ステップαkは集束を加速するように選択されるのが有利である。適応ステップ傾斜降下法は差Ｅが増加（減少）するときに、ステップαkを減少（増加）させることで構成されているが、αk∈［αmin,αmax］を目指すステップにサイズの制約がみられる。連続する差Ｅ間の差が最小閾値偏差より低いときに最終位置qn＝qSoが得られる。同様に、メッシングの残りのトップの最適位置が計算される。
【００６９】
既に述べたように、差Ｅは実際の画像に対して計算される。改良例では、メッシングレベルで「頻繁な」内容に関して類似している特定の基準画像Iに対して各メッシングレベルで差Ｅが計算される。したがって、ベースメッシング（レベル０）は画像の低い頻度のアスペクトのみを表すので、このレベルのトップの位置を最適化するのに用いる基準画像も低い頻度の「頻繁な」内容を有する。この基準画像は実際の画像をフィルタリングして得られる。
【００７０】
同様に、各メッシングレベルには「頻繁な」内容が該メッシングに適合した基準画像が組み合わされる。最高のメッシングレベルに組み合わされるこの基準画像は実際の画像に対応する（フィルタリングなし）。これらの基準画像を生成するために、無限パルスレスポンスハーフバンドローパスフィルタの近似値が用いられる：
【００７１】
【数１３】
（ここで、Lは二段抽出ファクタである）。
【００７２】
したがって、値Ｅを計算するために各メッシングレベルで異なる基準画像が用いられる。
【００７３】
メッシングトップと組み合わされる輝度およびクロミナンスの値の最適化によって本発明の方法の別の可能な改良が与えられる。
【００７４】
値Y、U、Vの最適化は最少誤差二乗法によって行われ、画像の領域Ωで以下の式で定義される基準Ｅを最小化することから成る：
【００７５】
【数１４】
【００７６】
（ここで、
・Snは前記階層メッシングの指数トップnであり、
・Mは前記階層メッシングのトップの合計数であり、
・I（x，y）はコード化される画像の座標(x，y)のピクセルの輝度値（それぞれクロミナンス値UまたはV）を表し、
・ΨSnはトップSnと組み合わされる補間関数であり、
・V（Sn）はトップSnと組み合わされる最適化輝度値（それぞれクロミナンス）である）。
【００７７】
この式が演繹される場合、最適化値はM個の式の以下の線形システムを解いてて得られる：
【００７８】
【数１５】
【００７９】
関数ΨSmのコンパクト支持関数によって、式のこのシステムは以下の式で表すこともできる：
【００８０】
【数１６】
【００８１】
（ここで、
・supp(Sm)はトップまたは頂点がSmである三角形またはメッシュを示し、
・ver(e)は三角形eのトップを示す）。
【００８２】
方程式の上記のシステムを解くことは
ＡＸ＝Ｂ
（ここで、
・Ａは規定された正の対称行列であり、
・Ｘはｍ∈［１．．Ｍ］を有する最適化値Ｖ（Ｓm）の列行列であり、
・Ｂはシステム（１）の右の項の値の列行列である）
のタイプの行列システムを解くことと同じである。
【００８３】
行列Ａは正として規定された対称行列であるので、行列Ａは唯一のＡ＝ＬＤＬ t因数分解を有し、Ｌは単位対角線を有するより低い三角行列を示し、Ｄは全ての対角係数が厳密に正である対角行列を示す。さらに隣接する行列Ａの調整は単位値を有する。
【００８４】
ＬおよびＤの係数の決定は行列のより低い三角部分に位置した係数を識別して行うことができる：
【００８５】
【数１７】
さらに、以下の式が得られる：
【００８６】
【数１８】
【００８７】
【数１９】
次に、最適化値のマトリクスXの項を以下の式で求める：
【００８８】
【数２０】
【００８９】
一改良実施例では、Ａの分解中にメモリサイズを制限するためにＡＸ＝Ｂシステムを分解するのにプロフィール法を用いることができる。プロフィール法はテーブルＭ×Ｍの形での従来の行列の表現の代わりに、２つのベクトルの形での表現を用いる。実際には、行列Ａは中空である（多くのゼロを有する）ので、従来の形でのその表現は不適当である。
【００９０】
最近の改良例では、メッシングのトポロジーを改良することもできる。実際には、メッシングの局所的構造は画像の特定の特性に適合していない。適合する階層メッシングが得られるまでメッシングを細分することは可能であるが、対角線反転処理を実施する方が簡単であることはわかる。
【００９１】
この対角線反転処理は最後のメッシングレベルで実施され、この処理は変更したメッシングが画像を再構築するためにより良い画質を与える場合は、前記メッシングレベルの２個の隣接する三角形で形成される凸状不等辺四辺形において対角線を反転させることから成る。
【００９２】
この対角線反転処理は凸状不等辺四辺形にのみ関与するものである。図８Ａには対角線反転処理が可能でない非凸状の不等辺四辺形の例が示されている。
【００９３】
図８Ｂには２個の三角形T1とT2とで形成される凸状不等辺四辺形Qでの対角線反転処理が示されている。この処理は２個の三角形T1とT2とに共通する辺を表す対角線を反転させることから成る。反転後、不等辺四辺形Qは２個の新しい三角形T1およびT2を含む。
【００９４】
トポロジーを最適化する処理は次に下記ステップを含む：
・最高のメッシングレベルの２個の隣接する三角形T1、T2で形成される各凸状不等辺四辺形Qで輝度差Ｅを計算し、この輝度差はT1およびT2の輝度差の合計の合計に等しい、Ｅ(Q)＝Ｅ(T1)+Ｅ(T2)、
・２個の三角形T1とT2とに共通する辺を表す対角線を反転させて２個の新しい三角形T1およびT2を形成し、
・新しい三角形T1およびT2の輝度差を計算し、Ｅ(Q)＝Ｅ(T1)+Ｅ(T2)を加え、
・輝度差の合計が最低である２個の三角形を保持する。
【特許請求の範囲】
【請求項１】
デジタル画像をコード化し、前記デジタル画像を表す２進信号列を生成するコーディング方法において、２進信号列の長さが画像の所望の画質の関数であり、
ａ）コード化される画像領域に、メッシュトップが前記デジタル画像のピクセルである複数のネストメッシングからなる階層メッシングを規定し、
ｂ）前記階層メッシングの各メッシュ毎に、コード化される画像と、当該メッシュが属するネストメッシングのトップから得られる補間画像との間の輝度差を決定し、
ｃ）前記輝度差が閾値偏差より大きいメッシュのトップの位置、輝度およびクロミナンスの値を２進信号列に導入する
ステップを含むことを特徴とするコーディング方法。
【請求項２】
前記階層メッシングが、より粗いベースメッシングのメッシュを規則的かつ連続的に細分化して得られることを特徴とする請求項１に記載のコーディング方法。
【請求項３】
前記ベースメッシングが、そのメッシュトップの規則的なスタガー分布を有することを特徴とする請求項２に記載のコーディング方法。
【請求項４】
前記階層メッシングと組み合わされるツリー構造を生成するステップをさらに含むことを特徴とする請求項１〜３のいずれか一項に記載のコーディング方法。
【請求項５】
前記閾値偏差がだんだん小さくして前記ステップｃ）を複数回繰り返して、各繰り返しにおいて、画像の画質が向上するビットのグループを生成することを特徴とする請求項１〜４のいずれか一項に記載のコーディング方法。
【請求項６】
２進信号列に導入されるメッシュのトップの位置、輝度およびクロミナンスの値を予め量子化処理することを特徴とする請求項１〜５のいずれか一項に記載のコーディング方法。
【請求項７】
前記量子化処理が不均一であることを特徴とする請求項６に記載のコーディング方法。
【請求項８】
量子化値を、データ圧縮処理した後、２進信号列に導入することを特徴とする請求項６または７に記載のコーディング方法。
【請求項９】
前記データ圧縮処理を適応算術コーダによって実施することを特徴とする請求項８に記載のコーディング方法。
【請求項１０】
ベースメッシングに関する値を除いて、２進信号列に導入されるネストメッシングのメッシュトップの輝度、クロミナンスおよび位置の値が、コード化される画像の対応する正確な値と、より低いレベルのネスト階層メッシングの隣接するトップの対応する正確な値から得られる補間値との間の差をそれぞれ表す「差分」値であることを特徴とする請求項２〜５のいずれか一項に記載のコーディング方法。
【請求項１１】
前記ステップｂ）の前に、前記階層メッシングの各ネストメッシング毎に、コード化される画像と、そのメッシュトップから得られる補間画像との間の輝度差を最小にして、そのメッシュトップの位置を最適化することを特徴とする請求項１〜１０のいずれか一項に記載のコーディング方法。
【請求項１２】
前記ステップｂ）の前に、基準画像を前記階層メッシングの各メッシングと組み合わせ、各ネストメッシング毎に、それと組み合わされる基準画像と、そのメッシュトップから得られる補間画像との間の輝度差を最小にして、そのメッシュトップの位置を最適化することを特徴とする請求項１〜１１のいずれか一項に記載のコーディング方法。
【請求項１３】
階層メッシングの各種メッシングと組み合わされる基準画像を、コード化される画像をフィルタリングして得ることを特徴とする請求項１２に記載のコーディング方法。
【請求項１４】
輝度差の最小化を、適応ステップ傾斜降下アルゴリズムによって行うことを特徴とする請求項１１〜１３のいずれか一項に記載のコーディング方法。
【請求項１５】
前記ステップｂ）の前に、ネストメッシングのメッシュのトップの輝度およびクロミナンスの値を、以下の基準Ｅで最適化することを特徴とする請求項１〜１４のいずれか一項に記載のコーディング方法：
【数２１】
（ここで、
・Ｓnは前記階層メッシングの指数トップnであり、
・Ｍは前記階層メッシングのトップの合計数であり、
・Ｉ（x，y）はコード化される画像の座標(x，y)のピクセルの輝度値（それぞれクロミナンス値UまたはV）を表し、
・ΨSnはトップSnと組み合わされる補間関数であり、
・Ｖ（Sn）はトップSnと組み合わされる最適化輝度値（それぞれクロミナンス）である）。
【請求項１６】
基準Ｅの最小化がＭ個の式の以下の線形システムを解いて実施されることを特徴とする請求項１５に記載のコーディング方法：
【数２２】
（ここで、
・supp(Sm)はトップがSmであるメッシュを示し、
・ver(e)はメッシュeのトップを示す）。
【請求項１７】
Ｍ個の式を有する前記線形システムがプロフィールLDLt因数分解法によって分解されることを特徴とする請求項１２に記載のコーディング方法。
【請求項１８】
階層メッシングが三角形メッシングであり、ステップｂ）の前に、
・最高レベルの階層メッシングに属する２個の隣接する三角形で形成される各凸状不等辺四辺形に対して２個の三角形と組み合わされる輝度差の合計を計算し、
・２個の三角形に共通する辺を表す不等辺四辺形の対角線を反転させ、２個の新しい三角形を規定し、
・この２つの新しい三角形のそれぞれの輝度差を計算してそれらを加え、
・輝度差の合計が最低である２個の三角形を前記メッシング内に保持するステップを実施することを特徴とする請求項１〜１７のいずれか一項に記載のコーディング方法。
【請求項１９】
請求項１〜１８のいずれか一項にしたがって生成された２進信号列を完全または部分的に利用することを特徴とする少なくとも１つのデジタル画像を表現する方法。
【請求項２０】
請求項１〜１８のいずれか一項に記載のコーディング法にしたがって、コード化された少なくとも１つのデジタル画像の２進信号列構造を生成する方法。
【請求項２１】
請求項９に記載のコーディング法によって生成された２進信号列のデータを解凍するステップを含むことを特徴とするデジタル画像のデコーディング方法。
【請求項１】
デジタル画像をコード化し、前記デジタル画像を表す２進信号列を生成するコーディング方法において、２進信号列の長さが画像の所望の画質の関数であり、
ａ）コード化される画像領域に、メッシュトップが前記デジタル画像のピクセルである複数のネストメッシングからなる階層メッシングを規定し、
ｂ）前記階層メッシングの各メッシュ毎に、コード化される画像と、当該メッシュが属するネストメッシングのトップから得られる補間画像との間の輝度差を決定し、
ｃ）前記輝度差が閾値偏差より大きいメッシュのトップの位置、輝度およびクロミナンスの値を２進信号列に導入する
ステップを含むことを特徴とするコーディング方法。
【請求項２】
前記階層メッシングが、より粗いベースメッシングのメッシュを規則的かつ連続的に細分化して得られることを特徴とする請求項１に記載のコーディング方法。
【請求項３】
前記ベースメッシングが、そのメッシュトップの規則的なスタガー分布を有することを特徴とする請求項２に記載のコーディング方法。
【請求項４】
前記階層メッシングと組み合わされるツリー構造を生成するステップをさらに含むことを特徴とする請求項１〜３のいずれか一項に記載のコーディング方法。
【請求項５】
前記閾値偏差がだんだん小さくして前記ステップｃ）を複数回繰り返して、各繰り返しにおいて、画像の画質が向上するビットのグループを生成することを特徴とする請求項１〜４のいずれか一項に記載のコーディング方法。
【請求項６】
２進信号列に導入されるメッシュのトップの位置、輝度およびクロミナンスの値を予め量子化処理することを特徴とする請求項１〜５のいずれか一項に記載のコーディング方法。
【請求項７】
前記量子化処理が不均一であることを特徴とする請求項６に記載のコーディング方法。
【請求項８】
量子化値を、データ圧縮処理した後、２進信号列に導入することを特徴とする請求項６または７に記載のコーディング方法。
【請求項９】
前記データ圧縮処理を適応算術コーダによって実施することを特徴とする請求項８に記載のコーディング方法。
【請求項１０】
ベースメッシングに関する値を除いて、２進信号列に導入されるネストメッシングのメッシュトップの輝度、クロミナンスおよび位置の値が、コード化される画像の対応する正確な値と、より低いレベルのネスト階層メッシングの隣接するトップの対応する正確な値から得られる補間値との間の差をそれぞれ表す「差分」値であることを特徴とする請求項２〜５のいずれか一項に記載のコーディング方法。
【請求項１１】
前記ステップｂ）の前に、前記階層メッシングの各ネストメッシング毎に、コード化される画像と、そのメッシュトップから得られる補間画像との間の輝度差を最小にして、そのメッシュトップの位置を最適化することを特徴とする請求項１〜１０のいずれか一項に記載のコーディング方法。
【請求項１２】
前記ステップｂ）の前に、基準画像を前記階層メッシングの各メッシングと組み合わせ、各ネストメッシング毎に、それと組み合わされる基準画像と、そのメッシュトップから得られる補間画像との間の輝度差を最小にして、そのメッシュトップの位置を最適化することを特徴とする請求項１〜１１のいずれか一項に記載のコーディング方法。
【請求項１３】
階層メッシングの各種メッシングと組み合わされる基準画像を、コード化される画像をフィルタリングして得ることを特徴とする請求項１２に記載のコーディング方法。
【請求項１４】
輝度差の最小化を、適応ステップ傾斜降下アルゴリズムによって行うことを特徴とする請求項１１〜１３のいずれか一項に記載のコーディング方法。
【請求項１５】
前記ステップｂ）の前に、ネストメッシングのメッシュのトップの輝度およびクロミナンスの値を、以下の基準Ｅで最適化することを特徴とする請求項１〜１４のいずれか一項に記載のコーディング方法：
【数２１】
（ここで、
・Ｓnは前記階層メッシングの指数トップnであり、
・Ｍは前記階層メッシングのトップの合計数であり、
・Ｉ（x，y）はコード化される画像の座標(x，y)のピクセルの輝度値（それぞれクロミナンス値UまたはV）を表し、
・ΨSnはトップSnと組み合わされる補間関数であり、
・Ｖ（Sn）はトップSnと組み合わされる最適化輝度値（それぞれクロミナンス）である）。
【請求項１６】
基準Ｅの最小化がＭ個の式の以下の線形システムを解いて実施されることを特徴とする請求項１５に記載のコーディング方法：
【数２２】
（ここで、
・supp(Sm)はトップがSmであるメッシュを示し、
・ver(e)はメッシュeのトップを示す）。
【請求項１７】
Ｍ個の式を有する前記線形システムがプロフィールLDLt因数分解法によって分解されることを特徴とする請求項１２に記載のコーディング方法。
【請求項１８】
階層メッシングが三角形メッシングであり、ステップｂ）の前に、
・最高レベルの階層メッシングに属する２個の隣接する三角形で形成される各凸状不等辺四辺形に対して２個の三角形と組み合わされる輝度差の合計を計算し、
・２個の三角形に共通する辺を表す不等辺四辺形の対角線を反転させ、２個の新しい三角形を規定し、
・この２つの新しい三角形のそれぞれの輝度差を計算してそれらを加え、
・輝度差の合計が最低である２個の三角形を前記メッシング内に保持するステップを実施することを特徴とする請求項１〜１７のいずれか一項に記載のコーディング方法。
【請求項１９】
請求項１〜１８のいずれか一項にしたがって生成された２進信号列を完全または部分的に利用することを特徴とする少なくとも１つのデジタル画像を表現する方法。
【請求項２０】
請求項１〜１８のいずれか一項に記載のコーディング法にしたがって、コード化された少なくとも１つのデジタル画像の２進信号列構造を生成する方法。
【請求項２１】
請求項９に記載のコーディング法によって生成された２進信号列のデータを解凍するステップを含むことを特徴とするデジタル画像のデコーディング方法。
【図１Ａ】
【図１Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図１Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【公開番号】特開２０１０−２７３３６７（Ｐ２０１０−２７３３６７Ａ）
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願番号】特願２０１０−１５７３０９（Ｐ２０１０−１５７３０９）
【出願日】平成２２年７月９日（２０１０．７．９）
【分割の表示】特願２０００−５７５０８６（Ｐ２０００−５７５０８６）の分割
【原出願日】平成１１年９月３０日（１９９９．９．３０）
【出願人】（５９１０３４１５４）フランス・テレコム (290)
【出願人】（５０１０８８６７１）
【氏名又は名称原語表記】ＴＤＦ
【Ｆターム（参考）】
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願日】平成２２年７月９日（２０１０．７．９）
【分割の表示】特願２０００−５７５０８６（Ｐ２０００−５７５０８６）の分割
【原出願日】平成１１年９月３０日（１９９９．９．３０）
【出願人】（５９１０３４１５４）フランス・テレコム (290)
【出願人】（５０１０８８６７１）
【氏名又は名称原語表記】ＴＤＦ
【Ｆターム（参考）】
[ Back to top ]