Analyse et omparaison de pro édures d'optimisation entomodensitométrieMaxime Toussaint, Christian Thibaudeau, Roger Le omte et Jean-Pierre DussaultUniversité de SherbrookeCourriel: maxime.toussaint�usherbrooke. a8 dé embre 2011

RésuméLa tomodensitométrie est une modalité d'imagerie médi ale utilisée pour représenter la stru ture interned'un être vivant. La re onstru tion de ette image doit être rapide et stable. En outre, le résultat doitreprésenter le plus �dèlement que possible la réalité. Ce do ument propose de omparer les performan esde quelques algorithmes itératifs en termes de qualité d'image re onstruite et de durée de al ul. Parmiles algorithmes testés, ertains ont été développés spé ialement pour le problème de tomodensitométriealors que d'autres sont des solveurs généraux. De plus, ha un des algorithmes sera testé ave une vari-ante in luant un terme de régularisation. Ce do ument propose de tester quelques variantes de gradient onjugué non-linéaire a�n d'observer leur performan e en tomodensitométrie.

Table des matières1 Introdu tion 32 Algorithmes utilisés 42.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Con ept ommun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 APT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 SG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Des ription des images tests utilisés 133.1 Shepp-logan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Shepp-logan fa ile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3 H.G.D. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4 Catphan CTP401 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 Analyses a omplies 144.1 Observer l'évolution des solutions au �l des itérations . . . . . . . . . . . . . . . . . . . . . . 154.2 Comparer les solutions obtenues ave un ritère d'arrêt . . . . . . . . . . . . . . . . . . . . . . 165 Résultats obtenus 175.1 Comportement des algorithmes sur 80 itérations . . . . . . . . . . . . . . . . . . . . . . . . . 175.2 Étalon des solutions obtenues à l'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 Idée à explorer 196.1 Les paramètres de la fon tion de pénalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 196.2 La majoration de la ourbure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196.3 Optimisation séquentielle de sous espa es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196.4 Approfondir l'expérien e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Remer iements 208 Annexe 208.1 Majoration utilisée dans pasAdmissible2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208.2 Zone d'importan e pour l'évaluation du LMH et de la varian e . . . . . . . . . . . . . . . . . 218.3 Con�guration d'a quisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218.4 Mires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228.5 Code des mires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238.6 Comparaison d'images obtenues ave quelques algorithmes . . . . . . . . . . . . . . . . . . . . 258.7 Figures utilisées dans l'analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2

1 Introdu tionLa tomodensitométrie est une pro édure qui onsiste à exploiter le taux d'absorption de rayons-x destissus pour représenter la stru ture interne d'un être vivant. Ce pro édé se divise en trois étapes, soit l'a -quisition, le traitement des données et la re onstru tion. Ce do ument se on entra sur ette dernière étapedans le as parti ulier d'une géométrie d'a quisition en seulement 2 dimensions.Dans la littérature, deux familles de méthode sont souvent reliées à la tomodensitométrie. Les méthodesanalytiques qui reposent sur l'inverse de la transformée Radon et les méthodes itératives qui optimisent desmodèles orrespondant au problème. Ces deux pro édés sont possibles grâ e à un théorème démontré parM. Johann Radon en 1917 [RP86℄.Théorème de proje tion de Radon : Si la totalité des proje tions d'un objet est disponible et que es dernières sont a quises selon des droites parallèles, il est alors possible de re onstruire la fon tion réelleà deux variables (position spatiale en x et en y) représentant et objet.En pratique, il est impossible d'obtenir toutes les proje tions. Toutefois, un sous é hantillon judi ieuse-ment hoisi permet d'a quérir su�samment de données pour onserver l'idée du théorème. De plus, leslimitations des ressour es informatiques ne permettent pas de représenter l'objet dans sa forme ontinue. Ladis rétisation en voxels permet de pallier à ette la une. Pour plus d'informations on ernant l'a quisitionet le traitement des données, le le teur est invité à onsulter [KS88℄ et [H80℄.Deux ara téristiques importantes en tomodensitométrie di�éren ient les algorithmes analytiques de euxdits itératifs : la durée de re onstru tion et la �exibilité de la méthode. Pour se représenter la di�éren e, ilfaut omprendre leur fon tionnent. La re onstru tion par al ul analytique onsiste à appliquer la fon tioninverse sur les résultats obtenus. L'idée de base veut que la méthode d'a quisition des données peut êtrereprésentée par une fon tion qui, en utilisant le théorème de proje tion de Radon, admet un inverse. Leprin ipe lé des algorithmes itératifs est de représenter la problématique sous forme d'un problème d'opti-misation et de her her, à haque étape, une solution qui se rappro he de la vérité. Il s'agit ensuite d'arrêterlorsque ette solution est jugée satisfaisante.Pour omparer la vitesse de re onstru tion des familles d'algorithmes, il faut introduire l'élément le plus oûteux à manipuler, soit la matri e système. Cette matri e permet de relier les données a quises à laversion dis rète de l'objet. Elle devient rapidement imposante puisque sa forme expli ite est omposée deNp × Nd × Nv éléments (où Np représente le nombre deproje tions, Nd le nombre de déte teurs et Nv lenombre de voxels). Ainsi, la vitesse de re onstru tion des méthodes dépendra largement de la taille de ettematri e et du nombre de fois qu'elle doit être utilisée. La méthode analytique demande l'appli ation d'uneformule, soit l'inverse de la fon tion de Radon, e qui onsiste à n'utiliser qu'une seule fois la matri e systèmepour approximer notre objet. La méthode itérative demande l'appli ation de ette matri e au minimum unefois par itération. Don , la méthode itérative demande beau oup plus de al ul que la méthode analytique.Toutefois, les algorithmes itératifs sont onnus pour être plus �exibles que les algorithmes analytiques. D'unepart, il est possible d'in lure dans es premiers la mathématique liée à la physique du pro essus d'a quisition(telle que la nature Poissonnienne du omptage de photons). D'un autre �té, alors que les algorithmes analy-tiques doivent travailler ave des données spatialement équidistribuées (et souvent uniquement en géométrieparallèle), les méthodes itératives ne sou�rent d'au unes limitations de e type. En modélisant orre tementla géométrie du système d'a quisition, par le biais de la matri e système, toutes les on�gurations possibles des anners peuvent être utilisées pour produire des images sans ré-interpolation des données. Les algorithmesitératifs sont prin ipalement omposés de deux éléments. D'abord, il faut un modèle qui se omporte bien, 'est-à-dire ontinu et dérivable, et dont l'image re her hée orrespond à la solution optimale. Puis, il fautune méthode d'optimisation qui onverge globalement vers la solution désirée. Les détails seront expliquésdans la se tion suivante. 3

Le but de e do ument est de omparer les performan es de di�érentes méthodes itératives. A�n d'o�rirune vue d'ensemble sur les méthodes disponibles en tomodensitométrie, des algorithmes re onnus dans ledomaine ont été employées ainsi que des variantes de deux solveurs généraux qui semblent prometteuses.Ainsi, la liste est omposée de méthodes développées uniquement pour résoudre des problèmes de tomogra-phie et de solveur général. Il est à noter que dans e travail, es deux groupes sont respe tivement nommésAPT 1 et SG 2. De plus, ha un de es algorithmes sera testé ave et sans un terme de régularisation, e quipermettra d'observer leurs performan es omparatives. Pour �nir, les expérien es in luent un APT qui sesert de sous-groupes ordonnés, une méthode re onnue dans la littérature pour sa rapidité de onvergen e.Avant de présenter les résultats, e do ument propose d'introduire les éléments testés. Pour ommen er,la motivation et la forme expli ite des modèles et des algorithmes in lus dans les expérien es seront présen-tées. Ensuite, les mires utilisées dans les simulations seront dé rites. Suivra la des ription de la méthodologieappliquée pour e�e tuer les tests et les omparaisons. Les résultats, appuyés par des graphiques, viendrontillustrer les performan es des algorithmes. Finalement, une évaluation des performan es et une ouverture sur e qui pourrait être fait pour approfondir le sujet se trouvent en on lusion de e do ument. Notez que laplupart des �gures se trouvent en annexe. Celle présentées dans le orps du texte ont simplement pour butde fa iliter la ompréhension lors de la le ture.2 Algorithmes utilisésCette se tion dé rit les algorithmes manipulés pendant e projet. Tout d'abord, la notation utilisée pourdé rire les algorithmes sera introduite. Ensuite, les on epts ommuns aux APT et aux SG seront présentés.Puis, ha un des algorithmes seront expliqués. Notez que les trois premiers ont été introduits dans [LF95℄ etque les preuves de leur onvergen e sont expliquées en détail dans elui- i.1. APT : Algorithmes Produits pour la Tomodensitométrie2. SG : Solveurs généraux

4

2.1 NotationsPosons : I Nombre de proje tions Np multiplié par le nombre de déte teur Nd

J Nombre de voxelsµ Ve teur olonne de J éléments tel que µj est la moyenne d'absorption dans le voxel jµ∗ Valeur ourante de l'estimé de µ à une itération donnéel Matri e I × J tel que lij est la longueur d'interse tion entre la proje tion i et le pixel ji Indi e utilisé pour représenter les di�érentes proje tionsj Indi e utilisé pour représenter les di�érents voxelsk Indi e utilisé pour représenter les voxels qui partagent au moins un vertex ave laproje tion ib Indi e utilisé pour représenter les di�érents déte teursY Ve teur olonne de I éléments tel que Yi est le nombre de photons déte té à laproje tion i lorsque l'objet est présentY Ve teur olonne de I éléments tel que Yi = Yi/db où b = i mod Nd

Y Ve teur olonne de I éléments tel que Yi = ln(Yi)d Ve teur olonne de Nd éléments tel que db est le nombre de photonsqui est ompté par le déte teur b lorsque l'objet est absent11 Ve teur ligne de I éléments tel que Ii = 1 ∀iγ Constante utilisée dans la fon tion pénalisationwj1j2 Constantes utilisées dans la fon tion pénalisationκ Ensemble de J valeurs tel que κj représente le poids relatif du voxel jǫ Constante utilisée dans la fon tion potentielx_critique Valeur utilisée pour évaluer ǫη Valeur utilisée pour évaluer ǫ2.2 Con ept ommunModèle utilisant la log-vraisemblan eLes APT présentés dans e do ument reposent tous sur le même modèle. Seulement la méthode permet-tant de trouver la solution optimale varie. Il faut don ommen er par présenter e modèle.Le modèle en question est la vraisemblan e 3 logarithmique des données obtenues. Cette méthode possèdedes propriétés théoriques intéressantes et est re onnue pour son e� a ité dans divers domaines. Elle permeten autre de modéliser orre tement le fait que le nombre de photons ompté suit une loi de Poisson. Cette ap-pro he permet d'obtenir une fon tion obje tif qui répond à la problématique. Il est évident, par la dé�nitionde la vraisemblan e, que la stru ture re her hée est une solution optimale de e modèle. Il est aussi possiblede démontrer, ave l'hypothèse que les données ne sont pas trop bruitées, que le maximum du logarithmede la vraisemblan e produit une fon tion obje tif qui a pour unique solution optimale elle re her hée. Pour�nir, les propriétés du logarithme naturel vont permettre de simpli�er la fon tion obje tif. Notez que le mod-èle in lut a posteriori le omportement Poissonnien du taux d'absorption. Ainsi, l'algorithme devrait être enmesure de produire des images satisfaisantes même lorsque le nombre de rayon-x utilisé est statistiquementfaible.Origine de la fon tion obje tif :Posons g(Y, µ) la vraisemblan e de µ sa hant Y et fi(Yi, µ) la vraisemblan e de µ sa hant Yi.3. La vraisemblan e est une fon tion qui orrespond à se demander : "Quel devrait être la valeur des paramètres onsidérantles résultats obtenus et le modèle statistique qu'ils suivent ?" 5

Notez que la probabilité qu'un photon réussit à traverser un objet obéit à une loi de Poisson.ln(g(Y, µ)) = ln(

∏Ii=0 f(Yi, µ)) Yi sont indépendants

