FR3046281A1

FR3046281A1 - METHOD AND DEVICE FOR AUTOMATICALLY DETECTING A ZONE OF INTEREST OF A DIGITAL IMAGE

Info

Publication number: FR3046281A1
Application number: FR1563331A
Authority: FR
Inventors: Bruno Girard; Alain Prola; Marc Berenguer
Original assignee: Orange SA
Current assignee: Orange SA
Priority date: 2015-12-24
Filing date: 2015-12-24
Publication date: 2017-06-30

Abstract

Le procédé selon l'invention comprend : - une étape (E10) de partitionnement de l'image en une pluralité de sous-images ; - une étape (E20) de détermination, pour chaque sous-image, d'un point remarquable de la sous-image au regard d'un modèle d'attraction prédéterminé et d'un poids associé à ce point remarquable ; - une étape (E30) de génération, selon une distribution et une densité prédéfinies, d'un ensemble de points virtuels sur l'image, chaque point virtuel étant associé à un poids déterminé à partir d'une valeur de consigne prédéfinie considérée comme représentative de la zone d'intérêt ; - une étape (E40) de sélection, pour chaque point virtuel généré, de la sous-image dont le point remarquable exerce une force d'attraction maximale conformément au modèle d'attraction prédéterminé sur le point virtuel ; et - une étape (E50) de détection de ladite zone d'intérêt à partir des points remarquables des sous-images sélectionnées.The method according to the invention comprises: a step (E10) for partitioning the image into a plurality of sub-images; a step (E20) of determining, for each subimage, a remarkable point of the sub-image with regard to a predetermined model of attraction and a weight associated with this remarkable point; a step (E30) of generation, according to a predefined distribution and density, of a set of virtual points on the image, each virtual point being associated with a weight determined from a predefined target value considered as representative the area of interest; a step (E40) for selecting, for each generated virtual point, the sub-image whose remarkable point exerts a maximum attraction force in accordance with the predetermined attraction model on the virtual point; and a step (E50) of detecting said zone of interest from the remarkable points of the selected sub-images.

Description

Arrière-plan de l'invention L'invention se rapporte au domaine générai du traitement d'images numériques.BACKGROUND OF THE INVENTION The invention relates to the general field of digital image processing.

Elle concerne plus particulièrement la détection automatique d'une zone d'intérêt (ou ROI pour « Région Of Interest » en anglais) sur une image numérique, telle que par exemple une image codée en niveaux de gris. L'invention a une application privilégiée mais non limitative dans le domaine notamment de l'imagerie médicale, dans lequel des images numériques haute définition ou très haute définition (i.e. de plusieurs gigaoctets voire dizaines de gigaoctets) sont couramment utilisées, et la détection de zones d'intérêt sur de telles images suscite un réel intérêt. On peut citer par exemple la détection des contours d'une lésion sur une image illustrant un examen radiographique pratiqué sur un patient.It relates more particularly to the automatic detection of an area of interest (or ROI for "Region Of Interest" in English) on a digital image, such as for example a grayscale-coded image. The invention has a preferred but nonlimiting application in the field of medical imaging in particular, in which high definition or very high definition digital images (ie of several gigabytes or even tens of gigabytes) are commonly used, and the detection of zones interest in such images arouses real interest. For example, the detection of contours of a lesion on an image illustrating a radiographic examination performed on a patient may be mentioned.

Le développement et le déploiement des technologies de l'information permettent aujourd'hui d'envisager dans le domaine de l'imagerie médicale l'échange intensif entre plusieurs personnes (ex. praticiens, patients) d'images haute (ou très) définition, via un réseau de télécommunications. Les équipements générateurs de telles images sont en effet maintenant nombreux et divers, de même que les terminaux dédiés à l'utilisation de ces images (interprétation, diagnostic, communications diverses), et les volumes de données afférentes à ce domaine sont en perpétuelle croissance.The development and deployment of information technologies makes it possible today to consider in the field of medical imaging the intensive exchange between several people (eg practitioners, patients) of high (or very) high definition images. via a telecommunications network. The equipment generating such images is indeed now numerous and diverse, as well as the terminals dedicated to the use of these images (interpretation, diagnosis, various communications), and the data volumes relating to this field are in perpetual growth.

Dans ce contexte, le stockage, le traitement et le transport de telles images constituent des enjeux importants.In this context, the storage, processing and transport of such images are important issues.

Pour optimiser le transport et le stockage une telle image, il est connu de mettre en oeuvre une détection des zones d'intérêt de l'image, en tenant compte de critères caractéristiques de ces zones (ex. propriétés spécifiques). Cette détection permet d'extraire de l'image uniquement une ou plusieurs régions (ex. modélisées par des rectangles) englobant la ou les zones d'intérêt détectées pour réduire la volumétrie des données destinées à être transportées et/ou stockées. EN outre, cette volumétrie peut être encore réduite en appliquant un traitement aux zones d'intérêt détectées par rapport au reste de l'image (« fond »). Un tel traitement peut consister par exemple en un filtrage (vectorisation légère des zones d'intérêt, réduction de la définition ou de la profondeur du fond de l'image) ou en une compression différentielle des zones d'intérêt par rapport au fond de l'image.To optimize the transport and the storage such an image, it is known to implement a detection of the areas of interest of the image, taking into account the characteristic criteria of these areas (eg specific properties). This detection makes it possible to extract from the image only one or more regions (eg modeled by rectangles) encompassing the area or zones of interest detected to reduce the volume of the data intended to be transported and / or stored. In addition, this volume can be further reduced by applying a treatment to the areas of interest detected relative to the rest of the image ("background"). Such a treatment can consist, for example, in a filtering (light vectorization of the areas of interest, reduction of the definition or depth of the image background) or in differential compression of the areas of interest with respect to the background of the image. 'picture.

Les techniques de détection de zones d'intérêt sur une image s'appuient essentiellement aujourd'hui sur des techniques géométriques analytiques (utilisant notamment des transformées de Fourier) ou sur des simulations numériques relativement longues et complexes (ex. techniques utilisant des transformations de type « watershed ») qui peuvent en outre s'avérer inefficaces dans certains cas en raison des hypothèses sur lesquelles elles s'appuient. Il existe donc un besoin d'un procédé de détection simple et efficace permettant de détecter sur une image une ou plusieurs zones d'intérêt.The techniques for detecting areas of interest on an image are essentially based today on analytical geometrical techniques (notably using Fourier transforms) or on relatively long and complex numerical simulations (eg techniques using transformations of the type "Watershed"), which may be ineffective in some cases because of the assumptions on which they are based. There is therefore a need for a simple and effective detection method for detecting on one image one or more areas of interest.

Objet et résumé de l'invention L'invention répond notamment à ce besoin en proposant un procédé de détection automatique d'une zone d'intérêt d'une image numérique, ce procédé comprenant : — une étape de partitionnement de l'image en une pluralité de sous-images ; — une étape de détermination, pour chaque sous-image, d'un point remarquable de la sous-image au regard d'un modèle d'attraction prédéterminé et d'un poids associé à ce point remarquable ; — une étape de génération, selon une distribution et une densité prédéfinies, d'un ensemble de points virtuels sur l'image, chaque point virtuel étant associé à un poids déterminé à partir d'une valeur de consigne prédéfinie considérée comme représentative de la zone d'intérêt ; — une étape de sélection, pour chaque point virtuel généré, de la sous-image dont le point remarquable exerce une force d'attraction maximale conformément au modèle d'attraction prédéterminé sur le point virtuel ; et — une étape de détection de la zone d'intérêt à partir des points remarquables des sous-images sélectionnées.OBJECT AND SUMMARY OF THE INVENTION The invention responds in particular to this need by proposing a method of automatically detecting an area of interest of a digital image, this method comprising: a step of partitioning the image into a plurality of sub-images; A step of determining, for each sub-image, a remarkable point of the sub-image with regard to a predetermined model of attraction and a weight associated with this remarkable point; A step of generating, according to a predefined distribution and density, a set of virtual points on the image, each virtual point being associated with a weight determined from a predefined target value considered representative of the zone; of interest; A step of selecting, for each generated virtual point, the sub-image whose remarkable point exerts a maximum attraction force in accordance with the predetermined attraction model on the virtual point; and a step of detecting the zone of interest from the remarkable points of the selected sub-images.

