UDC 004932:621.396

T. M. VLASOVA, V.G. KALMYKOV

ALGORITHME ET PROGRAMME DE RECONNAISSANCE DES CONTOURS D'IMAGE COMME SEQUENCE DE SEGMENTS DE LIGNES NUMERIQUES

Résumé : Dans le travail donné, l'algorithme de reconnaissance du segment de ligne directe numérique dans les contours des images binaires et le l'implémentation logicielle de l'algorithme est considérée. L'utilisation de cet algorithme pour traiter les images conduira à une description plus naturelle et économique par rapport aux manières connues de description des images. L'algorithme considéré et l'implémentation logicielle peuvent également être utilisés pour la description des contours lors du traitement des images en demi-teintes et en couleurs.

Mots clés : image, contour, segments droits numériques, algorithme, programme.

Annotation : Dans ce robot, un algorithme de reconnaissance de lignes numériques dans les contours d'images binaires est introduit, ainsi qu'une implémentation logicielle de l'algorithme. Nous avons développé l'algorithme de traitement de l'image dans la mesure où la description de l'image serait plus naturelle et économiquement à la hauteur des méthodes de codage de l'image. L'algorithme proposé et la mise en œuvre logicielle peuvent être configurés pour coder les contours lors du traitement des images en tons de navigation et en couleur. Mots clés : images, contour, droites numériques, algorithme, programme.

Résumé : Dans cet article, nous considérons un algorithme de reconnaissance de segments de lignes numériques dans les contours d'images binaires et l'implémentation logicielle de l'algorithme. L'utilisation de cet algorithme dans le traitement d'images se traduira par un rendu plus naturel et économique par rapport à manières connues descriptif des images. L'algorithme et l'implémentation logicielle considérés peuvent également être utilisés pour décrire les contours dans le traitement des images en niveaux de gris et en couleur. Mots clés : image, contour, segments de lignes numériques, algorithme, programme.

1. Introduction

L'analyse structurelle des contours d'images sous forme de séquences de segments de lignes et d'arcs de courbes est l'une des principales tâches du traitement d'images en vue de leur interprétation dans les systèmes d'intelligence artificielle.

Dans la plupart des cas, l'image peut être considérée comme une partie du plan, divisée en zones avec des paramètres constants ou changeants selon une loi, par exemple, la densité optique, la couleur, la texture, qui déterminent l'arrière-plan et les objets de l'image. Une propriété intégrale de chacune de ces zones est sa limite, c'est-à-dire que le contour est une séquence simplement connectée composée de segments de ligne et d'arcs courbes. Lors du traitement d'une image raster, les contours des objets sont généralement mis en surbrillance. Cependant, les contours des objets, présentés comme un ensemble de pixels frontières séparés, ne sont pas très adaptés à un traitement ultérieur, car ils n'expriment pas suffisamment son essence géométrique.

La reconnaissance des contours d'image sous la forme d'une séquence de segments de ligne peut être considérée comme l'une des principales tâches du processus de traitement d'une image tramée. Résoudre le problème de la représentation d'un contour sous la forme d'une séquence de segments de droite permet d'obtenir une description de l'image sous une forme compacte, naturelle pour la perception humaine, invariante par transformations affines, commode, notamment, pour un traitement par réseaux de neurones. Les segments de ligne sont les éléments de base d'un contour. L'arc de courbe est aussi souvent remplacé par une ligne brisée qui s'y inscrit, tant dans les fondamentaux du calcul que dans en grand nombre Applications pratiques.

Des méthodes et algorithmes connus, notamment ceux proposés dans l'ouvrage, permettent d'obtenir une solution approchée, qui n'est pas acceptable pour toutes les applications.

Dans cet article, nous considérons la reconnaissance du contour d'une image binaire comme une séquence de segments de droites numériques sans perte d'information.

2. Contour en tant que séquence de segments de lignes numériques

Cette section considère l'analyse structurelle des contours d'image comme une séquence de segments de lignes numériques, qui sont les données initiales pour segmenter le contour en arcs de courbes numériques et segments de lignes numériques.

Bornons-nous à considérer des images binaires dont les objets sont entièrement déterminés par leurs contours englobants. Des arcs de courbes numériques, ainsi que des segments de lignes numériques, sont formés en échantillonnant des images contenant des contours formés par des segments de lignes droites et des arcs de courbes.

Caractéristiques des segments de lignes droites et des arcs de courbes sont perdus lors de la transformation. Lors de la visualisation d'une image échantillonnée à un grossissement suffisant, il est souvent difficile de reconnaître des segments de ligne individuels et des arcs de courbes dans une séquence.

sections verticales et horizontales. Des difficultés supplémentaires surviennent lors du traitement en raison du fait que les lignes de contour - lignes mathématiques sans épaisseur - sont affichées sur l'écran du moniteur en séquences connectées de pixels, c'est-à-dire des lignes visuelles avec épaisseur.

Pour éliminer les problèmes qui en découlent, nous considérerons l'image obtenue à partir de l'original à la suite de la discrétisation comme un complexe cellulaire bidimensionnel. Dans ce cas

les pixels sont des éléments bidimensionnels de ce complexe cellulaire. En plus des pixels, il y a des fissures et des points. Le crack est

côtés de pixels qui sont des éléments unidimensionnels. Les points sont les extrémités des fissures et les points d'angle des pixels. Les points sont des éléments de dimension zéro. Alors

