小波聚類在多目標定位中的應用

王 崛，劉文杰

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

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

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

1 小波變換的邊緣檢測

小波變換是一種信號處理技術，小波變換的模極大值點對應于信號的突變點，通過檢測這些模極大值點可以檢測到信號的突變，利用這個原理可以進行圖像邊緣的檢測，應用到本文就可以檢測出簇，即聚類。

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

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

在不同尺度上得到的邊緣定位精度與抗噪性是互補的。在大尺度上，邊緣比較穩定，對噪聲不敏感，但是邊緣的定位精度較差;在小的尺度上，邊緣細節信息比較豐富，邊緣定位精度較高，但對噪聲比較敏感。在多尺度邊緣提取中，結合大、小尺度的優勢，對各尺度上的邊緣圖像進行綜合，可以得到精確的像素邊緣，也就是說可以以不同尺度從細尺度到粗尺度來聚類，選擇怎樣的聚類尺度可由實際情況決定。

2 小波聚類算法

小波聚類算法中主要思想是首先對輸入數據進行基于網格的劃分構造類似數字圖像的數據，通過小波變換進行邊緣檢測，檢測出簇邊界，如圖1 所示。在不同的分辨率和尺度上產生可以產生不同的簇，可根據實際情況選擇分辨率和尺度。小波聚類算法的主要步驟為:

輸入:多維數據對象

輸出:聚類對象

1)量化數據空間，然后分配對象到網格單元，并構造數據對象到網格單元的映射表;

2)對量化后的網格數據單元應用多尺度小波變換，檢測出簇的邊緣，并標號;

3)給每個單元分配簇標號;

4)根據映射表將數據對象分配到簇;

5)計算聚類中心點。

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

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

接下來進行多尺度的小波分解，在每個尺度上檢測邊緣信息，其基本步驟為:

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

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

3)針對尺度2j的邊緣點(n，m)，把Cj-1在以點(n，m)為中心的3 ×3 像素區域內所有可能的邊緣點均標成尺度2j-1上的候選邊緣點;

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

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

最后對小波變換檢測出的簇進行標號，給簇內每個單元分配簇標號，根據之前建立的單元格與數據對象之間的映射表，確定對象所屬的聚類。采用算術平均法計算聚類中心，即

其中:n 為簇內點的個數;Xi為簇內點坐標。

3 仿真實驗及分析

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

基于上述考慮，本文將利用Matlab 提供的C/C ++編譯器，將m 文件編譯成可執行的應用程序，使用的編譯環境是MS VC++ 6.0 和Matlab6.5。針對靜態多目標和動態多目標偵察2 種不同的情況，本文進行2 次測試，2 組測試數據分別為:

第1 組:靜態目標，有10 000個數據點，目標數目為100，并給出100 個目標中心點坐標，該數據樣本具有不規則的簇分布，且含有噪聲點;

第2 組:動態目標，有兩批數據點，假設時間(t -t +Δt)時，有10 000個數據點，目標數目為100，并給出100 個目標中心點坐標;(t+Δt，t+2Δt)時，有1000個數據點，目標數目為100，并給出100 個目標中心點坐標。該數據樣本具有不規則的簇分布，且含有噪聲點;

仿真測試在聯想y4 60 2.5GHz CPU 環境下進行。首先分別利用Kmeans 算法和Wavecluster 進行靜態多目標定位，獲取目標位置信息，選定的參數為:初始聚類數目K =100，分辨率resolution=1，數據維度Dimensions=2，采用的小波為二進小波。其結果如表1 所示。

表1 靜態多目標定位結果

從表1 中可以看出，相比于傳統的Kmeans 算法，Wavecluster 算法在處理簇分布不均勻、含有噪聲的大規模數據集時，聚類結果更加精確和細致。

然后利用基于時間窗口的Kmeans 算法和Wavecluster算法進行動態多目標定位，獲取目標位置信息，選定的參數為:初始聚類數目K =100，分辨率resolution =1，數據維度Dimensions=2，時間窗口W = Δt，采用的小波為二進小波。其結果如表2 所示。

表2 動態多目標定位結果

從表2 中可以看出，Wavecluster 算法在進行數據流聚類時，可以進行自動聚類，且具有較高的聚類精度;而傳統的Kmeans 算法在處理數據流時需要指定時間窗口W，W 的選擇直接影響著定位精度，而目前W 的選擇并沒有通用且有效的方法。

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

表3 在不同分辨率下的Wavecluster 定位結果

通過以上仿真測試可以看出，相比較Kmeans 聚類算法，Wavecluster 算法具有較大優勢，主要有:一是可以自動確定聚類數目，二是可以有效去除噪聲對聚類結果的影響并發現任意形狀的簇，三是在處理數據流聚類問題時可以自動聚類。

4 結束語

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

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

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

［3］姜園，張朝陽.用于數據挖掘的聚類算法［J］.電子與信息學報，2005，27(4):655-661.

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

［5］何承偉.基于小波變換的目標機動檢測［D］.太原:太原理工大學，2007.

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

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

［8］畢玲.小波聚類算法的研究及應用［D］.大連:大連理工大學，2006.

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

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