Showing posts with label hyperspectral+CS. Show all posts
Showing posts with label hyperspectral+CS. Show all posts

Tuesday, May 14, 2019

Compressive Single-pixel Fourier Transform Imaging using Structured Illumination

** Nuit Blanche is now on Twitter: @NuitBlog **


Here is some new CS related hardware 


Single Pixel (SP) imaging is now a reality in many applications, e.g., biomedical ultrathin endoscope and fluorescent spectroscopy. In this context, many schemes exist to improve the light throughput of these device, e.g., using structured illumination driven by compressive sensing theory. In this work, we consider the combination of SP imaging with Fourier Transform Interferometry (SP-FTI) to reach high-resolution HyperSpectral (HS) imaging, as desirable, e.g., in fluorescent spectroscopy. While this association is not new, we here focus on optimizing the spatial illumination, structured as Hadamard patterns, during the optical path progression. We follow a variable density sampling strategy for space-time coding of the light illumination, and show theoretically and numerically that this scheme allows us to reduce the number of measurements and light-exposure of the observed object compared to conventional compressive SP-FTI.
Related: Single Pixel Hyperspectral Imaging using Fourier Transform Interferometry


Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Monday, July 18, 2016

An approximate message passing approach for compressive hyperspectral imaging using a simultaneous low-rank and joint-sparsity prior

ah ! Using AMP in hyperspectral imaging with sparsity and low rank, this was much needed.
 


An approximate message passing approach for compressive hyperspectral imaging using a simultaneous low-rank and joint-sparsity prior by Yangqing Li, Saurabh Prasad, Wei Chen, Changchuan Yin, Zhu Han

This paper considers a compressive sensing (CS) approach for hyperspectral data acquisition, which results in a practical compression ratio substantially higher than the state-of-the-art. Applying simultaneous low-rank and joint-sparse (L&S) model to the hyperspectral data, we propose a novel algorithm to joint reconstruction of hyperspectral data based on loopy belief propagation that enables the exploitation of both structured sparsity and amplitude correlations in the data. Experimental results with real hyperspectral datasets demonstrate that the proposed algorithm outperforms the state-of-the-art CS-based solutions with substantial reductions in reconstruction error.
 
 
 
 
 
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Friday, May 13, 2016

Follow-up to 'Making Hyperspectral Imaging Mainstream'

Following up on this morning hyperspectral approach, here are some feedback from my proposal about Making Hyperspectral Imaging Mainstream?
 

Do you remember it ? No, well go read it, I'll wait....  Ximea, the maker of hyperspectral cameras, is still pondering the issue but I got a few very good interactions out of that idea. Here they are:

From the blog comment section:
Harrison Knoll said...
This is a great idea! We here at Aerial Agriculture have been collecting hyperspectral data and will be following your progress. Let us know if there is anything you need! ~Harrison
 
Someone from Movidius  said...
Great idea - Movidius would be very supportive
Alex St. John said...
Agreed, hyperspectral space is the place for next-level analysis!

Also from Aerial Agriculture here, and am interested to follow up on this kind of project and continue building.

Alex

Indir Jaganjac 

Igor, see these hyperspectral images of natural scenes at Manchaster University site: http://personalpages.manchester.ac.uk/staff/david.foster/Hyperspectral_images_of_natural_scenes_04.html. Scenes were illuminated by direct sunlight in clear or almost clear sky. Estimated reflectance spectra (effective spectral reflectances) at each pixel in each of scenes images can be downloaded ((1017x1338x33 Matlab array). Hyperspectral imaging system that was used to acquire scene reflectances was based on low-noise Peltier-cooled digital camera providing spatial resolution of 1344x1024 pixels (Hamamatsu, model C4742-95-12ER) with fast tunable liquid-crystal filter. 

Kyle Forbes 
Experienced Software and Data Leader
That's why I started www.agrolytic.com, leveraging machine learning with hyper spectral and other spatial data to address information challenges in agriculture. 

Very interesting !

 
All hyperspectral related blog entries are under the hyperspectral tag.

In other news, here is: Image-level Classification in Hyperspectral Images using Feature Descriptors, with Application to Face Recognition  by Vivek Sharma, Luc Van Gool

In this paper, we proposed a novel pipeline for image-level classification in the hyperspectral images. By doing this, we show that the discriminative spectral information at image-level features lead to significantly improved performance in a face recognition task. We also explored the potential of traditional feature descriptors in the hyperspectral images. From our evaluations, we observe that SIFT features outperform the state-of-the-art hyperspectral face recognition methods, and also the other descriptors. With the increasing deployment of hyperspectral sensors in a multitude of applications, we believe that our approach can effectively exploit the spectral information in hyperspectral images, thus beneficial to more accurate classification.
 
 
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Hyperspectral Blind Reconstruction From Random Spectral Projections

Devising the right hardware for hyperspectral imaging thanks to a clear path from reality to image reconstruction is what the authors of the following paper enable:




