鐘晉孝， 晉良念，2*

(1.桂林電子科技大學(xué)信息與通信學(xué)院， 桂林 541004； 2. 廣西無線寬帶通信與信號處理重點(diǎn)實驗室， 桂林 541004)

現(xiàn)代商用毫米波雷達(dá)體積小、質(zhì)量輕、處理速度快以及檢測精度高，使其在許多領(lǐng)域得到了廣泛的應(yīng)用，包括智能駕駛[1-2]、患者監(jiān)護(hù)[3-5]、交通管制[6]等。毫米波雷達(dá)的輸出為點(diǎn)云形式，點(diǎn)云通常是稀疏的，并且不容易可視化以檢測目標(biāo)，因此需要一種聚類算法將各目標(biāo)點(diǎn)云分離。

傳統(tǒng)的基于密度的帶噪聲聚類方法(density-based spatial clustering of applications with noise，DBSCAN)能夠有效分離噪聲點(diǎn)(離群點(diǎn))，它可以在固定的初始核心距離內(nèi)處理不同形狀和大小的集群，同時也不需要聚類數(shù)目的先驗知識。然而，缺點(diǎn)也是顯而易見的，不同的密度分布可能導(dǎo)致聚類效果不理想。對于毫米波雷達(dá)點(diǎn)云數(shù)據(jù)而言，由于雷達(dá)是在極(或球)坐標(biāo)下探測目標(biāo)的，探測所得的點(diǎn)云在近距離場中分布密集，在遠(yuǎn)距離場中分布稀疏，因此即使是同一目標(biāo)，處于雷達(dá)視場中的不同位置時，雷達(dá)點(diǎn)云圖的分布也是不同的。此外，DBSCAN算法對于搜索半徑等參數(shù)也十分敏感。另一方面，現(xiàn)有的聚類算法大多采用圓形區(qū)域聚類[7-8]，相比之下，橢圓形區(qū)域聚類在不規(guī)則分布點(diǎn)云聚類方面更加具有優(yōu)勢。Smith等[9]提出一種橢圓聚類算法，引入加權(quán)密度函數(shù)，基于橢圓結(jié)構(gòu)對點(diǎn)云簇進(jìn)行擴(kuò)展，取得了與標(biāo)準(zhǔn)聚類算法相當(dāng)?shù)男阅?。Mai等[10]提出了一種基于密度的各向異性聚類算法，對于各向同性空間點(diǎn)，該算法與標(biāo)準(zhǔn)算法性能相當(dāng)，而對于各向異性空間點(diǎn)，則具有較大優(yōu)勢。上述研究都是在DBSCAN的基礎(chǔ)上，通過改進(jìn)搜索區(qū)域形狀從而實現(xiàn)對任意形狀目標(biāo)的聚類，然而并沒有考慮各目標(biāo)間密度相差較大的情況。針對該問題，Wagner等[11]提出了一種針對毫米波雷達(dá)點(diǎn)云數(shù)據(jù)的橢圓聚類算法，調(diào)整比例因子對距離、速度以及波達(dá)方向(direction of arrival，DoA)進(jìn)行縮放操作，最終實現(xiàn)了對行人的正確分割。文獻(xiàn)[12]中也提出了一種穩(wěn)健的橢圓點(diǎn)云聚類方法，結(jié)合雷達(dá)的距離分辨率和角度分辨率，能夠?qū)崿F(xiàn)橢圓搜索區(qū)域的形狀根據(jù)位置而變化，使得聚類更加靈活。

