Fast implementation of kernel simplex volume analysis based on modified Cholesky factorization for endmember extraction

Jing LI; Xiao-run LI; Li-jiao WANG; Liao-ying ZHAO

doi:10.1631/FITEE.1500244

Your Location：

Home >

Browse articles >

Fast implementation of kernel simplex volume analysis based on modified Cholesky factorization for endmember extraction

Regular Papers | Updated：2022-05-19

- Fast implementation of kernel simplex volume analysis based on modified Cholesky factorization for endmember extraction
- 基于改进Cholesky分解的快速核单形体体积分析端元提取算法
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 3, Pages: 250-257(2016)
- Affiliations：
  
  1College of Electrical Engineering, Zhejiang University, Hangzhou 310027, China
  2Institute of Computer Application Technology, Hangzhou Dianzi University, Hangzhou 310018, China
- Author bio：
  
  E-mail: lxr@zju.edu.cn
- Funds：
- DOI：10.1631/FITEE.1500244
  CLC： TP75
- Received：31 July 2015，
  
  Accepted：16 October 2015，
  
  Published：2016-03
- Accepted：
Scan QR Code
Jing LI, Xiao-run LI, Li-jiao WANG, et al. Fast implementation of kernel simplex volume analysis based on modified Cholesky factorization for endmember extraction[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(3): 250-257.
DOI：

Jing LI, Xiao-run LI, Li-jiao WANG, et al. Fast implementation of kernel simplex volume analysis based on modified Cholesky factorization for endmember extraction[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(3): 250-257. DOI： 10.1631/FITEE.1500244.

摘要

目的

端元提取是高光谱图像处理中的关键步骤。研究表明，核单形体增长算法（KNSGA）是一种较好的非线性端元提取算法。然而，该算法存在两个主要问题，限制了其性能。第一，随机初始化导致算法结果不稳定；第二，算法中反复计算单形体体积导致算法时间复杂度较高。本文针对这两个问题，提出改进算法，以提高算法稳定性并降低算法时间复杂度。

创新点

本文提出采用空间像元纯度指数（SPPI）来确定KNSGA算法中的初值，提高了算法的稳定性。此外，对于KNSGA中耗时的单形体体积计算，利用改进的Cholesky分解的思想，将求单形体体积最大值转化为寻找矩阵对角元素最大值，进而降低了算法的时间复杂度。

方法

SPPI越小，则像素的纯度越高，因此将具有最小SPPI的像素作为KNSGA的初始值。原始的KNSGA提取端元的过程是循环计算单形体体积值，即每增加一个端元则计算一次端元构成的单形体体积值，直至找到所有端元为止；利用改进的Choelsky分解的快速实现算法，只需在所有端元都找到之后进行一次单形体体积计算。改进后的算法简化了算法的运算复杂度，加快了算法的实现过程。

结论

本文研究针对KNSGA的改进加速算法，利用SPPI解决初值问题，利用Cholesky分解降低计算时间复杂度。实验结果表明，提出的改进算法在算法稳定性和效率上相比原算法都有一定程度提高。

Abstract

Endmember extraction is a key step in the hyperspectral image analysis process. The kernel new simplex growing algorithm (KNSGA)

recently developed as a nonlinear alternative to the simplex growing algorithm (SGA)

has proven a promising endmember extraction technique. However

KNSGA still suffers from two issues limiting its application. First

its random initialization leads to inconsistency in final results; second

excessive computation is caused by the iterations of a simplex volume calculation. To solve the first issue

the spatial pixel purity index (SPPI) method is used in this study to extract the first endmember

eliminating the initialization dependence. A novel approach tackles the second issue by initially using a modified Cholesky factorization to decompose the volume matrix into triangular matrices

in order to avoid directly computing the determinant tautologically in the simplex volume formula. Theoretical analysis and experiments on both simulated and real spectral data demonstrate that the proposed algorithm significantly reduces computational complexity

and runs faster than the original algorithm.

关键词

Keywords

references

J.W Boardman , , , F.A Kruse , , , R.O Green . . Mapping target signatures via partial unmixing of AVIRIS data . . 1995 . . JPL Airborne Earth Science Workshop . . 23 - - 26 . . . .

C.I Chang , , , Q Du . . Estimation of number of spectrally distinct signal sources in hyperspectral imagery . . IEEE Trans. Geosci. Remote Sens. , , 2004 . . 42 ( ( 3 ): ): 608 - - 619 . . DOI: 10.1109/TGRS.2003.819189 http://doi.org/10.1109/TGRS.2003.819189 . .

C.I Chang , , , C Wu , , , W Liu , , , 等 . . A new growing method for simplex-based endmember extraction algorithms . . IEEE Trans. Geosci. Remote Sens. , , 2006 . . 44 ( ( 10 ): ): 2804 - - 2819 . . DOI: 10.1109/TGRS.2006.881803 http://doi.org/10.1109/TGRS.2006.881803 . .

J.T Cui , , , J Wang , , , X.R Li , , , 等 . . Endmember extraction algorithm based on spatial pixel purity index . . J. Zhejiang Univ. (Eng. Sci.) , , 2013 . . 47 ( ( 9 ): ): 1517 - - 1523 . . DOI: 10.3785/j.issn.1008-973X.2013.09.002 http://doi.org/10.3785/j.issn.1008-973X.2013.09.002 . .

S.W Dowler , , , R Takashima , , , M Andrews . . Reducing the complexity of the N-FINDR algorithm for hyperspectral image analysis . . IEEE Trans. Image Process. , , 2013 . . 22 ( ( 7 ): ): 2835 - - 2848 . . DOI: 10.1109/TIP.2012.2219546 http://doi.org/10.1109/TIP.2012.2219546 . .

X.R Geng , , , Y.C Zhao , , , F.X Wang , , , 等 . . A new volume formula for a simplex and its application to endmember extraction for hyperspectral image analysis . . Int. J. Remote Sens. , , 2010 . . 31 ( ( 4 ): ): 1027 - - 1035 . . DOI: 10.1080/01431160903154283 http://doi.org/10.1080/01431160903154283 . .

X.R Geng , , , Z.Q Xiao , , , L.Y Ji , , , 等 . . A Gaussian elimination based fast endmember extraction algorithm for hyperspectral imagery . . ISPRS J. Photogr. Remote Sens. , , 2013 . . 79 ( ( 5 ): ): 211 - - 218 . . DOI: 10.1016/j.isprsjprs.2013.02.020 http://doi.org/10.1016/j.isprsjprs.2013.02.020 . .

P.E Gill , , , W Murray . . Newton-type method for unconstrained and linearly constrained optimization . . Math. Programm. , , 1974 . . 7 ( ( 1 ): ): 311 - - 350 . . DOI: 10.1007/BF01585529 http://doi.org/10.1007/BF01585529 . .

P.E Gill , , , W Murray , , , M.H Wright . . Practical Optimization , , 1981 . . : : London Academic Press , , . .

G.H Golub , , , Loan, C.F van . . Matrix Computations , , 1996 . . : : Baltimore, Mariland The John Hopkins University Press , , . .

J.M Liu , , , J.S Zhang . . A new maximum simplex volume method based on householder transformation for endmember extraction . . IEEE Trans. Geosci. Remote Sens. , , 2012 . . 50 ( ( 1 ): ): 104 - - 118 . . DOI: 10.1109/TGRS.2011.2158829 http://doi.org/10.1109/TGRS.2011.2158829 . .

L Miao , , , H Qi . . Endmember extraction from highly mixed data using minimum volume constrained nonnegative matrix factorization . . IEEE Trans. Geosci. Remote Sens. , , 2007 . . 45 ( ( 3 ): ): 765 - - 777 . . DOI: 10.1109/TGRS.2006.888466 http://doi.org/10.1109/TGRS.2006.888466 . .

SA NA . . NASA AVIRIS Data . . 1997 . . Available from: http://aviris.jpl.nasa.gov http://aviris.jpl.nasa.gov . .

J.M.P Nascimento , , , J.M Bioucas-Dias . . Vertex component analysis: a fast algorithm to unmix hyperspectral data . . IEEE Trans. Geosci. Remote Sens. , , 2005 . . 43 ( ( 4 ): ): 898 - - 910 . . DOI: 10.1109/TGRS.2005.844293 http://doi.org/10.1109/TGRS.2005.844293 . .

J.M.P Nascimento , , , J.M Bioucas-Dias . . New developments on VCA unmixing algorithm . . SPIE , , 2008 . . 7109 71090F DOI: 10.1117/12.799838 http://doi.org/10.1117/12.799838 . .

H Ren , , , C.I Chang . . Automatic spectral target recognition in hyperspectral imagery . . IEEE Trans. Aerosp. Electron. Syst. , , 2003 . . 39 ( ( 4 ): ): 1232 - - 1249 . . DOI: 10.1109/TAES.2003.1261124 http://doi.org/10.1109/TAES.2003.1261124 . .

R.A Schowengerdt . . Remote Sensing: Models and Methods for Image Processing , , 1997 . . : : New York Academic Press , , . .

K Sun , , , X Geng , , , P Wang . . A fast endmember extraction algorithm based on gram determinant . . IEEE Geosci. Remote Sens. Lett. , , 2014 . . 11 ( ( 6 ): ): 1124 - - 1128 . . DOI: 10.1109/LGRS.2013.2288093 http://doi.org/10.1109/LGRS.2013.2288093 . .

X Tao , , , B Wang , , , L Zhang . . Orthogonal bases approach for decomposition of mixed pixels for hyperspectral imagery . . IEEE Geosci. Remote Sens. Lett. , , 2009 . . 6 ( ( 2 ): ): 219 - - 223 . . DOI: 10.1109/LGRS.2008.2010529 http://doi.org/10.1109/LGRS.2008.2010529 . .

L Wang , , , F Wei , , , D Liu . . Fast implementation of maximum simplex volume-based endmember extraction in original hyperspectral data space . . IEEE J. Sel. Topics Appl. Earth Observ. Remote Sens. , , 2013 . . 6 ( ( 2 ): ): 516 - - 521 . . DOI: 10.1109/JSTARS.2012.2234439 http://doi.org/10.1109/JSTARS.2012.2234439 . .

L.J Wang , , , X.R Li , , , L.Y Zhao . . Fast implement of the simplex growing algorithm for endmember extraction . . Acta Opt. Sin. , , 2014 . . 34 ( ( 11 ): ): 1128001 DOI: 10.3788/AOS201434.1128001 http://doi.org/10.3788/AOS201434.1128001 . .

W Xia , , , H.Y Pu , , , B Wang , , , 等 . . Triangular factorization- based simplex algorithms for hyperspectral unmixing . . IEEE Trans. Geosci. Remote Sens. , , 2012 . . 50 ( ( 11 ): ): 4420 - - 4440 . . DOI: 10.1109/TGRS.2012.2195185 http://doi.org/10.1109/TGRS.2012.2195185 . .

W Xiong , , , C.I Chang , , , C.C Wu . . Fast algorithms to implement N-FINDR for hyperspectral endmember extraction . . IEEE J. Sel. Topics Appl. Earth Observ. Remote Sens. , , 2011 . . 4 ( ( 3 ): ): 545 - - 564 . . DOI: 10.1109/JSTARS.2011.2119466 http://doi.org/10.1109/JSTARS.2011.2119466 . .

C.H Zhao , , , B Qi , , , Y.L Wang . . An improved N-FINDR hyperspectral endmember extraction algorithm . . J. Electron. Inform. Technol. , , 2012 . . 34 ( ( 2 ): ): 499 - - 503 . . . .

L.Y Zhao , , , J.P Zheng , , , X.R Li , , , 等 . . Kernel simplex growing algorithm based on a new simplex volume formula for hyperspectral endmember extraction . . J. Appl. Remote Sens. , , 2014 . . 8 ( ( 1 ): ): 083594 DOI: 10.1117/1.JRS.8.083594 http://doi.org/10.1117/1.JRS.8.083594 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