Ainsi, dans le cas considéré, le contour de l'objet est une séquence fermée connexe de fissures de contour, limitrophe entre les pixels de l'objet et le fond. Un contour peut être décrit comme une séquence de coordonnées de points entiers,

limiter les fissures de contour. Comme le montre la , la représentation du plan image sous la forme

Le complexe cellulaire offre de nombreux avantages. En particulier, la frontière de la région devient une courbe mince avec une aire nulle.

Sur la fig. La figure 1 montre un exemple de contour initial d'un objet formé par un arc de courbe et un segment de droite, ainsi que son équivalent numérique en une séquence de fissures. Les points appartenant à des fissures de directions différentes sont numérotés. Comme dans les travaux, par élément b, nous entendons une séquence connexe de fissures de même direction, partant d'un point et se terminant par une fissure de même direction ou de direction perpendiculaire. Sur la fig. 1 montre une des partitions possibles du contour en éléments b, qui sont formés par des fissures entre les points : (0-2), (2-4), (4-6), (6-8), (8 -9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25 ), (25-27 ), (27-0). Chaque élément b est caractérisé par les paramètres suivants : direction par rapport à son point initial g (pris g = 0 - pour la direction vers le haut, 1 - vers la droite, 2 - vers le bas, 3 - vers la gauche) ; l - le nombre de fissures dans la direction g (! = 1,2,...); la direction de la dernière fissure q par rapport à la direction g des fissures précédentes (q = -1 - la dernière fissure est dirigée vers la gauche par rapport à la direction g, +1 - vers la droite, 0 - coïncide avec la direction g ). Le nombre de fissures l sera appelé par convention la "longueur" de l'élément b. Pour l'élément b (0-2) g =0, !=3, q =+1. Pour l'élément b (27-0) g =3, =1, q =0.

Le procédé de sélection de segments de lignes numériques dans le contour utilise la propriété suivante de la séquence d'éléments b qui forment le segment. Une telle séquence comprend des éléments b avec les mêmes valeurs de g, q; leurs longueurs prennent les valeurs !, +1. Et

l'alternance des b-éléments de longueurs !, +1 est déterminée par la fraction continue obtenue en divisant des nombres entiers n = Ax = |x1 - x2| et m = Ay = |y1 - y2\, où (x1zy1), (x2,y2) sont les coordonnées du premier

et extrémités du segment : ou

Pour être précis, nous supposons que n > M. Comme il ressort de la formule (1), l - la partie entière de la division de n par m - correspond dans le segment de la droite numérique au nombre de l fissures successives de même direction. Avec la fissure perpendiculaire adjacente, ils forment l'élément b de longueur!. k1 éléments b successifs de longueur l et un élément b de longueur!+1 (ou k1 éléments b successifs de longueur +1 et un élément b de longueur!) forment un élément K1 de "longueur" k1 (par analogie avec "longueur" élément b). Un élément b qui diffère en longueur de 1 des éléments b consécutifs sera appelé un élément b modifié d'un élément K1 donné. De même, k2 éléments K1 consécutifs de "longueur" k1 et un élément K1 de "longueur" k1 +1 (ou k2 éléments K1 consécutifs de "longueur" k1 +1 et un élément K1 de "longueur" k1) forment K2- l'élément "longueur" k1. Alors

k + k 2 + k z + ... + kg

jusqu'à épuisement des membres de la fraction continue. K1 -élément (généralement K-1 -élément), qui diffère en longueur de 1 des éléments K1 consécutifs (Kg-1 -élément), nous appellerons l'élément K1 modifié (Kg-1 -élément) de ce K2 - élément (Kg -élément). Ainsi, à chacun

un segment numérique de droite correspond à une fraction continue dont les éléments déterminent la structure de ce segment.

Dans le contour de la Fig. 1 les segments suivants de lignes droites numériques peuvent être sélectionnés : 0-3, 3-9, 910, 10-17, 17-0.

3. Sélection de segments de ligne numériques dans le contour

Lors du traitement de contours d'images, en particulier d'images binaires, dans une séquence de fissures formant un contour, il est nécessaire de sélectionner des parties de la séquence qui forment des segments de ligne. Ce problème peut être considéré comme un problème de détermination des éléments d'une fraction continue à partir d'une séquence de L-éléments du contour. Ce problème est inverse par rapport au problème de détermination de la structure d'un segment de droite par la séquence des membres d'une fraction continue, obtenue comme le rapport des différences des coordonnées du début et de la fin du segment.

Le procédé de sélection de segments d'une ligne numérique consiste à effectuer séquentiellement les actions suivantes.

1. Sélection de la séquence des éléments b dans la séquence des fissures. Cette action correspond à la définition d'une partie entière ! tir continu (1).

2. Isolation de la séquence d'éléments Kg avec r = 1 dans la séquence d'éléments b, et l'un des éléments b de chaque élément K1 doit contenir 1 fissure de plus ou de moins que les autres. Cette action correspond à la définition du k1 -ième élément de la fraction continue (1). Après son exécution, la valeur de r doit être augmentée de 1.

3. Isolement de la séquence des éléments Kg dans la séquence des éléments Kg-1,