This paper proposes a blind hyperspectral reconstruction technique termed spectral compressive acquisition (SpeCA) conceived to spaceborne sensors systems which are characterized by scarce onboard computing and storage resources and by communication links with reduced bandwidth. SpeCA exploits the fact that hyperspectral vectors often belong to a low-dimensional subspace and it is blind in the sense that the subspace is learned from the measured data. SpeCA encoder is computationally very light; it just computes random projections (RPs) with the acquired spectral vectors. SpeCA decoder solves a form of blind reconstruction from RPs whose complexity, although higher than that of the encoder, is very light in the sense that it requires only the modest resources to be implemented in real time. SpeCA coding/decoding scheme achieves perfect reconstruction in noise-free hyperspectral images (HSIs) and is very competitive in noisy data. The effectiveness of the proposed methodology is illustrated in both synthetic and real scenarios.
earlier:
Robust Collaborative Nonnegative Matrix Factorization For Hyperspectral Unmixing (R-CoNMF)
Jun Li, Jose M. Bioucas-Dias, Antonio Plaza, Lin Liu

The recently introduced collaborative nonnegative matrix factorization (CoNMF) algorithm was conceived to simultaneously estimate the number of endmembers, the mixing matrix, and the fractional abundances from hyperspectral linear mixtures. This paper introduces R-CoNMF, which is a robust version of CoNMF. The robustness has been added by a) including a volume regularizer which penalizes the distance to a mixing matrix inferred by a pure pixel algorithm; and by b) introducing a new proximal alternating optimization (PAO) algorithm for which convergence to a critical point is guaranteed. Our experimental results indicate that R-CoNMF provides effective estimates both when the number of endmembers are unknown and when they are known.



 
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Wednesday, March 30, 2016

Miniature Compressive Ultra-spectral Imaging System Utilizing a Single Liquid Crystal Phase Retarder

Ah! here comes the Tsunami. Multispectral was fine and back in 2007 we already noted that hyperspectral imaging (Hyperion on EO-1) overloaded distribution channels such as TDRSS, (thereby elevating the issue of Making Hyperspectral Imaging Mainstream ). Just imagine what can be done if instead of 10 or 200 spectral bands, you could get 1000 spectral bands on a CubeSat ? We may not be far from this reality according to today's entry, woohoo !





Miniature Compressive Ultra-spectral Imaging System Utilizing a Single Liquid Crystal Phase Retarder by Isaac August, Yaniv Oiknine, Marwan AbuLeil, Ibrahim Abdulhalim, and Adrian Stern

Spectroscopic imaging has been proved to be an effective tool for many applications in a variety of fields, such as biology, medicine, agriculture, remote sensing and industrial process inspection. However, due to the demand for high spectral and spatial resolution it became extremely challenging to design and implement such systems in a miniaturized and cost effective manner. Using a Compressive Sensing (CS) setup based on a single variable Liquid Crystal (LC) retarder and a sensor array, we present an innovative Miniature Ultra-Spectral Imaging (MUSI) system. The LC retarder acts as a compact wide band spectral modulator. Within the framework of CS, a sequence of spectrally modulated images is used to recover ultra-spectral image cubes. Using the presented compressive MUSI system, we demonstrate the reconstruction of gigapixel spatio-spectral image cubes from spectral scanning shots numbering an order of magnitude less than would be required using conventional systems.

 and yes, there is also the issue of Making Hyperspectral Imaging Mainstream

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Friday, December 11, 2015

Perfect Recovery Conditions For Non-Negative Sparse Modeling / Compressive hyperspectral imaging via adaptive sampling and dictionary learning

 


Perfect Recovery Conditions For Non-Negative Sparse Modeling by Yuki Itoh, Marco F. Duarte, Mario Parente

Sparse modeling has been widely and successfully used in many applications such as computer vision, machine learning, and pattern recognition and, accompanied with those applications, significant research has studied the theoretical limits and algorithm design for convex relaxations in sparse modeling. However, only little has been done for theoretical limits of non-negative versions of sparse modeling. The behavior is expected to be similar as the general sparse modeling, but a precise analysis has not been explored. This paper studies the performance of non-negative sparse modeling, especially for non-negativity constrained and ℓ1-penalized least squares, and gives an exact bound for which this problem can recover the correct signal elements. We pose two conditions to guarantee the correct signal recovery: minimum coefficient condition (MCC) and non-linearity vs. subset coherence condition (NSCC). The former defines the minimum weight for each of the correct atoms present in the signal and the latter defines the tolerable deviation from the linear model relative to the positive subset coherence (PSC), a novel type of "coherence" metric. We provide rigorous performance guarantees based on these conditions and experimentally verify their precise predictive power in a hyperspectral data unmixing application.
 
 

In this paper, we propose a new sampling strategy for hyperspectral signals that is based on dictionary learning and singular value decomposition (SVD). Specifically, we first learn a sparsifying dictionary from training spectral data using dictionary learning. We then perform an SVD on the dictionary and use the first few left singular vectors as the rows of the measurement matrix to obtain the compressive measurements for reconstruction. The proposed method provides significant improvement over the conventional compressive sensing approaches. The reconstruction performance is further improved by reconditioning the sensing matrix using matrix balancing. We also demonstrate that the combination of dictionary learning and SVD is robust by applying them to different datasets.
 
 
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Tuesday, September 29, 2015

Anomaly Detection in High Dimensional Data: Hyperspectral data, movies and more...


From the CAIB report featured in The Modeler's Known Unknowns and Unknown Knowns
 
Anomaly detection is when you are concerned with the "unknown unknowns" or to put it in a perspective that is currently solely missing from many algorithms: you are dealing with sometimes adversarial/evading counterparties or unexpected/outside model behaviors (outliers). There are some very sophisticated algorithms in machine learning and compressive sensing dealing with detailed classifications but when faced with unkown unknowns, you want to quantify anomaly detection or how far data is from your "frame-of-mind" model. High dimensional data afforded by cheap memory and CMOS is likely making these needles hard to find. Here are some recent preprints that showed up on my radar screen recently on the subject. And yes sparsity is sometimes key to detect them. Enjoy !




