11institutetext: Huawei Cloud Computing
11email<EMAIL_ADDRESS>{shijiaxin3, jianlong.chang,
<EMAIL_ADDRESS>
# HiVLP: Hierarchical Vision-Language Pre-Training for Fast Image-Text
Retrieval

Feilong Chen  Xiuyi Chen  Jiaxin Shi
Duzhen Zhang  Jianlong Chang  Qi Tian

###### Abstract

In the past few years, the emergence of vision-language pre-training (VLP) has
brought cross-modal retrieval to a new era. However, due to the latency and
computation demand, it is commonly challenging to apply VLP in a real-time
online retrieval system. To alleviate the defect, this paper proposes a
Hierarchical Vision-Language Pre-Training (HiVLP) for fast Image-Text
Retrieval (ITR). Specifically, we design a novel hierarchical retrieval
objective, which uses the representation of different dimensions for coarse-
to-fine ITR, i.e., using low-dimensional representation for large-scale coarse
retrieval and high-dimensional representation for small-scale fine retrieval.
We evaluate our proposed HiVLP on two popular image-text retrieval benchmarks,
i.e., Flickr30k and COCO. Extensive experiments demonstrate that our HiVLP not
only has fast inference speed but also can be easily scaled to large-scale ITR
scenarios. The detailed results show that HiVLP is
$1,427$$\sim$$120,649\times$ faster than the fusion-based model UNITER and
2$\sim$5× faster than the fastest embedding-based model LightingDot in
different candidate scenarios. It also achieves about +4.9 AR on COCO and +3.8
AR on Flickr30K than LightingDot and achieves comparable performance with the
state-of-the-art (SOTA) fusion-based model METER.

###### Keywords:

Image-Text Retrieval, Hierarchical Pre-training, Vision-Language Pre-training

##  1 Introduction

Figure 1: Two kinds of Image-text Retrieval models. (a) Embedding-based Models
without cross-modal attention and fusion, (b) Fusion-based Models with cross-
modal attention and fusion.

With the explosive growth of multimodal data on the Internet, how to retrieve
the expected data of different modalities fast and well is becoming an urgent
problem. Image-text retrieval (ITR), which aims to retrieve the relevant
images and texts across each other, has been widely studied because of its
broad application prospects. Various benchmarks have been constructed to
promote the development of ITR, such as Flickr30k [34], COCO [3] and Multi30K
[10]

In terms of the cross-modal interaction, existing methods of ITR can be
divided into two categories: embedding-based models and fusion-based models.
Embedding-based models [11, 44, 40] employ separate image encoder and text
encoder to represent the image and text simultaneously and utilize their dot
product for similarity matching as shown in Figure 1 (a). Fusion-based models
[21, 22, 46, 51, 32, 4] apply cross-modal attention between textual features
and visual features for multimodal fusion as shown in Figure 1 (b). Some work
[21, 22, 46] improve visual representation by utilizing advanced region-based
visual encoder such as a pre-trained Faster R-CNN [35].

With the recent remarkable success of pre-training technologies [7, 8], the
pretraining-finetune paradigm is widely demonstrated in vision-language areas
[39, 25, 38, 5, 41, 29], which also promotes the performance of ITR to new
state-of-the-arts. Different from early models [19, 11, 44] that are train
from scratch with ranking loss, current approaches [40, 26] pre-train the
transformer-based [43] image/text/joint encoders [7] with millions of weakly-
supervised image-text pairs, and then finetune them with specific image-text
downstream benchmarks. The pre-training facilitates both embedding-based
models [40] and fusion-based ones [32, 4, 26, 12] and thus has become a
standard technology in the ITR area.

Embedding-based models and fusion-based models have different advantages. From
the accuracy aspect, fusion-based models inherently perform better than
embedding-based models because of the adequate cross-modal interaction [1].
However, fusion-based models have to fuse the query and all candidates online,
which will cause an intolerable latency in realistic search scenarios.
Instead, embedding-based models enjoy the searching efficiency because these
models disentangle the processing of images and texts and encode the massive
candidates offline, which greatly accelerates the real-time searching [40].
However, considering the huge amount of candidates on the Internet, it is
still unaffordable to compute so many dot products for each query. For
example, given $1e9$ candidates and $768$ hidden dimensions, the retrieval
needs about $1.5$ trillion operations (multiplication plus addition), which is
too costly even with a distributed cluster. If we increase the feature
dimension for better capability (i.e., $2048$ in [30]), the computation
overhead will become heavier.

To this end, we propose a novel embedding-based model, HiVLP, short for
Hierarchical Vision-Language Pre-Training, to enable fast and accurate real-
time ITR over massive candidates. We encode the query and candidates into
hierarchical features of different dimensions to obtain the coarse-to-fine
representation. Low-dimensional features are used for fast and coarse
retrieval over the large pool to narrow the candidate scope, and then high-
dimensional features are used for accurate retrieval over the resultant small
pool. Besides, hierarchical features are produced gradually by different
encoder layers so that we can parallel the encoding process with the retrieval
process, to reduce the overall latency further.

Specifically, we insert an Early Output Layer (EOL) into the intermediate
transformer layers, which converts the internal hidden states to external
representation features. Starting from the bottom of the transformer stack, we
increase the output dimension of EOL layer-by-layer to support a coarse-to-
fine representation capability. For model training, we propose three training
objectives to jointly train the visual transformer encoder and the linguistic
transformer encoder: (1) Linguistic Representation Modeling (LRM) to ensure
the model learns rich representations for both images and text, (2)
Hierarchical Retrieval Learning (HRL) to ensure cross-modal alignment of
different granularities, and (3) Vision-Language Matching (VLM) to obtain
accurate matching.

We evaluate the proposed approach on two popular ITR benchmarks, and
experiments show that our approach HiVLP is 1,427/6,426 $\times$ faster than
the existing fusion-based model UNITER on Flick30k/COCO and achieves a higher
performance. Moreover, we evaluate our approach on a larger candidate pool,
HiVLP further shows its efficiency.

Our contributions are summarized as follows:

  * •

We propose a novel approach HiVLP which utilizes hierarchical retrieval to
accelerate image-text retrieval with slight performance degradation.

  * •

We conduct extensive experiments on two popular ITR benchmarks and evaluate
our approach under larger candidates’ ITR settings. All the experiments show
that our approach dramatically improves the speed of image-text retrieval and
makes real-time ITR possible with low latency and high accuracy. HiVLP
achieves with comparable accuracy and higher speed than both fusion-based
models and embedding-based models. ($1,427$$\sim$$120,649\times$ faster than
UNITER, $2$$\sim$$5\times$ faster than fastest embedding-based model
LightingDot and comparable performance with METER).

##  2 Related Work

Image text retrieval aims to retrieve images with text or text with images.
The researchers’ exploration of this task is divided into two aspects: (1)
improving retrieval performance (2) accelerating retrieval speed.

###  2.1 Improving retrieval performance

One way to improve retrieval performance is to apply heavy cross-modal
interaction between vision and language. SCAN [21] utilize stacked cross-modal
transformer blocks to handle the interaction. CAMP [46] proposes cross-modal
adaptive message passing to improve retrieval performance, which adaptively
controls the information flow for message passing across modalities. CAAN [51]
obtains high retrieval performance via a unified context-aware attention
network, which selectively focuses on critical local fragments (regions and
words) by aggregating the global context. Another way to improve retrieval
performance is to utilize pre-training technology [45, 47]. Due to the success
of BERT [7] in NLP and ViT [8] in CV, more and more researchers begin to
explore the visual-language pre-training models [39, 25, 38, 5, 41, 29, 40].
Visual-language pre-training models learn the general vision-language
representation and achieve amazing performance via finetuning themselves on
image-text retrieval datasets.

###  2.2 Accelerating retrieval speed

There are some previous work [40, 42, 17] that aims to accelerate retrieval
speed. LightingDot [40] utilizes two independent encoders to represent images
and text and align them via dot product without cross-attention. Note that
LightingDot uses a faster RCNN pre-trained to extract images. Due to the slow
feature extraction speed of fast RCNN and the non-end-to-end training of
LightingDot, this may lead to the reduction of speed and accuracy. ALIGN [17]
leverages two transformers to learn visual and language representations via
large-scale image-text pairs (1.8B). HEI [42] learns to map the original data
points into short binary hash codes and coarsely preserve the heterologous
matching relationship in order to accelerate retrieval speed.

###  2.3 Hierarchical Retrieval

SHAN [16] proposes a step-wise hierarchical alignment network to learn the
alignment between images and text, which seems similar to our work. But in
fact, the difference between our proposed approach and SHAN is very obvious.
There are two main differences. First, SHAN learns hierarchical alignment
after the image and text are encoded by encoders, but our proposed method is
to let the model learn the alignment of different dimensional hierarchical
features in the process of encoding the image and text by encoders. Second,
the purpose of hierarchical retrieval is different. Hierarchical retrieval in
SHAN is for full multimodal interaction, and ours is to speed up retrieval.

Figure 2: An overview of our proposed approach HiVLP. HiVLP inverts an Early
Output Layer (EOL) into the intermediate transformer layers, which converts
the internal hidden states to external representation features.

##  3 Approach

In this section, we first introduce image-text retrieval and then propose our
model with hierarchical pre-training, which consists of the visual transformer
encoder, the linguistic transformer encoder and the cross-modal encoder as
shown in Figure 2. Third, we present the objectives to train our model and
finally, we describe the inference process by utilizing our hierarchical pre-
training model.

###  3.1 Task Definition

Image-text retrieval can be divided into two sub-tasks: (1) image annotation
for a given image and (2) image search for a given text. All the two sub-tasks
are to rank the candidates (texts or images) for a given image or text.

###  3.2 Hierarchical Pre-training Model

Following BERT [7] and ViT [8], we utilize the transformer encoder modified
from [43] as our visual encoder and linguistic encoder.

####  3.2.1 Visual Transformer Encoder

For a given image from a image-text pair $(I,T)$, we reshape the 2D image
$I\in\mathbb{R}^{H\times W\times C}$ into a sequence of 2D patches
$x_{p}\in\mathbb{R}^{N^{V}\times(P^{2}\cdot C)}$, where $(H,W)$ is the
resolution of the image, $C$ is the channel number, $(P,P)$ is the resolution
of each image patch, and $N^{V}=HW/P^{2}$ is the resulting number of patches.
And then, we flatten the patches and map them to $d_{h}$ dimensions with a
trainable linear projection. We regard the output of this projection as the
patch embeddings. We add a special token [IMG] to obtain the global
representation of the input image. We use standard learnable 1D position
embeddings to retain positional information. We add position embeddings to the
patch embeddings to obtain visual input features $\bf x_{V}$. We encode $\bf
x_{V}$ into multiple levels of visual representations
${\mathbf{h}_{V}}=\\{{\mathbf{h}_{V}}_{0},\dots,{\mathbf{h}_{V}}_{N^{V}}\\}$
$({\mathbf{h}_{V}}_{j}\in\mathbb{R}^{d})$ by using $L^{V}$-stacked Transformer
blocks, where the $l$-th Transformer block is denoted as
$\mathbf{H}^{l}=\text{Transformer}(\mathbf{H}^{l-1}),l\in[1,L^{V}]$.
Specifically, the representations $\mathbf{H}^{l}$ is calculated by using the
multi-head self-attention [43] as follows:

$\mathbf{Q}=\mathbf{H}^{l-1}\mathbf{W}_{l}^{Q},\mathbf{K}=\mathbf{H}^{l-1}\mathbf{W}_{l}^{K},\mathbf{V}=\mathbf{H}^{l-1}\mathbf{W}_{l}^{V},$
(1)
$\mathbf{A}_{l}=\text{softmax}(\frac{\mathbf{Q}\mathbf{K}^{T}}{\sqrt{d_{k}}})\mathbf{V},$
(2)

where
$\mathbf{W}_{l}^{Q},\mathbf{W}_{l}^{K},\mathbf{W}_{l}^{V}\in\mathbb{R}^{d_{h}\times
d_{k}}$ are learnable weights for computing the queries, keys, and values
respectively. Then $\mathbf{A}_{l}$ is passed into a feedforward layer to
compute $\mathbf{H}^{l}$ for the next layer:

$\mathbf{H}^{l}={\rm FFN}(\mathbf{A}_{l})$ (3)

We utilize $\mathbf{H}^{l}$ to represent ${\mathbf{h}_{V}}^{l}$. We use
${\mathbf{h}_{V}}_{0}^{l}$ to denote $l$-th global visual representation.

##### Linguistic Transformer Encoder

For a given text from a image-text pair $(I,T)$, we employ WordPiece tokenizer
[48] to split it into a word sequence $\mathbf{w}$, where each word is
embedded with an absolute positional code following [7], to obtain high-
dimensional feature vectors
${\mathbf{w}}=\\{{\mathbf{w}}_{0},{\mathbf{w}}_{1},...,{\mathbf{w}}_{N^{T}}\\}$
(${\mathbf{w}}_{j}\in\mathbb{R}^{d_{w}}$, $N^{T}$ is the number of tokens).
Similarly, we add a special token [TXT] and use $L^{T}$-stacked Transformer
blocks to obtain the global representation
${\mathbf{h}_{T}}=\\{{\mathbf{h}_{T}}_{0},\dots,{\mathbf{h}_{T}}_{N^{T}}\\}$
$({\mathbf{h}_{T}}_{j}\in\mathbb{R}^{d})$ of linguistic features. We use
${\mathbf{h}_{T}}_{0}^{l}$ to denote $l$-th global linguistic representation.

##### Cross-modal Encoder

To obtain the fused representation of vision and language, our cross-modal
encoder is applied a cross-attention [43] and takes the representation from
the linguistic transformer encoder as query input and the representation from
the visual transformer encoder as key and value inputs. We regard the fused
representation of [TXT] as multimodal representation.

###  3.3 Training Objectives

We utilize three objectives to train our model: (1) Linguistic Representation
Modeling (LRM) to ensure the model learns rich representations for both images
and text, (2) Hierarchical Retrieval Learning (HRL) to ensure hierarchical
retrieval from rough retrieval to fine retrieval, (3) Vision-Language Matching
(VLM) to obtain accurate matching.

####  3.3.1 Linguistic Representation Modeling (LRM)

Similar to [7, 40], we mask 15$\%$ tokens and train the model to reconstruct
the masked tokens. Formally, we denote
$\mathbf{w}_{\mathbf{m}}=\\{\mathbf{w}_{{\mathbf{m}}_{1}},\dots,\mathbf{w}_{{\mathbf{m}}_{M}}\\}$
as masked regions, where $\mathbf{m}\in\mathbb{N}^{M}$ is the set of masked
indices of size $M$, randomly sampled from a natural number $\mathbb{N}$.
$\mathbf{w}_{\setminus\mathbf{m}}$ are the unmasked tokens. Linguistic
Representation Modeling is supervised by:

$\begin{split}\mathcal{L}_{\text{LRM}}(T,I)=\mathbb{E}_{(I,T)\sim
D}\mathrm{CE}(P_{\theta}({\mathbf{w}}_{\mathbf{m}}&|{\mathbf{w}}_{\setminus{\mathbf{m}}},\,I))\\\
=-\frac{1}{M}\sum_{k=1}^{M}\log
P_{\theta_{\text{mlm}}}({\mathbf{w}}_{{\mathbf{m}}_{k}}&|{\mathbf{h}_{T}}_{{\mathbf{m}}_{k}}+{\mathbf{h}_{V}}_{0}^{l})\,,\end{split}$
(4)

where $\theta_{mlm}$ and the word probabilities $P_{\theta}$ are conditioned
on the corresponding image $I$ via the global image representation
${\mathbf{h}_{V}}_{0}^{l}$. Notice that we only utilize the final linguistic
representation of the last layer to train the model with the linguistic
representation modeling objective.

Figure 3: An overview of image retrieval by using our proposed approach HiVLP
at inference. Starting from the bottom of the transformer stack, we increase
the output dimension of EOL layer-by-layer, to support a coarse-to-fine
representation capability, which compute image-text similarity with
hierarchical representation to reduce the candidate images and accelerate
inference speed.

####  3.3.2 Hierarchical Retrieval Learning (HRL)

As shown in Figure 2, in order to better carry out image-text retrieval, we
leverage paired image-text samples to learn the strong correlation between
them at each early output layer. The model is trained to optimize the
similarity of paired samples $(I,T)$ and vice versa. The l-th layer similarity
of $(I,T)$ is calculated by dot product as follows:

$\displaystyle
S^{l}(t,i)=\hat{{\mathbf{h}_{T}}}_{0}^{l}\odot\hat{{\mathbf{h}_{V}}}_{0}^{l},$
(5)

where $\odot$ denotes the inner product between two vectors, and
$\hat{{\mathbf{h}_{V}}}_{0}^{l}$ and $\hat{{\mathbf{h}_{T}}}_{0}^{l}$ are the
output [IMG] and [TXT] representation from $l$-th early ouput layer of visual
encoder and linguistic encoder, respectively. We transform
${\mathbf{h}_{V}}_{0}^{l}$ into
$\hat{{\mathbf{h}_{V}}}_{0}^{l}\in\mathbb{R}^{d_{EOL_{l}}}$ via a MLP
projection named Early Output Layer (EOL). Similarly, We transform
${\mathbf{h}_{T}}_{0}^{l}$ into
$\hat{{\mathbf{h}_{T}}}_{0}^{l}\in\mathbb{R}^{d_{EOL_{l}}}$ via another MLP
projection. In order to utilize training samples efficiently, we propose a in-
batch retrieval learning, which close the matched sample and push far the
unmatched sample. Given a batch samples with $n$ image-text pairs
$(I_{i},T_{i})$, when we treat text $T_{i}$ as the query, there are one
positive image $I_{i}$ and $n-1$ negative images. The text-to-image similarity
of $l$-th early output layer is defined as follows:

$\displaystyle p^{l}_{t2v,T_{i}}=\frac{{\rm
exp}({S^{l}(T_{i},I_{i})})}{\sum_{k=1}^{n}{\rm exp}({S^{l}(T_{i},I_{k})})},$
(6)

Similarly, we take image $I_{i}$ as query and compute image-to-text similarity
$p^{l}_{v2t,I_{i}}$. The final retrieval loss at $l$-th layer is:

$\displaystyle\mathcal{L}^{l}_{\text{RL}}=\frac{1}{2}\mathbb{E}_{(I,T)\sim
D}[\mathrm{CE}(y_{t2v},p^{l}_{t2v,T_{i}})+\mathrm{CE}(y_{v2t},p^{l}_{v2t,I_{i}})],$
(7)

where $\rm CE(\cdot)$ denotes the cross-entropy, $y_{t2v}$ and $y_{v2t}$
denotes the ground-truth label and $D$ denotes the training set. For each
early output layer, there is a retrieval loss $\mathcal{L}^{l}_{\text{RL}}$
and the final hierarchical retrieval learning loss is defined as:

$\displaystyle\mathcal{L}_{\text{HRL}}=\sum_{l=1}^{L}\mathcal{L}^{l}_{\text{RL}}.$
(8)

####  3.3.3 Vision-Language Matching (VLM)

To further enhance the model’s performance, we utilize the cross-modal encoder
to fuse the visual representation and linguistic representation. We regard the
fused representation of [TXT] from the cross-modal encoder as multimodal
representation. We feed the fused multimodal representation of both modalities
to an FC layer and a sigmoid function to predict a score between 0 and 1,
where 0 indicates the vision and language are mismatched, and 1 indicates the
vision and language are matched as follows:

$\displaystyle\mathcal{L}_{\mathrm{VLM}}=\mathbb{E}_{(I,T)\sim
D}\mathrm{CE}(y,p({\bf z}^{L^{V}},{\bf h}^{L^{T}})),$ (9)

where $D$ is the training dataset, $p(\cdot)$ denotes the transformer decoder
blocks and $y$ denotes the ground-truth label.

Model | COCO Test (5k images) | Flickr30K Test (1k images)
---|---|---
Text Retrieval | Image Retrieval |  | Text Retrieval | Image Retrieval |
R@1 | R@5 | R@10 | R@1 | R@5 | R@10 | AR | R@1 | R@5 | R@10 | R@1 | R@5 | R@10 | AR
Fusion-based Model
GXN [13] | 42.0 | - | 84.7 | 31.7 | - | 74.6 | - | 56.8 | - | 89.6 | 41.5 | - | 80.0 | -
SCAN-single [21] | 46.4 | 77.4 | 87.2 | 34.4 | 63.7 | 75.7 | 64.1 | 67.9 | 89.0 | 94.4 | 43.9 | 74.2 | 82.8 | 75.4
R-SCAN [22] | 45.4 | 77.9 | 87.9 | 36.2 | 65.6 | 76.7 | 65.0 | 66.3 | 90.6 | 96.0 | 51.4 | 77.8 | 84.9 | 77.8
BFAN | 49.9 | 79.5 | 88.8 | 36.9 | 65.7 | 77.2 | 66.3 | 69.2 | 91.4 | 96.2 | 50.0 | 77.2 | 84.8 | 78.1
CAMP [46] | 50.1 | 82.1 | 89.7 | 39.0 | 68.9 | 80.2 | 68.3 | 68.1 | 89.7 | 95.2 | 51.5 | 77.1 | 85.3 | 77.8
CAAN [51] | 52.5 | 83.3 | 90.9 | 41.2 | 70.3 | 82.9 | 70.2 | 70.1 | 91.6 | 97.2 | 52.8 | 79.0 | 87.9 | 79.8
GSMN [28] | 49.4 | 79.3 | 88.8 | 35.9 | 65.5 | 76.9 | 66.0 | 73.3 | 91.8 | 96.4 | 52.4 | 79.2 | 86.3 | 79.9
IMRAN [2] | 52.5 | 81.2 | 89.8 | 39.1 | 68.4 | 79.5 | 68.4 | 71.0 | 92.0 | 96.3 | 53.1 | 79.9 | 86.2 | 79.7
CAMP-HEI [42] | 43.4 | 75.0 | 86.2 | 32.3 | 63.2 | 75.1 | 62.5 | 67.6 | 90.9 | 95.0 | 52.6 | 78.2 | 84.4 | 78.1
GSMN-HEI [42] | 49.3 | 79.3 | 88.8 | 35.9 | 65.4 | 76.7 | 65.9 | 73.4 | 91.9 | 96.7 | 52.4 | 79.0 | 86.0 | 79.9
IMRAN-HEI [42] | 52.5 | 81.3 | 89.8 | 35.9 | 65.4 | 76.7 | 66.9 | 71.0 | 92.0 | 96.4 | 53.2 | 79.7 | 85.8 | 79.7
BFAN-HEI [42] | 49.6 | 79.1 | 88.4 | 36.9 | 65.7 | 77.2 | 66.2 | 69.2 | 91.2 | 96.2 | 49.9 | 77.2 | 84.6 | 78.1
SHAN [16] | - | - | - | - | - | - | - | 74.6 | 93.5 | 96.9 | 55.3 | 81.3 | 88.4 | 81.7
UNITER [4] | 64.4 | 87.4 | 93.1 | 50.3 | 78.5 | 87.2 | 76.8 | 85.9 | 97.1 | 98.8 | 72.5 | 92.3 | 95.9 | 90.4
OSCAR [26] | 70.0 | 91.1 | 95.5 | 54.0 | 80.8 | 88.5 | 79.8 | - | - | - | - | - | - | -
ALBEF [24] | 73.1 | 91.4 | 96.0 | 56.8 | 81.5 | 89.2 | 81.3 | 94.3 | 99.4 | 99.8 | 82.8 | 96.7 | 98.4 | 95.2
VinVL [50] | 74.6 | 92.6 | 96.3 | 58.1 | 83.2 | 90.1 | 82.5 | - | - | - | - | - | - | -
ViLT [18] | 61.5 | 86.3 | 92.7 | 42.7 | 72.9 | 83.1 | 73.2 | 83.5 | 96.7 | 98.6 | 64.4 | 88.7 | 93.8 | 87.6
Pixel-BERT [15] | 63.6 | 87.5 | 93.6 | 50.1 | 77.6 | 86.2 | 76.4 | 87.0 | 98.9 | 99.5 | 71.5 | 92.1 | 95.8 | 90.8
Visual Parsing [49] | - | - | - | - | - | - | - | 87.0 | 98.4 | 99.5 | 73.5 | 93.1 | 96.4 | 91.3
METER [9] | 76.2 | 93.2 | 96.8 | 57.1 | 82.7 | 90.1 | 82.6 | 94.3 | 99.6 | 99.9 | 82.2 | 96.3 | 98.4 | 95.1
Embedding-based Model
VSE++ [11] | 41.3 | 69.2 | 81.2 | 30.3 | 59.1 | 72.4 | 58.9 | 52.9 | 80.5 | 87.2 | 39.6 | 70.1 | 79.5 | 68.3
SCO [14] | 42.8 | 72.3 | 83.0 | 33.1 | 62.9 | 75.5 | 61.6 | 55.5 | 82.0 | 89.3 | 41.1 | 70.5 | 81.1 | 69.9
LD [40] | 60.1 | 85.1 | 91.8 | 45.8 | 74.6 | 83.8 | 73.5 | 83.9 | 97.2 | 98.6 | 69.9 | 91.1 | 95.2 | 89.3
LD+OSCAR [40] | 74.2 | 92.4 | 96.0 | 57.4 | 82.7 | 89.9 | 82.1 | - | - | - | - | - | - | -
ALIGN∗ [17] | 77.0 | 93.5 | 96.9 | 59.9 | 83.3 | 89.8 | 83.4 | 95.3 | 99.8 | 100.0 | 84.9 | 97.4 | 98.6 | 96.0
HiVLP (Ours) | 71.7 | 91.4 | 96.0 | 52.3 | 78.8 | 86.8 | 79.4 | 92.6 | 99.3 | 99.9 | 79.8 | 95.3 | 97.7 | 94.1
HiVLP + CM (Ours) | 76.6 | 94.2 | 97.1 | 60.0 | 83.8 | 90.4 | 83.7 | 95.5 | 99.7 | 100.0 | 84.0 | 96.9 | 98.4 | 95.8

Table 1:  Comparision with both fusion-based models and embedding-based
models. Our approach achieves comparable performance with a faster inference
speed. “LD” denotes “LinghtDot”. * denotes that ALIGN utilizes 1.8B image-text
data for training.

###  3.4 Real-Time Inference

As shown in Figure 3, similar to most retrieval systems, our approach consists
of two phrases at real-time inference: (1) Offline Representation Extraction
and (2) Online Hierarchical Retrieval. We take text-to-image retrieval as an
example to introduce our hierarchical retrieval. The purpose of Offline
Representation Extraction is to extract the features of candidate images or
candidate texts extracted by visual encoder or text encoder offline before
retrieval.

####  3.4.1 Online Hierarchical Retrieval

During inference, given a text query $T$, we encode it with our linguistic
transformer encoder to obtain hierarchical global representation and compute
its similarity with small latency to reduce the candidate images as shown in
Figure 3. For $l$-th early output layer, we propose top-$K_{l}$ retrieval to
reduce image candidates and obtain a list of $K_{l}$ images $I_{T}$. At
$l+1$-th early output layer, the model only needs to retrieve top-$K_{l+1}$
images from $K_{l}$ images instead of all the image candidates $K_{ALL}$
($K_{l+1}\ll K_{l}\ll K_{ALL}$), which significantly reduces the retrieval
time. In addition, the query representation extraction and the similarity
computing are processed in parallel approximatively, which further reduces the
retrieval time.

####  3.4.2 Retrieval Time Analysis

The retrieval time consumption of embedding-based models comes from the query
encoding and the similarity calculation. We assume that the encoding time of
each layer is $t_{e}$, and the calculated time of each dot product similarity
is $t_{s}^{d}$ for $d$-dimensional vectors. For a text-to-image retrieval,
given a query text $T$ with $N$ image candidates, the traditional inference
time based on 12 layer encoders is $12t_{e}+Nt_{s}^{d}$. Considering our
hierarchical retrieval encoders with 3 early output layers, the inference time
of our approach is
$4t_{e}+max(4t_{e},N_{1}t_{s}^{d_{1}})+max(4t_{e},N_{2}t_{s}^{d_{2}})+N_{3}t_{s}^{d}$.
When there are $N=10^{9}$ image candidates and we adopt
$N_{1}=10^{9},N_{2}=10^{5},N_{3}=100$ and $d=768,d_{1}=128,d_{2}=300$, under
the assumption that each multiplication consumes unit time $1$ and the
encoding time $t_{e}=10^{3}$, the traditional inference time is about $7\times
10^{11}$ and our inference time is about $1\times 10^{11}$. Our proposed
hierarchical retrieval is $\sim 7\times$ faster than the traditional
embedding-based model settings based on the same model structure.

##  4 Experiments

###  4.1 Datasets and Implement Details

####  4.1.1 Datasets

Similar to most vision-language pre-training models [4, 23, 40], we utilize
four image-text pairs datasets with 4.1 million images and 9.5 million
associated captions for training, including COCO [27], Visual Genome [20],
Conceptual Captions [37], and SBU captions [33]. We use Flickr30k [34] and
COCO [27] datasets for evaluation, which include 31K images from Flickr30K
(29K/1k/1k images for train, validation and test, respectively) and 123K
images from COCO (114K/5K/5K for train, validation and test, respectively).
Each image from Flickr30k and COCO is associated with 5 human-written
captions.

####  4.1.2 Implement Details

We use the visual transformer encoder and linguistic transformer encoder,
which has 12/6 layers, 768 hidden states and 12 heads, respectively. The
cross-modal encoder has 6 layers, 768 hidden states and 12 heads. We utilize
AdamW [31] with $\beta_{1}{=}0.9$, $\beta_{2}{=}0.98$ to optimize the model
training. Moreover, a learning rate warm-up strategy is adopted, where the
learning rate 1e-4 is linearly increased during the first 10% of training
steps, followed by a linear decay to 1e-5 in pre-training and 1e-5 to 1e-6 in
finetune. The L2 weight decay is 0.01. We set the batch size to 32 per GPU. We
conduct pre-training experiments on 8$\times$ A100 GPUs with 6-step gradient
accumulation. We train our model for 10 epochs on Flickr30k, and 10 epochs on
COCO. In our experiments, we utilize 3 EOL layers. We set $N_{2}=1000$ and
$N_{3}=100$ for all the evaluate sets except for COCO FULL where we set
$N_{2}=5000$ and $N_{3}=1000$. Notice that $N_{1}$ equals the number of
candidates $N$ of each evaluation set.

###  4.2 Evaluation Metrics

We measure image-text retrieval by recall@$K$ (R@$K$) and the average R@$K$
(AR) for all $K$ for both image-to-text retrieval and text-to-image retrieval
tasks. All metrics are the higher the better.

Model | COCO-Full (123K Images) | Flickr30K-Full (31K Images)
---|---|---
Text Retrieval | Image Retrieval |  | Text Retrieval | Image Retrieval |
R@5 | R@10 | R@20 | R@5 | R@10 | R@20 | AR | R@5 | R@10 | R@20 | R@5 | R@10 | R@20 | AR
LightingDot | 40.1 | 51.0 | 62.0 | 28.2 | 37.4 | 47.8 | 44.4 | 69.6 | 78.9 | 86.1 | 51.8 | 62.3 | 72.3 | 70.2
HiVLP (Ours) | 54.3 | 65.6 | 69.5 | 42.8 | 55.4 | 60.6 | 58.3 | 78.5 | 94.1 | 97.4 | 60.5 | 84.2 | 90.7 | 84.2

Table 2:  Results on the large retrieval setting of full Flickr30k and full
COCO datasets.

###  4.3 Results

We compare our approach HiVLP with the mainstream state-of-the-art models
under the standard retrieval settings and the large candidate settings. The
inference speed comparision can be seen in Table 4 for details.

####  4.3.1 Base Models

The compared previous models are divided into two kinds. Fusion-based models:
GXN [13], SCAN [21], R-SCAN [22], CAMP [46], CAAN [51], ViLBERT [32],
Unicoder-VL [23], UNITER [4], OSCAR [26], VinVL [50], ALBEF [24], METER [9]
and so on. Embedding-based models: VSE++ [11], SCO [14], LightingDot [40],
ALIGN [17]. Notice that ALIGN utilizes 1.8B image-text data for training. For
fair comparison, we do not compare with ALIGN.

####  4.3.2 Results under standard retrieval settings

Performance on two benchmarks COCO and Flickr30K is shown in Table 1. “+OSCAR”
denotes LightingDot uses OSCAR as a Re-Ranker. “+CM” denotes we utilize our
cross-modal encoder to re-rank the results of the last EOL layer. From the
results, we can observe that: (1) Compared with embedding-based models. Our
approach outperforms non-pre-training approaches (VSE++, SCO) by large margins
on all metrics. Specifically, our HiVLP achieves $79.4\%$ on AR on COCO and
$94.1\%$ on Flickr30K on AR, beating SCO by $+17.8\%$ on AR on COCO Test and
$+24.2\%$ on Flickr30K Test. When comparing with pre-training models, our
approach is better than LightingDot on performance, and our HiVLP is much
faster than LightingDot (2.23$\times$ faster on Flickr30K-test, 3.33$\times$
faster on COCO-test). Our approach HiVLP achieves better performance compared
with the existing fastest pre-training model LightingDot ($+5.9\%$ AR on COCO
and $+4.8\%$ AR on Flickr30K) and is still much faster than it (see Table 4),
which shows the efficiency of the proposed hierarchical retrieval structure.

(2) Compared with models with fusion-based. HiVLP also outperforms the non-
pre-training models (CXN, CAAN and etc.) by a significant margin. Although
HiVLP achieves slightly lower performance on some metrics than pre-training
models with cross-attention, such as the SOTA model METER, HiVLP is much
faster than pre-training models with cross-attention. Notice that HiVLP is
$\sim$1,400/6,400$\times$ faster than UNITER during inference time and gains
3.7/2.6 points on Flickr30K/COCO simultaneously.

Model | Text Retrieval | Image Retrieval |
---|---|---|---
R@1 | R@5 | R@10 | R@1 | R@5 | R@10 | AR
HiVLP w/ HRL1 | 56.3 | 81.1 | 87.3 | 36.9 | 67.0 | 78.1 | 66.8
HiVLP w/ HRL2 | 71.9 | 92.4 | 96.8 | 56.2 | 81.0 | 88.7 | 81.2
HiVLP w/ HRL3 | 93.7 | 99.1 | 99.7 | 79.5 | 95.0 | 97.3 | 94.1
HiVLP | 92.6 | 99.3 | 99.9 | 79.8 | 95.3 | 97.7 | 94.1
HiVLP + CM | 95.5 | 99.7 | 100.0 | 84.0 | 96.9 | 98.4 | 95.8

Table 3:  Ablation studies on training strategy over Flickr30K. “HiVLP w/
HRL1” denotes we evaluate the model by utilizing the outputs of first EOL
layer. “HiVLP w/ HRL2” denotes we evaluate the model by utilizing the outputs
of second EOL layer. “HiVLP w/ HRL2” denotes we evaluate the model by
utilizing the outputs of last EOL layer.

####  4.3.3 Results under large candidate settings

To further demonstrate the efficiency of our approach HiVLP, we compare our
approach with previous work under large candidate settings following [40] as
shown in Table 2. HiVLP outperforms LignthingDot with a significant margin
($+14.0\%$ AR on Flickr30K and $+13.9\%$ AR on COCO) with much faster
inference speed (5.47$\times$ faster on Flickr30K-Full, 5.05$\times$ faster on
COCO-Full as shown in Table 4).

Method | #images | SCAN | LightingDot | HiVLP (Ours)
---|---|---|---|---
Flickr30K-test | 1,000 | 1.8$\times$ | 639$\times$ | 1,427$\times$
COCO-test | 5,000 | 1.9$\times$ | 1,927$\times$ | 6,426$\times$
Flickr30K-full | 31,014 | 1.8$\times$ | 6,591$\times$ | 36,051$\times$
COCO-full | 123,287 | 1.9$\times$ | 23,869$\times$ | 120,649$\times$

Table 4: Speedup w.r.t. UNITER-base. We compare HiVLP (Ours) and Lightningdot,
plus a lightweight cross-attention method SCAN [21].

###  4.4 Retrieval Time Comparison

Following LightingDot [40], we use UNITER as the baseline to compare inference
speed in order to demonstrate the efficiency of our HiVLP as shown in Table 4.
In addition, SCAN [21] is also compared, which uses GRU [6] instead of a
12-layer Transformer with a more lightweight cross-attention. We test HiVLP
and LightingDot on the same GPU and other results are from [40]. As shown in
Table 4, SCAN is $\sim$1.9$\times$ faster than UNITER across both benchmarks
because the computational cost of GRU is much cheaper than that of
Transformer, but SCAN drops much performance. However, SCAN still utilizes
cross-attention and the speedup from SCAN is limited. In contrast, the
embedding-based models without cross-attention are much faster than UNITER.
Lightningdot is 639$\times$ faster than UNITER on Flickr30K while our HiVLP is
1,427$\times$ faster. HiVLP is still 2.23$\times$ than Lightningdot. When
tested with five times more images in COCO, the speedup from HiVLP is
6426$\times$ faster than UNITER while LightingDot is 1927$\times$. HiVLP is
3.33$\times$ faster than Lightningdot.

Our purpose is to build a real-time image-text retrieval system. Thus we test
HiVLP in a simulated real-life scenario as shown in Table 2. The simulated
real-life scenario contains hundreds of thousands of images (text) where we
combine all images (text) from training, validation and test set to form a
larger candidate pool following [40]. We regard this setting on both
benchmarks as Flickr30k-full (31k) and COCO-full (123k), and models are still
trained on the training set following [40]. The number of candidate images
(texts) scales up by $>$20$\times$ in the simulated real-life scenario. With
the same number of text quires, the fusion-based models immediately become
impractical. As shown in Table 4, our HiVLP is 36,051$\times$ faster on
Flickr30k-full and 120,649$\times$ faster on COCO-full than UNITER. Moreover,
HiVLP is 5.47$\times$ and 5.05$\times$ faster than LightingDot on
Flickr30k-Full and on COCO-Full, respectively.

Figure 4: Visualization of GradCam for each word. Each image corresponds to a
word.

###  4.5 Ablation Study

In order to comprehensively analyze our model, we conduct the ablation study
from the aspect of hierarchical retrieval strategy.

To verify the effectiveness of our hierarchical retrieval strategy, the
ablation study is shown in Table 3. We utilize the outputs of different EOL
layers to evaluate the models for image-to-text retrieval and text-to-image
retrieval on Flickr30K. From the results

###  4.6 Qualitative Examples

As shown in Figure 4, we visualize GradCam [36] for each word. The results
show that our model aligns words well with visual semantics and thus obtain
satisfactory retrieval performance. As shown in Figure 5, 6, 7 and 8, we show
examples of image retrieval results. All the 10 images are retrieved by our
model. The ground truth image is grounded in the green rectangle. Our model
usually retrieves the right images in the top 10 candidates, which is
satisfies people’s sense of experience in multimodal Internet search.

##  5 Conclusion

In this paper, we propose Hierarchical Vision-Language Pre-Training (HiVLP)
for fast image-text retrieval (ITR). Specifically, we propose a novel
hierarchical retrieval objective, which uses the representation of different
dimensions for image-text retrieval from coarse-grained to fine-grained
retrieval. Specifically, HiVLP use low dimensional representation for large-
scale rough retrieval and high-dimensional representation for small-scale fine
retrieval. Experiments on two benchmarks show that HiVLP is
$1,427$$\sim$$120,649\times$ faster than the fusion-based models UNITER and
$2$$\sim$$5\times$ faster than the fastest embedding-based model LightingDot.
Moreover, HiVLP achieves the higher performance (about +4.9 AR on COCO and
+3.8 AR on Flickr30K than LightingDot) simultaneously.

Figure 5: Retrieved top 10 images for the query ”ice hockey player during the
first period of a hockey game against sports team”. The ground truth is in the
green rectangle. Figure 6: Retrieved top 10 images for the query ”a group of
boys in a crowd”. The ground truth is in the green rectangle. Figure 7:
Retrieved top 10 images for the query ”person on the summit in the snow”. The
ground truth is in the green rectangle. Figure 8: Retrieved top 10 images for
the query ”silhouette of people walking on the beach at sunset”. The ground
truth is in the green rectangle.

## References

  * [1] Anderson, P., He, X., Buehler, C., Teney, D., Johnson, M., Gould, S., Zhang, L.: Bottom-up and top-down attention for image captioning and visual question answering. In: CVPR (2018)
  * [2] Chen, H., Ding, G., Liu, X., Lin, Z., Liu, J., Han, J.: Imram: Iterative matching with recurrent attention memory for cross-modal image-text retrieval. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 12655–12663 (2020)
  * [3] Chen, X., Fang, H., Lin, T.Y., Vedantam, R., Gupta, S., Dollár, P., Zitnick, C.L.: Microsoft coco captions: Data collection and evaluation server. arXiv preprint arXiv:1504.00325 (2015)
  * [4] Chen, Y.C., Li, L., Yu, L., El Kholy, A., Ahmed, F., Gan, Z., Cheng, Y., Liu, J.: Uniter: Universal image-text representation learning. In: ECCV (2020)
  * [5] Cho, J., Lei, J., Tan, H., Bansal, M.: Unifying vision-and-language tasks via text generation. In: ICML (2021)
  * [6] Chung, J., Gulcehre, C., Cho, K., Bengio, Y.: Empirical evaluation of gated recurrent neural networks on sequence modeling. In: Deep Learning and Representation Learning Workshop. NeurIPS (2014)
  * [7] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. In: NAACL-HLT (2019)
  * [8] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., Houlsby, N.: An image is worth 16x16 words: Transformers for image recognition at scale (2020)
  * [9] Dou, Z.Y., Xu, Y., et al.: An Empirical Study of Training End-to-End Vision-and-Language Transformers. arXiv preprint arXiv:2111.02387 (2021)
  * [10] Elliott, D., Frank, S., Sima’an, K., Specia, L.: Multi30k: Multilingual english-german image descriptions. In: Proceedings of the 5th Workshop on Vision and Language. Association for Computational Linguistics (2016)
  * [11] Faghri, F., Fleet, D.J., Kiros, J.R., Fidler, S.: Vse++: Improving visual-semantic embeddings with hard negatives. In: BMVC (2017)
  * [12] Gan, Z., Chen, Y.C., Li, L., Zhu, C., Cheng, Y., Liu, J.: Large-scale adversarial training for vision-and-language representation learning. In: NeurIPS (2020)
  * [13] Gu, J., Cai, J., Joty, S.R., Niu, L., Wang, G.: Look, imagine and match: Improving textual-visual cross-modal retrieval with generative models. In: CVPR (2018)
  * [14] Huang, Y., Wu, Q., Song, C., Wang, L.: Learning semantic concepts and order for image and sentence matching. In: CVPR (2018)
  * [15] Huang, Z., Zeng, Z., Liu, B., Fu, D., Fu, J.: Pixel-bert: Aligning image pixels with text by deep multi-modal transformers. arXiv preprint arXiv:2004.00849 (2020)
  * [16] Ji, Z., Chen, K., Wang, H.: Step-wise hierarchical alignment network for image-text matching. arXiv preprint arXiv:2106.06509 (2021)
  * [17] Jia, C., Yang, Y., Xia, Y., Chen, Y.T., Parekh, Z., Pham, H., Le, Q.V., Sung, Y., Li, Z., Duerig, T.: Scaling up visual and vision-language representation learning with noisy text supervision. In: International Conference on Machine Learning (2021)
  * [18] Kim, W., Son, B., et al.: ViLT: Vision-and-language transformer without convolution or region supervision. arXiv preprint arXiv:2102.03334 (2021)
  * [19] Kiros, R., Salakhutdinov, R., Zemel, R.S.: Unifying visual-semantic embeddings with multimodal neural language models. In: Deep Learning and Representation Learning Workshop. NeurIPS (2014)
  * [20] Krishna, R., Zhu, Y., Groth, O., Johnson, J., Hata, K., Kravitz, J., Chen, S., Kalantidis, Y., Li, L.J., Shamma, D.A., et al.: Visual genome: Connecting language and vision using crowdsourced dense image annotations. IJCV (2017)
  * [21] Lee, K.H., Chen, X., Hua, G., Hu, H., He, X.: Stacked cross attention for image-text matching. In: ECCV (2018)
  * [22] Lee, K.H., Palangi, H., Chen, X., Hu, H., Gao, J.: Learning visual relation priors for image-text matching and image captioning with neural scene graph generators. arXiv preprint arXiv:1909.09953 (2019)
  * [23] Li, G., Duan, N., Fang, Y., Jiang, D., Zhou, M.: Unicoder-vl: A universal encoder for vision and language by cross-modal pre-training. In: AAAI (2020)
  * [24] Li, J., Selvaraju, R.R., Gotmare, A.D., Joty, S., Xiong, Caiming andHoi, S.: Align before fuse: Vision and language representation learning with momentum distillation. Tech. Rep. arXiv:2107.07651 (2021)
  * [25] Li, L.H., Yatskar, M., Yin, D., Hsieh, C.J., Chang, K.W.: Visualbert: A simple and performant baseline for vision and language. arXiv preprint arXiv:1908.03557 (2019)
  * [26] Li, X., Yin, X., Li, C., Hu, X., Zhang, P., Zhang, L., Wang, L., Hu, H., Dong, L., Wei, F., et al.: Oscar: Object-semantics aligned pre-training for vision-language tasks. In: ECCV (2020)
  * [27] Lin, T.Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., Zitnick, C.L.: Microsoft coco: Common objects in context. In: ECCV (2014)
  * [28] Liu, C., Mao, Z., Zhang, T., Xie, H., Wang, B., Zhang, Y.: Graph structured network for image-text matching. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 10921–10930 (2020)
  * [29] Liu, J., Zhu, X., Liu, F., Guo, L., Zhao, Z., Sun, M., Wang, W., Lu, H., Zhou, S., Zhang, J., et al.: Opt: Omni-perception pre-trainer for cross-modal understanding and generation. arXiv preprint arXiv:2107.00249 (2021)
  * [30] Liu, W., Zhou, P., Zhao, Z., Wang, Z., Deng, H., Ju, Q.: Fastbert: a self-distilling bert with adaptive inference time. arXiv preprint arXiv:2004.02178 (2020)
  * [31] Loshchilov, I., Hutter, F.: Decoupled weight decay regularization. In: ICLR (2019)
  * [32] Lu, J., Batra, D., Parikh, D., Lee, S.: Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks. In: NeurIPS (2019)
  * [33] Ordonez, V., Kulkarni, G., Berg, T.L.: Im2text: Describing images using 1 million captioned photographs. In: NeurIPS (2011)
  * [34] Plummer, B.A., Wang, L., Cervantes, C.M., Caicedo, J.C., Hockenmaier, J., Lazebnik, S.: Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models. In: ICCV (2015)
  * [35] Ren, S., He, K., et al.: Faster R-CNN: towards real-time object detection with region proposal networks. In: NeurIPS (2015)
  * [36] Selvaraju, R.R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., Batra, D.: Grad-cam: Visual explanations from deep networks via gradient-based localization. In: Proceedings of the IEEE international conference on computer vision. pp. 618–626 (2017)
  * [37] Sharma, P., Ding, N., Goodman, S., Soricut, R.: Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning. In: ACL (2018)
  * [38] Shen, S., Li, L.H., Tan, H., Bansal, M., Rohrbach, A., Chang, K.W., Yao, Z., Keutzer, K.: How much can clip benefit vision-and-language tasks? arXiv preprint arXiv:2107.06383 (2021)
  * [39] Su, W., Zhu, X., Cao, Y., Li, B., Lu, L., Wei, F., Dai, J.: Vl-bert: Pre-training of generic visual-linguistic representations. In: ICLR (2020)
  * [40] Sun, S., Chen, Y.C., Li, L., Wang, S., Fang, Y., Liu, J.: Lightningdot: Pre-training visual-semantic embeddings for real-time image-text retrieval. In: NAACL-HLT (2021)
  * [41] Tan, H., Bansal, M.: Lxmert: Learning cross-modality encoder representations from transformers. In: EMNLP (2019)
  * [42] Tu, R.C., Ji, L., Luo, H., Shi, B., Huang, H.Y., Duan, N., Mao, X.L.: Hashing based efficient inference for image-text matching. In: Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021. pp. 743–752 (2021)
  * [43] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. In: NeurIPS (2017)
  * [44] Wang, L., Li, Y., Huang, J., Lazebnik, S.: Learning two-branch neural networks for image-text matching tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence (2018)
  * [45] Wang, W., Bao, H., et al.: VLMo: Unified vision-language pre-training with mixture-of-modality-experts. arXiv (2021)
  * [46] Wang, Z., Liu, X., Li, H., Sheng, L., Yan, J., Wang, X., Shao, J.: Camp: Cross-modal adaptive message passing for text-image retrieval. In: ICCV (2019)
  * [47] Wang, Z., Yu, J., et al.: SimVLM: Simple visual language model pretraining with weak supervision. arXiv preprint arXiv:2108.10904 (2021)
  * [48] Wu, Y., Schuster, M., et al.: Google’s neural machine translation system: Bridging the gap between human and machine translation. CoRR (2016)
  * [49] Xue, H., Huang, Y.a.: Probing inter-modality: Visual parsing with self-attention for vision-language pre-training. arXiv preprint arXiv:2106.13488 (2021)
  * [50] Zhang, P., Li, X., Hu, X., Yang, J., Zhang, L., Wang, L., Choi, Y., Gao, J.: Vinvl: Revisiting visual representations in vision-language models. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 5579–5588 (2021)
  * [51] Zhang, Q., Lei, Z., Zhang, Z., Li, S.Z.: Context-aware attention network for image-text retrieval. In: CVPR (2020)


scaletikzpicturetowidth[1]

# Unfreezing Social Navigation: Dynamical Systems based Compliance for Contact
Control in Robot Navigation

Diego Paez-Granados1†, Vaibhav Gupta 2, Aude Billard2 † is the corresponding
author. 1 D.Paez-Granados was with LASA, EPFL during this work, and currently
is with the SCAI Lab at SPZ, ETH Zurich, Switzerland<EMAIL_ADDRESS>Gupta,
and A. Billard are with the Learning Algorithms and Systems Laboratory (LASA),
Swiss Federal School of Technology in Lausanne - EPFL, Switzerland
{vaibhav.gupta<EMAIL_ADDRESS>
###### Abstract

Large efforts have focused on ensuring that the controllers for mobile service
robots follow proxemics and other social rules to ensure both safe and
socially acceptable distance to pedestrians. Nonetheless, involuntary contact
may be unavoidable when the robot travels in crowded areas or when
encountering adversarial pedestrians. Freezing the robot in response to
contact might be detrimental to bystanders’ safety and prevents it from
achieving its task. Unavoidable contacts must hence be controlled to ensure
the safe and smooth travelling of robots in pedestrian alleys. We present a
force-limited and obstacle avoidance controller integrated into a time-
invariant dynamical system (DS) in a closed-loop force controller that let the
robot react instantaneously to contact or to the sudden appearance of
pedestrians. Mitigating the risk of collision is done by modulating the
velocity commands upon detecting a contact and by absorbing part of the
contact force through active compliant control when the robot bumps
inadvertently against a pedestrian. We evaluated our method with a personal
mobility robot -Qolo- showing contact mitigation with passive and active
compliance. We showed the robot able to overcome an adversarial pedestrian
within 9 N of the set limit contact force for speeds under 1 m/s. Moreover, we
evaluated integrated obstacle avoidance proving the ability to advance without
incurring any other collision.

###### Index Terms:

Mobile Service Robots, Human-Robot Interaction, Force control, Compliance and
Impedance Control

##  I Introduction

As a consequence of the widespread diffusion of mobile robots in public
environments, the chances that robots and bystanders may collide will
increase. Looking at the statistics in the automotive sector, the number of
crashes involving pedestrians is a considerable portion of the total number of
accidents [1]. Real-life implementations of any obstacle avoidance are limited
by the reactivity of the robot i.e. kinematic and dynamic constraints,
actuation power, and highly limited computational resources on mobile robots.
Robots cannot behave like pedestrians. Most of the service robots are non-
holonomic and cannot step on the side. They are also less reactive and lacks
the means to communicate their intended move in easily interpretable ways, and
are rarely knowledgeable of proxemics and other social rules [2]. Nonetheless,
the utility of mobile service robots is getting traction and valuable services
such as in-hospital assistance, last-mile deliveries (Starship Inc. USA),
autonomous cleaning robots (Bluebotics, Switzerland) and autonomous
wheelchairs (Whill Inc. Japan) are becoming popular.

Similarly to what happened with industrial collaborative robots [3, 4],
chances are high that deployment will proceed and that society will slowly
accept and allow physical contact between mobile robots and humans, especially
in crowded environments [5]. Hence, there is some urgency to develop control
approaches and design requirements to mitigate risks and allow motion control
in post-contact between a pedestrian and a service robot.

Figure 1: An adversarial pedestrian colliding with a service robot that senses
the collision and absorbs part it of through active compliance. The robot
finds a feasible path by sliding with a contact-aware surface towards the
opposite direction of detected pedestrians.

Most attention has been given to pre-collision planning [4, 6] and human
motion prediction [7, 8]. As far as physical collisions between humans and
robots are concerned, efforts were solely directed at evaluating collisions
with collaborative robot arm manipulators [9, 3, 10]. These works were
instrumental and led to the ISO 15066:2016 [11] standard that establishes
values for pain thresholds for blunt impacts with respect to force and
pressure, after collisions with a robotic arm for determining what should be
its operational velocity around humans. However, there is no equivalent
standard for collision with light-weight vehicles [12].

Mutual anticipation remains critical in ensuring that humans can navigate
safely in crowded environments [13]. Nonetheless, pedestrians’ expectations of
robots’ motion capabilities may exceed robots’ actual motion constraints,
thereby increasing the risk of misinterpreted reciprocal avoidance. Currently,
the basic safety control system let the robot freeze as soon as it perceives a
contact [14], a reaction that would most likely be unexpected by pedestrians
and lead to more dangerous collisions with pedestrians stumbling on the robot.
This may be particularly the case, considering that collisions would occur
within highly dynamic environments such as malls, airports, hospitals,
markets, or mix-traffic areas where pedestrians, mobility devices, and even
vehicles are frequent. Herewith, making a ”frozen” robot a danger to itself
and bystanders [15]. In this work, we investigate a possible less dangerous
and better accepted post-collision reaction that avoids the ”freezing” robot
problem.

We extend our dynamical systems (DS) based obstacle avoidance controller [16],
by augmenting it with a compliant control mechanism, using a passive DS
approached offered in [17]. Assuming that we have real-time contact sensing in
closed-loop control, we enable impedance control for our mobile robot through
estimated contact forces over a known hull, following our previous approach
for explicit force modulation for collaborative robot environments developed
in [18]. Unlike previous works on DS-based compliance, in our formulation the
obstacle’s exact shape and contact location are unknown. Thus, we simplify the
problem by assuming a single contact point and use the only information at our
disposal, namely the hull shape of the robot, for controlling the desired
force during the interaction.

A similar principle for closed-loop force control with 6-axes Force/Torque was
offered in [19] with a focus on learning touch commands on a stiff hull. While
the method in [20] offered an impedance control response when guiding a
person’s motion while limiting the maximum guidance force. Our control
approach offers the reactivity of time-invariant DS combined with contact
estimations of impacts through a compliant bumper, herewith ensuring impact
absorption through passive and active compliance for mitigating unexpected
impacts with mobile robots.

We validate the method on the semi-autonomous standing mobility vehicle Qolo
[21, 22] shown in Fig. 1; a type of powered wheelchair for standing mobility
of lower-limb impaired people, similar to powered scooters, hoverboards, and
unicycles, currently widespread. We tested the approach to validate
performance at mitigating contact forces by generating multiple collisions
with a static obstacle varying the speed at contact. We show that the robot
could successfully slide against the obstacle without exceeding the limit on
contact force. Although current implementation relies on the assumption of
single contact, this could be extended with higher sensing resolution such as
multi-contact sensing in mobile manipulators through artificial skin [23], or
through other sensing methods [24]. The source code and simulations with other
robot types is available at: https://github.com/epfl-lasa/sliding-ds-control
[25].

The remaining of this paper is organized as follows: We present the method and
controller in section II. We describe the controller structure with high-level
obstacle avoidance in section III. We evaluate the method in section IV.
Finally, we discuss and conclude in section V.

##  II Problem Statement

In this formulation for post-collision control, we assumed:

  1. 1.

Knowledge of the expected contact surface, namely a convex human body part.

  2. 2.

A collision could occur unexpectedly, thus, distance to the obstacle is
unknown a priori.

  3. 3.

Expected contact occurs at a single location per sensing surface.

  4. 4.

The operational speed of the robot is slow enough to be safe in the transient
phase thus, controllable post-collision.

In Fig. 2 we depicted a linear-DS with the robot represented as a holonomic
point-mass (any point in this Cartesian space) and the pedestrian in contact
as a convex shape. There are two zones of contact with the obstacle
represented by: first, a physically impenetrable obstacle (dark grey), and
second, a deformable region of the obstacle with a compliant boundary (dotted
line) which allows controlling for safe contact force. Finally, we mark a
sliding zone (lighter-grey) that represents the volume occupied by the robot
during contact around the obstacle. The resulting behaviour of the system is a
force bounded sliding contact around the obstacle after entering in contact
with the compliant boundary, assuming that there will be a state where the
modulated DS will lead away from the contact surface without colliding with
other obstacles.

### Controller Formulation

Figure 2: Sliding DS formulation for limiting contact forces while moving
along an underlying desired motion. When the robot enters in contact with the
obstacle (light-grey zone) the desired motion is controlled by the reaction
force at the boundary guaranteeing a limited contact force $F_{n}$ to the
obstacle and allowing a sliding motion $\xi_{d}$ around it.

In order to derive the motion controller, we modelled the robot dynamics as:
$M\ddot{\xi}+C\dot{\xi}=\tau_{c}+\tau_{e}$, where $\dot{\xi}\in\mathbb{R}^{2}$
represents the robot’s Cartesian velocity as a time invariant position
dependent dynamical system. $M\in\mathbb{R}^{2\times 2}$ corresponds to the
virtual mass of the robot, $C\in\mathbb{R}^{2\times 2}$ accounts for
centrifugal and Coriolis terms, $\tau_{c}$ represents the control forces and
$\tau_{e}$ any external disturbances to be rejected. An impedance-DS is used
to achieve a sliding motion for overcoming the obstacle. We design a nominal
trajectory controlling for the robot’s speed and generated through a function
$f({\xi})\in\mathbb{R}^{2}$. We then control for the torques using a damped
tracking controller over $f({\xi})$ ,

$\displaystyle\tau_{c}$ $\displaystyle=$
$\displaystyle\lambda_{t}f(\xi)-D\dot{\xi}$ (1)

where $D\in\mathbb{R}^{2\times 2}$ represents a negative defined damping
effect. $f(\xi)$ is the dynamical system effectively controlling the robot
during contact, composed as: $f(\xi)=f_{u}(\xi)+f_{n}(\xi)$, where
$f_{u}(\xi)$ represents the driving force generated by the nominal DS input
tangential to the collision surface which can be transformed into the contact
dynamics as:

$\displaystyle f_{u}(\xi)$ $\displaystyle=$
$\displaystyle\hat{t}^{T}\frac{M\dot{\xi}_{u}}{T_{s}}\hat{t}$ (2)

where $T_{s}$ accounts for a discretizing time constant. $f_{n}(\xi)$
describes the force control function as:

$\displaystyle f_{n}(\xi)$ $\displaystyle=$
$\displaystyle\frac{F_{n}+F_{c}}{\lambda_{t}}\hat{n}$ (3)

where $F_{n}$ was chosen a contact force limit bounded by safety and
acceptability, while $F_{c}$ represents the measured contact force. Yielding a
controller of the form:

$\displaystyle\tau_{c}$ $\displaystyle=$
$\displaystyle\lambda_{t}f_{u}(\dot{\xi})+(F_{n}+F_{c})\hat{n}-D\dot{\xi}$ (4)

The damping effect on the matrix $D$ was controlled by a normal and tangential
parameters over the surface of the obstacle, $\lambda_{n}$ and $\lambda_{t}$,
respectively.

$\displaystyle D$ $\displaystyle=$ $\displaystyle
Q\begin{bmatrix}\lambda_{t}&0\\\ 0&\lambda_{n}\\\ \end{bmatrix}Q^{T}$ (5)

where $Q=\begin{bmatrix}\hat{t}&\hat{n}\end{bmatrix}$ was defined by the
contact location normal. The parameter $\lambda_{t}$ allow to control the
behaviour around the surface, for instance by setting $\lambda_{t}=0$ we can
provide an undamped free motion along the tangential direction of the
collision surface.

Finally, transformation to the velocity domain of the robot was done by a
first order Taylor expansion, thus the control for a desired velocity
$\dot{\xi}_{d}$ can be written as,

$\displaystyle\dot{\xi}_{d+1}$ $\displaystyle=$
$\displaystyle\frac{T_{s}}{M}\left((F_{n}+F_{c})\hat{n}-D\dot{\xi}_{d}\right)+\hat{t}^{T}\dot{\xi}_{u}\hat{t}$
(6)

#### Releasing contact:

Equation 6 allows the robot to slide over the obstacle while limiting a
constant contact force ($F_{n}$), but it does not allow the robot to move away
from the obstacle. Thus, we defined an additional term in (6)
($\hat{n}^{T}\dot{\xi}_{u}\hat{n}$) when the normal vector and underlying
dynamical system desired motion oppose each other. Herewith, enabling the
robot to move away from the obstacle if the DS indicates a feasible free-
motion space.

Then, the final controller is defined as:

$\displaystyle\dot{\xi}^{\prime}_{d+1}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\dot{\xi}_{d+1}+\hat{n}^{T}\dot{\xi}_{u}\hat{n}&\mbox{if
}\left<\hat{n},\dot{\xi}_{u}\right><0\\\
\dot{\xi}_{d+1}&\mbox{otherwise}\end{array}\right.$ (9)

#### Velocity magnitude

When required by the robot application, the driving underlying DS magnitude
could be upper bounded by $|\dot{\xi}_{u}|\ <|\dot{\xi}_{max}|$, hereby,
guaranteeing a controllable speed allowed during contact interaction around
the obstacle.

#### Moving target

In case of a traceable moving obstacle in contact, we can include such
estimation of the obstacle’s motion to the previous formulation by defining
the robot’s state relative to the obstacle’s pose ($\xi=x_{r}-x_{o}$). This
effectively makes the desired motion $\dot{\xi_{d}}$ dependent on the
obstacle’s response. The DS, hence, speeds up or slows down according to the
obstacle’s speed while controlling the desired contact force. Such behaviour
requires explicit velocity estimation of the obstacle in contact. This
estimate could be local, using, for instance, optical flow from a fish-eye
camera or laser-based tracker of objects in close vicinity. While this
requires the placement of more sensors, such as sensors scanning space on the
side of the robot, this could enhance fluidity social navigation in
interactions with a crowd flow or other dynamic obstacles.

Figure 3: Sliding Dynamical System coupled with modulated obstacle avoidance
example of a pre-collision and post-collision response. Here, multiple moving
obstacles were modulated (red) in a linear-DS while a moving adversarial
obstacle (grey) collided with the robot, forcing a sliding response while
avoiding other obstacles.

Fig. 3 depicts a linear-DS towards an attractor (green mark) modulated by the
surrounding moving obstacles. An example of a mobile robot navigation in 2D.
The resulting DS acts as the input to the proposed compliant modulation when
an ”adversarial” obstacle (invisible to the modulation) gets in contact
(sensed by penetration and simulated with a constant mass-spring system),
which triggers the compliant controller and enables a sliding behaviour around
it while avoiding all other moving obstacles.

##  III Control architecture and Sliding surface

Figure 4: Compliant controller architecture proposed for the modulated and
passive Dynamical System handling the post-collision through sliding.

We based the robot’s control architecture on a continuous controller that
handles three states of the mobile robot, namely: obstacle avoidance, contact,
and post-collision control. Fig. 4 describes the general controller in three
stages. First a high-level closed-loop motion planner drives the dynamics of
the robot in its control space ($\dot{x}_{u}$). While we used a modulated DS
[16] for obstacle avoidance, any other velocity-based planners could be used
here, e.g, in the case of velocity obstacles (VO) based obstacle avoidance
through the formulation in [26]. Second, control of compliance and contact
force through sliding method using a known sensing surface over the robot’s
hull with a limited contact force $F_{n}$. Ensuring that the robot reacts to
unexpected contacts and advances with a sliding manoeuvre should the
underlying obstacle avoidance lead away from the contact surface without
colliding with other obstacles. Third, a low-level controller that handles the
execution in real-time closed-loop control.

###  III-A Control Point over the Robot’s Surface

To execute the control in a mobile robot we need to include a transformation
between the robot’s control space and a control point ($c$) around the bumper
shape by using the estimated collision location over the bumper surface at an
angle $\gamma$. Which was estimated as $c=(o\cos{\gamma},o\sin{\gamma})$ from
the center of the bumper (see Fig. 5).

Thus, we control the effective velocity ($\dot{\xi}_{u}$) at the point of
collision perpendicular to the bumper surface by transforming it to the
control space of the robot.

The surface at the control point can be described using the normal ($\hat{n}$)
and tangential ($\hat{t}$) unit vectors,

$\displaystyle\hat{n}$ $\displaystyle=$
$\displaystyle(\cos{\gamma},\sin{\gamma})$ (10) $\displaystyle\hat{t}$
$\displaystyle=$ $\displaystyle(-\sin{\gamma},\cos{\gamma})$ (11)

Then, we can define a Jacobian matrix ($J$) to transform the motion at center
of the robot $x$ (in the case of Qolo, a non-holonomic differential wheel
system) to an effective velocity ($\dot{\xi}_{u}$) at the control point on the
surface in contact (holonomic):

$\displaystyle\dot{\xi_{u}}$ $\displaystyle=$ $\displaystyle J\dot{x}_{u}$
$\displaystyle=$ $\displaystyle\begin{bmatrix}1&-o\sin{\gamma}\\\
0&o\cos{\gamma}\end{bmatrix}\begin{bmatrix}v_{u}\\\ \omega_{u}\end{bmatrix}$

With a known hull surface (see Fig. 5) described as,

$\displaystyle O$ $\displaystyle=$
$\displaystyle\sqrt{\left(o\sin{\gamma}\right)^{2}+\left(l+o\cos{\gamma}\right)^{2}}$
(13) $\displaystyle\beta$ $\displaystyle=$
$\displaystyle\tan^{-1}{\left(\frac{o\sin{\gamma}}{l+o\cos{\gamma}}\right)}$
(14)

With the system controlled in the velocity space of the robot we map the DS
through the following:

$\displaystyle\dot{\xi}_{u}$ $\displaystyle=$ $\displaystyle
v_{u}\cos{\gamma}+\omega_{u}O\sin{\left(\gamma-\beta\right)}$ (15)

where, $v_{u}$ and $\omega_{u}$ are the desired linear and angular velocities
defined by the high level planner resp.

Finally, we transform back to the robot’s control space
($\dot{x}_{d}=J^{-1}\dot{\xi}^{\prime}_{d+1}$) through the inverse of the
Jacobian.

Figure 5: Implemented structure for compliant control in real-life scenarios
through a frontal bumper on a person carrier type service robot.

###  III-B Non-linear compliance compensation

The impact absorbing bumper (see Fig. 5) was designed as a compliant surface
light-weighted ($900\text{\,}\mathrm{g}$) in ABS material, mounted on a 6 axis
force/torque (FT) sensor (Botasys Rokubi 2.0) at the centre of the semi-
circular bumper. The bumper was mounted through a padding material to the hard
surface of the robot frame with spring-loaded screws at each side of the
mount, thus, releasing part of the weight to the main frame of the robot.
Herewith, mitigating the impact during the transient phase. Unlike the work in
[19] where a stiff hull was developed mounted on an FT sensor. However, this
brings a challenge in accurately estimating contacts on the surface of the
hull, which we have tackled by learning the non-linearity of the passive-
compliance through data of known impact forces.

To remove the effects of the non-rigidity of the bumper (see Fig. 5), a
prediction model was developed through 2 methods, first with a support vector
regression (SVR), and secondly with a recurrent neural network (RNN), where we
chose the second in implementation.

We trained the models with a known force applied to the bumper at various
locations through an second FT sensor impacting the bumper surface. Then, the
effective force and moment at the onboard FT sensor were estimated assuming a
rigid model of the bumper. The non-linear model was trained over the measured
FT values from the onboard sensor to find $F_{x}$, $F_{y}$, and $M_{z}$. We
use three independent models to get corrections over $F_{x}$, $F_{y}$ and
$M_{z}$.

Assumptions: First, other components of the forces ($M_{x}$, $M_{y}$ and
$F_{z}$) are significantly smaller thus can be neglected. Second, the model
removes all non-rigidity effects from the sensor measurements, herewith, we
can consider the bumper as a rigid body on the robot’s structure. Third, we
only account for pure forces applied at the point of contact.

The calibration dataset consisted of slow and fast force variations on the
bumper at various force magnitudes, impulse responses at various force
magnitudes, and pulls on the bumper to cancel any undesired behaviour. The
dataset was generated by applying a known force (using a FT sensor) on a
$9\times 4$ grid on the bumper. For each type of force profile, 3 samples of
$60\text{\,}\mathrm{s}$ of impacts were recorded at
$400\text{\,}\mathrm{H}\mathrm{z}$ at each point on the grid. Further details
of the data and implementation of SVR and RNN are available in the online
repository [25].

##### Contact force estimation comparison SVR vs. RNN

The calibration dataset is divided into $9:1$ split with $9$ part for training
and $1$ part for validation. In this paper, on one hand, a $\nu$-SVR [27] was
trained over the training dataset resulting in approximately $92,000$ support
vectors for each axis. On the other hand, for the RNN, a single LSTM layer
with a buffer of 6 samples was implemented. The output of the LSTM layer was
then fed to a neural net for each of the desired force. Because of the lower
estimation error ($<15N$) and fastest processing time ($<0.4s$), we choose the
RNN for real-time usage in the robot (as shown in table I).

TABLE I: Error Comparison between SVR and RNN for 3D Contact Estimation on the Compliant Bumper |  | SVR | RNN
---|---|---|---
Training Performance |  $F_{x}$ [$\mathrm{N}$] | $-0.81\pm 15.82$ | $-0.19\pm 8.25$
$F_{y}$ [$\mathrm{N}$] | $21.68\pm 42.53$ | $-0.95\pm 13.08$
$M_{z}$ [$\mathrm{N}\,\mathrm{m}$] | $0.06\pm 20.20$ | $-0.06\pm 1.01$
Testing Performance |  $F_{x}$ [$\mathrm{N}$] | $-3.93\pm 31.67$ | $-0.16\pm 9.99$
$F_{y}$ [$\mathrm{N}$] | $36.55\pm 46.55$ | $-4.36\pm 14.99$
$M_{z}$ [$\mathrm{N}\,\mathrm{m}$] | $-1.09\pm 16.10$ | $0.10\pm 0.82$
On-board Computation Time [$\mathrm{ms}$] | $10.63$ | $0.383$

###  III-C Contact location estimation

We estimated the collision angle from the reference coordinate system at the
sensor $\gamma$ from $F_{x}$, $F_{y}$, and $M_{z}$, as
$M_{z}=F_{x}r\cos{\gamma}-F_{y}r\sin{\gamma}$. Note that $F_{x}$ and $F_{y}$
at the point of contact and the sensor are assumed the same as described
above. By replacing $\sin$ and $\cos$ by $\frac{e^{i\gamma}-e^{-i\gamma}}{2}$
and $\frac{e^{i\gamma}+e^{-i\gamma}}{2}$ respectively, we get eq. 16. Eq. 17
describes explicitly the $\gamma$ by solving the quadratic equation in
$e^{i\gamma}$.

$\displaystyle\frac{M_{z}}{r}$ $\displaystyle=$ $\displaystyle
F_{x}\left(\frac{e^{i\gamma}+e^{-i\gamma}}{2}\right)+iF_{y}\left(\frac{e^{i\gamma}-e^{-i\gamma}}{2}\right)$
(16) $\displaystyle\gamma$ $\displaystyle=$
$\displaystyle-i\log{\left(\frac{\frac{M_{z}}{r}+i\sqrt{F_{x}^{2}+F_{y}^{2}-\left(\frac{M_{z}}{r}\right)^{2}}}{F_{x}+iF_{y}}\right)}$
(17)

Finally, the force magnitude $F_{mag}$ can be estimated as
$F_{mag}=F_{x}\sin{\gamma}+F_{y}\cos{\gamma}$.

##  IV Experimental Evaluation

For evaluation in combination with obstacle avoidance in close to real-life
expected situations, we equipped the robot Qolo [22] with 2 Lidars (Velodyne
VLP-16), and an RGBD sensor (Intel Realsense). Obstacle’s tracking was
performed through real-time people detection implemented through a pipeline of
sensing fusion of Lidar-based detection by DR-SPAAM [28] and RGBD detection
through YOLO [29]. The full controller repository can be found here: Qolo-ROS
[30]. The control parameters were set as follows, he discretizing time
constant ($T_{s}$) to the sampling time of the control loop
($200\text{\,}\mathrm{H}\mathrm{z}$) for real-time controller dynamics. The
virtual robot mass ($M$) was set to $2\text{\,}\mathrm{k}\mathrm{g}$ for
light-behaviour. Damping parameters $\lambda_{t}$ and $\lambda_{n}$ were set
to $0$ and $0.5$ respectively to allow undamped tangential motion and
partially damped normal motion of the collision surface.

(a) Collision force.  (b) Time until stable compliant control (transient
time).

Figure 6: Resulting post-collision contact force response to changes in the
operational speed at the time for achieving a stable active compliance.

###  IV-A Contact Control Evaluation at Multiple Speeds

First, we evaluated the effects of increasing the operational speed of the
robot on the post-collision force response with the proposed controller, to
understand the effect of the approach for real-life contact situations. We run
five sets of collisions per condition between the mobile robot Qolo
($45\text{\,}\mathrm{k}\mathrm{g}$) and a static person
($80\text{\,}\mathrm{k}\mathrm{g}$). The contact force limit for compliance
was set to $F_{n}=$45\text{\,}\mathrm{N}$$ (well below the average pain
threshold for the lower legs $130\text{\,}\mathrm{N}$ [11]). While the desired
motion ($\dot{\xi}_{u}$) was set to a linear-DS (ignoring the obstacle)
towards an attractor at $4.5\text{\,}\mathrm{m}$ ahead of the robot.

The tests were conducted at four operational speeds of
$0.5\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}0.75\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}1.0\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}1.25\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$,
by setting the robot to approach the person (only the authors) frontally and
about $0.1\text{\,}\mathrm{m}$ of the line of motion, thus impacting the
bumper at $\gamma=\pi/6$. The post-contact speed magnitude $|\dot{\xi}_{max}|$
was set to $0.5\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$.

