Karim Belharet

David Folio

Antoine Ferreira
email: antoine.ferreira@ensi-bourges.fr

MRI-based Microrobotic system for the Propulsion and Navigation of Ferromagnetic Microcapsules

Keywords: Blood vessels, magnetic resonance imaging, minimally invasive interventions, real-time control

published or not. The documents may come

MRI-based microrobotic system for the propulsion and navigation of ferromagnetic microcapsules

Introduction

Microrobots designed to perform targeted therapy by navigating in the cardiovascular system are a prolific research area for minimally invasive surgeries [START_REF] Ishiyama | Magnetic micromachines for medical applications[END_REF] [START_REF] Abbott | Robotics in the small[END_REF] and treatments efficiency through early diagnosis of diseases [START_REF] Cavalcanti | Nanorobot for Brain Aneurysm[END_REF]. Cardiovascular problems are generally correlated with the obesity, human sedentary lifestyle, or hereditary characteristics. When microrobots are propelled in the body fluids, especially in the blood circulatory system, a very large number of remote locations in the human body become accessible. However, since the diameters of the blood vessels in the human body may vary from approximately 25 mm (aorta) down to 0.010 mm (capillaries), it is obvious that propelling such wireless microdevices in the human cardiovascular system with existing technologies represents a great technical challenge [START_REF] Abbott | How should microrobots swim?[END_REF]. Because the method of propulsion should allow such a microrobot to navigate through the cardiovascular system, the use of the normal blood flow itself must be considered only as a complementary means of propulsion when the travel path is in the direction of the blood flow. These untethered microrobots have been mainly developed according to three different designs: magnetic bead pulling [START_REF] Abbott | Robotics in the small[END_REF], biomimetic flagellated robot [START_REF] Behkam | Design methodology for biomimetic propulsion of miniature swimming robots[END_REF] and magnetotactic bacteria [START_REF] Martel | Flagellated magnetotactic bacteria as controlled MRItrackable propulsion and steering systems for medical nanorobots operating in the human microvasculature[END_REF].

Furthermore, navigation requires observation of the scene in order either to plan the trajectory by off-line mapping, or to correct on-line the microrobot's pose error between the planned and the observed trajectory. Recently, magnetic resonance imaging (MRI)-based medical microrobotic platforms are investigated to reach locations deep in the human body while enhancing targeting efficacy using real-time navigational and trajectory control [START_REF] Felfoul | In vivo MR-tracking based on magnetic signature selective excitation[END_REF]. For the position recognition of the microrobot in the blood vessels, from the pre-operation images, 3-D path planning and route optimization solutions have been proposed. The authors in [START_REF] Sabra | Use of 3D potential field and an enhanced breath-first search algorithms for path-planning of microdevices propelled in the cardiovascular system[END_REF] proposed an breath-first search algorithms based on MR-imaging. In [START_REF]Frontier research program on biomedical robot for intravascular therapy[END_REF], Intra-Vascular Ultra-Sound (IVUS) medical imaging technique coupled to pre-operational images of CT (Computerized Tomography) renders possible 3-D navigation in blood vessels.

Based on these path-planning techniques, only explorative 2-D control strategies have been adopted so far using simple proportional-integral-derivative (PID) controller [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF]. However, stability and robustness are not ensured against important perturbations. First, pulsatile flow whose variations in waveform, amplitude, and frequency exists from one vessel to another. Second, variation of time-multiplexed sequence parameters (duty cycle of the propulsion gradients, and repetition time of the tracking sequence) produce important trajectory errors during real-time navigation. Finally, random imaging signal noise degrades the localization of the microrobot during tracking.

The main objective of this paper is to propose an automated technique based on image processing and control algorithms for path finding, reconstruction and navigation control of a ferromagnetic microrobot using an MRI system. The MRI-based control of a ferromagnetic microcapsule presented here is dedicated to macroscale navigation, which focuses in conveying the device in vessels such as arteries and arterioles. As illustration of the concept, we consider a possible way for the microrobot get into the body through the femoral artery in the leg, which is the normal access point to the circulatory system. One possible application is to locate atherosclerotic lesions in stenosed blood vessels, particularly in vasculary circulation, and treat them either chemically or pharmacologically by targeted drug delivery. Based on slice images provided by an MRI system, relevant information related to detection of blood vessels is extracted using robust Frangi vesselness filtering from the pre-operation images. Then, a set of minimal trajectory is prede-fined, using path-planning algorithms, to guide the ferromagnetic microrobot from the injection point to the tumor area through the anarchic vessel network. Based on the precomputed path, a Generalized Predictive Controller (GPC) is proposed for robust time-multiplexed navigation along a two-dimensional (2D) path in presence of pulsative flow. The simulation results suggest the validation of the proposed image processing and control algorithms. A series of disturbances introduced in the presence and absence of closed-loop control affirms the robustness and effectiveness of this predictive control system.

Methods

MRI-based Microrobotic System Overview

The Magnetic Resonant Imaging (MRI)-based microrobotic system is used here for propulsion and navigation of the micro-device. The propulsion of the ferromagnetic microcapsule in the cardiovascular system is realized through the induction of force from magnetic gradients provided by the MRI. This MRI system will guide the microcapsule in vivo through vascular networks to a targeted area. MRI-guided microrobotic systems aim at diagnosing and treating diseases in cells, organs or vessels. Their proper function relies on providing engineering and scientific solutions in three technical challenges:

• Enhanced diagnostics: MRI is an advanced imaging system that provides 3D visualization, offering the radiologists a detailed three-dimensional view of the tissue or organ of interest. Microrobotic systems are detectable by MRI without creating artifacts.

• In-vivo propulsion and navigation: The MRI system is employed for propulsion and navigation of the microcapsules. The propulsion of a micro or nano-capsule with magnetic properties in the cardiovasular system is realized through the induction of forces and torques by magnetic gradients and magnetic fields respectively, generated by the MRI coils. The microcapsules are guided in-vivo to the targeted organs or are accumulated to the tumors' capillary networks. Also, the MRI forces retain the microcapsules at the target site.

