(57)【要約】【課題】  本発明は、物質の境界部分や薄板の中立面を形成するためのメッシュであっても形成可能なセル集合を提供する。また、本発明は、このようなセル集合を生成する方法も提供する。【解決手段】  セル集合の生成方法は、以下のステップを有する：（１）背景セル集合について、トンネル辺またはトンネル点を持つ背景セルを探索するステップ；（２）発見された背景セルの場所に、前景セルを追加するステップ。  この方法は、さらに以下のステップを備えていてもよい：（３）セル集合から境界セルを探索するステップ；（４）発見された境界セルを削除するステップ  本発明のセル集合は、面セルから構成されており、かつ、以下の２条件を満たしている：（１）トンネル不能（２）厚さが１。【選択図】図１２
2006018513.tif 000002
【特許請求の範囲】
【請求項１】
以下のステップを備えたことを特徴とする、セル集合の生成方法：
（１）背景セル集合について、トンネル辺またはトンネル点を持つ背景セルを探索するステップ；
（２）発見された背景セルの場所に、前景セルを追加するステップ。
【請求項２】
前記ステップ（１）において、前記背景セルが複数発見された場合には、評価関数を用いて優先順位を決定することを特徴とする、請求項１記載の生成方法。
【請求項３】
前記背景セルが発見できなくなるまで、前記ステップ（１）および（２）を繰り返すことを特徴とする、請求項１又は２に記載の生成方法。
【請求項４】
以下のステップを備えたことを特徴とする、セル集合の生成方法：
（１）セル集合から境界セルを探索するステップ；
（２）発見された境界セルを削除するステップ。
【請求項５】
前記ステップ（１）において、前記境界セルが複数発見された場合には、評価関数を用いて優先順位を決定することを特徴とする、請求項４記載の生成方法。
【請求項６】
前記境界セルが発見できなくなるまで、前記ステップ（１）および（２）を繰り返すことを特徴とする、請求項４又は５に記載の生成方法。
【請求項７】
前記請求項１〜３のいずれか１項に記載の方法を実行した後、請求項４〜６のいずれか１項に記載の方法を実行することを特徴とする、セル集合の生成方法。
【請求項８】
面セルから構成され、かつ、以下の２条件を満たしていることを特徴とするセル集合：
（１）トンネル不能
（２）厚さが１。
【請求項９】
以下のステップをコンピュータに行わせることを特徴とする、セル集合の生成用プログラム：
（１）背景セル集合について、トンネル辺またはトンネル点を持つ背景セルを探索するステップ；
（２）発見された背景セルの場所に、前景セルを追加するステップ。
【請求項１０】
以下のステップをコンピュータに行わせることを特徴とする、セル集合の生成用プログラム：
（１）セル集合から境界セルを探索するステップ；
（２）発見された境界セルを削除するステップ。
【請求項１１】
以下のステップを行うことを特徴とする、セル集合の生成用コンピュータ：
（１）背景セル集合について、トンネル辺またはトンネル点を持つ背景セルを探索するステップ；
（２）発見された背景セルの場所に、前景セルを追加するステップ；
（３）セル集合から境界セルを探索するステップ；
（４）発見された境界セルを削除するステップ。
【請求項１２】
等値面生成手法により多面体を生成できるセル集合を生成するための方法であって、以下のステップを実行することにより、請求項８記載のセル集合を生成することを特徴とする生成方法：
（１）セル集合にセルを追加するステップ
（２）セル集合からセルを削除するステップ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セル集合の生成方法、及び、これにより生成されたセル集合に関するものである。本発明は、特に、ボリュームモデルから面モデルを生成するためのセル抽出法に関係している。
【背景技術】
【０００２】
近年、産業用X線CT (Computed Tomography) 計測が普及し、製品の検査のみならず、CTデータから3次元形状モデルを生成し、このモデルを、CAD (Computer Aided Design) やCAE (Computer Aided Engineering) システムで利用するようになってきた。
【０００３】
図１にCTデータの例を示す。この図は、エンジンブロックの断面画像である。このような断面画像を、ある間隔で多数枚撮影することによって、3次元画像、いわゆるボリュームモデルを生成する。ボリュームモデルの画素のことをボクセルと呼ぶ。ボクセルは画像の値、すなわちボクセル値をもつ。ＣＴの場合は、その場所での撮影対象物の密度値にほぼ比例した実数値、あるいは整数値をもつ。
【０００４】
さて、このようなボリュームモデルは、測定対象物の内部構造（例えば鋳造品の「ひけ巣」）を観察するには有効であるが、前述のように、ボリュームモデルのままではCADやCAEなどのシステム利用することができない。そのため、ボリュームモデルから、物体の形を表す多面体を生成することが行われる。多面体としては、すべての面が3角形からなる3角形メッシュが利用されることが多い。
【０００５】
図２に三角形メッシュの例を示す。図（A）は比較的単純な例であるが、図（B）は微小な三角形で立体形状を表している。X線CTによるボリュームモデルから生成されるのは後者のタイプであり、三角形の数が数百万から数千万個にもなる。
【０００６】
このようにボリュームデータから三角形メッシュ（以下ではメッシュと呼ぶ）を生成する手法（ここでは面生成手法と呼ぶ）に、等値面生成 (iso-surfacing) がある。最も代表的な方法として、マーチングキューブ法と呼ばれる方法がある。等値面生成手法について以下に説明する。
【０００７】
（等値面生成手法）
（マーチングキューブ法）
マーチングキューブ法の詳細は下記非特許文献１に記載されている。ボリュームモデルは、2次元格子状に画素が並んだ断面画像を多数重ねたものなので、全体として3次元格子状に画素（ボクセル）が並んだものとなる。この中から、8個のボクセルで構成される直方体（3方向の格子間隔がすべて等しいときには立方体）をセルと呼ぶ。
【０００８】
さて、物体を計測した時に、その物体の表面に相当する部分をメッシュとして抽出することが、マーチングキューブ法の目的である。物体の外部（背景）と物体とでは密度が異なるので、それぞれに相当するボクセルのボクセル値も異なった値をとる。そこで、背景と物体のボクセル値を区別する閾値θを設定する。
【０００９】
そうすると、セルの8個のボクセルについて、そのボクセル値がθよりも大きいものと、小さいものに分けることができる（簡単のためボクセル値がθと等しい場合を除く）。そして、背景と物体との境界となる面は、θよりも大きいボクセルとθよりも小さいボクセルの間を通ることが分かる。そこで、セルの12個の辺について、その両端のボクセルの一方の値がθよりも大きく、他方がθよりも小さい場合、境界面は、その辺を切断するであろう。切断する場所は、その両端のボクセル値とθから内分によって求めることができる。このようにして境界面と辺との干渉点を求め、次に図３のパタンに従ってセルの中に三角形を生成する。セルの対称性を考えると、この図（ａ）から図（ｎ）の14パタンで十分であることが知られている。この方法は、例えば下記非特許文献２のように、多くの拡張が行われている。
【００１０】
（双対法(dual contouring)）
等値面生成手法のもう一つの方法として、双対法が知られている。この方法では、図4に示すように、2×2状に並んだ4個のセルの中心にある辺を考える。この辺の両端のボクセルの値の内の一方がθよりも大きく、他方が小さい場合に、その辺の上に、マーチングキューブ法と同様にして点を生成する。さらに、辺の周りの四つのセルの中心とを結んで三角形を生成する。この方法は、下記非特許文献３および４で紹介されている。
【００１１】
（等値面生成法のまとめ）
以上のように、ボリュームモデルから三角形メッシュを生成する等値面生成手法では、ボリュームモデルのボクセル値に対して、物体の境界を表す閾値を設定し、セル単位（マーチングキューブ法ではセル単位、双対法では４セル単位）で三角形を生成していく。
【００１２】
（等値面生成の問題点）
（薄板構造の中立面生成の問題点）
図5（Ａ）は、鉄板などの薄板構造をX線CTで撮影した例で、簡単のために2次元で表している。これに等値面手法を適用すると、図5（B）のようなメッシュが生成される。しかし、薄板を設計する際には、このような薄い厚さをもった形状ではなく、図（C）のような中立面の形状を表すサーフェスモデルで設計されることが多い。また、有限要素法などで解析計算を行う場合も、やはり中立面形状が必要となる。
【００１３】
このような中立面は、ボリュームモデルに対して閾値を設定することによっては抽出することができない。そこで、中立面を生成するためのセル集合や、その生成方法が必要となる。
【００１４】
（多媒質部品の物質境界面生成の問題点）
機械部品の多くは、複数の材質で構成される。図１のエンジンブロックでは、灰色のところがアルミで、白色のところが鉄で出来ており、空気と合わせて、この画像には三つの媒質が存在することになる。そして、異なる物質間の閾値も、当然複数存在することになる。マーチングキューブなどの等値面生成手法では、閾値は一つしか設定できないため、例えば、エンジンブロックの外形形状を生成するために、アルミと空気の閾値でメッシュを生成すると、鉄と空気の境界では正しい閾値とはならないために、メッシュも正しく求まらない。
【００１５】
図６に、多媒質部品の境界面生成の概要を示す。図６は、鉄、アルミ、空気の3媒質が出会う部分の様子を模式的に示したものである。
【００１６】
最初に、ボクセルを、鉄、アルミ、空気、さらには、それらのそれぞれ相異なる2媒質の境界、さらには3媒質の境界に分類する(図６Ａ)。これはボクセル値や物質境界の条件を使って行える。次に、2媒質境界のセルについては、その2媒質間の閾値を設定し、その閾値をボクセル値が挟むような（ボクセルが閾値よりも大きい値と、小さい値をもつような）セルを抽出し(図６Ｂ)、これによってそれぞれの2媒質で、該当する2媒質間の閾値を用いて境界面を生成できる。しかし、3媒質が集まるような領域では、閾値が定まらないので、閾値から面を生成するセルを抽出することはできず、面を生成することができない。
【非特許文献１】W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques, pages 163-169. ACM Press, 1987.
【非特許文献２】L. P. Kobbelt, M. Botsch, U. Schwanecke, and H.-P. Seidel. Feature sensitive surface extraction from volume data. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 57-66. ACM Press, 2001.
【非特許文献３】S. F. Frisken, R. N. Perry, A. P. Rockwood, and T. R. Jones. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 249-254. ACM Press/Addison-Wesley Publishing Co., 2000.
【非特許文献４】T. Ju, F. Losasso, S. Schaefer, and J. Warren. Dual contouring of hermite data. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, pages 339-346. ACM Press, 2002.
【発明の開示】
【発明が解決しようとする課題】
【００１７】
マーチングキューブ法や双対法のような等値面生成手法では、セルや2x2状のセルを単位として面を生成するが、見方を変えると、閾値を用いて、セル全体の中から面を生成すべきセルを抽出していると見ることができる。前述の薄板の場合や多媒質の場合は、閾値ではこのようなセル集合を抽出することはできなかったが、もし他の方法によって求めることができれば、そこに面を生成することができると考えられる。このようなセル集合は、まず適当なセル集合（薄板の場合はスケルトン化 (skeletonization) と呼ばれる処理によって求められる中立面付近のセル集合で、多媒質境界の場合は前述の媒質の分類によるセル集合）を求め、それをマーチングキューブ法や双対法を適用して面を生成できるようなセル集合へと適合化させることによって求めることができる(図６Ｃ)。そして、このようなセル集合が得られれば、そのセルのボクセルに符号を与え、マーチングキューブ法を適用して面を生成することができる（図６Ｄ）。ただし、ここではメッシュに分岐が生じるので、非多様体のマーチングキューブ法というものを用いる。
【００１８】
本発明は、このようなメッシュを生成できるセル集合の生成方法及びこれにより得られたセル集合を提供することを目的としている。
【課題を解決するための手段】
【００１９】
本発明に係るセル集合の生成方法は、以下のステップを備えている：
（１）背景セル集合について、トンネル辺またはトンネル点を持つ背景セルを探索するステップ；
（２）発見された背景セルの場所に、前景セルを追加するステップ。
【００２０】
前記ステップ（１）において、前記背景セルが複数発見された場合には、評価関数を用いて優先順位を決定することができる。
【００２１】
前記背景セルが発見できなくなるまで、前記ステップ（１）および（２）を繰り返すことも可能である。
【００２２】
本発明に係るセル集合の生成方法は、以下のステップを備えた構成であっても良い：
（１）セル集合から境界セルを探索するステップ；
（２）発見された境界セルを削除するステップ。
【００２３】
このステップ（１）において、前記境界セルが複数発見された場合には、評価関数を用いて優先順位を決定することができる。また、前記境界セルが発見できなくなるまで、前記ステップ（１）および（２）を繰り返すこともできる。
【００２４】
前者の生成方法におけるステップ（１）（２）を実行した後、後者の生成方法におけるステップ（１）（２）を実行することも可能である。
【００２５】
本発明に係るセル集合は、面セルから構成され、かつ、以下の２条件を満たしているものである：
（１）トンネル不能
（２）厚さが１。
【００２６】
本発明に係るセル集合の生成用プログラムは、以下のステップをコンピュータに行わせることを特徴としている：
（１）背景セル集合について、トンネル辺またはトンネル点を持つ背景セルを探索するステップ；
（２）発見された背景セルの場所に、前景セルを追加するステップ。
【００２７】
本発明に係るセル集合の生成用プログラムは、以下のステップをコンピュータに行わせることを特徴とするものであってもよい：
（１）セル集合から境界セルを探索するステップ；
（２）発見された境界セルを削除するステップ。
【００２８】
本発明に係るセル集合の生成用コンピュータは、以下のステップを行うことを特徴としている：
（１）背景セル集合について、トンネル辺またはトンネル点を持つ背景セルを探索するステップ；
（２）発見された背景セルの場所に、前景セルを追加するステップ；
（３）セル集合から境界セルを探索するステップ；
（４）発見された境界セルを削除するステップ。
【００２９】
本発明に係る生成方法は、等値面生成手法により多面体を生成できるセル集合を生成するための方法であって、以下のステップを実行するものであってもよい：
（１）セル集合にセルを追加するステップ
（２）セル集合からセルを削除するステップ。
【００３０】
これらのステップを実行することにより、面セルから構成され、かつ、以下の２条件を満たしていることを特徴とするセル集合を得ることができる。
（１）トンネル不能
（２）厚さが１。
【発明の効果】
【００３１】
本発明によれば、「対象物を表すセルの集合」を用いて、「所望のメッシュを生成できるセル集合」を生成することができる。このセル集合に対して、適当な等値面生成手法を適用することにより、メッシュを生成することができる。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の一実施形態を説明する。始めに、説明のために必要な概念を整理しておく。
【００３３】
（セルトポロジーの紹介）
ここでは、まず、セルについて説明し、その後、セル同士の関係などを表現するための概念について説明する。
【００３４】
（セル）
ボリュームモデルの画素をボクセルと呼ぶ。セルとは、ボクセルを頂点に持つ直方体要素である。セルは、図７に示すように、面、辺（稜線）、点（頂点）からなり、隣り合うセルと面・辺・点を共有する。
【００３５】
(点、辺、面の近傍)
点（辺、面）に接続する8 (4, 2) 個のセルを、点（辺、面）の近傍と呼ぶ。
【００３６】
2006018513.tif 000003
【００３７】
2006018513.tif 000004
【００３８】
2006018513.tif 000005
【００３９】
2006018513.tif 000006
【００４０】
2006018513.tif 000007
【００４１】
2006018513.tif 000008
【００４２】
2006018513.tif 000009
【００４３】
（前景セルと背景セル）
面生成手法の適用対象となるセルを前景セル(foreground cell)と、それ以外のセルを背景セル（background cell）とよぶ。
【００４４】
2006018513.tif 000010
【００４５】
2006018513.tif 000011
【００４６】
2006018513.tif 000012
【００４７】
2006018513.tif 000013
【００４８】
2006018513.tif 000014
【００４９】
以下、トンネル辺およびトンネル点の定義を厳密に行う。
【００５０】
2006018513.tif 000015
【００５１】
2006018513.tif 000016
【００５２】
2006018513.tif 000017
【００５３】
（セル適合化）
ここでは、セル適合化について説明する。セル適合化は、任意の前景セル集合が入力として与えられた時、セルの追加・削除を行うことで、キュービックシェルに変換する処理のことをいう。
【００５４】
2006018513.tif 000018
【００５５】
2006018513.tif 000019
【００５６】
2006018513.tif 000020
【００５７】
2006018513.tif 000021
【００５８】
2006018513.tif 000022
【００５９】
（ステップＳａ−３）
最も優先度の高い背景セルの場所に、前景セルを追加する。
【００６０】
2006018513.tif 000023
【００６１】
2006018513.tif 000024
【００６２】
2006018513.tif 000025
【００６３】
2006018513.tif 000026
【００６４】
（ステップＳｂ−３）
最も優先度の高い前景セルを削除する。
【００６５】
2006018513.tif 000027
【００６６】
2006018513.tif 000028
【００６７】
以上のようにセルの追加処理と削除処理を適用することで、トンネル不能かつ厚さ1のキュービックシェルが求まる。
【００６８】
（実施例）
前記したようなセルの生成方法は、コンピュータおよびコンピュータソフトウエアにより実行できる。図１４に一般的なコンピュータのハードウエア構成を示す。このコンピュータは、ＣＰＵ１と、メモリ２と、表示部３とを備えている。メモリ２は、処理に必要なデータ（例えば画素データ）と、処理をコンピュータに行わせるプログラムとを格納している。ＣＰＵ１は、プログラムに従って、前記したような生成方法を実行し、その結果を表示部３に出力する。使用者は、表示部３を介して結果を視認することができる。表示部３は、例えばプリンタやディスプレイである。
【００６９】
なお、前記実施形態の記載は単なる一例に過ぎず、本発明に必須の構成を示したものではない。各部の構成は、本発明の趣旨を達成できるものであれば、上記に限らない。
さらに、前記したコンピュータの機能ブロックどうしは、複合して一つの機能ブロックに集約されても良い。また、一つの機能ブロックの機能が複数の機能ブロックの協働により実現されても良い。さらに、前記した機能ブロックは、機能として存在していればよく、機能実現のための手段としては、ハードウエア、コンピュータソフトウエア、これらの組み合わせなどの、任意のものを用いることができる。一つの機能ブロックが、物理的に離散した位置に配置されたハードウエアやコンピュータソフトウエアの協働により実現されてもよい。
【図面の簡単な説明】
【００７０】
【図１】産業用Ｘ線ＣＴ画像の一例を示す図である。
【図２】三角形メッシュの一例を示す図である。
【図３】マーチングキューブ法を説明するための説明図であって、図（ａ）から図（ｎ）はセル中に生成する三角形の例を示す。
【図４】双対法を説明するための説明図である。
【図５】薄板構造物における中立面生成の必要性を説明するための説明図であって、図（Ａ）は薄板構造物のＣＴ画像の模式図、図（Ｂ）はマーチングキューブ法で生成されたボリュームモデル、図（Ｃ）は必要な中立面である。
【図６】多媒質部品における中立面生成の必要性を説明するための説明図であって、図（Ａ）は多媒質部品の分類、図（Ｂ）は、各２媒質間で、閾値を含むセルを抽出した状態、図（Ｃ）は、適合化した状態、図（Ｄ）は媒質間の境界面を示す図である。
【図７】セルおよび面・辺・点を説明するための説明図である。
【図８】図（Ａ）は面セル、図（Ｂ）は境界セルを、簡単のために２次元で示した説明図である。
【図９】トンネル不能な状態を説明するための説明図であって、図（ａ）は辺トンネルを有する状態、図（ｂ）は点トンネルを有する状態を示している。
【図１０】トンネルを有する状態を説明するための説明図であって、図（ａ）は辺トンネルを有する状態、図（ｂ）は点トンネルを有する状態を示している。
【図１１】厚さ１を満たさないようなセルの配置（２×２×２セル）を概念的に示す図である。
【図１２】セルの追加処理を説明するためのフローチャートである。
【図１３】セルの削除処理を説明するためのフローチャートである。
【図１４】セルの生成方法に使用するコンピュータの一例を説明するための概念的なブロック図である。
【符号の説明】
【００７１】
１  ＣＰＵ
２  メモリ
３  表示部
【図４】
2006018513.tif 000029
【図１０】
2006018513.tif 000030
【図１２】
2006018513.tif 000031
【図１３】
2006018513.tif 000032
【図１４】
2006018513.tif 000033
【図１】
2006018513.tif 000034
【図２】
2006018513.tif 000035
【図３】
2006018513.tif 000036
【図５】
2006018513.tif 000037
【図６】
2006018513.tif 000038
【図７】
2006018513.tif 000039
【図８】
2006018513.tif 000040
【図９】
2006018513.tif 000041
【図１１】
2006018513.tif 000042