Mȃdȃlina Hodorog

Bernard Mourrain
email: bernard.mourrain@inria.fr

Josef Schicho
email: josef.schicho@oeaw.ac.at

An Adapted Version of the Bentley-Ottmann Algorithm for Invariants of Plane Curves Singularities

Keywords:

We report on an adapted version of the Bentley-Ottmann algorithm for computing all the intersection points among the edges of the projection of a three-dimensional graph. This graph is given as a set of vertices together with their space Euclidean coordinates, and a set of edges connecting them. More precisely, the three-dimensional graph represents the approximation of a closed and smooth implicitly defined space algebraic curve, that allows us a simplified treatment of the events encountered in the Bentley-Ottmann algorithm. As applications, we use the adapted algorithm to compute invariants for each singularity of a plane complex algebraic curve, i.e. the Alexander polynomial, the Milnor number, the delta-invariant, etc.

Introduction

Computational geometry algorithms are used in many applications domains, such as robotics, computer vision, computer aided design, geographic information systems, etc. One of these algorithms, i.e. the Bentley-Ottmann algorithm for reporting the pairwise intersections among a set of objects in the plane, proved itself useful in many applications from combinatorial geometry and computer graphics. A generalized version of the Bentley-Ottmann algorithm [START_REF] Bieri | An On-Line Algorithm for Constructing Sweep Planes in Regular Position[END_REF] computes the pairwise intersections among geometric objects in R d . The Bentley-Ottmann algorithm uses a sweep technique, i.e. a sweep plane (or a sweep line in R 2 ) sweeps the space R d (or R 2 ) that contains a set of geometric objects. At certain positions called event points, the sweep is interrupted and the problem is locally solved. The sweep is greedy, without any backtracking.

In this paper, we propose an adapted version of the Bentley-Ottmann algorithm [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF] for computing all the intersection points among the edges of the projection of a 3-dimensional graph. In addition, the adapted algorithm computes some extra information on each intersection point and on the pair of edges that contains it. For our purpose, the adapted Bentley-Ottmann algorithm operates on a 3-dimensional graph data structure, which represents the piecewise linear approximation of a closed and smooth space algebraic curve, implicitly defined as the intersection of two algebraic surfaces. We compute this space algebraic curve as the link of the singularity of a plane complex algebraic curve, as described in [START_REF] Hodorog | A Symbolic-Numeric Algorithm for Genus Computation[END_REF].

We manage the adapted version of the Bentley-Ottmann algorithm in a simpler way than in the original version because the 3-dimensional graph has some special properties [START_REF] Diestel | Graph Theory[END_REF]: (i) it consists of several cycles; (ii) it is a regular graph, i.e. it contains no loops or multiple edges; (iii) and its projection contains at most one crossing point. The first two properties are always guaranteed since the 3dimensional graph represents the piecewise linear approximation of an implicitly defined space algebraic curve, which is closed and smooth (i.e. it does not intersects itself). We perform a test to check whether the third property holds for the given 3-dimensional graph and if the test fails, then we report a failure message. Using the free algebraic geometric modeler Axel [START_REF] Wintz | Axel Algebraic Geometric Modeler[END_REF] we compute efficient and robust results.

For our purpose, the adapted Bentley-Ottmann algorithm offers essential benefits: it allows us to compute the Alexander polynomial of the singularity of a plane complex algebraic curve as reported in [START_REF] Hodorog | A Symbolic-Numeric Algorithm for Computing the Alexander Polynomial of a Plane Curve Singularity[END_REF]. From the Alexander polynomial we compute other invariants of the singularity, e.g. the Milnor number and the delta-invariant. In this way, we recover topological local information on each singularity of a plane complex algebraic curve. Thus we can use the adapted algorithm to solve a specific problem from algebraic geometry, i.e. the problem of computing several topological invariants for each singularity of a plane complex algebraic curve. These topological invariants play an important role in the classification and the analysis of the singularities of a plane complex algebraic curve as discussed in [START_REF] Arnold | Singularities of Differentiable Maps[END_REF].

Description of the Algorithm

Data Structures

For our study, we define a 3-dimensional graph data structure as follows: E , where V is a list of points (vertices) in the 3-dimensional space together with their Euclidean coordinates, and E is a list of edges connecting them, i.e. V = {p(x, y, z) ∈ R 3 } and E = {e(i, j)|i, j ∈ V }.

Definition 1 A (3-dimensional) graph is defined as a pair G = V,
We are interested in the following elements of a 3-dimensional graph: Definition 2 A point (or vertex) in the 3-dimensional graph is a 4-tuple of the form p(index, x, y, z), where index ∈ Z uniquely identifies each point in the We introduce the following notations: (i) we use xycoord(index) for denoting the x, y coordinates of index and ycoord(index) for denoting the y coordinate of index; (ii) we access the i-th component of a list sw with the underscore notation for the index i, i.e sw i . We consider that the indexes of a list start from 0.

We recall that a path in the 3-dimensional graph is a sequence of consecutive edges in a graph, and a cycle (circuit) is a path which ends at the vertex it begins. In addition, a loop is an edge that connects a vertex to itself, and multiple edges are two or more edges connecting the same two vertices, see [START_REF] Diestel | Graph Theory[END_REF] for details.

We assume that the 3-dimensional graph is simple (regular), i.e. it has no multiple edges or loops as in Figure 2. For our purpose, we are interested in the projection of a 3-dimensional graph which always consists of several cycles, see Figure 3(b) for an example. We consider the edges of a 3-dimensional graph G to be "small" edges, i.e. the projection of any edge of G has at most one crossing point. If this property is not true for a certain pair of edges from a 3-dimensional graph, then we report a failure message during runtime. Remark 1 The 3-dimensional graph that we study in this paper represents the piecewise linear approximation of a closed and smooth implicitly defined space algebraic curve. We define this curve as the link of the singularity (0, 0) of a plane complex algebraic curve C, which characterizes completely the topology of the curve C around its singularity (0, 0). For instance, in Figure 3(b) we visualize the link of the singularity (0, 0) of the plane complex algebraic curve defined by the squarefree polynomial x 3y 3 = 0. In the literature [START_REF] Alcazar | Computation of the Topology of Real Algebraic Space Curves[END_REF], [START_REF] Liang | Subdivision Methods for 2d and 3d Implicit Curves[END_REF], the 3-dimensional graph computed as the piecewise linear approximation of an implicitly defined space algebraic curve is called the topology of the curve. We use the Axel [START_REF] Wintz | Axel Algebraic Geometric Modeler[END_REF] free algebraic geometric modeler to compute the 3-dimensional graph as presented in [START_REF] Hodorog | A Symbolic-Numeric Algorithm for Computing the Alexander Polynomial of a Plane Curve Singularity[END_REF], [START_REF] Hodorog | A Symbolic-Numeric Algorithm for Genus Computation[END_REF]. For the special case of smooth implicitly defined space algebraic curves, Axel uses certified algorithms to compute their topology.

We state the problem that we want to solve:

Problem 1 Given a 3-dimensional graph G = V, E as in Definitions 1 and 2, which has only "small" edges, which is regular and which consists of several cycles, our goal is to compute the intersection points among all the edges of the projection of G. In addition, we compute some extra information: (i) for each intersection point P find the pair of edges (e m , e n ) that contains it. (ii) the pair of edges (e m , e n ) is ordered, i.e. e m is under e n in R 3 .

Methods

To solve Problem 1, we first compute the intersection points of all the edges of the projection of a 3-dimensional graph, and for each intersection point, we compute the pair of edges that contains it. For this purpose, we design a sweep line based algorithm as the Bentley-Ottmann algorithm from [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF]. We distinguish several steps for our algorithm, that we describe in comparison with the original Bentley-Ottmann algorithm:

Step 1 (Ordering criteria). The edges of the projection of the 3-dimensional graph G are oriented from left to right and they are ordered in the list of edges E = {e 0 , ..., e N } as in Figure 4: (1) by the x-coordinates of their source points;

(2) if the x-coordinates of the source points of two edges coincide, then the two edges are ordered by the two slopes of their supporting lines; (3) if the x-coordinates of the source points and the slopes of two edges coincide, then the two edges are ordered by the y-coordinates of their destination points. The ordering criteria is necessary for the correctness of the algorithm.

e 0

? ? Step 2 (Sweep line paradigm). As in the Bentley-Ottmann algorithm, we consider a vertical sweep line l that sweeps the plane from left to right. While l moves, it intersects several edges from E, which are stored in a list denoted SW and that we call the sweep list. SW changes while l sweeps the plane and it is updated only at certain points of the edges from E called event points. In this algorithm, the sweep list SW is ordered by the y-coordinates of the intersections of the edges of E with the sweep line l. As in the Bentley-Ottmann algorithm, SW represents the status of the algorithm.