=∑I

i=0 ln(f(Yi, µ)) Prop. de ln=∑I

i=0 ln(e−die

−〈li,µ〉(die

−〈li,µ〉)Yi

Yi!) Déf. loi de poisson

=∑I

i=0 ln(e−die

−〈li,µ〉

) + ln((die−〈li,µ〉)Yi)− ln(Yi!) Prop. de ln

=∑I

i=0−die−〈li,µ〉 + Yi(ln(di) + ln(e−〈li,µ〉))− ln(Yi!) Prop. de ln=∑I

i=0−die−〈li,µ〉 + Yiln(di)− Yi〈li, µ〉 − ln(Yi!) Prop. de ln=∑I

i=0−die−〈li,µ〉 − Yi〈li, µ〉+ constante µ est la seule variableAinsi, l'image re her hé est la solution du problème d'optimisation suivant :argmax

µln(g(Y, µ)) = argmax

µ

I∑

i=0

−die−〈li,µ〉 − Yi〈li, µ〉Notez : L(µ) =∑

i=1{−die−〈li,µ〉 − Yi〈li, µ〉}∂L(µ)∂µj

=∑

i=1 lij [die−〈li,µ〉 − Yi]

∂2L(µ)∂µj∂µk

= −∑i lij likdie−〈li,µ〉Fon tion de pénalisationDans un monde parfait, les données obtenues lors de l'a quisition ne seraient pas a�e tées par des lim-itations physiques telles que la di�usion des rayons-X et le bruit de mesure des déte teurs. De plus, il estadmis que les stru tures re onstruites en tomodensitométrie sont généralement omposées de zones assezuniformes. Il est don parfois avantageux de for er les algorithmes à obtenir des solutions qui respe tent espropriétés. Une démar he re onnue en optimisation est d'ajouter une fon tion de pénalisation à la fon tionobje tif de départ. Par exemple, le but des APT est de maximiser la log vraisemblan e. Don , il faut unefon tion qui nuit à la maximisation lorsque la solution est peu uniforme. Son e�et doit augmenter lorsquedes voxels voisins possèdent des valeurs di�érentes tout en évitant de favoriser le rappro hement de voxelsvoisins très di�érents. Pour e projet, le hoix est tombé sur une fon tion suivant l'idée de la variation totale.Voi i la forme générale de la fon tion de pénalisation implantée :Ψ(µ) = γ

J∑

j

Kj∑

k

κjκkwjkφ(µj − µk)

tel queφ(µ) =

√

ǫ+ x2est la fon tion potentiel.Dans les SG de e projet, il faut additionner ette fon tion à la fon tion obje tif pour satisfaire le problèmede minimisation. De son �té, la onstante gamma établit la for e de la régularisation et le ompromis entrela résolution spatiale et le bruit dans l'image re onstruite. L'epsilon, produit une barrière qui di te la valeurde x_critique, où la fon tion potentiel passe d'une roissan e quadratique à une roissan e linéaire. Ainsi,lorsque la di�éren e entre deux voxels dépasse ette valeur, la fon tion onsidère que les voxels ne sont pas dela même valeur et aura moins tendan e à pénaliser leur di�éren e. L'idée est de s'assurer que les délimitationsentre deux zones uniformes ne soient pas trop lissées.Voi i la formule pour al uler la valeur d'epsilon pour les tests présentés dans e do ument 4 :ǫ =

(

x_critique

η

)2

(1− η)24. Cette formule orrespond à trouver ǫ tel que φ′(xcritique) = η6

