(57)【要約】【課題】３次元形状モデルを、簡略化された形状モデルが、詳細な元の形状モデルと近似し、簡略化及びその復元処理が、どちらも高速で、可逆的に実行可能で、復元形状モデルが元の形状モデルと完全に一致すると共に、簡略化処理／復元処理の演算過程において、データ量が常に一定な３次元形状モデルの多重解像度表現処理方法を提供する。【解決手段】３次元形状モデルの多重解像度表現方法で、前記３次元形状モデルを四辺形メッシュで分割する工程と、当該四辺形メッシュで分割した形状モデルを多重解像度表現する工程とを含み、前記多重解像度表現工程が、取り除いた頂点が、簡略化した頂点から復元可能であるように、予測演算子としてサブディビジョンを採用したリフティングスキームにより、簡略化工程及び復元工程を行う。【選択図】  図１３
2004164221.tif 000002
【特許請求の範囲】
【請求項１】
３次元形状モデルの多重解像度表現方法であって、
前記３次元形状モデルを四辺形メッシュで分割する工程と、当該四辺形メッシュで分割した形状モデルを多重解像度表現する工程とを含み、
前記多重解像度表現工程が、取り除いた頂点が、簡略化した頂点から復元可能であるように、予測演算子としてサブディビジョンを採用したリフティングスキームにより、簡略化工程及び復元工程を行うようにしたことを特徴とする３次元形状モデルの多重解像度表現方法。
【請求項２】
前記簡略化工程が、分割工程、予測工程、及び、更新工程を含み、前記復元工程が、逆更新工程、逆予測工程、及び、統合工程を含む請求項１に記載の３次元形状モデルの多重解像度表現方法。
【請求項３】
３次元形状モデルの多重解像度表現装置であって、
前記３次元形状モデルを四辺形メッシュで分割する手段と、当該四辺形メッシュで分割した形状モデルを、順変換手段及び逆変換手段により多重解像度表現する手段とを含み、更に、
前記順変換手段及び逆変換手段が、予測手段、更新手段、及び、分割手段又は統合手段を含み、
前記予測手段では、取り除いた頂点が、簡略化した頂点から復元可能であるように、予測演算子としてサブディビジョンを採用したリフティングスキームにより、順変換を演算し、前記３次元形状モデル・データの簡略化処理を行うようにしたことを特徴とする３次元形状モデルの多重解像度表現装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元形状モデルの多重解像度表現方法及び装置に関し、より詳しくは、３次元形状モデルの詳細かつ大量のメッシュ・データを、所定の解像度で高速に簡略化し、又、復元するのに最適な３次元形状モデルの多重解像度表現方法及び装置に関する。
【０００２】
【従来の技術】
近年、数値データに基づく数値解析計算により様々な物理現象や物性を解明し、これにより製品の性能や信頼性を効率良く高かめる支援技術としてＣＡＥシステムが知られている。かかるＣＡＥシステムを利用したＦＥＭ解析、インターネットでの３次元モデルによるプレゼンテーション、３次元ゲーム／アニメーション・ソフト、３次元地理情報／医療情報処理等、種々の３次元形状モデルをＣＲＴ等の表示手段に３次元表現する応用が普及しつつあるが、３次元形状モデルデータや、或いは、Ｘ線ＣＴ、ＭＲＩ等の非接触３次元計測オリジナル・点群データから、効率よく、３次元形状モデル・データを作成すると共に、所望の解像度で元の３次元形状モデルに忠実に再表示する要求が高まっている。かかる３次元形状モデルの表現方法として、
ａ１）  曲線・曲面を多項式によって、パラメトリックに表現する方法として、Ｂ−スプライン（Ｓｐｌｉｎｅ）曲線やＮＵＲＢＳ（Ｎｏｎ  Ｕｎｉｆｏｒｍ  Ｒａｔｉｏｎａｌ  Ｂ−Ｓｐｌｉｎｅ）曲線に基づいて、３次元形状モデルを表現する手法が知られている。又、高速演算が可能で、任意の位相構造に対応できる３次元形状モデルの生成方法として、ａ２）  所定の空間位置に配置した複数の制御点からなる初期ポリゴンを、予め設定した規則（スキーム）によって、繰り返し精細化した極限として、滑らかな曲線・曲面を生成するサブディビジョン（Ｓｕｂｄｉｖｉｓｉｏｎ）法も、種々の三角形メッシュ、四角形メッシュに対して提案されている。かかるサブディビジョン方法には、近似手法（スキーム）と、補間手法（スキーム）とがあり、それぞれ、三角形メッシュに対するサブディビジョン・近似手法では、Ｌｏｏｐの方法があり（例えば、非特許文献１参照）、又、三角形メッシュに対するサブディビジョン・補間手法では、Ｍｏｄｉｆｉｅｄ  Ｂｕｔｔｅｒｆｌｙ演算が知られている（例えば、非特許文献２参照）。更に、四角形メッシュに対するサブディビジョン・近似手法では、Ｃｕｔｍｕｌｌ−Ｃｌａｒｋの方法があり（例えば、非特許文献３参照）、四角形メッシュに対するサブディビジョン・補間手法では、Ｋｏｂｂｅｌｔのスキームがある（例えば、非特許文献４参照）。
尚、サブディビジョン近似手法では、Ｂ−スプラインと同様に、制御ポリゴンにより生成される曲面は、定義用の制御点を通過しない。
ａ３）  所望の解像度で３次元形状モデルを多段階に多重解像度表示する方法に関しては、三角形メッシュから構成された３次元形状モデルに対して多重解像度表現する方法として、Ｈｏｐｐｅにより提案されたプログレシブ・メッシュ（Ｐｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈ）法がある（例えば、特許文献１参照）。この手法は、三角形メッシュで表現された形状モデルの各エッジを、１つづつ消去して簡略化を行う連続的なメッシュ簡略化手法であり、エッジ消去のための変換は可逆性を有し、簡略化されたメッシュからオリジナルのメッシュを完全に再構成することも可能である。更に、特許文献２に、「ウェーブレットに基づくデータ圧縮」技術が、記載されている。この明細書に記載されたウェーブレット手法は、データ圧縮により、最小のビット数で、できるだけ正確に情報を表わすことにより、コンピュータシステムでの利用を目的として格納／転送するデータ量を最小化する有用な技術であることが指摘され、圧縮対象データは、オーディオ／ビデオ情報等の種々の情報があるが、データ圧縮用手段として、冗長な情報を取り除く方法を採用した場合、残った情報が、正確に圧縮されたデータを示すものが好ましいことも指摘されている。従来のデータ圧縮方法は、単純な形状において定義されたデータに関して行われ、かかる従来の圧縮方法で採用された典型的な形状は、実直線（例えば、オーディオ）、矩形（例えば、画像）、３次元ラスター（例えば、ビデオ）等であるが、これら従来のデータ圧縮技術は、球、一般的な多角形モデル等の、より高次元の形状或いは複雑な形状において定義されたデータの圧縮には適しておらず、数多くの複雑な形状に関して、適切なデータ圧縮技術を開発する必要が指摘されている。
一例として、地球に関するデータの圧縮が挙げられ、膨大な数の地球上の高度データに関するデータ集合が存在する。典型的な例として、ＥＴＯＰＯ５データ集合があり、このデータ集合は、地球全体にわたる地形データを示し、その解像度は、赤道において５アーク分の解像度で、海面からの地球上の高度（深度）をメートルで表わしている。強力なワークステーションを用いても、このようなデータ集合の処理、格納、および伝送にはかなりの費用がかかる。同様なデータ集合の他の例として、人工衛星から見た地球表面のデータや惑星データがあり、更に、情報のモデル化に有用な複雑な形状の他の例には、人間の頭部がある。複雑なデータ集合を双方向多重解像度で観察する技術も、他の適用例である。複雑な多様体に関する双方向ビューアーを構築する際には、ユーザーが必要とする情報を単に記憶し、表示する構成が望ましい。
【０００３】
単純な形状の圧縮に関しては、様々な手法が従来技術として利用可能であるのに対して、複雑な形状、及び／又は、より高次元の形状において定義されたデータの圧縮に関しては、従来は三角形メッシュに基づいた手法が、主として開発されてきた。
特許文献２では、ウェーブレットの１つの定義として「ウェーブレットは、データを迅速に分解することができる構成ブロックである」というものがある。則ち、データ集合のウェーブレット表現は、速やかに見いだすことができる。より正確に言えば、データの大きさに比例した時間で、データの元の表現とウェーブレット表現とを切り替えることができる。ウェーブレットの迅速な分解能力が、圧縮処理の一つの鍵となり、一般に、ウェーブレットは、色々なレベルの詳細さで、所定の関数を表現する基底関数である。空間および周波数における局在的な支援により、ウェーブレットは、関数の疎近似に適している。空間における局在性は、ウェーブレットのまとまりに起因するものであり、周波数の局在性は、平滑さと消滅モーメントに起因する。古典的なウェーブレット設定、すなわち、実直線におけるウェーブレット設定においては、ウェーブレットは、固定された１つの特定の関数の２値的な平行移動および拡張と定義される。
ウェーブレットは、通常、スケーリング関数を用いて形成される。スケーリング関数とウェーブレットは、どちらも詳細化関係（すなわち、二つのスケール関係：ツースケール関係）を満たすものである。則ち、所定のレベルの解像度（ｊ）におけるスケーリング関数或いはウェーブレットを、同一の形状で一段階詳細化したレベル（レベルｊ＋１）のスケーリング基底関数の線形結合で表すことができる。
この十年で、ウェーブレットは、演算とデータ要約を行うための非常に強力で融通の利く手段となってきた。ウェーブレットは、平滑さを理論的に特徴づけ、関数及び演算子の構造を考察し、更に、演算アルゴリズムの高速化につながる実用的な数値手段を提供する。コンピュータグラフィックスにウェーブレットを利用した例として、表面及び容積照明演算、曲線及び表面モデル化及びアニメーションが挙げられ、コンピュータグラフィックスの処理速度を上げるために演算需要が増大し、ウェーブレットの重要性が増している。このような分野でウェーブレット技術は大きな貢献をしているが、その一方で、新しい問題も生じている。一つの問題は、複雑な多様体上で定義されるデータの変換である。
一般に、Ｍ次元の多様体は、空間Ｎの各点の近傍がＲのＭ乗における開球と位相同形であるような空間Ｎである。例えば、ユークリッドの三次元（３−Ｄ）空間に存在する二次元（２−Ｄ）的な球表面においては、球表面上の各微小部分は、ユークリッドの２−Ｄ空間（則ち、平面）の小部分と同一であるように見える。この事実が、地球は平面である、という考え方につながった。
古典的なウェーブレット構造は、固定された１つの関数「マザーウェーブレット」による２値的な平行移動及び拡張として、ウェーブレット関数を定義する。これに関しては、例えば、非特許文献５、非特許文献６、並びに、非特許文献７を参照されたい。平面ユークリッド空間においてのみ、平行移動と拡張が意味を持つため、古典的な、則ち、第一世代のウェーブレットを、複雑な多様体上で定義されたデータの変換に用いることができない。このため、第二世代のウェーブレットへの一般化を考える必要がある。
第二世代のウェーブレットとは、必ずしも一つの関数の平行移動や拡張ではないが、第一世代のウェーブレットの強力な特性、則ち、基底関数特性、分解特性、及び、高速アルゴリズムを有しているウェーブレットのことである。一般に、広く用いられている古典的なウェーブレットの大部分は、第二世代ウェーブレットを用いて表すことができるため、全ての古典的なウェーブレットを表すことができると考えられる。言いかえると、第二世代ウェーブレットは、大部分の古典的なウェーブレットの上位集合である。従って、本明細書で用いられる「第二世代ウェーブレット」という表現は、特定の第二世代ウェーブレットのみを意味するものではなく、第二世代ウェーブレットを用いて表すことができる古典的なウェーブレットも意味する。
第二世代のウェーブレットの背景となる基本的な思想は、実直線よりも一般的な設定に適応できる所望の特性（局在性、高速変換）を持つウェーブレット、例えば、多様体上のウェーブレット、を構築することである。表面上におけるウェーブレットを考えるためには、表面上における測度に適応するウェーブレットを構成する必要がある。実直線（及び古典的な構成）の場合には、測度は、一般的な平行移動不変集合であるルベーグ測度ｄｘである。球に関して、一般的な面積測度を、例えば、ｄｗで表すことができる。所望の特性を有するウェーブレットを得るために平行移動と拡張が必要不可欠ではないということを認識することによって、適応構成が実現される。より細かく部分分割されたレベルにおける基底関数の有限線形結合として、ある基底関数を表現することができるという概念が維持され、これが、高速変換の鍵となる。
古典的なウェーブレットとの主な相違は、第二世代のウェーブレットのフィルター係数は、ずっと同じではなく、表面及びその測度の変動（平行移動ではない不変集合）に合わせて、局所的に変動する、ということである。
古典的なウェーブレットとそれに対応するフィルターは、フーリエ変換を用いて作成されていた。これは、平行移動と拡張が、フーリエ変換後、代数的な演算になるからである。第二世代のウェーブレットの設定においては、平行移動と拡張は、もはや用いられず、フーリエ変換も作成手段として用いられない。代わりの作成手段として、リフティング・スキームが用いられる。
ウェーブレット構造の新しい概念、リフティング・スキームは最近導入された考え方である。この概念に関しては、非特許文献８に記載されている。
このリフティング・スキームは、フーリエ変換を使う必要がないという意味において、古典的な構成と異なっている。このため、リフティング・スキームは、第二世代ウェーブレットの作成の優れた手段となる。
例えば、四角形の部分分割を利用して、三次元多様体をモデル化する部分分割の様子を図１に示す。図示するように、四角形Ｂ１０５を含む３次元表面は、四角形に部分分割されている。四角形Ｂ１０５は、３次元モデルの表面を形成する多くの四角形の一つである。四角形１０５は、四角形１０５、１０７、１０９、１１１から成る大きな四角形の一部を構成している。又、四角形１０５は、同様のスキームにより更に部分分割される。
ａ４）  ３次元モデル形状に合わせて、四辺形メッシュの対辺の分割格子点数が一致するメッシュ生成方法で、短時間に３次元有限要素メッシュ生成が可能な方法が、例えば、特許文献３に記載されている。
【特許文献１】
米国特許第５９２９８６０号明細書
【特許文献２】
特表２００１−５００６７６号公報
【特許文献３】
特開平５−１７４１１１号公報
【非特許文献１】
Ｌｏｏｐ  Ｃ．，  Ｓｍｏｏｔｈ  ｓｕｂｄｉｖｉｓｉｏｎ  ｓｕｒｆａｃｅｓ  ｂａｓｅｄ  ｏｎ  ｔｒｉａｎｇｌｅｓ．  ＭＳ  ｔｈｅｓｉｓ，  Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｍａｔｈｅｍａｔｉｃｓ，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｕｔａｈ，１９８７
【非特許文献２】
Ｍａｎｄａｌ  Ｃ．  ｅｔ  ａｌ，  Ａ  ｎｏｖｅｌ  ＦＥＭ−ｂａｓｅｄ  ｄｙｎａｍｉｃ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｓｕｂｄｉｖｉｓｉｏｎ  ｓｕｒｆａｃｅｓ，  Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ  Ｖｏｌ．３２，２０００，  ｐｐ．４７９−４９７
【非特許文献３】
Ｃａｔｍｕｌｌ  Ｅ．  ｅｔ  ａｌ，  Ｒｅｃｕｒｓｉｖｅｌｙ  ｇｅｎｅｒａｔｅｄ  Ｂ−ｓｐｌｉｎｅ  ｓｕｒｆａｃｅｓ  ｏｎ  ａｒｂｉｔｒａｒｙ  ｔｏｐｏｌｏｇｉｃａｌ  ｍｅｓｈｅｓ，  Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ，１９７８，１０（６）：３５０−５
【非特許文献４】
Ｋｏｂｂｅｌｔ  Ｌ．，  Ｉｎｔｅｒｐｏｌａｔｏｒｙ  Ｓｕｂｄｉｖｉｓｉｏｎ  ｏｎ  Ｏｐｅｎ  Ｑｕａｄｒｉｌａｔｅｒａｌ  Ｎｅｔｓｗｉｔｈ  Ａｒｂｉｔｒａｒｙ  Ｔｏｐｏｌｏｇｙ，  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  Ｆｏｒｕｍ  １５，  Ｅｕｒｏｇｒａｐｈｉｃｓ  ’９６，１９９６，ｐｐ．４０９−４２０
【非特許文献５】
Ｃ．Ｋ．Ｃｈｕｉ”Ａｎ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｗａｖｅｌｅｔｓ”（ウェーブレットの基礎）（Ａｃａｄｅｍｉｃ  Ｐｒｅｓｓ，１９９２）
【非特許文献６】
Ａ．Ｃｏｈｅｎ，Ｉ．Ｄａｕｂｅｃｈｉｅｓ及びＪ．Ｆｅａｕｖｅａｕ”Ｂｉ−ｏｒｔｈｏｇｏｎａｌ  Ｂａｓｅｓ  ｏｆ  Ｃｏｍｐａｃｔｌｙ  Ｓｕｐｐｏｒｔｅｄ  Ｗａｖｅｌｅｔｓ”（コンパクトに支援されたウェーブレットの２直交基底）（Ｃｏｍｍ．Ｐｕｒｅ  Ａｐｐｌ．Ｍａｔｈ．，４５：４８５−５６０，１９９２）
【非特許文献７】
Ｉ．Ｄａｕｂｅｃｈｉｅｓｉ”Ｏｒｔｈｏｎｏｒｍａｌ  ｂａｓｅｓ  ｏｆ  ｃｏｍｐａｃｔｌｙ  ｓｕｐｐｏｒｔｅｄ  ｗａｖｅｌｅｔｓ”（コンパクトに支援されたウェーブレットの正規直交基底）（Ｃｏｍｍ．Ｐｕｒｅ  Ａｐｐｌ．Ｍａｔｈ．，４１：９０９−９９６，１９９８）
【非特許文献８】
Ｗ．Ｓｗｅｌｄｅｎｓ”Ｔｈｅ  Ｌｉｆｔｉｎｇ  Ｓｃｈｅｍｅ：Ａ  Ｃｕｓｔｏｍ−ｄｅｓｉｇｎ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  Ｂｉｏｒｔｈｏｇｏｎａｌ  Ｗａｖｅｌｅｔｓ”（リフティング・スキーム：２直交ウェーブレットの注文設計構造）（Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  １９９４：７，Ｉｎｄｕｓｔｒｉａｌ  Ｍａｔｈｅｍａｔｉｃｓ  Ｉｎｉｔｉａｔｉｖｅ，Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｍａｔｈｅｍａｔｉｃｓ，Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｏｕｔｈ  Ｃａｒｏｌｉｎａ，１９９４）
【非特許文献９】
Ｊ．Ｍ．Ｓｈａｐｉｒｏ（”Ｅｍｂｅｄｄｅｄ  Ｉｍａｇｅ  Ｃｏｄｉｎｇ  Ｕｓｉｎｇ  Ｚｅｒｏｔｒｅｅｓ  ｏｆ  Ｗａｖｅｌｅｔ  Ｃｏｅｆｆｉｃｉｅｎｔｓ”（ウェーブレット係数のゼロツリーを利用した組込み型画像符号化方法），４１（１２）：３４４５３４６２，ＩＥＥＥ  Ｔｒａｎｓ．Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓ，１９９３）
【非特許文献１０】
”Ａ  Ｎｅｗ  Ｆａｓｔ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｉｍａｇｅ  Ｃｏｄｅｃ  Ｂａｓｅｄ  ｏｎ  Ｓｅｔ  Ｐａｒｔｉｔｉｏｎｉｎｇ  ｉｎ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｔｒｅｅｓ”（階層ツリーにおける集合分割に基づく新しい高速高性能な画像符号器）
【非特許文献１１】
”Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｕｓｉｎｇ  ｔｈｅ  Ｓｐａｔｉａｌ−Ｏｒｉｅｎｔａｔｉｏｎ  Ｔｒｅｅ”（空間配向ツリーを利用した画像圧縮）Ａ．Ｓａｉｄ及びＷ．Ｐｅａｒｌｍａｎ  ＩＥＥＥレポート０−７８０３−１２５４−６／９３，１９９３
【０００４】
【発明が解決しようとする課題】
しかして、特許文献２に記載されているように、データ圧縮／データ簡略化工程は、データ圧縮を効率よく行うために、通常、三つのステップからなる。変換ステップ、量子化ステップ、並びに、符号化ステップであり、複雑な多様体上でデータをモデル化するためのリフティング・スキームが開発されている。本発明は、リフティング・スキーム（並びに、第二世代ウェーブレットを利用する他の同様な構成）で生成されたデータを圧縮／簡略化する機構の改善を目的とする。圧縮の観点からすると、リフティング・スキームは、変換ステップの機能を効果的に実行するものである。
次に、データを圧縮する工程のうちの符号化ステップを説明する。従来、ゼロツリー・アルゴリズムと称されるビット符号化方法を用いて、古典的なウェーブレットの符号化が行われていた。ウェーブレット係数を符号化するゼロツリー・アルゴリズム方法は、最初、非特許文献９（ウェーブレット係数のゼロツリーを利用した組込み型画像符号化方法）により提唱された。この手法は、ビデオ技術用の回路並びにシステムに関するＩＥＥＥトランザクションに投稿された論文（非特許文献１０参照）に詳述されているように、最近になって、Ａ．Ｓａｉｄ並びにＷ．Ａ．Ｐｅａｒｌｍａｎにより、改良された。この手法に関しては、更に、非特許文献１１に詳述されている。
ＳａｉｄとＰｅａｒｌｍａｎは、従来のウェーブレット変換を改良して、ウェーブレット係数をビット符号化する高速で高性能の方法を提案した。図１（Ａ）及び図１（Ｂ）を参照して、この方法並びにその限界を説明する。図１（Ａ）は、ウェーブレット変換で処理される画像１００を示す図である。通常、ウェーブレット変換では、例えば、正方形１０２のような画像が繰り返し部分分割され、この各レベルにおいて、係数は、部分分割のレベルに関係づけられる。例えば、図１（Ａ）に示す最疎レベルでは、正方形１０２は、正方形１０２の全面に関係する予測係数値Ａ１０３を有する。ウェーブレット変換を繰り返すことにより、正方形１０２は、画素レベルに到達するまで、遂次小さな子正方形に、部分分割される。各レベルにおいて、係数は、分割された子正方形に対応する、と予測される。
図１（Ｂ）は、画像１００におけるウェーブレット変換の繰り返しの次の詳細化レベルを示す。図示するように、正方形１０２は、四つの同じ大きさの子正方形に分割される。ここで、係数Ａ１０３は、正方形１０２の中心に示されているように、正方形１０２の全面に関係しつづけている。この繰り返し段階において、正方形１０２は、正方形１０４、１０６、１０８、１１０に部分分割される。ウェーブレット変換と先に算出された係数を用いることにより、新しい係数Ｂ１０５、Ｃ１０７、Ｄ１０９、Ｅ１１１が、それぞれ、新たに分割された子正方形１０４、１０６、１０８、１１０の面に関係づけられる。言い換えると、係数Ａ１０３は、正方形１０２の面に関する予測係数値であり、一方、係数Ｂ１０５は、正方形１０４に関する予測値である。ここで、予測値は、所定の正方形のグレースケール、或いは、最下位のレベルにおいては、画素を示す。
同様にして、画像１００におけるウェーブレット変換の繰り返しの更に次のレベルを実行すると、部分分割された正方形１０２が、更に小正方形に部分分割され、例えば、正方形１０４は、四つの子正方形に部分分割され、これらの新しく分割された子正方形が、例えば、新たな予測係数、Ｆ１１３、Ｇ１１５、Ｈ１１７、Ｉ１１９で予測され、小さな子正方形の各々の面に関連づけられる。
かかる部分分割構造を、Ｓａｉｄ並びにＰｅａｒｌｍａｎによるゼロツリー方法を実現するツリー構造で表現すると、クアド（四部）ツリー或いはＱツリーと呼ばれるツリー構造は、各ノードが正方形を表わし、ゼロツリー方法では、まず最初に、Ｑツリー内のすべてのウェーブレット係数を配置し、Ｑツリーの根の部分には、最疎レベルにおける係数が配置される。（最上位レベルにおけるこのような係数は、スケール係数とも呼ばれる）。係数Ａ１０３が正方形１０２の最疎レベルを示す場合、係数Ａ１０３がＱツリー１２０の根に配置される。各係数は、四つの「子」、即ち、同じ位置に配置される、次の段階の、より高い解像度の係数を有する。つまり、ノードＡの子が、係数Ｂ１０５、Ｃ１０７、Ｄ１０９、Ｅ１１１である。言い換えると、ノードＡの子が、正方形１０２の次の段階の部分分割に対応する。正方形１０２が正方形１０４、１０６、１０８、１１０に部分分割されると、これらの部分分割された正方形の各々に関連づけられた係数が、親ノードＡの子ノードを形成する。
Ｓａｉｄ及びＰｅａｒｌｍａｎの符号化手法は、画像の滑らかな部分では、係数が指数関数的に減衰するという事実に依存している。これは、ある係数が閾値未満であれば、その子も同様に閾値未満である可能性が高いことを示している。則ち、このような場合には、小さな係数のツリー全体を放棄する可能性がある。例えば、係数Ｂが閾値未満或いはゼロに近ければ、同様に、係数Ｆ、Ｇ、Ｈ、Ｉも閾値未満である可能性が高い。
更に、Ｑツリーでは、各係数の物理的な位置に関しても、暗黙のうちに符号化を行っている。例えば、係数Ｂ、Ｃ、Ｄ、Ｅは、係数Ａの子であるため、係数Ｂが正方形１０２の左上部分を占め、係数Ｃが正方形１０２の右上部分を占めることが、暗黙のうちに了解され、ゼロツリー符号化アルゴリズムを用いることによって、各係数の個々の座標値を符号化することなく、係数の圧縮と伝送を行なっている。従って、かかる手法は、３次元形状モデルの表面にテクスチャを貼り付けるような場合には利用可能であるが、３次元形状モデルの詳細かつ大量のメッシュ用座標値データを、所定の解像度で高速に簡略化したり、又、復元するのには適していない。
又、入力した３次元空間の形状モデルは、通常、数十万から数百万個のｘ，ｙ，ｚ座標値で構成されているので、詳細なレベルまでモデル形状に忠実に復元できるように簡略化しようとすると、三角形メッシュに基づいた形状簡略化方法では、演算時間及び作業メモリを非常に大量に要求され、高速な簡略化はとても望めないという根本的な問題点があった。
よって、本発明は上述の様な事情に鑑みて成されたものであり、本発明の目的は、四辺形メッシュからなる３次元形状モデルの多重解像度表現処理において、数十万から数百万、或いは、それ以上の個数のｘ，ｙ，ｚ座標値で構成されている３次元形状モデルを、簡略化された形状モデルが、詳細な元の形状モデルと近似し、簡略化及びその復元処理が、どちらも高速で、可逆的に実行可能であり、詳細に復元された形状モデルが元の形状モデルと完全に一致すると共に、簡略化処理／復元処理の演算過程において、データ量が常に一定であり、則ち、逆変換に必要な情報のための記憶領域を新たに用意する必要が無い３次元形状モデルの多重解像度表現処理方法及び装置を提供することにある。
【０００５】
【課題を解決するための手段】
本発明は、３次元形状モデルの多重解像度表現方法に関し、本発明の上記目的は、
前記３次元形状モデルを四辺形メッシュで分割する工程と、当該四辺形メッシュで分割した形状モデルを多重解像度表現する工程とを含み、
前記多重解像度表現工程が、取り除いた頂点が、簡略化した頂点から復元可能であるように、予測演算子としてサブディビジョンを採用したリフティングスキームにより、簡略化工程及び復元工程を行うことによって達成される。
また、本発明は、３次元形状モデルの多重解像度表現装置にも関し、本発明の上記目的は、
前記３次元形状モデルを四辺形メッシュで分割する手段と、当該四辺形メッシュで分割した形状モデルを、順変換手段及び逆変換手段により多重解像度表現する手段とを含み、更に、
前記順変換手段及び逆変換手段が、予測手段、更新手段、及び、分割手段又は統合手段を含み、
前記予測手段では、取り除いた頂点が、簡略化した頂点から復元可能であるように、予測演算子としてサブディビジョンを採用したリフティングスキームにより、順変換を演算し、前記３次元形状モデル・データの簡略化処理を行うことによっても達成される。
【０００６】
【発明の実施の形態】
以下、図面に基づいて、本発明の好適な実施例について、詳細に説明する。
本発明は、コンピュータにより実現される種々の演算を実行するためのプログラム命令を含むコンピュータ読取り可能な媒体に関する。媒体及びプログラム命令は、本発明の目的のために特別に設計・構築されたものでもよいし、或いは、コンピュータソフトウェア分野の当業者に周知で利用可能なものでもよい。これに限定されるものではないが、コンピュータ読み取り可能な媒体の例としては、ハードディスク、フロッピーディスク、磁気テープ等の磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤ等の光学媒体、ＭＯディスク等の光磁気媒体、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）等の、プログラム命令を格納し、実行するように特別に構成されたハードウェア装置が挙げられる。又、プログラム命令の例としては、コンパイラ等により生成された機械コード、並びに、インタプリタを用いてコンピュータにより実行される高レベルのコードを含むファイルが挙げられる。
従って、本発明の３次元形状モデルの多重解像度表現装置では、上記３次元形状モデルを四辺形メッシュで分割する手段と、当該四辺形メッシュで分割した形状モデルを、順変換手段及び逆変換手段により多重解像度表現する手段とは、一般的に、コンピュータにより実現される種々の演算を実行するためのプログラム命令で構成し、また、上記順変換手段及び逆変換手段、並びに、予測手段、更新手段、分割手段、及び、統合手段も、コンピュータにより実現される種々の演算を実行するためのプログラム命令で構成するのが、好ましい。
図４に、本発明を実現するのに適した典型的なコンピュータ・システムを概念的に示す。図示するように、中央処理装置４（ＣＰＵ）は、リードオンリーメモリ８（ＲＯＭ）、ランダムアクセスメモリ６（ＲＡＭ）を含む記憶装置に接続されている。当業者に周知のように、ＲＯＭ８は、ＣＰＵ２にデータ及び命令を単方向転送し、一方、ＲＡＭ６は、通常、データ及び命令の双方向転送に用いられる。データ記憶容量を増やすように、大容量記憶装置１２が、更に、ＣＰＵ２と双方向に連結されている。大容量記憶装置１２をプログラム、データ等の保存に用いることもできるし、又、磁気テープ或いは紙テープ・リーダ或いは他の周知の装置（例えば、ＣＤ−ＲＯＭ）を大容量記憶装置１２として用いてもよい。大容量記憶装置１２内に保持されている情報を、仮想メモリとして、標準的な方法でＲＡＭ６に組み込むようにしてもよい。ＣＰＵ２は、更に、これに限定されるものではないが、ビデオモニタ、トラックボール、マウス、キーボード、マイク、タッチセンサー式のディスプレイ、変換カードリーダ、磁気或いは紙テープリーダ、タブレット、自動記録計、音声或いは手書き判別機、他のコンピュータ等、他の周知の入力装置を含む、一つ或いは複数の入出力装置１０に接続されている。更に、ＣＰＵ２を、ネットワーク接続１４を利用して、別のコンピュータや通信ネットワークに連結することもできる。これらの装置はコンピュータのハードウェア及びソフトウェア分野の当業者には周知のものである。
【０００７】
本発明では、３次元形状モデルを四辺形メッシュからなるサブディビジョン手法により表現する。３次元モデル形状に合わせた四辺形メッシュの対辺の分割格子点数が一致するメッシュ生成方法で、短時間に３次元有限要素メッシュ生成が可能な方法は、例えば、特開平５ー２６２７号に記載されている手法と同様な方法で実現できる。
又、Ｘ線ＣＴやＭＲＩで得られる断層画像データから、輪郭線データを抽出したり、レーザー光等により光学的に形状測定を実施し、直接、測定点群の座標データから最も詳細なレベルの３次元形状モデルを生成してもよい。
かくして、最も詳細なレベル（ｊ＝０）の３次元形状モデルの四辺形メッシュを構成する頂点座標を、Ｐｉｑ＝（ｘｉｑ、ｙｉｑ、ｚｉｑ）（ｉ＝１，２，３，・・・，ｍ、ｑ＝１，２，３，・・・，ｎ）で表現すると、レベルｊを考慮した頂点座標は、
Ｐ（０）ｉｑ＝（ｘ（０）ｉｑ、ｙ（０）ｉｑ、ｚ（０）ｉｑ）
（ｉ＝１，２，３，・・・，ｍ、ｑ＝１，２，３，・・・，ｎ）  ・・・（１）
と表現できる。又、解像度のレベルｊを、順次、図２に示すように粗くし、この粗くする簡略化の過程を、レベルｊ＝−１，−２，−３，・・・，Ｋで表現すると、簡略化されたレベルｊでの四辺形メッシュの頂点座標は、それぞれ、
Ｐ（ｊ）ｉｑ＝（ｘ（ｊ）ｉｑ、ｙ（ｊ）ｉｑ、ｚ（ｊ）ｉｑ）
（ｉ＝１，２，３，・・・，ｍ／２＊＊ｊ、ｑ＝１，２，３，・・・，ｎ／２＊＊ｊ）  ・・・（２）
と表現できる。
更に、レベルｊの頂点座標と、レベルｊ＋１（又はｊ−１）の頂点座標とは、各頂点座標の線形結合によって、相互に変換可能であるので、サブディビジョン・スキームでは、この入出力関係をＨ［］で表現すると、一般的に、偶数頂点Ｐ２ｉと、奇数頂点Ｐ２ｉ＋１とは、別々に処理される。数１、数２に、サブディビジョン・近似スキームの解像度変換式を、数３、数４に、サブディビジョン・補間スキームの解像度変換式をそれぞれ、示す。
【数１】
2004164221.tif 000003
但し、ｉは、ｘ，ｙ，ｚ座標毎に、それぞれ、独立しているとする。
【数２】
2004164221.tif 000004
但し、ｉは、ｘ，ｙ，ｚ座標毎に、それぞれ、独立しているとする。
【数３】
2004164221.tif 000005
但し、ｉは、ｘ，ｙ，ｚ座標毎に、それぞれ、独立しているとする。
【数４】
2004164221.tif 000006
但し、ｉは、ｘ，ｙ，ｚ座標毎に、それぞれ、独立しているとする。
一般に、曲面を表現するサブディビジョン・スキームでは、曲面の位置によらず一定（シフト不変）の関係が成立するため、数１から数４に示すように、畳み込みの形式で出力が得られ、補間スキームの数４においては、Ｐ（ｊ＋１）２ｉ＝Ｐ（ｊ）２ｉ  となっており、これにより、補間スキームでは、解像度を変化させても元の頂点が、自動的に補間され表現されることがわかる。
【０００８】
次に、リフティングスキームの予測演算子として利用する、４ーポイントスキームについて説明する。４−ポイントスキームは、隣接する４つの離散点の重み付き和により補間点を繰り返し演算し、その極限として補間曲線を得る方法であり、重みパラメータｗを用いて、次式で表現される。
【数５】
2004164221.tif 000007
但し、ｗは、０＜ｗ＜２（√（５）ー１）の範囲の値である。
【数６】
2004164221.tif 000008
数５で、ｗは、テンションパラメータ（ｔｅｎｓｉｏｎ  ｐａｒａｍｅｔｅｒ）とも呼ばれ、ｗ＝１の場合には、３次多項式で補間曲線／曲面を推定することに相当し、この場合に得られる曲線は、Ｃ１連続となることが証明されている。かかる関係を、上記数３、数４に適用すると、ｗ＝１の場合のサブディビジョンは、所定のフィルタ係数を有するインパルス応答して、以下のようにシステム的に表現できる。
【数７】
2004164221.tif 000009
【数８】
2004164221.tif 000010
上記数８において、一般的な畳み込みと異なり、ｈｌのシフトが２ｋであるため、偶数頂点と奇数頂点を得る処理は、その演算が異なる。又、数５は、以下のように書き換えられる。
【数９】
2004164221.tif 000011
この演算を図示すると、図５のようになり、その幾何学的な解釈は、点Ｐ（ｊ）ｉと点Ｐ（ｊ）ｉ＋１との中点に、加えるベクトルｅの大きさを、パラメータｗによって、調節していることが分かる。かくして、Ｋｏｂｂｅｌｔの補間スキームは、上記４−ポイントスキームを、４辺形メッシュ曲面に拡張したものであり、図６（Ｂ）に示すような１６点からなる近傍の制御点に、それぞれ所定の重み係数を設定し補間演算することで、補間点が生成されるようになっている。この演算は、４−ポイントスキームを縦横に連続して適用した結果であり、これは、Ｂ−スプライン演算におけるテンソル積曲面と同じ概念であり、又、システム理論的には、図６（Ａ）の４−ポイントスキームの縦続型構成ともいえる。
【０００９】
次に、３次元形状モデルの多重解像度解析表現について説明する。先ず、ウェーブレットとは、平均値が０で原点ｔ＝０の周りに局在する関数ψ（ｔ）のことであり、これをｔ  軸上でｂ単位シフトし、又、拡大・縮小率をａとすると、次式のような基底を得る。
【数１０】
2004164221.tif 000012
この基底関数と、信号ｆ（ｔ）との内積により、次式に示すウェーブレット変換が与えられる。
【数１１】
2004164221.tif 000013
又、ψ（ｔ）のフーリエ変換をψ（ω）とし、次のアドミッシブル条件を満たす場合、
【数１２】
2004164221.tif 000014
逆変換が存在し、その形式は、次式となる。
【数１３】
2004164221.tif 000015
更に、数１０において、ａ＝２＊＊（ーｊ）、ｂ＝ｋ・２＊＊（ーｊ）を代入し、２進分割（ｂｉｎａｒｙｐａｒｔｉｔｉｏｎ）すると、離散信号ｆ（ｎ）に対する離散ウェーブレットが、次式のように定義できる。
【数１４】
2004164221.tif 000016
ここで、ｊを、以下、レベルと呼び、レベルｊが大きい程高周波となる。この離散ウェーブレットが、シフト（ｋの変化）とダイレーション（ｊの変化）に対して、次式のような正規直交性をもつとき、
【数１５】
2004164221.tif 000017
【数１６】
2004164221.tif 000018
離散ウェーブレット変換対は、次式で演算できる。
【数１７】
2004164221.tif 000019
【数１８】
2004164221.tif 000020
かくして、近似連続関数を生成するためのスケーリング関数が、次のように定義できる。
【数１９】
2004164221.tif 000021
尚、上記スケーリング関数に関しても、数１５、数１６に示すような正規直交の条件を満たさなければならない。更に、上記スケーリング関数とウェーブレットとの間に、次式のような関係（ツースケール関係）が、成立する場合を考える。
【数２０】
2004164221.tif 000022
【数２１】
2004164221.tif 000023
上記ツースケール関係が成立する場合、最も精度の良い簡略化レベルｊ＝０、それより１段階低い（粗い）簡略化レベルｊ＝−１のスケーリング関数によって信号ｆ（ｎ）を近似すると、近似信号は、それぞれ、次式で演算できる。
【数２２】
2004164221.tif 000024
【数２３】
2004164221.tif 000025
ここで、簡略化レベルｊの近似関数及びスケーリング係数ｓ（ｊ）ｋは、それぞれ、次式で演算できる。
【数２４】
2004164221.tif 000026
【数２５】
2004164221.tif 000027
上記１段階粗い関数ｆー１（ｎ）は、ｆ０（ｎ）と比較すると、ある種の情報が欠落しており、この欠落情報は、数２１で演算したψー１、ｋ（ｎ）により演算されるウェーブレット成分
【数２６】
2004164221.tif 000028
であり、この結果、
ｆ０（ｎ）  ＝  ｆー１（ｎ）＋ｇー１（ｎ）    ・・・（３）
となる。これらは、一般の簡略化レベルｊについても成り立ち、レベルｊ＋１とレベルｊとの間には、次式が成立する。
【数２７】
2004164221.tif 000029
更に、簡略化レベルＪまで、繰り返し演算すると、次式が成立する。
【数２８】
2004164221.tif 000030
ここで、簡略化レベルｊでのウェーブレット成分は、次式で演算できる。
【数２９】
2004164221.tif 000031
上記数２８は、任意の簡略化レベルＪの粗さまで近似した関数ｆーＪ（ｎ）に、簡略化演算過程で失われた成分を、順次追加していくことにより、元の信号ｆ０（ｎ）が再現できることを示しているので、多重解像度解析が成立する。
次に、離散信号に関しては、推移インパルスと信号関数との内積（畳み込み）を用いて表すことができ、数２２におけるスケーリング関数を、以下に示す単位パルス関数
【数３０】
2004164221.tif 000032
とすることで
ｆ（ｎ）＝ｆ０（ｎ）＝Σｓ（０）ｋ・１（ｎ−ｋ）    ・・・（４）
となり、離散値を連続値にすることができる。つまり、
【数３１】
2004164221.tif 000033
と表現できる。スケーリング関数は信号を近似する目的で使われるので、単位パルス以外の場合にも、数３１の近似が成り立つとすると、数２５に数２０を代入することにより、次式が演算できる。
【数３２】
2004164221.tif 000034
同様にして、数１７に、数２１を代入して、次式が演算できる。
【数３３】
2004164221.tif 000035
数３２、数３３により、簡略化レベルｊ＋１のスケーリング係数から、１段階粗いレベルｊでのスケーリング係数、ウェーブレット展開係数を演算できる。この関係を用いて、図７（ａ）に示すように、順次低いレベル係数を求めることができる。数３１の関係を用い、スケーリング係数により離散信号を表現する場合、数３１より、任意の粗さ（レベル）で信号を近似できることになる。
【００１０】
次に、上記演算過程の逆の演算関係を求める。
上記数２５に、数２７を代入し、スケーリング関数の正規直交性を用いて展開すると、次式を得る。
【数３４】
2004164221.tif 000036
数３４より、図７（ｂ）に示すように、順次簡略化レベルの高い信号を復元することができる。かくして、数２０、数２１のツースケール関係に用いた数列ｐｋ，ｑｋは、各レベルに共通であり、これらが決まると、数３２〜数３４のように多重解像度解析が行える。
一般的な演算式である数１７、数２５に比べ、数３２、数３３では演算量が減少できるため、これらは高速ウェーブレット変換と呼ばれている。尚、具体的な数列ｐｋ，ｑｋに関しては、種々のものが利用可能であるが、例えば、Ｉ．  Ｄａｕｂｅｃｈｉｅｓの提案する係数列がある。
【００１１】
次に、サブディビジョン手法とウェーブレット変換による多重解像度解析を結びつけるために用いたリフティングスキームに関して説明する。
リフティングスキームは、数２０，数２１に示すようなツースケール関係を満たすスケーリング関数とウェーブレットをそれぞれ生成し、高速ウェーブレット変換を構成するための理論であり、１９９４年にＷ．  Ｓｗｅｌｄｅｎｓによって提案された。その順変換（ｆｏｒｗａｒｄ  ｔｒａｎｓｆｏｒｍ）は、レベルｊの入力信号ｓｊを、１段階低いレベルの近似信号ｓｊ−１と詳細信号（ｄｅｔａｉｌ  ｓｉｇｎａｌ）ｄｊ−１に分解処理することであり、図８（Ａ）に示すような配線図（ｗｉｒｉｎｇ  ｄｉａｇｒａｍ）で表すことができる。以下にその具体的な処理を説明する。
●分割（Ｓｐｌｉｔ）処理：
分割処理は、入力信号ｓｊに対して、偶数番目の信号ｓｊ，２ｌと、奇数番目の信号ｓｊ，２ｌ＋１に振り分け、これらの信号を、１段階低いレベルの信号ｅｖｅｎｊ−１，ｌ及びｏｄｄｊ−１，ｌ（それぞれ、以下、偶数信号及び奇数信号と呼ぶ）に、分割処理する。この操作を、以下の数３５のように表現する。
【数３５】
2004164221.tif 000037
●予測（Ｐｒｅｄｉｃｔ）処理：
入力信号ｓｊが、局所的な相関を有し滑らかに変化する信号の場合、上記分割された偶数信号ｅｖｅｎｊ−１と奇数信号ｏｄｄｊ−１との間には、比較的強い相関関係が存在する。従って、所定の精度で、一方の信号から、他方の信号を予測することが可能となり、例えば、上記偶数信号ｅｖｅｎｊ−１で、奇数信号ｏｄｄｊ−１を予測し、その差分を詳細信号ｄｊ−１として、次式で演算する。
【数３６】
2004164221.tif 000038
従って、信号が滑らかな場合には、ｅｖｅｎｊ−１に基づく信号予測精度が良く、詳細信号ｄｊ−１は小さくなり、上記予測値を求める関数Ｐ（）を以下予測関数と呼ぶ。
●更新（Ｕｐｄａｔｅ）処理：
１段階粗い近似信号ｓｊ−１に望ましい特性は、原信号ｓｊと同一の平均値を持つことである。すなわち信号の平均値
【数３７】
2004164221.tif 000039
がレベルｊが変化しても、同一のままであることが望ましく、これは最終の近似信号（ｓ０，０とする）が、信号全体の平均値（又は直流成分）と同一が望ましいことからも理解できる。単純に分割した信号ｅｖｅｎｊ−１において、平均値が保存されるように、詳細信号ｄｊ−１を用いて更新処理するのが、この段階である。
【数３８】
2004164221.tif 000040
以下、更新値を求める関数Ｕ（）を、更新関数と呼ぶことにする。
上記全ての演算は、次のように定位置（ｉｎ−ｐｌａｃｅ）で実行できる。
【数３９】
2004164221.tif 000041
【数４０】
2004164221.tif 000042
【数４１】
2004164221.tif 000043
つまり、奇数信号ｏｄｄｊ−１は、偶数信号ｅｖｅｎｊ−１によって求められた予測値を用いて上書きし、得られた奇数信号ｏｄｄｊ−１による更新値で、偶数信号ｅｖｅｎｊ−１を上書きすることで実行できる。
【００１２】
次に、上記変換の逆変換（ｉｎｖｅｒｓｅ  ｔｒａｎｓｆｏｒｍ）に関して、図８（Ｂ）の配線図を参照して説明する。先ず、
●逆更新（Ｕｎｄｏ  ｕｐｄａｔｅ）処理：
与えられた信号ｓｊ−１に対して、信号ｄｊ−１を用いた更新値を減算して信号ｅｖｅｎｊ−１を生成する。
【数４２】
2004164221.tif 000044
●逆予測（Ｕｎｄｏ  ｐｒｅｄｉｃｔ）処理：
信号ｓｊ−１より求めた予測値Ｐ（）を信号ｄｊ−１に加える。
【数４３】
2004164221.tif 000045
●統合（Ｍｅｒｇｅ）処理：
Ｓｐｌｉｔ（）により、偶数信号ｅｖｅｎｊ−１と奇数信号ｏｄｄｊ−１に分割された信号を、１レベル高い次元の１つの信号ｓｊに戻す。この操作を、次式で表す。
【数４４】
2004164221.tif 000046
逆変換に関しても、数３９〜数４１と同様の演算により、次式のように、定位置計算可能である。
【数４５】
2004164221.tif 000047
【数４６】
2004164221.tif 000048
【数４７】
2004164221.tif 000049
【００１３】
上述のリフティングスキーム演算では、アルゴリズム的、及び、その演算実行に関して、次のような特徴がある。
●定位置計算が可能
すべての演算が、数３９〜数４１、又は、数４５〜数４７のように、同じメモリ位置に上書きすることで実行でき、補助的なメモリ領域を必要としない。
●計算効率の高さ
その他の高速ウェーブレット演算と同様に、浮動小数点演算の回数を減らすことができる。
●並列性
図８（Ａ）、図８（ｂ）のような配線図の形でウェーブレットを構成できるため、それぞれのレベルで、入力を複数のシステム（配線）に分割して並列演算を実行することが容易である。
●逆変換の容易さ
図８（Ａ）、図８（Ｂ）の配線図を比較して分かるように、Ｓｐｌｉｔ（）演算とＭｅｒｇｅ（）演算、及び、上書きの際の＋＝演算と−＝演算を入れ換えるだけで、単純に逆ウェーブレット変換を実行できる。これにより変換対のコーディングが容易になる。
●設計の容易さ
要求される簡略化の性質に合わせて、予測値を得るための関数Ｐ（）を選ぶことにより、すべての変換が構築できる。
【００１４】
次に、サブディビジョン演算に、リフティング・スキームの概念を導入する。リフティング・スキームにおいて、予測関数Ｐ（）の役割は、偶数信号ｅｖｅｎｊ−１を用いて奇数信号ｏｄｄｊ−１を予測することにあるが、偶数信号ｅｖｅｎｊ−１に対してサブディビジョン演算の補間スキームを適用することで、その間に存在する奇数信号ｏｄｄｊ−１を予測できる。則ち、予測関数Ｐ（）として、補間サブディビジョン演算が利用できるという事である。これを補間予測関数ＰＩ（）と書くことにすると、１回のサブディビジョン演算は、図９の小ブロックような配線図で表すことができる。
又、連続信号を得るためには、図９の全体のように、これを無限個直列接続したもので構成できる。サブディビジョン演算では、離散入力に対して、精細化した連続信号を得ることになるので、数２４の関係式に示すように、スケーリング関数が、その性質を決める。スケーリング関数は、次式のように、
【数４８】
2004164221.tif 000050
レベルｊの離散信号から連続信号を得るように定義される。かくして、レベルｊの離散信号入力に対して、サブディビジョンを繰り返し実行して、連続信号を得るシステムとして考えることができる。従って、原点に開始レベルｊ＝０の単位インパルス信号
【数４９】
2004164221.tif 000051
を入力し、図９に示すようなシステムで得られた関数を、基本スケーリング関数
【数５０】
2004164221.tif 000052
と定義する。尚、離散信号は等間隔
【数５１】
2004164221.tif 000053
に配置するのが好ましい。数７のフィルタ係数で定義される４−ポイント補間スキームによって得られたスケーリング関数を図１０に示す。明らかに、
【数５２】
2004164221.tif 000054
となっており、補間の性質を有することがわかる。レベルｊが変化しても、数５２の特性を有するため、数１９のような振幅方向の拡大縮小の特性は無く、次式のように
【数５３】
2004164221.tif 000055
ｘ軸上の広がりとシフト演算により、任意のスケーリング関数が定義できる。故に、直交性に関しては、シフト演算に関してのみ定義されていれば良いが、これは図９から数５２に示すような特性を有するため容易に確認できる。又、ツースケール関係式である数２０の係数ｐｌ−２ｋに関しては、この場合、数７に示すようなサブディビジョンのフィルタ係数が利用可能である。
【数５４】
2004164221.tif 000056
数３４に対応する式を考えると、この式では、ウェーブレット展開係数ｗ（ｊ）ｋに対応する詳細信号ｄｊ−１，ｌが無く、次式のようになる。
【数５５】
2004164221.tif 000057
【００１５】
かくして、サブディビジョン演算に関して、そのスケーリング関数が定義できたので、次に、これに対応するウェーブレットに関して説明する。図９に示すようなサブディビジョン演算において、解像度ｊが１レベル上がる場合、入力信号がｍ個あると、その出力信号は、（２ｍ−１）個となり、逆に、解像度ｊが、１レベル下がる場合ａは、（２ｍ−１）個の入力信号が、ｍ個の出力信号に変換される。そこで、かかる解像度の変化により追加されたり失われたりする（ｍ−１）個の情報に対して、図７及び図８に示すようなリフティングスキームと同様に、サブディビジョン演算においても、詳細信号を考えることにする。
スケーリング関数の場合と同様に、図９に示すようなシステムにおいて、奇数信号ｏｄｄの原点に、開始レベルｊ＝０の単位インパルス信号を入力した場合、平均値（面積）が０ではないためにウェーブレットとはならない。そこで、リフティング演算における更新関数Ｕ（）を用いることにより、図１１に示すような、関数の平均値＝０であるようなウェーブレット関数ψ（ｘ）＝ψ０，０（ｘ）を得ることができる。よって、スケーリング関数と同様にして、任意のレベルｊのウェーブレット関数を
【数５６】
2004164221.tif 000058
のように演算できることが分かる。結局、リフティング・スキームを応用したサブディビジョン演算は、図１２のように構成でき、このような詳細信号ｄｊ−１を考慮したサブディビジョン演算を、以下、リフティングサブディビジョンと呼ぶ。
【００１６】
次に、図１２に示すようなリフティング・サブディビジョン演算の構成において、４−ポイントスキームに対する補間予測関数ＰＩ（）と、更新関数Ｕ（）の具体例を示す。
補間予測関数ＰＩ（）に関しては、４−ポイントスキームの演算式・数５、数６から分かるように、次式のように表現できる。
【数５７】
2004164221.tif 000059
又、更新関数Ｕ（）に関しては、
【数５８】
2004164221.tif 000060
のような構成を考え、この定数Ａを具体的に演算すると、先ず、更新関数Ｕ（）は、単位インパルスに対する平均値が０となるように設定されるので、図１２の詳細信号ｄｊとして単位インパルスを入力すると
【数５９】
2004164221.tif 000061
が成立し、この式を解くと、Ａ＝１／４となる。又、予測関数Ｐ（）の係数の１／２倍の係数を、更新関数Ｕ（）に用いることができるので、
【数６０】
2004164221.tif 000062
とすることも可能である。
上記のような構成では、信号の平均値（０次のモーメント）だけでなく、予測関数と更新関数のオーダー（次数＋１）Ｎとして、次式で演算されるｐ次のモーメント
【数６１】
2004164221.tif 000063
が解像度レベルｊによらず、保存される。
【００１７】
３．４．５  リフティングによる多重解像度解析
数５４の演算と同様に、ウェーブレットにおける次式に示すようなツー・スケール関係
【数６２】
2004164221.tif 000064
も成立し、これにより、上記段落００１４で説明したような多重解像度解析演算
【数６３】
2004164221.tif 000065
が可能となる。
ここで、数６２の係数ｇｌは、詳細信号に対するインパルス応答に対応し、例えば、数５８に示すような更新関数Ｕ（）を用いた場合、次式のように演算可能である。
【数６４】
2004164221.tif 000066
かくして、リフティング・スキームは、ウェーブレットのデザインを行い、かつ、ウェーブレット変換の多重解像度解析を高速に演算する手法であるが、本発明では、解像度レベルの変化に応じて要求される膨大な記憶容量（特に、詳細な高解像度レベルでは、３次元形状モデルでは、数百万点の頂点座標が利用される）を新しく用意せずとも、同一の記憶領域に上書き／再利用した形態で、効率よく、高解像度レベルから低解像度レベルまで同一の記憶領域が利用可能である。更に、サブディビジョンは、離散点から滑らかな曲面を構成するメッシュ詳細化手法であるが、これを元にウェーブレットをデザインし、簡略化された形状が元の形状の近似となるように、取り除く頂点を残された頂点からサブディビジョンで推定した場合、当該推定値と実際の座標値との差をウェーブレット係数として利用し、かかるウェーブレットを用いて、頂点座標の多重解像度解析を行うことによりメッシュの詳細度レベルを変更することが可能であり、又、かかるウェーブレット係数を用いて、完全な誤差の無い形状の復元も実行することができ、かかる手法を、以下、リフティング・サブディビジョンと呼ぶ。
【００１８】
次に、リフティングサブディビジョンの具体例に関して、更に説明する。先ず、最も詳細なレベル（ｊ＝０）の３次元形状モデルの四辺形メッシュを構成する頂点座標Ｐｉｑ＝（ｘｉｑ、ｙｉｑ、ｚｉｑ）（ｉ＝１，２，３，・・・，ｍ、ｑ＝１，２，３，・・・，ｎ）は、上記式（１）のように表現できる。
又、解像度のレベルｊを、順次、図２に示すように粗くし、この粗くする簡略化の過程を、レベルｊ＝−１，−２，−３，・・・，Ｋで表現すると、簡略化されたレベルｊでの四辺形メッシュの頂点座標は、それぞれ、上記式（２）のように表現できる。この簡略化したレベルｊでのモデルの頂点座標の個数は、上記例では、（ｍ／２＊＊ｊ）ｘ（ｎ／２＊＊ｊ）個となる。
本発明の目的は、最も詳細なレベルｊ＝０の頂点座標Ｐ（０）ｉｑの集合から、簡略化したレベルｊ＝−１，−２，−３，・・・，Ｋでの頂点座標Ｐ（ｊ）ｉｑを効率よく、使用メモリを増加させないで演算することである。
尚、レベルｊとレベルｊ−１との添え字の変化を、図３に示す。本発明では、簡略化のためにレベルｊを１つ減少させた場合、ｉ方向及びｑ方向に対して、それぞれ、１つおきに頂点座標データを残し、全体として、頂点の個数が、略１／４となるように簡略化を実行するのが好ましい。
【００１９】
本発明の簡略化では、入力された初期の頂点のｘ，ｙ，ｚ座標値ｘ（０）ｉｑ，ｙ（０）ｉｑ，ｚ（０）ｉｑに対し、それぞれ、ウェーブレットの多重解像度解析により、各簡略化後のｘ，ｙ，ｚ座標値を演算するようになっており、例えば、ｘ座標の多重解像度解析では、初期の頂点のｘ座標値ｘ（０）ｉｑに対して、２次元離散ウェーブレット変換に基づいた多重解像度解析を実行し、レベルｊ（＝−１，−２，−３，・・・，Ｋ）でのスケーリング関数の係数を、簡略化後のメッシュのｘ座標値ｘ（ｊ）ｉｑとして採用する。尚、ｙ座標値ｙ（ｊ）ｉｑ及びｚ座標値ｚ（ｊ）ｉｑに関しても、全く同様に演算できるので、以下では、ｘ座標値ｘ（ｊ）ｉｑに対してのみ示すが、ｙ座標値、ｚ座標値に対しても、同様に演算可能であることは明かである。
【００２０】
次に、レベルｊ（＝０、−１，−２，・・・，Ｋ）でのｘ座標値ｘ（ｊ）ｉｑが入力された場合の、簡略化レベルｊ−１（＝−１，−２，・・・，Ｋ）でのｘ座標値ｘ（ｊー１）ｉｑを演算する簡略化演算に関して説明する。図１４に示すような２次元配列で表現される座標値ｘ（ｊ）ｉｑ及びｘ（ｊー１）ｉｑの間には、レベルｊの場合にメッシュの大きさが４ｘ４であり、レベルｊ−１の場合、２ｘ２の座標値ｘ（ｊー１）ｉｑと共に、復元のための詳細情報ｄ（ｊ−１）ＨＬ，ｉｑ，ｄ（ｊ−１）ＬＨｉｑ，ｄ（ｊ−１）ＨＨｉｑが演算され、２ｘ２個の所定の記憶領域に格納されるようになっている。
従って、レベルｊでの頂点ｘ座標値ｘ（ｊ）ｉｑの集合は、簡略化レベルｊ−１のレベルダウンにより、４つの要素ｘ（ｊー１）ｉｑ，ｄ（ｊ−１）ＨＬ，ｉｑ，ｄ（ｊ−１）ＬＨｉｑ，ｄ（ｊ−１）ＨＨｉｑに分解され、これらの値は、２次元離散ウェーブレット変換により高速に演算可能である。尚、上記ｘ座標値ｘ（ｊー１）ｉｑは、スケーリング関数の係数から演算され、詳細情報ｄ（ｊ−１）ＨＬ，ｉｑ，ｄ（ｊ−１）ＬＨｉｑ，ｄ（ｊ−１）ＨＨｉｑは、ウェーブレット係数で演算される。
【００２１】
次に、ウェーブレット多重解像度解析には、リフティング・スキームを採用するが、この演算を、図１３に示す。同図において、演算子Ｓｉｍｐｌｉｆｉｃａｔｉｏｎは、メッシュの解像度レベルを１つ下げる簡略化スキームを表現し、又、演算子Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎは、簡略化されたメッシュから１つ上の解像度レベルが高いメッシュを復元する再構成復元スキームを表現している。
Ｓｉｍｐｌｉｆｉｃａｔｉｏｎスキームでは、入力が１次元の配列ｓ（ｊ）であり、この入力配列に対する１次元ウェーブレット変換のスケーリング係数列ｓ（ｊ−１）と、ウェーブレット係数列ｄ（ｊ−１）が、演算され出力される。
一方、Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎスキームでは、２つの１次元の配列ｓ（ｊー１）とｄ（ｊ−１）を入力とし、それぞれを、スケーリング係数列ｓ（ｊ−１）及びウェーブレット係数列ｄ（ｊ−１）とみなして、ウェーブレット逆変換を実行し、再構成されたスケーリング係数列ｓ（ｊ）を出力する。
尚、１次元配列ｓ（ｊ）から演算されるスケーリング係数列ｓ（ｊ−１）とウェーブレット係数列ｄ（ｊ−１）は、それぞれ、図１５に示すような順番で格納することにより、上書き可能であり、新しく記憶領域を確保する必要はない。
【００２２】
上記Ｓｉｍｐｌｉｆｉｃａｔｉｏｎスキーム及びＲｅｃｏｎｓｔｒｕｃｔｉｏｎスキームは、以下の４つの演算子を含む。
●分割（Ｓｐｌｉｔ）演算子：
分割（Ｓｐｌｉｔ）演算子は、１次元配列ｓ（ｊ）を、偶数番目の信号と、奇数番目の信号に分割し、これらの信号を、それぞれ、１次元配列ｅｖｅｎ（ｊ−１）及びｏｄｄ（ｊ−１）に格納する演算子である。
●予測（Ｐｒｅｄｉｃｔ）演算子：
予測（Ｐｒｅｄｉｃｔ）演算子は、偶数番目の配列ｅｖｅｎ（ｊ−１）から奇数番目の配列ｏｄｄ（ｊ−１）を、サブディビジョン手法により推定する演算子である。
●更新（Ｕｐｄａｔｅ）演算子：
更新（Ｕｐｄａｔｅ）演算子は、ウェーブレット係数ｄ（ｊ−１）から、スケーリング係数ｓ（ｊ−１）を演算する演算子である。
●統合（Ｍｅｒｇｅ）演算子：
統合（Ｍｅｒｇｅ）演算子は、１次元配列ｅｖｅｎ（ｊ−１）及びｏｄｄ（ｊ−１）から、それぞれが、偶数番目及び奇数番目に該当するような数列を構築し、１次元配列ｓ（ｊ）に格納する演算子である。
【００２３】
かかるリフティング・スキームを、図１４に示すような２次元座標配列ｘ（ｊ）ｉｑに適用し、簡略化レベルを（ｊ−１）に低下させた場合のｘ座標値ｘ（ｊー１）ｉｑ及び詳細情報ｄ（ｊ−１）ＨＬ，ｉｑ，ｄ（ｊ−１）ＬＨｉｑ，ｄ（ｊ−１）ＨＨｉｑを求める演算は、以下のとうりである。
先ず、ｘ（ｊ）ｉｑのそれぞれの行を１次元の配列とみなし、図１３に示すようなリフティング・スキーム演算を実行する。
具体的には、入力座標値配列ｘ（ｊ）ｉｑのサイズがｍｘｎである場合、ｎ個の行（ｑ＝０，１，・・・、Ｋ，・・・，ｎ−１）に対して、ｓ（ｊ）＝（ｘ（ｊ）０ｑ、ｘ（ｊ）１ｑ、・・・、ｘ（ｊ）Ｋｑ、・・・、ｘ（ｊ）ｎ−１ｑ）とおき、リフティング・スキーム演算により得られた結果ｓ（ｊ−１）、ｄ（ｊ−１）を、図１５に示すように配列ｘ（ｊ）ｉｑに上書きする。
次に、上記上書きされた２次元配列ｘ（ｊ）ｉｑを用い、ｍ個の列（ｉ＝０，１，・・・，Ｋ，・・・，ｍ−１）に対して、ｓ（ｊ）＝（ｘ（ｊ）ｉ０、ｘ（ｊ）ｉ１、・・・、ｘ（ｊ）ｉＫ、・・・、ｘ（ｊ）ｉｍ−１）とおき、リフティング・スキーム演算により得られた結果ｓ（ｊ−１）、ｄ（ｊ−１）を、図１５に示すように配列ｘ（ｊ）ｉｑに同様に上書きする。
かくして、入力頂点座標配列ｘ（ｊ）ｉｑに対する簡略化されたｘ座標値ｘ（ｊー１）ｉｑ及び詳細情報ｄ（ｊ−１）ＨＬ，ｉｑ，ｄ（ｊ−１）ＬＨｉｑ，ｄ（ｊ−１）ＨＨｉｑが、図１４に示すような配置で得られる。
逆に、簡略化されたメッシュから元の詳細メッシュの復元、則ち、レベルｊ−１の頂点ｘ座標値ｘ（ｊー１）ｉｑからレベルｊの頂点座標ｘ（ｊ）ｉｑへの変換は、図１３に示すリフティング・スキームのＲｅｃｏｎｓｔｒｕｃｔｉｏｎスキーム演算を適用することにより得られる。
以上が、リフティング・サブディビジョンによるメッシュ簡略化及び復元の手順である。
【００２４】
次に、リフティング・スキームにおける２つの作用素Ｐｒｅｄｉｃｔ及びＵｐｄａｔｅに関して説明する。リフティング・スキームによるウェーブレット変換のスケーリング関数とウェーブレットは、これらの演算子により決定される。本発明では、上記２つの演算子をサブディビジョン手法に基づいて決定する。
先ず、演算子Ｐｒｅｄｉｃｔとしては、任意の１次元サブディビジョン手法が利用可能である。例えば、上記４ーポイントスキームが利用可能であり、４ーポイントスキームは、離散点の間の点を補間するために、その周囲の４つの頂点を利用する手法であり、図１３に示すリフティング・スキームでは、演算子Ｐｒｅｄｉｃｔは、奇数番目の座標値ｏｄｄ（ｊ−１）＝（ｏｄｄ（ｊ−１）０，ｏｄｄ（ｊ−１）１，・・・，ｏｄｄ（ｊ−１）ｎ／２−１）を、偶数番目の座標値ｅｖｅｎ（ｊ−１）＝（ｅｖｅｎ（ｊ−１）０，ｅｖｅｎ（ｊ−１）１，・・・，ｅｖｅｎ（ｊ−１）ｎ／２−１）から４ーポイントスキームにより推定する。偶数番目の４つの座標値ｅｖｅｎ（ｊ−１）ｉ−１，ｅｖｅｎ（ｊ−１）ｉ，ｅｖｅｎ（ｊ−１）ｉ＋１ｅｖｅｎ（ｊ−１）ｉ＋２を用いると、ｏｄｄ（ｊ−１）ｉの推定値は、次式の演算で得られる。
【数６５】
2004164221.tif 000067
但し、ｗは、０＜ｗ＜２（√（５）ー１）の範囲の値であり、通常、ｗ＝１を利用可能である。
従って、図１３に示すリフティング・スキームにおける詳細情報ｄ（ｊ）ｉは、次式で演算可能である。
【数６６】
2004164221.tif 000068
【００２５】
一方、演算子Ｕｐｄａｔｅは、演算子Ｐｒｅｄｉｃｔに対応して決定され、これは、非特許文献８に記載されているように、ｓ（ｊ−１）、ｄ（ｊ−１）が、所定のスケーリング関数とウェーブレット係数となるような演算子であれば、任意に選択可能である。４ーポイントスキームの場合には、通常、次式で、演算子Ｕｐｄａｔｅは演算可能である。
【数６７】
2004164221.tif 000069
尚、上記数６５及び数６７で有限個の配列の境界が問題になる場合には、反射配列、又は、巡回配列を自動的に生成し、新しい座標値を挿入することにより、有限個の配列の境界問題を回避可能である。例えば、ＣＴ断面画像等から生成されるメッシュの３次元モデルに対しては、巡回配列が好ましく、又、３次元レーザスキャナ等から得られる３次元形状モデルの場合には、反射配列を用いるのが好ましい場合が多い。
【００２６】
次に、ツースケール関係による多重解像度解析とリフティングスキームによる多重解像度解析の計算量について比較する．先ず、レベルｊでの頂点座標値ｘ（ｊ）ｉｑから，レベルｊ−１に簡略化した頂点座標値ツｘ（ｊー１）ｉｑ及び詳細情報ｄ（ｊ−１）ＨＬ，ｉｑ，ｄ（ｊ−１）ＬＨｉｑ，ｄ（ｊ−１）ＨＨｉｑを求める演算量について考察する。但し、レベルｊ−１で求める頂点数と詳細情報の数はｎ１ｘｎ２とすると，このとき、レベルｊでの頂点数は２ｎ１ｘ２ｎ２となる。
先ず、ツースケール関係を用いた場合、表１に示すように数２０、数２１に使用するスケーリング係数を求めるためのツースケール列ｐｉの非零要素数は１１個であり，又、ウェーブレット係数を求めるための係数列ｑｉの非零要素数は５個である。従って、１次元のｎ１個のスケーリング係数とウェーブレット係数を求めるのに要する積和演算数は、それぞれ１１・ｎ１、５・ｎ１回であり，２次元の多重解像度解析では、合計３２・ｎ１・ｎ２回の積和演算となる．
【表１】
2004164221.tif 000070
一方，リフティングスキームを用いた場合，数５７、数６０より，１次元のｎ１個のスケーリング係数とウェーブレット係数を求めるのに要する積和演算数は共に４・ｎ１回であり，これより２次元多重解像度解析では、合計１６・ｎ１・ｎ２回となる．
従って、本発明の双直交ウェーブレットでは，リフティングスキームによる多重解像度解析は、従来のツースケール関係を用いた場合と比べて半分の演算量で計算可能となる．
【００２７】
次に、リフティングスキームを四辺形メッシュで構成された３次元形状モデルに適用し、多重解像度表現を行った実験例を示す。本実験では、３次元形状モデルは、複数の連続したＣＴ画像やＭＲＩ画像等の断面画像の輪郭線を自動的に抽出して、陰関数表現した形状モデルを生成し、この陰関数表現した形状モデルから各断面の格子点を特定し、相互の断面間に四辺形メッシュを生成したものである。具体的には、３次元形状モデルの表面を
Ｆ（ｘ，ｙ，ｚ）  ＝  ０      ・・・（５）
を満足する（ｘ，ｙ，ｚ）座標の集合として構成し、断面の数を２００とし、各断面での輪郭線上での格子点の数を、最も詳細なレベルｊ＝０で、８００点とした。又、座標軸（インデックス）は、断面の輪郭線方向をｉ方向とし、断面方向をｑ方向に設定した。従って、四辺形初期メッシュの頂点の総数は、８００ｘ２００個である。
かかる初期メッシュ（レベルｊ＝０）の頂点座標集合をＣ（０）とし、レベルｊ＝−１、−２、・・・、−５に対する簡略化された形状モデルＣ（ｊ）を演算した。形状Ｃ（ｊ）をレンダリングした結果を、図５（Ａ）〜（Ｆ）に示す。頂点数は、それぞれ、４００ｘ１００（ｊ＝−１）、２００ｘ５０（ｊ＝−２）、１００ｘ２５（ｊ＝−３）、５０ｘ１３（ｊ＝−４）、２５ｘ７（ｊ＝−５）となり、又、それぞれのレベルに対応した演算時間は、以下の表２のようになった。但し、演算に使用したＣＰＵは、ＡＭＤ社製のＡｔｈｌｏｎ１ＧＨｚ，１２８Ｍｂｙｔｅで、ＯＳは、Ｗｉｎｄｏｗｓ９８である。
【表２】
2004164221.tif 000071
【００２８】
【発明の効果】
本発明によれば、四辺形メッシュからなる３次元形状モデルの多重解像度表現処理において、数十万から数百万、或いは、それ以上の個数のｘ，ｙ，ｚ座標値で構成されている３次元形状モデルを、簡略化された形状モデルが、詳細な元の形状モデルと近似し、簡略化及びその復元処理が、どちらも高速で、可逆的に実行可能であり、詳細に復元された形状モデルが元の形状モデルと完全に一致すると共に、簡略化処理／復元処理の演算過程において、データ量が常に一定であり、則ち、逆変換に必要な情報のための記憶領域を新たに用意する必要が無い３次元形状モデルの多重解像度表現処理方法及び装置を提供することができる。
【図面の簡単な説明】
【図１】従来の多重解像度表現処理の１例を示す概念図である。
【図２】本発明の多重解像度表現処理の１例を示す概念図である。
【図３】本発明の簡略化レベルｊとレベルｊ−１との間の、頂点座標間の関係を説明する図である。
【図４】本発明のハードウエア構成の１例を示すブロック図である。
【図５】本発明の４−ポイントスキームの幾何学的概念を説明する図である。
【図６】その２次元に拡張した概念を説明する図である。
【図７】ウェーブレット変換による信号の分割／再構成の過程を説明する図である。
【図８】リフティングスキームの順変換及び逆変換の構成の１例を示す図である。
【図９】サブディビジョンにより連続関数を生成する１例を示す図である。
【図１０】本発明の補間サブディビジョンのスケーリング関数の１例を示す図である。
【図１１】本発明の補間サブディビジョンのウェーブレットの１例を示す図である。
【図１２】本発明のリフティング・サブディビジョンの１例を示すブロック図である。
【図１３】本発明の簡略化演算子及び再構成演算子の１例を示す図である。
【図１４】本発明のメモリ利用領域の記憶形式を説明する図である。
【図１５】その１次元配列でのメモリ利用領域の記憶形式を説明する図である。
【図１６】本発明の３次元形状モデルの多重解像度表現処理の１例を示す図である。
【図１】
2004164221.tif 000072
【図２】
2004164221.tif 000073
【図３】
2004164221.tif 000074
【図４】
2004164221.tif 000075
【図５】
2004164221.tif 000076
【図６】
2004164221.tif 000077
【図７】
2004164221.tif 000078
【図８】
2004164221.tif 000079
【図９】
2004164221.tif 000080
【図１０】
2004164221.tif 000081
【図１１】
2004164221.tif 000082
【図１２】
2004164221.tif 000083
【図１３】
2004164221.tif 000084
【図１４】
2004164221.tif 000085
【図１５】
2004164221.tif 000086
【図１６】
2004164221.tif 000087