Josselin Gautier
email: jgautier@irisa.fr

Olivier Le Meur
email: olemeur@irisa.fr

Christine Guillemot
email: christine.guillemot@inria.fr

Efficient Depth Map Compression based on Lossless Edge Coding and Diffusion

The multi-view plus depth video (MVD) format has recently been introduced for 3DTV and free-viewpoint video (FVV) scene rendering. Given one view (or several views) with its depth information, depth image-based rendering techniques have the ability to generate intermediate views. The MVD format however generates large volumes of data which need to be compressed for storage and transmission. This paper describes a new depth map encoding algorithm which aims at exploiting the intrinsic depth maps properties. Depth images indeed represent the scene surface and are characterized by areas of smoothly varying grey levels separated by sharp edges at the position of object boundaries. Preserving these characteristics is important to enable high quality view rendering at the receiver side. The proposed algorithm proceeds in three steps: the edges at object boundaries are first detected using a Sobel operator. The positions of the edges are encoded using the JBIG algorithm. The luminance values of the pixels along the edges are then encoded using an optimized path encoder. The decoder runs a fast diffusion-based inpainting algorithm which fills in the unknown pixels within the objects by starting from their boundaries. The performance of the algorithm is assessed against JPEG-2000 and HEVC, both in terms of PSNR of the depth maps versus rate as well as in terms of PSNR of the synthesized virtual views.

I. INTRODUCTION

3DTV and FVV are promising technologies for the next generation of 3D entertainment. To this end, the MultiView plus Depth (MVD) format has been developed. From a collection of multi-view video sequences captured synchronously from different cameras at different locations, a view synthesis or rendering method can generate new viewpoints. The first version of the dedicated MVD sequence encoder, so-called MVC, was based on block transforms of depth maps. As argued by [START_REF] Smirnov | 3D Video Processing Algorithms-Part I[END_REF], the deblocking of depth maps is today one of the most important pre-and post-processing task for the MVD representation.

Depth maps have two main features that must be preserved but can also be relied on for efficient compression. The first one is the sharpness of edges, located at the border between object depths. Distortions on edges during the encoding step would cause highly visible degradations on the synthesized views, that may require depth map post-processing. The second one comes from the general smooth surface properties of objects we are measuring the depth on. Based on these observations, Merkle et al. [START_REF] Merkle | The effects of multiview depth video compression on multiview rendering[END_REF] proposed a "Wedgelet" signal decomposition method (itself based on "Platelet"). The smooth regions of the depth maps are approximated using piecewiselinear functions separated by straight lines. A quadtree decomposition divides the image into variable-size blocks, each of them being approximated by a modeling function. The refinement of the quadtree is then optimized in the ratedistortion sense.

In this context, we also observed that these smooth surfaces can be efficiently approximated by interpolating the luminance values located at their boundaries, instead of using models based on piecewise-linear functions where the coefficients need to be encoded [START_REF] Merkle | The effects of multiview depth video compression on multiview rendering[END_REF]. To this end, we can observe that depth maps share similarity to cartoon-images. Mainberger et al. [START_REF] Mainberger | Edge-based image compression with homogeneous diffusion[END_REF] proposed a dedicated cartoon-image encoder, that -in low bitrate conditions-beats the JPEG-2000 standard. After a Canny edge detection, the edge locations are encoded with a lossless bi-level encoder, and the adjacent edge pixel values are lossy quantized and subsampled. At the decoding stage, a homogeneous diffusion is used to interpolate the inside unknown areas from lossy decoded edges. Indeed, the demonstrated performances -while beating state of the art codecs-reach the limit of 30dB. We revisited this edge-based compression method by proposing improvements to fit the high quality, low bitrate, and specific requirements of depth maps. Finally, we increase the diffusion-based depth map encoding performance, which might be generalized to all kinds of images. In the next section, the encoding process is described. In section III the new decoding and diffusion methods are explained. Results, performances and comparison with stateof-the-art methods are given in Section IV. Conclusions are then drawn in section V.

II. ENCODING

The encoding is a 3-step process: first is the detection of edges, then encoding of the edge location and finally encoding of the edge, border and seed pixel values.

A. Edge detection

Different operators exist to extract the contour of an image. An optimal edge detector should provide:

• a good detection: the algorithm should find as much real edges as possible.

• a good localization: the edges should be marked as edges as close as possible to the real edges. • a good robustness: as much as possible, the detector should be insensitive to noise. In our context of depth map edge coding, several requirements are added. The quality of reconstruction by diffusion should be maximized, while minimizing the number of edges to encode. To avoid diffusion from bad positioned edges causing "leakages", the localization of contours should be quasi-perfect (see section III for explanation). The detection of contours should be good but avoiding an over-detection. Up to a certain limit, weak contours (i.e. with a low gradient) might be useless to the reconstruction and might unnecessarily increase the edge coding cost. Also, noisily detected pixels should be avoided for the same reason.

The Marr-Hildreth edge detector combined with Canny-like hysteresis thresholding is used in [START_REF] Mainberger | Edge-based image compression with homogeneous diffusion[END_REF], but suffers from error of localization at curved edges. The widely used Canny edge detector has also been benchmarked. It relies on a 5x5 gradient prefiltering to cope with noise before local maxima edge detection. But this prefiltering step also makes this detector vulnerable to contour localization errors, as illustrated in Fig. 1(c), where inexact selection of adjacent edge pixels lead to improper diffusion. At the opposite Sobel has the advantage of an accurate contour localization -as shown in Fig. 1(d)-at the cost of a noisy, edge over-detection. To cope with these over-detected edges, contours c shorter than a certain value (c < 14) are excluded. Pixels with a bi-dimensional gradient amplitude larger than a threshold λ are extracted. Used with sharp depth maps, this gives well-localised contours.

B. Encoding the contour location

As in [START_REF] Mainberger | Edge-based image compression with homogeneous diffusion[END_REF], a bi-level edge image containing the exact location of previously detected edges is first encoded using the JBIG (Joint Bi-level Image Experts Group) standard. This is a context-based arithmetic encoder enabling lossless compression of bi-level images. We use the JBIG-Kit [START_REF]Joint Bi-level Image Experts Group: Information technology -progressive lossy-lossless coding of bi-level images[END_REF], a free C implementation of the JBIG encoder and decoder. The progressive mode is disabled to reduce the required bitrate.

C. Encoding the contour values

Once the edge pixel locations have been encoded, the pixel luminance values have also to be losslessly encoded following our initial requirements. The authors in [START_REF] Mainberger | Edge-based image compression with homogeneous diffusion[END_REF] proposed to store the pixel values on both sides of the edge, instead of the pixel values lying on the edge itself. Indeed, for blurry contours, this might be valuable to interpolate the inner part of the edge and code the luminance values on both sides. However, with sharp depth maps, the pixel values lying directly on an edge, as illustrated in Fig. 1(b), alternate between one side or another from this edge and couldn't be interpolated correctly.

With the Sobel edge detection not thinned to a single edge pixel, we ensure to retain at least one pixel value from each side of the frontier edge as shown in Fig. 1(d).

We keep the idea of storing the pixel values by their order of occurrence along the edge to minimize signal entropy. A path Additionally to these edges we also encode two kinds of information. The pixel values from the image border are stored to initiate the diffusion-based filling from borders. Inspired by the work of [START_REF] Belhachmi | How to choose interpolation data in images[END_REF] on "dithering" for finding optimal data for interpolation, we propose to sparsely deploy, at regular intervals, some seeds of original depth pixels as shown in Fig. 1(b). While having low overhead, we discovered that this helps accurate reconstruction by initializing and accelerating the diffusion in large missing areas.

