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

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

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.
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.  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.  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.  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.  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, (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.  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.  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.  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.  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.   Google Scholar

[13]

D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  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.  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, 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.  doi: 10.1109/36.298007.  Google Scholar

[18]

S. Kay, "Fundamentals of Statistical Signal Processing,", Englewood Cliffs, (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.  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.  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.  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.  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.  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.  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.  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.   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, 38 (1990), 1760.  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.  doi: 10.1109/7.135446.  Google Scholar

[29]

L. Scharf and B. Friedlander, Matched subspace detectors,, IEEE Transactions on Signal Processing, 42 (1994), 2146.  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.   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.  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), 10.   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.  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.  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.  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.  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.  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.  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, (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.  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.  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.  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.  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.   Google Scholar

[13]

D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  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.  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, 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.  doi: 10.1109/36.298007.  Google Scholar

[18]

S. Kay, "Fundamentals of Statistical Signal Processing,", Englewood Cliffs, (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.  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.  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.  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.  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.  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.  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.  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.   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, 38 (1990), 1760.  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.  doi: 10.1109/7.135446.  Google Scholar

[29]

L. Scharf and B. Friedlander, Matched subspace detectors,, IEEE Transactions on Signal Processing, 42 (1994), 2146.  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.   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.  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), 10.   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.  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.  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]

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

[7]

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

[8]

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

[9]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2019061

[10]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487

[11]

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

[12]

Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term. Evolution Equations & Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034

[13]

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

[14]

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

[15]

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

[16]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917

[17]

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

[18]

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

[19]

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

[20]

Daniel Han-Kwan. $L^1$ averaging lemma for transport equations with Lipschitz force fields. Kinetic & Related Models, 2010, 3 (4) : 669-683. doi: 10.3934/krm.2010.3.669

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]