Sketching Image Gist: Human-Mimetic Hierarchical Scene Graph Generation

The scene graph $\mathcal{G}=\{\mathcal{O},\mathcal{R}\}$ of an image $\mathcal{I}$ contains a set of entities $\mathcal{O}=\{o_{i}\}_{i=1}^{N}$ and their pairwise relations $\mathcal{R}=\{r_{k}\}_{k=1}^{M}$. Each $r_{k}$ is a triplet $\langle o_{i},p_{ij},o_{j}\rangle$ where $p_{ij}\in\mathcal{P}$ and $\mathcal{P}$ is the set of all predicates. As illustrated in Figure 2, our approach can be summarized into four steps. (i) We apply Faster R-CNN [30] with VGG16 [34] backbone to detect all the entity proposals and each of them possesses its bounding box $\bm{b}_{i}\in\mathbb{R}^{4}$, 4,096-dimensional visual feature $\bm{v}_{i}$, and the class probability vector $\bm{q}_{i}$ from the softmax output. (ii) In Section 3.2, HET is constructed by organizing the detected entities according to their perceptive levels. (iii) In Section 3.3, we design the Hybrid-LSTM network to parse HET, which firstly encodes the structured context then decodes it for graph inference. (iv) In Section 3.4, we improve the scene graph generated in (iii) with our devised RRM which further adjusts the rankings of relations and shifts the graph focus to the relations between entities that are close to top perceptive levels of HET.

We aim to construct a hierarchical structure whose top-down levels are accord with the perceptive levels of humans’ inherent scene parsing hierarchy. From a massive number of observations, it can be found that entities with larger sizes are relatively more likely to form the major events in a scene (this will be proved effective through experiments). Therefore, we arrange larger entities as close to the root of HET as possible. Each entity can be decomposed into finer entities that make up the inferior level.

Concretely, HET is a multi-branch tree $\mathcal{T}$ with a virtual root $o_{0}$ standing for the whole image. All the entities are sorted in descending order according to their sizes and we get an orderly sequence $\{o_{i_{1}},o_{i_{2}},\ldots,o_{i_{N}}\}$. For each entity $o_{i_{n}}$, we consider entities with larger size, $\{o_{i_{m}}\},1\leq m<n$, and calculate the ratio

where $A(\cdot)$ denotes the size of the entity and $I(\cdot,\cdot)$ is the intersection area of two entities. If $P_{nm}$ is larger than threshold $T$, $o_{i_{m}}$ will be a candidate parent node of $o_{i_{n}}$ since $o_{i_{m}}$ contains most part of $o_{i_{n}}$. If there is no candidate, the parent node of $o_{i_{n}}$ is set as $o_{0}$. If there are more than one, we further determine the parent with two alternative strategies:

The interpretability of HET implies that important relations are more likely to be seen between entities either inside a certain level or from two adjacent levels. Therefore, both hierarchical connection [38] and sibling association [51] are useful for context modeling. Our Hybrid-LSTM encoder is proposed, which consists of a bidirectional multi-branch TreeLSTM [36] (Bi-TreeLSTM) for encoding the hierarchy context, and a bidirectional chain LSTM [4] (Bi-LSTM) for encoding the siblings context. We use two identical Hybrid-LSTM encoders to encode two types of context for each entity, one is entity context which helps predict the information of entity itself, and the other is relation context which plays a role in inferring the relation when interacting with other potential relevant entities. For brevity we only provide a detailed introduction of entity context encoding (Figure 2(a)). Specifically, the input feature $\bm{x}_{i}$ of each node $o_{i}$ is concatenation of visual feature $\bm{v}_{i}$ and weighted sum of semantic embedding vectors, $\bm{z}_{i}=\bm{W}_{e}^{(1)}\bm{q}_{i}$, where $\bm{W}_{e}^{(1)}$ is word embedding matrix initialized from GloVe [27]. For the root node $o_{0}$, $\bm{v}_{0}$ is obtained with the whole-image bounding box, while $\bm{z}_{0}$ is initialized randomly.

The hierarchy context (blue arrows in Figure 2(a)) is encoded as:

where $\bm{C}=\{\bm{c}_{i}\}_{i=0}^{N}$ and each $\bm{c}_{i}=\left[\overrightarrow{\bm{h}_{i}^{\mathcal{T}}};\overleftarrow{\bm{h}_{i}^{\mathcal{T}}}\right]$ is the concatenation of the top-down and bottom-up hidden states of Bi-TreeLSTM:

where $C(\cdot)$ denotes the set of children nodes while subscript $p$ denotes the parent of node $i$.

