John Smith

Keywords: Fingerprint computation Fingerprint computation Identity: Video fingerprints, uniqueness, robustness, database search efficiency, distortions, grayscale conversion, linear or non-linear filtering, geometric transformations, live camcorder recording 2D-DWT coefficients, normalized cross-correlation, Rho test on correlation, localization, bag of visual words, synchronization Video fingerprinting theoretical model, theoretical limits for video fingerprinting systems, information theory model robust video fingerprinting, DWT, robustness, uniqueness, live camcorder recording uniqueness, robustness, scalability, bag of visual words, wavelets, synchronization, distortions, computer generated distortions, brightness increase/decrease, contrast decrease, conversion to grayscale, Gaussian filtering, sharpening, rotations with 2, StirMark live camcorder recording generated distortions

Context

With the advent of affordable devices (capturing, processing, storage) and with the wide spread of broadband Internet access, massive amount of video content is produced and disseminated instantaneously. Hence, efficient tools for searching, retrieving and tracking video content in very large video databases (e.g. YouTube) have to be deployed in order to serve the purposes of applications like copyright protection, parental control, etc. Moreover, augmented reality turns live camcorder recorded video into a challenging research topic. Live camcorder recording (or, live camcording) is the process through which some video content displayed on a screen (in theaters, on a TV set, on an advertising display, …) is captured with an external camera.

A potential solution intensively considered in research studies is video fingerprinting. Video fingerprints are compact and salient video features computed from the video itself and which can uniquely identify it.

Acknowledgment

Three years ago, as a young engineer in search of the great knowledge I was starting my PhD program. This work could not have been accomplished and I couldn't have learned all that I have learned without the help and collaboration of numerous people.

My deep gratitude goes to my thesis director, Professor Françoise Prêteux for the warm welcome she gave me for the first time in the ARTEMIS department at Institut Telecom, Telecom SudParis and for the second time in the CAOR department of MINES ParisTech. I would like to thank her for her trust and for seeing in me the future PhD. She taught me the lesson of hard work and precision in research activities and therefore I would like to express my appreciation for her help in broadening my technical skills, for her guidance and constant support.

Equally, my deep gratitude goes to my thesis co-director, HDR Mihai Mitrea for introducing me in the fascinating world of information theory while a student at POLITEHNICA University of Bucharest and then for granting me the chance to start the research work at ARTEMIS on the novel and exciting topic of video fingerprinting. I would like to express my profound appreciation and special thanks for his step by step guidance of the thesis, for his expertise, energy and enthusiasm that he invested in working with me, in providing me with the theoretical research tools as well as with the necessary logistic and administrative resources. I would also like to express my admiration and respect for Mr. Mitrea's passion and hard work for his research activity and for his dedication to his co-workers which highly inspired me and contributed to the success of this thesis.

