Gwénolé Quellec
email: gwenole.quellec@inserm.fr

Katia Charrière

Mathieu Lamard

Zakarya Droueche

Christian Roux

Béatrice Cochener

Guy Cazuguel

Real-Time Recognition of Surgical Tasks in Eye Surgery Videos

Keywords: CBVR, real-time, surgical task recognition, eye surgery

Nowadays, many surgeries, including eye surgeries, are video-monitored. We present in this paper an automatic video analysis system able to recognize surgical tasks in real-time. The proposed system relies on the Content-Based Video Retrieval (CBVR) paradigm. It characterizes short subsequences in the video stream and searches for video subsequences with similar structures in a video archive. Fixed-length feature vectors are built for each subsequence: the feature vectors are unchanged by variations in duration and temporal structure among the target surgical tasks. Therefore, it is possible to perform fast nearest neighbor searches in the video archive. The retrieved video subsequences are used to recognize the current surgical task by analogy reasoning. The system can be trained to recognize any surgical task using weak annotations only. It was applied to a dataset of 23 epiretinal membrane surgeries and a dataset of 100 cataract surgeries. Three surgical tasks were annotated in the first dataset. Nine surgical tasks were annotated in the second dataset. To assess its generality, the system was also applied to a dataset of 1,707 movie clips in which 12 human actions were annotated. High task recognition scores were measured in all three datasets. Real-time

Introduction

Nowadays, many surgeries are video-monitored. We believe real-time video monitoring may be useful to automatically communicate information to the surgeon in due time. Typically, whenever the surgeon begins a new surgical task, relevant information about the patient, the surgical tools, etc., in connection to this task, may be communicated to him or her (either visually or phonically). The advantage is obvious for the less experienced surgeons. Recommendations on how to best perform the current or the next task, given the patient's specificities, may be communicated to them: these recommendations would derive from the experience of their peers in similar surgeries. A first step towards that goal is presented in this paper: we describe an algorithm to detect surgical tasks in real-time during the surgery.

In recent years, a few systems have been presented for the automatic recognition of surgical tasks or gestures. A first group of systems assumes that the surgical tasks or gestures follow a predefined order: the goal is to find when each task or gesture ends and when the next one begins. [START_REF] Blum | Modeling and segmentation of surgical workflow from laparoscopic video[END_REF] proposed a system to segment such surgical tasks in laparoscopic videos. During the training phase, tool usage is analyzed to perform dimension reduction on visual features, using canonical correlation analysis. At the end of the surgery, the video is registered to a manually segmented average surgery, using Dynamic Time Warping (DTW). Note that a similar system was presented by [START_REF] Padoy | Statistical modeling and recognition of surgical workflow[END_REF]: the main difference is that it processes tool usage directly as observations, rather than visual features. [START_REF] Lalys | An applicationdependent framework for the recognition of high-level surgical tasks in the OR[END_REF] also proposed a similar system for microscope videos. Many visual features are extracted from images, including color histograms, Haar-based features and SIFT descriptors. Then, the surgery is temporally segmented in surgical tasks using the DTW. In a second group of systems, the DTW is replaced by a Hidden Markov Model (HMM) in order to relax the 'predefined order' hypothesis, although transitions between surgical tasks or gestures that are not seen in training will have a null probability. [START_REF] Blum | Modeling and segmentation of surgical workflow from laparoscopic video[END_REF], [START_REF] Padoy | Statistical modeling and recognition of surgical workflow[END_REF] and [START_REF] Lalys | An applicationdependent framework for the recognition of high-level surgical tasks in the OR[END_REF] proposed a variation on their technique described above, where the DTW is replaced by a HMM. [START_REF] Tao | Sparse hidden markov models for surgical gesture classification and skill evaluation[END_REF] proposed a system for segmenting a surgical task into a sequence of gestures, in laparoscopic videos. The system relies on sparse HMMs, whose observations are sparse linear combinations of elements from a dictionary of basic surgical motions; a dictionary is learnt for each gesture. A third group of systems assumes that the tasks or gestures have already been segmented and the goal is to classify each segmented task or gesture without contextual information. In that case, the predefined order hypothesis is completely relaxed. [START_REF] Haro | Surgical gesture classification from video data[END_REF] evaluated two approaches to surgical gesture classification in video clips. The first one is based on a linear dynamical system; the other is based on the Bag-of-Words (BoW) model [START_REF] Harris | Distributional structure[END_REF][START_REF] Huang | Retrieval of brain tumors with region-specific bag-of-visual-words representations in contrast-enhanced MRI images[END_REF][START_REF] Tamaki | Computer-aided colorectal tumor classification in NBI endoscopy using local features[END_REF][START_REF] Lalys | An applicationdependent framework for the recognition of high-level surgical tasks in the OR[END_REF]. These two approaches combined perform equally well as gesture classification based on kinematic data [START_REF] Haro | Surgical gesture classification from video data[END_REF]. Finally, note that several systems have been designed for related tasks: surgical tool detection and tracking [START_REF] Cano | Laparoscopic tool tracking method for augmented reality surgical applications[END_REF], surgical task detection without categorization [START_REF] Cao | Computer-aided detection of diagnostic and therapeutic operations in colonoscopy videos[END_REF][START_REF] Giannarou | Content-based surgical workflow representation using probabilistic motion modeling[END_REF], surgical skill evaluation [START_REF] Reiley | Task versus subtask surgical skill evaluation of robotic minimally invasive surgery[END_REF], etc. Like the third group of recognition methods, the proposed system does not assume that the surgical tasks follow a predefined order and it requires segmented surgical tasks for training. After training, the proposed system can detect, in real-time, key video subsequences that typically occur during a given task, but not during other tasks. This detection does not require any segmentation. The proposed system can also categorize a task as a whole in real-time. But in that case, like the third group of methods, it assumes that the task is segmented.

