Bingqing Qu

Félicien Vallet

Jean Carrive
email: jcarrive@ina.fr

Guillaume Gravier
email: guillaume.gravier@irisa.fr

CONTENT-BASED INFERENCE OF HIERARCHICAL STRUCTURAL GRAMMAR FOR RECURRENT TV PROGRAMS USING MULTIPLE SEQUENCE ALIGNMENT

Keywords: TV program structuring, hierarchical structural grammar, symbolic representation, multiple sequence alignment, unsupervised and multimodal approach

Recently, unsupervised approaches were introduced to analyze the structure of TV programs, relying on the discovery of repeated elements within a program or across multiple episodes of the same program. These methods can discover key repeating elements, such as jingles and separators, however they cannot infer the entire structure of a program. In this paper, we propose a hierarchical use of grammatical inference to yield a temporal grammar of a program from a collection of episodes, discovering both the vocabulary of the grammar and the temporal organization of the words from the vocabulary. Using a set of basic event detectors and simple filtering techniques to detect repeating elements of interest, a symbolic representation of each episode is derived based on minimal domain knowledge. Grammatical inference based on multiple sequence alignment is then used in a hierarchical manner to provide a temporal grammar of the program at various levels of details. Experimental validation is performed on 3 distinct types of programs on 4 datasets. Qualitative analyses show that the grammars inferred at the different levels of the hierarchy are relevant and can be obtained from a fairly limited number of episodes.

INTRODUCTION

The last decade has seen a rapid increase in multimedia content and large scale audiovisual archives are available for users and content providers. For instance, the French National Audiovisual Institute, a repository of French radio and television audiovisual archives, has more than five million hours of radio and television programs stored. However, such collections are useless in practice if they are not described and indexed so as to know what they contain and to provide easy access to a particular portion of their content. Therefore, indexing of such large-scale archives is indispensable for browsing, sharing and Internet diffusion.

In particular, program structuring, which this paper focuses on, is a crucial step for high-quality indexing. Especially, TV program structuring consists in obtaining a temporal segmentation of programs into their basic constitutive elements. Each program has its own way of being organized by editors. For example, TV news programs usually start with a brief outline of the reports, followed by an alternation of anchorperson's announcement of the upcoming topics and news reports. Most news programs end with interview segments, weather forecasts or program trailers. Program structuring aims at detecting the existence and the temporal boundaries, i.e., the start and end frames, of such constitutive elements, designated as the structural element, of the program. A structural element hence refers to a video segment with a particular syntactic meaning.

We focus on recurrent TV programs where program structuring is realized by leveraging the repetitiveness to discover recurrent structural elements from which to infer a temporal grammatical structure, i.e., structural elements and their temporal ordering. A recurrent TV program is a program with multiple episodes which are periodically broadcasted (e.g., daily, weekly), such as News, entertainments and magazines. Most of their episodes follow the same editorial structure: Structural elements appear in almost the same order with very similar duration, separated by certain short sequences (named separators) which repeat across episodes at similar time instants. However, different types of TV programs lead to diversity of program structures, so identifying such structural elements and separators is not a trivial task. In other words, the challenge lies in inferring grammatical structure with minimal prior knowledge about the program genre and the types of structural elements which may be present. Facing the challenge, based on a collection of episodes from the program, we discover elements relevant to the structure by means of repeatability of recurrent programs and infer the corresponding grammar. Thus a model of the structure of the program can be established to process additional episodes.

To achieve this goal, adopting an unsupervised framework of TV program structuring as presented in [START_REF] Qu | Using grammar induction to discover the structure of recurrent tv programs[END_REF], we propose a hierarchical architecture for grammatical inference based on multimodal structural elements. Specifically, the framework proposed in [START_REF] Qu | Using grammar induction to discover the structure of recurrent tv programs[END_REF] consists of three steps, i.e., generic visual event detection, structural element identification, basic grammatical inference. In this paper, we first extend the generic event detection and structural element identification approaches from the sole visual modality to audiovisual modality in order to increase the completeness of the program structure. We then adopt a top-down architecture for grammatical inference to obtain hierarchical structural grammars at different granularity, and integrate a sectional-aligned method where multiple sequence alignment techniques is piece-wise applied on grammar inference to ameliorate the disambiguity of the inferred grammar. The sectional-aligned method is the method that multiple sequence alignment techniques is applied to each of the per-determined intervals of a program while inferring grammars. The top-down architecture allows to infer diverse structural grammars from coarse-grain to fine-grain, and the sectionalaligned method provides more deterministic grammars by aligning shorter sequences.

The paper is organized as follows. Section 2 reviews the exist- ing techniques for TV program structuring. Section 3 explains the overall method and details each step of structural grammar inference for unsupervised TV program structuring. Experimental evaluations are reported in Section 4, followed by conclusions in Section 5.

RELATED WORK

TV program structuring has been extensively studied. Existing approaches can be classified in two categories, according to whether prior knowledge of structural elements is incorporated in program structuring or not.

Most previous studies on TV program structuring focused on the case where information on the structure is available as prior knowledge. Resorting on prior knowledge of the structure, research has targeted either on entire structure of the program (e.g., [START_REF] Bertini | Contentbased indexing and retrieval of tv news[END_REF], [START_REF] Li | Automatic detection and analysis of player action in moving background sports video sequences[END_REF]) by leveraging structure models learned from annotated data, or on typical structure elements (e.g., [START_REF] Hanjalic | Templatebased detection of anchorperson shots in news programs[END_REF], [START_REF] Gao | Unsupervised video-shot segmentation and model-free anchorperson detection for news video story parsing[END_REF]) by considering their inherent properties across diverse types of programs. Hidden Markov models have been widely used in the first case [START_REF] Xie | Structure analysis of soccer video with domain knowledge and hidden markov models[END_REF], [START_REF] Kijak | Audiovisual integration for tennis broadcast structuring[END_REF], while event detection has been applied to both cases. Most of these approaches are however supervised as they rely on the prior knowledge of the structure. They depend on genre of the program or type of the structural element.

As an alternative, another category of very recent approaches structures programs without prior knowledge of the structure. As not knowing the constituting structural elements, the structure of the program is discovered by means of event repetitiveness (e.g., visual recurrence [START_REF] Elma Abduraman | An unsupervised approach for recurrent tv program structuring[END_REF] and audio recurrence [START_REF] Muscariello | Audio keyword extraction by unsupervised word discovery[END_REF]), sequential model [START_REF] Qu | Using grammar induction to discover the structure of recurrent tv programs[END_REF], frequent pattern [START_REF] Jacobs | Using self-similarity matrices for structure mining on news video[END_REF] or audiovisual consistency [START_REF] Ben | Unsupervised mining of audiovisually consistent segments in videos with application to structure analysis[END_REF]. All these approaches are used for recovering the underlying structure of a program. The approaches of this category try to skirt supervised techniques and adopt minimal prior knowledge in order to preform unsupervised program structuring.

Work reported in this paper follows the last path and attempts at discovering the structural elements from a collection of episodes, along with a model for their sequential nature, thus targeting structure completeness and program type diversity.

HIERARCHICAL STRUCTURAL GRAMMAR INFERENCE

