METHOD FOR INDEXING MULTIMEDIA INFORMATION

[0001] The present invention generally relates to a method for indexing multimedia information, including a speech to text transcription of audio information, and more particularly to a method where the speech to text transcription is performed automatically by means of an ASR process, and which comprises a priori selection of acoustic and language models.

[0002] The method is particularly applicable to the indexing, aggregation and clustering of news from different sources and from different types of files, including text, audio and audiovisual documents without any manual annotation.

[0003] Nowadays, the access to digital news is easy and fast, only an internet connection is needed. Through the network users can visit their preferred news feeds, i.e. a radio station, a TV channel, a digital newspaper or a personal web site, and browse through the broadcasted contents. However, this is a browsing centered on the news feed, not in the news themselves. The access to all the pieces of news related to the same event broadcasted by different feeds and in different media at the same time is still a challenge, especially for those based on non-textual media.

[0004] To the knowledge of the inventors, nowadays the following indexation and aggregation systems exist:

[0005] Textual indexation: NewsExplorer [1], Google News Cloud [2] or CyberAlert [3],

[0006] Textual aggregation: NewsExplorer [1] or Google News Cloud [2].

[0007] Audio indexation: Gaudi (Google Audio Indexing), Dali [9], or Blinkx [10]

[0008] Previous studies that have become news aggregation applications open to the internet community are NewsExplorer, Google News Cloud or CyberAlert, for example. However, these applications only deal with textual data, without aggregating any information broadcasted in audiovisual format and if they include a conceptual relationship between news they are done manually. On the contrary, applications like Gaudi, Dali, or Blinkx are focused on indexing video content, but they do not deal with text and only-audio contents and the news aggregation is simple or inexistent. Moreover, videos are not treated as a whole but the news have been manually selected previous to its transcription.

[0009] To sum up:

• • [0010] 1. Index and aggregate of news are performed and provided separately for different media.
  • [0011] 2. Video and audio news programs must be manually segmented into individual news pieces in order to be aggregated independently.
  • [0012] 3. The conceptual relationship between news is manually labelled.

[0013] In order to transcript audio from audio or audiovisual files, automatic transcription systems are used to follow the scheme depicted in FIG. 3. An automatic speech recognition (ASR) is performed using autoadaptative acoustic and language models (AM and LM). There are several autoadaptation systems on the market, but most of them do their adaptation reacting to the incoming entrance. The acoustic and language model adapt to the content based on the recognitions done previously, i.e. they perform “a posteriori” adaptation, which result in drawbacks regarding the processing time and resources needed before the appropriate models have been generated for the ASR.

[0014] Regarding said AM and LM models, Dali [9] states that during processing, increasingly detailed models are used at each step, while Blinkx [10] uses audio analysis techniques that are based on neural network technology and Hidden Markov Models (HMMs) to construct an efficient acoustic model that can provide a fast, accurate and dynamic solution within rapidly changing acoustic environments, such as radio and television, and LM with predictive technology.

[0015] It is necessary to offer an alternative to the state of the art which covers the gaps found therein, particularly those existing in the known indexing methods which analyze audio content of multimedia files.

[0016] To that end, the present invention provides a method for indexing multimedia information, comprising analyzing audio content of multimedia files and performing a speech to text transcription thereof where, on contrary to the known proposals, and in a characteristic manner, said speech to text transcription is performed automatically, for each multimedia file, by means of an ASR process. The method of the invention also comprises selecting acoustic and language models adapted for said ASR process at least before the latter processes the multimedia file, i.e. “a priori”.

[0017] The method of the invention is applied, for an embodiment, to multimedia information which also comprises text files, the method comprising automatically aggregating information from said text files to information from said multimedia files with audio content.

[0018] The method further comprises, for some embodiments, automatically clustering said multimedia information.

[0019] For a preferred embodiment, said multimedia information refers to news, the method comprising indexing said news from different sources, and preferably aggregating and clustering it.

[0020] Other embodiments of the method of the invention are described according to appended claims 4 to 21, and in a subsequent section related to the detailed description of several embodiments.

[0027] The proposed invention is, for the embodiments described in this section, a method in the form of an application to index, aggregate and cluster news from different multimedia feeds: digital newspapers, online news channels, personal blogs or videoblogs, etc. The present inventors understand that:

• • [0028] Indexation: consists in the registration of all the relevant concepts or keywords that appears in the news content together with their positions (time for audiovisual data). The recognition confidence for transcribed words is also registered.
  • [0029] Aggregation: Joining different news from different media containing the indexed concept.
  • [0030] Cluster: Joining the more similar keywords in order to make relations among news.

