EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 8: 979 - 985

DOI: https://doi.org/10.3724/SP.J.1047.2015.00979

Orginal Article

Improved N-FINDR Algorithm on Hyperspectral Endmember Extraction Based on Spectral Shannon Entropy

  • YANG Keming , * ,
  • WEI Huafeng ,
  • LIU Fei ,
  • SHI Gangqiang ,
  • SUN Yangyang
Expand
  • College of Geosciences and Survey Engineering, China University of Mining & Technology (Beijing), Beijing 100083, China
*Corresponding author: YANG Keming, E-mail:

Received date: 2014-10-31

  Request revised date: 2015-02-13

  Online published: 2015-08-05

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Endmember extraction is a key step for unmixing hyperspectral mixed pixels and an important prerequisite in the further analysis of hyperspectral imagery. The traditional N-FINDR algorithm is a classical and effective algorithm among various endmember extraction methods. However, the N-FINDR algorithm need to compute all the possible pixel combinations, thus it is time consuming. In order to improve the time efficiency of the N-FINDR algorithm, this paper proposed an improved N-FINDR algorithm on hyperspectral endmember extraction based on spectral Shannon entropy theory and the convex geometry, meanwhile we utilize the characteristic that in spectral feature space, all pixels of the hyperspectral imagery could compose a single shape body, in which the pure pixels are located at the apex and the mixed pixels in the interior or at the surface. The spectral Shannon entropies of all pixels are calculated according to the pixel gray probability, and are used to determine the purity of pixels. The pixel is removed if its spectral Shannon entropy is greater than the threshold value of the spectral Shannon entropy, otherwise it is preserved. Next, the N-FINDR was used to search the largest volume from the single shape body composed by the preserved pixels, and the pixels at the apex of the body with the largest volume would be the endmembers. Finally, we use the Hyperion data of a copper mine in Dexing city from Jiangxi province to testify the improved N-FINDR algorithm. By analyzing the experimental results, the improved algorithm ensured a high accuracy as well as improved the data processing efficiency very greatly in the course of extracting hyperspectral endmembers.

Key words： hyperspectral imagery; mixed pixel; spectral Shannon entropy; N-FINDR; endmember extraction

Cite this article

YANG Keming , WEI Huafeng , LIU Fei , SHI Gangqiang , SUN Yangyang . Improved N-FINDR Algorithm on Hyperspectral Endmember Extraction Based on Spectral Shannon Entropy[J]. Journal of Geo-information Science, 2015 , 17(8) : 979 -985 . DOI: 10.3724/SP.J.1047.2015.00979

1 引言

高光谱遥感影像具有“图谱合一”、波谱信息丰富等特征,在多个领域得到广泛应用,但受较低空间分辨率和地表复杂性影响,高光谱影像中普遍存在混合像元,端元提取及其算法研究是混合像元分解的重要内容之一。目前,具有代表性的端元提取算法有：N-FINDR[1]、像元纯度指数（Pixel Purity Index,PPI）[2]、迭代误差分析（Iterative Error Analysis,IEA）[3]、单体增长（Simplex Growing Algorithm,SGA）[4]、顶点成分分析（Vertex Component Analysis,VCA）[5]等。传统的N-FINDR算法因操作简单、计算无参数和端元提取效果好等优点被广泛应用[6],但因其搜索凸面体最大体积需遍历所有可能的像元组合而计算量巨大[7]。
为此,本文在深入分析光谱信息熵理论和凸面体体积计算模型的基础上,提出了结合光谱信息熵的N-FINDR改进算法。该算法首先用光谱信息熵理论分析高光谱影像,从中提取出相对纯净的候选像元,然后用凸面体体积计算方法获取这些候选像元的最大体积,从而提取出影像的端元。

2 理论与算法

2.1 光谱信息熵

