Ines Khoufi
email: ines.khoufi@inria.fr

Mohamed Hadded
email: mohamed.hadded@telecom-sudparis.eu

Pascale Minet
email: pascale.minet@inria.fr

Anis Laouiti
email: anis.laouiti@telecom-sudparis.eu

Optimized Trajectories of Multi-Robot Deploying Wireless Sensor Nodes

A main reason to the growth of wireless sensor networks deployed worldwide is their easy and fast deployment. In this paper we consider deployments assisted by mobile robots where static sensor nodes are deployed by mobile robots in a given area. Each robot must make a tour to place its sensor nodes. All sensor nodes must be placed at their precomputed positions. The Multi-Robot Deploying wireless Sensor nodes problem, called the MRDS problem, consists in minimizing the longest tour duration (i.e. the total deployment duration), the number of robots used and the standard deviation between duration of robots tours. After a formal definition of the MRDS problem, we show how to use a multi-objective version of genetic algorithms, more precisely the NSGA-II algorithm, to solve this multi-objective optimization problem. The solutions belonging to the best Pareto front are given to the designer in charge of selecting the best trade-off taking into account various criteria. We then show how to extend this method to take obstacles into account, which is more representative of real situations.

I. INTRODUCTION AND MOTIVATION

Wireless Sensor Networks (WSNs) are widely used in monitoring applications due to their efficiency in detecting and reporting events. Area coverage and network connectivity are two major issues in the monitoring task. An area is considered covered if each event occurring in the area can be detected by at least one sensor node. Network connectivity is maintained if the detected event can be reported to the sink. Coverage and connectivity are related to sensor node positions in the area considered. For instance, if sensor nodes are densely deployed, multiple coverage (i.e. a zone is covered by several sensors) can be ensured and many paths from each node to the sink can be maintained. In a sparse deployment, coverage holes may exist and network connectivity may fail. Then, a deployment algorithm that determines the appropriate sensor node positions is needed to meet the coverage and connectivity requirements. We distinguish between two types of deployment: autonomous self-deployment and assisted deployment. In a self-deployment, sensor nodes are mobile and autonomous, they cooperate to determine their final positions. However, if the deployment is assisted, then sensor node positions are precomputed and a human or a mobile robot is in charge of placing static sensor nodes at their positions. When designing a deployment, some constraints should be taken into account. First, the number of nodes deployed should be minimized. Second, if the deployment is assisted, the time needed to place sensor nodes should also be minimized, mainly if the environment is hostile or if the robot is battery operated. Third, obstacles are always present in the area considered. They have an impact on the robot trajectory when deploying sensor nodes or on network connectivity: if the obstacle is opaque, the communication between two nodes at a distance less than the communication range may fail.

In this paper, we focus on a deployment assisted by mobile robots that copes with the presence of obstacles and optimizes the deployment duration by minimizing the longest robot tour duration, minimizes the number of robots used and balances the robot tour duration. We then show how to optimize the tours of robots, while avoiding obstacles in the area considered, which corresponds to more realistic configurations.

II. STATE OF THE ART

The reason to use one or several robots to deploy sensor nodes is that a high number of autonomous and mobile sensor nodes may be too expensive. In the assisted deployment, we distinguish between two different situations where mobile robots are in charge of deploying static sensor nodes.

In the first situation: the robot has two tasks: it should on the one hand move and discover the area considered and on the other hand place sensor nodes at their positions to meet the coverage and connectivity requirements. A robot has to follow predefined rules to move in the area considered and place sensor nodes. This strategy is proposed in [START_REF] Chang | An obstaclefree and power-efficient deployment algorithm for wireless sensor networks[END_REF] where one robot follows a spiral movement policy to deploy static sensor nodes along its trajectory. The goal is not to optimize the robot trajectory but to ensure full area coverage and network connectivity using the minimum number of sensor nodes. In addition, some movement policies are defined to permit the robot to bypass the obstacles. In a similar context, authors in [START_REF] Chang | Obstacle-resistant deployment algorithms for wireless sensor networks[END_REF], propose a serpentine movement policy with obstacle handling policy and boundary policy. The robot has to follow the serpentine movement policy while placing static sensor nodes separated by the optimal distance to reduce the total number of sensor nodes. To conclude, in such a situation, the policies proposed in the two papers cited permit the robot to visit the whole area while avoiding obstacles and placing sensor nodes.

In the second situation: sensor node positions are precomputed and given to the robot(s). In this situation, each position should be visited by exactly one robot and a sensor node should be placed at each position computed. Then, the problem is different. The goal is no longer to discover the area considered and compute node positions, but the problem is how to optimize the duration needed to deploy these sensor nodes. When one robot is involved, this problem becomes similar to the Traveling Salesman Problem, TSP [START_REF] Applegate | Thetravelingsalesman problem: A computationalstudy, princeton universitypress[END_REF], whose goal is to find the shortest tour visiting all sensor nodes positions (representing the cities) only once and going back to its initial position. In [START_REF] Khoufi | Optimized trajectory of a robot deploying wireless sensor nodes[END_REF], we propose the RDS problem, Robot Deploying Sensor, where one robot is in charge of placing sensor nodes at their precomputed positions. The RDS problem is based on the principle of TSP. However, the RDS problem aims to optimize robot tour duration instead of minimizing the total distance traveled. The robot tour duration includes not only the time needed to travel the distance between node positions but also the time needed to change the direction. Since the deployment duration should be minimized in order to save robot battery and in case of hostile environment to prolong its lifetime, more than one robot may be needed. A game theory approach is used in [START_REF] Khoufi | A game theorybased approach for robots deploying wireless sensor nodes[END_REF] to find the optimized tours in terms of deployment duration of two robots in charge of deploying static sensor nodes. In this study, the robots have not only to place sensor nodes at their appropriate positions but also to avoid opaque obstacles. The proposed approach meet some constraints such as the robots can carry a limited number of sensor nodes.

The Vehicle Routing Problem (VRP) [START_REF] Baker | A genetic algorithm for the vehicle routing problem[END_REF] generalizes the Traveling Salesman Problem. The vehicle routing problem aims to find a set of tours that visits all positions at a minimal cost such as the shortest path, the minimum number of vehicles, etc. The vehicles start and end their tours at the depot. Each position is visited only once, by only one vehicle, and each vehicle has a limited capacity.

Our problem, called the Multi-Robot Deploying wireless Sensor nodes (MRDS) problem, presents many similarities with the VRP problem: mobile robots correspond to vehicles and Points of Interest (PoIs) where sensor nodes should be placed to ensure the monitoring task, correspond to the customers to be served. However, there are differences on the objectives to optimize as we will see in the next section.

III. DEPLOYMENT ASSISTED BY ROBOTS

A. Goal

Our goal is to minimize the deployment duration of static sensor nodes, called Points of Interest, in a given environment by K ≥ 1 mobile robots. Since on the one hand robots are battery-operated and on the other hand the environment may be hostile (e.g. deployment in a postcrisis situation), the duration of the deployment must be the shortest as possible. Hence the idea of minimizing the duration of the longest tour performed by a robot. In addition, the best balancing between robot tours durations is required. Sensor node positions are computed such that area coverage and network connectivity are ensured. Then, there is at least one path from each sensor node to the sink in order to forward the collected data.

B. Problem formalization

The Multi-Robot Deploying wireless Sensor nodes (MRDS) problem is defined as follows:

Let {1, . . . N } be the set of PoIs to be visited by robots. By convention, 0 is called the depot. It is the departure and arrival location of robots. Let K ≥ 1 be the number of available robots. The problem is to design a set of k tours, one tour per robot with 1 ≤ k ≤ K, that:

• Minimizes the longest tour duration,

• Minimizes the number of robots used,

• Minimizes the standard deviation of the robot tour durations.

Under the constraints:

• Any robot k, with 1 ≤ k ≤ K, has a limited carriage capacity Q k : it is unable to carry more than Q k sensors.
• Each robot starts and ends its tour at the depot.

• Each PoI should be visited by exactly one robot.

The MRDS problem can be expressed more formally with the following notation: N : is the total number of PoIs to be visited, K ≥ 1 is the number of available robots and K * is the number of robots really used. Thus, we have 1 ≤ K * ≤ K. The depot is denoted by 0, and the PoIs are denoted by 1, 2 or N . Q k : is the capacity of robot k. d i,j : is the distance required for traveling from node i to node j. l s : is the linear speed of each robot. a s : is the angular speed of each robot. θi,j,t : is the angle formed by the segments [i, j] and [j, t].

The decision variables of the model are: X k ij : is the decision variable that is equal to 1 if robot k visits PoI j immediately after PoI i and is equal to 0 otherwise. Y k i : is the decision variable that is equal to 1 if PoI i is visited by robot k and is equal to 0 otherwise. Let T T k be the tour duration of the robot k. This duration includes the duration due to the distance traveled and the duration due to direction changes.

T T k = N i=0 N j=0 d i,j * X k ij /ls+ N i=0 N j=1 N t=0 θi,j,t * X k ij * X k jt /a s
(1) First objective: minimizing the longest tour T T :

M inimize T T = max k∈[1,K] T T k (2)
Second objective: minimizing the number of robots used N T (i.e. number of tours):

M inimize (N T = K * ) (3)
Third objective: minimizing the standard deviation σ of the robot tour durations:

M inimize(σ = 1 K * K * k=1 T T 2 k - 1 K * K * k=1 T T k 2 ) (4)
Constraints:

• Each PoI is visited by exactly one robot

K k=1 Y k i = 1 ∀i ∈ [1, N ] (5)
• The number of robots used is equal to

K * ≤ K K k=1 N i=1 Y k i = K * k=1 N i=1 Y k i = N (6)
• Each robot visits a number of PoIs less than its capacity

N i=1 Y k i ≤ Q k ∀k ∈ [1, K * ] (7)
• Subtours are eliminated

N i=0 N j=0 X k ij ≤ N i=1 Y k i ∀k ∈ [1, K * ] (8)
• Decision variables ∈ {0, 1}