然而現(xiàn)有的這些研究大多數(shù)是對二維數(shù)據(jù)進(jìn)行聚類[13-14]，同時需要手動設(shè)置多個參數(shù)[15]。現(xiàn)針對毫米波雷達(dá)點(diǎn)云遠(yuǎn)疏近密這一特點(diǎn)，提出一種結(jié)合遺傳算法(genetic algorithm，GA)的穩(wěn)健自適應(yīng)三維點(diǎn)云聚類方法——GA-DBSCAN。該方法的主要特點(diǎn)有：①將雷達(dá)點(diǎn)云表示為三維體素，三維分別表示距離、方位角以及俯仰角，單位分別為雷達(dá)距離分辨率、方位角分辨率以及俯仰角分辨率，以此來實現(xiàn)對點(diǎn)云目標(biāo)的穩(wěn)健聚類；②結(jié)合遺傳算法，將聚類輪廓系數(shù)以及點(diǎn)云相似度結(jié)合作為目標(biāo)優(yōu)化函數(shù)，實現(xiàn)橢圓搜索區(qū)域相關(guān)參數(shù)的自適應(yīng)學(xué)習(xí)。

1 雷達(dá)點(diǎn)云生成

毫米波調(diào)頻連續(xù)波多輸入多輸出(frequency modulated continuous wave multiple-input multiple-output，F(xiàn)MCW MIMO)雷達(dá)的常用工作頻率為20、60、77和120 GHz，其信號處理流程[16]如圖1所示。

圖1 信號處理流程Fig.1 Signal processing flow

MIMO雷達(dá)的發(fā)射陣列以時分的方式發(fā)射FMCW信號，第m個發(fā)射陣元的發(fā)射信號表示為

Stm(t)=Vtexp[j2π(fmt+0.5μt2)]， 0≤t≤T

(1)

式(1)中：Vt為信號幅值；fm為第m個發(fā)射陣元的載頻；μ為調(diào)頻斜率。第n個接收陣元接收到第m個發(fā)射陣元的回波信號為

(2)

式(2)中：A為信號在傳播路徑中的衰減以及收發(fā)天線的增益；τmn為信號傳播時間。Rmn(t)與Stm(t)混頻后，經(jīng)低通濾波得到中頻信號為

(3)

接下來對中頻信號進(jìn)行距離快速傅里葉變換(fast fourier transform，F(xiàn)FT)，然后通過波束形成得到距離-方位角熱圖，在此基礎(chǔ)上做距離、方位角二維恒虛警率(constant false-alarm rate，CFAR)檢測，得到目標(biāo)點(diǎn)的距離-方位角信息。最后，在俯仰角方向再次應(yīng)用波束形成，并通過峰值檢測獲得目標(biāo)的高度信息，多個點(diǎn)目標(biāo)組成點(diǎn)云輸出。

2 穩(wěn)健自適應(yīng)點(diǎn)云聚類方法

基于雷達(dá)參數(shù)的穩(wěn)健自適應(yīng)點(diǎn)云聚類方法流程如圖2所示，主要包括以下幾個步驟。

步驟1將點(diǎn)云數(shù)據(jù)以(r，θ，φ)的體素形式表示[17]，r、θ、φ分別為點(diǎn)云數(shù)據(jù)的距離、方位角、俯仰角信息，單位分別為距離分辨率、方位角分辨率和俯仰角分辨率。

步驟2計算基于雷達(dá)參數(shù)的局部度量值，用于后續(xù)確定搜索區(qū)域。

步驟3結(jié)合遺傳算法確定方位角和俯仰角方向搜索單元數(shù)的調(diào)整因子。

步驟4確定橢球體搜索區(qū)域。

步驟5標(biāo)記核心點(diǎn)、邊界點(diǎn)以及離群點(diǎn)，完成聚類。在整個聚類流程中，針對毫米波雷達(dá)點(diǎn)云目標(biāo)特點(diǎn)，因此主要解決聚類中的密度準(zhǔn)則確定問題，即流程中步驟1～步驟3，其他步驟遵循標(biāo)準(zhǔn)密度聚類方法。

圖2 聚類流程圖Fig.2 Cluster flow

2.1 點(diǎn)云數(shù)據(jù)的體素表示

