可視性データ圧縮方法、圧縮解除方法、圧縮システムおよびデコーダ
本発明は、可視性データの圧縮/圧縮解除方法、圧縮システムおよびデコーダに関する。本発明の方法は、可視性行列(Msr)内に含まれる行(i)が、共有される多数の要素を有しており、隣接していないことをチェックし、検出すると、修正済み可視性行列(M'sr)を形成するために、行を多数の共有要素を有すると検出された行に続くように切り換えるための自動検出(E7)と、修正済み可視性行列(M'sr)のブール要素へのデジタル画像符号化の適用(E8)とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可視性データベースからの可視性データの圧縮方法および圧縮解除方法、ならびにこれらの方法を実施するためのシステムに関する。
【背景技術】
【０００２】
本発明の適用分野は、たとえばシミュレーションやゲーム内のシーン内で移動する観察点からそのシーンのオブジェクトを表示することであり、そこでは観察点は、シーン内で移動するユーザの仮想観察点である。
【０００３】
オブジェクトは一般に事前に定義されており、観察点はその環境内で移動可能であり、この環境では、オブジェクトが様々な角度で見られ、オブジェクトが閉塞され(occlude)、または以前に閉塞された新しいオブジェクトが現れるので、画面上に表されるオブジェクトの外観を変化させるべきである。
【０００４】
オブジェクトを表示するときに生じる問題の1つは、観察点が移動する度に考慮されるべきデータが大量であることであり、この観察点は、ユーザの制御のもと非常に速く移動されることがある。
【０００５】
Peter Wonka、Michael WimmerおよびDieter Schmalstiegによる文献、「Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs」、Proceedings of Eurographic Rendering Workshop、2000年は、観察空間を表示セル(viewing cell)に分割し、オクルーダオブジェクトを量εだけ縮小し、各セルについてその十分な数のサンプリング点を決定し、そのセルから潜在的に見えるオブジェクトのセットを得るために各サンプリング点について可視性を計算することを提案している。
【０００６】
しかし、それらの潜在的可視オブジェクトのセットは、各セルごとに存在しており、非常に大量のデータである。
【０００７】
Michiel van de PanneおよびA. James Stewartによる文献、「Effective Compression Techniques for Precomputed Visibility」、Rendering Techniques 1999、305〜316頁、1999年は、観察点空間を小さい領域またはセルに分割し、ブール(Boolean)可視性テーブルを構築し、予備の計算ステップで事前に決定された情報を符号化し、各領域からどの多角形が見えるか示すことを提案している。その可視性テーブルでは、それぞれの行は観察点のセルに対応し、それぞれの列は、多角形に対応する。可視性テーブルの行i、列jに位置するいずれのエントリも、多角形jが領域iの点から少なくとも潜在的に可視である場合、かつその場合に限り、真の状態にある。可視性テーブルを圧縮するために、不可逆圧縮アルゴリズムでは、真エントリの類似のセットを有する行および列を併合する。別の、今度は可逆である圧縮アルゴリズムでは、共通のエントリを有する行から得られる新しい行および列を可視性テーブルに追加する。したがって、第1のアルゴリズムでは情報が失われ、または可視性テーブルは大き過ぎるままとなる。さらに、それらのアルゴリズムは、ネットワーク化された表示、すなわち可視性データを格納するデータベースから離れたユーザ局上での表示には適していない。
【０００８】
以下の文献を引用することもできる。
・C. Gotsman、O. SudarskyおよびJ. Fayman、「Optimized Occlusion Culling Using Five-Dimensional Subdivision」、Computer Graphics、23(5): 645〜654頁、1999年。この文献は、空間を5次元階層の可視性ツリー構造に編成する閉塞ソートアルゴリズム(occlusion sorting algorithm)について記載しており、この階層ではツリーの各葉が、より低いレベルの葉のうちの1つへの参照を含む。葉の第i位置の真の値は、その葉に第iのオブジェクトが存在することを示すものであり、偽の値は、その葉、またはそれより下のレベルの葉にそのオブジェクトが存在しないことを示すものである。そのアルゴリズムの欠点は、それぞれの観察点についてツリーがトラバースされなければならないことである。それは、可視性データを格納するデータベースから離れたユーザ局上でのネットワーク化された表示には適していない。
・Boaz Nadler、Gadi Fibish、Shuly Lev-YehudiおよびDanile Cohen-Or、「A qualitative and quantitative visibility analysis in urban scenes」、Computer & Graphics、23(5): 655〜666頁、1999年。この文献は、所与のオブジェクトが所与の表示セルから見える確率を、そのセルに対する距離の関数として計算する。隣接セルについての潜在的可視オブジェクトセットの交差がセル内で推定され、複製の数を減少させるためデータを階層構造に格納するために、セル間の一貫性が活用される。しかし、データの量は、大き過ぎるままである。
・Christopher ZachおよびKonrad Karner、「Progressive compression of visibility data for view-dependent multiresolution meshes」、Journal of WSCG、11巻、3号、546〜553頁、2003年。この文献は、可視性情報が多解像度構造のノードに直接格納されることができ、また可視性データの必要な部分だけが送信される圧縮方法を提案している。その方法では、最初に送信されなかった新しいデータの到着を待つことが必要であるので、見えるオブジェクトのすべてが毎回決定されるとは限らず、それによって、この方法に望ましくない待ち時間が生じることになる。
・V. Koltun、Y. ChrysanthouおよびD. Cohen-Or、「Virtual Occluders: An Efficient Intermediate PVS Representation」、Eurographics Workshop on Rendering、59〜70頁、Eurographics、2000年。この文献は、それらの仮想オクルーダを使用して表示セルについて潜在的可視セット(PVS: potentially visible set)を作成するために、その表示セルについての仮想オクルーダを定義することに限定しているが、しかし、取得されるデータが大量であることの問題には対処していない。
・Fabio O. Moreira、Joao L.D. CombaおよびCarla M. D. S. Freitas、「Smart Visible Sets for Networked Virtual Environments」、SIBGRAPI 2002。この文献は、潜在的可視セット(PVS)の情報を、位置を考慮した動的サブセットに分割したものに対応する、スマート可視セット(SVS: smart visible set)を定義している。分類機構は、最重要と分類されたデータだけが送信されることを可能にする。したがって、データの損失が生じる。その技術は、非常に大きいデータベース、またはネットワーク状況においてはテストされていない。
【非特許文献１】Peter Wonka、Michael Wimmer、Dieter Schmalstieg、「Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs」、Proceedings of Eurographic Rendering Workshop、2000年
【非特許文献２】Michiel van de Panne、A. James Stewart、「Effective Compression Techniques for Precomputed Visibility」、Rendering Techniques 1999、305〜316頁、1999年
【非特許文献３】C. Gotsman、O. Sudarsky、J. Fayman、「Optimized Occlusion Culling Using Five-Dimensional Subdivision」、Computer Graphics, 23(5): 645〜654頁、1999年
【非特許文献４】Boaz Nadler、Gadi Fibish、Shuly Lev-Yehudi、Danile Cohen-Or、「A qualitative and quantitative visibility analysis in urban scenes」、Computer & Graphics、23(5): 655〜666頁、1999年
【非特許文献５】Christopher Zach、Konrad Karner、「Progressive compression of visibility data for view-dependent multiresolution meshes」、Journal of WSCG、11巻、3号、546〜553頁、2003年
【非特許文献６】V. Koltun、Y. Chrysanthou、D. Cohen-Or、「Virtual Occluders: An Efficient Intermediate PVS Representation」、Eurographics Workshop on Rendering、59〜70頁、Eurographics、2000年
【非特許文献７】Fabio O. Moreira、Joao L. D. Comba、Carla M. D. S. Freitas、「Smart Visible Sets for Networked Virtual Environments」、SIBGRAPI 2002
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、従来技術の欠点を緩和し、また大部分が可逆でありながら圧縮データのサイズを著しく減少させる可視性データ圧縮方法を提供することである。
【課題を解決するための手段】
【００１０】
この目的のため、本発明は第1に、可視性データベースからの可視性データを圧縮する方法を提供し、
・可視性データが、所定のオブジェクトを観察するための観察空間内の観察点のセルと、観察点の各セルについて、観察点のそのセルから潜在的に見える前記所定のオブジェクトの中からのオブジェクトのリストとを含み、
・可視性データがデータベース内で少なくとも、各行がセルに対応し、各列が前記所定のオブジェクトのうちの1つに対応するブール要素の第1の可視性行列の形で表され、ブール要素がそれぞれ、オブジェクトjが、セルiに関連する潜在的可視オブジェクトのリストに属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
・多数の共通要素を有しており、隣接していない可視性行列内の行をデータベース内で自動的に検出し、修正済み可視性行列の形成のため、多数の共通要素を有すると検出された行を連続して置くようにこうしたいずれの行をも並べ替えること、および
・可視性データコードの取得のため、修正済み可視性行列のブール要素にデジタル画像符号化を自動的に適用することであって、修正済み可視性行列のこれらのブール要素が、符号化のためデジタル画像のピクセルを形成することを特徴とする方法を提供する。
【００１１】
本発明の他の特徴によれば、
・可視性データベースがデータ処理システムに関連付けられ、前記システムが、生成された可視性符号化データを可視性データ処理ユニットに送信し、
・データ処理システムがデータサーバであり、可視性データ処理ユニットが可視性データ処理局であり、
・データ処理システムおよび可視性データ処理ユニットが同じ可視性データ処理局内に設けられ、
・データ処理システムが、観察空間内の特定の観察点の位置に関する情報を処理ユニットから事前に受信しており、観察空間が可視性データベース内で領域に分割され、以下の諸ステップ、すなわち
・ユニットから受信された位置情報に対応する観察点が属する観察空間の領域の中から観察領域を決定するステップと、
・観察領域との交差を有する可視性データのセルの中から第1のセルを決定するステップと、
・決定された観察領域の前記第1のセルに対応する第1の可視性行列の行でその行が形成される第2の可視性行列を、第1の可視性行列から抽出するステップと、
・第2の可視性行列から修正済の可視性行列を形成するステップと、
・観察領域から潜在的に見えるオブジェクトのリストが、データ処理システム内で第2の可視性行列から自動的に決定され、データ処理システムによって可視性データコードを付けて処置ユニットに送信されるステップと、
・修正済の可視性行列のセルの識別子のリストが、データ処理システムによって可視性データコードを付けて処理ユニットに送信されるステップと、
・同一の行のグループごとに1つの行だけを第4の可視性行列内に保持するために、可視性行列の同一の列がデータ処理システムで自動的に決定され、修正済の可視性行列が第4の可視性行列から形成され、可視性行列の同一の行のグループの数であるデータアイテムが、データ処理システム内で自動的に計算され、同一の行の各グループについてグループデータアイテムが、グループの複数の同一行と、前記グループの同一の行の識別子のリストを含み、同一行のグループの数である前記データアイテム、および前記グループデータアイテムが、データ処理システムによって可視性データコードを付けて処理ユニットに送信されるステップと、
・同一の行の各グループについて、前記グループの同一の行の数が、所定の数のビット上で符号化され、前記グループの前記リストからの同一の行の各識別子が、所定の数のビット上で符号化され、各グループデータアイテムが、すべてのグループについて所定の順序において、グループの同一の行の前記数、およびグループの同一の行の前記識別子のリストからなるステップと、
・可視性行列内に少なくとも1つの0の列が自動的に検出され、修正済の可視性行列がそこから形成される第3の可視性行列を形成するため、検出されたいずれのこうした0の列もが可視性行列から自動的に削除されるステップと、
・修正済の可視性行列のブール要素に適用される前記デジタル画像符号化が、JBIGまたはPNGタイプのものであるステップとがデータ処理システム内で自動的に実行される。
【００１２】
本発明は第2に、デジタル画像復号が、生成された可視性データコードに適用されることを特徴とする、上述したような可視性圧縮方法によって生成された可視性データコードを圧縮解除する方法を提供し、その復号は、前記圧縮方法によって適用されるデジタル画像符号化の逆であり、復号により可視性行列がもたらされる。
【００１３】
この圧縮解除方法の他の特徴によれば、
・0の列が、前記デジタル画像復号によって得られた可視性行列に、観察領域から潜在的に見えるオブジェクトのリストによって示された潜在的に見えないオブジェクトの位置で自動的に追加され、
・前記デジタル画像復号によって得られた可視性行列に、グループデータアイテムの同一の行の識別子のリスト内には存在し、前記可視性行列には存在しない、同一の行の識別子によって示された少なくとも1つの欠落した行が自動的に追加され、次いで、その少なくとも1つの欠落した行が、同一の行の識別子の前記リスト内に存在する識別子を有する可視性行列の行に等しい。
【００１４】
本発明は、上述したような可視性データ圧縮解除方法を実行する手段を含むデコーダをも提供する。
【００１５】
本発明は、可視性データベースに関連するシステムをさらに提供し、
・可視性データが、所定のオブジェクトを観察するための観察空間内の観察点のセルと、観察点の各セルについて、観察点のそのセルから潜在的に見える前記所定のオブジェクトの中からのオブジェクトのリストとを含み、
・可視性データがデータベース内で少なくとも、各行がセルに対応し、各列が前記所定のオブジェクトのうちの1つに対応するブール要素の第1の可視性行列の形で表され、ブール要素がそれぞれ、オブジェクトjが、セルiに関連する潜在的可視オブジェクトのリストに属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
前記システムが、上述したような可視性データ圧縮方法を実行する手段を含む。
【００１６】
本発明は、コンピュータ上で実行されるときに、上記で述べたデータ圧縮方法を実施する命令を含むコンピュータプログラムをさらに提供する。
【００１７】
本発明は、コンピュータ上で実行されるときに、上記で述べたデータ圧縮解除方法を実施する命令を含むコンピュータプログラムをさらに提供する。
【００１８】
本発明は、非限定的な例としてのみ示された以下の説明を読み、添付の図面を参照してよりよく理解することができる。
【発明を実施するための最良の形態】
【００１９】
本発明について、オブジェクトを表示するための装置からなる一実施形態において、たとえばサーバSERVがデータベースBD内でオブジェクトについての可視性データDVをホストするクライアントサーバアーキテクチャを使用して以下に述べる。オブジェクトは、実際または抽象のオブジェクトをモデル化する幾何学的データセットDVOBJに対応する。そのコンピュータCAL内にデータ処理手段を含むサーバSERVは、データ処理システムSERVをも形成する。サーバSERVから離れたユーザの局CLは、それに要求を送信するため通信チャネルCTによってそれに接続され、したがって、この局CLがデータ処理ユニットを構成する。サーバSERVは、チャネルCT上で局CLにこれらの要求への応答を送信する。チャネルCTは、1つまたは複数の通信ネットワークを横断し、このために、たとえばサーバSERVおよび局CLのそれぞれに、ネットワークインターフェースINTS、INTCが設けられる。
【００２０】
もちろん、示されていない他の実施形態において、データベースBDおよびデータ処理システムSERVは、局CLと同じマシン、たとえばユーザのコンピュータ上に存在することもできる。次いで、たとえばデータベースBDは、コンピュータの大容量メモリ、たとえばハードディスク内に、または取出し可能記憶媒体、たとえばコンピュータの対応する読取り装置内に挿入されたCD-ROM内にあることがあり、圧縮データは、コンピュータ内のユニットによってそれができるだけ速く処理され得るように生成されなければならない。
【００２１】
以下では、圧縮された可視性データの処理は、そこから決定された画像を表示することにある。
【００２２】
局CTは、たとえば画像再生のための画面ECRと、拡声器とを含むユーザインターフェースIUTを有する。画面ECRに表示された像は、レンダリングエンジンMRによって、ネットワークインターフェースINTCを介して受信されたデータから、また適用可能であれば局CL内のローカルデータベースBLからのデータからも計算される。
【００２３】
例示するため、ユーザインターフェースIUTはさらに、たとえば、画面ECR上の画像として表示されたシーンまたは環境SC内で画面ECR上のカーソルまたは他の要素をユーザが移動させることを可能にするジョイスティックなどのコントロールCOMを含むと仮定する。こうした動作は、画面内のナビゲーションと呼ばれる。シーンSCは2または3次元であり、以下で述べる説明は、3次元のシーンについてである。3次元シーンについて述べる説明はもちろん、対応する適応がなされた2次元シーンに適用することができる。
【００２４】
スクリーンECR上に表示された画像は、カーソルの位置にある観察点Pから見たシーンSCであり、したがってカーソルは、ナビゲーションが行われるごとに画面SC内で移動されると仮定する。ナビゲーションによって画像の再計算が必要となり、画像は、画面ECR上に前に表示された画像に対して修正される。画面SC上で観察点Pが移動され得る空間は、観察(またはナビゲーション)空間EOと呼ばれる。
【００２５】
シーンSCは、存在する複数pのオブジェクトOBJを含み、したがって、オブジェクト空間EOが、オブジェクトOBJの間および周囲のギャップにより形成される。空間EOは、たとえば、すべてのオブジェクトOBJの和集合の補集合に等しい。オブジェクトOBJは、たとえば都市内の建物であり、次いで観察空間EOが、たとえばこれらの建物間に位置する通りにより形成される。
【００２６】
たとえば、オブジェクトOBJは、2.5Dモデル、すなわちフットプリントEMPR、高度ALT、上向きの垂直軸zに沿った高さHによって表されると以下で仮定する。図2および10のように、3次元の物体OBJは、2.5DオブジェクトOBJから、そのフットプリントEMPR上にその高度ALTから高さHのプリズムを立てることによって推定される。観察空間EOは、たとえば地面上に位置しており、場所によって異なる高度を有し得る。
【００２７】
可視性データDVは、オブジェクトに特有の幾何学的データDVOBJを含み、すなわち上記例では、その形状、たとえば高度ALT、高さHなど、フットプリントEMPRのデータを、シーンSC内のオブジェクトOBJの座標、すなわち上記の例ではフットプリントEMPRの座標と共に含む。
【００２８】
可視性データDVは、観察空間EOに特有のデータDVEOをも含む。
【００２９】
局CLは、観察空間EO(たとえばその座標)内の観察点Pの位置に関する情報INFPを含む、シーンSCの新しい画像の表示を求める要求REQVを、チャネルCTを介してサーバSERVに送信する。表示要求REQVは、各ナビゲーションごとに、たとえば、画面ECR上に表示された前の画像に対応する位置である開始位置から、画面ECR上での表示のために画像が再計算されなければならないシーンSC内の別の位置に観察点Pが移動される度に、自動的に送信される。
【００３０】
要求REQVの受信に応答して、サーバSERVのコンピュータCALは、データベースBD内に格納された可視性データDV、および要求REQV内に含まれる観察点Pについての位置情報INFPから、チャネルCTを介して局CLに応答RVで送信されるべき可視性データDEを決定する。このデータDEは、ステップE9の間にパケットで局CLに送信され、この局CLでデータDEが、そのレンダリングエンジンMRおよびそのインターフェースIUTによって処理される。サーバSERVによって計算された応答RVは、サーバSERV内に格納される。
【００３１】
観察空間EOは、データベースBDおよび局CLのローカルデータベースBLの中にそれらの個々の識別子iに関連する事前に計算された座標を有する観察(あるいは表示)点のセルiに分割される。セルは少なくとも2次元である。図2、3、4、5および7で、セルは2次元(2D)であるが、しかし、セルは同様に、図11を参照して以下に述べるように3次元(3D)であることも、図12を参照して以下に述べるように5次元(5D)であることもある。
【００３２】
表示セルiは、図3に示すようにたとえば2次元の三角測量によって得られ、三角形の頂点が、したがってオブジェクトOBJのフットプリントEMPRの角およびシーンSCのエッジ点で頂点SEMPRによって形成された表示セルiを形成する。図3で、太線LIMiは、セルiの境界を表し、したがって、三角形のセルiの辺を形成する直線分からなる。フットプリントと同じように、3次元の表示セルが、三角形上に垂直のプリズムを立てることにより得られる。
【００３３】
表示セルは環境の残りの分についての可視性データを含む環境の領域であり、そのデータは、セル内に位置する観察点に関係なくデータが同一である。表示セルの次元は、観察点の定義の仕方、および観察方向によって推定される。観察点は2次元(2D)、または3次元(3D)で定義されてもよい。可視性計算において観察方向が考慮されていない場合は、表示セルに追加の次元が割り当てられず、それは、観察点の次元、(すなわち2次元または3次元)を有することになる。観察方向が考慮される場合は、その方向を定義するために使用される角度値に対応する1つまたは2つの次元が追加され、2Dシーンでは、方向の定義のために1つの角度が必要とされ、3Dシーンでは、ほとんどの場合に2つの角度が必要とされ、したがって2つの次元が、表示セルのために追加される。
【００３４】
図10、ならびに図3および7で、2Dの表示セルの一例が、三角形によって表されている。次いで、表示セルは、2つの座標を用いて定義された観察点を含んでおり、観察方向は考慮されていない。最も従来的な状況は、観察方向が考慮されない、2次元の表示セルを含む2Dシーンである。図10で、オブジェクト1および3は表示セルから見えており、潜在的可視オブジェクトのリストLOPVを形成している。
【００３５】
図2、3、4、5、7の実施形態において、表示セルは、ベースを形成する三角形上にそれを立てることによって形成されるので、xおよびy軸に沿った2次元を有し、その可視性データは、観察点からのすべての観測方向について計算される。ナビゲーションの高さは、それが地面上でのナビゲーションの状況にあり、計算がこの仮定のもとで実行されるので考慮されない。
【００３６】
図11で、第3の次元が、上記例の表示セルに追加され、可視性情報が、軸zに沿って別の観察点について計算される。次いで、表示セルは、観察空間内の点の高さによって可視性情報が異なるので、3次元の観察点を含む。積み重ねられたプリズムとして提示された表示セルが得られる。最も低い表示セルC1(最も低いプリズムに対応する)は、高さh1未満であるその高度についての可視性を提供し、セルC1の上に位置する表示セルC2(最も高いプリズムに対応する)は、高さh1を超える高度についての可視性を提供する。
【００３７】
図12は、5D表示セルの5次元の座標系を表している。上記で述べたC. Gotsman、O. Sudarsky、J. Faymanによる文献、「Optimized Occlusion Culling Using Five-Dimensional Subdivision」、Computer Graphics、23(5); 645〜654頁、1999年の4頁の第3部で著者は、5次元を有する表示空間(すべての可能な表示半径の空間)、3次元(x、y、z)が観察点の原点を定義し、角度ΘおよびΦがその方向を定義することを考慮している。すべての次元が定義範囲を有することが考慮されよう。それぞれの表示セルは、x1、x2、y1、y2、z1、z2、Φ1、Φ2、Θ1およびΘ2を表示セルの範囲として、観察点P(x1≦X<x2となるようなX、およびy1≦Y<y2となるようなY、z1≦Z<z2となるようなZ)について、また角度ΦおよびΘがΦ1≦Φ<Φ2かつΘ1≦Θ<Θ2となる観察角度についての可視性情報を含む。
【００３８】
データベースBDは、可視性データDVによって、セルiおよびオブジェクトOBJに加えて、各セルiから潜在的に可視であり、事前計算もされているオブジェクトのリストLOPV(i)を含む。
【００３９】
この計算は、Peter Wonka、Michael WimmerおよびDieter Schmalstiegの方法によって、たとえばそれらの文献「Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs」、Proceedings of Eurographic Rendering Workshop、2000年に記載されるように行われる。
【００４０】
本発明によれば、各セルiから潜在的に見えるオブジェクトのリストLOPV(i)を得るために、各セルについて、そのセルに対するオブジェクトの最小の可視の高さのマップが計算される。そのマップは、シーンが占める地面の領域を格子状にし(grid)、各長方形rについて、セルに対して長方形の全体の最小高さHmin(r)を含めることによって得られる。このマップによって、オブジェクトが長方形r内に完全に含まれており、またその高さがHmin(r)未満である場合にはそのオブジェクトがセルから見えないことが保証される。このマップは、可視性行列と呼ばれる2次元の行列MVを用いて表される。次いで、それぞれのオブジェクトが潜在的に見えるかどうかが、オブジェクトの最大の高さを、オブジェクトのフィットプリントEMPRと交差する長方形の最小の高さHmin(r)と比較することにより確認される。完全には閉塞されないオブジェクトは、セルから潜在的に見えるオブジェクトのリストLOPVに追加される。
【００４１】
観察点についての最小の高さHmin(r)の行列MVは、以下のやり方で計算される。
【００４２】
地面に垂直な長方形によってモデル化された観察点および建物のファサード(オブジェクトの特別なケース)について考慮すると、影の体積OMBは、図4に示すように、観察点Pを通過する4つの半直線とファサードの4つの頂点の間で定義される角錐台である。この影の体積OMBによって、この3次元体積OMB内に完全に含まれるどのオブジェクトも観察点Pから見えないことが保証される。したがって、このファサードは、オクルーダファサードと呼ばれる。観察点Pについての最小の高さHmin(r)の行列MVは、行列の各長方形r内の影の体積の高さから推定される。図4では、陰影が付けられた長方形は、2つのファサードO1およびO2によって生成された影の体積OMB表している。したがって、図4からのファサードO1およびO2では、体積OMBの外に位置する長方形r1は、長方形r1に固有の高度の上で0の最小高さHmin(r)を有し、ファサードO1によって生成された影の体積OMBは、O1の影の体積の角錐上を通過し、またその角錐によって定義された位置および形状から計算され得る長方形r2に固有の高度の上で0より大きい最小高さHmin(r2)を有する。
【００４３】
次いで、セルについての関数Hmin(r)は、以下によって示される。
Hmin(r)=min{Hp(r)、pはPEに属する}
上式において、
・PEは、セルの上部面のエッジ上のサンプリング点のセットである。
・Hp(r)=max{Hp, o(r)、oはFOに属する}は、観察点Pに対する長方形rから見える最小の高さを表す関数である。
・FOは、オクルーダファサードのセットを表す。
・Hp, o(r)は、観察点Pに対する長方形rから見える最小の高さを表しており、オクルーダファサードoだけを考慮に入れた関数である。
【００４４】
図5に示すように、最小の高さHmin(r)の行列MVは、可視性水平線HVを計算するために使用される。この可視性水平線HVは、たとえば可視性行列MVのまわりで定義されており、また図5でボックスBiに対して水平線HVの下に投影POBJ1を有するオブジェクトOBJ1について当てはまるように、可視性行列MVによってカバーされる領域の外にあり、またセルiの境界を定めるボックスBiから可視性水平線HVの下に投影されたオブジェクトがそのセルiから見えないことを保証する。
【００４５】
セルiから潜在的に見えるオブジェクトのリストLOPV(i)は、データベースBD内で、論理値1または0を有するブール要素のn行およびp列をを備えた第1の可視性行列Mnpによって表され、この行列では、各行が特定のセルiに対応し、各列jが特定のオブジェクトOBJに対応し、ただし、
・Mnp -1(ai, j)1≦i≦n, 1≦i≦p、
・オブジェクトjがセルiから潜在的に見え、したがってリストLOPV(i)に属する場合は、ai, j=1
・オブジェクトjがセルiから潜在的に見えず、したがってリストLOPV(i)に属さない場合は、ai, j=0、
・n、p、i、jは、自然数である
【００４６】
本発明は、たとえばコンピュータCALによってサーバSERV内のデータベースBDのこの可視性行列Mnpを自動的に圧縮する手段を提供する。
【００４７】
可視性行列のサイズの縮小を可能にする可視性データ圧縮方法の一実施形態について以下に述べる。
【００４８】
本発明の特徴によれば、ステップE7の間、可視性行列Mnpの行iは、隣接行の間の一貫性を増加させ、またはできるだけ大きい一貫性を達成する順序に置かれ、その後に、ステップE8の間に、そのように修正された可視性行列にデジタル画像符号化を適用するために、次いで可視性行列の1および0が、符号化のためデジタル画像のピクセルを形成する。サーバSERVのコンピュータCALは、このための対応するコーダを含む。したがって、その行を移動させることにより可視性行列内に、黒が0で表され、白が1で表現された白黒デジタル画像のように、1で埋まった領域(solid area of 1s)および0で埋まった領域が形成される。
【００４９】
ステップE7を実行するために、可視性行列の行iが多数の共通要素(共通の0および1)を有するかどうか判断される。類似の行が、たとえば行列の2つの行のうちの一部またはすべての可能な組合せに排他的論理和(XOR)演算子を適用することにより検出される。2つの行i1およびi2は、(i1)XOR(i2)が多数の0を有する場合、多数の共通要素を有する。こうした状況で、多数の共通要素を有すると検出された2つの行i1および i2が、それらの間で、行i1と共通したより少ない要素を有する1つまたは複数の行を有する場合、行列の行は、i1およびi2が連続するように並べ替えられる。たとえば、連続した各行について、行列の各後続行との共通要素が検出される。これによって、最多の共通点を有する行がまとめられる。
【００５０】
次いで、このように修正された可視性行列は、デジタル画像コードに従って符号化される。行われる符号化は、アイテムのコンテンツの符号化を可能にする他の任意の符号化とすることができ、また適応可能であってもよい。
【００５１】
デジタル画像符号化に関して、デジタル画像は通常、画像の同じ単一色の領域が、事実上同じ値を有する隣接行内のピクセルによって通常表されるので、隣接行間で何らかの連続性を有する。このデジタル画像符号化は可視性行列に適用され、この符号化はそれ自体、画像ではなく、潜在的に見えるオブジェクトのリストLOPV(i)によって形成されたデータを符号化する。次いで、行列のブール要素は、レベル1あるいはレベル0だけを有し得るピクセルを形成し、このピクセルにデジタル画像処理が適用される。
【００５２】
このデジタル画像符号化は、任意選択によりデジタル画像であり得る、ユーザ局CLの画面ECR上に表示された画像とは全く関係がないが、それがデジタル画像に適用されないことを考慮すると、可視性データコードIまたはデジタル疑似画像コードIを生成する。
【００５３】
このデジタル画像符号化は、たとえば可逆の白黒画像用に設計された、JBIG(Joint Bi-level Image expert Group:共同Bi-レベル画像専門家グループ)タイプのものである。JBIG符号化は実際、符号化される画像のコンテンツを考慮し、以前に符号化されたデータの関数として現在のデータを予測し符号化するために適応演算コーダを使用する。JBIGコーダは、テンプレートと呼ばれる1組のピクセルで符号化されるピクセルの相関性を考慮して、符号化される画像内の冗長性をモデル化する。テンプレートは、たとえば、行内に前の2つのピクセル、および上の行内に、現在のピクセルの上に中心がある5つのピクセルを含み得る。JBIG符号化は、さらに正確な適応テンプレート、および確率的推定器に結合された演算コーダを使用することができ、その両方が非常に高い性能を提供する。
【００５４】
あるいは、行われる符号化は、グラフィック形式のためのものであり、また具体的にはインターネット用に設計されているPNG(Portable Network Graphics:ポータブルネットワークグラフィックス)タイプのものであり得る。
【００５５】
図6を参照して以下で述べる方法の実施形態のように、行を連続して置くステップE7は、可視性行列Mnp上で直接に行われても、可視性行列Mnpと異なる行列Msr上で行われ、そこから得られてもよい。
【００５６】
サーバSERV内で自動的に実行される方法のこの実施形態では、可視性行列Mnpが形成される第1の開始ステップE1の後、シーンSCが領域Rに分割される第2のステップE2が実行される。したがって、これらの領域Rは、図3と同じシーンSCについて図7に表されるように、観察空間EOおよびオブジェクトOBJをカバーする。領域Rは全体としてセルより大きく、したがって、事実上あらゆる領域Rが、複数のセルを少なくとも部分的にカバーする。領域Rは、たとえばシーンSCと関係なく、すべて同じ形であり、具体的には図7では矩形ブロックである。これらの矩形ブロックRは、たとえば図7に示すように、シーンの境界を定めるブロックに平行の辺を有し、平行六面体の(parallelepipedal)ブロックを形成するように垂直に立てられる。図7では、太線LIMRは、これらの矩形ブロックRの範囲を表し、したがって、それらの辺を形成する直線分によって形成される。領域Rの座標は、データベースBD内に格納される。
【００５７】
次いで、ステップE3の間に、要求REQV内に含まれる位置情報INFPに対応する観察点Pが属する領域Rが決定される。この領域は、以下、観察領域RPと呼ばれる。たとえば、xpおよびypが、図7の例の矩形ブロックRの辺に平行の2つの軸xおよびyを有する水平面のデカルト座標内の点Pの横座標および縦座標を表す場合、ブロックRPの座標(xminRP、xmaxRP、yminRP、ymaxRP)は、以下の条件に従って(xP、yP)と比較することによって決定される。
・xminRP≦xp≦xmaxRP、かつ
・yminRP≦yP≦ymaxRP
【００５８】
次いで、ステップE3の間に、セルiの座標、および観察領域RPの座標から、点Pの領域RPとの非ゼロの交差を有する、iRPと示されるセルが決定され、たとえばそれらのセルの数はmであり、ただしmはn以下である。次いで、第1の可視性行列Mnpから、領域RPのm個のセルiRPに対応するMnpのセルによって形成されるm個の行、およびMnpのp個の列を有する第2の可視性行列Mmpが形成される。したがって、行列Mmpは、行列Mnpより遥かに小さい。
【００５９】
次いで、第4のステップE4の間、観察領域RPから見えるオブジェクトOBJのリストTpが、第2の行列Mmpから決定される。したがって、(そのオブジェクトについての行内の1に対応する)セルiRPのうちの1つから見えるオブジェクトjは、このリストTp内にある。リストTpは、たとえば、行列Mmpの行にOR論理演算子を適用することによって得られる。このリストTpは、たとえば、領域RP内のオブジェクトのpビットテーブルで形成され、このテーブル内では、各ビットjは、行列Mmpの列j内に1つまたは複数の1(セルiRPのうちの1つまたは複数から見えるオブジェクトj)が存在する場合は1に等しく、また各ビットjは、行列Mmpの列jが0(セルiRPから見えないオブジェクトj)だけを含む場合は0に等しい。
【００６０】
r≦pとして第3の可視性行列Mmr取得のため、次の行列サイズ縮小ステップE5の間に、観察点Pの領域RPから見えないオブジェクトに対応する、0だけで形成される列jは、ステップE3で決定された第2の行列Mmpから削除される。また、削除された列の位置はマーク付けされる。たとえば、0で形成された列jは、上から下に行識別子1、2、3、4、5、6を有する、m=6行およびp=10列を備えた行列Mmpの例について以下で示す機構を使用して、領域RPから見えるオブジェクトOBJのリストTpの第jの位置にある値0に設定されていると検出される。
【００６１】
【表１】
【００６２】
したがって、この行列では、リストTpは以下に等しい。
【００６３】
【表２】
【００６４】
また、m=6、r=4の場合、第3の可視性行列MMrは、以下に等しい。
【００６５】
【表３】
【００６６】
削除された列は、領域RPから見えるオブジェクトOBJのリストTp内の0の位置により、すなわちj=1、2、4、7、8、9についてマーク付けされている。
【００６７】
次の行列サイズ縮小ステップE6の間、第3の可視性行列Mmrが同一の行iRPを有するかどうか判断される。少なくとも行i3とi4が同一である場合、それらのうちの1つ(i3)だけが、s≦mとする第3可視性行列Mmrから得られる第4の可視性行列Msr内に保持される。同一の行のグループGR=(i3、i4)は、たとえばMmrの2つの行のすべての可能な組合せに排他的論理和(XOR)演算子を適用することによって決定される。(i3)XOR(i4)が0の行である場合、2つの行i3およびi4は同一である。
【００６８】
第3の可視性行列Mmrの同一の行のグループGRの数NGRも計算される。
【００６９】
同一の行iRPの各グループGRについて、グループGRの同一の行i3=i4の数tからなるグループデータアイテムDGRも計算され、その後に、グループGRの同一の識別子i3、i4(識別子iRP)のリストLIDが続く。
【００７０】
図8に示すように、同一の行iRPのグループの数NGRは8ビット上で符号化され、たとえば、各グループデータアイテムDGRの同一の行の各数tが8ビット上で符号化され、グループGRの同一の行の識別子i3、i4の各リストLIDがt*kビット上で符号化され、ただしkは、行すなわちセル識別子i3またはi4を符号化するための固定数のビットである。データアイテムDGRは次々に符号化される。第1のデータアイテムDGR1の後の、第1のグループGR1の第1のデータアイテムDGR1から第2のグループGR2の第2のデータアイテムDGR2への変更は、DGR1の同一の行の数t1、すなわち8ビット長の後に、グループGR1の同一の行の識別子のリストLID1のためのt1*kビットだけがあり、またこれらのt1*kビットの後には、t2をDGR2の同一行の数として、DGR2のt2同一行、すなわち8ビット長が始まり、それに続いて、DGR2の同一行の識別子のt2*kビットのリストLID2のt2*kビットがあることが予想されるので復号される。
【００７１】
したがって、上記の例では、
・NGR=2
・DGR=(2、1、5、2、3、6)
t1=2、LID1=1、5(Mmrの第1と第5の行が同一)ではDGR1=(2、1、5)
t2=2、LID2=3、6(Mmrの第3と第6の行が同一)ではDGR2=(2、3、6)
・Msr(s=4、r=4であり、またMmrの行1および6を削除し、上から下に識別子2、3、4、5の行を保持した後)は、以下に等しい。
【００７２】
【表４】
【００７３】
次いで、第5の可視性行列M'srを得るために、上述の行を第4の可視性行列Msr内に連続して置くステップE7が実行され、デジタル疑似画像コードiを得るために、上述のデジタル画像符号化ステップE8が第5の可視性行列M'srに適用される。この第5の可視性行列M'srは、元の第1の可視性行列Mnpに対して修正された可視性行列M'srと呼ばれる。
【００７４】
第5の可視性行列M'sr内の連続した行i1、i2のs個の識別子iRPは、第5の行列M'sr内のそれらの出現順で(たとえば上から下に)、この第5の行列M'srのデジタル画像符号化のために連続して置かれたセルの識別子i1、i2のリストと呼ばれるリストLIOC、または修正済み可視性行列M'srのセルの識別子i1、i2のリストLIOC内に格納される。連続して置かれたセルの識別子のこのリストLIOCは、グループGRの同一のセルのリストLIDとは異なる。連続して置かれたセルの識別子のリストLIOCは、s*kビット上で符号化され、ただしkは、行あるいはセル識別子i1またはi2を符号化するための固定数のビットである。
【００７５】
上記の例の行列Msrに適用され、ステップE7は、たとえば、以下の可視性行列M'sr、
【００７６】
【表５】
【００７７】
すなわち、上から下に、Mmp、MmrおよびMsrの行2、3、4、5の識別子3、5、4、2の順序をもたらす。したがって、LIOC=(3, 5, 4, 2)である。
【００７８】
この行列M'srは、以下の1で埋まった領域を含む。
【００７９】
【表６】
【００８０】
ステップE3、E4、E5、E6、E7、E8、E9は、要求REQV内で示された各観察点P、および観察点Pが属すると判断された各領域RPについて実行される。適切であれば、ステップE5およびE6の順序は逆にされてもよい。
【００８１】
応答RVのデータDEは、観察領域RPから見えるオブジェクトOBJに関するデータDVOBJに等しい、データベースBDからの幾何学的データDGEなど、可視性データDVEを含む(図1参照)。このデータDGEは、サーバSERVのコンピュータCALによって、たとえば領域RPから見えるオブジェクトOBJのリストTpを使用して、ステップE4またはE5の間にデータベースBDからのデータDVOBJ内で選択される。
【００８２】
可視性データDVEは、符号化ステップE8の後、サーバSERVのコンピュータCALによって決定され、図8では、
・観察点Pの領域RPから見えるオブジェクトOBJのリストTpと、
・同一の列のグループGRの数NGRと、
・同一の列のグループのデータDGR(1、LID)と、
・第5の行列M'sのデジタル画像符号化のために連続して置かれたセルの識別子i1、i2のリストLIOCと、
・ステップE8によるデジタル画像符号化により符号化された第5の行列M'srに等しいデジタル疑似画像符号Iとを含んでいる。
【００８３】
以下の表は、上述の圧縮方法のテストの結果を示している。これらのテストは、5750個のオブジェクトおよび29153個の表示セルの仮想都市を定義するデータベースBDに対して実施されたものである。
【００８４】
【表７】
【００８５】
したがって、本発明の方法によって、従来技術の可逆符号化から開始したテスト1に従って行われる可逆符号化よりも、テスト2に従って可視性データのより可逆的な圧縮が可能になることが明らかである。
【００８６】
可視性データDVEを含む応答RVを受信した後、ユーザの局CLは、図9に示すやり方で可視性データDVEを圧縮解除する。このために、局CLは、データDVEを自動的に圧縮解除する手段たとえばコンピュータCAL2を含む。
【００８７】
観察領域RPの第2の可視性行列Mmpが、前の要求REQV(INFP)に関連して受信されるそれぞれの応答RVについて得られることを可能にする可視性データDVE圧縮方法の一実施形態について以下に述べる。この実施形態は、たとえばコンピュータCAL2のデコーダ内で実施される。
【００８８】
局CLは、観察点Pの領域RPから見えるオブジェクトOBTのリストTpがpビット上で符号されており、同一の行のグループGRの数が8ビット上で符号化されており、同一の行のグループのGRの数NGRが8ビット上で符号化されており、同一のグループのデータアイテムDGR(t、LID)のそれぞれが8ビット+t.kビット上で符号化されており、連続して置かれたセルi1、i2の識別子のリストLIOCがs*kビット上で符号化されている事実を記憶しており、リストTp、数NGR、データアイテムDGR(t、LID)、リストLIOCおよびデジタル疑似画像符号Iを、受信された応答RVから抽出し、第1の抽出ステップE11の間にそれらをそのローカルデータベースBL内に格納する。応答RVからのオブジェクトのデータDGEも、ローカルデータベースBL内に格納される。
【００８９】
圧縮解除プロセスの第2のステップE12の間、m行およびp列を有する第6のブール行列Mmp0が構築され、mおよびpが、応答RVのデータDVEから、すなわちpについてのリストTp、およびグループGRの同一の行の識別子i3、i4のリストLIDから、またmについて連続して置かれたセルi1、i2の識別子のリストLIOCから決定される。
【００９０】
次いで、可視オブジェクトのリストTpの0の位置にある行列Mmp0内の0に設定される列の位置が、リストTpから推定される。
【００９１】
したがって、上記の例では、m=6、p=10について、以下の行列Mmp0が得られる。
【００９２】
【表８】
【００９３】
次いで、コードIは、ステップE13の間に局CL内で、ステップE8でサーバSERV内で実施されたデジタル画像符号化の逆であるデジタル画像復号によって復号され、この復号の特徴は、局CLのメモリ内に存在している。したがって、この復号によって、ステップE7から、第5の可視性行列M'srが生成される。
【００９４】
次のステップE14の間、第7の行列Mmp0'を得るために、第5の可視性行列M'srの列が、可視オブジェクトのリストTpの1の位置、すなわち上記例では0の列で埋められていない位置にある、第6の行列Mmp0の空いた列に移される。この充填は、第5の行列M'srの列、および第6の行列Mmp0の空の列について同じ順序で行われる。第5の行列M'srが第6の行列Mmp0より小さい数sの行を有することを考慮して、M'srから来る第6の行列Mmp0内の第1のs個の行だけが埋められる。
【００９５】
連続して置かれたセルの識別子i1、i2のリストLIOCは、このようにして埋められた第7の行列Mmp0'の第1のs個の行の識別子を示している。したがって、埋められた、Mmp0の行の識別子がリストLIOCから知られているので、ステップE7で行われるものと逆の置換を行う必要はない。
【００９６】
したがって、上記の例では、ステップE14によって局CL内で以下の第7の行列Mmp0'が生成され、この第7の行列Mmp0では第3、第5、第6および第10の列が、LIOCのリストに従って、Mnpのセル3、5、4、2に対応する、S=4の第1の行でM'srによって埋められる。
【００９７】
【表９】
【００９８】
次のステップE15で、第8の行列Mmp'を得るために、同一の列のグループの数NGRによって定義された複製された列、およびグループのデータアイテムDGR(t、LID)が、ステップE14で得られた第7の行列Mmp0'に追加される。追加される行は、埋められていない第7の行列Mmp0'の行に取って換わる。ステップE6で、データDGRは、以下に示すやり方で、データDGR内に含まれる同一の行のグループの数NGR、および同一の行の数t、ならびに同一の行の識別子のリストLIDを使用して復号される。
【００９９】
したがって、上記の例では、行列Mmp'を形成するために行列Mmp0'に、DGR1によるMmp0'の識別子5を有する行に等しい識別子1を有する行、およびDGR2によるMmp0'の識別子3を有する行に等しい識別子6を有する行、すなわち下から上に識別子3、5、4、2、1、6を備えたセルを有する以下の行列Mmp'の最後の2つの行が追加され、したがって、それは以下の行列Mmpに対応する。
【０１００】
【表１０】
【０１０１】
局CLは、ステップE15によって得られた第8の行列Mmp'を、そのローカルデータベース内に格納する。
【０１０２】
次のステップE16で、局CLは、観察点Pが属する第8の行列Mmp'のセルiRPを、ローカルデータベースBL内に存在するセルiの座標および識別子から、また前の要求REQVを送信するためにコンピュータCAL2によって決定され、また送信された要求REQVと共にローカルデータベースBL内に格納された観察点Pの位置情報INFPから決定する。次いで、このように検出された点Pのセルiは、たとえばローカルデータベースBL内に識別子iPを有する。
【０１０３】
次いで、コンピュータCAL2は、データベースBLの第8の行列Mmp'内のセルiPに対応する行の位置を、この識別子iP、およびローカルデータベースBLに格納された、連続して置かれたセルi1、i2の識別子のリストLIOCから決定する。
【０１０４】
コンピュータCAL2は、ベースBLの第8の行列Mmp'の行iPをスキャンすることにより、観察点Pから見えるオブジェクトのリストLOPV(iP)を得る。
【０１０５】
次いで、局CLは、ステップE17で、観察点Pから見えるオブジェクトOBJを表す対応する画像を画面ECR上に表示するため、観察点Pから見えるオブジェクトのリストLOPV(iP)、および対応するオブジェクトのデータDVOBJを使用し、この画像は、このリストLOPV(iP)内で1が現れるデータDVOBJによって定義されたオブジェクトを表しており、このリストLOPV(iP)内で0が現れるデータDVOBJによって定義されたオブジェクトである、観察点Pから見えないオブジェクトOBJは表していない。
【０１０６】
次いで、局CLのユーザは、観察点Pを新しい点P2に移動させることができる。観察点Pを空間EO内の新しい位置INFP2に置き換える度に、新しい観察点P2が、ローカルベースBL内に格納された行列Mmp'内に既に存在するセル内にあるかどうかが局CL内で自動的に決定される。そうである場合は、この行列Mmp'のこのセルiRPについてステップE16を再び、またステップE17を実行するために、対応するMmp'が、局CLのベースBL内で探し求められる。そうでない場合は、局CLは、新しい観察点P2の位置情報INFP2を含む新しい要求REQV2をサーバSERVに送信し、サーバSERVは、上述したように新しい応答RV2を返送する。それぞれの新しい応答RV2について、サーバSERVは、その新しい応答RV2内に挿入されるデータDGEが前の応答RVで既に送信されているかどうか判断し、そうである場合は、サーバSERVは新しい応答RV2において、既に送信されたこのデータDGEを送信しない。そうではなく、それは新しい応答RV2において、まだ送信されていないデータDGEだけを送信し、それによって、新しい応答RV2内で送信されるデータの量がさらに減少される。
【０１０７】
同様に、観察点Pを空間EO内の新しい位置INFP2に置き換える度に、新しい観察点P2が、点Pについての前の画像の表示を可能にした前の応答RVにより得られた第8の行列Mmp'内に既に存在するセルiRP内にあるかどうかが局CL内で自動的に判断される。そうである場合は、新しい点P2を求める新しい要求REQV2を送信する必要はない。次いで、新しい観察点P2についてのリストLOPV(iP2)は、前の観察点PについてのリストLOPV(iP)と比較して補足のオブジェクトのリストLOPV(iP2)+を追加し、前の観察点PについてのリストLOPV(iP)と比較して欠落しているオブジェクトのリストLOPV(iP2)-を削除することによって、前の観察点PについてのリストLOPV(iP)から推定されることができる。この2つのリストLOPV(iP2)+およびLOPV(iP2)-は局CL内において、これらのリストの間で異なるオブジェクト((LOPV(iP))XOR(LOPV(iP2))において1で示される)のリストを取るために、点Pについて得られる前の行列Mmp'のリストLOPV(iP)およびLOPV(iP2)から、たとえばそれらに排他的論理和演算子を適用することによって計算される。これによって、非常に長いかもしれないリストLOPV(iP2)の全体をスキャンする必要性が回避される。
【０１０８】
あるいは、可視性データは、システムSERVが観察点位置情報INFPを受信する前に、領域Rのそれぞれについて、たとえば行列M'srの形で事前に圧縮される。
【０１０９】
コンピュータプログラムが、たとえばシステムSERVの上の圧縮プロセスおよびユニットCLの上の圧縮解除プロセスを実行するために、システムSERVおよびユニットCL上にインストールされる。
【図面の簡単な説明】
【０１１０】
【図１】本発明によるデータ圧縮および圧縮解除方法が実施される、クライアントサーバ装置を表す図である。
【図２】2.5次元での3次元オブジェクトモデル化を表す図である。
【図３】オブジェクト、およびそれらのオブジェクトの表示セルを含むシーンを上から示す図である。
【図４】潜在的に見えるファサードの背後のオブジェクトのリストを計算するために使用され得る、オクルーダファサードによって生成された影の体積を上から示す図である。
【図５】図4に示す計算方式によって生成された可視性水平線の透視図である。
【図６】本発明よる可視性データ圧縮方法の一実施形態のフローチャートである。
【図７】オブジェクトを含んでおり、領域に分割された図3からのシーンを上から示す図である。
【図８】図6による圧縮方法によって圧縮された可視性データの構造を表す図である。
【図９】本発明の可視性データ圧縮解除方法の一実施形態のフローチャートを表す図である。
【図１０】2次元シーンの表示セルを表す図である。
【図１１】3次元シーンの表示セルを表す図である。
【図１２】5Dシーンの表示セルの5つの次元を表す図である。
【符号の説明】
【０１１１】
ALT 高度
BD データベース
Bi ボックス
BL データベース
CAL、CAL1、CAL2 コンピュータ
CL 局
COM コントロール
CT 通信チャネル
C1、C2 表示セル
DE 可視性データ
DGE 幾何学的データ、
DGR データアイテム
DV 可視性データ
DVE 可視性データ
DVEO データ
DVOBJ 幾何学的データ
ECR 画面
EMPR フットプリント
EO 空間
E1〜E17 ステップ
GR グループ
H 高さ
HV 可視性水平線
I デジタル疑似画像コード/可視性データコード
i、i1、i2 行/セル/識別子
i3、i4 行/識別子
INFP 位置情報
INTC ネットワークインターフェース
INTS ネットワークインターフェース
iRP 行/セル/識別子
IUT ユーザインターフェース
LID リスト
LIMi 太線
LIMR 太線
LIOC リスト
NGR 数
LOPV、LOPV(i) リスト
MR レンダリングエンジン
Mnp 第1の可視性行列
Mmp 第2の可視性行列
Mmr 第3の可視性行列
Msr 第4の可視性行列
M'sr 第5の可視性行列
Mmp0 第6の行列
Mmp0' 第7の行列
MV 行列
OBJ オブジェクト
OMB 影の体積
O1、O2 ファサード
P 観察点
POBJ1 投影
R 領域/矩形ブロック
r 長方形
REQV 要求
RP 観察領域
RV 応答
SC 環境/シーン
SEMPR 頂点
SERV サーバ/データ処理システム
Tp リスト
x 軸
y 軸
z 軸
【技術分野】
【０００１】
本発明は、可視性データベースからの可視性データの圧縮方法および圧縮解除方法、ならびにこれらの方法を実施するためのシステムに関する。
【背景技術】
【０００２】
本発明の適用分野は、たとえばシミュレーションやゲーム内のシーン内で移動する観察点からそのシーンのオブジェクトを表示することであり、そこでは観察点は、シーン内で移動するユーザの仮想観察点である。
【０００３】
オブジェクトは一般に事前に定義されており、観察点はその環境内で移動可能であり、この環境では、オブジェクトが様々な角度で見られ、オブジェクトが閉塞され(occlude)、または以前に閉塞された新しいオブジェクトが現れるので、画面上に表されるオブジェクトの外観を変化させるべきである。
【０００４】
オブジェクトを表示するときに生じる問題の1つは、観察点が移動する度に考慮されるべきデータが大量であることであり、この観察点は、ユーザの制御のもと非常に速く移動されることがある。
【０００５】
Peter Wonka、Michael WimmerおよびDieter Schmalstiegによる文献、「Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs」、Proceedings of Eurographic Rendering Workshop、2000年は、観察空間を表示セル(viewing cell)に分割し、オクルーダオブジェクトを量εだけ縮小し、各セルについてその十分な数のサンプリング点を決定し、そのセルから潜在的に見えるオブジェクトのセットを得るために各サンプリング点について可視性を計算することを提案している。
【０００６】
しかし、それらの潜在的可視オブジェクトのセットは、各セルごとに存在しており、非常に大量のデータである。
【０００７】
Michiel van de PanneおよびA. James Stewartによる文献、「Effective Compression Techniques for Precomputed Visibility」、Rendering Techniques 1999、305〜316頁、1999年は、観察点空間を小さい領域またはセルに分割し、ブール(Boolean)可視性テーブルを構築し、予備の計算ステップで事前に決定された情報を符号化し、各領域からどの多角形が見えるか示すことを提案している。その可視性テーブルでは、それぞれの行は観察点のセルに対応し、それぞれの列は、多角形に対応する。可視性テーブルの行i、列jに位置するいずれのエントリも、多角形jが領域iの点から少なくとも潜在的に可視である場合、かつその場合に限り、真の状態にある。可視性テーブルを圧縮するために、不可逆圧縮アルゴリズムでは、真エントリの類似のセットを有する行および列を併合する。別の、今度は可逆である圧縮アルゴリズムでは、共通のエントリを有する行から得られる新しい行および列を可視性テーブルに追加する。したがって、第1のアルゴリズムでは情報が失われ、または可視性テーブルは大き過ぎるままとなる。さらに、それらのアルゴリズムは、ネットワーク化された表示、すなわち可視性データを格納するデータベースから離れたユーザ局上での表示には適していない。
【０００８】
以下の文献を引用することもできる。
・C. Gotsman、O. SudarskyおよびJ. Fayman、「Optimized Occlusion Culling Using Five-Dimensional Subdivision」、Computer Graphics、23(5): 645〜654頁、1999年。この文献は、空間を5次元階層の可視性ツリー構造に編成する閉塞ソートアルゴリズム(occlusion sorting algorithm)について記載しており、この階層ではツリーの各葉が、より低いレベルの葉のうちの1つへの参照を含む。葉の第i位置の真の値は、その葉に第iのオブジェクトが存在することを示すものであり、偽の値は、その葉、またはそれより下のレベルの葉にそのオブジェクトが存在しないことを示すものである。そのアルゴリズムの欠点は、それぞれの観察点についてツリーがトラバースされなければならないことである。それは、可視性データを格納するデータベースから離れたユーザ局上でのネットワーク化された表示には適していない。
・Boaz Nadler、Gadi Fibish、Shuly Lev-YehudiおよびDanile Cohen-Or、「A qualitative and quantitative visibility analysis in urban scenes」、Computer & Graphics、23(5): 655〜666頁、1999年。この文献は、所与のオブジェクトが所与の表示セルから見える確率を、そのセルに対する距離の関数として計算する。隣接セルについての潜在的可視オブジェクトセットの交差がセル内で推定され、複製の数を減少させるためデータを階層構造に格納するために、セル間の一貫性が活用される。しかし、データの量は、大き過ぎるままである。
・Christopher ZachおよびKonrad Karner、「Progressive compression of visibility data for view-dependent multiresolution meshes」、Journal of WSCG、11巻、3号、546〜553頁、2003年。この文献は、可視性情報が多解像度構造のノードに直接格納されることができ、また可視性データの必要な部分だけが送信される圧縮方法を提案している。その方法では、最初に送信されなかった新しいデータの到着を待つことが必要であるので、見えるオブジェクトのすべてが毎回決定されるとは限らず、それによって、この方法に望ましくない待ち時間が生じることになる。
・V. Koltun、Y. ChrysanthouおよびD. Cohen-Or、「Virtual Occluders: An Efficient Intermediate PVS Representation」、Eurographics Workshop on Rendering、59〜70頁、Eurographics、2000年。この文献は、それらの仮想オクルーダを使用して表示セルについて潜在的可視セット(PVS: potentially visible set)を作成するために、その表示セルについての仮想オクルーダを定義することに限定しているが、しかし、取得されるデータが大量であることの問題には対処していない。
・Fabio O. Moreira、Joao L.D. CombaおよびCarla M. D. S. Freitas、「Smart Visible Sets for Networked Virtual Environments」、SIBGRAPI 2002。この文献は、潜在的可視セット(PVS)の情報を、位置を考慮した動的サブセットに分割したものに対応する、スマート可視セット(SVS: smart visible set)を定義している。分類機構は、最重要と分類されたデータだけが送信されることを可能にする。したがって、データの損失が生じる。その技術は、非常に大きいデータベース、またはネットワーク状況においてはテストされていない。
【非特許文献１】Peter Wonka、Michael Wimmer、Dieter Schmalstieg、「Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs」、Proceedings of Eurographic Rendering Workshop、2000年
【非特許文献２】Michiel van de Panne、A. James Stewart、「Effective Compression Techniques for Precomputed Visibility」、Rendering Techniques 1999、305〜316頁、1999年
【非特許文献３】C. Gotsman、O. Sudarsky、J. Fayman、「Optimized Occlusion Culling Using Five-Dimensional Subdivision」、Computer Graphics, 23(5): 645〜654頁、1999年
【非特許文献４】Boaz Nadler、Gadi Fibish、Shuly Lev-Yehudi、Danile Cohen-Or、「A qualitative and quantitative visibility analysis in urban scenes」、Computer & Graphics、23(5): 655〜666頁、1999年
【非特許文献５】Christopher Zach、Konrad Karner、「Progressive compression of visibility data for view-dependent multiresolution meshes」、Journal of WSCG、11巻、3号、546〜553頁、2003年
【非特許文献６】V. Koltun、Y. Chrysanthou、D. Cohen-Or、「Virtual Occluders: An Efficient Intermediate PVS Representation」、Eurographics Workshop on Rendering、59〜70頁、Eurographics、2000年
【非特許文献７】Fabio O. Moreira、Joao L. D. Comba、Carla M. D. S. Freitas、「Smart Visible Sets for Networked Virtual Environments」、SIBGRAPI 2002
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、従来技術の欠点を緩和し、また大部分が可逆でありながら圧縮データのサイズを著しく減少させる可視性データ圧縮方法を提供することである。
【課題を解決するための手段】
【００１０】
この目的のため、本発明は第1に、可視性データベースからの可視性データを圧縮する方法を提供し、
・可視性データが、所定のオブジェクトを観察するための観察空間内の観察点のセルと、観察点の各セルについて、観察点のそのセルから潜在的に見える前記所定のオブジェクトの中からのオブジェクトのリストとを含み、
・可視性データがデータベース内で少なくとも、各行がセルに対応し、各列が前記所定のオブジェクトのうちの1つに対応するブール要素の第1の可視性行列の形で表され、ブール要素がそれぞれ、オブジェクトjが、セルiに関連する潜在的可視オブジェクトのリストに属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
・多数の共通要素を有しており、隣接していない可視性行列内の行をデータベース内で自動的に検出し、修正済み可視性行列の形成のため、多数の共通要素を有すると検出された行を連続して置くようにこうしたいずれの行をも並べ替えること、および
・可視性データコードの取得のため、修正済み可視性行列のブール要素にデジタル画像符号化を自動的に適用することであって、修正済み可視性行列のこれらのブール要素が、符号化のためデジタル画像のピクセルを形成することを特徴とする方法を提供する。
【００１１】
本発明の他の特徴によれば、
・可視性データベースがデータ処理システムに関連付けられ、前記システムが、生成された可視性符号化データを可視性データ処理ユニットに送信し、
・データ処理システムがデータサーバであり、可視性データ処理ユニットが可視性データ処理局であり、
・データ処理システムおよび可視性データ処理ユニットが同じ可視性データ処理局内に設けられ、
・データ処理システムが、観察空間内の特定の観察点の位置に関する情報を処理ユニットから事前に受信しており、観察空間が可視性データベース内で領域に分割され、以下の諸ステップ、すなわち
・ユニットから受信された位置情報に対応する観察点が属する観察空間の領域の中から観察領域を決定するステップと、
・観察領域との交差を有する可視性データのセルの中から第1のセルを決定するステップと、
・決定された観察領域の前記第1のセルに対応する第1の可視性行列の行でその行が形成される第2の可視性行列を、第1の可視性行列から抽出するステップと、
・第2の可視性行列から修正済の可視性行列を形成するステップと、
・観察領域から潜在的に見えるオブジェクトのリストが、データ処理システム内で第2の可視性行列から自動的に決定され、データ処理システムによって可視性データコードを付けて処置ユニットに送信されるステップと、
・修正済の可視性行列のセルの識別子のリストが、データ処理システムによって可視性データコードを付けて処理ユニットに送信されるステップと、
・同一の行のグループごとに1つの行だけを第4の可視性行列内に保持するために、可視性行列の同一の列がデータ処理システムで自動的に決定され、修正済の可視性行列が第4の可視性行列から形成され、可視性行列の同一の行のグループの数であるデータアイテムが、データ処理システム内で自動的に計算され、同一の行の各グループについてグループデータアイテムが、グループの複数の同一行と、前記グループの同一の行の識別子のリストを含み、同一行のグループの数である前記データアイテム、および前記グループデータアイテムが、データ処理システムによって可視性データコードを付けて処理ユニットに送信されるステップと、
・同一の行の各グループについて、前記グループの同一の行の数が、所定の数のビット上で符号化され、前記グループの前記リストからの同一の行の各識別子が、所定の数のビット上で符号化され、各グループデータアイテムが、すべてのグループについて所定の順序において、グループの同一の行の前記数、およびグループの同一の行の前記識別子のリストからなるステップと、
・可視性行列内に少なくとも1つの0の列が自動的に検出され、修正済の可視性行列がそこから形成される第3の可視性行列を形成するため、検出されたいずれのこうした0の列もが可視性行列から自動的に削除されるステップと、
・修正済の可視性行列のブール要素に適用される前記デジタル画像符号化が、JBIGまたはPNGタイプのものであるステップとがデータ処理システム内で自動的に実行される。
【００１２】
本発明は第2に、デジタル画像復号が、生成された可視性データコードに適用されることを特徴とする、上述したような可視性圧縮方法によって生成された可視性データコードを圧縮解除する方法を提供し、その復号は、前記圧縮方法によって適用されるデジタル画像符号化の逆であり、復号により可視性行列がもたらされる。
【００１３】
この圧縮解除方法の他の特徴によれば、
・0の列が、前記デジタル画像復号によって得られた可視性行列に、観察領域から潜在的に見えるオブジェクトのリストによって示された潜在的に見えないオブジェクトの位置で自動的に追加され、
・前記デジタル画像復号によって得られた可視性行列に、グループデータアイテムの同一の行の識別子のリスト内には存在し、前記可視性行列には存在しない、同一の行の識別子によって示された少なくとも1つの欠落した行が自動的に追加され、次いで、その少なくとも1つの欠落した行が、同一の行の識別子の前記リスト内に存在する識別子を有する可視性行列の行に等しい。
【００１４】
本発明は、上述したような可視性データ圧縮解除方法を実行する手段を含むデコーダをも提供する。
【００１５】
本発明は、可視性データベースに関連するシステムをさらに提供し、
・可視性データが、所定のオブジェクトを観察するための観察空間内の観察点のセルと、観察点の各セルについて、観察点のそのセルから潜在的に見える前記所定のオブジェクトの中からのオブジェクトのリストとを含み、
・可視性データがデータベース内で少なくとも、各行がセルに対応し、各列が前記所定のオブジェクトのうちの1つに対応するブール要素の第1の可視性行列の形で表され、ブール要素がそれぞれ、オブジェクトjが、セルiに関連する潜在的可視オブジェクトのリストに属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
前記システムが、上述したような可視性データ圧縮方法を実行する手段を含む。
【００１６】
本発明は、コンピュータ上で実行されるときに、上記で述べたデータ圧縮方法を実施する命令を含むコンピュータプログラムをさらに提供する。
【００１７】
本発明は、コンピュータ上で実行されるときに、上記で述べたデータ圧縮解除方法を実施する命令を含むコンピュータプログラムをさらに提供する。
【００１８】
本発明は、非限定的な例としてのみ示された以下の説明を読み、添付の図面を参照してよりよく理解することができる。
【発明を実施するための最良の形態】
【００１９】
本発明について、オブジェクトを表示するための装置からなる一実施形態において、たとえばサーバSERVがデータベースBD内でオブジェクトについての可視性データDVをホストするクライアントサーバアーキテクチャを使用して以下に述べる。オブジェクトは、実際または抽象のオブジェクトをモデル化する幾何学的データセットDVOBJに対応する。そのコンピュータCAL内にデータ処理手段を含むサーバSERVは、データ処理システムSERVをも形成する。サーバSERVから離れたユーザの局CLは、それに要求を送信するため通信チャネルCTによってそれに接続され、したがって、この局CLがデータ処理ユニットを構成する。サーバSERVは、チャネルCT上で局CLにこれらの要求への応答を送信する。チャネルCTは、1つまたは複数の通信ネットワークを横断し、このために、たとえばサーバSERVおよび局CLのそれぞれに、ネットワークインターフェースINTS、INTCが設けられる。
【００２０】
もちろん、示されていない他の実施形態において、データベースBDおよびデータ処理システムSERVは、局CLと同じマシン、たとえばユーザのコンピュータ上に存在することもできる。次いで、たとえばデータベースBDは、コンピュータの大容量メモリ、たとえばハードディスク内に、または取出し可能記憶媒体、たとえばコンピュータの対応する読取り装置内に挿入されたCD-ROM内にあることがあり、圧縮データは、コンピュータ内のユニットによってそれができるだけ速く処理され得るように生成されなければならない。
【００２１】
以下では、圧縮された可視性データの処理は、そこから決定された画像を表示することにある。
【００２２】
局CTは、たとえば画像再生のための画面ECRと、拡声器とを含むユーザインターフェースIUTを有する。画面ECRに表示された像は、レンダリングエンジンMRによって、ネットワークインターフェースINTCを介して受信されたデータから、また適用可能であれば局CL内のローカルデータベースBLからのデータからも計算される。
【００２３】
例示するため、ユーザインターフェースIUTはさらに、たとえば、画面ECR上の画像として表示されたシーンまたは環境SC内で画面ECR上のカーソルまたは他の要素をユーザが移動させることを可能にするジョイスティックなどのコントロールCOMを含むと仮定する。こうした動作は、画面内のナビゲーションと呼ばれる。シーンSCは2または3次元であり、以下で述べる説明は、3次元のシーンについてである。3次元シーンについて述べる説明はもちろん、対応する適応がなされた2次元シーンに適用することができる。
【００２４】
スクリーンECR上に表示された画像は、カーソルの位置にある観察点Pから見たシーンSCであり、したがってカーソルは、ナビゲーションが行われるごとに画面SC内で移動されると仮定する。ナビゲーションによって画像の再計算が必要となり、画像は、画面ECR上に前に表示された画像に対して修正される。画面SC上で観察点Pが移動され得る空間は、観察(またはナビゲーション)空間EOと呼ばれる。
【００２５】
シーンSCは、存在する複数pのオブジェクトOBJを含み、したがって、オブジェクト空間EOが、オブジェクトOBJの間および周囲のギャップにより形成される。空間EOは、たとえば、すべてのオブジェクトOBJの和集合の補集合に等しい。オブジェクトOBJは、たとえば都市内の建物であり、次いで観察空間EOが、たとえばこれらの建物間に位置する通りにより形成される。
【００２６】
たとえば、オブジェクトOBJは、2.5Dモデル、すなわちフットプリントEMPR、高度ALT、上向きの垂直軸zに沿った高さHによって表されると以下で仮定する。図2および10のように、3次元の物体OBJは、2.5DオブジェクトOBJから、そのフットプリントEMPR上にその高度ALTから高さHのプリズムを立てることによって推定される。観察空間EOは、たとえば地面上に位置しており、場所によって異なる高度を有し得る。
【００２７】
可視性データDVは、オブジェクトに特有の幾何学的データDVOBJを含み、すなわち上記例では、その形状、たとえば高度ALT、高さHなど、フットプリントEMPRのデータを、シーンSC内のオブジェクトOBJの座標、すなわち上記の例ではフットプリントEMPRの座標と共に含む。
【００２８】
可視性データDVは、観察空間EOに特有のデータDVEOをも含む。
【００２９】
局CLは、観察空間EO(たとえばその座標)内の観察点Pの位置に関する情報INFPを含む、シーンSCの新しい画像の表示を求める要求REQVを、チャネルCTを介してサーバSERVに送信する。表示要求REQVは、各ナビゲーションごとに、たとえば、画面ECR上に表示された前の画像に対応する位置である開始位置から、画面ECR上での表示のために画像が再計算されなければならないシーンSC内の別の位置に観察点Pが移動される度に、自動的に送信される。
【００３０】
要求REQVの受信に応答して、サーバSERVのコンピュータCALは、データベースBD内に格納された可視性データDV、および要求REQV内に含まれる観察点Pについての位置情報INFPから、チャネルCTを介して局CLに応答RVで送信されるべき可視性データDEを決定する。このデータDEは、ステップE9の間にパケットで局CLに送信され、この局CLでデータDEが、そのレンダリングエンジンMRおよびそのインターフェースIUTによって処理される。サーバSERVによって計算された応答RVは、サーバSERV内に格納される。
【００３１】
観察空間EOは、データベースBDおよび局CLのローカルデータベースBLの中にそれらの個々の識別子iに関連する事前に計算された座標を有する観察(あるいは表示)点のセルiに分割される。セルは少なくとも2次元である。図2、3、4、5および7で、セルは2次元(2D)であるが、しかし、セルは同様に、図11を参照して以下に述べるように3次元(3D)であることも、図12を参照して以下に述べるように5次元(5D)であることもある。
【００３２】
表示セルiは、図3に示すようにたとえば2次元の三角測量によって得られ、三角形の頂点が、したがってオブジェクトOBJのフットプリントEMPRの角およびシーンSCのエッジ点で頂点SEMPRによって形成された表示セルiを形成する。図3で、太線LIMiは、セルiの境界を表し、したがって、三角形のセルiの辺を形成する直線分からなる。フットプリントと同じように、3次元の表示セルが、三角形上に垂直のプリズムを立てることにより得られる。
【００３３】
表示セルは環境の残りの分についての可視性データを含む環境の領域であり、そのデータは、セル内に位置する観察点に関係なくデータが同一である。表示セルの次元は、観察点の定義の仕方、および観察方向によって推定される。観察点は2次元(2D)、または3次元(3D)で定義されてもよい。可視性計算において観察方向が考慮されていない場合は、表示セルに追加の次元が割り当てられず、それは、観察点の次元、(すなわち2次元または3次元)を有することになる。観察方向が考慮される場合は、その方向を定義するために使用される角度値に対応する1つまたは2つの次元が追加され、2Dシーンでは、方向の定義のために1つの角度が必要とされ、3Dシーンでは、ほとんどの場合に2つの角度が必要とされ、したがって2つの次元が、表示セルのために追加される。
【００３４】
図10、ならびに図3および7で、2Dの表示セルの一例が、三角形によって表されている。次いで、表示セルは、2つの座標を用いて定義された観察点を含んでおり、観察方向は考慮されていない。最も従来的な状況は、観察方向が考慮されない、2次元の表示セルを含む2Dシーンである。図10で、オブジェクト1および3は表示セルから見えており、潜在的可視オブジェクトのリストLOPVを形成している。
【００３５】
図2、3、4、5、7の実施形態において、表示セルは、ベースを形成する三角形上にそれを立てることによって形成されるので、xおよびy軸に沿った2次元を有し、その可視性データは、観察点からのすべての観測方向について計算される。ナビゲーションの高さは、それが地面上でのナビゲーションの状況にあり、計算がこの仮定のもとで実行されるので考慮されない。
【００３６】
図11で、第3の次元が、上記例の表示セルに追加され、可視性情報が、軸zに沿って別の観察点について計算される。次いで、表示セルは、観察空間内の点の高さによって可視性情報が異なるので、3次元の観察点を含む。積み重ねられたプリズムとして提示された表示セルが得られる。最も低い表示セルC1(最も低いプリズムに対応する)は、高さh1未満であるその高度についての可視性を提供し、セルC1の上に位置する表示セルC2(最も高いプリズムに対応する)は、高さh1を超える高度についての可視性を提供する。
【００３７】
図12は、5D表示セルの5次元の座標系を表している。上記で述べたC. Gotsman、O. Sudarsky、J. Faymanによる文献、「Optimized Occlusion Culling Using Five-Dimensional Subdivision」、Computer Graphics、23(5); 645〜654頁、1999年の4頁の第3部で著者は、5次元を有する表示空間(すべての可能な表示半径の空間)、3次元(x、y、z)が観察点の原点を定義し、角度ΘおよびΦがその方向を定義することを考慮している。すべての次元が定義範囲を有することが考慮されよう。それぞれの表示セルは、x1、x2、y1、y2、z1、z2、Φ1、Φ2、Θ1およびΘ2を表示セルの範囲として、観察点P(x1≦X<x2となるようなX、およびy1≦Y<y2となるようなY、z1≦Z<z2となるようなZ)について、また角度ΦおよびΘがΦ1≦Φ<Φ2かつΘ1≦Θ<Θ2となる観察角度についての可視性情報を含む。
【００３８】
データベースBDは、可視性データDVによって、セルiおよびオブジェクトOBJに加えて、各セルiから潜在的に可視であり、事前計算もされているオブジェクトのリストLOPV(i)を含む。
【００３９】
この計算は、Peter Wonka、Michael WimmerおよびDieter Schmalstiegの方法によって、たとえばそれらの文献「Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs」、Proceedings of Eurographic Rendering Workshop、2000年に記載されるように行われる。
【００４０】
本発明によれば、各セルiから潜在的に見えるオブジェクトのリストLOPV(i)を得るために、各セルについて、そのセルに対するオブジェクトの最小の可視の高さのマップが計算される。そのマップは、シーンが占める地面の領域を格子状にし(grid)、各長方形rについて、セルに対して長方形の全体の最小高さHmin(r)を含めることによって得られる。このマップによって、オブジェクトが長方形r内に完全に含まれており、またその高さがHmin(r)未満である場合にはそのオブジェクトがセルから見えないことが保証される。このマップは、可視性行列と呼ばれる2次元の行列MVを用いて表される。次いで、それぞれのオブジェクトが潜在的に見えるかどうかが、オブジェクトの最大の高さを、オブジェクトのフィットプリントEMPRと交差する長方形の最小の高さHmin(r)と比較することにより確認される。完全には閉塞されないオブジェクトは、セルから潜在的に見えるオブジェクトのリストLOPVに追加される。
【００４１】
観察点についての最小の高さHmin(r)の行列MVは、以下のやり方で計算される。
【００４２】
地面に垂直な長方形によってモデル化された観察点および建物のファサード(オブジェクトの特別なケース)について考慮すると、影の体積OMBは、図4に示すように、観察点Pを通過する4つの半直線とファサードの4つの頂点の間で定義される角錐台である。この影の体積OMBによって、この3次元体積OMB内に完全に含まれるどのオブジェクトも観察点Pから見えないことが保証される。したがって、このファサードは、オクルーダファサードと呼ばれる。観察点Pについての最小の高さHmin(r)の行列MVは、行列の各長方形r内の影の体積の高さから推定される。図4では、陰影が付けられた長方形は、2つのファサードO1およびO2によって生成された影の体積OMB表している。したがって、図4からのファサードO1およびO2では、体積OMBの外に位置する長方形r1は、長方形r1に固有の高度の上で0の最小高さHmin(r)を有し、ファサードO1によって生成された影の体積OMBは、O1の影の体積の角錐上を通過し、またその角錐によって定義された位置および形状から計算され得る長方形r2に固有の高度の上で0より大きい最小高さHmin(r2)を有する。
【００４３】
次いで、セルについての関数Hmin(r)は、以下によって示される。
Hmin(r)=min{Hp(r)、pはPEに属する}
上式において、
・PEは、セルの上部面のエッジ上のサンプリング点のセットである。
・Hp(r)=max{Hp, o(r)、oはFOに属する}は、観察点Pに対する長方形rから見える最小の高さを表す関数である。
・FOは、オクルーダファサードのセットを表す。
・Hp, o(r)は、観察点Pに対する長方形rから見える最小の高さを表しており、オクルーダファサードoだけを考慮に入れた関数である。
【００４４】
図5に示すように、最小の高さHmin(r)の行列MVは、可視性水平線HVを計算するために使用される。この可視性水平線HVは、たとえば可視性行列MVのまわりで定義されており、また図5でボックスBiに対して水平線HVの下に投影POBJ1を有するオブジェクトOBJ1について当てはまるように、可視性行列MVによってカバーされる領域の外にあり、またセルiの境界を定めるボックスBiから可視性水平線HVの下に投影されたオブジェクトがそのセルiから見えないことを保証する。
【００４５】
セルiから潜在的に見えるオブジェクトのリストLOPV(i)は、データベースBD内で、論理値1または0を有するブール要素のn行およびp列をを備えた第1の可視性行列Mnpによって表され、この行列では、各行が特定のセルiに対応し、各列jが特定のオブジェクトOBJに対応し、ただし、
・Mnp -1(ai, j)1≦i≦n, 1≦i≦p、
・オブジェクトjがセルiから潜在的に見え、したがってリストLOPV(i)に属する場合は、ai, j=1
・オブジェクトjがセルiから潜在的に見えず、したがってリストLOPV(i)に属さない場合は、ai, j=0、
・n、p、i、jは、自然数である
【００４６】
本発明は、たとえばコンピュータCALによってサーバSERV内のデータベースBDのこの可視性行列Mnpを自動的に圧縮する手段を提供する。
【００４７】
可視性行列のサイズの縮小を可能にする可視性データ圧縮方法の一実施形態について以下に述べる。
【００４８】
本発明の特徴によれば、ステップE7の間、可視性行列Mnpの行iは、隣接行の間の一貫性を増加させ、またはできるだけ大きい一貫性を達成する順序に置かれ、その後に、ステップE8の間に、そのように修正された可視性行列にデジタル画像符号化を適用するために、次いで可視性行列の1および0が、符号化のためデジタル画像のピクセルを形成する。サーバSERVのコンピュータCALは、このための対応するコーダを含む。したがって、その行を移動させることにより可視性行列内に、黒が0で表され、白が1で表現された白黒デジタル画像のように、1で埋まった領域(solid area of 1s)および0で埋まった領域が形成される。
【００４９】
ステップE7を実行するために、可視性行列の行iが多数の共通要素(共通の0および1)を有するかどうか判断される。類似の行が、たとえば行列の2つの行のうちの一部またはすべての可能な組合せに排他的論理和(XOR)演算子を適用することにより検出される。2つの行i1およびi2は、(i1)XOR(i2)が多数の0を有する場合、多数の共通要素を有する。こうした状況で、多数の共通要素を有すると検出された2つの行i1および i2が、それらの間で、行i1と共通したより少ない要素を有する1つまたは複数の行を有する場合、行列の行は、i1およびi2が連続するように並べ替えられる。たとえば、連続した各行について、行列の各後続行との共通要素が検出される。これによって、最多の共通点を有する行がまとめられる。
【００５０】
次いで、このように修正された可視性行列は、デジタル画像コードに従って符号化される。行われる符号化は、アイテムのコンテンツの符号化を可能にする他の任意の符号化とすることができ、また適応可能であってもよい。
【００５１】
デジタル画像符号化に関して、デジタル画像は通常、画像の同じ単一色の領域が、事実上同じ値を有する隣接行内のピクセルによって通常表されるので、隣接行間で何らかの連続性を有する。このデジタル画像符号化は可視性行列に適用され、この符号化はそれ自体、画像ではなく、潜在的に見えるオブジェクトのリストLOPV(i)によって形成されたデータを符号化する。次いで、行列のブール要素は、レベル1あるいはレベル0だけを有し得るピクセルを形成し、このピクセルにデジタル画像処理が適用される。
【００５２】
このデジタル画像符号化は、任意選択によりデジタル画像であり得る、ユーザ局CLの画面ECR上に表示された画像とは全く関係がないが、それがデジタル画像に適用されないことを考慮すると、可視性データコードIまたはデジタル疑似画像コードIを生成する。
【００５３】
このデジタル画像符号化は、たとえば可逆の白黒画像用に設計された、JBIG(Joint Bi-level Image expert Group:共同Bi-レベル画像専門家グループ)タイプのものである。JBIG符号化は実際、符号化される画像のコンテンツを考慮し、以前に符号化されたデータの関数として現在のデータを予測し符号化するために適応演算コーダを使用する。JBIGコーダは、テンプレートと呼ばれる1組のピクセルで符号化されるピクセルの相関性を考慮して、符号化される画像内の冗長性をモデル化する。テンプレートは、たとえば、行内に前の2つのピクセル、および上の行内に、現在のピクセルの上に中心がある5つのピクセルを含み得る。JBIG符号化は、さらに正確な適応テンプレート、および確率的推定器に結合された演算コーダを使用することができ、その両方が非常に高い性能を提供する。
【００５４】
あるいは、行われる符号化は、グラフィック形式のためのものであり、また具体的にはインターネット用に設計されているPNG(Portable Network Graphics:ポータブルネットワークグラフィックス)タイプのものであり得る。
【００５５】
図6を参照して以下で述べる方法の実施形態のように、行を連続して置くステップE7は、可視性行列Mnp上で直接に行われても、可視性行列Mnpと異なる行列Msr上で行われ、そこから得られてもよい。
【００５６】
サーバSERV内で自動的に実行される方法のこの実施形態では、可視性行列Mnpが形成される第1の開始ステップE1の後、シーンSCが領域Rに分割される第2のステップE2が実行される。したがって、これらの領域Rは、図3と同じシーンSCについて図7に表されるように、観察空間EOおよびオブジェクトOBJをカバーする。領域Rは全体としてセルより大きく、したがって、事実上あらゆる領域Rが、複数のセルを少なくとも部分的にカバーする。領域Rは、たとえばシーンSCと関係なく、すべて同じ形であり、具体的には図7では矩形ブロックである。これらの矩形ブロックRは、たとえば図7に示すように、シーンの境界を定めるブロックに平行の辺を有し、平行六面体の(parallelepipedal)ブロックを形成するように垂直に立てられる。図7では、太線LIMRは、これらの矩形ブロックRの範囲を表し、したがって、それらの辺を形成する直線分によって形成される。領域Rの座標は、データベースBD内に格納される。
【００５７】
次いで、ステップE3の間に、要求REQV内に含まれる位置情報INFPに対応する観察点Pが属する領域Rが決定される。この領域は、以下、観察領域RPと呼ばれる。たとえば、xpおよびypが、図7の例の矩形ブロックRの辺に平行の2つの軸xおよびyを有する水平面のデカルト座標内の点Pの横座標および縦座標を表す場合、ブロックRPの座標(xminRP、xmaxRP、yminRP、ymaxRP)は、以下の条件に従って(xP、yP)と比較することによって決定される。
・xminRP≦xp≦xmaxRP、かつ
・yminRP≦yP≦ymaxRP
【００５８】
次いで、ステップE3の間に、セルiの座標、および観察領域RPの座標から、点Pの領域RPとの非ゼロの交差を有する、iRPと示されるセルが決定され、たとえばそれらのセルの数はmであり、ただしmはn以下である。次いで、第1の可視性行列Mnpから、領域RPのm個のセルiRPに対応するMnpのセルによって形成されるm個の行、およびMnpのp個の列を有する第2の可視性行列Mmpが形成される。したがって、行列Mmpは、行列Mnpより遥かに小さい。
【００５９】
次いで、第4のステップE4の間、観察領域RPから見えるオブジェクトOBJのリストTpが、第2の行列Mmpから決定される。したがって、(そのオブジェクトについての行内の1に対応する)セルiRPのうちの1つから見えるオブジェクトjは、このリストTp内にある。リストTpは、たとえば、行列Mmpの行にOR論理演算子を適用することによって得られる。このリストTpは、たとえば、領域RP内のオブジェクトのpビットテーブルで形成され、このテーブル内では、各ビットjは、行列Mmpの列j内に1つまたは複数の1(セルiRPのうちの1つまたは複数から見えるオブジェクトj)が存在する場合は1に等しく、また各ビットjは、行列Mmpの列jが0(セルiRPから見えないオブジェクトj)だけを含む場合は0に等しい。
【００６０】
r≦pとして第3の可視性行列Mmr取得のため、次の行列サイズ縮小ステップE5の間に、観察点Pの領域RPから見えないオブジェクトに対応する、0だけで形成される列jは、ステップE3で決定された第2の行列Mmpから削除される。また、削除された列の位置はマーク付けされる。たとえば、0で形成された列jは、上から下に行識別子1、2、3、4、5、6を有する、m=6行およびp=10列を備えた行列Mmpの例について以下で示す機構を使用して、領域RPから見えるオブジェクトOBJのリストTpの第jの位置にある値0に設定されていると検出される。
【００６１】
【表１】
【００６２】
したがって、この行列では、リストTpは以下に等しい。
【００６３】
【表２】
【００６４】
また、m=6、r=4の場合、第3の可視性行列MMrは、以下に等しい。
【００６５】
【表３】
【００６６】
削除された列は、領域RPから見えるオブジェクトOBJのリストTp内の0の位置により、すなわちj=1、2、4、7、8、9についてマーク付けされている。
【００６７】
次の行列サイズ縮小ステップE6の間、第3の可視性行列Mmrが同一の行iRPを有するかどうか判断される。少なくとも行i3とi4が同一である場合、それらのうちの1つ(i3)だけが、s≦mとする第3可視性行列Mmrから得られる第4の可視性行列Msr内に保持される。同一の行のグループGR=(i3、i4)は、たとえばMmrの2つの行のすべての可能な組合せに排他的論理和(XOR)演算子を適用することによって決定される。(i3)XOR(i4)が0の行である場合、2つの行i3およびi4は同一である。
【００６８】
第3の可視性行列Mmrの同一の行のグループGRの数NGRも計算される。
【００６９】
同一の行iRPの各グループGRについて、グループGRの同一の行i3=i4の数tからなるグループデータアイテムDGRも計算され、その後に、グループGRの同一の識別子i3、i4(識別子iRP)のリストLIDが続く。
【００７０】
図8に示すように、同一の行iRPのグループの数NGRは8ビット上で符号化され、たとえば、各グループデータアイテムDGRの同一の行の各数tが8ビット上で符号化され、グループGRの同一の行の識別子i3、i4の各リストLIDがt*kビット上で符号化され、ただしkは、行すなわちセル識別子i3またはi4を符号化するための固定数のビットである。データアイテムDGRは次々に符号化される。第1のデータアイテムDGR1の後の、第1のグループGR1の第1のデータアイテムDGR1から第2のグループGR2の第2のデータアイテムDGR2への変更は、DGR1の同一の行の数t1、すなわち8ビット長の後に、グループGR1の同一の行の識別子のリストLID1のためのt1*kビットだけがあり、またこれらのt1*kビットの後には、t2をDGR2の同一行の数として、DGR2のt2同一行、すなわち8ビット長が始まり、それに続いて、DGR2の同一行の識別子のt2*kビットのリストLID2のt2*kビットがあることが予想されるので復号される。
【００７１】
したがって、上記の例では、
・NGR=2
・DGR=(2、1、5、2、3、6)
t1=2、LID1=1、5(Mmrの第1と第5の行が同一)ではDGR1=(2、1、5)
t2=2、LID2=3、6(Mmrの第3と第6の行が同一)ではDGR2=(2、3、6)
・Msr(s=4、r=4であり、またMmrの行1および6を削除し、上から下に識別子2、3、4、5の行を保持した後)は、以下に等しい。
【００７２】
【表４】
【００７３】
次いで、第5の可視性行列M'srを得るために、上述の行を第4の可視性行列Msr内に連続して置くステップE7が実行され、デジタル疑似画像コードiを得るために、上述のデジタル画像符号化ステップE8が第5の可視性行列M'srに適用される。この第5の可視性行列M'srは、元の第1の可視性行列Mnpに対して修正された可視性行列M'srと呼ばれる。
【００７４】
第5の可視性行列M'sr内の連続した行i1、i2のs個の識別子iRPは、第5の行列M'sr内のそれらの出現順で(たとえば上から下に)、この第5の行列M'srのデジタル画像符号化のために連続して置かれたセルの識別子i1、i2のリストと呼ばれるリストLIOC、または修正済み可視性行列M'srのセルの識別子i1、i2のリストLIOC内に格納される。連続して置かれたセルの識別子のこのリストLIOCは、グループGRの同一のセルのリストLIDとは異なる。連続して置かれたセルの識別子のリストLIOCは、s*kビット上で符号化され、ただしkは、行あるいはセル識別子i1またはi2を符号化するための固定数のビットである。
【００７５】
上記の例の行列Msrに適用され、ステップE7は、たとえば、以下の可視性行列M'sr、
【００７６】
【表５】
【００７７】
すなわち、上から下に、Mmp、MmrおよびMsrの行2、3、4、5の識別子3、5、4、2の順序をもたらす。したがって、LIOC=(3, 5, 4, 2)である。
【００７８】
この行列M'srは、以下の1で埋まった領域を含む。
【００７９】
【表６】
【００８０】
ステップE3、E4、E5、E6、E7、E8、E9は、要求REQV内で示された各観察点P、および観察点Pが属すると判断された各領域RPについて実行される。適切であれば、ステップE5およびE6の順序は逆にされてもよい。
【００８１】
応答RVのデータDEは、観察領域RPから見えるオブジェクトOBJに関するデータDVOBJに等しい、データベースBDからの幾何学的データDGEなど、可視性データDVEを含む(図1参照)。このデータDGEは、サーバSERVのコンピュータCALによって、たとえば領域RPから見えるオブジェクトOBJのリストTpを使用して、ステップE4またはE5の間にデータベースBDからのデータDVOBJ内で選択される。
【００８２】
可視性データDVEは、符号化ステップE8の後、サーバSERVのコンピュータCALによって決定され、図8では、
・観察点Pの領域RPから見えるオブジェクトOBJのリストTpと、
・同一の列のグループGRの数NGRと、
・同一の列のグループのデータDGR(1、LID)と、
・第5の行列M'sのデジタル画像符号化のために連続して置かれたセルの識別子i1、i2のリストLIOCと、
・ステップE8によるデジタル画像符号化により符号化された第5の行列M'srに等しいデジタル疑似画像符号Iとを含んでいる。
【００８３】
以下の表は、上述の圧縮方法のテストの結果を示している。これらのテストは、5750個のオブジェクトおよび29153個の表示セルの仮想都市を定義するデータベースBDに対して実施されたものである。
【００８４】
【表７】
【００８５】
したがって、本発明の方法によって、従来技術の可逆符号化から開始したテスト1に従って行われる可逆符号化よりも、テスト2に従って可視性データのより可逆的な圧縮が可能になることが明らかである。
【００８６】
可視性データDVEを含む応答RVを受信した後、ユーザの局CLは、図9に示すやり方で可視性データDVEを圧縮解除する。このために、局CLは、データDVEを自動的に圧縮解除する手段たとえばコンピュータCAL2を含む。
【００８７】
観察領域RPの第2の可視性行列Mmpが、前の要求REQV(INFP)に関連して受信されるそれぞれの応答RVについて得られることを可能にする可視性データDVE圧縮方法の一実施形態について以下に述べる。この実施形態は、たとえばコンピュータCAL2のデコーダ内で実施される。
【００８８】
局CLは、観察点Pの領域RPから見えるオブジェクトOBTのリストTpがpビット上で符号されており、同一の行のグループGRの数が8ビット上で符号化されており、同一の行のグループのGRの数NGRが8ビット上で符号化されており、同一のグループのデータアイテムDGR(t、LID)のそれぞれが8ビット+t.kビット上で符号化されており、連続して置かれたセルi1、i2の識別子のリストLIOCがs*kビット上で符号化されている事実を記憶しており、リストTp、数NGR、データアイテムDGR(t、LID)、リストLIOCおよびデジタル疑似画像符号Iを、受信された応答RVから抽出し、第1の抽出ステップE11の間にそれらをそのローカルデータベースBL内に格納する。応答RVからのオブジェクトのデータDGEも、ローカルデータベースBL内に格納される。
【００８９】
圧縮解除プロセスの第2のステップE12の間、m行およびp列を有する第6のブール行列Mmp0が構築され、mおよびpが、応答RVのデータDVEから、すなわちpについてのリストTp、およびグループGRの同一の行の識別子i3、i4のリストLIDから、またmについて連続して置かれたセルi1、i2の識別子のリストLIOCから決定される。
【００９０】
次いで、可視オブジェクトのリストTpの0の位置にある行列Mmp0内の0に設定される列の位置が、リストTpから推定される。
【００９１】
したがって、上記の例では、m=6、p=10について、以下の行列Mmp0が得られる。
【００９２】
【表８】
【００９３】
次いで、コードIは、ステップE13の間に局CL内で、ステップE8でサーバSERV内で実施されたデジタル画像符号化の逆であるデジタル画像復号によって復号され、この復号の特徴は、局CLのメモリ内に存在している。したがって、この復号によって、ステップE7から、第5の可視性行列M'srが生成される。
【００９４】
次のステップE14の間、第7の行列Mmp0'を得るために、第5の可視性行列M'srの列が、可視オブジェクトのリストTpの1の位置、すなわち上記例では0の列で埋められていない位置にある、第6の行列Mmp0の空いた列に移される。この充填は、第5の行列M'srの列、および第6の行列Mmp0の空の列について同じ順序で行われる。第5の行列M'srが第6の行列Mmp0より小さい数sの行を有することを考慮して、M'srから来る第6の行列Mmp0内の第1のs個の行だけが埋められる。
【００９５】
連続して置かれたセルの識別子i1、i2のリストLIOCは、このようにして埋められた第7の行列Mmp0'の第1のs個の行の識別子を示している。したがって、埋められた、Mmp0の行の識別子がリストLIOCから知られているので、ステップE7で行われるものと逆の置換を行う必要はない。
【００９６】
したがって、上記の例では、ステップE14によって局CL内で以下の第7の行列Mmp0'が生成され、この第7の行列Mmp0では第3、第5、第6および第10の列が、LIOCのリストに従って、Mnpのセル3、5、4、2に対応する、S=4の第1の行でM'srによって埋められる。
【００９７】
【表９】
【００９８】
次のステップE15で、第8の行列Mmp'を得るために、同一の列のグループの数NGRによって定義された複製された列、およびグループのデータアイテムDGR(t、LID)が、ステップE14で得られた第7の行列Mmp0'に追加される。追加される行は、埋められていない第7の行列Mmp0'の行に取って換わる。ステップE6で、データDGRは、以下に示すやり方で、データDGR内に含まれる同一の行のグループの数NGR、および同一の行の数t、ならびに同一の行の識別子のリストLIDを使用して復号される。
【００９９】
したがって、上記の例では、行列Mmp'を形成するために行列Mmp0'に、DGR1によるMmp0'の識別子5を有する行に等しい識別子1を有する行、およびDGR2によるMmp0'の識別子3を有する行に等しい識別子6を有する行、すなわち下から上に識別子3、5、4、2、1、6を備えたセルを有する以下の行列Mmp'の最後の2つの行が追加され、したがって、それは以下の行列Mmpに対応する。
【０１００】
【表１０】
【０１０１】
局CLは、ステップE15によって得られた第8の行列Mmp'を、そのローカルデータベース内に格納する。
【０１０２】
次のステップE16で、局CLは、観察点Pが属する第8の行列Mmp'のセルiRPを、ローカルデータベースBL内に存在するセルiの座標および識別子から、また前の要求REQVを送信するためにコンピュータCAL2によって決定され、また送信された要求REQVと共にローカルデータベースBL内に格納された観察点Pの位置情報INFPから決定する。次いで、このように検出された点Pのセルiは、たとえばローカルデータベースBL内に識別子iPを有する。
【０１０３】
次いで、コンピュータCAL2は、データベースBLの第8の行列Mmp'内のセルiPに対応する行の位置を、この識別子iP、およびローカルデータベースBLに格納された、連続して置かれたセルi1、i2の識別子のリストLIOCから決定する。
【０１０４】
コンピュータCAL2は、ベースBLの第8の行列Mmp'の行iPをスキャンすることにより、観察点Pから見えるオブジェクトのリストLOPV(iP)を得る。
【０１０５】
次いで、局CLは、ステップE17で、観察点Pから見えるオブジェクトOBJを表す対応する画像を画面ECR上に表示するため、観察点Pから見えるオブジェクトのリストLOPV(iP)、および対応するオブジェクトのデータDVOBJを使用し、この画像は、このリストLOPV(iP)内で1が現れるデータDVOBJによって定義されたオブジェクトを表しており、このリストLOPV(iP)内で0が現れるデータDVOBJによって定義されたオブジェクトである、観察点Pから見えないオブジェクトOBJは表していない。
【０１０６】
次いで、局CLのユーザは、観察点Pを新しい点P2に移動させることができる。観察点Pを空間EO内の新しい位置INFP2に置き換える度に、新しい観察点P2が、ローカルベースBL内に格納された行列Mmp'内に既に存在するセル内にあるかどうかが局CL内で自動的に決定される。そうである場合は、この行列Mmp'のこのセルiRPについてステップE16を再び、またステップE17を実行するために、対応するMmp'が、局CLのベースBL内で探し求められる。そうでない場合は、局CLは、新しい観察点P2の位置情報INFP2を含む新しい要求REQV2をサーバSERVに送信し、サーバSERVは、上述したように新しい応答RV2を返送する。それぞれの新しい応答RV2について、サーバSERVは、その新しい応答RV2内に挿入されるデータDGEが前の応答RVで既に送信されているかどうか判断し、そうである場合は、サーバSERVは新しい応答RV2において、既に送信されたこのデータDGEを送信しない。そうではなく、それは新しい応答RV2において、まだ送信されていないデータDGEだけを送信し、それによって、新しい応答RV2内で送信されるデータの量がさらに減少される。
【０１０７】
同様に、観察点Pを空間EO内の新しい位置INFP2に置き換える度に、新しい観察点P2が、点Pについての前の画像の表示を可能にした前の応答RVにより得られた第8の行列Mmp'内に既に存在するセルiRP内にあるかどうかが局CL内で自動的に判断される。そうである場合は、新しい点P2を求める新しい要求REQV2を送信する必要はない。次いで、新しい観察点P2についてのリストLOPV(iP2)は、前の観察点PについてのリストLOPV(iP)と比較して補足のオブジェクトのリストLOPV(iP2)+を追加し、前の観察点PについてのリストLOPV(iP)と比較して欠落しているオブジェクトのリストLOPV(iP2)-を削除することによって、前の観察点PについてのリストLOPV(iP)から推定されることができる。この2つのリストLOPV(iP2)+およびLOPV(iP2)-は局CL内において、これらのリストの間で異なるオブジェクト((LOPV(iP))XOR(LOPV(iP2))において1で示される)のリストを取るために、点Pについて得られる前の行列Mmp'のリストLOPV(iP)およびLOPV(iP2)から、たとえばそれらに排他的論理和演算子を適用することによって計算される。これによって、非常に長いかもしれないリストLOPV(iP2)の全体をスキャンする必要性が回避される。
【０１０８】
あるいは、可視性データは、システムSERVが観察点位置情報INFPを受信する前に、領域Rのそれぞれについて、たとえば行列M'srの形で事前に圧縮される。
【０１０９】
コンピュータプログラムが、たとえばシステムSERVの上の圧縮プロセスおよびユニットCLの上の圧縮解除プロセスを実行するために、システムSERVおよびユニットCL上にインストールされる。
【図面の簡単な説明】
【０１１０】
【図１】本発明によるデータ圧縮および圧縮解除方法が実施される、クライアントサーバ装置を表す図である。
【図２】2.5次元での3次元オブジェクトモデル化を表す図である。
【図３】オブジェクト、およびそれらのオブジェクトの表示セルを含むシーンを上から示す図である。
【図４】潜在的に見えるファサードの背後のオブジェクトのリストを計算するために使用され得る、オクルーダファサードによって生成された影の体積を上から示す図である。
【図５】図4に示す計算方式によって生成された可視性水平線の透視図である。
【図６】本発明よる可視性データ圧縮方法の一実施形態のフローチャートである。
【図７】オブジェクトを含んでおり、領域に分割された図3からのシーンを上から示す図である。
【図８】図6による圧縮方法によって圧縮された可視性データの構造を表す図である。
【図９】本発明の可視性データ圧縮解除方法の一実施形態のフローチャートを表す図である。
【図１０】2次元シーンの表示セルを表す図である。
【図１１】3次元シーンの表示セルを表す図である。
【図１２】5Dシーンの表示セルの5つの次元を表す図である。
【符号の説明】
【０１１１】
ALT 高度
BD データベース
Bi ボックス
BL データベース
CAL、CAL1、CAL2 コンピュータ
CL 局
COM コントロール
CT 通信チャネル
C1、C2 表示セル
DE 可視性データ
DGE 幾何学的データ、
DGR データアイテム
DV 可視性データ
DVE 可視性データ
DVEO データ
DVOBJ 幾何学的データ
ECR 画面
EMPR フットプリント
EO 空間
E1〜E17 ステップ
GR グループ
H 高さ
HV 可視性水平線
I デジタル疑似画像コード/可視性データコード
i、i1、i2 行/セル/識別子
i3、i4 行/識別子
INFP 位置情報
INTC ネットワークインターフェース
INTS ネットワークインターフェース
iRP 行/セル/識別子
IUT ユーザインターフェース
LID リスト
LIMi 太線
LIMR 太線
LIOC リスト
NGR 数
LOPV、LOPV(i) リスト
MR レンダリングエンジン
Mnp 第1の可視性行列
Mmp 第2の可視性行列
Mmr 第3の可視性行列
Msr 第4の可視性行列
M'sr 第5の可視性行列
Mmp0 第6の行列
Mmp0' 第7の行列
MV 行列
OBJ オブジェクト
OMB 影の体積
O1、O2 ファサード
P 観察点
POBJ1 投影
R 領域/矩形ブロック
r 長方形
REQV 要求
RP 観察領域
RV 応答
SC 環境/シーン
SEMPR 頂点
SERV サーバ/データ処理システム
Tp リスト
x 軸
y 軸
z 軸
【特許請求の範囲】
【請求項１】
可視性データベース(BD)からの可視性データを圧縮する方法であって、
・前記可視性データ(DV)が、所定のオブジェクト(OBJ)を観察するための観察空間(EO)内の観察点のセル(i)と、観察点の各セル(i)について、観察点のそのセル(i)から潜在的に見える前記所定のオブジェクト(OBJ)の中からの前記オブジェクトのリスト(LOPV(i))とを含み、
・前記可視性データ(DV)が、前記データベース(BD)内で少なくとも、各行がセル(i)に対応し、各列(j)が前記所定のオブジェクト(OBJ)のうちの1つに対応するブール要素(ai, j)の第1の可視性行列(Mnp)の形で表され、前記ブール要素(ai, j)がそれぞれ、前記オブジェクト(j)が、前記セル(i)に関連する潜在的可視オブジェクトの前記リスト(LOPV(i))に属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
・多数の共通要素を有しており、隣接していない前記可視性行列(Msr)内の行(i)を前記データベース(BD)内で自動的に検出し(E7)、修正済み可視性行列(M'sr)を形成するために、多数の共通要素を有すると検出された行を連続して置くようにこうしたいずれの行をも並べ替えること、および
・可視性データコード(I)の取得のため前記修正済み可視性行列(M'sr)のブール要素にデジタル画像符号化を自動的に適用する(E8)ことであって、前記修正済み行列(M'sr)のこれらのブール要素が、符号化のため前記デジタル画像のピクセルを形成することを特徴とする方法。
【請求項２】
前記可視性データベース(BD)がデータ処理システム(SERV)に関連付けられ、前記システム(SERV)が、前記生成された可視性符号化データ(I)を可視性データ処理ユニット(CL)に送信することを特徴とする請求項1に記載の圧縮方法。
【請求項３】
前記データ処理システム(SERV)がデータサーバ(SERV)であり、前記可視性データ処理ユニット(CL)が可視性データ処理局(CL)であることを特徴とする請求項2に記載の圧縮方法。
【請求項４】
・前記データ処理システム(SERV)および前記可視性データ処理ユニット(CL)が同じ可視性データ処理局(CL)に設けられることを特徴とする請求項2に記載の圧縮方法。
【請求項５】
・前記データ処理システム(SERV)が、前記観察空間(EO)内の特定の観察点(P)の位置に関する情報(INFP)を前記処理ユニット(CL)から事前に受信しており、前記観察空間(EO)が前記可視性データベース内(BD)で領域(R)に分割され、
・前記ユニット(CL)から受信された前記位置情報 (INFP)に対応する前記観察点(P)が属する前記観察空間の前記領域(R)の中から観察領域(RP)を決定するステップと、
・前記観察領域(RP)との交差を有する可視性データ(DV)の前記セル(i)の中から第1のセル(iRP)を決定するステップ(E3)と、
・行が、前記決定された観察領域(RP)の前記第1のセル(iRP)に対応する前記第1の可視性行列(Mnp)の前記行で形成される第2の可視性行列(Mmp)を前記第1の可視性行列(Mnp)から抽出するステップ(E3)と、
・前記第2の可視性行列(Mmp)から前記修正済の可視性行列(M'sr)を形成するステップ(E3)とが前記データ処理システム(SERV)内で自動的に実行されることを特徴とする請求項2から4のいずれか一項に記載の圧縮方法。
【請求項６】
前記観察領域(RP)から潜在的に見える前記オブジェクトのリスト(Tp)が、前記データ処理システム(SERV)内で第2の可視性行列(Mmp)から自動的に決定され(E4)、前記データ処理システム(SERV)によって前記可視性データコード(I)を付けて前記処理ユニット(CL)送信されることを特徴とする請求項5に記載の圧縮方法。
【請求項７】
前記修正済の可視性行列(M'sr)の前記セルの前記識別子(i1,i2)のリスト(LIOC)が、前記データ処理システム(SERV)によって可視性データコード(I)を付けて前記処置ユニット(CL)に送信されることを特徴とする請求項5または請求項6に記載の圧縮方法。
【請求項８】
前記可視性行列(Mmr)の前記同一の列が、第4の可視性行列(Msr)内で同一の行(i3,i4)のグループ((GR)ごとに1つの行だけを保持するために前記データ処理システム(SERV)内で自動的に決定され(E6)、前記修正済の可視性行列(M'sr)が前記第4の可視性行列(Msr)から形成され、前記データ処理システム(SERV)内で、
・前記可視性行列(Mmr)の同一の行のグループ(GR)の数であるデータアイテム(NGR)と、
同一の行の各グループ(GR)について、
・前記グループ(GR)の複数(t)の同一の行と、前記グループ(GR)の前記同一の行の前記識別子(i3,i4)のリスト(LID)とを含むグループデータアイテム(DGR)とが自動的に計算され(E6)、
同一の行のグループ(GR)の数である前記データアイテム(NGR)、および前記グループデータアイテム(DGR)が、前記データ処理システム(SERV)によって前記可視性データコード(I)を付けて前記処理ユニット(CL)に送信されることを特徴とする請求項2から7のいずれか一項に記載の圧縮方法。
【請求項９】
同一の行の各グループ(GR)について、前記グループ(GR)の同一の行の数(t)が、所定の数のビット上で符号化され、前記グループ(GR)の前記リスト(LID)からの同一の行の各識別子(i3,i4)が、所定の数のビット上で符号化され、各グループデータアイテム(DGR)が、前記グループ(GR)のすべてについて所定の順序で、前記グループ(GR)の同一の行の前記数(t)、および前記グループ(GR)の前記同一の行の前記識別子(i3,i4)の前記リスト(LID)からなることを特徴とする請求項8に記載の圧縮方法。
【請求項１０】
前記可視性行列(Mmp)内に少なくとも1つの0の列が存在することが自動的に検出され(E5)、前記修正済の可視性行列(M'sr)がそこから形成される第3の可視性行列(Mmr)を形成するために、検出されたいずれのこうした0の列もが前記可視性行列(Mmp)から自動的に削除される(E5)ことを特徴とする請求項1から9のいずれかに記載の圧縮方法。
【請求項１１】
前記修正済の可視性行列(M'sr)の前記ブール要素に適用される前記デジタル画像符号化がJBIGまたはPNGタイプのものであることを特徴とする請求項1から10のいずれかに記載の圧縮方法。
【請求項１２】
前記圧縮方法によって適用される前記デジタル画像符号化の逆であるデジタル画像復号が、前記生成された可視性データコード(I)に適用され(E13)、前記復号が可視性行列(M'sr)をもたらすことを特徴とする請求項1から11のいずれかに記載の可視性データ圧縮方法によって生成された可視性データコード(I)を圧縮解除する方法。
【請求項１３】
少なくとも請求項6に従属する場合、0の列が、前記デジタル画像復号によって得られた前記可視性行列(M'sr)に、前記観察領域(RP)から潜在的に見えるオブジェクトの前記リスト(Tp)によって示された潜在的に見えない前記オブジェクトの前記位置で自動的に追加される(E12、E14)ことを特徴とする請求項12に記載の圧縮解除方法。
【請求項１４】
少なくとも請求項8に従属する場合、前記グループデータアイテム(DGR)の前記同一の行の識別子(i3、i4)の前記リスト(LID)内には存在し、前記可視性行列(M'sr)には存在しない同一の行の前記識別子(i3、i4)によって示された少なくとも1つの欠落した行が、前記デジタル画像復号によって得られた前記可視性行列(M'sr)に自動的に追加され(E15)、次いで、少なくとも1つの欠落した行が、前記同一の行の識別子(i3、i4)の前記リスト(LID)内に存在する前記識別子を有する前記可視性行列(M'sr)の前記行に等しいことを特徴とする請求項12または請求項13に記載の圧縮解除方法。
【請求項１５】
請求項12から14のいずれか一項に記載の可視性データ圧縮解除方法を実行する手段(CAL2)を含むことを特徴とするデコーダ。
【請求項１６】
可視性データベース(BD)に関連するシステム(SERV)であって、
・前記可視性データ(DV)が、所定のオブジェクト(OBJ)を観察するための観察空間(EO)内の観察点のセル(i)と、観察点の各セル(i)について、観察点のそのセル(i)から潜在的に見える前記所定のオブジェクト(OBJ)の中からのオブジェクトのリスト(LOPV(i))とを含み、
・前記可視性データ(DV)が前記データベース(BD)内で少なくとも、各行がセル(i)に対応し、各列(j)が前記所定のオブジェクト(OBJ)のうちの1つに対応するブール要素(ai, j)の第1の可視性行列(Mnp)の形で表され、前記ブール要素(ai, j)がそれぞれ、前記オブジェクト(j)が、前記セル(i)に関連する潜在的可視オブジェクトの前記リスト(LOPV(i))に属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
前記システム(SERV)が、請求項1から11のいずれか一項に記載の可視性データ圧縮方法を実行する手段(CAL)を含むことを特徴とするシステム(SERV)。
【請求項１７】
コンピュータ上で実行されるときに、請求項1から11のいずれか一項に記載のデータ圧縮方法を実施する命令を含むことを特徴とするコンピュータプログラム。
【請求項１８】
コンピュータ上で実行されるときに、請求項12から14のいずれか一項に記載のデータ圧縮解除方法を実施する命令を含むことを特徴とするコンピュータプログラム。
【請求項１】
可視性データベース(BD)からの可視性データを圧縮する方法であって、
・前記可視性データ(DV)が、所定のオブジェクト(OBJ)を観察するための観察空間(EO)内の観察点のセル(i)と、観察点の各セル(i)について、観察点のそのセル(i)から潜在的に見える前記所定のオブジェクト(OBJ)の中からの前記オブジェクトのリスト(LOPV(i))とを含み、
・前記可視性データ(DV)が、前記データベース(BD)内で少なくとも、各行がセル(i)に対応し、各列(j)が前記所定のオブジェクト(OBJ)のうちの1つに対応するブール要素(ai, j)の第1の可視性行列(Mnp)の形で表され、前記ブール要素(ai, j)がそれぞれ、前記オブジェクト(j)が、前記セル(i)に関連する潜在的可視オブジェクトの前記リスト(LOPV(i))に属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
・多数の共通要素を有しており、隣接していない前記可視性行列(Msr)内の行(i)を前記データベース(BD)内で自動的に検出し(E7)、修正済み可視性行列(M'sr)を形成するために、多数の共通要素を有すると検出された行を連続して置くようにこうしたいずれの行をも並べ替えること、および
・可視性データコード(I)の取得のため前記修正済み可視性行列(M'sr)のブール要素にデジタル画像符号化を自動的に適用する(E8)ことであって、前記修正済み行列(M'sr)のこれらのブール要素が、符号化のため前記デジタル画像のピクセルを形成することを特徴とする方法。
【請求項２】
前記可視性データベース(BD)がデータ処理システム(SERV)に関連付けられ、前記システム(SERV)が、前記生成された可視性符号化データ(I)を可視性データ処理ユニット(CL)に送信することを特徴とする請求項1に記載の圧縮方法。
【請求項３】
前記データ処理システム(SERV)がデータサーバ(SERV)であり、前記可視性データ処理ユニット(CL)が可視性データ処理局(CL)であることを特徴とする請求項2に記載の圧縮方法。
【請求項４】
・前記データ処理システム(SERV)および前記可視性データ処理ユニット(CL)が同じ可視性データ処理局(CL)に設けられることを特徴とする請求項2に記載の圧縮方法。
【請求項５】
・前記データ処理システム(SERV)が、前記観察空間(EO)内の特定の観察点(P)の位置に関する情報(INFP)を前記処理ユニット(CL)から事前に受信しており、前記観察空間(EO)が前記可視性データベース内(BD)で領域(R)に分割され、
・前記ユニット(CL)から受信された前記位置情報 (INFP)に対応する前記観察点(P)が属する前記観察空間の前記領域(R)の中から観察領域(RP)を決定するステップと、
・前記観察領域(RP)との交差を有する可視性データ(DV)の前記セル(i)の中から第1のセル(iRP)を決定するステップ(E3)と、
・行が、前記決定された観察領域(RP)の前記第1のセル(iRP)に対応する前記第1の可視性行列(Mnp)の前記行で形成される第2の可視性行列(Mmp)を前記第1の可視性行列(Mnp)から抽出するステップ(E3)と、
・前記第2の可視性行列(Mmp)から前記修正済の可視性行列(M'sr)を形成するステップ(E3)とが前記データ処理システム(SERV)内で自動的に実行されることを特徴とする請求項2から4のいずれか一項に記載の圧縮方法。
【請求項６】
前記観察領域(RP)から潜在的に見える前記オブジェクトのリスト(Tp)が、前記データ処理システム(SERV)内で第2の可視性行列(Mmp)から自動的に決定され(E4)、前記データ処理システム(SERV)によって前記可視性データコード(I)を付けて前記処理ユニット(CL)送信されることを特徴とする請求項5に記載の圧縮方法。
【請求項７】
前記修正済の可視性行列(M'sr)の前記セルの前記識別子(i1,i2)のリスト(LIOC)が、前記データ処理システム(SERV)によって可視性データコード(I)を付けて前記処置ユニット(CL)に送信されることを特徴とする請求項5または請求項6に記載の圧縮方法。
【請求項８】
前記可視性行列(Mmr)の前記同一の列が、第4の可視性行列(Msr)内で同一の行(i3,i4)のグループ((GR)ごとに1つの行だけを保持するために前記データ処理システム(SERV)内で自動的に決定され(E6)、前記修正済の可視性行列(M'sr)が前記第4の可視性行列(Msr)から形成され、前記データ処理システム(SERV)内で、
・前記可視性行列(Mmr)の同一の行のグループ(GR)の数であるデータアイテム(NGR)と、
同一の行の各グループ(GR)について、
・前記グループ(GR)の複数(t)の同一の行と、前記グループ(GR)の前記同一の行の前記識別子(i3,i4)のリスト(LID)とを含むグループデータアイテム(DGR)とが自動的に計算され(E6)、
同一の行のグループ(GR)の数である前記データアイテム(NGR)、および前記グループデータアイテム(DGR)が、前記データ処理システム(SERV)によって前記可視性データコード(I)を付けて前記処理ユニット(CL)に送信されることを特徴とする請求項2から7のいずれか一項に記載の圧縮方法。
【請求項９】
同一の行の各グループ(GR)について、前記グループ(GR)の同一の行の数(t)が、所定の数のビット上で符号化され、前記グループ(GR)の前記リスト(LID)からの同一の行の各識別子(i3,i4)が、所定の数のビット上で符号化され、各グループデータアイテム(DGR)が、前記グループ(GR)のすべてについて所定の順序で、前記グループ(GR)の同一の行の前記数(t)、および前記グループ(GR)の前記同一の行の前記識別子(i3,i4)の前記リスト(LID)からなることを特徴とする請求項8に記載の圧縮方法。
【請求項１０】
前記可視性行列(Mmp)内に少なくとも1つの0の列が存在することが自動的に検出され(E5)、前記修正済の可視性行列(M'sr)がそこから形成される第3の可視性行列(Mmr)を形成するために、検出されたいずれのこうした0の列もが前記可視性行列(Mmp)から自動的に削除される(E5)ことを特徴とする請求項1から9のいずれかに記載の圧縮方法。
【請求項１１】
前記修正済の可視性行列(M'sr)の前記ブール要素に適用される前記デジタル画像符号化がJBIGまたはPNGタイプのものであることを特徴とする請求項1から10のいずれかに記載の圧縮方法。
【請求項１２】
前記圧縮方法によって適用される前記デジタル画像符号化の逆であるデジタル画像復号が、前記生成された可視性データコード(I)に適用され(E13)、前記復号が可視性行列(M'sr)をもたらすことを特徴とする請求項1から11のいずれかに記載の可視性データ圧縮方法によって生成された可視性データコード(I)を圧縮解除する方法。
【請求項１３】
少なくとも請求項6に従属する場合、0の列が、前記デジタル画像復号によって得られた前記可視性行列(M'sr)に、前記観察領域(RP)から潜在的に見えるオブジェクトの前記リスト(Tp)によって示された潜在的に見えない前記オブジェクトの前記位置で自動的に追加される(E12、E14)ことを特徴とする請求項12に記載の圧縮解除方法。
【請求項１４】
少なくとも請求項8に従属する場合、前記グループデータアイテム(DGR)の前記同一の行の識別子(i3、i4)の前記リスト(LID)内には存在し、前記可視性行列(M'sr)には存在しない同一の行の前記識別子(i3、i4)によって示された少なくとも1つの欠落した行が、前記デジタル画像復号によって得られた前記可視性行列(M'sr)に自動的に追加され(E15)、次いで、少なくとも1つの欠落した行が、前記同一の行の識別子(i3、i4)の前記リスト(LID)内に存在する前記識別子を有する前記可視性行列(M'sr)の前記行に等しいことを特徴とする請求項12または請求項13に記載の圧縮解除方法。
【請求項１５】
請求項12から14のいずれか一項に記載の可視性データ圧縮解除方法を実行する手段(CAL2)を含むことを特徴とするデコーダ。
【請求項１６】
可視性データベース(BD)に関連するシステム(SERV)であって、
・前記可視性データ(DV)が、所定のオブジェクト(OBJ)を観察するための観察空間(EO)内の観察点のセル(i)と、観察点の各セル(i)について、観察点のそのセル(i)から潜在的に見える前記所定のオブジェクト(OBJ)の中からのオブジェクトのリスト(LOPV(i))とを含み、
・前記可視性データ(DV)が前記データベース(BD)内で少なくとも、各行がセル(i)に対応し、各列(j)が前記所定のオブジェクト(OBJ)のうちの1つに対応するブール要素(ai, j)の第1の可視性行列(Mnp)の形で表され、前記ブール要素(ai, j)がそれぞれ、前記オブジェクト(j)が、前記セル(i)に関連する潜在的可視オブジェクトの前記リスト(LOPV(i))に属する場合は論理値1を有し、そうでない場合は論理値0を有する第iの行および第jの列に位置し、
前記システム(SERV)が、請求項1から11のいずれか一項に記載の可視性データ圧縮方法を実行する手段(CAL)を含むことを特徴とするシステム(SERV)。
【請求項１７】
コンピュータ上で実行されるときに、請求項1から11のいずれか一項に記載のデータ圧縮方法を実施する命令を含むことを特徴とするコンピュータプログラム。
【請求項１８】
コンピュータ上で実行されるときに、請求項12から14のいずれか一項に記載のデータ圧縮解除方法を実施する命令を含むことを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公表番号】特表２００８−５１１８８８（Ｐ２００８−５１１８８８Ａ）
【公表日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願番号】特願２００７−５２８９４２（Ｐ２００７−５２８９４２）
【出願日】平成１７年８月１９日（２００５．８．１９）
【国際出願番号】ＰＣＴ／ＦＲ２００５／０５０６７８
【国際公開番号】ＷＯ２００６／０２７５１９
【国際公開日】平成１８年３月１６日（２００６．３．１６）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
【公表日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願日】平成１７年８月１９日（２００５．８．１９）
【国際出願番号】ＰＣＴ／ＦＲ２００５／０５０６７８
【国際公開番号】ＷＯ２００６／０２７５１９
【国際公開日】平成１８年３月１６日（２００６．３．１６）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
[ Back to top ]