Vertex component analysis: a geometric-based approach to unmix hyperspectral data

Hyperspectral remote sensing exploits the electromagnetic scattering patterns of the different materials at specific wavelengths [2, 3]. Hyperspectral sensors have been developed to sample the scattered portion of the electromagnetic spectrum extending from the visible region through the near-infrared and mid-infrared, in hundreds of narrow contiguous bands [4, 5]. The number and variety of potential civilian and military applications of hyperspectral remote sensing is enormous [6, 7]. Very often, the resolution cell corresponding to a single pixel in an image contains several substances (endmembers) [4]. In this situation, the scattered energy is a mixing of the endmember spectra. A challenging task underlying many hyperspectral imagery applications is then decomposing a mixed pixel into a collection of reflectance spectra, called endmember signatures, and the corresponding abundance fractions [8–10]. Depending on the mixing scales at each pixel, the observed mixture is either linear or nonlinear [11, 12]. Linear mixing model holds approximately when the mixing scale is macroscopic [13] and there is negligible interaction among distinct endmembers [3, 14]. If, however, the mixing scale is microscopic (or intimate mixtures) [15, 16] and the incident solar radiation is scattered by the scene through multiple bounces involving several endmembers [17], the linear model is no longer accurate. Linear spectral unmixing has been intensively researched in the last years [9, 10, 12, 18–21]. It considers that a mixed pixel is a linear combination of endmember signatures weighted by the correspondent abundance fractions. Under this model, and assuming that the number of substances and their reflectance spectra are known, hyperspectral unmixing is a linear problem for which many solutions have been proposed (e.g., maximum likelihood estimation [8], spectral signature matching [22], spectral angle mapper [23], subspace projection methods [24,25], and constrained least squares [26]). In most cases, the number of substances and their reflectances are not known and, then, hyperspectral unmixing falls into the class of blind source separation problems [27]. Independent component analysis (ICA) has recently been proposed as a tool to blindly unmix hyperspectral data [28–31]. ICA is based on the assumption of mutually independent sources (abundance fractions), which is not the case of hyperspectral data, since the sum of abundance fractions is constant, implying statistical dependence among them. This dependence compromises ICA applicability to hyperspectral images as shown in Refs. [21, 32]. In fact, ICA finds the endmember signatures by multiplying the spectral vectors with an unmixing matrix, which minimizes the mutual information among sources. If sources are independent, ICA provides the correct unmixing, since the minimum of the mutual information is obtained only when sources are independent. This is no longer true for dependent abundance fractions. Nevertheless, some endmembers may be approximately unmixed. These aspects are addressed in Ref. [33]. Under the linear mixing model, the observations from a scene are in a simplex whose vertices correspond to the endmembers. Several approaches [34–36] have exploited this geometric feature of hyperspectral mixtures [35]. Minimum volume transform (MVT) algorithm [36] determines the simplex of minimum volume containing the data. The method presented in Ref. [37] is also of MVT type but, by introducing the notion of bundles, it takes into account the endmember variability usually present in hyperspectral mixtures. The MVT type approaches are complex from the computational point of view. Usually, these algorithms find in the first place the convex hull defined by the observed data and then fit a minimum volume simplex to it. For example, the gift wrapping algorithm [38] computes the convex hull of n data points in a d-dimensional space with a computational complexity of O(nbd=2cþ1), where bxc is the highest integer lower or equal than x and n is the number of samples. The complexity of the method presented in Ref. [37] is even higher, since the temperature of the simulated annealing algorithm used shall follow a log( ) law [39] to assure convergence (in probability) to the desired solution. Aiming at a lower computational complexity, some algorithms such as the pixel purity index (PPI) [35] and the N-FINDR [40] still find the minimum volume simplex containing the data cloud, but they assume the presence of at least one pure pixel of each endmember in the data. This is a strong requisite that may not hold in some data sets. In any case, these algorithms find the set of most pure pixels in the data. PPI algorithm uses the minimum noise fraction (MNF) [41] as a preprocessing step to reduce dimensionality and to improve the signal-to-noise ratio (SNR). The algorithm then projects every spectral vector onto skewers (large number of random vectors) [35, 42,43]. The points corresponding to extremes, for each skewer direction, are stored. A cumulative account records the number of times each pixel (i.e., a given spectral vector) is found to be an extreme. The pixels with the highest scores are the purest ones. N-FINDR algorithm [40] is based on the fact that in p spectral dimensions, the p-volume defined by a simplex formed by the purest pixels is larger than any other volume defined by any other combination of pixels. This algorithm finds the set of pixels defining the largest volume by inflating a simplex inside the data. ORA SIS [44, 45] is a hyperspectral framework developed by the U.S. Naval Research Laboratory consisting of several algorithms organized in six modules: exemplar selector, adaptative learner, demixer, knowledge base or spectral library, and spatial postrocessor. The first step consists in flat-fielding the spectra. Next, the exemplar selection module is used to select spectral vectors that best represent the smaller convex cone containing the data. The other pixels are rejected when the spectral angle distance (SAD) is less than a given thresh old. The procedure finds the basis for a subspace of a lower dimension using a modified Gram–Schmidt orthogonalizati on. The selected vectors are then projected onto this subspace and a simplex is found by an MV T pro cess. ORA SIS is oriented to real-time target detection from uncrewed air vehicles using hyperspectral data [46]. In this chapter we develop a new algorithm to unmix linear mixtures of endmember spectra. First, the algorithm determines the number of endmembers and the signal subspace using a newly developed concept [47, 48]. Second, the algorithm extracts the most pure pixels present in the data. Unlike other methods, this algorithm is completely automatic and unsupervised. To estimate the number of endmembers and the signal subspace in hyperspectral linear mixtures, the proposed scheme begins by estimating sign al and noise correlation matrices. The latter is based on multiple regression theory. The signal subspace is then identified by selectin g the set of signal eigenvalue s that best represents the data, in the least-square sense [48,49 ], we note, however, that VCA works with projected and with unprojected data. The extraction of the end members exploits two facts: (1) the endmembers are the vertices of a simplex and (2) the affine transformation of a simplex is also a simplex. As PPI and N-FIND R algorithms, VCA also assumes the presence of pure pixels in the data. The algorithm iteratively projects data on to a direction orthogonal to the subspace spanned by the endmembers already determined. The new end member signature corresponds to the extreme of the projection. The algorithm iterates until all end members are exhausted. VCA performs much better than PPI and better than or comparable to N-FI NDR; yet it has a computational complexity between on e and two orders of magnitude lower than N-FINDR. The chapter is structure d as follows. Section 19.2 describes the fundamentals of the proposed method. Section 19.3 and Section 19.4 evaluate the proposed algorithm using simulated and real data, respectively. Section 19.5 presents some concluding remarks.

