A Graph-Based Framework to Bridge Movies and Synopses

Introduction

Among various forms of media, movies are often considered as the best to convey stories. While creating a movie, the director can leverage a variety of elements – the scene, the characters, and the narrative structures – to express. From the perspective of computer vision, movies provide a great arena with a number of new challenges, e.g. substantially greater length, richer presentation styles, and more complex temporal structures. Recent studies attempted to approach this problem from different angles, only achieving limited progress.

Over the past decade, extensive studies have been devoted to video analytics. A number of video-based tasks, e.g. action recognition and event classification , have become active research topics. However, methods devised for these tasks are not particularly suitable for movie understanding. Specifically, for such tasks, visual features, which can be a combination of various cues, are often sufficient for obtaining good accuracies. However, movies are essentially different. A movie is created to tell a story, instead of demonstrating a scene or an event of a certain category. To analyze movies effectively, we need new data, new perspectives, and thus new approaches.

Recently, several datasets are constructed on movies, including LSMDC and MovieGraphs . These datasets, however, are limited in that they are small or have a narrow focus on very short clips, i.e. those that last for a few seconds. To facilitate the research in movie understanding, we need a new dataset that is large and diverse, and more importantly allows high-level semantics and temporal structures to be extracted and analyzed. In this work, we construct a large dataset called Movie Synopses Associations (MSA) over $327$ movies. This dataset not only provides a high-quality detailed synopsis for each movie, but also associates individual paragraphs of the synopsis with movie segments via manual annotation. Here, each movie segment can last for several minutes and capture a complete event. These movie segments, combined with the associated synopsis paragraphs, allow one to conduct analysis with a larger scope and at a higher semantic level.

Figure 1 shows a movie segment and the corresponding synopsis paragraph, where we have two important observations: (1) The story is presented with a flow of events, governed by the underlying narrative structures. The sentences in the synopsis often follow a similar order. (2) The characters and their interactions are the key elements of the underlying story. These two key aspects, namely the dynamic flow of events and the interaction among characters, distinguish movies from those videos in conventional tasks.

In this work, we develop a new framework for matching between movie segments and synopsis paragraphs. Rather than encoding them with feature vectors, we choose to use graphs for representation, which provide a flexible way to capture middle-level elements and the relationships among them. Specifically, the framework integrates two key modules: (1) Event flow module for aligning the sequence of shots in a movie segment, each showing a particular event, to the sequence of sentences in a synopsis paragraph. (2) Character interaction module for capturing characters and their behaviors (both actions and interactions) and associating them with the corresponding descriptions. Based on these two modules, the matching can then be done by solving optimization problems formulated based on their respective representations.

It is noteworthy that the use of graphs in movie representation has been explored by previous works . However, our framework is distinguished in several aspects: 1) It takes into account complicated temporal structures and character interactions mined from data. 2) Our method does not require node-to-node annotation when using graphs.

In summary, our contributions lie in three aspects: (1) We construct a large dataset MSA on $327$ movies, which provides annotated associations between movie segments and synopsis paragraphs. This dataset can effectively support the study on how movie segments are associated with descriptions, which we believe is an important step towards high-level movie understanding. (2) We develop a graph-based framework that takes into account both the flow of events and the interactions among characters. Experiments show that this framework is effective, significantly improving the retrieval accuracies compared to popular methods like visual semantic embedding. (3) We perform a study, which reveals the importance of high-level temporal structures and character interactions in movie understanding. We wish that this study can motivate future works to investigate how these aspects can be better leveraged.

Related Work

In recent years, with the increasing popularity of cross-modal understanding tasks, e.g. video retrieval by language, a large number of datasets have been proposed . ActivityNet Captions is a dataset with dense captions describing videos from ActivityNet , which can facilitate tasks such as video retrieval and temporal localization with language queries. Large Scale Movie Description Challenge (LSMDC) consists of short clips from movies described by natural language. MovieQA is constructed for understanding stories in movies by question answering. Some of the movies are provided plots with aligned movie clips. MovieGraphs is established for human-centric situation understanding with graph annotations. But there are three problems for these datasets: (1) most of them obtain dull descriptions from crowd-sourcing platforms, (2) they simply describe short video clips lasting a few seconds, which leads to a huge gap between proposed data and real-world data where the video is much longer and the description is much more complex. (3) some of them are relatively smaller in terms of dataset size. In order to explore the high-level semantics and temporal structures in the data from real-world scenarios, we build a new dataset with long segments cut from movies and diverse descriptions from the synopses in IMDbhttps://www.imdb.com.

