Blind as a bat: spatial perception without sight

Among our five senses, we rely mostly on audition and vision to perceive an environment. Our ears are able to detect stimuli from all directions, especially from obstructed and far-away objects. Even in smoke, harsh weather conditions, or at night â situations where our eyes struggle to operate â they are an essential source of information. On the other hand, our eyes add rich and instantaneous information to the auditory signals. These two senses are thus complementary; taken together, they constitute a powerful system for localization and navigation. In this thesis, non-visual ("blind") modalities are studied to solve spatial perception problems, particularly those involving localization and mapping in robotics. Although the potential of blind modalities has long been recognized for niche applications, including sonar for underwater navigation and radio-frequency signals for indoor localization, less progress has been made on blind methods than visual methods, and many interesting problems remain unsolved. In the application-oriented Part I of the thesis, an indoor localization solution based on WiFi and Bluetooth measurements is proposed that, unlike competing approaches, does not require offline calibration. Next, the localization of a moving device is analyzed, based on single, sequential distance measurements, which constitutes a fundamental but unsolved variation of trilateration. This problem is solved using a closed-form algorithm that includes recovery guarantees. Finally, a drone is equipped with microphones and a buzzer, thus emulating a bat â an expert of blind navigation. Algorithms are presented to detect walls using echoes as well as external sound sources. Throughout these chapters, the optimal exploitation of a device's motion, which is commonly ignored in sensing algorithms, is studied for improving spatial perception.Although blind modalities carry less information than images, they can be used to extract fundamental features, such as distances or angles between objects of interest. In Part II, we therefore treat the fundamental question of localization from distance and angle measurements. When performing localization from distance measurements, one can resort to distance geometry, a mature field with well-established results and methods. Many fewer results exist for angle measurements. Thus, novel localization algorithms are proposed to bridge this gap, using different angle measurements to supplement or replace distances. These algorithms are useful beyond localization, as they contribute to the much broader field of low-dimensional embedding of entities, such as images, words, or abstract concepts. Overall, novel algorithms, systems, and theories are proposed for spatial perception from a variety of non-visual signals. Along the way, a wide range of important problems from localization is approached from a signal-processing perspective. This enables the formulation of optimal and guaranteed algorithms in some cases, and efficient approximate solutions otherwise. Guaranteeing optimality has recently emerged as a pressing problem for achieving robust real-world operation in robotics; this thesis contributes to this ambitious goal.

Euclidean Distance Matrices

Reza Parhizkar

Euclidean distance matrices (EDMs) are central players in many diverse fields including psychometrics, NMR spectroscopy, machine learning and sensor networks. However, they are not often exploited in signal processing. In this thesis, we analyze attributes of EDMs and derive new key properties of them. These analyses allow us to propose algorithms to approximate EDMs and provide analytic bounds on the performance of our methods. We use these techniques to suggest new solutions for several practical problems in signal processing. Together with these properties, algorithms and applications, EDMs can thus be considered as a fundamental toolbox to be used in signal processing. In more detail, we start by introducing the structure and properties of EDMs. In particular, we focus on their rank property; the rank of an EDM is at most the dimension of the set of points generating it plus 2. Using this property, we introduce the use of low rank matrix completion methods for approximating and completing noisy and partially revealed EDMs. We apply this algorithm to the problem of sensor position calibration in ultrasound tomography devices. By adapting the matrix completion framework, in addition to proposing a self calibration process for these devices, we also provide analytic bounds for the calibration error. We then study the problem of sensor localization using distance information by minimizing a non-linear cost function known as the s-stress function in the multidimensional scaling (MDS) community. We derive key properties of this cost function that can be used to reduce the search domain for finding its global minimum. We provide an efficient, low cost and distributed algorithm for minimizing this cost function for incomplete networks and noisy measurements. In randomized experiments, the proposed method converges to the global minimum of the s-stress in more than 99% of the cases. We also address the open problem of existence of non-global minimizers of the s-stress and reduce this problem to a hypothesis. If the hypothesis is true then the cost function has only global minimizers, otherwise, it has non-global minimizers. Using the rank property of EDMs and the proposed minimization algorithm for approximating them, we address an interesting and practical problem in acoustics. We show that using five microphones and one loudspeaker, we can hear the shape of a room. We reformulate this problem as finding the locations of the image sources of the loudspeaker with respect to the walls. We propose an algorithm to find these positions only using first-order echoes. We prove that the reconstruction of the room is almost surely unique. We further introduce a new algorithm for locating a microphone inside a known room using only one loudspeaker. Our experimental evaluations conducted on the EPFL campus and also in the Lausanne cathedral, confirm the robustness and accuracy of the proposed methods. By integrating further properties of EDMs into the matrix completion framework, we propose a new method for calibrating microphone arrays in a diffuse noise field. We use a specific characterization of diffuse noise fields to relate the coherence of recorded signals by two microphones to their mutual distance. As this model is not reliable for large distances between microphones, we use matrix completion coupled with other properties of EDMs to estimate these distances and calibrate the microphone array. Evaluation of our algorithm using real data measurements demonstrates, for the first time, the possibility of accurately calibrating large ad-hoc microphone arrays in a diffuse noise field. The last part of the thesis addresses a central problem in signal processing; the design of discrete-time filters (equivalently window functions) that are compact both in time and frequency. By properly adapting the definitions of compactness in the continuous time to discrete time, we formulate the search for maximally compact sequences as solving a semi-definite program. We show that the spectra of maximally compact sequences are a special class of Mathieu’s cosine functions. Using the asymptotic behavior of these functions, we provide a tight bound for the time-frequency spread of discrete-time sequences. Our analysis shows that the Heisenberg uncertainty bound on the time-frequency spread of sequences is not tight and the lower bound depends on the frequency spread, unlike in the continuous time case.

