Franck’s Publications

This work is based on a cooperative co-evolution algorithm called `Fly Algorithm', which is an evolutionary algorithm (EA) where individuals are called `flies'. It is a specific case of the `Parisian Approach' where the solution of an optimisation problem is a set of individuals (e.g. the whole population) instead of a single individual (the best one) as in typical EAs. The optimisation problem considered here is tomography reconstruction in positron emission tomography (PET). It estimates the concentration of a radioactive substance (called a radiotracer) within the body. Tomography, in this context, is considered as a difficult ill-posed inverse problem. The Fly Algorithm aims at optimising the position of 3-D points that mimic the radiotracer. At the end of the optimisation process, the fly population is extracted as it corresponds to an estimate of the radioactive concentration. During the optimisation loop a lot of data is generated by the algorithm, such as image metrics, duration, and internal states. This data is recorded in a log file that can be post-processed and visualised. We propose using information visualisation and user interaction techniques to explore the algorithm's internal data. Our aim is to better understand what happens during the evolutionary loop. Using an example, we demonstrate that it is possible to interactively discover when an early termination could be triggered. It is implemented in a new stopping criterion. It is tested on two other examples on which it leads to a 60% reduction of the number of iterations without any loss of accuracy.

Keywords: Fly Algorithm; Tomography reconstruction; Information visualisation; Data exploration; Artificial evolution; Parisian evolution.

The aim of this study is to generate artistic images, such as digital mosaics, as an optimisation problem without the introduction of any a priori knowledge or constraint other than an input image. The usual practice to produce digital mosaic images heavily relies on Centroidal Voronoi diagrams. We demonstrate here that it can be modelled as an optimisation problem solved using a cooperative co-evolution strategy based on the Parisian evolution approach, the Fly algorithm. An individual is called a fly. Its aim of the algorithm is to optimise the position of infinitely small 3-D points (the flies). The Fly algorithm has been initially used in real-time stereo vision for robotics. It has also demonstrated promising results in image reconstruction for tomography. In this new application, a much more complex representation has been study. A fly is a tile. It has its own position, size, colour, and rotation angle. Our method takes advantage of graphics processing units (GPUs) to generate the images using the modern OpenGL Shading Language (GLSL) and Open Computing Language (OpenCL) to compute the difference between the input image and simulated image. Different types of tiles are implemented, some with transparency, to generate different visual effects, such as digital mosaic and spray paint. An online study with 41 participants has been conducted to compare some of our results with those generated using an open-source software for image manipulation. It demonstrates that our method leads to more visually appealing images.

Keywords: Digital mosaic; Evolutionary art; Fly Algorithm; Parisian evolution; Cooperative co-evolution

The Fly Algorithm was initially developed for 3-D robot vision applications. It consists in solving the inverse problem of shape reconstruction from projections by evolving a population of 3-D points in space (the `flies'), using an evolutionary optimisation strategy. Here, in its version dedicated to tomographic reconstruction in medical imaging, the flies are mimicking radioactive photon sources. Evolution is controlled using a fitness function based on the discrepancy of the projections simulated by the flies with the actual pattern received by the sensors. The reconstructed radioactive concentration is derived from the population of flies, i.e. a collection of points in the 3-D Euclidean space, after convergence. `Good' flies were previously binned into voxels. In this paper, we study which flies to include in the final solution and how this information can be sampled to provide more accurate datasets in a reduced computation time. We investigate the use of density fields, based on Metaballs and on Gaussian functions respectively, to obtain a realistic output. The spread of each Gaussian kernel is modulated in function of the corresponding fly fitness. The resulting volumes are compared with previous work in terms of normalised-cross correlation. In our test-cases, data fidelity increases by more than 10% when density fields are used instead of binning. Our method also provides reconstructions comparable to those obtained using well-established techniques used in medicine (filtered back- projection and ordered subset expectation-maximisation).

Keywords: Fly algorithm; Evolutionary computation; tomography reconstruction; iterative algorithms; inverse problems; co-operative co-evolution

We present a framework that combines evolutionary optimisation, soft tissue modelling and ray tracing on GPU to simultaneously compute the respiratory motion and X-ray imaging in real-time. Our aim is to provide validated building blocks with high fidelity to closely match both the human physiology and the physics of X-rays. A CPU-based set of algorithms is presented to model organ behaviours during respiration. Soft tissue deformation is computed with an extension of the Chain Mail method. Rigid elements move according to kinematic laws. A GPU-based surface rendering method is proposed to compute the X-ray image using the Beer–Lambert law. It is provided as an open-source library. A quantitative validation study is provided to objectively assess the accuracy of both components: (i) the respiration against anatomical data, and (ii) the X-ray against the Beer–Lambert law and the results of Monte Carlo simulations. Our implementation can be used in various applications, such as interactive medical virtual environment to train percutaneous transhepatic cholangiography in interventional radiology, 2D/3D registration, computation of digitally reconstructed radiograph, simulation of 4D sinograms to test tomography reconstruction tools.

Keywords: X-ray simulation, Deterministic simulation (ray-tracing), Digitally reconstructed radiograph, Respiration simulation, Medical virtual environment, Imaging guidance, Interventional radiology training

Purpose: Training in Interventional Radiology currently uses the apprenticeship model, where clinical and technical skills of invasive procedures are learnt during practice in patients. This apprenticeship training method is increasingly limited by regulatory restrictions on working hours, concerns over patient risk through trainees’ inexperience and the variable exposure to case mix and emergencies during training. To address this, we have developed a computer-based simulation of visceral needle puncture procedures. Methods: A real-time framework has been built that includes: segmentation, physically based modelling, haptics rendering, pseudo-ultrasound generation and the concept of a physical mannequin. It is the result of a close collaboration between different universities, involving computer scientists, clinicians, clinical engineers and occupational psychologists. Results: The technical implementation of the framework is a robust and real-time simulation environment combining a physical platform and an immersive computerized virtual environment. The face, content and construct validation have been previously assessed, showing the reliability and effectiveness of this framework, as well as its potential for teaching visceral needle puncture. Conclusion: A simulator for ultrasound-guided liver biopsy has been developed. It includes functionalities and metrics extracted from cognitive task analysis. This framework can be useful during training, particularly given the known difficulties in gaining significant practice of core skills in patients.

Keywords: Biomedical computing, Image segmentation, Simulation, Virtual reality

We present and analyze the behavior of an evolutionary algorithm designed to estimate the parameters of a complex organ behavior model. The model is adaptable to account for patients specificities. The aim is to finely tune the model to be accurately adapted to various real patient datasets. It can then be embedded, for example, in high fidelity simulations of the human physiology. We present here an application focused on respiration modeling. The algorithm is automatic and adaptive. A compound fitness function has been designed to take into account for various quantities that have to be minimized. The algorithm efficiency is experimentally analyzed on several real test-cases: i) three patient datasets have been acquired with the breath hold protocol, and ii) two datasets corresponds to 4D CT scans. Its performance is compared with two traditional methods (downhill simplex and conjugate gradient descent), a random search and a basic realvalued genetic algorithm. The results show that our evolutionary scheme provides more significantly stable and accurate results.

