一種基于K-means 的雷達(dá)機(jī)動(dòng)目標(biāo)檢測(cè)算法

程書慧，陳凌珊，楊軍典

（1.201620 上海市 上海工程技術(shù)大學(xué) 機(jī)械與汽車工程學(xué)院；2.213002 江蘇省 常州市 德心智能科技（常州）有限公司）

0 引言

無(wú)人駕駛實(shí)現(xiàn)原理分為感知層、控制層和決策層，感知層為控制、決策規(guī)劃層提供可靠基礎(chǔ)數(shù)據(jù)。毫米波雷達(dá)具有抗干擾能力強(qiáng)、穿透性好、分辨率高、全天候工作等優(yōu)點(diǎn)成為汽車高級(jí)輔助駕駛功能傳感器首選[1]。毫米波雷達(dá)通過(guò)發(fā)射機(jī)發(fā)射特定頻率信號(hào)，經(jīng)過(guò)目標(biāo)物反射，接收機(jī)接收信號(hào)。將發(fā)射信號(hào)與接收到的信號(hào)進(jìn)行混頻，得到中頻信號(hào)。中頻信號(hào)經(jīng)過(guò)模數(shù)轉(zhuǎn)換器數(shù)字采樣后進(jìn)行信號(hào)處理，包括一維（距離）快速傅里葉變換得到距離信息、二維（速度）快速傅里葉變換得到速度信息、動(dòng)目標(biāo)指示濾波器抑制雜波、恒虛警率(CFAR)過(guò)濾信號(hào)，得到有效目標(biāo)點(diǎn)進(jìn)行角度估計(jì)，得到目標(biāo)的方位信息。將有效檢測(cè)點(diǎn)進(jìn)行聚類，完成目標(biāo)檢測(cè)后進(jìn)行分類、追蹤等數(shù)據(jù)處理[2]。雷達(dá)工作流程如圖1 所示。

對(duì)于雷達(dá)機(jī)動(dòng)目標(biāo)檢測(cè)，CFAR 檢測(cè)算法是通過(guò)對(duì)速度FFT 后的信號(hào)處理，對(duì)檢測(cè)單元進(jìn)行噪聲處理，再統(tǒng)計(jì)樣本，設(shè)置閾值，剔除小于閾值的被測(cè)單元，提高了多目標(biāo)等雜波較多場(chǎng)景下的檢測(cè)性能[3]。而CAFR 目標(biāo)檢測(cè)缺少了后續(xù)的聚類步驟，不能夠有效地將檢測(cè)到的機(jī)動(dòng)目標(biāo)與反射的檢測(cè)點(diǎn)融合，因而不便于后續(xù)的數(shù)據(jù)處理。基于密度的聚類算法（DBSCAN）是通過(guò)檢測(cè)點(diǎn)密度間的關(guān)系，找到滿足設(shè)置掃描半徑與最小包含點(diǎn)數(shù)對(duì)數(shù)據(jù)樣本迭代循環(huán)[4]。而DBSCAN 算法對(duì)樣本質(zhì)量要求較高，一般適用于密度較大的數(shù)據(jù)集，而毫米波雷達(dá)采集的是稀疏點(diǎn)云數(shù)據(jù)，其密度較小，使用DBSCAN算法聚類效果不佳。基于傳統(tǒng)的K-means 算法機(jī)動(dòng)目標(biāo)的檢測(cè)，通過(guò)樣本間的距離作為目標(biāo)函數(shù)進(jìn)行迭代優(yōu)化檢測(cè)目標(biāo)[5]。由于雷達(dá)對(duì)采集的虛假信號(hào)處理后，雷達(dá)有效點(diǎn)云數(shù)量較少，且K-means聚類為無(wú)監(jiān)督學(xué)習(xí)，無(wú)法保證K 值的準(zhǔn)確性，且聚類結(jié)果對(duì)K 值及初始化中心較為敏感，使用傳統(tǒng)的K-means 聚類檢測(cè)效果會(huì)很差[6]。

