高級(jí)駕駛輔助系統(tǒng)（ADAS）開(kāi)發(fā)中最關(guān)鍵的問(wèn)題之一是汽車(chē)周?chē)h(huán)境的描述方式。環(huán)境可以分為動(dòng)態(tài)和靜態(tài)部分。第一個(gè)用于描述所有可移動(dòng)物體，如汽車(chē)或汽車(chē)等。行人。第二個(gè)代表靜態(tài)障礙物，如護(hù)欄、路緣石、建筑物或障礙物等。為了在擁擠的環(huán)境中自由移動(dòng)，需要提供有關(guān)所有周?chē)系K物的高精度信息。有一個(gè)可用于此目的的廣泛表示，即 2D和 3D 網(wǎng)格、區(qū)間圖、原始結(jié)構(gòu)和輪廓。

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

此外，將網(wǎng)格作為一組單元格的原始表示形式，填充了簡(jiǎn)單的占用概率，并不是真正有用的用于后續(xù)的上層 ADAS 感知算法。由于數(shù)據(jù)量很大且接口帶寬有限，因此無(wú)法通過(guò) CAN 等常見(jiàn)汽車(chē)接口輕松發(fā)送。這可以通過(guò)在占用之間添加一層參數(shù)化自由空間Parametric Free Space，PFS（PFS 通過(guò)參數(shù)化方法描述已知沒(méi)有障礙物的區(qū)域的邊界曲線(xiàn)，這種對(duì)主車(chē)靜止環(huán)境的緊湊描述可以有多種形式，這種描述的一種靈活而緊湊的形式稱(chēng)為參數(shù)自由空間）來(lái)消除這些復(fù)雜網(wǎng)格的對(duì)應(yīng)數(shù)據(jù)位（如下圖），這樣可以提供周?chē)h(huán)境的緊湊描述。

?

簡(jiǎn)而言之，PFS 確定包括兩個(gè)主要步驟。PFS 的輸入是占用網(wǎng)格，該算法從使用圖像處理技術(shù)進(jìn)行網(wǎng)格預(yù)置開(kāi)始，結(jié)果是生成一組代表自由空間邊界的網(wǎng)格單元。然后對(duì)這些單元進(jìn)行近似最終結(jié)果的一組預(yù)定義數(shù)量的控制點(diǎn)，代表給定次數(shù)的樣條曲線(xiàn)，這樣可以很容易地被后續(xù)ADAS算法使用。

問(wèn)題描述

在汽車(chē)行業(yè)中，所有感知算法都是循環(huán)執(zhí)行的，并且必須在預(yù)定義長(zhǎng)度的時(shí)隙（例如 50 ms）內(nèi)處理當(dāng)前輸入，當(dāng)前，有多種方法可以滿(mǎn)足嚴(yán)格的實(shí)時(shí)要求。第一個(gè)想到的想法，就是使用更好的CPU單元。這樣的解決方案并不令人滿(mǎn)意，因?yàn)樗鼤?huì)產(chǎn)生相當(dāng)大的成本，從而降低產(chǎn)品的競(jìng)爭(zhēng)力。基于摩爾定律上看，即使成本不會(huì)成為問(wèn)題，有些算法根本無(wú)法達(dá)到時(shí)間限制，這意味著最合理的解決辦法是算法優(yōu)化。

本文不關(guān)注代碼實(shí)現(xiàn)形式的優(yōu)化問(wèn)題，而是關(guān)注一般方法。討論的參數(shù)化可行使空間檢測(cè) PFS 確定算法是從圖像處理操作開(kāi)始，將其輸入占用網(wǎng)格轉(zhuǎn)換為一個(gè)二進(jìn)制文件，這些文件中僅限制目標(biāo)周?chē)杂蓞^(qū)域的單元具有非零值，所有其他單元均為零。由于在自由區(qū)域中，代表該邊界的像素?cái)?shù)量不是固定的，它可以在周期和場(chǎng)景之間變化（如下圖a）。這里假設(shè)設(shè)置可行駛區(qū)域的單元方式構(gòu)成是由有序像素的組成方式來(lái)進(jìn)行連接閉合邊界。

邊界單元的動(dòng)態(tài)數(shù)量

在處理的第二階段，邊界像素集是用參數(shù)樣條曲線(xiàn)進(jìn)行近似的。這種近似可能產(chǎn)生以下負(fù)擔(dān)：不必要的高計(jì)算復(fù)雜度，因?yàn)橥ǔ４蠖鄶?shù)像素不提供附加信息的。而且，在每個(gè)計(jì)算周期，邊界點(diǎn)的數(shù)量可能不同。如上圖b表示不太擁擠的道路環(huán)境將有更多的自由空間，因此邊界由更多的單元組成。