X k ij ∈ {0, 1}, Y k i ∈ {0, 1}, ∀i ∈ [1, N ]; ∀k ∈ [1, K] (9)
Thus, from equations 2, 3 and 4, the new MRDS problem is defined as follows,

M inimize f {T T,N T,σ} = max k∈K (T T k ), K * , 1 K * K * k=1 T T 2 k - 1 K * K * k=1 T T k 2    (10)
under the constraints 5 to 9 described above.

Property 1: A necessary feasibility condition of the MRDS problem is given by:

K k=1 Q k ≥ N. ( 11
) IV. NSGA-II BASED APPROACH FOR MRDS OPTIMIZATION A. Overview of NSGA-II
Multi-objective optimization (also known as multiobjective programming, vector optimization, multi-criteria optimization) is an area of multiple criteria decision making, that deals with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Optimizing a group of objective functions is not a simple task. The Multi-objective Optimization Problem (MOP) can be formulated as follows:

(M OP ) min f i (x), i ∈ [1, m] s.t x ∈ D
Where the vector x = (x 1 , . . . , x n ) T ∈ D is the vector of n decision variables and m is the number of objectives. D is the feasible solution space, and f i (x) is an objective function, and the vector y = (y 1 , y 2 , . . . , y m ) is a solution, with y i = f i (x).

Definition 1: For any MOP minimization, a solution x ∈ D is said to be dominated by a solution x ∈ D (it is denoted by x ≺ x ) if the following conditions are satisfied:

i)f i (x) ≤ f i (x ) ∀ i ∈ [1, m] ii)∃ i ∈ [1, m] such that f i (x) < f i (x )
The set of optimal solutions is composed of the nondominated vectors, often called the Pareto front and also denoted

P F * = {x ∈ D | ∃ x ∈ D, x ≺ x}.
In other words, the Pareto front provides the best tradeoff for the objectives considered. The goal of the multiobjective optimization is to find the Pareto front for a given problem. NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], Non dominated Sorting Genetic Algorithm, is often used to solve multi-objective optimization problems (see for instance, the use of NSGA-II to build clusters in vehicular networks [START_REF] Hadded | A multi-objective genetic algorithm-based adaptive weighted clustering protocol in vanet[END_REF]). This algorithm is a multi-objective version of the genetic algorithm in which the solutions explored are classified into Pareto-optimal fronts. The crossover operator is one of the main parts of NSGA-II. The input of this operator consists of two solution vectors (known as parents). The output is two child vectors, which have certain features from both parents. For the sensor-part, we will apply the same crossover operator as used in the RDS problem [START_REF] Khoufi | Optimized trajectory of a robot deploying wireless sensor nodes[END_REF], that is PMX (Partially Matched Crossover) due to its good performances [START_REF] Kumar | A comparative analysis of pmx, cx and ox crossover operators for solving traveling salesman problem[END_REF].

Mutation: After recombination, the mutation operator is applied to randomly change some genes in an individual. This operator serves as a strategy to prevent solutions from being trapped in local optima. An example of mutation is illustrated in Figure 2, where the 8 th gene of the sensor-part of the individual described in Figure 1 suffers a mutation. This gene corresponding to PoI 8 belongs to the third robot (see Figure 2(1)). After mutation, this gene belongs to the third robot (i.e. PoI 8 is visited by robot 2), see Figure 2(2). To make the mutated individual valid, the robot-part of the individual is updated (minus 1 in the number of PoIs visited by robot 3 and plus 1 for robot 2), see Figure 2(3) depicting the new individual obtained after mutation of gene 8.

Selection:

The selection process in NSGA-II is based on the dominance principle. The combined population P itr is sorted Into Non-dominated levels (F 1 , .., F r ) according to the non-dominance principle. Solutions from the nondominated front level 1 to fronts l ≤ r are included into the new population P itr+1 , such that |P Itr+1 |=population size. If some solutions of the last front F l should be added to P itr+1 , these solutions are chosen such as they have the best crowding distance. The next generation is started based on the new population P itr+1 .

Fig. 2: An example of mutation operator

Selection of the best solutions: After the experimentation, we identify a set of Pareto optimal solutions by gathering all the non-dominated solutions found in 30 independent runs. These solutions provide various tradeoffs between the three objective functions considered. We let the designer choose the best tradeoff. For instance, if a solution with two robots is preferred, the designer will select the solution working with two robots providing the smallest deployment duration. If several solutions provide close tour durations, the designer may take the solution with the smallest standard deviation.

C. Hybrid algorithm combining NSGA-II and 2-opt for the MRDS problem

Figure 3 depicts a solution found by NSGA-II that minimizes the standard deviation for 3 robots and 20 PoIs. It is obvious that the duration of each tour in this figure is not minimized. There exists a permutation of the ordered sequence of PoIs visited that improves the tour duration.

More generally, NSGA-II needs many iterations to find good solutions, specially when it starts with initial solutions randomly chosen. We decided to provide NSGA-II with initial solutions that have already been optimized by a heuristic, in order to improve the quality of the solutions obtained by NSGA-II. We also noticed that for any given number of robots, any permutation of the sequence of PoIs visited that decreases the tour duration tends to improve the first objective (i.e. minimizing the longest tour duration), has no effect on the second objective (number of robots used), and has a positive impact on the third objective (the standard deviation of the robots tour durations). In other words, the new solution obtained dominates the initial one. That is why we choose the 2-Opt heuristic [START_REF] Croes | A method for solving traveling-salesman problems[END_REF] to improve the tour duration of any individual given to or created by NSGA-II. The 2-Opt algorithm [START_REF] Croes | A method for solving traveling-salesman problems[END_REF] starts with an initial solution and tries to iteratively improve it by replacing two edges with two new ones that reduce the tour duration. This algorithm provides a local optimum based on the solution given initially. To improve the performance of the NSGA-II algorithm we decided to combine it with the 2-Opt algorithm adapted to the MRDS problem, this algorithm is called Hybrid. More precisely, instead of starting with an initial random population, the Hybrid algorithm applies the 2-Opt algorithm to optimize each individual of the initial population. In addition, at each iteration, the children obtained with the crossover operator are mutated with the gene mutation probability and then optimized by applying again the 2-Opt algorithm. As we will see in the next section, the solutions obtained by Hybrid dominate those obtained by NSGA-II with initial solutions randomly chosen.

D. Problem resolution

To solve the MRDS problem, we have implemented both the NSGA-II algorithm and the Hybrid algorithm using java programming language. We evaluated the performance of the NSGA-II algorithm and the Hybrid algorithm using 4 configurations with different numbers of PoIs {10, 20, 30, 40} located in a 500mx500m area. For each configuration, we conducted 30 independent simulation runs using different initial populations randomly selected. Table I shows the simulation parameters used in each configuration, the mutation probability is equal to 0.1. ) Deployment duration and presence of obstacles: Our goal is to evaluate the solutions provided by both NSGA-II and Hybrid algorithms in terms of the three objectives considered in the MRDS problem. Each simulation run gives a Pareto front. We then build the final Pareto front of each configuration from the 30 Pareto fronts previously obtained. Furthermore, we quantify the simulation time needed to get these results.

Number of

In the real environment, obstacles are always present. They have a big impact on the robot tour and the deployment duration. Thus we study the impact of obstacles. How to compute the deployment duration when one or multiple obstacles exist between two consecutive PoIs of the same robot tour? Figure 4 illustrates a configuration with 40 PoIs depicted in red, the depot depicted in green and three obstacles represented by black rectangles. We propose a strategy to bypass the obstacles with the minimum duration. More precisely, we assume that each obstacle is defined by the polygon formed by its vertices. For each obstacle, we define as many intermediate points as the number of obstacle vertices. Then, we select the path that goes through intermediate points until reaching the PoI destination, having the minimum duration. For instance, in Figure 5, the direct path from A to B is made impossible. The intermediate points I 1 , I 2 and I 3 are the best combination in terms of duration to go from A to B. The tour duration of this path is computed as the sum of the durations due to any segment composing the path and of course the time needed for angle changes between each two successive segments. Notice that, the list of intermediate points between each two PoIs are precomputed and stored in a file. This information will be used during the simulation runs.

2) Simulation results: When the number of PoIs is small, (e.g. 20 PoIs) both NSGA-II and Hybrid algorithms provide close Pareto fronts. For instance Figure 7a depicts the Pareto fronts obtained when 20 PoIs are deployed in an area without obstacles. However, when obstacles are present, the Pareto front obtained by the Hybrid algorithm In larger configurations, for instance when 30 or 40 PoIs should be deployed and when obstacles are present or are not, the Pareto fronts obtained by the Hybrid algorithm outperform the ones obtained by NSGA-II in terms of tours duration and tours balancing. This is due to the use of the 2-Opt algorithm that permits to avoid edges crossing in the same tour, leading to smaller tours duration and better balancing between these tours.

To demonstrate the distribution of non-dominated individuals on the objective space for NSGA-II and Hybrid algorithms, we have considered 4 configurations (10, 20, 30 and 40 PoIs) with and without obstacles. Figures 7a,8a, and 9a depict the Pareto front obtained by gathering all the non-dominated solutions found by each algorithm in the 30 independent runs corresponding to configurations with 20, 30 and 40 PoIs, respectively. provided by Hybrid dominates in most cases the Pareto front given by NSGA-II.

V. CONCLUSION

The deployment of static wireless sensor nodes is usually done by mobile robots in charge of placing these sensor nodes at precomputed positions in a given area. Since robots are usually battery-operated and the environment may be hostile, for instance in a post-crisis situation, the duration of the deployment must be minimized. This duration is equal to the longest duration of robot tours. In order to balance these tour durations, we also want to minimize their standard deviation. In addition, the number of robots used