Similar systems, without the real-time constraint, have been proposed outside the scope of surgery videos. They all rely on a collection of videos containing instances of the target actions for supervision. [START_REF] Piriou | Recognition of dynamic video contents with global probabilistic models of visual motion[END_REF] proposed an action recognition framework for sport video indexing. A global probabilistic motion model is trained for each target action. To process a new video, the camera motion is first estimated and removed. Then, the residual motion is analyzed to classify the current action by maximum a posteriori estimation. [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF] presented a weakly supervised action recognition framework for movie clip indexing. First, spatiotemporal interest points are detected in videos. Then, video subsequences are characterized using a BoW model. Finally, subsequences containing the target action are detected using a weakly supervised SVM classifier. [START_REF] Xu | Video event recognition using kernel methods with multilevel temporal alignment[END_REF] proposed an event recognition framework for news video indexing. A BoW representation was also adopted to characterize varying-sized video subsequences. To compare two sequences, a variation on the EMD distance between subsequence characterizations was used. These frameworks were primarily designed for offline indexing of broadcast video, so they do not need to be run in real-time.

In order to detect key subsequences of surgical tasks, the proposed system relies on the Content-Based Video Retrieval (CBVR) paradigm. Given a video query, CBVR systems search for similar video contents in a video archive. Initially popularized in broadcasting [START_REF] Naturel | Detecting repeats for video structuring[END_REF] and video surveillance [START_REF] Smeaton | Evaluation campaigns and TRECVid[END_REF][START_REF] Hu | Semantic-based surveillance video retrieval[END_REF], the use of CBVR is now emerging in medical applications [START_REF] André | An image retrieval approach to setup difficulty levels in training systems for endomicroscopy diagnosis[END_REF][START_REF] Syeda-Mahmood | Validating cardiac echo diagnosis through video similarity[END_REF]. We present a novel CBVR system able to perform real-time searches. In this paper, it is used to recognize the current surgical task by analogy reasoning. Section 2 presents the state of the art of CBVR and discusses the specific challenge of real-time CBVR.

The proposed system is applied to eye surgery. In those surgeries, the surgeon wears a binocular microscope and the output of the ophthalmoscope is recorded. Two of the most common eye surgeries are considered in this paper: epiretinal membrane surgery [START_REF] Dev | Visual outcomes after pars plana vitrectomy for epiretinal membranes associated with pars planitis[END_REF] and cataract surgery [START_REF] Castells | Clinical outcomes and costs of cataract surgery performed by planned ECCE and phacoemulsification[END_REF]. Recently, [START_REF] Lalys | A framework for the recognition of high-level surgical tasks from video images for cataract surgeries[END_REF] adapted their general system [START_REF] Lalys | An applicationdependent framework for the recognition of high-level surgical tasks in the OR[END_REF] for segmenting cataract surgery videos. In the improved system, visual features are only extracted within the pupil only; an automatic pupil segmentation procedure is presented. Good temporal segmentation performances were measured [START_REF] Lalys | A framework for the recognition of high-level surgical tasks from video images for cataract surgeries[END_REF]. However, that system does not allow real-time recognition of the surgical tasks. It needs to process the entire surgical video before segmenting it, which implies that the segmentation is only available after the end of the surgery. To our knowledge, this paper is the first attempt to recognize eye surgical tasks in real-time.

State of the Art of Content-Based Video Retrieval

Many CBVR systems have been presented in the literature. These systems differ by the nature of the objects placed as queries. First, queries can be images [START_REF] Patel | Content based video retrieval using entropy, edge detection, black and white color features[END_REF]. In that case, the goal is to select videos containing the query image in a reference dataset; these systems are very similar to image retrieval systems. Second, queries can be video shots [START_REF] Naturel | Detecting repeats for video structuring[END_REF][START_REF] Dyana | Combining features for shape and motion trajectory of video objects for efficient content based video retrieval[END_REF]. In that case, the goal is to find other occurrences of the query shot [START_REF] Naturel | Detecting repeats for video structuring[END_REF], or similar shots [START_REF] Dyana | Combining features for shape and motion trajectory of video objects for efficient content based video retrieval[END_REF], in the reference dataset. Third, queries can be entire videos [START_REF] André | An image retrieval approach to setup difficulty levels in training systems for endomicroscopy diagnosis[END_REF][START_REF] Syeda-Mahmood | Validating cardiac echo diagnosis through video similarity[END_REF]. In that case, the goal is to select the most similar videos, overall, in the reference dataset.

CBVR systems also differ by the way videos or video subsequences are characterized. Several systems rely mainly on the detection and characterization of key frames [START_REF] Juan | Content-based video retrieval system research[END_REF][START_REF] Patel | Content based video retrieval using entropy, edge detection, black and white color features[END_REF]. Others characterize videos or video subsequences directly [START_REF] Dyana | Combining features for shape and motion trajectory of video objects for efficient content based video retrieval[END_REF][START_REF] Gao | Content based video retrieval using spatiotemporal salient objects[END_REF]). In the system by [START_REF] Dyana | Combining features for shape and motion trajectory of video objects for efficient content based video retrieval[END_REF], video shots are characterized by shape parameters and by the evolution of motion vectors over time. In the system by [START_REF] Gao | Content based video retrieval using spatiotemporal salient objects[END_REF], spatiotemporal salient objects (i.e. moving objects) are detected in videos and characterized individually; videos are then compared using the Earth-Mover's Distance (EMD), which may be time consuming. The combination of multimodal (visual, audio and textual) information in a retrieval engine has also been proposed [START_REF] Hoi | A multimodal and multilevel ranking framework for content-based video retrieval[END_REF][START_REF] Bruno | Design of multimodal dissimilarity spaces for retrieval of video documents[END_REF].

Finally, CBVR systems differ by how flexible the distance metrics should be. First, several systems have been proposed to find objects that are almost identical to the query. For instance, [START_REF] Douze | An image-based approach to video copy detection with spatio-temporal post-filtering[END_REF] proposed a copy detection system to protect copyrighted videos. In this system, images are compared individually and their temporal ordering is checked after hand. Another system has been proposed by [START_REF] Naturel | Detecting repeats for video structuring[END_REF] to detect repeating shots in a video stream, in order to automatically structure television video content. However, in most CBVR systems, we are interested in finding videos or video subsequences that are semantically similar but whose visual content can significantly vary from one sequence to another [START_REF] Juan | Content-based video retrieval system research[END_REF][START_REF] Xu | Video event recognition using kernel methods with multilevel temporal alignment[END_REF][START_REF] André | An image retrieval approach to setup difficulty levels in training systems for endomicroscopy diagnosis[END_REF]. In other words, we need distance metrics able to bridge the so-called semantic gap [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF].

