(57)【特許請求の範囲】
【請求項１】
非一時的コンピュータ可読媒体と、
少なくとも一つの処理回路であって、物体構造を記述する空間構造データが、前記非一時的コンピュータ可読媒体に記憶されるとき、
前記空間構造データであって、前記物体構造について複数の層を示す奥行き情報を有する前記空間構造データにアクセスすることと、
前記空間構造データから、前記複数の層のうちの一層を表す、前記空間構造データの一部分を抽出することと、
前記空間構造データの前記一部分から、前記層の輪郭を記述する複数の頂点を識別することと、
前記複数の頂点の中から前記層の凸角を識別することと、
前記凸角に従って、物体認識を行うことと、
を行うように構成される、少なくとも一つの処理回路と、
を備え、
前記複数の頂点の中から前記層の前記凸角を識別することは、
（ａ）前記複数の頂点の中から、３Ｄ頂点の集合を識別することと、
（ｂ）前記３Ｄ頂点の集合の中から、３Ｄ角の集合を識別することと、
（ｃ）前記３Ｄ角の集合の中から、前記凸角の少なくとも一部を識別することと、によってなされ、
前記３Ｄ頂点の集合は、定義される閾値長さに等しいかまたはそれを超える、最も近い隣接頂点へのそれぞれの距離を各々有する頂点を含み、
前記３Ｄ頂点の集合は、前記定義される閾値長さよりも短い、最も近い隣接頂点へのそれぞれの距離を有するいかなる頂点を除外し、
前記３Ｄ角の集合は、前記３Ｄ頂点の集合の中から、前記物体構造の直交角を表す３Ｄ頂点を含む、計算システム。
【請求項２】
前記空間構造データが、前記物体構造の一つ以上の面上におけるそれぞれの位置を表す複数の点を識別する点群を含み、
抽出される前記空間構造データの前記一部分が、前記複数の点の一部分を表し、かつ、前記層を表す点の集合を識別する、請求項１に記載の計算システム。
【請求項３】
前記処理回路が、
前記層を表す前記点の集合について、真っ直ぐな縁を形成する複数の線分を識別することと、
前記複数の頂点を前記線分の終点として識別することと、によって、
前記層の前記輪郭を記述する前記複数の頂点を識別するように構成される、請求項２に記載の計算システム。
【請求項４】
前記処理回路が、
前記点の集合の周縁上にある点を表す複数の縁点を前記点の集合の中から識別することと、
前記複数の縁点を通り抜ける複数の線を判定することと、
前記複数の線が交差する交点を、前記複数の頂点として識別することと、によって、
前記層の前記輪郭を記述する前記複数の頂点を識別するように構成される、請求項２に記載の計算システム。
【請求項５】
前記処理回路がさらに、
凸状である３Ｄ角を、前記凸角として識別するように構成される、請求項１に記載の計算システム。
【請求項６】
前記処理回路がさらに、
前記複数の頂点のうちの第一頂点を、前記３Ｄ角の集合の中へ含むかどうかを判定することによって、前記３Ｄ角の集合を識別するように構成されており、
かかる判定は、
前記複数の頂点の中から、前記層の前記輪郭に沿う第一方向において、前記第一頂点に最も近い隣接頂点である第二頂点を選択することと、
前記第一頂点から前記第二頂点までである、第一ベクトルを画定することと、
前記複数の頂点の中から、前記層の前記輪郭に沿う第二方向において、前記第一頂点に最も近い隣接頂点である第三頂点を選択することであって、前記第二方向は、前記第一方向とは異なる、ことと、
前記第一頂点から前記第三頂点までである、第二ベクトルを画定することと、
前記第一ベクトルの第一長さを前記定義される閾値長さと比較することによって、前記第一頂点が第一長さ基準を満たすかどうかを判定することと、
前記第二ベクトルの第二長さを前記定義される閾値長さと比較することによって、前記第一頂点が第二長さ基準を満たすかどうかを判定することと、
前記第一ベクトルおよび前記第二ベクトルが実質的に互いに直交するかどうかを判定することによって、前記第一頂点が直交性基準を満たすかどうかを判定することと、
前記第一頂点が前記第一長さ基準を満たさない、前記第一頂点が前記第二長さ基準を満たさない、または前記第一頂点が前記直交性基準を満たさないという判定に応じて、前記３Ｄ角の集合から前記第一頂点を除外するように判定することと、
前記第一頂点が前記第一長さ基準を満たす、前記第一頂点が前記第二長さ基準を満たす、および前記第一頂点が前記直交性基準を満たすという判定に応じて、前記３Ｄ角の集合に前記第一頂点を含むように判定することと、
によってなされる、請求項１に記載の計算システム。
【請求項７】
前記処理回路がさらに、
前記３Ｄ角の集合に３Ｄ角として前記第一頂点を含むという判定に応じて、
前記３Ｄ角の凸状を判定するために、前記第一ベクトルと前記第二ベクトルとの外積を判定することによって、前記３Ｄ角が凸角であるかどうかをさらに判定するように構成される、請求項６に記載の計算システム。
【請求項８】
前記外積を判定することは、外積のベクトルを判定することを含み、
前記３Ｄ角が凸角であるかどうかを判定することは、前記外積のベクトルの方向が画定される方向に一致するかどうかを判定することを含む、請求項７に記載の計算システム。
【請求項９】
前記処理回路が、前記複数の頂点の各頂点について、
前記３Ｄ角の集合にそれぞれの３Ｄ角として前記頂点を含むかどうかを判定することと、
前記層の前記輪郭に沿って時計回りまたは反時計回りに、前記複数の頂点を経て進行する順番で、前記判定を実行することと、
を行うように構成され、
前記外積のベクトルの方向と比較される、前記画定される方向は、前記順番が前記時計回りに前記複数の頂点を経て進行するか、または前記順番が前記反時計回りに前記複数の頂点を経て進行するかによる、請求項８に記載の計算システム。
【請求項１０】
前記処理回路は、
前記第一頂点が前記直交性基準を満たさないという判定に応じて、前記第一頂点に基づいて融合角を判定するように構成され、
前記融合角は、前記物体構造に基づく形状の直交角であり、
前記融合角は、
前記層の前記輪郭に沿う前記第二方向において、前記第一頂点に二番目に近い隣接頂点である第四頂点を選択することと、
前記第四頂点と前記第三頂点との間に、第三ベクトルを画定することと、
前記第一ベクトルに沿って延びる第一線、および前記第三ベクトルに沿って延びる第二線を判定することと、
前記第一線と前記第三線との間の交点を識別することと、
前記第一線および前記第三線が実質的に互いに直交するかどうかを判定することによって、前記交点が前記直交性基準を満たすかどうかを判定することと、
前記交点が前記直交性基準を満たすという判定に応じて、前記交点を前記融合角として識別することと、
によって判定される、請求項６に記載の計算システム。
【請求項１１】
前記処理回路は、
前記融合角が前記層の前記輪郭の外側にあるかどうかを判定することによって、前記融合角が凸状であるかどうかを判定し、
前記融合角が凸状であるという判定に応じて、前記凸角のうちの一つとして前記融合角を識別するように構成される、請求項１０に記載の計算システム。
【請求項１２】
前記処理回路はさらに、
前記第一ベクトルおよび前記第二ベクトルを画定する前に、ならびに前記第一頂点が前記第一長さ基準、前記第二長さ基準、および前記直交性基準を満たすかどうかを判定する前に、
前記第一頂点、前記第二頂点、および前記第三頂点を共有平面上へ投影するように構成される、請求項６に記載の計算システム。
【請求項１３】
前記処理回路はさらに、前記凸角に従って検出仮説を生成することによって、前記物体認識を行うように構成される、請求項１に記載の計算システム。
【請求項１４】
前記処理回路は、前記凸角に基づいて、前記物体構造を記述する前記空間構造データを、同様に前記物体構造を記述するテンプレートの中の特徴にどのようにマッピングするかを判定することによって、物体認識を行うように構成される、請求項１に記載の計算システム。
【請求項１５】
前記処理回路はさらに、前記凸角に従って検出仮説を修正することによって、前記物体認識を行うように構成される、請求項１に記載の計算システム。
【請求項１６】
非一時的コンピュータ可読媒体であって、当該非一時的コンピュータ可読媒体上に記憶された命令を有する非一時的コンピュータ可読媒体であって、
前記命令は、処理回路によって実行されるとき、前記処理回路に、
物体構造を記述する空間構造データであって、前記物体構造について複数の層を示す奥行き情報を有する空間構造データにアクセスすることと、
前記空間構造データから、前記複数の層のうちの一層を表す、前記空間構造データの一部分を抽出することと、
前記空間構造データの前記一部分から、前記層の輪郭を記述する複数の頂点を識別することと、
前記複数の頂点の中から前記層の凸角を識別することと、
前記凸角に従って、物体認識を行うことと、
を行わせ、
前記複数の頂点の中から前記層の前記凸角を識別することは、
（ａ）前記複数の頂点の中から、３Ｄ頂点の集合を識別することと、
（ｂ）前記３Ｄ頂点の集合の中から、３Ｄ角の集合を識別することと、
（ｃ）前記３Ｄ角の集合の中から、前記凸角の少なくとも一部を識別することと、によってなされ、
前記３Ｄ頂点の集合は、定義される閾値長さに等しいかまたはそれを超える、最も近い隣接頂点へのそれぞれの距離を各々有する頂点を含み、
前記３Ｄ頂点の集合は、前記定義される閾値長さよりも短い、最も近い隣接頂点へのそれぞれの距離を有するいかなる頂点を除外し、
前記３Ｄ角の集合は、前記３Ｄ頂点の集合の中から、前記物体構造の直交角を表す３Ｄ頂点を含む、非一時的コンピュータ可読媒体。
【請求項１７】
前記命令が、前記処理回路によって実行されるとき、前記処理回路に、
凸状である３Ｄ角を、前記凸角として識別することを行わせる、請求項１６に記載の非一時的コンピュータ可読媒体。
【請求項１８】
計算システムによって行われる方法であって、
物体構造を記述する空間構造データにアクセスすることであって、前記空間構造データは、前記物体構造について複数の層を示す奥行き情報を有する、ことと、
前記空間構造データから、前記複数の層のうちの一層を表す、前記空間構造データの一部分を抽出することと、
前記空間構造データの前記一部分から、前記層の輪郭を記述する複数の頂点を識別することと、
前記複数の頂点の中から前記層の凸角を識別することと、
前記凸角に従って、物体認識を行うことと、を含み、
前記複数の頂点の中から前記層の前記凸角を識別することは、
（ａ）前記複数の頂点の中から、３Ｄ頂点の集合を識別することと、
（ｂ）前記３Ｄ頂点の集合の中から、３Ｄ角の集合を識別することと、
（ｃ）前記３Ｄ角の集合の中から、前記凸角の少なくとも一部を識別することと、によってなされ、
前記３Ｄ頂点の集合は、定義される閾値長さに等しいかまたはそれを超える、最も近い隣接頂点へのそれぞれの距離を各々有する頂点を含み、
前記３Ｄ頂点の集合は、前記定義される閾値長さよりも短い、最も近い隣接頂点へのそれぞれの距離を有するいかなる頂点を除外し、
前記３Ｄ角の集合は、前記３Ｄ頂点の集合の中から、前記物体構造の直交角を表す３Ｄ頂点を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、空間構造データを処理するための計算システムおよび方法に関連する。特に、本明細書の実施形態は、構造が空間構造データに記述される物体の角の検出に関連する。
【背景技術】
【０００２】
自動化がより一般的になるにつれ、倉庫や製造環境など、より多くの環境でロボットが使用されている。例えば、ロボットは、倉庫でパレットに品物を積む、もしくはパレットから品物を降ろす、または工場でコンベヤベルトから物体を拾い取るように使用されてもよい。ロボットの動きは、固定されていてもよく、または倉庫もしくは工場の中の一つ以上のセンサーにより得られる、空間構造データなどの入力に基づいてもよい。ロボット誘導は、空間構造データに従って行われる物体認識によって補助されうる。それゆえ、物体認識を改善する方法および技術は価値がある。
【発明の概要】
【０００３】
実施形態では、非一時的コンピュータ可読媒体および処理回路を含む計算システムを提供する。処理回路は、物体構造を記述する空間構造データが、非一時的コンピュータ可読媒体に記憶されるとき、次の方法、すなわち、物体構造について複数の層を示す奥行き情報を有する空間構造データにアクセスすることと、空間構造データから、複数の層のうちの一層を表す、空間構造データの一部分を抽出することと、空間構造データの一部分から、層の輪郭を記述する複数の頂点を識別することとを行うように構成される。実施形態では、非一時的コンピュータ可読媒体は、処理回路によって実行されるとき、上述の方法を処理回路に行わせる命令を有する。
【図面の簡単な説明】
【０００４】
【図１】図１Ａから１Ｆは、空間構造感知装置と、本明細書の実施形態と一致する空間構造データにアクセスして処理するための計算システムとを示す。
【図２】図２Ａ〜２Ｃは、本明細書の実施形態と一致する空間構造データを処理するように構成される、計算システムを示すブロック図を提供する。
【図３】図３は、本明細書の実施形態による、空間構造データを処理する方法を示すフロー図を提供する。
【図４】図４Ａ〜４Ｅは、本明細書の実施形態と一致する計算システムの動作の態様を示す。
【図５】図５Ａ〜５Ｇは、本明細書の実施形態と一致する計算システムの動作の態様を示す。
【図６】図６Ａ〜６Ｃは、本明細書の実施形態と一致する計算システムの動作の態様を示す。
【発明を実施するための形態】
【０００５】
本開示は、点群などの空間構造データを処理するためのシステムおよび方法を提供し、より具体的には、空間構造データからの凸角の識別に関する。実施形態では、空間構造データは、一つ以上の物体の構造（物体構造と呼んでもよい）を記述してもよく、凸角は、概して、物体構造の外角に対応してもよい。一部の事例では、凸角は、どんな物体またはどんなタイプの物体が空間構造データによって表されているかの判定を伴いうる、物体認識を行うのに使用されてもよい。空間構造データが、奥行きカメラなどの空間構造感知装置によって得られる場合、物体認識は、どんな物体もしくはどんなタイプの物体であるのか、またはどんな物体もしくはどんなタイプの物体が空間構造感知装置によって感知されたのかを判定してもよい。一部の事例では、ロボット制御システムにより物体認識の出力を使用して、空間構造感知装置により感知されている、一つまたは複数の物体と相互作用するように、ロボットまたは他の機械の動きを誘導してもよい。例えば、ロボットは、倉庫、工場、またはロボットの何らかの他の環境で、物体をつかみ、持ち上げ、および／または移動させるために構成されてもよい。ロボットの動きを誘導することは、種々の形状、サイズ、および／または配向を有しうる種々の物体または物体の種々のタイプに、ロボットの動きを適用させることを伴いうる。より具体的には、こうした誘導を実装することは、ロボットが相互作用しているのが、もしくは相互作用する予定であるのが、どんな物体もしくはどんなタイプの物体であるのかを認識するように、または物体の形状、サイズ、および／もしくは配向を認識するように、物体認識を行うことを伴いうる。ロボット制御システムによる使用に対して、正確な物体認識を提供することによって、ロボット操作の効率および／または有効性が増大しうる。
【０００６】
一つの例では、ロボットは、デパレタイズ動作の一部として、大量の箱など、大量の個々の物体と相互作用してもよい。こうしたシナリオで物体認識を行うのは、個々の物体間の境界、および各物体の角が始まる境界を検出するのが難しい場合があるため、困難でありうる。物体認識は、個々の物体の一つ以上の輪郭、面、縁、および／または角を認識ならびに識別することによって、拡張、またはそうでない場合、改善されうる。より具体的には、物体認識は、物体構造（すなわち、一つ以上の物体の構造）の凸角を識別することによって、強化されてもよい。例えば、物体認識は、空間構造データの中で識別されるすべての点ではなく、凸角のみに依存してもよい。物体認識のために物体自体の凸角を使用することで、十分なレベルの精度が提供されてもよく、物体認識を行うのに必要な時間または処理能力が減少しうる。
【０００７】
実施形態では、凸角の識別は層ごとに行ってもよい。例えば、大量の物体は、複数の層を形成する物体構造を有してもよい。各層は、例えば、物体構造の特定面（例えば、地面に平行な面）を表してもよく、物体構造の他層に対して異なる高さまたは奥行き（depth）を有してもよい。こうした例では、凸角の集合が、物体構造の各層に対して判定されてもよい。実施形態では、凸角は、物体構造の特定層の頂点の中から、またはより広くは、それらに基づいて識別されてもよい。頂点は、層の輪郭を記述する点であってもよく、それゆえ、輪郭点と呼んでもよい。
【０００８】
一部の実装では、凸角の識別には、空間構造データの中のどの頂点が３Ｄ角であるかを判定することを伴ってもよい。３Ｄ角は、直交性基準を満たす３Ｄ頂点であってもよく、３Ｄ頂点は、概して、ノイズ、干渉、または他の誤差源の結果として、空間構造データ中に導入されるアーチファクトである可能性が低い、空間構造データの中の頂点を指してもよい。例えば、空間構造データは、例えば、物体構造の一つ以上の面上の位置である、複数の点を識別、またはそうでない場合、記述する（例えば、座標によって）点群を含んでもよい。点群の中で識別される点の一部は、物体構造の中でいずれの物理的な点にも対応しない、アーチファクトでありうる。言い換えれば、点群の中で識別される一部の点は、構造のそれぞれの頂点として現れてもよいが、空間構造データの中に現れるそれらの頂点が、物体構造上のいずれの実際の物理的頂点も表さない、アーチファクトでありうる。それゆえ、頂点が３Ｄ頂点であるか、または３Ｄ角であるかを判定する一態様は、本明細書では、空間構造データから識別された特定の頂点が、物体構造上の物理的頂点を表すか、または識別された頂点がアーチファクトであるかを判定することに関する。
【０００９】
実施形態では、空間構造データから識別された頂点がアーチファクトであるかの判定は、頂点が一つまたは複数の長さ基準を満たすかに基づいてもよい。長さ基準は、例えば、空間構造データの中の特定の頂点と、その隣接頂点との間の距離が、定義される長さの閾値（また、閾値長さとも呼ぶ）に合致するか、またはそれを超えるかを評価するように使用されてもよい。例えば、アーチファクトを引き起こした、画像ノイズまたは他の誤差の源は、空間構造データの局部的部分にのみ影響を与えうるため、長さ基準は、空間構造データの中にアーチファクトの結果として現れる特徴（例えば、物体構造の縁）が、物体構造データの他の実際の物理的特徴に対して、サイズが小さくなりそうな一部の状況を反映しうる。それゆえ、アーチファクトに起因するか、またはその一部である頂点は、隣接頂点、または何らかの他の隣接する特徴の近くに位置する可能性がありうる。こうした例では、長さ基準を満たさない頂点を、アーチファクトでありそうだとみなしてもよく、無視するか、または凸角を識別するための使用から除外してもよい。一つまたは複数の長さ基準を満たす頂点は、凸角を識別するのに使用するに値しうる。
【００１０】
実施形態では、直交性基準が３Ｄ頂点（または任意の他の頂点）に対して評価されて、３Ｄ頂点が３Ｄ角でありうるかを判定してもよい。より具体的には、頂点は、物体構造の二つの縁の交差であってもよい。この実施形態では、３Ｄ角は、二つの縁が互いに直交、または実質的に直交する（また、実質的に互いに垂直であるとも呼ぶ）、それらの３Ｄ頂点を含んでもよい。凸角の少なくとも一部は、３Ｄ角の中から選択、またはそうでない場合、識別されてもよい。実施形態では、直交性基準はまた、アーチファクトでありうる頂点の検出および除外に寄与してもよい。実施形態では、認識すべき大部分またはすべての物体（例えば、箱）が、直交角を有すると予想される状況では、直交性基準によって物体認識が単純化しうる。
【００１１】
実施形態では、凸角の識別は、３Ｄ角の凸状を判定することを伴いうる。一部の事例では、頂点の凸状は、頂点から離れた方を、および／または二つのそれぞれの隣接頂点の方を指す、二つのベクトルの外積に基づいて判定されてもよい。外積は、二つのベクトルに直交する外積のベクトルであってもよく、またはそれを含んでもよい。この実施形態では、頂点の凸状は、外積のベクトルが定義される方向を指すか、またはそれに沿って指すかに基づいて判定されてもよい。一部の事例では、複数の頂点は、層の輪郭に沿って、時計回りまたは反時計回りに、頂点を経て進行する順番を複数回反復して評価されてもよい。こうした事例では、外積のベクトルが比較される、定義される方向は、複数の反復が時計回りに頂点を経て進行しているか、または複数の反復が反時計回りに頂点を経て進行しているかに基づいてもよい。
【００１２】
実施形態では、頂点が直交性基準を満たさない場合、融合角が生成されてもよい。融合角は、頂点の近くにあり、かつ、頂点に基づいて生成される、直交角であってもよい。例えば、頂点は、実質的には直交しない、第一縁および第二縁の交点にあってもよい。融合角の生成は、第一縁に（または第二縁に）直交する第三縁の識別を伴ってもよい。一部の事例では、縁は、以下で詳述するように、ベクトル、またはベクトルに沿って延びる線に対応してもよい。融合角は凸状である場合、凸角として識別されうる。
【００１３】
一部の例では、物体認識は、凸角に基づいて、検出仮説を生成または修正する判定を伴いうる。一部の例では、物体認識は、凸角に基づく検出仮説のフィルタリングを伴いうる。検出仮説は、例えば、テンプレートのテンプレート特徴を空間構造データへマッピングすることによってなど、空間構造データをテンプレートに一致させる試みに関連してもよい。テンプレートは、物体または物体のタイプに対する物体構造を記述してもよく、テンプレート特徴は、例えば、物体構造の形状、その角もしくは縁、または物体構造の他の特徴を識別してもよい。凸角によって、例えば、テンプレート特徴を空間構造データへマッピングするプロセスが単純化してもよく、および／またはそのマッピングの精度が向上しうる。例えば、物体認識によって、空間構造データの中で識別される点のすべてではなく、凸角とのみ、テンプレート特徴を比較してもよい。
【００１４】
図１Ａは、空間構造データを生成および処理するためのシステム１００を示す（空間構造データは以下で詳述する）。システム１００は、計算システム１０１および空間構造感知装置１５１を含みうる。実施形態では、空間構造感知装置１５１は、空間構造データを生成するように構成されてよく、空間構造データを処理するように構成されうる計算システム１０１が、空間構造データを利用できるようにするよう構成されてもよい。一部の例では、計算システム１０１および空間構造感知装置１５１は、倉庫または工場など、同じ施設の中に位置してもよい。一部の例では、計算システム１０１および空間構造感知装置１５１は、互いと遠隔であってもよい。
【００１５】
実施形態では、空間構造感知装置１５１は、通信インターフェースおよび／またはデータ記憶装置（また記憶装置と呼んでもよい）を介して、空間構造データを利用可能にするように構成されてもよい。例えば、図１Ｂは、図１Ａのシステム１００の実施形態である、システム１００Ａを描写する。システム１００Ａは、計算システム１０１と、空間構造感知装置１５１と、さらにデータ記憶装置１９８（または任意の他のタイプの非一時的コンピュータ可読媒体）とを含む。データ記憶装置１９８は、空間構造感知装置１５１の一部であってもよく、または空間構造感知装置１５１から分離していてもよい。例えば、記憶装置１９８は、空間構造感知装置１５１から遠隔のデータセンターに位置してもよく、空間構造感知装置１５１により生成される空間構造データを、受信および記憶してもよい。この実施形態では、計算システム１０１は、データ記憶装置１９８からデータを読み出す（またはより広くは、受信する）ことによって、空間構造データにアクセスするように構成されてもよい。
【００１６】
図１Ｂでは、記憶装置１９８は、また非一時的コンピュータ可読記憶装置と呼んでもよい、いかなるタイプの非一時的コンピュータ可読媒体（または複数の媒体）を含んでもよい。こうした非一時的コンピュータ可読媒体または記憶装置は、データを記憶し、データへのアクセスを提供するように構成されうる。非一時的コンピュータ可読媒体または記憶装置の例としては、例えば、コンピュータディスケット、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消却可能プログラム可能読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュメモリ）、ソリッドステートドライブ、スタティックランダムアクセスメモリ（ＳＲＡＭ）、携帯型コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、デジタル多目的ディスク（ＤＶＤ）、および／またはメモリスティックなど、電子記憶装置、磁気記憶装置、光記憶装置、電磁記憶装置、半導体記憶装置、またはそれらのいかなる適切な組み合わせが挙げられうるが、これらに限定されない。
【００１７】
実施形態では、計算システム１０１および空間構造感知装置１５１は、ネットワークを介して空間構造データを伝達するように構成されてもよい。例えば、図１Ｃは、図１Ａのシステム１００および／または図１Ｂのシステム１００Ａの実施形態である、システム１００Ｂを描写する。システム１００Ｂでは、計算システム１０１は、空間構造感知装置１５１からネットワーク１９９を介して、空間構造データを受信するように構成されてもよい。ネットワーク１９９によって、計算システム１０１が、本明細書の実施形態と一致する空間構造データを受信可能となるように、個々のネットワーク接続または一連のネットワーク接続が提供されてもよい。
【００１８】
図１Ｃでは、ネットワーク１９９に、有線または無線リンクを介して接続してもよい。有線リンクには、デジタル加入者回線（ＤＳＬ）、同軸ケーブル回線、または光ファイバ回線が含まれてもよい。無線リンクには、Ｂｌｕｅｔｏｏｔｈ（登録商標）、Ｂｌｕｅｔｏｏｔｈ  Ｌｏｗ  Ｅｎｅｒｇｙ（ＢＬＥ）、ＡＮＴ／ＡＮＴ＋、ＺｉｇＢｅｅ、Ｚ−Ｗａｖｅ、Ｔｈｒｅａｄ、Ｗｉ−Ｆｉ（登録商標）、Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ（ＷｉＭＡＸ（登録商標））、モバイルＷｉＭＡＸ（登録商標）、ＷｉＭＡＸ（登録商標）−Ａｄｖａｎｃｅｄ、ＮＦＣ、ＳｉｇＦｏｘ、ＬｏＲａ、Ｒａｎｄｏｍ  Ｐｈａｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ（ＲＰＭＡ）、Ｗｅｉｇｈｔｌｅｓｓ−Ｎ／Ｐ／Ｗ、赤外線チャネル、または衛星バンドが含まれてもよい。無線リンクはまた、２Ｇ、３Ｇ、４Ｇ、または５Ｇの資格がある規格を含む、モバイル機器間を通信する、いかなるセルラーネットワーク規格が含まれてもよい。無線規格は、例えば、ＦＤＭＡ、ＴＤＭＡ、ＣＤＭＡ、またはＳＤＭＡといった、様々なチャネルアクセス方法を使用してもよい。一部の実施形態では、異なるタイプのデータを、異なるリンクおよび規格によって伝送してもよい。他の実施形態では、同じタイプのデータを、異なるリンクおよび規格によって伝送してもよい。ネットワーク通信は、例えば、ｈｔｔｐ、ｔｃｐ／ｉｐ、ｕｄｐ、イーサネット、ＡＴＭなどを含む、いかなる適切なプロトコルによって実施されてもよい。
【００１９】
ネットワーク１９９は、いかなるタイプのおよび／または形態のネットワークであってもよい。ネットワークの地理的範囲は大きく異なってもよく、ネットワーク１９９は、ボディエリアネットワーク（ＢＡＮ）、パーソナルエリアネットワーク（ＰＡＮ）、例えば、イントラネットといったローカルエリアネットワーク（ＬＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、広域ネットワーク（ＷＡＮ）、またはインターネットでありうる。ネットワーク１９９のトポロジーは、いかなる形態であってもよく、例えば、次の、ポイントツーポイント、バス、スター、リング、メッシュ、またはツリーのうちのいずれを含んでもよい。ネットワーク１９９は、本明細書に記載する動作をサポートできる、当業者に既知であるような、いかなるこうしたネットワークトポロジーからなってもよい。ネットワーク１９９は、例えば、イーサネットプロトコル、インターネットプロトコル群（ＴＣＰ／ＩＰ）、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）技術、ＳＯＮＥＴ（Ｓｙｎｃｈｒｏｎｏｕｓ  Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋｉｎｇ）プロトコル、またはＳＤＨ（Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｉｇｉｔａｌ  Ｈｉｅｒａｒｃｈｙ）プロトコルを含む、プロトコルの異なる技術、および層またはスタックを利用してもよい。ＴＣＰ／ＩＰインターネットプロトコル群は、アプリケーション層、トランスポート層、インターネット層（例えば、ＩＰｖ４およびＩＰｖ４を含む）、またはリンク層を含んでもよい。ネットワーク１９９は、放送ネットワーク、電気通信ネットワーク、データ通信ネットワーク、またはコンピュータネットワークの１タイプであってもよい。
【００２０】
実施形態では、計算システム１０１および空間構造感知装置１５１は、ネットワーク接続ではなく直接接続によって通信できうる。例えば、こうした実施形態の計算システム１０１は、ＲＳ−２３２インターフェースなどの専用通信インターフェース、ユニバーサルシリアルバス（ＵＳＢ）インターフェース、および／または周辺構成要素相互接続（ＰＣＩ）バスなどのローカルコンピュータバスを介して、空間構造データを受信するように構成されてもよい。
【００２１】
図１Ｄは、空間構造データを生成および処理するための、システム１００の実施形態でありうるシステム１００Ｃを示す。システム１００Ｃは、計算システム１０１Ａ、空間構造感知装置１５１Ａ、記憶装置１９８、およびネットワーク１９９を含む。空間構造感知装置１５１Ａは、一つ以上の物体１９０の構造を記述する空間構造データを取り込み、またはそうでない場合、生成するように構成される。計算システム１０１Ａは、空間構造データにアクセスして処理するように構成される。図１Ｄの実施形態では、計算システム１０１Ａは、図１Ａの計算システム１０１の実施形態である、デスクトップコンピュータであってもよく、空間構造感知装置１５１Ａは、図１Ａの空間構造感知装置１５１の実施形態である、奥行き感知カメラ（例えば、ＴＯＦカメラまたは構造化光カメラ）であってもよい。さらにこの例では、計算システム１０１Ａは、いかなる適切な手段によって、空間構造データにアクセスしうる。例えば、計算システム１０１Ａは、空間構造感知装置１５１から、記憶装置１９８を介して、ネットワーク１９９上を、および／または直接接続によって、空間構造感知装置１５１Ａへ空間構造データを読み出し（またはより広くは、受信し）てもよい。
【００２２】
実施形態では、上述のように、空間構造データは、ロボットの制御を容易にするように生成されうる。例えば、図１Ｅは、空間構造データを生成および処理し、その処理に基づいてロボット１６１を制御できる、ロボット操作システム１００Ｄ（システム１００の実施形態である）を示す。例えば、空間構造感知装置１５１は、奥行き感知カメラの視野の中の一つ以上の物体の構造を記述する空間構造データを生成するように構成される、奥行き感知カメラであってもよい。計算システム１０１は、空間構造データを受信し、そのデータを使用して、一つ以上の物体のサイズ、形状、位置、および／または配向を判定するように構成されうる。これらの例では、ロボット１６１の動きは、判定されたサイズ、形状、位置、および／または配向に基づいて、一つ以上の物体と相互作用するように制御されうる。
【００２３】
実施形態では、計算システム１０１は、空間構造データの処理から判定した情報に基づいて、ロボット１６１の動きを直接制御するように構成されうる。例えば、計算システム１０１は、判定した情報に基づいて、一つ以上の動きの指令（例えば、運動指令）を生成し、一つ以上の動きの指令をロボット１６１へ伝達するように構成されてもよい。こうした例では、計算システム１０１は、ロボット制御システム（また、ロボットコントローラとも呼ぶ）として作用しうる。
【００２４】
別の実施形態では、計算システム１０１は、計算システム１０１から分離しているロボット制御システムへ、判定した情報を伝達するように構成されてもよく、ロボット制御システムは、その判定した情報に基づいて、（例えば、一つ以上の動きの指令を生成することによって）ロボット１６１の動きを制御するように構成されてもよい。例えば、図１Ｆは、ロボット制御システム１６２を含む、（図１Ａのシステム１００および図１Ｅのシステム１００Ｄの実施形態である）ロボット操作システム１００Ｅを描写する。より具体的には、図１Ｆの計算システム１０１および空間構造感知装置１５１は、ロボット１６１の環境についての、より具体的には、ロボット１６１が操作すべき、または何らかの他の方法で相互作用すべき、その環境の中にある物体についての、情報をロボット制御システム１６２へ提供するよう構成される、視覚システム１５０を形成してもよい。計算システム１０１は、その情報を判定するように、空間構造データを処理するよう構成される視覚コントローラとして機能してもよく、情報は、例えば、物体のタイプ、物体の形状もしくはサイズ、および／またはロボット１６１に対する（例えば、ロボット１６１のロボットアームに対する）物体の位置を示す分類を含みうる。計算システム１０１は、判定した情報をロボット制御システム１６２へ伝達するように構成されてもよく、ロボット制御システム１６２は、計算システム１０１から受信した情報に基づいて、一つ以上の動きの指令を生成するように構成されうる。
【００２５】
上述のように、図１Ａから１Ｆの空間構造感知装置１５１は、空間構造感知装置１５１の環境の中にある、一つ以上の物体の構造を記述する空間構造データを生成するように構成されうる。本明細書で使用する場合、空間構造データは、一つ以上の物理的物体（また、一つ以上の物体とも呼ぶ）の構造を記述する、いかなるタイプのデータ（また、情報とも呼ぶ）を指し、より具体的には、一つ以上の物理的物体の形状、配向、配置、および／またはサイズに関するデータを含みうる。実施形態では、空間構造データは、空間構造感知装置１５１に対する、ロボット１６１に対する、または何らかの他の要素に対する、構造の位置を記述する位置データを含んでもよい。
【００２６】
実施形態では、空間構造データは画像データを含んでもよく、空間構造データに関して本明細書に記載するすべてのシステム、方法、および技術は、別段の明示がない限り、空間構造データの形態である、画像データに等しく適用されてもよい。例えば、空間構造データは、奥行きマップである画像、または奥行きマップを含む画像を含みうる。奥行きマップは、複数のピクセルを有する画像であってもよく、さらに奥行き情報を含む。奥行き情報は、例えば、ピクセルの一部またはすべてに割り当てられた、またはそれらと共に含まれる、それぞれの奥行き値を含みうる。特定のピクセルに対する奥行き値は、そのピクセルによって表される、またはそうでない場合、それに対応する位置の奥行きを示しうる。
【００２７】
より具体的には、奥行き情報（depth information）は、空間構造感知装置１５１が位置する仮想平面に直交する軸に沿った、距離を示す情報を表す。一部の事例では、空間構造感知装置１５１が、画像センサーを有するカメラである場合、仮想平面は、画像センサーにより画定される画像平面であってもよい。実施形態では、奥行き情報は、本明細書で使用する場合、空間構造感知装置１５１から離れている距離を示しうる。実施形態では、空間構造感知装置１５１が位置する仮想平面に平行な、いずれの適切な平面からの相対距離を表すように、奥行き情報を操作してもよい。例えば、適切な平面は、部屋の天井、床、または壁によって、または一つ以上の物体が位置する台によって画定されうる。一つの例では、空間構造感知装置１５１が一つ以上の物体の上方に位置する場合、奥行き情報は、一つ以上の物体が配置される面に対する、一つ以上の物体の様々な点および面の高さを表しうる。別の例では、一つ以上の物体が、空間構造感知装置１５１からずらされるか、またはそうでなくて、そこから水平方向にオフセットされる場合、奥行き情報は、一つ以上の物体が空間構造感知装置から離れて、どのくらい水平方向に遠くへ延びるかを示しうる。実施形態では、空間構造データの奥行き情報は、以下で詳述するように、一つ以上の物体の複数の奥行き層を示してもよく、それらに従って整理されてもよい。複数の奥行き層は複数の層を含み、各々が、空間構造感知装置１５１が位置する仮想平面に直交する軸に沿って測定される、別々の奥行きレベルを示す。一部の実施形態では、各層は単一の奥行き値を表しうる。一部の実施形態では、各層は奥行き値の範囲を表しうる。それゆえ、奥行き情報は、連続して変化する距離測定値を含んでもよいが、奥行き情報のすべてを取り込むように有限個の層が使用してもよい。
【００２８】
実施形態では、空間構造データは点群であってもよい。本明細書で使用する場合、点群は、物体構造を記述する（すなわち、一つ以上の物体の構造を記述する）、複数の点を識別しうる。複数の点は、例えば、物体構造の一つ以上の面上のそれぞれの位置でありうる。一部の事例では、点群は、複数の点を識別する、またはそうでない場合、それらを記述する、複数の座標を含みうる。例えば、点群は、物体構造のそれぞれの位置もしくは他の特徴を指定する、一連のデカルト座標または極座標（または他のデータ値）を含みうる。それぞれの座標は、空間構造感知装置１５１の座標系に関して、または何らかの他の座標系に関して表示されてもよい。一部の事例では、それぞれの座標は離散しており、互いに間隙を介しているが、物体構造の接触面を表すと理解されうる。実施形態では、点群は、奥行きマップまたは他の画像データから（例えば、計算システム１０１によって）生成されうる。
【００２９】
一部の実施形態では、空間構造データはさらに、例えば、ポリゴンまたは三角形メッシュモデル、非一様有理Ｂスプラインモデル、ＣＡＤモデル、プリミティブのパラメータ化（例えば、長方形は中心並びにｘ、ｙ、およびｚの方向の延在部に従って画定されてもよく、円柱は中心、高さ、上半径、および下半径によって画定されうるなど）など、いかなる適切な形式に従って記憶されうる。
【００３０】
上述のように、空間構造データは、空間構造感知装置１５１によって取り込まれ、またはそうでない場合、生成される。実施形態では、空間構造感知装置は、カメラもしくはいかなる他の画像感知装置であってもよく、またはそれを含んでもよい。カメラは、飛行時間（ＴＯＦ）カメラまたは構造化光カメラなどの、奥行き感知カメラであってもよい。カメラは、電荷結合素子（ＣＣＤ）センサーおよび／または相補型金属酸化膜半導体（ＣＭＯＳ）センサーなど、画像センサーを含みうる。実施形態では、空間構造感知装置は、レーザー、ＬＩＤＡＲ装置、赤外線装置、明／暗センサー、モーションセンサー、マイクロ波検出器、超音波検出器、レーダー検出器、または空間構造データを取り込むように構成されるいかなる他の装置を含みうる。
【００３１】
さらに上で言及したように、空間構造感知装置１５１により生成される空間構造データは、計算システム１０１によって処理されてもよい。実施形態では、計算システム１０１は、サーバ（例えば、一つ以上のサーバブレード、プロセッサなどを有する）、パーソナルコンピュータ（例えば、デスクトップコンピュータ、ノートパソコンなど）、スマートフォン、タブレットコンピューティング装置、および／または他のいかなる他の計算システムを含んでもよく、またはそれらとして構成されてもよい。実施形態では、計算システム１０１の機能性のすべては、クラウドコンピューティングプラットフォームの一部として行われてもよい。計算システム１０１は、単一の計算装置（例えば、デスクトップコンピュータ）であってもよく、または複数の計算装置を含んでもよい。
【００３２】
図２Ａは、計算システム１０１の実施形態を示す、ブロック図を提供する。計算システム１０１は、処理回路１１０および非一時的コンピュータ可読媒体（または複数の媒体）１２０を含む。実施形態では、処理回路１１０は、一つ以上のプロセッサ、一つ以上の処理コア、プログラマブルロジックコントローラ（「ＰＬＣ」）、特定用途向け集積回路（「ＡＳＩＣ」）、プログラマブルゲートアレイ（「ＰＧＡ」）、フィールドプログラマブルゲートアレイ（「ＦＰＧＡ」）、それらのいかなる組み合わせ、またはいかなる他の処理回路を含む。実施形態では、非一時的コンピュータ可読媒体１２０は、電子記憶装置、磁気記憶装置、光記憶装置、電磁記憶装置、半導体記憶装置、またはそれらのいかなる適切な組み合わせなどの記憶装置であり、例えば、コンピュータディスケット、ハードディスク、ソリッドステートドライブ（ＳＳＤ）、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消却可能プログラム可能読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュメモリ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、携帯型コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、デジタル多目的ディスク（ＤＶＤ）、メモリスティック、それらのいかなる組み合わせ、またはいかなる他の記憶装置であってもよい。一部の例では、非一時的コンピュータ可読媒体は、複数の記憶装置を含みうる。特定の事例では、非一時的コンピュータ可読媒体１２０は、空間構造感知装置１５１から受信した空間構造データを記憶するように構成される。特定の事例では、非一時的コンピュータ可読媒体１２０はさらに、処理回路１１０によって実行されるときに、処理回路１１０に、図３に関連して記載する操作など、本明細書に記載する一つ以上の手法を行わせる、コンピュータ可読プログラム命令を記憶する。
【００３３】
図２Ｂは、計算システム１０１の実施形態であり、通信インターフェース１３０を含む、計算システム１０１Ａを描写する。通信インターフェース１３０は、例えば、空間構造感知装置１５１から、図１Ｂの記憶装置１９８、図１Ｃのネットワーク１９９を介して、またはより直接的な接続によってなど、空間構造データを受信するように構成されてもよい。実施形態では、通信インターフェース１３０は、図１Ｅのロボット１６１または図１Ｆのロボット制御システム１６２と通信するように構成されうる。通信インターフェース１３０は、例えば、有線または無線プロトコルによって通信を行うように構成される通信回路を含みうる。例として、通信回路は、ＲＳ−２３２ポートコントローラ、ＵＳＢコントローラ、イーサネットコントローラ、Ｂｌｕｅｔｏｏｔｈ（登録商標）コントローラ、ＰＣＩバスコントローラ、いかなる他の通信回路、またはそれらの組み合わせを含んでもよい。
【００３４】
実施形態では、処理回路１１０は、記憶装置１２０上に記憶される一つ以上のコンピュータ可読プログラム命令によってプログラムされてもよい。例えば、図２Ｃは、計算システム１０１の実施形態である、計算システム１０１Ｂを示し、処理回路１１０が、データ管理部２０２、分割管理部２０４、物体識別管理部２０６、および物体認識管理部２０８によってプログラムされる。本明細書で述べるような様々な管理部の機能性は、代表的なものであり、限定ではないことは理解されるであろう。
【００３５】
様々な実施形態では、「ソフトウェアプロトコル」、「ソフトウェア命令」、「コンピュータ命令」、「コンピュータ可読命令」、および「コンピュータ可読プログラム命令」という用語は、様々なタスクおよび動作を遂行するように構成される、ソフトウェア命令またはコンピュータコードを記述するために使用される。本明細書で使用する場合、「管理部」という用語は、処理回路１１０に一つ以上の機能タスクを行わせるように構成される、ソフトウェア命令またはコードの集まりを広く指す。便宜上、実際には、様々な管理部、コンピュータ命令、およびソフトウェアプロトコルによって、様々な動作およびタスクを行うように、ハードウェアプロセッサをプログラムするとき、管理部、コンピュータ命令、およびソフトウェアプロトコルは、それらの動作またはタスクを行っていると記載されるであろう。様々な箇所に「ソフトウェア」として記載するものの、「管理部」、「ソフトウェアプロトコル」、および「コンピュータ命令」によって行われる機能性は、より広くは、ファームウェア、ソフトウェア、ハードウェア、またはそれらのいかなる組み合わせとして実装されてもよいことは理解される。さらに、本明細書の実施形態は、方法ステップ、機能ステップ、およびその他のタイプの発生に関して記載する。実施形態では、これらのアクションは、処理回路１１０によって実行されるコンピュータ命令またはソフトウェアプロトコルに従って発生する。
【００３６】
実施形態では、データ管理部２０２は、計算システム１０１上で動作するソフトウェアプロトコルである。データ管理部２０２は、空間構造データにアクセス（例えば、受信、読み取り、記憶）し、計算システム１０１によって受信または処理（例えば、分析）されている空間構造データに関連する、いかなる他の適切な動作を行うように構成される。例えば、データ管理部２０２は、非一時的コンピュータ可読媒体１２０もしくは１９８の中に、またはネットワーク１９９および／もしくは図２Ｂの通信インターフェース１３０を介して記憶される、空間構造データにアクセスするように構成されてもよい。データ管理部２０２はまた、空間構造データを要求、読み出し、アクセス、送信、記憶するか、またはそうでない場合、それで動作を行うように、ネットワーク１９９を介して他の装置と、データ記憶ユニット１９８と、非一時的コンピュータ可読媒体１２０と、および／または空間構造感知装置１５１と相互作用するように構成されてもよい。
【００３７】
実施形態では、データ管理部２０２はさらに、空間構造データを管理および操作するために、ユーザにアクセスツールを提供するように構成される。例えば、データ管理部２０２は、データベース、テーブル、ファイルリポジトリ、および他のデータ記憶構造へのアクセスを生成ならびに／または提供するように構成されてもよい。実施形態では、データ管理部２０２がデータ保持能力を提供してもよい。データ管理部２０２は、記憶装置１２０、データ記憶ユニット１９８、および他のメモリユニットにアクセスして、空間構造データ、およびコンピュータシステム１０１の処理中に生成される、いかなる他のデータをアーカイブに入れ、記憶し、ならびに／またはそうでない場合、保持するように構成されてもよい。
【００３８】
実施形態では、分割管理部２０４は、制御システム１０１上で動作するソフトウェアプロトコルである。分割管理部２０４は、空間構造データの部分を分割または抽出するように構成されてもよい。例えば、分割管理部２０４は、以下で詳述するように、物体構造の層を表す、空間構造データの一部分を抽出するように構成されてもよい。空間構造データのこうした一部分は、空間セグメントを表してもよく、または空間セグメントと呼んでもよい。
【００３９】
実施形態では、物体識別管理部２０６は、制御システム１０１上で動作するソフトウェアプロトコルである。物体識別管理部２０６は、分割管理部２０４により生成される一つ以上の空間セグメントを受信し、またはそこにアクセスし、さらに処理を提供するように構成される。例えば、物体識別管理部２０６は、以下で詳述するように、物体構造の層の頂点を識別し、頂点に基づいて凸角を識別するように構成されうる。
【００４０】
実施形態では、物体認識管理部２０８は、計算システム１０１上で動作するソフトウェアプロトコルである。物体認識管理部２０８は、検出された凸角に従って、物体認識を行うように構成されてもよい。例えば、物体認識管理部２０８は、以下で詳述するように、凸角を用いて検出仮説を生成、修正、および／またはフィルタリングしてもよい。
【００４１】
図３は、空間構造データを処理するための方法３００の例示的な操作を示す、フローチャートである。一つの例では、方法３００は、大量の物体（例えば、箱または他のパッケージ）が降ろされるデパレタイズ手順の一部であってもよい。例えば、図４Ａは、空間構造データが一連の物体４０１、４０２のために生成される実施形態を示す。物体４０１、４０２は、例えば、ロボット１６１Ａ（図１Ｅおよび１Ｄのロボット１６１の実施形態であってもよい）により積み重ねから降ろされる、箱または他のパッケージの積み重ねであってもよい。空間構造データは、物体４０１、４０２の構造（物体４０１、４０２の物体構造と呼んでもよい）を記述してもよい。図４Ａの例では、物体４０１の上面４１１が物体構造の第一層を形成してもよく、物体４０２の上面４１２が物体構造の第二層を形成してもよい。図４Ｂは、物体４０１、４０２の真上に配置されうる、図４Ａの空間構造感知装置１５１Ａの観点からの物体４０１、４０２を示す。この観点からは、物体４０１および４０２の上面４１１および４１２のみがそれぞれ、空間構造感知装置１５１Ａから見ることができる。面４１１および４１２は、台４１０と平行で、かつ、奥行き寸法と垂直であり、奥行きは、台４１０と直交し、かつ、軸４８０と平行な寸法でありうる。図４Ｃに関して以下で詳述するように、空間構造感知装置１５１Ａにより生成される空間構造データは、上面４１１および４１２が、空間構造感知装置１５１Ａに対して異なる奥行きにあり（図４Ａの軸４８０に沿って測定する場合）、台４１０に対して異なる高さにあることを示しうる。
【００４２】
実施形態では、図３の方法３００は、物体構造を記述する空間構造データが計算システム１０１の非一時的コンピュータ可読媒体（例えば、１２０）に記憶されているとき、図２Ａから２Ｃの計算システム１０１によって、より具体的には、処理回路１１０によって行われてもよい。実施形態では、図２Ａから２Ｃの非一時的コンピュータ可読媒体１２０はさらに、処理回路１１０によって実行されるとき、処理回路１１０に方法３００を実施させる複数の命令（例えば、コンピュータプログラム命令）を記憶しうる。実施形態では、方法３００は、空間構造データから凸角を識別し、後続の（または同時に起こる）物体認識動作のために凸角を使用することを伴いうる。
【００４３】
実施形態では、図３の方法３００は、（図２Ａ〜２Ｃの）計算システム１０１の処理回路１１０が、物体構造を記述する空間構造データにアクセスする動作３０２を含む。一部の事例では、動作３０２は、図２Ｃのデータ管理部２０２によって行われてもよい。実施形態では、空間構造データへのアクセスは、非一時的コンピュータ可読媒体１２０から、またはいかなる他の装置から、空間構造データを読み取る（またはより広くは、受信する）ことを伴いうる。一部の状況では、空間構造データは、空間構造感知装置１５１から、図２Ｂの通信インターフェース１３０を介してなど、計算システム１０１によって受信されていてもよく、空間構造データに一時的バッファまたは長期記憶装置を提供しうる、非一時的コンピュータ可読媒体１２０に記憶されていてもよい。例えば、空間構造データは、空間構造感知装置１５１から受信され、非一時的コンピュータ可読媒体１２０に記憶される、点群を含みうる。点群は、それから、動作３０２で処理回路１１０によってアクセスされうる。
【００４４】
一部の状況では、アクセスされる空間構造データは、非一時的コンピュータ可読媒体１２０に記憶されてもよく、空間構造感知装置１５１から受信する情報に基づいて、処理回路１１０自体によって事前に生成されていてもよい。例えば、処理回路１１０は、空間構造感知装置１５１から受信する未加工のセンサーデータに基づいて、点群を生成するように構成されてもよく、生成された点群を非一時的コンピュータ可読媒体１２０に記憶するように構成されてもよい。点群は、次に、動作３０２で処理回路１１０によってアクセスされてもよい（例えば、非一時的コンピュータ可読媒体１２０からデータを読み出すことによって）。
【００４５】
上述のように、空間構造データは、図４Ａの物体４０１、４０２など、一つ以上の物体の構造を記述しうる。実施形態では、空間構造データは、複数のピクセル［ｕ，ｖ］を有しうる奥行きマップを含んでよく、複数のピクセルの一部またはすべては、奥行き値を有しうる。奥行きマップの中のピクセルの各々は、取り込まれるか、またはそうでない場合、ピクセルにより表される、それぞれの物理的位置に対応してよく、奥行き値は、空間構造感知装置（例えば、図４Ａの１５１Ａ）からの距離、およびその物理的位置を示しうる。物理的位置は、例えば、物体４０１、４０２の面、または物体４０１、４０２が位置する台４１０の面上であってもよい。一部の事例では、距離は、空間構造感知装置１５１Ａが位置する仮想平面４３０に直交する軸４８０に沿って測定されてもよい。一部の事例では、ピクセル［ｕ，ｖ］に割り当てられる奥行き値は、対応する物理的位置の座標のＺ成分を表しうる。例えば、空間構造感知装置１５１Ａは奥行き感知カメラであってもよい。こうした例では、奥行きマップの中の特定のピクセル［ｕ，ｖ］は、物体４０１、４０２または台４１０の面の物理的位置に対応してもよく、物理的位置は、Ｘ成分およびＹ成分が、奥行き感知カメラの逆射影行列に基づき、Ｚ成分が、ピクセル［ｕ  ｖ］に割り当てられる奥行き値と等しいか、またはそうでない場合、当該奥行き値に基づく、座標［Ｘ，Ｙ，Ｚ］を有する（座標［Ｘ  Ｙ  Ｚ］は奥行き感知カメラの座標系の中にあってもよい）。
【００４６】
実施形態では、空間構造データは点群を含んでもよい。上述のように、点群は、図４Ａの物体４０１、４０２の一つ以上の面上の物理的位置など、物体構造上の物理的位置である、複数の点を識別する複数の座標を含みうる。実施形態では、空間構造データは、点群を含む場合、一部のシナリオでは、上述した奥行きマップに基づいて（例えば、空間構造感知装置１５１または計算システム１０１によって）生成されうる。
【００４７】
図４Ｃは、図４Ａの物体４０１、４０２の物体構造を表す点群の例を示す。より具体的には、図は点群によって表される複数の点を示す。複数の点は、物体４０１、４０２の一つ以上の面上の物理的位置であってもよい。点群は、複数の点の各々に対するそれぞれの座標（例えば、［Ｘ  Ｙ  Ｚ］座標）を含みうる。点群によって表される物理的な点の密度は、空間構造感知装置１５１／１５１Ａの分解能に応じて、図４Ｃに示すものより大きくても、または小さくてもよい。特定の点の座標のＺ成分は、その点の奥行き値を表しうる。図４Ｃの例では、点群によって、物体４０１の図４Ａの上面４１１上の物理的な点に対して、奥行き値Ｚ＝Ｚ１（例えば、１５０ｃｍ）を識別し、物体４０２の図４Ａの面４１２上の物理的な点に対して、奥行き値Ｚ＝Ｚ２（例えば、２００ｃｍ）を識別し、図４Ａの台４１０の面上の物理的な点に対して、奥行き値Ｚ＝Ｚ３（例えば、２６０ｃｍ）を識別しうる。
【００４８】
実施形態では、空間構造データは、一つ以上の物体（例えば、４０１、４０２）の構造の複数の層を示す奥行き情報を有してもよい。一部の事例では、各層は、同じ奥行き値または実質的に同じ奥行き値を有する、構造上の点（例えば、物理的位置）を示してもよく、もしくは含んでもよく、または漸進的な量だけ、および／もしくは円滑に連続して（急激または唐突な様式とは対照的に）、奥行き値が変化する構造上の点を示してもよい。例えば、図４Ｃは、物体４０１の上面４１１を表す第一の点の集合４１１ａを識別し、物体４０２の上面４１２を表す第二の点の集合４１２ａを識別し、台４１０の上面を表す第三の点の集合４１０ａを識別する、点群に関する。この例では、第一の点の集合４１１ａは同じ奥行き値Ｚ１を有し、それゆえ、物体構造の第一層を表してもよい。同様に、第二の点の集合４１２ａはすべて、同じ奥行き値Ｚ２を有してもよく、一方で、第三の点の集合４１０ａはすべて、同じ奥行き値Ｚ３を有してもよく、それゆえ、第二の点の集合４１２ａおよび第三の点の集合４１０ａは、一つ以上の物体４０２および台４１０に対して、物体構造の第二層および第三層をそれぞれ表しうる。上述のように、各層は物体構造の異なる面に対応しうる。例えば、第一層は図４Ａの上面４１１に対応してもよく、第二層は上面４１２に対応してもよい。一部の事例では、層は、仮想平面４３０など、空間構造感知装置１３０の画像平面に平行な面のみに対応しうる。
【００４９】
実施形態では、点群（または他の形態の空間構造データ）により表される点は、奥行き値の急激な変化に基づいて、異なる層に分けられうる。変化は、例えば、定義される閾値を超える変化の絶対値、または変化率を有する場合、急激とみなされうる。例えば、図４Ｃの点群が表す点は、第一集合点４１１ａと第二の点の集合４１２ａとの間の変化Ｚ２−Ｚ１（例えば、５０ｃｍ）を含み、第二の点の集合４１２ａと第三の点の集合４１０ａとの間、より具体的には、隣接する点の間の変化Ｚ３−Ｚ２（例えば、６０ｃｍ）を含む。こうした変化は、定義される閾値（例えば、０．５ｃｍまたは１ｃｍ）を超える場合があり、それゆえ、急激な変化とみなされうる。急激な変化から、第一の点の集合４１１ａ、第二の点の集合４１２、および第三の点の集合４１０ａは、物体構造の異なる層上にあるとみなされうる。
【００５０】
図３に戻って参照すると、方法３００はさらに、計算システム１０１の処理回路１０１が動作３０４を含んでよく、かかる動作は、空間構造データから、複数の層のうちの一層を表す、空間構造データの一部分（一部分はまた、空間セグメントと呼んでもよい）を抽出する。実施形態では、動作３０４は分割管理部２０４によって行われてもよい。空間構造データが、グレースケール画像またはカラー画像など、一つ以上の物体の画像を取り込む場合、空間構造データから抽出される一部分もまた、画像セグメントと呼ばれうる。一部の実装では、抽出される一部分は、物体構造の複数の層のうちの一層のみを表しうる。
【００５１】
図４Ｄは、動作３０４によって、点群または他の空間構造データから、物体構造の第一層４２１を表す第一部分を抽出し、物体構造の第二層４２２を表す第二部分を抽出する例を描写する。第一部分は、第一の点の集合４１１ａ、すなわち、より具体的には、それらの点を表す座標の第一集合を含みうる。第二部分は、第二の点４１２ａ、および、より具体的には、第二の点の集合４１２ａを表す座標の第二集合を含みうる。図４Ｅはまた、抽出される第一層４２１および第二層４２２を示し、さらに、第一層４２１の輪郭４２３および第二層４２２の輪郭４２４を示す。それゆえ、実施形態では、空間構造データは、物体構造の一つ以上の面上のそれぞれの位置である、複数の点を識別する点群を含み、抽出される空間構造データの一部分は、特定層を表す点の集合を識別する。
【００５２】
実施形態では、動作３０４は、同じ奥行き値を有する、または奥行き値が定義される範囲内である、点の集合を識別するデータ値（例えば、座標）を、空間構造データから抽出することを伴ってもよい。例えば、図４Ｃおよび４Ｄの例に対する動作３０４は、第一の点の集合４１１ａが同じ奥行き値を有するため、その例の中の空間構造データから、第一の点の集合４１１ａを識別することを伴ってもよい。同様に、動作３０４は、代替としてまたは加えて、第二の点の集合４１２ａが同じ奥行き値を有するため、空間構造データから、第二の点の集合４１２ａを識別することを伴ってもよい。
【００５３】
実施形態では、動作３０４で抽出される一部分（空間セグメントと呼んでもよい）は、複数の層のうちの一層に対応する、定義される範囲内に入る奥行き値を有する空間構造データの一部分を表しうる。動作３０４が完了すると、各空間セグメントは、複数の層のうちの異なる層を表しうる。実施形態では、すべての複数の層のすべてまたは一部が、空間セグメントによって表されてもよい。実施形態では、一つ以上の物体の構造の一部の層には、適切な奥行きに対応する面がなく、そのため、対応する空間セグメントがない場合がある。さらなる例では、（例えば、分割管理部２０４によって）動作３０４で抽出される空間セグメントの数は、空間構造データによって表される検出された層の数に対応するであろう。
【００５４】
実施形態では、動作３０４は、異なるレベルの物体構造を表す、もしくはその物体構造に対する異なるそれぞれの奥行きの面を表す部分またはセグメントに、空間構造データを分ける計算システム１０１を伴ってもよい。一部の事例では、空間構造データを分けることは、異なる奥行き値を有する空間構造データのそれぞれの部分を識別することに基づいてもよい。一部の事例では、空間構造データを分けることは、空間構造データの部分の中で、奥行き値の急激な変化を検出することに基づいてもよい。例えば、図４Ｄに対する動作３０４を行うことは、奥行き値Ｚ１から値Ｚ２へ、この例の空間構造データの二つの点の集合の間における、奥行き値の急激な変化を検出することを伴いうる。二つの集合は、第一の点の集合４１１ａおよび第二の点の集合４１２ａとして識別されうる。
【００５５】
実施形態では、動作３０４は、傾斜面を持つ構造を有する一つ以上の物体に対処しうる。傾斜面は、例えば、空間構造感知装置１５１／１５１Ａと平行でなく、より具体的には、例えば、図４Ａの仮想平面４３０といった、空間構造感知装置１５１／１５１Ａの画像平面と平行ではない、面であってもよい。それゆえ、傾斜面は、面全体にわたって、空間構造感知装置１５１／１５１Ａに対して異なる奥行き値を有してもよい。実施形態では、層は、こうした傾斜面を収容するように選択されてもよい。例えば、層は、傾斜面全体を含む空間分割のために選択されうる。それゆえ、空間構造データの中の層は、傾斜面が単一の空間セグメントによって包含されることを、特に保証するように選択されうる。
【００５６】
上述のように、動作３０４で抽出されている空間構造データの一部分もまた、空間セグメントと呼んでもよい。実施形態では、抽出されている空間セグメントは、マスクとして（例えば、分割管理部２０４によって）記憶されてもよい。各マスクは、一つ以上の物体の物体構造のそれぞれの層の一部である、一つ以上の領域を指定する情報を含んでもよく、物体構造のそれぞれの層の一部でないすべての領域を除外してもよい。言い換えれば、マスクは、所与の奥行きにある構造の一部である、一つ以上の領域を指定する情報を含んでもよく、所与の奥行きにある構造の一部でない、すべての領域を除外してもよい。各空間セグメントは、例えば、図１Ｂのデータ記憶装置１９８、または他の非一時的コンピュータ可読記憶媒体に記憶されてもよい。実施形態では、空間セグメントは、分割管理部２０４から直接、またはデータ記憶装置１９８もしくは図２Ａの非一時的コンピュータ可読媒体１２０を介してのいずれかで、図２Ｃの物体識別管理部２０６によって、さらなる処理のために受信されてもよい。
【００５７】
図３に戻ると、方法３００は、計算システム１０１の処理回路１１０が動作３０６を含んでよく、かかる動作は、動作３０４で抽出された空間構造データの一部分から、動作３０４に関して述べた層の輪郭を記述する複数の頂点（また、輪郭点とも呼ぶ）を識別する。例えば、図５Ａは、層４２２に対して抽出される複数の頂点５１２ａ〜５１２ｆを示す。実施形態では、動作３０６は物体識別管理部５０６によって行われてもよい。
【００５８】
上述したように、一部の事例では、空間構造データは、物体構造の面上の点を識別する点群を含む。動作３０４で層を表す点群から抽出される一部分は、点群によって識別される複数の点から抽出される、点の集合（例えば、図４Ｄの点４１２ａ）を識別しうる。こうした事例では、処理回路１１０は、例えば、層（例えば、４２２）を表す点の集合の縁（例えば、真っ直ぐな縁）を形成する複数の線分を識別し、動作３０６の複数の頂点を線分の終点として識別することによって、動作３０６を行ってもよい。例えば、図５Ｂは、点の集合４１２ａの真っ直ぐな縁を形成する複数の線分５１３ａ〜５１３ｆを描写する。線分の各々は、二つのそれぞれの終点により画定される、二つの対向端部を有する線であってもよい。例えば、線分５１３ａは、動作３０６で二つの頂点として識別されうる、終点５１２ａおよび５１２ｂにより画定される二つの対向端部を有する。一部の事例では、特定の線分は、図５Ｂに示すように、点の集合４１２ａの縁点を通って延びる場合、縁とみなされうる。点の集合の（例えば、集合４１２ａの）縁点は、点の集合の周縁上にある、それらの点でありうる。より広くは、縁点は、特定層の一つ以上の外縁を表す点であってもよい。一部の事例では、特定の線分は、縁点の近くであってもよく、点の集合のいくつかの点が、その線分をわずかに越えて延びる場合であっても、縁とみなされうる。一部の事例では、特定の線分は、点の集合のうち、その線分を越えて延びる点が全くない場合のみ、縁とみなされうる。
【００５９】
一部の事例では、処理回路１１０は、点の集合（例えば、４１２ａ）の中から複数の縁点を抽出（またはより広くは、識別）し、複数の縁点を通り抜ける複数の線を判定することによって、動作３０６を行いうる。こうした事例では、処理回路１１０は、複数の線が交差する交点を、複数の頂点として識別しうる。例えば、図５Ｃは、動作３０４から抽出された空間構造データの一部分の複数の縁点を通り抜ける複数の線５１４ａ〜５１４ｅを示す。例として、線５１４ｆは、図５Ｃの縁点５１５の輪郭に近似するように合わせた線であってもよい。図は、層の全体の輪郭を囲む、層４２２の縁点の一部分のみを示す。図５Ｃはさらに、線５１４ａ〜５１４ｅの間の交差する点として、複数の頂点５１２ａ〜５１２ｆを描写する。例えば、頂点５１２ａは、線５１４ａと線５１５ｆとの間の交点であってもよい。動作３０６で識別される複数の頂点（例えば、５１２ａ〜５１２ｆ）は、上述した線の間の交差する点のすべて（例えば、線５１４ａ〜５１４ｆ）、または交差する点の部分集合のみを含みうる。
【００６０】
実施形態では、取り込まれる空間構造データにより表される縁点５１５は、一直線に並ばない場合がある。こうした実施形態では、動作３０６は、縁点のそれぞれの位置に最も近似するように、（例えば、物体識別管理部２０６によって）線５１４ａ〜５１４ｆの集合を合わせることを伴いうる。線の集合を合わせるプロセスは、例えば、最小二乗解析およびその他を含む、線５１４ａ〜５１４ｆを縁点５１５に合わせる、いかなる適切なアルゴリズムをも使用しうる。線５１４ａ〜５１４ｆを生成した後、複数の頂点５１２ａ〜５１２ｆは、線５１４ａ〜５１４ｆの交差部に従って識別されうる。線５１４ａ〜５１４ｆのうちの二つ以上が交差する交点の各々または一部は、層４２２の頂点５１２ａ〜５１２ｆのうちの一つとして画定、またはそうでない場合、識別されてもよい。それゆえ、複数の頂点５１２ａ〜５１２ｆは層の輪郭を画定しうる。実施形態では、図５Ｂに示す技術を使用して識別される複数の頂点は、図５Ｃに示す技術を使用して識別される複数の頂点と同じであってもよい。
【００６１】
図３に戻ると、方法３００は、計算システム１１０の処理回路１１０が、複数の頂点に基づいて層の凸角を識別する動作３０８を含みうる。実施形態では、動作３０８は物体識別管理部２０６によって行われてもよい。凸角は、例えば、物体認識を行う起点とするのに、より都合が良いか、より効率的であるか、もしくはより効果的である、物体構造上の物理的位置、もしくは一つ以上の物体とロボット（例えば、図１Ｆの１６１）との間で相互作用するのが都合のよい場合がある物理的位置であってもよいか、またはそれらを表してもよい。一部のシナリオでは、物体構造が、箱または他の直方体を含む場合、凸角は、例えば、直方体の外角の一部またはすべてを含んでもよく、一部のシナリオでは、凸角は、それらの位置のみを含んでも、または表してもよい。一部のシナリオでは、物体構造の凸角は、その角のみで物体構造と交差する平面を描くことができる外角であってもよい。以下で詳述するように、凸角を識別する一部の実施形態は、凸状である３Ｄ角の識別を伴ってもよい。３Ｄ角は、以下で詳述するように、直交性基準を満たす３Ｄ頂点であってもよい。３Ｄ頂点は、以下でまた詳述するように、第一長さ基準および／または第二長さ基準を満たす頂点であってもよい。第一長さ基準、第二長さ基準、および直交性基準は、より広くは、第一基準、第二基準、および第三基準とそれぞれ呼んでもよい。一部の実施形態では、凸角の識別は、以下でまた詳述する、一つ以上の融合角の判定、またはそうでない場合、識別を伴ってもよい。
【００６２】
実施形態では、動作３０８は、複数の頂点（動作３０６から識別されるものなど）の中から二つ以上の頂点間の、少なくとも一つまたは複数の距離を示す関係を判定することを伴いうる。その動作はさらに、その関係に従って、複数の頂点の部分集合を３Ｄ角として識別し、凸状である３Ｄ角を凸角として識別することを伴いうる。一部の事例では、その関係はさらに、ベクトルの対によって形成される、それぞれの角度を示し、ベクトルの各々は、複数の頂点のうちの一対の頂点の間を延びる。
【００６３】
実施形態では、３Ｄ角は、以下で詳述するように、直交性基準を満たす３Ｄ頂点であってもよい。動作３０８は、頂点間の関係に基づいて、３Ｄ頂点の集合の識別を伴いうる。３Ｄ頂点は、概して、アーチファクトである可能性が低い頂点でありうる。より具体的には、ノイズ、干渉、または誤差の他の源によって、動作３０２でアクセスされる空間構造データにアーチファクトが導入されうる。空間構造データのアーチファクトである頂点は、物体構造上の物理的頂点を表さない、空間構造データの一部分を指す。こうした頂点は、３Ｄ頂点の集合から除外されうる。一部の事例では、３Ｄ角の集合は、３Ｄ頂点の集合の中から識別され、凸角の少なくとも一部が、以下で詳述するように、３Ｄ角の中から識別されてもよい。
【００６４】
３Ｄ頂点の集合は、一部の実装では、定義される長さの閾値（また、閾値長さとも呼ぶ）に等しいか、またはそれを超える隣接頂点へのそれぞれの距離を各々有する、頂点を含みうる。３Ｄ頂点の集合はさらに、定義される長さの閾値よりも短い、隣接頂点へのそれぞれの距離を有する、いかなる頂点も除外しうる。言い換えれば、空間構造データはセンサーデータに基づいていて、それゆえに、ノイズ、誤差、アーチファクト、および他の不完全性に左右されるため、複数の識別された頂点は、完全な精度では、一つ以上の物体の構造の角または他の物理的特徴を表すことはできない。例えば、物体は、直方体（また、長方形の箱とも呼ぶ）の構造を、その構造の一層上に四つの頂点を伴って有してもよいが、その物体の構造の空間構造データは、層が七つの頂点を有することを示しうる。それゆえ、アーチファクトである可能性が低い頂点である、空間構造データの３Ｄ頂点を、空間構造データの中のアーチファクトでありそうな頂点から区別するように、動作を行ってもよい。
【００６５】
一部の事例では、この動作は一つ以上の長さ基準に基づいて行われる。一つ以上の長さ基準によって、特定の頂点から隣接頂点（例えば、最も近い隣接頂点）までの距離が、定義される閾値を超えるかを評価しうる。例えば、二つの頂点が、（例えば、閾値長さおよび／または長さ基準に基づくと）空間構造データの中で互いに近すぎる場合、アーチファクトを引き起こすノイズまたは干渉が、空間構造データ内で局在化されうるため、頂点のうちの一つがアーチファクトとなる場合があり、それゆえ、アーチファクトであるか、またはアーチファクトの結果として現れるいかなる特徴も、物体構造の実際の物理的特徴に対して、サイズが小さくなりうる。それゆえ、以下で詳述するように、一つ以上の長さ基準は、３Ｄ頂点の集合の中でどの頂点を３Ｄ頂点として含めるべきかを識別するように使用されうる。さらに、３Ｄ角の集合は、３Ｄ頂点の集合の中から、物体構造の直交角を表す３Ｄ頂点を含んでもよい。
【００６６】
実施形態では、動作３０８は、上述した長さ基準および／または直交性基準に基づいて、（動作３０６の）複数の頂点の各頂点が３Ｄ角であるかの（例えば、物体識別管理部２０６による）判定を伴う。こうした判定はさらに、複数の頂点の各頂点に対して、その頂点と、複数の頂点からの少なくとも一つの他の頂点との間の関係、またはその頂点と、二つの他の頂点（例えば、二つの最も近い隣接頂点）との間の関係を判定することを伴いうる。
【００６７】
実施形態では、動作３０８の一部として３Ｄ角を識別することは、複数の頂点のうちの第一頂点を、３Ｄ角の集合の中に含むかの判定を伴いうる。例として、図５Ｄで第一頂点は頂点５１２ｂであってもよい。一部の事例では、動作３０８は、複数の頂点のすべてを評価する複数の反復を伴い、複数の頂点が３Ｄ頂点であるかを判定し、および／または３Ｄ角であるかを判定してもよく、第一頂点は、例えば、反復のうちの一つの一部でありうる。反復は、例えば、時計回りまたは反時計回りで層４２２の輪郭４２３に続く順番に、複数の頂点を経て進行しうる。こうした事例では、第一頂点は、その特定の反復に対して、現在の頂点または現在の輪郭点（ｃＶｘまたはｃＰｔと呼んでもよい）であってもよい。
【００６８】
第一頂点が３Ｄ角であるかどうかという上記判定は、複数の頂点の中から、層の輪郭に沿う第一方向で、第一頂点に最も近い隣接頂点である第二頂点の（例えば、物体識別管理部２０６による）選択を伴ってもよい。例えば、第二頂点は、層４２２の輪郭４２３に沿う第一方向Ａ（例えば、破線矢印により図示するような、反時計回りの方向）で、頂点５１２ｂに最も近い隣接頂点（また、最も近接の隣接頂点とも呼ぶ）である頂点５１２ａであってもよい。上述のように、動作３０８は、頂点が３Ｄ頂点であるかを判定し、および／または頂点が３Ｄ角であるかを判定するように、複数の頂点の各頂点を評価するために、（例えば、時計回りに）動作３０６で識別される複数の頂点を経て進行する複数の反復を伴いうる。この例では、第二頂点は、前の頂点または前の輪郭点（ｐＶｘまたはｐＰｔと呼ぶ）でありうる。前の頂点は、前の反復（例えば、前の連続する反復）で評価された頂点であってもよい。例えば、現在の反復が、３Ｄ角であるかを判定するために、頂点５１２ｂを評価している場合、頂点５１２ｂは現在の頂点であってもよく、頂点５１２ａは前の頂点であってもよい。さらに、この例の頂点５１２ｃが次の頂点であってもよい。次の頂点または次の輪郭点は、頂点が３Ｄ頂点であるかを判定し、および／またはその頂点が３Ｄ角（ｎＶｘまたはｎＰｔと呼んでもよい）であるかを判定するように、次の連続する反復で評価されるであろう、頂点であってもよい。
【００６９】
第一頂点が３Ｄ角であるかどうかを判定する上述の実施形態はさらに、第一頂点から第二頂点まで（およびそれゆえ、第一頂点から離れた点）である第一ベクトルの画定を伴いうる。例えば、図５Ｄで第一ベクトルはベクトル５５１であってもよい。図５Ｄの第一ベクトル５５１は、一部の事例では、線分が方向性を有する、図５Ｂの線分５１３ａのバージョンであってもよい。一部の例では、第一頂点が第一座標［Ｘ１，Ｙ１，Ｚ１］によって表され、第二頂点が第二座標［Ｘ２，Ｙ２，Ｚ２］によって表される場合、第一ベクトル
【数１】
0006692107.tif 000002
は＜Ｘ２−Ｘ１，Ｙ２−Ｙ１，Ｚ２−Ｚ１＞として定義されてもよい。一部の事例では、頂点がそれぞれの座標に対して同じＺ成分を有する場合、Ｚ成分は無視されうる。こうした事例では、第一ベクトル
【数２】
0006692107.tif 000003
は＜Ｘ２−Ｘ１，Ｙ２−Ｙ１＞と定義されてもよい。一部の事例では、第一ベクトルは、現在の頂点または現在の輪郭点（ｃＶｘまたはｃＰｔ）から、前の頂点または前の輪郭点（ｐＶｘまたはｐＰｔ）までである。
【００７０】
第一頂点が３Ｄ角であるかどうかを判定する上述の実施形態はさらに、複数の頂点の中から、層の輪郭に沿う第二方向において、第一頂点に最も近い隣接頂点である第三頂点の選択を含んでもよく、第二方向は上述の第一方向とは異なる。例えば、第三頂点は、一部分／空間セグメントにより画定される層の輪郭４２３に沿う第二方向Ｂ（例えば、破線矢印により図示するような、時計回りの方向）で、頂点５１２ｂの最も近くに隣接する、図５Ｄの頂点５１２ａであってもよい。第二方向Ｂは第一方向Ａとは異なる。より具体的には、図５Ｄの第一方向Ａは、反時計回りに図の層の輪郭４２３をたどる、流れの方向であってもよく、一方、第二方向Ｂは、時計回りに輪郭４２３をたどる、流れの方向であってもよい。一部の事例では、第三頂点は、次の頂点または次の輪郭点（ｎＶｘまたはｎＰｔと呼ぶ）でありうる。さらに、第二ベクトルをこの実施形態で判定してもよく、第二ベクトルは第一頂点から第三頂点までである（それゆえ、第一頂点から離れた点でもある）。例えば、第二ベクトルは、頂点５１２ｂから頂点５１２ｃまでである、図５Ｄのベクトル５５２であってもよい。上記の例と同様に、第三頂点が第三座標［Ｘ３，Ｙ３，Ｚ３］によって表される場合、第二ベクトル
【数３】
0006692107.tif 000004
は＜Ｘ３−Ｘ１，Ｙ３−Ｙ１，Ｚ３−Ｚ１＞と定義されてもよい。一部の事例では、第二ベクトルは、現在の頂点または現在の輪郭点から、次の頂点または次の輪郭点まででありうる。
【００７１】
上記の実施形態はさらに、第一ベクトル
【数４】
0006692107.tif 000005
が第一長さ基準を満たすか、および第二ベクトル
【数５】
0006692107.tif 000006
が第二長さ基準を満たすかどうかの判定を伴いうる。こうした判定は、第一ベクトルの長さ（第一長さと呼びうる）と、定義される閾値長さとの比較、および第二ベクトルの長さ（第二長さと呼びうる）と、定義される長さの閾値との比較を伴いうる。第一長さは、例えば、頂点５１２ｂから頂点５１２ａまでの距離でありうる。一部の例では、第一ベクトルが、現在の頂点ｃＶｘから前の頂点ｐＶｘまでのベクトルである場合、第一長さは、Ｎｏｒｍ（ｃＶｘ−ｐＶｘ）と定義されてよく、「ノルム（Ｎｏｒｍ）」は二点間のユークリッド距離を判定する関数である。第二長さは、例えば、頂点５１２ｂから頂点５１２ｃまでの距離でありうる。一部の例では、第二ベクトルが、現在の頂点ｃＶｘから次の頂点ｎＶｘまでのベクトルである場合、第二距離はＮｏｒｍ（ｃＶｘ−ｎＶｘ）と定義されてよい。上述のように、ベクトルの長さを閾値長さと比較することによって、第一頂点（例えば、５１２ｂ）が、第二頂点（例えば、５１２ａ）および第三頂点（例えば、５１２ｃ）から十分遠く離れて、第一頂点がアーチファクトである可能性は低いと判定することを保証する。一部の事例では、頂点は、第一長さ基準および第二長さ基準を満たす場合、３Ｄ頂点であるとみなされうる。一部の事例では、頂点は、第一長さ基準および第二長さ基準のいずれか一方を満たさない場合、または第一長さ基準および第二長さ基準の両方を満たさない場合、３Ｄ頂点ではない（および、それゆえ３Ｄ角ではない）と判定される。頂点は、３Ｄ頂点ではないと判定される場合、凸角を識別するための使用から除外されうる。例えば、処理回路１１０は、凸角を識別するとき、頂点を無視してもよく、これは以下で詳述する。一部の事例では、処理回路１１０は、３Ｄ頂点ではない、こうした頂点に対応するデータ値を、空間構造データから除去するように構成されてもよい。
【００７２】
上記の例の閾値長さは、いくつかの技術のうちの一つ以上によって判定されてもよく、またはそうでない場合、定義されてもよい。実施形態では、閾値長さは、ユーザ、管理部、または図１Ａ〜１Ｃの計算システム１０１の操作者によって予め決められてもよい。閾値長さは、図１Ａ〜１Ｃの空間構造感知装置１５１により感知されている、もしくは感知されるであろう物体または物体タイプの知識に従って、予め決められてもよい。例えば、物体が、長さが最小と予想される縁を有すると分かっている場合、最小と予想される長さよりも小さい縁を形成する、空間構造データの頂点を排除するか、またはそうでない場合、フィルタリングして取り除くように、閾値長さを選択してもよい。一部の事例では、閾値長さは、空間構造感知装置１５１に関する知識（例えば、装置１５１が属する空間構造感知装置のタイプに対する、精度のレベルに関する知識）に基づいて判定されうる。
【００７３】
実施形態では、最小と予想される長さに補正係数を乗じて、閾値長さに達しうる。補正係数は、例えば、０と１との間の予め決められたスカラー値であってよい。補正係数は、空間構造データのノイズ量に応じて判定されうる。空間構造データにノイズが多い場合、補正係数はより小さい数でありうる。ノイズが多い空間構造データでは、空間構造データの中に、より多くの数のアーチファクトである頂点があろうと予想される。より多くのアーチファクトをフィルタリングして取り除くために、より小さい補正係数によって閾値長さを小さくして、空間構造データのより大きな変動およびノイズに対処する。一方で、空間構造データのノイズが少ない場合、補正係数はより大きな数であってもよい（すなわち、空間構造データに変動またはノイズが少ない場合には、閾値長さを上げる）。実施形態では、空間構造データは、物体識別管理部２０６によってノイズについて分析されてもよく、これによって、その後、空間構造データの中のノイズの尺度に従って、補正係数を選択してもよい。実施形態では、補正係数は、物体の予想される配置に従って選択されてもよく、またはそうでない場合、判定されてもよい。この機能について、物体５８０、５８１の構造を記述する、空間構造データの一部分／空間セグメントによって画定される、層５９０を描写する図５Ｅを参照して説明する。物体５８０、５８１は、同じサイズであってよく、不規則に配置されても、または互いにオフセットされてもよい。例えば、こうした物体５８０、５８１は互いに整列していない。こうした物体５８０、５８１は、配置のずれから、異なる長さの縁を伴う構造を有するとして感知されうる。より具体的には、物体５８０および５８１は、正方形で同じサイズであり、各々が同一の長さの四つの縁を伴う。したがって、最小と予想される長さが、例えば、物体５８０の縁５８３といった、いずれか一つの縁の長さとして選択されうる。しかしながら、図５Ｅは、空間セグメント５９０の中に短い縁５８４を作り出す、物体５８０と５８１との間の空間的ずれを描写する。補正係数が高い値（例えば、１に近い）に設定される場合、閾値長さは、縁５８３の長さよりもほんのわずか短くなるであろう。補正係数のこうした高い値ゆえに、縁５８４が、上述の第一長さ基準および第二長さ基準を満たさない結果となり、例えば、頂点５８２がアーチファクトでないにもかかわらず、頂点５８２を３Ｄ頂点として認識しない場合がある。したがって、実施形態では、物体識別管理部２０６は、より小さい補正係数（例えば、０により近い値を持つ補正係数）を選択し、その結果、頂点５８２が第一および第二長さ基準に合格するような、縁５８４の長さよりも小さい閾値長さとなってよい。
【００７４】
実施形態において、第一頂点が３Ｄ角であるかどうかを判定する、上記の実施形態はさらに、第一頂点が直交性基準を満たすかどうかの判定を伴ってもよい。これは、上術の第一ベクトル
【数６】
0006692107.tif 000007
および第二ベクトル
【数７】
0006692107.tif 000008
が、互いに実質的に直交するかどうかの判定を伴いうる。例えば、直交性基準は、図５Ｄのベクトル５５１および図５Ｄのベクトル５５２が、実質的に直交する（また、実質的に垂直であるとも呼ぶ）かどうかの評価を伴いうる。本明細書で使用する場合、実質的に直交するとは、約９０°の角度で出合う、二本の線または二つのベクトルを指す。約９０°は、９０°の＋／−０．１°、０．５°、１°、２°、３°、４°、および／または５°辺りの範囲を含みうる。一部の事例では、上記の判定は、第一ベクトル
【数８】
0006692107.tif 000009
および第二ベクトル
【数９】
0006692107.tif 000010
のドット積が、ゼロまたは実質的にゼロであるかどうかを判定することによって行われうる。実施形態では、頂点（例えば、頂点５１２ｂ）が上術の第一長さ基準、第二長さ基準、および直交性基準を満たす場合、頂点を３Ｄ角、または３Ｄ角の集合に含まれると判定してよい。実施形態では、動作３０６で識別される複数の頂点の各頂点は、頂点が３Ｄ角であるかどうかを判定するように評価されてもよい。頂点が、第一および第二長さ基準を満たす３Ｄ頂点であるが、直交性基準を満たさないため、３Ｄ角ではない場合、３Ｄ頂点は依然として、以下で詳述するように、融合角を判定するように使用されてもよい。
【００７５】
一部の実施形態では、第一ベクトル
【数１０】
0006692107.tif 000011
および第二ベクトル
【数１１】
0006692107.tif 000012
（例えば、ベクトル５５１およびベクトル５５２）が、実質的に互いに直交するかどうかの判定は、二つのベクトルを共有平面へ投影し（例えば、物体識別管理部２０６によって）、その後、投影したベクトルが実質的に直交するかどうかを判定することを伴ってもよい。例えば、空間構造データから抽出される一部分／空間セグメントは、奥行き値の範囲を伴う空間情報を含んでもよく、（例えば、図１Ａ〜１Ｃの空間構造感知装置１５１の画像平面に対して）傾斜面を形成する層を表してもよい。こうした状況では、第一ベクトル
【数１２】
0006692107.tif 000013
および第二ベクトル
【数１３】
0006692107.tif 000014
は、互いの面外であってもよい。こうした状況に対処するために、物体識別管理部206（またはより広くは、計算システム１０１の処理回路１１０）は、第一ベクトル
【数１４】
0006692107.tif 000015
および第二ベクトル
【数１５】
0006692107.tif 000016
を共有平面上へ投影し、投影されたベクトル間の角度を使用して、それらが互いに実質的に直交するかどうかを判定するように構成されてもよい。
【００７６】
実施形態では、動作３０８はさらに、３Ｄ角である頂点の凸状の判定（すなわち、３Ｄ角の凸状の判定）、またはより広くは、３Ｄ角が凸角であるかどうかの判定を伴う。この判定は、例えば、物体識別管理部２０６によって行われてよい。形状の中の凸角は、形状より内側の角度が１８０°未満である角であってよく、一方、形状のうち凹角は、形状より外側の角度が１８０°未満である角であってよい。例えば、図５Ｄの頂点５１２ｂは、直交性基準を満たすため、３Ｄ角であってよく、さらに、頂点５１２ｂにおいて図５Ｄの形状より内側の角度５１６が、１８０°未満である、実質的に９０°の角度を有するため、凸角であってよい。図５Ｄの頂点５１２ｄは、同様に直交性基準を満たすため、３Ｄ角であってよいが、頂点５１２ｄにおいて図５Ｄの形状より外側の角度５１７が、１８０°未満である、実質的に９０°であるため、凹角であってもよい。三次元の物体については、形状の中の凸角は、形状と凸角自体の一点でのみ交差する平面を描くことができる角として理解されうる。凸角および凹角はまた、それらの周りの空間の内容物によって画定されてもよい。例えば、頂点は、四象限が交差する点として理解されてもよく、頂点の凸状の判定は、いくつの象限が形状の一部分を包含するかの判定を含みうる。一つの象限のみが形状の一部を包含する場合、頂点は凹状であると判定されうる。三つの象限が形状の一部を包含する場合、頂点は凸状であると判定されうる。
【００７７】
実施形態では、３Ｄ角である頂点がまた、凸角でもあるかどうかの判定は、頂点から離れる方を指す、上述の二つのベクトルである、第一ベクトル
【数１６】
0006692107.tif 000017
および第二ベクトル
【数１７】
0006692107.tif 000018
の外積の（例えば、物体識別管理部２０６による）判定を伴う。外積は、外積のベクトルを含んでもよく、または外積のベクトルであってもよい。例えば、図５Ｆは、外積の演算結果である、外積のベクトル５５３および５５６を示す。より具体的には、図によって層４２２の斜視図が提供される。図５Ｆはまた、取り込まれた空間セグメント４２２に対する、空間構造感知装置１５１Ａの位置も示す。図５Ｆの例では、外積のベクトル５５３は、ベクトル５５１、５５２の外積の結果であり、両ベクトル５５１、５５２に直交する。さらに、外積のベクトル５５６はベクトル５５４、５５５の外積の結果である。右手の法則によって判定される、外積のベクトル５５３または５５６の方向は、３Ｄ角（例えば、図５Ｆの頂点５１２ｂまたは頂点５１２ｄ）である特定の頂点がまた、凸角であるか、または凹角であるかを示しうる。右手の法則は、外積のベクトルの方向を判定するためによく使用される慣習である。例えば、外積を方程式
【数１８】
0006692107.tif 000019
とする。右手を使用して、人差し指を
【数１９】
0006692107.tif 000020
の方に向け、中指を
【数２０】
0006692107.tif 000021
の方に向ける。人差し指および中指をそのように配置すると、延びた親指は外積
【数２１】
0006692107.tif 000022
の方向を指す。頂点が凸角であるかどうかの判定は、頂点に対応する外積のベクトルの方向が、定義される方向に一致するかどうかの判定を伴いうる。以下で詳述するように、外積のベクトルに一致する方向が、計算システム１０１が（動作３０６の）複数の頂点を経て進行している方向でありうる。
【００７８】
外積の演算は反可換であるため、ベクトルおよび頂点の順序付けは、上記の判定結果に影響を与える。例えば、計算システム１０１の処理回路１１０が、複数の頂点の各頂点が３Ｄ頂点であるかどうかを判定し、各頂点が３Ｄ角であるかどうかを判定し、および／または各頂点が凸角であるかどうかを判定している場合、頂点の順序付けは、処理回路１１０が、時計回りまたは反時計回りに、複数の頂点を経て進行する順番で上記判定を行っているかどうかを指してもよい。例として、処理回路１１０が、その順序で、図５Ｄまたは図５Ｆの頂点５１２ａ、５１２ｂ、５１２ｃ、５１２ｄ、５１２ｅ、および５１２ｆを評価して、各頂点が凸角であるかどうかを判定する場合、処理回路１１０は、層４２２の輪郭４２３に沿って時計回りに、頂点を経て進行しているとみなされうる。こうした例では、外積のベクトルと比較される画定された方向は、図５Ｆに描写する層４２２から外へ向いている（また、層から空間構造感知装置１５１Ａの方に上へ向いているとも言える）方向でありうる。この例では、頂点は、その外積のベクトルが画定された方向を指しているか、またはそうでない場合、その方向に一致するかの場合、凸角とみなされてもよく、その外積のベクトルが、画定された方向を指していないか、またはより広くは、その方向と一致しないかの場合、凹角とみなされてもよい。例えば、図５Ｆの頂点を評価する場合、ベクトル５５１および５５２の外積である外積のベクトル５５３は、空間セグメントにより表される層４２２から外へ（または層から上へ）向くであろう。外積のベクトル５３３は、画定された方向に一致するとみなされてもよく、それゆえ、その対応する頂点（５１２ｂ）は、凸角とみなされてもよい。図５Ｆの例では、第一ベクトル５５１は、反時計回りの方向とみなされうるか、または輪郭４２３に沿って反時計回りの流れに従う方向とみなされうる、方向Ａに沿って指す。
【００７９】
実施形態では、複数の頂点を経て進行する順番は、時計回りまたは反時計回りに連続して、輪郭の複数の頂点に到達する輪郭（例えば、輪郭４２３）に従う流れと類比されてもよく、画定された方向（外積のベクトルと比較される）は、流れの回転ベクトルの方向と反対でありうる。例えば、複数の頂点の評価が時計周りに進行する場合、回転ベクトルは、右手の法則により画定されるように、下方を（空間構造感知装置１５１Ａから離れるように）向きうる。画定された方向は回転ベクトルの方向と反対でありうる。複数の頂点を反時計回りに評価する場合、回転ベクトルは上方を向きうる。
【００８０】
図５Ｆの例では、動作３０８によって、頂点５１２ｄが凹角である、またはより広くは、頂点５１２ｄが凸角でないと判定されてもよい。上述のように、頂点５１２の輪郭４２３より外側の角度が１８０°未満であるため、頂点５１２ｄは輪郭４２３の凹角とみなされうる。頂点５１２ｄが凹角または凸角であるという判定はまた、頂点から二つのそれぞれ最も近い隣接頂点へ離れていく方を指す、二つのベクトルの外積に基づいてもよい。図５Ｆでは、これら二つのベクトルはベクトル５５４、５５５である。ベクトル５５４は、反時計回りの進行に従う方向において、最も近い隣接頂点の方を向き、一方、ベクトル５５５は、時計回りの進行に従う方向において、最も近い隣接頂点の方を向く。ベクトル５５４、５５６の外積は外積のベクトル５５６を含む。外積のベクトル５５６は層の中の方を向く（また、空間構造感知装置１５１Ａから離れて下方を指すとも呼ぶ）。外積のベクトル５５６の方向（下方）は、画定された方向（上方）と反対でありうる。それゆえ、外積のベクトル５５６に対応する頂点５１２ｄは、凹角である、またはより広くは、凸角ではないとみなされてもよい。
【００８１】
上述したように、外積を計算する際に使用されるベクトルおよび頂点の順序付けは、結果得られる外積のベクトルの方向に影響を与えうる。図５Ｆの示す例では、頂点は、複数回のそれぞれの反復で、時計回りに頂点を経て進行する順番（また、時計回りの順番とも呼ぶ）に評価することができ、外積を算出するのに使用する第一ベクトル
【数２２】
0006692107.tif 000023
は、（現在の頂点から前の頂点の方へ）反時計回りの流れに従う方向を指し、外積を算出するのに使用する第二ベクトル
【数２３】
0006692107.tif 000024
は、（現在の頂点から次の頂点の方へ）時計回りの流れに従う方向を指す。外積のベクトル
【数２４】
0006692107.tif 000025
は、空間構造感知装置１５１Ａへの方向を指してもよい。別の例では、頂点は、反時計回りに頂点を経て進行する順番（また、反時計回りの順番とも呼ぶ）に評価されうる。こうした例では、外積を算出するのに使用する第一ベクトル
【数２５】
0006692107.tif 000026
は、（現在の頂点から前の頂点の方へ）時計回りの流れに従う方向を指し、外積を算出するのに使用する第二ベクトル
【数２６】
0006692107.tif 000027
は、（現在の頂点から次の頂点の方へ）反時計回りの流れに従う方向を指す。外積のベクトル
【数２７】
0006692107.tif 000028
は、空間構造感知装置１５１Ａから離れる方向を指してもよい。それゆえ、二つの上記の例における外積のベクトルは、頂点を経て進行するのが時計回りか、または反時計回りかによって、異なる方向を指してもよい。そのため、頂点が凸角であるかを識別するとき、（例えば、物体識別管理部２０６を実行する）処理回路１１０は、頂点が時計回りまたは反時計回りで評価されているかどうかを考慮しうる。例えば、頂点が時計回りで評価されている場合、処理回路１１０は、（外積のベクトルと比較される）画定された方向が、空間構造感知装置１５１Ａの方へ上を指す方向であるかどうかを判定しうる。頂点が反時計回りで評価されている場合、処理回路１１０は、画定された方向が、空間構造感知装置１５１Ａから離れて下を指す方向であるかどうかを判定しうる。
【００８２】
実施形態では、（例えば、物体識別管理部２０６を実行中の）処理回路１１０は、どの頂点が３Ｄ角であるかどうかの判定、およびどの頂点が凸角であるかどうかの判定を、いかなる適切な順序でも行いうる。一部の実施形態では、どの頂点が３Ｄ角であるかどうかの判定は、どの頂点が凸角であるかどうかを判定する前に、行われる必要があってもよい。処理回路１１０は、どの頂点が同様に凸角であるかどうかを判定する前に、３Ｄ角を識別するように、動作３０６の複数の頂点のすべてを評価してもよく、または処理回路は、一部の頂点のみを評価して、それらの頂点が３Ｄ角であるかどうかを判定した後に、凸角の識別を始めてもよい。一部の実施形態では、処理回路は、頂点を３Ｄ角と判定した直後に、特定の頂点が凸角であるかどうかを判定しうる。
【００８３】
実施形態では、動作３０８は、凸角とみなされうる、融合角の判定を伴ってもよい。一部の事例では、融合角は、空間構造データにより記述される物体構造に近似するし、評価されている頂点の近くにある形状の直交角でありうる。融合角は、以下で詳述する角融合法の一部として判定されうる。こうした実施形態は、頂点が（第一長さ基準および第二長さ基準を満たすため）３Ｄ頂点として判定されるが、（直交性基準を満たさないため）３Ｄ角ではない状況に適用されうる。例えば、図５Ｇは、空間構造データの一部分／空間セグメントによって記述される構造の層６２２を描写し、層は、例えば、動作３０４で抽出される。より具体的には、図は、層６２２の輪郭を記述する、複数の頂点５３２ａ〜５３２ｇを描写する。頂点は、例えば、動作３０６で識別されていてもよい。この例では、頂点５３２ｂは複数の頂点のうちの第一頂点（例えば、現在の頂点）であってよく、一方、頂点５３２ａは第二頂点（例えば、前の頂点）であってよく、頂点５３２ｃは第三頂点（例えば、次の頂点）であってよい。頂点５３２ａは、層６２２の輪郭に沿う第一方向Ａにおいて、頂点５３２ｂに最も近い（また、最も近接とも呼ぶ）頂点であってよく、一方、頂点５３２ｃは、層６２２の輪郭に沿う第二方向Ｂにおいて、頂点５３２ｂに最も近い頂点である。第一ベクトル５６１は、頂点５３２ｂから頂点５３２ａへ延びるように画定されてよく、一方、第二ベクトル５６２は、頂点５３２ｂから頂点５３２ｃへ延びるように画定されてよい。この例では、頂点５３２ｂは、第一長さ基準および第二長さ基準を満たすため、３Ｄ頂点であると判定されうるが、直交性基準を満たさないため、３Ｄ角であるとはみなされない。第一ベクトル５６１および第二ベクトル５６２は互いに直交しないため、直交性基準を満たさない。
【００８４】
こうした状況で、処理回路１１０は、層の輪郭に沿う第二方向において、第一頂点に二番目に近接する隣接頂点である第四頂点を選択してもよく、第四頂点と第三頂点との間に第三ベクトルを画定してもよい。図５Ｇの例では、第四頂点は５３２ｄであり、方向Ｂに沿って頂点５３２ｂに二番目に近接の隣接頂点である。さらに、この例の第三ベクトルは、頂点５３２ｃと頂点５３２ｄとの間にあり、より具体的には、頂点５３２ｃから頂点５３２ｄまでのベクトル５６３である。一部の事例では、処理回路１１０は、（例えば、物体識別管理部２０６を実行することによって、）第三ベクトル５６３を閾値長さと比較することにより、第三ベクトルが第三長さ基準を満たすかどうかを判定してもよい。一部の事例では、こうした比較は省略されてもよい。
【００８５】
角融合法の上記の例では、処理回路１１０はさらに、第一ベクトルに沿って延びる第一線と、第三ベクトルに沿って延びる第二線とを判定してもよく、またはそうでない場合、画定しうる。例えば、図５Ｇは、第一線が線５７１であり、第二線が線５７３である例を描写する。線５７１は、ベクトル５６１に沿って延びてもよく、頂点５３２ａを通過して延び、頂点５３２ｂを通過して延びてもよい。同様に、線５７３は、ベクトル５６３に沿って延び、頂点５３２ｃおよび５３２ｄを通過して延びる。
【００８６】
角融合法の上記の例では、処理回路１１０はさらに、第一線（例えば、５７１）と第二線（例えば、５７３）との間の交差である交点（例えば、図５Ｇの点５３２ｈ）を識別しうる。点５３２ｈを頂点と識別すると、点５３２ｈは、頂点５３２ａ〜ｇと共に複数の頂点に追加されうる。図５Ｇに描写するように、交点５３２ｈは、図に描写する層により形成される形状の外側、または、より具体的には、層の輪郭の外側にある仮想点でありうる。一部の事例では、処理回路１１０はさらに、第一線（例えば、５７１）が第二線（例えば、５７３）に直交する、または実質的に直交するかどうかを判定することによってなど、交点（例えば、５３２ｈ）が直交性基準を満たすかどうかを判定しうる。交点を画定する第一線および第二線が互いに直交する場合、交点は融合角と呼ばれうる。
【００８７】
角融合法の上記の例では、処理回路１１０はさらに、融合角が凸状であるかどうかを判定しうる。一部の事例では、この判定は、第一ベクトルと第二ベクトルとの外積に関する上記説明に類似して、第一ベクトルおよび第三ベクトルの外積の判定に基づいてもよい。融合角の凸状は、対応する外積のベクトルの方向が、上述の画定された方向に一致するかどうかに基づいてもよい。一部の事例では、融合角が凸状であるかどうかの判定は、融合角が、複数の頂点により記述されている層の輪郭の外側にあるかどうかの判定を伴いうる。例えば、点５３２ｈは、層６２２の輪郭６２３の外側にあるため、凸状の融合角である。融合角は、凸状であると判定される場合、動作３０８の凸角として識別されうる。
【００８８】
上述のように、頂点が３Ｄ角であるかどうかの判定、すなわち、頂点に基づく融合角の判定は、複数の頂点の各々に対して、複数の反復を通して行われうる。図５Ｇに関して上述した例では、現在の反復は頂点５３２ｂに対して行われており、そのため、頂点５３２ｂが現在の頂点であり、頂点５３２ａおよび５３２ｃは、その反復に対して、それぞれ前の頂点および次の頂点である。次の連続反復で、処理回路１１０は次の未確認の頂点へ進みうる。点５３２ｈを融合角として識別した後、処理回路１１０は、頂点５３２ｃを抜かして、頂点５３２ｄが３Ｄ頂点または３Ｄ角であるかの判定へ進む。頂点５３２ｃは、点５３２ｈを融合角として判定するときに使用したため、この点を再度査定する必要はない。
【００８９】
さらなる実施形態では、点５３２ｈを融合角として識別した後、処理回路は、次に点５３２ｈに最も近い隣接頂点へ進みうる。例えば、この例では頂点５３２ｃへ進みうる。この例では、頂点５３２ｃが現在の頂点となり、一方、今は複数の頂点へ追加された点５３２ｈ、および５３２ｄが、その反復に対してそれぞれ前の頂点および次の頂点である。点５３２ｈが、頂点５３２ｃおよび５３２ｄを接続する線５７３上にあるため、頂点５３２ｃは第三基準（直交性）を満たすことができず、処理回路１１０は、頂点５３２ｃが３Ｄ頂点でも３Ｄ角でもないと判定するであろう。
【００９０】
上述したような角融合方法は、複数の状況で有利でありうる。こうした状況は、非垂直（すなわち、傾斜または円形）角を有する不規則な形状の物体を伴う場合があり、および／または図１Ａ〜１Ｄおよび図５Ｆの空間構造感知装置１５１／１５１Ａに対して見えない、もしくは見える所では遮られている角を有する、特定の物理的物体を伴いうる。例えば、第一物体は、第一物体の上部に積み重なる第二物体により見えない、または見える所では遮られている角を有しうる。別の例では、物体の角の彩色または材料（例えば、反射テープ）の違いによって、不正確な空間構造データの取り込みがもたらされうる。こうした状況では、角融合法によってこうした不正確さが補われうる。
【００９１】
図３に戻ると、方法３００はさらに動作３１０を含み、かかる動作では、計算システムの処理回路１１０が１０１を用いて、動作３０８で識別される凸角に従って物体認識を行う。一部の例では、動作３１０は物体認識管理部２０８によって行われてよい。実施形態では、動作３１０は、本明細書に記載するように、検出仮説の生成、検出仮説の修正、および／または検出仮説のフィルタリングを含みうる。
【００９２】
実施形態では、検出仮説は、どんな物体、どんなタイプの物体、および／またはどんな物体配向が、図１Ａ〜１Ｃの空間構造感知装置１５１によって感知されているのかという推定を指しうる。一部の例では、検出仮説は、特定の物体または特定タイプの物体（例えば、特定タイプの箱または他のパッケージ）が、動作３０２の空間構造データなどの空間構造データによって記述されているかどうかの判定であってもよい。一部の事例では、検出仮説は、空間構造データとテンプレートのテンプレート特徴との判定されたマッピングであってもよく、テンプレートは物体構造を記述する。テンプレートは、物体構造の角、面、および／または縁に対する一連の座標など、テンプレート特徴によって物体構造を記述しうる。図６Ａは、倉庫にある在庫の一部である特定タイプの箱など、特定タイプの物体用のテンプレートの例を描写する。上述のように、テンプレートは、角、縁、一つ以上の面、またはいくつかの他の特徴を表す一連の座標など、そのタイプの物体の複数の特徴を記述しうる。図６Ａの例では、テンプレートは、特定タイプの物体（例えば、箱）上の四点６１２ａ〜６１２ｄを記述する四つの座標を含む。四つの座標は、例えば、そのタイプの物体の四つの角を表してもよい。一部の実装では、検出仮説は、上述のテンプレートの特徴のうち一つ以上について、空間構造データの一つ以上のどの部分が、一つ以上の特徴とマッピングするのか、またはそうでない場合、それらに対応するのかの推定を含みうる。
【００９３】
実施形態では、動作３１０は、動作３０８で識別された凸角を使用して、検出仮説を生成することを伴う。例えば、図６Ａの点５１２ａにより表される凸角を使用して、検出仮説を生成してもよい。図６Ａの検出仮説は、図６Ａおよび６Ｂに示すように、点５１２ａにより表される凸角へ、テンプレートの点６１２ａをマッピングする、推定マッピングであってもよい。一部の事例では、検出仮説はまた、テンプレートの点６１２ａ〜６１２ｄが、識別された凸角と整列すべきであるという判定を伴いうる。例えば、こうした判定は、点６１２ａと６１２ｄとの間の線が、点５１２ａと５１２ｆとの間の線と平行であり、および／または点６１２ａと６１２ｂとの間の線が、５１２ａと５１２ｂとの間の線と平行であるような配向を有する点６１２ａ〜６１２ｄを伴いうる。検出仮説を生成するように、ステップ３０８の凸角を使用することによって、検出仮説が正しいという可能性が増大しうる。より具体的には、動作３０８で識別される凸角は、一つ以上の物体の角など、一つ以上の物体（例えば、図４Ａの４０１、４０２）の構造の物理的特徴に対応する可能性がより高くてもよい。テンプレートによっても、特定の物体または特定タイプの物体の物理的特徴が識別される場合、テンプレートの特徴を凸角に一致させる検出仮説は、正確である可能性がより高い場合がある。一部の事例では、検出仮説を修正および精緻化してもよく、凸角によって、正しい検出仮説を判定するための開始点が提供されてもよい。それゆえ、実施形態では、動作３１０は、凸角が、物体形状を画定するテンプレートの特徴と整合するかの判定を伴いうる。
【００９４】
実施形態では、動作３１０は、検出仮説をフィルタリングして取り除くかどうか、またはそうでない場合、無視するかどうかの判定を伴いうる。より広く言うならば、こうした実施形態は、検出仮説が誤りでありそうかどうかの判定を伴いうる。例えば、図６Ｃは、（点６１２ａ〜６１２ｄによって表される）テンプレートのどの部分が、空間構造データの別の部分へマッピングされるかという別の推定を伴う、別の検出仮説を描写する。この実施形態では、テンプレート特徴のうちのいずれも、凸角（例えば、点５１２ａ）へマッピングされないため、物体認識のために、検出仮説をフィルタリングして取り除いてもよく、またはそうでない場合、無視してもよい。別の例では、検出仮説によって、凸角に十分近い位置を表す空間構造データの一部分へ、テンプレートの少なくとも一つのテンプレート特徴をマッピングする必要がありうる。検出仮説でいずれのテンプレート特徴も、凸角に十分近い位置へマッピングされない場合、検出仮説はフィルタリングして取り除かれてもよい。
【００９５】
開示と一致するさらなる実施形態には、少なくとも以下が含まれる。
【００９６】
実施形態１は、非一時的コンピュータ可読媒体と、物体構造を記述する空間構造データが非一時的コンピュータ可読媒体に記憶されるとき、物体構造について複数の層を示す奥行き情報を有する空間構造データにアクセスすることと、空間構造データから、複数の層のうちの一層を表す、空間構造データの一部分を抽出することと、空間構造データの一部分から、層の輪郭を記述する複数の頂点を識別することと、複数の頂点に基づいて層の凸角を識別することと、凸角に従って物体認識を行うこととを行うように構成される、少なくとも一つの処理回路と、を備える、計算システムである。
【００９７】
実施形態２は、空間構造データが、物体構造の一つ以上の面上におけるそれぞれの位置を表す複数の点を識別する点群を含み、抽出される空間構造データの一部分が、複数の点の一部分を表し、かつ、層を表す点の集合を識別する、実施形態１に記載の計算システムである。
【００９８】
実施形態３は、処理回路が、層を表す点の集合について、真っ直ぐな縁を形成する複数の線分を識別することと、複数の頂点を線分の終点として識別することと、によって、層の輪郭を記述する複数の頂点を識別するように構成される、実施形態２に記載の計算システムである。
【００９９】
実施形態４は、処理回路が、点の集合の周縁上にある点を表す複数の縁点を点の集合の中から識別することと、複数の縁点を通り抜ける複数の線を判定することと、複数の線が交差する交点を、複数の頂点として識別することと、によって、層の輪郭を記述する複数の頂点を識別するように構成される、実施形態２または３に記載の計算システムである。
【０１００】
実施形態５は、処理回路がさらに、複数の頂点の中から二つ以上の頂点間の、少なくとも一つまたは複数の距離を示す関係を判定することと、関係に従って、複数の頂点の部分集合を３Ｄ角として識別することと、凸状である３Ｄ角を、凸角として識別することと、によって、複数の頂点の中から、層の凸角を識別するように構成される、実施形態１〜４のいずれか一つに記載の計算システムである。
【０１０１】
実施形態６は、関係がさらに、ベクトルの対によって形成されるそれぞれの角度を示し、ベクトルの各々は、複数の頂点のうちの一対の頂点の間を延びる、実施形態５に記載の計算システムである。
【０１０２】
実施形態７は、処理回路がさらに、複数の頂点の中から、３Ｄ頂点の集合を識別することと、３Ｄ頂点の集合の中から、３Ｄ角の集合を識別することと、３Ｄ角の集合の中から、凸角の少なくとも一部を識別することと、によって、複数の頂点の中から層の凸角を識別するように構成され、３Ｄ頂点の集合は、定義される閾値長さに等しいかまたはそれを超える、最も近い隣接頂点へのそれぞれの距離を各々有する頂点を含み、３Ｄ頂点の集合は、定義される閾値長さよりも短い、最も近い隣接頂点へのそれぞれの距離を有するいかなる頂点を除外し、３Ｄ角の集合は、３Ｄ頂点の集合の中から、物体構造の直交角を表す３Ｄ頂点を含む、実施形態１から６のいずれか一つに記載の計算システムである。
【０１０３】
実施形態８は、処理回路がさらに、複数の頂点のうちの第一頂点を、３Ｄ角の集合の中へ含むかどうかを判定することによって、３Ｄ角の集合を識別するように構成されており、かかる判定は、複数の頂点の中から、層の輪郭に沿う第一方向において、第一頂点に最も近い隣接頂点である第二頂点を選択することと、第一頂点から第二頂点までである、第一ベクトルを画定することと、複数の頂点の中から、層の輪郭に沿う第二方向において、第一頂点に最も近い隣接頂点である第三頂点を選択することであって、第二方向は、第一方向とは異なることと、第一頂点から第三頂点までである、第二ベクトルを画定することと、第一ベクトルの第一長さを定義される閾値長さと比較することによって、第一頂点が第一長さ基準を満たすかどうかを判定することと、第二ベクトルの第二長さを定義される閾値長さと比較することによって、第一頂点が第二長さ基準を満たすかどうかを判定することと、第一ベクトルおよび第二ベクトルが、実質的に互いに直交するかどうかを判定することによって、第一頂点が直交性基準を満たすかどうかを判定することと、第一頂点が第一長さ基準を満たさない、第一頂点が第二長さ基準を満たさない、または第一頂点が直交性基準を満たさないという判定に応じて、３Ｄ角の集合から第一頂点を除外するように判定することと、第一頂点が第一長さ基準を満たす、第一頂点が第二長さ基準を満たす、および第一頂点が直交性基準を満たすという判定に応じて、３Ｄ角の集合に第一頂点を含むように判定することと、によってなされる、実施形態７に記載の計算システムである。
【０１０４】
実施形態９は、処理回路がさらに、３Ｄ角の集合に３Ｄ角として第一頂点を含むという判定に応じて、３Ｄ角の凸状を判定するために、第一ベクトルと第二ベクトルとの外積を判定することによって、３Ｄ角が凸角であるかどうかをさらに判定するように構成される、実施形態８に記載の計算システムである。
【０１０５】
実施形態１０は、外積を判定することが、外積のベクトルを判定することを含み、３Ｄ角が凸角であるかどうかを判定することは、外積のベクトルの方向が画定された方向に一致するかどうかを判定することを含む、実施形態９に記載の計算システムである。
【０１０６】
実施形態１１は、処理回路が、複数の頂点の各頂点について、３Ｄ角の集合にそれぞれの３Ｄ角として頂点を含むかどうかを判定することと、層の輪郭に沿って時計回りまたは反時計回りに、複数の頂点を経て進行する順番で、当該判定を実行することと、を行うように構成され、外積のベクトルの方向と比較される、画定された方向は、順番が時計回りに複数の頂点を経て進行するか、または順番が反時計回りに複数の頂点を経て進行するかによる、実施形態１０に記載の計算システムである。
【０１０７】
実施形態１２は、処理回路が、第一頂点が直交性基準を満たさないという判定に応じて、第一頂点に基づいて融合角を判定するように構成され、融合角は、物体構造に基づく形状の直交角であり、融合角は、層の輪郭に沿う第二方向において、第一頂点に二番目に近い隣接頂点である第四頂点を選択することと、第四頂点と第三頂点との間に、第三ベクトルを画定することと、第一ベクトルに沿って延びる第一線、および第三ベクトルに沿って延びる第二線を判定することと、第一線と第三線との間の交点を識別することと、第一線および第三線が、実質的に互いに直交するかどうかを判定することによって、交点が直交性基準を満たすかどうかを判定することと、交点が直交性基準を満たすという判定に応じて、交点を融合角として識別することと、によって判定される、実施形態８から１１のいずれか一つに記載の計算システムである。
【０１０８】
実施形態１３は、処理回路が、融合角が層の輪郭の外側にあるかどうかを判定することによって、融合角が凸状であるかどうかを判定し、融合角が凸状であるという判定に応じて、凸角のうちの一つとして融合角を識別するように構成される、実施形態１２に記載の計算システムである。
【０１０９】
実施形態１４は、処理回路がさらに、第一ベクトルおよび第二ベクトルを画定する前に、ならびに第一頂点が第一長さ基準、第二長さ基準、および直交性基準を満たすかを判定する前に、第一頂点、第二頂点、および第三頂点を共有平面上へ投影するように構成される、実施形態８から１３のいずれか一つに記載の計算システムである。
【０１１０】
実施形態１５は、処理回路がさらに、凸角に従って検出仮説を生成することによって、物体認識を行うように構成される、実施形態１から１４のいずれか一つに記載の計算システムである。
【０１１１】
実施形態１６は、処理回路が、凸角に基づいて、物体構造を記述する空間構造データを、同様に物体構造を記述するテンプレートの中の特徴にどのようにマッピングするかを判定することによって、物体認識を行うように構成される、実施形態１から１５のいずれか一つに記載の計算システムである。
【０１１２】
実施形態１７は、処理回路がさらに、凸角に従って検出仮説を修正することによって、物体認識を行うように構成される、実施形態１から１６のいずれか一つに記載の計算システムである。
【０１１３】
実施形態１８は、非一時的コンピュータ可読媒体上に記憶された命令を有する非一時的コンピュータ可読媒体であって、命令は、処理回路によって実行されるとき、処理回路に、物体構造を記述する空間構造データであって、物体構造について複数の層を示す奥行き情報を有する空間構造データにアクセスすることと、空間構造データから、複数の層のうちの一層を表す、空間構造データの一部分を抽出することと、空間構造データの一部分から、層の輪郭を記述する複数の頂点を識別することと、複数の頂点に基づいて層の凸角を識別することと、凸角に従って物体認識を行うことと、を行わせる。
【０１１４】
実施形態１９は、複数の頂点の中から二つ以上の頂点間の、少なくとも一つまたは複数の距離を示す関係を判定することと、関係に従って、複数の頂点の部分集合を３Ｄ角として識別することと、凸状である３Ｄ角を、凸角として識別することと、によって、命令が、処理回路によって実行されるとき、処理回路に、複数の頂点の中から層の凸角を識別することを行わせる、実施形態１８に記載の非一時的コンピュータ可読媒体である。
【０１１５】
実施形態２０は、計算システムによって行われる方法であり、方法は、物体構造を記述する空間構造データにアクセスすることであって、空間構造データは、物体構造について複数の層を示す奥行き情報を有する、ことと、空間構造データから、複数の層のうちの一層を表す、空間構造データの一部分を抽出することと、空間構造データの一部分から、層の輪郭を記述する複数の頂点を識別することと、複数の頂点に基づいて層の凸角を識別することと、凸角に従って物体認識を行うこととを含む。
【０１１６】
関連分野の当業者にとって、本明細書に記載する方法および用途への修正ならびに適応は、実施形態のうちのいずれの範囲から逸脱することなく成すことができることは明らかであろう。上に記載する実施形態は、説明に役立つ例であり、本発明がこれらの特定の実施形態に限定されると解釈されるべきではない。本明細書に開示する様々な実施形態は、記載および添付の図に具体的に提示する組み合わせとは異なる組み合わせで、組み合わせてもよいことは理解されるべきである。例によっては、本明細書に記載するプロセスもしくは方法のいずれのある特定の行為または事象は、異なる順番で行われてもよく、追加、統合、または完全に省略してもよいことも理解されるべきである（例えば、記載したすべての行為または事象は、方法またはプロセスを実施することを必要としない場合がある）。加えて、本明細書の実施形態のある特定の特徴を、明確にするために、単一の構成要素、モジュール、またはユニットにより行われていると記載しているものの、本明細書に記載する特徴および機能は、構成要素、モジュール、またはユニットのいかなる組み合わせによって行われてもよいことは理解されるべきである。それゆえ、添付の特許請求の範囲に定義するような、発明の精神または範囲から逸脱することなく、当業者によって様々な変更および修正に影響を与えうる。
【要約】      （修正有）【課題】空間構造データを処理するためのシステムおよび方法を提供する。【解決手段】システムは、物体構造を記述する空間構造データであって、物体構造について複数の層を示す奥行き情報を有する空間構造データにアクセスし３０２、空間構造データから、複数の層のうちの一層を表す、空間構造データの一部分を抽出し３０４、空間構造データの一部分から、層の輪郭を記述する複数の頂点を識別し３０６。、複数の頂点に基づいて層の凸角を識別し３０８、凸角に従って物体認識を行う３１０。【選択図】図３【図１Ａ】
0006692107.tif 000029
【図１Ｂ】
0006692107.tif 000030
【図１Ｃ】
0006692107.tif 000031
【図１Ｄ】
0006692107.tif 000032
【図１Ｅ】
0006692107.tif 000033
【図１Ｆ】
0006692107.tif 000034
【図２Ａ】
0006692107.tif 000035
【図２Ｂ】
0006692107.tif 000036
【図２Ｃ】
0006692107.tif 000037
【図３】
0006692107.tif 000038
【図４Ａ】
0006692107.tif 000039
【図４Ｂ】
0006692107.tif 000040
【図４Ｃ】
0006692107.tif 000041
【図４Ｄ】
0006692107.tif 000042
【図４Ｅ】
0006692107.tif 000043
【図５Ａ】
0006692107.tif 000044
【図５Ｂ】
0006692107.tif 000045
【図５Ｃ】
0006692107.tif 000046
【図５Ｄ】
0006692107.tif 000047
【図５Ｅ】
0006692107.tif 000048
【図５Ｆ】
0006692107.tif 000049
【図５Ｇ】
0006692107.tif 000050
【図６Ａ】
0006692107.tif 000051
【図６Ｂ】
0006692107.tif 000052
【図６Ｃ】
0006692107.tif 000053