# When Causal Intervention Meets Adversarial Examples and Image Masking for
Deep Neural Networks

###### Abstract

Discovering and exploiting the causality in deep neural networks (DNNs) are
crucial challenges for understanding and reasoning causal effects (CE) on an
explainable visual model. ”Intervention” has been widely used for recognizing
a causal relation ontologically. In this paper, we propose a causal inference
framework for visual reasoning via do-calculus. To study the intervention
effects on pixel-level features for causal reasoning, we introduce pixel-wise
masking and adversarial perturbation. In our framework, CE is calculated using
features in a latent space and perturbed prediction from a DNN-based model. We
further provide the first look into the characteristics of discovered CE of
adversarially perturbed images generated by gradient-based methods 111
https://github.com/jjaacckkyy63/Causal-Intervention-AE-wAdvImg. Experimental
results show that CE is a competitive and robust index for understanding DNNs
when compared with conventional methods such as class-activation mappings
(CAMs) on the Chest X-Ray-14 dataset for human-interpretable feature(s) (e.g.,
symptom) reasoning. Moreover, CE holds promises for detecting adversarial
examples as it possesses distinct characteristics in the presence of
adversarial perturbations.

Index Terms—  Causal Reasoning, Adversarial Example, Adversarial Robustness,
Interpretable Deep Learning

##  1 Introduction

In recent years, deep neural networks (DNNs) based models have demonstrated a
significant improvement in state-of-the-art results for several vision tasks
[1, 2]. Despite their effectiveness, DNNs are notoriously cryptic for their
complexity, opacity, and lacking apparent relationship between neural
architecture and the function being evaluated by the network. These challenges
are amplified especially when DNN models show superior performance over
conventional methods (e.g., decision-trees) on human-interpretable feature
learning tasks, such as clinical (i.e., cancer recognition [3]), emotional
(i.e., violence detection [4]), and social (i.e., behavior reasoning [5])
patterns recognition, where even experts did not fully reach a proper
consensus. Therefore, interpretability [6] and explainable reasoning features
of DNNs remain challenging. From regulatory aspects (e.g., GDPR [7]), human-
interpretable feature selection is crucial for administrative decision-making,
as current DNNs highly depend on supervised labels generated by human
knowledge but barely explain the learned relationship between its labeled
input-feature(s) and predicted output(s). The importance of reasoning is also
motivated by demystifying the vulnerable properties of DNNs against
adversarial examples [8, 9, 10].

This paper studies the problems of causal interpretability on DNNs for vision
tasks. We propose a new visual reasoning method inspired by causal inference
embedded DNNs and verify its sensitivity on input masking and adversarial
perturbations. We summarize some input intervention-based explanation methods
for DNNs as follows.

Fig. 1: Visual intervention in three classical causal conditions [11]: (I)
$X\rightarrow{}Y$ for single class counterfactual reasoning; (II)
$X\leftarrow{}Y$ for multi-classes counterfactual reasoning, and (III)
$Z\leftarrow{}X\rightarrow{}Y$ for conditional multitasking counterfactual
reasoning of a visual perceptual-model.

Saliency map based method. Many works employ saliency map for visual
explanations. Class activation mappings [12] (CAMs) have provided visual
explanations via tracing gradient-based localization. Gradient information
from a penultimate convolutional layer was used in GradCAM [13] to identify
discriminating patterns in input images. However, CAM-based methods have some
limitations on causal reaonsing. They could only conclude that a DNN model
would feature with certain localized patterns. Denoting a trained DNNs model
as $Y$ and input data as $X$, CAM-based mothods can be viewed as a reverse
causation (e.g., $X_{input}\xrightarrow[\overleftarrow{CAM}]{\textbf{DNN Model
}}Y_{output}$). Saliency maps [12, 13] only establish a correlation for
interpretability while it is possible to trace a particular image region that
is responsible for it to be correctly classified; it cannot elucidate what
would happen if a certain portion of the image was masked out. See [11] for a
What If question, when a classifier is used in the wild. In addition to this
causal reasoning weakness, recent study also shows CAMs barely preserve
robustness from a gradient adversarial attacks as a secure reasoning index
[14].
Adversarial robustness. Although there has recently been a great deal of
research in adversarial defenses, many of these methods are later shown to be
broken [15]. The most common, “brute force” solution is adversarial training,
where we simply include a mixture of normal and adversarially-generated
examples in the training set [16]. One obvious limitation of previous work is
the robustness generalizability for adversarial examples beyond the pre-
defined norm or distributional constraints.
Causal reasoning. Building causal interpretations toward evaluating a robust
and interpretable DNNs are still largely unexplored. Causality as a means of
explanation has deep roots for factor selection and has received many
attentions. The rest of this paper is presented as follows. First, we describe
a general framework to build a causal inference to reason over a targeted DNN
model via intervention. Second, we discover adversarial robustness between
causal factor. Lastly, we propose an adversary-sensitive feature-map to
visualize the causal effects of interpreterable features (e.g., symptoms)
toward large-scale medical datasets by using DenseNet [2]. Our contributions
include:

  * •

The design of a causal inference framework for calculating CE on single task,
multi-labels, and multitasking vision tasks. An autoencoder network has been
introduced for intervening interpretable feature(s).

  * •

The investigation of CE toward highlighting counterfactual intervention by
pixel-wise masking and adversarial settings.

  * •

A case study for learning the causal effects from a large-scale medical
dataset (Chest X-Ray-14) for reasoning related chest symptoms by Causal Effect
Map (CEM).

##  2 Related Works

Causal models have been advocated as a proper method [17] for parameter
reasoning in a complex system. Modeling bias and fairness as a counterfactual
[17] is a new way to quantify the bias of models. Ideas from causal inference
have also been used in providing comprehensive explanations of deep learning
models. In [18], a method is developed to build a causal model over human-
centric image-based abstractions of the model, which helps provide the ability
to allow users to propose comprehensive queries. With an interpretable
concept, the method could learn a causal model relating to network activations
and features for classifications. Moreover, as DNNs can be viewed as a
graphical model for inference, recent work in [19] proposed using Structural
Causal Models (SCM) to reason over a deep-learning model. The technique
includes building the direct acyclic graph (DAG) structure from the DNN,
applying a suitable transformation and estimating the causal effect using
causal inference.

##  3 Visual Causal Intervention

###  3.1 Causal Theory

We adopt the widely-accepted Causal Effect (CE) from Pearl’s do-calculus222We
use do-operator $do(\cdot)$ as conditional intervention following by the
original definition in Pearl 2009 [11].  for $do(X_{i}=x_{i})\equiv
x_{i}=f_{i}(pa_{i},u_{i})$, where $pa_{i}$ are the parents of variable $X_{i}$
in a graph, $G$. Selecting two disjoint sets of random variables, $X$ and $Y$,
the causal effect of $X$ on $Y$ is denoted as $P(y|do(x))$, which is a
function from $X$ to the space of probability distributions on $Y$. As an
illustration, here we introduce a graph $G$ including random variables
$\mathbf{X,Y,Z}$ in Figure 1 for constructing elemental causal networks for
this study.
Computing the Effect of Intervention An atomic intervention
do($X_{i}=x^{\prime}_{i}$) has been used in the previous study [18] as a
$truncated~{}factorization$ for feature selection in a latent space of a
targeted DNN system for causal reasoning. Given a joint distribution
P($\mathbf{O},\mathbf{P},\mathbf{X}$), over a set of DNN with outputs
$\mathbf{O}$, inputs $\mathbf{P}$, and intermediate variables $\mathbf{X}$,
from the definition in [20], measuring CE of an intervention on
$x^{\prime}_{i}$ on $X_{j}=x_{j}$ with all of the evidence $Z$ could be
computed as:

$Effect(x_{i}\rightarrow{}x_{j},Z)=P(x_{j}|do(x_{i}^{\prime}),Z_{X_{i}})-P(x_{j}|Z_{X_{i}})$
(1)

The excepted casual effect from Eqn. 6 in [18] has been defined as:

$E_{X_{i}}[Effect(x_{i}\rightarrow{}x_{j},Z)]=\sum_{x_{i}\in
X_{i}}P(X_{i}=x_{i}|Z)\times(1)$ (2)

Then, we adapt the method in (2) on DNN model with (I) single task, (II)
multiple tasks, and (III) multiple labels from Figure.1 for computing
expected-CE analysis, where $Z_{X_{i}}$ is a counterfactual setting.
Interventions as Variables Different from previous approaches to directly
measuring the intervened result for calculating CE, alternatively, an
intervention $do(X_{i}=x^{\prime}_{i})$ could be encoded by adding to $G$ a
link $F_{i}\rightarrow{X_{i}}$, where $F_{i}$ is a new variable taking values
in $\left\\{do(x^{\prime}_{i}),idle\right\\}$. Here, the notion of $``idle"$
means “no intervention” following Pearl’s Eqn. 3.8 [11]. In this paper, we
adapt this concept by introducing masking and adversarial intervention as
$F_{i}$ variables for discovering CE within the DNN in a zero-out evident
state, $Z_{0}$. This conditional probability could be calculated by:

