高級駕駛輔助系統（ADAS）開發中最關鍵的問題之一是汽車周圍環境的描述方式。環境可以分為動態和靜態部分。第一個用于描述所有可移動物體，如汽車或汽車等。行人。第二個代表靜態障礙物，如護欄、路緣石、建筑物或障礙物等。為了在擁擠的環境中自由移動，需要提供有關所有周圍障礙物的高精度信息。有一個可用于此目的的廣泛表示，即 2D和 3D 網格、區間圖、原始結構和輪廓。

根據應用，不同表示形式具有不同程度的復雜性。此外，大多數表示都依賴于傳感器。之所以如此，是因為用于創建特定表示的算法依賴于傳感器的物理規格和限制，目前市場上可以找到使用雷達、攝像頭或激光雷達等傳感器的解決方案。然而，傳感器依賴性是一個不允許進一步改進的問題，可以通過直接使用來自不同類型傳感器的輸入來獲得。將來自各種傳感器的信息組合成一個表示的一種可能方法是占用網格，這種方法可以解釋為作為傳感器融合。不幸的是，由于內存和處理能力有限，占用網格并不是嵌入式系統的最佳解決方案。

此外，將網格作為一組單元格的原始表示形式，填充了簡單的占用概率，并不是真正有用的用于后續的上層 ADAS 感知算法。由于數據量很大且接口帶寬有限，因此無法通過 CAN 等常見汽車接口輕松發送。這可以通過在占用之間添加一層參數化自由空間Parametric Free Space，PFS（PFS 通過參數化方法描述已知沒有障礙物的區域的邊界曲線，這種對主車靜止環境的緊湊描述可以有多種形式，這種描述的一種靈活而緊湊的形式稱為參數自由空間）來消除這些復雜網格的對應數據位（如下圖），這樣可以提供周圍環境的緊湊描述。

?

簡而言之，PFS 確定包括兩個主要步驟。PFS 的輸入是占用網格，該算法從使用圖像處理技術進行網格預置開始，結果是生成一組代表自由空間邊界的網格單元。然后對這些單元進行近似最終結果的一組預定義數量的控制點，代表給定次數的樣條曲線，這樣可以很容易地被后續ADAS算法使用。

問題描述

在汽車行業中，所有感知算法都是循環執行的，并且必須在預定義長度的時隙（例如 50 ms）內處理當前輸入，當前，有多種方法可以滿足嚴格的實時要求。第一個想到的想法，就是使用更好的CPU單元。這樣的解決方案并不令人滿意，因為它會產生相當大的成本，從而降低產品的競爭力。基于摩爾定律上看，即使成本不會成為問題，有些算法根本無法達到時間限制，這意味著最合理的解決辦法是算法優化。

本文不關注代碼實現形式的優化問題，而是關注一般方法。討論的參數化可行使空間檢測 PFS 確定算法是從圖像處理操作開始，將其輸入占用網格轉換為一個二進制文件，這些文件中僅限制目標周圍自由區域的單元具有非零值，所有其他單元均為零。由于在自由區域中，代表該邊界的像素數量不是固定的，它可以在周期和場景之間變化（如下圖a）。這里假設設置可行駛區域的單元方式構成是由有序像素的組成方式來進行連接閉合邊界。

邊界單元的動態數量

在處理的第二階段，邊界像素集是用參數樣條曲線進行近似的。這種近似可能產生以下負擔：不必要的高計算復雜度，因為通常大多數像素不提供附加信息的。而且，在每個計算周期，邊界點的數量可能不同。如上圖b表示不太擁擠的道路環境將有更多的自由空間，因此邊界由更多的單元組成。

由于測量尺寸（邊界像素的數量）沒有嚴格定義的上限，因此需要在內存中保留足夠多的空間來滿足所有可能的情況。此外，邊界像素的數量在每個周期之間可能會有所不同。這些方面在嵌入式系統中并不受歡迎（大多數嵌入式系統甚至不允許動態內存分配）。

一旦完成圖像處理并確定邊界像素，單元定義的邊界將通過參數曲線（b 樣條曲線）來近似。它由狀態空間模型表示為：

?

其中，





表示觀測矩陣，其中的q表示為：

是作為一組2維B樣條控制點的狀態向量，Nq是控制點的數量，Nm是測量點的數量，qx,n表示第n個控制點的縱向位置，qy,n表示第n 個控制點的橫向位置。

