(57)【要約】      （修正有）【課題】ノイズポイントを含まずに、関節運動可能な部分に関連付けられたポイントクラウドを出力できるコンピュータ実装方法および装置を提供する。【解決手段】方法は、関節運動可能な部分の関節運動前の物理的オブジェクトに関連付けられた第１の３Ｄポイントクラウド及び関節運動可能な部分の関節運動後の第２の３Ｄポイントクラウドを取得することと、第１及び第２のポイントクラウドを位置合わせし第２のポイントクラウド内のポイントに対する第１のポイントクラウド内の最近傍のポイントを見つけることと、第２のポイントクラウド内の残りのポイントが関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように第２のポイントクラウド内の最近傍のポイントを排除することと、ノイズポイントを含まずに関節運動可能な部分に関連付けられた第２のポイントクラウドの残りのポイントを含む出力を生成することと、を含む。【選択図】図１
2020109626.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ実装方法であって、
少なくとも１つの関節運動可能な部分を有する物理的オブジェクトに関連付けられた第１の３次元ポイントクラウドを取得することであって、前記第１のポイントクラウドが、前記関節運動可能な部分の関節運動前の前記物理的オブジェクトに関連付けられている、ことと、
前記関節運動可能な部分の関節運動後の前記物理的オブジェクトに関連付けられた第２の３次元ポイントクラウドを取得することと、
前記第１及び第２のポイントクラウドを位置合わせすることと、
前記第２のポイントクラウド内のポイントに対する前記第１のポイントクラウド内の最近傍のポイントを見つけることと、
前記第２のポイントクラウド内の残りのポイントが前記関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように、前記第２のポイントクラウド内の前記最近傍のポイントを排除することと、
前記ノイズポイントを含まずに、前記関節運動可能な部分に関連付けられた前記第２のポイントクラウドの少なくとも前記残りのポイントを含む出力を生成することと、を含む、方法。
【請求項２】
前記第１及び第２のポイントクラウドを位置合わせすることが、
前記第１及び第２のポイントクラウドを粗く位置合わせすることと、
前記第１及び第２のポイントクラウドを粗く位置合わせした後に、前記第１及び第２のポイントクラウドを細かく位置合わせすることと、を含む、請求項１に記載の方法。
【請求項３】
前記第１及び第２のポイントクラウドを粗く位置合わせすることが、
前記第１及び第２のポイントクラウドから高速点特徴ヒストグラム（ＦＰＦＨ）記述子を計算することと、
前記第１及び第２のポイントクラウドの前記ＦＰＦＨ記述子を使用して前記第１のポイントクラウドと前記第２のポイントクラウドとの間のランダムサンプルコンセンサス（ＲＡＮＳＡＣ）レジストレーションを実行することと、を含む、請求項２に記載の方法。
【請求項４】
前記ＦＰＦＨ記述子を計算する前に、前記第１及び第２のポイントクラウドをダウンサンプリングすることを含む、請求項３に記載の方法。
【請求項５】
前記第１及び第２のポイントクラウドを細かく位置合わせすることが、前記粗く位置合わせされた前記第１及び第２のポイントクラウド上で反復最近傍点（ＩＣＰ）レジストレーションを実行することを含む、請求項２に記載の方法。
【請求項６】
前記第２のポイントクラウド内の前記残りのポイントにクラスタリングを適用して、ノイズポイントクラスタ、及び前記関節運動可能な部分に関連付けられたポイントのクラスタを生成することと、
前記関節運動可能な部分に関連付けられた前記ポイントのクラスタを前記ノイズポイントクラスタと区別することと、を更に含み、
前記生成された出力が、前記ノイズポイントクラスタを含まずに、前記関節運動可能な部分に関連付けられた少なくとも前記ポイントのクラスタを含む、請求項１に記載の方法。
【請求項７】
前記関節運動可能な部分に関連付けられた前記ポイントのクラスタを前記ノイズポイントクラスタと区別することが、
前記第１のポイントクラウド内の前記関節運動可能な部分の場所を識別するユーザ入力を受信することと、
前記ユーザ識別された場所にあるポイントのクラスタを、前記関節運動可能な部分に関連付けられた前記ポイントのクラスタとして選択することと、を含む、請求項６に記載の方法。
【請求項８】
前記関節運動可能な部分に関連付けられた前記ポイントのクラスタを前記ノイズポイントクラスタと区別することが、
前記ポイントのクラスタのそれぞれのサイズをアルゴリズム的に判定することと、
最大のポイントのクラスタを、前記関節運動可能な部分に関連付けられた前記ポイントのクラスタとして選択することと、を含む、請求項６に記載の方法。
【請求項９】
クラスタリングを適用することが、ノイズを有するアプリケーションの密度ベースの空間クラスタリング（ＤＢＳＣＡＮ）を前記第２のポイントクラウド内の前記残りのポイントに適用することを含む、請求項６に記載の方法。
【請求項１０】
前記最近傍のポイントを見つけることが、ｋ次元ツリー（ｋ−ｄツリー）及び所定の距離閾値を使用して、前記第２のポイントクラウド内のポイントに対する前記第１のポイントクラウド内の前記最近傍のポイントを見つけることを含む、請求項１に記載の方法。
【請求項１１】
前記生成された出力が、前記第１のポイントクラウド上に重ね合わせられた前記関節運動可能な部分に関連付けられた前記第２のポイントクラウドのポイントを含む、請求項１に記載の方法。
【請求項１２】
前記出力が、グラフィック出力及びデータ構造出力の一方又は両方を含む、請求項１に記載の方法。
【請求項１３】
装置であって、
入力インターフェース及び出力インターフェースであって、前記入力インターフェースが、
少なくとも１つの関節運動可能な部分を有する物理的オブジェクトに関連付けられた第１の３次元ポイントクラウドであって、前記第１のポイントクラウドが、前記関節運動可能な部分の関節運動前の前記物理的オブジェクトに関連付けられている、第１の３次元ポイントクラウドと、
前記関節運動可能な部分の関節運動後の前記物理的オブジェクトに関連付けられた第２の３次元ポイントクラウドと、を受信するように構成されている、入力インターフェース及び出力インターフェースと、
前記入力インターフェースに動作可能に連結され、かつ前記第１及び第２のポイントクラウド並びにプログラムコードを記憶するように構成されたメモリと、
前記入力インターフェース、前記出力インターフェース、及び前記メモリに動作可能に連結されたプロセッサであって、前記プログラムコードが、前記プロセッサによって実行されると、前記プロセッサに、
前記第１及び第２のポイントクラウドを位置合わせさせ、
前記第２のポイントクラウド内のポイントに対する前記第１のポイントクラウド内の最近傍のポイントを見つけさせ、
前記第２のポイントクラウド内の残りのポイントが前記関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように、前記第２のポイントクラウド内の前記最近傍のポイントを排除させ、
前記ノイズポイントを含まずに、前記関節運動可能な部分に関連付けられた前記第２のポイントクラウドの少なくとも前記残りのポイントを含む出力を生成させ、
前記出力を前記出力インターフェースに伝達させる、プロセッサと、を備える、装置。
【請求項１４】
前記プロセッサが、
前記第１及び第２のポイントクラウドを粗く位置合わせし、
前記第１及び第２のポイントクラウドを粗く位置合わせした後に、前記第１及び第２のポイントクラウドを細かく位置合わせする、ように構成されている、請求項１３に記載の装置。
【請求項１５】
前記プロセッサが、
前記第１及び第２のポイントクラウドから高速点特徴ヒストグラム（ＦＰＦＨ）記述子を計算することと、
前記第１及び第２のポイントクラウドの前記ＦＰＦＨ記述子を使用して前記第１のポイントクラウドと前記第２のポイントクラウドとの間のランダムサンプルコンセンサス（ＲＡＮＳＡＣ）レジストレーションを実行することと、によって、前記第１及び第２のポイントクラウドを粗く位置合わせするように構成されている、請求項１４に記載の装置。
【請求項１６】
前記プロセッサが、前記ＦＰＦＨ記述子を計算する前に、前記第１及び第２のポイントクラウドをダウンサンプリングするように構成されている、請求項１５に記載の装置。
【請求項１７】
前記プロセッサが、前記粗く位置合わせされた前記第１及び第２のポイントクラウド上で反復最近傍点（ＩＣＰ）レジストレーションを実行することによって、前記第１及び第２のポイントクラウドを細かく位置合わせするように構成されている、請求項１４に記載の装置。
【請求項１８】
前記プロセッサが、
前記第２のポイントクラウド内の前記残りのポイントにクラスタリングを適用して、ノイズポイントクラスタ、及び前記関節運動可能な部分に関連付けられたポイントのクラスタを生成し、
前記関節運動可能な部分に関連付けられた前記ポイントのクラスタを前記ノイズポイントクラスタと区別する、ように構成されており、
前記プロセッサによって生成された前記出力が、前記ノイズポイントクラスタを含まずに、前記関節運動可能な部分に関連付けられた少なくとも前記ポイントのクラスタを含む、請求項１３に記載の装置。
【請求項１９】
前記プロセッサが、
前記第１のポイントクラウド内の前記関節運動可能な部分の場所を識別するユーザ入力を受信することと、
前記ユーザ識別された場所にあるポイントのクラスタを、前記関節運動可能な部分に関連付けられた前記ポイントのクラスタとして選択することと、によって、前記関節運動可能な部分に関連付けられた前記ポイントのクラスタを前記ノイズポイントクラスタと区別するように構成されている、請求項１８に記載の装置。
【請求項２０】
前記プロセッサが、
前記ポイントのクラスタのそれぞれのサイズをアルゴリズム的に判定することと、
最大のポイントのクラスタを、前記関節運動可能な部分に関連付けられた前記ポイントのクラスタとして選択することと、によって、前記関節運動可能な部分に関連付けられた前記ポイントのクラスタを前記ノイズポイントクラスタと区別するように構成されている、請求項１８に記載の装置。
【請求項２１】
前記プロセッサが、ノイズを有するアプリケーションの密度ベースの空間クラスタリング（ＤＢＳＣＡＮ）を前記第２のポイントクラウド内の前記残りのポイントに適用するように構成されている、請求項１８に記載の装置。
【請求項２２】
前記プロセッサが、前記第２のポイントクラウド内のポイントに対する前記第１のポイントクラウド内の前記最近傍のポイントを見つけるために、ｋ次元ツリー（ｋ−ｄツリー）及び所定の距離閾値を使用して前記最近傍のポイントを見つけるように構成されている、請求項１３に記載の装置。
【請求項２３】
前記プロセッサによって生成された前記出力が、前記第１のポイントクラウド上に重ね合わせられた前記関節運動可能な部分に関連付けられた前記第２のポイントクラウドのポイントを含む、請求項１３に記載の装置。
【請求項２４】
前記プロセッサによって生成された前記出力が、グラフィック出力及びデータ構造出力の一方又は両方を含む、請求項１３に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示の実施形態は、少なくとも１つの関節運動可能な部分を有する物理的オブジェクトに関連付けられた第１の３次元ポイントクラウドを取得することを含むコンピュータ実装方法を対象とする。第１のポイントクラウドは、関節運動可能な部分の関節運動前の物理的オブジェクトに関連付けられている。方法は、関節運動可能な部分の関節運動後の物理的オブジェクトに関連付けられた第２の３次元ポイントクラウドを取得することを含む。方法はまた、第１及び第２のポイントクラウドを位置合わせすることと、第２のポイントクラウド内のポイントに対する第１のポイントクラウド内の最近傍のポイントを見つけることと、を含む。方法は、第２のポイントクラウド内の残りのポイントが、関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように、第２のポイントクラウド内の最近傍のポイントを排除することを更に含む。方法はまた、ノイズポイントを含まずに、関節運動可能な部分に関連付けられた第２のポイントクラウドの少なくとも残りのポイントを含む出力を生成することも含む。
【０００２】
本開示の実施形態は、入力インターフェース及び出力インターフェースを備える装置を対象とする。入力インターフェースは、少なくとも１つの関節運動可能な部分を有する物理的オブジェクトに関連付けられた第１の３次元ポイントクラウドを受信するように構成されている。第１のポイントクラウドは、関節運動可能な部分の関節運動前の物理的オブジェクトに関連付けられている。入力インターフェースはまた、関節運動可能な部分の関節運動後の物理的オブジェクトに関連付けられた第２の３次元ポイントクラウドを受信するようにも構成されている。メモリが、入力インターフェースに動作可能に連結されており、第１及び第２のポイントクラウド並びにプログラムコードを記憶するように構成されている。プロセッサが、入力インターフェース、出力インターフェース、及びメモリに動作可能に連結されている。プログラムコードは、プロセッサによって実行されると、プロセッサに、第１及び第２のポイントクラウドを位置合わせさせ、第２のポイントクラウド内のポイントに対する第１のポイントクラウド内の最近傍のポイントを見つけさせ、第２のポイントクラウド内の残りのポイントが、関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように、第２のポイントクラウド内の最近傍のポイントを排除させ、ノイズポイントを含まずに、関節運動可能な部分に関連付けられた第２のポイントクラウドの少なくとも残りのポイントを含む出力を生成させ、出力を出力インターフェースに伝達させる。
【図面の簡単な説明】
【０００３】
【図１】様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの関節運動可能な部分を識別するためのコンピュータ実装方法を示すフロー図である。
【図２】様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの多数の関節運動可能な部分を識別するためのコンピュータ実装方法を示すフロー図である。
【図３】様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの１つ以上の関節運動可能な部分を識別するためのシステム及び方法を示す。
【図４】様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの関節運動可能な部分を識別するためのコンピュータ実装方法を示すフロー図である。
【図５Ａ】様々な実施形態による、関節運動していない構成及び関節運動した構成でレーザプリンタを３Ｄスキャンすることに基づいて作成されたポイントクラウドの画像である。
【図５Ｂ】様々な実施形態による、関節運動していない構成及び関節運動した構成でレーザプリンタを３Ｄスキャンすることに基づいて作成されたポイントクラウドの画像である。
【図５Ｃ】様々な実施形態による、関節運動していない構成及び関節運動した構成でレーザプリンタを３Ｄスキャンすることに基づいて作成されたポイントクラウドの画像である。
【図６Ａ】様々な実施形態による、関節運動していない構成及び関節運動した構成でのレーザプリンタの位置合わせされていないポイントクラウドの重ね合わせを示す画像である。
【図６Ｂ】様々な実施形態による、図６Ａに示されるポイントクラウドの粗い位置合わせを示す画像である。
【図６Ｃ】様々な実施形態による、図６Ｂに示される粗く位置合わせされたポイントクラウドの細かい位置合わせを示す画像である。
【図７Ａ】様々な実施形態による、最近傍排除の結果として得られる重ね合わせられたポイントクラウドの図を示す２つの画像である。
【図７Ｂ】様々な実施形態による、最近傍排除の結果として得られる重ね合わせられたポイントクラウドの図を示す２つの画像である。
【図８Ａ】様々な実施形態による、関節運動可能な部分の関節運動前の、レーザプリンタの元のポイントクラウドを示す画像である。
【図８Ｂ】様々な実施形態による、最近傍排除後にポイントクラウドのクラスタリングを実行した結果を示す画像である。
【図８Ｃ】様々な実施形態による、ポイントクラウドのクラスタリングを実行した後の、関節運動可能な部分に対応する残りのポイントを示す画像である。
【図８Ｄ】様々な実施形態による、レーザプリンタの４つの関節運動可能な部分に対応する処理されたポイントクラウドでアノテーションされた、関節運動していない構成のレーザプリンタに対応するポイントクラウドを示す画像である。
【図８Ｅ】様々な実施形態による、図８Ｃに示されるクラスタリング結果から、関節運動可能な部分に対応するポイントのクラスタに属していない全ての点が削除された後の、関節運動可能な部分に対応する残りのポイントを示す画像である。
【図９】様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの１つ以上の関節運動可能な部分を識別するように構成されたシステムのブロック図である。
【発明を実施するための形態】
【０００４】
コンピュータ実装システムは、視覚及び聴覚に直接訴える合図を提供することによって、非専門家のエンドユーザ（例えば、サービス技術者）が多岐にわたる物理的（例えば、電気機械的）デバイスを設置、構成、及び修理するのを支援することができる。例えば、コンピュータ実装システムは、コンピュータ支援設計（ＣＡＤ）モデルの使用によってなど、視覚に訴えてエンドユーザに特定の物理的デバイスの複雑な修理手順を段階的に進めさせる構造化された方法を提供することができる。しかしながら、多くの状況では、特定の物理的デバイスに対してＣＡＤモデルが利用可能ではない。
【０００５】
本開示の実施形態は、一般商品の３次元（３Ｄ）センサを使用して、１つ以上の関節運動した（例えば、移動可能な）部分を有する物理的オブジェクトの近似ＣＡＤモデルを生成するためのシステム及び方法を対象とする。有利には、専門の技術者又は設計者を必要とせずに、近似ＣＡＤモデルを迅速に生成することができる。本開示の実施形態は、一般商品の３Ｄセンサから生成された複数の３Ｄメッシュ又はポイントクラウドを使用して、３Ｄオブジェクトの１つ以上の関節運動可能な部分を識別するためのシステム及び方法を対象とする。本開示の処理方法論（例えば、アルゴリズム）は、複雑な３Ｄ  ＣＡＤモデルの知識を必要としない。その代わりに、本開示の処理方法論は、１つ以上の関節運動可能な部分の関節運動前及び関節運動後の物理的オブジェクトの３Ｄポイントクラウド上で動作する。様々な出力が生成され得、これには、関節運動可能な部分の視覚／グラフィック出力（例えば、アノテーションされた形態）、関節運動可能な部分の移動前の物理的オブジェクトの、関節運動可能な部分がその移動前の位置で示されている視覚／グラフィック出力、及び関節運動可能な部分の移動後の物理的オブジェクトの、関節運動可能な部分がその移動後の位置で示されている視覚／グラフィック出力が含まれる。
【０００６】
実施形態は、ポイントクラウドから３Ｄモデルの関節運動可能な部分を識別するためのシステム及び方法を対象とする。システム及び方法の実施形態は、最初にポイントクラウドの精密な３Ｄレジストレーションを実行することができ、続いて、ポイントクラウド間の対応ポイントの効率のよい近似的な最近傍排除を実行することができる、多段階プロセスを実装することができる。システム及び方法の実施形態はまた、人間参加型のアプローチを使用して、又は人間の介入なしにアルゴリズム的に、排除プロセスの結果を精緻化するように実装することもできる。
【０００７】
本明細書で使用するとき、用語「関節運動可能な部分」は、物理的オブジェクトに対して少なくとも２つの位置の間で移動可能（関節運動可能）である３Ｄ物理的オブジェクトの部分又は構成要素を指す。全般的に、関節運動可能な部分は、関節運動可能な部分がその関節運動した位置及び関節運動していない位置において物理的オブジェクトに取り付けられたまま又は連結されたままであるように、物理的オブジェクトに移動可能に取り付けられるか、又は連結されている。場合によっては、関節運動可能な部分は、その関節運動していない位置において物理的オブジェクトに取り付け可能であり、かつその関節運動した位置において物理的オブジェクトから取り外し可能である、部分又は構成要素である。
【０００８】
図１は、様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの関節運動可能な部分を識別するためのコンピュータ実装方法を示すフロー図である。図１に示す方法は、少なくとも１つの関節運動可能な部分を有する物理的オブジェクトに関連付けられた第１の３Ｄポイントクラウドを取得すること（１０２）を含む。第１のポイントクラウドは、関節運動可能な部分の関節運動前の物理的オブジェクトに関連付けられている。方法は、関節運動可能な部分の関節運動後の物理的オブジェクトに関連付けられた第２の３Ｄポイントクラウドを取得すること（１０４）を含む。方法はまた、第１及び第２のポイントクラウドを位置合わせすること（１０６）も含む。いくつかの実施形態では、第１及び第２のポイントクラウドを位置合わせすること（１０６）は、第１及び第２のポイントクラウドを粗く位置合わせし、続いて、第１及び第２のポイントクラウドを細かく位置合わせすることを含む。
【０００９】
方法は、第２のポイントクラウド内のポイントに対する第１のポイントクラウド内の最近傍のポイントを見つけること（１０８）を含む。方法はまた、第２のポイントクラウド内の残りのポイントが、関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように、第２のポイントクラウド内の最近傍のポイントを排除すること（１１０）も含む。方法は、ノイズポイントを含まずに、関節運動可能な部分に関連付けられた第２のポイントクラウドの少なくとも残りのポイントを含む出力を生成すること（１１２）を更に含む。様々な実施形態では、第１及び第２のポイントクラウドは、市販の３Ｄスキャナなど、一般商品の３Ｄセンサを使用して取得される。
【００１０】
図１に示される実施形態では、物理的オブジェクトの２つ以上の関節運動可能な部分が図１に示される方法で識別され得ることは理解される。例えば、図２を参照すると、物理的オブジェクトは、複数の関節運動可能な部分を含み得、この複数の関節運動可能な部分のそれぞれは、図２に示される方法論に従って識別され得る。図２の方法は、Ｎ個の関節運動可能な部分を有する物理的オブジェクトに関連付けられた第１の３Ｄポイントクラウドを取得すること（２０２）を含み、Ｎは０を超える整数である。第１のポイントクラウドは、Ｎ個の関節運動可能な部分の関節運動前の物理的オブジェクトに関連付けられている。方法は、Ｎ個の関節運動可能な部分のそれぞれの関節運動後の物理的オブジェクトに関連付けられたＭ個の３Ｄポイントクラウドを取得すること（２０４）を含み、Ｍは０を超える整数である。方法はまた、第１のポイントクラウドをＭ個のポイントクラウドのそれぞれと位置合わせすること（２０６）も含む。いくつかの実施形態では、第１及びＭ個のポイントクラウドを位置合わせすること（２０６）は、第１及びＭ個のポイントクラウドを粗く位置合わせし、続いて、第１及びＭ個のポイントクラウドを細かく位置合わせすることを含む。
【００１１】
方法は、Ｍ個のポイントクラウドのそれぞれ内のポイントに対する第１のポイントクラウド内の最近傍のポイントを見つけること（２０８）を含む。方法はまた、Ｍ個の各ポイントクラウド内の残りのポイントが、関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように、Ｍ個のポイントクラウドのそれぞれ内の最近傍のポイントを排除すること（２１０）も含む。方法は、ノイズポイントを含まずに、関節運動可能な部分に関連付けられたＭ個の各クラウドの少なくとも残りのポイントを含む出力を生成すること（２１２）を更に含む。様々な実施形態では、第１及びＭ個のポイントクラウドは、市販の３Ｄスキャナなど、一般商品の３Ｄセンサを使用して取得される。
【００１２】
図３は、様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの１つ以上の関節運動可能な部分を識別するためのシステム及び方法を示す。図３に示される実施形態では、代表的な物理的オブジェクトは、レーザプリンタ３００である。物理的オブジェクトが、１つ以上の関節運動可能な部分を含む任意の３Ｄオブジェクトを表し得ること、及び図３のレーザプリンタ３００が、非限定的な例示目的のために示されていることは理解される。構成１は、１つ以上の関節運動可能な部分の関節運動前のレーザプリンタ３００を示す。構成２は、図３において引き出し式用紙トレイ３０１である第１の関節運動可能な部分の関節運動後のレーザプリンタ３００を示す。構成Ｎは、図３において引き出し式エンベロープ供給トレイ３０２である第Ｎの関節運動可能な部分の関節運動後のレーザプリンタ３００を示す。レーザプリンタ３００が、典型的には、いくつかの関節運動可能な部分（例えば、トナーカートリッジ引き出し、用紙トレイ、エンベロープ供給トレイ、ヒンジ式通信ポートドアなど）を含むこと、及びこれらの部分のそれぞれの関節運動が、プリンタ３００の異なる構成によって表わされ得ることは理解される。
【００１３】
図３に示されるように、３Ｄセンサ３０４は、プリンタ３００をその構成１〜Ｎのそれぞれにおいてスキャンするために使用される。３Ｄセンサ３０４は、スマートフォン又はタブレットコンピューティングデバイスと共に使用されるように構成された一般商品又は市販の３Ｄスキャナであり得、その例を以下に説明する。便宜上、３Ｄセンサ３０４は、ポータブルコンピューティングデバイスと組み合わせた３Ｄスキャンデバイスを指す。実際には、ユーザは、３Ｄセンサ３０４をレーザプリンタ３００に近接させて配置し、レーザプリンタ３００をその構成１〜Ｎのそれぞれにおいてスキャンする。例えば、第１のスキャンは、レーザプリンタ３００がその関節運動していない構成（構成１）にある状態で、３Ｄセンサ３０４によって生成される。第１のスキャンは、ポイントクラウド１の生成をもたらし、ポイントクラウド１はメモリ３１０に記憶される。ユーザは、レーザプリンタ３００の第１の関節運動可能な部分を表す用紙トレイ３０１を引き出す（構成２）。第２のスキャンは、ポイントクラウド２の生成をもたらし、ポイントクラウド２はメモリ３１０に記憶される。ユーザは、用紙トレイ３０１をその関節運動していない位置に戻し、レーザプリンタ３００の第２の関節運動可能な部分を表すエンベロープ供給トレイ３０２を引き出す（構成Ｎ）。第３のスキャンは、ポイントクラウドＭの生成をもたらし、このポイントクラウドはメモリ３１０に記憶される。
【００１４】
いくつかの実施形態では、３Ｄセンサ３０４は、メッシュジェネレータ３０６及びポイントクラウドジェネレータ３０８を含む。このような実施形態では、メッシュジェネレータ３０６は、スキャンのそれぞれの結果としてメッシュを生成するように構成されている。各メッシュは、頂点のセット、及び頂点を接続する辺によって形成された三角形面のセットから構成される。ポイントクラウドジェネレータ３０８は、メッシュジェネレータ３０６によって生成された各メッシュ上で動作するように構成されており、これらのメッシュのそれぞれからポイントクラウドを抽出する。各ポイントクラウドは、その対応するメッシュの全ての頂点から構成される。他の実施形態では、３Ｄセンサ３０４は、ポイントクラウドジェネレータ３０８を含むが、メッシュジェネレータ３０６を含まない。このような実施形態では、ポイントクラウドジェネレータ３０８は、各スキャンから結果として生じるポイントクラウドを生成するように構成されている。
【００１５】
メモリ３１０に収集されたポイントクラウド１〜Ｍは、位置合わせモジュール３１２によって処理される。位置合わせモジュール３１２は、２段階の位置合わせプロセスを実行するように構成されており、このプロセスは、ポイントクラウド２〜Ｍとのポイントクラウド１の粗い位置合わせ、及びその後に続く細かい位置合わせを含む。識別モジュール３１８は、位置合わせされたポイントクラウド１〜Ｍ上で動作して、関節運動可能な部分Ａ１〜ＡＮ３２０（例えば、用紙トレイ３０１、エンベロープ供給トレイ３０２）のそれぞれに属するポイントのクラスタを識別する。関節運動可能な部分Ａ１〜ＡＮ３２０のそれぞれを識別した後、関節運動可能な部分Ａ１〜ＡＮ３２０を出力及び／又はアノテーションすること（３２２）など、後続のプロセスが実行され得る。例えば、関節運動可能な部分Ａ１〜ＡＮ３２０をアノテーションされた形態（例えば、異なる色、シェーディング、ハッチング）で示しているアノテーションされたレーザプリンタ３００の近似ＣＡＤモデルなど、視覚又はグラフィック出力が生成され得る。代替的に、又は加えて、データ構造又は情報信号が、単独で又はアノテーションされたレーザプリンタ３００として組み合わせて、関節運動可能な部分Ａ１〜ＡＮ３２０の出力３２２として生成され得る。
【００１６】
図４は、様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの関節運動可能な部分を識別するためのコンピュータ実装方法を示すフロー図である。図４に示す方法は、物理的オブジェクトの第１の３Ｄポイントクラウド（ポイントクラウド１）を関節運動していない構成で取得すること（４０２）を含む。方法は、物理的オブジェクトの第２の３Ｄポイントクラウド（ポイントクラウド２）を、少なくとも１つの部分が関節運動した状態である関節運動した構成で取得することを含む（４０４）。方法はまた、ポイントクラウド１及びポイントクラウド２をダウンサンプリングして、疎なポイントクラウド１及び２を生成すること（４０６）も含む。方法は、疎なポイントクラウド１及び２から高速点特徴ヒストグラム（Ｆａｓｔ  Ｐｏｉｎｔ  Ｆｅａｔｕｒｅ  Ｈｉｓｔｏｇｒａｍ）（ＦＰＦＨ）記述子を計算すること（４０８）を更に含む。方法は、ＦＰＦＨ記述子を使用してポイントクラウド１及びポイントクラウド２を粗く位置合わせすること（４１０）を含む。方法は、ＩＣＰ位置合わせを使用してポイントクラウド１及びポイントクラウド２を細かく位置合わせすること（４１２）を含む。ポイントクラウド１及びポイントクラウド２をダウンサンプリングすること（４０６）は任意であり、処理速度を上げるために実行され得ることに留意されたい。
【００１７】
図４に更に示されるように、方法は、ポイントクラウド２内のポイントに対するポイントクラウド１内の最近傍のポイントを見つけること（４１４）を含む。方法はまた、ポイントクラウド２内の最近傍のポイントを排除すること（４１６）、及びポイントクラウド２内の残りのポイントにクラスタリングを適用すること（４１８）も含む。方法は、関節運動可能な部分に関連付けられたポイントのクラスタをノイズポイントクラスタと区別すること（４２０）を更に含む。いくつかの実施形態では、区別プロセス４２０は、関節運動可能な部分を識別するユーザ入力を受信すること、及びユーザ入力に応じて、関節運動可能な部分に関連付けられたポイントのクラスタをノイズポイントクラスタと区別することを含む。他の実施形態では、区別プロセス４２０は、関節運動可能な部分に関連付けられたポイントのクラスタをノイズポイントクラスタとアルゴリズム的に（例えば、ユーザ入力なしで）区別することを含む。区別プロセス４２０は、結果として、関節運動可能な部分を識別することになる。
【００１８】
いくつかの実施形態では、方法は、関節運動可能な部分を着色する、シェーディングする、ハッチングする、ないしは別の方法でグラフィカルに強調することなどによって、関節運動可能な部分に関連付けられたポイントのクラスタをアノテーションすること（４２２）を含む。例えば、関節運動可能な部分に関連付けられたポイントのクラスタは、物理的オブジェクトの色（又はグレースケール彩度）とは異なる色（又はグレースケール彩度）を有することができる。方法は、関節運動可能な部分の出力を、単独で又は物理的オブジェクトと組み合わせて、グラフィック出力（例えば、ディスプレイ上）、データ構造出力（例えば、データマトリックス）、情報信号、又はこれらの出力の任意の組み合わせの形態で、生成することを含み得る。
【００１９】
以下の説明は、様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの関節運動可能な部分を識別するためのコンピュータ実装方法を示す、更なる詳細を提供する。物理的オブジェクトは、本質的に［Ｘ，Ｙ］座標を有する２次元グリッド内のピクセル値（例えば、ＲＧＢ）である画像を使用して、２Ｄで表すことができる。ポイントクラウドは、この表現の３Ｄへの直接の拡張である。［Ｘ，Ｙ，Ｚ］座標によって位置が指定されているピクセル値のセットによって、物理的オブジェクトを表すことができる。ポイントクラウドは、常に矩形である画像とは異なり、処理されるデータの構造内でのばらつきがより大きくなる。ポイントクラウドはまた、深度についての正確な情報も含むことができ、一方、画像は相対的な深度のみを示すことができる。結果として、ポイントクラウドは、３Ｄでのオブジェクトの姿勢の修正であり得る、オブジェクトの関節運動を理解するための汎用かつ有用な表現である。
【００２０】
様々な実施形態によれば、市販の３Ｄスキャナをスマートフォン又はタブレットデバイスと共に使用して、３Ｄオブジェクトをスキャンし、複数のポイントクラウドを生成することができる。オブジェクトが、例えば、ｋ個の関節運動可能な部分を有する場合、３Ｄスキャナを使用して、ｋ＋１個のポイントクラウドが収集される。この場合、関節運動を有しないオブジェクトの１つのポイントクラウドが収集され、関節運動したｋ個の部分のそれぞれを有するｋ個のポイントクラウドが、１つずつ、収集される。関節運動を有しないポイントクラウドは、基準ポイントクラウドを定義し、この基準ポイントクラウドは、便宜上、ポイントクラウド１と呼ばれる。説明を明確にするために、３Ｄオブジェクトは１つの関節運動可能な部分を有することが想定されるが、３Ｄオブジェクトが任意の数の関節運動可能な部分を有し得ることは理解される。１つの関節運動可能な部分を有するポイントクラウドは、便宜上、ポイントクラウド２と呼ばれる。ポイントクラウド２内では、関節運動可能な部分に属する領域を除いて、ポイントが、ポイントクラウド１内の対応するポイントに極めて近接していることが想定される。この仮定を使用して、最近傍排除が実行される。例えば、ポイントクラウド１内のポイント［ｘ，ｙ，ｚ］がポイントクラウド１内のポイント［ｘ’，ｙ’，ｚ’］の近傍半径ｒ内に存在する場合、これらのポイントは両方ともわずかな動きを有する同じポイントであり、［ｘ，ｙ，ｚ］は関節運動可能な部分に属さないと見なされる。
【００２１】
しかしながら、この仮定を適用するには、ポイントクラウド１及びポイントクラウド２が、精密に位置合わせされている必要がある。これは、３Ｄスキャナから得られるノイズの多い再構築ではめったにないことである。この問題に対処するために、本発明者らは、最近傍排除を実行する前に、ユーザの介入なしにポイントクラウドを自動的に位置合わせする方法を開発した。ポイントクラウド１及びポイントクラウド２の自動レジストレーションは、ポイントクラウド１及びポイントクラウド２をダウンサンプリングし、ローカル記述子を計算し、マッチングのための閾値基準に基づいて対応ポイントを見つけることによって実行され得る。
【００２２】
ここで図５Ａ〜図５Ｃを参照すると、これらの図は、レーザプリンタ５００を３Ｄスキャンすることに基づいて作成されたポイントクラウドを示す画像である。図５Ａは、レーザプリンタ５００のその関節運動していない構成での基準ポイントクラウドとして機能する、ポイントクラウド１（姿勢１）を示す画像である。図５Ｂは、レーザプリンタ５００のその関節運動した構成でのポイントクラウドである、ポイントクラウド２（姿勢２）を示す画像である。特に、開放されたフロントドア５０２（例えば、トナーカートリッジにアクセスするため）が、レーザプリンタ５００の関節運動可能な部分として示されている。図５Ｃは、ポイントクラウド１及びポイントクラウド２の重ね合わせを示す画像である（説明の便宜上、重ね合わせにおけるポイントクラウド１及びポイントクラウド２のグレースケールの変化に注目する）。図５Ｃは、位置合わせされていないポイントクラウド１及びポイントクラウド２を示す。様々な実施形態によれば、ポイントクラウド１及びポイントクラウド２は、２段階の位置合わせプロセスに供される。この２段階の位置合わせプロセスは、ポイントクラウド１及びポイントクラウド２を粗く位置合わせし、続いて、ポイントクラウド１及びポイントクラウド２を細かく位置合わせすることを含む。次いで、最近傍排除及び後続のプロセスが、細かく（例えば、精密に）位置合わせされたポイントクラウド１及びポイントクラウド２上で実行され得る。
【００２３】
代表的な実施形態によれば、ポイントクラウド１及びポイントクラウド２は、０．０５ｍのボクセルサイズでダウンサンプリングされ、その結果、各寸法に沿って、１つのポイントが、ポイントクラウド１及びポイントクラウド２内で５ｃｍ毎に選択される。ボクセルサイズが必要又は所望に応じて変更され得ることは理解される。ポイントクラウド１及びポイントクラウド２をダウンサンプリングすることは、疎なポイントクラウド１及び疎なポイントクラウド２を生成する。疎なポイントクラウド１及び疎なポイントクラウド２上で高速点特徴ヒストグラム記述子が計算される。ＦＰＦＨ記述子を計算した後、ＦＰＦＨ記述子は、ポイントクラウド１及びポイントクラウド２にわたってマッチングされ、次いで、同次座標上で３Ｄ変換マトリックスを推定することによってポイントクラウド１及びポイントクラウド２を位置合わせするために使用される。この３Ｄ変換マトリックスは、好ましくは、回転、スケーリング、及び並進を取り扱うことができる一般化された４×４の変換マトリックスである。
【００２４】
この代表的な実施形態では、３Ｄ変換マトリックスのパラメータは、ランダムサンプルコンセンサス（ＲＡＮＳＡＣ）方法論（例えば、アルゴリズム）を使用することによって推定される。ＲＡＮＳＡＣ方法論は、サンプルコンセンサスアルゴリズムを使用して、特定の距離基準に従って最も少ないアウトライアをもたらすパラメータのセットを見つける。この例示的な実施形態では、変換されたポイント及び基準ポイントのＬ２ノルムが距離基準として選択される。基準ポイント及び変換されたポイントが、特定の閾値（例えば、２ｍｍ）を下回るＬ２ノルムを有する場合、変換されたポイントはインライアとして扱われ、そうでなければアウトライアとして扱われる。
【００２５】
疎なポイントクラウド１及び疎なポイントクラウド２上で計算された疎なＦＰＦＨ記述子に起因して、推定された３Ｄ変換マトリックスは、単にポイントクラウド１とポイントクラウド２との間の粗いグローバルレジストレーションに過ぎない。結果として、ポイントクラウド１及びポイントクラウド２を細かく位置合わせするプロセスが実装されている。この代表的な実施形態では、反復最近傍点（Ｉｔｅｒａｔｉｖｅ  Ｃｌｏｓｅｓｔ  Ｐｏｉｎｔ）（ＩＣＰ）アルゴリズムを使用してローカルな精緻化が適用される。ＩＣＰアルゴリズムは、近くのポイントが対応ポイントであると仮定し、近くのポイントに基づいて変換を推定する。次いで、変換が適用され、対応ポイントが更新される。目的は、もう一度、対応ポイントのペア間のＬ２ノルムを最小化することである。このプロセスは収束まで反復的に実行され、その結果、平均Ｌ２ノルムは連続した反復の間で変化しなくなる。
【００２６】
ＩＣＰアルゴリズムはローカルミニマムに陥りやすく、したがって、ＩＣＰによる細かい位置合わせを、位置合わせされていないポイントクラウド１及びポイントクラウド２上で直接使用することはできない（例えば、図５Ｃを参照）。しかしながら、ＲＡＮＳＡＣプロセスから抽出された変換でＩＣＰを初期化することにより、グローバルミニマムに非常に近いローカルミニマムが見出される。図６Ａ〜図６Ｃは、上述の２段階レジストレーションプロセスを示す画像である。図６Ａは、位置合わせされていないポイントクラウド１及びポイントクラウド２を示す画像である。図６Ｂは、ＲＡＮＳＡＣによる位置合わせから結果として生じるポイントクラウド１及びポイントクラウド２の粗い位置合わせを示す画像である。図６Ｃは、ＲＡＮＳＡＣ及びＩＰＣによる位置合わせから結果として生じるポイントクラウド１及びポイントクラウド２の細かい（例えば、精密な）位置合わせを示す画像である。
【００２７】
この精密な位置合わせの結果として、ポイントクラウド１及びポイントクラウド２の定常性要件が満たされ、細かく位置合わせされたポイントクラウド１及びポイントクラウド２上で最近傍排除を実行することができる。この代表的な実施形態では、ポイントクラウド１及びポイントクラウド２のそれぞれは、約１０５〜１０６個程度のポイントを含むため、単純な最近傍探索は、Ｏ（Ｎ２）の時間計算量を有することになるので、実行することはできない。その代わりに、近似的な最近傍探索が効率的なデータ構造で実行される。この代表的な実施形態によれば、ポイントクラウド１及びポイントクラウド２のそれぞれは、ｋ−ｄツリー（ｋ次元ツリー）として表される。ｋ−ｄツリーの構築は、Ｏ（Ｎ  ｌｏｇ  Ｎ）時間計算量で行うことができる。これに続いて、クラウド１内の各ポイントについて、対応する最近傍ポイントがクラウド２のツリー内に存在するか否か（すなわち、クラウド１内のポイントの近傍半径内にあるクラウド２内のいくつかのポイント）を判定するチェックが行われる。
【００２８】
範囲探索のための最悪の場合の時間計算量は、Ｏ（ｋＮ（１−１／ｋ））である。ここで、ｋ＝３であり、これは次元数であり、したがって、探索は１ポイント当たりＯ（Ｎ２／３）となる。結果として、ポイントクラウド全体にわたる近似的な最近傍探索は、Ｏ（Ｎ４／３）（Ｎポイント、１ポイント当たりＯ（Ｎ２／３））になる。ポイントは、探索が近傍ポイントを返すと、ポイントクラウド１及びポイントクラウド２（又は、代替的に、ポイントクラウド２のみ）から削除される。この削除は、１ポイント当たりＯ（ｌｏｇ  Ｎ）である。これは近似的な探索であるため、全ての最近傍ポイントを見つけることは保証されておらず、ポイントクラウド内のアーチファクトに起因して、ポイントクラウド内の特定のポイントには最近傍ポイントが存在しないことがある。結果として、ポイントを排除することは、乱雑な（ノイズの多い）結果をもたらす。
【００２９】
図７Ａ及び図７Ｂは、重ね合わせられたポイントクラウド１及びポイントクラウド２の２つの図を示す画像であり、ポイントクラウド１に対してポイントクラウド２からポイントを排除し、またその逆も同様に排除することによって、ポイント削除が実行されている。図７Ａ及び図７Ｂでは、より明るい灰色のポイントは、ポイント排除後のポイントクラウド１の残りのポイントであり、より暗い灰色のポイントは、ポイント排除後のポイントクラウド２の残りのポイントである。これらのアーチファクトを取り除くために、ポイントクラウド１及びポイントクラウド２のクラスタリングが最近傍排除後に実行される。例えば、ノイズを有するアプリケーションの密度ベースの空間クラスタリング（ＤＢＳＣＡＮ）が、最近傍排除後にポイントクラウド１及びポイントクラウド２上で実行され得る。
【００３０】
図８Ａは、レーザプリンタ５００の関節運動していない構成に対応する、元のポイントクラウド１を示す画像である。図８Ｂは、定位置にレンダリングされた関節運動可能な部分５０２を示す画像である。図８Ｃは、多数の個々のノイズクラスタ８０２と、関節運動可能な部分５０２に関連付けられたポイントクラスタ（例えば、レーザプリンタ５００のフロントドア）と、を含む、クラスタリング結果を示す画像である。図８Ｃは、関節運動可能な部分５０２に対応する残りのポイントクラウド２を示す。図８Ｃでは、元のポイントクラウド１（より明るいグレースケール）は、関節運動させられ得る、関節運動可能な部分５０２に対応するポイントクラウド２の残りのポイントを含むようにアノテーションされている。
【００３１】
図８Ｃに示されるクラスタリング結果内の関節運動可能な部分５０２を識別することは、関節運動可能な部分５０２に関連付けられたポイントのクラスタをノイズポイントクラスタ８０２と区別することを含む。いくつかの実施形態では、関節運動可能な部分５０２に関連付けられたポイントのクラスタをノイズポイントクラスタ８０２と区別することは、人間のアノテータからの入力を含む。例えば、人間のアノテータは、図８Ａに示される元のポイントクラウド１内で関節運動可能な部分５０２に対応するポイント８００をマーキングするように、ポイントクラウド処理（例えば、図４中の工程４２０）中に求められる。ポイント８００が属する、図８Ｂに示されるクラスタリング結果内のポイントクラスタは、関節運動可能な部分５０２に属するポイントのセットである。関節運動可能な部分５０２に対応するポイントのクラスタに属していない全ての点は、図８Ｃに示されるクラスタリング結果から削除され得、その結果、図８Ｅに示される画像が得られる。結果として、残りのポイントクラウド２（例えば、図８Ｅ）は、関節運動可能な部分５０２に属するポイントのセットのみを含む。
【００３２】
いくつかの実施形態によれば、図８Ｂに示されるクラスタリング結果内の関節運動可能な部分５０２を識別することは、関節運動可能な部分５０２に関連付けられたポイントのクラスタをノイズポイントクラスタ８０２とアルゴリズム的に区別することを含む。このアプローチは、人間のアノテータからの入力を含まない又は必要としない。関節運動可能な部分５０２に関連付けられたポイントのクラスタをノイズポイントクラスタ８０２と区別することは、ポイントのクラスタのそれぞれのサイズをアルゴリズム的に判定することと、最大のポイントクラスタを、関節運動可能な部分５０２に関連付けられたポイントのクラスタとして選択することと、を含む。
【００３３】
上述のプロセスは、多数の関節運動可能な部分を有する物理的オブジェクト上で実行され得る。関節運動可能な部分は、Ｎ個の関節運動可能な部分に対応するＭ個の３Ｄポイントクラウド、及び関節運動可能な部分の関節運動前の物理的オブジェクトに対応する基準ポイントクラウドを使用して、上述のように識別され得る。図８Ｄは、例えば、レーザプリンタ５００の４つの関節運動可能な部分５０２、８０４、８０６、８０８に対応する処理されたポイントクラウドでアノテーションされたレーザプリンタ５００（関節運動していない構成）に対応するポイントクラウド１を示す画像である。関節運動可能な部分は、フロントドア５０２、上部カバー８０４、前面パネル８０６、及びエンベロープ供給トレイ８０８を含み、これらのそれぞれは、関節運動させられ得る。
【００３４】
図９は、様々な実施形態による、複数の３Ｄポイントクラウドを使用して物理的オブジェクトの１つ以上の関節運動可能な部分を識別するように構成されたシステム９００のブロック図である。システム９００は、図１〜図４に示されるものを含む、上述のプロセスを実装するように構成されている。システム９００は、３Ｄセンサ９０４に通信可能に連結されたコンピューティングデバイス９０２を含む。いくつかの実施形態では、コンピューティングデバイス９０２及び３Ｄセンサ９０４は、単一又は共通の装置の構成要素である。他の実施形態では、３Ｄセンサ９０４は、コンピューティングデバイス９０２とは別個の構成要素であり、入力インターフェース９０８を介してコンピューティングデバイス９０２に通信可能に連結されている。
【００３５】
コンピューティングデバイス９０２は、例えば、スマートフォン、タブレット、ファブレット、ラップトップ又は他のポータブル若しくはデスクトップコンピュータを含む、様々な異なるコンピューティングデバイスを表す。３Ｄセンサ９０４は、例えば、赤外光若しくは構造化光３Ｄスキャナ、３Ｄライダスキャナ、共焦点若しくは３Ｄレーザスキャナ、コノスコピックホログラフィックスキャナ、変調光３Ｄスキャナ、タイムオブフライト３Ｄレーザスキャナ、又は三角測量ベースの３Ｄレーザスキャナを含む、様々な異なる３Ｄスキャンデバイスを表す。３Ｄセンサ９０４は、手持ち式スキャナ又は三脚支持された３Ｄスキャナであり得る。好適な一般商品の３Ｄセンサ９０４は、Ｏｃｃｉｐｉｔａｌ，Ｉｎｃ．（Ｓａｎ  Ｆｒａｎｃｉｓｃｏ  Ｃａｌｉｆｏｒｎｉａ）から入手可能なタブレット及びスマートフォン用のＳｔｒｕｃｔｕｒｅ  Ｓｅｎｓｏｒである。
【００３６】
コンピューティングデバイス９０２は、入力インターフェース９０８及び出力インターフェース９１０に連結されたプロセッサ９０６を含む。入力インターフェース９０８及び出力インターフェース９１０は、有線インターフェース又は無線インターフェース（例えば、Ｂｌｕｅｔｏｏｔｈ（登録商標）又はＩＥＥＥ８０２．１１準拠のトランシーバ）として構成され得る。プロセッサ９０６は、１つ以上のマルチコアプロセッサ、汎用マイクロプロセッサ、専用マイクロプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、フィルタ、及び他のデジタル論理回路（例えば、ＡＳＩＣ、ＦＰＧＡ、ＡＳＳＰ）のうちの１つ又は任意の組み合わせを表し得る。プロセッサ９０６は、ＲＯＭ、ＲＡＭ、ＳＤＲＡＭ、ＮＶＲＡＭ、ＥＥＰＲＯＭ、及びフラッシュのうちの１つ以上を含み得るメモリ９２０に作動的に連結される。メモリ９２０は、タスクをスケジューリングすること、アプリケーションを実行すること、及び周辺機器を制御することなど、コンピューティングデバイス９０２の基本機能をサポートするソフトウェアを含むオペレーティングシステム９２２を記憶するように構成されている。メモリ９２０はまた、本明細書に記載されるプロセス及びアルゴリズムを実装するためにプロセッサ９０６によって実行されるコード又は命令９２４をソフトウェア及び／又はファームウェアの形態で記憶するようにも構成されている。
【００３７】
コンピューティングデバイス９０２は、グラフィカルユーザインターフェース（ＧＵＩ）９３０を含み得、ＧＵＩ  ９３０は、タッチスクリーンを含んでもよく、又はタッチスクリーンの形態をとってもよい。コンピューティングデバイス９０２は、ポインティングデバイス９３２及び／又はキーボード９３４など、他のユーザ入力デバイスを含んでもよく、又はそれらに通信可能に連結されてもよい。コンピューティングデバイス９０２は、出力インターフェース９１０を介して１つ以上の出力デバイス９４０に通信可能に連結されてもよい。出力デバイス９４０は、ディスプレイ９４２、プリンタ９４４、大容量記憶デバイス９４６、ポータブル記憶デバイス９４８、及び通信チャネル９５０のうちの１つ以上を含み得る。
【００３８】
様々な実施形態によれば、入力インターフェース９０８は、少なくとも１つの関節運動可能な部分を有する物理的オブジェクトに関連付けられた、３Ｄセンサ９０４によって生成された第１の３Ｄポイントクラウドを受信するように構成されている。第１のポイントクラウドは、関節運動可能な部分の関節運動前の物理的オブジェクトに関連付けられている。入力インターフェース９０８はまた、関節運動可能な部分の関節運動後の物理的オブジェクトに関連付けられた、３Ｄセンサ９０４によって生成された第２の３Ｄポイントクラウドを受信するようにも構成されている。メモリ９２０は、入力インターフェース９０８に動作可能に連結されており、第１及び第２のポイントクラウド並びにプログラムコード９２４を記憶するように構成されている。プロセッサ９０６は、入力インターフェース９０８、出力インターフェース９１０、及びメモリ９２０に動作可能に連結されている。プログラムコード９２４は、プロセッサ９０６によって実行されると、プロセッサ９０６に、第１及び第２のポイントクラウドを位置合わせさせ、第２のポイントクラウド内のポイントに対する第１のポイントクラウド内の最近傍のポイントを見つけさせ、第２のポイントクラウド内の残りのポイントが、関節運動可能な部分に関連付けられたポイント及びノイズに関連付けられたポイントを含むように、第２のポイントクラウド内の最近傍のポイントを排除させる。プログラムコード９２４は、プロセッサ９０６によって実行されると、プロセッサ９０６に、ノイズポイントを含まずに、関節運動可能な部分に関連付けられた第２のポイントクラウドの少なくとも残りのポイントを含む出力を生成させ、出力を出力インターフェース９１０に伝達させる。出力は、出力インターフェース９１０から出力デバイス９４０のうちの１つ以上に伝達され得る、グラフィック出力、データ構造出力、及び情報信号のうちの１つ以上を含み得る。
【００３９】
端点による数値範囲の記載は、その範囲内に包含される全ての数（例えば、１〜５は、１、１．５、２、２．７５、３、３．８０、４、及び５を含む）及びその範囲内の任意の範囲を含む。本明細書において、数を修飾する用語「最大で」又は「以下」（例えば、「最大で５０」）は、その数（例えば、５０）を含み、数を修飾する用語「以上」（例えば、「５以上」）は、その数（例えば、５）を含む。
【図１】
2020109626.tif 000003
【図２】
2020109626.tif 000004
【図３】
2020109626.tif 000005
【図４】
2020109626.tif 000006
【図５Ａ】
2020109626.tif 000007
【図５Ｂ】
2020109626.tif 000008
【図５Ｃ】
2020109626.tif 000009
【図６Ａ】
2020109626.tif 000010
【図６Ｂ】
2020109626.tif 000011
【図６Ｃ】
2020109626.tif 000012
【図７Ａ】
2020109626.tif 000013
【図７Ｂ】
2020109626.tif 000014
【図８Ａ】
2020109626.tif 000015
【図８Ｂ】
2020109626.tif 000016
【図８Ｃ】
2020109626.tif 000017
【図８Ｄ】
2020109626.tif 000018
【図８Ｅ】
2020109626.tif 000019
【図９】
2020109626.tif 000020