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,, , ().

[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. 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. 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. 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. 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, (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. 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. 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. 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. 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.

[13]

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

[18]

S. Kay, "Fundamentals of Statistical Signal Processing,", Englewood Cliffs, (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. doi: 10.1109/78.782198.

[20]

S. Kraut, L. Scharf and L. McWhorter, Adaptive subspace detectors,, IEEE Transactions on Signal Processing, 49 (2001), 1. 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. 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. 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. 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. 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. 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.

[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.

[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.

[29]

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

[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.

[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.

[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.

[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.

[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. 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. 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. 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. 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, (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. 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. 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. 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. 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.

[13]

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

[18]

S. Kay, "Fundamentals of Statistical Signal Processing,", Englewood Cliffs, (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. doi: 10.1109/78.782198.

[20]

S. Kraut, L. Scharf and L. McWhorter, Adaptive subspace detectors,, IEEE Transactions on Signal Processing, 49 (2001), 1. 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. 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. 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. 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. 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. 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.

[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.

[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.

[29]

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

[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.

[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.

[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.

[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.

[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 & 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]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

T. L. van Noorden, I. S. Pop, M. Röger. Crystal dissolution and precipitation in porous media: L$^1$-contraction and uniqueness. Conference Publications, 2007, 2007 (Special) : 1013-1020. doi: 10.3934/proc.2007.2007.1013

[19]

C. García Vázquez, Francisco Ortegón Gallego. On certain nonlinear parabolic equations with singular diffusion and data in $L^1$. Communications on Pure & Applied Analysis, 2005, 4 (3) : 589-612. doi: 10.3934/cpaa.2005.4.589

[20]

Paola Goatin, Philippe G. LeFloch. $L^1$ continuous dependence for the Euler equations of compressible fluids dynamics. Communications on Pure & Applied Analysis, 2003, 2 (1) : 107-137. doi: 10.3934/cpaa.2003.2.107

2016 Impact Factor: 1.094

Metrics

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

Other articles
by authors

[Back to Top]