# Deep Cropping via Attention Box Prediction and Aesthetics Assessment

Wenguan Wang, and Jianbing Shen
Beijing Lab of Intelligent Information Technology,
School of Computer Science, Beijing Institute of Technology, China
Corresponding author: Jianbing Shen (shenjianbing@bit.edu.cn). This work was
supported in part by the National Basic Research Program of China (973
Program) (No. 2013CB328805), the National Natural Science Foundation of China
(61272359), and the Fok Ying-Tong Education Foundation for Young Teachers.
Specialized Fund for Joint Building Program of Beijing Municipal Education
Commission.

###### Abstract

We model the photo cropping problem as a cascade of attention box regression
and aesthetic quality classification, based on deep learning. A neural network
is designed that has two branches for predicting attention bounding box and
analyzing aesthetics, respectively. The predicted attention box is treated as
an initial crop window where a set of cropping candidates are generated around
it, without missing important information. Then, aesthetics assessment is
employed to select the final crop as the one with the best aesthetic quality.
With our network, cropping candidates share features within full-image
convolutional feature maps, thus avoiding repeated feature computation and
leading to higher computation efficiency. Via leveraging rich data for
attention prediction and aesthetics assessment, the proposed method produces
high-quality cropping results, even with the limited availability of training
data for photo cropping. The experimental results demonstrate the competitive
results and fast processing speed (5 fps with all steps).

##  1 Introduction

Figure 1: (a)-(c) Flowchart of our method. (d) Conventional methods apply
sliding-judging cropping strategy, which is time-consuming and violates
natural cropping procedure. (e) Our method works as a cascade of attention-
aware crop candidates generation and aesthetics-based crop window selection,
which handles photo cropping in a more natural manner and is achieved by a
neural network.

Consider Fig. 1 (a). How can we determine an appropriate crop for this
picture? It seems to be a natural choice that people first define a crop that
covers the desired or important region, and then, iteratively adjust the
position, size and ratio of the initial crop window until achieving visual-
quality-inspired result. This determining-adjusting cropping strategy brings
two advantages: (1) considering both attention and aesthetics in a cascaded
way; and (2) high computation efficiency since the searching space of the best
crop is only limited to the surrounding of the initial crop area.
Interestingly, however, most previous cropping approaches are proceeded in
another way. They usually generate a large number of sliding windows with
various ratios and sizes over all the positions, and find the optimal subview
via repeatedly computing attention scores [29, 40, 47, 3], or analyzing
aesthetics [32, 48] for all the sliding windows. This sliding-judging
strategy, as depicted in Fig. 1 (d), is companied with heavy computation load,
since the searching space would span all the possible subviews of the whole
image. Besides, compared with repeatedly calculating attention and/or
aesthetics scores over all the crop windows, arranging these two items in a
sequential order would be a more reasonable and time-saving choice.

In this paper, we design a deep learning based cropping method, which models
the cropping tasks as attention bounding box regression and aesthetics
classification problems. The network is learned for directly determining the
attention box that covers visually important area (the red rectangle in Fig. 1
(b)), which seems like people first placing a crop to cover important region.
Then the method generates cropping candidates (the yellow rectangles in Fig. 1
(b)) around the attention box and selects the one with the highest aesthetics
value as final crop (Fig. 1 (c)), as the process of human iteratively
adjusting initial crop and selecting the most beautiful crop window.

The proposed method approaches cropping task in a more natural and efficient
way, which has the following major characteristics and contributions:
Natural and unified deep cropping scheme. The cropping procedure is arranged
as a determining-adjusting process, where attention-guided cropping candidates
generation is cascaded by aesthetics-aware crop window selection, as
demonstrated in Fig. 1 (e). The tasks of attention box predication and
aesthetics assessment are achieved in a deep learning model, where attention
information is exploited for avoiding discarding important information, while
the aesthetics assessment is employed for ensuring the high aesthetic value of
cropping results. The deep learning model is based on fully convolutional
neural network, which naturally supports input images of arbitrary sizes, thus
avoiding undesired deformation for evaluating aesthetic quality.
High computation efficiency. Three strategies for enhancing computational
efficiency are proposed to achieve a fast processing speed of 5 fps. First,
instead of searching all the possible positions in an image domain via sliding
window, the approach directly regresses the attention box and generates far
less number of cropping candidates ($\thicksim~{}\\!\\!\\!1000$) around the
visual important areas. Second, the sub-networks of attention box prediction
and aesthetics assessment share several convolutional layers in the bottom.
The marginal cost for computing aesthetics estimate is decreased via sharing
convolutions with attention prediction task at test-time. Third, the approach
inherits the spirit of recent object detection algorithms [13, 35, 9], which
is trained to share convolutional features among cropping candidates on the
feature maps. The convolutional layers are only performed once on the entire
image (regardless of the number of cropping candidates), and then
convolutional features of cropping candidates are extracted from feature maps,
which avoiding applying the network to each cropping candidate for repeatedly
computing features.
Learning without sufficient cropping annotation. For applying deep leaning for
photo cropping, an important practical catch to that solution is training data
availability. The datasets for photo cropping are small-scale in deep learning
terms, and primarily support evaluation. Besides, the photo cropping sometimes
is a quite subjective problem which is difficult to offer a clear answer for
what is a ‘groundtruth’ crop. While the groundtruth for photo cropping is
difficult to access, datasets for human gaze prediction and photo aesthetics
assessment are more easily to obtain. In our method, the cropping task is
explicitly achieved via learning neural network on existing rich and high-
quality data for visual attention prediction and aesthetics assessment.

##  2 Related Work

In this section, we give a brief overview of recent works in three lines:
visual attention prediction, aesthetics assessment and photo cropping.

###  2.1 Visual Attention Prediction

Visual attention prediction aims to predict scene locations where a human
observer may fixate. Early attention models [16, 2] are typically based on
various low-level features (e.g., color, intensity, orientation), operating
and combining them at multiple scales to form a saliency map. In addition to
low-level features, some approaches [19, 1] try to employ high-level features
from person or face detectors learned from specific computer vision tasks.
Recently, driven by the success of deep learning in object recognition, many
deep learning based attention models [42, 23, 18, 33] are proposed, and
generally give impressive results. The output of traditional attention methods
is usually a gray-scale image that represents the visual importance of each
corresponding pixel in the image. However, in our approach, we try to predict
an attention bounding box, which covers the most informative regions of the
image.

###  2.2 Aesthetics Assessment

The main goal of aesthetics assessment is to imitate human interpretation of
the beauty of natural images. Many methods have been proposed for this topic,
we refer the reader to [5] for a more detailed survey. Traditionally,
aesthetic quality analysis is viewed as a binary classification problem of
predicting high- and low- quality images. Extracting visual features and then
employing various machine learning algorithms to predict photo aesthetic
values is a common pipeline in this research area.

Early methods [4, 20, 6] manually designed aesthetics features according to
photographic rules or practices, such as the rule of thirds and visual
balance. Instead of using hand-crafted features, other approaches [30, 38]
have been developed to leverage more generic image descriptors, such as Fisher
Vector and bag of visual words, which are previously used for image
classification but also capable of capturing aesthetic properties. In more
recent work [25, 41, 27, 21, 28], deep learning methods have been used to
aesthetics assessment and have shown promising results.

###  2.3 Photo Cropping

Cropping is an important operation for improving visual quality of digital
photos, which cuts away unwanted areas outside of a selected rectangular
region. A lot of methods have been proposed towards automating this task.
These methods, in general, can be categorized into attention-based or
aesthetics-based approaches. The attention-based approaches [29, 40, 3] focus
on preserving the main subject or visually important area in the scene after
cropping. These methods usually place the crop window over the most visually
significant regions according to certain attention scores [43, 44, 45, 46].
The other major direction of cropping methods is aesthetics-based approach
that emphasizes the general attractiveness of the cropped image. Those
aesthetics-based approaches [32, 48] are centered on composition-related image
properties. Taking various aesthetical factors into account, they try to find
the cropping candidate with the highest quality score.

In this paper, we consider both attention and aesthetics information, which
are arranged in a natural and cascaded manner. The proposed method approaches
photo cropping as a cascade of generating cropping candidates via attention
box prediction and selecting best crop according to aesthetics criteria. Our
method shares the spirit of recent object detection algorithms [13, 35, 9],
one branch of our network learns to predict the bounding box covers visually
important area, while the other one tries to analyze aesthetic value.

##  3 Our Approach

