Algorithmique et Programmation—

Projets 2013/2014—

G1: monasse(at)imagine.enpc.fr G2: boulc-ha(at)imagine.enpc.frG3: salauny(at)imagine.enpc.fr G4: arnaud.carayol(at)univ-mlv.frG5: de-la-gm(at)imagine.enpc.fr G6: vialette(at)univ-mlv.fr

Vous devez choisir un projet en binôme, puis envoyer un mail à votre enseignant pour indiquer la compositiondu binôme et le projet choisi. En cas de binômes mixtes entre groupes, envoyez le mail aux deux enseignantset choisissez dans lequel des deux groupes de TP vous allez.

1 DOOM

1.1 Présentation

Doom est l’un des premiers jeux en vue subjective (FPS). Le joueur évolue dans un environnement en 3Davec une vue à la première personne (ce que voit le joueur est ce que voit le personnage).

Ce jeu n’est pas un vrai jeu 3D comme les jeux d’aujourd’hui. La faible puissance des ordinateurs del’époque imposait d’utiliser des astuces pour améliorer le rendu du jeu. L’une des principales astuces est de nejamais passer par un moteur 3D, c’est un jeu en 2.5D. Le personnage se déplace sur une carte 2D, la 3D n’esten fait rendue que lors de l’affichage.

FIGURE 1 – Logo de Doom et exemple de rendu effectué avec Imagine++.

1.2 Travail demandé

1.2.1 Chargement de la carte

Une carte ou niveau, est un fichier texte qui contient une triangulation 2D. Une triangulation est un espacedécomposé en triangles.

Le fichier texte sera de la forme suivante :— des sommets : un sommet est un point 2D.

ex : P 0.5 1— des arètes : une arète est un ensemble de 2 sommets et de deux faces (pour lesquelles elle fait séparation).

On ajoute aussi un booléen (0 ou 1) pour dire si l’arète est contrainte (un mur) ou non (du vide). Parconvention la face extérieure à le label -1.ex : A 2 4 1 3 1 (Arète avec sommets 2 et 4, adjacentes aux faces 1 et 3 et c’est un mur)

— des faces : une face est un triangle, c’est un ensemble de 3 arètes.ex : F 0 1 2

Il faudra charger une telle carte pour pouvoir jouer. Les côtés extérieurs doivent être des murs.

1

FIGURE 2 – Une carte triangulalée, en rouge les mur, en noir les arètes non contraintes.

1.2.2 Position du personnage

Un personnage a une position et une orientation. Il faudra coder une fonction pour situer la personnagesur la carte (la face sur laquelle il est).

1.2.3 Raycasting

Le principe est de lancer un rayon pour chaque colonne de pixels de la fenêtre d’affichage. Lorsque cerayon heurte un mur, on mémorise la distance au mur et on affiche un mur centré en H/2 (H est la hauteur dela fenêtre) et de taille proportionnelle à l’inverse de la distance.

1.2.4 Imagination

Bien sûr avoir codé les étapes précédentes n’en fait pas un jeu. Il faut maintenant laisser parler son ima-gination pour construire un jeu à partir de ce code. Doom ou Wolfenstein 3D sont de bons exemples, mais ilexiste une multitude jeu en 2.5D et encore beaucoup à inventer.

1.2.5 Conseils

— Pour accélerer le raycasting, il faut exploiter la triangulation. on fait passer le rayon de face en face enpartant de la position du personnage jusqu’à heurter un mur.

— Comme il est nécessaire d’avoir la face sur laquelle se trouve le personnage, il est possible d’accéle-rer cette recherche en considérant que le personnage est après avoir bougé, soit sur la même face queprécédemment, soit sur une de ses voisines.

— Pour l’affichage, dessiner à l’écran est lent et non productif. Pour un affichage efficace, on préremplit lestableaux de couleurs et on affiche tout d’un coup.

— Imagine++ possède une multitude classes, points 2D, Images... Utilisez les.— Utiliser la STD pour éviter les problèmes de gestion de mémoire, courant dans les jeux.— l’affichage d’une texture sur les murs devra se faire point par point

2

2 Instagram

2.1 Présentation

Instagram est une application et un service de partage de photos et de vidéos disponible sur plates-formesmobile. Elle permet également d’appliquer des filtres graphiques sur les images ainsi partagées en leurs don-nant un effet retro.