Thus, these extra border and seed pixels are coded in DPCM and added to the differential edge values. The resulting file is thus composed of the payload of the JBIG data and of the arithmetic encoded bitstream of the DPCM edge, border, and seed pixel values.

III. DECODING AND DIFFUSION

A lossless decoding is performed, followed by a lossy diffusion from the decoded edges.

A. Decoding contour location and pixel values

Once the edge positions from JBIG payload are decoded, the edge pixel values are decoded and positioned following the same order in which they were encoded: the path along contour location respecting directional priorities.The border and seed values are also re-positioned following a predefined location.

B. Reconstructing the missing values by diffusion

We now have a sparse depth map containing only the edge, border and seed pixel values. A homogeneous diffusionbased inpainting approach is used to interpolate the missing data. This method is the simplest of the partial differential equations (PDEs) diffusion method, and has the advantage of low computational complexity. It directly stems from the heat equation:

I t=0 = I δI δt = ∆I where I is the decoded edge image before diffusion that will constitute the Dirichlet boundaries of the equation. The diffused data then satisfies the Laplace equation ∆I = 0. The diffusion process is run in a hierarchical manner, each diffusion step being in addition helped with seeds and appropriate initialization. These three improvements have been introduced in the classical diffusion approach to limit the number of iterations required to converge, hence to speed up the entire process:

Hierarchical diffusion: A Gaussian pyramid is built from I. The diffusion process is first performed on a lower level of the pyramid and the diffused values are then propagated to a higher level (3 levels are used and shown good performance). The propagation of the blurred version of the diffused pixel values from an lower level to an upper one helps to initialize the diffusion in unknown areas.

Middle range initialization: On the highest level, instead of starting from unknown value of I set at 0, we propose to initialize unknown values to the half of the possible range: 128 for an 8 bit depth map. This facilitates and speeds up the process of diffusion by limiting the number of required iterations to converge.

Seeding: As explained in section II-C, some seeds are chosen from a regular pattern both to accelerate the diffusion process and to provide accurate initialized values in large unknown areas. Indeed, this definitely achieves a fast and accurate diffusion -with a gain of 10 dB-for a quasi-exact reconstruction of the depth map.

IV. EXPERIMENTS A. Conditions

The performances of the proposed compression method are evaluated on an original resolution depth map from a MVD sequence "Breakdancers" from [START_REF] Zitnick | Highquality video view interpolation using a layered representation[END_REF]. The depth maps were estimated through a color segmentation algorithm. The choice of this sequence is motivated by the presence of sharp object edges on depth maps. Additional results can be found on our webpage 1 . Most other raw MVD sequences might be suitable once they would be "sharpened" i.e. post-processed with a bilateral filter, as it is often required in practice [START_REF] Smirnov | 3D Video Processing Algorithms-Part I[END_REF].

B. Depth map quality evaluation

The reconstruction quality of our PDE-based method is investigated and compared with the JPEG2000 and HEVC-HM-4.1 Intra compressed versions. First, to illustrate the difference of quality reconstruction on edges, the three methods are compared at equal Peak-Signal-to-Noise-Ratio (PSNR),(45 dB, JPEG-2000 with a Quality factor Q=25, HEVC-Q=40). A zoom on the head of a character presenting initially sharp edges highlights the difference of edge quality depending on the compression type (Fig. 2). While at high PSNR, the JPEG-2000 (a) and HEVC (b) versions of the depth map tend to blur the edges. This is commonly referred to as ringing artifacts. It appears with JPEG-2000 because of the lossy quantization following wavelet transformation. It might appears with HEVC because of deblocking filter limitation. Then both JPEG-2000 and HEVC cannot efficiently reconstitute the smooth gradient on uniform areas while preserving the edges. At the opposite, our proposed approach stores the exact edges and diffuses regions between these edges, resulting in a smooth gradient restitution on slanted surfaces and non distorted edges.

Thus we evaluate the global depth-map rate-distortion performances of the three encoding methods. Fig. 3 shows that our approach outperforms JPEG-2000 except in very low or high bitrate conditions, while being under HEVC. No dedicated adjustment was perform in our method, only the threshold λ was varying to adjust its bitrate. An optimisation of the seed locations depending on bitrate might however improve the performance.

C. View synthesis quality evaluation

The impact of depth compression methods on rendering is measured by calculating the PSNR of a synthesized view (from a pair of uncompressed textures and compressed depth maps), with respect to an original synthesized view (from a pair of uncompressed textures and depth maps). The corresponding synthesized view from two original depth maps is then the reference. VSRS 3.0 [START_REF] Tanimoto | Reference softwares for depth estimation and view synthesis[END_REF] is used for view interpolation from this 2-view dataset. The R-D synthesis performance, illustrated in Fig. 4, justifies the edge-coding approach over wavelet based encoders: undistorted edges permits an accurate and efficient view coding and rendering. Again, the PSNR measure shows its limitation of objective evaluation on perceived quality. Our method do not always outperform in term of rate-distorsion the existing methods (Fig. 3,4), but can improve the perceived quality of the synthesized view especially on edges.

V. CONCLUSION

We proposed a new method for lossless-edge depth map coding based on optimized path and fast homogeneous diffusion. Our method, combined with a Sobel edge detection, provides a simple but efficient compression of edges enabling a perfect restoration of the depth map contours. Then it outperforms JPEG-2000 in term of PSNR, while being competitive to HEVC in term of perceived quality. Thanks to careful edge selection and seeding, we also manage to increase the quality reconstruction of previous works based on edge image coding. Thus this lossless edge coding method could be locally applied to color image compression, especially on uniform areas. In this case the edge detection method should probably be optimized depending on edge smoothness. Finally, a depth map video encoder is in our scope for future research.

ACKNOWLEDGMENT

This work is supported by the ANR-PERSEE project.

Fig. 1 :

 1 Fig. 1: (a) A "Breakdancer" depth map, (b) the encoded and decoded Sobel edge and seed pixels (red selection on (a)), (c) the Canny edges (blue selection), (d) the selection of pixel values adjacent to Canny edges (c) as in [3], with an intruder edge pixel in orange that will lead to bad diffusion, (e) the proposed Sobel selection of edge pixel values, exactly located from both side of the frontier edge

Fig. 2 :

 2 Fig. 2: Upper row: zoom on the head of a dancer on original View #3 (V3) depth map (a) highlights -by comparison at equal depth map PSNR (45dB) referenced to (a)-the ringing artifact on JPEG-2000 (b) and the blur effect with HEVC (c). Our method (d) based on exact edges and homogeneous diffusion prevent this effect (contrast has been increased on depth maps for distortion visibility). Lower row: zoom on corresponding synthesized view V4 without (e) or with JPEG-2000 (f) and HEVC (g) compressions and our method (h).

Fig. 3 :

 3 Fig. 3: Rate-Distortion performance of the V3 depth map with different quality factors of JPEG-2000 and HEVC, and different Sobel detection thresholds λ of our method.

Fig. 4 :

 4 Fig. 4: Rate-Distortion performance of synthesized V4 with the bitrate of V3 depth map, for different quality factors of JPEG2000 and HEVC, and different Sobel detection thresholds of our method.

http://www.irisa.fr/temics/staff/gautier/diffusion/

Picture Coding Symposium


Claire-Hélène Demarty
email: claire-helene.demarty@technicolor.com

Cédric Penet
email: cedric.penet@technicolor.com

Guillaume Gravier

Mohammad Soleymani
email: m.soleymani@imperial.ac.uk

The MediaEval 2012 Affect Task: Violent Scenes Detection *

Keywords: Violence detection, Affect, Movies, Annotation, Benchmark