EPFL2013

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 GHz separated in a 9-cores architecture. This exponential evolution following the famous "Moore's Law" is possible thanks to the innovations made in every domain implied in a chip conception and allows chipset creation targeting a more and more wide range of applications. This variety of processors implies a great number of variations in the hardware choices, to match application (general purpose processor, digital signal processor, application-specific processor…), performance requirements and / or other operative constraints such as power consumptions. The applications running on these powerful solutions are growing in complexity exponentially as well, relying on more and more sophisticated software. Consequently the design team is facing a real challenge when designing and implementing an optimal architectural solution. To ease their task, the trend in computer aided design is to develop integrated frameworks for simulation and design, providing all the tools needed during the process, in a top-down approach. These tools allow system specification by means of abstract concurrent entities down to final implementation by means of successive refinements of the different entities and of the communication among then. In parallel, these hardware solutions run applications of a constantly increasing complexity, leading to the need for more and more intensive specification and validation tasks, by means of abstract software descriptions, typically referred to as verification models. These models implement all the functionalities of the application and thus, from the end of this specification phase, the abstract description of the application in the verification model becomes the most reliable reference for the corresponding application. All these reasons make the intuitive understanding of the processing complexity and tend to create redesign loops in the conception process when realizing that the initial architecture choices were sub-optimal (or even wrong), preventing the system to meet the desired performance constraints. In this case, a costly re-design iteration is mandatory, targeting a new platform choice but introducing delay and cost in the design causing the project to arrive too late on the market. Obviously, to eliminate these re-design iterations and to be able to help as soon as possible, the preliminary complexity analysis should be performed before starting the design of the target architecture. Since the first step of the design cycle implies an algorithm description through a verification model, it is desirable to perform the complexity study on this model. Indeed, though considerable efforts are carried out on developing powerful co-design tools, by means high-level abstract descriptions, fast prototyping and flexible design-reusability; no automatic tool is available to help the designer in the first analysis and comprehension phase. Moreover, the size of verification models is growing together with the complexity of the applications, and it is not surprising to have to deal with verification models of tens of thousands of source code lines; consequently, paper-and-pencil and manual-instrumentation analysis methods are neither feasible nor reliable any longer. Furthermore, static complexity evaluations, not taking into account the dynamic dependency of the complexity from the input data, are becoming less and less meaningful for the development of cost-effective solutions. Worst-case analysis is typically suitable for real-time control applications but it cannot be applied in all the cases in which quality-of-service/cost trade-offs are of concern; for instance, a multimedia or signal-processing architecture developed to support the worst-case scenario would simply result to be too expensive and under-exploited for most of the processing time. This dissertation presents a new approach to algorithmic complexity analysis, called the Software Instrumentation Tool (SIT), based on the previous observations and aiming at filling the gap in state of the art tools. The main goal of the SIT is to provide a high-level analysis framework for both a faithful design-oriented evaluation of the computational complexity of verification models and a hardware simulation of the projected architecture. The breakthrough in this version of the SIT is to provide a full set of results about complexity in a complete framework, allowing to use all these data in a methodology able to fill the gap from verification model to hardware implementation or algorithm porting. The analysis is performed at the highest possible abstraction level, i.e. at source code language level, in order to adhere to the same degree of abstraction of verification models; that is, the analysis is not biased by the underlying architecture over which the verification model is tested or by the compilation process. The analysis strictly depends on the input data, in order to take into account the real algorithmic complexity in real working conditions and relies on a completely automatic process, performed directly on the source code of verification models, without forcing the designer to make any manual modification such as source code rewriting or manual instrumentation. SIT approach to complexity analysis is based on the instrumentation by means of C++ operator overloading. SIT analyzes C source code and is capable to instrument, automatically, any legal C data-type or operation or statement, providing eventually an exhaustive complexity analysis at C language level. The tool is building on a core system (a core for the base algorithmic complexity, a second for memory analysis) and supports module extensions (a module for critical path evaluation, a module for data transfer, both can be plugged in the memory core). All the cores and modules are reporting their results in a single visual interface, allowing a quick and efficient complexity overview as well as an in-depth result exploration. As SIT allows extracting meaningful complexity measures directly from the verification models in the preliminary analysis and comprehension phase, the designer benefits from a tool-assisted approach allowing to step to the latest design phases through intermediate tools. The results provided by the first version of the SIT are computational data (what types of operation are performed? On which type of data? ...) and memory usage analysis (how many memory accesses? In which function?). This build of the SIT includes a customizable memory usage analysis, made possible by the simulation of (customizable) virtual memory architectures; this allows to focus the analysis on other aspects of the algorithmic complexity which could not otherwise be estimated by means of static analysis methods, or software profilers, or instruction-level profilers. Another novelty in the SIT is the data-transfer module, allowing both a quick and efficient overview of the main data flows inside the virtual architecture (thanks to a graphical representation of the mains transfers) and a precise in depth analysis of bandwidth and data transfers between functions (thanks to the detailed view included in Sitview). The latest result is the critical path evaluation analysis, allowing to detect the major functions of the execution tree and to extract information about parallelism at different level, from function to algorithm level. All these information are provided through the SIT graphical interface SitView, and a methodology is described to step from the high-level verification model in C to an actor language partioning based on the tool analysis. This partition can be used with dedicated actor languages to create a FPGA code or to create an optimized hardware solution, most probably better than an instinctively created hardware.

