Hachage géométrique: Algorithmes efficaces pour la reconnaissance et la correspondance d'images

Par Fouad Sabry

Qu'est-ce que le hachage géométrique

En informatique, le hachage géométrique est une méthode permettant de trouver efficacement des objets bidimensionnels représentés par des points discrets ayant subi une transformation affine, via des extensions. existent pour d’autres représentations et transformations d’objets. Dans une étape hors ligne, les objets sont codés en traitant chaque paire de points comme une base géométrique. Les points restants peuvent être représentés de manière invariante par rapport à cette base à l'aide de deux paramètres. Pour chaque point, ses coordonnées transformées quantifiées sont stockées dans la table de hachage sous forme de clé, et les indices des points de base sous forme de valeur. Ensuite, une nouvelle paire de points de base est sélectionnée et le processus est répété. Dans l'étape en ligne (reconnaissance), des paires de points de données sélectionnées au hasard sont considérées comme bases candidates. Pour chaque base candidate, les points de données restants sont codés en fonction de la base et les correspondances possibles de l'objet sont trouvées dans le tableau précédemment construit. La base candidate est acceptée si un nombre suffisamment grand de points de données indexent une base objet cohérente.

Comment vous en bénéficierez

(I) Insights, et validations sur les sujets suivants :

Chapitre 1 : Hachage géométrique

Chapitre 2 : Géométrie analytique

Chapitre 3 : Système de coordonnées cartésiennes

Chapitre 4 : Infographie 2D

Chapitre 5 : Système de coordonnées

Chapitre 6 : Translation (géométrie)

Chapitre 7 : Transformation de Hough

Chapitre 8 : Transformation de caractéristiques invariantes à l'échelle

Chapitre 9 : Homographie

Chapitre 10 : Apprentissage de caractéristiques géométriques

(II) Répondre aux principales questions du public sur hachage géométrique.

(III) Exemples concrets d'utilisation du hachage géométrique dans de nombreux domaines.

À qui s'adresse ce livre

Professionnels, étudiants de premier cycle et des cycles supérieurs, passionnés, amateurs et ceux qui souhaitent aller au-delà des connaissances ou des informations de base pour tout type de hachage géométrique.

• Langue: Français
• Éditeur: Un Milliard De Personnes Informées [French]
• Date de sortie: 11 mai 2024

Aperçu du livre

Hachage géométrique

Algorithmes efficaces pour la reconnaissance et la correspondance d'images

Fouad Sabry est l'ancien responsable régional du développement commercial pour les applications chez Hewlett Packard pour l'Europe du Sud, le Moyen-Orient et l'Afrique. Fouad est titulaire d'un baccalauréat ès sciences des systèmes informatiques et du contrôle automatique, d'une double maîtrise, d'une maîtrise en administration des affaires et d'une maîtrise en gestion des technologies de l'information de l'Université de Melbourne en Australie. Fouad a plus de 25 ans d'expérience dans les technologies de l'information et de la communication, travaillant dans des entreprises locales, régionales et internationales, telles que Vodafone et des machines commerciales internationales. Actuellement, Fouad est un entrepreneur, auteur, futuriste, axé sur les technologies émergentes et les solutions industrielles, et fondateur de l'initiative One billion knowledge.

Un milliard de connaissances

Hachage géométrique

Algorithmes efficaces pour la reconnaissance et la correspondance d'images

Fouad Sabry

Copyright

Hachage © géométrique 2024 par Fouad Sabry. Tous droits réservés.

Aucune partie de ce livre ne peut être reproduite sous quelque forme que ce soit ou par quelque moyen électronique ou mécanique que ce soit, y compris les systèmes de stockage et de récupération d'informations, sans l'autorisation écrite de l'auteur. La seule exception est celle d'un critique, qui peut citer de courts extraits dans une critique.

Couverture conçue par Fouad Sabry.

Bien que toutes les précautions aient été prises dans la préparation de ce livre, les auteurs et les éditeurs n'assument aucune responsabilité pour les erreurs ou omissions, ou pour les dommages résultant de l'utilisation des informations contenues dans ce livre.

