(57)【要約】本明細書で説明されるシステム、方法、および装置は、静的および動的オブジェクトを識別するように、三次元データを表すボクセルに対して区分化を実行することに関する。ＬＩＤＡＲデータは、自律車両についての知覚システムによって捕捉されてもよく、ボクセル空間において表されてもよい。オペレーションは、基準方向に対してボクセル化されたデータの平面近似の面法線の方位を決定するように個々のボクセルを構文解析することによって運転可能な面を決定することを含んでもよい。複数の局所的にフラットなボクセルを含むグランド面を拡張するためにクラスタ化技術が使用されることができる。グランド平面データがボクセル空間から除外されることができ、残りのボクセルがオブジェクトを決定するようにクラスタ化されることができる。ボクセルデータは、動的オブジェクトを決定するように経時的に分析されることができる。グランドボクセル、静的オブジェクト、および動的オブジェクトと関連付けられた区分化情報は、自律車両を動作させることとともにトラッカおよび／またはプランナに提供されることができる。
2020524330.tif 000002
【特許請求の範囲】
【請求項１】
環境と関連付けられたＬＩＤＡＲデータセットを表すボクセル空間を受信するステップと、
前記ボクセル空間のボクセルに対し、前記ボクセルによって表される三次元データと関連付けられた面法線ベクトルを決定するステップと、
前記ボクセルと関連付けられた前記面法線ベクトルに少なくとも部分的に基づいて、前記ボクセルが局所的にフラットなボクセルであると決定するステップと、
グランドクラスタを決定するステップであって、前記グランドクラスタは、複数の局所的にフラットなボクセルを含み、前記複数の局所的にフラットなボクセルは、前記局所的にフラットなボクセルを含む、ステップと、
自律車両についての運転可能な面を表す前記グランドクラスタに少なくとも部分的に基づいて、前記自律車両についての軌道を生成するステップと、
を備えたことを特徴とする方法。
【請求項２】
前記自律車両の方位に少なくとも部分的に基づいて、基準方位を決定するステップと、
前記面法線ベクトルと前記基準方位と関連付けられたベクトルとの間の角度が閾値以内であると決定するステップと、
前記角度が前記閾値を下回ることに少なくとも部分的に基づいて、前記ボクセルが前記局所的にフラットなボクセルであると決定するステップと、
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項３】
前記局所的にフラットなボクセルは、第１の局所的にフラットなボクセルであり、前記グランドクラスタを決定するステップは、
シードボクセルとして、前記第１の局所的にフラットなボクセルを選択するステップであって、前記シードボクセルは、前記自律車両に近接している、ステップと、
第２の局所的にフラットなボクセルが前記シードボクセルに隣接していると決定するステップと、
前記シードボクセルおよび前記第２の局所的にフラットなボクセルを前記グランドクラスタと関連付けるステップと、
をさらに備えたことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記ボクセル空間のサブセットを識別するように、前記グランドクラスタと関連付けられたボクセルを前記ボクセル空間から抽出するステップと、
第１のオブジェクトを決定するようにボクセルの第１のグループをクラスタ化するステップであって、ボクセルの前記第１のグループの個々の第１のボクセルは、ボクセルの前記第１のグループの少なくとも１つの他の第１のボクセルに隣接している、ステップと、
第２のオブジェクトを決定するようにボクセルの第２のグループをクラスタ化するステップであって、ボクセルの前記第２のグループの個々の第２のボクセルは、ボクセルの前記第２のグループの少なくとも１つの他の第２のボクセルに隣接し、前記個々の第１のボクセルは、前記個々の第２のボクセルに隣接していない、ステップと、
をさらに備えたことを特徴とする請求項１または２に記載の方法。
【請求項５】
第１の局所的にフラットなボクセルの第１のクラスタを決定するステップと、
第２の局所的にフラットなボクセルの第２のクラスタを決定するステップと、
局所的にフラットなボクセルの前記第１のクラスタと局所的にフラットなボクセルの前記第２のクラスタとの間の高さ勾配を決定するステップと、
前記高さ勾配が勾配閾値を下回ると決定するステップと、
前記グランドクラスタを表すように、前記高さ勾配が前記勾配閾値を下回ることに少なくとも部分的に基づいて、前記第１のクラスタを前記第２のクラスタと結合するステップと、
をさらに備えたことを特徴とする請求項１または２に記載の方法。
【請求項６】
前記ボクセル空間において表される少なくとも１つの動的オブジェクトを決定するように、経時的にボクセルの占有を決定するステップと、
前記ボクセル空間において表される前記少なくとも１つの動的オブジェクトに少なくとも部分的に基づいて、前記軌道を生成するステップと、
をさらに備えたことを特徴とする請求項１または２に記載の方法。
【請求項７】
１つ以上のプロセッサと、
前記１つ以上のプロセッサに通信可能に結合され、命令を記憶した１つ以上のコンピュータ可読記憶媒体と、を備え、前記命令は、
少なくとも１つのＬＩＤＡＲセンサを使用して、環境を表すＬＩＤＡＲデータセットを捕捉し、
前記ＬＩＤＡＲデータセットをボクセル空間と関連付け、前記ボクセル空間は、複数のボクセルを含み、
前記ボクセル空間のボクセルに対し、前記ボクセルによって表される三次元データと関連付けられた面法線ベクトルを決定し、
前記ボクセルと関連付けられた前記面法線ベクトルに少なくとも部分的に基づいて、前記ボクセルが局所的にフラットなボクセルであると決定し、
グランドクラスタを決定し、前記グランドクラスタは、複数の局所的にフラットなボクセルを含み、前記複数の局所的にフラットなボクセルは、前記局所的にフラットなボクセルを含む、
ように前記プロセッサによって実行可能である、ことを特徴とするシステム。
【請求項８】
前記命令は、
基準方位を決定し、
前記面法線ベクトルと前記基準方位と関連付けられたベクトルとの間で形成された角度が閾値を下回ると決定し、
前記角度が前記閾値を下回ることに少なくとも部分的に基づいて、前記ボクセルが前記局所的にフラットなボクセルであると決定する、
ように前記１つ以上のプロセッサによってさらに実行可能であることを特徴とする請求項７に記載のシステム。
【請求項９】
前記命令は、
前記ボクセル空間のサブセットを識別するように、前記グランドクラスタと関連付けられたボクセルを前記ボクセル空間から抽出し、
ボクセルのクラスタを決定するようにボクセルのグループをクラスタ化し、ボクセルの前記グループの個々のボクセルは、ボクセルの前記グループの少なくとも１つの他のボクセルに隣接している、
ように前記１つ以上のプロセッサによってさらに実行可能であることを特徴とする請求項７または８に記載のシステム。
【請求項１０】
前記ＬＩＤＡＲデータセットは、第１の時間に受信された第１のＬＩＤＡＲデータセットであり、前記命令は、
ボクセルの前記クラスタが少なくとも１つのオブジェクトと表すと決定し、
前記少なくとも１つのオブジェクトが前記第１の時間に前記ボクセル空間のボクセルの第１のサブセットを占有していると決定し、
第２の時間に第２のＬＩＤＡＲデータセットを受信し、
前記第２のＬＩＤＡＲデータセットの少なくとも１つのＬＩＤＡＲデータ点と関連付けられたベクトルが、前記第２の時間にボクセルの前記第１のサブセットの少なくとも一部を通じてトラバースすると決定し、
ボクセルの前記第１のサブセットの前記少なくとも一部が前記第２の時間に占有されていないと決定し、
ボクセルの前記第１のサブセットの前記少なくとも一部が前記第２の時間に占有されていないことに少なくとも部分的に基づいて、前記少なくとも１つのオブジェクトが動的オブジェクトであると決定する、
ように前記１つ以上のプロセッサによってさらに実行可能であることを特徴とする請求項９に記載のシステム。
【請求項１１】
前記命令は、
ボクセルの前記クラスタと関連付けられたボクセルの数がボクセルの閾値数を下回ると決定し、
ボクセルの前記クラスタがオブジェクトでないと決定する、
ように前記１つ以上のプロセッサによってさらに実行可能であることを特徴とする請求項９に記載のシステム。
【請求項１２】
前記命令は、
第１の局所的にフラットなボクセルの第１のクラスタを決定し、
第２の局所的にフラットなボクセルの第２のクラスタを決定し、
局所的にフラットなボクセルの前記第１のクラスタと局所的にフラットなボクセルの前記第２のクラスタとの間の高さ勾配を決定し、
前記高さ勾配が勾配閾値を下回ると決定するし、
前記グランドクラスタを表すように、前記高さ勾配が前記勾配閾値を下回ることに少なくとも部分的に基づいて、前記第１のクラスタを前記第２のクラスタと結合する、
ように前記１つ以上のプロセッサによってさらに実行可能であることを特徴とする請求項７または８に記載のシステム。
【請求項１３】
前記命令は、
前記ボクセル空間において表される少なくとも１つの動的オブジェクトを決定するように、経時的にボクセルの占有を決定し、
前記ボクセル空間において表される前記少なくとも１つの動的オブジェクトに少なくとも部分的に基づいて、自律車両についての軌道を生成する、
ように前記１つ以上のプロセッサによってさらに実行可能であることを特徴とする請求項７または８に記載のシステム。
【請求項１４】
前記命令は、
自律車両についての運転可能な面を表す前記グランドクラスタに少なくとも部分的に基づいて、前記自律車両についての軌道を生成し、
前記軌道に少なくとも部分的に基づいて、前記自律車両を制御する、
ように前記１つ以上のプロセッサによってさらに実行可能であることを特徴とする請求項７または８に記載のシステム。
【請求項１５】
前記命令は、前記ボクセルと関連付けられた前記面法線ベクトルを決定するように、前記ボクセルと関連付けられた前記三次元データに少なくとも部分的に基づいて、共分散行列に対して固有値分解を実行する、ように前記１つ以上のプロセッサによってさらに実行可能である請求項７または８に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
関連出願の相互参照
本願は、参照によって本明細書に完全に組み込まれる、２０１７年６月１４日に出願された米国特許出願第１５／６２２９０５号に基づく優先権を主張する。
【０００２】
画像区分化は、画像を異なるセグメントに区分化して、画像のより意味のある表現を提供するためにしばしば使用される、画像解析の１つのタイプである。一例として、画像は、画像内のオブジェクトを一意的に識別するために、区分化されてよい。画像区分化とは対照的に、３次元データの区分化は、区分化を困難にする特有の難題を提示することがある。
【図面の簡単な説明】
【０００３】
添付の図面を参照して、詳細な説明が行われる。図において、参照番号の左端の数字は、その参照番号が初めて出現した図を識別する。異なる図における同じ参照番号の使用は、類似または同一の構成要素または特徴を示す。
【０００４】
【図１】静的および／または動的オブジェクト区分化のための例示的なプロセスのフローチャートを示す。
【図２】本明細書において説明されるような、オブジェクト区分化を実施するための、例示的なアーキテクチャを示す。
【図３】ボクセル空間（voxel space）内に表されたグランド領域（ground region）を区分化するための、例示的なプロセスのフローチャートを示す。
【図４】グランドクラスタ（ground cluster）を拡張（grow）するために、ボクセル空間にわたって補間を行うための、例示的なプロセスのフローチャートを示す。
【図５】レイキャスティング（ray casting）および動的オブジェクト区分化と関連付けられた例示的な図を示す。
【図６】本明細書において説明されるような、オブジェクト区分化に基づいて自律車両のための軌道を生成するための、例示的なプロセスを示す。
【図７】経時的なボクセルデータの表現に基づいて、ボクセルマップ（voxel map）をクリアするための、例示的なプロセスを示す図である。
【図８】経時的なボクセルデータの表現に基づいて、オブジェクトが動的オブジェクトであると決定するための、例示的なプロセスを示す図である。
【図９】ボクセル表現に基づいたオブジェクトの区分化に基づいて、マップ生成および／またはセンサ較正を実行するための、例示的なプロセスを示す図である。
【図１０】ボクセル表現に基づいたオブジェクトの区分化に基づいて、オブジェクトに注釈を施すための、例示的なプロセスを示す図である。
【図１１】本明細書において説明される技法を実施するための、例示的なコンピュータシステムのブロック図である。
【発明を実施するための形態】
【０００５】
本開示は、ボクセル空間内に表された３次元データに対して区分化を実行して、環境内においてグランド平面（ground plane）、静的オブジェクト、および動的オブジェクトを決定するための、方法、装置、およびシステムについて説明する。例えば、３次元データセットは、自律車両用の知覚システムと併用されるＬＩＤＡＲシステムによって捕捉されたデータを含んでよい。ＬＩＤＡＲシステムは、光エミッタと、光センサとを有してよく、光エミッタは、オブジェクトまたは面に向かって高度に集束された光を方向付ける１つまたは複数のレーザを含み、オブジェクトまたは面は、光を光センサに再度反射させる。ＬＩＤＡＲシステムの測定結果は、ＬＩＤＡＲシステムによって捕捉された、位置および／または距離に対応する（例えば、直交座標、極座標などの）座標を有する、３次元ＬＩＤＡＲデータとして表されてよい。ＬＩＤＡＲシステムによって捕捉されたデータは、ボクセル空間内に表されてよく、それは、３次元空間内において、体積要素（「ボクセル」）からなるグリッド内にデータを表すことを含んでよい。
【０００６】
いくつかの例においては、ＬＩＤＡＲデータは、ボクセル空間内において、（例えば、データ点と関連付けられた個々の＜ｘ、ｙ、ｚ、範囲、時間などの＞値を有する）未処理（raw）センサデータとして表されてよく、またはデータの統計的蓄積として表されてよい。例えば、ＬＩＤＡＲデータは、ボクセル空間内に蓄積されてよく、個々のボクセルは、データ点の数、平均強度、個々のボクセルと関連付けられたＬＩＤＡＲデータの平均ｘ値、個々のボクセルと関連付けられたＬＩＤＡＲデータの平均ｙ値、個々のボクセルと関連付けられたＬＩＤＡＲデータの平均ｚ値、およびボクセルと関連付けられたＬＩＤＡＲデータに基づいた共分散行列など、処理されたデータを含んでよい。
【０００７】
ボクセル空間内に表されたＬＩＤＡＲデータを用いる場合、処理は、グランド平面（例えば、自律車両が（drivable surface））と関連付けられたボクセルを決定することを含むことができ、それは、局所的にフラットなボクセルを決定することを含んでよい。いくつかの例においては、局所的にフラットなボクセルを決定することは、面をボクセル内のデータ（例えば、個々のＬＩＤＡＲデータ点）に適合させること（および／または共分散行列に対する計算（例えば、固有値分解（Eigenvalue decomposition）もしくは主成分分析（principle component analysis））を実行すること）と、面の法線ベクトルを決定することと、法線ベクトルが、自律車両の方位に対応することができる基準方向の閾値方向以内にあるかどうかを決定することとを含むことができる。いくつかの例においては、局所的にフラットなボクセルを決定することは、ボクセル空間内においてメッシュを生成することと、メッシュがボクセルの少なくとも一部を占有すると決定することと、ボクセルと関連付けられたメッシュの面法線ベクトルを決定することと、面法線が基準方向の閾値方向以内にあるかどうかを決定することとを含む、マーチングキューブタイプのアルゴリズムを含むことができる。局所的にフラットなボクセルが決定された後、領域拡張などのクラスタリング技法が、フラットまたは運転可能な面を表すグランドボクセルまたはグランド平面を識別するために使用されてもよい。さらに、データ内にギャップが存在して、ボクセル空間内に多数のパッチまたはクラスタをもたらすことができるので、処理は、隣接クラスタがグランド平面として含まれるべきかどうかを決定するために、隣接クラスタ内のボクセル内の様々な点の間を補間することを含むことができる。グランド平面を識別した後、グランド平面は、ボクセル空間から除去されること、または除外されることができ、残りのデータに対して、オペレーションが実行されることができる。
【０００８】
領域拡張などのクラスタリング技法が、残りのボクセルに適用されて、ボクセル空間内に表されたオブジェクトを決定することができる。個々のオブジェクトは、隣接ボクセルをグループ化することによって識別されることができ、各オブジェクトは、一意的なオブジェクト識別子と関連付けられる。非限定的な例として、単一のオブジェクトと関連付けられるすべてのＬＩＤＡＲ点は、すべて、同じオブジェクト識別子を有してよく、一方、異なるオブジェクトと関連付けられるＬＩＤＡＲ点は、異なるオブジェクト識別子を有してよい。いくつかの例においては、オブジェクト識別子は、ボクセルと関連付けられ、および／またはＬＩＤＡＲデータに伝搬されてよい。ＬＩＤＡＲデータは、経時的に捕捉または受信されるので、静的オブジェクトと動的オブジェクトとを区別するために、ボクセルの占有時間が、評価されることができる。例えば、壁などの背景オブジェクトの近くを歩く人など、空間内において接近した関係にあるオブジェクトを区別して、静的オブジェクトと動的オブジェクトとを区別するために、レイキャスティングが使用されることができる。さらに、オブジェクトの運動を示してよい、第１の時間に占有されていたボクセルが、第２の後続する時間に占有されていないときを、およびそれとは反対のときを決定するために、レイキャスティングが使用されることができる。データは、経時的に蓄積されるので、マップをクリアするために、またはオブジェクトの解像度を高めるために、やはり、レイキャスティング技法が使用されてよい。動的オブジェクトであるオブジェクトは、さらに、動的オブジェクト識別子を用いてタグ付けされて、またはそれと関連付けられてよい。
【０００９】
処理が実行され、オブジェクトが識別されるにつれて、静的および／または動的オブジェクトのリストが、自律車両用の軌道を生成するための基礎として、トラッキングシステムおよび／またはプランニングシステムに提供されてよい。さらに、例えば、他のセンサが時間につれてドリフトするとき、車両の決定された位置の正確性を高めるために、自律車両の１つまたは複数のセンサを較正するように、オペレーションが拡張されることができる。さらに、ＬＩＤＡＲデータが捕捉され、局所マップを生成するために使用されるとき、全体マップに関して自律車両を位置特定するために、ＬＩＤＡＲデータが使用されることができる。オペレーションは、局所マップと全体マップとの間の差を決定することを含むことができ、差は、中央サーバにアップロードされて、全体マップに組み込まれること、および／または他の車両に配信することができる。
【００１０】
いくつかの例においては、ＬＩＤＡＲデータが捕捉された後、および／またはデータが、中央サーバなどのコンピューティングデバイスにダウンロードされた、もしくは他の方法で提供された後、マップを生成し、既存のマップをクリーンアップするために、オブジェクトの区分化が使用されることができ、および／または後続する注釈オペレーションのために、それが使用されることができる。例えば、識別された静的オブジェクトは、自律車両のナビゲーションを支援するために、全体マップに組み込まれることができる。別の例においては、レイキャスティングを使用して動的オブジェクトを全体マップから除去し、全体マップ内のオブジェクトを純化することによって、全体マップをクリーンアップするために、捕捉されたデータが使用されることができる。別の例においては、静止オブジェクト（例えば、静的オブジェクト）であるが、非永続的なオブジェクト（例えば、駐車中の車両）について、そのような非永続的オブジェクトを全体マップから除去して、全体マップが環境の静的オブジェクトを反映することをさらに確かにするために、区分化情報が使用されることができる。別の例においては、静的および／または動的オブジェクトが、人手のまたは自動注釈サービスに提供されることができ、それは、オブジェクトの分類を実行して、例えば、機械学習のためのトレーニングデータセットを生成してよい。ボクセル区分化技法の上記および他のオペレーションおよび応用が、本明細書において論じられる。
【００１１】
本明細書において説明される区分化技法は、オブジェクトトラッキングおよび／または自律車両のナビゲーションのために、データを効率的に区分化するためのフレームワークを提供することによって、コンピューティングデバイスの機能を改善することができる。いくつかの例においては、ＬＩＤＡＲデータなどの複雑な多次元データは、データの効率的な評価および処理を考慮して、データを区分化することができる、ボクセル空間内に表されることができる。いくつかの例においては、ボクセル空間は、処理のためのデータの量を減らした、疎らなボクセル空間を表すことができる。いくつかの例においては、技法は、例えば、軌道生成のために、グランド平面を迅速に区分化するための、ロバストなプロセスを提供する。グランド平面と関連付けられた情報は、省かれること、または除外されることができ、減らされたデータセットに対して、オブジェクト識別が実行されることができ、オペレーションのために必要とされるメモリおよび処理の量を減らす。静的および動的オブジェクトは、例えば、動的オブジェクトのトラッキングオペレーションに集中することによって処理をさらに単純化した、ロバストなクラスタリング技法を使用して識別されることができる。さらに、本明細書において説明されるオペレーションは、オンラインおよびオフライン状況において利用されることができ、様々な状況において区分化データを利用するための、柔軟なフレームワークを提供する。いくつかの例においては、自律車両の軌道を生成する際に、より迅速および／またはより正確な区分化が利用されてよく、それが、自律車両の乗員の安全性を改善してよい。いくつかの例においては、本明細書において説明されるオペレーションは、メモリ要件を減らしてよく、またはデータを効率的に単純化するようにボクセル化されたデータを演算することによって、処理の量を減らしてよい。コンピュータの機能に対する上記および他の改善が、本明細書において論じられる。
【００１２】
本明細書において説明される方法、装置、およびシステムは、数々の方法で実施されることができる。例示的な実施が、下記の図を参照して、以下で提供される。ＬＩＤＡＲデータとの関連において、および／または自律車両との関連において説明されるが、本明細書において説明される方法、装置、およびシステムは、マシンビジョンを利用する様々なシステムに適用されることができる。さらに、３次元ＬＩＤＡＲデータとの関連において説明されるが、本明細書において説明される方法、装置、およびシステムは、３次元データに限定されず、またＬＩＤＡＲデータに限定されない。一例においては、方法、装置、およびシステムは、ＲＡＤＡＲデータを用いる２次元状況において利用されてよく、または水平ＬＩＤＡＲデータとともに使用されてよい。例えば、方法、装置、およびシステムは、製造組立ライン状況において、または航空測量状況において利用されてよい。さらに、データセットは、立体視カメラ、深度カメラ、ＲＡＤＡＲセンサ、音響センサなどからのデータを含んでよく、任意の数の次元に対応してよい、任意の数のレイヤまたはチャネルを含んでよい。加えて、本明細書において説明される技法は、（例えば、センサを使用して捕捉された）実データ、（例えば、シミュレータによって生成された）シミュレートされたデータ、または２つの任意の組み合わせとともに使用されてよい。
【００１３】
図１は、ボクセル空間におけるＬＩＤＡＲデータセットを表し、グランドと関連付けられたボクセルを決定し、静的および動的オブジェクトを決定し、後続する処理のために静的および／または動的オブジェクトを利用するための例示的なプロセス１００のフローチャートを示している。
【００１４】
オペレーション１０２において、プロセスは、ＬＩＤＡＲデータセットを受信することを含むことができる。図１においては、ＬＩＤＡＲデータセットとして示されているが、そのようなデータセットは、上で詳細に説明されたような任意の１つまたは複数のセンサからの任意の形態の深度データを含んでよい。いくつかの例においては、オペレーション１０２は、自律車両の知覚システムとの関連において動作する複数のＬＩＤＡＲセンサから、複数のＬＩＤＡＲデータセットを受信することを含んでよい。いくつかの例においては、オペレーション１０２は、２つ以上のＬＩＤＡＲセンサからのデータを組み合わせて、または融合させて、（「メタスピン（meta spin）」とも呼ばれる）単一のＬＩＤＡＲデータセットにすることを含んでよい。いくつかの例においては、オペレーション１０２は、時間の期間にわたって、ＬＩＤＡＲデータの一部を処理のために抽出することを含んでよい。いくつかの例においては、オペレーション１０２は、ＲＡＤＡＲデータ（または他のセンサデータ）を受信し、ＲＡＤＡＲデータをＬＩＤＡＲデータと関連付けて、環境のより詳細な表現を生成することを含んでよい。ＬＩＤＡＲデータセットの例は、例１０４において示されており、それは、自動車、トラック、道路、ビルディング、バイク、歩行者など、都市環境における様々なオブジェクトと関連付けられた、ＬＩＤＡＲデータ（例えば、点群）を含んでよい。
【００１５】
オペレーション１０６において、プロセスは、ＬＩＤＡＲデータセットをボクセル空間と関連付けることを含むことができる。例１０８は、各次元（例えば、ｘ、ｙ、ｚ）において５つのボクセルを含むボクセル空間を示しているが、ボクセル空間には、任意の数のボクセルが含まれてよい。いくつかの例においては、ボクセル空間は、ＬＩＤＡＲデータセットの起点または仮想起点の周りのエリアなど、物理的環境に対応してよい。例えば、ボクセル空間は、幅１００メートル、長さ１００メートル、高さ２０メートルのエリアを表してよい。さらに、ボクセル空間内の各ボクセル（例えば、ボクセル１１０）は、各次元が２５センチメートルなどの、物理的エリアを表してよい。本開示との関連において理解されてよいように、ボクセル空間は、環境の任意のエリアを表してよく、個々のボクセルも、同様に、任意の体積を表してよい。いくつかの例においては、ボクセルは、ボクセル空間の全体を通して均一のサイズであってよいが、いくつかの例においては、ボクセルの体積は、データの起点に関するボクセルの位置に基づいて、変化してよい。例えば、ＬＩＤＡＲセンサからの距離が増大するにつれて、ＬＩＤＡＲデータの密度は減少してよいので、ボクセル空間内のボクセルのサイズは、ボクセルからＬＩＤＡＲセンサ（または複数のＬＩＤＡＲセンサを代表する起点）までの距離に比例して、増大してよい。
【００１６】
一例においては、データは、経時的に蓄積されるので、オペレーション１０６は、メタスピン（例えば、ＬＩＤＡＲデータセット）をボクセル空間と合わせることを含んでよい。例えば、オペレーション１０６は、メタスピンをボクセル空間に合わせるために、メタスピンに適用する変換を決定することを含んでよい。特に、オペレーション１０６は、観測された点の、データの既存の蓄積に適合させられた平面までの距離を決定することによって、捕捉されたＬＩＤＡＲデータを、ボクセル空間内に蓄積されたデータと照合することを含んでよい。いくつかの例においては、この変換は、全体マップ上の位置に関する車両の位置の誤差を減らすことができる。
【００１７】
一例においては、ボクセル空間は、空の空間として初期化されてよく、ＬＩＤＡＲデータは、それが捕捉されたときに、ボクセル空間に追加されてよく、別の例においては、ボクセル空間は、以前に捕捉されたデータからなる全体マップを表すデータを用いて、初期化されてよい。全体マップデータを使用するケースにおいては、オペレーションは、局所的に捕捉されたＬＩＤＡＲデータを全体データと比較して、全体マップ空間内において自律車両を位置特定することを含んでよい。
【００１８】
いくつかの例においては、オペレーション１０６は、点群の個々の点を個々のボクセルにマッピングすることを含むことができる。いくつかの例においては、オペレーション１０６は、例えば、ＬＩＤＡＲデータが、自律車両など、動いているプラットフォームによって捕捉された場合に、例えば、ＬＩＤＡＲデータを静止した基準点に変換するために、ＬＩＤＡＲデータと関連付けられた動きベクトルを減算することを含むことができる。すなわち、いくつかの例においては、ＬＩＤＡＲデータは、（例えば、動いている車両に関して固定されたボクセル空間とは対照的に）例えば、全体マップに関して固定されたボクセル空間と関連付けられてよい。いくつかの例においては、オペレーション１０６は、疎らなボクセル空間を生成するために、データを含まない、または閾値数を下回る数の点しか含まないボクセルを廃棄すること、または省くことを含むことができる。さらに、いくつかの例においては、オペレーション１０６は、例えば、ボクセル空間に関する車両の位置と関連付けられたいずれの誤差も補償または調整するために、車両の体勢（例えば、車両の方位）および関連付けられたＬＩＤＡＲデータをボクセルマップと合わせることを含むことができる。
【００１９】
さらに、いくつかの例においては、オペレーション１０６は、ＬＩＤＡＲデータを統計的に蓄積し、それが個々のボクセルに追加されるときに、データを処理することを含むことができる。例えば、個々のボクセルは、データ点の数、平均強度、データの平均ｘ値、データの平均ｙ値、データの平均ｚ値、および／または個々のボクセルと関連付けられたＬＩＤＡＲデータに基づいた共分散行列を表すデータを含んでよい。したがって、いくつかの例においては、個々のボクセルと関連付けられたデータは、一部には、システムの処理性能を改善するための処理されたデータを表してよい。
【００２０】
オペレーション１１２において、プロセスは、グランドと関連付けられた１つまたは複数のボクセルを決定することを含むことができる。いくつかの例においては、グランドは、自律車両によって運転可能な面に対応してよい。例１１４においては、ＬＩＤＡＲデータ１１６を含む単一のボクセル、例えば、ボクセル１１０が、示されている。上で論じられたように、いくつかの例においては、ＬＩＤＡＲデータ１１６は、データ点の数、平均強度、平均ｘ値、平均ｙ値、平均ｚ値、およびＬＩＤＡＲデータに基づいた共分散行列を含む、データの統計的蓄積を表してよい。そのような例においては、ＬＩＤＡＲデータ１１６は、図１においては、説明の目的で、多数の点として示されているが、各ボクセル１１０は、それらの点の統計的蓄積だけを記憶してよい。いくつかの例においては、オペレーション１１２は、平面１１８をＬＩＤＡＲデータ１１６に適合させることを含むことができ、それは、（例えば、固有値分解または主成分分析を共分散行列に対して実行することによって、例えば、共分散行列に少なくとも部分的に基づいて）ＬＩＤＡＲデータ１１６の平面近似を決定することを含んでよい。例えば、オペレーション１１２は、平面１１８をデータ１１６に適合させるために、固有値分解または主成分分析をボクセル１１０内に表されたＬＩＤＡＲデータ１１６に対して実行することを含んでよい。いくつかの例においては、オペレーション１１２は、ボクセル１１０内に表されたＬＩＤＡＲデータ１１６の平面近似を、少なくとも部分的に、ボクセル１１０の近隣ボクセルと関連付けられたデータ上において決定することを含んでよい。オペレーション１１２は、平面１１８と関連付けられた法線ベクトル１２０を決定することも含むことができる。さらに、オペレーション１１２は、自律車両の方位に対応してよい、基準方向を決定することを含むことができ、法線ベクトル１２０が、基準方向に関して、閾値量または方位内にあるかどうかを決定することを含んでよい。
【００２１】
非限定的な例として、オペレーション１１２においてグランド平面を決定することは、共通の座標系において表現された、そのようなＬＩＤＡＲシステムを搭載した装置の高さ次元（例えば、基準方向）におけるベクトルと、法線ベクトル１２０との間の内積を決定することを含んでよい。そのような例においては、１５度の閾値を超える内積は、ボクセル１１０がグランドを含まないことを示してよい。
【００２２】
さらに、オペレーション１１２は、グランドに対応する面を拡張するために、局所的にフラットなボクセルであると決定されたボクセルをクラスタ化することを含んでよい。グランドを決定する追加の詳細が、図２、図３、および図４との関連において提供され、本開示の全体を通しても提供される。
【００２３】
オペレーション１２２において、プロセスは、オブジェクトと関連付けられたボクセルを決定することを含むことができる。いくつかの例においては、オペレーション１１２に続いて、オペレーション１２２は、グランドの表示、グランド平面、および／またはグランドに対応するボクセルを受信することと、グランドと関連付けられたボクセルのサブセットを除去することとを含むことができる。この除去オペレーションの後、ボクセル空間内に残存するボクセルは、オブジェクトを表してよい。例１２４は、例１０８に示されたボクセル空間に対応してよい、ボクセル空間１０８’の上面図表現を示している。いくつかの例においては、ボクセル空間１０８’は、環境内のオブジェクトを表すＬＩＤＡＲデータ１２６、１２８を含む。いくつかの例においては、オペレーション１２２は、ＬＩＤＡＲデータ点１２６がオブジェクト１３０と関連付けられると決定し、ＬＩＤＡＲデータ点１２８がオブジェクト１３２と関連付けられると決定するための、クラスタリングを含むことができる。いくつかの例においては、オペレーション１２２は、閾値を下回る数のボクセルと関連付けられたオブジェクトを除去すること、またはさもなければ、オブジェクトと関連付けられたボクセルの数、個々のボクセルと関連付けられたＬＩＤＡＲデータ点の数、もしくは２つの任意の組み合わせに少なくとも部分的に基づいて、オブジェクトを分類することを含んでよい。いくつかの例においては、オペレーション１２２は、他の占有されたボクセルに隣接する占有されたボクセルに少なくとも部分的に基づいて、オブジェクトを決定してよい。理解されてよいように、グランドをボクセル空間１０８’から除去することによって、オブジェクト１３０、１３２は、グランドボクセルによって接続されずに隔離されてよく、オブジェクト１３０、１３２の効率的な識別および区分化をもたらす。
【００２４】
オペレーション１３４において、プロセスは、環境内の動的オブジェクトを決定することを含んでよい。例えば、ＬＩＤＡＲデータは、経時的に蓄積されるので、オペレーション１３４は、第１の時間に占有されていないボクセルを決定し、そのボクセルが第２の時間に占有されていると決定することによって、動きを決定することを含んでよい。例１３６においては、オブジェクト１３８は、第１の時間に対応するＴ1において、ボクセル空間内に表されることができ、オブジェクト１３８’は、第１の時間と異なる、第１の時間に後続する時間に対応してよいＴ2において、ボクセル空間内に表されることができる。したがって、オペレーション１３４は、オブジェクト１３８が、（例えば、オブジェクト１３８’として）時間につれて動いており、動的オブジェクトに対応してよいことを決定するために、ボクセルの占有を経時的にトラッキングすることを含んでよい。
【００２５】
さらに、オペレーション１３４は、第１の時間Ｔ1において占有されていたボクセルが、第２の時間Ｔ2において占有されていないと決定するために、レイキャスティングオペレーションを含んでよい。例えば、ＬＩＤＡＲセンサ１４０は、オブジェクト１３８を識別および区分化するために、ベクトル１４２によって表されるＬＩＤＡＲデータを捕捉してよい。その後、第２の時間Ｔ2において、ＬＩＤＡＲセンサ１４０は、例えば、壁またはビルディングに対応してよいオブジェクト１４６を識別および区分化するために、ベクトル１４４として表されるＬＩＤＡＲデータを捕捉してよい。いくつかの例においては、図５との関連において論じられるように、例えば、オペレーション１３４は、ＬＩＤＡＲセンサ１４０とオブジェクト１４６との間のボクセルが占有されていないことを決定するために、ベクトル１４４が通過するボクセルを決定することを含んでよい。いくつかの例においては、これらのレイキャスティングオペレーションは、例えば、オブジェクト１３８が動的オブジェクトであると決定するために、使用されることができる。さらに、例１３６において示されるレイキャスティングオペレーションは、経時的に蓄積するＬＩＤＡＲデータを表すマップをクリアするために、使用されることができ、それは、オブジェクトトラッキング、軌道プランニングなどの正確性を改善することができる。別の例として、レイキャスティングオペレーションは、局所的に捕捉されたＬＩＤＡＲデータと、以前に捕捉されたＬＩＤＡＲデータを表す全体マップとの間の差を決定するために、使用されることができる。
【００２６】
オペレーション１４８において、プロセスは、トラッキングおよび／または軌道プランニングのために、静的および／または動的オブジェクトのリストを提供することを含んでよい。例えば、プロセス１００は、グランド、静的オブジェクト、および／または動的オブジェクトに対応する、環境の部分を識別および区分化してよい。いくつかの例においては、動的オブジェクトのリストは、各動的オブジェクトの軌道を経時的にトラッキングおよび／または予測するために、トラッキングシステムに提供されることができる。いくつかの例においては、静的オブジェクトのリスト、および／またはグランドの識別は、運転可能な面を辿り、本明細書において識別される静的オブジェクトを回避し、またはさもなければ考慮する、自律車両のための軌道を生成するために、プランナシステムに提供されてよい。上記および他のオペレーションは、本明細書において説明される識別および区分化オペレーションの一部として、可能である。
【００２７】
図２は、本明細書において説明されるような、オブジェクト識別を実施するための例示的なアーキテクチャを示している。例えば、アーキテクチャ２００は、本明細書において説明されるシステム、方法、および装置の態様を実施するための、様々なハードウェアおよび／またはソフトウェアを含む、１つまたは複数のコンピュータシステム２０２を含んでよい。例えば、コンピュータシステム２０２は、ＬＩＤＡＲモジュール２０４と、カメラモジュール２０６と、ＲＡＤＡＲモジュール２０８と、ＳＯＮＡＲモジュール２１０と、ボクセル空間モジュール２１２と、グランド決定モジュール２１４と、クラスタリングモジュール２１６と、補間モジュール２１８と、オブジェクト決定モジュール２２０と、動的オブジェクト決定モジュール２２２と、レイキャスティングモジュール２２４と、トラッキングモジュール２２６と、プランニングモジュール２２８と、センサ較正モジュール２３０と、注釈モジュール２３２とを含んでよい。
【００２８】
いくつかの例においては、コンピュータシステム２０２は、自律車両内において具体化されてよい。いくつかの例においては、コンピュータシステム２０２は、自律車両用の知覚およびプランニング機能性を提供してよい。一般に、コンピュータシステム２０２は、ＬＩＤＡＲ知覚と、ＲＡＤＡＲ知覚と、ビジョン（カメラ）知覚と、音響知覚と、区分化および分類と、トラッキングおよび融合と、予測／プランニングとを含んでよい。
【００２９】
ＬＩＤＡＲモジュール２０４を参照すると、ＬＩＤＡＲモジュール２０４は、本明細書において説明されるように、区分化のためにＬＩＤＡＲデータを捕捉する、１つまたは複数のＬＩＤＡＲセンサを含んでよい。図２においては、ＬＩＤＡＲデータとして示されているが、そのようなＬＩＤＡＲモジュール２０４は、本明細書において詳細に説明されるような、いずれか１つまたは複数の深度センサを備えてよい。いくつかの例においては、ＬＩＤＡＲモジュール２０４は、複数のＬＩＤＡＲセンサからのＬＩＤＡＲデータを組み合わせて、または合成して、複数のＬＩＤＡＲセンサに基づいたＬＩＤＡＲデータのことを指してよい、ＬＩＤＡＲデータのメタスピンを生成するための機能性を含んでよい。ＬＩＤＡＲデータのメタスピンの場合、ＬＩＤＡＲモジュール２０４は、メタスピンデータの仮想起点（virtual origin）（例えば、すべてのＬＩＤＡＲセンサに共通する基準座標系）を決定し、１つまたは複数のＬＩＤＡＲセンサの各々からのＬＩＤＡＲデータが、仮想起点に関して表現されるように、データ変換を実行するための機能性を含んでよい。本開示との関連において理解されてよいように、ＬＩＤＡＲモジュール２０４は、データを捕捉してよく、後続する処理のために、データセットをコンピュータシステム２０２に送信してよい。
【００３０】
カメラモジュール２０６は、画像区分化および／または分類のためにビジョンデータを捕捉する、１つまたは複数のカメラセンサを含んでよい。カメラモジュール２０６は、任意の数およびタイプのカメラセンサを含んでよい。例えば、カメラモジュール２０６は、任意のカラーカメラ、モノクロームカメラ、深度カメラ、ＲＧＢ−Ｄカメラ、ステレオカメラ、赤外線（ＩＲ）カメラ、紫外線（ＵＶ）カメラなどを含んでよい。本開示との関連において理解されてよいように、カメラモジュール２０６は、データを捕捉してよく、後続する処理のために、データセットをコンピュータシステム２０２に送信してよい。例えば、カメラモジュール２０６からのデータは、マルチチャネル画像の１つまたは複数のチャネルとして含まれてよい。
【００３１】
ＲＡＤＡＲモジュール２０８は、環境内のオブジェクトの範囲、角度、および／または速度を捕捉する、１つまたは複数のＲＡＤＡＲセンサを含んでよい。本開示との関連において理解されてよいように、ＲＡＤＡＲモジュール２０８は、データを捕捉してよく、後続する処理のために、データセットをコンピュータシステム２０２に送信してよい。例えば、ＲＡＤＡＲモジュール２０８からのデータは、マルチチャネル画像の１つまたは複数のチャネルとして含まれてよい。
【００３２】
ＳＯＮＡＲモジュール２１０は、環境内のオブジェクトの音響情報を捕捉するための、１つまたは複数のスピーカまたは音エミッタと、（マイクロフォンアレイなどの）１つまたは複数のマイクロフォンとを含んでよい。加えて、または代わりに、そのようなＳＯＮＡＲモジュール２１０は、様々な超音波トランスデューサを備えてよい。例えば、ＳＯＮＡＲモジュール２１０は、音のパルスを発してよく、エコーを聴き取って、環境内のオブジェクトと関連付けられた位置および／または動き情報を決定してよい。本開示との関連において理解されてよいように、ＳＯＮＡＲモジュール２１０は、データを捕捉してよく、後続する処理のために、データセットをコンピュータシステム２０２に送信してよい。例えば、ＳＯＮＡＲモジュール２１０からのデータは、オブジェクトをより正確に区分化するために、および／またはオブジェクトについての情報を決定するために、ＬＩＤＡＲモジュール２０４からのデータと融合されてよい。
【００３３】
コンピュータシステム２０２は、例えば、自律車両における使用に適した、任意の数またはタイプの他のセンサを含んでよい。様々なセンサは、超音波トランスデューサ、ホイールエンコーダ、マイクロフォン、慣性測定ユニット（ＩＭＵ）、加速度計、ジャイロスコープ、磁力計、温度センサ、湿度センサ、光センサ、全地球測位システム（ＧＰＳ）センサなどを含んでよいが、それらに限定されない。
【００３４】
いくつかの例においては、ＬＩＤＡＲモジュール２０４、カメラモジュール２０６、ＲＡＤＡＲモジュール２０８、および／またはＳＯＮＡＲモジュール２１０は、改善された区分化のための、データの組み合わせおよび／または合成を行うために、１つまたは複数のデータセットをコンピュータシステム２０２に提供してよい。
【００３５】
コンピュータシステム２０２は、一部はテストにおける使用のために、コンピュータシミュレーションアルゴリズムによって生成された、シミュレートされたデータをさらに含んでよい。いくつかの例においては、シミュレートされたデータは、カメラデータ、ＬＩＤＡＲデータ、ＲＡＤＡＲデータ、ＳＯＮＡＲデータ、慣性データ、ＧＰＳデータなど、任意のタイプのシミュレートされたデータを含んでよい。いくつかの例においては、コンピュータシステム２０２は、本明細書において説明されるように、オペレーションを検証するために、および／または機械学習アルゴリズムをトレーニングするために、シミュレートされたデータに対する本明細書において説明される変換オペレーションを変更し、変換し、および／または実行することができる。
【００３６】
ボクセル空間モジュール２１２は、マップデータをボクセル空間に変換するための機能性を含んでよい。例えば、ボクセル空間モジュール２１２は、ＬＩＤＡＲデータ、カメラデータ、ＲＡＤＡＲデータ、ＳＯＮＡＲデータなどを受信し、個々のデータ点を、環境内の３次元空間を表すボクセルにマップし、変換し、または関連付けることができる。いくつかの例においては、ボクセル空間モジュール２１２は、ボクセル空間の長さ、幅、および高さを含む、ボクセル空間の次元を定義することができる。さらに、ボクセル空間モジュール２１２は、個々のボクセルのサイズを決定してよい。いくつかの例においては、ボクセルは、ボクセル空間の全体を通して均一のサイズおよび形状であってよく、一方、いくつかの例においては、ボクセルのサイズおよび／または密度は、ボクセル空間内の相対位置に基づいて、変化してよい。例えば、ボクセルのサイズは、ボクセル空間の起点または中心からのボクセルの距離に比例して、増大または減少してよい。加えて、または代わりに、そのようなボクセル空間モジュール２１２は、仮想起点とボクセル空間の起点との間の変換を含んでよい。いくつかの例においては、ボクセル空間モジュール２１２は、疎らなボクセル空間を生成するための機能性を含んでよく、それは、データを含まない、またはデータ閾値を下回る量のデータしか含まないボクセルを廃棄することを含んでよい。そのような例においては、ボクセル空間は、オクトマップ、またはボクセルハッシングなどを含んでよい。いくつかの例においては、ボクセル空間モジュール２１２は、データを、それがボクセル空間にマップされるときにフィルタリングすることによって、データ内のノイズの量を低減させるための機能性を含んでよい。例えば、フィルタリングは、ボクセル当たりのデータの閾値量（例えば、ボクセルと関連付けられたＬＩＤＡＲデータ点の数）を下回るデータ、または事前決定されたボクセルの数（例えば、近接ボクセルの数と関連付けられたＬＩＤＡＲデータ点の数）を超えるデータを除去することを含んでよい。いくつかの例においては、ボクセル空間モジュール２１２は、データが経時的に集められたときに、および／またはボクセル空間内を運行する自律車両に応答して、ボクセル空間を更新することができる。例えば、ボクセル空間モジュール２１２は、自律車両が環境内を運行するときに、ボクセル空間にデータを追加してよく、および／またはボクセル空間からデータを廃棄してよい。
【００３７】
いくつかの例においては、ボクセル空間モジュール２１２は、ボクセル空間を空の空間として初期化することができ、ＬＩＤＡＲデータが経時的に捕捉されるにつれて、オブジェクトの表現を構築することができる。他の例においては、ボクセル空間モジュール２１２は、局所的に捕捉されたＬＩＤＡＲデータが、全体マップ空間内において自律車両を位置特定するために使用されることができ、全体マップのボクセルをクリーンアップする、またはクリアするために使用されることができるように、全体マップデータを用いてボクセル空間を初期化することができる。
【００３８】
グランド決定モジュール２１４は、ボクセル空間の個々のボクセルを解析して、ボクセル空間内において環境と関連付けられたグランドを決定するための機能性を含んでよい。例えば、グランド決定モジュール２１４は、特定のボクセルと関連付けられたデータを代表する平面を推定し、その平面の法線ベクトルを決定することによって、局所的にフラットなボクセルを決定してよい。例えば、グランド決定モジュール２１４は、ボクセルに対して主成分分析を実行して、ボクセルと関連付けられたデータと関連付けられた最小主成分を決定してよい。いくつかの例においては、主成分分析の場合、最小固有ベクトルは、平面の法線ベクトルに対応してよく、一方、固有ベクトルと関連付けられた固有値は、最小固有ベクトルの方向における特定のボクセルと関連付けられたデータの拡散のスプレッドまたはレベルに対応してよい。別の例として、限定することなく、そのような面法線決定は、ボクセル内の点ＰからＰの最も近い２つの近隣点までの方向を示すベクトルの外積の法線を計算することによって行われてよい。別の例として、限定することなく、そのような面法線決定は、個々のボクセルと関連付けられた共分散行列に対する固有値分解を実行することによって、行われてよい。いくつかの例においては、グランド決定モジュール２１４は、近隣ボクセルと関連付けられた値に基づいて、ターゲットボクセルと関連付けられた面を決定することによって、ターゲットボクセルが局所的にフラットなボクセルであるかどうかを決定してよい。さらに、いくつかの例においては、グランド決定モジュール２１４は、面を生成する少なくとも３つの点を含む三角形を決定するために、マーチングキューブタイプのアルゴリズムを利用して、ボクセルと関連付けられた平均点値に基づいてメッシュを生成してよい。さらに、グランド決定モジュール２１４は、自律車両の方向または方位に対応してよい、基準方位を受信してよい。グランド決定モジュール２１４は、上で説明されたように、ボクセルと関連付けられた法線ベクトルが、基準方位の閾値量内にある場合、ボクセルは局所的にフラットなボクセルであると決定してよい。
【００３９】
クラスタリングモジュール２１６は、ＬＩＤＡＲデータの起点に最も近い面から開始して、または自律車両の下の面から開始して、グランド領域を拡張するために、グランド決定モジュール２１４と連携して動作してよい。すなわち、自律車両に近接したボクセルが、クラスタリングモジュール２１６のためのシードボクセル（seed voxel）として使用されてよい。クラスタリングモジュール２１６は、隣接する局所的にフラットなボクセルが同じクラスタに属すると決定してよく、グランド平面を取り囲むように、領域を拡張してよい。さらに、クラスタリングモジュール２１６は、ボクセルが特定のオブジェクトと関連付けられていると決定するために、以下で論じられるオブジェクト決定モジュール２２０と連携して動作してよい。クラスタリングモジュール２１６は、領域拡張、階層的クラスタリング、分割クラスタリング（partitional clustering）、平方誤差クラスタリング、グラフ理論クラスタリング、混合−分解クラスタリング（mixture-resolving clustering）、平均シーククラスタリング（mean-seeking clustering）、ｋ平均クラスタリング、Ｎカットクラスタリング（N-cut clustering）、近接クラスタリングなどを含むが、それらに限定されない、様々なクラスタリングアルゴリズムを利用してよい。
【００４０】
補間モジュール２１８は、様々なクラスタを一緒に組み合わせて、または関連付けて、グランド平面を拡大するために、グランド決定モジュール２１４および／またはクラスタリングモジュール２１６と連携して動作してよい。例えば、局所的にフラットなボクセルは、自律車両と関連付けられたグランド領域を決定するとき、単一のクラスタを形成しなくてよく、その場合、補間モジュール２１８は、グランド平面クラスタを拡張するために、点の間を補間して、勾配が閾値勾配を上回るか、それとも下回るかを決定してよい。グランド決定モジュール２１４、クラスタリングモジュール２１６、および補間モジュール２１８の追加の態様が、図３および図４との関連において以下で提供され、本開示の全体を通しても提供される。
【００４１】
オブジェクト決定モジュール２２０は、ボクセル空間内に表されたオブジェクトを決定するための機能性を含んでよい。例えば、オブジェクト決定モジュール２２０は、グランド決定モジュール２１４からグランド平面の表示を受信し、および／または局所的にフラットなボクセルのいくつかもしくはすべての表示を受信してよく、グランドと関連付けられたボクセルをボクセル空間から除去してよい。次に、オブジェクト決定モジュール２２０は、残存するボクセルを解析して、ボクセルの接続性に基づいてオブジェクトを決定してよい。例えば、オブジェクト決定モジュール２２０は、隣接ボクセルが同じオブジェクトの一部であると見なされるべきであると決定することによって、オブジェクトに対応するボクセル空間内の領域を拡張するために、クラスタリングモジュール２１６と連携して動作してよい。オブジェクト決定モジュール２２０は、特定のオブジェクトと関連付けられたすべてのボクセルに、オブジェクト識別子を割り当ててよく、いくつかの例においては、オブジェクト決定モジュール２２０によって割り当てられた、または決定されたオブジェクト識別子は、特定のオブジェクトを含むボクセルと関連付けられたＬＩＤＡＲデータに伝搬されてよい。オブジェクト決定モジュール２２０の追加の態様が、図３との関連において以下で提供され、本開示の全体を通しても提供される。
【００４２】
動的オブジェクト決定モジュール２２２は、静的オブジェクトと動的オブジェクトとを区別するための機能性を含んでよい。例えば、動的オブジェクト決定モジュール２２２は、データを経時的に蓄積して、第１の時間におけるボクセルを第２の時間におけるボクセルと比較して、ボクセルの占有が時間につれて変化したかどうかを決定することによって、オブジェクトの動きを決定してよい。例えば、第１の時間にオブジェクトによって占有されていたボクセルが、第２の時間にそのオブジェクトによって占有されていない場合、動的オブジェクト決定モジュール２２２は、オブジェクトが動的オブジェクトであると決定することができる。どのボクセルが時間につれて占有されるようになり、または占有されなくなるかに基づいて、動的オブジェクト決定モジュール２２２は、運動のスピードおよび方向など、動的オブジェクトの運動を決定することができる。いくつかの例においては、動的オブジェクト決定モジュール２２２は、動的オブジェクトの運動を決定するための表示を提供することができる。動的オブジェクト決定モジュール２２２の追加の態様が、図５との関連において以下で提供され、本開示の全体を通しても提供される。
【００４３】
レイキャスティングモジュール２２４は、静的オブジェクトと動的オブジェクトとを区別するために、動的オブジェクト決定モジュール２２２と連携して動作してよい。さらに、レイキャスティングモジュール２２４は、データがボクセル空間内に蓄積されるので、ボクセル空間を経時的にクリアするための機能性を含んでよい。例えば、オブジェクトは、時間につれてボクセル空間の全体にわたって動くので、動的オブジェクトによって占有されるボクセルは、時間につれてデータで満たされてよい。しかしながら、レイキャスティングモジュール２２４は、ＬＩＤＡＲデータと関連付けられた光線の経路を分析して、例えば、光線がその中を伝わるボクセルがクリアされるべきであると決定してよい。したがって、レイキャスティングモジュール２２４は、第１の時間に占有されていたボクセルが第２の時間に占有されていないとの決定を行うための追加の機能性を提供してよく、それは、例えば、オブジェクトが動的オブジェクトであると決定するために、様々なモジュールに提供されてよい。いくつかの例においては、ボクセル空間は、（例えば、占有されているボクセルを表し、占有されていないボクセルを無視する）疎方式で、または（例えば、廃棄ボクセルのない）密方式で表されてよい。いくつかの例においては、レイキャスティングモジュール２２４は、密方式においては、レイキャスティング情報を記憶してよく、すなわち、（例えば、ボクセルが、関連付けられたＬＩＤＡＲデータを有さないために）疎ボクセル表現において存在しないボクセルが、そのようなボクセルと関連付けられたレイキャスティング情報を有することができる。例えば、関連付けられたＬＩＤＡＲデータを有さないボクセルは、それにもかかわらず、ボクセルと関連付けられたレイキャスティング情報を含むために、密ボクセル空間において表されることができる。いくつかの例においては、密ボクセル表現は、本明細書において論じられるレイキャスティングオペレーションに少なくとも部分的に応答して、ボクセルが占有されていないという積極的な情報をボクセルと関連付けてよい。さらに、ＬＩＤＡＲデータが個々のボクセル内に蓄積されるので、例えば、それらが静的オブジェクトで占有されているという消極的な情報が、個々のボクセルと関連付けられてよい。データが経時的に蓄積されるので、情報が集約されて、一部は、例えば、ボクセルが空き空間を表すか、それとも静的オブジェクトを表すかを決定することができる。さらに、レイキャスティングモジュール２２４は、局所的に捕捉されたＬＩＤＡＲデータを全体マップデータと比較することによって、全体マップをクリーンアップするために使用されてよい。レイキャスティングモジュール２２４の追加の態様が、図５との関連において以下で提供され、本開示の全体を通しても提供される。
【００４４】
トラッキングモジュール２２６は、オブジェクトをトラッキングするために、１つまたは複数の動的オブジェクトの表示を受信し、追加の処理を実行するための機能性を含んでよい。例えば、トラッキングモジュール２２６は、動的オブジェクトの速度を決定してよく、および／または経時的に動的オブジェクトの軌道を決定し、記憶してよい。いくつかの例においては、トラッキングモジュール２２６は、オブジェクトの以前の動きに基づいて、トラッキングされるオブジェクトの経路を予測してよい、予測アルゴリズムを含んでよい。
【００４５】
プランニングモジュール２２８は、区分化されたデータ、ならびに／またはグランド平面、静的オブジェクト、および／もしくは動的オブジェクトの表示を受信して、自律車両の軌道を決定するための機能性を含んでよい。例えば、プランニングモジュール２２８は、グランド平面を識別する区分化情報を受信してよく、自律車両が辿る軌道を生成してよい。
【００４６】
センサ較正モジュール２３０は、環境に関して決定された区分化情報に少なくとも部分的に基づいて、１つまたは複数のセンサを較正するための機能性を含んでよい。例えば、ＬＩＤＡＲモジュール２０４、カメラモジュール２０６、ＲＡＤＡＲモジュール２０８、および／またはＳＯＮＡＲモジュール２１０からのセンサデータは、（例えば、ＳＬＡＭ（同時位置特定およびマッピング（simultaneous localization and mapping））を使用して、位置および／または方位を推定するために使用されてよいが、自律車両は、環境における自律車両の位置を決定するための、慣性測定ユニット（ＩＭＵ）および／またはＧＰＳユニットなどの、追加のセンサも含んでよい。いくつかの例においては、ＩＭＵは、自律車両が第１の位置にあることを示してよく、一方で、本明細書において論じられるＬＩＤＡＲデータの分析は、車両が第１の位置とは異なる第２の位置にあることを示す。センサ較正モジュール２３０は、位置の差を決定してよく、自律車両の位置、または１つもしくは複数のセンサ内的特性もしくは外的特性を更新するために、１つまたは複数のセンサを調整または較正してよい。
【００４７】
注釈モジュール２３２は、本明細書において論じられる区分化情報を受信するための機能性を含んでよく、オブジェクトと関連付けられた情報を用いて、グランド平面、静的オブジェクト、および／または動的オブジェクトに注釈を施してよい。いくつかの例においては、注釈モジュール２３２は、例えば、技術者による人手の検証および／または調整のために、区分化情報をグラフィカルユーザインターフェース内に提供してよい。いくつかの例においては、注釈モジュール２３２は、本明細書において論じられるオブジェクトの分類を決定および適用するための機能性を含んでよい。注釈モジュール２３２は、区分化および分類のオペレーションを実行するために、ニューラルネットワークなど、任意の機械学習アルゴリズムを含んでよい。
【００４８】
本明細書において説明されるように、例示的なニューラルネットワークは、生物学から発想を得たアルゴリズムであり、それは、入力データが一連の接続されたレイヤを通過するようにして、出力を生成する。ニューラルネットワークの一例は、畳み込みニューラルネットワーク（ＣＮＮ）を含んでよい。ＣＮＮの各レイヤは、別のＣＮＮを含んでよく、または任意の数のレイヤを含んでよい。本開示との関連において理解されてよいように、ニューラルネットワークは、出力が学習されたパラメータに基づいて生成されるようなアルゴリズムの広範なクラスのことを指してよい、機械学習を利用してよい。
【００４９】
ニューラルネットワークとの関連において論じられるが。本開示と矛盾しない任意のタイプの機械学習が、使用されてよい。例えば、機械学習アルゴリズムは、回帰アルゴリズム（例えば、最小２乗回帰（ＯＬＳＲ）、線形回帰、ロジスティック回帰、ステップワイズ回帰、多変量適応型回帰スプライン（ＭＡＲＳ：multivariate adaptive regression splines）、局所的に推定された散布図平滑化（ＬＯＥＳＳ：locally estimated scatterplot smoothing））、インスタンスベースのアルゴリズム（例えば、リッジ回帰（ridge regression）最小絶対収縮および選択演算子（ＬＡＳＳＯ：least absolute shrinkage and selection operator）、弾性ネット（elastic net）、最小角回帰（ＬＡＲＳ：least-angle regression））、決定木アルゴリズム（例えば、分類回帰木（ＣＡＲＴ：classification and regression tree）、反復二分器３（ＩＤ３：iterative dichotomiser 3）、カイ２乗自動相互作用検出（ＣＨＡＩＤ：Chi-squared automatic interaction detection）、決定株（decision stump）、条件付き決定木）、ベイジアンアルゴリズム（例えば、ナイーブベイズ、ガウシアンナイーブベイズ、多項ナイーブベイズ（multinomial naive Bayes）、平均一依存エスティメータ（ＡＯＤＥ：average one-dependence estimators）、ベイジアン信念ネットワーク（ＢＮＮ：Bayesian belief network）、ベイジアンネットワーク）、クラスタリングアルゴリズム（例えば、ｋ平均法、ｋメジアン法、期待値最大化（ＥＭ）、階層的クラスタリング）、相関ルール学習アルゴリズム（association rule learning algorithm）（例えば、パーセプトロン（perceptron）、バックプロパゲーション（back-propagation）、ホップフィールドネットワーク（hopfield network）、放射基底関数ネットワーク（ＲＢＦＮ：Radial Basis Function Network））、深層学習アルゴリズム（例えば、深層ボルツマンマシン（ＤＢＭ：Deep Boltzmann Machin）、深層信念ネットワーク（ＤＢＮ）、畳み込みニューラルネットワーク（ＣＮＮ）、積層オートエンコーダ（Stacked Auto-Encoder））、次元削減アルゴリズム（例えば、主成分分析（ＰＣＡ）、主成分回帰（ＰＣＲ）、部分最小２乗回帰（ＰＬＳＲ）、サモンマッピング（Sammon Mapping）、多次元スケーリング（ＭＤＳ）、射影追跡、線形判別分析（ＬＤＡ）、混合判別分析（ＭＤＡ）、２次判別分析（ＱＤＡ）、柔軟判別分析（ＦＤＡ））、アンサンブルアルゴリズム（例えば、ブースティング、ブートストラップアグリゲーション（Bootstrapped Aggregation）（（バギング（Bagging））、アダブースト（AdaBoost）、スタック汎化（Stacked Generalization）（ブレンディング（blending））、勾配ブースティングマシン（ＧＢＭ：Gradient Boosting Machines）、勾配ブースト回帰木（ＧＢＲＴ：Gradient Boosted Regression Trees）、ランダムフォレスト）、ＳＶＭ（サポートベクトルマシン）、教師あり学習、教師なし学習、半教師あり学習などを含んでよいが、それらに限定されない。
【００５０】
コンピュータシステム２０２の追加の詳細が、図１１との関連において以下で提供される。
【００５１】
図３は、ボクセル空間において表されたグランド領域を識別するための例示的なプロセス３００のフローチャートを示している。
【００５２】
オペレーション３０２において、プロセスは、データと関連付けられたボクセルを受信することを含むことができる。例えば、オペレーション３０２は、図１との関連において上で論じられたように、ボクセル空間にマッピングまたは変換されたＬＩＤＡＲデータを含む、１つまたは複数のボクセルを受信することを含むことができる。いくつかの例においては、オペレーション３０２は、ボクセル空間を受信することと、ボクセル空間の各ボクセルを解析することとを含むことができる。いくつかの例においては、ボクセルと関連付けられたデータは、ＬＩＤＡＲデータ、カメラデータ、ＲＡＤＡＲデータ、ＳＯＮＡＲデータ、全体マップデータ、およびそれらの任意の組み合わせを含んでよい。例３０４は、例えば、ＬＩＤＡＲデータ３０８を含む）ボクセル３０６を示している。
【００５３】
オペレーション３１０において、プロセスは、面を１つまたは複数のボクセルと関連付けられたデータに適合させることを含むことができる。例３１２において、面３１４は、ボクセル３０６と関連付けられたＬＩＤＡＲデータ３０８に適合させられる。いくつかの例においては、オペレーション３１０は、面３１４と関連付けられた法線ベクトル３１６を決定することをさらに含んでよい。いくつかの例においては、オペレーション３１０は、ＬＩＤＡＲデータ３０８の主成分分析を実行して、法線３１６に対応してよい、最小主成分を決定することを含んでよい。いくつかの例においては、概念的には、面３１４は、法線ベクトル３１６を決定することの一部として決定されてよいが、オペレーション３１０は、面３１４をＬＩＤＡＲデータ３０８に明確に適合させなくてよい。いくつかの例においては、オペレーション３１０は、ターゲットボクセルと関連付けられた近隣ボクセルに基づいて、ターゲットボクセルと関連付けられた面を決定することを含んでよい。いくつかの例においては、オペレーション３１０は、ボクセルと関連付けられたメッシュを決定することと、特定のボクセル（例えば、ボクセル３０６）と関連付けられた面を決定することとを含んでよい。
【００５４】
オペレーション３１８において、プロセスは、基準方向を決定することを含むことができる。例３２０において、基準方向３２２は、自律車両３２４の方位に対応してよい。非限定的な例として、基準方向３２２は、自律車両３２４の高さ方向に沿った単位ベクトルを含んでよい。したがって、自律車両３２４は、様々な面上（フラットな面、上り／下りする坂、傾斜面上など）を運行するので、基準方向３２２は、変化してよい。加えて、または代わりに、オペレーション３１８は、自律車両３２４を中心とする座標系からボクセル空間３０６の座標系への座標変換を含んでよい。
【００５５】
オペレーション３２６において、プロセスは、面法線ベクトルが基準方向の閾値内にあると決定することを含むことができる。例えば、閾値は、あらかじめ決定されてよく、または自律車両３２４の位置、路面のタイプ、自律車両３２４の速度などに基づいて、変化してよい。例３２８において、面法線ベクトル３１６は、２つのベクトルが角度Θを形成する、面法線ベクトル３１６と基準方向３２２との間の内積を取ることによって、基準方向３２２と比較される。いくつかの例においては、閾値は、１５度など、任意の角度になるように設定されてよく、Θが１５度よりも大きい場合、ボクセルは、局所的にフラットなボクセルに対応しないと決定される。
【００５６】
オペレーション３３０において、面法線ベクトル３１６が、基準方向の閾値内にある場合、プロセスは、ボクセルが局所的にフラットなボクセルであると決定することを含むことができる。オペレーション３３０は、ボクセルが局所的にフラットなボクセルであることを示すために、タグまたは識別子をボクセルと関連付けることを含んでよい。いくつかの例においては、タグまたは識別子は、特定のボクセルと関連付けられたＬＩＤＡＲデータに伝搬させることができる。
【００５７】
オペレーション３３２において、プロセスは、クラスタリングを実行して、自律車両３２４のための運転可能な面に対応してよい、フラットな領域を決定することを含むことができる。例３３４は、ボクセル３０６を含んでよい、ボクセル空間３３６の代表的な上面図（例えば、ｘ−ｙ平面におけるボクセル空間３３６の単一のレイヤ）を示している。いくつかの例においては、ボクセル空間３３６は、本明細書において論じられるような、局所的にフラットなボクセルに対応すると決定された複数のボクセルを含む。領域拡張技法を使用して、オペレーション３２２は、局所的にフラットなボクセルと関連付けられたＬＩＤＡＲデータ３３８、３４０を含むように、クラスタを拡張してよい。いくつかの例においては、クラスタは、互いに隣接する、または別の局所的にフラットなボクセルまでの距離が閾値距離内にある、局所的にフラットなボクセルを決定することによって拡張されて、第１のクラスタ３４２および第２のクラスタ３４４を生成してよい。いくつかの例においては、オペレーション３３２は、自律車両３２４’に近接したクラスタが、１次グランドクラスタであると見なされるべきであると決定してよい。したがって、１次グランドクラスタを拡張するとき、自律車両３２４’の位置が、シード点（seed point）に対応してよい。
【００５８】
オペレーション３４６において、プロセスは、グランドクラスタを拡張するために、ボクセル空間において補間を行うことを含むことができる。いくつかの例においては、オペレーション３４６において拡張されるグランドクラスタは、１次グランドクラスタに対応することができ、それは、自律車両３２４’に近接したクラスタに対応してよい。オペレーション３４６の追加の詳細は、図４との関連において提供される。
【００５９】
図４は、グランドクラスタを拡張するために、ボクセル空間において補間を行うための、例示的なプロセス４００のフローチャートを示している。
【００６０】
オペレーション４０２において、プロセスは、グリッドにおけるグランドセルの平均高さを決定することを含むことができる。例４０４において、ボクセル空間３３６は、局所的にフラットなボクセルからなるクラスタを表す、上で論じられたような、第１のクラスタ３４２と、第２のクラスタ３３４とを含む。いくつかの例においては、プロセス４００は、第１のクラスタ３４２と第２のクラスタ３４４が結合されて、単一のクラスタを形成すべきかどうかを決定するために、使用されることができる。いくつかの例においては、オペレーション４０２は、第１のクラスタ３４２における個々のボクセル内の点の平均高さを決定することを含むことができ、いくつかの例においては、オペレーション４０２は、クラスタ３４２におけるいくつかまたはすべてのボクセルの平均高さを決定することを含むことができる。いくつかの例においては、オペレーション４０２は、例えば、張り出しを表すオブジェクトを区別するために、グランドセルの高さを決定することを含むことができる。例４０４には、以下で論じられる細部４０６が含まれる。
【００６１】
オペレーション４０８において、プロセスは、グランドセル内の点と、潜在的なグランドボクセルと関連付けられた点とについての平均高さ間の勾配を決定することを含むことができる。例４１０において、細部４０６は、第１のクラスタ３４２に含まれる第１のボクセル４１２と、第２のクラスタ３４４に含まれる第２のボクセル４１４とを示している。理解されてよいように、第１のボクセル４１２は、グランドボクセルに対応し、第２のボクセル４１４は、潜在的なグランドボクセルに対応する。第１のボクセル４１２と関連付けられた点４１６は、第１のボクセル４１２と関連付けられたＬＩＤＡＲデータの平均＜ｘ，ｙ，ｚ＞座標と関連付けられてよい。いくつかの例においては、点４１６は、第１のボクセル４１２と関連付けられたＬＩＤＡＲデータの平均＜ｘ，ｙ，ｚ＞座標に対応してよく、平均ｚ値は、少なくとも部分的に、クラスタ３４２におけるボクセルのいくつかまたはすべての平均高さ（例えば、平均ｚ値）を計算するために、使用されてよい。いくつかの例においては、第２のボクセル４１４（例えば、潜在的なグランドボクセル）と関連付けられた点４１８は、第２のボクセル４１４と関連付けられたＬＩＤＡＲデータの平均＜ｘ，ｙ，ｚ＞座標と関連付けられてよい。オペレーション４０８は、クラスタ３４２における点、またはすべての点の平均と、クラスタ３４４における点、または点の平均との間の勾配を決定することを含む。いくつかの例においては、オペレーション４０８は、（例えば、本明細書において論じられるように、勾配を決定することに加えて、またはそれの代わりに）クラスタ３４４の平均ｚ値が、クラスタ３４２の平均ｚ値についての閾値内にあるかどうかを決定するために、クラスタ３４２およびクラスタ３４４の平均ｚ値を決定することを含むことができる。
【００６２】
オペレーション４２０において、プロセスは、勾配の成分が閾値を下回るかどうかを決定することを含むことができる。例４２２は、点４１６と点４１８との間の勾配または傾斜を示す。例４２２に示される図は、例４１０に示される上面図の側面図に対応してよい。いくつかの例においては、傾斜は、点４１６と点４１８との間の水平距離４２６によって除算された高さの変化４２４（Δｚ）として、決定されることができる。したがって、いくつかの例においては、傾斜は、第１のクラスタ３４２と関連付けられた平均＜ｘ，ｙ，ｚ＞値と、第２のクラスタ３４４と関連付けられた平均＜ｘ，ｙ，ｚ＞値とに少なくとも部分的に基づくことができる。
【００６３】
オペレーション４２８において、プロセスは、グランドクラスタを拡張するために、点をグランドと関連付けることを含むことができる。例４３０は、例４０４における第１のクラスタ３４２から、例４３０における更新されたグランドクラスタ４３２への、グランドクラスタの拡張を示している。したがって、プロセス４００は、グランドクラスタを拡張してよく、それは、自律車両３２４’によって運転可能な領域のサイズを増大させる。さらに、グランドクラスタのサイズを増大させることは、オブジェクト区分化の間に無視されるデータの量を増加させてよく、それは、オブジェクトと見なされるボクセルの量を減少させることによって、処理を改善する。さらに、いくつかの例においては、グランドクラスタ内のセルの高さは、関心オブジェクトを識別して、静的オブジェクトおよび動的オブジェクトをさらに識別するために、使用されることができる。すなわち、グランドに近接した（例えば、グランド上に位置特定された）オブジェクトについては、オブジェクトの下限は、グランドの高さに対応してよい。
【００６４】
図５は、レイキャスティングおよび動的オブジェクト識別と関連付けられた例を示している。例５０２は、図１に示された例１３６に対応する。いくつかの例においては、時間Ｔ1におけるオブジェクト１３８、および時間Ｔ2におけるオブジェクト１３８’に対応する動きは、第１の時間に占有されており、第２の時間に占有されていないボクセル、およびそれとは反対のボクセルを決定することによって、識別されることができる。さらに、例５０４は、本明細書において説明されるレイキャスティングの詳細を示している。
【００６５】
例５０４において、ベクトル１４４は、ＬＩＤＡＲセンサ１４０から発し、様々なボクセルを通過して、オブジェクト１４６と関連付けられたデータを捕捉するように示されている。理解されてよいように、ベクトル１４４は、第２の時間Ｔ2と関連付けられ、それによって、オブジェクト１３８は、時間Ｔ1における第１の位置から、オブジェクト１３８’と関連付けられた、時間Ｔ2における第２の位置に移動している。したがって、ベクトル１４４は、以前、時間Ｔ1においてはオブジェクト１３８を表すデータによって占有されていた、ボクセル５０６、５０８、５１０、５１２、５１４を通過する。さらに、本明細書において説明されるオペレーションは、ベクトル１４４が通過するボクセルのいくつかまたはすべてを決定して、以前は占有されていたボクセル５０６、５０８、５１０、５１２、５１４が、第２の時間Ｔ2においては占有されていないと決定することを含んでよい。したがって、例５０４において示されるレイキャスティングは、オブジェクト１３８および１３８’が動的オブジェクトであると決定するための追加の技法を提供する。
【００６６】
さらに、本明細書において示されるレイキャスティング技法は、第２の時間Ｔ2において、ボクセル５０６、５０８、５１０、５１２、５１４をクリアするために、使用されることができる。したがって、本明細書において説明される技法は、時間的な瞬間に維持されるべきデータの量を減少させるために、ならびにボクセル空間内において動的オブジェクトを検出および区分化するためのオペレーションを改善するために、経時的にボクセル空間の状態を更新することができる。
【００６７】
別の例においては、レイキャスティング技法は、局所的に捕捉されたＬＩＤＡＲデータを、以前に捕捉された全体マップデータと比較するために、使用されることができる。例えば、オブジェクト１３８は、全体マップデータ内に表されたオブジェクトに対応してよい。しかしながら、ベクトル１４４が、オブジェクト１３８を表すボクセルを通過する場合、ベクトル１４４が、局所的に捕捉されたＬＩＤＡＲデータを表すとき、オペレーションは、全体マップと局所マップとの間に差が存在すると決定することができる。いくつかの例においては、差は、全体マップが不正確であること、または環境の状態が変化した（例えば、樹木を除去したことによって、物理的世界が変化した）ことを示してよい。この方式においては、全体マップと局所ＬＩＤＡＲデータとの間の差が決定されるので、（差が、意見の一致によって（例えば、同じもしくは似たイベントまたはデータの繰り返される観測によって）検証された場合、またはデータの信頼水準が、閾値量を上回る場合）差は、中央サーバにアップロードされて、全体マップデータに組み込まれ、他の車両に配送されることができる。
【００６８】
図１、図３、図４、および図６〜図１０は、本開示の実施形態に従った、例示的なプロセスを示している。これらのプロセスは、論理フローグラフとして示され、それの各オペレーションは、ハードウェア、ソフトウェア、またはそれらの組み合わせで実施されることができるオペレーションのシーケンスを表す。ソフトウェアとの関連において、オペレーションは、１つまたは複数のプロセッサによって実行されたとき、述べられたオペレーションを実行する、１つまたは複数のコンピュータ可読記憶媒体上に記憶されたコンピュータ実行可能命令を表す。一般に、コンピュータ実行可能命令は、特定の機能を実行する、または特定の抽象データ型を実施する、ルーチン、プログラム、オブジェクト、コンポーネント、およびデータ構造などを含む。オペレーションが説明される順序は、限定として解釈されることは意図されておらず、プロセスを実施するために、任意の数の説明されるオペレーションが、任意の順序で、および／または並列して、組み合わされることができる。
【００６９】
図６は、本明細書において説明されるような、オブジェクト識別および区分化に基づいて自律車両のための軌道を生成するための例示的なプロセス６００を示している。例えば、プロセス６００の一部または全部は、本明細書において説明されるような、アーキテクチャ２００内の、または環境１１００内の１つまたは複数の構成要素によって実行されることができる。
【００７０】
オペレーション６０２において、プロセスは、環境と関連付けられたグランドボクセルを決定することを含むことができる。いくつかの例においては、このオペレーション６０２は、本明細書において論じられるように、局所的にフラットなボクセルを決定することと、グランドクラスタを拡張することと、処理を簡略化するために、グランドクラスタをボクセル空間から除去することとを含むことができる。
【００７１】
オペレーション６０４において、プロセスは、環境と関連付けられたオブジェクトボクセルを決定することを含むことができる。いくつかの例においては、このオペレーション６０４は、本明細書において論じられるように、静的および／または動的オブジェクトを決定することを含むことができる。いくつかの例においては、このオペレーション６０４は、オブジェクトを区分化することと、オブジェクト分類またはタイプを決定するために、区分化されたオブジェクトを、畳み込みニューラルネットワークなどの、クラシファイヤに提供することとを含んでよい。
【００７２】
オペレーション６０６において、プロセスは、グランドおよび／またはオブジェクトに少なくとも部分的に基づいて、自律車両のための軌道を生成することを含むことができる。例えば、オペレーション６０６において生成された軌道は、自律車両によって運転可能な領域に対応してよい、グランドボクセル内に制約されてよい。さらに、オペレーション６０６において生成された軌道は、識別されたオブジェクトを回避してよい。いくつかの例においては、オペレーション６０６は、オペレーション６０４において決定された動的オブジェクトを追跡すること、および／または動的オブジェクトの軌道を予測することを含んでよい。さらに、オペレーション６０６において生成される軌道は、動的オブジェクトの予測される軌道に少なくとも部分的に基づいてよい。例えば、そのような予測される軌道は、オブジェクトを追跡すること、およびオブジェクトの挙動分類などに少なくとも部分的に基づいて、生成されてよい。
【００７３】
オペレーション６０８において、プロセスは、オペレーション６０６において生成された軌道に沿って運転するように自律車両に命令するコマンドのシーケンスを生成することを含むことができる。いくつかの例においては、オペレーション６０８において生成されたコマンドは、軌道を運転するように自律車両を制御するために、自律車両に搭載されたコントローラに中継されることができる。自律車両との関連において論じられたが、プロセス６００、ならびに本明細書において説明される技法およびシステムは、マシンビジョンを利用する様々なシステムに適用されることができる。
【００７４】
図７は、経時的なボクセルデータの表現に基づいて、ボクセルマップをクリアするための例示的なプロセスを示している。例えば、プロセス７００の一部または全部は、本明細書において説明されるような、アーキテクチャ２００内の、または環境１１００内の１つまたは複数の構成要素によって実行されることができる。
【００７５】
オペレーション７０２において、プロセスは、第１の時間に、環境のＬＩＤＡＲデータを捕捉することを含むことができる。本明細書において論じられるように、環境のＬＩＤＡＲデータは、環境内に位置付けられた１つまたは多数のＬＩＤＡＲセンサからのＬＩＤＡＲデータを含んでよい。いくつかの例においては、このオペレーション７０２は、ノイズを除去するために、ＬＩＤＡＲデータをフィルタリングすることを含んでよい。さらに、オペレーション７０２は、本明細書において論じられるように、ＬＩＤＡＲデータをマッピングすること、変換すること、割り当てること、または環境を表すボクセル空間と関連付けることを含んでよい。
【００７６】
オペレーション７０４において、プロセスは、第１のＬＩＤＡＲデータと関連付けられたボクセルの第１のサブセットが、オブジェクトと関連付けられると決定することを含むことができる。上で論じられたように、このオペレーションは、グランドと関連付けられたボクセルを決定することと、潜在的なオブジェクトボクセルを隔離するために、グランドボクセルを区分化すること、除去すること、および／または除外することと、ボクセル空間内に表されたオブジェクトを決定するために、領域拡張技法を利用することとを含んでよい。上で論じられたように、個々のオブジェクトは、一意的なオブジェクト識別子と関連付けられてよく、それは、個々のオブジェクトと関連付けられた個々のボクセルおよび／またはＬＩＤＡＲデータに関連付けられて、および／または割り当てられてよい。
【００７７】
オペレーション７０６において、プロセスは、第２の時間に、環境の第２のＬＩＤＡＲデータを捕捉することを含むことができる。いくつかの例においては、オペレーション７０６は、オペレーション７０２において利用されたのと同じボクセル空間内において、第２の時間に捕捉されたＬＩＤＡＲデータを関連付けることを含んでよい。いくつかの例においては、ＬＩＤＡＲデータは、捕捉の異なる時間と関連付けられたデータを効率的にフィルタリングおよび／またはソートするために、次元として時間を含むことができる。いくつかの例においては、オペレーション７０６は、本明細書において論じられるように、グランドボクセルおよびオブジェクトボクセルを決定することを含むことができる。
【００７８】
オペレーション７０８において、プロセスは、第２のＬＩＤＡＲデータと関連付けられたベクトルが、ボクセルの第１のサブセットを通じてトラバース（traverse）すると決定することを含むことができる。例えば、図５に示されるように、オペレーション７０８は、ＬＩＤＡＲデータ点を捕捉することと関連付けられた、ボクセル空間を通るベクトルをトレースして、ベクトルが通過するボクセルを決定することを含むことができる。いくつかの例においては、オペレーション７０８は、ベクトルと関連付けられたボクセルが、オペレーション７０４において識別されたオブジェクトと関連付けられたボクセルと関連付けられると決定することを含むことができる。
【００７９】
オペレーション７１０において、プロセスは、第２のＬＩＤＡＲデータと関連付けられたボクセルの第１のサブセットが占有されていないと決定することを含むことができる。例えば、このオペレーションは、ボクセルの第１のサブセットを通過するベクトルに基づいて、第２の時間におけるボクセルの第１のサブセットの占有を決定することを含むことができる。
【００８０】
オペレーション７１２において、プロセスは、ボクセルの第１のサブセットを通じてトラバースする、第２のＬＩＤＡＲデータと関連付けられたベクトルに少なくとも部分的に基づいて、第２のＬＩＤＡＲデータを表すデータのボクセル空間をクリアすることを含むことができる。すなわち、オペレーション７１２は、第２の時間に、ボクセルの第１のサブセットを占有されていないボクセルとして表すことを含むことができる。いくつかの例においては、クリアされたボクセルと関連付けられた情報は、オペレーション７０４において決定されたオブジェクトが動的オブジェクトであると決定するために、使用されることができる。
【００８１】
図８は、経時的なボクセルデータの表現に基づいて、オブジェクトが動的オブジェクトであると決定するための例示的なプロセスを示している。例えば、プロセス８００の一部または全部は、本明細書において説明されるような、アーキテクチャ２００内の、または環境１１００内の１つまたは複数の構成要素によって実行されることができる。
【００８２】
オペレーション８０２において、プロセスは、オブジェクトが、第１の時間に、ボクセルの第１のサブセットと関連付けられると決定することを含むことができる。いくつかの例においては、オペレーション８０２は、本明細書において論じられるように、１つまたは複数のオブジェクトを識別することを含むことができる。いくつかの例においては、オペレーション８０２は、オブジェクトを識別するオブジェクト識別子を受信することと、オブジェクト識別子と関連付けられたボクセルを識別することとを含むことができる。同様に、オペレーション８０４において、プロセスは、オブジェクトが、第２の時間に、ボクセルの第２のサブセットと関連付けられると決定することを含むことができる。
【００８３】
オペレーション８０６において、プロセスは、ボクセルの第１のサブセットの少なくとも一部の位置が、ボクセルの第２のサブセットの少なくとも一部の位置と異なると決定することを含むことができる。すなわち、オブジェクトが、空間を通って移動するにつれて、したがって、（例えば）オブジェクトを表すＬＩＤＡＲデータが、時間につれてボクセル空間の全体にわたって更新されるにつれて、オブジェクトと関連付けられたボクセルの占有が、時間につれて変化する。例えば、第１の時間にオブジェクトによって占有されておらず、第２の時間にオブジェクトによって占有されている（またはその反対である）ボクセルは、オブジェクトの動きを表してよい。このオペレーション８０６は、ボクセルの第１のサブセットの位置および／または占有をボクセルの第２のサブセットと比較して、ボクセルのサブセット間で共通しないボクセルを識別することを含むことができる。
【００８４】
オペレーション８０８において、プロセスは、オブジェクトが動的オブジェクトであると決定することを含むことができる。例えば、オブジェクトと関連付けられたボクセルの占有および／または位置を経時的に決定することによって、オペレーション８０８は、ボクセル占有の変化が、例えば、動きに対応し、オブジェクトが動的オブジェクトであると決定することができる。すなわち、いくつかの例においては、ボクセルの第１のサブセットとボクセルの第２のサブセットとの間における、ボクセル空間内のボクセルの位置および／または場所の差は、オブジェクトの運動に対応することができる。いくつかの例においては、データ捕捉または処理におけるジッタ、ノイズ、または誤差が、オブジェクトが動的オブジェクトであるとの識別をトリガすることを防止するために、オペレーション８０８は、差が閾値量を上回ると決定することを含む。いくつかの例においては、オブジェクトは、オペレーション８０６において決定された差に少なくとも部分的に基づいて、動的オブジェクトであると決定される。いくつかの例においては、オペレーション８０８は、オブジェクトが動的オブジェクトであると決定するために、占有情報および／またはレイキャスティングと組み合わせて利用されてよい、例えば、オブジェクトのタイプ（例えば、自動車、ビルディング、樹木）を決定するために、オブジェクトを表すデータをニューラルネットワークに適用することをさらに含んでよい。
【００８５】
オペレーション８１０において、プロセスは、動的オブジェクトの表示をトラッカおよび／またはプランナに提供することを含むことができる。例えば、本明細書において論じられるように、動的オブジェクトと関連付けられたオブジェクト識別子が、後続するオペレーションのために、トラッカおよび／またはプランナに提供されることができる。例えば、オペレーションは、追跡されるオブジェクトのスピード、位置、速度などを決定するために、様々なオブジェクトと関連付けられたボクセルの占有を、経時的に追跡することができる。
【００８６】
図９は、マップ生成および／またはセンサ較正を実行するための例示的なプロセスを示している。例えば、プロセス９００の一部または全部は、本明細書において説明されるような、アーキテクチャ２００内の、または環境１１００内の１つまたは複数の構成要素によって実行されることができる。
【００８７】
オペレーション９０２において、プロセスは、ＬＩＤＡＲデータセットを受信することを含むことができる。いくつかの例においては、オペレーション９０２は、オペレーション１０２、３０２、および／または７０２に類似した、またはそれらと同じオペレーションを含んでよい。
【００８８】
オペレーション９０４において、プロセスは、ＬＩＤＡＲデータセットと関連付けられた静的ボクセルを決定することを含むことができる。いくつかの例においては、オペレーション９０４は、例えば、オペレーション１１２、１２２などにおいて説明されたオペレーションに類似した、またはそれらと同じオペレーションを含んでよい。いくつかの例においては、グランド面は、オペレーション９０４の目的で、静的オブジェクトのタイプと見なされてよい。
【００８９】
オペレーション９０６において、プロセスは、マップ生成および／またはセンサ較正のために、静的ボクセルの表示を提供することを含むことができる。例えば、オペレーション９０６は、環境の特徴を識別するために、経時的にデータを収集することを含むことができる。マップ生成の場合、環境のマップを生成するために、静的オブジェクトと関連付けられた情報が、提供されることができる。センサ較正の場合、オペレーション９０６は、ＧＰＳセンサ、慣性測定ユニット（ＩＭＵ）、ホイールスピードセンサなどの、第１のセンサから位置を決定することを含むことができる。さらに、オペレーションは、全体マップ上における自律車両の位置を決定するために、静的オブジェクトの相対位置を静的オブジェクトの知られた位置と比較することによって、（例えば、ＬＩＤＡＲデータセットを捕捉している）自律車両の第２の位置を決定することを含んでよい。非限定的な例として、ＬＩＤＡＲセンサデータを含む、様々なセンサデータは、いくつか名前を挙げると、ＳＬＡＭ、バンドル調整、ベイジアンフィルタリング、バッグオブワード、またはループ閉鎖アルゴリズムなどの技法を使用して、位置特定を実行するために使用されてよい。第１の位置と第２の位置との間の差に基づいて、オペレーションは、自律車両の場所のより正確な決定を提供するために、センサを較正すること、または場所の位置を調整することを含むことができる。
【００９０】
さらに、本明細書において論じられるオペレーションは、全体マップに関して自律車両を位置特定するために使用されることができる。例えば、ボクセル空間は、以前に捕捉されたセンサデータを表すことができる、全体マップに対応するＬＩＤＡＲデータを用いて、初期化されることができる。自律車両が、ＬＩＤＡＲデータを捕捉しながら、空間を通って運行するとき、オペレーションは、局所的に捕捉された特徴を、全体マップ上に存在する特徴と比較することによって、全体マップ内において自律車両を位置特定することができる。そのようなプロセスは、上で論じられたもの（例えば、ＳＬＡＭ、ベイジアンフィルタリング、およびバンドル調整などの形態）に類似してよい。いくつかの例においては、オペレーションは、局所マップと全体マップとの間の差を決定することができる。非限定的な例として、全体マップが、占有されているボクセルによって決定されるような、局所マップ内に存在しないオブジェクトの存在を示す場合について考える。そのような場合においては、差は、異なる状態（例えば、占有された状態または占有されていない状態）を有する、多数のボクセルを含んでよい。差の量が、第１の閾値を上回るが、第２の閾値を下回る場合、差は、駐車していた自動車が移動した、樹木の除去、ごみ収集日にごみ箱が出されているなど、環境の変化であると見なされてよく、差は、マークされ、全体マップに組み込まれるように、中央サーバにアップロードされることができる。さらに、レイキャスティングオペレーションが、実行されるとき、より詳細なデータが、中央サーバにアップロードされ、全体マップに組み込まれることができる。いくつかの例においては、差の数が、第２の閾値を上回る場合、オペレーションは、位置特定が失敗したと決定することができ、全体マップデータを無視し、局所的に捕捉されたＬＩＤＡＲデータだけを使用してオペレーションしてよい。
【００９１】
図１０は、ボクセル表現に基づいたオブジェクトの識別に基づいて、オブジェクトに注釈を施すための例示的なプロセスを示している。例えば、プロセス１０００の一部または全部は、本明細書において説明されるような、アーキテクチャ２００内の、または環境１１００内の１つまたは複数の構成要素によって実行されることができる。
【００９２】
オペレーション１００２において、プロセスは、ＬＩＤＡＲデータセットを受信することを含むことができる。このオペレーションは、本明細書において論じられるように、ＬＩＤＡＲデータセットをボクセル空間にマッピングすることを含んでよい。
【００９３】
オペレーション１００４において、プロセスは、ＬＩＤＡＲデータセットと関連付けられたグランドボクセルを決定することを含むことができる。このオペレーションは、本明細書において論じられるオペレーションに従って、グランドボクセルを決定することを含んでよい。
【００９４】
オペレーション１００６において、プロセスは、ＬＩＤＡＲデータセットと関連付けられたオブジェクトボクセルを決定することを含むことができる。本明細書において論じられるように、オペレーション１００６は、静的および動的オブジェクトを決定することと、本明細書において論じられるように、オブジェクト識別子を、ボクセル空間内にオブジェクトを表すボクセルと関連付けることとを含んでよい。
【００９５】
オペレーション１００８において、プロセスは、オブジェクトボクセルに対して区分化を実行することを含むことができる。いくつかの例においては、オペレーション１００８は、各個別オブジェクトの境界を画定する３次元境界ボックスを生成することを含んでよい。いくつかの例においては、境界ボックスは、例えば、オブジェクト識別子と関連付けられたボクセルと関連付けられた、ボクセル空間内の空間の体積を決定することによって、生成されることができる。
【００９６】
オペレーション１０１０において、プロセスは、後続する注釈のために、区分化されたオブジェクトボクセルを提供することを含むことができる。いくつかの例においては、オペレーション１０１０は、区分化されたオブジェクトボクセル（および例えば、関連付けられた３次元境界ボックス）を、人手の注釈サービスに提供することを含むことができ、それによって、区分化されたオブジェクトは、再検討のために、グラフィカルユーザインターフェース上に提示される。ユーザは、例えば、区分化情報または境界ボックスの１つまたは複数の態様を調整してよい。いくつかの例においては、区分化されたオブジェクトボクセルは、分類タイプを含むことができ、注釈サービスは、区分化されたボクセルと関連付けられた分類タイプを確認または編集してよい。いくつかの例においては、オペレーション１０１０は、区分化されたオブジェクトボクセルを、自動分類および注釈のために、深層学習ネットワークに提供することを含んでよい。
【００９７】
図１１は、本開示が全体的または部分的に実施されてよい、環境１１００を示している。環境１１００は、記憶装置１１０４と、１つまたは複数のプロセッサ１１０６と、メモリ１１０８と、オペレーティングシステム１１１０とを備える、１つまたは複数のコンピュータシステム１１０２を示している。記憶装置１１０４、プロセッサ１１０６、メモリ１１０８、およびオペレーティングシステム１１１０は、通信インフラストラクチャ１１１２上において、通信可能に結合されてよい。任意選択で、コンピュータシステム１１０２は、入力／出力（Ｉ／Ｏ）デバイス１１１４を介して、ユーザまたは環境と相互作用してよく、通信インフラストラクチャ１１１２を介して、ネットワーク１１１６上の１つまたは複数の他のコンピューティングデバイスとも相互作用してよい。オペレーティングシステム１１１０は、１つまたは複数のアプリケーション１１１８を制御するために、他の構成要素と相互作用してよい。
【００９８】
いくつかの例においては、コンピュータシステム１１０２は、図２のコンピュータシステム２０２に対応してよい。さらに、コンピュータシステム２０２は、本明細書において論じられるような、ボクセルベースの区分化を実行するために、任意のハードウェアおよび／またはソフトウェアを実施して、モジュール２０４、２０６、２０８、２１０、２１２、２１４、２１６、２１８、２２０、２２２、２２４、２２６、２２８、２３２を実施してよい。
【００９９】
本明細書において説明されるシステムおよび方法は、ソフトウェアもしくはハードウェア、またはそれらの任意の組み合わせで、実施されることができる。本明細書において説明されるシステムおよび方法は、物理的または論理的に互いに別々であってよく、または別々でなくてよい、１つまたは複数のコンピューティングデバイスを使用して、実施されることができる。方法は、オンプレミスハードウェア、オンプレミス仮想システム、またはホステッドプライベートインスタンスとして配置された構成要素によって実行されてよい。加えて、本明細書において説明される方法の様々な態様は、他の機能と組み合わされてよく、または他の機能に合併されてよい。
【０１００】
本明細書において説明されるシステムおよび方法を実施するための、例示的な環境およびコンピュータ化されたシステムが、図１１に示されている。プロセッサまたはコンピュータシステムは、特に、本明細書において説明される方法のうちのいくつかまたはすべてを実行するように構成されることができる。いくつかの実施形態においては、方法は、１つまたは複数のコンピュータまたはプロセッサによって、部分的または全体的に自動化されることができる。本明細書において説明されるシステムおよび方法は、ハードウェア、ファームウェア、および／またはソフトウェアのいずれかの組み合わせを使用して実施されてよい。本明細書において説明される本システムおよび方法（またはそれらのいずれかの部分もしくは機能）は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの組み合わせを使用して実施されてよく、１つまたは複数のコンピュータシステムまたは他の処理システムで実施されてよい。いくつかの実施形態においては、示されたシステム要素は、単一のハードウェアデバイスに組み合わされること、または複数のハードウェアデバイスに分割されることができる。多数のハードウェアデバイスが、使用される場合、ハードウェアデバイスは、物理的に互いに近接して、または遠く離れて配置されることができる。説明され、示される方法の実施形態は、説明的であることが意図されており、限定的であることは意図されていない。例えば、方法のステップのうちのいくつかまたはすべては、異なる実施形態においては、組み合わされること、再配置されること、および／または省かれることができる。
【０１０１】
例示的な一実施形態においては、本明細書において説明されるシステムおよび方法は、本明細書において説明される機能性を実施することが可能な１つまたは複数のコンピュータシステムを対象としてよい。例示的なコンピューティングデバイスは、ＯＳ  Ｘ（商標）、ｉＯＳ（商標）、Ｌｉｎｕｘ（商標）、Ａｎｄｒｏｉｄ（商標）、およびＭｉｃｒｏｓｏｆｔ（商標）  Ｗｉｎｄｏｗｓ（商標）などの、しかし、それらに限定されない、任意のオペレーティングシステムを動作させる、パーソナルコンピュータ（ＰＣ）システムであってよいが、それに限定されない。しかしながら、本明細書において説明されるシステムおよび方法は、これらのプラットフォームに限定されなくてよい。代わりに、本明細書において説明されるシステムおよび方法は、任意の適切なオペレーティングシステムを動作させる、任意の適切なコンピュータシステム上において実施されてよい。コンピューティングデバイス、通信デバイス、モバイルフォン、スマートフォン、テレフォニデバイス、電話、パーソナルデジタルアシスタント（ＰＤＡ）、パーソナルコンピュータ（ＰＣ）、ハンドヘルドＰＣ、双方向テレビ（ｉＴＶ）、デジタルビデオレコーダ（ＤＶＤ）、クライアントワークステーション、シンクライアント、シッククライアント、プロキシサーバ、ネットワーク通信サーバ、リモートアクセスデバイス、クライアントコンピュータ、サーバコンピュータ、ルータ、ウェブサーバ、データ、メディア、オーディオ、ビデオ、テレフォニ、またはストリーミング技術サーバなどの、しかし、それらに限定されない、本明細書において説明されるシステムおよび方法の他の構成要素も、コンピューティングデバイスを使用して実施されてよい。サービスは、例えば、限定されることなく、双方向テレビ（ｉＴＶ）、ビデオオンデマンドシステム（ＶＯＤ）を使用して、またデジタルビデオレコーダ（ＤＶＲ）または他のオンデマンド視聴システムを介して、オンデマンドで提供されてよい。
【０１０２】
システムは、１つまたは複数のプロセッサを含んでよい。プロセッサは、通信バス、クロスオーバーバー、またはネットワークなどの、しかし、それらに限定されない、通信インフラストラクチャに接続されてよい。プロセスとプロセッサは、同じ物理的ロケーションに配置される必要はない。言い換えると、プロセスは、例えば、ＬＡＮまたはＷＡＮ接続上において、１つまたは複数の地理的に遠いプロセッサにおいて、実行されることができる。コンピューティングデバイスは、ディスプレイユニット上に表示するために、グラフィックス、テキスト、および他のデータを通信インフラストラクチャから転送してよい、ディスプレイインターフェースを含んでよい。
【０１０３】
コンピュータシステムは、メインメモリ、ランダムアクセスメモリ（ＲＡＭ）、および２次メモリなどを含んでもよいが、それらに限定されない。２次メモリは、例えば、ハードディスクドライブ、および／またはコンパクトディスクドライブＣＤ−ＲＯＭなどのリムーバブル記憶ドライブなどを含んでよい。リムーバブル記憶ドライブは、リムーバブル記憶ユニットから読み取ってよく、および／またはリムーバブル記憶ユニットに書き込んでよい。理解されてよいように、リムーバブル記憶ユニットは、コンピュータソフトウェアおよび／またはデータをそこに記憶した、コンピュータ使用可能記憶媒体を含んでよい。いくつかの実施形態においては、マシンアクセス可能媒体とは、コンピュータによってアクセス可能なデータを記憶するために使用される任意の記憶デバイスのことであってよい。マシンアクセス可能媒体の例は、例えば、限定されることなく、磁気ハードディスク、フロッピディスク、コンパクトディスクリードオンリメモリ（ＣＤ−ＲＯＭ）もしくはデジタル多用途ディスク（ＤＶＤ）などの光ディスク、磁気テープ、および／またはメモリチップなどを含んでよい。
【０１０４】
プロセッサは、データを記憶するための１つもしくは複数のデータ記憶デバイスを含んでもよく、またはそれらと通信するように動作可能に結合されてよい。そのようなデータ記憶デバイスは、非限定的な例として、（内臓ハードディスクおよびリムーバブルディスクを含む）磁気ディスク、光磁気ディスク、光ディスク、リードオンリメモリ、ランダムアクセスメモリ、ならびに／またはフラッシュストレージを含むことができる。コンピュータプログラム命令およびデータを有形に具体化するのに適した記憶デバイスも、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイスなどの、半導体メモリデバイス、内臓ハードディスクおよびリムーバブルディスクなどの、磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭおよびＤＶＤ−ＲＯＭディスクを含む、不揮発性メモリのすべての形態を含むことができる。プロセッサおよびメモリは、ＡＳＩＣ（特定用途向け集積回路）によって補足されること、またはＡＳＩＣ内に組み込まれることができる。
【０１０５】
処理システムは、コンピュータ化されたデータ記憶システムと通信することができる。データ記憶システムは、非リレーショナルデータストア、またはＭｙＳＱＬ（商標）もしくは他のリレーショナルデータベースなどのリレーショナルデータストアを含むことができる。他の物理的および論理的データベースタイプが、使用されることができる。データストアは、Ｍｉｃｒｏｓｏｆｔ  ＳＱＬ  Ｓｅｒｖｅｒ（商標）、Ｏｒａｃｌｅ（商標）、ＩＢＭ  ＤＢ２（商標）、ＳＱＬＩＴＥ（商標）、またはリレーショナルもしくは他の方式の他の任意のデータベースソフトウェアなどの、データベースサーバであってよい。データストアは、構文タグを識別する情報と、構文タグを演算するのに必要とされる任意の情報とを記憶してよい。いくつかの実施形態においては、処理システムは、オブジェクト指向プログラミングを使用してよく、データをオブジェクト内に記憶してよい。これらの実施形態においては、処理システムは、オブジェクトリレーショナルマッパ（ＯＲＭ）を使用して、データオブジェクトをリレーショナルデータベース内に記憶してよい。本明細書において説明されるシステムおよび方法は、任意の数の物理データモデルを使用して、実施されることができる。例示的な一実施形態においては、リレーショナルデータベース管理システム（ＲＤＢＭＳ）が、使用されることができる。それらの実施形態においては、ＲＤＢＭＳにおけるテーブルは、座標を表す列を含むことができる。経済的システムの場合、会社、製品などを表すデータが、ＲＤＢＭＳにおけるテーブル内に記憶されることができる。テーブルは、それらの間の事前定義された関係を有することができる。テーブルは、座標と関連付けられた付加物も有することができる。
【０１０６】
例示的な代替実施形態においては、２次メモリは、コンピュータプログラムまたは他の命令が、コンピュータシステムにロードされることを可能にするための、他の類似のデバイスを含んでよい。そのようなデバイスは、例えば、リムーバブル記憶ユニットおよびインターフェースを含んでよい。そのようなものの例は、（例えば、ビデオゲームデバイスに見出されるものなどの、しかし、それらに限定されない）プログラムカートリッジおよびカートリッジインターフェース、（例えば、消去可能プログラマブルリードオンリメモリ（ＥＰＲＯＭ）、またはプログラマブルリードオンリメモリ（ＰＲＯＭ）および関連付けられたソケットなどの、しかし、それらに限定されない）リムーバブルメモリチップ、ならびにソフトウェアおよびデータがリムーバブル記憶ユニットからコンピュータシステムに転送されることを可能にしてよい、他のリムーバブル記憶ユニットおよびインターフェースを含んでよい。
【０１０７】
コンピューティングデバイスは、マイクロフォンなどの音声入力デバイス、タッチスクリーン、カメラなどのジェスチャ認識デバイス、他の自然なユーザインターフェース、マウス、またはデジタイザなどの他のポインティングデバイス、キーボード、または他のデータ入力デバイスなどの、しかし、それらに限定されない、入力デバイスも含んでよい。コンピューティングデバイスは、ディスプレイ、およびディスプレイインターフェースなどの、しかし、それらに限定されない、出力デバイスも含んでよい。コンピューティングデバイスは、通信インターフェース、ケーブル、および通信経路などの、しかし、それらに限定されない、入力／出力（Ｉ／Ｏ）デバイスを含んでよい。これらのデバイスは、ネットワークインターフェースカード、およびモデムを含むが、それらに限定されない。通信インターフェースは、ソフトウェアおよびデータが、コンピュータシステムと１つまたは複数の外部デバイスとの間で転送されることを可能にしてよい。
【０１０８】
１つまたは複数の実施形態においては、コンピューティングデバイスは、自動車システムに動作可能に結合されてよい。そのような自動車システムは、人手でオペレーションされてよく、半自律的であってよく、または完全に自律的であってよい。そのような実施形態においては、入力および出力デバイスは、加速、制動、およびステアリングなどの、しかし、それらに限定されない、自動車機能を制御するための、１つまたは複数の画像捕捉デバイス、コントローラ、マイクロコントローラ、および／または他のプロセッサを含んでよい。さらに、そのような実施形態における通信インフラストラクチャは、コントローラエリアネットワーク（ＣＡＮ）バスも含んでよい。
【０１０９】
１つまたは複数の実施形態においては、コンピューティングデバイスは、任意のマシンビジョンベースのシステムに動作可能に結合されてよい。例えば、そのようなマシンベースのビジョンシステムは、人手でオペレーションされる、半自律的な、または完全に自律的な産業用または農業用ロボット、家庭用ロボット、検査システム、セキュリティシステムなどを含むが、それらに限定されない。すなわち、本明細書において説明される実施形態は、１つの特定の状況に限定されず、マシンビジョンを利用する任意のアプリケーションに適用可能であってよい。
【０１１０】
１つまたは複数の実施形態においては、本実施形態は、１つまたは複数のコンピュータネットワークの環境において実践されることができる。ネットワークは、プライベートネットワーク、もしくはパブリックネットワーク（例えば、以下で説明されるような、インターネット）、または両方の組み合わせを含むことができる。ネットワークは、ハードウェア、ソフトウェア、または両方の組み合わせを含んでよい。
【０１１１】
遠隔通信指向の観点からは、ネットワークは、通信施設によって相互接続されたハードウェアノードのセットとして説明されることができ、１つまたは複数のプロセス（ハードウェア、ソフトウェア、またはそれらの組み合わせ）が、そのような各ノードにおいて機能する。プロセスは、プロセス間通信経路を使用する、それらの間の通信経路を介して、互いに情報を相互通信し、交換することができる。これらの経路上においては、適切な通信プロトコルが、使用される。
【０１１２】
本実施形態に従った例示的なコンピュータおよび／または遠隔通信ネットワーク環境は、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアの組み合わせを含んでよい、ノードを含んでよい。ノードは、通信ネットワークを介して、相互接続されてよい。各ノードは、ノードに組み込まれたプロセッサによって実行可能な１つまたは複数のプロセスを含んでよい。例えば、単一のプロセスが、多数のプロセッサによって実行されてよく、または多数のプロセスが、単一のプロセッサによって実行されてよい。加えて、ノードの各々は、ネットワークと外部世界との間のインターフェースポイントを提供してよく、サブネットワークの集まりを含んでよい。
【０１１３】
例示的な実施形態においては、プロセスは、任意の通信プロトコルを通して通信をサポートするプロセス間通信経路を通して、互いに通信してよい。経路は、順次的または並列的に、連続的または断続的に機能してよい。経路は、多くのコンピュータによって使用される標準的な並列命令セットに加えて、通信ネットワークに関して本明細書において説明される、通信規格、プロトコル、または技術のいずれかを使用することができる。
【０１１４】
ノードは、処理機能を実行することが可能な任意のエンティティを含んでよい。実施形態とともに使用されることができるそのようなノードの例は、（パーソナルコンピュータ、ワークステーション、サーバ、もしくはメインフレームなどの）コンピュータ、（パーソナルデジタルアシスタント（ＰＤＡ）、処理能力を有するモデムセルフォン、ＢｌａｃｋＢｅｒｒｙ（商標）デバイスを含む無線電子メールデバイスなどの）ハンドヘルド無線デバイスおよび有線デバイス、（スキャナ、プリンタ、ファクシミリマシン、もしくは多機能文書マシンなどの）文書処理デバイス、または説明されたように、プロセッサの集まりがそれに接続される（ローカルエリアネットワークもしくはワイドエリアネットワークなどの）複合エンティティを含む。例えば、本開示との関連において、ノード自体が、ワイドエリアネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、（仮想プライベートネットワーク（ＶＰＮ）などの）プライベートネットワーク、またはネットワークの集まりであることができる。
【０１１５】
ノード間の通信は、通信ネットワークによって可能にされてよい。ノードは、通信ネットワークを用いて、連続的または断続的に接続されてよい。例として、本開示との関連において、通信ネットワークは、適切な帯域幅および情報セキュリティを提供する、デジタル通信インフラストラクチャであることができる。
【０１１６】
通信ネットワークは、任意のタイプの規格、プロトコル、または技術を使用する、任意の周波数における、有線通信能力、無線通信能力、または両方の組み合わせを含むことができる。加えて、本実施形態においては、通信ネットワークは、プライベートネットワーク（例えば、ＶＰＮ）、またはパブリックネットワーク（例えば、インターネット）であることができる。
【０１１７】
通信ネットワークによって使用される例示的な無線プロトコルおよび技術の非包括的リストは、Ｂｌｕｅｔｏｏｔｈ（商標）、汎用パケット無線サービス（ＧＰＲＳ）、セルラデジタルパケットデータ（ＣＤＰＤ）、モバイルソリューションプラットフォーム（ＭＳＰ）、マルチメディアメッセージング（ＭＭＳ）、無線アプリケーションプロトコル（ＷＡＰ）、符号分割多元接続（ＣＤＭＡ）、ショートメッセージサービス（ＳＭＳ）、無線マークアップ言語（ＷＭＬ）、ハンドヘルドデバイスマークアップ言語（ＨＤＭＬ）、無線用バイナリランタイム環境（ＢＲＥＷ）、無線アクセスネットワーク（ＲＡＮ）、およびパケット交換コアネットワーク（ＰＳ−ＣＮ）を含んでよい。また、様々な世代の無線技術が含まれる。通信ネットワークによって使用される主に無線プロトコルおよび技術の例示的な非包括的リストは、非同期転送モード（ＡＴＭ）、高度化された内部ゲートウェイルーティングプロトコル（ＥＩＧＲＰ：ｅｎｈａｎｃｅｄ  ｉｎｔｅｒｉｏｒ  ｇａｔｅｗａｙ  ｒｏｕｔｉｎｇ  ｐｒｏｔｏｃｏｌ）、フレームリレー（ＦＲ）、高レベルデータリンク制御（ＨＤＬＣ）、インターネット制御メッセージプロトコル（ＩＣＭＰ）、内部ゲートウェイルーティングプロトコル（ＩＧＲＰ）、ネットワーク間パケット交換（ＩＰＸ）、ＩＳＤＮ、ポイントツーポイントプロトコル（ＰＰＰ）、伝送制御プロトコル／インターネットプロトコル（ＴＣＰ／ＩＰ）、ルーティング情報プロトコル（ＲＩＰ）、およびユーザデータグラムプロトコル（ＵＤＰ）を含む。当業者が認識するように、他の任意の知られた、または予想される無線または有線プロトコルおよび技術が、使用されることができる。
【０１１８】
本開示の実施形態は、本明細書におけるオペレーションを実行するための装置を含んでよい。装置は、所望の目的のために特別に構築されてよく、またはそれは、デバイス内に記憶されたプログラムによって選択的に活性化または再構成される、汎用デバイスを備えてよい。
【０１１９】
１つまたは複数の実施形態においては、本実施形態は、マシン実行可能命令で具体化される。命令は、命令を用いてプログラムされる処理デバイス、例えば、汎用または専用プロセッサに、本開示のステップを実行させるために、使用されることができる。あるいは、本開示のステップは、ステップを実行するための配線論理を含む特定のハードウェア構成要素によって、またはプログラムされたコンピュータ構成要素とカスタムハードウェア構成要素の任意の組み合わせによって、実行されることができる。例えば、本開示は、上で概要説明されたような、コンピュータプログラム製品として、提供されることができる。この実施形態においては、実施形態は、命令がその上に記憶されたマシン可読媒体を含むことができる。命令は、例示的な本実施形態に従って、プロセスまたは方法を実行するように、１つまたは複数の任意のプロセッサ（または他の電子デバイス）をプログラムするために、使用されることができる。加えて、本開示は、ダウンロードされ、コンピュータプログラム製品上に記憶されることもできる。ここでは、プログラムは、通信リンク（例えば、モデムまたはネットワーク接続）を介して、搬送波または他の伝搬媒体内に具体化されたデータ信号を用いて、リモートコンピュータ（例えば、サーバ）から要求コンピュータ（例えば、クライアント）に転送されることができ、最終的に、そのような信号は、後続する実行のために、コンピュータシステム上に記憶されてよい。
【０１２０】
方法は、コンピュータまたは任意の命令実行システムによる使用のために、またはそれらとの関連において、プログラムコードを提供する、コンピュータ使用可能または可読記憶媒体から取得可能な、コンピュータプログラム製品において実施されることができる。コンピュータ使用可能または可読記憶媒体は、コンピュータ、もしくは命令実行システム、装置、もしくはデバイスによる使用のために、またはそれらとの関連において、プログラムを含むこと、または記憶することができる、任意の装置であることができる。
【０１２１】
対応するプログラムコードを記憶および／または実行するのに適したデータ処理システムは、メモリ要素などのコンピュータ化されたデータ記憶デバイスに直接的または間接的に結合された、少なくとも１つのプロセッサを含むことができる。（キーボード、ディスプレイ、ポインティングデバイスなどを含むが、それらに限定されない）入力／出力（Ｉ／Ｏ）デバイスが、システムに結合されることができる。データ処理システムが、介在するプライベートまたはパブリックネットワークを通して、他のデータ処理システム、またはリモートプリンタもしくは記憶デバイスに結合されることを可能にするために、ネットワークアダプタも、システムに結合されてよい。ユーザとの相互作用を提供するために、ＬＣＤ（液晶ディスプレイ）などの表示デバイス、または情報をユーザに表示するための別のタイプのモニタ、ならびにユーザがそれによって入力をコンピュータに提供することができる、キーボード、およびマウスまたはトラックボールなどの入力デバイスを備えるコンピュータ上において、特徴が実施されることができる。
【０１２２】
コンピュータプログラムは、コンピュータにおいて直接的または間接的に使用されることができる、命令のセットであることができる。本明細書において説明されるシステムおよび方法は、コンパイル言語またはインタープリタ言語を含む、ＣＵＤＡ、ＯｐｅｎＣＬ、Ｆｌａｓｈ（商標）、ＪＡＶＡ（商標）、Ｃ＋＋、Ｃ、Ｃ＃、Ｐｙｔｈｏｎ、Ｖｉｓｕａｌ  Ｂａｓｉｃ（商標）、ＪａｖａＳｃｒｉｐｔ（商標）、ＰＨＰ、ＸＭＬ、ＨＴＭＬなどのプログラミング言語、またはプログラミング言語の組み合わせを使用して、実施されることができ、スタンドアロンプログラムとして、またはコンピューティング環境における使用に適したモジュール、コンポーネント、サブルーチン、もしくは他のユニットとしてを含む、任意の形態で展開されることができる。ソフトウェアは、ファームウェア、常駐ソフトウェア、マイクロコードなどを含むことができるが、それらに限定されない。プログラミングモジュール間のインターフェースを実施する際に、ＳＯＡＰ／ＨＴＴＰなどのプロトコルが、使用されてよい。本明細書において説明される構成要素および機能性は、仮想化または非仮想化環境において動作する、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（商標）、Ａｐｐｌｅ（商標）  Ｍａｃ（商標）、ｉＯＳ（商標）、Ｕｎｉｘ（商標）／Ｘ−Ｗｉｎｄｏｗｓ（商標）、Ｌｉｎｕｘ（商標）の異なるバージョンを含むが、それらに限定されない、任意のデスクトップオペレーティングシステム上において、ソフトウェア開発に適した任意のプログラミング言語を使用して、実施されてよい。システムは、ルビーオンレイルズ（Ｒｕｂｙ  ｏｎ  Ｒａｉｌｓ）などの、ウェブアプリケーションフレームワークを使用して、実施されることができる。
【０１２３】
命令からなるプログラムの実行に適したプロセッサは、任意の種類のコンピュータの、汎用および専用マイクロプロセッサ、ならびに単独のプロセッサ、または多数のプロセッサもしくはコアのうちの１つを含むが、それらに限定されない。プロセッサは、リードオンリメモリ、ランダムアクセスメモリ、両方、または本明細書において説明されるデータ記憶デバイスの任意の組み合わせなどの、コンピュータ化されたデータ記憶デバイスから、命令およびデータを受信し、記憶してよい。プロセッサは、電子デバイスの動作および実行を制御するように動作する、任意の処理回路または制御回路を含んでよい。
【０１２４】
本明細書において説明されるシステム、モジュール、および方法は、ソフトウェア要素またはハードウェア要素の任意の組み合わせを使用して、実施されることができる。本明細書において説明されるシステム、モジュール、および方法は、単独で、または互いに組み合わさって動作する、１つまたは複数の仮想マシンを使用して、実施されることができる。物理的コンピューティングマシンプラットフォームを、ハードウェアコンピューティングプラットフォームまたはホスト上において動作する仮想化ソフトウェアの制御下で実行される、仮想マシンにカプセル化するために、任意の適用可能な仮想化ソリューションが、使用されることができる。仮想マシンは、仮想システムハードウェアとゲストオペレーティングシステムソフトウェアの両方を有することができる。
【０１２５】
本明細書において説明されるシステムおよび方法は、データサーバなどのバックエンドコンポーネントを含む、またはアプリケーションサーバもしくはインターネットサーバなどのミドルウェアコンポーネントを含む、またはグラフィカルユーザインターフェースもしくはインターネットブラウザを有するクライアントコンピュータなどのフロントエンドコンポーネントを含む、またはそれらの任意の組み合わせを含む、コンピュータシステムにおいて実施されることができる。システムの構成要素は、通信ネットワークなど、デジタルデータ通信の任意の形態または媒体によって接続されることができる。通信ネットワークの例は、例えば、ＬＡＮ、ＷＡＮ、ならびにインターネットを形成するコンピュータおよびネットワークを含む。
【０１２６】
本開示の１つまたは複数の実施形態は、ハンドヘルドデバイス、マイクロプロセッサシステム、マイクロプロセッサベースまたはプログラマブル家電製品、ミニコンピュータ、メインフレームコンピュータなどを含む、他のコンピュータシステム構成を用いて実践されてよい。本明細書において説明されるシステムおよび方法は、ネットワークを通してリンクされたリモート処理デバイスによってタスクが実行される、分散コンピューティング環境において実践されてもよい。
【０１２７】
「コンピュータプログラム媒体」および「コンピュータ可読媒体」という用語は、リムーバブル記憶ドライブ、ハードディスクドライブ内に設置されたハードディスクなどの、しかし、それらに限定されない、媒体を一般に指すために、使用されてよい。これらのコンピュータプログラム製品は、ソフトウェアをコンピュータシステムに提供してよい。本明細書において説明されるシステムおよび方法は、そのようなコンピュータプログラム製品を対象としてよい。
【０１２８】
「一実施形態」、「実施形態」、「例示的な実施形態」、「様々な実施形態」などに対する言及は、本開示の実施形態が、特定の特徴、構造、または特性を含んでよいが、あらゆる実施形態が、特定の特徴、構造、または特性を必ずしも含むわけではないことを示してよい。さらに、「一実施形態においては」または「例示的な実施形態においては」という句の繰り返される使用は、同じ実施形態を必ずしも指しているわけではないが、同じ実施形態を指してもよい。同様に、「例」に対する言及は、本開示の様々な例が、特定の特徴、構造、または特性を含んでよいが、あらゆる例が、特定の特徴、構造、または特性を必ずしも含むわけではないことを示してよい。さらに、「いくつかの例においては」という句の繰り返される使用は、同じ例を必ずしも指しているわけではないが、同じ例を指してもよい。
【０１２９】
説明および特許請求の範囲において、「結合される」および「接続される」という用語が、それらの派生形とともに、使用されてよい。これらの用語は、互いに同義語として意図されていなくてよいことが、理解されるべきである。むしろ、特定の実施形態においては、「接続される」は、２つ以上の要素が、互いに物理的または電気的に直接接触していることを示すために、使用されてよい。「結合される」は、２つ以上の要素が、物理的または電気的に直接接触していることを意味してよい。しかしながら、「結合される」は、２つ以上の要素が、互いに直接接触しておらず、それでもなお、互いに協力し、または相互作用することを意味してもよい。
【０１３０】
ここでは、また一般に、アルゴリズムは、所望の結果にいたる、行為またはオペレーションの自己矛盾のないシーケンスであると見なされてよい。これらは、物理量の物理的オペレーションを含む。必ずではないが、通常、これらの量は、記憶され、転送され、組み合わされ、比較され、他の方法でオペレーションされることが可能な、電気または磁気信号の形態を取る。主として、共通使用の理由で、これらの信号を、ビット、値、要素、シンボル、文字、項、または数などと呼ぶことが、時には便利であることが分かっている。しかしながら、これらおよび類似の用語のすべては、適切な物理量と関連付けられるべきであり、これらの量に適用される便利なラベルにすぎないことが、理解されるべきである。
【０１３１】
特に別段の指摘がない限り、本明細書全体において、「処理する」、「計算する」、「算定する」、または「決定する」などの用語は、コンピューティングシステムのレジスタおよび／またはメモリ内の電子的などの物理量として表されるデータをオペレーションおよび／または変換して、コンピュータシステムのメモリ、レジスタ、または他のそのような情報記憶、伝送、もしくは表示デバイス内の物理量として同様に表される他のデータにする、コンピュータもしくはコンピューティングシステム、または類似の電子コンピューティングデバイスの、アクションおよび／またはプロセスを指すことが、理解されてよい。
【０１３２】
同様の方式で、「プロセッサ」という用語は、レジスタおよび／またはメモリからの電子データを処理して、その電子データを、レジスタおよび／またはメモリ内に記憶されてよい他の電子データに変換する、任意のデバイス、またはデバイスの一部を指してよい。非限定的な例として、「プロセッサ」は、中央処理ユニット（ＣＰＵ）、またはグラフィカル処理ユニット（ＧＰＵ）であってよい。「コンピューティングプラットフォーム」は、１つまたは複数のプロセッサを備えてよい。本明細書において使用されるとき、「ソフトウェア」プロセスは、例えば、タスク、スレッド、およびインテリジェントエージェントなどの、経時的に仕事を実行するソフトウェアエンティティおよび／またはハードウェアエンティティを含んでよい。また、各プロセスは、命令を順次的または並列的、連続的または断続的に実施するための、多数のプロセスを指してよい。「システム」および「方法」という用語は、システムが１つまたは複数の方法を具体化してよく、方法がシステムと見なされてよい限り、本明細書においては、交換可能に使用される。
【０１３３】
１つまたは複数の実施形態が、説明されたが、それらの様々な改変、追加、置換、および均等物が、本開示の範囲内に含まれる。
【０１３４】
実施形態の説明において、それの一部を形成する添付の図面に対する参照が行われ、それは、特許請求される発明の特定の実施形態を実例として示している。他の実施形態が使用されてよく、構造的変更などの変更または改変が行われてよいことが、理解されるべきである。そのような実施形態、変更または改変は、意図された特許請求される発明に関する範囲からの逸脱であるとは限らない。ステップは、本明細書においては、ある順序で提示されてよいが、いくつかのケースにおいては、順序付けは、ある入力が、説明されるシステムおよび方法の機能を変更することなく、異なる時間に、または異なる順序で、提供されるように、変更されてよい。開示される手順も、異なる順序で実行されることができる。加えて、本明細書における様々な計算は、開示された順序で実行される必要はなく、計算の代替的な順序付けを使用する他の実施形態が、容易に実施されることができる。並べ替えられるのに加えて、計算は、同じ結果を有するサブ計算に分解されることもできる。
【０１３５】
上の議論は、説明される技法の例示的な実施について説明するが、他のアーキテクチャが、説明される機能性を実施するために使用されてよく、それは、本開示の範囲内にあることが意図されている。さらに、議論の目的で、上では、責務の特定の分配が定義されたが、様々な機能および責務は、状況に応じて、異なる方法で、分配され、分割されてよい。
【０１３６】
さらに、本発明は、構造的特徴および／または方法論的動作に特有の言葉で説明されたが、添付の特許請求の範囲において定義される本発明は、説明された特定の特徴または動作に必ずしも限定されないことが、理解されるべきである。むしろ、特定の特徴または動作は、特許請求の範囲を実施する例示的な形態として開示されている。
【０１３７】
実施例の条項
Ａ．１つ以上のプロセッサおよび前記１つ以上のプロセッサに通信可能に結合され、命令を記憶した１つ以上のコンピュータ可読記憶媒体を備え、前記命令は、環境を表すＬＩＤＡＲデータセットを受信し、前記ＬＩＤＡＲデータセットをボクセル空間と関連付け、前記ボクセル空間は、複数のボクセルを含み、前記複数のボクセルの個々のボクセルと関連付けられた三次元データと関連付けられた面法線ベクトルを決定し、基準方向を決定し、前記基準方向は、自律車両の方位に対応し、前記面法線ベクトルおよび前記基準方向に少なくとも部分的に基づいて、前記個々のボクセルが局所的にフラットであると決定し、グランドクラスタを決定し、前記グランドクラスタは、前記自律車両についての運転可能な面を表し、前記グランドクラスタは、複数の局所的にフラットなボクセルを含み、前記複数の局所的にフラットなボクセルは、前記局所的にフラットなボクセルを含み、前記ボクセル空間から前記グランドクラスタを除去して前記ボクセル空間のサブセット決定し、前記ボクセル空間の前記サブセット内の隣接するボクセルをクラスタ化して少なくとも１つのオブジェクトを決定し、前記少なくとも１つのオブジェクトに少なくとも部分的に基づいて、前記自律車両についての軌道を生成する、ように前記プロセッサによって実行可能である、システム。
【０１３８】
Ｂ．前記命令は、前記面法線ベクトルと前記基準方向との間で形成された角度が閾値を下回ると決定し、前記角度が前記閾値を下回ることに少なくとも部分的に基づいて、前記個々のボクセルが前記局所的にフラットなボクセルであると決定する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ａに記載のシステム。
【０１３９】
Ｃ．前記グランドクラスタは、所的にフラットなボクセルの第１のクラスタであり、前記命令は、前記第１のクラスタにおいて表されるＬＩＤＡＲデータの平均高さを第１の高さとして決定し、局所的にフラットなボクセルの前記第１のクラスタ内の第１のボクセルを、第１の選択されたボクセルとして選択し、局所的にフラットなボクセルの第２のクラスタ内の第２のボクセルを、第２の選択されたボクセルとして選択し、前記第２の選択されたボクセルにおいて表されるデータの平均高さを第２の高さとして決定し、前記第１の選択されたボクセルと関連付けられた第１の代表点と前記第２の選択されたボクセルと関連付けられた第２の代表点との間の距離を決定し、前記第１の高さと前記第２の高さとの間の高さの差を決定し、前記距離および前記高さの差に少なくとも部分的に基づいて、勾配を決定し、前記勾配が閾値を下回ることに少なくとも部分的に基づいて、局所的にフラットなボクセルの前記第１のクラスタおよび局所的にフラットなボクセルの前記第２のクラスタの少なくとも一部を含む更新されたグランドクラスタを決定する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落ＡまたはＢに記載のシステム。
【０１４０】
Ｄ．前記ＬＩＤＡＲデータセットは、第１の時間における前記環境を表す第１のＬＩＤＡＲデータセットであり、前記命令は、第２の時間における前記環境を表す第２のＬＩＤＡＲデータセットを受信し、前記第２のＬＩＤＡＲデータセットを前記ボクセル空間と関連付け、前記第１のＬＩＤＡＲデータセットの少なくとも一部がオブジェクトを表すと決定し、前記第２のＬＩＤＡＲデータセットの少なくとも一部が前記オブジェクトを表すと決定し、差として、前記オブジェクトと関連付けられた前記第２のＬＩＤＡＲデータセットの少なくとも一部が、前記第１の時間における前記第１のオブジェクトによって前に占有されていなかった前記第２の時間における１つ以上のボクセルにマップすると決定し、前記差に少なくとも部分的に基づいて、前記第１のオブジェクトが動的オブジェクトであると決定する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ａ乃至Ｃのいずれかの１つに記載のシステム。
【０１４１】
Ｅ．前記ＬＩＤＡＲデータセットは、第１の時間に受信された第１のＬＩＤＡＲデータセットであり、前記命令は、前記少なくとも１つのオブジェクトが前記第１の時間に前記ボクセル空間のボクセルの第１のサブセットを占有していると決定し、第２の時間に第２のＬＩＤＡＲデータセットを受信し、前記第２のＬＩＤＡＲデータセットの少なくとも１つのＬＩＤＡＲデータ点と関連付けられたベクトルが、前記第２の時間にボクセルの前記第１のサブセットの少なくとも一部を通じてトラバースすると決定し、ボクセルの前記第１のサブセットの前記少なくとも一部が前記第２の時間に占有されていないと決定し、ボクセルの前記第１のサブセットの前記少なくとも一部が前記第２の時間に占有されていないことに少なくとも部分的に基づいて、前記少なくとも１つのオブジェクトが動的オブジェクトであると決定する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ａ乃至Ｄのいずれかの１つに記載のシステム。
【０１４２】
Ｆ．前記命令は、オブジェクト識別子を前記少なくとも１つのオブジェクトを表すボクセルと関連付ける、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ａ乃至Ｅのいずれかの１つに記載のシステム。
【０１４３】
Ｇ．前記命令は、個々のボクセルと関連付けられた前記面法線ベクトルを決定するように、前記個々のボクセルと関連付けられた前記三次元データに少なくとも部分的に基づいて、共分散行列に対して固有値分解を実行する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ａ乃至Ｆのいずれかの１つに記載のシステム。
【０１４４】
Ｈ．前記グランドクラスタは、前記グランドクラスタを拡張するためのシード点として、前記自律車両に近接した少なくとも１つのボクセルを含む、段落Ａ乃至Ｇのいずれかの１つに記載のシステム。
【０１４５】
Ｉ．環境と関連付けられたＬＩＤＡＲデータセットを表すボクセル空間を受信するステップと、前記ボクセル空間のボクセルに対し、前記ボクセルによって表される三次元データと関連付けられた面法線ベクトルを決定するステップと、前記ボクセルと関連付けられた前記面法線ベクトルに少なくとも部分的に基づいて、前記ボクセルが局所的にフラットなボクセルであると決定するステップと、グランドクラスタを決定するステップであって、前記グランドクラスタは、複数の局所的にフラットなボクセルを含み、前記複数の局所的にフラットなボクセルは、前記局所的にフラットなボクセルを含む、ステップと、自律車両についての運転可能な面を表す前記グランドクラスタに少なくとも部分的に基づいて、前記自律車両についての軌道を生成するステップと、を備えた方法。
【０１４６】
Ｊ．前記自律車両の方位に少なくとも部分的に基づいて、基準方位を決定するステップと、前記面法線ベクトルと前記基準方位と関連付けられたベクトルとの間の角度が閾値以内であると決定するステップと、前記角度が前記閾値を下回ることに少なくとも部分的に基づいて、前記ボクセルが前記局所的にフラットなボクセルであると決定するステップと、をさらに備えた段落Ｉに記載の方法。
【０１４７】
Ｋ．前記局所的にフラットなボクセルは、第１の局所的にフラットなボクセルであり、前記グランドクラスタを決定するステップは、シードボクセルとして、前記第１の局所的にフラットなボクセルを選択するステップであって、前記シードボクセルは、前記自律車両に近接している、ステップと、第２の局所的にフラットなボクセルが前記シードボクセルに隣接していると決定するステップと、前記シードボクセルおよび前記第２の局所的にフラットなボクセルを前記グランドクラスタと関連付けるステップと、をさらに備えた段落ＩまたはＪに記載の方法。
【０１４８】
Ｌ．前記ボクセル空間のサブセットを識別するように、前記グランドクラスタと関連付けられたボクセルを前記ボクセル空間から抽出するステップと、第１のオブジェクトを決定するようにボクセルの第１のグループをクラスタ化するステップであって、ボクセルの前記第１のグループの個々の第１のボクセルは、ボクセルの前記第１のグループの少なくとも１つの他の第１のボクセルに隣接している、ステップと、第２のオブジェクトを決定するようにボクセルの第２のグループをクラスタ化するステップであって、ボクセルの前記第２のグループの個々の第２のボクセルは、ボクセルの前記第２のグループの少なくとも１つの他の第２のボクセルに隣接し、前記個々の第１のボクセルは、前記個々の第２のボクセルに隣接していない、ステップと、をさらに備えた段落Ｉ乃至Ｋのいずれかの１つに記載の方法。
【０１４９】
Ｍ．第１の局所的にフラットなボクセルの第１のクラスタを決定するステップと、第２の局所的にフラットなボクセルの第２のクラスタを決定するステップと、局所的にフラットなボクセルの前記第１のクラスタと局所的にフラットなボクセルの前記第２のクラスタとの間の高さ勾配を決定するステップと、前記高さ勾配が勾配閾値を下回ると決定するステップと、前記グランドクラスタを表すように、前記高さ勾配が前記勾配閾値を下回ることに少なくとも部分的に基づいて、前記第１のクラスタを前記第２のクラスタと結合するステップと、をさらに備えた段落Ｉ乃至Ｌのいずれかの１つに記載の方法。
【０１５０】
Ｎ．前記ボクセル空間において表される少なくとも１つの動的オブジェクトを決定するように、経時的にボクセルの占有を決定するステップと、前記ボクセル空間において表される前記少なくとも１つの動的オブジェクトに少なくとも部分的に基づいて、前記軌道を生成するステップと、をさらに備えた段落Ｉ乃至Ｍのいずれかの１つに記載の方法。
【０１５１】
Ｏ．１つ以上のプロセッサおよび前記１つ以上のプロセッサに通信可能に結合され、命令を記憶した１つ以上のコンピュータ可読記憶媒体を備え、前記命令は、少なくとも１つのＬＩＤＡＲセンサを使用して、環境を表すＬＩＤＡＲデータセットを捕捉し、前記ＬＩＤＡＲデータセットをボクセル空間と関連付け、前記ボクセル空間は、複数のボクセルを含み、前記ボクセル空間のボクセルに対し、前記ボクセルによって表される三次元データと関連付けられた面法線ベクトルを決定し、前記ボクセルと関連付けられた前記面法線ベクトルに少なくとも部分的に基づいて、前記ボクセルが局所的にフラットなボクセルであると決定し、グランドクラスタを決定し、前記グランドクラスタは、複数の局所的にフラットなボクセルを含み、前記複数の局所的にフラットなボクセルは、前記局所的にフラットなボクセルを含む、ように前記プロセッサによって実行可能である、システム。
【０１５２】
Ｐ．前記命令は、基準方位を決定し、前記面法線ベクトルと前記基準方位と関連付けられたベクトルとの間で形成された角度が閾値を下回ると決定し、前記角度が前記閾値を下回ることに少なくとも部分的に基づいて、前記ボクセルが前記局所的にフラットなボクセルであると決定する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ｏに記載のシステム。
【０１５３】
Ｑ．前記命令は、前記ボクセル空間のサブセットを識別するように、前記グランドクラスタと関連付けられたボクセルを前記ボクセル空間から抽出し、ボクセルのクラスタを決定するようにボクセルのグループをクラスタ化し、ボクセルの前記グループの個々のボクセルは、ボクセルの前記グループの少なくとも１つの他のボクセルに隣接し、ボクセルの前記クラスタと関連付けられたボクセルの数がボクセルの閾値数を下回ると決定し、ボクセルの前記クラスタがオブジェクトでないと決定する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落ＯまたはＰに記載のシステム。
【０１５４】
Ｒ．前記命令は、第１の局所的にフラットなボクセルの第１のクラスタを決定し、第２の局所的にフラットなボクセルの第２のクラスタを決定し、局所的にフラットなボクセルの前記第１のクラスタと局所的にフラットなボクセルの前記第２のクラスタとの間の高さ勾配を決定し、前記高さ勾配が勾配閾値を下回ると決定し、前記グランドクラスタを表すように、前記高さ勾配が前記勾配閾値を下回ることに少なくとも部分的に基づいて、前記第１のクラスタを前記第２のクラスタと結合する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ｏ乃至Ｑのいずれかの１つに記載のシステム。
【０１５５】
Ｓ．前記命令は、前記ボクセル空間において表される少なくとも１つの動的オブジェクトを決定するように、経時的にボクセルの占有を決定し、前記ボクセル空間において表される前記少なくとも１つの動的オブジェクトに少なくとも部分的に基づいて、前記軌道を生成する、ように前記１つ以上のプロセッサによってさらに実行可能である、段落Ｏ乃至Ｒのいずれかの１つに記載のシステム。
【０１５６】
Ｔ．前記命令は、前記自律車両についての運転可能な面を表す前記グランドクラスタに少なくとも部分的に基づいて、自律車両についての軌道を生成し、前記軌道に少なくとも部分的に基づいて、前記自律車両を制御するように前記１つ以上のプロセッサによってさらに実行可能である、段落Ｏ乃至Ｓのいずれかの１つに記載のシステム。
【０１５７】
上記説明された実施例の条項が１つの特定の実装態様に関して説明されてきたが、本明細書のコンテキストでは、実施例の条項の内容は、方法、デバイス、システム、コンピュータ可読媒体、および／または別の実装態様を介して実装されることもできることを理解されるべきである。
【図１】
2020524330.tif 000003
【図２】
2020524330.tif 000004
【図３】
2020524330.tif 000005
【図４】
2020524330.tif 000006
【図５】
2020524330.tif 000007
【図６】
2020524330.tif 000008
【図７】
2020524330.tif 000009
【図８】
2020524330.tif 000010
【図９】
2020524330.tif 000011
【図１０】
2020524330.tif 000012
【図１１】
2020524330.tif 000013
【国際調査報告】
2020524330.tif 000014
2020524330.tif 000015
2020524330.tif 000016