$P(x_{i}|pa^{\prime}_{i})=\left\\{\begin{matrix}P(x_{i}|pa_{i})&if~{}F_{1}=idle,\\\
0&if~{}F_{i}=do(x^{\prime}_{i})~{}and~{}x_{i}\neq x^{\prime}_{i},\\\
1&if~{}F_{i}=do(x^{\prime}_{i})~{}and~{}x_{i}=x^{\prime}_{i}.\end{matrix}\right.$
(3)

The advantages of this augmented causal graph in (3) are its capability for
showing the ramification of spontaneous change in $f_{i}$ from $F_{i}$ instead
of merely replacing $f_{i}$ by a constant.

Fig. 2: Framework and deep network topology. We use pixel-wise masking as
$F_{i}$ and adversarial examples as $F_{j}$ intervention variables in the
$Z_{0}$ (zero-out) counterfactual setting.

###  3.2 Concept extraction by Autoencoder

Autoencoder networks Our autoencoder consists of five convolutional layers.
The encoder and decoder each have two symmetrical layers, and they aim to
capture the textural features corresponding to human visual perception.
However, our decoder reconstructs slightly altered network activations while
ensuring significant downstream network activations are unaffected. We mainly
designed a low-dimensional layer in the middle to integrate scattered features
into concepts. This is inspired by how our brain pays attention, processes
information and interpretsthe perceived inputs.
Build up a Causal Baseline To attain better causality measurement, we trained
our model with a designed loss function composed of three parts from the
existing studies [18] as casual baseline: interpretability loss, shallow
reconstruction loss, and deep reconstruction loss. Shallow reconstruction loss
is simply the $L_{1}$ norm of the difference between the input and output of
autoencoder to represent the activations of the network. Also, we applied the
deep reconstruction loss in the form of the KL-divergence between the output
probability distribution of original and autoencoder-inserted network. Our
total loss function for the causality model is (from Harradon et al. 2018 Eqn.
7 in [18]):
$L(\theta;x_{i})=\lambda_{shallow}\times
L_{shallow}(\theta;x_{i})+\lambda_{deep}\times L_{deep}(\theta;x_{i})\\\
\indent\indent\indent+\lambda_{interpretability}\times
L_{interpretability}(\theta;x_{i})$ (3)
Our method is based on the proposed loss in the previous work [18] to
reproduce the measurement of causality.

###  3.3 Intervention Methods

In the zero-out ($Z_{0}$) setting, we discuss two types of perturbation as
independent intervention variables for computing expected-CE: (1) pixel-wise
masking (PWM) and (2) adversarial noise. The purpose of pixel-wise
perturbation, $F_{i}$, is to recognize the causal relationship between a local
pixel and the final output result of a DNN. We apply the following adversarial
noises on images as another intervention $F_{j}$.
Fast Gradient Sign Method (FGSM) Fast Gradient Sign Method (FGSM) [21] is a
gradient-based adversarial noise to generate adversarial examples by one step
gradient update along the direction of the sign of gradient at each pixel.
Jacobian-Based Saliency Map (JBSM) Attack Papernot et al. [22] designed an
efficient saliency adversarial map, called Jacobian-based Saliency Map Attack
by saturating a few pixels in a given image to their maximum or minimum
values.
BIM and PGD Attacks Kurakin et al. [16] applied extended Fast Gradient Sign
method by running a finer optimization (smaller change) for multiple
iterations Basic Iterative Method (BIM) attack. Projected gradient descent
(PGD) attack has been introduced by subjecting to a constraint [16].

##  4 Experiments

We use three benchmark image datasets which have been proved robust to
reassure that the causal effect would not be compromised by the defect of
data. The datasets are fashion-MNIST, ImageNet and NIH-ChestX-Ray-14. We
investigate $X\rightarrow{}Y$ for single feature causal intervention. For
adversarial setting in our experiments, we use maximum $L_{\infty}$
perturabtion strength $\epsilon$ = $0.3$ and iterative steps = 10.
Numerical Validation on Bird Dataset In previous work, the VGG19 [23] model
applied to bird200 [24] had significant causal effect with intervention at
layer 18 feature 2. In our work, we also use VGG19 to reproduce the procedure
and test the causality by intervening the same position. The expect causal
effect is $7.6341\times 10^{-3}$, which suffices to validate our method and
proved the potential of better interpretability.

###  4.1 Quantitative Study on NIH-ChestX-Ray-14

NIH-ChestX-Ray-14 [25] is the largest available chest Xray dataset. Despite of
anatomical obstacles, CheXNet model could attain competitive classification
performance with radiologists [26]. Different from various classes in
ImageNet, the interpretable patterns in ChestX-ray14 are clinical symptoms,
which could only be recognized by radiologists and hardly identified by CAM
against adversarial setting in Figure 3.
CheXNet We implemented CheXNet [26] as a 121-layer convolutional neural
network trained on ChestX-ray14 dataset contains frontal-view chest X-ray
images and labeled with up to 14 different thoracic diseases. We modified the
DenseNet121 model by replacing the final fully connected layer and apply a
sigmoid layer. We use Adam with 0.001 learning rate, $\beta 1$ as 0.9, $\beta
2$ as 0.999. We choose binary cross entropy, and the classifier ended up
achieved 85.08% accuracy. Besides, we investigate $Y\rightarrow{}X$ by masking
the known symptoms and generate negative Expected-CE as ${-1.624}\times
10^{-4}$, which provides inference. For $Z\leftarrow{}X\rightarrow{}Y$, we
zero-out the nodes which activate additional feature identified as a pulmonary
disease as an additional label suggested by a pulmonologist. However, CE of
this multitasking reasoning is not obvious. Intervention by pixel-wise Masking
For PWM, we intervene with the visual traits of inputs. We mask 10 % area of
the images randomly to explore the impact of masking on the causal effect. We
could assure the intervention without bias with a chance to observe the region
of interest of the causal model. The results in Table 1, 3, and 4 show the
value of Expected-CE deceases by PWM, which indicate a declined causal
importance inferences by pixel-wise perturbation.
Intervention by Adversarial Attacks From Table 2., we observe a numerical
difference of Expected-CE by four gradient-based adversarial attacks, where
FGSM has a larger negative causal effect with -5.6129 $\times 10^{-6}$. We
then adapt FGSM to evaluate generic datasets in Section 4.2.

The presence of malicious adversarial-noise via CAMs such as (I) in Fig. 3 is
often hardly to detect if the dataset has similar visual patterns (e.g.,
clinical patterns). We propose an adversary-sensitive causal effect map (CEM)
by activated weights of CE in Eqn. 1 on each pixel toward classifying a
specific class.

Table 1: Expected-CE on CheXNet Level(L), Node(N) | $Z_{0}$ |  $F_{i}$ = PWM
---|---|---
3,4 | 4.5076$\times 10^{-3}$ | 7.2356$\times 10^{-7}$
6,5 | 2.843$\times 10^{-3}$ | 1.2154$\times 10^{-5}$
6,10 | 3.1939$\times 10^{-3}$ | 9.0066$\times 10^{-6}$
8,5 | 3.1939$\times 10^{-3}$ | 1.1536$\times 10^{-5}$
10,7 | 1.3775$\times 10^{-2}$ | -1.1506$\times 10^{-5}$
Table 2: CheXNet ($F_{j}$ on L = 10, N = 7) $F_{j}$ = Types of Adversarial Attack | Expected-CE
---|---
FSGM | -5.6129$\times 10^{-6}$
BIM | 4.3435$\times 10^{-5}$
JBSM | 7.7548$\times 10^{-5}$
PGD | -3.9605$\times 10^{-6}$
Fig. 3: Sensitivity for adversarial setting between (I) Class Activation Map
(CAM) [12] and (II) Causal Effect Map (CEM) on ChestX-ray 14 for clinical
symptoms labels [26].

###  4.2 Other Image Classification Datasets

Fashion-MNIST The fashion-MNIST dataset comprises of 28$\times$28 grayscale
images of 70,000 fashion products from 10 categories, with 7,000 images per
category. [27]. We use shallow model consists of 2 convolutional layers. The
weights are trained using Adam with initial learning rate 0.001. We train the
model using minibatches of size 100. The classifier with lowest validation
loss has 89.6% accuracy.

Table 3: Expected-CE on Fashion-MNIST L, N | $Z_{0}$ |  $F_{i}$ = PWM |  $F_{j}$ = FGSM
---|---|---|---
2,3 | 4.9543$\times 10^{-4}$ | -1.8947$\times 10^{-5}$ | -8.0042$\times 10^{-6}$
2,7 | 2.4600$\times 10^{-4}$ | -4.1068$\times 10^{-5}$ | -2.5742$\times 10^{-5}$

ImageNet The ImageNet [28] 2012 classification dataset consists 1.2 million
images for training, and 50,000 for validation, from 1, 000 classes. As a
benchmark dataset, we use it to demonstrate visual causality. We use VGG16
model which has 16 convolutional layers and is pretrained by ImageNet with 86%
top-1 accuracy.

Table 4: Expected-CE on ImageNet L, N | $Z_{0}$ |  $F_{i}$ = PWM |  $F_{j}$ = FGSM
---|---|---|---
3,2 | 4.2027$\times 10^{-4}$ | 6.0993$\times 10^{-5}$ | -5.1834$\times 10^{-5}$
9,10 | 8.9322$\times 10^{-3}$ | 7.2438$\times 10^{-5}$ | \- 2.8862$\times 10^{-4}$
13,6 | 6.7643$\times 10^{-4}$ | 2.3943$\times 10^{-6}$ | -6.8749$\times 10^{-5}$

###  4.3 Evaluation of Causal Effect

To validate the reliability of our approach, we also implemented our causal
inference framework on Fashion-MNIST and ImageNet. We applied random pixel-
wise feature masking and adversarial noise separately to the input images with
$Z_{0}$ coded feature map. Table 3 and 4 show that comparing to $Z_{0}$,
Expected-CE of these two datasets decreased drastically once we applied random
masking and adversarial noise, which are similar to the results of CheXNet.
The results suggest that our causality framework is generic and can be applied
to different datasets (please refer our reproducible code.)

##  5 Conclusion

With our proposed framework, experimental results on Fashion-MNIST, ImageNet,
and ChestX-ray14 datasets show that CE is a competitive and robust index for
understanding DNNs for generic and human-interpretable feature(s) reasoning.
CE also shows high sensitivity in the presence of adversarial perturbations
and could be used to identify adversarial examples.

## References

  * [1] Serena Yeung, Olga Russakovsky, Greg Mori, and Li Fei-Fei,  “End-to-end learning of action detection from frame glimpses in videos,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 2678–2687.
  * [2] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger,  “Densely connected convolutional networks,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 4700–4708.
  * [3] Andre Esteva, Brett Kuprel, Roberto A Novoa, Justin Ko, Susan M Swetter, Helen M Blau, and Sebastian Thrun,  “Dermatologist-level classification of skin cancer with deep neural networks,”  Nature, vol. 542, no. 7639, pp. 115, 2017.
  * [4] Waqas Sultani, Chen Chen, and Mubarak Shah,  “Real-world anomaly detection in surveillance videos,”  Center for Research in Computer Vision (CRCV), University of Central Florida (UCF), 2018.
  * [5] Yingxu Wang,  “Deep reasoning and thinking beyond deep learning by cognitive robots and brain-inspired systems,”  in Cognitive Informatics & Cognitive Computing (ICCI* CC), 2016 IEEE 15th International Conference on. IEEE, 2016, pp. 3–3.
  * [6] Quanshi Zhang, Ying Nian Wu, and Song-Chun Zhu,  “Interpretable convolutional neural networks,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 8827–8836.
  * [7] Jan Philipp Albrecht,  “How the gdpr will change the world,”  Eur. Data Prot. L. Rev., vol. 2, pp. 287, 2016.
  * [8] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy,  “Explaining and harnessing adversarial examples,”  ICLR, 2015.
  * [9] Battista Biggio and Fabio Roli,  “Wild patterns: Ten years after the rise of adversarial machine learning,”  Pattern Recognition, vol. 84, pp. 317–331, 2018.
  * [10] Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin-Yu Chen, and Yupeng Gao,  “Is robustness the cost of accuracy?–a comprehensive study on the robustness of 18 deep image classification models,”  in ECCV, 2018, pp. 631–648.
  * [11] Judea Pearl,  Causality,  Cambridge university press, 2009.
  * [12] Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba,  “Learning deep features for discriminative localization,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 2921–2929.
  * [13] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra,  “Grad-cam: Visual explanations from deep networks via gradient-based localization,”  in 2017 IEEE International Conference on Computer Vision (ICCV). IEEE, 2017, pp. 618–626.
  * [14] Aaditya Prakash, Nick Moran, Solomon Garber, Antonella DiLillo, and James Storer,  “Deflecting adversarial attacks with pixel deflection,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 8571–8580.
  * [15] Anish Athalye, Nicholas Carlini, and David Wagner,  “Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples,”  ICML, 2018.
  * [16] Alexey Kurakin, Ian Goodfellow, and Samy Bengio,  “Adversarial examples in the physical world,”  arXiv preprint arXiv:1607.02533, 2016.
  * [17] Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva,  “Counterfactual fairness,”  in Advances in Neural Information Processing Systems, 2017, pp. 4066–4076.
  * [18] Michael Harradon, Jeff Druce, and Brian Ruttenberg,  “Causal learning and explanation of deep neural networks via autoencoded activations,”  arXiv preprint arXiv:1802.00541, 2018.
  * [19] Tanmayee Narendra, Anush Sankaran, Deepak Vijaykeerthy, and Senthil Mani,  “Explaining deep learning models using causal inference,”  arXiv preprint arXiv:1811.04376, 2018.
  * [20] Paul R Rosenbaum and Donald B Rubin,  “Assessing sensitivity to an unobserved binary covariate in an observational study with binary outcome,”  Journal of the Royal Statistical Society: Series B (Methodological), vol. 45, no. 2, pp. 212–218, 1983.
  * [21] Michael Goodfellow and Amanda L Jones,  “Laceyella,”  Bergey’s Manual of Systematics of Archaea and Bacteria, pp. 1–4, 2015.
  * [22] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami,  “Distillation as a defense to adversarial perturbations against deep neural networks,”  in 2016 IEEE Symposium on Security and Privacy (SP). IEEE, 2016, pp. 582–597.
  * [23] Karen Simonyan and Andrew Zisserman,  “Very deep convolutional networks for large-scale image recognition,”  arXiv preprint arXiv:1409.1556, 2014.
  * [24] Steve Branson, Catherine Wah, Florian Schroff, Boris Babenko, Peter Welinder, Pietro Perona, and Serge Belongie,  “Visual recognition with humans in the loop,”  in European Conference on Computer Vision. Springer, 2010, pp. 438–451.
  * [25] Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald Summers,  “Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases,”  in 2017 IEEE Conference on Computer Vision and Pattern Recognition(CVPR), 2017, pp. 3462–3471.
  * [26] Pranav Rajpurkar, Jeremy Irvin, Kaylie Zhu, Brandon Yang, Hershel Mehta, Tony Duan, Daisy Ding, Aarti Bagul, Curtis Langlotz, Katie Shpanskaya, et al.,  “Chexnet: Radiologist-level pneumonia detection on chest x-rays with deep learning,”  arXiv preprint arXiv:1711.05225, 2017.
  * [27] Han Xiao, Kashif Rasul, and Roland Vollgraf,  “Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms,”  arXiv e-prints, p. arXiv:1708.07747, Aug. 2017.
  * [28] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei,  “Imagenet: A large-scale hierarchical image database,”  in Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. Ieee, 2009, pp. 248–255.


#  OMG: Observe Multiple Granularities for Natural Language-Based Vehicle
Retrieval

Yunhao Du1111Equal contribution , Binyu Zhang1111Equal contribution ,
Xiangning Ruan1, Fei Su1,2, Zhicheng Zhao1,2222Corresponding authors, Hong
Chen3
1Beijing University of Posts and Telecommunications
2Beijing Key Laboratory of Network System and Network Culture, China
3China Mobile Research Institute
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Retrieving tracked-vehicles by natural language descriptions plays a critical
role in smart city construction. It aims to find the best match for the given
texts from a set of tracked vehicles in surveillance videos. Existing works
generally solve it by a dual-stream framework, which consists of a text
encoder, a visual encoder and a cross-modal loss function. Although some
progress has been made, they failed to fully exploit the information at
various levels of granularity. To tackle this issue, we propose a novel
framework for the natural language-based vehicle retrieval task, OMG, which
Observes Multiple Granularities with respect to visual representation, textual
representation and objective functions. For the visual representation, target
features, context features and motion features are encoded separately. For the
textual representation, one global embedding, three local embeddings and a
color-type prompt embedding are extracted to represent various granularities
of semantic features. Finally, the overall framework is optimized by a cross-
modal multi-granularity contrastive loss function. Experiments demonstrate the
effectiveness of our method. Our OMG significantly outperforms all previous
methods and ranks the 9th on the 6th AI City Challenge Track2. The codes are
available at https://github.com/dyhBUPT/OMG.

##  1 Introduction

With the development of the artificial intelligence technology, smart
transportation and city has elicited increasing attention in recent years.
Vehicle retrieval, which aims to retrieve tracked vehicles given a query,
occupies an important position. Most previous works solve this problem under a
purely visual setting, which try to identify the images or tracklets of the
same vehicle across different surveillance camera views [20, 23, 39]. However,
image-based setting limits its application scenarios, bacause an image query
is not always available. Comparatively speaking, Natural Language (NL)
descriptions can be one of the most convenient way to give a query [7].
Therefore, it is not trivial to develop an effective system for natural
language-based vehicle retrieval. Figure 1 gives example frames, bounding
boxes and corresponding descriptions from the CityFlow-NL dataset [7], which
is a large-scale benchmark for the text-based vehicle retrieval task.

Figure 1:  Visualization examples of the natural language-based vehicle
retrieval task. The query generally describes the color, type, motion state
and the relations (with neighbor objects) of the target vehicle.

Existing works tend to solve this task by using a dual-stream framework [8]
because of its flexibility and efficiency [22]. This framework consists of
separate visual encoder and text encoder to extract modal-specific
representations respectively and then computes their similarity. Then it is
optimized by InfoNCE loss [42], Instance loss [46], etc. Though these methods
have made some progress, they fail to mine adequate multi-granularity
information. For instance, the relationships between the target vehicle and
its neighbors is ignored in [1, 38, 37, 14], and [30, 36] fail to fully utilze
the color and type information. Moreover, they don’t take good advantage of
rich textual granular features.

In this paper, we propose OMG, which observes multiple granularities in an
unified framework. It follows the dual-stream architecture, that is, one
visual stream and one textual stream. The visual stream takes a cropped
vehicle image, a context image and a foreground motion map as input, and then
extracts their features by three individual image encoders. As for the textual
stream, one global text, three local texts and one prompt are encoded
separately by five tied text encoders. While training, a multi-granularity
InfoNCE loss is applied to perform cross-modal contrastive learning between
them. Furthermore, an ID loss is also used for the visual stream for more
discriminative representation.

Extensive experiments verify the effectiveness of our proposed methods. To be
specific, by taking ”ResNet50 + BERT + InfoNCE” as baseline [10, 41, 42], a
series of proposed optimization strategies boost its performance by 144% on
the validation set (MRR from 0.208 to 0.507). Entries based on the presented
methodology ranks the 9th on the AI CIty Challenge 2022 Track2. The
contributions of this work are summarized as follows:

1) We propose a novel framework for the natural language-based vehicle
retrieval task, which fully exploits the multi-granularity information in a
joint manner.