This paper provides a description of the MediaEval 2012 Affect Task: Violent Scenes Detection. This task derives directly from a Technicolor use case which aims at easing a user's selection process from a movie database. This task will therefore apply to movie content. We provide some insight into the Technicolor use case, before giving details on the task itself. Dataset, annotations, and evaluation criteria as well as the two required and optional runs are described.

INTRODUCTION

The Affect Task -Violent Scenes Detection is part of the Me-diaEval 2012 benchmarking initiative for multimedia evaluation. It involves automatic detection of violent segments in movies. This challenge is a follow-up of last year's edition which served as a pilot, and therefore will only see slight modifications in 2012. It derives from a use case at Technicolor (http://www.technicolor.com). As a provider of services in multimedia entertainment, Technicolor is developing services connected to the management of movie databases, through content indexing and content discovery, for content creators. In that context, the company constantly seeks to help users select the most appropriate content, according to, for example, their profile or other constraints. Given this, a particular use case arises which involves helping users choose movies that are suitable for children in their family. The movies should be suitable in terms of their violent content, e.g., for viewing by users' families. Users select or reject movies by previewing parts of the movies (i.e., scenes or segments) that include the most violent moments. Despite its importance, there are only few published studies on the detection of violent scenes in videos. Among them, only a few use multimodal approaches [START_REF] Penet | Multimodal Information Fusion and Temporal Integration for Violence Detection in Movies[END_REF][START_REF] Chen | Violence detection in movies[END_REF]. Moreover, these methods suffer from a lack of a common and consistent database, and usually use a limited developement set [START_REF] Giannakopoulos | Audio-visual fusion for detecting violent scenes in videos[END_REF].

TASK DESCRIPTION

For 2012, the same task definition was kept: it still requires participants to deploy multimodal features to automatically detect portions of movies containing violent material. Defining the term 'Violence' is not an easy task, as this notion remains subjective and thus dependent on people. Since 2011, the chosen definition is the following: violence is defined as "physical violence or accident resulting in human injury or pain". Any features automatically extracted from the provided video, including the subtitles, may be used by participants. No external additional data such as metadata collected from the Internet can be used in this task. Only the content of the movie extractable from DVDs is allowed for feature extraction.

DATA DESCRIPTION

With respect to the use case, the dataset selected for the developed corpus is a set of 18 Hollywood movies that must be purchased as DVDs by the participants. The movies are of different genres (from extremely violent movies to movies without violence). The content extractable from DVDs consists of information from different modalities, namely, at least visual information, audio signals and subtitles. From these 18 movies, 15 are dedicated to the training process: Armageddon, Billy Elliot, Eragon, Harry Potter 5, I am Legend, Leon, Midnight Express, Pirates of the Caribbean 1, Reservoir Dogs, Saving Private Ryan, The Sixth Sense, the Wicker Man, Kill Bill 1, The Bourne Identity, the Wizard of Oz. The remaining 3 movies, Dead Poets Society, Fight Club and Independance Day, will serve as the evaluation set. As in 2011, we tried to respect the genre repartition (from extremely violent to non violent) both in the training and evaluation sets.

GROUNDTRUTH

The ground truth1 was created by 9 human assessors. In addition to segments containing physical violence (with the above definition), annotations also include high-level concepts for the visual and the audio modalities. Each annotated violent segment contains only one action, whenever it is possible. In the cases where different actions are overlapping, the whole segment is proposed with different actions. This was indicated in the annotation files by adding the tag "multiple action scene". Each violent segment is annotated at frame level, i.e. it is defined by its starting and ending video frame numbers.

Seven visual and three audio concepts are provided: presence of blood, fights, presence of fire, presence of guns, pres-ence of cold weapons, car chases and gory scenes (for the video modality); presence of screams, gunshots and explosions (for the audio modality). Participants should note that they are welcome to carry out detection of the highlevel concepts. However, concept detection is not the goal of the task and these high-level concept annotations are only provided for training purposes and only on the training set. For the video concepts, each of them follows the same annotation format as for violent segments, i.e. starting and ending frame numbers and possibly some additional tags. Regarding blood annotations, a proportion of the amount of blood in each segment is provided, as the percentage of the image surface covered by blood. Four different types of fights are annotated: only two people fighting, a small group of people (roughly less than 10), large group of people (more than 10), distant attack (i.e. no real fight but somebody is shot or attacked at distance). As for the presence of fire, anything from big fires and explosions to fire coming out of a gun while shooting, a candle, a cigarette lighter, a cigarette, or sparks was annotated, e.g. a space shuttle taking off also generates fire and receives fire label. An additional tag may indicate special colors of the fire (i.e. not yellow or orange). If a segment of video showed the presence of firearms (respectively cold weapons) it was annotated by any type of (parts of) guns (respectively cold weapons) or assimilated arms. By "cold weapon", we mean any weapon that does not involve fire or explosions as a result from the use of gun powder or other explosive materials. Annotations of gory scenes are more delicate. In the present task, they are indicating graphic images of bloodletting and/or tissue damage. It includes horror or war representations. As this is also a subjective and difficult notion to define, some additional segments showing really disgusting mutants or creatures are annotated as gore. In this case, additional tags describing the event/scene are added. For the audio concepts, each temporal segment is annotated with its starting and ending times in seconds, and an additional tag corresponding to the type of event, chosen from the list: nothing, gunshot, canon fire, scream, scream effort, explosion, multiple actions, multiple actions canon fire, multiple actions scream effort. Automatically generated shot boundaries with their corresponding key frames are also provided with each movie. Shot segmentation was carried out by Technicolor's software.

RUN DESCRIPTION

Participants can submit two types of runs: the required run or shot-classification run and the optional run which is the segment-level run. For the shot-classification run, participants are required to provide a violent scene detection at the shot level, according to the provided shot boundaries. Each shot should be classified as violent or non violent, with possibly a confidence score. As for the segment-level run, participants are required to, independently of shot boundaries, provide violent segments for each test movie. Once again, confidence scores may be added for each segment. In both cases, confidence scores are optional. However, providing a list of segments that covers the entire duration of the videos enables plotting of detection error trade-off curves based on the scores which should be of great interest to analyze and compare the different techniques. Hence, we encourage participants to do so. Scores will in any case not be used for the official performance evaluations which will be based solely on the decisions provided in the submitted resulting file.

EVALUATION CRITERIA

Several performance measures will be used for diagnostic purposes (false alarm and miss detection rates, AED-precision and recall as defined in [START_REF] Temko | Acoustic Event Detection: SVM-Based System and Evaluation Setup in CLEAR[END_REF], mean average precision, etc.). The MediaEval cost, used in 2011 as a basis for systems comparison, will still be computed for the sake of comparison with last year's results. However, as it has proven to be highly biased towards high precision rate values, it will be replaced by the computation of the mean average precision at the 20 top ranked violent shots. We nevertheless recall the definition of the MediaEval cost, which is a function weighting false alarms and missed detections, according to

C = C f a P f a + CmissPmiss (1)
with the costs C f a = 1 and Cmiss = 10. P f a and Pmiss are the estimated probabilities of resp. false alarm (false positive) and missed detection (false negative) given the system's output and the ground truth. In the shot classification, the false alarm and miss probabilities are then calculated on a per shot basis while, in the segment level run, they are computed on a per unit of time basis, i.e. durations of both references and detected segments are compared. To avoid only evaluating systems at given operating points and enable full comparison of the pros and cons of each system, we will use detection error trade-off (DET) curves whenever possible, plotting P f a as a function of Pmiss given a segmentation and a score for each segment, where the higher the score, the more likely the violence. Note that in the segment level run, DET curves are possible only for systems returning a dense segmentation (a list of segments that spans the entire video): segments not in the output list will be considered as non violent for all thresholds.

CONCLUSIONS