de plus, un des éléments Kg-1 de chaque élément Kg doit contenir un élément K-2 de plus ou de moins que les autres. Cette action correspond à la définition du k(-ième élément de la fraction continue (1). Après son exécution, la valeur de r doit être augmentée de 1.

4. Le paragraphe 3 est répété jusqu'à ce qu'il soit encore possible à partir d'éléments Kr consécutifs

forme Km-élément.

5. Les points frontières sont déterminés entre deux éléments b adjacents qui ne sont pas inclus dans le même élément Kg. Ces points sont les extrémités des segments de ligne numériques qui forment le contour.

Considérez l'algorithme de sélection des segments de ligne dans la séquence d'éléments b

Soit [b5 (/5,gs,qs)); s = 0,1,...,t - séquence d'éléments L formant le contour ; x5, y5 - coordonnées du début du e-ème élément b ; [hu, y y); y = ; r = 0,1,...,!; !< £ - множество

points de rupture des contours. Les points d'arrêt définissent les extrémités des segments de ligne qui forment le chemin. Trouver des points de rupture signifie déterminer les segments de ligne qui forment le contour.

Chaque segment considéré est caractérisé par un élément Kg, ainsi qu'une chaîne

tir. Au moment initial de la reconnaissance du segment, les éléments de la fraction continue correspondante sont égaux à 0. Un segment peut être considéré comme reconnu si les paramètres de l'élément Kr sont reconnus, y compris son ordre r et les valeurs des éléments de la fraction continue correspondante.

1. Conditions initiales.

Les séquences [b5 (/5, gs, qs)) et (x5, y5) sont données.

Il faut trouver les coordonnées des points de rupture |x;.,y,).

k0r:= 0, k1r:= 0, k2r:= 0,..., kr:= 0 - valeurs de travail des éléments de fraction continue.

Prenons comme point de départ du premier segment le point 5 = 0 ; je =0 ; je=0.

2. Prenez le premier élément b de la séquence au début du premier segment de droite. Son point de départ est x5,y. La longueur /=/0 est aussi la valeur du premier élément de la fraction continue.

5 :=5+1 ; k1p :=k1p+1.

3. Vérifiez pour l'élément b suivant s'il forme avec les précédents un élément K0.

3.1. Si ((q3 == q3-1) && (q3 == 73-1)&& (4 == /3-1)), alors la suite du Kr-élément k0p:= k0p +1; 5 := 5 + 1 ; et la continuation du segment de ligne. Passez au point 3.

3.2. Si ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1)), alors la fin du segment de ligne. Passez au point 5.

3.3. Si ((&== 93+1) && (%== 73+1)&& ((/3+1== /3+1)1! (/3 - 1 == /3+1))), puis la complétion de l'élément K0 ; å = å+1.

4. Vérification de la suite / achèvement du K (-élément.

4.1. Si (k == 0), alors k ^= k^ ; cr:= 0 ; k^1p := k1+ 1p+1 ; 5 :=5 +1 ; le début de l'élément Km.

Passez au point 3.

4.2. Si ((k SI 0)&&(k == k^)), alors k^1p:= k^1p+1 ; 5 := 5+1 ; continuation de l'élément Ki+1. Passez au point 3.

4.3. Si ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^))), alors Ї := +1; la fin de l'élément Km.

Passez au point 4.

4.4. Si ((^φ0)&&(|k - k1p|>1)), alors la fin du segment est une transition directe vers l'item 5.

5. Fin de segment.

X] = Xs ; y \u003d Uz; k1p:= 0, k2p:= 0,., kіp:= 0 ; k := 0, k2 := 0,., k := 0.

Si (s< S), то s:= s +1; переход к п. 2.

Sinon, la fin de la séquence de L -éléments. Fin de l'algorithme.

En fait, l'algorithme proposé trouve des éléments de la fraction continue et pour chaque élément Kt obtenu et vérifie si la fraction continue de l'élément Kt nouvellement construit convient à celle déjà construite.

4. Le programme de sélection des segments d'une ligne numérique

Comme le montre la description de l'algorithme, celui-ci contient un nombre important de sauts conditionnels, dont l'utilisation contredit les recommandations de la programmation structurée en raison des difficultés qui surviennent lors du débogage des programmes. De plus, le nombre de paramètres Kt à l'avance

ne peut pas être déterminé, car la variable t n'est pas bornée à l'avance. Limiter la valeur de t

Cela signifie limiter la taille de l'image à l'avance. La mise en œuvre logicielle, en particulier le débogage de l'algorithme proposé par des moyens triviaux, pour les raisons indiquées, est significativement difficile. Il est possible de réduire les difficultés de développement et de débogage d'une implémentation logicielle si des outils modernes de programmation orientée objet sont utilisés.

L'algorithme proposé est implémenté sous la forme du programme LINESEGM, qui fait partie du progiciel de laboratoire pour le traitement d'images dans l'environnement Visual C++.

Comme information initiale, le programme LINESEGM utilise des séquences de L-éléments construits pour chacun des contours de l'image traitée.

Le résultat du programme est une séquence connexe de segments de droites numériques construits pour chaque contour, représentés par les coordonnées des extrémités des segments.

Comme on peut le voir à partir de l'algorithme, les opérations de construction de Kt -éléments à partir de Kt-l -éléments