2) Various optimization tricks are employed to further improve the
representation capability of the network, i.e., auxiliary ID loss,
backtranslation-based text augmentation, stronger image and text encoders [24,
35].

3) Extensive experiments prove the effectiveness of our method.

Figure 2:  Framework of the proposed OMG, which consists of a visual stream
and a textual stream. For the visual stream, it takes a cropped target image,
a context image and a 4-channel foreground motion map as input, and encodes
them into a target feature $f^{i}_{t}$, a context feature $f^{i}_{c}$ and a
motion feature $f^{i}_{m}$ respectively. As to the textual stream, it embdes
one global feature $f^{t}_{g}$, three local features $f^{t}_{l}$ and one
prompt feature $f^{t}_{p}$ from different granularity of textual inputs. The
overall framework is optimized with a multi-granularity InfoNCE loss and an ID
loss in an end-to-end manner.

##  2 Related Works

###  2.1 Text-based Video Retrieval

Text-based video retrieval aims to search the corresponding video via the
given text description among a number of videos. Due to its great range of
potential applications, it has received wide attention by the researchers. The
most of existing methods adopt contrastive learning to train a network which
can estimate the similarity between the video and the text descriptions. They
take both video and text descriptions as input, and then extract the video
features and text features via the modal encoders. They tend to update the
networks by minimizing the distance between each pair of the video-text
features. Due to the difference of the modality and limitation of the network,
the early methods [29, 28, 18] usually use a dual-stream framework, which can
reduce the computational complexity. These works encode the video by the
visual feature extractor (C3D[40], I3D [2], etc.) and encode the text by the
textual feature extractor (LSTM [11], GRU [4], etc.), and then estimate the
video-text similarity in a potential semantic space.

Recently, with the successful migration of Transformer [43] from natural
language processing to computer vision, (ViT [5], Swin-Transformer [24],
etc.), the mainstream methods [26, 17, 16, 22, 6, 35, 9, 45, 44, 19] on video-
language retrieval tasks begin to utilize Transformer as encoders for both of
the video and the natural language. HERO [17] and ALPRO [16] explore to boost
the video-text alignment via the large-scale pre-training tasks. HiT [22]
further proposed a hierarchical model with momentum contrast for video-text
retrieval. Also, some single-stream networks come out, due to the consistency
of the Transformer encoders structure. ViLBERT [26] firstly explore to utilize
a single-stream Transformer network to retrieve the video based on natural
language descriptions, which also attempts to align the corresponding video
and text features in the potential semantic space. Further, due to the success
of CLIP [35], which demonstrates the powerful performance of image-text
contrastive learning, many researchers conduct experiments on the basis of
CLIP. Besides, CLIP2Video [6] extends CLIP from image-text retrieval to video-
text retrieval. Moreover, MFGATN [9], TACo [45], HANet [44] and FeatInter [19]
also achieve good performance in the video-text retrieval tasks by designing
different modules to enhance the comprehension of the video-text pair.

