(57)【要約】【課題】図形の欠損部分を周囲のデータから補完することができる３次元図形の曲面再構成方法および３次元図形の曲面再構成プログラムを提供すること。【解決手段】本発明の３次元図形の曲面再構成方法は、３次元空間において、ベクトルｐで表される所定のサンプル点１１から物体表面１０への符号付距離および最近点１２への法線により構成される、法線情報付符号付距離場が離散的にサンプルされたデータを入力する入力工程と、前記ベクトルｐで表されるサンプル点１０からベクトルΔｐｉだけずれたｉ番目のサンプル点近傍の法線ベクトルｎｉと符号付距離のサンプル値ｓｉに、所定の法線ベクトルｎ、符号付距離ｓおよび対称行列Ｍの成分で表される法線情報付符号付距離場の局所２次近似を行う近似工程と、を含むことを特徴とする。【選択図】        図５
2006039622.tif 000002
【特許請求の範囲】
【請求項１】
３次元空間において、ベクトルｐで表される所定のサンプル点から方向つき曲面である形状表面への符号付距離および最も近い点への法線により構成される、法線情報付符号付距離場が離散的にサンプルされたデータを入力する入力工程と、
前記ベクトルｐで表されるサンプル点からベクトルΔｐｉだけずれたｉ番目の近傍のサンプル点の法線ベクトルｎｉと符号付距離のサンプル値ｓｉに、所定の法線ベクトルｎ、符号付距離ｓおよび対称行列Ｍの成分で表される法線情報付符号付距離場の局所２次近似を行う近似工程と、
を含むことを特徴とする３次元図形の曲面再構成方法。
【請求項２】
前記近似工程は、ｉ番目の近傍の符号付距離の重み係数をｗｉ、法線成分の重み係数をｗｎｉとして、次の線形連立方程式の最小二乗解を求めることにより局所２次近似を行うことを特徴とする３次元図形の曲面再構成方法。
【数１】
2006039622.tif 000046
【請求項３】
前記サンプルされたデータは、３次元空間における図形のデータであり、前記近似工程は、前記局所２次近似を当てはめることにより、前記３次元空間における図形のデータの補完データを作成し、該補完データを用いて前記３次元空間における図形の描画を行うことを特徴とする請求項１または２に記載の３次元図形の曲面再構成方法。
【請求項４】
３次元空間において、ベクトルｐで表される所定のサンプル点から方向つき曲面である形状表面への符号付距離および最も近い点への法線により構成される、法線情報付符号付距離場が離散的にサンプルされたデータを入力させる入力工程と、
前記ベクトルｐで表されるサンプル点からベクトルΔｐｉだけずれたｉ番目の近傍のサンプル点の法線ベクトルｎｉと符号付距離のサンプル値ｓｉに、所定の法線ベクトルｎ、符号付距離ｓおよび対称行列Ｍの成分で表される法線情報付符号付距離場の局所２次近似を行う近似工程と、
をコンピュータに実行させることを特徴とする３次元図形の曲面再構成プログラム。
【請求項５】
前記近似工程は、ｉ番目の近傍の符号付距離の重み係数をｗｉ、法線成分の重み係数をｗｎｉとして、次の線形連立方程式の最小二乗解を求めることにより局所２次近似を行うことを特徴とする請求項４に記載の３次元図形の曲面再構成プログラム。
【数２】
2006039622.tif 000047
【請求項６】
前記サンプルされたデータは、３次元空間における図形のデータであり、前記近似工程は、前記局所２次近似を当てはめることにより、前記３次元空間における図形のデータの補完データを作成し、該補完データを用いて前記３次元空間における図形の描画を行うことを特徴とする請求項４または５に記載の３次元図形の曲面再構成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、形状モデルの欠損部分の補完を行う３次元図形の曲面再構成方法および３次元図形の曲面再構成プログラムに関する。
【背景技術】
【０００２】
近年、コンピュータ・デバイス・センサの性能・小型化・低価格化の向上により、様々な物体形状の計測手段が提案されている。光学的計測手法には、受光センサのみ使用する受動的手法と、光などを投射してその応答を利用する能動的手法がある。
【０００３】
グラフ曲面として記述できるようないわゆる２．５次元データの欠損を補完する一般的枠組みとしては、正則化によるエネルギー最小化がある。データへの当てはめと連続性をエネルギー関数の形で表し、両立の拘束がバランスをとって満たされるようにエネルギー関数を最小化することにより、連続したもっともらしい面を生成することができる。コンピュータビジョンでは、この枠組みの中で、ステレオなどによって得られた疎な形状を補完する手法が多く提案された（例えば、下記非特許文献１〜３参照。）。
【０００４】
物体表面からの符号付距離をスカラ場として離散的に標本化した符号付距離場（ＳＤＦ：Ｓｉｇｎｅｄ  Ｄｉｓｔａｎｃｅ  Ｆｉｅｌｄ）によって形状を記述する手法が提案されている。符号付距離場からは、距離０の等値面として滑らかな表面を再構成することができるので、複数の形状計測データの平均として全体形状モデルに統合する手法が多く提案されている（例えば、下記非特許文献４〜６参照。）。
【０００５】
また、距離データの統合だけでなく、誤計測点の判定や、複数の距離データの同時位置合わせに、ＳＤＦが利用できることが示されている（例えば、下記非特許文献７参照。）。この手法では、何らかの方法でデータ形状が事前にある程度大まかに位置合わせされていることを仮定し、外れ値処理を伴うロバストな形状統合処理と、統合形状への位置合わせを、交互に繰り返すことにより、重ねてみないと分からないような微妙な誤計測点やデータ欠損部を判定しながら、ＳＤＦによって記述された統合形状モデルを自動的に生成することができる。ＳＤＦにより記述された統合形状からは、簡単な処理でポリゴンによる形状記述を再構成することができる。
【０００６】
複数の距離画像の統合手法として、ボクセルにｏｂｊｅｃｔ（内部）、ｓｕｒｆａｃｅ（表面）、ｓｐａｃｅ（外部）の３種のラベルを付ける手法が提案されている（例えば、下記非特許文献８参照。）。この手法では、表面を挟まずに内部と外部が接している部分として未計測部分を判定することができる。この手法を適用するには、対象物とセンサの位置関係だけでなく、光学的な特性が既知である必要がある。ボクセルによる形状記述は滑らかでないため、ＳＤＦを経由した曲面復元が提案され、同様の方法でボクセルをｅｍｐｔｙ（外部）、ｎｅａｒ  ｓｕｒｆａｃｅ（表面）、ｕｎｓｅｅｎ（内部）と分類することにより欠損部分を簡易に埋めることができることが示されている（例えば、下記非特許文献５参照。）。
【０００７】
粗やノイズの多い距離データから平滑な形状モデルの再構成を行うために、ｌｅｖｅｌ−ｓｅｔ  ｍｅｔｈｏｄを利用する手法が提案された（例えば、下記非特許文献９参照。）。ｌｅｖｅｌ−ｓｅｔ  ｍｅｔｈｏｄは、界面の空間中の伝搬を微分方程式で記述したもので、時間微分の項を利用して場の更新規則を作ることができ、曲率に依存した伝搬速度を設定することで、場の平滑化などを行うことができる。ｌｅｖｅｌ−ｓｅｔ  ｍｅｔｈｏｄを応用して、符号付距離場での面の滑らかな補完（例えば、下記非特許文献１０参照。）や、複数距離データ統合時に生じる不整合の解決（例えば、下記非特許文献１１参照。）が行われた。
【０００８】
ｌｅｖｅｌ−ｓｅｔ  ｍｅｔｈｏｄは、ｌｅｖｅｌ−ｓｅｔの伝搬速度として曲率依存の値を設定することが一般的なため、生成される場の勾配の大きさがＳＤＦのように一定になるとは限らない。また、ＳＤＦの法線情報を利用することにより、曲面の曲率を求めることができる（例えば、下記非特許文献１２参照。）。
【０００９】
【非特許文献１】Ｗ．Ｅ．Ｌ．Ｇｒｉｍｓｏｎ、“Ａｎ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ａ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ｔｈｅｏｒｙ  ｏｆ  ｖｉｓｕａｌ  ｓｕｒｆａｃｅ  ｉｎｔｅｒｐｏｌａｔｉｏｎ”、“Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，Ｇｒａｐｈｉｃｓ，ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ”、２２号、１９８３年、ｐ．３９−６９
【非特許文献２】Ｄ．Ｔｅｒｚｏｐｏｕｌｏｓ、“Ｔｈｅ  ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｖｉｓｉｂｌｅ−ｓｕｒｆａｃｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ”、ＩＥＥＥ  Ｔｒａｎｓ．ＰＡＭＩ、１９８８年、第１０巻、第４号、ｐ．４１７−４３８
【非特許文献３】Ｒ．Ｓｚｅｌｉｓｋｉ、“Ｆａｓｔ  ｓｕｒｆａｃｅ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｕｓｉｎｇ  ｈｉｅｒａｒｃｈｉｃａｌ  ｂａｓｉｓ  ｆｕｎｃｔｉｏｎｓ”、ＩＥＥＥ  Ｔｒａｎｓ．ＰＡＭＩ、１９９０年、第１２巻、第６号、ｐ．５１３−５２８
【非特許文献４】Ａ．Ｈｉｌｔｏｎ，Ａ．Ｊ．Ｓｔｏｄｄａｒｔ，Ｊ．Ｉｌｌｉｎｇｗｏｒｔｈ  ａｎｄ  Ｔ．Ｗｉｎｄｅａｔｔ、“Ｒｅｌｉａｂｌｅ  ｓｕｒｆａｃｅ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｆｒｏｍ  ｍｕｌｔｉｐｌｅ  ｒａｎｇｅ  ｉｍａｇｅｓ”、Ｐｒｏｃ．ＥＣＣＶ９６、１９９６年、ｐ．１１７−１２６
【非特許文献５】Ｂ．Ｃｕｒｌｅｓｓ  ａｎｄ  Ｍ．Ｌｅｖｏｙ、“Ａ  ｖｏｌｕｍｅｔｒｉｃ  ｍｅｔｈｏｄ  ｆｏｒ  ｂｕｉｌｄｉｎｇ  ｃｏｍｐｌｅｘ  ｍｏｄｅｌｓ  ｆｒｏｍ  ｒａｎｇｅ  ｉｍａｇｅｓ”，Ｐｒｏｃ．ＳＩＧＧＲＡＰＨ９６、１９９６年、ｐ．３０３−３１２
【非特許文献６】Ｍ．Ｄ．Ｗｈｅｅｌｅｒ，Ｙ．Ｓａｔｏ  ａｎｄ  Ｋ．Ｉｋｅｕｃｈｉ、“Ｃｏｎｓｅｎｓｕｓ  ｓｕｒｆａｃｅｓ  ｆｏｒ  ｍｏｄｅｌｉｎｇ  ３Ｄ  ｏｂｊｅｃｔｓ  ｆｒｏｍ  ｍｕｌｔｉｐｌｅ  ｒａｎｇｅ  ｉｍａｇｅｓ”、Ｐｒｏｃ．ＩＣＣＶ９７、１９９７年、ｐ．９１７−９２４
【非特許文献７】増田健著、「符号付距離場の一致による複数距離画像からの形状モデル生成」、情報処理学会論文誌：コンピュータビジョンとイメージメディア、２００３年、ｐ．３０−４０
【非特許文献８】Ｙ．Ｓａｋａｇｕｃｈｉ，Ｈ．Ｋａｔｏ，Ｋ．Ｓａｔｏ  ａｎｄ  Ｓ．Ｉｎｏｋｕｃｈｉ、“Ａｃｑｕｉｓｉｔｉｏｎ  ｏｆ  ｅｎｔｉｒｅ  ｓｕｒｆａｃｅ  ｄａｔａ  ｂａｓｅｄ  ｏｎ  ｆｕｓｉｏｎ  ｏｆ  ｒａｎｇｅ  ｄａｔａ”、Ｔｒａｎｓ．ＩＥＩＣＥ、Ｅ−７４、第１０号、１９９１年、ｐ．３４１７−３４２２
【非特許文献９】Ｒ．Ｔ．Ｗｈｉｔａｋｅｒ、“Ａ  ｌｅｖｅｌ−ｓｅｔ  ａｐｐｒｏａｃｈ  ｔｏ  ３ｄ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｆｒｏｍ  ｒａｎｇｅ  ｄａｔａ”，“Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ”、第２９巻、第３号、１９９８年、ｐ．２０３−２３１
【非特許文献１０】Ｊ．Ｄａｖｉｓ，Ｓ．Ｒ．Ｍａｒｓｃｈｎｅｒ，Ｍ．Ｇａｒｒ  ａｎｄ  Ｍ．Ｌｅｖｏｙ、“Ｆｉｌｌｉｎｇ  ｈｏｌｅｓ  ｉｎ  ｃｏｍｐｌｅｘ  ｓｕｒｆａｃｅｓ  ｕｓｉｎｇ  ｖｏｌｕｍｅｔｒｉｃ  ｄｉｆｆｕｓｉｏｎ”、Ｐｒｏｃ．３ＤＰＶＴ２００２、２００２年、ｐ．４２８−４３７
【非特許文献１１】Ｒ．Ｓａｇａｗａ  ａｎｄ  Ｋ．Ｉｋｅｕｃｈｉ、“Ｔａｋｉｎｇ  ｃｏｎｓｅｎｓｕｓ  ｏｆ  ｓｉｇｎｅｄ  ｄｉｓｔａｎｃｅ  ｆｉｅｌｄ  ｆｏｒ  ｃｏｍｐｌｅｍｅｎｔｉｎｇ  ｕｎｏｂｓｅｒｖａｂｌｅ  ｓｕｒｆａｃｅ”、Ｐｒｏｃ．３ＤＩＭ２００３、２００３年、ｐ．４１０−４１７
【非特許文献１２】Ｔ．Ｍａｓｕｄａ、“Ｓｕｒｆａｃｅ  ｃｕｒｖａｔｕｒｅ  ｅｓｔｉｍａｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  ｓｉｇｎｅｄ  ｄｉｓｔａｎｃｅ  ｆｉｅｌｄ”、Ｐｒｏｃ．３ＤＩＭ２００３、２００３年、ｐ．３６１−３６８
【発明の開示】
【発明が解決しようとする課題】
【００１０】
センサには計測の原理や幾何的な配置から計測できる範囲が限定されており、一般に一度に対象物の全表面を計測することは難しい。例えば、表面が鏡面反射したり、黒い部分であったり、手前の部分に光路が遮られている場合には、投射した光の反射が戻って来ないので、能動的手法では計測できない。
【００１１】
テクスチャがない均一な面は受動的手法では計測できない。撮像センサの焦点距離やセンサ間の間隔によって、計測可能な空間的範囲は限定される。センサは自由な空間にしか設置することができず、物体の周囲に存在する地面・台・壁面・他の物体だけでなく、対象物自体にも視点を制限されてしまう。また、一度に撮影できるのは、物体の手前の面だけである。
【００１２】
このように視点の位置が制限されている場合には、単純な形状でも全面を計測するのに非常に多数の視点を要する場合がある。計測不可能であったり、計測するのに非常な労力を要したり、未計測のまま残されてしまったような欠損部分は、周囲のデータから補完することが実用上必要になる。
【００１３】
この発明は、上述した従来技術による問題点を解消するため、図形の欠損部分を周囲のデータから補完することができる３次元図形の曲面再構成方法および３次元図形の曲面再構成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上述した課題を解決し、目的を達成するため、この発明にかかる３次元図形の曲面再構成方法は、３次元空間において、ベクトルｐで表される所定のサンプル点から方向つき曲面である形状表面への符号付距離および最も近い点への法線により構成される、法線情報付符号付距離場が離散的にサンプルされたデータを入力し、前記ベクトルｐで表されるサンプル点からベクトルΔｐｉだけずれたｉ番目の近傍のサンプル点の法線ベクトルｎｉと符号付距離のサンプル値ｓｉに、所定の法線ベクトルｎ、符号付距離ｓおよび対称行列Ｍの成分で表される法線情報付符号付距離場の局所２次近似を行うことを特徴とする。
【００１５】
この発明によれば、複数方向から計測した距離データを統合して得られる形状データに未計測のまま残された領域を、後処理として補完することができる。形状表現として法線情報付の符号付距離場を用い、局所的な二次関数近似を繰り返し行うことにより欠損部分を推定することができ、二次関数を当てはめることにより、補完するだけでなく曲面の曲率を求めることができる。
【００１６】
また、この発明にかかる３次元図形の曲面再構成プログラムは、上述した３次元図形の曲面再構成方法を、コンピュータに実行させることを特徴とする。
【００１７】
この発明によれば、コンピュータを用いて上述した３次元図形の曲面再構成方法を実行できる。
【発明の効果】
【００１８】
本発明にかかる３次元図形の曲面再構成方法および３次元図形の曲面再構成プログラムによれば、ＳＤＦの逐次的な局所二次関数の当てはめによる形状モデルの欠損部分の補完を行うことができるので、当てはめる二次関数モデルと、曲面曲率との関係を明らかにし、符号付距離だけでなく法線の場も含めて整合性のとれた、曲率が滑らかな場の補完を行うことを図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１９】
以下に添付図面を参照して、この発明にかかる３次元図形の曲面再構成方法および３次元図形の曲面再構成プログラムの好適な実施の形態を詳細に説明する。まず、（符号付距離場）の説明でＳＤＦの概略を説明し、（符号付距離場と曲面曲率）の説明でＳＤＦと曲率の関係を説明し未計測部分の補完方法を導出する。（実験について）の説明で実験結果を示す。
【００２０】
（実施の形態）
（符号付距離場）
まず定義について説明する。図１は符号付距離場（ＳＤＦ）を記述するパラメータの概要を示す図である。物体表面１０を向き付の曲面Ｓとみなすとき、一般の位置にある３次元空間中の任意のベクトルｐで表されるサンプル点１１から最も近い曲面上の点である最近点１２は一意に決めることができる。例外は球の中心・円柱の軸・２平面からの等距離面のような、曲面上の複数の点から等距離にある点、一般的には表面のボロノイ境界上にある点である。サンプル点１１から物体表面１０に最も近い最近点１２を次の式（１）で表す。
【００２１】
【数１】
2006039622.tif 000003
曲面が微分可能であれば、最近点１２、ＣＰ［ｐ，Ｓ］での法線ＳＮ［ｐ，Ｓ］の向きはｐ（ベクトル値。以降ｐと表記される文字はスカラ値ではなくベクトル値である。）への方向と一致する。法線の長さは次の式（２）で表し、
【００２２】
【数２】
2006039622.tif 000004
物体の内から外へ向くようにとると、点ｐの符号付距離は次の（３）式で表されるスカラ場となり、
【００２３】
【数３】
2006039622.tif 000005
そして次の（４）式のようになるので、
【００２４】
【数４】
2006039622.tif 000006
その勾配は法線が成すベクトル場である。点ｐにおけるＳＤＦサンプルを次の（５）式で表す。
【００２５】
【数５】
2006039622.tif 000007
サンプル点１１の近傍の点ｘ（ベクトル値。以降座標以外の意味でをうをなくｊｘと表記される文字はスカラ値でなくベクトル値である。）での符号付距離は次の（６）式のように線形近似される。
【００２６】
【数６】
2006039622.tif 000008
以後、一つの対象形状について述べていて混同の恐れのない限り、ＣＰ［ｐ，Ｓ］，ＳＮ［ｐ，Ｓ］，ＳＤ［ｐ，Ｓ］をそれぞれｃ，ｎ，ｓ（いずれもベクトル値である。）と略記する。
【００２７】
次に、ＳＤＦ間の距離について説明する。サンプル点１１の近傍で二つのデータ形状ＡとＢのＳＤＦが与えられているときに、その間の距離を、点ｐの近傍内で線形近似したＳＤＦの差の二乗の積分で定義する（例えば、上記参考文献７参照。）。サンプル点１１の近傍内でＳＤＦが式（６）により線形近似されることを利用すると、ＳＤＦ間の距離は、次の（７）式のように表される。
【００２８】
【数７】
2006039622.tif 000009
ここでｗｎは近傍の形状と大きさによって決まるが、近傍を一辺の長さがδの立方体とした場合、ｗｎ＝δ２／１２になる。
【００２９】
次に、離散化について説明する。ＳＤＦは概念的には連続量であるが、計算を行うためには離散化を行わなくてはならない。対象曲面を包含できるような一辺の長さＷの立方体をサンプル領域としてとり、その端点を次の（８）式のようにする。
【００３０】
【数８】
2006039622.tif 000010
サンプル点１１はサンプル領域内で等間隔の格子点上にとり、レベルｌのサンプル間隔δはＷ＝２ｌδの関係を満たすようにとる。次の（９）式で整数座標を表すが、
【００３１】
【数９】
2006039622.tif 000011
この（９）式で指定されるサンプル点１１の座標を式（１０）でとる。
【００３２】
【数１０】
2006039622.tif 000012
【００３３】
図２−１は、格子上にとられたサンプル点１１において物体表面１０のＳＤＦをサンプリングする過程を示す２次元模式図である。図２−２は、サンプル点１１から最近点１２へのベクトルの概要を示す図である。最近点１２がデータ形状の端にある場合は無効なサンプルとしている。
【００３４】
全空間のＳＤＦサンプルは巨大な記憶容量を必要とするため、データ形状からの絶対値距離が閾値（実装ではＴ＝２δ）以内のものだけ保存している。また、最近点１２がデータの計測領域の端にある場合は法線ｎがサンプル点１１への向きと一致しないため有効なサンプルとしては採用していない。
【００３５】
次に、曲面再構成について説明する。ＳＤＦとして生成された統合形状から、汎用的な３角パッチによる形状表現に変換する手法としては、Ｍａｒｃｈｉｎｇ  Ｃｕｂｅ法が多く用いられているが、本手法ではＳＤＦに持たせている法線情報も有効に活用して曲面再構成を行う。図３−１〜３−４は、曲面再構成の過程を示す図である。サンプル点１１は次の（１１）式でとられている。
【００３６】
【数１１】
2006039622.tif 000013
【００３７】
従って、サンプル点１１を頂点とする立方体領域の中心点はｃｉ＝ｏ＋ｉδにある。それぞれの立方体領域について、頂点にあるサンプル点１１のＳＤＦを中心点に線形補外すると中心点での符号付距離を求めることができる。その平均値の符号により、立方体領域を物体の内外いずれに近似すべきかを判定することができる。
【００３８】
内外の立方体領域の境界は正方形の集合の多面体となるが（図３−１参照）、その構造を維持したまま、各頂点の座標値を、サンプル点１１に対応した最近点１２（ＣＰｐ）に置換することにより、滑らかな面が得られる（図３−２、３−３参照）。さらにサンプル点１１の法線情報ＳＮｐも追加すると、さらに滑らかに描画することができる（図３−４参照）。この手法はＳＤＦに含まれる法線情報も有効に利用しており、通常のＭａｒｃｈｉｎｇ  Ｃｕｂｅ法のように頂点座標の補間や接続の不定性の問題は起こらない（例えば、上記非特許文献４〜６参照。）。
【００３９】
（符号付距離場と曲面曲率）
まず曲面曲率について説明する。ＳＤＦの法線情報を利用すると、曲面の曲率を求めることができる（たとえば、非特許文献１２参照。）。図４はサンプル点１１の近傍のＳＤＦからの曲率の計算に用いられるパラメータの概要を示す図である。サンプル点１１における最近点１２と法線を、ｃとｎ（いずれもベクトル値。）とする。サンプル点１１がｐ＋Δｐに変化したときに最近点１２と法線がｃ＋Δｃとｎ＋Δｎに変化するとする。法線ｎの方向への射影行列を次の式（１２）とすると、
【００４０】
【数１２】
2006039622.tif 000014
変位の接平面成分は次の式（１３）のようになる。
【００４１】
【数１３】
2006039622.tif 000015
この変位の接平面成分の関係は、対称な行列Ｋを用いて次の式（１４）で表される。
【００４２】
【数１４】
2006039622.tif 000016
【００４３】
行列Ｋは対称であるので、６つの独立成分ｋ＝（ｋｘｘ，ｋｙｙ，ｋｚｚ，ｋｙｚ，ｋｚｘ，ｋｘｙ）があり、実データの各近傍サンプルについて次の式（１５）の方程式を立てることができる。
【００４４】
【数１５】
2006039622.tif 000017
【００４５】
方程式の数が変数より多いので、特異値分解を利用して対称行列Ｋの成分の最小自乗解を求めることができる。式（１５）を解いて推定された結果は実対称なので、次の式（１６）のように対角化できる。
【００４６】
【数１６】
2006039622.tif 000018
ここでΔは実数固有値κ１，κ２，κ３の対角行列である次の式（１７）は直交行列とする。
【００４７】
【数１７】
2006039622.tif 000019
変移ΔｎｃｉとΔｎｎｉは接平面成分なので、次の式（１８）を満たす固有ベクトルが存在する。
【００４８】
【数１８】
2006039622.tif 000020
対応する固有値κ３は不定値をとり得るのでκ３＝０とおくことができ、行列Ｋは階数２の対称行列で表される。行列Ｋは曲面上の面素とガウス面上の面素の対応関係を与えており、固有値κ１，κ２が主曲率、ｗ１，ｗ２が主方向となる。以上の計算は射影行列Ｐｎを掛ける事と等価であるので、曲率を表す行列Ｋの正規化された推定値は式（１９）により求められる。
【００４９】
【数１９】
2006039622.tif 000021
そして次の式（２０）の関係が成り立つ。
【００５０】
【数２０】
2006039622.tif 000022
【００５１】
ここで、｜｜・｜｜Ｆはフロベニウスノルムである。主方向が不要な場合はこの関係式を用いてＫの正規化された推定値の成分から直接主曲率を求めることができる。以上の計算方法は、ΔｎｃｉとΔｎｎｉの組さえあれば適用可能である。
【００５２】
次に平行曲面について説明する。図５は平行曲面上の面要素におけるパラメータの概要を示す図である。最近点１２の近傍での曲面上の面要素を次の式（２１）で表す。ここで、ｗ１とｗ２は主方向である。
【００５３】
【数２１】
2006039622.tif 000023
面要素上での点の変位に伴う法線の変化は、主曲率κ１とκ２を用いて次の式（２２）で表される。
【００５４】
【数２２】
2006039622.tif 000024
曲面上での変位に伴って、最近点１２から法線方向ｎに距離ｔ離れた点ｃｔ＝ｃ＋ｔｎについて生じる変化は次の式（２３）で表される。
【００５５】
【数２３】
2006039622.tif 000025
従って、曲面から距離ｔ離れた平行な曲面の面積要素は次の式（２４）で与えられる。
【００５６】
【数２４】
2006039622.tif 000026
法線の変化は共通なので、平行曲面上での曲率は式（２２）と（２３）での係数の比から、次の式（２５）で求められる。
【００５７】
【数２５】
2006039622.tif 000027
曲面上の単位面要素を挟む厚さ±Ｔの体積は、曲率半径がＴ以上である場合、次の式（２６）で与えられる。
【００５８】
【数２６】
2006039622.tif 000028
【００５９】
この計算結果は、曲面から一定幅内の空間内に均一な密度でサンプル点１１が分布しているときに、曲面上の最近点１２の面密度が、ガウス曲率に依存していることを示している。厚さをＴ＝２δとし、この計算の仮定上で最も曲がっている状態であるＫ＝±１／（２δ）２の場合、単位面積当りのサンプル点１１の個数が±１／３個変化する程度である。
【００６０】
次に二次近似による符号付距離場の補完について説明する。ここまで、サンプル点１１の近傍の点ｘでＳＤＦが線形補間できることを示し、サンプル点１１の近傍での最近点ＣＰ［ｘ，Ｓ］と法線ＳＮ［ｘ，Ｓ］の関係を線形近似することによって曲面の曲率を求めることができることを示した。欠損データの補完を行う場合、サンプル点１１ではＳＤＦの値が与えられておらず、周囲のＳＤＦから推定する必要がある。符号付距離場が局所的にサンプル点１１の変位Δｐｉについて次の式（２７）で表される二次式で近似できるとする。
【００６１】
【数２７】
2006039622.tif 000029
式（３）で表されるように、法線は符号付距離の勾配であるから、法線の変化は次の式（２８）のように近似できる。
【００６２】
【数２８】
2006039622.tif 000030
【００６３】
法線の場はスカラ場の勾配なので渦無しであり、Ｍは対称行列である必要がある。サンプル点１１についての二次近似パラメータＭ，ｎ，ｓをまとめてＱＳＤＦ（ｐ）と記述する。二次近似の係数ＱＳＤＦ（ｐ）について、実データに対して次の式（２９）を最小にするように当てはめを行う。
【００６４】
【数２９】
2006039622.tif 000031
【００６５】
ここで、ｄ２（・）は式（７）で与えられるＳＤＦ間の距離であり、ｗｉは各サンプルについての重み係数、ＳＤＦ［ｐｉ，Ｓ］は曲面Ｓについてのｐｉでのサンプル値、ＱＳＤＦ（ｐ）はｐに関して求められた局所二次近似モデルで推定したサンプル点１１の近傍でのＳＤＦ値である。
【００６６】
式（１５）と同様に、対称な行列Ｋの６つの独立成分・法線・符号付距離について、式（３０）の方程式を立てることができる。ここで、ｗｎｉ＝ｗｉｗｎである。左辺の行列を特異値分解して最小自乗解を求める。連立方程式の形にしてあるので、近傍が全て埋まっていない場合でも、非特許文献２のようにパターンを分類する必要がない。１０個の変数があるので、解くにはサンプル点１１を最低１０必要とする。
【００６７】
【数３０】
2006039622.tif 000032
式（１）から得られる次の式（３１）の関係について、
【００６８】
【数３１】
2006039622.tif 000033
両辺をｐで偏微分すると式（３２）のようになる。
【００６９】
【数３２】
2006039622.tif 000034
式（５）から次の式（３３）が求められ、
【００７０】
【数３３】
2006039622.tif 000035
式（１７）から次の式（３４）が求められ、
【００７１】
【数３４】
2006039622.tif 000036
また次の式（３５）の通りであるから、
【００７２】
【数３５】
2006039622.tif 000037
次の式（３６）のように表すことができる。
【００７３】
【数３６】
2006039622.tif 000038
式（７）の固有展開と式（１４）の平行曲面上の曲率を用いると、次の式（３７）のように表される。
【００７４】
【数３７】
2006039622.tif 000039
【００７５】
すなわちＭは階数２の対称行列で、その固有値は式（１４）で与えられる平行曲面上の曲率であり、符号付距離ｓを用いて曲面の曲率κ１，κ２を求めることができる。このようにして求めた曲面曲率を用いて重み係数を次の式（３８）で定めている。ただし、ｗ（Δｐｉ）は近傍のとりかたで決まる重みとする。
【００７６】
【数３８】
2006039622.tif 000040
式（３０）を解いて求めた係数を式（３９）のようにあらわす。
【００７７】
【数３９】
2006039622.tif 000041
以降、便宜上それぞれＭ（＾）、ｎ（＾）、ｓ（＾）という表記と併用する。これらの係数を上述の条件を満たすように正規化する。まず法線の大きさを次の式（４０）のように正規化する。
【００７８】
【数４０】
2006039622.tif 000042
次に二次形式の行列Ｍの固有ベクトルが法線と一致するように射影して式（４１）のようにする。
【００７９】
【数４１】
2006039622.tif 000043
最後に正規化した法線と二次形式を用いて符号付距離を調整して式（４２）のようにする。
【００８０】
【数４２】
2006039622.tif 000044
【００８１】
以上の計算により、中央のサンプル点１１でのＳＤＦのサンプルがなくても、近傍のＳＤＦからＱＳＤＦ（ｐ）を推定することができるため、ＳＤＦの欠損値の補完を行うことができる。空間の各位置で局所的に二次近似しようとしていることから、三次微分、すなわち曲率の変化が小さくなるような場が推定されていることになる。
【００８２】
式（３０）の左辺行列の一般逆行列を求めると、Ｍ，ｎ，ｓの係数は、右辺のデータｎｉ，ｓｉに対して３次元線形フィルタを掛けることによって得られることがわかる。すなわち、Ｍ（＾）の係数はｎｉに対する一次微分とｓｉに対する二次微分の和、ｎ（＾）はｎｉの平均とｓｉの一次微分の和、ｓ（＾）はｎｉの線形補外とｓｉの平滑化の和として求められる。正規化の影響をとりあえず考慮しなければ、データｎｉ，ｄｉの誤差がＱＳＤＦの推定値に及ぼす影響はその線形結合の程度である。
【００８３】
（実験について）
次に、ＳＤＦを用いて未計測部分の補完を行うアルゴリズムを提案する。光造形などの現場では、既に対話的な３次元形状編集ツールが使用されており、平面で埋めたり一定の厚みで表面を残すような操作は量が少なければあまり困難ではないため、今回対象とするのは、曲面として欠損している部分とする。
【００８４】
ＳＤＦを用いて行った誤計測点除去、統合、位置合わせによれば、スカラ場の符号付距離だけでなく、その勾配のベクトル場である法線も用いることで、局所線形近似していた。本実施の形態の手法では微分連続性も保つように補完を行うために、二次近似を利用する。二次近似を求めることにより、曲面曲率といった微分幾何学的特徴量も得られる。また、線形近似では解消できていなかったような不整合も整えることができる。アルゴリズムは次の通りである。
【００８５】
Ｓｔｅｐ１：入力ＳＤＦ：ｏｒｇに初期ＳＤＦを読み込む。
Ｓｔｅｐ２：出力ＳＤＦ：ｅｘｔ←ｏｒｇ
Ｓｔｅｐ３：ｅｘｔを拡張する。
Ｓｔｅｐ４：ｅｘｔの各サンプル点で近傍のｏｒｇまたはｅｘｔからＱＳＤＦを計算し、ｅｘｔを更新する。
Ｓｔｅｐ５：Ｓｔｅｐ３に戻って必要な回数繰り返す。
Ｓｔｅｐ６：ｅｘｔが結果となる。
【００８６】
ｏｒｇは初期化した後には変化しない。Ｓｔｅｐ３では、ｅｘｔを近傍のマスクで膨張させた領域を設定している。Ｓｔｅｐ４では、同一サンプル点について、ｏｒｇとｅｘｔの両方にサンプルがある場合は、ｏｒｇを優先することで、ｅｘｔが初期値から離れていかないように抑制している。ＱＳＤＦを計算して距離｜ｄ｜がＴ以上になるサンプルは除去して、計算対象が全空間に及んでしまわないように抑制している。
【００８７】
データへの適用結果について説明する。図６−１は初期状態における本実施の形態の楕円体への適用結果を示す図である。図６−２は１０回繰り返し後における本実施の形態の楕円体への適用結果を示す図である。図６−３は２０回繰り返し後における本実施の形態の楕円体への適用結果を示す図である。図６−４は５０回の繰り返し後における本実施の形態の楕円体への適用結果を示す図である。図６−５はサンプル点数、当てはめ誤差および初期状態を１とした場合の平均曲率の変化を示す図である。
【００８８】
初期状態として楕円体の半分が与えられ、繰り返しの途中の状態を表示している。全体の形状が楕円体なのは明らかであるが、大局的な形状の知識を用いずに、局所演算の繰り返しだけで、欠損部分が埋められて滑らかな面が生成されていることがわかる。この実験ではｗ（Δｐｉ）は標準偏差δのガウス分布とし、次の式（４３）のような近傍範囲（３３近傍）を用いている。
【００８９】
【数４３】
2006039622.tif 000045
繰り返し数とともに、サンプル点数と当てはめ誤差の変化をプロットすると、最初はどちらも増加するが、約４０回の繰り返しで穴が塞がると減少傾向にあることが観察される。曲率の平均はおおよそ単調に減少する。
【００９０】
図７−１〜７−４は本実施の形態における手法を、埴輪の馬を計測した距離データから生成したモデルに適用した結果を示す図である。生成に当たっては上述の非特許文献７の手法を用い、手法中の補外処理はあえて掛けていない。脚部の間に計測が困難な部分が残っていたが、本手法の２０回の繰り返しにより、連続な面で補完されていることがわかる。誤差や曲率は楕円体の場合程単純な挙動は示さなかった。サンプル点は補完処理により２４８ｋから２８２ｋに増加し、計算時間は１．７ＧＨｚの単一ＣＰＵで約１時間半であった。
【００９１】
ＳＤＦの逐次的な局所二次関数当てはめによる形状モデルの欠損部分の補完を行った。当てはめる二次関数モデルと、曲面曲率との関係を明らかにし、符号付距離だけでなく法線の場も含めて整合性のとれた、曲率が滑らかな場の補完を行うことができた。ロバスト統計と組み合わせて極端な外れ値を除去することも可能である。また、本手法は多重解像度処理へ拡張することが可能であり、局所性のレベルを複数設定することで、より安定で高速な処理が行えることが期待できる。
【産業上の利用可能性】
【００９２】
以上のように、本発明にかかる３次元図形の曲面再構成方法および３次元図形の曲面再構成プログラムは、形状モデルの欠損部分の補完に有用であり、特に、レーザー・符号化光源・カメラを組み合わせた三次元形状計測システムなどにおける、計測が困難な部分が生ずる場合の補完処理に適している。
【図面の簡単な説明】
【００９３】
【図１】符号付距離場（ＳＤＦ）を記述するパラメータの概要を示す図である。
【図２−１】格子上にとられたサンプル点においてデータ形状ＳのＳＤＦをサンプリングする過程を示す２次元模式図である。
【図２−２】サンプル点から最近点へのベクトルの概要を示す図である。
【図３−１】曲面再構成の過程を示す図である。
【図３−２】曲面再構成の過程を示す図である。
【図３−３】曲面再構成の過程を示す図である。
【図３−４】曲面再構成の過程を示す図である。
【図４】サンプル点の近傍のＳＤＦからの曲率の計算に用いられるパラメータの概要を示す図である。
【図５】平行曲面上の面要素におけるパラメータの概要を示す図である。
【図６−１】初期状態における本実施の形態の楕円体への適用結果を示す図である。
【図６−２】１０回繰り返し後における本実施の形態の楕円体への適用結果を示す図である。
【図６−３】２０回繰り返し後における本実施の形態の楕円体への適用結果を示す図である。
【図６−４】５０回の繰り返し後における本実施の形態の楕円体への適用結果を示す図である。
【図６−５】サンプル点数、当てはめ誤差および初期状態を１とした場合の平均曲率の変化を示す図である。
【図７−１】本実施の形態における手法を、埴輪の馬を計測した距離データから生成したモデルに適用した結果を示す図である。
【図７−２】本実施の形態における手法を、埴輪の馬を計測した距離データから生成したモデルに適用した結果を示す図である。
【図７−３】本実施の形態における手法を、埴輪の馬を計測した距離データから生成したモデルに適用した結果を示す図である。
【図７−４】本実施の形態における手法を、埴輪の馬を計測した距離データから生成したモデルに適用した結果を示す図である。
【符号の説明】
【００９４】
１０  物体表面
１１  サンプル点
１２  最近点
【図１】
2006039622.tif 000048
【図２−１】
2006039622.tif 000049
【図２−２】
2006039622.tif 000050
【図３−１】
2006039622.tif 000051
【図３−２】
2006039622.tif 000052
【図３−３】
2006039622.tif 000053
【図３−４】
2006039622.tif 000054
【図４】
2006039622.tif 000055
【図５】
2006039622.tif 000056
【図６−１】
2006039622.tif 000057
【図６−２】
2006039622.tif 000058
【図６−３】
2006039622.tif 000059
【図６−４】
2006039622.tif 000060
【図６−５】
2006039622.tif 000061
【図７−１】
2006039622.tif 000062
【図７−２】
2006039622.tif 000063
【図７−３】
2006039622.tif 000064
【図７−４】
2006039622.tif 000065