I would like to express my gratitude and special thanks to Professor Adriana Vlad from POLITEHNICA University of Bucharest for granting me the honor of being a reviewer of my thesis, for her constant help throughout my student activity, her genuine interest in my work and the perspectives she envisioned for the thesis. My gratitude and special thanks go to Professor Arnaud Reichart, deputy director at ENSTA ParisTech for granting me the honor and accepting the difficult task of reviewing the thesis, for the time and attention he dedicated to my thesis in the meeting that preceded the defense and for his insightful advice on the perspectives of the work. I would like to thank Professor Christine Graffigne from the René Descartes University Paris for the honor of chairing the jury, for the time, patience and expertise she invested in evaluating my work. I would like to thank HDR Claude Delpha from Paris-Sud University for the time he spent in evaluating the work, for his thoughtful comments and kind advice for the perspectives of the thesis. I would like to express my appreciation to Mr. Benoît Maujean, R&D Head responsible at Mikros Image for bringing the industry and strategic point of view in the evaluation of the thesis and during the development of the HD3D2 project. I would like to thank Mr. Arnaud de La Fortelle, Director of the CAOR Department and Mr. François, Goulette, coordinator of the thesis program at CAOR, who welcomed me at the CAOR Department of MINES ParisTech and for their interest they showed for my work during the Doctorades. I would like to express my appreciation to all the partners of the HD3D2 project for their help and support during the project meetings and for the availability of the HD3D-IIO video corpus (the testing corpus of the present thesis). Especially I would like to thank the two industrial partners who were particularly involved on the applicative side of the work, namely Mikros Image, through Mr. Benoît Maujean and Mr. Guillaume Chatelet and the CST (Commission Supérieure Technique de l'Image et du Son) through Mr. Rip O'Neil.

I would like to thank Mrs. Evelyne Taroni for her proactive attitude and valuable help with the administrative matters at the ARTEMIS department, and for the kind and informal French lessons I had when I went in her office. I would also like to thank Mrs. Christine Vignaux and Mrs. Sylvie Barizzi-Loisel from the CAOR department for their valuable help in the administrative matters. Special thanks: To Raluca Sambra for her generous help and very useful discussions on many image processing matters and beyond. To Thomas Laquet for his efficient help with the demos. To Afef Chammem and Sameh Hamrouni for their friendship and optimism day by day at the office. To Bojan Joveski, for being an exemple of patience and positive attitude towards work and people and for sharing his good spirit with me and with the colleagues.

I would also like to thank the entire ARTEMIS team, former and present members that I have met and who have contributed sometimes from the ARTEMIS offices, sometimes from far away to my work and who have all taught me something.

Video fingerprints can be best defined in relation to the human fingerprints, as illustrated in Figure 1. While the human fingerprint can be seen as a human summary (a signature) that is unique for every person, the video fingerprint can be seen as some short video feature (e.g. a string of bits with no particular format constraint) which can uniquely identify that video.

Scientific and technical challenges

Fingerprinting methods have three main characteristics:  Robustness to distortions: fingerprints extracted from a video subjected to contentpreserving distortions (attacked video) should be similar to the fingerprints extracted from the original video. Such attacks may include gray-scale conversion, linear or nonlinear filtering, geometric transformations, etc. The robustness property is also quantified by two objective evaluation criteria, namely the probability of missed detection (P md ) and the recall rate (Rec).

 Uniqueness: fingerprints extracted from different video clips should be considerably different. This property is assessed by two objective evaluation criteria: the probability of false alarm (P fa ) and the precision rate (Prec).

 Database search efficiency: for applications with a large scale database, fingerprints should be conducive to efficient database search (fast fingerprint computation and matching, compact form, …), resulting in scalable solutions.

iv

Current limitations

The fingerprinting state-of-the-art covers a large area of methodological tools from pixel difference of consecutive frames or RGB histograms to transform domain based fingerprinting approaches. However, despite the wide range of such methods, open research topics are still connected to each of the three above mentioned scientific challenges, see Table 1.

First, concerning the uniqueness, the state-of-the-art methods are generally constructed on heuristic basis and, with singular exceptions, tested on limited databases. Consequently, their mathematical basis (if any) comes rather as an a posteriori validation than as a true demonstration of the results. Secondly, to our best knowledge, no fingerprinting method was yet reported to withstand the live in-theater camcorder recording. Finally, the scalability issue, sine qua non for the content distribution on Internet can currently be obtained only at the expense of the uniqueness / robustness proprieties.

Moreover, these methods are generally tested on TV content data sets and don't take into account the particularities of the cinema content characterized by very high quality and presenting a high dynamics of the visual content, outdoor/indoor scenes and arbitrarily changing lighting conditions.

Methodological contributions and achievements

The present thesis takes a different approach and advances a novel DWT (discrete wavelet transform)-based video fingerprinting method involving a mathematical decision rule for the detection of replicas.

The fingerprint per-se is represented by a set of 2D-DWT coefficients of frames sampled from the video sequence. An in-depth statistical investigation on the 2D-DWT coefficients demonstrated not only the stationarity of such coefficients but also the stationarity of their modifications under the computer-simulated camcorder attacks.

Through its accurate representation of visual content, the wavelet transform grants the fingerprints the uniqueness property and limits the occurrences of false alarms (i.e. fingerprints extracted from different video content have to be different). The fingerprint matching is done based on a repeated Rho test on correlation which allows the detection of replicas, hence ensuring the robustness property (i.e. fingerprints extracted from an original video sequence and its replicas should be similar in the sense of the considered similarity metric).

In order to make the method efficient in the case of large scale databases, a localization algorithm is employed. Consequently, the replica sequence is not matched to the entire reference video collection but only with a few candidates determined based on a bag of visual words representation (concept introduced by Sivic and Zisserman in 2003) of the video keyframes. An additional synchronization mechanism able to address the strong distortions from difficult use-cases such as camcorder recording in cinema was also designed.

v

The method scalability is granted by the localization and synchronization procedures and by its low complexity which is kept under the ) log ( n n O limit.

Summarizing, the contributions of the thesis are threefold:

 a novel fingerprinting feature with a new mathematical matching procedure;  a dynamic synchronization block addressing for the first time the live camcorder recording;  a bag of visual words algorithm employed for granting the fingerprinting system scalability to large scale databases;

Functional evaluation

This method is evaluated in industrial partnership with professional players in cinematography special effects (Mikros Image) and with the French Cinematography Authority (CST -Commission Supérieure Technique de l'Image et du Son).

Two use cases have been incrementally considered: (1) computer generated replica video retrieval and (2) live camcorder recorded video retrieval. The reference dataset was composed of 14 hours of video content from different movies produced in Ile de France (e.g. Asterix), under the framework of the HD3D-IIO and HD3D2 CapDigital Competitiveness Cluster Projects. The query dataset was organized differently for each use case. For computer generated replica video retrieval, the query dataset consists of 24 hours of replica video content generated obtained by applying eight types of distortions (i.e. brightness increase/decrease, contrast decrease, conversion to grayscale, Gaussian filtering, sharpening, rotations with 2°, stirMark) on 3 hours of original video content from the reference dataset. For the live camcorder recording, the query corpus consisted of 1 hour of live camcorder recorded video content from the reference dataset.

The inner 2D-DWT properties with respect to content preserving attacks (such as linear filtering, sharpening, geometric, conversion to grayscale, small rotations, contrast changes, brightness changes, live camcorder recording), ensure the following results: in the first use case the probability of false alarm reached its null ideal value whereas the missed detection was lower than 0.025, precision and recall were higher than 0.97; in the second use case, the probability of false alarm was 0.000016, the probability of missed detection was lower than 0.041, precision and recall were equal to 0.93

In the absence of a clear benchmarking between state-of-the-art video fingerprinting methods (different testing data sets), the performances of the proposed fingerprinting system have been set by the industrial partners Mikros and CST to lower than 5% for the probability of false alarm and missed detection and higher than 95% for the precision and recall.

Considering the first case the performance limits have been successfully met by the proposed method, whereas considering the second use case, the precision and recall performances although feature satisfactory results, still need to be improved with 2%.

vi

Thesis structure

The present manuscript is structured in four main parts related to the video fingerprint overview, the proposed video fingerprinting method, the evaluation of the proposed method and to the conclusions which can be formulated, respectively.

Part I (Video fingerprinting overview) is composed by six sections (numbered from I.1 to I.6) and covering an introduction to the video fingerprinting: the main underlying definitions, a theoretical properties and requirements, a general panorama of the applicative and industrial use cases as well as state of the art on the research studies. The concluding section summarizes the open research challenges versus the current day methodological limitations

Part II is devoted to the specification of the TrackART, the new fingerprinting method advanced in the thesis. Its synoptic presentation (Section II.1) is followed by the detailed definitions of its building blocks, structured according to the offline (Section II.2) and online (Section II.3) blocks. Section II.4 considers two possible TrackART functional configurations: TrackART Full Fingerprint and TrackART Reduced Fingerprint. These two configurations are considered as a solution for reaching a potential trade-off among not only uniqueness, robustness and scalability but also fingerprint length. The TrackART key features are summarized in the concluding Section II.5.

Part III describes the experimental validation. The context of the study ( the HD3D2 competitiveness cluster project in Ile de France) and the processed corpus are presented in Section III.1. On this occasion, two fingerprinting use cases are stated by the two industrial partners, namely the retrieval of video sequences under computer generated distortions by Mikros Image and the live camcorder recording use case by CST. The uniqueness and robustness experimental results corresponding to the two use cases and to the two TrackART configurations are presented and discussed in Section III.3-4. The computational cost (invariant with respect to the use case) is analyzed in Section III.5. Section III.6 briefly introduces a software demonstrator meant to accustom a novice user with the video fingerprinting basic concepts. The conclusions on the quantitative results are drawn in Section III.7.

Although each part of the thesis contains detailed conclusions, Part IV gives a retrospective view on the thesis main contribution and presents the direction for future work.

The thesis has three Appendices which contain visual illustrations of the online localization block (procedure included in the TrackART method, detailed in Section II.3.2), the list of publications co-authored by the PhD candidate and a selection of these publications.

vii Le traçage du contenu vidéo est réalisé à partir des empreintes numériques qui sont des caractéristiques compacts et saillantes extraites à partir du vidéo contenu lui même, et qui peuvent identifier une séquence vidéo de manière unique.

Les méthodes de traçage ont trois propriétés principales. La première propriété est l'unicité, c'est-à-dire les empreintes numériques extraites de différents clips vidéo doivent être considérablement différentes. La seconde propriété est la robustesse aux distorsions, c'est-à-dire, les empreintes numériques extraites d'une vidéo soumise à différentes distorsions préservant le contenu visuel doivent être similaires aux empreintes d'origine. Des telles distordions peuvent inclure la conversion en niveaux de gris, le filtrage linéaire ou non linéaire, les transformations géométriques, ou bien l'enregistrement en salle de cinéma. La troisième propriété est la scalabilité, c'est-à-dire pour les applications vouées au traitement des bases des données à grande échelle, les empreintes numériques doivent être propices à une recherche efficace dans ces bases (calcul rapide des empreintes numériques, appariement rapide, forme compacte, ...).

L'analyse de l'état de l'art pour le traçage de la vidéo met en exergue qu'il y a encore des défis à adresser pour chacune des propriétés mentionnées ci-dessus. Tout d'abord, concernant l'unicité, les méthodes de l'état de l'art sont généralement construites sur des bases heuristiques et, à quelques exceptions singulières, testés sur des bases de données limitées en contenu. Par conséquent, leur support mathématique vient plutôt comme une validation a posteriori au lieu d'une véritable démonstration des résultats. Deuxièmement, à notre connaissance, aucune méthode de traçage du contenu video n'a été encore signalée à résister aux distordions introduites par l'enregistrement en salle de cinéma. Finalement, la scalabilité, est actuellement obtenue au détriment des propriétés d'unicité et de robustesse.

Mots clés

Empreintes digitales, unicité, robustesse, scalabilité, distorsions, conversion en niveaux de gris, filtrage linéaire ou non-linéaire, transformations géométriques, enregistrement en salle de cinéma.

I.1 Introduction

With Shannon's discovery of information theory and with the breakthrough brought in the hardware technology by the transistor's invention, the digital technology developed at a tremendous pace.

Major technical achievements, discoveries and inventions exploded year after year, such as the microprocessor, the cell phone, the PC, the operating system, the Internet, the smart phone as illustrated on the timeline in Moreover, the Google sites, of which YouTube is the largest, hold 43% of the video views worldwide, the rest of 57% being assured by Vimeo, DailyMotion, Flickr, Facebook, Animoto, SlideShare and others [ ROY 12].

Jointly with the increase in multimedia content, new viewing environments and delivery options have become available beyond the traditional TV: video on demand systems hosted by cable, telephone or satellite providers stream content through a connected TV, traditional set-top boxes, mobile phone, tablet, car entertainment system or PC allowing users to choose from a wide menu of programs and watch them at their convenience [AUD 12b].

Driven by the booming multimedia industry, the viewing devices sector has also seen a growth in smart gadgets, smart TVs (i.e. television set with integrated Internet capabilities, operating systems), PCs, handheld Internet phones and table devices (Apple iPhone, iPod, iPad, Motorola Droid, HP TouchPad, Samsung Galaxy, Motorola Xoom).

Currently, in order to make their businesses profitable and sustainable, multimedia stakeholders such as video sharing platforms (i.e. YouTube, Vimeo), television networks (i.e. BBC, TF1 ) monitoring agencies and advertising agencies (i.e. Auditoire [AUD 12a]) have to create added value for their content and to keep it protected from copyright infringements. These two key prerequisites become incrementally challenging with the continuously increasing volume of produced and consumed multimedia content and with the ease of the user interfering in the content creation and consumption phases. The solution that is intensively considered and researched is multimedia digital fingerprinting, commonly denoted as multimedia content-based copy detection (CBCD) or near duplicate detection. These terms were coined in order to designate technologies able to uniquely identify the multimedia content by means of the content's features (e.g. colors, shapes, textures, …) and not by its name of other metadata such as user annotations. In order to enhance the applicability and use of such technologies, two additional requirements are necessary. Firstly, multimedia content should be identified even if mundane or malicious transforms were applied to the content. Secondly, this type of video identification should be scalable with respect to the database size, so as to be successfully deployed even foe very large databases.

I.2 Definition

Video fingerprints can be best defined in relation with the human fingerprints [OOS 02] as illustrated in Fig. I.4. The patterns of dermal ridges on the human fingertips are natural identifiers for humans as discovered by Sir Francis Galton in 1893. Although they convey very little information compared to the entire human, human fingerprints are sufficient to uniquely identify a person even if the person changes haircut, clothes, or wears a wig or a disguise.

Analogously, video fingerprints are intended to be video identifiers. The video fingerprints have to be able to uniquely identify videos even if the video content goes under a predefined, application dependent set of transformations. The transformations a video can undergo will be further referred to as modifications, distortions, or attacks, be them malicious or mundane. The video which is transformed, modified, distorted or attacked will be denoted as a copy or a replica video.

-8 - Content-based copy detection systems should also not be confused with the watermarking systems.

A watermarking system inserts imperceptibly and persistently some additional information into a digital content (e.g. image, audio, video) [COX 08]. The additional information generally consists of some copyright information (e.g. owner, seller, etc). Imperceptibility refers to the property of the watermark to be invisible for a human observer while the persistency refers to the property of the mark to be detected even when strong malicious operations were applied to the marked content.

Watermarking schemes can address the technical challenges related to rights management, content management (e.g. filtering, classification), broadcast monitoring under the condition that the content is a priori watermarked, i.e. the additional information is inserted in the multimedia content before its distribution. Although similar in terms of their applicative field, watermarking and fingerprinting differ in one essential aspect. Watermarking is an active technique: it inserts a mark prior to the multimedia content's distribution and then extracts the watermark in order to obtain the owner's information. Multimedia fingerprinting is a passive technique: it computes the fingerprints from the content itself and matches them to the reference fingerprints thus establishing the ownership.

Under the framework of a fingerprinting system, a query is the name given throughout this paper to a video whose identity is inquired, whereas reference is the name given to the video sequences belonging to the database of known identity videos. Consequently, the fingerprint of a query video sequence will be denoted as query fingerprint and the fingerprint of a reference video sequence will be denoted as a reference fingerprint.

Analogous to the human fingerprinting system, the video fingerprinting system consists of two steps: 1 -query video fingerprint computation and 2 -query fingerprint matching with reference fingerprints.

Giving more theoretical basis to this analogy, the design of a video fingerprinting system leads to: 1 -finding features from the video able to concisely represent and summarize video content and 2 -using as fingerprint matching strategy a similarity metric, which can assure the retrieval of replica videos in the context of various transformations.

The peculiarity of the video fingerprinting system compared to the human fingerprinting system arises from the peculiarities of the video content and from the variety of transformations that a query video can subsist. For instance the video fingerprint and its matching have to be designed in order to address the common situation of videos sequences with different lengths and the situation in which the query video is a fragment of a reference video. Therefore a localization procedure of the query in the reference video sequence has to be developed as an integrating part of the video fingerprinting system.

A video fingerprinting system comports a general principle as illustrated in the schema in Firstly, a query video sequence whose identity is inquired is given as input to the fingerprinting system. Secondly the query sequence is localized within the collection of reference videos sequences. Thirdly, the fingerprints of the query and reference sequences are computed. Fourthly, the matching operation establishes the identity of the query video sequence.

As illustrated in Fig. I.6 the query localization and the fingerprint computation stages have to be connected to the reference database. In this way, the video sequences and relevant information derived from them is made available: in the query localization stage, the system needs to find the position of the query sequence within a reference video sequence while in the fingerprint computation stage, the system computes the fingerprints of the query and reference video sequences.

It can be intuitively noticed that, in a video fingerprinting system, while some computation has to be done when inquiring for a query, other operations can be performed before that moment in order to speed up the process of query identity retrieval. Therefore, the computation can be split in two parts, as illustrated in Fig.I.7: an online phase, when a user or a system is interested in the identity of the query video, and an offline phase which is performed before the query inquire and which computes all the relevant necessary information needed in the query localization and fingerprint matching stages.

I.3 Theoretical properties and requirements

The main properties a fingerprinting method features are robustness, uniqueness and database search efficiency.

I.3.1 Uniqueness

A fingerprinting method is said to feature uniqueness if the fingerprints computed from two video sequences with different content are different in the sense of the considered similarity metric. The uniqueness property is assessed by the incidence of false alarms. A false alarm is encountered when the video fingerprinting system retrieves a video sequences which is neither the query not its replicas. Consequently, the uniqueness property is evaluated by the probability of false alarm or alternatively by the precision rate, as detailed in Section I.3.4.

I.3.2 Robustness

A fingerprinting method is said to feature robustness to a particular distortion if the fingerprint computed from an original video sequence and its replicas with respect to the considered distortion, are similar in the sense of the considered similarity metric.

I.3.3 Database search efficiency

A fingerprinting method is said to feature database search efficiency if the computation of the fingerprints and the matching procedure ensure low, application dependent computation time for the video's identity retrieval. The database search efficiency is assessed by the mean computation -12 -time needed to retrieve the identity of a query in the context of a considered video fingerprinting use case.

I.3.4 Evaluation framework

The performances of a video fingerprinting system can be objectively assessed by evaluating its properties: the uniqueness, the robustness and the database search efficiency.

The evaluation of the uniqueness and the robustness properties can be synoptically achieved by using the schema in Table I.1.

Considering a query sequence whose identity is looked up in a reference database with the help of a video fingerprinting system. The two statistical hypotheses are H 0 : the query is a replica of a video sequence and H 1 : the query is not a replica of a video sequence. The output of the system can be of two types: (1) -positive when the query is identified as replica of a video sequence and (2) -negative when the query is not a replica of a video sequence.

When a user is examining the results outputted by the system or when these results are compared with the ground truth, the correctness/rightness of the results is established: if the result provided by the system is correct -the attribute given to the results is true and if the result is incorrect -the attribute given is false.

The above principle yields four types of situations arising at the output of a fingerprinting system:

 False positive: the system erroneously retrieved a reference video sequence as a copy of the query.

 False negative: the system erroneously did not retrieve a reference sequence which is a copy of the query.

 True positive: the system correctly retrieved a reference video sequence which was a copy of the query.

 True negative: the system correctly did not retrieve a reference video sequence which was not a copy of the query. The false positive results are also referred to in the literature as false alarms and will be denoted as fp. The false negative are also referred to as missed detections and will be denoted as fn. The true positives will be denoted as tp and the true negatives, as tn.

-13 -Having a fingerprinting system, a reference database and being given a query video sequence, the system can output several false positives, false negatives, true positives and true negatives.

In order to objectively evaluate a video fingerprinting system, the measures above have to be formalized into some performance indicators, as follows.

In order to evaluate the uniqueness property two measures are considered in the literature: the probability of false alarm (P fa ) and the precision rate (Prec), defined by the following formulas, [SU 09], [LEE 08]:

tn fp fn tp fp P fa     (I.1) fp tp tp   Prec (I.2)
In order to evaluate the robustness to distortions property is also quantified by two objective evaluation criteria, namely the probability of missed detection (P md ) and the recall rate (Rec), as defined below:

tn fp fn tp fn P md     (I.3) fn tp tp   Rec (I.4)
On the one hand, an efficient fingerprinting method should ensure a low probability of false alarm (i.e. low probability of retrieving video sequences which are neither the query nor its replicas) and low probability of missed detection (i.e. a low probability of not retrieving replica video sequences of the query). On the other hand, high values for precision (i.e. a high probability of retrieving replica video sequences for a given query out of all the retrieved video sequences) and recall (i.e. a high probability in retrieving all the replica video sequences existing in a database for a given query) should also be obtained.

The probability of false alarm and miss detection probabilities in their classical format cannot be applied to a video fingerprinting system, unless the query and reference sequences have the same lengths, i.e. when a query is individually compared to each sequence in the database. However such a situation is not corresponding to the reality when the query and reference videos sequences can have various lengths and when the query can be a part of a reference sequence, at an unknown position.

Assuming the video fingerprinting system is time-invariant (which is always the case) the probabilities of false alarm and miss detection can be temporally estimated, as follows. In order to properly evaluate a system, the precision and recall have to be jointly used with the probabilities of false alarm and missed detection.

Precision and recall are two measures very commonly used in the evaluation of information retrieval systems. However they are not statistical measures as they are not taking into account the true negative results. In order to take into account the true negative results and present the properties of a system comprehensively, the probabilities of false alarm and missed detection have to be taken into account. The probability of false alarm is a type II statistical error (i.e. wrong data are taken as good), while the probability of miss detection is a type I statistical error (i.e. good data are refuted by the test); hence they grant statistical relevance to the obtained results.

The database search efficiency property can be objectively assessed by the average processing time required by the video fingerprinting system to identify the query within the reference database and to output the result for a query video sequence. The average processing time can be obtained by averaging the processing time required by the system for the considered collection of queries.

I.3.5 Video fingerprinting requirements

With the social, economic and technical context beneficial to video fingerprinting applications, a large set of distortions and modifications can be envisioned to affect the video content. Leveraging the robustness, uniqueness and database efficiency performances for different applications, hence for different modifications encountered, is the innovation playground for video fingerprinting systems.

The modifications a video sequence can be subject to in order to become a replica can be classified in three major categories depending on the video features they modify, namely the video format, the frame aspect and the video content; they are synoptically presented in Table I

.2.
The limit of the applicative field of video fingerprinting is given by the commercial (or entertainment) value of the altered video, hence the transformations which render the video unusable are not considered in the sequel.

I.3.5.1 Video format modifications

With the wide range of applications, manufacturers and devices a variety of formats have been developed for the video content (e.g. the MPEG-4 Part 2, H.264/MPEG-1 AVC standards giving rise to the Blu-ray, HD DVD Digital Video Broadcasting, iPod Video, Apple TV implementations) imposing a mandatory requirement on video fingerprinting systems, robustness to different encoding and successive transcoding. Encoding refers to the process of converting the source video into digital code symbols followed by compression in order to make the video easier to distribute. Transcoding refers to the process of converting the video to another encoding format which is usually necessary when the target device has limited storage capacity or when the device does not support the initial format. Other video format modifications can occur when some encoding parameters are changed, i.e. frame rate changes or changes in the compression rate which yields bitrate changes and which degrade the visual quality of the video.

On the one hand encoding, transcoding and other parameter changes can occur in mundane and automatic video manipulations such as video upload on the Internet or video serving applications on thin clients. On the other hand, these modifications can be intentionally induced in videos by malicious users in order to render the video untraceable and to avoid the copyright policies. Software which serve transcoding and parameters modifications are open source software such as ffmpg or SUPER (Simplified Universal Player Encoder & Renderer), Mencoder, Mplayer, x264, etc.

Another important distortion that a video can subsist is the analog to digital conversion which occurs when a video projected on a screen is captured with a digital camera, e.g. camcording in theatre. Due to the inherent quantization, although sometimes not visible to human observers, video information is lost.

While the previous modifications could be mundane or malicious, the frame addition, frame dropping and frame substitution modifications are largely malicious aiming at desynchronizing the video and to render it undetectable by fingerprinting systems.

Frame addition refers to inserting white/black frames in the beginning or the end of the video, or to inserting a certain amount of copy frames between the original frames. Fade-over is a particular case of frame addition consisting in a transition effect in which the content of a frame fades away and leaves place to new content. Frame dropping is the opposite of frame addition and consists in removing from the video sequence a certain amount of frames. The frames can be added or removed from the original video sequence at random positions or uniformly through the entire video or through parts of it. Frame substitution consists in replacing a certain amount of frames at particular/random chosen location with frames from other videos or from the video itself. Depending on the amount and on the type of frames added/dropped/substituted, these modifications can be noticed by the user, i.e. for 1-3 copy frames added/dropped per second at a frame rate of 25 fps, most users will not notice disturbing effects, while when adding 1 black/white frame in the same conditions would decrease the user experience.

-16 -

I.3.5.2 Frame aspect modifications

The modifications changing the aspect of the video frames refer to the following categories of distortions: color, photometric, filtering and noise addition.

The color modifications consist in changing the composition of the color balance in the video frames (i.e. modifying the values of the pixels' colors), changing the color depth (i.e. changing the numbers of bits used to represent the color of an image pixel: 1-bit color, monochrome; 8-bit color, 256 colors; 24-bit color true color more than 16 million colors; 30-48-bit color, deep color), converting the image in grayscale, filtering a certain color channel (R, G, B) or swapping colors (i.e. RGB to BGR, replacing the red color channel with the blue one, or other configurations).

Adjustments in the brightness (i.e. in the RGB color space, brightness is the arithmetic mean of the red, green and blue color coordinates), contrast (i.e. the difference between the black and white levels in images), saturation (i.e. the dominance of hue in the color), gamma corrections (i.e. an nonlinear operation , where A is a constant and V is the value of a pixel, which changes the brightness of an image) or histogram equalizations (i.e. enhancement of the contrast of the images) of a frame are the photometric distortions a video often subsists. Image filtering is an operation which consists in removing some unwanted components of the 2D signal which is the frame. The Gaussian filtering or blurring is a type of linear filtering which passes the low frequencies and attenuates the the high frequencies, i.e. attenuating the contours of the shapes in the video frames. Sharpening is a type of linear filtering, which attenuates the low frequencies but passes the high frequencies, hence keeping the details in the images. Median filtering is a non-linear filtering operation used to remove noise from images and which is usually used in preprocessing steps in order to enhance the results of further processing, e.g. edge detection.

Image noise addition consists of adding a noise signal (Gaussian noise, white noise, salt and pepper noise) to the video frame in order to decrease its quality. The noise can be added by image processing operations or can be produced by the sensors and circuitry of digital cameras when camcording.

The color and photometric modifications as well as filtering and noise addition can be induced in videos by image processing operations or intrinsically by capturing the video with external devices which implicitly change the colors and the values of the photometric parameters due to the device dependent sensors, circuitry and transducers' parameters.

I.3.5.3 Frame content modifications

The distortions which modify the content of the frame itself can be of the following types: affine transformations, cropping, insertion, picture in picture, rows or columns shifting. By changing the intrinsic content of the frames, these modifications are difficult to handle by fingerprinting systems and generally require dedicated pre-processing blocks before the fingerprinting solution is deployed, e.g. letterbox removal block, detection and removal of caption, text or pattern, detection and extraction of the videos of interest from the background or the foreground.

The affine transforms are the transforms which preserve the collinearity of points (i.e. all points lying on a line initially still lie on a line after the transformation) and ratios of distances (i.e. the midpoint of a line segment remains the midpoint after transformation).

-18 -

The affine transformations for videos (applied at frame level) include the following types of modifications: geometric contraction, expansion, dilation, reflection, rotation, shear, translations, and their combinations. In general, the affine transformations are a combination of rotations, translations, dilations and shears.

An example of affine transformation is the rotation-enlargement transformation which combines a rotation and an expansion and can be mathematically written as in (I.7): Affine transformations can greatly modify the content, hence the limit of applicability of fingerprinting solutions.

                    y x s y x    
Scaling or resizing consists in changing the dimensions of the video frames, e.g. dilations or contractions of the height and width. Scaling can be done with the same scale factor for both height and width of frames (i.e. uniform/isotropic scaling) with different scale factor i.e. non-uniform, anisotropic scaling. The advantage of using uniform scaling is the fact that it preserves the shapes of objects inside the frames whereas non-uniform scaling changes these shapes. However in practice both scaling are intensively used in all types of applications, hence the modifications they induce in videos have to be addressed by video fingerprinting systems.

Original version

Camcorded replicas Small rotations (with angles ranging from ± 1° to ± 5°) often combined with cropping and scaling are efficient attacks as they generally do not modify the commercial value of the video. However they affect the frame content itself by removing the cropped parts and therefore can make a video fingerprinting system to mistakenly take the rotated, cropped and resized content for a new content and not a replica. In Image aspect ratio is the proportional relationship between its width and height. The diverse video standards deployed in various applications e.g. the HD 16:9, the standard television 4:3, the widescreen cinema standard 39:1 demand from video fingerprinting systems to cope with aspect ratio changes.

Cropping consists in removing certain parts of the frames content such as letter boxes, rows or columns depending on the application. Insertion of content does the reverse of cropping, which is inserting other visual content in the video frames such as text, captions, patters, letter-boxes.

Picture in picture consists in displaying two videos in the same time and on the same frame, one video being the foreground and one video being the background as illustrated in Fig. 13.a. Frame shifting consists in moving to the right, to the left, up or down a certain amount of columns or rows of the video frames. The amounts of columns or rows shifted can vary between 1% to 5% of the frame's width or height as it easily affects the visual quality of the video.

-21 - Once the applicative ground for video fingerprinting is defined and its concepts established, the state of the art comes with a wide palette of methods and approaches.

I.4 Applicative and industrial panorama

Video fingerprinting is the tool that enables a system to manage video content according to some predefined rules, by using the video content itself. Therefore, in the booming video industry its applications have a wide range and are summarized below.

The performance requirements for video fingerprinting system can slightly vary across use cases but in general the missed detections and false alarms have to feature very low values, and the computational time has to stay reasonable low in order to comply with the time requirements of in the use case.

I.4.1 Video identification and retrieval

Video identification and retrieval is at the heart of all systems dealing with video. The ability to identify and retrieve video even under distortions is a powerful tool for increasingly many applications.

Given a very large database of videos (e.g. TV broadcast archive) and a query video sequence (e.g. a segment of a film), the identification of such a query can pose complex challenges (e.g. time requirements, human observes). A video fingerprinting system enables the identification of a particular video sequence by computing its fingerprint and by efficiently querying it among the reference fingerprints without using human observers, Fig I. -22 -

The video fingerprinting scheme employed in the identification and retrieval of videos from large databases has to be adapted to the use case. Considering the interactive advertising, the false alarms have a slightly greater impact than the miss detections due to the fact that the user is involved. A missed detection is preferable, i.e. the pop-up overlay dialog box with the promotional coupon does not appear and hence the user does not see the offer. A false alarm means that the promotional coupon appears when another video sequence is running at TV, making it unpleasant for the user. However, the miss detections have to be sufficiently low so as to promote the offer. In this use case, the distortions are also related to the changes which can appear in the video format during the broadcast.

I.4.2 Authentication of multimedia content

Due to powerful software (e.g. Photoshop, Windows Movie Maker, Pinnacle) for multimedia manipulation, content became very easy to manipulate and alter (e.g. change of hair color of one of the characters), therefore in many cases the originality of the content might need to be checked. An authentication system based on fingerprinting verifies the originality of the content and aims at detecting the malicious transformation. This is achieved by designing a fingerprint and a similarity metric able to detect any minor transformation in the query compared to the original version.

In general, in content authentication applications the distortions that can appear are related to image aspect and content modification, as detailed in Sections I.3.4.2-3. Moreover, for such applications, the miss detections have a critical impact on the performances of the system, whereas the false alarms can be easier accepted, therefore the fingerprint and the similarity metric between the fingerprints have to be designed accordingly. By matching the fingerprints of the monitored videos with those from the reference video database, the copyright infringement can be detected and legal action can be taken.

I.4.3 Copyright infringement prevention

In video filtering and video tracking scenarios, the miss detections are highly costly for the copyright owners whereas the false alarms are less disturbing as they can be discarded by a human observer. However, the very low values for both false alarms and missed detections are very important.

Considering the distortions that can appear in these use cases they cover all the possibilities: video format, frame aspect and frame content modifications as detailed in Section I.3.5.

I.4.4 Digital watermarking

Fingerprinting can be used to prevent certain attacks against watermarking schemes. A well-known attack is the "copy attack" *OOS 01]: from the watermarked content an estimate of the embedded watermark is obtained. This estimate is subsequently embedded in another video content. Consequently, unauthorized users can create watermarked content. A method to prevent this is to embed content-dependent watermarks. The integrity of the watermark will be decided by matching the fingerprint computed from the content with the watermark (which is the content dependent fingerprint).

In such a scenario, the miss detections have a higher negative impact on the system, than the false alarms, as when missing the replica, a pirated content can pass for a watermarked one. Therefore the fingerprinting system designed for such application has to feature a very strong robustness.

Moreover the system has to be robust to the copy-attack and to all types of modifications detailed in Section I.3.5.

I.4.5 Broadcast monitoring

A broadcast monitoring application consists in tracking television or web video broadcasts [SEO 03].

In a broadcast monitoring application, video fingerprinting consists in computing the fingerprints of an interest broadcast channel and matching them to the reference database hence obtaining its playlist. Such an application enables program verification, ensures monetization of advertisements air-runs, and can provide audience measurement statistics.

Considering for instance, the video archives of a TV station, and the counting of a particular aired commercial in a month, the missed detections as well as the false alarms are equally important. The miss detections cause losing revenue to the TV station while the false alarms cause losing revenue for the commercial provider. Regarding the distortions for such a case, they are mostly related to the video format modification (detailed in Section I.3.4.3) and which are due to the storage requirements, e.g. compression.

I.4.6 Business analytics

With the enormous volume of multimedia content comes the great challenge of making it profitable through added value services. For instance, with the fast changing and diverse mix of broadcast platforms, accurate and reliable audience measurement services have become vital. Evaluating the media consumption, the user behavior and social reach can help understanding the multimedia market and therefore lead to successful business planning, decision making or brand management [VOB 12], [ AUD 12].

Using the principles of video fingerprinting, multimedia can be identified and tracked during its consumption on the Internet or at TV. Consequently, related analytics information can be obtained and different bussiness models for multimedia monetization can be enabled.

Examples of existing analytics services are YouTube analytics -which provides the number of viewers, their location, their age segment, the engagement in the viewing experience, the popularity and Audible's CopySense -which tracks, audits and reports usage across the Internet, radio, TV, cable and satellite transmission. Regarding the monetization services, YouTube developed a content ID technology which manages to monetize a third of the interest video playbacks and advertisement on their portal [ YOU 12].

-26 -

I.5 State of the art

Due to its large applicability in various existing domains and its enabling potential for monetization and business intelligence applications, video fingerprinting got an increasing interest from both industry and academia. Consequently, the state of the art for video fingerprinting presents a dichotomy, on the one hand the industrial approach and on the other the academia approaches as presented n the sequel.

I.5.1 Industrial solutions

Companies such as Vobile [VOB 12] developed multimedia fingerprinting solutions like the Vobile Video Tracker (a SaaS -Software as a Service, i.e. the software and the associated data is centrally hosted on the cloud -application which allows content owners to monitor online sharing sites, to identify their content and to decide whether to allow it to remain on the site or to send a notice to the site operator asking for the copy to be taken down), vCloud9 (Cloud Based Content Identification and Management an application for content identification and management which enables the filehosting services to eliminate unauthorized content, to assure storage efficiency by identifying duplicate content and to generate revenues by identifying premium content that can be legally monetized), the Media Tracker Analytics (an application which provides metrics on online audience viewing behavior for specific content).

Civolution Technicolor [TEC 12] provides solutions that serve content enrichment purposes (i.e. the video fingerprint is used as an index to retrieve relevant information in a relational database e.g. the title of the movie, the names of the actors playing in it, etc.), localization of copyright content (i.e. a crawler browses the Internet and retrieves movie files which are then inspected with video fingerprinting to check whether they are copyrighted or not), data loss prevention (the video fingerprint are used to find out which and where movies are stored and processed in order to prevent unauthorized operations), copyright infringement prevention.

ZiuZ [ZIU 12] developed Twin Match, a video fingerprinting-based software which compares videos from confiscated material to previously classified material in order to eliminate from sharing sites videos featuring child pornography.

Vercury [VER 12], Advestigo [ADV 12], GraceNote [GRA 12] are other companies that provide similar with the above video fingerprinting solutions for diverse purposes.

I.5.2 Academic state of the art

The academic state of the art for video fingerprinting exhibits a large variety of methods. While in the case of the industrial video fingerprinting solutions their methodology is not available for investigation, the academic solutions are publicly available and can be consulted and compared.

Considering the three main blocks of a video fingerprinting system, presented in Fig. I.6, namely the localization, the fingerprint computation and the fingerprint matching a classification can be made on three criteria: the type of localization strategies, the type of features chosen as fingerprints and on the type of similarity metric employed between fingerprints.

In the sequel, Section I.5.2.1 -Section I.5.2.3, such a classification will be made in order to structure and discuss the existing approaches to video fingerprinting and to provide a global overview. After the synoptic classification, seven reference video fingerprinting methods were selected, briefly described and analytically compared in Section I.5.2.4.

I.5.2.1 State of the art for video fingerprinting: localization strategies

The first key component of a fingerprinting method is the localization of the query sequence in the reference video sequence. This aspect is very important because in the majority of the applications the typical query video sequence is a part of a reference video sequence.

The localization strategy can be strongly related to the video feature selected as fingerprint (e.g. a sliding window is a usual strategy for binary fingerprints) or it can be totally different (e.g. obtaining a few video candidates through an independent localization strategy and just then applying the fingerprinting algorithm).

-28 -[OOS 02] proposes an indexing look-up table for binary fingerprints containing all the possible fingerprints and the position in the reference videos where they occur. When a new query video sequence is searched, its fingerprint is computed and identified in the look-up table, hence localized in the reference video collection. However, such a strategy is just a pseudo-localization approach as the queries are considered of equal length as the sequences in the reference database. Note that the localization of different lengths query sequences within a reference sequence is not addressed.

In [COS 06] the search is enabled by sliding a frame window, with the same size as the query video clip throughout the reference sequences. The fingerprint of the sequence covered by the window is computed and matched to the reference fingerprints. A value-position matching strategy is advanced by [MUK 10] and consists in moving a sliding window with same length as the query sequence over the reference video sequence and counting the matching fingerprints at the corresponding positions in the window.

[SU 09] builds up on the sliding window idea and designs a coarse to fine sliding window, but improves it with a look up table and voting strategy. [RAD 08] proposes the division of video sequences into chunks and associates fingerprints with each chunk.

A temporal pyramid matching is proposed by [JIA 11] and consists in partitioning the videos into increasing finer temporal segments and in computing similarities over each granularity. As a conclusion, a myriad of localization strategies can be envisioned, depending on the feature chosen as fingerprint, on its mathematical formalization and its matching procedure. The most desirable localization strategies are those which have a low overall computational time and whose computation time in the online phase is independent with respect to the size of the testing database.

I.5.2.2 State of the art for video fingerprinting: features

The second key component of a video fingerprinting system is the fingerprint. The quality of the fingerprint and its properties depend on the fingerprint features selected from the video sequences. The types of features which were used in the state of the art as video fingerprints are presented in Table I.3.

The state of the art presents a dichotomy for the types of features: they can be computed only from the visual content (i.e. the case of mono-modal methods) or from visual and audio content (i.e. the case of multi-modal methods). Independently with respect to its type, the video fingerprint can be computed at different granularity levels, e.g. frames, keyframes, blocks or regions of frames, group of frames, points of interest.

According to the domain in which the fingerprints are computed, the group of mono-modal methods can be of four types: spatial, temporal, transform and color.

The spatial fingerprints computed on blocks, regions of frames or whole frames are robust to nongeometric distortions, but they lack in robustness against geometric modifications (e.g. cropping, rotations). The interest points based features have a high robustness against the geometric distortions and transcoding transformations but lack in resilience against changes in color, illumination and filtering. Moreover, this type of features poses problems of uniqueness in the case of very similar video sequences, (e.g. TV news) therefore needs to be used in combination with other features.

The category of temporal fingerprints is generally robust to global changes in the quality of the video like non-geometric modifications of the frame aspect and they can resist several encoding (e.g. MPEG compression), but they are generally sensitive to distortions affecting the video format (e.g. framerate changes, frame-dropping, transcoding) and to geometric modifications.

Transform based fingerprints ensure robustness to geometric and non-geometric frame aspect modifications and to video format modification but are sensitive to modifications of video content such as cropping and content addition.

The color based category of fingerprints lacks resilience to global variations in color and illumination but can be used along with other features in order to enhance discriminability.

-30 - As explained above, the mono-modal methods employ a reduced number of visual features as fingerprints in order to identify the limitations that they pose and their possible applications. The multi-modal types of fingerprints combine the advantages of video and audio features of videos can achieve better results with faster computation time than the mono-modal methods.

The frequent disadvantage of the multi-modal types of fingerprints is their excessive number of computed features, which leads to redundant video information used as fingerprint (e.g. [GAO 10] using SIFT and SURF features simultaneously). As the computational resources increase steadily due to technological development, extra computation is not considered a prohibitive factor. However, a clear mathematical ground for video fingerprinting should not be ignored.

I.5.2.3 State of the art for video fingerprinting: similarity measures

The third key aspect of a video fingerprinting system is the matching between the fingerprints. The matching can be achieved by employing a similarity metric adapted to the feature chosen as fingerprint and to the distortions envisioned.

According to the similarity distance employed for matching, the fingerprinting methods can be divided in two categories, distance based and probability based, as illustrated in Table I.5.

-32 - As it can be observed, a multitude of similarity measures are available, depending on the selected feature. The distance-based group of methods has the advantage of allowing a decision based on an experimentally determined threshold. While they are easier to use due to their immediate empiric observation, they don't permit in the majority of cases a decision based on a mathematical ground. Therefore the alternative is the probability-based similarity measures which can grant a statistical rule for decision.

The desideratum for a similarity measure under a fingerprinting framework is that it does not depend on an empirical threshold but on a rigorous mathematical decision rule which can handle any content, distortion or use case particularity.

I.5.2.4 State of the art for video fingerprinting: representative methods

In this section, seven reference video fingerprinting methods developed in university labs have been searched, briefly presented and their performances analytically compared. Note that in the next Sections 1.5.2.4.a -1.5.2.4.f the performances of the presented methods are not discussed individually but comparatively at the end of Section I.5.2, in Table.I.6. The 3D-DCT transformation is employed for its high energy compaction property and its low frequency coefficients' insensitivity to minor spatial and temporal perturbations. As an alternative, for enforced security, the 3D Random Bases Transform, (i.e. the calculation of the coefficients is made secret by involving a secret key within the cosine transforms bases) was proposed. Fingerprints are matched by using the Hamming distance. If the Hamming distance between two fingerprints is below a certain threshold, the videos are declared as identical; if the distance is above the threshold, the videos are declared as different. The threshold is computed based on the statistical properties of the Hamming distance and depending on the length of the fingerprint. Concerning the query localization procedure, the paper proposes a sliding window of the same size as the query's length, which moves throughout the longer reference sequence and matches the query hashes and the reference hashes under the sliding window.

I.5.2.4.a The 3D-DCT method

I.5.2.4.b The visual attention regions method

In [SU 09], Su et al. propose a fingerprint extracted from the visual attention regions of sampled frames in the video. According to [KOCH 85], attention is implemented in the form of a spatially circumscribed region of the visual field, the so called focus of attention. This focus scans the image in two ways: a rapid bottom-up, saliency driven manner and afterwards in a task dependent, object driven manner. The saliency based visual attention model proposes an algorithm for computing the master saliency map which implements the bottom-up mechanism of attention by topographically coding the local conspicuity over the entire visual scene. The saliency map represents the saliency of every location in the visual field by a scalar quantity and guides the selection of attended locations based on the spatial distribution of the saliency. The robustness of the method relies on the fact that visual attention regions are invariant if the distorted video is content-preserving, even under heavy distortions.

-34 -

The fingerprint consists of a sequence of bits obtained by quantizing a saliency map which holds the visual attention regions; the saliency map is computed by combining intensity, color and orientation maps for sampled and normalized frames, Fig. I18.

Fig.I.18: Visual attention regions fingerprint computation

The matching procedure follows the same concept as 3D-DCT [COS 06] method, namely the Hamming distance as a distance measure and the statistically obtained threshold for establishing the perceptual similarity of two videos.

I.5.2.4.c The differential block luminance method

I.5.2.4.d The point of interest behavior method

In [LAW 06] and [LAW 07], Law-To et. al propose a fingerprinting scheme based on the description of motion of interest points across videos. The method is concept wise similar to [JOLY 03] with the differences that it is faster and developed in such a manner that it allows changing its parameters depending on the constraints of the desired application.

The fingerprint consists of a description at three levels of the video content: the low level consists 20dimensional descriptors of Harris interest points in every frame; the mid level description consists of the trajectories of the Harris interest points across the video; the high level description) consists of the labels attached to the trajectories defined.

The Harris interest points were used due to their local uniqueness and their high information content. Every Harris point is assigned a descriptor: Due to the underlying properties of the proposed fingerprints the matching and the localization procedure is done in the same time, at three levels, Fig.I.22. First a k-nearest neighbor search is performed for the interest points of the query video frames which are described by their descriptors; potential matches are found among the interest points of the reference video frames. Second, distances between the trajectories of interest points in the query and reference video sequences are computed and most similar trajectories are selected. Third and last, the final decision on the similarity of a query video with a reference video is taken by comparing the associated labels.

I.5.2.4.e The centroid of gradient orientations method

In [LEE 08], Lee et. al provide a fingerprinting method based on the centroid of gradient orientation (CGO) detailed further in Fig. I. [START_REF] Coskun | Spatio-temporal transform based video hashing[END_REF]. The CGO provides a measure of variation of the luminance throughout the frame. The CGO is computed based on the gradients related to the distribution of edges in the frame which provide relevant information about the visual content in the frame. As the gradients are not based on the pixel values but on their differences, the proposed fingerprint is automatically robust against global changes in pixel intensities such as brightness, color, contrast.

The video is sampled at a fixed frame rate in order to cope with the frame rate change attacks. The sampled frames are converted to grayscale to make the method robust against color variation and applicable to black and white films as well. Each grayscale frame is resized to a fixed format in order to assure the robustness in case of a resizing processing. The fingerprint of the videos consists of the CGO computed on blocks of the sampled frames.

The CGO is obtained as a sum of the gradient of the luminance of every pixel in the block, according to the following formula:

             k m n k m n B y x B y x k y x r k y x k y x r k m n c , , , , ) , ( ) , ( , , , , , , , ,  where
( M m N n     1 , 1 ) block.   k y x r , ,
and  

k y x , , 
are respectively the magnitude and orientation of the gradient vector The fingerprint matching is done by using the squared Euclidian distance as similarity measure. The decision threshold is statistically established by considering the fingerprints as realizations of stationary ergodic processes and by considering the central limit theory in order to minimize the false alarm probability.

               y f x f G G f y x
Concerning the query localization, the proposed approach is the range search: the fingerprint of a query frame is searched in the database of reference frames fingerprints. Upon matching of frame fingerprints, the fingerprints for the videos sequences are further matched in order to ensure a correct decision.

I.5.2.4.f Shot duration method

,..., , [ ) ( 2 1 n t t t v T  is obtained; ) 1 ( n i t i  
denotes the time (in seconds) at which the th i shot transitions occurs in v . The timing sequence is further divided into segments of the timing sequence, of k seconds each, in order to be able to identify smaller parts of the video. The similarity between the segments is computed based on a defined fuzzy distance measure which is a hybrid between the 1 L measure and the Hamming distance notions, for a certain integer that need to be matching in order to declare that two videos are similar) are parameters proposed and tested by the authors depending on the application desired.

1  a .                         ) ( ' () ) ( ) ( ' ) ' , (
The similarity of two videos is finally decided based on the number C of matching timing segments.

As search strategy, a high dimensional indexing data structure, namely the LSH (Locality Sensitive Hashing), [GIO 99] is used for the construction of the fingerprints database. The LSH structure indexes a bit string representing points in a high dimensional space. Given a query bit string example and some distance threshold m, the LSH returns a list of stired bit strings within Hamming distance m of query bit string.

I.5.2.4.g Cascade of multimodal features with temporal pyramid matching

In order to provide a comprehensive overview on the state of the art for video fingerprinting methods, a multi modal fingerprinting method is also presented in the sequel. -40 - The DCT global image feature is based on the relationship between the DCT coefficients of adjacent image blocks, of the Y component in the YUV color space. Such a feature was used due to its robustness to content-preserving transformations such as transcoding, change of gamma, decrease of quality (blurr, frame dropping, contrast, compression, noise). In order to speed up feature matching, the DCT features are indexed by Locality Sensitive Hashing.

For the audio feature the Weighted Audio Spectrum Flatness (WASF) [CHE 08] was used and a 14-D single WASF feature was considered; WASF extends the MPEG-7 Audio Spectrum Flatness (ASF) audio descriptor by introducing Human Auditory System functions to weight audio data. For the audio fingerprints matching, the Euclidian distance is adopted and the LSH is used for efficient feature matching.

