基于單體擴張的端元提取算法

董安國，韓 雪，龔文娟

?

基于單體擴張的端元提取算法

董安國，韓 雪，龔文娟

（長安大學(xué) 理學(xué)院，陜西 西安 710064）

端元提取是高光譜混合像元分解的重要環(huán)節(jié)。為了提取高光譜圖像的端元，本文基于線性表示理論與凸錐模型理論，論證了：與單體共面的單體外向量被單體的頂點向量線性表示時，表示系數(shù)必有負值，從而給出了理想情形下判別端元的充要條件，并在此基礎(chǔ)上，針對非理想情形提出了一種提取端元的迭代算法。實驗結(jié)果表明，算法提取端元的精度優(yōu)于VCA算法、效率高于搜索算法，算法穩(wěn)定性好，對噪聲的敏感性低。

高光譜；凸錐模型；端元提取；單體

0 引言

高光譜遙感圖像因具有較高光譜分辨率而成為當(dāng)今遙感領(lǐng)域研究的熱點，但其較低的空間分辨率和復(fù)雜的地物分布，導(dǎo)致影像中普遍存在混合像元，所以，基于高光譜圖像進行精確的地物識別和分類，首先要對混合像元進行分解，而端元提取是混合像元分解的關(guān)鍵環(huán)節(jié)[1]。目前，端元提取算法較多，總體可以分為3類：窮舉算法，投影算法與迭代算法。窮舉是一種重復(fù)型算法，它的基本思想是，對問題的所有可能狀態(tài)一一進行測試，直到找到解或全部可能的狀態(tài)都測試過為止，窮舉算法提取端元的精度高，但是算法運算量大，包括N-finder[2-3]算法，單體增長（simplex growing algorithm，SGA）[4-5]算法，其中N-FINDR算法，盡管無參數(shù)選擇效果好，但因其搜索凸面體最大體積需遍歷所有可能像元，計算量巨大。投影算法在進行端元提取時，計算速度相對較快，但是算法受噪聲影響較大，精度不高。例如：像元純凈指數(shù)（pixel purity index，PPI）[6-7]算法，頂點成分分析（vertex component analysis，VCA）[8-9]算法，它們都是基于投影的算法，只是投影的方式不同。迭代是不斷利用新值取代舊值，或者由舊值遞推出變量新值的過程，此法運算速度快，工作量少，精度取決于算法的本身。例如，序列最大角凸錐（sequential maximum angle convex cone，SMACC）[10-11]算法，它雖然計算速度快，但不能保證獲取端元的精度。

為此，論文在兼顧效率和精度的同時，基于線性表示理論，提出了一種迭代算法，即基于單體擴張的端元提取算法。首先，隨機選取已知數(shù)目的像元作為初始端元集，用初始端元線性表示其他像元，得到一系列表示系數(shù)，確定出負系數(shù)的絕對值最大的像元，表明此像元離單體的“距離”最遠，將其替換初始端元中的某一個，使得替換后的單體體積最大；重復(fù)上述過程直到無負系數(shù)。從而找到使凸面單體體積達到最大的像元集，即端元。

1 端元提取的相關(guān)理論

相關(guān)理論是基于理想情形下給出，即數(shù)據(jù)無噪聲，且完全滿足線性混合模型。

1.1 端元提取的理論模型

本文將基于線性混合模型展開討論。

1.2 基于線性表示的端元判定

在中任取個無關(guān)點1,2,…,，并記＝{1,2,…,}，＝{1,2,…,}是端元集，則有以下結(jié)論。

定理1的凸面單體()中的任意向量均可被1,2,…,線性表示，且系數(shù)和為1。

定理2的凸面單體包含于的凸面單體中，即()ì()。

定理1表明，對任意?，均可被唯一地線性表示，且系數(shù)之和為1，若系數(shù)全非負，則?()，否則?()。定理2表明，將?均由來線性表示，若所有的表示系數(shù)全非負，則就是端元。

定理3＝{1,2,…,}是端元集的充分必要條件是高光譜向量集被線性表示的系數(shù)均非負。

必要性，由定理1和定理2顯然可得。

2 理想情形下端元提取算法

基于上章給出的理論，端元提取的實現(xiàn)涉及3個內(nèi)容，分別是單體體積計算、線性表示的系數(shù)確定以及算法流程。

2.1 單體體積計算