sont les mêmes pour toutes les valeurs de t. Notez que la valeur initiale t = 0 augmente de 1 à chaque exécution de l'algorithme.La classe spéciale CKForLn comprend des méthodes correspondant aux opérations de l'algorithme. Lors du fonctionnement du programme qui implémente l'algorithme, à chaque augmentation de t de 1, un nouvel objet est créé contenant des fonctions qui effectuent les opérations de l'algorithme pour chaque valeur de t.

Considérant qu'au niveau zéro les K0 -éléments ne sont pas formés à partir de K -éléments, mais à partir de L -

éléments, une modification spéciale de la classe CKForLn, la classe Cmini, a été créée pour implémenter l'algorithme au niveau zéro.

Le principe de fonctionnement du programme est que pour chaque valeur de t, le programme implémente un objet de classe CKForLn du t-ème niveau, qui contient des fonctions qui déterminent les paramètres de l'élément Kt. Les paramètres initiaux de l'élément Kt sont les paramètres déjà

Kt-l -élément complété dont les paramètres ont été définis par un objet de classe CKForLn t-1

Waouh niveau.

Les objets de la classe CKForLn sont implémentés lorsque les conditions se présentent, à savoir: la nécessité de construire un élément K du niveau suivant, et sont accumulés dans un tableau dynamique spécial. L'objet de niveau zéro est créé immédiatement au démarrage du programme.

L'implémentation d'objets dans un tableau dynamique lorsque t augmente vous permet de ne pas imposer de restrictions sur la taille de l'image. Les limites de taille d'image ne sont déterminées que par les ressources de l'ordinateur utilisé.

Lors de la description du fonctionnement du programme, le concept de Kt complété sera utilisé -

élément. Chaque élément Kt complété contient kt Kt-l éléments et un élément Kt-l modifié qui contient kt-l ±1 Kt-2 éléments, contrairement à un élément Kt incomplet qui ne contient pas d'élément Kt incomplet.

La classe CKForLn inclut les méthodes suivantes.

1. Méthode DK(), (define K-element) - définit un K-element.

Déterminer un élément Kt signifie déterminer le nombre d'éléments Kt-1 qui forment un élément Kt donné.