Concerning the matching of the video sequences, a cascade architecture is used: the query is first processed by the WASF detector; if the matching is positive (i.e. the query contains a copy clip) it leads to immediate acceptance, while a negative result triggers the evaluation of the second DCT detector. If the copy is asserted as a non-copy again by the DCT detector, it will be passed to the last DCSIFT detector. In the context of the TRECVID platform the performance evaluation is done with three indicators, the normalized detection cost rate (NDCR) which is a cost function taking into account the incidence of false alarms and missed detection by assigning corresponding costs, the F1 measure combining precision and recall and the mean processing time per query.

-42 -

I.5.2.4.h Comparative view of the academic state of the art methods

I.6 Conclusion

As it can be observed from the synoptic review presented in Section I.4 the applicability field of video fingerprinting grew steadily in the last decade. To answer the need for efficient video fingerprinting systems, a lot of research has been done in the industrial and university sector as presented in Section I.5. In Table I.6, a comparative analysis between the performances of state of the art video fingerprinting methods is presented.

Despite the wide range of methods that have been investigated, limitations are identified and challenges are still to be taken considering video fingerprinting systems as formulated next and synthetically organized in Table I.7

 The uniqueness property of fingerprints is not granted by a mathematical ground i.e. the features which represent the visual content are not selected according to a comprehensive mathematical approach.

 The robustness property of fingerprints is based on partial mathematical models without a general framework able to address the wide variety of existing distortions (i.e. the methods presented do not feature robustness to video format, frame aspect and frame content distortions at the same time). Secondly, the academic state of the art methods presented in Section I.5.2 have not addressed yet, at our best knowledge, the challenging case of live camcorder recording. Thirdly, the methods are generally tested on TV content data sets and don't take into account the particularities of the cinema content. These particularities are twofold and refer to the types of visual content and to the types of distortions that need to be addressed by the fingerprinting method.

 The uniqueness and the robustness properties are never object to a joint optimization strategy. Consequently, the trade-off among the probability of false alarm, the probability of missed detection, the precision, the recall and the computational time required by such a use case has not yet been investigated.  a bag of visual words algorithm employed for granting the fingerprinting system scalability to large scale databases;


The fingerprint per-se is represented by a set of 2D-DWT coefficients of frames sampled from the video sequence. An in-depth statistical investigation on the 2D-DWT coefficients demonstrated not only the stationarity of such coefficients but also the stationarity of their modifications under the computer-simulated camcorder attacks. These mathematical properties grant the fingerprints the uniqueness property and limits the occurrences of false alarms (i.e. fingerprints extracted from different video content have to be different).

The fingerprint matching is done based on a repeated Rho test on correlation which allows the detection of replicas, hence ensuring the robustness property (i.e. fingerprints extracted from an original video sequence and its replicas should be similar in the sense of the considered similarity metric).

In order to make the method efficient in the case of large scale databases, a localization algorithm is employed. Consequently, the replica sequence is not matched to the entire reference video collection but only with a few candidates determined based on a bag of visual words representation (concept introduced by Sivic and Zisserman in 2003) of the video keyframes. An additional synchronization mechanism able to address the strong distortions from difficult use-cases such as camcorder recording in cinema was also designed.

The method scalability is granted by the localization and synchronization procedures and by its low complexity which is kept under the ) log ( n n O limit.

Resumé

Ce chapitre présent une nouvelle méthode de traçage du contenu vidéo, basée sur la transformée en ondelettes discrète (pour définir les empreintes numériques) et sur une règle de décision mathématique définie a partir du teste statistique Rho sur la corrélation appliquée selon une procédure répétitive (pour l'appariement des empreintes numériques).

Les contributions de cette méthode se situent à trois niveaux:

• une nouvelle empreinte numérique et une nouvelle procédure mathématique pour la détection des copies;

• un bloc de synchronisation dynamique pour adresser pour la première fois l'enregistrement en salle de cinéma;

• un algorithme sac de mots visuels (i.e. bag of visual words) utilisé pour assurer la scalabilité du système pour des bases de données à grande échelle.

Mots clés

Coefficients 2D-DWT, corrélation croisée normalisée, Rho test sur la corrélation, localisation, sac à mots visuels, synchronisation.

II.1 TrackART: Synopsis

The present thesis advances a novel video fingerprinting methodology called TrackART able to identify visual content subjected to different types of user induced, mundane or malicious distortions.

Concisely, the challenges the TrackART video fingerprinting method takes are threefold:

 Uniqueness: the TrackART method aims at proposing a video fingerprint which represents the video content with mathematical accuracy and rigor.

 Robustness: the TrackART method aims at providing a general mathematical decision rule for the robustness to distortions and at addressing the challenging use case of live camcorder recording (which has not been yet addressed in the state of the art).

 Scalability: the TrackART method aims at being operative even in large scale databases.

The functioning principle of the TrackART method consists in two phases: the offline phase and the online phase, as illustrated in Fig.II.1.

Fig.II.1 TrackART system functional schema

As the word "offline" suggests, the offline phase holds the computation executed before the runtime phase. Its purpose is to process the reference video collection in order to enable the retrieval (if existing) of the original version of the query from the reference database, i.e. to enable the localization and the fingerprint modules. The offline phase consists of two modules: pre-processing and offline localization.

The pre-processing stage prepares the reference video sequences for the further processing by performing some parameter setting and common image processing operations as detailed in Section II.2.1).

-58 -

The offline localization stage (detailed in Section II.2.2) consists in mapping the reference video content to a representation space which allows the matching of video content and enables the localization module.

In the online, a query video sequence is proposed for identification by a user or by another system. By passing the query through the modules of the run-time phase, its original version (if existing in the reference data set) has to be identified. The online phase consists in four modules whose role is briefly given here and further detailed in the rest of this chapter: pre-processing, localization, fingerprint and reduced fingerprint.

The pre-processing module (detailed in Section II.3.1) sets the parameters of the query video sequence to predefined values in order to avoid the variations induced by distortions.

The online localization module (detailed in Section II.3.2) aims at significantly reducing the multitude of reference sequences which are candidates for matching the query (i.e. all the video sequences) and to identify just a few nominees for further testing. Moreover, in the localization module, for each nominated video sequence, a potential starting position (i.e. the frame number) of the query sequence is obtained.

The Fingerprint module computes and matches the fingerprints of the query and reference video sequences. It consists in three blocks: fingerprint computation (detailed in Section II.3.3.2), fingerprint matching (detailed in Section II.3.3.3) and synchronization (detailed in Section II.3.3.4).

The synchronization module is designed to ensure the correct content correspondence between the query and reference video sequences which can be altered by video format distortions.

The reduced fingerprint module (detailed in Section II.3.4) consists in two blocks: reduced fingerprint computation (detailed in Section II.3.4.1) and reduced fingerprint matching (as detailed in Section II.3.4.2) and aims at reducing the amount of information needed for identifying a query video sequence.

II.2 Offline phase

The offline phase enables the localization of a query sequence within a reference sequence. Its purpose is to process the reference video collection and to map the visual content to a representation space. The representation of the content in a new space enables the comparison of the reference and query sequences with respect to certain similarity measures and under different types of distortions. The offline phase consists of two modules: pre-processing (Section II.2.1) and offline localization (Section II.2.2).

II.2.1

Pre-processing

The pre-processing stage aims at achieving a common formatting for the reference video sequences in order to reduce the influence of video format distortions (detailed in Section I.3.4.1) as follows.

Due to the multitude of different existing video formats and to the manipulations that video sequences subsist through their consumption chain (i.e. encodings, transcodings), the video framerate can have a large variation. In order to enable the TrackART method to cope with this fact, the reference video sequences are all brought to the same frame-rate value. In the current implementation, the frame rate was chosen to be 25 fps due to its frequent use in video formats, but another value can be equally chosen. The changes of the video parameters are done with the ffmpeg library which contains dedicated functions for controlling the video parameters.

The black keyframes were discarded and the letterboxing (if existing) was removed in order to consider only the valid visual information.

The length of a typical film is between 150-250 000 frames (i.e. between 1 hour and a half and two hours and a half at a 25 frames per seconds); in order to reduce the complexity, keyframes are extracted uniformly, one frame per second.

Note: Shot boundaries keyframes were also considered in the current study, but as they are not repeatable under video distortions they yield poor results (i.e. due to various distortions, the shot boundaries of an original video and its distorted version will not be the same).

II.2.2 Offline localization

The role of the offline localization module is to provide to the online localization module in the online phase potential positions within the reference sequences which might be the start of the query sequence. Calculating these potential positions relies in identifying matching keyframes between the reference and query video sequences. Therefore the offline localization module reduces to identifying the original version of a query keyframe within the reference keyframe collection.

Establishing keyframe similarity under different frame content and frame aspect modifications (described in detail in Section I. The representation space is called a visual vocabulary. It is built by detecting the local features (detailed in Section II.2.2.1) in all the reference images, by describing these local features with a formalized descriptor (detailed Section II.2.2.2) and by clustering the descriptors into visual words (detailed Section II.2.2.3). Each image in the reference is then expressed as a collection of weighted visual words from the vocabulary (detailed Section II.2.2.4). In order to ensure the retrieval of images in the run-time phase, an inverted file structure stores for every visual word its occurrences in the reference images (detailed Section II.2.2.5).

Within the framework of the TrackART method, the run-time phase of the bag of words framework takes place in the localization module of the TrackART fingerprinting system and is further detailed Section II.3.2. Good local features prove a few properties which make them useful in the above applications, [TUY 08]:

II.2.2.1 Local feature detection

A
(1) -repeatability: the propriety of local region of being re-detected in other image under different camera viewpoints, illumination conditions and noise)

(2) distinctiveness: the intensity patterns underlying the detected features should show a lot of variation, such that features can be distinguished and matched)

(3) -locality: the features should be local, so as to reduce the probability of occlusion and to allow simple model approximations of the geometric and photometric deformations between two images taken under different viewing conditions (4) quantity: the number of detected features should be sufficiently large, such that a reasonable number of features are detected even on small objects, ideally, the number of detected features should be adaptable over a large range by a simple and intuitive threshold [START_REF] Gao | PKU-IDM@TRECVID-CCD 2010: Copy Detection with Visual-Audio Feature Fusion and Sequential Pyramid Matching[END_REF] accuracy: the detected features should be accurately localized, both in image location, as with respect to scale and possibly shape Intuitively, in order to obtain a set of local features robust to a set of distortions, an approach can be to estimate the distortions through a mathematical transformation and then to look for the local features which are invariant to such transformations.

Following this approach, the mathematical transform which can model photometric distortion is a linear transform of pixel intensities whereas the transform which can model the image distortions like affine manipulations, (i.e. viewpoint changes, scale changes, rotations), partial occlusion or cropping is the affinity, [MIK 05a]. Consequently, the local features necessary for the TrackART video fingerprinting method have to be robust to linear and affine transformations. In order to obtain such features, local feature detectors which detect features with such properties have to be investigated.

The state of the art exhibits many approaches for local features and feature detectors, such as: -64 -


The key idea of the affine covariant region detectors is that the shape of the region is automatically adapted to underlying image intensities in a single image in such a way that regions detected independently in each image correspond to the same 3-dimensional surface patch. The size and shape of such regions are covariantly transformed under a particular 2-D image distortion. In most of the cases an affine transformation is a reasonably good local approximation to transformations arising from viewpoint changes for locally planar surfaces. In the case of video content, most of the objects and characters are in motion and suffer different transformations. Consequently, affine covariant regions are a priori a more suitable solution to this problem comparing to its DoG correspondent.

Concerning the detector, the study and comparison of affine covariant region detectors in [MIK 05a] concludes that no detector shows superiority in all experiments. However, the MSER and the Hessian-Affine detectors had consistently higher scores. The MSER detector performs well on images containing homogenous regions with distinctive boundaries but the number of detected regions is rather reduced comparing to Hessian-Affine. The Hessian-Affine detector provides more regions than other detectors, making them more suitable for identifying cluttered or occluded objects.

Taking into account all the considerations above, for the TrackART method the Hessian-Affine region detector is used for detecting the affine covariant regions which will be used as local features.

The Hessian-Affine detector algorithm consists in three major operations, [MIK 02]: the detection of the interest points, the detection and selection of scale for the interest points and the estimation of the region shape. The Hessian-Affine detector is applied on gray scale images, hence they consider the intensity information within an image.

The interest points and their scales are computed and selected with the Hessian matrix. The algorithm searches in the Gaussian scale space over a fixed number of predefined scales , with and k = 1.4 [MIK 04]. For each integration scale , chosen from this set, an appropriate local differentiation scale is chosen to be a constant factor of the integration scale , where .

