Search

Recently a sampling theorem for a certain class of signals with finite rate of innovation (which includes for example stream of Diracs) has been developed. In essence, such non band-limited signals can be sampled at or above the rate of innovation. In the present paper, we consider the case of such signals when noise is present. Clearly, the finite rate of innovation property is lost, but if the signal-to-noise ratio (SNR) is sufficient, several methods are possible to reconstruct the signal while sampling well below the Nyquist rate. We thus explore the trade-offs between SNR, sampling rate, computational complexity and reconstruction quality. Applications of such methods can be found in acquisition and processing of signals in high bandwidth communications, like ultra wide band communication.

Traditional sampling results assume that the sample locations are known. Motivated by simultaneous localization and mapping (SLAM) and structure from motion (SfM), we investigate sampling at unknown locations. Without further constraints, the problem is often hopeless. For example, we recently showed that, for polynomial and bandlimited signals, it is possible to find two signals, arbitrarily far from each other, that fit the measurements. However, we also showed that this can be overcome by adding constraints to the sample positions. In this paper, we show that these constraints lead to a uniform sampling of a composite of functions. Furthermore, the formulation retains the key aspects of the SLAM and SfM problems, whilst providing uniqueness, in many cases. We demonstrate this by studying two simple examples of constrained sampling at unknown locations. In the first, we consider sampling a periodic bandlimited signal composite with an unknown linear function. We derive the sampling requirements for uniqueness and present an algorithm that recovers both the bandlimited signal and the linear warping. Furthermore, we prove that, when the requirements for uniqueness are not met, the cases of multiple solutions have measure zero. For our second example, we consider polynomials sampled such that the sampling positions are constrained by a rational function. We previously proved that, if a specific sampling requirement is met, uniqueness is achieved. In addition, we present an alternate minimization scheme for solving the resulting non-convex optimization problem. Finally, fully reproducible simulation results are provided to support our theoretical analysis.

We consider the problem of sampling at unknown locations. We prove that, in this setting, if we take arbitrarily many samples of a polynomial or real bandlimited signal, it is possible to find another function in the same class, arbitrarily far away from the original, that could have generated the same samples. In other words, the error can be arbitrarily large.Motivated by this, we prove that, for polynomials, if the sample positions are constrained such that they can be described by an unknown rational function, uniqueness can be achieved.In addition to our theoretical results, we show that, in 1-D, the problem of recovering a painted surface from a single image exactly fits this framework. Furthermore, we propose a simple iterative algorithm for recovering both the surface and the texture and test it with simple simulations.

In many applications, the sampling frequency is limited by the physical characteristics of the components: the pixel pitch, the rate of the A/D converter, etc. A low-pass filter is then often applied before the sampling operation to avoid aliasing. However, when multiple copies are available, it is possible to use the information that is inherently present in the aliasing to reconstruct a higher resolution signal. If the different copies have unknown relative offsets, this is a non-linear problem in the offsets and the signal coefficients. They are not easily separable in the set of equations describing the super-resolution problem. Thus, we perform joint registration and reconstruction from multiple unregistered sets of samples. We give a mathematical formulation for the problem when there are M sets of N samples of a signal that is described by L expansion coefficients. We prove that the solution of the registration and reconstruction problem is generically unique if MN >= L+M-1. We describe two subspace-based methods to compute this solution. Their complexity is analyzed, and some heuristic methods are proposed. Finally, some numerical simulation results on one and two-dimensional signals are given to show the performance of these methods.

