Florent Lalys

Laurent Riffaud

David Bouget

Pierre Jannin

An application-dependent framework for the recognition of high-level surgical tasks in the OR

Keywords: Surgical phase, digital microscope, cataract surgeries, DTW

Surgical process analysis and modeling is a recent and important topic aiming at introducing a new generation of computer-assisted surgical systems. Among all of the techniques already in use for extracting data from the Operating Room, the use of image videos allows automating the surgeons' assistance without altering the surgical routine. We proposed in this paper an application-dependent framework able to automatically extract the phases of the surgery only by using microscope videos as input data and that can be adaptable to different surgical specialties. First, four distinct types of classifiers based on image processing were implemented to extract visual cues from video frames. Each of these classifiers was related to one kind of visual cue: visual cues recognizable through color were detected with a color histogram approach, for shape-oriented visual cues we trained a Haar classifier, for texture-oriented visual cues we used a bag-of-word approach with SIFT descriptors, and for all other visual cues we used a classical image classification approach including a feature extraction, selection, and a supervised classification. The extraction of this semantic vector for each video frame then permitted to classify time series using either Hidden Markov Model or Dynamic Time Warping algorithms. The framework was validated on cataract surgeries, obtaining accuracies of 95%.

Introduction

The field of surgical process analysis and modelling has recently gained much interest. Due to the technologically rich environment of the Operating Room (OR), a new generation of computer-assisted surgical (CAS) systems has appeared. As a result of these new systems, a better management, safety, and comprehension of the surgical process is needed. For such purposes, systems should rely on a context-aware tool, which knows the score to be played for adapting assistance accordingly. The challenge is therefore to assist surgery through the understanding of OR activities, which could be introduced in CAS systems. Clinical applications also include evaluation and training of surgeons, the creation of context-sensitive user interfaces, or the generation of automatic post operative reports.

The goal is to collect signals from the OR and automatically derive a model. While it is possible to design such model manually, there are advantages of automating this process, mainly because manual work is time-consuming and can be affected by human bias and subjectivity. Due to the increasing number of sensors in the OR, the automatic extraction of data is now easier. Based on these signals, it's possible to recognize high-level tasks and hence avoid any additional installation of materials. Among all sensors, teams recently focused on videos coming from cameras already used in the clinical routine, which are a rich source of information. Compared to other data extraction techniques, it uses a source that does not have to be controlled by humans, automating the surgeons' assistance without altering the surgical routine.

Current work has made progress in classifying and automating the recognition of high-level tasks in the OR based on videos. Using laparoscopic videos, Speidel et al. [START_REF] Speidel | Situation modeling and situation recognition for a context-aware augmented reality system[END_REF] focused on surgical assistance by identifying 2 scenarios: one for recognizing risk situations and one for selecting adequate images for visualization. Their analysis was based on augmented reality and computer vision techniques. Lo et al. [START_REF] Lo | Episode Classification for the Analysis of Tissue-Instrument Interaction with Multiple Visual Cues[END_REF] used vision to segment the surgical episode. They used color segmentation, shape-from-shading techniques, and optical flows for tracking instruments. These features, combined with other low-level cues, were integrated into a Bayesian framework. Klank et al. [START_REF] Klank | Automatic feature generation in endoscopic images[END_REF] extracted image features for scene analysis and frame classification. A crossover combination was used for selecting features, while Support Vector Machines (SVMs) were used for the classification. Blum et al. [START_REF] Blum | Modeling and Segmentation of surgical workflow from laparoscopic video[END_REF] automatically segmented the surgery into phases. A Canonical Correlation Analysis was applied based on tool usage to reduce the feature space, and the modeling of resulting feature vectors was performed using Dynamic Time Warping (DTW) and Hidden Markov Model (HMM). Bhatia et al. [START_REF] Bhatia | Real-time identification of operating room state from video[END_REF] analyses overall OR view videos. After identifying 4 states of a common surgery, relevant image features were extracted and HMMs were trained to detect OR occupancy. Padoy et al. [START_REF] Padoy | On-line recognition of surgical activity for monitoring in the operating room[END_REF] also used external OR videos to extract low-level image features through 3D motion flows combined with hierarchical HMMs to recognize on-line surgical phases. In robotic using the Da Vinci, Voros and Hager [START_REF] Voros | Towards "real-time" tool-tissue interaction detection in robotically assisted laparoscopy[END_REF] used kinematic and visual features to classify tool/tissue interactions. Similarly, Reiley and Hager [START_REF] Reiley | Decomposition of robotic surgical tasks: an analysis of subtasks and their correlation to skill[END_REF] focused on the detection of subtasks for surgical skill assessment.

In a previous work [START_REF] Lalys | Surgical phases detection from microscope videos by combining SVM and HMM[END_REF], using neurosurgical videos, we proposed to extract surgical phases by combining a feature extraction process with HMM. In this paper, we extend this approach by proposing an application-dependent framework that can be adaptable to any type of surgeries. The idea is first to extract visual cues that can be helpful for discriminating high-level tasks. The visual cues are detected by specific image-based classifiers, obtaining a semantic signature for each frame. Then, these time series are aligned with a reference surgery using DTW algorithm to recognize surgical phases. Compare to traditional video understanding algorithms, this framework extracts application-dependant visual cues that are generic. The combination of image-based analysis and time series classification allows getting high recognition rates. We evaluated our framework with a dataset of cataract surgeries through cross-validation studies, and compared results of the DTW approach with the HMM classification.

Materials and Methods

Application-Dependant visual cues

Four classifiers based on different image processing tools were implemented (Fig. 1.). Each of these classifiers was related to one kind of possible visual cue. Visual cues recognizable through color were detected using a color histogram approach. For each shape-oriented visual cue such as the recognition of a specific object, a Haar classifier was trained. For texture-oriented visual cues, we used a bag-of-word approach using Scale Invariant Feature Transform (SIFT) descriptors, and finally for other visual cues that don't match these descriptions, we used an image classification approach including a feature extraction, selection and a classification with SVM.

Fig. 1. Framework of the recognition system

Color-oriented visual cues: The color is one of the primary features used to represent and compare visual content. Especially, color histograms have a long history as a method for image description, and can also be used for identifying color shade through images. Here we used the principle of histogram classification to extract color-oriented visual cues, by creating a training image database composed of positive and negative images. Two complementary color spaces were extracted: RGB and HSV space. For quantifying similarities between histograms, we used the correlation.

Shape-oriented visual cues:

We used here a Viola-Jones object detection framework [START_REF] Viola | Rapid real-time face detection[END_REF], mainly used to detect specific object within images. The basic idea is to create a classifier based on features selected by AdaBoost. Weak learners of the algorithm are based on the Haar-like rectangular features, comparing the sum of intensities in adjacent regions inside a detection window. Then, strong learners are arranged into a classifier cascade tree in complexity order. The cascade classifier is therefore composed of stages, each one containing a strong learner. During the detection phase, a window looks through the image with different scales and positions. The idea is to determine at each stage if a given sub-window may be the searched object or not. The false positive rate and the detection rate are thus the product of each rate at each stage.

