JP3731466B2

JP3731466B2 - ３次元自由曲面データ圧縮転送方式

Info

Publication number: JP3731466B2
Application number: JP2000316599A
Authority: JP
Inventors: 通亀田
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 2000-10-17
Filing date: 2000-10-17
Publication date: 2006-01-05
Anticipated expiration: 2020-10-17
Also published as: JP2002123838A

Description

【０００１】
【発明の属する技術分野】
この発明は、Ｗeb等における仮想３次元空間の配布における３次元自由曲面、２次元自由曲線のデータ圧縮、転送に関するものである。
【０００２】
【従来の技術】
図９は、例えば、従来の装置の伝送の様式を示す原理図である。図において、９１は送出しようとする３次元曲面であり、９２は送出時の処理で、９３は送出媒体（この例では、無線回線）である。９４は無線回線受信機で、９５は復元の処理、９６は、復元再現された３次元商品である。なお、NURBS処理を利用して曲面処理をする従来例として、特開平07-021249号公報や、自由曲線近似変換方法や特開平07-244744号公報に、自由曲線近似変換方法などや、論文「Approximate conversion of spline curves」(Josef Hoschek, CAGD, Vol.4, 1987，pp5 9-66)など在るが、これらは機械ＣＡＤ分野で、利用者が曲面を容易に生成するためのものであり、本発明の通信のためのデータ圧縮に利用するものとは異なる。
【０００３】
次に、これらの動作について説明する。
従来は、３次元仮想物体や商品は、ポリゴンという微小三角形の要素によって自由曲面を構成し作成されていた。そして、これらの情報は、そのポリゴンデータのまま、送信回線に送出されていた。このとき、対象の仮想３次元物体、人物キャラクタ、商品などは、その形が複雑であればあるほど、莫大なポリゴンが発生する事となり、通信回線の上を莫大なデータが移動していた。それゆえ、低速の通信回線では、それがボトルネックとなって障害が発生していた。また受信した側でも、そのデータは、そのまま曲面を形成する為に使われていた。それゆえ、弾性的な柔構造の仮想物体を送付するには、新たな手法を模索しなければならない。
【０００４】
【発明が解決しょうとする課題】
しかし、上述の従来装置は、３次元曲面を表現するため、ポリゴンという細分化された微細３角形小平面で構成するようになっている。それゆえ、これらの３次元曲面をデータとして送付する場合、そのまま三角形の３個の頂点データを送る為、なめらかな曲面を送るには、極めて膨大なデータを送らねばならない困難性があった。
【０００５】
その結果、高速な通信回線が必要であり、また通信量が多い場合、輻輳などの障害の原因となっていた。
【０００６】
また、特に需要の多い無線回線を介しての通信の場合には、機能上からデータ転送速度に限界があるため、多大な影響があった。
【０００７】
例えば、高度に滑らかな３次元曲面を送付、転送しようとする場合、特に、Ｗeb上での３次元仮想遊園地での個性ある人物キャラクタ、仮想物体、３次元商品のデータを転送する場合、無線回線では大きな障害となった。
【０００８】
そこで、本発明は、ポリゴンで構成される３次元自由曲面を、無線などの低速回線においても、極めて容易に送付や転送することのできる３次元自由曲面データ圧縮転送方式を提供することを目的とする。
【０００９】
【課題が解決するための手段】
上記課題を解決するため、本発明の３次元自由曲面データ圧縮転送方式では、ポリゴンで構成される３次元自由曲面から遺伝的アルゴリズムと、Newton法の処理とを併用して、NURBS（Non Uniform Relational Base Spline）関数自由曲線と、そのパラメータデータを注出して使用する事を特徴とする。
【００１０】
特に、３次元自由曲面を任意方向でラスタスキャンして、曲線ストライプ状にして、これをNURBS曲線とする事を特徴とする。
【００１１】
また、ポリゴンで構成される３次元自由曲面データに雑音が混入している場合でも、遺伝的アルゴリズムとNewton法で共同使用するLMS（Loot Mean Square）処理によって抽出可能としている事を特徴とする。
【００１２】
また、NURBS各節点での各パラメータ数値をバイナリデータとして各染色体に対応させる事を特徴とする。
【００１３】
また、遺伝的アルゴリズムの染色体の適応度評価処理と、Newton法での方向ベクトル抽出とを併用する事を特徴とする。
【００１４】
また、遺伝的アルゴルズムで適合度を評価する処理と、Newton法でLMS処理を用いて方向ベクトルを抽出する処理は、隣り合う両節点までの補間データを用いて計算する事を特徴とする。
【００１５】
また、NURBS関数を抽出する際、あらかじめ頭初に任意NURBS曲線を設定し、これをポリゴンデータの統計的特性と整合させるように、遺伝的アルゴリズムとNewton法処理で交互に漸近制御する事を特徴とする。
【００１６】
また、遺伝的アルゴリズムを処理する際、染色体に変換するNURBS節点のパラメータは、位置座標X、位置座標Y、重み係数W、節点配順係数Kである事を特徴とする。
【００１７】
また、NURBS節点の各パラメータでの各染色体スープ数は、１０個以上である事を特徴とする。
【００１８】
また、遺伝的アルゴリズムでの１染色体上での交叉数は、１〜３個の範囲である事を特徴とする。
【００１９】
また、遺伝的アルゴリズムでの優生増殖、あよび突然変異の発生確率は１０％から９０％までとし、スープ数に応じた割合とし、また反比例してクローン生成個数を設定する事を特徴とする。
【００２０】
【発明の実施の形態】
図１は、この発明の実施のデータ送出、受信の方式を示す原理図である。図において、１１は送付しようとする仮想物体、人物キャラクタ商品の３次元自由曲面のポリゴン図、１２はそのポリゴン自由曲面をNURBS自由曲線群で示した図、１３はNURBSのパラメータデータのみを圧縮した圧縮済データ、１４はこの圧縮済データ１３を送出する無線回線送出装置（無線送信機）、１５は無線回線受信装置（無線受信機）であって、これで受信されたデータは、NURBS曲線群１６に再現され、仮想３次元自由曲面１７に復元される。
【００２１】
図２、この発明の実施の具体的適用例で、データ圧縮再現の工程を、さらに詳細に示した構成図である。図において、２１は３次元仮想遊園地を提供する為のVRMLのＷebサーバ、２２は、本発明の自由曲面の処理工程で、２３は従来の簡素形状の処理工程である。また、２４は本発明の自由曲面の処理工程２２と、従来の簡素形状の処理工程２３からのデータを送出するインターネット回線、２５はインターネット回線２４のつながる無線回線送出装置（この例で、無線送信機）である。これらで構成される送出側は、通常の無線回線も含めたサーバ回線である。また、従来の簡素形状の処理工程２３で膨大なポリゴンデータの発生を無くするため、本発明の自由曲面処理２２が併設されている点が、送出側の特徴である。
【００２２】
また、図において、２６は無線回線受信装置（無線受信機）であり、２７は無線回線受信装置（無線受信機）２６からのデータを従来のVRML書式と、本発明の書式とに分離抽出するVRML解析装置である。VRML解析装置２７から分離抽出されたデータは、NURBS自由局面復元装置２９で、曲面が復元され、こえらの復元された曲面要素で、さらに自由局面構成での仮想物体、人物キャラクタの復元装置２１０において仮想物体、仮想人物キャラクタが復元構成され、VR空間仮想３次元空間遊園地全復元装置２８へと送出される。
【００２３】
図３は、数理的な観点からの処理工程と復元工程をさらに詳細に説明した図である。図において、３１は仮想３次元遊園地内の仮想人物キャラクタ・物体の自由曲面を検索する為、VRML書式をタグリスト検索する工程である。３２はこれらの対象から自由曲面で構成されている部分を抽出する工程である。また３３はこれらの抽出された自由曲面から、さらに自由曲線群に変換する工程で、その曲面をストライプ状の折れ線として変換する。また３４はそしてこれの各頂点を点群としてNURBS自由曲線群にさらに変換する。そしてさらにパラメータデータとしてデータ圧縮処理をおこなう工程、３５は圧縮されたパラメータデータを、無線回線送出装置２５からに送出する工程である。
【００２４】
また、図３において、３６は無線回線受信装置２６（例：無線受信機）で受信する工程であり、パラメータデータを受信する。３７は受信されたパラメータデータからNURBS処理で曲線を復元再生する工程である。３８は復元されたNURBS曲線群で、さらに曲面を復元する工程である。３９はこれらの曲面で、人物キャラクタを創生したり、仮想３次元遊園地の中の構成対象を復元する工程である。
【００２５】
図４は、ポリゴン頂点の点群からNURBS曲線を生成させる処理ルーチンを詳細に説明する図である。
図４において、４１は、対象物体から自由曲面の部分を選出する処置の工程である。４２は曲線を生成する下準備として初期任意NURBS曲線を生成、設定する工程である。４３は遺伝的アルゴリズム（ＧＡ；Genetic Algorithm）で、NURBS各接点の各パラメータを原始染色体として通常の遺伝的アルゴリズムを適用する。４４はNewton法処理の工程である。４５は遺伝的アルゴリズムとNewton法で共通に使う適応性評価と方向ベクトル抽出処理工程である。ここで通出した結果で、実際のNURBS節点を移動させる。４６は遺伝的アルゴリズムが規定の世代交代の回数に達してかを判定する工程で、規定回数に達していれば、終了する。
【００２６】
図５は、遺伝的アルゴリズムの適応性評価とNewton法処理の方向ベクトル抽出を行うための説明図である。５１は任意NURBS曲線で、５２はそれを制御する各節点である。５３は各節点での評価値を計算するための範囲の部分で、両隣り合う節点までの範囲の補間データ部分で、計算をする事を示している。５４はこの計算の結果、得られた方向ベクトルで、これは各パラメータ（X,Y,W,K）に対して、それぞれ存在する。
【００２７】
図６は、NURBS節点の各パラメータを染色体に変換する処理を説明する図である。図において、６１はNURBS曲線、６２は節点である。６３は節点６２の各パラメータ（ｘ、ｙ、ｗ、ｋ）を染色体に変換した様子である。本実施の形態では、浮動小数点数値をバイナリデータに変換し、使用している。そして、突然変異、交叉処理は、バイナリ座位に応じたｌｏｇ的な発生確率で乱数発生させている。
【００２８】
図７は、本発明の遺伝的アルゴリズムとNewton法の処理との併用で、どのような探索動態を示すかを示した図である。図において、７１は染色体スープ、７２は遺伝的アルゴリズムでの探索動態、７３はNewton法での方向ベクトルでの移動軌跡である。探索動態７２が拡がっているのは、突然変異と交叉によって各染色体が探索している様子である。移動軌跡７３のベクトル矢印の尻部は、優性選択の部分から出ている事を示している。
【００２９】
図８は、ポリゴン頂点の点群からNURBS曲線を生成させた様子を示す図である。図において、８１はポリゴン頂点の点群で、８２はNURBS曲線、８３は節点を示している。
【００３０】
以上説明したように、本実施の形態１によれば、無線移動通信回線のような比較的低速な通信回線においても、仮想３次元空間遊園地や、そこに存在する個性ある仮想人物キャラクタや物体も、容易に受信、復元する事が出来る事になる。
【００３１】
また、遺伝的アルゴリズムは、一般には、NP−完全問題の平位面に対し適用するのだが、本発明では、数値生成における知的にエントロピー制御された乱数発生装置として利用した。
【００３２】
【発明の効果】
以上のように、この発明によれば、仮想３次元遊園地の内の構成対象の自由曲線で構成された部分を抽出し、NURBS曲線にしてデータ圧縮する事で、低速回線でも高速に転送できる効果がある。
【００３３】
また、この発明によれば、３次元曲面を２次元化する事で、NURBS曲線とする事で、関数化する事が出来、データ圧縮できるようになる効果がある。
【００３４】
また、この発明によれば、NURBS処理をLMS処理を用いる事で、雑音の混入した場合でも精製された曲線が生成できる効果がある。
【００３５】
また、この発明によれば、NURBS曲線の節点を染色体に変換する事で、遺伝的アルゴリズムで制御できる効果がある。
【００３６】
また、この発明によれば、遺伝的アルゴリズムとNewton法で、共用できるようになる効果がある。
【００３７】
また、この発明によれば、本来は３次４階のNURBS曲線であるが、これを若干、反映して評価できる効果がある。
【００３８】
また、この発明によれば、NURBS曲線をあらかじめ設定している事で、全く雑音に埋もれている点群データであっても、漸近適応で、NURBS曲線を生成できる大きな耐久性を持つ効果がある。
【００３９】
また、この発明によれば、節点の染色体化を規定し、遺伝的アルゴリズムの適応を可能とする効果がある。
【００４０】
また、この発明によれば、染色体スープ個数により、広範囲での探索が可能となる効果がある。
【００４１】
また、この発明によれば、交叉数の範囲内で類似探索が可能となる効果がある。
【００４２】
また、この発明によれば、発生確率を制御することで、探索暴走を防ぐ事と、Newton法とのバランスを維持する効果がある。
【図面の簡単な説明】
【図１】この発明の実施の形態１のポリゴンからNURBSデータ無線送出、受信の転送原理を示す原理図。
【図２】この発明の実施の形態１のデータ圧縮転送再現の装置の具体的適用例とその構成を詳細に示した構成図。
【図３】この発明の実施の形態１の処理工程の観点から、処理工程と復元工程を、さらに詳細に説明した図。
【図４】この発明の実施の形態１のポリゴンからNURBS曲線を生成する工程処理を詳細に説明する図。
【図５】この発明の実施の形態１の遺伝的アルゴリズムの適応化関数とNewton法での方向ベクトル抽出の処理の図。
【図６】この発明の実施の形態１の遺伝的アルゴリズムでのNURBS節点の染色体構造の図
【図７】この発明の実施の形態１の遺伝的アルゴリズムとNewton法を併用した場合の探索動態の図。
【図８】この発明の実施の形態１のポリゴンデータとこれらから生成させたNURBS曲線の対応図。
【図９】従来のポリゴン自由曲面の転送の方式を示す原理図。
【符号の説明】
１１自由曲面のポリゴン図
１２ NURBS抽出された自由曲線図
１３ URBSパラメータデータ
１４無線回線送出装置
１５無線回線受信装置
１６復元されたNURBS自由曲線群
１７仮想自由曲面
２１ VRMLのＷEBサーバ
２２のNURBS処理工程
２３従来の簡素形状の処理工程
２４インターネット回線
２５無線回線送出装置
２６無線回線受信装置
２７ VRML構文から分離抽出する工程
２８ VRML構文の簡素形状での仮想３次元空間遊園地の全復元装置
２９ NURBS自由曲面の復元装置
２１０自由曲面構成での仮想物体や人物キャラクタの復元装置

