(57)【要約】【課題】点群デ−タのノイズや誤差を、座標に関する制約を受けることなく、効率的かつ適切に除去することができる。【解決手段】被写体の形状を表す、３次元の座標点の集合を複数のクラスタに分割する分割手段と、各クラスタに対して、クラスタに含まれる各座標点の分散に基づき決定した座標軸を一の座標軸とする局所座標系を定義し、当該各座標点の当該局所座標系における座標値を算出する座標値算出手段と、座標値算出手段が算出した座標値に基づき、クラスタに対応する回帰曲面を算出する回帰曲面算出手段と、回帰曲面算出手段が算出した回帰曲面に基づき、クラスタに含まれる各座標点の局所座標系における座標値のうち、座標値算出手段が当該各座標点の分散に基づき決定した座標軸に対応する成分を補正する補正手段と、を備える。【選択図】図３
2017167671.tif 000002
【特許請求の範囲】
【請求項１】
被写体の形状を表す、３次元の座標点の集合を複数のクラスタに分割する分割手段と、
各クラスタに対して、クラスタに含まれる各座標点の分散に基づき決定した座標軸を一の座標軸とする局所座標系を定義し、当該各座標点の当該局所座標系における座標値を算出する座標値算出手段と、
前記座標値算出手段が算出した座標値に基づき、前記クラスタに対応する回帰曲面を算出する回帰曲面算出手段と、
前記回帰曲面算出手段が算出した前記回帰曲面に基づき、前記クラスタに含まれる各座標点の前記局所座標系における座標値のうち、前記座標値算出手段が当該各座標点の分散に基づき決定した前記座標軸に対応する成分を補正する補正手段と、を備える
ことを特徴とする情報処理装置。
【請求項２】
前記補正手段は、さらに、
前記クラスタに含まれる各座標点の前記局所座標系における座標値であって、前記座標値算出手段が当該各座標点の分散に基づき決定した前記座標軸に対応する成分が補正された座標値に基づき、当該各座標点の大域座標系における座標値を補正する
請求項１に記載の情報処理装置。
【請求項３】
前記補正手段により大域座標系における座標値が補正された、前記被写体の形状を表す座標点の集合が、前記分割手段に入力され、
前記分割手段と前記座標値算出手段と前記回帰曲面算出手段と前記補正手段とによる処理が繰り返し実行される
請求項２に記載の情報処理装置。
【請求項４】
前記座標値算出手段は、
前記複数のクラスタのそれぞれに対して局所座標を定義する際、局所座標系の座標軸のうち一の座標軸を、当該クラスタに含まれる各座標点と他の２軸がなす平面との距離の分散値が最小になるように、決定する
請求項１から請求項３のうちのいずれか１項に記載の情報処理装置。
【請求項５】
前記分割手段は、前記被写体の形状を表す座標点の集合について、距離が近い座標点どうしを所定の数ずつ集積させて、各クラスタを形成する
請求項１から請求項４のうちのいずれか１項に記載の情報処理装置。
【請求項６】
前記回帰曲面算出手段は、前記被写体の、少なくとも形状または種類を識別可能な識別データに基づき、回帰曲面のパラメータを決定する
請求項１から請求項５のうちのいずれか１項に記載の情報処理装置。
【請求項７】
前記回帰曲面算出手段は、前記クラスタに含まれる各座標点の位置と、算出した当該クラスタに対応する回帰曲面との関係に基づき、回帰曲面のパラメータを変更して、再度回帰曲面を算出する
請求項１から請求項６のうちのいずれか１項に記載の情報処理装置。
【請求項８】
回帰曲面がＰ次（Ｐ＝１，２，３・・・）の多項式であり、
回帰曲面のパラメータが、前記多項式の実定数または前記多項式の次数の少なくとも一方を含む
請求項６または請求項７に記載の情報処理装置。
【請求項９】
前記被写体の形状を表す座標点の集合のうち、ユーザによって指定された範囲に含まれる座標点の集合に対して、前記分割手段と前記座標値算出手段と前記回帰曲面算出手段と前記補正手段とによる処理が実行される
請求項１から請求項８のうちのいずれか１項に記載の情報処理装置。
【請求項１０】
前記被写体の形状を表す座標点の集合を分割して得られた前記複数のクラスタのうち、ユーザによって指定されたクラスタに対して、前記座標値算出手段と前記回帰曲面算出手段と前記補正手段とによる処理が実行される
請求項１から請求項９のうちのいずれか１項に記載の情報処理装置。
【請求項１１】
被写体の形状を表す、３次元の座標点の集合を複数のクラスタに分割する分割ステップと、
各クラスタに対して、クラスタに含まれる各座標点の分散に基づき決定した座標軸を一の座標軸とする局所座標系を定義し、当該各座標点の当該局所座標系における座標値を算出する座標値算出ステップと、
前記座標値算出ステップにおいて算出された座標値に基づき、前記クラスタに対応する回帰曲面を算出する回帰曲面算出ステップと、
前記回帰曲面算出ステップにおいて算出された前記回帰曲面に基づき、前記クラスタに含まれる各座標点の前記局所座標系における座標値のうち、当該各座標点の分散に基づき決定された前記座標軸に対応する成分を補正する補正ステップと、を含む
ことを特徴とする情報処理方法。
【請求項１２】
コンピュータを請求項１から請求項１０のうちのいずれか一項に記載の情報処理装置の各手段として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、点群データを補正する処理に関する。
【背景技術】
【０００２】
従来から、被写体の形状を表す３次元座標点の集合（以降では点群デ−タと呼ぶ）に含まれる、ノイズや誤差である座標点（以降、単にノイズや誤差とも呼ぶ）を除去する技術が知られている。一般に点群デ−タを取得する方法は、計測光を投射し被写体からの反射光を計測するアクティブ法と、複数の画像だけから推定を行うパッシブ法に分けられる。アクティブ法は、環境光による妨害や被写体の計測光に対する反射特性などの影響を受け、ノイズや誤差が発生する。パッシブ法は、被写体の光沢や遮蔽などの影響を受け、ノイズや誤差が発生する。そのため、点群デ−タの取得後にノイズや誤差を除去することが必要とされている。特許文献１では、点群デ−タを、４階差分商を用いて平滑化する方法が提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３６１０２９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に提案されている方法では、点群デ−タが２次元の等間隔直交格子上に配置されていることが前提とされている。さらに、特許文献１に記載されている方法では、修正パターン（５次ベジエ曲面）に任意性が残る場合がある。例えば、特許文献１の図４に示される例において、点列全体の平滑基準値Ｆが最小になる修正パターンが複数存在する場合である。その場合、一意に最適な平滑化を決定できない。そこで、本発明は、点群デ−タのノイズや誤差を、座標に関する制約を受けることなく、効率的かつ適切に除去することを目的とする。
【課題を解決するための手段】
【０００５】
本発明による情報処理装置は、被写体の形状を表す、３次元の座標点の集合を複数のクラスタに分割する分割手段と、各クラスタに対して、クラスタに含まれる各座標点の分散に基づき決定した座標軸を一の座標軸とする局所座標系を定義し、当該各座標点の当該局所座標系における座標値を算出する座標値算出手段と、座標値算出手段が算出した座標値に基づき、クラスタに対応する回帰曲面を算出する回帰曲面算出手段と、回帰曲面算出手段が算出した回帰曲面に基づき、クラスタに含まれる各座標点の局所座標系における座標値のうち、座標値算出手段が当該各座標点の分散に基づき決定した座標軸に対応する成分を補正する補正手段と、を備えることを特徴とする。
【発明の効果】
【０００６】
本発明によれば、点群デ−タのノイズや誤差を、座標に関する制約を受けることなく、効率的かつ適切に除去することができる。
【図面の簡単な説明】
【０００７】
【図１】本発明による情報処理装置の第１の実施例における構成を示すブロック図。
【図２】本発明による情報処理装置の機能ブロック図。
【図３】本発明による情報処理装置の第１の実施例における処理の流れを示すフローチャート。
【図４】クラスタに含まれる座標点が補正される様子を模式的に示す図。
【図５】第１の実施例の点群補正処理の処理結果の例を示す図。
【図６】第２の実施例の情報処理装置における処理の流れを示すフローチャート。
【図７】第３の実施例の情報処理装置における処理の流れを示すフローチャート。
【発明を実施するための形態】
【０００８】
以下、添付の図面を参照して、本発明を実施する形態について説明する。なお、以下の実施例において示す構成は一例に過ぎず、本発明は図示された構成に限定されるものではない。
【０００９】
［実施例１］
第１の実施例では、局所的な回帰分析を行うことで、効率的かつ正確な点群データ補正を実現する例を述べる。まず、第１の実施例の情報処理装置の構成を説明する。
【００１０】
図１は、第１の実施例の情報処理装置の構成の一例を示す図である。第１の実施例の情報処理装置１００（以下、処理装置１００とする）は、ＣＰＵ１０１、ＲＡＭ１０２、ＲＯＭ１０３、二次記憶装置１０４、入力インターフェース１０５、出力インターフェース１０６を含む。処理装置１００の各構成要素はシステムバス１０７によって相互に接続されている。また、処理装置１００は、入力インターフェース１０５を介して外部記憶装置１０８および操作部１１０に接続されている。また、処理装置１００は、出力インターフェース１０６を介して外部記憶装置１０８および表示装置１０９に接続されている。
【００１１】
ＣＰＵ１０１は、ＲＡＭ１０２をワークメモリとして、ＲＯＭ１０３に格納されたプログラムを実行し、システムバス１０７を介して処理装置１００の各構成要素を統括的に制御する。これにより、後述する様々な処理が実行される。二次記憶装置１０４は、処理装置１００で取り扱われる種々のデータを記憶する記憶装置であり、本実施例ではＨＤＤが用いられる。ＣＰＵ１０１は、システムバス１０７を介して二次記憶装置１０４へのデータの書き込みおよび二次記憶装置１０４に記憶されたデータの読出しを行う。なお、二次記憶装置１０４にはＨＤＤの他に、光ディスクドライブやフラッシュメモリなど、様々な記憶デバイスを用いることが可能である。
【００１２】
入力インターフェース１０５は、例えばＵＳＢやＩＥＥＥ１３９４等のシリアルバスインターフェースである。処理装置１００は、入力インターフェース１０５を介して、外部装置からデータや命令等を入力する。本実施例では、処理装置１００は、入力インターフェース１０５を介して、外部記憶装置１０８（例えば、ハードディスク、メモリカード、ＣＦカード、ＳＤカード、ＵＳＢメモリなどの記憶媒体）からデータを取得する。また本実施例では、処理装置１００は、操作部１１０に入力されたユーザの指示を、入力インターフェース１０５を介して取得する。操作部１１０は、マウスやキーボードなどの入力装置であり、ユーザの指示を入力する。
【００１３】
出力インターフェース１０６は、入力インターフェース１０５と同様にＵＳＢやＩＥＥＥ１３９４等のシリアルバスインターフェースである。なお、出力インターフェース１０６は、例えばＤＶＩやＨＤＭＩ（登録商標）等の映像出力端子であってもよい。処理装置１００は、出力インターフェース１０６を介して、外部装置にデータ等を出力する。本実施例では、処理装置１００は、出力インターフェース１０６を介して表示装置１０９（液晶ディスプレイなどの各種画像表示デバイス）に、ＣＰＵ１０１によって処理されたデータ（例えば、画像データ）を出力する。なお、処理装置１００の構成要素は上記以外にも存在するが、本発明の主眼ではないため、説明を省略する。
【００１４】
以下、第１の実施例の処理装置１００で行われる処理について、図２に示す機能ブロック図および図３に示すフローチャートを用いて説明する。図２は、本発明による処理装置の機能ブロック図である。処理装置１００は、図２に示すように、データ取得部２０１、クラスタ決定部（クラスタ分割部ともいう）２０２、座標変換部（座標値算出部ともいう）２０３、回帰曲面算出部２０４、および座標補正部２０５としての機能を有する。ＣＰＵ１０１がＲＯＭ１０３内に格納された制御プログラムを読み込み実行することで、上記各部の機能が実現される。なお、各部に相当する専用の処理回路を備えるように処理装置１００を構成するようにしてもよい。以下、各部により行われる処理の流れを説明する。図３は、本発明による処理装置の第１の実施例における処理の流れを示すフローチャートである。
【００１５】
ステップＳ３０１では、データ取得部２０１が、入力インターフェース１０５を介して外部装置から、または二次記憶装置１０４から、処理対象の点群データを取得する。そして、データ取得部２０１は、取得した点群データをクラスタ決定部２０２に出力する。点群データは、例えば被写体３次元形状を示すデータであり、３次元座標の集合を含む。
【００１６】
ステップＳ３０２では、クラスタ決定部２０２が、点群データを複数のクラスタに分割する。クラスタ分割には様々な公知の方法を用いることができる。一般的な方法としては、ｋｄ木を利用した最近傍点探索アルゴリズムにより、点群を構成する各点のそれぞれについて、その点に最も近いｋ個の点を探索し、探索した点を集積してクラスタを形成する方法がある。クラスタどうしの重複は許容してもよいし、排他的に形成してもよい。この時、クラスタ決定部２０２が点群データの全点に対し一括で最近傍点探索を行うと、完全に排他的なクラスタを形成することが困難になる。そのため、クラスタ決定部２０２は、次のように漸化的にクラスタを決定してもよい。第１の方法として、１つまたは複数のクラスタを決定した後、未だいずれのクラスタにも属していない点群だけに対して最近傍点探索を再度行い、当該最近傍点探索の結果に基づき新たなクラスタを決定する、という一連の処理を反復する方法がある。第２の方法として、１つまたは複数のクラスタを決定した後、最近傍点探索を再度行い、当該最近傍点探索の結果に対して、決定済みのクラスタに含まれる点を除外するなどの補正を行い、当該補正により更新された最近傍点探索の結果に基づき新たなクラスタを決定する、という一連の処理を反復する方法がある。なお、各クラスタに含まれる点数は同一でもよいし、適応的に変動してもよい。変動する場合は、クラスタ決定部２０２は、例えば、点間距離やその統計に基づいて各クラスタを構成する点数を決定してもよい。
【００１７】
ステップＳ３０３では、クラスタ決定部２０２が１つのクラスタを選択する。ここで選択されるクラスタは、後述する座標補正が行われた点を含んでいてもよい。そのような場合の例として、例えば、複数のクラスタが同一の点を共有していて、そのうち１つのクラスタが座標補正を既に行っている場合が挙げられる。また例えば、点群データの全点または一部に対し複数回座標補正を反復して行う場合が挙げられる。
【００１８】
ステップＳ３０４では、座標変換部２０３が、選択された１つのクラスタだけに適用するための局所座標系を定義し、クラスタに含まれる全点の局所座標系における座標値を算出する。なお、入力された点群データは、同一の大域座標系における全ての点の座標値を含んでいるものとする。なお、この大域座標系は局所座標系と必ずしも同一ではない。局所座標系の決定方法の例として、例えば、クラスタに含まれる点の大域座標系における３次元座標に主成分分析を行い、局所座標系の座標軸の方向を決定する方法がある。この方法では、クラスタに含まれるＮ個の点の大域座標系における３次元座標を結合したＮ行３列の行列をＡ、局所座標系の３つの座標軸の方向ベクトルを結合した３行３列の行列をＵとすると、これらを式（１）で関係づけることができる。
【００１９】
【数１】
2017167671.tif 000003
【００２０】
ここで、Ｃはクラスタの中心座標を表す３次元行ベクトルをＮ個繰り返し結合したＮ行３列の行列である。Ｔは行列の転置である。Σは固有値を表す３行３列の対角行列である。Ｃには、クラスタの重心またはクラスタに含まれる１点の３次元座標を用いることができる。重心とは、Ｎ個の点の大域座標系における３次元座標の加重平均を算出して得られた３次元ベクトルである。式（１）において、左辺から右辺のＵを数値的に算出する具体的な方法として、行列の特異値分解がある。このようにして算出される行列Ｕの各列が、局所座標系の３つの座標軸の方向を表す３次元ベクトルである。この局所座標系は、行列Ｕの第１，２列に対応する２つの軸が張る平面が、クラスタを最もよく近似する平面に一致する、という性質を有する。最もよく近似するとは、平面と各点との距離の分散値が最小になるという意味である。座標変換部２０３は、この平面に垂直な方向、すなわち法線方向にｚ軸を定義する。ｚ軸は、局所座標系の座標軸のうちクラスタに含まれる点群の各点と他の２軸がなす平面との距離の分散値が最小になる座標軸である。なお、局所座標系の座標軸の方向を決定する方法は主成分分析に限られることはなく、Ｌｏｃａｌｌｙ  Ｌｉｎｅａｒ  Ｅｍｂｅｄｄｉｎｇや局所性保存射影など様々な公知の次元削減の手法を応用することができる。
【００２１】
こうして、クラスタに含まれるＮ個の点の局所座標系におけるｘ，ｙ，ｚ各座標を表すＮ次元列ベクトルをそれぞれＸ，Ｙ，Ｚとすると、これらは式（２）で決定される。
【００２２】
【数２】
2017167671.tif 000004
【００２３】
式（２）は、クラスタの中心を原点とする局所座標系の各座標軸に、クラスタに含まれるＮ個の点を射影した座標値の集合を意味する。また、式（２）の左辺は、Ｎ次元列ベクトルを列方向に結合して得られる行列である。後述する回帰曲面の算出は、局所座標系上で座標Ｘ，Ｙ，Ｚに基づいて行われる。以降では、このようにしてＡからＸ，Ｙ，Ｚを算出することを座標変換と呼ぶ。座標変換が必要な理由は、後述する座標の補正において法線方向に各点を移動することにより、点群の密度の変化を最小限に抑えるためである。なお、ステップＳ３０４の座標変換は必ずしも行う必要はなく、大域座標系における３次元座標、すなわち行列Ａに対して直接、以降の処理を行ってもよい。ただし、座標変換を行う場合に比べて補正の誤差が大きくなりやすく、点群の密度がより大きく変化する懸念がある。
【００２４】
ステップＳ３０５では、回帰曲面算出部２０４が、ステップＳ３０３で選択されたクラスタに含まれるＮ個の点の座標Ｘ，Ｙ，Ｚに基づいて回帰曲面を算出する。回帰曲面としては任意の関数を用いることができるが、以降ではＰ次（Ｐ＝１，２，３・・・）の多項式とする。局所座標系における１点の３次元座標を（ｘ，ｙ，ｚ）とすると、回帰曲面は実定数ａijを用いて式（３）で表される。
【００２５】
【数３】
2017167671.tif 000005
【００２６】
本実施例では、回帰曲面を式（４）で表される２次の多項式として説明する。
【００２７】
【数４】
2017167671.tif 000006
【００２８】
不等間隔で配置されたデータの回帰曲面を算出する方法として、米国特許第７８８９９５０号公報に記載されている最小二乗推定が挙げられる。回帰曲面算出部２０４は、上記の回帰曲面を表す関数に基づき、クラスタに含まれるＮ個の点を回帰曲面上に移動した後の各点の座標を決定する。例えば、各点をｚ軸（法線方向）に沿って回帰曲面上に移動させる場合には、各点のｘ，ｙ座標を回帰曲面を表す関数に代入すればよい。それにより、回帰曲面上のｚ座標が導出される。このように各点を回帰曲面上に移動させることを、以降では補正と呼ぶ。ｚ軸に沿った補正を行うことで、補正による点群の密度の変化を最小限に抑えることができる。ただし、補正の方向は必ずしもｚ軸に限定されない。
【００２９】
効率的な補正方法の一例として、式（５）の線形代数演算を行うことで、反復処理なしにＮ個の点のｚ座標を一括で補正することができる。
【００３０】
【数５】
2017167671.tif 000007
【００３１】
ここで、Ｚ’は、局所座標系における補正後の上記Ｎ個の点の、ｚ座標を並べたＮ次元列ベクトルである。また、行列Ｅのｉ行目は、下記参考文献１に記載されている式（２６）を用いて、以下のように定義される。
【００３２】
【数６】
2017167671.tif 000008
【００３３】
［参考文献１］
Hiroyuki Takeda, Student Member, IEEE, Sina Farsiu, Member, IEEE, and Peyman Milanfar, Senior Member, IEEE, ”Kernel Regression for Image Processing and Reconstruction ”, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 16, NO. 2, FEBRUARY 2007, p349-366
式（６）における、ｅは第１要素が１で他の全要素が０であるＮ次元列ベクトルである。回帰曲面が、式（４）に示す２次多項式の場合には、行列Ｄは式（７）で定義されるＮ行６列の行列である。
【００３４】
【数７】
2017167671.tif 000009
【００３５】
ここで、太字の１は全要素が１のＮ次元列ベクトルである。・は要素ごとの積を表す。また、式（７）の右辺は式（４）の各項の変数ｘ，ｙのべきに対応している。なお、回帰曲面がＰ次多項式の場合には、行列Ｄは式（７）の右辺を式（３）に対応させることで同様に定義される。
【００３６】
また、行列Ｗは、２点間の距離の関数Ｋから決定される対角行列であり、式（８）で定義される。
【００３７】
【数８】
2017167671.tif 000010
【００３８】
ここで、ｄｉａｇは、引数のベクトルを対角成分に有する対角行列を生成する演算子である。また、関数Ｋは任意の関数である。関数Ｋには、２次元のガウス関数を用いることができる。
【００３９】
なお、Ｚ’を求める方法はこの方法に限定されない。また、ステップＳ３０５ではＺ’の導出を必ずしも行う必要はなく、式（３）または式（４）の係数ａを求めるだけでもよい。その場合、ステップＳ３０６において、座標補正部２０５がＺ’の算出を行えばよい。
【００４０】
ステップＳ３０６では、座標補正部２０５が、ステップＳ３０５の結果に基づきクラスタに含まれるＮ個の点の位置（座標値）を補正する。先述したＺ’が算出されている場合には、式（９）により、補正後のＮ個の点の大域座標系における３次元座標を結合したＮ行３列の行列Ａ’を決定する。
【００４１】
【数９】
2017167671.tif 000011
【００４２】
ここで、ｕzは行列Ｕの第３列で、法線ベクトルを表す３次元列ベクトルである。（Ｚ´−Ｚ）ＵzTは、大域座標系における補正量を表す。図４は、ステップＳ３０４〜Ｓ３０６の処理によりクラスタに含まれる座標点が補正される様子を模式的に示す図である。図４（ａ）に示される、黒色の座標点は、クラスタ決定部２０２によって選択されたクラスタであって、補正される前のクラスタである。白色の座標点はクラスタに含まれない座標点である。灰色の座標点はクラスタの重心である。ＧｘＧｙＧｚ軸からなる座標系は大域座標系の座標軸である。ｘｙｚ軸からなる座標系はクラスタに対応する局所座標系である。図４（ｂ）には、クラスタに含まれる座標点をｘ−ｚ平面に射影した散布図が示されている。図４（ｂ）に示される破線は、ステップＳ３０５の処理により算出される、クラスタに対応する回帰曲面である。図４（ｂ）に示される矢印は、Ｓ３０６の処理により、各座標点がｚ軸（法線方向）に沿って回帰曲面上に移動する様子を表している。
【００４３】
ステップＳ３０７では、処理装置１００が、データ取得部２０１が取得した点群データに含まれる全ての点について処理が完了したか、すなわち、全てのクラスタについて補正が完了したかを判断する。補正が完了していないクラスタが存在する場合には（ステップＳ３０７のＮＯ）、処理装置１００は、ステップＳ３０３に戻る。そして、クラスタ決定部２０２によって異なるクラスタが選択され、当該クラスタに対してステップＳ３０３〜Ｓ３０６の処理が行われる。処理装置１００は、点群データに含まれる全ての点について処理が完了した場合は（ステップＳ３０７のＹＥＳ）、補正された点群データを出力し処理を終了する。
【００４４】
以上が、第１の実施例の処理装置１００で行われる処理である。以上に説明したように、本実施例では、点群データを分割して得られた各クラスタに対して、局所座標系を定義する。そして、クラスタに含まれる各座標点の、局所座標系における座標値を、回帰曲面に基づき補正する。したがって、本実施例によれば、入力される点群データの配置に依らずに、すなわち座標に関する制約を受けることなく、点群データのノイズや誤差を除去することができる。また、座標に関する制約を受けないので、任意の次数の多項式の曲面を補正の対象にすることができる。
【００４５】
また、本実施例では、式（５）により点群データを一括補正する。したがって、本実施例によれば、点群データからノイズや誤差を効率的に除去することができる。また、本実施例では、図３に示すフローにより、各クラスタについて、行列Ａ’が一意に決定される。したがって、本実施例によれば、補正後の点群データに任意性が残らないので、ノイズや誤差を適切に除去することができる。
【００４６】
また、本実施例では、クラスタに対して局所座標系を定義する際に、クラスタに含まれる各点との距離が最小になる平面に垂直な方向（法線方向）を、ｚ軸として定義する。そして、ｚ軸方向（法線方向）に各点を移動させて、各点の座標値を補正する。したがって、本実施例によれば、補正の前後における、点群の密度の変化を最小限に抑えることができる。よって、例えば、点群データをポリゴンモデルに変換する際に、本実施例に示す方法を用いて、事前に点群データのノイズや誤差を除去することが可能となる。
【００４７】
本実施例の他の効果を説明するため、図３に示す処理を点群データに対して実際に行った実験の結果を以下に示す。１つ目の実験では、補正の精度を計測した。その際、真の点群をＧｚ（Ｇｘ，Ｇｙ）＝０．２Ｇｘ＋ｓｉｎ（πＧｘ／３）という関数によって与えた。なお、（Ｇｘ，Ｇｙ，Ｇｚ）は大域座標系における任意の点の３次元座標を表す。補正対象の１６８１点からなる点群の、（Ｇｘ，Ｇｙ）座標はいずれも［−１０，１０］の区間においてランダムに生成した座標値である。また、上記関数Ｇｚ（Ｇｘ，Ｇｙ）の出力値に標準偏差０．２のガウス乱数をノイズとして加えることで、Ｇｚ座標を生成した。また、クラスタの点数は３１点で固定し、クラスタどうしの重複を許容し、回帰曲面を２次多項式とした。図５（ａ）に、補正対象の点群をＧｘ−Ｇｚ平面に射影した散布図を示す。図５（ａ）において、○は真の点群、×はノイズを与えた点群を表す。図５（ｂ）に、図３に示すフローに従って補正を行った結果を示す。図５（ｂ）において、○は真の点群、△は補正後の点群を表す。図５（ａ）および図５（ｂ）の点群の真の点群に対する平均２乗誤差（Ｍｅａｎ  Ｓｑｕａｒｅ  Ｅｒｒｏｒ）を算出したところ、それぞれ０．２４７５、０．０４０７であった。このように、本実施例で示した方法により点群を補正することで、点群に含まれるノイズ成分を正確に除去することが可能となる。なお、より正確にノイズ成分を除去するために、点群データに含まれる全ての点について処理が完了した場合に（ステップＳ３０７のＹＥＳ）、処理装置１００が、補正された点群データを、再度入力するようにしてもよい。
【００４８】
２つ目の実験では、１つ目の実験と同じ条件で、補正処理に要する時間を計測した。ただし、上記関数Ｇｚ（Ｇｘ，Ｇｙ）の出力値に標準偏差０．４のガウス乱数をノイズとして加えることで、Ｇｚ座標を生成した。本実施例で示した方法により点群データを一括補正した場合、曲面回帰による各座標点の移動に要した時間は１０５秒であった。近傍点探索に要した時間３７５秒を含めると、補正処理全体に要した時間は４８０秒であった。このように、反復処理を必要とせず、点群データを一括補正する本実施例によれば、補正処理に要する時間を短縮させることができる。一方、補正の精度を高めるために反復処理を必要とする方法、例えば、下記参考文献２に記載される方法により点群データを補正した場合、近傍点探索に要した時間は同じく３７５秒であったが、補正処理全体に要した時間は３６４９秒であった。
【００４９】
［参考文献２］
Paola Valdivia, Douglas Cedrim, Fabiano Petronetto, Afonso Paiva, Luis Gustavo Nonato, "Normal Correction towards Smoothing Point-Based Surfaces" Conference on Graphics, Patterns and Images (SIBGRAPI), 2013
【００５０】
［実施例２］
第２の実施例では、ユーザが対話的な指示を行うことで特定の範囲の点群データだけを補正する例を説明する。なお、断りがない限り、第２の実施例における処理装置は、第１の実施例と同じ処理を行うものとする。図６は、第２の実施例の処理装置１００における処理の流れを示すフローチャートである。
【００５１】
ステップＳ５０１では、データ取得部２０１が、ステップＳ３０１の処理と同様に点群データを取得する。
【００５２】
ステップＳ５０２では、クラスタ決定部２０２が、入力インターフェース１０５を介して処理装置１００に入力されたユーザの指示に基づき、処理対象とする点群データの範囲を指定する。この処理に先立ち、クラスタ決定部２０２は、取得された点群データを、表示装置１０９を介してユーザに提示してもよい。そして、ユーザが、表示装置１０９に表示された点群データの中から、処理対象とする範囲を指定する操作を操作部１１０に対して行うようにしてもよい。また、後述するステップＳ５０４の処理を行う場合には、ステップＳ５０２の処理は必ずしも必要ない。
【００５３】
ステップＳ５０３では、クラスタ決定部２０２が、ステップＳ３０２の処理と同様に点群データを複数のクラスタに分割する。このとき、クラスタ決定部２０２は、ステップＳ５０２の処理で指定した、処理対象の点群データに対してクラスタの分割を行う。なお、ステップＳ５０２の処理が実行されていない場合には、データ取得部２０１が取得した点群データ全体に対してクラスタの分割が行われる。
【００５４】
ステップＳ５０４では、クラスタ決定部２０２が、処理対象とするクラスタを限定する。この処理に先立ち、クラスタ決定部２０２は、ステップＳ５０３の処理により取得されたクラスタの情報を、表示装置１０９を介してユーザに提示してもよい。そして、ユーザが、表示装置１０９に表示されたクラスタの中から、処理対象とするクラスタを指定する操作を操作部１１０に対して行うようにしてもよい。なお、クラスタ決定部２０２は、ステップＳ５０２の処理を行う場合には、ステップＳ５０４の処理を必ずしも実行する必要はない。
【００５５】
ステップＳ５０５〜Ｓ５０９の処理は、ユーザの指示に基づいて決定された点群データまたはクラスタの範囲に処理が限定されることを除けば、ステップＳ３０３〜Ｓ３０７の処理と同様である。
【００５６】
以上が、第２の実施例の処理装置１００で行われる処理である。以上の処理によれば、ユーザの判断に基づいて処理対象を必要な部分に限定することができるので、より効率的に点群デ−タを補正することができる。
【００５７】
［実施例３］
第３の実施例では、取得された点群データを識別する情報に基づき、点群データの補正方法を決定する例を説明する。なお、断りがない限り、第３の実施例における処理装置は、第１の実施例と同じ処理を行うものとする。図７は、第３の実施例の処理装置１００における処理の流れを示すフローチャートである。
【００５８】
ステップＳ６０１では、データ取得部２０１が、ステップＳ３０１の処理と同様に点群データを取得する。さらに、データ取得部２０１は、点群データに含まれるメタデータなどから、点群と対応付けられた識別データを取得する。または、データ取得部２０１が、点群データから識別データを生成する。識別データは、点群全体に対し１つの値でもよいし、点群の部分集合ごとに異なる値でもよい。例として、データ取得部２０１が、人物の顔を取得した点群データの場合には、データ取得部２０１は、取得した点群データによって示される点群の中から頭部・鼻・口・顎・耳・頬などの部分を識別し、各部分に対応する点群ごとに異なる識別データを対応付ける。また別の例として、データ取得部２０１が、点群データに含まれるメタデータに基づき、点群データごとに異なる識別データを対応付ける。または、データ取得部２０１が、取得した点群データから当該点群データによって示される被写体を識別し、識別結果に基づき生成した識別データを、当該点群データに対応付ける。これにより、例えば、取得された点群データが人物の点群データである場合と車両の点群データである場合とで、点群データに対して異なる識別データが対応付けられる。なお、識別データは、被写体の全体または一部の形状や種類を識別可能な情報であればどのような形態でもよい。
【００５９】
ステップＳ６０２では、クラスタ決定部２０２が、ステップＳ３０２の処理と同様にクラスタを決定する。
【００６０】
ステップＳ６０３では、クラスタ決定部２０２が、識別データに対応付けられたパラメータを各クラスタに付与する。パラメータとしては、回帰曲面の種類（例えば、実定数ａij）や、多項式の次数などがあるが、これらに限定されることはない。例えば、パラメータはクラスタの点数や重複などクラスタに関する情報でもよいし、反復回数など処理に関する情報でもよい。クラスタ決定部２０２は、識別データとパラメータとの対応を示すデータを、二次記憶装置１０４や外部記憶装置１０８に記憶する。
【００６１】
ステップＳ６０４〜Ｓ６０８の処理は、ステップＳ３０３〜Ｓ３０７の処理と同様である。なお、ステップＳ６０６では、回帰曲面算出部２０４は、各クラスタに対応付けられたパラメータを二次記憶装置１０４や外部記憶装置１０８から読み出し、読み出したパラメータに基づき回帰曲面を決定する。
【００６２】
以上が、第３の実施例の処理装置１００で行われる処理である。以上の処理によれば、点群データまたは各クラスタに対して最適なパラメータを用いて補正を行うことができるので、より正確な点群デ−タの補正を行うことができる。
【００６３】
なお、第２および第３の実施例に記載の実施形態を組合せてもよいことは言うまでもない。
【００６４】
［実施例４］
第４の実施例では、回帰曲面とクラスタに含まれる点の座標値との関係に基づき、適応的に点群データの補正方法を決定する例を説明する。なお、断りがない限り、第４の実施例における処理装置１００は、第１の実施例と同じ処理を行うものとする。
【００６５】
本実施例における処理装置１００は、第１の実施例の処理装置と同様の処理を行う。ただし、本実施例では、ステップＳ３０５の処理において、回帰曲面算出部２０４が、回帰曲面を算出した後、回帰曲面とクラスタに含まれる点の座標値との比較を行う。例えば、回帰曲面算出部２０４は、点と回帰曲面との距離を点ごとに評価してもよいし、点と回帰曲面との距離の総和を評価してもよい。回帰曲面算出部２０４は、評価結果に基づき、回帰曲面のパラメータを変更して再度回帰曲面を算出する。また、回帰曲面算出部２０４は、評価結果に基づき、曲面の距離が所定の閾値を超える点を削除する。なお、回帰曲面算出部２０４は、評価結果に基づき、その他の処理を行ってもよい。
【００６６】
以上の処理によれば、点群データの局所的な形状の非一様性や異常点の存在に対して頑健に点群デ−タの補正を行うことができる。
【００６７】
なお、第２，第３および第４の実施例に記載の実施形態を組合せてもよいことは言うまでもない。
【００６８】
（その他の実施例）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサがプログラムを読み出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００６９】
２０２  クラスタ決定部
２０３  座標変換部
２０４  回帰曲面算出部
２０５  座標補正部
【図１】
2017167671.tif 000012
【図２】
2017167671.tif 000013
【図３】
2017167671.tif 000014
【図４】
2017167671.tif 000015
【図５】
2017167671.tif 000016
【図６】
2017167671.tif 000017
【図７】
2017167671.tif 000018