The siblings context (red arrows in Figure 2(a)) is encoded within each set of children nodes which share the same parent:

where $\bm{S}=\{\bm{s}_{i}\}_{i=0}^{N}$ and each $\bm{s}_{i}=\left[\overrightarrow{\bm{h}_{i}^{\mathcal{L}}};\overleftarrow{\bm{h}_{i}^{\mathcal{L}}}\right]$ is concatenation of forward and backward hidden states of Bi-LSTM:

where $l$ and $r$ stand for left and right sibling which share the same parent with $i$. We further concatenate hierarchy and siblings context to obtain the entity context, $\bm{f}^{\mathcal{O}}_{i}=[\bm{c}_{i};\bm{s}_{i}]$. Missing branches or siblings are padded with zero vectors.

The relation context is encoded (Figure 2(b)) in the same way as entity context except that the input of each node is replaced by $\{\bm{f}^{\mathcal{O}}_{i}\}_{i=0}^{N}$ . Another Hybrid-LSTM encoder is applied to get the relation context $\{\bm{f}^{\mathcal{R}}_{i}\}_{i=0}^{N}$.

To generate a scene graph, we should decode the context to obtain entity and relation information. In HET, a child node strongly depends on its parent, i.e., information of parent node is helpful for prediction of child node. Therefore, to predict entity information, we decode entity context in a top-down manner following Eq. (4a) as shown in Figure 2(c). For node $o_{i}$, the input $\bm{x}_{i}$ in Eq. (4a) is replaced with $[\bm{f}_{i}^{\mathcal{O}};\bm{W}_{e}^{(2)}\bm{q}_{p}]$, where $\bm{W}_{e}^{(2)}$ is word embedding matrix and $\bm{q}_{p}$ is the predicted class probability vector of the parent of $o_{i}$. The output hidden state is fed into a softmax classifier and bounding box regressor to predict entity information of $o_{i}$. To predict the predicate $p_{ij}$ between $o_{i}$ and $o_{j}$, we feed $\bm{f}_{ij}^{\mathcal{R}}=[\bm{f}_{i}^{\mathcal{R}};\bm{f}_{j}^{\mathcal{R}}]$ to an MLP classifier (Figure 2(d)). As a result, a scene graph is generated, and for each triplet containing subject $o_{i}$, object $o_{j}$ and predicate $p_{ij}$, we obtain their scalar scores $s_{i}$, $s_{j}$, and $s_{ij}$.

So far, we obtain the hierarchical scene graph based on HET. As we collect the key relation annotations (Section 4.1), we intend to further maximize the performance on mining key relations with supervised information, and explore the advantages brought by HET. Consequently, we design a Relation Ranking Module (RRM) to prioritize key relations. As analyzed in Related Works, regions of humans’ interest can be tracked under the guidance of visual saliency although they do not always form the major events that humans want to convey. Besides, the size, which guides HET construction, not only is an important reference for estimating the perceptive level of entities, but also is found helpful to rectify some misleadings in humans’ subjective assessment on the importance of relations (see the Appendix). Therefore, we propose to learn to capture humans’ subjective assessment on the importance of relations under the guidance of visual saliency and entity size information.

We firstly employ DSS [8] to predict the pixel-wise saliency map (SM) $\mathcal{S}$ for each image. To effectively collect entity size information, we propose a pixel-wise area map (AM) $\mathcal{A}$. Given the image $\mathcal{I}$ and its detected $N$ entities $\{o_{i}\}_{i=1}^{N}$ with bounding boxes $\{\bm{b}_{i}\}_{i=1}^{N}$ (specially $o_{0}$ and $\bm{b}_{0}$ for the whole image), the value $a_{xy}$ of each position $(x,y)$ on $\mathcal{A}$ is defined as the minimum normalized size of entities which cover $(x,y)$:

where $\mathcal{X}=\{i|(x,y)\in\bm{b}_{i},0<i\leq N\}$. The sizes of both $\mathcal{S}$ and $\mathcal{A}$ are the same as that of input image $\mathcal{I}$. We apply adaptive average pooling ($\mathrm{AAP}(\cdot)$) to smooth and down-sample these two maps to align with the shape of conv5 feature map $\mathcal{F}$ from Faster-RCNN, and obtain the attention embedded feature map $\mathcal{F}_{S}$:

where $\odot$ is the Hadamard product.

