小波聚類在多目標(biāo)定位中的應(yīng)用

王 崛，劉文杰

(裝甲兵工程學(xué)院 信息工程系，北京 100072)

隨著現(xiàn)代戰(zhàn)爭(zhēng)中偵察監(jiān)視裝備的大量應(yīng)用，基于多傳感器的多目標(biāo)偵察［1-2］技術(shù)應(yīng)運(yùn)而生，這種方法有效地改善了偵察系統(tǒng)的性能，將各傳感器的信息資源進(jìn)行了整合。但要想從大量的、復(fù)雜的、變化的數(shù)據(jù)中挖掘出目標(biāo)并跟蹤并非易事，這涉及到噪聲的抑制，目標(biāo)的分割，跟蹤目標(biāo)的軌跡等一系列問(wèn)題。一種有效的方法是:應(yīng)用聚類算法解決目標(biāo)的分割以及目標(biāo)的跟蹤等問(wèn)題。目前，已經(jīng)提出的聚類方法主要有基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法等［3］。其中基于劃分方法的Kmeans 算法［3-4］在聚類算法中占有重要地位。該算法具有簡(jiǎn)便易實(shí)現(xiàn)、復(fù)雜度較低等優(yōu)點(diǎn)，但其在應(yīng)用上也明顯存在缺陷，如對(duì)于大數(shù)據(jù)集的聚類執(zhí)行效率低，不能發(fā)現(xiàn)任意形狀的簇，受孤立點(diǎn)的影響較大，需要預(yù)先指定聚類數(shù)目等等。尤其是在解決多個(gè)運(yùn)動(dòng)目標(biāo)的識(shí)別方面，這些缺陷都會(huì)使聚類的效果變差。

為克服傳統(tǒng)聚類方法在解決實(shí)際問(wèn)題上的缺陷，本文提出了一種基于小波技術(shù)［5］的聚類算法，簡(jiǎn)稱小波聚類［6-8］，并將其應(yīng)用到多傳感器的多目標(biāo)定位當(dāng)中。小波聚類是一種多分辨率的聚類算法，它首先通過(guò)在數(shù)據(jù)空間上強(qiáng)加一個(gè)多維網(wǎng)格［9-10］結(jié)構(gòu)來(lái)匯總數(shù)據(jù)，每個(gè)網(wǎng)格單元匯總了一組映射到該單元中的點(diǎn)的信息。這種匯總信息適合于在內(nèi)存中進(jìn)行多分辨率小波分析使用，以及隨后的聚類分析。在進(jìn)行小波分析時(shí)，原始數(shù)據(jù)將被變換為在不同的分辨率層次上對(duì)象間的相對(duì)距離，這使得數(shù)據(jù)的自然聚類變得更加容易區(qū)別，然后通過(guò)在新的空間中尋找高密度區(qū)域，可以確定聚類。

1 小波變換的邊緣檢測(cè)

小波變換是一種信號(hào)處理技術(shù)，小波變換的模極大值點(diǎn)對(duì)應(yīng)于信號(hào)的突變點(diǎn)，通過(guò)檢測(cè)這些模極大值點(diǎn)可以檢測(cè)到信號(hào)的突變，利用這個(gè)原理可以進(jìn)行圖像邊緣的檢測(cè)，應(yīng)用到本文就可以檢測(cè)出簇，即聚類。

假設(shè)將原始數(shù)據(jù)轉(zhuǎn)化為數(shù)字圖像數(shù)據(jù)形式后的數(shù)據(jù)為D，具有N×N 像素點(diǎn)。此時(shí)，只需要在log2m+1 個(gè)尺度上對(duì)D 進(jìn)行分解。選擇適當(dāng)?shù)亩S平滑函數(shù)θ(x，y)，定義小波構(gòu)造出離散濾波器。在尺度2j上，可以采用二維離散小波變換的快速算法進(jìn)行計(jì)算每一個(gè)點(diǎn)(n，m)的離散二進(jìn)小波變換W1.d2jf(n，m)，W2.d2j(n，m)。點(diǎn)(n，m)的模值為

假設(shè)在J 個(gè)尺度上進(jìn)行分解，在尺度s=2j(1≤j≤J)上，對(duì)可能的邊緣Pj={Pj(n，m)}，1≤n，m≤N 進(jìn)行連接處理，即將模值相近和相角相近的相鄰奇異點(diǎn)進(jìn)行連接，同時(shí)去掉長(zhǎng)度小于給定閾值的短連接，這樣就得到尺度s =2j(1≤j≤J)上的邊緣Ej={Ej(n，m)}。其中，若(n，m)為邊緣點(diǎn)，則Ej(n，m)=1;否則，Ej(n，m)=0。

