余渝生， 王志誠

（上海無線電設(shè)備研究所，上海200090）

0 引言

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

1 圓心半徑聚類算法

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

則點(diǎn)元B屬于目標(biāo)T。

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

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

a）對所有點(diǎn)元按能量大小排序；

b）以未被聚類的能量最大的點(diǎn)元為圓心，以預(yù)期目標(biāo)最大尺寸的一半為聚類半徑；

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

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

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

2 邊緣聚類算法

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

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

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

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

a）從檢測平面中檢測出一個新的待聚類的點(diǎn)元；

b）判斷當(dāng)前是否有類屬可以進(jìn)行聚類，若當(dāng)前沒有類屬，則生成一個類屬，并對該類屬進(jìn)行初始化，將該類邊緣的四個點(diǎn)的坐標(biāo)置為該點(diǎn)元的坐標(biāo)，然后進(jìn)行下一個點(diǎn)元的檢測；

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

d）若待聚類點(diǎn)元不屬于當(dāng)前任何類屬，則生成一個新類，并對該類進(jìn)行初始化，將該類邊緣的四個點(diǎn)的坐標(biāo)置為該點(diǎn)元的坐標(biāo)；

e）重復(fù)以上四個步驟，直到整個檢測平面遍歷結(jié)束。

3 逐點(diǎn)聚類算法

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

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

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

圖3 逐點(diǎn)聚類算法原理示意圖

（1）當(dāng)前查詢點(diǎn)無任何類屬

若當(dāng)前查詢點(diǎn)無任何類屬，則算法不進(jìn)行任何操作，直接查詢下一個點(diǎn)。

（2）當(dāng)前查詢點(diǎn)具有類屬

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

（3）所有查詢點(diǎn)均無類屬

若查詢的所有點(diǎn)都無類屬，則算法將待聚類點(diǎn)元設(shè)為一個新的類屬。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結(jié)

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

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

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

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

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