Description

Projet 3: R´esolution de probl`emes
On souhaite r´ealiser une application de recherche et de reconnaissance de croquis (“sketch” en anglais), c’est-`a-dire des croquis r´ealis´es rapidement `a main lev´ee. Pour ce faire, on a identifi´e dix classes d’int´erˆet et on dispose d’une base de donn´ees de r´ef´erence contenant 1000 croquis par classe (voir la figure 1 pour un exemple de croquis pour chacune des 10 classes).
A partir d’un croquis source (la requˆete), l’objectif est d’identifier le plus rapidement possible dans la base de donn´ees les k croquis “les plus proches” de cette requˆete selon une certaine mesure de distance. Les croquis ainsi retrouv´es peuvent ˆetre ensuite utilis´es pour faire une pr´ediction de la classe du croquis source, par exemple, en lui attribuant la classe majoritaire (i.e. la plus fr´equente) parmi les k croquis retrouv´es. Le processus est illustr´e sur un exemple `a la figure 2.
1 Description de l’approche
1.1 Repr´esentation des croquis
Un croquis est repr´esent´e par un ensemble de strokes. Un stroke est une polyligne repr´esentant un coup de crayon. Une polyligne est repr´esent´ee par une succession de points formant des segments de droite. L’ordre des strokes et des points `a l’int´erieur d’un strokes suit l’ordre chronologique de trac´e du croquis.
1.2 Dynamic time warping
Puisque le nombre de strokes et de segments par stroke varient d’un croquis `a l’autre, on se propose de proc´eder en deux temps pour calculer la similarit´e entre deux croquis. D’abord, on concat`ene les strokes d’un croquis en une seule polyligne. On obtient alors une s´erie temporelle d´ecrivant l’´evolution de la position du crayon. Ensuite, puisque ces s´eries ont des longueurs diff´erentes, on propose de calculer la distance entre elles `a l’aide d’un algorithme appel´e dynamic time warping (DTW). Cet algorithme g´en´erique calcule la distance entre deux s´eries temporelles en prenant en compte les variations en termes de vitesses et de longueurs entre les deux s´eries. Il semble donc tout `a fait appropri´e pour prendre en compte les variabilit´es en termes de d´eplacements du crayon entre personnes.
(c) Hamburger (classe 2) (d) Nuage (classe 3)
(a) Arbre (classe 0) (b) Zigzag (classe 1)

(e) Cellule (classe 4) (f) Balais (classe 5) (g) Porte (classe 6) (h) Tour Eiffel (classe 7)

(i) Soleil (classe 8) (j) Cl´e (classe 9)
Figure 1 – Exemples de croquis

(b) Plus proche voisin(a) Requˆete

(c) Deuxi`eme plus proche voisin
(d) Troisi`eme plus proche voisin
Figure 2 – Requˆete et plus proches voisins
1 is n

Figure 3 – Repr´esentation d’un chemin consid´er´e par le dynamic time warping.
L’id´ee de l’algorithme DTW est de rechercher l’appariement des points des deux s´eries temporelles (respectant l’ordre temporelles de ces points) qui minimisent la somme des distances entre points appari´es. Plus formellement, soient deux s´equences de points X = hx1,…,xmi et Y = hy1,…,yni. La distance DTW entre ces deux s´equences est d´efinie par :
k
DTW(X,Y ) = min Xd(xil,yjl) (1)
h(i1,j1),…,(ik,jk)i∈P(X,Y )
l=1
ou` d mesure la distance entre deux points et P(X,Y ) est l’ensemble des s´equences de paires d’indices h(i1,j1),…,(ik,jk)i telles que :
— (i1,j1) = (1,1), (ik,jk) = (m,n), — 0 ≤ is − is−1 ≤ 1 et 0 ≤ js − js−1 ≤ 1,
— is > is−1 ou js > js−1.
Sur une grille discr`ete de taille m × n, les s´equences de P sont donc tous les chemins allant du point (1,1) au point (m,n) en se d´epla¸cant d’une case maximum, soit vers la droite, vers la haut, ou en diagonale (voir figure 3). Bien que le nombre de chemins soit tr`es important, on vous demande dans ce projet d’impl´ementer le calcul de la distance (1) de mani`ere efficace en vous basant sur la programmation dynamique.
Dans le cadre de ce projet, nous utiliserons comme mesure de distance entre deux points xi = (xi,1,xi,2) et yj = (yj,1,yj,2) la distance absolue moyenne :
(2)
1.3 Recherche des k croquis les plus proches
La d´etermination des k croquis les plus proches d’un croquis source, not´e Q, dans la base de donn´ees de r´ef´erence, not´ee LS (pour “Learning Set”), sera effectu´ee par une fonction NearestNeighbours(LS, Q, k). Cette fonction devra calculer les distances selon l’algorithme DTW entre le croquis Q et successivement tous les croquis de l’ensemble LS. Afin de maintenir efficacement les k croquis les plus proches lors du parcours de la base de donn´ees de r´ef´erence, nous vous demandons d’utiliser une file `a priorit´e dont la capacit´e sera limit´ee `a k ´el´ements maximum et utilisant la distance `a l’exemple Q comme valeur de priorit´e. Lors du parcours de la base de donn´ees de r´ef´erence, un croquis sera ajout´e `a la file, soit si cette file contient moins que k croquis, soit si ce croquis est plus proche de Q que le croquis de la file le plus ´eloign´e de Q. Dans ce dernier cas, le nouveau croquis devra remplacer dans la file le croquis le plus ´eloign´e de Q.
1.4 Optimisation
Lorsque l’ensemble LS est grand, la recherche des k plus proches croquis d’une requˆete peut
ˆetre relativement lente. Dans le cas ou` la file contient d´ej`a k croquis, il est possible d’´eviter d’avoir `a effectuer tout le calcul de la distance DTW pour un nouveau croquis en prenant en compte la distance maximale courante, not´ee dmax, entre un croquis de la file et la requˆete. L’algorithme DTW calcule en effet une matrice de couˆt colonne par colonne ou ligne par ligne. D`es que le minimum d’une colonne ou d’une ligne est sup´erieure `a la distance dmax, on a la garantie que la distance DTW ne pourra pas ˆetre inf´erieure `a dmax et il est alors possible d’arrˆeter pr´ematur´ement le calcul de la distance. Pour impl´ementer cette optimisation, la fonction de calcul de la distance DTW prendra comme argument, en plus des deux s´equences, la distance maximale dmax et elle pourra interrompre son calcul et renvoyer une valeur +∞ d`es que la distance dmax sera d´epass´ee.
2 Impl´ementation
Les fichiers suivants vous sont fournis :
— Sketch.h/c : une librairie d´efinissant les structures utilis´ees pour repr´esenter les croquis et les bases de donn´ees et impl´ementant des fonctions permettant de charger en m´emoire un ensemble de croquis `a partir d’un fichier, d’afficher leur classe et de g´en´erer une image (au format ppm) du croquis. Cette derni`ere fonction utilise une librairie graphique (fichiers easyppm.h/c) ´egalement fournie.
— main.c : un fichier main d’exemple utilisant les fonctions `a impl´ementer pour retrouver les k plus proches croquis d’une requˆete ou pour calculer le taux d’erreur sur un ensemble de croquis de test.
— Makefile : un Makefile pour compiler et ex´ecuter le code.
Les diff´erents fichiers `a fournir sont les suivants :
— DynamicTimeWarping.c contenant l’impl´ementation du dynamic time warping en r´epondant `a l’interface d´efinie dans DynamicTimeWarping.h. Votre impl´ementation doit ˆetre bas´ee sur la programmation dynamique et exploiter l’optimisation d´ecrite dans la section 1.4.
— BoundedPriorityQueue.c regroupant les diff´erentes fonctions li´ees `a la file `a priorit´e dont l’interface est pr´ecis´ee dans le fichier BoundedPriorityQueue.h.
— NearestNeighbours.c impl´ementant la fonction de recherche des k croquis les plus proches selon l’interface d´efinie dans NearestNeighbours.h.
En outre, nous vous fournissons les bases de donn´ees suivantes :
— testset.txt la base de donn´ees de test.
— trainingsetverylarge.txt la base de donn´ees de r´ef´erence contenant 1000 exemples par classe.
— trainingset.txt un sous-ensemble de la base de donn´ees de r´ef´erence contenant 100 exemples par classe.
3 Rapport
R´epondez aux questions suivantes dans votre rapport :
1. Dans le cadre du Dynamic Time Warping, d´efinissez la fonction de couˆt qu’on cherche `a minimiser en pr´ecisant les param`etres dont elle d´epend. Donnez ensuite la formulation r´ecursive de cette fonction de couˆt `a la base de la solution par programmation dynamique. Si vous consultez certaines sources pour d´eriver cette formulation, citez les.
2. Pr´ecisez quelle impl´ementation (ascendante ou descendante) vous avez adopt´ee et donnez la complexit´e en temps et en espace de cette impl´ementation en fonction des longueurs m et n des s´equences compar´ees. Vous pouvez n´egliger l’optimisation de la section 1.4 pour cette analyse.
3. Donnez et justifiez (bri`evement) la complexit´e de la fonction NearestNeighbours que vous avez impl´ement´ee au pire et au meilleur cas en fonction de q = |Q|, le nombre de points du croquis Q, de N = |LS|, le nombre d’´echantillons de r´ef´erence, de l, la longueur des croquis de LS (qu’on supposera constante) et de k, le nombre de voisins. Vous pouvez ´egalement n´egliger l’optimisation de la section 1.4 pour cette analyse.
4. Pour k ∈ {1,3,7}, calculez le taux d’erreur de reconnaissance des ´echantillons de tests en utilisant les deux bases de donn´ees de r´ef´erence fournies. Le taux d’erreur est la fraction du nombre de fois ou` la vraie classe d’un croquis de l’ensemble de test ne correspond pas `a la classe majoritaire parmis les k croquis les plus proches de l’ensemble de r´ef´erence.
5. Reportez dans le rapport les temps n´ecessaires au calcul de ces taux d’erreur en fonction de k. Pr´ecisez s’ils sont en accord avec la complexit´e th´eorique.
NearestNeighbours.c et BoundedPriorityQueue.c) doiventˆetre soumis via deux projets s´epar´es sur Gradescope.
Vos fichiers seront ´evalu´es avec les flags habituels (–std=c99 –pedantic -Wall -Wextra -Wmissing-prototypes – DNDEBUG) sur les machines ms8xx. Respectez bien les noms des fichiers et n’incluez aucun fichier suppl´ementaires.
Un projet non rendu `a temps recevra une cote globale nulle. En cas de plagiat av´er´e, l’´etudiant se verra affecter une cote nulle `a l’ensemble des projets.
Les crit`eres de correction sont pr´ecis´es sur Ecampus.
Bon travail!