The Affect Task on Violent Scenes Detection in the context of the MediaEval 2012 benchmarking initiative has been presented. Dataset and groundtruth, specifications of the expected runs and evaluation criteria were detailed to give an overview of this new challenge.

The annotations, shot detections and key frames for this task were made available by Technicolor. Any publication using these data should acknowledge Technicolor's contribution.

supported, in part, by the Quaero Program http://www.quaero.org/.


Olivier Le Meur
email: olemeur@irisa.fr

Christine Guillemot
email: christine.guillemot@inria.fr

Super-Resolution-based Inpainting

Keywords:

This paper introduces a new examplar-based inpainting framework. A coarse version of the input image is first inpainted by a nonparametric patch sampling. Compared to existing approaches, some improvements have been done (e.g. filling order computation, combination of K nearest neighbours). The inpainted of a coarse version of the input image allows to reduce the computational complexity, to be less sensitive to noise and to work with the dominant orientations of image structures. From the low-resolution inpainted image, a single-image super-resolution is applied to recover the details of missing areas. Experimental results on natural images and texture synthesis demonstrate the effectiveness of the proposed method.

Introduction

Image inpainting refers to methods which consist in filling-in missing regions (holes) in an image [START_REF] Bertalmio | Image inpainting[END_REF]. Existing methods can be classified into two main categories. The first category concerns diffusion-based approaches which propagate linear structures or level lines (so-called isophotes) via diffusion based on partial differential equations [START_REF] Bertalmio | Image inpainting[END_REF][START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] and variational methods [START_REF] Chan | Variational restoration of non-flat image features: models and algorithms[END_REF]. Unfortunately, the diffusion-based methods tend to introduce some blur when the hole to be filledin is large. The second family of approaches concerns exemplar-based methods which sample and copy best matching texture patches from the known image neighborhood [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF][START_REF] Drori | Fragment-based image completion[END_REF][START_REF] Harrison | A non-hierarchical procedure for re-synthesis of complex texture[END_REF][START_REF] Barnes | PatchMatch: A randomized correspondence algorithm for structural image editing[END_REF]. These methods have been inspired from texture synthesis techniques [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] and are known to work well in cases of regular or repeatable textures. The first attempt to use exemplar-based techniques for object removal has been reported in [START_REF] Harrison | A non-hierarchical procedure for re-synthesis of complex texture[END_REF]. Authors in [START_REF] Drori | Fragment-based image completion[END_REF] improve the search for similar patches by introducing an a priori rough estimate of the inpainted values using a multi-scale approach which then results in an iterative approximation of the missing regions from coarse to fine levels. The two types of methods (diffusion-and exemplarbased) can be combined efficiently, e.g. by using structure tensors to compute the priority of the patches to be filled as in [START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF]. Although tremendous progress has been made in the past years on inpainting, difficulties remain when the hole to be filled is large and another critical aspect is the high computational time in general required. These two problems are here addressed by considering a hierarchical approach in which a lower resolution of the input image is first computed and inpainted using a K-NN (K Nearest Neighbours) examplar-based method. Correspondences between the K-NN lowresolution and high-resolution patches are first learnt from the input image and stored in a dictionary. These correspondences are then used to find the missing pixels at the higher resolution following some principles used in single-image super-resolution methods. Super-Resolution (SR) refers to the process of creating one enhanced resolution image from one or multiple input low resolution images. The two corresponding problems are then referred to as single or multiple images SR, respectively. In both cases, the problem is of estimating high frequency details which are missing in the input image(s). The proposed SR-aided inpainting method falls within the context of single-image SR on which we thus focus in this section. The SR problem is ill-posed since multiple high-resolution images can produce the same low-resolution image. Solving the problem hence requires introducing some prior information. The prior information can be an energy functional defined on a class of images which is then used as a regularization term together with interpolation techniques [START_REF] Dai | Softcuts: a soft edge smoothness prior for color image super-resolution[END_REF]. This prior information can also take the form of example images or corresponding LR-HR (Low Resolution -High Resolution) pairs of patches learnt from a set of un-related training images in an external database [START_REF] Freeman | Example-based super-resolution[END_REF] or from the input low resolution image itself [START_REF] Glasner | Super-resolution from a single image[END_REF]. This latter family of approaches is known as example-based SR methods [START_REF] Freeman | Example-based super-resolution[END_REF]. An examplebased SR method embedding K nearest neighbours found in an external patch database has also been described in [START_REF] Chang | Super-resolution through neighbor embedding[END_REF]. Instead of constructing the LR-HR pairs of patches from a set of un-related training images in an external database, the authors in [START_REF] Glasner | Super-resolution from a single image[END_REF] extract these correspondences by searching for matches across different scales of a multi-resolution pyramid constructed from the input lowresolution image. The proposed method thus builds upon earlier work on examplar-based inpainting in particular on the approach proposed in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF], as well as upon earlier work on single-image examplar-based super-resolution [START_REF] Glasner | Super-resolution from a single image[END_REF]. However, since the quality of the low-resolution inpainted image has a critical impact on the quality at the final resolution, the inpainting algorithm in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF] is first improved by considering both a linear combination of K most similar patches (K-NN) to the input patch rather than using simply the best match by template matching and K-coherence candidates as proposed in [START_REF] Ashikhmin | Synthesizing natural textures[END_REF]. The impact of different patch priority terms on the quality of the inpainted images is also studied, leading to retain a sparsitybased priority term. In addition, a new similarity measure based on a weighted Battacharya distance is introduced. In a second step, the patches to be filled within the input HR image are processed according to a particular filling order. The algorithm thus proceeds by searching for K nearest neighbours to the input vector concatenating the known HR pixels of the patch and the pixels of the corresponding inpainted LR patch. The K-NN patches are searched in a dictionary composed of LR-HR patches extracted from the known part of the image. The similarity metric is again the weighted Battacharya metric. Similarity weights are also computed between the input and K-NN vectors formed by the LR and known pixels of the HR patches. Finally, since the inpainted HR patches are overlapping, a seam is searched throughout the overlapping region, and the initially overlapping patches are thus pasted along this seam. In summary, the proposed method further advances the state-of-the-art in examplarbased inpainting methods by proposing:

a new framework which combines inpainting and super-resolution in a twostep approach improving the trade-off between quality and complexity; -improvements concerning the use of priority terms, the set of candidates (K-NN and K-coherence candidates) and distance metrics.

The paper is organized as follows. In Section II, the new framework of the proposed inpainting method is presented. Section III elaborates the proposed examplar-based inpainting and presents experimental results in comparison with those produced by with state-of-the-art methods. In Section IV, the details of the SR-aided inpainting method are introduced. Section V presents the performance of the proposed method as well as comparisons with state-of-the-art methods. Finally, we conclude this work in Section V.

Algorithm overview

Image completion of large missing regions is a challenging task. As presented in the previous section, there are a number of solutions to tackle the inpainting problem. In this paper, we propose a new inpainting method using a single-image SR algorithm. In the following sections, we briefly present the main ideas of this paper and the reasons why the proposed method is new and innovative.

Motivations

The proposed method is composed of two main and sequential operations.

The first one is a non-parametric patch sampling method used to fill-in missing regions. However, rather than filling in missing regions at the original resolution, the inpainting algorithm is applied on a coarse version of the input picture. There are several reasons for performing the inpainting on a low-resolution image. First, the coarse version of the input picture could be compared to a gist [START_REF] Oliva | Building the gist of a scene: the role of global image features in recognition[END_REF] representing dominant and important structures. Performing the inpainting of this coarse version is much easier since the inpainting would be less contingent on local singularities (local orientation for instance) or even noise. Second, as the picture to inpaint is smaller than the original one, the computational time to inpaint it is significantly reduced compared to the one necessary to inpaint the full resolution image.