Ces filtres sont, pour la plupart, issus de fonctions simples appliquées à tout ou parties des canaux (Rouge,Vert, Bleu) de l’image. Les reproduire est donc à la portée de n’importe quel débutant en informatique.

FIGURE 3 – Exemples de filtres Instagram. (Wikipedia)

2.2 Travail demandé

— Une interface permettant d’appliquer les filtres à une image préchargée en utilisant des boutons affichésà l’écran.

— Une banque de filtre permettant de transformer une image de multiples façons.

Seuillage Sepia Vignettage

FIGURE 4 – Exemples de filtres avec Imagine. (Wikipedia)

2.3 Image

Une image couleur est constituée de 3 tableaux de même taille contenant des valeurs entières variant entre0 et 255. Ces 3 valeurs représentent les intensités en Rouge, Vert ou Bleu de chacun des pixels.Voici des exemples de couleur :

— NOIR : (0, 0, 0)— BLANC : (255, 255, 255)— ROUGE : (255, 0, 0)— VERT : (0, 255, 0)— BLEU : (0, 0, 255)— VIOLET : (255, 0, 255)

3

Pour représenter une image, il faudra utiliser la class Image de Imagine++ présente dans la librairie Images.Il faudra penser à changer la CMakeList pour y ajouter ImagineUseModules(nomDuProjet Images) et ajouter#include < Imagine/Images.h > au début des fichiers utilisant cette librairie.

2.4 Interface

Il s’agit ici de faire apparaitre l’image ainsi que des boutons sur le bord. Pour cela, on pourra dessinerdes rectangles à côté de l’image et écrire le nom des filtres dessus. Lorsque la souris cliquera sur l’image, saposition nous permettra de savoir sur quel bouton l’utilisateur a appuyé et appliquer le filtre en conséquence.

2.5 Filtres

Il s’agira d’implémenter les filtres présentés dans le TP6 (flou, relief, inversion ...) ainsi que d’en ajouter desplus personnalisés. Voici quelques pistes pour compléter la banque de filtre.

2.5.1 Noir et Blanc

Une image noir et blanc est une image dont chacun des 3 canaux valent la même valeur. Cette valeur estcalculée comme barycentre des 3 couleurs. Cependant, ce n’est jamais la moyenne qui est utilisée.Une fois l’image en noir et blanc ainsi acquise, on peut multiplier indépendamment chacun des canaux parune nouvelle valeur et obtenir le filtre sepia par exemple.

2.5.2 Saturation

Une couleur peut être décomposée en teintes de Rouge-Vert-Bleu mais il existe d’autres espaces colorimé-triques. L’un d’entre eux est le modèle Teinte-Saturation-Valeur ou HSV pour Hue-Saturation-Value en anglais.Le passage d’un espace à l’autre se fait de façon bijective.L’avantage de cet espace est qu’il permet de séparer la saturation. On peut ainsi très facilement (une multipli-cation par exemple) augmenter la saturation ou la diminuer.Pour cela, il suffit de passer dans le domaine HSV, y appliquer un filtre, puis reconvertir l’image en couleur.En utilisant la teinte il est possible de sélectionner tout les pixels proche d’une couleur définie. On peut ainsitransformer l’image en teinte de gris et ne colorer que les zones bleues par exemple.

2.5.3 Vignettage

Pour donner un effet retro à l’image, il est également possible d’ajouter du vignettage à l’image . Cet arte-fact causé par les vieux appareils photos rend les coins de l’image beaucoup plus sombres. Pour cela il suffitd’utiliser une fonction dépendant de l’éloignement du pixel au centre de l’image. On multiplie ensuite les cou-leurs de chacun des pixels par cette fonction qui devra laisser intact les couleurs centrales et rapprocher lescouleurs des coins de la couleur NOIR (0, 0, 0).

2.5.4 Contraste

En floutant une image, on fait disparaitre les bords de l’image. On peut donc obtenir les bords de l’imageen soustrayant l’image floutée à l’image originale.Une fois les bords stockés dans une image à part, en les ajoutant ou en les soustrayant à l’image originale, onpeut faire varier le contraste de l’image.

2.5.5 Conseils

— En attendant que l’interface soit fonctionnelle, utilisez les touches du clavier pour tester différents filtres— Les couleurs sont toujours des valeures entières comprises entre 0 et 255. Cependant, en passant dans

