最短路徑距離矩陣修正的多維標(biāo)度定位算法

任克強(qiáng)，莊放望（江西理工大學(xué)信息工程學(xué)院，江西贛州341000）

?

最短路徑距離矩陣修正的多維標(biāo)度定位算法

任克強(qiáng)*，莊放望
（江西理工大學(xué)信息工程學(xué)院，江西贛州341000）

摘要：為了減小最短路徑距離矩陣與歐氏距離矩陣之間的差異，提高M(jìn)DS-MAP（C）算法的節(jié)點(diǎn)定位精度，提出一種改進(jìn)的多維標(biāo)度節(jié)點(diǎn)定位算法。該算法對(duì)MDS-MAP（C）算法進(jìn)行了以下改進(jìn)：采用啟發(fā)式的搜索策略對(duì)最短路徑距離矩陣進(jìn)行修正，以減少最短路徑距離矩陣與實(shí)際的歐氏距離矩陣之間的誤差；利用smacof算法迭代誤差函數(shù)代替SVD分解來(lái)求解節(jié)點(diǎn)的定位問(wèn)題，以優(yōu)化和改善節(jié)點(diǎn)定位的求解過(guò)程。實(shí)驗(yàn)結(jié)果表明，與MDS-MAP（C）算法相比，改進(jìn)算法能夠減少最短路徑距離的誤差，有效提高節(jié)點(diǎn)的定位精度，并且對(duì)不規(guī)則網(wǎng)絡(luò)具有更好的適應(yīng)性。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；最短路徑；MDS-MAP（C）算法；節(jié)點(diǎn)定位；多維標(biāo)度；smacof算法

無(wú)線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Net?work）由大量部署在監(jiān)測(cè)區(qū)域內(nèi)的廉價(jià)微型傳感器節(jié)點(diǎn)構(gòu)成，它是一種自組織、分布式處理以及快速展開(kāi)的無(wú)線網(wǎng)絡(luò)［1］。傳感器節(jié)點(diǎn)的位置信息對(duì)WSN的監(jiān)測(cè)活動(dòng)極其重要，獲取準(zhǔn)確的傳感器節(jié)點(diǎn)位置信息是WSN進(jìn)行相關(guān)監(jiān)測(cè)以及傳感器節(jié)點(diǎn)進(jìn)行下一步活動(dòng)和決策的基礎(chǔ)［2］。WSN的節(jié)點(diǎn)定位算法按定位機(jī)制的不同可分為基于測(cè)距（Rangebased）的算法和測(cè)距無(wú)關(guān)（Range-free）的算法［3-4］。Range-based算法通過(guò)測(cè)量節(jié)點(diǎn)之間的距離或角度來(lái)實(shí)現(xiàn)定位，Range-free算法則無(wú)需測(cè)量節(jié)點(diǎn)之間的距離和角度信息，而是根據(jù)網(wǎng)絡(luò)的連通性等信息來(lái)實(shí)現(xiàn)定位［5］。Range-based的代表算法有基于到達(dá)時(shí)間TOA（Time of Arrival）的定位、基于到達(dá)時(shí)間差TDOA（Time Difference of Arrival）的定位、基于接收信號(hào)強(qiáng)度指示RSSI（Received Signal Strength Indi?cator）的定位以及基于到達(dá)角度AOA（Angle of Ar?rival）的定位等算法［6-8］。Range-free的代表算法有距離向量-跳段DV-hop（Distance Vector-hop）定位、凸規(guī)劃（Convex Optimization）定位以及多維標(biāo)度MDS（Multidimensional Scaling）定位等算法［9-10］。