###  2.2 Text-based Vehicle Retrieval

AYCE [36] proposes a modular solution which applies BERT [41] to embed textual
descriptions and a CNN [10] with a Transformer model [43] to embed visual
information. SBNet [15] presents a substitution module that helps project
features from different domains into the same space, and a future prediction
module to learn temporal information by predicting the next frame. Pirazh et
al. [14] and Tam et al. [30] adopts CLIP [35] to extract frame features and
textual features. TIED [37] proposes an encoder-decoder based model in which
the encoder embeds two modalities into the common space and the decoder
jointly optimizes these embeddings by an input-token-reconstrucion task. Tien-
Phat et al. [31] adapts COOT [8] to model the cross-modal relationships with
both appearance and motion attributes. Eun-Ju et al. [33] propose to perform
color and type classification for both target and front-rear vehicles, and
conduct movement analysis based on the Kalman filter algorithm [13]. DUN [38]
uses pretrained CNN and GloVe [34] to extract modal-specific features and GRUs
[3] to exploit temporal information. CLV [1] proposes the simple and effective
global motion image, which is jointly encoded with the cropped image and
language description, and ranks first on the AI City Challenge 2021 Track5.

Though these methods have achieved promising results on the CityFlow-NL
benchmark, they don’t utilze omni-features adequately. Differently, our method
can mine rich information from multiple granularities, which helps extract
more discriminative features.

##  3 Method

In this section, we present the details of the OMG framework as shown in
Figure 2. Specifically, we start with the visual stream in Section 3.1, and
then introduce the textual stream in Section 3.2. Finally, Section 3.3
illustrates the multi-granularity InfoNCE loss and the auxiliary ID loss.

###  3.1 Multi-Granularity Visual Stream

For the visual stream, three granularities of images are inputed into image
encoders to extract features respectively. Note that these three encoders
don’t share weights.

Target Features. Given a trajectory of the target vehicle, a frame is sampled
and the target image is cropped according to the bounding box. Then it is
taken as the input to generate the target feature $f^{i}_{t}$. By setting a
high resolution, the network can focus on the details and implicitly encode
the appearance information, e.g., color and type.

Context Features. The target feature only contains the target vehicle’s own
information by excluding the background, ignoring the relationship between
neighbors. Instead, we extend the original bounding box $[x,y,w,h]$ to
$[x-w,y-h,3w,3h]$ to crop the context image around the target vehicle. It has
a larger receptive field and can usually include nearby vehicles, which helps
the encoder embed the relation information and predict the context feature
$f^{i}_{c}$.

Motion Features. Another vital information is the motion pattern of the target
vehicle. Inspired by the background modeling based motion image in [1], we
propose a 4-channel foreground motion map, which consists of a 3-channel
foreground cropped image and a single channel motion image. For the former
one, the whole trajectory of the target vehicle is cropped and pasted into a
black image. Note that we only keep the bounding boxes that don’t overlap too
much. For the latter one, the center positions of these bounding boxes are
used to form a thick trajectory line. Finally, these two images are
concatenated along the channel dimension and taken as the input of the image
encoder. It’s encoded into the motion feature $f^{i}_{m}$, which contains both
coarse appearance and motion information simutaneously.

Figure 3:  The illustration of the color-type prompt generation process, which
consists of three steps, i.e., dependency parsing, voting and prompt
generation. Note that we only visualize the dependency parsing results of one
sentence for simplicity, i.e., ”A blue wagon going straight down the street
passing an intersection”.

###  3.2 Multi-Granularity Textual Stream

Similar with the visual stream, the textual stream also contains three
granularities of inputs, i.e., the global text, the local texts and the color-
type prompt. The notable difference between these two streams is that the
weights of all text encoders are shared and freezed except for the last fully
connected layer.

Global Features. Every trajectory corresponds to three unique natural language
sentences. The descriptions of these sentences would have different emphases.
For example, some may focus on the appearance and motion information (e.g., A
black sedan makes a right turn at the intersection.), and others may contain
the relation information (e.g., A white SUV switches to the left lane followed
by another white vehicle.). In order to comprehensively consider them, an
intuitive and simple way is to concatenate these three sentences into an
unified one, termed the global text. The extracted global feature $f^{t}_{g}$
from it includes rich semantic information from a global view.

Local Features. Though the global feature embeds the integrated semantics, it
is too coarse to focus on details. To make the network pay attention to more
fine-grained information, we also input the three sentences into the network
respectively to predict three local features
$f^{t}_{l1},f^{t}_{l2},f^{t}_{l3}$. Different from $f^{t}_{g}$, the
$f^{t}_{l*}$ places more emphasis on some specific features, e.g., appearance,
motion and relation.

Prompt Features. The appearance would be the most vital information to
distinguish different vehicles. Inspired by the prompt learning in Natural
Language Processing (NLP) [21], we design a color-type prompt for better
appearance representation. The prompt generation process is illustrated in the
Figure 3. Specifically, the color and type of the vehicle are extracted from
each sentence first by using a dependency parser [12]. Then the final color
and type are determined by a simple voting mechanism (”gray” and ”SUV” in the
figure). Finally, the color-type prompt is generated by the template ”This is
a [COLOR] [TYPE]”, e.g., ”This is a gray SUV” in this example. By using this
simple and intuitive prompt as input and predicting the prompt feature
$f^{t}_{p}$, it is easier to focus on the appearance information for the text
encoder.

Table 1:  Ablation study of OMG on the validation set. “↑” means higher is
better.

| Method | BoT | Context | Motion | Local | Prompt | CLIP | NLAug | IDLoss | Swin | MFT | MRR(↑) | R@5(↑) | R@10(↑)
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
| Baseline |  |  |  |  |  |  |  |  |  |  | 0.208 | 0.269 | 0.363
|  | ✓ |  |  |  |  |  |  |  |  |  | 0.218 | 0.285 | 0.382
|  | ✓ | ✓ |  |  |  |  |  |  |  |  | 0.228 | 0.315 | 0.422
|  | ✓ | ✓ | ✓ |  |  |  |  |  |  |  | 0.204 | 0.263 | 0.435
|  | ✓ |  |  | ✓ |  |  |  |  |  |  | 0.241 | 0.333 | 0.457
|  | ✓ |  |  | ✓ | ✓ |  |  |  |  |  | 0.273 | 0.384 | 0.505
|  | ✓ | ✓ |  | ✓ | ✓ |  |  |  |  |  | 0.285 | 0.411 | 0.556
|  | ✓ | ✓ |  | ✓ | ✓ | ✓ |  |  |  |  | 0.316 | 0.435 | 0.586
|  | ✓ | ✓ |  | ✓ | ✓ | ✓ | ✓ |  |  |  | 0.401 | 0.567 | 0.723
|  | ✓ | ✓ |  | ✓ | ✓ | ✓ | ✓ | ✓ |  |  | 0.438 | 0.591 | 0.750
|  |  | ✓ |  | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |  | 0.490 | 0.672 | 0.790
| OMG |  | ✓ |  | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 0.507 | 0.667 | 0.812

###  3.3 Multi-Granularity Loss

InfoNCE loss [42] is a widely used objective function for contrastive
learning, which is then extended to cross-modal tasks. In this work, we apply
it to our cross-modal multi-granularity framework and name it Multi-
Granularity InfoNCE loss. Given a batch with $M$ text-vehicle pairs
$\\{(t_{i},v_{i})\\}_{i=1}^{M}$, we first extract their multi-granularity
features. Particularly, every $t_{i}$ is embedded into $N_{t}$ features
$\\{t_{i}^{j}\\}_{j=1}^{N_{t}}$ and every $v_{i}$ is embedded into $N_{v}$
features $\\{v_{i}^{k}\\}_{k=1}^{N_{v}}$, where $N_{t}=5$ and $N_{v}=3$ in
this work. Then the multi-granularity InfoNCE loss from text to image is:

$L_{info}^{t2i}={1\over{MN_{t}N_{v}}}\sum^{M}_{i=1}\sum^{N_{t}}_{j=1}\sum^{N_{v}}_{k=1}log({{e^{s(t^{j}_{i},v^{k}_{i})/\tau}}\over{\sum^{M}_{n=1}e^{s(t^{j}_{i},v^{k}_{n})/\tau}}}),$
(1)

where $\tau$ denotes a learnable temperature parameter and $s(\cdot,\cdot)$
measures the cosine similarity as:

$s(u,v)={{u^{T}v}\over{||u||\ ||v||}}.$ (2)

Similarly, the image-to-text one is:

$L_{info}^{i2t}={1\over{MN_{t}N_{v}}}\sum^{M}_{i=1}\sum^{N_{t}}_{j=1}\sum^{N_{v}}_{k=1}log({{e^{s(v^{k}_{i},t^{j}_{i})/\tau}}\over{\sum^{M}_{n=1}e^{s(v^{k}_{i},t^{j}_{n})/\tau}}}).$
(3)

Finally, the whole multi-granularity InfoNCE loss is:

$L_{info}=(L_{info}^{t2i}+L_{info}^{i2t})/2.$ (4)

Though $L_{info}$ can help improve the representational ability in a
contrastive learning manner, it treats all samples as the negatives except
that in the anchor pair. However, some vehicles from different text-vehicle
pairs have the same ID. To be specific, there are 2,155 pairs in the traning
set of the CityFlow-NL dataset [7], but they are from $C=482$ vehicles from
different views. It would deteriorate the feature learning by treating these
vehicles with the smae ID as negative samples, especially for the image
encoders. For that reason, we introduce the cross-entropy loss on the multi-
granularity visual features $\\{v_{i}^{k}\\}_{k=1}^{N_{v}}$ as an auxiliary ID
loss. Given a vehicle $v_{i}$, we denote $y_{i}$ as the truth ID label and
$p_{i,c}^{k}$ as the ID prediction logits of class $c$ for granularity $k$.
The ID loss is computed as follows:

$L_{id}={1\over{MN_{v}}}\sum^{M}_{i=1}\sum^{C}_{c=1}\sum^{N_{v}}_{k=1}-q_{c}log(p_{i,c}^{k}),$
(5)

where $q_{c}=1$ if $y_{i}=c$, otherwise $q_{c}=0$.

Finally, the overall objective function is formulated as:

$L_{OMG}=\lambda_{1}L_{info}+\lambda_{2}L_{id},$ (6)

where $\lambda_{1},\lambda_{2}$ are the weights for the two losses. We set
$\lambda_{1}=1,\lambda_{2}=1$ in our experiments.

##  4 Experiments

###  4.1 Dataset and Evaluation

We use the CityFlow-NL dataset [7] to train and evaluate our model, and it is
extended from the CityFlow benchmark [39] by annotating natural language
descriptions for vehicle targets. It is the first city-scale multi-target
multi-camera tracking with natural language descriptions dataset that provides
precise descriptions for multi-view ground truth vehicle tracks. The CityFlow-
NL dataset consists of 666 targets vehicles in 3,028 single-view tracks and
5,289 unique NL descriptions. For the AI City Challenge, the dataset contains
2,498 tracks of vehicles with three descriptions. 530 unique vehicle tracks
together with 530 query sets each with three descriptions are curated for this
challenge.

The natural language-based vehicle retrieval task uses the Mean Reciprocal
Rank (MRR) as the main evaluation metric. Specifically, the reciprocal rank of
a query response is the multiplicative inverse of the rank of the first
correct answer. The mean reciprocal rank is the average of the reciprocal
ranks of the overall test set:

$MRR={1\over N}\sum^{N}_{i=1}{1\over{rank_{i}}},$ (7)

where $rank_{i}$ is the rank position of the first correct answer for the
$i$-th query. Besides, Recall@5 and Recall@10 are also evaluated.

###  4.2 Implement Details

In the training phase, we train OMG with batch size 24 on three 16G Tesla T4
GPUs. For the visual stream, we first randomly sample a frame from the target
trajectory. Then the input images are resized to 384 $\times$ 384\. RandomCrop
and RandomApply are used to perform data augmentation. For the textual stream,
the backbone is freezed except the last fully connected layer. The cosine
annealing strategy is used with a base learning rate 6.7e-3 and a minimum
learning rate 6.7e-6. The network is trained with the AdamW [25] optimizer for
600 epochs with 300 warm-up epochs.

While inference, the middle frame of the trajectory is sampled as the input of
the visual stream. All $N_{t}N_{v}$ pairs of cross-modal multi-granularity of
features are used to compute pairwise similarities. Then they are simply
averaged for the final similarity prediction.

Table 2:  Ablation study of the OSG on the validation set. ”↑” means higher is
better.

| Method | NLAug | Color | Type | CLIP | ID | Motion | Swin | MRR(↑) | R@5(↑) | R@10(↑)
---|---|---|---|---|---|---|---|---|---|---|---
| Baseline |  |  |  |  |  |  |  | 0.208 | 0.269 | 0.363
|  | ✓ |  |  |  |  |  |  | 0.212 | 0.293 | 0.401
|  | ✓ | ✓ |  |  |  |  |  | 0.222 | 0.312 | 0.401
|  | ✓ | ✓ | ✓ |  |  |  |  | 0.224 | 0.280 | 0.422
|  | ✓ | ✓ |  | ✓ |  |  |  | 0.326 | 0.433 | 0.566
|  | ✓ | ✓ |  | ✓ | ✓ |  |  | 0.345 | 0.487 | 0.626
|  | ✓ | ✓ |  | ✓ | ✓ | ✓ |  | 0.380 | 0.505 | 0.621
| OSG | ✓ | ✓ |  | ✓ | ✓ | ✓ | ✓ | 0.441 | 0.567 | 0.685

###  4.3 Ablation Study

In this section, we summarize the ablation study of our method. First, we
conduct the ablation experiments for our OMG model, which has been introduced
previously. Moreover, we also present a single-granularity model, named OSG
(Observe Single Granularity) for the ensemble.

Ablation of OMG. Table 1 shows the ablation study of our OMG. The baseline is
a dual-stream architecture with ResNet50 [10], BERT [26] and InfoNCE loss
[42]. Only the target image and the global text are used as input for the
visual stream and textual stream respectively. Other optimization strategies
are illustrated as follows:

  * •

BoT: Pre-training a ReID model BoT [27] on Track1 with ResNet50-IBN [32] as
the backbone to replace the original image encoder. Experiments shows that the
stronger visual encoder brings 0.01 improvement for MRR.

  * •

Context: Taking the context image as the input to extract context features.
With the help of the context information, all metrics MRR, R@5 and R@10
improve.

  * •

Motion: Taking the motion image as the input to extract motion features. The
use of the foreground motion image doesn’t boost the performance, perhaps
beacuse of the too rough appearance information in it. Therefore, we discard
it in the future version of our framework.

  * •

Local: Adding three local texts as the input of the textual stream. Finer
granularities of textual descriptions improve the performance by a large
margin (from 0.218 to 0.241).

  * •

Prompt: Adding the prompt text as the input of the textual stream. Though its
simplicity, this simple color-type prompt boosts the performance
significantly.

  * •

CLIP: Replacing the text encoder BERT with the textual stream of CLIP [35].
The improvements can be attributed to its excellent ability of modal
alignment.

  * •

NLAug: Data augmentation with the backtranslation method for the natural
language data. We can observe a huge gap between the effect of $NLAug$ for OMG
and OSG (in Table 2). Specifically, it improves the MMR of OMG by 0.085 (from
0.316 ro 0.401), but only 0.004 for OSG (from 0.208 to 0.212). The reason
behind the gap is that the multi-granularity architecture makes better use of
the augmented data.

  * •

IDLoss: Applying the auxiliary ID loss. The ID loss helps the image encoder
achieve more robust representation ability and improves the retrieval
performance.

  * •

Swin: Replacing the image encoder ResNet50 with the Swin-Transformer-B [24]. A
stronger architecture of the image encoder further boosts the performance.

  * •

MFT: Multi-frame testing, i.e., sampling uniformly 8 frames for the target
trajectory to generate the mean features instead of only one frame.
Experiments proves its effectiveness.

Ablation of OSG. We also conduct various experiments on a single granularity
model (OSG) with different modules, as illustrated in Table 2. It has the same
baseline with OMG. The ”NLAug” denotes the same natural language augmentation
in Table 1, which can also improve the performance of OSG slightly. The terms
”Color”, ”Type” and ”ID” indicate that we utilize additional classification
heads to classify the color, type and ID of the vehicle. As shown in the Table
2, the color and ID supervision gains a relative MRR improvement which
demonstrates the effectiveness of the supervision for the vehicle properties.
However, the type of the vehicle can hardly help the OSG perform better. We
infer this is due to the variety descriptions of vehicle type for the same
target, such as ”truck”, ”pickup”, ”hatchback”, etc., which may lead to
confusion. We also replace BERT with the text encoder of CLIP, and replace
ResNet50 with Swin-Transformer, which gives a great boost to our model. To get
the correct and representative motion information from the annotation, we
first filter out the bounding box if its IoU is greater than 0.9 with the box
in the previous frames. Then we uniformly sample 16 boxes from the remaining
ones. At last, it is inputed into a GRU [4] to embed the motion features in
the potential semantic space. The introduction of motion information enhances
the model performance, which indicates the motion information plays an
important role in this task.

Figure 4:  Sample retrieval results visualization of our OMG on the test set
of the CityFlow-NL dataset. Only the rank 1 3 results are listed and only 3
frames are sampled for each trajectory. The image is cropped for clarity. The
target vehicle retrieved are marked with green bounding boxes. It’s shown that
our model has a certain semantic understanding ability.

###  4.4 Evaluation Results

Quantitative Results. We compare our OMG with previous state-of-the-art
methods in Table 3. It is shown that our method surpasses them by a large
margin. Specifically, our method is 61.1% better than the last year’s winning
team, i.e., 0.3012 vs. 0.1869. Table 4 lists the top-15 team results on the AI
City 2022 Challenge Track2 and we rank the 9th palce. Note that the final
submission are the ensemble results from both OMG and OSG (in Section 4.3)

Qualitative Results. Figure 4 visualizes the retrieval results of OMG on the
test set of the CityFlow-NL dataset. Only the top-3 results are listed here.

Table 3:  Comparision with previous methods.

| Team | MRR
---|---|---
| OMG(ours) | 0.3012
| Alibaba-UTS-ZJU [1] | 0.1869
| SDU-XidianU-SDJZU [38] | 0.1613
| SUNYKorea [33] | 0.1594
| Sun Asterisk [30] | 0.1571
| HCMUS [31] | 0.1560
| TUE [37] | 0.1548
| JHU-UMD [14] | 0.1364
| Modulabs-Naver-KookminU [15] | 0.1195
| Unimore [36] | 0.1078

Table 4:  The leaderboard of the 6th AI City Challenge Track2.

| Rank | Team | MRR
---|---|---|---
| 1 | Must Win | 0.6606
| 2 | Thursday | 0.5251
| 3 | HCMIU-CVIP | 0.4773
| 4 | MegVideo | 0.4392
| 5 | HCMUS | 0.3611
| 6 | P & L | 0.3338
| 7 | Terminus-AI | 0.3320
| 8 | MARS_WHU | 0.3205
| 9 | BUPT_MCPRL_T2(ours) | 0.3012
| 10 | folklore | 0.2832
| 11 | HYFL | 0.2804
| 12 | alpha | 0.2802
| 13 | SEEE-HUST | 0.2333
| 14 | ETRI_AIA | 0.0389
| 15 | Pair Lab | 0,0216

###  4.5 Limitations

Our OMG still has several limitations. First of all, though it can mine rich
information from multiple granularities, we simply average the similarities
between different cross-modal pairs. Improving the mechanism for fusing these
multi-granularity features is expected to bring significant improvements,
e.g., using the self-attention mechanism [43]. Besides, the leverage of the
motion and relation information should be further improved. The temporal
information is also underutilized. Data augmentation is vital for
representation learning, which should be studied further. Last but not least,
the cross-modal alignment problem is not trivial for the text-vision retrieval
task, which is not given enough attention in this work. A more effective
architecture or alignment mechanism would help boost the retrieval
performance.

##  5 Conclusion

In this paper, we propose a novel framework for the natural language-based
vehicle retrieval task, named OMG. It follows the dual-stream paradigm, which
consists of a multi-granularity visual stream and a multi-granularity textual
stream. By focusing on three-granularity of visual information (target,
context, motion) and three-granularity of textual information (global, local,
prompt), our model can mine rich semantics jointly with a multi-granularity
InfoNCE loss and an auxiliary ID loss. With some optimization tricks, our
method improves the performance of the baseline by 144% on the validation set.
On the test set, OMG outperforms all previous methods by a large margin and
ranks 9th on the 6th AI City Challenge Track2.