BRPDefinition 2 :

 2 . NSGA-II algorithm for the MRDS problem 1) Presentation of the NSGA-II algorithm: NSGA-II begins with an initial population P made up of solution vectors called individuals. At each iteration, an auxiliary population Q is formed by applying the crossover and mutation operators (lines 8 to 15). Then, both the current P and the new Q populations are merged together to form one set of solutions R, which will be sorted according to the non-domination and crowded comparison (line 17). Finally, only the best individuals in R are included in the next generation and will participate in the production step while the other individuals are deleted (lines 19 to 25). These steps are repeated until the maximum number of iterations is reached. Algorithm 1 NSGA-II algorithm for MRDS problem Input N // population size P c //crossover probability P m // mutation probability N br iteration max // maximum number of iterations 1: Itr ← 0 // current iteration 2: P Itr ← {∅} // population of iteration Itr 3: initialize P Itr=0 = { -→ x i Itr=0 , . . . , -→ x N Iter=0 } 4: evaluate P Itr=0 5: while (Itr < N br iteration max) do 6: Q Itr ← {∅} // new population 7: t ← 0 8: while (t ≤ size(Q Itr )/2) do 9: parents ← selection(P Itr ) 10: Child ← crossover(P c , parents) 11: E ← mutation(P m , Child) Itr ← P Itr ∪ {Q Itr } 17:R Itr = r i=1 F i //F i is a Pareto front meeting F 1 < F 2 < . . . < F r 18: P Itr+1 ← {∅}; i ← 0 19: while (|P Itr+1 | + |F i | < N ) do 20: P Itr+1 ← P Itr+1 ∪ F i Itr ← P Itr ∪ {N -|P Itr | f irst solutions in F i } 26: end while2) Application of NSGA-II to the MRDS problem:Individual Representation: In MRDS problem, an individual represents a possible solution: a set of robots tours where the k th robot makes the k th tour, each tour is defined by the sequence of PoIs visited by a same robot. That is why we use two parts to define an individual. The first part of the individual, called sensor-part, is a set of integers where each integer represents a PoI visited by a robot. The second part of the individual, called the robot-part, contains robots information. The robot-part contains as many genes as tours (i.e. robots used) described in the sensor-part. In the robotpart, the k th gene is equal to the number of PoIs visited by the k th robot. An example of individual is depicted in Figure1, where 3 robots are needed, robot 1 visiting 3 PoIs (4, 6 and 5 in this order). Robot 2 visiting the PoIs 1 and 2 and robot 3 the PoIs 3, 7 and 8 in this order. An individual is said valid (i.e. it corresponds to a feasible solution) if and only if each PoI occurs exactly once in the sensor-part (in other words, the sensor part is a permutation of the sequence 1, 2, . . . N ), the sum of the numbers included in the robot-part is equal to N the number of PoIs to visit and the size of the robot-part (i.e. number of robots really used) is less than or equal to K.

Fig. 1 :

 1 Fig. 1: An example of individual

Fig. 3 :

 3 Fig. 3: Best solution minimizing the standard deviation for 3 robots and 20 PoIs.

Fig. 4 :

 4 Fig. 4: Configuration with 40 PoIs.

Fig. 5 :

 5 Fig. 5: Intermediate points between sensor node positions A and B

Fig. 6 :

 6 Fig. 6: Tours of 3 robots with 20 PoIs without obstacles.

For

  each possible number of robots, the distribution of non-dominated solutions found by Hybrid is more localized than with NSGA-II, making easier the choice of the suitable solution. a Without obstacles. b With obstacles.

Fig. 7 :

 7 Fig. 7: Pareto front obtained by 20 PoIs.

Fig. 8 :

 8 Fig. 8: Pareto front obtained by 30 PoIs.

a

  Without obstacles. b With obstacles.

Fig. 9 :

 9 Fig. 9: Pareto front obtained by 40 PoIs.

Fig. 10 :

 10 Fig. 10: Tours of 3 robots with 20 PoIs and obstacles.

TABLE I :

 I Simulation parameters 1

TABLE II :

 II The average and the standard deviation of simulation times (in seconds) obtained by NSGA-II and Hybrid algorithms


Nicolas Lermé
email: nicolas.lerme@u-psud.fr

Petr Dokládal
email: petr.dokladal@mines-paristech.fr

Geometry Analysis of Superconducting Cables for the Optimization of Global Performances

Keywords: Segmentation, Registration, Shape analysis, Clustering, Superconductivity, Cable

Superconducting cables have now become a mature technology for energy transport, high-eld magnets (MRI, LHC) and fusion applications (ToreSupra, and eventually ITER and DEMO). The superconductors are extremely brittle and suer from electrical damages brought by mechanical strain induced by electromagnetic eld that they generate. An optimal wiring architecture, obtained by simulation, can limit these damages. However, the simulation is a complex process and needs validation. This validation is performed on real 3D samples by the means of image processing. Within this objective, this paper is, to our best knowledge, the rst one to present a method to segment the samples of three types of cables as well as a shape and geometry analysis. Preliminary results are encouraging and intended to be later compared to the simulation results.

Superconducting cables have now become a mature technology in energy transport, high-eld magnets (medicine (MRI), high-energy physics (LHC)) and magnetic connement in fusion applications (ToreSupra, eventually ITER, DEMO).

A superconducting cable presents a multiscale internal structure. Such a cable consists of strands arranged together given some application-dependent architecture. Individual strands are composite structures either formed by superconducting microlaments embedded in a metallic matrix or by a thin superconducting layer deposited onto a metallic substrate.

A substantial drawback of some of these cables is the fragility of the superconductors. Mechanical strains can indeed cause deformations, thus degrading their performance. Whereas these strains can be limited during shaping (wiring or winding) or thermal cool-down, they remain problematic during operation when exposed to high electromagnetic elds (due to its own Lorentz force, particularly under cyclic loading).

However, the performance degradation can be diminished by optimizing the geometry of the ca-bles. Optimize the performance of these cables is thus essential and could directly benet to a large number of research and industrial actors. The global performances of the cable are simulated using models of the electrical and/or mechanical behavior of the cable structure [START_REF] Torre | Mechanical and electrical modeling of strands in two ITER CS cable designs[END_REF][START_REF] Manil | Mechanical modeling of low temperature superconducting cables at the strand level[END_REF]. Given the complexity of various types of cables, the validation of these models is done by statistical comparison of the geometry of the models to the geometry of real cables obtained from tomography images. Depending on the result of these comparisons, the design of the cables can be optimized, until a better cable architecture is obtained.

This paper focuses on the identication of the experimental geometry on three types of cables, involving mostly 2 automatic registration, segmentation, clustering and features extraction tasks. To our best knowledge, this is the rst paper providing methods and results for the geometry analysis on these cables. For each type of cable, we provide below the physical parameters and the image characteristics.

Available cables

Three distinct types of cables are considered with dierent architectures, appearances and composition: the cables-in-conduit [START_REF] Weiss | Systematic approach to examine the strain eect on the critical current of Nb3Sn cable-in-conduitconductors[END_REF], the Rutherford cables [START_REF] Oberli | Development of the Nb3Sn Rutherford cable for the EuCARD high eld dipole magnet FRESCA2[END_REF][START_REF] Milanese | Design of the EuCARD high eld model dipole magnet FRESCA2[END_REF] and the power cables [START_REF] Seidel | Tensile surface and structure: A pratical guide to cable and membrane construction[END_REF]IEC, 2004). Several samples of each with dierent parameters were analyzed (see Tab. 1 and 2 for their characteristics, and Fig. 1 to assess the variety and the quality of the images).

Cables-in-conduit (see Fig. 1(a,b)) consist of superconducting strands (s.c.) and nonsuperconducting strands (n.s.c.). S.c. strands are composed of kernels in Nb 3 Sn and bronze (white) wrapped by a jacket in copper (gray) while n.s.c. strands are made of copper (gray). All strands are twisted together in a multistage fashion according to a predened cable pattern composed of stages and petals. For instance, the pattern (3, 3, 5) of the cable N05 has three stages. The rst (lower) stage consists of twisted triplets (15 petals), each with 2 s.c. and 1 n.s.c. strands. These triplets are again twisted by three (5 petals) and nally by ve (1 petal), thus leading to a total of 30 s.c. and 15 n.s.c. strands. All strands are then inserted in a stainless steel conduit. Some void fraction is kept to enable the circulation of a cooling uid (helium). Notice that all stages are twisted with a dierent twist-pitch. Typically used in fusion applications, these cables can transport currents of 45kA under a magnetic eld of 12.3T, exposed to transversal Lorentz forces of 554kN/m.

Power cables (see Fig. 1(c)) consist of s.c. strands in MgB 2 /nickel alloy and n.s.c. copper strands. All strands are arranged in concentric layers, twisted and inserted in a corrugated cryogenic envelope. Again, some void fraction is kept to enable the circulation of a coolant (gaseous and eventually liquid helium). S.c. strands are located on the outer layer. Typically used in energy distribution, each strand can convey a current of 400A under a magnetic eld of 1T, developing radial, centripetal, Laplace forces of 400N/m.

Rutherford cables (see Fig. 1(d,e)) roughly consist of s.c. strands composed of cores in copper (gray) surrounded by an intermediary zone containing Nb 3 Sn laments (white), themselves wrapped in a copper jacket (gray). All strands are twisted to form a two-layers at cable, compressed to a well-controlled rectangular section. Depending on the design used, the laments zone is arranged to form either an hexagon or a circle. Typically used in medical imaging and higheld magnets, these cables can transport currents of the order of 20kA under a magnetic eld of 10-15T, exposed to Lorentz forces of 1-5MN/m.

Outline of the paper

The rest of this paper is as follows. In Section 2, we briey explain the registration of overlapping samples. In Section 3, we detail, for each type of cable, the proposed methods for extracting the structures of interest from the resulting images.

In Section 4, we propose indicators reecting potential damages. Finally, we present results in Section 5 and discuss future work in Section 6.

IMAGE REGISTRATION

The cable samples being too long to be imaged at once, multiple overlapping scans have been acquired with a constant translation step along the z-axis 3 . Each scan has then been registered on the previous one by minimizing the mean square error of the dierence of intensities over the overlapping region along the z-axis. The minimization along the z-axis is sucient since no residual displacement along the x and y axes was observed.