The cropping algorithm is decomposed into two cascaded stages, namely,
attention-aware cropping candidates generation (Sec. 3.1) and aesthetics-based
crop window selection (Sec. 3.2). It infers initial crop as a bounding box
covering the most visually important area, and then selects the best crop with
highest aesthetic quality from a few crop candidates generated around the
initial crop. We design a deep learning model that has two sub-networks:
Attention Box Prediction (ABP) network and Aesthetics Assessment (AA) network,
for achieving two key subtasks in above cropping process: (1) attention box
prediction for determining the initial crop; and (2) aesthetics assessment for
determining the final crop. Those two networks share several convolutional
blocks in the bottom and are based on fully convolutional network, which will
be detailed in following sections. Finally, in Sec. 3.3, we will give more
details of our model in training and testing.

###  3.1 Attention-aware Cropping Candidates

In this section, we introduce our method for cropping candidates generation,
which is based on an Attention Box Prediction (ABP) network. This network
takes an image of any size as input and outputs a set of rectangular crop
windows, each with a score that stands for the prediction accuracy. Then the
initial crop is identified as the most accurate one, and various cropping
candidates with different sizes and ratios are generated around it. After
that, the final crop is selected from those candidates according to their
aesthetic quality based on an Aesthetics Assessment (AA) network (Sec. 3.2).

The initial crop can be viewed as a rectangle that preserves the most
informative part of the image while has minimum area. This optimal rectangle
searching problem is a common task for attention-based cropping methods. Let
$P\in[0,1]^{w\times h}$ be an attention mask, we first define a set of crop
windows $\mathfrak{W}$:

$\displaystyle\mathfrak{W}=\\{W|\sum_{x\in W}P(x)>\lambda\sum_{x}P(x)\\},$ (1)

where $\lambda\in[0,1]$ is a fraction threshold. Then the optimum rectangle
$\dot{W}$ is defined as:

$\displaystyle\dot{W}=\mathop{\operatorname*{argmin}}_{W\in\mathfrak{W}}|W|.$
(2)

Equ. 2 can be solved via sliding window with $\mathcal{O}(w^{2}h^{2})$
computation complexity, while a recent method [3] shows it can be solved with
computation complexity of $\mathcal{O}(wh^{2})$.

Figure 2: (a) Input image. (b) Attention map. (c) Ground truth attention box
generation via [3]. (d) Positive (red) and negative (blue) defaults boxes are
generated for training ABP network according to ground truth attention box.

Differently, we design a neural network for directly predicting such attention
box. Given a training sample $(I,G)$ consisting of an image $I$ of size
$w\times h\times 3$ (Fig. 2 (a)), and a groundtruth attention map
$G\in[0,1]^{w\times h}$ (Fig. 2 (b)), the optimum rectangular $\dot{W}$
defined in Equ. 2 is computed as the groundtruth attention prediction box.
Here we apply [3] for generating $\dot{W}$ over $G$ (Fig. 2 (c)) for
computation efficiency. We set $\lambda=0.9$ for preserving most informative
areas. Then the task of attention box prediction can be achieved via bounding
box regression as object detection [13, 35, 9]. Note that any other attention
scores can also be used for generating groundtruth bounding box for training
the ABP network.

Fig. 3 illustrates the architecture of ABP network. The bottom of this network
is a stack of convolutional layers, which are borrowed from the first five
convolutional blocks of VGGNet [37]. With the last convolutional layer, we
slide a small network with $3\times 3$ kernel over its convolutional feature
map, thus generating $512\\!-\\!d$ feature for each sliding location. The
feature vector is further fed into two fully-connected layers: box-regression
layer for predicting attention bounding box; box-classification layer for
determining the box whether belongs to attention box. For a given location,
those two fully-connected layers predict box offsets and scores over a set of
default bounding boxes, which are similar to the anchor boxes used in Faster
R-CNN [35].

Figure 3: Architecture of Attention Box Prediction (ABP) network.

During training, we need to determine which default boxes correspond to the
groundtruth attention box and train the network accordingly. We assign the
default box which has the highest Intersection-over-Union (IoU) with the
groundtruth box or with IoU higher than 0.7 as a positive label
($c=\mathbf{1}$). We assign the default box that has a IoU lower than 0.3 a
negative label ($c=\mathbf{0}$) and drop other default boxes. The above
process is illustrated in Fig. 2 (d). For the preserved boxes, we define
$\bar{p}^{c}_{i}\in\\{1,0\\}$ as an indicator for the label of $i$-th box and
vector $\bar{t}$ as a four-parameterized coordinate (coordinates of center,
width and height) of the groundtruth attention box. Similarly, we define
$p^{c}_{i}$ and $t_{i}$ as predicted confidence over $c$ class and predicted
attention box of $i$-th default box. With above definition, the ABP network is
trained via minimizing the following loss function derived from object
detection [10, 35, 24]:

$\displaystyle\mathcal{L}(p,t)=\sum\nolimits_{i}\mathcal{L}_{cls}(p_{i},\bar{p}_{i})+\sum\nolimits_{i}\bar{p}^{\mathbf{1}}_{i}\mathcal{L}_{reg}(t_{i},\bar{t}).$
(3)

The classification loss $\mathcal{L}_{cls}$ is the softmax loss over
confidences of two classes (attention box or not). The regression loss
$\mathcal{L}_{reg}$ is a Smooth L1 loss [10], between the predicated box and
the ground truth attention box, which is only activated for positive default
boxes.

With the ABP network trained on existing attention prediction datasets, it
learns to generates reliable attention boxes. Then we select the one with the
highest prediction score (${p}^{\mathbf{1}}_{i}$) as the initial crop. This
initial crop covers the most informative part of the image, which likes human
placing a crop around the desired area (Fig. 4 (a)). Next, we generate a set
of cropping candidates around the initial crop, as the human adjusting the
location, size and ratio of the initial crop. A rectangular can be uniquely
determined via the coordinates of its top-left and right-bottom corners. For
the top-left corner of the initial crop, we define a set of offsets:
$\\{-40,-32,\cdots,-8,0\\}$ in x- and y-axis. Similarly, a set of offsets:
$\\{0,8,...,32,40\\}$ in x- and y-axis is also defined for the bottom-right
corner. Via adding the top-left and bottom-right corners with corresponding
pre-defined offsets 111Since we resize the input image with $min(w,h)=224$, we
find the largest offset (40) is enough., we generate $6^{4}=1296$ cropping
candidates in total, which is far less than the sliding windows needed for
traditional cropping methods. Each of crop candidates is designed for covering
the whole initial crop area, since the initial crop is a minimum visually
importance-preserved rectangle that should be maintained in cropping process
(Fig. 4 (b)).

###  3.2 Aesthetics-based Crop Window Selection

Figure 4: (a) Initial crop (red rectangle) predicted via ABP network. (b)
Cropping candidates (blue rectangles) generated around the initial crop. (c)
Final crop selected as the candidate with highest aesthetic score from AA
network.

With our attention-aware cropping candidates by ABP network, we next select
the most aesthetics-inspired one as the final crop. It is important to
consider aesthetics for photo cropping task, since beyond preserving the
important content, a nice crop should also deliver pleasant viewing
experience. For analyzing the aesthetic quality of each cropping candidates,
one choice is training an aesthetics assessment network, and iteratively
applying forward-propagation for each crop candidate over this network when
cropping. Obviously, this strategy is straightforward but time-consuming.
Inspired by the recent advantages of object detection, which share
convolutional features between regions, we build a network that analyzes
aesthetic values of all cropping candidates simultaneously.

Figure 5: Architecture of Aesthetics Assessment (AA) network.

We achieve this via an Aesthetics Assessment (AA) network (Fig. 5), which
takes an entire image and a set of cropping candidates as input, and outputs
the aesthetic values of the cropping candidates. The bottom of the AA network
is the former four convolutional blocks of VGGNet [37] without $pool4$ layer.
Here we adopt a relatively shallow network mainly due to two reasons. First,
aesthetics assessment is a relatively easier problem (high quality vs low
quality) compared with image classification (with 1000 classes). Secondly, for
an image with the size of $w\times h\times 3$, the spatial dimensions of the
final convolutional feature map of AA network is
$\frac{w}{8}\times\frac{h}{8}$, which preserves discriminability for the
offsets defined in Sec. 3.1.

