近年来，高光谱遥感已经广泛应用于许多领域，相关的高光谱处理技术也迅猛发展。混合像元的存在使基于像元级的遥感分类和面积计算精度难以达到很好的效果。为提高高光谱遥感应用的精度，首先需要解决混合像元分解^[1]。光谱分离技术就是把混合像元分解成端元，并计算端元的丰度，使高光谱波段信息由像元级达到亚像元级。混合像元分解的流程主要有数据降维、端元提取和丰度估计，其中关键是端元提取。目前端元提取的算法主要有：像元纯度指数^[2](pixel purity index，PPI)、N-FINDR算法^[3]、迭代误差分析^[4](iterative error analysis, IEA)、自动形态学端元提取^[5](automated morphological endmember extraction, AMEE)、凸锥分析^[6](convex cone analysis, CCA)、顶点成分分析^[7](vertex component analysis, VCA)、单体增长算法^[8](simplex growing algorithm, SGA)、离散粒子群优化算法^[9](discrete particle swarm optimization, D-POS)等。N-FINDR算法由于无参数，操作简单，提取效果较好等优点被广泛应用。

本文在分析凸面单形体模型及传统N-FINDR的基础上，针对传统N-FINDR算法时间复杂度高等缺点，提出了一种改进的N-FINDR算法，即CIN-FINDR算法。

1 基于N-FINDR的相关算法 1.1 N-FINDR算法

N-FINDR算法是根据凸面几何学理论，通过寻找体积最大的单形体来自动获取图像中的所有端元^[1]。在误差项很小的情况下，满足线性混合模型的所有点的集合正好构成一个高维空间的凸集，而端元则位于凸集单形体的顶点。以两波段三个端元为例来说明它们之间的几何关系，如图 1所示。

原始N-FINDR算法采用全局搜索需遍历C_N^p=N!/[(N-p)!p!](N表示像元数，p表示端元个数)。由于影像中像元数量巨大，采用全局搜索非常费时，为此，相关学者对原N-FINDR算法进行改进，提出了串型N-FINDR算法(SQ N-FINDR)及并型N-FINDR算法(SC N-FINDR)等^[2-8]。通过分析可知，串型N-FINDR算法的时间复杂度为N×p²，而并型N-FINDR算法的时间复杂度为N×(p (p+1) /2)。

1.2 迭代N-FINDR算法(IN-FINDR)^[9]

相关学者对N-FINDR算法进行改进，多次选择初始端元进行迭代计算，提出了迭代N-FINDR算法(IN-FINDR)。算法的基本思想是：采用SQ N-FINDR算法或SC N-FINDR算法提取的端元作为初始端元，然后迭代运算至连续两次运算所得的单形体体积不变为止。具体算法如下：

1) 设置迭代次数，并估计端元数p。

2) 数据降维：用最小噪声分离(minimum noise fraction, MNF)变换将高光谱数据从L降维至p-1，其中，L表示波段数。

3) 初始化条件：在影像数据中随机初始化端元组合{e₁⁽⁰⁾ , e₂⁽⁰⁾ , …, e_p⁽⁰⁾ }，令迭代数k=1。

4) 外循环：当迭代数k≥0时，根据式(1) 计算单形体S (e₁^(k), e₂^(k), …, e_p^(k))的体积V (e₁^(k), e₂^(k), …, e_p^(k))。

$V\text{ }({{e}_{1}},\text{ }{{e}_{2}},\text{ }\ldots ,{{e}_{p}})=\frac{\left| \text{det}\left[ \begin{matrix} 1 & 1 & \ldots & 1 \\ {{e}_{1}} & {{e}_{2}} & \ldots & {{e}_{p}} \\ \end{matrix} \right] \right|}{\left( p-1 \right)!}$

(1)

5) 内循环：对于1≤j≤p，计算V (e₁^(k), …, e_j-1^(k), r, e_j+1^(k), …, e_p^(k))，如果计算的体积V (r, e₂^(k), …, e_p^(k))，V (e₁^(k), r, e₃^(k), …, e_p^(k))，…，V (e₁^(k), …, e_p-1^(k), r)小于V (e₁^(k), e₂^(k), …, e_p^(k))，那么p端元都没有替换，算法终止；否则继续。

6) 替换原则：基于端元所组成的单形体体积大，如果V (r, e₂^(k), …, e_p^(k))，V (e₁^(k), r, e₃^(k), …, e_p^(k))，…，V (e₁^(k), …, e_p-1^(k), r)大于原端元体积，则被替代。假设端元用e_j^(k+1) 表示，则e_j^(k+1) =r, e_i^(k+1) =e_i^(k), j≠i。令k←k+1，返回至步骤4)。