Texture-oriented visual cues: For whole-image categorization tasks, bag-of-visualwords (BVW) representations, which represent an image as an orderless collection of local features, have demonstrated impressive performances. The idea of BVW is to treat images as loose collections of independent patches, sampling a representative set of patches from the image, evaluating a descriptor vector for each patch independently, and using the resulting distribution of samples in descriptor space as a characterization of the image. A bag of keypoints is then expressed as a histogram recounting the number of occurrences of each pattern in a given image. For the texture analysis, we used the SIFT [START_REF] Lowe | Object recognition from scale-invariant features[END_REF] descriptors.

Other visual cues:

We already presented this approach in a previous paper [START_REF] Lalys | Automatic phases recognition in pituitary surgeries by microscope images classification[END_REF]. Each frame was represented by a signature composed of low-level spatial features (RGB space, co-occurrence matrix with Haralick descriptors [START_REF] Haralick | Textural features for image classification[END_REF], spatial moments [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF], and Discrete Cosine Transform (DCT) [START_REF] Ahmed | Discrete Cosine Transform[END_REF] coefficients). This signature was then reduced by feature selection. For that purpose, we fused a filter and a wrapper approach by using the union of both selection results. The RFE-SVM [START_REF] Guyon | Gene selection for cancer classification using support vector machine[END_REF] and the mutual information (MI) [START_REF] Hamming | Coding and Information Theory[END_REF] were chosen for the wrapper and the filter method respectively, keeping the 40 first features. Finally, a SVM was applied to extract the binary cue.

Time series classification