IMAGE SEGMENTATION

The purpose of the segmentation is to extract the contours of strands (and the conduit, if need be) and their centerlines. Most structures to extract are nearly circular and touch each other. Their appearance and contrast however dier for all cable architectures. Distinct algorithms have been designed for all types of cables with their own set of parameters. Some of these parameters still require a manual tuning (in this case, it will be mentioned below). However, most of them appear to be stable and expressed with respect to the image resolution and cables characteristics. These algorithms share common diculties to overcome to get reliable measurements. First, they must be able to assess slight deviations from the circularity, be robust to noise, artifacts and poor contrast. Second, they must be fast and able to handle large volume data (possibly more than shown in Tab. 1 and 2). To accommodate these constraints, a simple approach has been preferred (whenever possible) where the 3D volume is segmented as a sequence of 2D images along the z-axis. This allows to run some steps in parallel. Once strand contours have been obtained, the centerlines consist of the strand centroids. Moreover, we assume the following known and constant: the diameter of a strand (denoted by S dr ), the thickness of the strand jacket (denoted by S jt ), the thickness of the conduit of the cable (denoted by C ct ) as well as the number of s.c. and n.s.c. strands (denoted by N sc and N nsc , resp.).

Rutherford cables

The core of strands being better contrasted than the jackets, we propose an automatic procedure that relies on the laments zone to extract the contours of strands in two steps (see Fig. 2). Due to the variety of images, notice that the above thresholds need to be manually adjusted, independently of ground truths (see Section 5.1.1).

Extraction of strands

As shown in Fig. 2, the laments zone is poorly contrasted and strands touch with each other. To overcome these diculties, we introduce several priors (near circularity, small displacement and volume conservation of strands sections) and proceed in two successive steps. First, a distance transform is computed from each labeled core of I C using an ecient pixel queue algorithm [START_REF] Ikonen | Pixel queue algorithm for geodesic distance transforms[END_REF]. This algorithm has a worst-case complexity of O(n log n) (where n is the number of pixels in the image). Each distance map is computed using the WDTOCS metric, described in [START_REF] Ikonen | Pixel queue algorithm for geodesic distance transforms[END_REF]. Let I : Ω ⊂ Z 2 → R be an image and N be a neighborhood. Without loss of generality, we propose to use A region-growing algorithm is then used to extract the laments zone, based on geodesic distance maps whose amount of regularity is controlled by a parameter α (h). The impact of α after region-growing is shown when it is small (i), moderate (j), large (k). The strands are obtained by expanding the laments zone with α = 0 (l).

N = {(p, q) ∈ (Ω × Ω) | p -q ≤ √ 2}, (a) I D (b) I F (c) I A (d) I T (e) I T (f) I M (g) I C (h) I DM (α = 10 4 ) (i) I R (α = 0) (j) I R (α = 10 4 ) (k) I R (α = 10 6 ) (l) I R
where . is the L 2 norm in Z 2 . For any pair (p, q) ∈ N , the WDTOCS metric is dened as

dist(p, q) = p -q 2 + α(I p -I q ) 2 , (1)
where α ∈ R + is a parameter that balance geometric and image information. The larger the parameter α is, the more the image information is taken into account. An example of distance map from the rightmost core is shown in (h) where the distance is proportional to the intensity (the dynamic of the image has been stretched for visualization purpose). Distance transforms being independent from each other, their computation is in practice performed in parallel using OpenMP. Once all the distance maps obtained using α > 0, a region-growing algorithm is applied to obtain the outer contour of the laments zones: all cores grow simultaneously by greedily selecting the pixels having the minimum cost based on their respective distance maps, until a target volume is reached 4 . The eect of varying the parameter α after region-growing is depicted on the image I R when α is small (i), moderate (j) and large (k).

Finally, the contours of strands are obtained by expanding the laments zones in such a way that none of them is favored. This is achieved by repeating the above steps for α = 0 (image I R (l)).

In our experiments, we set α = 10 4 .

Cables-in-conduit

As shown in Fig. 3, the s.c. strands are better contrasted than the n.s.c. ones. Based on this observation, we propose a three-steps scheme that rst extracts automatically the conduit and then 4 It is adjusted if the laments zone is an hexagon.

the s.c. strands. The n.s.c. strands are then semiautomatically extracted based on initial markers.

Extraction of the conduit

First, the source image is denoised by an ASF with a squared structuring element up to the size of 0.05 × S dr [START_REF] Sternberg | Grayscale morphology[END_REF]) (image I D (a)).

To further atten homogeneous areas, the image I D is ltered by a Gaussian of size 0.05 × S dr and thresholded (image I T (b)). Next, a morphological opening, a holes lling algorithm and then a morphological closing are applied on the image I T using a square of size 0.2 × S dr as structuring element (image I M (c)). Assuming the ideal conduit is nearly circular, an ellipse is tted on the image I M . Its size is subtracted by 2 × C ct to t the inner contour of the conduit (image I R (d)).

Extraction of the s.c. strands

The strategy employed here is to rely on kernels to extract the contours of strands. For doing so, the source image is rst thresholded (image I T (e)). Next, the resulting contours are closed using a morphological dilation with a square of size 0.25 × S jt as structuring element and holes are lled (image I F (f)). To properly align the segmentation on the contours of kernels, a watershed algorithm [START_REF] Meyer | Un algorithme optimal de ligne de partage des eaux[END_REF] is applied on the source image (image I W (g)). The outside marker is the complementary of the image I F and the markers representing the kernels are obtained by performing a morphological erosion of the image I F with a squared structuring element of size 1.25 × S jt .

As for Rutherford cables, s.c. strands are nally obtained by expanding the kernels from the image (a) I W with α = 0 (see Section 3.1.2) and subtracting the complement of the mask I R (image I R (h)).

I D (b) I T (c) I M (d) I R (e) I T (f) I F (g) I W (h) I R (i) I C (j) I R (z = 0) (k) I R (z = 6211) (l) I R (z = 12423)

Extraction of the n.s.c. strands

To overcome the poor contrast on n.s.c. strands, we adopt the same strategy as for Rutherford cables (see Section 3.1.2) but with two dierences. First, the geodesic distances are computed using α > 0 but constrained in I R \ I R . Second, the centroids of s.c. strands must be provided as initialization (image I C (i)). Geodesic distance maps are computed from these centroids and the region-growing algorithm is applied. Once the centroids computed on the resulting contours of strands, the same procedure is applied on the next image (image I R ). This process continues until the end of the cable is reached. To illustrate the correctness of the propagation, the image I R is shown with the n.s.c. strands obtained at the beginning (j), the middle (k) and the end (l) of the cable. Unlike Rutherford cables, it is important to notice that such an approach can fail to recover the contours of n.s.c. strands since centroids depend on the result of the previous image. Such a situation can occur when the contribution of the right term in Eq. 1 is insucient. In that case, the procedure becomes unable to stick to the contours of strands. A suitable value of the parameter α must therefore be chosen carefully. In our experiments, we have chosen to set α = 8 × 10 4 .

Power cables

For extracting strands, a convenient solution would be to use the same approach as for Rutherford cables (see Section 3.1.2) and for the n.s.c. strands of the cables-in-conduit (see Section 3.2.3). As shown in Fig. 1, despite the important amount of noise, the images of power cables present however a much better contrast compared to the images of the other types of cables. We detail below a simple procedure that automatically nd the contours of the conduit and then the strands, both assumed to be nearly circular. First, the source image is thresholded (image I T (a)) and holes are lled (image I F (b)). From the image I F , the largest connected component is discarded and a morphological opening is applied with a squared structuring element of size 0.1 × C ct (image I O (c)). An ellipse is then tted on the image I O . Its size is subtracted by C ct to t the inner contour of the conduit (image I R (d)).

Second, the source image is denoised by an ASF with a squared structuring element up to the size of 0.05 × S dr (image I D (e)) [START_REF] Sternberg | Grayscale morphology[END_REF]. A rst rough estimate of the contours of strands is obtained by thresholding the image I D (image I T (f)). The complement of the mask I R is then subtracted from the image I T and a morphological opening is applied with a square of size 0.03 × S dr as structuring element (image I I (g)). Next, 3D connected components that do not spread all along the cable in the background are removed (image I H (h)). From the image I H , the Euclidean distance to the contours is computed and the resulting image is ltered by a Gaussian of size 0.25 × S dr (image I DM (i)) to ensure a good detection of maxima (image I M (j)). Finally, the contours of strands are obtained by applying a watershed [START_REF] Meyer | Un algorithme optimal de ligne de partage des eaux[END_REF] Second, the source image is denoised by an ASF (e) and thresholded (f). The complement of (d) is subtracted from (f) and a morphological opening is applied (g). 3D connected components that do not spread all along the cable are removed (h). The Euclidean distance to the contours of (h) is computed, ltered by a Gaussian (i) and maxima are identied (j). Strands contours are obtained by applying a watershed (l) on an image (k) combining the morphological gradient of the source image and the inverted distance map to ideal contours from maxima.

the summed image I S (k) composed of the inverted distance map to ideal contours from maxima and the morphological gradient (multiplied by a factor set to 0.1) of the source image (image I R (l)). The multiplier ensures the strands sections to remain mostly circular along the cable.

DAMAGE INDICATORS

During operation, the cables can be exposed to transversal Lorentz forces up to several MN/m. These forces induce deformation and/or damages to strands that come out as various geometrical features. The features detailed below aim at detecting these deformations.

Strand Section Compression

Any deviation to the circularity of strands is a potential source of damage that need to be measured. A variety of shape descriptors has been proposed in the literature. In this setting, desirable properties of shape descriptors are the invariance to translation and rotation, the robustness to noise and a reasonable sensitivity. The papers [START_REF] Montero | State of the art of compactness and circularity measures[END_REF][START_REF]Shape descriptors for image analysis[END_REF] gather a large number of descriptors, out of which two have been selected as applicable in this context and oering similar performance. Let S ⊂ Z 2 be a strand section of a 2D binary image taken along the z-axis. These two descriptors are dened as follows: Elongation Factor), where λ min , λ max are the eigenvalues of the covariance matrix of the strand section S, and