在不同尺度上得到的邊緣定位精度與抗噪性是互補(bǔ)的。在大尺度上，邊緣比較穩(wěn)定，對(duì)噪聲不敏感，但是邊緣的定位精度較差;在小的尺度上，邊緣細(xì)節(jié)信息比較豐富，邊緣定位精度較高，但對(duì)噪聲比較敏感。在多尺度邊緣提取中，結(jié)合大、小尺度的優(yōu)勢(shì)，對(duì)各尺度上的邊緣圖像進(jìn)行綜合，可以得到精確的像素邊緣，也就是說(shuō)可以以不同尺度從細(xì)尺度到粗尺度來(lái)聚類，選擇怎樣的聚類尺度可由實(shí)際情況決定。

2 小波聚類算法

小波聚類算法中主要思想是首先對(duì)輸入數(shù)據(jù)進(jìn)行基于網(wǎng)格的劃分構(gòu)造類似數(shù)字圖像的數(shù)據(jù)，通過(guò)小波變換進(jìn)行邊緣檢測(cè)，檢測(cè)出簇邊界，如圖1 所示。在不同的分辨率和尺度上產(chǎn)生可以產(chǎn)生不同的簇，可根據(jù)實(shí)際情況選擇分辨率和尺度。小波聚類算法的主要步驟為:

輸入:多維數(shù)據(jù)對(duì)象

輸出:聚類對(duì)象

1)量化數(shù)據(jù)空間，然后分配對(duì)象到網(wǎng)格單元，并構(gòu)造數(shù)據(jù)對(duì)象到網(wǎng)格單元的映射表;

2)對(duì)量化后的網(wǎng)格數(shù)據(jù)單元應(yīng)用多尺度小波變換，檢測(cè)出簇的邊緣，并標(biāo)號(hào);

3)給每個(gè)單元分配簇標(biāo)號(hào);

4)根據(jù)映射表將數(shù)據(jù)對(duì)象分配到簇;

5)計(jì)算聚類中心點(diǎn)。

圖1 小波分析聚類分類演示圖

進(jìn)行小波聚類的第1 步就是給待聚類的數(shù)據(jù)空間強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)匯總數(shù)據(jù)。假設(shè)A =Al，A2，…，Ad為有限規(guī)則集。S=A1×A2×…Ad為d維數(shù)字空間或特征空間。輸入數(shù)據(jù)集為d維點(diǎn){P1，P2，…，PN}的集合，其中Pi=〈Pi1，Pi2，…，Pid〉，1≤i≤N。把所有維Ai分割為m 個(gè)間隔，間隔的大小由分辨率決定，則空間S 可以分成多個(gè)長(zhǎng)度等同連續(xù)而又不相交的單元，則稱這些單元為數(shù)據(jù)單元。每個(gè)單元的形式為〈C1，C2，…，Cd〉，其中Ci=［Li，Hi)是Ai分區(qū)間的右開區(qū)間，如果Li≤Pki≤Hi，1≤i≤d，則點(diǎn)Pk=〈Pk1，Pk2，…，Pkd〉包含在該單元中。每個(gè)單元有一個(gè)關(guān)聯(lián)它的統(tǒng)計(jì)參數(shù)記為c. param，本文中這個(gè)參數(shù)為數(shù)據(jù)單元格內(nèi)數(shù)據(jù)點(diǎn)數(shù)。從數(shù)字圖像處理的角度看，經(jīng)過(guò)這種劃分后，就將待聚類數(shù)據(jù)轉(zhuǎn)化為了類似于圖像數(shù)據(jù)的形式。

接下來(lái)進(jìn)行多尺度的小波分解，在每個(gè)尺度上檢測(cè)邊緣信息，其基本步驟為:

1)求出每一個(gè)尺度s=2j(1≤j≤J)上可能的邊緣Cj={Cj(n，m)};

2)對(duì)CJ={CJ(n，m)}進(jìn)行連接處理，得到尺度2J上的邊緣EJ={EJ(n.m)}，并令j=J;

3)針對(duì)尺度2j的邊緣點(diǎn)(n，m)，把Cj-1在以點(diǎn)(n，m)為中心的3 ×3 像素區(qū)域內(nèi)所有可能的邊緣點(diǎn)均標(biāo)成尺度2j-1上的候選邊緣點(diǎn);

4)對(duì)尺度2j-1上的所有候選邊緣點(diǎn)進(jìn)行連接處理，得到尺度Ej-1上的邊緣Ej-1，并令j=j-1;