根據(jù)文獻[13]，以1,2,…,為頂點的－1維凸面單體的體積(())的計算公式為：

式中：＝{2－1,3－1,…,－1}。

2.2 線性表示的系數(shù)確定

若端元個數(shù)為，則在理想情形下，ì()，高光譜向量集的秩為，由于1,2,…,線性無關(guān)，所以?(＝1,2,…,)，均可由1,2,…,唯一地線性表示，＝{1,2,…,}其系數(shù)＝{1,2,…,}，由線性方程組確定：

＝(＝1,2,…,) (3)

2.3 端元提取算法流程

算法采用迭代思想，首先從中任意選取個無關(guān)點作為初始端元＝{1,2,…,}，再從中找出一個向量0來代替中的一個向量0，形成迭代過程。

確定0的規(guī)則是使其離單體()盡量“遠”，考慮到當(dāng)用1,2,…,來表示x時，其負系數(shù)的絕對值越大，表明離單體()的“距離”越遠，所以可用線性表示的系數(shù)來確定0。確定被替換對象0的規(guī)則是使替換后的單體體積盡量大。具體流程如下：

輸入：高光譜向量＝{1,2,…,}，端元個數(shù)；

輸出：端元向量1,2,…,。

第一步：在中任取個無關(guān)點1,2,…,；

第二步：對?，求線性方程組c＝得到系數(shù)，并記＝min(1,2,…,)(＝1, 2,…,)；

第三步：若≥0(＝1, 2,…,)，則1,2,…,是端元向量并輸出，結(jié)束；

盡管未能證明算法第三步中((0))＞(())一定成立，但大量數(shù)值實驗均未出現(xiàn)算法失效的情形。

3 非理想情形的端元提取算法

上述理論和算法均基于理想情形，而實際數(shù)據(jù)一定不是理想狀況，疊加了各種噪聲，理論條件均不滿足，幾個關(guān)鍵的問題及算法改進如下：

1）數(shù)據(jù)集不在同一－1維超平面內(nèi)，而分布在超平面“兩側(cè)”附近，ì()只在“距離很近”的意義下成立。

2）的秩遠遠大于，線性方程組(3)無解，但由于“近似”落在維超平面內(nèi)，所以，可以求出線性方程組(3)的最小二乘解，作為“近似線性表示”系數(shù)。

3）由于噪聲的存在，算法步驟第三步中不能保證((0))＞(())，每次迭代得到的單體體積不單調(diào)，不能保證算法收斂，出現(xiàn)算法失效的情況。對此，將算法第三步找出一個離()“最遠”點0的步驟，嵌套入一個內(nèi)層迭代，這樣，算法第三步改進如下：

第三步：若≥0(＝1,2,…,)，則1,2,…,是端元向量并輸出，結(jié)束；

理論上，可能存在算法失效的情形，但大量數(shù)值實驗均未出現(xiàn)失效情況。

4 實驗與分析

實驗首先通過人造數(shù)據(jù)，在端元已知的情況下，運用算法提取端元，再對真實高光譜數(shù)據(jù)進行實驗。

4.1 仿真實驗

首先針對不添加噪聲的理想情形，再次針對添加噪聲的非理想情形。

4.1.1 理想情形下

為驗證本算法的有效性，實驗首先用人工合成的三維數(shù)據(jù)，點(1,1.2,3)，(0.4,2,1)，(3,2,1)為理論端元，被隨機產(chǎn)生的歸一化的非負系數(shù)合成2000個點，即這2000個點在3個端點向量組成的三角形內(nèi)，此時不添加任何的噪聲。實驗結(jié)果如圖1所示，圖中黑色部分圈出的點為提取出的“端元”，圖1(a)為算法初始時隨機選取的3個“端元”，圖1(b)為算法經(jīng)過第一次迭代，可觀察到此時提取出其中的一個端元，圖1(d)為算法最終迭代，提取出的端元，恰為理論端元。

圖1 理想情形下的端元提取過程圖

4.1.2 非理想情形下

實驗依舊用人工合成的三維數(shù)據(jù)，點(1,1.2,3)，(0.4,2,1)，(3,2,1)為理論端元，被隨機產(chǎn)生的歸一化的非負系數(shù)合成2000個點，再附加0均值的高斯噪聲，實驗結(jié)果如圖2所示，圖中黑色部分，圈出的點為提取出的“端元”，圖2(a)為算法初始時隨機選取的3個“端元”，圖2(b)為算法第一次迭代，可觀察到此時提取出其中的一個端元，圖2(d)為算法最終迭代提取出的端元，恰為理論端元。計算出本算法提取的端元單體體積最大，如表1。

