Quelques mots sur la reconnaissance des formes. Image raster image sous forme de tableau de données bidimensionnel Exemple de reconnaissance numérique de triangles
Lorsque nous regardons une image bidimensionnelle d'une scène tridimensionnelle (dans un tableau, 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 de la vie sont directement présents. là. Pendant ce temps, tout ce que l'on nous donne réellement dans une image bidimensionnelle, c'est champ visible, ce qui ne représente qu'une partie fonction de répartition de la luminosité ou couleurs sur un plan bidimensionnel : F(X, oui) , Où X Et oui– Coordonnées cartésiennes décrivant le plan image.
De plus, si vous vous approchez d’un écran d’ordinateur, vous pouvez voir que l’image sur l’écran n’est pas réellement 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. Il s'agit d'une image numérique. D'un point de vue mathématique Image digitale est une matrice bidimensionnelle Im de taille (DimXDimY), 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 la ligne de la matrice dans laquelle se trouve cet élément. Dans ce cas, l'élément de l'image numérique elle-même (une cellule d'une matrice rectangulaire) est appelé pixels(pixel, élément d'image). Dans le cas le plus simple, chaque pixelIm a une valeur entière scalaire proportionnelle à la valeur de la fonction de distribution de luminosité F(X, oui) en un point donné du plan.
En figue. 1.1.1 à gauche se trouve une image d'un visage de femme, représenté comme une image, et à droite se trouve un fragment agrandi d'une image du même visage (œil droit), où pour chaque élément de l'image la valeur numérique correspondante du pixel est indiqué. Les éléments lumineux de l'image correspondent à b Ô valeurs matricielles plus grandes, sombre – valeurs plus petites. L'image numérique ne contient aucune autre information.
@Riz. 1.1.1 Image numérique comme matrice d'intensité bidimensionnelle
Lorsque vous commencez à étudier la vision par ordinateur, vous devez clairement comprendre 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. Toutes les autres données que nous souhaitons extraire de l'image (formes, lignes, objets, dimensions, contenu du texte représenté, etc., etc.) ne peuvent être obtenues qu'en appliquant un certain nombre de procédures de traitement et d'analyse d'image. , que nous devons soit programmer nous-mêmes, soit utiliser des procédures toutes faites disponibles dans les logiciels d'analyse d'images bien connus. Dans le même temps, pour résoudre des problèmes simples de vision par ordinateur, des outils prêts à l'emploi se trouveront très probablement dans les bibliothèques standards de procédures de traitement d'images ; pour résoudre des problèmes plus complexes, il sera nécessaire de combiner certaines procédures toutes faites, et pour de nombreuses tâches tout à fait « ordinaires » que la vision humaine « biologique » semble résoudre facilement et de manière ludique, la vision par ordinateur n'a toujours pas de solutions et les cherche toujours. Après tout, grâce à sa vision naturelle, une personne peut facilement naviguer dans n'importe quel environnement, reconnaître des objets, choisir un chemin, conduire 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 ? C'est peut-être 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 du cristallin, 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, le mécanisme complexe de traitement des informations reçues, fonctionnant dans la partie correspondante de notre cerveau, interprète ces impulsions comme une image de la scène visible que nous comprenons. Ainsi, chez l'homme, la fonction « 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 expliqué à l'aide de l'exemple suivant.
Lorsqu'au milieu du XXe siècle, les chirurgiens ophtalmologistes ont appris à effectuer des opérations sur le cristallin, de nombreuses personnes aveugles de naissance possédaient la capacité technique de voir. Autrement dit, après une telle opération chez une personne auparavant aveugle (la lumière ne traversait tout simplement pas la lentille), une image a commencé à se former sur la rétine et les signaux correspondants ont commencé à pénétrer dans le cerveau exactement de la même manière que cela se produit. chez les personnes en bonne santé. Malheureusement, dans ce cas, « voir la lumière » ne signifiait pas « commencer à voir ». Comme l'histoire ultérieure l'a montré, la plupart des patients adultes « techniquement éclairés » n'ont jamais pu obtenir des résultats plus significatifs dans le champ de vision que la reconnaissance de formes géométriques simples - et même cela a nécessité de sérieux efforts conscients de leur part. Reconnaître les gens à leur visage et s’orienter dans l’espace restaient pour eux des tâches impossibles. 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 à temps chez ces patients, et ils se sont retrouvés dans la position d'un ordinateur doté d'un dispositif de saisie d'images. , mais ne dispose pas du logiciel nécessaire à son analyse.
Pour enfin nous convaincre de la complexité de la tâche qui nous attend dans l’analyse d’une image, qui est un ensemble bidimensionnel de données numériques, essayons de nous mettre à la place d’un programme informatique traitant de nombres abstraits. Pour ce faire, changeons mentalement la modalité de perception de l’image – transférons-la de la zone visuelle à la zone tactile. Imaginons un tableau bidimensionnel de valeurs d'intensité sous la forme d'un échiquier dont la taille est égale à la taille de l'image (DimXDimY), et une colonne est insérée au centre de chaque cellule, dont la hauteur est proportionnel à la valeur du pixel correspondant dans l’image. En d’autres termes, considérons une image bidimensionnelle comme une sorte de surface tridimensionnelle conditionnelle. En figue. 1.1.2 à gauche est un fragment d'un visage de femme représenté sous forme d'image, et à droite est représenté un relief pseudo-3D.
@Riz. 1.1.2. Image numérique comme relief pseudo-3D
Imaginez maintenant que vous deviez, sans regarder l'image, ressentir le « relief » correspondant et essayer de déterminer ce que représente exactement ce « relief » - une maison, un chien ou un œil humain ? Les expériences montrent que la personne moyenne n’est pas capable de faire face à une telle tâche. Même reconnaître les figures géométriques les plus simples dans une telle représentation en « relief » impliquera des efforts importants et nécessitera le développement conscient d’une compétence, d’une stratégie et d’algorithmes de détection spéciaux. C’est là, malgré l’apparente simplicité de l’objet « image numérique », la véritable complexité des problèmes de vision informatique et industrielle.
J'ai longtemps voulu écrire un article général contenant les bases mêmes de la reconnaissance d'images, une sorte de guide sur les méthodes de base, indiquant quand les utiliser, quels problèmes elles résolvent, ce qu'on peut faire le soir à genoux et ce qu'il faut faire. mieux vaut ne pas y penser sans avoir une équipe de personnes dans 20.
J'écris depuis longtemps des articles sur la reconnaissance optique, donc plusieurs fois par mois, diverses personnes m'écrivent pour me poser des questions sur ce sujet. Parfois, on a le sentiment de vivre avec eux dans des mondes différents. D'une part, vous comprenez que la personne est très probablement un professionnel dans un domaine connexe, mais qu'elle connaît très peu les méthodes de reconnaissance optique. Et le plus ennuyeux, c'est qu'il essaie d'appliquer une méthode d'un domaine de connaissances proche, qui est logique, mais ne fonctionne pas complètement en reconnaissance d'images, mais ne comprend pas cela et est très offensé si vous commencez à lui dire quelque chose de les bases mêmes. Et étant donné que raconter à partir des bases prend beaucoup de temps, ce qui n'est souvent pas disponible, cela devient encore plus triste.
Cet article est destiné à ce qu'une personne qui n'a jamais travaillé avec des méthodes de reconnaissance d'images puisse, en 10 à 15 minutes, créer dans sa tête une certaine image de base du monde qui correspond au sujet et comprendre dans quelle direction creuser. La plupart des techniques décrites ici sont applicables au traitement radar et audio.
Je vais commencer par quelques principes que nous commençons toujours à expliquer à un client potentiel ou à une personne qui souhaite commencer à utiliser la reconnaissance optique :
- Lorsque vous résolvez un problème, partez toujours du plus simple. Il est beaucoup plus facile de mettre une étiquette orange sur une personne que de suivre une personne en la mettant en valeur en cascade. Il est beaucoup plus facile de prendre un appareil photo avec une résolution plus élevée que de développer un algorithme de super-résolution.
- Une formulation stricte du problème dans les méthodes de reconnaissance optique est d'un ordre de grandeur plus importante que dans les problèmes de programmation système : un mot supplémentaire dans la spécification technique peut ajouter 50 % du travail.
- Il n’existe pas de solutions universelles aux problèmes de reconnaissance. Vous ne pouvez pas créer un algorithme qui « reconnaîtrait simplement n’importe quelle inscription ». Un panneau dans la rue et une feuille de texte sont des objets fondamentalement différents. Il est probablement possible de créer un algorithme général (voici un bon exemple de Google), mais cela nécessitera beaucoup de travail de la part d'une grande équipe et sera composé de dizaines de sous-programmes différents.
- OpenCV est une bible qui propose de nombreuses méthodes et peut résoudre 50 % de presque tous les problèmes, mais OpenCV ne représente qu'une petite partie de ce qui peut réellement être fait. Dans une étude, les conclusions ont été écrites : « Le problème ne peut pas être résolu en utilisant les méthodes OpenCV, il est donc insoluble. » Essayez d'éviter cela, ne soyez pas paresseux et évaluez sobrement la tâche en cours à partir de zéro à chaque fois, sans utiliser de modèles OpenCV.
La liste des méthodes données ici n'est pas complète. Je suggère d'ajouter des méthodes critiques dans les commentaires que je n'ai pas écrits et d'attribuer 2-3 mots d'accompagnement à chacune.
Partie 1. Filtration
Dans ce groupe j'ai placé des méthodes qui permettent de sélectionner des zones d'intérêt dans les images sans les analyser. La plupart de ces méthodes appliquent une sorte de transformation unique à tous les points de l'image. Au niveau du filtrage, aucune analyse d'image n'est effectuée, mais les points filtrés peuvent être considérés comme des zones présentant des caractéristiques particulières.Binarisation par seuil, sélection de zone d'histogramme
La transformation la plus simple est la binarisation de l'image par seuil. Pour les images RVB et en niveaux de gris, le seuil est la valeur de couleur. Il existe des problèmes idéaux dans lesquels une telle transformation est suffisante. Supposons que vous souhaitiez sélectionner automatiquement des objets sur une feuille de papier blanche :
Le choix du seuil auquel se produit la binarisation détermine en grande partie le processus de binarisation lui-même. Dans ce cas, l’image a été binarisée par la couleur moyenne. Généralement, la binarisation est effectuée à l'aide d'un algorithme qui sélectionne un seuil de manière adaptative. Un tel algorithme peut être le choix d'une attente ou d'un mode. Ou vous pouvez sélectionner le plus grand pic de l'histogramme.
La binarisation peut donner des résultats très intéressants lorsqu'on travaille avec des histogrammes, y compris dans le cas où l'on considère une image non pas en RVB, mais en HSV. Par exemple, segmentez les couleurs qui vous intéressent. Sur ce principe, vous pouvez construire à la fois un détecteur d'étiquettes et un détecteur de peau humaine.
Filtrage classique : Fourier, filtre passe-bas, filtre passe-haut
Les méthodes classiques de filtrage radar et de traitement du signal peuvent être appliquées avec succès à diverses tâches de reconnaissance de formes. Une méthode traditionnelle en radar, qui n'est presque jamais utilisée dans les images sous forme pure, est la transformée de Fourier (plus précisément la FFT). L'une des rares exceptions dans lesquelles la transformée de Fourier unidimensionnelle est utilisée est la compression d'image. Pour l'analyse d'images, une transformation unidimensionnelle n'est généralement pas suffisante ; vous devez utiliser une transformation bidimensionnelle beaucoup plus gourmande en ressources.
Peu de gens le calculent réellement ; généralement, il est beaucoup plus rapide et plus facile d’utiliser la convolution de la zone d’intérêt avec un filtre prêt à l’emploi, réglé pour les fréquences hautes (HPF) ou basses (LPF). Bien entendu, cette méthode ne permet pas l'analyse du spectre, mais dans une tâche de traitement vidéo spécifique, ce qui est généralement nécessaire n'est pas l'analyse, mais le résultat.
Les exemples les plus simples de filtres mettant l'accent sur les basses fréquences (filtre gaussien) et les hautes fréquences (filtre Gabor).
Pour chaque point image, une fenêtre est sélectionnée et multipliée par un filtre de même taille. Le résultat d’une telle convolution est une nouvelle valeur en points. Lors de la mise en œuvre de filtres passe-bas et de filtres passe-haut, des images du type suivant sont obtenues :
Ondelettes
Mais que se passe-t-il si nous utilisons une fonction caractéristique arbitraire pour la convolution avec le signal ? On l'appellera alors "Transformation en ondelette". Cette définition des ondelettes n'est pas correcte, mais traditionnellement, dans de nombreuses équipes, l'analyse des ondelettes est la recherche d'un motif arbitraire dans une image par convolution avec un modèle de ce motif. Il existe un ensemble de fonctions classiques utilisées dans l'analyse par ondelettes. Il s'agit notamment de l'ondelette de Haar, de l'ondelette de Morlet, de l'ondelette du chapeau mexicain, etc. Les primitives Haar, sur lesquelles il y avait plusieurs de mes articles précédents (,), concernent de telles fonctions pour un espace bidimensionnel.
Ci-dessus, 4 exemples d'ondelettes classiques. Ondelette de Haar en 3 dimensions, ondelette de Meyer en 2 dimensions, ondelette de Chapeau Mexicain, ondelette de Daubechies. Un bon exemple d’utilisation de l’interprétation étendue des ondelettes est le problème de la recherche d’un éblouissement dans l’œil, pour lequel l’ondelette est l’éblouissement lui-même :
Les ondelettes classiques sont généralement utilisées pour la compression d'images ou pour la classification d'images (à décrire ci-dessous).
Corrélation
Après une interprétation aussi libre des ondelettes de ma part, il convient de mentionner la corrélation réelle qui les sous-tend. C'est un outil indispensable pour filtrer les images. Une application classique consiste à corréler un flux vidéo pour trouver des décalages ou des flux optiques. Le détecteur de décalage le plus simple est aussi, dans un sens, un corrélateur de différence. Là où les images ne correspondaient pas, il y avait du mouvement.
Fonctions de filtrage
Une classe intéressante de filtres est le filtrage des fonctions. Ce sont des filtres purement mathématiques qui permettent de détecter une fonction mathématique simple dans une image (ligne, parabole, cercle). Une image accumulée est construite, dans laquelle pour chaque point de l'image originale est dessiné un ensemble de fonctions qui la génèrent. La transformation la plus classique est la transformation de Hough pour les lignes. Dans cette transformation, pour chaque point (x;y), on trace un ensemble de points (a;b) de la droite y=ax+b pour lesquels l'égalité est vraie. Vous obtenez de belles images :
(le premier plus est pour celui qui est le premier à trouver un piège dans l'image et cette définition et à l'expliquer, le deuxième plus est pour celui qui est le premier à dire ce qui est montré ici)
La transformée de Hough vous permet de trouver toutes les fonctions paramétrables. Par exemple des cercles. Il existe une transformation modifiée qui vous permet de rechercher n'importe quelle forme. Les mathématiciens sont terriblement friands de cette transformation. Mais lors du traitement des images, cela ne fonctionne malheureusement pas toujours. Vitesse de fonctionnement très lente, très grande sensibilité à la qualité de binarisation. Même dans des situations idéales, j’ai préféré me contenter d’autres méthodes.
Un analogue de la transformée de Hough pour les lignes droites est la transformée de Radon. Il est calculé via FFT, ce qui donne un gain de performances dans une situation où il y a beaucoup de points. De plus, il peut être appliqué à une image non binarisée.
Filtrage des contours
Une classe distincte de filtres est le filtrage des bordures et des contours. Les contours sont très utiles lorsque nous voulons passer du travail avec une image au travail avec les objets de cette image. Lorsqu'un objet est assez complexe, mais clairement distinguable, la seule façon de travailler avec lui est souvent de sélectionner ses contours. Il existe un certain nombre d'algorithmes qui résolvent le problème du filtrage des contours :Le plus souvent c'est Canny qui est utilisé, qui fonctionne bien et dont l'implémentation est en OpenCV (Sobel est là aussi, mais il cherche des contours pires).
Autres filtres
Ci-dessus se trouvent des filtres dont les modifications aident à résoudre 80 à 90 % des problèmes. Mais à côté d'eux, il existe des filtres plus rares utilisés dans les tâches locales. Il existe des dizaines de filtres de ce type, je ne les énumérerai pas tous. Les filtres itératifs (par exemple, un modèle d'apparence actif) sont intéressants, ainsi que les transformations en crête et en courbure, qui sont une fusion du filtrage et de l'analyse par ondelettes classiques dans le domaine de la transformation du radon. La transformation en faisceaux fonctionne à merveille à la frontière de la transformation en ondelettes et de l'analyse logique, vous permettant de mettre en évidence les contours :
Mais ces transformations sont très spécifiques et adaptées à des tâches rares.
Partie 2. Traitement logique des résultats de filtrage
Le filtrage fournit un ensemble de données adaptées au traitement. Mais souvent, vous ne pouvez pas simplement récupérer et utiliser ces données sans les traiter. Dans cette section, nous présenterons plusieurs méthodes classiques qui permettent de passer d'une image aux propriétés des objets, ou aux objets eux-mêmes.Morphologie
Le passage du filtrage à la logique, à mon avis, ce sont les méthodes de morphologie mathématique (, ,). Essentiellement, ce sont les opérations les plus simples de croissance et d’érosion d’images binaires. Ces méthodes permettent de supprimer le bruit d'une image binaire en augmentant ou en diminuant les éléments existants. Il existe des algorithmes de contouring basés sur la morphologie mathématique, mais on utilise généralement des algorithmes hybrides ou des algorithmes combinés.
Analyse de contour
Des algorithmes pour obtenir des limites ont déjà été évoqués dans la section sur le filtrage. Les frontières ainsi obtenues sont tout simplement converties en contours. Pour l'algorithme Canny, cela se produit automatiquement ; pour les autres algorithmes, une binarisation supplémentaire est requise. Vous pouvez obtenir un contour pour un algorithme binaire, par exemple en utilisant l'algorithme Beetle.Un contour est une caractéristique unique d'un objet. Cela permet souvent d'identifier un objet par son contour. Il existe un puissant appareil mathématique qui vous permet de le faire. L'appareil s'appelle analyse de contour (,).
Pour être honnête, je n’ai jamais pu appliquer l’analyse des contours à des problèmes réels. Des conditions trop idéales sont requises. Soit il n’y a pas de frontière, soit il y a trop de bruit. Mais si vous avez besoin de reconnaître quelque chose dans des conditions idéales, l’analyse des contours est une excellente option. Cela fonctionne très rapidement, de belles mathématiques et une logique claire.
Points spéciaux
Les points singuliers sont des caractéristiques uniques d'un objet qui permettent de comparer l'objet avec lui-même ou avec des classes d'objets similaires. Il existe plusieurs dizaines de façons d'identifier de tels points. Certaines méthodes identifient des points spéciaux dans des images adjacentes, d'autres après une longue période de temps et lorsque l'éclairage change, d'autres vous permettent de trouver des points spéciaux qui le restent même lorsque l'objet est pivoté. Commençons par des méthodes qui nous permettent de trouver des points particuliers, qui ne sont pas si stables, mais qui sont rapidement calculés, puis nous irons dans une complexité croissante :Première année. Points spéciaux stables sur une période de quelques secondes. De tels points sont utilisés pour guider un objet entre des images vidéo adjacentes ou pour combiner des images de caméras voisines. Ces points incluent les maxima locaux de l'image, les coins de l'image (le meilleur détecteur est peut-être le détecteur Charis), les points auxquels la dispersion maximale est atteinte, certains gradients, etc.
Seconde classe. Points spéciaux stables lors des changements d'éclairage et des petits mouvements de l'objet. Ces points servent principalement à la formation et à la classification ultérieure des types d'objets. Par exemple, un classificateur piéton ou un classificateur facial est le produit d'un système construit précisément sur de tels points. Certaines des ondelettes mentionnées précédemment peuvent constituer la base de ces points. Par exemple, les primitives Haar, recherchent des faits saillants, recherchent d'autres fonctions spécifiques. Ces points incluent les points trouvés par la méthode de l'histogramme des gradients directionnels (HOG).
Troisième classe. Points stables. Je ne connais que deux méthodes offrant une stabilité totale et leurs modifications. Ce sont SURF et SIFT. Ils vous permettent de trouver des points spéciaux même lorsque vous faites pivoter l'image. Le calcul de ces points prend plus de temps que d’autres méthodes, mais le temps est assez limité. Malheureusement, ces méthodes sont brevetées. Bien qu'en Russie, il soit impossible de breveter des algorithmes, utilisez-les donc pour le marché intérieur.
Partie 3. Formation
La troisième partie du récit sera consacrée aux méthodes qui ne fonctionnent pas directement avec l'image, mais qui permettent de prendre des décisions. Il s’agit principalement de diverses méthodes d’apprentissage automatique et de prise de décision. Yandyx a récemment publié un cours sur ce sujet sur Habr, il y en a une très bonne sélection. Le voici dans la version texte. Pour une étude sérieuse du sujet, je recommande fortement de les regarder. Ici, je vais essayer de décrire plusieurs méthodes principales utilisées spécifiquement dans la reconnaissance de formes.Dans 80 % des situations, l'essence de l'apprentissage dans la tâche de reconnaissance est la suivante :
Il existe un exemple de test qui contient plusieurs classes d'objets. Que ce soit la présence/absence d'une personne sur la photo. Pour chaque image, il existe un ensemble de caractéristiques qui ont été mises en évidence par une caractéristique, que ce soit Haar, HOG, SURF ou une ondelette. L'algorithme d'apprentissage doit construire un modèle afin de pouvoir analyser une nouvelle image et décider quel objet se trouve dans l'image.
Comment c'est fait? Chacune des images de test est un point dans l'espace des fonctionnalités. Ses coordonnées sont le poids de chacune des caractéristiques de l'image. Que nos signes soient : « Présence d'yeux », « Présence d'un nez », « Présence de deux mains », « Présence d'oreilles », etc... Nous mettrons en évidence tous ces signes à l'aide de nos détecteurs existants, entraînés sur parties du corps semblables à celles de l'humain Pour une personne dans un tel espace, le point correct serait. Pour le singe, point pour le cheval. Le classificateur est formé à l'aide d'un échantillon d'exemples. Mais toutes les photographies ne montraient pas des mains, d’autres n’avaient pas d’yeux et sur la troisième, le singe avait un nez humain en raison d’une erreur de classificateur. Un classificateur humain entraîné divise automatiquement l'espace des fonctionnalités de manière à dire : si la première fonctionnalité se situe dans la plage 0,5
Il existe de nombreux classificateurs. Chacun d’eux fonctionne mieux dans une tâche particulière. La tâche consistant à sélectionner un classificateur pour une tâche spécifique est en grande partie un art. Voici quelques belles photos sur le sujet.
Cas simple, séparation unidimensionnelle
Regardons un exemple du cas de classification le plus simple, lorsque l'espace des fonctionnalités est unidimensionnel et que nous devons séparer 2 classes. Cette situation se produit plus souvent que vous ne le pensez : par exemple, lorsque vous devez distinguer deux signaux ou comparer un modèle avec un échantillon. Ayons un échantillon de formation. Cela produit une image où l'axe X est la mesure de similarité et l'axe Y est le nombre d'événements avec une telle mesure. Lorsque l’objet recherché est similaire à lui-même, une gaussienne gauche est obtenue. Quand ça n’en a pas l’air, c’est le bon. La valeur de X=0,4 sépare les échantillons de sorte qu'une mauvaise décision minimise la probabilité de prendre une mauvaise décision. La recherche d'un tel séparateur relève de la classification.
Une petite remarque. Le critère qui minimise l’erreur ne sera pas toujours optimal. Le graphique suivant est un graphique d'un véritable système de reconnaissance de l'iris. Pour un tel système, le critère est choisi pour minimiser la probabilité de fausse admission d'une personne non autorisée dans l'établissement. Cette probabilité est appelée « erreur de type I », « probabilité de fausse alarme », « faux positif ». Dans la littérature anglophone « False Access Rate ».
) AdaBusta est l'un des classificateurs les plus courants. Par exemple, la cascade Haar y est construite. Généralement utilisé lorsqu'une classification binaire est nécessaire, mais rien n'empêche de s'entraîner pour un plus grand nombre de classes.
SVM ( , , , ) L'un des classificateurs les plus puissants, qui a de nombreuses implémentations. Fondamentalement, sur les tâches d'apprentissage que j'ai rencontrées, cela a fonctionné de la même manière qu'Adabusta. Il est considéré comme assez rapide, mais son entraînement est plus difficile que celui d'Adabusta et nécessite de choisir le bon noyau.
Il existe également des réseaux de neurones et la régression. Mais pour les classer brièvement et montrer en quoi ils diffèrent, nous avons besoin d’un article bien plus long que celui-ci.
________________________________________________
J'espère avoir pu donner un aperçu rapide des méthodes utilisées sans plonger dans les mathématiques et la description. Peut-être que cela aidera quelqu'un. Bien que, bien sûr, l'article soit incomplet et qu'il n'y ait pas un mot sur le travail avec des images stéréo, ni sur le LSM avec un filtre de Kalman, ni sur l'approche adaptative de Bayes.
Si vous aimez l'article, je vais essayer de faire une deuxième partie avec une sélection d'exemples de la façon dont les problèmes existants de ImageRecognition sont résolus.
et enfin
Que lire ?1) J'ai déjà beaucoup aimé le livre « Digital Image Processing » de B. Yane, qui est écrit simplement et clairement, mais en même temps presque toutes les mathématiques sont données. Bon pour connaître les méthodes existantes.
2) Un classique du genre est R. Gonzalez, R. Woods « Digital Image Processing ». Pour une raison quelconque, c'était plus difficile pour moi que le premier. Beaucoup moins de mathématiques, mais plus de méthodes et d'images.
3) « Traitement et analyse d'images dans les problèmes de vision par ordinateur » - rédigé sur la base d'un cours dispensé dans l'un des départements de physique et de technologie. Il existe de nombreuses méthodes et leurs descriptions détaillées. Mais à mon avis, le livre présente deux gros inconvénients : le livre est fortement axé sur le progiciel qui l'accompagne, dans le livre la description d'une méthode simple se transforme trop souvent en une jungle mathématique, dont il est difficile de sortir. dériver le schéma structurel de la méthode. Mais les auteurs ont créé un site Web pratique où presque tout le contenu est présenté - wiki.technicalvision.ru
4) Pour une raison quelconque, il me semble qu'un bon livre qui structure et relie l'image du monde qui se présente lors de l'étude de la reconnaissance d'images et de l'apprentissage automatique est « On Intelligence » de Jeff Hawkins. Il n'y a pas de méthodes directes là-bas, mais il y a beaucoup de choses à réfléchir sur l'origine des méthodes de traitement d'image direct. Quand vous le lisez, vous comprenez que vous avez déjà vu les méthodes du cerveau humain, mais dans des tâches de traitement vidéo.
UDC004932:621.396
T.M. VLASOVA, V.G. KALMYKOV
ALGORITHME ET PROGRAMME DE RECONNAISSANCE DES CONTOURS D'IMAGES COMME SÉQUENCE DE SEGMENTS DE LIGNES NUMÉRIQUES
Résumé : Dans le travail donné, l'algorithme de reconnaissance du segment de ligne directe numérique dans les contours des images binaires et la mise en œuvre logicielle de l'algorithme sont considérés. L'utilisation de cet algorithme pour traiter les images aboutira à une description plus naturelle et plus économique par rapport aux méthodes connues de description des images. L'algorithme considéré et la mise en œuvre du logiciel 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.
Résumé : Ce robot développe un algorithme de reconnaissance de segments de droites numériques dans les contours d'images binaires, ainsi qu'une implémentation logicielle de l'algorithme. L'algorithme choisi pour compiler l'image conduira au fait que la description de l'image sera plus naturelle et économique, alignée sur les méthodes connues de codage de l'image. L'algorithme enregistré et l'implémentation logicielle peuvent être combinés pour coder les contours lors du traitement d'images monotones et couleur. Mots clés : image, contour, sections de lignes numériques, algorithme, programme.
Résumé : Cet article discute de l'algorithme de reconnaissance de segments de lignes numériques dans les contours d'images binaires et de la mise en œuvre logicielle de l'algorithme. L'utilisation de cet algorithme lors du traitement des images conduira à une description des images plus naturelle et plus économique par rapport aux méthodes connues. L'algorithme considéré et la mise en œuvre logicielle peuvent également être utilisés pour décrire les contours lors du traitement des images en demi-teintes 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 ligne droite et d'arcs courbes est l'une des tâches principales du traitement d'images en vue de leur interprétation dans les systèmes d'intelligence artificielle.
Dans la plupart des cas, une image peut être considérée comme une partie d'un plan, divisée en zones avec des paramètres constants ou variables selon une certaine 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 un contour - une séquence simplement connectée constituée de segments droits et d'arcs courbes. Lors du traitement d'une image raster, les contours des objets sont généralement mis en évidence. Cependant, les contours des objets, présentés comme un ensemble de pixels limites individuels, sont peu utiles pour un traitement ultérieur, car ils n'expriment pas suffisamment son essence géométrique.
La reconnaissance des contours de l'image sous la forme d'une séquence de segments droits peut être considérée comme l'une des tâches principales du processus de traitement d'images raster. Résoudre le problème de la représentation d'un contour comme 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 sous transformations affines, et pratique notamment pour le traitement par les réseaux de neurones . Les segments de ligne sont les principaux éléments d'un contour. L'arc d'une courbe est aussi souvent remplacé par une ligne brisée qui y est inscrite, tant dans les principes de base de l'analyse mathématique que dans un grand nombre d'applications pratiques.
Des méthodes et algorithmes bien connus, notamment ceux proposés dans l'ouvrage, permettent d'obtenir une solution approchée, qui n'est pas acceptable pour toutes les applications.
Cet article examine la reconnaissance du contour d'une image binaire comme une séquence de segments de lignes droites numériques sans perte d'information.
2. Contour comme séquence de segments de lignes numériques
Cette section traite de l'analyse structurelle des contours de l'image en tant que 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.
Nous nous limiterons à considérer des images binaires dont les objets sont entièrement déterminés par les contours qui les limitent. Les arcs de courbes numériques, comme les segments de lignes droites 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.
Les traits caractéristiques des segments droits et des arcs courbes sont perdus au cours du processus de transformation. Lors de la visualisation d'une image échantillonnée avec un grossissement suffisant, il est souvent difficile de reconnaître des segments droits individuels et des arcs courbes en séquence.
segments verticaux et horizontaux. Des difficultés supplémentaires surviennent lors du traitement du fait que les lignes de contour - lignes mathématiques sans épaisseur - sont affichées sur l'écran du moniteur sous forme de séquences de pixels connectées, 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 grâce à la discrétisation comme un complexe cellulaire bidimensionnel. Dans ce cas
les pixels sont les éléments bidimensionnels de ce complexe cellulaire. En plus des pixels, il y a des fissures et des points. Les fissures sont
côtés de pixels qui sont des éléments unidimensionnels. Les points sont les extrémités des fissures et les coins des pixels. Les points sont des éléments de dimension zéro. Donc
Ainsi, dans le cas considéré, le contour d'un objet est une séquence fermée connexe de fissures de contour bordant les pixels de l'objet et le fond. Un contour peut être décrit comme une séquence de coordonnées entières de points,
limiter les fissures de contour. Comme le montre la figure , représentant le plan image comme
Le complexe cellulaire offre de nombreux avantages. En particulier, la limite de la région devient une fine courbe de surface nulle.
En figue. La figure 1 montre un exemple du contour original d'un objet formé d'un arc de courbe et d'un segment de droite, ainsi que son équivalent numérique sous forme d'une séquence de fissures. Les points appartenant à des fissures de directions différentes sont numérotés. Comme dans les œuvres, par élément L, nous entendons une séquence connexe de fissures de même direction, émanant d'un certain point et se terminant par une fissure de même direction ou perpendiculaire. En figue. La figure 1 montre l'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 (accepté g = 0 - pour la direction vers le haut, 1 - vers la droite, 2 - vers le bas, 3 - vers la gauche) ; l - 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 classiquement appelé 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 droites numériques dans un contour utilise la propriété suivante de la séquence d'éléments L formant le segment. Une telle séquence comprend des éléments b avec les mêmes valeurs de g, q ; leurs longueurs prennent des valeurs !, +1. De plus
l'alternance des b-éléments de longueur !, +1 est déterminée par la fraction continue obtenue en divisant les entiers n = Ax = |x1 - x2| et m = Ау = |у1 - у2\, où (х1зу1), (х2, у2) sont les coordonnées du point initial
et les extrémités du segment : ou
Supposons pour être précis que n > m. Comme il ressort de la formule (1), l - la partie entière de la division de n par m - correspond dans un segment de la droite numérique au nombre de l fissures consécutives de la même direction. Avec la fissure perpendiculaire adjacente, ils forment l'élément b de longueur !. k1 éléments b consécutifs de longueur l et un élément b de longueur !+1 (ou k1 éléments b consécutifs de longueur +1 et un élément b de longueur !) forment un élément K1 de « longueur » k1 (par analogie avec la « longueur » de l'élément b). Un élément b dont la longueur diffère 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ément de « longueur » k1. Donc
k + k 2 + k z +... + kg
plus loin jusqu'à ce que les membres de la fraction continue soient épuisés. Un élément K1 (généralement un élément K-1), dont la longueur diffère de 1 des éléments K1 consécutifs (élément Kg-1), sera appelé élément K1 modifié (élément Kg-1) d'un élément donné. K2 -élément (Kg -élément). Ainsi, tout le monde
Un segment de ligne numérique correspond à une fraction continue dont les éléments déterminent la structure de ce segment.
Dans le schéma de la Fig. 1, on distingue les segments de droites numériques suivants : 0-3, 3-9, 910, 10-17, 17-0.
3. Sélection de segments d'une ligne numérique dans un contour
Lors du traitement de contours d'images, notamment 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 droits. Ce problème peut être considéré comme le problème de la détermination des éléments d'une fraction continue à partir d'une séquence d'éléments L d'un contour. Ce problème est inverse du problème de détermination de la structure d'un segment de droite à partir d'une séquence de termes d'une fraction continue, obtenue comme le rapport des différences entre les 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. Identification de la séquence d'éléments b dans la séquence de fissures. Cette action répond à la définition d’une partie entière ! fraction continue (1).
2. Isoler une séquence d'éléments Kr avec r = 1 dans une 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ème élément de la fraction continue (1). Après son exécution, la valeur de r doit être augmentée de 1.
3. Identification de la séquence d'éléments Kr-1 dans la séquence d'éléments Kr-1,
De plus, l'un des éléments Kr-1 de chaque élément Kr doit contenir un élément Kr-2 en plus ou en 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 point 3 est répété jusqu'à ce qu'il soit encore possible de
forment l’élément Km.
5. Déterminez les points limites entre deux éléments b voisins qui ne sont pas inclus dans le même élément Kr. Ces points sont les extrémités des segments de ligne numérique qui forment le contour.
Considérons un algorithme de sélection de segments de ligne dans une séquence d'éléments b
Soit [b5(/5,gs,qs)); 5 = 0,1,...,£ - séquence d'éléments b formant le contour ; x5,y5 - coordonnées du début du ème élément b ; [hu, ouais); y = ; r = 0,1,...,!; !< £ - множество
points de rupture de contour. Les points de rupture définissent les points d'extrémité des segments de ligne qui forment le contour. Trouver les points de rupture signifie identifier les segments droits qui forment le contour.
Chaque segment considéré est caractérisé par un élément Kg, ainsi qu'une chaîne
fraction Au moment initial de reconnaissance d'un segment de droite, les éléments de la fraction continue correspondante sont égaux à 0. Le segment peut être considéré comme reconnu si les paramètres de l'élément Kr sont reconnus, notamment son ordre r et les valeurs de les éléments de la fraction continue correspondante.
1. Conditions initiales.
Séquences données [b5 (/5, gs, qs)) et (x5,y5) .
Il faut trouver les coordonnées des points de rupture |x;.,y,).
k0р:= 0, к1р:= 0, к2р:= 0,..., кр:= 0 - valeurs de travail des éléments de la fraction continue.
Prenons le point 5 =0 comme point de départ du premier segment ; je =0 ; je =0.
2. Prenez le premier élément b de la séquence comme début du premier segment droit. Son point de départ est x5,y. La longueur /=/0 est également la valeur du premier élément de la fraction continue.
5 :=5+1 ; k1p :=k1p+1.
3. Vérifiez si l'élément b suivant forme avec les précédents un élément K0.
3.1. Si ((d3 == d3-1) && (d3 == 73-1)&& (4 == /3-1)), alors la suite de l'élément Kg k0p:= k0p +1; 5 := 5 + 1 ; et continuation d'un segment de droite. Passez à l'étape 3.
3.2. Si ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1)), alors la fin du segment droit. Passez à l'étape 5.
3.3. Si ((&== 9з+1) && (%== 7з+1)&& ((/з+1== /з+1)1! (/з - 1 == /3+1))), puis l'achèvement de l'élément K0 ; Ї = Ї+1.
4. Vérification de la continuation/complétion de l'élément K(-element.
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 à l'étape 3.
4.2. Si ((k iФ 0)&&(k == k^)), alors k^1p := k^1p+1 ; 5 := 5+1 ; continuation de l’élément Ki+1. Passez à l'étape 3.
4.3. Si ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^))), alors Ї := +1; fin de l'élément Km.
Passez à l'étape 4.
4.4. Si ((^ф0)&&(|к - к1р|>1)), alors la fin du segment est une transition directe vers l'étape 5.
5. Fin du segment.
X] = Xs ; y = Uz; k1р:= 0, к2р:= 0,., кір:= 0; k:= 0, k2:= 0,., k:= 0.
Si (s< S), то s:= s +1; переход к п. 2.
Sinon, la fin de la séquence des éléments L. La fin de l'algorithme.
Essentiellement, l'algorithme proposé trouve les é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 correspond à celle déjà construite.
4. Programme de sélection de segments de ligne numérique
Comme le montre la description de l'algorithme, il contient un nombre important de transitions conditionnelles, 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
il est impossible de le déterminer, puisque la variable t n'est pas limitée à l'avance. Valeur limite t
Cela signifie limiter la taille des images à l’avance. La mise en œuvre du logiciel, en particulier le débogage de l'algorithme proposé à l'aide de moyens triviaux, est très difficile pour les raisons ci-dessus. Les difficultés liées au développement et au débogage d’une implémentation logicielle peuvent être réduites si vous utilisez des outils de programmation orientés objet modernes.
L'algorithme proposé est implémenté sous la forme du programme LINESEGM, qui fait partie du progiciel du laboratoire pour le traitement d'images dans l'environnement Visual C++.
Comme information initiale, le programme LINESEGM utilise des séquences d'éléments L construites pour chacun des contours de l'image traitée.
Le résultat du programme est une séquence connectée de segments droits numériques construits pour chaque contour, représenté par les coordonnées des points d'extrémité des segments.
Comme le montre l'algorithme, les opérations de construction d'éléments Kt à partir d'éléments Kt-l
sont les mêmes pour toutes les valeurs de t. A noter que la valeur initiale t = 0 et pendant le fonctionnement de l'algorithme augmente à chaque fois de 1. La classe spéciale CKForLn comprend des méthodes correspondant aux opérations de l'algorithme. Lors du fonctionnement d'un 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 éléments K0 ne sont pas formés à partir d'éléments K, mais à partir de L -
éléments, pour implémenter l'algorithme au niveau zéro, une modification spéciale de la classe CKForLn a été créée - la classe Cmini.
Le principe de fonctionnement du programme est que pour chaque valeur de t, le programme implémente un objet de la classe CKForLn du t-ème niveau, contenant 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à
un élément Kt-l complété dont les paramètres ont été déterminés par un objet de la 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. Un objet de niveau zéro est créé immédiatement au démarrage du programme.
Implémenter des objets dans un tableau dynamique à mesure que t augmente vous permet de ne pas imposer de restrictions sur la taille de l'image. Les limites de taille d'image sont déterminées uniquement par les ressources de l'ordinateur utilisé.
Lors de la description du fonctionnement du programme, le concept de Kt terminé sera utilisé -
élément. Chaque élément Kt complété contient des éléments Kt-l et un élément Kt-l modifié, qui contient des éléments Kt-l ±1, contrairement à un élément Kt incomplet, qui ne contient pas d'élément Kt incomplet. -élément.
La classe CKForLn inclut les méthodes suivantes.
1. Méthode DK(), (définir l'élément K) - déterminer l'élément K.
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 en question avec un élément K du 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) - 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() du niveau t-1 est appelée par la fonction méthode DK() du 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éalablement déterminé par la fonction de la méthode DE().
La classe Cmini comprend les mêmes méthodes, différant des méthodes de la classe CKForLn en ce sens que les méthodes de la classe Cmini fonctionnent avec 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 d'éléments L construites pour chacun des contours de l'image traitée, à partir du numéro actuel de l'élément L au moment de l'appel de la fonction de méthode.
La fonction de 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 complet et se termine
travail. Un élément K0 est considéré comme complet s'il se termine par un élément L modifié, dont la longueur diffère des autres éléments L de l'élément K0 de 1 (opération 3.1 pour le début du segment - t = 0).
La fonction méthode VK() vérifie si les paramètres des éléments L k0 suivants correspondent aux paramètres des éléments L de l'élément K0 précédemment définis par la fonction méthode DK().
le même niveau. Si les paramètres de l'élément K0 actuel coïncident avec ceux précédemment
définie, la fonction VK() forme un signe de continuation de segment et termine le travail (opération 3.1 pour la continuation de segment - t > 0).
Sinon, la fonction VK() génère un signe d'achèvement de segment et complète
La fonction 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 est modifié. Si les autres paramètres sont égaux, le nombre d'éléments L k0
élément K0 modifié par rapport à l'élément K0 déterminé précédemment
fonction DK(), doit différer de 1 (opération 3.2, 3.3 pour déterminer l'achèvement
l'élément K0 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 méthode VE() compare les paramètres de l'élément K0 actuel avec les paramètres de l'élément K0 modifié, préalablement déterminés par la fonction DE(), pour déterminer
s'ils coïncident (opération 3.2, 3.3 pour continuer le segment - t > 0). Le résultat - signe d'une correspondance ou d'une discordance - est utilisé dans la méthode VК() de la classe CKForLn.
Méthodes de la classe CKForLn
Les méthodes utilisent les paramètres des éléments K construits pour le niveau le plus bas comme données initiales. 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 méthode DK() de niveau t de la classe CKForLn, lors de la définition des paramètres d'un élément ^, appelle la fonction VK() de niveau t-1 de la classe CKForLn, qui vérifie si un élément Kt-l déjà défini 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 de niveau t DK() appelle la fonction de niveau t-1 DE() pour déterminer l'élément Kt-l modifié et quitte. En fin de travail, la fonction DK() de niveau t de la classe CKForLn détermine les paramètres et génère les signes d'un élément Kt complété ou incomplet (opération 4.1, 4.2 à la valeur maximale actuelle de t).
La fonction de la méthode VK() de niveau t de la classe CKForLn vérifie si les paramètres des prochains éléments kt Kt correspondent aux paramètres de l'élément Kt précédemment défini
fonction de la méthode DK() du même niveau. Si les paramètres de l'élément Kt actuel coïncident avec
prédéterminé par la fonction DK() Kt -élément de même niveau, fonction VK()
génère un signe de continuation de segment et termine le travail.
Sinon, la fonction VK() génère un signe d'achèvement de segment et termine le travail (opération 4.1,4.2 avec la valeur actuelle de t inférieure au maximum).
Kt -elementLa fonction de la méthode DE0 de niveau t de la classe CKForLn, lors de la détermination des paramètres d'un Kt -élément, compare les paramètres de l'élément Kt actuel avec les paramètres de l'élément Kt précédemment définis par DK() fonction pour déterminer si l'élément Kt actuel est modifié. 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 d'un élément Kt modifié et
termine le travail (opération 4.3, 4.4 à la valeur maximale actuelle 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 actuel avec les paramètres de l'élément Kt modifié précédemment alloué par la fonction DE() pour déterminer si les valeurs de leurs paramètres coïncident .
Si les valeurs des paramètres de l'élément Kt actuel coïncident avec les valeurs précédentes
définie par la fonction DK() de même niveau, la fonction VK() génère un signe de coïncidence des valeurs des paramètres et termine le travail (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 à l'aide de l'exemple de reconnaissance d'un segment de droite. La partie inférieure de la figure montre une partie d'une ligne numérique, constituée d'éléments en L de mêmes directions principale et auxiliaire et de longueurs différentes.
A l'étape 0, un objet de la classe Stipi a été 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 l'objet 1 de la classe SKrogbn est créé, qui utilise les fonctions de l'objet créé précédemment pour déterminer les paramètres de l'élément K1. A l'étape 19, la détermination des paramètres de l'élément K1 est terminée et l'objet 2 de la classe SKrogbn est créé, qui utilise les fonctions d'objets créés précédemment 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 SKrogbn est créé, qui utilise les fonctions d'objets créés précédemment pour déterminer les paramètres de l'élément K3. L'étape 79 s'exécute
condition de fin du segment. Le fonctionnement du programme est décrit en détail en annexe.
Dans la section 0-6, deux éléments b forment un élément K0 incomplet. Il est évident que b -
l'élément 3-6 de longueur 3 complète le segment de ligne, puisque l'élément b 6-7 de longueur 1 ne peut pas en être la continuation. Ainsi, l'élément b 6-7 est le début d'un segment de la ligne numérique.
En figue. La figure 3 montre un exemple du fonctionnement du programme. Le contour de l'image binaire d'une flèche bouclée est divisé par des carrés en segments droits. Le résultat du programme – une séquence de segments droits – a été utilisé pour mettre en évidence les arcs de courbes numériques. Les grands carrés montrent les limites des arcs de courbes numériques.
Le travail 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. Fonctionnement du programme de reconnaissance des segments de ligne
Regardons le fonctionnement du programme iYEBESM en utilisant l'exemple de la Fig. 4. La partie inférieure de la figure montre une partie d'une ligne numérique, constituée d'éléments b de mêmes directions principale et auxiliaire et de longueurs différentes. Dans la section 0-6, deux éléments b forment un K0-incomplet
Riz. 3. Un exemple de travail d'un programme d'analyse structurelle d'un contour - segmentation d'un contour avec des segments de lignes numériques
élément. Évidemment, l'élément b 3-6 de longueur 3 complète le segment de ligne, puisque l'élément b 6-7 de longueur 1 ne peut pas en être la continuation. Ainsi, l'élément b 6-7 est le début d'un segment de la ligne numérique.
Le travail du programme pour déterminer le prochain segment de ligne droite commence par la fonction OK() de niveau zéro, qui détermine l'élément K0 6-10 terminé, 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 crée un objet de premier niveau et transfère le contrôle à la fonction OK() de cet objet. La fonction OK() au niveau 1 appelle la fonction VKQ au 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. Poursuivant son travail, 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. Ce dernier, commençant par 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, termine le travail et transfère le contrôle à la fonction OK() de niveau 1. Cette fonction détermine la présence d'un élément K1 terminé 6-19, composé de deux K0 -
éléments 1,1,2, (k1=2) et un modifié 1,1,1,2 (k0=3). Le programme crée un objet de deuxième niveau et transfère le contrôle à la fonction OK() de cet objet. La fonction OK() du niveau 2 appelle la fonction VKQ du niveau 1, qui, à son tour, appelle la fonction VKQ du niveau 0. La fonction VKQ compare les paramètres des éléments b des éléments K0 6 à 10 avec les b -
éléments et confirme la présence d'éléments K0 19-23, 23-27, identiques à l'élément K0 6-10, c'est-à-dire le même nombre de ces é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 continuation du 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 à K0 -élément 14-19. Ainsi, l'élément K1 19-32 est défini,
identique à l'élément K1 6-19. De plus, la fonction VKQ du niveau 1 ne définit pas l'élément K1 suivant, identique à l'élément K1 6-19, du fait que la fonction VE0 du niveau 0 ne détermine pas l'élément K1 modifié, identique au K1-élément 6-19, en commençant par l'élément b 40-41, et rend le contrôle à 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, constitué des éléments K0 32-36, 36-40,
40-44, 44-49. Ensuite, l'élément K2 6 à 49 est déterminé, un objet de niveau 3 est formé et 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 à K0 -élément 6-10, et la fonction VKQ de niveau 0 ne génère pas de signe de continuation
segment. Dans la séquence d'éléments L, un segment de la ligne numérique 6-79 est mis en évidence. Le programme commence à déterminer le segment suivant, en commençant par l'élément b 80-82.
b. conclusions
1. Un nouvel algorithme d'identification 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 la reconnaissance des contours d'image en tant que séquences de segments de ligne.
2. La mise en œuvre logicielle de l'algorithme de sélection de segments de droite dans les contours de l'image a été réalisée à l'aide d'outils de programmation orientés objet modernes, ce qui a permis de ne pas imposer de restrictions évidentes 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 sa mise en œuvre logicielle, une solution théorique a été obtenue et des expériences ont été menées sur la reconnaissance d'arcs de courbes numériques et la segmentation du contour d'images binaires sur un segment de droites numériques et d'arcs de courbes numériques.
BIBLIOGRAPHIE
1. Kovalevsky V.A. Applications des segments droits numériques au codage économique des images, Dans Actes du 7ème Atelier International, DGCI"97, Montpellier. - France, 1997. - 3-5 décembre. - P. 51-62.
2. Kalmokov V.G. Méthode structurelle de description et de reconnaissance de segments de lignes numériques dans les contours d'images binaires // Piece intelligence. - 2002. - N° 4. - P. 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. - P. 68 - 71.
4. Kalmikov V.G. Arc de courbe numérique - valorisé et stagné // Traitement des signaux et affichage et reconnaissance de motifs. Actes de cette conférence internationale panukrainienne. - Kyiv. - 2004. - 11 - 15 jours.
Formulation du problème déterminé par l'objectif et les possibilités de sa mise en œuvre.
Cible. Développer un programme de classification des pièces rectangulaires en qualité et défectueuses.
Possibilités de 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 selon 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 une transition d'un objet réel (monde) à une description codée de ses propriétés à l'aide de données et d'opérations sur ceux-ci. Une telle transition s'effectue généralement en plusieurs étapes :
Abstraction– sélection des caractéristiques les plus essentielles de l'objet du point de vue de la tâche.
Il est nécessaire de mener des recherches qui permettent de passer de l'objet de modélisation au sujet de modélisation, en écartant tout ce qui est inutile conformément au but de la tâche.
En quoi un rectangle diffère-t-il 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 bons.
Quelles fonctionnalités minimales sont nécessaires pour résoudre le problème sans ambiguïté ?
- Égalité de 2 côtés opposés + égalité des diagonales.
- Parallélisme de 2 côtés opposés + égalité des diagonales.
- Trois angles sont bons.
Ainsi, grâce à l'abstraction, nous avons reçu un modèle d'information verbal. Mais cela reste incompréhensible pour l’ordinateur. Il comprend un modèle mathématique représenté sous forme d'algorithme et implémenté dans un logiciel.
Méthodologie de mise en œuvre de la tâche.
Un dessin d'une pièce de qualité (rectangle) ou d'une pièce défectueuse (quadrangle) est réalisé à partir de segments (commande LIGNE) dans le système graphique AutoCAD et exporté au format . Le programme kntrs.lsp() lit les données sur les segments (coordonnées des sommets) à partir d'un fichier DXF et les écrit dans le fichier texte vrtks.txt dans un ordre circulaire de parcours des sommets.
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 afficher un enregistrement dans le fichier result.txt indiquant si la pièce répond aux exigences (rectangle ou non).
Formalisation des fonctionnalités
Égalité 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ù À– 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 d'un « Angle Droit » peut être déterminée par la perpendiculaire des segments : K2 = -1/K1, Où À– pente de la droite. K=(Y-Y0)/(X-X0).
Afficher le modèle sur l'ordinateur
Toute information est finalement affichée dans un ordinateur à l'aide de nombres binaires (codes) dans un modèle intra-machine. Auparavant, le codage était effectué par un programmeur. De nos jours, la plupart des programmes sont créés dans des langages algorithmiques.