MDS是一種將多維空間中的研究對(duì)象簡(jiǎn)化到低維空間中進(jìn)行定位、分析和歸類，并且保持研究對(duì)象之間原有關(guān)系的多元數(shù)據(jù)分析技術(shù)。Shang Yi等人將MDS技術(shù)應(yīng)用于WSN的節(jié)點(diǎn)定位，提出了MDSMAP算法［11］；該算法利用節(jié)點(diǎn)間的連通性或距離估計(jì)信息進(jìn)行定位，將節(jié)點(diǎn)間最短路徑距離近似為節(jié)點(diǎn)間的歐氏距離，再利用MDS方法進(jìn)行定位；當(dāng)網(wǎng)絡(luò)拓?fù)洳灰?guī)則時(shí)，由于最短路徑距離與節(jié)點(diǎn)間實(shí)際的歐氏距離相差較大，嚴(yán)重影響算法的定位精度。為了解決最短路徑距離與節(jié)點(diǎn)間實(shí)際歐氏距離的差異性問(wèn)題，國(guó)內(nèi)外研究人員提出了不同的MDS-MAP算法改進(jìn)和優(yōu)化方案。文獻(xiàn)［12］將網(wǎng)絡(luò)拓?fù)浞纸鉃槎鄠€(gè)局部地圖，再按分布式的計(jì)算模式對(duì)局部地圖進(jìn)行MDSMAP定位，減少了最短路徑距離與節(jié)點(diǎn)間實(shí)際歐氏距離的誤差，但在Range-Free環(huán)境的定位精度依然不高。文獻(xiàn)［13］在生成相對(duì)地圖的過(guò)程中采用迭代更新的方式來(lái)改善定位性能，使其定位精度有了較大的提升，但計(jì)算復(fù)雜度較高，節(jié)點(diǎn)的能耗較大。文獻(xiàn)［14］采用距離矩陣重構(gòu)的方式來(lái)替代最短路徑距離矩陣，并用奇異值分解SVD（Singular Value Decompo?sition）低秩近似的方法來(lái)求解距離矩陣。文獻(xiàn)［15］提出基于距離矩陣重構(gòu)的WSN多維標(biāo)度定位算法，利用節(jié)點(diǎn)間的相關(guān)信息對(duì)距離矩陣進(jìn)行線性重構(gòu)，然后使用經(jīng)典MDS進(jìn)行定位，取得了較好的定位精度。文獻(xiàn)［16］針對(duì)MDS-MAP在不均勻網(wǎng)絡(luò)中定位精度較低的問(wèn)題，提出一種可用于不均勻網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法，有效地減小了平均定位誤差。文獻(xiàn)［17］提出改進(jìn)距離重構(gòu)的三維節(jié)點(diǎn)定位算法，該算法利用MDS-MAP算法獲取節(jié)點(diǎn)之間相對(duì)的坐標(biāo)，并采用精度更高的坐標(biāo)映射方案對(duì)坐標(biāo)轉(zhuǎn)換過(guò)程進(jìn)行優(yōu)化，取得了較高的三維節(jié)點(diǎn)定位精度。

針對(duì)最短路徑距離與節(jié)點(diǎn)之間實(shí)際歐氏距離的差異性問(wèn)題，本文提出一種基于最短路徑距離矩陣修正的多維標(biāo)度定位算法MDS-DMC（MDSDistance Matrix Correction），通過(guò)修正最短距離矩陣來(lái)逼近歐氏距離矩陣，以提高節(jié)點(diǎn)的定位精度。

1　多維標(biāo)度定位算法

MDS-MAP（C）是一種基于經(jīng)典MDS（Classical MDS，CMDS）的多維標(biāo)度定位算法，該算法將各個(gè)節(jié)點(diǎn)視作一個(gè)實(shí)體元素，各節(jié)點(diǎn)之間的相似性用歐氏空間距離來(lái)表示，通過(guò)建立歐氏空間距離與相似性信息的線性映射關(guān)系后，就可在多維空間內(nèi)獲得節(jié)點(diǎn)的分布。如果獲得的相似性信息與歐氏空間距離的差異不大，則利用CMDS就可得到各節(jié)點(diǎn)之間相對(duì)的位置空間分布。

令Pi，j為m維空間中i和j兩個(gè)點(diǎn)的相似性信息，通常等價(jià)于歐氏空間距離di，j，i點(diǎn)坐標(biāo)為xi=(xi1，xi2，…，xim)，j點(diǎn)坐標(biāo)為xj=(xj1，xj2，…，xjm)，則：

其中，e為元素全1的N×1維向量。

定義中心矩陣H=I-eeT/N（I為單位矩陣），對(duì)D進(jìn)行雙中心化：

2　MDS-DMC算法