Then, on the top of the last convolutional layer, we adopt Region of Interest
(RoI) pooling layer [35], which is a special case of spatial pyramid pooling
(SPP) layer [13], to extract a fixed-length feature vector from the final
convolutional feature map. The RoI pooling layer uses max pooling to convert
the features inside any crop candidate into a small feature map with a fixed-
dimensional vector, which is further fed into a sequence of fully-connected
layer for aesthetic quality classification. This operation allows us to
operate image with arbitrary aspect ratios, thus avoiding undesired
deformation in aesthetics assessment. With a crop candidate with size of
$w^{\prime}\times h^{\prime}$, RoI pooling layer divides it into $n\times n$
spatial bins and applies max-pooling for the features within each bins. Here
we set $n=7$.

For training, given an image from the existing aesthetics assessment datasets,
it takes an aesthetic label $c\in\\{\mathbf{1},\mathbf{0}\\}$, where
$\mathbf{1}$ corresponds to high aesthetic quality and $\mathbf{0}$ represents
low quality. We resize the image with $min(w,h)=224$, similar to ABP net, and
the whole image can be viewed as a cropping candidate for training. For $i$-th
image in training, we define $\bar{q}^{c}_{i}\in\\{1,0\\}$ as an indicator for
its aesthetics-quality label and ${q}^{c}_{i}$ is its predicted aesthetics-
quality score for $c$ class.

Based on the above definition, the training of the AA network is done by
minimizing the following softmax loss over $N$ training samples:

$\displaystyle\mathcal{L}_{cls}(q,\bar{q})=-\frac{1}{N}\sum_{i}\sum_{c\in\\{\mathbf{1},\mathbf{0}\\}}\bar{q}^{c}_{i}log(\widehat{q}^{c}_{i}),$
(4) $\displaystyle
where~{}~{}\widehat{q}^{c}_{i}=exp(q^{c}_{i})\Big{/}(exp(q^{\mathbf{1}}_{i})+exp(q^{\mathbf{0}}_{i})).$

With the cropping candidates generated from APB network, the AA network is
capable of producing their aesthetics-quality scores
($\\{{q}^{\mathbf{1}}_{i}\\}$), where the one with the highest score is
selected as the final crop (Fig. 4 (c)).

(a) Images with highest aesthetics values  (b) Images with lowest aesthetics
values

Figure 6: Aesthetics assessment results via our AA network. The test images
with the highest predicted aesthetics values and those with the lowest
predicted aesthetics values are presented in (a) and (b), respectively.

###  3.3 Implementation Details

Training Two large-scale datasets: SALICON [18] and AVA [31], are used for
training our model. SALICON is used for training our ABP network. It contains
15000 natural images with eye fixation annotations which are simulated through
mouse movements of users on blurred images. For obtaining groundtruth
attention box, we follow the instructions of [18] for transferring the binary
mouse-clicking map into grey-scale human attention map, and then we apply [3]
for generating attention bounding box according to Equ. 2 with $\lambda=0.9$.
The AVA dataset is the largest publicly available aesthetics assessment
benchmark, which provides about 250,000 images in total. The aesthetics
quality of each image was rated on average by roughly 200 people with the
ratings ranging from one to ten, with ten indicating the highest aesthetics
quality. Followed by [25, 27, 28, 31], about 230,000 images are used for
training our AA network. More specially, images with mean ratings smaller than
5 are assigned as low quality and those with mean ratings larger than or equal
to 5 are labeled as high quality.

Our two sub-networks are trained simultaneously. In each training iteration,
we use a min-batch of 4 images, 2 of which are from SALICON dataset with the
groundtruth attention boxes and the rest from AVA dataset with aesthetics
quality groundtruth. Before feeding the input images and ground-truth to the
network, we scale the images such that the smaller dimension is 224. Since the
bottom two convolutional blocks ($conv1$ and $conv2$) are shared between both
the tasks of attention box prediction and esthetics assessment, they are
trained for the two tasks simultaneously using all the images in the batch.
For the layers specialized to each of the sub-networks are trained using only
those images in the batch having the corresponding ground-truth.

Both ABP and AA networks are initialized from the weights of VGGNet [37],
which is pre-trained on large-scale image classification dataset [36]. Our
model is implemented with the popular Caffe library [17] and trained with
stochastic gradient descent. The networks were trained over 200K iterations
where we use momentum of 0.9 and weight decay of 0.0001, which is reduced by a
factor of 0.1 at every 10K iterations.

Testing For training, our two sub-networks are trained in parallel strategy,
while for testing, they work in a cascaded way. With a given image (resized
with $min(w,h)=224$) for cropping, we first gain a set of attention boxes
generated via forward propagation on APB network. Then the initial crop was
selected as the one with the highest score of attention box prediction. After
that, a set of cropping candidates are generated around the initial crop.
Since the two convolutional blocks at the bottom are shared between ABP and AA
networks, we directly feed the cropping candidates and the convolutional
feature of last layer of $conv2$ into AA network. Finally, the final crop is
selected as the cropping candidate with best aesthetic quality. The cropping
model achieves a fast speed of 5 fps.

##  4 Experimental results

In this section, we first examine the performance of our ABP and AA networks
on their specific tasks. The goal of these experiments is to investigate the
effectiveness of individual components instead of comparing them with the
state-of-the-art. Then, we evaluate the performance of our whole cropping
model on two widely used photo cropping datasets with other competitors.

###  4.1 Evaluation for ABP and AA Networks

Performance of ABP Network We first evaluate the performance of ABP network on
PASCAL dataset [22], which is widely used for attention prediction. This
dataset contains totally 850 natural images from PASCAL 2010 [7], with the eye
fixations during 2 seconds of 8 different subjects. With the binary eye
fixation images, we follow [22] to generate gray-scale attention map. Then, as
the way described in Sec. 3.3, we generate groundtruth attention box for each
image. We consider eight state-of-the-art attention models: ITTI [16], AIM
[2], GBVS [12], SUN [49], DVA [15], SIG [14], CAS [11] and SalNet [33]. Then
we extract the attention boxes of above methods via the same strategy used for
generating groundtruth bounding box. We opt for the Intersection over Union
(IoU) score for quantifying the quality of extracted attention boxes. The
quantitative results are illustrated in Table 1. As seen, our attention box
prediction results are more accurate than previous attention models, since our
ABP network is specially designed for this task.

Method | Ours | ITTI[16] | AIM [2] | GBVS[12] | SUN[49]
---|---|---|---|---|---
IoU | 0.517 | 0.318 | 0.327 | 0.319 | 0.273
Method | Ours | DVA[15] | SIG[14] | CAS [11] | SalNet [33]
IoU | 0.517 | 0.346 | 0.272 | 0.356 | 0.379

Table 1: Attention box prediction with IoU for PASCAL [22].

Performance of AA Network We adopt the testing set of AVA dataset [31], which
is mentioned in Sec. 3.3, for evaluating the performance of our AA network.
The testing set of AVA dataset contains 19,930 images. The testing images with
mean ratings smaller than 5 are labeled as low quality; otherwise they are
labeled as high quality. We compare our methods with the state-of-the-art
methods: AVA [31], RAP [25], RAP2 [26], DMA [27], ARC [21] and CPD [28], where
AVA is based on manually designed features while other methods are based on
deep learning model. As shown in Table 2, our AA network is struggle to
achieve state-of-the-art performance due to relatively simple network
architecture. In Fig. 6, we present some examples of the test images that are
considered of the highest and lowest aesthetics values by our AA network.

Method | Ours | AVA [31] | RAP-DCNN [25] | RAP-RDCNN [25]
---|---|---|---|---
Accuracy | 0.769 | 0.667 | 0.732 | 0.745
Method | Ours | RAP2 [26] | DMA-SPP [27] | DMA [27]
Accuracy | 0.769 | 0.754 | 0.728 | 0.745
Method | Ours | DMA-Alex [27] | ARC [21] | CPD [28]
Accuracy | 0.769 | 0.754 | 0.773 | 0.774

Table 2: Aesthetics assessment accuracy for AVA [31].

Conclusion Overall, our two sub-networks generate the promising results or
compete with existing top-performance approaches. Considering the shared
convolutional layers in the bottom of these two networks, our model achieves a
good tradeoff between performance and computation efficiency. More important,
the robustness of those two basic components greatly contributes the high-
quality of our crop suggestions, which will be detailed in next section.

###  4.2 Evaluation for Photo Cropping

We evaluate our whole cropping model on two public image cropping datasets,
including Image Cropping Dataset from MSR (MSR-ICD) [48] and FLMS [8]. The
MSR-ICD dataset includes 950 images and each image is carefully cropped by 3
experts. The FLMS dataset contains 500 natural images which are collected from
Flickr. For each image, 10 expert users on Amazon Mechanical Turk who passed a
strict qualification test are employed for cropping groundtruth box.