We observed a peak collision force over $150\text{\,}\mathrm{N}$ in most
cases, as expected for the transient phase (see, Fig. 6(a)), given the overall
delay of the control system (passive-compliance is needed for absorbing part
of the impact). The mean collision force was $52\pm 9\text{\,}\mathrm{N}$ for
speeds up to $1\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$, and $51\pm
15\text{\,}\mathrm{N}$ for the highest speed of
$1.25\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$. All contact forces during
sliding were well within the desired limit of $65\text{\,}\mathrm{N}$ ($50\%$
of the pain threshold). Results are summarized in table II. The mean transient
phase time (time to stabilise the compliance control) showed a difference
between impacts below $1\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$ with $1.06\pm
0.46\text{\,}\mathrm{s}$, while for impacts at
$1.25\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$ presented a slower response of
$1.84\pm 0.75\text{\,}\mathrm{s}$ (see, Fig. 6(b)). Further control parameter
settings are detailed in the supplementary repository [25].

###  IV-B Evaluation with Integrated Obstacle Avoidance

(a) Snapshot of the experiment where an adversarial pedestrian intentionally
collides with the robot while a driver sets the desired velocity.

(b) Velocity obstacles based control with a user a high-level input, a
limiting contact force $F_{n}=$30\text{\,}\mathrm{N}$$, resulting in $25.88\pm
8.90\text{\,}\mathrm{N}$.

