Brevet FR2621148A1 — publié le 19890331

La présente invention concerne d'une manière généra- le la reconnaissance de formes et en particulier un procédé pour classer des objets en faisant correspondre la silhouette d'un objet inconnu à la silhouette d'un objet connu. La reconnaissance d'objets peut être réalisée moyen- nant l'utilisation de n'importe quelle caractéristique dis- tinctive d'un objet connu. Une telle caractéristique utile dans de nombreux cas est la silhouette de l'objet, telle au'elle est enregistrée par un dispositif sensible à la lumiè- re visible ou au rayonnement infrarouge. Si la silhouette d'un cbjet inconnu peut être mise en correspondance avec la si- lhouette d'un objet identifié antérieurement, on peut en con- clure aue l'objet non identifié appartient à la même classe que l'objet connu. Etant donné aue les silhouettessont éauiva- lentes à des formes bidimensionnelles, on peut utiliser n'im- porte auelle technique connue de mise en correspondance des formes. Selon une technique connue, les silhouettes sont sub- divisées en petits éléments, à savoir des "éléments d'image". ) On estime aue les silhouettes connues et inconnues se corres- pondent si les contenus d'un pourcentage prédéterminé d'élé- ments d'image correspondants sont identiques. La technique décrite, bien aue simple du point de vue des calculs, fournit de médiocres résultats si les silhouettes aue l'on compare ne sont pas en repérage l'une avec l'autre. Cette technique fournit aussi de médiocres résultats si l'image de l'ob- jet inconnu possède des dimensions différentes de celles de l'image de l'objet connu (comme cela pourrait être le cas si les images étaient obtenues à l'aide de dispositifs situés D à des distances différentes par rapport à J'objet). Une autre technique, qui met en oeuvre la comparaison de transformées de Fourier bidimensionnelles d'une image xoneavecla transfor- mée d'une image inconnue, fournit de bons résultats même si les silhouettes connue et inconnue sont orientées différem- ment. Cependant une telle technique requiert une quantité net- tement plus importante de calculs. Un but de la présente invention est de fournir des moyens permettant de classer des objets moyennant la mise en correspondance d'une image contenant la silhouette d'un objet inconnu et d'une image contenant la silhouette d'un objet con- nu. Un autre but de la présente invention est de fournir une technique de classement d'objets, qui soit simple du point de vue des calculs, tout en étant suffisamment sûre pour fonc- lO tionner d'une manière efficace même lorsque les silhouettes ne sont pas précisement en registre ou possèdent des tail- les différentes. Les buts indicués précédemment ainsi cue d'autres buts de la présente invention sont atteints grâce à un procédé incluant les étapes consistant à créer une silhouet- te d'un objet inconnu à partir d'une image numérisée, norma- liser la silhouette de l'objet inconnu par rapport à une for- me de manière à permettre sa comparaison à des silhouettes de référence d'objets connus normalisés de façon similaire, et comparer l'image normalisée de l'objet inconnu à une réfé- rence normalisée. De façon plus précise, la présente invention concer- ne un procédé d'identification d'un objet inconnu à partir d'une image numérisée de la silhouette de l'objet, moyennant la comparaison de cette image numérisée à chaque image d'une collection d'images de silhouettes d'objets connus, caractéri- sé en ce qu'il consiste à: (a) représenter l'image numérisée de la silhouette de l'objet inconnu sous la forme d'un ensemble de vecteurs verticaux; et (b) former une silhouette normalisée au moyen d'une normalisation de la largeur et de la surface de la silhouette représentée par l'ensemble des vecteurs verticaux. D'autres caractéristiques et avantages de la présen- te invention ressortiront de la description donnée ci-après faite en référence aux dessins annexés, sur lesauels: - la figure 1 représente uncroqis utile pour la com- préhension d'un système dans leauel l'invention peut être mi- se en oeuvre; - la figure 2 représente un organigramme du proces- sus en qsticn d'identification d'objets; et - la figure 3 représente un sd am utile pour la com- préhension de la manière dont une image est représentée par des vecteurs. Les techniques de reconnaissance des formes ont de nombreuses applications. Pour le but de décrire la présente invention, les formes sont ici illustrées par des images représentatives contenant des silhouettes de navires. Un spé- cialiste de la technique comprendra que la source des formes est uniquement représentative et que la présente invention peut être mise en oeuvre indépendamment de types particuliers de formes dont on effectue la reconnaissance. En se référant maintenant à la figure 1, on y voit représenté un dispositif 10 de formation d'images, mis au point sur un navire inconnu 14. Le dispositif 10 de formation d'ima- ges peut être n'importe quel dispositif connu servant à for- mer une image moyennant l'utilisation de la lumière visible ou d'un rayonnement infrarouae. L'image du navire inconnu 14 est numérisée par un numérisateur20. L'image numérisée est transmise alors à un calculateur numérique 12, dans lequel le traitement est réalisé conformément auprocessus illustré sur la figure 2 et décrit ci-après. En tant aue partie de ce traitement, l'image numérisée est comparée à des silhouettes de navires connues, mémorisées dans une mémoire 18. Les résul- ) tats des comparaisons sont envoyés à un dispositif d'utilisa- tion 11, comme par exemple un tube cathodique, ce qui permet & un opérateur humain de lire les résultats. Le dispositif de formation d'images, le numérisateur d'images 20, le cal- culateur numériaue 12 et la mémoire 18 peuvent être formés par des dispositifs connus dans la technique pour l'obtention et Je traitement d'images numérisées. En se référant maintenant à la figure 2, on note que Je traitement illustré sur cette figure est ici mis en oeuvre à l'aide de la programmation d'un calculateur numérique à usa- ge général comme par exemple un ordinateur connu sous le si- gle VAX 11/780, fabriqué par la société dite Digital Equip- ment Corporation, Maynard, Massachusetts. Les éléments rec- tangulaires de l'organigramme de la figure 2, représentés de façon typiaue par l'élément 30 et désignés ci-après sous le terme de "blocs de traitement", représentent une seule ins- truction ou un seul groupe d'instructions de lcaicieldevant être exécutées par le calculateur numérique à usage général 12 (fi- gure 1). Les éléments en forme de losanges, représentés à ti- tre d'exemple par l'élément 44 et désignés ci-après sous le terme de "blocs de décision" représentent des groupes d'ins- tructions delogiciel d'ordinateur aui évaluent une certaine condition et transmettent l'ordre d'eyécution des blocs de traitement de cette condition. Les éléments comportant des bases incurvées, représentés de façon typique par la mémoire 18, représentent une information mémorisée dans la mémoire matérielle accessible par le calculateur numérique à usage général 12 (figure 1). La mémoire est seule représentée de façon explicite aux endroits o des quantités importantes d'in- formations sont mémorisées. L'utilisation d'une mémoire com- mune à la plupart de programmesde logiciel d'ordinateur comme par exemple la mémorisation de variables d'un programme, n'est pas représentée de façon explicite. Le spécialiste de la tech- nique notera que l'initialisation des variables et des bou- cles (et d'autres éléments standards des programmes de logi- ciel d'ordinateur) n'est pas explicitement représentée. Du bloc de traitement 30, la silhouette du na- vire inconnu 14 (figure 1) est extrait' conformément à n'im- porte auel algorithme connu ou n'importe quelle combinaison d' algorithmeS. Par exemple on peut utiliser l'algorithme pour l'amélioration des bords décrit aux pages 322 à 326 du document "Digital Image Processing" de William K.Pratt, publié par John Wiley & Sons, Inc., i978, et les algorithmes pour la segmentation des bords, décrits aux pages 542-545 de ce même document. Cependant le spécialiste de la technique notera que l'on peut utiliser n'importe auel autre algo- rithme pour extraire la silhouette du navire inconnu 14 (fi- gure 1). Au niveau du bloc de traitement 32, la silhouette est vectorisée de manière à se présenter sous la forme d'un ensemble de vecteurs verticaux 74, comme représenté sur la figure 3. La figure 3 montre à titre d'exemple quelques vec- teurs d'un ensemble de N vecteurs verticaux 74, qui décrivent la silhouette 72 du navire inconnu 74 (figure 1) dans une zo- ne -'observation. Chaque vecteur vertical 74 est décrit par un couple de nomrbres représentant une valeur X et une valeur Y. Comme on peut le voir sur la figure 3, les vecteurs verti- caux 74 s'étendent depuis la partie inférieure jusqu'à la partie supérieure de la silhouette 72. On notera sur la figu- re 3 que les points de départ des vecteurs verticaux 74 sont séparés par des intervalles équidistants dans la direction X. Etant donné aue les vecteurs verticaux 74 sont espacés uni- formément dans la direction X, le nombre total N dépend de l'étendue de]a silhouette dans la direction X. La hauteur des vecteurs, c'est-à-dire les longueurs des vecteurs verti- caux dépendent de la distance entre la partie supérieure et la partie inférieure de la silhouette 72 au niveau de chaque emplacement X. Dans le bloc de traitement 34 sur la figure 2, les vecteurs verticaux 74 (figure 3), qui décrivent la silhouette du navire inconnu (14 sur la figure 1), sont ajustés de maniè- re à représenter uniquement des variations le long du bord supérieur de la silhouette, à savoir ici la superstructure du navire inconnu. Dans le bloc de traitement 34, le vecteur 761e plus petit vers le milieu du navire (figure 3), désigné ci-après par VN, est identifié comme étant le plus court de tous les vecteurs verticaux (à l'eyc]usion de quelques vec- teurs verticaux, à savcir quatre pour cent de ces vecteurs, sur le côté gauche de l'image, et à l'exclusion de Quelques vecteurs verticaux, à savoir quatre pour cent de ces vecteurs sur le côté droit de l'image). Tcus les vecteurs verticaux sont alors ajustés par soustraction de l'amplitude de VN. Cha- que élément de l'ensemble de vecteurs ajustés sera désigné ci-après par U (X). Sinon le traitement effectué dans le bloc de traitement 34 peut être omis et les vecteurs verticaux nor- malisés 74 peuvent être utilisés pour la suite du traitement. Dans le bloc de traitement 36 de la figure 2, la lar- geur de la silhouette est normalisée grâce à l'utilisation de seulement chaque CINT (N/100)-ème vecteur, CINT étant une fonction d'arrcndissement de la valeur entre parenthèses à l'entier le plus proche. L'image résultante peut toujours contenir par conséquent 100 vecteurs verticaux. Dans le bloc de traitement 38, la hauteur des vecteurs est normalisée de sorte oue la silhouette occupe une surface prédéterminée. La normalisation est réalisée conformément à la formule H(x) = U(Y)/(MSV/8) o H(X) est la hauteur normalisée du vecteur X, U(X) est la hauteur ajustée, non normalisée, du vecteur X,et MSV est la moyenne de l'ensemble de vecteurs ajustés. Dans les blocs de traitement 40,41 et 42, l'image normalisée de la silhouette du navire inconnu est comparée à des silhouettes mémorisées de navires connus. Les silhouet- tes des navires connus sont mémorisées, avant fonctionne- ment dans la mémoire 18, sous une forme normalisée vectorisée correspondant à la forme de la silhouette devant être identi- fiée après son traitement dans les blocs de traitement 30,32, 34,36 et 38. La mémoire 18 contient des images pour toutes les classes de navires, que le traitement permet d'identifier. En outre Ja mémoire 18 contient de préférence plusieurs ima- ges pour chaaue classe, représentant le navire observé sous plusieurs, ici quatre, directions d'observation différentes. Dans le bloc de traitement 40, un vecteur de l'image de réfé- rence, c'est-à-dire la silhouette connue d'une classe parti- culière de navires, est soustraite du vecteur correspondant de la silhouette reçue, normalisée et vectorisée. Etant donné que la proue du navire inconnu pourrait être située d'un côté cu de l'autre de l'image, une seconde différence est calculée dans le bloc de traitement 41. Dans le bloc de traitement 41, la différence est calculée moyennant la sélection d'un vec- teur de référence comme si l'image de référence avait été for- mée par un navire se dirigeant dans la direction opposée, c'est-à-dire aue, lorsaue le premier vecteur de référence est utilisé dans le bloc de traitement 40, le dernier vecteur de référence est utilisé dans le bloc de traitement 41; lorsaue le second est utilisé dans le bloc de traitement 40, l'avant- dernier est utilisé dans le bloc de traitement 41, et ainsi de suite.Dans le bloc de traitement 42, les valeurs absolues des différences calculées dans les blocs de traitement 40 et 41 sont cumulées. Le bloc de décision 44 déclenche la répéti- tion des blocs de traitement 40,41 et 42 pour le vecteur immé- diatement suivant dans la silhouette du navire inconnu, comme cela est déterminé dans le bloc de traitement 46, jusqu'à ce que chaque vecteur de la silhouette reçue, vectorisée et nor- malisée ait été soustrait du vecteur correspondant de l'image de référence aui est extraite de la mémoire 18. Les sommes résultantes des valeurs absolues des différences sont dési- gnées sous le terme de "scores" de l'image de référence, un score étant prévu pour l'image inconnue comparée à l'image de référence et l'autre score étant prévu pour l'image incon- nue comparée à l'image de référence dans le sens inverse. Dans le bloc de traitement 48, les scores pour le navire de réfé- rence, calculés dans les blocs de traitement 40,41 et 42, sont mémorisés dans la mémoire 50. Un spécialiste de cette tech- nique comprendra que le bloc de traitement 48 pourrait sinon traiter les scores d'une certaine manière, comme par exemple uniquement en mémorisant les scores les plus bas, de manière à réduire la auantité d'informations mémorisées dans la mémoi- re 50. Le processus de comparaison est répété jusau'à ce aue la silhouette du navire inconnu soit comparé à chaque image de référence mémorisée dans la mémoire 18, telle qu'elle est commandée par la boucle de réaction contenant le bloc de trai- tement 58. Après oue la silhouette du navire inconnu a été comparée à toutes les images de référence mémorisées dans la mémoire 18, l'image de référence présentant le score le plus faible est sélectionnée dans le bloc de traitement 54. Le na- vire de référence correspondant au score le plus bas "s'adap- te ou est en correspondance" avec le navire inconnu. Ce trai- tement identifie ainsi le navire inconnu comme appartenant à la même classe oue celle du navire de référence sélectionné. Sinon on peut utiliser une fonction de seuil telle qu'aucune classification ne serait affectée au navire inconnu sauf si le score le plus bas obtenu pour toutes les silhouettes de référence était inférieur a une certaine valeur prédéterminée. Les spécialistes de la technique comprendront que l'on peut apporter différentes modifications à la présente invention sans pour autant sortir du cadre de cette dernière. REVENDICATIONS 1. Procédé pour identifier un objet inconnu (14) à partir d'une image numérisée de la silhouette de cet objet par comparaison de J'image numérisée à chaque image faisant partie d'une collection d'images de silhouettes d'objets con- nus, caractérisé en ce qu'il comprend les étapes consistant a: (a) représenter l'image numérisée de la silhouette de l'objet inconnu (14) sous la forme d'un ensemble de vec- teurs verticaux (74); et (b) former une silhouette normalisée (72) à l'aide d'une normalisation de la largeur et de la surface de la si- lhouette telle qu'elle est représentée par l'ensemble de vec- teurs verticaux. 2. Procédé pour identifier un objet inconnu (14) se- lon la revendication 1, caractérisé en ce qu'ilcomprend en ou- tre les étapes consistant à: - (a) comparer la silhouette normalisée (72) à chaque silhouette faisant partie d'une collection de silhouettes nor- malisées connues formées à partir d'ensembles de vecteurs ver- ticaux représentant des images numérisées de silhouettes d'ob- jets connus de manière à calculer un score"'pour chacune des comparaisons, un tel éscore étant égal à la somme des valeurs absolues des différences entre chaque vecteur vertical (74) contenu dans la silhouette normalisée inconnue (72) et le vec- teur correspondant situé dans chacune des silhouettes norma- lisées connues. 3. Procédé pour identifier un objet inconnu (14) se- lon la revendication 2, caractérisé en ce au'ilcomprend en ou- tre l'étape consistant à identifier l'objet inconnu comme ap- ) partenant à la même classe que celle de l'objet connu, & par- tir de laquelle la silhouette normalisée connue correspondant au "score le plus bas calculé a été formée. 4. Procédé pour identifier un navire inconnu (14) selon la revendication 3, caractérisé en ce que lacollection des silhouettes normalisées connues inclut des silhouettes formées de navires vus sous différents angles d'observation.