We predict a score for each triplet to adjust their rankings. The input contains visual representation for a triplet, $\bm{v}_{ij}\in\mathbb{R}^{4096}$, which is obtained by RoI Pooling on $\mathcal{F}_{S}$. Besides, the geometric information is also an auxiliary cue for estimating the importance. For a triplet containing subject box $\bm{b}_{i}$ and object box $\bm{b}_{j}$, the geometric feature $\bm{g}_{ij}$ is defined as a 6-dimensional vector following [11]:

which is projected to a 256-dimensional vector and concatenated with $\bm{v}_{ij}$, resulting in the final representation for a relation $\bm{r}_{ij}=[\bm{v}_{ij};\bm{W}^{(g)}\bm{g}_{ij}]$ where $\bm{W}^{(g)}\in\mathbb{R}^{256\times 6}$ is projection matrix. Then we use a bi-directional LSTM to encode global context among all the triplets so that ranking score of each triplet can be reasonably adjusted considering scores of other triplets. Concretely, the ranking score $t_{ij}$ for a pair $(o_{i}$, $o_{j})$ is achieved as:

$\bm{W}^{(r)}_{1}$ and $\bm{W}^{(r)}_{2}$ are weights of two fully connected layers. The ranking score is fused with classification scores so that both the confidences of three components of a triplet and ranking priority are considered, resulting in the final ranking confidence $\phi_{ij}=s_{i}\cdot s_{j}\cdot s_{ij}\cdot t_{ij}$, which is used for re-ranking the relations.

We adopt the cross-entropy loss for optimizing Hybrid-LSTM networks. Let $e^{\prime}$ and $l^{\prime}$ denote the predicted label of entity and predicate respectively, $e$ and $l$ denote the ground truth labels. The loss is defined as:

When the RRM is applied, the final loss function is the sum of $\mathcal{L}_{CE}$ and ranking loss $\mathcal{L}(\mathcal{K},\mathcal{N})$, which is used to maximize the margin between the ranking confidences of key relations and those of secondary ones:

where $\gamma$ denotes margin parameter, $\mathcal{K}$ and $\mathcal{N}$ stand for the set of key and secondary relations, $r$ and $r^{\prime}$ are relations sampled from $\mathcal{K}$ and $\mathcal{N}$ with ranking confidences $\phi_{r}$ and $\phi_{r^{\prime}}$. $Z_{1}$, $Z_{2}$, and $Z_{3}$ are normalization factors.

Ablation studies are separated into two sections. The first part is to explore some variants of HET construction. We conduct these experiments on VG150. The complete version of our model is HetH, which is configured with IFS and Hybrid-LSTM. The second part is an investigation into the usage of SM and AM in RRM. Experiments are carried out on VG-KR. The complete version is HetH-RRM, whose implementation follows Eq. (8).

Ablation study on HET construction. We firstly compare AFS and IFS for determining the parent node. Then we investigate the effectiveness of the chain LSTM encoder in Hybrid-LSTM. The ablative models mentioned above are shown in Table 1 as HetH-AFS (i.e.replace IFS by AFS), and HetH w/o chain. We observe that using IFS together with Hybrid-LSTM encoder has the best performances, which indicates that HET would be more reasonable using IFS. It’s noteworthy that if the Bi-TreeLSTM encoder is abandoned, the Hybrid-LSTM encoder would almost degenerate to MOTIFS. Therefore, through comparisons between HetH and MOTIFS, HetH and HetH w/o chain, it implies that both hierarchy and siblings context should be encoded in HET.

Ablation study on RRM. In order to explore the effectiveness of saliency and size, we ablate HetH-RRM with the following baselines: (1) RRM-Base: $\bm{v}_{ij}$ is extracted from $\mathcal{F}$ rather than $\mathcal{F}_{S}$, (2) RRM-SM: only $\mathcal{S}$ is used, and (3) RRM-AM: only $\mathcal{A}$ is used. Results in Table 2 suggest that both saliency and size information indeed contributes to discovering key relations, and the effect of saliency is slightly better than that of the size. The hybrid version achieves the highest performances. From the following qualitative analysis, we can see that with the guidance of saliency and rectification effect of size, RRM further shifts the model’s attention to key relations significantly.

For scene graph generation, we compare our HetH with the following state-of-the-art methods: VRD [24] and KERN [2] use knowledge from language or statistical correlations. IMP [44], Graph-RCNN [45], MemNet [41], MOTIFS [51] and VCTree-SL [38] mainly devise various message passing methods for improving graph representations. For key relation prediction, we mainly evaluate two latest works, MOTIFS and VCTree-SL on VG-KR. Besides, we further incorporate RRM to MOTIFS, namely MOTIFS-RRM, to explore the transferability of RRM. Results are shown in Table 1 and 2. We give statistical significance of the results in the Appendix.