使用信息濾波器在每個周期遞歸地完成近似，這對于大量測量點而言比經典卡爾曼濾波器計算效率更高。即使進行了這種優化，大量測量仍然是一個問題（模型被視為單個 2D 測量，并用于更新兩個樣條函數x(s)和 y(s)。此外，為了能夠使用信息過濾器，必須預先在每個循環進行計算觀測矩陣H(s)，其大小（行數）嚴格取決于測量次數。

針對一般點云的數據縮減，人們提出了許多方法。比如，通過基于所需點數縮減的比率搜索點子集來實現。

本文介紹的方法最小化了原始集和縮減子集之間的幾何偏差。還有另一種方法由兩個步驟組成。第一步，通過八叉樹結構對點云進行正則化和壓縮。第二步，點云根據曲率規則進行簡化。這種方法與八叉樹結構有一些相似之處。還有一些基于kmeans聚類算法的自適應簡化方法。唯一的數據縮減（向下選擇）在曲線擬合上下文中找到的算法是“正切函數”專用于非均勻有理B樣條 (NURBS) 近似的方法”。

在該方法中，向下選擇步驟包括三個連續原始測量點的局部二次插值，以查找沿定義的二次插值的斜率符號的變化空間軸。如果檢測到斜率變化，則向下選擇最近的測量點，然后將其做為 NURBS 的控制點。否則，不向下選擇任何測量點。

解決方案

為了解決上一節中描述的大量測量的問題，這里提出了三種測量下選算法。

1、測量點分布均勻

PFS算法的一個假設是所有測量點均勻分布。這意味著樣條曲線和測量點的起點和終點相對應。基于此，最簡單（樸素）的下選算法是取每個第k測量點（mx,k，my,k），并根據以下公式：

該解決方案的缺點是它強制樣條線的每個控制點只有一個測量點，這可能不足以準確反映周圍環境。

2、“Line”向下選擇

本段和下一段中描述的算法集中于以下思想：僅保留行測量的特征點，并過濾掉所有冗余的點，即那些不提供有關邊界形狀的有價值信息的點。

“線”向下選擇是通過使用線性方程y=ax+b來過濾特征點（即單元格表示形式），其想法是拒絕盡可能多的共線點。整個邊界被分為相同長度的部分，部分端點是用虛擬線連接。

然后，對于該部分（其端點之間）內的每個點（像素），計算到該線的距離（例如下圖中綠色特征點連接的紅線部分）。如果該點的距離較大于閾值，該點被視為特征點。

所有比該閾值更接近直線的像素都被認為是冗余的。一段的每個終點也是下一段的起點，也被視為特征點，保留這些點的好處是每個樣條控制點（假設截面長度足夠小）至少有一個支撐測量點。該算法通過尋找部分端點之間的特定點來擴展簡單統一方法。

3、邊界方向的下采樣

為了限制額外操作的數量，尋找特征點，基于“方向”的方法僅限于對像素進行簡單操作。其想法是檢查從前一個像素到感興趣像素的移動方向是否正確。并且從感興趣的像素到下一個像素，按照該順序，是相同的。如果不同，則中間點被視為特征點。例如，如果所考慮的點之前和之后的移動方向是往右上角（見下圖所示）的，則該點不被標記為特征點。但如果連續移動方向不同，則該點被標記為特征點。

算法優勢的不同維度對比

為了避免操作系統對計算時間估算的影響，需要重復測試多次并取平均值。最終的計算時間在下一節中給出，是所有場景中最長的時間。比較最長時間而不是平均值更有價值，因為無論汽車周圍環境多么復雜，每種算法都應該在有限的時間內完成其工作。

1、降采樣大小

如下圖表示包含每種方法每個周期的平均測量點數量。正如預期的那樣，與不使用降選方法相比，Original表示所提出的下采樣方法中每個周期的平均測量點數量。本文提出的方法顯著減少了測量點的數量，“Uniform”算法平均值減少了 16.74 倍，基于“Line”的算法平均值減少了 11.61，基于“Direction”方法則只有 2.15。

因此，大多數點都是使用“Uniform”方法過濾的。過濾的點數正好是使用的樣條控制點的數量（即100）。“Line”方法作為前一種方法的擴展，添加了重要的點。這兩種方法比前一種方法要好得多。“Direction”方法僅將測量點的數量減少大約 2 倍。其主要原因是該方法實際上表現得更像插值器，因此它不能很好地處理噪聲數據，在這種情況下，噪聲數據可能是一個復雜的邊界形狀。