We discuss recent progress in techniques for modeling and analyzing hyperspectral images and movies, in particular for detecting plumes of both known and unknown chemicals. We discuss novel techniques for robust modeling of the background in a hyperspectral scene, and for detecting chemicals of known spectrum, we use partial least squares regression on a resampled training set to boost performance. For the detection of unknown chemicals we view the problem as an anomaly detection problem, and use novel estimators with low-sampled complexity for intrinsically low-dimensional data in high-dimensions that enable use to model the "normal" spectra and detect anomalies. We apply these algorithms to benchmark data sets made available by Lincoln Labs at the Automated Target Detection program co-funded by NSF, DTRA and NGA, and compare, when applicable, to current state-of-art algorithms, with favorable results.
Optimal Sparse Kernel Learning for Hyperspectral Anomaly Detection
Zhimin Peng, Prudhvi Gurram, Heesung Kwon, Wotao Yin

In this paper, a novel framework of sparse kernel learning for Support Vector Data Description (SVDD) based anomaly detection is presented. In this work, optimal sparse feature selection for anomaly detection is first modeled as a Mixed Integer Programming (MIP) problem. Due to the prohibitively high computational complexity of the MIP, it is relaxed into a Quadratically Constrained Linear Programming (QCLP) problem. The QCLP problem can then be practically solved by using an iterative optimization method, in which multiple subsets of features are iteratively found as opposed to a single subset. The QCLP-based iterative optimization problem is solved in a finite space called the \emph{Empirical Kernel Feature Space} (EKFS) instead of in the input space or \emph{Reproducing Kernel Hilbert Space} (RKHS). This is possible because of the fact that the geometrical properties of the EKFS and the corresponding RKHS remain the same. Now, an explicit nonlinear exploitation of the data in a finite EKFS is achievable, which results in optimal feature ranking. Experimental results based on a hyperspectral image show that the proposed method can provide improved performance over the current state-of-the-art techniques.

MultiView Diffusion Maps
Ofir Lindenbaum, Arie Yeredor, Moshe Salhov, Amir Averbuch

In this study we consider learning a reduced dimensionality representation from datasets obtained under multiple views. Such multiple views of datasets can be obtained, for example, when the same underlying process is observed using several different modalities, or measured with different instrumentation. Our goal is to effectively exploit the availability of such multiple views for various purposes, such as non-linear embedding, manifold learning, spectral clustering, anomaly detection and non-linear system identification. Our proposed method exploits the intrinsic relation within each view, as well as the mutual relations between views. We do this by defining a cross-view model, in which an implied Random Walk process between objects is restrained to hop between the different views. Our method is robust to scaling of each dataset, and is insensitive to small structural changes in the data. Within this framework, we define new diffusion distances and analyze the spectra of the implied kernels. We demonstrate the applicability of the proposed approach on both artificial and real data sets.

A Framework of Sparse Online Learning and Its Applications by Dayong Wang, Pengcheng Wu, Peilin Zhao, Steven C.H. Hoi

The amount of data in our society has been exploding in the era of big data today. In this paper, we address several open challenges of big data stream classification, including high volume, high velocity, high dimensionality, high sparsity, and high class-imbalance. Many existing studies in data mining literature solve data stream classification tasks in a batch learning setting, which suffers from poor efficiency and scalability when dealing with big data. To overcome the limitations, this paper investigates an online learning framework for big data stream classification tasks. Unlike some existing online data stream classification techniques that are often based on first-order online learning, we propose a framework of Sparse Online Classification (SOC) for data stream classification, which includes some state-of-the-art first-order sparse online learning algorithms as special cases and allows us to derive a new effective second-order online learning algorithm for data stream classification. In addition, we also propose a new cost-sensitive sparse online learning algorithm by extending the framework with application to tackle online anomaly detection tasks where class distribution of data could be very imbalanced. We also analyze the theoretical bounds of the proposed method, and finally conduct an extensive set of experiments, in which encouraging results validate the efficacy of the proposed algorithms in comparison to a family of state-of-the-art techniques on a variety of data stream classification tasks.


This paper presents a new approach, based on polynomial optimization and the method of moments, to the problem of anomaly detection. The proposed technique only requires information about the statistical moments of the normal-state distribution of the features of interest and compares favorably with existing approaches (such as Parzen windows and 1-class SVM). In addition, it provides a succinct description of the normal state. Thus, it leads to a substantial simplification of the the anomaly detection problem when working with higher dimensional datasets.


Anomaly Detection in Unstructured Environments using Bayesian Nonparametric Scene Modeling
Yogesh Girdhar, Walter Cho, Matthew Campbell, Jesus Pineda, Elizabeth Clarke, Hanumant Singh

This paper explores the use of a Bayesian non-parametric topic modeling technique for the purpose of anomaly detection in video data. We present results from two experiments. The first experiment shows that the proposed technique is automatically able characterize the underlying terrain, and detect anomalous flora in image data collected by an underwater robot. The second experiment shows that the same technique can be used on images from a static camera in a dynamic unstructured environment. The second dataset consisting of video data from a static seafloor camera, capturing images of a busy coral reef. The proposed technique was able to detect all three instances of an underwater vehicle passing in front of the camera, amongst many other observations of fishes, debris, lighting changes due to surface waves, and benthic flora.