In this paper, we address the problem of inferring a hierarchical structural grammar for recurrent TV programs from a collection of episodes of the same program based on minimal prior knowledge. To avoid any confusion, we propose to use the term program to refer to a recurrent TV program and episode to refer to an exemplar of the program. A structural grammar consists of the set of structural elements composing each episode, and their temporal order. For example, reports and anchorperson's announcements are structural elements for a news program, on top of which a temporal model with occurrence probabilities can be built to form a structural grammar. To achieve the temporal model discovery, symbolic representation of structural elements is proposed for grammatical inference. Especially, in the absence of prior knowledge of which structural elements compose the program, we adopt the property of event recurrence across all episodes to determine the structural elements, represented as symbols, in an almost unsupervised manner. A structural grammar can then be inferred by multiple sequence alignment techniques.

We propose a three step approach as illustrated in Figure 1. Firstly, a set of broad scope events are detected within each episode by a number of audiovisual detectors. These events might be of interest as potential structural elements. In the second step, we assess the set of events detected along two lines. Role recognition is to identify the important persons of each episode, while density estimation is used to find events which recurrently occur at about the same instant in each episode. These two strategies are further used to assess repeatability of structural elements so as to help in deriving a symbolic representation by adopting minimal domain knowledge. Finally, we infer the hierarchical structural grammar of the program by leveraging multiple sequence alignment techniques, where a top-down and sectional-aligned architecture is adopted.

In the following subsections, we will detail each step of our approach.

Multimodal detection of broad scope events

In order to detect general purpose events which serve for discovering generic enough structural elements for different types of shows, a large number of event detectors should be adopted. Practically, considering a trade-off between the type of programs, the complexity at run time and implementation, a number of key detectors are applied.

Five visual detectors described in [START_REF] Qu | Using grammar induction to discover the structure of recurrent tv programs[END_REF] were applied. Shot detector and dissolve detector are utilized to detect shots. A monochrome image detector is used for detecting the most evident separators. Person clustering classifies people appearing in each episode into different groups, and shot reverse shot detector is applied based on person clusters. Shot reverse shot depicts shots alternating between two characters facing one another, which are usually engaged in dialog scene or some face to face interaction.

In this paper, four detectors are added to improve the completeness of program structure, where text detector and motion activity detector are based on visual content, and speech/music/silence detector and audio recurrence detector are based on audio content. Text detector aims at detecting and localizing text(-like) regions in images. Motion activity estimation is often associated with text region localization to detect still text scene. We adopt a block matching algorithm [START_REF] Barjatya | Block matching algorithms for motion estimation[END_REF] to estimate the motion activity in current frame with respect to the previous frame of a video. Speech/music/silence detector allows evidently to identify different types of audio sequences. Music might refer to songs, jingles, etc. Evident silences might appear in commercials segments, (before or after) separators, etc. Outlines for a program, i.e., a brief summary of the main points of a show, are mostly found when speech and music appear at the same time. Speech/music/silence detector is performed by the implementation described in [START_REF] Panagiotakis | A speech/music discriminator based on rms and zero-crossings[END_REF]. Audio recurrence detector, based on the MODIS software [START_REF] Catanese | Modis: an audio motif discovery software[END_REF], aims at detecting identical audio sequences, which allows to detect separators as they repeat within or among different episodes of a program.

Determination of structural elements

A considerable amount of events are detected in the first step, but they are not all relevant to the structure of recurrent programs. For example, a sequence of monochrome images connecting two parts of a game show is a separator while it can also be found in a night scene. In order to remove the spurious structural elements, this step addresses the determination of valid structural elements for the structure of a program, from which a symbolic representation of episodes is obtained. Determination of structural elements implements two complementary strategies: role recognition and density filtering.

Role recognition is adopted to further characterize the outcome of person clustering and identify important persons. We mostly focus here on the conductor, or anchor, role which is clearly a strong cue with respect to structure. Five different features are defined to characterize each person cluster, viz.: total duration of appearance; total number of distinct appearances, i.e., number of non consecutive segments; duration of the longest segment in which the person appears; time range between the first and last occurrence; duration in which the speaker is engaged in a dialog. To account for varying episodes and program lengths, all five metrics are scaled to [0, 1]. Decision on the dominant person is made based on the sum of the five normalized metrics. The cluster for which the sum is maximal is identified as the dominant person, as a dominant person is assumed to ideally take significant time of an episode.

Following the role recognition, density filtering is to analyze the temporal distribution of the events which repeat with relative temporal stability across episodes, i.e., valid structural elements. For instance, repeated short audio sequences with similar temporal position across episodes are considered as separators, while a long shot containing dominant person is supposed to be anchor's opening if it is found at the beginning for most episodes of the program. Valid structural elements are identified by taking advantage of the repeatability for recurrent TV programs, as they share relatively stable temporal structures across different episodes which have almost identical structural elements. For a collection of episodes from a program, we project the occurrences of each kind of detected events onto the same temporal axis, filtering out events which occasionally appear in some episodes by counting the number of occurrences. Temporal density analysis with a kernel function as follows is adopted to select the valid structural elements:

f (x; h) = 1 nh d n i=1 K( x -xi h ) (1)
where f (x; h) is the estimated density function, x is the data from which the density estimate is constructed, h is the bandwidth and K() is the kernel. A Gaussian kernel is used with optimal bandwidth automatically chosen [START_REF] Botev | Kernel density estimation via diffusion[END_REF]. An illustration for density filtering is given in Figure 2, where events in black are removed while the ones in gray are considered as structural elements because of their high temporal concentration. The property of repetitiveness of structural elements across episodes gives the explanation for structural elements selection based on thresholding of density function.

Top-down sectional-aligned structural grammar inference

Recurrent events determined in the previous step, are identified as structural elements by adopting minimal prior knowledge of TV programs. For instance, a structural element corresponding to a sequence of white frames is a separator, while a long duration shot containing the dominant person at the beginning of a program is the conductor's opening. As a result of structural elements determination, symbolic representation is derived. Each element is represented as an alphabet symbols, while each episode of a program can then be represented as a time-ordered sequence of symbols. The temporal stability of recurrent TV program structure results in similar symbolic sequences across episodes. However, slight differences still exist among different episodes. In order to infer a structural grammar for the program from such sequences, we adopt multiple sequence alignment techniques to discover the common pattern across symbolic sequences. Multiple sequence alignment techniques allow to align the symbolic sequences in the way that alphabet symbols, i.e., valid structural elements, in a given position are homologous, superposable or play a common functional role. We adopt the ClustalW algorithm explained in [START_REF] Ma Larkin | Clustal w and clustal x version 2.0[END_REF] as multiple sequence alignment tool. The process of grammar inference from a symbolic representation is illustrated in Figure 3 with three episodes. Symbols, i.e., SGCDY E, represent the valid structural elements that are identified. we mark that the alphabet letter for each structural element is chosen manually. A graphical representation of the resulting grammar is obtained using WebLogo [START_REF] Gavin E Crooks | Weblogo: a sequence logo generator[END_REF]. A stack of symbols is used to illustrate each position in the grammar: The height of objects within the stack indicates the relative frequency of each symbol while the stack width is proportional to the fraction of valid symbols in that position.