Feature-based Methods.

To retrieve a video with natural language queries, the main challenge is the gap between two different modals. Visual Semantic Embedding (VSE) , a widely adopted approach in video retrieval , tries to tackle this problem by embedding multi-modal information into a common space. JSF proposed in learns matching kernels based on feature sequence fusion. To retrieve video and localize clips, introduces a framework that first perform paragraph level retrieval and then refine the features by sentence level clip localization. Feature-based approaches can not further improve retrieval performance because these methods fail to capture the internal structures of video and language.

Graph-based Methods.

Graph-based methods , which build semantic graphs from both language and video and then formulate the retrieval task as a graph matching problem , is also widely used for cross-modal retrieval. Method in generates scene graph from language queries for image retrieval. A graph matching algorithm is proposed by for semantic search in the domain of autonomous driving. The graph matching problem is formulated as LP optimization with ground-truth alignment in optimization constraints. MovieGraphs proposed in uses graph as semantic representation and integrates graph into potential functions for training. It’s noteworthy that node-level annotations are required during training. In this work, we also use graph-based representations for both movies and synopses. However, unlike previous works that depend on the costly node-level annotations, our graph matching only needs ground-truth of paragraph-level alignment, which makes it much more practical.

MSA Dataset

This section presents Movie Synopsis Association (MSA), a new dataset constructed upon $327$ movies. Particularly, we choose a set of high-quality synopses from IMDb, i.e. those with detailed descriptions of individual events, one for each movie. Each synopsis here consists of tens of paragraphs, each describing an event in the movie.

We also provide the associations between movie segments and synopsis paragraphs through manual annotation. These associations constitute a solid basis to support high-level semantic analysis. We collected the associations following the procedure below. (1) We provide the annotators with a complete overview of each movie, including the character list, reviews, etc., to ensure they are familiar with the movies. (2) We carry out the annotation procedure in two stages, from coarse to fine. At the first stage, each movie is divided into $64$ clips, each lasting for around $2$ minutes. For each synopsis paragraph, an annotator is asked to select a segment, i.e. a subsequence of $N$ consecutive clips, that cover the corresponding description. At the second stage, annotators adjust the temporal boundaries of the resultant segments to make them better aligned with the paragraphs. This two-stage procedure leads to a collection of paragraph-segment pairs. (3) We dispatch each paragraph to three annotators and only retain those annotations with high consistency among them. Here, the consistency is measured in terms of temporal IoU among the annotations. Finally, we obtained $4,494$ highly consistent paragraph-segment pairs (out of $5,725$ annotations of the original collection).

Table 1 shows some basic statistics of the dataset. This dataset is challenging: (1) The duration of each movie segment is over $400$ seconds on average, far longer than those in existing datasets like LSMDC . (2) The descriptions are rich with over $100$ words per paragraph.

Figure 2 compares ActivityNet Caption with the MSA dataset with examples. We can see that the descriptions in MSA are generally much richer and at a higher level, e.g. describing characters and events, instead of simple actions. MovieQA also contains description-clip pairs. Table 2 compares MovieQA with our MSA dataset. Note that the plot synopses from MovieQA are obtained from Wikipedia while ours are from IMDb. Compared to synopses from Wikipedia, those from IMDb are written by movie fans and reviewed by others. They are longer and contain more details.

Methodology

In this section, we would present our framework for matching between movie segments and synopsis paragraphs. Specifically, given a query paragraph $P$ from a synopsis, we aim at retrieving its associated movie segment $Q$ out of a large pool of candidates. This framework consists of two modules: a Event Flow Module (EFM) to exploit the temporal structure of the event flows, and a Character Interaction Module (CIM) to leverage character interactions.