2. Méthode VK§, (vérifier l'élément K) - vérifier l'identité de l'élément K considéré avec l'élément K de même niveau, préalablement déterminé par la fonction de la méthode DK().

3. Méthode DEO, (définir la fin de l'élément K) - pour déterminer la fin de l'élément K, c'est-à-dire, lors de la définition de l'élément Kt, trouver son élément Kt-1 modifié. La fonction méthode DE() de niveau t-1 est appelée par la fonction méthode DK() de niveau t.

4. Méthode VE(),(vérifier la fin de l'élément K) - vérifier l'identité de la fin de l'élément K considéré avec l'élément K modifié, précédemment défini par la fonction de la méthode DE ().

La classe Cmini comprend les mêmes méthodes, qui diffèrent des méthodes de la classe CKForLn en ce que les méthodes de la classe Cmini opèrent sur les éléments L et déterminent ou vérifient les éléments K0.

Méthodes de classe Cmini

Les méthodes de la classe Cmini utilisent comme données initiales des séquences de L -éléments construits pour chacun des contours de l'image traitée, à partir du numéro courant du L -élément au moment où la fonction méthode est appelée.

La fonction de la méthode DK() de la classe Cmini compare les paramètres de chaque élément L suivant avec les paramètres de l'élément L initial jusqu'à ce qu'ils correspondent. Si les paramètres ne correspondent pas, la fonction DK() vérifie si l'élément K0 est complété et se termine

travail. Un élément K0 est considéré comme terminé s'il se termine par un élément L modifié, dont la longueur diffère de 1 des autres éléments L de l'élément K0 (opération 3.1 pour le début du segment - t = 0).

La fonction de la méthode VK() vérifie si les paramètres des éléments k0 L suivants correspondent aux paramètres des éléments L de l'élément K0 précédemment définis par la fonction de la méthode DK()

le même niveau. Si les paramètres de l'élément K0 courant coïncident avec les précédents

définie, la fonction VK() génère un signe de continuation de segment et se termine (opération 3.1 pour la continuation de segment - t > 0).

À autrement la fonction VK() génère un signe de fin de segment et termine

La fonction de méthode DE() compare les paramètres de l'élément Kci courant avec les paramètres de l'élément K0 précédemment définis par la fonction DK() pour déterminer si l'élément K0 courant a changé. Si les autres paramètres sont égaux, le nombre de L -éléments k0

de l'élément K0 modifié par rapport à l'élément K0 précédemment défini

la fonction DK() doit différer de 1 (opération 3.2, 3.3 pour déterminer la complétion

K0 -élément initial du segment - t = 0). Résultat - paramètres de l'élément K0 modifié

sont utilisés dans la méthode VE() de la classe Cmini.

La fonction de méthode VE() compare les paramètres de l'élément K0 courant avec les paramètres de l'élément K0 modifié précédemment définis par la fonction DE() pour déterminer si

coïncident-elles (opération 3.2, 3.3 pour la suite du segment - t > 0). Le résultat - un signe de correspondance ou de non-concordance - est utilisé dans la méthode VK() de la classe CKForLn.

Méthodes de la classe CKForLn

Les méthodes utilisent comme données initiales les paramètres des éléments K construits pour le niveau le plus bas. Autrement dit, pour déterminer les paramètres de l'élément Kt, les paramètres sont utilisés

éléments Kt-l déjà construits.

La fonction de la méthode DK() du niveau t de la classe CKForLn, lors de la détermination des paramètres de l'élément ^, appelle la fonction VK() du niveau t-1 de la classe CKForLn, qui vérifie si le Kt déjà défini L'élément -l est suivi d'un élément Kt-l avec les mêmes paramètres. Si oui, l'appel de la fonction VK() est répété. Dans ce cas, le nombre de répétitions est compté, c'est-à-dire que le paramètre kt est déterminé.

Sinon, la fonction DK() de niveau t appelle la fonction DE() de niveau t-1 pour déterminer l'élément Kt-l modifié et sort. En fin de travail, la fonction DK() de niveau t de la classe CKForLn détermine les paramètres et génère des signes d'un élément Kt complété ou incomplet (opération 4.1, 4.2 avec la valeur maximale courante de t).

La fonction de la méthode VK() de niveau t de la classe CKForLn vérifie si les paramètres des kt Kt -éléments suivants sont les mêmes que les paramètres de l'élément Kt précédemment définis

fonction de la méthode DK() de même niveau. Si les paramètres de l'élément Kt actuel correspondent à

précédemment fonction définie DK() Kt -élément de même niveau, fonction VK()

génère un signe de la poursuite du segment et termine le travail.

Sinon, la fonction VK() génère un signe de fin de segment et sort (opération 4.1,4.2 avec la valeur courante de t inférieure au maximum).

Élément Kt La fonction de la méthode DE0 niveau t de la classe CKForLn, lors de la détermination des paramètres d'un élément Kt, compare les paramètres de l'élément Kt courant avec les paramètres de l'élément Kt précédemment définis par la fonction DK() pour déterminer si l'élément Kt actuel a changé. Si les autres paramètres sont égaux, leurs valeurs kt-1 doivent différer de 1. Si cette condition est remplie, la fonction DE() génère un signe de l'élément Kt modifié et

se termine (opération 4.3, 4.4 à la valeur maximale courante de t).

La fonction de la méthode VE() de niveau t de la classe CKForLn compare les paramètres de l'élément Kt courant avec les paramètres de l'élément Kt modifié précédemment alloués par la fonction DE() pour déterminer si leurs valeurs de paramètres correspondent.

Si les valeurs des paramètres de l'élément Kt actuel coïncident avec le précédent

définie par la fonction DK() de même niveau, la fonction VK() génère un signe que les valeurs des paramètres correspondent et se termine (opération 4.3,4.4 avec la valeur actuelle de t inférieure au maximum).

Le chronogramme (Fig. 2) illustre le fonctionnement du programme LINESEGM à partir de l'exemple de la reconnaissance d'un segment de droite. La partie inférieure de la figure montre une partie de la ligne numérique, constituée d'éléments en L de mêmes directions principales et auxiliaires et de longueurs différentes.

À l'étape 0, un objet de la classe Stinі est créé, qui définit les paramètres de l'élément K0.

A l'étape 10, la détermination des paramètres de l'élément K0 est terminée et un objet 1 de la classe CRORGn est créé, qui utilise les fonctions de l'objet précédemment créé pour déterminer les paramètres de l'élément K1. A l'étape 19, la définition des paramètres de l'élément K1 est terminée et un objet 2 de la classe CCROGn est créé, qui utilise les fonctions des objets précédemment créés pour déterminer les paramètres de l'élément K2. A l'étape 49, la détermination des paramètres de l'élément K2 est terminée et un objet 3 de la classe CRORGn est créé, qui utilise les fonctions des objets précédemment créés pour déterminer les paramètres de l'élément K3. A l'étape 79,

condition terminale. Le fonctionnement du programme est décrit en détail dans l'annexe.

Dans la section 0-6, deux éléments b forment un élément K0 inachevé. Il est évident que b -

l'élément 3-6 de longueur 3 complète le segment de droite, puisque l'élément b 6-7 de longueur 1 ne peut pas être sa continuation. Ainsi, l'élément b 6-7 est le début du segment de la ligne numérique.

Sur la fig. 3 montre un exemple du fonctionnement du programme. Le contour de l'image binaire de la flèche bouclée est divisé par des carrés en segments de droite. Le résultat du programme - une séquence de segments de ligne - a été utilisé pour mettre en évidence les arcs de courbes numériques. Les grands carrés indiquent les limites des arcs de courbe numériques.

Le fonctionnement du programme a été testé sur un nombre important (plus de 2000) d'exemples et est utilisé dans l'étude de l'analyse structurelle des images en demi-teintes.

5. Travaux du programme de reconnaissance des segments de ligne

Considérons le travail du programme iEBESM sur l'exemple de la fig. 4. La partie inférieure de la figure montre une partie de la ligne numérique, constituée d'éléments b de mêmes directions principales et auxiliaires et de longueurs différentes. Dans la section 0-6, deux éléments b forment un K0- incomplet

Riz. 3. Un exemple du travail du programme d'analyse structurelle du contour - segmentation du contour par segments de droites numériques

élément. Évidemment, le b-élément 3-6 de longueur 3 complète le segment de droite, puisque le b-élément 6-7 de longueur 1 ne peut pas être sa continuation. Ainsi, l'élément b 6-7 est le début du segment de la ligne numérique.

Le travail du programme pour déterminer le segment suivant de la ligne droite est lancé par la fonction OK() du niveau zéro, qui détermine l'élément K0 terminé 6-10, composé d'éléments b

longueurs 1,1,2 ; k0=2. Cet élément K0 est l'élément de départ de l'élément K1. Le programme forme un objet de premier niveau et transfère le contrôle à la fonction OK() de cet objet. La fonction OK() du niveau 1 appelle la fonction VKQ du niveau 0. La fonction VKQ compare les paramètres des éléments b de l'élément K0 6-10 avec les éléments b suivants et confirme la présence de l'élément K0 10-14,

identique à K0 -élément 6-10. En continuant, la fonction VKQ détecte que les éléments b suivants ne forment pas le même élément K0, quitte et transfère le contrôle à la fonction OK() de niveau 1. La fonction OK() de niveau 1 appelle la fonction OE() de niveau 0. avec l'élément b 6-7, détermine la présence d'un élément K0 modifié 14-19, constitué d'éléments b de longueurs 1,1,1,2 ; k0=3, sort et transfère le contrôle à la fonction OK() de niveau 1. Cette fonction détermine la présence d'un élément K1 complété 6-19, composé de deux K0 -

éléments 1,1,2, (k1=2) et un changé 1,1,1,2 (k0=3). Le programme forme un objet de deuxième niveau et transfère le contrôle à la fonction OK() de cet objet. La fonction OK() de niveau 2 appelle la fonction VKQ de niveau 1, qui à son tour appelle la fonction VKQ de niveau 0. La fonction VKQ compare les éléments b de l'élément K0 6-10 avec les b suivants

et confirme la présence des éléments K0 19-23, 23-27, identiques à l'élément K0 6-10, c'est-à-dire qu'il y a le même nombre d'éléments K0 contenus dans l'élément K1 6-19. Ensuite, la fonction VKQ de niveau 0 rend le contrôle avec le signe de continuer le segment de la fonction VKQ de niveau 1. La fonction VKQ appelle la fonction VE0 de niveau 0, qui détermine la présence d'un K0 modifié -

élément 27-32, identique à l'élément K0 14-19. Ainsi, K1-élément 19-32 est défini,

identique à K1 élément 6-19. De plus, la fonction VKQ de niveau 1 ne détermine pas l'élément K1 suivant, identique à l'élément K1 6-19, car la fonction de niveau 0 VE0 ne détermine pas l'élément K1 modifié, identique à l'élément K1 6-19, à partir de l'élément b 40-41, et rend le contrôle de la fonction OK() de niveau 2. La fonction OK() de niveau 2 appelle la fonction OE() de niveau 1, qui détermine la présence d'un élément K1 modifié 32-49, consistant en K0 éléments 32-36, 36- 40,

40-44, 44-49. Ensuite, l'élément K2 6-49 est déterminé, l'objet de niveau 3 est formé, l'élément K2 modifié 49-79 est déterminé. Ces deux éléments K2 forment l'élément K3 6-79. Ceci termine la construction du segment, puisque les éléments b suivants 79-81 et 81-83 ne forment pas un élément K0,

identique à l'élément K0 6-10, et la fonction VKQ de niveau 0 ne génère pas d'indicateur de continuation

segment. Dans la séquence d'éléments b, un segment de la ligne droite numérique 6-79 est sélectionné. Le programme commence la définition du segment suivant, en commençant par l'élément b 80-82.

b. résultats

1. Un nouvel algorithme de sélection de segments de ligne dans les contours d'image et une implémentation logicielle non triviale de l'algorithme sont proposés, qui permettent d'obtenir une solution exacte au problème de reconnaissance des contours d'image en tant que séquences de segments de ligne.

2. L'implémentation logicielle de l'algorithme de sélection des segments de ligne dans les contours de l'image est réalisée à l'aide de des moyens modernes la programmation orientée objet, qui permettait de ne pas imposer de restrictions explicites sur la taille de l'image traitée tout en maximisant l'utilisation des ressources de l'ordinateur utilisé.

3. Sur la base de l'algorithme proposé et de son implémentation logicielle, une solution théorique a été obtenue et des expériences ont été menées sur la reconnaissance des arcs de courbes numériques et la segmentation du contour d'images binaires sur un segment de lignes numériques et des arcs de courbes numériques.

BIBLIOGRAPHIE

1. Kovalevsky V.A. Applications of Digital Straight Segments to Economical Image Encoding, Actes du 7ème Atelier International, DGCI"97, Montpellier. - France, 1997. - 3-5 décembre. - P. 51-62.

2. Kalmykov V.G. Méthode structurelle pour décrire et reconnaître des segments de lignes numériques dans les contours d'images binaires // Piece Intellect. - 2002. - N° 4. - C. 450-457.

3. Kalmykov V.G., Vishnevsky V.V. Analyse des contours d'objets dans des images binaires // Machines et systèmes mathématiques. - 1997. - N° 2. - S. 68 - 71.

4. Kalmikov V.G. L'arc de courbe numérique - désignation et stagnation // Traitement du signal et reconnaissance d'images et reconnaissance d'images. Actes de la Conférence internationale panukrainienne. - Kiev. - 2004. - 11 - 15 Jovten.

Formulation du problème déterminé par le but et les possibilités de sa mise en œuvre.

Cibler. Développer un programme pour classer les pièces rectangulaires en pièces de qualité et défectueuses.

Opportunités pour la mise en œuvre de la tâche déterminé par les capacités de l'ordinateur. Un ordinateur est capable de traiter des informations numériques dans une séquence algorithmique. Pour réaliser les capacités d'un ordinateur, il est nécessaire de simuler le problème à résoudre.

La modélisation à l'aide d'un ordinateur implique le passage d'un objet réel (le monde) à une description codée de ses propriétés à l'aide de données et d'opérations sur celles-ci. Une telle transition, en règle générale, s'effectue en plusieurs étapes:

Abstraction- sélection des caractéristiques les plus significatives de l'objet en fonction de la tâche.

Il est nécessaire de mener des recherches qui vous permettent de passer de l'objet de modélisation au sujet de modélisation, en éliminant tout ce qui est superflu conformément à l'objectif de la tâche

En quoi un rectangle est-il différent des autres quadrilatères ?

• Égalité des côtés opposés.
• Parallélisme des côtés opposés.
• Égalité des diagonales.
• Tous les angles sont droits.

Quel est le nombre minimum de fonctionnalités nécessaires pour résoudre le problème de manière unique ?

• Egalité de 2 côtés opposés + égalité des diagonales.
• Parallélisme de 2 côtés opposés + égalité des diagonales.
• Trois coins sont à droite.

Ainsi, grâce à l'abstraction, nous avons obtenu un modèle d'information verbal. Mais, c'est encore incompréhensible pour l'ordinateur. Il comprend le modèle mathématique présenté comme un algorithme et implémenté dans un logiciel.

Méthodologie pour la mise en œuvre de la tâche.

Un dessin d'une pièce de qualité (rectangle) ou d'une pièce défectueuse (quadrilatère) est réalisé à partir de segments (commande LIGNE) dans le système graphique AutoCAD et exporté vers . Le programme kntrs.lsp() lit les données de segment de ligne (coordonnées des sommets) à partir d'un fichier DXF et les écrit dans un fichier texte vrtks.txt dans un ordre circulaire.

Le fichier texte vrtks.txt peut être créé manuellement en prenant les coordonnées des sommets directement à partir du dessin.

Le programme rct.lsp développé doit lire les données du fichier vrtks.txt, les analyser et générer dans le fichier result.txt un enregistrement sur la conformité de la pièce aux exigences (rectangle ou non).

Formalisation des fonctionnalités

Egalité des longueurs des segments (côtés ou diagonales) : La longueur de chaque segment est déterminée comme l'hypoténuse d'un rectangle rectangulaire (selon le théorème de Pythagore) par la différence des coordonnées des segments :

(setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))

Parallélisme des lignes : K2=K1, où Pour est la pente de la droite K=(Y2-Y1)/(X2-X1)

Comment formaliser la notion d'"Angle Droit" ? Dans le cadre de la tâche, la présence de " angle droit» peut être déterminé à partir de la perpendicularité des segments : K2= -1/K1, où Pour est la pente de la droite. K=(Y-Y0)/(X-X0).

Affichage du modèle sur l'ordinateur

Toute information est finalement affichée dans un ordinateur à l'aide de nombres binaires (codes) dans un modèle de machine interne. Auparavant, le codage était effectué par un programmeur. Aujourd'hui, la plupart des programmes sont créés dans des langages algorithmiques.

Lorsque nous regardons une image en deux dimensions d'une scène en trois dimensions (dans une image, une photographie, un écran de moniteur), il nous semble que tous les objets que nous pourrions voir si nous observions directement la même scène dans la vie sont directement présents là. Pendant ce temps, tout ce qui nous est réellement donné dans une image en deux dimensions est champ visible, ce qui n'est que quelques fonction de répartition de la luminosité ou alors couleurs sur un plan à deux dimensions : F(X, y) , où X et y sont des coordonnées cartésiennes décrivant le plan image.

De plus, si vous vous approchez de l'écran d'un écran d'ordinateur, vous pouvez voir que l'image à l'écran n'est en fait pas lisse et continue, mais est une "mosaïque" discrète composée de rectangles colorés individuels disposés dans une matrice rectangulaire régulière. C'est l'image numérique. D'un point de vue mathématique Image digitale est une matrice Im à deux dimensions de taille (DimXDimY), où x est un entier de 0 à DimX– 1, décrivant le numéro de l'élément dans la ligne de la matrice, y est un entier de 0 à DimY– 1, décrivant le numéro de ligne de la matrice dans laquelle se trouve l'élément donné. Dans le même temps, l'élément de l'image numérique lui-même (une cellule d'une matrice rectangulaire) est appelé pixels(pixel, élément d'image). Dans le cas le plus simple, chaque pixel Im a une valeur entière scalaire proportionnelle à la valeur de la fonction de répartition de la luminosité F(X, y) en un point donné du plan.

Sur la fig. Dans la figure 1.1.1, le côté gauche montre une image d'un visage féminin rendue sous forme d'image, et le côté droit montre un fragment d'image agrandi du même visage (œil droit), où chaque élément d'image a sa valeur de pixel numérique correspondante. Les éléments légers de l'image correspondent à b à propos Valeurs plus grandes de la matrice, sombres - valeurs plus petites. L'image numérique ne contient aucune autre information.

@Riz. 1.1.1 Image numérique comme matrice d'intensité bidimensionnelle

Pour commencer à étudier la vision artificielle, il est nécessaire de comprendre clairement que seul et exclusivement un tableau bidimensionnel de nombres d'un format ou d'un autre est stocké dans un ordinateur sous forme d'image numérique. Toute autre donnée que nous souhaiterions extraire de l'image (formes, lignes, objets, dimensions, contenu du texte affiché, etc., etc.) ne peut être obtenue qu'en appliquant un certain nombre de traitements et d'analyses d'images. procédures que nous devons soit programmer nous-mêmes, soit utiliser des procédures toutes faites disponibles dans des progiciels d'analyse d'images bien connus. En même temps, pour résoudre des problèmes simples de vision par ordinateur fonds prêts à l'emploi sont susceptibles de se trouver dans les bibliothèques standards de procédures de traitement d'images, pour résoudre des problèmes plus complexes il faudra combiner certaines procédures toutes faites, et pour de nombreuses tâches tout à fait "ordinaires" que la vision "biologique" d'une personne, il semblerait, résout facilement et sans effort, la vision artificielle par ordinateur jusqu'à n'a toujours pas de solutions et continue toujours à les chercher. Après tout, en utilisant sa vision naturelle, une personne navigue facilement dans n'importe quel environnement, reconnaît des objets, choisit un chemin, conduit une voiture et bien plus encore. Pourquoi un ordinateur qui reçoit une image d'une caméra vidéo ne peut-il pas faire tout cela ? Peut-être est-ce la structure de l'œil humain ?

En fait, l'œil humain, comme une caméra vidéo, ne forme qu'un "champ visible", semblable à une image numérique. Dans ce cas, le système optique, composé de la pupille et de la lentille, projette une image bidimensionnelle sur la rétine, où des cellules photosensibles ("bâtonnets" et "cônes") convertissent l'image résultante en influx nerveux. Et seulement après cela, un mécanisme complexe de traitement des informations reçues, fonctionnant dans le département correspondant de notre cerveau, interprète ces impulsions comme une image de la scène visible qui nous est compréhensible. Ainsi, chez l'homme, la fonction de « vision » est assurée non seulement par l'œil, mais par le système « œil + cerveau » (« capteur + ordinateur »). Ce sont les algorithmes de traitement de l'information intégrés au cerveau qui permettent à une personne de comprendre ce qu'elle voit. Le rôle de ces algorithmes intégrés peut être illustré par l'exemple suivant.

Quand, au milieu du XXe siècle, les chirurgiens ophtalmologistes ont appris à pratiquer des opérations sur le cristallin, de nombreuses personnes aveugles de naissance avaient la capacité technique de voir clairement. C'est-à-dire qu'après une telle opération chez une personne jusqu'alors aveugle (la lumière ne traversait tout simplement pas la lentille), l'image sur la rétine a commencé à se former et les signaux correspondants ont commencé à pénétrer dans le cerveau exactement de la même manière qu'il se passe dans personnes en bonne santé. Malheureusement, dans ce cas, « voir la lumière » ne signifie pas « commencer à voir ». Comme l'histoire ultérieure l'a montré, la majorité des patients adultes "techniquement éclairés" n'ont jamais été en mesure d'obtenir des résultats plus significatifs dans le champ de vision que la reconnaissance de formes géométriques simples - et même cela leur a demandé de sérieux efforts conscients. La reconnaissance des personnes par leurs visages et leur orientation dans l'espace restaient pour eux des tâches écrasantes. Le fait est que ces mécanismes intégrés d'analyse visuelle "automatique" qui se développent chez les personnes dans la petite enfance n'ont pas été développés en temps opportun chez ces patients, et ils se sont retrouvés dans la position d'un ordinateur doté d'un périphérique d'entrée d'image, mais ne dispose pas du logiciel nécessaire à son analyse.

Afin de nous convaincre enfin de la complexité de la tâche d'analyse d'une image qui est un tableau à deux dimensions de données numériques, nous allons essayer de nous mettre à la place d'un programme informatique qui traite des nombres abstraits. Pour ce faire, changeons mentalement la modalité de perception de l'image - nous la transférerons du domaine visuel au domaine tactile. Imaginons un tableau bidimensionnel de valeurs d'intensité sous forme de damier, dont la taille est égale à la taille de l'image (DimXDimY), et une colonne est collée au centre de chaque cellule, dont la hauteur est proportionnel à la valeur du pixel d'image correspondant. En d'autres termes, considérons une image bidimensionnelle comme une sorte de surface tridimensionnelle conditionnelle. Sur la fig. 1.1.2 à gauche, un fragment d'un visage féminin est représenté sous forme d'image, et à droite est représenté comme un relief pseudo-tridimensionnel.

@Riz. 1.1.2. Image numérique en pseudo-relief 3D

Imaginez maintenant que vous deviez, sans regarder l'image, ressentir le "relief" qui lui correspond et essayer de déterminer ce que représente exactement ce "relief" - une maison, un chien ou un œil humain ? Comme le montrent les expériences, la personne moyenne n'est pas capable de faire face à une telle tâche. Même la reconnaissance des formes géométriques les plus simples dans une telle représentation en "relief" sera associée à des efforts importants et nécessitera le développement conscient d'une compétence, d'une stratégie et d'algorithmes de palpation particuliers. Telle est, malgré l'apparente simplicité de l'objet « image numérique », la véritable complexité des tâches de vision par ordinateur et par machine.