NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 24/03/2017 Orientation générale  DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique
	Traitement du Signal
Débutants Général	Compression			Glossaire Général
INDEX Mathématiques Multimédia	Algorithmes	Parcimonie	Ondelettes
		Sommaire de cette page >>> Acquisition comprimée >>> Analogie >>> Parcimonie >>> Échantillonnage >>> Emmanuel Candès

Mathématiques de la PARCIMONIE

Exploiter l'information pertinente pour réduire les tailles mémoire et les temps de transmissions.

Acquisition comprimée

Procédé mathématique qui permet la reconstitution d'images complètes à partir d'une acquisition minimale. L'idée est simple: lorsque nous avons des images nous nous empressons de les comprimer pour qu'elles tiennent moins de place et pour que le temps de leur transmission soit réduit. Il y n'y aurait donc que 10% de signal utile pour 90% de jeter à la poubelle! Alors, pourquoi ne pas focaliser l'acquisition que sur le signal utile? Application majeure en imageries médicale avec deux bénéfices: moins de temps d'exposition aux rayons, et moins de temps d'immobilité imposé aux patients. Autres applications Tous les types d'imagerie; Tous les types de signaux; exemple: augmenter l'autonomie des holters des cardiaques La photographie pour des longueurs d'ondes qui exigent des capteurs coûteux; Le sismique et la recherche pétrolière; L'analyse du génome et la détection d'anomalie; Le calcul des préférences des usagers (livres, films …) Les applications manipulant de grandes quantités de données (Big Data).

Analogie

Parmi 1 million de balles, elles sont toutes identiques sauf mille dont la masse est différente. Comment les retrouver? La méthode exhaustive consisterait à peser chacune des balles. La méthode plus astucieuse consisterait à effectuer des pesées par groupes de balles. Alors, on montre que seulement 4000 pesées sont suffisante (1000 x k). Plus paradoxal encore, l'échantillonnage doit être aléatoire. Les mathématiciens connaissent le graphe qui exprime la quantité de mesures à effectuer pour retrouver l'information.

Voir Énigme des 12 balles

Recherche exhaustive

La méthode de recherche exhaustive consiste à passer en revue toutes les possibilités.

In computer science, brute-force search or exhaustive search consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.

Parcimonie – Sparce signals

Prenez les pixels d'une image quelconque. Il existe toujours des zones comportant les mêmes pixels. Leur frontières sont intéressantes, leur surface beaucoup moins. Ne caractériser que les frontières va réduire l'information décrivant l'image. C'est le principe de la parcimonie. Il existe des méthodes plus performantes que celles indiquée. Par exemple si vous voulez décrire quelques points qui s'approchent d'une parabole, il suffit de donner les paramètres de la parabole. Même principe pour une surface. Il existe des fonctions adéquates pour réaliser ces approximations: les splines, les ondelettes … Jusqu'aux années 2000, la compression intervenait après l'acquisition des données. Ce que nous pratiquons encore lorsque nous voulons envoyer nos photos sur le Web alors que notre puissant appareil photo est capable de plus de 10 millions de pixel: de plusieurs mégaoctets nous passons à quelques centaines de kilooctets). L'idée de limiter l'information à la source est venue avec l'imagerie médicale, notamment pour limiter le temps où le patient doit rester immobile. Avec la méthode de l'acquisition comprimée, le temps est passé de plusieurs minutes d'immobilité à quelques dizaines de secondes.

Expérience de l'auteur (1970)

Pour réaliser le simulateur de radar air-sol en environnement réel, j’avais imaginé une hiérarchie de mémoires (bandes, disque dur, mémoire intermédiaire, et mémoire centrale) et un algorithme d’anticipation des données de terrain nécessaires selon l’évolution de l’avion …

D’ailleurs pour limiter les données, nous avions mis au point une technique de compression de données. La compression est devenue classique. À cette époque, il ne fallait pas trop exagérer car, certes les mémoires étaient limitées, mais tout autant la capacité de calcul. Moralité : ne pas abuser des algorithmes de codage qui aurait coûté beaucoup en puissance calcul pour effecteur la décompression en temps réel. Comme, il est possible d’approximer une courbe par des marches d’escaliers, il est tout aussi possible d’approche une surface par des éléments de surface élémentaire (les splines). Au lieu de définir une matrice de points, il suffit alors de donner quelques coefficients caractérisant la spline. Soit une réduction impressionnante de données.

Échantillonnage

Il semble que l'on oublie Shannon-Nyquist dans cette histoire! En 1949, ces deux Américains, Claude Shannon et Haary Nyquist donnent les conditions nécessaires pour échantillonner un signal: Théorème de l'échantillonnage Si l'on veut restituer un signal dont la fréquence la plus élevée est F, la fréquence d'échantillonnage doit être au moins égale à 2F. L'échantillonnage consiste à prendre une mesure du signal F fois par seconde. Ces mesures dites discrètes sont généralement converties en informations numériques pour être mémorisées et traitées. Avec l'acquisition comprimée, nous faisons fi de ce théorème. Un bel exploit! La clé réside dans le fait que, dans un système d'équations sous-défini (beaucoup plus d'inconnues que d'équations), la solution la plus simple est choisie parmi de multiples possibilités.

Emmanuel Candès (1970-)
Mathématicien français, professeur de mathématique et de statistiques à Stanford University (Californie) – Dans de la Silicon Valley. Polytechnique 1993. Spécialiste du traitement du signal. Outils géométrique pour la représentation des images. Théorie de l'approximation non-linéaire. Généralisation des ondelettes avec les "curvelets et ridgelets", capables de représenter un haut niveau d'ordre dans les signaux Découvreur de l'acquisition comprimée (compressed sensing) en 2004.

Voir Contemporain

Sources: Sites au nom de Candès et le dossier de La Recherche, cités ci-dessous

Suite	Conversion analogique-numérique
Voir	Les algorithmes du monde de 2014 Échantillonnage
Livre	Nous avons développé les mathématiques de la parcimonie – Emmanuel Candès – La Recherche n°484 (février 2014) – Philippe Pajot
Site	Compressing sensing – Emmanuel Candès (Diaporama explicatif très complet en anglais) An introduction to complex sampling – Emmanuel Candès and Michael Wakin (narratif et théorique en anglais)
Cette page	http://villemin.gerard.free.fr/aMaths/Signal/Parcimon.htm