Template matching via $l_1$ minimization and its application to hyperspectral data

Zhaohui Guo; Stanley Osher

doi:10.3934/ipi.2011.5.19

Previous Article
Multimodal inverse problems: Maximum compatibility estimate and shape reconstruction
IPI Home
This Issue
Next Article
Modified iterated Tikhonov methods for solving systems of nonlinear ill-posed equations

February 2011, 5(1): 19-35. doi: 10.3934/ipi.2011.5.19

Template matching via $l_1$ minimization and its application to hyperspectral data

Zhaohui Guo ^1, and Stanley Osher ^2,

1.	Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095, United States
2.	Department of Mathematics, University of California, Los Angeles, CA 90095

Received May 2010 Revised August 2010 Published February 2011

Abstract
Related Papers
Under a Creative Commons license

Detecting and identifying targets or objects that are present in hyperspectral ground images are of great interest. Applications include land and environmental monitoring, mining, military, civil search-and-rescue operations, and so on. We propose and analyze an extremely simple and efficient idea for template matching based on $l_1$ minimization. The designed algorithm can be applied in hyperspectral classification and target detection. Synthetic image data and real hyperspectral image (HSI) data are used to assess the performance, with comparisons to other approaches, e.g. spectral angle map (SAM), adaptive coherence estimator (ACE), generalized-likelihood ratio test (GLRT) and matched filter. We demonstrate that this algorithm achieves excellent results with both high speed and accuracy by using Bregman iteration.

Keywords: $l_1$ minimization., Hyperspectral, Bregman, template matching.

Mathematics Subject Classification: 65N21, 86A2.

Citation: Zhaohui Guo, Stanley Osher. Template matching via $l_1$ minimization and its application to hyperspectral data. Inverse Problems & Imaging, 2011, 5 (1) : 19-35. doi: 10.3934/ipi.2011.5.19

References:

[1]	, Surface Optics Corporation,, , (). Google Scholar
[2]	, Urban hyperspectral data set,, , (). Google Scholar
[3]	C. Bachmann, T. Donato, G. Lamela, W. Rhea, M. Bettenhausen, R. Fusina, K. Du Bois, J. Porter and B. Truitt, Automatic classification of land cover on Smith Island, VA, using HyMAP imagery, IEEE Transactions on Geoscience and Remote Sensing, 40 (2002), 2313-2330. doi: 10.1109/TGRS.2002.804834. Google Scholar
[4]	C. Bachmann, Improving the performance of classifiers in high-dimensional remote sensing applications: An adaptive resampling strategy for error-prone exemplars (ARESEPE), IEEE Transactions on Geoscience and Remote Sensing, 41 (2003), 2101-2112. doi: 10.1109/TGRS.2003.817207. Google Scholar
[5]	C. Bachmann, T. Ainsworth and R. Fusina, Exploiting manifold geometry in hyperspectral imagery, IEEE Transactions on Geoscience and Remote Sensing, 43 (2005), 441-454. doi: 10.1109/TGRS.2004.842292. Google Scholar
[6]	C. Bachmann, T. Ainsworth and R. Fusina, Improved manifold coordinate representations of large scale hyperspectral imagery, IEEE Transactions on Geoscience and Remote Sensing, 44 (2006), 2786-2803. doi: 10.1109/TGRS.2006.881801. Google Scholar
[7]	J. Bioucas-Dias and M. Figueiredo, Alternating direction algorithms for constrained sparse regression: Application to hyperspectral unmixing, 2nd Workshop on Hyperspectral Image and Signal Processing: Evolution in Remote Sensing - WHISPERS, Reykjavik, Iceland, (2006). Google Scholar
[8]	L. Bregman, The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming, USSR Comput Math and Math. Phys., 7 (1967), 200-217. doi: 10.1016/0041-5553(67)90040-7. Google Scholar
[9]	J. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009), 337-369. doi: 10.1137/090753504. Google Scholar
[10]	E. Candes, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083. Google Scholar
[11]	E. Conte, M. Lops and G. Ricci, Asymptotically optimum radar detection in compound-Gaussian clutter, IEEE Transactions on Aerospace Electron. Syst., 31 (1995), 617-625. doi: 10.1109/7.381910. Google Scholar
[12]	G. Dimitris, A. Gary and K. Nirmal, Comparative analysis of hyperspectral adaptive matched filter detectors, SPIE., 4049 (2000), 2-17. Google Scholar
[13]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582. Google Scholar
[14]	T. Goldstein and S. Osher, The split Bregman algorithm for $L_1$ regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891. Google Scholar
[15]	T. Goldstein, X. Bresson and S. Osher, "Geometric Applications of the Split Bregman Method: Segmentation and Surface Reconstruction," UCLA CAM Report, 9 (2009). Google Scholar
[16]	Z. Guo, T. Wittman and S. Osher, $L_1$ unmixing and its application to hyperspectral image enhancement, in Proc. SPIE Conference on Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery, XV (2009). Google Scholar
[17]	J. Harsanyi and C. Chang, Hyperspectral image classification and dimensionality reduction: An orthogonal subspace projection approach, IEEE Transactions on Geoscience and Remote Sensing, 32 (1994), 779-785. doi: 10.1109/36.298007. Google Scholar
[18]	S. Kay, "Fundamentals of Statistical Signal Processing," Englewood Cliffs, NJ: Prentice-Hall, 1993. Google Scholar
[19]	S. Kraut and L. Scharf, The CFAR adaptive subspace detector is a scale-invariant GLRT, IEEE Transactions on Signal Processing, 47 (1999), 2538-2541. doi: 10.1109/78.782198. Google Scholar
[20]	S. Kraut, L. Scharf and L. McWhorter, Adaptive subspace detectors, IEEE Transactions on Signal Processing, 49 (2001), 1-16. doi: 10.1109/78.890324. Google Scholar
[21]	F. Kruse, A. Lefkoff, J. Boardman, K. Heidebrecht, A. Shapiro, P. Barloon and A. Goetz, The spectral image processing system (SIPS)-interactive visualization and analysis of imaging spectrometer data, Rem. Sens. Environ, 44 (1993), 145-164. doi: 10.1016/0034-4257(93)90013-N. Google Scholar
[22]	H. Kwon and N. Nasrabadi, Kernel RX-algorithm: A nonlinear anomaly detector for hyperspectral imagery, IEEE Transactions on Geoscience and Remote Sensing, 43 (2005), 388-397. doi: 10.1109/TGRS.2004.841487. Google Scholar
[23]	D. Manolakis and G. Shaw, Detection algorithms for hyperspectral imaging applications, IEEE Signal Processing Magazine, 19 (2002), 29-43. doi: 10.1109/79.974724. Google Scholar
[24]	D. Manolakis, Detection algorithms for hyperspectral imaging applications: A signal processing perspective, IEEE Workshop on Advances in Techniques for Analysis of Remotely Sensed Data, (2003), 378-384. doi: 10.1109/WARSD.2003.1295218. Google Scholar
[25]	S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, An iterative regularization method for total variation based image restoration, Multiscale Model. Simul., 4 (2005), 460-489. doi: 10.1137/040605412. Google Scholar
[26]	S. Osher, Y. Mao, B. Dong and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci., 8 (2010), 93-111. Google Scholar
[27]	I. Reed and X. Yu, Adaptive multiple-band CFAR detection of an optical pattern with unknown spectral distribution, IEEE Transactions on Acoustics, Speech and Signal Processing, 38 (1990), 1760-1770. doi: 10.1109/29.60107. Google Scholar
[28]	F. Robey, D. Fuhermann, E. Kelly and R. Nitzberg, A CFAR adaptive matched filter detector, IEEE Transactions on Aerospace and Electronic Systems, 28 (1992), 208-216. doi: 10.1109/7.135446. Google Scholar
[29]	L. Scharf and B. Friedlander, Matched subspace detectors, IEEE Transactions on Signal Processing, 42 (1994), 2146-2157. doi: 10.1109/78.301849. Google Scholar
[30]	D. Snyder, J. Kerekes, I. Fairweather, R. Crabtree, J. Shive and S. Hager, Development of a web-based application to evaluate target finding algorithms, Proceedings of the 2008 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), 2 (2008), 915-918. Google Scholar
[31]	D. Stein, S. Beaven, L. Hoff, E. Winter, A. Schaum and A. Stoker, Anomaly detection from hyperspectral imagery, IEEE Signal Processing Magazine, 19 (2002), 58-69. doi: 10.1109/79.974730. Google Scholar
[32]	A. Szlam, Z. Guo and S. Osher, A split Bregman method for non-negative sparsity penalized least squares with applications to hyperspectral demixing, UCLA CAM report, 10-06 (2010). Google Scholar
[33]	W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168. doi: 10.1137/070703983. Google Scholar
[34]	X. Yu, I. Reed and A. Stocker, Comparative performance analysis of adaptive multispectral detectors, IEEE Transactions on Signal Processing, 41 (1993), 2639-2656. doi: 10.1109/78.229895. Google Scholar
[35]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, preprint, (1993). Google Scholar