由于測(cè)量尺寸（邊界像素的數(shù)量）沒(méi)有嚴(yán)格定義的上限，因此需要在內(nèi)存中保留足夠多的空間來(lái)滿(mǎn)足所有可能的情況。此外，邊界像素的數(shù)量在每個(gè)周期之間可能會(huì)有所不同。這些方面在嵌入式系統(tǒng)中并不受歡迎（大多數(shù)嵌入式系統(tǒng)甚至不允許動(dòng)態(tài)內(nèi)存分配）。

一旦完成圖像處理并確定邊界像素，單元定義的邊界將通過(guò)參數(shù)曲線(xiàn)（b 樣條曲線(xiàn)）來(lái)近似。它由狀態(tài)空間模型表示為：

?

其中，





表示觀測(cè)矩陣，其中的q表示為：

是作為一組2維B樣條控制點(diǎn)的狀態(tài)向量，Nq是控制點(diǎn)的數(shù)量，Nm是測(cè)量點(diǎn)的數(shù)量，qx,n表示第n個(gè)控制點(diǎn)的縱向位置，qy,n表示第n 個(gè)控制點(diǎn)的橫向位置。

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

針對(duì)一般點(diǎn)云的數(shù)據(jù)縮減，人們提出了許多方法。比如，通過(guò)基于所需點(diǎn)數(shù)縮減的比率搜索點(diǎn)子集來(lái)實(shí)現(xiàn)。

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

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

解決方案

為了解決上一節(jié)中描述的大量測(cè)量的問(wèn)題，這里提出了三種測(cè)量下選算法。

1、測(cè)量點(diǎn)分布均勻

PFS算法的一個(gè)假設(shè)是所有測(cè)量點(diǎn)均勻分布。這意味著樣條曲線(xiàn)和測(cè)量點(diǎn)的起點(diǎn)和終點(diǎn)相對(duì)應(yīng)?；诖?，最簡(jiǎn)單（樸素）的下選算法是取每個(gè)第k測(cè)量點(diǎn)（mx,k，my,k），并根據(jù)以下公式：

該解決方案的缺點(diǎn)是它強(qiáng)制樣條線(xiàn)的每個(gè)控制點(diǎn)只有一個(gè)測(cè)量點(diǎn)，這可能不足以準(zhǔn)確反映周?chē)h(huán)境。

2、“Line”向下選擇

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

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

然后，對(duì)于該部分（其端點(diǎn)之間）內(nèi)的每個(gè)點(diǎn)（像素），計(jì)算到該線(xiàn)的距離（例如下圖中綠色特征點(diǎn)連接的紅線(xiàn)部分）。如果該點(diǎn)的距離較大于閾值，該點(diǎn)被視為特征點(diǎn)。

所有比該閾值更接近直線(xiàn)的像素都被認(rèn)為是冗余的。一段的每個(gè)終點(diǎn)也是下一段的起點(diǎn)，也被視為特征點(diǎn)，保留這些點(diǎn)的好處是每個(gè)樣條控制點(diǎn)（假設(shè)截面長(zhǎng)度足夠小）至少有一個(gè)支撐測(cè)量點(diǎn)。該算法通過(guò)尋找部分端點(diǎn)之間的特定點(diǎn)來(lái)擴(kuò)展簡(jiǎn)單統(tǒng)一方法。

3、邊界方向的下采樣

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

算法優(yōu)勢(shì)的不同維度對(duì)比

為了避免操作系統(tǒng)對(duì)計(jì)算時(shí)間估算的影響，需要重復(fù)測(cè)試多次并取平均值。最終的計(jì)算時(shí)間在下一節(jié)中給出，是所有場(chǎng)景中最長(zhǎng)的時(shí)間。比較最長(zhǎng)時(shí)間而不是平均值更有價(jià)值，因?yàn)闊o(wú)論汽車(chē)周?chē)h(huán)境多么復(fù)雜，每種算法都應(yīng)該在有限的時(shí)間內(nèi)完成其工作。

1、降采樣大小

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

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

2、計(jì)算時(shí)間

正如第一段所述，主要目標(biāo)是減少計(jì)算時(shí)間，以滿(mǎn)足算法執(zhí)行的實(shí)時(shí)性要求，耗時(shí)比較如下表2所示。

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

3、準(zhǔn)確性/質(zhì)量比較

由于PFS是主動(dòng)安全系統(tǒng)的一部分，所以可以用分類(lèi)器來(lái)評(píng)價(jià)，我們可以采用完整的（不是下選的）一組邊界像素為參考，則每個(gè)逼近樣條的點(diǎn)都可以落入以下事件之一：