MDS-MAP（C）算法以節(jié)點(diǎn)之間的最短路徑距離替代歐氏空間距離，并采用SVD分解求解節(jié)點(diǎn)位置。在密集且分布均勻的網(wǎng)絡(luò)環(huán)境中，最短路徑距離可以近似歐氏空間距離；但在稀疏且分布不均的網(wǎng)絡(luò)環(huán)境中，最短路徑距離與歐氏空間距離的差異往往很大，此時(shí)兩者近似將產(chǎn)生較大的誤差。此外，當(dāng)網(wǎng)絡(luò)規(guī)模很大時(shí)，采用SVD分解求解節(jié)點(diǎn)位置比較復(fù)雜且定位精度不高。本文針對(duì)這些問(wèn)題，提出MDS-DMC算法，對(duì)MDS-MAP （C）算法進(jìn)行了兩個(gè)方面的改進(jìn)：①采用啟發(fā)式的搜索策略對(duì)最短距離矩陣進(jìn)行修正，以減少最短距離矩陣與實(shí)際的歐氏距離矩陣之間的誤差；②使用smacof算法迭代誤差函數(shù)代替SVD分解來(lái)求解定位問(wèn)題，以改善和優(yōu)化節(jié)點(diǎn)定位的求解過(guò)程。

2.1最短距離矩陣的修正

假定節(jié)點(diǎn)所能輻射范圍的通信半徑為R，A、C兩個(gè)節(jié)點(diǎn)之間的距離L無(wú)法直接獲取，如圖1所示。

如果用最短路徑算法求取的最短路徑距離來(lái)近似代替A、C節(jié)點(diǎn)之間的距離L，則有AC≈AB+BC，即L≈d1+d2。

很明顯，這種近似存在誤差。為了減少誤差，本文通過(guò)以下啟發(fā)式的搜索策略來(lái)修正最短距離矩陣。

根據(jù)余弦定理，有：

由上可得：

因此，通過(guò)以上方法修正最短距離矩陣，可以改善用最短距離矩陣近似歐氏距離矩陣產(chǎn)生的誤差。

2.2求解節(jié)點(diǎn)位置的改進(jìn)

對(duì)于節(jié)點(diǎn)數(shù)目為N的網(wǎng)絡(luò)，使用SVD分解求解節(jié)點(diǎn)位置的復(fù)雜度為O(N3)，當(dāng)節(jié)點(diǎn)規(guī)模很大時(shí)，一般采用迭代的方法代替SVD分解，以提高求解節(jié)點(diǎn)位置的效率。本文采用Metric MDS求解節(jié)點(diǎn)的位置，并利用smacof算法迭代誤差函數(shù)代替SVD方法求解節(jié)點(diǎn)的定位問(wèn)題，以下簡(jiǎn)稱為MDS-MAP （smacof）算法。

定義函數(shù)S作為估算距離與實(shí)際距離的誤差函數(shù)：

將式（10）展開(kāi)得到：

將式（11）轉(zhuǎn)化成矩陣形式：

其中，trace{?}為跡運(yùn)算，代表矩陣的對(duì)角線元素之和；X是由所有節(jié)點(diǎn)組成的矩陣[x1，x2，…，xN]，XT是X的轉(zhuǎn)置；H為中心矩陣，H=I-eeT/N，I為單位矩陣；Ψ(X)是關(guān)于X的中心矩陣，其元素由式（13）組成：

采用smacof算法，定義輔助函數(shù)φ(X，Z)為：

每次迭代k，采用Z=Xk-1，由于φ(X，Z)的梯度函數(shù)為：

令梯度為0，可以得到：

根據(jù)矩陣H的特性，可以推導(dǎo)出X的迭代形式：

從而，節(jié)點(diǎn)的坐標(biāo)可通過(guò)迭代的方式求得。

分析式(17)的迭代公式，求解該遞歸過(guò)程的復(fù)雜度為O(N2)，即節(jié)點(diǎn)坐標(biāo)求解過(guò)程的復(fù)雜度為O(N2)；而執(zhí)行SVD分解求解節(jié)點(diǎn)位置的復(fù)雜度為O(N3)。因此，通過(guò)smacof算法可有效降低求解節(jié)點(diǎn)位置的復(fù)雜度。

圖1　最短距離矩陣修正示意圖

3　實(shí)驗(yàn)結(jié)果及分析