We adopt the same evaluation metrics as [48], i,e., IoU score and Boundary
Displacement Error (BDE), to measure the cropping accuracy of image croppers.
BDE is defined as the mean normalized displacement of four edges between the
cropping box and the groundtruth rectangles.

Method | Photographer 1 | Photographer 2 | Photographer 3
---|---|---|---
IoU$\uparrow$ | BDE$\downarrow$ | IoU$\uparrow$ | BDE$\downarrow$ | IoU$\uparrow$ | BDE$\downarrow$
ATC [39] | 0.605 | 0.108 | 0.628 | 0.100 | 0.641 | 0.095
AIC [3] | 0.469 | 0.142 | 0.494 | 0.131 | 0.512 | 0.123
LCC [48] | 0.748 | 0.066 | 0.728 | 0.072 | 0.732 | 0.071
MPC [34] | 0.603 | 0.106 | 0.582 | 0.112 | 0.608 | 0.110
SPC [32] | 0.396 | 0.177 | 0.394 | 0.178 | 0.385 | 0.182
ARC [21] | 0.448 | 0.163 | 0.437 | 0.168 | 0.440 | 0.165
Ours | 0.813 | 0.030 | 0.806 | 0.032 | 0.816 | 0.032

Table 3: Cropping results with IoU and BDE on MSR-ICD [48].

We compare our cropping method with two main categories of image cropping
methods, i.e., attention-based and aesthetics-based methods. For attention-
based method, we select ATC [39] which is a classical image thumbnail cropping
method. We also use AIC as a baseline, which is obtained via equipping crop
window researching method [3] with top-performing saliency detection method.

Method | Ours | ATC [39] | AIC [3] | LCC [48] | MPC [34] | VBC [8]
---|---|---|---|---|---|---
IoU$\uparrow$ | 0.81 | 0.72 | 0.64 | 0.63 | 0.41 | 0.74
BDE$\downarrow$ | 0.057 | 0.063 | 0.075 | - | - | -

Table 4: Cropping results with IoU and BDE on FLMS [8]. Figure 7: Qualitative
results on MSR-ICD [48] and FLMS [8] datasets. The red rectangles indicate the
initial crop generated via ABP network, and the yellow windows correspond to
the final crop selected via AA network.

We apply context-aware saliency [11] and optimal parameters, as suggested by
[3], for maximizing its performance. For aesthetics-based method, we select
LCC [48], MPC [34], and VBC [8]. We also consider SPC, which is an advanced
version of [32], as described in [48]. Additionally, we adopt a recent
aesthetics ranking method [21] combined with sliding window strategy as a
baseline: ARC. We select the crop as the one with the highest ranking score
from sliding windows. The comparison results on MSR-ICD and FLMS datasets are
demonstrated in Table 3 and Table 4, respectively. As seen, our cropping
method achieves the best performance in both datasets. Qualitative results on
MSR-ICD and FLMS datasets are presented in Fig. 7.

##  5 Conclusions

In this work, we propose a deep learning based photo cropping approach, driven
by human attention box prediction and aesthetics assessment. The proposed deep
model is decomposed into two sub-networks: Attention Box Prediction (ABP)
network and Aesthetics Assessment (AA) network, which share multiple
convolution layers at the bottom. The proposed method approaches photo
cropping in a determining-adjusting manner. It infers initial crop as a
bounding box covering the visually important area (attention-aware
determining), and then selects the best crop with highest aesthetic quality
from a few cropping candidates generated around the initial crop (aesthetic-
based adjusting). Our extensive experimental analyses demonstrate that our
solution achieves superior performance in comparison to the state-of-the-art.

## References

  * [1] A. Borji.  Boosting bottom-up and top-down visual features for saliency estimation.  In CVPR, 2012.
  * [2] N. Bruce and J. Tsotsos.  Saliency based on information maximization.  NIPS, 2006.
  * [3] J. Chen, G. Bai, S. Liang, and Z. Li.  Automatic image cropping : A computational complexity study.  In CVPR, 2016.
  * [4] R. Datta, D. Joshi, J. Li, and J. Z. Wang.  Studying aesthetics in photographic images using a computational approach.  In ECCV, 2006.
  * [5] Y. Deng, C. C. Loy, and X. Tang.  Image aesthetic assessment: An experimental survey.  arXiv preprint arXiv:1610.00838, 2016.
  * [6] S. Dhar, V. Ordonez, and T. L. Berg.  High level describable attributes for predicting aesthetics and interestingness.  In CVPR, 2011.
  * [7] M. Everingham, L. Van Gool, C. K. Williams, J. Winn, and A. Zisserman.  The PASCAL Visual Object Classes (VOC) challenge.  IJCV, 2010.
  * [8] C. Fang, Z. Lin, R. M ech, and X. Shen.  Automatic image cropping using visual composition, boundary simplicity and content preservation models.  In ACMMM, 2014.
  * [9] R. Girshick.  Fast R-CNN.  In ICCV, 2015.
  * [10] R. Girshick, J. Donahue, T. Darrell, and J. Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In CVPR, 2014.
  * [11] S. Goferman, L. Zelnik-Manor, and A. Tal.  Context-aware saliency detection.  IEEE PAMI, 2012.
  * [12] J. Harel, C. Koch, P. Perona, et al.  Graph-based visual saliency.  In NIPS, 2006.
  * [13] K. He, X. Zhang, S. Ren, and J. Sun.  Spatial pyramid pooling in deep convolutional networks for visual recognition.  In ECCV, 2014.
  * [14] X. Hou, J. Harel, and C. Koch.  Image signature: Highlighting sparse salient regions.  IEEE PAMI, 2012.
  * [15] X. Hou and L. Zhang.  Dynamic visual attention: Searching for coding length increments.  In NIPS, 2009.
  * [16] L. Itti, C. Koch, and E. Niebur.  A model of saliency-based visual attention for rapid scene analysis.  IEEE PAMI, 1998.
  * [17] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell.  Caffe: Convolutional architecture for fast feature embedding.  arXiv preprint arXiv:1408.5093, 2014.
  * [18] M. Jiang, S. Huang, J. Duan, and Q. Zhao.  SALICON: Saliency in context.  In CVPR, 2015.
  * [19] T. Judd, K. Ehinger, F. Durand, and A. Torralba.  Learning to predict where humans look.  In ICCV, 2009.
  * [20] Y. Ke, X. Tang, and F. Jing.  The design of high-level features for photo quality assessment.  In CVPR, 2006.
  * [21] S. Kong, X. Shen, Z. Lin, R. Mech, and C. Fowlkes.  Photo aesthetics ranking network with attributes and content adaptation.  In ECCV, 2016.
  * [22] Y. Li, X. Hou, C. Koch, J. M. Rehg, and A. L. Yuille.  The secrets of salient object segmentation.  In CVPR, 2014.
  * [23] N. Liu, J. Han, D. Zhang, S. Wen, and T. Liu.  Predicting eye fixations using convolutional neural networks.  In CVPR, 2015.
  * [24] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg.  SSD: Single shot multibox detector.  In ECCV, 2016.
  * [25] X. Lu, Z. Lin, H. Jin, J. Yang, and J. Z. Wang.  RAPID: Rating pictorial aesthetics using deep learning.  In ACMMM, 2014.
  * [26] X. Lu, Z. Lin, H. Jin, J. Yang, and J. Z. Wang.  Rating image aesthetics using deep learning.  In IEEE TMM, 2015.
  * [27] X. Lu, Z. Lin, X. Shen, R. Mech, and J. Z. Wang.  Deep multi-patch aggregation network for image style, aesthetics, and quality estimation.  In ICCV, 2015.
  * [28] L. Mai, H. Jin, and F. Liu.  Composition-preserving deep photo aesthetics assessment.  In CVPR, 2016.
  * [29] L. Marchesotti, C. Cifarelli, and G. Csurka.  A framework for visual saliency detection with applications to image thumbnailing.  In ICCV, 2009.
  * [30] L. Marchesotti, F. Perronnin, D. Larlus, and G. Csurka.  Assessing the aesthetic quality of photographs using generic image descriptors.  In ICCV, 2011.
  * [31] N. Murray, L. Marchesotti, and F. Perronnin.  AVA: A large-scale database for aesthetic visual analysis.  In CVPR, 2012.
  * [32] M. Nishiyama, T. Okabe, Y. Sato, and I. Sato.  Sensation-based photo cropping.  In ACMMM, 2009.
  * [33] J. Pan, E. Sayrol, X. Giro-i Nieto, K. McGuinness, and N. E. O’Connor.  Shallow and deep convolutional networks for saliency prediction.  In CVPR, 2016.
  * [34] J. Park, J.-Y. Lee, Y.-W. Tai, and I. S. Kweon.  Modeling photo composition and its application to photo re-arrangement.  In ICIP, 2012.
  * [35] S. Ren, K. He, R. Girshick, and J. Sun.  Faster R-CNN: Towards real-time object detection with region proposal networks.  In NIPS, 2015.
  * [36] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al.  Imagenet large scale visual recognition challenge.  IJCV, 2015.
  * [37] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [38] H.-H. Su, T.-W. Chen, C.-C. Kao, W. H. Hsu, and S.-Y. Chien.  Scenic photo quality assessment with bag of aesthetics-preserving features.  In ACMMM, 2011.
  * [39] B. Suh, H. Ling, B. B. Bederson, and D. W. Jacobs.  Automatic thumbnail cropping and its effectiveness.  In ACM UIST, 2003.
  * [40] J. Sun and H. Ling.  Scale and object aware image thumbnailing.  IJCV, 2013.
  * [41] H. Tang, N. Joshi, and A. Kapoor.  Blind image quality assessment using semi-supervised rectifier networks.  In CVPR, 2014.
  * [42] E. Vig, M. Dorr, and D. Cox.  Large-scale optimization of hierarchical features for saliency prediction in natural images.  In CVPR, 2014.
  * [43] W. Wang, J. Shen, and F. Porikli.  Saliency-aware geodesic video object segmentation.  In CVPR, 2015.
  * [44] W. Wang, J. Shen, and L. Shao.  Consistent video saliency using local gradient flow optimization and global refinement.  IEEE TIP, 2015.
  * [45] W. Wang, J. Shen, L. Shao, and F. Porikli.  Correspondence driven saliency transfer.  IEEE TIP, 2016.
  * [46] W. Wang, J. Shen, R. Yang, and F. Porikli.  Saliency-aware video object segmentation.  IEEE PAMI, 2017.
  * [47] W. Wang, J. Shen, Y. Yu, and K.-L. Ma.  Stereoscopic thumbnail creation via efficient stereo saliency detection.  IEEE TVCG, 2016.
  * [48] J. Yan, S. Lin, S. Bing Kang, and X. Tang.  Learning the change for automatic image cropping.  In CVPR, 2013.
  * [49] L. Zhang, M. H. Tong, T. K. Marks, H. Shan, and G. W. Cottrell.  SUN: A bayesian framework for saliency using natural statistics.  Journal of vision, 2008.