A binary semantic signature was extracted from each frame, composed of the recognized visual cues. We used the DTW algorithm [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken work recognition[END_REF] to classify these time series in a supervised way. The objective of DTW is to compare two sequences by computing an optimal match. These sequences may be time-series composed of feature sequences sampled at equidistant points in time. A local cost measure is needed to compare features. We used here the Hamming distance. To compare each surgery, we created an average surgery with the method described in [START_REF] Ahmadi | Recovery of surgical workflow without explicit models[END_REF]. Every query surgery was first processed to extract visual cues, and then the time series were compared to the average one. Once warped, the phases of the average surgery are transposed to the query one. We also used the Itakura parallelogram global constraint that limits the warping path to be within a parallelogram.

Data-set

Our framework was evaluated on cataract surgeries. 20 cataract surgeries from the Hospital of Munich were included to the study (mean surgical time: 15 min). Videos were recorded using the OPMI Lumera surgical microscope (Carl Zeiss) with a resolution of 720 x 576 at 25 fps. We downsampled the videos to 1 fps, and spatially downsampled by a factor 8 with a 5-by-5 Gaussian kernel. Eight surgical phases were defined (Fig. 2). Additionally, five binary visual cues were chosen: the pupil color range (orange or black), the presence of antiseptic, of the knife, of the IOL instrument, and the global aspect of the cataract. Combinations of these five binary cues are informative enough to discriminate all 8 phases. The pupil color range and the presence of the antiseptic were extracted using color histograms. The knife was recognized using a Haar classifier. The IOL instrument was not identifiable through only color or shape analysis, that's why we chose the fourth approach using global spatial feature extraction and SVM classification. Finally, the global aspect of the cataract was recognized using the BVW approach. For this detection as well as for the pupil color range classification, a step of pupil segmentation was first applied, using preprocessing steps composed of dilation/erosion operations and a Hough transform.

Cross-validation

The initial work of phase and visual cue labeling was performed for each video. From each video, we randomly extracted 100 frames, getting an image database composed of 2000 labeled images. We then evaluated both aspects of our framework. First, every visual cue detection was assessed trough 10-fold cross-validation studies, by dividing the image database into 10 random subsets. Then, we evaluated the global framework with the same procedure. At each stage, 18 videos (and their corresponding frames from the image database) were used for training and recognitions were made on the 2 others. For this validation, we computed the Frequency Recognition Rate (FRR). We also validated the added-value of the DTW algorithm, by comparing with an HMM approach, described in previous studies [START_REF] Lalys | Surgical phases detection from microscope videos by combining SVM and HMM[END_REF]. Results of the cross-validation studies (Tab. 1.) showed that very good accuracies were obtained for visual cues with quite low standard deviations. The best recognition was obtained for the detection of the antiseptic, with a recognition rate of 98.5%, whereas the lower rate was obtained for the IOL instrument recognition (94.8%). An example of a DTW computation is shown on Fig. 3. Small errors occur in the phase transitions, but the global FRR stay high (~93%). Tab. 2. shows the global accuracy of the framework, using DTW or HMM approach. The global validation study with DTW showed a mean FRR of 94.8%, with a min of 90.5% and a max of 98.6%. 4 Discussion

Visual cues and DTW

Combining with state-of-the-art techniques of visual cues recognition, DTW showed very good performance and allows further promising works on high-level tasks recognition in surgery. The comportment in color, texture and shape of the visual cues are intuitively known, allowing the classifiers to be effective. This approach turns out to be as generic as possible, and adaptable to any type of surgery. However, one limitation of the DTW algorithm is that it can't be used on-line, because the entire surgery is needed in order to find the optimal path. However, first results showed that the DTW algorithm was quite better for classifying times series data than the HMM.

Microscope video data

The real added value of the project lies in the use of microscope videos. This device is not only already installed in the OR, but it has also not to be monitored by the staff.

Compared to other additional sensors, this allows the recognition to be fully automatic and independent. Moreover, microscope video data are reproducible within a same surgical environment and image features are invariant to task distortion [START_REF] Bouarfa | Discovery of high-level tasks in the operating room[END_REF]. Due to facilities differences between surgical departments, the system could not be flexible. The solution would be to train dedicated databases for each department, which would be adapted to the corresponding surgical environment and microscope scene layout.

Clinical applications

The automatic recognition of surgical phases might be helpful for various applications. Purposes are generally to bring an added value to the surgery or to the OR management. This work could be integrated in an architecture that would take in real-time the microscope videos as input and transform it into information helping the decision making process, and driving context-sensitive user interfaces. Off-line, surgical videos would be very useful for learning and teaching purposes given their automatic indexation. Moreover, we could imagine the creation of pre-filled post operative reports that will have to be completed by surgeons. The recognition of lower level information, such as gestures, is difficult with microscope videos only. In future works, lower-level information such as surgeon's gestures will have to be detected to create multi-layer architectures.

Conclusion

We proposed in this paper a framework that automatically recognizes surgical phases from microscope videos. The first step of the framework is the definition of several visual cues for extracting semantic information and therefore characterizing every frame. Then, time series models allow an efficient representation of the problem by modeling time varying data. This association permits to combine the advantages of all methods for better modeling. We tested the framework on cataract surgeries, where 8 phases and 5 visual cues were defined by an expert, getting global accuracies of 95%. This recognition process is a first step in the construction of context-aware surgical systems, opening perspectives for a new generation of CAS systems.

Fig. 2 .

 2 Fig. 2. Example of typical digital microscope images for the eight phases: 1-preparation, 2betadine injection, 3-corneal incision, 4-capsulorhexis, 5-phacoemulsification, 6-cortical aspiration of the remanescent lens, 7-implantation of artificial IOL, 8-adjustment of the IOL.

Fig. 3 .

 3 Fig. 3. Distance map of two surgeries and dedicated warping path using the Itakura constraint (up), along with the transposition of the surgical phases (down).

Table 1 .

 1 Mean accuracy and standard deviation (Std) for the recognition of the 5 binary visual cues, computed on the entire video dataset.

	3 Results
		Pupil color	Presence	Presence	Presence IOL	Cataract aspect
		range	antiseptic	Knife	instrument
	Accuracy (%)	96,5	98,5	96,7	94,8	95,2
	Std (%)	3,7	0,9	3,4	1,1	1,8

Table 2 .

 2 Mean, minimum and maximum FRR of the HMM and DTW studies.

		FRR (Std)	Minimum (%)	Maximum (%)
	HMM (%)	92,2 (6,1)	84,5	99,8
	DTW (%)	94,8 (3,7)	90,5	98,6

Acknowledgements. The authors would like to acknowledge the financial support of Carl Zeiss Meditec.


Germain Forestier

Florent Lalys

Laurent Riffaud

Brivael Trelhu

Pierre Jannin

Assessment of surgical skills using Surgical Processes and Dynamic Time Warping

HAL is

Introduction

In the domain of medical engineering, the analysis and the modeling of surgical procedures has recently emerged. Surgical procedures can be decomposed into four main levels of granularity [START_REF] Mackenzie | Hierarchical decomposition of laparoscopic surgery: a human factors approach to investigating the operating room environment[END_REF]: the phases, steps, tasks and motions. A surgical intervention can then be described using a pre-defined level of granularity to create a Surgical Process (SP). Then, Surgical Process Models (SPMs), which are progression models of surgical interventions, are used to study, evaluate and analyze surgical activities in the Operating Room (OR). In this field, a recent and important challenge is the design of new methods to compare and group similar SPs in order to identify relevant patterns, that can be correlated with other pre-operative data in order to highlight specific information on the surgery. The main issue of such analysis is the definition of similarity metrics between SPs that reveal objective and quantitative differences at every granularity level of the surgical procedure. Indeed, SPs from the same intervention type can have a high variability, which can be caused by many parameters such as the different operating techniques, the intrinsic difficulty of the surgical procedure or the surgeon's expertise. Consequently, similarity measures have to be designed to accurately assess the similarity between SPs according to their content (i.e. the different activities performed by the surgeon) and their sequencing (i.e. the order in which the activities are performed).

In a recent work, Riffaud et al. [START_REF] Riffaud | Recording of surgical processes: a study comparing senior and junior neurosurgeons during lumbar disc herniation surgery[END_REF] computed similarity metrics and performed statistical analysis for comparing groups of senior and junior surgeons (i.e. experimented and not experimented surgeons). The metrics used were (i) General parameters of the procedure: the operating time for the whole procedure and for each step, (ii) General parameters of the surgeon's activity: the number of activities performed with either the right or the left hand and the number of changes in microscope position, (iii) Specific parameters of the surgeon's activity: all the gestures performed by the surgeon, the instruments used and the anatomical structure treated. Some of these metrics were found statistically significantly different when comparing the junior and the senior groups. Following this work, we introduced in this paper a new approach by exploring the use of the Dynamic Time Warping (DTW) [START_REF] Hiroaki | Dynamic programming algorithm optimization for spoken word recognition[END_REF] algorithm to evaluate the similarity between SPs. DTW allows to measure the similarity between two sequences which may vary in time or speed. As SPs have been acquired in different environments, they can easily vary in time which makes DTW particularly suitable for comparing SPs. Using DTW to compare SPs allows us to focus on the sequencing of the activities composing the SPs. Indeed, DTW allows to reduce the importance of time variations in the comparison and focuses on the number of activities and their organization in the timeline of the surgery.

Using this similarity metric, we addressed the problem of the automatic clustering of SPs. We focused our evaluation on the correlation between the clustering of SPs and the dedicated level of expertise of surgeons. We present experiments using 24 SPs of lumbar disc herniation surgery whose half were performed by senior surgeons, and half by junior surgeons. Evaluation studies shown that our approach was able to automatically identify these two clusters of surgeons based on the comparison of the SPs using DTW. Furthermore, our approach was also able to go further by identifying sub-clusters of surgeons.

Related work

Following the current technological advent within the Operating Room (OR), an important need emerged for tools allowing to assess and evaluate the impact of these new technologies. Within this field, the development of new methods for objective surgical skill evaluation is an important issue. Surgical skills can be assessed based on five factors: knowledge, decision making, technical skills, communication skills and leadership skills. From these five factors, many researches have been conducted for developing objective methods for technical skill evaluation. A comprehensive review can be found in [START_REF] Reiley | Review of methods for objective surgical skill evaluation[END_REF].

One approach for surgical evaluation [START_REF] Bridgewater | Surgeon specific mortality in adult cardiac surgery: comparison between crude and risk stratified data[END_REF] is to consider the patient's outcome for assessing surgeons. Unfortunately, this metric is highly variable and dependent of the patient's specific characteristics. Additionally, patient outcome is usually a multiple factors criterion requiring long term follow-up. Even if outcomebased metrics are straightforward to use, they are not objective enough and they do not study in detail the differences within the surgical procedure. Another approach uses human grading techniques. The underlying idea is to ask to a senior surgeon to provide an evaluation rating scale using dedicated check-lists during the observation of an intervention. Several scores have been proposed: Objective Structured Assessment of Technical Skills (OSATS) [START_REF] Reznick | Testing technical skill via an innovative "bench station" examination[END_REF], Objective Structured Clinical Examinations (OSCE) [START_REF] Moorthy | Objective assessment of technical skills in surgery[END_REF], or Global Rating Scale (GRS) [START_REF] Doyle | A universal global rating scale for the evaluation of technical skills in the operating room[END_REF] and have shown good results. However, this method turned out to be very time-consuming and also very observer-dependant. Motion has then been investigated to analyze dexterity, by tracking the surgeon's hand [START_REF] Datta | The use of electromagnetic motion tracking analysis to objectively measure open surgical skill in the laboratory-based model[END_REF], arm [START_REF] Francis | The performance of master surgeons on the Advanced Dundee Endoscopic Psychomotor Tester: contrast validity study[END_REF], or instruments [START_REF] Rosen | Markov modeling of minimally invasive surgery based on tool/tissue interaction and force/torque signatures for evaluating surgical skills[END_REF], using various and complementary tracking systems [START_REF] Chmarra | Systems for tracking minimally invasive surgical instruments[END_REF] or in the context of robotic assistance [START_REF] Guthart | The IntuitiveTM telesurgery system: overview and application[END_REF]. These works have focused on motion patterns analysis, using for instance time series analysis of the different motions. The main drawback of such approaches is its low level of granularity which do not give insight into the surgical scenario followed.

The on-line and off-line recordings of surgeries have been of growing interest for analysing procedures and assessing surgeons. Recordings can be performed using sensor devices or directly by an observer. This data extraction process can be supported by fixed protocol created by experts. In this case, the first step consist in building up its own vocabulary. A new terminology is employed and permits a knowledge representation that is proper to the own surgeon's experience and to the specific surgical environment. In this context, SP recordings can be driven by specific Surgical Process Models (SPMs), including complex dedicated ontologies.

The need of model-based systems for assisting and monitoring Computer-Assisted Surgical (CAS) has been discussed by Jannin et al. [START_REF] Jannin | Model of surgical procedures for multimodal image-guided neurosurgery[END_REF]. A model was proposed in the context of neurosurgical intervention, based on an UML class diagram and a textual description for decomposing the procedure. [START_REF] Neumuth | Acquisition of process descriptions from surgical interventions[END_REF] focused on the description of concepts and technologies for the acquisition of surgical workflows by monitoring surgical interventions. They introduced an universal and adaptable recording scheme describing the subdivision of the surgical interventions into manual work steps detailed records. A new software was implemented (i.e. a surgical workflow editor: the ICCAS editor system) that permitted to record process during the intervention. They also introduced methods for computing generic SPMs that could serve for the generation and the comparison of surgical procedures [START_REF] Neumuth | Analysis of surgical intervention populations using generic surgical process models[END_REF][START_REF] Neumuth | Validation of knowledge acquisition for surgical process models[END_REF].

Finally, Padoy et al. [START_REF] Padoy | Statistical modeling and recognition of surgical workflow[END_REF] proposed a system for the recognition of surgical workflow. They used Hidden Markov Models and Dynamic Time Warping to analyze and process a set of SPs and identify the different phases of the surgeries.

Methods

Surgical Process (SP) as sequence of activities

A Surgical Process (SP) can be seen in the real world as a sequence of flow objects [START_REF] White | Introduction to BPMN[END_REF]. According to the Workflow Management Coalition (WFMC) terminology [START_REF] Zur Muehlen | Organizational management in workflow applications-issues and perspectives[END_REF], we name flow objects representing surgical work steps as activities ac i and a set of activities as AC with ac i ∈ AC (ac i being the i th activity). Each activity in a SP corresponds to a surgical work step which contains several kinds of information. Thus, an activity ac i is defined as a triple :

ac i =< a; s; i > a ∈ A, s ∈ S, i ∈ I mi (1)
with A the set of possible actions (e.g. {cut, remove, . . . }), S the set of possible anatomical structures (e.g. {skin, dura matter, . . . }), I the set of possible instruments (e.g. {scalpel, scissors, . . . }) and m i the number of instruments used in the activity ac i . A full example of one activity could be : <cut, skin, scalpel>. Thus, the domain of definition of an activity is given by: A × S × I mi . These sets of possible values are generally specific to the type of studied surgery. An ontology can be used to describe the vocabulary for a specific type of surgery [START_REF] Neumuth | Analysis of surgical intervention populations using generic surgical process models[END_REF].

Along with the information of the action (a), the anatomical structure (s) and the used instrument(s) (i), each activity has a starting point (start(ac i )) and a stopping point (stop(ac i )) which respectively correspond to the time point when the activity started and the time point when the activity stopped (start(.) → R, stop(.) → R) on the timeline of the surgeries. Note that start(ac i ) < stop(ac i ), inducing a partial order among the activities. The last information carried on the activity is the hand used to perform the activity (hand(ac i )) which can either be right or left.

A Surgical Process can be seen as a sequence of activities (sp k ) performed during surgery. Each activity of this sequence belongs to the set of all the different activities performed during the surgery (AC k ) :

sp k =< ac (k) 1 , ac (k) 2 , . . . , ac (k) n k > | ac (k) i ∈ AC k (2)

Comparing SPs using Dynamic Time Warping (DTW)

When dealing with SPs, an important challenge is the design of metrics to evaluate the similarity of SPs. Indeed, defining a similarity measure is often the first step to identify patterns among a set of objects. As a SP can be seen as sequence of activities, we propose to use the Dynamic Time Warping (DTW) algorithm [START_REF] Hiroaki | Dynamic programming algorithm optimization for spoken word recognition[END_REF] to compare them. DTW is based on the Levenshtein distance (or edit distance), and was originatively used for applications in speech recognition. It finds the optimal alignment between two sequences, and captures flexible similarities by aligning the two sequences. In order to use DTW to compare two sequences, a distance has to be defined to evaluate the similarity between the different elements composing the sequence. In our case, it means defining a distance between two activities. Thus, we defined this distance as a binary function which returns 0 if all the three components (Eq. 1) of the two activities are equals, 1 else :

d(ac i , ac j ) =          0 if ac i (a) *
= ac j (a) and ac i (s) * = ac j (s) and ac i (i) * = ac j (i) 1 else [START_REF] Datta | The use of electromagnetic motion tracking analysis to objectively measure open surgical skill in the laboratory-based model[END_REF] with * = a boolean operator performing the comparison between the action, the anatomical structure or used the instrument(s) (e.g. d( <cut, skin, scalpel>,<cut, skin, scalpel>)=0).

To compare two SPs using DTW, the sequence of activities is first stretched by considering the starting and stopping of each activity. This step is needed to have the two SPs on the same timeline and to be able to compare the activities performed in each SP at given time point t in the timeline. The activity performed at the time point t will be ac i (t) iff t ∈ [start(ac i ); stop(ac i )]. Note that it is not necessary that the two SPs last the same amount of time, the only assumption we make is that for both SPs, the first activity started at the same moment (t = 0).

Considering two SPs, sp k =< ac

(k) 1 , ac (k) 2 , . . . , ac (k)
n k > and sp l =< ac

(l) 1 , ac (l) 2 , . . . , ac (l)
n l > the cost of the optimal alignment can be recursively computed with :

d(sp k (t), sp l (t)) = (4)
d(ac

(k) i (t), ac (l)
j (t)) + min      d(sp k (t -1), sp l (t -1)) d(sp k (t), sp l (t -1)) d(sp k (t -1), sp l (t))
where sp k (t) is the subsequence < ac

(k) 1 , . . . , ac (k)
i (t) >. Direct implementation of this recursive definition has an exponential cost. Fortunately, by decomposing it in subproblems, the complexity can be narrowed down to N k × N l , N being the number of time points in a SP, which is equivalent to the stopping value of the last activity of the SP.

DTW has already been successfully used as similarity measure for clustering [START_REF] Jain | Data clustering: 50 years beyond k-means[END_REF], for example in [START_REF] Petitjean | A global averaging method for dynamic time warping, with applications to clustering[END_REF] where the authors used DTW to perform KMeans clustering on sequential data to identify patterns in remote sensing images. Thus, we propose to use the similarity measure defined using DTW to automatically identify clusters of similar surgeries. We used an ascendent hierarchical clustering approach with the average-link method [START_REF] Manning | MITCogNet: Foundations of statistical natural language processing[END_REF], which consists in evaluating the similarity of two clusters according to the average distance between all the couple of objects in the two clusters.

Data presentation

Twenty-four procedures (10 men, 14 women, median age of 52 years) of lumbar disc herniation surgery were recorded in the Neurosurgery Department of the Leipzig University Hospital, Germany. The procedure can be divided into three major steps: the approach of the herniated disc via a posterior intermyolamar route, the discectomy including the dissection and removal of the disc, and the closure step. Additionally, a step of hemostasis might be necessary before the closure. Five senior surgeons and five junior ones have participated to the study. Senior surgeons had already performed more than 100 removals of lumbar disc herniation, whereas junior ones had performed more than 2 years of their residency program. Among the 24 recorded procedures, 12 were performed by one senior surgeon with the aid of one junior surgeon, and in the 12 remaining cases, surgery was performed by one junior surgeon with the aid of one senior surgeon. During all junior recordings, the only step that was performed by junior surgeons without the help of senior ones was the closure step. Thus, in this paper, we focused on the analysis of this last step for a better discrimination of junior and senior performance.

The data were acquired using the Surgical Workflow Editor [START_REF] Neumuth | Structured recording of intraoperative surgical workflows[END_REF]. SPs were recorded on-line by an observer, a senior neurosurgeon, with the help of a touchscreen laptop to facilitate the recording task.

Results

The figure 1 presents the dendrogram of the AHC for the closure step, which is the only step performed by junior and senior surgeons alone. Along with the clustering, the right-hand activities of each surgery are shown below as indexplots. The idea of index-plot is to display the sequence by representing an activity as a rectangle of a specific color for each activity, and a width proportional to its duration Three clusters visually emerged from the analysis. When cutting the dendrogram for creating 2 clusters, 12 surgeries in each cluster can be extracted. The first cluster (left part, in green and blue) contains 10 surgeries performed by senior and 2 by juniors. For the second cluster (right part, in red), 10 surgeries operated by juniors and 2 by seniors are present. Additionally, within the first cluster, a sub-classification can be found (between red and blue parts), where each sub-cluster contains five surgeries performed by seniors and 1 by junior. By keeping the two main clusters, an accuracy of 83.33% is found, considering that 20 surgeries over 24 are classified into the right cluster.

Discussion

Classification of surgeon's experience

According to figure 1, two main clusters are clearly identifiable. It turns out that these two clusters are strongly correlated with surgeon's experience, which is not surprising. Indeed, an actual tendency shows that senior surgeons perform less gestures than juniors. Particularly during a mechanical step (the closure step), experienced surgeons are more economical with their movements than the inexperienced ones, which explains that the DTW similarity can be able to capture the differences between both groups. Moreover, the two junior surgeries classified as being senior ones were actually both operated by the same junior surgeon. During the preliminary phase of experience's classification, our reference neurosurgeon wondered whether this surgeon had to be considered as being junior or senior regarding his intermediate experience (i.e. seventh year of resident training), which could explain this classification error. On the contrary, the two senior surgeries classified as being junior ones were not particularly complicated surgeries, as the total time of both surgeries were both quite low. This classification error could be explained by a lower gesture economy of corresponding senior surgeons, or even a lower manual dexterity.

According to figure 1, two sub-clusters of senior surgeons can be extracted. Similarly to the correlation with surgeon's experiences, explications with other pre-operative data were explored, without success. However, both sub-clusters contain surgeries performed by same senior surgeons. It reveals that seniors can have different operating techniques and preferably sequence of activities that differ from one senior to the other and that can explain this distinct separation.

A new metric for surgery comparison

The DTW approach for surgeries comparison allows to focus only on the sequentiality of surgeries by minimizing the time differences. Indeed, the DTW algorithm has been first used to synchronize two time series, for instance in the context of speech recognition. Using this method for synchronizing surgeries permit to take into account the difference of activities sequences, without time constraint. Assuming that for skill-evaluation the time is not a major parameter, the number of activities associated with their sequentiality is more relevant and surgery dissimilarities can be objectively quantified using the DTW distance. This metric is therefore an interesting and innovative way for comparing surgeries, and turns out to be a complementary approach of standard time/number of occurrences comparison approaches [START_REF] Riffaud | Recording of surgical processes: a study comparing senior and junior neurosurgeons during lumbar disc herniation surgery[END_REF].

Specific applications: training and assessment

Training and assessment of surgeons are now considered as crucial issues for patient safety. Training of junior surgeons is a very time-consuming, interactive and subjective task. As all juniors are currently learning with the teaching help of seniors, there has been a new demand for simulation devices. Moreover, some surgeons are clearly superior in performing tasks than other, resulting in a growing pressure to demonstrate their competences. These two challenges have motivated the creation of automatic systems for objective assessment of surgical skills. With automatic techniques recently proposed using sensor devices, systems are able to precisely recognize activities through different level of granularities, from the simple gesture to the global phases of the surgery, which is a powerful tool to automate surgical assessment and surgical training without being biased by humans. For assessment, surgical activities can be scored for precision, dexterity or global performance. For training, it would allow surgeons to benefit from constructive feedback and to learn from their mistakes. Similar methods can also be employed for other type of surgeries, or even other members of the surgical team.

Conclusion

An important challenge is the creation of new metrics for the comparison and the evaluation of SPs. In this paper, we proposed a new surgery metric based on the DTW algorithm that permit to focus the analysis on the different types of activity performed during the surgery and their sequencing, and not on the time differences. Results on the classification of the level of expertise of surgeons were shown.

One possibility for improving the analysis would be to introduce semantic in the surgeries similarity metrics. In this work, at each time step, a binary comparison of two surgical activities is performed. The idea would be to introduce semantic matrix in order to link each activity using different distance values of a predefined similarity scale for more complex analysis of SPs.

Fig. 1 .

 1 Fig. 1. Dendrogram of the clustering of the 24 SPs


René Lozi
email: lozi@unice.fr

J A Dieudonné

Estelle Cherrier
email: estelle.cherrier@ensicaen.fr

Noise-resisting ciphering based on a chaotic multi-stream pseudo-random number generator

. This Cms-PRNG co-generates an arbitrarily large number of uncorrelated chaotic sequences. These cogenerated sequences are actually used in several steps of the ciphering process. Noisy transmission conditions are considered, with realistic assumptions. The efficiency of the proposed method for ciphering and deciphering is illustrated through numerical simulations based on a Cms-PRNG involving ten coupled chaotic sequences.

I. INTRODUCTION

A. Chaos and cryptography: a brief state of the art Besides conventional cryptographic methods, relying on number theory, chaos-based cryptography has aroused a great attention for a few years. Indeed, chaotic systems seem to exhibit promising properties, among which one can mention: long-term unpredictability, noise-like behavior, spread spectrum. . . Two main classes can be distinguished in chaos-based cryptographic methods: those based on continuous-time chaos and those based on discrete-time chaos. In this paper, we will focus on cryptography with discretetime chaos, owing to a less computational complexity and no need for synchronization. The first references dealing with chaos cryptography are [START_REF] Matthews | On the derivation of a chaotic encryption algorithm[END_REF], which proposes a stream cipher based on a one-dimensional chaotic map and [START_REF] Habutsu | A secret key cryptosystem by iterating a chaotic map[END_REF], in which the secret key is chosen as some parameter of the tent map.

Generally the principle of discrete chaos based cryptography is directly inspired from that of classical cryptography, in the sense that either pseudo-random numbers are generated from a discrete chaotic system to perform stream ciphering or the cipher message follows the chaotic orbit whose initial condition is deduced from the plain message in block ciphering. Then chaos based cryptographic schemes are used in hashing techniques, authentication process, or key-exchange protocols. . . among other applications.

Most of the methods aimed at designing chaotic cryptosystems resort to pseudo-random number generators (which will be denoted chaotic PRNG in the sequel). Beside standard PRNG (see [9] and the references therein for a thorough study), chaotic systems can be used to generate sequences of pseudorandom numbers. Some works study the random properties exhibited by these chaotic PRNG, while other references discuss about their involvement in cryptography. We mention in this section a rapid survey about chaotic PRNG, among the numerous papers available in the literature. In the companion references [START_REF] Stojanovski | Chaos-Based Random Number Generators-Part I: Analysis[END_REF], [START_REF] Stojanovski | Chaos-Based Random Number Generators-Part II: Practical Realization[END_REF], an analysis is performed of the application of a chaotic piecewise linear one dimensional map as random number generator. The parameter values for which the RNG behaves as a Markov information source are analytically and practically studied. The reference [START_REF] Li | A multiple peudorandom-bit generator based on spatiotemporal chaotic map[END_REF] studies the cryptographic properties of a new pseudo-random bit generator based on the coupled map lattice: spatiotemporal chaos is dealt with, stemming from partial differential equation or coupled ordinary differential equations. It means that chaotic properties are exploited both in time and in space. A large number of chaotic oscillators are coupled to produce chaotic orbits whose period is too long to be reached in realistic conditions. In the paper [START_REF] Assad | Design and analyses of efficient chaotic generators for crypto-systems[END_REF] a perturbing orbit technique is used to avoid dynamical degradation due to finite state representation. It shows that this process also increases the cycle length. The authors proposes an analysis of the randomness based on system and signal processing tools. The work [START_REF] Kanso | Logistic chaotic maps for binary numbers generations[END_REF] proposes a chaotic PRNG based on a simple logistic map and on two coupled logistic maps. This CPRNG is used to encrypt binary plaintexts through bitwise XOR operation, as in standard stream ciphers. The reference [START_REF] Behnia | A novel dynamic model of pseudo random number generator[END_REF] proposes a review of RNG features and chaotic systems theory. It studies a family of rational order chaotic maps, obtained as the ratio between polynomials. Then some statistical tests are performed through an invariant measure to evaluate the performances of the corresponding chaotic PRNG. In the reference [START_REF] González | Statistical complexity measure of pseudorandom bit generator[END_REF], a particular statistical complexity measure (introduced by [START_REF] Martin | Statistical complexity and disequilibrium[END_REF]) is used to quantify the randomness of any PRNG. This measure exhibits the following interesting property: it is null for totally random process. The proposed method is evaluated on standard well-known PRNG as well as PRNG based on Lorenz chaotic system. This measure is improved in [START_REF] Larrondo | Random number generators and causality[END_REF]. The same authors present in [START_REF] Larrondo | Intensive statistical complexity measure of pseudorandom number generators[END_REF] a quantifier to predict whether a given RNG will pass the Marsaglia DIEHARD test suite [START_REF] Marsaglia | [END_REF]. The reference [START_REF] De Micco | Randomizing nonlinear maps via symbolic dynamics[END_REF] proposes a method to classify randomizing techniques, through a representation based on the statistical properties (see [START_REF] Martin | Statistical complexity and disequilibrium[END_REF], [START_REF] Larrondo | Intensive statistical complexity measure of pseudorandom number generators[END_REF]) of chaotic systems. They define randomizing techniques as suitable manipulations of the generated time series in order to improve their statistical properties. They show that PRNG based on very simple chaotic systems may be greatly improved by resorting to symbolic dynamics. Two techniques are tested, called discretization and skipping. A novel and efficient technique is presented in the papers [START_REF] Lozi | New enhanced chaotic number generators[END_REF], [START_REF] Lozi | Chaotic pseudo-random number generators via ultra weak coupling of chaotic maps and double threshold sampling sequences[END_REF] to randomize chaotic data. This technique relies on chaotic sampling and mixing, through extremely weak coupling of a piecewise linear chaotic map. The proposed method has been thoroughly studied and characterized and the generated numbers possess good random properties. A new generator on the torus has been proposed in [START_REF] Lozi | Random properties of ring-coupled tent maps on the torus[END_REF]: this generator will be used in the present paper to co-generate uncorrelated pseudo-random sequences to design an efficient and noise resisting chaotic cryptosystem by using the technique of chaotic sampling.

B. Problem formulation

This paper deals with the not so widely treated problem of data transmission in a noisy environment, based on a Cms-PRNG. The originality of this paper is twofold. First a novel ciphering method is proposed aimed at resisting to a noisy transmission channel. The main idea is to establish, between the transmitter and the receiver, a correspondence between the alphabet constituting the plain text and some intervals defining a partition of [-1, 1]. Some realistic assumption about the noise boundedness allows to restrict the bounds of the aforementioned intervals in order to precisely resist to the effects of the noise. An extra scrambling resorting to a co-generated chaotic sequence enhances the ciphering process. Then a new chaotic substitution method is developed: considering a chaotic carrier, belonging to the set of cogenerated and coupled pseudo-random chaotic sequences, the idea is to randomly/chaotically (in fact, this is determined by a second pseudo-random chaotic sequence) replace some elements of the carrier by a ciphered element (a letter here) of the message. At the receiver end, a copy of the Cms-PRNG, with the same parameters (hence we deal with a symmetrical ciphering method) allows to generate the necessary chaotic sequences and therefore to retrieve the initial message. The paper is organized as follows. In section II the chaotic pseudo-random numbers generator is detailed. Then section III is dedicated to the ciphering and the transmission processes. The decoding principle is summarized. In the last section some numerical illustrations show the efficiency of the proposed noise-resisting chaotic ciphering.

II. CMS-PRNG DESCRIPTION

The design of the proposed noise-resisting chaotic ciphering requires multiple random sequences. For this purpose consider the system with alternate coupled maps confined to the pdimensional torus [-1, 1] p recently introduced by Lozi and defined by:

                                                                               x 1 n+1 = 1 -2|x 1 n | +k 1     1 - p j=3 ε 1,j   x 2 n + p j=3 ε 1,j x j n   . . . = . . . x m n+1 = 1 -2|x m n | +k m     1 - p j=1,j =m,m+1 ε m,j   x m+1 n + p j=1,j =m,m+1 ε m,j x j n   . . . = . . . x p-1 n+1 = 1 -2|x p-1 n | +k p-1     1 - p-2 j=1 ε p-1,j   x p n + p-2 j=1 ε p-1,j x j n   x p n+1 = 1 -2|x p n | +k p     1 - p-1 j=2 ε p,j   x 1 n + p-1 j=2 ε p,j x j n   (1)
For more clarity, we also give the equation of the Cms-PRNG in dimension 4:

                                   x 1 n+1 = 1 -2|x 1 n | + k 1 (1 -ε 1,3 -ε 1,4 )x 2 n +ε 1,3 x 3 n + ε 1,4 x 4 n x 2 n+1 = 1 -2|x 2 n | + k 2 (1 -ε 2,4 -ε 2,1 )x 3 n +ε 2,4 x 4 n + ε 2,1 x 1 n x 3 n+1 = 1 -2|x 3 n | + k 3 (1 -ε 3,1 -ε 3,2 )x 4 n +ε 3,1 x 1 n + ε 3,2 x 2 n x 4 n+1 = 1 -2|x 4 n | + k 4 (1 -ε 4,2 -ε 4,3 )x 1 n +ε 4,2 x 2 n + ε 4,3 x 3 n (2)
with the following extra conditions, to stay on the torus, for all j ∈ {1, . . . , p}:

• if x j n+1 < -1 then add 2 • if x j n+1 > 1 then subtract 2
and k i = 1 or k i = -1 for i ∈ {1, . . . , p}.

It has been shown in reference [START_REF] Espinel | New alternate lozi function for random number generation[END_REF] that the chaotic map (1) co-generates p (p is arbitrarily chosen) uncorrelated sequences of pseudo-random numbers. This is a key property, that allows to use any generated chaotic sequence at any step of the proposed ciphering process: for security purpose, the transmitter and the receiver can agree to invert the role of the employed sequences. This property is very useful in the proposed method: the transmitter and the receiver can generate exactly the same pseudo-random sequences (from the same parameters and the same initial conditions, this point is discussed just below), but if an intruder intercept one of these sequences, he/she cannot deduce any information about the other coupled sequences. Therefore the proposed ciphering scheme is intrinsically linked with the inherent properties of the Cms-PRNG.

In practice,it is sufficient to choose p = 10 (see [START_REF] Espinel | New alternate lozi function for random number generation[END_REF]) to obtain good statistical properties. Among these p sequences, some will be used in the noise resisting transmission or ciphering process. Owing to their property of being non correlated, several sequences issued from the same chaotic generator can be entangled and transmitted at the same time.

Another interest for considering a coupled map such as [START_REF] Assad | Design and analyses of efficient chaotic generators for crypto-systems[END_REF] is that it provides many parameters, some of which will be used as secret keys. In the present work, we choose the parameters k i , i = 1, . . . , p as secret keys together with some of the ε i,j , i, j = 1, . . . , p. The only condition we impose is that the ε i,j must belong to the interval [10 -15 , 10 -5 ] to ensure good random properties for the generated sequences.

Besides, we choose to keep the initial conditions public and to eliminate the N 0 first iterations precisely to avoid the influence of the initial conditions. This means that the ciphered message will be transmitted inside a pseudo random carrier signal once its N 0 first iterations have been removed. In practice, some tests have been performed, showing that N 0 can be set to about 100 iterations. For security requirements, the value of N 0 can be increased at will.

Remark 1. To bear the fact that the initial conditions are public, the Cms-PRNG must exhibit a particularly strong sensitivity to its parameters, since some of the parameters only are kept secret. Some numerical tests illustrate this sensitivity, reported in the Appendix, at the end of the paper.

III. NOISE-RESISTING CIPHERING

In this section we detail the noise-resisting ciphered transmission principle, consisting of two steps: the ciphering process and the transmission process. Both resort to the coupled chaotic pseudo-random generated sequences.

A. Ciphering principle

We begin with some notations that will be used in the sequel.

The plain text is denoted (t k ) k=1,...,N : the letters t k , for i = 1, . . . , N belong to the alphabet {l 1 , . . . , l π } composed of π letters.

The ciphered text is a sequence of real numbers, denoted y k , k = 1, . . . , N and each y k belongs to the interval [-1, 1].

The transmitted signal (at the transmitter side) is denoted s n while the received signal is ŝn (at the receiver side).

In this paper we consider noisy transmission conditions, which means that ŝn = s n + α n , where α n > 0 denotes an unknown additive noise at time n. We make the following classical assumption: the additive noise is bounded by a known bound K, which means that

||s n -ŝn || = α n ≤ K, ∀n ≥ 0 (3)
We detail first how to transform each letter of the plain text t k into a real number y k ∈ [-1, 1], with an original noise-resisting method. In a second step, the sequence y k will be transformed to obtain a uniform distribution on the interval [-1, 1].

• Define a partition as follows:

[-1, 1] = m=1,π I m ( 4
)
with a m , b m the bounds of the interval each interval I m , i.e.:

I m = [a m , b m ].
In fact, owing to the presence of additive noise, not all real numbers inside I m can be selected, one must avoid an interval of length K at each side of the interval I m . Therefore some smaller intervals need to be defined.

• Define a sub-interval I m included in the corresponding interval I m such that:

I m = [a m , b m ] ⊂ I m (5)
and

[a m -K, b m + K] ⊂ I m ( 6
)
where we recall that K is the upper bound on the noise, see [START_REF] Espinel | New alternate lozi function for random number generation[END_REF].

Then the coding consists in randomly (i.e. with another pseudo-random sequence generated by (1): x p-1 n ) choosing for each letter t k of the plain text, a real number y k inside the interval I m (and not I m ) if t k = l m . Each interval I m corresponds to a letter l m , for m = 1, . . . , π. Remark that each letter has a frequency of apparition in the plain text, depending on the initial language. Therefore one must carefully choose the length of each interval I m in proportion to the corresponding frequency of the letter l m . An illustration is given by figure 1 for an alphabet with three letters: the letter A as a frequency of 10%, the letter B has a frequency of 30% and the letter C of 60%. Since one needs to leave some holes at the edges of the intervals I m to resist the additive noise, the transmitted signal cannot have a random-like repartition. So we propose to transform the ciphered data y k before transmitting it. For all steps n ∈ N such that an encrypted letter is transmitted, we propose to transmit not directly y n but:

ỹn =    y n + x p-2 n if y n + x p-2 n ∈ [-1, 1] y n + x p-2 n + 2 if y n + x p-2 n < -1 y n + x p-2 n -2 if y n + x p-2 n > 1 (7)
For simplicity of presentation, in the sequel, y n will denote ỹn , the ciphered message to transmit.

Then the obtained signal to transmit has the desired uniform repartition, as illustrated by figure 3

B. Transmission principle

We present now how to transmit the ciphered text using substitution method in a new pseudo-random chaotic The ciphered text y k , defined by [START_REF] Larrondo | Intensive statistical complexity measure of pseudorandom number generators[END_REF], is not directly transmitted, it is chaotically hidden in a chaotic carrier signal, as is explained below.

The ciphering makes use of two coupled chaotic sequences:

x 1
n is used as chaotic carrier, while x p n is used to select the substitution times.

s n = x 1 n if x p n < T y k(n) if x p n ≥ T ( 8
)
where T is a predefined threshold. For example, as the x p n are equally distributed on the interval [-1, 1], if one chooses T = 0.8, one ciphered letter will be transmitted in average each 10 element of the sequence x 1 n . If one chooses T = 0.98, one element over 100 is replaced by a letter.

We do not detail here the sequence k(n), it is easily understandable that k(n) increase of +1 each time s n = y k(n) in order to transmit each element of the ciphered sequence y k .

C. Decoding principle

At the receiver end, suppose that the same Cms-PRNG defined by ( 1) is available. The transmitter and the authorized receiver have fixed the same parameters, therefore the ciphering is a symmetrical one.

According to the substitution principle defined by [START_REF] Larrondo | Random number generators and causality[END_REF] and the hypothesis (3) on the additive noise, the received signal can be expressed as: Since the initial conditions of the chaotic pseudo-random number generator (1) are assumed to be public, the receiver exactly knows when x p n is smaller or larger than the threshold T , so the receiver is able to reconstruct the sequence (y k(n) + α n ), i.e. the sequence y q + β q where β q = α n for q = k(n).

ŝn = x 1 n + α n or y k(n) + α n (9)
Since β q ≤ K, there exists m ∈ {1, 2, . . . , π} such that ŝn ∈ I m . The receiver also exactly knows the value of x p-2 n and deduce from the rules (7) the value y q . Then the knowledge of the correspondence between the interval I m and the letter l m enables the receiver to retrieve the initial message.

IV. NUMERICAL ILLUSTRATIONS

Now we summarize the main steps of the proposed algorithm:

1) Choose the secret parameters k i = 1 or k i = -1 for i ∈ {1, . . . , p} and ε i,j ∈ [10 -15 , 10 -5 ], for i, j = 1, . . . , p 2) Choose N 0 ≥ 100 3) Define the initial conditions shared by the transmitter and the receiver 4) Iterate the Cms-PRNG (1) with the previous initial conditions, both at the transmitter and the receiver side 5) Apply the ciphering and transmission principle as detailed before The figure 4 shows the noisy signal at the receiver side (recall that the transmitted signal is given by figure 3). Notice that the figures 2 to 4 represent our simulations with 10 9 iterations. Remark 2. To generate the bounded additive noise in our simulations, we resort to the Box-Muller formula. The process consists of generating a white gaussian noise from two random sequences, uniformly distributed in ]0, 1]. These two random sequences are chosen between the remaining chaotic sequences (that have not been used in another step of the chaotic coding) and their absolute values are considered. The obtained noise is represented in figure 5. Notice that in real conditions, the noise naturally affects the transmission through the channel.