Table des matières

Chapitre 1 : Hachage géométrique

Chapitre 2 : Géométrie analytique

Chapitre 3 : Système de coordonnées cartésiennes

Chapitre 4 : Infographie 2D

Chapitre 5 : Système de coordonnées

Chapitre 6 : Translation (géométrie)

Chapitre 7 : Transformation de Hough

Chapitre 8 : Transformation de caractéristique invariante à l'échelle

Chapitre 9 : Homographie

Chapitre 10 : Apprentissage des caractéristiques géométriques

Appendice

À propos de l'auteur

Chapitre 1 : Hachage géométrique

Il existe des expansions dans diverses représentations et transformations d'objets, mais en informatique, le hachage géométrique est utilisé pour localiser efficacement des objets en deux dimensions représentés par des points discrets qui ont subi une transformation affine. Hors ligne, chaque paire de points est utilisée comme base géométrique pour encoder les objets. Deux paramètres permettent une représentation invariante de base des points restants. La table de hachage conserve une paire de valeurs : les indices des points de base pour chaque clé et les coordonnées converties quantifiées pour chaque valeur. La procédure est ensuite répétée, cette fois en utilisant un ensemble différent de points de base. Dans la phase de (reconnaissance) en ligne, des appariements arbitraires de points de données sont évalués comme des fondations potentielles. Afin de trouver des correspondances réalisables entre l'objet et chaque base candidate, les points de données restants sont codés en fonction de la base. Si une fraction suffisamment grande des points de données pointe vers une base d'objet constant, alors la base candidate est acceptée.

En vision par ordinateur, le hachage géométrique a été proposé pour la première fois pour la reconnaissance d'objets 2D et 3D, la reconnaissance d'objets utilisant le hachage géométrique.

Disons que nous voulons vérifier si une image de modèle peut être vue dans une image d'entrée.

Le hachage géométrique est une méthode qui peut être utilisée pour y parvenir.

La technique peut être utilisée pour identifier un seul objet parmi plusieurs dans une base de données, dans ce scénario, la table de hachage doit garder une trace à la fois des données de pose et de l'index de base du modèle objet.

Afin de garder l'exemple simple, nous utiliserons simplement quelques caractéristiques ponctuelles et supposerons que leurs descriptions proviennent uniquement de leurs coordonnées (en pratique, des descripteurs locaux tels que SIFT pourraient être utilisés pour l'indexation).

Découvrez les caractéristiques déterminantes du modèle.

Supposons que 5 points de caractéristique se trouvent dans l'image du modèle avec les coordonnées (12,17); (45,13); (40,46); (20,35); (35,25) , voir la photographie.

Fournir une base pour décrire les coordonnées des points de caractéristique.

Les deux points qui fournissent la base d'une transformation de similarité dans l'espace bidimensionnel.

Le point de départ est situé à mi-chemin de la ligne qui relie les deux points (P1, P2), le P4 de notre étude de cas, l' x' axe est dirigé vers l'un d'eux, le y' est orthogonal et passe par l'origine.

L'échelle est choisie de telle sorte que la valeur absolue de pour x' les deux points de base soit 1.

Expliquez où en sont les choses par rapport à cette fondation, c'est-à-dire

calculer les transformations vers les nouveaux axes.

Pour rendre la reconnaissance plus résistante au bruit, les coordonnées doivent être discrétisées, un bac de 0,25 unité est utilisé.

Nous obtenons ainsi les coordonnées (-0.75,-1.25); (1.00,0.00); (-0.50,1.25); (-1.00,0.00); (0.00,0.25)

Utilisez une table de hachage avec les entités comme index pour stocker la fondation (uniquement les coordonnées transformées dans ce cas). Nombre d'éléments à stocker avec la paire de base s'il y en a plus de deux à mettre en correspondance.

Passez à une nouvelle paire de base et continuez à partir de là (étape 2). Pour faire face aux occlusions, c'est essentiel. Toutes les paires qui ne sont pas linéaires devraient idéalement être répertoriées. Après deux itérations, dans lesquelles la paire (P1, P3) est choisie, nous présentons la table de hachage.