e 1 ! ! C C C C C C C X X X W W W z z z z z z e 1 = = { { { { { { { e 0 + + X X X X X X X X e 0 7
Step 3 (Sweep line management). We observe that in E each index appears two times since E always contains several cycles. This allows us to manage SW in a simpler way in our adapted Bentley-Ottmann algorithm than in the original version. While we traverse E, we insert the current edge e m (s m , d m ) from E in SW in the right position and that is: (1) we search for an edge e n (s n , d n ) in SW such that its destination coincide with the source of e m ∈ E, i.e. d n = s m ; if we find such an e n ∈ SW we replace it with e m ∈ E; (2) if such an edge e n ∈ SW does not exist, we insert e m in SW depending on its position against the current edges from SW . We assume SW = {e i 0 , e i 1 , e i 2 , ..., e i k }, with e i q ∈ E for all q ∈ {1, ..., k}. There exists a unique index j with 0 ≤ j ≤ k such that ycoord(s m ) is larger than the y-coordinates of all the intersections of e i 0 , ..., e i j with l, and smaller than the y-coordinates of all the intersections of e i j+1 , ..., e i k with l. This index j can be found by checking all the signs of the determinants constructed with (xycoord(s m ), 1), (xycoord(s i j ), 1) and (xycoord(d i j ), 1). Then we insert e m in SW between the two edges e i j and e i j+1 and we obtain SW = {e i 0 , e i 1 , ..., e i j , e m , e i j+1 , ..., e i k }. When we insert an edge from E into SW on the right position, we have to additionally update SW depending on the encountered event points:

we test each inserted edge in SW against its two neighbors for intersection. If an intersection point P is found we report it together with the pair of edges that contains it. In addition, we swap the edges that intersect in SW . As opposed to the original Bentley-Ottmann algorithm after swapping the edges in SW , we do not test the edges against their new neighbors for intersections because we consider only "small" edges. -we test each inserted edge in SW against its two neighbors for common destination. In addition, when two edges are swapped in SW after reporting their intersection point, we test them against their new neighbors for common destination. Whenever we find two consecutive edges with common destinations we erase them from SW . As opposed to the original Bentley-Ottmann algorithm after deleting edges from SW , we do not test the new neighbors for intersection because we consider only "small" edges.

We notice that in the adapted Bentley-Ottmann algorithm we basically process the pre-ordered list of edges E in a for-loop in a way which makes the explicit use of a sweep list redundant.

Remark 2 We mention briefly a way to modify the adapted Bentley-Ottmann algorithm such that in the case of a 3-dimensional graph G with "long" edges (i.e. the projection of any edge of G has at least one crossing point), the algorithm would detect all the intersection points and would not only report a failure message at runtime. The main idea is to update the ordered list of edges E and the sweep list SW each time the algorithm reports an intersection point as follows:

if the algorithm reports the intersection point P (x, y) ∈ R 2 together with the pair of edges (e 1 , e 2 ) that contains P (x, y), then for i = 1, 2 we split each edge of intersection e i in two new edges e l i , e r i . The new vertices e l i are determined by the source point of e i and by the coordinates of P (x, y), while the new vertices e r i are determined by the coordinates of P (x, y) and by the destination point of e i , as described in Figure 5. Then we update the lists SW and E as follows: we replace the edges e i by e l i in SW , and we insert the e r i edges in E following the ordering criteria from Step 1, Figure 4.

In the following we assume that we have computed: (1) a list I = {(x i , y i ) ∈ R 2 } of the intersection points of all the edges of the projection of a 3-dimensional graph; (2) and a list EI of pairs of edges for I such that the i-th element of EI represents the pair of edges that contains the i-th intersection point from I. In the example from Figure 3(b), our adapted Bentley-Ottmann algorithm computes all the 6 intersection points together with the list of pairs of edges that contain these intersection points.

To solve Problem 1, we now have to order each pair of edges from EI depending on the Euclidean space coordinates of the intersection points from I. For instance, in Figure 6 we consider P (x, y) ∈ I the intersection point of the pair of edges (e 1 , e 2 ) ∈ EI. We order this pair such that the first component always lies under the second component in R 3 . We assume that for i = {1, 2} the source and the destination points of e i are A i (a i , b i , 0), B i (d i , e i , 0), which are the projections of

A ′ i (a i , b i , c i ), B ′ i (d i , e i , f i ) from R 3 .
To order the pair of edges we proceed as follows:

1. For i = {1, 2} we compute the equations of the support lines L i for the edges e i in R 2 . We use the determinant formula for the equations of the lines L i and we obtain:

L i (x, y) : det   a i b i 1 d i e i 1 x y 1   = 0 , (1)
and thus

L i (x, y) : (b i -e i )x + (d i -a i )y + a i e i -b i d i = 0 . 2.
We compute the coordinates z 1 , z 2 of P 1 (x, y, z 1 ) and P 2 (x, y, z 2 ) in R 3 as in Figure 6. As an example we compute z 1 (we proceed in the same way for z 2 ). Firstly we compute α 1 from

α 1 L 2 (A 1 ) + (1 -α 1 )L 2 (B 1 ) = 0 . (2)
Then we compute z 1 as 3 and we return the pair (e 1 , e 2 ) for P (x, y) (i.e. e 1 is the undergoing edge and e 2 is the overgoing edge for (e 1 , e 2 )); otherwise e 2 is under e 1 in R 3 and we thus return the pair (e 2 , e 1 ) for P (x, y) (i.e. e 2 is the undergoing edge and e 1 is the overgoing edge for (e 2 , e 1 )), as in the example from Figure 6.

z 1 = α 1 c 1 + (1 -α 1 )f 1 . 3. If z 1 < z 2 then e 1 is under e 2 in R

Applications of the Algorithm

Our main goal is to compute the topological invariants for each singularity of a plane complex algebraic curve. For this purpose, it is essential for the adapted Bentley-Ottmann algorithm to compute the extra information on each detected pair of edges that contains an intersection point, i.e. to order the edges as described in Subsection 2.2, Figure 6 such that we distinguish the undergoing Additionally, we compute all the cycles of a 3-dimensional graph [START_REF] Hodorog | Computational Geometry and Combinatorial Algorithms for the Genus Computation Problem[END_REF]. For example, in Figure 8 we notice the 3 cycles of the graph data structure from Figure 3.

A ′ 1 (a1, b1, c1) B ′ 1 (d1, e1, f1) A ′ 2 (a2, b2, c2) B ′ 2 (d2, e2, f2) • P2(x, y, z2) P1(x, y, z1) A1(a1, b1, 0) B1(d1, e1, 0) A2(a2, b2, 0) B2(d2, e2, 0) • P (x, y) 2 2 d d d d d d d d d d d d d d d d d d d d d d d d -- [ [ [ [ [ [ [ [ [ [ [ e 1 2 2 d d d d d d d d d d d d d d d d d d d d d d d d d e 2 \ \ \ \ \ \ \ \ \ \ -- \ \ \ \ \ \ \ \ \ \
From this diagram and the cycles of the graph, we compute the Alexander polynomial of each singularity of the plane complex algebraic curve as presented in [START_REF] Hodorog | A Symbolic-Numeric Algorithm for Computing the Alexander Polynomial of a Plane Curve Singularity[END_REF]. Furthermore, from the Alexander polynomial we compute other topological invariants for the plane complex algebraic curve, i.e. the Milnor number, the delta-invariant of each singularity and the genus, as described in [START_REF] Hodorog | A Symbolic-Numeric Algorithm for Genus Computation[END_REF]. We implemented the adapted Bentley-Ottmann algorithm in GENOM3CK [START_REF] Hodorog | GENOM3CK -A Library for Genus Computation of Plane Complex Algebraic Curves using Knot Theory[END_REF], a library which was originally developed for GENus cOMputation of plane Complex algebraiC Curves using Knot theory. The library is written in the free algebraic geometric modeler Axel [START_REF] Wintz | Axel Algebraic Geometric Modeler[END_REF] and in the free computer algebra system Mathemagix [START_REF] Hoeven | Mathemagix Computer Algebra System[END_REF], i.e in C++ using Qt Script for Applications and Open Graphics Library. At present, the library is available for both Macintosh and Linux. More information about GENOM3CK (including documentation, download and installation instructions) can be found at http://people.ricam.oeaw.ac.at/ m.hodorog/software.html. For an example, see Figure 9, where we visualize the 6 intersection points among all the edges of the projection of the 3-dimensional graph from Figure 3 We give some reasons for motivating our choice to use Axel [START_REF] Wintz | Axel Algebraic Geometric Modeler[END_REF] for the implementation of the algorithms. The Computational Geometry Algorithms Library, CGAL [START_REF]CGAL -Computational Geometry Algorithms Library[END_REF], implemented in C++ is the standard library in the computational geometry community. The library provides data structures and algorithms that operate on geometric objects and thus it represents a good candidate to implement algorithms in computational geometry. Still for our purpose, the Bentley-Ottmann algorithm implemented in CGAL must provide for each detected intersection point the extra information on the reported pair of edges of intersection as discussed in Subsection 2.2, Figure 6. In our study, we compute the input data for the adapted Bentley-Ottmann algorithm (i.e. the 3-dimensional graph) using Axel as explained in Remark 1. Axel offers algebraic and geometric tools for computing the topology of smooth space algebraic curves as a 3-dimensional graph data structure in a certified way. To use directly this computed 3-dimensional graph and to obtain the essential extra information on each intersection point, we use Axel for the implementation of the adapted Bentley-Ottmann algorithm in a simplified form. Consequently, the adapted Bentley-Ottmann algorithm allows us to design more algorithms for computing the topological properties of each singularity of a plane complex algebraic curve as described in [START_REF] Hodorog | A Symbolic-Numeric Algorithm for Genus Computation[END_REF]. Another reason for the choice of the implementation system was that we wanted to write our package in one language, and we also needed algebraic functions for surfacesurface intersection, which are provided by Axel's libraries. To our knowledge, at present this is not implemented (yet) in CGAL.

Conclusion

We presented an adapted version of the Bentley-Ottmann algorithm for computing all the intersection points among the edges of the projection of a regular 3-dimensional graph, which consists of several cycles. We computed efficient and robust results using for the implementation free systems as Axel and Mathemagix. As applications, we use the adapted algorithm to solve a particular problem from algebraic geometry, i.e. the problem of computing the topological invariants for each singularity of a plane complex algebraic curve.

Fig. 1 .

 1 Fig. 1. An edge e(s, d) in a 3-dimensional graph. The edge e is determined by its source point A(s, x1, y1, z1) and by its destination point B(d, x2, y2, z2), where s, d ∈ Z uniquely identify the points A, B and (x1, y1, z1), (x2, y2, z2) ∈ R 3 are the Euclidean coordinates of A, B.

Fig. 2 .Fig. 3 .

 23 Fig. 2. (a) A graph with multiple edges. (b) A graph with a loop.

Fig. 6 .

 6 Fig.6. Ordering the pair of edges that contains an intersection point

Fig. 7 .

 7 Fig. 7. Diagram of the graph G from Figure

Fig. 8 . 3 4

 83 Fig. 8. The 3 cycles of the graph G from Figure 3

  (b).

Fig. 9 .

 9 Fig. 9. Implementation of the adapted Bentley-Ottmann algorithm in GENOM3CK

Acknowledgments. Many thanks to Julien Wintz, for the contribution to the implementation of the library in its starting phase and for creating the Axel software. This work is supported by the Austrian Science Funds (FWF) under the grant W1214/DK9. Bernard Mourrain is partially supported by the Marie Curie ITN SAGA [PITN-GA-2008-214584] of the European Community's Seventh Framework Programme [FP7/2007-2013].


Anirban Dhar
email: dhar@ufe.cz

Ivan Kasik

Bernard Dussardier

Ondrej Podrazky

Vlastimil Matejec

Preparation*and*properties*of*Er/doped*0r1 2* nanocrystalline*phase7 separated*preforms*of*optical*fibres*

The fabrication of Er-doped ZrO 2 -based nanocrystalline phase-separated silica optical preforms by the MCVD and solution doping techniques is presented. Fabricated preform cores are nearly transparent and contain phase-separated rare-earth doped nanocrystalline particles with diameters mainly in a range from 20 to 80 nm. High concentrations of erbium and aluminium in preform cores of about 0.3 and 14 mol%, respectively have been achieved without defects on the core-cladding interface. Spectral losses in a range 800-1600 nm and fluorescence spectra of erbium ions around 1550 nm measured on a fibre drawn from the preform are reported.

Introduction

Rare-earth (RE) doped optical fibres have been developed and successfully implemented in optical amplifiers and fibre lasers since late 1980. Among the different rare-earth ions; erbium (Er) has proved itself as one of significant candidates for applications in erbium-doped fibre amplifiers (EDFAs), one of revolutionary discoveries in the field of fibre optic telecommunication [START_REF] Mears | Neodymium-doped silica single mode fibre lasers[END_REF]. Since the discovery of the EDFAs, an extensive research has been carried out to improve spectroscopic properties of fabricated erbium-doped fibres (EDFs) in order to broaden the amplification bandwidth.

For achieving the fluorescence enhancement as high as possible different host materials other than pure silica, e.g. doped silica, phosphate glasses, telluride glasses, fluoride glasses, bismuth-based glasses doped with Er ions have been investigated [START_REF] Myers | High gain short length phosphate glass Erbium-doped fiber amplifier material[END_REF][START_REF] Luo | Optical properties of Er 3+ -doped telluride glasses with P 2 O 5 addition for 1.5 µm broadband amplifier[END_REF][START_REF] Waldmann | Erbium-doped fluoride glass waveguide[END_REF][START_REF] Harun | Experimental and theoretical studies on a double-pass C-band bismuthbased erbium-doped fiber amplifier[END_REF][START_REF] Fan | Broadband 1.5-µm emission of high erbiumdoped Bi 2 O 3 -B 2 O 3 -Ga 2 O 3 glass[END_REF]. These different host materials have shown their own advantages (wider emission, higher Er doping level etc.) but considering the practical applications in present telecommunication systems, silica based glass still has cutting edge over the other host materials due to its low loss, ruggedness, compatibility with other system components and low manufacture cost.

Therefore, one of new research directions is focused on fabrication processes of silica-based Er-doped optical fibres having properties of multicomponent glasses in order to control Er ion emission properties around 1.5 µm, a wavelength region which coincides with the lowest attenuation window of silica glasses. This research is aimed at incorporating of rare-earthdoped nanoparticles in fibres using a reliable and mature technology and taking the advantage of their spectroscopic properties to tune amplifiers characteristics, for example. For this purpose different techniques, such as co-sputtering [START_REF] Fujii | Photoluminescence from SiO 2 films containing Si nanocrystals and Er: Effects of nanocrystaline size on the photoluminescence efficiency of Er 3+[END_REF], laser ablation [START_REF] Nichols | Large-scale production of nanocrystals by laser ablation of microparticles in a flowing aerosol[END_REF], ion-implantation [START_REF] Chryssou | Evidence of energy coupling between Si nanocrystals and Er 3+[END_REF], pyrolysis [START_REF] St | Synthesis and characterization of discrete Luminescent Erbium-Doped Silicon Nanocrystals[END_REF], sol-gel technique [START_REF] Que | Luminiscence properties from erbium oxide nanocrystals dispersed in titania/organically modified silane composite sol-gel thin flims[END_REF][START_REF] Yeatman | Sol-gel fabrication of rare-earth doped photonic components[END_REF] and recently developed direct nanoparticle deposition (DND) technique [START_REF] Rajala | An industrial method for nanoparticle synthesis with a wide range of compositions[END_REF], etc, have been developed.

In spite of interesting achieved properties in fibres, most techniques suffer some drawbacks: low temperature glass fusion, or long and costy process, etc. Thus, it would be a challenging task to fabricate optical fibres with regions containing nanoparticles in rich-silica cores by using the conventional Modified Chemical Vapor Deposition (MCVD) process [START_REF] Li | Optical Fibre Communications Volume 1 Fibre Fabrication[END_REF][START_REF] Macchesney | MCVD: Its origin and subsequent developments[END_REF] combined with the solution doping technique [START_REF] Townsend | Solution doping technique for fabrication of rare earth doped optical fibers[END_REF]. Already some attempts have been made to study the properties of Er-doped nano-structured fibres completely produced by MCVD and the so-called solution doping technique [START_REF] Blanc | Erbium emission properties in nanostructured fibers[END_REF], containing amorphous calcium-phospho-silicate erbium-doped nanoparticles [START_REF] Acapito | Role of CaO addition in the local order around erbium in SiO 2 -GeO 2 -P 2 O 5 fiber preforms[END_REF]. Some interesting spectroscopic would also benefit from a nanocrystalline environment for the rare-earth ions.

In order to realize this task and develop so called Er-doped nanocrystalline phase-separated optical preforms for drawing optical fibres, it is necessary to select some dopants which allow nucleation processes and precise nucleation and growth control in the glass. Among different silica dopants available, namely ZrO 2 can be selected as host material for creating Er-doped nanocrystaline particles since it has many fold advantages. Particularly, the incorporation of ZrO 2 enhances the probability of radiative transitions through reducing glass phonon energy (~470 cm -1 ), ZrO 2 exhibit a boiling point (2300°C) higher than the drawing temperature of silica, has a high refractive index, good optical transparency and what is the most important, in the context of this paper, it can act as a good nucleating agent. Sol-gel process has been successfully used for incorporation of crystalline ZrO 2 in silica glass [START_REF] Brasse | Nanoscaled optical fiber obtained by the sol-gel process in the SiO 2 -ZrO 2 system doped with rare earth ions[END_REF].

The motivation of the presented work is based on the background summarized above. In this paper we are presenting results of systematic investigation and optimization of different fabrication stages employed for the preparation of Er-doped ZrO 2 -based nanocrystalline phase-separated optical preforms and fibres by using the MCVD and solution doping techniques. The paper deals also with detail characterization of preform samples and some of the initial results on fibre performances such as attenuation and fluorescence properties,which are necessary prerequisites for practical applications of the prepared fibres in amplifiers or lasers.

Experimental

Fabrication of preforms and fibres

The fabrication of an Er-doped ZrO 2 -based nanocrystalline phase-separated preforms of optical fibres consisted of two main stages, namely of the fabrication of a preform and its enhance the mechanical strength of the prepared glass and additionally increase the thermal mechanical strength and transparency of the glass similar to that of lithium-alumino silicate system [START_REF] Riello | Nucleation and crystallization behaviour of glass-ceramic materials in the Li 2 O-Al 2 O 3 -SiO 2 system of interest for their transparency properties[END_REF]. Doping with BaO was employed because this dopant possess good nucleating properties and additionally helps to prevent cracking caused by the volume expansion during ZrO 2 structural transformations at the preform thermal-treatment [START_REF] Cassir | Sythesis of ZrO2 thin flims by atomic layer deposition: growth kinetics, structural and electrical properties[END_REF]. After soaking the layer was dried in air and dehydrated in presence of chlorine. Subsequently, raw chemicals in the porous layer were oxidized and the layer was sintered to a clear glass layer by gradually increasing the temperature to around 1850°C. Finally, a solid rod, the preform, of diameter~ 10-10.5 mm was obtained through the viscous collapse of the tube with the layers deposited on the inner wall at a temperature above 2000°C.

5/20

The fabricated preform was thermally treated at a temperature around 1000°C in order to support nucleation and growth processes in the core. Fibres with diameters of 125±0.5 µm were drawn from thermally-treated preforms at temperatures around 2000 °C by using a conventional drawing tower (Special Gas Controls, GB) equipped with a graphite furnace (Centor, USA). A protective UV-curable acrylate jacket (De-Solite, NL) was applied onto the fibres during drawing.

Characterisation of preforms and fibres

Refractive-index profiles (RIPs) of the whole preforms were evaluated both before and after the thermal treatment using an A2600 preform analyser. Thin polished preform sections of a thickness ~ 1.5 to 2 mm were prepared to analyze core glass compositions and dopants distributions in the preform core using Electron Microprobe Analysis (EMA). Scanning

Electron Microscopy (SEM) (LEO-S430i) was used to investigate core-cladding interfaces of the fabricated preforms and presence of nanocrystalline-particle within the preform core region. For SEM analysis a sample about 0.8 mm long double-side-polished preform was prepared which was Ag coated (coating thickness ~200A). Samples for Transmission Electron Microscopy (TEM) analysis were also prepared to identify phase-separation and nanocrystals dimensions. These samples were prepared using two different approaches to identify the generation of nanocrystaline particles, their shapes and dimensions. In the first approach we polished a preform sample to a thickness of ~ 0.8 mm and then used Ar-ion mill thinning (~ to 10 µm) to achieve electronic transparency necessary for testing under High Resolution TEM. In the second approach chemical etching was carried out to remove the preform cladding and the extracted core (thickness ~ 1mm) was then crushed to powder. This powder was dispersed in acetone and applied onto a Cu saver for TEM tests. To determine the composition of phase-separated region and nanocrystalline particle formed the electron beam was focused on the selected spot over the investigated region, when the energy dispersive Xray diffraction (EDX) data were collected.

6/20

RIPs and fibre dimensions were measured using an S14 fibre analyser (York Technology, GB). Optical losses of the fibres in a range from 800 to 1600 nm were determined employing the cut-back technique [START_REF]Fundamentals of Fibre Optics in Telecommunication and Sensor Systems[END_REF]. A white light source was filtered by a computer controlled monochromator and coupled into a segment of the fibre under test. The output optical power P 1 (λ) from the fibre was measured, where λ is the signal wavelength.. Then a piece of the fibre of length L was cut at the output side of the fibre and the optical power P 2 (λ) from the fibre was measured again. The attenuation versus wavelength was determined from the general formula α(dB/m) = 10x log 10 [P 2 (λ)/P 1 (λ)]/L.

Fluorescence spectra of the fabricated fibres were also evaluated. The fluorescence measurement was carried out in the contra-propagative configuration using a 350-mW 978nm laser diode for the excitation of the fibre and a WDM coupler making possible to separate the excitation and fluorescence signals. A short fibre length was used (~14 mm) to avoid distortion by reabsorption and amplified spontaneous emission.

Optimisation of the fabrication process

In order to achieve the targeted core glass composition and designed preform properties, the optimization of different stages of the preparation process was carried out as it is described in following part.

The use of a suitable temperature of deposition of the porous layer is important since the porosity of the layer critically depends on this temperature and the porosity controls dopant incorporation levels in the preform core. This general experience can be specified as follows.

High layer porosities achieved at low deposition temperatures allow us to incorporate more dopants but the layer could peel off the tube wall during the solution doping stage, especially when high-viscous soaking solutions are used. On the contrary, the layer porosity and dopants incorporation is reduced at high deposition temperatures due to partial sintering of the deposited layer. Finally, the time duration of 45min was determined as the optimized soaking period.

After the solution doping stage, oxidation of the raw chemicals was carried out slowly around 900°C in pure oxygen, followed by dehydration around 700°C to avoid evaporation of Li 2 O from the porous layer in the form of LiCl due to reaction of Li 2 O with of Cl 2 .used for OH removal.

Sintering of the porous layer with the oxide dopants to a clear glass layer was carried out by a gradual increase of the temperature from 1050°C to 1850°C. This gradual temperature increase is essential to prevent sudden phase separations and reduce the possibility of dopant diffusion from the layer into the surrounding silica layers during the layer sintering.

8/20

After collapse of the tube with the deposited layers to the preform the heat-treatment stage took place. This treatment was performed in an electrical furnace which the preform was loaded in. To identify the suitable conditions for the formation of nanocrystalline particles within the preform core, a set of experiments with varied heat-treatment temperature, rate and time span was carried out. In each of these experiments a short section of the fabricated preform was heated at a temperature in a range of 850 to 1100°C and time span from 4 to 7 hours. TEM analysis and electron diffraction pattern of theheat-treated perform core indicates that suitable condition for formation of phase-separated rare-earth doped nanocrystalline particles is : temperature near 1000°C, time span of 5 hours where ramp rate to reach the target temperature was fixed at 7 °C/min. However, this temperature might vary with glass composition and not be considered as definite temperature for all glass compositions.

Results and discussion

Measured RIPs of the fabricated preforms before and after the thermal treatment showed that their numerical apertures (NA) related to the difference between refractive indexes of the core and the cladding, vary within 0.16±0.02. These values allow us to conclude that there is no essential effect of the heat treatment of the preforms onto their NAs. An example of a representative RIP measured on a preform at different angular projections is shown in Fig 1.

We have found that a RIP of a fibre drawn from the prepared preform is in a good agreement with that of the corresponding preform RIP. The core diameter of the fibre is around 12 µm provided the cladding diameter is 125 µm. It means that the fibre is not single mode at a wavelength of 1550 nm.

The composition of the preform cores prepared with the optimized soaking solution and evaluated from EMA measurements indicates high Al 2 O 3 incorporation of about 12-14 mol% in all prepared preforms. On the basis of such analysis determined with preciseness better than 0.1 mol% one could expected higher refractive index differences than those shown in The maximum concentrations for ZrO 2 and BaO are 0.9 and 0.2 mol%, respectively.

Concentrations of Er 3+ were also obtained from EMA measurements on the fabricated preforms and compared with those calculated from spectral attenuation curves of the drawn fibres (see an example in Fig. 7). These concentrations vary between 3000 and 4500 mol-ppm in different preforms and the EMA values agree within experimental errors with those measured on the fibres. Concentrations of Li could not be measured by EMA as lithium atoms are too light for this kind of analysis. However, as one can see from Fig. 4 the most of the nanocrystalline particles have diameters within the 20-80nm range. Although the size of these nanoparticles is-not uniform one can expect that it can be improved by finer optimization of the fabrication steps. To achieve this finer optimization, solution composition specially the ratio between Er/Zr salt will be varied further keeping other solution parameters fixed. Additionally longer annealing period is to be employed to achieve uniform particle size.

The electron diffraction pattern of the particles in the preform is presented in Fig. 5 clearly indicating the crystalline nature of the formed particles. SEM results in Fig. 6 show that the core-cladding interface is almost uniform in spite of the achieved high Al 2 O 3 doping. Such uniformity is not usually observed at preforms with high Al 2 O 3 contents prepared by the standard MCVD and solution-doping techniques [START_REF] Dhar | Elimination of core-clad interface problem in rare earth doped optical fiber[END_REF].

The preform core looks nearly transparent, however, the measured spectral attenuation curve (see Fig. 7) shows high base-line losses which may be either result of phase-separation within the preform core or due to formation of nanocrystalline particles which makes the core material non homogeneous. The presence of particles with diameters large than 50-100 nm in the preform indicate that scattering loss are expected in the fibre. Further work on the perform and fiber production process to lower the background loss to an acceptable value for application such as fiber amplifier.

The fluorescence of fibre drawn from nanoparticle doped preform has been measured in a wavelength region around 1550 nm, under 980-nm excitation at room temperature. The emission curve is shown in Fig. 8 together with the emission from a standard aluminogermano-silicate fibre. Both fluorescence curves have approximately the same shape, except for the shoulder around 1.55 µm: the fibre from the preform containing nanoparticles is slightly lower and some structured shapes are visible, whereas the alumino-silicate fibre has a smooth shoulder. It is out of the scope of this paper to discuss the spectroscopic differences.

Though we see that the luminescence from the nanoparticle doped fiber is much broaden compared to that from pure silica (not shown here): we have achieved to modify the close environment of the Er ions, as it is in a reference alumina-germano-silicate erbium-doped fiber, but using a different composition and structuration at a local nanometer scale. Further nanoscale analysis of the fibre structure as well as studies of refined spectroscopic details on these fibres are necessary to analyse whether the nanoparticles are present in the fibre and their effect of the rare-earth ions optical properties.

Conclusions

Er doped ZrO 2 -based nanocrystalline phase-separated preforms of optical fibres highly doped with Al 2 O 3 have been fabricated using the MCVD and solution doping techniques. The prepared preform cores are nearly transparent without defects on the core-cladding interface.

The presence of nanocrystalline particles inside the preform core has been observed with nonuniform particle size distributions and diameters within 20-400 nm. Initial results of measurements of fibre shows high base-line optical losses around 1300 nm explained by t strong light scattering on core inhomogeneities such as large nanoparticles or separated phases.

Acknowledgements

This research was supported by the Czech Science Foundation under contract P/102/10/554. M. Ude and S. Trzésien are acknowledged for fibre geometrical and absorption characterizations of the fibre. Authors are gratefully acknowledging fruitful discussions with other colleagues of IPE and LPMC.

From a set of

  initial experiments of deposition of porous layers we concluded that for preselected flow rates of starting SiCl 4 the optimum deposition temperature for the application of a porous layer was between 1250±10°C and 1290±10°C. We have found that an increase of the deposition temperatures above 1300°C makes porous layers more sintered leading to reduction of the dopant incorporation. On the other hand, a decrease of the deposition temperatures below 1210±10°C diminishes the adhesion strength of layers to the glass surface leading to enhanced chance of the layer delaminating during the solution impregnation stage.To optimize the solution composition, several preforms were fabricated under varying concentrations of the soaking solutions. During this optimization the following concentrations were varied in the following ranges, namely 0.015 to 0.05 M for LiNO 3 , 0.5 to 1.5 M for AlCl 3 , 0.015 to 0.05 M for BaCl 2 , 0.025 to 0.05 M ZrOCl 2 and 0.015 to 0.035 M for ErCl 3 .EMA results were used as the feedback for evaluating the glass compositions obtained from the fabricated preform samples. The optimized composition of the soaking solution was 1.25 M AlCl 3 , 0.035 M LiNO 3 , 0.05 M BaCl 2 , 0.035 M ZrOCl 2 and 0.03 M ErCl 3 . The time for contact of the porous layer and the optimized soaking solution was varied from 30 to 90min.

Fig. 1 .

 1 Fig.1. However, even a decrease of NA with an increase of AlCl3 in the soaking solution has

Distributions of Al 2 O 3 ,

 23 ZrO 2 and BaO concentrations in the preform core are presented in Fig 2. The Al 2 O 3 distribution in Fig.2 shows two distinct regions within the preform core; one which is rich in Al 2 O 3 (outside the central core region) and second with lower Al 2 O 3 concentrations (the central dip in Al 2 O 3 distribution). We presumed that central dip in the Al 2 O 3 distribution profile formed during the collapsing stage. During collapsing due to high temperature (>2000°C) appreciable volume change occurs as a result of transformation of three phases of ZrO 2 (cubic, tetragonal and monoclinic). This transformation associated with change in volume within preform core region and probably forces Al 2 O 3 away from central core region resulting central dip. Consequently, we could see two distinct phase separated region in Fig. 3a. Transmission electron image was taken from the extracted preform core (see details in Part 2.2.) and it is presented in Fig.3a. It indicates two different regions, namely Al 2 O 3 rich region (grey colour) and region rich in ZrO 2 (black colour). EDX analysis was carried out in different parts under investigation presented in Fig.3a and EDX spot analysis result from the ZrO 2 rich part is presented in Fig.3b.Dhar,Kasik , Dussardier , Podrazky,Matejec,Int.J.Appl.Ceram.Technol.,1-8(2011) DOI:10.1111/j.1744-7402.2011.00669.x 10/20 SEM results measured from the central core region of preform in Fig.4 revealed the formation of ZrO 2 nanocrystalline particles and characterized by diameters from 20 to 400 nm.

Figure caption:Fig. 1 :Fig. 2 :Fig. 3 :Fig. 4 :Fig. 5 :Fig. 6 :Fig. 7 :Fig. 8 :

 12345678 Figure caption:

Fig. 1 :

 1 Fig.1: refractive index profile of fabricated preform

Fig. 2 :Fig. 3 :

 23 Fig. 2: Dopant distributions in the preform core evaluated using EMA

Fig. 4 :Fig. 5 :

 45 Fig. 4: SEM image showing nanoparticle inside the central core region of the preform

Fig. 6 :Fig. 7 :

 67 Fig. 6: SEM image of the preform core and the core-cladding interface

Fig. 8 :

 8 Fig. 8: Normalized fluorescence curves from Er-doped fibres excited at 980 nm at


G Canat

J.-C Mollier

Y Jaouën

B Dussardier

Evidence of thermal effects in high power Er 3+ -Yb 3+ fiber laser

We analyse the influence of heat generation by non radiative transitions in high power 1.55µm double cladding Erbium-Ytterbium fiber laser. At strong pumping rates, 1µm lasing can start due to parasitic reflections. We present a model including heat generation and its effect on the Stark level population using the MacCumber relation. Heat generation plays then a significant role and improves the 1.5µm laser efficiency by increasing the 1µm threshold.

quantum defect between pump and laser photons, heat is generated into the active medium and thermal effects start to be significant in these lasers. Fibers take advantage of a much higher ratio volume / cross section than rods and disks frequently used in solid state laser. Heat generation in kilowatt Ytterbium fiber lasers has been previously studied [3].The quantum efficiency of Yb fiber laser is closed to 90% and these lasers were generally considered immune to thermal effects up to several kilowatts pump power [START_REF] Brown | Thermal, Stress, and Thermo-Optics Effects in High Average Power Double-Clad Silica Fiber Lasers[END_REF]. The theoretical efficiency of Er/Yb lasers is limited to 63 % but the actual efficiency typically between 30 % and 50%. It follows that a much larger amount of power is converted into heat. To the best of our knowledge, no work as yet been done on the effect of self induced heating in Erbium-Ytterbium codoped fiber laser. In spite of the large dissipation power of fibers, the core temperature can rise by several hundred of degrees. In this paper, we study the influence of self-induced heating due to pump absorption and its effect on lasing efficiency in Er 3+ /Yb 3+ co-doped fiber laser up to 100 W output power.

(note: pour éviter des confusions entre différents codopants (cas de yb et Er) et aider le lecteur, on note parfois les niveaux comme ceci: "Er: 4 I 13/2 ")

The Er/Yb system in silica involves absorption of pump photons between the Ytterbium manifolds 2 F 7/2 (fundamental) and 2 F 5/2 (excited). The energy is then resonantly transferred to the 3 Erbium 4 I 11/2 level which desexcites to 4 I 13/2 level. The lasing transition takes place between 4 I 13/2 and 4 I 15/2 levels. Due to the glass field, all these manifolds are split by Stark effect into sublevels (fig. 1). We have measured Er and Yb absorption and fluorescence on specially prepared singlemode phospho-alumino-silicate Er/Yb doped fibers. Even though the tail exhibits inhomogeneous broadening, the secondary emission peak is clearly visible at 1020 nm (fig. 2).

The emission beyond this peak is much larger than absorption when the Yb inversion is high, the net gain beyond 1030 nm is very high. At very high pump power, the residual reflections can thus lead to 1.06 µm parasitic lasing (plutôt 1015à 1025 nm?). This 1 µm threshold is lower when the cooperative energy transfer between Ytterbium and Erbium is not efficient enough.

Phosphorous doping is thus required to ensure short lifetime of the Erbium 4 I 11/2 and avoid back transfer to Ytterbium. Otherwise, this parasitic lasing effect can lead to gain clamping and power limitations for 1.5µm signal generation in Erbium-Ytterbium amplifiers and lasers.

The energy of the Stark sublevels of Yb were computed from the absorption and fluorescence measurements. Several works showed that Ytterbium lasers efficiency were quite sensitive to the fiber temperature [START_REF] Brilliant | Thermal effects in a dual-clad ytterbium fiber laser[END_REF][START_REF] Da Silva | Fourfold output power enhancement and threshold reduction through thermal effects in an Er3+/Yb3+codoped optical fiber laser excited at 1.064 µm[END_REF]. The absorption beyond 1030 nm is mainly caused by the transition b e (1030 nm) whose probability increases with the b level population following the Boltzman statistics. At room temperature, k B T~200 cm -1 . The population of level b is thus only 7% (fig. 1). At 400 K it grows up to 13%. The absorption in the long wavelength tail of Ytterbium can thus almost double when the fiber temperature increases by 100 K (fig. 2). The Erbium lasing transitions takes place between levels 4 I 15/2 and 4 I 13/2 which are split into 8 and 7

Stark sublevels respectively. The average Stark sublevel separation in each manifold is about 60 cm -1 . The population is thus almost evenly distributed at room temperature and Erbium crosssection are less sensitive to temperature variations than Ytterbium cross-sections.

4

Modeling of Er/Yb codoped lasers without temperature dependence has been described elsewhere [START_REF] Valley | Modeling Cladding-Pumped Er/Yb Fiber Amplifiers[END_REF][START_REF] Yahel | Modeling High-Power Er3+-Yb 3+ Codoped Fiber Lasers[END_REF][START_REF] Canat | Secondary energy transfer and nonparticipatory Yb3+ ions in Er3+-Yb3+ high-power amplifier fibers[END_REF]. The cross-relaxation transfer rates were taken from [11].We have implemented such a numeric model for lasers and amplifier study including computation of the fiber temperature due to the quantum defect and the effect of temperature rising on the initial crosssections. The power flow in the fiber is first computed using cross-sections at room temperature.

The fraction of power dissipated P diss by heating the fiber equals the absorbed pump power minus the signal powers generated at 1µm and 1.5µm (est-ce que ça inclut la fluo, qui est émise isotropiquement? Elle est probablement négligeable, mais on peut la mentionner). We assume that the heat flow is uniform along the fiber. The minimum heat flow dissipated Q in a given fiber cross-section is then estimated using

2 a L p Q diss    (1)
where a is the core radius, L the fiber length. The fiber temperature can then be computed using a simple cylindrical model with the following equations [3]

          2 1 ln 2 2 bh k a b k Qa T T air core (2a) bh Qa T T air clad 2 2   (2b)
where a is the fiber core radius, b is the fiber cladding radius and h=0.5 N u  A b -1 is the air convective parameter related to Nusselt number Nu computed from the Prandtl number Pr and Grasselt number Gr [START_REF] Brown | Thermal, Stress, and Thermo-Optics Effects in High Average Power Double-Clad Silica Fiber Lasers[END_REF]. The thermal conductivity k=1.38 W -1 m -1 is assumed to be the same for both glass and outer cladding. κ A = 0.026 W m -1 K -1 is the air conductivity. This is a conservative hypothesis since the outer cladding is usually prepared using a low index polymeric material with very low thermal conductivity.

When the fiber temperature increases, the high energy sublevels in each manifold (b-d and f-g) gets populated following the Boltzman statistics (fig. 1 1) Dernière remarque pas claire, ou confusion dans les "noms" de niveaux,. We therefore assume that the emission in this region will evolve with temperature as the occupation factor of level e given by 1/Z u were Z u is the upper partition function. To compute the evolution of the absorption when the temperature changes we use the Mac-Cumber relation which links the absorption and the emission (fig. 2) [START_REF] Brown | Thermal, Stress, and Thermo-Optics Effects in High Average Power Double-Clad Silica Fiber Lasers[END_REF].

T k h E Z Z B ZL l u e a      exp (5)
The zeroline energy E zl = 10256 cm-1, the upper Z u and lower partition functions Z l were computed using the Stark energy levels above. In order to scale the Er cross-sections we used the data from [12] which gives generalized Mac Cumber relations.

6

We applied this modeling to an Er/Yb laser at 1.55 µm similar to the 103 W laser reported by the Southampton group [1]. Parasitic lasing effects has been observed at the wavelength of maximum Yb gain: 90 W were generated at 1.06 µm versus 103 W at 1.56 µm.

Up to 350 W pump power at 975 nm were launched. This high pump power enters the domain where temperature effects can play a significant role. We assumed that the fiber had a 25 µm core and a 400 µm cladding, 60 dB/m Er core absorption, 6 dB/m Yb cladding absorption. The fiber reflectivity was 3.6% at at the pump end (perpendicularly cleaved) and -50 dB at pump wavelength (angle cleaved), 99% above 1520 nm (dichroic mirror) at the other end.

(mes remarques sur la figure 3 sont peut être fausses, car je ne vois pas les symboles sur la figure…) We can observe two kinds of behavior depending on whether the temperature dependence of cross-sections is taken into account or not (fig. 3). Without any temperature dependence, in the small pump rate region, the 1.5 µm power increases steadily. Above about 120 W of pump power, Yb lasing starts at 1060 nm and its population inversion is clamped. It follows that the Erbium population inversion is clamped too and the 1.5 µm output power is quickly limited to about 45 W (sur la figure je devine ~30W (?)). With temperature dependence, the fiber warms up due to pump absorption (figure 4a). For the cross-section scaling we assumed a uniform temperature profile along the fiber. A more detailed power balance allows from the cross-sections previously scaled to compute the local heat generation and temperature profile (fig. 4b???). (je n'ai pas vu d'indication concernant l'extrémité, gauche ou droite, par où la pompe est injectée). The temperature is maximum closed to the pump end with a slight decrease at the pump end due to strong 1um signal generation which reduces the amount of power dissipated. The hypothesis of temperature uniformity across the fiber tends to be inaccurate at very high pump rate. The fiber heating increases the absorption in the Ytterbium tail (fig. 2). The 1 µm lasing threshold is thus increased and the calculation agrees well with the experimental data with the exception of pump powers above 250 W. The discrepancy beyond 250 W may be due to the different approximations done. Suppression of the 3.6 % reflection at pump wavelength on one fiber facet would strongly reduce the 1 µm lasing and 1.5 µm roll-off.

In conclusion, we have demonstrated the influence of thermal effects in high power Erbium-Ytterbium double cladding fiber laser. Due to the pump fraction dissipated, the 1 µm co lasing threshold is increased (ou est-ce son efficacité (pente) qui a décru?) and the 1,5 µm rolloff is delayed (ce verbe ne me semble pas approprié: "shifted toward higher pump rates" serait mieux). Amazingly heat generation can lead to an increased output efficiency in the case of a Erbium-Ytterbium laser showing colasing at 1um and 1.5um. We underline that thermal modeling is thus required in 1.5 µm high power laser with output power larger than 100 W.

  ). The absorption beyond 1030 nm is mainly caused by the transition b  e (1030 nm) whose probability increases with the b level population. (déjà dit plus haut) The emission beyond 1030 nm is mainly caused by the transitions e  b (1030 nm), e  c (1087 nm) and f  d (1052 nm). However, the transition f  d is much weaker than e  b as the population of level e is only 4% at room temperature (fig.

Financial support for this 10 Figure 1 :

 101 Figure 1: Relative population of the upper (e-g) and lower (a-d) Stark sublevels of Ytterbium

Figure 2 :

 2 Figure 2: Evolution of the Ytterbium (left) and Erbium (right) absorption and gain with fiber

Figure 3 :

 3 Figure 3: Comparison between experimental values (from [1]) at 1.5 µm (■) and 1 µm (•) ;

Figure 4 :

 4 Figure 4: (a): evolution of the fiber temperature with the launched pump power assuming a

Figure 1 :

 1 Figure 1: Absorption (full line) and emission (dashed line) cross-sections of Ytterbium used in

Figure 2 :

 2 Figure 2: Relative population of the upper (e-g) and lower (a-d) Stark sublevels of Ytterbium

Figure 3 :

 3 Figure 3: Evolution of the Ytterbium (left) and Erbium (right) absorption and gain with fiber

Figure 4 :

 4 Figure 4: Comparison between experimental values (from [1]) at 1.5 µm (■) and 1 µm (•) ;

Figure 5 :

 5 Figure 5: (a) temperature distribution along the fiber for 350 W pump power (full line) and 200


Mathieu Ben
email: mathieu.ben@inria.fr

Guillaume Gravier
email: guillaume.gravier@irisa.fr

UNSUPERVISED MINING OF AUDIOVISUALLY CONSISTENT SEGMENTS IN VIDEOS WITH APPLICATION TO STRUCTURE ANALYSIS

Keywords: video mining, video structuring, multimodality, mutual information, clustering, content extraction

In this paper, a multimodal event mining technique is proposed to discover repeating video segments exhibiting audio and visual consistency in a totally unsupervised manner. The mining strategy first exploits independent audio and visual cluster analysis to provide segments which are consistent in both their visual and audio modalities, thus likely corresponding to a unique underlying event. A subsequent modeling stage using discriminative models enables accurate detection of the underlying event throughout the video. Event mining is applied to unsupervised video structure analysis, using simple heuristics on occurrence patterns of the events discovered to select those relevant to the video structure. Results on TV programs ranging from news to talk shows and games, show that structurally relevant events are discovered with precisions ranging from 87 % to 98 % and recalls from 59 % to 94 %.

INTRODUCTION

Video structuring is a crucial step in most video content analysis tasks with applications in archiving, browsing or re-purposing. Generally speaking, the structuring task consists in finding time stamps of events related to the underlying structure of an audiovisual material. From this general definition of structuring, two variants can be distinguished: (i) dense segmentation, where structural events explain the entire video, and (ii) detection of specific events relevant to the semantic or editing structure of the video, such as anchor shots, transition animated screens, advertisements, or goals in sport videos.

Many work have addressed event based video structuring using supervised approaches for which models-be they rule based, probabilistic or discriminative-are trained from manually annotated data. This supervised approach has been extensively used for anchor person detection [START_REF] Zhang | Video parsing, retrieval and browsing: an integrated and contentbased solution[END_REF][START_REF] Hauptmann | Informedia at TRECVID 2003: Analyzing and searching broadcast news video[END_REF][START_REF] Chua | Story boundary detection in large broadcast news video archives: techniques, experience and trends[END_REF] or event detection in sport videos [START_REF] Petkovic | Multi-modal extraction of highlights from TV Formula 1 programs[END_REF][START_REF] Wang | A generic framework for semantic sports video analysis using dynamic bayesian networks[END_REF]. However, such methods are poorly generic and lack robustness across genres and channels. Models have to be trained for each event considered or whenever an event changes appearance. Taking the example of anchor person shots, most approaches are highly specific of a particular channel or program and fail to generalize. As a mean towards generic and robust structural event detection, we propose a video mining technique to discover audiovisually consistent repeating segments among which those likely to be relevant to the editing structure of the video are selected.

Mining videos for repeating patterns has received attention over the past decade. Several approaches have focused on the discovery of near-duplicate repetitions [START_REF] Covell | Detecting ads in video streams using acoustic and visual cues[END_REF][START_REF] Herley | ARGOS: Automatically extracting repeating objects from multimedia streams[END_REF][START_REF] Jacobs | Using self-similarity matrices for structure mining on news video[END_REF] but cannot deal with the cru-cial issue of variability across repetitions. Since structurally relevant events are often characterized by their strong visual consistency, the problem of mining repeating structural elements has been addressed using clustering techniques (see, e.g., [START_REF] Clarkson | Unsupervised clustering of ambulatory audio and video[END_REF][START_REF] Divakaran | Video summarization using mpeg-7 motion activity and audio descriptors[END_REF][START_REF] Gao | Unsupervised video-shot segmentation and model-free anchroperson detection for news video story parsing[END_REF][START_REF] Wang | Unsupervised discovery of action classes[END_REF][START_REF] Ma | Unsupervised anchor shot detection using multi-modal spectral clustering[END_REF][START_REF] Broilo | Unsupervised event segmentation of news content with multimodal cues[END_REF]). But several problems arise from clustering, such as deciding the optimal number of clusters or dealing with outliers. This last point is particularly crucial since, in most cases, only those shots relevant to the structure exhibit similarity and should therefore be part of a cluster. Finally, models can be exploited to jointly discover structural events and the corresponding models [START_REF] Naphade | Discovering recurrent events in multichannel data streams using unsupervised methods[END_REF][START_REF] Clarkson | Unsupervised clustering of ambulatory audio and video[END_REF][START_REF] Xie | Unsupervised mining of statistical temporal structures in video[END_REF] but these approaches assume dense segmentation and cannot address the discovery of sporadic structural events.

This short survey of the literature points out two striking facts. Firstly, multimodality, in particular relations between modalities, is seldom exploited to discover events of interest and one rather assumes either visual or audio coherence. Secondly, apart from the dense segmentation case, most discovery techniques do not exploit models, in particular discriminative ones, which have proven highly efficient for event detection.

In this paper, a multimodal event mining technique is proposed to discover repeating video segments exhibiting audio and visual consistency. The mining strategy first exploits independent audio and visual cluster analysis to provide segments which are consistent in both their visual modality and their audio modality, thus likely corresponding to a unique underlying event. A subsequent modeling stage using discriminative models enables accurate detection of the underlying event throughout the video, automatically selecting positive and negative training examples from the output of the initial mining stage. This event discovery technique is applied to unsupervised video structuring, using simple heuristics on the occurrence patterns to select those audiovisually consistent events which are relevant with respect to the editing structure of the video.

The paper is organized as follows. The event mining stage is detailed in Section 2. Section 3 discusses selection of events relevant to the structure. Experimental setup and results are provided in Section 4 before concluding.

CROSS-MODAL DISCOVERY OF AUDIOVISUALLY CONSISTENT EVENTS

The cross-modal mining algorithm at the core of this work aims at discovering repeating events in the video with high audiovisual consistency across occurrences. The reason for this choice is that events with such characteristics are usually related to higher level information like the editing structure of a TV program or stream, which in turn often indicates a change in semantic content. The proposed method can discover multiple low-level audiovisual events among which the ones relevant to the structure will be selected based on simple rules as described in Section 3.

In this section, an overview of the method is first given before detailing the key components, namely, mining of candidate events and detection of those events using support vector machines (SVM).

Overview of the discovery method

Figure 1 schematically illustrates the various steps of the overall discovery method. Firstly, the soundtrack is segmented into homogeneous audio chunks. Similarly, the visual track is segmented into shots. For each modality, bottom-up clustering provides a hierarchical structure of nested clusters, known as dendogram, where each node in the dendogram represents a set of segments. To mine audiovisually consistent events, cross-modal consistency is measured between each pair consisting of one node from the audio dendogram and one node from the visual dendogram, the most consistent pairs defining candidate events. Note that this approach significantly differs from typical ones where the clusters of interest are selected from a fixed, unique clustering, be it monomodal or multimodal, using intra-clustering measures or heuristics. Finally, each candidate event is accurately detected using a SVM-based discriminative classifier trained in an unsupervised manner. To learn this classifier, positive and negative training samples are automatically selected from the results of the mining step, further exploiting cross-modality information. Note that, though not part of the mining algorithm itself, selection of candidate events relevant to the structure (grey box in Figure 1) might be performed between discovery and SVM detection for efficiency reasons that will be discussed in the Section 3.

Discovery of candidate events

Segmentation and clustering, independently performed in the audio and visual modalities, provide two dendograms where each node is a set of segments in the corresponding modality. Finding out a repeating event with high similarity in both its audio and visual content relies on a measure of the audiovisual consistency between a cluster of audio segments and a cluster of visual shots. Audiovisual consistency is measured using mutual information, a measure of the information shared by two random variables. Clearly, two inconsistent clusters should share little information.

Let us denote 𝐶 𝑥

𝑖 the 𝑖-th cluster for the modality 𝑥 ∈ {𝒜, 𝒱}, as defined by the 𝑖-th node of the corresponding dendogram. The mutual information between 𝐶 𝒜 𝑖 and 𝐶 𝒱 𝑗 is defined as

𝐼(𝐶 𝒜 𝑖 , 𝐶 𝒱 𝑗 ) = ∑ 𝑎∈{0,1} ∑ 𝑣∈{0,1}
𝑝(𝑎, 𝑣) ln

( 𝑝(𝑎, 𝑣) 𝑝(𝑎)𝑝(𝑣) ) (1)
where 𝑎 and 𝑣 are binary random variables indicating membership to 𝐶 𝒜 𝑖 and 𝐶 𝒱 𝑗 respectively. Practically the probabilities 𝑝(𝑎, 𝑣), 𝑝(𝑎) and 𝑝(𝑣) are estimated from the temporal segmentations. For example, the joint probability 𝑝(𝑎 = 1, 𝑣 = 1) is estimated as the amount of time jointly corresponding to a segment of 𝐶 𝒜 𝑖 and one of 𝐶 𝒱 𝑗 (dark grey area in Figure2), normalized by the total duration of the video. In other words, Eq. 1 indicates to what extent the segments in the audio cluster 𝐶 𝒜 𝑖 coincides with those of the shot cluster 𝐶 𝒱 𝑗 . Moreover, since clusters are selected from the dendograms, they exhibit a certain amount of homogeneity. These two facts guarantee that two clusters with high mutual information define audiovisually coherent segments.

The use of a cross-modal information measure has several invaluable advantages over conventional clustering methods. First of all, the problem of determining the best cluster-in our case, the one with the highest audiovisual coherence-is skirted. Indeed, conventional clustering approaches rely on somewhat arbitrary criteria to decide where to stop clustering. Moreover, among the resulting clusters, one has to find out the ones that best correspond to the application needs. By measuring the mutual information between all pairs of audio and visual clusters, these two problems are avoided. Another advantage of the cross-modal approach is that all possible pairs of clusters can be ranked from the more consistent to the less, thus providing multiple candidate events where conventional approaches usually output a single one. Having multiple solutions makes it possible to discover several characteristic events, for example, each guest in a talk show, and to filter out irrelevant ones using heuristic rules such as the one discussed in Section 3.

Note that, as the method explained above for the discovery of candidate characteristic events is fully based on a cross-modal measure of consistency, the work presented in this paper does not cover the case of audio-only or video-only repeats in the video. However such monomodal events could be searched for in a second step using appropriate techniques on a substantially reduced amount of data. image stream audio stream Fig. 2. Illustration of the combination of the audio and shot segmentations. Squared elements with diagonal filling denote, for each modality, the segments corresponding to the event selected. Dark grey regions define the intersection of the two segmentations where the event is present in both modalities, while light grey ones define the union where the event is present in either one of the modalities.

Unsupervised discriminative modeling

After the initial discovery step, a candidate event is characterized by a pair {𝐶 𝒜 𝑖 , 𝐶 𝒱 𝑗 }, with the corresponding temporal segmentations {𝑆 𝒜 𝑖 , 𝑆 𝒱 𝑗 }. Note that since segmentation and clustering are performed independently for each modality, 𝑆 𝒜 𝑖 and 𝑆 𝒱 𝑗 differs and must be combined to define the extent of the event under consideration, as illustrated in Figure 2. Early experiments have shown that taking segments occurring jointly in 𝑆 𝒜 𝑖 and 𝑆 𝒱 𝑗 (i.e., taking the intersection of the two segmentations) results in a high precision for the candidate event, however with poor recall. Oppositely, taking the union of the two segmentations increases recall while decreasing precision. The properties of the intersection and union of the two segmentations can be exploited to select positive and negative training samples in a totally unsupervised manner, so as to enable the use of a discriminative classifier in a final detection step. Following the idea that the intersection of the audio and video segmentations gives high precision, while their union gives high recall, the training samples were selected as follows.

First, an audiovisual segmentation of the video is constructed by merging the boundaries of the audio and visual segmentations. Each resulting segment, 𝑠 𝑘 , is described by an audiovisual feature vector ⃗ 𝐴𝑉 𝑠 𝑘 which consists of the concatenation of the two feature vectors ⃗ 𝐴𝑠 𝑙 and ⃗ 𝑉𝑠 𝑚 , describing respectively the current audio segment 𝑠 𝑙 and the current video shot 𝑠𝑚. Then, for an event characterized by the two clusters {𝐶 𝒜 𝑖 , 𝐶 𝒱 𝑗 } and the corresponding segmentations {𝑆 𝒜 𝑖 , 𝑆 𝒱 𝑗 }, the positive (+1 class) and negative (-1 class) training samples are selected according to

⃗ 𝐴𝑉 𝑠 𝑘 ∈ +1 if 𝑠 𝑘 ⊂ 𝑆 𝒜 𝑖 ∩ 𝑆 𝒱 𝑗 ⃗ 𝐴𝑉 𝑠 𝑘 ∈ -1 if 𝑠 𝑘 ∕ ⊂ 𝑆 𝒜 𝑖 ∪ 𝑆 𝒱

𝑗

In other words, vectors corresponding to the intersecting parts of 𝑆 𝒜 𝑖 and 𝑆 𝒱 𝑗 -a region where we expect low false positives-are chosen as positive training samples, while all those corresponding neither to 𝑆 𝒜 𝑖 nor 𝑆 𝒱 𝑗 -a region where we expect low false negatives-are selected as negative training samples. Here again, cross-modal information (i.e., A/V intersection and union segmentations) is fully exploited as a means to automatically select pseudo training samples from the originally unlabeled data.

Obviously, unsupervised selection of training samples cannot ensure that the training data is error free. Hence, training data are bound to contain false positive and false negative examples, which can be seen as outliers for their class. Support vector machines, known for their robustness to outliers, were thus used to model the data using a RBF kernel. Hyper-parameters were optimized in a unsupervised manner through a grid search with a 5-fold crossvalidation procedure on the training set. Finally, given the SVM trained with the optimal hyper-parameters, all segments in the video are classified as either corresponding to the event considered or not, thus terminating the entire discovery algorithm.

SELECTING RELEVANT EVENTS FOR STRUCTURE ANALYSIS

The discovery process finds audiovisually coherent events regardless of their relevance to some semantic information need. In the context of a particular application, re-ranking is needed to emphasize events of interest in this context. In the case of video structure analysis, not all audiovisually coherent events are relevant. For example, in a news show ending with a guest's interview, it was observed that the mining step ranked shots of the guest speaking as the most coherent event instead of the expected anchor shots which are much more relevant to the structure of the program. Thus minimal expert knowledge about the targeted event topology needs to be incorporated in the system at this point. One property of structural events is that they occur more or less regularly throughout the video and therefore spans the entire program. Based on this property, structurally relevant events should meet the following requirements in addition to audiovisual consistency: (1) span a large part of the program, (2) exhibit time regularity both in their duration and in their frequency, and (3) be sparse. Heuristic filtering rules are used to ensure these properties and to avoid partial discovery of events. Candidate events that do not span at least half of the program's duration as well as those with a single occurrence are discarded to fulfill requirement 1. Re-ranking the remaining events is done according to

𝑆(𝑘) = 𝑚 𝑠(𝑘) 𝜎𝑠(𝑘) 𝑚𝑖(𝑘) 𝜎𝑖(𝑘) (2)
where 𝑚𝑠(𝑘) and 𝜎𝑠(𝑘) are respectively the mean and standard deviation of the duration of the (discovered) occurrences of the 𝑘-th event, and 𝑚𝑖(𝑘) and 𝜎𝑖(𝑘) are the mean and standard deviation of the duration of the intervals between occurrences. The denominator term, related to requirement 2, benefits to solutions with high regularity in their appearance patterns. In the numerator, 𝑚𝑖(𝑘) enables sparsity while 𝑚𝑠(𝑘) aims at finding out the longest possible event, hence avoiding event splitting (i.e., an actual event whose occurrences are spread across two or more discovered segments). Note that event selection should ideally be performed at the end of the entire mining process. However, to avoid unnecessary and computationally demanding SVM training and classification steps, event selection was performed after the initial discovery step, considering only the 𝑁 most consistent events. After removing irrelevant events from the 𝑁 -best list of candidates, the remaining ones were sorted according to Eq. 2 and, in this work, only the best resulting event was further processed using SVM classification.

EXPERIMENTAL SETUP AND RESULTS

Experiments were carried out on a comprehensive data set including various types of TV shows. As no publicly available data set exists for such task, TV programs were recorded from various French television channels and segments corresponding to structural events were annotated by a human expert. We first describe the data and briefly present the video and audio segmentation and clustering algorithms used before discussing evaluation criteria and presenting results. Table 1. Description of the data set: #shows is the number of shows with a different name; #occs is the total number of occurrences; duration is the total duration over all occurrences.

Data set

Discovering structural events through audiovisual consistency in videos only makes sense for program genres in which such events are present. Evaluation is therefore performed on a selection of programs from the following genres: flash news, news, magazines, investigation reports, talk shows and games. The data set consists of a few shows for each genre, collected over various French television channels, as detailed in Table 1. A brief description of each genre and of the related key structural elements is provided below, key frames of typical events of interest being illustrated in Figure 3. News denote the classical news show where appearances of the anchor speaker(s) constitute the main structural event(s). Flash news are short news programs where no anchor speaker appears on screen. Rather, news items are separated by a typical computer-generated screen displaying the title of the next item with a jingle as background music. The variability between occurrences of the anchor event is less than for anchor person shots and mainly comes from the title of the news item.

Magazines denote news-like shows tackling non-news subjects. They are less formal than classical news shows in their structure, resulting in an increased variability of the structurally relevant events, and are therefore more challenging for mining purposes. Two different magazine shows are present in the data set: one consists of reports or interviews separated by sequences showing one or two anchor persons with various set-up (an example is shown in the leftmost column, bottom row of Figure 3) while the other one consists of journalists presenting sport news in turn, each news item being separated by a computer-generated screen.

Investigation reports are programs where a few topics are inves-tigated in-depth. As for news and magazines, they are presented by one or two anchor persons. In addition to variability, the challenge lies in the fact that anchor shots occur only a few times over a long period. Data were collected from three different programs with duration ranging from 1 hour to 2 hours, the longest one exhibiting two anchor persons. Finally, talk shows and games significantly differs from newslike contents and are much more challenging. In particular, such programs often exhibit several structuring events from an audiovisual standpoint. For example, in talk shows, a close-up of a particular participant is a structuring event that occurs several times across the program, roughly every time the participant is speaking.

Segmentation and clustering

Classical segmentation and clustering techniques were used to provide independent audio and visual dendograms.

Segmentation of the audio stream was performed using the Bayesian information criterion (BIC). Bottom-up agglomerative clustering is based on a variant of the BIC criterion to select the two closest clusters, where clusters are modeled using 16 component Gaussian mixture models [START_REF] Ben | Speaker diarization using bottom-up clustering based on a parameterderived distance between adapted gmms[END_REF]. Each audio cluster is characterized by a unique 528-dimensional feature vector gathering scaled versions of the 33-dimension mean vectors of the 16 Gaussian components.

The video stream is segmented into shots based on color histograms to detect abrupt changes and progressive transitions. Each of the resulting shot is summarized by a key frame, taken in the middle of the shot, in turn represented as a RGB histogram with 8 bins per color. Bottom-up clustering relies on the Euclidean distance between the 512-dimension color histograms using Ward's linkage.

The input samples of the SVM-based event detection module (see section 2.3) are thus 1040-dimensional audiovisual feature vectors, each resulting from the concatenation of the two feature vectors describing respectively the current audio segment and the current video shot.

Evaluation criteria

Evaluating mining algorithms raises two main issues: mapping the elements discovered to semantic events and evaluating the quality of the discovery job in regard of the mapping.

By construction, the mining process aims at finding out events with common low-level characteristics-in our case a strong audiovisual consistency-, in the hope that they correspond to some semantic event. Regarding editing structure analysis as the targeted application, ground truth for evaluation was constructed by systematically annotating all low-level events in the videos considered relevant from a structural viewpoint. Each event discovered is mapped to the best matching structural event in the ground truth to compute performance statistics. Note that, though discovering multiple events is possible with the proposed method, we did not considered this case and evaluation is limited to the discovery of a single event per program for sake of simplicity.

Given the occurrences of a discovered event and the occurrences of the best corresponding semantic event as annotated in the video, the quality of the discovery process is classically measured in terms of precision (𝑃 ), recall (𝑅) and 𝐹 1 measure. Precision corresponds to the proportion of discovered events actually corresponding to the mapped semantic event. Recall corresponds to the proportion of the semantic event actually included in the output of the discovery process. Precision and recall are computed on a time basis-as opposed

Results

Results are reported separately for each type of programs as defined in Section 4.1. Moreover, to illustrate the respective contribution of each step of the algorithm, results are reported for the structural audiovisual event discovery stage alone (mining+selection), and after SVM detection. For the sole discovery stage, segments for an event are defined as the intersection between the corresponding audio and video temporal segmentations (see discussion in section 2.3). All results are summarized in Table 2.

Qualitative analysis

Detailed analysis of the results has revealed that, when applying selection after the mining step, the best events selected were actually relevant from a structural viewpoint for all programs in the data set. This is not always the case when no selection is performed, thus proving the effectiveness of the requirements fixed to filter out irrelevant solutions for structure analysis purposes. For all flash news program, the computer-generated screens with an audio jingle separating the news items (middle and right-most samples in the top row of Figure 3) were systematically identified as the most structuring events. This was also the case for the sports magazine program. In the other magazine program where two anchor persons appear, shots showing the male anchor in a double screen set up (left-most sample in the bottom row of Figure 3) were returned by the algorithm. This shots actually are very relevant for the editing structure of the program as they correspond to the introduction of the coming report. For news and investigation programs, the most relevant events discovered correspond in all cases to occurrences of anchor person shots though sometimes partially retrieved. In the two investigation programs with two anchor persons, the algorithm focused on either one of the anchors, only returning occurrences of him/her speaking. Similarly, for the talk show program, the algorithm focused on appearances of one of the main guest speaking all along the program. Finally, for the game programs, the algorithm returned screens with a particular common visual set up and the same off-voice either presenting the participants, the coming game section or the gift given to the loosers at the end of a section.

Regarding computation time, programs were processed in half real-time (on a recent laptop), most of the computation (about 80 %) time being used for clustering audio and video segments.

Discovery step

In the 3 leftmost columns, results are reported after selecting the best event from the 𝑁 -best list provided by the initial discovery step using the heuristic described in Section 3. Clearly, the number 𝑁 of events retained from the discovery step results in a trade-off between the guarantee to select an audiovisually consistent event and the appropriateness of the solution with respect to the properties of structural elements. Too short a list guarantees audiovisual consistency but may not contain structuring events. On the contrary, a longer list might result in the selection of an event with good structuring properties but lacking audiovisual consistency. In these experiments, the list size was experimentally fixed to 𝑁 = 5 which globally gave the most satisfying results across all programs. Obviously, the optimal value of 𝑁 might be dependent upon the program's type. However, to keep the algorithm generic and keep the amount of supervision to a minimum, 𝑁 was fixed across all programs.

Results in Table 2 clearly confirm that the "intersection" solution indeed lead to discovering occurrences of structural events with a high precision. Across the various program types, precision ranges from about 90 % to 100 %. Recall, however, usually remains insufficient, in particular for investigation reports and talk shows for which 50 % is hardly achieved. The final SVM-based detection step aims at compensating this drawback.

Detection step

Results after the SVM detection step1 in the rightmost columns of Table 2, show systematic significant gains in recall with only minimal decrease in precision with respect to the discovery step. Recall values ranging from 47 % to 85 % after the discovery step are increased between 59 % and 94 % after unsupervised SVM classification. In particular performances are near perfect for the news programs, with a recall of 94 % and a precision of 95 % for the detection of close-up anchor shots. Exceptions are the game programs for which no improvement is obtained on the 𝐹 1 measure by the SVM-based detection step. These results validate the unsupervised selection of training data from the discovery step and shows that discriminative classifiers can be used in a totally unsupervised context in order to enhance the retrieving capacity of a discovery system, as long as an effective method for selecting training samples is used.

In spite of good results on several program types, progress are still needed to improve recall, in particular in difficult cases like the investigation programs where the audiovisual set-up may vary significantly.

CONCLUSION

A multimodal strategy for unsupervised mining of videos from audiovisually consistent segments was presented and applied to the discovery of events relevant to video structuring tasks. The use of multiple modalities to discover characteristic events enables to circumvent problems related to clustering in a single modality, in particular selecting the adequate stopping criterion and cluster. Rather, optimal clustering is found by comparing multiple audio and visual clusters as given by independent bottom-up hierarchical clustering in each modality. Experimental results show that this cross-modal mining step, associated to event selection, is efficient, yielding high precision however with insufficient recall. Recall is improved using discriminative models whose parameters are trained in a totally unsupervised manner, automatically selecting training samples from the initial mining and selection step.

From a more general standpoint, this work demonstrates the feasibility of unsupervised discovery of significant events for semantic tasks such as structure analysis. This opens numerous opportunities in the field of multimedia mining and content-based analysis. Indeed, the event discovery method discussed in the paper is in fact quite generic and not restricted to structure analysis. Mining is based on the general principle that events of interest share at least two common characteristics. In the framework of structure analysis, we limited ourselves to the two following characteristics: visual consistency-via color histograms-and audio consistencyvia speaker and sound class modeling. But any other characteristic could be used instead of, or in addition to, either one. For example, movement based clustering seems interesting for event discovery in sports video, while local visual interest points may probably allow clustering of shots with similar objects.

Finally, it was mentioned that the proposed mining method is not limited to the discovery of a single event and can provide a ranked list of characteristic events. We believe that this is a particularly interesting feature of the proposed cross-modal algorithm that has applications in many domains. Indeed, apart from news and flash news, most programs exhibit more than one structurally relevant event. Many news programs have two anchor persons. Magazines and talk shows often include guests which repeatedly appear throughout the show. Discovering multiple events is then necessary to reveal the structure of such programs. However, providing a ranked list of the N-best events is only a first step towards structure analysis from multiple events. In particular, selecting the relevant events among the N bests remains an open issue. How to ensure that there is no conflict in the discovery process, for example with SVM classification, is another one. Finally, accounting for multiple events in the structure probably requires expert knowledge on characteristic patterns of structural events.

Fig. 1 .

 1 Fig. 1. General principle of the proposed cross-modal discovery process. Note that the figure includes the selection of relevant events (in grey), which is not per se part of the mining process.

Fig. 3 .

 3 Fig. 3. Typical structural events. From left to right and up to down: anchor person in news, 2 flash news screens for 2 different programs, magazine anchor person, guest in a talk show, contestant presentation in a game.

Table 2 .

 2 Structural event detection performancesto an event basis-and, for each genre, performance measures are averaged across occurrences.

		Mining + selection	+ SVM detection
	Genre	𝑅	𝑃	𝐹1	𝑅	𝑃	𝐹1
	Flash News	0.57	1	0.71	0.76 0.98 0.85
	News	0.85	1	0.91	0.94 0.95 0.94
	Magazine	0.63 0.91 0.73	0.76 0.89 0.81
	Investigation	0.47 0.95 0.59	0.59 0.96 0.69
	Talk show	0.51 0.88 0.64	0.76 0.87 0.81
	Games	0.72 0.95	0.8	0.75 0.92	0.8

The publicly available libsvm implementation was used (C.-C. Chang and C.-J. Lin, LIBSVM: a library for support vector machines,

2001).

ACKNOWLEDGMENT

This work was partly funded by OSEO, French State agency for innovation, in the framework of the Quaero research program.

Many thanks to Mónica Corlay for doing the ground truth annotation work, and to Sébastien Campion for providing Python code for key frame clustering, as part of the PimPy library 2 .