Marie-Odile Berger

Dr Pietro Mascagni

Dr Juan Verde

Dr Cristians Gonzalez

Thanks to the MOSaiC team as well, for providing excellent annotation software. I am thankful of course for every member of team CAMMA -past and present. All of them contributed to creating a work environment I will remember very fondly long after my time here; especially Chinedu and Vinkle, who, as fellow PhD students, were in the same boat I was the entire time.

Outside of the lab, I am definitely thankful for the company of my friends from high school as well as various people who supported me along the way. Cara, thank you. Special

Abstract

The work presented in this thesis tackles the problem of video analysis for laparoscopic interventions, in the case of very scarcely annotated datasets. During laparoscopic surgery, the live video feed from inside the abdominal cavity of the patient is the keystone of the entire procedure, providing all the visual feedback required by the surgeon and the staff to carry out the intervention. Our objective is to develop methods capable of leveraging this source of information and understand it; thus providing the foundation for context-aware, vision-based systems to be developed in the future for decision support in the operating room. Recent breakthroughs in computer vision, spearheaded by deep learning methods brought major advances to surgical video analysis. However the current default approach of full supervision is an obstacle for future developments. Laparoscopic procedures generate vast amounts of video data which, even if stored, will for the most part almost certainly remain unannotated.

This thesis investigates the use of unannotated data across multiple visual tasks. In our first approach, we propose an automatic annotation method relying on a very small ratio of manually annotated data, and demonstrate the usability of the automatically annotated data for training real-time CNN-LSTM predictors. Our second approach then shows how this unannotated data can be leveraged and explored in a scalable, OR-compatible manner and without any annotations using video hashing. By learning, in a self-supervised manner, searchable binary representations of surgical videos, we are able to retrieve video content matching a given scene, represented by a video clip, in terms of surgical phase or surgical critical event. Based on its reading of the anatomy and the instruments, the system determines all three criteria for safely cutting the cystic duct are met. dominal cavity with higher amounts of adhesions. Not only does this anatomical variation increase the visual difficulty of recognition problems, it also alters the workflow, requiring the surgeon to perform adhesiolysis prior to the actual intervention. . . . . . . . . . . . . . . . . . 16 1.8 Excerpt from the original autocomplete patent; relevant items appear beneath the search bar before the query is even spelled out. . . . . . . . 17 1.9 Examples from Bing Visual Search. A picture of a kitchen island and a wallaby (left) serve as queries; for the wallaby the species is correct on every search result. Image credits: 4 Training approaches compared for real-time video retrieval. . . . . . . . 5.5 Evaluation protocols for real-time video retrieval. . . . . . . . . . . . . 5.6 mAP@20 for all methods, all levels of observation, on FCVID. . . . . . 5.7 mAP@20 for all methods, all levels of observation, on ActivityNet. . . . 5.8 mAP@K for LA-CODE on FCVID . . . . . . . . . . . . . . . . . . . . . . 5.9 mAP@20 for LA-CODE on ActivityNet . . . . . . . . . . . . . . . . . . . 5.10 Example of retrieval over time from FCVID, showing the top 5 results

List of Figures

for the beginning, middle and end. Red borders indicate class mismatches. 5.11 Successful example of retrieval over time from FCVID. . . . . . . . . . 6.1 Endocorpus splitting for retrieval experiments (the size of graphical elements in the diagram does not reflect data quantities). . . . . . . . . . 6.2 Primary and secondary uncertainty on the bitcode stored in the codebook. 6.3 Uncertainty pattern compression. Each 7-bit pattern of two uncertain bits can be assigned a rank from 0 to 7 2 = 5; for example by using the lexicographic order. This rank is then written in base 2. In this case this saves two bits over the original pattern. . . . . . . . . . . . . . . . 6.4 ULA-CODE pipeline overview. When building the codebook, the uncertainty pattern is compressed then stored alongside the bitcode. During retrieval, the uncertainty pattern is restored using combination unranking, and applied as a mask in the Hamming distance computation. . . . 6.5 ULA-CODE hyperparameter ranges: bit skepticism K bs , primary/secondary balance factor θ, uncertain bit discounting factor γ. Highlighted values are used in our experiments. Note that γ = 0 or K bs = 0 are equivalent to the regular LA-CODE, without using uncertainty . . . . . . . . . . . . 6.6 Influence of γ on mean average precision. . . . . . . . . . . . . . . . . . 6.7 Influence of θ on mean average precision. . . . . . . . . . . . . . . . . . 6.8 Influence of k on mean average precision. . . . . . . . . . . . . . . . . . The OR in the minimally invasive surgery era Among all the options available to healthcare providers for treatment, surgery often stands out as the most heavy-handed, and is only prescribed to a patient after careful diagnosis and deliberation. The surgeon is given the "authority to cure by means of bodily invasion" [START_REF] Gawande | Two hundred years of surgery[END_REF] and is therefore able to intervene directly on the area of interest; however it is well understood that this can be a double-edged sword, and carries risks of major collateral damage. For this reason the history of technological advances in surgery is defined by an increasing amount of concern and respect for the patient's integrity: from the discovery of anesthesia in the XIXth century, passing by the discovery of antiseptics, to medical imaging and finally the advent of minimally invasive surgery in the XXth century.

List of Tables

Minimally invasive surgery (Figure 1.1) decreases adverse outcomes and patient discomfort by restricting the size of the incisions employed for accessing a body cavity. The resulting loss in direct visibility in those procedures is generally compensated by the use of intraoperative imaging devices: in the case of laparoscopy, which is the modality featured in the work presented here, the instruments are inserted through very small incisions, along with an optical camera called a laparoscope (Figure 1.1). The surgeon is fully reliant on the picture from its video feed, displayed on a separate monitor in the operating room.

The OR as a high-stakes, timing-sensitive environment

While minimally invasive surgery has overall been a major step forward in the development of surgery, the introduction of any new technology to the OR comes at an expense, both in terms of time and material resources. According to a 2012 review by Ramsay et al. [RPR + 12], total costs for a laparoscopic setup exceed 161K $: this includes the laparoscope as well as the display unit, surgical instruments, and the generator powering energy-based instruments. Yet, this number is dwarfed by the 2M $ cost of Intuitive Surgical's Da Vinci robot, used in many gastrointestinal surgeries. In addition to these already high upfront costs, complex medical devices often require CHAPTER 1. INTRODUCTION long, specialized training: the IRCAD's course for laparoscopic general surgery takes place over a week full-time, for a total of 2780 euros per participant. Finally each new item entering the OR generates supplementary costs and delays due to sanitization requirements and maintenance.

Accumulating those technological expenses contributes to surgery's colossal footprint on total healthcare costs, which was evaluated at 1/3 in the United States in a 2014 study [START_REF] Childers | Understanding Costs of Care in the Operating Room[END_REF]. Within expenses related to surgical care, the operating room ranks second: in 2014, it was established that a single minute of OR usage in California costs between 36 and 37 $ [START_REF] Childers | Understanding Costs of Care in the Operating Room[END_REF]. Considering the average duration of 110 minutes for a Roux-en-Y gastric bypass in our dataset, a crude estimation for only one of these procedures puts its OR costs in the 4000 $ range. More importantly, the standard deviation in duration is considerable: 30 minutes, which translates to a 1100 $ swing. By cumulating over a year for the 43000 [EDH + 20] Roux-en-Y gastric bypass surgeries performed in the US, OR expenses would range between 129 and 215 M$, and are therefore largely impacted by in-OR workflow and efficiency. Beyond financial considerations, the impact on patient outcomes and quality of treatment -which are obvious top priorities -is critical as well. Tighter and more accurate timings enable treating more patients, keeping them under anesthesia for shorter periods of time and decreasing odds of adverse events. For instance, a study conducted by Peng et al.

[fPZY + 09] shows how prolonged insufflation of the abdominal cavity in laparoscopy can lead to hypothermia. CO 2 is also known to cause acidosis in the exposed tissues of the abdominal cavity [START_REF] Bonjer | Surgical Principles of Minimally Invasive Procedures: Manual of the European Association of Endoscopic Surgery[END_REF].

Yet, OR time management is often up to the surgeon. It is common practice for the surgeon to have the next patient brought in 15 minutes before the end of their current intervention. This requires taking a guess on a complex procedure, accounting for intraoperative conditions, surgical skill and critical events. "Active bleeding" critical events during laparoscopic interventions, for example, can severely disrupt the intervention; they require the surgeon to stop their course of action and switch to cleanup, using a dedicated irrigation & suction device. According to Travis et al. [TTW + 14], surgeons underestimate procedure duration by 31 minutes on average.

The proliferation of signals in the OR & the challenge of data

Under such high-pressure conditions, one would think the technological resources given to surgeons would help counterbalance the difficulty and make the workflow of surgery easier to navigate. In many aspects the opposite is true: while the proliferation of devices and signals in the operating room provides many benefits both in terms of comfort for the surgeon and patient outcomes, its current burden on the surgical staff is not to be neglected. Each device in the OR increases pre and post operative workload, due to sanitization and setup. Intraoperatively, many systems failure events need to be accounted for: loss of video feed, loss of power, loss of visibility are issues sometimes found in recordings from our Endocorpus dataset. Each device may also be a source of disruptions during the procedure: through visuals such as blinking lights and monitor displays, but also sounds. A study by Wung et In recent years, the surgeon has been given highly advanced technology to extend their perception and manipulation capabilities; on the other hand, little effort has been made to provide them with adequate tools to process information that is everincreasingly rich and difficult to process. This very information, however, may be the key to a solution: surgical data, if systematically collected on a large enough scale, can be used to develop powerful support tools for surgeons. This is the core premise behind Surgical Data Science [MHVS + 17, HMHV20]; according to its originators [MHVS + 17], this emerging discipline "focuses on the acquisition, modeling and analysis of data to improve the quality of interventional healthcare". Three key clinical applications are targeted:

• Decision support: by using comprehensive data to expand the information available to the surgeon, otherwise limited to their own experience

• Surgical training and skill evaluation: by using objective analytics to provide automated feedback to trainees

• Context-aware assistance: by building AI models capable of understanding clinical situations relevant previous cases -in real time and responding accordingly with properly timed support This last item is the focal point of the work presented here: knowing how and when to interact with the surgeon based on the real-time context ultimately determines whether a system is an asset or a liability in the OR. For instance, to guarantee a safe procedure, sending safety check alarms is a straightforward task. However doing so at the correct time is not: too often and the alarm system turns into a distraction at best, a hazard at worst [START_REF] Wung | Sensory overload and technology in critical care[END_REF]; too sporadically and the enforcement of safety checks loosens, allowing for more surgical errors. Both are characterized by a lack of awareness with regards to context: for example not knowing the overall progress of the surgery [TYM + 19], or the current surgical phase [START_REF] Putra | Vision-based approaches for surgical activity recognition using laparoscopic and RBGD videos[END_REF], or the surgical actions [NGY + 20] taking place. In all of these areas, the improvement AI support is capable of bringing is considerable.

Models of AI-enhanced support

1.2.1 The AI-enhanced control unit 1.2.1.1 Context-awareness in non-clinical domains Surgical Data Science is a critical first step before the actual deployment of new context-aware applications in the OR. Surgery, however, is far from the only domain regimented by tight timings and low margins for error -and yet several of these domains are far closer to the deployment stage, or even reached it years ago with AI or vision-enhanced support infrastructures already heavily in place. Examples from those other fields may serve as models for what future developments for an "OR control tower", as envisioned by Mascagni et al. [START_REF] Mascagni | Or black box and surgical control tower: recording and streaming data and analytics to improve surgical care[END_REF], could ultimately look like.

In the automotive industry, one of the major motivations for self-driving vehicles besides limiting accidents is the ability to drastically cut down traffic congestion, and thereby CO 2 emissions and fuel costs. Replacing human drivers with a context-aware 1.2. MODELS OF AI-ENHANCED SUPPORT Figure 1.4: AI-powered control tower concept by Searidge. Image credits: NVIDIA. system that integrates vision from onboard cameras but also nearby traffic data enables quick and optimal decision making, thus removing traffic jam causes such as human driver reaction time accumulation [START_REF] Friedrich | The Effect of Autonomous Vehicles on Traffic[END_REF].

In 2015, the Canadian company Searidge released AIMEE (Figure 1.4), an AI framework that can process up to 200 simultaneous video feeds in order to track aircrafts in airports. This information can be used to provide AR overlays to the airport security staff and report anomalies. The end goal is to enable fully remote, vision-based control towers, to replace current ones that are pinned down by radar infrastructure requirements.

Live sporting events are particularly ahead of the curve in terms of vision-enhanced support. Tennis tournaments have employed ball tracking technologies since the 2000s; this information is transmitted to TV production trucks, which use it to generate overlays for the audience. The "1st and 10 line" (Figure 1.5) in American football has been implemented by SportsMEDIA [Spo21] for the 2013 Super Bowl, as a visual cue for the audience. Hawk-Eye's vision-based goal line technology has become critical in soccer for supporting referree decisions.

Potential clinical applications

The key takeaway from the other domains mentioned before is the control tower concept: a unit equipped with ample computing resources, continuously collecting signals from the center of activity, determining its context and returning feedback to it. Similar to production trucks for sporting events or next-generation flight control towers, an infrastructure should collect video feeds from the various operating rooms in one or even several clinical facilities, interpret them using artificial intelligence and provide appropriately timed support to surgeons. The ABITO project [MVA + 20] is an example of context awareness driving in-OR support: during laparoscopic cholecystectomy, a control unit reads the endoscopic video feed from an operating room 1.6, and orders an intra-operative timeout when it determines the surgeon is about to cut the cystic duct.

However while future approaches to context awareness in the OR should draw inspiration from other domains, it is important to recognize challenges that are specific to surgery. Aircrafts, road infrastructure, football fields and player uniforms can all be standardized to a fairly advanced degree. Patient anatomy, for obvious reasons, currently cannot; which logically translates to extremely high variability in surgical workflow -for example the presence of adhesions in the abdominal cavity varies a large amount from one patient to another. This in turn induces variability in the workflow, forcing the surgeon to dedicate more or less time to adhesiolysis (Figure 1.7). Even in a highly standardized procedure such as cholecystectomy, actions may look drastically different between surgeries due to changing teams and habits of clinicians: this manifests, for instance, in non-standard usage of surgical tools; e.g, pulling apart tissue with graspers instead of using the laparoscopic hook, or electrifying a grasper with an energy-based tool to perform cauterization.

Ultimately, with this variability in mind, the current understanding of context awareness needs to be challenged. From a computer vision algorithm's perspective "understanding the context" in an endoscopic video can mean "recognizing one of seven standardized surgical phases", "recognizing one of seven standardized surgical tools" or even "recognizing one of a hundred standardized surgical actions". However when standardized categories fail to capture the full understanding of an endoscopic video, the best way a system can describe it may very well be another endoscopic video from a large enough database.

Harnessing large databases with search

A common approach for navigating unknown pieces of data is to search for similar items in a large and diverse database. Despite its simplicity this is a well-accepted principle; most notably, even state-of-the-art AI assistants such as Google Assistant (Google) or Siri (Apple) may defer to a popular search engine upon failure to process an instruction or question. According to Google, this feature reduced typing by 25 %, which amounts to 200 hours of typing saved each day [START_REF] Sullivan | How google autocomplete works in search[END_REF]; to mobile device users this is particularly beneficial. Search started as a task the user would perform all the way to completion, thinking ahead before before submitting; it has now become a rapid-fire tool that can be pulled out at any given moment, to assist the user on the fly in tight situations.

From tags to content queries

The other exciting development for search in recent years is the emergence of contentbased querying. Text is still by far the most dominant search modality; for text retrieval, but also across all types of media, notably images or videos. This relies for the most part on keywords, or text data pertaining to the piece of media -but not the content itself. This severely limits retrieval capabilities in those situations; even if a database is well tagged, which can be prohibitively time-consuming, visual or audio data can never truly be captured by a few keywords or a text description.

This limitation is the motivation behind content-based retrieval methods. Shazam, launched in 2002, is a popular example of service built around such a method: the 1.2. MODELS OF AI-ENHANCED SUPPORT Figure 1.9: Examples from Bing Visual Search. A picture of a kitchen island and a wallaby (left) serve as queries; for the wallaby the species is correct on every search result. Image credits: Hu et al. users directly use their mobile devices' audio input to search, in real time, for a song heard in the background (e.g. in public spaces or during commercials). Google Image Search, TinEye and Bing [HWY + 18] provide powerful reverse image search features that allow the user to submit their own pictures and find ones that are visually similar. The versatility of this tool is quite overlooked: by retrieving, this can identify objects, places, people, fraudulent postings -often down to very fine-grained details (Figure 1.9).

Outside of publicly available tools, content-based retrieval is already deployed in a multitude of scenarios. Youtube, the largest video content platform, systematically reviews the audio in user-submitted content (Figure 1.10), searching for unauthorized use of copyrighted songs -this is referred to as ContentID. Twitch currently uses a similar procedure for recordings of livestreams, automatically cutting out the audio in parts featuring DMCA-protected songs in the background. Uber uses a technique called Locality-Sensitive Hashing [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF] in order to retrieve fraudulent trips. Digimarc, Ivitec are other lesser known actors in the content control space. Although the inner workings of these techniques were never made public, monitoring and recognizing content on this scale inevitably requires quickly sifting through very large video databases in an automatic manner.

Potential clinical applications

Dynamic behavior and rich content understanding are two pillars of modern search, making it a highly versatile and expressive tool for investigating content. The surgeon, the surgical staff or the personnel in charge of the OR control tower mentioned in 1.2.1.2 could greatly benefit from the ability to rapidly access and explore a large database of surgical recordings. For reasons mentioned in 1.1.3, this process should 1.3. DATA interfere as little as possible with the actual surgical task at hand. One way to achieve this is to directly plug live video feeds from the OR into a content-based retrieval algorithm, thus removing the need for the surgeon to interrupt their course of action to formulate queries. This "surgical video recommender system" would act as a dynamic and responsive reference tool, fit not only for surgical education or indexing, but even for intraoperative decision support (Figure 1.11). As it is the case for current reverse image search services, this tool may be used as an always accessible, all-purpose recognition utility, presenting all the information attached to the retrieved videos. Depending on the system's performance, this information could range from broade.g. surgical phase -to very fine-grained, such as critical events or surgical actions.

Data

Clinical application ideas suggested in the previous section require powerful surgical activity understanding algorithms; the data at our disposal for developing those is presented in the following section.

Laparoscopic video data collection

In conventional or open surgery, the tissue covering the surgical site is cut open with an incision large enough to provide the surgeon full unobstructed view, as well as direct access for the hands and surgical instruments. For instance, the incision for open cholecystectomy is usually at least 20cm long [BMS + 11]. In contrast, laparoscopic surgery relies on one or several very small (less than 3 cm) incisions of the abdominal wall called ports, fitted with trocars. After general anesthesia, a preliminary phase establishes the pneumoperitoneum: the abdominal cavity is insufflated with carbon dioxyde in order to create space for the instruments, which are then inserted through the trocars. Two main types of instruments are employed: mechanical (graspers, staplers, scissors ...) and energy-based (hook, bipolar grasper, monopolar cautery devices), with the latter requiring a dedicated power generator in order to deliver the heat necessary for dissection and cauterization. A laparoscope -an optical fiber imaging device -is inserted as well, showing the anatomy and the instruments to the surgeon via a separate monitor. While a wide variety of signals can be collected from those procedures -such as RFID tracking data or energy-based tool usage [START_REF] Parlak | Introducing RFID technology in dynamic and time-critical medical settings: Requirements and challenges[END_REF][START_REF] Malpani | System events: readily accessible features for surgical phase detection[END_REF], the laparoscopic video feed stands out as the richest and most comprehensive by far. For this reason we chose it as our source of data for studying surgical workflow. Data collection has been made possible for this research by a joint effort from the Image-Guided Surgery Institute of Strasbourg (IHU Strasbourg), the Research Institute against Cancers of the Digestive Tract (IRCAD) and the Nouvel Hôpital Civil de Strasbourg (NHC). Surgeries were conducted at the NHC; the IRCAD, an international research and training institute for minimally invasive surgery, collected video recordings of those between 2015 and 2020 for research purposes. Researchers from team CAMMA and hepato-biliary surgeons affiliated with IHU Strasbourg selected videos and applied various types of annotations to generate several anonymized datasets for surgical workflow understanding. However, certain crucial traits are shared across workflows of many surgeries. Two GI surgeons from IHU Strasbourg collaborated to define a common set of surgical situations called critical events (Figure 1.13), found in 6 different types of laparoscopic procedures: cholecystectomy and gastric bypass, as well as eventration, hernia, nissen and sigmoidectomy. This led to the CEV64 dataset, generated during this thesis. Beginning and end for each event were marked in 64 videos, which helped generate a CHAPTER 1. INTRODUCTION Figure 1.13: Examples of critical events in surgery, from the CEV64 dataset. database of 20000 surgical video clips of approximately 30 seconds each. Annotations were applied using MOSaiC, an internally developed tool with dedicated features for temporal annotation. The 11 reported events are detailed in table 1.3.

Cholec120

The gap with large-scale video datasets

Video datasets employed within the rest of the computer vision community present major differences with the ones just mentioned. This is often a concern when adapting methods trained on those sources to surgical content. A comparison with a few prominent datasets is shown in table 1 The first major difference is duration; generic activity videos tend to be a lot shorter, sometimes lasting only a few seconds. This adds convenience for training; the content is a lot simpler and visually distinct as well. Surgeries often exceed featurelength films in terms of length, with many phases, events and actions taking place over their 140-minute average span. Processing them in a way that accounts for the entire workflow is a difficult challenge.

