Label Importance Ranking with Entropy Variation Complex Networks for Structured Video Captioning

The development of mobile Internet enables various media to disseminate information. In the era of mobile Internet, video becomes an important carrier of information, and video analysis attracts more and more attention. With a complex structure, video usually contains a huge amount of data with rich features. Describing video in natural language is trivial for human beings, but thorny for machines. Many problems need to be solved in order to effectively process multimedia videos, and fully understand the relevant data.

Computer vision has developed rapidly thanks to the proliferation of neural networks and emergence of various open-source datasets. Against this backdrop, there are two trends in the development of video interpretation and processing technology: video classification, and video captioning. For video classification, a video clip can be classified by spatiotemporal features of image frames or action-containing videos [1-3]. For video captioning, the aim is to dividing each image into multiple regions, and label meaningful phrases or sentences. At present, video captioning and its application are still in the preliminary stage [4-7].

With the advancement of deep learning (DL) frameworks, most scholars have tried to caption videos with an encoding and decoding structure: the video features are often extracted by a convolutional neural network (CNN), the video codes are transformed into a semantic eigenvector, the statements are treated as a sequence generation process, and the words and sentences are generated iteratively by the neural network, using context information. But video captioning faces a challenging problem: The video captioning algorithm needs to detect the moving people or objects in the video based on moving speed and direction, and describe them with accurate words. However, it is difficult to automatically detect the few important people or objects in a long video, which often involves multiple interrelated events. Only these people or objects need to be described by relationships.

To improve the video captioning quality, this paper presents a novel structured video captioning model based on entropy variation complex networks. The proposed model firstly extracts multiple features from the video, including the feature of each static frame, the existence of objects in the frame, and the spatiotemporal features of the whole video, and then stitch the extracted features into a natural caption statement, according to the feature lengths of memory encoding and decoding network. Next, a new video boundary-aware bidirectional long short-term memory network (BiLSTM) was designed to identify the discontinuities in video frames, and to better encode a video with multiple actions. After that, entropy variation complex networks were introduced to generate captions, making the generated statements more certain, and the video captions more accurate. Different feature extraction methods with multiple modes and video features were adopted to obtain more information, thereby adaptively controlling the effects of different modal features on word generation, acquiring more video contents, and generating richer descriptive texts. Then, natural language information was derived from word entropy, and natural expressions were obtained to enhance the generalization and practicality of our model. Finally, our model was proved better than other approaches on MSVD and MSR-VTT datasets.

The research roadmap is shown in Figure 1 below.

(a) Label importance ranking with entropy variation (label importance is defined as the variation of network entropy through the removal of the label, assuming that the removal of an important node could cause substantial variation in network structure)

(b) SABiLSTM encoding unit

(c) Multi-feature processing (a semantic network is constructed using entropy variation complex networks, and feature words are sorted in descending order of hybrid eigenvalues to generate descriptive statements)

(d) Whole image processing (the three-level structured video captioning system decomposes the structures of multiple levels and dimensions from different perspectives to establish the topology of video captioning network)

1.png

Figure 1. Research roadmap

3.1 Feature selection of entropy-based complex networks

3.1.1 Construction of complex networks

Each complex network is composed of nodes and edges. The smallest unit that represents the complete semantic information in a text is a sentence. Hence, this paper treats sentences as nodes, and analyzes the structural features of a text with sentences as the unit. Edges are defined as the connections between two sentences with a common noun. The two sentences linked up by an edge may elaborate on the same topic, or convey supplementary information on the same topic. Although they might contain redundant information, the two sentences are highly similar in contents. Based on the common noun relationship of sentence pairs, it is possible to build a complex network for the target text.

After preprocessing, the nouns in each sentence are mapped to the network. Then, two matrices A and W could be defined, representing adjacency matrix and n-order matrix weight (N is the number of nodes), respectively. In matrix A, if there is an edge between nodes i and j, then A_ij equals 1, and any other item equals zero. In matrix W, w_ij is the number of occurrences of common words between i and j.

