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

Zhaohui Guo; Stanley Osher

doi:10.3934/ipi.2011.5.19

Article Contents

2011, Volume 5, Issue 1: 19-35. Doi: 10.3934/ipi.2011.5.19 open access

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

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
2.
Department of Mathematics, University of California, Los Angeles, CA 90095

Received: April 30, 2010

Revised: July 31, 2010

Published: January 2011

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 65N21, 86A21.

Citation:

Related Papers

Cited by

References

[1]	Surface Optics Corporation, http://www.surfaceoptics.com.
[2]	Urban hyperspectral data set, http://www.agc.army.mil/Hypercube/.
[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).