# DSC: Deep Scan Context Descriptor for Large-Scale Place Recognition

Jiafeng Cui1,4, Tengfei Huang2,3, Yingfeng Cai2,3, Junqiao Zhao∗2,3,4, Lu
Xiong1,4 and Zhuoping Yu1,4 *This work is supported by the National Key
Research and Development Program of China (No. 2018YFB0105103, No.
2018YFB0505400), the National Natural Science Foundation of China (No.
U1764261, No. 41801335, No. 41871370)1School of Automobile, Tongji University,
Shanghai, China2Department of Computer Science and Technology, School of
Electronics and Information Engineering, Tongji University, Shanghai,
China3The Key Laboratory of Embedded System and Service Computing, Ministry of
Education, Tongji University, Shanghai, China4Institute of Intelligent
Vehicles, Tongji University, Shanghai, China*Corresponding Author:
<EMAIL_ADDRESS>
###### Abstract

LiDAR-based place recognition is an essential and challenging task both in
loop closure detection and global relocalization. We propose Deep Scan Context
(DSC), a general and discriminative global descriptor that captures the
relationship among segments of a point cloud. Unlike previous methods that
utilize either semantics or a sequence of adjacent point clouds for better
place recognition, we only use raw point clouds to get competitive results.
Concretely, we first segment the point cloud egocentrically to acquire
centroids and eigenvalues of the segments. Then, we introduce a graph neural
network to aggregate these features into an embedding representation.
Extensive experiments conducted on the KITTI dataset show that DSC is robust
to scene variants and outperforms existing methods.

##  I INTRODUCTION

Large-scale place recognition is an essential part of simultaneous
localization and mapping (SLAM), which is widely applied in many autonomous
robotics systems [1, 2]. Visual place recognition has been extensively studied
[3, 4, 5, 6]. However, these approaches are sensitive to illumination change
and easily fail when the viewpoint of the input images differs from each
other. LiDAR-based methods are more robust to illumination change and
viewpoint variants since the LiDAR sensor is capable of providing geometric
structural information in a 360-degree view.

Figure 1:  A brief concept of Deep Scan Context. We first divide the point
cloud into segments egocentrically, as a result, the segments will fall in
certain segments. Then we extract the centroids and eigenvalues of the
segments. The centroids, as well as eigenvalues, will together be encoded into
a graph neural network to finally output a global descriptor.

Previous works extracted local or global features from 3D point clouds [7, 8,
9, 10, 11, 12, 13]. These pointwise methods pay little attention to potential
topological information in the scenes, e.g. the arrangement of certain
segments and their spatial relations, hence it is difficult to distinguish
scenarios with similar features but different structures. In order to get
distinct features, high-level representations such as geometrical segments or
semantics were proposed [14, 15, 16, 17, 18]. SegMatch [14] first used
Euclidean clustering to segment a point cloud and search candidates by
matching K-nearest neighbour (KNN) segments. Locus [15] adopted the similar
segmentation-based method and generate a global descriptor for a point cloud.
However, these Euclidean clustering-based methods performed poorly in a sparse
point cloud.

SGPR [17] introduced the semantic information to achieve a stable
representation. SSC [18] further employed iterative closet point (ICP) and
semantics to align the point cloud pairs to get more accurate matching
results. Although the semantic information is helpful to the task, it is
difficult and time-consuming to get accurate semantic labels for generic
scenes.

In this paper, we present a novel method, named Deep Scan Context (DSC), to
effectively recognize similar places. As shown by Figure 1, given a point
cloud frame, we first segment the raw data egocentrically. Compared with
Euclidean clustering, it is more efficient and can avoid failure in sparse
scenes [15]. Next, we extract the centroid points of the segments and keep the
topological relation between centroids using a graph neural network (GNN). To
furture capture geometric features of the segments, we calculate eigenvalues
of the segments to improve the saliency of description. These eigenvalues are
then fed into another GNN to learn the relationships among features. Finally,
the graph outputs are flattened into a fixed descriptor for computing
candidates’ similarities. Our main contributions in this paper are summarised
as follows:

  * •

We introduce an egocentric segmentation method that can better adapt to
various scenes while other segmentation methods may fail to cluster enough
segments.

  * •

We use the eigenvalues as features of the segments to achieve rotational
invariance.

  * •

We propose a novel global descriptor to encode the structural features of
these segments and their mutual topological features.

Figure 2:  The architecture of our method. Top: the illustration of each
module in the method. Bottom: the illustration of the network that extracts
Euclidean and Eigenvalue space features in parallel and concatenates them to
aggregated features.

##  II RELATED WORK

We give an overview of LiDAR-based place recognition methods including
projection-based, handcraft descriptors-based, learning-based, and semantic-
based methods.

###  II-A Projection-based methods

Inspired by the success of visual place recognition methods [19, 3, 20], many
researchers proposed projection-based methods to utilize visual-based
pipelines. M2DP [11] projected the point clouds into different layers and
collected the signature in each layer to generate a global descriptor. LiDAR-
Iris [21] extracted binary signature images from the raw point cloud and
compared the Hamming distances with other candidates. Shan [22] projected the
intensity of points into pixels to construct a grayscale image, converting it
into a visual place recognition task. Disco [23] used a CNN network to extract
features from scan context images [12] and got an initial orientation guess
for later pose estimation. These projection-based methods lose the rich 3D
information because of projection.

###  II-B Handcraft descriptors-based methods

Other works focus on extracting key points and combine the key points with
their neighboring points to construct local features [8]. Then the retrieval
is implemented by vote-based or histogram-based approachs [7, 24]. Due to the
poor repeatability of key points between frames, these methods are difficult
to achieve highly accurate results. SegMatch [14] first introduced a
segmentation-based place recognition method with high-level features. They
used the Euclidean clustering to segment the point cloud into a few segments
and then compared each segment with its KNN neighbors in the presented map to
extract corresponding candidates. Scan context [12] proposed a global
descriptor that encoded the point cloud’s max height values. This method is
based on the hypothesis of structured scenes and may fail if there is no
significant variation in height. ISC [25] replaced height with remission
information to describe the scene and adopted a fast coarse-to-fine match
strategy. Similar to height, remission values are often affected by noise e.g.
strong light and specular reflection.

