雷達點元聚類算法性能的比較與分析

余渝生， 王志誠

（上海無線電設備研究所，上海200090）

0 引言

在高分辨雷達體制下，真實目標的雷達回波將覆蓋多個距離-多普勒分辨單元，形成若干雷達點元。若以點元為單位進行目標檢測和識別，則會將真實目標識別為多個目標。因此，需要對檢測到的所有點元進行聚類。點元聚類是指將所有檢測到的屬于一個真實目標的雷達點元進行歸類的操作。雷達點元聚類不僅有助于降低檢測虛警概率，同時有助于真實目標的識別以及目標跟蹤點的選取。點元聚類應同時具有完備性和排他性，即在將所有屬于同一目標的點元歸為一類的同時，將不屬于該目標的點元排除。本文主要介紹了三種點元聚類常用的算法：圓心半徑聚類算法、邊緣聚類算法和逐點聚類算法，并對這三種算法的聚類效果以及聚類時間進行了比較。

1 圓心半徑聚類算法

圓心半徑聚類算法是一種較簡單的聚類算法，該算法將雷達目標視為一個圓，以其圓心和半徑進行聚類。如圖1所示，假設目標T 中被設為圓心的點元A 在距離 -多普勒二維檢測平面（簡稱：檢測平面，下同）內(nèi)的坐標為（xA，yA），某個待聚類的點元B在檢測平面內(nèi)的坐標為（xB，yB），再假設目標T 的半徑為R。若點元A 與點元B之間的距離滿足關系式：

則點元B屬于目標T。

圖1 圓心半徑聚類算法原理示意圖

在實際處理中，圓心半徑聚類算法通常將雷達回波能量最大的點元作為圓心進行點元聚類。因此，需要將所有點元按照能量大小進行排序。然后按照能量從大到小的順序?qū)κＯ碌狞c元進行聚類。圓心半徑聚類算法的具體流程：

a）對所有點元按能量大小排序；

b）以未被聚類的能量最大的點元為圓心，以預期目標最大尺寸的一半為聚類半徑；

c）遍歷剩下的點元，查詢這些點元與圓心之間的距離是否滿足式（1），若滿足則將其與圓心歸為一類，同時更新該類的屬性；

d）重復b）、c）兩個步驟，直到檢測平面內(nèi)的所有點元都被聚類。

圓心半徑聚類算法的優(yōu)點是原理簡單，易于實施。但該算法存在聚類半徑不可調(diào)，聚類形狀單一以及無法邊檢測邊聚類等缺點，無法完成復雜目標的聚類處理。

2 邊緣聚類算法

邊緣聚類算法是基于圓心半徑聚類算法的改進算法。該算法以當前類屬的邊緣為基準進行聚類，隨著聚類點元的增加，當前類屬的邊緣會不斷向外擴展，能夠有效地對復雜目標聚類。在實際操作中，當前類屬的邊緣由四個邊緣點表示，邊緣點的坐標分別由該類屬中的所有點元在距離維和頻率維上的最大值和最小值組成，分別為（xmin，ymin）、（xmax，ymin）、（xmin，ymax）、（xmax，ymax）。邊緣聚類算法具備邊檢測邊聚類的能力，無需等待點元檢測操作完成，聚類效率較高。圖2給出了邊緣聚類算法的示意圖。

圖2 邊緣聚類算法原理示意圖

圖2 中，虛線框表示當前的聚類范圍，E1、E2、E3和E4表示類屬范圍的邊緣點。待聚類的點元分別計算與這四個類屬邊緣點之間的距離。若任意一段距離小于等于設定門限，則待聚類點元屬于當前類屬。若該點元被聚類入當前的類屬，則立即對當前類屬的邊緣點進行更新，為下一次聚類做準備。

邊緣聚類算法的具體流程：

a）從檢測平面中檢測出一個新的待聚類的點元；

b）判斷當前是否有類屬可以進行聚類，若當前沒有類屬，則生成一個類屬，并對該類屬進行初始化，將該類邊緣的四個點的坐標置為該點元的坐標，然后進行下一個點元的檢測；

c）若當前有類屬，則將待聚類點元與當前所有類屬的邊緣進行逐一比較，若滿足聚類條件，則將該點元歸為某個類屬，若該點元在聚類為某個類屬的同時已經(jīng)具有自己的類屬，且兩個類屬不相同，那么將這兩個類屬合并為一個類屬；