Claims

ポリゴンで構成される３次元自由曲面から遺伝的アルゴリズムと、Newton法の処理とを併用して、NURBS（Non Uniform Relational Base Spline）関数自由曲線と、そのパラメータデータを注出して使用する事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
３次元自由曲面を任意方向でラスタスキャンして、曲線ストライプ状にして、これをNURBS曲線とする事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
ポリゴンで構成される３次元自由曲面データに雑音が混入している場合でも、遺伝的アルゴリズムとNewton法で共同使用するLMS（Loot Mean Square）処理によって抽出可能としている事を特徴とするデータ３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
NURBS各節点での各パラメータ数値をバイナリデータとして各染色体に対応させる事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
遺伝的アルゴリズムの染色体の適応度評価処理と、Newton法での方向ベクトル抽出とを併用する事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
遺伝的アルゴルズムで適合度を評価する処理と、Newton法でLMS処理を用いて方向ベクトルを抽出する処理は、隣り合う両節点までの補間データを用いて計算する事を特徴とする３次元曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
NURBS関数を抽出する際、あらかじめ頭初に任意NURBS曲線を設定し、これをポリゴンデータの統計的特性と整合させるように、遺伝的アルゴリズムとNewton法処理で交互に漸近制御する事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
遺伝的アルゴリズムを処理する際、染色体に変換するNURBS節点のパラメータは、位置座標X、位置座標Y、重み係数W、節点配順係数Kである事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
NURBS節点の各パラメータでの各染色体スープ数は、１０個以上である事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
遺伝的アルゴリズムでの１染色体上での交叉数は、１〜３個の範囲である事を特徴とする３次元自由曲面データ圧縮転送方式。
請求項１に記載の３次元自由曲面データ圧縮転送方式において、
遺伝的アルゴリズムでの優生増殖、あよび突然変異の発生確率は１０％から９０％までとし、スープ数に応じた割合とし、また反比例してクローン生成個数を設定する事を特徴とする３次元自由曲面データ圧縮転送方式。