This dissertation presents methods for automatic segmentation optimization of 3D models, efficient sealed segmentation of surface mesh as well as powerful segmentation of tetrahedral mesh. Mesh segmentation and its optimization are research problems in geometrical modeling and computer graphics, which are widely applied in fields including modeling, reverse engineering systems, skeleton extraction, collision detection, 3D shape retrieval, simplification and remeshing.

In this thesis, shape segmentation optimization is firstly studied. A novel graph cut method is presented to smooth the irregular segment boundary curves between two adjacent segments. To further straighten these boundaries, we implement virtual triangle subdivision and the graph cut approach to add points and edges on these curves. We also rectify these boundaries with simple straightest geodesics.

Then we study sealed mesh segmentation problems. A novel method is provided for clustering a closed 2-manifold triangular mesh into a set of sub-components, which are sealed as well as whose surfaces are smoothed by the Laplacian smoothing.

Finally tetrahedral (triangular) shape segmentation method is presented. We generate segmented isotropic tetrahedral (triangular) meshes while taking 2D image (3D volumetric image) without segmentation as the input. A technique based on centroidal Voronoi tessellation is used to construct isotropic triangular (tetrahedral) meshes where considerably more vertices concentrate on boundaries between patches (objects). These meshes are segmented into patches (objects) by a graph cut method.

楊 彩雲提出の本論文は「Mesh Segmentation Methods based on Graph Cut(グラフカット法に基づくメッシュセグメンテーション手法)」と題し,全5章よりなり,各種のメッシュのセグメンテーション問題について、グラフカット法の適用を試みている。

ここでいうメッシュは、コンピュータグラフィックスや構造解析などで利用されているもので、三角形や四面体を要素とし、物体の形状を表現するために利用されるものである。セグメンテーションは、物体の全体形状を表すようなメッシュを、意味のある部分領域に自動的に分割する問題で、どのような部分領域を求めたいかによって様々な問題設定が可能である。また、グラフカット法は、画像や動画などのセグメンテーションに有効な方法として近年注目を浴びている方法で、一部メッシュのセグメンテーションにも適用されていたが、本研究ではそれが多様なメッシュのセグメンテーション問題にも有効であることを示している。

第1章では,研究の背景を説明し,研究の目的について述べている。特に近年物体の形状をスキャンして計算機に取り組むことのできるスキャナーが発達し、物体の形を容易に取得することができるようになってきた。これをコンピュータグラフィックスや機械設計で利用するためには、スキャンデータを分割する必要が生じており、セグメンテーションに関する研究が多数行われている。ここでは、それらに関する代表的な手法等についてサーベイしている。特に本研究でベースとしているグラフカット法についても述べている。

第2章では、関連の深い先行研究である"Quadric Surface Extraction by Variational Shape Approximation (以下、QSE法と呼ぶ)" という研究を拡張する形で行った研究について示している。QSE法は、比較的規則正しい並びをしている三角形メッシュに対して、2次曲面で局所的に近似できる部分を領域として抽出する方法を示しているが、その時に生じる領域のジグザグな境界をグラフカットによって平滑化する方法を示している。しかし、QSE法ではスキャナーによって生成された不規則なメッシュには適用することができなかった。そこで、本研究では境界を再分割とグラフカットを組み合わせて平滑化する新しい方法を提案している。さらに、より平滑化の必要な場合への対応として、測地線の計算に基づく方法も併せて提案している。

第3章では、"Sealed Decomposition"という三角形メッシュの新しいセグメンテーションの方法を提案している。多くの場合、三角形メッシュは、位相的には閉じた2多様体曲面となっている。しかし、セグメンテーションを行うと、各領域は境界付の2多様体となってしまう。そこで、ここでは三角形メッシュから、まずそれを境界とする四面体メッシュを作り、この四面体メッシュに対してグラフカットによるセグメンテーションを行う。この四面体で構成される領域の境界をとることによって、閉じた三角形メッシュを生成するという新しい手法を提案している。四面体メッシュにグラフカットを適用したのは、この研究が最初であり、そのためのコスト関数として、できるだけ凸部が抽出できるようなものを提案している。これによって、おおむね凸分割に近いようなセグメンテーションを実現し、他のセグメンテーションとも比較によってその有効性を示している。

第4章では,より新しい問題に挑戦している。産業用CT装置によって、工業製品などをスキャンすると、材質の密度を反映したCT画像が得られる。そこでこのCT画像から三角形メッシュや、あるいは3次元のCT画像の場合には四面体メッシュを生成し、さらにこれらのメッシュ上で材質の境界をグラフカットによって求める手法を提案している。CT画像からメッシュを生成する部分では重み付きの重心ドロネー分割という方法を適用しているが、重みの計算方法などについて工夫をしている。さらにグラフカットでは、材質の境界を表現するために、CT値によってメッシュの要素や要素間のコスト関数を提案している。特に2次元では良好な結果を得ている。

第5章では結論を述べている。以上の各章での成果をまとめるとともに、さらにその特徴、適用限界について述べている。また将来課題についても示してある。

以上を要約するに,本研究は、グラフカット法が様々なメッシュのセグメンテーションにおいて有効な手法となりえることを、セグメンテーション境界の平滑化、"Sealed Decomposition"、さらには材質を表す画像上でのメッシュセグメンテーションなどの具体的な課題に適用して見せることによって示しており、本分野に関して大きな貢献をしたと言える.

よって本論文は博士(工学)の学位請求論文として合格と認められる.