FR 3024264 A1 20160129 FR 1457099 A 20140723 3024264 PROCEDE, DISPOSITIF ET PRODUIT PROGRAMME D'ORDINATEUR DE DISCRETISATION D'UN ESPACE 3D Domaine de l'invention L'invention porte sur un procédé, un dispositif et un produit programme d'ordinateur pour la discrétisation d'un espace 3D à partir de vues 2D d'un objet. Etat de la Technique La reconstruction 3D est un problème dit de type inverse pour lequel un volume 3D est estimé à partir d'un ensemble de vues 2D d'un objet étudié. Classiquement, les méthodes de reconstruction 3D sont basées sur une représentation du volume de reconstruction en une grille régulière d'éléments cubiques appelés voxels. Le principal désavantage d'une telle représentation réside dans des coûts calculatoires conséquents même si il peut être recouru à du calcul parallélisé. En effet, pour obtenir une bonne représentation des contours des objets il est nécessaire d'échantillonner finement la grille voxélisée, ce qui conduit par ailleurs à sur-échantillonner des zones pourtant homogènes du volume. De plus, le coût en termes de mémoire de stockage des données 3D est d'autant plus élevé que l'échantillonnage du volume est fin. Dans le cadre plus spécifique de la tomographie, l'exploitation d'un 25 objet reconstruit se limite à sa visualisation pseudo 3D (par coupes 2D). L'accès à des informations plus pertinentes permettant de caractériser 2 302 42 64 l'objet de façon quantitative passe nécessairement par une étape de post-traitement comme de la segmentation. Il existe quelques méthodes de reconstruction basées sur une discrétisation adaptée à l'objet, comme par exemple, celles décrites dans 5 les articles suivants : - Jovan G. Brankov Yongyi Yang, M. N., "Tomographic Image Reconstruction Based on a Content-Adaptive Mesh Moder, IEEE Transactions on Medical Imaging, 2004, 202-212; - Arkadiusz Sitek, Ronald H. Huesman, G. T. G., "Tomographic 10 Reconstruction Using an Adaptive Tetrahedral Mesh Defined by a Point Cloud", IEEE Transactions on Medical Imaging, 2006, 25; - Michele A. Quinto, Dominique Houzet and Fanny Buyens, "Adaptive Triangular Mesh Image Representation for X-ray Tomographic Reconstruction", EEE Nuclear Science Symposium, Medical Imaging 15 Conference, Anaheim, Californie : États-Unis (2012) L'article de Brankov présente une méthode de reconstruction SPECT 2D sur une grille adaptative, générée par triangulation de Delaunay, à partir de projections 1D de l'objet à reconstruire en coupe. Le 20 maillage de reconstruction est obtenu à partir de noeuds placés par une méthode dite « content-adaptive mesh model » (CAMM). Au préalable, l'approche nécessite une étape de reconstruction 2D pixélisée basse résolution de la coupe par méthode dite « Filtered Back Projection » (FBP) qui requiert un grand nombre de projections. Même si une extension 3D de cette méthode pourrait être envisagée, permettant de diminuer l'espace mémoire de stockage de la reconstruction, les limitations de reconstruction liées au temps de calcul et au nombre de projections demeurent. 3 3024264 L'article de Sitek décrit une méthode de reconstruction SPECT 3D sur une grille tétraédrique. Le procédé consiste à raffiner une grille initialement régulière par alternance de reconstructions itératives-mises à jour de la grille (par ajout de noeuds) jusqu'à convergence quand un 5 nombre maximum de noeuds est atteint. Le nombre de vues utilisées peut être diminué mais les limites en termes de temps de calcul demeurent. Par ailleurs, l'obtention de la grille se base sur des critères issus d'une reconstruction. L'article de Quinto propose une méthode de reconstruction 3D sur 10 grille adaptée, avec mailles tétraédriques. La méthode repose sur une initialisation d'une grille 3D quelconque puis procède par alternance de reconstructions itératives-segmentation par ensemble de niveaux (ou level set en anglais) sur le volume reconstruit pour la mise à jour de la grille 3D. L'information mise à jour est de type contour ce qui permet 15 d'adapter rapidement la grille à son contenu et de réduire les temps de calcul. L'information contour émanant des reconstructions 3D, un premier problème associé est que l'accès à cette information nécessite une alternance d'étapes de reconstruction / segmentation qui sont coûteuses en termes de temps de calcul. Un second problème vient du fait que 20 l'information contour repose sur les données reconstruites et l'expose donc aux artéfacts associés. Il existe alors le besoin d'une solution qui palie aux inconvénients des approches connues. La présente invention répond à ce besoin. 25 Résumé de l'invention Un objet de la présente invention est de proposer une solution avantageuse en termes de réduction du temps de calcul grâce à une méthode d'échantillonnage d'un volume 3D de reconstruction adapté à son contenu en utilisant un échantillonnage irrégulier. La méthode est 4 3024264 aussi avantageuse en termes de stockage mémoire de par la discrétisation proposée. L'invention tire avantage de l'information structurelle qui est présente dans les vues 2D d'un objet à reconstruire pour réaliser une 5 initialisation adaptée d'une grille 3D. Grâce à l'échantillonnage réalisé (nuage de points), la méthode permet d'obtenir directement un modèle volumique ou surfacique 3D d'un objet sans aucune reconstruction volumique. La méthode utilise les vues 2D de l'objet à reconstruire pour placer un nuage de points spécifique à 10 sa complexité dans l'espace de reconstruction 3D par méthode statistique dans le contexte d'une géométrie d'acquisition connue. Cette méthode comprend deux étapes. Une première étape de tests statistiques est appliquée sur les données de contours 2D rétro-projetées en 3D pour fusionner l'information en un nuage de points 3D. Dans la seconde étape, 15 une grille irrégulière d'élément structurant quelconque est construite à partir du nuage de points, discrétisant l'objet en un faible nombre de cellules. Le champ scalaire associé à l'objet est estimé à l'aide d'un algorithme de reconstruction adapté à l'élément structurant de la grille. Cette discrétisation 3D permet de réduire considérablement d'une part la 20 taille du fichier contenant l'objet reconstruit et d'autre part le temps de calcul inhérent à l'algorithmique de reconstruction. Avantageusement, l'invention s'implémentera dans le domaine industriel : reverse engineering, données pour imprimantes 3D, contrôles de pièces manufacturées (CND) avec un modèle CAO d'origine, création 25 de modèle CAO d'objets spécifiques pour des codes de calcul de type éléments finis (calculs mécaniques, fluidiques, etc). Elle trouvera aussi avantage dans le domaine médical pour l'aide au diagnostic spécifique patient et plus particulièrement pour le suivi de pathologies orthopédiques, la planification de chirurgie osseuse, les applications 5 3024264 angiographiques, et également pour le dossier patient puisque cette représentation 3D est peu couteuse en stockage mémoire. Pour obtenir les résultats recherchés, un procédé mis en oeuvre par ordinateur, un dispositif comprenant des moyens pour mettre en 5 oeuvre le procédé, et un produit programme d'ordinateur sont proposés. En particulier, un procédé de discrétisation d'un espace 3D à partir de vues 2D d'un objet, comprend les étapes de : - générer pour chaque vue 2D une image de bords labellisés, ladite image étant représentative des bords contenus dans ladite chaque vue ; 10 - fusionner l'ensemble des images de bords labellisés en un nuage de points 3D ; et - générer une grille irrégulière 3D à partir du nuage de points 3D, ladite grille constituant une discrétisation de l'espace 3D adaptée audit objet. 15 Dans un mode de réalisation, la grille irrégulière 3D est volumique, et le procédé comprend de plus après l'étape de génération de la grille volumique, une étape de reconstruction tomographique de l'objet à l'aide d'un algorithme itératif. Dans une implémentation, l'étape de génération de la grille irrégulière 3D consiste en une tétraédrisation. Dans une 20 implémentation préférentielle, la tétraédrisation est de type Delaunay contraint. Dans un autre mode de réalisation, la grille irrégulière 3D est surfacique constituant une représentation surfacique de l'objet. Dans une implémentation préférentielle, l'étape de génération 25 d'images de bords labellisés est réalisée avec un détecteur de bords de Canny. 6 3024264 Dans un mode de réalisation, l'étape de fusion des images de bords labellisés comprend une étape de rétroprojection desdites images de bords en valeurs rétroprojetées dans un espace de reconstruction échantillonné sur une grille régulière de voxels. Dans une implémentation, 5 le procédé comprend de plus une étape de modélisation des valeurs rétroprojetées, par une loi de Poisson tronquée ou par une loi de Poisson. Selon un mode de réalisation, le procédé comprend une étape de filtrage des valeurs rétroprojetées qui sont supérieures à un seuil obtenu par l'étape de modélisation. Dans une implémentation, la grille irrégulière 10 3D est générée à partir des valeurs rétroprojetées filtrées. Avantageusement, dans une implémentation préférentielle, le nombre de vues 2D de l'objet est de l'ordre d'une trentaine de vues. L'invention couvre aussi un dispositif de discrétisation d'un espace 3D à partir de vues 2D d'un objet qui comprend des moyens pour mettre 15 en oeuvre les étapes du procédé. L'invention peut opérer sous la forme d'un produit programme d'ordinateur qui comprend des instructions de code permettant d'effectuer les étapes du procédé revendiqué lorsque le programme est exécuté sur un ordinateur. 20 Description des figures Différents aspects et avantages de l'invention vont apparaitre en appui de la description d'un mode préféré d'implémentation de l'invention mais non limitatif, avec référence aux figures ci-dessous : 25 La figure 1 illustre un enchainement des étapes du procédé de discrétisation dans un mode de réalisation de l'invention ; 7 3024264 Les figures 2a et 2b illustrent des exemples de vue 2D d'un objet à reconstruire selon le procédé de l'invention ; Les figures 3a et 3b illustrent des exemples d'images de bords obtenues pour les vues des figures 2a et 2b selon une mise en oeuvre du procédé 5 de l'invention ; Les figures 4a à 4c illustrent un exemple de nuage de points sous différents angles, obtenu selon une mise en oeuvre du procédé de l'invention ; Les figures 5a à 5d illustrent un exemple de grille irrégulière 3D sous 10 différentes coupes, obtenue selon une mise en oeuvre du procédé de l'invention ; Les figures 6a à 6c illustrent sous différentes coupes, un exemple de reconstruction tomographique 3D de l'objet des figures 2a et 2b selon une mise en oeuvre du procédé de l'invention ; 15 La figure 7 illustre un exemple de reconstruction surfacique selon une mise en oeuvre du procédé de l'invention. Description détaillée de l'invention 20 D'une manière générale, la présente invention a pour but de réduire la taille réservée au stockage d'un volume 3D sans affecter son contenu. Cet objectif nécessite de n'associer qu'un nombre faible de cellules de représentation 3D aux zones homogènes. Pour adapter au mieux la discrétisation à un objet imagé, il faut positionner les bords des 25 cellules uniquement sur les contours des zones homogènes du volume. 8 3024264 Le principe de l'invention est de considérer que l'information structurelle 3D, c'est-à-dire l'information de contours ou de bords, est présente de façon incomplète dans les données brutes 2D, et s'appuyant sur le fait que tout bord d'une vue 2D correspond à une projection 5 géométrique d'un contour d'un volume 3D, l'invention permet de localiser l'information contour dans les vues 2D, puis de la fusionner pour placer les noeuds d'une grille adaptée sur les contours 3D de l'objet étudié. Ainsi l'échantillonnage 3D obtenu s'affranchit de toute étape de reconstruction. Les gains en termes de temps de calcul sont conséquents. 10 Dans la suite de la description, le procédé de discrétisation est illustré en références aux figures 2 à 7 pour une reconstruction 3D issue de la tomographie par rayons X. Référence est d'abord faite à la figure 1 qui montre un enchainement des étapes du procédé de discrétisation dans un mode de 15 réalisation de l'invention. Le procédé débute après la réception (102) d'un nombre 'n' de vues 2D d'un objet. Les vues 2D peuvent être acquises depuis un système physique ou par simulation à l'aide d'un logiciel adéquat. Avantageusement, la présente invention permet la reconstruction 3D d'un objet à partir d'un faible nombre de vues 2D 20 initiales. Ainsi, dans un mode préférentiel, une trentaine de vues 2D sont suffisantes pour opérer le procédé de l'invention. Les figures 2a et 2b illustrent deux vues 2D d'un objet « os ». Comme énoncé précédemment, le principe de l'invention est de caractériser l'information structurelle d'intérêt sachant que la structure 25 d'un volume 3D à reconstruire est portée par l'ensemble des interfaces entre matériaux. Or, les discontinuités 3D caractérisant la structure d'un objet sont présentes dans une version dégradée - 2D - sur l'ensemble des vues 2D de ce dernier. Par conséquent, à partir des discontinuités présentes dans l'ensemble des vues prises depuis différents angles il est 9 302 42 64 possible de retrouver la distribution 3D des points de l'espace dont elles sont issues. Pour obtenir l'information structurelle recherchée, les 'n' vues 2D sont filtrées par un détecteur de bords. Ainsi, les bords sont détectés et 5 labellisés dans chaque vue 2D, et une image de bords labellisés est générée (104) pour chaque vue. Les figures 3a et 3b illustrent des images de bords obtenues à partir des vues des figures 2a et 2b. Dans un mode de réalisation, l'étape de détection de bords est réalisée avec un détecteur de bords de Canny. L'homme de l'art trouvera 10 les détails de ce type de détecteur, par exemple à la référence « A Computational Approach to Edge Detection, » Canny J., IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 6. Quand toutes les 'n' vues ont été filtrées, le procédé passe à une étape suivante (106) qui consiste à fusionner en 3D les 'n' images de 15 bords pour obtenir un nuage de points 3D. Les figures 4a à 4c illustrent un nuage de point sous différents angles, obtenu par la fusion des images des figures 3a et 3b. Dans une implémentation préférentielle, la fusion consiste en une rétroprojection simple des images de bords dans un espace de 20 reconstruction, échantillonné sur une grille régulière de voxels. Chaque voxel contient alors le décompte du nombre de bords qui lui est associé par projection dans les vues 2D filtrées, et les fortes valeurs correspondent aux points les plus représentatifs des contours 3D. Avantageusement, pour échantillonner l'objet étudié de façon 25 adaptée, les points les plus représentatifs sont sélectionnés par tests statistiques, et cela requiert de connaître la distribution suivie par les valeurs du volume. La modélisation classiquement utilisée pour caractériser de tels phénomènes de comptage est la loi de Poisson. Cependant, en fusionnant des images de bords, de nombreux voxels de 10 3024264 l'espace de reconstruction possèdent une valeur nulle. Ces voxels sont écartés de l'analyse. Ceci conduit à faire la modélisation sur les voxels restants par une loi de Poisson tronquée. L'estimation du paramètre ô caractéristique de cette loi est faite à 5 l'aide de l'estimateur de Plackett (R.F Tate, R.L. Goen, Minimum variance unbiaised estimation for the truncated Poisson distribution, The annals of Mathematical Statistics, 1958) à partir de l'observation des valeurs Xi, = 1, ...,n des voxels comme suit : T = -n(1 - T) où T = 0X1 10 et N1 = (riv=0 XL IXi = 1). Une fois le paramètre de la loi de Poisson tronquée estimé, cette loi est utilisée pour réaliser le seuillage des valeurs fusionnées à l'aide d'un test statistique permettant de sélectionner les grandes valeurs du comptage qui sont considérées comme des voxels représentatifs de bord 15 3D. Dans un mode de réalisation, les hypothèses suivantes sont prises pour le test statistique : Ho : Xi n'est pas une valeur extrème pour la loi de Poisson tronquée en 0 H1 : Xi est valeur extrème pour la loi de Poisson tronquée en 0 On décide de Hl si la valeur du voxel dépasse un seuil is' choisi, selon la théorie des tests, par le quantile Q de la loi de Poisson tronquée, 20 tel que : Qtronquée(1 a) 11 3024264 où a est le niveau du test utilisé généralement choisi dans la gamme [0,05 - 0,001] suivant la permissivité souhaitée de la sélection. Pour déterminer le quantile 0 -t. tronquée d'ordre 1 - a, de manière préférentielle on utilise la méthode de Gilchrist (Gilchrist, 5 Warren. Statistical modelling with quantile functions. CRC Press, 2000, p.149) qui approxime ce quantile par celui de la loi de Poisson de paramètre À pour un ordre (1 - a') comme suit : (1- a') = F(1) - (1- a)(1- F(1)) où F correspond à la fonction de répartition de la loi de Poisson de paramètre À. Ce paramètre est calculé en utilisant l'estimation empirique 10 de la moyenne des données (estimation optimale au sens du maximum de vraisemblance). La valeur de seuillage a ainsi pour valeur : s = Q(1- a') Pour chaque voxel de la grille portant une valeur supérieure au seuil considéré, un noeud est placé dans un repère cartésien. La grille 15 irrégulière est bâtie sur le nuage de points ainsi obtenu. Dans le cas particulier d'un faible nombre de vues 2D acquises par un système en rotation autour d'un axe unique, les bords situés dans des plans aux deux directions perpendiculaires à l'axe de rotation provoquent une forte variation de la distribution d'un plan à l'autre le long de l'axe de 20 rotation. Ce phénomène lié à la rétroprojection est pris en charge en traitant chaque plan tour à tour et en incluant la possibilité de modéliser les valeurs de comptage par une loi de Poisson. Ceci conduit à déterminer sur chaque plan du volume 3D la nature de la loi de Poisson (standard ou tronquée), et le paramètre associé. 12 3024264 La loi est déterminée par un test de sous-dispersion proposé par Mizere et al (Mizere D., Kokonendji C.C., Dossou-Gbété S., Quelques alternatives de la loi de Poisson contre des alternatives générales basées sur l'indice de dispersion de Fisher, Rev. Statistique Appliquée, LIV(4), 5 61-84, 2006). La dispersion d'une distribution est définie comme le ratio entre la variance et la moyenne de cette dernière. Les hypothèses du test sont les suivantes : Ho : Xi suit une loi de Poisson H1 : Xi suit une loi sous dispersée (Poisson tronquée ici) Dans le cadre de ce test, seules les valeurs rétro-projetées Xi non 10 nulles sont considérées. La statistique de test TF s'exprime par : S2 TF = n Xn où n correspond au cardinal de l'échantillon du plan considéré et les quantités X, et .S'iî sont calculés depuis les échantillons Xi comme suit : SZ n 15 13 3024264 En introduisant le quantile d'ordre a du Khi-deux à n-1 degrés de liberté A.2_,,,' , l'hypothèse Ho est rejetée si la statistique de test vérifie l'équation suivante : TF REVENDICATIONS1. Un procédé, mis en oeuvre par ordinateur, de discrétisation d'un espace 3D à partir de vues 2D d'un objet, le procédé comprenant les étapes de : générer pour chaque vue 2D une image de bords labellisés, chaque image étant représentative des bords contenus dans ladite chaque vue ; fusionner l'ensemble desdites images de bords labellisés en un nuage de points 3D ; et générer une grille irrégulière 3D à partir du nuage de points 3D, ladite grille constituant une discrétisation de l'espace 3D adaptée audit objet. 2. Le procédé selon la revendication 1, dans lequel la grille irrégulière 3D est volumique, et le procédé comprenant de plus après l'étape de génération de ladite grille volumique, une étape de reconstruction tomographique dudit objet à l'aide d'un algorithme itératif. 3. Le procédé selon les revendications 1 ou 2 dans lequel l'étape de génération de la grille irrégulière 3D consiste en une tétraédrisation. 4. Le procédé selon la revendication 3 dans lequel la tétraédrisation est de type Delaunay contraint. 17 3024264 5. Le procédé selon la revendication 1 dans lequel la grille irrégulière 3D est surfacique constituant une représentation surfacique de l'objet. 5 6. Le procédé selon l'une quelconque des revendications 1 à 5 dans lequel l'étape de génération d'images de bords labellisés est réalisée avec un détecteur de bords de Canny. 7. Le procédé selon l'une quelconque des revendications 1 à 6 10 dans lequel l'étape de fusion des images de bords labellisés comprend une étape de rétroprojection desdites images de bords en valeurs rétroprojetées dans un espace de reconstruction échantillonné sur une grille régulière de voxels. 15 8. Le procédé selon la revendication 7 comprenant de plus une étape de modélisation des valeurs rétroprojetées, par une loi de Poisson tronquée ou par une loi de Poisson. 9. Le procédé selon la revendication 8 comprenant de plus une 20 étape de filtrage des valeurs rétroprojetées qui sont supérieures à un seuil obtenu par l'étape de modélisation. 10. Le procédé selon la revendication 9 dans lequel la grille irrégulière 3D est générée à partir des valeurs rétroprojetées 25 filtrées. 11. Le procédé selon l'une quelconque des revendications 1 à 10 dans lequel le nombre de vues 2D est de l'ordre d'une trentaine de vues. 12. Un dispositif de discrétisation d'un espace 3D à partir de vues 2D d'un objet, le dispositif comprenant des moyens pour mettre en 18 3024264 oeuvre les étapes du procédé selon l'une quelconque des revendications 1 à 11. 13. Un produit programme d'ordinateur, ledit programme d'ordinateur comprenant des instructions de code permettant d'effectuer les étapes du procédé selon l'une quelconque des revendications 1 à 11, lorsque ledit programme est exécuté sur un ordinateur.