信息是对客观事物运动规律及其属性标识的描述。通常说到信息时,只能对其进行概述,却难以量化信息量的多少。直到1948年,Shannon提出了“信息熵”的概念[8],使得信息有了量化的度量。信息熵可理解为某种信息出现的概率,其出现概率越大,表明该信息被引用程度越高。从信息传播角度来说,信息熵可作为一个衡量信息价值的标准。信息熵可定义为：一个值域为 { x 1 , … , x n } 的随机变量X的熵值H。
H ( X ) = E ( I ( X ) ) （1）
式中, E 代表了期望函数; I ( X ) 是X的信息量; I ( X ) 本身是个随机变量。
光谱信息熵[9]是把信息论中熵的理论引入到高光谱影像的像元中。光谱信息熵是利用统计像元灰度的概率计算高光谱影像像元光谱的概率,用于计算光谱的信息熵。其计算如式（2）所示。
H ( j , k ) = - ∑ i = 1 n p ( x i ) lo g 2 p ( x i ) （2）
式中,xi是第i波段（j, k）位置像元的灰度值;p(xi)是i波段（j, k）位置像元亮度值的概率; p ( x i ) = NU M i ( j , k ) NU M i ; NU M i ( j , k ) 是第i波段上灰度值与xi相等的像元个数; NU M i 是第i波段上像元总数;n为影像波段数。
同一影像中,同类地物的纯净像元其DN值,在同一波段内基本相等,而混合像元由于其组成成分及其所占比例不同导致其DN值各不相等,混合像元个数比纯净像元个数更多,即式（2）中 p ( x i ) 较大。根据式（2）的单调性分析可知,若 p ( x i ) 越大,其像元光谱信息熵值越小。故可用像元的光谱信息熵值代表该像元的纯净程度。

2.2 传统N-FINDR算法

高光谱影像的所有像元,在高维空间形成凸面体。传统的N-FINDR算法基于凸面几何学理论,其先指定端元的个数为m个,使用最小噪声分离（Minimum Noise Fraction,MNF）对数据进行降维处理,降至m-1维。由m个随机像元作为端元组成凸面体并计算其体积,然后影像中其他像元逐个代替端元重新计算单形体体积[10-12],直到计算出最大体积（图1）。通常影像中的端元位于单形体的顶点,而混合像元则位于单形体结构的内部或者表面上。m个像元形成的单形体的体积计算如式（3）所示。
V ( e 1 , e 2 , ⋯ , e m ) = 1 ( m - 1 ) ! abs det 1 1 ⋯ e 1 e 2 ⋯ 1 e m （3）
式中,ei为表征第i个端元的列向量; V ( e 1 , e 2 , ⋯ , e m ) 是由 e 1 , e 2 , ⋯ , e m 这m个端元所构成的单形体的体积;abs（）为绝对值运算符;det[]为行列式运算符;m为端元个数;m-1为波段数。
Fig. 1 Single shape body of two-dimensional space

图1 二维空间的单形体

该算法虽简单易行,但仍存在缺点,如影像中的所有像元均参与最大体积的计算,对于高光谱数据而言,算法的计算量巨大。在端元提取前,需对数据进行降维处理,降维方法的差异对端元提取的结果造成影响[13-15]。由于初始时m个端元是随机选择的,所以对同一幅影像的多次运算,其提取结果也会有差异。

2.3 结合光谱信息熵改进后的N-FINDR算法

据传统N-FINDR算法理论,端元存在于凸面体的顶点位置,凸面体内部的混合像元在参与计算过程中,会逐步被靠近顶点位置的像元所替代[16-17]。所以,剔除凸面体内部的混合像元,对端元提取的精度不产生影响。在高维空间上,单形体的各个顶点处的像元为一类地物,其像元纯净程度越高,距顶点位置越近,则其像元光谱信息熵值就越小。因此,首先采用光谱信息熵算法对数据进行预处理,提取出影像中相对纯净的像元,这些像元位于单形体各个顶点处,且包含了影像中的全部地物类别;然后,计算其凸面体体积,并提取各个顶点位置像元作为端元。改进的N-FINDR算法的具体过程 如下：
（1）根据统计学原理计算每个像元所有波段的概率,然后根据式（2）计算每个像元的光谱信息熵;
（2）依据计算出的光谱信息熵大小,通过设定阈值的方式获得小于阈值的像元,这些像元即为影像中相对纯净的像元;
（3）把这些纯净像元在高维空间组成凸面体,结合凸面几何学理论,运用传统N-FINDR算法,计算凸面体的最大体积,此最大单形体顶点处的像元即为本文需要提取的端元。
对于同一地区不同时间获取的影像,其像元的DN值会发生变化,但各个像元间的DN值相对大小不变。在高维空间中,DN值的变化会导致单形体的位置发生变化,但组成单形体的像元间相对位置保持不变,即纯净像元依旧位于单形体顶点附近,混合像元位于单形体内部或表面。所以,对同一地区不同时间获取的影像,使用信息熵改进后的N-FINDR算法提取端元应一致。
结合光谱信息熵改进的N-FINDR算法的流程如图2所示。图2中M值表示判断是否为相对纯净像元的光谱信息熵阈值。阈值的选取是本文算法的关键,其值选取的大小关系到端元提取精度和时间效率的平衡问题。如果阈值选取偏小,会造成部分纯净被剔除,导致提取精度降低。如果其值选取偏大,会有更多的混合像元参与到体积计算中,导致时间效率降低。由于不同地区和时间获取的影像差异性较大,故还没有一个具有普适性的阈值选取方法。本文实验部分的阈值选取,首先由传统N-FINDR算法提取影像端元,然后由改进后的N-FINDR算法提取影像端元（此时的M值为像元光谱信息熵最大值与最小值之间的任意值）。对比2次端元提取结果,若改进后的N-FINDR算法端元提取精度低,则适当增大M值,以提高端元提取精度。若2次精度相当,则适当降低M值,以提高时间效率。经多次实验分析表明,本文实验影像M值的选择使得筛选出的相对纯净像元的个数占影像像元总数的5%左右时,提取精度和运算效率都达到最佳。
Fig. 2 Workflow of the improved N-FINDR algorithm