毫米波雷達(dá)中的觀測目標(biāo)由與天線間距離、方位角以及俯仰角確定，它在笛卡爾坐標(biāo)系中的位置可由三角函數(shù)計算得到，如圖3(a)所示。可以看出，目標(biāo)在笛卡爾坐標(biāo)系下屬于非等距采樣，兩點(diǎn)之間的最小方位角和俯仰角將隨距離的增大而增大。為了解決該問題，借助雷達(dá)的固定分辨率，將點(diǎn)云數(shù)據(jù)P(x，y，z)表示為體素形式V(r，θ，φ)，即

(4)

θ=arctan(x/y)/Δθ

(5)

φ=arcsin(z/r)/Δφ

(6)

式中：Δr、Δθ以及Δφ分別為雷達(dá)的距離、方位角以及俯仰角分辨率。具體計算公式為

(7)

(8)

(9)

式中：c0為電磁波傳播速度；B為FMCW雷達(dá)帶寬；θFOV為MIMO虛擬陣列在方位向上的視場區(qū)域；NVA為方位角方向上虛擬天線數(shù)目；φFOV為俯仰角方向上的視場區(qū)域；NVB為俯仰角方向上的虛擬天線數(shù)目。最終體素表示如圖3(b)所示。

2.2 聚類搜索區(qū)域確定

由于在距離方向上兩點(diǎn)之間的最小距離固定，因此在建立體素表示的基礎(chǔ)上，只需要計算基于雷達(dá)方位角和俯仰角分辨率的局部度量值，用于后續(xù)聚類搜索區(qū)域的確定。體素V(r，θ，φ)方位角局部度量值ci，j以及俯仰角局部度量值ci，k分別表示為

ci，j=rcos(Δφ)sin(Δθ)

(10)

ci，k=rsin(Δφ)

(11)

得到局部度量值后，角度方向的聚類搜索單元數(shù)可確定為

(12)

(13)

式中：wi，j、wi，k分別為方位角和俯仰角方向上的搜索單元數(shù)目；f1、f2分別為搜索單元數(shù)調(diào)整因子，用于調(diào)整搜索單元數(shù)個數(shù)。

最后得到用于聚類的橢球體搜索區(qū)域，表示為

(14)

式(14)中：g為距離方向的搜索單元數(shù)目；(ro，θo，φo)為橢球體的中心點(diǎn)，即當(dāng)前觀測點(diǎn)；(r，θ，φ)為搜索區(qū)域內(nèi)的點(diǎn)，即待聚類點(diǎn)。橢球體搜索區(qū)域如圖4所示。

與基于球體搜索區(qū)域的聚類方法相比，該方法在已知雷達(dá)分辨率的基礎(chǔ)上，能夠根據(jù)毫米波雷達(dá)點(diǎn)云的分布特點(diǎn)對橢球體搜索區(qū)域的長短軸進(jìn)行調(diào)整，使其更加適用于雷達(dá)點(diǎn)云數(shù)據(jù)。

2.3 聚類參數(shù)的自適應(yīng)學(xué)習(xí)

上述基于雷達(dá)參數(shù)的聚類搜索區(qū)域確定方法盡管能夠應(yīng)用于密度不一的點(diǎn)云目標(biāo)，并實現(xiàn)穩(wěn)健聚類，然而需要人工輸入各種參數(shù)g、f1、f2，因此，提出結(jié)合遺傳算法的自適應(yīng)聚類方法，以實現(xiàn)基于數(shù)據(jù)的參數(shù)自主學(xué)習(xí)。

遺傳算法通過數(shù)學(xué)的方式，利用計算機(jī)仿真運(yùn)算，將問題的求解過程轉(zhuǎn)換成類似生物進(jìn)化中的染色體基因的交叉、變異等過程。在求解較為復(fù)雜的組合優(yōu)化問題時，相對一些常規(guī)的優(yōu)化算法，通常能夠較快地獲得較好的優(yōu)化結(jié)果。遺傳算法在搜索進(jìn)化過程中一般不需要其他外部信息，僅用適應(yīng)度函數(shù)來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。因此，適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求，這也直接影響到遺傳算法的性能。

圖3 3D點(diǎn)云的體素表示Fig.3 Voxel representation of point cloud

圖4 橢球體搜索區(qū)域Fig.4 Search area of ellipsoid

