This thesis investigates the exact minimisation of treatment delivery time for Intensity Modulated Radiation Therapy (IMRT) for the treatment of cancer using Multileaf Collimators (MLC). Although patients are required to remain stationary during the delivery of IMRT, inevitably some patient movement will occur, particularly if treatment times are longer than necessary. Therefore minimising the treatment delivery time of IMRT may result in less patient movement, less inaccuracy in the dosage received and a potentially improved outcome for the patient. When IMRT is delivered using multileaf collimators in 'step and shoot' mode, it consists of a sequence of multileaf collimator configurations, or shape matrices; for each, time is needed to set up the configuration, and in addition the patient is exposed to radiation for a specified time, or beam-on time. The 'step and shoot leaf sequencing' problems for minimising treatment time considered in this thesis are the constant set-up time Total Treatment Time (TTT) problem and the Beam-on Time Constrained Minimum Cardinality (BTCMC) problem. The TTT problem minimises a weighted sum of total beam-on time and total number of shape matrices used, whereas the BTCMC problem lexicographically minimises the total beam-on time then the number of shape matrices used in a solution. The vast majority of approaches to these strongly NP-hard problems are heuristics; of the few exact approaches, the formulations either have excessive computation times or their solution methods do not easily incorporate multileaf collimator mechanical constraints (which are present in most currently used MLC systems). In this thesis, new exact mixed integer and integer programming formulations for solving the TTT and BTCMC problems are developed. The models and solution methods considered can be applied to the unconstrained and constrained versions of the problems, where 'constrained' refers to the modelling of additional MLC mechanical constraints. Within the context of integer programming formulations, new and existing methods for improving the computational efficiency of the models presented are investigated. Numerical results for all variations considered are provided. This thesis demonstrates that significant computational improvement can be achieved for the exact mixed integer and integer programming models investigated, via solution approaches based on an idea of systematically 'stepping-up' through the number of shape matrices used in a formulation, via additional constraints (particularly symmetry breaking constraints) and via the application of improved bounds on variables. This thesis also makes a contribution to the wider field of integer programming through the examination of an interesting substructure of an exact integer programming model. In summary, this thesis presents a thorough analysis of possible integer programming models for the strongly NP-hard 'step and shoot' leaf sequencing problems and investigates and applies methods for improving the computational efficiency of such formulations. In this way, this thesis contributes to the field of leaf sequencing for the application of Intensity Modulated Radiation Therapy using Multileaf Collimators.

Le but principal de ce projet est de préparer l’implantation clinique du système Clarity qui utilise une sonde ultrasonore pour visualiser l’anatomie interne du patient. Ce système est utilisé pour les cas de prostate et nécessite d’être adapté pour les cas de poumon. L’utilité de ce système est de suivre un substitut afin d’inférer la position d’une tumeur pulmonaire. L’hypothèse de cette étude est qu’un substitut interne serait mieux corrélé avec une tumeur pulmonaire que le seraient des marqueurs externes. Les sous-objectifs sont : 1) aborder l’adaptation du montage pour faire des acquisitions sur des patients ; 2) explorer la performance des algorithmes de détection de mouvements ainsi que des métriques de qualité d’image sur des images US et ciné IRM; 3) démontrer que la corrélation entre un substitut interne et une structure pulmonaire est plus grande que celle avec un substitut externe. Pour les acquisitions d’images US, la sonde est placée sur les volontaires et fixée à la table de traitement à l’aide d’un bras mécanique. Il a été démontré qu’une pression insuffisante peut causer une perte de signal dû à la forme curviligne de la sonde. La diminution de la moyenne des intensités de l’image et de l’écart-type confirme une perte de signal lors d’amplitudes respiratoires élevées justifiée par une perte de contact entre la sonde et la peau malgré la fixation de la sonde. Entre les algorithmes de corrélation croisée normalisée (NCC), d’erreur moyenne quadratique (RMS) et de flux optique, la méthode NCC semble la plus robuste pour suivre le substitut interne (structure dans le foie) dans les images IRM pour 5/9 volontaires sains ( = 0, 050). Cette méthode est utilisé présentement pour les cas de prostate. Le flux optique s’est montré plus efficace pour des cas spécifiques ce qui démontre l’intérêt d’adapter l’algorithme pour les cas de poumons. Enfin, il a été démontré sur les images IRM qu’un substitut interne au niveau du foie est plus efficace pour la majorité des volontaires (8/9) en comparaison avec un marqueur sur la peau placé dans la région abdominale. Le marqueur abdominal possède une meilleure corrélation qu’un marqueur thoracique (9/9) illustrant l’importance du positionnement d’un marqueur externe pour le suivi d’une tumeur pulmonaire. / The main objective of this thesis is to prepare the clinical implementation of the Clarity ultrasound system for indirect lung tumours tracking using a surrogate. It is currently used for motion management during prostate treatments and requires adaptation. Our hypothesis is that an internal marker would have a better correlation with the tumour’s position than an external surrogate. The sub-objectives are : 1) test different setups for the image acquisition on patients ; 2) explore the algorithms’ performance for motion detection as well as the image quality metrics on US and dynamic MRI images ; 3) evaluate the correlation between surrogates and a lung structure to determine which performs best. The ultrasound probe is fixed on the treatment couch for the acquisition on healthy volunteers using a mechanical arm. Low pressure on the patient’s skin results in a loss of signal due to the curvilinear shape of the probe. We observed a loss of contact between the probe and the volunteers’ skin due to ample movements causing a deterioration of the image quality. We tested three different motion detection algorithms on dynamic MRI images : normalized cross-correlation (NCC), root mean square error (RMS) and optical flow. The NCC algorithm is the most robust out of the three for 5/9 volunteers for the internal surrogate tracking ( < 0.050). In specific cases, the optical flow method performed better indicating an interest in developping a new algorithm for indirect lung tracking. Finally, the correlation between the surrogates and a lung structure were calculated using the MRI images. The internal surrogate inside the liver was proven more efficient for indirect lung tumour tracking for 8/9 volunteers. External markers give a greater prediction error. It has also been shown that the positioning of the external marker on the patient’s skin impacts the correlation. The abdominal marker is better than the thoracic one for all the volunteers.