In the future, we will focus on discriminative representation learning and
cross-modal alignment.

##  6 Acknowledgements

This work is supported by Chinese National Natural Science Foundation under
Grants (62076033, U1931202) and MoE-CMCC ”Artifical Intelligence” Project
No.MCM20190701.

## References

  * [1] Shuai Bai, Zhedong Zheng, Xiaohan Wang, Junyang Lin, Zhu Zhang, Chang Zhou, Hongxia Yang, and Yi Yang.  Connecting language and vision for natural language-based vehicle retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4034–4043, 2021.
  * [2] Joao Carreira and Andrew Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6299–6308, 2017.
  * [3] Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio.  On the properties of neural machine translation: Encoder-decoder approaches.  arXiv preprint arXiv:1409.1259, 2014.
  * [4] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  arXiv preprint arXiv:1406.1078, 2014.
  * [5] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [6] Han Fang, Pengfei Xiong, Luhui Xu, and Yu Chen.  Clip2video: Mastering video-text retrieval via image clip.  arXiv preprint arXiv:2106.11097, 2021.
  * [7] Qi Feng, Vitaly Ablavsky, and Stan Sclaroff.  Cityflow-nl: Tracking and retrieval of vehicles at city scale by natural language descriptions.  arXiv preprint arXiv:2101.04741, 2021.
  * [8] Simon Ging, Mohammadreza Zolfaghari, Hamed Pirsiavash, and Thomas Brox.  Coot: Cooperative hierarchical transformer for video-text representation learning.  Advances in neural information processing systems, 33:22605–22618, 2020.
  * [9] Xiaoshuai Hao, Yucan Zhou, Dayan Wu, Wanqian Zhang, Bo Li, and Weiping Wang.  Multi-feature graph attention network for cross-modal video-text retrieval.  In Proceedings of the 2021 International Conference on Multimedia Retrieval, pages 135–143, 2021.
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [11] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [12] Matthew Honnibal and Mark Johnson.  An improved non-monotonic transition system for dependency parsing.  In Proceedings of the 2015 conference on empirical methods in natural language processing, pages 1373–1378, 2015.
  * [13] Rudolph Emil Kalman.  A new approach to linear filtering and prediction problems.  1960\.
  * [14] Pirazh Khorramshahi, Sai Saketh Rambhatla, and Rama Chellappa.  Towards accurate visual and natural language-based vehicle retrieval systems.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4183–4192, 2021.
  * [15] Sangrok Lee, Taekang Woo, and Sang Hun Lee.  Sbnet: Segmentation-based network for natural language-based vehicle search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4054–4060, 2021.
  * [16] Dongxu Li, Junnan Li, Hongdong Li, Juan Carlos Niebles, and Steven CH Hoi.  Align and prompt: Video-and-language pre-training with entity prompts.  arXiv preprint arXiv:2112.09583, 2021.
  * [17] Linjie Li, Yen-Chun Chen, Yu Cheng, Zhe Gan, Licheng Yu, and Jingjing Liu.  Hero: Hierarchical encoder for video+ language omni-representation pre-training.  arXiv preprint arXiv:2005.00200, 2020.
  * [18] Xirong Li, Jianfeng Dong, Chaoxi Xu, Jing Cao, Xun Wang, and Gang Yang.  Renmin university of china and zhejiang gongshang university at trecvid 2018: Deep cross-modal embeddings for video-text retrieval.  In TRECVID, 2018.
  * [19] Baolong Liu, Qi Zheng, Yabing Wang, Minsong Zhang, Jianfeng Dong, and Xun Wang.  Featinter: Exploring fine-grained object features for video-text retrieval.  Neurocomputing, 2022.
  * [20] Hongye Liu, Yonghong Tian, Yaowei Yang, Lu Pang, and Tiejun Huang.  Deep relative distance learning: Tell the difference between similar vehicles.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2167–2175, 2016.
  * [21] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  arXiv preprint arXiv:2107.13586, 2021.
  * [22] Song Liu, Haoqi Fan, Shengsheng Qian, Yiru Chen, Wenkui Ding, and Zhongyuan Wang.  Hit: Hierarchical transformer with momentum contrast for video-text retrieval.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11915–11925, 2021.
  * [23] Xinchen Liu, Wu Liu, Tao Mei, and Huadong Ma.  A deep learning-based approach to progressive vehicle re-identification for urban surveillance.  In European conference on computer vision, pages 869–884. Springer, 2016.
  * [24] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10012–10022, 2021.
  * [25] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [26] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  Advances in neural information processing systems, 32, 2019.
  * [27] Hao Luo, Wei Jiang, Youzhi Gu, Fuxu Liu, Xingyu Liao, Shenqi Lai, and Jianyang Gu.  A strong baseline and batch normalization neck for deep person re-identification.  IEEE Transactions on Multimedia, 22(10):2597–2609, 2019.
  * [28] Niluthpol Chowdhury Mithun, Juncheng Li, Florian Metze, and Amit K Roy-Chowdhury.  Learning joint embedding with multimodal cues for cross-modal video-text retrieval.  In Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval, pages 19–27, 2018.
  * [29] Niluthpol Chowdhury Mithun, Juncheng B Li, Florian Metze, Amit K Roy-Chowdhury, and Samarjit Das.  Cmu-ucr-bosch@ trecvid 2017: Video to text retrieval.  In TRECVID, 2017.
  * [30] Tam Minh Nguyen, Quang Huu Pham, Linh Bao Doan, Hoang Viet Trinh, Viet-Anh Nguyen, and Viet-Hoang Phan.  Contrastive learning for natural language-based vehicle retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4245–4252, 2021.
  * [31] Tien-Phat Nguyen, Ba-Thinh Tran-Le, Xuan-Dang Thai, Tam V Nguyen, Minh N Do, and Minh-Triet Tran.  Traffic video event retrieval via text query using vehicle appearance and motion attributes.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4165–4172, 2021.
  * [32] Xingang Pan, Ping Luo, Jianping Shi, and Xiaoou Tang.  Two at once: Enhancing learning and generalization capacities via ibn-net.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 464–479, 2018.
  * [33] Eun-Ju Park, Hoyoung Kim, Seonghwan Jeong, Byungkon Kang, and YoungMin Kwon.  Keyword-based vehicle retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4220–4227, 2021.
  * [34] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014.
  * [35] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International Conference on Machine Learning, pages 8748–8763. PMLR, 2021.
  * [36] Carmelo Scribano, Davide Sapienza, Giorgia Franchini, Micaela Verucchi, and Marko Bertogna.  All you can embed: Natural language based vehicle retrieval with spatio-temporal transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4253–4262, 2021.
  * [37] Clint Sebastian, Raffaele Imbriaco, Panagiotis Meletis, Gijs Dubbelman, Egor Bondarev, et al.  Tied: A cycle consistent encoder-decoder model for text-to-image retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4138–4146, 2021.
  * [38] Ziruo Sun, Xinfang Liu, Xiaopeng Bi, Xiushan Nie, and Yilong Yin.  Dun: Dual-path temporal matching network for natural language-based vehicle retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4061–4067, 2021.
  * [39] Zheng Tang, Milind Naphade, Ming-Yu Liu, Xiaodong Yang, Stan Birchfield, Shuo Wang, Ratnesh Kumar, David Anastasiu, and Jenq-Neng Hwang.  Cityflow: A city-scale benchmark for multi-target multi-camera vehicle tracking and re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8797–8806, 2019.
  * [40] Du Tran, Lubomir Bourdev, Rob Fergus, Lorenzo Torresani, and Manohar Paluri.  Learning spatiotemporal features with 3d convolutional networks.  In Proceedings of the IEEE international conference on computer vision, pages 4489–4497, 2015.
  * [41] Iulia Turc, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Well-read students learn better: On the importance of pre-training compact models.  arXiv preprint arXiv:1908.08962, 2019.
  * [42] Aaron Van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  arXiv e-prints, pages arXiv–1807, 2018.
  * [43] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [44] Peng Wu, Xiangteng He, Mingqian Tang, Yiliang Lv, and Jing Liu.  Hanet: Hierarchical alignment networks for video-text retrieval.  In Proceedings of the 29th ACM International Conference on Multimedia, pages 3518–3527, 2021.
  * [45] Jianwei Yang, Yonatan Bisk, and Jianfeng Gao.  Taco: Token-aware cascade contrastive learning for video-text alignment.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11562–11572, 2021.
  * [46] Zhedong Zheng, Liang Zheng, Michael Garrett, Yi Yang, Mingliang Xu, and Yi-Dong Shen.  Dual-path convolutional image-text embeddings with instance loss.  ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 16(2):1–23, 2020.


# Wavefield recovery with limited-subspace weighted matrix factorizations

Yijun Zhang1, Shashin Sharan2, Oscar Lopez4, Felix J. Herrmann1,2,3
1 Department of Electrical & Computer Engineering, Georgia Institute of
Technology
2 Department of Earth & Atmospheric Sciences, Georgia Institute of Technology
3 School of Computational Science and Engineering, Georgia Institute of
Technology
4 Optimization and Uncertainty Quantification, Sandia National Laboratories

###### Abstract

Modern-day seismic imaging and monitoring technology increasingly rely on
dense full-azimuth sampling. Unfortunately, the costs of acquiring densely
sampled data rapidly become prohibitive and we need to look for ways to
sparsely collect data, e.g. from sparsely distributed ocean bottom nodes, from
which we then derive densely sampled surveys through the method of wavefield
reconstruction. Because of their relatively cheap and simple calculations,
wavefield reconstruction via matrix factorizations has proven to be a viable
and scalable alternative to the more generally used transform-based methods.
While this method is capable of processing all full azimuth data frequency by
frequency slice, its performance degrades at higher frequencies because
monochromatic data at these frequencies is not as well approximated by low-
rank factorizations. We address this problem by proposing a recursive recovery
technique, which involves weighted matrix factorizations where recovered
wavefields at the lower frequencies serve as prior information for the
recovery of the higher frequencies. To limit the adverse effects of potential
overfitting, we propose a limited-subspace recursively weighted matrix
factorization approach where the size of the row and column subspaces to
construct the weight matrices is constrained. We apply our method to data
collected from the Gulf of Suez, and our results show that our limited-
subspace weighted recovery method significantly improves the recovery quality.

##  1 Introduction

