Antonio Machado

ESIEE Laboratoire D'informatique Gaspard-Monge

Régis Vaillant

Laurent Najman

Image processing algorithms for the visualization of interventional devices in X-ray fluoroscopy.

by Vincent Bismuth Stent implantation is the most common treatment of coronary heart disease, one of the major causes of death worldwide. During a stenting procedure, the clinician inserts interventional devices inside the patient's vasculature. The navigation of the devices inside the patient's anatomy is monitored in real-time, under X-ray fluoroscopy.

Three specific interventional devices play a key role in this procedure: the guide-wire, the angioplasty balloon and the stent. The guide-wire appears in the images as a thin curvilinear structure. The angioplasty balloon, that has two characteristic marker-balls at its extremities, is mounted on the guide-wire. The stent is a 3D metallic mesh, whose appearance is complex in the fluoroscopic images. Stents are barely visible, but the proper assessment of their deployment is key to the procedure.

I want to thank:

Isabelle Bloch who has been president of the jury which was both an honor and a motivation for me.

The "rapporteurs" of this thesis: Nassir Navab and Grégoire Malandain for kindly accepting this demanding role. Living up to your expectations

The objective of the work presented in this thesis is twofold. On the first hand, we aim at designing, studying and validating image processing techniques that improve the visualization of stents. On the second hand, we study the processing of curvilinear structures (like guide-wires) for which we propose a new image processing technique. We present algorithms dedicated to the 2D and 3D visualization of stents. Since the stent is hardly visible, we do not intend to directly locate it by image processing means in the images.

The position and motion of the stent are inferred from the location of two landmarks: the angioplasty balloon and the guide-wire, which have characteristic shapes. To this aim, we perform automated detection, tracking and registration of these landmarks.

The cornerstone of our 2D stent visualization enhancement technique is the use of the landmarks to perform motion compensated noise reduction. We evaluated the performance of this technique for 2D stent visualization over a large database of clinical data (nearly 200 cases). The results demonstrate that our method outperforms previous state of the art techniques in terms of image quality. A comprehensive validation confirmed that we reached the level of performance required for the commercial introduction of our algorithm. It is currently deployed in a large number of clinical sites worldwide.

The 3D stent visualization that we propose, uses the landmarks to achieve motion compensated tomographic reconstruction. We show preliminary results over 22 clinical cases.

Our method seems to outperform previous state of the art techniques both in terms of automation and image quality.

The previous stent visualization methods involve the segmentation of the part of the guide-wire extending through the stent. We propose a generic tool, called the Polygonal Path Image (PPI), to process such curvilinear structures. The PPI relies on the concept of locally optimal paths. One of its main advantages is that it unifies the concepts of several previous state of the art techniques in a single formalism. Moreover the PPI enables to control the smoothness and the length of the structures to segment.

Its parameterization is simple and intuitive. In order to fully benefit from the PPI, we propose an efficient scheme to compute it. We demonstrate its applicability for the task of automated guide-wire segmentation, for which it outperforms previous state of the art techniques.

Keywords: stent, guide-wire, cardiology, image processing, Xray. par Vincent Bismuth La pose de stent est l'option de traitement la plus courante de la maladie coronarienne, l'une des principales causes de mortalité dans le monde. Lors d'une procédure de pose de stent, le médecin insère des outils chirurgicaux dans le réseau vasculaire du patient. La progression de ces outils à l'intérieur du corps est suivie en temps réel sous uoroscopie par rayons X. Trois outils, en particulier, jouent un rôle crucial dans la procédure : le guide, le ballon d'angioplastie et le stent. Le guide apparait dans les images sous la forme d'une structure curviligne. Le ballon, monté sur le guide, est équipé de deux marqueurs radio-opaques às e se x t r émités. Le stent est un maillage métallique qui se projette en une forme complexe dans les images uoroscopique. Le stent, dont le bon déploiement est essentiel au succès du geste médical, est souvent très difficilement visible dans les images.

UNIVERSITE PARIS EST

Résumé

Les travaux présentés dans cette thèse poursuivent un double objectif. Il s'agit d'une part, de concevoir, d'étudier et de valider des techniques de traitement d'image visant àa m éliorer la visualisation des stents. D'autre part, nous étudions le traitement des structures curvilignes (comme les guides) pour lesquelles nous proposons un nouvel outil.

Nous présentons des algorithmes de traitement d'image dédiés à la visualisation 2D et 3D des stents. Nous sommes amenés, dans ce but, àd étecter, suivre et recaler, de manière complètement automatique, les outils nécessaires à la pose de stent que sont le guide et le ballon.

Le stent étant à peine visible dans les images, nous ne cherchons pas à le localiser directement à l'aide de techniques de traitement d'images. La position et le mouvement du stent sont déterminées par nos algorithmes àp a r t i rd ec e l l e sd ed e u xa m e r s : l eg u i d e et le ballon qui ont des formes caractéristiques. Nous effectuons donc, dans ce but, la détection, le suivi et le recalage de ces amers, et ce de manière complément automatique.

Le coeur de notre méthode de visualisation des stents en 2D réside dans l'utilisation des amers pour effectuer un débruitage compensé en mouvement. Nous avons évaluél ape rformance des ces outils pour la visualisation des stents en 2D, sur une large base de près de 200 cas cliniques. Il en ressort que notre méthode surpasse les méthodes utilisées jusqu'ici sur le plan de la qualité image. La validation exhaustive que nous avons mené, a confirmé que nous avions atteint un niveau compatible avec son introduction commerciale.

Le logiciel qui en résulte est désormais installé sur un grand nombre de sites cliniques, où il est régulièrement utilisé. La méthode de visualisation 3D des stents que nous proposons utilise les amers pour effectuer une reconstruction tomographique compensée en mouvement. Nous exposons des résultats préliminaires sur une base de 22 cas cliniques.

Il semble que notre méthode surpasse les méthodes précédemment employées aussi bien du point de vue de la qualité image que de l'automatisation.

Les méthodes de visualisation des stents que nous proposons s'appuient sur la segmentation de la portion du guide qui traverse le stent. Nous proposons un nouvel outil pour le traitement de telles structures curvilignes que nous appelons : l'Image de Chemins Polygonaux (acronyme PPI en anglais). Cet outil repose sur la notion de chemin localement optimal. L'un des principaux avantages du PPI est d'unifier dans un même cadre différents concepts pré-existants. De plus, il permet de contrôler la régularité et la longueur des structures à traiter avec une paramétrisation simple et intuitive. Afin de tirer pleinement parti des performances du PPI nous proposons un schéma algorithmique efficace pour le calculer. Nous illustrons ses utilisations pour la segmentation automatique de guide ou il surpasse les techniques existantes.

Mots-clefs: stent, guide, cardiologie, traitement d'image, rayons X. with an Innova 2100 Xray system (GE) ................... 1.5 Quantitative coronary analysis allows the clinician to estimate the percentage of lumen reduction induced by the presence of the stenosis (Quantitative Analysis Software developed by Pie Medical Imaging BV c ;p i ctures courtesy by Pie Medical Imaging BV. Reproduced from [esa11]). .. 1.6 Balloon angioplasty [START_REF] Nih | this image is in the public domain because it contains materials that originally came from the national institutes of health[END_REF] and stenting [START_REF] Nih | this image is in the public domain because it contains materials that originally came from the national institutes of health[END_REF] procedures. ..... 1.7 Illustration of a bypass [NIH10a]. ....................... 1.8 Angiograms of Dotter's 1st catheter patient, Laura Shaw: A) before transluminal dilation of the left superficial femoral artery, B) immediately after dilation, and C) 3 weeks after the procedure (image from [START_REF] Payne | Charles theodore dotter: The father of intervention[END_REF]). .... 1.9 Visualization of a right coronary artery under before and during contrast media injection. We note that in the absence of contrast the medical tools inside the artery are visible but not the artery itself. When contrast media in injected, the artery is visible but the medical tools become hardly visible (images obtained on an Innova 2100 system of GE healthcare). .. 1.10 Various popular coronary stents. From left to right: Cypher [Hos07],

List of Figures

Endeavor [ptc09], Taxus Liberte [DC09], Xience V [START_REF]Drug-eluting stents help patients avoid amputation[END_REF]. Note that the metal meshes are quite different from one stent to another and can be rather complex. ............................... 1.11 In stent restenosis (image from [START_REF]stentrestenosis02.jpg -what are the risks of coronary angioplasty[END_REF]). This complication was common with bare metal stents. It decreased very significantly with the introduction of drug eluting stents. ...................... 1.12 Innova system -GE Healthcare ........................ 1.13 Calcification are very well visualized with Computed Tomography [START_REF]Brakes on cta and mra[END_REF].

