High Performance Computing in Remote Sensing - Chapter 4

Chapter 4 Parallel Implementation of the ORASIS Algorithm for Remote Sensing Data Analysis David Gillis, Naval Research Laboratory Jeffrey H. Bowles, Naval Research Laboratory Contents 4.1 Introduction ............................................................ 70 4.2 Linear Mixing Model ................................................... 71 4.3 Overview of the ORASIS Algorithms .................................... 72 4.3.1 Prescreener ...................................................... 73 4.3.1.1 Exemplar Selection ..................................... 74 4.3.1.2 Codebook Replacement ................................. 79 4.3.2 Basis Selection .................................................. 80 4.3.3 Endmember Selection ............................................ 81 4.3.4 Demixing ....................................................... 82 4.3.4.1 Unconstrained Demix ................................... 83 4.3.4.2 Constrained Demix ..................................... 83 4.4 Additional Algorithms .................................................. 83 4.4.1 ORASIS Anomaly Detection ..................................... 83 4.4.2 N-FINDR ....................................................... 84 4.4.3 The Stochastic Target Detector ................................... 86 4.5 Parallel Implementation ................................................. 86 4.5.1 ORASIS Endmember Selection .................................. 87 4.5.2 N-FINDR Endmember Selection ................................. 88 4.5.3 Spectral Demixing ............................................... 89 4.5.4 Anomaly Detection .............................................. 89 4.6 Results ................................................................. 90 4.7 Conclusions ............................................................ 92 4.8 Acknowledgments ...................................................... 94 References ................................................................... 94 69 © 2008 by Taylor & Francis Group, LLC 70 High-Performance Computing in Remote Sensing ORASIS (the Optical Real-Time Adaptive Spectral Identification System) is a series of algorithms developed at the Naval Research Lab for the analysis of HyperSpectral Image (HSI) data. ORASIS is based on the Linear Mixing Model (LMM), which assumes that the individual spectra in a given HSI scene may be decomposed into a set of in-scene constituents known as endmembers. The algorithms in ORASIS are designed to identify the endmembers for a given scene, and to decompose (or demix) the scene spectra into their individual components. Additional algorithms may be used for compression and various post-processing tasks, such as terrain classification and anomaly detection. In this chapter, we present a parallel version of the ORASIS algorithm that was recently developed as part of a Department of Defense program on hyperspectral data exploitation. 4.1 Introduction A casual viewing of the recent literature reveals that hyperspectral imagery is be-coming an important tool in many disciplines. From medical and military uses to environmental monitoring and geological prospecting the power of hyperspectral im-agery is being shown. From a military point of view, the primary use of hyperspectral data is for target detection and identification. Secondary uses include determination of environmental products, such as terrain classification or coastal bathymetry, for the intelligence preparation of the battlespace environment. The reconnaissance and surveillance requirements of the U.S. armed forces are enormous. Remarks at an in-ternational conference by General Israel put the requirements at a minimum of one millionsquarekilometersperdaythatneedtobeanalyzed.Usually,thisworkincludes theuseofhighresolutionpanchromaticimagery,withanalystsmakingdeterminations based on the shapes of objects in the image. Hyperspectral imagery and algorithms holdthepromiseofassistingtheanalystbymakingdeterminationsofareasofinterest or even identification of militarily relevant objects using spectral information with spatial information being of secondary importance. Both the power and the pitfalls of hyperspectral imaging originate with the vast amount of data that is collected. This data amount is a consequence of the detailed measurementsbeingmade.Forexample,givenasensorwitha2metergroundsample distance (GSD) and a spectral range of 400 to 1000 nanometers (with a 5 nanometer spectral sampling), a coverage area of 1 square kilometer produces approximately 57 MB of hyperspectral data. In order to meet the million square kilometer require-ment,ahyperspectralsensorwouldhavetoproduceupto57terabytesperday.Thisis trulyastaggeringnumber.Onlybyautomatingthedataprocessing,andbyusingstate-of-the-art processing capability, will there be any chance of hyperspectral imagery makingasignificantcontributiontomilitaryneedsinreconnaissanceandsurveillance. In order to deal with the large amounts of data in HSI, a variety of new algorithms have appeared in recent years. Additionally, advanced computing systems continue © 2008 by Taylor & Francis Group, LLC Parallel Implementation of the ORASIS Algorithm 71 to improve processing speed, storage, and display capabilities. This is particularly true of the high-performance computing (HPC) systems. One common technique used in hyperspectral data analysis is the Linear Mixing Model (LMM). In general terms (details are given in the next section), the LMM assumes that a given spectrum in a hyperspectral image is simply the weighted sum of the individual spectra of the components present in the corresponding image pixel. Ifweassumethatthetotalnumberofmajorconstituentsinthescene(generallyknown asthesceneendmembers)issmallerthanthenumberofbands,thenitfollowsthatthe original high-dimensional data can be projected into a lower-dimensional subspace (one that is spanned by the endmembers) with little to no loss of information. The projected data may then be used either directly by an analyst and/or fed to various other post-processing routines, such as classification or targeting. In order to apply the LMM, the endmembers must be known. There have been a number of different methods for determining endmembers presented in the litera-ture [1], including Pixel Purity [2], N-FINDR [3], and multidimensional morpholog-ical techniques [4]. The Optical Real-Time Adaptive Spectral Identification System (ORASIS) [5] is a series of algorithms that have been developed to find endmembers, using no a priori knowledge of the scene, capable of operating in (near) real-time. In addition to the main endmember selection algorithms, additional algorithms allow for compression, constrained or unconstrained demixing, and anomaly detection. The original ORASIS algorithm was designed to run in scalar (single-processor) mode.Recently,wewereaskedtodevelopaparallel,scalableversionoftheORASIS, aspartofaDepartmentofDefenseCommonHigh-PerformanceComputingSoftware SupportInitiative(CHSSI)program[6].InadditiontoORASIS,thisprojectincluded the development of parallel versions of N-FINDR and two LMM-based anomaly detection routines. In this chapter, we review the details of the algorithms involved in this project, and discuss the modifications that were made to allow them to be run in parallel. We also include the results of running our modified algorithms on a variety of HPC systems. Theremainderofthischapterisdividedintosixsections.InSection4.2wepresent the mathematical formalities of the linear mixing model. In Sections 4.3 and 4.4 we give a general overview of the (scalar) ORASIS and the anomaly detection and N-FINDR algorithms, respectively, used in this project. In Section 4.5 we discuss the modifications that were made to the scalar algorithms in order to be run in parallel mode, and present the computational results of our modifications in 4.6. We then present our conclusions in 4.7. 4.2 Linear Mixing Model The linear mixing model assumes that each spectrum in a given hyperspectral image may be decomposed into a linear combination of the scene’s constituent spectra, generally referred to as endmembers. Symbolically, let l be the number of spectral bands, and consider each spectrum as a vector in l-dimensional space. Let Ej be the © 2008 by Taylor & Francis Group, LLC 72 High-Performance Computing in Remote Sensing l-dimensional endmember vectors, k be the number of constituents in the scene, and j = 1···k. Then the model states that each scene spectrum s may be written as the sum k s = αj Ej + N (4.1) j=1 where αj is the abundance of the jth component spectrum Ej, and N is an l-dimensional noise vector. Intuitively, the αj’s represent the amount of each con-stituent that is in a given pixel, and are often referred to as the abundance (or mixing) coefficients. For physical reasons, one or both of the following constraints (respec-tively, sum-to-one and nonnegativity) are sometimes placed on the αj’s: k αj = 1 (4.2) j=1 αj ≥ 0 (4.3) Once the endmembers for a given scene are known (either by ORASIS or some other method), the abundance coefficients may be estimated using a least squares technique, a process generally known as demixing. If no constraints are placed on the coefficients, then this calculation reduces to a simple (and fast) matrix-vector product, as does the case involving the sum-to-one constraint (4.2). In the case of the nonnegativity constraint (4.3), the coefficients can only be found by using numerical optimization techniques. In this chapter, we consider only the unconstrained and nonnegative constrained problems. After demixing, each of the l-dimensional spectra from the original scene may be replaced by the k-dimensional demixed spectra. In this way, a set of grayscale images (generallyknownaseitherfractionplanesorabundanceplanes)isconstructed,where each pixel in the image is given by the abundance coefficient of the corresponding spectra for the given endmember. As a result, the fraction planes serve to highlight groups of similar image spectra in the original scene. An example of this is given in Figure 4.1, which shows a single band of a hyperspectral image taken at Fort AP Hill with the NVIS sensor, along with two of the fraction planes created by ORASIS. Also, since the number of endmembers is generally much smaller than the original number of bands, the fraction planes retain the significant information in the scene but with a large reduction in the amount of data. 4.3 Overview of the ORASIS Algorithms In its most general form, ORASIS is a collection of algorithms that work together to produce a set of endmembers. The first of these algorithms, the prescreener, is used to ‘thin’ the data; in particular, the prescreener chooses a subset of the scene © 2008 by Taylor & Francis Group, LLC Parallel Implementation of the ORASIS Algorithm 73 (a) (b) (c) Figure 4.1 Data from AP Hill. (a) Single band of the original data. (b) (c) Fraction planes from ORASIS processing. spectra (known as the exemplars) that is used to model the data. In our experience, up to 95% of the data in a typical scene may be considered redundant (adding no additional information) and simply ignored. The prescreener is used to reduce the complexity and computational requirements of the subsequent ORASIS processing, as well as acting as a compression algorithm. The second step is the basis selection module, which determines an optimal subspace that contains the exemplars. The existence of such a subspace is a consequence of the linear mixing model. Once the exemplars have been projected into the basis subspace, the endmember selection algorithm is used to actually calculate the endmembers for the scene. This algorithm, which we call the shrinkwrap, intelligently extrapolates outside the data set to find endmembers that may be closer to pure substances than any of the spectra that exist in the data. Large hyperspectral data sets provide the algorithm with many examples of the different mixtures of the materials present, and each mixture helps determine the makeup of the endmembers. The last step in ORASIS is the demixing algorithm, which decomposes each spectrum in the original scene into a weighted sum of the endmembers. In this section we discuss the family of algorithms that make up ORASIS. This sectionisfocusedprimarilyontheoriginal(scalar)versionsofORASIS;adiscussion of the modifications made to allow the algorithms to run in parallel mode is given in Section 4.4. © 2008 by Taylor & Francis Group, LLC ... - tailieumienphi.vn