Deepanshu Tyagi

Follow

SIFT signifie Scale-Invariant Feature Transform et a été présenté pour la première fois en 2004 par D.Lowe, Université de la Colombie-Britannique. SIFT est l’invariance à l’échelle et à la rotation de l’image. Cet algorithme est breveté, donc cet algorithme est inclus dans le module Non libre d’OpenCV.

Les principaux avantages de SIFT sont

• Localité:les caractéristiques sont locales, donc robustes à l’occlusion et à l’encombrement (pas de segmentation préalable)
• Caractère distinctif: les caractéristiques individuelles peuvent être associées à une grande base de données d’objets
• Quantité: de nombreuses fonctionnalités peuvent être générées même pour de petits objets
• Efficacité: performances proches des performances en temps réel
• Extensibilité: peut facilement être étendue à un large éventail de types de fonctionnalités différents, chacun ajoutant de la robustesse

Cela fait partie d’une détection et d’une correspondance de fonctionnalités de la série 7. D’autres articles inclus

• Introduction À La Détection et à la Correspondance des Caractéristiques
• Introduction au Détecteur de Coin Harris
• Introduction au SURF (Caractéristiques Robustes Accélérées)
• Introduction au FAST (Caractéristiques du Test de Segment Accéléré)
• Introduction au BRIEF (Caractéristiques Élémentaires Indépendantes Robustes Binaires)
• Introduction à ORB (Brève Orientée RAPIDE et Tournée)

SIFT est un algorithme assez impliqué. Il y a principalement quatre étapes impliquées dans l’algorithme SIFT. Nous les verrons un par un.

• Sélection des pics d’espace d’échelle: Emplacement potentiel pour trouver des fonctionnalités.
• Localisation des points clés : Localisation précise des points clés des entités.
• Affectation d’orientation : Attribution d’une orientation aux points clés.
• Descripteur de points clés : Décrivant les points clés comme un vecteur de dimension élevée.
• Correspondance de points clés

Sélection de pics d’espace d’échelle

Les objets du monde réel n’ont de sens qu’à une certaine échelle. Vous pourriez voir un cube de sucre parfaitement sur une table. Mais si vous regardez toute la voie lactée, elle n’existe tout simplement pas. Cette nature multi-échelle des objets est assez courante dans la nature. Et un espace à l’échelle tente de reproduire ce concept sur des images numériques.

L’espace d’échelle d’une image est une fonction L(x, y, σ) qui est produite à partir de la convolution d’un noyau gaussien (Flou) à différentes échelles avec l’image d’entrée. Échelle – l’espace est séparé en octaves et le nombre d’octaves et d’échelle dépend de la taille de l’image originale. Nous générons donc plusieurs octaves de l’image originale. La taille de l’image de chaque octave est la moitié de la précédente.

Flou

Au cours d’une octave, les images sont progressivement floues à l’aide de l’opérateur de flou gaussien. Mathématiquement, le ”flou » est appelé la convolution de l’opérateur gaussien et de l’image. Le flou gaussien a une expression ou un « opérateur » particulier qui est appliqué à chaque pixel. Ce qui en résulte est l’image floue.

G est l’opérateur de flou gaussien et I est une image. Alors que x, y sont les coordonnées d’emplacement et σ est le paramètre « échelle ». Pensez-y comme la quantité de flou. Plus la valeur, plus le flou.

DOG (Différence de noyau gaussien)

Maintenant, nous utilisons ces images floues pour générer un autre ensemble d’images, la Différence de Gaussiens (chien). Ces images de chien sont idéales pour découvrir des points clés intéressants dans l’image. La différence de Gaussienne est obtenue comme la différence de flou gaussien d’une image avec deux σ différentes, soit σ et kσ. Ce processus est effectué pour différentes octaves de l’image dans la pyramide Gaussienne. Il est représenté dans l’image ci-dessous:

Trouver des points clés

Jusqu’à présent, nous avons généré un espace d’échelle et utilisé l’espace d’échelle pour calculer la différence de Gaussiens. Ceux-ci sont ensuite utilisés pour calculer le Laplacien d’approximations gaussiennes qui sont invariantes à l’échelle.

Un pixel dans une image est comparé à ses 8 voisins ainsi qu’à 9 pixels dans l’échelle suivante et à 9 pixels dans les échelles précédentes. De cette façon, un total de 26 contrôles sont effectués. S’il s’agit d’un extrema local, c’est un point clé potentiel. Cela signifie essentiellement que le point clé est le mieux représenté dans cette échelle.