The original text should be preprocessed before constructing the weighted complex network. The proprocessing technqiues include word segmentation, word extraction, and the filtering of meaningless workds (e.g., pause words). If the text is in English, the feature words need to be restored to the prototype form, that is, the set of feature words should be extracted from the text.

The edges are assigned between nodes by Cancho and Solé’s method, that is, an edge is added between the keywords in a sentence that spans no greater than 2 keys, and the weight of the edge spans no greater than 2 co-occurrences. In this way, a text can be transformed into a weighted complex network. For a given text T, the internal keys are treated as nodes in a network of V = (v1, v2,...,vn), where V_i is a keyword, according to the edges between key nodes:

$E=\{(V i, v j) \mid V i, v j \in V\}$， $W=\{w i j \mid(v i, v j) \in V\}$     (1)

In this way, a weighted complex network can be constructed as G=(V, E, W).

3.1.2 Weighting of entropy variation in complex networks

Based on entropy-weighted complex networks, the text captioning algorithm needs to model the text as an entropy-weighted complex network, and then analyze each network node that represents a feature word. In addition, the feature words with a large composite eigenvalue will be extracted as the keywords of the text. According to complex network theories, the nodes with a large composite eigenvalue tend to cluster in local modules, and play a key role in linking up the nodes within the entire network, increasing the density and intensity of network edges. To calculate the composite eigenvalue of each node, our algorithm fully considers the weighted clustering coefficient and the number of intermediate nodes, and extracts the nodes with a large composite eigenvalue from the weighted complex network. The corresponding feature words are the keywords of the text. The algorithm flow is detailed below.

Step 1. Input the original text T for keyword extraction.

Step 2. Preprocess the original text, and extract the feature words.

Step 3. Take each feature word as a network node, connect the words in the same sentence with a span no greater than 2 with edges, and weigh each edge with the co-occurrence of words, creating a weighted complex network.

Step 4. Pair the nodes in the weighted complex network, compute the weighted clustering coefficient of nodes, the number of intermediate nodes, and the composite eigenvalue CP of network nodes:

$C P_{i}=\alpha \frac{W C_{i}}{2 \sum_{j=1}^{N} W C_{j}}+\frac{(1-\alpha) P_{i}}{2(N-1)(N-2)}$      (2)