Keywords: Evolutionary computation, inverse problems, medical simulation, adaptive algorithm

Purpose: We present here a simulator for interventional radiology focusing on percutaneous transhepatic cholangiography (PTC). This procedure consists of inserting a needle into the biliary tree using fluoroscopy for guidance. Methods: The requirements of the simulator have been driven by a task analysis. The three main components have been identified: the respiration, the real-time X-ray display (fluoroscopy) and the haptic rendering (sense of touch). The framework for modelling the respiratory motion is based on kinematics laws and on the Chainmail algorithm. The fluoroscopic simulation is performed on the graphic card and makes use of the Beer-Lambert law to compute the X-ray attenuation. Finally, the haptic rendering is integrated to the virtual environment and takes into account the soft-tissue reaction force feedback and maintenance of the initial direction of the needle during the insertion. Results: Five training scenarios have been created using patient-specific data. Each of these provides the user with variable breathing behaviour, fluoroscopic display tuneable to any device parameters and needle force feedback. Conclusions A detailed task analysis has been used to design and build the PTC simulator described in this paper. The simulator includes real-time respiratory motion with two independent parameters (rib kinematics and diaphragm action), on-line fluoroscopy implemented on the Graphics Processing Unit and haptic feedback to feel the soft-tissue behaviour of the organs during the needle insertion.

Keywords: Interventional radiology; Virtual environments; Respiration simulation; X-ray simulation; Needle puncture; Haptics; Task analysis

We present an integrated system for training ultrasound (US) guided needle puncture. Our aim is to provide a validated training tool for interventional radiology (IR) that uses actual patient data. IR procedures are highly reliant on the sense of touch and so haptic hardware is an important part of our solution. A hybrid surface/volume haptic rendering of an US transducer is proposed to constrain the device to remain outside the bony structures when scanning the patient's skin. A volume haptic model is proposed that implements an effective model of needle puncture. Force measurements have been made on real tissue and the resulting data is incorporated into the model. The other input data required is a computed tomography (CT) scan of the patient that is used to create the patient specific models. It is also the data source for a novel simulation of a virtual US scanner, which is used to guide the needle to the correct location.

Keywords: medical virtual environment; imaging guidance; interventional radiology training; needle puncture; volume haptics; vertex and pixel shaders

The medical domain provides excellent opportunities for the application of computer graphics, visualization and virtual environments, with the potential to help improve healthcare and bring benefits to patients. This survey paper provides a comprehensive overview of the state-of-the-art in this exciting field. It has been written from the perspective of both computer scientists and practising clinicians and documents past and current successes together with the challenges that lie ahead. The article begins with a description of the software algorithms and techniques that allow visualization of and interaction with medical data. Example applications from research projects and commercially available products are listed, including educational tools; diagnostic aids; virtual endoscopy; planning aids; guidance aids; skills training; computer augmented reality and use of high performance computing. The final section of the paper summarizes the current issues and looks ahead to future developments.

Keywords: visualization; augmented and virtual realities; computer graphics; health; physically-based modeling; medical sciences; simulation

Qualitative and quantitative use of volumes reconstructed by computed tomography (CT) can be compromised due to artefacts which corrupt the data. This article illustrates a method based on virtual X-ray imaging to investigate sources of artefacts which occur in microtomography using synchrotron radiation. In this phenomenological study, different computer simulation methods based on physical X-ray properties, eventually coupled with experimental data, are used in order to compare artefacts obtained theoretically to those present in a volume acquired experimentally, or to predict them for a particular experimental setup. The article begins with the presentation of a synchrotron microtomographic slice of a reinforced fibre composite acquired at the European Synchrotron Radiation Facility (ESRF) containing streak artefacts. This experimental context is used as the motive throughout the paper to illustrate the investigation of some artefact sources. First, the contribution of direct radiation is compared to the contribution of secondary radiations. Then, the effect of some methodological aspects are detailed, including under-sampling, sample and camera misalignment, sample extending outside of the field of view and photonic noise. The effect of harmonic components present in the experimental spectrum are also simulated. Afterwards, detector properties, such as its impulse response or defective pixels, are taken into account. Finally, the importance of phase contrast effects is evaluated. In the last section, this investigation is discussed by putting emphasis on the experimental context which is used throughout this paper.