In this paper, we present a CBVR system able to detect key subsequences in a video stream and also to categorize surgical tasks. Short video subsequences extracted from the video stream play the role of the query objects. A flexible distance metric is needed. As mentioned above, similar methods have been presented in the literature to solve this problem [START_REF] Piriou | Recognition of dynamic video contents with global probabilistic models of visual motion[END_REF][START_REF] Duchenne | Automatic annotation of human actions in video[END_REF][START_REF] Xu | Video event recognition using kernel methods with multilevel temporal alignment[END_REF]. When searching for similar video subsequences, and not simply video files as a whole, the number of items that should be compared to the query item explodes. And, as opposed to above methods, the proposed system needs to run in real-time. In order to meet the real-time constraint, a very fast similarity metric must therefore be used to compare video subsequences. In particular, the use of temporally flexible distance metrics such as DTW [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF][START_REF] Xu | Video event recognition using kernel methods with multilevel temporal alignment[END_REF] is prohibited for time reasons. An alternative solution is proposed: temporal flexibility is directly introduced in the way video subsequences are characterized. The idea is that video subsequences only need to be characterized once, whereas distances need to be computed every time the system processes a new subsequence, for as long as the video archive is used. So it is worth spending time computing a smart characterization for each subsequence.

System Overview

Let A j be a type of surgical tasks that we would like to recognize in videos, j = 1, ..., n A . The proposed system tries to detect short subsequences that typically occur during tasks of type A j , but not during other tasks. These "key subsequences" are detected, in real-time, in subsequences of n j images. Let V = {V 1 , V 2 , ..., V n V } be a video sequence of n V images. To detect key subsequences in V , the following steps are performed at each time instant t i , i = 2, ..., n V :

1. Texture and color features are extracted from V i , the current image. 2. Motion features are extracted from the optical flow between V i-1 , the previous image, and V i . 3. All features extracted in 1. and 2. are concatenated to form an instant feature vector, noted f (V i ). 4. In order to detect if a key subsequence has occurred in the time interval ]t i-n j ; t i ], i > n j , this instant feature vector is combined with previously computed instant feature vectors f (V k ), k = in j + 1, ..., i -1. The resulting feature vector is noted h(V ]i-n j ;i] ), where V ]i-n j ;i] denotes the { V i-n j +1 , ..., V i } video subsequence. 5. Feature vector h(V ]i-n j ;i] ) is compared to a pool of feature vectors that were extracted from a dataset of manually annotated videos and the nearest neighbors are retrieved. 6. Based on the number of neighbors that were extracted during surgical tasks of type A j , the probability p ij that a key subsequence occurred in V ]i-n j ;i] is computed. 7. A specific action can be taken if p ij is above a given threshold.

The probability that surgical tasks of type A j occurred in video sequence V is defined as the average p ij instant probability, i = n j + 1, ..., n V . The maximum average probability defines the most likely surgical task in V .

The main novelty in this paper lies in the way instant feature vectors f are combined into subsequence feature vectors h. The combined feature vector is built in such a way that it is unchanged by variations in duration and temporal structure among key subsequences of surgical tasks. Therefore, it is possible to perform simple nearest neighbor searches to compute instant probabilities. Without this computational trick, we would have to use complex distance metrics that are unchanged by such variations, but that are also very slow. In other words, the proposed f → h mapping allows realtime searches. A novel algorithm is proposed to learn the f → h mapping offline, from a dataset of weakly annotated videos, for each target task. The use of weakly annotated videos, which requires less annotation work from the experts, makes system adaptation more challenging. In particular, a novel feature weighting technique had to be designed.

Real-Time Detection of Key Subsequences

This section details how the proposed system processes video V at each time instant t i , i ≥ 2. Then, system adaptation is presented in section 5.

Extracting Instant Features Vectors

The first step is to extract an instant feature vector f (V i ) for the current image, V i . Any visual feature may be used in this purpose, with one limitation. If we want the system to process videos in real-time, then feature vector extraction must be faster than the image aquisition rate. So, simple features should be used. The feature vector we propose in this paper combines simple texture and color features extracted from V i and simple motion features extracted from the optical flow between V i-1 and V i . All these features are global features, so they can be computed fast.

In order to characterize both the textural content and the color content of V i , the wavelet transform of each color channel of V i is characterized as described hereafter. To allow real-time image characterization, a fast waveletbased image characterization from our group was used [START_REF] Quellec | Fast wavelet-based image characterization for highly adaptive image retrieval[END_REF]. The wavelet transform of each color channel consists of several subbands, each containing information extracted at a given scale and along a given direction. For each combination of color channel (3 channels), scale (3 scales) and direction (3 directions), the distribution of the wavelet coefficients in the associated subband is characterized by a two-parameter model [START_REF] Quellec | Fast wavelet-based image characterization for highly adaptive image retrieval[END_REF]. A total of 54 parameters are extracted from V i .

Motion features are extracted from the optical flow between V i-1 and V i . To this end, strong corners are first detected in V i-1 . These corners are selected, among all image pixels p, with respect to the smallest eigen value of matrix M p below:

                 M p = ( A p B p B p C p ) A p = ∑ (x,y)∈Np ( ∂I i n ∂x (x, y) ) 2 B p = ∑ (x,y)∈Np ∂I i n ∂x (x, y) • ∂I i n ∂y (x, y) C p = ∑ (x,y)∈Np ( ∂I i n ∂y (x, y) ) 2 (1)
where N p is a neighborhood of pixel p. Then, the optical flow between V i-1 and V i is computed at each strong corner by the Lucas-Kanade iterative method [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF]. The OpenCV1 library was used to select strong corners and compute the optical flow. Finally, motion is characterized by one 8-bin amplitude histogram, two 8-bin amplitude-weighted spatial histograms (one for the x-coordinates and one for the y-coordinates) and one 8-bin amplitude-weighted directional histogram. A total of 32 features are extracted from the optical flow between V i-1 and V i . Overall, the size of f (V i ) is 86 (54+32).

