有方向性 3D 框交集並集：一種新的演算法
作者：Georgia Gkioxari
實作：Georgia Gkioxari 和 Nikhila Ravi
說明
框的交集並集 (IoU) 廣泛用於物件偵測中作為評量指標 (1, 2)。在 2D 中，IoU 通常應用於軸對齊的框，也就是邊緣與影像軸平行的框。在 3D 中，框通常不會對齊軸線，可以在世界上以任何方式旋轉。我們引入一種新演算法，用來計算兩個有方向性 3D 框的精確 IoU。
我們的演算法基於一個簡單的觀察：兩個有方向性 3D 框 box1 和 box2 的交集是一個由 n > 2 個相連平面單位組成的凸多面體（2D 為凸 n 邊形）。在 3D 中，這些平面單位是 3D 三角形面。在 2D 中，它們是 2D 邊緣。每個平面單位都嚴格屬於 box1 或 box2。我們的演算法會透過反覆運算每個框的邊來尋找這些單位。
- 對於
box1中的每個 3D 三角形面e，我們檢查e是否在box2內。 - 如果
e不在內，則我們會捨棄它。 - 如果
e在內或部分在內，則e在box2內的部分會新增到組成最終交集形的單位中。 - 我們對
box2重複上述動作。
以下是我們演算法針對 2D 有方向性框範例的視覺化展示。
請注意，當框的單位 e部分在box內時，e 會分解成更小的單位。在 2D 中，e 為邊緣，會分解成更小的邊緣。在 3D 中，e 為 3D 三角形面，並會被其與之相交的 box 的平面裁切成更多且更小的面。這就是 2D 和 3D 演算法之間唯一的根本差異。
對於先前技術的限制有詳細的討論。物件體介紹了一種非常棒的演算法，可精確計算定向 3D 方框的 IoU。物件體的演算法使用蘇瑟蘭-霍吉曼演算法計算兩個方框的交點。交集形狀是由Qhull 函式庫使用交點構成的凸包形成。
我們的演算法比物件體的演算法有多項優勢
- 我們的演算法也會計算交點，就像物件體一樣，但此外還會儲存各點所屬的平面單元。這不需計算凸包，而凸包計算是
O(nlogn)，而且需仰賴第三方函式庫，該函式庫通常會因無法描述的錯誤訊息而崩潰。 - 物件體的實作假設方框與軸對齊後會旋轉。我們的演算法和實作沒有這樣的假設，而且適用於任何 3D 方框。
- 我們的實作支援分批，這點與物件體不同，後者假設
box1和box2有單元素輸入。 - 我們的實作容易平行化，而且我們提供自訂的 C++/CUDA 實作，其速度比物件體快 450 倍。
以下我們比較使用物件體 (C++) 和我們的演算法 (C++ 和 CUDA) 的效能。我們針對目標偵測的一般使用案例進行基準測試，其中boxes1包含圖像中 M 個預測，boxes2包含 N 個地面實況 3D 方框，並計算MxNIoU 矩陣。我們報告M=N=16時的 ms 時間。
使用方式及程式碼
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。
請注意，我們目前的實作無法微分。我們計畫很快新增對梯度的支援。
我們還包括大量的測試，將我們的實作與物件體和 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},
}