Détection de fonctionnalités, partie 3 : Détection de Harris Corner

Détection de fonctionnalités est un domaine de la vision par ordinateur qui se concentre sur l’utilisation d’outils pour détecter les régions d’intérêt dans les images. Un aspect important de la plupart des algorithmes de détection de fonctionnalités est qu’ils n’utilisent pas d’apprentissage automatique sous le capot, ce qui rend les résultats plus interprétables et même plus rapides dans certains cas.

Dans les deux articles précédents de cette série, nous avons examiné les opérateurs les plus populaires pour détecter les bords d’une image : Sobel, Scharr, Laplacienavec le Gaussienne utilisé pour le lissage de l’image. Sous une forme ou une autre, ces opérateurs utilisaient des dérivés d’image et des gradients cachés, représentés par des noyaux convolutifs.

Comme pour les bords, en analyse d’images, un autre type de région locale est souvent exploré : les coins. Les coins apparaissent plus rarement que les bords et indiquent généralement un changement de direction de la bordure d’un objet ou la fin d’un objet et le début d’un autre. Les coins sont plus rares à trouver et fournissent des informations plus précieuses.

Exemple

Imaginez que vous collectionnez un puzzle 2D. Ce que la plupart des gens font au début, c’est trouver une pièce avec une partie d’image contenant la bordure (bord) d’un objet. Pourquoi? Parce que de cette façon, il est plus facile d’identifier les pièces adjacentes, puisque le nombre de pièces partageant un bord d’objet similaire est minime.

Nous pouvons aller encore plus loin et nous concentrer sur la sélection non pas des bords mais des coins – une région dans laquelle un objet change la direction de ses bords. Ces pièces sont encore plus rares que de simples bords et permettent une recherche encore plus facile d’autres fragments adjacents en raison de leur forme unique.

Par exemple, dans le puzzle ci-dessous, il y a 6 arêtes (B2, B3, B4, D2, D3et D4) et seulement 1 coin (C5). En choisissant le coin dès le départ, il devient plus facile de localiser sa position car il est plus rare que les carres.

Le but de cet article est de comprendre comment détecter les coins. Pour ce faire, nous comprendrons les détails de l’algorithme de détection des coins de Harris – l’une des méthodes les plus simples et les plus populaires développées en 1988.

Idée

Prenons trois types de régions : plat, bordet coin. Nous avons déjà montré ci-dessus la structure de ces régions. Notre objectif sera de comprendre la répartition des gradients dans ces trois cas.

Au cours de notre analyse, nous construirons également une ellipse contenant la majorité des points tracés. Comme nous le verrons, sa forme fournira des indications fortes sur le type de région à laquelle nous avons affaire.

Région plate

Une région plate est le cas le plus simple. Habituellement, la région entière de l’image a presque les mêmes valeurs d’intensité, ce qui rend les valeurs de gradient sur les axes X et Y mineures et centrées autour de 0.

En prenant les points de dégradé (Gₓ, Gᵧ) de l’exemple d’image plate ci-dessus, nous pouvons tracer leur distribution, qui ressemble à ci-dessous :

Nous pouvons maintenant construire une ellipse autour des points tracés ayant un centre en (0, 0). On peut alors identifier ses deux axes principaux :

• Le axe majeur le long duquel l’ellipse est étirée au maximum.
• Le petit axe le long duquel l’ellipse atteint son étendue minimale.

Dans le cas de la région plate, il peut être difficile de différencier visuellement les axes majeurs et mineurs, car l’ellipse a tendance à avoir une forme circulaire, comme dans notre situation.

Néanmoins, pour chacun des deux axes principaux, on peut alors calculer les rayons d’ellipse λ₁ et λ₂. Comme le montre l’image ci-dessus, ils sont presque égaux et ont de petites valeurs relatives.

Région périphérique

Pour la région marginale, l’intensité change uniquement dans la zone marginale. En dehors du bord, l’intensité reste presque la même. Compte tenu de cela, la plupart des points de dégradé sont toujours centrés autour de (0, 0).

Cependant, pour une petite partie autour de la zone périphérique, les valeurs de gradient peuvent changer radicalement dans les deux sens. Dans l’exemple d’image ci-dessus, le bord est diagonal et nous pouvons voir des changements dans les deux directions. Ainsi, la distribution du gradient est asymétrique dans la direction diagonale, comme indiqué ci-dessous :

Pour les régions marginales, l’ellipse tracée est généralement inclinée dans une direction et présente des rayons λ₁ et λ₂ très différents.

Région d’angle

Pour les virages, la plupart des valeurs d’intensité en dehors des virages restent les mêmes ; ainsi, la distribution pour la majorité des points est toujours située près du centre (0, 0).

