基于矢量量化的高光谱图像有损压缩算法可以获得较高的压缩比,但是其时间复杂度高,失真较大. 为此,提出了模拟退火优化模糊C均值聚类(FCM)的高光谱图像有损压缩算法. 先对高光谱图像进行自适应波段合并算法降维,利用肘部现象确定量化级数,结合模拟退火的全局寻优能力和模糊聚类的快速收敛能力,找到最优解后恢复维度,最后去模糊优化编码方案. 通过这种方法,在提高高光谱图像压缩运算效率和减小解压后失真方面都有了较大的优化,是基于矢量量化的高光谱图像压缩的可行方法.
Lossy compression of hyperspectral image based on vector quantization algorithms can achieve a high compression ratio, but it is of time complexity and great distortion. This article proposed a new fuzzy C-means clustering (FCM) algorithm based on simulated annealing. Firstly, the dimensions were reduced by using the algorithm of adaptive band combination dimensional reduction (ABC), then the number of clusters with the elbow was determined. FCM was combined with simulated annealing, and found optimal result quickly, then recovered dimensions. We got optimization coding by deblurring U. Through this approach, the efficiency has been improved and the distortions have been reduced greatly.
高光谱图像(HI，hyperspectral image)指的是光谱的分辨率在数量级10-2λ范围内的光谱图像. 随着光谱分辨率、空间分辨率以及时间分辨率的不断提高，成像光谱仪获取的高光谱图像数据量越来越大，给数据的存储和传输带来了很大困难. 由于数据必须在卫星可测控范围内才能传输，除数据量庞大外，有限的传输时间也对高光谱图像压缩技术提出了更高的要求. 矢量量化是一种高效的有损压缩方法，它具有压缩比大、失真小、解码简单等优点，被广泛应用于语音和图像的压缩.
Singh等[1]、Motta等[2]、Kim等[3]改进了模糊C均值聚类(FCM，fuzzy C-means clustering)的相关算法. Qian等[4]提出了2种代表性的基于位运算的矢量量化算法. Zhao等[5]利用自组织特征映射神经网络算法对变换后的图像进行矢量量化. Liu等[6]提出了点阵矢量量化(LVQ)与四叉树排序算法相结合的算法. Chen等[7]和Wang等[8]描述了聚类算法在矢量量化中的优化应用.
1 FCM聚类算法FCM用隶属度数值来确定一个样本对每个聚类的属于程度. FCM的目的是在n个样本下找到c个模糊组，以及对应的隶属度矩阵U，使得代价函数达到最小.
FCM中引入了模糊划分的思想，即一个样本不单单只属于一个类. 每个样本的c个隶属度数值都在区间内，并且需要将其归一化，即隶属度矩阵需要满足
| $\sum\limits_{i=1}^{c}{u\left( i,j \right)=1,\ \ j=1,2,\ldots ,n}$ | (1) |
FCM的代价函数J一般化形式为
| $J\left( U,{{c}_{1}},{{c}_{2}},\ldots {{c}_{c}} \right)=\sum\limits_{i=1}^{c}{\sum\limits_{j=1}^{c}{u_{ij}^{m}}}d_{ij}^{2}$ | (2) |
其中：表示第i个模糊类的聚类中心；uij表示第j个样本对第i个聚类中心的隶属度数值；dij表示第i个聚类与第j个样本之间的欧氏距离；m为加权指数，取值区间为[2,+∞).
通过拉格朗日乘数法构造代价函数为
| $\begin{align} & J\left( U,{{c}_{1}},c2,\ldots {{c}_{c}},{{\lambda }_{1}},{{\lambda }_{2}},\ldots ,{{\lambda }_{n}} \right)= \\ & \sum\limits_{i=1}^{c}{\sum\limits_{j=1}^{c}{u_{ij}^{m}}}d_{ij}^{2}+\sum\limits_{j=1}^{c}{{{\lambda }_{j}}}\left( \sum\limits_{i=1}^{c}{{{u}_{ij}}-1} \right) \\ \end{align}$ | (3) |
为了使代价函数取最小值，对输入的参数求导，得到
| ${{c}_{i}}=\frac{\sum\limits_{j=1}^{n}{u_{ij}^{m}{{x}_{j}}}}{\sum\limits_{j=1}^{n}{u_{ij}^{m}}}$ | (4) |
| ${{u}_{ij}}=\frac{1}{\sum\limits_{k=1}^{c}{{{\left( \frac{{{d}_{ij}}}{{{d}_{kj}}} \right)}^{\left( \frac{2}{m-1} \right)}}}}$ | (5) |
FCM算法流程如下：
1) 初始化U，随机产生一个c×n的矩阵，矩阵的数值uij都属于［0,1]，并将其作归一化处理；
2) 利用式(4)求得c个聚类中心；
3) 利用式(2)计算代价函数，若算法满足以下3个条件之一则算法终止：迭代次数满足要求、代价函数满足某一阈值、代价函数结果收敛；
4) 利用式(5)更新U的值，并返回第2)步.
FCM算法是一种局部寻优算法，对初始值具有依赖性，且计算复杂，运算时间长；隶属度矩阵U的数值存储问题导致了压缩比的降低. 以上的这些问题，都限制了FCM算法的实际应用.
2 模拟退火优化算法模拟退火算法(SA，simulated annealing)是从较高温出发，逐渐降温，结合概率突跳特性，依概率在解空间找到目标函数的全局最优解.
根据Metropolis准则，粒子在温度T下，逐渐趋于平衡的概率为$P={{e}^{-\frac{\Delta E}{KT}}}$. 其中e表示自然指数，E表示固体中粒子在温度T下的内能，ΔE表示降温前后内能的改变量，k表示Boltzmann常数. 模拟退火算法正是利用了Metropolis准则，以概率p接受比当前状态更差的状态改变，通过这种方式，只要退火速度足够缓慢，则该算法依概率一定能跳出局部最优解，找到全局最优解.
经典的模拟退火算法描述如下：
1) 初始化温度T，确保T足够大，初始化解状态S作为算法迭代起点，设置每个T值的迭代次数为K；
2) 重复K次执行3)~6)步；
3) 产生新状态S′；
4) 计算增量ΔE=E(S′)-E(S)，其中E(S)为评价函数；
5) 若ΔE＜0则接受S′作为新的当前状态，否则以概率$P={{e}^{-\frac{\Delta E}{KT}}}$接受S′作为新的当前解；
6) 如果当前状态的评价函数E(S)满足终止条件，或者连续若干个新解都没有被接受时，则输出当前状态作为最优解，结束程序；
7) T逐渐减小，若T大于常温，执行第2)步.
3 模拟退火优化FCM聚类的矢量量化算法目前，基于模拟聚类的高光谱图像压缩算法通常具有计算复杂、容易陷入局部最优解而导致失真较大的问题. 直接采用模拟退火虽然可以解决陷入局部最优解的问题，但是直接又会导致计算量的急剧上升. 因此亟须寻找一种合理的方法以解决这些问题.
3.1 确定量化级数对于基于矢量量化的压缩算法而言，首先要确定量化级数，即聚类数目. Andrew N指出在K-Means算法中，尝试不同的聚类数目时，目标函数会呈现出类似于反比例函数的图像，其中存在着一种肘部现象. 即存在一个拐点，在拐点左侧，随着自变量增加，目标函数值迅速下降；拐点右侧，随着自变量增加，目标函数值下降缓慢，趋于收敛. 这个拐点称为肘部点. 这种肘部现象同样会出现在模糊聚类中. 因此可以利用该现象选择最优量化级数.
3.2 自适应波段合并降维高光谱图像具有较高的谱间冗余，在矢量量化的计算中，这将使得无谓的增加许多计算量. 考虑谱间相关性，可以极大的增加量化效率.
在谱间相关性的计算中，采用
| $\frac{\begin{align} & {{R}_{i,j}}\left( x,y \right)= \\ & \sum\limits_{x=1}^{M}{\sum\limits_{y=1}^{N}{\left( {{f}_{i}}\left( x,y \right)-\overline{{{f}_{i}}} \right)\left( {{f}_{i}}\left( x,y \right)\overline{{{f}_{i}}} \right)}} \\ \end{align}}{\sqrt{\left( \sum\limits_{x=1}^{M}{\sum\limits_{y=1}^{N}{{{\left( {{f}_{i}}\left( x,y \right)-\overline{{{f}_{i}}} \right)}^{2}}}} \right)}\left( \sum\limits_{x=1}^{M}{\sum\limits_{y=1}^{N}{{{\left( {{f}_{i}}\left( x,y \right)-\overline{{{f}_{i}}} \right)}^{2}}}} \right)}$ | (6) |
其中：σi是第i个波段标准差，Ri,j是i和j 2个波段间的相关系数.
笔者采用自适应波段合并降维法[9]，具体步骤如下：
1) 从第1波段开始，按式(6)顺序计算第1波段与其后波段的相关系数. 令符合式(7)的波段合并为一组；
| $\left. \begin{align} & {{R}_{ij}}\ge T,j=i+1,i+2,\ldots ,i+k \\ & {{R}_{i}}\left( i+k+1 \right)T \\ \end{align} \right\}$ | (7) |
2) 对同组的波段采用式(8)合并；
| ${{\text{g}}_{\text{i}}}\left( x,y \right)=\frac{{{f}_{1}}\left( x,y \right)+{{f}_{2}}\left( x,y \right)+\ldots +{{f}_{k}}\left( x,y \right)}{k}$ | (8) |
其中：f(x,y)为每个波段组里各波段像素，k为组内波段数，gi(x,y)为第i个波段组的平均值；
3) 将各波段组的均值gi(x,y)组成的3维矩阵P，即为原始高光谱图像降维后的图像数据.
| $P=\left[\begin{align} & {{\text{g}}_{1}}\left( x,y \right) \\ & \ \ \ \ \ \vdots \ \ \ \ \ \\ & {{\text{g}}_{m}}\left( x,y \right) \\ \end{align} \right],mn$ | (9) |
对P运用FCM算法获得最优量化的分组结果，丢弃降维数据的聚类中心C，并将分组信息U代入原始图像进行量化压缩. 在维度下降后处理数据方便快速，但是由于在图像处理完成后需要解压，所以需要考虑维度复原的问题，笔者采用了图 1所示的方法进行了维度复原.
|
图1 维度下降与复原示意图 |
传统的模拟退火流程在第2节已描述，此处考虑将其与FCM算法的结合和具体的算法设计.
1) 模拟退火中的冷却进度表设计. 冷却进度表设计的好坏关系着降温的快慢和Metropolis准则的判定的效率. 笔者设置一种简单的线性降温表，设定初始温度为100，最低温度为1，降温曲线为T′=0.9T. 这种冷却进度表，计算简单，而且初始阶段降温较快，之后逐渐减慢，能帮助算法尽快收敛，在后期能帮助调整状态.
2) 扰动策略的选择. 模拟退火的过程中有一步为等温状态，在这步中系统内部会发生热交换，但温度不变. 笔者选择的扰动策略为改变聚类中心矩阵C，参考遗传算法的交叉变异，将最大与最小的5%个类对应的聚类中心做出随机调整，一方面用于模拟退火的随机扰动，另一方面可以防止聚类时出现空胞，使聚类趋于均匀.
3) 模拟退火与FCM算法的结合. 笔者算法是结合了模拟退火算法的全局寻优能力和FCM算法的快速收敛能力而产生的一种优化方法. 所以在传统的等温状态下的k次扰动结束后，需要执行k次FCM迭代确保算法的快速收敛.
4) 由于模拟退火算法需要进行随机扰动，所以存在一定概率在找到最优解后又会因为扰动而丢失这个最优解，所以需要记录一个Best so far的状态. 这个状态包括当前的隶属度矩阵U、聚类中心矩阵C.
4 实验结果及分析笔者研究所用的高光谱数据，为中国环境与灾害监测小卫星星座A上搭载的高光谱成像仪获取的数据HJ1A和Hyperion光谱成像仪拍摄的EO1H图像数据.
先确定图像量化级数，以均方误差(MSE)为目标函数，对HJ1A和EO1H寻找肘部现象，如图 2所示.
|
图2 遥感图像肘部现象 |
从图 2中，可以大致看出，对于不同数据源的遥感图像，综合考虑计算效率和均方误差，找到的肘部点位置基本一致，都处在1 000左右，因此选取1 024作为高光谱遥感图像数据的量化级数是可行的.
对实验数据分别作传统的FCM算法、PCA降维的LBG算法(PCA-LBG)和自适应波段合并降维的模拟退火优化FCM算法(ABCSA-FCM)，参考运行时间和峰值信噪比(PSNR)，得表1所示的结果.
 | 表1 实验效果 |
