# Optimisation de l'algorithmé PatchMatch pour la segmentation de structures anatomiques

Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis, D. Louis Collins, Pierrick Coupé

Coupé

► To cite this version:

Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis, D. Louis Collins, Pierrick Coupé. Optimisation de l'algorithmé PatchMatch pour la segmentation de structures anatomiques. Colloque du Groupe de Recherche et d'Etudes de Traitement du Signal et des Images (GRETSI'15), Sep 2015, Lyon, France. hal-01170197

HAL Id: hal-01170197

https://hal.science/hal-01170197v1

Submitted on 1 Jul 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC0 1.0 - Universal - International License
# Optimisation de l'algorithmme PatchMatch pour la segmentation de structures anatomiques

Rémi GIRAUD<sup>1,2,3</sup>, Vinh-Thong TA<sup>1,3</sup>, Nicolas PAPADAKIS<sup>2</sup>, D. Louis COLLINS<sup>4</sup>, Pierrick COUPÉ<sup>1</sup>

<sup>1</sup>Univ. Bordeaux, LaBRI, CNRS, UMR 5800, PICTURA, F-33400 Talence, France.

<sup>2</sup>Univ. Bordeaux, IMB, CNRS, UMR 5251, F-33400 Talence, France.

<sup>3</sup>Bordeaux INP, LaBRI, CNRS, UMR 5800, PICTURA, F-33400 Talence, France.

<sup>4</sup>McConnell Brain Imaging Centre, Montreal Neurological Institute, McGill University, Montreal, Canada.

remi.giraud@labri.fr, vinh-thong.ta@labri.fr, nicolas.papadakis@math.u-bordeaux1.fr, louis.collins@mcgill.ca, pierrick.coupe@labri.fr

**Résumé** – Les méthodes de segmentation automatique sont des outils importants pour l’analyse des images par résonance magnétique. Dans ce travail, nous introduisons une nouvelle méthode basée sur l’utilisation de patchs pour effectuer une segmentation de structures anatomiques. La méthode proposée est basée sur l’algorithme PatchMatch, optimisé pour la fusion d’étiquettes. Elle est nommée OPAL (pour Optimized PAtchMatch Label fusion), et fournit une précision de segmentation très compétitive en quasi temps-réel (moins d’1s de traitement par sujet).

**Abstract** – Automatic segmentation methods are important tools for analysis of magnetic resonance images. In this paper, we introduce a new patch-based method using the PatchMatch algorithm to perform the segmentation of anatomical structures. Based on an Optimized PAtchMatch Label fusion (OPAL) strategy, the proposed method provides very competitive segmentation accuracy in near real-time (less than 1s per subject).

# 1 Introduction

La segmentation automatique est un outil décisif lors de l'étude quantitative des images par résonance magnétique (IRM). Elle permet notamment le suivi de pathologies neurodégénératives comme la maladie d'Alzheimer. Au cours des dernières années, plusieurs méthodes de segmentation de structures cérébrales ont été proposées. Celles-ci consistent à affecter une étiquette particulière à chaque voxel suivant la structure à laquelle il appartient.

Pour aborder ce problème, des méthodes basées sur l'utilisation d'un unique sujet pris comme modèle ont été proposées [3]. Ces méthodes impliquent un recalage non-linéaire vers le sujet à segmenter. Ensuite, des techniques de déformation multi-modèles, basées sur la fusion de plusieurs sujets d'entraînement manuellement étiquetés ont été introduites [7, 8, 4]. Ces approches multi-modèles, bien que performantes en termes de précision de la segmentation, sont obtenues avec un temps de calcul important (jusqu'à plusieurs heures).

Récemment, une méthode de fusion d’étiquettes PBL (pour Patch-Based Label fusion) [5], basée sur l’utilisation de patchs au sein d’une stratégie non-locale, a été proposée. Cette méthode trouve, pour tous les patchs du sujet, des correspondances dans la bibliothèque de modèles. Un poids est alors assigné à l’étiquette du patch modèle en fonction de sa similarité avec le patch du sujet à segmenter. Les étiquettes sont ensuite fusion-

nées selon leur poids pour générer la segmentation finale. Un des avantages de la méthode PBL est qu’elle requiert uniquement un recalage linéaire des images. La recherche non-locale permet alors de mieux gérer la variabilité inter-sujets et de compenser les imprécisions de recalage. Cette méthode obtient des résultats très compétitifs en seulement quelques minutes.

