表面メッシュ上での最適クラスタリングは,メッシュの領域分割のための重要な道具である.メッシュ上でのクラスタリングでは,メッシュの頂点(もしくは面)がクラスタリングされ,各クラスタが連結であるという制約が課される.また,最適クラスタリングとは目的関数を最適にするクラスタリングのことで,これを計算することはほとんどの場合にはNP 困難なので,実際には準最適なクラスタリングを計算することが目標とされる.メッシュの領域分割とは,各領域が一様な性質を持つようにメッシュを分割することで,テクスチャアトラス作成・形状近似・形状解析などの多くの応用を持つ.応用ごとに適切な目的関数を設定し,最適クラスタリングを計算することにより,一様な性質を持つ領域へとメッシュを分割することができる.

本論文は,表面メッシュ上での最適クラスタリングの計算法と位相保存について論じたもので,第1 章で研究の背景などを述べ,第2 章で基本事項の準備をした後,主要成果をそのあとの四つの章でまとめている.

第3 章では,最適クラスタリングの効率的な初期化法を提案している.最適クラスタリングは,初期化法により初期クラスタリングを計算し,それに反復改善法を適用することによって計算できる.初期クラスタリングは反復改善法の収束速度に大きな影響を与えるので,良質の初期クラスタリングを効率的に計算できる初期化法が望まれている.本章は領域融合法を利用した初期化法を提案し,初期化法として多く利用されているランダムサンプリング・最遠点サンプリングよりも効率的な初期化法であることを実験により示した.また,この方法は位相を保存するクラスタリングの計算を行うことができるという利点も持っている.

第4 章では,メモリに収まらないほどの大規模なメッシュに対しての最適クラスタリングの計算法を提案している.近年では3 次元形状測定装置の発展により非常に詳細なメッシュが得られるようになっており,メモリに収まらないほどの大規模なメッシュも存在する.既存の最適クラスタリングの計算法は,メッシュが全てメモリに収まることを仮定しており,そのようなメッシュを処理することができない.大規模メッシュを処理するには,データの一部のみをメモリに載せて処理を進めるOut-of-Core 法を利用する必要がある.本章では,最適クラスタリングを計算するOut-of-Core 法を提案した.これはOut-of-Core 初期法とOut-of-Core反復改善法により構成される.初期化法としては,Out-of-Core 領域融合法を提案した.これは,ストリーム処理を利用したOut-of-Core 辺縮約簡略化法をもとに設計した.反復改善法としては,Out-of-Core データ交換法を提案した.データ交換法とは最適クラスタリングの計算に利用される反復改善法で,データ交換を繰り返し適用する方法である.データ交換は局所的な情報のみを必要とするという特徴を持つ.このデータ交換法をストリーム処理に適応させることにより,Out-of-Core データ交換法を設計した.提案法により,大規模メッシュに対しても最適クラスタリングが計算できるようになった.形状近似のための最適クラスタリングは大規模メッシュに対して行われることが多いので,これは大きな意義のあることである.

第5 章と第6 章では,位相保存についての研究を述べている(ここでは,多様体的な三角形メッシュ上での頂点クラスタリングのみを扱う).より具体的には,Lloyd 法における位相保存の問題を扱っている.Lloyd法とは,最適クラスタリングの計算に最も多く用いられている反復改善法である.クラスタリングは,各クラスタが2-cell(円板)と同相で,任意の二つのクラスタの共通部分が空集合・一つの辺・一つの頂点のいずれかである場合,位相を保存すると言われる.三角形メッシュの頂点クラスタリングが位相を保存していれば,そのクラスタリングの双対分割はもとのメッシュと同相な三角形メッシュになる.メッシュ簡略化などの応用においては位相保存は非常に重要な問題であるが,Lloyd 法における位相保存の問題については今までほとんど研究されてこなかった.第5 章では,球面と同相なメッシュに対してはクラスタ数が4 以上であれば常に位相を保存するクラスタリングを計算できることを,また球面以外の曲面と同相なメッシュに対してはクラスタ数が大きくても位相を保存できないことがあることを明らかにした.境界を持つ球面と同相なメッシュに対しても同様の解析を行った.これらの解析を行うために,制限付き辺縮約という概念を定義した.本章では,位相を保存する最適クラスタリングを計算できるように,Lloyd 法の修正も行った.それから第6 章では,球面以外の曲面と同相なメッシュに対して,どのような場合に位相を保存するクラスタリングが存在するかという問題を考え,十分条件を導出することに成功した.この条件の導出には,三角形メッシュ上での離散ボロノイ図を利用した.

このように本論文では,表面メッシュ上での最適クラスタリングのための効率的な初期化法・Out-of-Core計算法・位相を保存する計算法を提案した.これらが主要な成果である.最後の第7 章で,以上の成果をまとめ今後の課題について述べている.