As shown in Figure 1, given a query paragraph $P$ and a candidate movie segment $Q$, each module yields a similarity score between $P$ and $Q$, denoted as $\mathcal{S}_{efm}(P,Q)$ and $\mathcal{S}_{cim}(P,Q)$ respectively. Then the overall matching score $\mathcal{S}(P,Q)$ is defined to be their sum as

In what follows, Sec. 4.1 and 4.2 present the EFM and CIM modules respectively. Sec. 4.3 introduces the training algorithm, where both modules are jointly optimized.

This module takes into account the temporal structures of event flows. It is motivated by the observation that the sentences in a synopsis paragraph tend to follow a similar order as that of situation in events (each captured by a sequence of movie shotsA shot is a series of frames, that runs for an uninterrupted period of time. Observing that frames within a shot are highly redundant, we use shot as the unit instead of frames.), as shown in Figure 3. In particular, the alignment between the sentences and the movie shots can be done based on the following principles: (1) Each sentence can match multiple shots while a shot can be assigned to at most one sentence. (2) The sentences and the movie shots follow the same order. The matching should not swap the order, e.g. associating a sentence that comes next to a preceding shot.

where $\boldsymbol{\Phi}=[\boldsymbol{\phi}_{1},\dots,\boldsymbol{\phi}_{M}]^{T}$ and $\boldsymbol{\Psi}=[\boldsymbol{\psi}_{1},\dots,\boldsymbol{\psi}_{N}]^{T}$ are the feature matrices for both domains. Taking the alignment principles described above into account, we can obtain the assignment $\mathbf{Y}$ by solving the following problem:

Here, $\mathbf{y}_{i}$ refers to the $i^{th}$ row of matrix $\mathbf{Y}$, and $\mathcal{I}(\cdot)$ denotes for the index of the first nonzero element in a binary vector. This is a bipartite graph matching problem which can be efficiently solved by dynamic programming.

2 Character Interaction Module

As discussed earlier, the interactions among characters play a significant role in movie storytelling. We also observe that the character interactions are often described in synopsis. To incorporate this aspect, we propose the Character Interaction Module (CIM) based on graph representations derived from both the synopsis paragraphs and the visual observations in the movie segments.

Specifically, each paragraph and movie segment are represented by graphs $\mathcal{G}_{p}=(V_{p},E_{p})$ and $\mathcal{G}_{q}=(V_{q},E_{q})$ respectively. The vertex sets $V_{p}$ and $V_{q}$ contain both character and action nodes. The edge sets $E_{p}$ and $E_{q}$ capture both character-character and character-action relations. With these two graphs, the similarity between $P$ and $Q$ can be computed by matching between $\mathcal{G}_{p}$ and $\mathcal{G}_{q}$. Below, we elaborate on the matching procedure.

Firstly, we generate the character and action nodes: (1) For character nodes, we utilize Faster-RCNN implemented on and pre-trained on to detect person instances in every shot. (2) We attach each person instance with an action node, which comes from a TSN pretrained on AVA dataset . Secondly, we produce the edge sets by the following procedures: (1) If a group of people appear in the same or adjacent shots, we introduce an edge between every pair of them. (2) We link each character node to its corresponding action node.

Semantic Graphs from Sentences.

For each paragraph, we construct a collections of sub-graphs from each sentence based on dependency trees, as illustrated in Figure 4.

The construction process consists of four major steps: (1) Name detection: We detect all the named entities (e.g., Jack) using StanfordNer . Then we resort to CorefAnnotator to link pronouns with named entities and substitute all pronouns with their corresponding names. (2) Character association: With the help of IMDb, we can retrieve a portrait for each named character and thus obtain facial and body features using ResNet pre-trained on PIPA . This allows character nodes to be matched to the person instances detected in the movie. (3) Sentence parsing: We use GoogleNLP APIhttps://cloud.google.com/natural-language/ to obtain the dependency tree of a sentence. Each node in the tree is labeled with a part-of-speech tagging. (4) Edge linking: Based on the dependency tree, we link each character name to its parent verb. Meanwhile, if a group of character names share the same verb, we introduce an edge between every pair of them. Note that we only consider the verbs that stand for action. We first select $1000$ verbs with the highest frequency from the synopses corpus, and then retain those corresponding to visually observable actions, e.g. “run”. This results in a set of $353$ verbs.