Keywords: X-ray microtomography; Artefact; Deterministic simulation (ray-tracing); Monte Carlo method; Phase contrast; Modulation transfer function

Throughout the practice of procedural medicine, there is an unrelenting shift to management by less invasive techniques such as interventional radiology (IR). This subspecialty within radiology uses imaging to guide needles, wires and catheters using tiny access incisions. Like other minimally invasive techniques, risk, pain and recovery times are reduced as compared with more invasive approaches such as open surgery. These benefits, alongside the emergence of increasingly novel therapeutic technologies, are driving worldwide expansion. The core skills of IR include the Seldinger technique and the use of imaging and touch to effectively guide needles, wires and catheters in a wide range of procedures. Safe practice requires the operator to respond correctly to both visual and tactile cues in vascular angioplasty, stenting and stent-grafting, as well as control of bleeding, biopsy, abscess drainage and catheterization of the urinary and biliary tracts for drainage and stenting. The operator's deliberations may then initiate and inform a range of motor actions, including very fine translational and rotational motions, particularly in challenging anatomy. As the spectrum of available techniques increases, so the limited number and availability of suitably trained practitioners becomes a factor in their restricted availability to patients. Awareness of the need to expand IR training facilities is thus highly topical.

Our work is based on a Cooperative Co-evolution Algorithm -- the Fly algorithm -- in which individuals correspond to 3-D points. The Fly algorithm uses two levels of fitness function: i) a local fitness computed to evaluate a given individual (usually during the selection process) and ii) a global fitness to assess the performance of the population as a whole. This global fitness is the metrics that is minimised (or maximised depending on the problem) by the optimiser. Here the solution of the optimisation problem corresponds to a set of individuals instead of a single individual (the best individual) as in classical evolutionary algorithms. The Fly algorithm heavily relies on mutation operators and a new blood operator to insure diversity in the population. To lead to accurate results, a large mutation variance is often initially used to avoid local minima (or maxima). It is then progressively reduced to refine the results. Another approach is the use of adaptive operators. However, very little research on adaptive operators in Fly algorithm has been conducted. We address this deficiency and propose 4 different fully adaptive mutation operators in the Fly algorithm: positrons, and the final solution of the algorithm approximates the radioactivity concentration. The view and analysis four mutation operators, which are Basic Mutation, Adaptive Mutation Variance, Dual Mutation, and Directed Mutation. Due to the complex nature of the search space, (kN-dimensions, with k the number of genes per individuals and N the number of individuals in the population), we favour operators with a low maintenance cost in terms of computations. Their impact on the algorithm efficiency is analysed and validated on positron emission tomography (PET) reconstruction.

Keywords: evolutionary algorithms, Parisian approach, reconstruction algorithms, positron emission tomography, mutation operator

Our work is based on a Cooperative Co-evolution Algorithm -- the Fly algorithm -- in which individuals correspond to 3-D points. The Fly algorithm uses two levels of fitness function: i) a local fitness computed to evaluate a given individual (usually during the selection process) and ii) a global fitness to assess the performance of the population as a whole. This global fitness is the metrics that is minimised (or maximised depending on the problem) by the optimiser. Here the solution of the optimisation problem corresponds to a set of individuals instead of a single individual (the best individual) as in classical evolutionary algorithms. The Fly algorithm heavily relies on mutation operators and a new blood operator to insure diversity in the population. To lead to accurate results, a large mutation variance is often initially used to avoid local minima (or maxima). It is then progressively reduced to refine the results. Another approach is the use of adaptive operators. However, very little research on adaptive operators in Fly algorithm has been conducted. We address this deficiency and propose 4 different fully adaptive mutation operators in the Fly algorithm: positrons, and the final solution of the algorithm approximates the radioactivity concentration. The view and analysis four mutation operators, which are Basic Mutation, Adaptive Mutation Variance, Dual Mutation, and Directed Mutation. Due to the complex nature of the search space, (kN-dimensions, with k the number of genes per individuals and N the number of individuals in the population), we favour operators with a low maintenance cost in terms of computations. Their impact on the algorithm efficiency is analysed and validated on positron emission tomography (PET) reconstruction.

Keywords: evolutionary algorithms, Parisian approach, reconstruction algorithms, positron emission tomography, mutation operator

The aim of this study is to generate artistic images, such as digital mosaics, as an optimisation problem without the introduction of any a priori knowledge or constraint other than an input image. The usual practice to produce digital mosaic images heavily relies on Centroidal Voronoi diagrams. We demonstrate here that it can be modelled as an optimisation problem solved using a cooperative co-evolution strategy based on the Parisian evolution approach, the Fly algorithm. An individual is called a fly. Its aim of the algorithm is to optimise the position of innitely small 3-D points (the flies). The Fly algorithm has been initially used in real-time stereo vision for robotics. It has also demonstrated promising results in image reconstruction for tomography. In this new application, a much more complex representation has been studied. A fly is a tile. It has its own position, size, colour, and rotation angle. Our method takes advantage of graphics processing units (GPUs) to generate the images using the modern OpenGL Shading Language (GLSL) and Open Computing Language (OpenCL) to compute the difference between the input image and simulated image. Different types of tiles are implemented, some with transparency, to generate different visual effects, such as digital mosaic and spray paint. An online study with 41 participants has been conducted to compare some of our results with those generated using an open-source software for image manipulation. It demonstrates that our method leads to more visually appealing images.