Si nous regardons la structure en coin, nous pouvons la considérer grossièrement comme une intersection de deux arêtes ayant deux directions différentes. Pour les arêtes, nous avons déjà expliqué dans la section précédente que la distribution va dans la même direction soit en X, soit en Y, ou dans les deux directions.

En ayant deux bords pour le coin, nous nous retrouvons avec deux spectres de points différents croissant dans deux directions différentes à partir du centre. Un exemple est présenté ci-dessous.

Enfin, si nous construisons une ellipse autour de cette distribution, nous remarquerons qu’elle est plus grande que dans les cas plat et bord. Nous pouvons différencier ce résultat en mesurant λ₁ et λ₂, qui dans ce scénario prendront des valeurs beaucoup plus grandes.

Visualisation

Nous venons de voir trois scénarios dans lesquels λ prenait des valeurs différentes. Pour mieux visualiser les résultats, nous pouvons construire un diagramme ci-dessous :

Formule

Pour pouvoir classer une région dans l’une des trois zones, une formule ci-dessous est couramment utilisée pour estimer le coefficient R :

R = λ₁ ⋅ λ₂ – k ⋅ (λ₁ + λ₂)² , où 0,04 ≤ k ≤ 0,06

Sur la base de la valeur R, nous pouvons classer la région de l’image :

• R < 0 – région marginale
• R ~ 0 – région plate
• R > 0 – région de coin

OuvrirCV

La détection Harris Corner peut être facilement implémentée dans OpenCV à l’aide de la fonction cv2.CornerHarris. Voyons dans l’exemple ci-dessous comment cela peut être réalisé.

Voici l’image d’entrée avec laquelle nous allons travailler :

Tout d’abord, importons les bibliothèques nécessaires.

import numpy as np
import cv2
import matplotlib.pyplot as plt

Nous allons convertir l’image d’entrée au format niveaux de gris, car le détecteur Harris fonctionne avec les intensités de pixels. Il est également nécessaire de convertir le format d’image en float32, car les valeurs calculées associées aux pixels peuvent dépasser les limites. [0, 255].

path = 'data/input/shapes.png'
image = cv2.imread(path)
grayscale_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
grayscale_image = np.float32(grayscale_image)

Nous pouvons maintenant appliquer le filtre Harris. Le cv2.cornerHarris la fonction prend quatre paramètres :

• image en niveaux de gris – saisissez une image en niveaux de gris au format float32.
• taille de bloc (= 2) – définit les dimensions du bloc de pixels au voisinage du pixel cible considéré pour la détection de coin.
• ktaille (= 3) – la dimension du filtre Sobel utilisé pour calculer les dérivées.
• k (= 0,04) – coefficient dans la formule utilisée pour calculer la valeur de R.

R = cv2.cornerHarris(grayscale_image, 2, 3, 0.04)
R = cv2.dilate(R, None)

La fonction cv2.cornerHarris renvoie une matrice des dimensions exactes de l’image en niveaux de gris d’origine. Ses valeurs peuvent être bien en dehors de la plage normale [0, 255]. Pour chaque pixel, cette matrice contient la valeur du coefficient R que nous avons examinée ci-dessus.

Le cv2.dilate est un opérateur morphologique qui peut éventuellement être utilisé immédiatement après pour mieux regrouper visuellement les coins locaux.

Une technique courante consiste à définir un seuil en dessous duquel les pixels sont considérés comme des coins. Par exemple, nous pouvons considérer tous les pixels de l’image comme des coins dont la valeur R est supérieure à la valeur R globale maximale divisée par 100. Dans notre exemple, nous attribuons à ces pixels la couleur rouge (0, 0, 255).

Pour visualiser une image, nous devons la convertir au format RVB.

image[R > 0.01 * R.max()] = [0, 0, 255]
image_rgb = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)

Enfin, nous utilisons maplotlib pour afficher l’image de sortie.

plt.figure(figsize=(10, 8))
plt.imshow(image_rgb)
plt.title('Harris Corner Detection')
plt.axis('off')
plt.tight_layout()
plt.show()

Voici le résultat :

Conclusion

Dans cet article, nous avons examiné une méthode robuste pour déterminer si une région d’image est un coin. La formule présentée pour estimer le coefficient R fonctionne bien dans la grande majorité des cas.

Dans la vraie vie, il existe un besoin courant d’exécuter un classificateur de contours pour une image entière. Construire une ellipse autour des points de gradient et estimer le coefficient R à chaque fois nécessite beaucoup de ressources, c’est pourquoi des techniques d’optimisation plus avancées sont utilisées pour accélérer le processus. Néanmoins, ils s’appuient en grande partie sur l’intuition que nous avons étudiée ici.

Ressources

Toutes les images, sauf indication contraire, sont de l’auteur.