1. 研究背景

コンピュータグラフィックスやリバースエンジニアリングなどの分野では,物体の形状をデザインする際,一からデザインするよりも,既に存在する物体の形状を基にデザインした方が効率が良いことがある.実在する物体の形状をコンピュータに取り込むには,3次元スキャナを用いるのが一般的である.スキャンデータは表面データとボリュームデータの2種類に大きく分類される.表面データは物体表面の形状のみ必要な場合に用いられ,レーザースキャンなどで物体表面からサンプリングした点の集合からなるものが多い(図1中央).ボリュームデータは物体の形状と内部構造を表現可能で,MRIやCTスキャンにより得られる(図1右).ボリュームデータは空間内の格子点集合からなり,各点には輝度値が与えられている.これらのスキャンデータ(点群)は,より汎用な形状表現であるメッシュ(微小な多角形・多面体の集合(それぞれ表面メッシュ・ボリュームメッシュという),図2)に変換されることが多い.スキャンデータにはノイズや異常値(計測誤差により表面から外れた位置に生じたデータ点),欠損が含まれるのが常であり,程度によっては後の工程で問題が生じることがある(図3).

近年,新たな形状表現として,球被覆関数を用いる手法が提案された[OBA+03].この手法はメッシュに比べ複雑な形状や滑らかな表面をよく再現できるため,注目を集めている.また,メッシュではCSGやブレンディングといった形状操作は困難であったが,これらを容易に行えるため,形状デザインにも適している.多少ノイズを含むスキャンデータからも元の形状を再現できるという優れた特長もある.メッシュへの変換も容易である.また,表面データとボリュームデータは従来異なるデータ構造で扱われてきたが,球被覆関数はこれらを統一的に扱える.

球被覆関数による形状表現では,まず表面[またはボリューム]点群を含む空間を関数付きの球(この球が関数のサポートとなるので,サポート球と呼ぶ)の集合で被覆する(球被覆を生成,図4(a),(b),図5(a)-(c)).各サポート球の関数は球内部の点に対し表面からの符号付き距離[輝度値]を近似するよう定める.これらの局所近似関数の重み付き平均(球被覆関数)が,被覆された空間内の任意の点に対し表面からの符号付き距離[輝度値]を近似する関数となる(図4(c),図5(d)).表面点群に対し本研究では,近似関数の符号は物体内部で正,外部で負となるよう定める.

2. 研究の目的と成果

本論文の主な研究成果は以下の3点である.

●球被覆関数固有の離散微分演算子の導出

●ノイズ・異常値耐性のある表面再構成アルゴリズムの構築

●ノイズ耐性のあるスケルトン構造抽出アルゴリズムの構築

以下,各成果について説明する.

2-1. 球被覆関数固有の離散微分演算子の導出

微分演算は形状の操作や解析に欠かせない演算の一つである.コンピュータ上では微分値は離散的な近似計算で求める.良い計算結果を得るには,対象とするデータ構造に特化した離散化を行うことが重要である.近年,メッシュに対する離散微分演算子 [DMSB99, TLHD03]が提案されたが,球被覆関数に固有のものはまだなかった.そこで本研究では球被覆上の離散微分演算子として,勾配,発散,ラプラシアンを導出・定義した.球被覆関数の局所近似関数の次数は1次式と仮定し,ガウスの発散定理に基づいて演算子を導出した.

2-2. ノイズ・異常値耐性のある表面再構成アルゴリズムの構築

表面点群の幾何処理の一つに,点群から物体の表面を表す表面メッシュを生成する表面再構成がある.本研究では,球被覆関数を用いることで,ノイズや異常値に耐性のあるアルゴリズムを構築した.