本文提出了一種改進(jìn)的K-means 算法來(lái)實(shí)現(xiàn)雷達(dá)機(jī)動(dòng)目標(biāo)的檢測(cè)。建立緩存區(qū)、速度預(yù)聚類及關(guān)聯(lián)門，用于解決傳統(tǒng)K-means 對(duì)雷達(dá)數(shù)據(jù)聚類中存在的問(wèn)題。改進(jìn)K-means 流程如圖1 所示。

圖1 雷達(dá)工作流程圖Fig.1 Radar work flow chart

1 傳統(tǒng)的K-means 聚類

K-means 將雷達(dá)接收到的稀疏數(shù)據(jù)聚類為不同的簇進(jìn)行目標(biāo)檢測(cè)，聚類結(jié)果取決于參數(shù)K 值和初始化中心的選取。K 表示最終所聚類得到的類別，不同初始化聚類中心點(diǎn)和K 值會(huì)得到不同結(jié)果。每一輪迭代重新計(jì)算質(zhì)心位置，直至質(zhì)心不再變化。

假設(shè)輸入已預(yù)處理的樣本集 X={x1，x2，…，xn}，輸出類別 C={c1，c2，…，cm}。步驟：（1）隨機(jī)指定m 個(gè)點(diǎn)作為初始化聚類中心μ0，μ1，…，μm；其次，計(jì)算各個(gè)樣本點(diǎn)距聚類中心的距離樣本距離dij最小，則該樣本屬于j 簇；（2）更新各簇的質(zhì)心位置（Cj——j 簇中樣本數(shù)；dj——j 簇中每個(gè)樣本距離聚類中心的距離）；（3）判斷是否達(dá)到最大迭代次數(shù)T 或聚類中心不再發(fā)生改變，若否重復(fù)步驟2、步驟3；（4）輸出集合C 中各個(gè)簇[7]。

傳統(tǒng)K-means 聚類為無(wú)監(jiān)督學(xué)習(xí)，而每個(gè)檢測(cè)場(chǎng)景中毫米波雷達(dá)檢測(cè)的目標(biāo)數(shù)量是一定的。若K 值不準(zhǔn)確，則聚類結(jié)果是錯(cuò)誤的。傳統(tǒng)的K-means通過(guò)肘部原則來(lái)確定K 值，將檢測(cè)點(diǎn)與各簇的聚類中心的平方差和定義為畸變函數(shù)，如式（1）所示。該函數(shù)值會(huì)隨著K 值的增大而降低，達(dá)到某個(gè)K值后，收斂速度放慢，該K 值則為K-means 中最佳初始化K 值[8]。

傳統(tǒng)K-means 聚類算法的復(fù)雜度為O（nmT），n 為樣本集的個(gè)數(shù)，m 為類別數(shù)，T 為最大迭代次數(shù)。若已知初始化中心和K 值，則不再進(jìn)行最大次數(shù)與肘部原則選取K 值的迭代，此時(shí)復(fù)雜度為O(1)，且正確的K 值將得到準(zhǔn)確的檢測(cè)結(jié)果。

2 改進(jìn)的K-means 聚類

本文使用nuScenes 提供的開源數(shù)據(jù)由大陸ASR408 毫米波雷達(dá)采集，采樣頻率為13 Hz，視場(chǎng)角FOV=120°。采集的每一幀數(shù)據(jù)包括18 個(gè)目標(biāo)物的屬性信息，125 個(gè)有效目標(biāo)檢測(cè)點(diǎn)。雷達(dá)坐標(biāo)系如圖2 所示，X 軸為汽車前進(jìn)方向，Y 為汽車側(cè)向，Z 軸為汽車垂直方向，F(xiàn)OV 為視場(chǎng)角。毫米波雷達(dá)部分采集數(shù)據(jù)見表1，每個(gè)檢測(cè)點(diǎn)屬性具有序號(hào)、坐標(biāo)位置（x，y）、雷達(dá)散射截面積RCS、目標(biāo)的速度vx和vy。