Sparsity in Multivariate Extremes with Applications to Anomaly Detection
Nicolas Goix (LTCI), Anne Sabourin (LTCI), Stéphan Clémençon (LTCI)
(Submitted on 21 Jul 2015)
Capturing the dependence structure of multivariate extreme events is a major concern in many fields involving the management of risks stemming from multiple sources, e.g. portfolio monitoring, insurance, environmental risk management and anomaly detection. One convenient (non-parametric) characterization of extremal dependence in the framework of multivariate Extreme Value Theory (EVT) is the angular measure, which provides direct information about the probable 'directions' of extremes, that is, the relative contribution of each feature/coordinate of the 'largest' observations. Modeling the angular measure in high dimensional problems is a major challenge for the multivariate analysis of rare events. The present paper proposes a novel methodology aiming at exhibiting a sparsity pattern within the dependence structure of extremes. This is done by estimating the amount of mass spread by the angular measure on representative sets of directions, corresponding to specific sub-cones of Rd_+. This dimension reduction technique paves the way towards scaling up existing multivariate EVT methods. Beyond a non-asymptotic study providing a theoretical validity framework for our method, we propose as a direct application a --first-- anomaly detection algorithm based on multivariate EVT. This algorithm builds a sparse 'normal profile' of extreme behaviours, to be confronted with new (possibly abnormal) extreme observations. Illustrative experimental results provide strong empirical evidence of the relevance of our approach.

Universal Anomaly Detection: Algorithms and Applications
Shachar Siboni, Asaf Cohen

Modern computer threats are far more complicated than those seen in the past. They are constantly evolving, altering their appearance, perpetually changing disguise. Under such circumstances, detecting known threats, a fortiori zero-day attacks, requires new tools, which are able to capture the essence of their behavior, rather than some fixed signatures. In this work, we propose novel universal anomaly detection algorithms, which are able to learn the normal behavior of systems and alert for abnormalities, without any prior knowledge on the system model, nor any knowledge on the characteristics of the attack. The suggested method utilizes the Lempel-Ziv universal compression algorithm in order to optimally give probability assignments for normal behavior (during learning), then estimate the likelihood of new data (during operation) and classify it accordingly. The suggested technique is generic, and can be applied to different scenarios. Indeed, we apply it to key problems in computer security. The first is detecting Botnets Command and Control (C&C) channels. A Botnet is a logical network of compromised machines which are remotely controlled by an attacker using a C&C infrastructure, in order to perform malicious activities. We derive a detection algorithm based on timing data, which can be collected without deep inspection, from open as well as encrypted flows. We evaluate the algorithm on real-world network traces, showing how a universal, low complexity C&C identification system can be built, with high detection rates and low false-alarm probabilities. Further applications include malicious tools detection via system calls monitoring and data leakage identification.

Anomaly Detection for malware identification using Hardware Performance Counters by Alberto Garcia-Serrano

Computers are widely used today by most people. Internet based applications, like ecommerce or ebanking attracts criminals, who using sophisticated techniques, tries to introduce malware on the victim computer. But not only computer users are in risk, also smartphones or smartwatch users, smart cities, Internet of Things devices, etc. Different techniques has been tested against malware. Currently, pattern matching is the default approach in antivirus software. Also, Machine Learning is successfully being used. Continuing this trend, in this article we propose an anomaly based method using the hardware performance counters (HPC) available in almost any modern computer architecture. Because anomaly detection is an unsupervised process, new malware and APTs can be detected even if they are unknown.

 
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Tuesday, July 14, 2015

Video: Compressive Hyperspectral Imaging via Approximate Message Passing

As New Horizons flies-by Pluto today, at a speed of 16+ km/s there will be a short window of opportunity for the spacecraft to perform the most accurate images of this planet before it continues its journey to the Kuyper belt (the speed of the spacecraft makes it impossible to orbit Pluto).




Images like the one above are taken by LORRI and are black and white (panchromatic) but the instrument that will provide much of the science data for this Pluto encounter will be Ralph 

...Ralph consists of three panchromatic (black-and-white) and four color imagers inside its Multispectral Visible Imaging Camera (MVIC), as well as an infrared compositional mapping spectrometer called the Linear Etalon Imaging Spectral Array (LEISA). LEISA is an advanced, miniaturized short-wavelength infrared (1.25-2.50 micron) spectrometer provided by scientists from NASA’s Goddard Space Flight Center. MVIC operates over the bandpass from 0.4 to 0.95 microns. Ralph’s suite of eight detectors – seven charge-coupled devices (CCDs) like those found in a digital camera, and a single infrared array detector – are fed by a single, sensitive magnifying telescope with a resolution more than 10 times better than the human eye can see. The entire package operates on less than half the wattage of an appliance light bulb.
 More detailed on this camera can be found here.

All this to say, that any improvement on obtaining hyperspectral data, such as the one provided by Ralph  during the fly-by, coupled with compression from cheap (powerwise) hardware could eventually be very useful to future space missions (please note the 6.3 watts power use of the camera). It so happens that in compressive sensing, we have the beginning of an answer as exemplified by the hardware in the CASSI imager (many of the blog entries relating to Hyperspectral imaging and ompressive sensing can be found under this tag.)

 Today, Dror and colleagues show us how to reconstruct hyperspectral images when they are taken by these compressive imagers using AMP solvers. Here is the tutorial video made by Jin Tan and Yanting Ma  followed by their preprint:




Compressive Hyperspectral Imaging via Approximate Message Passing by  Jin Tan, Yanting Ma, Hoover Rueda, Dror Baron, Gonzalo Arce

We consider a compressive hyperspectral imaging reconstruction problem, where three-dimensional spatio-spectral information about a scene is sensed by a coded aperture snapshot spectral imager (CASSI). The CASSI imaging process can be modeled as suppressing three-dimensional coded and shifted voxels and projecting these onto a two-dimensional plane, such that the number of acquired measurements is greatly reduced. On the other hand, because the measurements are highly compressive, the reconstruction process becomes challenging. We previously proposed a compressive imaging reconstruction algorithm that is applied to two-dimensional images based on the approximate message passing (AMP) framework. AMP is an iterative algorithm that can be used in signal and image reconstruction by performing denoising at each iteration. We employed an adaptive Wiener filter as the image denoiser, and called our algorithm "AMP-Wiener." In this paper, we extend AMP-Wiener to three-dimensional hyperspectral image reconstruction. Applying the AMP framework to the CASSI system is challenging, because the matrix that models the CASSI system is highly sparse, and such a matrix is not suitable to AMP and makes it difficult for AMP to converge. Therefore, we modify the adaptive Wiener filter to fit the three-dimensional image denoising problem, and employ a technique called damping to solve for the divergence issue of AMP. Our simulation results show that AMP-Wiener in three-dimensional hyperspectral imaging problems outperforms existing widely-used algorithms such as gradient projection for sparse reconstruction (GPSR) and two-step iterative shrinkage/thresholding (TwIST) given the same amount of runtime. Moreover, in contrast to GPSR and TwIST, AMP-Wiener need not tune any parameters, which simplifies the reconstruction process.
 
Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Southwest Research Institute
 
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Wednesday, October 01, 2014

Sparse Representation Issues in Hyperspectral and Multispectral Images

I just compiled a list of a few preprints and papers that recently came out in support of hyperspectral work and its relation to either compressive sensing or advanced matrix factorization. Without further ado:




This paper considers a recently emerged hyperspectral unmixing formulation based on sparse regression of a self-dictionary multiple measurement vector (SD-MMV) model, wherein the measured hyperspectral pixels are used as the dictionary. Operating under the pure pixel assumption, this SD-MMV formalism is special in enabling simultaneous identification of the endmember spectral signatures and the number of endmembers. Previous SD-MMV studies mainly focus on convex relaxations. In this study, we explore the alternative of greedy pursuit, which generally provides efficient and simple algorithms. In particular, we design a greedy SD-MMV algorithm using simultaneous orthogonal matching pursuit. Intriguingly, the proposed greedy algorithm is shown to be closely related to some existing pure pixel search algorithms, especially, the successive projection algorithm (SPA). Thus, a link between SD-MMV and pure pixel search is revealed. We then perform exact recovery analyses, and prove that the proposed greedy algorithm is robust to noise---including its identification of the (unknown) number of endmembers---under a sufficiently low noise level. The identification performance of the proposed greedy algorithm is demonstrated through both synthetic and real-data experiments.

Hyperspectral and Multispectral Image Fusion based on a Sparse Representation by Qi Wei, José Bioucas-Dias, Nicolas Dobigeon, Jean-Yves Tourneret
This paper presents a variational based approach to fusing hyperspectral and multispectral images. The fusion process is formulated as an inverse problem whose solution is the target image assumed to live in a much lower dimensional subspace. A sparse regularization term is carefully designed, relying on a decomposition of the scene on a set of dictionaries. The dictionary atoms and the corresponding supports of active coding coefficients are learned from the observed images. Then, conditionally on these dictionaries and supports, the fusion problem is solved via alternating optimization with respect to the target image (using the alternating direction method of multipliers) and the coding coefficients. Simulation results demonstrate the efficiency of the proposed algorithm when compared with the state-of-the-art fusion methods.

Effective Spectral Unmixing via Robust Representation and Learning-based Sparsity by Feiyun Zhu, Ying Wang, Bin Fan, Gaofeng Meng, Chunhong Pan
Hyperspectral unmixing (HU) plays a fundamental role in a wide range of hyperspectral applications. It is still challenging due to the common presence of outlier channels and the large solution space. To address the above two issues, we propose a novel model by emphasizing both robust representation and learning-based sparsity. Specifically, we apply the $\ell_{2,1}$-norm to measure the representation error, preventing outlier channels from dominating our objective. In this way, the side effects of outlier channels are greatly relieved. Besides, we observe that the mixed level of each pixel varies over image grids. Based on this observation, we exploit a learning-based sparsity method to simultaneously learn the HU results and a sparse guidance map. Via this guidance map, the sparsity constraint in the $\ell_{p}\!\left(\!0\!<\! p\!\leq\!1\right)$-norm is adaptively imposed according to the learnt mixed level of each pixel. Compared with state-of-the-art methods, our model is better suited to the real situation, thus expected to achieve better HU results. The resulted objective is highly non-convex and non-smooth, and so it is hard to optimize. As a profound theoretical contribution, we propose an efficient algorithm to solve it. Meanwhile, the convergence proof and the computational complexity analysis are systematically provided. Extensive evaluations verify that our method is highly promising for the HU task---it achieves very accurate guidance maps and much better HU results compared with state-of-the-art methods.