(c) Modulated DS mode with a limiting contact force
$F_{n}=$45\text{\,}\mathrm{N}$$, resulting in $49.18\pm
11.97\text{\,}\mathrm{N}$.

Figure 7: Experimental setup of obstacle avoidance and post-collision control
scenario with an adversarial pedestrian.

We further tested the approach in autonomous driving mode and contrasted two
obstacle avoidance methods: first modulated obstacles DS from [16] and second,
a variant on the Velocity-obstacle (VO) that solves operator given commands
with the known shape of the robot [26]. We recorded three tests per method
with a safe operational velocity
($\dot{\xi}_{u}=$0.65\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$$) and sliding
velocity ($|\dot{\xi}_{max}|=$0.5\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$$).
Results in Fig. 7(a) shows an illustration of the experimental scenario, where
an adversarial pedestrian jumps in front of the robot from behind another
pedestrian faster than the physical limits of the robot’s actuation, thus
producing a collision. In both examples (see Fig. 7(b)-7(c)) there is the
first stage of transient impact (left figure, shaded area) beyond any control
on the robot (passive-compliance is needed for absorbing part of the impact).
Subsequently, the compliant controller limits the contact interaction (active
compliance phase) to the set force value ($F_{n}$), while performing the
sliding motion around the obstacle as long as there is no other pedestrian on
its path.

