Alignment of text and video: matching ebooks and their film adaptations Jeppe Knockaert Supervisor: Prof. dr. ir. Rik Van de Walle Counsellors: Ir. Miel Vander Sande, Ir. Tom De Nies, Dr. Wesley De Neve Master's dissertation submitted in order to obtain the academic degree of Master of Science in de ingenieurswetenschappen: computerwetenschappen Department of Electronics and Information Systems Chairman: Prof. dr. ir. Jan Van Campenhout Faculty of Engineering and Architecture Academic year 2013-2014 Alignment of text and video: matching ebooks and their film adaptations Jeppe Knockaert Supervisor: Prof. dr. ir. Rik Van de Walle Counsellors: Ir. Miel Vander Sande, Ir. Tom De Nies, Dr. Wesley De Neve Master's dissertation submitted in order to obtain the academic degree of Master of Science in de ingenieurswetenschappen: computerwetenschappen Department of Electronics and Information Systems Chairman: Prof. dr. ir. Jan Van Campenhout Faculty of Engineering and Architecture Academic year 2013-2014 Preface Thisdissertationcombinestwothingsthathavefascinatedmesincemyyouth: technology and books. Choosing this subject has motivated me to discover the newest trends in the domains of digital publishing and natural language processing. This would not have been possible without my supervisor, prof. dr. ir. Rik Van de Walle and my counsellors: ir. Miel Vander Sande, ir. Tom De Nies and dr. Wesley De Neve. I want to thank my counsellors especially, for advising me, for sharing the newest trends in the digital publishing domain and for helping to keep me on track. I also want to thank my girlfriend, Sigried, for always supporting me and for sharing her knowledge in the domain of languages, of which I knew little myself. And finally, I want to thank my parents for their constant support and understanding during my five years as a student at Ghent University. Jeppe Knockaert, June 2014 i Usage permission “The author gives permission to make this master dissertation available for consultation and to copy parts of this master dissertation for personal use. In the case of any other use, the limitations of the copyright have to be respected, in particular with regard to the obligation to state expressly the source when quoting results from this master disserta- tion.” Jeppe Knockaert, June 2014 ii Alignment of text and video: matching ebooks and their film adaptations by Jeppe Knockaert Master’s dissertation submitted in order to obtain the academic degree of Master of Science in de ingenieurswetenschappen: computerwetenschappen Academic year 2013-2014 Ghent University Faculty of Engineering and Architecture Department of Electronics and Information Systems Chairman: Prof. dr. ir. Jan Van Campenhout Supervisor: Prof. dr. ir. Rik Van de Walle Counsellors: Ir. Miel Vander Sande, Ir. Tom De Nies, Dr. Wesley De Neve Summary Ebooks are on the rise and their enrichment is a hot topic in the publishing world. However, creating an enriched ebook currently still requires a lot of manual work. Au- thoring environments try to assist authors by taking over part of that effort. The goal of this dissertation is to find out if it is possible to align an ebook with its film adaptation. To achieve this goal, three matching methods are implemented in a web application that could be integrated in an authoring environment. One of these matching methods uses mainly exact matching, while the other two make use of semantic similarity measures based on WordNet. The results show that the method using exact matches outperforms the other two. The resulting recall and precision values indicate that there is still room for improvement, but that the implemented application could already be used in some use cases. Keywords: cross-media similarity, text alignment, digital publishing iii Alignment of text and video: matching ebooks and their film adaptations JeppeKnockaert Supervisor(s): Prof.dr.ir.RikVandeWalle,Ir.MielVanderSande,Ir.TomDeNies,Dr.WesleyDeNeve Abstract—Ebooksareontheriseandtheirenrichmentisahottopicin Inthenextsection, workrelatedtothisresearchwillbedis- thepublishingworld. However,creatinganenrichedebookcurrentlystill cussed.InSectionIII,thedifferentmethodsdevelopedforalign- requiresalotofmanualwork.Authoringenvironmentstrytoassistauthors inganebookwithitsfilmadaptationwillbetreated. SectionIV bytakingoverpartofthateffort.Thegoalofthisdissertationistofindout will elaborate on the architecture of the module and Section V ifitispossibletoalignanebookwithitsfilmadaptation. Toachievethis goal,threematchingmethodsareimplementedinawebapplicationthat willelaborateonitsimplementation. Themethodswillbeeval- couldbeintegratedinanauthoringenvironment. Oneofthesematching uated using two different ebooks in Section VI. Section VII methodsusesmainlyexactmatching,whiletheothertwomakeuseofse- discussesfutureworkandSectionVIIIconcludesthispaper. manticsimilaritymeasuresbasedonWordNet. Theresultsshowthatthe methodusingexactmatchesoutperformstheothertwo.Theresultingrecall andprecisionvaluesindicatethatthereisstillroomforimprovement,but II. RELATEDWORK thattheimplementedapplicationcouldalreadybeusedinsomeusecases. In this section, three relevant research topics will be high- Keywords—cross-mediasimilarity,textalignment,digitalpublishing lighted. Thefirstofthesetopicsiscross-mediaretrieval,which concerns retrieving media objects using other media objects as I. INTRODUCTION aquery. Thesecondisabouttextsimilarityandthethirdtopic WHILEprint book markets have been declining all over isabouttechniquesforpreprocessingtexts. Europe and the US, ebook markets start to gain some marketshare. ThisevolutionisespeciallynoticeableintheUS A. Cross-mediaretrieval andtheUK,witharound20%ebooksinthetrademarket. The Tomatchvideotoatext,anobviousareaofresearchtolook evolutionisalsoclearlystartingtohappeninGermanyandthe into,iscross-mediaretrieval.Inthisresearcharea,themaingoal Netherlands:about10%ofbooksinthetrademarketareebooks. istofindawaytoretrievemediafilesusingothermediafilesas OtherEuropeancountriesarenotthatfaryet,buttheretoo,the aquery. Forexample,tofindimagesbasedonanaudiofileor, trendisnowbeginningtoshow[1]. inthiscase,tofindavideousingtext. The evolution from print books to ebooks opens up a lot of While the techniques used for cross-media retrieval are use- newpossibilities. Ebooksarenotrestrictedtotextandimages, ful, they are mostly concerned with detecting high-level con- but can also contain video, audio and interactivity. But why ceptsinmediaobjects. Inordertoalignabooktoitsfilmadap- would you want interactivity in your books? Because of in- tation in an accurate way, concepts are most often too general. creasedimmersionandreaderengagement. Device6 isagood That is why the subtitles of the video are used instead of the example of an ebook that uses the possibilities of digital pub- videoitself. Thistransformstheproblemfromfindingmatches lishingtoencourageimmersionandreaderengagement[2]. As between a video and a text into finding matches between two youprogresstroughthebook,youhelptosolvethemysteryby texts. decipheringclueshiddenintext,imagesandaudiofragments. Withtheenrichmentofebooksinmind,thisresearchfocuses B. Textsimilarity on the automatic alignment of text and video. Using the in- Thereisalotofresearchintotheareaoftextsimilaritymea- formation on the alignment, a number of interactive elements sures. Some,suchasstringeditdistances,simplymeasuresim- couldbeprovided. Thecreatorofthebookcouldbesuggested ilarity by looking at the text characters. Other, more advanced possible matching video fragments for each chapter for exam- measures,takesemanticsintoaccount. ple. Another, more advanced interactive application, would be Themoreadvancedkindofsimilaritymeasuresoftenmakes theintegrationofasystemthatallowstheusertowatchashort useofalexicaldatabase,suchasWordNet[3]. WordNetinpar- videosummaryofwhathappenedbeforeinthebookheisread- ticulargroupswordsinsynsets: groupsofwordsthatexpressa ing. distinctconcept.Thesesynsetsarelinkedtoeachotherbasedon Todemonstratetheresults,amoduleforanonlineauthoring semanticandlexicalrelations. Byusingtheselinks,asemantic environment for ebooks has been developed. Such an environ- distancebetweenwordscanbededuced. ment can help a writer or a publisher to create digital publica- tions. The module in question provides a list of matching re- C. Preprocessingtechniques sults given an ebook and its film adaptation. The environment can choose to use these results for automatic enrichment or it A lot of text similarity measures make use of a form of pre- canchoosetoreturntheresultsimmediatelytotheuserinstead. processing. Thesetechniquesaimtoimproveperformance,ac- Forthisdissertation,ratherthanintegratingthemodule,ademo curacy or both. Two well-known and often-used methods are interfacehasbeenimplementedtodemonstratetheresults. Porterstemmingandstopwordremoval. inthesamewayitisdoneforthequotes.Thetiminginformation Book foreachsubtitleisalsoextractedandstored. sePnatresnincge s Prseepnrotecnecsessing sMeanttcehnicnegs Posmtparotccheesssing Fmoramtcahtteinsg The second parser is the scene parser. In addition to its ba- Subtitles sic functionality, which is the same as the functionality of the simple parser, this component tries to identify scenes and also tries to merge multiple partial subtitle sentences into one sen- Fig.1. Thegeneralflowoftheimplementedmethods tence. For the parsing of the ebook, nothing changes from the functionalityofthesimpleparser. Porterstemmingremovessuffixesfromaworduntilonlythe Scenedetectionisperformedbyonlylookingatthesubtitles. stemremains[4]. Awordstemisthepartofawordthatiscom- Whentwosubsequentsubtitlesarefarenoughfromeachother monamongallofitsvariants. Ininformationretrieval,ithelps intime,theyareconsideredtobeindifferentscenes. Thisway to identify which words have, in essence, the same meaning. ofworkingmightnotbesuitableingeneralforscenedetection, Stopword removalremovesthe wordsthatoccur frequentlyin butitprovidesaveryfastwayofdefiningcrudescenesinavideo alanguageorinatext[5]. Thesewordsoftencontributelittleto usingonlythesubtitles. Sometimesithappensinsubtitlesthat themeaningofatext,whichiswhytheycouldbeleftoutwhen differentpartsofonesentencearenotshownatthesametime. comparingtwotexts. Thisisdetectedbyrelyingonthepunctuationmarks. Whenap- propriate,thesepartialsentencesaremergedintoonesentence. III. METHODOLOGY C. Preprocessingthesentences Thissectionwillintroduceyoutothemethodsthatwereused in this research. Three methods were developed. One of these Beforepassingtheparsedsentencestothematcher, theyare is a lightweight and basic approach constructed from scratch. preprocessed. Multiple preprocessing steps can be included Theothertwomethodsuseadvancedsimilaritymeasuresfrom in one processing pipeline. In that case, they are executed in related work. First, an overview of the methods will be given. the order they are specified. Four preprocessing modules have Afterthat,everypartoftheprocessingsequenceofthemethods beenimplemented: ageneralpurposecleantextpreprocessor,a willbeexplainedinmoredetail. preprocessortoremovepunctuation,apreprocessorperforming Porterstemmingandapreprocessortoremovestopwords. A. Overviewofthemethods Thecleantextpreprocessor issomewhatgeneralpurpose. It Allmethodsusethesameprocessingsequenceconsistingof performsmultipletasksthatleadtoacleanertext. Forexample, differentmodules. TheflowofthemethodsisasshowninFig- it removes HTML tags and dashes indicating dialogues in the ure 1. When an ebook file and a subtitle file are entered, the subtitles. firststepisalwaystoparsethesentencesfrombothfiles. Each The punctuation removal preprocessor does what the name of these sentences gets preprocessed in order to make match- implies, it removes all punctuation marks from sentences. Al- ing easier, faster or both. Then the matching is made between though punctuation marks can be useful to guide matching, sentencesfromthebookandsentencesfromthesubtitles. This punctuation is dangerous to rely on when matching two texts is where the main difference between the three methods is lo- thatarenotequal. cated.Eachofthemimplementsadifferentmatchingalgorithm. The third preprocessor uses Porter stemming to transform a After a list of matches has been prepared, the matches are fed givensentence. PorterstemmingwasalreadydiscussedinSec- troughapostprocessingstepwhichtriestokeepthegoodones tionII. Wordsarereducedtotheirstem, whichmeansallvari- andthrowawaythebadones.Finally,thematchesareformatted ations of the word are represented in the same way. This can inanoutputformatchosenbytheuser. make matching easier. It can also reduce memory usage and increase matching speed, because less characters need to be B. Parsingtheinputfiles matched. The last preprocessor is one that was also already discussed Two parsing modules have been implemented, the first is in the related work section. Stop word removal is performed calledthesimpleparserandthesecondiscalledthesceneparser. byusingthestandardlistincludedinMySQL1.Thisisalistof Whilethesimpleparserextractsonlythenecessaryinformation, generalstopwordsintheEnglishlanguage. Stopwordremoval thesceneparserdoessomethingmore. ismostlyusedforincreasingspeedandreducingmemoryusage For books, the simple parser retrieves only the quotes. This byexcludingwordsthatdonotcontributetothemeaningofthe isbecausetheothersentencesinbooksmostlycontaincontex- textsinquestion. Therearealsodangerstousingstopwordre- tual information that cannot be found in the subtitles. When moval. Inthecaseofamatchingalgorithmbetweentwotexts, contextualinformationoccursinthefilmadaptation,itismostly itcouldbethatbyremovingallstopwords,toomanyshortsen- visualised instead of spoken out aloud. An example of this is tencesarelosttomakeagoodmatch. the description of characters or landscapes. Keeping only the quotesreducesthecomplexityoftheproblem. D. Matchingthesentencesfromthebookandthesubtitles The retrieved quotes are then split into sentences based on punctuation marks indicating the end of a sentence. Splitting The matching module is where the parsed and preprocessed into sentences helps to make the unit of comparison of ebooks sentences of the two texts get aligned to each other. The first assimilaraspossibletotheunitofcomparisoninsubtitles. For 1http://dev.mysql.com/doc/refman/5.7/en/fulltext- eachofthesubtitles,thetextisretrievedandsplitintosentences stopwords.html ofthemethodsisonethatwascreatedfromscratchforthisdis- Thefirstoneoftheseisthesubtitleperspectivepostprocessor. sertation. Itisintendedtobelightweightandfastcomparedto Whilethematchingmethodsfindoptimalmatchingsubtitlesfor theothertwomethods. Thosetwomethodsusemoreadvanced every quote, this postprocessor does the opposite: it finds the techniquesfromrelatedwork. best matching quotes for every subtitle and eliminates quotes The proposed method loops over all quotes from the book that have a lower similarity value. The thought behind this is andtriestofindthebestmatchingsubtitlesforeachoneofthese that most subtitles will only match to at most one quote in the quotes. Aseparatewayofmatchingisusedforsmallsentences text. and regular sentences. The number of words a sentence needs The second postprocessor is the scene postprocessor. This tobeconsideredregularisdecidedbytheparameterβ. postprocessorusesthesceneinformationextractedbythescene For regular sentences, the similarity is based on the number parser discussed earlier. The subtitles within one scene often ofexactmatchingwordsintwosentences. Thesimilarityvalue have a similar subject and this property is used to extract false iscalculatedastheaverageoftherelativenumberofmatchesin matches. To do this, the matches are grouped by scene first. bothsentences. Eachofthecombinationsofsentencesthathas Withinthatscene,theyareorderedbyquoteindex.Basedonthe at least a similarity value of α and at least β matching words allowedgapparameter,quotesthatarecloseenoughtogetherare isstoredtemporarily. Whenallsubtitleshavebeenconsidered, groupedinclusters. Onlytheclusterswiththehighesttotalsum onlythosewiththehighestsimilarityvaluearesavedasmatches ofsimilarityvaluescanstay,thematchesintheotherclustersof for that quote. For small sentences, only exact matches are thatscenearedeleted. used and they are only used if the subtitle index is within the The quote timeline postprocessor and the subtitle timeline timewindowofthelastreliablematchbetweentworegularsen- postprocessor are based on the same guiding principle. Let us tences. Tobereliable,amatchneedstohaveasimilarityvalue taketheformeroneasanexample.There,thematchesaresorted ofatleastthevalueofparameterθ. Theothertwomethodsem- basedonthesubtitleindexes. Inthatorder,themethodlooksat ploythesamewayofworkingastheproposedmethod,withone thequoteindexes.Ifthelinearityofthestoriesinthetextandthe bigdifference: thewayinwhichsimilarityiscalculated. There- filmadaptationissimilar,thequoteindexesshouldalsomoreor fore, for the other two methods, only that specific part will be lessbeinalinearorder. Themethodimposesthisbyremoving discussed. irregular indexes. This is accomplished by keeping a window The second method is the sentence analysis method. It is in which the next quote index is expected to be. To allow for based on research by Wang et al. [6]. The method is special bigger gaps in the story, matches outside the time window, but in that it uses semantic role labelling and a concept of related stillclosetoit,areconsideredagain. Ifabigenoughnumberof words. Semantic role labelling labels the words in a sentence subsequentmatcheshasquoteindexesclosetothequoteindex according to their roles relative to the predicates in that sen- ofthematchunderconsideration,itiskeptanyway. tence. Ingeneral,wordsareonlyconsideredsimilariftheyhave F. Formattingtheoutput thesamerolelabelandiftheyaresemanticallyrelated. Words areconsideredsemanticallyrelatedwhentheyarethesameorif The final list of matches is passed to the formatter, which is theyareinasemanticrelationshipsuchassynonym,hypernym, responsibleforcreatingarepresentationforthematchesthatis hyponym, meronymorholonym. Theserelationscanbefound usefulfortheuser.TheimplementedmoduleisanXMLformat- byqueryingWordNet,thelexicaldatabasementionedinSection ter,whichreturnsanXMLfilewiththeresults. Butother,more II. advanced representations are also possible. For example, there The third method is called the semantic nets method and is couldbeamodulethatputsvideofragmentsnexttothematch- based on a paper by Li et al. [7]. The method employs a ingsentencesoramodulethatreturnsanautomaticallyenriched weighted combination of word order similarity and semantic ebookfile. word similarity for its similarity measure. The semantic word similarityiscalculatedusingthepathlengthanddepthofwords IV. ARCHITECTURE inlexicalhierarchies.WordNetstructuresnounsandverbsinhi- Thedemoapplicationforsynchronisingbooksandfilmadap- erarchieswherethenodesarewordsandtheirsynonyms. Edges tationsconsistsoftwobigparts.Thefirstpartistheparttheuser in these hierarchies are defined by “is a”/“is a kind of” (ISA) getstosee:thefront-endoftheapplication. Thesecondbigpart and “part-whole” (HASA) relations, which can be discovered of the application is its back-end. The front-end consists of a by querying WordNet. The word order similarity is calculated user interface which is split into a synchronisation part and an bytakingthecombinedsetofdistinctwordsfromthetwosen- evaluation part. The first part allows the user to enter a book tences. For each of these words, the index of the most similar and a subtitle file in order to get a list of matches between the wordineachofthesentencesisstoredintwoseparatevectors. twofiles. Thesecondpartisusedforexperimentation. Whena Usingthesetwovectors,thewordordersimilarityvalueiscal- groundtruthhasbeencomposed,theevaluationpartcanbeused culated. tocalculaterecall,precisionandtheF-measure. The back-end of the application is built based on the Pipes E. Postprocessingtheresultingmatches and filters pattern [8]. When input data is given, a pipeline After a list of matches has been generated by the matching withfilteringstepsisexecutedsequentially. Eachfiltergetsthe module, asequenceofpostprocessorsisusedinordertotryto output of the previous step, uses it to perform its functional- eliminatefalsematchesthatmayhavebeenaddedtothelistof ity and passes the generated output to the next filter. The last matches. Atotaloffourpostprocessorshasbeenimplemented. filter reports the outcome. This pattern allows exchangeability andreusabilityofmodules. Theformerisimportantfortesting Method Precision Recall F2 multiplecombinationsofmodulesanditcouldalsoallowusers Proposed 0.38 0.38 0.38 to make their own combinations of modules. The latter allows Sentenceanalysis 0.22 0.28 0.27 reusingpartsofthemethods. Preprocessorsareagoodexample Semanticnets 0.16 0.28 0.24 ofmodulesthatareoftenreused.Thestructureoftheprocessing pipelinewasalreadyshownintheoverviewofSectionIII. The TABLEI differentcomponentsinFigure1matchwiththedifferentcom- COMPARISONOFTHEMETHODSFOR“THEHUNGERGAMES” ponents in the architecture, except for the book and subtitles, whicharenotapartoftheapplication. V. IMPLEMENTATION nativeimplementations[10]. Themeasuretakesanargumentβ. This argument determines the relative importance of precision Toshowcasetheimplementedalgorithms, awebapplication overrecallandviceversa. Whenβ = 1isused, precisionand was created. The web application helps the user to discover recallareofthesameimportance. Inthecaseofβ =0.5,preci- which part of a film adaptation adheres to a certain part of the sionismoreimportantthanrecallandforβ = 2,recallismore book. Bychoosingforawebapplicationoveranofflineappli- importantthanprecision. cation, thesynchronisationapplicationcaneasilybeintegrated asamoduleinaweb-basedauthoringenvironment. B. Datasetsusedfortheanalysis The front-end of the application is built using HTML, CSS Inordertotesttheimplementeddemosystem,twobooksand andJavaScript.JavaScriptwasalsousedtoimplementtheback- their film adaptations were used. Testing the system on multi- end of the application. The Node.js platform allows to use pledifferentinputsallowstoobserveifthemethodsaregeneral JavaScript as a server-side scripting language for creating fast enough. It also enables to see how much parameter values are andscalablenetworkapplications[9]. Themainreasonforthe tiedtoaspecificinput. speedandscalabilityoftheNode.jsplatformisthatitusesevent- The first book that was chosen, is “A Game of Thrones”3 driven,non-blockingI/O. by George R.R. Martin. As film adaptation for the book, the Node.js also provides a convenient package manager called npm2. More than 70,000 modules are available for use in episode“WinterIsComing”4 fromthe“GameofThrones”se- ries was taken. The episode represents only part of the book, Node.jstroughnpm,showingthepopularityofbothNode.jsand which makes the probability of generating false matches a lot npm. Afewofthesemoduleswereusedthroughouttheapplica- higher. tionfortasksasrunningthewebapplication,parsingtheEPUB The second book is “The Hunger Games”5 by Suzanne filesandPorterstemming. Collins. The film adaptation adhering to this book is the Because no full WordNet implementation was available for movie “The Hunger Games”6 from 2012. Unlike the episode Node.js and because two of the methods use WordNet for cal- from“GameofThrones”,thismovieencompassesthecomplete culating semantic similarity, an alternative solution was used. book. The first impression, when matching manually, was that ThetwomatchingmethodsthatneedWordNetfunctionalityare “A Game of Thrones” matches its film adaptation more accu- implemented as Java applications. The task of the JavaScript ratelythanisthecasefor“TheHungerGames”. module in the processing pipeline is to spawn the correct Java application and to process the results returned by that applica- C. Analysisoftheresults tion. The methods and data sets are compared using the scene VI. EVALUATION parser as parser module and the clean text preprocessor and punctuation removal preprocessor as preprocessing modules. Before discussing the evaluation results, the measures for ThesemodulesappearedtoprovidethemostcertaingaininF evaluatingtheresultswillbediscussed,followedbyashortdis- 2 measure. This measure was chosen because it creates a pref- cussionofthedatasets. erenceforrecallaboveprecision. Thisisdonedeliberately,be- A. Evaluationmeasures causetheprecisionvaluescanstillbeimproveduponinthepost- processingstep,whichisnotthecasefortherecallvalues. The Objectiveevaluationmeasuresareneededtobeabletoquan- results for “The Hunger Games” are presented in Table I and tify the difference between multiple implemented algorithms. thosefor“AGameofThrones”areshowninTableII. Threemeasuresareusedintheevaluation: precision,recalland Whentheseresultsarecompared,itisimmediatelyclearthat theF-measure,whichcombinestheothertwomeasures. the proposed method works best for the data sets in question. The precision and recall measures are two of the most used The other two methods lack in precision because the semantic objective performance measures in the area of information re- similarity allows for too much false positives. The lower re- trieval[10].Precisionisusedtoindicatethefractionofretrieved call values are caused by the strict parameter values for these matchesthatarerelevant, whilerecallmeasuresthefractionof methods. These strict parameter values were needed to keep thetotalamountofrelevantmatchesthatwereactuallyretrieved. The F-measure is a measure that combines recall and preci- 3http://www.goodreads.com/book/show/13496 sioninonesinglescore,makingiteasiertocomparetwoalter- 4http://www.imdb.com/title/tt1480055 5http://www.goodreads.com/book/show/2767052 2https://www.npmjs.org 6http://www.imdb.com/title/tt1392170