為了測(cè)試MDS-DMC算法的改進(jìn)效果，本文對(duì)MDS-MAP（C）算法、MDS-MAP（smacof）算法和MDSDMC算法進(jìn)行了仿真比較實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)：WIN?DOWS XP SP3+MATLAB 2009a。實(shí)驗(yàn)環(huán)境與場(chǎng)景：矩形隨機(jī)網(wǎng)絡(luò)、C型隨機(jī)網(wǎng)絡(luò)；2-D平面L×L的區(qū)域內(nèi)隨機(jī)分布300個(gè)節(jié)點(diǎn)，包括4個(gè)錨節(jié)點(diǎn)。實(shí)驗(yàn)參數(shù)：未知節(jié)點(diǎn)通信半徑為r，錨節(jié)點(diǎn)通信半徑為R，并且r=R。

使用歸一化的平均定位誤差來(lái)評(píng)價(jià)實(shí)驗(yàn)算法的性能：

其中，N為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)，M為錨節(jié)點(diǎn)個(gè)數(shù)，r為未知節(jié)點(diǎn)通信半徑，xi為節(jié)點(diǎn)i實(shí)際位置，為節(jié)點(diǎn)i估計(jì)位置。

3.1理想傳輸模型下的定位

該實(shí)驗(yàn)主要比較三種算法在理想傳輸模型的不同網(wǎng)絡(luò)拓?fù)湎碌男阅?。在?shí)驗(yàn)場(chǎng)景的兩種網(wǎng)絡(luò)拓?fù)湎拢S機(jī)部署300個(gè)節(jié)點(diǎn)，在通信半徑為0.2 L的情況下，矩形網(wǎng)絡(luò)平均連通度為31.1，C型網(wǎng)絡(luò)平均連通度為34.6，分別用MDS-MAP（C）算法、MDS-MAP（smacof）算法和MDS-DMC算法進(jìn)行定位。該實(shí)驗(yàn)的節(jié)點(diǎn)分布以及定位誤差如圖2~圖4所示，圖中空心圓圈代表未知節(jié)點(diǎn)的坐標(biāo)，實(shí)心圓圈代表錨節(jié)點(diǎn)的位置，線段代表定位誤差。

圖2　理想傳輸模型下的網(wǎng)絡(luò)分布

圖3　理想傳輸模型下矩形網(wǎng)絡(luò)的定位

圖4　理想傳輸模型下C形網(wǎng)絡(luò)的定位

由實(shí)驗(yàn)結(jié)果可知，在矩形網(wǎng)絡(luò)中，MDS-MAP （C）算法的平均定位誤差為18.7%；MDS-MAP （smacof）算法的平均定位誤差有了的改善，為16.9%；而MDS-DMC算法的平均定位誤差僅為4.1%，有效的提高了定位的精度。在C型網(wǎng)絡(luò)中，由于不規(guī)則網(wǎng)絡(luò)的影響，出現(xiàn)了拓?fù)淇斩吹那闆r，最短路徑距離矩陣存在較大的誤差，導(dǎo)致MDSMAP（C）算法的平均定位誤差高達(dá)117.8%，而采用MDS-MAP（smacof）算法和MDS-DMC算法的平均定位誤差分別為95%和17%，MDS-DMC算法大幅度的減小了平均定位誤差。因此，在C型網(wǎng)絡(luò)中，MDS-DMC算法可以有效減少最短路徑距離的差異，改善定位性能，提高對(duì)不規(guī)則網(wǎng)絡(luò)的適應(yīng)性。

3.2非理想傳輸模型下的定位

非理想傳輸模型的定位可用不規(guī)則的信號(hào)模型來(lái)模擬實(shí)際的環(huán)境，采用不規(guī)則度DOI（Degree of Irregular）表征錨節(jié)點(diǎn)的傳播信號(hào)在傳輸?shù)倪^(guò)程中受到的影響，DOI值反映了錨節(jié)點(diǎn)信號(hào)廣播的不規(guī)則程度。該實(shí)驗(yàn)主要比較三種算法在非理想傳輸模型的不同網(wǎng)絡(luò)拓?fù)湎碌男阅?，在?shí)驗(yàn)場(chǎng)景的兩種網(wǎng)絡(luò)拓?fù)湎?，隨機(jī)部署300個(gè)節(jié)點(diǎn)，在通信半徑為0.2L以及DOI為0.2的情況下，矩形網(wǎng)絡(luò)平均連通度為30.3，C型網(wǎng)絡(luò)平均連通度為35.9，分別用MDS-MAP（C）算法、MDS-MAP（smacof）算法和MDSDMC算法進(jìn)行定位。該實(shí)驗(yàn)的節(jié)點(diǎn)分布以及定位誤差如圖5~圖7所示。