Das entwickelte Bildgeführte Präzisionsbestrahlungsgerät für Kleintiere (engl. Small Animal Image-Guided Radiation Therapy – SAIGRT) dient der schnellen, hochauflösenden Röntgenbildgebung und präzisen, konformalen Bestrahlung von Kleintieren im Rahmen präklinischer in-vivo Experimente für die translationale Krebsforschung. Speziell programmierte Softwares zur Gerätesteuerung sowie zur Bildkorrektur- und Bildrekonstruktion auf dem zentralen leistungsfähigen Arbeitsplatz-PC stellen alle Gerätefunktionen zur Verfügung und ermöglichen durch automatisierte Abläufe und intuitive grafische Nutzeroberflächen eine einfache, sichere Bedienung. Für die Bestrahlungsplanung wird eine vollwertige, aus der humanen klinischen Strahlentherapie adaptierte 3D-Bestrahlungsplanungssoftware eingesetzt, die etablierte Werkzeuge für den Transfer und die Koregistrierung multimodaler Bilddaten, die Konturierung und Segmentierung von Zielvolumina und Risikoorganen sowie die Erstellung und Validierung von Bestrahlungsplänen enthält. Die resultierende Dosisverteilung wird darin basierend auf dem individuellen CT-Datensatz des Versuchstieres und einem auf das SAIGRT angepassten Maschinenmodell mittels eines Monte-Carlo-Algorithmus exakt und realitätsnah simuliert. Durch geometrische Kalibrierungen und vielfältige Basisdatenmessungen für die Bildgebung und Bestrahlung im Rahmen der Gerätekommissionierung ist eine Zielgenauigkeit von ca. ±0,1 mm mit hoher geometrischer Abbildungstreue und guter Bildqualität bei Bildgebungsdosen vergleichbar denen klinischer Radiografie- und CT-Geräte möglich. Die Dosisverteilung zur Bestrahlung der Versuchstiere spiegelt bei der definierten Strahlungsqualität größenskaliert die humane Strahlentherapie mit hochenergetischer Photonenstrahlung von klinischen Linearbeschleunigern wider. Ein umfassendes Qualitätssicherungsprogramm bestehend aus regelmäßiger Wartung und wiederkehrenden Konstanzprüfungen der Bildgebung und Bestrahlung sichert dauerhaft den technisch einwandfreien Zustand und die ordnungsgemäße Verfügbarkeit aller Gerätefunktionen in gleichbleibender Güte. Das SAIGRT ist somit nachweislich geeignet, bildgeführte Bestrahlungen mit einem Ablauf analog dem einer modernen klinischen Strahlentherapie am Menschen in präklinischen in-vivo Experimenten präzise an Kleintieren zu applizieren. Es leistet dadurch einen essentiellen Beitrag zur translationalen Krebsforschung in Dresden, indem die klinische Situation realistischer modelliert und so potenziell die Übertragbarkeit der Ergebnisse auf Krebspatienten verbessert werden kann. / The Small Animal Image-Guided Radiation Therapy (SAIGRT) platform facilitates fast, high resolution X-ray imaging and precise, conformal irradiation of small animals in preclinical in-vivo experiments for translational cancer research. Dedicated software for device control as well as image correction and reconstruction on a central high performance PC provide all device functions and allow simple and safe operation by automated procedures and intuitive graphical user interfaces. A fully 3D treatment planning software adapted from human clinical radiation therapy is used for treatment planning, containing established tools and methods for the transfer and registration of multimodality imaging data, contouring and segmentation of target volumes and organs at risk as well as creation and evaluation of treatment plans. Based on an individual CT scan of the small animal and a machine model adapted for the SAIGRT, the resulting dose distribution is simulated by a Monte-Carlo algorithm in a precise and realistic manner. Geometrical calibrations as well as manifold basic data measurements for X-ray imaging and irradiation during commissioning resulted in a targeting and imaging accuracy of about ±0.1 mm, a correct representation of imaging geometry and a good image quality with imaging doses comparable with those of clinical radiography and CT systems. Dose distribution of the defined beam quality used for irradiation of small animals reflects a downsized human radiation therapy using high energy photon beams of clinical linear accelerators. A comprehensive quality assurance program comprising regular maintenance and periodic constancy tests of X-ray imaging and irradiation ensures permanent technically perfect condition and proper availability of all implemented functions in a stable high quality. The SAIGRT platform is feasible for image-guided irradiations precisely applied to small animals in preclinical in-vivo experiments using a workflow of modern human radiation oncology. Thus, it significantly contributes to translational cancer research by more realistic modelling the clinical situation and potentially brings the results closer to their clinical implementation.