Accurately annotating this type of data requires highly specific clinical knowledge; which is why in our case this was done by experienced gastrointestinal or hepato-biliary surgeons and surgical fellows. As a result the number of available annotated videos is quite low, only reaching 204 for cholec80, bypass40 and CEV64 combined.

Finally, the appearance of laparoscopic video feeds is challenging in itself, as evidenced by Figure 1.14. Scenes from inside the abdominal cavity tend to have a high degree of similarity with each other. The field of view of 62 • [WKK + 20] is quite narrow; oftentimes relevant anatomy or instruments exit the frame. Visual landmarks for specific phases or events can be very sparse: for example cutting the cystic duct in cholecystectomy is often brief, with scissors appearing in the frame only for a few seconds. Recording quality is routinely affected by smoke, blood splatters and jittery motion as well as inconsistent lighting.

The big picture: Endocorpus

Endocorpus is the CAMMA team's first very-large-scale video dataset, containing the previously mentioned surgical datasets as well. In total, 1558 full-length recordings of surgeries are present, for a combined runtime of 3700 hours. 12 types of surgical procedure are featured; two of those, robotic sleeve gastrectomy and robotic bypass, involve Intuitive Surgical's Da Vinci. As such, this dataset therefore covers most of abdominal endoscopy, containing an amount of experience equivalent to several surgeon lifespans. expert-annotated data might be ill-advised: assuming surgical video data collection is to expand and become more systematic, ramping up manual annotations accordingly would come at an excessive cost, while leaving large swaths of data underused and underexplored would be a waste.

Contributions

Our goal is precisely to overturn this situation: we aim for semi-or self-supervised methods in order to avoid the dependency on manual labels, while providing the means to take advantage of the unannotated data and navigate it in a way that serves realtime, context-aware support in the OR. We propose two main paths for achieving this: the first is automatic annotation, an obvious alternative to expert-generated labels that is far more scalable; this is done for surgical phases, to provide a broad and standardized understanding of the context. The second is search, in the form of unsupervised video retrieval, capable of instantly delivering a richer and more expressive description of a captured surgical scene. The final vision for the innovations we propose in terms of context awareness is summed up in Figure 1.16, in the form of a control tower for the OR powered by large amounts of unlabelled data.

Listing them in detail, our first contribution is a method that leverages the unannotated data through automatic annotation of surgical phases, with a combination of strong offline predictor and weak real time predictor. This new semi-supervised approach is a breakaway not only from traditional phase recognition [TSM + 16, JDC + 18, JLD + 19] with full supervision, but also from the other semi-supervised methods in this space [YMMP18, FJM + 18] since it enriches the unannotated data instead of only using it for pretraining.

Our second contribution is a new method for a problem never tackled before: con-CHAPTER 1. INTRODUCTION tinuous video retrieval in real time. As opposed to previous video retrieval approaches [ZWHC16, SZL + 18, WLG + 17, WHG + 19, LCL + 19], ours is the very first tailored for live video sources; as such, we evaluate it with a new protocol reflecting livestreaming conditions. In the absence, at the time, of an adequate very-large-scale surgical dataset, and also in the absence of a method built for this specific task in the general vision community, we first demonstrated our approach on two generic activity datasets. Our third contribution is the application of continuous video retrieval to a large, more complex video dataset of surgical recordings. This is the first study of its kind in terms of scale, surpassing the few works on surgical video retrieval [DQL + 14, PS18] by a large margin in that regard. We show that content relevant to an ongoing surgical procedure from a massive database can be retrieved in real time. We also demonstrate the all-purpose ability of video retrieval, by using the same unsupervised model to return search results relevant for critical events in six types of procedures, as well as for phases in both cholecystectomy and bypass.

Our fourth contribution extends the previous retrieval method by introducing uncertainty awareness for video hashes: by adding compressed uncertain bit patterns to the database, the relevance of retrieval results is improved, while keeping additional space and time expenses to a minimum.

Finally, our last contribution is the generation of large-scale and very-large-scale datasets for activity recognition in surgery. In particular, our critical event dataset CEV64 is the very first of its kind.

Outline

The work presented in this thesis is organized according to the following outline:

• Chapter 2 provides a structured overview of previous publications relevant to our work.

• Chapter 3 demonstrates a semi-supervised method for surgical phase recognition relying on automatic annotation, using unlabeled surgery videos.

• Chapter 4 lays down the theoretical foundations for learning hash functions for content-based retrieval.

• Chapter 5 presents a methods for content-based video retrieval in real time, on generic activity large datasets from the general computer vision community.

• Chapter 6 brings the content-based video retrieval task to a very-large-scale surgical dataset and extends the previous methods by managing the uncertainty of database entries in a lightweight fashion.

CHAPTER 2

Related Work

Video Activity Understanding

Model architectures & general activity recognition

Video as a data format is particularly challenging to process in recognition tasks. High dimensionality already is a concern when it comes to static images; for a typical [224, 224, 3] RGB image used in CNN models the number of dimensions is 150528. For a single second of video at 25 frames per second with the same frame size, this number goes up to 3763200. This is without even considering the presence of an audio track; multimodal data is a rich and active research area of its own, which we will not go into here.

In addition to the high dimensionality of videos, the temporal information is a major source of difficulty as well. Just like the words in a sentence, the succession between frames matters, and determines motion and event logic in the video. An adequate video model should ideally learn those temporal dependencies in order to correctly make predictions.

Extraction -aggregation approaches

Early approaches have attempted to aggregate 2D static convolutional neural networks for video data, applying them to each frame separately. Karpathy et al. [KTS + 14] presented a few elementary aggregation possibilities through pooling. A two-stream approach was proposed by [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF], with, in parallel, one CNN processing RGB pixel data and another procesing the optical flow. [WXW + 16] reuses the two-stream architecture with snippets sparsely sampled across the video. In the examples above, there is no sequence modeling; the aggregation is not sensitive to the order between the frames.

Recurrent Neural Networks (RNN) are a type of DNN dedicated to sequential inputs. A function commonly referred to as the recurrent cell or recurrent unit is called at each timestep of the input, forwarding a state value taken into account during the next call. This enables sharing parameters across timesteps, as well as receiving inputs of arbitrary length. The recurrent unit from the original RNN, proposed in [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF], was prone to issues, namely vanishing and exploding gradients. To counteract those, [START_REF] Hochreiter | Long short-term memory[END_REF] introduced the Long Short-Term Memory unit, which made RNNs viable for training on longer sequences. [START_REF] Graves | Framewise phoneme classification with bidirectional lstm and other neural network architectures[END_REF] later proposed the bidirectional LSTM recurrent neural network. With two LSTM-RNNs processing the input sequence in opposite orders, both types of temporal dependencies can be captured: present to past and present to future.

The idea of combining this architecture with CNNs for video tasks was introduced by [DHG + 15]. The CNN maps video frames to visual feature vectors, which the LSTM then processes as a sequence, learning the temporal dependencies within it. End-toend [START_REF] Yengera | Less is more: Surgical phase recognition with less annotation through self-supervised pre-training of cnn-lstm networks[END_REF] training of the two components is possible, however with only a very limited small number of frames at each training iteration due to hardware constraints. Very long videos can be downsampled and have their frames extracted separately to facilitate training [TSM + 16].

The TCN [START_REF] Lea | Temporal convolutional networks: A unified approach to action segmentation[END_REF], or Temporal Convolutional Network, is a faster alternative to the LSTM. Its architecture featuring stacked convolutions is inspired by 2D CNNs, 2.1. VIDEO ACTIVITY UNDERSTANDING except with 1D temporal convolution kernels.

3D CNN

[TBF + 15] first introduced the concept of 3D Convnets. The architecture, stacking convolutions, ReLu activations and max pooling operations, is similar to ordinary 2D CNNs. The convolution operations, however, are performed using 3D 3x3x3 kernels over height, width and time. As such, it is capable of learning 3D features from video clips. [START_REF] Qiu | Learning spatio-temporal representation with pseudo-3d residual networks[END_REF] brought the idea of residual connections first found in ResNet [START_REF] He | Deep residual learning for image recognition[END_REF] to 3D CNNs. [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] used a pretrained Inception model, and expanded its convolution kernels in the time dimension to make them video-capable. The authors also offered a two-stream version of their model, with optical flow and RGB data. In [START_REF] Wang | Nonlocal neural networks[END_REF], a non-local 3D Resnet is presented; it is capable of learning long-range dependencies that would be overlooked by ordinary 3D CNNs due to their limited recptive field. [START_REF] Feichtenhofer | X3D: expanding architectures for efficient video recognition[END_REF] refined the process for expanding a Convnet from 2D to 3D. The authors of [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] explored options for mixing 2D and 3D convolutions within the same model, resulting in a more efficient and accurate model called S3D. Using a feature aggregation approach, similarly to the ones previously mentioned, [GCDZ19] used I3D as a feature extractor; the aggregation layer employed is a Transformer model [VSP + 17]. This recently developed sequence model relies on a scaled dot product attention mechanism to inspect relationships between any two items in the input sequence. The main benchmarks used for publications with 3D CNNs were Kinetics [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] and UCF-101 [START_REF] Soomro | UCF101: A dataset of 101 human actions classes from videos in the wild[END_REF], with action recognition as the task.

Early activity recognition

In ordinary action recognition, only the output of the model from a complete video observed all the way to the end is considered. This ensures the model takes all the visual information available into account; however this may not be a realistic use case, especially if it is meant to be used in real time. The task of early action recognition (EAR) works with this constraint in mind; the model is asked for a prediction at various stages of progress throughout the video. This far increases the task's difficulty, especially at the very beginning of the video since the available visual information is very minimal.

Several methods [ASS + 17, HZM + 19, MSS16] proceed by incorporating elapsed time or progression to inform the training process. [ASS + 17] trains an LSTM model with a temporally weighted loss enhancing the importance of predictions made early on in the video. [HZM + 19] proposes a method for early recognition based on soft labels at different levels of video progress.

A different type of approach for early recognition tasks is to synthesize the content in the video's future: [START_REF] Rodríguez | Action Anticipation by Predicting Future Dynamic Images[END_REF] attempts to generate future video frames using a DCGAN [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF] model. [START_REF] Gammulle | Predicting the future: A jointly learnt model for action anticipation[END_REF] employs video representations fed to generator models trained to synthesize future frame embeddings.

Teacher-student distillation methods train a student model that has not seen future frames to replicate representations learnt by a teacher model that has. [KTF17] applies a similar principle to representations from a 3D CNN. A different method introduced in [WHL + 19] uses another distillation approach: it involves training a forward-directional LSTM to match at each timestep the hidden states of a trained bidirectional LSTM. An approach incorporating reinforcement learning is presented in [START_REF] Weng | Early action recognition with category exclusion using policy-based reinforcement learning[END_REF]. Here an agent applies a mask to the output probabilities, allowing or forbidding classes depending on the time.

Methods in surgical video analysis

The problems studied in the field of Surgical Activity Understanding include recognizing surgical phases, tool usage, events, actions and timings in surgical procedures.

Before the introduction of deep learning to the field, methods mostly relied on traditional ML models processing handcrafted features, sometimes combined with sensor data indicating, for instance, surgical tool usage [START_REF] Blum | Modeling and segmentation of surgical workflow from laparoscopic video[END_REF]. However, DNN-based models have taken center stage for the most part, replacing former video analysis methods as it did in many other domains.

Surgical phases form the foundation for analyzing workflows in surgery. Lalys et al. + 18] improved on the CNN-RNN combination using a boosting strategy. MTRCNet-CL [JLD + 19] exploits the correlation between tool usage and surgical phase; for instance the specimen bag only appears in later phases, as the gallbladder is placed there only after it is dissected. The correlation loss term attempts to teach the model this type of relationship. Czempiel et al.'s TeCNO [CPK + 20] were the first to introduce temporal convolutional networks to surgical phase recognition. All the works mentioned so far using deep neural networks for phase recognition did so on cholecystectomy videos, which has a fairly simple workflow. Ramesh et al.'s MTMS-TCN [RDG + 21] was the first to bring phase recognition to gastric bypass; a much more complex and non-linear type of surgery with many phases themselves composed of multiple smaller steps.

Alternatives to full label supervision

The canonical setup for training deep neural networks involves a large, fully annotated dataset, with the full ground truth available for the task to train the model for. This section presents alternatives to this fully supervised setup.

Weak and semi supervision

Weakly supervised learning relies on supervision signals containing less information than actual labels corresponding to the actual task to perform; when those signals are much easier to procure than fully fleshed out annotations, this type of method is particularly adequate.

In videos, a common weakly supervised learning task is action localization. In contrast to video-level action recognition done on benchmarks such as Kinetics, where the model assigns a prediction to an entire video clip, action localization involves finding, within a video, frames where the action actually takes place. Achieving this without any frame-level annotations, with only video-level tags as the weak supervision source, is a challenging task attempted in several works [RKG17, WXLG17, PRRC18, NRF19, ASNS20, MGVY21, BLG + 15].

Outside of videos, another form of weak supervision involves noisy labels. Mislabeled data, while non-existent in major computer vision benchmarks such as ImageNet, can be a threat in real-life situations, with annotations from unreliable public sources.

Unsupervised representation learning

Unsupervised learning or self-supervised learning methods work from a completely unannotated training set. The condition for such a method's success is to have the model understand the underlying organization of the data purely based on its content, learning a representation that accounts for this organization. The training task chosen to teach this representation is referred to in the literature as the proxy or pretext task.

We present a few methods for static image data first. Noroozi et al. [START_REF] Noroozi | Unsupervised learning of visual representations by solving jigsaw puzzles[END_REF] introduced the jigsaw pretext task, consisting in identifying a permutation applied to the tiles of an image. Another work [START_REF] Noroozi | Representation learning by learning to count[END_REF] from the same authors trained a model to count visual primitives in images without labels, using a visual consistency rule enforced across tiles in the image. Zhang et al. [START_REF] Zhang | Colorful image colorization[END_REF] trained an autoencoder on images converted to grayscale, to reconstruct the original color images. BYOL or Bootstrap Your Own Latent was developed by Grill et al. [GSA + 20]; in this method the model has to predict its own representation of a transformed image using the original. SimCLR introduced by Chen et al. [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF] combined multiple data augmentation methods with a contrastive cross-entropy.

For video data, Srivastava et al. [START_REF] Srivastava | Unsupervised learning of video representations using lstms[END_REF] trained an LSTM autoencoder to learn video representations. Wang et al. [uns] used a handcrafted method to define image patches for the network to track across video frames. In Misra et al.'s work [START_REF] Misra | Shuffle and learn: Unsupervised learning using temporal order verification[END_REF], the model is trained to validate the temporal order of a sequence of frames. Vondrick et al. [VSF + 18] introduced a video colorization task; unlike the original image colorization task [START_REF] Zhang | Colorful image colorization[END_REF], the image to colorize is not the input but a further frame in the video.

Distillation by teacher supervision

Distillation approaches, for the most part, are not conceived with data scarcity issues in mind like the approaches mentioned previously. The objective for most of those methods is model compression, i.e. transferring the behavior of a large-capacity model to another one, with fewer parameters and lower hardware requirements. The large model in this framework is referred to as the teacher, while the smaller one is called the student. Wang [START_REF] Wang | Knowledge distillation and student-teacher learning for visual intelligence: A review and new outlooks[END_REF] as well as Gou et al [START_REF] Gou | Knowledge distillation: A survey[END_REF].

Outside of model compression, a few publications have used similar distillation concepts for other purposes; for example as a form of weakly supervised learning, or to condition specific behaviors from the student model. In Radosavovic et al's work [RDG + 18], distillation is used in a semi-supervised setup, performed from the ensemble to the student on the unlabeled data. The role of distillation in Wang's work [WHL + 19] on early action recognition is to enforce anticipation for the student.

ALTERNATIVES TO FULL LABEL SUPERVISION

Uses in medical context

A common obstacle in the fully supervised training of DNNs is the limited amount of annotated data available. This is especially true for surgical videos, which are difficult to acquire, and require expert medical knowledge for annotations. For surgical phase recognition under semi supervision, Bodenstedt et al. [BWK + 17] used a frame sorting task on unannotated videos. Funke et al. [FJM + 18] employed a method called second order temporal coherence to pretrain the visual feature extractor in their model, enforcing distance constraints in embedding space that reflect the temporal distance between frames of the same video. Their experiments used the cholec80 dataset for cholecystectomy phase recognition; with 60 total videos available for training, annotations were limited to 60, 40 and 20 videos. In Yengera et al.'s [START_REF] Yengera | Less is more: Surgical phase recognition with less annotation through self-supervised pre-training of cnn-lstm networks[END_REF] work, remaining time and progress regression were used as unsupervised pretraining tasks. From the cholec120 dataset, 8 to 80 annotated videos were used for phase recognition training.

Weak supervision has been employed for surgical instrument detection on cholec80, using binary presence annotations only [START_REF] Innocent Nwoye | Weakly supervised convolutional LSTM approach for tool tracking in laparoscopic videos[END_REF][START_REF] Vardazaryan | Weakly-supervised learning for tool localization in laparoscopic videos[END_REF]. A form of distillation was shown in Kannan et al.'s work [KYM + 20], to encourage anticipation in real-time surgery type recognition tasks.

Retrieval

The task of retrieval is, at its core, the task of learning representations that are adequate for searching. We break down the corresponding methods into two main types based on the representations used; then we examine a few uses of hashing in the medical community.

Embeddings

Embeddings are a byproduct of any DNN training process (see 4.2). Those compact vector representations are trained to incorporate rich content and to have good geometrical properties; it is therefore natural to use them for retrieval.

Image retrieval

For image retrieval, Hoang et al. [START_REF] Hoang | Selective deep convolutional features for image retrieval[END_REF] proposed a scheme for generating embeddings for retrieval, by selecting and aggregating convolutional features from a VGG model. Jimenez et al. [START_REF] Jimenez | Class-weighted convolutional features for visual instance search[END_REF] used class activation maps to add weight to more discriminative features in their embedding construction process. Liu et al. [LYV + 19] used Graph Convolutional Networks to compute a similarity score between images, serving as their basis for learning seachable embeddings. In Revaud et al.'s work [START_REF] Revaud | Learning with average precision: Training image retrieval with a listwise loss[END_REF], mAP, the metric generally used for retrieval evaluation, is approximated by a differentiable function and learnt by their model.

Video retrieval

Content-based video retrieval was performed by [START_REF] Xu | A discriminative CNN video representation for event detection[END_REF] with features extracted from a VGG CNN pretrained on ILSVRC 2014. The features were pooled using either 2.3. RETRIEVAL Fisher vectors or VLAD. Experiments using CNN embeddings were also performed by Kletz et al. [START_REF] Kletz | Evaluation of visual content descriptors for supporting ad-hoc video search tasks at the video browser showdown[END_REF], and showed that those yielded higher retrieval performance than handcrafted features.

Hashing

The previous principle of looking for compact and discriminative representations of large data is taken by hashing to an extreme level: instead of floating-point vectors with a few thousand components, hashing looks for representations in the form of binary arrays with only a few hundred entries. We present a few methods for static images first, followed by methods for video content.

Image hashing

Approaches outside of deep learning

A number of methods were originally developed without deep neural networks, although the hash functions described can be applied to features extracted by DNNs.

Locality-Sensitive Hashing [AI08] is a highly popular algorithm used in a wide variety of application scenarios, including genome sequencing [BKC + 14] and fraud detection [START_REF] Ni | Detecting abuse at scale: Locality sensitive hashing at uber engineering[END_REF]. This method however is completely data-independent, using random projections to build the hash function. Since then, a number of methods have attempted to tailor this function to the data to hash. Weiss et al. introduced Spectral Hashing [START_REF] Weiss | Spectral hashing[END_REF], a method based on a PCA of the data. Iterative Quantization [START_REF] Gong | Iterative quantization: A procrustean approach to learning binary codes BIBLIOGRAPHY for large-scale image retrieval[END_REF], discovered by Gong et al., relies on a rotation of the data that minimizes the quantization error. Spherical Hashing[HLH + 12] uses binarization functions with spherical separation surfaces instead of hyperplanes, and optimizes the position of the sphere centers, referred to as pivots.

Hashing with deep neural networks

Liong et al. [LLW + 15] first introduced two hash functions built around a multilayer perceptron on top of GIST [START_REF] Oliva | Modeling the shape of the scene: A holistic representation of the spatial envelope[END_REF] features, one supervised and another unsupervised. HashNet [START_REF] Cao | Hashnet: Deep learning to hash by continuation[END_REF] used AlexNet and ResNet CNNs with a continuous relaxation method, increasing the sharpness of a sign function approximator over the course of training. Deep Cauchy Hashing is a contrastive method [START_REF] Cao | Deep cauchy hashing for hamming space retrieval[END_REF] relying on a modified AlexNet and a pairwise loss based on a Cauchy distribution. DistillHash uses noisy similarity labels [YLD + 19] based on embedding distance between data pairs to learn bitcode assignments. HashGAN [START_REF] Cao | Hashgan: Deep learning to hash with pair conditional wasserstein GAN[END_REF] incorporates synthetic images generated by a GAN to augment the training data. K-Nearest-Neighbors Hashing [START_REF] He | K-nearest neighbors hashing[END_REF] takes advantage of the neighborhood structure in embedding space to binarize based on an optimal space partition. Wu et al. [WDL + 19] introduced a method for incremental hashing, in the sense that expanding the database does not require complete retraining of the hash function on the full dataset.

Video hashing

A number of methods [LLTZ17, WLG + 17, WHG + 19] for video hashing are poolingbased: a fixed number of frame representations is generated, then combined with

Retrieval in medical computer vision