表1 毫米波雷達(dá)預(yù)處理數(shù)據(jù)Tab.1 Some data attributes of radar detection points

圖2 車載毫米波雷達(dá)坐標(biāo)系Fig.2 Coordinate system of vehicular millimeter wave radar

駕駛過(guò)程中通常只關(guān)心機(jī)動(dòng)目標(biāo)，可能對(duì)行車安全造成危險(xiǎn)，需要知道機(jī)動(dòng)目標(biāo)的位置和速度等屬性信息，便于控制汽車保證行車安全[9]。雷達(dá)接收到的反射波經(jīng)過(guò)與發(fā)射波的混頻等處理得到物體的狀態(tài)信息。通過(guò)對(duì)目標(biāo)點(diǎn)速度屬性設(shè)置閾值，將靜態(tài)目標(biāo)過(guò)濾，得到有效的動(dòng)目標(biāo)點(diǎn)進(jìn)行聚類。由于多普勒特性和雷達(dá)性能影響，存在部分靜態(tài)目標(biāo)帶有微小速度噪聲[10]，本文設(shè)置的閾值為0.3 m/s。

2.1 緩存區(qū)的建立

車載毫米波雷達(dá)為77 GHz 發(fā)射信號(hào)頻率高波長(zhǎng)短，且雷達(dá)的回波信號(hào)往往是不穩(wěn)定的，由于多路徑效應(yīng)和遮擋等環(huán)境因素，會(huì)大幅降低毫米波能量，且信號(hào)處理會(huì)過(guò)濾不可靠數(shù)據(jù)，造成雷達(dá)采集點(diǎn)云為稀疏數(shù)據(jù)。雷達(dá)每幀數(shù)據(jù)僅有125 個(gè)檢測(cè)點(diǎn)，過(guò)濾靜態(tài)目標(biāo)后點(diǎn)的數(shù)量將減少，而K-means 聚類結(jié)果較為依賴樣本數(shù)據(jù)數(shù)量與質(zhì)量，在復(fù)雜的交通環(huán)境中數(shù)據(jù)樣本較少，聚類得到的結(jié)果將不具備參考意義。如圖3 所示，將雷達(dá)某一幀檢測(cè)點(diǎn)映射到圖像坐標(biāo)系中，不同的顏色代表不同距離的檢測(cè)點(diǎn)，可知每個(gè)目標(biāo)上的檢測(cè)點(diǎn)較少。

圖3 將雷達(dá)檢測(cè)點(diǎn)映射到圖像空間Fig.3 Map radar detection points to image space

基于數(shù)據(jù)樣本較少與質(zhì)量較差的問(wèn)題，提出緩存區(qū)以改進(jìn)K-means 聚類算法。將當(dāng)前幀與前4幀的檢測(cè)點(diǎn)經(jīng)運(yùn)動(dòng)補(bǔ)償后緩存，對(duì)5 幀數(shù)據(jù)進(jìn)行聚類。已知連續(xù)5 幀得到625 個(gè)樣本點(diǎn)一同進(jìn)行處理，過(guò)濾靜態(tài)點(diǎn)，增加樣本數(shù)量。雷達(dá)每一幀的采集間隔為77 ms，緩存5 幀的時(shí)間為0.3 s，該時(shí)間段內(nèi)車輛自身運(yùn)動(dòng)需對(duì)前4 幀的檢測(cè)結(jié)果進(jìn)行運(yùn)動(dòng)補(bǔ)償。假設(shè)物體在該0.3 s 內(nèi)為勻速運(yùn)動(dòng)，對(duì)前4 幀的數(shù)據(jù)進(jìn)行運(yùn)動(dòng)補(bǔ)償，并對(duì)緩存區(qū)數(shù)據(jù)進(jìn)行更新，每更新一幀，更新聚類結(jié)果達(dá)到實(shí)時(shí)性要求，此時(shí)可忽略運(yùn)動(dòng)方向改變所引起的誤差，使用速度與時(shí)間差進(jìn)行距離上的補(bǔ)償。將緩存區(qū)數(shù)據(jù)按照式（2）進(jìn)行運(yùn)動(dòng)補(bǔ)償，結(jié)果如圖4 所示。