圖2 非理想情形下的端元提取過程圖

表1 三種算法所得端元單體的體積

當(dāng)合成數(shù)據(jù)為20維，3個端元時，被隨機產(chǎn)生歸一化的非負系數(shù)合成10000個像元，分別加入信噪比為15dB，25dB，35dB，45dB，55dB的高斯白噪聲時，用3種方法提取出端元，計算平均光譜角距離（mSAD）的值，得到的結(jié)果如圖3(a)所示，本文算法對噪聲的敏感性低。

當(dāng)端元數(shù)目分別為3，4，5，6，7個時，維數(shù)為20，分別被隨機產(chǎn)生歸一化的非負系數(shù)合成10000個像元，加入信噪比為35dB的高斯白噪聲，用3種算法提取端元計算提取的端元與真實端元的mSAD值，如圖3(b)所示，本文算法得到mSAD值為0，說明端元提取精度最好的是本文算法，其次是VCA算法，PPI算法最差。

4.2 高光譜數(shù)據(jù)的算法實驗分析

本文用美國內(nèi)華達州Cuprite地區(qū)的AVIRIS數(shù)據(jù)進行分解實驗，Cuprite地區(qū)AVIRIS原始數(shù)據(jù)，共224個波段，光譜分辨率為10nm，尺寸為350×350像元，刪除噪聲較大和光譜吸收較大的波段，本文選擇172～221光譜區(qū)間的50個波段用于算法測試，已知端元數(shù)目為8[14]，算法迭代16次，便可提取出最終端元，用提取出的端元對高光譜影像進行豐度反演，反演時運用基于幾何距離的全約束混合像元分解算法（DGAE）[15]，得到的豐度圖如圖4(a)～圖4(h)所示，將各豐度圖與圖4(j)的調(diào)查分類結(jié)果圖比較，從而確定端元對應(yīng)的礦物。圖4(i)為端元的位置分布。圖4(k)為用于處理的區(qū)域的AVIRIS假彩色合成圖像。最終將本文算法與VCA，PPI算法得到的端元體積進行比較，如表2所示，本文算法得到的體積最大。

圖3 3種算法性能比較

表2 3種算法所得端元單體的體積

為了進一步比較，我們將USGS庫中對應(yīng)的礦物光譜作為參考光譜，將參考光譜在相應(yīng)的波段范圍內(nèi)能量求積分，轉(zhuǎn)換為光譜向量，并求取解混所得的端元與它們之間的光譜角，如表3所示，可以看出，用本文方法提取的端元與USGS光譜庫中的標準光譜相似度較高，總體上優(yōu)于VCA與PPI算法提取的端元光譜。

5 結(jié)論

本論文是在線性混合模型的基礎(chǔ)上，假設(shè)純凈像元存在的前提下提出的，是一種基于單體擴張的端元提取算法，它的主要思想就是基于線性表示的端元判定，給出了端元判別的定理，并將定理進行證明，是另外一種迭代算法，并且，通過迭代，優(yōu)化其時間效率。文中用人工仿真的數(shù)據(jù)與真實的高光譜數(shù)據(jù)進行實驗，表明本算法精度高，穩(wěn)定性好。算法是在端元數(shù)目已知的情況下給出的，后續(xù)工作將針對端元數(shù)目未知時進行研究。

圖4 美國Cuprite地區(qū)AVIRIS數(shù)據(jù)端元分解結(jié)果（350像元×350像元）

表3 提取的端元與標準光譜庫中的標準光譜的光譜角距離

[1] 李二森, 朱述龍, 周曉明, 等. 高光譜圖像端元提取算法研究進展與比較[J]. 遙感學(xué)報, 2011,15(4): 659-679.

LI Ersen, ZHU Shulong, ZHOU Xiaoming, et al. The development and comparison of endmember extraction algorithms using hyperspectral imagery[J]., 2011, 15(4): 659-679.

[2] JI Luyan, GENG Xiurui, Sun Kang, et al. Modified N-FINDR endmember extraction algorithm for remote-sensing imagery[J]., 2015, 36(8): 2148-2162.