• Drug delivery and release: The magnetic microcapsules are loaded with drug molecules. Moreover, their surface is chemically processed (coated with polymers and bioconjugated with specific antibodies) so that on one hand they are not detected by the immune system and on the other hand they have increased chances to bind to the receptors of malignant cells. When the microcapsules are inside the cell or at its vicinity, the release of the drug is triggered.

The overview of the software system architecture is given in Fig. 1. (i) The graphical user interface module, which comprises input command prompt, 3D-visualization, and process supervision tools. (ii) The control module, which comprises (a) the high-level controller responsible for the microcapsule navigation tasks and for the generation of the magnetic field gradients and (b) the low-level controller (manufacturer MRI controller) responsible for implementing the actuation commands for the generation of the desired field gradients and for the image acquisition tasks.

Then, (iii) the controlled hardware, which comprises (a) the MRI hardware and software systems and (b) the microcapsules that have been injected within the vasculature and are navigated by the field gradients. Finally, (iv) the image processing module, which comprises the (a) MRI image reconstruction and (b) the imageprocessing software that estimates the position and accumulation of the microcapsules within the vasculature, the tissues, and the organs of the human.

Finding Endovascular Navigation Path

In our context, the problem of finding the navigation path within the MRI data can be formulated as finding the correct way through the data which follows the vessel of interest between its start and end point. Finding a navigation path within the vessel network is then an essential, primary, and important step which must be addressed prior to the control procedure. The problem of vessels extraction has received considerable attention in the computer vision and medical imaging communities [START_REF] Kirbas | A review of vessel extraction techniques and algorithms[END_REF]. Hence, several class of methods have been proposed to find a path from a set of medical imaging, such as using tracking methods [START_REF] Reuzé | A 3D moment based approach for blood vessel detection and quantification in MRA[END_REF] [7] [START_REF] Tokuda | Integrated navigation and control software system for mri-guided robotic prostate interventions[END_REF], path extraction methods [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF][15] [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF], and so on. Most works based on in vivo MR-tracking methods usually need many user-defined way points as the input of a controller module for the navigation computation. A major drawback in general remains when the user must define many points (e.g. way or fiducial points) manually. Hence, for a complex structure (e.g. colon, small vessels. . . ) the required interactivity can be very tedious. As consequence, if the path is not correctly build, it can cross an anatomical wall during the in vivo navigation. In opposition, minimal path extraction approaches depend only on the manual definition of the start and end points of the desired vascular path. Therefore, we propose in this work to use path extraction technique to find the desired path to be followed in the vessel network.

The path extraction is useful for a range of application domains including medical image analysis, robot navigation, and artificial intelligence. The problem of finding the trajectory in the imaging data can be defined as finding the correct path through the data that follows the vessel of interest between its start and end point. The minimal path technique has many advantages. It needs a very simple initialisation and leads to global minimum of a snake-like energy, thus avoiding local minima.

Moreover it is fast and accurate. This minimal path problem has been studied for ages by mathematicians, and has been solved numerically using graph theory or dynamic programming. Several authors have addressed the minimal path extraction approaches. For instance, Cohen and Kimmel [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF] solved the minimal path problem in 2D with a front propagation equation between the two fixed end points, using the Eikonal equation (that physically models wave-light propagation), with a given initial front. Wink et al. [START_REF] Wink | Minimum cost path determination using a simple heuristic function[END_REF] explored different methods to determine the minimum cost path through a pre-defined cost image, for extraction of vessel centrelines from medical image data. Among them are Dijikstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], the A algorithm [START_REF] Pearl | Heuristics: intelligent search strategies for computer problem solving[END_REF], which makes use of additional heuristics to steer the search process, and wave front propagation analysis [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF]. Early, Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] explore the use of Fast Marching Method (FMM) to extract minimal paths. This method relies on the fact that the gradient of the FMM arrival function has only one local minimum, with is guaranteed to be global minimum [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF]. Therefore the minimal path can be extracted by back-propagating from given seed (corresponding to the end point of the desired path) to the starting point implicitly embedded in the arrival function. In this work the FMM is adopted to design a set of trajectory to guide the microdevice from the injection point to the tumor area through the vessel network. Our aim is to focus on the automation of the path construction, reducing the need of interaction and improving performance, in a robust way. Finally, as the proposed control strategy, presented in section 3.2, is designed for 2D navigation problem, we have limited our path extraction procedure to 2D application.

Path Extraction Results

The FMM algorithm, introduced by Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] is applied here to extract a targeted navigation path within the vessel network. The FMM is very closely related to Dijkstra's method [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], which is a very well-known method from the 1950's for computing the shortest path on a network. Hence, from the set of MRI data we have first to compute a speed map (ie. a weighting image map), which must enhance the relevant intravascular network. Choosing an appropriate and efficient image cost function is the most difficult part of the entire process. The definition of the optimal speed function is case dependent and should be set by the user, along with the start and end points of the path. Hence, an optimal path could be found only if the optimal cost function is provided. In this work, we focus mainly on finding a minimal path allowing reaching the targeted zone.

We describe in the sequel presented in Fig. 2, the process used to extract naviga- tion path. First, we need a relevant cost function which allow to enhance vessel in the image. To this aim we use some a priori knowledge about vessel shape and intensity in MRI data (see Fig. 3). Vessels are expected to appear as bright tubular structures in a darker environment. One way to account for the varying size of vessels is by multiscale analysis. It allows us to detect structures of different sizes according to the scale at which they give maximal response. In this context, a typical speed image is produced by using a Frangi vesselness filter [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF] which uses the eigenvectors of the Hessian matrix at each voxel of the image to compute the likeliness of an image region to vessels. This mapping is selected in such a way that vessels regions will have higher speed (high level in speed image, see Fig. 3). Once the speed map is generated, the user has to select a start and end points (ie. seed points) in the viewer of the input original image. The FFM will then propagate a front from the start seed and traveling to the targeted area, thanks to the speed map.