圖4 緩存區(qū)建立后動(dòng)態(tài)與靜態(tài)檢測(cè)點(diǎn)Fig.4 Dynamic and static detection points after the cache area is established

式中：t——每一幀數(shù)據(jù)間的時(shí)間差，t=77 ms；Δvij——第i 幀中第j 個(gè)目標(biāo)與主車的相對(duì)速度；Δdij——目標(biāo)所需要的補(bǔ)償?shù)木嚯x。

2.2 預(yù)聚類處理

對(duì)檢測(cè)點(diǎn)速度進(jìn)行過(guò)濾篩選，由于同一個(gè)目標(biāo)上對(duì)應(yīng)的檢測(cè)點(diǎn)應(yīng)具有相同的速度，可得到物體個(gè)數(shù)確定K-means 所需K 值，并將預(yù)聚類得到的質(zhì)心作為K-means 聚類的初始化中心，將在一定范圍的點(diǎn)速度差值小于設(shè)定的閾值則認(rèn)為是一個(gè)簇。本文設(shè)置在5 m 范圍內(nèi)速度相差±0.1 m/s 的檢測(cè)點(diǎn)，將被認(rèn)為同一個(gè)類的點(diǎn)即同一個(gè)目標(biāo)，對(duì)所有動(dòng)檢測(cè)點(diǎn)遍歷，K 值依次累加，此場(chǎng)景下的動(dòng)目標(biāo)個(gè)數(shù)為10。如圖5 所示，利用肘部原則選取K 的最佳值應(yīng)取3，通過(guò)速度預(yù)聚類K 取為10，預(yù)聚類得到的K 值較為接近真實(shí)情況。

圖5 肘部原則來(lái)確定初始K 值Fig.5 Elbow principle to determine initial K value

2.3 關(guān)聯(lián)門的建立

關(guān)聯(lián)門的大小取決于目標(biāo)尺寸，通?；谒俣却笮∨袛嗾J(rèn)為，機(jī)動(dòng)性大的目標(biāo)（即速度較大的目標(biāo)）尺寸較?。换诰彺鎱^(qū)內(nèi)點(diǎn)密度判斷目標(biāo)的大小，認(rèn)為檢測(cè)點(diǎn)密度較大，目標(biāo)反射電磁波較多的目標(biāo)尺寸較大。采用位置-速度關(guān)聯(lián)，先進(jìn)行位置關(guān)聯(lián)，若位置關(guān)聯(lián)成功則進(jìn)行速度關(guān)聯(lián)。所采用關(guān)聯(lián)門方程如式（3）所示：

式中：x0，y0——橢圓中心；kσx，kσy——橢圓的2個(gè)半軸。

當(dāng)σx=σy時(shí)，方程為圓的一般方程式即關(guān)聯(lián)門為圓形。將檢測(cè)點(diǎn)坐標(biāo)代入方程中，x0，y0為橢圓中心，x，y 為待關(guān)聯(lián)檢測(cè)點(diǎn)，kσx，kσy為設(shè)定關(guān)聯(lián)門大小。當(dāng)滿足方程左側(cè)值≤1，則關(guān)聯(lián)成功；當(dāng)方程左側(cè)值＞1，則關(guān)聯(lián)失敗。

一次關(guān)聯(lián)門使用較大的圓形關(guān)聯(lián)門進(jìn)行粗過(guò)濾。由于目標(biāo)形狀多為長(zhǎng)方形，在進(jìn)行二次關(guān)聯(lián)門時(shí)使用橢圓形關(guān)聯(lián)門，而當(dāng)主車速度大于10 m/s時(shí)，主車機(jī)動(dòng)性較強(qiáng)，造成緩存區(qū)建立時(shí)運(yùn)動(dòng)補(bǔ)償誤差累積，此時(shí)使用圓形關(guān)聯(lián)門。