###  II-C Learning-based methods

Based on PointNet [26], PointNetVLAD [13] extracted features for all the input
points, then introduced the NetVLAD module to generate a global descriptor.
LPD-Net [27] further concatenated local features of each point to enlarge the
receptive field and the retrieval performance improves a great margin. These
pointwise methods take the whole point cloud into consideration, and are
sensitive to rotation variants. Locus [15] segmented the point cloud through
Euclidean clustering and learned the descriptor of each segment via a CNN
model. To ensure the repeatability of the segmentation, Locus tried to find
correspondences of the segments both in the spatial and temporal dimensions.
The segments that had correspondences were kept and then integrated into a
global descriptor to match other frames instead of matching segments
independently. However, Euclidean clustering often fail to generate enough
segments in sparse scenes where there are few features.

###  II-D Semantic-based methods

Chen [28] designed a siamese network to acquire the overlap between pairs of
LiDAR scans. The similarity of two point clouds can be measured by the overlap
ratio. Semantic information was first exploited in place recognition tasks to
improve the ability of scene representation. SGPR [17] and SSC [18] both used
semantic information of the points to describe the scene. SGPR segmented the
point cloud in different semantic classes and used the Euclidean clustering in
each class to get more instances. These semantic instances were represented as
some nodes and the point cloud was represented as a graph. SSC further
introduced Iterative Closest Point (ICP) to align the two point clouds via
semantic labels before computing the similarity score, which achieves the
state-of-the-art performance. However, the predefined semantic labels are not
easy to obtain, which limits the application of these semantic-based methods.

To overcome the drawbacks above, we aim to design a generic and robust method
that can be utilized in various scenes.

##  III METHODOLOGY

In this section, we will introduce our method DSC in detail. Our method
consists of three main modules: egocentrically segmentation, segments feature
extraction and deep scan context network.

###  III-A Egocentrically Segmentation

Considering the nature of the rotating Lidar sensor, we first divide the 3D
scan space into azimuthal and radial segments similar to [12], which results
in $N_{s}$ sectors along the azimuthal direction and $N_{r}$ rings along the
radial direction. Figure 1 shows the egocentrically segmentation. Each segment
is assigned an unique index number $\left(i,j\right)$, where
$i\in\left\\{1,\dots,N_{s}\right\\}$ and $j\in\left\\{1,\dots,N_{r}\right\\}$.
$N_{s}$ and $N_{r}$ are defined by the intervals of two dimensions. We set the
radial interval as $\frac{L_{max}}{N_{r}}$ and the azimuthal interval as
$\frac{2\pi}{N_{s}}$, where $L_{max}$ is the maximum detection range of the
LiDAR. Specifically, given a point cloud $P\in R^{N\times 3}$, for each point
$p_{m}=\left(x_{m},y_{m},z_{m}\right)$, we calculate its polar coordinate
$\left(\lambda{{}_{m}},\theta{{}_{m}}\right)$:

$\displaystyle\lambda_{m}=\sqrt{x_{m}^{2}+y_{m}^{2}}$ (1)
$\displaystyle\theta_{m}=\arctan\left(\frac{y_{m}}{x_{m}}\right)$

Then $p_{m}$ will be classified into segment $\left(i,j\right)$, if:

$\displaystyle\left(j-1\right)\frac{L_{max}}{N_{r}}<=\lambda_{m}<=j\frac{L_{max}}{N_{r}}$
(2)
$\displaystyle\left(i-1\right)\frac{2\pi}{N_{s}}<=\theta_{m}<=i\frac{2\pi}{N_{s}}$

The point cloud is eventually divided into a set of segments
$S=\left\\{S_{1},\dots,S_{t}\right\\}$. To get the topological relation of the
segments, we calculate their centroids coordinates
($C=\left\\{C_{1},\dots,C_{t}\right\\}$) and later feed them into a GNN as
described in Section LABEL:INTRODUCTION.

###  III-B Segments Feature Extraction

Since centroid coordinates alone are not representive, more descriptions need
to be extracted for the segments. SGPR [17] used the pre-trained semantic
segmentation network to classify the segments. However, they are unable to
distinguish the difference between segments of the same class. Segmap [29] and
Locus [15] use a pre-trained CNN model on KITTI dataset to generate a
descriptor for each segment. However, the results of segmentation on different
datasets can be different, which leads to poor applicability of the pre-
trained CNN model. Therefore, we calculate eigenvalues of the segments as the
feature description which are not only rotation invariant [30] but can also
represent the shape information. Specifically, we first calculate the
covariance matrices $V=\left\\{V_{1},\dots,V_{t}\right\\}$ of all the
segments. These matrices are symmetric positive definite as long as the
segments are not flat [30]. The matrix can be decomposed by $V=RAR^{T}$, where
$R$ is a rotation matrix and $A$ is the diagonal matrix. We denote the values
on the main diagonal of $A$ as
$\vec{\lambda}=\left(\lambda_{1},\lambda_{2},\lambda_{3}\right)\in\mathbb{R}$
which are the eigenvalues. For each point cloud, we can get a eigenvalues set
$\Lambda=\left\\{\vec{\lambda}_{1},\dots,\vec{\lambda}_{t}\right\\}$. More 2D
and 3D shape features are proposed in [31] that are derived from eigenvalues.
However, they only focus on getting more representations on a single segment
while we also consider relations of the features in the eigenvalue space.
Consequently, we choose the coordinates of centroids $C$ and the eigenvalues
$\Lambda$ as the inputs of the deep scan context network.

###  III-C Deep Scan Context Network

As shown in Figure 2, our network mainly includes three parts: 1) Euclidean
and eigenvalue space clustering, 2) feature graph construction, and 3) Net
Vector of Locally Aggregated Descriptors (NetVLAD) [32].

####  III-C1 Euclidean and eigenvalue space clustering

For each input centroid, KNN search is utilized to cluster neighbor centroids
both in the Euclidean space and the eigenvalue space. Let
$\left\\{C_{i_{1}},\dots,C_{i_{k}}\right\\}$ be the $k$ nearest neighbor
centroids of $C_{i}$, and their coordinates are substracted by $C_{i}$ to get
the relative coordinates of each neighbor point. Consequently, we obtain the
Euclidean space features of $C_{i}$ as:

$\displaystyle
F_{eu_{i}}=\bigodot\left(f_{j}-f_{i},f_{j}\right),j\in\left\\{i_{1},\dots,i_{k}\right\\}$
(3)

where $\bigodot$ represents the concatenation of the relative coordinates and
original coordinates. Subsequently, we concatenate the Euclidean space
features $F_{eu_{i}}$ with the eigenvalue space features $F_{eig_{i}}$ to
boost the saliency of centroid $C_{i}$:

$\displaystyle
F_{i}=\left(F_{eu}^{i},F_{eig}^{i}\right),i\in\left\\{1,\dots,t\right\\}$ (4)

####  III-C2 Feature graph construction

The multi-space KNN clustering outputs the features of each center point
together with neighbor points. We introduce two GNNs for both Euclidean-based
features and eigenvalue-based features in parallel to learn the topological
relation of the scene. We regard the input features as graph nodes:
$D=\left\\{D_{1},\dots,D_{t}\right\\}$. For all the nodes, we implement a
shared multilayer perception Layer (MLP) and use MaxPool in neighbor domains
to get the embedded features:

$\displaystyle{D_{i}}^{\prime}=MaxPool\left(MLP\left(D_{i}\right)\right),i\in\left\\{1,\dots,t\right\\}$
(5)

The multi-layer feature graph is constructed to get a gloabl feature map
$M=\left\\{M_{1},\dots,M_{t}\right\\}$.

Finally, the NetVLAD layer is used to learn K-cluster centers of D-dimension
descriptors, namely $\left\\{C_{1},\dots,C_{K}|C\in R^{D}\right\\}$, and the
output is a $D\times K$-dimension vector that representing the relative
distances to the K cluster centers. A full connected layer followed by an L2
normalization layer finally compresses the vector to a 256-dimension global
descriptor. The Lazy Quadruplet loss is employed to minimize the descriptor
distance between the query and positive pairs, at the same time, maximize the
distance between the query and the hardest negative pairs:

$\displaystyle\mathcal{L}_{Q}=\max_{j}\left[\left(\alpha+|f_{query}-f_{pos}|-|f_{query}-f_{neg_{j}}|\right)_{+}\right]$
(6)
$\displaystyle+\max_{k}\left[\left(\beta+|f_{query}-f_{pos}|-|f_{neg^{*}}-f_{neg_{k}}|\right)_{+}\right]$