d）若待聚類點元不屬于當前任何類屬，則生成一個新類，并對該類進行初始化，將該類邊緣的四個點的坐標置為該點元的坐標；

e）重復以上四個步驟，直到整個檢測平面遍歷結束。

3 逐點聚類算法

圓心半徑聚類算法和邊緣聚類算法都是以待聚類點元與參考點之間的聚類為依據(jù)進行聚類的。與這兩類算法不同，逐點聚類算法是以待聚類點周邊其它點元的類屬情況為依據(jù)進行聚類的，即對待聚類點元周邊一定區(qū)域內(nèi)的點元的類屬情況進行查詢。查詢的范圍和數(shù)量決定了聚類的范圍和形狀，聚類靈活性高。

逐點聚類算法需遍歷查詢待聚類點元周邊指定區(qū)域和數(shù)量的點元的類屬情況，并以此為依據(jù)對待聚類點元的類屬進行判定。

如圖3所示，原點o 上的空心點為待聚類點元，實心點為待查詢的點元。算法對實心點的類屬情況進行遍歷查詢。根據(jù)查詢結果，分三種情況對待聚類點元的類屬進行判定。分別以該點的坐標為基準，去查詢其周圍的規(guī)定范圍的點的類屬，每查詢一個點，進行一次處理。

圖3 逐點聚類算法原理示意圖

（1）當前查詢點無任何類屬

若當前查詢點無任何類屬，則算法不進行任何操作，直接查詢下一個點。

（2）當前查詢點具有類屬

若當前查詢點有類屬，則算法根據(jù)待聚類點元的類屬情況，進行聚類操作。若待聚類點元沒有類屬，則將當前查詢點的類屬賦予待聚類點元；若待聚類點元有類屬，但與查詢點的類屬不同，則將查詢點的類屬賦予待聚類點元所在類屬的所有點；若待聚類點元與查詢點元的類屬相同，則不進行任何操作，直接查詢下一個點。

（3）所有查詢點均無類屬

若查詢的所有點都無類屬，則算法將待聚類點元設為一個新的類屬。

4 三種聚類算法的仿真與比較

采用模擬回波數(shù)據(jù)和真實回波數(shù)據(jù)分別對三種聚類算法進行驗證。從聚類效果和聚類時間兩個方面進行比較和評估。

4.1 模擬回波數(shù)據(jù)驗證

利用模擬回波數(shù)據(jù)，在三種仿真狀態(tài)下對聚類算法進行驗證。對三種算法在軟件優(yōu)化和未優(yōu)化兩種情況下的聚類效果和聚類時間進行了對比。每種狀態(tài)均包含100個點元，由此形成的目標個數(shù)在三種狀態(tài)下分別為2 個、3 個和5 個。表1列出了三種仿真狀態(tài)下的模擬回波數(shù)據(jù)規(guī)格。

表1 三種仿真狀態(tài)下的模擬回波數(shù)據(jù)規(guī)格

（1）仿真狀態(tài)Ⅰ

仿真狀態(tài)Ⅰ包含2個目標，分別包含96個點元和4個點元。圖4給出了仿真狀態(tài)Ⅰ的模擬回波數(shù)據(jù)示意圖。表2列出了三種聚類算法對該仿真狀態(tài)Ⅰ中點元的聚類結果。

圖4 仿真狀態(tài)Ⅰ模擬回波數(shù)據(jù)示意圖

在仿真狀態(tài)Ⅰ下，圓心半徑聚類算法將較大的目標聚類為幾個小目標，聚類效果不理想；而邊緣聚類算法和逐點聚類算法能夠有效地聚類。從表2 中可以看出，逐點聚類算法的聚類時間較長。

表2 三種聚類算法對仿真狀態(tài)Ⅰ的聚類結果

（2）仿真狀態(tài)Ⅱ

仿真狀態(tài)Ⅱ包含3個目標，其中2個目標各包含48個點元，一個目標包含4個點元。圖5給出了仿真狀態(tài)Ⅱ的模擬回波數(shù)據(jù)示意圖。

表3列出了三種聚類算法對該仿真狀態(tài)Ⅱ中點元的聚類結果。

在仿真狀態(tài)Ⅱ下，圓心半徑聚類算法仍將大的目標聚類為多個小目標，效果仍不理想。邊緣聚類算法和逐點聚類算法仍能夠有效地聚類，但逐點聚類算法的聚類時間仍較長。