1.3 候选像元的迭代N-FINDR算法

为解决候选像元数量大的问题，结合端元坐标的高光谱影像端元提取方法的思想^[10]，本文提出了候选像元的迭代N-FINDR算法(CIN-FINDR)。CIN-FINDR算法的基本思想是：在进行IN-FINDR算法运算前，对候选像元进行预选择，将明显是混合像元的数据在样本中进行剔除，从而减少候选像元的样本数，然后再从预选择后的像元中进行IN-FINDR算法运算。其具体算法是在迭代N-FINDR算法的第1) 步前增加如下步骤：选取候选像元：根据凸面几何性质，端元总是落在每一维的最小最大位置(如图 2所示)。基于这个原理，同时考虑噪声的影响，在经过预处理的高光谱数据中寻找出第i维数据中的最大值max_i和最小值min_i。提取边缘距离d_i=k×(max_i-min_i)，k为常数，本实验中k取0.1。那么候选像元区域为(min_i, min_i+d_i)和(max_i-d_i, max_i)，i=1, 2, …, p。其余步骤同迭代N-FINDR算法。

其流程图如图 3所示。

2 实验与结果分析 2.1 实验数据

为了更好地评价算法的有效性，实验采用模拟数据和真实高光谱数据两种数据。模拟数据采用USGS光谱库^[11]中的Alunite (A)、Buddingtonite (B)、Calcite (C)、Kaolinite (K)、Muscovite (M)等5种光谱作为端元构建大小为200像素×200像素共224个波段的模拟图像，光谱范围为0.38~2.5 μm，光谱分辨率为10 nm，其光谱曲线如图 4所示。模拟图像的背景为5种光谱的均值，并构建25个模块，每一列的模块有相同的尺寸，如图 5所示。模拟数据的具体构建情况参见文献[12]。最后在模拟图像中添加均值为零、信噪比SNR=30的高斯噪声。

真实数据为2011-08获取的内华达州Cuprite采矿区的AVIRIS数据(图 6)。该数据大小为350像素×350像素，共有224个波段(0.36~2.5 μm)，空间分辨率为15.5 m，光谱分辨率为10 nm。由于水蒸汽吸收和低信噪比去除1~3、105~115、150~170波段，实验中使用189个波段。经过大气校正，反射率转换得到反射率数据。

2.2 模拟数据实验结果及分析

考虑到算法的随机性，本次实验共分为5组，每组实验分别采用SQ N-FINDR算法、SC N-FINDR算法、IN-FINDR算法和CIN-FINDR算法进行端元提取。其中IN-FINDR算法与CIN-FINDR算法的迭代系数设为15，实验结果如表 1所示。

从端元位置分析，在理想条件下，4种算法都能够准确地搜寻出端元，但SC N-FINDR算法的随机性强，其寻找的端元稳定性较差。从单形体体积分析，SC N-FINDR算法搜寻出的端元的单形体体积比其他3种算法小，稳定性差。从运行时间分析，IN-FINDR算法是SQ N-FINDR算法(或SC N-FINDR算法)的3倍，通过分析可知，IN-FINDR多次迭代必然会增加运行时间，但得到的端元更可靠；CIN-FINDR算法的运算时间约为IN-FINDR算法的1/50，SQ N-FINDR算法(或SC N-FINDR算法)的1/20。因此，实验结果表明，CIN-FINDR算法能够有效地减少运行时间，同时又有IN-FINDR算法稳定性强的特点。

2.3 真实数据实验结果及分析

实验中端元数目设为p=8。首先将实验分成两组，每组实验分别采用SQ N-FINDR算法、SC N-FINDR算法、IN-FINDR算法和CIN-FINDR进行端元提取，每种算法运行10次，实验结果如表 2所示。

从单形体体积分析，在实际的高光谱数据中采用IN-FINDR算法和CIN-FINDR算法的稳定性好，能够较好地搜寻出端元，但同时由于实际地物中很难确定端元个数，因此算法会出现误差，导致搜寻的端元不准确。从运行时间分析，CIN-FINDR算法搜寻出端元的时间更短，约为SQ N-FINDR算法(或SC N-FINDR算法)的1/7, IN-FINDR算法的1/25。

3 结束语

在端元提取时，采用CIN-FINDR算法时间效率明显优于IN-FINDR算法，算法的稳定性比SQ N-FINDR算法(或SC N-FINDR算法)更高，能够更有效地寻找出端元。但是CIN-FINDR算法的不足之处就是对端元数目较敏感，不同端元的数目值对搜寻端元的结果影响较大。因此，在算法运行前，对端元个数的估计显得非常重要。