It is worth noting that we generate a collection of sub-graphs from paragraph instead of a connected graph. For convenience, we consider the collection of sub-graphs as a graph with notation $\mathcal{G}_{p}$ although it can be further decomposed into multiple disjoint sub-graphs. This is also what we do in our implementation.

Matching Paragraph with Movie Segment.

For graph $\mathcal{G}_{p}$, let $V_{p}$ be its vertex set with $|{V_{p}}|=m=m_{c}+m_{a}$, where $m_{c}$ is the number of character nodes and $m_{a}$ is that of action nodes. Similarly, we have $\mathcal{G}_{q}$ with $|{V_{q}}|=n=n_{c}+n_{a}$.

The target of graph matching is to establish a node-to-node assignment for the two input graphs while taking the the pair-wise constraints, namely the edges, into account.

Given the indicator $\mathbf{u}$ and the similarity matrix $\mathbf{K}$, the similarity of two graphs can be derived as

where the first term models the similarity score between matched notes $i\in V_{q}$ and $a\in V_{p}$. The second term gives the bonus from matched edges between $(i,j)$ and $(a,b)$.

Based on the properties of nodes, certain constraints are enforced on $\mathbf{u}$: (1) The matching should be a one-to-one mapping. For example, one node in a vertex set can only be matched to at most one node in the other set. (2) Nodes of different types cannot be matched together. For example, a character node can not be assigned to an action node.

The objective function, together with the constraints, can be simply expressed in the following form:

Here $V_{q}^{a}$ denotes the vertex set containing only action nodes in video with $|V_{q}^{a}|=n_{a}$ and $V_{q}^{c}$ for vertex only containing cast nodes in video. The same for $V_{p}^{a}$ and $V_{p}^{c}$.

Graph Pruning

The problem itself is known as an NP-hard Quadratic Assignment Problem (QAP). Solving it could be time consuming especially when the graph is large, which is normally the case for our video graph. To ease the problem, we propose a graph pruning strategy to reduce the graph size to an appropriate one that it can be solved in an affordable time. The strategy is described as follows:

Seed Node Generation. We first select the most important nodes as seed nodes. They are selected by the following two criteria: (a) The problem can be approximately solved by Kuhn–Munkres (KM) algorithm in polynomial time. The matched nodes can be selected as seed nodes. (b) The $k$ most similar nodes with each node from the query graph will be chosen as seed nodes.

Selection Propagation. Given the seed nodes, we extend the node selection by considering the nodes within $J^{th}$ degree connection of a seed node. We denote the seed nodes by another indicator vector $\mathbf{v}\in\{0,1\}^{n\times 1}$, the adjacency matrix as $\mathcal{A}$ of graph $\mathcal{G}_{q}$, the nodes we select can be expressed as $\mathbf{v}\leftarrow\mathcal{A}^{J}\mathbf{v}$. The pruned graph is obtained by cropping the whole graph using selected nodes.

3 Joint Optimization.

The quality of the node features would highly influence the result of matching. It is necessary for us to finetune the parameters of the models in EFM and CIM for a better representations. Since we do not have the ground truth alignment of $\mathbf{Y}$ in EFM or $\mathbf{u}$ in CIM, we can not directly update the model parameters in a supervised manner. Hence, we adopt an EM-like procedure to finetune the feature representations and optimize matching objectives. The overall loss of the whole framework is given below:

where $\boldsymbol{\theta}_{efm}$ and $\boldsymbol{\theta}_{cim}$ denote model parameters for embedding networks in EFM and CIM respectively.