Corrélativement, l'invention vise également un dispositif de détection automatique d'une zone d'intérêt d'une image numérique, ce dispositif comprenant : — un module de partitionnement, configuré pour partitionner limage en une pluralité de sous-images ; — un module de détermination, configuré pour déterminer pour chaque sous-image point remarquable de la sous-image au regard d'un modèle d'attraction prédéterminé et d'un poids associé à ce point remarquable ; — un module de génération, configuré pour générer selon une distribution et une densité prédéfinies un ensemble de points virtuels sur l'image, chaque point virtuel étant associé à un poids déterminé à partir d'une valeur de consigne prédéfinie considérée comme représentative de la zone d'intérêt ; — un module de sélection, configuré pour sélectionner pour chaque point virtuel généré la sous-image dont le point remarquable exerce une force d'attraction maximale conformément au modèle d'attraction prédéterminé sur le point virtuel ; et — un module de détection, configuré pour détecter la zone d'intérêt à partir des points remarquabels des sous-images sélectionnées.Correlatively, the invention also relates to a device for automatically detecting an area of interest of a digital image, this device comprising: a partitioning module configured to partition the image into a plurality of sub-images; A determination module configured to determine for each sub-image a remarkable point of the sub-image with regard to a predetermined model of attraction and a weight associated with this remarkable point; A generation module, configured to generate, according to a predefined distribution and density, a set of virtual points on the image, each virtual point being associated with a weight determined from a predefined target value considered representative of the zone; of interest; A selection module, configured to select for each virtual point generated the sub-image whose remarkable point exerts a maximum attraction force in accordance with the predetermined attraction model on the virtual point; and a detection module, configured to detect the zone of interest from the remarkable points of the selected sub-images.

Dans un mode privilégié de réalisation et à titre d'exemple : — le modèle d'attraction prédéterminé est un modèle de gravitation universelle ; — le point remarquable de la sous-image au regard du modèle d'attraction prédéterminé est un centre de gravité de la sous-image ; et — la force d'attraction est une force de gravitation exercée par la centre de gravité sur la point virtuel. L'invention propose donc un procédé simple permettant la détection automatique de zones d'intérêt dans une image numérique, telle que par exemple une image codée en niveaux de gris. Par zone d'intérêt, on entend une zone de l'image numérique jugée intéressante pour son analyse ou qui correspond/représente un objet recherché, et présente des propriétés locales remarquables.In a preferred embodiment and by way of example: the predetermined attraction model is a model of universal gravitation; The remarkable point of the sub-image with regard to the predetermined attraction model is a center of gravity of the sub-image; and the attraction force is a gravitational force exerted by the center of gravity on the virtual point. The invention thus proposes a simple method allowing the automatic detection of zones of interest in a digital image, such as for example a gray-scale coded image. By zone of interest, we mean an area of the digital image considered interesting for its analysis or which corresponds / represents a desired object, and has remarkable local properties.

De façon connue en soi, une image numérique peut être modélisée sous forme d'une matrice de pixels, chaque pixel ayant une couleur traduisant un poids du pixel dans l'image. Dans l'exemple d'une image en niveau de gris, ce poids traduit par exemple la densité ou encore la profondeur du pixel, c'est-à-dire un niveau de gris. On note que le poids d'un pixel peut résulter d'une mesure réalisée par un capteur ; ainsi par exemple, il peut traduire une mesure de fréquence par le capteur photographique CCD (pour Charge Coupled Device en anglais ou « dispositif à transfert de charge), une mesure de densité par un capteur de scanner, un nombre de photons gamma mesuré par un photodétecteur, un délai mesuré par un capteur d'échographe, etc. L'invention propose un procédé en rupture avec les procédés de détection de l'état de la technique qui s'appuie sur trois mécanismes pour détecter automatiquement les zones d'intérêt d'une image, à savoir : — le partitionnement de l'image numérique en une pluralité de sous-images ; — la génération d'une pluie aléatoire de « gouttes » (c'est-à-dire de points virtuels) sur l'image selon une distribution et une densité prédéfinies, chacune des gouttes générées étant associée à un poids déterminé à partir d'une valeur de consigne considérée comme étant représentative d'un poids d'un pixel de la zone d'intérêt. Par exemple, chaque goutte générée est associée à un poids égal à la valeur de consigne. Il convient de noter que la détermination de la valeur de consigne ne présente en soi aucune difficulté pour l'homme du métier (à partir par exemple de la sensibilité du capteur utilisé pour générer les pixels de l'image et/ou de sa connaissance des caractéristiques de la zone d'intérêt recherchée) ; et — la migration des gouttes de pluie générées selon un modèle d'attraction prédéfini (ex. gravitation universelle) vers la ou les zones d'intérêt de l'image correspondant à la valeur de consigne et donc exerçant une force d'attraction maximale sur ces gouttes qui ont elles-mêmes un poids proche de cette valeur de consigne. Cette migration permet d'identifier les zones d'intérêt : les points remarquables de l'image (ex. barycentres ou centres de gravité l'exemple précité de la gravitation universelle) vers lesquels ont migré les gouttes définissent en effet les zones d'intérêt recherchées.In a manner known per se, a digital image can be modeled as a matrix of pixels, each pixel having a color reflecting a weight of the pixel in the image. In the example of a gray level image, this weight for example reflects the density or the depth of the pixel, that is to say a gray level. It is noted that the weight of a pixel can result from a measurement made by a sensor; for example, it can translate a frequency measurement by the CCD (charged charge coupled device), a density measurement by a scanner sensor, a number of gamma photons measured by a photodetector, a time measured by an ultrasound sensor, etc. The invention proposes a method that breaks with state-of-the-art detection methods that relies on three mechanisms for automatically detecting the areas of interest of an image, namely: partitioning the image digital in a plurality of sub-images; Generating a random rain of "drops" (that is to say virtual points) on the image according to a predefined distribution and density, each of the drops generated being associated with a weight determined from a setpoint considered to be representative of a weight of one pixel of the area of interest. For example, each drop generated is associated with a weight equal to the set value. It should be noted that the determination of the setpoint does not present any difficulty for the skilled person (from, for example, the sensitivity of the sensor used to generate the pixels of the image and / or its knowledge of the images. characteristics of the area of interest sought); and the migration of the raindrops generated according to a predefined attraction model (eg universal gravitation) towards the zone or zones of interest of the image corresponding to the setpoint value and thus exerting a maximum force of attraction on these drops which themselves have a weight close to this set value. This migration makes it possible to identify the zones of interest: the remarkable points of the image (eg centroids or gravity centers the aforementioned example of universal gravitation) to which the drops have migrated define the zones of interest sought.

La combinaison de ces trois mécanismes permet une détection automatique, robuste et fiable des zones d'intérêt comprises dans l'image numérique. En outre, l'exécution du procédé de détection selon l'invention peut être très rapide, l'étape de sélection pouvant être mise en œuvre en parallèle pour chaque point virtuel généré.The combination of these three mechanisms allows automatic, robust and reliable detection of the areas of interest included in the digital image. In addition, the execution of the detection method according to the invention can be very fast, the selection step can be implemented in parallel for each virtual point generated.

Par ailleurs, conformément à l'invention, la ou les zones d'intérêt d'une image numérique sont détectées à partir des points remarquables (ex. centres de gravité pour un modèle de gravitation universelle) des sous-images résultant du partitionnement de l'image numérique qui ont été sélectionnées au cours de l'étape de sélection, autrement dit vers lesquels ont migré les points virtuels (gouttes) générés. On obtient donc à l'issue du procédé selon l'invention une représentation selon une forme condensée de la ou des zones d'intérêt de l'image numérique (i.e. sous la forme d'un ensemble de points remarquables). La détection des zones d'intérêt permise par l'invention permet ainsi avantageusement de minimiser le nombre d'octets à transmettre sur un réseau de télécommunication lors de la diffusion de l'image ou lors de son stockage.Furthermore, according to the invention, the area or areas of interest of a digital image are detected from the remarkable points (eg centers of gravity for a universal gravitation model) of the sub-images resulting from the partitioning of the image. digital image that have been selected during the selection step, that is, to which virtual points (drops) have been generated. At the end of the method according to the invention, a representation in a condensed form of the region or areas of interest of the digital image (i.e. in the form of a set of remarkable points) is thus obtained. The detection of the zones of interest allowed by the invention thus advantageously makes it possible to minimize the number of bytes to be transmitted on a telecommunication network during the diffusion of the image or during its storage.