Most digital cameras employ a spatial subsampling process, implemented as a color filter array (CFA), to capture color images. The choice of CFA patterns has a great impact on the performance of subsequent reconstruction (demosaicking) algorithms. In this work, we propose a quantitative theory for optimal CFA design. We view the CFA sampling process as an encoding (low- dimensional approximation) operation and, correspondingly, demosaicking as the best decoding (reconstruction) operation. Finding the optimal CFA is thus equivalent to finding the optimal approximation scheme for the original signals with minimum information loss. We present several quantitative conditions for optimal CFA design, and propose an efficient computational procedure to search for the best CFAs that satisfy these conditions. Numerical experiments show that the optimal CFA patterns designed from the proposed procedure can effectively retain the information of the original full-color images. In particular, with the designed CFA patterns, high quality demosaicking can be achieved by using simple and efficient linear filtering operations in the polyphase domain. The visual qualities of the reconstructed images are competitive to those obtained by the state-of-the-art adaptive demosaicking algorithms based on the Bayer pattern.

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.

Aliasing in images is often considered as a nuisance. Artificial low frequency patterns and jagged edges appear when an image is sampled at a too low frequency. However, aliasing also conveys useful information about the high frequency content of the image, which is exploited in super-resolution applications. We use a set of input images of the same scene to extract such high frequency information and create a higher resolution aliasing-free image. Typically, there is a small shift or more complex motion between the different images, such that they contain slightly different information about the scene. Super-resolution image reconstruction can be formulated as a multichannel sampling problem with unknown offsets. This results in a set of equations that are linear in the unknown signal coefficients but nonlinear in the offsets. This thesis concentrates on the computation of these offsets, as they are an essential prerequisite for an accurate high resolution reconstruction. If a part of the image spectra is free of aliasing, the planar shift and rotation parameters can be computed using only this low frequency information. In such a case, the images can be registered pairwise to a reference image. Such a method is not applicable if the images are undersampled by a factor of two or larger. A higher number of images needs to be registered jointly. Two subspace methods are discussed for such highly aliased images. The first approach is based on a Fourier description of the aliased signals as a sum of overlapping parts of the spectrum. It uses a rank condition to find the correct offsets. The second one uses a more general expansion in an arbitrary Hilbert space to compute the signal offsets. The sampled signal is represented as a linear combination of sampled basis functions. The offsets are computed by projecting the signal onto varying subspaces. Under certain conditions, in particular for bandlimited signals, the nonlinear super-resolution equations can be written as a set of polynomial equations. Using Buchberger's algorithm, the solution can then be computed as a Gröbner basis for the corresponding polynomial ideal. After a description of a standard algorithm, adaptations are made for the use with noisy measurements. The techniques presented in this thesis are tested in simulations and practical experiments. The experiments are performed on sets of real images taken with a digital camera. The results show the validity of the algorithms: registration parameters are computed with subpixel precision, and aliasing is accurately removed from the resulting high resolution image. This thesis is produced according to the concepts of reproducible research. All the results and examples used in this thesis are reproducible using the code and data available online.

Sampling has always been at the heart of signal processing providing a bridge between the analogue world and discrete representations of it, as our ability to process data in continuous space is quite limited. Furthermore, sampling plays a key part in understanding how to efficiently capture, store and process signals. Shannon's sampling theorem states that if the original signal is known to have a limited bandwidth, we can retrieve the signal from uniformly-spaced samples, provided that the sampling rate is greater than twice the highest frequency in the signal. Here, we see two key attributes: prior knowledge on the original signal (limited bandwidth) and a constrained sampling setup (uniform samples at a particular rate). In this thesis, we make weaker assumptions on the sampling setup by assuming that some information, such as the sample positions, is lost. We show that under proper prior knowledge, we can reconstruct the signal from its samples uniquely or up to some equivalence class. We start by the problem of linear sampling of discrete signals, where the sample values are known, but their order is lost. In general, the original signal is impossible to retrieve from the samples, but we show that by taking out symmetry from the sampling vectors, we can reconstruct the signal uniquely. We provide an efficient algorithm to find the sample orders and thus reconstruct the original signal. We also study the problem of reconstructing a continuous signal from samples taken at unknown locations. The lost sample locations take away any hope of uniquely retrieving the signal without prior knowledge. We show that this problem is equivalent to reconstructing a composite of functions from uniformly spaced samples. Then we provide an efficient algorithm that can recover bandlimited signals warped by a linear function uniquely given enough sampling frequency. We then investigate a problem, dubbed shape from bandwidth, where we have uniform samples from a picture (projection) of an unknown surface that is painted with an unknown texture. The goal is to reconstruct the shape of the surface from these samples. We show that having prior knowledge of the texture bandwidth provides us with enough information to reconstruct the surface from its picture. We provide reconstruction algorithms for both orthogonal and central projections and provide equivalence classes of solutions in each case. Next, in two consecutive chapters, using techniques from geometrical signal processing, we offer new designs for 3-D barcodes, whose information can be retrieved from a single projection using penetrating waves from an unknown direction. Because of the unknown scan direction, the correct correspondence of the samples to the information bits in the barcodes is lost. In this case, we use the known shape of the barcode as prior knowledge to estimate the unknown scan direction from the samples, and then transform the reconstruction as a linear problem that can be solved efficiently. Finally, we cover the theory of coordinate difference matrices (CDMs): matrices that store mutual differences between coordinates of points (sensors, microphones, molecules, etc.) in space. We show how we can leverage specific properties of these matrices, such as their low rank, as prior knowledge in order to reconstruct the position of the points in space using CDMs. We use our reconstruction algorithm to solve many real-life signal processing problems.