Hyperspectral unmixing algorithm via dependent component analysis

This paper introduces a new method to blindly unmix hyperspectral data, termed dependent component analysis (DECA). This method decomposes a hyperspectral images into a collection of reflectance (or radiance) spectra of the materials present in the scene (endmember signatures) and the corresponding abundance fractions at each pixel. DECA assumes that each pixel is a linear mixture of the endmembers signatures weighted by the correspondent abundance fractions. These abudances are modeled as mixtures of Dirichlet densities, thus enforcing the constraints on abundance fractions imposed by the acquisition process, namely non-negativity and constant sum. The mixing matrix is inferred by a generalized expectation-maximization (GEM) type algorithm. This method overcomes the limitations of unmixing methods based on Independent Component Analysis (ICA) and on geometrical based approaches. The effectiveness of the proposed method is illustrated using simulated data based on U.S.G.S. laboratory spectra and real hyperspectral data collected by the AVIRIS sensor over Cuprite, Nevada.

Análise de Desempenho e Recomendação para Soluções IVR

Mestrado em Engenharia Informática, Área de Especialização em Tecnologias do Conhecimento e da Decisão

A lightweight distributed super peer election algorithm for unstructured dynamic P2P systems

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Domestic Consumption Simulation and Management Using a Continuous Consumption Management and Optimization Algorithm