In medical computer vision, most works on content-based retrieval focus on diagnostic medical imaging [CCL + 18, PBW + 19, SPCR20, GVYY17]. One from Chen et al. [START_REF] Gu | Unsupervised feature learning for endomicroscopy image retrieval[END_REF] involves hashing, on a database of chest X-ray images.

A few works have used intraoperative video data: Droueche et al.[DQL + 14]'s video retrieval method is based on MPEG-compressed video representations and handcrafted features. Amanat et al's [AIK + 18] performed retrieval based on PCA applied to SIFT features. Funke et al. retrieved still frames from cholec80, however this only was a qualitative evaluation of their features trained with temporal coherence[FJM + 18]. Petscharnig et al. [START_REF] Petscharnig | Binary convolutional neural network features off-the-shelf for image to video linking in endoscopic multimedia databases[END_REF] tackled the problem of image-to-video linking, i.e. retrieving the video source of a still frame. Their study was done on a dataset of gynecologic endoscopies.

Thesis Positioning

Our objective is to introduce new uses for the unannotated data which will directly or indirectly assist the surgeon in navigating the surgery in the operating room, and do so in real time.

An overview of the previous work using unannotated videos for surgical activity understanding tasks shows that the role of these videos was fairly limited. For the most part, they were used as pretraining fodder for visual feature extractors: frame sort-2.4. THESIS POSITIONING ing [BWK + 17], temporal distance comparisons [FJM + 18], remaining time [START_REF] Yengera | Less is more: Surgical phase recognition with less annotation through self-supervised pre-training of cnn-lstm networks[END_REF]. While those methods proved to be efficient for enhancing the downstream task of surgical phase recognition, the vast pool of unannotated videos they used served no further purpose beyond a self-supervised pretext task. No attempt was made to understand this data, navigate it and turn it into more valuable information for future use. Self-training [RHS05, RDG + 18] is a semi-supervision modality addressing those shortcomings, since it generates synthetic labels for the unannotated data -however to the best of our knowledge, no application to surgical activity recognition or even general video activity recognition existed at the time. The real-time usability / recognition performance has also never been adequately addressed either. Pointed out by [START_REF] Putra | Vision-based approaches for surgical activity recognition using laparoscopic and RBGD videos[END_REF] when observing a performance increase upon replacing the standard LSTM by one that is bidirectional, no attempt has been made in order to reduce this performance gap for real-time use. The method we propose [START_REF] Yu | Learning from a tiny dataset of manual annotations: a teacher/student approach for surgical phase recognition[END_REF] in the next section addresses all those issues , by introducing a semi-supervised self-training scheme using both LSTM and bidirectional LSTM in a complimentary manner.

Enriching the unannotated data is one way of using it; providing the tools to explore it and efficiently search through it is another, which can be done with video hashing. Literature on this topic is quite limited [LLTZ17, ZWHC16, SZL + 18, WLG + 17, WHG + 19, LCL + 19]. The main shortcoming of all presented approaches is to consider video retrieval from a purely static standpoint. Meanwhile text-based search has evolved into a dynamic tool, capable of adapting to the anticipated course of events in order to be used out of the pocket in the middle of any task. One key concern is the sampling scheme employed: out of all the frames in a video, a small predetermined number of evenly spaced frames is considered, independently of the video's duration. The extracted information is therefore very sparse, and in the case of a real-time video source, needs to be constantly regenerated from the beginning of the video. Lack of anticipation is another concern: all those methods assume the entire video from beginning to end is available as the search query, and therefore no content is missing. In the case of livestreams, this working hypothesis is false. Our method [START_REF] Yu | Encode the unseen: Predictive video hashing for scalable mid-stream retrieval[END_REF] addresses both these concerns, making video hashing both incremental and predictive.

The existing work on video retrieval for surgical videos is minimal; Droueche et al.'s [DQL + 14] work on retrieval for cataract surgery videos relied on handcrafted features from compressed videos instead of DNNs operating on the actual pixel data. The scale of the experiments conducted was fairly small, using datasets of 23, 250 and 69 videos. The training set was used as the database, which deviates from the stricter protocol enforced in video hashing publications [LLTZ17, ZWHC16, SZL + 18, WLG + 17, WHG + 19, LCL + 19]. No hashing was involved either; retrieval was based on floating-point values. Retrieval times of 9 minutes were mentioned, which limits real-time usage. Our work, on the other hand, brings DNN-based hashing to a verylarge-scale surgical video database, ensuring real-time video retrieval efficiency with delays of a few seconds at most.

CHAPTER 3

Semi-supervision for real-time surgical phase recognition Between the standard approach of full supervision, and self-supervision where no annotations are available for training, semi-supervision occupies the middle ground, with methods relying on partially annotated datasets. With phase annotations being currently scarce, it is natural to consider methods that facilitate their production. Assisted annotation, explored by research efforts simultaneous to ours in a study on two cholecystectomy videos, is an option [LRM + 19]. Automatic annotation is another which we study here, allowing both increased phase recognition performance and exploration of the unannotated data.

Objectives

The work presented in this chapter is a first attempt at answering the question "what can be achieved in the OR with the unannotated endoscopic video data?". Here we tackle the problem of surgical phase recognition in cholecystectomy, a staple in surgical activity understanding. As shown in Chapter 1, a fraction of the cholecystectomies registered in our database come with phase annotations: 120 videos are currently annotated with phases, while over 500 are registered in Endocorpus. This situation is therefore an excellent fit for a semi-supervised method. In the following experiments we recreate those conditions of annotation scarcity on a smaller scale: assuming 80 videos are at our disposal, how do our methods perform when only 20 out of those are annotated? How do they perform when this number drops down to 10, 5, 3, all the way down to a single video?

Methods

Data preparation

The chosen dataset for this task is cholec120, containing 120 recordings of laparoscopic cholecystectomy performed at Strasbourg's Nouvel Hôpital Civil. We reserve 30 for testing and 10 for validation, leaving N = 80 videos to choose from for training.

As shown in Figure 3.1, the workflow is mostly linear. A few videos do not feature a CHAPTER 3. SEMI-SUPERVISION FOR REAL-TIME SURGICAL PHASE RECOGNITION preparation phase, starting directly with the Calot triangle dissection phase. The order between phases 5 (gallbladder packaging) and 6 (cleaning coagulation) is occasionally reversed. However, despite the dataset's uniformity with respect to phase ordering, workflow greatly varies within the dataset: video duration considerably changes from one case to another, with 956s of standard deviation around the 2287s average. The shortest video only lasts 741 s -barely over 10 min-while the longest lasts 5987s or over an hour and a half. When selecting small numbers of annotated videos for training, it is therefore important that the selection has similar duration statistics. Even then, the selection process should be repeated in order to mitigate the effect of potential outliers.

In the following lines, we will refer to:

E = {(V 0 , A(V 0 )), (V 1 , A(V 1 )), ..., (V N -1 , A(V N -1 ))} , (3.1)
as the initial set of 80 manually annotated videos to choose from, V k and A(V k ) being a video and its ground truth annotations respectively. Considering the voluntarily low number of annotated videos selected for training (from 20 down to 1), we sample 3 non-overlapping mini-training sets of every size in order to prevent biased results coming from the selection process, and ran our series of experiments independently for each mini-training set. In an effort to match the original training set in terms of video duration statistics, we divide the 80 videos into duration quartiles Q1 to Q4, then randomly sample videos from Q1, Q2 Q3, and Q4 with a 20/60/20 ratio respectively. For mini-training sets of only one video the single choice is limited to Q2 Q3 in order to avoid outliers. The mini-training sets are referred to as:

E i,j = {(V k , A(V k )), ...} , (3.2)
where the first index i ∈ {1, 3, 5, 10, 20} indicates the size of the set of ground truth labeled videos employed, and the second index j ∈ {0, 1, 2} denotes the first, second or third repeat of the experiment for that particular size.

Teacher & student models

We present two model architectures for surgical phase recognition: the CNN-LSTM and the one newly introduced in our work, the CNN-biLSTM-CRF. The choice between the two is subject to a tradeoff between real-time usability for the first, and enhanced recognition performance for the second; those characteristics are directly tied to their distinct architectures, which we discuss in the following subsections. Using them in our setting as teacher (CNN-biLSTM-CRF) and student (CNN-LSTM) ultimately solves this tradeoff.

DNN components

Both architectures rely on a combination of spatial and temporal artificial neural networks. The spatial component in both is a ResNet-50 V2 CNN [START_REF] He | Deep residual learning for image recognition[END_REF], serving as the visual feature extractor on RGB frames: for one 256 × 256 × 3 input, a 2048dimensional vector representation is generated.

The sequence of feature vectors extracted from a video is then aggregated by a recurrent neural network (RNN). In the case of the student, the chosen RNN is built around a forward-directional LSTM. At any given timestep, all the student needs for inference is the feature vector from the current frame as well as the previously computed cell state and hidden state. Functioning in real time is therefore entirely within its capabilities. The teacher, however, feeds the feature vector sequence to a RNN based on a bidirectional LSTM [GS05], i.e. a pair of LSTMs, one chronological and one reverse. Its output at any given timestep depends on the current feature vector for the current frame and the chronological LSTM's previous states, computed using all past instants. It also depends on the reverse chronological LSTM's previous state, which requires input features for all future instants. This property of the biLSTM is a double-edged sword; because of it the teacher cannot be used intraoperatively, i.e. before the actual end of the surgery. On the flipside its predictions factor in much more useful information than the student, and are more likely to be correct.

Transition logic

A single fully connected layer projects the sequence of outputs from the temporal model to a sequence of per-class log-probabilities or logits. This is the case for both the teacher and the student. However, the student has its predictions decoded with a simple argmax, independently from timestep to timestep. Since the teacher is forced to see the entire sequence, we take advantage of this by incorporating an additional layer, enabling it to learn the transition logic between phases. This is the role played by the linear chain conditional random field or CRF in the model, the inner workings of which we describe here.

Given a sequence of logits S = (s 0 , ..., s T ), for any given timestep t and class index k we note the k th entry of s t as s t [k]. Let Θ be an N c × N c real-valued matrix, with entries noted as Θ[i, j] for class indices i, j.

The score of any sequence of tags (i.e. predicted classes) Y = (y 0 , ..., y T ) can then be defined as:

CHAPTER 3. SEMI-SUPERVISION FOR REAL-TIME SURGICAL PHASE RECOGNITION C(S, Y, Θ) = T t=0 s t [y t ] + T -1 t=0 Θ[y t , y t+1 ].
(3.3)

The first sum collects unary potentials, i.e. terms associated with single sequence elements, while the second one collects binary potentials resulting from transitions.

The trainable parameter of the model is Θ, called the transition matrix. Using the definition of the score C, we are able to define the likelihood of a tag sequence as:

p(Y |S) = e C(S,Y,Θ) U ∈ 1,Nc T +1 e C(S,U,Θ) , (3.4)
which can be seen as a softmax value for Y over all possible tag sequences U . The scaling factor Z = U ∈ 1,Nc T +1 e C(S,U,Θ) is also called the partition function. Bruteforce computation of Z is O(N T +1 ), and generally intractable. A more adequate way to carry out this computation uses dynamic programming, via the forward algorithm. We can observe:

Z = U ∈ 1,Nc T +1 e T t=0 st[yt]+ T -1 t=0 Θ[yt,y t+1 ] (3.5) = k,n∈ 1,Nc 2 e T t=0 st[k]+ T -1 t=0 Θ[k,n] U ∈ 1,Nc T e T t=1 st[yt]+ T -1 t=0 Θ[yt,y t+1 ] (3.6)
This simply factors Z by the contribution of the first item in the sequence. The left-hand term of the product costs O(N 2 c ) operations, and the same factorization can be applied to the right-hand term. Recursive computation of Z in this manner is therefore O((T + 1)N 2 c ). We then employ L = -log(p(Y true |S)) as our training loss, Y true being the tag sequence corresponding to the ground truth.

At inference time, the CRF returns the best scoring sequence Y opt . This is also computed using dynamic programming, with the Viterbi algorithm. We define:

δ τ (k) = max U ∈ 1,Nc τ +1 ,uτ =k ( T t=0 s t [u t ] + T -1 t=0 Θ[u t , u t+1 ]) (3.7)
This is the maximum scoring sequence up to timestep τ ending with tag k. Then:

δ τ (k) = s τ (k) + Nc n=1 δ tau-1 (n) + Θ[n, k] (3.8)
Recursive computation of all the δ values costs, again, O((T + 1)N 2 c ). The best path can be found by recording the tags corresponding to each δ in a separate array to backtrack from.

Training

In all of the following experiments, the Resnet-50 CNN is initialized with ImageNet pretrained weights. Test accuracy on ImageNet for those weights reaches 75.6%. The teacher model's CNN is first pretrained with only one fully connected layer on top, on E i,j , directly for phase recognition. Weights from the first and second blocks of Resnet are frozen. Data augmentation is applied using random isometries. Visual feature vectors are then extracted from E i,j using the pretrained CNN.

The biLSTM -CRF is then trained end-to-end on the extracted features with untruncated backpropagation through time across the entire video, with binary crossentropy as the loss function.

Using the trained biLSTM -CRF, we generate new annotations for videos in E\E i,j . This leads to a set of videos with synthetic annotations:

F i,j = (V k , A i,j (V k )), ... . (3.9)
We then define G i,j = E i,j F i,j , which contains all videos from the original training set, and combines a small set of manual annotations with a majority of synthetic labels.

The student CNN-LSTM model is trained in the same two-step manner, this time on G i,j . Hyperparameters used for training are detailed in table 3.1. All experiments are performed using Tensorflow with the Adam optimizer [START_REF] Diederik | Adam: A method for stochastic optimization[END_REF], on servers fitted with Nvidia 1080Ti GPUs.

In order to justify every component in the teacher model, we conduct a series of ablation studies 3.4 by training and evaluating the following models:

• (M1) CNN (obtained from the pretraining step) RECOGNITION • (M2) CNN-CRF

CNN

• (M3) CNN-unidirectional LSTM • (M4) CNN-biLSTM
Temporal models M2 to M4 are trained in the same two-step manner as the proposed CNN-biLSTM-CRF model, referred to as M5.

In order to provide comparison points with the fully supervised approach, the teacher model along with every model featured in the ablation studies are also trained on the original set of 80 manually annotated videos. The only student model mentioned so far is the CNN-unidirectional LSTM, due to its real-time inference capabilities. Another interesting possibility is to also use a CNN-biLSTM-CRF as the student, in order to obtain a stronger offline predictor. To demonstrate the benefits of our approach, we have conducted a total number of 125 experiments, counting all mini-training set sizes and all the models featured in the complementary studies. To test our models, we reported their accuracy (Acc). This metric is valuable in the sense that it measures the amount of time spent making correct predictions. However, it lacks responsiveness to potential deficiencies in less populated classes. For this reason we also reported their precision (Pre), recall (Rec) and F1 score during inference on the test set. Unless otherwise specified, precision, recall and F1 are averaged over the 7 classes. For every metric at a given minitraining set size, we provide the mean and standard deviation over the 3 repeats of the corresponding experiment.

Results

Teacher model ablation studies

Results for every mini-training set size, the proposed teacher model (M5) and models from the ablation study (M1 to M4) are shown in Table 3.2. Directly applying the CRF after the CNN (M2) yields poor results, likely due to temporal noise affecting the logits emitted by the CNN. Temporal models trained on a single video are severely affected by overfitting, and therefore also exhibit subpar performance. With 3 or more manually annotated videos, however, the biLSTM and the CRF deliver significant performance improvements.

The CNN-biLSTM (M4) achieves stronger performance than the CNN-LSTM (M2), although not as much as the full CNN-biLSTM-CRF model (M5), which is consistently the best performer (Figure 3.5). This is observed on all mini-training set sizes except for single videos. As expected, increasing the number of videos improves all global metrics -accuracy, average F1, average precision, average recall -although per-phase precision and recall may fluctuate (Table 3.3). This establishes the CNN-biLSTM-CRF model as the strongest predictor, and therefore the best suited for the role of teacher.

To qualitatively appreciate improvements from the new model, the predictions on six videos from the test set are presented in Figure 3.6: the top three and bottom three of the CNN-biLSTM-CRF ranked by accuracy. The CNN-biLSTM-CRF makes the most sensible predictions with respect to the chronological order between the 3.3. RESULTS phases; it more specifically avoids inferring incorrect phases in short isolated bursts as the biLSTM sometimes does.

In order to confirm the quality of the material the student model learns from, we ran our metrics on the annotations from G i,j , which mix ground truth annotations and teacher-generated annotations. Results are shown in Table 3.4.

As expected, teachers trained on more manually annotated videos produce better annotations. The presence of more manually annotated videos in the G i,j sets also contributes to greater overall label quality, e.g. 83.5 % F1 score for G 20,j on average. Per-phase results indicate stronger performance on phases P2 (90.3% precision, 91.6 % recall for 20 manually annotated videos) and P4 (87.4% precision, 92.5 % recall), which are usually the most prevalent. Despite uneven results across phases, G i,j sets obtained from 3 or more manually annotated videos appear to be overall serviceable for training a student model. RECOGNITION

Student performance

To appreciate the benefits of using our synthetic labels, we compare in the first two groups of rows of Table 3.5 the CNN-LSTM only trained with few manually annotated videos against the CNN-LSTM trained with these same videos and annotations plus the videos annotated by the teacher. Results for a single ground truth-annotated video, as one can expect from the results of the corresponding teacher models, are quite poor. Even though the G 1,j sets contain 80 times as many videos as the E 1,j used for the teachers, the quality of the annotations, as shown in Table 3.4, is extremely low. CNN-LSTM models trained on those all exhibit sub-50% performance on every global metric, despite showing some improvement compared to the CNN-LSTM trained on E 1,j . Decent results are observed starting from 3 videos, with a 2.9 to 8.8 point increase in accuracy when adding synthetic annotations, and similar increase in F1 score.

With 80 ground truth-annotated videos, accuracy and F1 reach 86.3% and 78.2% respectively (Table 3.5). Therefore, the use of synthetic annotations roughly cuts down the performance gap between using 20 and 80 ground truth-annotated videos by half.

Self-learning of the teacher model

Teacher self-learning

By using the G i,j sets to train a new CNN-biLSTM-CRF model, the offline performance increases even further (Table 3.5, last 2 groups of rows) -except for the 1-video case, where performance actually degrades. Results with 20 ground truth-annotated videos are particularly notable, as they match those obtained with 80 ground truth-annotated videos from the CNN-LSTM model (86.3% accuracy, 78.2% F1).

Conclusion

The work presented in this section shows the superior performance of the new CNN-biLSTM-CRF teacher architecture compared to the previous CNN-LSTM used for surgical phase recognition. Although this model is restricted to offline inference, we also propose a teacher/student strategy that leverages the new model for real-time prediction, by exploiting it as a source of synthetic annotations for a CNN-LSTM student model. Experimental results, obtained using manual annotations for 25% or less of all available training data, show serious potential for scaling surgical phase recognition to a large number of videos while alleviating the burden of collecting manual annotations. The performance deficit between scenarios with 25% and 100% ground truth annotation availability is halved for a CNN-LSTM online prediction model when adding synthetic labels from the teacher. When swapping the student for a CNN-biLSTM-CRF offline prediction model, the gap is fully closed.

Many other types of surgical procedures than cholecystectomy for which large amounts of annotated data are not yet available, such as gastric bypass might be able to benefit from this method as well. RECOGNITION 73.8 ± 5 76.9 ± 1.9 81.7 ± 0.5 F1 18.2 ± 10.9 55.7 ± 9.7 66.8 ± 2.7 69.9 ± This chapter lays down theoretical foundations for video retrieval with hashing, which is at the core of the following chapters. After formalizing the problem of retrieval and search with the concept of nearest neighbors, our objective is to find a representation for videos that fit this concept: first, with combinations of deep neural networks that extract and aggregate information over the various time scales involved in video data; then, by compressing this information to an extreme degree via hashing to fit real-time requirements.

Nearest Neighbor Search

Definition

The problem of retrieving relevant entries from a database is a problem of abstract semantics (in our case, visual similarity with respect to surgical workflow). Nearest neighbors search attempts to solve it by turning it into a geometry problem; more specifically, a distance optimization problem. We assume we have at our disposal a set of data entries represented by data points E = x 1 , ... x N in a metric space Ω with a distance function D. The goal is to find a function φ verifying, for any query point u ∈ Ω, φ :

   Ω → E u → argmin x∈E D(u, x) (4.1)
φ retrieves the closest data point, with the underlying assumption that similar entries semantically are close geometrically. Geometrically speaking, if Ω = R d and D is the Euclidean distance, then φ partitions Ω into N convex polyhedrons (Y 1 , ... Y N ). The face separating two adjacent polyhedrons Y i , Y j belongs to the plane passing through 1 2 (x i + x j ) orthogonal to x j -x i . This set of polyhedrons, or cells, is known as the Voronoï tesselation (Figure 4.1) for E.

The Nearest Neighbor problem can be generalized as such: given the same query x, we look for Ψ verifying

Ψ : Ω → σ(E) u → π | π(x 0 ) ≤ π(x 1 ) ≤ ... ≤ π(x N ) (4.2)
where σ is the set of permutations over E. In other words, Ψ returns a ranking of E's items from closest to furthest to x. One can also only consider the top k items; formally:

ξ : Ω → E k u → (Ψ(u)(x 0 ), ... Ψ(u)(x k )) (4.3)
This is the k-NN search problem, which serves as the foundation for the k-NN classifier in machine learning; this method simply outputs the majority class among the top k closest retrieved entries.

Challenges & complexity

A straightforward approach for computing k nearest neighbors consists in computing the distance of every data point from the query before sorting. Known as linear search, With this complexity in mind, we can immediately point out two major challenges for retrieval in our case:

• Typical values for N , in our datasets, fall into the 10 3 ∼ 10 4 range -for instance FCVID contains 91000 videos. Real-life video databases, however, can exceed this quantity by several orders of magnitude. With approximately 700000 cholecystectomies and 200000 bariatric surgeries per year in the United States alone, a database obtained by recording all procedures over a 10-year period would likely fall into the 10 6 ∼ 10 7 range. For public video platforms such as Youtube, with 500 hours of content uploaded every minute [Woj20], upwards of 10 9 would be a safe estimate.

• The working assumption for nearest neighbor search is that similar entries semantically are close geometrically. Finding an appropriate space for data points, with reasonably low d, where the distance function D presents this property is a difficult task in the case of videos. The original dimension of video data in pixel space, assuming 224 • 224 resolution, 25 fps -our preprocessing for the FCVID dataset-and 134s duration, almost reaches 1.7 • 10 8

We can therefore conclude that the larger the database, the stronger the incentive to find low-dimensional, semantically rich representations of the data considered.

Video representation learning with CNN-RNNs

General concepts

Learning rich and compact representations of its training data is the core task of a deep neural network (DNN). Assuming a single-class classification task with M classes and a perfect classifier f of the data:

f : Ω → [0, 1] M x → 1 i∈ 1,M (x ∈ c i ) (4.4)
We look for an approximation f in the form of a DNN that verifies, for some loss function L:

f = argmin g x∈Ω L(f (x), g(x))dx (4.5)
Generally speaking, f can be separated into a deep feature extractor fF and a linear classifier fL , such that f = fL • fF . While learning fL is trivial, the bulk of the difficulty (non-linearity of f , high input dimensionality) is carried by fF , which has to learn a semantically rich, compact representation of the input data for the classifier.

In the case of surgical videos this is a particularly challenging task, due to multiple levels of modeling (Figure 4.2) to account for. To our knowledge, no single model type is capable of adequately covering them all, which is why we resort to DNN combinations described below.

CNN

In its simplest form (ignoring maximum pooling layers or residual connections), a Convolutional Neural Network or CNN applies a succession of convolutional layers, followed by the final linear classifier: we have f (x) = fL • fC,J • fC,J-1 ... • fC,1 (x) where J is the number of layers and x is an H × W × C input image.

Each convolutional layer fC,j : R