一次關(guān)聯(lián)門利用圓形關(guān)聯(lián)門過(guò)濾已知不屬于目標(biāo)的檢測(cè)點(diǎn)，利用傳統(tǒng)K-means 聚類中聚類中心的確定方法，對(duì)關(guān)聯(lián)門內(nèi)的檢測(cè)點(diǎn)重新計(jì)算聚類中心，作為二次關(guān)聯(lián)門的中心。二次關(guān)聯(lián)門是由于毫米波雷達(dá)對(duì)金屬反射的敏感性，易產(chǎn)生一些虛假檢測(cè)點(diǎn)“鬼影”，緩存區(qū)的建立增加有效目標(biāo)檢測(cè)點(diǎn)的同時(shí)會(huì)增多虛假檢測(cè)點(diǎn)。本文算法利用關(guān)聯(lián)門以聚類中心為關(guān)聯(lián)門中心，將一些虛假檢測(cè)點(diǎn)過(guò)濾，使目標(biāo)分離出來(lái)。

2.4 算法描述

改進(jìn)后的K-means 算法流程圖如圖6 所示，其實(shí)現(xiàn)步驟為：

圖6 算法流程圖Fig.6 Algorithm flow chart

（1）完成緩存區(qū)的建立。將5 幀數(shù)據(jù)緩存到一起，經(jīng)運(yùn)動(dòng)補(bǔ)償后進(jìn)行靜態(tài)與動(dòng)態(tài)檢測(cè)點(diǎn)的過(guò)濾；

（2）速度預(yù)聚類。確定預(yù)聚類的位置范圍值與速度差的值，經(jīng)預(yù)聚類后得到K-means 聚類的初始化K 值，并在K 類中隨機(jī)指定每個(gè)類內(nèi)的檢測(cè)點(diǎn)作為初始化聚類中心；

（3）K-means 聚類。給定K 值與初始化聚類中心的K-means 聚類，不再對(duì)K 值與初始化中心的選取進(jìn)行循環(huán)迭代；

（4）一次關(guān)聯(lián)門處理。對(duì)聚類得到的簇以步驟（3）的聚類中心作為關(guān)聯(lián)門中心，使用圓形關(guān)聯(lián)門，并重新計(jì)算關(guān)聯(lián)門內(nèi)的檢測(cè)點(diǎn)，以確定類內(nèi)中心；

（5）二次關(guān)聯(lián)門處理。以步驟4 中得到的中心點(diǎn)作為關(guān)聯(lián)門的中心點(diǎn)進(jìn)行關(guān)聯(lián)門處理，最終在檢測(cè)點(diǎn)中區(qū)分各個(gè)目標(biāo)。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)使用設(shè)備為筆記本電腦i7-5600，顯卡為GTX970M，PyCharm 軟件，Python3.7.3 與PyTorch深度學(xué)習(xí)網(wǎng)絡(luò)框架。由于毫米波雷達(dá)采集數(shù)據(jù)為點(diǎn)云，檢測(cè)結(jié)果不能直觀判斷目標(biāo)檢測(cè)的準(zhǔn)確性。利用nuScenes 提供的場(chǎng)景標(biāo)注作對(duì)比，如圖7 所示，主車?yán)走_(dá)位于圖中×位置，方框?yàn)樗鶚?biāo)注的目標(biāo)，帶有短線段的點(diǎn)表示毫米波雷達(dá)所采集的檢測(cè)點(diǎn)，線段表示檢測(cè)點(diǎn)的速度。利用圖像檢測(cè)算法YOLOv5 的檢測(cè)結(jié)果與本文算法作為對(duì)比，圖像檢測(cè)算法結(jié)果如圖8 所示。

圖7 數(shù)據(jù)集標(biāo)注圖Fig.7 Data set annotation map

圖8 YOLOv5 檢測(cè)場(chǎng)景圖Fig.8 YOLOv5 detection scene diagram