where, $\alpha$ is an adjustable parameter; $N$, is the number of nodes in the network; $W=\{w i j \mid(v i, v j) \in V ; C$ is the distance between node $\mathrm{i}$ and the other nodesm $C_{i}=\frac{1}{\sum_{j=1}^{N} d_{i j}} ; P$ is the importance of a node, $P_{i}=\frac{1}{\sum_{j=1}^{N} d_{i}}$.

Step 5. Sort the feature nodes in descending order of eigenvalue, extract the first k feature words with a large composite eigenvalue, and take them as the k keywords of the text.

Step 6. Output the k keywords of the text.

3.1.3 Application of entropy variation complex networks

In our model, the semantics obtained by the SABi-LSTM are built into a semantic network, with each feature word as a node, and an edge between each pair of words spanning no greater than 2. The number of word co-occurrences is the weight of each edge. In the resulting weighted complex network, the weighted clustering coefficient of node v can be calculated by formula (1), and the intermediate nodes of node v can be computed by formula (2). After that, the CP value of the node is calculated, and the feature words are sorted in descending order by that value. Eventually, these keywords are constructed into description statements.

3.2 Multi-feature fusion

The flow of multi-feature fusion is depicted in Figure 2. Linear and nonlinear mappings have little difference in the case of high-dimensional data. But linear classification or regression usually achieves better results at a faster speed. After the high-dimensional features are extracted from the video, linear mapping is performed to reduce the dimensions of the features, and realize bidirectional labeling of the video and sentences.

2.png

Figure 2. Multi-feature fusion

This paper fuses the multiple features of the video, which belongs to the intermediate level of information fusion. The basic theory of feature fusion is information fusion theory. Information fusion refers to the comprehensive processing of multi-source heterogeneous data, laying the basis for joint decision-making.

Taking video recognition as a pattern classification problem, the video features can be fused under two empirical assumptions: (1) Multi-feature fusion tends to improve the classification performance from that based on a single feature; (2) Multi-feature fusion is the starting point of pattern classification, while single feature is the guide for the selection of multiple image features.

Feature fusion directly employs the current feature extraction algorithm to mine multiple features from the video than a single feature. This approach is much less costly than redesigning the features or the feature extraction algorithm. Different feature descriptors, such as red-green-blue (RGB) feature, and light flow motion, are utilized comprehensively to illustrate different aspects of the video, breaking the limitation of single feature-based content captioning. The multi-feature fusion is realized in two steps.

Step 1. Feature stitching

During feature extraction, each model uses a vector F to represent the whole video, and to splice the features extracted from various models. Then, F_fusion is directly assembled by selecting the combination of these features. The video feature imported to the natural language captioning model.

Step 2. Weighted summation

The features extracted from different models are aligned by length, and trainable weight vectors are set for weighted summation of the features. Then, the fused features are imported as video features into the natural language captioning model:

$\mathrm{F}_{\text {fision }}=W F^{T}=\left(w_{1} F_{1}+w_{2} F_{2}+\cdots+w_{m} F_{m}\right)$       (3)

where, F_fusion is the final fused feature; m is the number of features being used, $\sum_{i=0}^{m} w_{i}=1$.

3.3 Video boundary-sensing BiLSTM encoding unit

This paper proposes a new LSTM unit to identify the discontinuities in video frames, i.e., the discontinuities between actions, such as to better encode a video with multiple actions. For a given input video, the video encoder can output a sequence (s₁,s₂,…,s_m) for the entire video based on the input (x₁,x₂,…,x_n). In the encoder, the connection between layers varies with the current input and hidden state.

Then, a scene- aware loop unit is defined to modify layer connectivity over time. Whenever the action changes, the hidden state and cell memory of LSTM are reinitialized, and the hidden state of the output layer is exported at the end of the segment, i.e., the feature output of the current image. Hence, the input data following time boundaries are not affected by the contents before the boundaries, and a hierarchical representation of the video is generated, where each block encompasses similar frames.

3.png

Figure 3. Time connections determined by the scene-aware encoder and the common LSTM encoder

Figure 3 compares the time connections determined by the scene-aware encoder and the common LSTM encoder. Our encoder is based on LSTM unit, which can learn patterns with wide time dependence. At the core of the encoder lies a storage unit, capable of preserving the observed inputs in a time step.

The memory is updated under the control of three gates, all of which are combinations of the current input and the previous hidden state, followed by the sigmoid activation function. The input gate controls the addition of input to the memory; the forget gate controls what the unit forgets; the output gate controls whether the current memory should be outputted.

In each time step, the hidden state and storage location are transferred to the next time step, or reinitialized according to the detected state. Hence, the seamless update and processing of the input sequence are interrupted. The boundaries of each block are derived by a learnable function, which varies with the inputs. Finally, the scene-aware encoder is established as a linear combination the current input and the hidden state, followed by the activation function, a combination of sigmoid function and step function:

$s_{t}=\tau\left(\boldsymbol{V}_{s}^{T} \cdot\left(W_{s i} x_{t}+W_{s h} h_{t-1}+b_{s}\right)\right)$      (4)

$\tau(x)=\left\{\begin{array}{l}1, \text { if } \sigma(x)>0.5 \\ 0, \text { otherwise }\end{array}\right.$      (5)

where, v^T_s is a learnable row vector; W_sh and b_s are learning weight and bias, respectively.

Let s_t be the state before unit update. According to the state, the hidden state and memory unit at the start of a new segment will be transferred or reinitialized:

$\mathrm{i}_{t}=\sigma\left(W_{i x} x_{t}+W_{i h} h_{t-1}+b_{i}\right)$     (6)

$\mathrm{f}_{t}=\sigma\left(W_{f x} x_{t}+W_{f h} h_{t-1}+b_{f}\right)$     (7)

$g_{t}=\sigma\left(W_{g x} x_{t}+W_{g h} h_{t-1}+b_{g}\right)$     (8)

$c_{t}=\mathrm{f}_{t} \odot c_{t-1}+\mathrm{i}_{t} \odot g_{t}$     (9)

$o_{t}=\phi\left(W_{f x} x_{t}+W_{f h} h_{t-1}+b_{f}\right)$      (10)

$h_{t}=o_{t} \odot \phi\left(c_{t}\right)$     (11)

$h_{t-1} \longleftarrow h_{t-1} \cdot\left(1-s_{t}\right)$     (12)

$c_{t-1} \longleftarrow c_{t-1} \cdot\left(1-s_{t}\right)$      (13)

The previous video encoding methods simply stack many layers together, adding to the nonlinearity of LSTM structure, or build a layered architecture in which the lower level encodes fixed-length blocks, while the higher level merges the blocks into the final video representation. By contrast, our encoder can generate variable length blocks according to the input features, and encode them in a hierarchical structure, without damaging the structure of the neural network.

where, $\odot$ is the Hadamard product; σ is an S-shaped function; ϕ is the hyperbolic tangent function tanh; W_* is the learning weight matrix; b_* is the learning bias vector. The internal state h and the memory unit C are initialized as zero.

Then, the gates are recalculated from the resulting state and memory unit, and adopted for the next time step. The encoder generates output only at the end of the segment. If S_t=1, the hidden state of time step t-1 will be passed onto the next layer.

Figure 4 presents the structure of our scene-aware encoder. The above formulas are executed layer by layer to produce a variable-length output set $\left(S_{1}, S_{2}, \cdots, s_{m}\right)$, where m is the number of segments. Each output conceptually summarizes the contents of the segments detected in the video. The output set is passed onto another layer to build a hierarchical representation of the video. Hence, the output of the scene-aware encoder is imported to another LSTM layer, and the final hidden state is taken as the eigenvector of the entire video.

4.png

Figure 4. BiLSTM unit

The previous video encoding methods simply stack many layers together, adding to the nonlinearity of LSTM structure, or build a layered architecture in which the lower level encodes fixed-length blocks, while the higher level merges the blocks into the final video representation. By contrast, our encoder can generate variable length blocks according to the input features, and encode them in a hierarchical structure, without damaging the structure of the neural network.

It can be also inferred from Table 1 that our technique clearly outshined the average pooling methods and the common LSTM-based method (S2VT). Besides, METEOR was compared with the state-of-the-art methods that rely on rich visual features for optimal performance. In this regard, our approach surpassed the closest competitor by a wide margin (1%).

Concerning the performance on MSR-VTT (Table 2), our technique outperformed other baselines in CIDER. Similar to the observations on MSVD, our technique achieved better performance than the basic CNN+RNN, MP-LSTM, by replacing RNN with convolutional layers in the decoder.

Further, different aspects of our technique were evaluated empirically. A few highlights are mentioned in the following text. If necessary, the readers can request for supplementary materials that support the discussion.

Whereas all the components of the proposed technique contribute to the overall performance, the biggest innovation of our work is the application of entropy variation complex networks to calculate the node weight of video captions. Unlike to the “nearly standard” averaging pooling in the existing captioning pipeline, the proposed use of entropy variation complex networks promises a significant performance gain for any method. Hence, the authors recommended replacing the mean pooling operation with our entropy variable complex network for the future techniques.