圖6　非理想傳輸模型下矩形網(wǎng)絡(luò)的定位

圖7　非理想傳輸模型下C形網(wǎng)絡(luò)的定位

由實(shí)驗(yàn)結(jié)果可知，在非理想傳輸模型的矩形網(wǎng)絡(luò)中，MDS-MAP（C）算法、MDS-MAP（smacof）算法以及MDS-DMC算法的平均定位誤差分別為20.7%、17.4%和8.1%，MDS-DMC算法的定位性能有了明顯的改善。而在非理想傳輸模型的C型網(wǎng)絡(luò)中，由于最短路徑距離矩陣差異的影響不同，MDS-MAP （C）算法、MDS-MAP（smacof）算法以及MDS-DMC算法的平均定位誤差分別為118%、107%和18.1%，MDS-DMC算法定位性能的提升更為顯著。因此，MDS-DMC算法能夠較穩(wěn)定的適應(yīng)非理想傳輸模型的節(jié)點(diǎn)定位，提高不規(guī)則網(wǎng)絡(luò)的節(jié)點(diǎn)定位精度。

3.3不同連通度的定位誤差

該實(shí)驗(yàn)主要比較三種算法在不同通信半徑和連通度下的性能。在實(shí)驗(yàn)場(chǎng)景的兩種網(wǎng)絡(luò)拓?fù)湎?，隨機(jī)部署300個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)通信半徑r分別取0.125L、0.15L、0.175L、0.2L、0.225L和0.25L時(shí)，矩形網(wǎng)絡(luò)的連通度分別為13.6、18.7、25.1、31.1、38.0和48.3，C型網(wǎng)絡(luò)的連通度分別為16.5、22.8、29.1、38.2、45.1和51.3。實(shí)驗(yàn)結(jié)果如圖8所示。

從圖8可以看出，MDS-DMC算法在不同連通度的定位性能均優(yōu)于MDS-MAP（C）算法，在連通度較低的情況下，MDS-DMC算法的定位精度有了明顯的提高，特別是在C型網(wǎng)絡(luò)中，定位精度的提高幅度更大。因此，與MDS-MAP（C）算法相比，MDS-DMC算法在不規(guī)則網(wǎng)絡(luò)拓?fù)湎掠懈玫倪m應(yīng)性，在WSN的定位應(yīng)用中具有明顯的優(yōu)勢(shì)。

圖8　不同連通度的歸一化平均定位誤差比較

4　結(jié)論

①針對(duì)MDS-MAP（C）算法中的距離矩陣問(wèn)題，提出MDS-DMC算法。該算法采用啟發(fā)式搜索的最短路徑距離修正策略來(lái)減小最短路徑距離與實(shí)際歐氏距離之間的誤差，有效地提高了節(jié)點(diǎn)的定位精度和對(duì)不規(guī)則網(wǎng)絡(luò)的適應(yīng)性；引入smacof算法迭代誤差函數(shù)取替SVD分解來(lái)優(yōu)化節(jié)點(diǎn)定位的求解過(guò)程，進(jìn)一步提升了算法的性能。

②在理想傳輸模型、非理想傳輸模型以及不同傳輸半徑和連通度的算法仿真對(duì)比實(shí)驗(yàn)中，MDSDMC算法均表現(xiàn)出比MDS-MAP（C）算法更加優(yōu)異的性能，進(jìn)而驗(yàn)證了改進(jìn)方法是正確和有效的。

③減小最短路徑距離與實(shí)際歐氏距離之間的誤差是提高多維標(biāo)度節(jié)點(diǎn)定位算法性能的有效途徑之一。如何進(jìn)一步減小距離矩陣之間的差異是后續(xù)重點(diǎn)的研究工作。

參考文獻(xiàn)：

［1］Liu Qiang，Huang Xiaohong，Leng Supeng，et al. Deployment Strategy of Wireless Sensor Networks for Internet of Things［J］. China Communications，2011，8（8）：111-120.

［2］侯洪濤，周鴻偉，李群，等.衛(wèi)星導(dǎo)航系統(tǒng)接收傳感器網(wǎng)絡(luò)的攻擊檢測(cè)研究［J］.系統(tǒng)工程與電子技術(shù)，2014，36（6）：1195-1200.