Considering an image I , the interest points a are detected in the Gaussian scale space with the Hessian matrix H . For each integration scale , the Hessian matrix is issued from the Taylor expansion of the intensity function ) (a The algorithm starts from the determinant and the trace of the Hessian similarly with the Laplacian of Gaussians [LIN 98], (the trace of this matrix is also referred to as the Laplacian):

I .         ) , , ( ) , , ( ) , , ( ) , , ( ) , ,
)) , ( ) , ( ) , ( ( )) , ( det( 2 D xy D yy D xx D D a I a I a I a H        (II.3) )) , ( ) , ( ( )) , ( (
D yy D xx D D a I a I a H trace       (II.4)
At each scale, the interest points are detected as those points that are simultaneously local extrema of both the determinant and trace of the Hessian matrix (i.e. a local maximum of the determinant decides if it is an interest point, a local maximum in the trace decides its characteristic scale).

By thresholding the Hessian determinant and the Laplacian response, the number of regions detected can be controlled.

Having the interest points extracted at their characteristic scale, the shape of the affine elliptical region of the point neighborhood is determined based on the eigenvalues of the second moment matrix (i.e. called the autocorrelation matrix) with an iterative region estimation algorithm as described in [LIN 97] and illustrated in The scale-adapted second moment matrix for a point a is defined by:

                 ) , ( ) , ( ) , ( ) , ( * ) ( ) , , (
I I a I g x M              (II.5)
where is the derivative computed in the direction . The eigenvalues of the second moment matrix are used to measure the affine shape of the point neighborhood, by computing the transformation that projects the intensity pattern of this neighborhood to one with equal eigenvalues. Practically, the affine region is skewed or stretched to a normalized circular region where the second moment matrix is isotropic. A new location and scale are detected in the normalized region. If the eigenvalues of the second moment matrix for the new point are equal, the estimation is correct. Otherwise, a new affine shape is estimated with the second moment matrix and tested. When estimating the shape and size of the affine region, with the algorithm proposed in [LIN 97] there can be a maximum of 16 iterations. If the shape of the region is not detected after 15 iterations, the algorithm discards the current interest point and takes another one.

The resulting shapes of the regions will be adapted to the underlying intensity patterns and ensure in this manner that the same parts of different instances of the same region are covered in spite of deformations caused by viewpoint change or rotations.

A few examples of Hessian-Affine regions are illustrated in Fig.II.8. Note that only 10% of the regions detected in the images are shown so that the illustration is not overwhelmed by the amount of regions.

The software implementation of the Hessian-Affine detector was used from [PER 09].

-68 -

II.2.2.2 Local feature description

Once the local features have been identified, they have to be formalized into a description which can allow their matching or further use. Choosing or designing a descriptor preserving and enhancing the affine invariance of the Hessian-Affine regions is not an easy task.

The study in [MIK 05b] investigates the performances of certain descriptors in the context of descriptor matching (for recognition of the same object or scene purposes) between images under the following distortions: affine transformations, scale changes, rotation, blur, jpeg compression and illumination changes. The results of the study brought to light the superiority of the SIFT and GLOH descriptors and proved the robust and distinctive character of the region based SIFT descriptor (e.g. SIFT and GLOH had the highest matching accuracies for affine transformation of 50°; for scale changes in the range 2-2.5 and image rotations with 30-45° the SIFT descriptor outperformed the others; the SIFT descriptor proved better on both textured and structured images; the introduction of blur also pointed to the superiority of the SIFT descriptor; in terms of distinctiveness, the SIFT was ranked top three).

While [MIK 05b

] investigates the SIFT descriptor used as an entity for matching (i.e. the descriptors of the query and reference images are matched one to one based on a nearest neighbor similarity metric), its good properties have been confirmed in bag of visual words approaches as well.

The A smoothing Gaussian function with σ equal to one half the width of the descriptor window is added in order to emphasize the information in the close neighborhood of the interest points. This is illustrated with the circular window in Fig. II.9.a. The purpose of the Gaussian window is to avoid sudden changes in the descriptor with small changes in the position of the window and to give less weight to the gradients which are far from the center of the descriptor.

In order to achieve the rotations invariance, all gradients within the patch are computed relative to a dominant gradient orientation, which is obtained as the highest peak in a histogram of all gradient orientations within the patch. The gradients are illustrated with small arrows at each sample location in Fig. 9.II.a.

The interest point descriptor is shown in

II.2.2.3 Clustering

II.2.2.3.1 Visual vocabulary

The local features detected in the reference keyframes and their formalized descriptors pile up to a significant amount of data which is not easily comparable without an a priori structuring.

Consequently, in order to reduce the number of considered features and to optimize the search times, large scale image or video retrieval systems cluster the high-dimensional descriptors into a limited set of descriptors, a so called vocabulary of visual words. The visual words vocabulary has been also referred in the state of the art as visual codebook or visual dictionary.

Based on the visual vocabulary, images are mapped into the bag of words representation by assigning to their local features the corresponding visual word in the vocabulary. The advantage of this approach is the increased efficiency: the assignment of visual words labels to image local features, leads to matching becomes labels (i.e. the visual words) instead of matching the high dimensional descriptors of the local regions.

The visual vocabulary is a key component for a large scale image retrieval system because it enhances the efficiency in the online localization stage. However, the creation of the vocabulary, i.e. the clustering, is in general the most computational expensive stage of the offline phase.

Considering the case of the proposed video fingerprinting technique, the amount of descriptors to be clustered depends on the number of reference keyframes in the reference video database and can easily vary between 50 000 and millions of keyframes. Considering the amount of affine covariant regions within a keyframe, it can vary between a few hundreds and up to thousands of regions, hence yielding millions of SIFT descriptors.

Generating clusters from large collections of high dimensional descriptors presents computational costs which cannot be surmounted by typical clustering algorithms such as k-means, mean-shift, spectral and agglomerative. The proof comes from the study reported in [SIV 03] which uses flat kmeans clustering effectively but concludes that it is impossible to scale it to large vocabularies. Therefore k-means algorithms, scalable to high dimensional spaces need to be investigated.

A big step towards this direction is made by Nister and Stewenius [NIS 06] who introduce the vocabulary tree obtained from hierarchical k-means (HKM) clustering and brought significant improvements in the retrieval accuracy. Due to its reduced complexity, the method can scale to very large numbers of clusters and feature points (i.e. more than 1 million visual words).

An advantage of the HKM and vocabulary tree is the hierarchical scoring, which considers nodes from several levels in the similarity score, weighting the contribution of each level to the score with an entropy weight relative to the root of the tree and ignoring dependencies within the path. In this way, possible quantization errors can be overcome.

Local feature detection

Local feature description

Clustering -Visual vocabulary TF-IDF weighting

Inverted Index -73 -  is the mean of points in i S .

In the typical k-means algorithm, the majority of computational cost is due to the computation of the nearest neighbors between the points and the cluster centers. In the approximate k-means algorithm, the nearest neighbor operation is replaced with an approximate nearest neighbor method and 8 randomized k-d trees are built over the clusters centers at the beginning of each iteration to increase speed, as proposed in [LEP 05] and [MUJ 09].

In a typical k-d tree, [FRI 77] each node splits the dataset using the dimension with the highest variance for all the data points falling into that node and the value to split on is found by taking the median value along that dimension. Concerning the randomized k-d trees, the splitting dimension is chosen at random from a set of the dimensions with highest variance and the split value is randomly chosen using a point close to the median. The union of these trees creates an overlapping partition of the feature space and helps to diminish the quantization effects, where features which fall close to a partition boundary are assigned to an incorrect nearest neighbor.

A new data (i.e. descriptor) is assigned to the approximately closest cluster center as follow. Initially, each tree is descended to a leaf and the distances to the discriminating boundaries are recorded in a single priority queue for all trees. Then, the most promising branch from all trees is iteratively chosen and unseen nodes are added into the priority queue. The stop condition is when a fixed number of tree paths have been explored.

The algorithmic complexity of a single k-means iteration is reduced from

) (Nk O to ) log ( k N O ,
where N is the number of SIFT descriptors that is being clustered. It was proved by [PHI 10] that for moderate values of k, the percentage of points assigned to different cluster centers differs from the exact version of the algorithm by less than 1%.

The choice between the two state of the art scalable k-means algorithms is for the AKM due to its close to optimal results. The main drawback of the HKM method is that at each level in the tree, a decision is made on cluster ownership. At each such point, a wrong decision can be taken and thus the HKM features multiple occasions of causing quantization errors. Since it relies on the flat kmeans, the AKM involves only a single decision, so the probability of a quantization error is reduced. Moreover, the studies in [PHI 07], [ PHI 10] show that the AKM algorithm achieves better results than the HKM.

Another parameter to be set is the size of the visual vocabulary. No guidelines have been yet derived in order to establish a clear relationship between the number of descriptors to be clustered, the clustering techniques and the results they provide.

Unlike the vocabulary of a text corpus whose size is relatively fixed, the size of a visual word vocabulary is controlled by the number of clusters in the clustering process, [ YAN 07]. A good -74 -vocabulary size involves the trade-off between discriminability and generalization. In the case of small vocabularies, the visual words are not very discriminative because dissimilar points can be mapped to the same visual word. With the increase in vocabulary size, the visual words become more discriminative, but in the same time less generalizable. Using a large vocabulary also increases the cost of clustering the descriptors and the computation of the bag of words representation. Usually smaller vocabularies are used for image classification whereas for object or image retrieval, larger and more discriminative vocabularies are considered. However, in general the increase in vocabulary size yields better results. Philbin For the TrackART video fingerprinting method, the uniform sampling of the video sequences in the reference database yielded 47 163 keyframes. For the sampled keyframes, the local feature detection and description lead to 38 466 280 descriptors.

Based on the examples in other studies [JEG 08], [PHI 07] and in order to achieve an accurate retrieval of keyframes even in the context of distortions while keeping a reasonable computational cost, the size of the vocabulary was chosen to be 250 000 clusters.

Following the approach in [PHI 07] illustrated in Table II.1, the ratio between the number of descriptors and the vocabulary size, K:N was chosen to be 1:15, therefore the a subset of the descriptors from the dataset was sampled. The sampling yielded a subset of 10% descriptors, totalizing 3 846 628 descriptors.

Note that the sub-sampling of the descriptors is done randomly: the order of the images is randomized and the order of the descriptors for each image is randomized as well. Thus, all bias is avoided and the sub-sampling is done in a completely automatic manner.

-75 - For the reference dataset of N = 3 846 628 descriptors the clustering into K = 250 000 clusters on a 4 core machine took 3 hours.

II.2.2.3.2 Bag of words representation

Having the visual vocabulary computed, the next step consists in expressing the reference keyframes as a collection of visual words from the vocabulary, the bag of words representation (BoW). This is achieved by assigning each SIFT descriptors from every reference keyframe to the most similar visual words in the vocabulary. The descriptor assignment is done with a fast approximate nearest neighbor strategy proposed in [MUJ 09]

The nearest neighbor search problem can be formulated as follows: given a set of points   n p p p P ,..., , 2 1  in a vector space X q  , these points must be preprocessed in such a way that given a new query point X q  , finding the points in P that are nearest to q can be performed efficiently. For high dimensional spaces (as it is the case of the SIFT descriptor which has 128 dimensions) there are no known algorithm for nearest neighbor search that are more efficient than linear search. As linear search is too costly for many applications, the algorithms which compute an approximate nearest neighbor search have been considered. Such approximate algorithms can be orders of magnitude faster than exact search, while still providing near-optimal results.

The two approaches for computing the fast approximate nearest neighbor proposed in [MUJ 09] are the randomized kd-tree algorithm and the hierarchical k-means tree algorithm which were implemented in the C++ FLANN library (Fast Library for Approximate Nearest Neighbors).

The classical kd-tree algorithm [FRE 77] is efficient in low dimensions but its performances degrade rapidly in high dimensions. In its original form, the kd-tree algorithm splits the data in half at each level of the tree on the dimension for which the data exhibits the greatest variation. [SIL 08] improved the algorithm by using multiple randomized kd-trees, which are built by choosing the split dimension randomly from the first D dimensions on which data has the greatest variance. The fixed value D = 5 was used as it was proven to perform well in the [MUJ 09] and does not benefit greatly from further tuning.

When searching the trees, a single priority queue is maintained across all the randomized trees so that search can be ordered by increasing distance to each bin boundary. The degree of The hierarchical k-means tree is constructed by splitting the data points at each level into K distinct regions using a k-means clustering, and then applying the same method recursively to the points in each region. The recursion stops when the number of points in a region is smaller than K. The algorithm explores the hierarchical k-means tree in a best-bin-first manner by analogy to what has been found to improve the exploration of the kd-tree. The algorithm initially performs a single traversal through the tree and adds to a priority queue all unexplored branches in each node along the path. Next, it extracts from the priority queue the branch that has the closest center to the query point and it restarts the tree traversal from that branch. In each traversal, the algorithm keeps adding to the priority queue the unexplored branches along the path. The degree of approximation is specified in the same way as for the randomized kd-trees, by stopping the search early after a predetermined number of leaf nodes (dataset points) have been examined.

Within the FLANN library, the selection of the algorithm for approximate nearest neighbor can be done automatically, based on a precision wanted by the user, e.g. considering a precision of 60% it is assume that 40% of the nearest neighbors returned are not the exact nearest neighbors, but just approximations under the advantage of greatly reducing the computational cost. Within the algorithm the precision parameter given by the user is represented as a cost function which allows the algorithm to choose between the two possibilities of computing the approximate nearest neighbors, either the kd-tree method, either the hierarchical k-means tree. The cost function is based on the method's specificities search time, tree build time and tree memory overhead.

For the TrackART video fingerprinting method, the kd-tree algorithm was chosen and not the precision auto-tuned version. The kd-tree algorithm was chosen because it is the fastest to build and most memory efficient. The number of randomized trees was set to D = 4 trees and the number of examined leaf nodes to 32.

II.2.2.4 TF-IDF weighting

The bag of words representations obtained in the previous stage for the reference keyframes are further used to build a vector of visual word frequencies for each keyframe. This is achieved by employing text retrieval and statistical text analysis techniques as proposed in [SIV 06]. The components of this vector are weighted in order to overcome biases related to the uneven number of visual words per image or to the reachability of often encountered visual words or less encountered ones.

These vectors are weighted with the standard weighting, [BAE 99], known as term frequencyinverse document frequency (tf-idf) and is computed as follows. .

Intuitively, it can be observed that on the one hand, the word frequency ( tf ) gives a higher weight to the words occurring more often in a particular document in comparison with words that do not appear at all, hence offering a relevant representation.

On the other hand, the inverse document frequency downweights words that appear often in the database, which do not help to discriminate between different documents, hence contributing to the relevant representation of the image through visual words.

II.2.2.5 Inverted index

Having the reference keyframes represented as bags of visual words, i.e. as tf-idf vectors, efficient matching can be achieved with the help of an inverted file structure.

An inverted file [WIT 99] is a commonly used indexing structure in text retrieval and its structure is analogue to a complete book index.

In the current implementation the format of the inverted index was chosen as illustrated in Fig.II.11.

For each visual word in the vocabulary, an entry is considered in the inverted index table. For each entry, a list of all the occurrences of the considered visual word in the reference keyframes is attached.

Local feature detection

Local feature description

Clustering -Bag of words representation TF-IDF weighting Inverted Index -78 - Depending on the application and on the computation needed in the online phase, the structure of the inverted index can be more complex.

For example, [SIV 09] stores for each occurrence of the visual word, its position in the corresponding frame and the distance to the 15 th nearest neighbor in the image, in order to achieve a fast geometrical consistency verification. In [JEG 07], a tree-based inverted index for fast search is designed and in [PHI 10] the position and the coordinates of the elliptical shape of each point is stored.

The advantage of using an inverted index is shown in the online localization phase (Section II.3.2.), when a query keyframe is given in its BoW representation and the reference keyframes which contain the same visual words are inquired. The visual words of the query keyframe are searched in the inverted index and are used to generate a list of plausible reference keyframe candidates by selecting only images that contain at least an occurrence of one query visual word. Consequently, this strategy reduces greatly the number of keyframes to be compared, while ensuring that no plausible candidates have been omitted.

II.3 Online phase

In the online phase of the TrackART video fingerprinting system, a query video sequence is considered to be given by a user or another system. Depending on the use case scenario, the identity of the query or its existence in a database is inquired. The run-time phase consists of the following modules: pre-processing, localization, fingerprint and reduced fingerprint.

II.3.1 Pre-processing

The pre-processing step in the run-time phase is identical to the pre-processing step in the offline phase (detailed in Section II.2.1) with the difference that it is applied to the query video sequence.

It consists in the following operations: frame rate adjustment to 25 fps, removal of black keyframes, uniform frame sampling at 1 fps, letter-boxing removal and storing of the sampled keyframes together with their positions (i.e. frame number).

II.3.2 Online localization

In general, the query video sequence is just a part of a reference video sequence and therefore needs to be localized within that particular reference video sequence. The online localization procedure refers to identifying the position (i.e. the frame number) at which the query video sequence is located within the reference video sequence. Due to the distortions (described in Section I. In the run-time phase of the bag of words algorithm, a query image is considered and its original version it's searched for in the reference image database (i.e. in the case of the TrackART method, the original version of a query keyframe is searched for among the reference keyframes). This is achieved by detecting the local features in the query image, by computing their descriptors and by quantizing the descriptors into visual words. Having the bag of words representation, the matching between the query and the reference images can take place. Based on the inverted index, reference image candidates are obtained and matched based on the normalized scalar product similarity metric (detailed in Section II.3.2.1). The matching reference images are further filtered through a geometrical verification as detailed in Section II.3.2.2.

The localization step for the TrackART method takes as input the sampled keyframes of the query video sequences and returns their matches in the reference keyframes database and implicitly their location within the reference video sequences.

II.3.2.1 Keyframe matching

In the keyframe matching stage, the similarity between query keyframes and reference keyframes is inquired. The similarity between keyframes is formulated under the bag of words framework as a histogram similarity measure, where the tf-idf BoW representations of keyframes are considered as histograms with equal number of bins (i.e. the size of the vocabulary).

The keframe matching stage consists in the following steps: (1) -considering a given query keyframe, its visual words are searched within the inverted index and a list of reference keyframes which contain the same visual words is retrieved; (2) -a histogram similarity distance is employed between the tf-idf vectors of the query and reference keyframe.

In order to achieve the matching of these keyframes, the normalized scalar product is considered between their tf-idf vectors, as proposed in [SIV 06].

The normalized scalar product between the query vector q v and all reference vectors d v in the database is:

2 2 d q d T q d v v v v f  (II.8) where v v v T  2 is the L 2 norm of v .
Note that when the vectors are normalized using the L 2 , then

1 2 2   d q v v
and (eq f d ) becomes:

2 2 2 1 1 d q d T q d v v v v f     (II.9)
Therefore, ranking keyframes in ascending order of their L 2 distance (i.e.

d q v v 
), is equivalent to ranking them in the ascending order of The inverted index is essentially a compressed sparse row representation of the matrix D . The sparse matrix-vector product only needs to explicitly consider the non-zero contributions to this product.

In our case the query vector is given by the frequencies of visual words contained the query keyframe, weighted by the inverse document frequencies computed on the visual word.

Retrieved keyframes are ranked according to the similarity of their weighted vectors to this query vector.

Other weighting schemes and distances between the tf-idf vectors were tested in the state of the art. The study in [TIR 10] proposed probabilistic models for weighting such as BM25 [ROB 77] which weights the tf (by considering that word occurrences are distributed following two Poisson distributions) and the idf terms (according to a probability ranking principle which ranks the results according to their relevance with the query); different variants of the Ln histogram distance have been tested by varying the value of n. No method showed superior performance and the authors concluded that the choice of the technique depends on the dataset and its size, on the size of the vocabulary and on the use case. ). Their experiments found that the standard tf-idf and Bhattacharyya ranking had the best scores, followed closely by the Kullback-Liebler divergence methods and the standard tf-idf method with L2 ranking.

Considering that no tf-idf weighting technique and histogram distance proved better results and due to the fact that it is difficult to estimate automatically the most suitable choice given a dataset and a query, for the TrackART video fingerprinting method, the standard tf-idf weighting and the normalized scalar product.

II.3.2.2 Geometric consistency verification

In the keyframe matching step, the reference keyframes which are the most similar to a given query keyframe are returned based on the normalized scalar product and the bag of words representation. The bag of words representation does not take into account the spatial configuration of the visual words within the keyframes. However, it was proved in [PHI 07] that a spatial consistency between the visual words of the query and reference images can improve the results.

Therefore, the aim of the geometric consistency verification block is to establish a spatial coherence between the visual words of the query keyframe and the visual words of the reference keyframes returned by the keyframe matching block.

The geometric consistency verification has been done with several algorithms in the literature. The standard solution is to use the RANSAC (RANdom SAmple Consensus, proposed by [FIS 81])

-82 -algorithm which is an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers. A basic assumption for RANSAC is that the data consists of "inliers", i.e., data whose distribution can be explained by some set of model parameters, and "outliers" which are data that do not fit the model. The RANSAC algorithm consists in generating hypothesis concerning the targeted geometrical transformation using a minimal number of correspondences between two images. Then, each hypothesis is evaluated based on the number of inliers among all features under the hypothesis. The transformation hypotheses are scored by maximum number of inliers. The algorithm checks the top results yield by the bag of words matching and re-ranks them according to their spatial consistency with the query.

Other For the TrackART video fingerprinting method, the approach proposed in [PHI 07] was chosen because it is fast, effective and can generate transformation hypotheses even with a single pair of corresponding features, which is very useful the case of distortions which induce content addition or content cropping.

The geometrical consistency verification proposed in [PHI 07] starts from one pair of matched points (correspondences) and uses a 5 degrees of freedom affine transform combined with a decision threshold (for deciding the points that feature geometric consistency). The threshold is chosen in order to allow the matching of images with significant perspective distortions which can appear in camcorder recording use-cases. The transformation between the points of the correspondence is used for generating a hypothesis, which is further applied to the rest of the correspondences. The correspondences with the distances lower than the threshold are considered to be verified for the assumed hypothesis and added to a list of verified inliers.

The inliers from the list are then used to re-estimate a full affine homography with the least-squares method. In practice, this step can be discarded as accurate results can be obtained also by simply counting the verified inliers for each hypothesis and selecting the one with the highest number of inliers.

The 5 degrees of freedom transform allows translation, anisotropic scaling and vertical-preserving shear. The elliptical regions are constrained to be oriented "up" as it is a good assumption for videos to be filmed in without significant rotations in the viewpoint. This transform is computed from a single correspondence of two elliptical regions and from the reference image and the query image, respectively. The region centroids are used to compute the translation, while the affine 2 x 2 sub-matrix is computed as (Fig. II.13), where and project the ellipses to a unit circle such that the orientation of the unit vector in the y direction (i.e. "up") is maintained. The matrices and can be computed in closed form using a transposed Cholesky decomposition, . The transformation considered in this case is modeled with the following functional matrix:

[ ] (II.10)
The geometrical consistency verification is applied as following for the TrackART method. In the keyframe matching block the distances between the BoW representations of the query keyframe and the reference keyframes are computed and a ranked list of reference keyframes is generated for the query keyframe.

The geometrical consistency verification is performed on the first N reference keyframes which are further re-ranked. Firstly, a matching between the affine covariant regions of the query keyframe and the reference keyframe is performed with an approximate nearest neighbors algorithm (FLANN) proposed in [MUJ 09].

Fig.II.13

Computing by projecting ellipses and to a unit circle and preserving the "up" orientation Secondly, once this list of matches between the covariant regions is computed, they are checked iteratively by employing the 5 degrees of freedom transform. This 5 degrees of freedom transformation is considered as a hypothesis and applied to all matched points from the query keyframe, and then projected into the reference keyframe. The projected points that are localized close to their corresponding points are considered as inliers and added to the list of verified matches for this transform. The configuration which yields the highest number of inliers is returned and the N considered frames are re-ranked in decreasing order of the number of verified inliers, leaving the ranking of the rest of the results unchanged.

-84 -

II.3.3 Fingerprint

The input for the Fingerprint block is a pair of matching query and reference keyframes provided by the localization module. Implicitly, the associated query frame f q , reference frame f r and their position in the video sequences are known.

In order to grant a mathematical based video feature as fingerprint, the properties and statistics of the wavelet coefficients have been reconsidered and investigated in Section II.3.3.1.

Having identified potential locations where the query sequence can start in the reference video sequence, the fingerprints of the query and reference videos can to be computed (detailed in Section II.3.3.2) and matched (detailed in Section II.3.3.3). Moreover in order to enable the proposed video fingerprint to resist inner time-variant desynchronization, a synchronization block has been designed (as detailed in Section II.3.3.4).

II.3.3.1 Discrete Wavelet Transform coefficients statistics

Having in view the fingerprinting and watermarking applications [MIT 04b], [DUM 07] investigated the probability density law modelling the 2D-DWT coefficients and established at what extent the ergodicity hypothesis of these law holds.

A concise presentation of the proposed procedure [MIT 04a] follows:

 Be there a video sequence sampled from the 2D random process representing the video.

 Consider the video sequences as a set of L successive frames.

 Compute the DWT to the V component of each frame; these coefficients can be either considered according to their spatial position; sort coefficients in a decreasing order; record the largest R coefficients. -86 -Although the estimation of the probability density law modelling the 2D-DWT coefficients and its ergodicity has been determined for DWT coefficients disposed on ranks, a similar behaviour can be presumed for all the DWT coefficients. In the sequel, a collection of DWT coefficients are employed as video features for the TrackART video fingerprinting system.

II.3.3.2 Fingerprint computation

The fingerprint for the TrackART method was computed in the DWT domain due to its capacity of identifying the overall salient content of images and representing it through edges in the high frequency sub bands and due to the fine statistical properties featured by the wavelet coefficients. Moreover the Daubechies (9, 7) wavelets were used due to their very fine capacity of approximating the visual content.

The 2D wavelet coefficients are computed as following.

Assuming a pair of sampled query and reference frames, the fingerprint computation can take place. The fingerprint computation module consists of four main steps: spatial subsampling, color space conversion, wavelet transform and coefficients selection as illustrated in Fig. II. [START_REF] Massoudi | A Video Fingerprint Based on Visual Digest and Local Fingerprints[END_REF].

Fig.II.16. Fingerprint computation principle

In the first step, the spatial re-sampling to W × H pixels is performed on the reference and query frames. The CIF format (i.e. W = 352 and H = 288) was chosen in the current implementation in order to decrease the computational time, i.e. the computation of the fingerprint is directly proportional to the size of the video frames, therefore the smaller the size of the video frame, the shorter the processing time. Note that the CIF resolution is not mandatory and other formats can be equally chosen as they do not influence the stability of the video fingerprint.

In the second step, the color space is changed from the native RGB to HSV (Hue -Saturation -Value) and only the V component is considered further in the fingerprint computation. The HSV color space separates the luma (i.e. the image intensity, in the H and S components) from chroma (i.e. the color information in the V component), thus making the fingerprint invariant to color changes or distortions and increasing the robustness of the proposed method.

In the third step, a (9, 7) Daubechies wavelet transform at the resolution level of Nr = 3 is applied on the V component of every sampled frame.

Fourthly, the fingerprint is computed by selecting DWT coefficients from the query and the reference frames. The coefficient selection aims at conveying as much information as possible about the frames in order to achieve robustness to transformations like the frame aspect and frame content modifications (detailed in Section I.3.4.2-3). Consequently, all the DWT coefficients in each frequency sub-band (LL, LH, HL, HH) yielded by wavelet transform are selected.

-87 -Note that The fingerprint was computed in the DWT domain due to its capacity of identifying the overall salient content of images and representing it through edges in the high frequency sub bands. Moreover the Daubechies (9, 7) wavelets were used due to their very fine capacity of approximating the visual content.

However, other types of DWT like (2,2) or (4,4) can be used with a very low impact on robustness, while keeping the same uniqueness and reducing the computational time.

II.3.3.3 Fingerprint matching

Once the fingerprints of the query and the reference frames are computed, they have to be matched.

The proposed similarity measure between the fingerprints is the normalized correlation as given by the formula in (II.12). A perfect match (identity) between the query and the reference fingerprints is obtained when

      y x k t k f k k k k k t y x t f y x f N t f corr , ) ) , ( )( ) , ( ( 1 1
1   ; a value 0   indicates no correlation between k f and k t .
In practice, in order to be able to also retrieve content preserving replicas, the absolute value of the normalized correlation should be compared to some threshold T; should T   , then the query and the reference ranks are considered as similar. A match between the query and the reference frames is obtained when the coefficients in all four frequency sub-bands are correlated. Should the coefficients in one of the frequency sub-band be uncorrelated, the query and reference frames are considered as distinct.

-88 -Assuming the N 2D-DWT coefficients from a frequency sub-band are i.i.d. (identically and independently distributed) and that they follow a Gaussian distribution, and assuming the H 0 is true, the t test value of the test statistics, see (II.13), follows a Student probability density function of N-2 degrees of freedom: Considering that frames throughout a video sequence can be very similar, (for example in the case of scene with no motion) a query keyframe can turn out to be correlated with more than one reference frames. In order to establish which of the reference frames is the original version of the query frame, the match between the query and the reference frames is established with a correlation score as defined in (II.14) used. The correlation score is computed as the average of the correlation coefficients on all four sub-bands

4 / ) ( HH HL LH LL score          (II.14)
The higher score  , the higher the correlation and hence the similarity between two frames.

Consequently the pair of query-reference with the highest correlation score will be considered as matched.

The match between the query and video sequences is achieved by using a threshold E of correlated sampled frames. Should the number of sampled correlated frames be equal or higher than E the video sequences are considered as matched. Should the number of sampled correlated frames be lower than E the video sequences are distinct.

To conclude with, the fingerprints of a video sequence are the wavelet coefficients in every frequency sub-band for a selection of sampled frames. The matching between the wavelet coefficients is assured by the Rho test on correlation, whereas the matching between query and reference frames in hence based on the correlation score. The statistical error control is given by the type I statistical error in the test.

II.3.3.4 Synchronization

Some video processing operations (e.g. change of frame rate) or user manipulations like camcorder recording can induce in a video sequence, an inner time-variant desynchronization. Examples of these desynchronizations are the combined frames at shot transitions or slightly different shot durations between the original and the attacked video sequences.

Consequently, between the distorted and the original version video, the "video content -frame number" correspondence is not identical anymore. Therefore an operation which ensures that the features that will be used as fingerprints are computed from the same visual content in the original and distorted video sequences is needed.

Moreover, as the video content exhibits a high redundancy between adjacent frames, a frame subsampling is necessary in order to reduce the computational cost.

Actually, prior to the fingerprint computation, this synchronization should be achieved. While conceptually different tasks, in order to increase the efficiency of the TrackART method, the fingerprint computation/matching and the synchronization are nested. Actually, in the synchronization procedure described below, the fingerprint computed from candidate frames represents the feature on which the synchronization relies. Similarly, the fingerprint matching gives the similarity measure considered in the synchronization procedure.

To serve these aims, a procedure trying to synchronize the video content and to reduce the computational cost was designed to complement the fingerprint computation step.

The synchronization block consists in two stages: the first solves the light time-variant desynchronization whereas the second aims at solving distortions which induce a higher degree of desynchronization.

In the first stage of the algorithm, when attempting to synchronize the query with the reference sequence, the query frame is not matched to a single reference frame but to several frames from its neighborhood (e.g. In case a match between the query and the reference frames is obtained, the matching referencequery pair is stored and the process continues as the scope is to synchronize the entire query sequence with the frames of the reference sequence.

In order to reduce the computational cost, just a selection of query frames are matched to their reference frames. This selection is obtained by using a sampling strategy: considering a general sampling rate 25  T , the query is sampled with T and the reference with

   L T , where framePos L   
The Δ factor is used to compensate the desynchronisation that might exist between the query and reference frames.

In case no match is obtained after the reference neighborhood window The synchronization stage finishes when all the query frames corresponding to the query keyframes were processed as explained above, or when no matching pair query-reference frames are encountered for 5  Z processed query keyframes. This condition verifies the temporal consistency of the query sequence with respect to the reference sequence (i.e. if the succession of frames in the query sequence is the same as in the reference). Moreover, this condition automatically discards the similar, but not original versions reference frames retrieved by the localization algorithm as potential matched for the query keyframes.

-91 -

II.3.4.1 Reduced fingerprint computation

The synchronization block can retrieve a query video sequence based on the correlation of all DWT coefficients in each frequency band of a frame. The Reduced fingerprint block aims at reducing the number of DWT coefficients required for matching a video sequence.

The reduced fingerprint is computed similarly to the fingerprint proposed in Section II.3.3.2 following the steps 1-3 (formatting, color space conversion, wavelet coefficients). The difference appears in the fourth step, the coefficients selection. In the case of the reduced fingerprint, the coefficients selection (i.e. the fingerprint) aims at conveying information about the spatial -92 -distribution of salient features within the frames. Consequently, the 2D-DWT coefficients are selected depending on the role of the video sequence (reference or query).

For the reference video sequences, the R = 360 highest absolute value coefficients from the HL Nr and LH Nr frequency sub-bands of the transform V component, together with their locations are selected and stored in the coefficients matrix (as illustrated in The rank matrix is filled-in with all the fingerprints computed on then N sampled frames. The fingerprints of the frames consist of R = 360, 2D-DWT coefficients sorted in a decreasing order of their absolute values. It can be considered that the coefficients are disposed on 360 ranks (where "1" corresponds to the highest absolute value coefficient). This approach will turn to be particularly useful for fingerprint matching.

In the computation of the fingerprint for a query video sequence, the absolute value 2D-DWT coefficients are selected from the HL Nr and LH Nr frequency sub-bands of the V transform component from the locations indicated as salient by the reference coefficients matrices. After selecting the salient coefficients from every selected frame of the reference video, the rank matrix will be obtained.

II.3.4.2 Reduced fingerprint matching

Having the reduced fingerprints of the query and the reference they are matched analogously to the fingerprint matching done in Section II.3.3.3 with the normalized correlation coefficient.

The difference is the fact that the wavelet coefficients are disposed in ranks for the reduced fingerprint, hence the measures in the normalized correlation given by the formula in (II.13) are the following: k f and k t designate the 2D-DWT coefficients of the query and the reference videos respectively, on a rank k, -93 -A perfect match (identity) between the query and the reference rank is obtained when

1   ; a value 0   indicates no correlation between k f and k t .       y x k t k f k k k k k t y x t f y x f N t f corr , ) ) , ( )( ) , ( ( 1 1
) , (    (II.13)
The normalized correlation is computed between the absolute values of the 2D-DWT coefficients disposed on ranks, i.e. the columns of the rank matrix. Such a strategy is justified by the statistical investigation of the 2D-DWT coefficient behavior in [MIT 07], [DUM 08]: it was proved that the values taken by a rank in the 2D-DWT coefficient hierarchy feature stationarity and the corresponding probability density function was estimated using a mixture of Gaussian laws. Hence, the stationarity property of these coefficients ensures a certain degree of independence of the results with respect to the experimental corpus.

In practice, in order to be able to also retrieve content preserving replicas, the absolute value of the normalized correlation should be compared to some threshold T; should T   , then the query and the reference ranks are considered as similar. A match between the query and the reference video sequences is obtained when the majority of ranks (i.e. more than R/2 = 180) are correlated and when the number or selected frames N is larger than or equal to a threshold E = 10 frames. Should the majority of ranks be uncorrelated, or the threshold E< 10, the query and the reference video sequences are considered as distinct.

Assuming the k ranked absolute value 2D-DWT coefficients from the query and from the reference video sequence are i.i.d. (identically and independently distributed) and that they follow a Gaussian distribution, and assuming the H 0 is true, the t test value of the test statistics, see (II.13), follows a Student probability density function of N-2 degrees of freedom: where N and  are the same as above.

-94 - H , hypothesis is accepted, i.e. the 2D-DWT coefficients on the k rank are correlated.

In the experiments presented in this thesis, a significance level of 05 . 0   was considered. Note that in our application, the Rho test is run properly. First, the stationarity behavior of the 2D-DWT coefficients [MIT 07], [DUM 08] and the original video pre-processing ensures the i.i.d. behavior for the tested coefficients. Secondly, the robustness of the Rho test for non-Gaussian data may be invoked [WAL 02] in this case.

II.4 TrackART possible configurations

Due to the mathematical principles on which the TrackART method is built upon, the method can be used in two configurations.

The first configuration, denoted as TrackART Full Fingerprint consists the system illustrated in o Offline localization: provides a framework which can ensure the localization of the query sequence among the reference sequences. This framework is the bag of words approach which consists in: (1) -identifying local features in all the reference keyframes, (2) -describing the local features with a formal descriptor, (3) clustering all the local descriptors into a visual word vocabulary, (4) describing each reference keyframe as a collection of visual words (bag of words), ( 5) weighting the visual words in each keyframe according to their relative frequencies in both the keyframe and the reference vocabulary, (6) organizing an inverted index file which keeps for each visual words its occurrences in the reference keyframes.

 The online phase: a query video sequence is given to the system and its identity is inquired. It consists in four stages:

o Pre-processing stage: formats the query video sequence with the common formatting done for the reference video sequences.

o Online localization: provides possible starting locations of the query within the reference video sequence. It consists in two steps: (1) -identifying matching reference keyframes for the query keyframes, (2) re-ranking the matched reference keyframes according to a geometric consistency verification.

-96 -o Fingerprint: computed the fingerprints of the query and reference video fingeprints o Reduced fingerprint: reduces the amount of information needed for identifying a query video sequence. It consists of two steps: the reduced fingerprint computation and the reduced fingerprint matching.

The novelty of the TrackART video fingerprinting system can be identified at two levels.

First, at the offline phase was obtained by reconsidering, adapting and integrating state of the art image processing algorithms for fingerprinting purposes.

Second, at the online phase, the fingerprint and reduced fingerprint blocks are proposed in the present thesis. They are specified and designed so as to empower the fingerprint with the mathematical properties of the DWT coefficients and to grant statistical error control in the fingerprint matching.

The method thus obtained is a priori able to cope with two real life applicative characteristics:

 No constraint is imposed on the query and reference sequences length; the query can have an arbitrarily length and the localization and fingerprint modules are able to position it at the corresponding starting point in the reference sequence.

 No constraint is imposed on the distortions; the localization procedure was designed so as to take into account the effects of not only computer generated distortions but also live camcorder recording as well.

From the functional point of view TrackART is expected to answer the main challenges of a video fingerprinting system:

 The uniqueness property of fingerprints should be ensured by the fact that the video features are selected according to a mathematical model representing the visual content (the wavelet coefficients).

 The robustness property of fingerprints should be achieved by the fact that the mathematical models governing the selected features are robust to frame content and aspect distortions as well as video format distortions.

 The scalability to large scale databases should be ensured by the fact that a query localization procedure is employed and by the fact that the all the algorithms have fast implementations.

The relation between the TrackART method and the state of the art limitations are presented in Table II.2.

These a priori properties are experimentally validated in Part III of the present thesis.

III.3 Video retrieval use-case

A video identification and retrieval use case consists in identifying a query video sequence in a reference database of video sequences. When consulting the reference database with a query video sequence, all its replicas should be retrieved. Irrelevant video sequences (not connected to the query) should be ignored.

The reference video database consists of the entire HD3D-IIO corpus totalizing 14 hours of video content. The reference content is structured in its original chapter format, as detailed in Section III.

III.3.2 TrackART Reduced Fingerprint evaluation

This section investigates whether the fingerprint size can be reduced.

In the evaluation of the TrackART Reduced Fingerprint method, the precision and recall rates and the probabilities of false alarm and missed detection are investigated. -116 -distortions like brightness decrease/increase, contrast decrease, Gaussian filtering, conversion to grayscale, and sharpening the results are very good, the robustness to rotations by 2° and to StirMark yields quite poor results. This results can be explained as following.

A change in image contrast consists in multiplying each pixel value by a constant; a change in brightness consists in adding a constant to each image pixel. The very good results obtained in the case of brightness increase/decrease, and contrast decrease are achieved due to the normalized correlation coefficient which normalizes the DWT coefficients before computing their correlations, and hence, the changes induced in the images by these distortions are discarded.

The Gaussian filtering and the sharpening multiply each pixel value with a filtering kernel which takes into account a 3×3 pixel neighborhood. The effect of the Gaussian filtering is a smoothing, a blurring on the image, i.e. the high frequencies are attenuated. The effect of the sharpening filtering is contrary to the Gaussian filtering, the contours and the edges in the image are enhanced, i.e. the low frequencies are attenuated. The wavelet transform is computed as weighted averages and differences of the pixel values, and separate the image content into high and low frequencies, hence discarding the changes induced by such filters.

In the case of the small rotations, the unsatisfactory results can be explained by the fact that the content of the frames is changed (i.e. the frames are rotated by 2°, cropped and brought to the resolution of the original frame) and consequently the fingerprint of the rotated video sequence is computed from different content compared to the original sequence. Moreover, the fingerprint is dependent on the positions of the DWT coefficients, while the cropping and resizing change those positions in the rotated sequence.

Considering the StirMark attack, the results can be explained by the nature of the attack which performs local de-synchronization in the frame. The StirMark attack performs a global bending and random displacement in the image, followed by a slight deviation of each pixel (greatest at the center of the picture and almost null at the borders) and a higher frequency displacement. A transfer function that introduces a small and smoothly distributed error into all sample values is applied and a medium jpg compression is performed.

Analogous, to the case of rotations, the StirMark attack modifies the content of the StirMarked frames, and hence the fingerprints are computed from different content.

The conclusion which can be drawn from the results of the first experiment is that the proposed fingerprint is robust to distortions which preserve the content of the video frames and which do not induce local de-synchronizations inside the video frames.

By comparing the results obtained with the TrackART Full Fingerprint configuration and TrackART Reduced Fingerprint, it can be observed that for all the distortions, a significant gain is achieved by the TrackART Full Fingerprint, as presented in Table III

III.4 Live camcorder recording use-case

The camcording use case consists of tracking an in-theatre camcorder recorded video sequence in a database of original video sequences. In such a case, the attacked video sequences are obtained by capturing with a non-professional camcorder the original sequence which is displayed on a screen.

The reference video database for the camcording use case consists of the entire HD3D-IIO corpus totalizing 14 hours of video content structured in chapters, as detailed in Section III.2.

-118 - .c: the PC screen has two functions, i.e. screen and projector, while the camcorder was positioned with its optical axe perpendicular on the PC screen, but the same random capturing angles, -2° ≤ Ω ≤ 2°. were encountered.

In the proposed experimental set-up, the angle Ω was not considered larger than 2° and the position of the camcorder was approximately maintained in a central position of the screen in order to capture the entire video content displayed on the screen.

III.4.1 TrackART Full Fingerprint evaluation

In the described set-up for the live camcorder recording use case, the evaluation of the TrackART Full Fingerprint video fingerprinting system feature excellent results, in terms of average values of precision, recall, probability of false alarm and miss detection as presented in Table III

III.4.2 TrackART Reduced Fingerprint evaluation

The evaluation of the TrackART Reduced Fingerprint video fingerprinting system under the live camcorder use case has been also performed and the results obtained in terms of average values of precision, recall, probability of false alarm and miss detection are presented in Table III It can be observed that the values in Table III.6 indicate an intuitive discrepancy between the precision and false alarm. This can be explained by the computation formulas of the two metrics.

The probability of false alarm is computed as a rate by taking into the account the length of the database and the length of the query sequences.

-120 -Precision denotes the probability of retrieving replica video sequences for a given query out of all the retrieved video sequences. Hence, the precision does not take into account the length of the query nor of the database.

Considering the case there is no false positive and no true positive detected by the system for a certain query video, the value of precision will be put to zero, although the result is a division by zero. This situation yields the worst case for the precision metric, while for the probability of false alarm metric it would yield zero which constitutes the best case.

In Table III.7 the gain the TrackART Full Fingerprint configuration achieves over the TrackART Reduced Fingerprint configuration is presented for each evaluation metric.

It can be observed that the TrackART Full Fingerprint configuration improves the precision and recall rates with 31%, whereas the probability the false alarm is decreased by 29% and the probability of false alarm is increased with 0.001.

The gain obtained by the TrackART Reduced Fingerprint method over the TrackART Full Fingerprint can be explained as in the video retrieval use case by two facts. Firstly, the correlation between the frames of the query and reference video sequences performed in the Fingerprint block is based on a statistical ground and provides reliable results. Secondly, the computation of the video fingerprint employs information (i.e. location of the DWT coefficients) from the video frames which is subject to change in distortions like the camcorder recording, i.e. random and abrupt geometric transformations.

Gain

III.5 Computational cost

The computational cost for the TrackART video fingerprinting method can be computed by assessing the computational costs of every functional block of the method. Considering the method has two phases (the offline and the online), the computational cost will be computed individually for each of the two phases.

The parameters employed in the TrackART video fingerprinting system are presented in Table III.8 and the computational complexity of the algorithms is presented in Table III.9.

It can be noticed that:

 each operation has a maximum complexity of

) log ( n n O
, where n is the underlying data size; there is only one exception, namely the computation of the SIFT descriptor which has an

) ( 2 G J O 
complexity. However, J = 8 and G = 4, irrespective to the frame size.

 the heavier computational cost is performed in the offline phase, whereas the online phase performs light computational operations.

 the offline phase is computed only once, and then used each time there is a query in the online phase.

The properties featured by the computational cost complements the automatic localization procedure thus granting the scalability for the TrackART method. The functionality of the fingerprinting demonstration software is assured by four steps corresponding to the four blocks in Fig. III.9 In the first step the system takes as input an unknown/not identified sequence of video. The second step introduces the fingerprinting process by computing the fingerprint of the input video whereas the third step performs a search in a database of fingerprints. This search step will provide a fingerprint which is the closest match for the fingerprint of the input video sequence. Given the fact that each fingerprint from the database references a known video, the system is able to retrieve the identity of the unknown input video sequence. 

Step 1: Fingerprinting application: a video can be selected from the first drop-down menu "Choose video" and viewed in the Windows Media Player window. From the second dropdown menu "Choose fingerprinting method" a fingerprinting method can be selected. By clicking on the "Generate fingerprint" button, the fingerprint of the selected video will be computed according to the desired method.

Step 1 is illustrated in Fig.III.10.



Step 2: The message box with the text "Fingerprint computed" announces that the fingerprint computation process ended. Following, the extracted fingerprint has to be looked-up in the reference fingerprints database so that the name of the video will be retrieved. The look-up step starts when the "Search the database" button is pressed.

III.7 Conclusion

The TrackART framework introduced in PART II is experimentally validated for two configurations as explained in Section II.4: TrackART Full Fingerprint (i.e. which employs all the wavelet coefficients from video frames) and TrackART Reduced Fingerprint (i.e. which employs a reduced selection of wavelet coefficients).

The evaluation considers two use cases, namely, the retrieval of video sequences under computer generated dirtsortions and live camcorder recording. The former use case emcompases both mundane (like the Gaussian filtering, sharpening, contrast and brightness changes) and malicious (like small rotations and the StirMark attack) distortions. The latter use case deals with the very sophisticated malicious distortion of live camcorder recording which includes and combines abrupt geometric transformations with brightness, color and contrast variations.

The quantitative results are obtained on a corpus totalizing 14 hours of reference video content and 24 hours of distorted video content for the video retreival use case and 1 hour of live camcorded content for the live camcorder recording use case.

The results show that when assuming mundane computer generated distortions, the TrackART Reduced Fingerprint reaches very good values: the probability of false alarm reaches its ideal null value, the probability of missed detection is 0.026, precision and recall equal to 0.96. This configuration is particularly useful when no malicious distortion occur which is the case for example in large scale archives of INA.

When malicious distortions are encountered, the TrackART Reduced Fingerprint has to be replaced by the TrackART Full Fingerprint. With this configuration, the results are kept at a very good level: the probability of false alarm maintains its ideal null value, the probability of missed detection is 0.025 whereas precision and recall are equal to 0.97. It can be observed that the TrackART Full Fingerprint configuration ensures very good results even under malicious computer generated results, but at the expense of increasing the length of the fingerprint (i.e. the size of the full fingerprint is 17 times larger than the size of the reduced fingerprint).

When considering the complex case of live camcorder recording use case, the TrackART Full fingerprint configuration proved itself to be strong enough and featured very good results: the probability of false alarm equal to 0.000016, the probability of missed detection equal to 0.041, precision and recall equal to 0.93. When compared to the CST limits (i.e. probabilities of false alarm and missed detection lower that 0.05 and precisions and recall higher than 95%), the results can be considered satisfactory. While complying with the limits set for the probabilities of false alarm and missed detection, the precision and recall are just 2% lower.

The in depth analysis of the computational cost for the TrackART video fingerprinting method proved its feasibility and scalability. Firstly, each operation has a maximum complexity of

) log ( n n O
, where n is the underlying data size; there is only one exception, namely the computation of the SIFT descriptor which has an

) ( 2 G J O 
complexity. However, J = 8 and G = 4, irrespective to the frame size. Secondly, the heavier computational cost is performed in the offline phase, whereas the online phase performs light computational operations. Thirdly, the offline phase is computed only once, and then used each time there is a query in the online phase.

Resumé

Mots clés

Model théorique pour le traçage du contenu vidéo, les limites théoriques d'un système de traçage de contenu vidéo, modèle basse sur la théorie de l'information.

Conclusions

The worldwide mass production context brings technology closer to people. Affordable capturing, processing and storage devices along with wide spread broadband Internet access, empowers people to easily produce, manipulate and distribute large amounts of visual content. Hence, efficient tools for searching, retrieving and tracking distorted video content in very large video databases have to be deployed in order to serve the purposes of applications like copyright protection, parental control. Video fingerprinting is an appealing solution to these issues Despite the wide range of methods that have been investigated in the state of the art for video fingerprinting methods, limitations have been identified at three levels. Firstly, the uniqueness property of fingerprints is not granted by a mathematical comprehensive approach. Secondly, the robustness property of fingerprints is based on partial mathematical models without a general framework able to address the wide variety of existing distortions. Moreover, the academic state of the art methods have not addressed yet, at our best knowledge, the challenging case of live camcorder recording. Thirdly, in general the state of the art video fingerprinting methods do not have query localization support able to result in scalable solutions for large scale databases.

The video fingerprinting method advanced in the present thesis (TrackART) is characterized from the structural point of view, by two phases: the offline phase and the online phase.

The offline phase enables the localization of a query sequence within a reference video sequence. Its purpose is to process the reference video collection and to map the visual content to a new representation space. This phase comports a usage innovation: it reconsiders, adapts and integrates state of the art image processing algorithms for fingerprinting purposes.

The online phase: a query video sequence is given to the system and its identity is inquired. This phase comports a design innovation: the fingerprint and reduced fingerprint blocks are advanced in the present thesis so as to empower the fingerprint with the mathematical properties of the DWT coefficients and to grant statistical error control in the fingerprint matching.

From the functional point of view, TrackART answers the main challenges for a video fingerprinting system (described in Table IV.1):

 The uniqueness property of fingerprints is ensured by the fact that the video features are selected according to a mathematical model representing the visual content (the wavelet coefficients).

 The robustness property of fingerprints is achieved by the fact that the mathematical models governing the selected features are robust to frame content and aspect distortions as well as video format distortions.

 The scalability to large scale databases is ensured by the fact that a query localization procedure is employed and by the fact that the all the algorithms have fast implementations.

-136 - The worldwide mass production context brings technology closer to people. Affordable capturing, processing and storage devices along with wide spread broadband Internet access, empowers people to easily produce, manipulate and distribute large amounts of visual content. Such a situation raises complex challenges in various multimedia domains (copyright protection, illegal distribution and management of massive databases, …). Despite the particular applicative target, issues connected to video identification, authentication, indexation, retrieval, searching, navigation, organization and manipulation have to be always addressed.

The bottleneck in developing practical solutions for such problems makes the cinematography industry very suspicious in using Internet as a main movie distribution support.

Currently, a solution intensively considered in research studies is video fingerprinting also referred to as content-based copy detection or near-duplicate copy detection.

Throughout the current study, a copy, a replica or an attacked video is obtained from some original video excerpt by means of any transformation/distortion, such as addition, deletion, modifications (of aspect, color, contrast, encoding, …), or camcording [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF], see Table 1. Due to the practical applicative field of video fingerprinting, although the modifications considered in this classification alter the quality of the video content, they do not destroy its commercial or entertainment value. These modifications can be classified in three major categories depending on the domain they affect, namely the video format, the frame aspect and the video content. Video fingerprints can be best defined in relation with human fingerprints, [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF], as illustrated in Figure 1. While the human fingerprint can be seen as a human summary (a signature) that is unique for every person, the video fingerprint can be seen as some short video feature (e.g. a string of bits, color histograms, …) which can uniquely identify that video.In practice, video fingerprints are used just as human fingerprints: they are first computed and then searched for in a database, according to a given similarity measure.

Assume the case in which S video sequences have their fingerprints computed and are sequentially searched for in the database. A correct answer in such a matching procedure is obtained when the same visual content is detected not only in its original video sequence but also in all its replica videos; be there tp the number of such correct answers. Practical fingerprinting methods may also come across with two types of matching errors. First, some video content existing in the database might not be retrieved; be fn the number of such erred decisions. Secondly, the detection procedure can also yield a false positive i.e. take some visual content for another one. Be fp the number of such situations. Note that S = tp + fp +fn.

Video fingerprints have two main properties:  Uniqueness: fingerprints extracted from different video content should be different. This property is assessed by two objective evaluation criteria: the probability of false alarm (P fa ) and the precision rate (Prec), defined by the following formulas:

fp fn tp fp P fa    (1) fp tp tp   Prec (2)
 Robustness to distortions: fingerprints extracted from an original video sequence and its replicas should be similar in the sense of the considered similarity metric. The robustness property is also quantified by two objective evaluation criteria, namely the probability of missed detection (P md ) and the recall rate (Rec), as defined below: In the sequel, the fingerprinting state of the art will be structured according to the type of feature representing the fingerprint (Table 2) and the similarity metric achieving the fingerprints matching (Table 3).

The video features used as fingerprints can be computed only from the visual content (i.e. the case of mono-modal methods) or from visual and audio content (i.e. the case of multimodal methods). Independently with respect to its type, the video fingerprint can be computed at different granularity levels, e.g. frames, keyframes, blocks or regions of frames, group of frames, points of interest.

According to the domain in which the fingerprints are computed, the group of mono-modal methods can be of four types: spatial, temporal, transform and color.

The spatial fingerprints computed on blocks, regions of frames or whole frames are robust to non-geometric distortions, but they lack in robustness against geometric modifications (e.g. cropping, rotations). The interest points based features have a high robustness against the geometric distortions and transcoding transformations but lack in resilience against changes in color, illumination and filtering. Moreover, this type of features poses problems of uniqueness in the case of very similar video sequences, (e.g. TV news) therefore needs to be used in combination with other features. The category of temporal fingerprints is generally robust to global changes in the quality of the video like non-geometric modifications of the frame aspect and they can resist several encoding (e.g. MPEG compression), but they are generally sensitive to distortions affecting the video format (e.g. frame-rate changes frame-dropping, transcoding) and to geometric modifications).

Transform based fingerprints ensure robustness to geometric and non-geometric frame aspect modifications and to video format modification but are sensitive to modifications of video content such as cropping and content addition.

The color based category of fingerprints lacks resilience to global variations in color and illumination but can be used along with other features in order to enhance discriminability. As explained above, the mono-modal methods employ a reduced number of visual features as fingerprints in order to identify the limitations that they pose and their possible applications. The multi-modal types of fingerprints combine the advantages of video and audio features of videos can achieve better results with faster computation time than the mono-modal methods.

The frequent disadvantage of the multi-modal types of fingerprints is their excessive number of computed features, which leads to redundant video information used as fingerprint (e.g. [START_REF] Gao | PKU-IDM@TRECVID-CCD 2010: Copy Detection with Visual-Audio Feature Fusion and Sequential Pyramid Matching[END_REF] using SIFT and SURF features simultaneously). As the computational resources increase steadily due to technological development, extra computation is not considered a prohibitive factor. However, a clear mathematical ground for video fingerprinting should not be ignored. According to the similarity distance employed for matching, the fingerprinting methods can be divided in two categories, distance based and probability based, as illustrated in Table 2.

-144 -

DWT-BASED VIDEO FINGERPRINTING

Due to its possibility of representing, in a very compact way, salient characteristics of the video content and also to its low complexity, the 2D-DWT is already intensively considered in practically all image processing applications, from compression and watermarking to defect detection in garments. Our study investigates whether the 2D-DWT can be employed in order to uniquely and robustly identify the visual content.

In this respect, a new video fingerprinting method is advanced. In order to extract a fingerprint from a video sequence (arbitrarily chosen), that sequence is first pre-processed, then a 2D-Wavelet transform is applied to its frames and finally a certain selection of the coefficients is carried on in order to obtain the fingerprint per-se, see Section 3.1. The fingerprint matching is achieved by a repeated test on correlation, see Section 3.2.

Fingerprinting computation principle

Be there a video sequence, represented in a given format (compressed or not). The pre-processing step aims at increasing the invariance of the envisioned fingerprint to different video processing operations, be they malicious (attacks) or mundane (ordinary video manipulations). First, the video sequence is decoded into frames in order to diminish the influence of a particular video format or codec. Second, a temporal sub-sampling to 1 fps is performed in order to eliminate the redundancy between adjacent frames and to speed-up the fingerprint computation. Third, a spatial re-sampling to W × H pixels (in our experiments, W = 352 and H = 288) is performed on the sampled frames, thus increasing the robustness of the method to frame size changes attacks. Fourthly, in order to extract the salient information contained within the frame while reducing the computational costs, the down-sampled frames are represented in the HSV (Hue -Saturation -Value) color space with the V component normalized to the [0, 1] interval.

In the 2D-DWT Transform step, a (9, 7) Daubechies wavelet transform at the resolution level of Nr = 3 is applied on the V component of every sampled frame. The coefficients selection (i.e. the fingerprint) aims at conveying information about the spatial distribution of salient features within the frames.

In the coefficients selection step, the 2D-DWT coefficients are selected depending on the role of the video sequence (reference or query).

For the reference video sequences in the database, the R = 360 highest absolute value coefficients from the HL Nr and LH Nr frequency sub-bands of the transform V component, together with their locations are selected and stored in the coefficients matrix (as illustrated in Figure 2.a). The coefficient matrix in Figure 2.a illustrates the fingerprint of a sampled frame, while the fingerprint of an entire reference video sequence is presented in Figure 2.b and it is called the rank matrix. The rank matrix is filled-in with all the fingerprints computed on then N sampled frames. The fingerprints of the frames consist of R = 360, 2D-DWT coefficients sorted in a decreasing order of their absolute values, it can be considered that the coefficients are disposed on 360 ranks (where "1" corresponds to the highest absolute value coefficient). This approach will turn to be particularly useful for fingerprint matching.

In the computation of the fingerprint for a query video sequence, the 2D-DWT coefficients are selected from the HL Nr and LH Nr frequency sub-bands of the V transform component from the locations indicated as salient by the reference coefficients matrices. After selecting the salient coefficients from every sampled frame of the reference video, the rank matrix will be obtained.

Fingerprint matching

The proposed similarity measure between fingerprints is the normalized correlation as given by the formula in [START_REF] Gao | PKU-IDM@TRECVID-CCD 2010: Copy Detection with Visual-Audio Feature Fusion and Sequential Pyramid Matching[END_REF]. -148 -investigation of the 2D-DWT coefficient behavior in [START_REF] Dumitru | Video Modelling in the DWT domain[END_REF] and [START_REF] Buccigrossi | Image Compression via Joint Statistical Characterization in the Wavelet Domain[END_REF]: it was proved that the values taken by a rank in the 2D-DWT coefficient hierarchy feature "stationarity" and the corresponding probability density function was estimated using a mixture of Gaussian laws. Hence, the "stationarity" property of these coefficients ensures a certain degree of independence of the results with respect to the experimental corpus. In practice, in order to be able to also retrieve content preserving replicas, the absolute value of the normalized correlation should be compared to some threshold T; should T 

      y x k t k f k k k k k t y x t f y x f N t f corr , ) ) , ( )( ) , ( ( 1 1



, then the query and the reference ranks are considered as identical.

The value of the T threshold is statistically determined according to the Rho test on correlation [START_REF] Walpole | Probability & Statistics for Engineers and Scientists[END_REF]. This test is individually applied to each of the R = 360 ranks under investigation; the null/alternative hypotheses are: A match between the query and the reference video sequences is obtained when the majority of ranks (i.e. more than R/2 = 180) are correlated. Should the majority of ranks be uncorrelated the query and the reference video sequences are considered as distinct. Assuming the k ranked 2D-DWT coefficients from the query and from the reference video sequence are i.i.d. (identically and independently distributed) and that they follow a Gaussian distribution, and assuming the H 0 is true, the t test value of the test statistics, see [START_REF] Su | Robust video fingerprinting based on visual attention regions[END_REF], follows a Student probability density function of N-2 degrees of freedom: where N and  are the same as above.

As illustrated in Figure 3, if . Note that in our application, the Rho test is run properly. First, the "stationarity" behavior of the 2D-DWT coefficients [START_REF] Dumitru | Video Modelling in the DWT domain[END_REF], [START_REF] Buccigrossi | Image Compression via Joint Statistical Characterization in the Wavelet Domain[END_REF] and the original video pre-processing ensures the i.i.d. behavior for the tested coefficients. Secondly, the robustness of the Rho test for non-Gaussian data may be invoked [START_REF] Walpole | Probability & Statistics for Engineers and Scientists[END_REF] in this case.

-150 - The query video corpus consisted of 140 video sequences chosen from the reference database (20 original video sequences and 20 replica video sequences for each of the attacks). The replica video sequences were obtained by considering the following modifications: contrast decrease (25%), linear filtering (Gaussian filter), conversion to grayscale, sharpening, brightness increase (20%) and brightness decrease (25%) as illustrated in Figure 6. . The experimental set-up for the ARTEMIS video captures is depicted in Figure 10.c: the PC screen has two functions, i.e. screen and projector, while the camcorder was positioned with its optical axe perpendicular on the PC screen, but the same random capturing angles,

      2 2
were encountered. In the proposed experimental set-up, the angle Ω was not considered larger than 2° and the position of the camcorder was approximately maintained in a central position of the screen in order to capture the entire video content displayed on the screen.

Due to the severe modifications induced in the camcorded video, a more elaborated approach is needed. Firstly, in order to address the modifications induces in the video by the re-encoding performed by the camcorder (frame-rate changes, bitrate changes, A/D, D/A conversions) the pre-processing step (described in Section 3.1) needs two extra operations: a transcoding to the original parameters (bit rate, frame rate, GOP) by using the ffmpeg libraries [START_REF] Yeh | NTNU-Academia Sinica at TRECVID 2010 Content Based Copy Detection[END_REF] and the black letterboxing removal. Secondly, in order to eliminate as much as possible the inner time-variant desynchronization induced between the query and the reference frames by the very camcording mechanisms a dynamic synchronization block was designed, as illustrated in Figure 11. To this aim, the fingerprinting matching is no longer performed between frames sampled according to a fixed sampling period but an adaptive mechanism is considered cf. Figure 12.

In the experiments of this study, a coarse synchronization of the starting time of the reference and query is already available (e.g. obtained through a shot detection procedure).

-154 - Be there f 1r the first frame sampled from the reference sequence by using a fixed-period sampling of P frames. The same P period is considered to sample the query and a neighborhood window of L frames is selected accordingly. In this window, the frame which is the closest to the f 1r frame (in the sense of some similarity measure, e.g. relative mean square error, eq. 7) is selected; be this frame f 1q . This procedure is recursively applied, by considering f 1r and f 1q as the starting frames for the rest of the reference and query sequence. This way, dynamic desynchronization lower than L/2 frames can be compensated inside each P frame interval.

    x x x f x t x f t f MSE 2 2 )) ( ( )) ( ) ( ( ) , ( (7)
In the formulas above, f and t designate the 2D-DWT coefficients of the query and the reference images respectively. In our implementation the size of the window was considered L = 7 frames and the frame sampling period was P = 25. The results are presented in Table 5 and point to very good false alarm and missed detection probabilities, significantly lower than the limits imposed by the CST. Precision and recall rates indicate reasonable retrieval accuracy but still need to be improved in order to cope with the CST constraints. The results can be further improved by an adapted shot detector and by finding an efficient matching procedure between the reference and query sampled frames in the resynchronization step.

Computational time

The main steps in our method are the computation of the DWT (hence, an significance level. Note that the stationarity of the information sources modeling the hierarchy of the 2D-DWT coefficients allows us to run such a test with statistical rigor. This very fine mathematical model also allows us to consider results obtained on particular databases as being representative for larger corpora. A future direction of our research will be to exploit the probability density function of the 2D-DWT coefficients during the fingerprinting matching procedure. The advanced method was tested in two applicative use cases related to the cinematography industry (the experiments being jointly conducted with CST experts): video retrieval in databases and live camcorded sequence tracking. In the former case, very good results in terms of probability of false alarm and missed detection lower than 0.0005, precision and recall higher than 0.97 were obtained. Note that the procedure involves only low computational complexity algorithms (the 2D-DWT computation with linear complexity ). While imposing the same computational constraints on the algorithm, the latter case resulted in practical acceptable performances: probability of false alarm equal to 0.00009, probability of missed detection equal to 0.0036, precision and recall equal to 0.72. To our best knowledge, this is the first time when the tracking of the live camcorder recording video sequences can be achieved in practice by completely automatic procedures. Further work will be devoted to developing an adapted shot detector and to optimizing the matching procedure between the reference and query sampled frames in the resynchronization step. In this respect, SIFT techniques can be completed with some MPEG-7 descriptors. Obtaining significant gain in matching speed is also part of our future work. This can be obtained by performing an offline clustering of the database, e.g. by PCA means. Video fingerprints can be best defined in relation with the human fingerprints, [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF], as illustrated in Figure 1.

While the human fingerprint can be seen as a human summary (a signature) that is unique for every person, the video fingerprint can be seen as short video features (e.g. a string of bits with no particular format constraint) which can uniquely identify every video.

Fingerprinting methods have three main characteristics:

 Robustness to distortions: fingerprints extracted from a video subjected to content-preserving distortions (attacked video) should be similar to the fingerprints extracted from the original video. A robust fingerprinting method should ensure low probability of missed detection, i.e. a low probability of not retrieving an attacked video registered in the database.

 Uniqueness: fingerprints extracted from different video clips should be considerably different. A fingerprinting technique featuring uniqueness should ensure low probability of false alarm, i.e. low probability in retrieving a video sequence which is neither the query nor its replicas.

 Database search efficiency: for applications with a large scale database, fingerprints should be conducive to efficient database search (fast fingerprint computation and matching, compact form, …).

The present study is focused on a video retrieval applicative scenario. In this respect, a video sequence (arbitrarily chosen) is used as a query, and its would-be replicas are searched for in the database (i.e. within the reference video sequences.

In a previous study [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF], the authors have already addressed the Discrete Wavelet Transform (DWT) video fingerprinting issue. Although that method proved to be very efficient in practice (resulting in probability of false alarm and missed detection lower then 0.005), it is intrinsically limited by its empirical approach.

The present paper also deals with the DWT-based video fingerprinting, this time focusing on deriving a related method allowing for an objective, mathematical decision rule to be specified. -164 -While only the DWT coefficients compose the fingerprint of the query video sequence, the locations of these coefficients will be used to compute the fingerprint of the reference video sequences.

The coefficient matrix in Figure 3 illustrates the fingerprint of a sampled frame, while the fingerprint of the entire query video sequence is presented in Figure 4 and it is called the rank matrix.

The rank matrix is filled-in with all the fingerprints computed on the N sampled frames. Because the fingerprints of the frames consist of  R 360 DWT coefficients sorted in a decreasing order, it can be considered that the coefficients are disposed on 360 ranks, with "1" being the highest and "360" being the smallest value coefficient. This approach will turn to be particularly useful for fingerprint matching.

Fingerprint matching

The proposed similarity measure between fingerprints is the normalized correlation as given by the formula in [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF].

      y x k t f k k k k k k t y x t f y x f N t f corr , ) ) , ( )( ) , ( ( 1
1 ) , (    (1)
In (1), A perfect match (identity) between the query and the reference rank is obtained when

EXPERIMENTAL RESULTS

Video corpus

The quantitative results were obtained by processing 3 corpora consisting of 3, 6 and 9 hours of original content, belonging to 7 different movies from the HD3D-IIO corpus [3]. The content combines indoor and outdoor scenes, unstable and arbitrary lighting conditions, still and high motion scenes.

The corpora are composed of 540 video excerpts of either 20, 40, 60 seconds each, and of their 6 attacked versions. The following attacks have been considered: conversion to grayscale, contrast decrease, sharpening, small rotations (2°), linear filtering (Gaussian filter) and geometric (StirMark random bending) attacks simulating the in-theater camcordering.

Consequently, the final corpora are composed of 3780 sequences of 20, 40, 60 seconds each, i.e. 21, 42, 63 hours of video for each corpus, respectively.

Targeted application

The present experimental study is focused on video identification, Figure 5. The database is represented by one of the above corpuses containing 3780 video sequences of 20, 40, 60 seconds respectively.

When inquiring this database with one of its sequences, the 7 versions (one original and six attacked) should be retrieved. A missed detection occurs when at least one of the expected 7 versions is not retrieved. A false alarm is encountered when at least one sequence which is not related to the query is retrieved. -168 -

Computational complexity

The main steps in our method are the computation of the DWT (hence, an

) ( H W O  complexity),
the sorting of the corresponding coefficients (hence, an

) log ( R R O
complexity and the matching of the fingerprints by a normalized correlation coefficient (hence, an ) log ( R R O complexity). Figure 8 illustrates the computation times for the proposed fingerprinting method.

The task durations were computed using a system with the following configuration: Intel Xeon CPU processor at 2.8 GHz with 6 Go of RAM memory, with an operating system working on 32 bits.

CONCLUSION AND PERSPECTIVES

The present paper presents a simple yet very efficient video fingerprinting method. The fingerprint is represented by a hierarchy of largest 2D-DWT coefficients selected from two low-frequency subbands. The fingerprint matching is carried on by a normalized correlation coefficient and the decision is based on the Rho test on correlation. Applied to different lengths of the video sequence (i.e. 20, 40, 60 seconds) and tested on reference corpora of 21, 42, 63 hours of visual content respectively, the method featured These good performances result from the stationarity of the information sources modeling the hierarchy of the DWT coefficients. A future direction of our research will be to exploit the probability density function of the DWT coefficients during the fingerprinting matching procedure.

The experiments performed in the present paper pointed out that the optimal length for a video sequence to be identified would be 40 seconds. This 40 seconds duration seems to be long enough so to reflect the inner salient content of the sequence (hence, to reduce the probability of missed detection) but short enough so as to ensure low values for the false alarm probability. Future work will be devoted to the integration of the proposed fingerprinting method for a movie identification application. This would suppose first a shot detection and then a search according to

Figure 1 :

 1 Figure 1: Human versus video fingerprinting

  les principales définitions et limitations de l'état de l'art pour le traçage du contenu vidéo.

Fig.I. 1 .Fig.I. 1 :

 11 Fig.I.1: Timeline of memorable inventions and advancements of the digital revolution

Fig. I. 2 :

 2 Fig. I.2: Sales in PCs, smart phones and digital cameras 2009-2012 [GAR 12]

Fig.I. 3 :

 3 Fig.I.3: Video content uploaded on YouTube every minute

Fig.I. 4 :

 4 Fig.I.4: Human versus video fingerprinting Content-based copy detection systems (CBCD) should not be confused with Content Based Video Retrieval (CBVR) system. On the one hand, the CBVR systems aim at retrieving visually similar videos, i.e. from the same genre of category, for instance, soccer games, or episodes of soap operas. On the other hand, the CBCD systems aim at retrieving the original version of a query sequence, and have to be able to discriminate between different content belonging to the same genre as illustrated in Fig.I.5, [LAW 06].

  Fig. I.6.

Fig.I. 6 :

 6 Fig.I.6: Video fingerprinting system schema

Fig.I. 7 :

 7 Fig.I.7: Video fingerprinting system: online and offline phase

Fig.I. 8 .

 8 a illustrates how two different video contents are identified as having different identities based on the matching of their fingerprints.

Fig.I. 8 :

 8 Fig.I.8: (a) The uniqueness property; (b) The robustness property

  is the total length in (minutes) or the false alarms and l fn is the total length in (minutes) or the missed detections, refdata T is the total length (in minutes) of the entire reference database and target T is the total length (in minutes) of the video replicas in the reference database. Hence refdata T and target T are fixed values, known by pre-processing the database, while fpl and fn l are random results (experiment dependent) outputted by the system)

Fig.I. 10 :

 10 Fig.I.10: Affine transforms induced by camcording

Fig. I. 11 :

 11 Fig. I.11 : Frames rotated with 2°, 3°, 5° and 10° in (a) column and frames rotated and cropped in (b) column

  Fig. I.13: Television specific modifications

14 .A

 14 possible use case for identification of multimedia in large databases is interactive advertising. In Fig.I.15, an agency has created a digital fingerprint for their specific TV commercial. When the fingerprint of the content playing on the screen is detected, a pop-up overlay dialog box is triggered on top of the advertisement asking the viewers if they want to take advantage of the coupon being offered on screen. By pressing their TV remote select button the viewers confirm they would like the coupon offered. Using the LAN connection, a coupon request is sent via the Internet to the retail web site. The requested coupon is sent by the retailer to the viewer's smart phone *AUD 12c].

Fig.I. 14 :

 14 Fig.I.14: Video Identification and retrieval of video sequences

Fig.I. 15 :

 15 Fig.I.15: Interactive advertising

Web 2 .

 2 0 services like YouTube, Vimeo, DailyMotion offer platforms for users to view and exchange videos. On numerous occasions YouTube was accused of being an illegal distribution channel and trials such as Viacom [WIR 12] pushed Google Inc. (the YouTube holder) to implement technology able to detect copyright infringement in their video database. Such technology relies on video fingerprinting principles and in the case of YouTube it is named the Content ID system. In order to achieve copyright infringement-free video database by means of video fingerprinting, content owners would have to provide reference fingerprints to user generated content (UGC) sites, which would allow through the matching procedure the identification of the video content. According to this identification and to the business or copyright rules established for each video, action can be taken, e.g. allow, filter, notify as illustrated in Fig.I.16.

Fig.I. 16 :

 16 Fig.I.16: Video filtering in UGC platforms

  Through a k-nearest neighbor matching algorithm for interest points, [LAW 06] localizes similar frames from the query and the reference video sequence and then trough a voting function based on a label description of interest point motion, the matching video sequences are identified. Another approach used by [IND 09] and [JIA 11] is the Locality Sensitive Hashing (LSH) which consists in indexing binary fingerprints in a high dimensional indexing data structure, [GIO 99]. The LSH indexes a bit string representing points in a high dimensional space. Given a query bit string example and some distance threshold m, the LSH returns a list of stored bit strings within Hamming distance m of query bit string. A nearest neighbor search and mapping of each query frame to the closest reference frame is proposed by [FOU 11]. A different approach comes from [HIL 10] which proposes as localization strategy the linear fit filtering (RANSAC [FIS 81]) and the Bi-partite match filtering which filters out a list of candidate video sequences yielded from the fingerprint matching algorithm. As a side note, in the video fingerprinting methods which use the audio component, [JIA 11], [MUK 10], the localization strategy generally starts with a localization based on audio: e.g. the WASF audio descriptor is computed and then searched for in the database in [JIA 11], or the spectrogram of the audio signal is computed, divided into small regions and then query regions are localized in the reference sequence.

  Fig.I.16: 3D transform fingerprinting principle

  In [OOS 02], Oostveen et al. propose a 32-bit fingerprint obtained by quantizing the values obtained by differencing the mean values of neighboring blocks of luminance inside a frame and by differencing the mean values luminance blocks in subsequent frame, Fig.I.19.

Fig.I. 19 :

 19 Fig.I.19: Block diagram of the differential block luminance algorithm

  the L 2 distances between descriptors of consecutive and subsequent frames the motion -36 -trajectories of the interest points are built as illustrated in Fig.I.21. For each trajectory, the following salient characteristics are considered:  the mean descriptor (defined as the average of each component of the local descriptors) is associated;  the average position along the trajectory

Fig.I. 21 :

 21 Fig.I.21: Algorithm for points of interest trajectory estimation

Fig.I. 22 :

 22 Fig.I.22: Video copy detection framework in [LAW 07]

  the block in the th n row and th m column of the th k frame and  

  Fig.I.23: Centroid of gradient orientations fingerprint computation

  In [IND 99], Indyk et al. exploit the temporal dimension of the videos and propose a fingerprinting method based on shot durations i.e. the fingerprint consists of the timing patterns of when shots change in videos. As illustrated in Fig.I.24, a shot transition algorithm [GAR 98] is run on a video v and its timing sequences

]

Fig.I. 24 :

 24 Fig.I.24: Basic principle of timing segments extraction

  The study in[JIA 11] exploits the audio and video components of a video sequence and proposes the use of several features: a local visual feature -the Dense Color SIFT [LOW 04], a global visual featurethe DCT and an audio feature -the WASP. The architecture of their system is presented in Fig.I.25. In the pre-processing part, the query and reference audio and video components are split: the video is uniformly sampled, and the audio content is divided in audio frames. Additional blocks for picture in picture and flipping distortions are also included. The multimodal features used as fingerprints are: a local visual feature of Dense Color SIFT [LOW 04], a global visual feature based on the DCT and an audio feature, WASP [CHE 08].

Fig.I. 25 :

 25 Fig.I.25: Video copy detection approach proposed in [JIA 11]

  Fig.I.25: Keyframe retrieval using the inverted index of DCSIFT visual words and spatial information in [JIA 11]

Fig.II. 2 .

 2 Fig.II.2. Offline pre-processing module

  Fig.II.3. The bag of words framework

( 6 )Fig. II. 4 :

 64 Fig. II.4: Examples of local features, [SZE 10]

  the SIFT detector [LOW 99], the Harris detector, [HAR 84] and the SUSAN detector [SMI 97] detect corners as local features, robust to translation, rotation and stable under varying lighting conditions;  the Harris-Laplace detector yields scale and rotation invariant regions, and the Harris-Affine detector yields affine invariant regions as showed in [MIK 04];  the Hessian-Laplace and Hessian-Affine detectors identify scale invariant and respectively affine invariant blobs (ellipsoid regions) as local features in [MIK 04]; the intensity based detector in[TUY 00], [TUY 04] leads to affine covariant regions as local features;  the MSER (Maximally Stable Extremal Regions) detector proposed in [MAT 02] identifies affine covariant (photometrically and geometrically) regions. Note that the local features identified with the help of detectors have been referred in the state of the art, both as invariant or covariant. On the one hand, the local features are detected invariant to the image distortions and on the other hand, the local features covariantly change with the image distortions (i.e. with the 2D affine image transform which models the distortions). Taking into account the requirements set for the TrackART video fingerprinting method, the local features that qualify the best are the affine covariant regions. They can cope with the geometric and photometric deformation of images. Typically, such regions have an elliptical shape while other approaches such as the DoG (Difference of Gaussians) [LOW 99] use fixed shape circular support regions. The advantage of elliptical shaped regions over circular ones is illustrated in Fig.II.5.

Fig.II. 5

 5 Fig.II.5 Limitation of circular support regions under large viewpoint changes [MIK 05a]: (a) First viewpoint. (b)-(c) second viewpoint. The circular region in (b) does not cover the same object surface patch as the circular region in (a). What is needed is a deformation of the circular region in (b) by an anisotropic scaling to the ellipse shown in (c). Note that regions in (a) and (c) cover approximately the same surface patch on the book. (d)-(f) close-ups of (a)-(c).

  where the local image derivates are computed with Gaussian kernels of local derivation scale .is second order partial derivate in the direction and is the mixed partial second order derivative in the and directions. The derivatives are computed at the current integration scale and are thus the derivatives of an image smoothed by a Gaussian kernel .

2 )

 2 The components of the Hessian matrix are illustrated in Fig.II.6.

Fig.II. 6

 6 Fig.II.6 Illustration of components of the Hessian matrix and Hessian determinant [TUY 08]

Fig.II. 7 .

 7 The autocorrelation matrix describes the gradient distribution in a local neighborhood of a point a . The eigenvalues of the autocorrelation matrix represent the principal signal changes in two orthogonal directions in a neighborhood of the point a at the scale I  . The matrix must be adapted to scale changes to make it independent of the image'

Fig.II. 7

 7 Fig.II.7 Obtaining the affine shape of a region through the iterative algorithm in [LIN 97]

Fig.II. 8 .

 8 Fig.II.8.Examples of Hessian-Affine regions (only 10% of the regions are illustrated)

  Fig.II.9 SIFT descriptor illustration [LOW 04]. Image gradients within a patch (left) are accumulated into a coarse 4 × 4 spatial grid (right). In this example we show only a 2 × 2 grid. A histogram of gradient orientations is formed in each grid cell. 8 orientation bins are used in each grid cell giving a descriptor with the dimension 128 = 4 × 4 × 8)

  Fig.II.10.The image patch on from which the SIFT descriptor is computed

Fig.II. 11

 11 Fig.II.11 Inverted index

  Fig.II.12. Run-time phase of the Bag of Words framework

s

  sparse then the dot product can be computed very quickly by only considering terms which are non-zero in both q v and d v . Computing the ranking for all images in the dataset where, is then the similarity of the i th document to the query.

Fig.II. 14 :

 14 Fig.II.14: The relative number of Chi-square tests on concordance with the Gaussian law which are not passed ( 360  R coefficients, 35000  L frames, and 250  D frames)

  .12), k f and k t designate the 2D-DWT coefficients of the query and the reference frames respectively, in a frequency sub-band k, k k t f , are the mean values of the 2D-DWT coefficients in the considered frequency sub-band, while standard deviations, respectively. N designates the number of 2D-DWT coefficients in every frequency sub-band k. is each of the frequency sub-bands: LL, LH, HL, HH yield by the wavelet transform.

H 1 H

 1 N and  are the same as above. As illustrated in Fig.II.17, if α-point value of the above-mentioned Student law), then the 0 hypothesis is accepted, i.e. the 2D-DWT coefficients in a considered frequency sub-band are not correlated. If , hypothesis is accepted, i.e. the 2D-DWT coefficients in a particular frequency sub-band are correlated.In the experiments presented in this thesis, a significance level of