社会の情報化がますます加速する中で,コンピュータグラフィクスにおいても,高品質な形状の表現技術およびその利用技術がいっそう求められている.特に,立体の表面三角形メッシュによる表現法は,その簡便性・柔軟性のゆえに,コンピュータグラフィクスのための立体表現法として最も広く用いられているが,扱うデータの大規模化に伴って,解決すべき新しい技術課題も山積している.中でもメッシュの頂点のクラスタリングによる領域分割は,メッシュ簡略化,形状解析,テクスチャーマッピングなどさまざまな応用をもつ基本技術で,その品質の改善が望まれている.

本論文は,このような背景のもとで,三角形メッシュで表現された立体表面の領域分割とその応用に焦点を当てたもので,「Optimal Clustering on Surface Meshes and Its Topology Preservation(表面メッシュ上でのクラスタリングとその位相保存)」と題して7章から成る.

第1章「Introduction(序章)」では,三角形メッシュ上でのクラスタリングの歴史や理論を概観し,本論文の主要成果と構成を明らかにしている.

第2章「Preliminaries(準備)」では,基本概念の定義,記号法,性質などをまとめ,次章以降の準備としている.

第3章は「Initialization Methods(初期化法)」と題し,良質なクラスタリングを求めるための効率的な初期化法を提案している.最良のクラスタリングを求める問題はNP困難に属すため,初期クラスタリングに反復改善法を適用して準最適なクラスタリングを求めることが実用上大切である.したがって,良質のクラスタリングを短い収束時間で求めるためには,初期クラスタリングの選び方が重要である.本章では領域融合法を利用した初期化法を提案し,初期化法として従来から利用されているランダムサンプリングや最遠点サンプリングよりも効率的な初期化法であることを実験により示した.また,この方法は位相を保存するクラスタリングの計算を行うことができるという利点も持っている.

第4章「Out-of-Core Algorithm(大規模メッシュに対する省メモリアルゴリズム)」では,メモリに収まらないほどの大規模なメッシュに対してのクラスタリング計算法を提案している.近年では,3次元形状測定装置の性能向上により非常に詳細なメッシュが得られるようになっており,メモリに収まらないほどの大規模なメッシュも存在する.既存の最適クラスタリングの計算法は,メッシュが全てメモリに収まることを仮定しており,それより大きなメッシュを処理できない.本章では,データの一部のみをメモリに載せて準最適クラスタリングを計算するOut-of-Core法を提案している.これは初期化と反復改善により構成される.初期化法としては,ストリーム処理を利用したOut-of-Core辺縮約簡略化法をもとに領域融合を行うものである.一方,反復改善法としては,局所的な情報のみによって実現できるOut-of-Coreデータ交換法を提案している.これにより,大規模メッシュに対しても準最適クラスタリングが計算できるようになった.

第5章「Topology-Preserving Region Growing(位相保存領域成長法)」では,クラスタリングの反復改善法であるLloyd法の位相保存性を理論的に明らかにしている.Lloyd法は,準最適なクラスタリングを求めるための反復法として最もよく用いられているものであるが,この方法では曲面の位相構造が保存されるとは限らず,どのような場合に位相が保存されるものかもほとんど明らかとなっていなかった.本章では,Lloyd法の手続きを制限つき辺縮約という概念で整理し,球面と同相なメッシュに対しては,クラスタ数が4以上であれば常に位相を保存するクラスタリングがあり,それを求める計算法も存在することを証明した.さらに,球面以外の曲面と同相なメッシュに対しては,どれほどクラスタ数が大きくても位相を保存するメッシュの変更では,目的のクラスタ数のクラスタリングに到達できない場合があることも示した.

第6章「Existence of Topology-Preserving Clustering(位相保存クラスタリングの存在)」では,球と同相ではない曲面のメッシュに対して,位相を保存するクラスタリングが存在するための十分条件を導出することに成功している.この条件は,三角形メッシュ上の離散ボロノイ図を手がかりとして,クラスタの種となる頂点集合が満たすべき性質を明らかにしたものである.これは,曲面上のドロネー三角形分割がもとの曲面と同相になるためのサンプリング条件の離散曲面(三角形メッシュ)版とみなすことができる.これによって,位相を保存するクラスタリングを得るための種頂点の特徴づけが初めて可能となった.

第7章「Conclusions(結論)」では,以上の成果をまとめるとともに,今後に残された主要な課題を整理している.

以上を要するに,本論文は,立体の表面メッシュ上での最適クラスタリングを近似的に求めるための効率的な初期化法,Out-of-Core計算法という実用的手法を提案すると同時に,それが曲面の位相を保存するための条件を明らかにして,性能を理論的に保証することに成功したものであり,数理情報学へ大きく貢献するものである.

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