The second operation is run on the output of the first step. Its goal is to enhance the resolution and the subjective quality of the inpainted areas. We use a single-image SR approach. Given a low-resolution input image, which is the result of the first inpainting step, we recover its high-resolution using a set of training examples, which are taken from the known part of the input picture. This new method is generic since there is no constraint on both the number and the type of inpainting methods used in the first pass. The better the inpainting of low-resolution images, the better the final result should be. Regarding the number of methods, one could imagine using different settings (patch size, search windows etc) or methods to fill-in the low-resolution images and to fuse results. We believe that it would increase the robustness and the visual relevance of inpainting, as recently proposed by Bugeau et al. [START_REF] Bugeau | A comprehensive framework for image inpainting[END_REF]. They have indeed shown that the best inpainting results are obtained by a combination of three different methods. In this paper, due to the limited space, we will not consider the possibility to combine the results of different inpainting algorithms, but rather focus on the proposed SR-aided inpainting framework.

Principle

Figure 1 illustrates the main concept underlying the proposed method. The two main components are the inpainting and the super-resolution algorithms. More specifically, the following steps are performed:

1. a low-resolution image is first built from the original picture; 2. an inpainting algorithm is applied to fill-in the holes of the low-resolution picture; 3. the quality of the inpainted regions is improved by using a single-image SR method.

Examplar-based inpainting of low-resolution images

This section presents the inpainting method which is used in this paper to fill in the low-resolution images. This is an adaptation of the Criminisi et al. [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF] method. The influence of different priority terms on the quality of the inpainted images is first studied. A similarity metric based on a weighted Bhattacharya distance is proposed. The resulting inpainting algorithm is compared against two state-of-the-art methods. The first one is also based on a non-parametric patch sampling (Patch Match, [START_REF] Barnes | PatchMatch: A randomized correspondence algorithm for structural image editing[END_REF]) whereas the second one is based on partial derivatives equations [START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF]. We have chosen these two methods because of their relevance and because the code is available. The proposed examplar-based method follows the two classical steps as described in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF]: the filling order computation and the texture synthesis. These are described in the next sections.

Patch priority and filling order

The filling order computation defines a measure of priority for each patch in order to distinguish the structures from the textures. Classically, a high priority indicates the presence of structure. The priority of a patch centered on p is just given by a data term (the confidence term proposed in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF] is not used here since it does not bring about any improvement). Three different data terms have been tested: gradient-based priority [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF], tensor-based [START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF] and sparsity-based [START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF].

The sparsity-based priority has been proposed recently by Xu et al. [START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF]. In a search window, a template matching is performed between the current patch ψ p and neighbouring patches ψ p,pj that belong to the known part of the image. By using a non-local means approach [START_REF] Wexler | Space-time video completion[END_REF], a similarity weight w p,pj (i.e. proportional to the similarity between the two patches centered on p and p j ) is computed for each pair of patches. The sparsity term is defined as:

D(p) = w p 2 × |N s (p)| |N (p)| (1)
where N s and N represent the number of valid patches (having all its pixels known) and the total number of candidates in the search window. When w p 2 is high, it means larger sparsity whereas a small value indicates that the current input patch can be efficiently predicted by many candidates. As illustrated in figure 2, the sparsity-based priority is more robust and visually improves the final result compared to the gradient and tensor-based priority. In the following, we adopt this method to compute the filling order.

Texture synthesis

The filling process starts with the patch having the highest priority. Two sets of candidates are used to fill in the unknown part of the current patch. A first set is composed of the K most similar patches located in a local neighbourhood centered on the current patch. They are combined by using a non-local means approach [START_REF] Wexler | Space-time video completion[END_REF]. The weighting factors are classically defined as follows:

w p,pj = exp - d(ψ p , ψ p,pj ) h (2)
where d() is a metric indicating the similarity between patches, and h is a decay factor. These weights are then normalized as w p,pj / k w p,p k . The number of neighbours is adapted locally so that the similarity of chosen neighbours lies within a range (1 + α) × d min , where d min is the distance between the current patch and its closest neighbour, α is equal to 0.75. As mentioned by [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF], a major problem of local neighbourhood search is its tendency to get stuck at a particular place in the sample image and to produce verbatim copying. This kind of regions is often called garbage region. This problem can be addressed by introducing some constraints in terms of spatial coherence.

The idea is based on the fact that patches that are neighbours in the input image should be also neighbours in the output image [START_REF] Ashikhmin | Synthesizing natural textures[END_REF][START_REF] Tong | Synthesis of bidriectional texture functions on arbitrary surfaces[END_REF]. Concerning the similarity measure, we have considered two metrics: the classical Sum of Squared Differences (d SSD ) and a weighted Bhattacharya distance as the one proposed in [START_REF] Bugeau | A comprehensive framework for image inpainting[END_REF] (d (SSD,BC) ). The last metric is defined as follows:

d (SSD,BC) (ψ p , ψ p,pj ) = d SSD (ψ p , ψ p,pj ) × (1 + d BC (ψ p , ψ p,pj )) (3)
where, d BC (ψ p , ψ p,pj ) is a modified version of the classical Bhattacharya distance as described in [START_REF] Bugeau | A comprehensive framework for image inpainting[END_REF] (d BC (ψ p , ψ p,pj ) = 1k p 1 (k)p 2 (k) where p 1 and p 2 represent the histograms of patches ψ p , ψ p,pj , respectively). This is not exactly the same formulation as in [START_REF] Bugeau | A comprehensive framework for image inpainting[END_REF]: indeed Bugeau et al. directly multiply the SSD distance with d BC . This presents a drawback: for two patches having the same distribution, no matter how the rotation the value d BC is null, leading to a null distance d (SSD,BC) . With the proposed metric, the distance is equal to the SSD distance.

Other state-of-the-art methods

To compare the proposed inpainting method to existing ones, we have chosen methods for which either the source code or an executable file are available.

Criminisi et al. method: Criminisi et al. [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF] proposed to guide the filling process with a priority term based on edge strength. A modified version of the Matlab software available on http://www.cc.gatech.edu/\mytildesooraj/ inpainting/ is used to perform the inpainting.

Diffusion-based method: as introduced earlier, diffusion-based methods propagate the structures into missing regions. For comparison purposes, we use in this paper the approach proposed in [START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF]. Patch Match: Published in 2009 [START_REF] Barnes | PatchMatch: A randomized correspondence algorithm for structural image editing[END_REF], the PatchMatch method is a fast algorithm for computing dense approximate nearest neighbour correspondences between patches of two image regions. This algorithm is available in Adobe Photoshop CS5 and works well. We will systematically compare our results to Patch Match'ones.

Note that we have also tested a method called tensor completion [START_REF] Liu | Tensor completion for estimating missing values in visual data[END_REF]. However, when the missing area is too large, the inpainting quality is low. We then put aside this method.

Comparison between proposed and state-of-the-art methods

Figure 4 (e) and (f) illustrate the performance of the proposed method on various low-resolution pictures. These pictures are downsampled versions of the original one (the down sampling factor is equal to 4 in both directions for (e) and equal to 2 for (f)). Results from [START_REF] Barnes | PatchMatch: A randomized correspondence algorithm for structural image editing[END_REF] and [START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] are also depicted. As expected, the diffusion-based approach retrieves the main structures of the scene (except for the third and fifth pictures). However, it tends to smooth the textured regions.

Results obtained by the proposed and the Patch Match methods are comparable although artefacts are not the same (for Patch Match: a man is duplicated (see second row) and some grass appears on the rock (last row); for the proposed method (e): the picture on the third row presents more artefacts).

Super-resolution algorithm