where $f$ represents the descriptor vector and $|.|$ calculates the Euclidean
distance between the two elements. $\alpha$ and $\beta$ are two margin values
and $neg^{*}$ is another negative descriptor chosen from different queries.

(a) 00

(b) 02

(c) 05

(d) 06

(e) 07

(f) 08

Figure 3: Precision-Recall curves on KITTI dataset TABLE I:  F1 max scores and
Extended Precision on KITTI dataset

Methods | 00 | 02 | 05 | 06 | 07 | 08 | Mean
---|---|---|---|---|---|---|---
SC[12] | 0.750/0.609 | 0.782/0.632 | 0.895/0.797 | 0.968/0.924 | 0.662/0.554 | 0.607/0.569 | 0.777/0.681
ISC[25] | 0.657/0.627 | 0.705/0.613 | 0.771/0.727 | 0.842/0.816 | 0.636/0.638 | 0.408/0.543 | 0.670/0.661
M2DP[11] | 0.708/0.616 | 0.717/0.603 | 0.602/0.611 | 0.787/0.681 | 0.560/0.586 | 0.073/0.500 | 0.575/0.600
LI[21] | 0.668/0.626 | 0.762/0.666 | 0.768/0.747 | 0.913/0.791 | 0.629/0.651 | 0.478/0.562 | 0.703/0.674
PNV[13] | 0.779/0.641 | 0.727/0.691 | 0.541/0.536 | 0.852/0.767 | 0.631/0.591 | 0.037/0.500 | 0.595/0.621
Locus-SP | 0.889/0.752 | * | 0.832/0.733 | 0.880/0.793 | 0.701/0.637 | 0.734/0.666 | 0.807/0.716
SSC-NICP | 0.772/0.620 | 0.818/0.693 | 0.779/0.718 | 0.902/0.792 | 0.649/0.625 | 0.618/0.661 | 0.757/0.685
Ours | 0.880/0.696 | 0.841/0.675 | 0.781/0.628 | 0.860/0.731 | 0.819/0.581 | 0.852/0.648 | 0.839/0.660
ON[28] | 0.869/0.555 | 0.827/0.639 | 0.924/0.796 | 0.930/0.744 | 0.818/0.586 | 0.374/0.500 | 0.790/0.637
SGPR[17] | 0.820/0.500 | 0.751/0.500 | 0.751/0.531 | 0.655/0.500 | 0.868/0.721 | 0.750/0.520 | 0.766/0.545
Locus[15] | 0.957/0.828 | * | 0.968/0.919 | 0.950/0.913 | 0.922/0.825 | 0.900/0.742 | 0.939/0.845
SSC[18] | 0.951/0.849 | 0.891/0.748 | 0.951/0.903 | 0.985/0.969 | 0.875/0.805 | 0.940/0.932 | 0.932/0.868
Ours | 0.880/0.696 | 0.841/0.675 | 0.781/0.628 | 0.860/0.731 | 0.819/0.581 | 0.852/0.648 | 0.839/0.660

  * The methods in the upper half of the table can be applied for large-scale place retrieval while those in the bottom half are not suitable.
∗ In Sequence 02, some point cloud frames are failed to generate locus
descriptors because spatial and temporal correspondences are unavailable.

TABLE II:  Robustness evaluation of F1 max scores on KITTI dataset Methods | Rotation | Occlusion
---|---|---
00 | 02 | 05 | 06 | 07 | 08 | Mean | 00 | 02 | 05 | 06 | 07 | 08 | Mean
SC[12] | 0.719 | 0.734 | 0.844 | 0.898 | 0.606 | 0.546 | 0.725 | 0.724 | 0.751 | 0.845 | 0.904 | 0.616 | 0.552 | 0.732
ISC[25] | 0.659 | 0.701 | 0.769 | 0.840 | 0.629 | 0.403 | 0.667 | 0.620 | 0.686 | 0.711 | 0.812 | 0.589 | 0.387 | 0.634
M2DP[11] | 0.276 | 0.282 | 0.341 | 0.316 | 0.204 | 0.201 | 0.27 | 0.199 | 0.138 | 0.283 | 0.140 | 0.113 | 0.046 | 0.153
LI[21] | 0.667 | 0.764 | 0.772 | 0.912 | 0.633 | 0.479 | 0.705 | 0.627 | 0.710 | 0.679 | 0.859 | 0.585 | 0.383 | 0.641
PNV[13] | 0.083 | 0.090 | 0.490 | 0.094 | 0.064 | 0.086 | 0.151 | 0.547 | 0.570 | 0.295 | 0.589 | 0.444 | 0.031 | 0.413
Ours | 0.852 | 0.793 | 0.737 | 0.847 | 0.775 | 0.842 | 0.808 | 0.820 | 0.773 | 0.704 | 0.834 | 0.751 | 0.800 | 0.780

##  IV EXPERIMENTS

###  IV-A Experiment Setup

For a fair comparison, we follow the experiment settings of SSC [18] on the
KITTI odometry dataset, which includes 11 sequences (00-10) with ground truth
poses. Sequence (00, 02, 05, 06, 07, 08) containing real loop closure are
chosed for evaluation, and the rest sequences are used for training [17]. If
the distance between two point clouds is less than 3 meters or more than 20
meters, we treat the pair as positive pair or negative pair relatively. In the
evaluation, pairs whose timestamp offset is less than 30 seconds will be
excluded even if they are close.

In our experiments, we set $N_{s}=60$, $N_{r}=20$, $L_{max}=60m$, so that we
have 1200 segments per frame. All experiments are implemented on the same
system with an Intel Xeon E5-2680 v4 @ 2.40GHz CPU and an NVIDIA GeForce RTX
2080 Ti GPU.

###  IV-B Place Recognition Performance

We compared our method with the state-of-the-art methods including Scan
Context (SC) [12], Intensity Scan Context (ISC) [25], M2DP [11], LiDAR Iris
(LI) [21], PointNetVLAD [13](PNV), OverlapNet (ON) [28], SGPR [17], Locus
[15], and SSC [18]. Among them, OverlapNet [28] and SGPR [17] need to
recognition places pair by pair, makes them unfeasible for large-scale
retrieval task when no prior pose information is provided. The original Locus
and SSC are also time-consuming since they need a pre-match step between the
query and the candidates. We replaced the spatiotemporal feature of Locus with
spatial feature due to the inefficiency caused by temporal feature pooling.
The modified version is named Locus-SP. For SSC, we kept the semantic
information but dropped the fast ICP, namely SSC-NICP. We adopt the $100N_{p}$
pair list presented in SSC [18] and all methods follow the same settings so
that they can be evaluated fairly. The maximum F1 score ($F1_{max}$) and
Extended Precision [33] (EP) are taken to evaluate the performance. The
$F1_{max}$ and EP are defined as:

$\displaystyle F1_{max}=\max_{\tau}2\times\frac{P_{\tau}\times
R_{\tau}}{P_{\tau}+R_{\tau}}$ (7) $\displaystyle EP=\frac{P_{R0}+R_{P100}}{2}$

where $P_{\tau}$ and $R_{\tau}$ is the max Precision and Recall. $P_{R0}$ is
the precision with minimum recall and $R_{P100}$ is the recall with 100%
precision. Note that if $P_{R0}$ is less than 1, then $R_{P100}$ will be 0.

The evaluation results are shown in Figure 3 and Table I. Both Locus and
Locus-SP fail to generate Locus descriptors for some frames in sequence 02 so
they can’t get the results. In sequence 08, where the looped path is in a
reverse direction, all methods except ours have accuracy drops, which proves
that our method is robust to rotation variants. For SSC-NICP, even we keep the
semantic information for matching, the results are still not good.

The methods in the bottom half of Table I use a retrieval strategy which
limits their real-time applications. Our method is competitive even though it
is slightly behind other methods in accuracy.

TABLE III: Time retrieval efficiency in large scale setting Methods | Size | KDTree/s | One Frame/ms | Total/s | Avg/s
---|---|---|---|---|---
SSC[12] | $50\times 360$ | 0 | 40000 | 402.6 | 40.3
SGPR[17] | $\left(100,32\right)$ | 0 | 1300 | 13.8 | 1.4
Locus[15] | 4096 | 12.1 | 0.9 | 12.11 | 1.21
SC [12] | $20\times 60$ | 3.7 | 0.2 | 3.702 | 0.37
M2DP [11] | 192 | 0.3 | 0.1 | 0.301 | 0.03
Ours | 256 | 0.5 | 0.2 | 0.502 | 0.05

