(57)【特許請求の範囲】
【請求項１】
３次元デジタルオブジェクトを表わすデータを圧縮する方法であって、
当該方法は、３次元オブジェクトを表わすデータを取得することを含み、
これらのデータは、互いに隣接する複数の平面ポリゴンで形成されるメッシュと、メッシュのポリゴンの全てのテクスチャを含むテクスチャアトラスとを含み、
各ポリゴンは、ポリゴンの面を画定するエッジによりつながれる複数の頂点と、ポリゴンの面を覆うテクスチャとを備え、
当該方法は、メッシュの頂点を削除することにより、メッシュを簡略化することも含み、
簡略化することは、ポリゴンを削除してそれらの位置に、より広い面を有する新しいポリゴンを生成するもので、
所定の基準に応じて削除される頂点を特定することと、
特定された頂点、及び、これらの頂点とメッシュの他の頂点とをつなぐエッジを備えるポリゴンを削除するために、これらの頂点とエッジとを削除することと、
削除されなかった頂点をつなぐ新しいエッジを生成することと、これらの新しいポリゴンのために、削除されたポリゴンの各テクスチャからの新しいテクスチャを生成することと
を含み、
当該方法は、頂点を削除する前に、
もしも、２つのポリゴンが、共有のエッジによりつながれる第１、第２の共有の頂点を有するならば、２つのポリゴンは隣接するといわれるときに、メッシュにおいて、異なるテクスチャを有する第１、第２の隣接するポリゴンを特定することと、
第３、第４の頂点が、空間で、それぞれ、第１、第２の頂点と同じ位置を占めるように、第２ポリゴンにおいて、第１、第２の共有の頂点をそれぞれ第３、第４の頂点で置換することと、
それぞれ、第１、第３の頂点と、第２、第４の頂点との間の長さゼロの２つのエッジ、及び、第１、第２のポリゴンの間に挟まれた表面ゼロの少なくとも１つの中間ポリゴンを生成することと
を含むことを特徴とするデータを圧縮する方法。
【請求項２】
当該方法は、頂点を削除する前に、第１、第２、第３、第４の頂点をマーキングすることを含み、
メッシュの簡略化では、前記マーキングを受けた第１、第２、第３、第４の頂点は、仮にそれらが所定の基準を満たしていても、削除される頂点として特定されない
請求項１記載のデータを圧縮する方法。
【請求項３】
もしも、テクスチャアトラスにおいて２つのテクスチャの交差がゼロ集合に等しければ、これらのテクスチャは異なるといわれる
請求項１、又は２記載のデータを圧縮する方法。
【請求項４】
もしも、テクスチャアトラスにおいて２つのテクスチャを隔てる最短距離が所定のしきい値よりも大きければ、これらのテクスチャは異なるといわれる
請求項１、又は２記載のデータを圧縮する方法。
【請求項５】
圧縮された３次元デジタルオブジェクトを表すデータを伸張する方法であって、
３次元デジタルオブジェクトを表すデータのセットを取得することと、
簡略化されたメッシュと増分データとからより複雑なメッシュを再構成することとを含み、
前記３次元デジタルオブジェクトを表すデータのセットは、
複数のポリゴンで形成され、請求項１〜４のいずれか１項記載のデータを圧縮する方法により得られる、簡略化されたメッシュと、
前記データを圧縮する方法を実行する間にメッシュから削除された頂点及びエッジのリストを有する、増分伸張データと
を備え、
少なくとも１つの簡略化されたメッシュ、及び、増分伸張データは、第１、第３の頂点が長さゼロのエッジによりつながれ、第２、第４の頂点が長さゼロのエッジによりつながれるように、メッシュの第１、第２、第３、第４の頂点を符号化し、
この再構成は、
簡略化されたメッシュにおいて、取得された増分データから追加の頂点を生成すること、及び、簡略化されたメッシュからポリゴンを削除してそれらをより削減された表面を有する追加のポリゴンで置換するために、簡略化されたメッシュのエッジを、これらの新しい頂点を現在ある頂点とつなぐことによる追加のエッジで置換することと、
これらの追加のポリゴンについて、置換されたポリゴンの各テクスチャと増分データとから追加のテクスチャを生成すること
とを含み、
そのように再構成されたより複雑なメッシュが、長さゼロのエッジでつながれた第１、第３の頂点と、長さゼロのエッジでつながれた第２、第４の頂点とを含む
ことを特徴とするデータを伸張する方法。
【請求項６】
再構成されたメッシュは、
第２のポリゴンの第３、第４の頂点を、それぞれ第１、第２の頂点で置換することにより、及び、
一方では、第１、第３の頂点の間の、他方では、第２、第４の頂点の間の長さゼロのエッジを削除することにより、
フォーマットされる
請求項５記載のデータを伸張する方法。
【請求項７】
送信機と受信機との間で３次元デジタルオブジェクトを表すデータを伝達する方法であって、
この方法は、
送信機により、デジタルオブジェクトを表すデータを取得することと、
そのように取得されたデータを、請求項１〜４のいずれか１項記載の方法により、圧縮することと、
データ交換リンクにより、送信機から受信機へ圧縮されたデータを転送することと、
そのように転送された圧縮データを、請求項５又は請求項６記載の方法により、受信機により伸張すること
を含む、データを伝達する方法。
【請求項８】
請求項１〜４のいずれか１項記載の方法を実行するための指令が、電子計算機により実行されるときに、これらの指令を備えることを特徴とする情報記録媒体。
【請求項９】
請求項１〜４のいずれか１項記載の方法をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項５、又は請求項６記載の方法を実行するための指令が、電子計算機により実行されるときに、これらの指令を備えることを特徴とする情報記録媒体。
【請求項１１】
請求項５、又は請求項６記載の方法をコンピュータに実行させるためのプログラム。
【請求項１２】
請求項７記載の方法を実行するための指令が、電子計算機により実行されるときに、これらの指令を備えることを特徴とする情報記録媒体。
【請求項１３】
請求項７記載の方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元オブジェクトを表わすデータを圧縮するための方法に関する。本発明は、更に、この圧縮方法を用いて得られた、３次元オブジェクトを表わす圧縮データのセット、及び、このデータセットを含む情報記録媒体に関する。本発明は、同様に、この方法を用いて圧縮されたそのようなデータを伸張する方法に関する。本発明は、最後に、これらの方法を実行するための情報記録媒体及び計算機に関する。
【背景技術】
【０００２】
一般的に、コンピュータビジョン及び３次元コンピュータグラフィックスの分野において、３次元オブジェクトは、ポリゴンメッシュの形でデジタル的に表される。このメッシュは、互いに隣接する複数の平面ポリゴンで形成される。各ポリゴンは、ポリゴンの１つの面を画定するエッジにより相互接続される複数の頂点を備える。
【０００３】
いわゆる「プログレッシブ圧縮」方法が知られている。これらの方法は、特に、マルチメディアコンテンツのサーバから、オブジェクトが表示されることが必要なクライアント端末への、３次元オブジェクトの送信を容易にする。これらの方法では、メッシュの大きさを削減するために、頂点の選択的抑制処理（「デシメーション（decimation）」としても知られている）により、メッシュは徐々に簡略化される。簡略化されたメッシュは端末に送信されて、そこで表示される。圧縮前の最初にあったような３次元オブジェクトが復元されるまで、簡略化されたメッシュは、この端末上で、後から送信される増分データにより徐々に再構成される。
【０００４】
この方法の１つの例が、非特許文献１に記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願公開第２００４／１６４９８２号明細書
【特許文献２】仏国特許出願公開第２９９８６８５号明細書
【非特許文献】
【０００６】
【非特許文献１】Ho Lee et al.， Rate-distortion optimization for progressive compression of 3D mesh with color attributes， The Visual Computer，米国， Springer Verlag，２０１１年５月１２日，第２８巻，第２号， p.137-153
【非特許文献２】Hugues Hoppe， Progressive Meshes， SIGGRAPH '96 Proceedings of the 23rd annual conference on Computer graphics and interactive techniques，米国， ACM，１９９６年， p.99-108
【非特許文献３】Hugues Hoppe et al.， Efficient implementation of progressive meshes， Computers and graphics，英国，１９９８年２月２５日，第２２巻，第１号， p.27-39
【非特許文献４】Lili Wang et al.， Simplification for texture mapping models with mesh segmentation， 2010 16th International Conference on Virtual Systems and Multimedia (VSMM)，米国， IEEE，２０１０年１０月２０日， p.197-203
【非特許文献５】Xiuwen Liu et al.， Feature-Preserving Simplification of Texture-Mapped Models， International Conference on Computer Graphics, Imaging and Visualisation (CGIV'06)，豪州，IEEE，２００６年７月２６日， p.390-395
【非特許文献６】Pierre Alliez et al.， Progressive compression for lossless transmission of triangle meshes， Proceedings of the 28th annual conference on Computer graphics and interactive techniques，米国， ACM，２００１年， p.195-202
【非特許文献７】Adrien Maglo et al.， Progressive compression of manifold polygon meshes， Computers and Graphics，英国，２０１２年３月２３日，第３６巻，第５号， p.349-359
【発明の概要】
【発明が解決しようとする課題】
【０００７】
伸張して３次元オブジェクトをプログレッシブ表示するときに、これらの方法は、テクスチャ付き３次元オブジェクトで用いられると、画像アーティファクトを生成する欠点を有する。「テクスチャ付きオブジェクト」は、メッシュのポリゴンが、「テクスチャ」として知られるデジタル画像により覆われる表面を有する、３次元オブジェクトを意味する（「テクスチャマッピング」）。
【０００８】
このように、３次元オブジェクトがテクスチャを含むときに、オブジェクト上でのそのような画像アーティファクトの出現を制限する、３次元オブジェクトのプログレッシブ圧縮の方法の要望がある。
【課題を解決するための手段】
【０００９】
本発明は、請求項１に係る、３次元デジタルオブジェクトを表わすデータを圧縮するための方法に関する。
【００１０】
本発明者は、３次元オブジェクトが、互いに隣接するポリゴンを含み、それらのテクスチャが異なるときに、問題が発生することを特定した。問題は、特に、互いにとても異なるテクスチャを有する、オブジェクトの複数の部分の間の境界領域で発生する。一般に、プログレッシブ圧縮のための既知の方法は、ポリゴンのテクスチャ情報を考慮することなしに、メッシュの幾何学的特性に応じて、削除する頂点を選択する。このように、これらの隣接するポリゴンを分離する共通のエッジは、簡略化のために削除されるかもしれない。メッシュの簡略化の前に、そのように削除されるエッジの両側に異なるテクスチャが存在するという事実に関する情報は、結果としての簡略化されたメッシュには存在しない。それゆえ、伸張の間に、この簡略化されたメッシュが表示されると、画像アーティファクトが出現するであろう。このことは、伸張の間に認知される３次元オブジェクトの見栄えを低下させる。
【００１１】
上記方法において、第１、第２のポリゴンを見つけることは、もしも、簡略化が直接行わるならば、アーティファクトが出現する傾向にあるポリゴンを特定することを可能にする。第２のポリゴンにおいて、第１、第２の共有の頂点を、第３、第４の別個の頂点で置換し、エッジを生成することは、第１、第２のポリゴンを分離することを可能にする。このように、それらはもはや互いに隣接しない。それゆえ、例えば、第１又は第２の頂点を削除することは、第１、第２のポリゴンが同時に消滅することを結果として伴わない。圧縮の間に、第１、第２、第３、第４の頂点が、簡略化されたメッシュから削除されない限り、テクスチャの違いに関する情報は、少なくともこのように保持される。この情報は、圧縮工程の間に、このように、より長く保持される。それゆえ、他方では、伸張の間に、スクリーン上に表示される簡略化されたメッシュにおいて、この情報はより早く再現するであろう。このように、そのようなアーティファクトが見える期間を最小化して、伸張するときに表示されるオブジェクトの見栄えを改善する。
【００１２】
最後に、第３、第４の頂点は、第１、第２の頂点と同じ位置を占め、エッジの長さはゼロであるから、オブジェクトの外観は、この補充の頂点の生成により修正されない。
【００１３】
他の側面によれば、本発明は、更に、請求項３に従う、圧縮された３次元デジタルオブジェクトを表わすデータのセットに関する。
【００１４】
他の側面によれば、本発明は、更に、本発明に係る圧縮された３次元デジタルオブジェクトを表わすデータのセットを含む情報記録媒体に関する。
【００１５】
他の側面によれば、本発明は、更に、請求項５に従う、圧縮された３次元デジタルオブジェクトを表わすデータを伸張する方法に関する。
【００１６】
他の側面によれば、本発明は、更に、送信機と受信機との間で３次元デジタルオブジェクトを表わすデータを伝達する方法に関し、当該方法は、
本発明に係る圧縮方法により得られるデータを圧縮すること、
本発明に係る伸張方法により、そのように転送された圧縮データを、受信機により伸張すること
を含む。
【００１７】
本発明の実施の形態は、従属請求項の１つ以上の特徴を有していても良い。
【００１８】
他の側面によれば、本発明は、更に、本発明に係る方法を実行するための指令を、これらの指令が電子計算機により実行されるときに含む、情報記録媒体に関する。
【００１９】
他の側面によれば、本発明は、最後に、本発明を実行する電子計算機に関する。
【発明の効果】
【００２０】
本発明は、図面を参照して、何も限定しない例として単に与えられる以下の記載を熟読することにより、より良く理解されるであろう。
【図面の簡単な説明】
【００２１】
【図１】３次元デジタルオブジェクトの概略図である。
【図２】図１のオブジェクトの一部分の代表データのセットの概略図である。
【図３】図２のデータを伝達するための装置の図である。
【図４】図２のデータの圧縮方法のフローチャートである。
【図５】図４の方法の一工程の結果として修正された、図２のオブジェクトの一部分の概略図である。
【図６】図４の方法の一工程を実行する間に修正される、図１のオブジェクトのメッシュの一部分の概略図である。
【図７】図４の圧縮方法を適用した後の、図１のオブジェクトの概略図である。
【図８】図４の圧縮方法から頂点を複製する工程が省かれたときの、図４の圧縮方法を適用した後の、図１のオブジェクトの概略図である。
【図９】図４の方法の結果としての、圧縮された３次元デジタルオブジェクトの代表データのセットを含む情報記録媒体の概略図である。
【図１０】図１のオブジェクトを再構成するための、図７Ａ〜図８Ｂのオブジェクトの伸張方法のフローチャートである。
【図１１】図４の方法の一工程の他の実施の形態の概略図である。
【発明を実施するための形態】
【００２２】
これらの図面において、同じ符号は同じ構成要素を示すために用いられる。
【００２３】
以下の記載において、当業者に良く知られる特徴及び機能は、詳細には記載されないであろう。
【００２４】
図１は、市松模様が適用される３次元デジタルオブジェクト２を示す。このオブジェクト２は、メッシュ４及びテクスチャアトラス６を備える。
【００２５】
メッシュ４（「ポリゴンメッシュ」）は互いに接続する複数の平面ポリゴンで形成される。各ポリゴンは、頂点、ポリゴンの頂点を２つずつつなぐエッジ、及び、エッジにより画定される面を備える。
【００２６】
ここでは、メッシュ４は穴を含まない。
【００２７】
アトラス６は、複数の別々のテクスチャを備え、テクスチャのそれぞれは、メッシュ４のポリゴンの面を覆う。各テクスチャは２次元画像であり、例えば、ラスター画像である。この技術は、英語では「texture mapping」として知られている。
【００２８】
ここでは、ポリゴンは、３角形状のものである。事実、画像処理部の大部分は、３角形のポリゴンを処理するために最適化される。このように、以下では、これらのポリゴンを示すために、用語「３角形」を用いるかもしれない。
【００２９】
この例では、オブジェクト２は概略的に蛙を表わす。アトラス６は、メッシュ４の全外表面を覆う、白黒の市松模様を示す。
【００３０】
図２は、オブジェクト２を表わすために用いられるデジタルデータのセット１０を示す。単純化のために、これらのデータは、メッシュ４の２つの３角形１２、１４だけで記載される。これらの２つの３角形１２、１４は、図２の拡大図で更に示される。以下では、用語「オブジェクト２」は、オブジェクト２の代表データ１０を示すために用いられる。データ１０の取得を意味するために、オブジェクト２の取得というであろう。
【００３１】
セット１０は、テクスチャアトラス６、メッシュ４のポリゴンの頂点のリスト２２、メッシュ４のポリゴンのリスト２４、及び、メッシュ４のポリゴンのテクスチャ座標のリスト２６を備える。
【００３２】
アトラス６は、メッシュ４の各ポリゴンの各面を満たすのに必要な全てのテクスチャを含む。ポリゴンの面の各テクスチャは、３つの座標（ＵａＶａ）、（ＵｂＶｂ）、（ＵｃＶｃ）のセットによりアトラス６内部でインデックス付けされる（「ＵＶマッピング」）。例えば、アトラス６は、２次元のラスター画像２７を含む。座標（ＵａＶａ）、（ＵｂＶｂ）、（ＵｃＶｃ）は、この画像２７の直交参照系の３ポイントの位置を符号化する。これらの３ポイントは、「テクスチャピース（texture piece）」としても知られる、画像２７の部品を画定する。ポリゴンの面を満たすために用いられるのは、このテクスチャピースである。以下では、これらの座標は、「ＵＶ座標」として示されるであろう。より正確には、ここでは、各テクスチャピースは、それが対応するポリゴンと同じ形状を有する。このように、各テクスチャピースは、このテクスチャピースで満たされるポリゴンの面と全く同じ大きさの３角形状を有する。しかしながら、テクスチャピースの頂点は、メッシュ４の頂点ではない。いかなる混乱も避けるために、テクスチャピースの頂点を示すために、「ポイント」というであろう。ポリゴン１２、１４に対応するテクスチャピースは、画像２７において、それぞれ符号２８、２９を有する。それらの各テクスチャ座標、ピース２８に対する（Ｕ１ａＶ１ａ）、（Ｕ１ｂＶ１ｂ）、（Ｕ１ｃＶ１ｃ）、ピース２９に対する（Ｕ２ａＶ２ａ）、（Ｕ２ｂＶ２ｂ）、（Ｕ２ｃＶ２ｃ）が言及される。
【００３３】
一般に、異なる画像特性を示すテクスチャが画像２７の別個の位置に入れられるように、アトラス６は構成される。「画像特性」は、例えば、画素強度を示す値を意味する。
【００３４】
リスト２２は、各頂点について、空間の参照系で表現されるときの、この頂点の座標を含む。図２の例では、ポリゴン１２の頂点をＡ、Ｂ、Ｃとして示す。この例では、ポリゴン１２、１４は隣接し、頂点Ｂ、Ｃはポリゴン１２、１４により共有されるので、ここでは、ポリゴン１４は、頂点Ｂ、Ｃ、Ｄを備える。
【００３５】
リスト２４は、各ポリゴンについて、このポリゴンに含まれる、リスト２２の頂点を列挙する入力を含む。例えば、「Ｐ１」で示される、リスト２４のポリゴン１２の入力は、頂点「ＡＢＣ」を含む。
【００３６】
リスト２６は、リスト２４の各ポリゴンについて、このポリゴンと関連付けられたテクスチャピースを画定するＵＶ座標のセットを含む。例えば、ポリゴン１２と関連付けられた入力「Ｐ１」は、アトラス６のテクスチャピース２８を画定する３ポイントの、（ｕ１，ｖ１）で示される座標を含む。ポリゴン１４に対応し、Ｐ２で示される入力についても同様である。入力Ｐ２は、リスト２６によって、テクスチャピース２９を画定する３ポイントの座標（ｕ２，ｖ２）と関連付けられる。
【００３７】
例えば、データ１０は、当業者に良く知られた規格「ＯｐｅｎＧＬ」（open graphics library）と互換性を有する。
【００３８】
図３は、送信機４０から受信機４２までオブジェクト２を伝達するための装置の例を示す。送信機４０及び受信機４２は、それらの間で、データ交換リンク４４によりデータを交換することができる。一般に、送信機４０と受信機４２とは、数メートル又は数キロメートルにより互いに分離される。リンク４４は、一般に、インターネット（ワールドワイドウェブ）のような長距離情報伝達ネットワークにより設けられるリンクである。
【００３９】
送信機４０は計算部４６を備え、計算部４６は、情報記録媒体４８、プログラム可能な電子計算部５０、及び、データ交換インターフェイス５２を含む。
【００４０】
媒体４８は、図４の圧縮方法を実行するのに必要な指令を含む。計算部５０は、媒体４８に記録された指令を読み込んで、実行する。インターフェイス５２は、リンク４４上でのデータ１０の交換及び転送を可能にする。
【００４１】
例えば、送信機４０は、メディアコンテンツ分配サーバである。ここでは、受信機４２は、コンピュータ又は移動通信装置のようなクライアント端末である。特に、受信機４２は、オブジェクト２を表示する（「描写する」）ことができる。これを達成するために、それは、画像処理部４８、及び、例えば、計算部４６と同様の計算部４７を備えている。
【００４２】
受信機４２がデータ１０を伸張して、オブジェクト２をスクリーン４９上に描写できるように、送信機４０は、データ１０を圧縮して、次にそれを受信機４２に送信することができる。
【００４３】
データ１０の圧縮の１つの例は、図４のフローチャートを最初に参照して、図１〜７Ｃを用いて、説明されるであろう。この方法は、メッシュのプログレッシブ圧縮の方法である。
【００４４】
最初に、ステップ６０において、データ１０が計算部４６により取得される。
【００４５】
次に、ステップ６２では、メッシュ４は圧縮方法の次の工程のためにフォーマットされる。これらの工程、特に、簡略化は、以下でより詳細に説明されるであろう。
【００４６】
この工程は、最初に、メッシュ４のポリゴンの中から、異なるテクスチャを有する第１、第２の隣接するポリゴンを見つける動作６４を含む。
【００４７】
もしも、２つのポリゴンは、それらの間に第１、第２の共有の頂点を有し、共有のエッジによりつながれているのならば、それらは隣接するといわれる。
【００４８】
もしも、アトラス６の対応するテクスチャピースの交差（intersection）がゼロ集合（zero set）である、すなわち、テクスチャピースがアトラス６内で完全に分離されているならば、ここでは、２つのテクスチャは異なるといわれる。例えば、テクスチャピース２８、２９の間の最短距離はゼロではないので、テクスチャピース２８、２９は分離されている。
【００４９】
ここでは、ポリゴン１２、１４は隣接し、共有の頂点Ｂ、Ｃを有する。その上、それらのテクスチャピース２８、２９は異なる。以下では、一般に、そのようなポリゴンを示すために、符号１２、１４も用いるであろう。同様に、ポリゴン１２、１４の共有の頂点を示すために、符号Ｂ、Ｃを用いるであろう。
【００５０】
例えば、互いに隣接するとともに、リスト２６により別々のテクスチャピースと関連付けられるポリゴンを、リスト２４、２６を用いて、自動的に探索することにより、ポリゴン１２、１４は特定される。
【００５１】
ポリゴン１２、１４がいったん特定されると、次に、ステップ２６は、そのように特定されたポリゴンの各組みについて、以下に従って、これらのポリゴンを分離することを含む。
【００５２】
動作６６では、ポリゴン１４において、頂点Ｂ、Ｃは、分割頂点として知られる頂点Ｂ'、Ｃ'で置換される。頂点Ｂ'、Ｃ'は、それぞれ、空間において、頂点Ｂ、Ｃと同じ位置を占める。このように、頂点Ｂ'、Ｃ'は、頂点Ｂ、Ｃと同じ座標を有する。
【００５３】
例えば、リスト２２において、頂点Ｂ'、Ｃ'が生成され、リスト２４の多項式１４の定義ＢＣＤが定義Ｂ'Ｃ'Ｄで置換される。このように、データ１０において、新しいエッジＢ'Ｃ'が生成され、ポリゴン１４のエッジＢＤ、ＣＤが、それぞれ、エッジＢ'Ｄ、Ｃ'Ｄで置換される。その後、そのように修正されたポリゴン１４は、符号１４'を有するであろう（図５）。この明細書では、ポリゴンにおいて２つの頂点Ｘ、Ｙを直接つなぐエッジは、符号「ＸＹ」を有するであろう。
【００５４】
動作６８では、ポリゴン１２、１４'の間に挟まれた少なくとも１つの中間のポリゴンを生成するために、長さゼロの少なくとも２つのエッジが、一方では、頂点ＢＢ'の間に、他方では、頂点ＣＣ'の間に生成される。これらのエッジＢＢ'、ＣＣ'はポリゴン１２、１４'をつなぐ。この接続は、ポリゴン１２、１４'の接合部において、穴の出現のような、追加のアーティファクトの出現を避けるために必要である。この中間のポリゴンの面は、それがスクリーン上で見えず、また、目に見えるアーティファクトを生成しないように、ゼロの表面を有する。ここでは、メッシュ４のポリゴンは必ず３角形であるから、ポリゴン１２、１４'の間に挟まれた、２つの生成された中間の３角形のポリゴン６７、６９がある（図５）。例えば、これらのポリゴン６７、６９を形成するために、追加のエッジＢ'Ｃが生成される。ここでは、ポリゴン６７は、エッジＢＣ、ＣＢ'、ＢＢ'により画定され、ポリゴン６９はエッジＢ'Ｃ'、ＣＣ'、ＣＢ'により画定される。新しいエッジＢＢ'、ＣＣ'、ＣＢ'は、リスト２４にこれらの新しいポリゴン６７、６９の定義を追加することにより生成される。例えば、ポリゴン６７、６９は値ゼロのテクスチャを有し、このように、リスト２６によるいかなるテクスチャピースとも一致しない。
【００５５】
図５の理解を容易にするために、３角形６７、６９はゼロではない表面で描かれているが、上で説明されるように、それらはゼロの表面を有している。同様に、この図では、エッジＢＢ'、ＣＣ'はゼロではない長さで表されているが、そういうわけではない。そこにある各ポリゴンは、特にリスト２４において、その頂点の関数として定義されているので、ポリゴンがゼロの表面を有しているという事実は、それがメッシュ４に存在しないということを意味していない。エッジについても同様である。
【００５６】
これらの動作６６、６８は、メッシュ４に対する修正を反映するための、データ１０のリスト２２、２４、２６の対応する修正に帰結する。
【００５７】
頂点Ｂ、Ｃを複製し、ポリゴン１４においてそれらを頂点Ｂ'、Ｃ'と置換することは、ポリゴン１２、１４を互いに分離することを可能にする。このことは、頂点Ｂ、Ｃの１つが削除されるときに、これらの２つのポリゴンの間にテクスチャの違いが存在するという情報を失うことを防ぐ。その上、頂点Ｂ'、Ｃ'がエッジにより頂点Ｂ、Ｃにつながれているという事実は、ポリゴン１２、１４'が、方法の残りの部分で、互いに対して置換されるのを防ぐ。そのような置換はメッシュ４に穴を生成し、オブジェクト２の見栄えを劣化させるであろう。エッジの長さのゼロの値及びポリゴン６７、６９の面の表面のゼロの値は、頂点Ｂ、Ｃのこの複製が、メッシュ４及びオブジェクト２の画像外観の修正を必要としないことを意味する。接続情報に基づく更なる簡略化動作が、これらのポリゴンのあまりに早い消滅とならないように、これらのエッジは、メッシュ４の接続の局所的な修正を可能にする。
【００５８】
修正データ１０において、異なるテクスチャを有して隣接する、ポリゴンの他の組みが見つからないときに、ステップ６２は終了する。
【００５９】
ステップ６２の終わりに、メッシュ４は異なるテクスチャの隣接するポリゴンを有していない。
【００６０】
次に、ステップ７０では、メッシュ４が簡略化される。この簡略化は、メッシュ４の頂点及びポリゴンの削除を含む。この簡略化の目的は、削除されるポリゴンよりも広い面を有する新しいポリゴンを生成することにある。これらの新しいポリゴンは、削除されるポリゴンを置換するであろう。このようにして、メモリに、より少ない空間を要する簡略化された画像を得る。
【００６１】
このことについて、ステップ７０は、
所定の基準に応じて、削除される頂点を特定する動作７２、
特定された頂点、これらの頂点を互いにつなぐエッジ、及び、これらの頂点とメッシュ４の他の頂点とをつなぐエッジを削除する動作７４、
削除されなかった頂点をつなぐ新しいエッジを生成して新しいポリゴンを生成し、削除されたポリゴンの各テクスチャから新しいポリゴンの面を覆う新しいテクスチャを生成する動作７６
を含む。
【００６２】
動作７２での特定は、例えば、最も近い隣接する頂点の数のような、接続基準に基づいてリスト２２から頂点を選択することにより、行われる。
【００６３】
動作７４は、メッシュ４からポリゴンの一部を削除した結果を有する。
【００６４】
この例では、ステップ７０は、非特許文献１、６記載のアルゴリズムにより行われる。
【００６５】
図６Ａ〜６Ｃは、メッシュ４の部分８０での、このアルゴリズムの働きを示す。
【００６６】
このアルゴリズムは２つのステップで働く。最初に、いわゆる「征服（conquest）」段階では動作７２〜７４が行われる。メッシュ４の頂点は、グラフの格好でメッシュ４のエッジに沿って１段ずつ自動的に移動することにより走査される。頂点が走査される順序は、所定の「グラフ走査」により定義される。各頂点について、その頂点の価数、すなわち、エッジによって直接接続される、この頂点のすぐ隣の頂点Ｓ'の数が決定される。もしも、この頂点Ｓが所定のしきい値よりも小さな価数を有するならば、頂点Ｓは削除される。次に、この頂点Ｓとそのすぐ隣の頂点とをつなぐエッジが削除される。これらのエッジは、図６Ａでは符号ＳＳ'を有する。新しいエッジ８０、８１、８２がエッジＳＳ'を置換するために生成される（図６Ｂ）。
【００６７】
第２段階又は片付け段階では、アルゴリズムは、有利には、一定の過剰な頂点８３と、これらの頂点をつなぐエッジとを削除し、通常の形状を有する新しいポリゴン８４を得るために、代わりに、新しいエッジを生成する。エッジがそこで生成されるので、動作７６はこの段階で部分的に行われる。
【００６８】
これらの動作７２、７４、７６は、リスト２２、２４、２６及びアトラス６の対応する修正につながって、メッシュ４に対してなされた修正を反映する。
【００６９】
有利には、動作８９では、いわゆる増分データ又は改良（refinement）データが記録される。このデータは、削除された頂点及びエッジと、ステップ７０で生成された頂点及びエッジとが何であるかを示す。例えば、このデータは、ステップ７０で削除された頂点のリストと、これらの削除された頂点のそれぞれについて、この削除された頂点がエッジで直接接続される隣接する頂点のセットを与えるリストとを含む。増分データは、伸張方法で用いられるときに、ステップ７０の動作とは逆の動作を実行することを可能にする。このことは、ステップ７０の最後に得られる簡略化されたメッシュとこの増分データとから、ステップ７０を適用する前に存在したようなメッシュを再構成することを可能にする。有利には、このデータは同様に、情報を失うことなしに、再構成された各ポリゴンと関連付けられたテクスチャピースを見つけることを可能にする情報を含む。
【００７０】
図７Ａは、オブジェクト２の簡略化の後のステップ７０の最後に得られる、簡略化オブジェクト９４としても知られる、オブジェクト２の簡略化バージョンを示す。オブジェクト９４は、オブジェクト２よりも少ない頂点とポリゴンとを有する。この小さな解像度のために、このオブジェクト９４を表わすデータは、データ１０のものよりも小さなサイズを有する。このように、オブジェクト９４の伝達は容易にされる。
【００７１】
この例では、より高い圧縮率を得るために、簡略化は複数回繰り返される。この場合、方法は更に、ステップ７０の最後に、追加の簡略化ステップ９１を含む。例えば、ステップ９１は、このオブジェクト９４を簡略化するために、オブジェクト９４に行われることを除いて、ステップ７０と同一である。一般に、ステップ９１のそれぞれの新しい反復では、新しい頂点を削除するために、削除される頂点の選択基準は拡げられる。
【００７２】
このように、ステップ９１の最後に、図７Ｂに示されるような、最終オブジェクト９６として知られるオブジェクト２の最終バージョンが得られる。オブジェクト９６はオブジェクト９４よりも少ない頂点とポリゴンとを含む。それは、オブジェクト２の、オブジェクト９４よりも簡略化されたバージョンに対応する。ステップ９１をこのように実行して生成される増分データは同様に記録される。
【００７３】
最後に、ステップ９２で、オブジェクト９６はインターフェイス５０に伝達される。
【００７４】
本方法は、圧縮の最後に、オブジェクト９４、９６での画像アーティファクトの出現を減少させるために、特に有利である。事実、古典的に用いられるプログレッシブ圧縮方法は、隣接するポリゴンの間のテクスチャの違いを考慮していない。そのような古典的な方法では、ポリゴン１２、１４の頂点Ｂ、Ｃは、動作７４で直ぐに削除されるかもしれない。次に、ポリゴン１２、１４が削除されて、新しいポリゴンで置換される。次に、ポリゴンのテクスチャは、テクスチャピース２８、２９のポイントから決定される新しいテクスチャで置換される。例えば、これらの新しいポリゴンの１つが、ピース２９の２ポイントと、ピース２８の１ポイントとにより定義される新しいテクスチャピースと関連付けられることがしばしば発生する。この新しいピースは、ピース２８、２９の間に位置する画像２７の一部分を含む。ところで、この一部分は、しばしばピース２８、２９とは全く異なる。そして、このことは、簡略化されたオブジェクトのポリゴン１２、１４の位置において、とても異なり、かつ、特に目に見えるテクスチャピースの出現を引き起こす。このことは、ポリゴン１２、１４のテクスチャの違いのために特に目に見える画像アーティファクトをもたらす。
【００７５】
図８Ａ、８Ｂはそれぞれオブジェクト９４'、９６'を示す。
【００７６】
オブジェクト９４'は、オブジェクト２に適用され、図４の方法と同一である（ステップ９１はない）が、ステップ６２が行われていない圧縮方法の最後に得られる簡略化されたオブジェクトである。
【００７７】
同様に、オブジェクト９６'は、ステップ７０、９１は適用されるがステップ６２が行われないように、オブジェクト２の圧縮方法を行った後に得られる最終オブジェクトである。
【００７８】
オブジェクト９４'は、画像アーティファクト１００を含むことを除いて、オブジェクト９４と同一である。同様に、オブジェクト９６'は、画像アーティファクト１０２を含むことを除いて、オブジェクト９６と同一である。これらのアーティファクト１００、１０２は、ステップ７０又はステップ９１で、テクスチャ情報の全部又は一部が失われたポリゴンに対応する。この情報の消失は、異なるテクスチャを有する隣接するポリゴンの削除の結果である。これらのポリゴンは、簡略化工程の前のステップ６２での分離を受けないので、動作７４で削除される。
【００７９】
他方、図４の方法が適用されるときに、頂点Ｂ、Ｂ'、Ｃ、Ｃ'のいずれもが削除されないので、隣接するポリゴン１２、１４が異なるテクスチャを有するという情報は失われない。それゆえ、情報のこの消失は、より大きな数の、ステップ７０、９１の反復の後にだけ発生することができる。このように、目に見えるアーティファクトは出現しないか、それらはもっと後の圧縮段階で出現する。ところで、以下を熟読すれば理解されるように、目に見えるアーティファクトが出現するのが、圧縮のより後の段階であればあるほど、それらは伸張ではより早く消滅する。図４の方法を用いると、伸張ではアーティファクトはこのように削除されるか、なおいっそう短命である。
【００８０】
図９は、オブジェクト９６'を表わすデータのセット１０６を含む情報記録媒体１０４を示す。
【００８１】
簡略化されたオブジェクトは、その後、描写されるために、送信機４０から受信機４２に送られる。同様に、ステップ７０又はステップ９１のそれぞれの実行とそれぞれ関連付けられた増分データは、同様に、送信機４０から受信機４２に送られる。この伝達は、例えば、連続的に行われる。
【００８２】
図１０は、オブジェクト２を再構成する伸張方法を示す。この方法は、例えば、特許文献２に記載されたものである。
【００８３】
ステップ１１０では、送信機４０から送信された後に、オブジェクト９６を表わすデータは最初に受信機４２により取得される。受信機４２は、そのように受信されたオブジェクト９６を直ちに描写する。
【００８４】
次に、ステップ１１２で、受信機４２は、ステップ９１で生成された増分データを用いて、このステップ９１で行われたものとは逆の動作を行って、オブジェクト９６からオブジェクト９４を自動的に再構成する。
【００８５】
この増分データは、一般的に、オブジェクト９６を表わすデータを受信した後、そして、しばしばスクリーン４９上にオブジェクト９６を描写した後に、受信機４２により取得される。そして、このデータから、受信機４２はオブジェクト９６を修正して、ステップ９１で削除されたメッシュの頂点を追加する。このことは、オブジェクト９６のメッシュのある種のポリゴンを削除し、それらをより多くの、より削減された表面を有する、代わりのポリゴンで置換することにつながる。
【００８６】
このように、オブジェクト９６において、受信機４２は、
ステップ９１の簡略化で削除された頂点を追加し、
追加のポリゴンを生成するために、ステップ９１で生成されたメッシュのエッジを、追加された頂点とオブジェクト９６の現在ある頂点とをつなぐ追加のエッジで置換し、
置換されたポリゴンの各テクスチャと増分データとから、これらの追加のポリゴンのための追加のテクスチャピースを生成する。
【００８７】
ステップ１１２の最後に、受信機４２は、オブジェクト９４を再構成する。次に、オブジェクト９４はスクリーン４９上のオブジェクト９６の位置に描写される。
【００８８】
そして、ステップ１１４で、受信機４２は、ステップ７０で生成された増分データを用いて、再構成されたオブジェクト９４からオブジェクト２を再構成する。このステップ１１４は、例えば、それがオブジェクト９６ではなくてオブジェクト９４に適用されることを除いて、ステップ１１２と同一である。
【００８９】
このように、オブジェクト２は、それが圧縮前に有していたのと同一又は近い詳細さのレベルに到達するまで、増分データから、それらを受信するうちに正確さを増加して、連続的な改良により、プログレッシブに再構成される。オブジェクト９４のような中間の簡略化されたオブジェクトは、それらが再構成されると直ぐに描写される。このように、受信機４２は、それが増分データを受信し、再構成の工程を実行すると正確さが増加するオブジェクトを描写する。この方法は、リンク４４のフローレートが制限され、又は、大きな変動を受けるときに、便利である。このことは、受信機４２でのオブジェクトの描写が「ラグ」効果によって乱されることを防ぐ。同様に、このことは、伸張して描写することを開始できる前に、全ての圧縮されたオブジェクト２が受信機４２に送信されるのを待つことが必要な場合と比べて、受信機４２により描写されるオブジェクト（簡略化バージョンでも）の待ち時間を限定する。
【００９０】
簡略化されたオブジェクトは、伸張の間に、圧縮によりそれらが生成されたのとは逆の順序で描写されるので、目に見えるアーティファクトは、圧縮の間に遅く出現すればするほど、それは、伸張の間に、伸張されたオブジェクトのプログレッシブ描写からより早く消滅するであろう。
【００９１】
有利には、ステップ１１６で、再構成されたオブジェクト２のメッシュがフォーマットされ、ステップ６２で生成された頂点及びエッジを削除する。
ここでは、このステップは、
頂点Ｂ'、Ｃ'をそれぞれ頂点Ｂ、Ｃで置換すること
エッジＢＢ'、ＣＣ'、Ｂ'Ｃを削除すること
を含む。
【００９２】
このように、ポリゴン６７、６９は削除され、ポリゴン１２、１４が再びオブジェクト２においてそれらの最初の配置をとる。
【００９３】
多くの他の実施の形態が可能である。
【００９４】
オブジェクト４は異なることができる。それは、メッシュの形で表されることができるどのようなオブジェクトを含んでも良い。同様に、アトラス６は異なるように選択されることができる。
【００９５】
ポリゴンは３角形以外の形状を有しても良い。例えば、ポリゴンは平行６面体形状を有する。
【００９６】
データ１０は、Ｄｉｒｅｃｔ３Ｄのような、異なる画像規格と互換性のあるフォーマットで記録されても良い。
【００９７】
送信機４０は異なっても良い。例えば、計算部４６は送信機４０とは別にあっても良い。このように、オブジェクト２の圧縮は送信機４０で行われず、送信機４０は、データを受信機４２に転送する役割だけを有している。
【００９８】
受信機４２は異なっても良い。例えば、それは、タブレット、携帯電話、テレビセットであっても良い。同様に、オブジェクト２の描写は受信とは独立して行われても良い。このように、用語「受信機」４２は、２つの別々の装置、すなわち、オブジェクト２を受信するもの、このオブジェクト２を描写する別のものを包含する。
【００９９】
ステップ６２は、異なるように行われても良い。
【０１００】
特に、動作６４は、隣接するポリゴンを特定するために、異なるように行われることができる。例えば、図１１は、メッシュ４の一部分のポリゴン１２、１４を特定する他の方法を示す。この方法により、所定の順序で次々とメッシュの頂点を選択することにより、メッシュのエッジは自動的に走査される。選択された各頂点１５０について、ここでは、矢印１５４により特定される所定の方向に頂点１５０の周りを移動することにより、この頂点１５０の直ぐ隣の全ての頂点１５２、１５３は走査される。これらの隣接する頂点は、エッジにより頂点１５０と直接接続される頂点として定義される。単純化のために、頂点１５２、１５３だけが符号により示される。次に、頂点１５０以外の他のすぐ隣の共有の頂点１５６を有している頂点１５２、１５３を、もしもそのようなものが存在するならば、判定する。もしもそうであるならば、このことは、頂点１５２、１５３がいくつかのポリゴンにより共有されていることを示す。この例では、隣接するポリゴン１５８、１６０を特定する。ポリゴン１５８は、頂点１５０、１５２、１５３を備える。ポリゴン１６０は、頂点１５２、１５３、１５６を備える。次に、ポリゴン１５８、１６０と関連付けられたテクスチャピースが異なるものであるか確認する。
【０１０１】
変形例として、頂点Ｂ'、Ｃ'で置換されるのは、ポリゴン１２の頂点Ｂ、Ｃである。
【０１０２】
ステップ９１は省略されても良い。この場合、オブジェクト９４が最終オブジェクトであって、これが送信されるものである。次に、伸張方法からステップ１１２が省略される。
【０１０３】
他の変形例によれば、送信前にオブジェクト２の圧縮レベルを増加させるために、ステップ９１は複数回繰り返される。次に、伸張方法は、ステップ９１が繰り返された回数に等しい数の、ステップ１１２と同一のステップを含む。
【０１０４】
他の変形例では、ステップ９１が少なくとも１回行われるときに、例えば、ステップ９１をそれぞれ行う前に、ステップ６２が繰り返される。もしも、ステップ９１を行っている間にポリゴン６７、６９が削除されたならば、それらはこのようにステップ９１をもう一度行う前に再生されるかもしれない。このことは、このステップ９１でポリゴン１２、１４が削除されるリスクを限定する。この場合に、ステップ１１６は何回か繰り返されても良い。例えば、ステップ１１６は、ステップ１１２又はステップ１１４の後の伸張中に適用される。
【０１０５】
ステップ７０は、異なるように行われても良い。例えば、非特許文献７記載のアルゴリズムを用いる。
【０１０６】
ステップ１１６は省略されても良い。このステップは、ステップ１１４を適用する前に、再構成されたオブジェクト９４のメッシュを片付けるために、ステップ１１２の後に適用されても良い。
【０１０７】
他の実施の形態では、ステップ６２の間に、頂点Ｂ、Ｃと同様に、頂点Ｂ'、Ｃ'が動作１８０でマーキングを受けて（図４）、好ましくは、それらはステップ７０で削除されるべきではないことを示す。例えば、このマーキングは、各頂点についてリスト２２に追加される、追加のデータビットの所定値である。このように、ステップ７０では、頂点がそのようなマーキングを有しているかを調べる確認が、動作７２で行われる。例えば、メッシュの全ての頂点の第１の走査が行われる。もしも、マークキングされていない頂点が見つかって、それが、削除されるための基準を満たすならば、それは削除される。他方で、もしもそれがマーキングされていれば、それは直ぐには削除されず、メッシュの頂点の第２の走査で調べられるだけであろう特定のリストで示される。もしも、ステップ７０が、この頂点を削除する必要なしに終了できるのであれば、この頂点は削除されないであろう。もしも、この頂点を削除しないことが不可能であれば（例えば、メッシュの規則性のある特性を維持するためにこの頂点の削除が要求されるために）、この頂点は削除される。言い換えると、この頂点の削除は、完全に必要となるまで遅延される。簡略化によりもたらされるメッシュの修正を考慮するために、マーキングはステップ７０、ステップ９１をそれぞれ適用した後に、繰り返されることができる。極端な場合では、そのようにマーキングされた頂点の削除は禁止され、目に見えるアーティファクトが全く出現しないであろうことを保証する。
【０１０８】
最後に、異なるテクスチャピースを特定するための他の方法が可能である。例えば、簡略化されたバージョンでは、もしも、複数のテクスチャピースが、画像２７において共通のポイントを有していなければ、それらのテクスチャピースは異なる。他の変形例では、２つのテクスチャピースを隔てる最短距離が所定のしきい値よりも断然大きいときだけ、これらのテクスチャピースは異なる。この所定のしきい値は、ゼロに等しいか、ゼロよりも断然大きくても良い。
【０１０９】
テクスチャピースが異なっているか、そうでないかを判定するために、代表テクスチャ特性を比べることも可能である。例えば、この特性は各テクスチャピースについて計算され、もしも、第１のピースと第２のピースについて、この特性値の間の差異が所定のしきい値よりも大きければ、これらのテクスチャピースは異なるといわれる。特性は、ピースに含まれる色のヒストグラムの中央値、最大値又は最小値であっても良い。特性は、フラクタル次元又はハースト指数のような、テクスチャに出現する画像パターンの代表量であっても良い。代表特性に基づく後者のアプローチは、画像２７のテクスチャピースを画定するポイントの位置を用いない。
【図１】
0006689269.tif 000002
【図２】
0006689269.tif 000003
【図３】
0006689269.tif 000004
【図４】
0006689269.tif 000005
【図５】
0006689269.tif 000006
【図６Ａ】
0006689269.tif 000007
【図６Ｂ】
0006689269.tif 000008
【図６Ｃ】
0006689269.tif 000009
【図７Ａ】
0006689269.tif 000010
【図７Ｂ】
0006689269.tif 000011
【図８Ａ】
0006689269.tif 000012
【図８Ｂ】
0006689269.tif 000013
【図９】
0006689269.tif 000014
【図１０】
0006689269.tif 000015
【図１１】
0006689269.tif 000016