Fig.II. 17

 17 Fig.II.17 Student probability density function (the illustration corresponds to 25 degrees of freedom)

  Fig.II.18 Synchronization algorithm first stage

  second stage of the algorithm starts: the window is enlarged, by doubling its size L 2 , and a new browsing is done as illustrated in Fig.II.19. If a match occurs, the reference and the query sampling rates are set as before, whereas if no match occurs after iterating the procedure 10  X times, both sampling rates are lowered in order to try to resynchronize in the neighborhood; the query sampling rate is set to 10 ' T and the reference sampling rate to in   ' T .

Fig

  Fig.II.19 Synchronization algorithm second stage

  Fig.II.20). The coefficient matrix in Fig.II.20.a illustrates the fingerprint of a sampled frame, while the fingerprint of an entire reference video sequence is presented in Fig.II.20.b and it is called the rank matrix.

  Fig.II.20: (a) Coefficients matrix for a frame, (b) Rank matrix of DWT coefficients

  , are the mean values of the 2D-DWT coefficients on the considered rank, while k t k f   , are the related standard deviations, respectively. N designates the number of 2D-DWT coefficients in every rank k, i.e. the number of selected frames in each video sequence.

  The value of the T threshold is statistically determined according to the Rho test on correlation [WAL 02]. This test is individually applied to each of the R = 360 ranks under investigation; the null/alternative hypotheses are:

  Fig.II.21: offline phase: pre-processing and offline localization and online phase: pre-processing, online localization, and fingerprint. Consequently, the TrackART Full Fingerprint video fingerprinting method outputs results based on the fingerprint block. The decision in this block is based on the Rho test on correlation between full fingerprints of the query and reference video sequences.