The recent changes concerning the consumers’ active participation in the efficient management of load devices for one’s own interest and for the interest of the network operator, namely in the context of demand response, leads to the need for improved algorithms and tools. A continuous consumption optimization algorithm has been improved in order to better manage the shifted demand. It has been done in a simulation and user-interaction tool capable of being integrated in a multi-agent smart grid simulator already developed, and also capable of integrating several optimization algorithms to manage real and simulated loads. The case study of this paper enhances the advantages of the proposed algorithm and the benefits of using the developed simulation and user interaction tool.

A Learning Algorithm and System Approach to Address Exceptional Events in Domestic Consumption Management

The integration of the Smart Grid concept into the electric grid brings to the need for an active participation of small and medium players. This active participation can be achieved using decentralized decisions, in which the end consumer can manage loads regarding the Smart Grid needs. The management of loads must handle the users’ preferences, wills and needs. However, the users’ preferences, wills and needs can suffer changes when faced with exceptional events. This paper proposes the integration of exceptional events into the SCADA House Intelligent Management (SHIM) system developed by the authors, to handle machine learning issues in the domestic consumption context. An illustrative application and learning case study is provided in this paper.

Acceleration of physics simulation engine through OpenCL

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Geodupa - a geography-driven partial membership algorithm

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

Efficient Legendre spectral tau algorithm for solving two-sided space-time Caputo fractional advection-dispersion equation

In this paper we present the operational matrices of the left Caputo fractional derivative, right Caputo fractional derivative and Riemann–Liouville fractional integral for shifted Legendre polynomials. We develop an accurate numerical algorithm to solve the two-sided space–time fractional advection–dispersion equation (FADE) based on a spectral shifted Legendre tau (SLT) method in combination with the derived shifted Legendre operational matrices. The fractional derivatives are described in the Caputo sense. We propose a spectral SLT method, both in temporal and spatial discretizations for the two-sided space–time FADE. This technique reduces the two-sided space–time FADE to a system of algebraic equations that simplifies the problem. Numerical results carried out to confirm the spectral accuracy and efficiency of the proposed algorithm. By selecting relatively few Legendre polynomial degrees, we are able to get very accurate approximations, demonstrating the utility of the new approach over other numerical methods.

Volume da Aurícula Esquerda: um "Velho" Cálculo Ecocardiográfico com uma Importância Prognóstica Renovada. Um Estudo em Doentes com Miocardiopatia Dilatada