On note que l'invention a une application privilégiée lorsque des images numériques de grande taille sont considérées, par exemple des images haute définition ou très haute définitions comme celles utilisées classiquement dans le domaine médical. Toutefois aucune limitation n'est attachée au type d'images ni au domaine auquel s'applique l'invention.Note that the invention has a preferred application when large digital images are considered, for example high definition images or very high definitions such as those conventionally used in the medical field. However, no limitation is attached to the type of images or to the field to which the invention applies.

Dans un mode particulier de réalisation, au cours de l'étape de partitionnement, l'image est partitionnée récursivement en un nombre prédéterminé k d'images sur une pluralité de niveaux de partitionnement.In a particular embodiment, during the partitioning step, the image is recursively partitioned into a predetermined number k of images over a plurality of partitioning levels.

En outre, l'étape de sélection peut également être mise en oeuvre récursivement sur tout ou partie des niveaux de partitionnement. Dans ce cas, une sous-image est sélectionnée à chaque niveau de partitionnement considéré, et au cours de l'étape de sélection récursive, une sous-image est sélectionnée sur un niveau de partitionnement parmi les sous-images résultant du partitionnement en k sous-images d'une sous-image sélectionnée sur un niveau de partitionnement précédent.In addition, the selection step can also be implemented recursively on all or part of the partitioning levels. In this case, a sub-image is selected at each partitioning level considered, and during the recursive selection step, a sub-image is selected on a partitioning level among the sub-images resulting from k partitioning. -images of a selected subpicture on a previous partitioning level.

Corrélativement, dans ce mode de réalisation particulier, dans le dispositif de détection : — le module de partitionnement est configuré pour partitionner l'image de manière récursive en un nombre prédéterminé k d'images sur une pluralité de niveaux de partitionnement ; et — le module de sélection est configuré pour sélectionner récursivement une sous-image sur tout ou partie de ladite pluralité de niveaux de partitionnement, une sous-image étant sélectionnée par le module de sélection sur un niveau de partitionnement parmi les sous-images résultant du partitionnement en k sous-images d'une sous-image sélectionnée par ledit module de sélection sur un niveau de partitionnement précédent.Correlatively, in this particular embodiment, in the detection device: the partitioning module is configured to partition the image recursively into a predetermined number k of images on a plurality of partitioning levels; and the selection module is configured to recursively select a sub-image on all or part of said plurality of partitioning levels, a sub-image being selected by the selection module on a partitioning level among the sub-images resulting from the partitioning into k subpictures of a sub-image selected by said selection module on a previous partitioning level.

Ce mode de réalisation récursif facilite la mise en oeuvre de l'invention. Il permet notamment de minimiser la complexité des calculs de force d'attraction réalisés entre chaque point virtuel et son voisinage dans l'image numérique lors de l'étape de sélection.This recursive embodiment facilitates the implementation of the invention. In particular, it makes it possible to minimize the complexity of the attraction force calculations made between each virtual point and its neighborhood in the digital image during the selection step.

Par ailleurs, les inventeurs ont constaté qu'une détection correcte de la zone d'intérêt peut être réalisée moyennant le recours à un faible nombre de niveaux de partitionnement (par exemple 4-5).Moreover, the inventors have found that a correct detection of the area of interest can be achieved using a small number of partitioning levels (eg 4-5).

Dans un mode particulier de réalisation, le nombre k considéré lors de l'étape de partitionnement est égal à 4.In a particular embodiment, the number k considered during the partitioning step is equal to 4.

Par exemple, l'image numérique est partitionnée en quatre cadrans ou sous-images rectangulaires ou carrées, eux-mêmes partitionné(e)s en quatre cadrans ou sous-images, etc., i.e. à chaque niveau de partitionnement, l'image est divisée en quatre cadrans identiques ici. On obtient ainsi, à l'issue de l'étape de partitionnement, un arbre quaternaire ou « quadtree » en anglais dans cet exemple spécifique de k=4, basé dans le cas d'un modèle de gravitation universelle sur les barycentres des points de chaque cadran de l'image. De façon connue, un « quadtree » est un arbre dont chaque nœud est composé d'exactement quatre fils correspondant aux quatre cadrans de l'image ou de la sous-image subdivisée au niveau de partitionnement auquel appartient le nœud.For example, the digital image is partitioned into four rectangular or square quadrants or sub-images, themselves partitioned into four quadrants or sub-images, etc., ie at each level of partitioning, the image is divided into four identical dials here. Thus, at the end of the partitioning step, a quaternary tree or "quadtree" is obtained in English in this specific example of k = 4, based in the case of a universal gravitation model on the barycentres of the each dial of the image. In a known manner, a "quadtree" is a tree in which each node is composed of exactly four threads corresponding to the four dials of the image or sub-image subdivided at the level of partitioning to which the node belongs.

Bien que ce mode de réalisation soit particulièrement simple à mettre en œuvre, le nombre k peut prendre d'autres valeurs, et les sous-images résultant du partitionnement de l'image numérique avoir d'autres formes qu'une forme rectangulaire ou carrée, comme par exemple une forme triangulaire.Although this embodiment is particularly simple to implement, the number k may take other values, and the sub-images resulting from the partitioning of the digital image may have other shapes than a rectangular or square shape, as for example a triangular shape.

Comme mentionné précédemment, dans un mode particulier de réalisation, la force d'attraction maximisée lors de l'étape de sélection est une force de gravitation exercée par le centre de gravité de la sous-image considérée sur le point virtuel.As mentioned above, in a particular embodiment, the maximized attraction force during the selection step is a gravitational force exerted by the center of gravity of the subimage considered on the virtual point.

Cette force de gravitation a une expression analytique relativement simple qui dépend du poids des points virtuels et de celui des centres de gravité. Toutefois, en variante, d'autres modèles d'attraction peuvent être envisagés.This gravitational force has a relatively simple analytical expression that depends on the weight of the virtual points and that of the centers of gravity. However, alternatively, other models of attraction can be envisaged.

Dans un mode particulier de réalisation, la force de gravitation est pondérée par un facteur de correction tenant compte d'un écart entre le poids du centre de gravité et la valeur de consigne.In a particular embodiment, the gravitational force is weighted by a correction factor taking into account a difference between the weight of the center of gravity and the set value.

Cette pondération permet avantageusement de s'assurer que les points virtuels ne sont pas attirés par des centres de gravité éloignés de la zone d'intérêt. Le facteur de pondération appliqué peut être choisi par exemple de sorte à atténuer fortement la force de gravitation exercée par ces centres de gravité, ou à l'inverse à majorer la force de gravitation exercée par les centres de gravité des sous-images appartenant à la zone d'intérêt. Un choix approprié de ce facteur permet avantageusement d'accélérer la migration des points virtuels vers la zone d'intérêt.This weighting advantageously ensures that the virtual points are not attracted by centers of gravity remote from the area of interest. The weighting factor applied can be chosen for example so as to strongly attenuate the gravitational force exerted by these centers of gravity, or conversely to increase the gravitational force exerted by the centers of gravity of the subpictures belonging to the area of interest. An appropriate choice of this factor advantageously makes it possible to accelerate the migration of the virtual points towards the area of interest.

Dans un autre mode de réalisation, la distribution des points virtuels considérée lors de l'étape de génération est une distribution uniforme sur l'image.In another embodiment, the distribution of the virtual points considered during the generation step is a uniform distribution on the image.

En variante, d'autres distributions peuvent être envisagées comme par exemple une distribution gaussienne.Alternatively, other distributions may be envisaged such as a Gaussian distribution.

Par ailleurs, préférentiellement, on choisit une densité des points virtuels telle que le nombre de points virtuels générés est bien inférieur à celle des points de l'image numérique source pour avoir une description « allégée » de la zone d'intérêt et ne pas trop ralentir l'exécution du procédé de détection selon l'invention. Par exemple on génère un nombre de points virtuels égal à environ 20% du nombre de pixels de l'image numérique source.Furthermore, preferentially, a density of virtual points is chosen such that the number of virtual points generated is much less than that of the points of the source digital image to have a "light" description of the area of interest and not too much to slow down the execution of the detection method according to the invention. For example, a virtual number of points equal to about 20% of the number of pixels of the source digital image is generated.

Dans un mode particulier de réalisation, les différentes étapes du procédé de détection sont déterminées par des instructions de programmes d'ordinateurs.In a particular embodiment, the different steps of the detection method are determined by instructions of computer programs.