This step allow to build an image of distance between the start seed and all other pixels. The corresponding shortest path is then traced thanks to the distance map.

We have applied the described approach on some representative MRI data which validate our image processing pipeline. The application is to locate atherosclerotic lesions in stenosed blood vessels, particularly in vascular circulation. We consider that the microrobot get into the body through the femoral artery in the leg, and treat them pharmacologically, by tageted drug delivery (see Fig. 3). Let us also notice that the proposed image processing pipeline (see Fig. 2) could be applied to 3D MRI data, and then provide 3D navigation path. A MRI system generates slice images sequentially of a specific zone. Due to the fact that the body is in motion, there may be discontinuities between two images generated by these motion artifacts. In order to setup a 3D volume of the images, the images are parsed and relevant information is extracted. Once the images are reconstructed, the 3D data structures and filters may be applied to the whole volume. Applying the proposed image processing pipeline, 3D navigation path extraction is rendered possible. The Fig. 4 shows the 3D navigation path extraction processing steps. A close view of all possible paths along the blood vessel network is presented in Fig. 5.

CONTROL DESIGN

Problem formulation

Endovasular navigation requires observation of the scene in order either to plan the trajectory by off-line mapping, or to correct online the microrobot's pose error between the planned and the observed trajectory. To insure a smooth conveyance of the microcapsule to destination, collisions and the risk to be trapped by the endothelium, optimal navigation performance will be affected by external perturbations and MRI technological constraints:

• Nonnegligible pulsatile flow, whose variations in waveform, amplitude, and frequency exist from one vessel to another (such as arteries and arterioles).

• Magnetic gradients are used both for observation and control purposes in a timemultiplexed sequence. It requires different trade-offs in terms of refresh rate, duty cycle of the propulsion gradients, and repetition time of the tracking sequence.

• MRI overheating avoidance leading to limitations on the MRI duty cycle, tends to increase the disproportional scaling between magnetic forces used for control purpose and perturbation forces (drag forces and net buoyancy forces).

• Limitations on the magnetic gradient amplitude in available MRI devices.

• Proper delay in the image processing algorithms that renders the navigation control unstable.

Real-Time Sequence Design

The overall concept of the in-vivo MRI-tracking system is based on the fact that both tracking and propulsion is possible with the gradient coils of the MRI system. Software based upgrading of a clinical MRI system is the least expensive approach to convert a platform that is used for imaging to an effective interventional platform. At any instant only of the functions could be applied (i.e. either tracking or propulsion), but both will be executed over the same MRI interface.

The MRI interface has therefore to be shared and a time-division-multiple-access scheme for it has to be developed. Fig. 6 shows an overview of the real-time sequence with time-multiplexed positioning and propulsion phases introduced by Martel et al. [START_REF] Felfoul | In vivo MR-tracking based on magnetic signature selective excitation[END_REF]. The main aspect relevant to the controller's performance is (i) the duty cycle T Prop /T s that stands for the ratio between the propulsion time and the time between two successive position requests, and (ii) the synchronization event delay T sync that stands for the minimum time allowed for image processing and real-time control feedback. First, the duty cycle should be adapted to apply sufficient magnetic propulsion gradients during a predefined propulsion time T Prop to prevent the microrobot from drifting away from the trajectory. Second, a large time delay T sync produces oscillations as the microrobot approaches the reference trajectory leading to position instabilities. Such limitations have been pointed out by Mathieu et al. [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF] when implementing simple proportional-integral-derivative (PID) controller.

We proposed a navigation Generalized Predictive Controller (GPC) including microrobot's motion and dynamics with estimation of the pulsative blood flow and time-multiplexed positioning. A predictive trajectory-tracking control consider a prediction window varying typically from 10 to 50 sampling intervals. The propulsion phase starts during T Prop seconds at the same initial condition as the prediction phase, recording the performance of the system according to a prediction horizon.

After this phase the system ends after a imaging-propulsion sequence at a final position q which is set as the new initial condition of the next prediction output q.

The proposed navigation based predictive controller offers stability by design and allows the designer to trade-off performance for (computation) speed, stability margins according to the MRI application and technological requirements outlined in section 3.1.

Model description

The linear model that was used in this work, derived from the nonlinear model developed in a previous study [START_REF] Arcèse | Nonlinear modeling and robust controllerobserver for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF]. In [START_REF] Arcèse | Nonlinear modeling and robust controllerobserver for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF], we used this model to combine the backstepping controller and high gain observer in order to control the trajectory of microrobot inside a vessel using the MRI gradients.