Fig.II. 21

 21 Fig.II.21 TrackART Full Fingerprint functional schema

Fig.II. 22

 22 Fig.II.22 TrackART Reduced Fingerprint functional schema

  Fig.III.1 Frames from the HD3D-IIO video corpus

Fig.III. 4

 4 Fig.III.4 The probabilities off false alarm and miss detection for TrackART Full Fingerprint in the video retrieval use depending on the distortions

  Fig.III.6 graphically illustrates the average values of the probability of false alarm (the diamonds in blue) and of the probability of miss detection (the squares in red) depending on the particular attack.

FromFig.III. 8

 8 Fig.III.7 Frames from camcorder recorded video sequences

1  2 

 12 163  total number of reference keyframes W orig  the original width for a frame (content dependent) H orig  the original height for a frame (content dependent) L = 16  the number of iterations employed by the shape adaptation [LIN 97] algorithm to estimate the hessian-affine regions S = 3  the size of the scale search (the number of scales investigated) in the shape adaptation algorithm in [LIN 97] M  the number of potential interest point detected by the Hessian-Affine detector J = 8  number of orientations for the SIFT descriptor G = 4  the size of orientation histogram of the SIFT descriptor T =38 466 280  10% of the total numbers of SIFT descriptors computed from all the reference keyrames K=250 000  the total number of visual words of the vocabulary P the number of interest point detected in a keyframe (content dependent); typical values can be between 0 and a few thousands, depending on the size of the image and the content) P the number of interest point detected in a keyframe (content dependent); typical values can be between 0 and a few thousands, depending on the size of the image and the content) W = 352  the predefined width for the frames before the wavelet computation H = 288  the predefined height for the frames before the wavelet computation B  the number of matching interest points between two reference keyframes (content dependent)

Fig.III. 9

 9 Fig.III.9 Video fingerprinting demonstrator

  Step 2 is illustrated in Fig.III.11.  Step 3: The message box with the name of the videos indicated as matching by the fingerprinting methods pops up. Step 3 is illustrated in Fig.III.12.

Fig.III. 10

 10 Fig.III.10 Illustration of the step 1 of a fingerprinting demonstrator system

Fig.A. 1

 1 Fig.A.1 Illustration of the first 10 best matching reference keyframes for the first query keyframe of: (a) query sequence seqQuery7, (b) query sequence seqQuery27

Figure 1 :

 1 Figure 1: Human versus video fingerprinting

Figure 2 :

 2 Figure 2: (a) Coefficients matrix for a frame, (b) Rank matrix of DWT coefficients

t

  designate the 2D-DWT coefficients of the query and the reference videos on a rank k, values of the 2D-DWT coefficients on the considered rank, standard deviations, respectively. N designates the number of 2D-DWT coefficients in every rank k, i.e. the number of sampled frames in each video sequence. A perfect match (identity) between the query and the reference rank is obtained when normalized correlation is computed between the 2D-DWT coefficients disposed on ranks, i.e. the columns of the rank matrix. Such a strategy is justified by the statistical

the H 1 ,

 1  -point value of the abovementioned Student law), then the 0 H hypothesis is accepted, i.e. the 2D-DWT coefficients on the k rank are not correlated. If hypothesis is accepted, i.e. the 2D-DWT coefficients on the k rank are correlated. In our experiments, we considered a significance level of

  The reference video database contains original video sequences from the HD3D-IIO [40] corpus and computer generated video replicas totalizing 21 hours of video content. It is structured in 1260 video sequences of 1 minute each, 180 original sequences and 1080 replicas. The HD3D-IIO video corpus consists of 180 original video sequences of 1 minute each and totalizes 3 hours of visual content. The HD3D-IIO video content belongs to 7 different movies and combines indoor and outdoor scenes, unstable and arbitrary lighting conditions, still and high motion scenes as illustrated in Figure5.

Figure 5 :

 5 Figure 5: Frames from the HD3D-IIO video corpus

Figure 6 :Table 4 :Figure 10 :

 6410 Figure 6: The replica video sequences

Figure°11:

  Figure°11: Fingerprint computation principle

Figure 12 :

 12 Figure 12: Frame sampling strategy

  the matching of the fingerprints by a normalized correlation coefficient (hence, an) log ( R R O complexity).

  Figure 13 illustrates the computation times for the proposed -156 -two low-frequency sub-bands. The fingerprint matching is carried on by a normalized correlation coefficient and the decision is based on a repeated Rho test on correlation,

Figure 1 :

 1 Figure 1: Human and video fingerprinting

Figure 4 :

 4 Figure 4: Rank matrix of DWT coefficients

  coefficients of the query and the reference videos on a rank k ; values of the DWT coefficients on the considered rank, while deviations, respectively. N designates the number of DWT coefficients in every rank k , i.e. the number of sampled frames in each video sequence.

Figure 5 :

 5 Figure 5: Video retrieval Consequently, the robustness and the uniqueness of the method can be evaluated by computing the probability of false alarm and the probability of missed detection, according to (3) and (4), respectively:

Figure 8 :

 8 Figure 8: Computation time for the proposed video fingerprinting method

  a low complexity.

Table 1

 1

. Camcorder recording robust video fingerprinting: constraints, challenges, state of the art limitations and thesis contributions.

Table I . 2

 I2

	Distortions	Examples
		 encoding, transcoding
		 compression
	Video format	 frame rate changes  bitrate changes
		 D/A and A/D conversions
		 frame dropping, frame addition (e.g. fade-over ), frames substitution
		 color modifications: conversion to grayscale; conversion to sepia
		 color filtering or corrections
		 decrease of color depth
	Frame aspect	 photometric changes: brightness, contrast, saturation  gamma correction
		 histogram equalization
		 filtering: linear (Gaussian, sharpening), non-linear (median filter)
		 noise addition
		 affine transformations
		 geometric modifications:
		o uniform or non-uniform scaling, rotations
		o reflection
		o aspect ratio changes
		o dilations
		o contractions
		o shear
	Frame content	 similarity transforms (spiral similarity)
		 translations
		 cropping
		 letterbox removal
		 row or columns removal
		 insertion: text, caption, pattern, letter-box insertion
		 picture in picture
		 shifting
		 StirMark
	Mixed	 combinations of all the above modifications