TP 真陽(yáng)性 — 偏差（樣條點(diǎn)與相應(yīng)邊界點(diǎn)之間的距離）低于定義的最大允許偏差。

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

FP 誤報(bào) — 樣條點(diǎn)超出最大允許偏差但在參考邊界像素內(nèi)。

根據(jù)上述事件，計(jì)算以下指標(biāo)：

TPR 真陽(yáng)性率 — 衡量正確識(shí)別的實(shí)際陽(yáng)性結(jié)果的百分比。

PPV：陽(yáng)性預(yù)測(cè)值 — 定義測(cè)量的性能。

F1：F1 分?jǐn)?shù) — 是分類(lèi)準(zhǔn)確性（包括精確率和召回率）的綜合衡量標(biāo)準(zhǔn)。

? ?

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

使用上述指標(biāo)的目的是從安全角度評(píng)估道路基礎(chǔ)設(shè)施分類(lèi)結(jié)果，顯然，障礙物被錯(cuò)誤分類(lèi)為自由空間，比自由空間分類(lèi)為障礙物更危險(xiǎn)。

4、自由空間估計(jì)精度

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

正如預(yù)期的那樣，根據(jù)所使用的測(cè)量點(diǎn)的數(shù)量，基于“Direction”的算法獲得了最好的結(jié)果，基于“Uniform”算法獲得了最差的幾何近似值。為了決定應(yīng)該采取哪種解決方案，讓我們考慮兩個(gè)質(zhì)量因子Qtime，它更關(guān)注計(jì)算時(shí)間Qmemory，它專(zhuān)注于內(nèi)存計(jì)算。在這兩種情況下，值越高表示結(jié)果越好。

Xref,k - 參考點(diǎn)的縱向位置（像素中心） yref,k - 參考點(diǎn)的橫向位置（像素中心） Xspline,k - 樣條線(xiàn)采樣點(diǎn)的縱向位置 對(duì)應(yīng)于Xref,k，yspline,k- 樣條線(xiàn)樣本點(diǎn)的橫向位置對(duì)應(yīng)于yref,k。 K - 點(diǎn)索引 Mi- 第 i個(gè)周期的參考點(diǎn)（像素）數(shù)量（周期之間有所不同） N - 周期數(shù)（來(lái)自所有使用的日志） T - 每個(gè)周期的平均計(jì)算時(shí)間 Nall - 所有測(cè)量點(diǎn)的數(shù)量

Nreduce - 減少的測(cè)量點(diǎn)數(shù)量

總結(jié)

參數(shù)曲線(xiàn)可以是智能汽車(chē)感知系統(tǒng)中自由空間邊界的緊湊表示。在這樣的應(yīng)用中，它通常通過(guò)占用網(wǎng)格上自由空間和占用空間之間的邊界的近似來(lái)獲得。近似這種邊界處理的現(xiàn)有算法具有大量必須處理的測(cè)量點(diǎn)（也即網(wǎng)格單元）。實(shí)際上，其中許多點(diǎn)是冗余的并且不添加任何信息。為了降低對(duì)處理能力的需求，一般可以拒絕對(duì)這些冗余點(diǎn)進(jìn)行進(jìn)一步處理，也不會(huì)降低近似的質(zhì)量。本文介紹了幾種可以達(dá)到這一目標(biāo)的下采樣算法，所有算法都使用通用的統(tǒng)計(jì)指標(biāo)進(jìn)行比較。算法性能的比較是在代表不同道路場(chǎng)景的數(shù)十條日志的基礎(chǔ)上進(jìn)行的。

實(shí)驗(yàn)表明并證明，對(duì)于使用所提出的方法的所有測(cè)試用例，PFS 計(jì)算中的運(yùn)行時(shí)間和內(nèi)存需求都可以顯著降低，同時(shí)可以保持性能（準(zhǔn)確性）。這對(duì)于資源有限的汽車(chē)嵌入式系統(tǒng)非常重要。所提出的下選算法在數(shù)據(jù)減少、執(zhí)行時(shí)間、準(zhǔn)確性和安全性方面進(jìn)行了比較。總體而言，“線(xiàn)”算法是最有前途的一種。它提供了算法效率（即時(shí)間/內(nèi)存消耗）和性能（準(zhǔn)確性）之間的最佳平衡。對(duì)于未來(lái)的工作中，人們可以研究整個(gè)處理流程的其他步驟，特別是圖像預(yù)處理步驟等方向，因?yàn)樗匀皇亲詈臅r(shí)的部分。

審核編輯：劉清