| Titre : | Approche quantique pour l'appariement de formes |
| Auteurs : | MEZGHICHE Mohamed Khalil, Auteur ; kamal Eddine Melkemi, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2015 |
| ISBN/ISSN/EAN : | TINF/74 |
| Format : | 1 vol. (112 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
L'appariement de formes est un sujet important dans la vision par ordinateur, il étudie la mesure de similarité entre les formes, il représente un composant essentiel dans la recherche de formes, la reconnaissance, la classification et le recalage. Dans ce travail, nous avons essayé d’aborder l’appariement de formes comme un problème d'optimisation, à l'aide des algorithmes évolutionnaires quantiques qui ont démontré le pouvoir d'être une amélioration majeure par rapport aux algorithmes évolutionnaires classiques. Nous proposons de combiner le descripteur shape context avec les algorithmes génétiques quantiques afin de définir une nouvelle approche d’appariement et de recherche de formes. L’appariement de formes avec shape context est basé sur l'idée de trouver la meilleure correspondance entre deux ensembles de points échantillonnés à partir des deux formes. Notre approche proposée utilise les algorithmes génétiques quantiques pour trouver la meilleure configuration de points afin d'obtenir le meilleur appariement possible entre les deux formes. Notre algorithme proposé (Quantum Shape Context) est également utilisé pour résoudre une des faiblesses de shape context, sa faible invariance à la rotation et le retournement, où nous utilisons les algorithmes génétiques quantiques pour estimer la meilleure orientation de la forme cible qui permet d’obtenir le meilleur appariement pour les formes avec des rotations et retournements. Les résultats expérimentaux ont montré la supériorité de notre algorithme proposé dans les tâches d’appariement et de recherche de formes par rapport au shape context et d'autres méthodes d'appariement de formes contre divers types de tests. |
| Sommaire : |
Introduction générale 1 1 Informatique quantique 4 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Mécanique quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Espace de Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.2 Notation de Dirac . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3 Postulats de la mécanique quantique . . . . . . . . . . . . . . . . . 7 1.3 Notions de l'informatique quantique . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 Bit quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2 Réalisation physique d'un bit quantique . . . . . . . . . . . . . . . 9 1.3.3 Registre quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.4 Principes de l'informatique quantique . . . . . . . . . . . . . . . . . 12 1.3.5 Mesure quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.6 Calcul quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.7 Portes quantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.8 Circuits quantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3.9 Cryptographie quantique . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.10 Correction d'erreurs quantiques . . . . . . . . . . . . . . . . . . . . 20 1.3.11 Téléportation quantique . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.12 Critéres de la réalisation d'un ordinateur Quantique . . . . . . . . . 22 1.3.13 Algorithmes quantiques . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.14 Ordinateurs quantiques . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2 Algorithmes évolutionnaires quantiques 28 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Algorithmes évolutionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1 Classes des algorithmes évolutionnaires . . . . . . . . . . . . . . . . 30 2.2.2 Principes des algorithmes évolutionnaires . . . . . . . . . . . . . . . 31 2.3 Principes des algorithmes évolutionnaires quantiques . . . . . . . . . . . . 34 2.3.1 Représentation quantique dans les AEQs . . . . . . . . . . . . . . . 35 2.3.2 Observation dans les AEQs . . . . . . . . . . . . . . . . . . . . . . 36 2.3.3 Opérations de mise ?a jour . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.4 Structure générale des AEQs . . . . . . . . . . . . . . . . . . . . . . 39 2.3.5 Types des AEQs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.3.6 Caractéristiques des AEQs . . . . . . . . . . . . . . . . . . . . . . . 42 2.3.7 Renforcement et Diversi?cation dans les AEQs . . . . . . . . . . . . 43 2.3.8 Avantages des AEQs . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3 Decripteurs et mesures de similarité 45 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Quelques dé?nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3 Paramétres de forme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.1 Centre de gravité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.2 Axe de moindre inertie . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.3 énergie de pliage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.4 Excentricité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.5 Rapport de circularité . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.6 Rectangularit?e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.7 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.8 Solidité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.9 Nombre d'Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.10 Pro?ls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3.11 Rapport de la surface du trou . . . . . . . . . . . . . . . . . . . . . 51 3.3.12 Invariance aux transformations géométriques . . . . . . . . . . . . . 51 3.4 Descripteurs de formes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.4.1 Descripteurs basés région . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4.2 Descripteurs basés contour . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.3 Ensemble ?ni de points . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4.4 L'invariance et la résistance des descripteurs de forme . . . . . . . . 60 3.5 Mesures de similarité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.5.1 Distance métrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.5.2 Distance non métrique . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.6 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6.1 Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6.2 Transformation rigide . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6.3 Similitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6.4 Transformation a?ne . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.6.5 Transformation projective . . . . . . . . . . . . . . . . . . . . . . . 67 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4 Approche évolutionnaire quantique pour l'appariement de formes 69 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.2 Principes de l'algorithme évolutionnaire quantique pour l'appariement de formes . . . . . . . . 70 4.2.1 Descripteur de forme shape context . . . . . . . . . . . . . . . . . . 70 4.2.2 Représentation quantique . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.3 Fonction objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.2.4 Stratégie de recherche . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.2.5 Algorithme QSC propos?e . . . . . . . . . . . . . . . . . . . . . . . . 77 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5 Evaluation de l'approche proposée 82 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2 Expérimentations et résultats . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2.1 Matériels et logiciels utilisés . . . . . . . . . . . . . . . . . . . . . . 83 5.2.2 Protocole d'évaluation . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.2.3 Etude de l’eut de th^eta sur la convergence de l'algorithme . . . . . 84 5.2.4 Etude de l’eut de nombre d'individus sur la convergence de l'algorithme .. . . . . . . . 86 5.2.5 Recherche d'images . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.2.6 Temps de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Conclusion génerale 105 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/1229 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/74 | Mémoire de magister | bibliothèque sciences exactes | Consultable |
