Faculté des sciences et techniques de l'ingénieur STI, Section de génie électrique et électronique, Institut de traitement des signaux ITS (Laboratoire de traitement des signaux 2 LTS2)

Nonlinear approximation with redundant multi-component dictionaries

Granai, Lorenzo ; Vandergheynst, Pierre (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3404.

Ajouter à la liste personnelle
    Summary
    The problem of efficiently representing and approximating digital data is an open challenge and it is of paramount importance for many applications. This dissertation focuses on the approximation of natural signals as an organized combination of mutually connected elements, preserving and at the same time benefiting from their inherent structure. This is done by decomposing a signal onto a multi-component, redundant collection of functions (dictionary), built by the union of several subdictionaries, each of which is designed to capture a specific behavior of the signal. In this way, instead of representing signals as a superposition of sinusoids or wavelets many alternatives are available. In addition, since dictionaries we are interested in are overcomplete, the decomposition is non-unique. This gives us the possibility of adaptation, choosing among many possible representations the one which best fits our purposes. On the other hand, it also requires more complex approximation techniques whose theoretical decomposition capacity and computational load have to be carefully studied. In general, we aim at representing a signal with few and meaningful components. If we are able to represent a piece of information by using only few elements, it means that such elements can capture its main characteristics, allowing to compact the energy carried by a signal into the smallest number of terms. In such a framework, this work also proposes analysis methods which deal with the goal of considering the a priori information available when decomposing a structured signal. Indeed, a natural signal is not only an array of numbers, but an expression of a physical event about which we usually have a deep knowledge. Therefore, we claim that it is worth exploiting its structure, since it can be advantageous not only in helping the analysis process, but also in making the representation of such information more accessible and meaningful. The study of an adaptive image representation inspired and gave birth to this work. We often refer to images and visual information throughout the course of the dissertation. However, the proposed approximation setting extends to many different kinds of structured data and examples are given involving videos and electrocardiogram signals. An important part of this work is constituted by practical applications: first of all we provide very interesting results for image and video compression. Then, we also face the problem of signal denoising and, finally, promising achievements in the field of source separation are presented.
    Riassunto
    Riassunto Il problema della rappresentazione ed approssimazione efficiente dell'informazione digitale é una sfida aperta e ricopre una fondamentale importanza per molte applicazioni. Questa tesi si concentra sull'approssimazione di segnali naturali in quanto combinazione organizzata di elementi mutuamente connessi; approssimazione che preserva e allo stesso tempo beneficia della struttura inerente ai segnali. Ció é ottenuto decomponendo un segnale su un insieme ridondante di funzioni composto da piú componenti (detto anche dizionario), creato dall'unione di diversi sotto-dizionari, ognuno dei quali e' progettato per catturare uno specifico comportamento del segnale. In questo modo, ci sono molte alternative alla rappresentazione dei segnali come superposizione di sinusoidi o wavelet. Inoltre, visto che i dizionari che ci interessano sono overcompleti la decomposizione non é unica. Questo ci fornisce la possibilitá di adattamento, scegliendo tra le molteplici possibili rappresentazioni quella che meglio si adegua ai mostri scopi. D'altra parte ció richiede anche tecniche di approssimazione piú complesse le cui capacita' di decomposizione e il cui costo computazionale devono essere studiati attentamente. In generale, vogliamo rappresentare un segnale con pochi e significativi componenti. Se siamo in grado di rappresentare dell'informazione usando solo pochi elementi, vuol dire che tali elementi possono catturare le sue caratteristiche principali, permettendo di compattare l'energia del segnale nel minimo numero di termini. In questo ambito, questo lavoro propone anche metodi di analisi che mirano a considerare l'informazione a priori che e' disponibile quando un segnale strutturato viene decomposto. Infatti, un segnale naturale non e' solo una serie di numeri, bensí un'espressione di un evento fisico di cui in generale abbiamo una profonda conoscenza. Quindi sosteniamo che sfruttare la sua struttura sia vantaggioso, non solo in quanto puó aiutare il processo di decomposizione, ma anche per rendere la rappresentazione piu' accessibile e significativa. Questo lavoro é stato ispirato dallo studio di una rappresentazione adattativa delle immagini. Nel corso di questa tesi, quindi, facciamo spesso riferimento alle immagini e all'informazione visiva. Comunque lo scenario di approssimazione qui proposto si estende a molti differenti tipi di dati strutturati e vengono forniti degli esempi che coinvolgono video e segnali cardiaci. Una parte importante di questo lavoro e' costituita da applicazioni pratiche: in primo luogo sono forniti risultati molto interessanti per quanto riguarda la compressione di immagini e video. Quindi viene anche affrontato il problema dell'eliminazione del rumore e, in fine, vengono presentati risultati promettenti nell'ambito della separazione di sorgenti.
    Résumé
    Le problème de la représentation et de l'approximation efficace de données numériques est un défi ouvert, d'une importance capitale pour de nombreuses applications. Cette thèse se concentre sur l'approximation de signaux naturels en tant que combinaison organisée d'éléments connectés, en préservant leur structure inhérente tout en en tirant parti. Ceci est accompli en décomposant un signal en une collection de fonctions (dictionnaire) redondante et possédant plusieurs composants, qui est construite par l'union de plusieurs sous-dictionnaires, chacun étant conçu pour capturer un comportement spécifique du signal. Ainsi, plutôt que de représenter des signaux comme une superposition de sinusoïdes ou d'ondelettes, nous avons plusieurs alternatives. De plus, puisque les dictionnaires qui nous intéressent sont surcomplets, la décomposition n'est pas unique. Ceci nous offre des possibilités d'adaptation, puisque nous pouvons choisir parmi les multiples représentations possibles celle qui correspond le mieux à nos buts, mais demande aussi des techniques d'approximations plus complexes dont la capacité de décomposition théorique et la complexité doivent être étudiées avec soin. De façon générale, nous visons à représenter un signal avec peu de composants significatifs. Si nous pouvons représenter une information en utilisant seulement quelques éléments, cela signifie que de tels éléments peuvent en capturer les caractéristiques principales, ce qui permet de comprimer l'énergie transportée par un signal en un minimum de termes. Ce travail propose aussi des méthodes d'analyse qui permettent de considérer l'information a priori disponible lorsqu'un signal structuré est décomposé. En effet, un signal naturel n'est pas seulement un tableau de nombres, mais l'expression d'un événement physique dont nous avons généralement une connaissance profonde. C'est pourquoi nous maintenons qu'il est avantageux d'exploiter les relations mutuelles entre éléments constituants, car ceci peut aider non seulement le processus d'analyse mais encore à rendre la représentation d'une telle information plus accessible et significative. L'étude d'une représentation d'image adaptive a été l'inspiration de ce travail et lui a donné naissance, c'est pourquoi nous nous référons souvent à des images et à de l'information visuelle au long de cette thèse. Cependant, ce système d'approximation s'étend à de nombreuses sortes de données structurées, et nous donnons des exemples implicant des signaux vidéo et des électrocardiogrammes. Une partie importante de ce travail est constituée d'applications pratiques: premièrement nous fournissons des résultats très intéressants pour la compression d'image et de vidéo. Puis, nous affrontons le problème du débruitage de signal, et finalement nous présentons des résultats prometteurs dans le domaine de la séparation de source.