H j × R W j × R D j → R H j+1 × R W j+1 × R D j+1
is a mapping between two stacks of 2D feature slices. Each slice in the output is layer 2 layer 5 layer 1 obtained by passing the input slices through linear 2D filters then summing before applying a bias: fC,j (x) , ,r = ReLu(

D j r =1
x , ,r K , ,r + β , ,r ) (

with K ∈ R R H ×R R W ×R D j+1 the convolutional kernel, β the bias and the convolution operation (adequate padding of the input is implied). This use of convolutions ensures the representations learnt in the CNN preserve the spatial structure found in the input: each feature vector in the output fC,j (x) p,q, is a function of a 2D patch from the input around the same location, the size of the patch being the size of K's receptive field R R H × R R W . Additionally, features learnt by convolutional layers have appealing visual properties: invariance to small translations is built-in, while other forms of invariance can be enforced using data augmentation [START_REF] Baird | Document image defect models and their uses[END_REF].

The nature of the learnt representations gradually evolves as they move up the CNN's layers, from low-level local properties related to color and texture and edges, to the high-level semantic properties useful for classification according to Zeiler et al. [START_REF] Zeiler | Visualizing and understanding convolutional networks[END_REF]. A example of visualization of those features is given in Figure 4.3

3D CNN

The principles for learning visual representations from images with CNNs can be extended to short video clips as well. 3D CNN architectures, introduced in [TBF + 15], rely on stacked convolutional layers as well: fC,j (x) , , ,r = ReLu(

D j r =1
x , , ,r K , , ,r + β , , ,r ) (4.7)

The added dimension is of course time. The 2D convolution operator is therefore replaced with the 3D convolution . K, as a set of spatio-temporal filters, can capture temporal variations between frames such as object motion. In practice however, the number of timesteps is subject to memory limitations, since all frames in the video clip are simultaneously processed. Typical inputs [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] contain up to 64 frames sampled at 25 fps, making up barely over 2 seconds of footage.

Transfer learning

Parameter counts for CNNs typically fall into the 10 7 range [START_REF] He | Deep residual learning for image recognition[END_REF], often making them difficult to train from scratch (i.e. starting from randomly initialized weights) to perform a task T 1 for which low amounts of annotated data are available. Transfer learning attempts to circumvent this issue by repurposing a model already trained on a different task T 2 . Taking for example a CNN f2 trained on T 2 , in the general case the decomposition f2 = fL,2 • fF,2 applies, with fL,2 as the linear classifier and fF,2 as the feature extractor or backbone. The linear classifier fL,2 is mostly task-specific; however one can take advantage of the representation learnt by the linear classifier fF,2 in order to obtain a well-initialized model for T 1 , by only grafting a head h to it as shown in Figure 4.4:

f1 = h • fF,2 (4.8)
Training the entirety of this model on T 1 is a lightweight process, since fF,2 's weights are already considered close to optimal. Generally performed with low learning rate values for a relatively small number of epochs, this is commonly referred to as finetuning. If the dataset involved in T 1 is particularly small, the common practice is to freeze fF,2 in part or in its entirety, in order to prevent overfitting.

The key assumption in this approach is that T 2 is visually generic, so that features learnt by fF,2 generalize well to other tasks. In large-scale image or video benchmarks it is generally assumed to be the case; therefore in our work, we used a Resnet-50 CNN [START_REF] He | Deep residual learning for image recognition[END_REF] pretrained on the ImageNet [DDS + 09] dataset, as well as an I3D backbone pretrained on Kinetics [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] in later chapters.

An important observation is that the head h is not necessarily another linear classifier, as evidenced by the next section.

Cell RNN

RNN

In our approaches to video processing, CNN backbones handle the scale of frames or short clips; when moving to larger time scales, we add Recurrent Neural Network models, which we explain here. Considering a 2-to-2 vector function:

f : (I, H) → (O, H) (a, b) → (f 1 (a, b), f 2 (a, b)) (4.9)
and an initial state h 0 , the Recurrent Neural Network (Figure 4.5) corresponding to f is defined as:

F : I * → O * (x 0 , ... x T ) → (y 0 , ... y T ) (4.10)
with, for any t ∈ 0, T :

(y t , h t+1 ) = f (x t , h t ) (4.11)
This recurrent equation updates the internal temporal representation or state h t to h t+1 , from one timestep to the next. The length of the sequence T is arbitrary; therefore inputs of any length in time can be processed. Since h t depends on all previous inputs x 0 ... x t , the state functions as the RNN's memory or internal summary of past events; this is a temporal representation learnt by the RNN.

f 's parameters -noted W -are learnt via backpropagation through time. We consider an error E(y t ) to minimize, computed from f's last output. ∂E ∂W depends on ∂ht ∂W , which itself depends on recurrent gradients ∂h j+1 ∂h j for j ∈ 0, T -1 ; each of these terms can be computed using the next one via the chain rule, which facilitates training.

Similar to stacked layers in CNNs or multilayer perceptrons, multiple recurrent neural networks F 1 ... F L can form a single stacked RNN F with function composition (Figure 4.6), as F = F L • F L-1 ... • F 1 . This means, for a given timestep, the external output from a layer is forwarded to the external input of the next one. According to Graves et al. [START_REF] Graves | Speech recognition with deep recurrent neural networks[END_REF] this provides "depth in space" for the RNN's RETRIEVAL learnt representations, in addition to "depth in time", which is naturally obtained by forwarding the state.

Another classic enhancement comes in the form of the bidirectional RNN (Figure 4.6). Two RNNs F , F process the input sequence in opposite orders; at any given timestep j, their outputs y ,j and y ,j are concatenated together into a single output y j , which is a function of both states h ,j and h ,j , accounting for past and future events respectively. The entire temporal context is therefore available throughout the sequence -the downside, as previously stated in Chapter 3, is the inability to use this model in real time.

LSTM

A commonly used model for f is the LSTM (Figure 4.7) [START_REF] Hochreiter | Long short-term memory[END_REF], defined by the following set of equations:

                         f t = σ(W x,f • x t + W h,f • h t + b f ) i t = σ(W x,i • x t + W h,i • h t + b i ) g t = tanh(W x,g • x t + W h,g • h t + b g ) o t = σ(W x,o • x t + W h,o • h t + b o ) c t+1 = c t * f t + i t * g t h t+1 = o t * tanh(c t+1 ) y t = h t+1 "
•" is the dot product, while " * " is the element-wise multiplication. The internal state is composed of two vectors (c t , h t ), named respectively cell state and hidden state; the hidden state is also used as the output y t . Optionally, the state h t can be treated with Ioffe et al's batch normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] in order to improve the model's convergence and generalizability. While most common in CNNs, its use has previously been seen in LSTM models as well [CBL + 17, ZWHC16].

The total number of parameters is:

N prm = 4 • dim(x) • dim(h) + 4 • dim(h) 2 + 4 • dim(h) (4.12)
while the number of floating-point operations for one iteration is: While, to our knowledge, no formal constraints exist for dimensions dim(x) and dim(h), values for those overwhelmingly tend to fall into the 10 1 ∼ 10 3 order of magnitude. Direct usage on video frames (10 5 ∼ 10 6 ) is generally ruled out.

N op = 4 • dim(x) • dim(h) + 4 • dim(h) 2 + 17 • dim(h) (
It has been shown [START_REF] Hochreiter | Long short-term memory[END_REF] that, during the training process, the LSTM learns to write into the state the information needed for predictions at much later timesteps; hence "long term". According to Tallec et al. [START_REF] Tallec | Can recurrent neural networks warp time?[END_REF], the gate values f t and i t act as "time contraction or time dilation coefficients", rendering the LSTM's learnt representations "quasi-invariant" to time warping.

Seq2Seq architectures

A sequence-to-sequence mapping is a function f : A * → B * , with A and B vector spaces of finite dimension and A * , B * the corresponding spaces of sequences. The key consideration here is that the input and output sequence lengths are arbitrary; approximating f therefore requires a high degree of flexibility in the model's architecture.

Some of that flexibility can be provided by a Recurrent Neural Network, which, on its own, naturally maps a sequence to another sequence. However in this approach outputs and inputs are matched timestep for timestep, which constrains input and output sequence lengths to be identical. Limited input visibility is also an issue: for machine translation tasks, the information required by the target language in the middle of a sentence found at a further location in the source language sentence.

Sequence-to-sequence learning [START_REF] Sutskever | Sequence to sequence learning with neural networks[END_REF] or Seq2seq refers to a family of models designed to solve those issues (Figure 4.8). They consist in a pair of RNNs, one encoder and one decoder: the encoder reads the input sequence from beginning to end. The final state h T is then forwarded to the decoder, which sets it as its own initial state. From there, the decoder generates the target sequence, without any external inputs -for example the original Seq2seq publication connects the external input of the previous timestep to the output of the previous one.

Here h T acts as a representational bottleneck. All the information required by the decoder to generate the target sequence needs to be written into h T by the encoder, regardless of input or output sequence length.

Combined with a pretrained CNN used as a feature extractor, this results in a model capable of generating compact video representations, accounting for all temporal scales involved in surgical videos.

Hashing

The video representation obtained with ordinary CNN-RNNs is the RNN's memory, i.e. a floating-point vector of a few hundred coordinates in general. Hashing enables compressing this representation to an extreme degree, resulting in binary arrays that are convenient for indexing.

Hash functions: definitions, basic properties

The term "hashing" refers to a family of methods employed for computing a fixed-size value called a hash from a given data input, which the hash will then identify -similar to a signature or a fingerprint. Formally speaking, a hash function is a mapping with n being the hash length. From this point onwards we will consider Σ = {-1, 1} i.e. binary hashes, or bitcodes. For example:

h : E * → Σ n
h : 0, 1 * → 0, 1 (4.15) : (b 1 ... bT ) → b 1 ⊗ b 2 ... ⊗ b T (4.16)
⊗ denotes the logical XOR operator.h is a basic single-bit hash function. We can already point out h(1, 0, 1) = h(1, 1, 0); in general, any hash function is redundant. As a mapping from a set to a smaller one it indeed falls under the pigeonhole principle. Redundencies, i.e. pairs (a, b) such that a = b, h(a) = h(b) are called collisions. Under uniformity assumptions, the probability of finding at least one collision in a set of k random data inputs is given by

P C = 1 - k-1 j=1 2 n -j 2 j (4.17) = 1 - 2 n ! 2 kn (2 n -k)! (4.18)
Stirling's factorial approximation gives an asymptotic equivalent for P C :

P C = 1 -e -k 2 2 n+1 (4.19)
Notably, when k > 2 n+1 ln(2) ∼ 1.18 • 2 n/2 , then the collision probability exceeds 1 2 ; this is commonly known as the Birthday Paradox. This is an important principle in hashing: although many distinct bitcodes (2 n ) are available, collisions are more likely than one might first expect. For instance 32-bit hashes offer 4 • 10 9 possible values, but collisions are more likely to occur than not in a set of only 80000 32-bit hashes (Figure 4.9). Along with computation speed, collision behavior is one of the main factors determining the choice of h. This heavily depends on h's purpose: for encryption, accidental collisions should be avoided at all costs, which is why the chosen hash RETRIEVAL functions for this use case exhibit extremely high sensitivity to input perturbations. This property is known the Avalanche Effect; formally, the Strict Avalanche Criterion dictates that one flipped bit in the input causes every bit in the output to flip with a 50% probability for each one, independently. An example of a situation where this property is useful is file verification upon transfer -this is routinely performed using a hash function called md5sum. Instead of examining a file f for errors bit by bit, the file's receiver computes h(f ) and compares it against the original signature h(f original ). While a collision between a corrupted file and the original is possible (f = f original , h(f ) = h(f original )), it is so exceedingly improbable for reasonably large n that the received file is considered clean if the hashes match.

Retrieving data with hashing

The term hashing covers several families of tasks, with vastly different methods and applications. Retrieval with hashing is most commonly understood in the context of hash tables, which we will explain here in order to clear potential confusions with similarity-preserving hashing. Hash tables are data structures storing values to be retrieved with a corresponding key. Unlike ordinary arrays, which are indexed by integer indices, the data type for the key is arbitrary. Well-known implementations of this data structure include C++'s std::unordered map or Python's dict.

During storage, a hash function hashes the key -the resulting code is the address in an array where the corresponding value is stored. Retrieving can then be done using the same key, which, evaluated by the hash function, immediately gives the exact location to retrieve from in the array. This makes retrieval O(1). This is much faster than retrieving from an ordinary array with n (key, value) pairs, which takes at best O(ln(n)) comparisons if sorted by keys, O(n) otherwise.

Once again collisions are to be avoided; if two keys share the same hash, the value to retrieve is ambiguous. In those cases an ad hoc collision resolution routine is performed; querying with unseen keys is also forbidden.

In content-based data retrieval, the requirement for hash functions is radically different (Figure 4.10). Similarity preservation is crucial here; data entries that are very distinct from one another should produce many conflicting bits. Conversely, data entries with a high degree of similarity should produce similar bitcodes or even collide, a property considered unacceptable in cryptographic hashing or exact retrieval. This is formalized by the locality-sensitive property [START_REF] Andoni | Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[END_REF], as stated in [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF]:

d(a, b) ≤ r 1 ⇒ P (h(a) = h(b)) ≥ p 1 (4.20) d(a, b) > r 2 ⇒ P (h(a) = h(b)) ≤ p 2 (4.21)
The choice of distance d in input space is of course crucial and to be discussed later on. In bitcode space we use the hamming distance, defined as

d(a, b) = n j=0 1(a j = b j ) (4.22)
This is simply the number of conflicting bits between the two codes. Assuming h exhibits decent locality-sensitive properties, one can use it to perform Approximate Nearest Neighbors Search [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF], as a substitute for the costly exact nearest neighbors previously mentioned. While exact retrieval is O(1) (no comparisons), approximate nearest neighbors retrieval requires O(n) distance computations just like the exact version. However depending on the implementation the corresponding computation can be extremely quick; using true bits, a single bitwise XOR operation leads to the result, instead of 1 floating-point operation for every vector component. This solution is much more storage-efficient as well.

Challenges of learning hash functions

Finding a good candidate for h is a difficult task. Assuming a set of data points to hash x 1 ... x N Finding h with the best similarity-preserving properties can be formulated as the following discrete optimization problem:

argmin b 1 ... b N i,j∈ 1,N d(x i , x j )|b i -b j | 2 (4.23) under: b i ∈ {-1, 1} n (binary constraint) (4.24) n i=1 b i = (0, ... 0) (even bit distribution) (4.25) 1 n n i=0 b i b T i = 0 (decorrelated bits) (4.26)
This is known to be NP-hard [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF]; with a large database of inputs, solving it quickly becomes impractical.

As mentioned earlier, h(x) should, for any x, contain rich discriminative information extracted from x. It is therefore natural to turn to learning-based approaches, considering their success extracting information from complex and high-dimensional input data. We now assume h is a function with parameters W -noted h W from now on.

The immediate issue we encounter is that, strictly speaking, h W is not differentiable. Indeed, it is not even continuous.

While h can be differentiated outside of its discontinuity points, it is locally constant there, and the result will therefore always be a zero derivative. When backpropagating to the parameters W this is an issue; as an effect of the chain rule, ∇ W L(h W (x)) = 0. Workarounds, however, do exist. First, we can look for a relaxation in the form of

h W (x) = sgn(A • g V (x)) (4.27)
with sgn mapping < 0 inputs to -1, and the rest to +1. g V is a differentiable function with learnable parameters V , A is a projection matrix. We will refer to the argument of sgn as the prebitcode b.

It is now clear how learning hash functions can be posed as a representation learning problem, i.e. mapping the data to a feature vector space that can be linearly partitioned by N affine hyperplanes P i . Each column A i of A is a normal vector of one of the P i hyperplanes, and the position of the input in feature space relative to the hyperplane determines the corresponding bit value.

Training g is a real-valued optimization problem instead of a discrete one, and can be solved using gradient descent. Using conventional approaches for training deep neural networks, we can learn a function that will incorporate rich, discriminative information into b. This does, however, result in a certain amount of quantization error which can be measured by [START_REF] Gong | Iterative quantization: A procrustean approach to learning binary codes BIBLIOGRAPHY for large-scale image retrieval[END_REF]:

Q(h, x 1 ... x N ) = N i=1 ||b i -A • g(x i )|| 2 (4.28)
Prebitcode positioning with respect to the zero line in each component is crucial in managing this error. Methods such as ITQ [START_REF] Gong | Iterative quantization: A procrustean approach to learning binary codes BIBLIOGRAPHY for large-scale image retrieval[END_REF] or UDVH [WLG + 17, WHG + 19] try to enforce this with geometric transformations. However this can be handled by the training process itself in an elegant and end-to-end manner. First, batch normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF], by centering activations around zero, achieves this effect. Second, although sgn is not differentiable, a workaround is given in [HCS + 16].

We can introduce:

f :      x ∈] -1, -∞] → -1 x ∈ [-1, 1] → x x ∈ [1, +∞[ → 1 (4.29)
This is sometimes referred to as hardtanh, due to similar behavior near -∞, 0 and ∞. Then: Forward pass is done with a true sgn, while backpropagation replaces the gradient with ∇ * W (h(x)) (Figure 4.11).Experimentally, Zhang et al. [START_REF] Zhang | Play and rewind: Optimizing binary representations of videos by selfsupervised temporal hashing[END_REF] observed that this training method, along with batch normalization, improved prebitcode spread around zero in their modified LSTM.

∇ * W (h(x)) = 1 [-1,1] (A • g v (x)) • A • ∇ V (g V (x)) (4.30) 4.3. HASHING -1 1 0 -1 1 -1 1 ...

Objectives

As established in the previous chapter, learning video representations for large-scale retrieval is a challenging problem: information from a wide range of temporal scales needs to be accounted for, and undergo extreme levels of compression. Here we introduce an additional technical difficulty, by examining the case of live video sources. Obvious examples include TV event broadcasts, livestreams from platforms such as Youtube Live or Twitch. However, those also encapsulate a wide variety of settings and devices: from surveillance cameras and dashcams to personal smartphones, and medical video capture devices such as endoscopes.

The difficulty of this task comes from two major challenges:

1. Search needs to be fast enough for real-time use. If too slow to compute, search results risk becoming irrelevant to the content currently displayed. This constraint is extremely harsh: large-scale video databases can consist of tens of thousands if not millions of items, each one the size of many static images.

2. When streaming in real time, the video content is de facto incomplete. At the beginning of a video especially, only a fraction of the total information is available.

As stated in Chapter 2 the previous literature on video retrieval does not fit the requirements of real-time usage. The few recent works involving deep computer vision models [ZWHC16, SZL + 18, WLG + 17, WHG + 19, LCL + 19] only retain a fixed, very small (N f rames = 20or25) number of evenly spaced frames out of the entire video. In addition to destroying most of the visual content, this process is also impossible to exactly replicate live, since the sampling rate of Total duration N f rames would be unknown.

Methods

Setup and data preparation

Overview

The problem can be formally stated as follows: given a level of observation α ∈ (0, 1], a video Q with duration T (Q), a query Q α consisting of Q truncated mid-stream at time αT (Q), and a database of videos B = {V 0 ...V N }, use only Q α to find the K videos from B most similar to Q.

Since hashing is the method employed here, B and Q are represented by binary codes during search operations. The overall protocol is therefore composed of the following steps:

• video-level feature extraction • self-supervised hash function training • codebook, query encoding • search operations

Datasets

Experiments shown in this chapter involve two very large scale, public datasets of generic human activities. The first is FCVID [JWW + 18], a public video dataset used for research on video retrieval [ZWHC16, SZL + 18, WLG + 17, WHG + 19, LCL + 19] and activity understanding depicting various activities, objects, sports and events. 234 video classes are present. The average video duration is 134 ± 92 seconds. Data was split as follows: 45K for training, 45K for testing. Within the test videos, 42.5K constitute the database while the remaining 2.5k (about 10 videos per class on average) are used for querying. The second dataset we employed is ActivityNet [START_REF] Caba Heilbron | Activitynet: A large-scale video benchmark for human activity understanding[END_REF]. We used the 18K videos available for download. 200 activity classes are featured. A number of videos had their labels concealed by the organizers of the ActivityNet challenge; those videos were put in the training set. The average duration is 117 ± 67 seconds. Data was split as follows: 9K for training, 9K for testing, and within the testing videos 8K for the codebook, 1K (about 5 per class on average) for the query. In both datasets, the videos are untrimmed, which implies that the content reflecting a given video's class may not be shown for its entire duration. All videos have been resampled at 30 fps and a few excessively long videos have been cropped to 4 min 30s; we then sort them into 12 duration buckets of 22s in diameter each.

Sampling & feature extraction

As mentioned in the related work section, previous approaches have chosen sparse, fixed-length video-level representations which can result in the loss of large amounts of visual information in long videos. More importantly, such sampling and feature extraction schemes are inadequate for real-time usage: the sampling rate in that case is dependent on the length of the full video, which would be unknown mid-stream. An early retrieval algorithm should be capable of delivering search results at a fast and steady pace.

To solve this issue, we have chosen a dense, fixed-rate sampling and feature extraction scheme that leverages a 3D CNN to aggregate visual information over short time windows. The chosen architecture is I3D [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF], pretrained on the Kinetics dataset for action recognition. Input frames from the videos are center-cropped to 224 × 224. Clip input length is 64 frames (roughly 2 seconds at 30 fps). This yields a feature tensor with dimensions 8 × 7 × 7 × 1024, which we average pool into a feature vector of size N f = 1 × 2 × 2 × 1024 = 4096. The entire video is processed in consecutive clips, resulting in a 30 / 64 = 0.47 Hz constant feature output rate.

Binary RNN encoder

An RNN (Figure 5.3) takes the feature vectors f 0 , f 1 , ..., f t , ..., f T (V ) from I3D in chronological order and maps each one to a bitcode of size N bits . This RNN is built on two stacked LSTMs, with a binary LSTM as introduced in [START_REF] Zhang | Play and rewind: Optimizing binary representations of videos by selfsupervised temporal hashing[END_REF]. The hidden state circulating from one RNN timestep t to the next is the above mentioned bitcode noted b(V, t) for a video V . Batch normalization is applied to the cell state as done in [START_REF] Zhang | Play and rewind: Optimizing binary representations of videos by selfsupervised temporal hashing[END_REF]. This RNN is trained as the encoder part of an autoencoder model. The final hidden state of the decoder -the video's bitcode -is passed to two decoder RNNs tasked with reconstructing the sequence of input feature vectors in opposite orders. This training process encourages the encoder to incorporate rich, discriminative information into the bitcodes.

Formally, the autoencoder is trained to minimize the following unsupervised loss function:

L decoder (V ) = T (V ) j=0 f j - ← - f j 2 + f j - - → f j 2 . (5.1) ← - f , - →
f are the reverse and forward reconstructed sequences, respectively. Backpropagation relies on the gradient substitution method shown in [START_REF] Zhang | Play and rewind: Optimizing binary representations of videos by selfsupervised temporal hashing[END_REF]. Trained as such with full videos, we call this configuration SSTH-RT (Figure 5.4, top left) for real-time, as each new increment of the video playing in real-time is incorporated into the bitcode. This is, in the form presented here, our first baseline approach.

Data-augmentated encoder via truncated training duplicates

Since the training process for the baseline setting always involves complete videos, a straightforward data augmentation method for training the autoencoder is to simply give the autoencoder videos truncated at various levels of observation to reconstruct (Figure 5.4, left). This approach provides some training exposure to videos that are incomplete. This is referred to as SSTH-RT + in the later sections.

Augmented codebook with truncated database duplicates

Another idea to improve early retrieval results is to incorporate trimmed videos, both during training -as in SSTH-RT + -and codebook construction (Figure 5.4, center). We refer to this later on as SSTH-RT ++ . While this idea might seem appealing at a first glance, it causes the search protocol to slow down due to the insertion of bitcodes from trimmed duplicates. This requires inserting as many duplicates per video as levels of observation employed -in our case: 10 from 0.1 to 1.0 -which is also a source of scalability issues. Assuming N α levels of observation are employed, search time and storage space requirements both get multiplied by N α . Duplicates in the search results, namely, videos truncated at different levels of observations from the same original video, would also need to be purged, the cost of which has N cb × N α complexity, N cb being the size of the codebook without duplicates. Correctly retrieved results that are duplicates may improve retrieval metrics, but do not suit general application cases: a search operation returning truncated versions of the same video would be unhelpful to the user. The approaches proposed in the next section are faster as they employ codebooks with the exact same population size as the original video database.

Look-ahead distillation for encoders

We propose two forms of distillation in order to train predictive encoders that can anticipate the future content when presented with incomplete videos, and therefore generate richer, more discriminative bitcodes that are more likely to yield better search results.

Indirect distillation: look-ahead reconstruction (LA-RECO) loss

An encoder, which will from now on be referred to as the primary encoder (P in Figure 5.4), is trained following the same process as SSTH-RT + jointly with a decoder. Once this training is done, the main encoder is set aside and a secondary encoder (S in Figure 5.4, top right) is introduced. Only incomplete videos are fed into iti.e. videos truncated to αT (V ) with randomized alpha for each training step. The resulting bitcode is passed to the trained decoder with frozen parameters. The output of the decoder is compared to the full sequence in the loss, not just the truncated part fed to the secondary. This forces the secondary encoder to guess a representation accounting for future video frames.

L decoder (V ) = T (V ) j=0 f j - ← - f j 2 + f j - - → f j 2 (5.2)

Direct distillation: look-ahead bitcode (LA-CODE) loss

A secondary encoder is introduced as in the previous section, however this time the primary is put to use and the decoder is set aside (Figure 5.4, bottom right). During training, the primary encoder receives the entire video while the secondary encoder is only fed the αT first frames, again with randomized alpha. From the secondary, we extract the real-valued input β to the sgn function that leads to the last bitcode -we refer to this as the prebitcode -and compare that to the bitcode b given by the primary using an L 2 loss function:

5.2. METHODS L LA-CODE = β(V, αT ) -b(V ) 2 . (5.3)
This conditions two behaviors:

• the secondary, despite being only fed part of a video, mimics the full video's bitcode

• the primary adapts the bitcode of the full video, making it more robust to temporal crops

Training

Video-level features are extracted separately by I3D and loaded from binary files.

Training is done in batches, which involves certain technical difficulties linked to sequence duration. Unlike in other video hashing approaches presented earlier, for which videos were downsampled to a fixed sequence length and evenly-sized batches could always be built, in our case the feature sequence length varies from one video to another due to the fixed sampling rate. Batching would require either zero padding, which is not an option here due to the use of batch normalization, or cropping to the shortest sequence; which, if performed carelessly, might discard significant portions of training videos due to length discrepancies within a batch. As a countermeasure, batching is based on the buckets defined in 5.2.2.1. We dynamically pick randomized batches from a single bucket at a time, guaranteeing a maximum length difference of about 22s inside a batch. Those batches are then trimmed to the shortest duration present in each of them; at most 22s of video are lost through this process.

Gradient descent is performed using the RMSProp algorithm. We introduce a new method named recurrent gradient clipping, as detailed in Appendix B; applied to hidden states and cell states, this entirely prevents gradient explosion, a long-standing issue of RNNs [START_REF] Pascanu | On the difficulty of training recurrent neural networks[END_REF]. Encoder/decoder pairs are trained for 60 epochs with a learning rate of 5.10 -3 and a batch size of 40. The encoder is a 2-layer RNN with 2 • N bits in the first layer and N bits units in the second. The decoder also has two layers, with N bits in the first layer and 2 • N bits units in the second. Secondary encoders in LA-RECO or LA-CODE are trained for 15 epochs with a learning rate of 5.10 -4 . Their weights are initialized from the values of the trained primary encoder's weights.

Evaluation

Once the primary and secondary encoders are trained, we use the primary to generate the codebook from the 9.7K videos picked from the test set. The remaining 1K form the query set. Evaluation is based on the video classes: for a given query video, a retrieved video is considered correct if its class matches the query's. The query encoder (i.e. the secondary encoder in LA-RECO or LA-CODE) generates a bitcode for each query video, truncated at αT frames. The code is compared to codebook entries, which are then ranked by Hamming distance to the query bitcode starting from the closest. Query videos are truncated using 10 different values for α ranging from 0.1 to 1.0.

As in [START_REF] Zhang | Play and rewind: Optimizing binary representations of videos by selfsupervised temporal hashing[END_REF] we use the following definition for average precision at K -or AP@K -for a single video:

AP @K = 1 K K j=0 N correct (j) j (5.4)
where N correct (j) is the number of matching results among the top j.

The mean over all query videos is the Mean Average Precision at K -or mAP@K. We report this metric by level of observation for all methods and all bitcode sizes for K = 20. Lower values of K are more relevant in a real-time use case, where one can only handle a small number of search results; nonetheless we provide mAP@K curves for K up to 100 for our best model. We also provide qualitative retrieval results in two cases.

All experiments are repeated for four different bitcode sizes: 64, 96, 128, 192 bits. The compared approaches are: SSTH-RT (binary autoencoder trained to reconstruct full sequences from full sequences) SSTH-RT + (binary autoencoder trained to reconstruct full sequences from full sequences, as well as partial sequences from partial sequences) SSTH-RT ++ (SSTH-RT + with truncated duplicates hashed into the codebook) LA-RECO (SSTH-RT + as primary encoder, secondary trained to reconstruct full sequences from partial sequences) LA-CODE (SSTH-RT + as primary encoder, secondary trained to predict the primary's full-sequence-bitcodes from partial sequences)

Implementation & optimization details

Deep models are implemented in Tensorflow 1.13, and training is performed on servers fitted with either NVIDIA Tesla P100, K40m, K40c, K80 or GTX1080Ti GPUs. On a Tesla P100, training is done in under two hours for an encoder-decoder pair, and under 30 minutes for a secondary encoder. As stated in Chapter 4, distance computation consumes O(N bits •N cb ) operations; ranking costs O(N cb •log(N cb )) using Python's builtin sort function. It is worth noting that for convenience reasons the search protocol is implemented in Numpy, with bitcodes represented as 8-bit Numpy booleans. An implementation with actual bits via a dedicated bit manipulation library would likely yield higher speeds than what we were able to achieve.

Results

Method comparison

mAP@20 is compared by level of observation for each method in Figures 5.6 5.7 with separate graphs for each size of bitcode. SSTH-RT serves as reference baseline. SSTH-RT + is a much more competitive model to compare to, SSTH-RT ++ even more so but at the cost of 10 times the space requirements and search time.

Both LA-RECO and LA-CODE outperform the SSTH-RT baseline by a substantial margin: 4 to 8%. LA-RECO outperforms SSTH-RT + by a small amount for 128 bits (less than 1%), but usually reaches similar or slightly worse mAP at other bitcode sizes. LA-CODE on the other hand outperforms both SSTH-RT + and SSTH-RT ++ significantly at most observation levels. For 128 bits, LA-CODE is superior to SSTH-RT + by 4 to 5% on Compared to LA-CODE, LA-RECO enforces a softer constraint: the bitcode-to-sequence mapping performed by the decoder may not be one-to-one. A learnt representation may therefore reconstruct well without approaching the bitcodes of relevant complete videos.

In terms of bitcode size, the general tendency observed in Figure 5.6 5.7 is that performance increases with size, as more bits provide more capacity for encoding information from the video. Looking at one method, peak mAP@20 for LA-CODE starts at 48% for 64 bits, then moves up to 51% for 96, 54% for 128, 55% for 192.

To highlight the compared methods' behavior in very early and early parts in a video, we consider the average of mAP@20 over three ranges of observation levels in Table 5.1.

Even though the focus of this work is early retrieval (50% of the video or less), in real-time the current level of observation would be unknown. Sustaining acceptable performance at higher levels of observation would therefore still be valuable.

The performance increase in the very low α range is generally accentuated compared to the whole range of α. This makes sense since the losses employed emphasize anticipation. For 128 bits, LA-RECO surpasses SSTH-RT + by 1% on average. However for α specifically in [0.1, 0.2] the performance increase is 1.9%. This also holds true for LA-CODE, which beats SSTH-RT + by 2.8% overall and 4% in the very early α range, and SSTH-RT++ as well by a 1.9% margin overall and 2.7% for very low α. We display mAP@K for LA-CODE for all bitcode sizes for increasing observation levels, compared with SSTH-RT ++ 's mAP@K on full queries (SSTH-RT ++ 1.0 ) in Figures 5.8, 5.9. With 20% of video observed at 128 bits, LA-RECO loses to SSTH-RT ++ 1.0 by 5%, which is expected due to the amount of missing information compared to the full video. However the gap is almost nullified with 40% of video observed. At 60% then 80% of video observed LA-RECO surpasses SSTH-RT ++ 1.0 by up to 1 then 2%. MAP@K plots for other bitcode sizes and methods are provided separately in Appendix C. We selected two queries from the query set on which LA-RECO returned successful results (all results correct in top 10) at the end of the video, and followed the evolution of the top 5 search results at different points in time. Both of them depict the action "decorating a christmas tree". Retrieval might be subpar early on in the video but the model should ideally adapt and return increasingly more relevant database entries as the video plays. Figure 5.11 is an example of a successful case. A mistake is made early on at 20%, but top 5 search results improve to a perfect 5/5 after 50% of the video is seen. On the other hand, in Figure 5.10 the model starts with 3/5 correct results, then drops to 1/5 in the middle. Retrieval eventually improves towards the end with 4/5 correct results at 81%. In-depth qualitative results are available in the video at https://www.youtube.com/watch?v=Eq-lIUipd4E.

RESULTS

Conclusion

In this chapter, we presented an unsupervised video hashing approach designed for retrieval from incomplete video queries. We proposed to optimize the bitcode rep-5.4. CONCLUSION resentation of incomplete queries by distilling knowledge from an encoder trained on complete videos into a secondary encoder used only for the queries. For this purpose, we introduced two losses that are used to train the secondary encoder to match the encoding performance of the first encoder while using only truncated data as input. The secondary encoder thereby learns to produce informative bitcodes that can anticipate the future video content. The approach yields a large performance improvement over the baseline. It also outperforms a naive approach that inflates the codebook by adding codes generated from truncated copies of the videos in the database, while being at the same time much faster and more scalable for live hashing and retrieval on video streams.

OBJECTIVES

In our binary representations of videos, every bit contributes equally when performing retrieval. Not all bits, however are equally reliable. When moving from generic human activity to endoscopic video data, we address this concern by proposing a new, lightweight method relying on compressed uncertain bit patterns corresponding to each database entry. As an extension of the previous work published in [START_REF] Yu | Encode the unseen: Predictive video hashing for scalable mid-stream retrieval[END_REF], the work presented here is the subject of a separate manuscript titled Real-time Laparoscopic Video Retrieval with Compressed Uncertainty, in preparation for Medical Image Analysis.

Objectives

The endoscopic video data in our dataset is vastly unused and unexplored, due to a lack of annotations for nearly 90 % of it. Available exploitation possibilities from the preexisting literature are scarce:

• Supervised learning using surgery type as the label [KYM + 20]. This is the lowest possible resolution for describing surgical activity.

• Self-supervised or semi-supervised learning, which for the most part [FJM + 18, YMMP18] uses the unannotated data without providing information about it. Even our previous method [START_REF] Yu | Learning from a tiny dataset of manual annotations: a teacher/student approach for surgical phase recognition[END_REF] has its limitations, since it is specific to the task of phase recognition in cholecystectomy.

An adequate content-based video retrieval method would be a considerable breakthrough for the exploitation of this dataset, essentially turning a passive video archive into a surgical video index that can be browsed visually, without requiring any tags. This opens up opportunities for various applications: post-operatively for indexing or reporting, or during surgical training as an educational tool. Intra-operative use would be valuable as well, but requires the ability to function in real time. Real-time retrieval, as shown in the previous chapter, brings its own set of challenges. With Endocorpus at our disposal, the first very-large-scale surgical video dataset, we study the problem of surgical video hashing in real time. What we verify here is retrieval's versatility, i.e. its ability to capture a wide variety of semantics in surgery. Therefore, the same model trained on one large collection of unlabelled videos is evaluated under three protocols: one based on cholecystectomy phases, one based on bypass phases, and one based on surgical critical events.

Methods

Data preparation

Out of the 1558 videos, we pick 81000 clips of 32s each for unsupervised training, and 16000 for validation. The training set incorporates all 12 available types of surgery, including the 6 not appearing in any of the test protocols.

Three types of labels are available for retrieval test:

• 7 cholecystectomy phase labels on • 11 gastric bypass phase labels on Bypass40 (Chapter 1, Section 1.3.3)

• 11 critical event labels on CEV64 1.3.4 (Chapter 1, Section 1.3.4)

Data splitting is done according to Table 6.1. Due to high imbalances in CEV64, both the query set and codebook set for this dataset were built by evenly collecting clips from the 11 event classes.

Uncertainty

When hashing live video sources dynamically using the approaches proposed in Chapter 5, the expected behavior is that the hash function updates the bit representation of the video content it has seen so far at regular time intervals (approximately 2 seconds in our case). Over the course of a given video, any given bit in the representation may flip several times. While this behavior is what makes our approach dynamic and fit for real-time use, excessive fluctuations for a particular bit make its value uncertain. So far, this uncertainty has been left unaccounted for in the codebook: the final bitcode, obtained after the primary encoder reads a video from the database from beginning to end, is taken at face value and stored as is, regardless of previous bit fluctuations.

In the case of LA-CODE, introduced in Chapter 5, another source of uncertainty is at play: the secondary encoder is trained to copy the primary encoder's representations of full videos, and is then used for querying. For a given clip, any bit where the primary and the secondary often enter in conflict should therefore be considered untrustworthy. From now on, we will refer to those as primary uncertainty and secondary uncertainty respectively.

Formally, let us consider a sequence of features representing a video clip V = V 1 , ...V T . We write the t-th subclip as U t = (V 1 , ...V t ). Assuming we use d bits, let π and σ be LA-CODE s primary and secondary encoders. Then throughout the course of the video V , π outputs the bitcode sequence:

π(U 1 ), π(U 2 ), ...π(U t ), ...π(U T ). (6.1)
π(U T ) in particular is the one stored in the codebook. For any timestep t, the i-th bit in the primary s bitcode is written as π i (U t ). σ for the secondary follows the same notation.

The primary uncertainty for video V at bit i is defined as follows:

p i (V ) = 1 N -1 N -1 t=1 π i (V T ) ⊗ π i (V t ). (6.2)
⊗ is the bitwise XOR operation. Concretely speaking, this is the fraction of the time the primary spends in disagreement with the bitcode stored in the codebook. The secondary uncertainty, on the other hand, is defined as:

s i (V ) = 1 T N t=1 π i (V T ) ⊗ σ i (V t ). (6.3)
Or, more simply, the fraction of the time the secondary spends disagreeing with the bitcode stored in the codebook. p and s can then be blended into a single uncertainty score, using a balance factor θ:

µ(V, θ) = θ • p(V ) + (1 -θ) • s(V ). (6.4)
Storing µ itself along with π(U T ), however, would be an extremely disproportionate way of communicating uncertainty (d floating-point values for d bits; with 32-bit floats that would be a factor 32). A much more space-efficient way to proceed is, for a given bit skepticism level K bs (i.e. presumed number of untrustworthy bits in a bitcode), to flag the position of the K bs most uncertain bits: CHAPTER 6. REAL-TIME SURGICAL VIDEO RETRIEVAL WITH UNCERTAINTY F(V, θ, K bs ) = Φ K bs (µ(V, θ)).

(6.5)

The i-th coordinate of Φ K bs (X) is 1 if X i is in X's top K bs values, 0 otherwise. This is simply a binary mask suppressing non-top K entries.

With this information at our disposal, the querying mechanism can be readjusted to account for uncertainty: consider a query video Q at time t, and a database entry R to compare it to. In LA-CODE, the hamming distance would be computed as the number of conflicting bits between the query and the database entry's representations:

d(Q t , R) = d i=1 π i (R) ⊗ σ i (Q t ), (6.6)
Using the binary uncertainty F and a discounting factor γ, we can modulate the contribution of each bit in the sum:

∆(Q t , R, γ) = d i=1 [π i (R) ⊗ σ i (Q t )] • (1 -γ • F i (V, θ, K bs )). (6.7)
In summary, our new method, which we will refer to as ULA-CODE, performs the following steps:

• compute primary and secondary uncertainty values π, σ

• blend the two using a balance factor θ

• flag the position of the top K bs uncertain bits

• when querying, discount uncertain bits in the hamming distance computation by a factor γ

The 3 free hyperparameters of the method are the discounting factor γ, the balance factor θ, and the bit skepticism level K bs .

Computational footprint of uncertainty awareness

Accounting for bit uncertainty during retrieval comes at a certain cost, both in terms of time and space. With execution speed and compactness both being key selling points of hashing, it is crucial that the impact of our additions on the overall computational footprint is kept at a minimum.

Formally, we would like the following two constraints to be respected:

1. Redundancy limit: the additional space consumed remains strictly under dN bits(i.e. the size of the original codebook)

2. Speed conservation: the number of additional bit operations required per query is small compared to dN (the number of xor operations for hamming distance computations required in the original algorithm) SSTH-RT ++ , in the previous Chapter 5, egregiously contradicted both; with n dupl truncated duplicates, both the space consumption and the number of operations were multiplied by n dupl . This shows how careless tampering with the codebook purely for the sake of retrieval performance can severely undercut computational performance, which should not happen with ULA-CODE.

We first examine the redundancy limit constraint. Communicating the position of K bs uncertain bits in an array of d bits can trivially be done with another d-bit array acting as a binary mask, i.e. set at 1 at uncertain bit positions. Doing so for each of the N codebook therefore requires d • N additional bits -exactly the limit. However keeping the space consumption strictly underneath is possible by compressing the uncertainty pattern.

The number of possible binary masks of d bits is of course 2 d . Yet, among those, we only need to account for the ones with a predetermined number k of bits set to 1. This drops the number of possibilities to the number of k-combinations of d elements, also known as the binomial coefficient d k = d! k!(d-k)! . Encoding an uncertainty pattern for k bits therefore only requires d u = log 2 d k bits instead of d. Evaluating the difference is not straightforward -we provide examples in Table 6.2. However we are able to provide a lower bound for the number of bits we are able to save:

d -log 2 d k > 1 2 log 2 ( π • d 2 ). (6.8)
A proof for this result is given in the corresponding Appendix F. Practically speaking, any of the 2 du binary masks of k uncertain bits can be indexed by a binary array of size d u ; for example, by using the lexicographic order position written in base 2 (Figure 6.3).

Storing this compressed mask instead of the mask itself preserves space -however restoring the mask using its index is not trivial: this is referred to as the combination unranking problem.

For very low values of k, one can maintain a look-up Fortunately, we can use partial sorting to drastically cut down the overall number of operations. In practice, N is extremely large -applications to extremely large databases is indeed a key motivation of hashing. On the other hand the number K of top items to retrieve should be quite small. Even though we show results for mAP@K for K going up to 100, in practice going through a list of 100 search results every two seconds does not make much sense for the end user or user application.

It is therefore safe to assume we can find K such that N K K. Using partial sorting, N -K irrelevant items can then be filtered out based on the raw Hamming distance, without accounting for uncertainty. This costs the same d • N XOR operations as previously. Within the remaining K items, using uncertainty only requires an additional O(d 2 • K ), which can be considered small next to d • N .

The overall encoding and retrieval pipeline for ULA-CODE, including the use of compressed uncertainty, is shown in Figure 6.4

Encoder training & codebook preparation & evaluation

Bitcodes of size [START_REF] Gonzalez | 1 Recurrent gradient clipping[END_REF]128,192,256 are employed. Independently of the test protocol, the same model trained on the 81000 training set clips is used, in order to assess the versatility of the retrieval system. As previously done, we first train SSTH-RT + as the teacher for LA-CODE. This time, LA-CODE is trained for a maximum of 30 epochs, with early stopping based on bitwise accuracy measured on the validation set.

ULA-CODE reuses LA-CODE's pair of encoders; the difference is in the way the codebook is built, since we incorporate the uncertainty defined above. ULA-CODE's hyperparameter space, which is fairly small, is explored with all 80 combinations shown in Figure 6.5.

The metric employed is still top K Mean Average Precision (mAP@K), with mAP@10 as the main reference. Even though we constrained the problem by dividing videos into units of uniform duration, the incremental nature of our methods enable efficient retrieval, in real time, at any point inside the clip; which was impractical and not attempted with video hashing methods from the rest of the literature [ZWHC16, SZL + 18, WLG + 17, WHG + 19, LCL + 19]. By doing so during testing, we essentially try to examine the retrieval system's responsiveness to the context, or very short-term anticipation; after only watching a portion of a clip, can the system quickly return relevant videos? We therefore report mAP@10 for one third and two thirds of a clip, in addition to the full clip (roughly 10, 20 and 30s respectively).

Results

Influence of hyperparameters

We start by examining the influence of each of the three hyperparameters in ULA-CODE separately. We report two quantities: first, the maximum mAP@10 obtained by fixing the value of one hyperparameter. We refer to this as max ULA-CODE. Second, the average mAP@10 obtained by fixing the value of a parameter and averaging over all combinations containing that value. This is referred to as avg ULA-CODE. LA-CODE sets our baseline. Results are displayed in Figures 6.6, 6.7, 6.8. In those figures a performance data point is obtained at every combination of:

• protocol (Bypass40, Cholec80, CEV64 ) -plot grid column

• bitcode size -plot grid row

• hyperparameter value -x-axis

• observation level α -line color

• mode or method (LA-CODE, avg ULA-CODE or max ULA-CODE) -line texture Across all hyperparameters, max ULA-CODE is obviously superior to avg ULA-CODE, which is itself in the vast majority of cases above LA-CODE. For 256 bits on Bypass40 at full observation, LA-CODE achieves 38%, which is beaten by avg ULA-CODE with a 1.2% minimum margin, and by max ULA-CODE by 2 to 3%. For the same code size and observation level on Cholec80, LA-CODE sets the baseline at 39%, again surpassed by avg ULA-CODE (41.5%) and max ULA-CODE (41.3 to 42%). Similar observations can be made for critical events, with LA-CODE at 38.8%, avg ULA-CODE ranging from 39.5 to 41% and max ULA-CODE ranging from 40.2% to 42.2%.

This means even with a random choice of hyperparameters, the odds of achieving higher performance than LA-CODE are favorable.

For the γ parameter (Figure 6.6), we can see a slight trend favoring higher values: for instance, for 256 bits on critical events at 2/3 observation, max ULA-CODE goes from 41.2% at γ = 0 to 41.5% at γ = 1. In general, this suggests stricter suppression of uncertain bits improves retrieval performance.

For θ (Figure 6.7), it appears that lower values generally lead to higher mAP@10; such as for critical events with 256 bits at 2/3 observation, the dropoff from θ = 0 to The query is from CEV64, a clip showing incising. By discounting uncertain bits, irrelevant results originally returned by LA-CODE (abdominal access and idle) are pushed down ULA-CODE's ranking, while more accurate results appear higher.

In this chapter, we achieved the task of real-time video retrieval on a very-large-scale surgical dataset for the first time. Our proposed method ULA-CODE builds upon its predecessor LA-CODE, and addressed the problem of uncertain bits used in the codebook by measuring their degree of uncertainty, then reporting it in the codebook in a highly compressed manner: by doing so, ULA-CODE provides up to 4 % improvement in terms of retrieval mAP@10, measured using three semantic contexts in surgery: phases for cholecystectomy, phases for bypass and surgical critical events, introduced for the first time in our work. Usability on this wide range of semantics is encouraging for the generalizability of our method. Several correct videos overlooked by the first approach are ranked higher by the second.

CHAPTER 7

SUMMARY

This final chapter recapitulates the contributions presented throughout this work, and how they respond to our original problem of providing real-time support in the operating room with vast amounts of unannotated data. Application possibilities, as well as current limitations and paths for further developments are discussed next.

Summary

The primary goal in the work presented here is the development of methods for surgical activity understanding with endoscopic videos, under two key constraints:

1. Extensive use of unlabelled video data

Real-time capability

These constraints fit our overarching vision of an OR control tower (Figure 1.16) with minimal reliance on human-annotated video data, providing well-timed support to surgeons during interventions. The methods we proposed successfully addressed those.

Addressing unlabelled data domination

As mentioned in Figure 1.15, the state of the Endocorpus dataset reflects the general state of endoscopic video data: generated in massive amounts by operating rooms, yet unannotated and unexplored for its vast majority. Since systematic human-generated annotations are not a scalable option, we turned to semi-and self-supervision in order to make efficient use of unlabelled videos.

The semi-supervised approach presented in Chapter 3 used automatic annotation to turn large quantities of unannotated videos into usable training material for other models: labels generated by a CNN-biLSTM-CRF, while not perfect with respect to ground truth, are sufficient to enhance a CNN-LSTM's performance.

In Chapters 5 and 6, the hash function generating compact binary representations of videos was trained in a self-supervised manner. Since no labels were used, training data was abundantly available -especially in the case of Endocorpus. Additionally, the resulting encoder was label-agnostic: distance between codes was based on visual similarity. Not only retrieval gives the unlabelled data a purpose, it also enables exploring it, functioning as a visual index.

Addressing real-time conditions

While surgical activity understanding from endoscopic videos certainly has potential outside of the operating room -for example in surgical education, skill evaluation or video indexing -our primary target for applications has been in-OR context-aware support from the start. Since this requires the ability to function in real time, the level of difficulty is raised by a considerable amount. In particular, a certain degree of anticipation is needed, which is challenging to achieve due to the variability and unpredictability of surgical workflows.

In Chapter 3, our method took advantage of a model that is not real-time compatible, the CNN-biLSTM-CRF, to annotate data with anticipation of the future, by CHAPTER 7. CONCLUSION reading the video frame sequence in both directions. This artificially annotated data was then fed to the real-time compatible CNN-LSTM.

In Chapter 5, we transformed the previously established approach to video retrieval, by sampling video data in a way that makes retrieval usable in real time with live sources. We also incorporated anticipation in our LA-CODE model, in order to account for missing future frames in real-time conditions.

Chapter 6 introduced a method to cut down the contribution of noisy bits during retrieval. Computational burden is kept at a minimum, in order to preserve the efficiency of hashing for real-time use.

Discussion and future work

Discussion points opened by the work from this thesis can be grouped in three key areas. The first one is methodology, concerning technical details of our approaches. The second is scale, with questions on expanding the data used for our methods. Finally, we discuss the more practical aspects of applications and deployment.

Methods

Evaluating video retrieval in a satisfying manner is a delicate question -to determine whether a returned entry is relevant or not, all video retrieval protocols in the literature rely on class labels provided by the dataset employed. To a certain degree, we mitigated this issue in Chapter 6 by evaluating the same model on multiple sub-datasets, each with its own label type, showing the method can capture visual similarity in a way that is generic across multiple surgical contexts. Still, a protocol that is less reliant on labels would be a major step forward. Indeed, the power of content-based retrieval lies not in its ability to recognize queries based on predetermined classes, but rather in its expressiveness and ability to find information users did not know they were looking for, as it is often the case for popular services such as Bing [HWY + 18] or Google Image Search.

Another pending question is retrieval granularity; even though we are able to retrieve relevant videos from a query, our methods -as well as all video retrieval methods from the literature -do not expose which parts inside of the retrieved videos are relevant. The leeway for achieving this is razor thin: incorporating uncertainty without severely cutting down performance was already a challenging problem. Adding intra-video retrieval on top of ordinary retrieval is likely even more difficult.

Scale

Within the literature on endoscopic video processing, the body of work presented here sits at the top in terms of scale, with 12 types of surgery and over 1.5K recordings of surgical procedures in Endocorpus. Still, this amount is negligible compared to what an actual full-scale database could be: as stated in Chapter 1, Subsection 4.1.2, an ideal case scenario where all procedures are systematically collected would likely lead to databases in the 10 6 -10 7 range. In addition to the issue of raw size, Endocorpus only features a single location and a relatively small number of surgeons. Other clinical institutions and other teams might largely deviate from our dataset in terms of 7.2. DISCUSSION AND FUTURE WORK workflow and appearance, due to, among other factors, different surgical tool brands and different habits when performing surgery. A larger study spanning multiple clinical facilities would be necessary in the future, potentially with the help of federated learning.

In addition to data sourcing and quantity, using our methods with a wider variety of annotation types would be an appropriate next step. For retrieval, we introduced the first dataset of surgical critical events, which could be expanded with more event types in the future. The automatic annotation method from Chapter 3 has so far only been used on cholecystectomy; other more complex surgery types may be interesting targets as well, such as gastric bypass with Bypass40.

Applications & deployment

The efficiency of visual search in other domains leaves no doubt on the potential of video retrieval in surgery. However, a number of questions surrounding in-OR implementation would need to be addressed. Assuming we are able to achieve context awareness as presented in our work and implement it within a system, how would it interact with the surgeon and the clinical staff inside the OR? Video retrieval, in particular, is unprecedented in this kind of context. For publicly available tools such as Google Image Search, the user prompts the search by manually uploading the query, or taking a picture. In the tightly controlled environment of the OR, however, this interaction needs to be carefully designed in order to be as unobtrusive as possible. A vocal command, or a separate display automatically refreshing search results at regular time intervals are possible options. Another one is to delegate the review of retrieved videos to the OR control tower staff, as suggested in Figure 1. 16.

Querying, however, is only half of the user experience; careful attention should be given to the presentation of search results. Showing the retrieved raw video data itself may not be the best option -reviewing it takes time, and paying attention to multiple videos simultaneously is nearly guaranteed to result in cognitive overload. An adequate preview system, as found on popular video platforms, would need to be designed; for instance with animated thumbnails giving a brief and compact overview of a video's content. Showing any relevant video metadata would also be a valuable feature; although in our experiments this metadata was limited to class labels and links to future clips (Chapter 7), content-based retrieval can collect far more descriptive information, as shown by current reverse search engines.

APPENDIX F Uncertain bit flagging

As stated in Chapter 6, the position of exactly k uncertain bits in a 2n-bit array can be flagged using strictly fewer than 2n bits, with the following upper bound:

d -log 2 d k > 1 2 log 2 ( π • d 2 ) (F.1)
The number of possible configurations for the position of k uncertain bits in an array of size 2n is given by the binomial coefficient: A draft for an unpublished but more accessible proof for this inequality than Dutton's [START_REF] Dutton | Computationally efficient bounds for the catalan numbers[END_REF] can be found at https://mathoverflow.net/a/133752 (credits: Noam

G.2 Méthodes G.2.1 Annotations automatiques pour l'identification temps réel des phases

Une première approche pour naviguer au sein d'une base de données brutes, en l'absence d'annotateurs experts humains, consiste à remplacer ces derniers par un modèle entraîné sur un jeu de données réduit. Nous nous intéressons ici à l'un des problèmes fondamentaux de l'analyse de vidéo chirurgicales, à savoir la reconnaissance des phases. Conformément à notre hypothèse de données annotées rares, nous procèdons de manière semi-supervisée: sur 80 vidéos, nous nous autorisons à utiliser les annotations manuelles sur seulement 1 à 20 vidéos. Les modèles utilisés dans ce problème sont sujets à un compromis: temps réel avec performances limitées (CNN-LSTM), ou a posteriori avec performances maximales (CNN-biLSTM-CRF introduit dans nos travaux). Nous parvenons à dépasser ce compromis en utilisant les deux types de modèle de manière complémentaire G.1: le modèle a posteriori, dans le rôle du maître, est entraîné sur les 1 à 20 vidéos manuellement annotées, puis annote automatiquement le reste des 80 enregistrements. L'ensemble sert à entraîner le modèle temps réel, qui tient le rôle d'élève. Le F1-score ainsi obtenu est de 78.2 %, contre 70.2 % avec les 20 vidéos manuellement annotées sans annotations automatiques supplémentaires.

G.2.2 Fouille temps réel de vastes bases de données vidéo génériques

Obtenir des informations sur du contenu vidéo à partir d'un classifieur entraîné à reconnaître un nombre prédéterminé de classes est l'approche canoniquement préconisée en vision par ordinateur, qui pourrait être qualifiée de directe et explicite. À l'inverse, se renseigner sur un contenu en l'utilisant pour rechercher les éléments pertinents d'une vaste base de donnée est une approche indirecte et implicite, qui propose davantage de flexibilité et de polyvalence.

Les fonctions de hachage profondes constituent une méthode efficace pour la fouille de bases de données; celles-ci calculent des clés binaires de taille réduite à partir de contenus de très grandes dimensions. Ces clés étant optimisées pour préserver les similarités et différences entre contenus, il est alors possible de rapidement effectuer des requêtes par simples comparaisons binaires. Les fonctions de hachage sont souvent entraînées de manière auto-supervisée; leur fonctionnement est dans ce cas complètement indépendant des annotations, qui servent uniquement à leur évaluation quantitative. Le hachage présente donc un double intérêt dans notre situation, en permettant d'utiliser les données non annotées et de les explorer via des requêtes.

La vidéo est cependant fortement en retard par rapport aux autres modalités de recherche telles que les images statiques concernant le hachage. Les quelques travaux traitant de ce problème pour les vidéos ne considèrent de plus que la recherche a posteriori, proposant des méthodes incompatibles avec des recherches temps réel à partir de flux vidéo instantanés.

Le cas temps réel G.2 est justement celui que nous choisissons de traiter: considérant une vidéo de durée totale T , nous souhaitons rechercher au sein d'une base de données les vidéos les plus similaires, en observant uniquement les αT premières secondes pour α ∈]0, 1] -cette situation correspond au cas d'une diffusion en direct, ou du streaming. Pour cela nous proposons un encodeur vidéo binaire incrémental et prédictif: un modèle LSTM met à jour la clé binaire toutes les deux secondes environ afin que celle-ci tienne compte du contenu visuel en temps réel. Ce modèle est de plus entraîné à anticiper le futur contenu vidéo, afin de compenser le manque d'information visuelle dû à la diffusion en direct.

Nous présentons notre méthode sur deux jeux de données vidéo génériques de très grande taille: FCVID et ActivityNet. L'évaluation s'effectue à partir des étiquettes d'activité fournis par ces jeux de données: dans le classement des meilleurs résultats de recherche, un résultat est considéré correct si sa classe correspond à celle de la requête. Notre méthode, LA-CODE, surpasse les méthodes non prédictives avec notamment 27.4 % de mAP@20 sur FCVID, 14.7 % sur ActivityNet avec moins de 30% de la vidéo observés, pour des clés binaires de 128 bits.

G.3. CONCLUSION

G.2.3 Fouille temps réel de vastes bases de données vidéo chirurgicales

Pour mettre à l'épreuve nos méthodes de fouilles de données vidéo sur du contenu chirurgical, nous introduisons le jeu de données Endocorpus, contenant 1558 enregistrements complets de 12 types de procédures minimalement invasives. Ces enregistrements sont divisés en clips de 30 secondes environ, formant une base de données de plus de 500000 clips.

Nous montrons qu'un même modèle, entraîné sur un vaste ensemble de clips non annotés, permet de rechercher du contenu au sein de trois bases de données: cholecystectomie, pontage gastrique et événements chirurgicaux critiques. L'évaluation s'effectue à partir des phases pour les deux premières; pour la dernière, à partir du type d'événement critique.

À cela, nous ajoutons une nouvelle méthode de fouille tenant compte de l'incertitude sur les bits des clés binaires représentant les vidéos. Nommée ULA-CODE, cette méthode consiste à comprimer un masque signalant les bits incertains puis à stocker ce masque avec les clés binaires. En décompressant ce masque et en l'utilisant au moment d'une requête pour réduire la contribution des bits incertains, la pertinence des résultats retrouvés augmente de 2 à 4%..

G.3 Conclusion

Les méthodes proposées permettent de tirer parti avec succès des données vidéo endoscopiques non annotées, permettant ainsi de les annoter automatiquement pour l'entraînement de classifieurs temps réel, de les utiliser pour l'entraînement autosupervisé de modèles pour la fouille de bases de données vidéo, et d'explorer ces dernières par le biais de requêtes vidéo instantanées. Ce succès est encourageant pour un passage à l'échelle à partir d'annotations raréfiées, ainsi que le déploiement dans le bloc opératoire de ces méthodes temps réel pour assister le chirurgien.

CONTENTSG

  Résumé en français G.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.2 Méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.2.1 Annotations automatiques pour l'identification temps réel des phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.2.2 Fouille temps réel de vastes bases de données vidéo génériques . G.2.3 Fouille temps réel de vastes bases de données vidéo chirurgicales G.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. 1

 1 Left: trocar inserted into the patient's abdomen, as preparation for the laparoscopic procedure. Right: Surgeon performing a suture, with instruments inserted through trocars. The image on the right is the feed from the laparoscope used for visual feedback. . . . . . . . . . . . 10 1.2 Aftermath of iatrogenic bile duct injury. The common bile duct is sometimes mistaken for the cystic duct and cut as a result. Courtesy of Websurg. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Overview of Surgical Data Science concepts. Image credits: Maier-Hein et al. [MHVS + 17] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 AI-powered control tower concept by Searidge. Image credits: NVIDIA. 14 1.5 Left: diagram from the original patent by Honey et al. for the 1st down line overlay, using multiple cameras in the stadium for registration. Right: Image from Super Bowl LV, with the 1st down line as a dynamic, real-time overlay. It leaves players unoccluded, behaving like a physical line. Image credits: NFL. . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6 AI-controlled safety check: critical view of safety in cholecystectomy.

  Image credits: Mascagni et al. [MVA + 20] . . . . . . . . . . . . . . . . . 16 1.7 (a): Abdominal cavity presenting low amounts of adhesions. (b): Ab-

1. 1

 1 Phases in cholecystectomy . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2 Phases in gastric bypass . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3 Overview of surgical critical events . . . . . . . . . . . . . . . . . . . . 22 1.4 Comparison of surgical video datasets against generic activity datasets 23 1.5 Overview of Endocorpus . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1 Hyperparameter table . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Ablation study for the teacher model, accuracy and average F1 . . . . . 48 3.3 Per-phase precision and recall, CNN-biLSTM-CRF model . . . . . . . . 48 3.4 Teacher-completed annotation set metrics . . . . . . . . . . . . . . . . 50 3.5 Performance with and without teacher-generated annotations. . . . . . 51 5.1 Results breakdown by α range. For each bitcode size: left column shows very early results (VE, average mAP@20 for α from 0.1 to 0.2); Middle column shows early results (E, average for α from 0.1 to 0.5); Right column shows overall results (O, average over all α). . . . . . . . . . . . 76 6.1 Data splitting for all three test protocols. Note that the training set and validation set are common to all three. . . . . . . . . . . . . . . . . 83 6.2 Selected examples for log 2 d k ; d indexes rows, k as a ratio of d indexes columns. In each cell, left is k and right is log 2 d k . . . . . . . . . . . . . 86 6.3 ULA-CODE optimal parameter combinations for each bitcode size and test protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 E.1 Description of critical events reported in CEV64 . . . . . . . . . . . . . 122 List of Abbreviations ANN Artificial Neural Network CNN Convolutional Neural Network DNN Deep Neural Network CRF Conditional Random Field LA-CODE Look-Ahead Code LA-RECO Look-Ahead Reconstruction LSTM Long Short-Term Memory OR Operating Room RNN Recurrent Neural Network SEQ2SEQ Sequence-to-Sequence SSTH Self-Supervised Temporal Hashing SDS Surgical Data Science ULA-CODE Uncertain LA-CODE CHAPTER 1 Introduction ""Even this must have a preface -that is, a literary preface," laughed Ivan, "and I am a poor hand at making one."" -Fyodor Dostoevsky, The Brothers Karamazov Contents 1.1 Clinical & technological context . . . . . . . . . . . . . . . . 10 1.1.1 The OR in the minimally invasive surgery era . . . . . . . . 10 1.1.2 The OR as a high-stakes, timing-sensitive environment . . . 10 1.1.3 The proliferation of signals in the OR & the challenge of data 11 1.2 Models of AI-enhanced support . . . . . . . . . . . . . . . . 13 1.2.1 The AI-enhanced control unit . . . . . . . . . . . . . . . . . 13 1.2.2 Harnessing large databases with search . . . . . . . . . . . . 15 1.3 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.1 Laparoscopic video data collection . . . . . . . . . . . . . . 20 1.3.2 Cholec120 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.3 Bypass40 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.4 CEV64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.5 The gap with large-scale video datasets . . . . . . . . . . . 23 1.3.6 The big picture: Endocorpus . . . . . . . . . . . . . . . . . 24 1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.1. CLINICAL & TECHNOLOGICAL CONTEXT 1.1 Clinical & technological context 1.1.1

Figure 1

 1 Figure 1.1: Left: trocar inserted into the patient's abdomen, as preparation for the laparoscopic procedure. Right: Surgeon performing a suture, with instruments inserted through trocars. The image on the right is the feed from the laparoscope used for visual feedback.

  Figure 1.2: Aftermath of iatrogenic bile duct injury. The common bile duct is sometimes mistaken for the cystic duct and cut as a result. Courtesy of Websurg.

Figure 1

 1 Figure 1.3: Overview of Surgical Data Science concepts. Image credits: Maier-Hein et al. [MHVS + 17]

Figure 1 . 5 :

 15 Figure 1.5: Left: diagram from the original patent by Honey et al. for the 1st down line overlay, using multiple cameras in the stadium for registration. Right: Image from Super Bowl LV, with the 1st down line as a dynamic, real-time overlay. It leaves players unoccluded, behaving like a physical line. Image credits: NFL.

Figure 1

 1 Figure 1.6: AI-controlled safety check: critical view of safety in cholecystectomy. Based on its reading of the anatomy and the instruments, the system determines all three criteria for safely cutting the cystic duct are met. Image credits: Mascagni et al. [MVA + 20]

Figure 1

 1 Figure 1.10: Patent from Google for automatic melody identification from usersubmitted audio for copyright management purposes.

Figure 1 .

 1 Figure 1.12: Left: Cutting of the cystic duct in cholecystectomy, to release the gallbladder. Right: Jejunojejunal anastomosis in bypass. The intestine is stapled to itself, closing the digestive path coming from the stomach.

Figure 1

 1 Figure 1.14: Frames from Endocorpus and ActivityNet. Note the difference in visual diversity and complexity.

Figure 1 .

 1 Figure 1.15: Current state of the Endocorpus dataset. Annotations are only available for a small fraction of it -barely over 15%.

Figure 1 .Figure 1 . 16 :

 1116 Figure1.15 sets the stage for the work of this thesis, overwhelmingly dominated by unannotated data. Collecting, selecting and storing endoscopic video data into datasets is relatively easy compared to having human experts annotate it, which explains the disproportionate 83.4 % of unlabelled videos. This situation suggests that in future developments of Surgical Data Science, overreliance on full supervision with

  Figure 2.1: Endonet CNN-LSTM model for surgical phase recognition on videos. Courtesy of Twinanda et al.

  [START_REF] Lalys | Surgical process modelling: A review[END_REF] define them as the first level of granularity for decomposing surgical workflows. Deep vision models trained to recognize them were first introduced by Dergachyova et al. [DBH + 16] as well as Twinanda et al. in 2016 [TSM + 16]. Twinanda et al.'s EndoNet incorporated a Resnet18 CNN used as a feature extractor followed by a highlevel classifier, either a Support Vector Machine or a Hidden Markov Model. Training was performed in a multi-task manner, with both surgical instrument and phase recognition as learning objectives. Results were shown on the cholec80 dataset, which was introduced in this work as well. Its successor EndoLSTM [TMM + 16, YMMP18] replaced the previous high-level classifier layer with an LSTM. SVRCNet [JDC + 18] uses a similar architecture combining Resnet and LSTM, with an added Prior Knowledge 2.2. ALTERNATIVES TO FULL LABEL SUPERVISION Inference to post-process predictions. Al Hajj et al. [HLC

Figure 2

 2 Figure 2.2: Distillation for early action recognition. The student model, handling partial videos, is trained to copy the representation of the teacher that has knowledge of the full videos. Image credits: Wang et al.

Figure 2

 2 Figure 2.3: Self-supervised temporal hashing method. The binary keys or bitcodes used for retrieval are generated by an encoder trained on a self-supervised reconstruction task. Courtesy of Zhang et al.

"

  Figure 3.1: Surgical phases in the workflow of laparoscopic cholecystectomy

Figure 3

 3 Figure 3.2: Overview of the teacher-student method.

Figure 3

 3 Figure 3.3: Data splitting and sampling process.

Figure 3 . 4 :

 34 Figure 3.4: Ablation studies conducted for the teacher model. Left to right, top to bottom: M1, M2, M3, M4.

  Figure 3.5: Accuracy (left) and F1 (right) for the ablation models, for all mini-training set sizes

Figure 3 . 6 :

 36 Figure 3.6: Qualitative results for the teacher, compared to ablation models -top 3 best and worst. Note the suppression of error bursts.

Figure 3

 3 Figure 3.7: Single loop of self-learning for the teacher.

4. 1 .

 1 Figure 4.1: Voronoï tessellation of a set of data points (blue). Any point in a given convex polygon has the corresponding blue data point as its nearest neighbor.

Figure 4 . 2 :

 42 Figure 4.2: Temporal scales involved in surgical video processing.

Figure 4 . 3 :

 43 Figure 4.3: Features from a trained AlexNet-like CNN. Lower layers capture lower-level information such as color, texture and edges, while higher layers refer to recognizable objects. Image credits: Zeiler et al.

CHAPTER 4 .Figure 4 . 4 :

 444 Figure 4.4: Principle of transfer learning.

Figure 4 . 5 :

 45 Figure 4.5: Recurrent cell function, and its deployment into an RNN.

Figure 4 . 6 :

 46 Figure 4.6: RNN variants. Left: stacked RNN. Right: bidirectional RNN.

  Figure 4.7: LSTM computation.

Figure 4 . 8 :

 48 Figure 4.8: Seq2Seq architecture.

Figure 4 . 9 :

 49 Figure 4.9: Collision probability for hashes of size 32. Collision odds quickly exceed 50%.

Figure 4 .

 4 Figure 4.10: Cryptographic and locality-sensitive hash function purposes. The two types of hash functions have opposite priorities.

Figure 4 .

 4 Figure 4.11: Workaround for training a network with binary outputs.

Figure 5

 5 Figure 5.1: Real-time video retrieval concept. An archery event is being streamed. Simultaneously, a search engine scans a large video database for similar content.

CHAPTER 5 .

 5 REAL-TIME RETRIEVAL BY HASHING LIVE VIDEO SOURCES

Figure 5 . 2 :Figure 5 . 3 :

 5253 Figure 5.2: Comparison of video sampling approaches for two videos of distinct durations. The previous video sampling paradigm (orange) outputs a constant number of features per video, but the rate is variable and determined with knowledge of the entire video length. Our real time-compatible sampling approach (purple) outputs a variable number of features at a constant rate.

Figure 5 . 4 :

 54 Figure 5.4: Training approaches compared for real-time video retrieval.

Figure 5 . 5 :

 55 Figure 5.5: Evaluation protocols for real-time video retrieval.

Figure 5 . 6 :Figure 5 .

 565 Figure 5.6: mAP@20 for all methods, all levels of observation, on FCVID.

Figure 5 .

 5 Figure 5.8: mAP@K for LA-CODE on FCVID

Figure 5 Figure 5 .

 55 Figure 5.9: mAP@20 for LA-CODE on ActivityNet

Figure 5 .

 5 Figure 5.11: Successful example of retrieval over time from FCVID.

Figure 6 . 2 :

 62 Figure 6.2: Primary and secondary uncertainty on the bitcode stored in the codebook.

Figure 6 . 3 :

 63 Figure 6.3: Uncertainty pattern compression. Each 7-bit pattern of two uncertain bits can be assigned a rank from 0 to 7 2 = 5; for example by using the lexicographic order. This rank is then written in base 2. In this case this saves two bits over the original pattern.

Figure 6 . 4 :Figure 6 . 5 :

 6465 Figure 6.4: ULA-CODE pipeline overview. When building the codebook, the uncertainty pattern is compressed then stored alongside the bitcode. During retrieval, the uncertainty pattern is restored using combination unranking, and applied as a mask in the Hamming distance computation.

Figure 6 . 9 :

 69 Figure 6.9: Mean average precision over time.

Figure 6 .

 6 Figure 6.10: Qualitative results, with and without using uncertainty. Left: query clip. Center: LA-CODE search results, green highlight if correct and red otherwise. Right: ULA-CODE. Under thumbnails: black is the bitcode, red is the uncertainty pattern.Several correct videos overlooked by the first approach are ranked higher by the second.

Figure C. 2 :

 2 Figure C.2: FCVID: results for SSTH-RT +

Figure C. 4 :

 4 Figure C.4: FCVID: results for LA-RECO

Figure C. 10 :

 10 Figure C.10: ActivityNet: results for LA-CODE

4 )

 4 k)!(k!) (F.2)The maximum is reached for the central binomial coefficient2n n = (2n)! (n!) 2 . Indeed, 2n k+1 = 2n-k k+1 2n k > 2n k for k < n.Therefore 2n k monotonously increases with k over the left side of n, and monotonously decreases over the right side due to 2n k = 2n 2n-k , leaving 2n n as the maximum. This means we have at most 2n n configurations to map to an m-bit array, requiring log 2 2n n ≤ m. On the other hand, we set for ourselves m < 2n as our limit. A useful result published by Dutton [DB86] states: Note that it also is an asymptotic equivalent for 2n n (easily derived from Stirling's approximation n! ∼ √ 2πn n e n ), making it a tight upper bound.

GFigure G. 1 :

 1 Figure G.1: Le modèle CNN-biLSTM-CRF (maître) annote des données pour le CNN-LSTM (élève), améliorant ainsi ses performances en reconnaissance de phase chirurgicale.

  The place of video search in the clinical space. Besides logistical aspects such as indexing, two main branches of applications can be envisioned: educational and interventional, with the latter requiring real-time operability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.12 Left: Cutting of the cystic duct in cholecystectomy, to release the gallbladder. Right: Jejunojejunal anastomosis in bypass. The intestine is stapled to itself, closing the digestive path coming from the stomach. . 21 1.13 Examples of critical events in surgery, from the CEV64 dataset. . . . . 23 1.14 Frames from Endocorpus and ActivityNet. Note the difference in visual diversity and complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.15 Current state of the Endocorpus dataset. Annotations are only available for a small fraction of it -barely over 15%. . . . . . . . . . . . . . . . . 25 1.16 OR control tower concept, exploiting surgical video retrieval. An unfamiliar situation prompts the surgeon to request assistance. Control room staff is shown, in real time, the surgical phase and a collection of visually similar clips as reference, with corresponding future outcomes -one of which being a case of bile duct injury. In addition to the control room, the workflow navigation display may be redirected for other purposes: for example, an online classroom for surgical training. . . . . 26 Accuracy (left) and F1 (right) for the ablation models, for all minitraining set sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Qualitative results for the teacher, compared to ablation models -top 3 best and worst. Note the suppression of error bursts. . . . . . . . . . 49 3.7 Single loop of self-learning for the teacher. . . . . . . . . . . . . . . . . 51 4.1 Voronoï tessellation of a set of data points (blue). Any point in a given convex polygon has the corresponding blue data point as its nearest neighbor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2 Temporal scales involved in surgical video processing. . . . . . . . . . . 55 4.3 Features from a trained AlexNet-like CNN. Lower layers capture lowerlevel information such as color, texture and edges, while higher layers refer to recognizable objects. Image credits: Zeiler et al. . . . . . . . . 56 4.4 Principle of transfer learning. . . . . . . . . . . . . . . . . . . . . . . . 57 LIST OF FIGURES 4.5 Recurrent cell function, and its deployment into an RNN. . . . . . . . . 4.6 RNN variants. Left: stacked RNN. Right: bidirectional RNN. . . . . . 4.7 LSTM computation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Seq2Seq architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Collision probability for hashes of size 32. Collision odds quickly exceed 50%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Cryptographic and locality-sensitive hash function purposes. The two types of hash functions have opposite priorities. . . . . . . . . . . . . . 4.11 Workaround for training a network with binary outputs. . . . . . . . . 5.1 Real-time video retrieval concept. An archery event is being streamed. Simultaneously, a search engine scans a large video database for similar content. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Comparison of video sampling approaches for two videos of distinct durations. The previous video sampling paradigm (orange) outputs a constant number of features per video, but the rate is variable and determined with knowledge of the entire video length. Our real timecompatible sampling approach (purple) outputs a variable number of features at a constant rate. . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Binary autoencoder training process. . . . . . . . . . . . . . . . . . . . 5.

Hu et al. . . . . . . . . . . . . . . . 18 1.10 Patent from Google for automatic melody identification from user-submitted audio for copyright management purposes. . . . . . . . . . . . . . . . . 19 LIST OF FIGURES 1.11 2.1 Endonet CNN-LSTM model for surgical phase recognition on videos. Courtesy of Twinanda et al. . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Distillation for early action recognition. The student model, handling partial videos, is trained to copy the representation of the teacher that has knowledge of the full videos. Image credits: Wang et al. . . . . . . 34 2.3 Self-supervised temporal hashing method. The binary keys or bitcodes used for retrieval are generated by an encoder trained on a selfsupervised reconstruction task. Courtesy of Zhang et al. . . . . . . . . 37 3.1 Surgical phases in the workflow of laparoscopic cholecystectomy . . . . 40 3.2 Overview of the teacher-student method. . . . . . . . . . . . . . . . . . 42 3.3 Data splitting and sampling process. . . . . . . . . . . . . . . . . . . . 44 3.4 Ablation studies conducted for the teacher model. Left to right, top to bottom: M1, M2, M3, M4. . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.5

  We provide a detailed breakdown in Table1.5. Unless the videos belong to one of the previously mentioned subsets, no annotations other than the surgery types are available. The work presented in this thesis is the first attempt to exploit it and explore its contents; even without annotations, the scale of Endocorpus makes it an appropriate target for unsupervised video retrieval.

	CHAPTER 1. INTRODUCTION
	Surgery	Description	Count Duration (h)
	Cholecystectomy	Removal of gallbladder	518	1.4 ± 0.4
	Bypass	Stomach reduction	388	1.8 ± 0.5
	Hernia	Inguinal hernia repair	341	2.1 ± 0.3
	Eventration	Diaphragmatic eventration repair	133	1.9 ± 0.5
	Bypass robot	Robot-assisted stomach reduction	125	2.0 ± 0.5
	Sigmoidectomy	Colon removal	118	1.2 ± 0.4
	Sleeve gastrectomy	Stomach reduction	90	1.7 ± 0.4
	Nissen	Esophageal sphincter reinforcement	87	1.9 ± 0.3
	Adrenalectomy	Adrenal glad removal	25	1.9 ± 0.4
	Hepatic surgery	Liver-related interventions	17	2.4 ± 0.6
	Pancreatic surgery	Pancreas-related interventions	12	5.3 ± 1.1
	Sleeve robot	Robot assisted stomach reduction	11	2.4 ± 0.8
		Table 1.5: Overview of Endocorpus
	3.9% the various types of surgery. 1.9% 7.7% 3.1%	phases + instruments + actions phases + instruments phases critical events unannotated
		83.4%
	Videos last on average 140 min, with major discrepancies between

  Patrini et al. [PNNC16] performed a theoretical study of label noise effect on common loss functions. [XXY + 15, NLX15] both leverage large amounts of web-sourced images for image classification. Cheng et al. [CZZ + 20] used an auxiliary model called Side Information Network to estimate the correctness of images with label noise. In semi-supervised learning methods, a small amount of annotated training data is available, as well as a certain amount of completely unannotated data. Those methods are appropriate in contexts where data is abundant, but annotations are scarce due to time constraints or costs. Dai et al.'s [DG13] method builds prototype sets from the annotated data points, trains classifiers on each set then uses them as an ensemble. Sajjadi et al. [SJT16] introduced a loss function enforcing robustness to random transformations on the CHAPTER 2. RELATED WORK unlabeled data. Radosavovic et al. [RDG + 18] labeled the unannotated images with ensembled predictions on transformed duplicates. Iscen et al. [ITAC19] used graph methods to propagate labels to the unannotated part of the dataset.

Rosenberg et al. [RHS05]

presented a self-training method for object detection.

Table 3

 3

	.1: Hyperparameter table
	CNN pretraining
	Learning rate	5 • 10 -5
	# of epochs	27
	Minibatch size	32
	Weight decay	5 • 10 -4
	LSTM
	Learning rate	5 • 10 -5
	# of epochs	350
	State size	128
	Dropout	0.3
	Weight decay	5 • 10 -4
	CRF
	Learning rate	5 • 10 -5
	# of epochs	350
	Weight decay	5 • 10 -3
	BiLSTM/BiLSTM-CRF
	Learning rate (biLSTM)	1 • 10 -3
	Learning rate (biLSTM-CRF)	1 • 10 -4
	# of epochs	350
	State size	2 • 64
	Dropout	0.4
	Weight decay	5 • 10 -4
	Weight decay	5 • 10 -4

Table 3 .

 3 2: Ablation study for the teacher model, accuracy and average F1 ± 25 76.9 ± 12.6 62.6 ± 17 80.4 ± 11.5 93.4 ± 3.9 96.5 Rec 50.5 ± 44.9 64.3 ± 15.8 39.4 ± 26.1 31.6 ± 10.9 75.9 ± 2.9 79.9

		1	3	5	10	20	80
	M1	Acc 40.8 ± 2.6 57.3 ± 1.5 62.2 ± 1.2 67.4 ± 1.5 71 ± 1.9 F1 23 ± 4.3 39.9 ± 4.1 48.8 ± 2.6 56 ± 1.9 59.1 ± 1.6 63.8 75.3
	M2	Acc 41 ± 3.5 F1 22.1 ± 5.2 40.7 ± 4.6 48.5 ± 3.3 54.3 ± 1.3 59.9 ± 1.8 69.7 58 ± 1.2 63 ± 0.6 65 ± 0.3 72.5 ± 1.9 80.5
	M3	Acc 40.1 ± 4.7 65.4 ± 5.7 72.3 ± 0.9 74.7 ± 2.6 80.5 ± 0.7 86.3 F1 5 ± 2.9 47.4 ± 9.9 57.9 ± 1.8 62.7 ± 3 70.2 ± 1.3 78.2
	M4	Acc 36.5 ± 4.7 66.3 ± 3.7 73.7 ± 1.6 76.6 ± 3 82.6 ± 0.6 88.4 F1 2.9 ± 3 47.9 ± 8.5 60.1 ± 5 67 ± 3.8 74.5 ± 1.3 81.7
	M5	Acc 40.1 ± 3.1 71.1 ± 4.6 76.2 ± 0.3 78.5 ± 2.6 84.1 ± 1 F1 21.1 ± 11 55.3 ± 9 65.8 ± 1.2 69.7 ± 1.3 75.8 ± 1.5 82.5 89.5
	Table 3.3: Per-phase precision and recall, CNN-biLSTM-CRF model
		1	3	5	10	20	80
	P1	Pre Rec 56.6 ± 26.7 77.4 ± 14.8 51.7 ± 4.8 54.4 ± 14.1 92.6 ± 4.5 96.4 5.5 ± 8.4 59.6 ± 0.8 52 ± 14.3 56.9 ± 14.7 68.4 ± 8.3 86.6
	P2	Pre 48.3 ± 42.3 48.1 ± 10.5 80.1 ± 3.7 Rec 24.8 ± 23.7 83.5 ± 10.7 84.7 ± 3.1	77.1 ± 0.9 58.8 ± 10 68.9 90.6 ± 5 87.2 ± 2.2 83.4
	P3 36.7 P4 Pre Pre 61.3 ± 10.4 75.4 ± 3.2 Rec 45.9 ± 45.2 50.1 ± 29	81.1 ± 5.2 84.4 ± 4.8	86.3 ± 6.7 83.1 ± 3.3 89.4 80.4 ± 1.8 70.3 ± 8.8 72.7
	P5	Pre Rec 12.9 ± 11.6 71.8 ± 16.2 83.3 ± 1.7 0 ± 0 10.9 ± 15.5 74.4 ± 3.1	77.7 ± 0.8 42.6 ± 5.1 53.5 84 ± 3.1 83.2 ± 1.4 88.2
	P6	Pre Rec 11.3 ± 16.6 71 ± 11.9 3.7 ± 6.4 38.7 ± 29.5 80.4 ± 2.1 46.7 ± 7.6	76.2 ± 4.2 85.1 ± 2.8 91.5 61.5 ± 5.4 81.2 ± 3.6 91.5
	P7	Pre 60.3 ± 44.7 82.1 ± 8.5 Rec 50.3 ± 38.9 64.6 ± 8.3 77.7 ± 10.1 77.8 ± 9.5 64.1 ± 7.9 70.8 ± 1.6 87.1 ± 3.6 94.1 80 ± 4.1 77.3
	Avg	Pre 26.4 ± 4.5 Rec 40.5 ± 18.5 62.9 ± 7.5 62 ± 6.1	70.4 ± 4.2 66.8 ± 4.7	75.1 ± 1.6 75.8 ± 1.4 82.6 68.6 ± 0.5 79.8 ± 1.3 84.5

Table 3 .

 3

			4: Teacher-completed annotation set metrics
			1	3	5	10	20
	P1	Pre 44.4 ± 33.4 63.5 ± 10.5 68.8 ± 10.3 Rec 4.6 ± 5 55.2 ± 3.4 47.9 ± 2.8	78.2 ± 5.3 52.4 ± 12.7	85.9 ± 5.5 73.5 ± 4.3
	P2	Pre Rec 35.4 ± 17.2 60.9 ± 4.7	81.1 ± 1.9 77.4 ± 5.7	86 ± 2.5 79.1 ± 6.6	83.1 ± 2.3 88.9 ± 0.3	90.3 ± 1.6 91.6 ± 3
	P3	Pre 79.7 ± 28.8 Rec 0.6 ± 0.2	67.9 ± 9.4 19.5 ± 12.3	66.2 ± 18.7 47 ± 23.2	76.3 ± 5.4 40.9 ± 7	84.3 ± 2.5 60 ± 5.8
	P4	Pre 53.6 ± 18.6 72.7 ± 10.5 Rec 60.8 ± 36.9 84.6 ± 5.2	74.5 ± 4 89.2 ± 2.9	83.2 ± 0.6 86.4 ± 4.4	87.4 ± 3.6 92.5 ± 1.5
	P5	Pre 87.2 ± 11.4 66.6 ± 14.9 Rec 23.2 ± 16.5 78.6 ± 9.1	77.6 ± 1.9 81.7 ± 1	82.8 ± 3.1 81.1 ± 4.2	83.9 ± 2.9 88.3 ± 2.1
	P6	Pre 43.4 ± 39.5 Rec 43.9 ± 38.9 52.2 ± 24.1 51.2 ± 10.1 71.2 ± 10.1 70.1 ± 9.1 71.8 ± 7.5 76.9 ± 4.2	87.3 ± 1.2 82 ± 4
	P7	Pre 58.1 ± 31.3 Rec 13.4 ± 14.8	62.4 ± 5 72.3 ± 8.1	63.3 ± 9.2 77.6 ± 7.9	71.8 ± 5.9 81.2 ± 1.8	84.4 ± 4.3 84.2 ± 2.6
	Avg	Pre Rec	61.3 ± 3.8 26 ± 15.7	69.2 ± 2 62.8 ± 5.3	72.6 ± 5.3 67.7 ± 4.7	78.9 ± 0.8 71.7 ± 2.3	86.2 ± 1.3 81.7 ± 0.6
	Acc		39.2 ± 4.7 73.1 ± 3.1 76.6 ± 1.2	81.6 ± 1	88 ± 1.2
	F1		23.5 ± 3.2	62 ± 4.7	67.6 ± 0.8 73.7 ± 2.1 83.5 ± 1.1

Table 3 .

 3 5: Performance with and without teacher-generated annotations.

			1	3	5	10	20
		Acc 40.1 ± 4.7 65.4 ± 5.7 72.3 ± 0.9 74.7 ± 2.6 80.5 ± 0.7
	CNN-LSTM,	Pre 20.7 ± 1.9 51.7 ± 7.1 60.4 ± 2.9 64.1 ± 1.5 71.1 ± 0.7
	no teacher	Rec 17.5 ± 7.5 58.6 ± 8.2 64 ± 5.5	68 ± 3.1 64.1 ± 2.7
		F1	5 ± 2.9	47.4 ± 9.9 57.9 ± 1.8 62.7 ± 3 70.2 ± 1.3
		Acc 42.1 ± 6.3 74.6 ± 3.6 77.7 ± 0.8 79.1 ± 0.9 83.4 ± 0.3
	CNN-LSTM,	Pre 24.6 ± 5.6	63 ± 5	65.8 ± 5.1 66.6 ± 1.7 73.5 ± 1.2
	with teacher	Rec 38.9 ± 19.4 65.1 ± 7.3 72.3 ± 5.2 74.7 ± 1.7 76.8 ± 0.7
		F1 14.5 ± 13.5 56.1 ± 8.6 64.5 ± 2.9 66.9 ± 3.1 73.2 ± 0.8
	CNN-	Acc 40.1 ± 3.1 71.1 ± 4.6 76.2 ± 0.3 78.5 ± 2.6 84.1 ± 1
	biLSTM-	Pre 26.4 ± 4.5	62 ± 6.1 70.4 ± 4.2 75.1 ± 1.6 75.8 ± 1.4
	CRF, no	Rec 40.5 ± 18.5 62.9 ± 7.5 66.8 ± 4.7 68.6 ± 0.5 79.8 ± 1.3
	teacher	F1	21.1 ± 11	55.3 ± 9 65.8 ± 1.2 69.7 ± 1.3 75.8 ± 1.5
	CNN-	Acc 43.1 ± 7.5 74.9 ± 4.6 78.7 ± 1 80.8 ± 0.8 86.3 ± 1
	biLSTM-	Pre 26.3 ± 4.1 64.2 ± 5.8 67.4 ± 5.9 70.2 ± 2.7 78 ± 1.4
	CRF, with	Rec 38.8 ± 16.5 65 ± 7.3
	teacher

  Table5.1: Results breakdown by α range. For each bitcode size: left column shows very early results (VE, average mAP@20 for α from 0.1 to 0.2); Middle column shows early results (E, average for α from 0.1 to 0.5); Right column shows overall results (O, average over all α). CHAPTER 5. REAL-TIME RETRIEVAL BY HASHING LIVE VIDEO SOURCES most observation levels. Compared to SSTH-RT ++ the improvement is smaller: around 2% on most observation levels. Outdoing this approach, even by a small margin, is however significant since this came at no extra storage and search time cost compared to the baseline, while SSTH-RT ++ requires a codebook 10 times larger, takes 10 times as long to search (plus extra time to remove duplicate results).

			96 bits			128 bits			192 bits			256 bits
	FCVID	VE	E	O	VE	E	O	VE	E	O	VE	E	O
	SSTH-RT	17.8 23.5 27.6	20.2 25.9 29.9	20.9 27.4 31.8	11.5 20.6 27.9
	SSTH-RT +	20.3 24.2 26.6	22.9 27.6 30.6	24.2 29.4 32.6	18.5 25.6 31.0
	SSTH-RT ++	22.5 26.2 28.2	25.5 29.7 32.1	26.2 30.9 33.6	25.4 31.6 35.6
	LA-RECO	21.5 24.6 26.2	25.7 28.8 30.5	28.4 31.5 33.0	28.6 31.2 32.6
	LA-CODE	24.8 27.5 28.8 27.4 30.2 31.4 30.3 33.5 35.0 32.0 34.9 36.3
	ActivityNet	VE	E	O	VE	E	O	VE	E	O	VE	E	O
	SSTH-RT	7.8	12.2 14.9	8.3	13.4 16.5	7.8	14.0 17.9	8.0	15.7 20.6
	SSTH-RT +	9.7	12.1 13.7	10.4 14.2 16.5	12.1 16.4 18.5	13.3 17.3 19.6
	SSTH-RT ++	10.9 13.6 15.0 12.2 15.8 17.8	14.2 18.4 20.3 15.4 19.5 21.4
	LA-RECO	11.3 13.2 14.0	12.7 14.8 15.6	14.5 17.2 18.1	16.8 19.3 19.9
	LA-CODE	12.9 14.6 15.0 14.7 17.9 19.4 16.8 19.1 19.8 17.0 19.2 19.9

Table 6 .

 6 Figure 6.1: Endocorpus splitting for retrieval experiments (the size of graphical elements in the diagram does not reflect data quantities). 1: Data splitting for all three test protocols. Note that the training set and validation set are common to all three.

	Cholec80

  This is roughly exponential; to provide one example, a look-up table for uncertainty patterns of 48 bits in arrays of 96 bits would approximately consume 3.5 • 10 58 bits

			table during retrieval. Looking
	up a mask costs O(1); space complexity, however, is C s = d • k d bits. In the worst case of k = d 2 , we can use Stirling's approximation to gauge this quantity:
	C s ∼ 4 d d π	.	(6.9)

données vidéo de manière incrémentale, au fur et à mesure du déroulement en direct de la vidéo utilisée comme requête. Un archer est filmé; le flux vidéo est soumis au moteur de recherche, qui retrouve deux résultats corrects sur trois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Acknowledgements

CHAPTER 4

Learning efficient video representations for retrieval "In the afterlife you relive all your experiences, but this time with the events reshuffled into a new order: all the moments that share a quality are grouped together."

-David Eagleman, Sum CHAPTER 6. REAL-TIME SURGICAL VIDEO RETRIEVAL WITH UNCERTAINTY θ = 1 is over 2%. We can therefore assume that, generally speaking, the secondary uncertainty is more informative, and has higher odds of pointing towards faulty bits in the bitcode. The trend for K bs is more difficult to identify (Figure 6.8), although the results seem to slightly lean towards higher values. This would mean the number of untrustworthy bits is generally close to half the size of the bitcode. However this comes with a caveat: the compression rate of the uncertainty pattern decreases as the number of uncertain bits to report gets close to d/2.

For every code size and protocol, we are able to obtain an optimal value based on the highest mAP@10 achieved by ULA-CODE, averaged over all levels of observation. These optimal hyperparameters are reported in 6.3. The combinations found seem to confirm the trend observed: higher values of γ and K bs , lower values for θ. Table 6.3: ULA-CODE optimal parameter combinations for each bitcode size and test protocol.

Comparison against baselines

The max ULA-CODE reported here uses the hyperparameter combinations found in Table 6.3. This time, avg ULA-CODE uses the average performance over the entire hyperparameter space. Additionally, we report the performance of SSTH-RT + . mAP@10 is plotted for all three levels of observation: 10s, 20s and the complete clip of 30s. On average, ULA-CODE outperforms our previous approach LA-CODE by 1 to 2 %. An optimized choice of parameters doubles this gain, surpassing LA-CODE by a 3 to 4 % margin. Exceptions to the order between the approaches -SSTH-RT + followed by LA-CODE, then average ULA-CODE and best ULA-CODE -in terms of performance are rare. For critical events, across all bitcode sizes and levels of observation, avg ULA-CODE exceeds the baseline LA-CODE by a mostly consistent 2% margin, Generally speaking, overall performance is higher for Cholec80 (especially for 128 and 192 bits), which makes sense as it has a simpler workflow than Bypass40 and is visually simpler than CEV64.

Qualitative results

Here we provide qualitative results in Figure 6.10 for surgical video retrieval, comparing search results returned by LA-CODE and ULA-CODE for a surgical clip used as the query. We display the bitcode corresponding to a video beneath its thumbnail, as well as the corresponding uncertainty pattern. The code size used is 128; for ULA-CODE, the parameters used were γ = 0.75, θ = 0, K bs = 64.

Appendices

APPENDIX A

List of publications

This method of scaling back gradients above a certain magnitude threshold is called norm clipping; using this, Pascanu et al. were able to successfully train RNNs to generate longer sequences than with unclipped gradients.

In practice however, extreme cases can cause this workaround to fail. Those are cases where explosion occurs in a single training iteration, i.e. if ∇ W L yields NaN in the first place. In that case attempting to scale the result back still yields NaN, returning to the original issue.

APPENDIX B. RECURRENT GRADIENT CLIPPING

B.2.2 Clipping between RNN iterations

Drawing inspiration from artificial gradient methods featured in [ZWHC16, HCS + 16], we define the following computation node: Experiments first performed in Chapter 5 were prone to NaN errors, which persisted after implementing standard gradient clipping. After implementing recurrent gradient clipping, no NaN errors were reported again.

APPENDIX C

Detailed mAP@K results for retrieval on generic activity datasets This appendix expands on mAP@K retrieval results shown in Chapter 5. Each group of four sets of curves corresponds to a method, with each set of curves accounting for a particular code size and each curve showing mAP@K for a certain level of observation.

APPENDIX D EndoVis 2019 Surgical Workflow challenge

The EndoVis 2019 Surgical Workflow Challenge was organized as a side event for the 2019 edition of MICCAI. Participants were given a dataset of 24 annotated recordings of laparoscopic cholecystectomy from Heidelberg University Hospital, named HeiChole, to be used as training material for three recognition tasks: surgical phase recognition, instrument recognition and action recognition.

After the competition, submissions remained open, inviting non-competing teams such as ours to contribute solutions for the final publication. Our submission as Team CAMMA 1 took on the surgical phase recognition task.

D.1 Methods

D.1.1 Overview

Two visual feature extractors are employed in our approach: Inception-Resnet (IRN) [START_REF] Szegedy | Inception-v4, inception-resnet and the impact of residual connections on learning[END_REF] and Inflated-3D (I3D) [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF]. Features extracted by each of them serve as input for separate LSTM models. A third LSTM trained on the combined features is also added. Predictions from the three temporal models are ensembled with majority voting to obtain the final predicted surgical phase class (Figure D.1).

D.1.2 Data preparation

We used 4-fold cross-validation for our experiments, splitting the dataset in a training set of 18 and a validation set of 6 in each fold. Frames were resized to (256, 455) pixels. to "Mixed 7a" were frozen during this process. The 1536-d output from "Conv2d 7b" was sent to two separate fully connected layers -one for tools and one for phases.

D.1.3 IRN-LSTM

We then used the trained IRN model to extract 1536-d feature vectors from videos at 1 fps. A 1-layer LSTM with 192 units was trained on the feature vector sequences, again on simultaneous phase & tool recognition.

D.1.4 I3D-LSTM

I3D was initialized using Kinetics-pretrained parameters. To finetune it, we supplied it with 25-frame clips from training videos at 25 fps. Layers up to "Mixed 5b" were kept frozen. The (4, 8, 15, 1024) output feature was average pooled into a (1, 1, 2, 1024) = 2048-d vector, which served as input for two separate fully connected layers for instrument and phase prediction.

2048-d feature vectors were extracted from videos at 1 fps, then fed to a 1-layer LSTM with 512 units.

D.1.5 DUAL-LSTM

In this setup both IRN and I3D are employed. We pretrained them as described in the previous sections, then concatenated features corresponding to the same timestep into a single 3584-d vector, which goes into a 1-layer LSTM with 512 units. For this LSTM we found that employing the distillation method presented in [?] slightly improves phase recognition performance: a bidirectional LSTM is first trained on phase & tool recognition, then the (monodirectional) LSTM is trained on the same task plus an L2 loss term forcing its hidden states to be similar to those of the bidirectional model. This is meant to incorporate anticipation into the LSTM, which does not have access to future frames in the video but must learn to mimic the behavior of a model that does.

D.1.6 Ensembling

The final phase prediction model is an ensemble of the three architectures presented above. We used majority voting as a way to aggregate the predictions from each of the networks. The contribution of each network is weighted equally.

In the dataset some phases are more common and last across more frames than others. Because of this imbalance, the networks may perform worse for the less prevalent classes. To mitigate this tendency, we double the votes for the gallbladder packaging and retraction phases during the ensembling process.

D.1.7 Model selection

Hyperparameters were selected based on average validation performance over all 4 folds. We submit two different models; the first one trained on one fold's training set, with the corresponding validation set used for early stopping. The other one is trained on all 24 videos, with training stopped on the average stopping epoch over 4 folds.

D.1.8 Experimental setup

Tensorflow 1.14 was used for all experiments. Models were trained on servers fitted with NVIDIA GTX1080Ti or P100 GPUs.

D.2 Conclusion

Several methods were incorporated into our approach in order to capture as much information as possible from a limited dataset of videos: multitask phase and instrument training, two sets of visual features from a 2D and a 3D CNN, three separate LSTMs -one of them having been trained with distillation from a bidirectional model. With an average F1 score of 68.78%, our team placed first out of 9 contributing teams.

APPENDIX E Critical events in CEV64

The CEV64 dataset was built from 64 complete recordings of surgical interventions taken from Endocorpus: its objective was to study moments in surgery with a high degree of clinical importance, for reasons detailed in Table E.1. The value in terms of clinical application is substantial: documentation, surgical reports, education, training and skill assessment are a few examples that can be envisioned outside of the OR. Intraoperatively, critical event lookup may serve as a powerful monitoring reference tool as mentioned many times throughout this work.

Unlike the most prominent datasets for surgical activity understanding -such as Cholec80 -which focus on a single type of procedure, here a wide range of abdominal procedures is covered with 6 distinct types featured:

Events tend to be well-spread across videos in the dataset as shown in Figure E.1, suggesting their high potential for generalizability. Most events can be found in nearly half the videos.

Annotations were defined then performed by two hepato-biliary surgeons from IHU Strasbourg, Dr. P. Mascagni & Dr. J. Verde, using the MOSaiC video annotation platform. For each instance of an event, the start and the end were set by the annotator. Annotated videos were then broken into clips of 30 seconds each for retrieval; each clip was marked with a given event if said event overlapped with it for over 50% of the clip duration. Statistics for collected clips are presented in Figure E.2.

Event classes are noticeably imbalanced; "Out of body" is particularly predominant with over 3200 clips while "sealing" tends to be quite rare, with under 100 clips. The rest tends to be mostly balanced with a few hundred clips each. In Chapter 6's retrieval experiments, query and codebook sets were therefore sampled evenly across all classes. To the 10 reported event classes, a final background class was added with clips sampled outside of any marked critical event, thus completing the 11 classes found in CEV64.

Taking log 2 of the last term yields the following upper bound:

Meaning in the worst case scenario of n bits to flag out of 2n, we can still use m = 2n -1 2 log 2 (π • n) and strictly remain under the 2n bit limit, for n > 1 (n = 1 trivially requires 1 bit).

The compression rate log 2 (πn)/4n tends to 0 as n tends towards +∞; however it should be noted that this is in the one worst case of k = n. Values closer to 0 or 2n lead to much more favorable compression rates.

APPENDIX G Résumé en français

G.1 Introduction

En l'espace de quelques années, les techniques de vision par ordinateur ont progressé de manière considérable grâce aux récents développements réalisés dans le domaine de l'apprentissage profond. Ces techniques, désormais capables de rivaliser avec la vision humaine sur un grand nombre de tâches visuelles, permettent d'offrir une assistance en temps réel dans de nombreux domaines d'application où les enjeux sont importants, la marge d'erreur est faible et la cadence de travail est soutenue.

Un tel système d'assistance, construit à partir d'algorithmes de vision performants, serait donc particulièrement adéquat au sein d'un bloc opératoire pour venir en aide au chirurgien et au personnel clinique. En particulier, le flux vidéo intra-abdominal utilisé en chirurgie minimalement invasive est une source d'information extrêmement riche, dont le contenu peut être analysé pour fournir au praticien en temps réel des informations pertinentes sur l'action ou l'événement en cours de réalisation. Cependant, un obstacle majeur au développement de ces algorithmes est la rareté des données annotées; entraîner un réseau de neurones de manière complètement supervisée en requiert une quantité considérable.

La base de données dont nous disposons est vaste: plus de 4800 heures de procédures chirurgicales complètes, réparties sur 12 types de procédures mini-invasives en chirurgie abdominale. Les annotations sont cependant fortement limitées: sur les 518 cholecystectomies et 318 pontages gastriques disponibles, respectivement 120 et 40 sont annotées avec leur décomposition en phases. En l'absence d'annotations, cette base de donnée est pour l'essentiel inexploitée et inexplorée. Collecter plus d'annotations semble être une solution évidente; à grande échelle cependant celle-ci entraînerait des coûts et des délais prohibitifs, d'où la nécessité de solutions alternatives.

Ce constat est le point de départ des travaux présentés dans cette thèse, où nous cherchons à utiliser et explorer cette immense réserve de données brutes pour obtenir des modèles temps réel performants sur des tâches d'analyse vidéo en chirurgie minimalement invasive.

Résumé en anglais

Endoscopic video streams, as rich sources of information on the operating field, show great potential for exploitation by deep learning-based computer vision algorithms. Such algorithms can indeed serve as the foundation for context-aware surgery systems, capable of improving clinical outcomes by assisting surgeons during interventions. However this approach would require, under ordinary circumstances of full supervision, vast quantities of annotated recordings. While video data is abundant in endoscopy, annotations are highly scarce, which calls for alternative solutions using unannotated videos. We first propose a semi-supervised surgical phase recognition method, where an offline teacher model automatically labels data for a real-time model. We then move from recognition to video retrieval tasks, with self-supervised methods capable of continuously scanning large video databases for content visually matching a video live stream.

Keywords: Deep learning -Computer vision -Retrieval -Hashing -Self-supervised learning -Semi-supervised learning -Endoscopy