Beaucoup d'améliorations ont été proposées [11, 6, 12, 13], mais PBL souffre toujours de plusieurs limitations. Premièrement, la recherche de patchs similaires est coûteuse, même avec une pré-sélection de modèles [5], de patchs [5, 11] ou avec une stratégie multi-échelle [6]. Deuxièmement, la pré-sélection des modèles peut empêcher de trouver les patchs les plus similaires situés dans des sujets modèles globalement très différents, et retirés lors de la pré-sélection. Enlever ces modèles *a priori* peut donc mener à des résultats sous-optimaux. Troisièmement, dans la méthode PBL, un poids est assigné à un grand nombre de patchs, parmi lesquels se trouvent des patchs très peu similaires avec le patch courant du sujet. Ainsi, des ressources sont dédiées inutilement à l'estimation de poids négligeables qui peuvent diminuer la précision de la segmentation [12]. Des méthodes parcimonieuses peuvent limiter cet aspect au détriment d'un temps de calcul important [12, 13]. Toutes ces limitations diminuent la précision des segmentations et rendent les implémentations actuelles très coûteuses.

Dans ce travail, nous introduisons une nouvelle méthode pour répondre à ces limitations. La méthode proposée est nom-
mée OPAL (pour Optimized PatchMatch Label fusion), et est basée sur l'algorithme PatchMatch (PM), optimisé pour la fusion d'étiquettes et la segmentation de structures anatomiques.

Comparée aux précédentes méthodes de la littérature, OPAL produit des résultats en quasi temps-réel. De plus, OPAL ne requiert pas de pré-sélection, donc la recherche de patchs similaires s'effectue sur toute la bibliothèque de modèles, et la segmentation est ainsi plus précise. Enfin, en ne prenant en compte qu'un faible nombre de patchs similaires, OPAL limite l'introduction de patchs dissimilaires durant l'étape de segmentation.

Les principales contributions de ce travail sont : (1) L'adaptation de l'algorithme PM à la fusion d'étiquettes pour la segmentation de structures anatomiques sur des IRM 3D. (2) L'introduction de techniques d'accélération de PM comme une initialisation contrainte, une parallélisation de l'algorithme et une optimisation du calcul de distance. (3) La validation d'OPAL sur la segmentation de l'hippocampe, et la comparaison avec plusieurs méthodes de l'état de l'art en termes de temps de calcul et de précision de la segmentation.

# 2 La méthode OPAL

## 2.1 L'algorithme PatchMatch

PM [1] est une approche rapide et efficace permettant de calculer des correspondances de patchs, ou plus proches voisins approximés ANN (pour Approximate Nearest Neighbor), entre deux images 2D (notées A et B). Le cœur de la méthode repose sur le fait que les bonnes correspondances peuvent être propagées aux patchs adjacents au sein d'une image. La méthode est basée sur trois étapes : une initialisation, une propagation et une recherche aléatoire. L'initialisation consiste à affecter à chaque patch de l'image A, un patch aléatoire de l'image B. L'étape de propagation tente d'améliorer ces correspondances en se basant sur l'observation que si un patch situé à $p = (x, y) \in A$ correspond bien à un patch situé à $q = (x', y') \in B$, alors le patch adjacent de $p$ devrait bien correspondre avec le patch adjacent de $q$. L'étape de recherche aléatoire consiste à échantillonner aléatoirement autour du meilleur ANN courant. Cette dernière étape permet notamment de pouvoir sortir d'une zone de minimum local. Ces deux dernières étapes sont effectuées itérativement afin d'améliorer les correspondances entre patchs.

## 2.2 OPAL

Contrairement à [1], où deux images 2D sont considérées, OPAL trouve des correspondances entre un sujet 3D $S$ et une bibliothèque de $n$ sujets 3D considérés comme modèles $L = \{M_1, ..., M_n\}$. La distance utilisée est une somme des différences au carré (SSD). Un avantage d'OPAL (grâce à PM), est que sa complexité ne dépend que de la taille de l'image $S$ et pas de la taille de la bibliothèque $L$. Ce fait important permet à OPAL de considérer l'entière bibliothèque des images de $L$ sans étape de pré-sélection, et ce, à complexité constante. De plus, pour chaque patch dans $S$, OPAL ne calcule pas qu'une

<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Principales étapes d'OPAL. (a) Initialisation contrainte, (b) et (d) étapes de propagation pour l'itération #1 et #2, (c) et (e) recherches aléatoires contraintes pour l'itération #1 et #2, et (f) PM multiples.</figcaption></figure>