[3] 楊可明, 魏華鋒, 劉飛, 等. 以光譜信息熵改進的N-FINDR端元提取算法[J]. 地球信息科學(xué)學(xué)報, 2015, 17(8): 980-985.

YANG Keming, WEI Huafeng, LIU Fei, et al. Improved N-FINDR algorithm on hyperspectral endmember extraction based on spectral Shannon entropy[J]., 2015, 17(8): 980-985.

[4] ZHAO L, FAN M, WANG L. Fast implementation of linear and nonlinear simplex growing algorithm for hyperspectral endmember extraction[J].,2015, 126(23): 4072-4077.

[5] LIU Junmin, ZHANG Jiangshe. A new maximum simplex volume method based on householder transformation for endmember extraction[J]., 2012, 50(1): 104-111.

[6] Rob Heylen, Paul Scheunders. Multidimensional pixel purity index for convex Hull estimation and endmember extraction[J]., 2013, 51(7): 4059-4069.

[7] 徐軍, 徐富紅, 蔡體健, 等. 一種基于最大距離的純像元指數(shù)端元提取算法[J].地球信息科學(xué)學(xué)報, 2015, 17(1): 86-90.

XU Jun, XU Fuhong, CAI Tijian, et al. A novel pure pixel endmember extraction algorithm based on the maximum distance[J]., 2015, 17(1): 86-90.

[8] Jose M, Rodriguez Alves, Jose M, et al. Vertex component analysis Gpu-based implementation for hyperspectral unimixing[C]//, 2012: 10.1109/WHISPERS.2012.6874337.

[9] 何曉寧, 曹建農(nóng), 高坡, 等. 基于頂點成分分析法的端元提取改進算法[J]. 測繪通報, 2013 (7): 30-34.

HE Xiaoning, CAO Jiannong, GAO Po, et al. An improved algorithm of endmember extraction based on vertex component analysis[J]., 2013(7): 30-34.

[10] John Gruninger, Anthony J Ratkowski, Michael L Hoke. The sequential maximum angle Convex Cone(SMACC) endmember model[C]//,[C]//2004, 5425: doi:10.1117/12.543794.

[11] LIU C, LI J, WANG G. Endmember extraction algorithm for hyperspectral image based on PCA-SMACC[C]//,, 2014, 9142:91421A.

[12] Ambikapathi A M, Chan T H, Ma W K. A robust alternating volume maximization algorithm for endmember extraction in hyperspectral images[C]// 2on, 2010: 10.1109/WHISPERS.2010.5594862.

[13] SUN Kang, GENG Xiurui, WANG Panshi, et al. A fast endmember extraction algorithm based on gram determinant[J].,2014, 11(6): 1124-1127.

[14] 田玉剛, 楊貴. 端元快速提取的光譜梯度特征搜索法[J]. 測繪學(xué)報, 2015, 44(2): 214-219.

TIAN Yugang, YANG Gui. A fast endmember extraction algorithmusing spectrum gradient features[J]., 2015,44(2): 214-219.

[15] PU H, XIA W, WANG B, et al. A fully constrained linear spectral unmixing algorithm based on distance geometry[J].,2014, 52(2): 1157-1176.

Endmember Extraction Algorithm Based on the Simplex Expansion

DONG Anguo，HAN Xue，GONG Wenjuan

（School of Science, Chang’an University, Xi’an 710064, China）

Endmember extraction is a key step in unmixing hyperspectral mixed pixels. In order to extract endmembers of hyperspectral image, this paper proves that if a vector in vitro and vivo is represented by a vertex vector, there will be a negative coefficient based on the theory of linear representation and the theory of convex cone model. The theory gives a necessary and sufficient condition for the endmembers identification. A new iterative algorithm is proposed under non-ideal situation. The experimental results show that the precision of the endmember extraction using the algorithm proposed in this paper is better than VCA algorithm. And this algorithm has better efficiency than the search algorithm. It has good stability and a low sensitivity to noise.

hyperspectral，convex cone，endmember extraction，simplex

TP7

A

1001-8891(2016)11-0947-06

2016-05-24；

2016-08-05.

董安國（1964-），男，浙江象山人，教授，碩士生導(dǎo)師，主要研究領(lǐng)域為數(shù)值代數(shù)，數(shù)字圖像處理，E-mail：donganguo@chd.edu.cn。

國家自然科學(xué)基金項目（41571346），國家自然科學(xué)基金項目（40971217），國家自然科學(xué)基金項目（11201038）。