方向付き3DボックスのIntersection over Union：新しいアルゴリズム

著者：Georgia Gkioxari

実装：Georgia Gkioxari と Nikhila Ravi

説明

ボックスのIntersection over Union（IoU）は、物体検出における評価指標として広く用いられています（1、2）。2Dでは、IoUは一般的に軸に平行なボックス（画像軸に平行な辺を持つボックス）に適用されます。3Dでは、ボックスは通常軸に平行ではなく、空間内で任意の方向を向いている可能性があります。私たちは、2つの方向付き3Dボックスの正確なIoUを計算する新しいアルゴリズムを紹介します。

私たちのアルゴリズムは、2つの方向付き3Dボックスbox1とbox2の交差が、連結された平面単位からなる凸多面体（2Dでは凸n角形）であり、n > 2であるという単純な観察に基づいています。3Dでは、これらの平面単位は3D三角面です。2Dでは、それらは2D辺です。各平面単位は、box1またはbox2のどちらかに厳密に属します。私たちのアルゴリズムは、各ボックスの辺を反復処理することでこれらの単位を見つけます。

box1内の各3D三角面eについて、eがbox2の内部にあるかどうかを確認します。
eが内部にない場合、破棄します。
eが内部にあるか部分的に内部にある場合、box2の内部にあるeの部分が、最終的な交差形状を構成する単位に追加されます。
box2についても同様の処理を繰り返します。

以下に、2D方向付きボックスの場合のアルゴリズムの可視化を示します。

drawing

ボックスの単位eがboxの内部に部分的にある場合、eはより小さな単位に分割されることに注意してください。2Dでは、eは辺であり、より小さな辺に分割されます。3Dでは、eは3D三角面であり、交差するboxの平面によってさらに小さく多くの面にクリッピングされます。これが、2Dと3Dのアルゴリズムの唯一の基本的な違いです。

他のアルゴリズムとの比較

3DボックスIoUの現在のアルゴリズムは、粗い近似に依存するか、ボックスの仮定を行う（たとえば、3Dボックスの方向を制限する）などです。Objectronは、以前の研究の限界について優れた議論を提供しています。Objectronは、方向付き3Dボックスの正確なIoU計算のための優れたアルゴリズムを紹介しています。Objectronのアルゴリズムは、サザランド・ホジマンアルゴリズムを使用して2つのボックスの交点座標を計算します。交差形状は、Qhullライブラリを使用して、交点座標からなる凸包によって形成されます。

私たちのアルゴリズムは、Objectronのアルゴリズムよりもいくつかの利点があります。

私たちのアルゴリズムもObjectronと同様に交点座標を計算しますが、さらに、座標が属する平面単位を保存します。これにより、O(nlogn)であり、しばしば説明のないエラーメッセージでクラッシュするサードパーティライブラリに依存する凸包計算が不要になります。
Objectronの実装では、ボックスが軸に平行なボックスから回転したものだと仮定しています。私たちのアルゴリズムと実装では、そのような仮定はしておらず、あらゆる3Dボックスで機能します。
私たちのアルゴリズムはバッチ処理をサポートしていますが、Objectronはbox1とbox2に対して単一要素の入力を想定しています。
私たちのアルゴリズムは容易に並列化でき、実際、Objectronよりも450倍高速なカスタムC++/CUDA実装を提供しています。

以下に、C++によるObjectronと、C++およびCUDAによる私たちのアルゴリズムのパフォーマンスを比較します。boxes1にM個の予測を、boxes2にN個の画像内の正解3Dボックスを格納し、MxN IoU行列を計算する物体検出における一般的なユースケースについてベンチマークを行います。M=N=16の場合の時間をms単位で報告します。

drawing

使用方法とコード

from pytorch3d.ops import box3d_overlap
# Assume inputs: boxes1 (M, 8, 3) and boxes2 (N, 8, 3)
intersection_vol, iou_3d = box3d_overlap(boxes1, boxes2)

詳細については、iou_box3d.pyを参照してください。

現在、実装は微分可能ではありません。近いうちに勾配サポートを追加する予定です。

また、ObjectronとMeshLabと比較した広範なテストも含まれています。

引用

3D IoUアルゴリズムを使用する場合は、PyTorch3Dを引用してください。

@article{ravi2020pytorch3d,
    author = {Nikhila Ravi and Jeremy Reizenstein and David Novotny and Taylor Gordon
                  and Wan-Yen Lo and Justin Johnson and Georgia Gkioxari},
    title = {Accelerating 3D Deep Learning with PyTorch3D},
    journal = {arXiv:2007.08501},
    year = {2020},
}