jeudi 17 mai 2007

Reconstruction de documents détruits


J'ai eu beaucoup de messages de gens (« anciens », collègues, ...) me signalant des articles au sujet de la reconstruction de documents détruits. Cela m'a donné l'idée de résumer ce que les étudiants ont réussit à faire sur ce sujet dans le cadre de mon cours.
Voici les liens vers les articles en question :

Ces articles leur ont fait pensé au projet que je soumets aux étudiants de deuxième année dans mon cours d'algorithmique pour illustrer les liste chaînées. Je suis content de voir que ce type de projet non seulement est un bon moyen d'intéresser les étudiants à l'algorithmique mais peut aussi avoir des applications pratiques.

Bien sur le projet que nous avons réalisé en deuxième années est moins ambitieux que celui relaté dans ces articles. Il nous manque la traitement d'image mais l'approche algorithmique reste valide. L'année dernière j'avais proposé le challenge « original » de reconstruction de document détruit (et cela à fait l'objet d'une épreuve du challenge sécuritech). Il s'agissait de reconstruire un document comme celui-ci.


Il était assez facile d'arriver à écrire un programme donnant un résultat comme celui-ci (un étudiant avait réussit la reconstruction parfaite).


Cette année nous avons revisité le problème avec une image, et non un document texte. Dans la mesure où il y a beaucoup plus d'information dans une telle image, le problème à été rendu plus compliqué en augmentant le nombre de coupures dans l'image. Le problème semble alors plus limite impossible. Voici l'image « détruite ».


Il n'en reste pas moins que certains étudiants ont réussit à faire un programme opérant la reconstruction parfaite (et beaucoup on fait une reconstruction tout à fait acceptable.)


Quelque soit le type d'image, la problématique se résumait à reconstruire une seule page ou une seule image. Le problème devient bien plus complexe quand il s'agit de reconstruire plusieurs pages différentes, pour deux raisons :
  • Il devient rapidement difficile de générer de très grandes image. Il faut donc décider, au bons endroit, de stopper la reconstruction d'une page pour passer à la suivante, mais sur quels critères ?
  • Comme on peut le voir sur l'exemple du document texte reconstruit, à certains endroit la reconstruction est imparfaite. Il serait très simple à un opérateur de corriger cette erreur « manuellement », si on était capable de lui proposer un nombre d'alternative raisonnable... Or si on traite plusieurs pages la gestion de toutes ces alternatives de reconstruction devient très complexe.
Une solution est de voir le problème les alternative de reconstruction comme un graphe... Chaque morceau de document est représenté par un sommet du graphe et chaque liens entre sommet représente un ordre possible de reconstruction. Il se trouve que les graphes sont au programme du second semestre... Je pense que je tien l'idée de projet pour ce semestre ;-) , reste à trouver un autre projet pour le premier semestre ...
En avant première je me suis amusé à tenter l'aventure et c'est effectivement très instructif, le graphe produit semble bien montrer :
  • certaines zones assez linéaire : il s'agit des régions que l'algorithme de base reconstruit sans problème.
  • certaines zones avec beaucoup d'embranchement : il s'agit des régions où l'algorithme de base risque potentiellement de générer des erreurs, et c'est donc la qu'il faut proposer des solutions alternatives.
  • La topologie de graphe semble donner des indications sur les débuts et fins de page pour permettre à l'algorithme de reconstruction de proposer un résultat par page.
Cette solution semble bien couvrir toutes les problématique d'une reconstruction d'un document de plusieurs pages. Je pense qu'on va bien s'amuser ...