表面再構成は古くから研究されており,多くの手法が提案されている.それらはVoronoi図やその関連構造を用いる陽的手法[ACK01]と,近似関数を用いて空間を物体の内部と外部に分割し,近似関数の等値面で形状を近似する陰的手法とに分類される.陽的手法は直感的であるがノイズに弱く,スキャンデータを処理するには不向きである.陰的手法をさらに分類すると,球被覆関数のように局所的な処理を行うものと大域的処理を行うものに分けられる.大域的陰的手法[KBH06]はノイズへの耐性が非常に高いが,複雑な形状の表現は一般に困難である.一方,局所的陰的手法[OBA+03]はノイズ耐性があり,複雑な形状も表現できる.局所性のおかげで計算が非常に高速で,大規模データも処理できる.こういった長所がある反面,スキャンデータに大きな欠損や多量のノイズ,異常値が存在するとその影響を受けやすいという短所もある(図3).そこで,それらを含む低品質なスキャンデータも処理可能な表面再構成法として,欠損・異常値対策にはグラフカットを用いるアルゴリズムを,ノイズ対策には局所関数のスムーシングを用いるアルゴリズムを提案した.

○ グラフカットの利用

欠損・異常値の問題が局所性に起因することに着目し,大域的手法であるグラフカットを用いた内外判定を提案する.陰関数による表面再構成では,球被覆関数の符号によって空間を物体の内部と外部に分割している.図6左は異常値なしの点群(a)から表面再構成を行った結果である.球被覆関数による表面再構成では,値0の等値面(黒線)が近似表面となる(b).一方,点群に異常値が含まれる場合(c),球被覆関数の近似が失敗することがあり(d),符号による内外判定では失敗箇所の周囲に不要な面が生じる.そこで符号による判定に替わる新たな内外判定として,球被覆関数の値を基にした重み付きグラフのグラフカットを用いる(e).空間中の点をノードとするグラフを,球被覆に基づく重み付きドロネー四面体分割[Ede93] などで生成し,グラフカットを行うと,各ノードの内外が定まる.

異常値を含む3次元の表面点群に対する結果を図7に示す.大域的判定を用いているので,不要な面のない表面が得られている.また,欠損を含む表面点群に対しても,穴のない望ましい形状の表面メッシュが得られた(図8).

○ 局所近似関数のスムーシング

局所近似関数は互いに独立に生成されるため,表面点群に多量のノイズが存在すると(図9(a)),局所近似関数同士の等値面が互いに全く異なる球被覆(図9 (b)上段)が生成されることがある.その結果近似表面には微小な凹凸や不要な面が多数出現する(図9(b)下段).この問題に対し,局所近似関数をスムーシングして滑らかな等値面をもつ球被覆関数を得て,ノイズの影響のない近似表面を生成した(図9(c)).スムーシングには球被覆関数固有の離散微分演算子を用いた.

スムーシング技術は既に深く研究されているが,その多くがメッシュやボリュームデータを対象とし,頂点位置や法線ベクトルの方向を変更するというものであった.これらを陰関数による表面再構成に用いるには近似表面を一度ポリゴン化する必要がある.この時,ノイズの影響で生じた不要な表面も一緒にポリゴン化されるが,既存のスムーシングではこの不要な面を消すことはできない.提案手法ではポリゴン化せずに局所近似関数自身をスムーシングするため,不要な面が生じにくい球被覆関数が得られる.

2-3. ノイズ耐性のあるスケルトン構造抽出アルゴリズムの構築

スケルトン構造は物体の骨格を表す形状の総称で,元の物体の直観的形状を把握するのに役立ち,品質評価や物理シミュレーションに用いられる.本論文ではリバースエンジニアリングで多く扱われる板状の物体(薄板)のボリュームデータから,面状のスケルトン構造を近似する表面メッシュの生成法を提案する(図10).

提案手法は,薄板のスケルトン構造と輝度値の極大点集合とが非常に近い形状であることに着目している.図11に薄板の物体(a)とそのCT画像の一断面(b)を示す. (b)の青線における物体の密度のグラフ(c)と輝度値のグラフ(d)を見ると,スケルトン構造部分と極大点の位置がほぼ一致することが分かる.提案手法では輝度値を近似する球被覆関数を生成し,その極大点を検出・ポリゴン化してスケルトン構造を得る(図12).