Recentemente, surgiram alguns trabalhos que ressaltaram a importância do cálculo do volume da aurícula esquerda (VAE) como um marcador de eventos cardíacos adversos. Foi objectivo deste estudo avaliar a importância prognóstica deste parâmetro em doentes (dts) com deficiente função ventricular esquerda e correlacioná-lo com outros parâmetros clássicos de prognóstico – consumo de O2 (VO2 max) e pro-BNP (pBNP). Métodos: Analisou-se o volume da aurícula esquerda (VAE) por método de Simpson, numa população de 35 dts com cardiopatia dilatada (idiopática e isquémica) com fracção de ejecção (FE) 31±9,6% doentes (dts) eram de sexo masculino e a média de idades foi de 50,5±10,5 anos. Toda a população efectuou estudos de ecocardiografia convencional (incluindo avaliação por M-mode, bidimensional e Doppler), prova cardiorespiratória (VO2max) e doseamento de pro-BNP. O tempo médio de seguimento foi de 24 ± 4 meses, tendo-se considerado como eventos cardíacos (EC): internamento por insuficiência cardíaca, transplante e morte. Resultados: Dos parâmetros da ecocardiografia - o diâmetro da AE foi de 46,6±5,7mm, as dimensões do VE em diástole – 73,5±10mm e em sístole -58,9±11mm, a média da fracção de ejecção foi de 31±9,6%, o VAE foi de 78,6±33 ml, os volumes do VE foram de 214±82ml em diástole e de 153±75ml em sístole, 15 dts tinham padrão restritivo de enchimento ventricular (E/A>2), a média da área (Doppler cor) da insuficiência mitral foi de 4±3,3cm2, 14 dts tinham E/E’>15. O VO2 max médio foi de 20±5,8ml/kg/min e o pro-BNP de 3146±4629pg/mL. Para além da correlação de outros parâmetros clássicos ecocardiográficos com o prognóstico (volumes VE, FE e E/E’), o VAE e o volume indexado da AE (VAE/SC) mostraram uma correlação com o prognóstico (EC) com r=0,4 (p=0,02) que não se verificou para o diâmetro da AE (p=ns). Em relação à tolerância ao esforço, houve uma correlação inversa entre o diâmetro, o volume e o volume indexado da AE e o VO2max, com maior significado estatístico para o VAE e VAE/SC com r=-0,48, p=0,008. Quanto ao pro-BNP, quer o diâmetro, quer o VAE (ou volume indexado) tiverem o mesmo nível de significado estatístico (r=0,43; p=0,02). O valor predictivo de eventos (curvas ROC) para o VAE foi de 70ml e de 37ml/m2 para o VAE/m2. Conclusão: O volume da aurícula esquerda/volume indexado é um parâmetro ecocardiográfico com significado prognóstico em dts com deficiente função ventricular esquerda, correlacionando-se com a tolerância ao esforço e pro-BNP.

Algoritmo genético para empacotamento de contentores

No âmbito da investigação operacional o problema de empacotamento de contentores é conhecido por procurar definir uma configuração de carga, de forma a otimizar a utilização de um espaço disponível para efetuar o empacotamento. Este problema pode ser apresentado em diversas formas, formas estas que variam em função das características de cada empacotamento. Estas características podem ser: o tipo de carga que se pretende carregar (homogénea ou heterogénea), a possibilidade de a carga poder sofrer rotações em todas as suas dimensões ou apenas em algumas, o lucro que está associado a cada caixa carregada ou restrições inerentes ao contentor como por exemplo dimensões. O interesse pelo estudo de problemas de empacotamento de contentores tem vindo a receber cada vez mais ênfase por várias razões, uma delas é o interesse financeiro dado que o transporte é uma prática que representa custos, sendo importante diminuir estes custos aproveitando o volume do contentor da melhor forma. Outra preocupação que motiva o estudo deste problema prende-se com fatores ambientes, onde se procura racionalizar os recursos naturais estando esta também ligada a questões financeiras. Na literatura podem ser encontradas varias propostas para solucionar este problema, cada uma destas dirigidas a uma variante do problema, estas propostas podem ser determinísticas ou não determinísticas onde utilizam heurísticas ou metaheurísticas. O estudo realizado nesta dissertação descreve algumas destas propostas, nomeadamente as metaheurísticas que são utilizadas na resolução deste problema. O trabalho aqui apresentado traz também uma nova metaheurísticas, mais precisamente um algoritmo genético que terá como objetivo, apresentar uma configuração de carga para um problema de empacotamento de um contentor. O algoritmo genético tem como objetivo a resolução do seguinte problema: empacotar várias caixas retangulares com diversos tamanhos num contentor. Este problema é conhecido como Bin-Packing. A novidade que este algoritmo genético vai introduzir nas diversas soluções apresentadas até à data, é uma nova forma de criar padrões iniciais, ou seja, é utilizada a heurística HSSI (Heurística de Suavização de Superfícies Irregulares) que tem como objetivo criar uma população inicial de forma a otimizar o algoritmo genético. A heurística HSSI tenta resolver problemas de empacotamento simulando, o comportamento da maioria das pessoas ao fazer este processo na vida real, contudo, tem um campo de busca reduzido entre as soluções possíveis e será então utilizado um algoritmo genético para ampliar este campo de busca e explorar novas soluções. No final pretende-se obter um software onde será possível configurar um dado problema de empacotamento de um contentor e obter, a solução do mesmo através do algoritmo genético. Assim sendo, o estudo realizado tem como principal objetivo contribuir com pesquisas e conclusões, sobre este problema e trazer uma nova proposta de solução para o problema de empacotamento de contentores.

