Mercredi 26
Heuristiques et méta-heuristiques
Abbas Eldor
› 14:00 - 14:20 (20min)
› Bât. C - Sigalas
Une comparaison entre deux méthodes de recherche locale pour la reconstruction des images binaires convexes
Mohamed Hadded  1@  
1 : Doctorant à l'école nationale des sciences informatiques

Parmi les problèmes de la tomographie discrète est la reconstruction des images binaires à partir seulement de deux projections H et V qui donnent respectivement le nombre cellules noires dans chaque ligne et dans chaque colonne. Ce problème est polynomial et de nombreuses solutions peuvent exister. Afin de réduire l'espace des solutions réalisables, une connaissance préalable sur l'image à reconstruire doit être considérer. Dans ce travail, nous nous intéressons au problème de reconstruction de matrices binaires convexes à partir de projections orthogonales. Ce problème consiste à trouver une image binaire qui respecte les projections orthogonales (H, V) et qui maximise le nombre des cellules noires adjacentes dans chaque ligne et dans chaque colonne. Puisque ce problème est NP-Complet, plusieurs méthodes de résolution approximatives ont été proposées afin de résoudre ce problème. Dans ce travail, nous reformulons ce problème comme un programme linéaire en nombres entiers et nous présentons une comparaison entre deux méthodes de recherche locale « la recherche taboue et HillClimbing ». Les résultats numériques montrent que la recherche taboue est plus performante que HillClimbing en termes de qualité de résultat et le temps d'exécution.



  • Autre
Personnes connectées : 1