圖5 仿真狀態(tài)Ⅱ模擬回波數(shù)據(jù)示意圖

表3 三種聚類算法對仿真狀態(tài)Ⅱ的聚類結果

（3）仿真狀態(tài)Ⅲ

仿真狀態(tài)Ⅲ包含5個目標，其中4個目標各包含24個點元，一個目標包含4個點元。圖6給出了仿真狀態(tài)Ⅲ的模擬回波數(shù)據(jù)示意圖。

表4列出了三種聚類算法對該仿真狀態(tài)Ⅲ中點元的聚類結果。

圖6 仿真狀態(tài)Ⅲ模擬回波數(shù)據(jù)示意圖

表4 三種聚類算法對仿真狀態(tài)Ⅲ的聚類結果

在仿真狀態(tài)Ⅲ下，隨著目標中點元數(shù)量的減少，圓心半徑聚類算法的聚類效果變好，且聚類時間與邊緣聚類算法相當。另外，邊緣聚類算法和逐點聚類算法仍能夠有效地聚類，其中逐點聚類算法的聚類時間仍較長。

通過對以上三種仿真狀態(tài)的驗證發(fā)現(xiàn)，圓心半徑聚類算法對于點元數(shù)量較多的目標不能夠有效地聚類，而當目標所包含的點元數(shù)量減小到一定范圍后，聚類效果變好。邊緣聚類算法和逐點聚類算法均能有效聚類。在聚類時間方面，三種仿真狀態(tài)下，邊緣算法的聚類時間最短，圓心半徑聚類算法次之，逐點聚類算法最長。因此，逐點聚類算法不適于對實時性要求高的系統(tǒng)。

圖7 真實回波數(shù)據(jù)平面三維視圖

4.2 真實回波數(shù)據(jù)驗證

采用真實雷達回波數(shù)據(jù)對三種聚類算法進行仿真。該數(shù)據(jù)為某型號雷達在進行抗箔條試驗時所采集的艦船和箔條的回波數(shù)據(jù)。圖7、圖8 給出了該數(shù)據(jù)的“頻率-距離-強度”三維視圖以及“頻率-距離”平面視圖。

從圖7、圖8中可以看出，數(shù)據(jù)中含有兩個目標。通過對該數(shù)據(jù)進行恒虛警檢測，得到20個點元。其中，箔條目標包含18個點元；艦船目標包含2個點元。在驗證時，將圓心半徑聚類算法的聚類半徑設為10個點元；將邊緣聚類算法的距離門限設為10個點元；將逐點聚類算法的查詢點總數(shù)設為26點。下面給出三種聚類算法的聚類結果。

圖8 真實回波數(shù)據(jù)俯視圖

通過表5可以看出，三種聚類算法均能有效地聚類。其中，圓心半徑聚類算法和邊緣聚類算法的聚類時間相當，而逐點聚類算法的聚類時間則要長于前兩種聚類算法。

表5 三種算法對雷達回波數(shù)據(jù)的聚類結果

5 總結

點元聚類算法是高分辨雷達信號處理的一個重要的組成部分，較好地對檢測平面內(nèi)所檢測到的點元進行聚類是目標搜索跟蹤、目標識別以及抗干擾等處理的前提。通過以上的分析和對比發(fā)現(xiàn)，圓心半徑聚類算法由于其聚類半徑不能夠自適應地改變，不適于大型復雜目標的聚類；逐點聚類算法能夠?qū)碗s目標進行有效聚類，但其聚類時間較長，對系統(tǒng)的實時性影響較大；邊緣聚類算法能夠在較短的時間內(nèi)完成對復雜目標的聚類，聚類效果較好。

［1］ William K.Pratt.數(shù)字圖像處理（原書第三版）［M］.北京：機械工業(yè)出版社，2005.

［2］ 章毓晉.圖像處理和分析［M］.北京：清華大學出版社，1999.［3］ 趙榮椿.數(shù)字圖像處理導論［M］.西安：西北工業(yè)大學出版社，1995.

［4］ 劉書明，羅勇江.ADSP TS20XS系列DSP原理與應用設計［M］.北京：電子工業(yè)出版社，2007.

［5］ 鄭存紅，張文艷，董靜.紅外小目標聚類算法研究及DSP實現(xiàn)［C］.電子技術學術委員會，2006.