5)重復(fù)步驟3)與4)，直到j(luò)=1，邊緣E1就是綜合得到的簇邊界;

最后對(duì)小波變換檢測(cè)出的簇進(jìn)行標(biāo)號(hào)，給簇內(nèi)每個(gè)單元分配簇標(biāo)號(hào)，根據(jù)之前建立的單元格與數(shù)據(jù)對(duì)象之間的映射表，確定對(duì)象所屬的聚類。采用算術(shù)平均法計(jì)算聚類中心，即

其中:n 為簇內(nèi)點(diǎn)的個(gè)數(shù);Xi為簇內(nèi)點(diǎn)坐標(biāo)。

3 仿真實(shí)驗(yàn)及分析

Matlab 是一套功能非常強(qiáng)大的商業(yè)數(shù)學(xué)軟件，從信號(hào)處理、語(yǔ)音處理、數(shù)據(jù)采集、數(shù)值運(yùn)算、圖像處理到電子仿真，金融分析等等，幾乎在各個(gè)工業(yè)領(lǐng)域，它都已經(jīng)得到了廣泛應(yīng)用，同時(shí)也取得了巨大的成功。但是，由于Matlab 是用一種腳本語(yǔ)言，他的解釋是逐行執(zhí)行的，程序中所有的變量都是用MxArray 來(lái)實(shí)現(xiàn)的，所以為了保證通用性，它的執(zhí)行效率非常低，常常看到:在開發(fā)一些復(fù)雜的算法時(shí)，通常會(huì)發(fā)現(xiàn)程序執(zhí)行得特別慢，雖然Mathworks 公司已經(jīng)在竭力提高m 腳本文件(script files)的運(yùn)算速度，但目前為止效果仍然不能和實(shí)現(xiàn)同樣功能的可執(zhí)行程序相比。

基于上述考慮，本文將利用Matlab 提供的C/C ++編譯器，將m 文件編譯成可執(zhí)行的應(yīng)用程序，使用的編譯環(huán)境是MS VC++ 6.0 和Matlab6.5。針對(duì)靜態(tài)多目標(biāo)和動(dòng)態(tài)多目標(biāo)偵察2 種不同的情況，本文進(jìn)行2 次測(cè)試，2 組測(cè)試數(shù)據(jù)分別為:

第1 組:靜態(tài)目標(biāo)，有10 000個(gè)數(shù)據(jù)點(diǎn)，目標(biāo)數(shù)目為100，并給出100 個(gè)目標(biāo)中心點(diǎn)坐標(biāo)，該數(shù)據(jù)樣本具有不規(guī)則的簇分布，且含有噪聲點(diǎn);

第2 組:動(dòng)態(tài)目標(biāo)，有兩批數(shù)據(jù)點(diǎn)，假設(shè)時(shí)間(t -t +Δt)時(shí)，有10 000個(gè)數(shù)據(jù)點(diǎn)，目標(biāo)數(shù)目為100，并給出100 個(gè)目標(biāo)中心點(diǎn)坐標(biāo);(t+Δt，t+2Δt)時(shí)，有1000個(gè)數(shù)據(jù)點(diǎn)，目標(biāo)數(shù)目為100，并給出100 個(gè)目標(biāo)中心點(diǎn)坐標(biāo)。該數(shù)據(jù)樣本具有不規(guī)則的簇分布，且含有噪聲點(diǎn);

仿真測(cè)試在聯(lián)想y4 60 2.5GHz CPU 環(huán)境下進(jìn)行。首先分別利用Kmeans 算法和Wavecluster 進(jìn)行靜態(tài)多目標(biāo)定位，獲取目標(biāo)位置信息，選定的參數(shù)為:初始聚類數(shù)目K =100，分辨率resolution=1，數(shù)據(jù)維度Dimensions=2，采用的小波為二進(jìn)小波。其結(jié)果如表1 所示。

表1 靜態(tài)多目標(biāo)定位結(jié)果

從表1 中可以看出，相比于傳統(tǒng)的Kmeans 算法，Wavecluster 算法在處理簇分布不均勻、含有噪聲的大規(guī)模數(shù)據(jù)集時(shí)，聚類結(jié)果更加精確和細(xì)致。

然后利用基于時(shí)間窗口的Kmeans 算法和Wavecluster算法進(jìn)行動(dòng)態(tài)多目標(biāo)定位，獲取目標(biāo)位置信息，選定的參數(shù)為:初始聚類數(shù)目K =100，分辨率resolution =1，數(shù)據(jù)維度Dimensions=2，時(shí)間窗口W = Δt，采用的小波為二進(jìn)小波。其結(jié)果如表2 所示。