En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations ou d'enregistrement, ce programme étant susceptible d'être mis en œuvre dans un dispositif de détection ou plus généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre des étapes d'un procédé de détection tel que décrit ci-dessus.Consequently, the invention also relates to a computer program on an information or recording medium, this program being capable of being implemented in a detection device or more generally in a computer, this program comprising instructions adapted to the implementation of the steps of a detection method as described above.

Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations ou d'enregistrement lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus.This program can use any programming language, and be in the form of source code, object code, or intermediate code between source code and object code, such as in a partially compiled form, or in any other form desirable shape. The invention also relates to a computer-readable information or recording medium and comprising instructions of a computer program as mentioned above.

Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet.The information carrier may be any entity or device capable of storing the program. For example, the medium may comprise storage means, such as a ROM, for example a CD ROM or a microelectronic circuit ROM, or a magnetic recording medium, for example a floppy disk or a disk. hard. On the other hand, the information medium may be a transmissible medium such as an electrical or optical signal, which may be conveyed via an electrical or optical cable, by radio or by other means. The program according to the invention can be downloaded in particular on an Internet type network.

Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question.Alternatively, the information carrier may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the execution of the method in question.

On peut également envisager, dans d'autres modes de réalisation, que le procédé de détection et le dispositif de détection selon l'invention présentent en combinaison tout ou partie des caractéristiques précitées.It can also be envisaged, in other embodiments, that the detection method and the detection device according to the invention present in combination all or some of the aforementioned characteristics.

Brève description des dessins D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif. Sur les figures : — la figure 1 représente, de façon schématique, un dispositif de détection selon l'invention, dans un mode particulier de réalisation ; — la figure 2 illustre l'architecture matérielle du dispositif de détection de la figure 1 dans un mode particulier de réalisation ; — la figure 3 représente les principales étapes d'un procédé de détection selon l'invention dans un mode particulier de réalisation dans lequel il est mis en oeuvre par le dispositif de la figure i; — la figure 4 illustre une arborescence de sous-images résultant du partitionnement d'une image numérique ; — la figure 5 représente une cartographie des centres de gravité des sous-images de la figure 4 ; — la figure 6 illustre la mise en œuvre récursive d'une étape du procédé représenté à la figure 3 ; et — la figure 7 illustre un exemple d'application de l'invention à une image numérique médicale. Description détaillée de l'inventionBRIEF DESCRIPTION OF THE DRAWINGS Other features and advantages of the present invention will emerge from the description given below, with reference to the accompanying drawings which illustrate an embodiment having no limiting character. In the figures: - Figure 1 shows, schematically, a detection device according to the invention, in a particular embodiment; FIG. 2 illustrates the hardware architecture of the detection device of FIG. 1 in a particular embodiment; FIG. 3 represents the main steps of a detection method according to the invention in a particular embodiment in which it is implemented by the device of FIG. FIG. 4 illustrates a tree of sub-images resulting from the partitioning of a digital image; FIG. 5 represents a map of the centers of gravity of the sub-images of FIG. 4; FIG. 6 illustrates the recursive implementation of a step of the method represented in FIG. 3; and FIG. 7 illustrates an example of application of the invention to a medical digital image. Detailed description of the invention

La figure 1 représente, dans son environnement, un dispositif de détection 1 conforme à l'invention, configuré pour détecter une ou plusieurs zones d'intérêt ROI sur une image numérique IM conformément à un mode particulier de réalisation.FIG. 1 represents, in its environment, a detection device 1 according to the invention, configured to detect one or more areas of interest ROI on an IM digital image in accordance with a particular embodiment.

Dans l'exemple envisagé ici, l'image numérique IM traitée par le dispositif de détection 1 est une image haute définition (occupant par exemple plusieurs giga octets), en deux dimensions et codée en niveaux de gris. Elle est ici carrée de dimension 2nx2n où n désigne un entier supérieur à 1. Une telle image est par exemple une image fournie au dispositif de détection 1 par un scanner ou un dispositif de radiographie classiquement utilisés dans le domaine médical, représentant une partie du corps d'un patient, et la zone d'intérêt recherchée ROI est par exemple une lésion affectant cette partie du corps.In the example envisaged here, the digital image IM processed by the detection device 1 is a high definition image (occupying, for example, several gigabytes), in two dimensions and coded in gray levels. It is here square of dimension 2nx2n where n denotes an integer greater than 1. Such an image is for example an image supplied to the detection device 1 by a scanner or a radiography device conventionally used in the medical field, representing a part of the body of a patient, and the area of interest sought ROI is for example a lesion affecting this part of the body.

Toutefois l'invention s'applique avantageusement à d'autres types d'images, fixe ou issues de flux vidéo, en couleur ou noir et blanc, en deux ou trois dimensions, et dans d'autres contextes.However, the invention advantageously applies to other types of images, fixed or from video streams, in color or black and white, in two or three dimensions, and in other contexts.

De façon connue en soi, chaque image numérique peut être représentée par une matrice de pixels c'est-à-dire de points, chaque pixel ayant une couleur ou un niveau de gris traduisant son poids dans l'image et résultant des mesures ayant conduit à l'image IM (par exemple mesures de fréquence pour un capteur CCD d'un appareil photographique, mesures de densité pour un capteur de scanner, mesure d'un nombre de photons gamma pour un photodétecteur, mesure de délais pour un capteur d'échographe, etc.). Le poids de chaque pixel est dans le cas de l'image IM codée en niveau de gris le niveau de gris du pixel, codé sur un nombre prédéterminé d'octets.In a manner known per se, each digital image can be represented by a matrix of pixels that is to say points, each pixel having a color or a gray level reflecting its weight in the image and resulting from the measurements having led to the IM image (eg frequency measurements for a CCD sensor of a camera, density measurements for a scanner sensor, measurement of a number of gamma photons for a photodetector, measurement of delays for a sensor of a camera ultrasound, etc.). The weight of each pixel is in the case of the IM image coded in gray level the gray level of the pixel, encoded on a predetermined number of bytes.

Dans le mode de réalisation décrit ici, le dispositif de détection 1 a l'architecture matérielle d'un ordinateur tel que représenté schématiquement à la figure 2. Il comprend notamment un processeur 2, une mémoire vive 3, une mémoire morte 4, une mémoire non volatile 5 ainsi qu'un module de communication 6 permettant au dispositif de détection 1 de communiquer par exemple via un réseau de télécommunications filaire ou sans fil, mobile ou fixe, avec d'autres dispositifs.In the embodiment described here, the detection device 1 has the hardware architecture of a computer as shown diagrammatically in FIG. 2. It notably comprises a processor 2, a random access memory 3, a read-only memory 4, a memory non-volatile 5 and a communication module 6 allowing the detection device 1 to communicate for example via a wired or wireless telecommunications network, mobile or fixed, with other devices.

La mémoire morte 4 du dispositif de détection 1 constitue un support d'enregistrement conforme à l'invention, lisible par le processeur 2 et sur lequel est enregistré un programme d'ordinateur PROG conforme à l'invention, comportant des instructions pour l'exécution des étapes d'un procédé de détection conforme à l'invention.The read-only memory 4 of the detection device 1 constitutes a recording medium in accordance with the invention, readable by the processor 2 and on which is recorded a computer program PROG according to the invention, comprising instructions for execution. steps of a detection method according to the invention.