［3］王福豹，史龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，2005，16（5）：857-868.

［4］張亞明，史浩山，劉燕，等.不對(duì)稱鏈路環(huán)境下的WSN節(jié)點(diǎn)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2014，27（3）：320-326.

［5］劉瑜，衣曉，何友.基于分治求精的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.系統(tǒng)工程與電子技術(shù)，2012，34（9）：1906-1913.

［6］錢志鴻，王義君.面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述［J］.電子與信息學(xué)報(bào)，2013，35（1）：215-227.

［7］Park J W，Park D H，Lee C. Angle and Ranging Based Localiza?tion Method for ad hoc Network［J］. The Journal of Supercomput?ing，2013，64（2）：507-521.

［8］袁鑫，吳曉平，王國(guó)英.線性最小二乘法的RSSI定位精確計(jì)算方法［J］.傳感技術(shù)學(xué)報(bào)，2014，27（10）：1412-1417.

［9］彭宇，王丹.無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)綜述［J］.電子測(cè)量與儀器學(xué)報(bào)，2011，25（5）：389-399.

［10］Macagnano D，de Abreu G. Algebraic Approach for Robust Local?ization with Heterogeneous Information［J］. IEEE Transactions on Wireless Communication，2013，12（10）：5334-5345.

［11］Shang Y，Ruml W，Zhang Y，et al. Localization from Mere Connec?tivity［C］//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York：ACM Press，2003：201-212.

［12］Shang Y，Ruml W. Improved MDS-based localization［C］// Twen?ty-Third Annual Joint Conference of the IEEE Computer and Com?munications Societies. Washington：IEEE Press，2004：2640-2651.

［13］Vivekanandan V，Wong V W S. Ordinal MDS-Based Localisation for Wireless Sensor Networks［J］. International Journal of Sensor Networks，2006，1（3）：169-178.

［14］Regalia P A，Wang J. On Distance Reconstruction for Sensor Net?Work Localization［C］// Proceedings of 2010 IEEE International Conference on Acoustics Speech and Signal Processing，Washing? ton：IEEE Press，2010：2866-2869.

［15］黃亮，王福豹，段渭軍，等.基于距離重構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)多維定標(biāo)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（9）：1284-1287.

［16］溫龍飛，崔靈果，張百海，等.不均勻布置傳感器網(wǎng)絡(luò)定位優(yōu)化算法［J］.兵工學(xué)報(bào)，2013，34（05）：639-643.

［17］張亞杰，段渭軍，王福豹，等.改進(jìn)的距離重構(gòu)三維定位算法［J］.傳感技術(shù)學(xué)報(bào)，2014，27（12）：1681-1686.

任克強(qiáng)（1959-），男，教授，碩士研究生導(dǎo)師，主要研究方向?yàn)榍度胧较到y(tǒng)、無(wú)線傳感器網(wǎng)絡(luò)等，jxrenkeqiang@163.com；

莊放望（1988-），男，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

A Preliminary Study of Zanthoxylurn Bungeanum Maxim Varieties Discriminating by Computer Vision*

WU Lili*，XING Yuqing，ZHENG Baozhou，LIN Aiying
（College of Sciences，Henan Agricultural University，Zhengzhou 450002，China）

Abstract：Zanthoxylurn Bungeanum Maxim is a kind of important ingredients for cooking and traditional Chinese medicine. In this paper，the computer vision technology was introduced to discriminate the varieties of Zanthoxylurn Bungeanum Maxim rapdily. The Zanthoxylurn Bungeanum Maxim image of six categories were obtained by the com?puter vision hardware device，and the total number of images was 90，of which 60 were used as training samples and 30 as test samples. The 10 feature parameters of color and texture features were extracted from all the samples，which were identified by the probabilistic neural network. The correct recognition rate was 93.33%. The discrimination method of Zanthoxylurn Bungeanum Maxim varieties by computer vision can quickly and accurately extract the char?acteristic data of the Zanthoxylurn Bungeanum Maxim samples，which lays the technical foundation for batch sorting. Key words：computer vision；color feature；texture feature；probabilistic neural network；Zanthoxylurn Bungeanum Maxim

doi：EEACC：6135;7230G10.3969/j.issn.1004-1699.2016.01.023

收稿日期：2015-08-06修改日期：2015-10-20

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1699（2016）01-0129-07