TABLE II: Post-collision force statistics |  | Mean Force [$\mathrm{N}$] | Std. Deviation [$\mathrm{N}$]
---|---|---|---
Robot Speed [̇$\mathrm{m}\mathrm{/}\mathrm{s}$] | $0.5$ | $42.74$ | $6.18$
$0.75$ | $48.04$ | $9.01$
$1.0$ | $52.51$ | $9.07$
$1.25$ | $51.64$ | $15.37$
Control Type | VO control | $46.08$ | $6.97$
MDS Control | $54.57$ | $5.63$

Results showed performance of contact force error of $9.5\pm
5.6\text{\,}\mathrm{N}$, and $1.0\pm 6.9\text{\,}\mathrm{N}$ for MDS and VO
modes resp. (see, table II). In VO mode (with an operator on-board) the
heavier robot was more controllable, achieving a smaller error in comparison
with MDS mode. Results of the trajectory response showed in VO mode that the
user was able to overcome the adversarial pedestrian by drifting away quicker
from contact, thus trajectories deviated further from the linear path (see,
Fig. 7(b) right side). In contrast, the MDS control made longer contact with
the obstacle, moving around it, thus the overall trajectories were closer to
the original linear DS (see, Fig. 7(c) right side).

##  V Summary and Discussion

We have presented a control method for a mobile service robot to achieve a
reactive control on post-collision which allows to absorb part of the impact
and continue moving by sliding around the pedestrian. Herewith, proposing an
alternative solution to the common ”safe” approach of freezing a robot upon
contact.