Extracting Subsequence Feature Vectors

Before describing precisely how subsequence feature vectors are extracted, let us first illustrate the underlying idea with an example taken from cataract surgery, namely "implant insertion". Depending on how weak the expert annotations are, implant insertion can either be a task in itself or a key subsequence in the more general "implant setting-up" task, which would also include implant positioning after the insertion. In Fig. 1, implant insertions are decomposed into four basic actions that are always visible in implant insertion subsequences: tool insertion, implant injection, tool removal, termination. Their duration can vary. The duration of the time interval between basic actions can vary. The same action can occur several times (as illustrated in V 3 ). Other actions may occur within the subsequence (as also illustrated in V 3 ). In fact, the only constraint is that each basic action occurs at least once into a predefined time interval, relative to the current image, called "basic image interval". These basic image intervals are illustrated respectively in violet, in green, in blue and in red in Fig. 1. Whenever all four basic actions have been detected in their respective basic image intervals, an implant injection is detected.

Without any time constraints, this problem could be solved using DTW on the instant feature vectors, for instance. However, to achieve real-time detection, we need to perform fast comparisons. And search algorithms allowing fast comparisons only work with simple distance metrics, such as the Euclidean distance. So we need to create a fixed-size feature vector that is unchanged by all the allowed variations mentioned above.

Temporal Setup of the Subsequence Feature Vector

Let m j denote the number of basic image intervals for the target surgical task A j . Each basic image interval is defined by a relative starting point t j,b and a length ∆t j,b , b = 1, ..., m j . The size of the video subsequences is defined as follows:

n j = max b=1,...,m j {t j,b + ∆t j,b } (2)
Let T = {(t j,b , ∆t j,b ), b = 1, ..., m j } denote the temporal setup. This temporal setup should be adapted to each target task. Its length in particular: short tasks without early warning signs do not need long video subsequences, but long tasks or tasks with early warning signs do. Typical examples of temporal structures are given in Fig. 2. Note that some images in a subsequence may not appear in any basic image interval. It happens if early basic image intervals are defined to detect early warning signs and late basic image intervals are defined to detect the task itself, but what happens in between is not relevant.

In order to detect that each basic action occurred at least once into the associated basic image interval, through a nearest neighbor search, two video subsequences should have similar feature vectors if their first basic image intervals are similar and their second basic image intervals are similar and etc. This behavior can be achieved if one feature vector is extracted from each basic image interval and if those feature vectors are further concatenated. Let g(V ]i-t j,b -∆t j,b ;i-t j,b ] ) denote the feature vector extracted from the

V ]i-t j,b -∆t j,b ;i-t j,b ] basic image interval.
Figure 1: Temporal setup of implant insertion. This figures shows three video subsequences, V 1 , V 2 and V 3 , in which an implant is inserted into the patient's eye. This task is performed at different paces from one subsequence to another. These subsequences are registered at the end of the task. Note that a small complication occurred in the third subsequence: the surgeon had to remove his tool and insert it again later. The violet interval indicates a range of dates for tool insertion, relatively to the end of the task. The green interval indicates a range of dates for implant injection. The blue interval indicates a range of dates for tool removal. The red interval indicates a range of dates for task termination (when the tool becomes invisible and the implant starts to unfold). ) should be unchanged if its temporal structure changes. In particular, whether some discriminative event occurs in image V k or in image V l should not affect the characterization of V ]i-n j ;i] so long as, for all b,

• i -t j,b -∆t j,b ≥ k, l, • or i -t j,b -∆t j,b < k, l ≤ i -t j,b , • or k, l > i -t j,b .
Subsequence feature vector extraction is summarized in Fig. 3 and detailed in the following paragraphs.

Characterizing one Basic Image Interval

Each basic image interval V ]i-t j,b -∆t j,b ;i-t j,b ] is characterized by the following average feature vector:

g(V ]i-t j,b -∆t j,b ;i-t j,b ] ) = 1 ∆t j,b i-t j,b ∑ k=i-t j,b -∆t j,b +1 f (V k ) (3)
Clearly, whether some discriminative event occurs in image

V k or in image V l , with i -t j,b -∆t j,b < k, l ≤ i -t j,b , will not affect g(V ]i-t j,b -∆t j,b ;i-t j,b ] ).

Characterizing the Video Subsequence

As mentioned above, subsequence V ]i-n j ;i] may first be characterized by the concatenation of all g(V ]i-t j,b -∆t j,b ;i-t j,b ] ) vectors, b = 1, ..., m j . Let h(V ]i-n j ;i] ) be that compound feature vector. Note, however, that basic image intervals in a subsequence are likely correlated. It follows that feature vectors g(V ]i-t j,b -∆t j,b ;i-t j,b ] ), b = 1, ..., m j , also are. In order to obtain more compact feature vectors, with less correlated components, h(V ]i-n j ;i] ) is projected onto the principal components Γ j,c , c = 1, ..., C j , obtained by a principal component analysis [START_REF] Pearson | On lines and planes of closest fit to systems of points in space[END_REF]. Finally, the projection on each principal component is weighted by λ j,c ≥ 0, c = 1, ..., C j . The λ j,c weights are chosen to fill the semantic gap between low-level feature vectors and the high-level concept of surgical task, as described in section 5.

Let h(V

]i-n j ;i] ) = { λ j,c ( h(V ]i-n j ;i] ) • Γ j,c
) , c = 1, ..., C j } denote the resulting feature vector.

Key Subsequence Detection Probability

Working with fixed-length feature vectors, such as h(V ]i-n j ;i] ), has one major advantage: similar feature vectors can be searched with fast algorithms, such as k-d trees [START_REF] Arya | Approximate nearest neighbor queries in fixed dimensions[END_REF] or Locality-Sensitive Hashing [START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF]. ANN 2 , a fast variation on k-d trees, was used in this paper to perform nearest neighbor searches in a reference dataset R j , j = 1, ..., n A . In this reference dataset, every feature vector is associated with one binary label, indicating whether or not this feature vector was extracted during a surgical task of type A j . The probability p ij that a key subsequence of type A j occurred in V ]i-n j ;i] is defined as the proportion of feature vectors with a positive label among the K nearest neighbors of h(V ]i-n j ;i] ) in R j . In all experiments, the number of nearest neighbors was set to K = 5.