Comparing with the induced structural grammars in [START_REF] Qu | Using grammar induction to discover the structure of recurrent tv programs[END_REF] which are relatively concise, more complete structural grammars are in this paper inferred, since multimodal event detectors are applied to programs. Increased structural completeness and complexity leads evidently to more ambiguities for structural grammars in the process of multiple sequence alignment. To reduce the grammar ambiguity and infer grammars at different granularity, we propose hierarchical structural grammar inference with a top-down and sectional-aligned architecture. Firstly, separators are determined by filtering recurrent events whose durations are significantly short as well as adopting prior knowledge of most common separators, such as monochrome images and repeated audiovisual sequence. Based on separator determination, a coarse-grain grammar is obtained with only separators and chapters, i.e., video segments between two separators, whose Fig. 4. A top-down and sectional-aligned architecture for hierarchical structural grammar inference structural grammar is to be discovered. Secondly, the structural grammar of each chapter is inferred by leveraging the basic grammar inference explained in the previous paragraph, and a fine-grain structural grammar can be obtained. Moreover, we can still infer a grammar for each detected structural element if it can be decomposed into parts of different elements. Thus a finer-grain structural grammar can be obtained. The top-down and sectional-aligned architecture is illustrated in Figure 4. A program is firstly decomposed only into separators represented by Si and chapters represented by Ci. The grammars of each chapters are then inferred: The grammar of chapter C1 is composed of two structural elements A and B; the grammars of C2, C3 and C4 are also obtained. The structural elements are represented by different alphabet letters, i.e., ABCD..., where P stands for the entire program. At last, we can go deeper to discover the grammars of structural elements if any. For example, structural element C can be decomposed into alternation of elements M and N , therefore a detailed grammar can be inferred.

In short, a program is decomposed from coarse elements to greater details, i.e., top-down approach, and during each step of decomposition, grammars of different levels of elements are inferred, i.e., sectional-aligned approach. The sectional-aligned grammar inference replaces aligning long sequences of entire programs by aligning short sequences of certain segments of a program, which obtains a more deterministic structural grammars. Besides, grammars at different granularity from coarse grain to fine grain can be obtained at the same time.

EXPERIMENTAL RESULTS

Experiments are conducted on four recurrent programs from three different types, viz., game, news and magazine. We firstly demonstrate structural element determination. Then the qualitative analysis of inferred grammar is performed by varying the number of episodes used for grammar inference.

Dataset description

Four different programs, with 24 episodes each, are used for inference and evaluation, as given in Table 1. 20h News (NEWS), a daily news show of 2007, follows a very standard pattern for such programs. Two programs of type magazine, Telematin (MAGM) and Thalassa (MAGS), were taken with episodes selected from 1989 and 1997. MAGM is a morning program proposing news and topics about culture and daily life. Different topics of the program are separated by separators. MAGS is a magazine about sea stories, where a conductor leads the show which is composed of reports and discussions. Que le meilleur gagne (GAME) is a game show whose episodes were taken over two years (1991 and 1992). It has four parts divided by separators. The program, hosted by a conductor, mainly contains interview scenes and question/answer scenes with full text segments. While the same conductor appears in all the episode of GAME, more than two distinct conductors can be found for NEWS, MAGM and MAGS.

Performance of structural elements determination

A number of structural elements were determined from a scope of recurrent events with minimal prior knowledge. Different types of structural elements are presented in Table 2, where the corresponding event detectors of each structural element are listed. Specifically, if an event detector contribute to identifying a specific structure element, it is marked as "yes" or with its corresponding detected results.

As described in previous sections, density filtering is applied to find the recurrent elements across episodes. Some structural elements are determined by a sole event detector such as dialogs, music/songs or separators for NEWS, MAGS and MAGM. Some structural elements are discovered by more than two event detectors. In other words, the high temporal concentration of density functions of events are coincident. Person cluster results with long shot duration are used to find person's monologues, anchor person's monologues can also be found if we count in dominant person prediction. Besides, commercials are characterized by the presence of (any combination of) black frame, short shot duration and audio silence. In NEWS the outlines pronouncing the main topics in each episode always has short shot duration and anchor person's speech with back ground music. Effectiveness of structural element determination is detailed in [START_REF] Qu | Using grammar induction to discover the structure of recurrent tv programs[END_REF], where a high detection recall for structural elements are presented.

Hierarchical structural grammar inference

The inferred grammars are illustrated in Figure 5 for the four programs. Separators are firstly determined, and the coarse-grain grammars with separators and chapters are obtained. Chapter is represented as N , whose structural grammar is to be inferred. We denote separator as S for NEWS, MAGS and GAME since each of them have identical separators, while we denote different separators of MAGM as S,V ,F ,H,G,I,K because of diversity of its separators: The separators are found in different clusters of repeated audio sequences. We mark that although separators for both MAGS and MAGM are detected by audio recurrence, the difference is that the separators of MAGS belong to the same recurrent audio class while the separators of MAGM are found in different recurrent audio classes. For further discovery, based on the hierarchical method described in section 3.3, the chapters are then structured and finergrain grammars are inferred. For NEWS, illustrated in Figure 5(a), after determining the separators, we then determine the outlines. The segment after outlines, accounting for most time of the program, is From the grammars, the main syntax of GAME can be explained as: the game starts with an introduction (separator) followed by a dialog (between the anchor and the participants). We then have an alternation of person interacting (dialogs) and game phases (full screen texts), or one of them.

For MAGS, illustrated in 5(c), selected symbols are based on dominant person's monologue and dialog segments, yielding a relatively deterministic grammar. A continuous segment with long duration, denoted as N , is considered as a report while A and D represent anchorperson's monologue and dialog respectively. For MAGM, the grammars are in Figure 5(d), where anchorperson's opening, music, dialog, monologue, full screen text and commercials are determined structural elements, resp. denoted as A, M , D, L, E and P . MAGM is divided into many chapters by separators, and content of each chapter varies a lot. The inferred grammars of different granularity represent the structures of different levels of details.

In order to analyze the stability of grammars inferred, i.e., quantity of determined structural elements and their temporal stability, we vary the number of episodes used to infer the grammars. 6, 12, 18 and 24 episodes are chosen respectively to infer grammars for each program and the results are illustrated in Figure 6. We observe that with less episodes we could have more separators detected. Typically, in Figure 6(d), the grammar of MAGM inferred by 6 episodes has 8 separators, while 6 for 12 episodes and 5 for 18 and 24 episodes. This can be explained by the fact that separators are very short audio or visual sequences easily drowned in a large number of episodes. The same phenomenon can be found in grammars of GAME in Figure 6(b), the proportion of separators reduces when the number of episodes increases. This result shows that a small collection of episodes usually results in a high recall of separator detection. On the contrary, the numbers of detected structural elements tend to be stable along with the augmentation of the number of episodes, and the grammars converge, as shown in Figure 6(a), 6(b), 6(c). For MAGM in Figure 6(d), grammar stability is less evident, for the structure is more complex than others. However, the grammars stay relatively stable for those two inferred by 18 and 24 episodes. In order to infer a complete grammar which is generic enough to represent the structure of the program, these two phenomena hint that we may vary the number of episodes used to infer the grammar according to the wanted granularity. A small quantity of episodes, like 6 episodes, is sufficient for a coarse-grain grammar with only separators and chapters. For inferring a finer-grain grammar, the appropriate quantity of episodes is the number for which the grammar of program tend to converge. For instance, 6 episodes for GAME, 12 episodes for both NEWS and MAGS and 18 episodes for MAGM.

CONCLUSION

The structure discovery work described in this paper shows that a hierarchical structural grammar inference can efficiently yield an overview model for program structure. Moreover, the symbolic representation can serve for grammar inference for recurrent programs from a collection of episodes, with almost no supervision and no specific training data. In this work, a broad scope of event detectors of multimodality are firstly applied, followed by structural elements determination with minimal prior knowledge by exploiting role recognition and recurrence across episodes. A top-down and sectionalaligned architecture is then designed for grammatical inference to obtain hierarchical structural grammar at different granularity with minimal ambiguities. The event detection and selection techniques used are generic enough to be useful for a large variety of programs. The generalization of our approach lies in automatic discovery of the structure of recurrent TV programs. Experimental evaluation on four datasets of three types of programs shows that the grammar of program brings a final layer of structure of the program. By varying the number of episodes used for grammatical inference, a more relevant structure can be obtained for different granularity. Once the grammars of a program is obtained, the grammatical model can be utilized to structure additional episodes from the same program.