This paper presents a conceptually simple, robust, yet highly effective approach to both texture classification and material categorization. The proposed system is composed of three components: (1) local, highly discriminative, and robust features based on sorted random projections, built on the universal and information-preserving properties of random projections; (2) an effective Bag-of-Words (BoW) global model; and (3) a novel approach for combining multiple features in a Support Vector Machine (SVM) classifier. The proposed approach encompasses the simplicity, broad applicability, and efficiency of the three methods. We have tested the proposed approach on eight popular texture databases, including FMD, a highly challenging materials database. We compare our method with thirteen recent stateof- the-art methods, and the experimental results show that our texture classification system yields the best classification rates of which we are aware of 99.37% for CUReT, 97.16% for Brodatz, 99.30% for UMD and 99.29% for KTH-TIPS. Moreover, the proposed approach significantly outperforms the current state-of-the-art approach in materials categorization, with an improvement to classification accuracy of 67%. 



Many powerful pansharpening approaches exploit the functional relation between the fusion of PANchromatic (PAN) and MultiSpectral (MS) images. To this purpose, the modulation transfer function of the MS sensor is typically used, being easily approximated as a Gaussian filter whose analytic expression is fully specified by the sensor gain at the Nyquist frequency. However, this characterization is often inadequate in practice. In this paper, we develop an algorithm for estimating the relation between PAN and MS images directly from the available data through an efficient optimization procedure. The effectiveness of the approach is validated both on a reduced scale data set generated by degrading images acquired by the IKONOS sensor and on full-scale data consisting of images collected by the QuickBird sensor. In the first case, the proposed method achieves performances very similar to that of the algorithm that relies upon the full knowledge of the degrading filter. In the second, it is shown to outperform several very credited state-of-the-art approaches for the extraction of the details used in the current literature.
of related interest:

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Saturday, July 06, 2013

Sunday Morning Insight: Faster Than a Blink of an Eye



If you recall in a recent Sunday Morning Insight: A Quick Panorama of Sensing from Direct Imaging to Machine Learning I pointed out that coded aperture imaging fell in the indirect imaging category with initially a linear encoder and linear decoder:

x = L(Ax)

But then with people like Zachary Harmany, Roummel Marcia, and Rebecca Willett, these systems could also be looked at as a compressive sensing ones with the following decomposition:

x = N(Ax) or even x = N(A(Bx))

with a linear encoder but a nonlinear decoder.




This paper describes a coded aperture and keyed exposure approach to compressive video measurement which admits a small physical platform, high photon efficiency, high temporal resolution, and fast reconstruction algorithms. The proposed projections satisfy the Restricted Isometry Property (RIP), and hence compressed sensing theory provides theoretical guarantees on the video reconstruction quality. Moreover, the projections can be easily implemented using existing optical elements such as spatial light modulators (SLMs). We extend these coded mask designs to novel dual-scale masks (DSMs) which enable the recovery of a coarse-resolution estimate of the scene with negligible computational cost. We develop fast numerical algorithms which utilize both temporal correlations and optical flow in the video sequence as well as the innovative structure of the projections. Our numerical experiments demonstrate the efficacy of the proposed approach on short-wave infrared data.
I note the following tidbit:

In summary we see that the CAKE acquisitions are able to outperform traditionally sampled video in terms of reconstruction accuracy and reconstructing salient motion. On average, to reconstruct the 28 video frames, CAKE took 96 minutes and Dual-Scale Mask CAKE took 93 minutes, while CAKE with Optical Flow took only 31 minutes. Conventional spline upsampling took nearly 23 seconds
Emphasis is mine.

Ever since the beginning of compressive sensing, signal/image reconstruction has been Achille's heel of the technique. And as shown in this last paper, it is still an issue. This is very salient problem because it also means that any other technology developed with compressive sensing in mind, is likely to be a second class citizen to more direct, faster but less precise approaches. Like we say in Texas, it's a damn shame because compressive sensing allows new kinds of data acquisition (hyperspectral, 1-bit,...) with an attendant reduction in complexity on the hardware/sensor side. It's not just a question of nice sensors, it's an issue of direct economical impact. Who wouldn't want that ? These new fields will not develop or will remain a niche and expensive if the issue of data reconstruction is not solved. What's on the horizon ?

 Let us first note that in the first few years, reconstruction speed increased dramatically allowing an order of magnitude speed gain per year for about three years.





This was nice, but the trend did not continue at that pace.