Mobile health is gradually taking more importance in our society and the need of new power efficient devices acquiring biosignals for long periods of time is becoming substantial. In this thesis, we study the power reduction we could achieve on ECG sensing devices. Emphasis is made on reducing the number of samples both during the sensing phase and the compression phase. To that end, a new scheme called variable pulse width finite rate of innovation (VPW-FRI) is investigated. This new technique relies on the classical finite rate of innovation (FRI) theory and enables the use of a sum of asymmetric Cauchy-based pulses to model ECG signals. Research is done in order to implement VPW in practice and its performance are carefully analysed. Among others, we consider the potential instability of the method, we study its compression effectiveness and compare it with compression schemes widespread in the literature. We also evaluate the spectrum extrapolation performance of VPW when fed with signals sampled at sub-Nyquist rates and propose a modification that improves it. Furthermore, we introduce a method based on the similarities between different heart beats that reduces the computational costs of VPW. The parametric nature of VPW finally allows us to use it as a noise reduction algorithm. In parallel, we review and test a non-uniform sensing technique that adapts the sampling rate to the slope of the signal.

Estimating intensity fields of stochastic phenomenons is of crucial interest in many scientific applications. Typical experimental setups involve an acquisition system, that subsequently filters and samples the probed intensity field. This equivalently defines a sampling operator, fully specified by the characteristics of the measuring device. Reconstruction of the intensity field can then be achieved by performing an interpolation step on the collected samples, with an interpolation operator ideally matched with the sampling operator. Sampling followed by interpolation can be shown to act as an orthogonal projection onto the unknown intensity field. For this reason, the reconstructed intensity field can in general differ quite substantially from the actual one, polluted by aliasing artifacts that complicate and often forbid the identification of features within it. Nonlinear algorithms such as CLEAN (acclamated in radio astronomy) have been proposed to recover the actual features from the aliased intensity field, but their convergence properties have not yet been fully assessed. In this work, we propose a novel method to locate sources within the recovered intensity field and attribute aliasing artifacts to their parent source, in the specific case of point source intensity fields. Rather than directly estimating the intensity field, we first reconstruct the underlying random field it characterises. We then estimate the second moment of this reconstructed random field, including its covariance function. We use the covariance function as a measure of resemblance of different parts of the intensity field. The problem is then formulated as a clustering problem on a graph: the intensity field is sampled on a fine grid, each grid point is interpreted as a node on a graph, and edges between nodes are weighted proportionally to their covariance. We then use spectral clustering to separate the artifacts in groups, and identify the actual sources in the field as the nodes with maximum intensity within each cluster. We conclude with an application of our method to the field of radio astronomy.