[0031] There are three main application novelties in the invention:

• • [0032] 1. The aggregation is performed on different media news, improving the indexing performance by jointly using different media (specifically text and audio)
  • [0033] 2. Complete news programs/articles are automatically incorporated to the aggregation, by automatically segmenting them in order to provide the aggregation system a set of individual pieces of news.
  • [0034] 3. Link news containing different concepts

[0035] The method of the invention is based on an iterative process to get an accurate transcription of the audio content, and a posterior textual analysis in order to aggregate and cluster similar news from different sources. The final result from the process would be an unified description of the multimedia file. This description will facilitate the indexing, classification, search and aggregation of the multimedia content.

[0036] The main objectives of the invention are:

• • [0037] 1. To improve the textual description of the audiovisual news by incorporating textual information in the ASR process.
  • [0038] 2. To segment complete news programs/articles in individual news to be aggregated by the system.
  • [0039] 3. To provide an aggregation of news of different media.
  • [0040] 4. To cluster conceptually similar news.

[0041] The Indexing and Aggregation of news is an innovative application to automatically cluster news from different mass media (TV, Radio, Newspapers). In order to do so, the news aggregation provided by the proposed invention is based on the information stored in xml files that have been automatically generated by the back-end system. The back-end system is depicted in FIG. 1. On the figure, darker color is for innovative workflows and modules.

[0042] To index and cluster the multimedia feeds every new multimedia document is treated according to the media available: text, audio or both. The back-end system transcribes the audio track into text by an ASR (Automatic Speech Recognition). Then transcription and text data from the newspapers are lemmatized. The indexation consists of detecting all the relevant concepts in the multimedia material and in keeping track of the place (for textual documents) or instant (for audiovisual documents) of their appearances. The clustering consists in selecting the keywords among all the relevant indexed concepts to generate a news label with the relationship between all the documents that contains the same keyword. Finally, for each concept the nearest keywords are selected.

[0043] By the moment, any visual cues, as from the video track as well as from images inserted in digital newspapers, are not used. However, the architecture of the indexing system has been designed to be easily extendable.

[0044] The technological innovations included on the invention are:

[0045] Convergent ASR module:

• • [0046] Textual diarization
  • [0047] “A priori” selection of acoustic and language models for ASR (Model Selection)
  • [0048] Aggregation of subtitles and ASR transcription (Aggregator)
  • [0049] Iterative ASR to include more information on each instance (Iteration)

[0050] KeyWords Selection

[0051] Concept clustering module:

[0052] More detailed information about each module is provided in the following sections.

[0053] A block diagram of the back-end system is shown in FIG. 2.

[0054] Automatic transcription systems are used to follow the scheme depicted in FIG. 3. An automatic speech recognition (ASR) is performed using autoadaptative acoustic and language models (AM and LM). There are several autoadaptation systems on the market, but most of them do their adaptation reacting to the incoming entrance. The acoustic and language model adapt to the content based on the recognitions done previously.

[0055] The Convergent ASR of the method of the present invention deals with the information in a completely different way. Instead of adapting the models to the content, the system selects the more appropriate models to make the recognition. Instead of “a posteriori” adaptation, “a priori” selection is done.

[0056] The goal of the Speaker Diarization module (see FIGS. 2 and 4) is to continuously provide the most adequate ASR acoustic model to perform the automatic transcription of the audio content. This module consists in three main operations: the segmentation of the audio track, the identification of the acoustic characteristics of each segment and the selection of the most adequate ASR acoustic model from an available set.

[0057] The segmentation of the audio track into similar acoustic intervals is performed by removing the non-speech parts using a VAD (Voice Activity Detection) and applying a diarization technique based on BIC (Bayesian information criterion) [5]. Then, each cluster is processed by an open set acoustic identifier using LLR (log-likelihood ratio) as a decision score [7]. When an identification is positive, the corresponding adapted ASR acoustic model is selected. If the identification is “Unknown” a general ASR acoustic model for multimedia applications is selected.

[0058] The models for acoustic identification and for the adapted ASR have been estimated in the development phase of the back-end system for: general multimedia applications, news conductors and noisy environments typical of news programs (background music, outdoor connections . . . ). All the acoustic models are HMM of cepstrum features adapted using the MLLR+MAP technique [8].

