Template matching via l_1 minimization and its application to hyperspectral data

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 and Imaging, 2011, 5 (1) : 19-35. doi: 10.3934/ipi.2011.5.19

References:

[1]	, Surface Optics Corporation,, , ().
[2]	, Urban hyperspectral data set,, , ().
[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.
[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.
[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.
[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.
[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).
[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.
[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.
[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.
[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.
[12]	G. Dimitris, A. Gary and K. Nirmal, Comparative analysis of hyperspectral adaptive matched filter detectors, SPIE., 4049 (2000), 2-17.
[13]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[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.
[15]	T. Goldstein, X. Bresson and S. Osher, "Geometric Applications of the Split Bregman Method: Segmentation and Surface Reconstruction," UCLA CAM Report, 9 (2009).
[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).
[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.
[18]	S. Kay, "Fundamentals of Statistical Signal Processing," Englewood Cliffs, NJ: Prentice-Hall, 1993.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[29]	L. Scharf and B. Friedlander, Matched subspace detectors, IEEE Transactions on Signal Processing, 42 (1994), 2146-2157. doi: 10.1109/78.301849.
[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.
[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.
[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).
[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.
[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.
[35]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, preprint, (1993).

show all references

References:

[1]	, Surface Optics Corporation,, , ().
[2]	, Urban hyperspectral data set,, , ().
[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.
[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.
[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.
[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.
[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).
[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.
[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.
[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.
[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.
[12]	G. Dimitris, A. Gary and K. Nirmal, Comparative analysis of hyperspectral adaptive matched filter detectors, SPIE., 4049 (2000), 2-17.
[13]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[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.
[15]	T. Goldstein, X. Bresson and S. Osher, "Geometric Applications of the Split Bregman Method: Segmentation and Surface Reconstruction," UCLA CAM Report, 9 (2009).
[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).
[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.
[18]	S. Kay, "Fundamentals of Statistical Signal Processing," Englewood Cliffs, NJ: Prentice-Hall, 1993.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[29]	L. Scharf and B. Friedlander, Matched subspace detectors, IEEE Transactions on Signal Processing, 42 (1994), 2146-2157. doi: 10.1109/78.301849.
[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.
[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.
[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).
[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.
[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.
[35]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, preprint, (1993).

[1]	Lei Wu, Zhe Sun. A new spectral method for $l_1$-regularized minimization. Inverse Problems and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533
[11]	Lican Kang, Yuan Luo, Jerry Zhijian Yang, Chang Zhu. A primal and dual active set algorithm for truncated $L_1$ regularized logistic regression. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022050
[12]	Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $ L_1 $ and $ L_\infty $ norms. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079
[13]	Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l₁ norm fidelity term. Evolution Equations and Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034
[14]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[15]	Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[16]	Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems and Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[17]	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
[18]	Yunmei Chen, Xianqi Li, Yuyuan Ouyang, Eduardo Pasiliao. Accelerated bregman operator splitting with backtracking. Inverse Problems and Imaging, 2017, 11 (6) : 1047-1070. doi: 10.3934/ipi.2017048
[19]	Seung-Yeal Ha, Eunhee Jeong, Robert M. Strain. Uniform $L^1$-stability of the relativistic Boltzmann equation near vacuum. Communications on Pure and Applied Analysis, 2013, 12 (2) : 1141-1161. doi: 10.3934/cpaa.2013.12.1141
[20]	Chérif Amrouche, Huy Hoang Nguyen. Elliptic problems with $L^1$-data in the half-space. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 369-397. doi: 10.3934/dcdss.2012.5.369

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Zhaohui Guo Stanley Osher
on Google Scholar
Zhaohui Guo Stanley Osher

[Back to Top]