大規模ボリュームデータの距離場生成方法とプログラム
【課題】ＲＡＭの容量を超える大規模ボリュームデータから距離場を不連続性が発生することなく全体として正しく生成することができる距離場生成方法とプログラムを提供する。
【解決手段】ＲＡＭとハードディスクを有するコンピュータを用いる。ＲＡＭの容量を超える二値化した大規模ボリュームデータをハードディスクに入力する入力ステップＳ１と、ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップＳ２と、クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップＳ３と、局所距離変換後に境界クラスタの距離値を隣接クラスタに伝播させるクラスタ間伝播ステップＳ４と、クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップＳ５と、統合されたボリュームデータ全体の距離場を出力する出力ステップＳ６とを備える。
【解決手段】ＲＡＭとハードディスクを有するコンピュータを用いる。ＲＡＭの容量を超える二値化した大規模ボリュームデータをハードディスクに入力する入力ステップＳ１と、ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップＳ２と、クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップＳ３と、局所距離変換後に境界クラスタの距離値を隣接クラスタに伝播させるクラスタ間伝播ステップＳ４と、クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップＳ５と、統合されたボリュームデータ全体の距離場を出力する出力ステップＳ６とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＲＡＭの容量を超える大規模ボリュームデータから距離場を生成する方法とプログラムに関する。
【０００２】
本発明において「距離場」とは、距離関数によって定義されたスカラ場の一種である。距離関数とは、ある位置における境界面又は境界線までの最短距離を意味する。また、「距離変換」とは、二値化されたボリュームデータから距離場を生成することをいう。距離場の定義及びその計算法に関しては、非特許文献１に詳細に記載されている。
【０００３】
本発明は、近年のデジタルエンジニアリング分野の発展に動機付けられている。最近のＸ線ＣＴ装置は５０００３ 程度の高解像度で部品の測定ができる。
自動車メーカなどの工業分野では、測定したＣＴ画像から得られたメッシュデータに対する需要が高い。得られたメッシュデータは、ＣＡＤモデルとの比較などの品質保証の用途に用いられる。ＣＴ画像からメッシュに変換する際の一般的な手法に、二値化したＣＴ画像から距離場を計算した後、中立面を抽出する方法がある。中立面は距離場の局所的最小によって定義される。
【０００４】
距離場は、中立面の抽出，干渉判定，ソリッドモデリング，アニメーションなど多くの分野に応用できる。
距離場の計算は、コンピュータグラフィックスおよび画像処理分野において広く研究されている。最も単純な方法は、セルＶに対して全ての境界セルとの距離値を求めて、その最小値を距離値とする方法である。得られた距離値は、高精度かつ大規模化も可能であるという利点がある一方で、計算時間が膨大となる。
ｎはセルの数、ｍは境界セルの数とすると、計算コストは、オーダがＯ（ｍｎ）となり現実的ではない。そのため、計算コストを抑えるような種々の方法が提案されている。
【０００５】
距離場の計算は、陰関数曲面、パラメトリック曲面、ポリゴンなど様々な入力を対象とした方法が存在する。しかし、これらの方法は、ボクセル化によりボリュームデータに変換できることから、本発明では、二値化したボリュームデータを入力とした方法を対象とする。
【０００６】
Ｃｈａｍｆｅｒ距離変換（Ｃｈａｍｆｅｒ Ｄｉｓｔａｎｃｅ Ｔｒａｎｓｆｏｒｍ：以下、ＣＤＴ）は、距離テンプレート（ｄｉｓｔａｎｃｅ ｔｅｍｐｌａｔｅ）を用いて距離場を計算する。距離テンプレートとは隣接するセル間の距離差を定義したものである。二値化画像が入力として与えられると、ＣＤＴは、距離場を２つの方法で計算する。一つはｓｗｅｅｐｉｎｇ法である。これは、ボリュームの先端から末端まで走査しつつ距離値を伝播させた後、同様のことを末端から行うことで距離場を計算する手段であり、オーダがＯ（ｎ）の計算コストを必要とする。
もう一つの方法はｗａｖｅｆｒｏｎｔ法で、距離値の伝播を境界から物体の内部に向けておこなう手法である。この方法はＤｉｊｋｓｔｒａの最短経路を求めるアルゴリズムに類似している。この手法の利点は、境界近辺の距離場のみを求めたい場合に有効である。この手法は、最小距離を持つセルの探索に優先順位付きキューを用いるため、計算コストはＯ（ｎｌｏｇｎ）である。以上２つの手法に共通する問題点として精度が低いという点がある。
【０００７】
Ｖｅｃｔｏｒ距離変換（ＶＤＴ）はＣＤＴにおける精度の問題を改善した手法である。ＶＤＴは距離値の代わりに自分のセルから最近セルへの位置ベクトルとの差分を保持している。距離値は、最後に差分ベクトル推定し、最後に距離値を評価する。そのため、ＶＤＴは正確な距離値が計算できる。またＶＤＴもｓｗｅｅｐｉｎｇとｗａｖｅｆｒｏｎｔによる計算方法が存在する。ＶＤＴにおけるｓｗｅｅｐｉｎｇスキームは、距離場を決定のために、８回の走査を必要とする。
【０００８】
ポリゴンを入力した手法をボリュームモデルに適用することは可能である。例えば、ＧＰＵを用いた高速な距離場計算手法が提案されている。この手法は、ＧＰＵを用いた２次元ボロノイ図の計算アルゴリズムを基にしており、各スライスに距離場を計算している。その手法の貢献は、ボロノイ図構築時における前スライスとの相関性を利用することで、評価対象となるポリゴンの数を劇的に減らした点にある。この手法は、境界セルを母点とみなすことでボリュームデータに対しても適用可能である。しかし、ボリュームデータ自体が膨大なセル数を保持しているため、枝狩りができたとしても、それがボトルネックとなる。また、サイズはＧＰＵのＲＡＭに制限される。そもそも、この手法は衝突判定など、対話性のあるアプリケーションを対象としているため、本発明で対象としているような形状モデリングを目的とした大規模ボリュームデータの距離場計算には向いていない。
【０００９】
一方、特徴を保持した距離場は、サイズが大きくなりがちになるため、効率的な表現手法も広く研究されている。
例えば、八分木に基づくサンプリングによる距離場表現手法ａｄａｐｔｉｖｅｌｙ ｓａｍｐｌｅｄ ｄｉｓｔａｎｃｅ ｆｉｅｌｄｓ（ＡＤＦ）が提案されている。各点における距離関数はサンプリングポイントを補間することによって決定することができ、鋭角特徴やフラクタルといった高解像度な詳細を表現できる。しかし、最適な八分木構造を決定することが難しいことから、ＡＤＦを距離変換のデータとして用いることは難しい。
【００１０】
また、ｃｏｍｐｌｅｔｅ ｄｉｓｔａｎｃｅ ｆｉｅｌｄ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ（ＣＤＦＲ）も提案されている。この手法は、空間を３次元グリッドに分割し、各セルに、そのセル内の距離場に影響する三角形群を格納している。一度ＣＤＦＲが形成されれば、セル内の距離場は、三角形間からの距離を用いて、正確かつ高解像度な距離場を計算できる。しかし、ボリュームデータに適用した場合、各セルに格納する境界セルは膨大であるため、距離場を計算することが容易にできるという利点がある。しかし、ボリュームデータに対する距離変換には適切ではない。境界表面としてセル集合を用いることになるが、それらのセルを保存するためにたくさんの空間が必要となるためである。
【００１１】
【非特許文献１】Ｍ．Ｗ．Ｊｏｎｅｓ，Ｊ．Ａ．Ｂｅｒｅｎｔｚｅｎ，ａｎｄ Ｍ．Ｓｒａｍｅｋ，“３Ｄ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄｓ：Ａ Ｓｕｒｖｅｙ ｏｆ Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，Ｖｏｌ．１２，Ｎｏ．４，Ｊｕｌｙ／Ａｕｇｕｓｔ ２００６
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上述したように、ボリュームデータから距離場を求める手法は、従来から数多く存在しており、距離変換（Ｄｉｓｔａｎｃｅ Ｔｒａｎｓｆｏｒｍ，ＤＴ）と呼ばれている。しかし，上述した従来の距離変換に共通する特徴として全てのセルがＲＡＭに格納される。そのため大規模ボリュームデータにこれらの手法を適用することは、現行の３２ｂｉｔＰＣではＲＡＭの制限により不可能である。距離場は格子空間上に離散的に表現され、各セルに距離値が割り当てられる。距離値が４ｂｙｔｅの浮動小数点で表現されていた場合、ＲＡＭの最大値は２ＧＢであることから、５億セル（約８００３）程度のボリュームデータしか扱うことができない。そのため、従来の方法では大規模ボリュームデータから距離場を計算することができない。
【００１３】
６４ｂｉｔＰＣを用いることにより、この問題を解消することは可能であるものの、ボリュームデータのサイズは、解像度の三乗に比例することから、すぐに限界を迎える。
一方、現在ボリュームデータのサイズは、高精度になる一方になっている。例えば、工業用ＣＴは、１スライス当たり、５０００×５０００×５０００のＣＴ画像を取り出すことが可能となっている。そのため従来の距離変換では、ＲＡＭの容量を超える大規模ボリュームデータから距離場を生成することができなかった。
【００１４】
本発明は、上述した問題点を解決するために創案されたものである。すなわち、本発明の目的は、ＲＡＭの容量を超える大規模ボリュームデータから距離場を不連続性が発生することなく全体として正しく生成することができる距離場生成方法とプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
本発明によれば、ＲＡＭとハードディスクを有するコンピュータを用いて、
入力装置によりＲＡＭの容量を超える二値化した大規模ボリュームデータをハードディスクに入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを備えたことを特徴とする大規模ボリュームデータの距離場生成方法が提供される。
【００１６】
本発明の好ましい実施形態によれば、前記クラスタ分割ステップにおいて、ボリュームデータを、互いに隣接した複数のセルからなるブロック形状の複数のクラスタと、クラスタ間に位置する複数の連続したセルからなるクラスタインタフェースに分割し、
各クラスタは、ボリュームデータの一部分のセルと、隣接する６つのクラスタインタフェースへのポインタを有し、
各クラスタインタフェースは、隣接する２つのクラスタと重複するセルと、当該２つのクラスタへのポインタを有する。
【００１７】
また、前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタに対し、前記局所距離変換ステップとクラスタ間伝播ステップを、前記汚染セルがなくなるまで繰り返す。
【００１８】
また、前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行う。
【００１９】
また本発明によれば、コンピュータのハードディスクにＲＡＭの容量を超える二値化した大規模ボリュームデータを入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを実行するための大規模ボリュームデータの距離場生成プログラムが提供される。
【発明の効果】
【００２０】
上記本発明の方法とプログラムによれば、ＲＡＭの容量を超える二値化した大規模ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶し、クラスタ毎に距離変換を行うので、距離変換を行わないクラスタは、ハードディスクに格納できるため、使用するメモリ量は、非常にコンパクトにできる。
【００２１】
また、このとき、クラスタ間で距離場の不連続性が発生するが、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させ、局所距離変換ステップとクラスタ間伝播ステップを、クラスタ間伝播によって距離値が更新されるセル（汚染セル）がなくなるまで繰り返すことで、全体として正しい距離場が生成できる。
【００２２】
また、前記クラスタ間伝播ステップにおいて、距離値が更新されたセルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行うことで、高速に収束させることができる。
【００２３】
従って本発明により、ＲＡＭの容量を超える大規模ボリュームデータから距離場を不連続性が発生することなく全体として正しく生成することが可能となる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の好ましい実施形態を図面を参照して説明する。
【００２５】
図１は、本発明の方法を実行するための装置構成図である。この図に示すように、この装置は、入力装置２、外部記憶装置３、内部記憶装置４、中央処理装置５および出力装置６を備える。
【００２６】
入力装置２は、例えばＣＴ装置、非接触／接触測定器、キーボード等であり、対象物に関するボリュームデータを外部記憶装置３（ハードディスク）に入力する。このボリュームデータは、内部記憶装置４（ＲＡＭ）の容量を超える二値化した大規模ボリュームデータである。
【００２７】
外部記憶装置３は、この例ではハードディスクであり、後述する二値化した大規模ボリュームデータ、複数のクラスタ、クラスタ毎の距離場、ボリュームデータ全体の距離場、およびこれに関連する距離場生成プログラムを記憶する。
【００２８】
内部記憶装置４は、この例ではＲＡＭであり、演算情報を保管する。中央処理装置５（ＣＰＵ）は、演算や入出力等を集中的に処理し、内部記憶装置４と共に、プログラムを実行する。出力装置６は、例えば表示装置とプリンタであり、統合されたボリュームデータ全体の距離場を出力するようになっている。
【００２９】
中央処理装置５、内部記憶装置４及び外部記憶装置３は、共同して、後述する距離場生成プログラムを実行する。
【００３０】
本発明の距離場生成方法は、上述した内部記憶装置４（ＲＡＭ）と外部記憶装置３（ハードディスク）を有するコンピュータを用いる。図２は、本発明の方法を示す全体フロー図である。この図に示すように、本発明の距離場生成方法は、入力ステップＳ１、クラスタ分割ステップＳ２、局所距離変換ステップＳ３、クラスタ間伝播ステップＳ４、距離場統合ステップＳ５及び出力ステップＳ６を有する。
【００３１】
入力ステップＳ１では、入力装置２によりＲＡＭ４の容量を超える二値化した大規模ボリュームデータをハードディスク３に入力する。
クラスタ分割ステップＳ２では、ボリュームデータをＲＡＭ４の容量より十分小さい複数のクラスタＣｉに分割してハードディスクに記憶する。
局所距離変換ステップＳ３では、クラスタ毎に距離変換してクラスタ毎の距離場生成を行う。
クラスタ間伝播ステップＳ４では、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させる。
距離場統合ステップＳ５では、クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う。
出力ステップＳ６では、出力装置６に統合されたボリュームデータ全体の距離場を出力する。
【００３２】
図２において本発明の距離場生成方法は、クラスタ間伝播ステップＳ４と距離場統合ステップＳ５の間に、汚染セルの有無を判断する判別ステップＳ７を有する。
判別ステップＳ７において、クラスタ間伝播ステップＳ４において距離値が更新された汚染セルがある場合には、局所距離変換ステップＳ３とクラスタ間伝播ステップＳ４を汚染セルがなくなるまで繰り返す。
【００３３】
本発明は、大規模ボリュームモデルから距離場を計算する方法とそのプログラムを提案する。従来の方法では、距離場を計算するためにＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）に全てのボリュームデータを割り当てる必要がある。そのため適用できるサイズの限界は、ＲＡＭに厳しく制限されていた。
本発明は、この問題をアウトオブコア法（Ｏｕｔ−ｏｆ−Ｃｏｒｅ ｍｅｔｈｏｄ）を用いて解決する。ここで、アウトオブコア法とは、ハードディスク等の記憶装置を用いて、ＲＡＭの容量を超えるデータを処理する方法を意味する。
【００３４】
本発明で提案する手段は、クラスタ分割ステップＳ２においてボリュームモデルをクラスタと呼ばれる小領域に分割することから始まる。距離場は、クラスタに対する局所距離変換（局所距離変換ステップＳ３）およびクラスタ間伝播（クラスタ間伝播ステップＳ４）により計算する。
局所距離変換は、他のクラスタに依存しないので、対象以外のクラスタは、ハードディスク等の記憶装置に保存できる。
クラスタ間伝播は、クラスタ間の距離場の一貫性を確保するために、クラスタの境界の距離値を隣接クラスタに伝播させる処理である。更に、伝播された距離値を用いた局所距離変換の順序を決定する手段を提案する。これにより、局所距離変換の回数をできるだけ少なくすることができる。本発明により、後述するように１０億セル以上のボリュームモデルから距離場を生成することができる。
【００３５】
本発明では、三次元グリッド上に定義された二値化されたセル（ｃｅｌｌ、ボクセル、点）で定義されたボリュームデータを扱う。オブジェクトは、物体内部を表す前景セル（又は内部セル）と外部を表す背景セル（又は外部セル）で表現されている。距離場は、式（１）の距離関数ｄ（ｐ）で定義されるスカラ場である。
【００３６】
【数１】
【００３７】
ｐ∈Ｒ３はセルを表し，ｑは物体の境界上の内部セル（「境界セル」と呼ぶ）を表す。本発明では、内部セルの境界セルからの距離値を計算することを想定している。内部セルと外部セルの関係を逆転することにより、外部セルの境界セルからの距離値を計算することも可能である。本発明では、大規模ボリュームデータからの距離場計算手法に焦点を当てる。
【００３８】
本発明は、Ｏｕｔ−ｏｆ−Ｃｏｒｅ距離変換（ｄｉｓｔａｎｃｅ ｔｒａｎｓｆｏｒｍ：以下、「ＯｏＣＤＴ」又は「アウトオブコア距離変換」という）を提案する。
本発明によるアウトオブコア距離変換は、大規模データに対する距離変換を小さいＲＡＭで可能にする方法である。アウトオブコア距離変換は、ボリューム空間をａ×ｂ×ｃ個のクラスタに分割することから始まる。
【００３９】
次に、各クラスタに対して距離変換を適用する。これを局所距離変換（ｌｏｃａｌ ｄｉｓｔａｎｃｅ ｔｒａｎｓｆｏｒｍ：ＬＤＴ）と呼ぶ。局所距離変換は、他のクラスタに依存しないため、必要となるメモリのサイズは、一つのクラスタに相当する量で十分である。その他のクラスタについてはハードディスク上に保存できる。
局所距離変換は、各々独立して行われるため、隣接クラスタ間の境界で距離値の一貫性が損なわれる。そこで本発明では、クラスタ間伝播（ｉｎｔｅｒｃｌｕｓｔｅｒ ｐｒｏｐａｇａｔｉｏｎ：ＩＣＰ）によりこの問題を解消する。
【００４０】
クラスタ間伝播は、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させる。クラスタ間伝播によって距離値が更新されたセルを、本発明では「ＤＩＲＴＹセル」（汚染セル）と呼ぶ。汚染セルが現れたクラスタは、再び局所距離変換を適用する必要がある。本発明の手段では、局所距離変換とクラスタ間伝播を汚染セルがなくなるまで続ける。
【００４１】
アウトオブコア距離変換（ＯｏＣＤＴ）の計算時間は局所距離変換の回数に依存するため、局所距離変換の回数をできるだけ少なくするような局所距離変換の順番を決定する必要がある。そこで本発明では、各クラスタの汚染セルの最小値に基づく順序付けを提案する。これにより、少ない回数での収束が実現する。
【００４２】
図３（ａ）は機械部品のＣＴ画像のボリュームレンダリング画像であり、図３（ｂ）（ｃ）はその本発明による距離場計算結果である。
本発明の特徴の１つは、アウトオブコア距離変換法に基づく枠組みを距離変換に適用した点にある。これにより、図３（ｂ）（ｃ）に示したような、大規模ボリュームデータの距離場を計算可能にした。
【００４３】
本発明の利点として以下の点が挙げられる。
（１）大容量メモリを必要としない。本発明の手段で必要とするメモリは、クラスタ１個分であるため、一般的な３２ｂｉｔＰＣでも計算可能である。
（２）適用できるボリュームデータの制限が劇的に緩和された。従来手法は、ＲＡＭやＧＰＵのメモリに依存していたが、本発明の方法は、ハードディスク等のストレージの容量に依存する。
（３）局所距離変換は他のクラスタに依存しないため、マルチコアプロセッサを使用することで高速化が可能である。
（４）精度、データサイズ、速度は、局所距離変換で使用する距離変換法に依存しており、目的に応じて使い分けることが可能である。
（５）本発明の手段は、ｎ−Ｄ画像（ｎは１以上の整数）に適用可能である。
【００４４】
以下、本発明を詳細に説明する。
１ データ構造
はじめに、本発明で用いるデータ構造について図４，５を用いて説明する。Ｖは入力ボリュームモデルであり、Ｖは、ａ×ｂ×ｃ個（この例では５×５）のブロック形状のクラスタＣｉ（ｉ＝０，１，２，…）とクラスタ間に位置するクラスタインタフェース＜ｉ，ｊ＞に分解される。
クラスタＣｉは、ボリュームモデルＶの一部分のセルと、隣接する６つのクラスタインタフェースへのポインタを持つ。クラスタインタフェースは、＜ｉ，ｊ＞と表す。これは、クラスタＣｉとＣｊの重複領域に存在していることを表す。クラスタインタフェース＜ｉ，ｊ＞は、重複領域のセルとクラスタＣｉ、Ｃｊへのポインタを持つ。
各セルｖｉは、距離値ｖｉを持つ。本発明では、クラスタＣｊとクラスタインタフェース＜ｉ，ｊ＞に属するセルをそれぞれｖｉｊ，ｖｉ＜ｊ，ｋ＞と表す。セルｖｉ＜ｊ，ｋ＞は、対となるセルをＣｊ，Ｃｋにそれぞれ持つ。図４（Ａ）における○印で示すセルは、そのようなセルを表す。ｖｉｊ，ｖｉ＜ｊ，ｋ＞は、同じセルを共有しており、ｖｉｊ，ｖｉ＜ｊ，ｋ＞は常に、ｖｉ＜ｊ，ｋ＞＝ｍｉｎ（ｖｉｊ，ｖｉＫ）を満たす。
【００４５】
２ 本発明の概要
図４，５を用いて本発明の概要を説明する。図４（Ａ）は入力ボリュームモデルＶである。この図において、太い実線はオブジェクトの境界、その内側はオブジェクトの内部、斜線で示す外側は外部を示す。
本発明では、はじめに、ボリュームモデルＶをクラスタＣｉ（ｉ＝０，１，２，３）とクラスタインタフェース＜ｉ，ｊ＞に分解する。（図４（Ｂ））。三次元の場合、Ｖはａ×ｂ×ｃのクラスタとクラスタインタフェースに分解される。ａ，ｂ，ｃは、ユーザによって与えられるものとする。クラスタに分割した後、各セルｖｋ’に数２の式（２）の距離値を与えて初期化を行う（図４（Ｃ））。
【００４６】
【数２】
【００４７】
初期化が済んだクラスタとクラスタインタフェースは、一時ファイルとしてハードディスクに保存する。次に、一つのクラスタを選択し、ＲＡＭに格納する。そして、局所距離変換を適用して距離値を計算する。図４（Ｄ）では、Ｃ０が選択されている。
【００４８】
この局所距離変換によりクラスタＣ０内の全てのセルは、局所的に最適化される。つまり、クラスタと隣接するクラスタインタフェースが与えられている条件下において最適化されている状態を指す。
しかし、全体で見た場合、距離値が正しいという保証はない。例えば、図４（Ｄ）は、Ｃ０に対して局所距離変換を１回適用した結果であり、図５（Ｊ）は２回適用した結果である。Ｃ０のセルの幾つかが更新されていることがわかる。これは、クラスタ外のセルが最近セルだった場合にそれを見つけることができないためである。
本発明では、これをクラスタ間伝播（ｉｎｔｅｒ−ｃｌｕｓｔｅｒ ｐｒｏｐａｇａｔｉｏｎ：以下、ＩＣＰ）によって解決する。
【００４９】
図４（Ｅ）に示すとおり、局所距離変換を適用後のクラスタの境界セルの距離値は、対応するクラスタインタフェースのセルと異なっている。そこで、そのようなセルの距離値が一致するように書き換える。すなわちこれらの距離値を、隣接するクラスタの境界セルにコピーする。この処理をクラスタ間伝播と呼ぶ。
図４（Ｅ）ではＣ０からＣ１とＣ２へのクラスタ間伝播が適用されている。局所距離変換とクラスタ間伝播の処理（図４（ｄ）から図４（ｅ）までの処理）を１ステップとして数える。
クラスタ間伝播によって距離値が変更されたセルを、本発明では「ＤＩＲＴＹセル」（汚染セル）と呼ぶ。図４（Ｆ）〜図５（Ｊ）では、局所距離変換とクラスタ間伝播を汚染セルがなくなるまで繰り返す。この繰り返し処理は、付録にて証明を行っている。
処理が終了した時点で、全てのセルには正しい距離値が格納されており、大域的に最適化された状態であるといえる。最後に、クラスタを合成して距離場を作成する（図５（ｋ））。
【００５０】
以下、上述した局所距離変換、クラスタ間伝播等の詳細について述べる。
３ 局所距離変換
図６は、Ｗａｖｅｆｒｏｎｔ Ｃｈａｍｆｅｒ距離変換を用いた局所距離変換のアルゴリズムを示す。ｎｂｒ（ｖｍ）は、ｖｍの１−ｒｉｎｇ近傍（２６個）を表す。ｄｉｓｔ（ｖｉ，ｖｊ）は、ｖｉｖｊ間の距離である。ｓｗｅｅｐｉｎｇ ｃｈａｍｆｅｒ距離変換やｖｅｃｔｏｒ距離変換といった他の距離変換手法も局所距離変換として使うことができる。
【００５１】
４ クラスタ間伝播
クラスタ間伝播（Ｉｎｔｅｒ−Ｃｌｕｓｔｅｒ Ｐｒｏｐａｇａｔｉｏｎ：ＩＣＰ）は、局所距離変換を適用したクラスタＣｉからＣｉに隣接するクラスタＣｊへの距離値の伝播である。クラスタ間伝播は、クラスタＣｉとＣｊによって共有されているセルの距離値を比較する。図７にクラスタ間伝播のアルゴリズムを示す。
【００５２】
クラスタＣｉに局所距離変換を適用した後、クラスタ間伝播では、対応する境界セルｖｋｉｖｋｊの距離値を比較する。もしｖｋｉ＜ｖｋｊだった場合は、ｖｋｊはｖｋｉに置き換えられる。このようなセルは汚染セルとみなし、汚染セルが含まれるクラスタは、局所距離変換を再度適用する対象となる。これは、汚染セルが隣接セルの距離値よりも小さいため、局所距離変換によって値が更新されやすいためである。
【００５３】
本発明の実施例では、ファイルの入出力を減らすために、クラスタとクラスタが重複するようにクラスタを分割している。隣接クラスタが重複していない場合は、２６個の隣接クラスタに対して伝播処理を行う必要がある。それに対して、本発明の実施例では、６個であり、２３％程度のファイル入出力の削減を実現している。
【００５４】
更に、本発明では、クラスタ間伝播のためにクラスタインタフェースと呼ばれるデータ構造を導入している。クラスタインタフェースは、一見冗長に見えるが、アルゴリズムの高速化に寄与している。図８に簡単な例を示す。クラスタインタフェースなしのクラスタ間伝播では、６個の隣接クラスタを読み込む必要があるのに対して、クラスタインタフェースを導入した場合は、６個のクラスタインタフェースを読み込むだけでよく、明らかに読み込むデータ量を減らせている。
【００５５】
クラスタインタフェースは、局所距離変換処理の最適化にも利用できる。本発明では、クラスタ間伝播を分割することで局所距離変換を次の通り改良した。
（１） ハードディスクからクラスタＣｉを読み込む
（２） クラスタインタフェース＜ｉ，ｊ＞からＣｉへ伝播させる
（３） 局所距離変換を実行する
（４） クラスタＣｉからクラスタインタフェース＜ｉ，ｊ＞へ伝播される
（５） クラスタＣｉを保存する。
【００５６】
以上の処理によりファイル入出力が劇的に削減される。もし、クラスタ間伝播を一度に適用すると、７個のクラスタを局所距離変換を実行するごとに読み込む必要があった。それに対して、改良アルゴリズムでは、１個のクラスタだけで十分であり、クラスタインタフェースの利点を最大限活用している。
【００５７】
５ 最小汚染距離値（ＭＤＤ）を用いた局所距離変換適用順序の決定
局所距離変換とクラスタ間伝播によって大規模距離場は計算できるものの、計算速度に関する問題が残っている。図９に１次元における簡単な例を示す。どちらのクラスタから局所距離変換を適用するかによって局所距離変換の回数が異なっていることがわかる。もし、この差が大きいと、パフォーマンスの違いは顕著になる。よって、局所距離変換の回数が少なくなるような順序付けが必要となる。
【００５８】
最適な順序付けは、ボリュームデータやクラスタリング方法に依存することから、ほぼ不可能である。そこで、局所距離変換の回数が最小になるようなヒューリスティクスを導入する。本出願の発明者の観察により、より小さな距離値を持つ汚染セルを持つクラスタに対して優先的に局所距離変換を適用すればよいことがわかった。これは、そのようなクラスタが、隣接クラスタへ伝播しやすいためである。
【００５９】
ここで、局所距離変換適用順序付けの優先度を評価する基準として最小汚染距離値（ＭＤＤ）を導入する。最小汚染距離値は、「各クラスタの最小の距離値を持つ汚染セル」によって定義され、クラスタ間伝播によってセルが更新されたときに更新される。局所距離変換を適用した後のクラスタは、最小の優先順位を持つべきと考えられるので、局所距離変換を適用した後の最小汚染距離値は、無限大とする。
【００６０】
最小汚染距離値を用いた順位付けは簡単である。各ステップにおいて、各クラスタの最小汚染距離値の集合Ｍの中で最小である最小汚染距離値を持つクラスタを選択する。この最小汚染距離値（ＭＤＤ）を極小汚染距離値（ｍＭＤＤ）と呼ぶ。この繰り返し処理は、極小汚染距離値が無限大になったときに終了する。最終的な距離場は、クラスタを合成することによって得られる。
【００６１】
アウトオブコア距離変換をまとめると、図１０に示すとおりである。
【００６２】
６ 実施例および評価
本発明の実施例を図３、図１３に示す。“Ｅｎｇｉｎｅ−Ｈｅａｄ”“ＵＴ−ｆｉｇｕｒｉｎｅ”データは、ＣＴ画像を二値化して得られたものである。他のデータは、ポリゴンモデルをボクセル化して得られたものである。これらの例題の多くは、メモリの問題により従来は計算不可能であった。また各図は、表面をレンダリングしたものと距離場をボリュームレンダリングしたものを示している。ＵＴ−ｆｉｇｕｒｉｎｅデータが透明に見えるのは、モデルに空洞があるためである。
【００６３】
上述した全ての例題は、以下の環境のＷｉｎｄｏｗｓ(登録商標）ＸＰ ＰＣで計算した。
・Ｉｎｔｅｌ Ｃｏｒｅ２ Ｄｕｏ Ｅ６４００（２．１３ＧＨｚ，２−ｃｏｒｅ）
・２ＧＢ ＲＡＭ
・ＳＡＴＡ ３２０ＧＢ ＨＤＤ×２ （ＲＡＩＤ０構成）
【００６４】
さらに、本発明のプログラムは、マルチスレッドをサポートし中間ファイルは圧縮ライブラリｚｌｉｂを使って圧縮している。実験データを表１に示す。＃ＬＤＴは局所距離変換（ＬＤＴ）の回数である。Ｒは、式３で示すパフォーマンスの指標である。計算時間については、３ステップから構成される。「Ｉｎｉｔ．」は、ボリュームデータの分割に要した時間である。「ＯｏＣＤＴ」は、局所距離変換とクラスタ間伝播に要した時間である。「Ｃｏｍｐｏ．」はクラスタの合成に要した時間である。「Ｓｔｏｒａｇｅ」は中間データの最大サイズを、％は、圧縮比をあらわす。
【００６５】
（評価）
Ｗａｖｅｆｒｏｎｔ法の計算効率は、ｎをセルの数とした場合、Ｏ（ｎｌｏｇｎ） であることは知られている。局所距離変換の計算効率は、ｍをクラスタの数とした場合、Ｏ（ｎ／ｍ（ｌｏｇｎ−ｌｏｇｍ））である。局所距離変換の順序付けアルゴリズムでは、極小汚染距離値（ｍＭＤＤ）の探索に優先順位付きキューを使用しているので、対数時間を必要とすることから、本アルゴリズムの計算効率は、ｋを局所距離変換の回数とすると、Ｏ（ｋ・ｎ／ｍｌｏｇｍ（ｌｏｇｎ−ｌｏｇｍ））である。ここで、パフォーマンスを評価するために、従来のアルゴリズムとの比を表す評価値Ｒを数３の式（３）によって定義する。
【００６６】
【数３】
【００６７】
もしＲ＝１ならば、計算効率は、ｉｎ−ｃｏｒｅ（コア内処理）と同じであることがいえる。もしＲ＜１ならば、ｉｎ−ｃｏｒｅよりも小さいといえる。もちろんハードディスクを利用している以上、本発明のほうが計算時間は遅い。しかしＲは、パフォーマンスを評価する良い指標となりうると考えられる。表１にＲの計算結果を示している。内部セルのないクラスタに対しては、局所距離変換が実行されないのでほとんどの結果で２以下の結果が出ている。このように、本発明は、よく最適化されているといえる。
【００６８】
【表１】
【００６９】
本発明のパフォーマンスとクラスタ分割数の関連性を観察することは興味深い。図１１にクラスタ分割数とパフォーマンスの関連性を示す。始めに、初期化と合成処理において、クラスタ数が多いと計算時間が少ないことが判る。これは、多くのファイルを開いたり閉じたりするためである。この点に関しては、ＲＡＩＤ０（ストライピング）の導入により幾分改善される。一方で、アルゴリズム自体は、ある程度細かいほうが早くなる。これは、局所距離変換の計算コストが減少するのと、全て外部のクラスタの個数が増えた結果、クラスタあたりの局所距離変換の回数が少なくなるためである。両者をあわせると一定のクラスタ数において最小値が存在することが確認きる。しかしこのクラスタ数について、明確な傾向は確認できない。ただし、クラスタ数が多すぎたり、少なすぎるとパフォーマンスが低下することがわかる。
【００７０】
局所距離変換は、他のクラスタからは独立しているため、マルチコアプロセッサを用いることにより高速化が実現する。表２に、使用したコアの数により計算時間を比較した結果を示す。４スレッドを使用した場合には、１スレッドを使用した場合よりも２倍高速なのが判る。ただし、初期化と合成処理においては、マルチスレッドの効果はないため、距離変換のみに注目すると、４スレッドでは、１スレッドより３倍以上も高速なことが判った。これにより距離変換アルゴリズムは、マルチスレッド環境において高い並列性を持っていることがわかる。
【００７１】
【表２】
【００７２】
最小汚染距離値は、ｗａｖｅｆｒｏｎｔベースの局所距離変換の最適化に利用することもできる。局所距離変換は、最小汚染距離値より小さな距離値を持つセルに関しては、大域的に最適化されているため、局所距離変換の計算からはずすことができるという興味深い特徴を持つ（証明は省略する）。
【００７３】
図１２に各ステップにおける最小汚染距離値（ＭＤＤ）と計算時間をプロットした図を示す。この図から、２２４ステップ辺りから幾つかの局所距離変換が高速になっており、その際の最小汚染距離値が１以上であることがわかる。これは、クラスタ内の幾つかのセルが大域的に最適化され、局所距離変換から除外されたためである。
【００７４】
本発明は、クラスタとクラスタインタフェースを保存するための一時ファイルをハードディスク上に作成する。距離場は、よく同じ距離値を持つことから、圧縮ライブラリを用いることで高圧縮が実現する。表１の例題においても圧縮前と比較して１％程度とよく圧縮されていることがかる。例えば、６０億セル持つ“ｔｗｉｒｌ”モデルは、非圧縮では２４ＧＢあるにもかかわらず、中間データは２７０ＭＢである。このことから本手法で適用できるサイズの限界は、使用できるハードディスクに依存するということができ、それは、１０，０００３セルを越えるということができる。
【００７５】
本発明で得られる距離場の精度は、どの距離変換手法を用いたかによって決定される。本発明は、ＩＮ−ＣＯＲＥアルゴリズムと同等の計算結果が得られることから、クラスタの分割方法などには影響をうけない。
【００７６】
上述したように、本発明では、Ｏｕｔ−ｏｆ−Ｃｏｒｅ化された距離変換方法とプログラムを提案した。本発明は、局所距離変換とクラスタ間伝播により、従来手法がもつメモリ上の問題を解決した。また、実験結果により、従来と比較して巨大なボリュームデータから距離場を計算できることを示した。また、図１０に示した順序付けアルゴリズムは、局所距離変換の回数をできるだけ少なくする。実際に実験を通して、妥当な速度で計算できることを示した。
【００７７】
上述したように本発明の方法とプログラムによれば、ＲＡＭの容量を超える二値化した大規模ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶し、クラスタ毎に距離変換を行うので、距離変換を行わないクラスタは、ハードディスクに格納できるため、使用するメモリ量は、非常にコンパクトにできる。
また、このとき、クラスタ間で距離場の不連続性が発生するが、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させ、局所距離変換ステップとクラスタ間伝播ステップを、クラスタ間伝播によって距離値が更新されるセルがなくなるまで繰り返すことで、全体として正しい距離場が生成できる。
また、前記クラスタ間伝播ステップにおいて、距離値が更新されたセルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行うことで、高速に収束させることができる。
従って本発明により、ＲＡＭの容量を超える大規模ボリュームデータから距離場を不連続性が発生することなく全体として正しく生成することが可能になった。
【００７８】
なお、本発明は上述した実施形態に限定されず、本発明の要旨を逸脱しない範囲で種々変更できることは勿論である。
【図面の簡単な説明】
【００７９】
【図１】本発明の方法を実行するための装置構成図である。
【図２】本発明の方法を示す全体フロー図である。
【図３】機械部品のＣＴ画像のボリュームレンダリング画像とその本発明による距離場計算結果である。
【図４】本発明で用いるデータ構造の第１説明図である。
【図５】本発明で用いるデータ構造の第２説明図である。
【図６】局所距離変換のアルゴリズムを示す図である。
【図７】クラスタ間伝播のアルゴリズムを示す図である。
【図８】クラスタインタフェースの例を示す図である。
【図９】局所距離変換適用の順序を示す例である。
【図１０】本発明のアウトオブコア距離変換のアルゴリズムを示す図である。
【図１１】クラスタ分割数とパフォーマンスの関連性を示す図である。
【図１２】各ステップにおける最小汚染距離値（ＭＤＤ）と計算時間をプロットした図である。
【図１３】本発明による距離場の計算結果を示す図である。
【符号の説明】
【００８０】
２ 入力装置、
３ 外部記憶装置、
４ 内部記憶装置、
５ 中央処理装置、
６ 出力装置
【技術分野】
【０００１】
本発明は、ＲＡＭの容量を超える大規模ボリュームデータから距離場を生成する方法とプログラムに関する。
【０００２】
本発明において「距離場」とは、距離関数によって定義されたスカラ場の一種である。距離関数とは、ある位置における境界面又は境界線までの最短距離を意味する。また、「距離変換」とは、二値化されたボリュームデータから距離場を生成することをいう。距離場の定義及びその計算法に関しては、非特許文献１に詳細に記載されている。
【０００３】
本発明は、近年のデジタルエンジニアリング分野の発展に動機付けられている。最近のＸ線ＣＴ装置は５０００３ 程度の高解像度で部品の測定ができる。
自動車メーカなどの工業分野では、測定したＣＴ画像から得られたメッシュデータに対する需要が高い。得られたメッシュデータは、ＣＡＤモデルとの比較などの品質保証の用途に用いられる。ＣＴ画像からメッシュに変換する際の一般的な手法に、二値化したＣＴ画像から距離場を計算した後、中立面を抽出する方法がある。中立面は距離場の局所的最小によって定義される。
【０００４】
距離場は、中立面の抽出，干渉判定，ソリッドモデリング，アニメーションなど多くの分野に応用できる。
距離場の計算は、コンピュータグラフィックスおよび画像処理分野において広く研究されている。最も単純な方法は、セルＶに対して全ての境界セルとの距離値を求めて、その最小値を距離値とする方法である。得られた距離値は、高精度かつ大規模化も可能であるという利点がある一方で、計算時間が膨大となる。
ｎはセルの数、ｍは境界セルの数とすると、計算コストは、オーダがＯ（ｍｎ）となり現実的ではない。そのため、計算コストを抑えるような種々の方法が提案されている。
【０００５】
距離場の計算は、陰関数曲面、パラメトリック曲面、ポリゴンなど様々な入力を対象とした方法が存在する。しかし、これらの方法は、ボクセル化によりボリュームデータに変換できることから、本発明では、二値化したボリュームデータを入力とした方法を対象とする。
【０００６】
Ｃｈａｍｆｅｒ距離変換（Ｃｈａｍｆｅｒ Ｄｉｓｔａｎｃｅ Ｔｒａｎｓｆｏｒｍ：以下、ＣＤＴ）は、距離テンプレート（ｄｉｓｔａｎｃｅ ｔｅｍｐｌａｔｅ）を用いて距離場を計算する。距離テンプレートとは隣接するセル間の距離差を定義したものである。二値化画像が入力として与えられると、ＣＤＴは、距離場を２つの方法で計算する。一つはｓｗｅｅｐｉｎｇ法である。これは、ボリュームの先端から末端まで走査しつつ距離値を伝播させた後、同様のことを末端から行うことで距離場を計算する手段であり、オーダがＯ（ｎ）の計算コストを必要とする。
もう一つの方法はｗａｖｅｆｒｏｎｔ法で、距離値の伝播を境界から物体の内部に向けておこなう手法である。この方法はＤｉｊｋｓｔｒａの最短経路を求めるアルゴリズムに類似している。この手法の利点は、境界近辺の距離場のみを求めたい場合に有効である。この手法は、最小距離を持つセルの探索に優先順位付きキューを用いるため、計算コストはＯ（ｎｌｏｇｎ）である。以上２つの手法に共通する問題点として精度が低いという点がある。
【０００７】
Ｖｅｃｔｏｒ距離変換（ＶＤＴ）はＣＤＴにおける精度の問題を改善した手法である。ＶＤＴは距離値の代わりに自分のセルから最近セルへの位置ベクトルとの差分を保持している。距離値は、最後に差分ベクトル推定し、最後に距離値を評価する。そのため、ＶＤＴは正確な距離値が計算できる。またＶＤＴもｓｗｅｅｐｉｎｇとｗａｖｅｆｒｏｎｔによる計算方法が存在する。ＶＤＴにおけるｓｗｅｅｐｉｎｇスキームは、距離場を決定のために、８回の走査を必要とする。
【０００８】
ポリゴンを入力した手法をボリュームモデルに適用することは可能である。例えば、ＧＰＵを用いた高速な距離場計算手法が提案されている。この手法は、ＧＰＵを用いた２次元ボロノイ図の計算アルゴリズムを基にしており、各スライスに距離場を計算している。その手法の貢献は、ボロノイ図構築時における前スライスとの相関性を利用することで、評価対象となるポリゴンの数を劇的に減らした点にある。この手法は、境界セルを母点とみなすことでボリュームデータに対しても適用可能である。しかし、ボリュームデータ自体が膨大なセル数を保持しているため、枝狩りができたとしても、それがボトルネックとなる。また、サイズはＧＰＵのＲＡＭに制限される。そもそも、この手法は衝突判定など、対話性のあるアプリケーションを対象としているため、本発明で対象としているような形状モデリングを目的とした大規模ボリュームデータの距離場計算には向いていない。
【０００９】
一方、特徴を保持した距離場は、サイズが大きくなりがちになるため、効率的な表現手法も広く研究されている。
例えば、八分木に基づくサンプリングによる距離場表現手法ａｄａｐｔｉｖｅｌｙ ｓａｍｐｌｅｄ ｄｉｓｔａｎｃｅ ｆｉｅｌｄｓ（ＡＤＦ）が提案されている。各点における距離関数はサンプリングポイントを補間することによって決定することができ、鋭角特徴やフラクタルといった高解像度な詳細を表現できる。しかし、最適な八分木構造を決定することが難しいことから、ＡＤＦを距離変換のデータとして用いることは難しい。
【００１０】
また、ｃｏｍｐｌｅｔｅ ｄｉｓｔａｎｃｅ ｆｉｅｌｄ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ（ＣＤＦＲ）も提案されている。この手法は、空間を３次元グリッドに分割し、各セルに、そのセル内の距離場に影響する三角形群を格納している。一度ＣＤＦＲが形成されれば、セル内の距離場は、三角形間からの距離を用いて、正確かつ高解像度な距離場を計算できる。しかし、ボリュームデータに適用した場合、各セルに格納する境界セルは膨大であるため、距離場を計算することが容易にできるという利点がある。しかし、ボリュームデータに対する距離変換には適切ではない。境界表面としてセル集合を用いることになるが、それらのセルを保存するためにたくさんの空間が必要となるためである。
【００１１】
【非特許文献１】Ｍ．Ｗ．Ｊｏｎｅｓ，Ｊ．Ａ．Ｂｅｒｅｎｔｚｅｎ，ａｎｄ Ｍ．Ｓｒａｍｅｋ，“３Ｄ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄｓ：Ａ Ｓｕｒｖｅｙ ｏｆ Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，Ｖｏｌ．１２，Ｎｏ．４，Ｊｕｌｙ／Ａｕｇｕｓｔ ２００６
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上述したように、ボリュームデータから距離場を求める手法は、従来から数多く存在しており、距離変換（Ｄｉｓｔａｎｃｅ Ｔｒａｎｓｆｏｒｍ，ＤＴ）と呼ばれている。しかし，上述した従来の距離変換に共通する特徴として全てのセルがＲＡＭに格納される。そのため大規模ボリュームデータにこれらの手法を適用することは、現行の３２ｂｉｔＰＣではＲＡＭの制限により不可能である。距離場は格子空間上に離散的に表現され、各セルに距離値が割り当てられる。距離値が４ｂｙｔｅの浮動小数点で表現されていた場合、ＲＡＭの最大値は２ＧＢであることから、５億セル（約８００３）程度のボリュームデータしか扱うことができない。そのため、従来の方法では大規模ボリュームデータから距離場を計算することができない。
【００１３】
６４ｂｉｔＰＣを用いることにより、この問題を解消することは可能であるものの、ボリュームデータのサイズは、解像度の三乗に比例することから、すぐに限界を迎える。
一方、現在ボリュームデータのサイズは、高精度になる一方になっている。例えば、工業用ＣＴは、１スライス当たり、５０００×５０００×５０００のＣＴ画像を取り出すことが可能となっている。そのため従来の距離変換では、ＲＡＭの容量を超える大規模ボリュームデータから距離場を生成することができなかった。
【００１４】
本発明は、上述した問題点を解決するために創案されたものである。すなわち、本発明の目的は、ＲＡＭの容量を超える大規模ボリュームデータから距離場を不連続性が発生することなく全体として正しく生成することができる距離場生成方法とプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
本発明によれば、ＲＡＭとハードディスクを有するコンピュータを用いて、
入力装置によりＲＡＭの容量を超える二値化した大規模ボリュームデータをハードディスクに入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを備えたことを特徴とする大規模ボリュームデータの距離場生成方法が提供される。
【００１６】
本発明の好ましい実施形態によれば、前記クラスタ分割ステップにおいて、ボリュームデータを、互いに隣接した複数のセルからなるブロック形状の複数のクラスタと、クラスタ間に位置する複数の連続したセルからなるクラスタインタフェースに分割し、
各クラスタは、ボリュームデータの一部分のセルと、隣接する６つのクラスタインタフェースへのポインタを有し、
各クラスタインタフェースは、隣接する２つのクラスタと重複するセルと、当該２つのクラスタへのポインタを有する。
【００１７】
また、前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタに対し、前記局所距離変換ステップとクラスタ間伝播ステップを、前記汚染セルがなくなるまで繰り返す。
【００１８】
また、前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行う。
【００１９】
また本発明によれば、コンピュータのハードディスクにＲＡＭの容量を超える二値化した大規模ボリュームデータを入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを実行するための大規模ボリュームデータの距離場生成プログラムが提供される。
【発明の効果】
【００２０】
上記本発明の方法とプログラムによれば、ＲＡＭの容量を超える二値化した大規模ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶し、クラスタ毎に距離変換を行うので、距離変換を行わないクラスタは、ハードディスクに格納できるため、使用するメモリ量は、非常にコンパクトにできる。
【００２１】
また、このとき、クラスタ間で距離場の不連続性が発生するが、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させ、局所距離変換ステップとクラスタ間伝播ステップを、クラスタ間伝播によって距離値が更新されるセル（汚染セル）がなくなるまで繰り返すことで、全体として正しい距離場が生成できる。
【００２２】
また、前記クラスタ間伝播ステップにおいて、距離値が更新されたセルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行うことで、高速に収束させることができる。
【００２３】
従って本発明により、ＲＡＭの容量を超える大規模ボリュームデータから距離場を不連続性が発生することなく全体として正しく生成することが可能となる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の好ましい実施形態を図面を参照して説明する。
【００２５】
図１は、本発明の方法を実行するための装置構成図である。この図に示すように、この装置は、入力装置２、外部記憶装置３、内部記憶装置４、中央処理装置５および出力装置６を備える。
【００２６】
入力装置２は、例えばＣＴ装置、非接触／接触測定器、キーボード等であり、対象物に関するボリュームデータを外部記憶装置３（ハードディスク）に入力する。このボリュームデータは、内部記憶装置４（ＲＡＭ）の容量を超える二値化した大規模ボリュームデータである。
【００２７】
外部記憶装置３は、この例ではハードディスクであり、後述する二値化した大規模ボリュームデータ、複数のクラスタ、クラスタ毎の距離場、ボリュームデータ全体の距離場、およびこれに関連する距離場生成プログラムを記憶する。
【００２８】
内部記憶装置４は、この例ではＲＡＭであり、演算情報を保管する。中央処理装置５（ＣＰＵ）は、演算や入出力等を集中的に処理し、内部記憶装置４と共に、プログラムを実行する。出力装置６は、例えば表示装置とプリンタであり、統合されたボリュームデータ全体の距離場を出力するようになっている。
【００２９】
中央処理装置５、内部記憶装置４及び外部記憶装置３は、共同して、後述する距離場生成プログラムを実行する。
【００３０】
本発明の距離場生成方法は、上述した内部記憶装置４（ＲＡＭ）と外部記憶装置３（ハードディスク）を有するコンピュータを用いる。図２は、本発明の方法を示す全体フロー図である。この図に示すように、本発明の距離場生成方法は、入力ステップＳ１、クラスタ分割ステップＳ２、局所距離変換ステップＳ３、クラスタ間伝播ステップＳ４、距離場統合ステップＳ５及び出力ステップＳ６を有する。
【００３１】
入力ステップＳ１では、入力装置２によりＲＡＭ４の容量を超える二値化した大規模ボリュームデータをハードディスク３に入力する。
クラスタ分割ステップＳ２では、ボリュームデータをＲＡＭ４の容量より十分小さい複数のクラスタＣｉに分割してハードディスクに記憶する。
局所距離変換ステップＳ３では、クラスタ毎に距離変換してクラスタ毎の距離場生成を行う。
クラスタ間伝播ステップＳ４では、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させる。
距離場統合ステップＳ５では、クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う。
出力ステップＳ６では、出力装置６に統合されたボリュームデータ全体の距離場を出力する。
【００３２】
図２において本発明の距離場生成方法は、クラスタ間伝播ステップＳ４と距離場統合ステップＳ５の間に、汚染セルの有無を判断する判別ステップＳ７を有する。
判別ステップＳ７において、クラスタ間伝播ステップＳ４において距離値が更新された汚染セルがある場合には、局所距離変換ステップＳ３とクラスタ間伝播ステップＳ４を汚染セルがなくなるまで繰り返す。
【００３３】
本発明は、大規模ボリュームモデルから距離場を計算する方法とそのプログラムを提案する。従来の方法では、距離場を計算するためにＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）に全てのボリュームデータを割り当てる必要がある。そのため適用できるサイズの限界は、ＲＡＭに厳しく制限されていた。
本発明は、この問題をアウトオブコア法（Ｏｕｔ−ｏｆ−Ｃｏｒｅ ｍｅｔｈｏｄ）を用いて解決する。ここで、アウトオブコア法とは、ハードディスク等の記憶装置を用いて、ＲＡＭの容量を超えるデータを処理する方法を意味する。
【００３４】
本発明で提案する手段は、クラスタ分割ステップＳ２においてボリュームモデルをクラスタと呼ばれる小領域に分割することから始まる。距離場は、クラスタに対する局所距離変換（局所距離変換ステップＳ３）およびクラスタ間伝播（クラスタ間伝播ステップＳ４）により計算する。
局所距離変換は、他のクラスタに依存しないので、対象以外のクラスタは、ハードディスク等の記憶装置に保存できる。
クラスタ間伝播は、クラスタ間の距離場の一貫性を確保するために、クラスタの境界の距離値を隣接クラスタに伝播させる処理である。更に、伝播された距離値を用いた局所距離変換の順序を決定する手段を提案する。これにより、局所距離変換の回数をできるだけ少なくすることができる。本発明により、後述するように１０億セル以上のボリュームモデルから距離場を生成することができる。
【００３５】
本発明では、三次元グリッド上に定義された二値化されたセル（ｃｅｌｌ、ボクセル、点）で定義されたボリュームデータを扱う。オブジェクトは、物体内部を表す前景セル（又は内部セル）と外部を表す背景セル（又は外部セル）で表現されている。距離場は、式（１）の距離関数ｄ（ｐ）で定義されるスカラ場である。
【００３６】
【数１】
【００３７】
ｐ∈Ｒ３はセルを表し，ｑは物体の境界上の内部セル（「境界セル」と呼ぶ）を表す。本発明では、内部セルの境界セルからの距離値を計算することを想定している。内部セルと外部セルの関係を逆転することにより、外部セルの境界セルからの距離値を計算することも可能である。本発明では、大規模ボリュームデータからの距離場計算手法に焦点を当てる。
【００３８】
本発明は、Ｏｕｔ−ｏｆ−Ｃｏｒｅ距離変換（ｄｉｓｔａｎｃｅ ｔｒａｎｓｆｏｒｍ：以下、「ＯｏＣＤＴ」又は「アウトオブコア距離変換」という）を提案する。
本発明によるアウトオブコア距離変換は、大規模データに対する距離変換を小さいＲＡＭで可能にする方法である。アウトオブコア距離変換は、ボリューム空間をａ×ｂ×ｃ個のクラスタに分割することから始まる。
【００３９】
次に、各クラスタに対して距離変換を適用する。これを局所距離変換（ｌｏｃａｌ ｄｉｓｔａｎｃｅ ｔｒａｎｓｆｏｒｍ：ＬＤＴ）と呼ぶ。局所距離変換は、他のクラスタに依存しないため、必要となるメモリのサイズは、一つのクラスタに相当する量で十分である。その他のクラスタについてはハードディスク上に保存できる。
局所距離変換は、各々独立して行われるため、隣接クラスタ間の境界で距離値の一貫性が損なわれる。そこで本発明では、クラスタ間伝播（ｉｎｔｅｒｃｌｕｓｔｅｒ ｐｒｏｐａｇａｔｉｏｎ：ＩＣＰ）によりこの問題を解消する。
【００４０】
クラスタ間伝播は、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させる。クラスタ間伝播によって距離値が更新されたセルを、本発明では「ＤＩＲＴＹセル」（汚染セル）と呼ぶ。汚染セルが現れたクラスタは、再び局所距離変換を適用する必要がある。本発明の手段では、局所距離変換とクラスタ間伝播を汚染セルがなくなるまで続ける。
【００４１】
アウトオブコア距離変換（ＯｏＣＤＴ）の計算時間は局所距離変換の回数に依存するため、局所距離変換の回数をできるだけ少なくするような局所距離変換の順番を決定する必要がある。そこで本発明では、各クラスタの汚染セルの最小値に基づく順序付けを提案する。これにより、少ない回数での収束が実現する。
【００４２】
図３（ａ）は機械部品のＣＴ画像のボリュームレンダリング画像であり、図３（ｂ）（ｃ）はその本発明による距離場計算結果である。
本発明の特徴の１つは、アウトオブコア距離変換法に基づく枠組みを距離変換に適用した点にある。これにより、図３（ｂ）（ｃ）に示したような、大規模ボリュームデータの距離場を計算可能にした。
【００４３】
本発明の利点として以下の点が挙げられる。
（１）大容量メモリを必要としない。本発明の手段で必要とするメモリは、クラスタ１個分であるため、一般的な３２ｂｉｔＰＣでも計算可能である。
（２）適用できるボリュームデータの制限が劇的に緩和された。従来手法は、ＲＡＭやＧＰＵのメモリに依存していたが、本発明の方法は、ハードディスク等のストレージの容量に依存する。
（３）局所距離変換は他のクラスタに依存しないため、マルチコアプロセッサを使用することで高速化が可能である。
（４）精度、データサイズ、速度は、局所距離変換で使用する距離変換法に依存しており、目的に応じて使い分けることが可能である。
（５）本発明の手段は、ｎ−Ｄ画像（ｎは１以上の整数）に適用可能である。
【００４４】
以下、本発明を詳細に説明する。
１ データ構造
はじめに、本発明で用いるデータ構造について図４，５を用いて説明する。Ｖは入力ボリュームモデルであり、Ｖは、ａ×ｂ×ｃ個（この例では５×５）のブロック形状のクラスタＣｉ（ｉ＝０，１，２，…）とクラスタ間に位置するクラスタインタフェース＜ｉ，ｊ＞に分解される。
クラスタＣｉは、ボリュームモデルＶの一部分のセルと、隣接する６つのクラスタインタフェースへのポインタを持つ。クラスタインタフェースは、＜ｉ，ｊ＞と表す。これは、クラスタＣｉとＣｊの重複領域に存在していることを表す。クラスタインタフェース＜ｉ，ｊ＞は、重複領域のセルとクラスタＣｉ、Ｃｊへのポインタを持つ。
各セルｖｉは、距離値ｖｉを持つ。本発明では、クラスタＣｊとクラスタインタフェース＜ｉ，ｊ＞に属するセルをそれぞれｖｉｊ，ｖｉ＜ｊ，ｋ＞と表す。セルｖｉ＜ｊ，ｋ＞は、対となるセルをＣｊ，Ｃｋにそれぞれ持つ。図４（Ａ）における○印で示すセルは、そのようなセルを表す。ｖｉｊ，ｖｉ＜ｊ，ｋ＞は、同じセルを共有しており、ｖｉｊ，ｖｉ＜ｊ，ｋ＞は常に、ｖｉ＜ｊ，ｋ＞＝ｍｉｎ（ｖｉｊ，ｖｉＫ）を満たす。
【００４５】
２ 本発明の概要
図４，５を用いて本発明の概要を説明する。図４（Ａ）は入力ボリュームモデルＶである。この図において、太い実線はオブジェクトの境界、その内側はオブジェクトの内部、斜線で示す外側は外部を示す。
本発明では、はじめに、ボリュームモデルＶをクラスタＣｉ（ｉ＝０，１，２，３）とクラスタインタフェース＜ｉ，ｊ＞に分解する。（図４（Ｂ））。三次元の場合、Ｖはａ×ｂ×ｃのクラスタとクラスタインタフェースに分解される。ａ，ｂ，ｃは、ユーザによって与えられるものとする。クラスタに分割した後、各セルｖｋ’に数２の式（２）の距離値を与えて初期化を行う（図４（Ｃ））。
【００４６】
【数２】
【００４７】
初期化が済んだクラスタとクラスタインタフェースは、一時ファイルとしてハードディスクに保存する。次に、一つのクラスタを選択し、ＲＡＭに格納する。そして、局所距離変換を適用して距離値を計算する。図４（Ｄ）では、Ｃ０が選択されている。
【００４８】
この局所距離変換によりクラスタＣ０内の全てのセルは、局所的に最適化される。つまり、クラスタと隣接するクラスタインタフェースが与えられている条件下において最適化されている状態を指す。
しかし、全体で見た場合、距離値が正しいという保証はない。例えば、図４（Ｄ）は、Ｃ０に対して局所距離変換を１回適用した結果であり、図５（Ｊ）は２回適用した結果である。Ｃ０のセルの幾つかが更新されていることがわかる。これは、クラスタ外のセルが最近セルだった場合にそれを見つけることができないためである。
本発明では、これをクラスタ間伝播（ｉｎｔｅｒ−ｃｌｕｓｔｅｒ ｐｒｏｐａｇａｔｉｏｎ：以下、ＩＣＰ）によって解決する。
【００４９】
図４（Ｅ）に示すとおり、局所距離変換を適用後のクラスタの境界セルの距離値は、対応するクラスタインタフェースのセルと異なっている。そこで、そのようなセルの距離値が一致するように書き換える。すなわちこれらの距離値を、隣接するクラスタの境界セルにコピーする。この処理をクラスタ間伝播と呼ぶ。
図４（Ｅ）ではＣ０からＣ１とＣ２へのクラスタ間伝播が適用されている。局所距離変換とクラスタ間伝播の処理（図４（ｄ）から図４（ｅ）までの処理）を１ステップとして数える。
クラスタ間伝播によって距離値が変更されたセルを、本発明では「ＤＩＲＴＹセル」（汚染セル）と呼ぶ。図４（Ｆ）〜図５（Ｊ）では、局所距離変換とクラスタ間伝播を汚染セルがなくなるまで繰り返す。この繰り返し処理は、付録にて証明を行っている。
処理が終了した時点で、全てのセルには正しい距離値が格納されており、大域的に最適化された状態であるといえる。最後に、クラスタを合成して距離場を作成する（図５（ｋ））。
【００５０】
以下、上述した局所距離変換、クラスタ間伝播等の詳細について述べる。
３ 局所距離変換
図６は、Ｗａｖｅｆｒｏｎｔ Ｃｈａｍｆｅｒ距離変換を用いた局所距離変換のアルゴリズムを示す。ｎｂｒ（ｖｍ）は、ｖｍの１−ｒｉｎｇ近傍（２６個）を表す。ｄｉｓｔ（ｖｉ，ｖｊ）は、ｖｉｖｊ間の距離である。ｓｗｅｅｐｉｎｇ ｃｈａｍｆｅｒ距離変換やｖｅｃｔｏｒ距離変換といった他の距離変換手法も局所距離変換として使うことができる。
【００５１】
４ クラスタ間伝播
クラスタ間伝播（Ｉｎｔｅｒ−Ｃｌｕｓｔｅｒ Ｐｒｏｐａｇａｔｉｏｎ：ＩＣＰ）は、局所距離変換を適用したクラスタＣｉからＣｉに隣接するクラスタＣｊへの距離値の伝播である。クラスタ間伝播は、クラスタＣｉとＣｊによって共有されているセルの距離値を比較する。図７にクラスタ間伝播のアルゴリズムを示す。
【００５２】
クラスタＣｉに局所距離変換を適用した後、クラスタ間伝播では、対応する境界セルｖｋｉｖｋｊの距離値を比較する。もしｖｋｉ＜ｖｋｊだった場合は、ｖｋｊはｖｋｉに置き換えられる。このようなセルは汚染セルとみなし、汚染セルが含まれるクラスタは、局所距離変換を再度適用する対象となる。これは、汚染セルが隣接セルの距離値よりも小さいため、局所距離変換によって値が更新されやすいためである。
【００５３】
本発明の実施例では、ファイルの入出力を減らすために、クラスタとクラスタが重複するようにクラスタを分割している。隣接クラスタが重複していない場合は、２６個の隣接クラスタに対して伝播処理を行う必要がある。それに対して、本発明の実施例では、６個であり、２３％程度のファイル入出力の削減を実現している。
【００５４】
更に、本発明では、クラスタ間伝播のためにクラスタインタフェースと呼ばれるデータ構造を導入している。クラスタインタフェースは、一見冗長に見えるが、アルゴリズムの高速化に寄与している。図８に簡単な例を示す。クラスタインタフェースなしのクラスタ間伝播では、６個の隣接クラスタを読み込む必要があるのに対して、クラスタインタフェースを導入した場合は、６個のクラスタインタフェースを読み込むだけでよく、明らかに読み込むデータ量を減らせている。
【００５５】
クラスタインタフェースは、局所距離変換処理の最適化にも利用できる。本発明では、クラスタ間伝播を分割することで局所距離変換を次の通り改良した。
（１） ハードディスクからクラスタＣｉを読み込む
（２） クラスタインタフェース＜ｉ，ｊ＞からＣｉへ伝播させる
（３） 局所距離変換を実行する
（４） クラスタＣｉからクラスタインタフェース＜ｉ，ｊ＞へ伝播される
（５） クラスタＣｉを保存する。
【００５６】
以上の処理によりファイル入出力が劇的に削減される。もし、クラスタ間伝播を一度に適用すると、７個のクラスタを局所距離変換を実行するごとに読み込む必要があった。それに対して、改良アルゴリズムでは、１個のクラスタだけで十分であり、クラスタインタフェースの利点を最大限活用している。
【００５７】
５ 最小汚染距離値（ＭＤＤ）を用いた局所距離変換適用順序の決定
局所距離変換とクラスタ間伝播によって大規模距離場は計算できるものの、計算速度に関する問題が残っている。図９に１次元における簡単な例を示す。どちらのクラスタから局所距離変換を適用するかによって局所距離変換の回数が異なっていることがわかる。もし、この差が大きいと、パフォーマンスの違いは顕著になる。よって、局所距離変換の回数が少なくなるような順序付けが必要となる。
【００５８】
最適な順序付けは、ボリュームデータやクラスタリング方法に依存することから、ほぼ不可能である。そこで、局所距離変換の回数が最小になるようなヒューリスティクスを導入する。本出願の発明者の観察により、より小さな距離値を持つ汚染セルを持つクラスタに対して優先的に局所距離変換を適用すればよいことがわかった。これは、そのようなクラスタが、隣接クラスタへ伝播しやすいためである。
【００５９】
ここで、局所距離変換適用順序付けの優先度を評価する基準として最小汚染距離値（ＭＤＤ）を導入する。最小汚染距離値は、「各クラスタの最小の距離値を持つ汚染セル」によって定義され、クラスタ間伝播によってセルが更新されたときに更新される。局所距離変換を適用した後のクラスタは、最小の優先順位を持つべきと考えられるので、局所距離変換を適用した後の最小汚染距離値は、無限大とする。
【００６０】
最小汚染距離値を用いた順位付けは簡単である。各ステップにおいて、各クラスタの最小汚染距離値の集合Ｍの中で最小である最小汚染距離値を持つクラスタを選択する。この最小汚染距離値（ＭＤＤ）を極小汚染距離値（ｍＭＤＤ）と呼ぶ。この繰り返し処理は、極小汚染距離値が無限大になったときに終了する。最終的な距離場は、クラスタを合成することによって得られる。
【００６１】
アウトオブコア距離変換をまとめると、図１０に示すとおりである。
【００６２】
６ 実施例および評価
本発明の実施例を図３、図１３に示す。“Ｅｎｇｉｎｅ−Ｈｅａｄ”“ＵＴ−ｆｉｇｕｒｉｎｅ”データは、ＣＴ画像を二値化して得られたものである。他のデータは、ポリゴンモデルをボクセル化して得られたものである。これらの例題の多くは、メモリの問題により従来は計算不可能であった。また各図は、表面をレンダリングしたものと距離場をボリュームレンダリングしたものを示している。ＵＴ−ｆｉｇｕｒｉｎｅデータが透明に見えるのは、モデルに空洞があるためである。
【００６３】
上述した全ての例題は、以下の環境のＷｉｎｄｏｗｓ(登録商標）ＸＰ ＰＣで計算した。
・Ｉｎｔｅｌ Ｃｏｒｅ２ Ｄｕｏ Ｅ６４００（２．１３ＧＨｚ，２−ｃｏｒｅ）
・２ＧＢ ＲＡＭ
・ＳＡＴＡ ３２０ＧＢ ＨＤＤ×２ （ＲＡＩＤ０構成）
【００６４】
さらに、本発明のプログラムは、マルチスレッドをサポートし中間ファイルは圧縮ライブラリｚｌｉｂを使って圧縮している。実験データを表１に示す。＃ＬＤＴは局所距離変換（ＬＤＴ）の回数である。Ｒは、式３で示すパフォーマンスの指標である。計算時間については、３ステップから構成される。「Ｉｎｉｔ．」は、ボリュームデータの分割に要した時間である。「ＯｏＣＤＴ」は、局所距離変換とクラスタ間伝播に要した時間である。「Ｃｏｍｐｏ．」はクラスタの合成に要した時間である。「Ｓｔｏｒａｇｅ」は中間データの最大サイズを、％は、圧縮比をあらわす。
【００６５】
（評価）
Ｗａｖｅｆｒｏｎｔ法の計算効率は、ｎをセルの数とした場合、Ｏ（ｎｌｏｇｎ） であることは知られている。局所距離変換の計算効率は、ｍをクラスタの数とした場合、Ｏ（ｎ／ｍ（ｌｏｇｎ−ｌｏｇｍ））である。局所距離変換の順序付けアルゴリズムでは、極小汚染距離値（ｍＭＤＤ）の探索に優先順位付きキューを使用しているので、対数時間を必要とすることから、本アルゴリズムの計算効率は、ｋを局所距離変換の回数とすると、Ｏ（ｋ・ｎ／ｍｌｏｇｍ（ｌｏｇｎ−ｌｏｇｍ））である。ここで、パフォーマンスを評価するために、従来のアルゴリズムとの比を表す評価値Ｒを数３の式（３）によって定義する。
【００６６】
【数３】
【００６７】
もしＲ＝１ならば、計算効率は、ｉｎ−ｃｏｒｅ（コア内処理）と同じであることがいえる。もしＲ＜１ならば、ｉｎ−ｃｏｒｅよりも小さいといえる。もちろんハードディスクを利用している以上、本発明のほうが計算時間は遅い。しかしＲは、パフォーマンスを評価する良い指標となりうると考えられる。表１にＲの計算結果を示している。内部セルのないクラスタに対しては、局所距離変換が実行されないのでほとんどの結果で２以下の結果が出ている。このように、本発明は、よく最適化されているといえる。
【００６８】
【表１】
【００６９】
本発明のパフォーマンスとクラスタ分割数の関連性を観察することは興味深い。図１１にクラスタ分割数とパフォーマンスの関連性を示す。始めに、初期化と合成処理において、クラスタ数が多いと計算時間が少ないことが判る。これは、多くのファイルを開いたり閉じたりするためである。この点に関しては、ＲＡＩＤ０（ストライピング）の導入により幾分改善される。一方で、アルゴリズム自体は、ある程度細かいほうが早くなる。これは、局所距離変換の計算コストが減少するのと、全て外部のクラスタの個数が増えた結果、クラスタあたりの局所距離変換の回数が少なくなるためである。両者をあわせると一定のクラスタ数において最小値が存在することが確認きる。しかしこのクラスタ数について、明確な傾向は確認できない。ただし、クラスタ数が多すぎたり、少なすぎるとパフォーマンスが低下することがわかる。
【００７０】
局所距離変換は、他のクラスタからは独立しているため、マルチコアプロセッサを用いることにより高速化が実現する。表２に、使用したコアの数により計算時間を比較した結果を示す。４スレッドを使用した場合には、１スレッドを使用した場合よりも２倍高速なのが判る。ただし、初期化と合成処理においては、マルチスレッドの効果はないため、距離変換のみに注目すると、４スレッドでは、１スレッドより３倍以上も高速なことが判った。これにより距離変換アルゴリズムは、マルチスレッド環境において高い並列性を持っていることがわかる。
【００７１】
【表２】
【００７２】
最小汚染距離値は、ｗａｖｅｆｒｏｎｔベースの局所距離変換の最適化に利用することもできる。局所距離変換は、最小汚染距離値より小さな距離値を持つセルに関しては、大域的に最適化されているため、局所距離変換の計算からはずすことができるという興味深い特徴を持つ（証明は省略する）。
【００７３】
図１２に各ステップにおける最小汚染距離値（ＭＤＤ）と計算時間をプロットした図を示す。この図から、２２４ステップ辺りから幾つかの局所距離変換が高速になっており、その際の最小汚染距離値が１以上であることがわかる。これは、クラスタ内の幾つかのセルが大域的に最適化され、局所距離変換から除外されたためである。
【００７４】
本発明は、クラスタとクラスタインタフェースを保存するための一時ファイルをハードディスク上に作成する。距離場は、よく同じ距離値を持つことから、圧縮ライブラリを用いることで高圧縮が実現する。表１の例題においても圧縮前と比較して１％程度とよく圧縮されていることがかる。例えば、６０億セル持つ“ｔｗｉｒｌ”モデルは、非圧縮では２４ＧＢあるにもかかわらず、中間データは２７０ＭＢである。このことから本手法で適用できるサイズの限界は、使用できるハードディスクに依存するということができ、それは、１０，０００３セルを越えるということができる。
【００７５】
本発明で得られる距離場の精度は、どの距離変換手法を用いたかによって決定される。本発明は、ＩＮ−ＣＯＲＥアルゴリズムと同等の計算結果が得られることから、クラスタの分割方法などには影響をうけない。
【００７６】
上述したように、本発明では、Ｏｕｔ−ｏｆ−Ｃｏｒｅ化された距離変換方法とプログラムを提案した。本発明は、局所距離変換とクラスタ間伝播により、従来手法がもつメモリ上の問題を解決した。また、実験結果により、従来と比較して巨大なボリュームデータから距離場を計算できることを示した。また、図１０に示した順序付けアルゴリズムは、局所距離変換の回数をできるだけ少なくする。実際に実験を通して、妥当な速度で計算できることを示した。
【００７７】
上述したように本発明の方法とプログラムによれば、ＲＡＭの容量を超える二値化した大規模ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶し、クラスタ毎に距離変換を行うので、距離変換を行わないクラスタは、ハードディスクに格納できるため、使用するメモリ量は、非常にコンパクトにできる。
また、このとき、クラスタ間で距離場の不連続性が発生するが、局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させ、局所距離変換ステップとクラスタ間伝播ステップを、クラスタ間伝播によって距離値が更新されるセルがなくなるまで繰り返すことで、全体として正しい距離場が生成できる。
また、前記クラスタ間伝播ステップにおいて、距離値が更新されたセルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行うことで、高速に収束させることができる。
従って本発明により、ＲＡＭの容量を超える大規模ボリュームデータから距離場を不連続性が発生することなく全体として正しく生成することが可能になった。
【００７８】
なお、本発明は上述した実施形態に限定されず、本発明の要旨を逸脱しない範囲で種々変更できることは勿論である。
【図面の簡単な説明】
【００７９】
【図１】本発明の方法を実行するための装置構成図である。
【図２】本発明の方法を示す全体フロー図である。
【図３】機械部品のＣＴ画像のボリュームレンダリング画像とその本発明による距離場計算結果である。
【図４】本発明で用いるデータ構造の第１説明図である。
【図５】本発明で用いるデータ構造の第２説明図である。
【図６】局所距離変換のアルゴリズムを示す図である。
【図７】クラスタ間伝播のアルゴリズムを示す図である。
【図８】クラスタインタフェースの例を示す図である。
【図９】局所距離変換適用の順序を示す例である。
【図１０】本発明のアウトオブコア距離変換のアルゴリズムを示す図である。
【図１１】クラスタ分割数とパフォーマンスの関連性を示す図である。
【図１２】各ステップにおける最小汚染距離値（ＭＤＤ）と計算時間をプロットした図である。
【図１３】本発明による距離場の計算結果を示す図である。
【符号の説明】
【００８０】
２ 入力装置、
３ 外部記憶装置、
４ 内部記憶装置、
５ 中央処理装置、
６ 出力装置
【特許請求の範囲】
【請求項１】
ＲＡＭとハードディスクを有するコンピュータを用いて、
入力装置によりＲＡＭの容量を超える二値化した大規模ボリュームデータをハードディスクに入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを備えたことを特徴とする大規模ボリュームデータの距離場生成方法。
【請求項２】
前記クラスタ分割ステップにおいて、ボリュームデータを、互いに隣接した複数のセルからなるブロック形状の複数のクラスタと、クラスタ間に位置する複数の連続したセルからなるクラスタインタフェースに分割し、
各クラスタは、ボリュームデータの一部分のセルと、隣接する６つのクラスタインタフェースへのポインタを有し、
各クラスタインタフェースは、隣接する２つのクラスタと重複するセルと、当該２つのクラスタへのポインタを有する、ことを特徴とする請求項１に記載の大規模ボリュームデータの距離場生成方法。
【請求項３】
前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタに対し、前記局所距離変換ステップとクラスタ間伝播ステップを、前記汚染セルがなくなるまで繰り返す、ことを特徴とする請求項１に記載の大規模ボリュームデータの距離場生成方法。
【請求項４】
前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行う、ことを特徴とする請求項３に記載の大規模ボリュームデータの距離場生成方法。
【請求項５】
コンピュータのハードディスクにＲＡＭの容量を超える二値化した大規模ボリュームデータを入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを実行するための大規模ボリュームデータの距離場生成プログラム。
【請求項１】
ＲＡＭとハードディスクを有するコンピュータを用いて、
入力装置によりＲＡＭの容量を超える二値化した大規模ボリュームデータをハードディスクに入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを備えたことを特徴とする大規模ボリュームデータの距離場生成方法。
【請求項２】
前記クラスタ分割ステップにおいて、ボリュームデータを、互いに隣接した複数のセルからなるブロック形状の複数のクラスタと、クラスタ間に位置する複数の連続したセルからなるクラスタインタフェースに分割し、
各クラスタは、ボリュームデータの一部分のセルと、隣接する６つのクラスタインタフェースへのポインタを有し、
各クラスタインタフェースは、隣接する２つのクラスタと重複するセルと、当該２つのクラスタへのポインタを有する、ことを特徴とする請求項１に記載の大規模ボリュームデータの距離場生成方法。
【請求項３】
前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタに対し、前記局所距離変換ステップとクラスタ間伝播ステップを、前記汚染セルがなくなるまで繰り返す、ことを特徴とする請求項１に記載の大規模ボリュームデータの距離場生成方法。
【請求項４】
前記クラスタ間伝播ステップにおいて、距離値が更新された汚染セルを有するクラスタの距離値の小さい順に、局所距離変換ステップを行う、ことを特徴とする請求項３に記載の大規模ボリュームデータの距離場生成方法。
【請求項５】
コンピュータのハードディスクにＲＡＭの容量を超える二値化した大規模ボリュームデータを入力する入力ステップと、
前記ボリュームデータをＲＡＭの容量より十分小さい複数のクラスタに分割してハードディスクに記憶するクラスタ分割ステップと、
前記クラスタ毎に距離変換してクラスタ毎の距離場生成を行う局所距離変換ステップと、
前記局所距離変換後に境界クラスタの距離値を、隣接クラスタに伝播させるクラスタ間伝播ステップと、
前記クラスタ毎の距離場を統合してボリュームデータ全体の距離場生成を行う距離場統合ステップと、
出力装置に統合されたボリュームデータ全体の距離場を出力する出力ステップとを実行するための大規模ボリュームデータの距離場生成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００８−１８１２８６（Ｐ２００８−１８１２８６Ａ）
【公開日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願番号】特願２００７−１３６０３（Ｐ２００７−１３６０３）
【出願日】平成１９年１月２４日（２００７．１．２４）
【出願人】（５０３３５９８２１）独立行政法人理化学研究所 (1,056)
【Ｆターム（参考）】
【公開日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願日】平成１９年１月２４日（２００７．１．２４）
【出願人】（５０３３５９８２１）独立行政法人理化学研究所 (1,056)
【Ｆターム（参考）】
[ Back to top ]