2、計算時間

正如第一段所述，主要目標是減少計算時間，以滿足算法執行的實時性要求，耗時比較如下表2所示。

表2的每一行都顯示了測試方法的結果，表中只列出了下選影響的PFS算法階段，乍一看，所提出的解決方案比原始算法至少快1.38倍。在觀測矩陣計算中尤其明顯，更少的測量次數有助于將該階段的運行時間提高 14 倍。

3、準確性/質量比較

由于PFS是主動安全系統的一部分，所以可以用分類器來評價，我們可以采用完整的（不是下選的）一組邊界像素為參考，則每個逼近樣條的點都可以落入以下事件之一：

TP 真陽性 — 偏差（樣條點與相應邊界點之間的距離）低于定義的最大允許偏差。

FN 假陰性 — 樣條點超出參考邊界像素之外的最大允許偏差。

FP 誤報 — 樣條點超出最大允許偏差但在參考邊界像素內。

根據上述事件，計算以下指標：

TPR 真陽性率 — 衡量正確識別的實際陽性結果的百分比。

PPV：陽性預測值 — 定義測量的性能。

F1：F1 分數 — 是分類準確性（包括精確率和召回率）的綜合衡量標準。

? ?

樣條采樣示例——縱向部分

使用上述指標的目的是從安全角度評估道路基礎設施分類結果，顯然，障礙物被錯誤分類為自由空間，比自由空間分類為障礙物更危險。

4、自由空間估計精度

使用一組 20 個不同的場景日志進行精度分析，并使用每種下采樣算法重新模擬。由算法的圖像處理部分生成的測量點集用作參考。這是一個足夠多的選擇，因為每個所提出的方法不會影響原始測量點集，而只會執行下選擇。為進行比較而進行的整個統計分析依賴于這樣的假設：生成的樣條是在與邊界像素向量具有相同分布的點處進行采樣的。因此，如果邊界由 321 個點組成，用于樣條更新，則樣條會在沿整個長度均勻分布的 321 個點中采樣（如上圖）。對于每個點，計算與參考的偏差進行最終匯總。如下圖顯示了所有算法的誤差累積分布。

正如預期的那樣，根據所使用的測量點的數量，基于“Direction”的算法獲得了最好的結果，基于“Uniform”算法獲得了最差的幾何近似值。為了決定應該采取哪種解決方案，讓我們考慮兩個質量因子Qtime，它更關注計算時間Qmemory，它專注于內存計算。在這兩種情況下，值越高表示結果越好。

Xref,k - 參考點的縱向位置（像素中心） yref,k - 參考點的橫向位置（像素中心） Xspline,k - 樣條線采樣點的縱向位置 對應于Xref,k，yspline,k- 樣條線樣本點的橫向位置對應于yref,k。 K - 點索引 Mi- 第 i個周期的參考點（像素）數量（周期之間有所不同） N - 周期數（來自所有使用的日志） T - 每個周期的平均計算時間 Nall - 所有測量點的數量

Nreduce - 減少的測量點數量

總結

參數曲線可以是智能汽車感知系統中自由空間邊界的緊湊表示。在這樣的應用中，它通常通過占用網格上自由空間和占用空間之間的邊界的近似來獲得。近似這種邊界處理的現有算法具有大量必須處理的測量點（也即網格單元）。實際上，其中許多點是冗余的并且不添加任何信息。為了降低對處理能力的需求，一般可以拒絕對這些冗余點進行進一步處理，也不會降低近似的質量。本文介紹了幾種可以達到這一目標的下采樣算法，所有算法都使用通用的統計指標進行比較。算法性能的比較是在代表不同道路場景的數十條日志的基礎上進行的。

實驗表明并證明，對于使用所提出的方法的所有測試用例，PFS 計算中的運行時間和內存需求都可以顯著降低，同時可以保持性能（準確性）。這對于資源有限的汽車嵌入式系統非常重要。所提出的下選算法在數據減少、執行時間、準確性和安全性方面進行了比較。總體而言，“線”算法是最有前途的一種。它提供了算法效率（即時間/內存消耗）和性能（準確性）之間的最佳平衡。對于未來的工作中，人們可以研究整個處理流程的其他步驟，特別是圖像預處理步驟等方向，因為它仍然是最耗時的部分。

審核編輯：劉清