EF(S) = λ max λ min ∈ [1, +∞[ (
CMPN(S) = ( S) 2 2π(µ 2,0 + µ 0,2 ) ∈]0, 1] (Compactness),
where denotes the cardinality of a set and µ p,q denotes the moment of order (p + q) of the strand section S. EF and CMPN are statistical descriptors. EF is lower-bounded by one for a circle and increases for elongated shapes while CMPN is upper-bounded by one for a circle and tends to zero for elongated shapes. These two descriptors verify the above mentioned properties.

Curvature

For all the considered types of cables, strands can locally bend signicantly and these locations are potentially source of damage. Do detect bendings with a large amplitude, we propose to measure the local curvature of the strand centerlines.

The curvature measures a failure of a curve to be straight. It is is positive or null and equal to the inverse of the radius of the tangent circle.

Let us represent a centerline with a two times continuously dierentiable space curve C(t) = (x(t), y(t), z(t)) T ∈ R 3 , parameterized by t. Also, we denote resp. by γ (t) and γ (t) the rst and second and derivatives of C with respect to t. The local curvature of the curve C is dened by

κ(t) = γ (t) × γ (t) γ (t) 3 , (2)
where . and × are respectively the L 2 norm and the cross product, both in R 3 . In what follows, we briey discuss some numerical considerations. First, to avoid division by zero, Eq. 2 is set to zero when the denominator is smaller than some presence of noise, estimating small values of curvatures is however a delicate problem. Nevertheless, under the assumption that the strands cannot mechanically bend over some limit value, the nite dierences are computed using a grid spacing (denoted by ∆h) proportional to the strand diameter S dr . A large value of ∆h allow us to assess small curvature values despite the noise. Also, we choose not to consider extremities of centerlines. Finally, to yet increase the robustness, the centerlines are rst smoothed by a Gaussian lter of standard deviation σ = 0.05 × S dr .

Void fraction

It is the ratio of area not occupied by the strands over the area delimited by the inner part of the conduit. A large void fraction means that strands are likely to move and bend. Once the cables are segmented, it can be obtained without diculty.

Twist-pitch

The twist-pitch refers to the stranding periodicity of a cable. Unlike the power cables or the Rutherford cables, the cables-in-conduit are wired and compacted so that some (limited though) randomness is injected in the architecture. As a consequence, the estimation of twist-pitches only applies to cables-in-conduit. Given the presence of some quantity of randomness, we will estimate the twist-pitches using the autocorrelation of the strand centerlines. Recall that dierent stages are wired with dierent twist-pitches (see Tab. 1). The estimation of these twist-pitches thus implies to identify the stages of the cable. The identication of the petals at dierent stages can be seen as a hierarchical clustering problem, constrained by the pattern of the cable. To form clusters at a given stage, a possible choice is to use pairwise distances of all strands. Indeed, closely running strands are more likely to belong to the same petal.

Let us formalize the above problem. We denote the set of N centerlines of length K by

{c i } N i=1
, where c i ∈ R 3K . For any couple (i, j) ∈ {1, . . . , N } 2 , we dene d(c i , c j ) as the distances between c i and c j . The distance is dierent depending of the norm. A reasonable choice for d is the mean distance, based on the L 2 norm. Additionally, for a given number of stages (denoted by M ), we denote by P m the number of petals, for any m ∈ {1, . . . , M }. We also denote by {ϕ m } M m=1 a set of applications where ϕ m : {1, . . . , N } → {1, . . . , P m } assigns a label to each centerline of the stage m, for any m ∈ {1, . . . , M }. Last, we denote by 1 {.} the indicator function returning 1 if its argument is true, 0 otherwise. Then, we propose to solve the constrained hierarchical clustering problem by nding a minimizer to M m=1 (i,j)∈{1,...,N } 2

1 {ϕm(i)=ϕm(j)} d(c i , c j ) 2P m KM , (3)
subject to the following constraints: 1. {ϕ m } M m=1 is a hierarchy, 2. For each petal at M = 1, N sc /N nsc are xed, 3. For any stage, the size of each petal is xed. For a single stage, Eq. 3 can be put under the form of an integer linear program (with a number of variables and constraints both of O(N 2 P 1 )) and solved exactly using an integer linear programming solver. For this experiment, the last version of CPLEX has been chosen for its good performances [START_REF] Mittelmann | Recent benchmarks of optimization software[END_REF]. Even for a simplistic situation where a single stage and a limited number of centerlines are considered (N=15), several days of calculus are needed. This remains acceptable for this setting but becomes intractable for large cables with hundreds of strands.

To overcome this situation, we use a greedy strategy for solving Eq. 3 heuristically. An illustrative example is provided in Fig. 5 for the N05 cable (clusterings are superimposed on source images). For the rst stage, random triplets satisfying the above second and third constraints, are formed (see Fig. 5(a)). A greedy heuristic is then applied, that consist in swapping the pairs of centerlines satisfying the above second constraint and making the strongest decrease of Eq. 3. This process is iterated until no swaps can be performed (see Fig. 5(b)). The next stages are optimized in the same way, except that (i) the initialization is based on the clustering obtained at the previous stage and (ii) that pairs of groups of centerlines are swapped instead of centerlines (see Fig. 5(c,d)). This allows us to keep clusterings as a hierarchy (rst above constraint). Finally, the overall approach is run 100 times and the solution having Eq. 3 minimum is kept.

4.5

Free areas and segments Subject to an intense magnetic eld, strands of cables-in-conduit will transversally move wherever there is locally an insucient compaction. Identifying these locations is therefore an important indicator of fragility of some particular stranding pattern. For doing so, we need a measure to estimate the area where a strand can move. Let us denote by S ⊂ Z 2 the section of a particular strand and by T that of the union of the remaining ones, both from the same 2D binary image taken along the z-axis (see Fig. 6(a)). We denote by F the area where S can move, obtained by applying a morphological closing on T using S as a structuring element (denoted by ϕ S (T ), see Fig. 6(b)) and then performing a geodesic reconstruction of S under the complement (denoted by (.) c ) of ϕ S (T ) (see Fig. 6(c)):

F = [δ B (S) ∧ [ϕ S (T )] c ] ∞ ,
where δ B (S) denotes the dilation of S by a ball B of unit radius, ∧ denotes the logical AND and [.] ∞ denotes iterated until idempotence (achieved in practice, in a nite number of iterations). Based on F , we propose a rst possible descriptor, Free Transversal Area (FTA), expressed as

FTA(F, S) = (F \ S) S × 100 ∈ R + .
The above descriptor is null when the strand cannot move and increases as the strand gets a larger space to move. The distribution of FTA is a descriptor revealing a fragility of a cable exposed to a strong magnetic eld. Extracting connected components where FTA is greater than some positive value alongside a strand permits to identify portions of strands able to move transversally. This allows us to propose a second descriptor of cable fragility, Free Transversal Segments (FTS), dened as the set of all lengths of such segments.

EXPERIMENTAL RESULTS

Validation

Segmentation

Due to the variety of used cables and the variable quality of images, the segmentation is a delicate task needing validation. We propose to validate the results by relying on an expert. First, this expert did a visual check of the segmented cables to ensure there are no inconsistencies. Second, the contours of the strands and the conduit (where applicable) have been manually delineated by this expert on a few 2D images, equally spaced along the z-axis. For cables-in-conduit and power cables, one image every 1.5mm and 8.5mm has been selected, resp. Due to the variety of resolution, three images have been only selected per Rutherford cable.

To assess the accuracy of the results, we use evaluation metrics on the contours of strands and the conduit using the Volumetric Overlap Error (VOE), the Relative Absolute Volume Difference (RAVD), the Root Mean Square Distance (RMSD) and the Maximum Distance (MD) (see [START_REF] Ginneken | 3D segmentation in the clinic: A grand challenge[END_REF]) but also the popular Dice Coecient [START_REF] Dice | Measures of the amount of ecologic association between species[END_REF]. Although the metrics from [START_REF] Ginneken | 3D segmentation in the clinic: A grand challenge[END_REF] were presented in a clinical setting, we do believe that they still remain relevant here. In addition, we also propose to compare the position of centerlines using the L 2 norm between centroids (CD).

The results of these comparisons are summarized in Tab. 3. For each metric and type of cable, the mean and standard deviation are provided. For cables-in-conduit, the negative value of the mean RVD for s.c. and n.s.c. strands indicates that their volume is under-estimated and suggest an adjustment of segmentation parameters. As expected, the error on n.s.c. strands appears to be larger than of the s.c. ones due to their poorly contrasted contours (e.g. a factor of two for the mean CD). For most of the metrics used, compared to other types of cables, the worst error is reached for Rutherford cables. Nevertheless, all metrics globally show that the structures of interest (especially the conduit) are well segmented with, for instance, a mean DC greater than 94% and a mean RMSD always less than 3 pixels. The N22 (96.42%) mgb2_133 (98.22%)18PITN01 (95.46%) N05 (95%) mgb2_113 (97.78%) 40RRPR01 (93.4%)

Figure 7: Accuracy of the segmentation procedures on the contours strands and the conduit (if available). For each type of cable, we select the 2D images from the obtained segmentations and the manual ones with the same position along the z-axis, having the mean largest (top row) and smallest (bottom row) DC. Both images are combined to show false negatives (red) and false positives (cyan), superimposed on the corresponding source image. For each image, the average DC is provided between parentheses. position of centerlines is also well preserved with a mean CD always less than 1.4 pixels.

A subset of these results is illustrated in Fig. 7. For each type of cable, we provide the 2D images from the obtained segmentations and the manual ones with the same position along the z-axis (where manual segmentations are available) having the largest (top row) and the smallest (bottom row) average DC. Each couple of images is then combined to show false negatives (red) / false positives (cyan), superimposed on the source image.

Damage indicators

To validate the capacity of the strand sections compression indicators (see Section 4.1) to detect non-circularities, we propose the following experiment (see Fig. 8). Two distinct locations have been identied along the same strand of the N25 cable, where the section is either ellipsoid or circular. It has been veried that the compression is unique along the strand. The contours of these sections superimposed on source images are shown on top row. On the bottom row are shown the response returned by the indicators along the cable. Both EF and CMPN depict a good robustness to noise and highlight well the compression by reaching a large peak at the compressed location and remaining close to zero or one elsewhere. The same observations were made at other loca- tions and on Rutherford cables.

Clustering

Estimate the quality of the clustering w.r.t. ground truths is an important issue. However, no ground truths are currently available. Due to a large number of strands and an important number of constraints to satisfy, their construction is indeed a dicult task, especially when the cables are very short (as here). Since the calculus of twist-pitches requires the cables to be clustered, we believe that obtaining reasonable, close-to-expected values, veries the clusterings.

Results

Cables-in-conduit

First, we have compared the values of void fraction obtained experimentally to nominal values. The result of these comparisons is presented in Tab. 4. In average, the void fraction diers (in absolute value) by 1.23% and does not exceed 2.72%. Compared to the cable N05, it also conrms that the cables N22 and N25 are more likely do develop damages due to larger void fraction.

Similarly, experimental values of twist-pitches have been compared to nominal values. Depending of the length of the sample, more than one or less than one twisting periods can be available. For the studied cables, an exhaustive comparison to references values is possible. The result of these comparisons is shown in Tab. 5. In average, the twist-pitches dier (in absolute value) (blue) and both (black thick line) strands. For both cables, local curvatures remain very small due to the near linearity of strands. Also, the shape of the related distribution suggests that it is centered around the curvature induced by the twist-pitch and that local curvature maxima correspond to locations of potential conductivity loss. The mean of these distributions is nearly the same (2×10 -5 µm -1 ) corresponding to a curvature radius of 50mm. Nevertheless, the mean is slightly larger for the N25 cable. This is consistent with the fact that this cable has smaller twist-pitch values. Additionally, the distribution of EF and CMPN on both cables is centered, as expected, on a value close to one, meaning that strands sections are mainly circular. The higher peak and longer tail of the EF distribution on s.c. strands for N05 than for N25 indicates more frequent and more heavily compressed strands. This is expected as a consequence of stronger compaction of the N05 cable.

Finally, the tail of the FTA and FTS distributions of the N05 cable is shorter than for the N25 cable. This means that the strands of the N05 cable have much less space to move and that the segments where they can move are shorter. These distributions tend to decrease, meaning that a large area where a strand can move is less likely to occur in the cable than a small one. Again, this is an expected consequence of the stronger compaction of the N05 cable. Moreover, large areas are more likely to occur for s.c. strands than for n.s.c. strands. This is consistent with the fact that the number s.c. strands is greater than the number of n.s.c. strands (see Table 1).

Power cables

As for cables-in-conduit, the values of void fraction obtained experimentally from segmentations have been rst compared to nominal values. The result of these comparisons is available in Tab. 4. In average, the void fraction diers (in absolute value) by 2.6% from the nominal values and does not exceed 2.87% (which appears to be slightly larger than for cables-in-conduit). Finally, we have compared in Fig. 10 the distributions of the local curvature of the two power cables: mgb2_113 and mgb2_133. As for cablesin-conduit, the strands have near linear trajecto- ries, thus leading to small values of local curvature up to 9 × 10 -6 µm -1 . This corresponds to a maximum radius of curvature of 111mm. Unlike cables-in-conduit, the shape of the related distributions is multimodal where each mode is centered on the local curvature of the corresponding concentric layer of strands. Each mode appears to be well separated from the others. Whereas we expect to get an increasing local curvature as the concentric layer becomes large, it seems to be only partially true. A possible explanation is the existence of slightly dierent twist-pitches among these layers.

Rutherford cables

In Fig. 11, we have compared the distributions of several damage indicators (local curvature, CMPN and EF) of two Rutherford cables presenting a dierent length and number of strands: 18RRPN01 and 40RRPR02. Notice that the yaxis of all images is in log-scale to ease the analysis of results. In contrast to the other types of cables studied, the local curvature appears to be much larger (due to the folding of the cable), up to 2.75×10 -4 µm -1 . This corresponds to a radius of curvature of 3.63mm. Moreover, the distribution of all indicators share the same shape. More precisely, the head of these distributions corre- Finally, the correlations between all the above indicators have been computed. The most relevant couples of indicators were selected as those having an absolute correlation coecient above 0.8. These correlations have permitted to conclude that EF and CMPN are the most correlated ones. The obtained correlations between local curvature and strand sections compression indicators also conrmed that bendings and compressions locations coincide quite well with a coecient of about 0.7 in absolute value.

CONCLUSION

This paper presents a segmentation and geometry analysis of three types of cables and is, to our knowledge, the rst one to provide methods and results to this aim. The segmentation results exhibit a good accuracy w.r.t. manually provided ground truth. The features appear to be relevant for detecting deformations such as crushing or bending. The results are now going to be analyzed. We have found, for instance, that s.c. and n.s.c. strands exhibit dierent distributions of the crushing-related features. Similarly, no spatial correlation between crushing and bending was found. A further statistical analysis of the results will be done in the future.

Figure 1 :

 1 Figure 1: Cross-sectional images from cables-in-conduit (a,b), power cables (c) and Rutherford cables (d,e).

Figure 2 :

 2 Figure 2: Steps for extracting the cores (a-g) and the strands (h-l) from an image of a Rutherford cable (COP-RRP). The source image is rst denoised by an ASF (a). Once (a) lled (b), it is subtracted from (a), giving (c). An intermediate result (d) is obtained by thresholding (c). A mask (f) is built by thresholding (b) (giving (e)) and applying a morphological erosion on the result (f). (f) is then intersected with (d) and the 3D Nsc largest connected components are kept. The resulting components are labeled and correspond to the cores (g).A region-growing algorithm is then used to extract the laments zone, based on geodesic distance maps whose amount of regularity is controlled by a parameter α (h). The impact of α after region-growing is shown when it is small (i), moderate (j), large (k). The strands are obtained by expanding the laments zone with α = 0 (l).

Figure 3 :

 3 Figure 3: Steps for segmenting the conduit (a-d), the s.c. strands (e-h) and the n.s.c. strands (i-l) from an image of a cable-in-conduit (N22). The source image is rst denoised by an ASF (a). Next, (a) is ltered by a Gaussian and thresholded (b). Holes are lled in (b) by various morphological operations (c). An ellipse is then tted on (c) and adjusted on the inner contour of the conduit (d).Once the conduit obtained, (a) is thresholded from the source image (e), dilated and lled (f). Using (d) and (f), kernels are obtained by applying a watershed algorithm (g) on the source image. S.c. strands (h) are then extracted by expanding (g) (same approach as Rutherford cables with α = 0) and subtracting the complement of (d). Finally, n.s.c. strands are extracted with α > 0 (j-l), constrained by (d) and (h) but from the strands centroids f the previous image (i).

Figure 4 :

 4 Figure4: Steps for segmenting the conduit (a-d) and the strands (i-l) of a power cable (mgb2_113). First, the source image is thresholded (a) and lled (b). From (b), the largest connected component is discarded and a morphological opening is applied (c). An ellipse is tted on (c) and adjusted on the inner contour of the conduit (d). Second, the source image is denoised by an ASF (e) and thresholded (f). The complement of (d) is subtracted from (f) and a morphological opening is applied (g). 3D connected components that do not spread all along the cable are removed (h). The Euclidean distance to the contours of (h) is computed, ltered by a Gaussian (i) and maxima are identied (j). Strands contours are obtained by applying a watershed (l) on an image (k) combining the morphological gradient of the source image and the inverted distance map to ideal contours from maxima.

Figure 5 :Figure 6 :

 56 Figure 5: Example of constrained hierarchical clustering for identifying the the stages of the cable-inconduit N05 at the beginning (top row) and the end (bottom row). (a): initialization of rst stage, (b): result -rst stage petals (triplets), (c): initialization of second stage, (d): result -second stage petals.

Figure 8 :

 8 Figure 8: Validation of the strand section compression indicators on the N25 cable. Orange and green triangles are resp. normal and compressed locations along the same strand. On top row, the sections contours are superimposed on source images. Red circles are locations where partial scans have been registered.

Figure 9 :

 9 Figure 9: Distributions of damage indicators for s.c. (pink), n.s.c. (blue) and both (black thick line) strands along the cables-in-conduit N05 (top row) and N25 (bottom row). The y-axis of FTA and FTS is in log-scale.

  by 2.93mm (3.25%) and do not exceed 9.38mm (7.5%). Despite the randomness injected in these cables, this result demonstrates that twist-pitches remain close to nominal values.Additionally, we have computed the correlations between local curvature and strand sections compression indicators. Then, we have decided to retain the most relevant couples of indicators for which the absolute value of the correlation coecient is larger than 0.8. Not surprisingly, EF and CMPN are well correlated. But most importantly, no correlation have been identied between locally elevated curvature and other indicators, meaning that bendings and compressions locations do not coincide.Moreover, we have compared in Fig.9the distributions of several damage indicators (local curvature, CMPN, EF, FTA and FTS) of two cables-in-conduit that present dierent lengths, void fractions and twist-pitches: N05 (top row) and N25 (bottom row). The distribution of FTS is obtained by thresholding FTA at 15%, which appears to be a good value to keep signicant transversal moves. For each image, we provide both the distribution over s.c. (pink), n.s.c.

Figure 10 :

 10 Figure 10: Distributions of the local curvature κ along the power cables mgb2_113 (top) and mgb2_133 (bottom) for s.c. strands (pink), n.s.c. strands (green, blue, orange, cyan, resp. from outer to inner stages) and all strands (black thick line).

Figure 11 :

 11 Figure 11: Distributions of the local curvature (top row), CMPN (middle row) and the elongation factor (bottom row) along the Rutherford cables 18RRPN01 and 40RRPR02. For the purpose of visualization, the y-axis of all images is in log-scale.

Table 1 :

 1 Image characteristics (top) and physical parameters (bottom) of the cables-in-conduit (left to the double bar) and power cables (right to the double bar).

	N05 750 × 800 × 12431 12 6.94 Number of s.c./n.s.c. (all) strands 30/15 (45) 15/30 (45) 30/15 (45) N22 N25 750 × 850 × 750 × Image size (x,y,z) 12424 750 × 7745 Resolution (µm) 12 12 Memory usage (GB) 7.37 4.05 Strand (µm) 800 800 800 Avail. sample length (µm) 149172 149088 92940 Twist-pitch sequence (mm) 45/85/125 45/85/125 35/65/110 First triplet (s.c.,n.s.c.) (2, 1) (1, 2) (2, 1) Cable pattern (3, 3, 5) (3, 3, 5) (3, 3, 5) Void fraction (%) 25 33 33	mgb2_113 1200 × 1200 × 5972 10 8.1 24/37 (61) 1130 59270 227 / / 24.7	mgb2_133 1300 × 1605 × 6071 10 12 24/37 (61) 1330 60710 260 / / 24.7

Table 2 :

 2 Image characteristics (top) and physical parameters (bottom) of the Rutherford cables.

	Image size (x,y,z) Resolution (µm) Memory usage (MB) Number of strands Strand (µm) Avail. Sample Length (µm)	COP-RRP 1500 × 300 × 1300 15 558 40 1050 19500	18PITN01 750 × 1100 × 1200 10 945 18 1020 12000	18PITN01_2 1600 × 500 × 1200 6.75 916 18 1000 8100	18RRPN01 1100 × 750 × 1200 10 945 18 1050 12000	18RRPN01_2 1700 × 700 × 1200 6 1434 18 1046 7200	40RRPR01 1600 × 500 × 1200 15 916 40 1080 18000	40RRPR02 1500 × 500 × 1200 15 859 40 1035 18000

Table 3 :

 3 Accuracy of the segmentation procedures with respect to ground truths for several metrics. The keyword "all" gathers the contours of s.c. and n.s.c. strands as well as the contours of the conduit (if need be). .77 ± 1.04 8.11 ± 1.91 -7.47 ± 2.171.60 ± 0.28 3.73 ± 0.97 0.59 ± 0.36 n.s.c.95.47 ± 1.31 8.63 ± 2.35 -3.04 ± 2.89 1.85 ± 0.41 5.04 ± 1.63 1.22 ± 0.84 s.c.+n.s.c.95.63 ± 1.18 8.35 ± 2.14 -5.44 ± 3.35 1.72 ± 0.37 4.33 ± 1.47 0.88 ± 0.70 Conduit 99.67 ± 0.06 0.67 ± 0.12 -0.07 ± 0.

			DC (%)	VOE (%)	RVD (%) RMSD (pixels) MD (pixels) CD (pixels)
		s.c.
	In-conduit
					23	1.69 ± 0.17	5.16 ± 1.15	/
		all	95.72 ± 1.31 8.18 ± 2.39 -5.33 ± 3.41	1.71 ± 0.36	4.34 ± 1.47	/
		s.c.	97.86 ± 0.51 4.18 ± 0.97 1.06 ± 1.69	1.62 ± 0.21	4.54 ± 1.03 0.86 ± 0.48
		n.s.c.	97.99 ± 0.44 3.93 ± 0.84 -0.87 ± 1.53	1.57 ± 0.23	4.27 ± 1.02 0.83 ± 0.43
	Power	s.c.+n.s.c. 97.94 ± 0.47 4.03 ± 0.90 -0.11 ± 1.85	1.59 ± 0.22	4.38 ± 1.03 0.84 ± 0.45
		Conduit 99.80 ± 0.10 0.39 ± 0.20 0.38 ± 0.22	2.10 ± 0.35	7.06 ± 3.43	/
		all	97.97 ± 0.52 3.97 ± 1.01 -0.10 ± 1.84	1.60 ± 0.23	4.42 ± 1.16	/
	Rutherford	s.c.	94.44 ± 1.19 10.52 ± 2.13 -0.99 ± 3.10	2.45 ± 0.74	6.49 ± 2.56 1.39 ± 1.05
	(a)		(b)		(c)	(d)	(e)

95

Table 4 :

 4 Comparison of experimental and nominal values of void fraction for all cables-in-conduit (top) and all power cables (bottom).

		Measured void fraction (%)	Nominal void fraction (%)
	N05	24.16 ± 0.19	25%
	N22	30.28 ± 0.16	33%
	N25	33.13 ± 0.14	33%
	mgb2_113	27.57 ± 0.38	24.7%
	mgb2_133	27.09 ± 0.41	24.7%

Table 5 :

 5 Comparison of experimental and nominal values of twist-pitches for all cables-in-conduit.

	Cable Stage	Twisting Period	Experimental twist-pitches (mm)	Nominal twist-pitches (mm)
			1	43.81 ± 1.46	45
		1	2	87.95 ± 2.52	90
	N05		3	131.57 ± 5.89	135
		2	1	83.10 ± 6.00	85
		3	1	129.06 ± 0.00	125
			1	43.92 ± 1.26	45
		1	2	87.82 ± 2.24	90
	N22		3	131.77 ± 3.63	135
		2	1	82.22 ± 2.80	85
		3	1	115.62 ± 0.00	125
	N25	1	1 2	35.84 ± 1.13 72.93 ± 2.48	35 70
		2	1	61.89 ± 1.49	65

The segmentation of cables-in-conduit require initial manual markers.

From here, the z-axis will refer to the longitudinal one while x,y axes will refer to transversal ones.

ε > 0 5 . Second, the derivatives are approximated by standard nite central dierences. Due to the 5 ε is w.r.t. the precision of the implementation.

1 * This work was funded by the ANR project ANR-GUI-AAP-05 (20132017) and performed during the post-doctoral research project of Nicolas Lermé at the Centre for Mathematical Morphology.


Adrià Arrufat

Anne-Flore Perrin

Pierrick Philippe

IMAGE CODING WITH INCOMPLETE TRANSFORM COMPETITION FOR HEVC

Keywords: Transform coding, orthogonal transforms, sparse data representation, image coding

Overcomplete transforms have received considerable attention over the past years. However, they often suffer from a complexity burden. In this paper, a low complexity approach is provided, where an orthonormal basis is complemented with a set of incomplete transforms: those incomplete transforms include a reduced number of basis vectors that allow a reduction on the coding complexity and ensure a certain level of sparsity. The solution has been implemented in the HEVC standard and compression gains of around 1% on average are reported while reducing the decoder complexity in about 5%.

INTRODUCTION

Sparse data representation has been an important field of study in the last years thanks to its countless applications in many domains, in which, compression and feature extraction stand out.

Sparse representation focuses on finding the most compact representation of a given signal [START_REF] Huang | Sparse representation for signal classification[END_REF]. Amongst them, the K-SVD is one way of designing overcomplete dictionaries to achieve sparse data representation [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF].

The usage of multiple complementary transforms to provide sparse representations has been addressed in previous work [START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF] where the high computational requirements were pointed out: this motivates the work carried out here. In this paper, a low-complexity solution for sparse representation is proposed. The approach is based on a standard orthogonal transform, the discrete cosine transform (DCT), in competition with multiple elementary sparse transforms called Incomplete Transforms. The competition exists in the sense that the encoder selects, for each image block, the transform that provides the best signal representation in the distortion-sparsity plane.

The effectiveness of the approach is first measured using a sparsity metric that serves to design effective incomplete transforms based on a learning algorithm. The incomplete transforms are subsequently implemented in High Efficiency Video Coding (HEVC), the state-of-the-art image/video coding standard, defined in January 2013 [START_REF] Sullivan | Overview of the High Efficiency Video Coding standard[END_REF].

This paper is organised as follows: section 2 describes the main idea and the motivation to use incomplete transforms. Section 3 proposes a design method for this kind of transforms, which have been implemented HEVC and the results are discussed in section 4.

PRINCIPLES OF INCOMPLETE TRANSFORMS

In this paper, the concept of incomplete transforms is introduced. They can be considered as a special case of sparse orthonormal transforms [START_REF] Sezer | Sparse orthonormal transforms for image compression[END_REF] in which only one basis vector is retained and considered: consequently, a signal that has been transformed using an incomplete transform has only one coefficient different from zero in the transform domain.

In order to be able to represent any signal within a given distortion, incomplete transforms are conceived to work as companions of a main orthogonal transform, such as the DCT for image coding.

To illustrate a case where incomplete transforms can be useful, figure 1 presents a two-dimensional scenario, where the small dots symbolise the 2D signals to be transformed.

The main transform, whose basis vectors are v 0 and v 1 , is able to represent the signal in a very efficient way, as v 0 follows the main direction of the dark dots. By construction v 1 is orthogonal to v 0 .

However, there exists a secondary direction that cannot be represented compactly using the (v 0 , v 1 ) basis: both axis are needed to describe their coordinates. Just by adding an extra axis (w 0 ) adapted to this secondary direction, an effective and sparser representation of those dots can be achieved.

Therefore, the dots plotted in this space can be represented efficiently thanks to the union of two basis. One basis is complete, the second one, which can be conceived as a complete basis, is restricted to only one axis, the principal component: in this way, the compactness is guaranteed as only one transform coefficient need to be transmitted.

If only one adapted transform had been used in figure 1 to adapt to all those points, such as the Karhunen-Loève transform (KLT), the main axis would have been placed some-

w 0 v 0 v 1
Fig. 1: Illustration of the incomplete transform concepts. An additional basis vector (w 0 ) is added to assist an orthogonal transform (v 0 , v 1 ) where in between v 0 and w 0 , which would not provide sparse representation of the signal.

A remarkable consequence of using incomplete transforms is a decrease in complexity when decoding a signal, since there will be one coefficient different from zero, the decoding implies only one basis vector of the incomplete transform multiplied by this coefficient.

In image coding, a separable two-dimensional transform writes:

X = A • A • x T T = A • x • A T (1)
Assuming the image is composed of 8 × 8 blocks, x stands for the 8 × 8 pixels, and X their frequency representation. A is the 8 × 8 1D transform. The usual transform used in image coding is the DCT, whose fast algorithm requires 12 multiplications and 29 additions per 8 × 1 vector. As 8 vectors per block need to be processed both for the vertical and horizontal transform, processing an 8 × 8 block requires a total of 192 multiplications and 464 additions. This number of operations is identical for the inverse transform.

For an incomplete transform, only one axis needs to be processed: each axis being formed by 64 values in this example. Consequently, only 64 multiplications and 63 additions are need to transform the input block x into the transform domain. For the inverse transformation, only 64 multiplications are needed.

As a result, in this case, the incomplete transforms can be applied with an number of operations of approximatively one third of the cost of regular separable transforms. This complexity reduction benefits both the encoder and the decoder.

It is also worth noticing, that those incomplete transforms are non-separable and, therefore, able to exploit any linear correlation amongst pixels within a block. Separable transforms, on the other hand, are only able to exploit correlation of pixels sharing the same row or column.

DESIGN OF INCOMPLETE TRANSFORMS

The incomplete transform design is based upon the sparse orthogonal transforms model proposed and detailed in [START_REF] Sezer | Sparse orthonormal transforms for image compression[END_REF]. The original method describes how to derive one optimal transform iteratively for some training data and an initial transform by using a metric that includes a sparsity constraint.

In this paper, this method has been further adapted to handle incomplete transforms.

Incomplete transform learning

The method proposes a weighted rate-distortion metric that is able to provide different trade-offs. This metric includes a measure of the distortion in the mean square error sense of the quantised samples and a sparsity constraint, as explained below.

A opt = arg min A ∑ ∀i min c i x i -A T c i 2 2 + λ c i 0 (2)
Where x i is signal from the training set, e.g. a block of pixels reshaped into a N 2 × 1 vector, X i = A • x i are the transformed coefficients using the transform A and c i are the quantised transformed coefficients. A T is the inverse transform, since A is chosen orthonormal.

The constraint in the cost function is the 0 norm of the coefficients, i.e. the number of non-zero coefficients, also called the number of significant coefficients. Finally, λ is the Lagrange multiplier.

The equation 2 is minimised in two steps. First, the optimal coefficients are obtained by hard-thresholding X i . Afterwards, the transform is updated given the hard-thresholded coefficients c i and the x i . A detailed resolution of this equation is described in [START_REF] Sezer | Sparse orthonormal transforms for image compression[END_REF], as well as the relation between λ and the hard-thresholding parameter.

The algorithm iterates over the two steps until the metric converges.

The design of an incomplete transform takes one extra step: one and only one coefficient is kept after hardthresholding, the first one. Consequently, only X 0 is considered and the level of sparsity is guaranteed as c i 0 = 1. This makes the incomplete transform to have only one meaningful basis vector.

Therefore, for a given set of training signals, one obtains a transform consisting of one meaningful basis vector. The remaining vectors, albeit constituting a basis, are useless for the aim of the paper.

Multiple incomplete transforms

Since incomplete transforms are designed with a strong sparsity constraint of the quantised coefficients, it seems reasonable to generate several incomplete transforms to be able to adapt to different signal natures. However, an incomplete transform cannot represent accurately a signal provided a desired level of fidelity (e.g. a distortion criterion).

Consequently, the purpose of this paper is to complement a set of incomplete transforms with a standard orthogonal transform, such as the DCT.

As a result, a coding scheme based on such an approach is able to compress a signal at any quality level and might be able to be efficient sparsity-wise thanks to the incomplete transforms.

A learning algorithm and classification algorithm based on the metric defined in equation 2 has been implemented to design a set of 1 + N transforms: N incomplete transforms that complement a standard orthogonal transform, the DCT.

In order to design multiple transforms, an additional learning step is required: this consists in a classification step in which each learning signal is assigned to the transform, complete or incomplete, that provides the best representation in a rate distortion sense.

The rate distortion metric is consistent with the one defined in equation 2 and its purpose is to assign a signal x i to the transform A n that minimises the value:

δ n = x i -A T n c i,n 2 2 + λ c i,n 0 (3)
To this end, the representation of any signal x i is computed for all transforms A n , delivering a set of X i,n , subsequently quantised into c i,n . The quantisation operator is the hardthresholding function presented before, but only the first frequency coefficient is retained for the incomplete transforms. Therefore, the sparsity constraint, i.e. the second half of equation 3 equals to λ for the incomplete transforms and proportional to the number of significant coefficients for the DCT.

Once the learning signals have been classified given a set of transforms, each incomplete transform is updated using the learning algorithm of section 3. The classification/transform update steps are repeated until convergence.

Note that only transforms A 1 to A N are updated while A 0 (the DCT) is also considered in the classification step.

To illustrate the effectiveness of the algorithm, figure 2 presents how the increase of the number of incomplete transforms is able to provide a more sparse representation of the signal. To evaluate this, the average number significant coefficients is computed at a similar distortion level for different coding configurations (from 1 to 32 incomplete transforms used in conjunction with the DCT). The results are presented relative to the reference system which consists of a coding system using the DCT alone, such as HEVC.

As the number of incomplete transforms is increased, the proportion of significant coefficients is decreased to 66% of The result of a learning experiment is shown in figure 3, where 32 8 × 8 incomplete transforms are presented. For each one, only the first basis vector is displayed, since is the only one delivering significant frequency coefficients. In the case of two-dimensional signals, like images, incomplete transforms can be directly interpreted as texture patterns.

The learning set in this experiment is made of prediction residuals extracted from a directional mode from the HEVC coding scheme. The selected mode (intra prediction 6) is an angular prediction of approximatively +26 • . Accordingly, the blocks selected by HEVC for this mode mostly present a directional pattern following that direction.

It can be observed how the incomplete transforms have patterns containing that particular direction, each exhibiting a particular band-shaped pattern. Note that the DCT requires a significant number of coefficients to represent such directional, and inherently non-separable, patterns.

APPLICATION TO IMAGE CODING

The usefulness of incomplete transforms has also been applied to a practical environment, more precisely, inside the HEVC, the latest video coding standard, which is considered as the most performing image coder as of today [START_REF] Hanhart | Subjective Evaluation of Higher Dynamic Range Video[END_REF].

To evaluate the coding performance of the approach, a set of incomplete 8 × 8 transforms is designed for each HEVC intra prediction mode. At the encoder, for each block, the best prediction mode/transform pair is selected.

The conventional HEVC work flow is used except for two changes:

1. The signalling of the selected transform is requested. A flag + index approach has been retained here for its simplicity. If the DCT is selected, 0 is signalled, otherwise a flag is set to 1 and a fixed-length codeword indicates the incomplete transform index.

2. As the incomplete transforms retain only the first coefficient, the position of the last significant coefficient does not need to be conveyed.

Experiments have been performed following the common test conditions described in [START_REF] Bossen | Common test conditions and software reference configurations[END_REF] for an established test set (independent from our learning set). Sequences have been coded in all intra (AI) mode, meaning that each image is coded independently.

As specified in the test conditions, the improvement are presented as percentage of bit rate reduction relative to the HEVC coding scheme, using the Bjøntegaard Distortion-rate (BD-rate) metric [START_REF] Bjøntegaard | Calculation of average PSNR differences between RD-curves[END_REF].

Table 1 shows that around 1% of bit-rate reduction with regards to the HEVC standard can be achieved using this technique. There are some sequences which present notable gains over HEVC, such as SteamLocomotiveTrain and BasketballDrill. This is due to the large amount of diagonal patterns in those sequences, which are hardly handled by separable transforms like the DCT.

Complexity-wise, the proposed system is much more attractive that the previous one from [START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF], where regular nonseparable transforms are tested in the HEVC rate-distortion optimisation loop, which lead to a complexity of around 8 times the one from HEVC [START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF]. Using incomplete transforms leads to a complexity 2.7 times higher than that of HEVC. On the decoder side, complexity has been decreased due to the reduction in the number of operations with regards to the DCT when using incomplete transforms. Whilst the previous system increased the decoding complexity by 30% [START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF], the incomplete transforms reduce the decoding time in 5% on average. Keeping in mind that the transform does not represent the whole decoding process and that the DCT is still used, complexity reductions affecting the transform are moderate.

CONCLUSIONS

This paper has proved the effectiveness of incomplete transforms. When used as complementary transforms, they are able to increment the sparsity of the signal in the transform domain. The number of non-zero coefficients has been reduced to around two thirds of its original value. First experimental results on the HEVC-based image coder prove that incomplete transforms can be used to obtain some compression gains, 1% on average and up to 6% bit-rate reduction is achieved, with a slight decrease of the decoding complexity.

Fig. 2 :

 2 Fig. 2: Percentage of non-zero coefficients referred to the DCT

Fig. 3 :

 3 Fig. 3: List of 32 incomplete transforms for 8 × 8 blocks

Table 1 :

 1 BD-rate savings referred to HEVC

		Sequence	Y BD-rate
		PeopleOnStreet	-0.64%
	Class A	Traffic	-0.68%
	(2560 × 1600)	NebutaFestival	-0.91%
		SteamLocomotiveTrain	-5.25%
		BasketballDrive	-0.99%
	Class B (1920 × 1080)	BQTerrace Cactus Kimono1	-1.06% -1.38% -0.31%
		ParkScene	-0.15%
		BasketballDrill	-6.22%
	Class C	BQMall	-0.66%
	(832 × 480)	PartyScene	-0.18%
		RaceHorses	-0.44%
		BasketballPass	-0.47%
	Class D	BQSquare	-0.25%
	(416 × 240)	BlowingBubbles	-0.21%
		RaceHorses	-0.32%
	Class E (1280 × 720)	FourPeople Johnny KristenAndSara	-1.07% -1.25% -1.15%
		Average	-1.18%