图2 改进N-FINDR算法的流程图

3 实验分析与算法比较

3.1 实验数据

本实验采用美国EO-1卫星的Hyperion高光谱数据。Hyperion是第一个星载民用成像光谱仪,采用了谱像合一技术为使用者提供242个波段,光谱覆盖范围355~2577 nm,传感器空间分辨率30 m,光谱分辨率达10 nm。首先对实验数据进行了定标、无效波段和信噪比较低波段的剔除、大气校正和研究范围剪裁等预处理,经过预处理后影像保留151个波段,图幅大小为400×250像元。研究区域为江西省德兴市某铜矿部分采区（图3）,该区位于怀玉山脉孔雀山下,地形以山地为主,矿产资源十分丰富,其中,铜、铅、锌、钼、金、银的储量较大。该区域的森林覆盖率较高,其中针叶林的面积比重大。
Fig. 3 Hyperion hyperspectral image of a miningarea in Dexing city

图3 德兴矿区Hyperion高光谱遥感影像

3.2 改进N-FINDR算法提取端元

改进的N-FINDR算法采用Matlab编程实现,先用式（2）计算出影像上每个像元的光谱信息熵。同时,根据所选取相对纯净像元的个数（占像元总数的5%）设置光谱信息熵阈值,从中选出5000个相对纯净的像元,对这些相对纯净的像元采用最小噪声分离变换（MNF变换）进行降维处理。并在高维空间形成的单形体上用传统的N-FINDR算法搜索最大体积,根据最大体积的顶点最终取出了9个端元,端元波谱曲线见图4。利用线性波谱分离（Linear Spectral Unmixing）方法得到各个端元的丰度图（图5）。
Fig. 4 Endmember spectra extracted by the improved N-FINDR algorithm

图4 改进N-FINDR法提取的端元光谱

Fig. 5 Inversion maps of the extracted endmember abundance

图5 所提取的端元丰度反演图

由于实验区有植被和矿物,所以,将选出的端元光谱曲线与美国地质勘探局（United States GeologicalSurvey,USGS）光谱库中的数据进行匹配。USGS标准光谱库波长范围400~2500 nm,包括近500种典型的矿物,近红外波长精度为0.5 nm,可见光波长精度为0.2 nm。由于本实验使用的数据与USGS波谱库中的光谱维分辨率不同,需根据Hyperion影像,对USGS波谱库中的波谱库文件进行重采样。完成重采样后进行光谱曲线匹配,采用光谱角制图（SAM）和光谱特征拟合（SFF）,对提取的端元进行相似度分析,匹配值越高代表光谱曲线相似度越高,从而确定各个端元的地物名称,结果如表1所示。
Tab. 1 Analysis of similarity between the extracted endmembers and USGS-library

表1 所提取的端元与USGS波谱库相似度分析