Ce programme d'ordinateur définit de façon équivalente des modules fonctionnels (et logiciels ici) du dispositif de détection 1, configurés pour mettre en œuvre les étapes du procédé de détection selon l'invention. Ces modules fonctionnels s'appuient ou commandent les éléments physiques matériels 2-6 du dispositif 1 décrits précédemment. Ils comprennent ainsi ici : — un module IA de partitionnement de l'image source destinée à être traiter par le dispositif de détection 1 (image IM dans l'exemple envisagé ici), en une pluralité de sous-images ; — un module IB de détermination configuré pour déterminer pour chaque sous-image un point remarquable de la sous-image au regard d'un modèle d'attraction prédéterminé, par exemple un centre de gravité (i.e. barycentre) pour un modèle d'attraction de type gravitation universelle, et un poids associé à ce point remarquable ; — un module IC de génération d'une pluie aléatoire de points virtuels sur l'image, selon une distribution et une densité prédéfinies ; — un module 1D de sélection, configuré pour sélectionner pour chaque point virtuel généré une sous-image dont le point remarquable de la sous-image exerce sur ce point virtuel une force d'attraction maximale (force de gravitation dans le cas précité du modèle d'attration de type gravitation universelle) ; et — un module 1E de détection d'une ou de plusieurs zones d'intérêt (ROI) sur l'image traitée à partir des points remarquables (ex. centres de gravité) des sous-images sélectionnées par le module de sélection.This computer program equivalently defines functional modules (and software here) of the detection device 1, configured to implement the steps of the detection method according to the invention. These functional modules support or control the physical hardware elements 2-6 of the device 1 described above. They thus comprise here: an IA module for partitioning the source image intended to be processed by the detection device 1 (IM image in the example envisaged here), into a plurality of sub-images; A determination module IB configured to determine for each subimage a remarkable point of the subimage in relation to a predetermined attraction model, for example a center of gravity (ie barycenter) for a model of attraction of universal gravitation type, and a weight associated with this remarkable point; An IC module for generating a random rain of virtual points on the image, according to a predefined distribution and density; A selection module 1D, configured to select for each virtual point generated a sub-image whose remarkable point of the subimage exerts on this virtual point a maximum force of attraction (gravitational force in the aforementioned case of the model d attrition of the universal gravitation type); and a module 1E for detecting one or more zones of interest (ROI) on the image processed from the remarkable points (eg centers of gravity) of the sub-images selected by the selection module.

Les fonctions de ces modules sont décrites maintenant plus en détail en référence à la figure 3.The functions of these modules are now described in more detail with reference to FIG.

La figure 3 représente, sous forme d'ordinogramme, les principales étapes d'un procédé de détection de zones d'intérêt sur une image numérique, conforme à l'invention, dans un mode particulier de réalisation dans lequel il est mis en œuvre par le dispositif de détection 1 de la figure 1 sur l'image numérique IM.FIG. 3 represents, in the form of a flow chart, the main steps of a method of detecting zones of interest on a digital image, in accordance with the invention, in a particular embodiment in which it is implemented by the detection device 1 of Figure 1 on the digital image IM.

Conformément à l'invention, le dispositif de détection 1 procède en premier lieu à un partitionnement de l'image numérique IM en une pluralité de sous-images (étape E10). Dans le mode de réalisation décrit ici, ce partitionnement de l'image IM est réalisé de manière récursive, sur une pluralité de niveaux de partitionnement.In accordance with the invention, the detection device 1 first proceeds to partition the digital image IM into a plurality of sub-images (step E10). In the embodiment described here, this partitioning of the IM image is performed recursively, on a plurality of partitioning levels.

Plus précisément, l'image numérique IM est décomposée récursivement ici par le module de partitionnement IA sous la forme d'un arbre quaternaire ou « quadtree » en anglais, i.e., à chaque niveau de partitionnement, l'image ou la sous-image considérée est divisée en un nombre k=4 sous-images (i.e. 4 cadrans). Ainsi, à chaque niveau LEV de l'arborescence résultant du partitionnement récursif de l'image IM, chaque nœud est formé par une image (ou une sous-image) et est relié à exactement quatre nœuds fils correspondant respectivement aux quatre cadrans Ql, Q2, Q3 et Q4 de cette image (ou sous-image). La figure 4 illustre une telle arborescence pour trois niveaux LEV=1, 2, 3.More precisely, the digital image IM is recursively decomposed here by the partitioning module IA in the form of a quaternary tree or "quadtree" in English, ie, at each level of partitioning, the image or the sub-image considered is divided into a number k = 4 sub-images (ie 4 dials). Thus, at each LEV level of the tree resulting from the recursive partitioning of the IM image, each node is formed by an image (or a sub-image) and is connected to exactly four child nodes respectively corresponding to the four quadrants Q1, Q2. , Q3 and Q4 of this image (or sub-image). Figure 4 illustrates such a tree structure for three levels LEV = 1, 2, 3.

On note que par souci de simplification, on note Ql, Q2, Q3 et Q4 les quatre cadrans obtenus pour chaque image ou sous-image, indépendamment du niveau de partitionnement auquel on fait référence et de l'image ou sous-image considérée à ce niveau.It should be noted that, for the sake of simplification, the four dials obtained for each image or subimage, regardless of the level of partitioning referred to and the image or subimage considered for this purpose, are noted Q1, Q2, Q3 and Q4. level.

Le critère d'arrêt du partitionnement récursif est ici l'obtention de sous-images de dimension 2 pixels par 2 pixels. Autrement dit, pour une image numérique IM carrée de taille 2nx2n pixels, n niveaux de partitionnement sont envisagés.The criterion for stopping recursive partitioning is here obtaining sub-images of dimension 2 pixels by 2 pixels. In other words, for a square IM digital image of size 2nx2n pixels, n partitioning levels are envisaged.

Le module de détermination IB du dispositif de détection 1 détermine pour chaque sous-image obtenue à chaque niveau de partitionnement LEV, i.e. pour chaque nœud de l'arbre, un point remarquable au regard d'un modèle d'attraction prédéterminé ainsi qu'un poids associé à ce point remarquable (étape E20).The determination module IB of the detection device 1 determines for each sub-image obtained at each level of LEV partitioning, ie for each node of the tree, a remarkable point with regard to a predetermined model of attraction as well as a weight associated with this remarkable point (step E20).

Dans le mode de réalisation décrit ici, on envisage un modèle d'attraction de type gravitation universelle. Pour ce modèle, le point remarquable déterminé pour chaque sous-image est le centre de gravité (barycentre des pixels) de cette sous-image. En variante, d'autres modèles d'attraction et points remarquables au regard de ces modèles peuvent être considérés.In the embodiment described here, an attraction model of the universal gravitation type is envisaged. For this model, the remarkable point determined for each sub-image is the center of gravity (centroid of the pixels) of this sub-image. Alternatively, other models of attraction and remarkable points with regard to these models can be considered.

Plus particulièrement, si Pi désigne un pixel d'une sous-image Qj, j=l,...,k=4 résultant du partitionnement d'une image ou sous-image d'un niveau de partitionnement LEV, avec i=l,...,MLEV, où MLEV désigne le nombre de pixels de la sous-image Qj (identique ici pour toutes les sous-images considérées sur un même niveau de partitionnement LEV), le centre de gravité Gj de cette image est obtenu par le module de détermination IB en appliquant l'équation suivante :More particularly, if Pi designates a pixel of a subimage Qj, j = 1,..., K = 4 resulting from the partitioning of an image or sub-image of an LEV partitioning level, with i = l , ..., MLEV, where MLEV denotes the number of pixels of the subimage Qj (identical here for all sub-images considered on the same level of LEV partitioning), the center of gravity Gj of this image is obtained by the IB determination module by applying the following equation:

où Wi désigne le poids (ou la masse) associé au pixel P;. Dans l'exemple de l'image codée en niveaux de gris IM, le poids d'un pixel correspond à la valeur de niveau de gris qui lui est attribuée ou à une valeur normalisée. Selon un autre exemple, pour une image en couleurs par exemple, le poids d'un pixel correspond à sa couleur, codée sur un nombre prédéterminé d'octets.where Wi denotes the weight (or mass) associated with the pixel P ;. In the example of the grayscale image IM, the weight of a pixel corresponds to the grayscale value assigned to it or to a normalized value. According to another example, for a color image for example, the weight of a pixel corresponds to its color, coded on a predetermined number of bytes.

Par ailleurs, lors de l'étape E20, le module de détermination IB associe à chaque centre de gravité G), j=l,...,4, un poids (ou une masse) wGj en appliquant l'équation suivante :Moreover, during step E20, the determination module IB associates with each center of gravity G), j = 1, ..., 4, a weight (or mass) wGj by applying the following equation:

Les centres de gravité obtenus pour chaque niveau de partitionnement LEV=l,...,n et les poids qui leur ont été associés sont mémorisés par le module de détermination IB par exemple dans la mémoire non volatile 5 du dispositif de détection 1. Ils sont représentés à titre illustratif sur la figure 4 associés à leur poids selon la notation w(wGj) ; par exemple sur cette figure la notation G2,W(1032) au niveau LEV1 désigne le centre de gravité G2 de la sous-image Q2 résultant du partitionnement de l'image IM dont le poids est wG2=1032. Autrement dit, à l'issue de l'étape E20, le dispositif de détection 1 dispose en mémoire d'une cartographie des centres de gravité des sous-images résultant du partitionnement récursif de l'image numérique IM. Cette cartographie est donnée par l'ensemble des coordonnées des centres de gravité et les poids qui leur ont été associés. Elle est illustrée schématiquement à la figure 5 suivant un autre mode de représentation que l'arborescence représentée à la figure 4. Sur la figure 5, les éléments ronds représentent les centres de gravité des sous-images.The centers of gravity obtained for each level of partitioning LEV = 1, ..., n and the weights associated with them are stored by the determination module IB, for example in the nonvolatile memory 5 of the detection device 1. are shown for illustrative purposes in FIG. 4 associated with their weight according to the notation w (wGj); for example in this figure, the notation G2, W (1032) at level LEV1 denotes the center of gravity G2 of the subimage Q2 resulting from the partitioning of the image IM whose weight is wG2 = 1032. In other words, at the end of step E20, the detection device 1 has in memory a map of the centers of gravity of the sub-images resulting from the recursive partitioning of the digital image IM. This mapping is given by all the coordinates of the centers of gravity and the weights associated with them. It is illustrated schematically in FIG. 5 according to another mode of representation than the tree represented in FIG. 4. In FIG. 5, the round elements represent the centers of gravity of the sub-images.

Puis, le dispositif de détection 1 génère, via son module de génération IC, une pluie aléatoire sur l'image IM (étape E30). Cette pluie aléatoire de points virtuels (aussi appelés « gouttes ») est générée ici selon une distribution uniforme sur l'image IM, et une densité de points prédéfinie. Cette densité est définie ici par le rapport entre le nombre total Q de points virtuels générés par le module de génération IC et le nombre total de pixel de l'image IM. Par exemple, cette densité est prise égale ici à 20%. Elle résulte plus généralement d'un compromis entre complexité du procédé de détection et précision de la détection que l'on souhaite obtenir de la zone d'intérêt.Then, the detection device 1 generates, via its generation module IC, a random rain on the IM image (step E30). This random rain of virtual dots (also called "drops") is generated here in a uniform distribution on the IM image, and a predefined dot density. This density is defined here by the ratio between the total number Q of virtual points generated by the generation module IC and the total number of pixels of the image IM. For example, this density is taken here equal to 20%. It results more generally from a compromise between the complexity of the detection method and the precision of the detection that one wishes to obtain from the zone of interest.

Pour générer la pluie aléatoire de points virtuels Dq, q=l...,Q, le module de génération IC utilise ici un générateur de nombres pseudo-aléatoires lui permettant de générer les coordonnées des points virtuels Dq, q=l,...,Q.To generate the random rain of virtual points Dq, q = l ..., Q, the generation module IC uses here a pseudorandom number generator enabling it to generate the coordinates of the virtual points Dq, q = 1,. ., Q.

