Uncertain Sampling with Certain Priors

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.

Shapes from Pixels

Mitra Fatemi

In today's digital world, sampling is at the heart of any signal acquisition device. Imaging devices are ubiquitous examples that capture two-dimensional visual signals and store them as the pixels of discrete images. The main concern is whether and how the pixels provide an exact or at least a fair representation of the original visual signal in the continuous domain. This motivates the design of exact reconstruction or approximation techniques for a target class of images. Such techniques benefit different imaging tasks such as super-resolution, deblurring and compression. This thesis focuses on the reconstruction of visual signals representing a shape over a background, from their samples. Shape images have only two intensity values. However, the filtering effect caused by the sampling kernel of imaging devices smooths out the sharp transitions in the image and results in samples with varied intensity levels. To trace back the shape boundaries, we need strategies to reconstruct the original bilevel image. But, abrupt intensity changes along the shape boundaries as well as diverse shape geometries make reconstruction of this class of signals very challenging. Curvelets and contourlets have been proved as efficient multiresolution representations for the class of shape images. This motivates the approximation of shape images in the aforementioned domains. In the first part of this thesis, we study generalized sampling and infinite-dimensional compressed sensing to approximate a signal in a domain that is known to provide a sparse or efficient representation for the signal, given its samples in a different domain. We show that the generalized sampling, due to its linearity, is incapable of generating good approximation of shape images from a limited number of samples. The infinite-dimensional compressed sensing is a more promising approach. However, the concept of random sampling in this scheme does not apply to the shape reconstruction problem. Next, we propose a sampling scheme for shape images with finite rate of innovation (FRI). More specifically, we model the shape boundaries as a subset of an algebraic curve with an implicit bivariate polynomial. We show that the image parameters are solutions of a set of linear equations with the coefficients being the image moments. We then replace conventional moments with more stable generalized moments that are adjusted to the given sampling kernel. This leads to successful reconstruction of shapes with moderate complexities from samples generated with realistic sampling kernels and in the presence of moderate noise levels. Our next contribution is a scheme for recovering shapes with smooth boundaries from a set of samples. The reconstructed image is constrained to regenerate the same samples (consistency) as well as forming a bilevel image. We initially formulate the problem by minimizing the shape perimeter over the set of consistent shapes. Next, we relax the non-convex shape constraint to transform the problem into minimizing the total variation over consistent non-negative-valued images. We introduce a requirement -called reducibility- that guarantees equivalence between the two problems. We illustrate that the reducibility effectively sets a requirement on the minimum sampling density. Finally, we study a relevant problem in the Boolean algebra: the Boolean compressed sensing. The problem is about recovering a sparse Boolean vector from a few collective binary tests. We study a formulation of this problem as a binary linear program, which is NP hard. To overcome the computational burden, we can relax the binary constraint on the variables and apply a rounding to the solution. We replace the rounding procedure with a randomized algorithm. We show that the proposed algorithm considerably improves the success rate with only a slight increase in the computational cost.

EPFL2016

Signal Processing in Space and Time

Francisco Pereira Correia Pinto