le domaine HSV les valeurs deviennent des flottants. Il est donc conseillé d’utiliser la version float desimages et appliquer la fonction floor (valeur entière inférieure) quand il faut afficher l’image.

— Attention à toujours avoir des valeurs comprises entre 0 et 255. Les dépassements risquent de donnerdes images aux couleurs étranges.

— Lors de la programmation des filtres, des entiers vont être manipulés. Attention, pour deux entiers a etb, a/b représente la division Euclidienne de a par b.

— Soyez créatifs ! !

4

FIGURE 5 – Exemples de reconstitution de panorama. En bas : reconstruction cylindrique d’une vue à 360◦.

3 Construction de panorama

3.1 Introduction

Si on a un ensemble d’images prises par une caméra tournante, les images sont liées les unes aux autres parune transformation à peu de paramètres. On va donc pouvoir transformer chaque image vers l’espace d’uneimage de référence et on obtiendra ainsi une image unique offrant un très grand champ angulaire commemontré en Figure 8.

Lorsque deux caméras sont uniquement en rotation l’une par rapport à l’autre et sans translation (le centreoptique ne bouge pas), les coordonnées des points x dans l’image 1 et x′ dans l’image 2 visualisant un mêmepoint 3D P de la scène, sont liées par la relation (pour simplifier) x′ = Hx. Ainsi pour une série d’imagesprises par une caméra tournante on déduit, à partir des mises en correspondance de points, des mises encorrespondance d’images grâce aux homographies H . De cette façon on va pouvoir rectifier toutes les imagespour les mettre en correspondance avec une image de référence choisie (a priori l’image centrale en terme depoint de vue angulaire dans la série de photos) et ainsi reconstruire un panorama.

Notez que comme souvent en informatique, nous importons le vocabulaire anglo-saxon et employons icile terme “caméra” au sens appareil photographique.

3.2 Un peu de Théorie : caméras en rotation

Nous supposons que la caméra est un modèle parfait pinhole, 1. Dans le repère attaché à la caméra (x ety dans le sens des pixels de l’image, z orthogonal au plan image, l’origine est le centre optique O) on a unetransformation simple qui est représentée dans la Figure 6.

En utilisant le théorème de Thalès on obtient : x′ = f ′ xzy′ = f ′ yzz′ = −f ′