球被覆関数値を用いることで,CTデータの輝度値を直接使わずに済み,また微分値も解析的に計算できる.その結果CTデータに含まれるノイズの影響が緩和され滑らかなスケルトン構造が得られる.このスケルトン構造は図10(c)に示すように,物体と同位相(穴が開かず,縁に枝分かれがない)で縁まで伸びるという特長をもつ.スケルトン構造を極大点検出とポリゴン化には球被覆に基づく四面体メッシュを用いる.サポート球の大きさは物体の形状の複雑さに応じて適応的に変化するため,スケルトン構造の近似メッシュも適応的なものが得られる.

図1 スキャンデータの取得例.

左: 素焼きのウサギの像.中央: 表面点群.右: CTスキャンデータ(水平方向の一断面).

図2 メッシュ.

左: 表面メッシュ.中央・右: ボリュームメッシュおよびその断面.

図3 ノイズの影響でメッシュの生成に失敗した例.

左:ノイズを含む表面点群.右:左の点群から生成した表面メッシュ.

図4 2次元の表面点群から球被覆関数で元の形状を再現した例.

(a) 表面点群.(b) 円被覆(青点は円の中心).(c) 球被覆関数のスカラー場(値が小:黒,大:赤で示す).黒線は元の形状の表面を近似する曲線.

図5 CTデータから球被覆関数を生成した例.

(a) 工業製品.(b) (a)のCTデータ(異なる3方向からの断面).(c)球被覆.(d) 球被覆関数のスカラー場(値が小:青,大:赤で示す).

図6 異常値が表面再構成に及ぼす影響.(a) 異常値なしの表面点群.(b) (a)から得た球被覆関数のスカラー場(関数値が小:青,大:赤で表示).黒線が近似表面.(c) 異常値を含む表面点群.(d) (c)から生成した球被覆関数のスカラー場.符号はその点における球被覆関数値の符号.青丸・黄色の四角はそれぞれその点が外部・内部と判定されたことを示す.(e) グラフカットによる内外判定で得た近似表面.

図7 異常値を含む3次元表面点群からの表面再構成.左:表面点群.中央: 球被覆関数の符号による内外判定で得た表面.右: グラフカットによる内外判定で得た表面.

図8 欠損を含む3次元表面点群からの表面再構成.左: 点群の欠損部分.中央: 生成された表面メッシュの,左図に対応する箇所.右: 生成された表面メッシュの全体.

図9 ノイズを含む表面点群からの表面再構成.(a) 表面点群.(b) (a)から生成された球被覆関数の等値面の模式図(上段)と近似表面(下段).上段の黒点は点群,破線は局所近似関数の等値面,実線は球被覆関数の等値面を表す.(c) 局所近似関数スムーシング後の被覆関数の等値面の模式図と近似表面.

図10 スケルトン構造抽出.(a) 金属製の薄板の工業製品.(b) (a)のCTデータ(異なる3方向からの断面図).(c) CTデータの等値面(ピンク)と抽出したスケルトン構造(青).等値面の断面の色は,輝度値の近似値を示す(青: 小,赤: 大).

図11 輝度値の極大点集合でスケルトン構造を近似する.(a) 薄板.(b) (a)のCT画像の一断面.(c) (b)の青線における物体の密度のグラフ.赤線はスケルトン構造の位置を示す.(d) (b)の青線における輝度値のグラフ.赤線は極大点の位置を示す.

図12 画像からスケルトン構造を抽出した例.(a) グレイスケール画像.(b) (a)の物体部分に対する円被覆.(c) (b)から得た三角形メッシュ.(d)スケルトン構造(青線).

長井超慧(ながいゆきえ)提出の本論文は「Processing of Scanned GeometryUsing Spherically Supported Functions(球被覆関数によるスキャン形状処理)」と題し,全7章よりなり,実物体をスキャンすることによって取得した形状を球被覆関数を用いて処理するための問題を扱っている.