show all references

References:

[1]	, Surface Optics Corporation,, , (). Google Scholar
[2]	, Urban hyperspectral data set,, , (). Google Scholar
[3]	C. Bachmann, T. Donato, G. Lamela, W. Rhea, M. Bettenhausen, R. Fusina, K. Du Bois, J. Porter and B. Truitt, Automatic classification of land cover on Smith Island, VA, using HyMAP imagery, IEEE Transactions on Geoscience and Remote Sensing, 40 (2002), 2313-2330. doi: 10.1109/TGRS.2002.804834. Google Scholar
[4]	C. Bachmann, Improving the performance of classifiers in high-dimensional remote sensing applications: An adaptive resampling strategy for error-prone exemplars (ARESEPE), IEEE Transactions on Geoscience and Remote Sensing, 41 (2003), 2101-2112. doi: 10.1109/TGRS.2003.817207. Google Scholar
[5]	C. Bachmann, T. Ainsworth and R. Fusina, Exploiting manifold geometry in hyperspectral imagery, IEEE Transactions on Geoscience and Remote Sensing, 43 (2005), 441-454. doi: 10.1109/TGRS.2004.842292. Google Scholar
[6]	C. Bachmann, T. Ainsworth and R. Fusina, Improved manifold coordinate representations of large scale hyperspectral imagery, IEEE Transactions on Geoscience and Remote Sensing, 44 (2006), 2786-2803. doi: 10.1109/TGRS.2006.881801. Google Scholar
[7]	J. Bioucas-Dias and M. Figueiredo, Alternating direction algorithms for constrained sparse regression: Application to hyperspectral unmixing, 2nd Workshop on Hyperspectral Image and Signal Processing: Evolution in Remote Sensing - WHISPERS, Reykjavik, Iceland, (2006). Google Scholar
[8]	L. Bregman, The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming, USSR Comput Math and Math. Phys., 7 (1967), 200-217. doi: 10.1016/0041-5553(67)90040-7. Google Scholar
[9]	J. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009), 337-369. doi: 10.1137/090753504. Google Scholar
[10]	E. Candes, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083. Google Scholar
[11]	E. Conte, M. Lops and G. Ricci, Asymptotically optimum radar detection in compound-Gaussian clutter, IEEE Transactions on Aerospace Electron. Syst., 31 (1995), 617-625. doi: 10.1109/7.381910. Google Scholar
[12]	G. Dimitris, A. Gary and K. Nirmal, Comparative analysis of hyperspectral adaptive matched filter detectors, SPIE., 4049 (2000), 2-17. Google Scholar
[13]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582. Google Scholar
[14]	T. Goldstein and S. Osher, The split Bregman algorithm for $L_1$ regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891. Google Scholar
[15]	T. Goldstein, X. Bresson and S. Osher, "Geometric Applications of the Split Bregman Method: Segmentation and Surface Reconstruction," UCLA CAM Report, 9 (2009). Google Scholar
[16]	Z. Guo, T. Wittman and S. Osher, $L_1$ unmixing and its application to hyperspectral image enhancement, in Proc. SPIE Conference on Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery, XV (2009). Google Scholar
[17]	J. Harsanyi and C. Chang, Hyperspectral image classification and dimensionality reduction: An orthogonal subspace projection approach, IEEE Transactions on Geoscience and Remote Sensing, 32 (1994), 779-785. doi: 10.1109/36.298007. Google Scholar
[18]	S. Kay, "Fundamentals of Statistical Signal Processing," Englewood Cliffs, NJ: Prentice-Hall, 1993. Google Scholar
[19]	S. Kraut and L. Scharf, The CFAR adaptive subspace detector is a scale-invariant GLRT, IEEE Transactions on Signal Processing, 47 (1999), 2538-2541. doi: 10.1109/78.782198. Google Scholar
[20]	S. Kraut, L. Scharf and L. McWhorter, Adaptive subspace detectors, IEEE Transactions on Signal Processing, 49 (2001), 1-16. doi: 10.1109/78.890324. Google Scholar
[21]	F. Kruse, A. Lefkoff, J. Boardman, K. Heidebrecht, A. Shapiro, P. Barloon and A. Goetz, The spectral image processing system (SIPS)-interactive visualization and analysis of imaging spectrometer data, Rem. Sens. Environ, 44 (1993), 145-164. doi: 10.1016/0034-4257(93)90013-N. Google Scholar
[22]	H. Kwon and N. Nasrabadi, Kernel RX-algorithm: A nonlinear anomaly detector for hyperspectral imagery, IEEE Transactions on Geoscience and Remote Sensing, 43 (2005), 388-397. doi: 10.1109/TGRS.2004.841487. Google Scholar
[23]	D. Manolakis and G. Shaw, Detection algorithms for hyperspectral imaging applications, IEEE Signal Processing Magazine, 19 (2002), 29-43. doi: 10.1109/79.974724. Google Scholar
[24]	D. Manolakis, Detection algorithms for hyperspectral imaging applications: A signal processing perspective, IEEE Workshop on Advances in Techniques for Analysis of Remotely Sensed Data, (2003), 378-384. doi: 10.1109/WARSD.2003.1295218. Google Scholar
[25]	S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, An iterative regularization method for total variation based image restoration, Multiscale Model. Simul., 4 (2005), 460-489. doi: 10.1137/040605412. Google Scholar
[26]	S. Osher, Y. Mao, B. Dong and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci., 8 (2010), 93-111. Google Scholar
[27]	I. Reed and X. Yu, Adaptive multiple-band CFAR detection of an optical pattern with unknown spectral distribution, IEEE Transactions on Acoustics, Speech and Signal Processing, 38 (1990), 1760-1770. doi: 10.1109/29.60107. Google Scholar
[28]	F. Robey, D. Fuhermann, E. Kelly and R. Nitzberg, A CFAR adaptive matched filter detector, IEEE Transactions on Aerospace and Electronic Systems, 28 (1992), 208-216. doi: 10.1109/7.135446. Google Scholar
[29]	L. Scharf and B. Friedlander, Matched subspace detectors, IEEE Transactions on Signal Processing, 42 (1994), 2146-2157. doi: 10.1109/78.301849. Google Scholar
[30]	D. Snyder, J. Kerekes, I. Fairweather, R. Crabtree, J. Shive and S. Hager, Development of a web-based application to evaluate target finding algorithms, Proceedings of the 2008 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), 2 (2008), 915-918. Google Scholar
[31]	D. Stein, S. Beaven, L. Hoff, E. Winter, A. Schaum and A. Stoker, Anomaly detection from hyperspectral imagery, IEEE Signal Processing Magazine, 19 (2002), 58-69. doi: 10.1109/79.974730. Google Scholar
[32]	A. Szlam, Z. Guo and S. Osher, A split Bregman method for non-negative sparsity penalized least squares with applications to hyperspectral demixing, UCLA CAM report, 10-06 (2010). Google Scholar
[33]	W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168. doi: 10.1137/070703983. Google Scholar
[34]	X. Yu, I. Reed and A. Stocker, Comparative performance analysis of adaptive multispectral detectors, IEEE Transactions on Signal Processing, 41 (1993), 2639-2656. doi: 10.1109/78.229895. Google Scholar
[35]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, preprint, (1993). Google Scholar