###  IV-C Retrieval Efficiency

In this part, we compared our method with SC [12], M2DP [11], Locus [15], SGPR
[17], and SSC [18] to evaluate the time cost for single frame and multi-frame
retrieval. We first combined the KITTI datasets (sequence 00, 02, 05, 06, 07,
08) to construct a database that contains 18236 point cloud frames. Then we
randomly selected 10 point clouds as our query frames and searched the top 1
candidates in the database. For SC [12], M2DP [11], Locus [15] and our method,
a KDTree is needed to save all the candidates’ descriptors. This will cost
additional time in the first retrieval. For SGPR [17] and SSC [18], their
retrieval strategy has to compare the query with all the other frames one by
one. Both the average and total retrieval time costs are evaluated and the
results are shown in Table III.

###  IV-D Robustness

We evaluated the robustness of our method with SC [12], ISC [25], M2DP [11],
LI [21] and PNV [13] on challenging situations including viewpoint changes and
occlusion. We randomly rotated the input point clouds around the z-axis, and
randomly dropped the point cloud data in a range of 30 degrees to verify the
robustness to occlusion. The same evaluation samples are selected for
evaluation. The results are shown in Table II.

##  V CONCLUSION

In this paper, we propose a general and effective place recognition method,
which can be applied in real-time applications in large-scale scenes. We
segment the point cloud egocentrically to avoid the disadvantages of Euclidean
segmentation. We introduce novel GNN-based method to embed the features of all
segments with a few salient points makes the module run fast and small. The
method is evaluated on the KITTI dataset and it shows the competitive
performance and robustness against viewpoint changes and occlusion. In further
work, we would like to take the height value into consideration when
segmenting the point cloud in order to better preserve the spatial structure.
A better representation of segments is also worth exploring since the centroid
coordinates are affected by rotation variants.

## References

  * [1] H. Durrant-Whyte and T. Bailey, “Simultaneous localization and mapping: part i,” _IEEE robotics & automation magazine_, vol. 13, no. 2, pp. 99–110, 2006.
  * [2] C. Stachniss, J. J. Leonard, and S. Thrun, “Simultaneous localization and mapping,” in _Springer Handbook of Robotics_. Springer, 2016, pp. 1153–1176.
  * [3] M. Cummins and P. Newman, “Fab-map: Probabilistic localization and mapping in the space of appearance,” _The International Journal of Robotics Research_ , vol. 27, no. 6, pp. 647–665, 2008.
  * [4] M. J. Milford and G. F. Wyeth, “Seqslam: Visual route-based navigation for sunny summer days and stormy winter nights,” in _2012 IEEE international conference on robotics and automation_. IEEE, 2012, pp. 1643–1649.
  * [5] S. Salti, F. Tombari, and L. Di Stefano, “Shot: Unique signatures of histograms for surface and texture description,” _Computer Vision and Image Understanding_ , vol. 125, pp. 251–264, 2014.
  * [6] C. Park, S. Kim, P. Moghadam, J. Guo, S. Sridharan, and C. Fookes, “Robust photogeometric localization over time for map-centric loop closure,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 1768–1775, 2019\.
  * [7] M. Bosse and R. Zlot, “Place recognition using keypoint voting in large 3d lidar datasets,” in _2013 IEEE International Conference on Robotics and Automation_. IEEE, 2013, pp. 2677–2684.
  * [8] R. B. Rusu, N. Blodow, and M. Beetz, “Fast point feature histograms (fpfh) for 3d registration,” in _2009 IEEE international conference on robotics and automation_. IEEE, 2009, pp. 3212–3217.
  * [9] M. Magnusson, H. Andreasson, A. Nuchter, and A. J. Lilienthal, “Appearance-based loop detection from 3d laser data using the normal distributions transform,” in _2009 IEEE International Conference on Robotics and Automation_. IEEE, 2009, pp. 23–28.
  * [10] R. B. Rusu, G. Bradski, R. Thibaux, and J. Hsu, “Fast 3d recognition and pose using the viewpoint feature histogram,” in _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2010, pp. 2155–2162.
  * [11] L. He, X. Wang, and H. Zhang, “M2dp: A novel 3d point cloud descriptor and its application in loop closure detection,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2016, pp. 231–237.
  * [12] G. Kim and A. Kim, “Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 4802–4809.
  * [13] M. A. Uy and G. H. Lee, “Pointnetvlad: Deep point cloud based retrieval for large-scale place recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 4470–4479.
  * [14] R. Dubé, D. Dugas, E. Stumm, J. Nieto, R. Siegwart, and C. Cadena, “Segmatch: Segment based place recognition in 3d point clouds,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 5266–5272.
  * [15] K. Vidanapathirana, P. Moghadam, B. Harwood, M. Zhao, S. Sridharan, and C. Fookes, “Locus: Lidar-based place recognition using spatiotemporal higher-order pooling,” _arXiv preprint arXiv:2011.14497_ , 2020.
  * [16] Y. Zhu, Y. Ma, L. Chen, C. Liu, M. Ye, and L. Li, “Gosmatch: Graph-of-semantics matching for detecting loop closures in 3d lidar data,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 5151–5157.
  * [17] X. Kong, X. Yang, G. Zhai, X. Zhao, X. Zeng, M. Wang, Y. Liu, W. Li, and F. Wen, “Semantic graph based place recognition for 3d point clouds,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 8216–8223.
  * [18] L. Li, X. Kong, X. Zhao, T. Huang, and Y. Liu, “Ssc: Semantic scan context for large-scale place recognition,” _arXiv preprint arXiv:2107.00382_ , 2021\.
  * [19] R. Mur-Artal, J. M. M. Montiel, and J. D. Tardos, “Orb-slam: a versatile and accurate monocular slam system,” _IEEE transactions on robotics_ , vol. 31, no. 5, pp. 1147–1163, 2015.
  * [20] D. Gálvez-López and J. D. Tardos, “Bags of binary words for fast place recognition in image sequences,” _IEEE Transactions on Robotics_ , vol. 28, no. 5, pp. 1188–1197, 2012.
  * [21] Y. Wang, Z. Sun, C.-Z. Xu, S. E. Sarma, J. Yang, and H. Kong, “Lidar iris for loop-closure detection,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 5769–5775.
  * [22] T. Shan, B. Englot, F. Duarte, C. Ratti, and D. Rus, “Robust place recognition using an imaging lidar,” _arXiv preprint arXiv:2103.02111_ , 2021.
  * [23] X. Xu, H. Yin, Z. Chen, Y. Li, Y. Wang, and R. Xiong, “Disco: Differentiable scan context with orientation,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 2791–2798, 2021.
  * [24] B. Steder, R. B. Rusu, K. Konolige, and W. Burgard, “Narf: 3d range image features for object recognition,” in _Workshop on Defining and Solving Realistic Perception Problems in Personal Robotics at the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , vol. 44, 2010.
  * [25] H. Wang, C. Wang, and L. Xie, “Intensity scan context: Coding intensity and geometry relations for loop closure detection,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 2095–2101.
  * [26] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 652–660.
  * [27] Z. Liu, S. Zhou, C. Suo, P. Yin, W. Chen, H. Wang, H. Li, and Y.-H. Liu, “Lpd-net: 3d point cloud learning for large-scale place recognition and environment analysis,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 2831–2840.
  * [28] X. Chen, T. Läbe, A. Milioto, T. Röhling, O. Vysotska, A. Haag, J. Behley, and C. Stachniss, “Overlapnet: Loop closing for lidar-based slam,” _arXiv preprint arXiv:2105.11344_ , 2021.
  * [29] R. Dubé, A. Cramariuc, D. Dugas, J. Nieto, R. Siegwart, and C. Cadena, “Segmap: 3d segment mapping using data-driven descriptors,” _arXiv preprint arXiv:1804.09557_ , 2018.
  * [30] M. Xu, Z. Zhou, and Y. Qiao, “Geometry sharing network for 3d point cloud classification and segmentation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 07, 2020, pp. 12 500–12 507.
  * [31] M. Weinmann, B. Jutzi, and C. Mallet, “Semantic 3d scene interpretation: A framework combining optimal neighborhood size selection with relevant features,” _ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences_ , vol. 2, no. 3, p. 181, 2014.
  * [32] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “Netvlad: Cnn architecture for weakly supervised place recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 5297–5307.
  * [33] B. Ferrarini, M. Waheed, S. Waheed, S. Ehsan, M. J. Milford, and K. D. McDonald-Maier, “Exploring performance bounds of visual place recognition using extended precision,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 1688–1695, 2020.