Once the inpainting of the low-resolution picture is completed, a single-image super-resolution approach is used to reconstruct the high resolution of the image. The idea is to use the low-resolution inpainted areas in order to guide the texture synthesis at the higher resolution. As in [START_REF] Freeman | Example-based super-resolution[END_REF], the problem is to find a patch of higher-resolution from a database of examples. The main steps, illustrated in figure 5 are described below:

1. Dictionary building: it consists of the correspondences between low and high resolution image patches. The unique constraint is that the high-resolution patches have to be valid, i.e. entirely composed of known pixels. In the proposed approach, high-resolution and valid patches are evenly extracted from the known part of the image. The size of the dictionary is a user-parameter which might influence the overall speed/quality trade-off. An array is used to store the spatial coordinates of HR patches (D HR ). Those of LR patches are simply deduced by using the decimation factor; 2. Filling order of the HR picture: the computation of the filling order is similar to the one described in Section 3. It is computed on the HR picture with the sparsity-based method. The filling process starts with the patch ψ HR p having the highest priority. This improves the quality of the inpainted picture compared to a raster-scan filling order; 3. For the LR patch corresponding to the HR patch having the highest priority, its K-NN in the inpainted images of lower resolution are sought. The number of neighbours is computed as described in the previous section. The similarity metric is also the same as previous; 4. Weights w p,pj are calculated by using a non-local means method as if we would like to perform a linear combination of these neighbours. However, the similarity distance used to compute the weights is composed of two terms: the first one is classical since this is the distance between the current LR patch and its LR neighbours, noted d(ψ LR p , ψ LR p,pj ). The second term is the distance between the known parts of the HR patch ψ HR p and the HR patches corresponding to the LR neighbours of ψ LR p . Say differently, the similarity distance is the distance between two vectors composed of both pixels of LR and HR patches. The use of pixel values of HR patches allows to constraint the nearest neighbour search of LR patches. 5. A HR candidate is finally deduced by using a linear combination of HR patches with the weights previously computed:

ψ HR p = pj ∈D HR w p,pj × ψ p,pj (4)
with the usual conditions 0 ≤ w p,pj ≤ 1, and k w p,p k = 1. 6. Stitching: the HR patch is then pasted into the missing areas. However, as an overlap with the already synthesized areas is possible, a seam cutting the overlapped regions is determined to further enhance the patch blending.

The minimum error boundary cut [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF] is used to find a seam for which the two patches match best. The similarity measure is the Euclidean distance between all pixel values in the overlapping region. More complex metrics have been tested but they do not substantially improve the final quality. At most four overlapping cases (Left, Right, Top and Bottom) can be encountered.

There are sequentially treated in the aforementioned order. The stitching algorithm is only used when all pixel values in the overlapping region are known or already synthesized. Otherwise, the stitching is disabled.

After the filling of the current patch, priority value is recomputed and the aforementioned steps are iterated while there exist unknown areas.

Experimental results

In order to assess the performance of the proposed approach, the parameters of the algorithm are kept constant for the tests presented in this paper.

Implementation details and parameters

Reproducible research: It is possible to reproduce results by using the executable software, the masks and pictures available on authors' web page. Parameters: Two versions of the proposed method are evaluated. One uses a down sampling factor of 4 in both directions (the patch size is equal to 5 × 5) whereas this factor is set to 2 for the second version (the patch size is equal to 7 × 7). For both versions, the size of the dictionary is the same and can contain at most 6000 patches evenly distributed over the picture. The LR patch size is 3 × 3 and the HR patch size is 15 × 15.

Line front feathering: in spite of the use of stitching method, the front line which is the border between known and unknown areas can still be visible. It is possible to hide this transition by feathering the pixel values across this seam.

A Gaussian kernel is used to perform the filtering.

Comparison with state-of-the-art methods

Figure 6 illustrates the comparison between the proposed methods and state-ofthe-art methods. The proposed method (for both settings (e) and (f)) provides similar results to Patch Match and visually outperforms Criminisi's approach. Figure 8 gives further results. For these examples, a large missing area has been filled in. Figure 7 presents additional results for texture synthesis. A small chunk of texture (in the example 256 × 256) was placed into the upper left corner of an empty image. Figure 7 illustrates the performance of the proposed method for these kinds of texture. For deterministic textures, results are very good. For stochastic ones, some artefacts are visible. However, increasing the patch size would cope with these artefacts, as illustrated on the bottom-right of figure 7.

The running time on a 3 GHz CPU is less than one minute for pictures having a resolution of 512 × 512.

Conclusion

In this paper we have introduced a new inpainting framework which combines non-parametric patch sampling method with a super-resolution method. We first propose an extension of a well-known examplar-based method (improvements are sparsity-based priority, K-coherence candidates and a similarity metric adapted from [START_REF] Bugeau | A comprehensive framework for image inpainting[END_REF]) and compare it to existing methods. Then, a super-resolution method is used to recover a high resolution version. This framework is interesting for different reasons. First the results obtained are within the state-of-the-art for a moderate complexity. Beyond this first point which demonstrates the effectiveness of the proposed method, this framework can be improved. For instance, one interesting avenue of future work would be to perform several inpainting of the low-resolution images and to fuse them by using a global objective function. First, different kinds of inpainting methods (patch-based or PDE-based) could be used to fill-in the missing areas of a low-resolution image. Second, for a given inpainting method, one can envision to fill-in the missing areas by using different settings e.g. for the patch size in order to better handle a variety of textures and to better approach the texture element sizes. Finally, we believe that the proposed framework will be appropriate for video completion. This application is indeed very time-consuming. The use of the proposed framework could dramatically reduce the computational time.

Acknowledgment

This work is supported by the ANR-PERSEE project.

Fig. 1 .

 1 Fig. 1. The framework of the proposed method.

Fig. 2 .

 2 Fig. 2. Inpainting of LR pictures with different gradient-based priority [4] (first row), tensor-based priority [9] (second row) and sparsity-based priority [17] (third row).

Figure 3

 3 a) illustrates this process. With a 8-connexity neighbourhood centered on the current patch (noted C on figure3 a)), K i patches are used as candidates and compared to the best candidate obtained by the local neighbourhood search. Figure3 b) and c) show the influence of the k-coherence method on the quality of the low-resolution inpainted image. The use of k-coherence candidates improves locally the quality on many parts of the pictures.

Fig. 3 .

 3 Fig. 3. (a) K-coherence algorithm: candidates shown in orange are used as predictors; (b) and (c) are inpainted images when the k-coherence method is disabled or enabled respectively. Green circles stress the major differences between pictures (b) and (c).

Fig. 4 .

 4 Fig. 4. (a) low-resolution pictures with missing areas in black; (b) Criminisi et al.'s results; (c) Patch Match results; (d) Diffusion-based results; (e) Proposed method (the down sampling factor is set to n = 4; patch size is 11 × 11); (f) Proposed method with n = 2 and patch's size of 15 × 15.

Fig. 5 .

 5 Fig. 5. Flowchart of the super-resolution algorithm. The missing parts of the red block is filled by a linear combination of K HR-candidates (green arrows). The weights are computed using the similarity distance between LR and HR patches (green and red arrows, respectively). The top image represents the original image with the missing areas whereas the bottom one is the result of the low-resolution inpainting.

Fig. 6 .

 6 Fig. 6. Comparison of the proposed method with state-of-the-art approaches: (a) Criminisi et al. [4]; (b) Patch Match [7]; (c) proposed method (n = 4), (n = 2) (f).

Fig. 7 .

 7 Fig. 7. Texture synthesis (down sampling factor n = 2).

Fig. 8 .

 8 Fig.8. For these pictures, a large missing region has been inpainted (masks are not intentionally given but are available as supplementary materials).


Cédric Penet

Claire-Hélène Demarty