correspondance comme dans [1], mais $k$-ANN dans $L$. La Figure 1 montre une vue schématique de l'algorithme. Pour faciliter la représentation, seuls 3 modèles de la bibliothèque sont représentés et les sujets 3D sont affichés en 2D.

**Initialisation contrainte.** L'extension naturelle de l'étape d'initialisation de [1] au cas 3D serait d'assigner chaque patch situé à $(x, y, z) \in S$, à un patch aléatoire situé à $\{(x', y', z')\}, t\} \text{ où } t \in \{1, ..., n\}$ est l'indice du modèle $M_t$ dans la bibliothèque $L$. Cependant, nous pouvons tirer profit du recalage linéaire de tous les volumes IRM dans $L$. Nous proposons donc de contraindre la position initiale aléatoire à l'intérieur d'une fenêtre de recherche de taille fixe, centrée autour de la position courante $(x, y, z)$. L'indice $t$ du modèle est ensuite assigné aléatoirement pour chaque patch de $S$. La Figure 1(a) illustre cette étape où pour trois patchs dans $S$, la fenêtre d'initialisation aléatoire est dessinée en pointillés dans les sujets modèles. Après l'initialisation, les étapes de propagation et de recherche aléatoire sont effectuées itérativement.

**Propagation et calcul rapide de distance.** Pour chaque patch situé à $(x, y, z) \in S$, nous testons si l'ANN décalé de ses voisins adjacents précédemment traités, et situés à $(x \pm 1, y, z)$, $(x, y \pm 1, z)$ et $(x, y, z \pm 1)$ fournit une meilleure correspondance. Trois voisins sont considérés selon le sens de parcours de $S$, qui est inversé à chaque itération. Les Figures 1(b) et 1(d) illustrent cette étape, où les lignes pointillées bleues indiquent
les correspondances décalées des voisins dans L.

Dans cet exemple, la meilleure correspondance pour le patch bleu se déplace du modèle $M_1$ à $M_2$ (itération #1) puis de $M_2$ à $M_1$ (itération #2). La propagation est une étape clé, puisqu'elle permet à une correspondance de se déplacer parmi tous les modèles de la bibliothèque.

Nous proposons enfin une accélération basée sur le fait que la distance entre un patch adjacent et son propre ANN a été calculée, et est donc connue. Avec des fenêtres glissantes, nous utilisons le recouvrement entre patchs successifs afin de ne pas recalculer la distance sur les voxels qui se superposent.

**Recherche aléatoire contrainte.** OPAL, contrairement à [1], gère une bibliothèque d'images. Pour s'assurer de la cohérence spatiale, la recherche aléatoire n'est effectuée que sur le modèle courant contenant la meilleure correspondance (c.-à-d., $t$ est fixé) et l'échantillonnage est réalisé sur $(x', y', z') \in M_t$ à l'intérieur d'une fenêtre décroissante. Les Figures 1(c) et 1(e) montrent des recherches aléatoires où les fenêtres de taille décroissante sont représentées en lignes bleues pointillées.

**PM multiples et calcul parallélisé.** Tandis que dans [1], seule la meilleure correspondance est estimée, OPAL calcule $k$-ANN dans L. Une extension de PM au cas $k$-ANN a été proposée dans [2]. Une pile des meilleurs patchs visités est alors construite pour obtenir les $k$-ANN. Cependant, paralléliser cette approche nécessite un découpage en plusieurs parties de l'image $S$, entraînant des problèmes de superposition de patchs entre processus. Par conséquent, dans OPAL, nous basons la recherche des $k$-ANN sur $k$-PM indépendants, chacun géré en parallèle par un processus dédié. La Figure 1(f) illustre le résultat obtenu pour plusieurs PM où $k = 3$ et chaque PM$_{i}$=$\{1,2,3\}$ désigne un PM indépendant.

**Fusion d'étiquettes.** À la fin du processus, $k$-ANN sont estimés pour chaque patch de $S$. Ainsi, la position et la distance entre les patchs de $S$ et leur $k$-ANN sont connues. Nous utilisons donc la segmentation par fusion d'étiquettes de la méthode PBL originale [5] pour obtenir la segmentation finale du sujet.

Cependant, dans OPAL, seuls les $k$ patchs les plus similaires sont utilisés, ce qui limite les erreurs de segmentation, et toute la bibliothèque est considérée, ce qui augmente la précision de la segmentation. Enfin, pour encore améliorer la segmentation, la fusion des étiquettes est effectuée sur la totalité du patch comme dans [11, 13], et pas uniquement sur le voxel central.

# 3 Expérimentations et résultats

## 3.1 Validation

**Base de données.** La méthode a été évaluée sur la base de données ICBM (International Consortium for Brain Mapping), qui contient 80 IRM d'individus jeunes et sains, ainsi que des segmentations manuelles réalisées selon le protocole de Pruessner [10]. Les paramètres d'acquisition sont donnés dans [5]. Les

coefficients de fiabilité intra (5 répétitions) et inter-classe (4 experts) ont respectivement été estimés à 92% et 90%.

Les images ont été prétraitées selon la même méthode que [5], excepté pour l'étape de normalisation des intensités des sujets IRM, qui a été réalisée avec [9].

**Métrique et méthodes comparées.** Afin de valider la méthode, nous procédons par validation croisée : un sujet est retiré de la base pour être segmenté par ceux restants. Cette procédure est itérée sur toute la base de données. L'impact de la taille du patch ainsi que du nombre $k$ de correspondances (c.-à-d., nombre de PM) ont été étudiés. Le Tableau 1 présente des comparaisons d'OPAL avec des résultats publiés obtenus sur la même base de données : une méthode de correspondances multi-modèles (MTM) [4], la méthode PBL originale [5], une méthode de classification par représentation parcimonieuse (SRC) [12], et deux méthodes d'apprentissage par dictionnaire (DDLS) dont une version hors-ligne (F-DDLS) [12]. La qualité de la segmentation des hippocampes droit et gauche a été estimée avec le coefficient Dice $D$, qui compare la segmentation automatique $S_A$ à celle manuelle effectuée par l'expert $S_M$,

$$D(S_A, S_M) = \frac{2 | S_A \cap S_M |}{| S_A | + | S_M |}, \quad (1)$$

où $| \cdot |$ représente le nombre de voxels étiquetés comme structure anatomique.

OPAL a été implémentée avec MATLAB via du code C-MEX parallélisé. Nos expériences ont été menées sur une machine possédant 16 cœurs à 2.6 GHz avec 100GB de RAM. Le nombre de processus a été fixé à $k$, c.-à-d. un pour chaque PM, et le nombre d'itérations de PM a été fixé à 5.

## 3.2 Résultats

**Influence des paramètres.** La Figure 2 montre l'influence du nombre de correspondances et de la taille du patch sur la qualité de la segmentation, ainsi que sur le temps calcul. De même que pour les premières méthodes PBL [5, 12], nous avons déterminé que les patchs de taille $7 \times 7 \times 7$ et surtout $5 \times 5 \times 5$ voxels, fournissent les meilleurs résultats (89.4% pour $k = 20$ et patchs de taille $5 \times 5 \times 5$ voxels). Des patchs plus larges et un plus grand nombre d'ANN demandent logiquement plus de temps de calcul. Par conséquent, nos expériences suggèrent que l'utilisation d'une taille de patch de $5 \times 5 \times 5$ voxels et $k = 10$ offre un bon compromis entre précision de la segmentation (89.3%) et temps de calcul (0.89s).

**Comparaison avec l'état de l'art.** Les performances d'OPAL sont comparées à celles de cinq autres méthodes dans le Tableau 1. Les temps de calcul fournis n'incluent pas l'étape de pré-sélection. Par conséquent, ils sont sous-estimés à l'exception de celui d'OPAL, qui n'effectue pas cette étape. De plus, la méthode F-DDLS requiert un apprentissage hors-ligne de 1781s. Cependant, OPAL obtient le plus haut coefficient Dice, et ce, le plus rapidement. Ces résultats soulignent les excellentes performances d'OPAL en termes de précision de la seg-
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>FIGURE 2 – Coefficient Dice médian selon la taille de patch et le nombre de correspondances (en haut), et le temps de calcul correspondant (en bas).</figcaption></figure>

<table><caption>TABLE 1 – Comparaison des méthodes en termes de précision de la segmentation et de temps de calcul sur la base ICBM.</caption><thead><tr><td>Méthode</td><td>D médian</td><td>Temps de calcul</td></tr></thead><tbody><tr><td>PBL[5]</td><td>88.2%</td><td>662s</td></tr><tr><td>MTM[4]</td><td>88.6%</td><td>3974s</td></tr><tr><td>F-DDLS[12]</td><td>88.6%</td><td>193s</td></tr><tr><td>SRC[12]</td><td>88.7%</td><td>5587s</td></tr><tr><td>DDLS[12]</td><td>89.0%</td><td>943s</td></tr><tr><td><strong>OPAL</strong></td><td><strong>89.3%</strong></td><td><strong>0.89s</strong></td></tr></tbody></table>

mentation et de temps de calcul. OPAL obtient une meilleure précision que pour la méthode PBL originale [5], et ce, 700× plus rapidement. Notre méthode obtient également un coefficient Dice supérieur, et 1000× plus rapidement que la méthode la plus précise (DDLS [12]). Enfin, le temps de calcul d'OPAL reste tout de même 200× inférieur à celui de la méthode la plus rapide publiée sur la même base de données (F-DDLS [12]).

## 4 Conclusion

Dans ce papier, nous proposons une nouvelle méthode de segmentation basée sur l'utilisation de patchs, s'appuyant sur l'algorithme PatchMatch, optimisé pour la fusion d'étiquettes. La méthode proposée obtient des résultats compétitifs en termes de qualité de segmentation et de temps de calcul comparée aux approches de l'état de l'art. En effet, OPAL a obtenu le plus haut coefficient Dice, et ce, avec le plus faible temps de calcul. De plus, les capacités temps-réel d'OPAL ouvrent la voie à de nouvelles applications. OPAL peut être utilisée par exemple comme outil performant de segmentation automatique ou interactive dans un logiciel de visualisation médicale. Enfin, un futur travail sera de valider OPAL sur des bases de données hétérogènes ne contenant pas uniquement des sujets sains.

## Remerciements

Ce travail a bénéficié d'un support financier de l'état Français, via l'Agence Nationale de la Recherche (ANR) dans le cadre d'Investissements d'avenir Initiative d'excellence IdEx Bordeaux (ANR-10-IDEX-03-02), le Cluster d'excellence CPU et TRAIL (HR-DTI ANR-10-LABX-57). Les auteurs souhaitent également remercier le Fonds de Recherche du Québec - Santé (FRQS-Pfizer).

## Références

[1] C. Barnes et al. PatchMatch: A Randomized Correspondence Algorithm for Structural image Editing. ACM SIGGRAPH, 28(3), 2009.

[2] C. Barnes et al. The Generalized PatchMatch Correspondence Algorithm. ECCV, 6313:29-43, 2010.

[3] D.L. Collins et al. Automatic 3-D model-based neuroanatomical segmentation. Human Brain Mapping, 3(3):190-208, 1995.

[4] D.L. Collins et al. Towards accurate, automatic segmentation of the hippocampus and amygdala from MRI by augmenting ANIMAL with a template library and label fusion. NeuroImage, 52(4):1355-1366, 2010.

[5] P. Coupé et al. Patch-based segmentation using expert priors: Application to hippocampus and ventricle segmentation. NeuroImage, 54(2):940-954, 2011.

[6] S.F. Eskildsen et al. BEaST: Brain Extraction based on nonlocal Segmentation Technique. NeuroImage, 59(3):2362-2373, 2012.

[7] R.A. Heckemann et al. Automatic anatomical brain MRI segmentation combining label propagation and decision fusion. NeuroImage, 33(1):115-126, 2006.

[8] J. Lötjönen et al. Fast and robust multi-atlas segmentation of brain magnetic resonance images. NeuroImage, 49(3):2352-2365, 2010.

[9] J.V. Manjón et al. Robust MRI brain tissue parameter estimation by multistage outlier rejection. Magnetic Resonance in Medicine, 59(4):866-873, 2008.

[10] J.C. Pruessner et al. Volumetry of hippocampus and amygdala with high-resolution MRI and three-dimensional analysis software: minimizing the discrepancies between laboratories. Cerebral Cortex, 10(4):433-442, 2000.

[11] F. Rousseau et al. A supervised patch-based approach for human brain labeling. Medical Imaging, 30(10):1852-1862, 2011.

[12] T. Tong et al. Segmentation of MR images via discriminative dictionary learning and sparse coding: Application to hippocampus labeling. NeuroImage, 76:11-23, 2013.

[13] G. Wu et al. A generative probability model of joint label fusion for multi-atlas based brain segmentation. Medical Image Analysis, 18(6):881-890, 2014.