Let us turn our attention to different modalities that are currently being developed to see if there is a way we can leap forward in the future. All modalities I know seem to fall in the same broad category which follows some of the early thinking from neurosciences: build a neutral network with little if any feedback.  ( see this 2007's entry on Compressed Sensing in the Primary Visual Cortex ?, Compressed Sensing, Primary Visual Cortex, Dimensionality Reduction, Manifolds and Autism )

and I found three:

First,  there is this approach by Aurele Balavoine, Chris Rozell, Justin Romberg [1,2] that builds up a analog neural network and study if it converges to the expected sparse solutions:

The Locally Competitive Algorithm (LCA) [8] is a continuous-time system of coupled nonlinear differential equations that settles to the minimizer of (1) in steady state [9]. The LCA architecture consists of simple components (matrixvector operations and a pointwise nonlinearity for thresholding), giving it the potential to be implemented in an analog circuit [10], [11]. Analog networks for solving optimization problems have a long history, dating back to Hopfield’s pioneering results for linear programming [12] (a comprehensive treatment of the subject can be found in [13]). Such analog systems can potentially have significant speed and power advantages over their digital counterparts.
and what do they find ?





that indeed few of neutral network branches were activated for sparse inputs! This is good, 

The second approach follows that of machine learning as applied in computer vision through the recent breakthrough in deep learning, i.e. the utilization of neutral networks with some unsupervised training algorithms to perform sparse coding. In the end and as mentioned in Sunday Morning Insight: A Quick Panorama of Sensing from Direct Imaging to Machine Learning. It comes down to the ability to build an encoder/decoder pair with a neutral network and using the right regularization to find some of the weights of the network. Examples of approaches mostly by the group of Yann LeCun can be found in  [5,6,7,8,9]


From [7]

From [8]

From [8]

From [3]


Finally, Pablo Sprechmann, Alex Bronstein, Guillermo Sapiro [3,4] made the case that a proximal approach could be implemented on learning encoder/decoder couples in order to produce an online sparse coding capability. It turns out that the iterative process can be truncated and directly mapped into a neutral network type of approach [5,6] 
In their inspiring recent paper, [30] showed that a particular network architecture can be derived from the iterative shrinkage-thresholding (ISTA) [17] and proximal coordinate descent (CoD) algorithms [19].

That approach leads to very fast sparse coding and NMF decomposition type of results. As they point out in [3]

These works were among the first to bridge between the optimization based sparse models and the inherently process-centric neural networks, and in particular auto-encoder networks [31, 32], extensively explored by the deep learning community.


(please note the use of an iPad for the reconstruction task)

So roughly, all these solutions seem to converge toward a nonlinear reconstruction technique using neural networks or equivalent that have online training capabilities. I wonder how, instead of ISTA/FISTA, an AMP solution would provide an even faster capability since we know these iterations schemes to be pretty fast. It looks like the connection between neural networks and belief propagation is being made [10] (see also Blind Calibration in Compressed Sensing using Message Passing Algorithms )

Finally, I note that in most of these approaches based on computer vision, the dictionary learning phase uses the sparsity of the elements of the scene. In a compressive sensing scenario, the acquisition system captures an already compressed ( i.e. non sparse) version of the scene. 

References:

Sparse approximation is an optimization program that produces state-of-the-art results in many applications in signal processing and engineering. To deploy this approach in real-time, it is necessary to develop faster solvers than are currently available in digital. The Locally Competitive Algorithm (LCA) is a dynamical system designed to solve the class of sparse approximation problems in continuous time. But before implementing this network in analog VLSI, it is essential to provide performance guarantees. This paper presents new results on the convergence of the LCA neural network. Using recently developed methods that make use of the Łojasiewicz inequality for nonsmooth functions, we prove that the output and state trajectories converge to a single fixed point. This improves on previous results by guaranteeing convergence to a singleton even when the optimization program has infinitely many and nonisolated solution points.

Abstract—This paper studies the convergence rate of a continuous-time dynamical system for `1-minimization, known as the Locally Competitive Algorithm (LCA). Solving `1-minimization problems efficiently and rapidly is of great interest to the signal processing community, as these programs have been shown to recover sparse solutions to underdetermined systems of linear equations and come with strong performance guarantees. The LCA under study differs from the typical `1-solver in that it operates in continuous time: instead of being specified by discrete iterations, it evolves according to a system of nonlinear ordinary differential equations. The LCA is constructed from simple components, giving it the potential to be implemented as a large-scale analog circuit. The goal of this paper is to give guarantees on the convergence time of the LCA system. To do so, we analyze how the LCA evolves as it is recovering a sparse signal from underdetermined measurements. We show that under appropriate conditions on the measurement matrix and the problem parameters, the path the LCA follows can be described as a sequence of linear differential equations, each with a small number of active variables. This allows us to relate the convergence time of the system to the restricted isometry constant of the matrix. Interesting parallels to sparse-recovery digital solvers emerge from this study. Our analysis covers both the noisy and noiseless settings and is supported by simulation results.
Parsimony, including sparsity and low rank, has been shown to successfully model data in numerous machine learning and signal processing tasks. Traditionally, such modeling approaches rely on an iterative algorithm that minimizes an objective function with parsimony-promoting terms. The inherently sequential structure and data-dependent complexity and latency of iterative optimization constitute a major limitation in many applications requiring real-time performance or involving large-scale data. Another limitation encountered by these modeling techniques is the difficulty of their inclusion in discriminative learning scenarios. In this work, we propose to move the emphasis from the model to the pursuit algorithm, and develop a process-centric view of parsimonious modeling, in which a learned deterministic fixed-complexity pursuit process is used in lieu of iterative optimization. We show a principled way to construct learnable pursuit process architectures for structured sparse and robust low rank models, derived from the iteration of proximal descent algorithms. These architectures learn to approximate the exact parsimonious representation at a fraction of the complexity of the standard optimization methods. We also show that appropriate training regimes allow to naturally extend parsimonious models to discriminative settings. State-of-the-art results are demonstrated on several challenging problems in image and audio processing with several orders of magnitude speedup compared to the exact optimization algorithms.


In Sparse Coding (SC), input vectors are reconstructed using a sparse linear combination of basis vectors. SC has become a popular method for extracting features from data. For a given input, SC minimizes a quadratic reconstruction error with an L1 penalty term on the code. The process is often too slow for applications such as real-time pattern recognition. We proposed two versions of a very fast algorithm that produces approximate estimates of the sparse code that can be used to compute good visual features, or to initialize exact iterative algorithms. The main idea is to train a non-linear, feed-forward predictor with a specific architecture and a fixed depth to produce the best possible approximation of the sparse code. A version of the method, which can be seen as a trainable version of Li and Osher’s coordinate descent method, is shown to produce approximate solutions with 10 times less computation than Li and Osher’s for the same approximation error. Unlike previous proposals for sparse code predictors, the system allows a kind of approximate “explaining away” to take place during inference. The resulting predictor is differentiable and can be included into globally trained recognition systems.
We describe a method for fast approximation of sparse coding. A given input vector is passed through a binary tree. Each leaf of the tree contains a subset of dictionary elements. The coefficients corresponding to these dictionary elements are allowed to be nonzero and their values are calculated quickly by multiplication with a precomputed pseudoinverse. The tree parameters, the dictionary, and the subsets of the dictionary corresponding to each leaf are learned.In the process of describing this algorithm, we discuss the more general problem of learning the groups in group structured sparse modeling. We show that our method creates good sparse representations by using it in the object recognition framework of [1,2]. Implementing our own fast version of the SIFT descriptor the whole system runs at 20 frames per second on 321 × 481 sized images on alaptop with a quad-core cpu, while sacrificing very little accuracy on the Caltech101, Caltech 256, and 15 scenes benchmarks.
[7] Li Wan, Matthew Zeiler, Sixin Zhang, Yann LeCun and Rob Fergus: Regularization of Neural Networks using DropConnect. DropConnect CUDA Code and page is here.
We introduce DropConnect, a generalization of Dropout (Hinton et al., 2012), for regularizing large fully-connected layers within neural networks. When training with Dropout, a randomly selected subset of activations are set to zero within each layer. DropConnect instead sets a randomly selected subset of weights within the network to zero. Each unit thus receives input from a random subset of units in the previous layer. We derive a bound on the generalization performance of both Dropout and DropConnect. We then evaluate DropConnect on a range of datasets, comparing to Dropout, and show state-of-the-art results on several image recognition benchmarks by aggregating multiple DropConnect-trained models.
We present the discriminative recurrent sparse auto-encoder model, comprising a recurrent encoder of rectified linear units, unrolled for a fixed number of iterations, and connected to two linear decoders that reconstruct the input and predict its supervised classification. Training via backpropagation-through-time initially minimizes an unsupervised sparse reconstruction error; the loss function is then augmented with a discriminative term on the supervised classification. The depth implicit in the temporally-unrolled form allows the system to exhibit far more representational power, while keeping the number of trainable parameters fixed. From an initially unstructured network the hidden units differentiate into categorical-units, each of which represents an input prototype with a well-defined class; and part-units representing deformations of these prototypes. The learned organization of the recurrent encoder is hierarchical: part-units are driven directly by the input, whereas the activity of categorical-units builds up over time through interactions with the part-units. Even using a small number of hidden units per layer, discriminative recurrent sparse auto-encoders achieve excellent performance on MNIST.

[9] Rotislav Goroshin and Yann LeCun: Saturating Auto-Encoders.
We introduce a simple new regularizer for auto-encoders whose hidden-unit activation functions contain at least one zero-gradient (saturated) region. This regularizer explicitly encourages activations in the saturated region(s) of the corresponding activation function. We call these Saturating Auto-Encoders (SATAE). We show that the saturation regularizer explicitly limits the SATAE’s ability to reconstruct inputs which are not near the data manifold. Furthermore, we show that a wide variety of features can be learned when different activation functions are used. Finally, connections are established with the Contractive and Sparse Auto-Encoders.
[10] Intrinsic Gradient Networks, Jason Tyler Rolfe
Artificial neural networks are computationally powerful and exhibit brain-like dynamics. Unfortunately, the conventional gradient-dependent learning algorithms used to train them are biologically implausible. The calculation of the gradient in a traditional artificial neural network requires a complementary network of fast training signals that are dependent upon, but must not affect, the primary output-generating network activity. In contrast, the network of neurons in the cortex is highly recurrent; a network of gradient-calculating neurons in the brain would certainly project back to and influence the primary network. We address this biological implausibility by introducing a novel class of recurrent neural networks, intrinsic gradient networks, for which the gradient of an error function with respect to the parameters is a simple function of the network state. These networks can be trained using only their intrinsic signals, much like the network of neurons in the brain.
We derive a simple equation that characterizes intrinsic gradient networks, and construct a broad set of networks that satisfy this characteristic equation. The resulting set of intrinsic gradient networks includes many highly recurrent instances for which the gradient can be calculated by a simple, local, pseudo-Hebbian function of the network state, thus resolving a long-standing contradiction between artificial and biological neural networks. We demonstrate that these networks can learn to perform nontrivial tasks like handwritten digit recognition using only their intrinsic signals. Finally, we show that a cortical implementation of an intrinsic gradient network would have a number of characteristic computational, anatomical, and electrophysiological properties, and review experimental
evidence suggesting the manifestation of these properties in the cortex.




Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Printfriendly