The different forces acting on the microrobot are (see figure 7 apparent weight -→ W a and magnetic force -→ F m . The application of Newton's third law and the projection on the -→ x -axis and -→ y -axis leads to:

           m ẍ = - → F dx + - → F mx m ÿ = - → F dy + - → F my + - → W a ( 1
)
where m is the mass of the microrobot.

Let - → v = (v f x , v f x )

Generalized Predictive Control (GPC)

Generalized Predictive Control (GPC) belongs to the class of Model Predictive Control (MPC) techniques and was first introduced by Clarck et al. [START_REF] Clarke | Generalized predictive control -Part I. The Basic algorithm[END_REF][START_REF]Generalized predictive control -part II. Extensions and interpretations[END_REF]. GPC approach is a popular control predictive method, experienced on number various applications [START_REF] Mahfouf | Generalised predictive control and bioengineering, ser. Systems and Control[END_REF] [START_REF] Huang | Applied predictive control, ser. Advances in Industrial Control[END_REF], especially in industrial process [START_REF] Qin | A survey of industrial model predictive control technology[END_REF]. It combines the prediction of future behavior of the system with feedback control (see figure 8). A process model is explicitly used to predict the future behavior of the system over the given time horizon. From this prediction, a control is computed by minimizing a quadratic cost function.

MIMO GPC Scheme

The system is modeled using the model Controlled Auto-Regressive Integrated Moving-Average (CARIMA) with integrator form, that is [START_REF] Clarke | Generalized predictive control -Part I. The Basic algorithm[END_REF]:

A(z -1 )q(t) = B(z -1 )u(t -1) +C(z -1 ) ζ (t) ∆(z -1 ) , (5)
where ∆(z -1 ) = 1z -1 define the difference operator; ζ (t) is a zero mean white noise; and A(z -1 ), B(z -1 ) and C(z -1 ) are polynomial matrix in the backward shift operator z -1 , for order n A , n B , n C we get:

A(z -1 ) = 1 + a 1 z -1 + . . . + a n z -n A B(z -1 ) = 1 + b 1 z -1 + . . . + b n z -n B C(z -1 ) = 1 + c 1 z -1 + . . . + c n z -n C (6)
The GPC control strategy is obtained by minimizing a weighted sum of square predicted future errors and square control signal increments:

J {N 1 ,N 2 ,N u ,λ } = N 2 ∑ j=N 1 ( y(t + j) -w(t + j)) 2 + λ N u ∑ j=1 ∆u 2 (t + j -1) (7)
where y t+ j is the optimum predicted output of the system at time t + j; w t+ j is the future reference; N 1 and N 2 are the minimum and the maximum of the prediction horizon. N u is the control horizon; and λ > 0 is the control increment weighting.

N 1 , N 2 , N u and λ are the design parameters of the GPC.

The optimal predictor built from the measured output data up to time t and any given u(t + j) for j > 1 is:

q = G u + f(z -1 )q(t) + h(z -1 )∆u(t -1) (8)
where f(z -1 ) and h(z -1 ) are the polynomial calculated by solving the Diophantine equations:

           A(z -1 )J j (z -1 )∆(z -1 ) + z -1 F j (z -1 ) = 1 B(z -1 )J j (z -1 ) = G j (z -1 ) + z -1 H j (z -1 ) f = F N 1 (z -1 ) . . . F N 2 (z -1 ) T h = H N 1 (z -1 ) . . . H N 2 (z -1 ) T u = [∆u(t) . . . ∆u(t + N u -1)] T q = [ q(t + N 1 ) . . . q(t + N 2 )] T G =                 g N 1 N 1 g N 1 N 1 -1 . . . g N 1 +1 N 1 +1 g N 1 +1 N 1 . . . . . . . . . g N 2 N 2 g N 2 N 2 -1 . . . g N 2 N 2 -N u +1                 (9)
where G j represents the future; F j and H j define respectively the present and the past; and J j is related to the disturbance.

Hence, the optimal control is defined by: u = M wf(z -1 )q(t) -h(z -1 )∆u(t -1) [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF] with w = [w(t + N 1 ) . . . w(t

+ N 2 )]; M = QG T with dimension N u × (N 2 -N 1 + 1); and Q = G T G + λ I N u -1 with dimension N u × N u .
Only the first element of u is applied to the system, that is:

∆u Opt (t) = m T 1 w -f(z -1 )q(t) -h(z -1 )∆u(t -1) (11)
where m T 1 is the first row of M.

Classically a RST polynomial structure is introduced at the end to determine a relation between the output q(t), the control signal u(t) and the setpoint w(t), according to the scheme of Fig. 8. The advantage of RST polynomial structure is that on the other hand offers the possibility to analyze the stability of the controlled open loop in the frequency domain. In fact, this off-line operation is a very helpful strategy to determine the stable set of tuning parameters just before applying the control law on the real system. Hence the above control law [START_REF] Kirbas | A review of vessel extraction techniques and algorithms[END_REF] can be rewritten in a RST polynomial form:

S(z -1 )∆(z -1 )u(t) = T (z -1 )w(t) -R(z -1 )q(t) (12)

GPC implementation

In order to design the GPC controller the transfer functions of the two subsystems (S x ) and (S y ) of Eq.( 4) are obtained:

H x (s) = 243.8 s 2 + 49.25s (13)
H y (s) = 243.8 s 2 + 79.77s [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF] The GPC controller under RST polynomial form requires tuning of the set parameters N 1 , N 2 , N u and λ to ensure good stability. Some guidelines may be found in the literature [START_REF] Boucher | ser. Collection Mthodes et Pratiques de l?Ingnieur[END_REF]. For this process, two independent GPC controllers has been designed for a sampling period of T s = 50 ms, satisfying stability and robustness features [START_REF] Boucher | ser. Collection Mthodes et Pratiques de l?Ingnieur[END_REF], with the tuning parameters:

N 1 = 1; N 2 = 4; N u = 1; λ x = 0.77, λ y = 0.34 (15)
According to these parameters, the model of the process using ( 13) and ( 14) in

(S x )            A x (z -1 ) = 1 -1.085z -1 + 0.085z -2 B x (z -1 ) = 0.155 + 0.071z -1 , (16)
(S y )            A y (z -1 ) = 1 -1.018z -1 + 0.018z -2 B y (z -1 ) = 0.115 + 0.034z -1 , (17)
and where C x (z -1 ) and C y (z -1 ) are set to 1.

The RST form optimal control is:

∆u Opt x (t)S x (z -1 ) = -R x (z -1 )q x (t) + T x (z -1 )w x (t) (18)
∆u Opt y (t)S y (z -1 ) = -R y (z -1 )q y (t) + T y (z -1 )w y (t)

with

                     R x (z -1 ) = 2.855 -2.222z -1 + 0.169z -2 S x (z -1 ) = 1 + 0.140z -1 T x (z -1 ) = 0.123z + 0.273z 2 + 0.405z 3 (20)                      R y (z -1 ) = 4.0.61 -2.906z -1 + 0.052z -2 S y (z -1 ) = 1 + 0.098z -1
T y (z -1 ) = 0.206z + 0.410z 2 + 0.592z 3 (21)

Simulation Results

Simulations are conducted within the scope of actual commonly spread MRI system abilities. At the moment, MRI systems are able to generate magnetic gradients with an intensity of some tens of mT.m -1 . Let us note that this limitation is additionally affected by the gradient coils duty cycle and by the multiplexing needed both for controlling and observing. In order to make sure that the amplitude of the control inputs remains bounded by physical actuators limits u i,max and to protect the system, we perform a simple time scaling. Thus, the applied control law is given by u i k(t) , with k(t) =max{1, Figure 9 presents the trajectories followed by the microrobot, and the relative error between the current position q and the reference path w. As one can see the system output follows correctly the reference trajectory w for each considered time horizon. The output of the closed loop system is dependent on the setting parameters of the GPC. The previous curves show the impact of the prediction horizon N for the controlled system. Moreover, comparing both plots, the nature of anticipation of the GPC scheme is illustrated by -greater is N more is anticipated the path behavior-.

Hence, a great value of N does not necessarily guarantee good performance, and generally increase the complexity of the scheme. To evaluate the efficiency of the proposed MRI-based predictive controller, we added a white Gaussian noise on the system output measure q. Fig. 10 shows the system response in the presence of this disturbance on the system. Globally, tracking is not too much affected by the noise, since position standard deviation (std) and root mean square (RMS) error are quite satisfactory (see Table 1). We validated the proposed control strategy on 2D endovascular navigation path extracted from MRI-data with the method presented in section III.4. As shown in Fig. 11, the system output q follows perfectly the reference trajectory w without (cf.

Figure 1 .

 1 Figure 1. Overall MRI-based microbotic system for steering and navigation of ferromagnetic microcapsules.

Figure 2 .

 2 Figure 2. Image processing pipeline.

Figure 3 . 2 -

 32 Figure 3. 2-D Navigation path extraction processing of atherosclerotic lesions in the upper right leg: a) Original MRI data; b) Computed cost function using Frangi vesselness filter (light pixel have higher weight); c) FFM propagation to build the distance to targeted seed map; d) Computed navigation path between the start and end seeds.