Seismic data acquisition plays a key role in the initial phase of oil & gas
exploration. It also represents a significant budget item for monitoring of
carbon sequestration. For these reasons, it is a challenge to come up with new
acquisition methodologies that improve acquisition productivity [Mosher et
al., 2014] without sacrificing data quality. Randomized acquisition according
to the principles of compressive sensing [Herrmann et al., 2012] in
combination with large-scale wavefield reconstruction algorithms [Kumar et
al., 2015] has proven a viable tool to improve the acquisition productivity
both in marine and land seismic settings.

So far, many of the employed approached of wavefield reconstruction are based
transform-domain sparsity, which is deigned to explore local smoothness
typically in small windows in up to five dimensions. While these approaches
have been applied successfully on production data, they do no exploit
redundancies present in the data over long distances. Recovery techniques
based on low-rank matrix factorizations [Kumar et al., 2015] do not suffer
from this shortcoming because this method works with monochromatic frequency
slices that contain data from the complete survey instead of working within
small windows limiting the apperture. By organizing the data in the
appropriate domain, e.g. midpoint-offset domain for seismic lines,
monochromatic frequency slices permit approximations in low-rank form, which
can be used to recover fully sample wavefields from subsampled data.

While low-rank factorizations have been employed successfully for low and
midrange frequencies, their performance deteriorates at high frequencies
because monochromatic frequency slices can no longer be approximated
accurately by low-rank factorizations. In this work, we overcome this problem
by using the fact that factorizations at neighboring frequencies live in
close-by subspaces. As described in early work by Aravkin et al. [2013];
Eftekhari et al. [2018], this property can be exploited by introducing matrix
weights defined in terms of factorizations of near-by frequency slices. Recent
work by Zhang et al. [2019] took this initial a step further by proposing a
recursive approach where factorizations of frequency slices at lower
frequencies are used as weight for factorizations at the higher frequencies
starting at the low frequencies and working its way up.

While this approach has had some success (see e.g. Zhang et al. [2019]), there
is challenge related to the fact that high frequencies require higher rank
factorizations and this can lead to overfitting when using this higher rank
throughout. We avoid this overfitting, by adapting the rank of the weighting
matrices such that overfitting is avoided. We do this by actively limiting the
row and column subspaces of the weight matrices. Because we avoid overfitting,
we are able to further improve the wavefield recovery. We also introduce an
alternative formulation where the weight matrices are moved from the
constraint, as in Kumar et al. [2015], to the data misfit objective, which
leads to a significant improvement ($20$ to $25$ times speedup) computational
efficiency.

We organize our paper as follows. First, we review the recursively weighted
wavefield recovery via matrix factorization including the new formulation
where the weight appear in the data misfit term. Next, we discuss how to limit
the subspace of our weighted matrix factorizations. We conclude by
demonstrating our approach on a field data example from the Gulf of Suez,
which shows improved recovery quality compared to conventional recursively
weighted matrix completion.

##  2 Methodology

We start by introducing wavefield reconstruction via weighted matrix
factorization. To improve computational efficiency, we move the weight
matrices to the data misfit term so we no longer have to carry out numerically
expensive weighted projections as in [Aravkin et al., 2013]. Aside from
allowing for a much more computationally efficient implementation, this
alternative formulation also forms the basis for our limited-subspace approach
designed to prevent overfitting at the low frequencies.

###  2.1 Weighted low-rank matrix factorization

Our proposed extension to wavefield reconstruction via recursively weighted
matrix factorization derives from earlier work by Kumar et al. [2015], Aravkin
et al. [2013], and Zhang et al. [2019], where we solve

$\displaystyle\mathop{\hbox{minimize}}_{\mathbf{X}_{i}}\quad\|\mathbf{Q}\mathbf{X}_{i}\mathbf{W}\|_{*}$
(1) $\displaystyle\text{subject
to}\quad\|\mathcal{A}(\mathbf{X}_{i})-\mathbf{b}_{i}\|_{2}\leq\tau$

to within a noise-level dependent data misfit tolerance $\tau$. In this
expression, the matrix $\mathbf{X}_{i}$ corresponds to a monochromatic
frequency slice in the midpoint/offset domain (in case of $2$D) at the
$i\mathrm{th}$ frequency ($i\in[1,\cdots,n_{f}]$ with with $n_{f}$ the number
of frequencies).

During the wavefield recovery, fully sampled frequency slices are represented
by the complex valued matrix, $\mathbf{X}\in\mathbb{C}^{n_{f}\times
n_{m}\times n_{h}}$ where $n_{m}$ is the number of midpoints and $n_{h}$ the
number of offsets. The symbol $\mathcal{A}(\cdot)$ stands for the subsampling
operator, which collects monochromatic data at the observed source/receiver
combinations into the vector $\mathbf{b}_{i}$. Given these observations, we
solve for the fully sampled $\mathbf{X}_{i}$ for each frequency by minimizing
equation 1 with weight matrices $\mathbf{Q}$ and $\mathbf{W}$ given by

$\mathbf{Q}={w}_{1}\mathbf{U}\mathbf{U}^{H}+\mathbf{U}^{\perp}\mathbf{U}^{{\perp}{H}}$
(2)

and

$\mathbf{W}={w}_{2}\mathbf{V}\mathbf{V}^{H}+\mathbf{V}^{\perp}\mathbf{V}^{{\perp}{H}}.$
(3)

In these expressions for the weight matrices, the
$\mathbf{U}\in\mathbb{C}^{n_{m}\times r}$ and
$\mathbf{V}\in\mathbb{C}^{n_{h}\times r}$ are the column and row subspaces
that derive from the low-rank factorization of the nearby frequency slice.
$\mathbf{U}$ and $\mathbf{V}$ have orthonormal columns that span top column
and row subspaces of nearby frequency slice. Because these weight matrices
include information on the subspaces of the current factorization, they serves
as prior information aiding the wavefield recovery via the weighted nuclear
norm minimization (denoted by
$\|\mathbf{QXW}\|_{\ast}=\sum_{j=1}^{r}\sigma_{j}$ with $\sigma_{j}$ the
$j^{\text{th}}$ singular value). Depending on whether we have confidence in
the fact that the neighboring frequency slice has an overlapping subspace, we
chose the weights $w_{1}$ and $w_{2}$ close to $0$ if we have confidence and
close to $1$ if we do not.

While the above weighted formulation has resulted in major improvements in the
recovery when reliable information on a neighboring frequency slice is
available [Kumar et al., 2015, Aravkin et al. [2013], and Zhang et al.
[2019]], the minimization in equation 1 is complicated by the presence of the
weighting matrices in the nuclear norm objective. As a result, the
minimization becomes computationally expensive. To avoid this complication, we
replace the optimization variable by
$\mathbf{\bar{X}}_{i}=\mathbf{Q}\mathbf{X}_{i}\mathbf{W}$, and rewrite
equation 1 as

$\displaystyle\mathop{\hbox{minimize}}_{\mathbf{\bar{X}}_{i}}\quad\|\mathbf{\bar{X}}_{i}\|_{*}$
(4) $\displaystyle\text{subject
to}\quad\|\mathcal{A}({\mathbf{Q}^{-1}}\mathbf{\bar{X}}_{i}{\mathbf{W}^{-1}})-\mathbf{b}_{i}\|_{2}\leq\tau$

where the modified weighting matrices

${\mathbf{Q}^{-1}}=\frac{1}{w_{1}}\mathbf{U}\mathbf{U}^{H}+\mathbf{U}^{\perp}\mathbf{U}^{{\perp}{H}}$
(5)

and

${\mathbf{W}^{-1}}=\frac{1}{w_{2}}\mathbf{V}\mathbf{V}^{H}+\mathbf{V}^{\perp}\mathbf{V}^{{\perp}{H}}$
(6)

are moved from the objective to the data misfit constraint. To reflect that we
changed the problem, we introduced barred quantities from which the solution
original solution can be readily computed—i.e., we recover the solution
$\mathbf{X}_{i}=\mathbf{Q}^{-1}\mathbf{\bar{X}}_{i}\mathbf{W}^{-1}$ since
$\mathbf{\bar{X}}_{i}=\mathbf{Q}\mathbf{X}_{i}\mathbf{W}$ solves the above
optimization problem. Compared to equation 1, this new formulation does not
require nuclear norm projections onto weighted matrices while its solution is
equivalent to equation 1.

Like the original formulation, our new formulation lends also itself to be
cast into a low-rank ($r\ll\max(n_{m},n_{h})$) factorized form so that
expensive SVDs are avoided in the nuclear norm. After factorization our
wavefield reconstruction involves

$\displaystyle\mathop{\hbox{minimize}}_{\mathbf{\bar{L}}_{i},\mathbf{\bar{R}}_{i}}\quad\frac{1}{2}{\left\|\begin{bmatrix}\mathbf{\bar{L}}_{i}\\\
\mathbf{\bar{R}}_{i}\end{bmatrix}\right\|}_{F}^{2}$ (7)
$\displaystyle\text{subject
to}\quad\|\mathcal{A}{({\mathbf{Q}^{-1}}\mathbf{\bar{L}}_{i}\mathbf{\bar{R}}_{i}^{H}{\mathbf{W}^{-1}})}-\mathbf{b}_{i}\|_{2}\leq\epsilon,$

where the symbol H denotes the Hermitian transpose and $\|\cdot\|_{F}$ is the
Frobenius norm (2-norm of the vectorized matrix) [Kumar et al., 2015, Aravkin
et al., 2013, Zhang et al., 2019]. Compared to the original representation for
frequency slices, the above factored form is compressed since it entails the
low-rank pair $\\{\mathbf{\bar{L}}_{i},\,\mathbf{\bar{R}}_{i}\\}$ ,where
$\mathbf{\bar{X}}_{i}=\mathbf{\bar{L}}_{i}\mathbf{\bar{R}}_{i}^{H}$, and does
not rely on storage and manipulation of the original and dense optimization
variable $\mathbf{X}_{i}$ or $\mathbf{\bar{X}}_{i}$. Despite gains in
computation, because of the factored form and redefined data misfit term,
challenges remain with recursive weighted matrix factorizations [Zhang et al.,
2019] at the high frequencies and as we will show these have to do with
overfitting.

###  2.2 Limited subspace weighted implementation

To reduce approximation errors at the high frequencies, we can increase the
rank of the factorization throughout. While increasing the rank leads to
better approximations at the high frequencies adapting this higher rank at the
lower frequencies can lead to overfitting. The resulting poor reconstructions
at the lower frequencies can in turn have a detrimental effect on the
reconstruction at higher frequencies, which information from the lower
frequencies as the recursive algorithm sweeps from the low to the high
frequencies.