The experimental assessment at multiple operational speeds allowed us to
illustrate the approach in real-life operations. In the case of the robot
Qolo, we found the current control system capable of recovering from an
unexpected collision within $1\text{\,}\mathrm{s}$ of the impact when driving
below $1\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$, and navigating around the
unforeseen obstacle.

The results with integrated obstacle avoidance showed a robot able to overcome
a pedestrian in both tested methods, namely, modulated dynamical systems (DS)
and velocity obstacles (VO). In both cases without incurring further contact
with bystanders, and within desired limits of ”safe” contact force. Among the
two methods, a smoother trajectory was achieved in DS controlled motions,
whereas user-driven VO tests showed lower contact forces. A likely result of
the user decision of drifting away quicker from contact, which in turn
resulted in a larger deviation from the initial trajectory.

Future work should look more closely at how to handle multiple contacts. As
well, investigate how pedestrian responses to contact and its effect to the
robot planner for social acceptability and safety.

## Acknowledgement

This work was funded by the EU H2020 project ”Crowdbot” (779942). The
experiments were approved with an ethical protocol by the human research
ethical committee of EPFL (Approval No: HREC-032-2019). We thank K. Suzuki and
the University of Tsukuba for lending the robot Qolo used in this experiment.
Disclaimer: DP holds a patent of the robot Qolo and shares in the company Qolo
Inc.