Mohammad Soleymani
email: m.soleymani@imperial.ac.uk

Guillaume Gravier

Patrick Gros
email: patrick.gros@inria.fr

Technicolor/INRIA/Imperial College London at the MediaEval 2012 Violent Scene Detection Task * †

This paper presents the work done in Technicolor, INRIA and Imperial College London regarding the Affect Task at MediaEval 2012. This task aims at detecting violent shots in movies. Four different systems and a fusion of three of them are proposed in this paper.

INTRODUCTION

The MediaEval 2012 Affect Task is the continuation of the MediaEval 2011 Affect Task and aims at detecting violence in movies. A complete description of the task and datasets may be found in [START_REF] Demarty | The MediaEval 2012 Affect Task: Violent Scenes Detection[END_REF].

This paper is a joint effort between Technicolor, INRIA and the Imperial College of London. The different systems used are presented in section 2 and the results are discussed in section 3.

SYSTEMS DESCRIPTION

In this section, we briefly present the different systems behind each run for this year's task.

Run #1: Similarity

The idea that motivated the method for run #1 is to check whether it is feasible to achieve comparable results to those of the 2011 campaign using only a similarity measure between the training and test sets. Besides avoiding the use of machine learning techniques, this run is an attempt, given a new event, to classify it simply by measuring the similarity between this event and some violent and non violent events. The final decision is made using a knn scheme, measuring the shortest distance between the event and his neighbours and their labels. For each event, a set of only 4 video features was used: three color harmonization features (an harmonization template, its corresponding angle and a minimum energy value [START_REF] Cohen-Or | Color harmonization[END_REF]) and a motion activity measure over each frame were computed and then agregated over one shot, by either taking a maximum voting scheme (harmonization template), or an average value over all frames (angle, energy or motion activity). We used a set of 10 movies from the learning database to create some frame clusters, using the lib-pq and yael software detailed in [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. Each frame of the three test movies was then labeled according to its closest neighbour's label. The final decision at shot level was made by simply labelling any shots with at least one violent frame as violent.

Run #2: Bag of Audio Words

