Détection des contours - Edge detection

La détection des contours comprend une variété de méthodes mathématiques qui visent à identifier les contours , les courbes d'une image numérique au niveau desquelles la luminosité de l' image change fortement ou, plus formellement, présente des discontinuités . Le même problème de recherche de discontinuités dans des signaux unidimensionnels est connu sous le nom de détection de pas et le problème de recherche de discontinuités de signal dans le temps est connu sous le nom de détection de changement . La détection des contours est un outil fondamental dans le traitement d'images , la vision industrielle et la vision par ordinateur , en particulier dans les domaines de la détection et de l' extraction de caractéristiques .

Motivations

Détection des contours astucieuse appliquée à une photo

Le but de la détection des changements brusques de luminosité de l'image est de capturer des événements importants et des changements dans les propriétés du monde. On peut montrer que sous des hypothèses assez générales pour un modèle de formation d'image, les discontinuités de luminosité de l'image sont susceptibles de correspondre à :

  • discontinuités en profondeur,
  • discontinuités dans l'orientation de la surface,
  • changements dans les propriétés des matériaux et
  • variations de l'éclairage de la scène.

Dans le cas idéal, le résultat de l'application d'un détecteur de contour à une image peut conduire à un ensemble de courbes connectées qui indiquent les limites des objets, les limites des marquages ​​de surface ainsi que des courbes qui correspondent à des discontinuités dans l'orientation de la surface. Ainsi, l'application d'un algorithme de détection de contour à une image peut réduire considérablement la quantité de données à traiter et peut donc filtrer des informations qui peuvent être considérées comme moins pertinentes, tout en préservant les propriétés structurelles importantes d'une image. Si l'étape de détection de contour est réussie, la tâche ultérieure d'interprétation du contenu d'informations dans l'image originale peut donc être sensiblement simplifiée. Cependant, il n'est pas toujours possible d'obtenir de tels contours idéaux à partir d'images réelles de complexité modérée.

Les bords extraits d'images non triviales sont souvent entravés par la fragmentation , ce qui signifie que les courbes de bord ne sont pas connectées, des segments de bord manquants ainsi que des faux bords ne correspondant pas à des phénomènes intéressants dans l'image - compliquant ainsi la tâche ultérieure d'interprétation des données d'image.

La détection des contours est l'une des étapes fondamentales du traitement d'images, de l'analyse d'images, de la reconnaissance de formes d'images et des techniques de vision par ordinateur.

Propriétés de bord

Les bords extraits d'une image bidimensionnelle d'une scène tridimensionnelle peuvent être classés comme dépendants du point de vue ou indépendants du point de vue. Un bord indépendant du point de vue reflète généralement les propriétés inhérentes des objets tridimensionnels, telles que les marques de surface et la forme de la surface. Un bord dépendant d' un point de vue peut changer au fur et à mesure que le point de vue change et reflète généralement la géométrie de la scène, comme des objets qui s'obstruent les uns les autres.

