Looking beyond Pixels | EPFL Graph Search

Sparse recovery is a powerful tool that plays a central role in many applications, including source estimation in radio astronomy, direction of arrival estimation in acoustics or radar, super-resolution microscopy, and X-ray crystallography. Conventional approaches usually resort to discretization, where the sparse signals are estimated on a pre-defined grid. However, sparse signals do not line up conveniently on any grid in reality. While the discrete setup usually leads to a simple optimization problem that can be solved with standard tools, there are two noticeable drawbacks: (i) Because of the model mismatch, the effective noise level is increased; (ii) The minimum reachable resolution is limited by the grid step-size. Because of the limitations, it is essential to develop a technique that estimates sparse signals in the continuous-domain--in essence seeing beyond pixels.

The aims of this thesis are (i) to further develop a continuous-domain sparse recovery framework based on finite rate of innovation (FRI) sampling on both theoretical and algorithmic aspects; (ii) adapt the proposed technique to several applications, namely radio astronomy point source estimation, direction of arrival estimation in acoustics, and single image up-sampling; (iii) show that the continuous-domain sparse recovery approach can surpass the instrument resolution limit and achieve super-resolution.

We propose a continuous-domain sparse recovery technique by generalizing the FRI sampling framework to cases with non-uniform measurements. We achieve this by identifying a set of unknown uniform sinusoidal samples and the linear transformation that links the uniform samples of sinusoids to the measurements. The continuous-domain sparsity constraint can be equivalently enforced with a discrete convolution equation of these sinusoidal samples. The sparse signal is reconstructed by minimizing the fitting error between the given and the re-synthesized measurements subject to the sparsity constraint. Further, we develop a multi-dimensional sampling framework for Diracs in two or higher dimensions with linear sample complexity. This is a significant improvement over previous methods, which have a complexity that increases exponentially with dimension. An efficient algorithm has been proposed to find a valid solution to the continuous-domain sparse recovery problem such that the reconstruction (i) satisfies the sparsity constraint; and (ii) fits the measurements (up to the noise level).

We validate the flexibility and robustness of the FRI-based continuous-domain sparse recovery in both simulations and experiments with real data. We show that the proposed method surpasses the diffraction limit of radio telescopes with both realistic simulation and real data from the LOFAR radio telescope. In addition, FRI-based sparse reconstruction requires fewer measurements and smaller baselines to reach a similar reconstruction quality compared with conventional methods. Next, we apply the proposed approach to direction of arrival estimation in acoustics. We show that accurate off-grid source locations can be reliably estimated from microphone measurements with arbitrary array geometries. Finally, we demonstrate the effectiveness of the continuous-domain sparsity constraint in regularizing an otherwise ill-posed inverse problem, namely single-image super-resolution. By incorporating image edge models, the up-sampled image retains sharp edges and is free from ringing artifacts.

Towards Generalized FRI Sampling with an Application to Source Resolution in Radioastronomy

Thierry Blu, Hanjie Pan, Martin Vetterli

It is a classic problem to estimate continuous-time sparse signals, like point sources in a direction-of-arrival problem, or pulses in a time-of-flight measurement. The earliest occurrence is the estimation of sinusoids in time series using Prony's method. This is at the root of a substantial line of work on high resolution spectral estimation. The estimation of continuous-time sparse signals from discrete-time samples is the goal of the sampling theory for finite rate of innovation (FRI) signals. Both spectral estimation and FRI sampling usually assume uniform sampling. But not all measurements are obtained uniformly, as exemplified by a concrete radioastronomy problem we set out to solve. Thus, we develop the theory and algorithm to reconstruct sparse signals, typically sum of sinusoids, from non-uniform samples. We achieve this by identifying a linear transformation that relates the unknown uniform samples of sinusoids to the given measurements. These uniform samples are known to satisfy the annihilation equations. A valid solution is then obtained by solving a constrained minimization such that the reconstructed signal is consistent with the given measurements and satisfies the annihilation constraint. Thanks to this new approach, we unify a variety of FRI-based methods. We demonstrate the versatility and robustness of the proposed approach with five FRI reconstruction problems, namely Dirac reconstructions with irregular time or Fourier domain samples, FRI curve reconstructions, Dirac reconstructions on the sphere and point source reconstructions in radioastronomy. The proposed algorithm improves substantially over state of the art methods and is able to reconstruct point sources accurately from irregularly sampled Fourier measurements under severe noise conditions.

Institute of Electrical and Electronics Engineers2017

LEAP: Looking beyond pixels with continuous-space EstimAtion of Point sources