[0059] Provided a textual representation of the audiovisual document (coming either from the subtitles alone, or from a previous running of the transcription module), a textual diarization (see FIGS. 2 and 4) and subject identification is made, in order to select a better Language Model to transcribe the audio.

[0060] This module is a novelty, as usually document classification tasks treat the document as a whole, and provide a single class representative for the document. As (some of) the documents of this application are in fact news aggregation (radio and TV news programs), a finer classification is needed.

[0061] The input of the module is the text transcription of the document:

[0062] a) Close-caption of the TV program, if available

[0063] b) Output of a previous transcription cycle, with the subtitles info aggregated, if available

[0064] c) Text of the news, if the document is a newspaper page.

[0065] In c), the document already represents only one piece of information, so no diarization is needed, and textual classification runs in the state of the art procedure.

[0066] In both a) and b), textual representation includes temporal information, representing (approximately) when the transcribed speech was uttered in the document. Transcription is provided in pseudo-sentences (either speech between pauses of a minimal duration, or lines in the close-caption system). In this case, the module has to provide a splitting of the document in temporal chunks, and the subject classification for each of these chunks. All the procedure is independent of the taxonomy of the classes to be recognized. The class universe is only defined by the tags and models previously trained in the system. It can be the classical news sections (“national”, “international”, “sports” . . . ) or a more complex system (like IPTC taxonomy [13]), or even single news identifiers. Only two special classes are defined: “welcome” and “farewell”.

[0067] The procedure sequence to obtain each chunk with its classification is the following:

• • [0068] For each piece of information (“pseudo-sentences”), a context aggregation is performed, as usually a single phrase does not provide enough information for the classification task. This aggregation is made with a temporal criterion (an application parameter (20 seconds have been found the better for the invention) before and after the sentence to be classified), so if there is a long break, chances are less to get into a different piece of information.
  • [0069] Standard classification strategy (Bow toolkit for statistical language modeling [6], Naive Bayes, with Laplace smoothing) is applied to every contextual aggregated sentence.

[0070] After the classification, all class hypotheses with their scores are kept.

• • [0071] A time-weighted rank ordering filter is applied to select the best hypothesis for the “sentence” to be classified. The rank order filter aggregates the scores for each class in a time window, using a triangular shape windowing function, and selects the class with the highest value.
  • [0072] Finally, a postprocessing is run in order to avoid class sequences too shorts, if they lay between two long sequences with the same class. Only “welcome” and “farewell” are allowed be elude this condition.

[0073] Once the file has been acoustically and textually diarized, it is necessary to select the models to perform the best recognition possible on each part of the file.

[0074] In order to select the most appropriate acoustic model (see FIGS. 2 and 4), every Acoustic Event (speaker change) or Textual Event (topic change) are considered as independent Events. And it is considered that the beginning of the file, Acoustic and Language Models are General Ones.

[0075] Then all Events (Acoustic and Textual indistinctively) are temporally sorted out, and algorithm depicted in FIG. 5 is implemented.

[0076] It is also necessary to consider that not all acoustic or language models are available, so they should be changed to the nearest acoustic/topic model available.

[0077] For some documents (TV news), there is close-captioned information available. These subtitles are usually available for the conductors and for the edited news, but not for the live connections. These subtitles, even though they are not literal transcription of the uttered words, and can have typos and misspellings, are usually much more correct than the straight output of the ASR.

[0078] For this reason a new module (aggregator in FIG. 4) has been developed, whose function is to join the subtitles (if available) and the ASR output for the blanks in the close-captioned information. This task is not as straightforward as could seem to be. Subtitles are not exactly aligned with the spoken speech, so some heuristics have to be implemented in order to obtain the best aggregation of information:

• • [0079] First, subtitles time information is converted to the same units (seconds) of the ASR output, as this information comes originally in frames per second.
  • [0080] “Blanks” in the subtitles are detected. This “blanks” are defined as time spans longer than a threshold application dependent (15 seconds; shorter “blanks” can come from the music lead, and can be sometimes incorrectly interpreted as voice and transcribed by the ASR).
  • [0081] For every “blank”, it is filled with the output of the ASR. But time information is not enough to select the right transcribed sentences to fill the gap. The most frequent situation is that subtitles are delayed with respect to the speech (up to 5 seconds). To take this case into account, the different sentences in the ASR output, candidates to begin the filling, are evaluated against the last piece of information in subtitles before the “blank” (let's call this line “reference sentence”). These candidates are those sentences whose begin time are between five seconds before and two seconds after the end time of the “reference sentence”. The measure is the number of non-stopwords in common between the candidate and the reference sentence. The candidate with the maximum number of matches is selected as the alignment point, and the filling starts with the next sentence candidate. This is the main innovation in order to make this innovative module work properly.
  • [0082] For the end of the blank, a similar procedure is followed, modifying the overlapping thresholds, as usually the subtitles begin are better aligned to the speech (so one second before, and three seconds after).
  • [0083] Finally, time stamps are corrected, in order to keep temporal information as coherent as possible. For subtitles beginning and end times are kept. For the ASR output filled in the blank, ASR time information is also kept. The only modifications made are in border areas, in order to avoid temporal overlapping of the sources. In these cases overlapping area is split between the subtitle reference sentence and the first (or last) ASR transcription sentence.

[0084] In order to improve the performance of the overall system, the process can be iterated. The “new” transcription can be diarized, and used to repeat the transcription process with more accurate information.

[0085] Depending on the initial information available, the process could be as follows:

If there are subtitles: The subtitles are diarized, and the file is recognized, on places where no subtitles are found a general language model will be used. The new transcription is appropriately added to the original subtitles, filling the gaps, and a new diarization is made. A new transcription is done, but in this case, most of the file will be transcribed with appropriate language models.

[0086] If there are not subtitles: The file is recognized using general language models. The new transcription is textually diarized and used to make a new, more accurate transcription using a selection of language models based on the new diarized transcription.

[0087] Once the transcriptions have been done by the convergent ASRs, as shown in FIG. 1 every multimedia news document ingested in the system is automatically indexed and an xml file for each document is generated.

[0088] The indexation carried on consists in the registration of all the relevant words that appears in the news text together with their positions (time for audiovisual data). The recognition confidence for transcribed words is also registered.

[0089] The last module of the back-end system extracts the most relevant keywords of all the material that has been ingested to the system and generates an xml clustering file.

[0090] The clustering file is generated from the list of selected keywords by searching each keyword on the indexing files and contains for each keyword the number of occurrences on the database, the list of the documents where the keyword appears, and the list of related keywords. For each one of the documents, it is specified the kind of media: video, audio or text. Each video and audio file has associated the list of segments (in seconds) when the word has been said. Each segment also contains information on the ASR confidence measure and its thumbnail file. The information associated to text files includes the link to the news and its thumbnail.

[0091] To select the most relevant keywords, text is lemmatized [14], and then a modified TFIDF [12] algorithm is applied to select a set of lemmatized words extracted from all the indexing files.

[0092] The standard tfidf formula states:

$\mathrm{tfidf}\left(i,j\right)=\frac{n_{i,j}}{\sum _kn_{k,j}}\times \log \frac{D}{\left\{d\text{:}t_i\in d\right\}}$

[0093] n_i,j is the number of occurrences of the considered term (t_i) in document d_j, and the denominator on the first division is the sum of number of occurrences of all terms in document d_j.

[0094] |D|: total number of documents in the corpus

[0095] |{d:t_iεd}|: number of documents where the term t_i appears (that is n_i,j≠0). This formula represents how relevant a word i is in a document j.

[0096] It can also been used to identify the most relevant words in a set of documents, summing up the tfidf(ij) for all the documents.

$\mathrm{tfidf}\left(i\right)=\sum _j\mathrm{tfidf}\left(i,j\right)$

[0097] This formula can be improved, using as much information from the document and its structure as possible:

• • [0098] Words present in the headline or abstracts (if available, like in newspapers) are boosted with respect to the body words. They are weighted with a factor greater than one (factor W_head=10.2 in the invention).
  • [0099] Another factor (W_POS) is included in the equation. This weight depends on Part-of-Speech (POS).

[0100] Geographical and organization proper nouns receive a greater weight (1.0) than verbs and common nouns (0.6) and adjectives (0.2). People first names receive also a low weight (0.2). Stop-words receive a 0.0 weight.

[0101] Finally, the presented application has a different goal than the standard information retrieval the formula was developed for. In this application, the interest is not focused only in the words more relevant for a single document, but for the whole set of documents. So terms present in a number of documents can be more relevant than terms present in a single document. So instead of using the logarithm of the inverse of the document frequency, a power is used, whose exponent is dependent on the POS of the word:

$\mathrm{tfidf}\left(i,j\right)=W_{\mathrm{POS}}\times W_{\mathrm{head}}\frac{n_{i,j}}{\sum _kn_{k,j}}\times \left(1-{\left(\frac{d_j}{D}\right)}^{f\left({\mathrm{POS}}_i\right)}\right)$

[0102] This dependency allows us to control the distribution of the nature of relevant words in the documents. The highest this pseudo-kurtosis weight is, the less sensible is the word to be penalized by the number of documents it appears in.

f(NPRO)=2.5, so “España” can be relevant even if it appears in almost half of the documents.
f(NOMB)=0.2, so “noticia” gets a very low score for being in lot of documents, and “secuestro” is more relevant for being in a small subset.
where NPRO stands for “Proper Noun” and NOMB stands for “Noun”.

[0103] For each keyword the list of related keywords is extracted. In order to do so, the following formula is applied to calculate the correlation of each pair of words X and Y:

$C_{\mathrm{xy}}=k_y\frac{N_{\mathrm{xy}}}{N_x+N_y}$

[0104] Where N_x is the number of documents where word X appears, N_xy is the number of documents where words X and Y appear. And ky is the relevance of word Y as calculated at TFIDF algorithm.

[0105] Let be T the minimal number of selected keywords on the list, then C_xT is the correlation of word X with its Tth more correlated word (T). And ave(C_xT) the average of the correlation values for the Tth correlated term for every word.

[0106] The list of related keywords will contain:

[0107] All words with a correlation bigger than ave(Cxy).

[0108] At least the Tht more correlated words.

[0109] The Conceptual Clustering is performed periodically in order to capture the news evolution in time and the appearance/disappearance of tags.

[0110] Next are some features of the invention:

[0111] 1.—The invention provides a unique aggregation of textual, audio and audiovisual feeds.

[0112] 2.—The invention extracts individual news pieces from a complete news program/article in order to aggregate each piece independently.

[0113] 3.—In the indexation process, textual and acoustical information are jointly used to improve the performance.

[0114] 4.—The audio transcription accuracy is improved by an iterative process that selects a priori trained acoustic and language models using both textual and audio information.

[0115] 5.—Other interesting information (speakers, environments, . . . ) is captured on the process that may be used to gather new information.

[0116] 6.—The modularity of the system allows to incorporate new indexing modules based on different techniques that improve the overall system.

[0117] A person skilled in the art could introduce changes and modifications in the embodiments described without departing from the scope of the invention as it is defined in the attached claims.

[0118] BIC Bayesian information criterion

• [0119] [1] R. Steinberger, B. Pouliquen, C. Ignat Navigating multilingual news collections using automatically extracted information. Journal of Computing and Information Technology, 2005. http://emm.newsexplorer.eu/NewsExplorer/home/ES/latest.html
• [0120] [2] http://fserb.com.br/newscloud
• [0121] [3] http://www.cyberalert.com/cyberalerttv.html
• [0122] [4] http://silverlight.net
• [0123] [5] S. Chen, P. Gopalakrishnan. Speaker, environment and channel change detection and clustering via the bayesian information criterion. Proceedings DARPA Broadcast News Transcription and Understanding Workshop, Virginia, USA, 1998.
• [0124] [6] A. K. McCallum Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. http://www.cs.cmu.edu/mccallum/bow, 1996.
• [0125] [7] D. A. Reynolds Comparison of background normalization methods for text-independent speaker verification in Proc. 5^th European Conference on Speech Communication and Technology, Eurospeech 97 Sep. 1997, Greece
• [0126] [8] J.-L. Gauvain and C.-H. Lee Maximum a posteriori estimation for multivariate Gaussian mixture observations of Markov chains IEEE Trans. Speech, and Audio Processing, vol. 2, no. 2, pp. 291-298, 1994.
• [0127] [9] http://showroom.daedalus.es/es/tecnologias-de-busqueda/dali/
• [0128] [10] http://www.blinkx.com/
• [0129] [11]N. Sarris, P. Villegas, M. Pinkerneil, J. Spangenberg, J. Picault Personal navigation in the world of news 1st International conference on Semantics And digital Media Technology, SAMT2006 6-8 Oct. 2006, Athens, Greece http://www.mesh-ip.eu/
• [0130] [12]G. Salton and C. Buckley Term-weighting approaches in automatic text retrieval Information Processing & Management vol. 24, no. 5, pp. 513-523, 1988
• [0131] [13] http://www.iptc.org
• [0132] [14] http://www.loria.fr/˜gardent/applicationsTAL/slides/I4-nltk-corpora-tokenization-2x2.pdf