Figure 4 .

 4 Figure 4. 3-D Navigation path extraction processing of atherosclerotic lesions in the upper right. leg.

Figure 5 .

 5 Figure 5. Path extraction in blood vessel network of upper right leg.

Figure 6 .

 6 Figure 6. Timeline of acquisition and control prediction.

Figure 7 .

 7 Figure 7. Forces applied on microrobot.

Figure 8 .

 8 Figure 8. Navigation based-Generalized Predictive Control (GPC) strategy..

  u i u i,max }. The set of simulations corresponds to microcapsule's radius of 300 µm and a time scaling settled at k(t) = 0.55. Different situations are considered in this section to illustrate and validate the performance and robustness of the proposed MRI-based predictive controller shown on Fig. 8. As the considered system is decoupled into two subsystems (S x ) and (S y ) (4), we have first to validate the control strategy onto 1D longitudinal path. As illustration, the microcapsule has to follow a sinusoidal reference trajectory (cf. Fig. 9 and 10) for different time horizons N = N 2 -N 1 (namely N = 3, 10, and 15).

Figure 9 .

 9 Figure 9. Longitudinal position microrobot control.

Figure 10 .

 10 Figure 10. Longitudinal position microrobot control with white noise.

Fig. 11 (

 11 Fig.11(a)) and with (cf. Fig.11(b)) white noise added. In particular, the microrobot is able to converge quickly towards the navigation path, in spite of a large gap between the injection point and the starting of reference path w (about 50 pixels).

Fig. 12 describes

 12 Fig.12describes the error evolution in both cases. Once again the error remains small with low values of std and RMS parameters. Let us notice that these 2D error statistics given in table 1 take into account the gap between the injection point and the initial reference path.

( a )

 a Trajecrory without noise. (b) Trajectory with white noise.

Figure 11 .

 11 Figure 11. 2D MRI-based microrobot endovascular navigation (N = 3).

Figure 12 .

 12 Figure 12. 2D trajectories tracking error (N = 3): qw .

Table 1

 1

	Error statistics
		1D navigation with noise	2D navigation
		N = 3 N = 10 N = 15 without noise with noise
	std	0.2723 0.2887 0.2976 1.0438	1.2121
	RMS 0.2753 0.3068 0.3153 1.0480	1.2306

ACKNOWLEDGMENTS

This work was supported by European Union's 7th Framework Program and its research area ICT-2007.3.6 Micro/nanosystems under the project ICT-224594 entitled NANOMA (Nano-Actuactors and Nano-Sensors for Medical Applications).

with the following parameters α i and β i , and the magnetic gradients considered as control inputs u x and u y , that is:

where ρ is the density of the fluid; η is the fluid viscosity; r is the spherical radius;

and B = (B x , B y ) T is the magnetic field generate by the MRI system.

Finally, the state space representation is deduce from (2):

where (v x , v y ) T denote the robot velocity along x-axis and y-axis. Assuming that microrobot location (x, y) can be measured thanks to the MRI system, we denote by q = (x, y) T the process measure. We can notice that system (S) can be divided into two subsystems (S x ) and (S y ), which allow us to define two independents GPC schemes to track the reference trajectory in 2D MRI data.


Piotr Bilinski

Francois Bremond

Evaluation of local descriptors for action recognition in videos

Recently, local descriptors have drawn a lot of attention as a representation method for action recognition. They are able to capture appearance and motion. They are robust to viewpoint and scale changes. They are easy to implement and quick to calculate. Moreover, they have shown to obtain good performance for action classification in videos. Over the last years, many different local spatio-temporal descriptors have been proposed. They are usually tested on different datasets and using different experimental methods. Moreover, experiments are done making assumptions that do not allow to fully evaluate descriptors. In this paper, we present a full evaluation of local spatio-temporal descriptors for action recognition in videos. Four widely used in state-of-the-art approaches descriptors and four video datasets were chosen. HOG, HOF, HOG-HOF and HOG3D were tested under a framework based on the bag-of-words model and Support Vector Machines.

Introduction