Using current model parameter values $\boldsymbol{\theta}_{efm}^{*}$ and $\boldsymbol{\theta}_{cim}^{*}$, we solve Eq.3 by dynamic programming mentioned in Sec.4.1 and we obtain a sub-optimal value in Eq.7 by applying KM algorithm. Here in our implementation, the time complexity of the KM algorithm is $\mathcal{O}(\tau^{3})$ where $min(n,m)\leq\tau\leq max(n,m)$.

M-Step.

We update the model parameters in M-step with optimal solutions $\mathbf{Y}^{*}$ and $\mathbf{u}^{*}$ obtained in E-step. Particularly, given $\mathbf{Y}^{*}$ and $\mathbf{u}^{*}$, we update model parameters by

where $\mathcal{L}(S;\boldsymbol{\theta})$ is the pair-wise ranking loss with margin $\alpha$ shown below:

Experiments

We conduct experiments of movie-synopsis retrieval on MSA dataset. Specifically, search a movie segment from candidate pool given a synopsis paragraph as query.

The MSA dataset is randomly split into train, val, test subsets with $3329,341,824$ samples respectively. Note that there are no overlap movies among subsets. The statistic of the subsets is shown in Table 1.

There are two settings to measure the performance, namely, cross-movie and within-movie. The cross-movie setting considers the whole test set as the candidate pool for each query whereas the within-movie setting only takes the segments from the same queried movie to be the candidates.

Evaluation Metrics.

To evaluate the performance, we adopt the commonly used metrics: (1) Recall@K: the fraction of GT videos that have been ranked in top K; (2) MedR: the median rank of GT videos. (3) Avg. MedR: Average MedR, this is only for within-movie setting.

Implementation Details.

In EFM, Word2Vec embedding is used as sentence representation. The Word2Vec model is finetuned on MSA corpus, i.e., synopses and subtitles. The shot feature consists of two parts: 1) visual features extracted from $pool5$ layer of ResNet-101 . 2) its subtitle’s Word2Vec embedding. In CIM, we adopt ResNet-50 pre-trained on PIPA to extract the face and body feature for a detected person instance or a cast portrait. The action features in videos come from TSN pre-trained on AVA and action verbs are represented by Word2Vec embeddings. We train all the embedding networks using SGD with learning rate $0.001$. The batch size is set to 16 and the margin $\alpha$ in pair-wise ranking loss is set to $0.2$.

2 Overall Results

We adopt VSE as the base models and previous method JSF is also used for comparison. Also for comparison, we gradually add three kinds of features, namely, appearance, cast and action as nodes to baseline method. Particularly, appearance node denotes the sentence embeddings or shot features. For VSE, the features of movie shots and sentences are further transformed with two-layer MLPs. We then obtain the features of segments and paragraphs by taking the average of the shot and sentence features. During matching, the segment/paragraph similarities are computed with cosine similarity. We use the same loss as shown in Eq. 14. Matching scores from different nodes are fused by weighted sum. The weights are obtained by observing the performance of single node on val set. Here, for cross-movie setting, weights are simply set as $0.3,1.0$ and $0.1$ for appearance, cast and action respectively. For within-movie setting, weights are $0.3,0.3$ and $0.1$. Table 3 shows the overall results of video retrieval on MSA.

From the results shown in Table 3, by comparing different methods, we observe that:

(1) Both VSE and JSF outperform random guess by a large margin. The performance of JSF does not exceed that of VSE because the learned kernels in JSF fail to capture the matching pattern between paragraphs and long videos, when the concepts in paragraphs are complicated and lengths of videos vary a lot.

(2) Our method with EFM and CIM outperforms the conventional methods that only fuse features under both cross-movie and within-movie settings. Particularly, Recall@1 under cross-movie setting is raised from $19.05\%$ to $24.15\%$ ($5.10\%$ absolute and $27\%$ relative improvement) and each recall under within-movie setting improves over $1.5\%$.

Analysis on EFM and CIM.

Also shown in Table 3, the results of rows 3,6 demonstrate that the proposed EFM improves the performance on most of the metrics. We can see from the table that EFM works better especially under within-movie setting ($6.31\%$ increment on Recall@1). It is because that encoded story and narrative structure in EFM is the key to distinguish segments from the same movie.