Real-time Processing Pipeline

This section describes, in practical terms, how the system can be used to recognize several surgical tasks A j , j = 1, ..., n A , simultaneously, in real-time. Let N = max j=1,...,n A (n i ) denote the maximal subsequence length. At each time instant t i , i ≥ 2:

1. The instant feature vector f (V i ) is characterized. 2. f (V i ) is stored in a FIFO queue of size N .
3. For each surgical task A j , the last n j instant feature vectors in the FIFO queue are combined: the subsequence feature vector h(V ]i-n j ;i] ) is obtained.

It should be noted that the first step, which is typically the most computationally intensive, is independent of the target surgical task; therefore, it is only performed once. The FIFO queue is only useful if two consecutive subsequences overlap, that is if N > 1. In that case, instant feature vectors are stored and are used up to ∑ n A j=1 n j times to compute subsequence feature vectors.

System Adaptation

Let D be a dataset of video sequences, divided into a training subset D train and a test subset D test . For training and testing purposes, it is assumed that experts indicated whether or not each target surgical task occurred in each video sequence V ∈ D. Note that experts are not expected to indicate precisely when target tasks occurred in each video sequence. They are only expected to assign n A binary labels δ(A j , V ), j = 1, ..., n A , to each video V ∈ D: δ(A j , V ) = true if at least one A j task occurred in V , δ(A j , V ) = f alse otherwise.

The proposed system has three undetermined sets of parameters: a temporal setup, principal components, and a weight vector (see section 4.2). These parameters need to be tuned specifically for each target task A j , j = 1, ..., n A . System adaptation can be summarized as follows. After the summary, a more detailed explanation of each point is given.

1. Temporal setups are generated at random using a stochastic algorithm.

2. For each temporal setup, (a) the principal components are computed, (b) a weight vector is optimized, (c) a performance score is computed. Because experts are only expected to interpret video sequences as a whole (through binary labels δ(A j , V )), semantic relevance is assessed at video sequence level. 3. The temporal setup maximizing the performance score in the training set is retained.

Adapting the Temporal Setup

The main novelty in this paper comes from the way instant feature vectors are combined into subsequence feature vectors, using a task specific temporal setup. The main question we need to answer for system adaptation is the following: what temporal setup best captures A j tasks? This question is actually twofold. First, we need to know how many basic image intervals are needed (i.e. what is the value of m j ?). Second, we need to choose the relative starting point and the length of each basic image interval (t j,b , ∆t j,b ), b = 1, ..., m j . Given the high dimensionality of this problem, a machine learning solution is desirable. Optimization techniques able to work with variable-length vectors T = {(t j,b , ∆t j,b ), b = 1, ..., m j } are suitable candidates. A stochastic solution based on Grammatical Evolution (GE) is proposed hereafter [START_REF] O'neill | Grammatical evolution[END_REF]. A boosting strategy is also possible [START_REF] Schapire | Strength of weak learnability[END_REF].

In GE, a genetic algorithm is used to generate variable-length strings or genotypes. These strings are then mapped to programs through a userdefined grammar. The objective is to find the program that maximizes a user-defined objective function [START_REF] O'neill | Grammatical evolution[END_REF].

In order to fit into the GE paradigm, the temporal setup T = {(t j,b , ∆t j,b ), b = 1, ..., m j } is regarded as a program. The objective function that should be maximized is the performance score described in section 5.4. Let S t and S ∆t denote a set of relative starting points and a set of lengths, respectively. The grammar used to generate temporal setups is given in algorithm 1. In a grammar, symbols are delimited by angled brackets (< . >). To generate programs, GE recursively replaces each symbol, starting with symbol < T >, by one expression. The list of valid expressions for each symbol starts with ::= and uses | as delimiter.

Algorithm 1 Temporal Setup Grammar < T >::= {< bbi >} < bbi >:

:=< bbi >, < bbi > | (< t >, < ∆ t >) < t >::= S t,1 | S t,2 | ... < ∆ t >::= S ∆t,1 | S ∆t,2 | ...
In all experiments, the following set of relative starting points was used: S t = {0, 1, 2, 5, 10, 20, 50, 100}. The following set of lengths was used: S ∆t = {1, 2, 5, 10, 20, 50, 100}. This grammar generates a variable-length list of (< t >, < ∆ t >) tuples. In the first line of the grammar, the list is initialized by a symbol with undefined value: < bbi >. In the second line of the grammar, the list is expanded by recursively duplicating the < bbi > symbol whenever the first valid expression in that line (< bbi >, < bbi >) is randomly chosen by the GE engine. The expansion stops when all < bbi > symbols have been replaced by a (< t >, < ∆ t >) tuple: this happens when the second valid expression of line 2 is chosen. Then, the GE engine randomly chooses a value for each relative starting point < t > and each length < ∆ t > using the third and the fourth line of the grammar, respectively. Populations of 30 programs were evolved by grammatical evolution. Grammatical evolution was stopped when the optimal solution did not evolve for more than 5 generations. The proposed learning algorithm does not ensure that the first basic image interval starts at t = 0. Therefore, as a post processing step, all relative starting points are translated such that the first one equals 0.

Principal Component Analysis

The principal components Γ j,c , c = 1, ..., C j , are obtained by a Principal Component Analysis (PCA) [START_REF] Pearson | On lines and planes of closest fit to systems of points in space[END_REF]. The dataset analyzed by the PCA algorithm is formed by h(V ]i-n j ;i] ) subsequence feature vectors extracted from the training subset D train , using the current temporal setup. As commonly done in the literature, C j was chosen such that 90% of the energy is preserved [START_REF] Ricci | [END_REF]. Note that the projections h(V ]i-n j ;i] )•Γ j,c on the principal components do not depend on the order of the features in the input training samples. It implies that the order in which the g(V ]i-t j,b -∆t j,b ;i-t j,b ] ) vectors are concatenated to form the h(V ]i-n j ;i] ) vectors does not matter.

Adapting the Weight Vector