2.3.1 遺傳算法的適應(yīng)度函數(shù)

進(jìn)化論中的適應(yīng)度，是表示某一個體對環(huán)境的適應(yīng)能力，也表示該個體繁殖后代的能力。適應(yīng)度高的，即優(yōu)秀的個體有更大的概率參與繁衍，遺傳自己的基因。這里，將聚類性能評價中的輪廓系數(shù)以及聚類后各個目標(biāo)點(diǎn)云數(shù)據(jù)間的相似度結(jié)合作為適應(yīng)度函數(shù)，將聚類后各目標(biāo)間分離度以及各目標(biāo)內(nèi)部聚合度和相似度作為綜合考慮指標(biāo)，相應(yīng)的適應(yīng)度函數(shù)越大，表明聚類效果越好，此時的各參數(shù)也越接近最佳要求。下面將簡單介紹輪廓系數(shù)以及數(shù)據(jù)相似度。

1) 輪廓系數(shù)

輪廓系數(shù)[18](silhouette coefficient， SC)是聚類效果好壞的一種評價指標(biāo)，可以理解為描述聚類后各個類別的輪廓清晰度的指標(biāo)。它結(jié)合內(nèi)聚度和分離度兩種因素：內(nèi)聚度反映觀測體素與類內(nèi)其他體素的緊密程度，分離度反映觀測體素與類外體素的分離程度。

定義體素Vi的內(nèi)聚度為a(i|g，f1，f2)，計算方式為

(15)

式(15)中：j為與體素Vi在同一類內(nèi)的其他體素；distance為體素Vi與Vj的距離；n為同一類內(nèi)體素個數(shù)，因此a(i|g，f1，f2)越小表示該類越緊密。此外，再定義分離度為b(i|g，f1，f2)，計算方式與a(i|g，f1，f2)類似，只不過需要遍歷其他類簇得到多個值b1(i|g，f1，f2)，b2(i|g，f1，f2)，…，bm(i|g，f1，f2)，并從中選擇最小的值作為最終的分離度。

由此，體素Vi的輪廓系數(shù)表示為

(16)

由式(16)可知，輪廓系數(shù)的取值范圍為[-1，1]，越接近1表示聚類效果相對較優(yōu)。最后將所有點(diǎn)的輪廓系數(shù)求平均，即為聚類結(jié)果總的輪廓系數(shù)，表示為

(17)

式(17)中：N為體素總數(shù)。

2) 數(shù)據(jù)相似度

類內(nèi)樣本間相似度矩陣表示為

Wij|g，f1，f2=Wji|g，f1，f2

(18)

式(18)中：KNN(Vi)為體素Vi的鄰域；Wij為體素Vi與體素Vj的相似度，由高斯距離計算得到。相似度矩陣對應(yīng)的度矩陣D表示為

(19)

可以看出，度矩陣D為相似度矩陣每一行元素之和，且為N×N的對角矩陣。在這里，將度矩陣D的跡定義為數(shù)據(jù)相似度，記為sim，數(shù)據(jù)相似度越大，則表明樣本間相似度越高。

3) 適應(yīng)度函數(shù)

為了更加全面地評估聚類效果，將適應(yīng)度函數(shù)表示為輪廓系數(shù)與數(shù)據(jù)相似度之和，即

fitness(g，f1，f2)=Sall(g，f1，f2)+

(20)

式(20)中：g、f1、f2分別為橢球體搜索區(qū)域內(nèi)距離、方位角、俯仰角方向上的搜索單元數(shù)調(diào)整因子；fitness(g，f1，f2)為適應(yīng)度；Sall(g，f1，f2)為樣本總輪廓系數(shù)；K為聚類所得目標(biāo)個數(shù)；simk(g，f1，f2)為第k個目標(biāo)內(nèi)部點(diǎn)云數(shù)據(jù)間相似度。

2.3.2 結(jié)合遺傳算法自適應(yīng)求解聚類參數(shù)