[1]	Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems & Imaging, 2015, 9 (1) : 257-272. doi: 10.3934/ipi.2015.9.257
[2]	Yingying Li, Stanley Osher, Richard Tsai. Heat source identification based on $l_1$ constrained minimization. Inverse Problems & Imaging, 2014, 8 (1) : 199-221. doi: 10.3934/ipi.2014.8.199
[3]	Jiying Liu, Jubo Zhu, Fengxia Yan, Zenghui Zhang. Compressive sampling and $l_1$ minimization for SAR imaging with low sampling rate. Inverse Problems & Imaging, 2013, 7 (4) : 1295-1305. doi: 10.3934/ipi.2013.7.1295
[4]	Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial & Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191
[5]	Gautier Picot. Energy-minimal transfers in the vicinity of the lagrangian point $L_1$. Conference Publications, 2011, 2011 (Special) : 1196-1205. doi: 10.3934/proc.2011.2011.1196
[6]	Wei Wang, Degen Huang, Haitao Yu. Word sense disambiguation based on stretchable matching of the semantic template. Mathematical Foundations of Computing, 2021, 4 (1) : 1-13. doi: 10.3934/mfc.2020022
[7]	Satoshi Ito, Soon-Yi Wu, Ting-Jang Shiu, Kok Lay Teo. A numerical approach to infinite-dimensional linear programming in $L_1$ spaces. Journal of Industrial & Management Optimization, 2010, 6 (1) : 15-28. doi: 10.3934/jimo.2010.6.15
[8]	Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061
[9]	Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037
[10]	Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533
[11]	Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $ L_1 $ and $ L_\infty $ norms. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079
[12]	Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l₁ norm fidelity term. Evolution Equations & Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034
[13]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[14]	Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems & Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[15]	Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[16]	Yoshikazu Giga, Jürgen Saal. $L^1$ maximal regularity for the laplacian and applications. Conference Publications, 2011, 2011 (Special) : 495-504. doi: 10.3934/proc.2011.2011.495
[17]	Yunmei Chen, Xianqi Li, Yuyuan Ouyang, Eduardo Pasiliao. Accelerated bregman operator splitting with backtracking. Inverse Problems & Imaging, 2017, 11 (6) : 1047-1070. doi: 10.3934/ipi.2017048
[18]	Seung-Yeal Ha, Eunhee Jeong, Robert M. Strain. Uniform $L^1$-stability of the relativistic Boltzmann equation near vacuum. Communications on Pure & Applied Analysis, 2013, 12 (2) : 1141-1161. doi: 10.3934/cpaa.2013.12.1141
[19]	Chérif Amrouche, Huy Hoang Nguyen. Elliptic problems with $L^1$-data in the half-space. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 369-397. doi: 10.3934/dcdss.2012.5.369
[20]	Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems & Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093

2020 Impact Factor: 1.639

American Institute of Mathematical Sciences

Template matching via $l_1$ minimization and its application to hyperspectral data

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Template matching via $l_1$ minimization and its application to hyperspectral data

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors