Algorithmes de détection de contour d'image

L'article présente les quatre algorithmes de détection de boucle les plus courants.

Les deux premiers, à savoir l'algorithme de traçage des carrés et de traçage de l'environnement de Moore, sont faciles à mettre en œuvre et sont donc souvent utilisés pour déterminer le contour d'un motif donné. Malheureusement, les deux algorithmes ont plusieurs faiblesses, ce qui rend impossible la détection du contour d'une grande classe de motifs en raison de leur type particulier d'adjacence.

Ces algorithmes ignoreront tous les «trous» du motif. Par exemple, si nous avons un motif similaire à celui montré sur la figure 1 , alors le circuit détecté par les algorithmes sera similaire à celui montré sur la figure 2 (le contour est indiqué par des pixels bleus). Dans certains domaines d'application, cela est tout à fait acceptable, mais dans d'autres domaines, par exemple, dans la reconnaissance des caractères, il est nécessaire de détecter les parties internes du motif pour trouver tous les espaces qui distinguent un caractère particulier. (La figure 3 montre le contour «complet» du motif.)



Par conséquent, pour obtenir un contour complet, il est d'abord nécessaire d'utiliser l'algorithme de «recherche de trous» qui détermine les trous dans un motif donné, puis d'appliquer l'algorithme de détection de contour à chaque trou.

Qu'est-ce que la connectivité?

Dans les images numériques avec des valeurs binaires, un pixel peut avoir l'une des valeurs suivantes: 1 - lorsqu'il fait partie du motif, ou 0 - lorsqu'il fait partie de l'arrière-plan, c'est-à-dire pas de dégradé de gris. (Nous supposerons que les pixels avec une valeur de 1 sont noirs et avec une valeur de 0 sont blancs).

Pour identifier des objets dans un motif numérique, nous devons trouver des groupes de pixels noirs qui sont «connectés» les uns aux autres. En d'autres termes, les objets d'un modèle numérique donné sont les composants connectés de ce modèle.

Dans le cas général, un composant connecté est un ensemble de pixels noirs P , de telle sorte que pour chaque paire de pixels p _i et p _j dans P il y a une séquence de pixels p _i , ..., p _j tels que:

a) tous les pixels de la séquence sont dans l'ensemble P , c'est-à-dire sont noirs, et

b) tous les 2 pixels de la séquence côte à côte sont des «voisins».

Une question importante se pose: quand peut-on dire que 2 pixels sont «voisins»? Puisque nous utilisons des pixels carrés, la réponse à la question précédente n'est pas anodine pour la raison suivante: en pavage carré, les pixels ont un bord ou un sommet commun, ou n'ont rien en commun. Chaque pixel a 8 pixels en commun avec lui; ces pixels constituent le "voisinage de Moore" de ce pixel. Faut-il considérer des pixels "voisins" n'ayant qu'un seul sommet commun? Ou pour être considérés comme «voisins», deux pixels doivent avoir un bord commun?

Il existe donc deux types de connectivité, à savoir: la connectivité 4 et la connectivité 8.

4 connexions

Quand peut-on dire qu'un ensemble donné de pixels noirs est connecté à 4? Tout d'abord, vous devez définir le concept de 4 voisins (également appelé voisin direct ):

Définition 4 voisins : Un pixel Q est un 4 voisins d'un pixel P donné si Q et P ont un bord commun. Les 4 voisins du pixel P (désignés par P2, P4, P6 et P8 ) sont représentés sur la figure 2 ci-dessous.


Définition d'un composant à 4 connexions : l'ensemble des pixels noirs P est un composant à 4 connexions si pour chaque paire de pixels p _i et p _j dans P il y a une séquence de pixels p _i , ..., p _j tels que:

a) tous les pixels de la séquence sont dans l'ensemble P , c'est-à-dire sont noirs, et

b) tous les deux pixels adjacents dans la séquence sont 4 voisins

Exemples de modèles à 4 connexions

Les diagrammes ci-dessous montrent des exemples de modèles à 4 connexions:

8 connexions

Quand puis-je dire qu'un ensemble donné de pixels noirs est connecté à 8 ? Tout d'abord, nous devons définir le concept d'un voisin à 8 (également appelé voisin indirect ):

Définition de 8 voisins : Un pixel Q est un 8 voisins (ou juste un voisin ) d'un pixel P donné si Q et P ont un bord ou un sommet commun. Les 8 voisins d'un pixel P constituent le voisinage de Moore de ce pixel.

Définition d'un composant connecté à 8 : l'ensemble des pixels noirs P est un composant connecté à 8 (ou juste un composant connecté ) si pour chaque paire de pixels p _i et p _j dans P il y a une séquence de pixels p _i , ..., p _j tels que :

a) tous les pixels de la séquence sont dans l'ensemble P , c'est-à-dire sont noirs, et

b) tous les deux pixels adjacents dans cette séquence sont 8 voisins

Remarque : tous les modèles à 4 connexions sont à 8 connexions, c'est-à-dire Les modèles à 4 connexions sont un sous-ensemble des nombreux modèles à 8 connexions. En revanche, un modèle à 8 connexions peut ne pas être à 4 connexions.

Exemple de modèle lié à 8

Le diagramme ci-dessous montre un modèle qui est connecté à 8 mais pas à 4:

Un exemple de modèle non connecté à 8:

Le diagramme ci-dessous montre un exemple d'un modèle qui n'est pas connecté à 8, c'est-à-dire composé de plusieurs composants connectés (le schéma montre trois composants connectés):

Algorithme de trace carrée

Idée

L'idée derrière l'algorithme de tracé carré est très simple; cela peut être attribué au fait que l'algorithme a été l'une des premières tentatives de détection du contour d'un motif binaire.

Pour comprendre comment ça marche, il faut un peu d'imagination ...

Supposons que nous ayons un motif numérique, par exemple, un groupe de pixels noirs sur un fond de pixels blancs, c'est-à-dire sur la grille; trouver le pixel noir et le déclarer comme notre pixel " initial ". (Trouver le pixel « initial » peut être implémenté de différentes manières; nous commencerons par le coin inférieur gauche de la grille, nous balayerons chaque colonne de pixels de bas en haut, de la colonne la plus à gauche à l'extrême droite, jusqu'à ce que nous tombions sur un pixel noir. Nous le déclarerons « initial » ".)

Imaginez maintenant que vous êtes une coccinelle debout sur le pixel de départ , comme le montre la figure 1 ci-dessous. Pour obtenir le contour d'un motif, vous devez procéder comme suit:

, , ,

, , ,

.

Les pixels noirs que vous avez encerclés seront le contour du motif.


Un aspect important de l'algorithme du tracé carré est le «sens de l'orientation». Les virages à gauche et à droite sont effectués par rapport à l'emplacement actuel, ce qui dépend de la façon dont vous êtes arrivé au pixel actuel. Par conséquent, afin de faire les bons mouvements, vous devez suivre votre direction.

Algorithme

Ce qui suit est une description formelle de l'algorithme de trace carrée:

Entrée: pavage carré, T , contenant la composante connectée P des cellules noires.

Sortie: ligne B (b ₁ , b ₂ , ..., b _k ) de pixels de bordure, c'est-à-dire contour.

Commencer

• Définissez B comme un ensemble vide.
• Scannez les cellules T de bas en haut et de gauche à droite jusqu'à ce qu'un pixel noir s de P soit trouvé .
• Insérez s dans B.
• Faire du pixel actuel p le pixel initial s .
• Tournez à gauche, c'est-à-dire aller au pixel voisin à gauche de p .
• Mettre à jour p , c'est-à-dire il devient le pixel actuel.
• Alors que p n'est pas égal à s , exécutez
  
  Si le pixel actuel p est noir
  
  • insérez p dans B et tournez à gauche (allez au pixel voisin à gauche de p ).
  • Mettre à jour p , c'est-à-dire il devient le pixel actuel.
  
  sinon
  
  • tourner à droite (passer au pixel suivant à droite de p ).
  • Mettre à jour p , c'est-à-dire il devient le pixel actuel.
  
  Fin du cycle «Bye»

La fin

Remarque: les concepts de «gauche» et de «droite» doivent être considérés non pas par rapport à la page ou au lecteur, mais par rapport à la direction d'entrée dans le pixel «actuel» pendant la numérisation.

Démonstration

Ce qui suit est une démonstration animée de la façon dont l'algorithme de trace carrée détecte le contour d'un motif. N'oubliez pas que la coccinelle se déplace en pixels; remarquez comment sa direction change en tournant à gauche et à droite. Les virages à gauche et à droite sont effectués par rapport à la direction actuelle dans un pixel, c'est-à-dire orientation coccinelle.

Analyse

Il s'avère que les capacités de l'algorithme de trace carrée sont très limitées. Il est incapable de détecter les contours d'une grande famille de motifs qui surviennent souvent dans des applications réelles.

Ceci est principalement dû au fait que les rotations gauche et droite ne prennent pas en compte les pixels situés
diagonales "du pixel actuel.

Examinons les différents modèles avec une connectivité différente et voyons pourquoi l'algorithme de trace carrée échoue. De plus, nous étudierons les moyens d'améliorer les capacités de l'algorithme et de le faire fonctionner même avec des modèles qui ont un type spécial de connectivité.

Critère d'arrêt

L'une des faiblesses de l'algorithme est le choix du critère d'arrêt. En d'autres termes, quand un algorithme cesse-t-il de s'exécuter?

Dans la description d'origine de l'algorithme de trace carrée, la condition de fin consiste à toucher le pixel initial une deuxième fois. Il s'avère que si l'algorithme dépend d'un tel critère, il ne pourra pas détecter les contours d'une grande famille de motifs.

Ce qui suit est une démonstration animée expliquant comment l'algorithme est incapable de détecter le contour exact du motif en raison de la sélection d'un mauvais critère d'arrêt:


Comme vous pouvez le voir, l'amélioration du critère d'arrêt peut être un bon début pour améliorer les performances globales de l'algorithme. Il existe deux alternatives efficaces pour un critère d'arrêt existant:

a) Arrêtez-vous uniquement en visitant le pixel de départ n fois, où n vaut au moins 2, OU

b) Arrêtez après avoir frappé le pixel de départ une deuxième fois, tout comme nous l'avons touché au départ.

Ce critère a été proposé par Jacob Eliosoff , nous l'appellerons donc le critère d'arrêt de Jacob .

La modification du critère d'arrêt dans le cas général améliore l'efficacité de l'algorithme de trace carrée, mais ne remédie pas aux autres faiblesses qu'il présente dans le cas de modèles avec des types de connectivité spéciaux.

L'algorithme de traçage carré est incapable de détecter le contour d'une famille de motifs avec une connectivité de 8 qui n'a PAS une connectivité de 4.

Ce qui suit est une démonstration animée de la façon dont l'algorithme de trace carrée (avec le critère d'arrêt de Jacob) ne parvient pas à détecter le contour correct d'un modèle avec connectivité 8 sans connectivité 4:

Cet algorithme est-il complètement inutile?

Si vous lisez l'analyse ci-dessus, vous pensez probablement que l'algorithme de trace carrée ne parvient pas à détecter les contours de la plupart des modèles. Mais cela s'avère. qu'il existe une famille spéciale de motifs dans lesquels le chemin est entièrement détecté par l'algorithme de trace carrée.

Soit P l'ensemble des pixels noirs avec la connectivité 4 sur la grille. Soit les pixels blancs de la grille, c'est-à-dire les pixels d'arrière-plan W ont également une connectivité de 4. Il s'avère que dans de telles conditions du motif et de son arrière-plan, il peut être prouvé que l'algorithme de trace carrée (avec le critère d'arrêt de Jacob) traitera toujours avec succès la détermination du contour.

Ci-dessous est la preuve que dans le cas où le motif et les pixels d'arrière-plan sont connectés, l'algorithme de trace carrée déterminera correctement le contour lors de l'utilisation du critère d'arrêt Jacob.

Preuve
Étant donné : le motif P est tel que tous les pixels du motif (c'est-à-dire noir) et les pixels d'arrière-plan (c'est-à-dire blanc) W ont une connectivité de 4.

Première observation

Puisque l'ensemble de pixels blancs W a une connectivité de 4, cela signifie qu'il ne peut pas y avoir de « trous » dans le motif (en termes informels, « trous », nous entendons des groupes de pixels blancs complètement entourés par des pixels noirs du motif).

La présence de tout « trou » dans le motif entraînera la séparation du groupe de pixels blancs des pixels blancs restants; cependant, de nombreux pixels blancs perdent leur connectivité 4.

La figure 2 et la figure 3 ci-dessous montrent deux types de « trous » qui peuvent se produire dans un modèle avec connectivité 4:



Deuxième observation

Deux pixels noirs d'un motif DOIVENT avoir un côté commun.

Supposons que deux pixels noirs aient un seul sommet commun. Ensuite, afin de satisfaire la propriété de 4-connectivité du motif, il doit y avoir un chemin reliant ces deux pixels afin que tous les deux pixels adjacents sur ce chemin aient une connectivité de 4. Mais cela nous donnera un motif similaire à la figure 3 . En d'autres termes, cela entraînera une séparation des pixels blancs. La figure 4 ci-dessous montre un motif typique satisfaisant à l'hypothèse que les pixels du motif et de l'arrière-plan sont connectés en 4, c'est-à-dire n'ont pas de « trous » et tous les deux pixels noirs ont un côté commun:


Il est utile de représenter ces modèles comme suit:

Nous considérons d'abord les pixels limites, c'est-à-dire contour du motif. Ensuite, si nous considérons chaque pixel frontière comme ayant 4 bords de longueur unitaire, nous verrons que certains de ces bords sont communs avec les pixels blancs voisins. Nous appellerons ces arêtes des arêtes limites .

Ces bords limites peuvent être considérés comme des bords d'un polygone. Dans l' image
5 ci-dessous, cette idée est illustrée par l'exemple d'un polygone correspondant au motif de la figure 4 ci-dessus:


Si nous considérons toutes les «configurations» possibles de pixels limites qui peuvent se produire dans de tels motifs, nous verrons qu'il existe deux cas simples, illustrés dans les figures 6 et 7 ci-dessous.

Les pixels limites peuvent être des multiples de ces cas ou d'autres dispositions, c'est-à-dire les rebondissements de ces deux cas. Les côtes frontières sont marquées en bleu comme E1, E2, E3 et E4 .


Troisième observation

Dans le cas des deux cas ci-dessus, quel que soit le pixel initial que nous choisissons, et quelle que soit la direction dans laquelle il tombe , l'algorithme de tracé carré ne "reviendra" jamais (retour arrière) , il ne "traversera" jamais le bord de frontière deux fois seulement s'il ne trace pas la frontière une deuxième fois) et ne manquez jamais le bord de la frontière . Découvrez-le!

Deux concepts doivent être clarifiés ici:

a) l'algorithme "remonte" , quand avant de tracer la bordure entière il revient pour visiter un pixel déjà visité, et

b) pour chaque nervure limite, il y a deux façons de «la traverser» , à savoir «vers l'intérieur» et «vers l'extérieur» (où «vers l'intérieur» signifie le mouvement vers l'intérieur du polygone correspondant et «vers l'extérieur» - vers l'extérieur du polygone).

De plus, lorsque l'algorithme passe "vers l'intérieur" à travers l'un des bords de frontière, il passera "vers l'extérieur" à travers le bord de frontière suivant, c'est-à-dire l'algorithme de tracé carré ne doit pas pouvoir traverser deux bords consécutifs de la même manière.

Dernière observation

Chaque motif a un nombre pair d' arêtes limites .

Si vous regardez le polygone de la figure 5 , vous pouvez voir que:

si nous voulons partir du sommet S marqué dans le diagramme et suivre les bords limites jusqu'à ce que nous atteignions à nouveau S , alors nous remarquons que dans le processus, nous traversons un nombre pair de bords limites. Nous pouvons considérer chaque bord de frontière comme un «pas» dans une direction distincte. Ensuite, pour chaque «pas» à droite, il doit y avoir un «pas» correspondant à gauche, si nous voulons revenir à la position de départ. Il en va de même pour les «marches» verticales. Par conséquent, les «étapes» doivent avoir des paires correspondantes, ce qui explique pourquoi chacun de ces motifs aura un nombre pair d'arêtes limites.

Par conséquent, lorsque l'algorithme de traçage des carrés entre par le bord limite initial (du pixel initial) une deuxième fois, il le fera dans la même direction que la première fois.

La raison en est que, comme il existe deux façons de traverser le bord de limite, et que l'algorithme se déplace alternativement vers l'intérieur et l'extérieur, et qu'il existe un nombre pair de bords de limite, l'algorithme passera pour la deuxième fois par le bord de limite initial de la même manière que dans premier.

Conclusion

Dans le cas d'un motif et d'un arrière-plan connectés à 4, l'algorithme de tracé carré détectera la bordure entière, c'est-à-dire contour, motif et cessera de fonctionner après une seule trace, c.-à-d. il ne le tracera pas à nouveau, car lorsqu'il atteindra le bord limite initial pour la deuxième fois, il l'entrera de la même manière que la première fois. Par conséquent, l'algorithme de tracé carré avec le critère d'arrêt de Jacob déterminera correctement le compteur de n'importe quel motif, à condition que le motif et l'arrière-plan soient tous les quatre connectés.

Retrouver les environs de Moore

Idée

L'idée derrière le traçage Moore-Neighbour est simple; mais avant de l'expliquer, nous devons expliquer un concept important: le voisinage Moore d'un pixel.

Le quartier de Moore

Le voisinage de Moore d'un pixel P est un ensemble de 8 pixels ayant un sommet ou un bord commun avec ce pixel. Ces pixels, à savoir P1, P2, P3, P4, P5, P6, P7 et P8 , sont représentés sur la figure 1 .

Le quartier Moore (également appelé 8 voisins ou voisins indirects ) est un concept important souvent mentionné dans la littérature.


Nous sommes maintenant prêts à nous familiariser avec l'idée qui sous-tend la trace de l'environnement de Moore.

Qu'il y ait un modèle numérique, c'est-à-dire un groupe de pixels noirs, sur un fond de pixels blancs, c'est-à-dire sur la grille; trouver le pixel noir et le déclarer pixel " initial ". (Il existe plusieurs façons de trouver le pixel « initial », mais comme précédemment, nous commencerons par le coin inférieur gauche et numériserons toutes les colonnes de pixels dans l'ordre, jusqu'à ce que nous trouvions le premier pixel noir, que nous déclarerons « initial ».)

Maintenant, imaginez à nouveau que vous êtes une coccinelle debout sur le pixel de départ , comme le montre la figure 2 ci-dessous. Sans perte de généralisation, nous allons détecter le contour en se déplaçant dans le sens horaire. (Peu importe la direction que nous choisissons, l'essentiel est de l'utiliser constamment dans l'algorithme).

L'idée générale est la suivante: chaque fois que nous arrivons au pixel noir P , nous revenons, c'est-à-dire au pixel blanc dans lequel nous nous trouvions auparavant. Ensuite, nous contournons le pixel P dans le sens des aiguilles d'une montre, visitant chaque pixel à proximité de Moore, jusqu'à ce que nous arrivions au pixel noir. L'algorithme se termine lorsque le pixel de départ atteint le pixel de démarrage une deuxième fois.

Ces pixels noirs que l'algorithme a visités seront le contour du motif.

Algorithme

Voici une description formelle de l'algorithme de suivi du voisinage de Moore:

Entrée: pavage carré T contenant une composante connectée P de cellules noires.

Sortie: ligne B (b ₁ , b ₂ , ..., b _k ) de pixels limites, c'est-à-dire contour.

Notons M (a) le voisinage de Moore du pixel a .

Soit p le pixel de bordure actuel.

Soit c le pixel courant considéré, c'est-à-dire c est dans M (p) .

Commencer

• Définissez B comme un ensemble vide.
• De bas en haut et de gauche à droite, scannez les cellules T jusqu'à ce que nous trouvions un pixel noir s de P.
• Insérez s dans B.
• Nous définissons le point s comme le point limite actuel p , c'est-à-dire p = s
• Revenons en arrière, c'est-à-dire Passons au pixel d'où nous sommes arrivés à l' art .
• Soit c le pixel suivant dans le sens des aiguilles d'une montre dans M (p) .
• Alors que c n'est pas égal à s , exécutez
  
  
  • si c est noir
    
    • Insérez c dans B
    • on pose p = c
    • revenir en arrière (déplacer le pixel actuel c vers le pixel à partir duquel nous sommes arrivés à p )
    
    sinon
    
    • déplacer le pixel actuel c vers le pixel suivant dans le sens des aiguilles d'une montre dans M (p)
    
    Fin du cycle d'adieu

La fin

Démonstration

Ce qui suit est une démonstration animée de la façon dont la trace de voisinage de Moore effectue la détection de contour de motif. (Nous avons décidé de tracer le contour dans le sens horaire.)

Analyse

La principale faiblesse du tracé des environs de Moore réside dans le choix des critères d'arrêt.

Dans la description originale de l'algorithme de traçage de l'environnement de Moore, le critère d'arrêt est de toucher le pixel initial une seconde fois. Semblable à l'algorithme de tracé carré, il s'avère que le traçage de l'environnement de Moore en utilisant ce critère ne peut pas détecter les contours d'une grande famille de motifs.

Ce qui suit est une démonstration animée expliquant pourquoi l'algorithme ne peut pas trouver le contour exact du motif en raison de la sélection d'un mauvais critère d'arrêt:


Comme vous pouvez le voir, l'amélioration du critère d'arrêt peut être un bon début pour améliorer les performances globales de la trace. Il existe deux alternatives efficaces pour le critère d'arrêt, similaires au critère d'arrêt de Jacob.

L'utilisation du critère de Jacob améliore considérablement l'efficacité du traçage de l'environnement de Moore, ce qui en fait le meilleur algorithme pour déterminer le contour de n'importe quel motif, quelle que soit sa connectivité.

La raison en est principalement que l'algorithme vérifie tout le voisinage de Moore du pixel limite pour rechercher le pixel limite suivant. Contrairement à l'algorithme de tracé carré, qui ne tourne qu'à gauche et à droite et qui manque les pixels «en diagonale», le tracé de voisinage de Moore sera toujours en mesure de détecter la limite extérieure de tout composant connecté. La raison en est la suivante: pour tout motif à 8 connexions (ou simplement connecté ), le pixel de bordure suivant se trouve dans le voisinage de Moore du pixel de bordure actuel. Étant donné que la trace de voisinage de Moore vérifie chacun des pixels dans le voisinage de Moore du pixel limite actuel, il doit détecter le pixel limite suivant.

Lorsque le tracé du voisinage de Moore atteint le pixel initial une deuxième fois de la même manière que la première fois, cela signifie qu'un contour externe complet du motif a été détecté, et si l'algorithme n'est pas arrêté, il détectera à nouveau le même contour.

Balayage radial

L'algorithme de balayage radial est un algorithme de détection de contour discuté dans certains livres. Malgré le nom complexe, l'idée sous-jacente est très simple. En fait, il s'avère que l'algorithme de balayage radial est identique à la trace de l'environnement de Moore. On peut se demander: "Pourquoi le mentionnons-nous?"

Le traçage de l'environnement de Moore recherche à proximité de Moore le pixel limite actuel dans une certaine direction (nous avons choisi la direction horaire) jusqu'à ce qu'il trouve un pixel noir. Elle déclare ensuite ce pixel comme pixel limite actuel et continue.

L'algorithme de balayage radial fait de même. D'un autre côté, il fournit un moyen intéressant de trouver le prochain pixel noir dans le voisinage de Moore d'un pixel limite donné.

La méthode est basée sur l'idée suivante:

chaque fois que nous trouvons un nouveau pixel limite, en faisons le pixel actuel P et dessinons un segment de ligne imaginaire reliant P au pixel limite précédent . Ensuite, nous faisons pivoter le segment par rapport à P dans le sens des aiguilles d'une montre jusqu'à ce qu'il rencontre un pixel noir dans le voisinage de Moore du pixel P. La rotation de la ligne est identique à la vérification de chaque pixel au voisinage de Moore P.

Nous avons créé une démonstration animée du fonctionnement de l'algorithme de balayage radial et à quoi il ressemble en traçant les environs de Moore.


Et quand l'algorithme de balayage radial s'arrête-t-il?

Expliquons le comportement de l'algorithme en utilisant les critères d'arrêt suivants ...

Critère d'arrêt 1

Laissez l'algorithme de balayage radial se terminer lorsqu'il visite le pixel initial une deuxième fois.

Vous trouverez ci-dessous une démonstration animée, à partir de laquelle il est clair pourquoi le critère de rupture sera modifié correctement.


Il convient également de mentionner qu'en utilisant ce critère d'arrêt dans les deux algorithmes, l'efficacité de l'algorithme de balayage radial est identique au traçage de l'environnement de Moore.

Dans l'algorithme de trace carrée et dans la trace de voisinage de Moore, nous avons constaté que l'utilisation du critère d'arrêt de Jacob améliore considérablement les performances des deux algorithmes.

Le critère d'arrêt de Jacob nécessite que l'algorithme arrête de s'exécuter lorsqu'il visite le pixel de départ une deuxième fois dans la même direction que la première fois.

Malheureusement, nous ne pouvons pas utiliser le critère d'arrêt de Jacob dans l'algorithme de balayage radial. La raison en est que l'algorithme de balayage radial ne définit pas le conceptLa "direction" dans laquelle il frappe le pixel limite . En d'autres termes, la «direction» dans laquelle l'algorithme est tombé dans le pixel limite n'est pas claire (et sa définition n'est pas triviale).

Par conséquent, nous devons proposer un autre critère d'arrêt, qui ne dépend pas de la direction de frapper un certain pixel, ce qui peut améliorer l'efficacité de l'algorithme de balayage radial ...

Critère d'arrêt 2

Supposons que chaque fois que l'algorithme détecte un nouveau pixel frontière P _i , il soit inséré dans une série de pixels frontière: P ₁ , P ₂ , P ₃ , ..., P _i ; et déclaré comme pixel de bordure actuel. ( P ₁ nous considérerons le pixel initial ). Cela signifie que nous connaissons le pixel de bordure précédent P _{i-1 de} chaque pixel de bordure actuel P _i . (Quant au pixel de départ , nous supposerons que P ₀est un pixel imaginaire qui n'est équivalent à aucun des pixels de la grille qui fait face au pixel initial de la rangée de pixels limites).

Sur la base des hypothèses ci-dessus, nous pouvons déterminer le critère d'arrêt comme suit:

L'algorithme arrête l'exécution lorsque:

a) le pixel limite actuel P _i s'est précédemment rencontré en tant que pixel P _j (où j <i ) dans une série de pixels limites, Et

b) P _{i- 1} = P _j-1 .

En d'autres termes, l'algorithme termine son exécution lorsqu'il visite le pixel limite P dans le secondfois si le pixel limite avant P (dans la rangée de pixels limites) pour la deuxième fois est le même pixel qu'avant P lorsque P a été visité pour la première fois.

Si la condition du critère d'arrêt est satisfaite et que l'algorithme ne s'arrête pas, l'algorithme de balayage radial continuera à détecter la même limite une deuxième fois.

Les performances de l'algorithme de balayage radial avec ce critère d'arrêt sont similaires à celles du traçage du voisinage de Moore avec le critère d'arrêt Jacob.

Algorithme de Theo Pavlidis

Idée

Cet algorithme est l'un des derniers algorithmes de détection de boucle proposés par Theo Pavlidis . Il l'a cité dans son livre de 1982, Algorithms for Graphics and Image Processing (chapitre 7, section 5). Ce n'est pas aussi simple que l'algorithme de traçage des carrés ou de traçage de l'environnement de Moore, mais ce n'est pas si compliqué (c'est typique de la plupart des algorithmes de détection de bord).

Nous n'expliquerons pas cet algorithme de la même manière que cela a été fait dans son livre. Notre approche est plus facile à comprendre et donne une idée de l'idée générale sous-jacente à l'algorithme.

Sans perte de généralisation, nous avons décidé de faire le tour de la boucle dans le sens horaire pour correspondre à l'ordre de tous les autres algorithmes présentés dans l'article. En revanche, Pavlidis a choisi la direction dans le sens antihoraire. Cela n'affectera pas les performances de l'algorithme. La seule différence est la direction relative des mouvements que nous ferons lorsque nous contournerons le contour.

Passons maintenant à l'idée ...

Disons que nous avons un modèle numérique, c'est-à-dire un groupe de pixels noirs sur fond de pixels blancs, c'est-à-dire sur la grille; trouver le pixel noir et le déclarer pixel " initial ". Vous pouvez rechercher le pixel «de départ » de différentes manières, par exemple, comme décrit ci-dessus.

Pour trouver l' initialepixels pour utiliser cette méthode est facultatif. Au lieu de cela, nous choisirons un pixel de départ qui satisfait aux restrictions suivantes imposées par l'algorithme Pavlidis pour sélectionner un pixel de départ:

Une limitation importante de la direction dans laquelle nous entrons le pixel de départ

En fait, vous pouvez choisir N'IMPORTE QUEL pixel de bordure noire comme pixel de départ dans cette condition: si vous vous tenez initialement dessus, le pixel voisin gauche n'est PAS noir. En d'autres termes, vous devez entrer le pixel de départ dans une direction telle que le pixel voisin gauche est blanc (la «gauche» ici est prise par rapport à la direction dans laquelle nous entrons le pixel de départ ).

Imaginez maintenant que vous êtes une coccinelle deboutpixel de départ , comme le montre la figure 1 ci-dessous. Lors de l'exécution de l'algorithme, nous ne nous intéresserons qu'à trois pixels devant vous, soit P1, P2 et P3 illustrés à la figure 1 . (Nous désignerons P2 comme le pixel devant vous, P1 est le pixel à gauche de P2 et P3 est le pixel à droite de P2 ).


Comme pour l'algorithme de trace carrée, la chose la plus importante dans l'algorithme de Pavlidis est le «sens de l'orientation». Les virages à gauche et à droite sont relatifs à la position actuelle, qui dépend de la façon dont vous avez entré le pixel actuel. Par conséquent, afin de faire les bons mouvements, il est important de garder une trace de votre orientation actuelle. Mais quelle que soit votre position, les pixels P1, P2 et P3 sont déterminés comme décrit ci-dessus.

Ayant ces informations, nous sommes prêts à expliquer l'algorithme ...

Chaque fois que vous vous tenez sur le pixel limite actuel (qui est d'abord le pixel initial ), nous faisons ce qui suit:

Tout d'abord , vérifiez le pixel P1 . Si P1 est noir, déclarez P1le pixel limite actuel et avancer d'un pas, puis faire un pas vers la gauche pour être à P1 (l' ordre des déplacements est très important).

Dans la figure 2 ci - dessous illustre ce cas. Le chemin pour arriver à P1 est indiqué en bleu.


Et seulement si P1 est blanc, nous procédons à la vérification de P2 ...

Si P2 est noir, alors déclarons P2 le pixel limite actuel et avançons d'un pas pour être sur P2 . Ce cas est illustré à la figure 3 ci-dessous. Le chemin que vous devez suivre sur P2 est indiqué en bleu.


Uniquement si P1 et P2 sont blancs, passez à la vérification P3 ...

Si P3 est noir, déclarez P3 le pixel de bordure actuel et déplacez-vous d'un pas vers la droite, puis d'un pas vers la gauche , comme le montre la figure 4 ci-dessous.


C'est tout! Trois règles simples pour trois cas simples. Comme vous pouvez le voir, il est important de garder une trace de votre direction dans les virages, car tous les déplacements sont effectués par rapport à l'orientation actuelle. Mais il semble que nous ayons oublié quelque chose? Et si les trois pixels sont blancs devant nous? Ensuite, nous tournons (debout au pixel limite actuel) de 90 degrés dans le sens des aiguilles d'une montre pour voir un nouvel ensemble de trois pixels devant nous. Ensuite, nous faisons la même vérification pour ces nouveaux pixels. Vous avez peut-être encore une question: que faire si ces trois pixels sont blancs?! Ensuite, nous tournons à 90 degrés dans le sens des aiguilles d'une montre, en nous tenant au même pixel. Avant de vérifier tout le voisinage du pixel de Moore, vous pouvez faire pivoter trois fois (chaque fois à 90 degrés dans le sens des aiguilles d'une montre).

Si nous tournons trois fois sans jamais trouver de pixels noirs, cela signifie que nous nous trouvons sur un pixel isolé qui n'est connecté à aucun autre pixel noir. C'est pourquoi l'algorithme vous permet de faire pivoter trois fois, puis termine son exécution.

Autre aspect: quand l'algorithme termine-t-il l'exécution?

L'algorithme se termine dans deux cas:

a) comme mentionné ci-dessus. l'algorithme vous permet de faire pivoter trois fois (90 degrés dans le sens horaire à chaque fois), après avoir terminé l'exécution et déclaré le pixel isolé OU

b) lorsque le pixel limite actuel est le pixel initial , l'algorithme termine l'exécution en «déclarant» qu'il a détecté le contour du motif.

Algorithme

Voici une description formelle de l'algorithme de Pavlidis:

Entrée: pavage carré T contenant une composante connectée P de cellules noires.

Sortie: ligne B (b ₁ , b ₂ , ..., b _k ) de pixels limites, c'est-à-dire contour.

Définitions:

• Notons p le pixel limite actuel, c'est-à-dire le pixel sur lequel nous nous tenons.
• Définissez P1, P2 et P3 comme suit: (voir également la figure 1 ci-dessus)
• P2 est le pixel devant vous, adjacent à celui sur lequel vous vous tenez, c'est-à-dire avec pixel p .
• P1 — , P2 .
• P3 — , P2 .
• «» .

Commencer

• B .
• T , s P (. , )
• s B .
• p s .
• :
  P1
  
  • P1 B
  • p=P1
  • ,
  
  P2
  
  • P2 B
  • p=P2
  • (. 3)
  
  P3
  
  • P3 B
  • p=P3
  • , (. 4)
  
  90 , p
  
  • terminer le programme et déclarer p un pixel isolé
  
  sinon
  
  • tourner de 90 degrés dans le sens des aiguilles d'une montre, se tenant au pixel actuel p
  
  Jusqu'à présent p = s (Fin de la boucle de répétition)

La fin

Démonstration

Ce qui suit est une démonstration animée de la façon dont l'algorithme Pavlidis détecte le contour d'un motif donné. N'oubliez pas que nous marchons en pixels; remarquez comment l'orientation change lorsque vous tournez à gauche ou à droite. Pour expliquer l'algorithme de manière aussi détaillée que possible, nous y avons inclus tous les cas possibles.

Analyse

Si vous pensez que l'algorithme Pavlidis est idéal pour détecter les contours de motifs, alors vous devriez changer d'avis ...

Cet algorithme est vraiment un peu plus compliqué que, par exemple, pour tracer les environs de Moore, dans lequel il n'y a pas de cas particuliers qui nécessitent un traitement séparé, mais il ne sera pas en mesure de déterminer les contours d'un grand une famille de modèles qui a un certain type de connectivité.

L'algorithme fonctionne très bien sur les modèles à 4 connexions. Son problème se produit lors du traçage de certains modèles connectés à 8 qui ne sont pas connectés à 4. Ce qui suit est une démonstration animée de la façon dont l'algorithme Pavlidis ne parvient pas à détecter le contour correct d'un modèle à 8 connexions (pas un modèle à 4 connexions) - il saute la majeure partie de la frontière.


Il existe deux façons simples de modifier un algorithme pour améliorer considérablement ses performances.

a) Remplacer le critère d'arrêt

Au lieu de terminer l'algorithme lorsqu'il visite le pixel de départ une deuxième fois, vous pouvez le terminer lorsqu'il visite le pixel de départ une troisième ou même une quatrième fois. Cela améliorera les performances globales de l'algorithme.

OU

b) Aller à la source du problème, c'est-à-dire avant de sélectionner le pixel de départ