A weight vector λ j has been introduced in section 4.2 to bridge the semantic gap between low-level subsequence feature vectors and the high-level concept of 'similar surgical tasks'. Because experts are only expected to interpret video sequences as a whole, weight adaptation cannot be supervised at video subsequence level: it is supervised at video sequence level. A novel feature weighting technique is proposed for this specific setup.

First, a semantic and a low-level distance between video sequences are defined. D sem j (U, V ), the semantic distance between two video sequences U and V , is defined as follows:

D sem j (U, V )=0 if δ(A j , U ) = δ(A j , V ) and D sem j (U, V )=1 otherwise. D low j (U, V )
, the low-level distance between U and V , derives from the weight vector λ j and all feature vectors h(U ]i-n j ;i] ) and h(V ]i-n j ;i] ) (see section 5.3.1). In order to maximize the semantic relevance of retrieved video subsequences, λ j is tuned so that D sem j and D low j become as close as possible in the training subset D train (see section 5.3.2). In other words, λ j is chosen to bridge the semantic gap in the least-squares sense.

Low-Level Distance

For each feature vector component c = 1, ..., C j , a partial low-level distance between video sequences U and V is defined: D low j,c (U, V ). Assuming that U and V both contain the target task, they are considered similar no matter when the target tasks occurred in these videos. Therefore, we simply need to compare the distributions

H c (U ) = { h c (U ]i-n j ;i] ), i = n j , ..., n U } and H c (V ) = { h c (V ]i-n j ;i] ), i = n j , ..., n V }
, regardless of time sequencing. D low j,c (U, V ) is defined as the maximal deviation between the Cumulative Distribution Function (CDF) of H c (U ) and the CDF of H c (V ). In other words, D low j,c (U, V ) is the Kolmogorov-Smirnov statistic of the test "H c (U ) = H c (V )" [START_REF] Von Mises | Mathematical Theory of Probability and Statistics[END_REF].

Bridging the Semantic Gap

Let T = |D train | be the number of video sequences in the training set. Let T ′ = 1 2 T (T -1) be the number of pairs of video sequences. For each video sequence pair (U, V ), one semantic distance D sem j (U, V ) and C j partial low-level distances D low j,c (U, V ) have been computed. Semantic distances are grouped together in a vector d sem j of size T ′ . Low-level distances are grouped together in a matrix D low j of size (T ′ × C j ). The weight vector λ j minimizing the sum of the squared errors between d sem j and D low j • λ j is found by multi-parameter linear fitting with positivity constraints: the nonnegative least squares algorithm is used [START_REF] Lawson | Solving Least Squares Problems[END_REF].

Performance Assessment at Video Sequence Level

The performance of the system is assessed using a reference dataset R (from which the nearest neighbors are extracted) and a validation dataset V. During system adaptation, R is a portion of the training subset D train and V is the complement of R in D train . After system adaptation, R is the entire training subset and V is the test subset D test .

Performances are assessed in terms of A z , the area under the Receiver Operating Characteristic (ROC) curve [START_REF] Hanley | The meaning and use of the area under a receiver operating characteristic (ROC) curve[END_REF]. The following procedure is applied to build the ROC curve for a given task A j . First, for each video sequence V ∈ V in the validation set, p(δ(A j , V )), the probability that V contains at least one A j task, is defined as the average instant probability p ij , i = n j + 1, ..., n V . Instant probabilities are computed using nearest neighbors extracted from R. Then, the ROC curve of p(δ(A j , V )), against the ground truth δ(A j , V ), is built using every p(δ(A j , V )) value, V ∈ V, as a threshold.

Video Datasets

The proposed framework was evaluated in two eye surgery datasets: a dataset of retinal surgeries (see section 6.2) and a dataset of cataract surgeries (see section 6.3). To assess its generality, the method was also evaluated in a dataset of human actions in general (walking, sitting down, etc. -see section 6.4).

Weak Supervision for Surgery Videos

In order to evaluate the performance of surgical task detectors, surgical tasks need to be manually delimited in full surgery videos. Note that a surgery is generally not a predefined linear sequence of surgical tasks. For instance, surgeons may have to widen an incision afterwards because they realized the initial incision was not large enough. The "current task" may be combined with recurring tasks such as moisturizing the patient, sucking out blood, etc. Also, surgeons generally have two hands, so two "consecutive tasks" may actually overlap. Therefore, partitioning a surgery into task-specific video sequences is not always possible. For each surgical task, a specialist was asked to indicate the date of the first appearance of one tool related to this task into the field of view. Similarly, he was asked to indicate the date of the last disappearance of one of these tools from the field of view. These two dates define the beginning and the end of each manually delimited video. As a consequence, these manually delimited videos are weakly annotated: other tasks may appear into the video. It means that, given a manually delimited video V , δ(A j , V ) may be true for multiple A j tasks. Also, these videos often contain time intervals when no task is visible into the field of view: it happens, for instance, if the surgeon needs to change one of his or her tools. Every manually delimited video V was classified (the value of δ(A j , V ) was determined for each task A j ) and assigned to the dataset D.

Retinal Surgery Dataset (RSD)

The first dataset consists of 69 videos of Epiretinal Membrane Surgery (EMS) collected at Brest University Hospital (France). EMS is the most common vitreoretinal surgery [START_REF] Dev | Visual outcomes after pars plana vitrectomy for epiretinal membranes associated with pars planitis[END_REF]. It involves a pars plana vitrectomy procedure with membrane peeling. Twenty-three consecutive surgeries of twenty-three patients have been video-recorded with a CCD-IRIS device (Sony, Tokyo, Japan) and the videos were stored in MPEG2 format with the highest quality settings. The frame frequency is 25 frames per seconds. Images have a definition of 720x576 pixels. Three video sequences were manually delimited in each surgery video as explained in section 6.1. Each video sequence corresponds to one step of the EMS: Injection, Coat and Vitrectomy (see Fig. 4). The duration of each surgical task is reported in table 1. The dataset was randomly divided into two subsets of 12 and 11 surgeries, respectively. In order to deal with the small number of surgeries in this dataset (23), a special training procedure was adopted. At first, surgical tasks detectors were trained in the first subset and their performance was tested in the second subset. Then, new surgical task detectors were trained in the second subset and their performance was tested in the first subset. Therefore, performance scores were computed for each video sequence.