Fig. 1 .

 1 Fig. 1. General architecture of the three step approach for the grammatical inference of a program structure.

Fig. 2 .

 2 Fig. 2. Example of temporal density filtering to select structural events corresponding to structure separators (from [8])

Fig. 3 .

 3 Fig. 3. Illustration of structural grammar inference from three episodes with symbols SGCDYE.

Fig. 5 .

 5 Fig. 5. Grammars inferred using 12 episodes for resp. NEWS, GAME, MAGS and MAGM, each of which are coarse-grained to fine-grained grammar from top to down.

Fig. 6 .

 6 Fig. 6. Grammars for resp. NEWS, GAME, MAGS and MAGM. From top to down of each, the grammars are inferred using resp. 6, 12, 18 and 24 episodes.

Table 1 .

 1 Description of the datasets used for evaluation

	Dataset	Date	Episodes	Type	Average duration
	GAME 1991 -1992	24	Game	31.9 m
	NEWS	2007	24	TV news	37.9 m
	MAGS	1997	24	Magazine	57.7 m
	MAGM	1989	24	Magazine	61.9 m

Table 2 .

 2 Structural elements detection using a broad scope of detectors Based on anchorperson prediction, news content can then be divided into alternating patterns and anchorperson's introduction and news report, resp. denoted as A and R. As the number of reports varies across news episodes, we use just one occurrence to represent the repeated alternation. For GAME in Figure5(b), besides separators, dominant person (i.e., monologues of the conductor) and dialogs are the valid structural elements, resp. denoted as A and D. The segments in the second level of the grammar, denoted as N , can be further determined for different episodes, as dialogs or/and full screen text denoted as E.

	Structural element	Symbol	Shot duration	Dissolve transition	Mono-chrome image	Centra-lized text	Motion activity	(Dominant) person	Shot reverse shot	Speech music silence	Audio recurrence
	Separator GAME	S		yes	yes
	Separator MAGM S,V ,F ,H,G,I,K									yes
	Separator MAGS	S									yes
	Separator NEWS	S			yes
	Dialog	D							yes
	(Anchor's) monologue	(A) L	long					yes
	Music/song	M								music
	Commercials	P	short		yes					silence
	Outline NEWS	T	short							music&speech
	Full screen text	E				yes	low
	considered as news content.


Marie-Dominique E Leroux
email: marie-dominique.leroux@meteo.fr

Matthieu Plu

Frank Roux

ON THE SENSITIVITY OF TC INTENSIFICATION UNDER UPPER-LEVEL TROUGH FORCING

INTRODUCTION

Issues to accurately predict tropical cyclone (TC) intensification using NWP models remain, stressing out the need to unravel or clarify some of the mechanisms leading to TC spinup, and/or better resolve multiscale processes in prediction models; indeed, both large-scale (e.g., [START_REF] Molinari | External influences on hurricane intensity. Part III: Potential vorticity structure[END_REF][START_REF] Molinari | Potential vorticity analysis of tropical cyclone intensification[END_REF][START_REF] Hanley | A compositive study of the interactions between tropical cyclones and upper-tropospheric troughs[END_REF][START_REF] Davidson | Downstream development during the rapid intensification of hurricanes Opal and Katrina: the distant trough interaction problem[END_REF]) and vortexscale (e.g., [START_REF] Emanuel | An air-sea interaction theory for tropical cyclones. Part I: Steady-state maintenance[END_REF][START_REF] Willoughby | Concentric eyewalls, secondary wind maxima, and the evolution of the hurricane vortex[END_REF][START_REF] Montgomery | A theory of vortex Rossby waves and its application to spiral bands and intensity changes in hurricanes[END_REF] processes have been demonstrated to control rapid intensification (RI), defined in the North Atlantic by an increase of the maximum sustained surface winds above 30 kt (15.4 m s -1 ) in the course of 24 hours [START_REF] Kaplan | Large-scale characteristics of rapidly intensifying tropical cyclones in the North Atlantic basin[END_REF].

Understanding TC intensity changes under upperlevel trough forcing, in particular, remains one of the strongest challenges of operational forecasting. The various perturbations of the large-scale environment induced by a trough have already been documented, together with their possible impact on storm intensity: significant vertical wind shear (usually detrimental, [START_REF] Kaplan | Large-scale characteristics of rapidly intensifying tropical cyclones in the North Atlantic basin[END_REF], increased upper-level divergence and enhanced outflow poleward of the storm (beneficial, [START_REF] Ritchie | Simulations of the extratropical transition of tropical cyclones: Phasing between the upper-level trough and tropical systems[END_REF], as well as cyclonic eddy angular momentum import [START_REF] Molinari | External influences on hurricane intensity. Part III: Potential vorticity structure[END_REF] and cyclonic potential vorticity (PV) advection toward the TC core, beneficial below the level of the outflow anticyclone ("PV superposition principle", [START_REF] Molinari | Potential vorticity analysis of tropical cyclone intensification[END_REF]. However, to help forecasters tackle the "bad trough/good trough" [START_REF] Hanley | A compositive study of the interactions between tropical cyclones and upper-tropospheric troughs[END_REF]) issue, fur-ther investigation is needed to clarify the physical and dynamical processes involved in TC-trough interactions and accurately predict the systematic impact of an upper-level trough on TC intensity.

As [START_REF] Molinari | Potential vorticity analysis of tropical cyclone intensification[END_REF] concluded: "A great need exists for systematic study of hurricane-trough interactions with a hierarchy of numerical models that isolate the various mechanisms and for observation of the upper troposphere during such interactions." The present study attempts to address this request by examining the sensitivity of TC intensification in the presence of a nearby trough. Relevant questions include: Why can some TCs intensify in moderate to high shear conditions while others decay? Are the initial relative positions and intensities of the trough and the TC important in favoring a good trough interaction? What is the dynamic impact of an outside upper to midlevel PV anomaly in vortex intensification?

DATA AND TOOLS

Many observational studies and numerical modeling have documented TC-trough interaction. [START_REF] Kimball | Idealized numerical simulations of hurricane-trough interaction[END_REF] in particular ran numerical simulations in an idealized framework to modify the intensity and size or depth of a cold core upper-level low approaching a same initial vortex. [START_REF] Shapiro | Influence of atmospheric asymmetries on the intensification of GFDL model forecast hurricanes[END_REF] used piecewise PV inversion to modify the trough approaching a real hurricane and quantify its contribution to storm intensification. The idea now is to a use a real case of TCtrough interaction and run sensitivity experiments in which only the initial position and intensity of the TC are modified, leaving the trough untouched.

a. TC Dora TC Dora (2007) is an interesting case to study TC-trough interaction. Its deepening occurred in the southwest Indian ocean under hardly conducive conditions: ambient wind shear was large (above 9 m s -1 during 36 hours, peaking at 12 m s -1 ), and ocean heat content was below the 50 kJ cm -2 threshold that has been shown to promote high rates of intensity change. Rapid intensification occurred between 1800 UTC 31 January and 0000 UTC 3 February with a 50 hPa pressure fall from 975 hPa (see Fig. 1 of [START_REF] Leroux | Dynamical and physical processes leading to tropical cyclone intensification under upper-level trough forcing[END_REF]. From late 1 to early 2 February, the intensification was temporarily slowed down by an ERC "eyewall replacement cycle" (ERC, [START_REF] Willoughby | Concentric eyewalls, secondary wind maxima, and the evolution of the hurricane vortex[END_REF]) clearly identified on passive microwave imagery.

b. The reference experiment

A control run (hereafter called "reference experiment") of TC Dora was previously examined by [START_REF] Leroux | Dynamical and physical processes leading to tropical cyclone intensification under upper-level trough forcing[END_REF]. This 60-h forecast, starting at 0600 UTC 31 January 2007 (12 hours prior to the onset of RI), was carried out using the limited-area model Aladin-Reunion in its 2011 operational version (domain shown in Fig. 1, hydrostatic, 70 vertical levels, 8-km horizontal resolution, cf. [START_REF] Montroty | Impact of wind bogus and cloud-and rain-affected SSM/I data on tropical cyclone analyses and forecasts[END_REF]. The forecast was initialized and coupled with ECMWF global analyses, and Aladin's 3D-Var assimilation of cyclone wind bogus was used to get a realistic vortex structure at the basetime of the forecast. Fig. 1 indicates that Dora was approached by an upper-level trough associated with a planetary Rossby wave train originating from the midlatitudes. A high negative (cyclonic) PV anomaly associated with a cutoff cyclone formed during the isentropic equatorward advection of stratospheric air into the troposphere; It is located some 12 degrees southeast of Dora's center at the basetime of the forecast (Fig. 1).

In the reference simulation, the model captured the PV interaction as well as the two periods of RI (see Fig. 4 of [START_REF] Leroux | Dynamical and physical processes leading to tropical cyclone intensification under upper-level trough forcing[END_REF]). The main mechanisms identified for vortex intensification were PV superposition between about 33 and 40 h, followed by secondary eyewall formation induced by eddy angular momentum flux convergence, eddy PV fluxes, and vertical velocity forcing from the trough. was moved 1, 2, 3 or 4 degrees away from the best track position in 8 different quadrants, as illustrated in Fig. 1 (red dots). 1 degree is realistic and close to an operational analysis error; 4 degrees is approximately one third of the initial distance separating Dora from the cutoff cyclone. Also, some 10 hPa difference being within the range of initial intensity error from observations or model analyses, three values were tested to initialize the vortex central pressure: 975 hPa (the best track value used in the reference experiment), as well as 990 and 960 hPa. The latter were experienced by the storm at other times of its life cycle, and therefore chosen in order to constrain the bogussed vortex with realistic values of RMW and MSLP pressure (obtained from the best track data).

RESULTS

Weaker initial vortices systematically deviate to the east due to a smaller vertical extension of the vortex, lowering the depth of the steering flow that affects the storm track. Therefore, we will focus on the other intensity experiments, whose tracks are similar to that of the reference experiment with a general movement of the vortex to the south, then southeast, before veering to the south-southwest. To stay in realistic conditions, all simulations are initialized with the same operational sea surface temperature (SST) field (not shown). This field is not uniform: depending on its track, a vortex will move over warmer or colder SSTs than in the reference experiment, which will be quantified below.

a. Central experiments

The evolution of the predicted pressure along the 60-h forecast shows that a stronger initial vortex placed in the same location as Dora has a greater intensification rate after 36 hours (not shown). With a track almost identical to that of the reference experiment, and less than 0.05 • C SST difference on average over a 300-km radius area and over the 60-h period, this intensification is most likely related to a favored interaction of the two cyclonic PV anomalies in the 500-300 hPa layer. At 400 hPa (Fig. 2), cyclonic PV advection from the trough into the TC core begins at 33 h, like in the reference experiment, but lasts longer (at least 8 more hours).

b. 975-hPa experiments

To see how environmental parameters evolve with initial vortex position for all quadrants and distances, area and time averages are computed over the 60-h period of the forecast. Fig. 3 shows PV values averaged over a 200-800-km annulus region surrounding the storm predicted center, and over a 335-350-K layer to take into account the vertical extension of the PV anomaly approaching Dora. The x-axis gives the initial distance from the best track center from 1 to 4 degrees and the 8 quadrants are plotted with different colors, a grey color corresponding to the reference experiment (best track position). Results show, in most quadrants, a quasi-linear evolution of the PV with the initial distance from the storm: such parameter is therefore a good indication of the trough proximity. Secondly, the storm is surrounded by more cyclonic potential vorticity when it is initially moved to the south, southeast, southwest, and eastern quadrants to a lesser extent, which is summarized in Fig. 4 (red dots). FIG. 3. Mean PV values averaged over a 60-h period, a 335-350-K layer and a 200-800 annulus region surrounding the storm predited center, for experiments initialized with a 975 hPa central pressure.

Briefly, Fig. 4 summarizes the favorable (red) and unfavorable (blue) quadrants for the most important large-scale parameters influencing TC intensity. SSTs are colder in the south, southeastern and eastern quadrants (up to 0.35 • C) which is consistent with the latitudinal gradient of SSTs and may be observed in most TC-trough interaction cases in the southern hemisphere. Divergence increases at 200 hPa when the vortex is moved towards the south, southeast, east and northeast, while vortices displaced further north, southwest and south experience less vertical wind shear from a trough origi-nally located in the southeastern quadrant of the vortex. Note that both the divergence and shear are conducive to TC intensification when the vortex is initially moved to the south. It is important to stress the fact that the shear and the divergence, both computed over a 200-800 annulus region, do not systematically evolve in the same way: in most cases, i.e. in most quadrants here, when the shear increases, the divergence increases (not shown). However, in the case of a cutoff low originally located southeast of the storm, we notice that, when the vortex is moved to the south, the shear abates while the divergence increases compared to the reference experiment; when moved to the west instead, the shear amplifies and the divergence decreases (except for an initial 1-degree distance).

Pressure forecasts indicate that no vortex initialized at 975 hPa intensifies more than the reference experiment, for an initial distance greater than one degree, albeit higher SSTs in some quadrants (not shown), or favorable shear and divergence conditions in the southern quadrant. This suggests that the trough interaction has a major role to play in storm intensification. However, after 60 hours, 4 vortices initially displaced by one degree are deeper than the reference experiment, due to a greater intensification rate after 36 h: the one shifted to the northwest, with the help of higher SSTs, and all the 3 vortices that benefit from lower SSTs in the south, southeast and eastern quadrants. The southeastern quadrant in particular deepens by more than 10 hPa. Once again, this result seems correlated with a longer (at least 14 more hours) and greater PV superposition at 400 hPa when the TC is initially displaced 1 degree in the direction of the cutoff low.

CONCLUSION

Diagnostics confirm the importance of the relative positions and strength of a TC and a cutoff cyclone interacting together to promote TC intensification. In the case of TC Dora, when the vortex is initially stronger and located at the best track position, the merging of the two cyclonic PV anomalies associated with the trough and the TC is favored at midlevels (330 K, or about 400 hPa) which helps strengthening the TC inner-core even more. It also occurs for a vortex initially as strong as Dora, positioned one degree closer to the cutoff low, originally located 12 degrees southeast: it intensifies more after 36 hours from longer PV advection into the TC core, albeit colder SSTs.

Another interesting aspect is that the southern quadrant of a TC approached by an upper-level low located to the southeast has favorable conditions in terms of divergence, shear and mean cyclonic potential vorticity. In the context of TC-trough interaction, it was shown that the divergence and the shear do not necessarily evolve in the same way. They are asymmetric processes that we try to estimate using symmetric averaged quantities. This might be part of our difficulty to forecast good trough/bad trough interactions in a systematic way. Future work is planned to compute PV budgets and Eliassen-Palm flux diagrams for several interesting experiments and see how the processes identified in the reference experiment [START_REF] Leroux | Dynamical and physical processes leading to tropical cyclone intensification under upper-level trough forcing[END_REF] are modified. Is it possible to elaborate a conceptual model for TC-trough interaction?

  FIG. 1. Wind vectors (arrows) and PV field (PVU; negative, shaded with -0.7 PVU and -1.5 PVU contours; positive, 0.2 PVU and 1 PVU dotted contours) at 200 hPa at the initial time of the reference simulation. A cross indicates Dora's best track center. Red dots delineate the various initial vortex positions in the sensitivity experiments. Label "B" indicates the coherent structure (cutoff low) approaching TC Dora.

  FIG. 2. As inFig. 1 but at level 400 hPa after 48 hours of model integration for (left) the reference simulation and (right) a stronger initial vortex positioned at the same initial location. A cross (resp. circle) indicates the vortex predicted center in the simulation (resp. in the reference experiment).

FIG. 4 .

 4 FIG. 4. Systematic favorable (red) and unfavorable (blue) quadrants for storm intensification at each initial distance, in the case of middle intensity experiments. Quadrants are left blank if favorability varies among initial distances. 4 distinct large-scale parameters are examined: (a) the SST, (b) the divergence at 200 hPa (DIV), (c) the potential vorticity averaged over a 335-350-K layer (PV), and (d) the shear computed between 200 and 850 hPa (Shear). Values are also averaged over the 60-h forecast and over a 200-800-km annulus region surrounding the storm predicted center, except for the SST averaged over a 300-km radius area.


Guillaume Gravier

Nathan Souviraà-Labastie

Sébastien Campion

Frédéric Bimbot

Audio thumbnails for spoken content without transcription based on a maximum motif coverage criterion

Keywords: spoken content processing, audio mining, motif discovery, summarization, thumbnailing

The paper presents a system to create audio thumbnails of spoken content, i.e., short audio summaries representative of the entire content, without resorting to a lexical representation. As an alternative to searching for relevant words and phrases in a transcript, unsupervised motif discovery is used to find short, word-like, repeating fragments at the signal level without acoustic models. The output of the word discovery algorithm is exploited via a maximum motif coverage criterion to generate a thumbnail in an extractive manner. A limited number of relevant segments are chosen within the data so as to include the maximum number of motifs while remaining short enough and intelligible. Evaluation is performed on broadcast news reports with a panel of human listeners judging the quality of the thumbnails. Results indicate that motif-based thumbnails stand between random thumbnails and ASR-based keywords, however still far behind thumbnails and keywords humanly authored.

Introduction

Over the past few years, unsupervised word discovery methods have been proposed with the goal of finding patterns in the signal which correspond to words or short sequences of words [START_REF] Park | Unsupervised pattern discovery in speech[END_REF][START_REF] Muscariello | Audio keyword extraction by unsupervised word discovery[END_REF][START_REF] Anguera | Partial sequence matching using an unbounded dynamic time warping algorithm[END_REF][START_REF] Jansen | Efficient spoken term discovery using randomized algorithms[END_REF], similar to previous work in the field of music processing [START_REF] Dannenberg | Pattern discovery techniques for music audio[END_REF][START_REF] Paulus | Music structure analysis by finding repeated parts[END_REF]. All of these methods search for repeating acoustic patterns in speech data in a totally unsupervised manner, targeting patterns which are likely to correspond to wordlike units because of their length and repetitiveness. Apart from being a fun and challenging scientific problem, unsupervised word discovery has a number of potential applications, among which transcript-free spoken content processing. Indeed, many natural language processing techniques exploit the notion of reoccurrence, i.e., repetition of a term at the lexical level, e.g., to weight terms, to find out keywords, to measure lexical cohesion. Unsupervised word-like motif discovery have made it possible to measure reoccurrence directly at the acoustic level, without resorting to a lexical representation, hence opening the door to transcript-free spoken content processing. This idea has been (briefly) explored in a few tasks such as topic segmentation [START_REF] Malioutov | Making sense of sound: Unsupervised topic segmentation over acoustic input[END_REF], multiple document summarization [START_REF] Zhu | Summarizing multiple spoken documents: Finding evidence from untranscribed audio[END_REF], document clustering [START_REF] Dredze | NLP on spoken documents without ASR[END_REF] and acoustic word cloud representations [START_REF] Flamary | Spoken Wordcloud: clustering recurrent patterns in speech[END_REF].

Following this line of thought, we propose and evaluate a transcript-free algorithm to generate audio thumbnails of spoken content, an idea initially introduced for music summarization [START_REF] Cooper | Summarizing popular music via structural similarity analysis[END_REF][START_REF] Chai | Structural analysis of musical signals for indexing and thumbnailing[END_REF][START_REF] Peeters | Computer Music Modeling and Retrieval[END_REF]. Thumbnails, whether written or audio, are intended for users to quickly grasp the content of a document without having to read it or listen to it entirely. Similar to classical thumbnails, e.g., on popular web search engines, an audio thumbnail is a short audio file, typically 10 s long, providing a condensed version of the information contained in a document. The straightforward way to generate thumbnails for spoken content consists in obtaining a lexical representation via automatic speech recognition (ASR) before applying text summarization techniques [START_REF] Goldman | Accessing the spoken word[END_REF]. Resorting to ASR is however costly from a computational standpoint and only applicable to languages for which ASR systems exist. As an alternative to ASR-based thumbnailing, word discovery and pattern reoccurrence can be exploited to directly generate an audio thumbnail.

In this paper, we introduce a criterion based on maximum motif coverage for transcript-free audio thumbnailing, elaborating on the idea that words that repeat within a spoken document are meaningful and relevant and should therefore be included in the thumbnail. The maximum motif coverage criterion hence seeks to maximize the number of motifs which have at least one occurrence included in the thumbnail, subject to length and intelligibility constraints. Via listening tests, we experimentally compare audio thumbnails based on motif discovery to various contrasts, including ASR-based keywords, on broadcast news reports with the ultimate goal of helping users navigate within audiovisual news archives as illustrated by the Texmix demo [START_REF] Bréhinier | Texmix: An automatically generated news navigation portal[END_REF] 1 .

The paper is organized as follows. Sec. 2 briefly recalls the word-like motif discovery method used. Sec. 3 details the thumbnailing algorithm based on the notion of maximum motif coverage. Finally, human-centric evaluations are reported in Sec. 4 before a concluding discussion in Sec. 5.

Word-like motif discovery

The discovery of repeating motifs follows the algorithm of Muscariello et al. [START_REF] Muscariello | Unsupervised motif acquisition in speech via seeded discovery and template matching combination[END_REF], whose main principles are recalled hereunder. Given a set of feature vectors x = {x1, . . . , xn}, we seek all pairs [a, b] and [c, d] such that the two subsequences {xa, . . . , x b } and {xc, . . . , x d } are acoustically close enough subject to minimal constraints (minimal segment length and non overlapping segments). Segments that verify this property are considered as belonging to the same underlying motif .

Efficiently finding reoccurrences of a portion of x exploits two properties. First, we rely on the notion of seed, borrowed from the field of genomics, where a seed is a short segment that might be contained in a bigger motif. The foundational idea of the seed based approach is to search for repetitions of a seed using a segmental variant of dynamic time warping (DTW) which enables locating the start and end point of subsequences close to the seed in the data, if any. A motif is hypothesized whenever such a subsequence is similar enough to the seed. In this case, the seed and its matching sequence are grown both forward and backward to find maximal length occurrences of a repeating motif by extending the optimal warping path in both directions as long as the average path distortion does not grow too high. The two extended matching segments are considered as occurrences of a motif if the average warping distortion is below a similarity threshold. Second, similar to [START_REF] Herley | ARGOS: Automatically extracting repeating objects from multimedia streams[END_REF], we assume that repeating words repeat at least once locally, i.e., with a minimum time between two occurrences. In other words, for a motif, there are at least two occurrences which repeat within a limited time span. This assumption enables to break down the inherently quadratic complexity of the search for repetitions, restricting the search for a reoccurrence of a seed to a short time window in the future (or, equivalently, in the past). To find long span repetitions of a motif, a library is used to store a locally reoccurring motif whenever one is discovered. The library also acts as a clustering step, grouping all occurrences of a motif within the same entry.

Combining the property of local repetition with the seed principle leads to the following algorithm sequentially processing the data to incrementally build the library which is initially empty. Starting with a short seed at t = 0, segmental DTW is used to search for a repetition of the seed either in the library or, if not found there, in the near future. If a close-enough repetition of the seed is found, the match is grown to find maximally repeating sequences which are considered as a reoccurrence if the DTW similarity between the extended matching sequences is below a threshold α. A reoccurrence found with a library entry indicates that a long span match of an existing motif was found. A reoccurence found in the near future means that a new locally repeating motif was discovered and must be added to the library. The algorithm proceeds by shifting the seed until the data has been entirely processed.

The crucial parameters of the motif discovery algorithm are (a) the seed length, which is directly related to the minimum length of a motif occurrence; (b) the size of the near future time window in which the seed is searched for; (c) the similarity threshold α, where the lower the threshold, the more similar the occurrences of a motif. For word discovery, a short seed length must be considered with a sufficiently loose threshold α to account for variability in speech, yet preserving precision for each motif. The size of the near future depends on the type of data considered and is only critical for computation time.

Thumbnailing algorithm

Elaborating on the postulate that repeated words/motifs are meaningful to spoken content understanding and should therefore be included in the thumbnail, the thumbnailing algorithm exploits motif discovery to find repeating word-like patterns. Thumbnails are generated by extracting a very limited number of segments from the original data, typically one or two, as illustrated in Fig. 1. The selection of the segments to extract is based on the maximum motif coverage principle with the goal of including at least one occurrence of as many motifs as possible, subject to constraints on the total length and on continuity.

We briefly discuss how motif discovery was used to generate a library of motifs before providing the details of the segment selection algorithm.

Creation of the library

Motif discovery as presented in Sec. 2 may yield significantly different results depending on the length of the seed and on the similarity threshold α which controls the amount of variability tolerated between two occurrences of a motif. Very short seeds will often result in non informative, mostly non lexical, motifs such as breath intakes. On the contrary, long seeds will result in no motifs being found. Interestingly, within the range of reasonable seed size, experience tells that different, complementary, libraries are often found when using different lengths for the seed. We exploit this property to create a library of motif which combines motifs found with a seed of 500 ms with motifs found with a longer seed of 1 s. Those values were empirically chosen and are well adapted to the broadcast news data we consider in the experimental section. The similarity threshold α is determined independently for each waveform file to process and each seed length. Setting the threshold appropriately result from a trade-off between various factors, mostly, the number of motifs within the library and the balance between precision and recall for each motif. Low thresholds yield libraries with few motifs detected with high precision and limited recall. Conversely, high thresholds will provide libraries with many entries and exhibit poor precision. To ensure that a sufficient number of motifs are found for each document processed, similarity thresholds are set depending on the file length so as to yield an average number of motif occurrences per minute. For a 0.5 s (resp. 1 s) seed, we target 20 (resp. 10) occurrences for a 2 m file. For a set of feature vectors x, of length L(x) minutes, this is generalized by defining the expected number of motif occurrences in x as

b Kx = k " 1 + log " L(x) 2 «« , ( 1
)
where k is either 10 or 20 depending on the seed length. Given b Kx, α is empirically determined by grid search so that the actual number of occurrences is as close as possible to b Kx.

Selection of the segments

The motif discovery step yields a library Mx of Nx motifs resulting from the mere concatenation of the motifs found with seed lengths of resp. 0.5 s and 1 s. In the sequel, Mx(i) denotes the ith motif and Mx(i, j) its jth occurrence (j ∈ [1, N

x ]).

Selection criteria

Thumbnails are created by selecting a small number of relevant segments within x which are then combined to provide an audio output. In spirit, this approach is similar to selecting relevant sentences in extractive text-based summarization (see, e.g., [START_REF] Gupta | A survey of text summarization extractive techniques[END_REF] for a review on the subject). However, contrary to texts, the notion of sentence is obviously absent from audio files and one must jointly define the segments to consider and assess their relevance. The set of segments selected for thumbnailing should globally have three main properties, namely, be relevant and exhaustive with respect to the original message, be short enough and be easy to understand. We propose to translate relevance and exhaustiveness into a motif coverage criterion which counts the number of motifs that have occurrences within the set of segments selected. Formally, if Ux = {x e 1 s 1 . . . x en sn } denotes a collection of n segments in x, identified by their start and end times si and ei (i ∈ [1, n]), the motif coverage of Ux with respect to the library Mx is defined as

c(Ux, Mx) = Nx X i=1 δ(Mx(i) ∩ Ux) Nx , (2)
where δ(Mx(i)∩Ux) = 1 if at least one occurrence Mx(i, j) is contained within a segment of Ux, 0 otherwise. In plain words, coverage is the proportion of motifs in Mx which occur in Ux.

Motif coverage can obviously be maximized simply by selecting one occurrence of each motif as Ux. However, this trivial solution is not very satisfactory as far as understandability is concerned. Indeed, concatenating a large number of very short segments, without any context, is hard to comprehend at the audio level. It is interesting to draw a parallel with texts at this point. Playing an occurrence of each motif is similar to displaying keywords, which is different from thumbnailing where short excerpts of the text are displayed. While keywords provide an efficient way for a human reader to get a gross feeling for the content, thumbnails usually enables a better understanding. Moreover, preliminary experiments on a very limited scale with audio keywords, i.e., motifs occurrences, stressed that listening significantly differs from reading, resulting in increased difficulty to get a feeling of the content from audio keywords compared to text keywords. Hence, in addition to motif coverage, we ensure the easiness of understanding criterion by selecting a very limited number of segments, typically one or two, thus favoring long segments which include the largest possible number of motifs with a natural context.

Incorporating the maximum length criterion of the thumbnail with motif coverage and easiness of understanding, the segment selection step consists in finding the set of segments maximizing the global, empirically defined, cost function

C(Ux; Mx) = c(Ux, Mx) " 1 - l(Ux) 25 « 3 (1 -0.2|1 -n|) , (3)
where l(Ux) = P eisi is the total duration in seconds. The first term of the product in C(Ux; Mx) is the coverage, the second accounts for the total duration of the audio thumbnail, with an upper limit of 25 s, while the third limits the number of segments included. Parameters were empirically fixed on a few examples.

Algorithm 1 Two-level greedy optimization algorithm for (3)

1: b Ux ← ∅ 2: for m = 2 to Nx do
⊲ for all possible subset sizes 3:

Ux ← MAXIMIZE(Mx, m) ⊲ find best segment 4: b Ux ← Ux if C(Ux, Mx) > C( b Ux, Mx) 5: M ′ x ← Mx-MOTIF(Ux, Mx) ⊲ remove motifs in Ux 6:
for m ′ = 2 to Nxm do ⊲ proceed at level 2 7:

U ′ x ← Ux ∪ MAXIMIZE(M ′ x , m ′ ) 8: b Ux ← U ′ x if C(U ′ x , Mx) > C( b Ux, Mx) 9:
end for

return arg max U C(U ; M ) s.t. X i δ(M (i) ∩ U ) = m 16: end function 3.2.

Algorithmic implementation

The maximization of ( 3) is performed in a greedy heuristic way, considering in turn various combinations of motifs from the library and limiting ourselves to a maximum of n = 2 segments selected. The idea is to search for combinations of motifs with consecutive occurrences for all possible sizes of such combination. The solution is initialized to the empty set. For all sizes m of the possible motif subsets, we determine the segment in x that maximizes (3) across all tuples of motifs of size m with consecutive occurrences. Since the first and third terms in [START_REF] Anguera | Partial sequence matching using an unbounded dynamic time warping algorithm[END_REF] are fixed in this case, the best segment is actually the smallest segment which includes occurrences of exactly m motifs. This selection procedure is recursively pursued in search of a potential second segment after removing from the library the motifs considered at level one. In the end, we pick the configuration that maximizes the global cost function among the one or two segments solutions enumerated, as illustrated by Algorithm 1.

In practice, segment boundaries are adjusted according to silences in Algorithm 1. Silence detection is performed based on the waveform energy profile. When searching for the minimum length segment maximizing (3), boundaries of the segments are extended to the nearest silence of at least 0.2 s, including silences within the segment to avoid concatenation artifacts.

Human-centric evaluations

Evaluation was performed on reports from TV broadcast news which were presented to users along with a variety of audio thumbnails and of keywords. We first describe the data and setting for this evaluation before reporting results.

Data and settings

A total of 20 reports, taken from the regular 20h broadcast news show on the French channel France 2, were selected to include a diversity of topics (sports, politics, etc.). Reports have an average duration of 1 m 48 s, including the anchorperson's introduction preceding the report itself, with mostly a unique speaker during the report. The introduction was considered as being part of the report and was included in all of the experiments.

For each report, a thumbnail based on motif discovery was created according to Algorithm 1 along with two contrasts, namely a random thumbnail and an oracle thumbnail. Random thumbnails are made by selecting at random between single or multiple segments. In the first case, an initial utterance (as provided by the ASR partitioning system) is chosen at random, selecting contiguous utterances to ensure at least a 10 s thumbnail. In the second case, a set of non contiguous utterances are chosen at random until a minimum duration of 10 s is reached. Oracle thumbnails simply consist in taking the introduction of the report by the anchorperson, authored by journalists as a teasing summary. In addition to audio thumbnails, keywords were also used as a different type of thumbnail, presenting a list of keywords to the user instead of an audio summary. For each report, a set of 10 keywords was selected, either by a human listener or automatically from the ASR transcript. Note that in the first case, keywords were chosen with no constraints, in particular no requirement to select keywords in a thesaurus or in the transcripts, with listeners often knowing the context of the news. ASR-based keywords were selected using the standard tfidf weighting after lemmatization, considering only adjectives, nouns and verbs. Transcripts exhibit a word error rate of about 18 % [START_REF] Huet | Morpho-syntactic postprocessing of n-best lists for improved french automatic speech recognition[END_REF] and inverse document frequencies were computed on a large collection of newspaper articles.

For evaluation, subjects were presented with the original report with either one of the audio thumbnails or keyword lists. They were asked to judge whether the thumbnail or keywords summary was characteristic of the report and provide a score on a scale from 1 to 7, the lowest score meaning "not at all" and the highest "that's exactly it". Evaluation was implemented via a dedicated web page that subjects could access any time they wanted, each time with a randomly chosen pair among the 100 possible tuples (20 reports, 5 thumbnail types). Subjects were recruited mostly among researchers and students in computer science, with some researchers in the speech communication field. A few votes from non technical people were also registered. All had limited knowledge of what they were evaluating and the contrasts were never described to the subjects who obviously didn't know which type of thumbnails they were rating.

Results

About 100 subjects participated in the evaluation2 , one third female and two third male. In total, 515 pairs report/thumbnail were evaluated, with about 100 responses for each type of thumbnails. The average number of votes per subject (excluding anonymous votes) is 4.2 but we observed significant variations across subjects with a standard deviation of 6.1: Around 50 % of the subjects only evaluated one or two pairs while the top 5 contributors account for about 30 % of the votes. This is clearly not an optimal situation but we believe it is the price to pay to ensure a sufficient number of responses by imposing almost no constraint for participation to the evaluation process.

Results are reported in Tab. 1, averaged across all votes for a given type of thumbnails. We report the empirical mean of the scores, the empirical standard deviation and the coefficient of variation, along with the number of votes on which these statistics were established. The coefficient of variation is a measure of how spread the votes are, independent of the value of the mean, thus providing a better measure of dispersion than the standard deviation. of multimedia spoken data, with significant differences in the average score to the benefit of human keywords and oracle thumbnails. Also, comparing these two strategies, i.e., audio thumbnail and keywords, in the human generated case, keywords appeared as more relevant to characterize a report than audio thumbnails. We believe that this is partly attributable to the fact that reading is faster and easier than listening to quickly comprehend the content. However, it is interesting to note that the average score for oracle audio thumbnails is reasonably high, indicating that in the absence of ASR transcription, audio thumbnails provide an interesting option.

Focusing on the comparison of the machine-generated audio thumbnails, motif-based thumbnails stand between random ones and oracle ones, with a large difference for the latter. Variations in the scores across subjects is also much higher for the machine-generated thumbnails than for the oracle ones, as indicated by the variation coefficients. Two factors can be invoked to explain this observation. On the one hand, automatically created thumbnails vary in quality from one report to another, depending on a variety of factors (number of actual motifs, quality of the motif discovery, randomness in the random case, etc.). On the other hand, facing poorer global quality, judgments greatly vary according to the degree of expectation of the subjects. Finally, the difference between random thumbnails and motif thumbnails is only marginally significant (p=0.057 according to the unpaired Student test). Interestingly, the difference in scores between motif thumbnails and ASR keywords is not significant (p=0.44). While word-discovery based thumbnails are only marginally better than random selection, they provide information comparable to ASR based keywords without the burden of transcription.

Discussion

The human-based experimental evaluation of audio thumbnails and keywords reported in this paper clearly establishes that transcript-free thumbnailing is possible and provide a level of information similar to ASR-based keywords. But reaching the level of humanly authored thumbnails and keywords require further work. The maximum coverage criterion is based on repetitions but do not account for the notion of frequency, less that of inverse document frequency. These two notions are known to be crucial in keyword extraction and should therefore be taken into account. While accounting for frequency is fairly easy, defining the notion of inverse document frequency in the framework of unsupervised motif discovery remains a challenge. Another interesting question to address is that of contextualization. Motif-based thumbnails include motifs plus context while ASR keywords, which obtained a similar average score, only include motifs. Measuring the importance of the context in audio thumbnails thus appear as a key to a better understanding of human acceptability of summaries and thumbnails.

Figure 1 :

 1 Figure 1: The different steps involved in motif discovery based thumbnail generation: motifs occurrences are indicated with colored rectangles, selected segments are highlighted in shadowed rounded boxes. Pale green regions below the waveform indicate silences.

See http://texmix.irisa.fr/modis for examples of audio thumbnails in French broadcast news data.

To keep things as light as possible, subjects were not required to identify themselves but were rather invited to enter a pseudo: Some did not and voted anonymously.