遺傳算法評價解的好壞取決于該解的適應(yīng)度值，這正體現(xiàn)了“優(yōu)勝劣汰”的特點(diǎn)。在完成適應(yīng)度函數(shù)選取后，自適應(yīng)求解聚類參數(shù)分為以下幾個步驟[19]。

步驟1為了確保遺傳種群的多樣性，隨機(jī)初始化一個種群，作為問題的初代解，將前文中的調(diào)整因子g、f1、f2作為遺傳算法的個體。

步驟2將個體編碼為二進(jìn)制數(shù)據(jù)(對應(yīng)染色體)。

步驟3根據(jù)適應(yīng)度函數(shù)對個體進(jìn)行適應(yīng)程度評估，基于評估結(jié)果從群體中選擇優(yōu)勝的個體。

步驟4將選擇的兩個個體的部分結(jié)構(gòu)加以替換重組以及以一定的變異率隨機(jī)改變個體的其中一位或多位數(shù)值，即交叉變異操作。

步驟5當(dāng)最優(yōu)個體的適應(yīng)度達(dá)到給定的閾值，或者最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升/下降時，或者迭代次數(shù)達(dá)到預(yù)設(shè)的代數(shù)時得到最佳調(diào)整因子g、f1、f2以及聚類結(jié)果。

算法偽代碼如表1所示。

通過對于遺傳算法的應(yīng)用，聚類過程中的所需超參數(shù)不再是人工選取，而是通過輪廓系數(shù)和數(shù)據(jù)相似度結(jié)合的雙重評價指標(biāo)來進(jìn)行擇優(yōu)選取，避免了人為因素造成的聚類誤差，使得超參數(shù)的選取具有更強(qiáng)的可解釋性。

表1 穩(wěn)健自適應(yīng)聚類算法偽代碼Table 1 Pesudocode of robust and adaptive clustering algorithm

3 實驗數(shù)據(jù)及結(jié)果分析

為了驗證該算法的有效性，進(jìn)行了多次實驗并獲取了相應(yīng)的雷達(dá)點(diǎn)云數(shù)據(jù)。實驗所用毫米波雷達(dá)為TI公司的IWR6843，IWR6843支持水平和垂直方向各120°的視角。由于實驗場景中的最大測量距離為6 m，采樣頻率一般取3 000 ksps以上，其中，ksps(kilo sample per second)為采樣頻率單位，表示每秒鐘采樣點(diǎn)的數(shù)量。因此根據(jù)Rmax=fsc/(2K)計算得到頻率斜率K。對于IWR6843的參數(shù)配置如表2所示。

表2 IWR6843參數(shù)配置Table 2 Parameter configuration of IWR6843

測量時安置在距地面高度為2 m處，下傾角為30°，這樣雷達(dá)的主波束斜向下能照射到人的頭，軀干和腳，可以形成比較豐富的點(diǎn)云。實驗所用測試場景分別為2、3、5個人體目標(biāo)，同時將兩幀數(shù)據(jù)合并以顯示更全面的人體目標(biāo)。

目標(biāo)數(shù)為兩個時的聚類結(jié)果如圖5所示。圖5(a)為實驗場景，圖5(b)為經(jīng)過雷達(dá)信號處理后體素表示形式下的未聚類點(diǎn)云數(shù)據(jù)，圖5(c)為經(jīng)過點(diǎn)云過濾[20]后笛卡爾坐標(biāo)系下DBSCAN聚類結(jié)果，圖5(d)為笛卡爾坐標(biāo)系下GA-DBSCAN聚類結(jié)果。從圖5(c)中可以看到，DBSCAN的聚類結(jié)果中產(chǎn)生了一個虛假目標(biāo)(藍(lán)色標(biāo)記)，這是由于DBSCAN在各個距離處的搜索區(qū)域都是大小相同的球體，而在圖5(d)中，GA-DBSCAN根據(jù)距離的不同，近處的搜索橢球體相對較小，遠(yuǎn)處的相對較大，結(jié)合密度擴(kuò)展準(zhǔn)則，能夠有效解決虛假目標(biāo)的問題。