Où η ∈ (0, 1) tel que plus η est pro he de 1, plus la fon tion potentiel va tenter de for er le rappro hementde voxels voisin. Les omégas servent à pondérer la valeur de la fon tion potentiel selon la proximité desvoxels j et k. Dans e travail, les poids asso iés aux voxels partageant deux vertex, un vertex et zéro vertexsont respe tivement 1, 1/√2 et 0. En�n, l'essen e des kappas est de pondérer ha une des sommes a�nd'obtenir une résolution uniforme dans l'image. La preuve qu'une pénalisation standard produit des imagesde résolution non uniforme, la motivation des kappas et plus en ore sont disponible dans [FR96℄. De plus,les auteurs de e rapport te hnique présentent une méthode pour produire une table de gamma, propre à haque on�guration d'a quisition, qui permet de hoisir la résolution désirée.Voi i la formule pour al uler les kappas pour les tests présentés dans e do ument :κj(µ) =

√

∑

j

l2ijYi/∑

j

l2ij2.3 APTL'ati le suivant [LF95℄ expli ite les motivations et les preuves de onvergen es des algorithmes APTprésentés dans le présent do ument.Algorithme EMPour ommen er, onstatez que le problème est plus fa ile à résoudre si l'ensemble des données estdisponible. C'est-à-dire que non seulement le nombre de photons sortant de la sour e, di, et sortant de l'ob-jet, Yi, sont onnus, mais aussi elui qui entre et sort de haque voxel, pour haque proje tion. Notons Uijet Vij étant respe tivement le nombre de photon rentrant et sortant au voxel j sur la proje tion i.L'algorithme EM onsiste à répéter deux étapes. Pour ommen er, il al ule l'espéran e de la fon tion ob-je tif en utilisant le dernier estimé de µ. Puis, il trouve le µ qui maximise la fon tion obtenue à la premièreétape. Pour formuler la fon tion obtenue dans la première étape, notez Q(µ|µn) où µn est le dernier es-timé. Il devient né essaire de onnaître Mij = E(Uij |Yi, µn) et Nij = E(Vij |Yi, µ

n). Or, [LC84℄ démontreque Mij = Yi + die−

∑k∈Sij

likµ∗k − die

−〈li,µ∗〉∀i, j et que Nij = Yi + die

−∑

k∈Sij∪j likµ∗k − die

−〈li,µ∗〉 ∀i, j.Notez que Sij est l'ensemble des voxels se trouvant entre la sour e et le pixel j, sur la proje tion i. Ainsi,

Q(µ|µ∗) =∑

ij [Nij lijµj + (Mij −Nij)ln(1− e−lijµj )].Toutefois, il est di� ile d'expli iter le µ qui maximise ette fon tion. Malgré tout, il a été démontré quela fon tion Q(µ|µ∗) admet seulement un extremum et qu'il s'agît d'un maximum global. Il existe plusieursméthodes pour approximer la solution her hée. Celle hoisie pour l'algorithme EM est d'approximer l'élé-ment problématique, soit (e−likµk − 1)−1 de la fon tion par une approximation de sa série de Taylor. Aprèsavoir pris en onsidération la pré ision voulue et le nombre de al uls, les auteurs de [LC84℄ ont dé idéd'utiliser une approximation d'ordre 3. C'est-à-dire que 1s− 1

2 +s12 +O(s3) est utilisé pour approximer 1

(es−1)puisque 1(es−1) = 1

s− 1

2 + s12 + (s3) où s = likµk. Ainsi, les valeurs approximatives qui maximisent Q(µ|µ∗)sont égales à µj =

[11(M.j−N.j)]1

2[M.j+N.j ]tl.j

∀j.7

Espéran e-Maximisation (µ, Y , l, Sij){ Donnés : µj > 0 ∀j ; }{ Indi e des pixels entre la sour e i et le pixel j : Sij }{ Q(µ|µ∗) =

∑

ij [Nij lijµj + (Mij −Nij)ln(1− e−lijµj )] }répéterMij ← Yi + e

−∑

k∈Sijlikµ

∗k − e−〈li,µ

∗〉 ∀i, jNij ← Yi + e

−∑

k∈Sij∪j likµ∗k − e−〈li,µ

∗〉 ∀i, jµ∗j ←

[11(M.j−N.j)]1

2[M.j+N.j ]tl.j

≈ maxµ>0 Q(µ|µ∗) ∀jjusqu'à ( Critère de onvergen e satisfait)Résultats ← µ∗ Algorithme 1 � trmlL'algorithme 2 est une modi� ation de la méthode de Newton appliquée à la fon tion obje tif pénalisée.Notez que la fon tion de pénalité exploitée est une majoration de Ψ qui respe te l'idée des algorithmes EMet que seulement les éléments diagonales du Hessien sont utilisés.Majoration de Ψ : V (µ|µ∗) = γ2 (∑

j

∑

k(wjkφ(µj − µ∗k − µ∗

j )))

+ γ2 (∑

j

∑

k(wjkφ(µk − µ∗k − µ∗

j )))Fon tion optimisée : −Υ(µ|µ∗) = −Q(µ|µ∗) + V (µ|µ∗)Espéran e-Maximisation pénalisé (µ, Y , l, Sij){ Donnés : µj > 0 ∀j ; }{ Q(µ|µ∗) =

∑

ij [Nij lijµj + (Mij −Nij)ln(1− e−lijµj )] }répéterMij ← Yi + e

−∑

k∈Sijlikµ

∗k − e−〈li,µ

∗〉 ∀i, jNij ← Yi + e

−∑

k∈Sij∪j likµ∗k − e−〈li,µ

∗〉 ∀i, jµ∗j ← µ∗

j −(∇Υ(µ|µ∗)|µ=µ∗ )j(∇2Υ(µ|µ∗)|µ=µ∗ )j

∀jjusqu'à ( Critère de onvergen e satisfait)Résultats ← µ∗Algorithme 2 � trml_PAlgorithme du gradientL'ar hite ture de ette pro édure provient d'une observation faite sur l'algorithme EM dans le as del'émission. En e�et, elle peut être représenté sous la forme suivante : λn+1 = λn +D(λn)dL(λn)′. Où λ estl'équivalent du oe� ient d'atténuation dans le as de l'émission et D(λn) est une matri e diagonale telle queD(λn)jj =

λnj∑

i∈JjCij

. Pour la transmission, ette reformulation est omplexe. Toutefois, la forme généralede la formulation dans le as de l'émission permet de développer un algorithme pour la transmission. Pour ommen er, il faut hanger λ et la dérivée de sa fon tion obje tif par leur équivalent dans le as de la trans-mission. Trouver l'équivalent de D(λn) pour la situation étudiée exige une observation de son omportementdans sa formulation de départ. A�n que le omportement de D(λn) soit semblable dans les deux as, il fautque D(µn)jj =µnj∑

i∈JjYilij

. Don , la formule obtenue est de la forme suivante : µj = µnj +D(µn

j )j∇L(µj)j

∀j. Cet algorithme demande moins de al ul que la version EM puisqu'il né essite le al ul de moins d'expo-nentielles. Cependant, il n'assure pas que L(µ) augmente pour haque itération. Cette propriété est obtenue8

en al ulant un pas admissible à haque itération.Des ente par le gradient (µ, Y , l, UseArmijo){ Donnés : µj > 0 ∀j ; }répéter

dirj ← µ∗j

Y tli.∇L(µ∗)j ∀j

f ← ∑

i=1{−die−〈li,µ〉 − Yi〈li, µ〉}|µ=µ∗

g ← ∑

i=1 lij [die−〈li,µ〉 − Yi]|µ=µ∗

θ ← trouvePasAdmissible(f, g, dir)µ∗j ← µ∗

j + θ × dirj ∀jjusqu'à ( Critère de onvergen e satisfait)Résultats ← µ∗Algorithme 3 � GradientOù trouvePasAdmissible renvoie θ tel que θ respe te le ritère d'Armijo 5. La méthode ommen e partester θ = 1 et divise par 2 le θ jusqu'à e qu'il trouve un θ satisfaisant.trouvePasAdmissible (f, g, dir){ Donnés : f valeur de la fon tion obje tif, g sa dérivée et dir la dire tion de la mise à jour de l'algo ; }{ F est la fon tion obje tif }τ0 ← 0.25prodGradDir ← 〈g, dir〉tantque ([F (µ+ θ ∗ dir)− f ] < τ0 ∗ θ ∗ prodGradDir )

θ ← θ/2Résultats ← θ Algorithme 4 � trouvePasAdmissibleL'algorithme qui suit est une modi� ation de la méthode de Newton appliquée sur la fon tion obje tifpénalisée. L'équation maximiser est la somme de −Ψ(µ) et de Q(µ|µ∗) tel queQ(µ|µ∗) =

∑

j

(

µj(lije−〈li,µ〉)−

µ2j

2

∑

i Yilijµ∗j

)

5. Voir ondition d'arrêt de trouvePasAdmissible

9

Des ente par le gradient pénalisé (µ, Y , l, UseArmijo){ Donnés : µj > 0 ∀j ; }{ ∆(µ) = Q(µ|µ∗)−Ψ(µ) }répéter

dirj ←µ∗j∑

i Yilij+µ∗j (∇

2Ψ(µ))jj |µ=µ∗(∇∆(µ))j |µ=µ∗ ∀j

f ← ∑

i=1{−die−〈li,µ〉 − Yi〈li, µ〉}|µ=µ∗

g ← ∑

i=1 lij [die−〈li,µ〉 − Yi]|µ=µ∗

θ ← trouvePasAdmissible(f, g, dir)µ∗j ← µ∗

j + θ × dirj ∀jjusqu'à ( Critère de onvergen e satisfait)Résultats ← µ∗Algorithme 5 � Gradient_PAlgorithme onvexL'algorithme onvexe a été adapter à partir de son homonyme en tomographie par émission. Il onsisteà formuler, pour haque itération, une équation équivalente à la fon tion obje tif et de trouver le µ orre-spondant à son maximum. Soit fi(t) = die−t+Yit. Cette équation est stri tement onvexe. Ainsi, la fon tionobje tif peut être reformulée omme suit : L(µ) = −∑i fi(〈li, µ〉). Insérez les idées de De Pierro dans le asde la tomographie par émission et la pro édure est omplète :

L(µ) = −∑i fi(〈li, µ〉)= −∑i fi(

∑

j

lijµnj

〈li,µn〉µj

µnj

〈li, µn〉)≥ −∑i

∑

j

lijµnj

〈li,µn〉fi(µj

µnj

〈li, µn〉)= Q(µ|µn)La forme de Q(µ|µn) garantit que le µ maximisant e dernier orrespond à elui maximisant aussi lafon tion obje tif. Don , il ne reste plus qu'à trouver µ qui maximise Q(µ|µn). Puisque fi(t) est une fon tion onvexe, le seule point stationnaire de Q(µ|µn) est un maximum global. Or, il est di� ile de résoudreanalytiquement l'équation 0 = ∂

∂µjQ(µ|µn). Les auteurs de [LF95℄ ont dé idé de se servir de la méthode deNewton pour trouver la solution optimale. Notez que et algorithme ne garantit pas que µn

j ≥ 0. Toutefois,l'argument respe te habituellement ette restri tion dans la pratique.

10

Algorithme onvexe (µ, Y , d, l){ Donnés : µj > 0 ∀j ; }{ Q(µ|µ∗) = −∑ij

lijµ∗j

〈li,µ∗〉µj

µ∗j〈li, µ∗〉 }

{ fi(t) = e−t + Yit }répéterµ∗j ← µ∗

j +∇Q(µ|µ∗)j |µ=µ∗

∇2Q(µ|µ∗)jj |µ=µ∗∀jjusqu'à ( Critère de onvergen e satisfait)Résultats ← µ∗Algorithme 6 � ConvexLa modi� ation de l'algorithme onvexe pour tenter de diminuer le bruit est la même que elle de l'algo-rithme EM.Algorithme onvexe pénalisé (µ, Y , l)

{ Donnés : µj > 0 ∀j ; }{ fi(t) = e−t + Yit }{ Q(µ|µ∗) = −∑ij

lijµ∗j

〈li,µ∗〉fi(µj

µ∗j

〈li, µ∗〉) }{ V (µ|µ∗) = γ

2 (∑

j

∑

k(wjkφ(µj − µ∗k − µ∗

j ))) +γ2 (∑

j

∑

k(wjkφ(µk − µ∗k − µ∗

j ))) }{ Υ(µ|µ∗) = Q(µ|µ∗)− V (µ|µ∗) }répéter

µ∗j ← µ∗

j −(∇Υ(µ|µ∗)|µ=µ∗ )j

(∇2Υ(µ|µ∗)|µ=µ∗ )jj∀jjusqu'à ( Critère de onvergen e satisfait)Résultats ← µ∗ Algorithme 7 � Convex_PEn re onstru tion itérative, il existe une lasse d'algorithme qui est re onnue pour sa rapidité de re on-stru tion. Il s'agit des algorithmes utilisant les sous-ensembles ordonnés, notés OS. Le prin ipe est de séparerles proje tions en quelques groupes et de mettre à jour, à haque itération, la solution ave ha un des sous-groupes. De manière à diversi�er l'information ontenue dans un sous-groupe, la séparation angulaire entreses éléments est maximisée. La mise à jour peut être faite ave n'importe quelle méthode APT. La référen e[KB05℄ rapporte les performan es pour di�érentes grandeurs d'OS 6. Toutefois, ette méthode tournera au-tour de la solution optimale du problème sans l'atteindre puisqu'elle tente de résoudre le sous-problème ourant. Malgré tout, les performan es des OS méritent d'être analysés plus en détails. Ainsi, l'algorithme onvexe et onvexe pénalisé tous deux ave 10 OS seront in lus dans les tests. Dans e do ument, onvexosva être utilisé pour désigné l'utilisation de l'algorithme onvex ave 10 OS.2.4 SGLes SG vont être appliqués sur deux fon tions obje tif, soit L(µ) et G(µ). L(µ) est la fon tion utiliséeave les APT. G(µ) est une approximation quadratique de L(µ). La démar he derrière le développement de ette formule se retrouve dans l'appendi e A de [SB93℄.

G(µ) = 12 ‖ Y − lµ ‖2Σ où Σ = diag{Y1, ..., YJ}6. OS vient de Ordered subsets 11

Gradient onjugué non linéaireLa méthode du gradient onjugué non linéaire est souvent utilisée pour résoudre des problèmes d'opti-misation ave des systèmes éparses. Cette te hnique fait partie de la famille des algorithmes à dire tion dedes ente. En parti ulier, sa dire tion de des ente est omposée de l'inverse additif du gradient à laquelle estajouté une fra tion, le Bêta, de la dire tion appliqué dans l'itération pré édente. Pour plus d'information sur et algorithme, voir [HZ05℄.Posons F (µ) la fon tion obje tif. Alors F (µ) est omposé de −L(µ) ou de G(µ) additionné à une fon -tion barrière. Il su�t d'ajouter la fon tion Ψ pour avoir un modèle qui onverge vers une image moins bruitée.Cette pro édure n'a pas été onstruite pour prendre en ompte des ontraintes. Une fon tion barrièreest ajoutée à l'obje tif a�n d'assurer que la solution �nale soit dans le domaine réalisable. La seule restri -tion en tomodensitométrie est qu'un oe� ient d'atténuation ne peut pas être négatif. La fon tion hoisiedans e projet est la barrière logarithme. Don , elle a la forme suivante : ρ∑j ln(µj). Puisque l'obje tif estde minimiser et que logarithme naturel d'un nombre près de 0 est négatif, il faut soustraire ette fon tionau modèle. Le rho régularise la for e de la barrière. Cette dernière doit être diminuée lorsque la solutionoptimum du problème ourant est obtenu. La solution du problème respe tant les ontraintes est atteintelorsque rho est su�samment petit. Voir [D95℄ pour une expli ation détaillée de la méthode. Notez que Bêtadoit être remis à 0 lorsque rho est diminué puisque le problème n'est plus le même.Algorithme gradient onjugué Formule de Polak et Ribière(µ, Y , l){ Donnés : µj > 0 ∀j ; }β ← 0g ← derfon tObjrépéter

dir ← −derfon tObj +β × dirf ← fon tObjθ ← trouvePasAdmissible2(f, g, dir)g_prec ← gµj ← µj + θ × dirsi (µ est la solution optimale du problème ourant ) alors

ρ ← 0.5ρβ ← 0sinong ← derFon tObjy ← g − g_precβ ← Formule Beta de Pilak et Ribière ou de Hager et Zhangβ ← max(0, β)jusqu'à ( Critère de onvergen e satisfait)Résultats ← µ Algorithme 8 � Grad_ConjFormule Bêta de Polak et Ribière :

β =〈g, yt〉〈g, gt〉

12

Formule de Hager et Zhang :β =

1

〈y, dir〉

(

y − 2× dirt〈y, yt〉〈y, dir〉

)

gL'implémentation de trouvePasAdmissible2 est dé rite dans [CMI09℄. Elle a été onstruite spé i�quementdans le but de trouver un pas optimal dans le as où la fon tion obje tif in lut une fon tion barrière. Lesperforman es de ette méthode peuvent être modi�ées par l'utilisateur à l'aide de deux paramètres : le nombred'itérations et la majoration de la fon tion obje tif sans la barrière. Un plus grand nombre d'itérations permetde trouver un meilleur estimé de pas optimal. Tandis qu'un hoix judi ieux de majoration 7 permet de faireles approximations sur un modèle pro he de elui qui doit être maximisé. L'implémentation de ette méthodedans le adre des tests de e projet limite le nombre d'itérations de trouvePasAdmissible2 à 6. Ce hoix a étémotivé en observant l'évolution du pas à haque itération pour une batterie de test et par la volonté d'utiliserle moins possible la matri e système. Les majorations utilisées et leur motivation peuvent être trouvés à lase tion 8.1.L-BFGS-BLe L-BFGS-B orrespond à Limited-memory Broyden Flet her Goldfarb Shanno Bounded. Elle fait partiede la famille des méthodes quasi-Newton d'optimisation. Il s'agît d'une variante de L-BFGS qui prend en ompte les restri tions de la forme ai ≤ xi ≤ bi. Cette méthode est re onnue pour ses bonnes performan esdans des problèmes d'optimisation ave un grand nombre de variables. De plus, les résultats présentés dans[HGD11℄ indique que et algorithme est e� a e dans des problèmes de tomodensitométrie. Les tests ontété fait ave le ode présent dans EMAN2 8. Pour e projet, L-BFGS-B garde en mémoire les 13 dernièresitérations e�e tuées.Posez F (µ) la fon tion obje tif. Alors F (µ) est omposé de −L(µ) ou de G(µ). Il su�t d'ajouter lafon tion Ψ(µ) pour avoir un modèle qui onverge vers une image moins bruitée.3 Des ription des images tests utilisésA�n de omparer les performan es des algorithmes dans di�érentes situations, les données vont êtresimulées à partir de 4 objets synthétiques. Les mires de test ont été produites par CTSim 9 et les sinogrammesont été réés par simulation à l'aide du programme Spe troSin développé par M. Christian Thibaudeau. Lasimulation a été produite dans quatre onditions di�érentes. Soit 100, 1 000 et 10 000 photons envoyés pardéte teur par proje tion en ajoutant un bruit de nature Poissonienne 10 et une version sans bruit. Ainsi, ilest possible d'e�e tuer des analyses plus intéressantes.Pour fa iliter et uniformiser l'évaluation des ritères de omparaison, les objets ont été onstruits ave quelques propriétés. Tout d'abord, les objets peuvent tous être insérés dans un plan de 20 par 20 mm. Le al ul de ertains des ritères de omparaison utilisés dans e projet exige une zone uniforme, notée A, et unemin e ligne, notée B, ave un oe� ient d'atténuation élevé. Voir la se tion 8.2 pour observer leur positiondans les mires. Les valeurs des oe� ients d'atténuation des mires ont été ajustées a�n que la zone qui in lutA ait la même amplitude dans les quatre mires. Les mires sont a� hées à la se tions 8.4.Le ode qui a permis de onstruire les mires et des images de eux- i se retrouvent respe tivement auxse tions 8.5 et 8.4 respe tivement.7. C'est-à-dire une valeur pro he du maximum en valeur absolue de la ourbure de la fon tion obje tif.8. http :blake.b m.edueman2doxygen_htmllbfgsb_8 pp_sour e.html9. Programme open sour e de simulation de tomographie, http :// tsim.org/10. Le rapport de signal-sur-bruit est donné par N/sigma = N/sqrt(N)13

3.1 Shepp-loganLa mire du Shepp-logan, dont la dé�nition peut être trouvée dans [KS88℄, représente une oupe du rânehumain. À l'intérieur de elui- i, se trouvent des zones d'atténuation di�érentes orrespondant à des formestypiques de e que l'algorithme doit être apable de reproduire.3.2 Shepp-logan fa ileLa stru ture de ette mire est identique à la pré édente. Cependant, les valeurs des oe� ients d'atténu-ation ont été modi�ées a�n de fa iliter l'observation des onstrastes. Ils onsistent à augmenter de 25 ou 50fois la di�éren e entre les oe� ients de la stru ture de base et eux des autres zones.3.3 H.G.D.L'image a été inspirée de la mire utilisée dans [HGD11℄ a�n de omparer les performan es de ertainsalgorithmes de re onstru tion en tomographie. Elle est omposée de plusieurs disques qui varient en tailleet en atténuation. Cette mire permet d'évaluer les limites des algorithmes. Elle permet d'évaluer la limited'amplitude et de surfa e qu'une zone uniforme doit avoir pour être visible dans la solution.3.4 Catphan CTP401Les mires Catphan sont utilisées pour tester et ajuster la qualité des re onstru tions. Habituellement,elles servent à tester l'équipement. Après une le ture d'un de leurs atalogues 11, il a été dé idé d'in lure dansles tests le module CTP401 a�n d'obtenir un aperçu de la performan e des algorithmes sur une stru turere onnue dans le domaine. La mire utilisée est une approximation du module CTP401.4 Analyses a ompliesL'obje tif prin ipal de e do ument est de omparer l'e� a ité des algorithmes. Or, il existe plus d'unete hnique pour omparer leurs performan es. L'appro he hoisie dans e projet est divisée en deux parties.Pour ommen er, elle propose d'observer le omportement des méthodes au �l des itérations. Ensuite, elle onfronte les résultats des algorithmes a�n d'en tirer un lassement selon di�érents ritères.Cependant, ette dernière appro he in lut quelques di� ultés. Tout d'abord, la onduite et les solutionsobtenues par les méthodes sont potentiellement sensibles à la on�guration de l'a quisition, à la solutioninitiale, à l'objet analysé et à la qualité des données obtenues. Les analyses de e projet se limitent à uneseule on�guration 12. Tous les tests sont initialisés ave une image dont toutes les valeurs d'atténuationsont égales à 0.02. La se tion 3 introduit les 16 problèmes que doivent résoudre les méthodes. Soit 4 miresave ha un 4 niveaux de bruit. Cet éventail d'expérien es sera utilisé pour tenter de présenter des donnéesindépendantes des mires et/ou de la qualité des a quisitions. D'autres obsta les se présentent lorsque lessolutions des méthodes sont omparées. Il faut hoisir un ritère d'arrêt pour les algorithmes et dé�nir uneméthode pour évaluer le meilleur résultat. Notez que dans e travail, la valeur du gamma est de 0.1 pourtous les algorithmes sauf lorsque les OS sont utilisés, où il vaut 0.01. Le gamma a été hoisi après des testse�e tués sur les APT. La modi� ation apportée pour les OS est motivée par un désir de garder la même for ede pénalisation pour tous les algorithmes et le fait que l'utilisation de 10 sous-groupes divise le problème dedépart en 10 sous-problèmes. La for e du epsilon sera établie à 0.8 et le x_critique orrespondra à la pluspetite di�éren e d'atténuation non-nulle. Soit 0.05, 0.001, 0.005 et 0.089, respe tivement pour Shepp-Loganfa ile, Shepp-Logan, H.G.D et CTP401.11. Il est a essible à la page web www.phantomlab. om/do uments.php12. Voir se tion 8.3. 14

4.1 Observer l'évolution des solutions au �l des itérationsL'obje tif derrière l'observation du omportement des méthodes est de fournir su�samment d'informa-tion a�n de pouvoir les lasser. En vue d'a omplir ette tâ he, et arti le propose d'observer trois variables :le MSE 13 entre la solution à une itération donnée et la mire pixelisée, la LMH 14 de la ligne B et la varian ede la zone A 15. Les valeurs a� hées sont les moyennes des 16 tests. Les variables ont été enregistrées à toutesles 10 itérations, et e jusqu'à la 80ième itération. C'est en observant que les APT produisaient des images onvenables en 80 itérations et le désir de ne pas faire trop d'itérations qui a motivé le hoix ette borne.Notez que dans e do ument, une itération est dé�nie omme une mise à jour de la solution ourante. Don ,une appli ation de la méthode onvexe OS 10 est omptée pour 10 itérations. A�n que les résultats soientsemblables entre les algorithmes, ils sont tous ompilés aux 10 itérations. Les méthodes vont être séparéesen deux graphiques selon s'ils ont un terme de régularisation ou non, et e, pour haque variable. Ils vontêtre respe tivement nommés algorithmes pénalisés et algorithmes standards. L'ajout de _P à un nom d'al-gorithme indique qu'il fait partie des algorithmes pénalisés. Le but est d'éviter de sur harger les graphiqueset de permettre une omparaison rapide entre es deux types d'algorithmes. Les graphiques sont tous d'uneforme semblable à la �gure 6a. Chaque algorithme est représenté par une ligne brisée d'une ouleur indiquéedans la légende. Cette ourbe représente la moyenne de l'évolution de la variable en question sur les 16 testsselon les itérations.convexconvexos10Grad_ConjGrad_Conj_HZGrad_Conj_HZFObj1Grad_ConjFObj1gradientL_BFGS_BL_BFGS_BFObj1trml

0.000

0.001

0.002

0.003

0.004

0.005

0.006

0.007

0.008

10 20 30 40 50 60 70 80Nombre d'itérations

MSE

Figure 1 � MSE entre la solution ourante et la mire selon le nombre d'itérations13. Mean square error ou erreur quadratique moyenne14. La largeur à mi-hauteur est évaluée sur une ligne verti ale de 18 voxels. A�n de diminuer l'e�et du bruit sur l'évaluationdu LMH, ette ligne est la moyenne de 22 lignes de même longueur et dont ha une interse te perpendi ulairement la ligne B.L'interse tion divise les 22 lignes en deux parties égales.15. Voir la se tion 8.2 15

4.2 Comparer les solutions obtenues ave un ritère d'arrêtPour être en mesure de omparer les résultats produits par ha une des méthodes, il faut déterminer un ritère d'arrêt. Habituellement, l'obje tif prin ipal en tomodensitométrie est de re onstruire une image quia une résolution satisfaisante. Une appro he re onnue pour évaluer la résolution est de mesurer la LMH. Deplus, des analyses préliminaires montrent que les algorithmes itératifs ommen ent par produire la formegénérale de la mire 16. Don pour ette batterie de tests, les algorithmes itèrent jusqu'à e que la LMH dela ligne B soit su�samment petite. Toutefois, ertains algorithmes onvergent trop lentement vers une LMHa eptable ou même qu'ils ommen ent à roître au �l des itérations. Ainsi, les algorithmes ont été �xés àune limite de 200 itérations. Ce i orrespond à 2.5 fois plus que e qui est né essaire pour les algorithmesAPT avant d'obtenir une solution très pro he, à vue d'oeil, de leur mire respe tive. De plus, des expérien espréliminaires indiquent que les algorithmes ave un terme de régularisation ont des valeurs de LMH plusélevées. Cette di�éren e est induite par l'e�et de lissage du terme de pénalisation. Suite à d'autres tests,les hoix de LMH sont �xés à 2 voxels et à 5 voxels pour les algorithmes standard et les algorithmes_Prespe tivement. Le ritère d'arrêt étant hoisi, il ne reste plus qu'à hoisir les ritères de omparaison. L'unedes ara téristiques les plus importantes lorsque vient le temps de omparer des méthodes re onstru tionest la durée de al ul. A�n que les on lusions soient les plus générales possibles, les données a� hées orrespondront aux moyennes des 16 as disponibles. Ensuite, le MSE et la varian e dans la zone A seront al ulés pour permettre d'évaluer qualitativement les solutions obtenues. Des diagrammes à bandes, tel queprésenté en �gure 13a, vont être utilisés pour fa iliter les omparaisons. La hauteur d'une bande représente lamoyenne de la variable pour les tests présentés par ette dernière. Dans la �gure 13a, la bande à l'extrémitégau he représente la moyenne des MSE pour les 4 mires lorsque re onstruites en utilisant l'algorithme onvexeave 10 OS, et e, pour des données non bruitées. Les bandes sont triées en ordre roissant de bruit. Il s'agitdes mêmes sous-groupes pour les graphiques sur la varian e. Dans le graphique qui représente la durée dere onstru tion des algorithmes, la bande à gau he orrespond à la version standard de l'algorithme.

0.0e+00

5.0e-05

1.0e-04

1.5e-04

2.0e-04

2.5e-04

3.0e-04

3.5e-04

4.0e-04

4.5e-04

5.0e-04

Conv_os

Conv

Gradient

GC

GC*

GC_HZ

GC_HZ*

trml

L-BFGS-B

L-BFGS-B*

Algorithmes

MSE

Figure 2 � Valeurs moyennes des MSE sur les mires selon les algorithmes standard et le bruit16. Ce onstat n'est pas toujours vrai, et en onséquen e, il a fallu demander un minimum d'itérations, 15 dans ette expéri-en e, avant l'arrêt de l'algorithme.16

5 Résultats obtenusAvant d'évaluer la apa ité des algorithmes à produire une solution exa te et rapide, il faut observer omment ils se omportent généralement. Préalablement à la le ture des résultats, il faut spé i�er ertainsdétails. Les �gures nommées dans ette se tion se retrouvent toutes dans la se tion 8.7. Les algorithmes vontêtre appelés par les noms utilisés dans les légendes des �gures de ette se tion. Les notations "FObj1" ou"*" font référen e à la fon tion obje tif présentée dans la se tion 2.4.5.1 Comportement des algorithmes sur 80 itérationsMSE sur 80 itérationsLes �gures 6a et 7a montrent que les solutions ourantes des variantes du GC ommen ent loin de lasolution de départ et peinent à rattraper les autres méthodes. Cette observation n'est pas sans fondement.Ces algorithmes sont les seuls qui doivent in lure un terme de barrière. Or, lors des tests, il n'y avait passu�samment d'information pour gérer la for e de la barrière. Don , il est possible qu'il existe un meilleur hoix de ρ0 qui améliorerait leur performan e. De plus, il est possible de onstater que les performan essont pires lorsqu'un terme de régularisation est ajouté. Cette onstatation peut être expliquée par le hoixde majoration qui n'est pas optimale. Puisqu'il est di� ile de voir l'évolution des autres algorithmes dans es �gures, une �gure orrespondante, ave une é helle logarithmique a été jointe. La �gure 6b montre uneaugmentation du MSE des algorithmes standards e qui indique qu'ils s'éloignent des mires 17. Ce résultatest attendu puisque la solution optimale d'un sinogramme bruité est une image bruitée. L'ajout d'un termede régularisation permet de orriger ette divergen e (Figure 7a). Remarquez que la ourbe de onvex n'estpas visible dans es �gures. Cela est dû au fait qu'elle est trop près de la ourbe de onvexos10. Ainsi le faitd'utiliser environ 10 fois moins d'information par itération a permis d'obtenir des résultats quasi identiquesà la méthode utilisant la totalité des données. On note aussi dans la �gure 6b que les variantes de L-BFGS-Bse omportent orre tement au début, mais divergent de la solution voulue dès la 20ième itération. Cettepro édure est re onnue pour sa grande vitesse de onvergen e, e qui n'est pas né essairement voulue lorsqueles données sont bruitées. La �gure 7a montre que l'ajout d'un terme de régularisation rend ses performan eséquivalentes aux APT. En résumé, les algorithmes qui se omportent le mieux pour le MSE, ave ou sansfon tion pénalisation, sont onvexos10 et onvex.LMH sur 80 itérationsAve les �gures 8a et 9a, il est possible de voir que l'évolution de la LMH selon les itérations. Bien quela LMH semble être quasi indépendant du terme de régularisation, il onverge vers des valeurs di�érentes,soit 2 et 5 voxels respe tivement pour tous les algorithmes sauf les GC. D'ailleurs, le omportement desvariantes du GC dans les 30 premières itérations est omplètement di�érent de eux des autres algorithmes.Les hypothèses retenues, après analyse des images à haque 10 itérations, sont que la fon tion barrière esttrop forte au départ ou que sa for e n'est pas su�samment diminuée au �l des itérations. Ces hypothèses sontmotivées par le fait que les premières estimées de es algorithmes ont des oe� ients d'atténuation élevés dansdes zones où ils devraient être nuls. Pour être en mesure de départager les pro édures selon la LMH, il fautregarder les �gures 8b et 9b qui représentent un zoom des �gures pré édentes sur les meilleurs algorithmes.Tout d'abord, notez que gradient et gradient_P semblent être meilleur que leurs onfrères. Toutefois, etteavan e semble être favorisée par la limite de 80 itérations puisque L-BFGS-B et L-BFGS-BFObj1 semblentêtre en mesure de le rattraper. De plus, les méthodes onvex et onvexos10 n'ont pas eu le même genre dedépart et onvexeos10 a toujours un peu d'avan e sur onvex. Pour �nir, les APT semblent tous avoir un omportement semblable, et e, dans le as ave et sans le terme de régularisation. Cette onstatation estlogique ave le fait qu'ils ont tous plus ou moins été onstruits sur les mêmes bases. En outre, les variantesde L-BFGS-B gèrent plus di� ilement l'ajout d'un terme régulateur que les APT. Considérant la vitesse17. Ce onstat n'est pas vrai pour les variantes du gradient onjugué. Cette ontradi tion provient surement du fait qu'ellesne sont pas en ore su�samment près de leur solution. 17

de onvergen e de e dernier, il faudrait peut-être songer à diminuer la for e de la fon tion de pénalisationlorsqu'il a atteint une ertaine valeur de la fon tion obje tif.Varian e sur 80 itérationsL'analyse de l'évolution de la varian e de la zone B 18 selon les itérations on�rme ertaines des on lusionsobtenues en observant le MSE. La �gure 10a montre que lorsque les algorithmes itèrent trop longtemps, ils ommen ent à in lure du bruit dans la solution. De plus, elle appuie le fait que L-BFGS-B et L-BFGS-BFObj1 débutent t�t à reproduire le bruit. La �gure 11a, pour sa part, apporte un peu plus d'information.Ce graphique semble indiquer que les APT ont plus tendan e que les SG à re onstruire le bruit lo alement, e qui ne se voyait pas dans les graphiques de MSE. Pour �nir, la �gure 10b, qui est un zoom sur les lignesbrisées les plus basses de la �gure 10a, semble indiquer que les variantes du GC ont un ontr�le a eptabledu bruit lo alement lorsqu'il n'in lut pas un terme de régularisation. Cette dernière remarque supporte l'idéeque es algorithmes ont du potentiel et qu'une meilleure gestion de l'intera tion entre la fon tion barrière etde pénalisation, suivie d'une meilleure majoration, pourraient améliorer leurs performan es.5.2 Étalon des solutions obtenues à l'arrêtVarian e ave ritère d'arrêt sur FWHML'idée de ette sous-se tion est de présenter le meilleur algorithme lorsque le but est d'obtenir des solutionsdont les zones uniformes ont le moins de bruit possible. Si les �gures 12a et 12b sont utilisées pour omparerles méthodes, il en ressort que les algorithmes trml_P et GC_P sont les plus performants. En outre,les algorithmes ave un terme régulateur se omportent mieux que leur onfrère. Toutefois, il faut savoirque GC_P a de la di� ulté à atteindre le ritère d'arrêt. Don , il est possible qu'il n'ait simplement pas onvergé su�samment pour re onstruire le bruit. Dans une situation où utiliser un algorithme ave un termede pénalisation est dé onseillé, notez que l'algorithme trml_P est le hef de �le dans ette sous- atégorie.MSE ave ritère d'arrêt sur LMHMaintenant, les algorithmes seront lassés selon le MSE entre la solution à l'arrêt de l'algorithme et lamire originale. En observant les �gures 13a et 13b, il est possible de onstater que les résultats sont beau oupplus stables ave les méthodes pénalisées, mais que les résultats dans les as peu bruités sont meilleurs ave les pro édures standard. Don , si le niveau de bruit est relativement faible, il est avantageux de prendre uneméthode standard. Plus parti ulièrement, la �gure 13a montre qu'utiliser L-BFGS-B ou L-BFGS-BFOb1,lorsque les données sont prises dans des bonnes onditions, est un hoix judi ieux. Cependant, si des solutionsstables sont re her hées, mieux vaut prendre des algorithmes pénalisés. En outre, onvexos_P a obtenue desrésultats supérieurs et plus stables que ses onfrères pénalisés. Toutefois, il ne faut pas é arter L-BFGS-B_Pet L-BFGS-BFOb1_P qui sont très pro he de elui- i. A�n d'appuyer les résultats pré édents, la se tion8.6 montre des images obtenues ave ertains algorithmes pour la mire Shepp-Logan-easy lorsque la sour eenvoie théoriquement 1000 photons. Les re onstru tions obtenues par les algorithmes pénalisés sont �ous equi indique que le gamma hoisi était un peu trop fort.Temps de al ul ave ritère d'arrêt sur LMHLe dernier ritère de omparaison utilisé dans e projet est la durée de re onstru tion. Les donnéesobtenues pour ha un des algorithmes sont illustrées dans la �gure 14a. La �gure montre que onvexos sedistingue des autres méthodes. Ensuite, il y a les variantes de L-BFGS-B suivi de près par onvex et Gradient.Notez que la durée a� hée n'a pas été pénalisée lorsque la méthode est arrêtée avant d'atteindre la LMH visé.Toutefois, les variantes de GC sont elles qui ont le moins réussi à atteindre ette ible, e qui ne hange pasle lassement a tuel. L-BFGS-B_P et L-BFGS-BFOb1_P ont eue, eux aussi, quelques problèmes à arriver18. Voir se tion 8.2 18

à l'obje tif. Don , leurs valeurs sont sous-évaluées dans ette �gure. La �gure 14b n'in lut que les tests quiont atteint la LMH ritique. Cette �gure montre seulement que les variantes du GC utilisées dans e travailont de la di� ulté à onverger et que les algorithmes pénalisés n'atteignent pas toujours le ritère d'arrêt.Cette dernière remarque pourrait provenir de la for e du gamma.Con lusionPour terminer, un rappel sur ertains des résultats obtenus. Pour ommen er, l'utilisation de méthodesstandards devrait être limitée aux données qui sont peu ontaminées par du bruit puisque la qualité de lare onstru tion est très a�e tée par la présen e de bruit. Sinon il vaut mieux utiliser les méthodes robustes quesont les algorithmes pénalisés. De plus, malgré les réserves faites sur la onvergen e des APT utilisant des OS,les �gures de e projet semblent indiquer que es algorithmes ont un omportement égal ou même supérieuraux autres méthodes. Ensuite, les résultats de e projet démontrent en ore que les variantes de L-BFGS-Bsont très e� a es en tomodensitométrie. Toutefois, les résultats de e do ument dé onseillent de l'utilisersur des données relativement bruit ées sans terme de pénalisation. En�n, les résultats de l'implantationde variantes de gradient onjugué n'ont pas été fru tueux. Or, ils indiquent que ette méthode possède dupotentiel. Il su�rait de la retravailler sur les points notés pré édemment.6 Idée à explorerVoi i quelques idées qui seraient intéressantes d'explorer.6.1 Les paramètres de la fon tion de pénalisationLe gamma et l'epsilon présents dans la pénalisation déterminent l'e� a ité de ette dernière. Dans etravail, le hoix du gamma a été �xé à une valeur hoisie a posteriori. Or, il serait intéressant de voir si eparamètre a une in�uen e di�érente sur les performan es de re onstru tion selon les algorithmes. De plus, laformule de l'epsilon utilisé par l'auteur est onstruite dans l'idée de garder le plus petit détail d'intérêt dansun objet. Cependant, il faudrait démontrer l'e� a ité de ette dernière ou trouver une meilleure méthodepour atteindre et obje tif.6.2 La majoration de la ourbureLes majorations utilisées pour trouvePasAdmissible2 ne sont pas optimales. C'est-à-dire qu'il existe desplus petites majorations. Le fait que ∇2h(θ) soit toujours positif dans son domaine et que ette dernièresoit une fon tion onvexe permet de trouver une meilleure majoration, plus parti ulièrement dans le as deG(µ). Améliorer es majorations, surtout dans les as ave pénalisation, permettrait surement d'obtenir desrésultats satisfaisants en utilisant les variantes de gradient onjugué non linéaire.6.3 Optimisation séquentielle de sous espa esCet algorithme est re onnu pour sa grande vitesse de onvergen e dans des problèmes tel la tomographie.De plus, ette méthode a été testée dans e domaine et il semblerait que les résultats obtenus soient trèssatisfaisants pour une durée de re onstru tion ourte. Bref, il s'agit d'une pro édure qui mérite d'être priseen ompte.6.4 Approfondir l'expérien eIl y a beau oup d'avenues qui méritent d'être étudiées. Par exemple, voir si les on lusions sont semblablesdans la re onstru tion d'objet en 3 dimensions. Ensuite, les �gures montrent que ertains des algorithmesdébutent lentement. Cependant, une fois su�samment pro he de la solution, elle onverge rapidement. Or,19

l'inverse de Radon produit un bon estimé de la solution et à moindre oût. Don , il serait intéressant derefaire les analyses ave ette solution initiale et de voir si le lassement des algorithmes est modi�é.7 Remer iementsCet arti le provient d'un travail qui a été �nan é par une bourse o�erte par la Fa ulté de méde ine etdes s ien es de la santé de l'Université de Sherbrooke (FMSS), les Instituts de re her he en santé du Canada(IRSC) et le Conseil de re her hes en s ien es naturelles et en génie du Canada (CRSNG). L'auteur tient àremer ier M. Roger Le omte pour lui avoir permis de travailler sur e projet, M. Jean-pierre Dussault pourles dis ussions qui ont motivé l'ajout des SG et M. Christian Thibaudeau pour son aide dans le projet. Les ritiques de eux- i ont permis d'améliorer la réda tion de e rapport te hnique.8 Annexe8.1 Majoration utilisée dans pasAdmissible2La ourbure d'un graphe, h(θ) est évalué ave la formule suivante :∣

∣

∣

∣

∇2h(θ)

(1 + (∇h(θ))2)1.5∣

∣

∣

∣L'algorithme trouvePasAdmissible2 demande une valeur majorant ette expression pour θ ∈ [0, α[. Ces bornesproviennent du fait que la valeur α représente le plus grand theta tel que µj + θ ∗ dirj ≥ ǫ ∀j et qu'un pasdans une dire tion ne peut pas être négatif. Notez que h(θ) = F (µ+θ∗dir) où F (x) est la fon tion à optimisésans la barrière logarithme. Dans e projet, es fon tions sont L(µ) et G(µ).Notez que −∇2L(µ) > 0∀µ et que ∇2G(µ) > 0∀µAisni, (1 + (∇h(θ))2)1.5 ≥ 1⇒ ∇2h(θ)(1+(∇h(θ))2)1.5 ≤ ∇2h(θ)Rappel : L(µ) =∑i=1{−die−〈li,µ〉 − Yi〈li, µ〉} et G(µ) = 1

2 ‖ Y − lµ ‖2Σ.Majoration ave L(µ)Soit h(θ) = L(µ+ θ ∗ dir) alors ∇2h(θ) =∑

i[〈li, diri〉2e−〈li,µ〉e−θ〈li,diri〉]

∇2h(θ) =∑

i[〈li, diri〉2e−〈li,µ〉e−θ〈li,diri〉]

=∑

i|diri≥0[〈li, diri〉2e−〈li,µ〉e−θ〈li,diri〉] +∑

i|diri<0[〈li, diri〉2e−〈li,µ〉e−θ〈li,diri〉]

≤∑

i|diri≥0[〈li, diri〉2e−〈li,µ〉] +∑

i|diri<0[〈li, diri〉2e−〈li,µ〉e−θ〈li,diri〉]

≤ ∑

i|diri≥0[〈li, diri〉2e−〈li,µ〉] +∑

i|diri<0[〈li, diri〉2e−〈li,µ〉e−α〈li,diri〉]Don , K =∑

i|diri≥0[〈li, diri〉2e−〈li,µ〉] +∑

i|diri<0[〈li, diri〉2e−〈li,µ〉e−α〈li,diri〉] pour h(θ) = L(µ+ θ ∗ dir)Majoration ave G(µ)Soit h(θ) = G(µ+ θ ∗ dir) alors ∇2h(θ) =∑

i[〈li, diri〉2Yi]Don , K =∑

i[〈li, diri〉2Yi] pour h(θ) = G(µ+ θ ∗ dir)

20

Majoration ave l'ajout de la fon tion de pénalisationSoit Ψ(µ) = γ(

∑Jj

∑Kj

k κjκkwjkφ(µj − µk)). Notez que

∇2θΨ(µ+ θ ∗ dir) = γ

J∑

j

Kj∑

k

κjκkwjk

ǫ(dirk − dirkj)2

(ǫ + [(µk + θ ∗ dirk)− (µkj+ θ ∗ dirkj

)])1.5

On remarque que le domaine de ette fon tion est stri ement positif. Don , il su�t de trouver une valeur, Kpqui majorise ette expression pour obtenir une majoration des ourbures des fon tions pénalisés La majora-tion des fon tions pénalisés utilisés dans e projet est K +Kp ave K orrespondant à la fon tion obje tif ourante..La majoration hoisie est Kp = γ

(

∑Jj

∑Kj

k κjκkwjk

(dirk−dirkj )2

(ǫ)0.5

)8.2 Zone d'importan e pour l'évaluation du LMH et de la varian eL'image qui suit est la superposition des 4 mires à laquelle a été ajouté la position de la zone A et elle dela ligne B.

Figure 3 � Zone utilisée pour les tests8.3 Con�guration d'a quisitionDimension de l'image 20 m x 20 mDis rétisation 256 x 256Mode d'a quisition Géométrie à angles égauxNombre de déte teurs 520Nombre de proje tions 360Largeur angulaire du panneau des déte teurs 60◦Distan e entre la sour e et le point de rotation 28.2843 mRayon de ourbure des déte teurs 56.5686 m21

8.4 Mires

(a) Shepp-Logan (b) Shepp-Logan-easy

( ) H.G.D. (d) CTP401Figure 4 � Mires : Noir = 0 et blan = 2.5

22

8.5 Code des miresUne ligne de ode représente un objet en CTsim. Signi� ation du ode :OBJET PositionX PositionY HauteurX HauteurY AngleRotation Coe�D'aténuationH.G.D. :Stru ture de base :ELLIPSE 0 0 10 10 0 0.1Cer le extérieurELLIPSE 6.6 0 0.55 0.55 0 0.005ELLIPSE 3.3 5.5 0.55 0.55 0 0.020ELLIPSE −3.3 5.5 0.55 0.55 0 0.035ELLIPSE −6.6 0 0.55 0.55 0 0.050ELLIPSE −3.3 −5.5 0.55 0.55 0 0.065ELLIPSE 3.3 −5.5 0.55 0.55 0 0.080Cer le du milieuELLIPSE 2.2 1.1 0.033 0.033 0 0.150ELLIPSE 1.1 2.2 0.044 0.044 0 0.150ELLIPSE −1.1 2.2 0.055 0.055 0 0.150ELLIPSE −2.2 1.1 0.066 0.066 0 0.150ELLIPSE −2.2 −1.1 0.077 0.077 0 0.150ELLIPSE −1.1 −2.2 0.088 0.088 0 0.150ELLIPSE 1.1 −2.2 0.099 0.099 0 0.150ELLIPSE 2.2 −1.1 0.11 0.11 0 0.150Cer le intérieurELLIPSE 1.1 0 0.0275 0.0275 0 0.3ELLIPSE 0 1.1 0.00198 0.00198 0 0.3ELLIPSE −1.1 0 0.0022 0.0022 0 0.3ELLIPSE 0 −1.1 0.0242 0.0242 0 0.3Ligne A ELLIPSE 0 4 1.5 0.02 0 0.4CTP401 :Stru ture de base :ELLIPSE 0 0 10 10 0 0.12Segment droite :RECTANGLE 5.5 1.5 0.025 1.4 0 0.2RECTANGLE 5.5 −1.5 0.025 1.4 0 0.2Segment gau he :RECTANGLE −5.5 1.5 0.025 1.4 0 0.2RECTANGLE −5.5 −1.5 0.025 1.4 0 0.2Ligne A :ELLIPSE 0 4 0.02 3 90 0.4Segment bast :RECTANGLE 1.5 −5.5 0.025 1.4 90 0.2RECTANGLE −1.5 −5.5 0.025 1.4 90 0.2Cer le extérieur ds segments :ELLIPSE 8 0 1 1 0 0.089ELLIPSE 0 8 1 1 0 0.157ELLIPSE −8 0 1 1 0 0.436ELLIPSE 0 −8 1 1 0 −0.12 23

Cer le entre deux segments :ELLIPSE 4 4 0.25 0.25 0 0.436ELLIPSE 4 −4 0.25 0.25 0 −0.12ELLIPSE −4 −4 0.25 0.25 0 0.436ELLIPSE −4 4 0.25 0.25 0 −0.12Cer le qui forment un pentagone :ELLIPSE 0 −2 0.8 0.8 0 0.157ELLIPSE 1.90 −0.62 0.6 0.6 0 0.157ELLIPSE 1.18 1.62 0.4 0.4 0 0.157ELLIPSE −1.18 1.62 0.2 0.2 0 0.157ELLIPSE −1.90 −0.62 0.1 0.1 0 0.157Shepp-easy :Stru ture de base :ELLIPSE 0 0 10 7 90 0.2ELLIPSE 0 −0.0184 9.46 6.624 90 −0.1Grande zoneELLIPSE 2.2 0 3.1 1.1 72 −0.05ELLIPSE −2.2 0 4.1 1.6 108 −0.05ELLIPSE 0 3.5 2.5 2.1 90 0.005ELLIPSE 5.538 −3.858 0.33 2.06 −18 0.075Petite zoneELLIPSE −0.8 −6.05 0.46 0.23 0 0.05ELLIPSE 0 1 0.46 0.46 0 0.05ELLIPSE 0 −1 0.46 0.46 0 0.05ELLIPSE 0 −6.05 0.23 0.23 0 0.05ELLIPSE 0.6 −6.05 0.46 0.23 90 0.05Ligne AELLIPSE 0 4 1.5 0.02 0 0.4Shepp-logan :Stru ture de base :ELLIPSE 0 0 10 7 90 0.2ELLIPSE 0 −0.0184 9.46 6.624 90 −0.1Grande zoneELLIPSE 2.2 0 3.1 1.1 72 −0.002ELLIPSE −2.2 0 4.1 1.6 108 −0.002ELLIPSE 0 3.5 2.5 2.1 90 0.001ELLIPSE 5.538 −3.858 0.33 2.06 −18 0.0015Petite zoneELLIPSE −0.8 −6.05 0.46 0.23 0 0.001ELLIPSE 0 1 0.46 0.46 0 0.002ELLIPSE 0 −1 0.46 0.46 0 0.001ELLIPSE 0 −6.05 0.23 0.23 0 0.001ELLIPSE 0.6 −6.05 0.46 0.23 90 0.001Ligne AELLIPSE 0 4 1.5 0.02 0 0.4

24

8.6 Comparaison d'images obtenues ave quelques algorithmes(a) ConvexOs_10 (b) Convex ( ) L-BFGS-B (d) trlm(e) ConvexPOs_10 (f) Convex_P (g) L-BFGS-B_P (h) trml_PFigure 5 � Images obtenues pour di�érents algorithmes ave la mire Shepp-Logan-easy et en utilisant 1000photons. Les algorithmes standards et pénalisés ont été arrêtés lorsque la ligne B de la solution ouranteavait un LMH de 2 et de 5 respe tivement. Un pixel noir et un pixel blan représentent respe tivement un oe� ient d'atténuation de 0 et de 2.58.7 Figures utilisées dans l'analyseSoit MSE(i,j)

k le MSE entre la mire et la solution à l'itération k d'un algorithme appliqué sur un sino-gramme de la mire i ave un niveau de bruit j 19. Soit Var(i,j)k et LMH(i,j)k respe tivement la varian e de lazone A et la largeur à mi-hauteur de la ligne B 20 de la solution à l'itération k d'un algorithme appliqué surun sinogramme de la mire i ave un niveau de bruit j.Alors, MSE∗

k, Var∗k et LMH∗k sont respe tivement les moyennes des MSE(i,j)

k , des Var(i,j)k et des LMH(i,j)kpour les 4 mires ave ha un des 4 niveaux de bruit.Soit MSE(i,j) et Var(i,j) respe tivement MSE(i,j)

k∗ et Var(i,j)k∗ où k∗ représente l'itération à laquelle lasolution ourante a atteint le ritère d'arrêt. Soit Re on_Time(i,j) le temps né essaire pour atteindre le ritère d'arrêt d'un algorithme appliqué sur un sinogramme de la mire i ave un niveau de bruit j.Alors, MSE∗,j et Var∗,j sont respe tivement la moyenne des MSE(i, j) et la moyenne des Var(i,j) sur les4 mires à un niveau de bruit j. L'ordre, de gau he à droite, des niveaux de bruit est noNoise, 10000 , 1000 et 100 21. Re on_Time∗ est la moyenne des Re on_Time(i,j) pour les 4 mires ave ha un des 4 niveauxde bruit.19. Voir se tion 320. Voir se tion 8.221. Voir la se tion 325

convexconvexos10Grad_ConjGrad_Conj_HZGrad_Conj_HZFObj1Grad_ConjFObj1gradientL_BFGS_BL_BFGS_BFObj1trml

0.000

0.001

0.002

0.003

0.004

0.005

0.006

0.007

0.008

10 20 30 40 50 60 70 80Nombre d'itérations

MSE

(a) é helle standard 10

10

10

10

-5

-4

-3

-2

10 20 30 40 50 60 70 80Nombre d'itérations

MSE

(b) é helle logFigure 6 � MSE∗k à haque 10 itérations pour ha un des algorithmes standards

convex_Pconvex_Pos10Grad_Conj_PGrad_Conj_P_HZGrad_Conj_P_HZFObj1Grad_Conj_PFObj1gradient_PL_BFGS_B_PL_BFGS_B_PFObj1trml_P

0.000

0.001

0.002

0.003

0.004

0.005

0.006

0.007

0.008

10 20 30 40 50 60 70 80Nombre d'itérations

MSE

(a) é helle standard 10

10

10

10

-5

-4

-3

-2

10 20 30 40 50 60 70 80Nombre d'itérations

MSE

(b) é helle logFigure 7 � MSE∗k à haque 10 itérations pour ha un des algorithmes pénalisés.

26

convexconvexos10Grad_ConjGrad_Conj_HZGrad_Conj_HZFObj1Grad_ConjFObj1gradientL_BFGS_BL_BFGS_BFObj1trml

0

�

10

1�

�0

10 20 30 40 �0 "0 #0 $0%ombre d&itérations

LMH en pixel

(a) é helle standard 1

2

3

4

5

10 20 30 40 50 60 70 80Nombre d'itérations

LMH en pixel

(b) Zoom inFigure 8 � LMH∗k à haq ue 10 itérations pour ha un des algorithmes standards

convex_Pconvex_Pos10Grad_Conj_PGrad_Conj_P_HZGrad_Conj_P_HZFObj1Grad_Conj_PFObj1gradient_P_pasAdmL_BFGS_B_PL_BFGS_B_PFObj1trml_P

0

5

10

15

20

10 20 30 40 50 60 70 80Nombre d'itérations

LMH en pixel

(a) é helle standard 3.5

4.0

4.5

5.0

5.5

6.0

6.5

7.0

7.5

20 30 40 50 60 70 80Nombre d'itérations

LMH en pixel

(b) Zoom inFigure 9 � LMH∗k à haque 10 itérations pour ha un des algorithmes pénalisés

27

convexconvexos10Grad_ConjGrad_Conj_HZGrad_Conj_HZFObj1Grad_ConjFObj1gradientL_BFGS_BL_BFGS_BFObj1trml

0.0000

0.0001

0.0002

0.0003

0.0004

0.0005

0.0006

10 20 30 40 50 60 70 80Nombre d'itérations

Variance

(a) é helle standard 0.0e+00

2.0e-05

4.0e-05

6.0e-05

8.0e-05

1.0e-04

1.2e-04

10 20 30 40 50 60 70 80Nombre d'itérations

Variance

(b) Zoom inFigure 10 � Var∗k à haque 10 itérations pour ha un des algorithmes standardsconvex_Pconvex_Pos10Grad_Conj_PGrad_Conj_P_HZGrad_Conj_P_HZFObj1Grad_Conj_PFObj1gradient_PL_BFG�_B_PL_BFG�_B_PFObj1tr��_P

0�0e 00

!�0e�0�

��0e�0�

��0e�0�

��0e�0�

1.0e�0�

1.2e-0�

1.4e-0�

1.6e-0�

10 !0 '0 40 �0 �0 (0 �0

)ar�ance

*o�bre d+��érations(a) é helle standardFigure 11 � Var∗k à haque 10 itérations pour ha un des algorithmes pénalisés28

10

10

10

10

10

10

-7

-6

-5

-4

-3

-2

Algorithmes

Va

�

iance

Conv

Conv_os

GC

GC_HZ

GC_HZ*

GC*

Gradient

L-BFGS-B

L-BFGS-B*

trml(a) LMH ritique : 2 10

10

10

10

10

-8

-7

-6

-5

-4

Algorithmes

Va

�

iance

Conv

Conv_os

GC

GC_HZ

GC_HZ*

GC*

Gradient

L-BFGS-B

L-BFGS-B*

trml(b) LMH ritique : 5Figure 12 � Var∗,j selon les algorithmes pénalisés et le bruit représenté ave une é helle log. Les algorithmessont arrêtés lorsque la solution ourante a atteint la LMH ritique ou lorsque le nombre d'itérations dépasse200. Les ouleurs de gau he à droite représentent respe tivement noNoise, 10000 , 1000 et 100 .

0.0e+00

5.0e-05

1.0e-04

1.5e-04

2.0e-04

2.5e-04

3.0e-04

3.5e-04

4.0e-04

4.5e-04

5.0e-04

Conv_os

Conv

Gradient

GC

GC*

GC_HZ

GC_HZ*

trml

L-BFGS-B

L-BFGS-B*

Algorithmes

MSE

(a) LMH ritique : 2 0.0e+00

5.0e-05

1.0e-04

1.5e-04

2.0e-04

2.5e-04

3.0e-04

3.5e-04

4.0e-04

4.5e-04

5.0e-04

Conv_os

Conv

Gradient

GC

GC*

GC_HZ

GC_HZ*

trml

L-BFGS-B

L-BFGS-B*

Algorithmes

MSE

(b) LMH ritique : 5Figure 13 � MSE∗,j selon les algorithmes pénalisés et le bruit représenté ave une é helle log. Les algorithmessont arrêtés lorsque la solution ourante a atteint la LMH ritique ou lorsque le nombre d'itérations dépasse200. Les ouleurs de gau he à droite représentent respe tivement noNoise, 10000 , 1000 et 100 .29

0

50

100

150

200

250

300

350

400

450

500

Temps(secondes)

Conv

Conv_os

GC

GC_HZ

GC_HZ*

GC*

Gradient

L-BFGS-B

L-BFGS-B*

trml Algorithmes(a) Re on_Time∗ sur tous les tests 0

50

100

150

200

250

300

350

400

450

500

Algorithmes

Temps(secondes)

Conv

Conv_os

GC

GC_HZ

GC_HZ*

GC*

Gradient

L-BFGS-B

L-BFGS-B*

trml(b) Re on_Time∗ sur les tests qui ont atteint la LMH ritiqueFigure 14 � Re on_Time∗ selon les algorithmes et l'in lusion d'un terme de régularisation. Les algorithmesont été arrêtés lorsque la LMH de la solution ourante atteint la valeur ritique ou lorsque le nombre d'itéra-tions dépasse 200. La valeur ritique pour les algorithmes standards(Bleu) et les algorithmes pénalisés(Cyan)sont respe tivement de 2 et de 5.Référen es[CMI09℄ É. Chouzenoux, S. Moussaoui & J. Idier, "A majorize-minimize line sear h algorithm for barrierfun tion", version 4, 31 p., 2009.[D95℄ J-P. Dussault, "Numeri al stability and e� ien y of penalty algorithms", SIAM Journal on Numeri alAnalysis, Vol 32, No. 1, pp. 296-317, 1995.[FR96℄ J.A. Fessler & W.L. Rogers, "Resolution properties of regularized image re onstru tion methods",Te hni al Report No. 297, 25 p., 1996.[H80℄ G.T. Herman, "Image re onstru tion from proje tions : The fundamentals of omputerized tomogra-phy", IEEE Transa tions on Signal Pro essing, vol. 41, no 2, pp. 534-548, 1980.[HGD11℄ B. Hamelin, Y. Goussard & J-P. Dussault, "Comparison of optimization te hniques for regularizedstatisti al re onstru tion in x-ray tomography", IEEE IPTA, pp. 87-91, 2011.[HZ05℄ W.H. Hager & H. Zhang, "A survey of nonlinear onjugate gradient methods", 21 p. , 2005.[KB05℄ J.S. Kole & F.J. Beekman, "Evaluation of the ordered subset onvex algorithm for one-beam CT",Physi s in Medi ine and Biology, pp. 613-623, 2005.[KS88℄ A.C. Kak & M. Slaney, "Prin iples of Computerized Tomographi Imaging", IEEE, 327 p., 1988.[LC84℄ K. Lange & R. Carson, "EM re onstru tion algorithms for emission and transmission tomography",Journal of Computer Assisted Tomography pp. 306-316 1984.[LF95℄ K. Lange & J.A. Fessler, "Globally onvergent algorithms for maximum a posteriori transmissiontomography", IEEE Trans on Image Pro essing pp. 1430-1438, 1995.[RP86℄ J. Radon & P.C. Parks, (translator), "On the determination of fun tions from their integral valuesalong ertain manifolds", IEEE Transa tions on Medi al Imaging 5, pp. 170�176, 1986.[SB93℄ K. Sauer, & C. Bouman , "A lo al update strategy for iterative re onstru tion from proje tions,"IEEE Transa tions on Signal Pro essing, Vol. 41, no. 2, pp. 534-548, Feb. 1993.30