This thesis addresses three problems related to image registration, prediction and tracking, applied to Angiography and Oncology. For image analysis, various probabilistic models have been employed to characterize the image deformations, target motions and state estimations. (i) In Digital Subtraction Angiography (DSA), having a high quality visualization of the blood motion in the vessels is essential both in diagnostic and interventional applications. In order to reduce the inherent movement artifacts in DSA, non-rigid image registration is used before subtracting the mask from the contrast image. DSA image registration is a challenging problem, as it requires non-rigid matching across spatially non-uniform control points, at high speed. We model the problem of sub-pixel matching, as a labeling problem on a non-uniform Markov Random Field (MRF). We use quad-trees in a novel way to generate the non uniform grid structure and optimize the registration cost using graph-cuts technique. The MRF formulation produces a smooth displacement field which results in better artifact reduction than with the conventional approach of independently registering the control points. The above approach is further improved using two models. First, we introduce the concept of pivotal and non-pivotal control points. `Pivotal control points' are nodes in the Markov network that are close to the edges in the mask image, while 'non-pivotal control points' are identified in soft tissue regions. This model leads to a novel MRF framework and energy formulation. Next, we propose a Gaussian MRF model and solve the energy minimization problem for sub-pixel DSA registration using Random Walker (RW). An incremental registration approach is developed using quad-tree based MRF structure and RW, wherein the density of control points is hierarchically increased at each level M depending of the features to be used and the required accuracy. A novel numbering scheme of the control points allows us to reuse the computations done at level M in M + 1. Both the models result in an accelerated performance without compromising on the artifact reduction. We have also provided a CUDA based design of the algorithm, and shown performance acceleration on a GPU. We have tested the approach using 25 clinical data sets, and have presented the results of quantitative analysis and clinical assessment. (ii) In External Beam Radiation Therapy (EBRT), in order to monitor the intra fraction motion of thoracic and abdominal tumors, the lung diaphragm apex can be used as an internal marker. However, tracking the position of the apex from image based observations is a challenging problem, as it undergoes both position and shape variation. We propose a novel approach for tracking the ipsilateral hemidiaphragm apex (IHDA) position on CBCT projection images. We model the diaphragm state as a spatiotemporal MRF, and obtain the trace of the apex by solving an energy minimization problem through graph-cuts. We have tested the approach using 15 clinical data sets and found that this approach outperforms the conventional full search method in terms of accuracy. We have provided a GPU based heterogeneous implementation of the algorithm using CUDA to increase the viability of the approach for clinical use. (iii) In an adaptive radiotherapy system, irrespective of the methods used for target observations there is an inherent latency in the beam control as they involve mechanical movement and processing delays. Hence predicting the target position during `beam on target' is essential to increase the control precision. We propose a novel prediction model (called o set sine model) for the breathing pattern. We use IHDA positions (from CBCT images) as measurements and an Unscented Kalman Filter (UKF) for state estimation. The results based on 15 clinical datasets show that, o set sine model outperforms the state of the art LCM model in terms of prediction accuracy.