Keywords: Digital mosaic, Evolutionary art, Fly algorithm, Parisian evolution, cooperative co-evolution

This study is about Evolutionary art such as digital mosaics. The most common techniques to generate a digital mosaic effect heavily rely on Centroidal Voronoi diagrams. Our method generates artistic images as an optimisation problem without the introduction of any a priori knowledge or constraint other than the input image. We adapt a cooperative co-evolution strategy based on the Parisian evolution approach, the Fly algorithm, to produce artistic visual effects from an input image (e.g. a photograph). The primary usage of the Fly algorithm is in computer vision, especially stereo-vision in robotics. It has also been used in image reconstruction for tomography. Until now the individuals correspond to simplistic primitives: Infinitely small 3-D points. In this paper, the individuals have a much more complex representation and represent tiles in a mosaic. They have their own position, size, colour, and rotation angle. We take advantage of graphics processing units (GPUs) to generate the images using the modern OpenGL Shading Language. Different types of tiles are implemented, some with transparency, to generate different visual effects, such as digital mosaic and spray paint. A user study has been conducted to evaluate some of our results. We also compare results with those obtained with GIMP, an open-source software for image manipulation.

Keywords: Digital mosaic; Evolutionary art; Fly algorithm; Parisian evolution; Cooperative co-evolution

Visual computing represents one of the most challenging and inspiring arenas in computer science. Today, fifty percent of content on the internet is in the form of visual data and information, and more than fifty percent of the neurons in the human brain are used in visual perception and reasoning. RIVIC is the collaborative amalgamation of research programmes between the computer science departments in Aberystwyth, Bangor, Cardiff and Swansea universities. Its aim is to promote research in visual computing, e.g. visualisation, computer vision and image/video processing, computer graphics and virtual environments.

This paper shows new resutls of our artificial evolution algorithm for Positron Emission Tomography (PET) reconstruction. This imaging technique produces datasets corresponding to the concentration of positron emitters within the patient. Fully three-dimensional (3D) tomographic reconstruction requires high computing power and leads to many challenges. Our aim is to produce high quality datasets in a time that is clinically acceptable. Our method is based on a co-evolution strategy called the “Fly algorithm”. Each fly represents a point in space and mimics a positron emitter. Each fly position is progressively optimised using evolutionary computing to closely match the data measured by the imaging system. The performance of each fly is assessed based on its positive or negative contribution to the performance of the whole population. The final population of flies approximates the radioactivity concentration. This approach has shown promising results on numerical phantom models. The size of objects and their relative concentrations can be calculated in two-dimensional (2D) space. In (3D), complex shapes can be reconstructed. In this paper, we demonstrate the ability of the algorithm to fidely reconstruct more anatomically realistic volumes.

Keywords: Evolutionary computation, inverse problems, adaptive algorithm, Nuclear medicine, Positron emission tomography, Reconstruction algorithms