利用Python 實(shí)現(xiàn)算法，并將聚類結(jié)果在雷達(dá)坐標(biāo)系中顯示，圖9 為傳統(tǒng)K-means 算法檢測(cè)結(jié)果，不同形狀的點(diǎn)表示不同的簇。圖10 為本文算法檢測(cè)結(jié)果，星狀表示一次關(guān)聯(lián)門處理時(shí)的聚類中心，圓點(diǎn)表示重新計(jì)算后二次關(guān)聯(lián)門的中心。其中，縱坐標(biāo)x 軸為汽車前進(jìn)的方向，橫坐標(biāo)y 軸為汽車橫向的方向，坐標(biāo)系的圓點(diǎn)為車載雷達(dá)的坐標(biāo)原點(diǎn)。圖9 中，傳統(tǒng)K-means 中肘部原則所得K 值錯(cuò)誤，且未經(jīng)過(guò)關(guān)聯(lián)門處理將5 幀中干擾點(diǎn)也進(jìn)行聚類，而且不能確定目標(biāo)的確定位置。對(duì)比圖8 與圖10可知，在護(hù)欄外的車輛及被樹木遮擋的車輛，圖像算法并未檢測(cè)出，而毫米波雷達(dá)利用電磁波的特性可清晰看到目標(biāo)存在。

圖9 傳統(tǒng)K-means 檢測(cè)結(jié)果Fig.9 Traditional K-means detection results

圖10 本文算法檢測(cè)結(jié)果Fig.10 Detection results of the algorithm

利用多幀數(shù)據(jù)進(jìn)行檢測(cè)并與場(chǎng)景中的真值標(biāo)簽進(jìn)行對(duì)比，使用外部指標(biāo)來(lái)評(píng)價(jià)模型在整個(gè)場(chǎng)景中的性能表現(xiàn)，對(duì)正確檢測(cè)與錯(cuò)誤檢測(cè)進(jìn)行統(tǒng)計(jì)，如表2 所示。將在相同設(shè)備下不同算法的代碼運(yùn)行時(shí)間來(lái)評(píng)判檢測(cè)速度。經(jīng)統(tǒng)計(jì)計(jì)算，文本算法的正確率達(dá)到92.04%，在相同的設(shè)備情況下相較于傳統(tǒng)的K-means 準(zhǔn)確率0.889 1 有較大提升，同時(shí)由于不再對(duì)K 值及初始化中心進(jìn)行迭代，檢測(cè)速度提高百分之36%。利用本文提出的算法進(jìn)行檢測(cè)，速度較傳統(tǒng)的檢測(cè)算法有很大提升，且檢測(cè)精度較高，由此得出此算法模型可靠性較高，為控制層和決策層提供了有力保證。

表2 檢測(cè)結(jié)果統(tǒng)計(jì)Tab.2 Test result evaluation index

4 結(jié)論

本文基于傳統(tǒng)的K-means檢測(cè)算法進(jìn)行改進(jìn)，不再對(duì)雷達(dá)的頻域信號(hào)進(jìn)行處理?；诶走_(dá)一次處理得到的點(diǎn)，對(duì)雷達(dá)點(diǎn)云的屬性信息進(jìn)行分析。通過(guò)預(yù)聚類的手段使算法自動(dòng)獲取最優(yōu)解對(duì)應(yīng)的k值，將K-means 由無(wú)監(jiān)督學(xué)習(xí)變?yōu)楸O(jiān)督學(xué)習(xí)。利用聚類結(jié)果進(jìn)行一次關(guān)聯(lián)門重新確定聚類中心，基于聚類中心進(jìn)行二次關(guān)聯(lián)門，分離出目標(biāo)。進(jìn)而提高了檢測(cè)速度和精度。在相同的設(shè)備下，通過(guò)分別計(jì)算傳統(tǒng)K-means 算法與本文算法對(duì)相同數(shù)據(jù)處理速度和精度，得到本文算法檢測(cè)的準(zhǔn)確率達(dá)到92.04%，高于傳統(tǒng)的檢測(cè)準(zhǔn)確率，同時(shí)檢測(cè)速度提高了36%，經(jīng)驗(yàn)證該算法具有良好的檢測(cè)性能。