They appear in white, around the lumen of the artery. ........... 1.14 Stent cross section in OCT versus conventional angiography [START_REF] Loder | Taking a closer look inside blood vessels[END_REF] rotational acquisition (top row: original images -bottom row: segmented interventional tools). Observe that the markers exchange their relative positions as a result of the gantry rotation. ................. 1.25 Top left: an extract from a cine image depicting a set of smooth paths between two endpoints. Top center: A clinical image corrupted with a high level of noise. Top right: guide-wire segmented with our method between the two markerballs. Bottom left: A clinical image depicting a guide-wire. Bottom center: 3 candidate curves (note that the blue one is well aligned with the guide-wire centerline whereas the red and green ones are not). Bottom right: The three averaged profiles (same color code as bottom center). Abscissa is the signed distance to the curve and ordinate is the pixel intensity. Only the profile of the blue curve that is aligned with the guide-wire exhibits a marked minimum at its center. ....... standard contrast enhancement techniques, which may be considered a form of DSE. The resulting stent visualization is substantially inferior to that produced with a dedicated technique, as shown on the right. ..... 2.5 Study of the impact of the misregistration error. Image after the application of DSE with various misregistration magnitudes. The images were produced by registering thirty frames with a registration error following a uniform distribution and averaging the frames. The misregistration magnitude is indicated in pixel units below each image. .......... 2.6 Schematic illustration of the limitations of the linear, marker-ball based registration realized with an image processing software for explanatory purpose (not necessarily geometrically exact). The two top images are two images of a same stent. Bottom is the marker-ball based registration. Although the two marker-balls are accurately registered, the stent, that underwent a non-linear deformation is not accurately registered. The guide-wire that supports the marker-balls is also undergoing a non-linear deformation. We use it as additional landmark in our nonlinear registration. The stent image is derived from a photo of a Cypher coronary stent [tim05] (a) Although the landmarks are well registered and sharp, the stent struts do not appear and the upper part of the stent is blurry. (b) Case of two stents at a bifurcation. Only the marker-balls and the guide-wire supporting them are used as registration landmarks. Therefore, the stent in the side branch is not registered as accurately as the one in the main branch and is blurrier. traction is satisfactory but not perfect. We can observe in the upper section of the stent a residual guide-wire signal. Our hypothesis to explain it is that the guide-wire centerline estimation is less reliable in this area where the stent border and the guide-wire are very close one to another. 97 3.17 (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction. The stent-signal is rather weak compared to the intensity of the guide-wire, therefore subtraction improves one's ability to assess the general shape of the stent. ........................... 3.18 (a) input image. (b) guide-wire subtracted image. The subtraction is not perfect in the lowest part of the stent where one can notice an unusually white signal. However, on the upper part of the stent, the subtraction drives the attention of the reader on a dark area. Its presence is also visible (but far less conspicuous) in the non-subtracted image. This area is likely to be a large calcification that can have impacted stent deployment in a plane perpendicular to the one of the image. List of figures xxiii 4.15 A situation where affine registration is not optimal. Between images (a) and (b) we assume that the marker segment has undergone a rotation out of the image plane, around the (Ox) axis. We illustrate in red the marker segment of image (a). Note the change in the marker segment length between figures (a) and (b). The change in distance between the markers in images (a) and (b) is compensated by a global scaling with the similarity transform that modifies the (nearly unchanged) diameter of the stent (image (c)). In image (d) a stretching along the axis of the markers but not perpendicularly keeps unchanged the stent diameter while registering the markers. In these two last images the registered markers are illustrated in green. ........................1 4.16 Motion compensated images. Left and center: Two registered images in a phase where the gantry is static. Right: Registration of the manually segmented stents. Top row state of the art similarity transform, bottom row linear diameter preservation registration. Observe that the registered stents match better with the proposed registration than with the classical affine one (as indicated by the arrows). ....................1 4.17 Illustration of the non-linear registration and of the guide-wire subtraction on three images taken at different instants during a rotational acquisition. We represent the segmented guide-wire in green, and the projected 3D guide-wire model in red. Top row: original images. Bottom row: registered and guide-wire subtracted images. Left: We can observe the discontinuity of the guide-wire based registration far from the segmented guide-segment (notice the "broken guide-wire effect"). Middle: the projected and detected guide-wires occasionally match very closely, typically once per heart beat, as in this example. Right: notice the difference in curvature between the projected and detected guide-wires. ......... Observe that the inflation of the balloon is (i) beneficial to the quality of the enhanced stent and that (ii) prevents the guide-wire from overlapping with the stent border. This illustration case is the one where the impact of balloon inflation is the most striking in our database. ....1

5.27

We illustrate here the result of path pruning with x = 50%. We can observe that among the small number of paths selected, the ones illustrating the guide-wire are present. Further path selection, based on their cost for instance can be performed to better isolate the guide-wire. .........1 5.28 We illustrate here the result of path pruning with x = 50% and tortuosity constraints (top 0.6, bottom 0.75). We can observe how the conjuction of pruning and constrained path smoothness help segment the guide-wire. . 164 5.29 Extract of ϑ(P) obtained from the X-ray image of a guide-wire. The arrow resulting from direction estimation give the direction of the closest curvilinear structure. Note that on the structure itself the direction of the arrow is not relevant (the linear structure can be found in both opposite directions), but the orientation is accurate. .................1 5.30 Counter example to the triangular inequality when path curvature is bounded. The "distance" between two points is defined as the minimal cost of all the paths joining two points, under the constraint that the maximum curvature of the paths shall not exceed a given bound. We build a particular potential cost image for this counter example, where: all the image has cost +∞ except the three paths that are drawn. Let L AB be the length of the path from A to B. We assign to each pixel on this path the cost 3/L AB . Consequently the cost of the whole path is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB .T h ec o s t of each of these two paths is thus 1. Then, we note that the only finite cost path from A to B, is the one that is drawn (see Fig.

Glossary

angina pectoris commonly known as angina, is severe chest pain due to ischemia (a lack of blood, hence a lack of oxygen supply) of the heart muscle, generally due to obstruction or spasm of the coronary arteries (the heart's blood vessels). Coronary artery disease, the main cause of angina, is due to atherosclerosis of the cardiac arteries. The term derives from the Latin angina ("infection of the throat") from the Greek ankhone ("strangling"), and the Latin pectus ("chest"), and can therefore be translated as "a strangling feeling in the chest". Worsening ("crescendo") angina attacks, sudden-onset angina at rest, and angina lasting more than 15 minutes are symptoms of unstable angina (usually grouped with similar conditions as the acute coronary syndrome) (from http: //encyclopedia.thefreedictionary.com/Angina+pectoris). 1

angiogenesis The process of developing new blood vessels (from http://www.medterms.

com/script/main/art.asp?articlekey=6597). 27

angiogram or angiography is a medical imaging technique used to visualize the inside, or lumen, of blood vessels and organs of the body, with particular interest in the arteries, veins and the heart chambers. This is traditionally done by injecting a radio-opaque contrast agent into the blood vessel and imaging using X-ray based techniques such as fluoroscopy. The word itself comes from the Greek words angeion, "vessel", and graphein, "to write or record". The film or image of the blood vessels is called an angiograph, or more commonly, an angiogram (from http://en.wikipedia.org/wiki/Angiography). 4, 9, 15 angiographic catheter also called injection catheter. A catheter through which a contrast medium is injected for visualization of the vascular system of an organ (from http://medical-dictionary.thefreedictionary.com/Angioplasty,+balloon). 9

atherosclerosis (also known as arteriosclerotic vascular disease or ASVD) is a condition in which an artery wall thickens as the result of a build-up of fatty materials such as cholesterol. The purpose of this thesis is to study ways of imaging coronary stents with Xray fluoroscopy, in order to assess qualitatively and quantitatively their shape and deployment.

In this introductory chapter, we first present coronary heart disease and its most common treatment, stenting, in Section 1.1. Then we expose the clinical facts motivating the need to visualize stents during the course of an intervention and we summarize the ultimate needs of the clinicians regarding stent visualization (Section 1.2). Section 1.3 covers the limitations of the existing stent visualization techniques and grounds the need for new ones. The technical context of this thesis is described in Section 1.4. Section 1.5 presents the overall structure of the thesis, describing how each chapter answers to the identified needs and limitations. Our main technical contributions are summarized in Section 1.6. Finally, Section 1.7 covers some perspectives for the near future of the cathlab.

Pathology and treatment

This section aims at giving to the reader a brief overview of the clinical context and introducing the terms that are commonly met in the field of interventional cardiology.

We introduce the cardiovascular system, then we explain the pathology of atheromatous stenosis and its potential consequences: angina pectoris and myocardial infarction.

Finally we present the associated treatment options.

The cardiovascular system

The cardiovascular system is in charge of the circulation of blood through the entire body providing oxygen and nutrient supply to the organs. It is constituted of the heart which similarly to a pump is responsible for the circulation of the blood, and of the arteries, veins and capillaries through which blood is carried. The blood circulates through the body inside two circuits that interconnect at the level of the heart (Fig. 1.1):

• the pulmonary circulation which carries oxygen-depleted blood away from the heart, to the lungs, and returns oxygenated blood back to the heart at the entry of the systemic circulation.

• the systemic circulation which carries oxygenated blood away from the heart to the body, and returns deoxygenated blood back to the heart at the entrance of the pulmonary circulation.

Just like every other organ, the heart has its own vascularisation system formed of veins and arteries. The coronaries arteries, whose name comes from their location as a crown around the heart, are irrigating, thus feeding the heart muscle called the myocardium. The coronary arteries are formed of two distinct coronary trees, the right one and the left one that both originate from the beginning of the aortic root immediately above the aortic valve. The left coronary artery that is generally more developed than the right one, divides into two main branches: the left anterior descending (LAD) and the left circumflex artery (LCX). The Figure 1.2 depicts the coronary arteries.

The coronary arteries are classified as end circulation, since they represent the only source of blood supply to the myocardium: there is very little redundant blood supply, which is why blockage of these vessels can be so critical [Wik11a]. We will see in the next section that these relatively narrow vessels are commonly affected by a pathology named atherosclerosis and can see their diameter drastically reduced, causing angina or heart attack. Each beating of the heart produces the following chain of events, called heart cycle:

• atrial systole, the atria contract and eject blood into the ventricles.

• ventricular systole contraction of the ventricles injecting blood into the circulatory system. The atria, now relaxed are being filled with blood.

• diastole, relaxation of all parts of the heart allowing ventricles to be filled.

The atheromatous stenosis and the myocardial infarction

Coronary heart disease (CHD) and its consequences are one of the major world public health issues, as we can understand from the following few figures on its epidemiology.

Treatment options

The main treatment options share some similarities for the angina and the acute myorcadial infarction. There are four axes in these therapies: drug administration, minimally invasive procedures, bypass, and risk factor management.

Drug administration

The drugs commonly involved in the treatment of the angina are inspired by the following strategy: • Reduce the needs in oxygen of the heart, slow its rate and decrease arterial pressure (Beta blockers and calcium channel blockers).

• Help dilate the coronary arteries to improve the blood supply (vasodilators drugs like nitrates).

• Prevent the formation of blood clots (Antiplatelet/anticoagulant drugs such as aspirin). If the patient is presumed to have an occlusive thrombosis (typically in case of myocardial infarction) a specific drug is envisaged called thrombolysis that dissolves the thrombus.

Angioplasty

The angioplasty, or Percutaneous Coronary Intervention (PCI) is a minimally invasive procedure that consists in introducing a balloon into the clotted artery and inflating it to dilate the artery. A fine mesh of wire, called a stent can additionally be placed inside the artery as a permanent endoprothesis to reduce the risk of future restenosis.T h e main steps of these procedures are illustrated in Fig. 1.6. A more detailed description of this therapy will be given in section 1.2 since it is the procedure of interest for our work.

Coronary artery bypass graft (CABG)

CABG is a surgical procedure performed to relieve angina and reduce the risk of death from coronary artery disease. Arteries or veins from elsewhere in the patient's body are grafted to the coronary arteries to bypass atherosclerotic narrowing and improve the blood supply to the coronary circulation (Fig. 1.7).

Risk factor Management

None of the exposed treatment options actually removes or reduces the plaques that lie inside the arteries. In the case of the CABG they are bypassed and in the case of the angioplasty they are pushed away from the lumen. If the risk factors are not taken into account by the patient it is highly likely that the arteries will get clotted again.

The important risk factors fall into two categories, the uncontrollable ones, and the controllable ones. In the first category fall age, (male) sex and heredity. The second [START_REF] Maccia | Niveaux de référence et évaluation dosimétrique des patients[END_REF] 57 Gy.cm 2 , 1270 images Xray dose of an angioplasty [START_REF] Maccia | Niveaux de référence et évaluation dosimétrique des patients[END_REF] 94 Gy.cm

A short presentation of interventional cardiology

A very short historical perspective [START_REF] Garg | Coronary stents: Current status[END_REF] on interventional cardiology will enable us to introduce all the concepts necessary to understand the technique as it is performed nowadays (more information about this field can be found in [START_REF] Redwood | Oxford Textb o ok of Interventional Cardiology[END_REF]). Interventional cardiology is a young, successful, rapidly changing field. The history of interventional cardiology has been forged by repeated loops consisting in identifying the major limitations of the current technique and developing technological innovations to overcome them. The main steps of this recent history, that build the clinical context of the current PhD thesis are the following. First Angiography in 1964 by Charles Theodore Dotter and Melvin P. Judkins: contrast media was injected into vessels to make them visible on radiographs (Fig. 1.8 and 1.9). In 1977 Andreas Gruntzig performed the first balloon coronary angioplasty, it was the birth of interventional cardiology (Fig. We note that in the absence of contrast the medical tools inside the artery are visible but not the artery itself. When contrast media in injected, the artery is visible but the medical tools become hardly visible (images obtained on an Innova 2100 system of GE healthcare).

The cathlab

The PCI procedures take place in a dedicated interventional room called catheterization lab, or simply cathlab. At the center of the cathlab is the imaging system, in our case a system from the Innova series manufactured by GE (Innova 2100, or 2100 IQ for instance

[Ele11]). The imaging of the coronary arteries (coronarography) and the deployment of stents (PCI) are minimally invasive techniques monitored under Xray fluoroscopy with the Innova system. At the demand of the clinician, real-time Xray video is produced at 7.5, 15 or 30 images per second. Any part of the body can be imaged, under virtually any angle, thanks to the positioning capabilities of the system: a moving table (3 degrees of freedom in translation), on which the patient lies, and an imaging chain (3 degrees of freedom in rotation) that can be positioned around the patient. The images are displayed on suspended monitors, right in front of the clinician. Fig. 1.12 shows the Innova system, and the positioning of the patient, the clinician and the screens. The system also offers the possibility to spin the image chain around the patient, in order to perform 3D reconstructions for instance. There are two main types of image acquisition commonly available: cine (or graphy) and fluoro (also called fluoroscopy, or scopy). The cine images are acquired at a dose level 5 to 10 times superior to fluoro. Therefore they have better image quality. They are automatically stored on the system and are used for diagnosis and documentation of the stages of the treatment. Fluoro images, of lower image quality and dose, are used for the longest parts of the intervention to monitor the medical tools inside the patient body. They are not systematically stored. In some cases, when cine is required to document a given stage of the intervention, it may be replaced by fluoro when it is stored (on request of the clinician). The appropriate usage of both and of the multiple dose customization capabilities of the system enables performing interventions according to the ALARA principle that rules the image quality/dose trade-off: Xray dose must be As Low As Reasonably Achievable.

The technical developments presented in the following chapters are typically designed to be potential features of cathlab systems.

Figure 1.12: Innova system -GE Healthcare

Breakdown of a stenting procedure

The stenting procedure follows a set of pre-defined steps. We detail them, and for each of them express what are the challenges met by the clinician. We refer to this breakdown in several chapters to explain which clinical need we are addressing, and how the workflow is possibly modified by the proposed solution.

In practice, the interesting part of the procedure starts when the clinician inserts an injection catheter at the entry of the coronary artery to produce reference images of the pathology. These images, illustrating the vessels, help the clinician decide upon the treatment strategy. If stenting is selected, he/she will keep this reference image on one of his screens to help him guide his gesture all along the procedure. The imaging chain typically stays in the same position until the end of the treatment phase. Then a guide-wire is inserted down to the distal end of the artery. The crossing of the lesion may present some difficulties depending on its characteristics. This guide-wire will serve as support to slide all the necessary medical tools. A balloon is slided down to the lesion and inflated at high pressure (typically 12atm). Then a stent, mounted on a balloon is slided down to the lesion and inflated. Finally, the balloon is removed and a record acquisition is performed with contrast injection to verify that the lesion is properly treated. To complete the check the same injection is performed again in a perpendicular These facts emphasis on the utility of visualizing the stent and assessing its deployment in real time in the cathlab at the time of the procedure. This is the core clinical need addressed by of all the image processing applications that are presented in the following chapters of this thesis.

A word about calcifications

Some lesions (stenoses) when aging can develop calcific layers (Fig.

Synthesis of the needs of the clinician in PCI

According to the clinical context we have exposed, we are now in position to synthesize the needs of clinicians in PCI. These needs are different according to the stage of the procedure. Before expanding the stent (step 6 of table 1.2), the clinician is interested in the exact positioning of the balloon versus the lesion, the calcifications, the potential bifurcations and potentially pre-existing stents from prior procedures. Right after stenting (step 8 of table 1.2), the clinician is interested in the shape of the stent to assess its proper expansion/deployment and its relative position to the vessel wall. Quantitative assessment of stent expansion (measurement of diameters) is also relevant in this context. At patient follow-up, detecting potential stent fractures (that typically appear late after stent deployment as a result of fatigue) is one of the concerns. Therefore a cathlab shall ideally provide:

• visualization of the position of the balloon with respect to the vessels, stents and calcifications,

• visualization of deployed stents,

• visualization of the relation between deployed stents, vessels and calcifications, and

• quantitative measurements of stent deployment.

Stent visualization in the cathlab

Let us now review how conventional imaging techniques address the needs we have expressed with respect to PCI. There are two families of imaging techniques in the cathlab: Xray imaging with the interventional system as presented so far, and intra-vascular imaging, with ultra-sound or optical coherence tomography. The properties of the stents are such that they have very low visibility in conventional Xray images. Therefore, intravascular imaging is the preferred option to visualize them. To better understand this, let us consider more precisely what a stent is. A look at the data sheets of the most common stents (Cypher, Taxus Express, Taxus Liberte, Endeavor and Xience V) shows that they share the following characteristics [START_REF] Garg | Coronary stents: Current status[END_REF]: they are made either of stainless steel or CoCr, the strut thickness is between 81 and 140 µm, and they are fine complex meshes. The SNR under Xray is directly related to the material and its thickness.

Although metals have great radio-opacity, the struts are so fine that the resulting attenuation of the Xray beam is minor. Simulations [RLM + 05] show that for typical patient thicknesses the contrast to noise ratio of the stent is between 1.3a n d0 .19. In addition to these discouraging figures, the very nature of the geometry of the stent (Fig. 1.10), a complex 3D mesh, adds to the difficulty of assessing it from projection images.

Conversely in intra-vascular imaging the stent is visualized into cross sections. Therefore its geometry is simple to understand, and each strut can be visualized separately.

Moreover its contrast to noise ratio is such that strut conspicuity is high, and that they can be immediately identified in the images. Finally the vessel is also visible in the cross sections, enabling the clinician to assess the apposition of the stent onto the vessel (Fig. 1.14). However, it is important to note that intra-vascular imaging is a significant additional cost over the regular procedure and is therefore only moderately used (at the exception of Japan where it is reimbursed according to the national policy). Moreover, there is a large number of vessel slices to examine, and it is not mentally straightforward to build an image of the general stent scaffolding out of them. In short, conventional Xray imaging does not allow to visualize properly the stent and intravascular imaging, although better suited, is longer, more complex and costly.

There is no imaging techniques providing a cheap, convenient and easy way to visualize stents inside the cathlab during every procedure. on the SNR of stents is the limited Xray dose delivered in each frame. However, along an image sequence the whole dose that is delivered would be sufficient to image the stent with a much higher contrast to noise ratio (typically 5 times better than in a single frame). Consequently DSE proposes to track the stent along the image sequence and to integrate the value of the pixels of the stent along their trajectories. For each stent pixel, all the information present in each image of the sequence is cumulated. As a consequence, in the resulting image the stent is greatly enhanced. Since the stent itself is extremely hard to detect, its motion is inferred from the position of the balloon markerballs and of the guide-wire.

The full automation of the DSE algorithms is key to their adoption by clinicians in daily practice. Indeed, during the course of an intervention the clinician is extremely busy: his hands manipulate the interventional tools, his feet control the X-ray on/off pedals and his eyes focus on the display of the imaging system. Any user interaction that distracts his attentions from these tasks is considered a serious limitation. The philosophy of this PhD thesis is to develop image processing applications to support clinicians in their daily practice. Some of the developments presented in this manuscript (Chapters 2 and 3) have recently been implemented into commercial products (StentViz -GE) and are used in daily practice by clinicians (Fig. 1.16). To this end, I performed the following tasks1 listed in chronological order:

Context of the thesis

• develop the algorithm,

• install a prototype on a clinical site and improve it based on clinical feedback2 ,

• lead the clinical validation study on the GE side,

• issue patents protecting our intellectual property and publications to valor our technology,

• deliver the implementation of the industrial product,

• define the specifications and tests of the application,

• deliver design, specification and test documents,

• demonstrate substantial equivalence with an existing industrial product for the approval on the US market by the FDA.

I benefited during this work of a hardware/software platform developed internally that allows to seamlessly install prototypes on sites without impacting the clinical workflow.

In order to reach the expected level of performance for an industrial product, we paid particular attention to the validation of the performance of each algorithmic brick on large sets of clinical data (from 20 to 200 clinical sequences depending on the chapter).

Up to now, we keep on monitoring the feedbacks associated with these products from the hundreds of equipped sites.

The technical developments presented here address a large number of topics starting with feature detection and tracking (Chapters

Structure of this thesis

The chapters of the thesis address DSE and related topics in the following manner:

• Chapter 2: Stent visualization enhancement algorithm. This key chapter presents a thorough analysis of the problem of DSE, a fully automated and image quality oriented algorithm to solve it, detailed clinical validation and comparison with an existing commercial DSE software.

• Chapter 3: Subtraction of the guide-wire in enhanced stent images. We take advantage of the transparent nature of Xray images to overcome a common limitation of DSE: the guide-wire, that has no clinical interest, overlaps with the stent and hides it. The technique we propose, allows to erase the guide-wire from the images without degrading the subtle details of the stent struts. • Chapter 5: Curvilinear structure enhancement. We investigate here a new approach to curvilinear structure enhancement based on the combination of local shortest paths and voting. In a first part, curvilinear structure enhancement techniques and evaluation methodologies are presented. Then our technique is described and the links with other existing techniques are discussed. Finally we evaluate its performance for the enhancement of guide-wires in Xray images.

Each chapter is organized as a independent publication (abstract -introductionbackground -method -result -discussion -conclusion) and can be read quite independently from the other ones. However there is a logic in the organization of this thesis and the reader will benefit from reading them in order: the second chapter introduces the problem of stent visualization and our digital stent enhancement technique. In Chapters 3 and 4, we elaborate on it. Chapter 5 presents a more standalone work dedicated to the enhancement of curvilinear structure in images. It is applied to the detection of the guide-wire, a problematic discussed in the 3 previous chapters.

Main technical contributions

The most significant contributions of this thesis can be classified into the following topics: stent visualization, interventional tool detection and tracking, curvilinear structure enhancement and methodology. and patented [START_REF] Vaillant | System and method to enhance visualization of an object in a vascular vesselus patent 7734328[END_REF].

(a) (b) To further improve the visualization of stents we develop in Chapter 3 an original approach that erases the guide-wire from Xray images. It takes advantage of the transparency of the images acquired with this modality. We express the guide-wire removal task as a layer separation problem where the image is modeled as a sum of three layers:

the background, the guide-wire and the stent (Fig. 1.18). The first two layers are estimated and subtracted from the original image to isolate the stent layer (Fig. 1.19). The performance of this technique has been demonstrated on a set of clinical cases. Results

have been presented at a conference [START_REF] Funck | Guide-wire subtraction in enhanced stent images[END_REF] and some technical aspects have been patented [START_REF] Bismuth | Procédé de traitement d'images radiologiques -french application number 1000078096[END_REF][START_REF] Vaillant | Procede de traitement d'images radiologiques -french application number 1000076021[END_REF].

Interventional tool detection and tracking

The 2D and 3D stent visualization techniques that we propose, rely on the automatic detection and tracking of two interventional tools: the radio-opaque markers embedded in the angioplasty balloon and the guide-wire supporting it. In Chapter 2, we describe an algorithm to perform this task in static acquisitions (Fig. Moreover, we propose in Chapter 2, a technique to segment a guide-wire between two given points. The main challenge in this application is to design a technique that is particularly robust to noise. State of the art techniques usually rely on the computation of a geodesic path between the two end points. The geodesic minimizes the integral of a potential along the path. Our approach differs by two aspects:

• First, we define a metric based on the shape of the integrated profile along the path (Fig. 1.25). If the path is aligned with the guide-wire, the integrated profile shows a characteristic shape with a clear minimum at its center. Otherwise the minima of the profiles sampled along the path do not add up coherently and the integrated profile does not present the expected shape.

• Moreover, contrarily to classical shortest paths approaches, the paths are constrained to be smooth parametric curves (piecewise polynomial). This prevents them from wandering around the actual guide-wire under the attraction of local noise fluctuations (Fig. 1.25).

We demonstrate the ability of our technique to handle large amounts of noise on clinical data (Fig. 1.25). It has been patented [START_REF] Vaillant | System and method to enhance visualization of an object in a vascular vesselus patent 7734328[END_REF] and published in a journal [BVF + 11]. Bottom left: A clinical image depicting a guide-wire. Bottom center: 3 candidate curves (note that the blue one is well aligned with the guide-wire centerline whereas the red and green ones are not). Bottom right: The three averaged profiles (same color code as bottom center). Abscissa is the signed distance to the curve and ordinate is the pixel intensity. Only the profile of the blue curve that is aligned with the guide-wire exhibits a marked minimum at its center.

Curvilinear structure enhancement

We present in Chapter 5 a new tool to process curvilinear structures in images: the polygonal path image (P). It is based on the concept of locally optimal paths and has several interesting properties:

• a unification of local, semi local, and global curvilinear structure analysis in a single framework,

• the ability to control the smoothness and length of the structures to analyze,

• an intuitive and simple parametrization,

• an efficient computational scheme.

P is a rich descriptor of the curvilinear structures present in an image from which we derive line enhancement and direction field computation techniques. We have demonstrated the relevance of this line enhancement technique for the application of guide-wire segmentation both qualitatively (Fig. 1.26) and quantitatively using the ROC analysis formalism. We show that it outperforms previous state of the art techniques. Moreover, contrarily to the direction fields built with state of the art methods that are not relevant outside of the curvilinear structures, P indicates the direction of the closest such structure (Fig. 1.26).

Methodological contributions

We finally want to emphasize on the significant and systematic efforts that we dedicated frames. The performance of our line enhancement technique has been quantified on 100+ guide-wire images. Moreover, each validation covers the design of assessment metrics. One of the challenge of this task is to translate the performance expected by the user into measurable technical quantities. We believe that these methodologies and their associated results can be considered as best practices and constitute a relevant comparison point for other researchers in our field.

Material published for the first time

Several of the studies presented in this manuscript appear publicly for the first time.

Among these, we would like to point out:

• The comparison of our stent enhancement technique to an industrial product (Section 2.4.5)

• Most of the content of Chapters 3 (guide-wire subtraction) and 4 (3D stent visualization). • The entire content of Chapter 5 (locally optimal path technique for curvilinear structure processing).

The future of the cathlab in interventional cardiology

Before concluding this introductory chapter, let us have a look at what we can foresee of the near future of the cathlab for PCI related procedures. In the 90s and early 2000 the introduction of BMS and DES has been a complete game changer in cardiology enabling to treat safely a very wide population of patients. Nowadays, the trend is to improve the short and long term safety of re-vascularisation procedures. It includes, on the one hand, doing it better (safer stents, additional tools) and performing it only when it is best suited (improvements in decision making). Stent design is an extremely active research area [START_REF] Garg | Coronary stents:: Looking forward[END_REF]. Current developments focused on stent safety include reducing the thickness of the struts and developing biodegradable stents [START_REF] Garg | Coronary stents:: Looking forward[END_REF]. Both of them raise issues concerning the radio-opacity of the new stents, and will probably raise the level of expectations on DSE algorithms.

Besides, two recent studies may impact the "stenting procedure breakdown" that we have presented (see Fig. 1.27). The first one [SVvdH + 08] demonstrates that adding a step to this procedure is beneficial in case of acute MI. Instead of proceeding to stenting and potentially crushing the thrombus onto the vessel wall, the emerging practice tends to perform thrombus aspiration with a specific device prior to stenting. The second study [TDBP + 09] deals with the choice of the lesions to stent. They propose to systematically base this choice on a measure of the hemodynamic impact of the lesion, the Fractional Flow Reserve. This measure is also performed with a specific catheter mounted device. It will probably result in less lesions being stented.

Conversely, PCI has conquered a new territory over the past years. Chronic Total Occlusions (CTO) that used not to be treated, are now more and more handled by PCI.

These complex and often long procedures will probably drive new image processing applications based on clinical tool detection and tracking. From a more prospective standpoint, current research efforts aim at curing the consequences of MI and restoring valid heart tissue. These techniques based on stem cells injection and angiogenesis are still at a very early stage.

Conclusion

This thesis presents stent imaging techniques based on conventional Xray acquisition that aim at addressing previously unmet needs of the clinicians. To this end, we present a set of image processing algorithms, that typically incorporate detection, tracking and registration of the clinician's tools. The resulting techniques provide relevant clinical information that was not accessible in the original X-ray images. Moreover it does not increase the time or cost of the procedures. From a long term perspective, the development of algorithms dedicated to the processing of the clinical tools in interventional imaging is a trend that is likely to increase and find new applications with emerging procedures, ultimately improving device guidance with real-time implementations. 1

The technical work we present in this chapter has been partly published in a conference [BV08b] and a journal paper [BVF + 11]. The key points of the technique are covered by a patent application [START_REF] Vaillant | System and method to enhance visualization of an object in a vascular vesselus patent 7734328[END_REF] and some of the results were the subject of an oral presentation at EuroPCR 2009 and have been published in an abstract [START_REF] Funck | Quantitative evaluation of an elastic stent enhancement technique in x-ray image sequences[END_REF]. Finally, the comparative data of Section 2.4.5 have supported the pre-market notification of StentViz (GE) [Mor09].

Introduction

The general clinical context of this thesis has been extensively described in Chapter 1.

In order to keep this chapter self-complete, we start with a brief reminder of the most important elements necessary to understand the covered topic. Coronary heart disease is the most common cause of sudden death, and the most common reason for death of men and women over the age of 20 [RFF + 07]. This disease tends to narrow the lumen of coronary arteries by the accumulation of atheromatous plaques within their walls.

The narrowing of the artery lumen due to plaque progression, or plaque rupture can be cured by the expansion of a fine metallic mesh called a stent that is implanted in an artery wall acting as a scaffolding to open the lumen thereby restoring blood flow. Stent placement is performed as part of a percutaneous coronary interventional procedure.

The procedure is typically performed under the guidance of X-ray fluoroscopy delivering real time video of the clinical tools and devices in the patient's anatomy, (Fig. 2.2 (a)), typically at 15 fps. The clinician first introduces a metallic guide-wire inside the artery that serves as support for sliding an angioplasty balloon equipped with a stent.

The angioplasty balloon is used to expand the stent. Its inflation simultaneously opens the lumen and embeds the stent into the vessel wall. In order to visually assess the location of the balloon/stent on the guide-wire, the balloon is equipped with two highly radio-opaque marker-balls delimiting the position and extent of the devices. However visualizing stents with conventional X-ray images is extremely challenging. Indeed, coronary stents are characterized by their low radio-opacity and their fast motion. The recommended solution to assess stent deployment and apposition is to perform Intra-Vascular Ultra-Sound imaging (IVUS). This modality, considered as the gold standard for stent and vessel assessment during percutaneous coronary interventions, provides cross sectional images of the vessel, depicting the stent, the vessel wall and enables quantitative length and area measurements. Unfortunately systematic use of IVUS is impractical since it would add significant time and cost to the procedure. It is only used in 4.5% of the cases in Europe, 14% in the USA and 60% in Japan where it is reimbursed. In this chapter, we consider techniques enabling stent visualization that are consistent with the normal workflow of an angioplasty procedure. Although they cannot bring direct information on the apposition of the stent onto the vessel wall, they can provide relevant images for assessing deployment irregularities, lesion treatment and potentially measuring stent expansion. requirements that make it suitable to register not only stents but also any medical device inserted inside a vessel, or vessels themselves and can thus have various applications.

The chapter is organized as follows: In section 2.3 we define user requirements and flow them down to quantifiable metrics. We show how the main characteristics of a successful DSE algorithm can be deduced by the analysis of the problem. Then we describe a fully automated algorithm to perform DSE that segments the marker-balls and the guide-wire and registers images in a non-linear manner to take into account vessel and stent deformations. In section 2.4, we validate the fulfillment of the user needs on a large number of cases, addressing the performance of the segmentation of the landmarks, the image quality improvements and comparing non-linear to linear registration. In section 2.5, we discuss the results and expose the challenges that are still not met by DSE. Conclusions are drawn in the last section.

Method 2.3.1 Clinicians' needs

From the clinician's standpoint, the value of a DSE technique depends upon three factors : improvement in image quality, limited user interaction and reasonable execution time. For each factor, we defined a metric and set goals that capture clinical needs.

The first factor, image quality, is the most subjective and therefore the most difficult to measure. For our application we defined a 5-grade image quality scale quantifying the visibility of stents:

1. the stent is hardly visible 2. the stent border can be guessed 3. the stent border is clearly visible 4. the stent border is clearly visible and some struts are visible

the stent is perfectly visible

In order to quantify improvement in image quality, two clinicians3 rated images before and after the application of the DSE technique. They considered that a statistically meaningful improvement of one grade is necessary for the method to be adopted. Regarding user interaction, clinical feedback suggested that a DSE technique that is successful in 80% of the cases in a fully automatic manner, and in 90% when the user selects a region of interest (ROI), was sufficient to be regularly employed in practice. In terms of execution time, one has to keep in mind that an angioplasty procedure typically lasts between 20 minutes and 2 hours. During an interventional cardiac procedure, clinicians do not need to have DSE images in real-time, but in a "reasonable" time after the deployment of the stent. The delay induced by the computation of the DSE image should not disturb the regular work-flow of the procedure. Clinical feedback suggests that a DSE technique should not exceed 30s execution time.

From problem statement to algorithm design

The main characteristics of a DSE algorithm that will fulfill the clinicians' requirements can be deduced from a detailed analysis of the DSE problem. In this section we study how image quality can be improved. In the case of stents, it can be split into four factors : contrast, zoom, sharpness and noise.

Contrast

DSE seeks to emphasize the subtle contrast variations induced by the presence of the stent. However, traditional processing and display strategies are generally optimized for the visualization of large structures like coronary vessels while concurrently suppressing noise, and not for the fine stent details. Consequently, contrast and windowing of traditional processing approaches are suboptimal for stent visualization(Fig. 2.4). Dedicated image processing, like unsharp masking (background subtraction), must be set in place to enhance the fine details of the images.

Zoom

The stent only represents a small portion of the original images. Typically a 100 2 area in a 1024 2 image. DSE can directly improve stent visualization by zooming on the region of interest and masking un-necessary image parts. The comparison of Fig. 2.2 (a) and (c) illustrates this.

Sharpness

The sharpness of the enhanced image is a function of the sharpness of each input frame and the precision of the registration. The sharpness of the input frames is mainly ruled by the focal spot of the Xray tube and the characteristics of the detector. These physical parameters are generally well optimized by the constructors and the input images can be considered sharp, at the exception of one or two frames every heartbeat that are some- Transfer Function (MTF) that tends to spread the stent strut over the neighbor pixels.

Determining the required precision of the registration and its implications for the design of a stent enhancement algorithm was the subject of dedicated studies. Langan et al [RLM + 05] determined that DSE is robust to some degree of error in the registration process. They centered their approach on a task oriented framework, evaluating the ability of an observer to detect stent under deployment. They concluded that it was improved by DSE up to a registration error of 2 pixels but that the benefit exhibited a significant fall off beyond 1.25 pixels of error. On our side, we attempted to quantify the effect of the registration error directly on the image quality regardless of a specific task.

We imaged several still stents with an X-ray angiographic system. We averaged these images with various simulated registration error (Fig. 2.5). The registration error was modeled as a uniform distribution on each coordinate of amplitude ranging from 0 to 2.5 pixels. It turned out that stent struts were visible up to an error below 1 pixel. An error between 1 and 2 pixels would preserve the border but make delineation of stent struts very difficult. Any error above 2 pixels would impair the visibility of the stents.

These two experiments confirmed that given stent geometry and acquisition resolution, registration errors less than a pixel are tolerable, whereas registration error in excess of 2 pixels severely degrades performance rendering the algorithms benefit to be questionable. We want to emphasize that these results hold for the imaging system considered in our experiment and in the cited study [RLM + 05]: the Innova 2000 and 2100 series (GE). They shall be revisited for systems with different imaging chains since pixel size and magnification factor can vary. In order to optimize this error we analyzed its origins.

We identified two primary root causes for misregistration: landmark localization error;

and the error in inferring stent motion relative to that of the landmarks. Stent and landmark motion is complex due to projection of 3D motion onto a 2D plane, and stent motion that is independent of the landmarks (see section 2.5.6). We concluded that, in order to optimize stent visualization, we need to minimize landmark segmentation error (ideally sub-pixel). Additionally, to minimize the stent motion estimation error, we have added the guide-wire supporting the markers balls to the set of landmarks. We show that by considering guide-wire and marker ball motion, we have improved the accuracy and robustness of stent motion estimation (Fig. 2.6).

Noise

The major source of noise in X-ray fluoroscopy is quantum noise. It follows a Poisson distribution and it is spatially correlated but temporally white [SBE + 95, ASS99].

A variance stabilization transform is commonly applied to Xray images [Ans48]a f t e r which the noise can be considered stationary and Gaussian. There are two sources of information redundancy in the image sequences that can be used to reduce the noise:

the spatial content of each independent image, and the temporal content of the image sequence. The spatial content of a stent image being very complex, intra image denoising could result in stent detail degradation. Therefore a DSE algorithm will preferentially restrict denoising to the temporal domain. The temporal redundancy is advantageously

(0) (1.5) (0.5) (2)
(1) (2.5) Bottom is the marker-ball based registration. Although the two marker-balls are accurately registered, the stent, that underwent a non-linear deformation is not accurately registered. The guide-wire that supports the marker-balls is also undergoing a nonlinear deformation. We use it as additional landmark in our nonlinear registration. The stent image is derived from a photo of a Cypher coronary stent [tim05] utilized by integrating the values of each pixel of the stent along its trajectory (therefore it requires the estimation of the trajectory of each pixel of the stent). The way the values are combined together and the number of images taken into account drive the noise reduction capability. Typical DSE strategies [RLM + 05, Koo05, SF09] involve averaging t h ep i x e lv a l u e so v e ras h o r t( ≈ 30 frames) sequence. It yields a noise reduction factor of approximately 5 that is usually enough to make a major difference in image quality.

We study here in more details the way to combine the images and the required number of images.

To Let us call {x i } 1≤i≤n the values of a given pixel along its trajectory in the n images of the sequence. We model the noise on the pixels by considering that the {x i } 1≤i≤n are the realization of random variables {X i } 1≤i≤n . We examine the task of combining the values of the pixels in the different images of the sequences by considering that it consists in estimating a given parameter of the distributions of the {X i } 1≤i≤n . The choice of the adequate estimator then depends on the hypotheses we make on these distributions.

Given the properties of the noise previously listed, we consider the {X i } 1≤i≤n to follow Gaussian distributions of same standard deviation σ. Estimators are classically characterized based on their bias and variance. In our case the bias induces a shift in pixel intensities in the combined image and the variance predicts its noise.

We consider two different hypotheses regarding the {X i } 1≤i≤n that yield different estimators. The first one is that they all follow the same distribution of mean µ and variance σ 2 . It relies on the assumption that the pixels have been perfectly tracked in the background subtracted images (we call it the hypothesis 1): a same pixel corresponds exactly to a same stent or background element and has thus the same value across the images except for the noise. Under this assumption we aim at estimating the expectation (the parameter µ) of the underlying Gaussian distribution. The empirical mean (Eq 2.1)i s the non biased estimator of minimal variance in this case. It is thus an ideal choice. The noise in the combined image 4 (the standard deviation of the estimator) is

σn -1/2 . Xn = 1 n 1≤i≤n X i (2.1)
The second hypothesis we consider regarding the distribution of the {X i } 1≤i≤n is that they do not all have the same mean. It is an attempt to account for imperfections in the pixel trajectory estimation. These inaccuracies can result from the non uniformity of the cardiac motion. More precisely, in a short lapse of time in the cardiac cycle (typically less than 20%) corresponding to the beginning of the systole, the cardiac motion accelerates and the motion estimation may be less accurate. We thus propose the hypothesis that the values of a pixel along its estimated trajectory correspond to a same mean in 80%

of the samples and to different means in the other 20%. In such a case the empirical mean Xn may not be the optimal estimator. A common strategy in such a situation where outliers are present in the sample is to use a robust statistic, typically the median a n dt h et r i m m e dm e a n[ Wik11d]. In order to further express these estimators let us consider the rank statistic X (i) that returns the i th value of the set {x i } 1≤i≤n sorted in the increasing order. The median is simply X ([n/2]) and the trimmed mean excluding the k lowest and the l highest values on each side is defined following Eq 2.2.I nt h i s section the brackets [.] denotes rounding to the closest integer.

Tn,l,k = 1 n -k -l k+1≤i≤n-l X (i) (2.2)
The trimmed mean is often considered to be in between the mean and the median:

for l = k = 0 it equals to the mean and for l = k =[n/2] to the median. We selected it for our application since it allows to reject a precise percentage of outliers. We consider three trimmed mean estimators, rejecting p = 20% of the outliers: the symmetric one Tn,[

p 2 n],[ p 2 n]
, and the two disymetric ones Tn,[pn],0 and Tn,0,[pn] . Regarding rank filters, we did not restrict to the median, and for sake of exhaustivity considered the 5 following ones :

X (0) , X ([n/4]) , X ([n/2]) , X ([3n/4]) , X (n) . W en o t et h a tX (0) ,t h a tt a k e st h em i n
of the values of the pixel along the sequence is commonly employed in vascular imaging under the name peak opacification to image contrast media traveling inside vessels [START_REF] Kump | Comparison of algorithms for combining x-ray angiography images[END_REF][START_REF] Kump | Digital subtraction peripheral angiography using image stacking: Initial clinical results[END_REF].

We thus selected 9 estimators to combine the values of the pixels across the frames : the empirical mean, the 3 trimmed means, and the 5 rank filters. We first compared these estimators based on their bias and variance under hypothesis 1. Since it is delicate to precisely simulate the second hypothesis we applied the estimators to a set of 30 clinical sequences and visually evaluated the image quality of the combined images.

It can be demonstrated that under the assumption of a symmetric distribution (that is the case of the Gaussian) the estimators Xn , X ([n/2]) ,and Tn,[ p 2 n],[ p 2 n] are non biased and the other ones biased. Their variance can be analytically derived for Xn and X ([n/2]) , and the trimmed means respectively σ 2 n and πσ 2 2n . However, although the cumulative distributions of the rank filters F X (i) can be derived from the Gaussian cumulated distribution function denoted F according to equation 2.4 [START_REF] Slotboom | The effect of order-statistics filtering on the output probability density functions[END_REF], the moments are not straightforward to derive (for instance trimmed means variances are

F X (i) (x)= j=1 n n j F (x) j (1 -F (x)) n-j (2.3)
For Xn and X ([n/2]) the variance follows the expected theoretical curves. The general decrease of the standard deviation in n -1/2 is observed for all the estimators except the min and max (resp. X (0) and X (n) ). We observe that Xn has the lowest standard deviation, very close to the one of the trimmed means Tn,[

p 2 n],[ p 2 n] ,
Tn,[pn],0 and Tn,0,[pn] . The rank filters have higher standard deviation, and can be ranked in increasing order (denoting σ(E) the standard deviation of estimator E):

σ(X ([n/2]) ) <σ(X ([3n/4]) )=σ(X ([n/4]) ) <σ(X (0) )=σ(X (n) ) (2.4)
Therefore, we expect to observe an optimal noise reduction capability for the empirical mean, very closely followed by the trimmed means, and larger noise in the rank filter estimates. We validated the relevance of our model on two clinical sequences. We measured the noise in the images by computing the empirical standard deviation in an ROI where there is no significant structures. The background of the images being subtracted, the choice of such an ROI is facilitated (Fig. 2.8). We performed the noise measurement in one image of the original sequence and on the combined images obtained with each of the 9 estimators (for a combination of 30 images). We then plotted the noise standard deviation predicted by our simulated curves (Fig. 2.7) and the measured ones in Fig. 2.9. The overall accuracy is satisfying: Our model predicts well the general impact of the estimators on noise with an average absolute error of 9%. It validates that the hypotheses on the noise that we made (predominance of quantum noise, Gaussian distribution and temporal independance) are valid enough. We further explored the performance of the different estimators by evaluating the image quality visually on 30 clinical cases. We used Xn as reference and performed relative rating. The observer (who is also the author of this thesis) was asked to rate each estimator among the 5 following categories:

• --: The image is significantly worse than the one obtained with Xn . More details are visible with Xn .

• -: The image is slightly worse than the one obtained with Xn . The same details are visible but noise or contrast is less good.

• = : No image is better than the other one.

• + : The image is slightly better than the one obtained with Xn . The same details are visible but noise or contrast is better.

• ++ : The image is significantly better than the one obtained with Xn . Less details are visible with Xn .

For this task the examination was on purpose restricted to the stent area. The output of this review are presented in Table 2.1. Since the images were never better than with Xn we omitted the empty categories + and ++. The figures demonstrate that the mean filters (empirical and trimmed) perform better than the rank filters. All the mean filters are visually indiscernible in the stent area. Among the rank filters that generally exhibit more noise, the best one is the median that yields results that are never very different from the reference (no case in the category --). X ([n/4]) is often acceptable also though significantly worse than Xn in some cases. The other rank filters generally yield very poor results. We illustrated the images produced with the different estimators and their difference to Xn in Fig. 2.10.

Observation of the part of the image that does not contain the stent (and that is thus less clinically critical) shows that trimmed means are more robust to registration inaccuracies. Far from the markers (typically 50 pixels away from the marker segment) the landmarks are not registered anymore in our experiment and the guide-wire appears at different locations in each image. As a result it appears duplicated in the combined image. Since the guide-wire is darker than the background, it affects the lower part of the distribution of the {X i } i and trimmed means Tn,[

p 2 n],[ p 2 n] ,
Tn,[pn],0 allow to attenuate this undesirable effect (and not Tn,0,[pn] that keeps unchanged the lowest part of the distribution). We illustrate this observation on a clinical case on Fig. 2.11.

Rating X (0) X ([n/4]) X ([n/2]) X ([3n/4]) X (n) Tn,[ p 2 n],[ p 2 n]
Tn The output of this study on image combination and its effect on noise and image quality is that empirical and trimmed means appear to be the most relevant techniques and yield a noise reduction factor of approximately n -1/2 when n images are combined.

They are equally relevant on the stent area but the trimmed means are superior in the rest of the image where registration is less accurate. For the remainder of this chapter we will produce results with the empirical mean, since they have been produced before this part of the study was complete. We expect to have optimal results on the most clinically relevant part: the stent.

We have seen that, theoretically, an increase in the number of combined images always decreases the resulting DSE image yielding asymptotically a total noise removal (σ( Xn ) -→ n→∞ 0). However three factors tend to limit the practical number of images taken into account:

• The improvement in image quality is limited by the minimal image quality required to visualize the stent. Beyond this point, there is no clinically added value to further denoising. Moreover, the inaccuracies of the motion compensation tend to introduce blur into the DSE images that limit the quantity of visible stent details. Those destroyed by this blur cannot appear whatever the noise reduction.

Therefore the image tends to converge to an optimal point when the number of images increase.

• The decrease in noise is not a linear function of the number of image combined.

The theoretical law of noise decrease being n 1/2 , each additional frame reduces noise less than all the previous ones. With 25 images, 80% of the noise is removed.

In order to reach 90% of noise removal one has to combine 100 images.

• Regarding Xray dose, a relevant order of magnitude is the reference level in France for an angioplasty: 1355 cine frames. It is defined as the 3thrd quartile of the distribution, meaning that 75% of the procedures involve less frames than this limit. It is desirable that DSE not increase significantly the whole procedure dose.

A few percent of the dose (some tens of frames) are far more acceptable than some tens of percent (some hundreds of frames).

For all these reasons we will only consider short sequences of some tens of frames. In order to evaluate the number of images to take into account in the image combination, we studied the residual noise and the visual image quality as a function of the number of combined images. For this study we used the empirical mean estimator. We studied experimentally the image quality and the noise in 4 short sequences of some tens of frames as a function of the number of combined images. The noise standard deviation measurements, plotted in Fig. 2.12, show that once again the noise follows reasonably the expected power low. Regarding image quality, DSE images resulting from the combination of 1, 10, 20, 30, 40, 50 and (when available) 60 frames are illustrated in Fig. 2.13. We observe, as expected, that most of the benefit comes from the first tens of frames. Moreover, above 30 to 40 frames the DSE image converges to some optimum.

These considerations and results motivate the use of sequences of 30 to 40 frames in DSE. The noise reduction factor is in this case approximately 5.

DSE algorithm design take away

To conclude this section, our analysis of the DSE problem resulted in the determination that a successful DSE algorithm shall automatically process short (30 to 40 frames) image sequences with a high success rate (> 80%) and enable a computation time (< 30s) to fit within the interventional work-flow. Moreover, in order to attain optimal image quality, it shall perform noise reduction preferentially by temporal techniques, combine images with (trimmed) averaging, include a background removal and adaptive zoom for visualization. Last but not least, it shall detect the marker-balls, the guide-wire and register the stents with a high precision, ideally sub-pixel.

DSE algorithm

In this section, we describe a DSE algorithm derived from the objectives and constraints previously listed. We first give a general overview of the method, then we detail the parts that are specific to our approach. Finally we explain our strategy to find a relevant setting of the many parameters that are involved.

Algorithm overview

The DSE algorithm that we propose can be divided into four main steps (Fig. Image combination consists of averaging all the registered frames together to produce a denoised image. Then the contrast is set to enhance stent details. It benefits from the dark top hat pre-processing that removes background variations. Finally zooming is performed centering on the landmarks. The most challenging problems addressed by our algorithm are the segmentation of the guide-wire and the non-linear registration. We first published them in the patent application [START_REF] Vaillant | System and method to enhance visualization of an object in a vascular vesselus patent 7734328[END_REF]. We detail them in the following sections.

Guide-wire segmentation

Segmenting the guide-wire in an X-ray image is known to be a difficult problem. Indeed, guide-wires are fine elongated structures, typically 3 to 5 pixels wide, of low Contrast to Noise Ratio (CNR) 5 . A typical CNR is around 3, but may fall below 1 in the most challenging cases. Previous researches on guide-wire segmentation fall into two categories. One category is based upon building a map of the probability that a guide-wire is present [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF], and the second category explicitly segments the guide-wire. The second category is of interest for our application. On the one hand, a set of articles [BAG + 07, HVP10b, HVP10a, HGG + 09] present sophisticated approaches to guide-wire segmentation based upon a machine learning formalism. They attempted to solve a problem that is more general than ours since they segment the whole guide-wire, whereas we are only interested in a local segmentation at the close vicinity of the marker-balls. On the other hand, Florent [START_REF] Florent | Medical viewing system and method for enhancing structures in noisy images[END_REF] addresses exactly our problem with a minimal cost path approach but does not guarantee the continuity of the first derivative of the guidewire curve that is required for our application, detailed in section 2.3.3.4. Therefore we developed a new guide-wire detection procedure designed at producing a smooth curve, while being robust to high level of noise and enabling fast computation. Our observation of clinical sequences suggests that the guide-wire between the markers may be modeled as a simple curve, typically a spline. Most of the time it may be approximated by a parabola. This observation is shared in [START_REF] Florent | Medical viewing system and method for enhancing structures in noisy images[END_REF]. In a subset of cases, the guide-wire possesses an inflexion point and may be accurately modeled by a set of two parabolas or a third degree polynomial expression. In the general case, a simple set of smooth parametric curves will describe all the possible guide-wire configurations between the markers, as well as in a short distance beyond the markers. Based on these observations, we decided to specify a discrete set of curves spanning a family of parametric curves (Fig. 2.17). Each curve is piece-wise polynomial. We proceed in two steps in a coarse to fine approach. First the discretization of the family is such that the maximal distance between two curves is 2 pixels. The guide-wire radius being 3 to 5 pixels we are certain that one of the curves is included in the guide-wire. Then we refined the selected curve to sub pixel accuracy with a maximal distance between curves of 0.5 pixels. A figure of merit is assigned to each curve in the set quantifying how well it represents the image content. We retain the parametric curve yielding the highest figure of merit. The challenge of our approach lies in the design of the figure of merit which is robust to the low CNRs of imaged guide-wires. In order to do so, we averaged intensity profiles line segments which are uniformly spaced between the marker balls, perpendicular to the tested curve, and centered on it (Fig. 2.17). The length of the segments shall be long enough to illustrate the guide-wire profile. Therefore, we selected it to be a few times the expected guide-wire diameter. Moreover, in order to capture all the information along the curve, the segments are spaced by one pixel in our experiment. The resulting average profile enables robust contrast estimation due to the reduction in noise. If the curve is well aligned with the guide-wire all the profiles are theoretically the same except for the noise. Averaging the profiles reduces this noise and yields a typical guide-wire profile.

Conversely, if the tested curve is not properly matching the guide-wire shape every profile is different and averaging does not make any particular pattern emerge from noise.

The analysis of the averaged profile is performed in two steps. First, a test is performed on the shape of the profile to determine if it has a significant minimum at its center (Fig. 2.17

Figure 2.17: (a) A set of tested parametric curves to segment a guide-wire between two markers. (b) In this clinical image, the dark line along the guide-wire depicts a parametric curve to be tested. The set of dark short segments represent the perpendicular profiles that are computed for this curve. (c) Illustration of the values along one of the profiles of image (b). We see that the noise is high and there is no particular pattern in this curve. (d) Averaged profile. We see that the curve follows the expected pattern: a smooth curve with a significant minimum at its center.

Constrained registration derived from a stent deformation model

Once the landmarks (marker-balls and guide-wire) have been segmented, we must then estimate their motion field. Secondly, we must define how to extend this motion field beyond the landmarks encompassing the image area occupied by the stent. Finally, we utilize the motion field for each image to temporally register the image sequence.

We denote (I t ) 1≤t≤n as the input image sequence of n images and we define I t 0 as the Center: All the profiles extracted for each curve (same color code as top right). On the abscissa is the signed distance to the curve and on the ordinate the pixel intensity. Bottom: The three average profiles. Only the one of the blue curve that is aligned with the guide-wire exhibits a marked minimum at its center.

reference frame over which all frames are temporally registered. The motion fields are computed with respect to this reference position. The definition of a motion field on the landmarks is straightforward. We force the marker centers to match from one image to another and the guide-wire to match according to the curvilinear abscissa. We define a reference point, O t , in each image that is the point of the guide-wire between the markers that separates it into two curves of equal length (Fig. 2.19.a). It is equidistant to the two marker-balls on the guide-wire. We compute the signed curvilinear abscissa from this point. We cope with global foreshortening by normalizing the curvilinear abscissa to the total length of the guide-wire between the markers. The motion field registers points relative to their normalized curvilinear abscissa (Fig. 2.19.b).

In order to extend the motion field from the landmarks to the stent we incorporated design constraints reflecting the physical properties of stents. First, stents must be very rigid on their radial axis in order to maintain the desired artery diameter under the pressure of the artery wall. Consequently, the radius of the stent at a given point must be constant over the image sequence. Second, stents must be flexible on their longitudinal axis in order to bend with the vessels to follow the heart contractions and expansions (Fig. 2.20). Therefore stents follow the deformations of the major axis of the vessel. Finally, we assume that the central line of stents does not shrink when the stents bend (the stents are extending on one side and shrinking on the one, but the length of their centerline is supposed to be invariant). These motion assumptions were confirmed through observation and analysis of clinical image sequences.

Although the major axis of the vessel is unknown, the guide-wire can be used as a surrogate estimate. The first two constraints can be translated into constraints with respect to the position of the guide-wire. Imposing that the distance of any point of the stent to the guide-wire is invariant along the sequence is enough to fulfill the two first constraints. In order to satisfy the stent length invariance constraint, we consider the orthogonal projection of each point of the stent onto the guide-wire (F P on Fig. 2.19.a)

and impose that the curvilinear abscissa of this point be invariant from one image to another. The constrained registration proposed has been demonstrated to perform well in practice (section 2.4.3), although alternate approaches are possible. In the following section, we detail the image registration based on the aforementioned considerations.

The design of this image registration technique and its usage are new and particularly tailored to the application of DSE. Moreover, one can observe that the constraints we listed and the solution that we propose in the next section may be extended beyond this context to register other medical tools traveling inside vessels and potentially vessels themselves as summarized in our previous work [START_REF] Bismuth | Elastic registration for stent enhancement in x-ray image sequences[END_REF].

Non-linear Registration

We build a system of coordinates (Fig. 2.19.a) in each image I t such that for any point P , d 1 is its distance to the curve defining the guide-wire and F P the point of the guide-wire that actually minimizes this distance. F P is unique outside of the medial axis 6 of the curve. Let us call d 2 the curvilinear abscissa from O t to F P along the guide-wire curve divided by the total length of the curve between the markers. We propose to use d 1 and d 2 as coordinate system. In order to create a coordinate system without ambiguities, let us give signs to d 1 and d 2 . Let us call M 1 and M 2 the centers of the two marker-balls in this frame. We define the curvilinear abscissa d 2 in the direction from O t to M 1 to be positive and the direction from O t to M 2 to be negative. Noting the curve defining the guide-wire is smooth, we can define a tangent to the curve t(F P )a ta n yp o i n tF P of the curve, pointing in the direction of positive curvilinear abscissa. Finally, we also define a normal vector n(F P ) such that ( t(F P ), n(F P )) is direct and we assign d 1 the sign of the scalar product t(F P ). F P P . Outside of the medial axis of the curve defining the guide-wire, T t , that maps a point P of

I t to (d 1 ,d 2 )
, is a continuous one to one mapping but is not defined on the medial axis. On a database of 241 clinical cases, we observed that the stent is never intersecting the medial axis. This can be explained by the rather high radii of curvature of the guide-wires in the clinical images. Therefore there is no artifact introduced by this transformation on clinical images in the area of interest.

In order to perform registration, we need to define the inverse transform T -

P ′ t = T -1 t (T t 0 (P )) (2.5)
Conversely any point P ′ t of an image I t is registered to the point P of I t 0 according to:

P = T -1 t 0 (T t (P ′ t )) (2.6)
Let Ĩt be the result of applying equation (2) to every point in I t . In any image Ĩt ,t h e marker-balls and the guide-wire are exactly at the same location as in I t 0 .U s i n gt h e empirical mean estimator, the image combination simply consists in averaging all the images Ĩt to produce the enhanced image I enhanced :

I enhanced = 1 n n t=1 Ĩt (2.7) (a) (b)

Settings and algorithm validation

Detecting the marker-balls, forming pairs, tracking them, and segmenting the guidewire required setting a large number of parameters. In order to determine optimal parameter settings, we collected a large database of 241 clinical sequences, representing approximately 7000 markers pairs. An operator manually determined the position of each marker ball in each image, and marked some guide-wire points in a subset of the images. Over this database we have been able to estimate typical values and variability of marker characteristics, marker motion, and guide-wire curvature. Moreover it enabled testing the landmark detection performances for a given set of algorithm parameters by comparing the results given by the algorithm to the ground truth. This process enabled parameter tuning for the detailed DSE algorithm. We found that the optimal setting of some key parameters is as follows: the size of the structuring element for the subtraction must be set to 9 pixels, the maximum height of the parabola describing the guide-wire must be set to 20% of the distance between the markers, and the distance between two markers does not vary more than 15% from one frame to another. The results presented in the next section have been obtained with the best parameter set that we tested.

Results

According to the clinical criteria defined in section 2.3.1, we elaborate on the validation framework for our algorithm. We have quantified its ability to automatically segment the landmarks. Results regarding the precision and robustness of their segmentation are also reported. Clinical interest of the technique has been assessed by evaluating the improvement it brings in image quality. In order to compare to other existing methods we have assessed the performance of the linear marker-ball based registration versus our non-linear registration and quantified both the difference in motion fields that are encountered on clinical data and difference in image quality in the resulting images.

Finally we compared our software to another commercially available solution.

Landmark detection and localization performance

Accuracy and robustness evaluation strategy

We have separated the problem of estimating the landmark detection/tracking performance into two sub-problems. The first category is to quantify, on clinical sequences, how well the automatic marker-ball segmentation is able to detect and track the marker-balls.

The main challenges are robustness to complex image content (anatomical structures and medical tools) in the detection algorithm, and to cardiac and respiratory motion with respect to tracking. It is evaluated in Section 2.4.1.2. The second category addresses quantitative accuracy of the segmentation, given that the marker balls are detected by the algorithm. We noted in the section 2.3.2.3 that we would like to reach a sub-pixel precision to insure the sharpness of the DSE image. Quantitative performance measurement of the registration accuracy requires precise knowledge of (sub-pixel) ground truth.

This precision cannot be achieved by a human operator on clinical sequences. Therefore we set up a specific simulation to assess that is the subject of the section 2.4.1.3.

Marker ball detection robustness

In the present section, we deal with landmark detection and tracking performance.

To this end, we had an operator mark the position of the markers on clinical image sequences. The position marked by the operator lies inside of the marker-ball but is not precisely at its center since this exact position is unknown. We compared the position of the detected markers to this ground truth on every image, calculating the number of false negatives, true positives and false positives (there are no true negatives since the marker-balls are present in every frame of the sequence) according to the following definitions:

• True positives are frames where the detected marker candidates are closer to the ground truth than a given tolerance.

• False positives are frames where the detected markers are further from the ground truth markers than a given tolerance.

• False negatives are frames where no marker is detected.

Marker ball being ellipses of large axis between 7 to 10 pixels, the tolerance was set to ±5 pixels. We computed the number of cases where the markers that our DSE algorithm output were closer than the tolerance to the ground truth. On a database of 241 clinical sequences, illustrating 7230 pairs of markers, our algorithm exhibited a true positive rate of 91.5%, a false positive rate of 1.5% and a false negative rate of 7.5%. We studied the detection performance in more detail to tell if some frames are regularly failed in every image sequence, or if some images sequences completely failed whereas others were completely successful. The histogram of the true positives, false positives and false negatives per image sequence are reported in Fig. 2.21. We can observe that some frames are regularly missed in each sequence as false negatives (2 to 3 frames). This does not have a strong impact on the final image quality. They often coincide with the small number of frames were the markers are very blurry due to the heart acceleration at the end of the rest phase. These images contain only very low information for stent enhancement, since the stent is also blurred. Regarding false positives, we can notice that in 98% of the sequence there are less than 5% of them. The overall performance over the database is very satisfying, and far beyond the 80% acceptance criterion set in 2.3.1 on the true positive rate.

Marker ball segmentation accuracy

For this task, we simulated a marker ball on a guide-wire using a model of a sphere and of a cylinder corrupted by typical noise and system point spread function (see Fig.

2.22

). We set the CNR of the synthetic marker-balls to values ranging from 5 to 10, since it is the range of values observed in clinical sequences. We applied our technique to the synthetic images and estimated for each input CNR the average distance between the detected marker location and the real marker center. A marker was considered detected if its center lied within the synthetic marker ball. The marker detection rate was 98%. This excellent result can be explained by the simplicity of our synthetic sequences. A more meaningful success rate is the one of 91.5% reported previously reported in Section 2.4.1 computed on the clinical database. The synthetic sequences are however particularly interesting to estimate the precision of the marker detection.

We found that the average error is less than 0.5 pixels both along the guide-wire and perpendicularly to it. As one can expect from the structure of the test images, the tests demonstrated that our marker localization process is more precise perpendicular to the guide-wire than parallel to it.

Guide-wire segmentation accuracy and robustness

Two main factors impact the success of guide-wire segmentation. On the one hand, the precise shape of the guide-wire, since we assume that it can be modeled by a set of parametric curves. On the other hand, the contrast to noise ratio of the guidewire. In order to address the topic of the shape of the guide-wire, we have selected 10 clinical sequences out of 241 on the criteria of very diversified guide-wire shapes and orientations, and rather favorable image quality. We ran our segmentation algorithm on each of these sequences and visually assessed the quality of the result. All segmentations were visually perfect (Fig. 2.23 (a) and (b)). This experiment validated that the set of selected parametric curves spans the natural variability of guide-wire configurations. We then considered these segmentations to be the ground truth for these images. Given the guide-wire width of 3 to 5 pixels and the difficulty to delineate precisely its centerline, we considered that this segmentation was precise within a range of plus or minus 1.5 pixel. Recognizing the challenge in the segmentation of the guide-wire being attributed to the low CNRs often encountered in clinical conditions, we degraded the 10 clinical images with noise to evaluate the robustness of the segmentation (Fig. 2.23 (c) and (d)).

We ran our algorithm on each degraded image and computed the Hausdorff distance of the segmentation to the ground truth (Fig. 2.23 (e) and (f)) according to Eq 2.8.

We generated 1400 degraded images adding noise of various standard deviations, up to producing images with 3 times the original noise level, which is considered an extreme situation. The CNR of the guide-wires ranged from 0.6to5.6 with an average of 1.7±0.9.

Over all the degraded images the Hausdorff distance was 0.8 ± 1.2a n dw a sb e l o w1 .5 pixels in 93% of the cases. This error increased with an increase in noise. For the cases where the noise was less than twice the original noise its repartition was 0.5 ± 1.0, below 1.5 in 97% of the cases. When the noise was two to three times the original noise it was 0.9 ± 1.3, again below 1.5 in 91% of the cases. An analysis of the histogram of the Hausdorff distances demonstrates that the overall 6% of failed segmentations fall equally into two categories (Fig. 2.24). Half of them are the tail of a distribution centered on the true segmentation. The other half are very large errors (superior to 7 pixels) where the segmentation departed from the guide-wire. In these cases, the algorithm was influenced by the image content, for example the border of a stent. The overall results are very satisfying with the segmentation being accurate in 97% of the cases portraying realistic conditions, and in 91% in extremely difficult cases which are less commonly encountered.

d H (X, Y )=max(sup x∈X inf y∈Y d(x, y), sup y∈Y inf x∈X d(x, y)) (2.8)

Image quality improvement

The image quality has been rated independently by two clinicians, before and after the application of the stent enhancement software according to the 5 grade image quality scale presented in section 2. image quality by more than one point (p ≤ 0.001) on the same image quality scale over a large variety of imaging conditions and stents. We present here this larger study into more details.

Data acquisition

The image sequences included in this study come from patients who were having a stent implanted during an angioplasty procedure on an Innova 2100 IQ (General Electric, Milwaukee, WI, USA) at Hospital René Dubos (Pontoise, France). The data collection From an image quality standpoint, the Innova system was set so as to produce images at 15 fps in the low dose setting. This setting is typical of a cardiac site, and for a DSE software it is a rather difficult case since frame-to-frame marker-ball motion is higher at 15 fps than at 30 fps and image quality is more challenging in the "low" than in the "normal" dose setting (the dose is reduced by a factor of 2). The patient population that was included in this study is typical of the clinical site: the average cardiac patient is male, 60 ± 10 years old, approximately 25% of them being classified obese.

Image quality and clinical benefit results

Each observer was asked independently to review the original image sequences and the resulting StentViz image and to rate stent visibility in both according to the IQ scale defined in Section 2.3.1. The IQ over the whole dataset was 1.2 ± 0.4 before application of DSE and 2.9 ± 1.1 after (Fig. 2.25). The average improvement is 1.8 ± 1.1(p ≤ 0.001).

According to the IQ scale, DSE allowed in average, improving from an image where the stent is hardly visible to an image where the stent border is clearly visible. A 95%

Confidence Interval (CI) for the improvement is [1.7, 1.9]. We assessed inter-observer variability by computing linearly weighted kappa (κ) [START_REF] Anthony | Understanding interobserver agreement: the kappa statistic[END_REF]. Since the unprocessed and processed images are of different nature, we computed it separately on both. The κ measuring agreement between the two observers at rating unprocessed images is 0.34 demonstrating "fair agreement". On processed images the κ of 0.49 is the expression of "moderate agreement". Finally, the Pearson correlation coefficient between the scores before and after application of DSE is 0.2( p ≤ 0.001). This positive correlation demonstrates the general trend: the higher the image quality of the input image sequence, the higher the image quality of the DSE image. where cine is better than fluoroscopy, we computed the histogram of the difference of the IQ score in cine and in fluoroscopy averaged over the two raters (Fig. 2.27). In 72% of the cases the difference is between -0.5a n d+ 0 .5, corresponding to very similar results. In 28% of the cases the difference is greater or equal to 1 meaning that the DSE on cine is better than on fluoroscopy.

In order to go beyond pure IQ rating and evaluate the clinical benefit, we asked the observers to rely on their experience, and to assess it based on the couples of processed and unprocessed images. Indeed DSE was not available at the time of the interventions and all the study has been performed in post processing. Each observer answered the yes/no question: "Would StentViz have helped you perform a better angioplasty?". The word "better" was to be understood as: faster, with more confidence or with less dose.

In 13% of the cases, both observers showed agreement and answered Yes. Observer 1 alone answered positively in 40% of the cases and observer 2 in 19%. A possible explaination for this difference is that observer 1 was more familiar with DSE at the time of the study. Indeed, he was also working, on a regular basis, with a product from Philips that presented a DSE feature. This may be a reason why he gave more credit to DSE images and therefore found them more useful.

Finally we investigated how the stent type impacts the result of DSE. It is of daily clinical experience that different stents have different aspect under X-rays. Indeed, stent composition and strut geometry impact directly their visibility. We have computed separately the IQ improvement for each stent type (Table 2.2). The stents that are based on the same platform have been grouped together (Driver and Endeavor on the one side, and Vision and Xience on the other one). The results confirmed that all stents are not equally visible in the input images. Moreover the study demonstrates that the improvement is not constant for each stent but depends on its type. In general, we observed that the better the input IQ, the better the output IQ and the larger the improvement. The stents for which we have sufficient data points could be ranked according to their visibility by decreasing order: Driver and Endeavor, Cypher, Vision and Xience, Taxus, Prokinetic.

Non linear versus linear registration

In this section we studied the impact of the choice of the registration technique (marker based or curve based) on DSE published in [START_REF] Bismuth | Elastic registration for stent enhancement in x-ray image sequences[END_REF]. On the first hand we computed the difference it created on the motion fields. On the second hand we studied its impact on image quality thank to image reviews.

Quantitative comparison of the transforms

We quantified here the differences between the similarity registration based on the mark- transforms that are equal on the markers do not differ much on the whole stent. In this section we aim to automatically and quantitatively compare the transforms.

The only way to measure this is to have realistic motion and deformation of the stent, t h eg u i d e -w i r ea n dt h em a r k e r s . W eh a v eu s e dt ot h i se n dad a t a b a s eo f1 4 4c l i n i c a l sequences of deployed stents with the balloons markers and guide-wires, that is a subset of the database presented in 2.4.2.1. We applied our marker and guide-wire detection algorithm to every sequence. In each sequence we chose a reference frame. We then registered every image of each sequence to the reference frame with the similarity transform and with the curve-based transform. Finally we averaged the registered images for each transform to produce the enhanced images.

For comparison purpose we denote S t 0 →t the similarity transform that is used to register t h ef r a m e si n[ CAW00, FNLR08, Koo05] and that actually registers the marker-balls.

It is the composition of a translation that registers the center of the markers, a rotation that aligns the axes of the markers and a scaling that actually registers the markers.

Let us denote P ′′ t the point of I t resulting of the application of S t 0 →t to the point P of I: P ′′ t = S t 0 →t (P ). For a given pixel to register, each transform generates a motion field that can be represented by a vector. We compared these vectors at any point P of I t 0 by computing the norm of the difference between the vector obtained with the similarity transform, PP ′′ t , and with the curve-based transform, PP ′ t . In order to quantify the difference for a whole sequence we averaged PP ′ t -PP ′′ t , along the sequence. We call the resulting image the transform difference map: I ∆ .L e tI ∆ (P ) be its value at a pixel P , it is defined by the equation:

I ∆ (P )= 1 n n t=1 PP ′ t -PP ′′ t (2.9)
An example of I ∆ can be observed in Fig. 2.28 (b). Black represents 0 and white any value above 2.75 pixel. The two dark halos demonstrate that the two transforms are equal around the markers. We can observe that the difference increases further away from the markers, especially in the area of the stent. In order to build a quantitative metric of the difference between the two transformations, we then defined a Region Of Interest (ROI) where we compare both transforms. This ROI must exclude the markers where there is obviously no difference and must take into account the area where we suppose the stent is. We chose a band around the guide-wire, 30 pixel wide, centered between the markers and whose length is half the length of the guide-wire between the markers. Fig. 2.28 (c) depicts such an ROI on a clinical example. Our quantitative measure to compare the 2 transforms is the average in this ROI of I ∆ . We denote this quantity ∆. Let |ROI| be the number of pixels in the ROI, ∆ is computed by: ∆= 1 |ROI| P ∈ROI I ∆ (P ) (2.10) Fig. 2.29 summarizes the measures of ∆ over the database. In 2.3.2.3 the precision of the registration versus typical stent dimensions is discussed. We found out that although stent struts are typically below the pixel, the observer who is interested in the overall shape of the stent can cope with a registration error up to the value of 2 pixels.

Meanwhile the blurring introduced by mis-registration impairs the visibility of the struts of the stent even with mis-registration errors of approximately one pixel. The histogram of ∆ demonstrates it is above 0.75 pixels for 68% of the sequences of the database. In 16% of the sequences ∆ is superior to 1.5. The two transforms are thus clearly different in a wide proportion of clinical sequences. On a significant number of them we expect great differences in the enhanced images. On Fig. 2.28 (d) for instance, that depicts the guide-wires of all the images of the sequence registered with the linear transformation, we can observe a misregistration of several pixels. By construction these guide-wires would perfectly superimpose with the our linear registration.

Impact of the transform on image quality

In this section we evaluated the impact of the choice of the registration on the enhanced image. We visually inspected the enhanced images with both registration techniques on a database of 144 sequences. Each sequence contains 30 frames. We reported if there was a significant difference on the stent and if the stent was better visualized with one of the registration techniques. The observed differences fell into two categories. Category A regroups the cases where the same details are visible but where one technique creates more blurring on the stent. Category B regroups the cases when one technique is so much better suited than the other one that we actually see more details with it.

Execution time

Our DSE technique implemented on a PC with a 3.2 GHz single-core processor performs on average in 16.6 s over a database of 40 cases with a standard deviation of 3.0s . T h e maximum execution time was 30s and the minimum was 13s. The algorithm is fast enough to fit seamlessly in the interventional work flow. With a dedicated implementation, on a multi-core Xeon X3450 processor with a 2.66 GHz clock speed, the average time drops down to approximately 3 s.

Comparison with existing software

We led a study to compare the output of StentViz with the one of another commercially available DSE software in clinical conditions with our partners from Hopital René Dubos.

This study was originally conducted to support the submission of StentViz to the FDA [Mor09]. In this context, in order to introduce StentViz on the American market, we had to demonstrate its "substantial equivalence" to an existing device, called "predicate device" in the FDA terminology and we chose to compare to StentOp from Paieon.

In order to demonstrate equivalence, we gathered a set of images and processed them with StentViz and StentOp. Then we organized blinded reviews with three clinicians independently where they rated and compared the image quality of the images produced by both softwares. The conclusion of the test was grounded on statistics and hypothesis testing.

Data collected and stent information

The study included 41 image sequences, originating from 28 different patients. They have been acquired on an Innova 2100 IQ system. Some of the most commonly used coronary stents worldwide have been imaged in the study. The following tables show the types of stents, the number of occurrences and the stent dimensions (table 2.4 and 2.5). They are typical of the classical distribution of stent types and dimensions encountered in common clinical practice. The observers were also requested to compare the visibility of the stents with StentViz and with StentOp, in a side-by-side blinded review and to rate it according to the 5 following classes:

• "Left ++": The image on the left is better than the one on the right because it enables to see more details.

• "Left +": The image on the left is better than the one on the right but the same details are visible on both images.

• "=": Both are equal.

• "Right+": The image on the right is better than the one on the left but the same details are visible on both images.

• "Right++": The image on the right is better than the one on the left because it enables to see more details. The results of the side-by-side comparison are presented in table 2.7. presents some images to illustrate the results of the two DSE products.

Results of the comparison

Discussion

Non linear versus linear registration

Although section 2.4.3 demonstrated that the non-linear registration outperformed performed linear registration, we must keep in mind that it is more computationally intensive. Indeed, the non-linear registration requires precise segmentation of the guide-wire to compute the motion fields using curvilinear abscissa and projections of points onto curves. Nevertheless, it is noteworthy that the overall execution time of the non-linear registration DSE is compliant with the clinicians needs. However some users may prefer

(a) (b) (c) (d) (e) (f)
an alternate trade-off between image quality and latency within the application.

An additional performance comparison between marker-ball based and guide-wire based registration may be made with respect to the accuracy of the stent diameter. Since clinicians can perform measurements on the enhanced stent to assess if it is properly deployed [Koo05, CAC + 09], a registration that preserves the actual diameter of the stent is preferred. As far as the stent follows the motion model described in 2.3.3.3,t h e guide-wire based registration preserves the stent diameter. On the contrary, there is no such guarantee with the marker ball based registration. Indeed, the linear transform includes a scaling to cope with the change of distance between the markers from frame to frame. The change in distance between the marker-balls can be the result of a change of curvature of the guide-wire due to the heart beat or a change of the angle between the markers and the image plane. In the first case, scaling the whole region of interest is not adequate because it will modify the diameter of the stent. Guide-wire based registration enables better image quality and probably more accurate stent diameters, whereas marker ball based registration results in faster processing.

Comparison with related work

Comparison of the technical aspects

There exists in the literature four teams that described similar techniques we can compare to. The first one, [CAW00, CAW02, CWA03], deals with transparent layer decomposition. These pioneer articles do not aim at presenting an automatic DSE algorithm.

They demonstrated that motion compensated temporal denoising based on the motion of the balloon can improve the visibility of stents and help a user to position more accurately its edges. The second team published a patent [START_REF] Florent | Medical viewing system and method for enhancing structures in noisy images[END_REF] describing a method to perform motion compensated noise reduction based on the detection of one or several markers. They work for the firm, Philips, that commercializes the DSE software called StentBoost. They cite the application to a pair of marker-balls for stent enhancement and describe a semi automatic method (it requires the user to input a region of interest).

It is similar to the one described here from a structural standpoint: marker candidates are detected, then pairs are formed in each image. The main difference of their approach versus ours is that they choose the best pair of markers independently on each frame without forcing the pairs to have a smooth motion within the image sequence. We notice that they pay particular attention to designing a marker ball detector that will not produce responses along uniform ridges and that they segment the guide-wire between the markers. Additionally, although they segment the guide-wire, they do not use it for In the definition of these scales, the rater had the responsibility of choosing for each clinical case the details to focus the rating on. These scales share some similarities with the one that we have employed, but the main difference is in the precise definition of the levels. We made explicit the details to be visible at each level in hope to make the rating as reproducible and objective as possible. As expected, the different authors observed an improvement in image quality following the application of DSE. Koolen found that rates had increased from 1.7 ± 0.6b e f o r et o3 .5 ± 0.8 after enhancement. Ohanessian observed an increase from 2.03 ± 0.76 to 2.76 + / -0.94. The improvements are thus respectively of 1.7 and 0.9 points out of 5 (after compensation of Ohanessian results to emulate a 5-level scale).

It is to be compared with the 1.7 point improvement we found. These positive results are in accordance with the noise reduction and contrast enhancement capabilities of DSE. It demonstrates that the potential inaccuracies of the registration that can impair the quality of the enhanced stent images are efficiently counterbalanced by the noise reduction and contrast enhancement.

On the clinical usefulness of DSE

One may wonder whether the demonstrated improvement in image quality end up in a clinical benefit. The study we led was not designed to support an objective assessment of this aspect since the enhanced images were not available during the procedures themselves. However, we relied on the experience of the readers to determine if the use of the enhanced images during the procedure would have increased the quality of the angioplasty. In our case, the two observers agreed that, in 13% of the cases, the enhanced image would have helped them to perform a better angioplasty. This question is very subjective and there is an important variability in the answers: the answer is positive in 40% of the cases for one observer and 19% for the second observer. Ohanessian [OSB + 08] pursued a similar goal by asking to the observers about the usefulness of DSE compared with conventional cine images. They report a proportion of 72% positive answers. Despite the differences in the figures, both their study and ours tend to show that the increase in image quality due to the enhanced image is of clinical value in a number of cases. The exact percentage and typology of concerned cases is not known and is probably difficult to establish. studied the relationship between the stent expansion quantification performed with this technique with respect to IVUS as gold standard. These five studies led to the interesting result that the relationship is linear with a rather good correlation (r ≈ 0.7). It is a promising step towards quantitative assessment of stent expansion using DSE. However DSE alone cannot provide any information regarding the apposition of the stent onto the vessel wall. The only recognized technique to perform this remains intra-vascular imaging.

The role of DSE in clinical practice

Selected cases

We illustrate the interest of DSE on a set of clinical cases where it happens to be especially relevant. The first case we illustrate (see The second case we consider deals with stent positioning. When a stent is positioned in continuation of an existing one, good clinical practice consists in overlapping them at the junction with the minimal achievable overlapping area. This is extremely challenging, and stent visualization can facilitate this task. On the left image of Fig. 2.34 the stent undeployed is positioned without overlap with the existing one. The clinician rectified this before stent expansion in Fig. 2.34 right.

The third case deals with bifurcation stenting. A recent popular trend [MCTTY10]

for these procedure consists in using a single stent in the main vessel that is inflated successively with different balloons to adjust its shape to the bifurcation and open the struts that jail the bifurcating vessel. In this context DSE can be used to visualize the modified shape of the stent. In Fig. 2.35 we can observe the uncommon shape of the stent resulting from this procedure.

Finally we present a rare but severe complication. In this case the patient presented at follow-up a coronary aneurysm at the very location where a stent had been deployed (Fig. 2.36). DSE at this location enabled to determine that the stent had fractured, damaging the artery. It allowed to understand the precise location and size of the orifice of the aneurysm. A specific treatment option (2 coils and 2 stents) has been performed

to prevent the aneurysm from further inflating and possibly rupturing.

Hardware vs software DSE

The method discussed in this chapter relies on a standard Xray acquisition complemented by the use of specifically designed image processing algorithms. One may wonder if a specific Xray acquisition could produce the desired enhancement in stent CNR, without invoking image processing. To yield similar enhancement to the accumulation of 30 frames by the DSE algorithm, a single Xray shot shall deliver 30 times the conventional dose. It results on constraints on the tube and on the detector. The tube peak power shall support delivering such dose in less than 10ms (not to introduce blur), and the detector shall not saturate. It is approximately 6 times the capacity of an Xray tube, and 3 times the saturation level of a detector. None of these constraints can be fulfilled todays nor in a near future.

Observed limitations of the technique

In 7% of the cases, stents do not appear clearly after stent enhancement (IQ scores equal to 1). There are various explanations that we can propose for this. The first one is that although the registration was perfect, the input CNR was so small that noise reduction was not efficient enough to make stent struts visible. Our set of test sequences includes on purpose approximately half of the sequences in challenging imaging conditions. Although this is much more challenging than daily clinical practice, we believe that it is not a good explanation for every case. Some of the low scores have been obtained in good imaging conditions. We do not have a final explanation, however we suspect that in a significant proportion of the cases there was registration error (Fig. 2.38 (a)). Since the landmarks are almost always very accurately detected by our method, we think that the registration errors are due to the fact that the stent does not follow the expected motion. We identified two cases. First, there can be motion between the stent and the landmarks since they are not rigidly linked. A visual inspection of the database indicates that in some critical cases this motion can exceed 10 pixels. Our method does not behave well in these cases. Secondly, the motion of the stent occurs in 3D and may not be compensated by 2D image deformations. Fig. 2.37 shows a stent under two view points differing by a rotation of a few degrees around the long axis of the stent. We can observe that the appearance of the struts is completely different and therefore cannot be compensated by a 2D registration. A potential solution to theses cases where stent registration is not perfect, could be to select a subset of images in the sequences in which the motion of the stent is less significant. Ross [RLM + 05] noticed on one clinical case that using a subset of frames restricted to a specific interval of the heartbeat yielded a sharper stent image, similarly to Zaid [ZHB + 08]. This research direction needs further studies to be confirmed. The registration model we used is also challenged in the case of multiple stents at a vessel bifurcation. In such a case there is typically one stent in the main vessel and another one in a side branch. The presence of the landmarks in one of the vessels is not enough to predict the motion of the other vessel. Therefore the second stent is usually blurred as a consequence of the incorrect registration. This clinical situation would require extending the method to detect and register landmarks in both vessels. Fig. 2.38 (b) shows an example of a result of stent enhancement at a bifurcation.

Another limitation to stent visualization is the presence of structures that are superimposed to the stent and hide it. The landmarks for instance, and especially the guide-wire, impair the visibility of some stent struts. Moreover, in some clinical situations, highly radio-opaque sternal wires that do not follow the motion of the stent can severely degrade its visualization. Specific algorithms [START_REF] Funck | Guide-wire subtraction in enhanced stent images[END_REF] have been designed to address these limitations, the main one being discussed in the next chapter.

(a) (b) Therefore, the stent in the side branch is not registered as accurately as the one in the main branch and is blurrier.

Conclusion

We have presented a comprehensive approach to DSE. We studied the problem from a clinical standpoint to define the requirements on the solution. The most original parts of our DSE technique, the guide-wire segmentation and non-linear registration, have been

Introduction

Digital stent enhancement has been presented in Chapter 2. This image processing technique enables the visualization of the stent with conventional Xray in the cathlab.

The presence of the guide-wire in the input image sequence has proven to be useful to accurately estimate the motion of the stent that is key to the sharpness of the DSE image.

However, from a visualization perspective, the guide-wire has no interest and introduces difficulties. Indeed, the stent is a very fine mesh of wire of very low contrast whereas the guide-wire is of much larger contrast.

Background

In multimedia image processing, the task of removing the guide-wire would typically be addressed with inpainting techniques, marking the guide-wire pixels, and replacing their original values by computed ones according to some prior on the image [BSCB00, DCOY03, CPT03]. Typical priors include the regularity of the isophote lines [START_REF] Bertalmio | Image inpainting[END_REF] for instance. Although multimedia image editing techniques have been applied to X-ray images [BDN09], we note that there is a fundamental difference between both image types: in X-ray images the guide-wire does not occlude the stent. On the contrary, both objects superimpose. Therefore, on the pixels of the guide-wire, the stent information is also theoretically present (though much weaker than the guide-wire signal, thus almost 0 The work presented in this chapter is covered by two patent applications [BV10, VB10] and was the subject of an oral presentation at the EuroPCR 2010 conference associated with an abstract published in EuroIntervention [START_REF] Funck | Guide-wire subtraction in enhanced stent images[END_REF]. invisible with a regular display). We aim at retrieving this information that is naturally present in the image rather than guessing a likely image content. This is the reason why we prefer to invoke the formalism of layer separation in transparent images rather than inpainting.

The transparent layer model for Xray images

Transparent images refer to images where the observed intensity of a pixel is the sum of the input intensities of the rays coming to the pixel attenuated by the integral of the attenuation along their paths according to the Beer-Lambert law [START_REF] Bushberg | The essential physics of medical imaging[END_REF]. According to this model, if a ray r j of input intensity Nj 0 , crosses a medium of attenuation µ(p)a t a spatial position p, the output intensity i(r j )o ft h er a yi s :

i(r j )=Nj 0 .e In this case, the image formation mechanism is modeled as X-rays crossing the layer plans. We denote I the Xray image, p a pixel location and I(p) its intensity. According to this model, if a ray r j of input intensity Nj 0 , crosses n planes at points of attenuation µ i , the output intensity of the ray is according to the Beer Lambert law:

i(r j (p)) = Nj 0 .e - i µ i (p) (3.2)
The value I(p) of the pixel a point p is the sum of the intensities of the rays reaching p:

I(p)= j i(r j (p)) = j Nj 0 .e - i µ i (p) (3.3)
Moreover, we generally assume that one ray only having a straight path from a pointwise X-ray source reaches a point-wise pixel detector. This model is simplistic and does not take into account many of the specificities of X-ray images such as scatter radiation or beam hardening for instance. However it is very practical to handle and More precisely, the transition from a 3D volume to a set of planar layers can be thought as a set of successive projections: Let us consider a 3D volume Ω through which the rays travel. We associate an attenuation factor µ(q)t oe v e r ypo i n tq of this volume.

The image intensity at a location p is the integral of the attenuation along the ray r(p) reaching this pixel:

I(p)=N 0 .e -q∈r(p) µ(q) (3.5)
Now let us consider a partition {Ω i } i of the volume Ω, the equation rewrites:

I(p)=N 0 .e -i q∈r(p)∩Ω i µ(q) (3.6)
We observe immediately that it is equivalent to an image formed with a layer model where the layers are defined by their attenuations {µ i } i following:

µ i (p)= q∈r(p)∩Ω i µ(q) (3.7)
This illustrates the generality of the layer model. A layer decomposition is thus any partition of the imaged volume. Generally the volume is split into layers that make sense from a physical/clinical point of view: organs or medical devices for instance. It is important to keep in mind that a planar layer is not the model of a planar object, but the model of a 3D volume as it appears under a given projection angle.

Layer separation in transparent images

We propose to consider the guide-wire subtraction task as a layer separation problem in X-ray images (which refers to decomposing an input image into the different theoretical layers composing it, i.e. estimating the layer images). This problem also arises in radiology for applications different from stent visualization where the layers correspond to different organs, bones, vessels or the interventional tools of a clinician (stents, balloons, catheters...). It is obviously an ill posed problem that consists in estimating many images (the layers) from a single one (the transparent image). Although it is an active research topic, current techniques only allow layer separation in some very special cases.

Close [START_REF] Close | Improved Localization of Coronary Stents Using Layer Decomposition[END_REF] proposed to process a sequence of moving images and to separate layers assuming that their motions are distinct (for instance to separate a static background layer from the moving layer of an artery of the heart). They proposed to estimate the motion of a layer, to produce a stabilized sequence where this layer is made static and to average the stabilized sequence. In the resulting image, the other layers that were not stabilized are blurred whereas the fixed layer is enhanced (denoised). Such a technique relies on strong hypotheses that limit its applicability:

• it assumes that the motions of the different layers are distinct. Therefore two layers undergoing the same motion cannot be separated.

• It assumes that layer motion can be estimated. This can be very challenging since the general intensity invariance hypothesis that is the basis of optical flow methods does not hold in transparent images. Therefore, motion estimation in transparent images is only feasible in a more reduced number of situations [ABL09, SABM04, TOM00].

• Moreover it assumes that the 3D motion of the layer can be compensated by 2D registration in the projection images.

Close et al. presented their general method with two main applications: vessel visualization enhancement and DSE. As previously mentioned in Chapter 2 this team was the first one to expose the concept of motion compensated averaging for DSE.

DSE can therefore be seen as a layer separation process, where the layer regrouping the structures following the same motion as the landmarks is separated from the other ones.

The strong hypotheses of the method of Close are generally well satisfied in this context, as previously discussed in Section 2.5:

• The stent is animated by the motion of the coronary segments it lies in, which is different from the background anatomy motion and the motion of the other coronary arteries.

• The motion of the stent layer can be estimated thanks to the presence of landmarks:

guide-wire and balloon marker-balls.

• Motion compensation based on 2D non linear registration generally yields satisfying results.

However, since the stent and the landmarks have similar motion (it is the main hypothesis of chapter 2), they cannot be separated with this technique and as a consequence DSE produces an image where both are visible together.

All the other woks on layer separation deal with applications that are different from DSE. The two most common ones are vessel layer separation in coronary angiograms and non medical multimedia applications. Sarel and Irani [START_REF] Sarel | Separating transparent layers through layer information exchange[END_REF] proposed a technique to separate two layers when one of them is moving pseudo-periodically in a sequence of images and another method to separate layers when two images are available [START_REF] Sarel | Separating transparent layers of repetitive dynamic behaviors[END_REF].

Several other methods have been proposed to separate layers when a sequence of images is processed. Shizawa and Mase [SM91] exposed a method in the 3D Fourier space for the special case where the layers move at a constant translational speed. To conclude this review of the literature, all known layer separation techniques require a set of several images. The case of the guide-wire layer that we are addressing has some particularities that make it solvable with one single image. We explain in the next section a dedicated technique to estimate it directly from the stent enhanced image.

Method

In the context of stent visualization we propose to consider a three layer model. The first layer is the anatomical background, the second the stent and the third the guide-wire.

In such a model, we aim removing the guide-wire and background layers.

Layer separation in DSE images

We first apply the log to the DSE image to have a linear relationship between the layers, where the value of a pixel is simply the sum of the values of the layers crossed by the Xray (Eq. 3.8).

I 1 (p)=ln(I(p)) = ln(N 0 ) - i µ i (p) (3.8) I 1 (p)=ln(N 0 ) -(

Guide-wire layer separation

In order to constrain the ill-posed problem of estimating the guide-wire layer we introduce a-priori knowledge. We define a mathematical parametric model of the guide-wire and estimate it based on the DSE image. Injecting the estimated parameters inside the model allows the generation of the guide-wire layer, that is further subtracted from the DSE image.

The guide-wire is accurately described by a curvilinear cylinder of circular section.

Assuming that the angle formed between the incident X-rays and the guide-wire is constant over the piece of guide-wire that is considered, we can state that its absorbency is a function of the distance to its centerline only [START_REF] Bismuth | Shape from radio-opacity for interventional devices 3d[END_REF]. We want to emphasize that we do not assume that the guide-wire is parallel to the image plane. We only assume that it forms a constant angle with the imaging plane. It is a far less restrictive and more realistic hypothesis. The guide-wire section is typically composed of several concentric layers, the core (typically in stainless steel), coils or cover and coating composed of different materials [ENS + 10] (see Fig. 3.7). Its tip, that is not the portion of interest in our case, has a different composition that make it more flexible and more radio-opaque. In order to compute an estimate Ĉ of C we segment the guide-wire in the image.

Several techniques are suitable for this task. The one we use is detailed in Section 2.3.3.2.

Once Ĉ is known, we estimate α. We could argue that based on the exact composition of the guide-wire and of the imaging system response one could derive α. Although true from a theoretical standpoint, it turns out to be a difficult topic in practice. A precise estimation of α would have to be tuned to the particular composition of the layers composing each guide-wire, to the angle between the guide-wire and the incident rays (that is unknown), and to the precise system Mean Transfer Function (MTF) that mainly accounts for blurring and sampling in the physical imaging chain. This is reason why we rather propose to estimate α from the data available in the image. In order to estimate α(d g )f o rag i v e nd g , we consider the set of values {I 2 (p)} p∈V (dg) of all the pixels in the image at distance d g from Ĉ with a tolerance δ (see Eq 3.12). Then we estimate a representative value from this set, for instance by computing the average or the median, that we assign to α(d g ). In practice for d g superior to a typical guide-wire radius, α(d g ) is set to 0. Knowing Ĉ and α(d g ) we can compute the value of the guide wire at any pixel and thus compute the guide-wire layer:

V (d g )={p |-δ<d (p, C) -d g <δ} (3.12) α(d g )= 1 |V (d g )| p∈V (dg) I 2 (p)o rM e d ( I 2 (p)) for p ∈ V (d g ) (3.13) μguide (p)=α(d(p, Ĉ)) (3.14)
The guide-wire layer is then subtracted from the image to produce the output image

I ′ . I ′ = µ stent + µ guide -μguide (3.15)
In the resulting image the guide-wire is erased while preserving the image content.

Fig. 3.9 and 3.10 show the application of the guide-wire subtraction between the two radio-opaque marker-balls and the estimated guide-wire layer.

Simultaneous display of two DSE images

General technique

The guide-wire subtraction procedure previously described generates an additional image over the classical DSE one. For safety reasons it is preferable to display both to the clinician, in case the guide-wire subtraction had created artifacts, or had removed some image content. However, from an ergonomical standpoint, having two images to review is cumbersome. The clinician would have to switch on the system from one to the other, false relationship/distances between anatomical features and potentially remove some relevant image content. Therefore we rather look for an optimal crop of the images, since it guarantees that the geometrical relationships are preserved. We take advantage of the fact that most of the time, when we want to display several images together we do not have to display them totally, but that only a given region in each image is of interest. We propose to process images automatically to determine this area of interest and to crop the images in a potentially non rectangular manner to make them fit into one screen with no (or minimal) loss of resolution. For instance in an image of a coronary artery, the area of interest to the clinician is just a band of pixels around the artery, and the rest of the image can be cropped out. An additional difficulty appears then because the resulting images after cropping are not square nor rectangle anymore. However, in some particular cases, a set up can be found that allows to display them together with much less down-scan than if they had not been cropped. We illustrate this in the case of displaying two images of a same deployed stent on one screen.

Based on automatic processing, we infer the position of the stent, its privileged direction and its dimensions (length and diameter) that are similar in both images. In our case, for DSE images, we can rely on the marker-ball and guide-wire segmentation previously presented. It enables us to define in each of the two stent images an area of interest. Then we split the image for display into two areas (area A and area B) by a line passing through the center of the image and of same direction as the direction of the stents. In the first half of the image we will place the first stent so that none of its area of interest is out of area A. If necessary we will down-scan the first stent image to make its area of interest fit in area A. Similarly we will position the second stent image in area B. In order to maximize the zoom factor we position the image with the minimum down-scanning that allows the areas of interest to fit within the half images. From a practical standpoint, we decided to split the images only in a given set of four predetermined directions (horizontal, vertical, and the two diagonals) and to chose among these directions the one that is the closest to the direction of the stent. On Fig.

3

.12 simultaneous display of stents is illustrated, choosing among the four predetermined orientations. The area of interest used for this display is illustrated on the image on the right, it is the union of the 3 colored squares.

Implementation details

The DSE images (with and without guide-wire subtraction) undergo up-scan and cropping before being displayed in one single image. There are two constraints to fulfill to produce the final image: the zoom factor shall be as close as possible to the one of the regular DSE image, and the stent shall be fully displayed. The area of interest is a band of pixels around the stent, that has been determined to be of approximately 8mm on each side of the guide-wire. It allows to display the full stent (whose diameter is typically 2.9 mm and at maximum 4.5 mm -see Table 1.1 and Section 2.4.2.1)a n di f necessary a part of bifurcating stent. Taking into account a typical conversion factor for cardiac interventions of 1.4 mm/pixel for the current design of the GE systems, this band shall be approximately 60 pixel wide on each side of the guide-wire (thus a total of 2 × 60 = 120 pixels). Our task consists in cropping the images while making sure that the area of interest is preserved. For the horizontal (resp. vertical) stents we can extract For the diagonal cases it is a bit less straightforward. We test for zoom factors between 1.5a nd2.8 several different diagonal crops and retain the crop with the highest zoom factor where the 120 pixel wide area of interest is preserved. In practice we test with a simplified area of interest defined with a set of 3 squares, each 120 pixel wide, centered on both makers and the central point of the guide-wire (see Fig. 3.12).

Results

We display here a picture gallery of the results of the guide-wire subtraction in clinical conditions (Fig. 3.15 to 3.26). The overall level of the results looks good. Every figure is accompanied by a comment on the performance of the subtraction technique and when it is relevant on the clinical content. The method and many of these results have been presented at an oral presentation at the EuroPCR 2010 conference and are associated with an abstract published in EuroIntervention [START_REF] Funck | Guide-wire subtraction in enhanced stent images[END_REF].

In order to compare the relevance of the median or the average estimators to estimate α (Eq. 3.12) we also illustrate the guide-wire attenuation profiles estimated in 10 clinical sequences (Fig. 3.13). The estimated profiles with both estimators generally yield satisfactory results: The attenuation profile is globally decreasing with the distance to the guide-wire centerline, converging to null attenuation far enough from it. We note a minor numerical artifact: some curves slightly decrease beyond 0. This is due to the fact that the level 0, defined versus the background that is itself estimated, contains a degree of uncertainty.

We observe that the highest curve seems to be different from the other ones. It can be explained by the corresponding image (Fig. 3.19) that contains an unusual amount of stent information, because of the particular procedure in which a new stent is deployed inside a pre-existing one. The additional amount stent metal tends to generate an overestimation of the guide-wire attenuation in our method. We consider that the median performs better than the average on this case given that the curve converges to a value closer to 0. However the resulting images a visually almost indiscernible. This remark happens to be general over our dataset: in almost every case both estimators yield similar images. In one case only, the difference is noticeable (Fig. 3. [START_REF]2 Results of the algorithm vs ground truth for each different stage[END_REF]. The particularity of this case is that the guide-wire is at the same distance from the stent border in the whole segment of interest. Therefore the stent border pixels pollute the estimation at this very distance. The median happens to be more robust to this situation than the average. We thus recommend the use of the median estimator for task of estimating the guide-wire attenuation profile α.

Moreover we observe that the estimated guide-wire profiles are significantly different from the theoretical one presented in Fig. 3.8. We assume that it is mainly due to the system MTF: the profiles we estimate are likely to be low-pass versions of the theoretical ones.

Discussion

The benefits of guide-wire subtraction

The first benefit of the guide-subtraction is the comfort it brings to assess stent deployment. The clear view of the stent, as illustrated in the previous image gallery, and the visualization of the stent struts and border without obstacle is helping the clinician. In the cases where the guide-wire is stuck to the border of the stent, it can be of significant clinical interest. Such a case, in Fig. 3.27, depicts an non straight stent border beneath the guide-wire that was not straightforward to detect without the subtraction. In one of the cases that we have processed, illustrated on 3.18, the subtraction makes a large dark area appear behind a segment of the guide-wire that may be a calcified plaque.

From a qualitative standpoint, we notice that the guide-wire subtraction brings more information in the cases where StentViz result is particularly good (IQ score 4 and 5

typically on the scale defined in Section 2.3.1). Indeed if the IQ is poor, there are less details to reveal in the narrow band of pixels concerned by the processing.

A potential benefit of guide-wire subtraction is easier and more optimal setting of the contrast of the image on the stent signal. Indeed without the guide-wire subtraction an image windowing that would be optimal for the stent would result in saturation all over the guide-wire. This benefit has not been much investigated in this study but is illustrated on Fig. 3.28. Finally it seems that the removal of the guide-wire that is a strong signal along a curve makes it easier to assess the parallelism of stent struts. This hypothesis would require further experiments to be demonstrated.

Position of the guide-wire subtraction in our processing chain

We have presented in this chapter a scheme where the guide-wire subtraction is the last piece of the DSE image processing chain. However the technique is general and applicable at other stages of the chain provided that the background layer has been removed. We assume that the results would be similar especially with the average estimator for α:

The specificity of our non linear registration is to register the levelsets of the distance to the guide-wire among the images. Since it is exactly the sets that we compute in V (d g ), the estimation of α by averaging and the registration commute. Moreover it commutes also (obviously) with image combination by averaging. Therefore it would yield the same result to perform guide-wire subtraction right after background removal in each image independently or at the very end of our DSE processing. We prefer to perform it once only on the final DSE image to avoid unnecessary computations.

We note that it is not possible with a linear registration in the DSE algorithm. The guide-wires would not be registered and could therefore not be estimated in a similar manner. One would have to proceed to guide-wire subtraction before registration.

Limitations

We identified two root causes for the cases where guide-wire subtraction creates artifacts.

The first one is that the guide-wire may not be accurately described by the parametric model we propose. More specifically, it can happen that its contrast is varying along its curve, whereas the model assumes that the intensity profile is the same at any point of the curve. This may be explained by variations of the angle of the guide-wire with the incident Xray beam as explained in [START_REF] Bismuth | Shape from radio-opacity for interventional devices 3d[END_REF]. The second cause of failure of the technique are errors in the estimation of the model from the data. In some cases the segmented guide-wire is not well centered on the actual one that results in artifacts after subtraction. In some other cases the estimation of the intensity profile results in an erroneous profile. Future work could include constraints on the intensity profile such as monotonicity, or the fit of a theoretical guide-wire profile model to the data observed in the image.

The layer separation technique presented here could moreover be extended to other components of the DSE image. In our approach we did not subtract the guide-wire layer outside of the segment delimited by the marker-balls because our estimation of the guide-wire centerline in this area. Therefore when the distance from the markers increases the subtraction creates artifacts (typically where the guide-wire is not accurately segmented/registered). The extension of the subtraction outside of the markerball segment would probably require an improved guide-wire segmentation in this area.

Finally, parametric layer separation could also be extended in an attempt to subtract the marker-ball.

Conclusion

The framework of transparent layers has been applied successfully to the removal of guide-wire in enhanced stent images. It found here a clinically relevant application.

The use of parametric models, that enables its resolution may be applied successfully to other situations. The technique described in this chapter is the basis of the second commercialized version of StentViz. The feedbacks from the clinicians about it are positive. They consider that in daily practice it facilitates the visualization of stents, and in some cases resolves ambiguities. The key points of our method are the bottom-up approach, building primitives of increasing level of confidence, and the incorporation of the 3D properties of the object to track. The results on 22 clinical sequences are the best reported so far in this field.

Moreover, the work we present regarding guide-wire subtraction and registration are new developments in the domain of 3D stent reconstruction.

Background

Clinical Background

The topic of stent visualization inside the cathlab has been extensively presented in Chapter 1.I nC h a p t e r s2 and 3 we presented technical developments to enhance the visibility of stents in projection images and subtract the guide-wire. These techniques, by improving the signal to noise ratio of stent images and removing disturbing structures, aim at producing the best possible 2D images out of a set of conventional Xray

1 Part of the work presented in this chapter has been done with Angela Chieh during her master's thesis internship. Quero agradecer a Angela por sua contribuição durante sua tese de Mestrado. I also want to thank Liliane Ramus for her collaboration and her support with the reconstruction and visualization softwares. images. However, one of the key characteristics of stents, its three dimensional (3D) structure, has been neglected so far.

Conversely, intra-vascular imaging, like IVUS and OCT, presents the stent as a stack of 2D slices that better renders its 3D nature and enables the precise quantification of its expansion in every direction. For the sake of completeness, let us mention that Computed Tomography (CT) also enables 3D stent reconstruction. However, its temporal and spatial resolution does not allow to precisely visualize coronary stents.

In daily clinical practice, the 3D nature of the lesions and of the stents is systematically taken into account through repeated imaging under different viewpoints. Fig. 4.2 illustrates an under-deployed stent where only one of the two viewing angles allows to detect the defect. A potential solution to grasp the 3D nature of the stent from Xray images could be to repeat DSE under several viewpoints. However a 3D stent reconstruction is a more appealing objective and achieving such reconstruction is the aim of this chapter.

Beyond the routine cases, a 3D stent reconstruction would be particularly useful in the complex ones, like bifurcations and overlapping stents, where the 3D stent shape is particularly complex.

State of the art

3D stent reconstruction

The first attempt to reconstruct coronary stents with conventional Xray has been performed by Close [START_REF] Close | Fluoroscopic 3d reconstruction of coronary stents[END_REF], who demonstrated the feasibility of motion compensated stent reconstruction. The work that we present here is in the continuity of the work of

Marker detection and tracking

The spin acquisition used to compute the 3D stent typically involves 150 frames. The manual detection of the balloon markers is clearly impossible in daily clinical practice and has to be automated. One of the goals of the present study is precisely to design and validate a fully automated marker detection algorithm. The challenges raised by this task are the following: first of all, the balloon appearance and its 2D apparent motion change significantly along the run, as the acquisition system is rotating. The balloon appearance commonly changes from two distinct markers to both markers superimposed. Moreover, it can be superimposed in some parts of the run to highly radio-opaque structures (catheters, or wires) hiding it. Finally a significant number of anatomical disturbing elements impairs its detection. These situations are illustrated in Fig. 4.4. + 08] have exposed some results on automated marker detection and its impact on the quality of the reconstruction. They obtain 84% of correct detection but do not give much details about the algorithm they use. They report that this performance is enough to produce 3D reconstructions similar to the ones obtained by manual marker localisation.

Schoonenberg et al [SFL

Overview of the chapter

The chapter is structured as follows. We first present a fully automated marker tracking algorithm for rotational acquisitions (Sections 4.3.2). The specificities of the 2D DSE algorithms that we exposed in the previous chapters are extended to the 3D case in and discussed (Section 4.6). Finally, conclusions are drawn.

Our main contributions are on the one hand the description of a fully automated algorithm for marker tracking in spin acquisition that yields, to the best of our knowledge, the best performance reported so far and, on the other hand, the extension to 3D of the specificities of our 2D DSE algorithm: non-linear registration and guide-wire subtraction.

The necessity of a new algorithm

Method 4.3.1 Clinical sequence database

The database is constituted of 22 clinical sequences acquired on 11 different patients.

For each patient it contains a sequence with the balloon deflated and another one with the balloon inflated to reduce the motion between the balloon and the stent [START_REF] Perrenot | Reconstruction tomographique 3D de stent coronaire avec prise en compte du mouvement en angiographie rotationnelle cardiaque par rayons X[END_REF]. In the presentation of our data, we use the labels 1 to 11 for the sequences with the balloon inflated and 1a to 11a for their counterparts with the deflated balloon. The sequences have been acquired on an Innova 2000 system (GE Healthcare). The pixel size is 0.2 mm, the framerate 30 fps, and the angular coverage 200 o . For evaluation purposes, we have manually marked, on each sequence, the position of each marker. It enables the computation of the TP, FP and FN rates.

Marker detection and tracking in rotational acquisitions

High-level architecture of the algorithm

The object that we want to detect and track is an angioplasty balloon delimited by two marker-balls at its extremities. Each marker is a small (5 pixel diameter) radio-opaque ellipsoid and both of them are linked by a guide-wire whose visibility varies significantly depending on its properties, on patient size and on the imaging angle. The 2D apparent properties of this balloon change dramatically along the image sequence as a consequence of the rotation of the image chain around the patient. The challenge is to build a robust and fully automated algorithm for the detection and tracking of the marker-balls. This algorithm shall output the precise position of each marker in every image of the sequence and shall label each marker to enable 3D reconstruction. It is very challenging to detect the correct markers among false alarms on each frame independently. Therefore we use the smoothness of the motion of the markers from frame to frame and the conservation of their appearance properties over some frames to achieve accurate detection among a set of pre-detected candidates. We design a bottom-up approach that is building primitives of increasing level of complexity and confidence: firstly points, then pairs of points, then short tracks of pairs and finally a full track of pairs. This single track obtained at the end of the processing is used to determine a 3D marker pair model and to compute the motion-compensated tomographic reconstruction of the stent. The first stages of marker detection are similar to the ones presented in Chapter 2 for DSE.

From a high level perspective, our detection and tracking scheme performs as follows:

images undergo a pre-processing to ease the marker detection process, then a series of potential markers are detected in each frame, and are grouped into potential pairs of markers. Based on typical markerball motion parameters, a tracking algorithm regroups the pairs into short tracks. Once the entire sequence has been processed the short tracks are merged in an iterative process that produces longer tracks until convergence to a single track representing most of the frames, or until no tracks can be harmoniously merged together. A refinement step is applied to the selected track in view of completing it and improving it. At this stage a 3D marker pair model is estimated and used to perform marker labeling and a final refinement that reduces FP and FN. The overall structure of the algorithm is illustrated in Fig. 4.5.

Pre-processing

Contrasted objects in the image include not only our object of interest but also a number of anatomical structures which create potential false alarms. The main properties of the marker-balls are their small size and their high radio-opacity (they are more radio-opaque than common anatomical structures). Background intensity variations as well as objects larger than the marker-balls are eliminated by a black top-hat transform (structuring element of size 9 like in Chapter 2). The details that remain after the transform are those that were, in the original image, darker than the background and smaller than the structuring element. Therefore, not only the marker balls are present in the top-hated image but also are the guide-wire, the stent, parts of the catheters, bone edges, sternal wires and noise. Among these features, the sternal wires are the main source of FP and degrade the performance of the algorithm. We designed a higher level process to remove them. They are easily identified based on their large radio-opacity and spatial extent.

Pair detection

In a first step we identify marker-ball candidates in the transformed image by selecting the relevant local minima. The relevance of a minimum is assessed based on its amplitude, on the local noise variance, and on the amplitude of other surrounding local minima. The marker candidates are then paired together based on geometric criteria (min and max distance between candidate points) and the resulting pairs are sorted according to the relevance of the markers composing them. Finally a predetermined number of pairs are retained in each frame. The thresholds are such that the ground truth markers are selected in more than 95% of the frames on clinical test sequences. In the next stages, we explain how we use temporal coherence to choose within this set of selected pairs the one that actually contains the markers.

Short track construction

Tracking consists in grouping together marker pairs that appear consistently over frames.

Because of the rotation during the acquisition, the appearance of the markers is very variable over the sequence, making tracking a more challenging task than in DSE. We propose at this stage to regroup marker pairs together over sets of frames where their appearance and motion properties are invariant enough. This first level tracking is a causal algorithm, that outputs a catalog of tracks which length is limited to some dozens of frames. The catalog is built by considering the succession of frames in chronological order2 . For each frame the algorithm updates the tracks based on the detected pairs.

Each pair is associated to the track that is considered the most probable or is used to initiate a new track. The probability for a given pair to be the continuation of a track is estimated based on a set of cinematic parameters (marker segment variation in position and orientation, direction of the motion and speed), image based parameters (correlation of a neighborhood around the markers) and track related parameters (the number of appearances and absences of the considered track). The essential parameters of this probability function have been estimated on a large set of short clinical sequences.

The tracking algorithm differs from the one of DSE to take into account specificities of rotational acquisitions: First of all, the distance between the markers can become zero when the viewing angle gets aligned with their axis during the rotation. Moreover the angle and length variations are far larger in the rotational acquisitions than in the DSE sequences. These two specificities have been taken into account by adapting the cost functions of the tracking. Finally rotational sequences are significantly longer -30 frames for DSE, 150 for spin acquisitions. In order to have accurate short tracks at this stage, we forbid new detections to be associated with the tracks that have not been updated since a maximal number of frames.

Track merging

Presentation of the algorithm At this stage the correct markers typically appear in some of the short tracks stored in the tracking catalog among other tracks of false alarms. Statistics on the catalog show that in more than 50% of the cases the markers are scattered in several short tracks. In such cases it is necessary to merge tracks to regroup the markers. Therefore, we aim at merging together the tracks containing the markers to build a single long track. In order to differentiate marker tracks from false alarm tracks and drive the merge we rely on three properties:

• Marker tracks are generally longer than false alarm tracks,

• marker tracks are smoother than false alarms tracks (according to the parameters listed in the tracking),

• two consecutive marker tracks usually merge in a smoother way than two false alarms tracks or than markers and false alarms.

Algorithm

The track-merging algorithm proceeds as follows: for each two tracks in the tracking catalog, it computes a score associated to the action of merging them.

Then, it finds the two tracks that merge with the best score. If this score is higher than a threshold, it merges the two tracks together to form a new track. This new track is added to the track catalog and the two merged tracks are removed from it. Otherwise (if the score is too low) no relevant merge can be achieved within the catalog and the catalog is un-modified. An additional stopping criteria is added to this first one to stop it once a long track covers most the frames: the process of merging tracks is stopped as soon as a track covers more than 95%.

The track merging score computed for each pair of two tracks in the catalog is the combination of:

• a track confidence score that favors tracks that have high probability of being actual marker tracks,

• a continuity score that favors tracks that merge smoothly,

• a novelty score that helps fill the missing frames as much as possible.

The track confidence score is similar to the one used to determine the marker track We then define the set of couples of points ξ(C, D), where two non-overlapping tracks C and D merge: • the gap between the two tracks: |i -j|.

ξ(C, D)={(c i ,d j )|c i ∈ C, d j ∈ D and ]min(i, j),max(i, j)[∩(I C ∪ I D )=∅} (4.1)
• the distance d between the centers of the pairs.

• the variation of length of the pairs ∆l.

• the variation of angle ∆θ.

• the correlation c between patches centered on the extremities of the pairs.

We compute it with the following formula, where the σ x are sensitivity parameters that have been set on our test database:

ω(c i ,d j )=1-e -( |i-j| σg + d σ d + ∆l σ l + cos(∆θ)-1 σ θ + c σc ) (4.2)
An overall continuity score is computed as:

ω(C, D)= 1 #ξ(C, D) (c i ,d j )∈ξ(C,D) ω(c i ,d j ) (4.3)

Determination of the marker track and refinement of the track

At this stage the tracking catalog contains a set of long tracks. In order to identify the one that is the most likely to contain the actual markers we use a metric similar to the confidence metric presented in the last section. The track that raises the best score is selected. The confidence in the track selection is high and the selected track is the only one that will be considered for the remainder of the algorithm. It typically contains most of the markers (≈ 85%) of the sequence but lacks some markers and includes a small proportion (typically a few percents) of false alarms. This is below the target we aim at, (see Section 4.2.3) and probably suboptimal for 3D reconstruction. The refinement step that we describe hereafter aims at solving these issues. The first part of the refinement identifies the frames where wrong markers (false positives) were detected.

The track being known, its typical motion parameters (namely frame-to-frame variation of length, orientation and position) can be precisely estimated. The frames where the variation are statistically unlikely are removed. The second part of the refinement detects the markers in the frames where they were not previously detected. The fundamental hypothesis guaranteed by the acquisition protocol is that the markers are present in every frame. In a given frame where the markers were not found, the search area and

D(p)[i]= D(p)[i] -µ(D(p)) k p σ(D(p)) (4.4)
We gather the normalized measurements for all the parameters length l,a n g l eθ, position x and y in a vector D[i]:

D[i]= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ Dl [i] Dθ [i] Dx [i] Dy [i] ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
We reject a frame (considered false positive) if:

D[i] ∞ ≥ 1. (4.5)
The philosophy of this test is to remove detections that are unlikely to belong to the distribution of measurements. This test is similar in its form (threshold of the type µ + kσ) to typical statistical tests. We observed that the method gives satisfying results by using the second derivative as a measure of the parameter. It can be explained by the fact that the parameter itself and its first derivative are put under control by the tracking. The sensitivity parameters k p are typically of the order of 5.

False negative reduction

The chosen track originally contains some FN. Their proportion is most of the time increased by the FP reduction that transforms the detected FP into FN. This motivates the design of an FN reduction block following the FP reduction one. We refine the pair extraction for the FP frames by considering an ROI adjusted based on the detections in the closest previous and next frames (resp. indexed i p and i f ). In this ROI we set less restrictive pairing constraints to increase the likelihood that the actual marker pair is selected. The main hypothesis in the definition of the ROI, is that the motion between frames i p and i f is close to a monotonous motion in both

x and y coordinates. It is a good approximation given the trajectory of the imaging system. The main sources of deviation with respect to this assumption are the cardiac and respiratory motions. Therefore the ROI for frame i is defined by:

ROI(i)={(x, y) | x min ≤ x ≤ x max and y min ≤ y ≤ y max } (4.6)
where

x min =m i n ( x(M 1,ip ),x(M 2,ip ),x(M 1,i f ),x(M 2,i f )) -B(i, i p ,i f ), y min =m i n ( y(M 1,ip ),y(M 2,ip ),y(M 1,i f ),y(M 2,i f )) -B(i, i p ,i f ), (4.7)
x max = max(x(M 1,ip ),x(M 2,ip ),x(M 1,i f ),x(M 2,i f )) + B(i, i g ,i d ), y max = max(y(M 1,ip ),y(M 2,ip ),y(M 1,i f ),y(M 2,i f )) + B(i, i g ,i d ),
and B(.) is an additional margin that enables handling motion further than the bounds dictated by a strictly monotonous model. It is defined by:

B(i, i g ,i d )=b + c • min(i -i g -1,i d -i -1), (4.8)
where b and c are constants that have been set based on our database. Fig. 4.9 illustrates this process. We can observe the ROI and the list of pairs. Since the region where the processing occurs is reduced owing to the knowledge of the position of the markers in previous and next frames, and the parameters of the pairing relaxed, it is highly likely that actual markers are among the pairs. In this example, that actual marker pair was not present in the original pair list. We can observe that it is present in the new one (Fig. 4.9(e)).

The best pair is chosen according to a continuity score is similar to the one defined in Section 4.3.2.5. As in the tracking process the best pair is added to the track only if its score is greater than a minimal threshold.

Track refinement

The process of reducing false positives followed by false negatives is beneficial to the quality of the track. Therefore iterating it generally further improves the track. In practice we iterate this process until the track stays unchanged or a maximal number of iterations is reached.

Labeling of the markers

The last challenge of the marker tracking is the labeling of the markers i.e. identifying all along the sequence the proximal and the distal markers. This step is essential to avoid performing an inverted registration during the motion compensated tomographic reconstruction. Approaches based on the analysis of their relative position along the sequences fail because the two markers may superimpose and invert their relative positions (see Fig. 4.10). As a consequence, we have adopted a 3D geometrically oriented approach. First of all, the center and the direction of the segment forming the markers in 3D are roughly estimated in a mean least square fashion. This rough estimate corresponds to an average position in the sequence. It is then projected on each frame and the position of the markers versus the segment and the center allows their labeling. We define these operations specifically hereafter.

3D reconstruction of the marker line segment

We first reconstruct the average 3D position of the center point of the markers. The 2D position of the center point is computed thanks the position of the markers in the track.

We consider the set E d of the back-projection lines of this point over all the frames. We Once the center point has been reconstructed, we determine the direction of the line segment joining the markers. To this end, we consider the set of planes formed by the triplet of points: (F i ,M 1,i ,M 2,i )i ne a c hf r a m ei,w h e r eF i is the focal point, and the other two the markers in the image plane. The normal vectors {n i } i<n of these n planes, illustrated in Fig. 4.12, are computed according to:

n i = ----→ F i M 1,i ∧ ----→ F i M 2,i ----→ F i M 1,i ∧ ----→ F i M 2,i , (4.10)
Figure 4.12: Plane associated with a marker couple i.

We express the computation of the direction as a mean square minimization problem, searching for a unitary vector d such that:

d =a r g m i n v∈R 3 and v =1 N i=1 (v • n i ) 2 (4.11)
Let us consider the following matrix A:

A = ⎛ ⎜ ⎜ ⎝ n x 1 n y 1 n z 1 . . . n x N n y N n z N ⎞ ⎟ ⎟ ⎠
It is well known that the eigenvector d of A ⊤ A associated with its minimal eigenvalue is a solution to Eq 4.11. A rough 3D reconstruction ( M1,3D , M2,3D )of the marker segment is then computed by positioning the two markers at an arbitrary distance from the center point along the 3D segment direction:

M1,3D =p + k d (4.12) M2,3D =p -k d (4.13) 4.3.2

.10 Application to labeling and track refinement

The labeling of the markers in the projections is performed thanks to the rough 3D model ( M1,3D , M1,3D ). Both markers are projected on every frame and their center is aligned with the center of the detected marker pair. Then, label i is associated with the closest marker to Mi,3D , as illustrated on Fig. 4.13.

We further refine the track to minimize FN and FP iteratively. At this stage the FN reduction can benefit from the 3D information. Given the labeling of the markers, we reconstruct them in 3D using the same technique as for the center point. It yields a 3D estimate of the average position of the markers ( M1,3D , M1,3D ). Then, during FN reduction, each pair is evaluated versus the projected 3D model in terms of angle and length to decide u pon the one to select. This ends the marker tracking.

Guide-wire subtraction

Similarly to the 2D DSE case (see Chapter 3), the guide-wire that is reconstructed has no clinical added value and induces visualization difficulties. In the context of volume rendering the guide-wire occludes the stent struts that are behind it in the scene. Moreover, when it gets close to the stent border it prevents the user from properly visualizing the general shape of the stent. Therefore, we propose to remove it. There are basically two ways to deal with this task: processing the 3D volume or pre-processing the projections before reconstruction. According the work exposed in Chapter 3,w e favor the second approach. We detect the guide-wire between the markers in each frame This algorithm demonstrated its robustness in this situation, achieving a successful segmentation in more than 95% of the images. Then guide-wire subtraction is performed according to the parametric model developped in Chapter 3. Given the properties of the algorithm that is based on the transparent nature of Xray images, the fundamental hypotheses of tomography are not violated by the processing. After subtraction, the observed absorbance at the location where the guide-wire was is theoretically exactly the one that would be observed if it where not present. Fig. 4.14 illustrates guide-wire segmentation and subtraction in rotational acquisitions.

On the choice of the registration for 3D stent reconstruction

The method proposed by Perrenot [START_REF] Perrenot | Reconstruction tomographique 3D de stent coronaire avec prise en compte du mouvement en angiographie rotationnelle cardiaque par rayons X[END_REF] for 3D stent reconstruction is based on the motion of the markers. Once the markers have been detected in every image of the input sequence an average 3D marker pair model is reconstructed. This model is forward projected on the images of the spin and the difference between the detected and projected positions of the markers is compensated by modifying the projection matrices. Then standard cone beam 3D reconstruction is performed. Similarly Schoonenberg et. al.

[SF09] detects the position of the markers in every image of the spin acquisition and reconstructs a 3D marker pair model that is projected on each frame of the spin. However instead of encoding the position differences in the projection matrices, the authors warp the projection images so that the detected markers match the projected model before performing a 3D reconstruction. In both cases the motion compensation is performed with a similarity transform. The second approach can be easily extended to different registration techniques. It can be formalized through the following scheme:

1. Detect landmarks in the 2D projections.

2. Compute 3D landmark model.

3. Project the 3D landmark onto the 2D projections.

4. Register the 2D projections so that the detected landmarks match their projected 3D model.

Perform cone beam 3D reconstruction.

We note that the approach of Perrenot [START_REF] Perrenot | Reconstruction tomographique 3D de stent coronaire avec prise en compte du mouvement en angiographie rotationnelle cardiaque par rayons X[END_REF] does not necessitate to explicitly transform the images and thus avoids the interpolation associated with this kind of techniques. It is an advantage since it allows preserving the sharpness of the original images.

Linear constant radius registration

We propose here to modify the 4 th step of the Schoonenberg et. al. scheme. The classical marker based registration (a similarity transform) suffers drawbacks that we have discussed in Chapter 2. We proposed here an alternative one that combines the smoothness of the linear transformation with approximate stent radius preservation. The main idea behind its design, is to account for the change in distance between the markers by performing scaling only in the direction of the marker segment, thus not modifying the diameter of the stent (see Fig. 4.16).

The registration step aims at compensating the differences between the projected and detected markers. From a geometrical standpoint, the differences between the length of the detected and of the projected marker segments can be attributed to foreshortening or to global image scaling. Foreshortening is due to a change in orientation versus the Xray beam, whereas global scaling is due to a change in the source to object distance.

These changes are due to the respiratory and cardiac motions, since the system geometry is taken into account while projecting the 3D marker model. The change in source to object distance, however is supposed to have little impact on the marker segment length.

A typical displacement of 1cm results only in a 1% variation of the marker segment. For a typical stent length of 20mm that translates to 140 pixels the change is only of 1,4 pixel (below the radius of the markerball). Therefore we believe that when a significant change in marker segment is observed it is to be attributed to foreshortening rather than global scaling. Under this hypothesis, the correct way to account for a difference between the length of the projected and detected marker segment is to stretch the image only along the direction of this segment followed by a rigid transformation. We illustrate this in Fig. 4.15. In this example the stent has an out of plane rotational motion around (Ox) from the position of (a) to (b). If the change in distance between the markers is compensated by a global scaling, its factor λ = d 1 d 2 also affects the diameter of the stent, resulting in a false diameter change (Fig. 4.15 (c)). With the proposed technique the stent diameter is nearly unchanged. Its preservation is crucial to the quality of the reconstructed 3D stent.

The scaling in the direction of the markers is modifying the image I to produce an image Stretch(I) according to:

Stretch(I)= cos(θ)s i n ( θ) -sin(θ) cos(θ) λ 0 01 cos(θ) -sin(θ) sin(θ) cos(θ) I (4.14)
Where θ is the angle formed by the marker segment and the abscissa axis. The rigid transform T that maps the markers of Stretch(I) to the projected ones is:

T (X)= cos(α) -sin(α) sin(α) cos(α) X + X 0 Y 0 (4.15)
where α is the angle between the projected and the detected marker segments and (X 0 ,Y 0 ) the translation between their centers. The overall registration yields a registered image I r defined by:

I r = T (Stretch(I)) (4.16)
We note that T (.) is a rigid transform (preservation of distances) since the stretching has already been compensated by Stretch(.). Moreover, the overall transform coincides with the guide-wire based transform (Section 2.3.3.4) when the guide-wire is a straight line (this is not the case of the classical affine transform). Finally, we note that this linear registration can also be embedded in the framework of Perrenot [Per08] that directly modifies the projection matrices. We would thus avoid the sharpness loss resulting from the image resampling during registration. In the results section we present examples with this transformation and with the similarity transform to register the detected marker on the projected marker model.

Guide-wire based registration

We consider here a non-linear warping accounting for the guide-wire deformation simi-

larly to what we have exposed in the 2D case in Section 2.3.3.4. The 3D motion compensated scheme is thus modified by extending the concept of landmarks to the markers and the guide-wire and by modifying the registration process. It can be rewritten as follows:

• Detect the markers in the 2D projections.

• Detect the guide-wire in the 2D projections.

• Compute an average 3D landmark model (including the markers and the guidewire).

• Project the landmark model onto the 2D projections.

• Non-linearly register the detected landmark on the projected landmark model.

• Perform cone beam 3D reconstruction.

In order to compute a single point of the guide-wire model, one has to determine its position in every projection image. However, this is not completely straightforward, Stent visualization enhancement in Xray image sequences

s i n c ew ed on o tk n o wt h ec o r r e s p o n d e n c e sb e t w e e nt h ep o i n t so ft h eg u i d e -w i r ei nt h e

different images (at the exception of the markers that are clearly identified). A solution would be to use the epi-polar lines to match points and account for frame to frame motion (see [START_REF] Blondel | Reconstruction of coronary arteries from a single rotational xray projection sequence[END_REF] for instance). We propose an alternate simple yet efficient approximation using the arc-length along the guide-wire. In order to account for the arc-length variations due to the projection angle in the spin acquisition we normalize it by the arc-length between the two markers. We then assume that points of normalized arc-length correspond to the same physical guide-wire point along the sequence.

It is equivalent to making the hypothesis that the angle between the guide-wire and the Xray beam is constant between the markers. This approximation can be grounded by the small length of the guide-wire segment (making conic projection similar to parallel) and neglecting the guide-wire curvature. Therefore we sampled each segmented guide-wire with a constant step in normalized arc-length to generate a set of corresponding points. Each point is then reconstructed in a least square fashion similarly to Eq. 4.9.

Once the average guide-wire has been reconstructed in 3D, it is projected back onto the images. However, this guide-wire is typically a polygonal structure, since only a set of sampled points have been reconstructed. Since the registration technique exposed in Section 2.3.3.4 assumes that the curve is differentiable, a fit is performed on the projected guide-wire points to yield a smooth parametric structure. Finally this structure is used as input to the non-linear registration.

Results

Marker detection and tracking

The algorithm described above relies on several figures of merits in the different steps (selecting pairs, building tracks, merging tracks . . . ). To address the problems of selecting the numerical parameters involved in these different figures of merits, we did our best to identify linked parameters and limit at maximum the parameter sets. We then collected a database of sequences either static (i.e. DSE sequences without rotating the image chain around the patient) or dynamic (rotational acquisition). Manual identification of the markers has been performed in these sequences. The parameters mentioned above have been adjusted by optimizing the results on this database. In this framework, "results" means essentially percentage of correctly identified markers. At the end, the algorithm was applied on 22 clinical sequences of average length 145 frames (for a total of nearly 3200 frames). In the table below, we report the percentage of frames where the actual markers are detected and the percentage of frames where a false alarm is detected at different stages of the algorithm. We can observe how each brick improves the quality of the track. The results listed in table 4.2 demonstrate that the level of performance of our approach is satisfactory. In 90% of the sequences (20/22) more than 97% of the markers are detected. In the worst case 94% of the markers are detected. In average the TP rate is 98.5% ± 1.6, the FP 0.6% ± 1.1a n dt h eF N0 .9% ± 1.0. Finally there is absolutely no labeling error. These results are very promising. The detected markers were used to make a 3D motion compensated reconstruction of the stents. The output 3D volumes were qualitatively compared to the volumes obtained with a manual segmentation of the markers. No visual difference was noticed. From an applicative standpoint these results can be considered as excellent.

Detailed results of the different algorithms

The algorithm that best improves the TP rate is the track merging. It raises it on average from 82% to 95%. Moreover the improvement of the minimum performance is more striking that the average one: It improves it from 55% to 85% of TP, i.e. from results that could not yield a satisfactory 3D reconstuction to results enabling it. However, the FP is increased in 18% ( 98,7 0,0 98,7 0,0 98,7 0,0 98,7 0,0 1,3 3a 83,7 3,3 98,7 0,0 98,7 0,0 98,7 0,0 1,3 4a 100,0 0,0 100,0 0,0 100,0 0,0 100,0 0,0 0 5a 97,6 0,0 97,6 0,0 100,0 0,0 100,0 0,0 0 6a 94,9

99,3 0,0 99,3 0,0 99,3 0,0 99,3 0,0 0,7 11a 80,4 12,3 92,0 with an average number of merges of 1.3 among these cases.

The stage that best reduces the number of FP is the track refinement technique, decreasing it on average from 2, 9% to 1, 2% and for the worst case from 11, 3% to 5% while improving similarly the TP rate (94, 8% to 96, 7%).

The track refinement based on the 3D marker segment model has a positive impact on the quality of tracks (no decrease in TP, no increase in FP). Fig. 4.18 illustrates several frames of sequence 3 and the automatically detected and labeled markers.

3D stent Reconstructions

We have reconstructed the stents both based on the ground truth and on the automated marker detection. No visual differences could be observed between the two volumes.

Therefore the results produced by our automated marker detection are fully satisfying for our application. We illustrate some of the 3D stent reconstructions hereafter. Fig.

Guide-wire subtraction and registration

The guide-wire subtraction is visually satisfying on the projection images as illustrated previously in Fig. 4.14. In the 3D reconstruction however a mark persists, though much weaker than the original guide-wire signal. Note on Fig. 4.22 that the stent border that was hidden by the guide-wire is restored by the guide-wire subtraction technique. We did not perform a quantitative comparison of the different registration techniques.

However, we present here some preliminary qualitative results that demonstrate the interest of the tools we developed on clinical cases. We first note, that the impact of the registration technique on the reconstructed volumes is visible on the longer stents only.

For the small ones, all the registrations yield visually equivalent results. This behavior was expected, and is similar to the 2D case (see Section 2.4.3.1). We illustrate in Fig. 4.23 and 4.24 a long stent case (20mm) where the quality of the results can be ranked in the following order: similarity < radius preserving affine < non-linear (4.17)

In this case, the combination of guide-wire subtraction and the non-linear registration yields a significant improvement: the stent is sharper and its shape better defined, both in volume rendering and in the slices of the volume. '97 that demonstrated the feasibility of the approach. However they did not follow this research path any further.

The second one, from Philips Healthcare, started more recently to tackle this topic and produced numerous publications [MSG + 06, MB06, SMG07, SFL + 08, SF09, SFL + 09a] including human studies. This is the only other team who published on automatic marker detection and tracking in spin acquisitions. The general architecture of their tracking algorithm shares some similarities with ours. First they detect marker candidates, then form couples, and build tracks based on temporal constraints. The detected markers are reconstructed in 3D, and the 3D model is used to further enhance the 2D track. The results they report, in their latest publication [SFL + 09a] on automated marker tracking are: TP 84%, FN 18% and FP 2% with the necessity of user interaction in 1 case out of the 10 cases. These results are in the same order of magnitude as ours, but inferior. However, the databses are different and several external factors, like the acquisition protocol, the image quality, the devices (stents and balloons) that are used, can impact these success rates. Regarding motion compensation, they register the projected 3D marker model to the actual detected markers with a linear registration. We proposed two variations over this concept: a modification to the linear registration to better preserve the stent radius, and a non-linear registration that can account for more complex motions (like vessel bending).

The third team [START_REF] Rohkohl | Non-Periodic 3-D Motion Estimation and Reconstruction of Coronary Stents[END_REF] relies on manually detected markers and focuses on the 3D reconstruction technique. They first reconstruct the trajectory of the markers in 3D

(yielding a 3D+t marker model) that they use for the reconstruction of the stent volume. We have not investigated this research axis on our side.

Finally, we note that there is no previous work about guide-wire subtraction that we could compare our method with.

On the acquisition

Two points can be optimized to increase the success rate of the automated 3D stent reconstruction. On the first hand the position of the axis of the spin with respect to the axis of the balloon. On the second hand the low pressure inflation of the balloon to minimize the relative motion between the balloon and the stent.

If the axis of the spin is chosen to be parallel to the one of the stent, the stent will appear with a rather constant length. Conversely, if the axes are orthogonal, the length of the stent will vary along the spin acquisition passing by a singular case where it is null. In the frames close to this singular point the markers appear as one single point.

This situation is clearly less favorable for a tracking algorithm since is makes the balloon appearance less invariant and the labeling less straightforward. Moreover the estimation of the registration parameters becomes singular. Only the translation parameter can be estimated, while the rotation and scaling are degenerated. Error propagation shows that an uncertainty ǫ in the position of the exact marker center generates an uncertainty in the scaling factor and on the cosinus of the rotation angle proportional to ǫ/l,w h e r e l is the length of the marker segment. As a result there is a higher uncertainty on the transform in the angles where the stent projection is shorter. Fig. 4.25 illustrates the inverse of the length of the marker segment and the estimated rotation angle as a function of the frame index. We observe that the rotation angle becomes unstable when the length of the marker segment decreases. We finally want to recall that when the stent length decreases as a result of foreshortening, the stent diameter stays constant.

Therefore the uncertainty on the transformation parameters impacts the diameter of the stent.

It has been observed on the reconstructed stents in the Results section 4.4 that balloon inflation presents two advantages: it enhances the quality of the reconstructed stent, and positions the guide-wire further from the stent border (see Fig 4.26). We also observed less difference between the non-linear and linear registrations on the balloon inflated cases. This is probably due to the fact that the inflated balloon prevents the artery from bending. Therefore balloon inflation reduces the need for sophisticated transforms and for guide-wire subtraction. However it is an additional constraint on the work-flow that may severely reduce its acceptability in daily practice. Observe that the inflation of the balloon is (i) beneficial to the quality of the enhanced stent and that (ii) prevents the guide-wire from overlapping with the stent border. This illustration case is the one where the impact of balloon inflation is the most striking in our database.

Future work

The overall results of the automated marker detection and labeling algorithm (TP 98%) are very close to the maximal achievable result. Since we noticed no difference between the reconstruction based on automatically detected and manually segmented markers, enhancing TP can only have marginal impact on the the 3D stent. However it can be useful for other applications, like enhanced stabilized display [SF09].

Developments that are relevant for our application are the one that can further enhance the quality of the reconstructed stents. Taking into account a 3D+t guide-wire models can be a future research axis.

Ultimately, compensating the motion of the stent versus the landmarks may enable to yield similar results with and without balloon inflation and would simplify the workflow. Finally, a clinical validation with IVUS on a large database of cases would enable to quantify the reliability of the reconstructed stents.

Conclusion

We have proposed an algorithm for the fully automated detection and labeling of the balloon marker-balls in rotational acquisition image sequences. Our bottom-up approach is building primitives of increasing level of abstraction and confidence. It exploits the 2D and 3D properties of the object to detect. It has been applied on 22 clinical sequences with a very satisfying success rate (on average 98%), the best reported so far in this context. The results of the automated detection have been used for motion compensated 3D stent reconstruction. The comparison of the reconstructed volumes with the ones reconstructed using a full manual segmentation exhibit no noticeable difference. The quality of the automated detection enables the daily use of the 3D stent reconstruction from rotational acquisitions from a workflow point of view. Moreover we showed the feasibility of guide-wire subtraction in the 3D volume by processing of the 2D projection images. We investigated the impact of several 2D registrations for motion compensation.

It resulted on our dataset that there is no noticeable difference in the reconstructed between the different reconstruction. We thus recommend the similarity transform that is the simplest one from a computational standpoint. etc. We therefore start this section with a description of the state of the art in curvilinear structure segmentation. Then, we present a challenging application in the context of interventional radiology: the segmentation of guide-wires in X-ray images. Contrarily to the approach presented in Chapter 2, where we relied on the presence of contrasted markerballs to constrain guide-wire detection, we aim here at segmenting it without any external information. Finally we explain the methodology we used to compare curvilinear structure detectors. Step 1 very often relies on the computation of the Second Order Derivatives of the image (SOD), known to characterize locally elongated structures [FNVV98, Lin98]a s valleys or ridges. In the simplest cases, the feature map is obtained with a Laplacian [START_REF] Palti-Wasserman | Identifying and tracking a guide wire in the coronary arteries during angioplasty from xray images. BiomeA comparison of line enhancementdical Engineering[END_REF]. However, most of the time, the feature map is derived from the eigenvalues/vector of the Hessian [LBL + 09, OG10, HTD05, MJS + 04, WZL + 07, BLHS09, MvdEV96], that characterize the presence/absence of an elongated structure, its contrast and orientation [FNVV98, SNA + 97, Lin98]. Some authors convolve the image with a bank of filters (each filter being dedicated to a specific orientation in the image) [KS05, BVG09] and extract from the bank of responses the local direction and intensity of the potential elongated structure. This approach can be elegantly embedded in the steerable filter formalism that reduces the amount of required computation [START_REF] Freeman | Massachusetts Institute of Technology. Media Laboratory. Vision, and Modeling Group. The design and use of steerable filters[END_REF][START_REF] Jacob | Design of steerable filters for feature detection using canny-like criteria[END_REF] in some particular cases. It can be considered as a generalization of the Hessian since the Hessian is one of them. Finally, the learning formalism has been used to build the feature map [BAG + 07, WCZ + 09, HVP10a, HVP10b]. The resulting feature map can combine a large number of curvilinear structure detectors (for instance more than a dozen in [START_REF] Honnorat | Robust guidewire segmentation through boosting, clustering and linear programming[END_REF]). An exception to these approaches is the case of local path processing [Vin98, TA07] that characterizes the local structure as following a path in the image. This notion is more general and flexible than the ones expressed by the Hessian and filter bank formalisms.

State of the art

Step 2 consists in enhancing the feature map responses that are close and aligned.

This enhancement of the feature map can be a filtering of the feature map, for instance when it is performed by tensor voting [START_REF] Franken | Detection of electrophysiology catheters in noisy fluoroscopy images[END_REF]. In some other cases it involves an explicit parametric representation of the contour [START_REF] Palti-Wasserman | Identifying and tracking a guide wire in the coronary arteries during angioplasty from xray images. BiomeA comparison of line enhancementdical Engineering[END_REF][START_REF] Gigus | Detecting curvilinear structure in images[END_REF]. Generally speaking, features derived from the Hessian, are considered as first order models of the curvilinear structures (they provide its contrast and orientation or tangent line). The parametric local fits extend this local knowledge beyond the first order with parabolic [START_REF] Palti-Wasserman | Identifying and tracking a guide wire in the coronary arteries during angioplasty from xray images. BiomeA comparison of line enhancementdical Engineering[END_REF] or circular models [START_REF] Gigus | Detecting curvilinear structure in images[END_REF] that are usually valid on a larger scale.

The third and last step involves grouping the significant responses in the feature map together into full curvilinear structures. It is the conversion from a pixel-wise, or short range information to a higher level primitive. The formalism of grouping [START_REF] Sarkar | Perceptual organization in computer vision: A review and a proposal for a classificatory structure[END_REF]h a s been successfully applied to this problem in its different variations, from the simplest to the most sophisticated:

• greedy, grouping first the responses that match best.

• hierarchical [BAG + 07], building primitives of increasing length.

• yielding the solution of a minimization problem [START_REF] Honnorat | Guide-wire extraction through perceptual organization of local segments in fluoroscopic images[END_REF].

The most common alternate approach to grouping is tracking: starting from a point on the structure (potentially given by the user in a semi-automatic framework), the extrac-

Guide-wire detection in X-ray fluoroscopy

We are interested here in one particular application of curvilinear structure segmentation: the segmentation of guide-wires in X-ray fluoroscopy during PCI. We recall the clinical challenges that motivate this application and the technical specificities encountered in this context.

Motivations

Interventional radiology/cardiology therapies imply inserting guide-wires in the vascular system of the patients under the monitoring of low dose X-ray images, called fluoroscopic images. The field of application of such procedures is constantly growing, far beyond the scope of angioplasty dealt in the previous chapters of this thesis, extending from aneurysm treatment to tumor embolization. Over the past years, guide-wire detection in fluoroscopic images has gained interest and maturity among the image processing researcher community, addressing a trade off between fast execution and high detection performance. Guide-wire detection enables a wide range of applications such as visualization enhancement, 3D guide-wire reconstruction and respiratory motion tracking.

The automatic segmentation of the guide-wires in a wide variety of clinical conditions differs from the problem that we treated in Chapter 2. In this chapter, guide-wire detection was considered in the context of DSE where we supposed that the two radio-opaque balloon markerballs were present. The detection of these markerballs considerably simplified the task of segmenting the guide-wire. Here, we do not assume that markerballs are present. In this context, guide-wire segmentation is a particularly difficult task. We detail hereafter the related technical challenges.

The technical challenge

In X-ray images, guide-wires appear as thin, dark curves. Therefore, their detection can be achieved with methods commonly used for thin objects detection. More specifically, they are hundred of pixels long structures of typical radius 0.036mm, which translates into 1 to 5 pixels on Xray images in the cathlab. They are thus extremely anisotropic structures. A small number of guide-wires simultaneously appear in images: in most of cases a single one, rarely two to three. Their appearance obeys to the physics of the formation of X-ray images: their Contrast to Noise Ratio (CNR) is decreasing with decreasing background intensity. They are generally formed of two distinct parts: a long guide-wire body of low CNR (between 0 and 3) and a short guide-wire tip, or extremity, of higher CNR. The challenges in guide-wire segmentation arise from the low CNR of their body part and of the disturbing clutter and anatomical structures that superimpose to them. It is thus a relevant technical challenge to benchmark line enhancement techniques according to their ability to handle high noise and clutter.

Evaluating and comparing line enhancement methods

For evaluation purposes, we consider line enhancement as a two class detection problem where the line enhancement algorithm is the classifier: it assigns a value to each pixel that increases as the pixel is likely to belong to a curvilinear structure. We want to characterize the ability of this processing to assign larger values to the pixels of the structure to detect than to the other ones. This is classically captured by a ROC analysis that we briefly recall hereafter. Then we explain precisely how this formalism can be adapted to our guide-wire detection application.

About ROC curves

ROC stands for Receiver Operating Characteristic. It is a common tool to study the performance of a classifier and to compare several of them. It was first introduced in signal detection theory [START_REF] Swets | Signal detection theory and ROC analysis in psychology and diagnostics[END_REF] and later conquered a wide range of fields including medicine [START_REF] Swets | Measuring the accuracy of diagnostic systems[END_REF] and machine learning [START_REF] Bradley | The use of the area under the roc curve in the evaluation of machine learning algorithms[END_REF] where it is extremely popular nowadays.

We recall here briefly the necessary background knowledge to support our use of this tool in this chapter 2 . We explain in this section, what is the ROC curve, what are its principal properties, and how to use it to compare classifiers. These quantities form the basis of the most common metrics. Those necessary to define t h eR O Cs p a c ea r et h eT r u eP o s i t i v eR a t e( T P R )a n dt h eF a l s eP o s i t i v eR a t e( F P R ) defined in the following equations:

2 A very comprehensive introduction to ROC curves can be found in [START_REF] Fawcett | An introduction to roc analysis[END_REF]. We have seen that a binary classifier generates a single ROC point. However, the line enhancement techniques we deal with are not binary classifiers: they output a continuous quantity f (i), that has the only property, that a higher score indicates a higher probability of belonging to the linear structure class. A set of thresholds can be applied to this output to derive a family of binary classifiers {f t } according to Eq. 5.5.

Each of these binary classifiers generates a point in the ROC space, so that f generates a whole set of points that are aligned on a curve called the ROC curve. An illustration of a ROC curve is shown on Fig. 5.3. Conceptually the thresholds range from -∞ to +∞.

For the thresholds higher than max i∈D f (i) the ROC point is (0,0) and for those lower than min i∈D f (i) the point is (1,1). The curve is monotonous since a lower threshold produces necessarily higher FPR and TPR. From a practical standpoint, the ROC curve can be efficiently computed in one pass over the sorted values of f over D. Similarly to ROC point comparison, the classifier with the highest ROC curve is the best. The optimal classifier is represented by a step function that is 0 for x = 0 and 1 otherwise.

f t (i)= ⎧ ⎨ ⎩ N if i<t P if i ≥ t
(5.5) In the general case, when a set of classifiers are compared, none of them presents a ROC curve higher than all the other ones. The curves intercept, and the highest one depends on the considered interval. However, the ROC curve can be used to derive a statistically meaningful metric to evaluate classifiers: the Area Under the Curve (AUC).

It has be shown that it is an estimate of the probability that the classifier will rank a randomly chosen positive instance higher than a randomly chosen negative instance [START_REF] Fawcett | An introduction to roc analysis[END_REF] . T h em i n i m a lv a l u eo ft h i sm e t r i ci s0 .5, for a random choice classifier, and the maximal value is 1 for a perfect classifier. The relevance of the AUC to compare classifiers versus other metrics like the accuracy has been demonstrated in the context of machine learning in [START_REF] Bradley | The use of the area under the roc curve in the evaluation of machine learning algorithms[END_REF]. Efficient algorithms exist to compute the AUC from the sorted f (i) data in one single pass [START_REF] Fawcett | An introduction to roc analysis[END_REF]. When the number of negatives is far larger than the number of positives, the left side of the ROC is the most relevant part [START_REF] Fawcett | An introduction to roc analysis[END_REF]. A common way to focus the ROC comparison on an interval of interest is to restrict the AUC computation to this interval. This metric is denoted the partial AUC.

Finally when two classifiers are compared based on their AUC, the uncertainty on the AUC shall be taken into account.

Application to guide-wire detection

We have previously compared guide-wire segmentations in Chapter 5.W e w e r e i n a context where the method to evaluate was actually producing a segmentation of the guide-wire as a smooth curve. In this case, the Hausdorff distance between the segmented guide-wire and the ground truth was a relevant tool to estimate the accuracy of the segmentation. We are more interested here in comparing classifiers that return a real value for each pixel. This value is all the greater as the probability of the pixel belonging to the guide-wire is high. In this context, ROC curves are a naturally suited tool.

Two recent papers presented comparisons of line enhancement techniques based on ROC analysis [START_REF] Zwiggelaar | Linear structures in mammographic images: detection and classification[END_REF]AR07]. We have also used this methodology in two of our previous works [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF][START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF] and to local curvature [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF]. Each of these aspects is associated with a dedicated methodology. This is beyond the scope of the present study that focuses on the common aspect of all these papers, the detection capability of the techniques, that is also to our eyes the most important one. A review of published comparisons of line detection techniques is summarized in Table 5.1 where we indicate the methodology, the compared techniques and the outcome. The AUC is used to compare line detection techniques in [START_REF] Zwiggelaar | Linear structures in mammographic images: detection and classification[END_REF]AR07]. In [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF][START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF] the ROC curves are computed and compared qualitatively, but the quantitative comparison is performed on the TPR for a fix FPR of 1% in [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF] and on accuracy in [START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF]. In [BAG + 07, HVP10a, HVP10b]t h e performance evaluation is based on metrics derived from precision and TPR. Finally, in [START_REF] Honnorat | Robust guidewire segmentation through boosting, clustering and linear programming[END_REF] • it is based on TPR and FPR,

• measures the ability of the line enhancement technique to set larger values to the pixels belonging to the linear structures

• it is focused on an interval of FPR rate.

The choice of the interval of interest is guided by the strong class skew of our problem:

negatives are typically some hundred times more numerous than positives in our image.

Therefore we focus on low FPR rate in the range [0, 5%]. We will also compute additional metrics derived from TPR, precision and accuracy in order to derive results similar to previous publications (see Table 5.1).

The computation of all these quantities is straightforwardly derived from TP, FP, TN and FN as explained previously. The definition of these elementary quantities is however According to these metrics, a classifier is all the better as both MDR and FDR are low. In order to illustrate the classifiers performance, we show the segmentation results for the threshold yielding the minimum of MDR+FDR. In order not to corrupt our assessment of line enhancement techniques with the presence of other interventional tools or similar curvilinear structures we also compute the metrics associated to false positives in an ROI around the marked truth (see Fig. 5.4).

We want to end this section by raising a methodological point. As pointed out in [START_REF] Jiang | Supervised evaluation methodology for curvilinear structure detection algorithms[END_REF], the output of most line enhancement techniques depends on a scale parameter.

When this parameter is larger, a given linear structure produces a response that has larger spatial extent. Therefore the definition of FP that we presented has a size bias.

In order to avoid this undesirable behavior we skeletonize the detected pixels at each threshold used for the computation of the ROC curve. Conceptually, it is equivalent to considering that we dispose of a set a classifiers that are the combination of thresholding and skeletonization for every threshold. In this case, the computation cannot be achieved with the efficient algorithms presented in [START_REF] Fawcett | An introduction to roc analysis[END_REF]. We have to actually define a family of thresholds and to apply them to the output of the line enhancement techniques.

Output of previous line enhancement technique comparisons

An interesting pattern emerges from the data presented in Table 5. We believe that this success can be explained by the strong anisotropy that can be modeled with such templates. Second order derivative kernels have the drawback of linking the extent of the analysis in the direction of the curvilinear structure and perpendicularly to it with a single scale parameter. On the contrary line template can be tuned in length and width independently to match the image content. This property is key and shall be embedded in a successful line enhancement technique. We note, in accordance with this observation, that in one of the case where RLT are bested by other filters

[AR07], the length of the RLT is very small (5 pixels) in regard to the lines to segment (115 pixels). Since the authors do not take advantage of the tuning capability of the RLT in their study it is expected that they do not obtain relevant results.

Gabor filters [START_REF] Chui | An introduction to wavelets[END_REF] Gabor [START_REF] Chui | An introduction to wavelets[END_REF] The

Selected line enhancement methods for comparison

We will compare our line enhancement method presented hereafter to state of the art line enhancement techniques. We chose one representant of each main family of technique:

• Rotated Line Template [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF] (linear filter)

• Second order Gaussian derivative [FNVV98] (Frangi's vesselness)

5. [START_REF]Result of the detection and tracking algorithm designed for DSE[END_REF] The polygonal path image

Motivations

We have seen in the previous section, that according to the experiments we have performed on line enhancement methods for the detection of the guide-wire [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF][START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF],

and to published studies [START_REF] Zwiggelaar | Linear structures in mammographic images: detection and classification[END_REF], the best local detectors are simply segment matching (RLT). We have previously explained why we believe they achieve good performance.

We want here to put this in regard with the properties of the guide-wires. We believe that RLT is well suited to the two main properties of the guide-wires (see Fig. 5.5).

• Guide-wires follow smooth curves in the images. They are not tortuous and can be efficiently approximated by simple shapes over large distances.

• Guide-wires have low contrast to noise ratio. In order to have a filter that produces significantly different responses on the guide-wire and on the background, it needs to integrate information over a large number of pixels to reduce the noise. As a rule of the thumb, the CNR of the response of a filter of length l is proportional to √ l.

As previously mentioned, sophisticated methods, like steerable filters cannot be used with extremely elongated kernels. Therefore they fail to handle the low CNRs of the guide-wires properly. Local path techniques do not generally constrain the paths to be smooth curves as one would expect for the guide-wires. RLT, on the contrary, can be used to integrate pixel values over long distances (some tens of pixels) along straight lines. Now that we have understood the basic mechanics behind the success of segment matching techniques, we want to investigate how to improve on them. The developments we propose are applicable to guide-wire segmentation and to the more general task of segmenting smooth curves of potentially low CNR in images. The main limitation to the CNR improvement that segment matching can bring on a curve is imposed by the curvature radius of the structure. Beyond a given length, the segments do not accurately match the curve anymore. An ideal filter would compute the response on the whole curve describing the structure to segment (some hundreds of pixels in the case of guide-wires), thus yielding a significant improvement in CNR. This is not computationally achievable in the classical filter bank formalism that would imply to build a convolution kernel for each considered path in the image.

The general idea of our method can be summarized as follows. We observe that RLT selects at each pixel the line segment that best fits locally. Similarly, we propose to get rid of the line segment constraint and select at each pixel the smooth path of given length that best fits.

We hope that such a technique, that can integrate pixel information on a larger scale than segment matching, can detect curves even in the parts where they are locally less visible. It would also be potentially very robust to noise thanks to the integration of a large number of pixels along the paths. In order to constrain the smoothness of the paths we force them to be regular polygonal lines. Such an approach can be implemented efficiently by combining segment matching and local path algorithms. We call this technique "the polygonal path image" and associate it to the notation P. P,thatis described in the next section, is the image analysis tool from which we propose a series of curvilinear structure processing techniques. It is defined by two parameters: the total arclength of the path and the length of each line segment forming the polygonal line.

The first one controls the analysis scale and the second one the path smoothness. The first parameter allows to embed the concepts used in the three typical analysis scales (local, semi-local and global) into one single formalism. The smoothness parameter is to be set according to the a priori smoothness of the structures to segment.

We present P in Sections 5.4.

The polygonal path image: P

The image analysis tool that we propose to build is a very rich structure that contains for each pixel the locally optimal smooth path and its cost. It is a generalization around the concept of locally optimal paths [Vin98] that we first recall. Then we motivate the need for a new tool, and describe our solution.

Locally optimal paths

Interested in the segmentation of low contrast curvilinear structures, Vincent [Vin98]

proposed the concept of locally optimal paths and an algorithm to compute them. The optimality of the path is defined by the minimization of a cost function. Similarly to classical shortest path techniques [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF], it is based on a potential image I that encodes the local cost information I(p)a te a c hp i x e lp. The cost J(P)o fap a t hP is defined as the sum of the values of the pixels in I along the path:

J(P)= p∈I I(p).1 P (p) (5.12)
Classical shortest paths approaches require a start and an end point, between which a globally optimal path is computed. Vincent considers a path length, denoted L to define the notion of locality.L e tΦ L p be the set of the paths of length L starting at pixel p. The locally optimal path, denoted P p , is the one that yields the minimal cost in Φ L p :

P p =argmin φ∈Φ L p J(φ) (5.13)
In order to prevent pathological situations with self intersecting paths, and to put the smoothness of the paths under control, he refines the concept and considers to:

Compute for each pixel p of an image, the minimal cost J(p) for all the paths P of a given length L originating in p and whose possible orientation and straightness are within a given range.

In this approach a path is thus controlled by two additional terms: orientation and straightness. The orientation is a reference angle θ and the straightness is an angular range δθ. The three constraints, orientation, straightness and length define a search cone in which Vincent imposes that the path shall stay at every pixel. It is illustrated in Fig. 5.6. The straightness and orientation constraints are recursive: at every pixel of the path, the remaining path must fulfill them (see Fig. 5.7). Thanks to these constraints pathological situations are avoided: paths cannot self intersect or describe a circle around the center pixel. The cost of any path of length L that is inside the angular range [θ-δθ, θ+δθ] is computed and the path yielding the lowest cost is selected. In order to simplify the problem only a small number of orientations (θ i ) i , generally regularly sampled between 0 and 2π, are considered (see Fig. 5.8). The parameters (θ i ) i and δθ are chosen so that all the orientations are within at least one cone. In some applications [START_REF] Talbot | Efficient complete and incomplete path openings and closings[END_REF], the parametrization is such that the cones overlap.

With a brute force approach, the number of paths to evaluate at each pixel is extremely high. However Vincent [Vin98] proposed an efficient iterative algorithm for this task (discussed in Section 5.4.4). This approach has been successfully extended to define efficient algorithms that perform morphological operations on paths [START_REF] Talbot | Efficient complete and incomplete path openings and closings[END_REF]. One of the limitations of the straightforward implementation of the minimal local path [Vin98] or the path opening [START_REF] Talbot | Efficient complete and incomplete path openings and closings[END_REF] in our context is that, in spite of the cone constraint, the paths are still allowed to be tortuous. It results in paths that can wander in the image, attracted by local noise fluctuations to minimize their cost. Fig. 5.9 shows the example of such a minimal path.

The second limitation is that in his article Vincent considers to store the cost of each optimal path, and not the path itself. However, the cost of the path carries very little information compared to the path about the geometry of the curvilinear structures present in the image. In order to remove the first limitation we propose a simple way to control the smoothness of the paths: we force them to be polygonal. The tortuosity is controlled by the length of the edges forming the polygonal path 4 . If this length is one pixel we are back to the original formalism. With increasing edge length, the number of allowed directional changes along the path is decreased. Similarly to [Vin98]a n d [START_REF] Talbot | Efficient complete and incomplete path openings and closings[END_REF] we divide the neighborhood of each pixel into cones of orientation θ i , and we constrain each path to be inside the search cone at each of its vertices. The cone constraint allows to further control the smoothness of the paths, to avoid pathological situations and enables the use of efficient algorithms. Finally we additionally constrain the polygon to be formed of segments of equal length. Let l be the length of each segment of the polygon, n the number of segments and L = nl the total arclength of each path. We denote Φ L p,l,θ the set of regular polygonal paths of segment l, total length L, inside the cone of orientation θ and originating at pixel p. The locally optimal path selected by the polygonal path image is:

P p =argmin θ∈(θ i ) i argmin φ∈Φ L p,l,θ J(φ) (5.14)
We note that contrarily to most local path techniques that only compute the cost of the selected path, we compute and store the whole paths. We illustrate in the next section the local geometrical information that is encoded in the paths. We further derive a set of curvilinear structure processing techniques, that rely on the use of the whole paths on not on their cost.

Besides, the polygonal path image has the nice property of only depending on two parameters : the length of the base line segment and the number of line segments in the path. These two parameters can be easily set. The length of the base segment shall be the largest possible provided that it fits in the curve to detect and the number of line segments shall be longest possible so that the curve stays in the cone. They are directly related to the typical shapes of guide-wires on X-ray images and can be adapted to the application. For instance in cardiology where arteries are less tortuous than in neurology, they can be set to larger values. From a higher level perspective the product of these two parameters is the arclength of the paths to consider that is equivalent of the analysis scale presented in Section 5. The main differences are that one path is built originating from each pixel and that the paths are formed of segments of equal length.

Structure of the path image

In order to illustrate the content of the path image and to understand its structure we have represented some paths originating from random locations on clinical and synthetic images on Fig. 5.12, 5.13 and 5.14.

We observe that the paths tend to converge into bundles around the main linear structures. From a shortest path perspective, the linear structures are similar to highways where the speed is high. The paths originating outside of the linear structures are immediately directed on the linear structures, taking the shortest possible way to reach the highway. Those that start directly on linear structures stay on them until the end or until the linear structure cannot be followed anymore because it escapes the cone.

Therefore many paths have large parts in common. In the areas where there is no linear structure to attract the path, they wander randomly in noise. In the example we depict the path that we built are so long that starting from virtually anywhere in the image they finally end up stuck to a linear structure. We can also observe some discontinuities in the path image. Indeed at a pixel that is on the equivalent of the medial axis of the linear structures for our problem, there are several shortest path of equal length that lead to different parts of the linear structures. Therefore some paths originating from pixels in the close vicinity of the medial axis will be attracted by one linear structure and others by another one. We illustrated this situation in fig 5 .13.

Finally the set of paths that intersect at a pixel convey some information about the local geometry of the linear structures at the intersection point. Fig. 5.14 illustrates all the paths intersecting at a point of the guide-wire. We observe not only the high number of paths crossing at this point (nearly 2000 in this case) as previously explained but also that these paths are well aligned with the guide-wire in a short neighborhood around the considered pixel. They can thus be used to derive geometrical properties like local orientation or curvature for instance.

In order to write more specifically about the elements of the P, we recall the following notations: We call P q the path originating from the pixel q. The cost of the path P q is denoted J(q), or J(P q ).

Efficient algorithm for the computation of P

In this section we explain how to build a structure that contains the minimal path of given arclength originating from each image pixel. It can be computed efficiently thanks to an algorithm commonly used in mathematical morphology [Vin98, TA07] provided that we impose a few restrictions on the paths (the cone constraint presented in Section 5.4.2). We first recall these techniques, then explain how we adapted them to force polygonal paths.

Let us describe the algorithm of Vincent [Vin98] in the case of 4 cones where δθ i = π/4, of directions θ 1 =0,θ 2 = π/2,θ 3 = π, θ 4 =3π/2 (Fig. 5.8). His algorithm computes the minimal cost for paths of length l with only 12l image shift, 8l point-wise minima and 4l additions. It is remarkable that this computation can be performed in a linear time whereas the number of paths increases exponentially with l (as O(3 l )). The idea of the algorithm is that the computations performed for one pixel can be partially reused for the neighboring ones. The algorithm that processes an image of potential I and returns the cost of the minimal path originating from each pixel in an image J is presented in Alg. 1.

In the case of P, one can observe that the cost of a path is the sum of the costs of its segments. A given segment being used in many potential paths, we propose to precompute the cost of each segment5 and to iteratively build polygonal paths of increasing number of segments. In order to compute the cost of every possible segment we compute a set of cost images for each of them: (I θ i ) 1≤i≤N . I θ i is an image that contains the sum of the pixels along a discrete segment of length l and orientation θ i starting at each pixel. There are typically N =2πl such images. For each of the θ i we define t x i and t y i , the translation parameters from the center pixel to the extremity of the segment. We for α ∈{θπ/4,θ,θ+ π/4} do 5:

J α ← I θ shifted by 1 pixel in direction -α;

6: end for 7:

I θ ← I θ + min α J α ; 8:
end for 9:

J ← min θ I θ ; 10: end for 11: return J; illustrated these notations in Fig. 5.15. A given cone that is naturally defined by an interval of angles, can thus be defined by two integers, cone.start and cone.end between 1andN . We define a path by a set of vertices

V = {v k , 1 ≤ k ≤ n} where v k =(x v k ,y v k )
and a cost c. Let us call P iter cone the image that contains at each pixel the best polygonal path originating from this pixel of length iter.l inside a given cone. In order to compute P, i.e. the structure that contains at each pixel the minimal polygonal path originating from this pixel, we perform the procedure described in algorithm 2. We illustrated some steps in Fig. 5.15, 5.16, 5.17. For our implementation we considered 8 overlapping cones of angular aperture π 2 at orientations 0, π 4 , π 2 , 3π 4 ,π,-π 4 , -π 2 , -3 π 4 .

Algorithm 2 Computation of P Require:

(θ i ,tx i ,ty i )w i t h1≤ i ≤ N 1: for θ ∈ (θ i ) i do 2:
P 0 θ (x, y).V ←∅;1≤ x, y ≤ ImageSize 3:

P 0 θ (x, y).c ← 0; 1 ≤ x, y ≤ ImageSize 4:
for j =1to n do 5:

for x =1to ImageSize do 6:

for y =1to ImageSize do 7:

for k = cone.start to cone.end do 8:

J k ← P j-1 θ (x + tx k ,y+ ty k )+I θ k (x, y) 9:
end for 10:

k opt ← argmin k {J k } 11: P j θ (x, y).c ← J kopt 12: P j θ (x, y).V ← P j-1 θ (x, y).V ∪ (x + tx kopt ,y+ tx kopt ) 13:
end for end for 22: end for 23: return P At this stage we have built the polygonal path image. No detection has been explicitly made so far, we just built a rich structure that contains locally minimal paths and their costs for each pixel. Its construction can be efficiently implemented thanks to the presented algorithm. The only known alternatives for the efficient computation of polygonal paths in images, are approximate. The beamlets [DHJ + 01] build a multiresolution pyramid a line segment and Brandt [BD99] computes the minimal necessary set of orientations, spatial positions and segment lengths to approximate line segments within a given error bound. Let the center pixel be of coordinates (i, j). In the image I θ k we store the sum of the pixels along line segments of orientation θ k . Such a line segment is illustrated on the figure with plain lines. Translation parameters (t x k ,t y k ) are also stored. A search cone is defined by a start angle cone.start and an end angle cone.end. All the possible locations of the end of the segments in a given search cone are illustrated by the arc of circle in dashed line. These are the locations of the pixels that will be evaluated to extend the path in the successive iterations.

Figure 5.16: At the second iteration of the algorithm, each pixel p i contains the minimal path originating from it of length l. In order to compute the minimal path of 2 segments (length 2l) originating from pixel p we consider each pixel p i and note that the minimal path originating from p and passing trough p i is simply the already computed path originating from p i to the which we add the line segment p i p. An existing approach to building a linear feature detector out the path image consists in associating to each pixel the cost of the path originating from it (J with our notations)

[Vin98]. We have illustrated the results of this strategy on 5.19. We can observe on the perfect circle image that the cost image is quite complex. Segmenting the circle out of it is not straightforward. In the case of a clinical image 5.19 the task is even more complex. The reason for this is that the paths originating from any pixel close enough to the linear structure are attracted by it and thus are associated to a cost that is low, and rather close to the cost of a path starting right on the linear structure. As we build very long paths, even far away from linear structures this behavior is observed. A solution to this would be to narrow the angular aperture of the cones. Most of the path far from the linear structures could not converge following the shortest geometrical path since it would not be aligned with the linear structure inside the small aperture cones. This strategy is used in [Vin98]. However, we do not want to impose that the structure to segment stays in narrow cones on long distances6 . The solutions that we propose rely on the fact that the polygonal path image is much richer than the simple cost image. We expose hereafter two solutions that process the polygonal path image in two opposite directions: the first one takes advantage of the redundancy of the paths to re-enforce the linear structures and the second one eliminates all the redundant paths conserving a very small set of them, most representative of the actual linear structures.

Path voting

Instead of having each pixel basically contributing to all the paths passing through it, that we typically summarize in the cost image, we propose to have each minimal path vote for all the pixels it passes through. This way, all the paths that form a bundle around the linear structures will re-enforce this structure. In the traditional approach a very contrasty pixel will spread its contrast on all the paths going trough it creating a star effect. Conversely, in the proposed approach, all these paths vote for the pixels on which they intersect, making them more visible. This approach shares some similarities with the one of [START_REF] Mark | Enhancement of low-contrast curvilinear features in imagery[END_REF] who first had also observed how minimal paths are attracted by linear structures. This methodology has recently been adopted in geodesic voting We can observe that the image is complex and that linear structures tend to extend to neighbor pixels. We can observe that the image is complex and that linear structures tend to extend to neighbor pixels. [START_REF] Rouchdy | Image segmentation by geodesic voting. application to the extraction of tree structures from confocal microscope images[END_REF]. We have several options to aggregate the votes of the paths. Either each path can vote for one, which is equivalent to counting the number of paths intersecting at one pixel (we call the resulting image the "path voting image" and write it ϑ(P)), or each path can vote according to its cost (the resulting image is denoted ϑ J (P)).

ϑ(P)= p∈I 1 Pp (5.15) ϑ J (P)= p∈I f (J(p))1 Pp (5.16)
Where f is a decreasing function in order to assign larger weights to the low cost paths.

In practice, both technique gave quite similar results. From a qualitative standpoint ϑ(P) was slightly better.

In practice path voting is a powerful tool that yields very interesting results. We use it here to illustrate the relevance of the polygonal structure of the paths (see Fig.

Pruning

A completely opposite way to exploit the structure of the path image is to prune paths to get rid of the redundancy, retaining only a small set of relevant, non redundant minimal paths. In order to do so we define a relation that allows to determine the paths that are neighbor to a given path. We retain the path of minimal cost over the whole image and prune all the paths that are neighbors to it. They correspond to minor variations around the minimal one. The one with the best cost is likely to be the one most aligned with the actual linear structures of the image. We iterate this process in a greedy fashion selecting the path of minimal cost again and pruning its neighbors, until there is no more paths in the path image or until some stopping criterion is reached. The small set of paths finally retained (typically less than 100) describe the linear features in the image. We call them "non redundant paths". The relation defining neighbor paths can be defined in several ways. We propose to consider the following one : a path P i is neighbor to a path P min if their partial Hausdorff distance [START_REF] Huttenlocher | Comparing images using the hausdorff distance[END_REF] h K (P i , P min )i s below a given distance d (see Eq. 5.17).

h K (P i , P min )=K th p∈P i min q∈P min dist(p, q) <d (5.17)

In practice, for the sake of computational speed, we approximated this relation by counting the percentage of vertex of P i closer to P min than d. We used it to generate the results we present. We illustrate here the result of path pruning with x = 50%. We can observe that among the small number of paths selected, the ones illustrating the guide-wire are present. Further path selection, based on their cost for instance can be performed to better isolate the guide-wire.

Selecting path according to smoothness

It can be noted in the results produced with the proposed technique that the paths that are extracted in the parts of the image where there is no relevant linear structure are especially tortuous. Similarly some paths with very abrupt directional change occur close to high contrast objects since they are attracted by them. These paths do not meet the expected requirements of a smooth curvilinear structure like a guide-wire. Therefore we propose to remove them from the path image prior to building the detection image by pruning or voting. We define to this end a tortuosity metric τ to penalize the abrupt changes in direction. In the cones we defined the paths cannot undergo a directional change of more than 90 • . Therefore we design a metric that will be 0 for a path we change of 90 • and 1 for a perfectly straight path. In order to do so we simply compute the product of the normalized scalar product between each two consecutive segments of the path.

Let V(k) be the vector formed by two consecutive vertexes of the path P, τ (P)i sg i v e n by 7 :

7 Several other tortuosity metrics can be considered like min 1≤k≤n-2

V(k).V(k+1)

V(k) . V(k+1) , for instance that decreases less fast towards 0 when the length of the paths increases. pixel p. We build the set of the paths {P i } intersecting at p (i.e. p ∈P i ∀i). For each of these path we compute the tangent unit vector at point p: {t i }. Then we find the angle α ∈ [0,π[ such that the norm of the projection of the {t i } over the line of orientation α is maximal. Let α i be the angle between t i and the horizontal, α is solution of (see [START_REF] Rao | Computing oriented texture fields[END_REF] for details):

tan(2α)= i t i 2 sin(2α i ) i t i 2 cos(2α i ) (5.21)
Among the two possible solutions we keep the one that yields the highest sum of square projections. This α is the orientation at pixel p. The vector indicating the direction to follow to get to the closest linear structure has orientation α and two possible directions.

Since the paths are oriented (from the start point to the end point) so are the tangent vectors {t i }. We select between the two possible directions the one that yields the maximal sum of scalar products with the {t i }. On the curvilinear structure itself, this sums tends to 0 and the direction looses its meaning. The orientation, however, is still relevant.

We illustrate the result of this method in Fig. 5.29. We note that contrary to the orientation fields estimated with state of the art techniques that are non relevant outside of the curvilinear structures, ours has a precise, potentially useful, meaning. Finally, a similar methodology could be used to derive other local geometrical properties, such as curvature.

Figure 5.29: Extract of ϑ(P) obtained from the X-ray image of a guide-wire. The arrow resulting from direction estimation give the direction of the closest curvilinear structure. Note that on the structure itself the direction of the arrow is not relevant (the linear structure can be found in both opposite directions), but the orientation is accurate.

Links with other existing techniques

Geodesic shortest path

We have seen in our state of the art review, that the shortest path approach is among the most popular ones for the segmentation of curvilinear structures. Our approach belongs to this wide family, but differs from traditional techniques on several aspects.

The one we want to discuss here, is the link with the notion of geodesic distance. To the best of our knowledge, the link between the search of shortest paths inside cones and the minimization of a geodesic distance has not been previously investigated. We present here a first reflexion on this link, that we hope to pursue in our future work. The other differences with classical shortest path approaches will be discussed in the next section.

The classical approach of Cohen [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF], defines the shortest path between two points Let us examine how this translates to our local path approach.

Our technique also consists in computing a path that is minimal among a set of paths.

However, not every possible path between the two extremities is considered. The cone constraint rejects tortuous ones. It can be interpreted as a bound that is set on the curvature of the paths. This property is highly desirable in some applications. In medical imaging for instance, where the paths correspond to biological structure, we often expect them to be smooth. We first observe that bounding the curvature of paths invalidates the triangular inequality necessary to the concept of distance (see Fig. 5.30). We show in the following developments that the path that are minimal within the cone constraint are equivalent to minimizing a cost that is very similar to a distance: it verifies all the necessary mathematical properties except the triangular inequality that is only valid in a weakened, local version. The "distance" between two points is defined as the minimal cost of all the paths joining two points, under the constraint that the maximum curvature of the paths shall not exceed a given bound. We build a particular potential cost image for this counter example, where: all the image has cost +∞ except the three paths that are drawn. Let L AB be the length of the path from A to B. We assign to each pixel on this path the cost 3/L AB . Consequently the cost of the whole path is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB . The cost of each of these two paths is thus 1. Then, we note that the only finite cost path from A to B, is the one that is drawn (see Fig. We first expose the properties of paths within a single cone. In a second step, we consider the combination of several cones together. For the sake of the clarity of the explanations, we consider here the paths as defined by Vincent in [Vin98].

Let us consider the simple case of shortest paths restricted to two opposite cones, for a given orientation θ (see Fig. 5.31). For any point A in the plane, we denote these two cones C θ A and C -θ A . We call conic-path, a path that fulfills the cone constraint: the path shall never escape the cone starting at any of its pixels. We define the distance d θ (called cone-distance) between to points A and B in the image, by the cost of the minimal conic-path joining A to B. If no conic-path exists, we set d θ (A, B) to infinity. If λ were a distance, λ l would be a geodesic distance from A to the square surrounding it. This is not the case here. The triangular inequality has been weakened to a local version to restrict the set of paths in a way that enables to control their curvature. . We build a particular potential cost image (b) where: all the image has cost ∞ except the three paths that are drawn. Let L AB be the length of the p a t hf r o mAt oB ,w ea s s i g nt oe a c hp i x e lo nt h i sp a t ht h ec o s t3 /L AB . Consequently the whole path cost is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB . The cost of each of these two paths is thus 1. Then we note that the only finite cost path from A to B is the one that is drawn that is included in cone (a) (see Fig. point. In its original formulation a geodesic weighted distance U is computed as in the classical shortest path by fast marching from the starting point. Then a large set of "end points" is computed (all the points in the image, or random points etc...) from which shortest path are computed back to the starting point. Each path votes for all the pixels it passes through. The number of paths intersecting at a pixel is denoted by the authors the geodesic density and the process of computing it geodesic voting. This approach has been later extended to embed vessel radius information or to serve as shape prior to drive a snake levelset.

Remark: alternate approaches have been proposed in the past to get rid of the end point but rely on extra parameters and/or a priori knowledge on the structure to segment, and are thus less general.

This approach has obvious similitudes with ours but also striking differences. Geodesic voting do not constrain the paths to be included in cones (this is not necessary in this numerical scheme). Therefore the paths can follow a larger variety of curves to match the image content. However we note that the paths in geodesic voting are global while ours are local. It is acceptable from an intellectual standpoint to constrain paths locally whereas globally this constraints would seem artificial and limiting. To better understand the differences between the approaches it is key to note that geodesic voting relies on a start point from which the action map is computed. This point plays a critical role and the minimal paths that vote converge to it. On the contrary our approach does not require either a starting or an ending point. The path do not all converge to a unique pixel but start from each pixel of the image. With the regular fast marching formalism this would require to repeat all the computations for each pixel. In our approach thanks to the constraint that the paths are included in the cones the computation is performed for all the pixels of the image simultaneously. Moreover, it has been shown in the geodesic voting approach that if the set of end points is not properly scattered all over the image some structures have no paths passing through them (this is referred as the shadow problem). In our approach all the pixels of the images are taken into account avoiding this pitfall. Finally if the SNR of the structure to segment is low in the potential we suspect that the geodesic path go through shortcuts to reach the starting point in the geodesic voting approach when the end points are too far from it [START_REF] Benmansour | Fast object segmentation by growing minimal paths from a single point on 2d or 3d images[END_REF].

In classical minimal path approaches this problem is addressed by computing smaller paths between key points [START_REF] Benmansour | Fast object segmentation by growing minimal paths from a single point on 2d or 3d images[END_REF] (see Fig. 5.34). This is an artificial way of making the notion of shortest path local instead of global. This problem either does not appear with our approach that builds path of fix length in a local fashion (the length of the path is not dependent on the position of the point in the image).

Hough transform

The Hough transform [Pau59, DH72] is a widely used technique for pattern recognition in images. In its most famous form it relies on a parametric representation of the shape to recognize. After discretization (sampling) of the parameter space, two approaches can be used:

• for each possible value of the parameters all the pixels of the image intersected by the pattern participate in the vote.

• the image is spanned and each pixel votes for all the parameters sets describing a pattern intersecting this pixel.

The process we use to select local optimal paths is very similar to a hough transform.

F o rag i v e ns t a r t i n gpo i n t ,e a c hp i x e li nt h ec o n ev o t e sw i t hi t sv a l u ei nt h ef e a t u r em a p for all the curves passing through it. The curve yielding the extremal vote is selected as the local optimal path for this starting point. The main difference with Hough is that voting does not occur explicitly in the parameter space. Regarding our explicit voting scheme, it is somewhat the dual approach of the Hough transform: instead of pixels voting for curves, curves vote for pixels. In our case a set of curves (the optimal paths) are selected in the image and vote for all the pixels they pass through. Deeper links may exists between the techniques that shall be explored into future work.

Results

We present here the application of the polygonal path image to the detection of guidewires in interventional cardiology.

Database

Our clinical case database is constituted of 12 clinical sequences illustrating PCI angioplasty exams from which we isolated 9 successive frames. It represents a total of 108 frames where we manually annotated the position of the guide-wire. In these images one can observe the injection catheter, the guide-wire, the angioplasty and the anatomical background. Some of them additionally display stents and sternal wires.

Setting of the techniques

Each technique requires some specific parameters to be set. We chose for each one the setting that appeared the most optimal to us. Regarding vesselness, we set α and β to the values proposes in Frangi's article [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF]. The scale factor σ, was set to the approximate guide-wire radius: 2 pixels. For the RLT we relied on a previous study with a similar technique [START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF] that concluded that a length of 61 pixels and a width of 3 pixels was optimal for guide-wire detection. We note that these parameters generate very anisotropic filters compared to the Gaussian derivatives used in the vesselness. For the two new techniques that we presented in this chapter ϑ(P)a n dϑ τ min (P), we set : l = 11, niter = 10, tortuosity =0 .6 and applied them on half resolution images for sake of computational speed. In terms of scale, we note that with these settings, the vesselness integrates pixels along the curvilinear structure over a range of ≈ 8 pixels (= ±2σ), the RLT 61, and P 220 (in the original image resolution).

Potential cost image

In order to compute P we process the image so that minimal paths actually correspond to guide-wires. In this context the potential cost image is often derived from a Hessian based metric that already encodes information about curvilinear structures (see Section 5.3.1). In order to illustrate the power of the proposed technique we generate a very simple potential cost image based on scale selection. We remove background variations and select thin dark object with a dark top hat. The guide-wire radius being between 1 and 2 pixels, we use a square structuring element of 2 pixels in radius. In the resulting image the guide-wire is actually a path that is of low intensity. Summing the pixels along the path and retaining the minimal path, as proposed for the construction of the polygonal path image shall thus enable to select it. However, its tip is much more contrasted and tortuous than its body and tends to better attract path than the body does. In order to get rid of this unwanted behavior we simply threshold the image to isolate the tip, and set the corresponding pixels to a more moderate value.

Qualitative results

We illustrated the result of the voting technique (ϑ τ min (P)) on the last frame of each image sequence of our database in Fig. 5.35, 5.36, 5.37 and 5.38. We observe that the results are generally speaking very satisfactory: most of the guide-wire is enhanced, and few false alarm remain in the background. However three problems remain. The guide-wire tip attacks paths too much (creating false positives in its vicinity) and is too tortuous to be accurately fitted by our detector with the same setting as the guide-wire body. We shall detect it separately. Secondly, some linear structures are detected in the background that are not guide-wires. Since they satisfy all the properties that we selected for guide-wires, a higher level processing, based on other criteria shall handle them. For instance the presence of a tip is very characteristic of the guide-wire, as well a the motion that animate it. Finally, P is not able to handle some shapes properly, especially S shapes since they do not stay in the cones over long distances. In such cases the results are not as good as on simpler guide-wire shapes.

Quantitative results

We used the ROC curve formalism described in Section 5.3.3.2 to quantify the results obtained on the database of clinical cases with four different methods: ϑ(P), ϑ τ min (P), and two classical detectors, a Rotated Line Template (RLT) [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF] and Hessian based techniques (Frangi's vesselness [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF]). We have computed the partial AUC independently on each image of each sequence. We report in Fig. 5.39, for each sequence s the mean and standard deviation of the AUC denoted AUC µ (s)a n dA U C σ (s). The This is due to the fact that they detect a large proportion of anatomical structures in the background that yield larger responses that the guide-wire. These structures are not impacting P because they are attenuated by the top hat in the potential cost image and because they cannot be linked into long smooth curvilinear structures. In order not to We can sort the techniques in two groups based on their performance. The first one, constituted of the line enhancement techniques derived from P performs better than the second one formed of classical techniques (RLT and Hessian). The difference between the two groups is greater than the differences inside each group. Local descriptors like RLT and Hessian show variations of a few percent whereas P shows twice their performance.

Moreover we note than, in accordance with other publications [ZABT04, BVG09, Tan10],

the RLT performs better than Frangi's vesselness. We have previously discussed this fact and proposed an explanation in Section 5.3.3.3. Finally the results show that path selection based on smoothness has a positive impact in this application. We can propose the following ranking of the techniques:

ϑ τ min (P) >ϑ(P) >> RLT > Vesselness (5.37)

In order to illustrate the performance of the different techniques we selected an "optimal" threshold for which we display the result (see Section 5.3.3.2). We adopt the metrics of Missed Detection Rate (MDR) and False Detection Rate (FDR) presented in [START_REF] Honnorat | Guide-wire extraction through perceptual organization of local segments in fluoroscopic images[END_REF] to define this optimal threshold. When the threshold increases the MDR increases and the FDR decreases. Since we want both to be small we select the threshold minimizing MDR+FDR. For this experiment we restricted the computation of FDR to a band around the guide-wire.

Conclusion and further work

We have presented in this chapter a reflexion on curvilinear structure enhancement in image processing that led us to propose an efficient new approach, the polygonal path image (P) that has several interesting properties:

• an efficient computational scheme, • the ability to control the smoothness and length of the structures to be analyzed,

• a unification of local, semi local, and global curvilinear structure analysis in a single framework,

• intuitive and simple parametrization. We also believe that the reflexion we proposed on line enhancement comparison methodologies could be useful to other researchers.

Future work may include some natural extensions of the usage/construction of P that include:

• compute rank order costs instead of average along the paths. • extend the computation of P to vector potentials to better constrain local orientation,

• include a tortuosity cost in the cost of paths to build P,

• iterate P,

• extend the set of operators on the path structure, • select the optimal path length at each pixel.

Finally we believe that P is a generic tool for the analysis and processing of curvilinear structure that can find applications for the filtering and tracking of such structures for instance. In order to make the use of stent visualization enhancement techniques possible in daily clinical practice, our objective was twofold:

• yield significant improvements in image quality,

• reach a high level of automation and robustness.

In this conclusion, we first summarize the main achievements of our work that we regroup under the following topics: 2D and 3D stent visualization, image processing tools for interventional imaging, curvilinear structure processing and methodology. Some of these developments have been published and/or patented (refer to my publication list in App. A), some appear publicly for the first time here (mainly the content of Chapters 3, 4 and 5). We then recall the identified limitations of the proposed techniques and expose perspectives to overcome them.

Main results

2D and 3D stent visualization enhancement

In Chapter 1, we presented the interventional imaging system, the angioplasty procedures and the existing stent visualization techniques. Based on this context, we summarized the needs and requirements of the clinician regarding stent visualization. In Chapter 2, we pursued this analysis and translated the clinician needs into quantifiable evaluation metrics and algorithm design-guidelines. We proposed in Chapters 2, 3 and 4, a set of algorithms for 2D and 3D stent visualization. They involved the design of fully automated techniques, that include two original contribution in our field: non-linear registration and guide-wire subtraction. Regarding the 2D case, we presented a comprehensive study of the stent visualization problem covering thoroughly the technical and clinical aspects of this topic.We demonstrated the following results:

• Our method yields an improvement in image quality over the input images of more than 1 point on a 5 level scale (p value < 0.001), as assessed by two clinicians on nearly 200 clinical cases.

• Our non-linear registration is superior to the state of the art similarity transform (improvement is visible in 27% of the cases). It has been evaluated by the author of this thesis on 140+ cases.

• The overall approach that we proposed, has been compared blindly to another commercially available software by three clinicians. Our technique has been judged to yield superior results (p value < 0.001 -A noticeable improvement was observed in 74% of the cases).

• The guide-wire that impairs the visibility of stent details can be removed from the image with image processing techniques without degrading the stent information (illustrated on 10+ clinical cases).

Regarding 3D stent visualization, we demonstrated on a database of 22 clinical cases:

• A fully automated algorithm to perform 3D stent reconstruction that yields no visual difference with the reference, non-automated, reconstruction.

• The extension to the 3D case of the tools that we developed for 2D stent visualization (non-linear registration and guide-wire removal), yielding promising results.

Image processing tools for interventional imaging

The stent visualization techniques that we developed and exposed in this thesis involved the design and validation of the following set of algorithms:

• an algorithm to detect and track the angioplasty balloon markerballs in short (≈ 30 frames), static, image sequences. This fully algorithm has been validated on 7000+ images. Its success rate is superior to 90% and its accuracy on the position of the markerballs is sub-pixel.

• a similar algorithm for the case of long rotational image sequences (> 100 images).

Its evaluation on a database of ≈ 3000 images demonstrated a success rate of 98%.

These results are the best reported so far in this field.

• a technique to segment the guide-wire between two given endpoints. In typical clinical conditions, its precision is inferior to the radius of the guidewire in 97% of the cases.

• a non-linear registration technique, tailored for the registration of stents and vessels.

• a guide-wire removal technique that does not degrade the content of the image that is overlapping with the guide-wire.

Curvilinear structure processing

In Chapter 5 we were interested in the segmentation of guide-wires without any user interaction or a priori on the presence of markerballs (i.e. without given endpoints for instance). In this context we developed a tool to process curvilinear structures, denoted the polygonal path image P, that has several interesting properties :

• a unification of local, semi local, and global curvilinear structure analysis in a single framework,

• the ability to control the smoothness and length of the structures to analyze,

• an intuitive and simple parametrization,

• an efficient computational scheme.

We derived from P several curvilinear structure processing techniques. We demonstrated the superiority of this tool over state of the art line enhancement techniques on a database of 100+ clinical sequences: Its performance is twice better than the state of the art, as measured by the partial area under the ROC curve.

Methodology

Each of the quantitative validation that we summarized in the previous sections of this conclusion, required to design an appropriate measurement methodology. We proposed validation methodologies to quantify the performance of algorithms for the following tasks:

• automatic markerball segmentation,

• automatic guide-wire segmentation,

• relative and absolute visual quality assessment of stent images.

6.2 Limitations and technical perspectives 6.2.1 Limitations

Image quality of enhanced stent images

We noted that the stent visualization techniques presented in this thesis, despite their good performance versus state of the art ones, do not always enable the observation of all the desired stent details. We believe that one of the main contributors to this image quality limitation is the relative motions of the landmark versus the stent (that we just call "relative motion" in this paragraph). Rigidly linking the landmarks to the stent, in order to annihilate this motion, can be achieved by inflating the balloon. However, it is unlikely that clinicians would perform this action in daily practice, for the sake of visualizing the stent (it results in blocking the blood flow of the artery). Therefore, the developement of image processing techniques that would compensate the relative motion is a potential field of further research.

A second potential solution to improve image quality in stent visualization applications, is to select a subset of the input image to take into account. This strategy allows to reject the frames where the relative motion is the largest.

Applicability of stent visualization techniques

All the stent visualization techniques that we have presented (Chapters 2, 3,a n d4) rely on the presence of the guide-wire and of the markerballs of the angioplasty balloon.

Although the presence of the guide-wire is natural since it is the first device to enter the artery, and the last one to leave it, the presence of the markerballs can be regarded as a constraint for the clinician. In several cases, he faces the desire to visualize a stent while there is no markerball in its close vicinity. The techniques that we propose do not allow to answer this need. A stent visualization techniques that would not require the presence of the markerball would better integrate into the clinical workflow and potentially save dose (since all the stents present in the artery could be enhanced with a single Xray sequence).

Co-visualization of stents and vessels

When we listed the needs of the clinicians regarding stent visualization in Chapter 1, we expressed the interest of visualizing the stent with respect to its environment: the vessel lumen, the potential bifurcations and the calcifications. The techniques that we presented focus on the stent and did not bring any information regarding the vessel itself. Techniques that enable the joint visualization of stents and vessels have recently appeared on the market [SF09, Inc11] and will probably be the subject of further research.

Perspectives

Layer separation

We presented a three-layer-model (background, guide-wire and stent) for the stent images, and proposed a method to extract the stent layer. The key point of the method is that the guide-wire can be accurately modeled by a parametric model. We believe that this formulation can potentially be extended to separate other structures in the images, provided that one can come up with a relevant parametric model. It could be used, for instance, to remove the markerballs or some simple anatomical features.

Curvilinear structure processing

The tool that we have presented for the processing of curvilinear structures has been used to derive enhancement and direction estimation algorithms. Our future work will include full guide-wire segmentation and the application of P to other structures in biomedical imaging. Moreover the theoretical foundation in which it fits needs to be further developed.

Interventional tool detection and tracking

As previously mentioned, the developments of Chapters 2 and 3 are the basis of the StentViz feature commercially available on the Innova systems. Other similar products exist on the market, that we regrouped under the generic name Digital Stent Enhancement (DSE). To the best of our knowledge DSE is the first family of industrial products based on the automatic detection and tracking of interventional tools. As mentioned in Section 1.4.1, the research in this area has been intensifying over the past years. Automatic detection and tracking of interventional tool is being studied for a large number of specific interventional tools (lasso catheters, ablation catheters, guide-wire, IVUS probes etc). As a result, we expect new clinical applications and products to appear in a near future. Finally, the real-time extension of the concept of DSE seems to be a logical next step towards improved guidance during PCI.

-2000

UniversitéP i e r r ee tM a r i eC u r i e ,P a r i s B S ci na p p l i e dm a t h e m a t i c s-w i t hh i g hh o n o r s( m e n t i o nt r ès bien).

-1999 Lycée Charlemagnes, Paris

Post-secondary preparatory school / classes preparing for entrance examinations to the French Grandes Ecoles.

  laboratoire d'informatique Gaspard-Monge ESIEE Doctorat Algorithmes de traitement d'images pour la visualisation d'outils interventionnels dans des séquences de fluoroscopie par rayons X.

1. 1

 1 Simplified view of the cardiovascular system (Copyright c Addison Wesley Longman, Inc publishing as Benjamin Cummings). ........... 1.2 Overview of the coronary arteries [LtOH10]. ................. 1.3 Progression of the atheromatous stenosis over decades, potentially rupturing putting the patient at risk of major adverse events (image from [Chi06]). ..................................... 1.4 Visualization of a diseased artery under Xray fluoroscopy (angiography)

  . ... 1.15 Coronary stent image with conventional Xray (image zoomed on the stent). Note that the stent is almost invisible, only the guide-wire and the two are clearly visible (image obtained on an Innova 2100 system from GE). .................................... xv List of figures xvi 1.16 Clinicians performing an angioplasty. Note the use of the stent visualization enhancement software on the top left screen that is the output of the work presented in Chapter 2. This image depicts a stent that has just been deployed with an image quality far superior to conventional Xray [FGBV09]. Image courtesy of Dr. T. Lefèvre, Dr. M-C. Morice, Dr. T. Hovasse, Dr. B. Chevalier, Dr. Y. Louvard -Institut Cardiovasculaire Paris Sud, Massy, France ........................... 1.17 Stent visualization enhancement results obtained with: (a) state of the art linear registration, (b) our non-linear one. Observe that the stent is sharper in (b). ................................. 1.18 Planar layer modeling of a DSE image: 3 separate layers, namely the anatomical background, the guide-wire and the stent, are combined in the image formation mechanism. ....................... 1.19 Left: input image. Center: DSE image (note that the background layer has been removed). Right: guide-wire subtracted image. .......... 1.20 3D coronary stent reconstruction at a bifurcation. ............. 1.21 A 3D stent slice: on the left classical processing, on the right the guidewire has been subtracted between the markers. The stent border that is hidden by the guide-wire on the left is visible on the right, at the location indicated by the arrows. ............................ 1.22 Volume rendering of a reconstructed stent. Left: state of the art reconstruction technique. Right: The reconstruction benefited from the extension of our stent techniques to the 3D case. The motion compensation is performed with non-linear registration and the guide-wire has been removed from the image. Notice that the overall stent shape is easier to delineate. .................................... 1.23 Left: a frame of a short static acquisition. Center: automatically segmented markers and guide-wire. Right: Close up on the segmented interventional tools. ................................. 1.24 Markers and guide-wire automatically segmented in three frames of a

1 .

 1 26 Illustration of two applications of P. Top left: a clinical image illustrating a guide-wire. Top right: line enhancement by smooth local path voting. Bottom left: aggressive contrast setting on the image displayed in top right reveals its structure: A path attracted by linear structures originates from each pixel of the image. Bottom right: Direction field estimated with P. ........................................ 1.27 Top [Med11] principle of the FFR: the device allows to compute the ratio of pressures distaly and proximaly to the lesion in the hyperhemic state. Bottom [CJHJ05] effect of thrombus aspiration and balloon dilatation in an occluded artery. ............................... 2.1 Left: a coronary stent imaged with Xray. Right: Result after DSE. .... 2.2 (a) An image from a clinical image sequence with the clinician's tools positioned in the patient's vasculature; (b) the region in (a) delimited by the gray square with annotation of tools/devices; (c) the region in (b) inside the gray square with a deployed stent; (d) demonstration of the improved stent visualization by the application of DSE to (a). This last image has been produced with StentViz, the DSE feature of GE, that is partly described in this chapter. ........................ 2.3 General architecture of a DSE algorithm. .................. 2.4 Left: Illustration of a deployed stent in an x-ray image processed with

2. 23

 23 Figures illustrating the characterization of the guide-wire segmentation. (a) Input clinical image, (b) Guide wire segmented on image (a),( c ) Image (a) degraded up to three times the original noise, (d) Guide wire segmented on image (c), (e) Another input clinical image, (f) Ground truth (in black) and actual segmentation (in white) of the guide-wire in image (e) degraded. The Hausdorff distance, of 12 pixels in this case, is illustrated by the dashed white line. ..................... 2.24 Histogram of the Hausdorff distances in pixels between the ground truth guide wires and the ones segmented on degraded images. ......... 2.25 Image quality scores histograms. In gray the values before DSE and in black after. ................................... 2.26 Image quality score histograms in fluoro and cine separately before and after DSE (StentViz). ............................. 2.27 Histogram of the DSE score in cine minus the score in fluoro averaged over the two raters. ............................... 2.28 (a) Image obtained with StentViz; (b) I ∆ ; (c) ROI to compute ∆. Observe that on the markers the two motion fields are identical (black spots in (b)) but differ on the rest of the image. (d) All the segmented guide wires registered by the marker ball based techniques. Note that they are not accurately registered outside of the markerballs. ............... 2.29 Histogram of the measures of ∆ over the database, indicating the average difference between the transformations. ................... 2.30 Comparison of the linear and the non-linear registration on two sequences where the difference is of category B. (a) Sequence 1 processed with the linear registration, (b) Sequence 1 processed with the non linear registration, (c) Sequence 2 processed with the linear registration, (d) Sequence 2 processed with the non linear registration. ................. 2.31 Histogram of StentViz image score -StentOp Image score; Hypothesis H 0 is represented by the blue dot. 95% confidence interval for the difference of scores is represented in red (rated by: Left reader 1, center reader 2 and right reader 3). ............................... 2.32 Two examples ((a) and (b)) and the images produced by StentViz ((c) and (d)) and StentOp ((e) and (f)). Note that with StentViz the details of the stent are more visible. ......................... 2.33 DSE image: Observe the plaque indicated by the arrow that prevents the proper deployment of the stent. ........................ 2.34 Use of DSE to optimize stent overlapping. .................. 2.35 Use of DSE for a bifurcation treatment procedure. Top: bifurcation before treatment presenting significant stenoses. Center row: a first stent is deployed / a second stent is positioned next to it / both stent expanding (note the overlapping) / stent shape is further modified by balloon inflation in the side branch. Bottom: Final angiographic result of the treated bifurcation. ................................... 2.36 Use of DSE to detect stent fracture. Left: a coronary aneurysm is indicated by the arrow. Center: DSE enables to see that the aneurysm is linked with the stent rupture indicated by the arrow. Right: after treatment. .................................... List of figures xx 2.37 Illustration of the variability of the appearance due to strut superimpositions patterns. (a) and (b) depict a same stent under two viewpoints differing from few degrees. ........................... 2.38 Illustration of imperfect registration in some cases (see text for details).

  ............................. 3.1 (a) input image. (b) output image of StentViz "guide-wire subtracted", top regular DSE image, bottom guide-wire subtracted. ........... 3.2 Scheme illustrating the difficulties in stent visualization introduced by the presence of the guide-wire. Top: the guide-wire hides the structure of the stent struts; Middle: the guide-wire hides partially the border of the stent; Bottom: ideal case for stent visualization where the guide-wire is not displayed (images are adapted from a Cypher stent photo [tim05]). .. 3.3 Stent visualization difficulties in clinical DSE images. Left: the guidewire hides the structure of the stent struts; Right: the guide-wire hides partially the border of the stent. ....................... 3.4 Illustration of the continuous (volumetric) Xray image formation model (left) and the discrete planar layer model (right). .............. 3.5 Planar layer modeling of a DSE image: 3 separate layers, namely the anatomical background, the guide-wire and the stent, are combined in the image formation mechanism. ....................... 3.6 Background subtraction in DSE images. Left: motion compensated integration of the images. Right same as left performed on background subtracted images. ............................... 3.7 Anatomy of a coronary guide-wire illustrating its main components: the core, the cover and the tip (Figure reproduced from [ENS + 10]). ...... 3.8 Theoretical attenuation profile of a uniform cylindrical guide-wire imaged with a perfect system (MTF = dirac). Abscissa: distance to the centerline in pixels (the radius of the guide-wire is here 1,5 pixels). Ordinates: attenuation factor (no dimension). ...................... 3.9 From left to right: DSE image, guide-wire subtracted image, estimated guide-wire layer, curve of the intensities of the pixels on the guide-wire in the DSE image. Observe on the curve all the variations induced by the stent signal as a consequence of the transparency of X-ray images. .... 3.10 From left to right: input image, estimated guide-wire layer, guide-wire subtracted image. ................................ 3.11 From left to right: regular DSE image, guide-wire subtracted DSE image, both downscanned to fit the display, both cropped on the area of interest to fit the display. ................................ 3.12 Simultaneous display of two DSE image with/without guide-wire subtraction in the case of a diagonal stent. The area of interest is represented by the union of the three squares in the upper part. .............. xxi 3.13 Attenuation profiles of 10 guide-wires in clinical cases estimated with the average (left) and the median (right). Abscissa: distance to the guidewire centerline in pixels. Ordinate: attenuation factor (no dimension). The average profile with both methods is plotted with a dashed line. ... 3.14 Guide-wire subtraction results: left average, right median. Observe on the image on the left the white line (artifact) at the center of the stent. .9 3.15 (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction. ................................... 3.16 (a) input image. (b) guide-wire subtracted image. The guide-wire sub-

  Such a finding can encourage the cardiologist to repeat a StentViz acquisition with a different viewing angle. ...................................... 3.19 (a) input image. (b) guide-wire subtracted image. The subtraction proved to be efficient in this stent in stent situation (two stents are superimposed in the lowest part). StentViz enables to understand the relative positioning of the two stents. .............................. 3.20 (a) input image. (b) guide-wire subtracted image. Perfect subtraction example. ..................................... 3.21 (a) input image. (b) guide-wire subtracted image. Excellent guide-wire subtraction. ................................... 3.22 (a) input image. (b) guide-wire subtracted image. Excellent guide-wire subtraction. ................................... 3.23 (a) input image. (b) guide-wire subtracted image. Interesting case where the guide-wire is constantly at the same distance to the stent border. Thanks to the median estimator in the estimation of the attenuation profile the processing is robust to such situations. .............. 3.24 (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction. ................................... 3.25 (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction. ................................... 3.26 (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction. ................................... 3.27 This case is of particular clinical interest. The guide-wire subtraction (on the right) reveals the border of the stent that is not straight, as indicated by the arrow. This finding was not obvious in the regular DSE image (left).100 xxii 3.28 (From left to right: Regular contrast setting (no saturation); Aggressive contrast setting allows to improve the display of the stent but saturate the guide-wire; With guide-wire subtraction this contrast setting does not create saturation in the stent area. ......................1 4.1 3D coronary stent reconstruction at a bifurcation. .............1 4.2 Illustration of a locally under-deployed stent in a pig artery. In image (a) the under-deployment circled in blue is visible. In image (b), under a different viewing angle the defect is hardly noticeable (images from [Per08]).103 4.3 (a) A frame of the input sequence. (b) Visualization of the stent reconstruction with the method of Perrenot [Per08]. (c) Same stent reconstructed with a CT scan. Images extracted from [Per08]. ..........1 4.4 Five images extracted from a rotational acquisition. Note the changes in balloon appearance and marker position. In the second image, one of the markers is overlapping the tip of the catheter, making it hardly visible. In the third image sternal wires appear, and in the fourth the markers overlap the guide-wire tip. ...........................1 4.5 General overview of the marker tracking algorithm. .............1 4.6 Merging two potentially overlapping tracks A and B is reduced to merging non overlapping ones by assigning all the common indexes to either one or the other. ...................................1 4.7 Two non overlapping tracks C and D are represented. The merging point couples (ξ(C, D) in the text) are represented with a wider black border. . 110 4.8 Plot of the length of the detected marker segment versus the frame index. False positives are circled in green. ......................1 4.9 (a) et (b): Frames 158 and 160 of a clinical sequence. The actual markers have been detected at the locations indicated in green. However, in the intermediate frame (number 159) they have not been detected. (c) The set of detected pairs in frame 159. The actual marker pair does not belong to them. (d) The ROI for pairing and the new set of pairs in frame 159, based on the detected markers in the previous and next frames. (e) Extract from (c) where we can observe that the actual markers did not belong to the set of detected pairs. ......................1 4.10 Top: Example of wrong marker labeling. Bottom: A typical case where marker labeling is a difficult case because the markers invert their relative positions along the sequence. .........................1 4.11 3D reconstruction of the center point from 3 detections. ..........1 4.12 Plane associated with a marker couple i. ...................1 4.13 Projection of the rough 3D model on the image, translation of the projected segment and labeling of the detected marker couple (in green). ...1 4.14 3 images of a spin sequence. Top row: original image. Central row: segmented guide-wire. Bottom row: subtracted guide-wire. ........1

1 4 . 1 List of figures xxiv 4 .

 414 18 Automated marker detection and labeling on sequence 3. .........1 4.19 Left: 3D stent model reconstructed from sequence 3. Right: 3D stent of sequence 6 (bifurcation case) .........................1 4.20 3D stent reconstructions from left to right: sequence 2, 3a and 1a. ....1 4.21 Left longitudinal slice / Right axial slice of the reconstructed stent (image from [Per08]). ..................................1 4.22 3D stent slice: Left classical processing, right guide-wire subtracted between the markers. The stent border hidden by the guide-wire on the left is visible on the right, as indicated by the white arrows. The guidewire subtraction process attenuates the guide-wire signal, but in the 3D volume a mark still persists. ..........................1 4.23 Left: state of the art. The transform to register the markers is a similarity and the guide-wire is not subtracted; center: radius preserving affine registration and guide-wire subtraction; right: non-linear registration and guide-wire subtraction. The three rows illustrate different viewing angles of the same stent. Observe on top right that the strut pattern appears in the upper side of the stent. This pattern is not visible on the left image. On the bottom right the general shape of the stent can be easily assessed (this it is not the case on the left). ......................1 4.24 Comparison of the similarity transform (right) and of the non-linear one (left), in the slices of a reconstructed stent volume (same example as Fig. 4.23. Guide-wire has been subtracted in both cases. ............25 Stability of the estimation of the parameters of the 2D registration versus the marker segment length. Left: inverse of the marker segment length (in pixels) vs the frame index. Right: estimated rotation angle in radians vs the frame index. ...............................1 4.26 Volume rendering of a same stent, with (left) and without (right) balloon inflation.

Fig. 5 .

 5 [START_REF]Comparison of the line enhancement techniques. SOD stands for Second Order Derivative, RLT for Rotated Line Template and SF for Steerable Filter[END_REF] and associated to each pixel the cost of the path originating from it. We can observe that the image is complex and that linear structures tend to extend to neighbor pixels. ......................................1 5.20 Path voting on the image illustrated on Fig. 5.5. See section 5.5.3 for details on the pre-processing. .........................1 5.21 A more aggressive contrast setting (saturation) of fig 5.20 shows lower values of the image. We see some path that are attracted by the guidewire. Especially close to the tip. .......................1 5.22 Even more aggressive contrast setting of image fig 5.20 enables to see its complex structure. ...............................1 5.23 Similar image as fig 5.20 except that constrained path smoothness, rejecting any path of tortuosity lower than 0.6 ...................1 5.24 A more agressive contrast setting (saturation) of fig 5.23 shows lower values of the image. We see some path that are attracted by the guidewire. Especially close to the tip, however there are less such path than in 5.21 thanks to the tortuosity constraint. ...................1 5.25 Even more agressive contrast setting of image fig 5.20 enables to see its complex structure. Compared to fig 5.22 we see that the most tortuous path have been removed. ............................1 5.26 ϑ(P) with 3 pixel long polygonal segments (top) and 11 pixel long segments (bottom) for a similar total path length. In the left column (nominal windowing) we observe that the curvilinear structure appear tortuous with short path segments and smooth with longer segments (as in the original image). ................................1

  (c)). Indeed, the only other finite cost path is the one going though C, but it does not verify the curvature bound constraint. Therefore d(A, B) = 3. Similarly d(A, C)=d(C, B) = 1. Finally: d(A, B) >d(A, C)+d(C, B). .......1 5.31 The cone distance. ...............................1 5.32 Counter example for the triangular inequality on λ. We consider the 4 cones used by Vincent [Vin98] that we group in two pairs of opposite cones, illustrated on (a) and (b). We build a particular potential cost image (b) where: all the image has cost ∞ except the three paths that are drawn. Let L AB be the length of the path from A to B, we assign to each pixel on this path the cost 3/L AB . Consequently the whole path cost is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB .T h e c o s to fe a c ho ft h e s et w op a t h si st h u s1 . T h e nw en o t et h a tt h eo n l y finite cost path from A to B is the one that is drawn that is included in cone (a) (see Fig. (c)). Therefore λ(A, B) = 3. Similarly λ(A, C)=1 . The only finite cost path from C to B is the one that is drawn, and it is in the cone (b) (see Fig. (d)). Consequently λ(C, B) = 1. Finally: λ(A, B) >λ(A, C)+λ(C, B). .........................1 5.33 Illustrations of R A,B , for several configuration of A and B with the set of four non-overlapping cones presented in Fig 5.8. In this case R A,B is the inter-visibility parallelogram. .........................1 5.34 Images extracted from [BC09] .........................1 5.35 Application of the PSI to clinical examples. .................1 5.36 Application of the PSI to clinical examples. .................1 5.37 Application of the PSI to clinical examples. .................1 xxvii 5.38 Application of the PSI to clinical examples. .................1 5.39 Illustration of the performance of the line enhancement techniques (measured by the partial AUC) on each sequence of the database. Top: FPR is computed on the whole image. Bottom: FPR is computed only in a band around the guide-wire. ..........................1 5.40 Average performance of four line enhancement techniques over our database of clinical cases. Top: FPR is computed on the whole image. Bottom: FPR is computed only in a band around the guide-wire. ..........1 5.41 MDR (blue), FDR (red) and MDR+FDR (green) as a function of the threshold in three different clinical cases. As expected, MDR increases, FDR decreases and their sum has a clear minimum. In this experiment we chose 500 thresholds regularly sampled between the max and the min of the image. ..................................1 5.42 Top: input image. Middle row: Frangi (left) and RLT (right). Bottom row: ϑ(P)( l e f t )a n dϑ τ min (P) (right). Observe that traditional methods (middle row) enhance a large amount of non relevant structures in the background. Moreover, they fail to enhance some parts of the guide-wire. These problems are not present with ϑ τ min (P). ...............1 5.43 Similar experiment as Fig. 5.42 on another clinical case. This one is the most challenging case yielding the poorest results due to the presence of the ribs that are very visible under this viewing angle and of sternal wires (first sequence in Fig. 5.39). Same observations apply. ...........1 5.44 Similar experiment as Fig. 5.42 on another clinical case. Same observations apply. ...................................1 5.45 Similar experiment as Fig. 5.42 on another clinical case. Same observations apply. ...................................1 5.46 Similar experiment as Fig. 5.42 on another clinical case. Same observations apply. ...................................1

Chapter 1 Introduction

 1 This PhD thesis in the field of image processing falls into the context of curing coronary heart disease, the leading cause of death for both men and women worldwide. One of the most common treatment option is a minimally invasive procedure monitored under Xray fluoroscopy. It consists in the deployment of a stent (a fine scaffolding of wire), in the clotted artery to re-open it and restore the blood flow. The proper deployment of the stent and its apposition to the vessel wall are key to the success of the intervention.

Figure 1 . 1 :

 11 Figure 1.1: Simplified view of the cardiovascular system (Copyright c Addison Wesley Longman, Inc publishing as Benjamin Cummings).

Figure 1 . 2 :

 12 Figure 1.2: Overview of the coronary arteries [LtOH10].

Figure 1 . 3 :

 13 Figure 1.3: Progression of the atheromatous stenosis over decades, potentially rupturing putting the patient at risk of major adverse events (image from [Chi06]).

Figure 1 . 4 :

 14 Figure 1.4: Visualization of a diseased artery under Xray fluoroscopy (angiography)with an Innova 2100 Xray system (GE)

Figure 1 . 5 :

 15 Figure 1.5: Quantitative coronary analysis allows the clinician to estimate the percentage of lumen reduction induced by the presence of the stenosis (Quantitative Analysis Software developed by Pie Medical Imaging BV c ; pictures courtesy by Pie Medical Imaging BV. Reproduced from [esa11]).

Figure 1 . 6 :

 16 Figure 1.6: Balloon angioplasty [NIH10b] and stenting [NIH10c] procedures.

Figure 1 . 7 :

 17 Figure 1.7: Illustration of a bypass [NIH10a].

[

  GS10b]) demontrasted the superiority of DES over Bare Metal Stents (BMS) resulting in significant reductions in angiographic in-stent-late-loss, in-stent angiographic binary restenosis, and repeated vascularisation at both short term and long term follow up, over numerous types of patients and lesions. However rates of death and myocardial infarction at long term follow up are comparable. Today 75% of the revascularisation procedures for patients suffering from CAD are performed with DES.

Figure 1 . 8 :

 18 Figure 1.8: Angiograms of Dotter's 1st catheter patient, Laura Shaw: A) before transluminal dilation of the left superficial femoral artery, B) immediately after dilation, and C) 3 weeks after the procedure (image from [Pay01]).

Figure 1 . 9 :

 19 Figure1.9: Visualization of a right coronary artery under Xray fluoroscopy before and during contrast media injection. We note that in the absence of contrast the medical tools inside the artery are visible but not the artery itself. When contrast media in injected, the artery is visible but the medical tools become hardly visible (images obtained on an Innova 2100 system of GE healthcare).

Figure 1 . 10 :

 110 Figure 1.10: Various popular coronary stents. From left to right: Cypher [Hos07], Endeavor [ptc09], Taxus Liberte [DC09], Xience V [DC10b]. Note that the metal meshesare quite different from one stent to another and can be rather complex.

Figure 1 . 11 :

 111 Figure 1.11: In stent restenosis (image from [NIH10d]). This complication was common with bare metal stents. It decreased very significantly with the introduction of drug eluting stents.

  1.13). This aspect of the lesions is checked by the clinicians and is taken into account in the American College of Cardiology/American Heart Association (ACC/AHA) stenosis morphology classification (making the lesion at least of type B). This calcium happens to complicate the stent deployment since it makes the vessel more rigid. It can impact the choice of the tools (the balloon and its pressure) used for (re)deployment and of the procedure since the clinician may pre-dilate before stenting to maximize the chances of proper lesion treatment. Visualizing the calcium and its position relatively to the stent is thus of interest to the clinician. Moreover calcium deposit has gained interest over the past years in the context of CT scans since it has been demonstrated to provide predictive information beyond that of classical risk factors [GLA + 04].

Figure 1 . 13 :

 113 Figure 1.13: Calcification are very well visualized with Computed Tomography [DC10a]. They appear in white, around the lumen of the artery.

Figure 1 . 14 :

 114 Figure 1.14: Stent cross section in OCT versus conventional angiography [Lod10].

Figure 1 .

 1 Figure 1.15: Coronary stent image with conventional Xray (image zoomed on the stent). Note that the stent is almost invisible, only the guide-wire and the two balloon markerballs are clearly visible (image obtained on an Innova 2100 system from GE).

I

  performed the work presented in this PhD thesis concurrently with my full-time research-engineer position at GE Healthcare. I had held this position since nearly 6 years when I started this project, in collaboration with the A3SI team at ESIEE. Both institutions were complementary: GE impulsed a result-oriented and application-driven direction to my work, while ESIEE was instrumental in the formalization of my contributions and in the developement of new techniques. From an organizational standpoint, I dedicated one day per week to my PhD activities at ESIEE, and the rest of the week to my research-engineer position. The time spent at GE was mainly dedicated to the developments of image processing algorithms, their evaluation in clinical setting and their adaptation into industrial products. The time at ESIEE was spent on brainstorming, writing, learning and teaching.

2 and 4 )

 4 , passing through registration, curvilinear structure segmentation (Chapter 5) and layer separation (Chapter 3). I have chosen to present this PhD guided by the applicative direction that is common to the entire document: device visualization enhancement. It has been the subject of several publications and patent applications [BV08b, BVG09, BVF + 11, VLB06, BV10, VB10, FGBV09, FLBV10].

Figure 1 . 16 :

 116 Figure 1.16: Clinicians performing an angioplasty. Note the use of the stent visualization enhancement software on the top left screen that is the output of the work presented in Chapter 2. This image depicts a stent that has just been deployed with an image quality far superior to conventional Xray [FGBV09]. Image courtesy of Dr. T. Lefèvre, Dr. M-C. Morice, Dr. T. Hovasse, Dr. B. Chevalier, Dr. Y. Louvard -Institut Cardiovasculaire Paris Sud, Massy, France

Figure 1 . 17 :

 117 Figure 1.17: Stent visualization enhancement results obtained with: (a) state of the art linear registration, (b) our non-linear one. Observe that the stent is sharper in (b).

Figure 1 .

 1 Figure 1.18: Planar layer modeling of a DSE image: 3 separate layers, namely the anatomical background, the guide-wire and the stent, are combined in the image formation mechanism.

Figure 1 .

 1 Figure 1.19: Left: input image. Center: DSE image (note that the background layer has been removed). Right: guide-wire subtracted image.

  1.23)a n dw ea d a p ti tt o the rotational case in Chapter 4 (Fig. 1.24) by revisiting the cinematic hypotheses and taking into account 3D motion consistency. These fully automated methods yield state of the art performance.

Figure 1 .

 1 Figure 1.20: 3D coronary stent reconstruction at a bifurcation.

Figure 1 .

 1 Figure 1.21: A 3D stent slice: on the left classical processing, on the right the guidewire has been subtracted between the markers. The stent border that is hidden by the guide-wire on the left is visible on the right, at the location indicated by the arrows.

Figure 1 . 22 :

 122 Figure 1.22: Volume rendering of a reconstructed stent. Left: state of the art reconstruction technique. Right: The reconstruction benefited from the extension of our stent techniques to the 3D case. The motion compensation is performed with nonlinear registration and the guide-wire has been removed from the image. Notice that the overall stent shape is easier to delineate.

Figure 1 .

 1 Figure 1.23: Left: a frame of a short static acquisition. Center: automatically segmented markers and guide-wire. Right: Close up on the segmented interventional tools.

Figure 1 .

 1 Figure 1.24: Markers and guide-wire automatically segmented in three frames of a rotational acquisition (top row: original images -bottom row: segmented interventional tools). Observe that the markers exchange their relative positions as a result of the gantry rotation.

Figure 1 .

 1 Figure 1.25: Top left: an extract from a cine image depicting a set of smooth paths between two endpoints. Top center: A clinical image corrupted with a high level of noise. Top right: guide-wire segmented with our method between the two markerballs.Bottom left: A clinical image depicting a guide-wire. Bottom center: 3 candidate curves (note that the blue one is well aligned with the guide-wire centerline whereas the red and green ones are not). Bottom right: The three averaged profiles (same color code as bottom center). Abscissa is the signed distance to the curve and ordinate is the pixel intensity. Only the profile of the blue curve that is aligned with the guide-wire exhibits a marked minimum at its center.

  to the evaluation and validation of the proposed algorithms in clinical settings. The image quality of the digital stent enhancement technique studied in Chapter 2 has been validated on nearly 200 clinical cases and its detection and tracking capabilities on several thousands of frames. Similarly, the detection and tracking algorithm in rotational acquisitions (Chapter 4) has been validated on a set of 22 sequences totalizing 3000+

Figure 1 .

 1 Figure 1.26: Illustration of two applications of P. Top left: a clinical image illustrating a guide-wire. Top right: line enhancement by smooth local path voting. Bottom left: aggressive contrast setting on the image displayed in top right reveals its structure: A path attracted by linear structures originates from each pixel of the image. Bottom right: Direction field estimated with P.

Figure 1 .

 1 Figure 1.27: Top [Med11] principle of the FFR: the device allows to compute the ratio of pressures distaly and proximaly to the lesion in the hyperhemic state. Bottom [CJHJ05] effect of thrombus aspiration and balloon dilatation in an occluded artery.

  In this chapter1 we propose a comprehensive study of Digital Stent Enhancement (DSE), from the analysis of requirements to the validation of the proposed solution. First, we derive the stent visualization requirements in the context of the clinical application and work-flow. Then, we propose a DSE algorithm combining automatic detection, tracking, registration and contrast enhancement. The most original parts of our solution: landmark segmentation and non-linear image registration are detailed. Finally, we validate the algorithm on a large number of synthetic and clinical cases. Performance is characterized in terms of image quality, automation, and execution time. This work is, to the best of our knowledge, the first comprehensive work on DSE, covering problem statement, proposed solution, and validation strategies.

Figure 2 . 1 :

 21 Figure 2.1: Left: a coronary stent imaged with Xray. Right: Result after DSE.

Fig. 2 . 2 (

 22 b) depicts a part of an X-ray image, with a guide-wire, the deflated balloon (invisible), its two marker-balls and the deployed stent. Proper positioning of the stent and apposition onto the vessel wall are key to the success of the procedure and patient safety [GS10b, ASPV + 07, FCM + 05, BDJ + 04].

Figure 2 . 2 :

 22 Figure 2.2: (a) An image from a clinical image sequence with the clinician's tools positioned in the patient's vasculature; (b) the region in (a) delimited by the gray square with annotation of tools/devices; (c) the region in (b) inside the gray square with a deployed stent; (d) demonstration of the improved stent visualization by the application of DSE to (a). This last image has been produced with StentViz, the DSE feature of GE, that is partly described in this chapter.

Figure 2 . 3 :

 23 Figure 2.3: General architecture of a DSE algorithm.

Figure 2 . 4 :

 24 Figure 2.4: Left: Illustration of a deployed stent in an x-ray image processed with standard contrast enhancement techniques, which may be considered a form of DSE. The resulting stent visualization is substantially inferior to that produced with a dedicated technique, as shown on the right.

  times blurrier due to heart motion velocity. Sharpness is thus intrinsically related to the precision of the registration. Registration is crucial, considering the stent geometry relative to the optical magnification and detector pixel pitch. Stent struts are typically 0.16 mm wide, less than 0.2 mm pitch [RLM + 05]. Taking into account a typical magnification factor of 1.4 for cardiac interventions, the projection of the stent struts onto the detector are on the order of one pixel. Finally the stent structure is blurred by the system Mean

Figure 2 . 5 :

 25 Figure 2.5: Study of the impact of the misregistration error. Image after the application of DSE with various misregistration magnitudes. The images were produced by registering thirty frames with a registration error following a uniform distribution and averaging the frames. The misregistration magnitude is indicated in pixel units below each image.

Figure 2 . 6 :

 26 Figure2.6: Schematic illustration of the limitations of the linear, marker-ball based registration realized with an image processing software for explanatory purpose (not necessarily geometrically exact). The two top images are two images of a same stent. Bottom is the marker-ball based registration. Although the two marker-balls are accurately registered, the stent, that underwent a non-linear deformation is not accurately registered. The guide-wire that supports the marker-balls is also undergoing a nonlinear deformation. We use it as additional landmark in our nonlinear registration.The stent image is derived from a photo of a Cypher coronary stent[tim05]

  the best of our knowledge image combination in the context of DSE has not been studied so far. All the authors [RLM + 05, KL05, Koo05, SF09] propose to simply average the values of the motion compensated images to produce the DSE image. In the context of Digital Subtracted Angiography (DSA), this topic has been studied in more details [KSW01b, KSW01a, SGH + 04, LT05]. Authors propose a wide variety of techniques: rank filters [KSW01b, KSW01a], match filters [KSW01b, KSW01a], entropy measurement [SGH + 04] and learning based approaches [LT05]. However, the problem is totally different from DSE: in DSA authors want to capture the arrival of contrast media that induces a change in the temporal series of values at a given pixel. On the contrary, in DSE the main hypothesis is that there is little change in the motion compensated images object along time. Therefore the image combination techniques we propose in this section are significantly different.

σ 2 W

 2 n(1-p) 2 where σ W is a function of the truncated moments of the Gaussian distribution[START_REF] Stigler | The asymptotic distribution of the trimmed mean[END_REF]). We estimate them under the assumption of centered normalized and uncorrelated Gaussian variables {X i } i through simulation (Fig.2.7).

Figure 2 . 7 :

 27 Figure 2.7: Standard deviation of the estimators versus the number of images in the input sequence. Results obtained with one billion simulations. Observe the general decreased in n -1/2 predicted by the theory for the empirical mean, the trimmed means and the median.

Figure 2 . 8 :

 28 Figure 2.8: Application of the background subtraction to a clinical image. Left: Original. Right: Background subtracted. Observe that most of the structures have disappeared.

Figure 2 . 9 :

 29 Figure 2.9: Simulated vs estimated noise on two clinical cases for the 9 estimators: red and purple are estimated, blue and green are simulated. The overall precision of our model is typically 10%.

Figure 2 .

 2 Figure 2.10: Result of the different estimators on a clinical case. Left column: result obtained with Xn (reference). Center: Result obtained with the considered estimator. Right: difference image. From top to bottom: X (0) , X ([n/4]) , X ([n/2]) , X ([3n/4]) , X (n) , Tn,[ p

Figure 2 .

 2 Figure 2.11: Combined image. From left to right: Xn , Tn,[ p 2 n],[ p 2 n] , Tn,[pn],0 and Tn,0,[pn] . Observe that Tn,[ p 2 n],[ p 2 n] and Tn,[pn],0 allow to attenuate the undesirable guidewire multiplication effect far from the landmarks.

Figure 2 .

 2 Figure 2.12: Noise reduction as a function of the number of combined frames (1, 10, 20, 30, 40, 50 and 60 when available) with the empirical mean estimator for four different clinical sequences (one color for each: red, blue, purple and green). Solid line, manual estimation, dashed line theoretical noise with the σn -1/2 model. Ordinate: noise standard deviation; Abscissa: number of averaged frames.

Figure 2 .

 2 Figure 2.13: DSE images for different numbers of averaged frames: from top to bottom 1, 10, 20, 30, 40, 50 and (when available) 60. Image have undergone background subtraction as recommended in Section 2.3.2.1. Observe on the very low stent visibility in the original data on top row. Visibility increases rapidly in the first rows, then stagnates.

  2.14): landmark detection and tracking, image registration, image combination, and display processing.A bottom-up approach is pursued in landmark detection and tracking. First, in each image, we detect points representing potential marker-balls, then we form pairs of points and build tracks of pairs. The detection of the potential marker-balls is close to the problem of detecting micro calcifications in mammograms[START_REF] Cihan | An application of topological median on detection and clustering of microcalcification in digital mammograms[END_REF][START_REF] Grimaud | La géodésie numérique en morphologie mathématique[END_REF]. Similarly, we pre-process images with a dark top hat [Soi99]. It enables the removal of the background variations while retaining dark objects of a given scale. In practice with a relevant setting of the structuring element, the marker-balls, the guide-wire and the stent are preserved (Fig.2.15). Moreover efficient implementations exist [vH92]. In the resulting image the potential marker-balls can be characterized as being local minima in a given range of intensity. Forming pairs of potential markers and building tracks of pairs along the sequence (Fig.2.16) is constrained by a priori knowledge of device (stent/marker ball/guide wire) geometry, and the characteristics of cardiac motion (see section 2.3.4). We assign a figure of merit to each track based on its regularity and attenuation properties of its candidate markers. Finally, we identify the most promising track and we segment the guide-wire supporting each pair of markers.Image registration of the stent relies on a model to infer stent motion from the position of the landmarks. Each image is registered to a reference position in a non-linear fashion.

Figure 2 . 14 :Figure 2 .

 2142 Figure 2.14: Block diagram of our DSE technique.

Figure 2 .

 2 Figure 2.16: Illustration of the "detection and tracking" brick of our DSE. Top row, from left to right: original image, candidate points, candidate pairs formed out of the points. Bottom row, from left to right: three successive frames and the detected candidate pairs. Among them the tracking was able to build five relevant tracks.

  (d) and Fig. 2.18). Then contrast is measured by computing the difference between the value at the minimum and the values at the extremities. Evaluations on clinical data have demonstrated that this method enables guide-wire segmentation in extremely noise-corrupted images (Section 2.4.1.4 and Fig. 2.23 (c) and (d)).(a) (

Figure 2 .

 2 Figure 2.18: Top left: an extract from a cine image depicting the guide-wire, the stent and the markerballs. Top right: 3 candidate curves (note that the blue one is well aligned with the guide-wire centerline whereas the red and green ones are not).Center: All the profiles extracted for each curve (same color code as top right). On the abscissa is the signed distance to the curve and on the ordinate the pixel intensity. Bottom: The three average profiles. Only the one of the blue curve that is aligned with the guide-wire exhibits a marked minimum at its center.

Figure 2 .

 2 Figure 2.19: (a) Notations for the curve based registration. (b) Schematic illustration of the motion field on the landmarks

Figure 2 .

 2 Figure 2.20: Coronary stents are very rigid on their radial axis to handle the pressure of the artery wall, but very flexible in the perpendicular direction to conform to the curvature of the artery.

Figure 2 .

 2 Figure 2.21: In dark (top), histogram of the percentage of the true positive per image sequence. In gray, histogram of false positive per image sequence (center). In white (bottom), histogram of false negative per image sequence.

Figure 2 .

 2 Figure 2.22: An image of a synthetic marker-ball and guide-wire used to quantify the precision of the marker-ball segmentation.

Figure 2 . 23 :

 223 Figure 2.23: Figures illustrating the characterization of the guide-wire segmentation. (a) Input clinical image, (b) Guide wire segmented on image (a), (c) Image (a) degraded up to three times the original noise, (d) Guide wire segmented on image (c), (e) Another input clinical image, (f) Ground truth (in black) and actual segmentation (in white) of the guide-wire in image (e) degraded. The Hausdorff distance, of 12 pixels in this case, is illustrated by the dashed white line.

Figure 2 .

 2 Figure 2.24: Histogram of the Hausdorff distances in pixels between the ground truth guide wires and the ones segmented on degraded images.

For most of the

  patients, several sequences were collected, because fluoroscopy and cine acquisitions were performed and/or because several stents were placed. The set of sequences includes 110 fluoroscopy and 86 cine. In 72 cases, a cine and a fluoroscopy of the same patient at the same stage of the intervention have been collected (representing a total of 144 sequences). It enabled comparing the performances of DSE in both acquisition modes.

Fluoroscopic sequences included in

  the study present the advantage of requiring less Xray dose but the drawback of having lower image quality. We investigated how it interacts with DSE. We have compared the performance of DSE on fluoro versus cine by comparing the IQ scores of the 72 cases where both have been acquired in comparable conditions. The fluoroscopic sequences improved from 1.3 ± 0.6t o2 .7 ± 1.1 after processing and the cine from 1.5 ± 0.7to3.2 ± 1.0. We have confirmed that these differences are statistically meaningful by performing paired T-tests. The input cine sequences have better IQ than the input fluoroscopy (p ≤ 0.001, 95% CI [0.2, 0.4]). As expected, the DSE images derived from cine sequences have better IQ than the DSE images derived from fluoroscopic sequences (p ≤ 0.001, 95% CI [0.3, 0.6]). The histograms of the distributions are represented on Fig.2.26. We observe a shift of population towards higher score passing from fluoroscopy to cine. In order to quantify the proportion of sequences

Figure 2 .

 2 Figure 2.25: Image quality scores histograms. In gray the values before DSE and in black after.

Figure 2 .

 2 Figure 2.26: Image quality score histograms in fluoro and cine separately before and after DSE (StentViz).

  ers and the proposed curve-based registration taking into account the markers and the guide. The increased level of complexity brought by the curve-based transform only makes sense if it differs significantly from the similarity on a relevant proportion of clinical cases. One notices that the 2 proposed transforms are obviously equal on the

Figure 2 .

 2 Figure 2.27: Histogram of the DSE score in cine minus the score in fluoro averaged over the two raters.

Figure 2 .

 2 Figure 2.28: (a) Image obtained with StentViz; (b) I ∆ ; (c) ROI to compute ∆. Observe that on the markers the two motion fields are identical (black spots in (b)) but differ on the rest of the image. (d) All the segmented guide wires registered by the marker ball based techniques. Note that they are not accurately registered outside of the markerballs.

Figure 2 . 29 :

 229 Figure 2.29: Histogram of the measures of ∆ over the database, indicating the average difference between the transformations.

Figure 2 . 30 :

 230 Figure 2.30: Comparison of the linear and the non-linear registration on two sequences where the difference is of category B. (a) Sequence 1 processed with the linear registration, (b) Sequence 1 processed with the non linear registration, (c) Sequence 2 processed with the linear registration, (d) Sequence 2 processed with the non linear registration.

  To demonstrate the substantial equivalence in image quality of StentViz and Sten-tOp, we ran a paired T-Test with the following hypotheses:• H 0 : average of StentViz scores = average of StentOp scores.• H 1 : average of StentViz scores > average of StentOp scores.The hypothesis H 0 has been rejected by the T-Test (p value < 0.001) for each observer.

Figure 2 .

 2 Figure 2.31 depicts the histogram of the difference of image quality scores (StentViz score -StentOp score). H 0 is represented by the blue dot and a 95% confidence interval for the difference of the scores is represented in red. According to this result we can state that in average the StentViz scores are superior to the StentOp scores and that this difference is statistically significant.

Figure 2 .

 2 Figure 2.31: Histogram of StentViz image score -StentOp Image score; Hypothesis H 0 is represented by the blue dot. 95% confidence interval for the difference of scores is represented in red (rated by: Left reader 1, center reader 2 and right reader 3).

Figure 2 . 32 :

 232 Figure 2.32: Two examples ((a) and (b)) and the images produced by StentViz ((c) and (d)) and StentOp ((e) and (f)). Note that with StentViz the details of the stent are more visible.

  registration. Because the patent only provides a description and no result or evaluation of the technique, comparison is limited. In a separate patent[START_REF] Mory | Multi-feature time filtering for enhancing structures in noisy images[END_REF] dedicated to guidewire tip tracking and enhancing they describe the segmentation of a guide-wire and its use for image registration. However, they do not specify the registration technique nor present result. They also published on the use of maker-ball detection and tracking for 3D stent reconstruction and compared it to IVUS [SFL + 09b]. In this publication they briefly mention a marker-ball detection and tracking algorithm that relies on the temporal smoothness of the marker motion (as in the technique that we exposed in 2.3.3.1), but their main focus is the validation of the technique. The third team[START_REF] Kaufhold | Methods and appartus for visualizing low contrast moveable objects[END_REF] from GE Healthcare describes a method to detect and track the markerballs and register them with a linear transform. Their approach emphasises on the use of correlation with a marker template to detect and track them. The fourth team [ZHB + 08]d o e s not describe much the detection and tracking part but state that they use the classical linear transform for registration, a specific contrast enhancement based on the image histogram and a blur reduction filtering. Moreover, they restrict averaging only to the frames in a similar cardiac cycle phase, probably to enhance the sharpness of the DSE image. Finally, two other commercially available DSE products exist, one from Siemens called IC stent and one from Paieon called StentOp. Comparisons from an algorithmic standpoint were not possible as the technical details are not publicly available. 2.5.2.2 Comparison of the improvement in image quality Two previous articles [Koo05, OSB + 08] have evaluated the potential of DSE from an image quality improvement standpoint. The different teams had clinicians perform an assessment on a database of cine image sequences with the objective of comparing the images before and after enhancement. Formally, the individual clinicians were asked to rate each image according to a given scale, however the scales differ from one study to the other. Koolen [Koo05] used a 5-level scale defined by: (1) not visible, (2) poorly visible, (3) visible, (4) well visible, (5) crystal clear. Ohanessian [OSB + 08] used a 4level-scale defined as: (1) poor, (2) average, (3) good, (4) excellent.

As a consequence of

  the growing interest of clinicians for DSE, several studies have been conducted [MVP + 07, Koo05, CSMS05, KJY + 05, OSB + 08, CAC + 09, Cho10, FGBV09, MSB + 10] that demonstrated that DSE is bringing a significant improvement in image quality and that it is deemed useful in clinical practice in a large proportion of cases (≈ 70%). DSE can help evaluate the deployment of the stent and detect some underdeployments or non optimally treated lesions. In such cases, clinicians can post-dilate the stents to improve their expansion. The rate of stent post-dilation using DSE ranges from 30% to 70% depending on the study. Further studies are needed to better understand the role and the impact of DSE on clinical practice, for instance comparing post-dilatation rates with and without DSE. Only one study[START_REF] Cheol | Tct-375: Impact of stentboost enhancement guided percutaneous coronary intervention on midterm angiographic and clinical outcomes[END_REF] investigated the impact of DSE on the main clinical endpoints such as the occurence of major adverse cardiac events and target lesion re-vascularisation. Based on a two arm set up involving nearly 900 patients, they demonstrated significant improvement of the clinical endpoints at mid-term follow-up. Moreover, various teams [Koo05, CSMS05, KJY + 05, MVP + 07, CAC+ 09]

Fig 2 .

 2 33) shows a deployed stent and a calcification. The harder plaque structure prevents the stent from optimally deploying and fully treating the lesion.

Figure 2 .

 2 Figure 2.33: DSE image: Observe the plaque indicated by the arrow that prevents the proper deployment of the stent.

Figure 2 . 34 :

 234 Figure 2.34: Use of DSE to optimize stent overlapping.

Figure 2 . 35 :

 235 Figure 2.35: Use of DSE for a bifurcation treatment procedure. Top: bifurcation before treatment presenting significant stenoses. Center row: a first stent is deployed / a second stent is positioned next to it / both stent expanding (note the overlapping) / stent shape is further modified by balloon inflation in the side branch. Bottom: Final angiographic result of the treated bifurcation.

Figure 2 . 36 :

 236 Figure 2.36: Use of DSE to detect stent fracture. Left: a coronary aneurysm is indicated by the arrow. Center: DSE enables to see that the aneurysm is linked with the stent rupture indicated by the arrow. Right: after treatment.

Figure 2 . 37 :

 237 Figure 2.37: Illustration of the variability of the appearance due to strut superimpositions patterns. (a) and (b) depict a same stent under two viewpoints differing from few degrees.

Figure 2 . 38 :

 238 Figure 2.38: Illustration of imperfect registration in some cases (see text for details). (a) Although the landmarks are well registered and sharp, the stent struts do not appear and the upper part of the stent is blurry. (b) Case of two stents at a bifurcation. Only the marker-balls and the guide-wire supporting them are used as registration landmarks.Therefore, the stent in the side branch is not registered as accurately as the one in the main branch and is blurrier.

Figure 3 . 1 :

 31 Figure 3.1: (a) input image. (b) output image of StentViz "guide-wire subtracted", top regular DSE image, bottom guide-wire subtracted.

Figure 3 . 2 :

 32 Figure 3.2: Scheme illustrating the difficulties in stent visualization introduced by the presence of the guide-wire. Top: the guide-wire hides the structure of the stent struts; Middle: the guide-wire hides partially the border of the stent; Bottom: ideal case for stent visualization where the guide-wire is not displayed (images are adapted from a Cypher stent photo [tim05]).

Figure 3 . 3 :

 33 Figure 3.3: Stent visualization difficulties in clinical DSE images. Left: the guidewire hides the structure of the stent struts; Right: the guide-wire hides partially the border of the stent.

1 )

 1 An image formed with an Xray source is thus naturally transparent. Such images where one observes the transmitted light are often opposed to visible light photographs, where one observes reflected light and where objects usually occlude one another. Transparent images are often modeled as superimpositions of layers [CAW02, ABL09, SI04, SI05, SABM04, TOM00, WA96, BBHP92, IRP94, SM91, ZLP+ 09]. In this simplified model, a layer is a plan on which each point is associated with an attenuation. The layers are usually represented without loss of generality as parallel plans (see Fig.3.4).

Figure 3 . 4 :

 34 Figure 3.4: Illustration of the continuous (volumetric) Xray image formation model (left) and the discrete planar layer model (right).

Figure 3 . 5 :

 35 Figure 3.5: Planar layer modeling of a DSE image: 3 separate layers, namely the anatomical background, the guide-wire and the stent, are combined in the image formation mechanism.

Figure 3 . 6 :

 36 Figure 3.6: Background subtraction in DSE images. Left: motion compensated integration of the images. Right same as left performed on background subtracted images.

Figure 3 . 7 :Figure 3 . 8 :

 3738 Figure 3.7: Anatomy of a coronary guide-wire illustrating its main components: the core, the cover and the tip (Figure reproduced from [ENS + 10]).

Figure 3 . 9 :

 39 Figure 3.9: From left to right: DSE image, guide-wire subtracted image, estimated guide-wire layer, curve of the intensities of the pixels on the guide-wire in the DSE image. Observe on the curve all the variations induced by the stent signal as a consequence of the transparency of X-ray images.

Figure 3 . 10 :

 310 Figure 3.10: From left to right: input image, estimated guide-wire layer, guide-wire subtracted image.

Figure 3 . 11 :

 311 Figure 3.11: From left to right: regular DSE image, guide-wire subtracted DSE image, both downscanned to fit the display, both cropped on the area of interest to fit the display.

Figure 3 . 12 :

 312 Figure 3.12: Simultaneous display of two DSE image with/without guide-wire subtraction in the case of a diagonal stent. The area of interest is represented by the union of the three squares in the upper part.

Figure 3 . 13 :

 313 Figure 3.13: Attenuation profiles of 10 guide-wires in clinical cases estimated with the average (left) and the median (right). Abscissa: distance to the guide-wire centerline in pixels. Ordinate: attenuation factor (no dimension). The average profile with both methods is plotted with a dashed line.

Figure 3 . 14 :

 314 Figure 3.14: Guide-wire subtraction results: left average, right median. Observe on the image on the left the white line (artifact) at the center of the stent.

Figure 3 .

 3 Figure 3.15: (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction.

Figure 3 .

 3 Figure 3.16: (a) input image. (b) guide-wire subtracted image.The guide-wire subtraction is satisfactory but not perfect. We can observe in the upper section of the stent a residual guide-wire signal. Our hypothesis to explain it is that the guidewire centerline estimation is less reliable in this area where the stent border and the guide-wire are very close one to another.

Figure 3 .

 3 Figure 3.17: (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction. The stent-signal is rather weak compared to the intensity of the guide-wire, therefore subtraction improves one's ability to assess the general shape of the stent.

Figure 3 .

 3 Figure 3.18: (a) input image. (b) guide-wire subtracted image. The subtraction is not perfect in the lowest part of the stent where one can notice an unusually white signal. However, on the upper part of the stent, the subtraction drives the attention of the reader on a dark area. Its presence is also visible (but far less conspicuous) in the non-subtracted image. This area is likely to be a large calcification that can have impacted stent deployment in a plane perpendicular to the one of the image. Such a finding can encourage the cardiologist to repeat a StentViz acquisition with a different viewing angle.

Figure 3 .

 3 Figure 3.19: (a) input image. (b) guide-wire subtracted image. The subtraction proved to be efficient in this stent in stent situation (two stents are superimposed in the lowest part). StentViz enables to understand the relative positioning of the two stents.

Figure 3 .

 3 Figure 3.20: (a) input image. (b) guide-wire subtracted image. Perfect subtraction example.

Figure 3 .

 3 Figure 3.21: (a) input image. (b) guide-wire subtracted image. Excellent guide-wire subtraction.

Figure 3 .

 3 Figure 3.22: (a) input image. (b) guide-wire subtracted image. Excellent guide-wire subtraction.

Figure 3 .

 3 Figure 3.23: (a) input image. (b) guide-wire subtracted image. Interesting case where the guide-wire is constantly at the same distance to the stent border. Thanks to the median estimator in the estimation of the attenuation profile the processing is robust to such situations.

Figure 3 .

 3 Figure 3.24: (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction.

Figure 3 .

 3 Figure 3.25: (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction.

Figure 3 .

 3 Figure 3.26: (a) input image. (b) guide-wire subtracted image. Perfect guide-wire subtraction.

Figure 3 .

 3 Figure 3.27: This case is of particular clinical interest. The guide-wire subtraction (on the right) reveals the border of the stent that is not straight, as indicated by the arrow. This finding was not obvious in the regular DSE image (left).

Figure 3 .

 3 Figure 3.28: (From left to right: Regular contrast setting (no saturation); Aggressive contrast setting allows to improve the display of the stent but saturate the guide-wire; With guide-wire subtraction this contrast setting does not create saturation in the stent area.

Figure 4 . 1 :

 41 Figure 4.1: 3D coronary stent reconstruction at a bifurcation.

Figure 4 . 2 :

 42 Figure 4.2: Illustration of a locally under-deployed stent in a pig artery. In image (a) the under-deployment circled in blue is visible. In image (b), under a different viewing angle the defect is hardly noticeable (images from [Per08]).

Figure 4 .

 4 Figure 4.3: (a) A frame of the input sequence. (b) Visualization of the stent reconstruction with the method of Perrenot [Per08]. (c) Same stent reconstructed with a CT scan. Images extracted from [Per08].

Sections 4 .

 4 3.4 and 4.3.3. Results on a database of 22 cases are reported (Section 4.4)

Figure 4 . 4 :

 44 Figure 4.4: Five images extracted from a rotational acquisition. Note the changes in balloon appearance and marker position. In the second image, one of the markers is overlapping the tip of the catheter, making it hardly visible. In the third image sternal wires appear, and in the fourth the markers overlap the guide-wire tip.

  Given the similarities of the proposed problem with DSE, it is natural to evaluate the performance of the DSE detection and tracking scheme exposed in Chapter 2 on the spin datasets. We measure it in terms of True Positive (TP) -the percentage of frames where both markers have been correctly detected -False Positive (FP) -where a false pair is detected instead of the actual markers -and False Negative (FN) -where no pair is detected. There are no True Negative (TN) since the markers are present in every frame of the sequences. Therefore the relation FN + TP + FP = 1 holds. The results on 3 patients, are reported in

Figure 4 . 5 :

 45 Figure 4.5: General overview of the marker tracking algorithm.

  among the catalog in DSE. It combines the number of frames of the track, the average absorption of the candidate markers, and the average correlation of the candidate markers. The novelty score is the percentage of missing frames that would be filled by performing the fusion. The track continuity score, a more technical matter, is defined hereafter. Track continuity score Let us call A = {a i ,i ∈ I A } and B = {b i ,i ∈ I B } the two tracks considered for merging, where a i and b i are the pairs detected in the frames indexed in I A,B ⊂{ 1, 2,...,n},a n dn is the number of frames of the sequence. We do not consider the merging of tracks if one is included in the other one (I A ⊆ I B or I B ⊆ I A ). We transform the problem of merging tracks into the one of merging non overlapping tracks (see Fig. 4.6). To this end, let us consider the following reduced tracks: A r = {a i ,i ∈ I A \ (I B ∩ I A )} and B r = {b i ,i ∈ I B \ (I B ∩ I A )}. We forced the merged track M (A, B)t ob ee i t h e rM (A r ,B)={a i ,i ∈ I Ar }∪{ b i ,i ∈ I B } or M (B r ,A)={a i ,i ∈ I A }∪{b i ,i ∈ I Br } (i.e. the merge of two non overlapping tracks).

Figure 4 . 6 :

 46 Figure 4.6: Merging two potentially overlapping tracks A and B is reduced to merging non overlapping ones by assigning all the common indexes to either one or the other.

Figure 4 . 7 :

 47 Figure 4.7: Two non overlapping tracks C and D are represented. The merging point couples (ξ(C, D) in the text) are represented with a wider black border.

Fig. 4 .

 4 Fig. 4.7 illustrates these points. For each merging point (c i ,d j ) ∈ ξ(C, D) we define a local continuity score ω(c i ,d j ) that is a function of the following parameters:

  the pairing criteria are refined based on the known position of the markers in the past and future frames. It allows detecting marker pairs that may have been lost in the first stages of the algorithm or where FP have been rejected. The refinement procedure is iterated until convergence or until a maximum number of iterations is reached. FP and FN reduction techniques are presented thoroughly hereafter. False positive reduction Fig. 4.8 illustrates the evolution of the length between the candidate markers in a track. We can observe peaks in the interval of frames [150, 155] and [58, 160] that correspond to false positives in the frames 152, 153 and 159.This suggests that abnormal variations in the evolution of the parameters describing the markers can be used to detect false positives. Therefore, for every description parameter p (length, angle and position) we define a measure at each frame δ(p)[i]. We compute a smoothed version of this measure by local averaging on a window of a few

Figure 4 . 8 :

 48 Figure 4.8: Plot of the length of the detected marker segment versus the frame index.False positives are circled in green.

Figure 4 .

 4 Figure 4.9: (a) et (b): Frames 158 and 160 of a clinical sequence. The actual markers have been detected at the locations indicated in green. However, in the intermediate frame (number 159) they have not been detected. (c) The set of detected pairs in frame 159. The actual marker pair does not belong to them. (d) The ROI for pairing and the new set of pairs in frame 159, based on the detected markers in the previous and next frames. (e) Extract from (c) where we can observe that the actual markers did not belong to the set of detected pairs.

Figure 4 .

 4 Figure 4.10: Top: Example of wrong marker labeling. Bottom: A typical case where marker labeling is a difficult case because the markers invert their relative positions along the sequence.

  define the average position, p as: p =argmin p∈R 3 D∈E d d(p, D) 2 (4.9) where d is the Euclidean distance function. It is illustrated on Fig. 4.11.

Figure 4 .

 4 Figure 4.11: 3D reconstruction of the center point from 3 detections.

Figure 4 .

 4 Figure 4.13: Projection of the rough 3D model on the image, translation of the projected segment and labeling of the detected marker couple (in green).

Figure 4 . 14 :

 414 Figure 4.14: 3 images of a spin sequence. Top row: original image. Central row: segmented guide-wire. Bottom row: subtracted guide-wire.

Figure 4 .

 4 Figure 4.15: A situation where affine registration is not optimal. Between images (a) and (b) we assume that the marker segment has undergone a rotation out of the image plane, around the (Ox) axis. We illustrate in red the marker segment of image (a). Note the change in the marker segment length between figures (a) and (b). The change in distance between the markers in images (a) and (b) is compensated by a global scaling with the similarity transform that modifies the (nearly unchanged) diameter of the stent (image (c)). In image (d) a stretching along the axis of the markers but not perpendicularly keeps unchanged the stent diameter while registering the markers. In these two last images the registered markers are illustrated in green.

Figure 4 .

 4 Figure 4.16: Motion compensated images. Left and center: Two registered images in a phase where the gantry is static. Right: Registration of the manually segmented stents. Top row state of the art similarity transform, bottom row linear diameter preservation registration. Observe that the registered stents match better with the proposed registration than with the classical affine one (as indicated by the arrows).

Figure 4 .

 4 Figure 4.17: Illustration of the non-linear registration and of the guide-wire subtraction on three images taken at different instants during a rotational acquisition. We represent the segmented guide-wire in green, and the projected 3D guide-wire model in red. Top row: original images. Bottom row: registered and guide-wire subtracted images. Left: We can observe the discontinuity of the guide-wire based registration far from the segmented guide-segment (notice the "broken guide-wire effect"). Middle: the projected and detected guide-wires occasionally match very closely, typically once per heart beat, as in this example. Right: notice the difference in curvature between the projected and detected guide-wires.

Figure 4 .

 4 Figure 4.18: Automated marker detection and labeling on sequence 3.

Figure 4 .

 4 Figure 4.19: Left: 3D stent model reconstructed from sequence 3. Right: 3D stent of sequence 6 (bifurcation case)

Figure 4 .

 4 Figure 4.20: 3D stent reconstructions from left to right: sequence 2, 3a and 1a.

Figure 4 .

 4 Figure 4.21: Left longitudinal slice / Right axial slice of the reconstructed stent (image from [Per08]).

Figure 4 .

 4 Figure 4.22: 3D stent slice: Left classical processing, right guide-wire subtracted between the markers. The stent border hidden by the guide-wire on the left is visible on the right, as indicated by the white arrows. The guide-wire subtraction process attenuates the guide-wire signal, but in the 3D volume a mark still persists.

Figure 4 .

 4 Figure 4.23: Left: state of the art. The transform to register the markers is a similarity and the guide-wire is not subtracted; center: radius preserving affine registration and guide-wire subtraction; right: non-linear registration and guide-wire subtraction.The three rows illustrate different viewing angles of the same stent. Observe on top right that the strut pattern appears in the upper side of the stent. This pattern is not visible on the left image. On the bottom right the general shape of the stent can be easily assessed (this it is not the case on the left).

Figure 4 . 1

 41 Figure 4.24: Comparison of the similarity transform (right) and of the non-linear one (left), in the slices of a reconstructed stent volume (same example as Fig. 4.23.Guide-wire has been subtracted in both cases.

Figure 4 .

 4 Figure 4.25: Stability of the estimation of the parameters of the 2D registration versus the marker segment length. Left: inverse of the marker segment length (in pixels) vs the frame index. Right: estimated rotation angle in radians vs the frame index.

Figure 4 . 26 :

 426 Figure 4.26: Volume rendering of a same stent, with (left) and without (right) balloon inflation.Observe that the inflation of the balloon is (i) beneficial to the quality of the enhanced stent and that (ii) prevents the guide-wire from overlapping with the stent border. This illustration case is the one where the impact of balloon inflation is the most striking in our database.

  tion of the curvilinear structures propagates the information by selecting the relevant neighbors [LBL + 09, PWBB97]. It is very often expressed in a shortest path formalism where the feature map is used as a potential [WZL + 07, BLHS09]. In case when the feature map contains orientation and contrast information, both can be embedded in the potential [OG10, HTD05, MJS + 04]. In the more restricted number of applications where a set of images are segmented successively, this last step can be performed by snake spline tracking [BVN03, SKUF07, HGG + 09].

Figure 5 . 1 :

 51 Figure 5.1: Confusion matrix

  is the characterization of a classifier by the couple (TPR, FPR). It is usually represented in a two axis graph (see Fig.5.2). Several points are of particular interest in this space : The point (0, 0) illustrates an extremely conservative classifier that never outputs any positives and (1, 1) an extremely liberal one that always outputs positives. The point (0, 1) corresponds to the ideal classifier that never commits any classification error. Generally speaking a point in ROC space is better than another if it is to the northwest (TPR is higher, FPR is lower) of the first. On Fig. 5.2,p o i n tC ' thus represent a better classifier than A. The points that lie on the y = x diagonal line are random choice classifiers (plotted with a dashed red line on Fig. 5.2). They have no information about the class. The points below the y = x line represents classifiers that perform worse than random guessing. This triangle is therefore usually empty in ROC graphs. In such a case, simply negating the classifier (inverting its classification decisions) turns it into relevant one. The ROC characterization of a classifier has the important property of being insensitive to a change in class distribution: no matter if a given class is more represented than the other in the dataset, the ROC point of a classifier stays the same 3 . This is important for our application where we have far more negatives than positives in an image.

Figure 5 . 2 :

 52 Figure 5.2: ROC space (image from [Ind09]). Point B illustrate a random choice classifier. C' is a better classifier than A. C is the negation of C'.

Figure 5 . 3 :

 53 Figure 5.3: ROC curve illustration (image from [Ind09]).

  different from one author to another in the case of curvilinear structures. In accordance to[START_REF] Zwiggelaar | Linear structures in mammographic images: detection and classification[END_REF][START_REF] Honnorat | Guide-wire extraction through perceptual organization of local segments in fluoroscopic images[END_REF][START_REF] Honnorat | Robust guidewire segmentation through boosting, clustering and linear programming[END_REF][START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF] we propose to define a ground truth T on each image (annotated by a operator) that is a one pixel thin line. It is the representation of the centerline, or backbone, of the structure. We denote by D the set of points detected in an image. In order to take into account the real width of the curvilinear structure, we define the true positive as the pixels of T that lie closer to D than a pre-defined distance d,w h e r ed is typically the radius (width) of the curvilinear structure. It can be simply computed by |T ∩ δ d (D)| where δ d (A) is the morphological dilation of A by a ball structuring element of radius d.L e t|E| denote the cardinal of set E.T P Ri st h e n defined by: TP = |T ∩ δ d (defined as the detected pixels that lie further from T than a distance d. Denoting A c the complementary of the set A in the image, the FPR rate is computed by: FP = |δ d (T ) c ∩D| (5.8) FPR = |δ d (T ) c ∩D| |δ d (T ) c | (5.9) These definitions allow us to compute ROC curves and partial AUC for any line enhancement technique. Moreover they allow us to compute the Missed Detection Rate (MDR) and False Detection Rate (FDR) defined in [BAG + 07, HVP10a, HVP10b]. For sake of completeness, we express these quantities with the previously introduced nota-

Figure 5 . 4 :

 54 Figure 5.4: Illustration of the computation of TP, FP, TN and FN. Top row: original image, ground truth and dilated ground truth. Bottom row, ROI, output of our line enhancement technique and threshold and skeletonization of this output.

1 .

 1 The Rotated Line Templates (RLT) techniques outperform other detectors in 3 of the 5 studies [BVG09, Tan10, ZABT04]. In one of them [Tan10] the line template is expressed in the morphological framework and in the two other ones in the linear filtering one [BVG09, ZABT04].

Figure 5 . 5 :

 55 Figure 5.5: X-ray fluoroscopy image. A guide-wire is illustrated. Note that it is a long smooth curve, with low contrast to noise ratio.

  2 and 5.4.3. An efficient algorithm to compute it is described in Section 5.4.4. We define several operators on P dedicated to curvilinear structures in Sections 5.4.5, 5.4.6 and 5.4.7. Section 5.4.8 deals with the theoretical links with existing techniques. Quantitative results based on the ROC formalism and comparison to other techniques are presented in Section 5.5.

Figure 5 . 6 :

 56 Figure 5.6: Illustration of the definition of the paths by Vincent. The center pixel,where the path originates, is p. l i st h el e n g t ho ft h ep a t h ,θ i its orientation, and the angular range δθ the straightness. The search cone in which paths are constrained to be located is shaded on the figure.

Figure 5 . 7 :

 57 Figure 5.7: Illustration of the recursivity of the cone constraint. A path originating from a pixel p shall stay in the cone placed in any of its pixels p ′ . The path of (a) verifies this property illustrated in (b). The path of (c) does not verify this property (see (d)) and will thus not be considered by the technique.

Figure 5 . 8 :

 58 Figure 5.8: Triangular search cones defined by Vincent. These four cones of straigthness π/2 cover the whole angular range.

Figure 5 . 9 :

 59 Figure 5.9: Left a curvilinear structure in a very noisy environment. Right, minimal path computed between the top and the bottom of the image (illustration from [Vin98]). It is extremely tortuous, and does not follow the smooth curves that are naturally present in medical images.

  3.1 and the length defines the smoothness of the paths to analyze. With one single segment in the polygon we compute the equivalent of what we denoted the local processing. With a few segments a semi-local processing similar to those that tend to re-inforce aligned responses of the local processing. With a large number of segments (typically ten) the procedure builds paths of length similar to the one obtained with a grouping or a tracking technique applied to a local processing.

Figure 5 .

 5 Figure 5.10: 500 paths originating at random locations are illustrated. We can observe how they all tend to converge to the linear structures of the image and especially to the guide-wire.

Figure 5 .

 5 Figure 5.11: Extract of the top image. Observe the density of paths on the guide-wire.

Figure 5 . 12 :

 512 Figure 5.12: Here we built a test image with a perfect circle. We illustrated again the content of the polygonal path image at 500 random locations. The behavior is similar to the one observed on the guide-wire image.

Figure 5 .

 5 Figure 5.13: We illustrated 5000 paths originating at random locations. We can observe on the line that is similar to the medial axis of the curvilinear structure for our problem, that the paths are attracted by different equidistant parts of the guide-wire.We approximately represented this line in black on the figure.

Figure 5 . 14 :Algorithm 1

 5141 Figure 5.14: All the paths intersecting at one given point. This particular point belongs to the guide-wire.

Figure 5 .

 5 Figure 5.15: Illustration of the notations for the computation of P. Let the center pixel be of coordinates (i, j). In the image I θ k we store the sum of the pixels along line segments of orientation θ k . Such a line segment is illustrated on the figure with plain lines. Translation parameters (t x k ,t y k ) are also stored. A search cone is defined by a start angle cone.start and an end angle cone.end. All the possible locations of the end of the segments in a given search cone are illustrated by the arc of circle in dashed line. These are the locations of the pixels that will be evaluated to extend the path in the successive iterations.

5. 4 . 5

 45 Curvilinear structure enhancement techniques derived from the polygonal path image 5.4.5.1 The cost image

Figure 5 . 17 :

 517 Figure 5.17: We illustrated 3 typical paths of 2 segments that have been considered by the algorithm.

Figure 5 .

 5 Figure 5.18: On a synthetic image representing a circle we have computed P and associated to each pixel the cost of the path originating from it. We can observe that the image is complex and that linear structures tend to extend to neighbor pixels.

Figure 5 .

 5 Figure 5.19: We have computed P on the clinical from Fig. 5.5 a n da s s o c i a t e dt o each pixel the cost of the path originating from it.We can observe that the image is complex and that linear structures tend to extend to neighbor pixels.

Figure 5 .

 5 Figure 5.20: Path voting on the image illustrated on Fig. 5.5. See section 5.5.3 for details on the pre-processing.

Figure 5 .

 5 Figure 5.21: A more aggressive contrast setting (saturation) of fig 5.20 shows lower values of the image. We see some path that are attracted by the guide-wire. Especially close to the tip.

Figure 5 . 22 :

 522 Figure 5.22: Even more aggressive contrast setting of image fig 5.20 enables to see its complex structure.

Figure 5 .Figure 5 .

 55 Figure 5.23: Similar image as fig 5.20 except that constrained path smoothness, rejecting any path of tortuosity lower than 0.6

Figure 5 . 25 :

 525 Figure 5.25: Even more agressive contrast setting of image fig 5.20 enables to see its complex structure. Compared to fig 5.22 we see that the most tortuous path have been removed.

Figure 5 .

 5 Figure 5.26: ϑ(P) with 3 pixel long polygonal segments (top) and 11 pixel long segments (bottom) for a similar total path length. In the left column (nominal windowing) we observe that the curvilinear structure appear tortuous with short path segments and smooth with longer segments (as in the original image).

Figure 5 .

 5 Figure 5.27: We illustrate here the result of path pruning with x = 50%. We can observe that among the small number of paths selected, the ones illustrating the guide-wire are present. Further path selection, based on their cost for instance can be performed to better isolate the guide-wire.

A

  and B, by finding a geodesic for the following weighted distance: d(A, B)=min y L 0 (w + I(y(s))ds (5.22) where s is the arclength and L is the length of the curve. The minimum is considered over all curves y(s) traced on the image domain that link the two end points, that is, y(0) = A and y(L)=B.T h ec o n s t a n tw imposes regularity on the curve. I>0i s a potential cost function computed from the image, that takes lower values near linear features. The obtained path is geodesic meaning that d is actually a distance in the mathematical sense of the term. It verifies the following set of properties: ∀(x, y) d(x, y) ≥ 0 (5.23) ∀(x, y) d(x, y)=0 ⇔ x = y (5.24) ∀(x, y) d(x, y)=d(y, x) (5.25) ∀(x, y, z) d(x, y) ≤ d(x, z)+d(z, y) (5.26)

Figure 5 .

 5 Figure 5.30: Counter example to the triangular inequality when path curvature is bounded. The "distance" between two points is defined as the minimal cost of all the paths joining two points, under the constraint that the maximum curvature of the paths shall not exceed a given bound. We build a particular potential cost image for this counter example, where: all the image has cost +∞ except the three paths that are drawn. Let L AB be the length of the path from A to B. We assign to each pixel on this path the cost 3/L AB . Consequently the cost of the whole path is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB . The cost of each of these two paths is thus 1. Then, we note that the only finite cost path from A to B, is the one that is drawn (see Fig. (c)). Indeed, the only other finite cost path is the one going though C, but it does not verify the curvature bound constraint. Therefore d(A, B) = 3. Similarly d(A, C)=d(C, B)=1 . Finally: d(A, B) >d(A, C)+d(C, B).

  Figure 5.30: Counter example to the triangular inequality when path curvature is bounded. The "distance" between two points is defined as the minimal cost of all the paths joining two points, under the constraint that the maximum curvature of the paths shall not exceed a given bound. We build a particular potential cost image for this counter example, where: all the image has cost +∞ except the three paths that are drawn. Let L AB be the length of the path from A to B. We assign to each pixel on this path the cost 3/L AB . Consequently the cost of the whole path is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB . The cost of each of these two paths is thus 1. Then, we note that the only finite cost path from A to B, is the one that is drawn (see Fig. (c)). Indeed, the only other finite cost path is the one going though C, but it does not verify the curvature bound constraint. Therefore d(A, B) = 3. Similarly d(A, C)=d(C, B)=1 . Finally: d(A, B) >d(A, C)+d(C, B).

Figure 5 .λ

 5 Figure 5.31: The cone distance.

5. 4 . 8 . 2

 482 Geodesic votingGeodesic voting has recently been introduced by Rouchdy and Cohen in [RC08, RC09, RC11b, RC11a] to segment tree structures in medical images. While minimal paths are popular techniques to extract a structure between two end points, they are not easily applied with a high level of automation. The geodesic voting has been proposed as a technique to improve the automation by only requiring a starting point but no end

Figure 5 . 32 :

 532 Figure 5.32: Counter example for the triangular inequality on λ. We consider the 4 cones used by Vincent [Vin98] that we group in two pairs of opposite cones, illustrated on (a) and (b). We build a particular potential cost image (b) where: all the image has cost ∞ except the three paths that are drawn. Let L AB be the length of the p a t hf r o mAt oB ,w ea s s i g nt oe a c hp i x e lo nt h i sp a t ht h ec o s t3 /L AB . Consequently the whole path cost is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB . The cost of each of these two paths is thus 1. Then we note that the only finite cost path from A to B is the one that is drawn that is included in cone (a) (see Fig. (c)). Therefore λ(A, B) = 3. Similarly λ(A, C) = 1. The only finite cost path from C to B is the one that is drawn, and it is in the cone (b) (see Fig. (d)). Consequently λ(C, B)=1 . Finally: λ(A, B) >λ(A, C)+λ(C, B).

  Figure 5.32: Counter example for the triangular inequality on λ. We consider the 4 cones used by Vincent [Vin98] that we group in two pairs of opposite cones, illustrated on (a) and (b). We build a particular potential cost image (b) where: all the image has cost ∞ except the three paths that are drawn. Let L AB be the length of the p a t hf r o mAt oB ,w ea s s i g nt oe a c hp i x e lo nt h i sp a t ht h ec o s t3 /L AB . Consequently the whole path cost is 3. Similarly we assign to the pixels on the path from A to C the cost 1/L AC and to those on the path from C to B the cost 1/L CB . The cost of each of these two paths is thus 1. Then we note that the only finite cost path from A to B is the one that is drawn that is included in cone (a) (see Fig. (c)). Therefore λ(A, B) = 3. Similarly λ(A, C) = 1. The only finite cost path from C to B is the one that is drawn, and it is in the cone (b) (see Fig. (d)). Consequently λ(C, B)=1 . Finally: λ(A, B) >λ(A, C)+λ(C, B).

Figure 5 . 33 :

 533 Figure 5.33: Illustrations of R A,B , for several configuration of A and B with the set of four non-overlapping cones presented in Fig 5.8. In this case R A,B is the inter-visibility parallelogram.

Figure 5 . 34 :

 534 Figure 5.34: Images extracted from [BC09]

Figure 5 . 35 :

 535 Figure 5.35: Application of the PSI to clinical examples.

Figure 5 . 36 :

 536 Figure 5.36: Application of the PSI to clinical examples.

Figure 5 . 37 :

 537 Figure 5.37: Application of the PSI to clinical examples.

Figure 5 . 38 :

 538 Figure 5.38: Application of the PSI to clinical examples.

Figure 5 .

 5 Figure 5.39: Illustration of the performance of the line enhancement techniques (measured by the partial AUC) on each sequence of the database. Top: FPR is computed on the whole image. Bottom: FPR is computed only in a band around the guide-wire.

Figure 5 . 40 :

 540 Figure 5.40: Average performance of four line enhancement techniques over our database of clinical cases. Top: FPR is computed on the whole image. Bottom: FPR is computed only in a band around the guide-wire.

Fig. 5 .

 5 41 displays the evolution of MDR, FDR and their sum as function of the threshold on three different sequences. We illustrate the thresholded images obtained with the four methods in Fig. 5.42, 5.43, 5.44 and 5.46. The outcomes are well aligned with the conclusions drove from the partial AUC: P based methods perform significantly better than the other ones. The smoothness constraints in ϑ τ min (P) removes some anatomical false alarms that yield tortuous paths, and RLT is superior to Frangi's vesselness.

Figure 5 .

 5 Figure 5.41: MDR (blue), FDR (red) and MDR+FDR (green) as a function of the threshold in three different clinical cases. As expected, MDR increases, FDR decreases and their sum has a clear minimum. In this experiment we chose 500 thresholds regularly sampled between the max and the min of the image.

Figure 5 .

 5 Figure 5.42: Top: input image. Middle row: Frangi (left) and RLT (right). Bottom row: ϑ(P)( l e f t )a n dϑ τmin (P) (right). Observe that traditional methods (middle row) enhance a large amount of non relevant structures in the background. Moreover, they fail to enhance some parts of the guide-wire. These problems are not present with ϑ τmin (P).

Figure 5 . 43 :

 543 Figure 5.43: Similar experiment as Fig. 5.42 on another clinical case. This one is the most challenging case yielding the poorest results due to the presence of the ribs that are very visible under this viewing angle and of sternal wires (first sequence in Fig. 5.39). Same observations apply.

Figure 5 . 44 :

 544 Figure 5.44: Similar experiment as Fig. 5.42 on another clinical case. Same observations apply.

Figure 5 . 45 :

 545 Figure 5.45: Similar experiment as Fig. 5.42 on another clinical case. Same observations apply.

Figure 5 . 46 :

 546 Figure 5.46: Similar experiment as Fig. 5.42 on another clinical case. Same observations apply.

  This PhD thesis falls into the context of curing coronary heart disease with minimally invasive techniques. These procedures involve a clinician inserting interventional tools inside the patient's vasculature, under the monitoring of Xray fluoroscopy. The purpose of the intervention is to restore the blood flow in a narrowed coronary artery by delivering an endo-prosthesis, called a stent. The objective of the work presented in this thesis was to design, study and validate, image processing techniques to improve the visualization of stents with the Xray imaging system. To this aim, we studied the automated detection, tracking and registration of two closely related interventional tools: the balloon markerballs and the guide-wire. Moreover, our work on guide-wire detection led us to propose a new generic tool for the processing of curvilinear structures: the polygonal path image.

1997 1997 :

 1997 Baccalauréat S -Equivalent to English A-levels in pure maths and physics, Awarded with merit. Teaching 2009 -current ESIEE Paris Teaching Linear methods in image processing to Master students Skills Software languages C/C++, Matlab, shell, Latex Languages English and Spanish: fluent German, Portuguese and Hebrew: basic Misc 6 sigma green belt certification (since 2003 @ GE) > 15 patent applications > 10 times Master thesis tutor 2008 -current @ Ecole Centrale Paris: Brazilian Jiu Jitsu instructor

  Standard deviation of the estimators versus the number of images in the input sequence. Results obtained with one billion simulations. Observe the general decreased in n -1/2 predicted by the theory for the empirical mean, the trimmed means and the median. ................. 2.8 Application of the background subtraction to a clinical image. Left: Original. Right: Background subtracted. Observe that most of the structures have disappeared. ................................ 2.9 Simulated vs estimated noise on two clinical cases for the 9 estimators: red and purple are estimated, blue and green are simulated. The overall precision of our model is typically 10%. ................... 2.10 Result of the different estimators on a clinical case. Left column: result obtained with Xn (reference). Center: Result obtained with the considered estimator. Right: difference image. From top to bottom: X (0) ,

...................................... 2.7 X ([n/4]) , X ([n/2]) , X ([3n/4]) , X (n) , Tn,[ p

  5.1 Confusion matrix ................................1 5.2 ROC space (image from [Ind09]). Point B illustrate a random choice classifier. C' is a better classifier than A. C is the negation of C'. .....1 5.3 ROC curve illustration (image from [Ind09]). ................1 5.4 Illustration of the computation of TP, FP, TN and FN. Top row: original image, ground truth and dilated ground truth. Bottom row, ROI, output of our line enhancement technique and threshold and skeletonization of this output. ...................................1 5.5 X-ray fluoroscopy image. A guide-wire is illustrated. Note that it is a long smooth curve, with low contrast to noise ratio. ............1 5.6 Illustration of the definition of the paths by Vincent. The center pixel, 5.10 500 paths originating at random locations are illustrated. We can observe how they all tend to converge to the linear structures of the image and especially to the guide-wire. ..........................1 5.11 Extract of the top image.Observe the density of paths on the guide-wire. 154 5.12 Here we built a test image with a perfect circle. We illustrated again the content of the polygonal path image at 500 random locations. The behavior is similar to the one observed on the guide-wire image. ......1 5.13 We illustrated 5000 paths originating at random locations. We can observe on the line that is similar to the medial axis of the curvilinear structure for our problem, that the paths are attracted by different equidistant Illustration of the notations for the computation of P. Let the center pixel be of coordinates (i, j). In the image I θ k we store the sum of the pixels along line segments of orientation θ k . Such a line segment is illustrated on the figure with plain lines. Translation parameters (t x k ,t y k )a r ea l s o stored. A search cone is defined by a start angle cone.start and an end angle cone.end. A l lt h epo s s i b l el oc a t i o n so ft h ee n do ft h es e g m e n t si na given search cone are illustrated by the arc of circle in dashed line. These are the locations of the pixels that will be evaluated to extend the path in the successive iterations. ..........................1 5.16 At the second iteration of the algorithm, each pixel p i contains the minimal path originating from it of length l. In order to compute the minimal path of 2 segments (length 2l) originating from pixel p we consider each pixel p i and note that the minimal path originating from p and passing trough p i is simply the already computed path originating from p i to the which we add the line segment p i p. ......................1 5.17 We illustrated 3 typical paths of 2 segments that have been considered by the algorithm. .

where the path originates, is p. l i st h el e n g t ho ft h ep a t h ,θ i its orientation, and the angular range δθ the straightness. The search cone in which paths are constrained to be located is shaded on the figure. ........1 5.7 Illustration of the recursivity of the cone constraint. A path originating from a pixel p shall stay in the cone placed in any of its pixels p ′ .T h e path of (a) verifies this property illustrated in (b). The path of (c) does not verify this property (see (d)) and will thus not be considered by the technique. ....................................1 5.8 Triangular search cones defined by Vincent. These four cones of straigthness π/2 cover the whole angular range. ...................1 5.9 Left a curvilinear structure in a very noisy environment. Right, minimal path computed between the top and the bottom of the image (illustration from [Vin98]). It is extremely tortuous, and does not follow the smooth curves that are naturally present in medical images. ............1 parts of the guide-wire. We approximately represented this line in black on the figure. ..................................1 5.14 All the paths intersecting at one given point. This particular point belongs to the guide-wire. ................................1 5.15 ...............................1 5.18 On a synthetic image representing a circle we have computed P and associated to each pixel the cost of the path originating from it. We can observe that the image is complex and that linear structures tend to extend to neighbor pixels. ............................1 5.19 We have computed P on the clinical from

  the walls of arteries, in large part due to the accumulation of macrophage white blood cells and promoted by low-density lipoproteins (plasma proteins that carry cholesterol and triglycerides) without adequate removal of fats and cholesterol from the macrophages by functional high density lipoproteins (HDL). It is commonly referred to as a hardening or furring of the arteries. It is caused by the formation of multiple plaques within the arteries (from http://encyclopedia.thefreedictionary.com/Atherosclerosis). 3 balloon catheter a catheter whose tip has an inflatable balloon that holds the catheter in place or can dilate the lumen of a vessel, such as in angioplastic procedures (from Stent visualization enhancement in Xray image sequences xxxii restenosis literally means the reoccurrence of stenosis, a narrowing of a blood vessel, leading to restricted blood flow. Restenosis usually pertains to an artery or other large blood vessel that has become narrowed, received treatment to clear the blockage and subsequently become renarrowed. This is usually restenosis of an artery, or other blood vessel, or possibly a vessel within an organ. This term is common in vascular surgery, cardiac surgery, and angioplasty, all branches of medicine that frequently treat narrowing of blood vessels. 6 stem cell One of the human body's master cells, with the ability to grow into any one of the body's more than 200 cell types. All stem cells are unspecialized (undifferentiated) cells that are characteristically of the same family type (lineage).

It is a syndrome affecting arterial blood vessels, a chronic xxix Stent visualization enhancement in Xray image sequences xxx inflammatory response in http://medical-dictionary.thefreedictionary.com/Angioplasty,+balloon). 6

balloon markerballs the balloon catheter has metallic markers (either at the center or on either side of the balloon). This helps the cardiologist know the location of the otherwise "invisible" balloon (from http://www.heartsite.com/html/ptca. html). 16 bare metal stent a vascular stent without a coating (as used in drug-eluting stents). It is a mesh-like tube of thin wire. The first stents licenced for use in cardiac arteries were bare metal -often 316L stainless steel. More recent ('2nd generation') stents use cobalt chromium alloy (from http://en.wikipedia.org/wiki/Bare-metal_ stent). 9 catheterization lab or cathlab, the room where the catheterization procedure takes place. 9 chronic total occlusion (CTO) Although it is often impossible to know exactly when the occlusion occurred, a CTO is arbitrarily defined as a > 3 month old, total obstruction of a coronary artery (from http://heart.bmj.com/content/91/suppl_ 3/iii42.extract). 27 coronary angiography also called coronarography. The most accurate method (the gold standard) for evaluating and defining coronary artery disease (CAD). Coronary angiography is used to identify the exact location and severity of CAD. 8 coronary stent a tube placed in the coronary arteries that supply the heart, to keep the arteries open in the treatment of coronary heart disease. It is used in a procedure called percutaneous coronary intervention (PCI). Stents reduce chest pain and have been shown to improve survivability in the event of an acute myocardial infarction. Similar stents and procedures are used in non-coronary vessels e.g. in the legs in peripheral artery disease. 1 Stent visualization enhancement in Xray image sequences xxxi drug eluting stent (DES) a peripheral or coronary stent (a scaffold) placed into narrowed, diseased peripheral or coronary arteries that slowly releases a drug to block cell proliferation. This prevents fibrosis that, together with clots (thrombus), could otherwise block the stented artery, a process called restenosis. The stent is usually placed within the peripheral or coronary artery by an Interventional Cardiologist or Interventional Radiologist during an angioplasty procedure (from http://en.wikipedia.org/wiki/Drug-eluting_stent). 8

guide-wire a thin, usually flexible wire that can be inserted into a confined or tortuous space to act as a guide for subsequent insertion of a stiffer or bulkier instrument (from http://medical-dictionary.thefreedictionary.com/guidewire). 11 interventional cardiology is a branch of the medical specialty of cardiology that deals specifically with the catheter based treatment of structural heart diseases. This most commonly involves the insertion of a sheath into the femoral artery and cannulating the heart under X-ray visualization. The interventional cardiology procedure of primary angioplasty is now the gold standard of care for an acute myocardial infarction. It involves the deployment of stents and balloons, leaving no scars, which has given it the name "pin-hole surgery" (as opposed to "key-hole surgery") (from http://encyclopedia.thefreedictionary.com/ Interventional+cardiology). 1 ischemia (from Greek, ischaima; isch-root denoting a restriction or thinning or to make or grow thin/lean, haema blood) is a restriction in blood supply, generally due to factors in the blood vessels, with resultant damage or dysfunction of tissue.

It may also be spelled ischaemia. It also means local anemia in a given part of a body sometimes resulting from congestion (such as vasoconstriction, thrombosis or embolism (from http://encyclopedia.thefreedictionary.com/Ischemia).

4 myocardial infarction (MI) or acute myocardial infarction (AMI), commonly known

as a heart attack, is the interruption of blood supply to a part of the heart, causing heart cells to die. This is most commonly due to occlusion (blockage) of a coronary artery following the rupture of a vulnerable atherosclerotic plaque, which is an unstable collection of lipids (fatty acids) and white blood cells (especially macrophages) in the wall of an artery. The resulting ischemia (restriction in blood supply) and oxygen shortage, if left untreated for a sufficient period of time, can cause damage or death (infarction) of heart muscle tissue (myocardium). 1, 9 PCI Percutaneous Coronary Intervention. 6 They retain the ability to divide throughout life and give rise to cells that can become highly specialized and take the place of cells that die or are lost (from http://www.medterms.com/script/main/art.asp?articlekey=10597). 27 stenosis (plural: stenoses) is an abnormal narrowing in a blood vessel or other tubular organ or structure (from http://en.wikipedia.org/wiki/Stenosis). 1 stent In the technical vocabulary of medicine, a stent is an artificial 'tube' inserted into a natural passage/conduit in the body to prevent, or counteract, a diseaseinduced, localized flow constriction. The term may also refer to a tube used to temporarily hold such a natural conduit open to allow access for surgery (from http://en.wikipedia.org/wiki/Stent). 1

StentViz a stent enhancement visualization software (DSE) commercialized by GE. 17 thrombosis Thrombosis is the formation of a blood clot inside a blood vessel, obstructing the flow of blood through the circulatory system. When a blood vessel is injured, the body uses platelets and fibrin to form a blood clot to prevent blood loss. Alternatively, even when a blood vessel is not injured, blood clots may form in the body if the proper conditions present themselves. If the clotting is too severe and the clot breaks free, the traveling clot is now known as an embolus (from http://encyclopedia.thefreedictionary.com/Thrombosis). 6 thrombus A clot consisting of fibrin, platelets, red blood cells, and white blood cells that forms in a blood vessel or in a chamber of the heart and can obstruct blood flow. The rupture of atherosclerotic plaques can cause arterial thrombosis (the formation of thrombi), while tissue injury, decreased movement, oral contraceptives, prosthetic heart valves, and various metabolic disorders increase the risk for venous thrombosis. A thrombus in a coronary artery can cause a heart attack (from http://www.thefreedictionary.com/thrombus). 4

  Approximately 16,000,000 Americans over the age of 20 have CHD (7% of the population). The two main consequences of CHD are heart attack that affects 1,225,000 people per year and angina that affects 10,200,000 living people both in the

	United States.
	We are particularly interested here in the main cause of angina and heart attack:
	the atheromatous stenosis. This disease is also called atherosclerosis. It is the gradual
	buildup of cholesterol and fibrous tissue in plaques in the wall of coronary arteries typi-
	cally over decades (Fig. 1.3). Blood stream column irregularities visible on angiography
	(Fig. 1.4), an Xray technique that enables vessel visualization, reflect artery lumen nar-
	rowing as a result of decades of advancing atherosclerosis. When the narrowing is severe
	enough, it can have consequences on the blood supply of the depending heart territory.
	It typically results in a severe chest pain due to ischemia (a lack of blood, hence a lack

According to the World Health Organization

[START_REF]Cardiovascular diseases (cvds)[END_REF]

7.2 million people died from coronary artery disease in 2004 representing 12% of all deaths. Moreover it is the leading cause of death in developed countries. For instance, statistics for 2007 in the United

States [RGLJA11]

show that it is the single leading cause of death, representing one sixth of the deaths. of oxygen supply) of the heart muscle. It is called angina pectoris (commonly known as angina). It often appears under stress, when the demand of oxygen from the heart muscle is higher, and stops at rest. From a quantitative standpoint, a stenosis is considered significant if the narrowing obstructs more than 70% of the diameter of the artery (Fig.

1

.5) and non significant below 50% [BLA02]. For intermediate cases, additional information is necessary to quantify the impact of the stenosis.

At a more severe stage, plaques can become unstable, rupture, and additionally promote a thrombus (blood clot) that occludes the artery; this can occur in minutes

[Wik11c]

. When a severe enough plaque rupture occurs in the coronary vasculature, it leads to myocardial infarction (necrosis of downstream myocardium), known as heart attack, that can cause death. The non irrigated cardiac cells can eventually die, typically after 4 hours, causing non-reversible damage since these cells do not regenerate themselves. A collagen scar forms in their place. The injured tissue will not contract similarly to normal tissue, nor will it conduct properly electrical impulse, putting the patient at risk for potentially life threatening complications. As a rule of thumb, the longer the infarct, the greater the damage. It is summarized in the famous adage "time is muscle"

[START_REF] Gibson | Time is muscle in primary pci: the strength of the evidence grows[END_REF][START_REF] Antman | Time is muscle:: Translation into practice[END_REF]

.

Table 1 .

 1 2 , 1355 images Complication rate [SJP + 09] 3%

1: Some key figures about PCI (typical orders of magnitude).

Table 2 .

 2

1: Repartition of the images produced with the different estimators according to relative image quality scale (percentages).

  ,w ed e fi n et h epo i n tF P as the only point on the guide-wire having the signed curvilinear abscissa d 2 . Then we define the point P = T -1 t (d 1 ,d 2 )b ym o v i n ga w a yf r o mF P perpendicularly to t(F P ) by (signed distance) d 1 . The registration of a point P of the image I t 0 on an image I t is the point P ′ t computed according to:

		t	1	that
	maps (d 1 ,d 2 )t oap o i n tP . The definition of T -1 t	is straightforward. From the point
	O

t

Table 2 . 2 :

 22 Stents data, including type, length and diameter, have been reported in 85% of the sequences. The lengths of the stents range from 8 to 34 mm, with an average stent length of 19.4m m±6.9. The stent diameters range from 2.25 to 4.[START_REF]Comparison of the line enhancement techniques. SOD stands for Second Order Derivative, RLT for Rotated Line Template and SF for Steerable Filter[END_REF] mm, with an average diameter of 2.9mm±0.47. The types of stents imaged in the study are reported in Table 2.2. The two most represented stents are Cypher (44 times) and Taxus (41 times). Several sequences can contain images of the same stent, in the same patient, but under different imaging conditions (angulation or Xray dose). Stents in the image quality study: stent model, manufacturer, number of occurrences, input image quality, image quality after the application of DSE and improvement in image quality.

	Stent	Manufacturer	Number of cases Input IQ DSE IQ ∆I Q
	Cypher	Cordis	44	1.6	3.4	1.8
	Taxus	Boston Scientific	41	1.2	2.4	1.3
	Pro-kinetic	Biotronik	23	1.2	2.4	1.3
	Vision and Xience	Abbott Vascular	25	1.4	3.2	1.8
	Driver and Endeavor	Medtronic	27	1.7	3.6	1.9
	Lekton Motion	Biotronik	4	1.0	2.5	1.5
	Flexmaster	Abbott	2	1.0	3.0	2.0
	Tsunami	Terumo	1	1.0	3.0	2.0

Table 2 .

 2 3 summarizes the results and tends to demonstrate that the proposed non-linear curve-based technique performs significantly better than the linear marker-ball based registration. Indeed for 27.9% of the cases the non-linear registration produces a better image than the linear one, whereas the opposite only happens in 3.4% of the cases. Moreover in 11.6% of the cases the non-linear registration is better and differs from the linear registration with a difference of category B. The occurrence rate of the opposite is less than 1%. Fig.2.30 depicts examples where the non-linear registration is better suited than the linear one. Around the markers the two enhanced images are very similar, but on the center of the stent the linear registration produces a strong blurring and details are lost. On the contrary, these details are enhanced with the curve-based registration.

Table 2

 2

			.3: Influence of the transform
	curve-based better	=	similarity (marker based) better
	B	A		A	B
	16.3%	11.6%	68.0% 2.7%	0.7%
	(a)				(b)
	(c)				(d)

Table 2 . 4 :

 24 Stents types in the study

	Stent Model	Manufacturer	Occurrence in the study
	Prokinetic	Biotronik	16
	Xience	Abbott	9
	Cypher	Cordis	3
	Tsunami	Terumo	5
	Chrono	Sorin	3
	Taxus	Boston Scientific

Table 2 . 5 :

 25 Stents dimensions in the study The same clinical sequences were processed with StentViz and StentOp. The observers (Reader 1: Dr Funck from René Dubos Hospital, Pontoise, France, and two cardiologists of his team, reader 2 and 3: Dr Guillard and Dr Decalf) rated independently, and blindly the visibility of stents in the input cardiac record sequences, in the StentViz and in the StentOp images according to the image quality scale we presented in 2.3.1 that ranges from 1 (stent hardly visible) to 5 (perfect stent visibility).

		Minimum Maximum Mean Standard deviation
	Stent diameter (mm)	2.25	4.00	2.85	0.44
	Stent length (mm)	8.00	31.00	16.17	6.57
	2.4.5.2 Comparison method

Table 2 .

 2 6 reports the average image quality scores of the input sequences and of the StentViz and StentOp images. µ denotes the average image quality score and σ its standard deviation.

Table 2

 2

			.6: Image quality ratings
		Reader 1	Reader 2	Reader 3
		µ	σ	µ	σ	µ	σ
	Innova	1.39 0.54 1.85 0.73 1.80 0.68
	StentOp 1.98 0.76 2.46 0.78 3.05 1.00
	StentViz 2.63 0.80 3.39 0.89 3.56 1.07

Table 2

 2 We can observe that the results are very favorable to Stentviz, that is perceived superior to StentOp in 74% of the cases. Conversly, StentOp was considered superior to StentViz only in 3% of the cases, and both were considered equal in 23%. Fig.2.32

			.7: Comparative ratings
		StentViz ++ StentViz +	=	StentOp + StentOp ++
	Reader 1	10%	61%	22%	7%	0%
	Reader 2	27%	61%	12%	0%	0%
	Reader 3	24%	39%	34%	2%	0%

Table 4

 4

	Patient TP (%) FP (%)
	1	46	1
	2	53	7
	3	69	4

.1. The algorithm fails in typically half of the frames which is far below the target that we set above 90% (similarly to DSE). This justifies the need for a specific algorithm. However, some bricks of the DSE algorithm that are relevant for this application are kept or adapted.

Table 4 . 1 :

 41 Result of the detection and tracking algorithm designed for DSE.

Table 4 . 2 :

 42 Results of the algorithm vs ground truth for each different stage.

  These results need now to be validated from a clinical point of view. It would be especially interesting to compare this technique to other reference ones such as IVUS. GBK + 09, AGZ + 08, HGG + 09, WCZ + 09, BLHS09, LBL + 09, HVP10a, HVP10b, BWL + 10, Lia10, BLSH10]. We propose in this chapter a new powerful technique for the enhancement of curvilinear structures in an image, based on local shortest paths. The proposed technique associates: (i) a simple formalism, (ii) the resolution of several limitations of previous state of the art techniques and (iii) efficient implementation. It only involves a very reduced number of parameters (typically 2) that have simple interpretation and, in contrast to most of the shortest paths approaches, it does not require either a starting or an ending point. One of the main advantages of our proposed formalism is that it unifies local, semi-local, and global techniques in a single framework where one can set the scale of analysis. We first review state of the art techniques for curvilinear structure enhancement and methodologies to compare them. Then we expose a theoretical description of our method and discuss its links with other known techniques (namely local paths [Vin98, TA07], geodesic voting [RC08] and Hough transform [Pau59]). We finally quantify its performance for the difficult task of guide-wire detection in X-ray fluoroscopy and compare it to other state of the art techniques. BAG + 07, GBK + 09, AGZ + 08, HGG + 09, WCZ + 09, BLHS09, LBL + 09, HVP10a, HVP10b, BWL + 10, Lia10, BLSH10]

	5.3 Background
	The segmentation of curvilinear structures in medical imaging is an extensively stud-
	ied topic that covers a wide variety of naturally elongated biological structures and
	medical tools: neurites [MJS + 04, MJSU03], microtubules [HTD05, OG10], microglia
	[RC08], neurones/axons [WZL + 07, Mei10], ducts in mammograms [ZABT04], cerebral
	structures [MvdEV96], vessels [LABFL09], interventional tools like catheters and guide-
	wires [PWBB97, BVN03, FRvAtHR06, SKUF07, BVG09,

  At this stage, simple operators like thresholding are generally not sufficient to segment the curvilinear structure. A higher level process is invoked to perform segmentation of the feature map. It either involves grouping [SB93, BAG + 07, HVP10a] or tracking [WZL + 07, BLHS09] (usually within a shortest path formalism). Heuristic information about the nature of the structure to segment can be embedded in the algorithm at this stage [BAG + 07]. When several images of a slowly moving structure are segmented in a row, this stage can be performed by tracking a snake spline [BVN03, HGG + 09].

	1. Local scale: This step consists in building a map (sometimes called feature map)
	that represents the probability of presence of an elongated structure at each pixel
	and possibly its orientation [FNVV98, SNA + 97, Lin98, PWBB97, LBL + 09, OG10,
	HTD05, MJS + 04, WZL + 07, BLHS09, MvdEV96, KS05, BVG09, FAoTMLVG91,
	JU04, BAG + 07, WCZ + 09, HVP10a, HVP10b, Vin98, TA07]. The computation
	of such features generally involves considering pixels at a short distance from the
	pixel to process and assumes that the structure is straight at the considered scale.
	2. Semi local scale: The feature map is re-enforced by a process that tends to enhance
	aligned responses [FRvAtHR06, PWBB97, GM91]. Tensor voting and coherence
	enhancing diffusion are examples of such techniques.
	3. Global scale:
	Authors generally describe line detection techniques in two steps: a local pre-processing
	followed by a global segmentation approach [BVG09, HVP10a, HVP10b]. Looking in
	more details at the related literature, it appears more accurate to us to describe them
	in three steps (the second one being optional) that correspond to three different scales
	of analysis:

  in the context of guide-wire detection. Another group of authors [BAG + 07, HVP10a, HVP10b] that do not exactly rely on this methodology, computed metrics related to precision and TPR (but not to FPR). We examine here what are these different methodologies and present ours. Then we synthesize the results of the previous comparisons of line enhancement methods and draw guidelines for the design of successful techniques.

	The first point to address to compare methodologies is the choice of the aspect of
	line enhancement techniques that one wants to evaluate. All the authors have compared
	detection capability [ZABT04, AR07, BAG + 07, HVP10a, HVP10b]. Some authors addi-
	tionally estimated the ability to compute local orientation [ZABT04, AR07], localization
	error [ZABT04], execution time [BVG09, AR07], robustness to parameter setting [AR07]

  several methods are compared based on the qualitative comparison of the ROC curves. We reject the qualitative comparison of ROC curves since it is not properly defined if the curves intersect. The metrics that are not based on TPR and FPR are usually not insentitive to class skew. Therefore we do not select them. The TPR at 1% false positive is not integrating the response of the line enhancement technique over a significant interval of FPR/TPR trade-off and thus lacks generality. Therefore, we propose to evaluate line detection techniques based on the partial AUC. It has the following properties:

Table 5 . 1 :

 51 Comparison of the line enhancement techniques. SOD stands for Second Order Derivative, RLT for Rotated Line Template and SF for Steerable Filter. These are generic categories of filters that include a large number of variations (see references in the table for more details).

	SOD filters are
	steerable.	Study
	also evaluates ori-
	entation accuracy,
	robustness to pa-
	rameter setting and
	execution time.

n],[ p 2 n] , Tn,[pn],0 , Tn,0,[pn] ........

under the supervision of Régis Vaillant -Principal engineer.

This work has been done in the cardiology department of Institut René Dubos (Pontoise -France), under the supervision of Dr. F. Funck.

For more details, the transparent layer formalism is thoroughly described in Chapter

Dr François Funck, head of the cardiology departement of centre hospitalier René Dubos (Pontoise -France) and Neils Guillard, interventional cardiologist in the same institution.

This results holds independently of the distribution of the {Xi} 1≤i≤n . It is a consequence of their statistical independence. At this stage the Gaussian hypothesis is thus not useful.

n],[ p 2 n] , Tn,[pn],0 , Tn,0,[pn]

We define the CNR of an object in the following way: Let v be the value of the object, b the one of the background and σ the standard deviation of the noise in the considered area: CNR = |v-b| σ .

The medial axis of an object is the set of all points having more than one closest point on the object's boundary. In 2D, the medial axis of a plane curve S is the locus of the centers of circles that are tangent to curve S in two or more points, where all such circles are contained in S [B + 67].

This terminology does not mean that we are not dealing with interventional cardiology, but means that the patients are treated in the standard way.

We note that the tracking scheme that we selected is order dependent: its output can be different if the sequence is reversed.

I want to thank Hugues Talbot for his supervision on this study, Olena Tankyevych for her collaboration on the comparison of line enhancement techniques and Nicolas Honnorat for the annotated ground truth on the clinical image database.

This is not the case of metrics like the precision that are not normalized by the number of elements in the two classes

A potential variation at this stage of the definition of the polygonal path image is to assign to each segment of the polygon the cost the minimal path joining its two extremities.

This is for instance false for guide-wires.

Acknowledgements

Caminante no hay

Abbreviations

AMI

List of Tables

We first propose in this chapter 1 a review and a classification of curvilinear structure enhancement methods. Then the methodologies to compare them are reviewed. We propose a new structure to process curvilinear structures, that we call the the polygonal path image. We derive from P some linear structure enhancement and analysis algorithms. We show that P has several interesting properties: it generalizes the concepts of several methods into a unified formalism, and has very simple and intuitive parametrization, and enables the control of the smoothness and length of the structures to detect.

Moreover it benefits from an efficient computational scheme. In order to evaluate the applicability of the method, we estimate quantitatively its performance within the ROC curve formalism on a practical example, the detection of guide-wires in X-ray images.

The results outperform previous state of the art techniques.

Introduction

Curvilinear structures appear naturally in the human body and thus in medical images.

Their segmentation, that enables various diagnostic and interventional application, is an extensively studied topic [MJS + 04, MJSU03, HTD05, OG10, RC08, WZL + 07, Mei10, LABFL09, FRvAtHR06, PWBB97, BVN03, FRvAtHR06, SKUF07, BVG09, BAG + 07,

In the case where all vectors have the same norm (the parameter l of P), this simplifies to :

The operation of voting with a path smoothness constraint is denoted ϑ τ min (P):

p∈I and τ (Pp)>τ min 1 Pp (5.20)

Figure 5.28: We illustrate here the result of path pruning with x = 50% and tortuosity constraints (top 0.6, bottom 0.75). We can observe how the conjuction of pruning and constrained path smoothness help segment the guide-wire.

Estimating local orientation

We demonstrate here how P can be used to estimate the local geometrical properties of the curvilinear structure. We have already illustrated in Fig. 5.14 that when they reach a linear structure the paths tend to follow it and align with it. Therefore the set of paths intersecting on a pixel of a curvilinear structure can be used to derive its orientation (an angle in [0,π[). Outside of the curvilinear structures the paths follow the shortest path that leads to a linear structure. Therefore they convey the piece of information indicating where to find this closest linear structure (a vector in the plane).

Several methods can be used to retrieve this information, the most important pitfall being the extraction of a typical orientation from a set of angles (since angle averaging is not mathematically correct). We propose a two step approach: first we extract an angular information (in [0,π[) at each pixel representing an average orientation of the paths. Then we find the direction that best aligns with paths. Let us consider a given One can easily prove that d θ is a distance in the mathematical sense of the term. The first two properties result from the strict positivity of the potential image. The third one and fourth ones (symmetry and triangular inequality), result from the symmetry of the cones.

In order to demonstrate symmetry, let us consider two points A and B in the image (see Fig. 5.31). If B is neither inside C θ A or C -θ A , there is no conic-path from A to B. Therefore d θ (A, B)=+ ∞. Given the symmetry of the cone definition, A is neither in

In this trivial case, symmetry is thus satisfied. Let us now consider the case where B is inside

Without loss of generality let us consider that it is inside C θ A . Given the symmetry of the cones of orientation θ and -θ, one observes that a conic-path from A to B in the cone C θ A is also a path from B to A in the cone C -θ B . Therefore the distance is symmetric. Regarding the triangular inequality, let us consider a third point C. If there is either no conic path from A to C or from C to B, the inequality is trivial. If there exists a conic-path from A to C and a conic-path from C to B, then, the demonstration (not detailed here) consists in observing that the union of theses path is a conic-path from A to B. Therefore triangular inequality holds.

The computation of the local shortest paths in our presentation is using a set of cones. We denote the set of orientations of these cones Θ. The cost function associated with the local path computation is λ defined by:

Lambda is a semi-metric but not a distance: it verifies the 3 first conditions of a distance but not the triangular inequality (see Fig. 5.33 for a counter example that is similar to the one of bounded curvature paths). However a weaker local triangular inequality holds: given two points A and B, there is a non-void region R A,B such that:

In order to define more precisely R A,B ,wewanttointroduceatthisstagetheconcept of inter-visibility parallelogram. To this end, we consider again the case where B is in

We additionally, consider a point C that is on a conic-path from A to B. C must fulfill the two following conditions:

Moreover, if a point C verifies these two constraints, there exists a conic path from A

Clinical impact and applications

The DSE technique that we proposed, integrated into the Innova series (GE Healthcare), is installed on a large number of clinical sites. Beyond the technical benefits that we have demonstrated (workflow, image quality. . . ), we hope that further long-term studies will ultimately demonstrate that some the tools we develop can yield a significant improvement in either:

• cost: reduce the cost of interventions.

• quality: improve patient outcome.

• access: enable to treat patients that could not benefit from these interventions.

Appendix A

Publication list

Some of the material described in this manuscript have been the subject of publications, patents and master of science thesis.

A.1 Journal