This paper is an overview of a method recently published in a biomedical journal (IEEE Transactions on Biomedical Engineering, http://tbme.embs.org). The method is based on an optimisation technique called “evolutionary strategy” and it has been designed to estimate the parameters of a complex 15-D respiration model. This model is adaptable to account for patient's specificities. The aim of the optimisation algorithm is to finely tune the model so that it accurately fits real patient datasets. The final results can then be embedded, for example, in high fidelity simulations of the human physiology. Our algorithm is fully automatic and adaptive. A compound fitness function has been designed to take into account for various quantities that have to be minimised (here topological errors of the liver and the diaphragm geometries). The performance our implementation is compared with two traditional methods (downhill simplex and conjugate gradient descent), a random search and a basic real-valued genetic algorithm. It shows that our evolutionary scheme provides results that are significantly more stable and accurate than the other tested methods. The approach is relatively generic and can be easily adapted to other complex parametrisation problems when ground truth data is available.

Keywords: Evolutionary computation, inverse problems, medical simulation, adaptive algorithm

We propose a method to automatically tune a patient-based virtual environment training simulator for abdominal needle insertion. The key attributes to be customized in our framework are the elasticity of soft-tissues and the respiratory model parameters. The estimation is based on two 3D Computed Tomography (CT) scans of the same patient at two different time steps. Results are presented on five patients and show that our new method leads to better results than our previous studies with manually tuned parameters.

We present and analyse the behaviour of specialised operators designed for cooperative coevolution strategy in the framework of 3D tomographic PET reconstruction. The basis is a simple cooperative co-evolution scheme (the “fly algorithm”), which embeds the searched solution in the whole population, letting each individual be only a part of the solution. An individual, or fly, is a 3D point that emits positrons. Using a cooperative co-evolution scheme to optimize the position of positrons, the population of flies evolves so that the data estimated from flies matches measured data. The final population approximates the radioactivity concentration. In this paper, three operators are proposed, threshold selection, mitosis and dual mutation, and their impact on the algorithm efficiency is experimentally analysed on a controlled test-case. Their extension to other cooperative co-evolution schemes is discussed.

In this paper, we propose a deterministic simulation of X-ray transmission imaging on graphics hardware. Only the directly transmitted photons are simulated, using the Beer-Lambert law. Our previous attempt to simulate Xray attenuation from polygon meshes utilising the GPU showed significant increase of performance, with respect to a validated software implementation, without loss of accuracy. However, the simulations were restricted to monochromatic X-rays and finite point sources. We present here an extension to our method to perform physically more realistic simulations by taking into account polychromatic X-rays and focal spots causing blur.

Keywords: Three-Dimensional Graphics and Realism; Raytracing; Physical Sciences and Engineering; Physics

This paper presents an evolutionary approach for image reconstruction in positron emission tomography (PET). Our reconstruction method is based on a cooperative coevolution strategy (also called Parisian evolution): the “fly algorithm”. Each fly is a 3D point that mimics a positron emitter. The flies' position is progressively optimised using evolutionary computing to closely match the data measured by the imaging system. The performance of each fly is assessed using a “marginal evaluation” based on the positive or negative contribution of this fly to the performance of the population. Using this property, we propose a “thresholded-selection” method to replace the classical tournament method. A mitosis operator is also proposed. It is triggered to automatically increase the population size when the number of flies with negative fitness becomes too low.

This paper presents a method to take advantage of artificial evolution in positron emission tomography reconstruction. This imaging technique produces datasets that correspond to the concentration of positron emitters through the patient. Fully 3D tomographic reconstruction requires high computing power and leads to many challenges. Our aim is to reduce the computing cost and produce datasets while retaining the required quality. Our method is based on a coevolution strategy (also called Parisian evolution) named “Fly algorithm”. Each fly represents a point of the space and acts as a positron emitter. The final population of flies corresponds to the reconstructed data. Using “marginal evaluation”, the fly's fitness is the positive or negative contribution of this fly to the performance of the population. This is also used to skip the relatively costly step of selection and simplify the evolutionary algorithm.

We present an integrated system for training visceral needle puncture procedures. Our aim is to provide a cost effective and validated training tool that uses actual patient data to enable interventional radiology trainees to learn how to carry out image-guided needle puncture. The input data required is a computed tomography scan of the patient that is used to create the patient specific models. Force measurements have been made on real tissue and the resulting data is incorporated into the simulator. Respiration and soft tissue deformations are also carried out to further improve the fidelity of the simulator.

Keywords: Physically based modelling, Virtual reality

We present an integrated system for training ultrasound guided needle puncture. Our aim is to provide a cost effective and validated training tool that uses actual patient data to enable interventional radiology trainees to learn how to carry out image-guided needle puncture. The input data required is a computed tomography scan of the patient that is used to create the patient specific models. Force measurements have been made on real tissue and the resulting data is incorporated into the simulator. Respiration and soft tissue deformations are also carried out to further improve the fidelity of the simulator.

Keywords: image guided needle puncture training, interventional radiology training, needle puncture

This paper reports on a low cost system for training ultrasound imaging techniques. The need for such training is particularly acute in developing countries where typically ultrasound scanners remain idle due to the lack of experienced sonographers. The system described below is aimed at a PC platform but uses interface components from the Nintendo Wii games console. The training software is being designed to support a variety of patient case studies, and also supports remote tutoring over the internet.

Keywords: Ultrasound Training, medical virtual environment, hci

Recent years have seen a significant increase in the use of Interventional Radiology (IR) as an alternative to open surgery. A large number of IR procedures commences with needle puncture of a vessel to insert guidewires and catheters: these clinical skills are acquired by all radiologists during training on patients, associated with some discomfort and occasionally, complications. While some visual skills can be acquired using models such as the ones used in surgery, these have limitations for IR which relies heavily on a sense of touch. Both patients and trainees would benefit from a virtual environment (VE) conveying touch sensation to realistically mimic procedures. The authors are developing a high fidelity VE providing a validated alternative to the traditional apprenticeship model used for teaching the core skills. The current version of the CRaIVE simulator combines home made software, haptic devices and commercial equipments.

Keywords: Virtual environment, patient specific model, interventional radiology

Interventional Radiology (IR) procedures are minimally invasive, targeted treatments performed using imaging for guidance. Needle puncture using ultrasound, x-ray, or computed tomography (CT) images is a core task in the radiology curriculum, and we are currently devel- oping a training simulator for this. One requirement is to include support for physically-based simulation of x-ray images from CT data sets. In this paper, we demonstrate how to exploit the capability of today's graphics cards to efficiently achieve this on the Graphics Processing Unit (GPU) and compare performance with an efficient software only implementation using the Central Processing Unit (CPU).

Keywords: X-ray simulation, GPU-based volume rendering, Interventional radiology

We present a simulator for guided needle puncture procedures. Our aim is to provide an effective training tool for students in interventional radiology (IR) using actual patient data and force feedback within an immersive virtual environment (VE). Training of the visual and motor skills required in IR is an apprenticeship which still consists of close supervision using the model: (i) see one, (ii) do one, and (iii) teach one. Training in patients not only has discomfort associated with it, but provides limited access to training scenarios, and makes it difficult to train in a time efficient manner. Currently, the majority of commercial products implementing a medical VE still focus on laparoscopy where eye-hand coordination and sensation are key issues. IR procedures, however, are far more reliant on the sense of touch. Needle guidance using ultrasound or computed tomography (CT) images is also widely used. Both of these are areas that have not been fully addressed by other medical VEs. This paper provides details of how we are developing an effective needle guidance simulator. The project is a multi-disciplinary collaboration involving practising interventional radiologists and computer scientists.

Keywords: Interventional radiology; Virtual environments; Needle puncture; Haptics

The medical domain offers many excellent opportunities for the application of computer graphics, visualization, and virtual environments, offering the potential to help improve healthcare and bring benefits to patients. This report provides a comprehensive overview of the state-of-the-art in this exciting field. It has been written from the perspective of both computer scientists and practicing clinicians and documents past and current successes together with the challenges that lie ahead. The report begins with a description of the commonly used imaging modalities and then details the software algorithms and hardware that allows visualization of and interaction with this data. Example applications from research projects and commercially available products are listed, including educational tools; diagnostic aids; virtual endoscopy; planning aids; guidance aids; skills training; computer augmented reality; and robotics. The final section of the report summarises the current issues and looks ahead to future developments.

Keywords: Augmented and virtual realities, Computer Graphics, Health, Physically based modelling, Medical Sciences, Simulation, Virtual device interfaces

Purpose: We propose a fast software library implemented on graphics processing unit (GPU) to compute digitally reconstructed radiographs (DRRs). It takes into account first order Compton scattering.
Methods: The simulation is based on the evaluation of the Beer‐Lambert law and of the Klein‐Nishina equation. The algorithm is fully determinist and has been fully implemented on GPU to achieve clinically acceptable efficiency. A full resolution simulation is performed for primary radiation. A much lower image resolution is used for Compton scattering as it adds a low frequency pattern over the projection image. Each voxel of the CT dataset is considered as a secondary source. The number of photons that reach each voxel is evaluated. Then, for each secondary source, a projection image is computed and integrated in the final image. The photon energy between each secondary source and each pixel is also computed. An interlaced sampling mode is also proposed to further reduce the computation time without sacrificing numerical accuracy. Finally, the speed and accuracy are assessed.
Results: We show that the computations can be fully implemented on the GPU with an original under‐sampling method to produce clinically acceptable results. For example, a simulation can be achieved in less than 7 seconds whilst the maximum relative error remains below 5% and the average relative error below 1.4%. At full resolution, a speed‐up by factor ∼12X is achieved for the GPU implementation with our interlaced‐mode by comparison with our multi‐threaded CPU implementation using 8 threads in parallel.
Conclusions: DRR calculation with scatter is computationally intensive. The use of GPU can achieve clinically acceptable efficiency. A Compton fluence map can be computed in a few seconds using under‐sampling, whilst keeping numerical inaccuracies relatively low. This work can be used for CBCT reconstruction to reduce scatter artifacts.

Purpose: We propose an evolutionary approach for image reconstruction in nuclear medicine. Our method is based on a cooperative coevolution strategy (also called Parisian evolution): the “fly algorithm”.
Method and Materials: Each individual, or fly, corresponds to a 3D point that mimics a radioactive emitter, i.e. a stochastic simulation of annihilation events is performed to compute the fly's illumination pattern. For each annihilation, a photon is emitted in a random direction, and a second photon is emitted in the opposite direction. The line between two detected photons is called line of response (LOR). If both photons are detected by the scanner, the fly's illumination pattern is updated. The LORs of every fly are aggregated to form the population total illumination pattern. Using genetic operations to optimize the position of positrons, the population of flies evolves so that the population total pattern matches measured data. The final population of flies approximates the radioactivity concentration.
Results: We have developed numerical phantom models to assess the reconstruction algorithm. To date, no scattering and no tissue attenuation have been considered. Whilst this is not physically correct, it allows us to test and validate our approach in the simplest cases. Preliminary results show the validity of this approach in both 2D and fully‐3D modes. In particular, the size of objects, and their relative concentrations can be retrieved in the 2D mode. In fully‐3D, complex shapes can be reconstructed.
Conclusions: An evolutionary approach for PET reconstruction has been proposed and validated using simple test cases. Further work will therefore include the use of more realistic input data (including random events and scattering), which will finally lead to implement the correction of scattering within our algorithm. A comparison study against ML‐EM and/or OS‐EM methods will also need to be conducted.

Purpose: We previously proposed to compute the X‐ray attenuation from polygons directly on the GPU, using OpenGL, to significantly increase performance without loss of accuracy. The method has been deployed into a training simulator for percutaneous transhepatic cholangiography. The simulations were however restricted to monochromatic X‐rays using a point source. They now take into account both the geometrical blur and polychromatic X‐rays.
Method and Materials: To implement the Beer‐Lambert law with a polychromatic beam, additional loops have been included in the simulation pipeline. It is split into rendering passes and uses frame buffer objects to store intermediate results. The source shape is modeled using a variable number of point sources and the incident beam is split into discrete energy channels. The respiration model is composed of ribs, spine, lungs, liver, diaphragm and the external skin. The organ motion simulation is based on anatomical and physiological studies: the model is monitored by two independent active components: the ribs with a kinematics law and the diaphragm tendon with an up and down translation. Other soft‐tissue components are passively deformed using a 3D extension of the ChainMail algorithm. The respiration rate is also tunable to modify the respiratory profile.
Results: We have extended the simulation pipeline to take into account focal spots that cause geometric unsharpness and polychromatic X‐rays, and dynamic polygon meshes of a breathing patient can be used as input data.
Conclusions: X‐ray transmission images can be fully simulated on the GPU, by using the Beer‐Lambert law with polychromatism and taking into account the shape of the source. The respiration of the patient can be modeled to produce dynamic meshes. This is a useful development to improve the level of realism in simulations, when it is needed to retain both speed and accuracy.

Keywords: Interventional radiology, Virtual environments, Respiration simulation, X-ray simulation, Needle puncture, Haptics, Task analysis

We use the Fly algorithm, an artificial evolution strategy, to reconstruct positron emission tomography (PET) images. The algorithm iteratively optimises the position of 3D points. It eventually produces a point cloud, which needs to be voxelised to produce volume data that can be used with conventional medical image software. However, resulting voxel data is noisy. In our test case with 6,400 points the normalised cross-correlation (NCC) between the reference and the reconstruction is 85.53%; with 25,600 points it is 93.60%. This paper introduces a more robust 3D voxelisation method based on implicit modelling using metaballs to overcome this limitation. With metaballs, the NCC with 6,400 points increases up to 92.21%; and up to 96.26% with 25,600 points.

We propose a simulation framework to simulate the computed tomography acquisition process. It includes five components: anatomic data, respiration modelling, automatic parametrisation, X-ray simulation, and tomography reconstruction. It is used to generate motion artefacts in reconstructed CT volumes. Our framework can be used to evaluate CT reconstruction algorithm with motion artefact correction in a controlled environment.

Haptics technologies are frequently used in virtual environments to allow participants to touch virtual objects. Medical applications are no exception and a wide variety of commercial and bespoke haptics hardware solutions have been employed to aid in the simulation of medical procedures. Intuitively the use of haptics will improve the training of the task. However, little evidence has been published to prove that this is indeed the case. In the paper we summarise the available evidence and use a case study from interventional radiology to discuss the question of how important is it to touch medical virtual environments?

Keywords: Haptics, virtual environments, touch

This paper presents preliminary results of a novel method that takes advantage of artificial evolution for positron emission tomography (PET) reconstruction. Fully 3D tomographic reconstruction in PET requires high computing power and leads to many challenges. To date, the use of such methods is still restricted due to the heavy computing power needed. Evolutionary algorithms have proven to be efficient optimisation techniques in various domains. However the use of evolutionary computation in tomographic reconstruction has been largely overlooked. We propose a computer-based algorithm for fully 3D reconstruction in PET based on artificial evolution and evaluate its relevance.

Keywords: Positron emission tomography, genetic algorithms, optimization methods

Medical visualization in a hospital can be used to aid training, diagnosis, and pre- and intra-operative planning. In such an application, a virtual representation of a patient is needed that is interactive, can be viewed in three dimensions (3D), and simulates physiological processes that change over time. This paper highlights some of the computational challenges of implementing a real time simulation of a virtual patient, when accuracy can be traded-off against speed. Illustrations are provided using projects from our research based on Grid-based visualization, through to use of the Graphics Processing Unit (GPU).

Keywords: Medical visualization, virtual environment, Grid, GPU

In this paper, we propose to take advantage of computer graphics hardware to achieve an accelerated simulation of X-ray transmission imaging, and we compare results with a fast and robust software-only implementation. The running times of the GPU and CPU implementations are compared in different test cases. The results show that the GPU implementation with full floating point precision is faster by a factor of about 60 to 65 than the CPU implementation, without any significant loss of accuracy. The increase in performance achieved with GPU calculations opens up new perspectives. Notably, it paves the way for physically-realistic simulation of X-ray imaging in interactive time.

Keywords: Physically based modeling, Raytracing, Physics

KEY LEARNING OBJECTIVES: To determine face and content validity of a physics-based virtual reality (VR) training simulation of visceral interventional radiology needle puncture procedures.
DESCRIPTION: Imaging-guided needle puncture procedures use hand-eye coordination to direct needles, wires and catheters to perform nephrostomy. The visuo-spatial and manipulation skills required are learnt in a traditional apprenticeship, though Working Time Directives are reducing the time and case mix available to train. Animal and fixed models reproduce some training objectives, though they are an imperfect substitute for the `real patient' experience. ImaGiNe-S is a computer-based VR training simulation, using variable virtual environments with stereo 3D visual representation and devices to convey feel, realistically mimicking a percutaneous nephrostomy procedure. With ethical approval, a prospective pilot study was conducted at two international conferences to assess validity of Imagine-S. 53 subjects (49 male, 4 female: 30 trainees and 23 subject matter experts), underwent baseline testing on a simulated percutaneous nephrostomy. Face and content validation were assessed using a 5-point Likert scale. Outcomes showed that 41/53 (78%) participants thought that the design of Imagine-S was moderately realistic with content validity being rated averagely for all critical task steps. 44/53 (83%) participants thought that Imagine-S is a useful model for training skills for nephrostomy.
CONCLUSION: Imagine-S may be a useful model for training skills for nephrostomy. With further development it may allow trainees to develop basic skills of percutaneous renal collecting system access. Further assessment of face and content validity is needed.

PURPOSE-MATERIALS: To use patient imaging as the basis for developing virtual environments (VE).
BACKGROUND: Interventional radiology basic skills are still taught in an apprenticeship in patients, though these could be learnt in high fidelity simulations using VE. Ideally, imaging data sets for simulation of image-guided procedures would alter dynamically in response to deformation forces such as respiration and needle insertion. We describe a methodology for deriving such dynamic volume rendering from patient imaging data.
METHODS: With patient consent, selected, routine imaging (computed tomography, magnetic resonance, ultrasound) of straightforward and complex anatomy and pathology was anonymised and uploaded to a repository at Bangor University. Computer scientists used interactive segmentation processes to label target anatomy for creation of a surface (triangular) and volume (tetrahedral) mesh. Computer modeling techniques used a mass spring algorithm to map tissue deformations such as needle insertion and intrinsic motion (e.g. respiration). These methods, in conjunction with a haptic device, provide output forces in real time to mimick the ‘feel’ of a procedure. Feedback from trainees and practitioners was obtained during preliminary demonstrations.
RESULTS: Data sets were derived from 6 patients and converted into deformable VEs. Preliminary content validation studies of a framework developed for training on liver biopsy procedures, demonstrated favourable observations that are leading to further revisions, including implementation of an immersive VE.
CONCLUSION: It is possible to develop dynamic volume renderings from static patient data sets and these are likely to form the basis of future simulations for IR training of procedural interventions.

Computer software was created to simulate the process of administering an x-ray, from the initial positioning of patient, x-ray source and cassette, to the resulting image. Thanks to this approach patient exposure is no longer necessary for training and research. Two programs have already been created: one for research and another for teaching purposes

The potential for the use of computer graphics in medicine has been well established. An important emerging area is the provision of training tools for interventional radiology (IR) procedures. These are minimally invasive, targeted treatments performed using imaging for guidance. Training of the skills required in IR is an apprenticeship which still consists of close supervision using the model i) see one, ii) do one and iii) teach one. Simulations of guidewire and catheter insertion for IR are already commercially available. However, training of needle guidance using ultrasound (US), fluoroscopic or computed tomography (CT) images - the first step in approximately half of all IR procedures - has been largely overlooked and we have developed a simulator, called BIGNePSi, to provide training for this commonly performed procedure.

This thesis is devoted to the development of novel techniques to provide an integrated visual-haptic system for the simulation of US guided needle puncture using patient specific data with 3D textures and volume haptics. The result is the realization of a cost effective training tool, using off-the-shelf components (visual displays, haptic devices and working stations), that delivers a high fidelity training experience.

We demonstrate that the proxy-based haptic rendering method can be extended to use volumetric data so that the trainee can feel underlying structures, such as ribs and bones, whilst scanning the surface of the body with a virtual US transducer. A volume haptic model is also proposed that implements an effective model of needle puncture that can be modulated by using actual force measurements. A method of approximating US-like images from CT data sets is also described. We also demonstrate how to exploit today's graphics cards to achieve physically-based simulation of x-ray images using GPU programming and 3D texture hardware. We also demonstrate how to use GPU programming to modify, at interactive framerates, the content of 3D textures to include the needle shaft and also to artificially add a tissue lesion into the dataset of a specific patient. This enables the clinician to provide students with a wide variety of training scenarios.

Validation of the simulator is critical to its eventual uptake in a training curriculum and a project such as this cannot be undertaken without close co-operation with the domain experts. Hence this project has been undertaken within a multi-disciplinary collaboration involving practising interventional radiologists and computer scientists of the Collaborators in Radiological Interventional Virtual Environments (CRaIVE) consortium. The cognitive task analysis (CTA) for freehand US guided biopsy performed by our psychologist partners has been extensively used to guide the design of the simulator. In addition, to ensure that the fidelity of the simulator is at an acceptable level, clinical validation of the system's content has been carried out at each development stage. In further, objective evaluations, questionnaires were developed to evaluate the features and the performances of the simulator. These were distributed to trainees and experts at different workshops. Many suggestions for improvements were collected and subsequently integrated into the simulator.

This work presents a method for modelling the response of X-ray detectors applied to remove artefacts in tomography. On some reconstructed volumes by tomography using synchrotron radiations at ESRF, dark line artefacts (under-estimation of linear attenuation coefficients) appear when high density material are aligned. The causes of these artefacts have been determined using experimental and simulation methods; then simulated artefacts were removed. Finally two different causes are highlighted in this study. One of them is the impulse response of the used detector, the Frelon camera of ID19 beamline. An iterative fixed point algorithm has been used successfully to remove simulated artefacts on tomographic slices.

Keywords: tomography; X-ray; detectors response modelling; artefacts; simulation; deconvolution

This project presents the GUI for a radiographer's training tool. It is one of the two parts of a project idea proposed by Senior Lecturer, Philip Cosson, from the School of Health and Social Care at the University of Teesside. His wish was to develop a program, which would allow students to train themselves to take X-Ray images without exposing patients to X-rays. It has been divided into two different projects, the GUI and the X-Ray rendering. There are two parts to the GUI system, a 3D reconstruction and the setting of the radiography parameters via the GUI. Volumetric data, obtained by MR or CT scanners, is stored, slice by slice, in a DICOM file, the medical imaging file standard. The Papyrus toolkit, developed at the University Hospital of Geneva, is used to read DICOMDIR files and DICOM files, which contain medical images. Before 3D reconstruction, information is extracted and a segmentation algorithm detects bones and skin on the different images of the dataset. From these data and using the marching cube algorithm, a 3D model is created. The GUI lets users select different datasets. Users can set the position and the orientation of the 3D reconstructed objects. They are able to choose the corresponding cassette and to move the X-Ray source. The GUI communicates, via an agreed protocol, all settings of the scene to the other part of the project, the X-Ray renderer. The GUI project is written in C++ using the WIN32 API and OpenGL.