第1章では,まず研究の背景を説明し,次に研究の目的および達成した目標について述べ,最後に論文の構成を述べている.球被覆関数はコンピュータ上で形状データを統一的に表現可能で形状処理に適した形状表現である.実物体はスキャンによってその形状を取得することができるが,取得した形状データにはノイズや異常値が含まれ,正しい球被覆関数を生成することができない.そこで本論文では,スキャンデータを対象に,ノイズ・異常値耐性のある球被覆関数生成と,球被覆関数を用いた形状処理について研究を行っている.スキャンデータは表面データとボリュームデータの2種類があり,形状処理として,表面データから表面メッシュを生成する「表面再構成」およびボリュームデータから物体の面状骨格構造を得る「スケルトン構造抽出」の2種類の問題を扱った.

第2章では,まず本論文において扱う球被覆関数以外の形状表現である,測定点群とメッシュを紹介している.次いでデータ構造固有の微分演算子導出に関する既存の研究について紹介している.その後,表面再構成,スムーシング,スケルトン構造抽出に関して,既存の手法を特徴と問題点を挙げながら概説している.なお,スムーシングはノイズ対策として最も一般的な手法である.

第3章では,球被覆関数のデータ構造とその生成手法,そこから得られる副次的構造であるメッシュの生成手法について述べている.まず,球被覆関数が,形状データを被覆する関数付き球(サポート球)集合で実現されることを説明する.次に表面データとボリュームデータそれぞれについて,球被覆の最小単位であるサポート球の生成について述べ,それをふまえて球被覆の生成法を述べている.生成された球被覆の球同士に隣接関係を定めることで,球被覆と同じ次元の単体メッシュを生成することができ,その具体的な手法を本章の最後で紹介している.

第4章では球被覆関数固有の微分演算子の必要性について述べ,導出を行い,実際にコンピュータ上で用いるための式を示している.形状処理を行う際に用いるデータ構造に特化した微分演算子を用いることが望ましいが,球被覆関数には固有の微分演算子が今までなかったという背景についてまず述べている.次いで発散定理を用いてサポート球単位で離散化したgradient , divergence,Laplacianを導出し,実際に計算で用いる式を示している.

第5章では,異常値やノイズを含む表面データに対しても球被覆関数を用いて頑健に表面再構成を行う手法を提案し,様々なスキャンデータに適用することでその有効性を示している.球被覆関数を用いた表面再構成では,被覆領域を物体の内部と外部に分割し,その境界で物体表面を表現する.提案手法もその流れに則っている.本章ではまず,球被覆関数による既存の手法ではスキャンデータを処理する際に内外分割に失敗することを紹介する.異常値とノイズは異なる特徴をもつ外乱因子であり,異なる対策が必要であることを指摘している.それをふまえ,異常値は局所的外乱であることに着目し,大域的手法であるGraph-cutを用いて異常値の影響を受けたサポート球を選別することを提案している.また,データ点に対する異常値らしさの指標を球被覆関数とGraph-cutを用いて考案し,指標の有効性も示している.次いでノイズの影響を緩和するために,サポート球の関数に対するスムーシングを提案している.このスムーシングでは,第4章で導出した離散Laplacianを用いて勾配ベクトル場のラプラシアンスムーシングを行い,その結果をスカラー場に反映するために,離散divergenceを用いたポアソン方程式を解いている.

第6章では,薄い板状の物体をスキャンして得たボリュームデータから,その物体の面状のスケルトン構造を得るための手法を提案し,実験によって手法の有効性を示している.提案手法は厚みが薄い物体の場合はスケルトン構造とボリュームデータの輝度値の極大点集合がほぼ一致するという観察に基づいている.スキャンデータに含まれるノイズの影響を緩和するために,輝度値を球被覆関数で近似した値を用いることを提案している.

第7章では結論と今後期待される展開について述べている.本論文で提案する手法により,球被覆関数を用いてスキャンデータを処理することが可能になったこと,球被覆関数を用いたよりよい形状表現および形状処理のために今後行うべき研究の方向性を述べている.

以上を要約するに,本研究により,球被覆関数によってスキャン形状を表現および処理するための複数の手法が提案され,その有効性が確認された.また,残された課題についても問題点が明らかにされ,球被覆関数を用いた形状表現および処理手法に関して大きな貢献をしたといえる.このことにより,コンピュータグラフィックスやエンジニアリングの発展に寄与するところが大である.

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