Si l’origine dans le plan image est dans le coin en haut à gauche de l’image comme c’est souvent le cas onobtient alors : {

x′ = f ′ xz + u0y′ = f ′ yz + v0

,

où (u0, v0) sont les coordonnées pixel du point C ′.Evitons la division en multipliant ces équations par z pour obtenir un système linéaire :uv

w

:=

x′zy′zz

=

f ′ 0 u00 f ′ v00 0 1

xyz

= K

xyz

.

1. la traduction française “sténopée” est rarement employée

5

FIGURE 6 – Modéle de caméra pinhole

Notez que x′ = u/w et y′ = v/w.Maintenant si le repère est toujours centré au centre optique de la caméra mais avec une rotation on obtient :uv

w

= KR

xyz

et pour la seconde caméra qui à le même centre optique mais une autre rotation on a :u′v′

w′

= K ′R′

xyz

.

Eliminons les inconnues x, y et z de ces 6 équations ; les matrices K et R étant inversibles on en déduit :u′v′w′

= K ′R′R−1K−1

uvw

= H

uvw

.

Pour repasser des coordonnées projectives aux coordonnées euclidiennes il suffit de diviser par la troisièmecoordonnée w′, soit x′ = u′

w′ et y′ = v′

w′ . Nous n’utilisons pas le fait que K = K ′ (même focale), donc entoute généralité, la matrice H a 9 coefficients. Notons que H peut être multipliée par un réel λ quelconqueet on obtient encore les mêmes x′ et y′. Donc on a 8 coefficients indépendants, et on peut supposer h33 = 1.On en déduit la relation homographique en développant la relation matricielle ci-dessus et en divisant par latroisième coordonnée : x′ = a1x+a2y+a3

a7x+a8y+1 et y′ = a4x+a5y+a6a7x+a8y+1 , où a1 . . . a8 sont les coefficients de H . Ainsi, avec

les coordonnées d’un point vu dans les deux images, déduisez de ces deux équations la relation du type :

A(x, y, x′, y′)

a1a2a3a4a5a6a7a8

︸ ︷︷ ︸

h

= b1(x, y, x′, y′).

Ce système est composé de 2 équations.En déduire qu’avec 4 points en correspondance dans les deux images, on a la relation

A︸︷︷︸8×8

h = b.

Ainsi on peut simplement en déduire les 8 coefficients de l’homographie. Une fois cette homographieconnue on peut facilement calculer les coordonnées dans l’image 2 d’un point de l’image 1 :{

x′calcul = a1x+a2y+a3a7x+a8y+1

y′calcul = a4x+a5y+a6a7x+a8y+1

6

3.3 Calcul de l’homographie par RANSAC

La première étape consiste à extraire des points d’intéret dans les images et à les mettre en correspondanceentre 2 images. Etant donné un point d’intéret dans une image on cherche tous les descripteurs des pointsd’intéret dans l’autre image et on conserve le plus proche ; s’il est suffisemment proche, on le considère commeune correspondance. Le programme extrayant les points d’intéret, les descripteurs et la mise en correspon-dance vous est fourni avec un fichier test.cpp pour avoir un exemple d’utilisation.

Dans cet ensemble E de correspondances on a des correspondances effectivement correctes inliers et descorrespondances fausses dites outliers. On cherche a déterminer les inliers et les outliers gràce à un algorithme,le RANSAC, que vous allez implémenter.

Le RANSAC (RANdom SAmple Consensus) consiste à itérer un grand nombre de fois N des hypothèsesd’inliers et à les vérifier. A chaque itération on prend s correspondances au hasard nécessaires à l’estimationdu modèle, parmi l’ensemble de correspondances E. Ici s = 4 et le modèle est l’homographie H . Ensuiteon teste le nombre de points en adéquation avec le modèle, soit le nombre d’inlier ni. Ici la correspondance(x, y)↔ (x′, y′) est un inlier si l’erreur de reprojection est sous un seuil s (en général s = 1− 2 pixels) :

x′calcul =a1x+a2y+a3a7x+a8y+1

y′calcul =a4x+a5y+a6a7x+a8y+1

si (x′ − x′calcul)2 + (y′ − y′calcul)2 ≤ s2 alors c’est un inlier.

A la fin de chaque itération on teste si on a plus d’inliers que pour les itérations précédentes si c’est le cas onenregistre et met à jour le plus grand nombre d’inlier et la meilleure homographie, nbest et Hbest ainsi que untableau d’indice des inliers Indinliers. Au bout de N itérations on a le modèle Hbest qui a permis de retrouverle plus grand nombre d’inliers, ainsi que les indices des inliers Indinliers.

Ce modèle Hbest a été obtenu à partir de seulement 4 correspondances et n’est pas ajusté au mieux à l’en-semble des inliers. A partir de là on estime la meilleure solution avec l’ensemble des inliers. Notre équation vuepour estimer le modèle à partir de 8 points devient :

A︸︷︷︸(2×nbest)×8

h = b︸︷︷︸(2×nbest)

(plus d’équations que d’inconnues). La solution approchée est :

hfinal = PseudoInverse(A) b︸︷︷︸(2×nbest)

.

Pour résoudre un système surdéterminé comme ci-dessus, on utilise la fonction linSolve de la bibliothèqueLinAlg d’Imagine++.

Pour estimer le modèle final avec les nbest points il est préférable de donner une égale importance à chaqueligne de l’équation Ah = b. Pour cela on peut simplement diviser chaque ligne de A par sa norme et diviser lescoefficients de b en adéquation. Il est en fait préférable d’utiliser une normalisation plus adaptée au problèmequi consiste à travailler sur des points normalisés tels que les inliers aient pour moyenne 0 et une déviationstandard de 1. On à alors les équations matricielles utilisant les coordonnées projectives (u, v, w) (on note avecun ˆ les données dans l’espace normalisé) :uinlier1vinlier1

winlier1

= Norm1︸ ︷︷ ︸3×3

uinlier1vinlier1winlier1

uinlier2vinlier2winlier2

= Norm2︸ ︷︷ ︸3×3

uinlier2vinlier2winlier2

uinlier1vinlier1winlier1

= H

uinlier2vinlier2winlier2

En déduire la fonction de dénormalisation permettant de passer de H àH , en fonction deNorm1 etNorm2.

3.4 Démarche générale et Implémentation

On calculera les homograhies de proche en proche entre 2 images consécutives. Puis on calculera les com-position d’homographies qui permettent de passer d’une image à l’image centrale de référence. Pour chaqueimage on calculera la bouding box en fonction des coordonnées des 4 sommets d’une image et de leur trans-formations homographiques dans l’image de référence. Ainsi avec toutes les images on obtiendra la tailleminimale de la fenêtre qu’il nous faut.

7

Du point de vue de l’implémentation, un programme de test utilisant les librairies nécessaires et leur utili-sation vous est fourni. Principalement : calcul matriciel, extraction de points d’intéret, mise en correspondance.On utilisera le module LinAlg d’Imagine++ pour les matrices et la résolution de systèmes linéaires.

Remarque : la bonne façon de calculer l’image transformée par une homographie n’est pas de pousser lespixels originaux vers l’image résultat, mais au contraire de partir des pixels de l’image finale et de voir d’oùils viennent dans l’image initiale (donc de se servir de l’inverse de H).

Avant même de programmer le RANSAC, faites le test avec deux images seulement et des correspondancescliquées par l’utilisateur.

Vous pouvez commencer par utiliser les images fournies avec le projet puis chercher sur le web d’autresimages permettant de reconstituer des panoramas.

3.5 Travail supplémentaire : recollage d’images

Lorsque vous recollez les images, vous pouvez voir nettement les frontières de recollement, car les imagesA et B ont des différences d’intensité lumineuse. S’il vous reste du temps, Il est donc plus élégant de faireune frontière progressive. Le problème est de recoller deux images A et B en une image C sans que cela soitflagrant. On part de deux méthodes.

L’idée la plus naïve consiste à construire C(x) = (1− λ)A(x) + λB(x) avec λ qui passe progressivement de0 à 1.

S’il vous reste davantage de temps, vous pouvez essayer la méthode suivante qui est plus efficace : leprincipe du mélange multi-échelle est de faire varier λ de 0 à 1 sur une bande de largeur dépendant de lafréquence. Plus exactement, on décompose les images en fréquence. On mélange leur spectre sur une largeurdifférente pour chaque fréquence. Puis on revient à l’espace initial pour obtenir l’image finale. Cette méthodeest décrite ici :http://web.mit.edu/persci/people/adelson/pub_pdfs/spline83.pdf.

8

4 Jeu des inversions

4.1 Présentation

Afin de comprendre l’évolution du génome de groupes d’espèces, de nombreux outils mathématiques etalgorithmiques ont été développés. C’est en particulier le cas de la reconstruction de scénarios d’évolution ba-sés sur des réarrangements génomiques, modélisation que nous utiliserons sous forme d’un jeu dans ce projet.Les génomes sont alors codés par des permutations signées. (Chaque élément de la permutation représenteun segment génomique stable, c’est-à-dire conservé entre plusieurs génomes d’étude.) L’objectif est alors deretrouver la bonne séquence d’inversions qui transforme une permutation d’un génome en une autre.

Intéressons nous au problème le plus connu, le tri par inversions : étant donnée une permutation de n élé-ments, le but est d’ordonner ses éléments de façon croissante en utilisant le moins de retournements d’inter-valles possibles. Il est à noter que nous nous intéressons ici à des permutations signées : chaque élément est dotéd’un signe positif ou négatif représentant l’orientation du gène correspondant, et où les inversions inversentégalement le signe des éléments sur lesquels elles agissent. Les permutations représentent des ordonnance-ments de partitions de génomes que l’on désire comparer, et les inversions correspondent à des mutations ouréarrangements génomiques se produisant au cours de l’évolution de ces espèces.

π = −5 +1 +2 +4 −7 −3 +6

−5 +1 +2 −4 −7 −3 +6

−5 +1 +2 −4 −7 −6 +3

−5 +1 +2 −4 −3 +6 +7

−5 +1 +2 +3 +4 +6 +7

−5 −4 −3 −2 −1 +6 +7

σ = +1 +2 +3 +4 +5 +6 +7

FIGURE 7 – Un exemple de tri par inversions signées. Chaque opération renverse l’ordre des éléments contenusdans l’intervalle sur lequel elle agit, ainsi que leur signe.

Sous forme de jeu, il s’agit alors à partir d’une permutation signée donnée d’effectuer le moins d’inversionspossible pour parvenir à l’identité. Il est bien sûr possible de jouer seul, mais le plus intéressant est un modecontre l’ordinateur : à partir de la même permutation signée, le joueur et l’ordinateur jouent simultanémentune inversion sur leur permutation courant, le premier parvenant à l’identité étant déclaré vainqueur.

4.2 Travail demandé

Programmer le jeu des inversions en mode "joueur contre ordinateur". Pour débuter, il sera bien sûr plusfacile de programmer le jeu en mode "un joueur". Pour l’intelligence artificielle, il est conseillé de commencerpar minimiser le nombre de points de cassure dans la permutation.

9

FIGURE 8 – Exemples de configurations initiales de Candy Crush. Notez que le plateau n’est pas forcémentcarré.

5 Candy Crush

5.1 Introduction

Candy Crush est un jeu qui connait un grand succès sur smartphone. Les règles sont simples : vous de-vez vider le tableau de tous les éléments. Pour cela, vous avez le droit de permuter deux éléments voisinsdans n’importe quelle direction. Si vous alignez trois éléments identiques sur une même ligne ou colonne, ilsdisparaissent et font descendre les éléments situés au-dessus. Les combinaisons de 4 ou 5 ont des effets pluscomplexes, voir par exemple http://www.wikihow.com/Play-Candy-Crush-Saga.

5.2 Travail demandé

Il s’agit en premier lieu de fournir la fonctionnalité de base : les éléments sont sur le plateau et l’utilisateurpeut permuter des éléments voisins. Les combinaisons de 3 sont gérées. Attention, une combinaison de 3 peuten créer une autre par le jeu de la descente de la partie supérieure.

Dans une deuxième partie, on créera des niveaux : faire jouer l’ordinateur à l’envers ; il fait partir du basune combinaison de 3, en rajoute une autre en faisant éventuellement monter les éléments déjà installés pourfaire de la place, etc. En fin de compte, on fait quelques inversions de voisins.

Pour aller plus loin, on pourra :

1. laisser la possibilité au joueur de refaire le tableau avec la même configuration initiale.

2. demander la solution à l’ordinateur, qui montrera la bonne combinaison d ’inversions.

10

FIGURE 9 – A partir de l’image exemple en haut à droite, on peut générer des images de largeur arbitraire(plus petite ou plus grande, à gauche), en découpant suivant des chemins verticaux et en recollant. Chaqueassemblage possible est défini par un chemin dans un graphe, dont celui de coût minimal est choisi. Lescoupures rouges représentent une transition parallèle, celles en vert par successeur immédiat.

6 Génération de texture à partir d’exemple

6.1 Présentation

En synthèse d’image, générer une texture structurée, typiquement une texture d’immeuble, est un pro-blème délicate à faire a priori de façon réaliste, même en ayant des règles d’agencement (espacement entrefenêtres, etc.). Les meilleurs résultats sont obtenus en partant d’une image exemple et en la déformant pourqu’elle fasse la taille voulue. Cependant un simple zoom sur l’image n’est pas satisfaisant dès que le facteurn’est pas proche de 1. Une solution proposée récemment est de générer la nouvelle image en découpant desbandes de l’image exemple et en les recollant comme un puzzle, de manière à minimiser les artefacts visuels.

Le découpage se fait en deux étapes : une première fois horizontalement jusqu’à atteindre la largeur voulue,une deuxième fois verticalement sur l’image intermédiaire pour atteindre la hauteur voulue. Les minimisationsse font en appliquant un algorithme célèbre de plus court chemin dans un graphe :

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

qu’il sera nécessaire de comprendre et d’implémenter.

6.2 Principe

On va s’intéresser au redimensionnement horizontal de l’image. Le redimensionnement vertical utilise lemême principe. Pour redimensionner dans les deux directions, on peut le faire d’abord horizontalement puisappliquer sur l’image générée le redimensionnement vertical.

On assemble des morceaux de l’image initiale découpés suivant des bandes verticales (non droites) pourobtenir l’image finale, voir Figure 9. Chaque collage engendre un coût d’autant plus fort que les pixels à gaucheet à droite de la coupure sont dissemblables. Définissons une coupure et ce qui y est attaché (image initiale detaille W ×H :

— coupure : application c de {0, . . . ,H − 1} → {−1, . . . ,W − 1} telle que |c(y) − c(y + 1)| ≤ 1, désignantun découpage entre les pixels.

— successeurs d’une coupure c : coupures c′ telles que c ≤ c′ et c 6= c′, successeurs immédiats ceux pourlesquels c ≤ c′′ ≤ c⇒ c′′ ∈ {c, c′}. Les successeurs immédiats se coupent forcément.

— coupures parallèles : ce sont des coupures telles que c′(y)− c(y) est une constante indépendante de y.— coût d’une paire de coupures parallèles :

δ(c, c′) =∑y

‖I(c(y) + 1, y)− I(c′(y), y)‖4.

— bande : partie de l’image entre une coupure c et une coupure parallèle (bande parallèle) ou successeurimmédiat c′.

— coût d’une bande : le coût de la paire de coupures si c’est une bande parallèle, 0 sinon.

6.3 Ensemble des coupures

On sélectionne un ensemble de coupures C possibles avec l’algorithme suivant :Pour chaque σ ∈ {1, . . . ,W − 1} :

11

FIGURE 10 – Exemples de synthèse, les images initiales sont marquées par un carré rose.

1. Calcul de la carte d’erreur :

Eσ : {0, . . . ,W − σ − 1} × {0, . . . ,H − 1} → N(x, y)→ ‖I(x, y)− I(x+ σ, y)‖4

2. Tant qu’il existe un plus court chemin π de coût fini de haut en bas de Eσ

(a) Ajoute à C les chemins parallèles correspondant à π

(b) Met à∞ les pixels de Eσ à moins de σ pixels de π

6.4 Assemblage des coupures

On définit un assemblage par un recollement de bandes, c’est-à-dire un chemin dans le graphe dont lessommets sont les coupures et les arêtes désignent les bandes. A chaque sommet on a un choix d’arêtes : soitaller vers une coupure parallèle (avec coût), soit aller vers une coupure successeur immédiat (coût nul).

Partons de la coupure c−1(y) = −1. Définissons la largeur d’un assemblage (c−1, c0, . . . , cn) par

w(c−1, c0, . . . , cn) = miny

∑{ci(y)− ci−1(y) : ci successeur immédiat de ci−1}.

Cela représente l’abscisse minimale de la bande. On cherche parmi les assemblages celui dont la largeur w ≥W ′ (W ′ étant la largeur cible de l’image) et ce coût minimal parmi celles-ci.

6.5 Travail demandé

Partir d’images initiales et essayer de leur faire subir diverses variations de dimensions horizontales etverticales, dans le style de la Figure 10. Quand vous générez une image, montrer aussi les coupures avec descouleurs différentes pour les coupures parallèle et successeur immédiat.

12

7 Fast Marching

7.1 Introduction

Le fast marching est une méthode de calcul de chemins minimaux étant donné une carte de potentiel. Il géné-ralise l’algorithme de Dijkstra (cf. http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra.) pourdes métriques plus complexes que la distance euclidienne et distance `1. Cette technique est assez largementutilisée pour la segmentation d’images médicales, extraction de structure tubulaires (angiographie, extractionde routes, . . .). On peut y trouver d’autres applications comme la planification de chemin en robotique.

En théorie des graphes, le problème est modélisé à chercher un chemin entre deux nœuds d’une grapheG(E, V), telle que la somme des poids d’arête que le chemin a parcouru est minimisée.

7.2 L’approche

Dans ce projet, nous demandons de trouver le plus court chemin sur une image à partir d’un point dedépart et un point d’arrivé illustré à la fig. 7.2. Il est naturel de considérer l’image comme une graphe où lespixels sont des nœuds et les arêtes sont des liens entre les voisins.

FIGURE 11 – Le plus court chemin sur une photo satellite.

En 2D, étant donné un métrique W(x, y),un point de départ (x0,y0) et un point d’arrivé (x1,y1) le cout totald’une courbe r(t) à minimiser est :

‖L(r)‖ =∫ 1

0

(W (r(t))||r′(t)||)dt (1)

où r(0)=(x0,y0) et r(1)=(x1,y1).

Le cout de déplacement vers (x, y) qu’on défini dans un premier temps est le suivant :

‖W (x, y)‖ = ε+ |f(x0, y0)− f(x, y)| (2)

où ε est une constant de lissage,f(x,y) est le niveau de gris du voisin avec lequel on construit le lien.

7.3 La carte de distance

Chercher la solution en itérant sur tous les chemins possible est peu efficace. En fait, la recherche du cheminpeut se faire a l’aide de la carte de distance.

A partir du point de départ d, on calcule petit à petit le cout de chemin d’abord pour les voisins de d, puispour les voisins des voisins, etc... Si un point p est déjà calculé mais on rencontre à nouveau ce point dansl’itération, on garde la valeur la plus petite. Attention : si p est mis à jour à nouveau, les voisins de p le doiventaussi (si nécessaire), et les voisins des voisins etc...(Conseil : on utilise la notion de points actifs). L’itération decalcul de la carte de distance se termine au moment où la frontière touche le point d’arrivée.

Le premier travail consiste donc à réaliser et illustrer la processus pour calculer la carte de distance à partird’une image donnée 12.

13

FIGURE 12 – calcule de la carte de distance

7.4 La descente de gradient

Une fois la carte de distance réalisée, il suffit de calculer les gradients des points sur la carte de distance, eteffectuer une descente de gradient à partir du point d’arrivée jusqu’au point de départ.

Donc le deuxième travail est de— calculer et montrer l’image des gradients.— montrer le chemin construit sur l’image des gradients, la carte de distance et l’image initiale 13.

FIGURE 13 – l’image des gradients, la carte de distance et l’image initiale avec la solution

7.5 Variation de ε

Dans cette partie, vous devez essayer de varier la valeur ε pour voir les résultats diffèrer. Quand ε tend versl’infini et quand ε tend vers 0, que deviendra la courbe ?

7.6 Variation de la fonction W(x, y)

Maintenant, vous devez aussi varier la fonction W pour voir la performance. Si W est quadratique ? Siau lieu de comparer avec (x0, y0), le cout de déplacement W(x,y) ne dépend que du contraste avec le voisin(xv,yv) ? Rapporter vos résultats.

7.7 Tester sur d’autres images

Vous pouvez maintenant tester le programme sur d’autres images avec des paramètres appropriés. Parexemple, lancez le programme sur les images de labyrinthes et les images de carte de parc pour trouver les

14

plus courts chemins.14

FIGURE 14 – l’image de labyrinthe et la carte de distance

7.8 Application à la détection de contours

Le plus court chemin peut aussi appliquer à la détection de contours, qui consiste à trouver le cheminpassant par les points ayant un grand contraste. Ici, le poids peut être défini comme :

W(x, y) =1

ε+ Gσ * G(x,y)(3)

où G(x, y)=||∇ f||, * est une convolution

Il vous faut :

1. Programmer d’abord l’image de gradient, IG

2. Ensuite, lisser l’image IG par une gaussienne G de variance σ pour obtenir l’image I* qui représenteGσ*G(x,y)

3. Programmer aussi l’image 15 qui représente 1ε+Gσ*G(x,y) .

FIGURE 15 – l’image initiale, l’image Gσ * G(x,y) et l’image W(x,y)

4. Choisir deux points sur le contour, et programmer la carte de distance pour les deux.

5. Sélectionner les point à équidistance des deux points de départ.

6. Trouver deux points sur la ligne d’équidistance, qui ont les valeurs de distance les plus petites

7. Trouver les plus courts chemins entre les points pour compléter le contour

8. Faire la même chose sur d’autres images 16 pour tester.

7.9 Segmentation d’image

En fait, on peut avoir un ensemble de points de départ au lieu d’avoir un seul, et encore plus, avoir plusieursgroupes d’ensembles de points. Donc on peut segmenter l’image en posant seulement quelques taches pourindique vaguement les parties différentes.

Vous devez dans cette partie,

15

FIGURE 16 – les étapes de la segmentation

— Proposer et implémenter cette méthode de segmentation.— Expliquer vos algorithmes et les résultats— Améliorer le système

7.10 Travail à fournir

1. Implémenter et vérifier la technique de la carte de distance.

2. Réaliser une interface graphique simple avec Imagine++ permettant de poser des points de départ etles point d’arrivée, de charger les fichier et d’illustrer les résultats. Il faut donc être capable de :— Charger une image.— Choisir l’application qu’on veut utiliser (chercher le plus court chemin, détection de contour ou

segmentation)— modifier les paramètres s’il y en a.— afficher la solution et la carte de distance— Annuler ou recommencer une action (pour la pose de point)— Sauvegarder l’image de la carte de distance et la solution obtenue.

3. Analyser vaguement le temps d’exécution.

8 Autre

Vous pouvez proposer des sujets (à faire valider par le responsable du cours !) mais ne le faîtes que si vousvous sentez à l’aise en programmation et si vous êtes autonome.

16