圖5 兩個目標(biāo)的聚類結(jié)果Fig.5 Cluster results for two targets

目標(biāo)數(shù)為3時的聚類結(jié)果如圖6所示。盡管DBSCAN的聚類結(jié)果目標(biāo)數(shù)為3，然而對于目標(biāo)3(藍(lán)色標(biāo)記)的聚類與實際數(shù)據(jù)存在較大偏差，有一部分人體目標(biāo)的點(diǎn)云被聚類為虛假目標(biāo)(黑色標(biāo)記)。這是因為目標(biāo)較遠(yuǎn)時，點(diǎn)云在角度方向上分布較為稀疏，而DBSCAN在聚類過程中搜索半徑是固定不變的，因此會存在圖5(c)所示的問題。在圖5(d)中，GA-DBSCAN在目標(biāo)距離雷達(dá)較遠(yuǎn)時，其俯仰角搜索區(qū)域也相應(yīng)地增大，以達(dá)到對遠(yuǎn)疏近密的毫米波點(diǎn)云的有效聚類。

目標(biāo)數(shù)為5時的聚類結(jié)果如圖7所示。觀察圖7(c)可知，DBSCAN存在與圖6相同的問題，而GA-DBSCAN則可以有效解決該問題。

綜合圖5～圖7的實驗結(jié)果可知，對于遠(yuǎn)疏近密、扇形分布的毫米波雷達(dá)點(diǎn)云，原始DBSCAN聚類在固定搜索區(qū)域的限制條件下，即對于不同距離處的目標(biāo)均采用統(tǒng)一搜索半徑。對于單個近距離人體目標(biāo)，其對應(yīng)雷達(dá)點(diǎn)云分布較密集，占據(jù)了雷達(dá)視場中的多個或離散或連續(xù)的角度單元中，而遠(yuǎn)距離目標(biāo)則只分布在較少的幾個角度單元中。因此，當(dāng)搜索半徑單元數(shù)較小時，近處的單個目標(biāo)可能會被聚類為多個目標(biāo)；當(dāng)搜索半徑單元數(shù)較大時，遠(yuǎn)處的多個目標(biāo)則可能會被聚類為單個目標(biāo)。而結(jié)合遺傳算法的穩(wěn)健自適應(yīng)橢圓聚類算法能夠根據(jù)數(shù)據(jù)特點(diǎn)自主學(xué)習(xí)聚類所需參數(shù)，自適應(yīng)調(diào)節(jié)各個距離單元的搜索區(qū)域，對于近距離目標(biāo)采用較大的搜索半徑，而遠(yuǎn)距離目標(biāo)則采用較小的搜索半徑，從而實現(xiàn)穩(wěn)健聚類的目的。

4 結(jié)論

針對毫米波FMCW MIMO雷達(dá)人體目標(biāo)點(diǎn)云遠(yuǎn)疏近密這一特點(diǎn)，提出了一種結(jié)合遺傳算法的穩(wěn)健自適應(yīng)聚類方法。所得結(jié)論如下。

(1)對于密度分布不一的多個人體目標(biāo)點(diǎn)云，通過結(jié)合雷達(dá)各維度的分辨率來調(diào)節(jié)聚類時的搜索區(qū)域范圍，實現(xiàn)了對3D點(diǎn)云目標(biāo)的穩(wěn)健聚類。

圖6 3個目標(biāo)聚類結(jié)果Fig.6 Cluster results for three targets

圖7 5個目標(biāo)聚類結(jié)果Fig.7 Cluster results for five targets

(2)引入遺傳算法對聚類所需參數(shù)進(jìn)行自主學(xué)習(xí)，實現(xiàn)了對點(diǎn)云目標(biāo)的自適應(yīng)聚類。

在未來的工作中，將對無監(jiān)督信息點(diǎn)云數(shù)據(jù)的聚類評價指標(biāo)進(jìn)行進(jìn)一步的研究，以爭取得到更加準(zhǔn)確有效的聚類效果。