Table de hachage :

La plupart des tables de hachage ne permettent pas d'associer des clés en double à des valeurs distinctes.

Ainsi, dans la vraie vie, on n'encodera pas les clés de base (1.0, 0.0) et (-1.0, (table de hachage, valeur de 0).

Localisez les points d'attrait visuel dans l'image donnée.

Choisissez un point de départ aléatoire. L'image d'entrée ne contient probablement pas l'élément cible s'il n'y a pas de base arbitraire adéquate pour déterminer s'il est présent ou non.

Détailler les emplacements des points caractéristiques du nouveau système de coordonnées. Effectuez la quantification traditionnelle des coordonnées résultantes.

Vérifiez les entités ponctuelles converties de l'image d'entrée par rapport à la table de hachage. Dans le cas où les entités ponctuelles sont identiques ou très similaires, le nombre de la base pertinente doit être augmenté (et le type d'objet, le cas échéant).

Si le nombre d'une certaine base est supérieur à un certain seuil, il est probable que cette base corresponde à une base d'image sélectionnée à l'étape 2. Pour ce faire, nous convertissons d'abord le système de coordonnées de l'image en celui du modèle (pour l'objet fictif). Si cela fonctionne, l'article est localisé. Si ce n'est pas le cas, revenez à l'étape précédente.

Il semble que les seules transformations que cette approche puisse gérer sont celles de la taille, de la position et de l'orientation. Cependant, l'élément peut déjà exister dans l'image fournie dans un format d'image miroir. Par conséquent, l'objet doit également être découvrable par hachage géométrique. Les objets en miroir peuvent être identifiés de deux manières différentes.

Faites en sorte que le côté gauche du graphique vectoriel soit positif et le côté droit négatif. Pour obtenir le même résultat en multipliant par x, il suffit d'ajouter -1.

Utilisez une triade comme point de départ. Cela permet d'identifier les reflets (ou objets). Une autre méthode de hachage géométrique utilise un ensemble de trois points comme base.

Le hachage fonctionne de la même manière pour les données de dimension supérieure, comme indiqué ci-dessus. Trois points sont nécessaires pour la base des données tridimensionnelles. L'axe des x est défini par les deux premiers points et l'axe des y par le troisième (avec le premier point). En utilisant la règle de la main droite, un axe peut être construit et l'axe z lui sera perpendiculaire. La base résultante est sensible à l'ordre dans lequel les points sont saisis.

{Fin du chapitre 1}

Chapitre 2 : Géométrie analytique

La géométrie analytique, souvent appelée géométrie de coordonnées ou géométrie cartésienne, est une branche des mathématiques qui s'intéresse à l'étude de la géométrie d'un point de vue cartésien. La géométrie synthétique est à l'opposé de cela.

La physique, l'ingénierie, l'aviation, les fusées, les sciences spatiales et les voyages spatiaux utilisent tous la géométrie analytique. Elle est à la base de plusieurs branches de la géométrie contemporaine, telles que la géométrie algébrique, différentielle, discrète et computationnelle.

Lorsque vous travaillez avec des équations impliquant des plans, des lignes droites et des cercles, le système de coordonnées cartésiennes est généralement utilisé. En géométrie, le plan euclidien bidimensionnel et l'espace euclidien tridimensionnel sont étudiés. La géométrie analytique, telle qu'elle est généralement définie et enseignée dans les manuels, s'intéresse à la création et à la représentation de formes géométriques au sens numérique, et à l'extraction d'informations numériques à partir de ces représentations. L'axiome de Cantor-Dedekind garantit que les calculs dans la géométrie du continuum linéaire peuvent être effectués en utilisant uniquement l'algèbre des nombres réels.

Il a été soutenu que le mathématicien grec Menaechmus a développé la géométrie analytique en raison de son utilisation d'une technique qui ressemblait à l'utilisation de coordonnées pour résoudre des problèmes et prouver des théorèmes.

Le mathématicien persan du XIe siècle Omar Khayyam a vu une forte relation entre la géométrie et l'algèbre et