Thierry Blu, Paul Hurley, Hanjie Pan, Matthieu Martin Jean-André Simeoni, Martin Vetterli

Context. Two main classes of imaging algorithms have emerged in radio interferometry: the CLEAN algorithm and its multiple variants, and compressed-sensing inspired methods. They are both discrete in nature, and estimate source locations and intensities on a regular grid. For the traditional CLEAN-based imaging pipeline, the resolution power of the tool is limited by the width of the synthesized beam, which is inversely proportional to the largest baseline. The finite rate of innovation (FRI) framework is a robust method to find the locations of point-sources in a continuum without grid imposition. The continuous formulation makes the FRI recovery performance only dependent on the number of measurements and the number of sources in the sky. FRI can theoretically find sources below the perceived tool resolution. To date, FRI had never been tested in the extreme conditions inherent to radio astronomy: weak signal / high noise, huge data sets, large numbers of sources. Aims. The aims were (i) to adapt FRI to radio astronomy, (ii) verify it can recover sources in radio astronomy conditions with more accurate positioning than CLEAN, and possibly resolve some sources that would otherwise be missed, (iii) show that sources can be found using less data than would otherwise be required to find them, and (v) show that FRI does not lead to an augmented rate of false positives. Methods. We implemented a continuous domain sparse reconstruction algorithm in Python. The angular resolution performance of the new algorithm was assessed under simulation, and with visibility measurements from the LOFAR telescope. Existing catalogs were used to confirm the existence of sources. Results. We adapted the FRI framework to radio interferometry, and showed that it is possible to determine accurate off-grid point source locations and their corresponding intensities. In addition, FRI-based sparse reconstruction required less integration time and smaller baselines to reach a comparable reconstruction quality compared to a conventional method. The achieved angular resolution is higher than the perceived instrument resolution, and very close sources can be reliably distinguished. The proposed approach has cubic complexity in the total number (typically around a few thousand) of uniform Fourier data of the sky image estimated from the reconstruction. It is also demonstrated that the method is robust to the presence of extended-sources, and that false-positives can be addressed by choosing an adequate model order to match the noise level.

2017

Sampling the Multiple Facets of Light

Gilles Baechler

The theme of this thesis revolves around three important manifestations of light, namely its corpuscular, wave and electromagnetic nature. Our goal is to exploit these principles to analyze, design and build imaging modalities by developing new signal processing and algorithmic tools, based in particular on sampling and sparsity concepts. First, we introduce a new sampling scheme called variable pulse width, which is based on the finite rate of innovation (FRI) sampling paradigm. This new framework enables to sample and perfectly reconstruct weighted sums of Lorentzians; perfect reconstruction from sampled signals is guaranteed by a set of theorems. Second, we turn to the context of light and study its reflection, which is based on the corpuscular model of light. More precisely, we propose to use our FRI-based model to represent bidirectional reflectance distribution functions. We develop dedicated light domes to acquire reflectance functions and use the measurements obtained to demonstrate the usefulness and versatility of our model. In particular, we concentrate on the representation of specularities, which are sharp and bright components generated by the direct reflection of light on surfaces. Third, we explore the wave nature of light through Lippmann photography, a century-old photography technique that acquires the entire spectrum of visible light. This fascinating process captures interferences patterns created by the exposed scene inside the depth of a photosensitive plate. By illuminating the developed plate with a neutral light source, the reflected spectrum corresponds to that of the exposed scene. We propose a mathematical model which precisely explains the technique and demonstrate that the spectrum reproduction suffers from a number of distortions due to the finite depth of the plate and the choice of reflector. In addition to describing these artifacts, we describe an algorithm to invert them, essentially recovering the original spectrum of the exposed scene. Next, the wave nature of light is further generalized to the electromagnetic theory, which we invoke to leverage the concept of polarization of light. We also return to the topic of the representation of reflectance functions and focus this time on the separation of the specular component from the other reflections. We exploit the fact that the polarization of light is preserved in specular reflections and investigate camera designs with polarizing micro-filters with different orientations placed just in front of the camera sensor; the different polarizations of the filters create a mosaic image, from which we propose to extract the specular component. We apply our demosaicing method to several scenes and additionally demonstrate that our approach improves photometric stereo. Finally, we delve into the problem of retrieving the phase information of a sparse signal from the magnitude of its Fourier transform. We propose an algorithm that resolves the phase retrieval problem for sparse signals in three stages. Unlike traditional approaches that recover a discrete approximation of the underlying signal, our algorithm estimates the signal on a continuous domain, which makes it the first of its kind. The concluding chapter outlines several avenues for future research, like new optical devices such as displays and digital cameras, inspired by the topic of Lippmann photography.