Cataract Surgery Dataset (CSD)

The second dataset consists of 900 videos of phacoemulsification cataract surgery collected at Brest University Hospital (France). Cataract surgery is the most common ophthalmic surgery and most of the cataract surgeries are phacoemulsification procedures [START_REF] Castells | Clinical outcomes and costs of cataract surgery performed by planned ECCE and phacoemulsification[END_REF]. In this procedure, an ultrasonic device is used to break up and then remove a cloudy lens, or cataract, from the eye to improve vision. One hundred consecutive surgeries of one hundred patients have been video-recorded. Some surgeries were recorded with a CCD-IRIS device (Sony, Tokyo, Japan), the others were recorded with a MediCap USB200 video recorder (MediCapture, Philadelphia, USA). They were stored in MPEG2 format, with the highest quality settings, or in DV format. The frame frequency is 25 frames per seconds. Images have a definition of pixels. Nine video sequences were manually delimited in each surgery video as explained in section 6.1. Each video sequence corresponds to one step of the cataract surgery: Incision, Rhexis, Hydrodissection, Phacoemulsification, Epinucleus removal, Viscous agent injection, Implant setting-up, Viscous agent removal and Stitching up (see Fig. 5). The duration of each surgical task is reported in table 1. The dataset was randomly divided into two subsets of 50 surgeries: one was used as training set, the other was used as test set.

Movie Clip Dataset (MCD)

The third dataset consists of 1,707 video sequences extracted by the IRISA lab from 69 Hollywood movies 3 (Marsza lek et al., 2009). The authors indicated which human actions were visible in each video sequence, out of 12 possible actions. In most of the dataset, a semi-automatic procedure was used: 1) clips were automatically annotated using text mining techniques in the movie scripts and 2) the automatic annotations were controlled by a human observer. In the Training subset (automatic), the annotations were fully automatic: they were not controlled by a human observer. The frame frequency is 25 frames per seconds. Typical image definitions include 640x352, 576x312 and 548x226. Videos have an average duration of 20 seconds. The test subset consists of 884 video sequences. The training set consists of 823 video sequences: we decided not to use the Training subset (automatic) because the annotations have a lower quality.

Results

The optimal selections of basic image intervals, obtained in the training subset of each dataset4 , are reported in table 2. In practice, basic image The proposed method does not detect the appearance or disappearance of tools in the field of view, unlike the manual segmentation provided by experts. It detects clinically-significant actions, which can happen anytime between the appearance and the disappearance of the associated tools. So the system was assessed at the surgical task level. The performance of the proposed framework in the test subset, in terms of A z , the area under the Time Interest Point extraction [START_REF] Laptev | On space-time interest points[END_REF], is OpenCV code provided by the authors6 . The rest of the method was implemented in C++, also using OpenCV and LIBSVM7 . All computations were performed using one core of an Intel Xeon(R) E5649 processor running at 2.53GHz. In all three datasets, most of the computation time was dedicated to subsequence characterization, and to image characterization in particular (see section 4.1). Retrieval only took about eight milliseconds per query on average. Because image sizes are lower in MCD, computation times are lower in that dataset (see table 4). To assess the overall accuracy of the system, we performed an additional experiment where all target task detectors are run simultaneously, as described in section 4.4. This defines the most likely surgical task in each video

Discussion and Conclusion

A novel framework for real-time retrieval of similar video subsequences was presented in this paper. Given a target surgical task, video subsequences are decomposed into an optimal set of overlapping basic image intervals. The proposed video description ignores the temporal structure within basic image intervals by averaging instant feature vectors. The temporal structure is only encoded, in a fuzzy fashion, by concatenating the feature vectors describing the basic image intervals composing the subsequence. The proposed framework was applied to real-time recognition of high-level surgical tasks in video-monitored eye surgeries. Two types of surgeries were considered: epiretinal membrane surgery and cataract surgery. For most surgical tasks (7 out of 12), the system compared favorably to a state-of-the-art human action recognition system in terms of area under the ROC curve (see table 3). The proposed method failed to recognize one surgical step, namely viscous agent injections, but so did the baseline method. This was to be expected: injections mostly involve subtle fluid motions within the eye. Note that the largest dataset group together videos recorded with different devices, which makes the recognition task more challenging. To assess its generality, the proposed system was also applied to human action recognition. For most human actions (8 out of 12), the proposed system turned out to be more efficient than the baseline method as well (see table 3). Overall, the proposed method significantly outperforms the baseline method in RSD and MCD, but not in CSD (p > 0.05, see table 5). The proposed system is very fast: while the baseline method processes less than one image per second (see table 4), the proposed system runs nearly in real-time (= 25 frames per second). Note that the cataract surgery phase segmentation system by [START_REF] Lalys | A framework for the recognition of high-level surgical tasks from video images for cataract surgeries[END_REF] also processes less than one image per second (one image every 3 seconds). One limitation of the proposed method, in terms of computation times, is that training is slow, due to the use of grammatical evolution: on average, training lasts 16 hours per surgical task or action on an Intel Xeon(R) E5649 12-core processor. One strength of the method is that it does not assume that consecutive surgical tasks follow a predefined order, unlike methods by [START_REF] Lalys | A framework for the recognition of high-level surgical tasks from video images for cataract surgeries[END_REF] and [START_REF] Blum | Modeling and segmentation of surgical workflow from laparoscopic video[END_REF] for instance. One such method [START_REF] Blum | Modeling and segmentation of surgical workflow from laparoscopic video[END_REF] was implemented and run on our cataract surgery dataset (CSD). For several reasons, surgical videos could not be registered to a manually segmented average surgery. First, several surgeons, with varying skill levels and varying techniques, participated in the study. Second, surgical tasks usually overlapped in those videos. Third, in some surgeries, additional tasks had to be performed, such as removing an old implant for instance.

We believe this success comes from the high flexibility in the adaptation process. It can be seen in table 2 that very different temporal setups were obtained depending on the target task. However, it should be noted that most temporal setups are quite simple (see table 2): they usually consist of two or three basic image intervals. This prevents overfitting and ensures good performances in the test set. This good property comes from the use of grammatical evolution, which penalizes complex solutions in accordance with Occam's razor principle [START_REF] O'neill | Grammatical evolution[END_REF].