In this thesis, timing is everything. In the first part, we mean this literally, as we tackle systems that encode information using timing alone. In the second part, we adopt the standard, metaphoric interpretation of this saying and show the importance of choosing the right time to sample a system, when efficiency is a key consideration. Time encoding machines, or, alternately, integrate-and-fire neurons, encode their inputs using spikes, the timings of which depend on the input and therefore hold information about it. These devices can be made more power efficient than their clocked counterparts and have thus been studied in the fields of signal processing, event-based vision, computational neuroscience and machine learning. However, their timing-based spiking output has so far often been considered a nuisance that one must make do with, rather than a potential advantage. In this thesis, we show that this timing-based output equips spiking devices with capabilities that are out of reach for classical encoding and processing systems. We first discover the benefits of time encoding on multi-channel encoding and recovery of a signal: with time encoding, clock alignment is easy to solve, although it poses problems in the classical sampling scenario. Then, we study the time encoding of low-dimensional signals and see that the asynchrony of spikes allows for a lower sample complexity in comparison with synchronous sampling. Thanks to this same asynchrony, time encoding of video results in an entanglement between spatial sampling density and temporal resolution---a relationship which is not present in frame-based video. Finally, we show that the all-or-none nature of the spikes allows training spiking neural networks in a layer-by-layer fashion---a feat that is impossible with clocked, artificial neural networks, due to the credit assignment problem. The second part of this thesis shows that choosing the right timing of samples can be crucial to ensure efficiency when performing nanoscale magnetic sensing. We are given a stochastic process, where each sample at time t follows a Bernoulli distribution, and which is characterized by oscillation frequencies that we are interested in recovering. We search for an optimal approach to sample this process, such that the variance of the frequencies' estimates is minimized, given constraints on the measurement time. The models we assume stem from the field of nanoscale magnetic sensing, where the number of parameters to be estimated varies with the number of spins one is trying to sense. We present an adaptive approach to choosing samples in both the single-spin and two-spin cases and compare the adaptive algorithm's performance to classical approaches to sampling. In both parts of the thesis, we move away from classical amplitude sampling and consider cases where timing takes the forefront and amplitude information is merely binary, to shows that timing can carry information and that it can control the amount of information gain.

Shannon's sampling theorem for bandlimited signals, formulated in 1949, has become a cornerstone for modern digital communications and signal processing. The importance of sampling and reconstruction of analog signals has led to great advances in the field, such as sampling of nonbandlimited signals, compressed sensing, or unlabeled sensing, which go far beyond the uniform sampling of bandlimited signals. In this thesis, we address the problem of reconstructing multi-input signals from shuffled samples; a problem which has not yet been covered by the scientific literature. This sampling setup can occur in various real-world applications that include, but are not limited to, whole-brain calcium imaging and general fluorescence microscopy of moving cell cultures as well as radar entomology. We first study the case of two shuffled signals with finite rate of innovation, focusing on streams of decaying exponentials, and derive necessary conditions for unique reconstruction by drawing a link between the studied problem and previous work on signals with finite rate of innovation and linear regression without correspondences. Building on this derivation we propose a two-step estimation approach for unshuffling and reconstructing the signals of interest: Step 1 deals with the recovery of the signal parameters of the sum of the input signals. These parameters are fed to Step 2, which focuses on solving a structured unlabeled sensing problem. We devise a heuristic relying on concepts from robust estimation theory to iteratively estimate the signal parameters of the individual signals and reduce the number of shuffled samples. We provide a comprehensive evaluation of the proposed method in numerical experiments, where the influence of additive noise, the number of shuffled samples, the exponential decay, and the propagated errors from Step 1 to Step 2 are analyzed. In addition, we investigate a possible gain from reestimating the signal parameters from the estimated individual channels and present exemplary results on artificially shuffled calcium imaging traces. Furthermore, in a benchmark against an expectation maximization method for unlabeled sensing, we observe the proposed method's average signal reconstruction error to be multiple orders of magnitude smaller. The results illustrate the satisfactory performance of the proposed method, which to date is the first method developed to deal with the considered sampling setup.