Sound waves propagate through space and time by transference of energy between the particles in the medium, which vibrate according to the oscillation patterns of the waves. These vibrations can be captured by a microphone and translated into a digital signal, representing the amplitude of the sound pressure as a function of time. The signal obtained by the microphone characterizes the time-domain behavior of the acoustic wave field, but has no information related to the spatial domain. The spatial information can be obtained by measuring the vibrations with an array of microphones distributed at multiple locations in space. This allows the amplitude of the sound pressure to be represented not only as a function of time but also as a function of space. The use of microphone arrays creates a new class of signals that is somewhat unfamiliar to Fourier analysis. Current paradigms try to circumvent the problem by treating the microphone signals as multiple "cooperating" signals, and applying the Fourier analysis to each signal individually. Conceptually, however, this is not faithful to the mathematics of the wave equation, which expresses the acoustic wave field as a single function of space and time, and not as multiple functions of time. The goal of this thesis is to provide a formulation of Fourier theory that treats the wave field as a single function of space and time, and allows it to be processed as a multidimensional signal using the theory of digital signal processing (DSP). We base this on a physical principle known as the Huygens principle, which essentially says that the wave field can be sampled at the surface of a given region in space and subsequently reconstructed in the same region, using only the samples obtained at the surface. To translate this into DSP language, we show that the Huygens principle can be expressed as a linear system that is both space- and time-invariant, and can be formulated as a convolution operation. If the input signal is transformed into the spatio-temporal Fourier domain, the system can also be analyzed according to its frequency response. In the first half of the thesis, we derive theoretical results that express the 4-D Fourier transform of the wave field as a function of the parameters of the scene, such as the number of sources and their locations, the source signals, and the geometry of the microphone array. We also show that the wave field can be effectively analyzed on a small scale using what we call the space/time-frequency representation space, consisting of a Gabor representation across the spatio-temporal manifold defined by the microphone array. These results are obtained by treating the signals as continuous functions of space and time. The second half of the thesis is dedicated to processing the wave field in discrete space and time, using Nyquist sampling theory and multidimensional filter banks theory. In particular, we show examples of orthogonal filter banks that effectively represent the wave field in terms of its elementary components while satisfying the requirements of critical sampling and perfect reconstruction of the input. We discuss the architecture of such filter banks, and demonstrate their applicability in the context of real applications, such as spatial filtering and wave field coding.

EPFL2010

Resolving Ambiguities in Monocular 3D Reconstruction of Deformable Surfaces

Aydin Varol

In this thesis, we focus on the problem of recovering 3D shapes of deformable surfaces from a single camera. This problem is known to be ill-posed as for a given 2D input image there exist many 3D shapes that give visually identical projections. We present three methods which make headway towards resolving these ambiguities. We believe that our work represents a significant step towards making surface reconstruction methods of practical use. First, we propose a surface reconstruction method that overcomes the limitations of the state-of-the-art template-based and non-rigid structure from motion methods. We neither track points over many frames, nor require a sophisticated deformation model, or depend on a reference image. In our method, we establish correspondences between pairs of frames in which the shape is different and unknown. We then estimate homographies between corresponding local planar patches in both images. These yield approximate 3D reconstructions of points within each patch up to a scale factor. Since we consider overlapping patches, we can enforce them to be consistent over the whole surface. Finally, a local deformation model is used to fit a triangulated mesh to the 3D point cloud, which makes the reconstruction robust to both noise and outliers in the image data. Second, we propose a novel approach to recovering the 3D shape of a deformable surface from a monocular input by taking advantage of shading information in more generic contexts than conventional Shape-from-Shading (SfS) methods. This includes surfaces that may be fully or partially textured and lit by arbitrarily many light sources. To this end, given a lighting model, we learn the relationship between a shading pattern and the corresponding local surface shape. At run time, we first use this knowledge to recover the shape of surface patches and then enforce spatial consistency between the patches to produce a global 3D shape. Instead of treating texture as noise as in many SfS approaches, we exploit it as an additional source of information. We validate our approach quantitatively and qualitatively using both synthetic and real data. Third, we introduce a constrained latent variable model that inherently accounts for geometric constraints such as inextensibility defined on the mesh model. To this end, we learn a non-linear mapping from the latent space to the output space, which corresponds to vertex positions of a mesh model, such that the generated outputs comply with equality and inequality constraints expressed in terms of the problem variables. Since its output is encouraged to satisfy such constraints inherently, using our model removes the need for computationally expensive methods that enforce these constraints at run time. In addition, our approach is completely generic and could be used in many other different contexts as well, such as image classification to impose separation of the classes, and articulated tracking to constrain the space of possible poses.

EPFL2012