EPFL2007

Transformation-Invariant Analysis of Visual Signals with Parametric Models

Elif Vural

The analysis of collections of visual data, e.g., their classification, modeling and clustering, has become a problem of high importance in a variety of applications. Meanwhile, image data captured in uncontrolled environments by arbitrary users is very likely to be exposed to geometric transformations. Therefore, efficient methods are needed for analyzing high-dimensional visual data sets that can cope with geometric transformations of the visual content of interest. In this thesis, we study parametric models for transformation-invariant analysis of geometrically transformed image data, which provide low-dimensional image representations that capture relevant information efficiently. We focus on transformation manifolds, which are image sets created by parametrizable geometric transformations of a reference image model. Transformation manifolds provide a geometric interpretation of several image analysis problems. In particular, image registration corresponds to the computation of the projection of the target image onto the transformation manifold of the reference image. Similarly, in classification, the class label of a query image can be estimated in a transformation-invariant way by comparing its distance to transformation manifolds that represent different image classes. In this thesis, we explore several problems related to the registration, modeling, and classification of images with transformation manifolds. First, we address the problem of sampling transformation manifolds of known parameterization, where we focus on the target applications of image registration and classification in the sampling. We first propose an iterative algorithm for sampling a manifold such that the selected set of samples gives an accurate estimate of the distance of a query image to the manifold. We then extend this method to a classification setting with several transformation manifolds representing different image classes. We develop an algorithm to jointly sample multiple transformation manifolds such that the class label of query images can be estimated accurately by comparing their distances to the class-representative manifold samples. The proposed methods outperform baseline sampling schemes in image registration and classification. Next, we study the problem of learning transformation manifolds that are good models of a given set of geometrically transformed image data. We first learn a representative pattern whose transformation manifold fits well the input images and then generalize the problem to a supervised classification setting, where we jointly learn multiple class-representative pattern transformation manifolds from training images with known class labels. The proposed manifold learning methods exploit the information of the type of the geometric transformation in the data to compute an accurate data model, which is ignored in previous manifold learning algorithms. Finally, we focus on the usage of transformation manifolds in multiscale image registration. We consider two different methods in image registration, namely, the tangent distance method and the minimization of the image intensity difference with gradient descent. We present a multiscale performance analysis of these methods. We derive upper bounds for the alignment errors yielded by the two methods and analyze the variations of these bounds with noise and low-pass filtering, which is useful for gaining an understanding of the performance of these methods in image registration. To the best of our knowledge, these are the first such studies in multiscale registration settings. Geometrically transformed image sets have a particular structure, and classical image analysis methods do not always suit well for the treatment of such data. This thesis is motivated by this observation and proposes new techniques and insights for handling geometric transformations in image analysis and processing.

EPFL2013

Transformation-Invariant Analysis of Visual Signals with Parametric Models

Elif Vural

EPFL2013

A profiling framework for high level design space exploration for memory and system architectures

EPFL2007

Euclidean Distance Matrices

Reza Parhizkar

EPFL2013