端元编号 Name 中文名称 SAM SFF
1 Staurol 十字石 0.849 0.758
2 Galena 方铅矿 0.781 0.836
3 Juniper 刺柏 0.908 0.756
4 Stilbite 辉沸石 0.866 0.794
5 Epsomite 泻利盐 0.838 0.748
6 Augite 斜辉石 0.859 0.805
7 Hematita 赤铁矿 0.836 0.766
8 Mascagnin 硫铵石 0.769 0.728
9 Cookeite 锂绿泥石 0.868 0.795

3.3 算法的时效对比分析

对改进后N-FINDR算法与传统N-FINDR算法的程序运算时间效率进行对比。本次实验所使用惠普笔记本,处理器为四核AMD A6-3400M APU with Radeon(tm) HD Graphics,1.40 GHz,内存6 G。选取2幅江西德兴矿区的Hyperion高光谱影像,图幅大小分别为100×100像元和400×250像元。对每幅影像进行2组实验,2组实验中计算最大单形体体积时的迭代次数,分别设置为10和50,每组实验进行5次。图幅100×100、400×250像元的时间效率对比结果如表2、3所示。
Tab. 2 Comparison of calculation time for 100×100 pixel image

表2 100×100像元影像的运算时间对比（s）

实验组别 迭代次数10 迭代次数50
N-FINDR 改进的N-FINDR N-FINDR 改进的N-FINDR
1 315.8 19.3 535.7 23.7
2 338.1 18.1 520.6 25.4
3 319.3 18.4 529.4 23.3
4 304.6 19.7 537.9 23.9
5 310.4 19.0 531.6 24.2
Tab. 3 Comparison of calculation time for 400×250 pixel image

表3 400×250像元影像的运算时间对比（s）

实验组别 迭代次数10 迭代次数50
N-FINDR 改进的N-FINDR N-FINDR 改进的N-FINDR
1 952.8 43.3 1558.4 69.4
2 979.3 47.9 1498.4 61.7
3 971.8 50.3 1532.7 73.3
4 980.6 55.7 1626.3 66.7
5 968.7 49.6 1573.6 75.8
结果表明,随着迭代次数的增加,传统N-FINDR的运算时间明显增加,而改进后N-FINDR的运算时间增幅较小。随着图幅的增大,像元数量的增多,改进后的N-FINDR算法其时间效率优于传统N-FINDR算法。
分别用改进后N-FINDR、传统N-FINDR、连续最大角凸锥（Sequential Maximum Angle Convex Cone,SMACC）3种端元提取方法,对实验区域影像做端元提取。改进后N-FINDR、传统N-FINDR算法的迭代次数设为50,SMACC算法的端元波谱数量设为9,选择合并相似端元的波谱。最终应用改进的N-FINDR和传统N-FINDR算法提取出9个端元,SMACC算法提取出7个端元,各算法所提取的端元光谱如图6所示。由于N-FINDR算法初始端元组的随机选择性,使计算出的最大体积不完全相同,从而导致所提取的同一种端元的DN值不同。
Fig. 6 Endmember spectra extracted by improved N-FINDR, traditional N-FINDR and SMACC algorithms

图6 改进的N-FINDR、传统N-FINDR与SMACC算法提取的端元光谱

用3种算法提取出来的端元光谱分别与重采样后的USGS光谱库,进行光谱相似度分析时,由于SAM主要是匹配整体波形的相似性,SFF是对光谱特征波段进行匹配。所以,为有效识别所提取端元的地物类别,故设SAM和SFF的权重分别为0.3和0.7,计算二者加权之和得到最终匹配值。匹配值越高,说明端元提取精度越好,相似度分析结果见表4。由于N-FINDR算法初始端元选择的随机性,导致了改进N-FINDR算法和传统N-FINDR算法提取端元有所不同。传统N-FINDR算法中8号端元的匹配值过低,故标注为Unknown。在SMACC算法中,由于选择了合并相似端元的波谱,所以最后保留7个端元。由表4可知,改进N-FINDR算法和传统N-FINDR算法精度基本相当,SMACC算法的精度低于前2种算法。
Tab. 4 Comparison of accuracy between traditional N-FINDR, improved N-FINDR and SMACC algorithms for endmember extraction

表4 传统N-FINDR、改进的N-FINDR与SMACC算法提取端元的精度比较

