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

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

Endmember extraction / Modified Cholesky factorization / Spatial pixel purity index (SPPI) / New simplex growing algorithm (NSGA) / Kernel new simplex growing algorithm (KNSGA)

References

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

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

[3] Chang, C.I., Wu, C., Liu, W., et al., 2006. A new growing method for simplex-based endmember extraction algo-rithms. IEEE Trans. Geosci. Remote Sens., 44(10):2804–2819. http://dx.doi.org/10.1109/TGRS.2006.881803

[4] Cui, J.T., Wang, J., Li, X.R., et al., 2013. Endmember extrac-tion algorithm based on spatial pixel purity index. J. Zhejiang Univ. (Eng. Sci.), 47(9):1517–1523 (in Chinese). http://dx.doi.org/10.3785/j.issn.1008-973X.2013.09.002

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

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

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

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

[9] Gill, P.E., Murray, W., Wright, M.H., 1981. Practical Opti-mization. Academic Press, London.

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

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

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

[13] NASA, 1997. NASA AVIRIS Data. Available from https://www.jpl.nasa.gov/missions/airborne-visible-infrared-imaging-spectrometer-aviris.

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

[15] Nascimento, J.M.P., Bioucas-Dias, J.M., 2008. New devel-opments on VCA unmixing algorithm. SPIE, 7109: 71090F. http://dx.doi.org/10.1117/12.799838

[16] Ren, H., Chang, C.I., 2003. Automatic spectral target recog-nition in hyperspectral imagery. IEEE Trans. Aerosp. Electron. Syst., 39(4):1232–1249. http://dx.doi.org/10.1109/TAES.2003.1261124

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

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

[19] Tao, X., Wang, B., Zhang, L., 2009. Orthogonal bases ap-proach for decomposition of mixed pixels for hyperspec-tral imagery. IEEE Geosci. Remote Sens. Lett., 6(2): 219–223. http://dx.doi.org/10.1109/LGRS.2008.2010529

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

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

[22] Xia, W., Pu, H.Y., Wang, B., et al., 2012. Triangular factori-zation-based simplex algorithms for hyperspectral un-mixing. IEEE Trans. Geosci. Remote Sens., 50(11): 4420–4440. http://dx.doi.org/10.1109/TGRS.2012.2195185

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

[24] Zhao, C.H., Qi, B., Wang, Y.L., 2012. An improved N-FINDR hyperspectral endmember extraction algorithm. J. Elec-tron. Inform. Technol., 34(2):499–503 (in Chinese).

[25] Zhao, L.Y., Zheng, J.P., Li, X.R., et al., 2014. Kernel simplex growing algorithm based on a new simplex volume for-mula for hyperspectral endmember extraction. J. Appl. Remote Sens., 8(1):083594. http://dx.doi.org/10.1117/1.JRS.8.083594

RIGHTS & PERMISSIONS

2016 Zhejiang University and Springer-Verlag Berlin Heidelberg 2016