For this run, TF-IDF Bag of Audio Words (BoAW) were used as features. First, we extracted spectrum coefficients using a 24 filterbank along with the deltas and accelerations on 20 ms audio frames with 10 ms overlap. Then, spectrally coherent audio segments were extracted using [START_REF] Andre-Obrecht | A new statistical approach for the automatic segmentation of continuous speech signals[END_REF], the silence segments were removed using Spro1 and all 20ms audio frames lying within each segment were averaged. In order to produce audio words, the yael implementation of K-Means was used [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. 128 clusters were extracted from the 15 development movies, and one cluster was added for silence segments. We finally extracted TF-IDF histograms [START_REF] Jones | A statistical interpretation of term specificity and its application in retrieval[END_REF] considering that each shot is a document. For classification, we used SVM with Histogram Intersection kernel (HIK) and Chi-squared kernel (χ 2 ):

KHIK (x, y) = D k=0 min(x k , y k ) (1) K χ 2 (x, y) = D k=0 x k * y k 2(x k + y k ) 2 (2)
where x, y ∈ ℜ D , and x k is the k th element of x. In order to obtain confidence scores to compute the Mean Average Precision at 100 (MAP@100), a sigmoid function was applied to the distance of each sample to the classification hyperplane.

A grid search was applied on the SVM parameter C, and to cope with the imbalance data problem, the C parameter for violent samples was set to 10 * C. In cross-validation over the development set, the best MAP@100 was obtained for the χ 2 kernel, with a weight of 10 for violent samples and C = 2 -6 . The value reached for the MAP@100 is 44.77% and the standard deviation (STD) over all movies is 15.01%.

Run #3: Bayesian Networks

The method presented in [START_REF] Penet | Multimodal information fusion and temporal integration for violence detection in movies[END_REF] and developed for the Me-diaEval 2011 campaign was used again with more features and a new temporal filter. For the video modality, color coherence and color harmonisation [START_REF] Cohen-Or | Color harmonization[END_REF] features were added, which brings the number of features from 4 up to 10. For the audio modality, only the roll-off at 90% was added.

We employed a majority vote post-processing filter that works over a window of size n (we used n = 5). For the confidence scores, we consider two cases, depending on whether the maximum vote is violent or non violent:

Violent The confidences of the non violent samples are set to min(P (Sv)) where P (Sv) is the set of confidences of the violent samples within the window.

Non violent

The confidences of the violent samples are set to max(P (Snv)) where P (Snv) is the set of confidences of the non violent samples within the window.

As in [START_REF] Penet | Multimodal information fusion and temporal integration for violence detection in movies[END_REF], the parameters and configurations are chosen based on the system's performance in a one-movie-out cross-validation on the development set. The best system configuration, with a MAP@100 of 43.18% and a STD of 18.67%, was obtained using late fusion with the following configuration:

Audio K2-learned structure with non contextual features and the new temporality.

Video Naive structure with contextual features and the new temporality.

Late Fusion Averaging filter applied to the confidence scores.

Run #4: Imperial College

The system implemented by UniGe in Mediaeval 2011 [START_REF] Gninkoun | Automatic Violence Scenes Detection: A multi-modal approach[END_REF] was re-implemented with a refined set of features. The results of text features on the training set were not satisfactory. Therefore, only audio and visual modalities were used after a weighted decision level fusion. Naïve Bayesian classifiers' confidence scores were added using the weights obtained based on the best results on one-movie-out cross validation on the development set. The weight for the audio modality was set to 0.95 and the visual modality weight was set to 0.05 respectively. Although the confidence scores of naïve Bayesian classifiers are not reliable in case of redundant features, feature reduction techniques such as Principal Component Analysis failed to improve the MAP on the development set.

Run #5: Classifier fusion

For this system, the results from runs #2, #3 and #4 were fused by simply multiplying the confidence scores with the effect of reducing the false alarms rate.

RESULTS AND DISCUSSION

Table 1 presents the results obtained on the test set. The first noticeable point from this table is the high average precision (AP) variation between the different movies. This first result highlights clearly the difficulty of the task, as well as the high variability of violence between movies. It is also interesting to note that for runs #1 and #2, the movie that have the worst result is the least violent movie (according to the definition), i.e., "Dead Poet Society". The inferior results on "Fight Club" compared to "Independence Day" can be due to the nature of the violent events present in these movies. Violent actions such as fist fight in "Fight Club" are under-represented in the training set whereas the Table 1:

Results for submitted runs (MAP: MAP@100, AP: average precision for "Deap Poet Society" (AP-1), "Fight Club" (AP-2) and "Independence Day" (AP-3), STD is the standard deviaton over the test movies and MC11: MediaEval Cost from 2011 campaign).

Run The best performing run is the third run using a Bayesian network with temporal integration post-processing. This further emphasizes the importance of multimodal approaches as well as the value of taking into account the temporal dimension. Nevertheless, this result might not generalize over a larger development set since the obtained MAP is almost 20% higher than the cross-validation MAP. Indeed, the standard deviation and mean might have more meaning if extracted on more test movies.

Finally, run #1 has proved that using only a similarity measure between such events is worth begin further tested. Although the MAP@100 value is not so good and it used a really small set of features, the MC11 is one of the best among all the participants.

https://gforge.inria.fr/projects/spro

* This work was partly achieved as part of the Quaero Program, funded by OSEO, French State agency for innovation. † The work of Soleymani is funded by European Research Council under the FP7 Marie Curie Intra-European Fellowship, EmoTag.


Florian Metze
email: fmetze@cs.cmu.edu

Etienne Barnard

Marelie Davel

Charl Van Heerden

Xavier Anguera
email: xanguera@tid.es

Guillaume Gravier

Nitendra Rajput
email: rnitendra@in.ibm.com

The Spoken Web Search Task

Keywords: H.3 [Information Storage and Retrieval]: Content Analysis and Indexing Algorithms, Performance, Experimentation, Languages Spoken Term Detection, Zero-Resource Techniques

In this paper, we describe the "Spoken Web Search" Task, which is being held as part of the 2012 MediaEval campaign. The purpose of this task is to perform audio search in multiple with very little resources being available for each individual language. The data is being taken from audio content that was created in live and realistic low-resource settings.

INTRODUCTION

The "Spoken Web Search" task of MediaEval 2012 [3] involves searching for audio content within audio content using an audio content query. The task requires researchers to build a languageindependent audio search system so that, given an audio query, it should be able to find the appropriate audio file(s) and the (approximate) location of a query term within the audio file(s). Evaluation is performed using standard NIST metrics [START_REF] Fiscus | Results of the 2006 Spoken Term Detection Evaluation[END_REF]. The 2012 evaluation expands on the MediaEval 2011 "Spoken Web Search" task [START_REF] Metze | The Spoken Web Search task at MediaEval 2011[END_REF], adding more evaluation conditions, and a new "African" dataset as the primary evaluation corpus.

As contrastive condition, participants can submit systems not based on an audio query. Note that language labels and pronunciation dictionaries were not provided for any evaluation data. The lexical form of the query cannot be used to deduce the in the audio-only condition. The goal of the task is primarily to compare the performance and limitations of different approaches on this type of task and data, not so much a performance comparison between different sites.

MOTIVATION

Imagine you want to build a simple speech recognition system, or at least a spoken term detection (STD) or keyword search (KWS) system in a new dialect or language, for which only very few audio examples are available. Maybe there even is no written form for that dialect or language? Is it possible to do something useful (i.e. identify the topic of a query) by using only those very limited resources available? Full speech recognition may be unrealistic to be used for such a task, but it may not be required to solve a specific information access or search problem.

RELATED WORK

This task has originally been suggested by IBM Research India, and the 2011 data was provided by this group, see [START_REF] Diao | Faceted Search and Browsing of Audio Content on Spoken Web[END_REF]. In 2012, the evaluation is performed on new data [START_REF] Barnard | ASR Corpus design for resource-scarce languages[END_REF]; participants are given access to the 2011 data to allow them to gauge their systems.

TASK DESCRIPTION

Participants receive development and evaluation utterances (audio data) as well as development and evaluation (audio) queries, described in more detail below. Only the occurrence of development queries in development utterances is provided.

Participants are required to submit the following runs in the audioonly condition, without exploiting the textual form of the queries:

• On the evaluation utterances: identify which query (from the set of development queries) occurs in each utterance (0-n matches per term, i.e. not every term necessarily occurs, but multiple matches are possible per utterance)

• On the evaluation utterances: identify which (evaluation) query occurs in each utterance (0-n matches)

• On the development utterances: identify which evaluation query occurs in each utterance (0-n matches)

The purpose of requiring these three conditions is to see how critical tuning is for the different approaches, i.e., we assume that participants already know their performance for "development queries" on "development utterances", so for evaluation we will evaluate the performance of unseen "evaluation queries" on previously known "evaluation utterances" (which could have been used for unsupervised adaptation, etc), known queries (for which good classifiers could have been developed) on unseen data, and unseen queries on unseen utterances. There may be partial overlap between evaluation and development queries.

Optionally, participants can submit the same runs also using the provided lexical form (not the phonetic transcription) of the query, i.e. they could use existing speech recognition systems, etc., for comparison purposes. Participants can submit multiple systems, but need to designate one primary system. Participants are encouraged to submit a system trained only on data released for the 2012 SWS task, but are allowed to use any additional resources they might have available (with one exception for 2012), as long as their use is documented.

Development Data

Participants are provided with two distinct datasets. The 2011 "Indian" data has been kindly made available by the Spoken Web team at IBM Research, India [4]. The audio content is spontaneous speech that has been created over phone in a live setting by low-literate users. While most of the audio content is related to farming practices, there are other domains as well. The data set comprises audio from four different Indian languages: English, Hindi, Gujarati and Telugu. Each data item is ca. 4-30 seconds in length. The development set contains 400 utterances (100 per language) and 64 queries (16 per language), all as audio files recorded in 8kHz/ 16bit, as WAV file. For each query and utterance, the organizers also provided the lexical transcription.

For each utterance, the organizers provide 0-n matching queries (but not the exact location of the match).

The "African" data consists of 1580 audio files (395 per language) from isiNdebele, Siswati, Tshivenda, and Xitsonga, and 100 example queries in these languages with overall similar characteristics to the "Indian" data. These were also collected over a telephone channel [START_REF] Barnard | ASR Corpus design for resource-scarce languages[END_REF] and provided as 8kHz/ 16bit WAV files.

No language labels or pronunciation dictionaries are provided by default, although these are available for contrastive experiments. The locations of the occurrences are being provided.

Evaluation Data

For the 2011 "Indian" data, the test set consists of 200 utterances (50 per language) and 36 queries (9 per language) as audio files, with the same characteristics. As with the development data, the lexical form of the query was provided, but not the matching utterances. The 2012 "African" dataset consists of 1660 audio files and 100 queries (transcribed with 170 words), from 4 languages (25 queries per language).

Data is being provided as a "termlist" XML file, in which the "termid" corresponds to the filename of the audio query. This information is packaged together with the scoring software ,e.g.:

<?xml version="1.0" encoding="UTF-8"?> <termlist ecf_filename="expt_06_std_dryrun06_ eng_all_spch_expt_1.ecf.xml" ... > <term termid="DryRun06_eng_0001"><termtext> "years"</termtext></term> </termlist>

EVALUATION OF RESULTS

The ground truth was created manually by native speakers, and provided by the task organizers, following the principles and using the tools of NIST's Spoken Term Detection (STD) evaluations. The primary evaluation metric was ATWV (Actual Term Weighted Value), as used in the NIST 2006 Spoken Term Detection (STD) evaluation [START_REF] Fiscus | Results of the 2006 Spoken Term Detection Evaluation[END_REF].

On development data, the systems can be scored using the software provided in the me2012-scoring-beta3.tar.bz2 archive available on the FTP server, as described in the MediaEval Task Wiki. This software allows participants to verify themselves that the organizers can process their output for scoring, and reports the respective figure of merit plus graphs the development data. For evaluation, participants will mail their output on development and evaluation data to the organizers, who compute the results. Because the 2011 evaluation data has already been distributed to the community in the past, it is designated as a contrastive dataset for 2012, and is provided so that participants can compare their results to published work. Participants should however focus on the larger "African" data, and treat the "Indian" data as a "progress" set, even if this use cannot be mandated by the organizers.

For 2012, the NIST-compatible reference files are generated on automatically aligned transcriptions. The trade-off parameters are set so that equal weight is being put on missed detections and false alarms, given the known number of occurrences of search terms in the respective data sets. These parameters are different for each evaluated reference and query set and are set in evaluation scripts. Other weighting schemes may be investigated during the evaluation as diagnostic runs.

OUTLOOK

Spoken Web Search and similar technology is primarily targeted at communities whose members do not have Internet access, have low literacy levels, or speak in traditional languages for which good speech technology does not exist. Low (or even zero) resource speech recognition is currently receiving a lot of attention, because it could be a useful contribution in these, and other settings. We will discuss evaluation outcome and future directions at the workshop and in future publications.

ACKNOWLEDGMENTS

The organizers would like to thank Martha Larson for organizing this event [3], and the participants for putting in a lot of hard work into submitting their systems. The "African" data [5] has kindly been collected by CSIR and made available by NWU.