Localisation des points clés

Les points clés générés à l’étape précédente produisent beaucoup de points clés. Certains d’entre eux se trouvent le long d’un bord, ou ils n’ont pas assez de contraste. Dans les deux cas, ils ne sont pas aussi utiles que les fonctionnalités. Alors on s’en débarrasse. L’approche est similaire à celle utilisée dans le détecteur de coin Harris pour supprimer les caractéristiques de bord. Pour les caractéristiques à faible contraste, nous vérifions simplement leurs intensités.

Ils ont utilisé l’expansion de l’espace d’échelle de la série de Taylor pour obtenir une localisation plus précise des extrema, et si l’intensité à cet extrema est inférieure à une valeur seuil (0,03 selon l’article), elle est rejetée. Le chien a une réponse plus élevée pour les bords, donc les bords doivent également être enlevés. Ils ont utilisé une matrice Hessienne 2×2 (H) pour calculer la courbure principale.

Affectation d’orientation

Nous avons maintenant des points clés légitimes. Ils ont été testés pour être stables. Nous connaissons déjà l’échelle à laquelle le point clé a été détecté (c’est la même que l’échelle de l’image floue). Nous avons donc une invariance d’échelle. La prochaine chose est d’affecter une orientation à chaque point clé pour le rendre invariant en rotation.

Un voisinage est pris autour de l’emplacement du point clé en fonction de l’échelle, et l’amplitude et la direction du gradient sont calculées dans cette région. Un histogramme d’orientation avec 36 bacs couvrant 360 degrés est créé. Disons que la direction du gradient à un certain point (dans la « région de collecte d’orientation ») est de 18,759 degrés, puis elle ira dans le bac à 10-19 degrés. Et la « quantité » qui est ajoutée au bac est proportionnelle à l’ampleur du gradient à ce point. Une fois que vous avez fait cela pour tous les pixels autour du point clé, l’histogramme aura un pic à un moment donné.

Le pic le plus élevé de l’histogramme est pris et tout pic supérieur à 80% de celui-ci est également pris en compte pour calculer l’orientation. Il crée des points clés avec le même emplacement et la même échelle, mais des directions différentes. Il contribue à la stabilité de l’appariement.

Descripteur de point clé

À ce stade, chaque point clé a un emplacement, une échelle, une orientation. Ensuite, il s’agit de calculer un descripteur pour la région d’image locale sur chaque point clé qui est très distinctif et invariant autant que possible aux variations telles que les changements de point de vue et d’éclairage.

Pour ce faire, une fenêtre 16×16 autour du point clé est prise. Il est divisé en 16 sous-blocs de taille 4×4.

For each sub-block, 8 bin orientation histogram is created.

So 4 X 4 descriptors over 16 X 16 sample array were used in practice. 4 X 4 X 8 directions give 128 bin values. It is represented as a feature vector to form keypoint descriptor. Ce vecteur de fonctionnalités introduit quelques complications. Nous devons nous en débarrasser avant de finaliser l’empreinte digitale.

1. Dépendance à la rotation Le vecteur caractéristique utilise des orientations de gradient. Clairement, si vous faites pivoter l’image, tout change. Toutes les orientations de gradient changent également. Pour obtenir l’indépendance de rotation, la rotation du point clé est soustraite de chaque orientation. Ainsi, chaque orientation de gradient est relative à l’orientation du point clé.
2. Dépendance à l’éclairage Si nous seuils des nombres qui sont grands, nous pouvons atteindre l’indépendance de l’éclairage. Ainsi, tout nombre (sur les 128) supérieur à 0,2 est changé en 0,2. Ce vecteur caractéristique résultant est à nouveau normalisé. Et maintenant, vous avez un vecteur de fonction indépendant de l’éclairage!

Correspondance des points clés

Les points clés entre deux images sont appariés en identifiant leurs voisins les plus proches. Mais dans certains cas, le deuxième match le plus proche peut être très proche du premier. Cela peut arriver à cause du bruit ou d’autres raisons. Dans ce cas, le rapport de la distance la plus proche à la deuxième distance la plus proche est pris. S’il est supérieur à 0,8, ils sont rejetés. Il élimine environ 90% des fausses correspondances tout en rejetant seulement 5% des correspondances correctes, selon le document.

Implémentation

J’ai pu implémenter sift en utilisant OpenCV(3.4). Voici comment je l’ai fait:

Lien Github pour le code: https://github.com/deepanshut041/feature-detection/tree/master/sift