NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 26/05/2014

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

 

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.

 

 

 

ParcimonieSparce 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