Quantitative Analysis. In Table 1, when evaluated on VG150, HetH dominantly surpasses most methods. Compared to MOTIFS and VCTree-SL, HetH using multi-branch tree structure outperforms MOTIFS and yields comparable recall rate with VCTree-SL which uses a binary tree structure. It indicates that hierarchical structure is superior to plain one in terms of modeling context. We observe that HetH achieves better performances compared to VCTree-SL under PREDCLS protocol, while there exists a slight gap under SGCLS and SGGEN protocols. This is mainly because our tree structure is generated with artificial rules and some incorrect subtrees inevitably emerge due to occlusion in 2D images, while VCTree-SL dynamically adjusts its structure in pursuit of higher performances. Under SGCLS and SGGEN protocols in which object information is fragmentary, it is difficult for HetH to rectify the context encoded from wrong structures. However, we argue that our interpretable and natural multi-branch tree structure is also adaptive to the situation when there is an increment of object and relation categories but fewer data. It can be seen from evaluation results on VG200 that the HetH outperforms MOTIFS by 0.67 mean points and VCTree-SL by 1.1 mean points. On the contrary, in this case, the data are insufficient for dynamic structure optimization.

As SGG task is highly related to VRD task, we apply HetH on VRD and the comparison results are shown in Table 3. Both the HetH and RelDN [55] use pre-trained weights on MSCOCO, while only [48] states that they use ImageNet pre-trained weights and others remain unknown. It’s shown that our method yields competitive results and even surpasses state-of-the-arts under some metrics.

When it comes to key relation prediction, we directly evaluate HetH, MOTIFS, and VCTree-SL on VG-KR. As shown in Table 2, HetH substantially performs better than other two competitors, suggesting that the structure of HET provides hints for judging the importance of relations, and parsing the structured information in HET indeed capture humans’ perceptive habits.

In pursuit of ultimate performances on mining key relations, we jointly optimize the HetH with RRM under the supervision of key relation annotations in VG-KR. From Table 2, both HetH-RRM and MOTIFS-RRM achieve significant gains, and HetH-RRM is better than MOTIFS-RRM, which proves the superiority of HetH again, and shows excellent transferability of RRM.

Qualitative Analysis. We visualize intermediate results in Figure 4(a-d). HET is well constructed and close to human’s analyzing process. In the area map, regions of arm, hand, and foot get small weights because of their small sizes. Actually, relations like $\langle$lady, has, arm$\rangle$ are indeed trivial. As a result, RRM suppresses these relations. More cases are provided in the Appendix.

We conduct additional experiments to validate whether HET has a potential to reveal humans’ perceptive habits. As shown in Figure 6(a), we compare the depth distribution of top-5 predicted relations (represented by tuple $(d_{o_{i}},d_{o_{j}})$ consisting of the depths of two entities, and the depth of root is defined as 1.) of HetH, RRM-base and HetH-RRM. After applying RRM, there is a significant increment on the ratio of depth tuples (2, 2) and (2, 3), and a drop on (3, 3). This phenomenon is also observed in Figure 4(e). Previous experiments have proved that RRM obviously upgrades the rankings of key relations. In other words, relations which are closer to the root of HET are regarded as key ones by RRM. We also analyze the ranking confidence ($\phi$) of relations from different depths with the RRM-base model (to eliminate the confounding effect caused by AAP information). We sample 10,000 predicted relation triplets from each depth five times. In Figure 6(b), the ranking confidence decreases as the depth increases. Therefore, different levels of HET indeed indicate different perceptive importance of relations. This characteristic makes it possible to reasonably adjust the scale of a scene graph. As shown in the first row in Figure 7, hierarchical scene graph from our HetH-RRM enlarges in a top-down manner as the quota of top relations increases, while the ordinary scene graph in the second row enlarges itself aimlessly. If we want to limit the scale of a scene graph but keep its ability to sketch image gist as far as possible, it is feasible for our hierarchical scene graph since we just need to cut off some secondary branches of HET, but is difficult to realize in an ordinary scene graph.

Besides, different from traditional Exhausted Prediction (EP, predict relation for every pair of entities) during inference stage, we adopt a novel Structured Prediction (SP) strategy, in which we only predict relations between parent and children nodes, and any two sibling nodes that share the same parent. In Figure 6, we compare the performances and inference speed between EP and SP for HetH-RRM. Despite the slight gap in terms of performances, the interpretability of connections in HET makes SP feasible to take a further step towards efficient inference, getting rid of the $O(N^{2})$ complexity [16] of EP. Further researches need to be conducted to balance performance and efficiency.