By choosing the rank for the limited subspace, we reduce the size of the
subspaces of the weight matrices to prevent overfitting at the lower
frequencies. In equations 2, 3, 5 and 6, we notice that the size of the weight
matrices $\mathbf{Q}$ and $\mathbf{W}$ are independent of rank $r$. Therefore,
we can use a limited subspace to remove the influence of overfitting and get
better results.

By limited subspace, we mean that at a given frequency slice, instead of using
a rank $r$ for row and column subspaces $\mathbf{U}$ and $\mathbf{V}$
respectively, we can use a lower rank $r_{s}$. In this way, we can choose
higher rank $r$ to reconstruct each frequency but use lower rank $r_{s}$ to
construct the weight matrices ($\mathbf{Q}$ and $\mathbf{W}$). By choosing
smaller rank for the subspaces, we mitigate the negative influence of
overfitting. Therefore, in the limited-subspace method, we are free to choose
smaller values for the $r_{s}$ for each frequency slice and higher values for
the rank $r$ for the factorization itself (not for the weights) for each
frequency.

##  3 Numerical Experiments

To demonstrate the advocacy of the proposed method, we use $2$D field seismic
data acquired in the Gulf of Suez with number of sources, ${N}_{s}=355$, and
number of receivers, ${N}_{r}=355$. The total number of time samples in this
dataset is ${N}_{t}=1024$ and the sampling interval is $0.004\,\mathrm{s}$. We
use a jittered subsampling [Herrmann and Hennenfent, 2008] mask to remove
$75\%$ of the sources to obtain the subsampled data. When data is organized in
the midpoint-offset domain, we know that randomized jittered subsampling
method breaks the inherent low-rank property of seismic data while controlling
the largest gap size of the subsampled data [Herrmann and Hennenfent, 2008].
Controlling largest gap is important because very large gaps are not suitable
for wavefield reconstruction using sparsity-promotion or low-rank matrix
completion. We use the weighted method as described by Zhang et al. [2019] to
reconstruct frequency slices starting at $10\,\mathrm{Hz}$ and working our way
up to $70\,\mathrm{Hz}$. We use constant rank across all the frequencies for
weight matrices and matrix factorization. We base these choices for $r_{s}<r$
on visual inspection of the recovered frequency slices. To avoid overfitting
at lower frequencies we select rank $r_{s}$ of the limited subspace constant
across all the frequencies. And to better approximation of higher frequencies
we choose higher rank $r$ across all the frequencies. Combination of higher
rank for matrix factorization and smaller rank for limited subspace avoid the
risk of overfitting and at the same time improves the data reconstruction
quality.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 1: Reconstruction for missing source for a frequency slice at
$22\,\mathrm{Hz}$ shown in the source-receiver domain but reconstructed in the
midpoint-offset domain. _(a)_ Ground truth, _(b)_ $75\%$ subsampled seismic
data with jittered subsampling. _(c)_ and _(d)_ recovery by weighted matrix
factorization ($S/R=13.09\,\mathrm{dB}$) using conventional recursively
weighted approach with fixed rank $r=85$ and corresponding residual w.r.t. the
ground truth, respectively. _(e)_ and _(f)_ contain recovery
($S/R=15.50\,\mathrm{dB}$) for conventional recursively weighted with a rank
$r=25$ and corresponding residual w.r.t. the ground truth respectively. _(g)_
and _(h)_ represent recovery ($S/R=19.52\,\mathrm{dB}$) using limited-subspace
weighted method with limited-subspace rank $r_{s}=25$ and corresponding
residual w.r.t. the ground truth respectively.

To demonstrate that the limited-subspace recursively weighted method gives
improved results compared to conventional recursively weighted method [Zhang
et al., 2019], we first show results in the frequency domain. For each
frequency slice, we perform $150$ iterations for both the methods. For the
limited-subspace weighted method, we use rank $r=85$ and limited subspace rank
of $r_{s}=25$. For comparison with the conventional weighted method, we
perform two experiments with a fixed high rank of $r=85$ and lower rank of
$r=25$. We choose lower rank for conventional weighted method to show that
smaller rank itself is not sufficient for significant improvement in data
reconstruction at higher frequencies. On the other hand we choose higher rank
of 85 for conventional weighted method to show that higher rank is alone not
sufficient to improve the quality of reconstructed data at higher frequencies
because of the overfitting at lower frequencies. We show reconstruction
results for a frequency slice at $22\,\mathrm{Hz}$ in Figure 1. Due to
overfiting, the conventional method with rank $r=85$ gives a reconstruction
with a smaller S/R of $13.09\,\mathrm{dB}$ compared to the wavefield
reconstruction (Figures 1c and 1d) obtained with the smaller rank $r=25$ for
which we get S/R of $15.50\,\mathrm{dB}$ (Figures 1e and 1f). We get S/R of
$19.52\,\mathrm{dB}$ for the reconstructed data (Figures 1g) using the
limited-subspace weighted method. Figure 1h shows the data residual with
respect to the ground truth (Figure 1a). Clearly, our limited-subspace
weighted method outperforms the conventional weighted method in terms of
improved quality of reconstructed data.

To further compare our limited-subspace method with the original method, we
repeat wavefield reconstructions over a range of frequencies
$7-74\,\mathrm{Hz}$. In Figure 2, we show the comparison of the S/R’s across
the whole frequency range. As expected, we observe that limited-subspace
weighted method (red line in Figure 2) outperforms conventional weighted
method for both ranks of $25$ (blue line in Figure 2) and $85$ (black line in
Figure 2) for most of the frequencies. This is because of using limited
subspace we avoid risk of overfitting at lower frequencies and hence get
improvement in quality of reconstructed data.

Figure 2: $S/R$ of reconstructed data vs frequency based on our limited-
subspace weighted method (red color), conventional weighted method with rank
equals to $85$ (black color) and $25$ (blue color).

To show the recovery improvement in the time domain, we included Figure 3. To
make fair comparison, we construct a bandpass filter with pass frequency
$7-74\,\mathrm{Hz}$ with a transition width at both ends of
$3.66\,\mathrm{Hz}$. We apply this bandpass filter on the true data, the
subsampled data, and on recovered data recovered using the three scenarios
described above. After applying the filter, we transform the filtered data
back to the time domain. As we can see from Figure 3e, we observe less leakage
of coherent signal in the data residual for results obtained with our limited-
subspace weighted method in comparison to the data residual yielded by the
conventional weighted method with ranks of $r=85$ (Figure 3c) and $r=25$
(Figure 3d). With the conventional weighted method for rank equals to $r=85$,
we get S/R of $10.69\,\mathrm{dB}$, and for rank $r=25$, we get S/R of
$11.49\,\mathrm{dB}$. With the limited-subspace weighted method we get S/R of
$13.31\,\mathrm{dB}$, which is a significant improvement.

(a)

(b)

(c)

(d)

(e)

Figure 3: Wavefield reconstruction results in the time-domain. _(a)_ Ground
truth. (b) $75\%$ subsampled seismic data with jittered subsampling. _(c)_
using conventional weighted method ($S/R=10.69\,\mathrm{dB}$) for rank equals
to $r=85$, _(d)_ using conventional weighted method ($S/R=11.49\,\mathrm{dB}$)
for rank equals to $r=25$, _(e)_ using limited subspace weighted method
($S/R=13.31\,\mathrm{dB}$) with limited subspace rank $r_{s}=25$.

##  4 Conclusions

In this work, we proposed a limited-subspace weighted method to further
improve the performance of recursively weighted method in terms of better data
reconstruction quality. By exploiting the fact that dimensions of weight
matrices are independent of the rank of the subspaces, our method allows us to
use higher ranks for data reconstruction while avoiding the risk of
overfitting at the lower frequencies. Matrices with higher rank allow for a
better approximation of the frequency slices at higher frequencies and hence
allow for better quality of reconstructed data if we prevent overfitting by
working with limited-subspace weights. Through experiments we performed on a
field data acquired in the Gulf of Suez, we demonstrated the advantage of our
method in comparison to the recursively weighted method without using limited
subspace. We also introduced a computationally more efficient formulation by
moving the weight matrices to the data-misfit term. In future work , we would
like to extend the application of limited-subspace weighted method to large
scale $3$D data examples.

##  5 Related materials

In order to facilitate the reproducibility of the results herein discussed,
Matlab & Julia implementation of this work are made available on the SLIM
GitHub page https://github.com/slimgroup/Software.SEG2020.

##  6 Acknowledgement

We would like to acknowledge the support from Georgia Institute of Technology
for funding this research.

## References

  * Aravkin et al. [2013] Aleksandr Y Aravkin, Rajiv Kumar, Hassan Mansour, and Ben Recht.  A robust svd-free approach to matrix completion, with applications to interpolation of large scale data.  2013\.  URL http://arxiv.org/abs/1302.4886.
  * Eftekhari et al. [2018] Armin Eftekhari, Dehui Yang, and Michael B Wakin.  Weighted matrix completion and recovery with prior subspace information.  _IEEE Transactions on Information Theory_ , 64(6):4044–4071, 2018.
  * Herrmann and Hennenfent [2008] Felix J Herrmann and Gilles Hennenfent.  Non-parametric seismic data recovery with curvelet frames.  _Geophysical Journal International_ , 173(1):233–248, 2008.
  * Herrmann et al. [2012] Felix J Herrmann, Michael P Friedlander, and Ozgur Yilmaz.  Fighting the curse of dimensionality: Compressive sensing in exploration seismology.  _IEEE Signal Processing Magazine_ , 29(3):88–100, 2012.
  * Kumar et al. [2015] Rajiv Kumar, Curt Da Silva, Okan Akalin, Aleksandr Y Aravkin, Hassan Mansour, Benjamin Recht, and Felix J Herrmann.  Efficient matrix completion for seismic data reconstruction.  _Geophysics_ , 80(5):V97–V114, 2015.
  * Mosher et al. [2014] Charles Mosher, Chengbo Li, Larry Morley, Yongchang Ji, Frank Janiszewski, Robert Olson, and Joel Brewer.  Increasing the efficiency of seismic data acquisition via compressive sensing.  _The Leading Edge_ , 33(4):386–391, 2014.
  * Zhang et al. [2019] Yijun Zhang, Shashin Sharan, and Felix J Herrmann.  High-frequency wavefield recovery with weighted matrix factorizations.  In _SEG Technical Program Expanded Abstracts 2019_ , pages 3959–3963. Society of Exploration Geophysicists, 2019.