提取算法 端元1 端元2 端元3 端元4 端元5 端元6 端元7 端元8 端元9
N-FINDR 十字石0.744 赤铁矿0.791 锂绿泥石0.832 刺柏0.793 斜辉石0.795 泻利盐0.770 辉沸石0.845 硫铵石0.837 未知
改进的N-FINDR 十字石0.785 赤铁矿0.787 锂绿泥石0.817 刺柏0.802 斜辉石0.821 泻利盐0.775 辉沸石0.816 硫铵石0.74 方铅石0.82
SMACC 十字石0.753 赤铁矿0.741 锂绿泥石0.615 刺柏0.674 斜辉石0.579 海绿石0.586 方铅石
0.683

4 结语

端元提取作为高光谱影像分析的重要前提,仅仅保证提取精度已不能满足现在大数据时代的要求,应在算法提取结果精度可靠的前提下,优化其时间效率。本文在传统N-FINDR算法的基础上,结合光谱信息熵理论增加了数据预处理机制。通过设置光谱信息熵的阈值,筛选出数据中相对纯净的像元,然后对相对纯净的像元计算单形体最大体积来提取端元。
改进的N-FINDR算法,保留了传统N-FINDR算法的无参数、端元提取精度高等优点。通过对影像中相对像元的筛选,优化了传统N-FINDR算法的时间效率。经过对Hyperion数据的反复实验,验证改进后的算法可行。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Winter M E.N-FINDR: An algorithm for fast autonomous spectral endmember determination in hyperspectral data[C]. International Society for Optical Engineering, International Symposium on Optical Science, Engineering, and Instrumentation. Denver, USA, 1999,3753:266-275.

[2]
Boardman J W, Kruse F A, Green R O.Mapping target signatures via partial unmixing of AVIRIS data[C]. Fifth JPL Airborne Earth Science Workshop, Pasadena, USA, 1995:23-26.

[3]
Neville R A, Staenz K, Szeredi T.Automatic endmembers extraction from hyperspectral data for mineral exploration[C]. 21st Canadian Symposium on Remote Sensing, Ottawa, Canada, 1999:21-24.

[4]
Chang C I, Wu C C, Liu W M, et al.A new growing method for simplex-based endmember extraction algorithm[J]. IEEE Transactions on Geoscience and Remote Sensing, 2006,44(10):2804-2819.

[5]
Nascimento J M P, Dias J M B. Vertex component analysis: A fast algorithm to unmix hyperspectral data[J]. IEEE Transactions on Geoscience and Remote Sensing, 2005,43(4):898-910.

[6]
郝虑远,孙睿,谢东辉,等.基于改进N-FINDR算法的华北平原冬小麦面积提取[J].农业工程学报,2013,29(15):153-161.

[7]
唐晓燕,高昆,倪国强,等.基于流形学习和空间信息的改进N-FINDR端元提取算法[J].光谱学与光谱分析,2013,33(9):2519-2524.

[8]
Shannon C E. A mathematical theory of communication[J]. The Bell System Technical Journal, 1948,27:379-423, 623-656.

[9]
杨可明,刘士文,王林伟,等.光谱最小信息熵的高光谱影像端元提取算法[J].光谱学与光谱分析,2014,34(8):2229-2233.

[10]
Junmin Liu, Jiangshe Zhang.A New Maximum Simplex Volume Method Based on Householder Transformation for Endmember Extraction[J]. IEEE Transactions on Geoscience and Remote Sensing, 2012,50(1):104-118.

[11]
赵春晖,齐滨,王玉磊.一种改进的N-FINDR高光谱端元提取算法[J].电子与信息学报,2012,34(2):499-503.

[12]
李二森,朱述龙,周晓明,等.高光谱图像端元提取算法研究进展与比较[J].遥感学报,2011,15(4):659-679.

[13]
路漫漫. 融合PSO的N-FINDR改进端元提取算法研究[D].大连:大连海事大学,2014.

[14]
张兵,高连如.高光谱图像分类与目标探测[M].北京:科学出版社,2011:102-104.

[15]
齐滨. 高光谱图像分类及端元提取方法研究[D].哈尔滨:哈尔滨工程大学,2012.

[16]
Winter M E.A proof of the N-FINDR algorithm for the automated detection of endmembers in a hyperspectral image[C]. Defense and Security, International Society for Optics and Photonics, 2004:31-41.

[17]
朱述龙,齐建成,朱宝山,等.以凸面单体边界为搜索空间的端元快速提取算法[J].遥感学报,2010,14(3):482-292.

Options
Outlines

/

〈 〉