In last years, many researchers have been working on developing effective descriptors to recognize objects, scenes and human actions. Many suggested descriptors have proven to establish very good performance for action classification in videos. They are able to capture appearance and motion. They are robust to viewpoint and scale changes. Moreover, they are easy to implement and quick to calculate. For example [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF] proposed Scale-Invariant Feature Transform (SIFT) descriptor, [START_REF] Bay | SURF: Speeded Up Robust Features[END_REF] proposed Speeded Up Robust Features (SURF), [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF] proposed Histogram of Oriented Gradients (HOG) descriptor. [START_REF] Ke | PCA-SIFT: A More Distinctive Representation for Local Image Descriptors[END_REF] proposed PCA-SIFT, [START_REF] Dollar | Behavior recognition via sparse spatio-temporal features[END_REF] proposed Cuboid descriptor, [START_REF] Laptev | Learning realistic human actions from movies[END_REF] proposed Histogram of Oriented Gradients (HOG) and Histogram of Optical Flow (HOF) descriptors computed on spatiotemporal grids. [START_REF] Kläser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF] proposed a Spatio-Temporal Descriptor based on 3D Gradients (HOG3D). Although much has been done, it is not clear which descriptors are better than the others. They are usually evaluated on different datasets and using different experimental methods. Moreover, existing comparisons usually involve smaller or bigger restrictions. For example, [START_REF] Wang | Evaluation of local spatiotemporal features for action recognition[END_REF] to limit the complexity choose a subset of 100, 000 selected training features what is around 21% of all HOG-HOF descriptors and around 40% of all HOG3D descriptors computed for the KTH Dataset. Moreover, the authors make all the experiments using only one codebook size (4000). Also in [START_REF] Stöttinger | Systematic Evaluation of Spatio-temporal Features on Comparative Video Challenges[END_REF] the authors make an assumption about the codebook size (one codebook size) and evaluate descriptors on one dataset.

In this paper, we present an evaluation of local spatio-temporal features for action recognition in videos. Four widely used in the state-of-the-art approaches descriptors were chosen: HOG, HOF, HOG-HOF and HOG3D. All these descriptors are tested on the same datasets with the same split of training and testing data, and using the same identical classification method. Our evaluation framework is based on the bag-of-words approach, an approach that is very often used together with local features. Computed descriptors are quantized into visual words and videos are represented as histograms of occurrences of visual words. For action classification, non-linear Support Vector Machines (SVM) together with leave-one-out cross-validation technique are used. Our experiments are performed on several public datasets containing both low and high resolution videos recorded using static and moving camera (KTH Dataset, Weizmann Action Dataset, ADL Dataset and Keck Dataset). In contrast to other evaluations, we test all the computed descriptors, we perform evaluation on several differing in difficulty datasets and perform evaluation on several codebook sizes. We demonstrate that accuracy of evaluated descriptors depends on the codebook size and a dataset.

The paper is organized as follows. In section 2, we briefly present the main idea of our evaluation framework. Section 3, presents our experiments and obtained results. Finally, in section 4, we present our conclusion.

Evaluation Framework

Our evaluation framework is as follows. In the first step, for each video, local space-time detector is applied. For each obtained point, local space-time descriptor is computed (Section 2.1). In the second step, the bag-of-words model is used to represent actions (Section 2.2). For each video, four different codebooks and four different video representations are computed. Finally, to evaluated descriptors, the leave-one-person-out cross-validation technique and non-linear multiclass Support Vector Machine are applied (Section 2.3 and 2.4). To speed-up the evaluation process, clusters of computers are used.

Space-Time Local Features

Local spatio-temporal features are extracted for each video. As a local feature detector, the Harris3D algorithm is applied. Then, for each detected feature, four types of descriptors are computed (HOG, HOF, HOG-HOF and HOG3D). The detector and descriptors were selected based on their use in the literature and availability of the original implementation 12 . For each algorithm, the default values of parameters were used.

Harris3D [START_REF] Laptev | Space-Time Interest Points[END_REF] detector -it is proposed by Laptev and Linderberg extension of the Harris corner detector [START_REF] Harris | A Combined Corner and Edge Detector[END_REF]. The authors propose to extend the notion of spatial interest and detect local structures in space-time where the image values have significant local variations in both space and time. The authors use independent spatial and temporal scale values, a separable Gaussian smoothing function, and space-time gradients.

Histogram of Oriented Gradients (HOG) [START_REF] Laptev | Learning realistic human actions from movies[END_REF] -it is a 72-bins descriptor describing the local appearance. The authors propose to define a grid n x ×n y ×n t (default settings: 3 × 3 × 2) in the surrounding space-time area and compute for each cell of the grid 4-bins histogram of oriented gradients.

Histogram of Optical Flow (HOF) [START_REF] Laptev | Learning realistic human actions from movies[END_REF] -it is a 90-bins descriptor describing the local motion. The authors propose to define a grid n x × n y × n t (default settings: 3 × 3 × 2) around the encompassing space-time area and compute for each cell of the grid 5-bins histogram of optical flow.

HOG-HOF descriptor -it is a 162-bin descriptor combining both Histogram of Oriented Gradients and Histogram of Oriented Flow descriptors.

Spatio-Temporal Descriptor based on 3D Gradients (HOG3D) -it is a 300-bins descriptor proposed by Klaser et al. [START_REF] Kläser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF]. It is based on orientation histograms of 3D gradients. The authors propose to define a grid n x × n y × n t (default settings: 2 × 2 × 5) in the surrounding space-time area and compute for each cell of the grid 3D gradients orientations.

Bag-of-words Model

To represent videos using local features we apply common bag-of-words model. All computed descriptors for all Harris3D detected points are used in the quantization process. First of all, the k-means clustering algorithm with the Euclidean distance is used to create a codebook. Then, each video is represented as a histogram of occurrences of the codebook elements. In our experiments we use four different sizes of codebooks (1000, 2000, 3000 and 4000).

Classification

In order to perform classification, we use a multi-class non-linear Support Vector Machines using radial basis function defined by:

K(H a , H b ) = exp(-γD(H a , H b )) (1)
where both H a = {h a1 , ..., h an } and H b = {h b1 , ..., h bn } are n-bins histograms. Function D is a χ 2 distance function defined by:

D(H a , H b ) = n i=1 (h ai -h bi ) 2 h ai + h bi (2)
Such defined kernel requires two parameters: (a) trade-off between training error and margin, and (b) parameter gamma in the rbf kernel. To evaluate As a Support Vector Machine, the SVM multi-class [START_REF] Tsochantaridis | Large Margin Methods for Structured and Interdependent Output Variables[END_REF] is used (multi-class variant of SVM light [START_REF] Joachims | Making Large-Scale SVM Learning Practical[END_REF]). To speed-up the evaluation process, clusters of computers are used.

Evaluation

To evaluate selected descriptors, we use leave-one-person-out cross-validation technique (unless specified for a dataset), where videos of one actor are used as the validation data and videos from the remaining actors as the training data. This is repeated in such a way that videos from one person are used exactly once as the validation data. In our experiments we use all the descriptors calculated for all detected points to comprehensively try out the effectiveness of used local feature descriptors.

Experiments

Our experiments are performed on four different datasets: Weizmann Action Recognition Dataset (Section 3.1), KTH Dataset (Section 3.2), ADL Dataset (Section 3.3) and Keck Dataset (Section 3.4). A few sample frames from these video datasets can be found in Figure 1 and Figure 2. These datasets contain various types of videos: low and high resolution videos, recorded using static and moving camera, and containing one and many people. Information about these databases are summarized in Table 1.

Weizmann

Weizmann Action Recognition Dataset

The Weizmann Action Recognition Dataset [2, 5]3 is a low-resolution (180 × 144 pixel resolution, 50 fps) dataset of natural human actions. The dataset contains 93 video sequences showing 9 different people. The dataset contains 10 actions. The full list of actions is: run, walk, skip, jumping-jack (shortly jack), jumpforward-on-two-legs (shortly jump), jump-in-place-on-two-legs (shortly pjump), gallop-sideways (shortly side), wave-two-hands (shortly wave2), wave-one-hand (shortly wave1), and bend. Statistics about this dataset are available in table 1. Evaluation is done using leave-one-person-out cross-validation technique. Results are presented in table 2. As we can observe, all the descriptors obtain the same accuracy for codebook 2000 and 4000. In this case, the codebook of size 2000 is preferred (faster codebook computation and faster SVM classification). The HOG descriptor performs the best for codebook 2000, the HOF descriptor for codebook 3000, HOG-HOF for codebook 2000 and HOG3D descriptor for codebook 3000. According to the results, the HOG-HOF is the best descriptor for the Weizmann dataset and the HOG descriptor is the worst. Ranking is: HOG-HOF > HOF = HOG3D > HOG. The HOF descriptor obtains the same classification accuracy as HOG3D descriptor but HOF descriptor is smaller in size (90-bins descriptor instead of 300-bins). It takes less time to compute codebook and perform classification for the HOF descriptor. Kläser [START_REF] Kläser | Learning human actions in video[END_REF], employing random sampling on training features for codebook generation (codebook size 4000), obtained 75.3% accuracy for the HOG descriptor, 88.8% for the HOF descriptor, 85.6% for the HOG-HOF and 90.7% for the HOG3D descriptor. This shows that the codebook selection method has significant importance to the effectiveness of the BOW method (we obtained up to 10.72% better results). Results are presented in table 3. Both HOG and HOF descriptors perform the best for codebook 1000 and both HOG-HOF and HOG3D descriptors for codebook 3000. According to the results, the HOF descriptor is superior descriptor for the KTH dataset and again the HOG descriptor is inferior quality. Ranking is: HOF > HOG-HOF > HOG3D > HOG. Wang et al. [START_REF] Wang | Evaluation of local spatiotemporal features for action recognition[END_REF], choosing a subset of 100, 000 selected training features and using codebook size of 4000, obtained 80.9% accuracy for the HOG descriptor, 92.1% for the HOF descriptor, 91.8% for the HOG-HOF and 89% for the HOG3D descriptor. We obtain up to 4.52% better results on this dataset. Selecting only a subset of descriptors can cause loss of some important information.

ADL Dataset

The University of Rochester Activities of Daily Living (ADL) dataset [START_REF] Messing | Activity recognition using the velocity histories of tracked keypoints[END_REF] 5 is a high-resolution (1280 × 720 pixel resolution, 30 fps) video dataset of activities of daily living. The dataset contains 150 video sequences showing five different people. The dataset contains ten activities. The full list of activities is: answering a phone, dialling a phone, looking up a phone number in a telephone directory, writing a phone number on a whiteboard, drinking a glass of water, eating snack chips, peeling a banana, eating a banana, chopping a banana, and eating food with silverware. These activities were selected to be difficult to separate on the basis of single source of information (e.g. eating banana and eating snack or answering a phone and dialling a phone). These activities were each performed three times by five people differing in shapes, sizes, genders, and ethnicity. The videos were down-sampled to the spatial resolution of 640 × 360 pixels. Statistics about this dataset are available in table 1. Evaluation is done using leave-oneperson-out cross-validation technique. Results are presented in table 4. As we can observe, apart from the HOG descriptor, all the other descriptors perform the best for codebook 1000. The HOG descriptor performs the best for codebook 2000. According to the results, the HOG-HOF is the best descriptor for the ADL dataset and the HOG descriptor is again the worst. Ranking is: HOG-HOF > HOG3D > HOF > HOG. Results are presented in table 5. The HOG descriptor performs the best for codebook 3000, the HOF descriptor for codebook 4000, the HOG-HOF for codebook 2000 and the HOG3D for codebook 3000. The HOG3D is the best descriptor for the Keck dataset and the HOF descriptor is the worst. Ranking is: HOG3D > HOG-HOF > HOG > HOF. According to the obtained results, we observe that accuracy of descriptors depends on the codebook size (12.5% difference on the Keck dataset for the HOF descriptor, 7% difference on the ADL dataset for the HOG3D descriptor), codebook selection method (up to 10.72% better results comparing to [START_REF] Kläser | Learning human actions in video[END_REF] on the Weizmann dataset) and dataset (HOF descriptor obtains 95.37% on the KTH dataset but only 42.86% on the Keck dataset). Also, we observe that smaller codebook sizes (1000, 2000, 3000) are found to lead to consistently good performance across the different datasets. Due to random initialization of kmeans used for codebook generation, we observe no linear relationship accuracy of codebook size.