Un bord typique pourrait par exemple être la frontière entre un bloc de couleur rouge et un bloc de jaune. En revanche, une ligne (telle qu'elle peut être extraite par un détecteur de crête ) peut être un petit nombre de pixels d'une couleur différente sur un fond autrement immuable. Pour une ligne, il peut donc généralement y avoir un bord de chaque côté de la ligne.

Un modèle de bord simple

Bien que certaines publications aient envisagé la détection de bords de marche idéaux, les bords obtenus à partir d'images naturelles ne sont généralement pas du tout des bords de marche idéaux. Au lieu de cela, ils sont normalement affectés par un ou plusieurs des effets suivants :

Un certain nombre de chercheurs ont utilisé un bord de marche lissé gaussien (une fonction d'erreur) comme extension la plus simple du modèle de bord de marche idéal pour modéliser les effets du flou de bord dans des applications pratiques. Ainsi, une image unidimensionnelle qui a exactement un bord placé sur peut être modélisée comme :

Sur le côté gauche du bord, l'intensité est , et à droite du bord c'est . Le paramètre d'échelle est appelé l'échelle de flou du bord. Idéalement, ce paramètre d'échelle doit être ajusté en fonction de la qualité de l'image pour éviter de détruire les vrais bords de l'image.

Pourquoi c'est une tâche non triviale

Pour illustrer pourquoi la détection des contours n'est pas une tâche triviale, considérons le problème de la détection des contours dans le signal unidimensionnel suivant. Ici, on peut intuitivement dire qu'il doit y avoir un bord entre le 4e et le 5e pixels.

5 7 6 4 152 148 149

Si la différence d'intensité était plus petite entre le 4e et le 5e pixels et si les différences d'intensité entre les pixels voisins adjacents étaient plus élevées, il ne serait pas aussi facile de dire qu'il devrait y avoir un bord dans la région correspondante. De plus, on pourrait soutenir que ce cas est un cas dans lequel il y a plusieurs bords.

5 7 6 41 113 148 149

Par conséquent, énoncer fermement un seuil spécifique sur l'ampleur du changement d'intensité entre deux pixels voisins doit être pour nous de dire qu'il devrait y avoir un bord entre ces pixels n'est pas toujours simple. En effet, c'est l'une des raisons pour lesquelles la détection des contours peut être un problème non trivial à moins que les objets de la scène ne soient particulièrement simples et que les conditions d'éclairage puissent être bien contrôlées (voir par exemple, les contours extraits de l'image avec la fille au dessus ).

Approches

Il existe de nombreuses méthodes de détection des contours, mais la plupart d'entre elles peuvent être regroupées en deux catégories, basées sur la recherche et basées sur le passage à zéro . Les méthodes basées sur la recherche détectent les bords en calculant d'abord une mesure de la force des bords, généralement une expression dérivée du premier ordre telle que la magnitude du gradient, puis en recherchant les maxima directionnels locaux de la magnitude du gradient à l'aide d'une estimation calculée de l'orientation locale du bord, généralement la direction du gradient. Les méthodes basées sur les passages par zéro recherchent les passages par zéro dans une expression dérivée du second ordre calculée à partir de l'image afin de trouver des bords, généralement les passages par zéro du Laplacien ou les passages par zéro d'une expression différentielle non linéaire. En tant qu'étape de prétraitement jusqu'à la détection des contours, une étape de lissage, typiquement un lissage gaussien , est presque toujours appliquée (voir aussi la réduction du bruit ).

Les méthodes de détection de contour qui ont été publiées diffèrent principalement par les types de filtres de lissage appliqués et la manière dont les mesures de force de contour sont calculées. Comme de nombreuses méthodes de détection de contour reposent sur le calcul de gradients d'image, elles diffèrent également par les types de filtres utilisés pour calculer les estimations de gradient dans les directions x et y .

Une étude d'un certain nombre de différentes méthodes de détection des contours peut être trouvée dans (Ziou et Tabbone 1998) ; voir aussi les articles d'encyclopédie sur la détection des contours dans Encyclopedia of Mathematics et Encyclopedia of Computer Science and Engineering.

Prudent

John Canny a examiné le problème mathématique consistant à dériver un filtre de lissage optimal compte tenu des critères de détection, de localisation et de minimisation des réponses multiples à un seul bord. Il a montré que le filtre optimal compte tenu de ces hypothèses est une somme de quatre termes exponentiels. Il a également montré que ce filtre peut être bien approché par les dérivées du premier ordre des gaussiennes. Canny a également introduit la notion de suppression non maximale, ce qui signifie qu'étant donné les filtres de prélissage, les points de bord sont définis comme des points où la magnitude du gradient suppose un maximum local dans la direction du gradient. La recherche du passage par zéro de la dérivée 2 le long de la direction du gradient a été proposée pour la première fois par Haralick . Il a fallu moins de deux décennies pour trouver une signification variationnelle géométrique moderne pour cet opérateur qui le relie au détecteur de bord Marr-Hildreth (passage à zéro du Laplacien). Cette observation a été présentée par Ron Kimmel et Alfred Bruckstein .

Bien que son travail ait été réalisé au tout début de la vision par ordinateur, le détecteur de bord Canny (y compris ses variantes) est toujours un détecteur de bord à la pointe de la technologie. Les détecteurs de bords qui fonctionnent mieux que le Canny nécessitent généralement des temps de calcul plus longs ou un plus grand nombre de paramètres.

Le détecteur de Canny-Deriche a été dérivé de critères mathématiques similaires à ceux du détecteur de bord de Canny, bien que partant d'un point de vue discret et conduisant ensuite à un ensemble de filtres récursifs pour le lissage de l'image au lieu de filtres exponentiels ou de filtres gaussiens.

Le détecteur de bords différentiel décrit ci-dessous peut être vu comme une reformulation de la méthode de Canny du point de vue des invariants différentiels calculés à partir d'une représentation d'espace d'échelle conduisant à un certain nombre d'avantages en termes d'analyse théorique et de mise en œuvre de sous-pixels. Dans cet aspect, le filtre Log Gabor s'est avéré être un bon choix pour extraire les limites des scènes naturelles.

Autres méthodes de premier ordre

Différents opérateurs de gradient peuvent être appliqués pour estimer les gradients d'image à partir de l'image d'entrée ou d'une version lissée de celle-ci. L'approche la plus simple consiste à utiliser les différences centrales :

correspondant à l'application des masques de filtrage suivants aux données d'image :

L' opérateur Sobel bien connu et antérieur est basé sur les filtres suivants :

Étant donné de telles estimations des dérivées d'image du premier ordre , la magnitude du gradient est alors calculée comme suit :

tandis que l'orientation du gradient peut être estimée comme

D'autres opérateurs de différence du premier ordre pour estimer le gradient d'image ont été proposés dans l' opérateur de Prewitt , la croix de Roberts , l' opérateur de Kayyali et l'opérateur de Frei-Chen .

Il est possible d'étendre la dimension des filtres pour éviter le problème de reconnaissance des contours dans une image à faible SNR. Le coût de cette opération est une perte en terme de résolution. Les exemples sont Extended Prewitt 7×7.

Seuils et liens

Une fois que nous avons calculé une mesure de la force des bords (généralement la magnitude du gradient), l'étape suivante consiste à appliquer un seuil, pour décider si des bords sont présents ou non à un point de l'image. Plus le seuil est bas, plus les bords seront détectés, et le résultat sera de plus en plus sensible au bruit et à la détection de bords de caractéristiques non pertinentes dans l'image. Inversement, un seuil élevé peut manquer des contours subtils ou entraîner des contours fragmentés.

Si le bord est appliqué uniquement à l'image de magnitude du gradient, les bords résultants seront généralement épais et un certain type de post-traitement d'amincissement des bords est nécessaire. Cependant, pour les contours détectés avec une suppression non maximale, les courbes de contour sont fines par définition et les pixels de contour peuvent être liés au polygone de contour par une procédure de liaison de contour (suivi de contour). Sur une grille discrète, l'étape de suppression non maximale peut être mise en œuvre en estimant la direction du gradient à l'aide de dérivées du premier ordre, puis en arrondissant la direction du gradient à des multiples de 45 degrés, et enfin en comparant les valeurs de l'amplitude du gradient dans le gradient estimé direction.

Une approche couramment utilisée pour traiter le problème des seuils appropriés pour le seuillage consiste à utiliser le seuillage avec hystérésis . Cette méthode utilise plusieurs seuils pour trouver des arêtes. Nous commençons par utiliser le seuil supérieur pour trouver le début d'une arête. Une fois que nous avons un point de départ, nous traçons ensuite le chemin du bord à travers l'image pixel par pixel, marquant un bord chaque fois que nous sommes au-dessus du seuil inférieur. Nous arrêtons de marquer notre bord uniquement lorsque la valeur tombe en dessous de notre seuil inférieur. Cette approche suppose que les bords sont susceptibles d'être dans des courbes continues et nous permet de suivre une faible section d'un bord que nous avons vu précédemment, sans signifier que chaque pixel bruyant de l'image est marqué comme un bord. Cependant, nous avons toujours le problème de choisir des paramètres de seuillage appropriés, et les valeurs de seuillage appropriées peuvent varier sur l'image.

Amincissement des bords

L'amincissement des bords est une technique utilisée pour supprimer les points parasites indésirables sur les bords d'une image. Cette technique est utilisée après que l'image a été filtrée pour le bruit (à l'aide d'un filtre médian, gaussien, etc.), l'opérateur de bord a été appliqué (comme ceux décrits ci-dessus, canny ou sobel) pour détecter les bords et après que les bords ont été lissés en utilisant une valeur seuil appropriée. Cela supprime tous les points indésirables et, s'il est appliqué avec soin, donne des éléments de bord épais d'un pixel.

Avantages :

  1. Des bords nets et fins conduisent à une plus grande efficacité dans la reconnaissance d'objets.
  2. Si les transformations de Hough sont utilisées pour détecter les lignes et les ellipses, l'amincissement pourrait donner de bien meilleurs résultats.
  3. Si le bord se trouve être la limite d'une région, alors l'amincissement pourrait facilement donner aux paramètres de l'image comme le périmètre sans beaucoup d'algèbre.

Il existe de nombreux algorithmes populaires utilisés pour ce faire, l'un d'entre eux est décrit ci-dessous :

  1. Choisissez un type de connectivité, comme 8, 6 ou 4.
  2. La connectivité 8 est préférée, où tous les pixels immédiats entourant un pixel particulier sont considérés.
  3. Supprimez les points du nord, du sud, de l'est et de l'ouest.
  4. Faites cela en plusieurs passes, c'est-à-dire après la passe nord, utilisez la même image semi-traitée dans les autres passes et ainsi de suite.
  5. Supprimer un point si :
    Le point n'a pas de voisins au Nord (si vous êtes dans le col nord, et les directions respectives pour les autres cols).
    Le point n'est pas la fin d'une ligne.
    Le point est isolé.
    La suppression des points n'entraînera en aucun cas la déconnexion de ses voisins.
  6. Sinon, gardez le cap.

Le nombre de passes transversales doit être choisi en fonction du niveau de précision souhaité.

Approches de second ordre

Certains opérateurs de détection de contour sont plutôt basés sur des dérivées du second ordre de l'intensité. Cela capture essentiellement le taux de changement du gradient d'intensité. Ainsi, dans le cas continu idéal, la détection des passages par zéro dans la dérivée seconde capture les maxima locaux dans le gradient.

Le premier opérateur de Marr-Hildreth est basé sur la détection des passages par zéro de l'opérateur laplacien appliqué à une image lissée de Gauss. On peut cependant montrer que cet opérateur renverra également de faux bords correspondant aux minima locaux de la magnitude du gradient. De plus, cet opérateur donnera une mauvaise localisation aux bords courbes. Cet opérateur présente donc aujourd'hui un intérêt principalement historique.

Différentiel

Une approche de détection de contours de second ordre plus raffinée qui détecte automatiquement les contours avec une précision inférieure au pixel, utilise l' approche différentielle suivante pour détecter les passages par zéro de la dérivée directionnelle de second ordre dans la direction du gradient :

En suivant la manière géométrique différentielle d'exprimer l'exigence de suppression non maximale proposée par Lindeberg, introduisons en chaque point de l'image un repère local , avec la direction - parallèle à la direction du gradient. En supposant que l'image a été pré-lissée par lissage gaussien et qu'une représentation de l'espace d'échelle à l'échelle a été calculée, nous pouvons exiger que la magnitude du gradient de la représentation de l'espace d'échelle , qui soit égale à la dérivée directionnelle du premier ordre dans la direction , devrait avoir sa dérivée directionnelle du premier ordre dans la direction égale à zéro

tandis que la dérivée directionnelle du second ordre dans la direction de doit être négative, c'est-à-dire

Écrit comme une expression explicite en termes de dérivées partielles locales , cette définition de bord peut être exprimée comme les courbes de passage par zéro de l'invariant différentiel

qui satisfont une condition de signe sur l'invariant différentiel suivant

désignent les dérivées partielles calculées à partir d'une représentation d'espace d'échelle obtenue en lissant l'image originale avec un noyau gaussien . De cette façon, les bords seront automatiquement obtenus sous forme de courbes continues avec une précision inférieure au pixel. Un seuillage d'hystérésis peut également être appliqué à ces segments de bord différentiels et de sous-pixels.

En pratique, les approximations des dérivées du premier ordre peuvent être calculées par différences centrales comme décrit ci-dessus, tandis que les dérivées du second ordre peuvent être calculées à partir de la représentation de l'espace d'échelle selon :

correspondant aux masques filtrants suivants :

Des dérivées d'ordre supérieur pour la condition de signe de troisième ordre peuvent être obtenues d'une manière analogue.

Basé sur la congruence de phase

Un développement récent des techniques de détection des contours utilise une approche du domaine fréquentiel pour trouver les emplacements des contours. Les méthodes de congruence de phase (également connues sous le nom de cohérence de phase) tentent de trouver des emplacements dans une image où toutes les sinusoïdes dans le domaine fréquentiel sont en phase. Ces emplacements correspondront généralement à l'emplacement d'un contour perçu, que le contour soit ou non représenté par un grand changement d'intensité dans le domaine spatial. Un avantage clé de cette technique est qu'elle répond fortement aux bandes de Mach et évite les faux positifs généralement trouvés autour des bords de toit . Un bord de toit, est une discontinuité dans la dérivée du premier ordre d'un profil de niveau de gris.

Inspiré de la physique

Amélioration des fonctionnalités d'une image ( cathédrale St Paul , Londres) à l'aide de la transformation d'étirement de phase (PST). Le panneau de gauche montre l'image d'origine et le panneau de droite montre les caractéristiques détectées à l'aide de PST.

La transformation par étirement de phase ou PST est une approche informatique inspirée de la physique pour le traitement du signal et de l'image. L'un de ses utilitaires est destiné à la détection et à la classification des caractéristiques. PST est une retombée de la recherche sur la transformée de Fourier dispersive dans le temps . PST transforme l'image en émulant la propagation à travers un milieu de diffraction avec une propriété de dispersion 3D (indice de réfraction). L'opération repose sur la symétrie du profil de dispersion et peut être comprise en termes de fonctions propres dispersives ou de modes d'étirement. PST effectue des fonctionnalités similaires à celles de la microscopie à contraste de phase, mais sur des images numériques. Le PST est également applicable aux images numériques ainsi qu'aux données temporelles et temporelles.

Sous-pixel

Pour augmenter la précision de la détection des contours, plusieurs techniques de sous-pixels ont été proposées, notamment des méthodes d'ajustement de courbe, basées sur le moment, reconstructives et à effet de zone partielle. Ces méthodes ont des caractéristiques différentes. Les méthodes d'ajustement de courbe sont simples en termes de calcul mais sont facilement affectées par le bruit. Les méthodes basées sur les moments utilisent une approche basée sur l'intégrale pour réduire l'effet du bruit, mais peuvent nécessiter plus de calculs dans certains cas. Les méthodes de reconstruction utilisent des dégradés horizontaux ou verticaux pour créer une courbe et trouver le sommet de la courbe comme bord du sous-pixel. Les méthodes à effet de zone partielle sont basées sur l'hypothèse que chaque valeur de pixel dépend de la zone des deux côtés du bord à l'intérieur de ce pixel, produisant une estimation individuelle précise pour chaque pixel de bord. Certaines variantes de la technique basée sur les moments se sont avérées les plus précises pour les arêtes isolées.

Détection des contours sur une image angiographique. A gauche, la détection des contours est effectuée au niveau du pixel. A droite, la détection de contour de sous-pixel localise le contour à l'intérieur du pixel avec précision

Voir également

Les références

  1. ^ Umbaugh, Scott E (2010). Traitement et analyse d'images numériques : applications de vision humaine et informatique avec CVIPtools (2e éd.). Boca Raton, Floride : CRC Press. ISBN 978-1-4398-0205-2.
  2. ^ HG Barrow et JM Tenenbaum (1981) "Interprétation des dessins au trait comme surfaces tridimensionnelles", Intelligence artificielle, vol 17, numéros 1 à 3, pages 75 à 116.
  3. ^ a b Lindeberg, Tony (2001) [1994], "Edge detection" , Encyclopedia of Mathematics , EMS Press
  4. ^ A b c d T. Lindeberg (1998) "Détection de contours et la détection crête avec sélection automatique de l' échelle", International Journal of Computer Vision, 30, 2, pages 117-154.
  5. ^ W. Zhang et F. Bergholm (1997) " Estimation du flou à plusieurs échelles et classification du type de contour pour l'analyse de scène ", International Journal of Computer Vision, vol 24, numéro 3, Pages: 219-250.
  6. ^ D. Ziou et S. Tabbone (1998) " Techniques de détection des contours : un aperçu ", International Journal of Pattern Recognition and Image Analysis, 8(4):537-559, 1998
  7. ^ JM Park et Y. Lu (2008) "Détection des contours dans les images en niveaux de gris, couleur et plage", dans BW Wah (éditeur) Encyclopedia of Computer Science and Engineering, doi 10.1002/9780470050118.ecse603
  8. ^ J. Canny (1986) " Une approche informatique de la détection des contours ", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 8, pages 679-714.
  9. ^ R. Haralick, (1984) " Bords de pas numériques du passage à zéro des deuxièmes dérivés directionnels ", IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (1):58-68.
  10. ^ R. Kimmel et AM Bruckstein (2003) "Sur les passages à zéro laplacien régularisés et autres intégrateurs de bord optimaux", International Journal of Computer Vision , 53 (3) pages 225-243.
  11. ^ Shapiro LG & Stockman GC (2001) Vision par ordinateur. Londres etc. : Prentice Hall, page 326.
  12. ^ R. Deriche (1987) En utilisant les critères de Canny pour dériver un détecteur de bord optimal mis en œuvre récursivement , Int. J. Computer Vision, vol 1, pages 167-187.
  13. ^ Sylvain Fischer, Rafael Redondo, Laurent Perrinet, Gabriel Cristobal. Approximation clairsemée d'images inspirées de l'architecture fonctionnelle des aires visuelles primaires . EURASIP Journal on Advances in Signal Processing, numéro spécial sur la perception des images, 2007
  14. ^ Faible, Jules R.; Takamura, Tamio (2013-12-11). « Approche alternative pour la classification des nuages ​​par satellite : application de gradient de bord » . Avancées de la météorologie . 2013 : 1–8. doi : 10.1155/2013/584816 . ISSN  1687-9309 .
  15. ^ T. Lindeberg (1993) "Approximations dérivées discrètes avec des propriétés d'espace d'échelle: Une base pour l'extraction de caractéristiques de bas niveau", J. of Mathematical Imaging and Vision, 3(4), pages 349-376.
  16. ^ T. Pajdla et V. Hlavac (1993) « Discontinuités de surface dans les images de plage », dans Proc IEEE 4th Int. Conf. Calcul. Vision, p. 524-528.
  17. ^ MH Asghari et B. Jalali, "Détection des bords dans les images numériques utilisant l'étirement de la phase dispersive," International Journal of Biomedical Imaging, Vol. 2015, Article ID 687819, pages 1 à 6 (2015).
  18. ^ MH Asghari et B. Jalali, " Détection de bord d'image inspirée de la physique ", IEEE Global Signal and Information Processing Symposium (GlobalSIP 2014), article : WdBD-L.1, Atlanta, décembre 2014.
  19. ^ B. Jalali et A. Mahjoubfar, " Adapter les signaux à large bande avec un accélérateur matériel photonique ", Actes de l'IEEE, vol. 103, n° 7, pp. 1071-1086 (2015).
  20. ^ Ghosal, S.; Mehrota, R (1993-01-01). « Opérateurs de moment orthogonal pour la détection de bords de sous-pixels ». Reconnaissance de motifs . 26 (2) : 295-306. doi : 10.1016/0031-3203(93)90038-X .
  21. ^ un b Christian, John (2017-01-01). « Localisation précise des membres planétaires pour la navigation des engins spatiaux à base d'images ». Journal des vaisseaux spatiaux et des fusées . 54 (3) : 708-730. Bibcode : 2017JSpRo..54..708C . doi : 10.2514/1.A33692 .
  22. ^ Trujillo-Pino, Agustin; Krissian, Karl ; Alemán-Flores, Miguel; Santana-Cédrés, Daniel (2013-01-01). « Emplacement précis du bord du sous-pixel basé sur un effet de zone partiel ». Informatique de l'image et de la vision . 31 (1) : 72-90. doi : 10.1016/j.imavis.2012.10.005 . hdl : 10553/43474 .

Lectures complémentaires