: Types of computer or camcorder generated video modification

  /replacement) and synchronous mobile applications (smartphone two screen interaction with video content immersive social networking applications, 2nd screen applications, direct check-in, program guide correlation with rich meta-data).

	Zeitera offers cloud services for smartTV (allows SmartTV apps to interact with TV content, interactive
	advertising	applications,	targeted	ads,	coupon	capabilities	commercial
	monitoring/localization
	[CIV 12] provides television (Teletrax Television Monitoring) and Internet (Teletrax Internet
	Monitoring) multimedia monitoring solutions which and are based on a combination of watermarking
	and fingerprinting technologies. Teletrax Television Monitoring enables clients such as entertainment
	studios, news and sport organizations, TV syndicators, and advertisers to determine when, where and
	how their video content is being used around the world (e.g. confirmation and prove of airing
	content). Civolution is currently monitoring over 1,500 television channels in more than 50 countries.
	Teletrax Internet Monitoring identifies controls and monetizes content as it travels around the
	Internet (peer-to-peer file sharing networks, video sharing and social media websites, live streaming
	sites, usenet newsgroups, chat rooms, forums and blogs).
	With clients such as 20 th Century Fox Studio, Disney NBC Universal, RTL Group, Canal Plus, Viacom,
	DailyMotion, Facebook and with more than 12 million music, movies and television fingerprints in
	their Global Rights Registry™ database, Audible Magic [AUD 12b] proposes a broad range of solutions
	based on fingerprinting. From broadcasting monitoring services for music and advertising content to
	recognition technology for cloud service operators, from social TV services (e.g. interactive
	advertising, social engagement) to audience measurement and from copyright compliance to HEOA
	compliance (i.e. Higher Education Opportunity Act is a law passed by the American Congress on
	August 14, 2008, one of the policies of the Act requires colleges and universities to mitigate the use of
	P2P networks to illegally upload or download copyrighted materials across campus networks).
	IPharro, a Fraunhoher Institut spinoff ,proposes iPharro MediaSeeker Core Platform a solution for
	multimedia search applications, archive versioning, content future-proofing, media redundancy
	prevention, broadcast monitoring.

  YUV histograms of the DC sequence of MPEG videos [NAP 00], [HAM 07]  YCbCr histogram of a group of frames, [SAR 08]  color moment representation, [GAU 01]  RGB, HSV histogram of frames, [HAM 01]  the principal component of the color histograms of keyframes, [SAN 99]

	Types of fingerprints Spatial Color  Multi-modal Granularity Blocks, regions of frames, frames, keyframes  visual attention regions, [SU 09] Fingerprint examples  ordinal ranking of average gray level of frame blocks, [HAM 02], [KIM 09]  quantized block motion vectors of frames, [HAM 02]  invariant moments of frames edge representation, [HU 62]  centroid of gradient orientations, [LEE 08]  dominant edge orientation, [HAM 01] Points of interest  signal description of motion of interest points (corner features, Harris points), across videos, [LAW 06], [LAW 07], [JOL 05]  scale-space features (e.g. SIFT), [SAR 08]  descriptors of interest points, [MAS 06] Histogram based  SIFT, GIST and color correlogram features for keyframes, [HIL 10]  global visual feature (DCT), local visual feature (SIFT, SURF), audio feature (WASF, modified MPEG-7 descriptor ASF), [GAO 10] (Video and Audio approaches Combined Combined methods  visual feature: center-symmetric local binary
	features)		Group of
			frames
	Mono-		Down-
	modal methods (Video	Temporal	sampled frames
	content		Keyframes
	features)
				 pixel differences between consecutive frames,
			Every frame	[HAM 01]
				 shot duration sequence, [IND 99]
			Re-sampled
			video
		2D/3D
		Transform
			Frame
			transform

 differential block luminance features between consecutive frames, [OOS 02]  temporal ordinal measure (ordering of intensity blocks in successive frames depending on their average intensity), [CHE 08], [HUA 04], [KIM 05], [HAM 01]  ordinal histogram over the frames of the entire video, [SAR 08], [YUA 04] GOP  quantized compact Fourier-Mellin transform coefficients of keyframes, [SAR 08]  subspace embedding using the singular value decomposition [RAD 08]  the signs of DCT coefficients of keyframes, [ARN 09]  the averages of DC coefficients blocks of I frames [YAN 08]  3D DCT coefficients of sub-sampled keyframes, [COS 06]  DCT coefficients of the radial projection vector of the keyframes pixels, [ROO 05]  2D wavelet transform, [GAR 11a], [GAR 11b], [GAR 12], [DUT

10] pattern (CS-LBP), hamming embedding; audio feature: filter banks, [JEG 10], [AYA 11]  coarsely quantized area matching -visual feature, divide and locate -audio feature, [FOU 11], [MUK 11]  cascade of multimodal features (Dense Color SIFT, Bag of Words, DCT, WASF) and temporal pyramid matching, [JIA 11] Table I.3: Types of video fingerprints

Table I .

 I 6 offers a comparative view of the academic state of the art for video fingerprinting methods detailed in Sections I.5.2.4 a -f. Note that the video fingerprinting method presented in Section I.5.2.4.g has not been included in the critical review in TableI.6 due to the fact that it has a multi-modal approach and therefore does not fit the comparison.

	Conclusions			 Robustness to: geometric modifications: cropping, resizing,		Conclusions shifting, and encrusting, image translation and to affine illumination changes	 Robustness to: blurring, white Gaussian noise addition,  A basic localization is available but its computational	brightness increase/decrease, MPEG-4 compression, lossy complexity is not assesed	channel, fade-over, time clipping, frame rotation (up to 3°),	frame dropping, frame rate changes   No scalable localization procedure Robustness to: non geometric distortions: lossy compression, global change in color, brightness, gamma,	 Robustness to: resolution reduction to CIF, QCIF format, Gaussian blur, additive noise and combinations of the above; frame rate changes, frame dropping up to 70% of logo overlay (by 5%-30%), frame-rate changes conversion frames lost, robust to rotations up to 1° and cropping to gray which retains 80% of the central portion of the frame  No scalable localization procedure	 No localization procedure	 Robustness to: MPEG compression, median filtering,  histogram equalization; not robust to scaling or shifting Robustness to: translations in time and jittered video sequences operations   No localization procedure Limited applicability for news programs as they have predefined formats which leads to similar timing	sequences.	 No localization procedure
	Evaluation metrics and	performances	 The recall = 0.82 for a	precision = 0.95	Evaluation metrics and  performances Computational time= 27 seconds for a query of 15 mins to be	 Ratio of correct detections to searched in a 3 hours reference database total tests between 83% and	100%, when the P fa = P md				 Probability of false The probability of missed	alarm = probability of missed detection = 0.0246	detection = 0.086	 Bit error rate between binary	fingerprints 2.9% and 30%	Processing time per query: between	10 seconds and 25 minutes
	Corpus	Reference database: 3 hours of TV	content stored as MPEG-1, 25fps, at a	resolution 352 x 288	Corpus Queries: 69 replica versions of the	Reference database: 244 video clip reference video sequences with	database, with lengths between 12-lengths between 1 second -30	300 seconds minutes	Queries: 61 sequences of 14 seconds Reference database:	of video 1) 300 movies totalizing 590 hours (for	testing the uniqueness)	Reference database: 100 hours 2) 50 videos totalizing 100 hours (for	consisting of video clips from the testing the robustness)	Internet, TV, broadcasting, DVD Queries: replica version of 10 seconds Queries: N/A video sequences selected from the	Reference database: 10 seconds reference sequences 2) Reference database: 2000 MPEG clips video clips from movies and television from Internet with lengths between 2-broadcasts, at a resolution 480 x 720 5 minutes and 5 movie trailers Queries: the replica versions of	reference video sequences Queries: a selection of a few	sequences from the reference	database and their frame-rate was	changes
	Method			Interest	Method points behavior		[LAW 07]	3D-DCT	[COS 06]				CGO	VAR [LEE 08]	[SU 09]	Differential	block	luminance Shot	[OOS 02] duration	[IND 99]
																		-44 -

Table I.6: A comparative view on the performances of the state of the art video fingerprinting systems Table I.6 (continued): A comparative view on the performances of the state of the art video fingerprinting systems

  L'empreinte numérique per-se est représentée par un ensemble de coefficients 2D-DWT obtenu à partir de trames échantillonnées de la séquence vidéo. Une analyse statistique approfondie sur les coefficients 2D-DWT a démontrée non seulement la stationnarité de ces coefficients, mais aussi, la stationnarité de leurs modifications sous des distorsions simulées par l'ordinateur. Ces comportements mathématiques assurent la propriété d'unicité et limite les occurrences de fausses alarmes (c'est-à-dire les empreintes extraites de contenu vidéo différente doit être différent).

	( O	n	log	) n	.

L'appariement des empreintes numériques est réalisé avec un test Rho sur la corrélation, qui permet la détection des copies, assure la propriété de robustesse et limite les occurrences de pertes (c'est-a-dire les empreintes numériques extraites de la séquence vidéo originale et des ses répliques doivent être similaires dans le sens de la métrique de similarité considéré).

Afin de rendre la méthode efficace dans le cas de bases de données à grande échelle, un algorithme de localisation a été proposé. Par conséquent, la séquence copie n'est pas apparie avec toutes les séquences video de la basse de donne, mais seulement avec quelques candidates déterminées sur la représentation sac des mots visuels (concept introduit par Sivic et Zisserman en 2003) des images clés vidéo. Un mécanisme de synchronisation supplémentaire, capable de répondre aux fortes distorsions qui apparait dans les cas d'usage difficiles comme celui d'enregistrement du caméscope dans le cinéma a également été conçu.

La scalabilité de la méthode est assurée par les procédures de localisation et synchronisation et par leur basse complexité qui est maintenue sous la limite

  local feature is an image pattern which differs from its immediate neighborhood, [TUY 08]. It is usually associated with a change of an image property (e.g. intensity, color and texture) or several properties simultaneously; a few examples are illustrated in Fig II.4. To identify local features in images, the underlying intensity patterns in a local neighborhood of pixels needs to be analyzed by using a local feature detector. Local features can be interest points, regions (blobs) or edge segments. A set of local features can be used as a robust image representation that allows recognizing objects or scenes without the need for segmentation, [TUY 08].Consequently, local features have gained a lot of momentum in computer vision in the last fifteen years because they are powerful tools in applications like image retrieval from large databases [SCH 97], object retrieval in video [SIV 03], [SIV 04a], visual data mining [SIV 04b], texture recognition [LAZ 03a], [LAZ 03b], shot location [SCH 03], robot localization [SE 02], recognition of object categories [DOR 03]. The relevance of local features has also been demonstrated in the context of object recognition by the human visual system [BIE 98]. Their experiments shown that removing the corners from images impedes human recognition, while removing most of the straight edge does not.

  The investigated descriptors are: SIFT [LOW 04], PCA-SIFT [KE 04], gradient location and orientation histogram (GLOH) [MIK 05b], shape context [BEL 02], spin images [LAZ 03a], steerable filters [FRE 91], moment invariant [GOO 96], and cross-correlation of sampled pixel values which are all computed on Hessian-Affine regions.

  The study in [PHI 07] introduced the Approximate k-Means (AKM) which is a scalable version of the k-means algorithm.A typical k-means algorithm is a method which aims at partitioning a set of n observations,

	x 1	x , 2	,...,	x	n	, into k clusters,	S		 S 1	,	S	2	,...,	S	k		in which each observation belongs to the cluster
												k
	with the nearest mean, i.e.	arg	min	 	x	j		i  , where 2
								s			i	S   x 1		i
														j	i

  [PHI 10] tested vocabulary sized to 2 million visual words, while Nister and Stewenius [NIS 06] reached 16 million points for a vocabulary size. The conclusion of the studies was that in general the large vocabularies yield better results and that an increase in the number of clusters achieves a better improvement than taking more data in the clustering process, i.e. more descriptors.TableII.1 illustrates the choice made in [PHI 07] for the size of the vocabulary according to the number of descriptors. The obtained mean Average Precision (mAP) in the case of the typical kmeans algorithm and in the case of the approximate k-means (AKM) is also mentioned for the different size vocabularies.

	Clustering parameters	mAP
	# of desc	Voc. size	k-means	AKM
	800K	10K	0.355	0.358
	1M	20K	0.385	0.385
	5M	50K	0.464	0.453
	16.7M	1M		0.618

Table II.1. Clustering parameters and their performances as shown in [PHI 07]

  Concerning the practical implementation of the AKM technique, the specifications of the authors [PHI 10] were used: 30 iterations, 8 trees and 1024 distance computations, for the clustering 784 checks per point and 1500 for the final assignment. The AKM is easily parallelizable and its distributed memory computed can be achieved with the open source MPI library [MPI 12]. A publicly available implementation of AKM is available from [PHI 12].

  is determined by examining a fixed number of leaf nodes, at which point the search is terminated and the best candidates returned.

	Local feature detection	Local feature description	Clustering representation -Bag of words	TF-IDF weighting	Inverted Index
			-76 -

approximation

  is the number of documents containing term i , and N is the number of documents in the whole database. The weighting is a product of two terms: the word frequency,

	Assuming the computed visual vocabulary has K words, then each image (i.e. each keyframe) is
	represented by a vector:
					v	d		t ( 1	,...,	t	i	,...,	t	K	)	T	(II.6)
	of weighted word frequencies with components:
						t	i		id n	log	N	(II.7)
										n			N
											d			i
	where	id n is the number of occurrences of word i in document d ,	d n is the total number of
	words in the document d ,
	tf 	n	id	and the inverse document frequency,	tidf log 	N
		n											N
			d											i
			Local feature detection	Local feature description							Clustering representation -Bag of words	TF-IDF weighting	Inverted Index

i N

  versions of the RANSAC algorithm were proposed in the state of the art for geometric verification: the PROSAC (Progressive Sample Consensus), [CHU 05] method weights correspondences by employing an external measure of confidence, which is used as a priority for guiding the search towards good solutions; the GroupSAC [NI 09] partitions points into groups based on similarity information; for their large scale object retrieval, Philbin et al. [PHI 07] don't use RANSAC because the estimation of a full 3-D fundamental matrix or 2-D projective homography between two images is too general and runs very slowly. They use LO-RANSAC (Locally Optimized-RANSAC) [CHU 04] a variant of RANSAC which consists in (1) -generating hypotheses of an approximate model and then (2) -iteratively re-evaluating promising hypotheses using the full transformation. The approximate model is built iteratively from single pairs of correspondences verified through a class of transformations of the affine-invariant regions corresponding to the matched points.

  The value of the T threshold is statistically determined according to the Rho test on correlation [WAL 02]. This test is individually applied to each frequency band under investigation; the null/alternative hypotheses are:

	  	1 H H 0	fficients : the coe ficients : the coef	in in	a a	sub sub	--	band band	lated are corre orrelated are not c

  hypothesis is accepted, i.e. the 2D-DWT coefficients on the k rank are not correlated. If

	If	t test 	z		/	2	(where	z		/	2	is the α-point value of the above-mentioned Student law), then the
	the	1										t test 	z		/	2

0 H

Table II

 II

	Thesis contributions	Fingerprint computation independent of	random, time-variant conditions:	 stationary/ergodic fingerprints	 2D-wavelet coefficients	Mathematical decision rule in	fingerprint matching:	 method based on a repeated statistical test	 statistical error control	Scalable method	 automatic retrieval procedure	 O(n) complexity for fingerprint computation	 O(nlog(n)) complexity for fingerprint	matching with respect to the fingerprint size
	Current limitation PART III: TRACKART -Heuristic procedures Heuristic procedures No related method reported in the state-of-the-art Very few full scalable mono-modal methods reported in the state-of-the-art EXPERIMENTAL RESULTS
	Constraints Challenge	Uniqueness Accurate representation	of the video content			Robustness Mathematical ground		In-theater live camcorder	recording	Search efficiency Scalability
						-109 -

.2. Camcorder recording robust video fingerprinting: constraints, challenges, state of the art limitations and thesis contributions.

  2.

	Distortion		Precision	Recall	P fa	P md
	Brightness decrease	1	1	0	0
	Brightness increase	0.983	0.983	0	0.016
	Contrast decrease		0.988	0.988	0	0.011
	Gaussian filtering		0.994	0.994	0	0.005
	Grayscale conversion	0.988	0.988	0	0.011
	Rotation 2°		0.866	0.866	0	0.133
	Sharpening		0.988	0.988	0	0.011
	StirMark		0.988	0.9888	0	0.011
	Average		0.975	0.975	0	0.025
	Table III.2 Average results for precision and recall rates and for the probabilities of false alarm and
	miss detection for TrackART Full Fingerprint under the video retrieval use case for different
			distortions
	0.99
	0.97
	0.95
	0.93
	0.91
	0.89
	0.87
	0.85
	Fig.III.3 Precision and recall rates for TrackART Full Fingerprint in the video retrieval use case Original version depending on the distortions
	Brightness decrease	Brightness increase	Contrast decrease	Gaussian filtering
	Grayscale conversion		Rotation 2°	Sharpening	StirMark
			Fig.III.2: The replica video sequences
			-114 -

Table III .

 III 3 presents the average values for the precision (Prec) and recall (Rec) rates, as well as for the probabilities of false alarm (P fa ) and miss detection (P md ) for the considered distortions. The average values are obtained by averaging the precision/recall/Probability of false alarm/Probability of miss detection obtained individually for each query.

	Distortion	Prec	Rec	P fa	P md
	Brightness decrease	0.983	0.983	0	0.016
	Brightness increase	0.966	0.966	0	0.033
	Contrast decrease	0.972	0.972	0	0.027
	Gaussian filtering	0.972	0.9722	0	0.022
	Grayscale conversion	0.972	0.972	0	0.027
	Rotation 2°	0.461	0.461	0	0.466
	Sharpening	0.966	0.966	0	0.033
	StirMark	0.883	0.883	0	0.094
	Average	0.897	0.897	0	0.090

Table III .

 III

Table III .

 III .4. The gain is computed as: Gain = abs(EvaluationMetric TrackART Full Fingerprint -EvaluationMetric TrackART Reduced Fingerprint ).Specifically, in the case of rotations with 2°, precision and recall are improved with 40%, probability of miss detection decreased with 33%. In the case of the StirMark attack, precision and recall are increased with 10%, while the probability of miss detection is reduced with 9%. 4 Gain obtained in the performances of TrackART Full Fingerprint configuration over the TrackART Reduced Fingerprint configuration in the video retrieval use caseThe gain obtained in results for the TrackART Full Fingerprint can be explained by two facts. Firstly, the correlation between the frames of the query and reference video sequences performed in the Fingerprint block is based on a statistical ground and can provide reliable results. Secondly, the computation of the video fingerprint employed information (i.e. location of the DWT coefficients) from the video frames which is subject to change in distortions like the rotations with 2° or the StirMark attack and therefore is sensitive to this type of distortions. These functional gains are obtained at the expense of the fingerprint length, which is in the TrackART Full Fingerprint 17 times larger than the TrackART Reduced Fingerprint. Hence, assuming the case no malicious distortion occurs (i.e. content in large archives such as INA [INA 12]) the TrackART Reduced Fingerprint is the best solution as it withstands all the mundane signal processing operations like: Gaussian filtering, sharpening, brightness and contrast changes, or conversion to grayscale.

			Gain(%)
	Distortion	Precision Recall	P fa	P md
	Brightness decrease	1.66	1.66	0	1.66
	Brightness increase	1.66	1.66	0	1.66
	Contrast decrease	1.66	1.66	0	1.66
	Gaussian filtering	2.22	2.22	0	1.66
	Grayscale conversion	1.66	1.66	0	1.66
	Rotation 2°	40.55	40.55	0	33.33
	Sharpening	2.22	2.22	0	2.22
	StirMark	10.55	10.55	0	8.33
	Average	7.77	7.77	0	6.52

  .5.

	Distortion	Precision	Recall	P fa	P md
	Live camcorder recording	0.930	0.930	0.000016	0.041
	Table III.5 Average results for the live camcorder recording use-case

Table III .

 III .6. 6 Average results for the live camcorder recording use-caseThe values in TableIII.6 point to results far below the minimal requirements for a practical application such as live camcorder recording.

	Distortion	Precision	Recall	P fa	P md
	Live camcorder recording	0.611	0.611	0	0.333

Table III .

 III [START_REF] Hampapur | Comparison of Sequence Matching Techniques for video copy detection[END_REF] Gain obtained in the performances of Partial TrackART over the Full TrackART methods in the camcorder recording use case Of course, the gain in performances is obtained at the expense of the fingerprint size which is 17 times larger in the case of the TrackART Full Fingerprint configuration. However, TrackART Full Fingerprint is the only solution currently available able to identify live camcorder recorded video content.

				(%)
	Distortion	Precision	Recall	P fa	P md
	Live camcorder recording	31.94	31.94	-0.001	29.16