Il existe une limitation importante concernant la direction dans laquelle l'entrée du pixel de départ est effectuée. Essentiellement, vous devez entrer le pixel de départ pour que lorsque vous vous tenez dessus, le pixel à votre gauche soit blanc. La raison de l'introduction de cette restriction est la suivante: puisque nous regardons toujours les trois pixels devant nous dansdans un certain ordre , dans certains motifs, nous ignorerons le pixel limite situé directement à gauche du pixel initial.

Nous risquons de manquer non seulement le pixel voisin gauche du pixel initial, mais aussi le pixel directement en dessous (comme démontré dans l'analyse). De plus, dans certains motifs, un pixel correspondant au pixel R de la figure 5 ci - dessous sera ignoré . Par conséquent, nous supposons que le pixel de départ doit être frappé dans une direction telle que les pixels correspondant aux pixels L, W et R représentés sur la figure 5 ci-dessous sont blancs.


Dans ce cas, des modèles comme celui montré dans la démonstration seront détectés correctement et l'efficacité de l'algorithme Pavlidis s'améliorera considérablement. D'un autre côté, trouver un pixel initial qui satisfait à ces exigences peut être difficile, et dans de nombreux cas, il sera impossible de trouver un tel pixel. Dans ce cas, vous devez utiliser un autre moyen d'améliorer l'algorithme Pavlidis, à savoir l'achèvement de l'algorithme après avoir visité le point de départ pour la troisième fois.