En outre, le module de génération IC associe à chaque point virtuel Dq ainsi généré, un poids wDq, déterminé à partir d'une valeur de consigne prédéfinie WREF. Cette valeur de consigne est représentative du poids des pixels susceptibles d'appartenir à la zone d'intérêt. Elle traduit le critère que le dispositif de détection 1 utilise ici pour délimiter le contour de la zone d'intérêt (i.e. elle fixe le seuil bas des zones de contraste à prendre en compte dans l'image) et est par conséquent discriminante pour le type d'objet (i.e. zone d'intérêt) dont on souhaite déterminer le contour. Une telle valeur de consigne peut être aisément fixée par l'homme du métier, en fonction de sa connaissance du dispositif ayant acquis et fourni l'image IM et de la zone d'intérêt recherchée. Par exemple, si cette zone d'intérêt est une lésion recherchée sur une image IM correspondant à un examen radiographique effectué via un scanner sur un patient, la densité des pixels (i.e. le poids des pixels représenté par un niveau de gris) censés représenter cette lésion sur l'image est connue de l'opérateur du dispositif de scanner ou du médecin apte à interpréter les résultats de l'examen. A titre illustratif, pour une image IM fournie par un scanner, le poids des pixels de l'image représente la densité de la matière. Cette densité va de -1000 UH (pour unités Hounsfield) pour l'air à +1000 UH pour de l'os, -50 UH pour la graisse et 0 UH pour l'eau. En fonction de l'objet dont on cherche à détecter le contour, la valeur de consigne sera fixée à l'une quelconque de ces valeurs traduites en niveaux de gris.Furthermore, the generation module IC associates with each virtual point Dq thus generated, a weight wDq, determined from a predefined setpoint value WREF. This setpoint is representative of the weight of the pixels likely to belong to the area of interest. It translates the criterion that the detection device 1 uses here to delimit the contour of the zone of interest (ie it fixes the low threshold of the contrast zones to be taken into account in the image) and is therefore discriminant for the type object (ie zone of interest) whose contour is to be determined. Such a setpoint value can be easily set by the person skilled in the art, according to his knowledge of the device having acquired and provided the IM image and the desired area of interest. For example, if this area of interest is a lesion sought on an IM image corresponding to a radiographic examination performed via a scanner on a patient, the density of the pixels (ie the weight of the pixels represented by a gray level) supposed to represent this lesion on the image is known to the operator of the scanner device or the physician able to interpret the results of the examination. As an illustration, for an IM image provided by a scanner, the weight of the pixels of the image represents the density of the material. This density ranges from -1000 HU (for Hounsfield units) for air at +1000 HU for bone, -50 HU for fat and 0 HU for water. Depending on the object whose contour is to be detected, the setpoint will be set to any of these values translated into gray levels.

Dans le mode de réalisation décrit ici, le module de génération IC associe à chaque point virtuel généré Dq un poids égal à la valeur de consigne WREF, autrement dit : wDq= WREF pour q=l,...,Q.In the embodiment described here, the generation module IC associates with each generated virtual point Dq a weight equal to the set value WREF, in other words: wDq = WREF for q = 1, ..., Q.

En variante, le module de génération IC peut générer les points virtuels selon une autre distribution qu'une distribution uniforme (ex. distribution gaussienne), et/ou leur attribuer un poids distinct de la valeur de consigne WREF mais déterminé à partir de celle-ci. Par exemple, il peut leur attribuer un poids vérifiant une distribution gaussienne autour de la valeur de consigne WREF.As a variant, the generation module IC can generate the virtual points according to a distribution other than a uniform distribution (eg Gaussian distribution), and / or assign them a weight different from the set value WREF but determined from this one. this. For example, it can assign a weight that satisfies a Gaussian distribution around the WREF setpoint.

On note que si l'on souhaite détecter des zones d'intérêt correspondant à des valeurs de consigne distinctes, le module de génération IC génère une pluie aléatoire pour chacune des zones d'intérêt associée à une valeur de consigne distincte que l'on souhaite détecter.Note that if it is desired to detect zones of interest corresponding to distinct setpoints, the generation module IC generates a random rain for each of the zones of interest associated with a distinct setpoint value that is desired. detect.

Suite à la génération des points virtuels Dq, q=l,...,Q, le dispositif de détection 1 déclenche, via son module de sélection 1D, la « migration » de ces points virtuels vers les zones de l'image IM exerçant sur ces points une attraction maximale (étape E40). Cette migration consiste en le calcul (étape E41) de forces d'attraction exercées sur chaque point virtuel par les différentes sous-images en lesquelles l'image IM a été partitionnée et en la sélection (étape E42) pour chaque point virtuel de la sous-image exerçant la force d'attraction maximale.Following the generation of the virtual points Dq, q = 1, ..., Q, the detection device 1 triggers, via its selection module 1D, the "migration" of these virtual points to the areas of the IM image exerting on these points a maximum attraction (step E40). This migration consists of the calculation (step E41) of the attraction forces exerted on each virtual point by the different sub-images in which the IM image has been partitioned and in the selection (step E42) for each virtual point of the sub-image. -image exerting the maximum force of attraction.

Dans le mode de réalisation décrit ici, afin de modéliser les forces d'attraction exercées par les centres de gravité des sous-images sur les points virtuels, le module de sélection 1D utilise un modèle basé sur la gravitation universelle. Conformément à la gravitation universelle, l'attraction d'un point PI (ex. point virtuel généré par le module de génération IC) par un point P2 ou une zone représentée par un point P2 (ex. centre de gravité des sous-images), est représentée par la force F définie par :In the embodiment described here, in order to model the attraction forces exerted by the sub-image centers of gravity on virtual points, the 1D selection module uses a universal gravitation-based model. According to universal gravitation, the attraction of a PI point (eg virtual point generated by the generation module IC) by a point P2 or an area represented by a point P2 (eg center of gravity of sub-images) , is represented by the force F defined by:

(Eql) où w(Pi) désigne le poids associé au point Pi, i=l,2, et dist(Pl,P2) est la distance entre les points PI et P2 et K est un facteur de correction. La distance dist est par exemple une distance euclidienne.(Eql) where w (Pi) denotes the weight associated with the point Pi, i = 1, 2, and dist (P1, P2) is the distance between the points P1 and P2 and K is a correction factor. The distance dist is for example a Euclidean distance.

Dans le mode de réalisation décrit ici, le facteur de correction tient compte de l'écart entre les poids des points PI et P2 et est défini par :In the embodiment described here, the correction factor takes into account the difference between the weights of the points PI and P2 and is defined by:

(Eq2) où m désigne un entier supérieur à 1. Ce facteur de correction permet de majorer la force d'attraction F exercée sur un point virtuel lorsque le poids du centre de gravité de la sous-image considérée est proche du poids du point virtuel et plus précisément ici de la valeur de consigne WREF modélisée par ce poids. Au contraire le facteur K minore la force d'attraction F lorsque les poids du centre de gravité et du point virtuel sont éloignés, autrement dit ici lorsque le poids du centre de gravité est éloigné de la valeur de consigne WREF. Le nombre m représente l'ordre du facteur de correction K et est modélise un critère de respect de la consigne. Il peut être déterminé empiriquement.(Eq2) where m denotes an integer greater than 1. This correction factor makes it possible to increase the force of attraction F exerted on a virtual point when the weight of the center of gravity of the sub-image considered is close to the weight of the virtual point. and more precisely here the setpoint WREF modeled by this weight. On the contrary the factor K minores the force of attraction F when the weight of the center of gravity and the virtual point are remote, in other words here when the weight of the center of gravity is far from the setpoint value WREF. The number m represents the order of the correction factor K and is modeled a criterion of respect of the setpoint. It can be determined empirically.

Bien entendu, d'autres facteurs de correction remplissant une fonction similaire peuvent être envisagés.Of course, other correction factors fulfilling a similar function can be envisaged.

Afin de minimiser la complexité (en ordre de o(Q2)) des calculs de gravitation entre chaque point virtuel (i.e. chaque goutte) et son voisinage de point dans l'image source, le module de sélection 1D met en oeuvre une évaluation récursive des forces d'attraction F basée sur l'arbre des centres de gravité obtenu à l'étape E10 (modélisée par la flèche de retour entre les étapes E42 et E41 sur la figure 3).In order to minimize the complexity (in order of o (Q2)) of gravitational calculations between each virtual point (ie each drop) and its point neighborhood in the source image, the selection module 1D implements a recursive evaluation of attraction forces F based on the center of gravity tree obtained in step E10 (modeled by the return arrow between steps E42 and E41 in FIG. 3).

Plus particulièrement, à chaque niveau de partitionnement LEV considéré (en partant de LEV=1), le module de sélection 1D sélectionne, pour chaque point virtuel Dq généré, q=l,...,Q, une sous-image résultant du partitionnement en k sous-images d'une image ou d'une sous-image sélectionnée pour ce point Dq au niveau de partitionnement précédent LEV-1. Pour LEV=1, la sous-image sélectionnée au niveau précédent est prise égale à l'image source IM.More particularly, at each level of LEV partitioning considered (starting from LEV = 1), the selection module 1D selects, for each virtual point Dq generated, q = 1, ..., Q, a subimage resulting from partitioning. in k subpictures of an image or subpicture selected for this point Dq at the previous partitioning level LEV-1. For LEV = 1, the subimage selected at the previous level is taken equal to the source image IM.

Pour sélectionner une sous-image au niveau LEV pour un point Dq, le module de sélection 1D calcule, au moyen des équations (Eql) et (Eq2), les forces gravitationnelles F exercées sur ce point Dq par les centres de gravité des k sous-images Q1-Q4 résultant de la partition de la sous-image sélectionnée pour Dq au niveau LEV-1, et sélectionne la sous-image parmi les sous-images Q1-Q4 correspondant à la force gravitationnelle maximale exercée sur le point virtuel Dq. On note que lorsque plusieurs sous-images exercent la même force de gravitation sur un point virtuel Dq, le module de sélection 1D sélectionne une de ces sous-images au hasard.To select a sub-image at the LEV level for a point Dq, the selection module 1D calculates, by means of the equations (Eql) and (Eq2), the gravitational forces F exerted on this point Dq by the centers of gravity of the k's. images Q1-Q4 resulting from the partition of the sub-image selected for Dq LEV-1 level, and selects the sub-image among sub-images Q1-Q4 corresponding to the maximum gravitational force exerted on the virtual point Dq. Note that when several sub-images exert the same gravitational force on a virtual point Dq, the selection module 1D selects one of these sub-images at random.

Le module 1D réalise cette opération pour chaque point virtuel Dq sur une pluralité de niveaux de partitionnement (par exemple 4-5), en partant du niveau de partitionnement LEV=1. En variante, le module 1D peut réaliser cette opération sur tous les niveaux de partitionnement de LEV=1 jusqu'à LEV=n, i.e. jusqu'aux sous-images Q1-Q4 de dimension 1 pixel par 1 pixel.The module 1D performs this operation for each virtual point Dq on a plurality of partitioning levels (for example 4-5), starting from the partitioning level LEV = 1. As a variant, the module 1D can perform this operation on all the partitioning levels of LEV = 1 up to LEV = n, i.e. up to the sub-images Q1-Q4 of dimension 1 pixel by 1 pixel.

La figure 6 illustre un exemple des opérations récursives mises en œuvre par le module de sélection 1D, pour un point virtuel Dl.FIG. 6 illustrates an example of the recursive operations implemented by the selection module 1D, for a virtual point D1.

Sur cet exemple, pour le niveau LEV=1, le module de sélection 1D calcule tout d'abord les forces gravitationnelles exercées sur le point virtuel Dl par les sous-images Ql, Q2, Q3 et Q4 (ou plus précisément par leurs centres de gravité G1-G4) résultant du partitionnement de l'image IM en k=4 sous-images (cadrans ici).In this example, for the level LEV = 1, the selection module 1D first calculates the gravitational forces exerted on the virtual point D1 by the subimages Ql, Q2, Q3 and Q4 (or more precisely by their centers of gravity G1-G4) resulting from the partitioning of the IM image into k = 4 sub-images (dials here).

Puis, parmi les k=4 sous-images Ql, Q2, Q3, Q4, on suppose que Q2 est la sous-image associée à la force gravitationnelle maximale exercée sur Dl. Elle est donc sélectionnée au niveau LEV=1 par le module de sélection 1D (représentée en grisé sur la figure 6).Then, among the k = 4 sub-images Q1, Q2, Q3, Q4, we assume that Q2 is the sub-image associated with the maximum gravitational force exerted on D1. It is therefore selected at level LEV = 1 by the selection module 1D (shown in gray in Figure 6).

Puis, pour le niveau LEV=2, le module de sélection 1D calcule les forces gravitationnelles exercées sur le point Dl par les barycentres des 4 sous-images Q1-Q4 de la sous-image Q2 sélectionnée au niveau LEV=1, et sélectionne la sous-image exerçant la force maximale. On suppose que Q3 correspond à la sous-image sélectionnée (représentée en grisé sur la figure 6).Then, for the LEV level = 2, the selection module 1D calculates the gravitational forces exerted on the point D1 by the barycentres of the four sub-images Q1-Q4 of the selected subimage Q2 at level LEV = 1, and selects the sub-image exerting the maximum force. It is assumed that Q3 corresponds to the selected subimage (shown in gray in Figure 6).

Pour le niveau LEV=3, le module de sélection 1D calcule alors les forces exercées sur le point Dl par les barycentres des 4 sous-images Q1-Q4 de la sous-image Q3 sélectionnée au niveau LEV=2, et sélectionne la sous-image exerçant la force maximale, à savoir Q4 dans l'exemple illustré à la figure 6.For the level LEV = 3, the selection module 1D then calculates the forces exerted on the point D1 by the centers of gravity of the four sub-images Q1-Q4 of the selected subimage Q3 at level LEV = 2, and selects the sub-image image exerting the maximum force, namely Q4 in the example illustrated in Figure 6.

Cette même opération est réitérée sur un nombre de niveaux de partitionnement prédéterminé (ex. 4 ou 5) ou sur l'ensemble des niveaux de partitionnement (n).This same operation is repeated on a number of predetermined partitioning levels (eg 4 or 5) or on all the partitioning levels (n).

Comme mentionné précédemment elle est par ailleurs réalisée pour l'ensemble des points virtuels générés par le module de génération IB à l'étape E30. On note que pour accélérer l'exécution du procédé de détection selon l'invention, les étapes E41 de calcul des forces d'attraction et E42 de sélection d'une sous-image peuvent être conduites en parallèle pour les différents points virtuels considérés. A l'issue de cette opération récursive, le module de sélection 1D mémorise le centre de gravité de la dernière sous-image sélectionnée pour chaque point virtuel dans un fichier F stocké ici dans la mémoire non volatile 5 du dispositif de détection 1 (étape E50).As mentioned above, it is also performed for all the virtual points generated by the generation module IB in step E30. It should be noted that in order to accelerate the execution of the detection method according to the invention, the steps E41 for calculating the attraction forces and E42 for selecting a sub-image can be carried out in parallel for the different virtual points considered. At the end of this recursive operation, the selection module 1D stores the center of gravity of the last subimage selected for each virtual point in a file F stored here in the nonvolatile memory 5 of the detection device 1 (step E50 ).

En variante, il peut stocker l'historique de l'opération de sélection récursive mise en œuvre par le module de sélection 1D, c'est-à-dire qu'il stocke, par exemple dans une liste chaînée, la série de centres de gravité sélectionnés sur les différents niveaux de partitionnement pour chaque point virtuel.As a variant, it can store the history of the recursive selection operation implemented by the selection module 1D, that is to say that it stores, for example in a linked list, the series of data centers. gravity selected on the different levels of partitioning for each virtual point.

Puis le module de détection 1E détecte, à partir de l'ensemble des centres de gravité mémorisés dans le fichier F, la zone d'intérêt recherchée, correspondant à la valeur de consigne VAL (étape E60). Autrement dit, les centres de gravité mémorisés dans le fichier F modélisent les contours de la zone d'intérêt ROI recherchée, sous forme compressée. L'extraction automatique de zones d'intérêt sur une image numérique telle que permise par l'invention peut avoir de nombreuses applications dont la reconnaissance automatique d'objets dans une scène, l'optimisation de la compression d'images vidéo factorisant les zones invariantes de l'image, l'optimisation des fonctions de compression d'image en appliquant de faibles facteurs de compression sur les zones d'intérêt et un facteur plus élevé en dehors de ces dernières.Then the detection module 1E detects, from all the centers of gravity stored in the file F, the desired area of interest, corresponding to the set value VAL (step E60). In other words, the centers of gravity stored in the file F model the contours of the area of interest ROI sought, in compressed form. The automatic extraction of areas of interest on a digital image as permitted by the invention can have many applications including the automatic recognition of objects in a scene, the optimization of the compression of video images factorizing the invariant areas image, optimizing image compression functions by applying low compression factors on areas of interest and a higher factor outside of them.

Dans le mode de réalisation décrit ici, le partitionnement de l'image IM et la sélection des centres de gravité pour détecter la zone d'intérêt sont mis en œuvre de façon récursive afin de réduire la complexité de réalisation de l'invention. Toutefois, cette hypothèse n'est pas limitative et ces étapes peuvent être réalisées de façon directe, sans recourir à des opérations récursives.In the embodiment described here, the partitioning of the IM image and the selection of the centers of gravity to detect the area of interest are implemented recursively to reduce the complexity of embodiment of the invention. However, this assumption is not limiting and these steps can be performed directly, without resorting to recursive operations.

Les figures 7A et 7B illustrent un exemple de mise en œuvre de l'invention.Figures 7A and 7B illustrate an example of implementation of the invention.

Sur cet exemple, l'image IM représentée en figure 7A est une image médicale 512x512 représentant une partie de cartilage humain. Il s'agit d'une image codée sur 256 niveaux de gris. L'image 7B illustre la zone d'intérêt ROI détectée conformément à l'invention. Elle apparaît comme un nuage de points représentant les centres de gravité des sous-images sélectionnées pour chaque point de la pluie aléatoire générée par le module de génération IC du dispositif de détection 1. Les paramètres du procédé de détection considérés pour obtenir la zone d'intêrét ROI sont les suivants : — densité des points virtuels : 10% (distribution uniforme) ; — poids de consigne WREF = 205 ; — 8 niveaux de partitionnement ont été considérés (ce qui correspond à des sous-images de 4 pixels par 4 pixels) ; — m=6 dans le facteur de correction K.In this example, the IM image shown in Figure 7A is a 512x512 medical image representing a portion of human cartilage. This is an image coded on 256 gray levels. The image 7B illustrates the zone of interest ROI detected in accordance with the invention. It appears as a cloud of points representing the centers of gravity of the sub-images selected for each point of the random rain generated by the generation module IC of the detection device 1. The parameters of the detection method considered to obtain the zone of Interest ROI are: - density of virtual points: 10% (uniform distribution); - set weight WREF = 205; - 8 levels of partitioning were considered (which corresponds to sub-images of 4 pixels by 4 pixels); M = 6 in the correction factor K.

Claims

A method for automatically detecting an area of interest (ROI) of a digital image (IM), said method comprising: a step (E10) of partitioning the image into a plurality of sub-images; A step (E20) of determining, for each subimage, a remarkable point of the sub-image with regard to a specific attraction model and a weight associated with this remarkable point; A step (E30) of generation, according to a predefined distribution and density, of a set of virtual points on the image, each virtual point being associated with a weight determined from a predefined target value considered as representative the area of interest; A step (E40) for selecting, for each generated virtual point, the sub-image whose remarkable point exerts a maximum attraction force in accordance with the predetermined attraction model on said virtual point; and a step (E50) of detecting said zone of interest from the remarkable points of the selected sub-images.

2. Detection method according to claim 1, wherein during the partitioning step (E10), the image is recursively partitioned into a predetermined number k of images over a plurality of partitioning levels.

3. Detection method according to claim 2 wherein: the selection step is implemented recursively on all or part of the partitioning levels, a subimage being selected at each level of partitioning considered; and during this recursive selection step, a sub-image is selected on a partitioning level among the sub-images resulting from partitioning into k subpictures of a selected subimage on a previous partitioning level.

4. Detection method according to claim 2 or 3 wherein the number k is equal to 4.

5. Detection method according to any one of claims 1 to 4 wherein: the predetermined attraction model is a universal gravitation model; The remarkable point of the sub-image with regard to the predetermined attraction model is a center of gravity of the sub-image; and said attraction force is a gravitational force exerted by said center of gravity on said virtual point.

6. Detection method according to claim 5 wherein said gravitational force is weighted by a correction factor taking into account a difference between the weight of the center of gravity and the set value.

7. Detection method according to any one of claims 1 to 6 wherein the virtual point distribution considered during the generation step is a uniform distribution on the image.

8. Detection method according to any one of claims 1 to 7 wherein the selection step is implemented in parallel for each of the virtual points of said set of virtual points.

9. Detection method according to any one of claims 1 to 8 wherein said image is a greyscale coded image.

Computer program (PROG) comprising instructions for executing the steps of the detection method according to any one of claims 1 to 9 when said program is executed by a computer.

A computer-readable recording medium on which a computer program is recorded including instructions for performing the steps of the detection method according to any one of claims 1 to 9.

12. A device (1) for automatically detecting an area of interest of a digital image (IM), said device comprising: a partitioning module (IA) configured to partition the image into a plurality of sub-partitions; images; A determination module (IB), configured to determine for each sub-image a remarkable point of the sub-image with regard to a predetermined model of attraction and a weight associated with this remarkable point; A generation module (IC), configured to generate a set of virtual points on the image according to a predefined distribution and density, each virtual point being associated with a weight determined from a predefined target value considered as representative the area of interest; A selection module (1D), configured to select for each virtual point generated the sub-image whose remarkable point exerts a maximum attraction force in accordance with the predetermined attraction model on said virtual point; and a detection module (1E), configured to detect said zone of interest from the remarkable points of the selected sub-images.

13. Detection device (1) according to claim 12 wherein: the partitioning module is configured to recursively partition the image into a predetermined number k of images on a plurality of partitioning levels; and the selection module is configured to recursively select a sub-image on all or part of said plurality of partitioning levels, a sub-image being selected by the selection module on a partitioning level among the sub-images resulting from the partitioning into k subpictures of a sub-image selected by said selection module on a previous partitioning level.