Table III . 8 :

 III8 Parameters employed in the TrackART video fingerprinting method Under the HD3D2 project, one of the deliverables consisted in the implementation and comparison of the TrackART method with two state of the art competitors, namely the 3D-DCT based fingerprint advanced in the study in [COS 06] the visual attention regions based method advanced in the study in [SU 09].

			Operation	Complexity
		Local feature	Interest point detection algorithm	( W orig O			H	orig	)
		detection	Scale and affine shape estimation	( O	M		(	S		)) L
	Offline		Local descriptor computation	( O  J	G	2	)
	phase		Vocabulary computation	( T O			log	K	)
			BoW keyframe representation		O	(K	)
			TF-IDF weighting		O	(V	)
			Inverted index		O	(V	)
		Local feature	Interest point detection algorithm	orig W ( O			H	orig	)
		detection	Scale and affine shape estimation	( O	M		(	S		)) L
			Local descriptor computation	( O  J	G	2	)
			Keyframe matching		O	(K	)
	Online	Geometrical	Matching between the interest points in two keyframes	1 P O  (	2 P	log	2 P	)
	phase	verification	Geometrical transformation estimation and
			verification		O	(B	)
			Synchronization	( W O 	H	)
			Computation of the DWT	( W O 	H	)
			Sorting of the coefficients	( O	R		log	R	)
			Fingerprint matching	( O	R		log	R	)
	Table III.9 The computational complexity of the algorithms employed in the TrackART video
			fingerprinting method
	III.6	Video fingerprint demonstrator
			-122 -

  D'un point de vue fonctionnel, le système TrackART répond aux enjeux d'aujourd'hui: la propriété d'unicité est assurée par le fait que les empreintes numérique ont été sélectionnés selon un modèle mathématique représentant le contenu visuel (les coefficients d'ondelettes) ; la propriété de robustesse est atteinte par le fait que les modèles mathématiques régissant les empreintes numériques sélectionnées sont robuste à des distorsions du contenu, d'aspect ainsi que de format vidéo ; la propriété de scalabilité pour des bases de données à grande échelle est assurée par le la procédure de localisation de requête et par le fait que tous les algorithmes ont des implémentations rapides. Un tel modèle permet notamment une étude sur la taille minimale de l'empreinte capable d'identifier une séquence vidéo d'une longueur donnée, sous contraintes d'unicité et robustesse pré-imposées.

	La méthode de traçage de contenu vidéo avance a été testée dans deux cas d'usage proposés par
	nos partenaires industriels, notamment (1) -la recherche des séquences vidéo qui comportent des
	distorsions générées par ordinateur et (2) -la recherche des séquences vidéo qui comportent des
	distorsions générées par l'enregistrement en salle de cinéma.

Les perspectives sont liées à la définition d'un modèle théorique pour les systèmes de traçage du contenu. En l'absence d'un tel modèle, les limites théoriques d'un système de traçage de contenu vidéo ne peuvent être ni calculées ni explorées. Pour apporter une solution à ce problème, un modèle basse sur la théorie de l'information est avancé.

Table 1 :

 1 Types of computer or camcording generated video modifications

	Distortions		Examples
			encoding
			transcoding
			bitrate changes
	Video		D/A and A/D conversions
	format		frame dropping
			frame addition
			framerate changes
			frames substitution
		 geometric modifications: scaling, rotations, shifting
		 color modifications: conversion to grayscale, sepia, color filtering
		 illumination changes: brightness, contrast, saturation, gamma correction
	Frame		modifications, histogram equalization
	aspect	 compression
		 filtering: linear (Gaussian, sharpening), non-linear (median filter)
		 noise addition
		 aspect ratio changes
			cropping
	Video		text insertion, caption insertion
	content		letter-box insertion
			affine transformations
	Mixed		combinations of all the above modifications

Table 2 :

 2 Types of video fingerprints

	Types of fingerprints	Granularity	Fingerprint examples

Table 5 :

 5 Average results for the camcording use-case

	Probability of false alarm	0.00009	Precision	0.72
	Probability of missed detection	0.0036	Recall	0.72

Abstract

The present section relates to the experiments. The TrackART video fingerprinting system advanced by the present thesis is evaluated in industrial partnership with professional players in cinematography special effects (Mikros Image) and with the French Cinematography Authority (CST -Commision Supérieure Technique de l'Image et du Son).

Two use cases have been incrementally considered: (1) computer generated replica video retrieval and (2) live camcorder recorded video retrieval. The reference dataset was composed of 14 hours of video content from different movies produced in Ile de France (e.g. Asterix), under the framework of the HD3D-IIO and HD3D2 CapDigital Competitiveness Cluster Projects. The query dataset was organized differently for each use case. For computer generated replica video retrieval, the query dataset consists of 24 hours of replica video content generated obtained by applying eight types of distortions (i.e. brightness increase/decrease, contrast decrease, conversion to grayscale, Gaussian filtering, sharpening, rotations with 2°, stirMark) on 3 hours of original video content from the reference dataset. For the live camcorder recording, the query corpus consisted of 1 hour of live camcorder recorded video content from the reference dataset.

The properties of the TrackART video fingerprinting system were evaluated as following: the robustness property is assessed by two objective evaluation criteria, namely the probability of missed detection (P md ) and the recall rate (Rec); the uniqueness property is assessed by two objective evaluation criteria: the probability of false alarm (P fa ) and the precision rate (Prec); the scalability property is assessed by an in depth complexity evaluation.

The inner 2D-DWT properties with respect to content preserving attacks (such as linear filtering, sharpening, geometric, conversion to grayscale, small rotations, contrast changes, brightness changes, live camcorder recording), ensure the following results: in the first use case the probability of false alarm reached its null ideal value whereas the missed detection was lower than 0.025, precision and recall were higher than 0.97; in the second use case, the probability of false alarm was 0.000016, the probability of missed detection was lower than 0.041, precision and recall were equal to 0.93

Keywords

Computer generated replica video retrieval, brightness increase/decrease, contrast decrease, conversion to grayscale, Gaussian filtering, sharpening, rotations with 2, StirMark, camcorder recorded replica video retrieval, probability of false alarm, probability of missed detection, precision, recall, complexity evaluation.

Resumé

Ce chapitre porte sur la validation expérimentale. TrackART, le système de traçage du contenu vidéo avancé dans cette thèse, est évalué en partenariat avec des professionnels de l'industrie des effets spéciaux (Mikros Image) et avec l'autorité cinématographie française (CST -Commission Technique Supérieure de l'Image et du Son).

Deux cas d'usages ont été examinés: (1) -recherche des séquences vidéo qui comporte des distorsions générée par l'ordinateur et (2) -recherche des séquences vidéo qui comporte des distorsions générée par l'enregistrement en salle de cinéma. La basse de donnes de référence est composée par 14 heures de contenu vidéo obtenu à partir de différents films produits en Ile de France (par exemple Astérix), dans le cadre de projets pôle de compétitivité CapDigital, HD3D-IIO et HD3D2. La basse de donne de requête a été organisée différemment pour chaque cas d'usage. Pour le cas de recherche des séquences vidéo qui comporte des distorsions générée par l'ordinateur, la basse de données de requête est constituée par 24 heures de contenu vidéo obtenu en appliquant huit types de distorsions (augmentation/diminution de la luminosité, diminution du contraste, conversion en niveaux de gris, filtrage Gaussien, le rehaussement, rotation 2°, StirMark) sur 3 heures de contenu vidéo original. Pour le cas d'enregistrement en salle de cinéma, le corpus requête consiste en 1 heure de contenu vidéo, i.e. 1 heure de originale a été enregistré avec un caméscope.

Les propriétés du système TrackART ont été ensuite évaluées: la robustesse est évaluée selon deux critères d'évaluation objectifs, i.e. la probabilité de pertes et le taux de rappel ; l'unicité est également évaluée par deux critères objectives, à savoir la probabilité de fausse alarme et le taux de précision ; la scalabilité est évaluée par la complexité du calcul du chaque block fonctionnelle du système.

Les propriétés intrinsèque des coefficients 2D-DWT en ce qui concerne le distorsions préservant le contenu (tels que le filtrage linéaire, rehaussement, conversion en niveaux de gris, les petits rotations, les changements de contraste et luminosité, l'enregistrement en salle de cinéma), assurent les résultats suivants: dans le premier cas d'usage la probabilité de fausse alarme atteint sa valeur idéale (nulle), la probabilité de détection manquée est inférieure à 0.025, la précision et le rappel sont plus élevé que 0,97 ; dans le deuxième cas d'usage d'autre, la probabilité de fausse alarme est 0.000016, la probabilité de détection manquée était inférieur à 0.041 , la précision et le rappel sont 0.93.

Mots clés

Recherche des séquences vidéo qui comporte des distorsions générée par l'ordinateur, augmentation/diminution de la luminosité, diminution du contraste, conversion en niveaux de gris, filtrage Gaussien, le rehaussement, rotation 2°, StirMark, recherche des séquences vidéo qui comporte des distorsions générée par l'enregistrement en salle de cinéma, la probabilité de fausse alarme, ), la probabilité de détection manquée, la précision, le rappel.

-107 -

III.1 Context

Part III of the current thesis experimentally validates the TrackART method proposed in Part II.

The evaluation of the TrackART method was accomplished under the framework of the HD3D2 project [ HD3 11] and in direct partnership with Mikros Image [ MIK 12] and the CST-Commission Supérieure Technique de l'Image et du Son [ CST 12].

The aim of the HD3D2 project was to develop a platform able to provide film and animation producers with all the tools needed for film making, starting from content production, management and finishing with copyright protection and legal matters.

Mikros Image is a major player in the post production industry (the Oscar in 2010 for short animation movies, La Palme d'Or Cannes 2012), dedicated to high-end visual effects. The CST is an association of professionals from the audiovisual field, in charge of supervising the quality of the production and broadcast of sound and images, whether they are intended for cinema, television or any other medium.

Under this framework, the role of the ARTEMIS department of Institut Telecom; Telecom SudParis was in charge of investigating the state of the art fingerprinting methods and of providing a novel fingerprinting method able to cope with the particularities of the use cases stated by the industrial partners.

Both partners, Mikros Image and the CST proposed a use-case which they found relevant in their business activities. On the one hand, Mikros Image as a post-production company, was interested in having a method able to cope with the distortions induced in video content with the help of the computer. On the other hand, the CST as quality supervisors were interested in researching a fingerprinting method able to address the challenging case of live camcorder recording. To our best knowledge (Section I.5.2), camcording has been addresses by the state of the art video fingerprinting methods only in its computer simulated form and not in its live version.

These two use case have been considered in the present thesis.

III.2 Testing corpus

The reference database for the TrackART method is the HD3D-IIO video corpus which was compiled by the HD3D2 project partners. It consists of 8 video videos Asterix, Chromophobia, Fauteuil d'Orchestre 3, Femme Fatale, Hannibal, Hitman, La Mome and The Last Legion which totalize 14 hours of video content.

The films are divided into chapters as follows: Hitman -7 chapters (denoted as seqRef1, …, seqRef7), Chromophobia -7 chapters (denoted as seqRef8, …, seqRef14), Femme Fatale -6 chapters (denoted as seqRef15, …, seqRef20), The Last Legion -1 chapter (denoted as seqRef21), Fauteuil d'Orchestre -5 chapters (denoted as seqRef22, …, seqRef26), Hannibal -3 chapters (denoted as seqRef27, …, seqRef29), Asterix -1 chapter (denoted as seqRef30), La Mome -1 chapter (denoted as seqRef31).

-108 -

The films in the reference corpus were provided as a collection of images encoded with the tiff format and with HD definition. The resolutions are presented in Table III.1. In order to assess the performances of the TrackART video fingerprinting system, the processing of the HD3D-IIO corpus is detailed for every use case in the sequel.

Film Resolution

Asterix -112 -

The query video corpus consisted of 1440 video sequences chosen from the reference database, i.e. 180 replica video sequences with length of 1 minute for each of the distortions. The replica video sequences were obtained by applying distortions in the video sequences selected from the reference database. The distortions considered are the following: brightness decrease (25%), brightness increase (20%), contrast decrease (25%), linear filtering (Gaussian filter), conversion to grayscale, rotations by 2°, sharpening, and and StirMark attack. The effect of the attack on the video frames is illustrated in Fig.

Note that the distortions applied on the query video sequences include only frame aspect and frame content distortions and no video format distortions were induced at this stage of experimental work.

Having this experimental set-up, the TrackART video fingerprinting method will be tested under the video retrieval use case in two configurations denoted as TrackArt Full Fingerprint (cf. [START_REF] Radhakrishnan | Robust Video Fingerprints Based on Subspace Embedding[END_REF]. The difference between the two configurations of the TrackART method is the functional block of the method which provides the results of the system.

In the TrackART Full Fingerprint configuration, the result is given by the fingerprint block which computes the number of matching frames (according to the Rho test on correlation) between the query and the reference video sequences. Consequently the amount of matching frames is considered as the criterion for the video sequences matching. A query is retrieved if E of its frames are correlated with the frames of a reference sequence. The E threshold needs to be set by taking into account the sampling rate performed in the synchronization step of the Fingerprint block (Section II. 3.3.4) of 1 frame per second (a frame every 25 frames) and the length of the query sequence. Considering the size of the query sequences was of 1 minute (25 x 60 = 1500 frames) each, and that general sampling rate is 1 frame per second, the minimum amount of matching frames was set at E= 20 i.e. a third of the total sampled frames. Consequently, if equal or more than E= 20 matching frames are encountered, the query sequence has been identified in the reference database.

In the TrackART Reduced Fingerprint configuration, the decision criterion is based on the Rho statistical test between the reduced fingerprints of the query and reference video sequences.

III.3.1 TrackART Full Fingerprint evaluation

Analogous to the the evaluation of TrackART Full Fingerprint for the evaluation of the TrackART Reduced Fingerprint configuration, the average precision (Prec) and recall (Rec) rates and as well as the probabilities of false alarm (P fa ) and missed detection (P md ) are investigated.

In Table III. As it can be observed, the results obtained are excellent, with precision, recall rates and probabilities of false alarm and missed detection close to their ideal values.

PART IV: FINAL CONCLUSIONS AND

PERSPECTIVES

Abstract

From the functional point of view, TrackART answers the main challenges for a video fingerprinting system: the uniqueness property of fingerprints is ensured by the fact that the video features are selected according to a mathematical model representing the visual content (the wavelet coefficients); the robustness property of fingerprints is achieved by the fact that the mathematical models governing the selected features are robust to frame content and aspect distortions as well as video format distortions; the scalability to large scale databases is ensured by the fact that a query localization procedure is employed and by the fact that the all the algorithms have fast implementations.

The advanced video fingerprinting method has been tested in two practical use cases proposed by the industrial partners, namely the retrieval of video sequences from database under computer generated distortions and the live camcorder recording.

While the present thesis offers a solution to the nowadays limitations in deploying video fingerprinting in two real-life applications, the perspectives are connected to defining a theoretical model for video fingerprinting. As no such model is currently available in the literature, the video fingerprinting theoretical limits can neither be computed nor explored. To offer a solution to this problem, an information theory based model is advanced. Such a model allows the investigation of the minimal fingerprint size able to identify a video sequence of a given length under prescribed robustness/uniqueness constraints, can be established.

-132 -

The advanced video fingerprinting method has been tested in two practical use cases proposed by the industrial partners, namely the retrieval of video sequences from database under computer generated distortions and the live camcorder recording.

The a priori properties described above are validated by the experimental results: in the video retrieval use case, the probability of false alarm reached is null i whereas the missed detection was lower than 0.025, precision and recall were higher than 0.97; in the live camcorder recording use case, the probability of false alarm was 0.000016, the probability of missed detection was lower than 0.041, precision and recall were equal to 0.93.

To conclude with, the present thesis offers a solution to the nowadays limitations in deploying fingerprinting in two real-life applications.

Perspectives

The perspectives of the present thesis are connected to the fingerprinting theoretical model.

Actually, no such model is currently available in the literature and hence the fingerprinting theoretical limits cannot be explored. In order to establish the minimal fingerprint size able to identify a video sequence of a given length under prescribed robustness/uniqueness constraints, the model presented in the

Appendix

A.1. Online localization illustrations

In order to have a visual explanation for the Online localization block of the TrackART method (detailed in Section II.3), some situations are illustrated below.

To recap, the function online localization block is to position the query starting point in the reference database. As explained in Section II.3 the query is represented as a set of successive keyframes. In our experiments, the maximum number of tested query keyframes in order to obtain a positive answer from the fingerprinting block is 5.

Note that the illustrations are made only for the use case of live camcorder recording because the use case of computer generated distortions (i.e. Gaussian filtering, sharpening, contrast and brightness changes, conversion to grayscale) are practically included within the distortions induced by live camcorder recording (i.e. abrupt geometric transformations with brightness, color and contrast variations).

-138 -

A.2. Publications

The incremental results obtained during the thesis were included in one journal papers and four conference proceddings: -139 -

A.3. Selection of publications

A.3.1. Journal paper

Cinematography sequences tracking by means of fingerprinting techniques

ABSTRACT

By advancing a new robust fingerprinting method, the present paper takes the challenge of designing an enabler for the use of Internet as a distribution tool in cinematography. Video fingerprints are short features extracted from a video sequence in order to uniquely identify that visual content and its replicas. This paper develops a new 2D-DWT-based robust video fingerprinting method able to address two use cases related to the cinematography industry, namely the retrieval of video content from a database and the tracking of in-theater camcorder recorded video content. In this respect, a set of largest absolute value wavelet coefficients is considered as the fingerprint and a repeated statistical test is used as the matching procedure. The video dataset consists of two corpora, one for each use case. The first corpus regroups 3 hours of heterogeneous original content (organized under the framework of the HD3D-IIO French national project) and of its attacked versions (a total of 21 hours of video content). The second corpus consists of 3 hours of heterogeneous content (i.e. HD3D-IIO corpus) and of 1 hour of live camcorder recorded video content (a total of 4 hours of video content). The inner 2D-DWT properties with respect to content preserving attacks (such as linear filtering, sharpening, geometric, conversion to grayscale, small rotations, contrast changes, brightness changes, live camcorder recording), ensure the following results: in the first use case the probability of false alarm and missed detection were lower than 0.0005, precision and recall were higher than 0.97; in the second use case, the probability of false alarm was 0.00009, the probability of missed detection was lower than 0.0036, precision and recall were equal to 0.72.

-142 -

On the one hand, an efficient fingerprinting method should ensure a low probability of false alarm (i.e. low probability of retrieving video sequences which are neither the query nor its replicas) and low probability of missed detection (i.e. a low probability of not retrieving replica video sequences of the query). On the other hand, high values for precision (i.e. a high probability of retrieving replica video sequences for a given query out of all the retrieved video sequences) and recall (i.e. a high probability in retrieving all the replica video sequences existing in a database for a given query) should also be obtained. Additional functional properties (database search efficiency, automatic processing, localization of a query in the reference video) can be set, according to the targeted practical application.

The present study is focused on two applicative use cases of relevance for the cinematography industry: database video retrieval and live camcorder recording tracking. The former takes a video sequence (arbitrarily chosen) as a query and searches for its potential replicas in the database. The latter covers the case in which an arbitrarily chosen sequence from the reference database is live camcorder recorded and its original version is searched in the reference database. French cinematography authorities (CST -Commission Supérieure Technique de l'Image et du Son [3]) have set for the fingerprinting methods serving these two cases the following constraints: probabilities of false alarm/missed detection lower than 5% and precision/recall rates higher than 95%. In order to reach these performances, the present research study advances a 2D-DWT (Discrete Wavelet Transform)-based video fingerprinting method. The fingerprint itself consists of highest absolute value 2D-DWT coefficients, computed on video key-frames. As already known in the literature [START_REF] Mitrea | Zero-memory information sources approximating to video watermarking attacks[END_REF], such coefficients feature very fine statistical behaviors; hence, repeated statistical tests can be considered in the fingerprint matching, thus granting mathematical relevance to the experimental results. The present paper is structured as follows. Section 2 presents the state of the art for video fingerprinting. Section 3 advances an original method for video fingerprinting. Section 4 experimentally validates the proposed method, according to the two above mentioned use cases. Conclusions are drawn and perspectives are opened in Section 5.

STATE OF THE ART

Despite its young age, video fingerprinting can serve a large variety of applications: detection of copyright infringement, detection of known illegal content, control and management of video content, broadcast and advertisement monitoring, audience measurement, business intelligence, … . Consequently, the research studies cover a large area of methodological tools from pixel difference of consecutive frames or RGB histograms to transform domain based fingerprinting approaches.

-145 - The distance-based group of methods has the advantage of allowing a decision based on an experimentally determined threshold. While they are easier to use, they don't permit in the majority of cases a decision based on a mathematical ground. Therefore the alternative is the probability-based similarity measures which can grant a statistical rule for decision.

As it can be seen, although in the last decade the applicability field of video fingerprinting grew steadily and despite the wide range of methods that have been investigated, at least two challenges are still to be taken. First, the state of the art methods presented in Tables 2 and3 are generally tested on TV content data sets and don't take into account the particularities of the cinema content. These particularities are twofold and refer to the types of visual content and to the types of distortions that need to be addressed by the fingerprinting method. For the former particularity, the cinema visual content has HD quality and presents a high dynamics of the visual content, outdoor/indoor scenes and arbitrarily changing lighting conditions. For the latter particularity, the category of distortions introduced by live camcording is one of the most complexes because it includes and combines abrupt geometric transformations with brightness, color and contrast variations. Secondly, the trade-off among the probability of false alarm, the probability of missed detection, the precision, the recall and the computational time required by such a use case has not yet been investigated. Therefore the objective of this paper is to advance a DWTbased video fingerprinting method using a mathematical decision rule for the detection of replicas, capable of addressing not only the use case of video retrieval but also the complex use case of camcording in movie theatres.

-149 -

EXPERIMENTAL RESULTS

The proposed 2D-DWT-based fingerprinting technique was tested in two applicative use cases: (1)video identification and retrieval in a database and (2)live camcorder recording.

In the experiments, the probability of false alarm (P fa ), the probability of missed detection (P md ), the precision (Prec) and the recall (Rec) rates were computed for every query and average values were obtained by successively considering all the sequences in the database and by averaging the corresponding results.

Video retrieval use-case

A video identification and retrieval use case consists of identifying a video sequence (further referred as query sequence) in a database of video sequences, called the reference video database, as illustrated in Figure 4. The computation of the fingerprint for the query video is done online, whereas the computation for the reference videos is done offline. The identification process is based on the video fingerprints and on the matching between them.

When consulting the reference database with a query video sequence, all its replicas should be retrieved. Irrelevant video sequences (not connected to the query) should be ignored. The overall results, point to a very good retrieval accuracy, with average false alarm probability lower than 0.0005 and average missed detection probability lower than 0.0002. The results are reinforced by the average precision higher than 0.98 and average recall higher than 0.97. Figure 7.a illustrates the average values (obtained by averaging the results for all the considered queries) of the probability of false alarm (the diamonds in blue) and of the probability of missed detection (the squares in red) depending on the particular attack.

Similarly, Figure 7 The quantitative results in Figure 7 show that the most disturbing effects are induced by the sharpening and by the brightness increase attacks. This can be explained by the fact that these two types of attacks follow the stationarity investigation with less accuracy than the other four types [START_REF] Mitrea | Zero-memory information sources approximating to video watermarking attacks[END_REF]. Consequently a matching rule devoted to non-stationary information sources is expected to improve the results.

Camcording use-case

The camcording use case consists of tracking an in-theatre camcorder recorded video sequence in a database of original video sequences, as illustrated in Figure 8. In such a case, the attacked video sequences are obtained by capturing with a non-professional camcorder the original sequence which is displayed on a screen. A simplified geometrical representation of the recording process performed in the CST cinema theatre is given in Figure 10.a, the theatre being viewed from the top side view [START_REF] Chupeau | In-theater piracy: Finding where the pirate was[END_REF].

The optical axes of the camcorder and of the projector do not usually intersect with the screen at the same point and are not parallel with each other. The angle Ω measures the rotation of the camcorder around its optical axe.

-155 -fingerprinting method. The task durations were computed using a system with the following configuration: Intel Xeon CPU processor at 2.8 GHz with 3.5 Go of RAM memory, with an operating system working on 32 bits.

Parameter choice

Throughout the presentation of the fingerprinting method, several choices for parameters have been made. This section discusses their practical impact.

The fingerprint was computed in the DWT domain due to its capacity of identifying the overall salient content of images and representing it through edges in the high frequency sub bands. Moreover the Daubechies (9, 7) wavelets were used due to their very fine capacity of approximating the visual content. However, other types of DWT like (2,2) or (4,4) can be used with a very low impact on robustness, while keeping the same uniqueness and reducing the computational time.

For the fingerprint itself, the R = 360 2D-DWT coefficients from every frame were chosen due to their good [START_REF] Mitrea | Zero-memory information sources approximating to video watermarking attacks[END_REF] statistical properties, i.e. due to their stationarity. However, should the user be interested in a shorter fingerprint, the R value can be reduced. For instance, when considering R = 250, the P fa , P md , Prec and Rec values are affected by less than 0.03 (absolute value).

The fingerprint computation on the V component ensures total robustness against color editing. The pre-processing step (temporal down sampling at 1 frame per second and spatial down sampling at 352 x 288) is meant to ensure robustness against re-encoding. While these values are chosen according to the state of the art hints ( [START_REF] Yeh | NTNU-Academia Sinica at TRECVID 2010 Content Based Copy Detection[END_REF], [START_REF] Barrios | Content-Based Video Copy Detection: PRISMA at TRECVID 2010[END_REF], [START_REF] Coskun | Spatio-temporal transform based video hashing[END_REF]) they can be modified according to the practical application. For instance assuming a high motion FX sequence, the temporal down sampling can be neglected. When considering the live camcording case, the size of the dynamic synchronization window should be set so as to reach the trade-off between time jitter compensation and computational time. While the results reported in the paper corresponds to L = 7, a value L = 11 can slightly improve the results (by 2%).

CONCLUSION AND PERSPECTIVES

This paper advances a simple yet very efficient video fingerprinting method. The fingerprint is represented by the hierarchy of largest absolute value 2D-DWT coefficients selected from

A.3.2. Conference paper

Garboan, A., Mitrea, M., Prêteux, F., "Video retrieval by means of robust fingerprinting", Proceedings for the IEEE 15th Symposium on Consumer Electronics (ISCE), 2011, Singapore, pp. 299 -303.

Video retrieval by means of robust fingerprinting

A. Garboan 1,3 , M. Mitrea 1,3 , F. Prêteux 2, 3 1 Institut Télécom -Télécom SudParis, Department ARTEMIS ; 2 MINES ParisTech;

3 UMR CNRS 8145 MAP5 9, rue Charles Fourier, 91011 Evry France adriana.garboan@it-sudparis.eu, mihai.mitrea@it-sudparis.eu, francoise.preteux@minesparistech.fr

Abstract

Uniquely identifying visual content remains a challenging issue for a large variety of nowadays applications, as video browsing, database search and multimedia security, for instance.

In this respect, our study brought to light a simple yet efficient fingerprinting technique allowing short video sequences to be tracked. Three corpora, all of them containing 3780 video excerpts, with different excerpts lengths (20 seconds, 40 seconds and 60 seconds) were considered in the experiments. The quantitative results established that the average probability errors for both missed detection and false alarm are lower than 0.0007. These good practical results derive from the very fine mathematical properties of stationarity governing the DWT coefficients representing the fingerprint.

Index Terms -robust video fingerprinting, DWT, robustness, uniqueness.

INTRODUCTION

The worldwide mass production context brought technology closer to people. Affordable capturing, processing and storage devices along with the wide spread of broadband Internet access, empowered people to easily produce, manipulate and distribute large amounts of visual content.

Such a situation raises complex challenges in various multimedia domains (copyright protection, illegal distribution and management of massive databases, …). Despite the particular applicative challenge, issues connected to identification, authentication, indexation, retrieval, searching, navigation, organization and manipulation have to be addressed.

-162 -

The present paper is structured as follows. Section 2 introduces an original method for video fingerprinting which is experimentally validated in Section 3. Conclusions are drawn and perspectives are opened in Section 4.

DWT-BASED VIDEO FINGERPRINTING

Due to its possibility of representing in a very compact way salient characteristic of the video content and to its low complexity, the 2D-DWT is already intensively considered in practically all image processing applications, from compression and watermarking to default finding in garments.

Our study investigated whether the 2D-DWT can be employed in order to uniquely and robustly identify the visual content.

In this respect, a new video fingerprinting method is advanced, Figure 2.

In order to extract a fingerprint from a video sequence (arbitrarily chosen), that sequence is first preprocessed, then a 2D-wavelet transform is applied to its frames and finally a certain selection of the coefficients will be carried on in order to obtain the fingerprint per-se.

Fingerprinting computation principle

Be there a video sequence, represented into a given format (compressed or not).

The pre-processing step is aimed at increasing the invariance of the envisioned fingerprint to different video processing operations, be they malicious (attacks) or mundane (ordinary video manipulation).

First, the video sequence is decoded in frames in order to diminish the influence of a particular video format or codec. Second, a temporal sub-sampling to 1 fps is performed in order to eliminate the redundancy between adjacent frames and to speed-up the fingerprint computation.

Third, a spatial re-sampling to

) is performed on the sampled frames, thus increasing the robustness of the method to frame size changes attacks.

Fourth, in order to extract the salient information within the frame while reducing the computational costs, the down-sampled frames are represented in the HSV (Hue -Saturation -Value) color space with the V (luminace) component normalized to the   First, a previous study reported in [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF] employed as fingerprint the 360 highest absolute value coefficients from the This approach leads to an empiric matching procedure yielding satisfactory results on the testing database. The testing database was the same as in the current study [3]. For a heuristically determined optimal matching threshold, the average probability of false alarm and the average probability of missed detection were both lower than 005 . 0

. However, as the method did not rely on scientific ground it cannot be proposed for general applications (its performances are a priori depending on the investigated corpus).

Second, the new strategy employed in the present paper relies on a coefficients selection dependent on the role of the video sequence (query or reference).

The coefficients selection (i.e. the fingerprint) proposed here aims at conveying more information about the spatial distribution of salient features within the frames as compared to the proposal in [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF]. In this respect, the fingerprint of the query video sequence is computed and then, the fingerprints of the reference video sequences are obtained by using some spatial information provided by the query fingerprint. While for the method in [START_REF] Oostveen | Feature Extraction and a Database Strategy for Video Fingerprinting[END_REF] the correlation was computed between the DWT coefficients without any organization or hierarchy of the coefficients, for the current method, the correlation is computed between the coefficients disposed on ranks, i.e. the columns of the rank matrix. Such a strategy is justified by the statistical investigation on the DWT coefficient behavior in [START_REF] Mitrea | Zero-memory information sources approximating to video watermarking attacks[END_REF]: it was proved that the values taken by a rank in the DWT coefficient hierarchy feature stationarity and the corresponding probability density function was estimated by a mixture of Gaussian laws. Hence, the stationarity property of these coefficients ensures a certain degree of independence of the results with respect to the experimental corpus.

In practice, in order to be able to also retrieve content preserving replicas, the absolute value of the normalized correlation should be compared to some threshold T ; should A match between the query and the reference video sequences is obtained when the majority of ranks (i.e. at least 181) is correlated. Should the majority of ranks be uncorrelated the query and the reference video sequences are considered as distinct.

Assuming the k ranked DWT coefficients from the query and from the reference video sequence are i.i.d. (identically and independently distributed) and that they follow a Gaussian distribution, and assuming the 0 H is true, the

where N and  are the same as above.

Experimental results

The overall results, Figure 6, point to a very good retrieval accuracy, with false alarm and missed detection probability lower than 0007 . 0 for all the three considered corpora. On the one hand, as an empiric rule (Figure 6), the missed detection probability decreases with the length of the video sequences, i.e. with the temporal information conveyed by the fingerprint.

On the other hand the probability of false alarm increases as the length of the video sequences increases. The balanced is reached for the 40 seconds corpus. It should be also noticed that for a given attack the longer the video sequence, the better the robustness of the fingerprint. Par rapport à l'état de l'art, sous contrainte de robustesse à l'enregistrement en salle de cinéma, trois verrous scientifiques restent à lever : (1) unicité des signatures, (2) appariement mathématique des signatures, (3) scalabilité de la recherche au regard de la dimension de la base de données.

La principale contribution de cette thèse est de spécifier, concevoir, implanter et valider TrackART, une nouvelle méthode de traçage des contenus vidéo relevant ces trois défis.

L'unicité de la signature est obtenue par sélection d'un sous-ensemble de coefficients d'ondelettes, selon un critère statistique de leurs propriétés. La robustesse des signatures aux distorsions lors de l'appariement est garantie par l'introduction d'un test statistique Rho de corrélation. Enfin, la méthode développée est scalable : l'algorithme de localisation met en oeuvre une représentation par sac de mots visuels. TrackART comporte également un mécanisme de synchronisation supplémentaire, capable de corriger automatiquement le jitter introduit par les attaques de désynchronisation variables en temps.

La méthode TrackART a été validée dans le cadre d'un partenariat industriel, avec les principaux professionnels de l'industrie cinématographique et avec le concours de la Commission Technique Supérieure de l'Image et du Son. La base de données de référence est constituée de 14 heures de contenu vidéo. La base de données requête correspond à 25 heures de contenu vidéo attaqué, obtenues en appliquant neuf types de distorsion sur le tiers des vidéo de la base de référence.

Les performances de la méthode TrackART ont été mesurées objectivement dans un contexte d'enregistrement en salle : la probabilité de fausse alarme est inférieure à 16 10 -6 , la probabilité de perte inférieure à 0,041, de précision et de rappel égaux à 0,93. Ces valeurs représentent une avancée par rapport à l'état de l'art qui n'exhibe aucune méthode de traçage robuste à l'enregistrement en salle et constituent une première preuve de concept pour les technologies sous-jacentes.

MOT CLES : unicité, robustesse, scalabilité, sac à mots visuels, ondelettes, synchronisation, distorsions, augmentation/diminution de la luminosité, diminution du contraste, conversion en niveaux de gris, filtrage Gaussien, le rehaussement, rotation 2°, StirMark.

Towards camcorder recording robust video fingerprinting ABSTRACT

Sine qua non component of multimedia content distribution on the Internet, video fingerprinting techniques allow the identification of content based on digital signatures computed from the content itself. The signatures have to be invariant to content transformations like filtering, compression, geometric modifications, and spatial-temporal sub-sampling/cropping. In practice, all these transformations are non-linearly combined by the live camcorder recording use case.

The state-of-the-art limitations for video fingerprinting can be identified at three levels: (1) the uniqueness of the fingerprint is solely dealt with by heuristic procedures;

(2) the fingerprinting matching is not constructed on a mathematical ground, thus resulting in lack of robustness to live camcorder recording distortions;

(3) very few, if any, full scalable mono-modal methods exist.

The main contribution of the present thesis is to specify, design, implement and validate a new video fingerprinting method, TrackART, able to overcome these limitations. In order to ensure a unique and mathematical representation of the video content, the fingerprint is represented by a set of wavelet coefficients. In order to grant the fingerprints robustness to the mundane or malicious distortions which appear practical use-cases, the fingerprint matching is based on a repeated Rho test on correlation. In order to make the method efficient in the case of large scale databases, a localization algorithm based on a bag of visual words representation [START_REF] Sivic | Video Google: A Text Retrieval Approach to Object Matching in Videos[END_REF] is employed. An additional synchronization mechanism able to address the time-variants distortions induced by live camcorder recording was also designed.

The TrackART method was validated in industrial partnership with professional players in cinematography special effects (Mikros Image) and with the French Cinematography Authority (CST -Commission Supérieure Technique de l'Image et du Son). The reference video database consists of 14 hours of video content. The query dataset consists in 25 hours of replica content obtained by applying nine types of distortions on a third of the reference video content. The performances of the TrackART method have been objectively assessed in the context of live camcorder recording: the probability of false alarm lower than 0.000016, the probability of missed detection lower than 0.041, precision and recall equal to 0.93. These results represent an advancement compared to the state of the art which does not exhibit any video fingerprinting method robust to live camcorder recording and validate a first proof of concept for the developed statistical methodology.