(57)【要約】高速Ｔスプラインフィッティングシステムが、３次元（３Ｄ）センサと、プロセッサと、Ｔスプライン表現を用いてシーンのポイントクラウドを表現するプログラムを記憶するメモリとを備える。そのシステムは、３Ｄセンサを用いてシーンの画像を取り込むことと、画像からポイントクラウドを生成することと、ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、ポイントクラウドのパラメータ化領域を決定することと、パラメータ化領域を一組のパッチに再帰的に分割処理することと、パッチを接続して、パラメータ化領域内の制御点のトポロジーを規定するＴメッシュを形成することと、Ｔメッシュに従ってポイントクラウドにＴスプライン表面をフィッティングし、制御点の位置を特定することとを実行する。
2019536162.tif 000002
【特許請求の範囲】
【請求項１】
Ｔスプライン表現を用いてシーンのポイントクラウドを表現するシステムであって、
前記シーンの画像を取り込むように構成される３次元（３Ｄ）センサと、
前記３Ｄセンサ、及びＴスプライン表現を用いて前記シーンのポイントクラウドを表現するプログラムを記憶するメモリと通信し、前記プログラムの命令を実行するように構成されるプロセッサであって、前記命令は、
前記３Ｄセンサを用いて前記シーンの画像を取り込むステップと、
前記画像から前記ポイントクラウドを生成するステップと、
前記ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、前記ポイントクラウドの前記パラメータ化領域を決定するステップと、
終了条件が閾値条件を満たすまで、前記パラメータ化領域及び前記ポイントクラウドの前記マッピングされたデータ点を一組のパッチに再帰的に分割処理するステップであって、現在の分割処理は、先行する分割処理によって形成されたパッチに対応する前記ポイントクラウドの部分にスプライン表面をフィッティングすることと、前記パッチを更に分割処理することとを含む、ステップと、
前記パッチを接続して、前記パラメータ化領域内の制御点のトポロジーを規定するＴメッシュを形成するステップと、
前記Ｔメッシュに従って前記ポイントクラウドにＴスプライン表面をフィッティングし、前記制御点の位置を特定するステップと、
を含む、プロセッサと、
を備える、システム。
【請求項２】
前記パッチはそれぞれ、前記パラメータ化領域内の長方形のサブパッチである、請求項１に記載のシステム。
【請求項３】
前記分割処理することは、前記パラメータ化領域を前記一組のパッチに均等に、又は不均等に分割する、請求項１に記載のシステム。
【請求項４】
前記閾値条件は、パッチ内のデータ点に対してフィッティングされるスプラインに関する所定のフィッティング誤差値である、請求項１に記載のシステム。
【請求項５】
前記閾値条件は、前記画像の所定のデータサイズである、請求項４に記載のシステム。
【請求項６】
前記命令は、
前記フィッティング済みＴスプライン表面のデータをディスプレイデバイス又は別のコンピュータに送信することを更に含む、請求項１に記載のシステム。
【請求項７】
ディスプレイデバイスを更に備え、
前記ディスプレイデバイスは、前記ディスプレイデバイスの画面上に前記Ｔスプライン表面及びＴメッシュを表示するように構成される、請求項１に記載のシステム。
【請求項８】
メモリ及び３次元センサと通信するプロセッサを用いて、Ｔスプライン表現を用いてシーンのポイントクラウドを表現する方法であって、
前記３Ｄセンサを用いて前記シーンの画像を取り込むことと、
前記画像から前記ポイントクラウドを生成することと、
前記ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、前記ポイントクラウドの前記パラメータ化領域を決定することと、
終了条件が閾値条件を満たすまで、前記パラメータ化領域及び前記ポイントクラウドの前記マッピングされたデータ点を一組のパッチに再帰的に分割処理することであって、現在の分割処理は、先行する分割処理によって形成されたパッチに対応する前記ポイントクラウドの部分にスプライン表面をフィッティングすることと、前記パッチを更に分割処理することとを含むことと、
前記パッチを接続して、前記パラメータ化領域内の制御点のトポロジーを規定するＴメッシュを形成することと、
前記Ｔメッシュに従って前記ポイントクラウドにＴスプライン表面をフィッティングし、前記制御点の位置を特定することと、
を含む、方法。
【請求項９】
前記パッチのそれぞれのフィッティング誤差は、前記パラメータ化領域の他のパッチのフィッティング誤差から独立して求められる、請求項８に記載の方法。
【請求項１０】
前記閾値条件は前記部分の面積によって決定される、請求項８に記載の方法。
【請求項１１】
前記パッチはそれぞれ、前記パラメータ化領域内の長方形のサブパッチである、請求項８に記載の方法。
【請求項１２】
前記分割処理することは、前記パラメータ化領域を前記一組のパッチに均等に、又は不均等に分割する、請求項８に記載の方法。
【請求項１３】
前記閾値条件は、所定のフィッティング誤差値である、請求項８に記載の方法。
【請求項１４】
前記閾値条件は、前記画像の所定のデータサイズである、請求項８に記載の方法。
【請求項１５】
前記分割処理することは、最大フィッティング二乗平均平方根誤差（ＲＭＳＥ）を用いて、前記パッチの分割処理パーセンテージに基づいて実行される、請求項８に記載の方法。
【請求項１６】
前記分割処理パーセンテージは、０．１％〜１％の範囲内のノット挿入比である、請求項１５に記載の方法。
【請求項１７】
前記フィッティング済みＴスプライン表面のデータをディスプレイデバイス又は別のコンピュータに送信することを更に含む、請求項８に記載の方法。
【請求項１８】
前記ディスプレイデバイスの画面上に前記Ｔスプライン表面及びＴメッシュを表示することを更に含む、請求項１７に記載の方法。
【請求項１９】
プロセッサにＴスプライン表現を用いてシーンのポイントクラウドを表現する方法を実行させるプログラムコードを記憶する非一時的コンピュータ可読記録媒体であって、前記プログラムコードは、
前記３Ｄセンサを用いて前記シーンの画像を取り込むプログラムコードと、
前記画像から前記ポイントクラウドを生成するプログラムコードと、
前記ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、前記ポイントクラウドの前記パラメータ化領域を決定するプログラムコードと、
終了条件が閾値条件を満たすまで、前記パラメータ化領域及び前記ポイントクラウドの前記マッピングされたデータ点を一組のパッチに再帰的に分割処理するプログラムコードであって、現在の分割処理は、先行する分割処理によって形成されたパッチに対応する前記ポイントクラウドの部分にスプライン表面をフィッティングすることと、前記パッチを更に分割処理することとを含む、プログラムコードと、
前記パッチを接続して、前記パラメータ化領域内の制御点のトポロジーを規定するＴメッシュを形成するプログラムコードと、
前記Ｔメッシュに従って前記ポイントクラウドにＴスプライン表面をフィッティングし、前記制御点の位置を特定するプログラムコードと、
を含む、非一時的コンピュータ可読記録媒体。
【請求項２０】
前記パッチのそれぞれのフィッティング誤差は、前記パラメータ化領域の他のパッチのフィッティング誤差から独立して求められる、請求項１９に記載の非一時的コンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、シーンの一組の３次元（３Ｄ）点を迅速に表現するシステム及び方法に関し、より具体的には、高速Ｔスプラインフィッティング（fast T-spline fitting）を用いて、シーンの一組の３Ｄ点を表現するシステム及び方法に関する。
【背景技術】
【０００２】
Ｔスプラインは、コンピュータ支援設計、コンピュータグラフィックス及びリバースエンジニアリングにおける従来の不均一有理基底スプライン（NURBS：non-uniform rational bases spline：不均一有理Ｂスプライン）又は基底スプライン（bases spline：Ｂスプライン）表現に比べて、はるかに少ない数の制御点を用いて、任意の形状の物体を表現するために使用される。
【０００３】
従来のＴスプラインフィッティングアルゴリズムは、一般に、簡単なＢスプライン又はベジェ表面から開始して、入力ポイントクラウドを近似する。その後、より多くの制御点を制御メッシュの中に挿入することによって、大きいフィッティング誤差を有する場所において、制御メッシュが局所的に精緻化される。メッシュ精緻化後に、全ての入力点を再び用いて、新たな一組の制御点を精緻化する。これは、各メッシュ精緻化反復において、新たな最小二乗フィッティングのために、あらゆる単一のデータ点がアクセスされることを意味する。数多くの細部を有する大規模なポイントクラウドの場合、そのようなメッシュ精緻化及び最小二乗フィッティングは、高いフィッティング精度と少ない数の制御点との間の合理的なバランスを達成するために、何度も実行されなければならない。そのような従来のＴスプラインフィッティング方式にとって、高速計算を達成するのは難しい。
【０００４】
したがって、既存の方法を用いてポイントクラウドにわたってＴスプラインをフィッティングすることは、Ｔスプライン制御点が同時に全てのデータ点とフィッティングされなければならないことから時間がかかり、それにより計算コストもかかる。
【０００５】
例えば、画像を取り込む方法が特許文献１に記述されているが、その方法は、より長い計算時間を必要とする。それゆえ、シーンの一組の３Ｄ点を表現する高速Ｔスプラインフィッティングを提供することができるシステム及び方法が必要とされている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許出願公開第２０１６０００５２２１号
【発明の概要】
【０００７】
いくつかの実施形態は、高速Ｔスプラインフィッティングアルゴリズムによって、Ｔスプライン表面が２Ｄパラメータ化ポイントクラウドに効率的にフィッティングされるということの認識及び理解に基づく。
【０００８】
本発明の実施形態によれば、Ｔスプライン表現を用いてシーンのポイントクラウドを表現するシステムは、シーンの画像を取り込むように構成される３次元（３Ｄ）センサと、３Ｄセンサ、及びＴスプライン表現を用いてシーンのポイントクラウドを表現するプログラムを記憶するメモリと通信し、プログラムの命令を実行するように構成されるプロセッサであって、命令は、３Ｄセンサを用いてシーンの画像を取り込むステップと、画像からポイントクラウドを生成するステップと、ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、ポイントクラウドのパラメータ化領域を決定するステップと、終了条件が閾値条件を満たすまで、パラメータ化領域及びポイントクラウドのマッピングされたデータ点を一組のパッチに再帰的に分割処理するステップであって、現在の分割処理は、先行する分割処理によって形成されたパッチに対応するポイントクラウドの部分にスプライン表面をフィッティングすることと、パッチを更に分割処理することとを含む、ステップと、パッチを接続して、パラメータ化領域内の制御点のトポロジーを規定するＴメッシュを形成するステップと、Ｔメッシュに従ってポイントクラウドにＴスプライン表面をフィッティングし、制御点の位置を特定するステップとを含む、プロセッサとを備える。
【０００９】
本発明の別の実施形態は、メモリ及び３次元センサと通信するプロセッサを用いて、Ｔスプライン表現を用いてシーンのポイントクラウドを表現する方法であって、３Ｄセンサを用いてシーンの画像を取り込むことと、画像からポイントクラウドを生成することと、ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、ポイントクラウドのパラメータ化領域を決定することと、終了条件が閾値条件を満たすまで、パラメータ化領域及びポイントクラウドのマッピングされたデータ点を一組のパッチに再帰的に分割処理することであって、現在の分割処理は、先行する分割処理によって形成されたパッチに対応するポイントクラウドの部分にスプライン表面をフィッティングすることと、パッチを更に分割処理することとを含むことと、パッチを接続して、パラメータ化領域内の制御点のトポロジーを規定するＴメッシュを形成することと、Ｔメッシュに従ってポイントクラウドにＴスプライン表面をフィッティングし、制御点の位置を特定することとを含む、方法を提供する。
【００１０】
さらに、別の実施形態は、プロセッサにＴスプライン表現を用いてシーンのポイントクラウドを表現する方法を実行させるプログラムコードを記憶する非一時的コンピュータ可読記録媒体であって、プログラムコードは、３Ｄセンサを用いてシーンの画像を取り込むプログラムコードと、画像からポイントクラウドを生成するプログラムコードと、ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、ポイントクラウドのパラメータ化領域を決定するプログラムコードと、終了条件が閾値条件を満たすまで、パラメータ化領域及びポイントクラウドのマッピングされたデータ点を一組のパッチに再帰的に分割処理するプログラムコードであって、現在の分割処理は、先行する分割処理によって形成されたパッチに対応するポイントクラウドの部分にスプライン表面をフィッティングすることと、パッチを更に分割処理することとを含む、プログラムコードと、パッチを接続して、パラメータ化領域内の制御点のトポロジーを規定するＴメッシュを形成するプログラムコードと、Ｔメッシュに従ってポイントクラウドにＴスプライン表面をフィッティングし、制御点の位置を特定するプログラムコードとを含む、非一時的コンピュータ可読記録媒体を開示する。
【００１１】
本開示の実施形態によれば、本開示の実施形態によるＴスプライン表現を用いてシーンのポイントクラウドを表現するシステム及び方法は、コンピュータを用いて、計算コストを著しく削減することができ、シーン物体内の画像のデータ処理を改善することができる。
【００１２】
さらに、本開示の実施形態によれば、プロセッサと接続されるメモリ又はコンピュータ可読記録媒体に記憶されるプログラムのアルゴリズムは、制御処理ユニット使用量、及びプロセッサの電力消費量を削減することができる。
【００１３】
本明細書に組み込まれ、その一部を構成する添付の図面は、１つ以上の特定の例を示し、例の説明とともに、その特定の例の原理及び実施態様を説明する役割を果たす。
【図面の簡単な説明】
【００１４】
【図１Ａ】本開示の実施形態による、高速Ｔスプラインフィッティングシステムを示すブロック図である。
【図１Ｂ】３Ｄセンサを用いて３Ｄポイントクラウドを取り込むことを例示する図である。
【図２Ａ】ベジェパッチの場合に計算される制御点を表す図である。
【図２Ｂ】頂点ｎに対応する破線円内部の６つの接合部を表す図である。
【図２Ｃ】頂点ｎに対応する破線円内部の６つの接合部を表す図である。
【図３Ａ】未処理のポイントクラウドのデータから、フィッティング済みＴスプライン表面を取得するＴスプラインフィッティングプロセスのデータ処理ステップを示すブロック図である。
【図３Ｂ】本開示の実施形態による、物体としてソファを使用するＴスプラインフィッティングのデータ処理ステップを示す図である。
【図４】いくつかの異なるシーンについて、本発明のアルゴリズムと、ＫｉｎＦｕ、すなわち、キネクトフュージョン（Kinect Fusion）のオープンソース実施態様との定性的比較を示す図である。
【図５Ａ】本開示の一実施形態による、ＳＫＩ法とＦａｓＴｆｉｔ法との比較を示す図である。
【図５Ｂ】本開示の一実施形態による、ＳＫＩ法とＦａｓＴｆｉｔ法との比較を示す図である。
【図６Ａ】ＦｉｎｄＫｎｏｔＭｕｌｔｉｐｌｉｃｉｔｙアルゴリズムを用いて取得されるフィッティング結果を示す図である。
【図６Ｂ】ＦｉｎｄＫｎｏｔＭｕｌｔｉｐｌｉｃｉｔｙアルゴリズムを用いない場合に取得されるフィッティング結果を示す図である。
【図７】未編成ポイントクラウドをフィッティングする例を示す図である。
【図８】２つの元の画像と、対応する画像フィッティング結果を有するＣ３２  Ｔメッシュ結果及びＳＫＩ−Ｃ３２ＣＴＲＬ  Ｔメッシュ結果とを示す図である。
【発明を実施するための形態】
【００１５】
上記で明らかにされた図面は、ここに開示されている実施形態を記載しているが、この論述において言及されるように、他の実施形態も意図されている。この開示は、限定ではなく代表例として例示の実施形態を提示している。ここに開示されている実施形態の原理の範囲及び趣旨に含まれる非常に多くの他の変更及び実施形態を当業者は考案することができる。
【００１６】
以下の説明は、例示的な実施形態のみを提供し、本開示の範囲も、適用範囲も、構成も限定することを意図していない。そうではなく、例示的な実施形態の以下の説明は、１つ以上の例示的な実施形態を実施することを可能にする説明を当業者に提供する。添付の特許請求の範囲に明記されているような開示された主題の趣旨及び範囲から逸脱することなく要素の機能及び配置に行うことができる様々な変更が意図されている。
【００１７】
以下の説明では、実施形態の十分な理解を提供するために、具体的な詳細が与えられる。しかしながら、当業者は、これらの具体的な詳細がなくても実施形態を実施することができることを理解することができる。例えば、開示された主題におけるシステム、プロセス、及び他の要素は、実施形態を不必要な詳細で不明瞭にしないように、ブロック図形式の構成要素として示される場合がある。それ以外の場合において、よく知られたプロセス、構造、及び技法は、実施形態を不明瞭にしないように不必要な詳細なしで示される場合がある。さらに、様々な図面における同様の参照符号及び名称は、同様の要素を示す。
【００１８】
また、個々の実施形態は、フローチャート、フロー図、データフロー図、構造図、又はブロック図として描かれるプロセスとして説明される場合がある。フローチャートは、動作を逐次的なプロセスとして説明することができるが、これらの動作の多くは、並列又は同時に実行することができる。加えて、これらの動作の順序は、再配列することができる。プロセスは、その動作が完了したときに終了することができるが、論述されない又は図に含まれない追加のステップを有する場合がある。さらに、特に説明される任意のプロセスにおける全ての動作が全ての実施形態において行われ得るとは限らない。プロセスは、方法、関数、手順、サブルーチン、サブプログラム等に対応することができる。プロセスが関数に対応するとき、その関数の終了は、呼び出し側関数又はメイン関数へのその機能の復帰に対応することができる。
【００１９】
さらに、開示された主題の実施形態は、少なくとも一部は手動又は自動のいずれかで実施することができる。手動実施又は自動実施は、マシン、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、又はそれらの任意の組み合わせを用いて実行することもできるし、少なくとも援助することができる。ソフトウェア、ファームウェア、ミドルウェア又はマイクロコードで実施されるとき、必要なタスクを実行するプログラムコード又はプログラムコードセグメントは、マシン可読媒体に記憶することができる。プロセッサ（複数の場合もある）が、それらの必要なタスクを実行することができる。本発明は、高速Ｔスプラインフィッティングを利用することによって従来技術のフィッティングシステムを改善する。
【００２０】
図１Ａは、本開示の実施形態による、高速Ｔスプラインフィッティングシステム１００を示すブロック図である。高速Ｔスプラインフィッティングシステム１００は、キーボード１１１及びポインティングデバイス／メディア１１２、マイクロフォン１１３と接続可能な入力／出力（Ｉ／Ｏ）インターフェースを有するヒューマンマシンインターフェース（ＨＭＩ）１１０、受信機１１４、送信機１１５、３Ｄセンサ１１６、全地球測位システム（ＧＰＳ）１１７、１つ以上のＩ／Ｏインターフェース１１８、プロセッサ１２０、記憶装置１３０、メモリ１４０、ローカルエリアネットワーク及びインターネットネットワーク（図示せず）を含むネットワーク１５５と接続可能なネットワークインターフェースコントローラ１５０（ＮＩＣ）、ディスプレイデバイス１６５に接続されたディスプレイインターフェース１６０、撮像デバイス１７５と接続可能な撮像インターフェース１７０、印刷デバイス１８５と接続可能なプリンタインターフェース１８０を備えることができる。Ｉ／Ｏインターフェースを有するＨＭＩ１１０は、アナログ／デジタル変換器及びデジタル／アナログ変換器を含むことができる。Ｉ／Ｏインターフェースを有するＨＭＩ１１０は、無線インターネット接続又は無線ローカルエリアネットワークを介して、複数の３Ｄポイントクラウドを完成させることを可能にする、他の高速Ｔスプラインフィッティングシステム又は他のコンピュータと通信することができる無線通信インターフェースを含む。高速Ｔスプラインフィッティングシステム１００は、電源１９０を備えることができる。電源１９０は、外部電源（図示せず）からＩ／Ｏインターフェース１１８を介して充電可能なバッテリーとすることができる。用途に応じて、電源１９０は、任意選択で、システム１００の外部に配置することができる。ＨＭＩ及びＩ／Ｏインターフェース１１０及びＩ／Ｏインターフェース１１８は、とりわけ、コンピュータモニター、カメラ、テレビ、プロジェクター、又はモバイルデバイスを含む別のディスプレイデバイス（図示せず）に接続するように適応させることができる。
【００２１】
高速Ｔスプラインフィッティングシステム１００は、ＮＩＣ１５０に接続したネットワーク１５５を介して発話データを含む電子テキスト／撮像文書を受信することができる。記憶装置１３０は、高速Ｔスプラインフィッティングプログラム１３１を含み、そのプログラム１３１のアルゴリズムは、コードデータとして記憶装置１３０に記憶され、そのアルゴリズムは、コードデータ（プログラムのアルゴリズム又は命令）に従ってプロセッサ１２０によって実行される。プログラム１３１は、メモリ１４０を用いてコンピュータ可読記録媒体（図示せず）からプログラムのアルゴリズムをロードすることによってプロセッサ１２０が高速Ｔスプラインフィッティングプログラムを実行できるように、この媒体に記憶することができる。さらに、ポインティングデバイス／媒体１１２は、コンピュータ可読記録媒体上に記憶されたプログラムを読み出すデータ処理デバイスを含むことができる。
【００２２】
３Ｄセンサ１１６を用いてシーンの３Ｄポイントクラウドを取り込み始めるために、キーボード１１１、ポインティングデバイス／媒体１１２を用いて、又は他のコンピュータ１９５に接続されるワイヤレスネットワーク若しくはネットワーク１９０を介して、システム１００に命令を送信することができる。３Ｄポイントクラウドの取り込みは、記憶装置１３０内に記憶されるプリインストールされた従来の音声認識プログラムを用いて、マイクロフォン１１３を介してユーザーの音響信号を受信するのに応答して開始することができる。さらに、高速Ｔスプラインフィッティングシステム１００は、ネットワーク１５５を介して、他のコンピュータ１９５から３Ｄポイントクラウドのデータを受信することができ、３Ｄポイントクラウドの受信データを用いて、高速Ｔスプラインフィッティングを実行することができる。システム１００は、高速Ｔスプラインフィッティングプロセスの結果として生成されたデータを、ネットワーク１５５を介して他のコンピュータ１９５に送信することができる。
【００２３】
プロセッサ１２０は、１つ以上のグラフィックス処理ユニット（ＧＰＵ）を含む、複数のプロセッサとすることができる。記憶装置１３０は、マイクロフォン１１３を介して取得された音声信号を認識するためにプロセッサ１２０によって実行することができる音声認識アルゴリズム（図示せず）を含むことができる。
【００２４】
プロセッサ１２０は、メモリ１４０と通信する記憶装置１３０に記憶されるプログラム１３１の命令を実行する。３Ｄセンサ１１６は、シーンのデータを取り込み、画像のデータを、Ｉ／Ｏインターフェース１１０を介してメモリ１４０に送信する。プロセッサ１２０は、メモリ１４０内の画像のデータから、シーンの３Ｄポイントクラウドを生成する。３Ｄポイントクラウドから、プロセッサ１２０は、ポイントクラウドのデータ点をパラメータ化領域のパラメータの値にマッピングすることによって、ポイントクラウドのパラメータ化領域を決定する。さらに、プロセッサ１２０は、パラメータ化領域及びポイントクラウドのマッピングされたデータ点を、終了条件が満たされるまで、一組のパッチに再帰的に分割処理する。この場合、現在の分割処理は、先行する分割処理によって形成されるパッチに対応するポイントクラウドの部分にスプライン表面をフィッティングすることと、フィッティングの誤差が或る閾値（誤差値）より大きいとき、更にパッチを分割処理することとを含む。閾値は事前に決定することができる。例えば、閾値は、ポイントクラウドのその部分の面積によって、又は所定のフィッティング誤差値によって決定することができる。この場合、各パッチのフィッティング誤差は、パラメータ化領域の他のパッチのフィッティング誤差から独立して求められる。フィッティング誤差値は、フィッティング誤差と呼ばれる場合がある。さらに、各パッチのフィッティング誤差は、パラメータ化領域の他のパッチのフィッティング誤差から独立して求めることができる。
【００２５】
場合によっては、閾値は、画像の所定のデータサイズに基づいて自動的に決定される場合がある。閾値はデータに依存する場合があり、使用されるデータのコンテキストに応じて決定される場合がある。さらに、プロセッサ１２０は、パッチの接続を実行して、パラメータ領域内の制御点のトポロジーを規定するＴメッシュを形成し、Ｔメッシュに従ってポイントクラウドにＴスプライン表面をフィッティングし、制御点の位置を特定する。
【００２６】
場合によっては、パッチはそれぞれ、パラメータ化領域内の長方形のサブパッチとすることができる。さらに、分割処理することは、パラメータ化領域を一組のパッチに均等に、又は不均等に分割することができる。
【００２７】
いくつかの例では、閾値条件は、パッチ内のデータ点に対してフィッティングされるスプラインに関する所定のフィッティング誤差値によって定義することができる。別の場合では、閾値条件は、画像の所定のデータサイズによって定義することができる。
【００２８】
さらに、フィッティング済みＴスプライン表面のデータは、ディスプレイデバイス又は別のコンピュータに送信することができる。この場合、ディスプレイデバイスは、ディスプレイデバイスの画面上にＴスプライン表面及びＴメッシュを表示することができる。
【００２９】
ポイントクラウド取込プロセス
図１Ｂは、本開示の実施形態による、高速Ｔスプラインフィッティングシステム１００の３Ｄセンサ１１６を用いて３Ｄポイントクラウドを取り込むことを例示する図である。この場合、高速Ｔスプラインフィッティングシステム１００は、前壁２１０、左壁２１１、右壁２１２、床２２０、天井（図示せず）、ソファ２３０、ランプ２４０及び窓２５０を含む、室内の物体の点データをスキャンする。
【００３０】
３Ｄセンサ１１６は、物体の表面上で測定された一組の３Ｄ点を含む、物体の点データを取り込み、点データはメモリ１４０又は記憶装置１３０に記憶される。高速Ｔスプラインフィッティングプログラム１３１に従って、プロセッサ１２０を用いて、点データに関するデータ処理が実行される。通常、一組の３Ｄ点は、奥行画像として知られる、ピクセルによって示される２Ｄ画像として取り込まれ、各ピクセルは、そのピクセルによって規定される光線の方向に沿って位置する物体の表面上の３Ｄ点までの距離測定値（距離値）を含む。ピクセルごとに、ピクセルに対応する光線の方向は、３Ｄセンサ１１６の内部較正パラメータを用いてピクセルを逆投影することによって再生することができ、３Ｄ点は３Ｄロケーションにおいて光線上で再生することができ、３Ｄセンサ１１６からの３Ｄロケーションの距離は距離測定値によって与えられる。
【００３１】
本開示の一実施形態において、３Ｄポイントクラウドは、３Ｄセンサ１１６を固定された姿勢に配置することによって生成される。３Ｄセンサ１１６の姿勢は３自由度並進（位置）及び３自由度回転（向き）を含み、全部で６自由度を有する。この場合、点データは固定された姿勢において単一フレームとして（奥行画像として）取り込まれ、その点データの単一のフレームによって３Ｄポイントクラウドが生成される。別の実施形態において、３Ｄポイントクラウドは、３Ｄセンサを異なる姿勢に動かし、異なる姿勢において点データの複数のフレームを取り込み、複数のフレームを単一の共通座標系（所定の座標系）の中に互いに位置合わせすることによって生成される。そのような位置合わせは、当前記技術分野において既知であるような同時位置特定及びマッピング（ＳＬＡＭ：simultaneous localization and mapping）技法を使用することによって行うことができる。
【００３２】
入力ポイントクラウドが、奥行画像行−列インデックスを使用することによって固定的にパラメータ化されたと仮定する。任意のダウンストリームアプリケーションに関して高速計算が不要である場合でも、本発明の高速Ｔスプラインフィッティング方式は依然として任意の、より良好なパラメータ化方法を用いて機能することができ、制御点の数がより少ない、潜在的により良好なフィッティング結果をもたらす。さらに、大部分の他のパラメータ化は時間がかかるので、はるかに高速の計算と引き換えに、わずかに制御点が増える負担を担うのが合理的である。したがって、本開示のいくつかの実施形態は、制御処理ユニット使用量及び電力消費量を削減することができ、それもコンピュータの機能を改善する。
【００３３】
図２Ａは、ｕ−ｖ座標上のシート表面の例示であり、そのシートは制御点及びパッチによって表される。図２Ｂ及び図２Ｃは、ｄ＝３の場合の局所ノットベクトル推定の例を示す。３つのベジェパッチ（ｂ１；ｂ２；ｂ３）が、Ｃ１の所定の表面連続性を有する単一のＴメッシュを生成するように接続される。各パッチ境界は、データに応じて連続（実線）又は不連続（破線）に分類され、それを用いて、インデックス／パラメータ空間内でノット多重度（重複するノットラインの数）を求める。図２Ｃ内の破線円内部の６つの接合部は、図２Ｂ内の頂点ｎ（×印）に対応する。ベジェパッチ（黒点）に対して計算される制御点を用いて、最終的なＴスプラインに関して制御点を初期化する。
【００３４】
図３Ａは、本開示の実施形態による、未処理のポイントクラウドのデータからフィッティング済みＴスプライン表面を取得する高速Ｔスプラインフィッティングプロセスのデータ処理ステップを示すブロック図である。Ｔスプラインフィッティングプロセスは、３Ｄセンサ１１６を用いて未処理のポイントクラウド（ポイントクラウドデータ）を取り込むステップ（ステップＳ１）と、パラメータ化ポイントクラウドを取得する（ステップＳ３）ためのデータパラメータ化ステップ（ステップＳ２）と、Ｂスプラインパッチを取得する（ステップＳ５）ための適応分割ステップ（ステップＳ４）と、異なる連続性を有するＴメッシュを取得する（ステップＳ７）ためにＢスプラインパッチに基づいてＴメッシュを推定するステップ（ステップＳ６）と、フィッティング済みＴスプライン表面を取得する（Ｓ９）ために、パラメータ化ポイントクラウドデータと、異なる連続性を有するＴメッシュとを用いて、Ｔスプラインをフィッティングするステップ（ステップＳ８）とを含む。
【００３５】
図３Ｂは、本開示の実施形態による、物体としてソファを使用するＴスプラインフィッティングのデータ処理を示す。この場合、未処理のポイントクラウド（ソファの３Ｄポイントデータ）が３Ｄセンサ１１６を用いて取り込まれる。ポイントクラウドの各データ点が、３次元空間（ｘ軸、ｙ軸及びｚ軸）によって表される。ポイントクラウドに関してデータパラメータ化が実行され、パラメータ化されたポイントクラウドがベクトル｛（ｘ，ｙ，ｚ，ｕ，ｖ）｝として取得される。ただし、パラメータ化されたポイントクラウドは、図示されるように、ｕ−ｖ座標上の点（ｕｉ，ｖｉ）に基づいてパラメータ領域によって表すことができる。図３Ａの各ステップも対応して図に示される。
【００３６】
Ｂスプライン及びＮＵＲＢＳフィッティング
Ｂスプライン又はＮＵＲＢＳ表面をフィッティングするための２つの方式がある。第１の方式は、簡単な制御メッシュから開始し、大きいフィッティング誤差（フィッティング誤差値）を有するエリアにおいてグローバルノット精緻化を実行し、全ての制御点の最適な位置を求め、必要に応じて、データパラメータ化を更新し、その後、フィッティング誤差が十分に小さくなるまで、このプロセスを繰り返す。第２の方式は、必要以上に複雑なメッシュから開始し、ノット除去によってそのメッシュを繰り返し簡単にすることによって、その手順を逆に実施する。
【００３７】
Ｔスプラインフィッティング
或る次数のＴスプライン式が、関連するパラメータｕ及びｖを有する各Ｔスプライン表面点Ｑ（ｕ，ｖ）∈Ｒ３を、以下のように、全ての制御点Ｃｋ∈Ｒ３，ｋ＝１，．．．，Ｋの組み合わせとして表す。
【数１】
2019536162.tif 000003
ただし、Ｕｋ及びＶｋは、第ｋの制御点に関連付けられる、Ｒ２ｄ−１内の局所ノットベクトルであり、Ｔ：Ｒ×Ｒ→Ｒは、入力変数としてｕ、ｖをとり、関数パラメータとしてＵｋ、ＶｋをとるＴスプラインブレンディング関数であり、ｗｋは、制御点ごとの重みである。
【００３８】
ＦＡＳＴＦＩＴアルゴリズム
ＦａｓｔＦｉｔアルゴリズムと呼ばれる、高速Ｔスプラインフィッティングアルゴリズムの概要が、本開示の実施形態による、以下のアルゴリズム１によって記述される。
【表１】
2019536162.tif 000004
ＦａｓｔＦｉｔアルゴリズムは以下のステップを含むことができる。
ＦｉｔＢｅｚｉｅｒＰａｔｃｈＡｄａｐｔｉｖｅ：第一に、入力ポイントクラウドが、所定のフィッティング誤差閾値に従って、一組のＢスプライン／ベジェパッチに適応的に分割（分割処理）される。これらのパッチはそれぞれ、入力データパラメータ領域内の長方形のサブ領域に対応する。言い換えると、各パッチは、パラメータ化領域内の長方形のサブパッチである。例えば、図２Ｂ及び図２Ｃに示されるように、パラメータ化領域は不均等に分割される場合がある。
【００３９】
ＩｎｆｅｒＬｏｃａｌＫｎｏｔＶｅｃｔｏｒ：第二に、所定の最終モデル連続性と、隣接するパッチの共有エッジにおけるデータ連続性との両方に応じて、これらのサブ領域が、異なる接続選択肢を有するＴメッシュに構成される。これは、制御点の数を決定し、Ｔメッシュを生成するために、対応する局所ノットベクトルを推定できるようにする。
【００４０】
ＳｏｌｖｅＣｏｎｔｒｏｌＰｏｉｎｔ：この固定Ｔ−メッシュを見つけた後に、ベジェパッチフィッティング結果で初期化されたＰＣＧを用いて、最適な制御点を取得するために、最終的に、大きい疎線形システムを解く。
【００４１】
各ステップの詳細を説明する前に、固定されたパラメータ化を有するポイントクラウドに焦点を合わせる。
【００４２】
本実施態様において、数多くの３Ｄセンサの未処理の出力は一組の２Ｄインデックス付き３Ｄ点Ｆ＝｛ｐｉ，ｊ∈Ｒ３；ｉ＝１，．．．，Ｍ、ｊ＝１，．．．，Ｎ｝に容易に編成できるので、編成済みポイントクラウド（奥行画像又はｚマップデータのいずれか）に関して、簡単な均一なパラメータ化が使用される。ただし、２Ｄインデックス（ｉ，ｊ）及び（ｉ±１，ｊ±１）は、奥行不連続性がない限り、対応する点間の３Ｄ近接関係を反映する。そのようにして、各データ点のパラメータ化は直接、その２Ｄインデックス（ｉ，ｊ）になり、すなわち、式（１）からのフィッティング済みＴスプライン表面上のＱ（ｉ，ｊ）が、データ点ｐｉ，ｊに対応する。未編成ポイントクラウドＦの場合、ＰＣＡベースパラメータ化、すなわち、Ｆ＝｛（ｐｉ；ｕｉ，ｖｉ），ｐｉ∈Ｒ３，ｕｉ∈Ｒ，ｖｉ∈Ｒ；ｉ＝１，．．．，Ｍ｝であり、ただし、３Ｄ点ｐｉごとの式（１）への入力変数としての（ｕｉ，ｖｉ）パラメータは、２つの最も大きい固有値に対応する２つの固有ベクトルで張られた平面上にｐｉを投影することによって取得される。この定式は、パラメータ化されたポイントクラウド内の部分領域に適用可能であり、任意選択で、入力ポイントクラウドのプリセグメンテーションを使用することができ、本アルゴリズムを各セグメントに適用することができる。
【００４３】
いくつかの実施形態において、数多くの３Ｄセンサの未処理の出力は一組の２Ｄインデックス付き３Ｄに編成することができるので、未編成ポイントクラウド（奥行画像又はｚマップデータのいずれか）に関して、簡単な均一のパラメータ化を使用することができる。
【００４４】
適応的パッチ生成
本開示のいくつかの実施形態は、その多重度が、根底にあるＢスプライン基底関数の次数、すなわち、ｄ＋１に等しくなるまで、各ノットラインにおいて繰り返されるノット挿入を使用することによって、任意のＴスプライン表面を一組の独立したＢスプライン、又はより簡単に言うと、ベジェ表面に変換できるという認識に基づく。逆の手順において考えるとき、入力点のそれぞれを、固定ノットベクトルを有する簡単なＢスプラインによって、或いはベジェパッチによって十分に表すことができるまで、入力点をより小さいパッチに適応的に分割するとどうなるかを解析した。そうすると、共有されるノットラインにおいて、すなわち、パラメータ領域内の各パッチの境界において、全てのそのようなパッチを、適切な連続性を有する単一のＴスプラインになるように互いに構成するだけで十分である。
【００４５】
これが、以下のアルゴリズム２において説明される本発明の適応的パッチ生成につながる。本発明の表記に基づいて、未編成ポイントクラウドの場合、
【数２】
2019536162.tif 000005
であり、編成済みポイントクラウドの場合、
【数３】
2019536162.tif 000006
である。不要な初期パッチフィッティングを回避するために、ＩｎｉｔＳｐｌｉｔ関数によって、入力領域全体をいくつかの領域に均等に分割する。本実施態様では、常に、４×４ブロックから開始する。本開示の別の実施形態によれば、各領域に関する所定の面積比に従って、入力領域全体を分割することができる。
【表２】
2019536162.tif 000007
【００４６】
ＦｉｔＢｅｚｉｅｒＰａｔｃｈ関数は、領域ｒ内の全てのデータ点を取り込み、そのｒに関して規定されるベジェパッチｂをフィッティングする。これは、標準的なＱＲ又はコレスキー分解のいずれかを用いて以下の式を解くことによって行われる。
【数４】
2019536162.tif 000008
【００４７】
ここで、Ｐの各行はベジェ制御点を表す。領域ｒ内の入力データ点がＱの各行に記憶され、Ｂ行列の（ｉ，ｊ）エントリは、ｒ内の第ｉのデータ点のパラメータにおいて評価される第ｊの制御点のベジェ基底関数値を記憶する。
【００４８】
Ｂスプラインをフィッティングするのとは異なり、ベジェパッチのためのノットベクトルを求める必要はないことに留意されたい。それゆえ、Ｂ行列は、その領域ｒのサイズにのみ依存する。ＦｉｔＢｅｚｉｅｒＰａｔｃｈ関数は、Ｂの階数不足に起因して、最小二乗フィッティングを実行できない場合がある。これは通常、大きい細部変動を有する小さい領域において、又はあまりに多くの欠落データを有する領域において生じる。上記のシステムの階数を十分にするために、空のフィットｂを返し、対応するｒを無視するか、又はトレードオフパラメータλを用いて、制御点間に線形制約Ｓを加える。例示的な制約は、隣接する制御点が互いに近づくように単に強制するか、又はフィットが揺れ動くのを抑制するために、より高度なものとすることができる。
【００４９】
ＮｅｅｄＳｐｌｉｔ関数は、異なる基準を用いて、ｂがフィット不良であるか否かを、それゆえ、より小さい部分に更に分割される必要があるか否かを判断することができる。入力データが、あらゆる場所において同じ等方性誤差を有することが既知である場合には、この関数は、所定の閾値で、Ｌ∞フィッティング誤差をチェックすることができる。そうでない場合、例えば、奥行依存性誤差を有することが既知であるキネクトデータの場合、この関数は、動的な奥行依存性閾値で、フィッティング誤差をチェックすることができる。
【００５０】
ＣａｎＳｐｌｉｔ関数は、所与の領域ｒを更に分割できるか否かを検査する。本実施態様において、未編成ポイントクラウドの場合、その関数は常に真を返す。編成済みポイントクラウドの場合、分割された領域ｒ０及びｒ１が有効なベジェフィットを得るのに十分なデータを内部に有することができない場合には、すなわち、ｕｍａｘ−ｕｍｉｎ＋１及びｖｍａｘ−ｖｍｉｎ＋１がいずれも２ｄ＋１より小さい場合には、領域ｒは分割することはできない。これは、分割後に、結果として生成されたブロックが制御点より少ないデータ点を有することになり、その結果、式（２）において制約付きのフィッティングを実行しない限り、階数不足のシステムが生じるためである。パッチが分割される必要があるが、分割できない状況は、留意にするに値する。これは一般に、簡単なベジェ表面として表すことができない、あまりにも多くの細部を有する小さいブロックにおいて起こる。この状況を取り扱う２つの選択肢がある。すなわち、フィッティング誤差が、所定の誤差に比べて十分に小さくなるまで、そのベジェ表面上でＢスプライン精緻化を実行すること、又はこの小さいデータ部分を単に破棄することである。実施態様の一例として、それらの小さい細部は一般にセンサ雑音によって引き起こされ、それらを無視しても、多くの場合に、最終的なフィッティング結果を著しく損なうことはないので、後者が選択される。
【００５１】
Ｓｐｌｉｔ関数は異なる挙動を有することができる、すなわち、大きいベジェフィッティング誤差を有する場所において分割することができるか、又はフィッティング誤差分布に従って分割することができる。本実施態様では、良好なフィッティング結果を与える傾向がない疎らな領域を回避するために、その領域の長い方の側の中央において常に分割する。
【００５２】
局所ノットベクトル推定
アルゴリズム２の出力Ｂ、すなわち、一組のベジェパッチは基本的に、既に有効なＴスプラインであり、あらゆるノットラインの多重度が全てのベジェパッチの選択された次数、ｄ＋１に等しい。しかしながら、パッチの境界にわたって滑らかであることを確実にするために、表面パラメータ連続性を規定することが、より望ましい。上記で言及されたように、パラメータ領域内の全ての返されるパッチの境界は、本発明のＴスプラインフィッティングの場合に再生されるＴメッシュとして取り扱われ、それは、以下のステップにおいても固定されたままである。例えば、図２Ｂにおいて、３つのパッチｂ１、ｂ２及びｂ３から簡単なＴメッシュが生成される。しかしながら、Ｔメッシュの原画像、すなわち、いわゆる、インデックス／パラメータ空間内のＴメッシュが、局所ノットベクトルを推定するために依然として特定されることになる。これは、所望の表面モデルの所定のパラメータ連続性及び入力ポイントクラウドから得られるデータ連続性の両方を考慮して、Ｔメッシュの各エッジに異なる多重度を割り当てることができるためである。
【００５３】
アルゴリズム３は、局所ノットベクトルの推定に関して記述する。最初のステップは、関数ＢｕｉｌｄＭｅｓｈを用いて、全てのベジェパッチの境界から、面−エッジ−頂点で表されるメッシュＴｍｅｓｈを構築することである。このＴｍｅｓｈの頂点は、全てのパッチの角に対応する。このＴｍｅｓｈのエッジは、中間に任意の他の頂点を含まない全てのパッチの辺に対応する。このＴｍｅｓｈの面は全てのパッチに対応する。また、このＴｍｅｓｈは、図２Ｂに示されるように、ｕ方向において［・・・，ｕ１，ｕ２，ｕ３，・・・］として、ｖ方向において［・・・，ｖ１，ｖ２，ｖ３，・・・］としてその局所的ノット隣接要素を特定するために、頂点（ｕ２，ｖ２）からその上方向、下方向、左方向及び右方向に光線を放つ動作も可能にするはずである。
【００５４】
そのようなＴｍｅｓｈを構築した後に、ＦｉｎｄＥｄｇｅＭｕｌｔｉｐｌｉｃｉｔｙ関数が、Ｔｍｅｓｈ内の各エッジを調べ、そのエッジの両側に存在する２つの面／パッチ間の入力データ連続性を検査する必要がある。検査結果は、その後、そのエッジ内に記憶される。本発明の実施態様では、奥行依存性閾値を用いて、２つのパッチ間のデータ不連続性、すなわち、２つのパッチが互いに接続を断たれるか否かを検出する。これは多くの場合に、物体閉塞（object occlusion）が隣接する点間に大きい奥行差を生成するキネクトライクポイントクラウドにおいて生じる。Ｔメッシュ内でこの不連続を適切に取り扱わないと、結果として生じるＴスプラインは、接続を断たれた入力点をフィッティングするための表現能力が低下することになる。入力ポイントクラウドのプリセグメンテーションを使用する場合であっても、データ不連続性は各セグメント内に残存する場合があり、それゆえ、局所ノットベクトルを推定するときにノット多重度を追加するために、依然としてそのような検出を実行する必要があることに留意されたい。
【００５５】
最後に、このアルゴリズムは、Ｔｍｅｓｈ内の各頂点を調べ、ＧｅｎＬｏｃａｌＫｎｏｔＶｅｃｔｏｒ関数を用いて、その頂点に関連付けられる制御点のための一組の局所ノットベクトルを生成及び記憶する。これは、頂点の局所ノット隣接要素を見つける、上記で言及されたＴｍｅｓｈ演算の助けを借りて行われる。例えば、図２Ｂでは、破線エッジにおいて入力点の接続が断たれるので、このエッジは不連続として表示される。したがって、フィッティングされる表面モデルに関してＣ１連続性が規定される場合には、ＧｅｎＬｏｃａｌＫｎｏｔＶｅｃｔｏｒ関数が、図２Ｂのようなパラメータ空間内のソースＴメッシュから、図２Ｃのようなインデックス／パラメータ空間内のＴメッシュを生成する。同じ演算を用いて、青色破線円内の６つの接合部、すなわち、いわゆる、アンカーに対応する、頂点ｎに関する６対のノットベクトルを出力することができる。
【表３】
2019536162.tif 000009
【００５６】
制御点初期化及び精緻化
一般に、ベジェパッチフィッティングにおいて単に、境界制御点が強制的に共有されるようにしても、結果として、表面の滑らかさ又はフィッティング誤差のいずれかに関して最適なＴスプライン表面は生じない。アルゴリズム３から出力される一組の局所ノットベクトル（Ｕ、Ｖ）を用いてＴメッシュが発見されると、
【数５】
2019536162.tif 000010
として、最良の制御点位置を解くための疎線形システムを構築しなければならない。ただし、Ｔは行あたりのデータ点ごとに式（１）からのＴスプラインブレンディング関数値を保持するＭＮ×Ｋ行列であり、ＱはＴと同じ行順の行あたりの各入力データ点を保持するＭＮ×３行列であり、Ｃは、Ｔと同じ列順の行あたりの各未知の制御点を保持するＫ×３行列である（未編成ポイントクラウドの場合、Ｎ＝１）。
【００５７】
制御点の数及び入力データサイズがいずれも小さい場合には、この疎線形システムは、コレスキー又はＱＲ分解等の直接ソルバーを用いて解くことができる。しかしながら、問題サイズが大きいとき、直接ソルバーの使用は扱いにくいので、ＰＣＧ又は漸進的フィッティング（progressive fitting）等の反復ソルバーを使用することができる。したがって、高速計算のために反復数を削減する良好な初期化が必要になる。
【００５８】
アルゴリズム４は、関数ＡｓｓｉｇｎＲｅｌｅｖａｎｔ−ＣｏｎｔｒｏｌＰｏｉｎｔを示し、その関数は、その関連するベジェパッチＢ内の対応する制御点として各初期Ｔスプライン制御点を設定することを採用することができる。図２Ｃは１つのそのような例を示し、４つの小点がそれらのＴスプライン制御点のアンカーを示し、それらの小点はパッチｂ３に関連付けられる。このヒューリスティックな初期化後に、ＲｅｆｉｎｅＣｏｎｔｒｏｌＰｏｉｎｔｓ関数が、反復ソルバーを用いて、その初期推測を精緻化する。本発明の実施態様では、そのような精緻化のために、ヤコビ前処理（Jacobi preconditioner）を伴うＰＣＧを選択する。
【表４】
2019536162.tif 000011
【００５９】
本開示の実施形態によれば、上記のアルゴリズムを介して、フィッティング済みＴスプライン表面を取得した後に、Ｔスプライン表面がディスプレイデバイス１６５の画面モニター上に表示される。フィッティング済みＴスプライン表面のデータは、ユーザーの入力動作時に、又はネットワーク１５５を介した別のコンピュータ若しくは他のコンピュータからのデータ要求時に、ＷｉＦｉネットワークを含むネットワーク１５５を介してディスプレイデバイス又は他のコンピュータ（高速Ｔスプラインフィッティングシステム１００の外部にある）に送信することができる。
【００６０】
実験結果
２つの異なる適用例、すなわち、３Ｄポイントクラウド及び画像データにＴスプラインをフィッティングする際のいくつかのデータセットにわたる本発明のＦａｓＴＦｉｔアルゴリズムの速度及び精度を評価した。編成済み３Ｄポイントクラウド、すなわち、キネクトライク及びｚマップライク編成済みポイントクラウド、並びに未編成ポイントクラウドの３種類を検討する。キネクトポイントクラウドの場合、点間のユークリッド距離に基づく簡単なプリセグメンテーションを使用し、本発明のアルゴリズムを各セグメントに適用した。このセグメントベース手法によれば、ポイントクラウド全体に対して単一のＴスプラインをフィッティングするより、制御点の数が少なくなり、それゆえ、計算が高速になることがわかった。画像データの場合、画像全体に対して単一のＴスプラインをフィッティングした。４．０ＧＨｚのインテルＣｏｒｅ  ｉ７ＣＰＵを備える標準的なデスクトップＰＣにおいて、ＯｐｅｎＭＰ並列化を伴うＣ＋＋においてアルゴリズムを実施し、全ての実験を行った。
【００６１】
図４は、いくつかの異なるシーンの場合の本発明のアルゴリズムと、ＫｉｎＦｕ、すなわち、キネクトフュージョンのオープンソース実施態様との間の定性的比較を示す。
【００６２】
第１の行は、未処理の入力ポイントクラウドを示す。第２の行は、複数のポイントクラウドを融合することによって、ＫｉｎＦｕで得られた結果を示す。これは、複数のフレーム間の正確な位置合わせを必要とし、第２の列のように位置合わせが正確でない場合には、品質が劣化することに留意されたい。第３の行は、単一の入力ポイントクラウドの異なるセグメントにＣ２  Ｔスプライン表面をフィッティングすることによって、本開示の実施形態による本発明の結果を示す。第４の行は、異なる色において示される、ポイントクラウドセグメントにわたるフィッティング済みＴメッシュを示す。正確な位置合わせを仮定すると、その表面再構成品質は、ＫｉｎＦｕの品質に相当する。
【００６３】
３Ｄポイントクラウド
第１の適用例は、３Ｄポイントクラウドの各単一フレームにわたってＴスプライン表面をフィッティングすることである。本発明の方法と２つの関連する従来の方法との間の定量的比較及び定性的比較の両方を実行した。
【００６４】
反復方式との定量的比較
小領域ノット挿入（ＳＫＩ：subregional knot insertion）は、反復方式に従う編成済み入力データのためのＴスプラインフィッティング方法のうちの１つである。各メッシュ精緻化反復において、その方法は、入力データ全体をいくつかの小領域（一組のパッチ）に均等に分割する。言い換えると、分割処理プロセスによって、パラメータ化領域を一組のパッチに均等に分割する。さらに、場合によっては、分割処理が、いくつかの小領域（一組のパッチ）に不均等に分割する場合がある。小領域の数は、反復とともに二次的に増加する。その際、最大フィッティング二乗平均平方根誤差（ＲＭＳＥ：root-mean-squared-error）を有する小領域の一定のパーセンテージが選択され、そのパーセンテージは挿入比α％と呼ばれる。言い換えると、分割処理は、最大フィッティングＲＭＳＥを用いて、分割処理パーセンテージ（挿入比α％）に基づいて実行される。例えば、分割処理パーセンテージは、０．１％〜１％の範囲内のノット挿入比とすることができる。
【００６５】
その後、選択された小領域ごとに、その選択された小領域内部に最大フィッティング誤差を有するデータ点を含むＴメッシュ面の中心にノットが挿入される。最後に、この新たなＴスプラインの制御点位置を最適化するために、ＰＣＧの代わりに、漸進的フィッティングアルゴリズム。
【００６６】
キネクトポイントクラウドフィッティングを本発明のＦａｓＴＦｉｔ方式と比較するために、α％＝０．１を用いて、ＳＫＩ方式を実施した。
【００６７】
特定の疎線形システム解法アルゴリズムの代わりに、反復フィッティング方式対非反復フィッティング方式を比較することに留意されたい。この実験において、式（３）の線形システムが、ＳＫＩ及びＦａｓＴＦｉｔの両方に関してＰＣＧによって解かれた。
【００６８】
この比較に関して、３つの不可欠な統計値、すなわち、フィッティング時間、ＲＭＳＥ及び制御点の数がある。それらの統計値はそれぞれ、フィッティング方式の速度、品質及びモデル簡潔性を表す。６つのフィッティング構成、すなわち、Ｃ３１、ＳＫＩ−Ｃ３１ＣＴＲＬ、ＳＫＩ−Ｃ３１ＲＭＳＥ、Ｃ３２、ＳＫＩ−Ｃ３２ＣＴＲＬ、ＳＫＩ−Ｃ３２ＲＭＳＥが設計された。Ｃ３１（１の所定のノット多重度を有する３次スプライン）及びＣ３２（２のノット多重度を有する３次）構成はそれぞれ、Ｃ２及びＣ１の所定の表面連続性を有するＦａｓＴ−Ｆｉｔを使用する。他の全ての構成は、ＳＫＩを適用し、ＳＫＩのメッシュ精緻化反復に関して異なる中止条件を用いてＣ２表面をフィッティングする。ＳＫＩ−Ｃ３１ＣＴＲＬは、制御点の数が本発明のＣ３１フィットの制御点の数以上になると、そのメッシュ精緻化を中止し、一方、ＳＫＩ−Ｃ３１ＲＭＳＥは、現在のフィッティングＲＭＳＥが本発明のＣ３１フィッティングのＲＭＳＥ以下になると中止し、ＳＫＩ−Ｃ３２ＣＴＲＬ及びＳＫＩ−Ｃ３２ＲＭＳＥは、Ｃ３２フィットの制御点の数及びＲＭＳＥの場合に同様に規定される。
【００６９】
通常の屋内シーンにわたってＶＧＡサイズのキネクトポイントクラウドの１２００を超える数のフレームを収集し、これらのポイントクラウドにわたって６回の実験を実行した。その結果が表１に要約され、その表からＦａｓＴＦｉｔの以下の利点を観測することができる。
【００７０】
フィッティング速度
ＦａｓＴＦｉｔは、ＳＫＩより少なくとも１０倍〜１５倍速く動作する。ＦａｓＴＦｉｔのステップごとの処理時間が表２に示される。表１にセグメンテーション時間は含まれないことに留意されたい。
【表５】
2019536162.tif 000012
【表６】
2019536162.tif 000013
【００７１】
品質
ＳＫＩが同じレベルの制御点数において中止されるとき、ＦａｓＴＦｉｔの結果として、同等のフィッティングＲＭＳＥが生じる（表１内のＣ３１に対するＳＫＩ−Ｃ３１ＣＴＲＬのＲＭＳＥの差は０．２％未満である）。ノット挿入に起因して、ＳＫＩはＦａｓＴＦｉｔ内の制御点と厳密に同じ数において中止できないので、ＳＫＩ−Ｃ３１ＣＴＲＬの制御点の平均数は、Ｃ３１の平均数よりわずかに多い。そのような条件下であっても、約２９％の事例において、Ｃ３１がＳＫＩ−Ｃ３１ＣＴＲＬより小さいＲＭＳＥを有する。
【００７２】
コンパクト性
ＳＫＩが同じレベルのＲＭＳＥにおいて中止されるとき、ＦａｓＴＦｉｔの結果として、大抵の場合に、制御点の数が少なくなる（表１内のＣ３１に対するＳＫＩ−Ｃ３１ＲＭＳＥの制御点の数を比較）。同様に、ＳＫＩはＦａｓＴＦｉｔと厳密に同じＲＭＳＥにおいて中止できないので、ＳＫＩ−Ｃ３１ＲＭＳＥの平均ＲＭＳＥは、Ｃ３１の平均ＲＭＳＥよりわずかに小さい。
【００７３】
それゆえ、ＦａｓＴＦｉｔは、ＳＫＩと同等であるか、又はＳＫＩより良好である品質及び簡潔性で、より効率的に表面表現を与える。本開示の実施形態によるＦａｓＴＦｉｔの利点は、反復メッシュ精緻化に時間を費やすことなく、適切なＴメッシュを効率的に発見することができ、結果として生じるＴスプラインが、以下の定性的比較において確認できるように、満足のいく表面フィットであることである。この特徴は、計算機能の改善を提供し、計算タスクに関する電力消費量を削減する。
【００７４】
定性的比較
表面フィッティングの品質を評価するために、ＳＫＩに加えて、本発明の結果を、打切り符号付き距離フィールド（ＴＳＤＦ：truncated signed distance field）において複数のポイントクラウドを融合することによって従来の表面再構成品質のうちの１つを提供するＫｉｎＦｕ、すなわち、キネクトフュージョンのオープンソース実施態様によって得られた結果と比較する。
【００７５】
図４はその比較を示し、その比較では、ＫｉｎＦｕにおいて実現されるのと同じシェーディングパイプラインを用いて全ての結果を視覚化する。本発明のアルゴリズムは、単一のフレームしか使用しなくても、ＫｉｎＦｕと同等の高品質の表面再構成を提供する。また、本発明の表現は、図４のＴメッシュ視覚化において示されるように、固定ボクセル分解能を有するＴＳＤＦ表現に比べて、コンパクトであることにも留意されたい。
【００７６】
Ｚマップ／ポイントクラウド
ｚマップライク３Ｄポイントクラウドに関するＦａｓＴＦｉｔが、既知のピュージェット湾地形のデジタル標高マップ（ＤＥＭ：digital elevation map）の拡張バージョン（１００ｍのピクセル間間隔及び０．５ｍのピクセル単位を有する１０２５×１０２５ピクセル）を用いて評価される。図５Ａ及び図５Ｂは、本開示の一実施形態による、ＳＫＩ法とＦａｓＴｆｉｔ法との比較を示す。この場合、反復方式は、著しく多い数の制御点に起因して、ＦａｓＴＦｉｔよりはるかに（４桁）遅い速度で動作し、その結果として、最大ＲＭＳＥ領域を含むＴメッシュ面の探索、形状保存制御点挿入、及び各反復におけるＴメッシュの保持に関する計算コストによって、ＳＫＩ、すなわち、反復方式は更に低速になることに留意されたい。行１は概観を示す。行２及び行３は詳細な図を示す。行４は凡例及びＴメッシュを示す。メッシュはフィッティング誤差を示す。図５Ｂは、ＳＫＩ法と比べて、ＦａｓＴＦｉｔが４桁高速であり、同等の表面をフィッティングすることを示す実験結果である。
【００７７】
また、１０〜５０の範囲の次数（degree）の異なるランダムベジェ表面から生成される４１個の異なるｚマップポイントクラウド（１×１×１．２ｍ３の領域内の３００×３００点）のデータセットをシミュレートする。これに基づいて、見逃したデータ点、不連続性及び等方性ガウス雑音（０．００３ｍ標準偏差）を追加することによって、３つのデータベースを更にシミュレートする。これらのシミュレートされたデータセット（全部で１６４のポイントクラウド）に関するＳＫＩ法との比較が表３に示される。
【表７】
2019536162.tif 000014
【００７８】
図６Ａ及び図６Ｂは典型的なフィッティング結果を示し、その結果は、ＦａｓＴＦｉｔのフィッティング効率及び品質を実証し、特に、ＦｉｎｄＫｎｏｔＭｕｌｔｉｐｌｉｃｉｔｙを通してデータ不連続性を考慮する利点を実証する。
【００７９】
未編成ポイントクラウド
ＳＬＡＭシステムを用いて、複数のダウンサンプリングされたキネクトポイントクラウドを位置合わせすることによって取り込まれた未編集３Ｄポイントクラウドに関してＦａｓＴＦｉｔを更に評価する。ここでは、スキャンされたシーンからの物体を手作業でセグメント化し、上記のようなＰＣＡベース法及び単一のＴスプライン表面を用いて、物体ポイントクラウドをパラメータ化した。図７は、上から下に、未処理点、フィッティング済みＴスプライン及びＴメッシュに対応する、未編成ポイントクラウドをフィッティングする例を示す。
【００８０】
画像データ
第２の適用例は、カラー画像に関してＲＧＢ空間内でＴスプラインをフィッティングすることであり、その結果は、ズーム処理及び幾何学的変換等の、種々の画像プロセスアルゴリズムを助けることができる。
【００８１】
図８は、２つの元の画像と、対応する画像フィッティング結果を有するＣ３２  Ｔメッシュ結果及びＳＫＩ−Ｃ３２ＣＴＲＬ  Ｔメッシュ結果とを示す。それらの画像は、フィッティング結果及び対応するＴメッシュから再構成される。元の画像と、ＦａｓＴＦｉｔ及びＳＫＩの両方からのフィッティング済み画像との間の違いは、ほとんど目に見えない。元の画像、Ｃ３２画像フィッティング結果及びＳＫＩ−Ｃ３２ＣＴＲＬ画像フィッティング結果を示す図８を参照されたい。ＳＫＩに関する時間を節約するために、この場合、形状保存制御点挿入を適用しなかったことに留意されたい。
【００８２】
表４はフィッティング統計値を示す。Ｌｅｎａの事例では、ＲＭＳＥをＳＫＩ−Ｃ３１ＣＴＲＬ及びＣ３１未満に低減する前に最大反復に達するので、ＳＫＩ−Ｃ３１ＲＭＳＥはＳＫＩ−Ｃ３１ＣＴＲＬと同じ結果を有する。全ての事例において、ＦａｓＴＦｉｔは、類似の画像再構成品質をもたらしながら、ＳＫＩより著しく高速である。本発明のＦａｓＴＦｉｔ及び元のＳＫＩ実施態様はいずれも並列化のためにＯｐｅｎＭＰを使用することに留意されたい。ＦａｓＴＦｉｔのＰＳＮＲはＳＫＩのＰＳＮＲよりわずかに小さい場合であっても、画像がキネクトライクポイントクラウドより多くのデータ不連続を有する傾向があるので、場合によってはＦａｓＴＦｉｔがはるかに多くの制御点を有し、計算速度を優先するためにＦａｓＴＦｉｔにおいてトレードオフが行われた。
【表８】
2019536162.tif 000015
【００８３】
上記のように、新規のＴスプラインフィッティング方式は、ＶＧＡサイズのキネクトデータ等の大きいポイントクラウドを効率的、かつ正確にモデル化することができる。それぞれが独立したベジェパッチによって忠実に表現できるまで、入力ポイントクラウドをより小さい部分に適応的に分割することによって、反復ノット精緻化及び制御点調整を用いることなく、適切なＴメッシュが効率的に発見される。その後、入力データにおいて明らかにされたパッチ境界にわたる表面連続性を考慮する異なるパッチ接続選択肢を通して、Ｔメッシュ上で全ての制御点に関する局所ノットベクトルが推定される。フィッティング済みベジェパッチに基づく、全ての制御点のヒューリスティックな初期化を通して、制御点精緻化を効率的に実行することができ、それにより、入力ポイントクラウドに関する本発明によるフィッティング済みＴスプラインモデルがもたらされる。本開示の実施形態による結果は、複数のフレームを融合した後にキネクトフュージョンによって生成される結果と比べて、単一フレームキネクトポイントクラウドデータに関して同等か、場合によっては更に良好な表面再構成を示す。
【００８４】
本開示の実施形態によるアルゴリズムは、平均で４００ｍｓ未満の処理時間で、ＶＧＡサイズのキネクトデータに関して概ねリアルタイムの性能を与えることができる。画像データフィッティングに関して、本発明のアルゴリズムは、公表されている最新技術の結果より少なくとも１桁速い処理時間を達成した。そのような高速の処理速度は、数多くのダウンストリームアプリケーションに利益を与えることができる。
【００８５】
従来の反復フィット及び精緻化パラダイムから転換することによって、本発明は、このタスクをより効率的に実行する新規のアルゴリズムを提示する。ポイントクラウドを一組のＢスプラインパッチに適応的に分割することを通して、本発明は最初に、Ｔスプライン制御点の適切なトポロジー、すなわち、Ｔメッシュを発見する。その後、本発明は、これらのＢスプラインパッチを接続して、データに応じて隣接するパッチ間で異なる連続性を有する単一のＴスプライン表面にする。Ｔスプライン制御点はＢスプラインパッチにおけるそれらの対応からヒューリスティックに初期化され、それらの制御点は共役勾配法を使用することによって精緻化される。本発明の実験は、提案されるアルゴリズムのＣＰＵ実施態様が、合理的な数の制御点を有するＶＧＡサイズのキネクトポイントクラウドにわたってＴスプラインを４００ｍｓ以内に効率的にフィッティングできることを実証し、その時間は最新技術のアルゴリズムより少なくとも２桁速い。したがって、本開示の実施形態によるＴスプライン表現を用いてシーンのポイントクラウドを表現するシステム及び方法は、コンピュータを用いて、計算コストを著しく削減することができ、シーン物体内の画像のデータ処理を改善することができる。
【００８６】
本開示の実施形態によれば、プロセッサと接続されるメモリ又はコンピュータ可読記録媒体に記憶されるプログラムのアルゴリズムは、制御処理ユニット使用量、及びプロセッサの電力消費量を削減することができる。
【００８７】
本開示の上記で説明した実施形態は、多数の方法のうちの任意のもので実施することができる。例えば、実施形態は、ハードウェア、ソフトウェア又はそれらの組み合わせを用いて実施することができる。ソフトウェアで実施される場合、ソフトウェアコードは、単一のコンピュータに設けられるのか又は複数のコンピュータ間に分散されるのかにかかわらず、任意の適したプロセッサ又はプロセッサの集合体において実行することができる。そのようなプロセッサは、１つ以上のプロセッサを集積回路部品に有する集積回路として実装することができる。ただし、プロセッサは、任意の適したフォーマットの回路類を用いて実装することができる。
【００８８】
また、本明細書において略述された様々な方法又はプロセスは、様々なオペレーティングシステム又はプラットフォームのうちの任意の１つを用いる１つ以上のプロセッサ上で実行可能なソフトウェアとしてコード化することができる。加えて、そのようなソフトウェアは、複数の適したプログラミング言語及び／又はプログラミングツール若しくはスクリプティングツールのうちの任意のものを用いて記述することができ、実行可能機械語コード、又はフレームワーク若しくは仮想機械上で実行される中間コードとしてコンパイルすることもできる。通常、プログラムモジュールの機能は、様々な実施形態において所望に応じて組み合わせることもできるし、分散させることもできる。
【００８９】
また、本開示の実施形態は、方法として具現化することができ、この方法の一例が提供されている。この方法の一部として実行される動作は、任意の適した方法で順序付けることができる。したがって、例示したものと異なる順序で動作が実行される実施形態を構築することができ、この順序は、いくつかの動作が例示の実施形態では順次的な動作として示されていても、それらの動作を同時に実行することを含むことができる。さらに、請求項の要素を修飾する、特許請求の範囲における第１、第２等の序数の使用は、それ自体で、１つの請求項の要素の別の請求項の要素に対する優先順位も、優位性も、順序も暗示するものでもなければ、方法の動作が実行される時間的な順序も暗示するものでもなく、請求項の要素を区別するために、単に、或る特定の名称を有する１つの請求項の要素を、同じ（序数の用語の使用を除く）名称を有する別の要素と区別するラベルとして用いられているにすぎない。
【図１Ａ】
2019536162.tif 000016
【図１Ｂ】
2019536162.tif 000017
【図２Ａ】
2019536162.tif 000018
【図２Ｂ】
2019536162.tif 000019
【図２Ｃ】
2019536162.tif 000020
【図３Ａ】
2019536162.tif 000021
【図３Ｂ】
2019536162.tif 000022
【図４】
2019536162.tif 000023
【図５Ａ】
2019536162.tif 000024
【図５Ｂ】
2019536162.tif 000025
【図６Ａ】
2019536162.tif 000026
【図６Ｂ】
2019536162.tif 000027
【図７】
2019536162.tif 000028
【図８】
2019536162.tif 000029
【手続補正書】
【提出日】令和1年5月17日(2019.5.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
３Ｄセンサ１１６を用いてシーンの３Ｄポイントクラウドを取り込み始めるために、キーボード１１１、ポインティングデバイス／媒体１１２を用いて、又は他のコンピューター１９５に接続されるワイヤレスネットワーク若しくはネットワーク１５５を介して、システム１００に命令を送信することができる。３Ｄポイントクラウドの取り込みは、記憶装置１３０内に記憶されるプリインストールされた従来の音声認識プログラムを用いて、マイクロフォン１１３を介してユーザーの音響信号を受信するのに応答して開始することができる。さらに、高速Ｔスプラインフィッティングシステム１００は、ネットワーク１５５を介して、他のコンピューター１９５から３Ｄポイントクラウドのデータを受信することができ、３Ｄポイントクラウドの受信データを用いて、高速Ｔスプラインフィッティングを実行することができる。システム１００は、高速Ｔスプラインフィッティングプロセスの結果として生成されたデータを、ネットワーク１５５を介して他のコンピューター１９５に送信することができる。
【国際調査報告】
2019536162.tif 000030
2019536162.tif 000031
2019536162.tif 000032
2019536162.tif 000033