V. CONCLUSION

In this paper we have proposed a novel method of noiseresisting ciphering. The originality lies in the use of a chaotic pseudo-random number generator: several co-generated sequences can be used at different steps of the ciphering process, since they present the strong property of being uncorrelated. Each letter of the initial alphabet of the plain text is encoded as a subinterval of [-1, 1]. The bounds of each interval are defined in function of the known bound of the additive noise. A pseudo-random sequence is used to enhance the complexity of the ciphering. The transmission consists of a substitution technique inside a chaotic carrier, depending on another cogenerated sequence. The efficiency of the proposed scheme is illustrated on some numerical simulations. As further work, some studies should be performed of several sets of unknown parameters, since with the considered CMS-PRNG with 10 states, the number of possible parameters amounts to 90 (the ε i,j and the k i ). It is also possible to discuss about the opportunity to keep secret the correspondence between the alphabet and the intervals I m .

x

k 1 = 1, k 2 = -1, k 3 = 1, k 4 = 1

Fig. 1 .

 1 Fig. 1. Repartition of an alphabet of three letters

Fig. 2 .

 2 Fig. 2. Signal to be transmitted without transformation

Fig. 3 .

 3 Fig. 3. Signal to be transmitted after transformation

Fig. 4 .

 4 Fig. 4. Received noisy signal