## References

  * [1] J. Anderson, N. Kalra, K. Stanley, P. Sorensen, C. Samaras, and O. Oluwatola, _Autonomous Vehicle Technology: A Guide for Policymakers_ , 1st ed. Santa Monica, Calif.: RAND Corporation, 2016.
  * [2] K. Charalampous, I. Kostavelis, and A. Gasteratos, “Recent trends in social aware robot navigation: A survey,” _Robotics and Autonomous Systems_ , vol. 93, pp. 85–104, 2017. [Online]. Available: http://dx.doi.org/10.1016/j.robot.2017.03.002
  * [3] M. J. Rosenstrauch and J. Kruger, “Safe human-robot-collaboration-introduction and experiment using iso/ts 15066,” in _2017 3rd International Conference on Control, Automation and Robotics (ICCAR)_ , 2017, pp. 740–744.
  * [4] S. Haddadin, A. De Luca, and A. Albu-Schäffer, “Robot collisions: A survey on detection, isolation, and identification,” _IEEE Transactions on Robotics_ , vol. 33, no. 6, pp. 1292–1312, 2017.
  * [5] M. C. Shrestha, Y. Nohisa, A. Schmitz, S. Hayakawa, E. Uno, Y. Yokoyama, H. Yanagawa, K. Or, and S. Sugano, “Using contact-based inducement for efficient navigation in a congested environment,” in _2015 24th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN)_ , Aug 2015, pp. 456–461.
  * [6] A. Bajcsy, S. Bansal, E. Ratner, C. J. Tomlin, and A. D. Dragan, “A Robust Control Framework for Human Motion Prediction,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 1, pp. 24–31, 2021.
  * [7] Y. Kobayashi, T. Sugimoto, K. Tanaka, Y. Shimomura, F. J. Arjonilla Garcia, C. H. Kim, H. Yabushita, and T. Toda, “Robot Navigation Based on Predicting of Human Interaction and its Reproducible Evaluation in a Densely Crowded Environment,” _International Journal of Social Robotics_ , 2021. [Online]. Available: https://doi.org/10.1007/s12369-021-00791-9
  * [8] D. Fridovich-Keil, A. Bajcsy, J. F. Fisac, S. L. Herbert, S. Wang, A. D. Dragan, and C. J. Tomlin, “Confidence-aware motion prediction for real-time collision avoidance1,” _International Journal of Robotics Research_ , vol. 39, no. 2-3, pp. 250–265, 2020.
  * [9] S. Haddadin, A. Albu-Schäffer, M. Strohmayr, M. Frommberger, and G. Hirzinger, “Injury evaluation of human-robot impacts,” in _Proceedings - IEEE International Conference on Robotics and Automation_ , no. 011838, 2008, pp. 2203–2204.
  * [10] S. Haddadin, A. Albu-SchäCurrency Signffer, and G. Hirzinger, “Requirements for safe robots: Measurements, analysis and new insights,” _International Journal of Robotics Research_ , vol. 28, no. 11-12, pp. 1507–1527, 2009.
  * [11] International Organization for Standarization, _ISO / TS 15066 Robots and robotic devices — Collaborative robots_ , E. K. für Normung, Ed. Geneva, Switzerland: ISO, 2016.
  * [12] P. Salvini, D. Paez-Granados, and A. Billard, “On the safety of mobile robots serving in public spaces: Identifying gaps in en iso 13482:2014 and calling for a new standard,” _ACM Transactions on Human-Robot Interaction_ , vol. 10, pp. 1–28, 2021.
  * [13] H. Murakami, C. Feliciani, Y. Nishiyama, and K. Nishinari, “Mutual anticipation can contribute to self-organization in human crowds,” _Science Advances_ , vol. 7, no. 12, 2021.
  * [14] A. J. Sathyamoorthy, U. Patel, T. Guan, and D. Manocha, “Frozone: Freezing-free, pedestrian-friendly navigation in human crowds,” _IEEE Robotics and Automation Letters_ , vol. 5, pp. 4352–4359, 7 2020.
  * [15] P. Salvini, D. Paez-Granados, and A. Billard, “Safety Concerns Emerging from Robots Navigating in Crowded Pedestrian Areas,” _International Journal of Social Robotics (SORO)_ , 2021. [Online]. Available: https://doi.org/10.1007/s12369-021-00796-4
  * [16] L. Huber, A. Billard, and J.-J. Slotine, “Avoidance of Convex and Concave Obstacles With Convergence Ensured Through Contraction,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 1462–1469, 2019. [Online]. Available: https://doi.org/10.1109/lra.2019.2893676
  * [17] K. Kronander and A. Billard, “Stability Considerations for Variable Impedance Control,” _IEEE Transactions on Robotics_ , vol. PP, no. 99, pp. 1298–1305, 2016.
  * [18] W. Amanhoud, M. Khoramshahi, and A. Billard, “A Dynamical System Approach to Motion and Force Generation in Contact Tasks,” in _Robotics: Science and Systems (RSS)_ , no. June, 2019. [Online]. Available: https://doi.org/10.15607/rss.2019.xv.021
  * [19] M. Kollmitz, D. Buscher, T. Schubert, and W. Burgard, “Whole-Body Sensory Concept for Compliant Mobile Robots,” _Proceedings - IEEE International Conference on Robotics and Automation_ , pp. 5429–5435, 2018.
  * [20] D. Paez-Granados, B. Yamamoto, H. Kamide, J. Kinugawa, and K. Kosuge, “Dance Teaching by a Robot: Combining Cognitive and Physical Human-Robot Interaction for Supporting the Skill Learning Process,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 3, pp. 1452–1459, 2017. [Online]. Available: https://doi.org/10.1109/LRA.2017.2671428
  * [21] D. Paez Granados, H. Kadone, and K. Suzuki, “Unpowered Lower-Body Exoskeleton with Torso Lifting Mechanism for Supporting Sit-to-Stand Transitions,” in _IEEE International Conference on Intelligent Robots and Systems_ , 2018, pp. 2755–2761. [Online]. Available: https://doi.org/10.1109/iros.2018.8594199
  * [22] D. Paez-Granados, H. Kadone, M. Hassan, Y. Chen, and K. Suzuki, “Personal mobility with synchronous trunk-knee passive exoskeleton: Optimizing human-robot energy transfer,” _IEEE/ASME Transactions on Mechatronics_ , vol. 1, pp. 1–12, 2022. [Online]. Available: https://doi.org/10.1109/TMECH.2021.3135453
  * [23] Q. Leboutet, E. Dean-Leon, F. Bergner, and G. Cheng, “Tactile-Based Whole-Body Compliance with Force Propagation for Mobile Manipulators,” _IEEE Transactions on Robotics_ , vol. 35, no. 2, pp. 330–342, 2019.
  * [24] K. S. Kim, T. Llado, and L. Sentis, “Full-body collision detection and reaction with omnidirectional mobile platforms: a step towards safe human–robot interaction,” _Autonomous Robots_ , vol. 40, no. 2, pp. 325–341, 2016.
  * [25] D. Paez-Granados and V. Gupta, “Compliant DS for Mobile Robots: sliding-ds-control,” 3 2022. [Online]. Available: https://github.com/epfl-lasa/sliding-ds-control
  * [26] D. J. Gonon, D. Paez-Granados, and A. Billard, “Reactive Navigation in Crowds for Non-holonomic Robots with Convex Bounding Shape,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 4728–4735, 2021. [Online]. Available: https://doi.org/10.1109/LRA.2021.3068660
  * [27] V. Kecman, T.-M. Huang, and M. Vogt, _Iterative Single Data Algorithm for Training Kernel Machines from Huge Data Sets: Theory and Performance_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 255–274. [Online]. Available: https://doi.org/10.1007/10984697_12
  * [28] D. Jia, A. Hermans, and B. Leibe, “DR-SPAAM: A Spatial-Attention and Auto-regressive Model for Person Detection in 2D Range Data,” in _International Conference on Intelligent Robots and Systems (IROS)_ , 2020\.
  * [29] G. Jocher, Y. Kwon, guigarfr, perry0418, J. Veitch-Michaelis, Ttayu, D. Suess, F. Baltacı, G. Bianconi, IlyaOvodov, Marc, e96031413, C. Lee, D. Kendall, Falak, F. Reveriano, FuLin, GoogleWiki, J. Nataprawira, J. Hu, LinCoce, LukeAI, NanoCode012, NirZarrabi, O. Reda, P. Skalski, SergioSanchezMontesUAM, S. Song, T. Havlik, and T. M. Shead, “ultralytics/yolov3: v9.5.0 - YOLOv5 v5.0 release compatibility update for YOLOv3,” Apr. 2021. [Online]. Available: https://doi.org/10.5281/zenodo.4681234
  * [30] D. Paez-Granados and V. Gupta, “ROS-based Qolo’s controller architecture for shared control and crowd navigation,” 3 2022. [Online]. Available: https://github.com/DrDiegoPaez/qolo_ros/