(57)【要約】【課題】再構成に必要となるノードの探索処理を効率的に行える、多重解像度表現による非構造数値データの階層化方法を提供する。【解決手段】本発明は、階層化データを生成する際、解像度レベルごとに空間に周期格子状に敷き詰められたセル２２に、解像度および空間位置がこのセルの解像度レベルおよび空間位置とそれぞれ所定の範囲内で一致するノード２４を格納する。ある解像度レベルのセルは、当該解像度レベルよりも高い解像度レベルのセルを包含する関係にある。ある解像度レベルのセルから、このセルが包含し、内部にノードを有する高解像度レベルのセルへ下層リンク２３を設け、再構成の際、この下層リンク２３を用いることによりノード単位ではなくセル単位で詳細化に必要なノードの探索を行う。【選択図】  図３
2004171139.tif 000002
【特許請求の範囲】
【請求項１】
非構造数値データを多重解像度表現により階層化する方法において、
離散的な解像度レベルごとに空間に周期格子状に敷き詰められたセルであって、ある解像度レベルのセルは当該解像度レベルよりも高い解像度レベルのセルを包含する関係にあるセルを設けるステップと、
所定のセルに、解像度および空間位置が前記セルの解像度レベルおよび空間位置とそれぞれ所定の範囲内で一致するノードを格納するステップと、
前記セルから、該セルが包含し、内部にノードを有する高解像度レベルのセルへ下層リンクを設けるステップを有することを特徴とする方法。
【請求項２】
特定の解像度レベルのセルを追加するステップをさらに有する、請求項１に記載の方法。
【請求項３】
特定の解像度レベルまで最も単純化された数値データを詳細化し、該解像度レベルのセルを消去するステップをさらに有する、請求項１または２に記載の方法。
【請求項４】
所定の解像度レベルよりも高い解像度レベルのセルをすべて削除するステップをさらに有する、請求項１から３のいずれか１項に記載の方法。
【請求項５】
所定の解像度レベルよりも高い解像度レベルのセルを設けない、請求項１から３のいずれか１項に記載の方法。
【請求項６】
全ての解像度レベルのセルを削除し、階層化されたデータを元のデータに復元するステップをさらに有する、請求項１から３のいずれか１項に記載の方法。
【請求項７】
同じ解像度レベルの分解処理を並列に行う、請求項１から６のいずれか１項に記載の方法。
【請求項８】
ノード間の依存関係である依存リンクを、該ノードが属するセルの解像度レベルと、前記セルの相対的な位置関係と、前記セル内のノード番号により表現する、請求項１から７のいずれか１項に記載の方法。
【請求項９】
所定のセルからより高解像度レベルのセルへ詳細化されたときの付随属性および／または表面境界の変化量を示す変動データを生成するステップをさらに有する、請求項１から８のいずれか１項に記載の方法。
【請求項１０】
幾何構造と付随属性を独立に分解処理する、請求項１から９のいずれか１項に記載の方法。
【請求項１１】
前記ノードおよび前記依存リンクおよび前記下層リンクおよび前記変動データを含むセルに関係するデータを、解像度レベルごとにまとめて記録媒体に記録する、請求項１から１０に記載の方法。
【請求項１２】
前記セルに関係するデータを空間充填曲線に沿う順序で前記記録媒体に記録する、請求項１１に記載の方法。
【請求項１３】
前記空間充填曲線はヒルベルト曲線またはＺ曲線である、請求項１２に記載の方法。
【請求項１４】
請求項１から１０のいずれか１項に記載の方法で生成された、前記ノードおよび前記依存リンクおよび前記下層リンクおよび前記変動データを含むセルに関係するデータが、解像度レベルごとにまとめて記録されたデータ記録媒体。
【請求項１５】
前記セルに関係するデータは空間充填曲線に沿う順序で記録されている、請求項１４に記載のデータ記録媒体。
【請求項１６】
前記空間充填曲線はヒルベルト曲線またはＺ曲線である、請求項１５に記載のデータ記録媒体。
【請求項１７】
請求項１から１０のいずれか１項に記載の方法で分解されたデータを、前記リンクによって詳細化に関係するセルを検索し、該セル内のノードを抽出して詳細化することにより、再構成する方法。
【請求項１８】
請求項９または１０に記載の方法で分解されたデータを、前記リンクによって詳細化に関係するセルを検索し、前記変化量が所定の範囲内の場合には詳細化を省略し、前記変化量が所定の範囲外の場合には前記セル内のノードを抽出して詳細化することにより、再構成する方法。
【請求項１９】
請求項１から１０のいずれか１項に記載の方法によって分解されたデータを、幾何構造と付随属性を独立に再構成する方法。
【請求項２０】
前記分解されたデータの再構成を連続してするとき、前回の再構成に用いたノードと今回の再構成に用いるノードを比較して、前回の再構成にのみ用いたノードについては単純化操作を行い、今回の再構成にのみ用いるノードについては詳細化操作を行う、請求項１７から１９のいずれか１項に記載の方法。
【請求項２１】
セル内に詳細化を行う必要のない領域がある場合に、該領域に含まれるノード検索し、該ノードは詳細化を行わない、請求項１７から２０のいずれか１項に記載の方法。
【請求項２２】
請求項１４から１６のいずれか１項に記載のデータ記録媒体を読み取り、前記リンクによって詳細化に関係するセルを検索し、該セル内のノードを抽出して詳細化することにより、分解されたデータを再構成する方法。
【請求項２３】
請求項１４から１６のいずれか１項に記載のデータ記録媒体を読み取り、前記リンクによって詳細化に関係するセルを検索し、前記変化量が所定の範囲内の場合には詳細化を省略し、前記変化量が所定の範囲外の場合には前記セル内のノードを抽出して詳細化することにより、分解されたデータを再構成する方法。
【請求項２４】
請求項１４から１６のいずれか１項に記載のデータ記録媒体を読み取り、分解されたデータを、幾何構造と付随属性を独立に再構成する方法。
【請求項２５】
前記分解されたデータの再構成を連続してするとき、前回の再構成に用いたノードと今回の再構成に用いるノードを比較して、前回の再構成にのみ用いたノードについては単純化操作を行い、今回の再構成にのみ用いるノードについては詳細化操作を行う、請求項２２から２４のいずれか１項に記載の方法。
【請求項２６】
セル内に詳細化を行う必要のない領域がある場合に、該領域に含まれるノード検索し、該ノードは詳細化を行わない、請求項２２から２５のいずれか１項に記載の方法。
【請求項２７】
請求項１４から１６のいずれか１項に記載のデータ記録媒体をキャッシュまたはバッファを介在させて読み取る、請求項２２から２６のいずれか１項に記載の方法。
【請求項２８】
非構造数値データを多重解像度表現により階層化する装置において、
離散的な解像度レベルごとに空間に周期格子状に敷き詰められたセルであって、ある解像度レベルのセルは当該解像度レベルよりも高い解像度レベルのセルを包含する関係にあるセルを設ける手段と、
所定のセルに、解像度および空間位置が前記セルの解像度レベルおよび空間位置とそれぞれ所定の範囲内で一致するノードを格納する手段と、
前記セルから、該セルが包含し、内部にノードを有する高解像度レベルのセルへ下層リンクを設ける手段を有することを特徴とする装置。
【請求項２９】
特定の解像度レベルのセルを追加する手段をさらに有する、請求項２８に記載の装置。
【請求項３０】
特定の解像度レベルまで最も単純化された数値データを詳細化し、該解像度レベルのセルを消去する手段をさらに有する、請求項２８または２９に記載の装置。
【請求項３１】
所定の解像度レベルよりも高い解像度レベルのセルをすべて削除する手段をさらに有する、請求項２８から３０のいずれか１項に記載の装置。
【請求項３２】
所定の解像度レベルよりも高い解像度レベルのセルを設けない、請求項２８から３０のいずれか１項に記載の装置。
【請求項３３】
全ての解像度レベルのセルを削除し、階層化されたデータを元のデータに復元する手段をさらに有する、請求項２８から３０のいずれか１項に記載の装置。
【請求項３４】
同じ解像度レベルの分解処理を並列に行う手段を有する、請求項２８から３３のいずれか１項に記載の装置。
【請求項３５】
ノード間の依存関係である依存リンクを、該ノードが属するセルの解像度レベルと、前記セルの相対的な位置関係と、前記セル内のノード番号により表現する手段を有する、請求項２８から３４のいずれか１項に記載の装置。
【請求項３６】
所定のセルからより高解像度レベルのセルへ詳細化されたときの付随属性および／または表面境界の変化量を示す変動データを生成する手段をさらに有する、請求項２８から３５のいずれか１項に記載の装置。
【請求項３７】
幾何構造と付随属性を独立に分解処理する手段を有する、請求項２８から３６のいずれか１項に記載の装置。
【請求項３８】
前記ノードおよび前記依存リンクおよび前記下層リンクおよび前記変動データを含むセルに関係するデータを、解像度レベルごとにまとめて記録媒体に記録する手段を有する、請求項２８から３７に記載の装置。
【請求項３９】
前記セルに関係するデータを空間充填曲線に沿う順序で前記記録媒体に記録する手段を有する、請求項３８に記載の装置。
【請求項４０】
前記空間充填曲線はヒルベルト曲線またはＺ曲線である、請求項３９に記載の装置。
【請求項４１】
請求項２８から３７のいずれか１項に記載の装置で分解されたデータを、前記リンクによって詳細化に関係するセルを検索し、該セル内のノードを抽出して詳細化することにより、再構成する装置。
【請求項４２】
請求項３６または３７に記載の装置で分解されたデータを、前記リンクによって詳細化に関係するセルを検索し、前記変化量が所定の範囲内の場合には詳細化を省略し、前記変化量が所定の範囲外の場合には前記セル内のノードを抽出して詳細化することにより、再構成する装置。
【請求項４３】
請求項２８から３７のいずれか１項に記載の装置によって分解されたデータを、幾何構造と付随属性を独立に再構成する装置。
【請求項４４】
前記分解されたデータの再構成を連続してするとき、前回の再構成に用いたノードと今回の再構成に用いるノードを比較して、前回の再構成にのみ用いたノードについては単純化操作を行い、今回の再構成にのみ用いるノードについては詳細化操作を行う手段を有する、請求項４１から４３のいずれか１項に記載の装置。
【請求項４５】
セル内に詳細化を行う必要のない領域がある場合に、該領域に含まれるノード検索し、該ノードは詳細化を行わない手段を有する、請求項４１から４４のいずれか１項に記載の装置。
【請求項４６】
請求項１４から１６のいずれか１項に記載のデータ記録媒体を読み取り、前記リンクによって詳細化に関係するセルを検索し、該セル内のノードを抽出して詳細化することにより、分解されたデータを再構成する装置。
【請求項４７】
請求項１４から１６のいずれか１項に記載のデータ記録媒体を読み取り、前記リンクによって詳細化に関係するセルを検索し、前記変化量が所定の範囲内の場合には詳細化を省略し、前記変化量が所定の範囲外の場合には前記セル内のノードを抽出して詳細化することにより、分解されたデータを再構成する装置。
【請求項４８】
請求項１４から１６のいずれか１項に記載のデータ記録媒体を読み取り、分解されたデータを、幾何構造と付随属性を独立に再構成する装置。
【請求項４９】
前記分解されたデータの再構成を連続してするとき、前回の再構成に用いたノードと今回の再構成に用いるノードを比較して、前回の再構成にのみ用いたノードについては単純化操作を行い、今回の再構成にのみ用いるノードについては詳細化操作を行う手段を有する、請求項４６から４８のいずれか１項に記載の装置。
【請求項５０】
セル内に詳細化を行う必要のない領域がある場合に、該領域に含まれるノード検索し、該ノードは詳細化を行わない手段をさらに有する、請求項４６から４９のいずれか１項に記載の装置。
【請求項５１】
請求項１４から１６のいずれか１項に記載のデータ記録媒体をキャッシュまたはバッファを介在させて読み取る手段を有する、請求項４６から５０のいずれか１項に記載の装置。
【請求項５２】
請求項１から１３のいずれか１項に記載の方法をコンピュータに実行させるデータ階層化プログラム。
【請求項５３】
請求項１から１３のいずれか１項に記載の方法をコンピュータに実行させるデータ階層化プログラムを記録した、コンピュータで読み取りが可能な記録媒体。
【請求項５４】
請求項１７から２７のいずれか１項に記載の方法をコンピュータに実行させるデータ再構成プログラム。
【請求項５５】
請求項１７から２７のいずれか１項に記載の方法をコンピュータに実行させるデータ再構成プログラムを記録した、コンピュータで読み取りが可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、多重解像度表現による非構造数値データの階層化に関する。
【０００２】
【従来の技術】
従来、多重解像度表現による非構造数値データの階層化方法は、大規模もしくは精細な非構造数値データを高速に可視化するために用いられている。ここで、非構造数値データとは、地図データ、地形データ、三次元オブジェクトデータ、三次元ボリュームデータ、粒子データなどを指す。これらはすべて、図１０の非構造数値データ４０のように、１個以上の節点４１と０個以上の要素４２で構成される。要素４２は複数の節点４１によって形状が定義される。要素４２は、例えば三次元オブジェクトデータにおいてはポリゴン、三次元ボリュームデータにおいては多面体に相当し、粒子データには相当するものがない。さらに、節点４１および要素４２にはデータの用途に応じて付随属性が定義される。例えば、三次元グラフィックス用途ならば反射率や透過率、数値シミュレーション用途ならば圧力や速度などの物理量が付随属性として用いられる。以降、特に断らない限り、数値データは非構造数値データのことを指す。また、多重解像度表現とは、複数レベルの解像度の数値データを容易に生成可能なデータ形式のことである。
【０００３】
従来の多重解像度表現による非構造数値データの階層化方法の一例が、例えば非特許文献１に記載されている。この方法は当初、ＭＴ（Ｍｕｌｔｉ−ＴｒｉａｎｇｕｌａｔｉｏｎまたはＭｕｌｔｉ−Ｔｅｓｓｅｌｌａｔｉｏｎ）と呼ばれていたが、後に対象数値データの次元によらない一般化された定義となり、ＭＣ（Ｍｕｌｔｉ−Ｃｏｍｐｌｅｘ）と命名されている。
【０００４】
この方法では、非構造数値データの多重解像度表現を得るために、空間的に局所的な単純化操作を用いる。単純化操作の方法は様々あるが、その一例として図１１に示すような節点除去がある。これによれば、非構造数値データの一部分４００は、節点４１０を節点４１１に縮重させた後に除去することで、４０１のように一部の要素も除去されて単純化される。このような単純化操作を非構造数値データの各部位に繰り返し適用していき、非構造数値データが所定の解像度になるまで続ける。その際、単純化操作は単純化誤差の少ないものから順に行っていく。ここで単純化誤差とは、単純化操作による見た目の変化を表す量である。単純化誤差も様々な定義が考えられるが、単純化によって影響を受ける範囲４００の最小包含球の直径、もしくは各座標軸に平行な最小包含直方体の最長辺を単純化誤差として定義する方法がある。単純化操作ごとに、詳細化データ、単純化誤差、さらに以前の単純化操作との依存関係を記録しておく。ここで、図１１に示すように、詳細化データ３３０とは、単純化操作の逆操作である詳細化操作に必要な情報であり、単純化操作により喪失する情報に相当する。詳細化データは単純化操作の方法によって内容が変わってくるが、単純化操作が節点除去である場合、分裂節点４１３（縮重節点４１１に相当）を分裂させて生成する挿入節点４１２（除去節点４１０に相当）の座標と付随属性、変形を受ける要素の範囲、挿入する要素の構成節点番号と付随属性が詳細化データの一例として考えられる。ところで、単純化誤差は、詳細化操作からの視点では、詳細化操作により確保される解像度と見ることができ、以降は単純化誤差のことを単に解像度と呼ぶことにする。
【０００５】
詳細化データ、解像度、依存関係の一連の情報を整理することにより、元の非構造数値データは、図１２に示すような詳細化操作の依存関係グラフの形で表現できる。このグラフにおいて、ノード２４は詳細化操作を表し、依存リンク２５は詳細化操作の依存関係を表している。また、元の数値データ２０は最下位ノード、一連の単純化の結果である単純化数値データ２１は最上位ノードとなっている。ノード間には依存関係という上下関係があるため、このグラフは広い意味での階層構造を有していると言える。この依存関係グラフのデータを階層化データと呼ぶことにする。元の数値データ２０、および、それにつながる依存リンク２５０は、今後不要なので階層化データには記録しない。元の数値データから階層化データを生成する一連の処理を分解という。
【０００６】
この依存関係に基づく順序で、都合に合った詳細化操作を取捨選択して行うことで、必要な部位のみを詳細化した数値データを得ることができる。例えば、図１３に示すように、ある空間範囲２６において解像度をある程度高めたい場合、単純化数値データ２１に対し、点線２６０で囲まれたノード２４に対応する詳細化操作を依存リンク２５に矛盾しない順序で行えばよい。点線２６０は、影響範囲が空間範囲２６と重なり、かつ、解像度が要求解像度より低い詳細化操作のノードを囲んでいる。さらに空間範囲２６で解像度を高めたい場合は、同様にして点線２６１で囲まれたノード２４に対応する詳細化操作を行えばよい。階層化データから任意に詳細化された数値データを生成する一連の処理を再構成という。この階層化データは、解像度を局所的に任意に変化させた数値データを再構成可能な、汎用性の高い多重解像度表現となっている。
【０００７】
この特徴を利用すれば、大規模な三次元非構造数値データでも、画質を損なうことなく少ないデータアクセスにより高速に可視化することができる。つまり、可視化画像の範囲外になる部位や、画像に詳細が反映されない遠方の部位は低解像度に、画像に詳細まで反映されうる視点近傍の重要な部位は高解像度にして非構造数値データを再構成し、これを可視化すればよい。再構成された非構造数値データは、階層化前の元の非構造数値データに比べ大幅にデータ量が削減されており、可視化処理の負荷を大きく減らすことができる。また、再構成の際、詳細化操作にあずからない大多数の詳細化データは参照されないため、データアクセスも大幅に削減できる。
【０００８】
【非特許文献１】
プロシーディングス・カナディアン・カンファレンス・オン・コンピュテーショナル・ジオメトリ、２０２〜２１０頁、１９９６年８月（Ｐｒｏｃｅｅｄｉｎｇｓ  Ｃａｎａｄｉａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ、ｐａｇｅｓ  ２０２−２１０，Ａｕｇｕｓｔ  １９９６）
【０００９】
【発明が解決しようとする課題】
上記従来技術の第１の問題点は、再構成の際に階層化データに対しランダムアクセスが頻発することである。その理由は、詳細化操作の複雑な依存関係を表す階層化データのデータ構造が不規則で構造的でないことに起因し、再構成に必要なデータが記録媒体上で細かな断片となって分散している場合が多いためである。階層化の利点は、データが大規模であればあるほど大きくなる。しかし、大規模データを格納するための大容量記録媒体は、ランダムアクセスが連続アクセスに対して桁違いに低速である磁気ディスクや磁気テープであるのが普通であるため、再構成が著しく遅延してしまうという問題がある。この問題を解決するために、ランダムアクセスによる遅延が磁気ディスクや磁気テープに比べて顕著ではない半導体メモリのような記録媒体に、階層化データを記録することも考えられるが、半導体メモリは容量あたりのコストが非常に高価であり、現実的ではない。また、記録媒体と再構成装置の間に、半導体メモリによるバッファやキャッシュを介在させることにより、ランダムアクセスをいくらか削減することができるが、そのためにはアクセスするデータが記録媒体上である程度局在している必要があり、データがまばらに分散している場合には効果が薄くなってしまう。
【００１０】
第２の問題点は、階層化データのサイズが元の数値データよりも増大してしまうことである。その理由は、冗長な情報である依存リンクデータが階層化データに含まれるためである。依存リンクデータは、記録しなくても詳細化データなどの他の情報により導き出すことができるが、非構造数値データの空間的不規則性ゆえに、それには多くの処理が必要となり、柔軟な再構成を高速に行うためには、依存リンクデータの記録が必須となる。とはいえ、これによるデータサイズの増大は、階層化対象となる数値データが大規模であるほど、無視できない問題となる。
【００１１】
第３の問題点は、再構成の際に依存関係グラフから必要ノードを探索する処理に無駄があることである。その理由は、ノード取捨選択の判定を必要以上の精度で行っているためである。取捨選択は、ノードの表す詳細化操作の解像度が要求解像度より低い空間領域に、詳細化操作の影響範囲が重なるかどうかで判定する。その重なり判定は、詳細化操作の解像度に応じた粗い精度で簡略化しても差し支えないところ、要求解像度と関わりなく一律に精細な精度で行っている。ストレスのないインタラクティブな可視化を実現するためにも、再構成には無駄のない処理による高速化の要請がある。
【００１２】
第４の問題点は、解像度だけではなく、付随属性も加味した多元的な基準での再構成ができないことである。その理由は、従来の方法では多元的な基準での再構成について何ら考慮されていないためである。付随属性の空間的な変化が少なく、表面境界を含まない領域では、解像度の基準から詳細化の必要があると判定されたとしても、要素境界を可視化するという特殊な場合を除き、詳細化による要素細分化の意味はなく、このような場合、解像度の基準だけでは、詳細化操作処理量と再構成数値データの無駄な増大を招いてしまう。そのため、付随属性も加味した多元的な基準での再構成が必要となる。
【００１３】
本発明の第１の目的は、再構成の際の階層化データに対するランダムアクセスを低減できる、多重解像度表現による非構造数値データの階層化方法を提供することにある。
【００１４】
本発明の第２の目的は、階層化データのサイズ増大を低減できる、多重解像度表現による非構造数値データの階層化方法を提供することにある。
【００１５】
本発明の第３の目的は、再構成に必要となるノードの探索処理を効率的に行える、多重解像度表現による非構造数値データの階層化方法を提供することにある。
【００１６】
本発明の第４の目的は、解像度に加えて付随属性も加味した多元的な基準での再構成が行える、多重解像度表現による非構造数値データの階層化方法を提供することにある。
【００１７】
【課題を解決するための手段】
上記第１の目的を達成するために、本発明は、階層化データを生成する際、空間的に規則階層構造を持つセルを用いて不規則な依存関係グラフを構造化し、ノード即ち詳細化操作の空間配置に関連付けて、ノードデータを記録媒体上に配置し、空間的に近傍のノードデータが記録媒体上でも近傍になる確率を高める。また、ノードデータを納めたセルのデータも空間配置を考慮した並びに記録媒体上に配置し、空間的に近傍のセルデータが記録媒体上でも近傍になる確率を高める。再構成に関与する詳細化操作が空間的に局在していることから、再構成に必要なデータも記録媒体上で局在するようになり、階層化データに対するランダムアクセスの低減を達成することができる。アクセスが局在していても不連続であることも多いため、キャッシュやバッファを介在させると、なお一層効果的にランダムアクセスの低減を達成することができる。
【００１８】
上記第２の目的を達成するために、本発明は、階層化データを生成する際、従来の方法における依存リンクのうち、高解像度方向への依存リンクは生成せず、代わりに、それよりも数の少ないセルの下層リンクを生成する。また、低解像度方向への依存リンクのデータ量は、セルの規則構造を利用して圧縮することができる。さらに、本発明においては、連続的な解像度ではなく、離散的な解像度レベルを再構成の基準に用いるが、詳細化操作の解像度レベルはセルの規則構造により自明となるため、ノードに格納しておく必要がない。これらの理由により、階層化データのサイズ増大の低減を達成することができる。
【００１９】
上記第３の目的を達成するために、本発明は、階層化データを生成する際、セルの空間的な大きさを、格納するノード即ち詳細化操作の解像度レベルにあわせ、再構成の際、ノード単位ではなくセル単位で探索を行う。これにより、解像度レベルに応じた精度の探索が行え、解像度レベルの許容する精度以下の近傍にあるノードが一括判定される。また、ノードは親を複数持つ複雑な依存グラフを構成している一方、セルは親を一つしか持たない単純な木構造を構成していることから、セル単位の探索の方が、手順が単純である。これらの理由により、再構成でのノード探索処理の効率化を達成することができる。
【００２０】
上記第４の目的を達成するために、本発明は、階層化データを生成する際、セル以下の各レベルのセルまで詳細化を行った場合の各付随属性の変動および、表面境界の凹凸変動をセルに保持しておくこともでき、再構成の際、解像度の基準からはセルによる詳細化が必要であると判断されても、このデータを参照することにより、表面境界の変動が要求解像度の許す範囲内で、かつ付随属性の変動が指定された許容誤差以内の場合にセル以下のレベルの詳細化を省略する。このようにして、解像度に加えて付随属性も加味した多元的な基準での再構成を達成することができる。
【００２１】
【発明の実施の形態】
次に、本発明の実施の形態について、図面を参照して説明する。
【００２２】
図１を参照すると、本発明の実施の形態のうち、分解を行うシステムが示されており、階層化を行う数値データを格納するための数値データ格納装置１６と、数値データの分解により、階層化データの生成、階層追加を行う分解装置１０と、処理途中および処理後の階層化データを格納するための階層化データ格納装置１７とから構成されている。
【００２３】
数値データ格納装置１６と階層化データ格納装置１７は、半導体メモリ、磁気ディスク装置、光ディスク装置、その他のデータ格納装置であってよい。
【００２４】
分解装置１０は、数値データ入力部１００と、単純化操作生成部１０１と、セル管理部１０２と、ノード管理部１０３と、詳細化データ生成部１０４と、単純化操作実行部１０５とを備えている。
【００２５】
数値データ入力部１００は、階層化データを新規に生成する際に、数値データ格納装置１６に格納された元の数値データ３０を、階層化データの構成要素である単純化数値データ３１として階層化データ格納装置１７に格納する。
【００２６】
単純化操作生成部１０１は、階層化データ格納装置１７に格納された単純化数値データ３１を参照し、可能なすべての単純化操作の候補を生成し、単純化誤差をもとにそれらの優先順位付けを行い、随時、セル管理部１０２と、詳細化データ生成部１０４と、単純化操作実行部１０５とに、最優先の単純化操作に関わる情報を出力する。単純化操作に関わる情報には、単純化操作を特定するための情報と、単純化誤差と、単純化操作の影響範囲とが含まれる。単純化操作を特定するための情報とは、例えば単純化操作が節点除去である場合、除去節点番号と縮重節点番号のことである。単純化操作の影響範囲は、多面体や多角形で表される厳密な範囲でなくてもよく、処理の単純化のために、例えば、影響範囲における各座標成分の範囲で代用してもよい。単純化操作は、節点除去や辺収縮など複数の種類を利用してもよいが、単一の種類の単純化操作に限定し、詳細化操作の規則を統一した方が、少ない情報量で詳細化データを記述できる。
【００２７】
セル管理部１０２は、階層化データ格納装置１７に格納された階層化データのもう一つの構成要素であるセルデータ３２を管理する。セルは詳細化操作の依存関係グラフにおけるノードを複数格納するためのデータ構造であり、解像度および影響範囲が近いノードは一つのセルにまとめられる。複数のセルは、後述のとおり、解像度を基準とした規則的な階層構造を成しており、親子関係にあるセル間は下層リンクによって結ばれている。セル管理部１０２は、単純化操作生成部１０１から出力された単純化誤差と、単純化操作の影響範囲、即ち、詳細化操作の解像度と影響範囲をもとに、これから生成されるノードを格納するセルを特定し、セルが存在していない場合は、これを新規に生成し、このセルにつながる下層リンクも生成、更新する。また、特定されたセル内にノードを格納するために必要な情報、例えばセルデータの記録媒体上での位置などを、ノード管理部１０３に出力する。分解の過程が進むに従い、単純化数値データ３１は、単純化によりデータサイズが縮小していくが、セルデータ３２は、セルの生成によりデータサイズが拡大していく。
【００２８】
ノード管理部１０３は、階層化データ格納装置１７に格納されたセルデータ３２に含まれるノードデータを管理する。セル管理部１０２から出力された情報をもとに、セル内にノードを生成し、詳細化データ生成部１０４より出力された詳細化データをノード内に格納し、このノードにつながる依存リンクの生成、更新も行う。
【００２９】
詳細化データ生成部１０４は、階層化データ格納装置１７に格納された単純化数値データ３１を参照して、単純化操作生成部１０１から出力された単純化操作に対応する詳細化データを生成し、ノード管理部１０３に出力する。
【００３０】
単純化操作実行部１０５は、階層化データ格納装置１７に格納された単純化数値データ３１に対し、単純化操作生成部１０１から出力された単純化操作を実行する。
【００３１】
次に、図２を参照して、本システムの動作について説明する。
【００３２】
まず、新規に階層化データを生成する場合、数値データ入力部１００は、数値データ格納装置１６に格納された元の数値データ３０を、階層化データの単純化数値データ３１として階層化データ格納装置１７に格納する（ステップＡ００）。既存の階層化データを再分解により階層追加する場合、このステップは不要である。
【００３３】
次に、単純化操作生成部１０１は、階層化データ格納装置１７に格納された単純化数値データ３１をもとに、可能なすべての単純化操作の候補を生成し、単純化誤差をもとにそれらの優先順位付けを行い、最優先の単純化操作を選定する。この処理は、初回に生成した単純化操作の候補とそれらの優先順位の情報を保持しておけば、次回からは単純化数値データに変更のあった部位の単純化操作についてのみ更新することで高速に行える。もし、単純化操作の候補が存在しない場合は、分解処理を終了する（ステップＡ０１）。
【００３４】
優先順位付けは、単純化誤差そのもので行ってもよいが、単純化誤差をＥとして、ｉｎｔ（ｌｏｇ２（Ｌ／Ｅ））で定義される解像度レベルによって行い、解像度レベルが高いほど、高い優先順位をつける。ただし、ｉｎｔは小数点を切り捨てて整数化する関数である。また、Ｌは誤差の基準とする距離であり、通常は元の数値データの各座標軸方向の幅のうち最大値を用いるが、他に基準がある場合はこれを用いてもよい。解像度レベルが高いほど、解像度が高く、誤差が少ないということになる。単純化誤差を離散化した解像度レベルを用いると、単純化誤差を用いる場合と比べ優先順位が前後するが、再構成は解像度レベルで区分けされたセル単位で処理を行うため、結果にほとんど差はない。また、単純化誤差が異なっていても解像度レベルが同じになる単純化操作が通常複数存在するため、単純化操作の順序の自由度が増し、影響範囲の競合しない同じ優先順位の単純化操作に関する分解処理を並列に行うことも可能となる。ところで、このように解像度レベルの高い順に単純化操作を行っていったとしても、解像度レベルが以前の単純化操作のものより低いとは限らず、このような場合、以前の単純化操作の解像度レベルを今回の単純化操作の解像度レベルとし、解像度レベルが分解の過程で増加しないようにする。
【００３５】
次に、単純化操作生成部１０１は、選定された単純化操作の解像度レベルが、あらかじめ与えられた指定レベル以上であるかを確認し、そうでない場合は、分解処理を終了する（ステップＡ０２）。
【００３６】
次に、セル管理部１０２は、単純化操作生成部１０１の生成した単純化操作に対応する詳細化操作のノードを格納するセルを、単純化操作の解像度レベルと影響範囲により決定する（ステップＡ０３）。
【００３７】
セルとは、ノードを複数格納するためのデータ構造である一方、空間的な観点では、空間に格子状に敷き詰められた仮想的な立方体（一次元空間の場合は線分、二次元空間の場合は正方形、多次元空間の場合は超立方体）である。解像度レベルごとに異なる大きさのセルの格子があり、解像度レベルの異なるセル間に親子関係が成り立っている。つまり、セルは、それよりも低い各解像度レベルにおいて、ただ一つのセルに包含されている。通常、セルの一辺を、その解像度レベルをもつ単純化操作または詳細化操作が持ちうる最大の影響範囲が収まる大きさとする。これより大きい場合は、再構成の精度が無駄に粗くなってしまい、これより小さい場合は、後述する依存リンクデータの圧縮が行えなくなる。以降、解像度レベルＲの定義より、セルの一辺の長さをＬ×２−Ｒとして説明する。
【００３８】
ノードを格納するセルの決定方法は様々に考えられるが、例えば、詳細化操作の影響範囲の最小包含球の中心、もしくは各座標軸に平行な最小包含直方体の重心を含む、同じ解像度レベルのセルに格納する。中心や重心がセル境界上にある場合は、境界を共有するセルのどれか一つに格納する。
【００３９】
次に、セル管理部１０２は、階層化データ格納装置１７に格納されたセルデータ３２を参照し、ノードを格納するセルが既存かどうかを確認し（ステップＡ０４）、存在しない場合は新規にセルを生成し（ステップＡ０５）、そのセルよりも高い解像度レベルの既存のセルを包含する場合は、そのセルへの下層リンクも生成する（ステップＡ０６）。
【００４０】
下層リンクは、セルが直接包含する高い解像度レベルのセルへの単方向リンクである。分解処理の立場で見れば、直系の子に相当する既存のセルへの単方向リンクである。
【００４１】
付随属性も加味した多元的な基準による再構成が可能な階層化データを生成する場合は、下層リンクの生成と共に、下層変動データの生成も行い、セルに格納する。下層変動データとは、セル自身、および、子やそれ以下の各レベルの子のセルまで詳細化を行った場合の、表面境界および各付随属性のレベルごとの変動を表すデータである。各下層レベルの子のセルは、複数存在するのが普通であるので、それらのセルの詳細化による変動を集計したものを、そのレベルの変動とする。集計方法は様々に考えられるが、例えば、変動の最大値をとる方法がある。
【００４２】
セルの記録媒体上でのデータ配置についてであるが、再構成の際のアクセスが局在するように、解像度レベル別にセルデータをまとめ、同じ解像度レベルのセルデータは、ヒルベルト曲線、Ｚ曲線などの近傍保存性のよい空間充填曲線に沿う並びで、記録媒体上に配置するのが好ましい。
【００４３】
次に、ノード管理部１０３は、セル管理部１０２が手配したセル内にノードを生成する（ステップＡ０７）。
【００４４】
次に、詳細化データ生成部１０４は、階層化データ格納装置１７に格納された単純化数値データ３１を参照して、単純化操作生成部１０１が生成した単純化操作に対応する詳細化データを生成し、ノード管理部１０３は、先ほど生成したノードに、この詳細化データを格納する（ステップＡ０８）。
【００４５】
次に、ノード管理部１０３は、生成したノードに対応する詳細化操作の影響範囲をもとに、既存のノードとの間の依存関係を見出し、関係する依存リンクを生成、更新する（ステップＡ０９）。
【００４６】
依存リンクは、詳細化操作を行う前提となる詳細化操作への単方向リンクである。分解処理の立場で見れば、依存関係にある既存のノードから新規のノードへの単方向リンクである。依存リンクは、依存するノードが属するセルの解像度レベルおよび相対的な位置関係と、セル内ノード番号とで表現すれば、データを圧縮できる。つまり、依存するノードが含まれうるセルは、セルの構造的配置から明確に限定され、セル自身、もしくは親やそれ以上のレベルの親のセル、またはそれらから直接隣接する同レベルのセルのいずれかになる。このため、相対的な位置関係により少ないビット数でセルを指定できる。直接隣接するとは、セルの頂点を含めた境界を共有しているという意味である。従って、三次元の場合は前後左右上下と斜めも含め、２６個の直接隣接セルが存在し、５ビットあればその位置関係を表現できる。解像度レベルは数十から数百段程度あれば十二分であるため、数ビットから８ビット程度あれば表現できる。また、セル内ノード番号であるが、セルに含まれるノード数もさほど多くはないので、これについても少ないビット数で表現できる。
【００４７】
次に、単純化操作実行部１０５は、階層化データ格納装置１７に格納された単純化数値データ３１に対し、単純化操作生成部１０１が生成した単純化操作を実行する（ステップＡ０Ａ）。
【００４８】
再びステップＡ０１から処理を繰り返す。
【００４９】
これら一連の分解処理は、付随属性を含まない要素と節点の幾何構造と、各付随属性とを分けて行うこともできる。この場合、処理を独立に行う都合上、階層化データは、幾何構造に関する部分と各付随属性に関する部分とで、記録媒体上で分けて格納した方がよい。付随属性の階層化データは、単純化数値データの節点と要素の付随属性データと、詳細化データのうち付随属性に関わる部分と、もしあれば、付随属性の下層変動データとで構成される。幾何構造の階層化データは、付随属性に関わる部分を一切省き、代わりに、付随属性の階層化データを参照するためのリンクに相当する情報を、セルデータに挿入する。独立に分解処理を行う手順は次のようになる。まず、付随属性を無視して、幾何構造のみの分解を行い、幾何構造のみの階層化データを生成、更新する。それと同時に、付随属性の階層化データにおける各データ要素の配置を計算し、付随属性の階層化データへのリンクに相当する情報をセルデータに格納し、また、各データ要素の配置の情報を別に保持しておく。次に、この保持しておいた情報を参照して、各付随属性の階層化データを生成、更新する。これにより、階層化データの付随属性の増減や、付随属性のみが時間変化するような時系列データにおいて、時刻ステップの追加、削除、間引きが行いやすくなる。
【００５０】
ところで、必要以上に高い解像度レベルのセルを除去することで、データ圧縮を行うこともできる。ただし、除去した解像度レベルの詳細化は不可能になるので、非可逆圧縮である。高周波成分の除去による画像データの非可逆圧縮と似通っている。このデータ圧縮は、階層化データの生成、階層追加後に行ってもよいし、生成中に行ってもよい。後者は、除去するセルを初めから生成しない方法であり、階層化データの生成開始後、単純化操作の解像度レベルが所定のレベルに下がるまで、セル生成を停止することで実施できる。
【００５１】
図３を参照すると、本発明による階層化データは、単純化数値データ２１と、セル２２と、直系の子のセルへの単方向リンクである下層リンク２３と、セル内に格納されたノード２４と、依存するノードへの単方向リンクである依存リンク２５とから構成されている。図中、点線で示された、元の数値データ２０と、そこを起点とする依存リンク２５０は、必要がないので階層化データには記録されない。図１２と比較すると、本発明による階層化データは、従来の方法による階層化データとは異なり、セルと下層リンクが追加され、依存リンクが単方向リンクになっている。
【００５２】
図４は、本発明による階層化データのデータ構造の一例を示す図である。
【００５３】
階層化データは、単純化数値データ３１と、セルデータ３２とから構成されている。
【００５４】
単純化数値データ３１は、節点データ３１０と、要素データ３１１とから構成されている。
【００５５】
節点データ３１０は、各節点の座標と付随属性を含む。付随属性はない場合もあれば、多数ある場合もある。
【００５６】
要素データ３１１は、各要素の構成節点番号と付随属性を含む。粒子データの階層化の場合は、このデータは存在しない。付随属性はない場合もあれば、多数ある場合もある。また、節点の付随属性と共通の場合もあれば、そうでない場合もある。
【００５７】
セルデータ３２は、下層リンクデータ３２０と、下層変動データ３２１と、ノードデータ３３とから構成されている。
【００５８】
下層リンクデータ３２０は、リンク先のセルデータの記録媒体上での位置、もしくはセルを一意に識別できる番号などで表現される。
【００５９】
下層変動データ３２１は、表面境界および各付随属性の下層レベル毎の変動データから成っている。多元的な基準での再構成を考えない場合、このデータは必要ない。
【００６０】
ノードデータ３３は、詳細化データ３３０と、依存リンクデータ３３１とから構成されている。
【００６１】
依存リンクデータ３３１は、前述のとおり、依存先のノードが含まれるセルの解像度レベルと、セルの相対的な位置関係と、セル内ノード番号とで構成されている。依存リンクデータの圧縮を考えない場合は、この限りではなく、リンク先のノードデータの記録媒体上での位置、もしくはノードを一意に識別できる番号などで表現される。
【００６２】
節点データ３１０、要素データ３１１、下層変動データ３２１、詳細化データ３３０は、各付随属性に関わる部分を分離し、記録媒体上でそれぞれ別の場所に分けて格納してもよい。これにより、階層化データにおける付随属性の増減や、時系列データの対応、つまり時刻ステップの追加、削除、間引きが行いやすくなる。
【００６３】
図５を参照すると、本発明の実施の形態のうち、逆分解を行うシステムが示されており、復元された数値データを格納するための数値データ格納装置１６と、階層化データの逆分解により、階層削減、数値データの復元を行う逆分解装置１１と、処理途中および処理後の階層化データを格納するための階層化データ格納装置１７とから構成されている。
【００６４】
逆分解とは、後述する再構成と同様に、分解の逆操作であるが、階層化データが変更される点で再構成と異なり、主に階層化データのメンテナンスに用いる。逆分解により、階層化データの階層を削減することができ、これを最後まで行えば、元の数値データを復元することができる。
【００６５】
数値データ格納装置１６と階層化データ格納装置１７は、半導体メモリ、磁気ディスク装置、光ディスク装置、その他のデータ格納装置であってよい。
【００６６】
逆分解装置１１は、数値データ出力部１１０と、セル管理部１１２と、ノード管理部１１３と、依存関係解決部１１４と、詳細化操作実行部１１５とを備えている。
【００６７】
数値データ出力部１１０は、階層化データ格納装置１７に格納された逆分解後の階層化データの単純化数値データ３１を、数値データ格納装置１６に格納する。階層化データを完全に逆分解すれば、この数値データ３０は、復元された元の数値データとなる。
【００６８】
セル管理部１１２は、階層化データ格納装置１７に格納された階層化データのセルデータ３２を管理する。削除すべきセルを探索し、そのセルにアクセスするために必要な情報、例えばセルデータの記録媒体上での位置などを、ノード管理部１１３に出力する。また、すべてのノードの削除が完了したセルの削除と、そのセルにつながる下層リンクの削除、更新も行う。逆分解の過程が進むに従い、単純化数値データ３１は、詳細化によりデータサイズが拡大していくが、セルデータ３２は、セルの削除によりデータサイズが縮小していく。
【００６９】
ノード管理部１１３は、階層化データ格納装置１７に格納されたセルデータ３２に含まれるノードデータを管理する。セル管理部１１２から出力された情報をもとに、削除すべきセル内のノードを抽出し、そのノードにアクセスするために必要な情報、例えばノードデータの記録媒体上での位置などを、依存関係解決部１１４に出力する。また、詳細化操作が完了し、削除可能になったノードにつながる依存リンクの削除、更新も行う。
【００７０】
依存関係解決部１１４は、ノード管理部１１３から出力された情報をもとに、削除すべきノードのリストを作成し、リストされたノードの詳細化データなどの情報を、依存関係を満たす順序で詳細化操作実行部１１５に出力する。また、削除可能になったノードの情報、例えばノードデータの記録媒体上での位置などを、ノード管理部１１３に出力する。
【００７１】
詳細化操作実行部１１５は、階層化データ格納装置１７に格納された単純化数値データ３１に対し、依存関係解決部１１４から出力された詳細化データをもとに詳細化操作を実行する。
【００７２】
次に、図６を参照して、本システムの動作について説明する。
【００７３】
まず、セル管理部１１２は、階層化データ格納装置１７に格納された階層化データにおいて、削除すべきセル、つまり、解像度レベルが、あらかじめ与えられた指定レベルより低いセルを探索する（ステップＡ１０）。ノード管理部１１３は、そのセル内のノードを抽出し、依存関係解決部１１４は、そのノードをリストに登録する（ステップＡ１１）。リストは、ノードデータの記録媒体上での位置などのリストでもよいし、明示的にリストを作成せずにノード自身に登録済みのマークをつけることで代替してもよい。
【００７４】
次に、依存関係解決部１１４は、リストされたノードのうち、依存関係が満たされていながら未処理のもの、つまり、ノードに対応する詳細化操作がまだ行われておらず、すべての依存先ノードに対応する詳細化操作が完了しているノードを検索する（ステップＡ１２）。詳細化操作実行部１１５は、階層化データ格納装置１７に格納された単純化数値データ３１に対し、検索されたノードに対応する詳細化操作を実行する（ステップＡ１３）。ノード管理部１１３は、検索されたノードにつながる依存リンクの削除、更新を行う（ステップＡ１４）。ステップＡ１２において、依存先ノードが単純化数値データの場合は、対応する詳細化操作が完了しているとみなす。
【００７５】
次に、セル管理部１１２は、削除すべきセルを探索し（ステップＡ１５）、格納しているノード共々セルを削除し、そのセルにつながる下層リンクの削除、更新も行う（ステップＡ１６）。ここで行うセルの探索はステップＡ１０と同じであるので、ステップＡ１０の探索結果を保持しておき、それを利用して探索を省略してもよい。
【００７６】
次に、数値データ出力部１１０は、階層化データ格納装置１７に格納された逆分解後の階層化データの単純化数値データ３１を、数値データ格納装置１６に格納する（ステップＡ１７）。階層化データを完全に逆分解すれば、この数値データは、復元された元の数値データとなる。階層化データの階層削減のみが目的である場合、このステップは不要である。
【００７７】
図７を参照すると、本発明の実施の形態のうち、再構成を行うシステムが示されており、再構成を行う階層化データを格納するための階層化データ格納装置１７と、階層化データから数値データの再構成を行う再構成装置１２と、再構成された数値データを格納するための再構成数値データ格納装置１８とから構成されている。
【００７８】
再構成とは、前述した逆分解と同様に、分解の逆操作であるが、階層化データが一切改変されない点で逆分解と異なり、主に階層化データの可視化や、数値シミュレーションへの再利用のために用いる。
【００７９】
階層化データ格納装置１７と再構成数値データ格納装置１８は、半導体メモリ、磁気ディスク装置、光ディスク装置、その他のデータ格納装置であってよい。
【００８０】
再構成装置１２は、数値データ複製部１２０と、セル管理部１２２と、ノード管理部１２３と、依存関係解決部１２４と、詳細化操作実行部１２５とを備えている。
【００８１】
数値データ複製部１２０は、階層化データ格納装置１７に格納された階層化データの単純化数値データ３１を、再構成数値データ格納装置１８に格納する。この数値データ３４は、その後の詳細化操作によりデータサイズが拡大していき、最終的に再構成数値データとなる。
【００８２】
セル管理部１２２は、階層化データ格納装置１７に格納された階層化データのセルデータ３２を管理する。詳細化操作を行うべきセルを探索し、そのセルにアクセスするために必要な情報、例えばセルデータの記録媒体上での位置などを、ノード管理部１２３に出力する。
【００８３】
ノード管理部１２３は、階層化データ格納装置１７に格納されたセルデータ３２に含まれるノードデータを管理する。セル管理部１２２から出力された情報をもとに、詳細化操作を行うべきセル内のノードを抽出し、そのノードにアクセスするために必要な情報、例えばノードデータの記録媒体上での位置などを、依存関係解決部１２４に出力する。また、依存関係解決部１２４からノードへのアクセス要求を受け付け、要求されたノードにアクセスするために必要な情報を依存関係解決部１２４に返す。
【００８４】
依存関係解決部１２４は、ノード管理部１２３から出力された情報をもとに、詳細化操作を行うべきノードのリストを作成し、リストされたノードの詳細化データなどの情報を、依存関係を満たす順序で詳細化操作実行部１２５に出力する。また、依存関係を満たすために必要なノードがリストに未登録である場合、ノード管理部１２３に必要ノードへのアクセス要求を出し、返された情報により必要ノードをリストに追加する。
【００８５】
詳細化操作実行部１２５は、再構成数値データ格納装置１８に格納された再構成数値データ３４に対し、依存関係解決部１２４から出力された詳細化データをもとに詳細化操作を実行する。
【００８６】
次に、図８を参照して、本システムの動作について説明する。
【００８７】
まず、数値データ複製部１２０は、階層化データ格納装置１７に格納された階層化データの単純化数値データ３１を、再構成数値データ格納装置１８に格納する（Ａ２０）。
【００８８】
次に、セル管理部１２２は、階層化データ格納装置１７に格納された階層化データにおいて、詳細化操作を行うべきセル、つまり、解像度レベルが、あらかじめ与えられた要求レベルより低いセルを探索する（ステップＡ２１）。ノード管理部１２３は、そのセル内のノードを抽出し、依存関係解決部１２４は、そのノードをリストに登録する（ステップＡ２２）。リストは、ノードデータの記録媒体上での位置などのリストでもよいし、明示的にリストを作成せずにノード自身に登録済みのマークをつけることで代替してもよい。
【００８９】
要求レベルは、例えば、詳細化したい部位は高い要求レベル、その他の部位は低い要求レベルというように、場所によって変わってもよい。その場合、ステップＡ２１の探索条件である、要求レベルより解像度レベルが低いセルとは、セル内の領域における要求レベルの最大値よりも解像度レベルが低いセルという意味になる。
【００９０】
詳細化操作を行うべきセルの探索は、セルと下層リンクで構築された木によって行うが、探索方法は、深さ優先探索、幅優先探索などいずれでもよい。ただし、セルデータが記録媒体上で解像度レベル別にまとまっている場合は、幅優先探索が最もアクセス局在性が高く、好適である。
【００９１】
詳細化操作を行うべきノードの探索は、セル単位で行い、探索されたセル内のすべてのノードをリストに登録するのが基本であるが、さらに探索精度を高めたい場合、セル内の一部の領域で探索条件を満たさない場合に限り、ノード毎に要求レベルより解像度レベルが低いかどうかの判定を行い、判定に合格したノードのみをリストに追加すればよい。処理量は増加するが、セル内の全領域で探索条件を満たす場合と、全く満たさない場合は、処理内容に変更はなく、セル単位で処理を行うため、セルを使わずノードを直接探索する従来の方法より依然高速である。
【００９２】
セルに下層変動データがある場合、解像度に加えて付随属性も加味した多元的な基準での再構成が行える。下層変動データによって、要求レベルまで詳細化した場合の、表面境界および各付随属性の変動がわかる。ここで、下層変動データについて、付随属性番号をｉ、セルからの相対解像度レベルをｊとして、表面境界の変動値をＳｊ、付随属性の変動値をＡｉｊとする。また、再構成処理に先立って与えられた要求レベルをＲ、付随属性の許容誤差をＥｉとする。また、現在のセルの解像度レベルをＲ０とする。０≦∀ｊ＜Ｒ−Ｒ０および∀ｉにおいて、Ｓｊ≦ＲかつＡｉｊ≦Ｅｉが成り立てば、つまり、現在のセルの領域を要求レベルまで詳細化した場合の、表面境界とすべての付随属性についての変動が、許容誤差以内であれば、前述の探索条件を満たしていても、現在のセルおよびその子のセルを探索から除外する。これにより、付随属性の空間変化が少ない領域では、詳細化が抑止されて要素が粗くなり、変化が急な領域では、通常どおり詳細化されて要素が細かくなった数値データを再構成できる。また、表面境界の変動のみを加味した再構成も行え、この場合、表面境界から離れた領域や、緩やかな凹凸の表面境界付近では、詳細化が抑止されて要素が粗くなり、細かな凹凸の表面境界付近では、通常どおり詳細化されて要素が細かくなった数値データを再構成できる。
【００９３】
次に、依存関係解決部１２４は、リストされた各ノードについて、依存先のすべてのノードがリストに登録されているかを確認する（ステップＡ２３）。未登録の依存先ノードがあれば、それをノード管理部１２３に照会し、リストに登録する（ステップＡ２４）。依存先のノードが単純化数値データである場合は、リストに登録する必要はない。
【００９４】
次に、依存関係解決部１２４は、リストされたノードのうち、依存関係が満たされていながら未処理のもの、つまり、ノードに対応する詳細化操作がまだ行われておらず、すべての依存先ノードに対応する詳細化操作が完了しているノードを検索する（ステップＡ２５）。詳細化操作実行部１２５は、階層化データ格納装置１８に格納された再構成数値データ３４に対し、検索されたノードに対応する詳細化操作を実行する（ステップＡ２６）。ステップＡ２５において、依存先ノードが単純化数値データの場合は、対応する詳細化操作が完了しているとみなす。
【００９５】
図９を参照すれば、単純化数値データ２１において、ある空間範囲２６で解像度レベルを２に高めたい場合、言い換えれば、要求レベルがある空間範囲２６においては２で、その他の領域では０である場合、前述の動作により、単純化数値データ２１に対し、点線２６０で囲まれたセル２２に含まれるノード２４に対応する詳細化操作を依存リンク２５に矛盾しない順序で行い、要求レベルを満たした数値データを再構成することができる。さらに、空間範囲２６で解像度レベルを４に高めたい場合、言い換えれば、要求レベルがある空間範囲２６においては４で、その他の領域では０である場合、同様にして点線２６１で囲まれたセル２２に含まれるノード２４およびノード２４０に対応する詳細化操作を行い、要求レベルを満たした数値データを再構成することができる。ここで、ノード２４０は、要求レベル以上のセルに含まれており、本来、再構成に関与しないはずであるが、他のノードの依存関係を満たすために必要となっている。
【００９６】
これら一連の再構成処理は、付随属性を含まない要素と節点の幾何構造と、各付随属性とを分けて行うこともできる。このようにすれば、再構成する付随属性の切り替えや増減を行う際、幾何構造の再構成を省略できるので効率がよい。
【００９７】
ところで、連続して再構成を行う場合、次のようにすることもできる。まず、前回の再構成数値データと、その再構成に用いたノードを記録しておき、今回の再構成で用いるノードと比較する。次に、前回の再構成数値データに対し、前回にしかないノードに対応する単純化操作を行い、さらに、今回にしかないノードに対応する詳細化操作を行う。前回と今回に共通するノードに関しては単純化操作も詳細化操作も行わない。単純化数値データではなく、前回の再構成数値データをもとに再構成を行うので、差分再構成と呼ぶことにする。差分再構成は、目安として、前回と今回で共通するノード数が、前回にしかないノード数よりも多ければ、通常の再構成よりも有利となる。
【００９８】
なお、上記の分解・再分解・再構成システムは、専用のハードウェアにより実現する以外に、その機能を実現するためのプログラムを、コンピュータで読み取りが可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行するものであってもよい。コンピュータで読み取りが可能な記録媒体とは、半導体メモリ、磁気ディスク、光ディスク、その他の記録媒体、コンピュータシステムに内蔵されるハードディスク装置等の記憶装置を指す。
【００９９】
【発明の効果】
以上説明したように、本発明によれば、以下のような効果がある。
【０１００】
まず、分解においては以下のような効果を有する。
【０１０１】
セルを用いて不規則な依存関係グラフを構造化し、ノード即ち詳細化操作の空間配置に関連付けて、ノードデータを記録媒体上に配置し、空間的に近傍のノードデータが記録媒体上でも近傍になる確率を高めている。また、セルデータも空間配置を考慮した並びに記録媒体上に配置し、空間的に近傍のセルデータが記録媒体上でも近傍になる確率を高めている。このため、再構成に関与する詳細化操作が空間的に局在していることから、再構成に必要なデータも記録媒体上で局在するようになり、階層化データに対するランダムアクセスを低減できる。アクセスが局在していても不連続であることも多いため、キャッシュやバッファを介在させると、なお一層効果的にランダムアクセスを低減できる。
【０１０２】
さらに、従来の方法における双方向の依存リンクのうち、高解像度方向への依存リンクは生成せず、代わりにセルの下層リンクを生成する。セルには一つ以上のノードが含まれるため、セルの数はノードの数より少なく、かつノードは一つ以上の親を持つが、セルは必ず一つの親しか持たないため、下層リンク数は依存リンク数より大幅に少なくなる。このため、高解像度方向へのリンクのデータ量を削減することができる。
【０１０３】
さらに、従来の方法における双方向の依存リンクのうち、低解像度方向への依存リンクを、依存先のノードが含まれるセルの相対的な位置関係および、セル内ノード番号により記述する。依存するノードが含まれうるセルの範囲は、セルの構造的配置から明確に限定され、また、セルの保持するノード数もさほど多くはないので、少ないビット数でセルおよびセル内のノードを指定できる。このため、低解像度方向へのリンクのデータ量も削減することができる。
【０１０４】
さらに、詳細化操作の解像度をノードに格納しておく必要がない。従来の方法においては、算出に手間がかかるこの情報を、高速化のためにノードに格納しておく必要があった。その必要がないのは、再構成の基準とするのは解像度ではなく、離散的な解像度レベルであり、ノードの解像度レベルは、ノードを含んでいるセルの規則的な階層構造によって容易に特定できるからである。このため、ノードのデータ量も削減することができる。
【０１０５】
また、逆分解においては以下のような効果を有する。
【０１０６】
逆分解では、分解と全く逆の操作が行えるため、階層数を削減した階層化データが必要な場合や、元の数値データが必要な場合に備えて、元の数値データを保持しておく必要がなくなり、データ格納装置を有効利用できる。
【０１０７】
そして、再構成においては以下のような効果を有する。
【０１０８】
再構成では、分解で生成された階層化データを利用し、この階層化データは、空間的に近傍のセルデータおよびノードデータの記録媒体上での近傍性が高い。このため、再構成に関与する詳細化操作が空間的に局在していることから、再構成に必要なデータも記録媒体上で局在するようになり、階層化データに対するランダムアクセスを低減できる。アクセスが局在していても不連続であることも多いため、キャッシュやバッファを介在させると、なお一層効果的にランダムアクセスを低減できる。
【０１０９】
さらに、分解で生成された階層化データにおいて、セルの空間的な大きさが、格納しているノード即ち詳細化操作の解像度レベルに合わせた大きさであるのを利用して、ノード単位ではなくセル単位で探索を行う。これにより、解像度レベルに応じた精度の探索が行え、解像度レベルの許容する精度以下の近傍にあるノードが一括判定されるので、再構成における探索処理を効率化できる。さらに、ノードは親を複数持つ複雑な依存グラフを構成している一方、セルは親を一つしか持たない単純な木構造を構成していることから、セル単位の探索の方が単純な手順で行うことができ、このことからも処理を効率化できる。
【０１１０】
さらに、下層変動データがセルに保持されていれば、表面境界および各付随属性の観点からも、セルおよびそれ以下の子のセルによる詳細化操作が必要かどうかの判断ができる。このため、解像度に加えて表面境界や付随属性も加味した多元的な基準での再構成が行え、無駄な詳細化操作と、無駄な節点数、要素数の増加を避けることができる。
【０１１１】
なお、本発明によっても、データ階層化が次元に依存せず、単純化操作方法に依存しない点は損なわれない。また、ＢＦＣ（境界適合）格子などの構造格子や、それらを組み合わせた重合格子、マルチブロック格子などの数値データも階層化可能である点も損なわれない。
【図面の簡単な説明】
【図１】本発明の分解システムの構成を示すブロック図である。
【図２】本発明の分解システムの動作を示す流れ図である。
【図３】本発明による階層化データの概念的な構造を示す図である。
【図４】本発明による階層化データのデータ構造の一例を示す図である。
【図５】本発明の逆分解システムの構成を示すブロック図である。
【図６】本発明の逆分解システムの動作を示す流れ図である。
【図７】本発明の再構成システムの構成を示すブロック図である。
【図８】本発明の再構成システムの動作を示す流れ図である。
【図９】本発明による階層化データを用いた再構成を説明するための図である。
【図１０】非構造数値データの一例を示す図である。
【図１１】非構造数値データに対する単純化操作と詳細化操作を説明するための図である。
【図１２】従来の方法による階層化データの概念的な構造を示す図である。
【図１３】従来の方法による階層化データを用いた再構成を説明するための図である。
【符号の説明】
１０    分解装置
１００  数値データ入力部
１０１  単純化操作生成部
１０２  セル管理部
１０３  ノード管理部
１０４  詳細化データ生成部
１０５  単純化操作実行部
１１    逆分解装置
１１０  数値データ出力部
１１２  セル管理部
１１３  ノード管理部
１１４  依存関係解決部
１１５  詳細化操作実行部
１２    再構成装置
１２０  数値データ複製部
１２２  セル管理部
１２３  ノード管理部
１２４  依存関係解決部
１２５  詳細化操作実行部
１６    数値データ格納装置
１７    階層化データ格納装置
１８    再構成数値データ格納装置
２０    元の数値データ
２１    単純化数値データ
２２    セル
２３    下層リンク
２４    （詳細化操作を表す）ノード
２４０  依存関係を満たすためだけに再構成に関与するノード
２５    依存リンク
２５０  記録が不要な依存リンク
２６    再構成範囲
２６０  低解像度での再構成に関与する部分
２６１  高解像度での再構成に関与する部分
３０    元の数値データ
３１    単純化数値データ
３１０  節点データ
３１１  要素データ
３２    セルデータ（ノードデータを含む）
３２０  下層リンクデータ
３２１  下層変動データ
３３    ノードデータ
３３０  詳細化データ
３３１  依存リンクデータ
３４    再構成数値データ
４０    非構造数値データ
４００  非構造数値データ中の単純化される部分
４０１  非構造数値データ中の詳細化される部分
４１    節点
４１０  除去節点
４１１  縮重節点
４１２  挿入節点
４１３  分裂節点
４２    要素
Ａ００〜Ａ０Ａ  ステップ
Ａ１０〜Ａ１７  ステップ
Ａ２０〜Ａ２６  ステップ
【図１】
2004171139.tif 000003
【図２】
2004171139.tif 000004
【図３】
2004171139.tif 000005
【図４】
2004171139.tif 000006
【図５】
2004171139.tif 000007
【図６】
2004171139.tif 000008
【図７】
2004171139.tif 000009
【図８】
2004171139.tif 000010
【図９】
2004171139.tif 000011
【図１０】
2004171139.tif 000012
【図１１】
2004171139.tif 000013
【図１２】
2004171139.tif 000014
【図１３】
2004171139.tif 000015