Fig. 5 .

 5 Fig. 5. Distribution of the noise obtained by the Box-Muller formula

  k 1 = 1, k 2 = -1, k 3 = 1, k 4 = -1

		1		x 2	x 3	x 4
	i=2	0.802775649423882687	0.198337199944899456	0.893873727345795399	-0.347193769493635562
	i=3	0.407214033713460932	-0.290548081240143419	0.865058835244629565	-0.497163215517021417
	i=4	-0.104976034759294692	-0.446154478326659054	0.772719118773404601	0.412887220696436463
	i=5	0.343893580914444885	-0.665027721577955644	-0.1325510441039911	0.279201330018808036
				TABLE I
	CASE 1: Iteration x 1	x 2	x 3	x 4
	i=2	0.802775649423882687	0.198337199944899456	0.893873727345795399	0.0828063103885205709
	i=3	0.407214030273460315	-0.290548084551144059	-0.704941107276218393	-0.362836944247290738
	i=4	0.104976187115677827	-0.876155183551102557	-0.772719161018440959	-0.132888008099043914
	i=5	0.0861075414927185007	0.0204085218923464214 -0.678326329298663211	0.629247595921321956
				TABLE II
			CASE 2:

• Once this first step of the coding is achieved, one has to ensure that the ciphered text has a random-like distribution inside [-1, 1]. With the aforementioned coding alone, this property cannot be ensured, as it can be seen in figure2:

APPENDIX

In this part, we show the results of some tests we have performed to evaluate the required sensitivity of the trajectories of the Cms-PRNG (1) to the parameters k i and ε i,j . The same initial conditions are kept, and only one parameter is changed in each test, with respect to the other test. To alleviate the presentation, we give the results in the case n = 4. The sensitivity increases with the value of n.

Below are the initial conditions (i = 1), kept for all the tests:

• Sensitivity to the k i .

The following values are chosen for the ε i,j :

The results are presented in tables I and II. Considering these two tests, with the considered set of parameters, choosing the value N 0 ≥ 4 is sufficient.

• Sensitivity to the ε i,j .

The same methodology has been tested, with the following values for the k i :

and only one ε i,j is slightly varied (from 10 -15 ) from one test to another. For lack of place, the tables with the obtained results are not reported here. Again the value of N 0 can be fixed larger than 4.