从表1可以看出，模拟退火优化后的FCM算法在峰值信噪比方面提高了约3 dB，而且由于事先进行了降维处理，虽然增加了模拟退火的计算量，但是在运算时间方面依然降低了1/3到1/2左右. 与传统的PCA降维的FCM算法相比较，信噪比提高了约5 dB.
图3(a)是高光谱图像HJ1A的第56波段原图，图3(b)是经过传统FCM算法压缩解压后的效果图，图3(c)是经过目前主流的PCA降维和LBG算法处理后的效果图，图3(d)是经过自适应波段合并降维的模拟退火优化FCM算法压缩解压后的效果图. 可以明显看到，PCA-FCM算法压缩后的图像河流变得不够清晰，对于右侧河流区域，传统FCM算法解压完后呈现出模糊状，通过笔者算法解压后的结果，河流的显示明显优于传统FCM，效果接近原图.
|
图3 HJ1A第56波段优化前后压缩效果图 |
由以上实验结果得出，软聚类算法FCM在提高信噪比，降低失真方面，比传统的LBG算法有较大的优势，但是随之带来的计算效率的降低也十分明显；ABCSA-FCM算法相比于传统FCM算法，由于模拟退火较强的全局寻优能力，使得在提高信噪比方面获得了进一步的提升，提出的自适应波段合并算法(ABC，adaptive band combination dimensional reduction)降维在降低运算量方面也有所提高，但是和传统的主流算法比较，运算时间还存在较大的差距，FCM的快速算法还有待进一步的研究. 总的来说，ABCSA-FCM在高光谱图像压缩的提高失真方面有着明显的优势，在研究图像压缩方面存在着积极的意义.
| [1] | Singh K, Mehrotra A, Nigam P. Unsupervised change detection from remote sensing images using hybrid genetic FCM[J]. Engineering and Systems(SCES), 2013: 1-5.[引用本文:1] |
| [2] | Motta G, Rizzo F, Storer J A. Compression of hyperspectral imagery[C]//Proceedings of Data Compression Conference. [S.l.]: Int Conf on E-business and Telecommunication Networks, 2003.[引用本文:1] |
| [3] | Kim W, Pedrycz W. A design of FCM-based interval type-2 fuzzy neural network classifier with the aid of PSO[C]//IFSA World Congress and NAFIPS Annual Meeting(IFSA/NAFIPS). [S.l.]: Ifsa World Congress and Nafips Meeting, 2013, 164(2): 1209-1214.[引用本文:1] |
| [4] | Qian Shenen, Hollinger A B, Williams D, et al. Vector quantization using spectral index-based multiple subcode-books for hyperspectral data[J]. IEEE Transactions on Geoscience Electronics, 38(3): 1183-1190.[引用本文:1] |
| [5] | Zhao Chunhui, Chen Wanhai, Zhang Lingyan. A compression algorithm of hyperspectral remote sensing image based on vector quantization[J]. Journal of Harbin Engineering University, 2006, 27(3): 447-452.[引用本文:1] |
| [6] | Liu Ying, Pearlman W. Compression of hyperspectral images with LVQ-SPECK[C]//Data Compression Conference. 2008: 25-27.[引用本文:1] |
| [7] | Chen Yushi, Zhang Ye, Gu Yanfeng. Fast VQ algorithm for hyperspectral image compression based on feature selection[J]. Journal of Harbin Engineering University, 2007, 39(11): 1748-1750.[引用本文:1] |
| [8] | Wang Xin, Huang Zhongyi. Network resource personalized recommendation based on K-means clustering[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37.[引用本文:1] |
| [9] | Zhao Xuejun, Yu Kaimin, Wang Xiaojuan. Adaptive band combination dimensional reduction based on point of accumulation for hyperspectral image[J]. Journal of Information and Computational Science, 2015,12(11): 4479-4486.[引用本文:1] |