A filter algorithm: comparison with NLP solvers

The purpose of this work is to present an algorithm to solve nonlinear constrained optimization problems, using the filter method with the inexact restoration (IR) approach. In the IR approach two independent phases are performed in each iteration—the feasibility and the optimality phases. The first one directs the iterative process into the feasible region, i.e. finds one point with less constraints violation. The optimality phase starts from this point and its goal is to optimize the objective function into the satisfied constraints space. To evaluate the solution approximations in each iteration a scheme based on the filter method is used in both phases of the algorithm. This method replaces the merit functions that are based on penalty schemes, avoiding the related difficulties such as the penalty parameter estimation and the non-differentiability of some of them. The filter method is implemented in the context of the line search globalization technique. A set of more than two hundred AMPL test problems is solved. The algorithm developed is compared with LOQO and NPSOL software packages.

Geometry based visualization with OpenCL

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

O Volume da Aurícula Esquerda como Marcador Ecocardiográfico de Prognóstico em Doentes com Miocardiopatia Dilatada

Introdução: O aumento da aurícula esquerda (AE) é um marcador de mortalidade na população geral. Os doentes com miocardiopatia dilatada (MCD) têm um amplo espetro de tamanhos deAE, mas a importância clínica desta observação tem sido pouco estudada. Objectivo: Avaliar a importância prognóstica a longo prazo do volume da AE (VAE) em doentes com MCD. Métodos: Estudo prospetivo de doentes admitidos durante o ano de 2004 com o diagnóstico deMCD, em ritmo sinusal. Foi realizado estudo ecocardiográfico completo em repouso e após stress farmacológico. O endpoint composto considerou a assistência ventricular mecânica (AVM), a transplantação cardíaca ou a morte. Resultados: Foram incluídos 35 doentes (68,6% sexo masculino, idade média 52,0), 82,9% etiologia não isquémica. Fração ejeção em repouso 31,1 ± 9,4%.Durante o seguimento, oito doentes morreram, um foi colocado em AVM e um foi transplantado. A análise de Cox univariável revelou potenciais marcadores ecocardiográficos de prognóstico na amostra tais como a dimensão da AE em modo M (HR-1,12; IC: 0,99-1,26;p = 0,067); VAE (HR-1,02; IC: 1,00-1,04; p = 0,046); VAE ajustado à superfície corporal (HR-1,03;IC: 1,00-1,07; p = 0,049); E/A (HR-0,99; IC: 0,99-1,81; p = 0,060); E/A > 2 (HR-7,00; IC:1,48-32,43; p = 0,014) e E/E’ mitral (HR-1,04; IC: 1,00-1,09; p = 0,074). Na análise multivariável a única variável que permaneceu no modelo foi o VAE com o ponto de corte de 63 ml (HR-7,7, IC:0,97-60,61, p = 0,05).Conclusão: Nesta amostra, o VAE foi o único parâmetro ecocardiográfico determinante de AVM,transplantação cardíaca ou morte. Os parâmetros ecocardiográficos habitualmente utilizadospara estratificação de risco, tais como a fração ejeção do ventrículo esquerdo, a dimensão do ventrículo esquerdo e a reserva contrátil não tiveram valor prognóstico na nossa amostra.