Note that, although the proposed system is particularly well suited to eye surgeries, it could be applied to other surgeries where video-recording is available, for instance minimally invasive surgeries. Indeed, all the visual cues are application-independent. This is an advantage, but also a drawback: it means that the visual cues are probably not optimal for a specific application. To push performance further, we should include eye-related and tool-related visual cues into the image characterizations [START_REF] Lalys | A framework for the recognition of high-level surgical tasks from video images for cataract surgeries[END_REF]. It may also be possible to push performance further by taking into account the temporal relationships between the composing tasks of a surgery, using an HMM for instance. However, as discussed above, a strict task ordering should not be assumed. Depth information should also be included whenever stereorecording of the microscope output will be widely available.

As discussed in the introduction section, the proposed video monitoring system was primarily designed to communicate information to the surgeon in due time. In particular, it was designed to send recommendations to the less experienced surgeons slightly before the beginning of each task. We have shown that it can detect and categorize surgical tasks approximately when they happen. So, when task n -1 is detected, we can provide recommendations for task n based on observations from tasks 1, ..., n-1. Note that giving recommendations while the surgeon has already started performing task n would not be optimal: the decision on how to perform that task has already been made. Note that the proposed system is a case-based reasoning system: it relies on a dataset of surgical videos in which experts have temporally segmented the surgical tasks. If, in addition to segmenting the surgical tasks, experts were also asked to temporally segment surgical complications, then we may be able to go one step further: knowing what the surgeon is doing and what problem he or she is facing, recommendations could be refined. We believe that, one day, such an automatic video monitoring system may also be used to communicate with surgical devices directly. The idea would be, for instance, to preventively shut down a device in case of complication. Finally, note that the system may also be used offline, for video structuring. Video content structuring will allow efficient video browsing and therefore, efficient video archive browsing. Browsing video archives may be useful for retrospective clinical studies, skill assessment or training. It may be used to generate surgery reports at the end of each surgery [START_REF] Lalys | A framework for the recognition of high-level surgical tasks from video images for cataract surgeries[END_REF].

In conclusion, we have presented a system that can retrieve similar video subsequences in real-time. It was successfully applied to real-time recognition of surgical tasks in eye surgeries. And we have discussed its potential clinical applications. society, president of the French Academy of Ophthalmology and editorial board member of the Journal Français d'Ophtalmologie, she is a specialist of refractive techniques in vision correction. She participated in three books on surgical techniques and has published more than 30 peer reviewed journal articles.

Guy

Figure 2 :

 2 Figure 2: Examples of temporal setups. In those examples, each image is represented by one column. In examples (a) and (c), each video subsequence consists of n j = 32 images; in example (b), each video subsequence consists of n j = 36 images. Each basic image interval is represented by one row. In examples (a) and (b), each video subsequence consists of m j = 8 basic image intervals; in example (c), each video subsequence consists of m j = 6 basic image intervals. If one image appears in several rows, like in example (c), it means that two or more basic image intervals overlap. Note that there are no overlaps in examples (a) and (b).

Figure 3 :

 3 Figure 3: Extracting subsequence feature vectors

Figure 5 :

 5 Figure 5: Images from different high-level surgical tasks in the Cataract Surgery Dataset (CSD)

Figure 6 :

 6 Figure 6: Receiver Operating Characteristic (ROC) curves for the RSD dataset (see section 6.2)

Figure 8 :

 8 Figure 8: ROC curves for the MCD dataset ( §6.4) 36

Table 3 :

 3 Performance evaluation (A z ) in the test set

		Dataset / Action	Proposed method	Method by Duchenne et al.
			Injection	0.923	0.500
	RSD		Coat	0.995	0.978
			Vitrectomy	0.898	0.906
			Incision	0.741	0.801
			Rhexis	0.878	0.837
		Hydrodissection	0.762	0.719
		Phacoemulsification	0.923	0.912
	CSD	Epinucleus removal	0.969	0.946
		Viscous agent injection	0.561	0.614
		Implant setting-up	0.703	0.792
		Viscous agent removal	0.729	0.695
			Stitching up	0.883	0.982
		AnswerPhone	0.801	0.602
			DriveCar	0.914	0.910
			Eat	0.848	0.799
			FightPerson	0.905	0.932
			GetOutCar	0.794	0.782
	MCD		HandShake HugPerson	0.830 0.691	0.751 0.715
			Kiss	0.852	0.696
			Run	0.873	0.883
			SitDown	0.777	0.832
			SitUp	0.800	0.729
			StandUp	0.786	0.778
		Table 4: Computation times (frames per second)
		Dataset Proposed method Method by Duchenne et al.
		RSD	26.0 FPS	0.78 FPS
		CSD	24.3 FPS	0.72 FPS
		MCD	28.9 FPS	1.39 FPS

  Cazuguel received the engineering degree from the Ecole Nationale de l'Aviation Civile, in 1975, the M.S. degree in advanced automatics, in 1976, and the Ph.D. degree in signal processing and telecommunications from the University of Rennes I, France, in 1994. He is currently a Professor in the Image and Information Processing Department, TELE-COM Bretagne. His research interests include image analysis and content based image retrieval in medical applications, within the LaTIM Inserm Research Unit 1101.

		1
		0.8
	true positive rate	0.4 0.6
					AnswerPhone
		0.2			DriveCar Eat
					FightPerson
					GetOutCar
		0			HandShake
		0	0.2	0.4	0.6	0.8	1
				false positive rate
		1
		0.8
	true positive rate	0.4 0.6
					HugPerson
		0.2				Kiss Run
					SitDown
					SitUp
		0			StandUp
		0	0.2	0.4	0.6	0.8	1
				false positive rate

http://opencv.willowgarage.com/wiki/

http://www.cs.umd.edu/ ~mount/ANN/

http://www.irisa.fr/vista/actions/hollywood2/

In RSD, a 2-fold cross-validation was performed: we only reported the basic image intervals obtained in the first fold.

http://opencv.willowgarage.com/wiki/

http://www.di.ens.fr/ ~laptev/download.html

http://www.csie.ntu.edu.tw/ ~cjlin/libsvm/