Meanwhile, results from rows 7-8 prove the effectiveness of using character interaction graph, especially under cross-movie setting. The CIM does not bring consistent performance gain under within-movie setting compared to EFM. The reason is that segments from the same movie share a group of characters and their interactions are also similar. This is also illustrated in the right part of rows 4-5.

3 Ablation Studies

We present ablation studies on different hyper parameters. Unless stated, experiments are conducted under cross-movie setting.

As mentioned before, at inference stage, we need to obtain score in CIM by solving the optimization problem in Eq.7. It takes 2 seconds to solve one matching on average. Under the cross-movie setting, we need to solve these problems for $824^{2}$ times (the number of test samples is $824$), which sums up to more than a week. To save time, we only update the score of candidates that rank top $N$ in previous stage, e.g., VSE with score fusion.

Table 4 shows the influence on different choices of $N$. Note that we take the score in the first row to filter out a candidate list for updating. We see that from $N=15$ to $N=40$, the performance drops while remains steady when $N$ increases from $40$ to $80$. All the results still outperform the baseline in the first row. The performance drop comes from the increasing outliers when $N$ increases. Therefore, decrease $N$ can not only improve inference efficiency but also decrease the number of distractors in candidate pool.

Influence of using subtitle feature.

Recall that we use both the visual and subtitle feature as the representation of a shot by observing that sometimes the narrators tend to summarize important dialogues in synopses. We conduct ablation study on the effectiveness of subtitle feature shown in Table 5. The experiments are based on appearance nodes only. The results show that subtitle are complementary to visual information.

Graph Pruning Parameters.

To raise inference efficiency, we perform graph pruning in CIM. We set $k=2$ to select seed and $J=2$ to spread selection (recall Sec. 4.2). As $k$ and $J$ are complementary for controlling the size of pruned graph, we only conduct studies on different values of $J$. The results are shown in Table 6. It demonstrates that $J=2$ is enough for pruning a graph and increase $J$ may introduce more noise.

4 Qualitative Results

We present qualitative results on both EFM and CIM modules to further explore their effectiveness.

Figure 5 (a) shows a positive result that the characters and actions in the sentence are accurately matched. The right matching is obtained with the help of character-character and character-action relations.

Figure 5 (c) shows a case that EFM successfully assigns each sentence to the corresponding shots while CIM fails to assign the characters. In particular, “Pentangeli” is assigned to a wrong person instance while the other three names match nothing. The reason is that the person instances from movie segment are in poor quality due to dim light, occlusion or large motion expect the one appearing at the end of the segment.

Figure 5 (b) shows a failure case of EFM where the second sentence is completely miss-aligned. As shown in the upper part of the figure, this is possible because the shots belong to the third sentence contain some content of “shoot” and “tire” which mislead the model. We also observe that this case is challenging because the shots look similar to each other due to no transition of scene.

From the above observations and analysis on more such cases, we come to the following empirical conclusions: (1) Edge constraints are important for alignments. (2) The quality of nodes matters. If nodes are in poor quality, the edge constraints will take no effect. (3) Discriminative shot appearance, together with our proposed EFM, is helpful for temporal alignment.

Conclusion

In this paper, we propose a new framework for matching between movie segments and synopsis paragraphs. The proposed framework integrates a Event Flow Module to capture the narrative structures of movies and a Character Interaction Module to model character interactions using graph-based formulation. To facilitate research for movie-synopsis matching, we construct a dataset called Movie Synopses Associations (MSA). Experimental results show the effectiveness of the proposed modules. Our framework outperforms conventional feature-based methods and improves the matching accuracy consistently on all metrics. Both quantitative and qualitative studies demonstrate that our method can capture rich temporal structures and diverse interactions among characters.

Acknowledgment

This work is partially supported by the Collaborative Research grant from SenseTime Group (CUHK Agreement No. TS1610626 & No. TS1712093), and the General Research Fund (GRF) of Hong Kong (No. 14236516 & No. 14203518).

References