表2 動(dòng)態(tài)多目標(biāo)定位結(jié)果

從表2 中可以看出，Wavecluster 算法在進(jìn)行數(shù)據(jù)流聚類時(shí)，可以進(jìn)行自動(dòng)聚類，且具有較高的聚類精度;而傳統(tǒng)的Kmeans 算法在處理數(shù)據(jù)流時(shí)需要指定時(shí)間窗口W，W 的選擇直接影響著定位精度，而目前W 的選擇并沒(méi)有通用且有效的方法。

在Wavecluster 算法當(dāng)中，參數(shù)resolution 表示分辨率，也即網(wǎng)格單元粒度，它的值與樣本在各維度上的值有關(guān)。如果resolution 值較大，網(wǎng)格單元就會(huì)較大，那么得到的聚類的精度就較低。反之，得到的聚類的精度就較高，但是算法的計(jì)算復(fù)雜度會(huì)較大。通過(guò)表3 可以看到在不同resolution 下的聚類效果，測(cè)試數(shù)據(jù)為第1 組數(shù)據(jù)。

表3 在不同分辨率下的Wavecluster 定位結(jié)果

通過(guò)以上仿真測(cè)試可以看出，相比較Kmeans 聚類算法，Wavecluster 算法具有較大優(yōu)勢(shì)，主要有:一是可以自動(dòng)確定聚類數(shù)目，二是可以有效去除噪聲對(duì)聚類結(jié)果的影響并發(fā)現(xiàn)任意形狀的簇，三是在處理數(shù)據(jù)流聚類問(wèn)題時(shí)可以自動(dòng)聚類。

4 結(jié)束語(yǔ)

本文提出了基于小波聚類的多目標(biāo)分群算法，仿真試驗(yàn)結(jié)果證明了該方法的可行性和有效性。此方法先把原始數(shù)據(jù)進(jìn)行量化，形成矩陣數(shù)據(jù)，然后在該矩陣數(shù)據(jù)形式中實(shí)施小波變換檢測(cè)出簇的邊緣，并為每個(gè)簇添加標(biāo)簽，然后通過(guò)算法提供的映射表確定原始數(shù)據(jù)集中的各數(shù)據(jù)點(diǎn)所屬的聚類，最后計(jì)算定位中心。該聚類方法在性能和效率上比傳統(tǒng)的聚類算法有較大的改進(jìn)，對(duì)于多傳感器的多目標(biāo)偵察研究有著極大的借鑒意義，此外，由于該算法基于網(wǎng)格的特性，可以解決數(shù)據(jù)流據(jù)類的大數(shù)據(jù)量問(wèn)題。但是該方法也存在一定的局限性，如分辨率的選擇以及處理二維以上數(shù)據(jù)等問(wèn)題，還需在今后的工作中進(jìn)一步研究。

［1］張晶煒，劉永，熊偉.多傳感器多目標(biāo)跟蹤算法性能分析［J］.現(xiàn)代雷達(dá)，2004，26(3):37-39.

［2］楊國(guó)盛，竇麗華.多傳感器多目標(biāo)定位與跟蹤技術(shù)研究［J］.火力與指揮控制，2002，27(1):30-32.

［3］姜園，張朝陽(yáng).用于數(shù)據(jù)挖掘的聚類算法［J］.電子與信息學(xué)報(bào)，2005，27(4):655-661.

［4］徐義峰，陳春明，徐云青.一種改進(jìn)的k-均值聚類算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2008，25(3):275-277.

［5］何承偉.基于小波變換的目標(biāo)機(jī)動(dòng)檢測(cè)［D］.太原:太原理工大學(xué)，2007.

［6］黃文佳.基于小波的腫瘤基因表達(dá)數(shù)據(jù)聚類分析模型［J］.上海大學(xué)學(xué)報(bào)，2011，17(5):625-630.

［7］李云，劉學(xué)誠(chéng). 小波聚類在算法在入侵檢測(cè)中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用與軟件，2010，27(6):103-125.

［8］畢玲.小波聚類算法的研究及應(yīng)用［D］.大連:大連理工大學(xué)，2006.

［9］孫玉芬.基于網(wǎng)格方法的聚類算法研究［D］.武漢:華中科技大學(xué)，2006.

［10］張西芝，姬波，邱保志. 基于網(wǎng)格的多密度聚類算法［D］.鄭州:鄭州大學(xué)，2009.