Our experiments show that the HOG-HOF, combination of gradient and optical flow based descriptors, seems to be a good descriptor. For the Weizmann and ADL datasets, the HOG-HOF descriptor performs best and takes the second place for the KTH and Keck datasets. The HOG descriptor usually perform the worst. The accuracy of the HOF and HOG3D descriptors depends on a dataset. Also, we observe that regardless of the dataset, the HOG-HOF and HOG3D descriptors always work better than the HOG descriptor.

Conclusions

In this paper, we present a full evaluation of local spatio-temporal descriptors for action recognition in videos. Four widely used in state-of-the-art approaches descriptors (HOG, HOF, HOG-HOF and HOG3D) were chosen and evaluated under the framework based on the bag-of-words approach, non-linear Support Vector Machine and leave-one-out cross-validation technique. Our experiments are performed on four public datasets (KTH Action Dataset, Weizmann Action Dataset, ADL Dataset and Keck Dataset) containing low and high resolution videos recorded by static and moving cameras. In contrast to other existing evaluations, we test all the computed descriptors, perform evaluation on several differing in difficulty datasets and perform evaluation on several codebook sizes.

  Fig. 1: A few sample frames from video sequences from Weizmann (the first row) and KTH (the second row) datasets.

Fig. 2 :

 2 Fig. 2: A few sample frames from video sequences from ADL (the first row) and Keck (the second row) datasets.

Table 1 :

 1 Statistics for the Weizmann, KTH, ADL and Keck datasets: number of videos, frames, detected points, HOG-HOF (HOG, HOF) descriptors, HOG3D descriptors, frames per video, detected points per video, HOG-HOF descriptors per video, HOG3D descriptors per video, points per frame, HOG-HOF descriptors per frame, HOG3D descriptors per frame, ratio of number of HOG-HOF descriptors to number of points, and ratio of number of HOG3D descriptors to number of points.

			KTH	ADL	Keck
	resolution	180 × 144	160 × 120	640 × 360	640 × 480
	#videos	93	599	150	98
	#frames	6,108	289,715	72,729	25,457
	#Harris3D points	13,259	473,908	718,440	227,310
	#HOG-HOF descriptors	13,259	473,908	718,440	227,310
	#HOG3D descriptors	9,116	252,014	690,907	207,655
	#frames/#videos	65.68	483.66	484.86	259.77
	#points/#videos	142.57	791.17	4789.60	2319.49
	#HOG-HOF/#videos	142.57	791.17	4789.60	2319.49
	#HOG3D/#videos	98.02	505.04	4606.05	2118.93
	#points/#frames	2.17	1.64	9.88	8.93
	#HOG-HOF/#frames	2.17	1.64	9.88	8.93
	#HOG3D/#frames	1.49	0.87	9.50	8.16
	#HOG-HOF/#points	1.00	1.00	1.00	1.00
	#HOG3D/#points	0.69	0.53	0.96	0.91

Table 2 :

 2 Action recognition accuracy for the Weizmann dataset.The KTH dataset[START_REF] Schuldt | Recognizing Human Actions: A Local SVM Approach[END_REF] 4 contains six types of human actions (walking, jogging, running, boxing, hand waving and hand clapping) performed several times by 25 subjects in four different scenarios: outdoors, outdoors with scale variation, outdoors with different clothes and indoors. The dataset contains 599 videos. All videos were taken over homogeneous backgrounds with a static camera with 25 fps. The sequences were down-sampled by the authors to the spatial resolution of 160 × 120 pixels. For this dataset, as it is recommended by the authors, we divide the dataset into testing part (person 2, 3, 5, 6, 7, 8, 9, 10 and 22) and training part (other video sequences). Statistics about this dataset are available in the table 1.

	3.2 KTH Dataset

Table 3 :

 3 Action recognition accuracy for the KTH dataset.

Table 4 :

 4 Action recognition accuracy for the ADL dataset.3.4 Keck DatasetThe Keck gesture dataset[START_REF] Lin | Recognizing Actions by Shape-Motion Prototype Trees[END_REF] 6 consists of 14 different gesture classes, which are a subset of military signals. The full list of activities is: Turn left, Turn right, Attention left, Attention right, Attention both, Stop left, Stop right, Stop both, Flap, Start, Go back, Close distance, Speed up, Come near. The dataset is collected using a color camera with 640 × 480 resolution. Each gesture is performed by 3 people. In each sequence, the same gesture is repeated 3 times by each person. Hence there are 3 × 3 × 14 = 126 video sequences for training which are captured using a fixed camera with the person viewed against a simple, static background. There are 4 × 3 × 14 = 168 video sequences for testing which are captured from a moving camera and in the presence of background clutter and other moving objects. Statistics about this dataset are available in table 1.

Table 5 :

 5 Action recognition accuracy for the Keck dataset.

http://www.irisa.fr/vista/Equipe/People/Laptev/download.html

http://lear.inrialpes.fr/people/klaeser/software_3d_video_descriptor/

http://www.wisdom.weizmann.ac.il/ ~vision/SpaceTimeActions.html

http://www.nada.kth.se/cvap/actions/

http://www.cs.rochester.edu/ ~rmessing/uradl/

http://www.umiacs.umd.edu/ ~zhuolin/Keckgesturedataset.html

Acknowledgements. This work was supported by the Région Provence-Alpes-Côte d'Azur and partly by the Sweet-Home, Video-Id, ViCoMo, Vanaheim, and Support projects. However, the views and opinions expressed herein do not necessarily reflect those of the financing institutions.