(57)【要約】面細分化処理を用いて三次元オブジェクトの受信及び再構築を行うために、角頂（１２、１８）データを、角頂（１８’Ａ）の変位に関する情報と共に送信する、三次元画像データ（１４）の送信及び受信のための方法及び装置を開示する。用いる方法は、角頂（１２、１８、１８’Ａ）のより小さな変位のすべての前に、角頂（１２、１８、１８’Ａ）のより大きな変位のすべてを送信し、受信して適用するという特徴がある。このため、処理が不完全に終わった場合、面（１４）精度は相応な程度になるが、イメージはばらばらにならない。送信及び受信処理は、（ＳＰＨＩＴツリーが考案された）二次元的な面ではなく、三次元オブジェクトに適用するＳＰＨＩＴツリーを用いる。このＳＰＨＩＴツリーは、また、角頂の変位の方向を表す符号ディジットの必要性を排除する。データ圧縮及び復元は、算術コーディング・データ圧縮方法を用いて行う。
2004535028.tif 000002
【特許請求の範囲】
【請求項１】
面細分化によって三次元面を再構築するのに用いる角頂位置及び変位情報を伝送するための装置であって、面細分化処理で発生する個々の角頂の座標を定義する手段、そして変位のより無意な要素のすべてを送信する前に変位のより有意な要素のすべてを送信する手段からなる装置。
【請求項２】
前記変位が２進数として定義され、前記より有意な要素が、より大きな有意性を持つ２進数字である、請求項１による装置。
【請求項３】
大きさが減少する順序で前記変位を選択する手段、有意性が減少する順序で、変位を表すために用いた各位の２進数字を選択する手段、変位の大きさの順序で、選択２進数字に等しい最上位の数字を持つ変位の角頂の合計数と座標とを送信する手段、そして、変位の大きさが減少する順序で、先に選択した位の２進数字に等しい最上位の数字を持つことが先に分かった各角頂に対する変位の表現内の選択位ビットを送信する手段を含む、請求項２による装置。
【請求項４】
前記送信手段がデータ圧縮手段からなる、前記請求項のいずれかによる装置。
【請求項５】
前記データ圧縮手段が、算術コーディング・データ圧縮の使用を含む、請求項４による装置。
【請求項６】
どの角頂も変位可能である、前記請求項のいずれかによる装置。
【請求項７】
ＳＰＨＩＴツリーをコード化する手段を含み、前記ＳＰＨＩＴツリーが、三次元オブジェクトに適用されるという特徴がある、前記請求項のいずれかによる装置。
【請求項８】
ＳＰＨＩＴツリーをコード化する手段を含み、前記ＳＰＨＩＴツリーが、変位の各指標からの符号の欠如という特徴がある、前記請求項のいずれかによる装置。
【請求項９】
三次元イメージの受信及び再構築のための装置であって、面細分化によって三次元の面を再構築するのに使用する角頂位置及び変位情報を受信する手段、面細分化処理中に個々に発生する角頂の座標の定義を受信する手段、そして変位のより無意な要素のすべての前に、変位のより有意な要素のすべてを受信する手段からなる装置。
【請求項１０】
前記変位が２進数として定義され、前記より有意な要素が、より大きな有意性の２進数字である、請求項９による装置。
【請求項１１】
変位の大きさの順序で、選択２進数字に等しい最上位の数字を持つ変位の各角頂の合計数及び座標を受信する手段を含み、前記変位が、大きさが減少する順序で、伝送のために選択されて、そして、変位を表すために用いる各位の２進数字が、有意性が減少する順序で、伝送のために選択されており、さらに、先に選択された位の２進数字に等しい最上位の数字を持つことが先に分かっている各角頂に対して、変位の大きさが減少する順序で、変位の表現内の選択位ビットを受信する手段を含む、請求項１０による装置。
【請求項１２】
前記受信手段がデータ復元手段からなる、請求項９から１１のいずれかによる装置。
【請求項１３】
前記データ復元手段が、算術コーディング・データ圧縮の使用を含む、請求項１２による装置。
【請求項１４】
どの角頂も変位が可能な、請求項９から１３のいずれかによる装置。
【請求項１５】
ＳＰＨＩＴツリーを解読する手段を含み、前記ＳＰＨＩＴツリーが、三次元オブジェクトに適用されることを特徴とする、請求項９から１４のいずれかによる装置。
【請求項１６】
ＳＰＨＩＴツリーを解読する手段を含み、前記ＳＰＨＩＴツリーが、各変位に符号指標が欠如しているという特徴がある、請求項９から１５のいずれかによる装置。
【請求項１７】
面細分化によって三次元の面を再構築するのに使用するための、角頂位置及び変位情報の伝送方法であって、面細分化処理中に個々に発生する角頂の座標を定義するステップ、そして変位のより無意な要素のすべての前に、変位のより有意な要素のすべてを送信するステップを含む方法。
【請求項１８】
前記変位を２進数として定義するステップ、そして、より有意な要素が、より大きな有意性を持つ２進数字であることを提供するステップを含む、請求項１７による方法。
【請求項１９】
大きさが減少する順序で前記変位を選択するステップ、有意性が減少する順序で、変位を表すのに用いた各位の２進数字を選択するステップ、変位の大きさの順序で、選択２進数字に等しい最上位の数字の変位を持つ各角頂の合計数及び座標を送信するステップ、そして先に選択した位の２進数字に等しい最上位の数字を持つことが先に分かっている各角頂に対して、変位の大きさが減少する順序で、変位の表現内の選択位ビットを送信するステップを含む、請求項１８による方法。
【請求項２０】
送信データに対してデータ圧縮を用いるステップを含む、請求項１７から１９のいずれかによる方法。
【請求項２１】
前記データ圧縮の使用が、算術コーディング・データ圧縮に用いるのに適当な手段を使用することを含む、請求項２０による方法。
【請求項２２】
どの角頂も変位が可能な、請求項１７から２１のいずれかによる方法。
【請求項２３】
ＳＰＨＩＴツリーをコード化することを含み、前記ＳＰＨＩＴツリーが、三次元に適用されるという特徴がある、請求項１７から２２のいずれかによる方法。
【請求項２４】
ＳＰＨＩＴツリーをコード化することを含み、前記ＳＰＨＩＴツリーが、各変位に対する符号指標の欠如という特徴がある、請求項１７から２３のいずれかによる方法。
【請求項２５】
三次元イメージの受信及び再構築方法であって、面細分化によって三次元の面を再構築するのに使用する角頂位置及び変位情報を受信するステップ、面細分化処理中に個々に発生する角頂の座標定義を受信するステップ、そして変位のより無意な要素のすべての前に、変位のより有意な要素のすべてを受信して適用するステップを含む方法。
【請求項２６】
前記変位の定義を２進数として受信するステップ、そして、より有意な要素が、より大きな有意性を持つ２進数字であることを提供するステップを含む、請求項２５による方法。
【請求項２７】
変位の大きさの順序で、選択２進数字に等しい最上位の数字を持つ変位の各角頂の合計数及び座標を受信するステップ、この場合、前記変位が、大きさが減少する順序で、伝送のために選択されており、変位を表すのに用いた各位の２進数字が、有意性が減少する順序で、伝送のために選択されており、そして変位の大きさが減少する順序で、先に選択した位の２進数字に等しい最上位の数字を持つことが先に分かっている各角頂に対する変位の表現内の選択位ビットを受信するステップを含む、請求項２６による方法。
【請求項２８】
受信データに対してデータ復元を用いるステップを含む、請求項２５から２７のいずれかによる方法。
【請求項２９】
前記データ復元の使用が、算術コーディング・データ圧縮に適用可能な手段の使用を含む、請求項２８による方法。
【請求項３０】
どの角頂も変位が可能な、請求項２５から２９のいずれかによる方法。
【請求項３１】
ＳＰＨＩＴツリーを解読することを含み、前記ＳＰＨＩＴツリーが、三次元オブジェクトへの適用という特徴がある、請求項２５から３０のいずれかによる方法。
【請求項３２】
ＳＰＨＩＴツリーを解読することを含み、前記ＳＰＨＩＴツリーが、各変位に関する符号指標の欠如という特徴がある、請求項２５から３１のいずれかによる方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、効率的な保存及び伝送のための、三次元オブジェクト・データの圧縮に関する。本発明は、特に、表面テキスチャで「装う」、微細なメッシュ・ワイヤ・フレーム面の三次元オブジェクトの外観を生成することに関する。これらの外観は、レンダリングして陰影を施すことによって、写実的な容姿の、オブジェクトのイメージに生成し、ワイヤ・フレームの回転、反射及び移動によって動かすこともできる。本発明は、とりわけ、単純な形状の初期ワイヤ・フレーム「ハル」から始まる面分割処理を繰り返して適用することよって、そのような微細なメッシュ・ワイヤ・フレーム面を生成することに関する。最終的な、被覆した詳細なオブジェクトは、回転、移動、大きさ調整、あるいは単純な初期ハルの変形によって動かすことができる。
【背景技術】
【０００２】
本文の三次元オブジェクトは、多角形（小面）のコレクションによって表す非常に薄いシェルであり、多角形の各角（角頂）における三次元位置ベクトルによって三次元空間内に定義される。各多角形は、関連する色調、飽和度、指向及び陰影効果を持つ。三次元オブジェクトは、角頂の全セットの移動、回転、大きさ調整及び変形によって動かすことができる。単純なオブジェクトでさえ、何百万ものピクセルを持ち、各ピクセルは、それに関する、空間内に（高精度で）その位置を定義する多ビットのデータを持つ。さらに、各小面は、それに関する、形状を構成する角頂、そして色調、飽和度、反射等の視覚特性を定義する多ビットのデータを持つ。したがって、三次元視覚オブジェクトはデータ量が非常に大きい。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
問題が起こるのは、三次元オブジェクトを、例えば、インターネット上に、または携帯電話に送信する、あるいはディスクまたは他のメモリ・デバイス上に保存するときである。何メガバイトものデータは、送信するのに時間がかかるし、また多くの容量を占拠する。１４．４ｋｂ／ｓの標準インターネット速度では、１メガバイトの視覚オブジェクトをダウンロードするのに９分以上を要する。より遅い携帯電話の情報伝達速度では、比例して、より長い時間が必要である。このような遅延は受け入れ難い。
【０００４】
もう一つの問題は、三次元視覚オブジェクトのビューを操ろうとするときに起こる。従来の二次元表示装置においては、三次元データの、二次元ディスプレイ上への投影を介して視覚化を達成する。受信装置は、操作イメージを適当な状態で見るのに、非常に多量な位置データ（各角頂に対して少なくとも一セットの計算）を計算する必要がある。さらに、多くの個々の三次元オブジェクトから「シーン」が構成される場合に困難が生じる。計算は、ビューポイントに関して移動あるいは回転する各オブジェクトに対して行わなければならない。全体的に、ある程度の写実性を持つ複雑な三次元視覚オブジェクトは、高速伝送には適していない、あるいは現代の装置での、その後の方向変更には向かない。
【０００５】
それでも各面の角頂位置を定義するデータを送信しなければならないという問題を避けるために、リダクション技術が用いられている。少数の角頂を持つ、単純化した形状を用い、この単純化した形状の非常に少数な角頂の位置的な詳細を送信する。受信側は、この単純化した形状を、面分割アルゴリズムと共に用いる。単純化した形状を定義する各多角形を、面分割処理において処理（分割）し、結合したより小さな多角形を生成する。この処理は、適当な繊細さ（解像度そして／あるいは表面平滑性）が得られるまで、新しい多角形に適用する。
【０００６】
このような技術の性能の例としては、球体がある。非常に高画質な球体を、四面体（四つの三角形の面を与える四つの角頂）等の（ハルとして知られる）単純化したオブジェクトから、空間内に定義することができる。一般に、ハルは、最終的なオブジェクトに準同形である（同じエッジ接続性及び面連続性を持つ）べきである。例えば、四面体は、終止エッジを全く持たない連続的な単一面を持つ。したがって、球体に準同形である。
【０００７】
非常に単純なハルは、非常に限定的なレパートリーの最終オブジェクトのみを生成することができる。複雑なオブジェクトで高度な写実性を達成するためには、より複雑な初期ハルを用いなければならない。この技術を拡張するために、角頂の位置補正が行われている。分割アルゴリズムの各々のステージで、表面上の二つの既存の角頂を結ぶラインを分割して生成される新しい角頂の各々を、ＲＡＷアルゴリズムによって定義した、その位置に対する新しい位置に移動（変位）させる。この変位は、アルゴリズムの適用の特定なステージ（分割）で、ハルの詳細と共に送信され、特定な新たに生成した角頂に適用される。アルゴリズムの適用の特定なステージにおいて、選択した角頂は、選択した量だけ変位させる。その角頂に対する新しい（変位させた）位置を用いて、アルゴリズムの次の適用を行う。したがって、面分割アルゴリズムを用いる特定なステージの角頂を移動させることは、選択した角頂の位置の関数として位置が決定するすべての次の新しい角頂の位置に影響する。新たに生成した角頂のみが（生成時に、あるいはその直後に）移動可能であるため、生成可能な異なる形状には、あるいは特定な形状を達成するのに必要な情報伝達の経済性には、未だに制限がある。本発明は、これらの欠点を改善することを目的とする。
【０００８】
オブジェクトを構成する種々のポイント間の関係の完全性を保持するためには、デカルト座標系に基づく原点に対してではなく、選択した角頂が割り当てられている多角形に対して、選択角頂の変位を定義するのが通常である。関連する一つの多角形、あるいは複数の多角形の平面は、選択角頂に対して法線方向を定義するのに用いる。そして、この法線方向と、二つの直交接線方向とで変位を定義する。
【０００９】
同出願者が１９９９年１１月５日に出願した、英国特許出願第９９２６１３１．５号「画像の向上」には、上記のようなエッジ細分化法の説明がある。この方法では、新しい角頂の位置は、必ずしもエッジの中心にあるのではなく、最終オブジェクトの表現におけるエッジ及び角頂に与える（可視の、不可視の、滑らかな、等の）品質に依存している。
【００１０】
上記のシステムでは問題が起こる。面の特徴を生成するためには、連続したレベルの繊細さ（面分割アルゴリズムの連続適用）で、多数の変位を生成することがしばしば必要である。本発明は、微細な面の詳細に必要な変位の数を減少させるための方法及び手段を提供することを目的とする。
【００１１】
三次元イメージ生成には、二つの一般的なアプローチがある。第一のアプローチは分析的である。実際のオブジェクトの三次元スキャンを得、それから、オブジェクトを再構築するのに使用可能な最も単純なハルを見いだすために、（本質的に面分割処理とは正反対な）リダクション・アルゴリズムを適用する。第二のアプローチは構成的である。ハルを仮定し、所望のオブジェクトに十分に近いオブジェクトを生成するよう、その後の面分割ステージに補正を加える。アクセプタビリティを達成するまで、ハルへの修正と変位を行う。本発明は、分析的な処理の結果に適用することも可能ではあるが、第二の（構成的な）方法に改良を提供し、有用性を加えることを目的とする。
【００１２】
ハル分割及び角頂変位方法によってオブジェクトを再構築するのに必要な、単純化したデータの伝送でさえも、所望の速度よりも遅いこともあり、不完全な伝送から生じる問題にさらされる。これらの問題を克服するために、種々のコーディング技術が用いられている。
【００１３】
メッセージが切断した場合の一つの問題は、局所的な詳細がかなり損失してしまうことである。これを克服するために、アミール・サイド氏及びウィリアム・Ａ・パールマン氏は、１９９６年にＩＥＥＥへ、論文「階層的なツリーにおけるセット分割に基づく、新しい、速い、そして効率的なイメージ・コーデック」（"A New, Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees" IEEE Trans on Circuits and Systems for Video Technology 6（3）: pages 243-250 1996）を提示し、階層的なツリーにおけるセット分割（ＳＰＨＩＴ）方法を提供した。この論文は、二次元的フラット・イメージ（画像）に関するが、参照として本出願に組み込まれる。
【００１４】
サイド・パールマン方法では、ピクセルの座標を、変換サブバンドに対応する係数の角錐に「ユニット式の階層的なサブバンド変換」によってマッピングする。この場合の係数の数は、元のイメージ内のピクセル数と同じで、この係数の配列は、それから順次伝送スキームに用いる。
【００１５】
配列のコンテンツは、それらの２進数の大きさに従ってランク付けを行う。最上位ビット（ＭＳＢ）が１に設定されたすべての係数は、第一にランク付けを行う（その後、大きさが減少する順に行う）。最上位ビットが０に設定されているが第二の上位ビットが１に設定されたすべての係数は、次にランク付けし、同様に、その後、大きさが減少する順に行う。最大から最小まで、すべての係数が順番にランク付けされるまで、この処理を繰り返す。第二上位ビットが０に設定されるが各ビット（最上位ビットから最下位ビット（ＬＳＢ）まで）が１に設定された係数を数え、各２進数字に対してビット・カウント数を与える。これは、最下位ビット（ＬＳＢ）にビット・カウント数を割り当てるまで続ける。各係数の符号は、ランク付けの順序で付加する。
【００１６】
伝送においては、座標の表現に必要なビット（２進数字）の最大数を、デコーダに最初に送信する。それから、「分類パス」は、現在の（この場合は最上位の）ビットに対するビット・カウント数、現在の（この場合は最上位の）ビットが１に設定された係数が示すすべてのピクセルの座標、そして現在の（この場合は最上位の）ビットが１に設定され、大きさが減少する順序でランク付けされた全係数の符号を送信する。これで、現在の（最上位の）ビットに対する「分類パス」が終了する。
【００１７】
次に、「改善パス」は、ピクセルの座標を送信するのに用いたと同じ順序で、この、あるいは先の分類パスの対象である係数の各々に対する現在の（この場合は最上位の）ビットを送信する。「改善パス」は、これで終了する。
【００１８】
その後、現在の位のビットとして第二上位ビットを選択し、「分類パス」、その後に「改善パス」を実行する。最下位ビット（ＬＳＢ）が分類されて改善されるまで、あるいは許容可能な程度の歪み（所望のイメージからの狂い）が達成されるまでのいずれかが得られるまで、これを続ける。
【００１９】
最上位の係数が第一に送信されて、それらの最上位の２進数字が第一に送信されるため、（混雑する通信環境で起こり得る）伝送の中断に際しても、画像の外観は送信され、劣化（所望のイメージからの逸脱）は最小限になる。大きな係数は、画像の全体的な外観に最も影響を与える。それらの最上位ビット（ＭＳＢ）は最大の影響を持つ。それらを第一に送信することによって、画像の主な構造を最初に確立できる。より小さな係数は、画像の外観への影響がより小さい。それらも、高い位のビットから送信される。したがって、伝送がどのステージで終了しても、そのステージまで、位の高いビットから順に、最上位の係数と、それらの最上位の２進数字、そしてすべてのより小さな係数が送信されたことになる。全体的な結果として、画像の概要的な構造はすべて得られ、単に、伝送が継続していたならば提供されたであろう詳細の繊細さが欠けることになる。伝送がより長く継続すれば、それだけより多くの詳細が、係数に加えられ、先に述べた「ユニット式の階層的なサブバンド変換」の逆の結果から画像の詳細に加えられる。伝送が短ければ短いほど、それだけ画像の細部は粗くなるが、それでも画像は全体を表す。
【００２０】
同じ論文で、アミール・サイド氏及びウィリアム・Ａ・パールマン氏は、また「セット分割分類アルゴリズム」の組み込みを提案している。このアルゴリズムでは、係数が、１に設定されたｎ番目の、あるいはより高位のビットを持つ場合、その係数はｎレベルにおいて有意であると言える。係数が、１に設定されたｎ番目の、あるいはより高位のビットを全く持たない場合、その係数はｎレベルにおいて無意であると言える。
【００２１】
分類アルゴリズムは、ピクセルを分割サブセットに分ける。各サブセット内の最大係数のピクセルは、その係数が、レベルｎにおいて有意であるか、あるいは無意あるかを判断するために試験される。
【００２２】
サブセットに関連する最大係数が無意である場合、そのサブセット内のピクセルのすべてが、無意な係数を持つ。
【００２３】
サブセット内の最大係数が、レベルｎにおいて有意である場合、そのサブセットに関連する他の係数は、レベルｎにおいて、全く有意ではない、または、いくつか、あるいはすべてが有意である。サブセットは、送信エンコーダ及び受信デコーダとして一般に知られるルールに従って、より小さな第二のサブセットへ分割し、これらの第二のサブセットの各々に対して同じテストを適用する。この試験及び細分処理は、第二の、そしてその後のサブセットに対して、レベルｎにおいて有意な係数を持つすべての単一要素（単一係数）サブセットが識別されるまで続ける。この処理は、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）まで、ｎのすべての値に対して行う。このようにして、係数は、２のｎ乗以上の大きさを持つすべてのサブセットへ盲従的に分類される。この場合のｎは、係数の大きさを表すビット数である。係数は大きさによって分類する、と言うことができる。各分類カテゴリは、因数２による大きさの増加を表す。係数がカテゴリ最大よりも大きい場合、それはカテゴリ内に含められる。もし係数がカテゴリ最大よりも小さいなら、それはカテゴリから除かれる。
【００２４】
この方法は、また「空間的な方向ツリー」の使用を提案する。サブセット内のピクセルに関連する最大係数が、レベルｎにおいて有意であると分かったときにサブセットを分割する処理は、「親」係数及び「子」係数の概念に基づいている。分割アルゴリズム処理の各ステージにおいて、各既存係数（親）が、（最終ステージを除き）さらに四つの係数（子）を生む。初期分割は、各根ピクセルのすべての子と、それらの子（子孫全体）を用いて形成する。全子孫のセットが有意であることが分かった場合、そのセットを、直系の子サブセット、そして孫及び以降のサブセットへと分割する。孫及び以降のサブセットが有意であることが分かった場合、それを、元の根ピクセルの直系の子の子孫から各々がなる四つのサブセットに分割する。このようにして、サブセット生成は、新しいレベルの各々において同じ分割戦略を維持しながら、根から小枝の先端へとツリーを「上へ這い上がる」。このような階層を用いる理由は、ＳＰＩＨＴアルゴリズムが、係数が有意でなく、その子供たちも全く有意ではない場合、ツリー全体を省略できるという事実を利用することができる、ということである。
【００２５】
有意性試験の結果は、三つの順序付けリストに保存する。これらは、無意セットのリスト（ＬＩＳ）、無意ピクセルのリスト（ＬＩＰ）、そして有意ピクセルのリスト（ＬＳＰ）である。ＬＩＳ内では、サブセットは、根ピクセルのすべての子孫を含むかどうか、あるいは根ピクセルの孫または以降のみを含むかどうかに応じて区別される。分類パス中、以前のパスにおいて無意であったＬＩＰ内のピクセルを試験し、もし有意であることが分かったなら、それらをＬＳＰへ移動する。ＬＩＳ内のサブセットも同様に試験する。有意であることが見いだされたものは、ＬＩＳから取り除いて分割する。一つ以上の要素を持つ、分割から得た新しいサブセットは、ＬＩＳに戻す。分割から得た、単一要素のサブセットは、有意であるか否かに応じて、ＬＩＰへ、あるいはＬＳＰへ加える。ＬＳＰは、改善パスで対象とする角頂を含む。本発明は、修正して改善した形態で、そして三次元イメージという新しい領域で、この技術を利用することを目的としている。
【００２６】
本発明は、また、ウイッテン、ニール及びクリアリーが、１９８７年６月にＡＣＭ通信に「データ圧縮のための算術コーディング」（"Arithmetic Coding for Data Compression" by Witten, Neal & Clearly in the Communications of the ACM in June 1987）の表題の論文で開示したコード圧縮技術の、新規なアプリケーションを提供することを目的とする。この論文も、参照として組み込まれている。
【００２７】
第一の局面によれば、本発明は、面細分化によって三次元の面を再構築するのに使用する角頂変位情報の伝送装置を提供する。この装置は、面細分化処理中に発生する角頂の座標を定義する手段、そして、変位のより小さな要素の前に、変位のより有意な要素を送信する手段からなる。
【００２８】
本発明は、また、変位が２進数として定義され、より有意な要素が、より大きな有意性を持つ２進数字である装置を提供する。
【００２９】
本発明は、また、次のものを含む装置を提供する。大きさが減少する順序で、変位を選択する手段。有意性が減少する順序で、変位を表すのに用いる各位の２進数字を選択する手段。変位の大きさの順序で、選択した位の２進数字に等しい最上位の数字を持つ変位の各角頂の合計数及び座標を送る手段。そして変位の大きさが減少する順序で、先に選択した位の２進数字に等しい最上位の数字を持つことが先に分かっている各角頂に対する変位の表現内の選択位ビットを送る手段。
【００３０】
本発明は、また、データ・コンプレッサからなる装置を提供する。算術コーディング・データ・コンプレッサであることが好ましい。
【００３１】
もう一つの局面によれば、本発明は、どの角頂も変位が可能な面細分化手段を提供する。
【００３２】
さらに、もう一つの局面によれば、本発明は、二次元的な面ではなく、三次元オブジェクトに対するＳＰＨＩＴツリーのコード化の使用を提供する。
【００３３】
さらに、他の局面では、本発明は、本発明が提供するすべてのものと共に用いる受信及び再構築の装置である。
【００３４】
さらに、もう一つの局面では、本発明は、本発明が提供するすべての他のものと一貫した方法である。
【発明を実施するための最良の形態】
【００３５】
本発明を、例として、添付図面を参照にする次の記述から、さらに説明する。
【００３６】
図１Ａから１Ｊは、本発明の望ましい実施例に好適な、ループ・エッジ細分化ルーチン内の種々のステージを示す。通常、図１Ａに示す初期三角形ハル１０から始まり、三つの初期の角頂１２を持つハル１０のエッジ分割処理を順次ステージで示す。図１Ｃ、１Ｅ、１Ｇ及び１Ｉからなる左側コラムは、不可欠なエッジ分割及び移動処理を示し、図１Ｄ、１Ｆ、１Ｈ及び１Ｊからなる右側コラムは、左側コラムに示すものに同様な処理を表すが、変位に付加的なランダムなノイズ要素が加えられている。図１Ｂは、この例では岩の形状にある、最終的な標的オブジェクト１４の線画を示す。角頂１２は、それらの生成位置から変位させ、標的オブジェクト１４の最終的な形状を形成する。
【００３７】
さて、詳細に図１Ａ及び図１Ｂを参照する。図１Ｂに示す第一ステージの形状を生成するために、初期エッジ１６を、ループ・アルゴリズムに従って細分し、分割初期エッジ１６Ｄ上に角頂１８を形成する。図１Ｄに示す第一ステージの形状は、第一ステージ角頂１８の変位にランダムなノイズが加わって、ノイズのある第一ステージの角頂１８’が生じる点を除いて、同様に得られるものである。第一ステージの角頂１８、そしてノイズのある第一ステージの角頂１８’を結合することによって、第一ステージのエッジ２０’を生成する。
【００３８】
第一ステージの、一つの細分化処理を実行した後、さらに、第二ステージの細分化処理を適用する。この結果を図１Ｅ及び１Ｆに示す。第一ステージのエッジ１８の各々と分割初期エッジ１６Ｄの各々を再び二分割し、ループアルゴリズムに従って配置される第二ステージの角頂２２を形成する。これによって、図１Ｅに示す形状を得る。同様に、第一ステージのエッジ１８’の各々と分割初期エッジ１６Ｄ’の各々を再び二分割し、第二ステージの角頂２２’を形成する。これらは、ループアルゴリズムによって定義されて初期生成点から変位されるが、ランダムなノイズが加わるため、図１Ｆに示す形状になる。詳細を線と数字で正しく指すには、あまりにも細かすぎる。
【００３９】
本発明において特に興味深いのは、図１Ｆに示す第一ステージの移動角頂１８’Ａである。図１Ｅに示すそのカウンターパートが、図１Ｃに比べ、第二ステージでは変位しないのに、図１Ｄの場合は、第一ステージの移動角頂１８’Ａが、図１Ｄの第一ステージと、図 １Ｆの第二ステージとの間で移動している。
【００４０】
本発明では、本質的に、分割処理のどのステージにおいても、どの角頂も移動可能である。新しい角頂の各々は、分割処理の前ステージで生成された角頂、あるいは既存の角頂の位置に基づいて生成され、変位される。したがって、新たに生じた角頂は、変位する場合も、あるいは全く変位しない場合もある。
【００４１】
変位する場合、それが生成される分割ステージで変位するかもしれないし、あるいは後のステージで変位するかもしれない。変位のタイミングは、変位の大きさに完全に依存する。このことは、次の説明から明らかである。次の角頂の位置は、新たに生じる角頂の位置に依存し、その新生角頂が変位するまで変位が起こらない新生角頂によって決定される。ここに、本発明と、新しい変位可能な角頂を生成するために多分割を用いる他のすべての方法との本質的な違いがある。
【００４２】
細分化処理は、さらにステージを通過して、図１Ｇ及び１Ｉの形状と図１Ｈ及び１Ｊの形状を生成する。ワイヤー・メッシュ形状に許容可能な程度の詳細を得るまで、細分化処理は続く。これは、標的オブジェクト１４を用いるアプリケーションがすべて決定する。低解像度のアプリケーションは、ほとんどステージを持たないが、高解像度のアプリケーションは、多くのステージを持つ。
【００４３】
本発明は、好適実施例として、多角形の最も単純な形状である三角形を用いて多角形分割処理を説明している。本発明は、如何なる形状の多角形を用いても、古い角頂から新しい変位可能な角頂を生成する細分化処理に適用できることを理解すべきである。
【００４４】
さて、新しい発明を用いてどのように面の特徴が形成されるのかを、従来の技術による方法と比較して示す、図２Ａから図２Ｃに注目する。これは、三次元ハル２４から最終オブジェクト２６を生成する。最終オブジェクト２６は、第一のスパイク２８及び第二のスパイク３０を持つ。スタート角頂３２は、従来の技術に従って新しい角頂のみを移動させることによって次第に修正され、図２Ｄに示す第一のスパイク２６が不満足な（スパイクのない）形状に形成される。従来の技術は、その幾分不満足な形状に到達するために、１５の新生角頂の変位をとる。これと比較して、第二のスパイク３０は、（本発明によれば）移動させた（既存である必要はない）既存の角頂の単一の変位と、三次元ハル２４の後の二つの分割ステージによって形成される。これが、この例で、より満足な形状の第二のスパイク３０を生成するのに必要な唯一の変位である。
【００４５】
さて、図３に注目する。これは、本発明が伝送のための最終オブジェクトを用意する方法を概念的に示す概略図である。
【００４６】
矢印４０で示すように、中間及び最終オブジェクト３８上のすべての角頂３６を角頂マップ４２上へマッピングする。角頂マップ４２上の位置は、特定な最終角頂３６が生じた分割ステージで決定される。例えば、元のハル上の最終角頂３６は、０番目のステージ・エントリーの位置でエントリーを持つ。この例では、第一の分割で生じる各最終角頂３８は、第一ステージ・エントリーのための角頂マップ上にエントリーを持つ。各分割ステージにおいて、そのステージで既存の各最終角頂３６に対して、四つの新しい最終角頂３６が生成される。各ステージにおける新生角頂は、設計者の選択による望ましい、予め定めた順序で識別される。このようにして、その「先祖」角頂に依存して特定な最終角頂３６の識別「ツリー」が生成される。この場合、各「子供」は、分割の次のステージで「先祖」になる。ツリー上の位置が、角頂マップ４２上の最終角頂３６の位置を決定する。ハル１０、２４内の、元の角頂１２の各々は、それ自身のツリーを生成する。元の角頂１２は、また、角頂表内に順序付けられる。角頂表４２内の特定な位置に参照することによって、元のどの角頂１２から最終角頂３６を得るのか、そして分割処理のどのステージで最終角頂３６が生じるのかを知ることが可能である。
【００４７】
角頂表は、実体がなく、単に、各々が特定な最終角頂３６を識別するアドレスの整然としたセットである。Ｓｐｈｉｔツリーとは異なり、二次元イメージ内の個々のピクセルではなく、三次元最終オブジェクト３８内における最終角頂を識別する。角頂マップは、変位表４４のための、関連する最終角頂を識別するアドレスとして用いる。変位表４４は、特定な最終角頂３６に適当な位置に、その角頂３６に与えるべき変位を保存する。本発明は、これによって、三次元最終オブジェクト３８内の角頂に対する暗黙アドレスを生成することに成功する。
【００４８】
さて、本発明の好適実施例において、変位が何を意味するかを表す図４に注目する。選択した角頂３６を、変位前の静止位置４６から変位位置４８に変位させる。ここに示す例では、角頂３６への法線５０が、この特定な分割方法に用いるルールに従って描かれる。法線の方向は、周囲の多角形（この場合は三角形）が占める平面に依存する。変位は、法線５０に沿った変位と、二つの直交接線方向５２、５４に沿った変位とによって決定する。ここに示す例では、変位の各要素の大きさを表現するために複数の２進数字を用いる。最終オブジェクト３８の視覚品質は、接線方向５２、５４に沿った変位によりも、法線３８に沿った変位に非常に敏感であることが分かっている。したがって、この例では、法線変位の表現に１２ビットを、接線変位の各々には単に１０ビットを割り当てる。このことは、本発明に重要ではない。本発明は、どの変位に対しても、任意のビット数を用いることができる。本発明は、限定しないが、極座標（角と半径）等の、変位を表現する他のシステムと共に用いてもよい。
【００４９】
さて、図５に注目する。これは、サイド・パールマン方法の序説に表された単純な分類アルゴリズムを用いて、三次元最終オブジェクト３８の外観を準備して送信するときの、本発明の観念的なアクティビティのフローチャートを示す。実際のアプリケーションでは、限定しないが、サイド・パールマンのセット分割スキーム等の、より効率的な圧縮アルゴリズムを用いてもよい。
【００５０】
エントリー５６から第一の処理５８へ進み、そこでは、最終角頂３６の成長ツリー位置が決定される。第二の処理６０は、変位を、それらの対応する最終角頂３６と対にする。第三の処理６２は、成長ツリー位置を、角頂マップ４２内へ分類し、そして第四の処理６４は、変位表４４を構築する。これですべての準備が整い、最終オブジェクト３８の外観を送信できる。
【００５１】
第五の処理６６は、第一に、ハル１４、２４上の初期角頂１２の各々の絶対空間座標を送信する。これは、送信装置にたいして、正確に逆なやり方で機能する受信装置が、最終オブジェクト３８の外観を再構築するために必要である。
【００５２】
それから、第六の処理６８では、大きさが減少する順序で、変位が分類される。これは、設計者の選択によって決定される。例えば、法線変位の減少する大きさで分類してもよい。択一的に、法線及び接線要素のベクトル和によって生成するベクトルの絶対長で分類してもよい。極座標系では、変位を、半径の長さで分類することができる。本発明では、固執しないが、最終オブジェクト３８の最終表現に最大の影響を与える変位要素に対する大きさが減少する順序で分類することが好ましい。とにかく、２進数字配列内に、共に最上位ビットが１に設定された変位のすべてを減少する順序で、第二上位ビットが１に設定されているが最上位ビットが０のすべての変位を減少する順序で、そして同様に、一連の２進数を生成する。
【００５３】
第七の処理７０は、２進数字配列内の各変位に対応させて各最終角頂３６を合わせる。これは、変位表４４内の変位のアドレスを知ることによって行うことができる。これで変位データを送信し始めるすべての準備が整う。
【００５４】
第八の処理７２は、２進数字配列内にリストされている変位の最上位ビットを選択する。第九の処理７４は、選択位ビット（この場合、最上位ビット）に等しい最上位の数字（表現における最高値２進数字）を持つ変位の数を数える。それから、その数を送信する。これは、選択位ビットを最上位の数字として持つ最終角頂の数を表す。したがって、数「１」が既知であるから、そのカテゴリ内の各最終角頂３６に対して「１」を送信する必要はない。第十の処理は、最上位の数字が選択位ビットに等しい各最終角頂３６のアイデンティティを送信する。これは、単に、角頂マップ４２内の角頂の座標であって、変位のアドレスである。
【００５５】
それから、第十一の処理７８は、角頂送信リストを調べる。これは、先に最上位の数字が選択位ビットに等しいことが分かったすべての最終角頂３６の、２進数字配列と同じ順序のリストである。最上位ビットを選択した、この第一のパスでは、角頂送信リストは、もちろん空である。角頂送信リスト内にエントリーがある場合（次のパスから起こる）、角頂送信リストでリストされた角頂３６の変位のすべてに対する選択位ビットを、２進数字配列上に現われると同じ順序で送信する。
【００５６】
それから、第十二の処理８０は、最上位の数字が選択位ビットに等しいと分かったすべての角頂を、２進数字配列上に現れると同じ順序で、角頂送信リストに加える。そのようにして、第十三の処理８２で選択位ビットを次の下位ビットへ変えたとき、次のパスでは、同じようにして、２進数字配列の順序で次の下位ビットが送信される。
【００５７】
それから、第一のテスト８４は、ルーチンが最下位ビットに到達して処理を完了したかどうかをチェックする。完了している場合は、ルーチンは出口８６へ進む。完了していない場合は、制御は第九の処理７４に戻る。
【００５８】
ルーチンは、最終角頂３６のすべての変位における全２進数字が送信されるまで、それを繰り返す。もう一度言うが、最終角頂３６の合計数が、ハル１０、２４内の初期角頂１２の数と、初期ハル１０、２４からの分割のステージ数とから既知であるため、変位のない最終角頂に関する詳細を送信する必要は全くない。
【００５９】
図５のフローチャートに関する説明を分かり易くするために、同じアクティビティの概略図を図６Ａから６Ｄに示す。
【００６０】
（図５の第九の処理７４による）最上位の数字が選択位ビットに等しい変位の数を得て送信するために、ビット数レジスタ８８が設けられている。
【００６１】
２進数字配列９０は、大きさの減少する順序で、（図５の第六の処理６８による）変位を保持する。模範的なエントリーを示す。「１」は２進数１を示し、「０」は２進法０を示す。「Ｘ」は、個々の変位の大きさを表す２進数であって、どちらの２進数字をも示す。次の説明を考察すると、図示のように「０」及び「１」がブロックで配置されなくてはならないことが分かる。
【００６２】
角頂アドレス・レジスタ９２は、真下にある変位に対応する角頂３６のアドレスを保存する。これは、図５の第七の処理７０による。各角頂３６のアドレスは、単に成長ツリー上の出現点であって、図３の角頂マップ４２に例示されている。
【００６３】
角頂送信リスト９４は、先に処理された各角頂３６のアイデンティティを保存する。これは、図５の第十一７８及び第十二８０の処理による。その意味と用途は、次の説明から明確になる。
【００６４】
明確に、そして簡潔にするため、この例に示す２進数字配列９０は、単に、最上位ビット（ＭＳＢ）、ビット５から始まり、最下位ビット（ＬＳＢ）、ビット０へ下降する六つの位ビットだけを持つ。しかしながら、現実は、６よりも遙かに多くの位ビットがあり、ここに示す１６よりもずっと多くのエントリーがあることを理解すべきである。
【００６５】
さて、図６Ｂに注目する。これは、図５の第八の処理７２により最上位ビット（ＭＳＢ、ビット５）が選択されるときの送信シーケンスを示す。
【００６６】
データ・スタート９６から、ビット数レジスタ８８のコンテンツが送信される。２進数字配列の試験は、ビット５行内に、二つの１があることを示す。したがって、ビット数レジスタ内の数は、２進法の２（０００００１０）である。
【００６７】
ビット数レジスタ８８のコンテンツを送信したので、送信シーケンスは、角頂アドレス・レジスタ９２へ進む。ここでは、２進数字配列のビット５行内に１を持つ変位の、二つの角頂３６のアドレスが、それらの変位が２進数字配列９０内に現われる順番で送信される。
【００６８】
このステージで、送信シーケンスは、エントリーがあるかどうか、角頂送信リスト９４を調べる。これは、図５の第十一の処理７８に一致する。現在、ＭＳＢ（ビット５）が選択されるため、角頂送信リスト９４にはエントリーが全くなく、空である。これ以上のデータは全く送信せず、送信リストはデータ終了９８へ進む。
【００６９】
さて、送信シーケンスの第二のステージを示す図６Ｃに注目する。
【００７０】
図５の第十二の処理８０に従ってＭＳＢ（ビット５）送信シーケンスが実行されたので、ビット５行内に１を持つ二つの角頂３６が角頂送信リストに加えられている。また、図５の第十三の処理８２に従って、ビット４（次の下位ビット）が選択された。ビット４行内には二つの１があるため、ビット数レジスタ８８のコンテンツは、もう一度、２進数の２（０００００１０）である。送信シーケンスは、第一に、ビット数レジスタ８８のコンテンツを送信し、そしてそれらの変位が２進数字配列内に現われる順番で、ビット４行が１ですべての高位行が０である（すなわち、それらの最上位の数字がビット４行にある）変位の角頂３６のアイデンティティを送信する。このステージで、送信シーケンスは角頂送信リスト９４を調べる。そこには、ビット５行内に最上位の数字を持つ変位の角頂の各々に対する二つのエントリーがある。したがって、送信シーケンスは、角頂送信リスト９４内にリストされた二つの角頂に対して、２進数字配列９２内に現われる順序で、ビット４行データ・ビット（Ｘ）を送信する。これでビット４の送信シーケンスが終了９８する。このステージで、送信シーケンスは、既に、ビット５行内のすべての最上位の数字１、ビット４行内のすべての最上位の１、そして送信した最上位の数字１に対するデータ・ビット（Ｘ）を送信している。
【００７１】
さて、ビット３が選択位の数字である場合の送信シーケンスを示す図６Ｄに注目する。
【００７２】
図５の第十二の処理８０に従って、変位がビット４行内に１を持つ二つの角頂が角頂送信リスト９４に加えられている。したがって、角頂送信リストは、ビット５行及びビット４行内に１を示す変位を持つ角頂３６を含んでいる。角頂は、変位が２進数字配列９０内に現れる順序でリストされている。また、図５の第十三の処理８２に従って、次の下位ビット、ビット３が選択されている。
【００７３】
図５の第九の処理７４に従って、ビット３行内には、四つの１があることが分かる。したがって、ビット数レジスタ８８は２進数の４（００００１００）を含む。送信シーケンスは、ビット数レジスタ８８のコンテンツを、それから、２進数字配列９０内に変位が現われる順序で、ビット３行内に１を持つ四つの角頂３６のアイデンティティを送信する。
【００７４】
次に送信シーケンスは、図５の第十一の処理７８に従って、角頂送信リスト９４を調べる。その中の四つのエントリーは、変位がビット５行あるいはビット４行に１を示した角頂３６に対するものである。したがって送信シーケンスは、角頂送信リスト９４内の各角頂３６に対して、２進数字配列９０内に現われる順序で、ビット３行データ・ビット（Ｘ）を送信する。それから送信シーケンスは、ビット３行送信ステージを終了９８させる。このステージまでに、送信シーケンスは、暗黙の秩序化によって正確に再構築されるように、２進数字配列内に現われる順番で、ビット４行あるいはビット３行内に現われるデータ・ビット（Ｘ）と共に、ビット５、ビット４及びビット３行上のすべての最上位の数字１を送信している。
【００７５】
さて、選択位ビットとしてビット２の送信シーケンスを示す図６Ｅに注目する。
【００７６】
図５の第十二の処理８０に従って、２進数字配列９０内における変位のビット３行内に１を示す角頂３６が、角頂送信レジスタ９４に加えられている。図５の第十三の処理８２に従って、次の下位ビット、ビット２が選択位ビットになっている。
【００７７】
ビット２行内には七つの１があることが分かる。ビット数レジスタ内の数は、それ相応に、２進数の７（００００１１１）である。図５の第九の処理７４に従って、送信シーケンスはこの数を送信する。送信シーケンスは、次に、図５の第十の処理７６に示すように、変位が２進数字配列内に現われる順序で、角頂アドレス・レジスタ９２内に保存された角頂３６のアイデンティティを送信する。送信シーケンスは、次に、図５の第十一の処理７８に従って、角頂送信リスト９４を調べる。ビット５、ビット４あるいはビット３行内に１を示す変位を持つ各角頂に対して一つずつ、八つのエントリーがある。送信シーケンスは、２進数字配列９０内に現れる順序で、角頂送信リスト９４内の角頂３６に対するビット２行データ・ビット（Ｘ）を送信する。それから、ビット２行の送信シーケンスは終了９８する。送信シーケンスは、これまでに、ビット５、ビット４、ビット３及びビット２行内のすべての最上位の数字１を、ビット４、ビット３及びビット２行内のすべてのデータ・ビット（Ｘ）と共に送信している。
【００７８】
さて、図６Ｆに注目する。これは、どのように送信シーケンスがビット１行を進行するのかを表し、単に例として、最上位の数字１がない場合を示している。
【００７９】
このため、第九の処理７４に従って、ビット数レジスタ８８は、２進法の０、すなわち０００００００を送信する。ビット１行内に最上位の数字を持つ新しい角頂３６がないので、角頂アドレス・レジスタへのアクセスは全く起こらない。その代わりに、送信シーケンスは、２進数字配列９０へ直行し、そして角頂送信リスト内の角頂３６に対する、ビット１行内のすべてのデータ・ビット（Ｘ）を送信する。これで送信シーケンスのビット一部分が終了する。ビット１に対しては、ビット０が選択されるとき、角頂送信リスト内に形成されるエントリーはない。
【００８０】
処理は、すべての他のビットの場合と同様、ビット０に対しても実行される。
【００８１】
さて、本発明を用いることができる環境の概略図である図７に注目する。
【００８２】
送信装置１００は、三次元最終オブジェクト１４、３８のワイヤ・メッシュ表現を生成するメッシュ・ジェネレータ１０２からなる。ワイヤ・メッシュ生成は、提供する情報内に、最終オブジェクト内のすべての角頂３６、すべてのハル初期角頂１２及びそれらの絶対空間位置、そして最終オブジェクト１４、３８を再現するための、分割ルーチンから生じるすべての角頂のすべての変位を含む。メッシュ・ジェネレータは、その情報を、図３、４、５及び６に関連して上記に説明したように作用する送信エンコーダ１０４に送る。
【００８３】
送信エンコーダは、データの流れをデータ・コンプレッサ１０６に送る。データ・コンプレッサは、先に「データ圧縮のための算術コーディング」（"Arithmetic Coding for Data Compression" by Whitten, Neal & Cleary, Communications of the ACM, June 1987, volume 30, Number 6, pages 520 to 540）で言及して説明した算術コーディング・データ・コンプレッサであることが好ましい。この技術は、変化するコンテンツに対して最少のコーディングを維持するために、情報量を追跡し、絶えず変化する最短長コーディングを生成する。受信器は、同じ方法を用いて、変化する伝送コードを独立して追跡し、送信に追随することができる。他の形態のデータ圧縮を用いることもできる。
【００８４】
最後に、データ・コンプレッサの出力は、伝送装置１０８に送る。送信装置１００がインターネットの一部である場合は、伝送装置１０８はインターネットに接続される。送信装置が移動電話である場合、伝送装置１０８は移動電話回線網に接続される。主に、三次元オブジェクトのワイヤ・メッシュ表現を、もう一つの装置に送信する必要がある、他の領域で用いることも可能である。
【００８５】
受信装置１１０は、伝送装置１０８から信号を受信して復調する受信器１１２からなる。受信器１１２からの信号は、送信エンコーダ１０４からの送信信号を再生するデータ・デコンプレッサー１１４へ渡され、そして、送信エンコーダからの信号を用いてメッシュを再生するメッシュ・リクリエータ１１６へ送られる。再生されたメッシュは、送信装置１００からの命令に応じて、再生メッシュを修正するイメージ・コントローラ１１８に送られる。コントローラは、（ハルを振る、そして移動することによって、揺らす、あるいは大きさを調整して）例えば、コンピュータのモニター１２０上に、または移動電話あるいはパーソナル・ディジタル・アシスタント（ＰＤＡ）のスクリーン１２２上に三次元オブジェクトを表示する。本発明の用途のもう一つの領域は、ＲＯＭ及びＰＲＯＭ、磁性テープ、ハード及びフレキシブル磁性ディスク、ＣＤ 、ＤＶＤ 等のデジタル記憶媒体からの、イメージのコンパクトな保存及び回収である。
【００８６】
メッシュ・ジェネレータ１０２は、それにプログラムされている特定な分割方法を用いる。メッシュ・リクリエータ１１６は、同じ分割方法で処理するプログラムを用いる。伝送の始めに、送信装置１００は、必要なプログラムが利用可能かどうかを調べるために受信装置１１０と交信してもよい。利用できない場合、送信装置１００は、メッシュ・リクリエータ１１６内での使用のために、受信装置１１０に必要なプログラムを送信することもできる。択一的に、メッシュ・ジェネレータは、自由に選択可能な、複数の異なる分割方法を持つことができる。送信装置１００は、受信装置１１０内で利用可能なプログラムをチェックして、適当な分割方法を用いることができる。また、択一的に、受信装置１１０は、送信装置にどの方法を用いるかを通知して、送信装置はそれを用いることができる。
【００８７】
メッシュ再生器１１６は、たとえ変位の詳細の一部にミスがあっても、メッシュ再生で続ける。伝送に中断あるいは干渉があったのかもしれない。択一的に、特定なアプリケーションでは、最終オブジェクト１４、２８の面定義において、特定な程度を越える必要は全くないかもしれない。変位データは、第一に最大変位が送信され、より小さな変位へと送信が進むため、伝送の中断（あるいは故意の伝送の中断）の影響は、単により詳細なデータを失うことである。その結果は、いくつかの角頂３６が、もし伝送が完全であった場合に受け取ったであろう小さな変位を、実際は、変位を全く受信しないし、他の角頂３６は、それらの変位を定義する、すべての２進数字を受信することがない。しかし、第一で、最上位ビットが定義する変位を受信するので、単に細かな調整が失われるだけである。この影響は、レンズの焦点を合わせることに例えることができる。伝送がより長く継続すると、それだけイメージの解像度も良い。しかし、焦点が完全に合っていなくとも、イメージは、いくらかの解像度が欠けるが、それでも全体を表すものである。
【図面の簡単な説明】
【００８８】
【図１】ＡからＪは、本発明の好適実施例で用いるメッシュ分割処理の図示である。
【図２】ＡからＤは、従来の技術である変位方法を、本発明が提供する方法に比較する。
【図３】伝送、送信あるいは保存のためのメッシュ・データのコード化の第一ステージを表す。
【図４】角頂変位の意味を表す。
【図５】本発明の完全なメッシュ・コード化方法を示すフローチャートである。
【図６Ａ】図５のコード化方法を、概略的に、さらに明確に示す。
【図６Ｂ】図５のコード化方法を、概略的に、さらに明確に示す。
【図６Ｃ】図５のコード化方法を、概略的に、さらに明確に示す。
【図６Ｄ】図５のコード化方法を、概略的に、さらに明確に示す。
【図６Ｅ】図５のコード化方法を、概略的に、さらに明確に示す。
【図６Ｆ】図５のコード化方法を、概略的に、さらに明確に示す。
【図７】データ圧縮及び復元を含む本発明を用いることが可能な、一つの環境を表す概略的なブロック図である。
【図１】
2004535028.tif 000003
【図２】
2004535028.tif 000004
【図３】
2004535028.tif 000005
【図４】
2004535028.tif 000006
【図５】
2004535028.tif 000007
【図６Ａ】
2004535028.tif 000008
【図６Ｂ】
2004535028.tif 000009
【図６Ｃ】
2004535028.tif 000010
【図６Ｄ】
2004535028.tif 000011
【図６Ｅ】
2004535028.tif 000012
【図６Ｆ】
2004535028.tif 000013
【図７】
2004535028.tif 000014
【国際公開パンフレット】
2004535028.tif 000015
2004535028.tif 000016
2004535028.tif 000017
2004535028.tif 000018
2004535028.tif 000019
2004535028.tif 000020
2004535028.tif 000021
2004535028.tif 000022
2004535028.tif 000023
2004535028.tif 000024
2004535028.tif 000025
2004535028.tif 000026
2004535028.tif 000027
2004535028.tif 000028
2004535028.tif 000029
2004535028.tif 000030
2004535028.tif 000031
2004535028.tif 000032
2004535028.tif 000033
2004535028.tif 000034
2004535028.tif 000035
2004535028.tif 000036
2004535028.tif 000037
2004535028.tif 000038
2004535028.tif 000039
2004535028.tif 000040
2004535028.tif 000041
2004535028.tif 000042
2004535028.tif 000043
2004535028.tif 000044
2004535028.tif 000045
2004535028.tif 000046
2004535028.tif 000047
2004535028.tif 000048
2004535028.tif 000049
2004535028.tif 000050
2004535028.tif 000051
【国際調査報告】
2004535028.tif 000052
2004535028.tif 000053
2004535028.tif 000054