# Quantized Proximal Averaging Network for Analysis Sparse Coding

Kartheek Kumar Reddy Nareddy  Mani Madhoolika Bulusu  Praveen Kumar Pokala
Chandra Sekhar Seelamantula

###### Abstract

We solve the analysis sparse coding problem considering a combination of
convex and non-convex sparsity promoting penalties. The multi-penalty
formulation results in an iterative algorithm involving proximal-averaging. We
then unfold the iterative algorithm into a trainable network that facilitates
learning the sparsity prior. We also consider quantization of the network
weights. Quantization makes neural networks efficient both in terms of memory
and computation during inference, and also renders them compatible for low-
precision hardware deployment. Our learning algorithm is based on a variant of
the ADAM optimizer in which the quantizer is part of the forward pass and the
gradients of the loss function are evaluated corresponding to the quantized
weights while doing a book-keeping of the high-precision weights. We
demonstrate applications to compressed image recovery and magnetic resonance
image reconstruction. The proposed approach offers superior reconstruction
accuracy and quality than state-of-the-art unfolding techniques and the
performance degradation is minimal even when the weights are subjected to
extreme quantization.

Keywords: Analysis sparse model, Quantized neural networks, Compressed
sensing, Compressed image recovery, Proximal averaging.

##  1 Introduction

The objective in Compressive Sensing (CS) is to reconstruct a sparse signal
${\boldsymbol{x}}\in\mathbb{R}^{n}$ from its compressed observation,
$\boldsymbol{y=\Phi x}\in\mathbb{R}^{m}$, where $\mathbf{\Phi}$ is an
${m\times n}$ matrix, with $m\ll n$. The standard convex optimization
formulation to solve the CS problem is given as follows:

$\underset{\boldsymbol{x}}{\min}\leavevmode\nobreak\ \leavevmode\nobreak\
\frac{1}{2}\|\boldsymbol{\Phi x-y}\|^{2}_{2}+\lambda\|\boldsymbol{\Psi
x}\|_{1},$ (1)

where $\boldsymbol{y}$ is the observation, $\boldsymbol{\Psi}$ is the
sparsifying transform for $\boldsymbol{x}$, and sparsity is enforced on
$\boldsymbol{\Psi x}$ using an appropriate regularizer, which in this case is
the $\ell_{1}$-norm, and $\lambda$ is the regularization parameter.

However it has been shown that $\ell_{1}$-norm regularization results in
biased amplitude estimates (Zhang, 2010). Non-convex regularizers are known to
reduce the bias in the estimates. One can design efficient non-convex
regularizers by considering a combination of several sparsity-promoting
regularizers.

Figure 1: Brain MRI image reconstruction for CS ratio 40% by the proposed
1-bit Quantized models. The bottom row visualizes the absolute difference
between the ground truth and the reconstructed images. The Q-PAN+ (3R) model
captured the brain structure better and hence the difference image is majorly
composed of noise.The numbers indicates the PSNR, SSIM values.

The CS framework has enabled several practical applications particularly in
the context of computational imaging (Willett et al., 2012), ultrasound
imaging (Quinsac et al., 2010), magnetic resonance imaging (Jacob et al.,
2020), cognitive radar (Stinco et al., 2014), cognitive radio (Tian &
Giannakis, 2007), etc.
Sparse recovery algorithms are iterative and involve manual parameter tuning
and several iterations to achieve accurate reconstruction. Iterative
algorithms when unfolded into a feedforward neural network architecture can
greatly enhance the reconstruction accuracy since the network has the
advantage of learnability. Further, the depth of the network is also
significantly lower than the number of iterations of the algorithm from which
it is inspired. Therefore, the inference time is reduced. However, the price
to pay for these advantages is the overhead of training. A practical
bottleneck in deploying such models is that they require more memory to store
the high-precision weights and consequently also more computation. In
applications involving low-precision hardware, the reconstruction accuracy
reduces drastically. One of the issues that is addressed in this paper is the
effect of weight quantization on the performance of unfolded networks. The
objective is to obtain comparable accuracy to the full-precision scenario
considering weights that are coarsely quantized (which we show in the Figure
1). Such quantized unfolded networks are more amenable to practical
implementation particularly in resource constrained settings.
Another important aspect that we focus on in this paper is the problem of
analysis prior learning using a combination of convex/non-convex sparsity
promoting regularizers. The analysis prior is more effective than the
synthesis prior because most naturally occurring signals and images are sparse
only when analyzed using a suitable transformation (Rubinstein et al., 2013).
Further, employing a combination of penalty functions has been shown to result
in superior reconstruction performance than a single penalty function
(Kamilov, 2017) and gives rise to the notion of proximal averaging. The
penalty functions could be convex or non-convex. Learning a convex combination
of penalty functions is also likely to improve the sparse recovery
performance.
Before proceeding with further developments, we review recent state of the art
in these domains.

Table 1: Sparsity-promoting regularizers and corresponding proximal operators
employed in this study.

Name | Penalty Function | Proximal Operator
---|---|---
$\ell_{1}-\mathrm{norm}$ $(\lambda>0)$ | $g_{1}(x)=\lambda\left|x\right|$ | $\mathcal{P}_{1}(x)=\mathrm{sgn}(x)\mathrm{max}\left(\left|x\right|-\lambda,0\right)$
MCP (Zhang, 2010) $(\lambda>0,\gamma>1)$ | $g_{2}(x)=\begin{cases}{\lambda\left|x\right|-\cfrac{{\left|x\right|}^{2}}{2\lambda\gamma},}\qquad\enspace\,{\mathrm{for}\left|x\right|\leq\gamma\lambda,}\\\ {\cfrac{{\lambda}^{2}\gamma}{2},}\qquad\qquad\qquad{\mathrm{for}\left|x\right|\geq\gamma\lambda.}\end{cases}$ | $\mathcal{P}_{2}(x)=\begin{cases}{0,}\qquad\qquad\qquad\qquad\qquad{\mathrm{for}\;\left|x\right|\leq\lambda,}\\\ {\mathrm{sgn}\left(x\right)\cfrac{\gamma}{\gamma-1}\left(\left|x\right|-\lambda\right),}\enspace\,{\mathrm{for}\;\lambda<\left|x\right|\leq\gamma\lambda,}\\\ {x,}\qquad\qquad\qquad\qquad\qquad{\mathrm{for}\;\left|x\right|>\gamma\lambda.}\end{cases}$
SCAD (Fan & Li, 2001) $(\lambda>0,a>2)$ | $g_{3}(x)=\begin{cases}{\lambda\left|x\right|,}\qquad\qquad\qquad\quad{\mathrm{for}\left|x\right|\leq\lambda,}\\\ {\cfrac{{\left|x\right|}^{2}-2a\lambda\left|x\right|+\lambda^{2}}{2(1-a)},}\enspace\,{\mathrm{for}\lambda<\left|x\right|\leq a\lambda,}\\\ {\cfrac{(a+1){\lambda^{2}}}{2},}\qquad\qquad\enspace\,{\mathrm{for}\left|x\right|>a\lambda.}\end{cases}$ | $\mathcal{P}_{3}(x)=\begin{cases}{\mathrm{sgn}\left(x\right)\mathrm{max}\left(\left|x\right|-\lambda,0\right),}\,{\mathrm{for}\;\left|x\right|\leq 2\lambda,}\\\ {\cfrac{\left(a-1\right)x-\mathrm{sgn}\left(x\right)a\lambda}{a-2},}\enspace\,{\mathrm{for}\;2\lambda<\left|x\right|\leq a\lambda,}\\\ {x,}\qquad\qquad\qquad\qquad\qquad{\mathrm{for}\;\left|x\right|>a\lambda.}\end{cases}$

##  2 Prior Art

We present the literature in two categories, namely, quantized networks and
analysis sparse recovery techniques.

Quantized Networks Neural Networks that employ binary weights and activations,
also known as binary neural networks (BNNs) (Courbariaux et al., 2015; Hubara
et al., 2016, 2018) have been shown to be promising for solving classification
problems. Their efficacy has been demonstrated on MNIST (LeCun & Cortes, 2010)
and CIFAR10 (Krizhevsky et al., ) datasets. The XNOR-Net (Rastegari et al.,
2016) used a gain term computed from the statistics of the weights to scale
the binary weights in order to reduce the quantization error. The XNOR-Net
performed relatively better than previous BNN architectures on the ImageNet
(Deng et al., 2009) dataset. The learned quantization networks (LQ-Net) (Zhang
et al., 2018) was proposed to minimize the quantization error by jointly
learning the quantizer and the network. The Bi-Real Network (Liu et al., 2018)
employs residual connections where full-precision activations from the
previous layer affect the quantization in the current layer. On the
optimization front Meng et al. (2020) justified the straight-through-estimator
(STE) method used for training the BNNs through bayesian learning. The
quantization of weights has also been shown to be promising in the context of
generative adversarial networks (GANs) (Wang et al., 2019; Wan et al., 2020).
Zhu et al. (2020) adapts Neural Architecture Search (NAS) to find an optimized
architecture for the binarization of Convolutional Neural Networks (CNNs).
Duncan et al. (2020) showed that quantized neural networks are generally
robust relative to their full precision counterpart against adversarial
perturbations. While the role of quantization has been considered in
classification and generation problems, it has been relatively unexplored in
the context of optimizing unfolded networks for sparse recovery.

Analysis Sparse Priors Several works (Beck & Teboulle, 2009; Elad et al.,
2007; Liu et al., 2016; Donoho et al., 2009) have considered the
$\ell_{1}$-regularized analysis/synthesis sparse recovery problems owing to
its convexity. In order to solve the CS problem in the context of recovering
natural images, optimization based techniques assumed that the input images
are sparse in a fixed transform domain such as the discrete cosine transform
(DCT), wavelet domain (Sungkwang Mun & Fowler, 2009), gradient-domain (Li et
al., 2013), etc. Denoising based AMP (D-AMP) (Metzler et al., 2016), etc.
ensures good recovery for natural images. Most methods exploit structured
sparsity of the data as an image prior and solve the problem iteratively (Kim
et al., 2010; Li et al., 2013; Metzler et al., 2016; Zhang et al., 2014). All
iterative sparse recovery methods require hundreds of iterations to solve Eq.
(1), which inevitably gives rise to high computational overhead thus
restricting the application of CS. In addition, the analysis operator or the
hyperparameters such as learning rate and regularization parameter are usually
hand-crafted.

To overcome the limitations of optimization based techniques, network-based
approaches have been proposed recently. ReconNet is a neural network approach
proposed in (Kulkarni et al., 2016), which takes in CS measurements of an
image as input and outputs an intermediate reconstruction. Networks such as
ISTA-Net (Zhang & Ghanem, 2018) performed better when the sparsifying
transform was learned by imposing the $\ell_{1}$ penalty on the prior. Two
aspects are missing from current literature. First, finer approximation of
$\ell_{0}$ pseudonorm in the context of data-driven analysis-prior learning
and second, reducing the model size and improved hardware-compatibility of the
CS networks. We aim to address these two aspects with application to
compressed image reconstruction.

##  3 Contribution of this Paper

Our contribution lies at the intersection between the two aspects – network
quantization and optimization for analysis sparse prior learning while
employing several regularizers.
The starting point for the developments is a multi-penalty/composite
regularization formulation of the sparse recovery problem in an analysis-
sparse setting. The result is the proximal-averaged iterative shrinkage
algorithm (PAISA), which when unfolded gives rise to the proximal-averaging
network (PAN). It is in the context of PAN that we consider the effect of
quantization (Q-PAN). On the application front, we consider image recovery
from compressed measurements both for natural images and magnetic resonance
images.

Figure 2: Illustration of the proposed Quantized Proximal Averaging Network
(Q-PAN).

##  4 Composite Regularization in the Analysis Setting

Consider the problem of compressed sensing recovery based on multiple
penalties $\\{g_{i}\\}$ as given below:

$\displaystyle\underset{\boldsymbol{x}}{\min}$
$\displaystyle\leavevmode\nobreak\
\frac{1}{2}\|\mathbf{\Phi}\boldsymbol{x}-\boldsymbol{y}\|^{2}_{2}+\underbrace{\sum_{i=1}^{p}\alpha_{i}g_{i}(\mathcal{F}(\boldsymbol{x}))}_{g(\boldsymbol{x})}$
$\displaystyle\text{subject to }\sum_{i=1}^{p}\alpha_{i}=1,\quad
0<\alpha_{i}<1,\forall i,$ (2)

where $\mathcal{F}$ is the data-driven, sparsifying, analysis operator and $p$
is the number of sparsity-promoting regularizers. The convex and non-convex
regularizers that are considered in our work are the $\ell_{1}$-norm, minimax-
concave penalty (MCP) (Zhang, 2010), and smoothly clipped absolute deviation
(SCAD) (Fan & Li, 2001). While the $\ell_{1}$-norm is convex, the other two
penalties – MCP and SCAD – are not convex. The MCP and SCAD penalties
approximate the $\ell_{0}$ pseudonorm better than the $\ell_{1}$ norm and
hence give rise to better recovery performance (Zhang, 2010). The ideal sparse
recovery problem requires minimization of the $\ell_{0}$ pseudonorm, but it is
NP-hard and hence tractable solvers that approximate $\ell_{0}$ minimization
are preferred. The MCP and SCAD penalties perfectly fit the bill and hence we
consider them for composite regularization. The three penalties under
consideration and the corresponding proximal operators are given in Table 1.

###  4.1 Proximal-Averaged Iterative Shrinkage Algorithm (PAISA)

The problem in Eq. (2) is optimized based on majorization-minimization
(Figueiredo et al., 2007) and proximal-averaging (Zhong & Kwok, 2014). The
update $\boldsymbol{x}$ at $(k+1)^{\text{th}}$ iteration is obtained by
solving the following optimization problem:

$\underset{\boldsymbol{x}}{\min}\leavevmode\nobreak\
\frac{1}{2\rho}\|\boldsymbol{x}-\boldsymbol{r}^{(k+1)}\|^{2}_{2}+\sum_{i=1}^{p}\alpha_{i}g_{i}(\mathcal{F}(\boldsymbol{x})),$
(3)

where
$\boldsymbol{r}^{(k+1)}=\boldsymbol{x}^{(k)}-\rho{\mathbf{\Phi}^{\textsc{T}}(\mathbf{\Phi}\boldsymbol{x}^{(k)}-\boldsymbol{y})}$
and $\rho$ is the step-size. The above problem can be rewritten as

$\underset{\boldsymbol{x}}{\min}\leavevmode\nobreak\
{\sum_{i=1}^{p}\left(\frac{\alpha_{i}}{2\rho}\|\boldsymbol{x}-\boldsymbol{r}^{(k+1)}\|^{2}_{2}+\alpha_{i}g_{i}(\mathcal{F}(\boldsymbol{x}))\right)}.$
(4)

Zhang & Ghanem (2018) showed that a data-driven analysis transform improves
the reconstruction of natural images from the compressed measurements. Based
on this observation, $\mathcal{F}$ is chosen to be a combination of two linear
convolutional operators, without bias terms, separated by a rectified linear
unit (ReLU) (Nair & Hinton, 2010). $\mathcal{F}$ can be formulated in matrix
form as
$\mathcal{F}(\boldsymbol{x})=\mathbf{B}\,\text{max}(\mathbf{A}\boldsymbol{x},\boldsymbol{0})$,
where $\mathbf{A}$ and $\mathbf{B}$ correspond to the two convolutional
operators, and $\text{max}(\cdot,\boldsymbol{0})$ denotes the ReLU. The
convolutional operators $\mathbf{A}$ and $\mathbf{B}$ use $n_{f}$ filters of
size $3\times 3$ and $3\times 3\times n_{f}$, respectively. Zhang et al.
(2014) showed that, in the context of inverse problems in imaging, it is
reasonable to assume that the elements of
$(\boldsymbol{x}^{(k+1)}-\boldsymbol{r}^{(k+1)})$ are independent normal
distributed random variables with zero mean and variance $\sigma^{2}$. Let
$\boldsymbol{r}^{(k+1)}$ and $\mathcal{F}(\boldsymbol{r}^{(k+1)})$ denote the
mean values of $\boldsymbol{x}$ and $\mathcal{F}(\boldsymbol{x})$,
respectively. The following approximation holds (Zhang & Ghanem, 2018):

$\|\mathcal{F}(\boldsymbol{x})-\mathcal{F}(\boldsymbol{r}^{(k+1)})\|^{2}_{2}\approx\beta\|\boldsymbol{x}-\boldsymbol{r}^{(k+1)}\|^{2}_{2},$
(5)

where $\beta$ depends only on the parameters of $\mathcal{F}$. Incorporating
the approximation in Eq. (5) into Eq. (4), we obtain (merging $\rho$ and
$\beta$ into the parameters of the regularizers):

$\displaystyle\boldsymbol{x}^{(k+1)}$ $\displaystyle=$
$\displaystyle\text{arg}\min_{\boldsymbol{x}}\sum_{i=1}^{p}\alpha_{i}\|\mathcal{F}(\boldsymbol{x})-\mathcal{F}(\boldsymbol{r}^{(k+1)})\|^{2}_{2}$
(6)
$\displaystyle+\sum_{i=1}^{p}\alpha_{i}g_{i}(\mathcal{F}(\boldsymbol{x})).$

The solution to the above problem relies on proximal-averaging and is given by

$\boldsymbol{x}^{(k+1)}=\widetilde{\mathcal{F}}\Bigg{(}\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{F}(\boldsymbol{r}^{(k+1)}))\Bigg{)},$
(7)

where $\widetilde{\mathcal{F}}$ is the adjoint of $\mathcal{F}$ such that
$\widetilde{\mathcal{F}}(\mathcal{F}(\boldsymbol{x}))=\boldsymbol{x}$. The
optimization steps for minimizing the problem in Eq. (2) are listed in
Algorithm 1.

###  4.2 Proximal Averaging Network (PAN)

Unfolding the iterations of PAISA (Algorithm 1) results in a feedforward
neural network, which we refer to as the proximal averaging network (PAN). A
single PAN layer is represented by

$\boldsymbol{x}^{(k)}=\widetilde{\mathcal{F}}^{(k)}\Bigg{(}\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{F}^{(k)}(\boldsymbol{r}^{(k)}))\Bigg{)}.$
(8)

The parameters corresponding to the sparsity promoting regularizers and the
analysis transform
$\\{\lambda_{1}^{(k)},\lambda_{2}^{(k)},\lambda_{3}^{(k)},a^{(k)},\gamma^{(k)},\mathcal{F}^{(k)},\widetilde{\mathcal{F}}^{(k)}\\}$
are all learnable subject to the conditions
$\lambda_{i}^{(k)}>0,\gamma^{(k)}>1,a^{(k)}>2$ for each layer $k$ of the
network.

Algorithm 1 Proximal-Averaged Iterative Shrinkage Algorithm (PAISA)

Input: $\boldsymbol{x}$, K, $\boldsymbol{\lambda}_{1}$,
$\boldsymbol{\lambda}_{2}$, $\boldsymbol{\lambda}_{3}$, $\boldsymbol{\gamma}$,
$\boldsymbol{a}$

Initialize $\boldsymbol{x}_{0},k=0$.

while $k\leq K-1$ do

$\boldsymbol{x}_{k}=\widetilde{\mathcal{F}}(\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{F}(\boldsymbol{r}_{k})))$

$k\leftarrow k+1$

end while

Figure 3: Structure of a layer in the Q-PAN. Quantized weights
($\mathbf{W}_{i}^{Q}$) are obtained from their full precision copy
($\mathbf{W}_{i}^{R}$) via quantization operator $Q(\cdot)$. The intermediate
reconstruction $\boldsymbol{x}^{(k)}$ is processed through convolution filters
$\\{\mathbf{W}_{i}^{Q}\\}$, ReLU transform, proximal operators
$\\{\mathcal{P}_{i}\\}$ to give $\boldsymbol{x}^{(k+1)}.$

###  4.3 Loss Function

The loss function comprises two terms. The first term captures the mean-
squared error between the ground truth $\boldsymbol{x}_{i}$ and the
reconstructed image $\boldsymbol{x}^{(n_{l})}_{i}$, where $n_{l}$ denotes the
number of layers in the network. The second term seeks to enforce
invertibility of the sparsifying transform $\mathcal{F}$ across the layers.
The loss function $\mathcal{L}$ proposed in (Zhang & Ghanem, 2018) is used in
our training:

$\displaystyle\mathcal{L}$ $\displaystyle=$
$\displaystyle\frac{1}{N}{\sum^{n_{b}}_{i=1}\|\boldsymbol{x}^{(n_{l})}_{i}-\boldsymbol{x}_{i}\|^{2}_{2}}$
$\displaystyle+\gamma\,\frac{1}{N}\,{\sum^{n_{b}}_{i=1}\sum^{n_{l}}_{k=1}\|\widetilde{\mathcal{F}}^{(k)}(\mathcal{F}^{(k)}(\boldsymbol{x}_{i}))-\boldsymbol{x}_{i}\|^{2}_{2}},$

where $n_{b}$ is the number of training patches extracted from the images in
the dataset, $n$ is the size of each training patch, $n_{l}$ is the number of
layers of the network, $N=n_{b}n$, and $\gamma$ determines the trade-off
between the two terms under consideration. $\gamma$ is fixed at 0.01 in our
experiments.

###  4.4 PAISA+ Update

The residuals (defined as the difference between the ground truth and its
prediction) of natural images and videos are compressible (Wallace, 1991;
Sullivan et al., 2012). The residual learning framework named ResNet (He et
al., 2015) explicitly formulates the layers of the network to learn residual
functions with reference to the layer inputs. Drawing inspiration from ResNet
and ISTA-Net+, we propose PAISA+, whose iterations are unfolded to yield PAN+,
which learns a residual function for the update $\boldsymbol{x}_{k+1}$,
instead of learning it directly as done in PAN.

The update step is:
$\boldsymbol{x}^{(k+1)}=\boldsymbol{r}^{(k+1)}+\boldsymbol{w}^{(k+1)}+\boldsymbol{e}^{(k+1)}$,
where $\boldsymbol{w}^{(k+1)}$ is the residual and $\boldsymbol{e}^{(k+1)}$ is
the error, as recommended in ISTA-Net+ (Zhang & Ghanem, 2018). The residual
$\boldsymbol{w}^{(k+1)}$ contains the high-frequency component of
$\boldsymbol{x}^{(k+1)}$ missing from $\boldsymbol{r}^{(k+1)}$. It can be
extracted from $\boldsymbol{x}^{(k+1)}$ by an affine transformation
$\mathcal{R}$ i.e., $\boldsymbol{w}^{(k+1)}$ =
$\mathcal{R}(\boldsymbol{x}^{(k+1)})$ =
$\mathcal{G}(\mathcal{D}(\boldsymbol{x}^{(k+1)}))$, where $\mathcal{D}$ has
$n_{f}$ filters (of size $3\times 3$) and $\mathcal{G}$ has one filter (of
size $3\times 3\times n_{f}$).

To obtain a closed-form solution, we model
$\mathcal{F}=\mathcal{H}\circ\mathcal{D}$, where $\mathcal{H}$ is composed of
two convolutional operators separated by a ReLU. Substituting $\mathcal{F}$ in
Eq. (6) by $\mathcal{H}\circ\mathcal{D}$ gives

$\displaystyle\boldsymbol{x}^{(k+1)}$ $\displaystyle=$
$\displaystyle\text{arg}\min_{\boldsymbol{x}}\leavevmode\nobreak\
\leavevmode\nobreak\
\frac{1}{2}\|\mathcal{H}(\mathcal{D}(\boldsymbol{x}))-\mathcal{H}(\mathcal{D}(\boldsymbol{r}^{(k+1)}))\|^{2}_{2}$
$\displaystyle+\sum_{i=1}^{p}\alpha_{i}g_{i}(\mathcal{H}(\mathcal{D}(\boldsymbol{x}))).$

Following the same strategy as in PAISA, we define $\widetilde{\mathcal{H}}$,
the adjoint of $\mathcal{H}$ to be symmetric. The PAISA+ update is:

$\displaystyle\boldsymbol{x}^{(k+1)}$ $\displaystyle=$
$\displaystyle\boldsymbol{r}^{(k+1)}$
$\displaystyle+\,\mathcal{G}\bigg{(}\widetilde{\mathcal{H}}\bigg{(}\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{H}(\mathcal{D}(\boldsymbol{r}^{(k+1)})))\bigg{)}\bigg{)}.$

The iterations of PAISA+ are unfolded into the layers of a neural network,
henceforth referred to as PAN+. The parameters in all the layers of the model
are learnable, i.e., all convolutional operators $\mathcal{H}$,
$\widetilde{\mathcal{H}}$, $\mathcal{D}$, $\mathcal{G}$ are learned in each
layer of the network, along with parameters involved in the proximal operators
$\mathcal{P}_{i}$. A layer of PAN+ is given by the input-output equation:

$\displaystyle\boldsymbol{x}^{(k)}$ $\displaystyle=$
$\displaystyle\boldsymbol{r}^{(k)}$
$\displaystyle+\,\mathcal{G}^{(k)}\bigg{(}\widetilde{\mathcal{H}}^{(k)}\bigg{(}\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{H}^{(k)}(\mathcal{D}^{(k)}(\boldsymbol{r}^{(k)})))\bigg{)}\bigg{)}.$

The learnable parameters in this case are
{$\lambda_{1}^{(k)},\lambda_{2}^{(k)},\lambda_{3}^{(k)},\\\
a^{(k)},\gamma^{(k)},\mathcal{H}^{(k)},\widetilde{\mathcal{H}}^{(k)},\mathcal{D}^{(k)},\mathcal{G}^{(k)}$}
subject to the conditions $\lambda_{i}^{(k)}>0,\gamma^{(k)}>1,a^{(k)}>2$ for
each layer $k$ of the network. Also, the loss function is augmented with a new
term as done in Eq. (4.3) to enforce the adjoint property:
$\widetilde{\mathcal{H}}^{(k)}\circ\mathcal{H}^{(k)}=\mathcal{I}$.

Algorithm 2 Training strategy for Q-PAN

Input: $\boldsymbol{x}$, $\Phi$, $\boldsymbol{y}$

Output: $\boldsymbol{x}^{*}$

for $\boldsymbol{y},\boldsymbol{x}$ in training data do

for $\mathbf{W}_{Q},\mathbf{W}$ in $\mathcal{F}_{Q},\mathcal{F}$ do

$\mathbf{W}_{Q}\leftarrow Q(\mathbf{W})$

end for

for $\widetilde{\mathbf{W}}_{Q},\widetilde{\mathbf{W}}$ in
$\widetilde{\mathcal{F}}_{Q},\widetilde{\mathcal{F}}$ do

$\widetilde{\mathbf{W}}_{Q}\leftarrow Q(\widetilde{\mathbf{W}})$

end for

for $k$ = 1 : $n_{b}$ do

$\boldsymbol{r}^{(k+1)}=\boldsymbol{x}^{(k)}-\rho{\mathbf{\Phi}^{\textsc{T}}(\mathbf{\Phi}\boldsymbol{x}^{(k)}-\boldsymbol{y})}$

$\boldsymbol{x}^{(k)}=\widetilde{\mathcal{F}}_{Q}^{(k)}\Big{(}\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{F}_{Q}^{(k)}(\boldsymbol{r}^{(k+1)}))\Big{)}$

end for

Compute $\mathcal{L}_{Q}$ per Eq. (5)

for $\mathbf{W}$, $\widetilde{\mathbf{W}}$ in $\mathcal{F}$,
$\widetilde{\mathcal{F}}$ do

$\mathbf{W}\leftarrow\mathbf{W}-\delta\nabla_{\mathbf{W}}\mathcal{L}_{Q}\,|_{\mathbf{W}=\mathbf{W}_{Q}}$

$\widetilde{\mathbf{W}}\leftarrow\widetilde{\mathbf{W}}-\delta\nabla_{\mathbf{W}}\mathcal{L}_{Q}\,|_{\mathbf{W}=\widetilde{\mathbf{W}}_{Q}}$

end for

end for

##  5 Quantized Deep-Unrolled Compressive Sensing Networks

We now consider the effect of quantization of weights in the network. We
consider $K$ bit quantization of the weights. We work with two versions of the
filter weights – the unquantized version and the quantized version. In the
forward pass of Q-PAN, the full precision weights are mapped to the
quantization levels, which are determined in a minimum mean-square error sense
based on the weights obtained in the backpropagation update. The gradients of
the loss function are computed with respect to the quantized weights. The
weight updates happen on the full-precision version. The training strategy for
Q-PAN models has been captured in Algorithm 2, where $Q(\cdot)$ denotes the
quantization operator, defined in Fig. 3. The quantization scheme is
learnable. $Q(\boldsymbol{x})=v\,\cdot\boldsymbol{b}$, where $\boldsymbol{b}$
has integer entries and $v$ is a scale factor. The scale factor is “learned”
from the data $\boldsymbol{x}$. Effectively, we are learning to match the
dynamic range of the quantizer to that of the data.

Table 2: PSNR [dB] comparison between quantized and unquantized networks on
Set11 dataset between techniques from literature and Q-PAN+ (3R) models.

CS |  | Recon | ISTA- | ISTA- |  | 1-bit | 2-bit | 3-bit
---|---|---|---|---|---|---|---|---
Ratio | SDA | Net | Net |  Net+ |  PAN+ |  Q-PAN+ |  Q-PAN+ |  Q-PAN+
1$\%$ | 17.29 | 17.27 | 17.30 | 17.34 | 17.43 | 17.46 | 17.48 | 17.49
4$\%$ | 20.12 | 20.63 | 21.23 | 21.31 | 21.83 | 20.95 | 21.20 | 21.47
10$\%$ | 22.65 | 24.28 | 25.80 | 26.64 | 26.90 | 25.15 | 25.84 | 26.38

Table 3: Comparison between quantized and unquantized networks over average
PSNR [dB] values on BSD68 dataset for different compression ratios. The PAN+
models are of $3$R variant

CS |  |  | 1-bit | 3-bit
---|---|---|---|---
Ratio |  ISTA-Net+ |  PAN+ |  Q-PAN+ |  Q-PAN+
10$\%$ | 25.33 | 25.48 | 24.69 | 25.27
4$\%$ | 22.17 | 22.49 | 21.96 | 22.28
1$\%$ | 19.17 | 19.21 | 19.15, | 19.21

The non-linear sparsifying transform $\mathcal{F}$ in Eq. (2) is modeled using
a convolution network. In Q-PAN, a learnable quantization scheme maps the
filter weights to lower-precision weights resulting in a quantized transform
$\mathcal{F}_{Q}$. The sparsifying transform ($\mathcal{F}_{Q}$) is
represented by conjunction of quantized convolution filters with ReLU. The
update $\boldsymbol{x}$ at $(k+1)^{\text{th}}$ iteration with the quantized
transform is given by

$\boldsymbol{x}_{k+1}=\arg\min_{x}J(x),$ (12)

where

$J(x)\ =\
\sum_{i=1}^{p}\frac{\alpha_{i}}{2\rho}\|\boldsymbol{x}-\boldsymbol{r}^{(k+1)}\|^{2}_{2}+\sum_{i=1}^{p}\alpha_{i}g_{i}(\mathcal{F}_{Q}(\boldsymbol{x})),$

$\rho$ is the step-size and
$\boldsymbol{r}^{(k+1)}=\boldsymbol{x}^{(k)}-\rho{\mathbf{\Phi}^{T}(\mathbf{\Phi}\boldsymbol{x}^{(k)}-\boldsymbol{y})}$.
$\mathcal{F}_{Q}$ could be expressed in matrix form as
$\mathcal{F}_{Q}(\boldsymbol{x})=\mathbf{B}_{Q}\,\text{max}(\mathbf{A}_{Q}\boldsymbol{x},\boldsymbol{0})$,
where $\mathbf{A}_{Q}$ and $\mathbf{B}_{Q}$ correspond to the convolutional
operators with quantized weights. Following the procedure outlined in Section
4, the structure of a layer in Q-PAN is modelled as follows:

$\boldsymbol{x}=\widetilde{\mathcal{F}}_{Q}\Bigg{(}\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{F}_{Q}(\boldsymbol{r}))\Bigg{)},$
(13)

where the learnable parameters are
$\\{\lambda_{i},a,\gamma,\mathcal{F}_{Q},\widetilde{\mathcal{F}_{Q}}\\}$
subject to the conditions $\lambda_{i}>0,\gamma>1,a>2$. The Q-PAN architecture
is depicted visually in Figure 2. Similarly, each layer of the Q-PAN+ model is
given by:

$\boldsymbol{x}=\boldsymbol{r}+\mathcal{G}_{Q}(\widetilde{\mathcal{H}}_{Q}(\sum_{i=1}^{p}\alpha_{i}\mathcal{P}_{i}(\mathcal{H}_{Q}(\mathcal{D}_{Q}(\boldsymbol{r}))))).$
(14)

The weights of Q-PAN+ are also quantized to $K$-bits. The loss function with
weight quantization in the learning framework is given by

$\displaystyle\mathcal{L}_{Q}$ $\displaystyle=$
$\displaystyle\frac{1}{N}{\sum^{n_{b}}_{i=1}\|\boldsymbol{x}^{n_{l}}_{i}-\boldsymbol{x}_{i}\|^{2}_{2}}$
$\displaystyle+\gamma\,\frac{1}{N}\,{\sum^{n_{b}}_{i=1}\sum^{n_{l}}_{k=1}\|\widetilde{\mathcal{F}}_{Q}^{(k)}(\mathcal{F}_{Q}^{(k)}(\boldsymbol{x}_{i}))-\boldsymbol{x}_{i}\|^{2}_{2}}.$

Once the training is completed, only the quantized version of the weights is
retained for inference. The architecture of one layer of Q-PAN is depicted in
Fig. 3.

##  6 Experimental Results and Discussion

We validate the performance of our networks, PAN, PAN+ and their quantized
counterparts, namely, Q-PAN and Q-PAN+ on natural image recovery and MR image
reconstruction from compressed measurements. The results corresponding to PAN+
and Q-PAN+ are reported here. Due to space constraints, the results
corresponding to PAN and Q-PAN are reported in the Supplementary Document. For
performance assessment and comparison, we use peak signal-to-noise ratio
(PSNR) and structural similarity index metric (SSIM) (Zhou Wang et al., 2004).

Figure 4: Comparative performance of Quantized ISTA-Net+, Q-PAN+ (2R) and
Q-PAN+ (3R) on Set11 dataset for CS Ratio = 10 with varying quantization bits

Figure 5: Reconstruction results for Flintstones image based on 10% compressed
measurements. Figure 6: Foreman (Set11) image reconstruction for CS ratio 10%
by the proposed 1-bit Quantized models. The bottom row visualizes the absolute
difference between the ground truth and the reconstructed images. The numbers
indicate the PSNR, SSIM values. Figure 7: MR Image Reconstruction: Performance
comparison of Q-PAN+ with the full-precision models, namely, PAN (Ours), ISTA-
Net, and ISTA-Net+ in terms of PSNR as a function of CS ratio. One can infer
that Q-PAN+ with $1$-bit quantization achieves image reconstruction
performance on par with that of the full-precision models.

Several CS techniques (Li et al., 2013; Metzler et al., 2016; Zhang et al.,
2017; Mousavi et al., 2015; Kulkarni et al., 2016) are shown to be under-
performing in comparison to ISTA-Net and ISTA-Net+ (Zhang & Ghanem, 2018).
Therefore we compare the proposed PAN+ and Q-PAN+ models with ISTA-Net+ and
quantized ISTA-Net+ (Q-ISTA-Net+) in the context of compressed image
reconstruction. ISTA-Net+ uses single regularizer i.e. $\ell_{1}$ penalty,
where as PAN+ (3R) models employs two additional regularizers (SCAD and MCP).
The performance improvement of PAN+ (3R) over ISTA-Net+ authenticates the
superiority of three regularizers over one.

To ensure fair comparison, we use the same set of images as recommended in
(Zhang & Ghanem, 2018) to train our models. The loss function, number of
layers in the networks, the size and number of filters learned in the
sparsifying function $\mathcal{F}$ are maintained the same for all the
networks under consideration. The compressed measurements $\boldsymbol{y}$ are
computed as $\boldsymbol{y}=\mathbf{\Phi}\boldsymbol{x}$, where
$\mathbf{\Phi}\in\mathbb{R}^{m\times n}$ and $m$ varies depending on the
compressive sensing (CS) ratio. The measurement matrix $\mathbf{\Phi}$ is
obtained by orthonormalizing the rows of a random Gaussian matrix. In training
our models, we set the batch size $n_{b}$ to $64$, and the number of layers
$n_{l}$ as 9. In the transform $\mathcal{F}$, $n_{f}=32$ filters of size
$3\times 3$ are learned in the first convolutional operation. The second
convolutional operator learns $n_{f}=32$ filters each of size $3\times 3\times
32$.

The training data consists of 88,912 cropped image patches each of size 33
$\times$ 33\. We trained the network models considering CS ratios of $1\%,4\%$
and $10\%$ . The training and inference is carried out on a workstation with
dual Intel® Xeon® Silver 4110 processors and RTX2080Ti GPU. The models are
trained for 100 epochs and take approximately 9 hours. The PAN+ (2R), Q-PAN+
(2R) models employ two regularizers, namely the $\ell_{1}$ penalty and the MC
penalty. The convex combination weights are fixed as
$\alpha_{1}=\alpha_{2}=\frac{1}{2}$. The PAN+ (3R), Q-PAN+ (3R) models
additionally use the SCAD penalty alongside $\ell_{1}$ and the MCP with
$\alpha_{1}=\alpha_{2}=\alpha_{3}=\frac{1}{3}$.

The models are tested on the widely used Set11 (Kulkarni et al., 2016) and
BSD68 (Martin et al., 2001) datasets, which contain 11 and 68 grayscale images
respectively. We report the average PSNR over the test images in Table 3. To
compare the effect of quantization on various models, we trained quantized
versions of ISTA-Net+ also. The variation of PSNR with the change in
quantization bit-width is captured in Figure 4. We observe that Q-PAN+ (3R)
outperforms Q-ISTA-Net+ consistently across different quantizations. The CS
reconstructions by the proposed models are shown in Figs. 5 and 6 for visual
inspection. From the zoomed-in figure (cf. Fig. 5), one can infer that the
PAN+ (3R) model preserves the structure of the ground truth better, in
comparison to the benchmark reconstructions. From the reconstruction error
images (cf. Fig. 6) from the $1$-bit quantized models, one can observe that
the Q-PAN+ (3R) model contains fewer artefacts in its reconstruction.

Table 4: Comparison of average PSNR [dB] on MR images between techniques from
the literature and proposed models with three regularizers.

CS | ADMM- | ISTA- | ISTA- |  | 1-bit | 2-bit | 3-bit
---|---|---|---|---|---|---|---
Ratio | Net | Net |  Net+ |  PAN+ |  Q-PAN+ |  Q-PAN+ |  Q-PAN+
20$\%$ | 37.17 | 38.30 | 38.73, | 38.90 | 38.17 | $38.55$ | 39.13
30$\%$ | 39.84 | 40.52 | 40.89 | 41.02 | 40.36 | $40.76$ | 41.32
40$\%$ | 41.56 | 42.12 | 42.52 | 42.71 | 42.41 | $42.60$ | 43.04
50$\%$ | 43.00 | 43.60 | 44.09 | 44.29 | 43.84 | $44.29$ | 44.41

###  6.1 MR image reconstruction

We evaluate the effectiveness of PAN+ and Q-PAN+ models on the CS MRI problem.
The MR image reconstruction methods sample data in the Fourier space and adopt
the CS theory to reconstruct images. During the reconstruction, the sensing
matrix is obtained through a combination of under-sampling matrix ${\bf P}$
and a discrete Fourier Transform matrix ${\bf F}$ as in ${\bf\Phi=PF}$. We use
the same training and testing brain medical images as in (Zhang & Ghanem,
2018), and train models with $n_{l}=11$ layers for CS ratios of
$20\%,30\%,40\%,50\%$. The comparison between ISTA-Net+, PAN+ (3R), and
$1$-bit Q-PAN+ (3R) techniques is summarized in Table 4. The experimental
results shows that PAN+ outperforms ISTA-Net+ for all the compression ratios
under consideration. Even when extremely quantized 1-bit representations are
used, one can observe that the reconstruction performance degradation is at
most 0.56 dB.

##  7 Conclusion

We proposed a multi-penalty formulation for the problem of compressed image
reconstruction to learn data-driven analysis prior and developed proximal-
averaged iterative shrinkage algorithm for solving it. We then unfolded the
iterations to otain a neural network architecture. Making use of the knowledge
that natural images are compressible in the residual domain, the enhanced
network PAN+ is proposed. We then incorporated a novel learnable quantization
strategy into the unfolded networks and showed that the performance
degradation even considering the extreme case of 1-bit quantization is less
than 1 dB compared with the full precision case. The results present strong
evidence that unfolded proximal-averaging networks with a quantizer
incorporated into the loop in the learning stage offers competitive
performance compared with the full-precision case. This makes a strong case
for deployment of such networks on low-precision hardware.

## References

  * Beck & Teboulle (2009) Beck, A. and Teboulle, M.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  _SIAM Journal on Imaging Sciences_ , 2(1):183–202, 2009.
  * Courbariaux et al. (2015) Courbariaux, M., Bengio, Y., and David, J.-P.  Binaryconnect: Training deep neural networks with binary weights during propagations.  In _Advances in neural information processing systems_ , pp. 3123–3131, 2015.  URL https://arxiv.org/pdf/1511.00363.pdf.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  ImageNet: A Large-Scale Hierarchical Image Database.  In _CVPR09_ , 2009.
  * Donoho et al. (2009) Donoho, D. L., Maleki, A., and Montanari, A.  Message-passing algorithms for compressed sensing.  _in Proceedings of the National Academy of Sciences, U.S.A._ , 106(45):18914–18919, 2009.
  * Duncan et al. (2020) Duncan, K., Komendantskaya, E., Stewart, R., and Lones, M.  Relative robustness of quantized neural networks against adversarial attacks.  In _2020 International Joint Conference on Neural Networks (IJCNN)_ , pp. 1–8, 2020.  doi: 10.1109/IJCNN48605.2020.9207596.
  * Elad et al. (2007) Elad, M., Milanfar, P., and Rubinstein, R.  Analysis versus synthesis in signal priors.  _Inverse Problems_ , 23(3):947, 2007.
  * Fan & Li (2001) Fan, J. and Li, R.  Variable selection via nonconcave penalized likelihood and its oracle properties.  _Journal of the American Statistical Association_ , 96:1348–1360, 02 2001.  doi: 10.1198/016214501753382273.
  * Figueiredo et al. (2007) Figueiredo, M. A., Bioucas-Dias, J. M., and Nowak, R. D.  Majorization-minimization algorithms for wavelet-based image restoration.  _IEEE Transactions on Image Processing_ , 16(12):2980–2991, 2007.
  * He et al. (2015) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  _CoRR_ , abs/1512.03385, 2015.  URL http://arxiv.org/abs/1512.03385.
  * Hubara et al. (2016) Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., and Bengio, Y.  Binarized neural networks.  In _Advances in Neural Information Processing Systems_ , volume 29, pp. 4107–4115. Curran Associates, Inc., 2016.
  * Hubara et al. (2018) Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., and Bengio, Y.  Quantized neural networks: Training neural networks with low precision weights and activations.  _Journal of Machine Learning Research_ , 18(187):1–30, 2018.
  * Jacob et al. (2020) Jacob, M., Ye, J. C., Ying, L., and Doneva, M.  Computational MRI: Compressive Sensing and Beyond.  _IEEE Signal Processing Magazine_ , 37(1):21–23, 2020.  doi: 10.1109/MSP.2019.2953993.
  * Kamilov (2017) Kamilov, U. S.  A parallel proximal algorithm for anisotropic total variation minimization.  _IEEE Transactions on Image Processing_ , 26(2):539–548, 2017.  doi: 10.1109/TIP.2016.2629449.
  * Kim et al. (2010) Kim, Y., Nadar, M. S., and Bilgin, A.  Compressed sensing using a gaussian scale mixtures model in wavelet domain.  In _2010 IEEE International Conference on Image Processing_ , pp. 3365–3368, 2010.  doi: 10.1109/ICIP.2010.5652744.
  * (15) Krizhevsky, A., Nair, V., and Hinton, G.  Cifar-10 (canadian institute for advanced research).  URL http://www.cs.toronto.edu/~kriz/cifar.html.
  * Kulkarni et al. (2016) Kulkarni, K., Lohit, S., Turaga, P., Kerviche, R., and Ashok, A.  ReconNet: Non-iterative Reconstruction of Images from Compressively Sensed Measurements.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 449–458, 2016.  doi: 10.1109/CVPR.2016.55.
  * LeCun & Cortes (2010) LeCun, Y. and Cortes, C.  MNIST handwritten digit database.  2010\.  URL http://yann.lecun.com/exdb/mnist/.
  * Li et al. (2013) Li, C., Yin, W., Jiang, H., and Zhang, Y.  An efficient augmented lagrangian method with applications to total variation minimization.  _Computational Optimization and Applications_ , 56:507–530, 12 2013.  doi: 10.1007/s10589-013-9576-1.
  * Liu et al. (2016) Liu, Y., Zhan, Z., Cai, J. F., Guo, D., Chen, Z., and Qu, X.  Projected iterative soft-thresholding algorithm for tight frames in compressed sensing magnetic resonance imaging.  _IEEE Transactions on Medical Imaging_ , 35(9):2130–2140, 2016.
  * Liu et al. (2018) Liu, Z., Wu, B., Luo, W., Yang, X., Liu, W., and Cheng, K.  Bi-Real Net: Enhancing the Performance of 1-bit CNNs with Improved Representational Capability and Advanced Training Algorithm.  _CoRR_ , abs/1808.00278, 2018.
  * Martin et al. (2001) Martin, D., Fowlkes, C., Tal, D., and Malik, J.  A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics.  In _ICCV_ , volume 2, pp. 416–423 vol.2, 2001.  doi: 10.1109/ICCV.2001.937655.
  * Meng et al. (2020) Meng, X., Bachmann, R., and Khan, M. E.  Training binary neural networks using the Bayesian learning rule.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 6852–6861. PMLR, 13–18 Jul 2020.
  * Metzler et al. (2016) Metzler, C. A., Maleki, A., and Baraniuk, R. G.  From denoising to compressed sensing.  _IEEE Transactions on Information Theory_ , 62(9):5117–5144, 2016.
  * Mousavi et al. (2015) Mousavi, A., Patel, A. B., and Baraniuk, R. G.  A deep learning approach to structured signal recovery.  _53rd Annual Allerton Conference on Communication, Control, and Computing_ , pp. 1336–1343, 2015.
  * Nair & Hinton (2010) Nair, V. and Hinton, G.  Rectified Linear Units Improve Restricted Boltzmann Machines.  _in Proceedings of the International Conference on Machine Learning_ , 27:807–814, 06 2010.
  * Quinsac et al. (2010) Quinsac, C., Basarab, A., Kouamé, D., and Grégoire, J.  3D Compressed sensing ultrasound imaging.  In _2010 IEEE International Ultrasonics Symposium_ , pp. 363–366, 2010.  doi: 10.1109/ULTSYM.2010.5935479.
  * Rastegari et al. (2016) Rastegari, M., Ordonez, V., Redmon, J., and Farhadi, A.  XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks, 2016.  URL http://arxiv.org/abs/1603.05279.  cite arxiv:1603.05279.
  * Rubinstein et al. (2013) Rubinstein, R., Peleg, T., and Elad, M.  Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model.  _IEEE Transactions on Signal Processing_ , 61(3):661–677, 2013.  doi: 10.1109/TSP.2012.2226445.
  * Stinco et al. (2014) Stinco, P., Greco, M., Gini, F., and Manna, M. L.  Compressed spectrum sensing in cognitive radar systems.  In _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 81–85, 2014.  doi: 10.1109/ICASSP.2014.6853562.
  * Sullivan et al. (2012) Sullivan, G. J., Ohm, J.-R., Han, W., and Wiegand, T.  Overview of the High Efficiency Video Coding (HEVC) Standard.  _IEEE Transactions on Circuits and Systems for Video Technology_ , 22(12):1649–1668, 2012.
  * Sungkwang Mun & Fowler (2009) Sungkwang Mun and Fowler, J. E.  Block compressed sensing of images using directional transforms.  In _2009 16th IEEE International Conference on Image Processing (ICIP)_ , pp. 3021–3024, 2009.  doi: 10.1109/ICIP.2009.5414429.
  * Tian & Giannakis (2007) Tian, Z. and Giannakis, G. B.  Compressed sensing for wideband cognitive radios.  In _2007 IEEE International Conference on Acoustics, Speech and Signal Processing - ICASSP ’07_ , volume 4, pp. IV–1357–IV–1360, 2007.  doi: 10.1109/ICASSP.2007.367330.
  * Wallace (1991) Wallace, G. K.  The JPEG Still Picture Compression Standard.  _Communications of the ACM_ , 34:31–44, April 1991.
  * Wan et al. (2020) Wan, D., Shen, F., Liu, L., Zhu, F., Huang, L., Yu, M., Shen, H. T., and Shao, L.  Deep quantization generative networks.  _Pattern Recognition_ , 105:107338, 2020.  ISSN 0031-3203.  doi: https://doi.org/10.1016/j.patcog.2020.107338.
  * Wang et al. (2019) Wang, P., Wang, D., Ji, Y., Xie, X., Song, H., Liu, X., Lyu, Y., and Xie, Y.  QGAN: quantized generative adversarial networks.  _CoRR_ , abs/1901.08263, 2019.  URL http://arxiv.org/abs/1901.08263.
  * Willett et al. (2012) Willett, R. M., Marcia, R. F., and Nichols, J.  Compressed sensing for practical optical imaging systems: A tutorial.  In _IEEE Photonics Conference 2012_ , pp. 586–586, 2012.  doi: 10.1109/IPCon.2012.6358756.
  * Zhang (2010) Zhang, C.-H.  Nearly unbiased variable selection under minimax concave penalty.  _The Annals of Statistics_ , 38(2):894–942, 2010\.
  * Zhang et al. (2018) Zhang, D., Yang, J., Ye, D., and Hua, G.  Lq-nets: Learned quantization for highly accurate and compact deep neural networks.  _CoRR_ , abs/1807.10029, 2018.
  * Zhang & Ghanem (2018) Zhang, J. and Ghanem, B.  ISTA-Net: Interpretable optimization-inspired deep network for image compressive sensing.  _in Proceedings of International Conference on Computer Vision and Pattern Recognition_ , pp. 1828–1837, 2018.
  * Zhang et al. (2014) Zhang, J., Zhao, C., Zhao, D., and Gao, W.  Image compressive sensing recovery using adaptively learned sparsifying basis via $\ell_{0}$ minimization.  _Signal Processing_ , 103:114–126, 10 2014.  doi: 10.1016/j.sigpro.2013.09.025.
  * Zhang et al. (2014) Zhang, J., Zhao, D., and Gao, W.  Group-based sparse representation for image restoration.  _IEEE Transactions on Image Processing_ , 23(8):3336–3351, 2014.
  * Zhang et al. (2017) Zhang, K., Zuo, W., Gu, S., and Zhang, L.  Learning deep CNN denoiser prior for image restoration.  In _in Proceedings of International Conference on Computer Vision and Pattern Recognition_ , pp. 2808–2817, 2017.  doi: 10.1109/CVPR.2017.300.
  * Zhong & Kwok (2014) Zhong, L. W. and Kwok, J. T.  Gradient descent with proximal average for nonconvex and composite regularization.  _Twenty Eighth AAAI Conference on Artificial Intelligence_ , 3:2206–2212, 01 2014.
  * Zhou Wang et al. (2004) Zhou Wang, Bovik, A. C., Sheikh, H. R., and Simoncelli, E. P.  Image quality assessment: from error visibility to structural similarity.  _IEEE Transactions on Image Processing_ , 13(4):600–612, 2004.  doi: 10.1109/TIP.2003.819861.
  * Zhu et al. (2020) Zhu, B., Al-Ars, Z., and Hofstee, H. P.  Nasb: Neural architecture search for binary convolutional neural networks.  In _2020 International Joint Conference on Neural Networks (IJCNN)_ , pp. 1–8, 2020.  doi: 10.1109/IJCNN48605.2020.9207674.


# TReR: A Lightweight Transformer Re-Ranking Approach
for 3D LiDAR Place Recognition

Tiago Barros, Luís Garrote, Martin Aleksandrov, Cristiano Premebida, Urbano J.
Nunes T. Barros, L. Garrote, C. Premebida, and U.J. Nunes are with the
University of Coimbra, Institute of Systems and Robotics, Department of
Electrical and Computer Engineering, Portugal. E-mails:{tiagobarros, garrote,
cpremebida<EMAIL_ADDRESS>Martin Aleksandrov is with Dahlem Center for
Machine Learning and Robotics, Freie Universität Berlin, Berlin. E-mail:
<EMAIL_ADDRESS>
###### Abstract

Autonomous driving systems often require reliable loop closure detection to
guarantee reduced localization drift. Recently, 3D LiDAR-based localization
methods have used retrieval-based place recognition to find revisited places
efficiently. However, when deployed in challenging real-world scenarios, the
place recognition models become more complex, which comes at the cost of high
computational demand. This work tackles this problem from an information-
retrieval perspective, adopting a first-retrieve-then-re-ranking paradigm,
where an initial loop candidate ranking, generated from a 3D place recognition
model, is re-ordered by a proposed lightweight transformer-based re-ranking
approach (TReR). The proposed approach relies on global descriptors only,
being agnostic to the place recognition model. The experimental evaluation,
conducted on the KITTI Odometry dataset, where we compared TReR with s.o.t.a.
re-ranking approaches such as $\alpha QE$ and SGV, indicate the robustness and
efficiency when compared to $\alpha QE$ while offering a good trade-off
between robustness and efficiency when compared to SGV.

##  I INTRODUCTION

Place recognition has become a popular approach to perform global localization
and loop closure detection [1]. With the development of efficient deep
learning (DL) techniques able to model geometrical information, 3D LiDAR
information has gained increasing relevance in place recognition due to being
more robust compared to visual data in appearance-changing environments: a
feature of key importance in the long-term operation of autonomous vehicles
[2]. In 3D LiDAR-based place recognition, DL networks are used to map the
geometrical information (i.e. point clouds) into an adequate descriptor space,
where descriptors from nearby physical places are close. In contrast,
descriptors from farther physical places are apart. Nevertheless, as the DL-
based models are exposed to more realistic scenarios, the more complex they
become, which usually means more parameters to train and, consequently, more
computational power is required for training. In other fields, such as
information retrieval (IR), a common approach to this problem is the first-
retrieve-then-re-ranking (RTrR) paradigm [3, 4].

Figure 1: A two stage framework with 3D LiDAR-based place recognition and re-
ranking. For a given query $q$ location, a pre-trained place recognition model
first maps the point cloud $P_{q}$ to a descriptor. The descriptor is used to
query a database to return the $k$ nearest neighbors, which represent an
initial loop candidate ranking. The ranking is ordered from the most to the
least similar. This process is illustrated with the following example: for the
query point cloud $P_{q}$ captured from the location $q$, four loop candidates
are returned, which are identified in the map by a number and a shape. The
number represents the initial rank, and the shape represents true loops (green
star) or false loops (red circle).

In an RTrR architecture, two sequential stages take place: an initial coarse
retrieval stage, where pre-trained models are used, and a re-ranking stage,
where smaller re-ranking models are used, trained on a target domain dataset
[5]. In the first stage, the goal is to learn global descriptors from the
input point clouds. In the second stage, the goal is to learn interactions
[6], associating a higher rank to more relevant candidates and a lower rank to
less relevant candidates, such as false positives, as a way to refine the
initial estimate. In traditional loop closure detection, false positives are
identified using geometrical verification approaches such as RANSAC [7] and
Iterative Closest Point [8], which are computationally demanding and, for this
reason, often not being well-suited for large-scale applications.

In this work, we study the viability of the first-retrieve-then-re-ranking
paradigm in place recognition, as shown in Figure 1. Inspired by the success
of re-ranking-based applications in image retrieval [3, 4], our approach,
called TReR, is a lightweight, transformer-based model trained in a supervised
regime. Unlike common transformer-based approaches for vision applications
(e.g. [3, 4]), which rely on local features and return similarity scores for
pairs of images, TReR relies on global descriptors only, making it lightweight
and agnostic to place recognition models. Furthermore, TReR computes
similarity scores for $k$ loop candidates simultaneously instead of pairs.

We assess the adequacy of the approach within a 3D LiDAR place recognition
framework for urban contexts. TReR is evaluated on five different place
recognition models [9, 10, 11], which serve as baselines. Additionally, we
also compare TReR to another global descriptor-based re-ranking approach
($\alpha QE$ [12]) and a geometrical verification (GV) method (SGV[13]). The
results are obtained on the KITTI dataset and indicate that TReR achieves a
greater performance than the baselines (with no re-ranking) and $\alpha QE$
while offering an acceptable trade-off between performance and efficiency in
contrast to SGV[13]. In brief, the main contributions of this work are the
following:

  * •

An lightweight Transformer-based re-ranking approach (TReR) for 3D LiDAR place
recognition that relies only on global descriptors and predicts the relative
similarity scores of $k$ candidates in one forward pass;

  * •

TReR improves retrieval performances compared to other global-based methods
and offers a good compromise between performance and efficiency.

Figure 2: The place recognition framework with two sequential tasks: (1) place
modeling (Loop retrieval) and (2) re-ranking. The first model (Loop retrieval)
receives a query point cloud $P_{q}$ and then returns a loop ranking $L_{q}$
and the corresponding descriptors $D_{q}$. The proposed re-ranking approach
TReR receives the descriptors as input and returns a new ranking $\bar{L}_{q}$
as output.

##  II RELATED WORK

Place recognition has been an active field of research over the last decade,
used in increasingly complex scenarios such as long-term operation in ever-
changing environments [2]. The current endeavor to deal with such scenarios
has been in the direction of proposing more complex models, requiring higher
computational resources, which are not easily available. In other fields, such
as IR, a common approach is to use an RTrT architecture, where, in the first
stage, pre-trained models are used to generate coarse ranking estimates, and
in the second stage, these initial estimates are refined using re-ranking
models [5].

We next outline and discuss works on 3D LiDAR-based place recognition, which
relate to the first stage, and works on re-ranking, which relate to the second
stage.

###  II-A 3D-LiDAR-based Place Recognition

In 3D LiDAR-based place recognition, works such as PointNetVLAD [9] and LPD-
Net [14] pioneered the idea of modeling physical places from point clouds
directly by using end-to-end frameworks. Such frameworks, similar to those for
vision-based place recognition, extract local features from point clouds and
then aggregate the local features into a global descriptor. Over the years,
the research interests have focused on different aspects of place recognition
frameworks.

Some works focus on improving the feature extraction from point clouds e.g.,
addressing the rotation invariance problem in neural networks [15], proposing
more suitable feature extraction operators for point clouds, such as sparse 3D
convolutions [10] and hierarchical graphs [16].

Other works have focused on aggregating local features into global
descriptors. Most aggregators were initially proposed for images, such as the
popular NetVLAD [17], which is a trainable generalization of VLAD [18]. Other
approaches, for instance, resort the attention to re-adjusting the weights of
local features [19], or compute various pooling operations on the local
features, such as sum pooling (SPoC) [20] or generalized-mean pooling (GeM)
[12]. In addition, the combination of the aforementioned aggregators into one
global aggregator to leverage the strength of each aggregator has been
explored in [11].

In this work, we use PointNetVLAD [9], LoGG3D-Net [10], and ORCHNet [11] for
generating global descriptors and, additionally, we have adapted SPoC [20] and
GeM [12] for working with point clouds.

###  II-B Re-Ranking

A re-ranking approach takes an initial ranking estimate and re-orders it based
on a pre-defined criterion. In information retrieval, such a criterion is to
rank higher content that is more relevant for a given query. In retrieval-
based place recognition, the aim is to promote loop candidates that are true
loops while ranking lower false positives.

These re-ranking methods can be categorized into two families: those that use
only global descriptors and those that use local and global features combined.
As for the global descriptors only, a widely used approach is Query Expansion
(QE). In particular, $\alpha QE$ has been used both in image retrieval [12]
and retrieval-based place recognition [13]. On the other hand, the category of
methods that use both local and global information is more common in
applications with geometrical data. For instance, RANSAC [7] and Iterative
Closest Point [8] are widely adopted in localization-related tasks, where they
are employed to assess how well two distinct point clouds match. These
methods, known as geometrical verification (GV), work well when seeking false
positives but are usually computationally demanding when working with large
point clouds. More recently, a more efficient approach was proposed in [13]
called spectral geometrical verification (SGV), which relies on correspondence
compatibility graphs [21] to assess the spatial consistency of two point
clouds.

##  III PROPOSED APPROACH

In this section, we describe the proposed Transformer-based Re-Ranking
framework (TReR) outlined in Figure 2. Firstly, we formulate the place
recognition and re-ranking tasks in generic terms. Secondly, we present the
proposed approach in more detail.

###  III-A Problem Formulation

The proposed framework is depicted in Figure 2. It can be split into two sub-
tasks: 1) loop retrieval, using a place recognition approach for generating
$k$ candidates; 2) loop re-ranking, which re-orders the initial loop ranking,
giving greater ranks to the true loops and lower ranks to the false loops.

####  III-A1 Loop Retrieval

A point cloud-based loop retrieval task can be formulated as follows: given a
query 3D point cloud $P_{q}\in\mathbb{R}^{n\times 3}$ with $n$ points, and a
database with descriptors of already visited places, the task goal is to map
$P_{q}$ to a descriptor vector $d_{q}\in\mathbb{R}^{d}$ of $d$ dimensions, and
use $d_{q}$ to query the database to retrieve the $k$ nearest neighbors based
on a similarity score computed using the Euclidean distance. The retriever
returns a set of database indices
$L_{q}=\\{l_{i}\\}_{i=1}^{k}\in\mathbb{N}^{k}$, where $l_{i}$ is the index
(i.e. position in the database) of the $i$-th retrieved loop candidate. The
candidates are ordered from the most similar to the least similar.

In this work, a loop candidate $l_{i}\in L_{q}$ is a true loop, when the loop
candidate is within a given $\zeta$ Euclidean distance from the query: i.e.
both the query and the respective candidate originated from the same place. In
generic terms, this can be formulated by the following function:

$\Gamma:\mathbb{R}^{n\times 3}\rightarrow\mathbb{N}^{k}\mbox{,}$ (1)

where $\Gamma$ can be learned. Since this work focuses on re-ranking, we refer
the reader to [22] for more details on the training procedure for this
learning task.

Figure 3: The loop retrieval framework, where the input point cloud $P_{q}$ is
mapped to the descriptor vector $d_{q}$. The descriptor vector $d_{q}$ is then
used to query the database, after which the $k$ nearest neighbors are
returned, serving as loop candidates $L_{q}$. Both $L_{q}$ and the respective
descriptors $D_{q}$ are returned.

In the main framework, shown in Figure 2, the loop retrieval task is performed
by the “Place Modeling & Loop Retrieval” module, which is detailed in Figure
3. This module returns the loop candidates in $L_{q}$ and their descriptor
vectors in $D_{q}=\\{d_{i}\\}_{i=1}^{k}\in\mathbb{R}^{k\times d}$, where $k$
is the number of retrieved candidates, each of dimension size $d$.

####  III-A2 Re-Ranking

The re-ranking task works on the premise that the initial loop ranking over
candidates from $L_{q}$, contains samples that are not loops (i.e. False
Positives), in which case we need an approach that is specialized in re-
ordering the candidates, ranking higher loop candidates that correspond to
real loops and lower loop candidates that correspond to false positives.
Mathematically, the re-ranking process can be formulated as follows: given an
initial loop ranking over candidates from $L_{q}$ for a given query point
cloud $P_{q}$, a function $\Theta$ such that:

$\Theta:\mathbb{N}^{k}\rightarrow\mathbb{N}^{k}\mbox{,}$ (2)

maps the initial ranking to a new ranking over the same $k$ candidates, whose
corresponding set is $\bar{L}_{q}\in\mathbb{N}^{k}$, where the true positives
are promoted higher, and the false positives are promoted lower.

####  III-A3 Re-ranking training

In this work, we resort to the global descriptor-based learning-to-rank
approach depicted in Figure 2. In a learning-to-rank setting, the function
$\Theta$ is trained. To define the training set, let us define a set of
queries $Q\in\mathbb{N}^{M}$, where $M$ is the number of queries, for each
query $q\in Q$ exists a set of loop candidates $L_{q}\in\mathbb{N}^{k}$, their
respective descriptors $D_{q}\in\mathbb{R}^{k\times d}$ and the ground-truth
relevance scores $Y_{q}=\\{y_{i}=\|p_{q}-p_{l_{i}}\|_{2}|\forall l_{i}\in
L_{q}\\}\in\mathbb{R}^{k}$, where $p_{q}\in\mathbb{R}^{3}$ and
$p_{l_{i}}\in\mathbb{R}^{3}$ are the 3D coordinates of the query $q$ and the
$l_{i}$-th loop candidate, respectively. The training set can thus be defined
as follows:

$\Upsilon=\\{(D_{q},Y_{q})|q\in Q\\}\mbox{.}$ (3)

Given a training set $\Upsilon$, the goal of training is to find
$\hat{\Theta}$, given by:

$\hat{\Theta}=\operatorname*{arg\,min}(\mathcal{L}(\Theta))\mbox{,}$ (4)

that minimizes the overall loss, given by:

$\mathcal{L}(\Theta)=\frac{1}{|\Upsilon|}\sum_{(D_{q},Y_{q})\in\Upsilon}l(Y_{q},\Theta(D_{q}))\mbox{,}$
(5)

with $l$ being a ranking loss function of a single query. This loss is
computed between the ground-truth relevance scores $Y_{q}$, and the predicted
relevance scores $S_{q}=\Theta(D_{q})$.

###  III-B Transformer-based Re-Ranking

This section describes the proposed transformer-based re-ranking approach,
TReR, depicted in Figure 2. Instead of following traditional point cloud-based
loop re-ranking approaches, which rely predominantly on geometrical cues
present in the scene [13], we adopt a more general information re-ranking
approach, mainly used in image-related ranking tasks [3]. We are furthermore
inspired by other works in context ranking, such as [23]. However, our
approach differs in two ways: (a) the re-ranking model in [23] relies on local
features, whereas the TReR model relies only on the global descriptors, which
allows TReR to be used in applications where it is difficult to extract the
local features; (b) the re-ranking model in [23] and the TReR model also have
different output layers. More specifically, we add a max-polling layer
followed by a linear transformation to compute the relative relevance scores
used for re-ranking loop candidates.

####  III-B1 Architecture

The proposed transformer-based re-ranker TReR is based on the multi-layer
transformer encoders as proposed in [24]. We let $C$ denote the number of
transformer encoders. Pick $i\in\\{1,\ldots,C\\}$. The $i$-th transformer
encoder is outlined in Figure 2. We denote the input of the $i$-th transformer
encoder as $Z_{(i)}$. For example, the input of the first encoder (i.e.
$Z_{(1)}$) is the set of global descriptor vectors
$D_{q}\in\mathbb{R}^{k\times d}$. The multi-layer transformer encoder can thus
be defined by the following equations:

$\bar{Z}_{(i+1)}=l_{N}\left(Z_{(i)}+h_{A}(Z_{(i)})\right)\mbox{ and}$ (6)
$Z_{(i+1)}=l_{N}\left(f(\bar{Z}_{(i+1)})\right)\mbox{,}$ (7)

where $l_{N}(\cdot)$ is a normalization layer as proposed in [25] and
$f(\cdot)$ is a multi-layer perceptron network with two linear transformations
and a ReLU activation in between, given by:

$f(Z)=\text{max}(0,Z\,W_{1}+b_{1})\,W_{2}+b_{2}\mbox{,}$ (8)

where $W_{1}\in\mathbb{R}^{d\times d_{h}}$, $W_{2}\in\mathbb{R}^{d_{h}\times
d}$, $b_{1}\in\mathbb{R}^{k\times d_{h}}$, and $b_{2}\in\mathbb{R}^{k\times
d}$ are weights and biases of linear projections, with $d$ being the
input/output dimensionality and $d_{h}$ the hidden dimensionality. The
function $h_{A}(\cdot)$ is a multi-head attention module with $n$ heads,
defined as follows:

$h_{A}(Z)=W_{AO}\,[h_{1},...,h_{j},...,h_{n}]^{T}\mbox{,}$ (9)

where $W_{AO}\in\mathbb{R}^{d\times d\,n}$ and $h_{j}$ is the $j$-th attention
head given by the following equation:

$h_{j}=\sigma(\frac{Q\,K^{T}}{\sqrt{d}})\,V\mbox{,}$ (10)

with $\sigma(\cdot)$ being the softmax function and $d$ is the feature
dimensionality, while $Q$, $K$, and $V$ are, respectively, the queries, keys,
and values. In this work, the attention mechanism is transformed to self-
attention, which results in $Q=Z_{(i)}\,W^{Q}_{j}$, $K=Z_{(i)}\,W^{K}_{j}$,
and $V=Z_{(i)}\,W^{V}_{j}$, where $W^{Q}_{j}$, $W^{K}_{j}$, and
$W^{V}_{j}\in\mathbb{R}^{d\times d}$ are linear projection matrices of the
$j$-th head.

The $i$-th transformer encoder outputs re-weighted descriptors
$Z_{(i+1)}\in\mathbb{R}^{k\times d}$, to which a max-pooling operation is
applied alongside the feature dimensions followed by a linear projection:

$S_{q}=\max(Z_{(i+1)})\,W_{o}+b_{o}\mbox{,}$ (11)

with $S_{q}\in\mathbb{R}^{k}$, whereas $W_{o}\in\mathbb{R}^{k\times k}$ and
$b_{o}\in\mathbb{R}^{k}$ encode the weights and biases, respectively. To
obtain the final re-ranking, TReR sorts $S_{q}$ in a descending direction as
follows:

$\bar{I}_{q}=\operatorname*{arg\,sort}(S_{q})\mbox{,}$ (12)

with $\bar{I}_{q}\in\mathbb{N}^{k}$ being a vector of $k$ dimensions,
containing the reordering indices, which can be used for transforming the
initial ranking of candidates from $L_{q}$ into the final ranking of
candidates from $\bar{L}_{q}$, as illustrated in Figure 2.

####  III-B2 Training

The proposed re-ranking approach is trained in a supervised regime, where the
objective is to maximize the correctness of the relative descriptor order
instead of the absolute relevance. As in other ranking works such as [26] and
[27], we adopt the logistic loss, which is a pairwise loss based on the cross-
entropy and is given by:

$l(Y_{q},S_{q})=\sum_{y_{i}>y_{j}}\text{log}_{2}(1+e^{-\sigma(s_{i}-s_{j})})\mbox{,}$
(13)

where $\sigma$ is an adjustable parameter, and $s_{i},s_{j}\in S_{q}$ and
$y_{i},y_{j}\in Y_{q}$. The advantage of this loss is that it penalizes each
out-of-order pair $(i,j)$ that has $y_{i}>y_{j}$ but $s_{i}<s_{j}$.

TABLE I: The number of frames and loops in the dataset.

Sequence: 00 02 05 06 08 Length [frames]: 4051 4661 2761 1101 4071 Queries
[loops]: 1097 450 692 284 521

TABLE II: The loop retrieval results obtained with the baseline models and the
respective re-ranking models TReR and $\alpha\text{QE}$ on the dataset. All
models were evaluated using a cross-validation approach, tested on a fixed
sequence, and trained on the remaining sequences. The presented results are
the mean recall scores for the test sequence, $Recall@N$ for
$N\in\\{1,5,10\\}$, which are denoted as R1, R5, and R10, respectively,
computed by using the $N$ most relevant loop candidates.

00 02 05 06 08 R1 R5 R10 R1 R5 R10 R1 R5 R10 R1 R5 R10 R1 R5 R10 LoGG3D-Net
0.69 0.75 0.79 0.55 0.58 0.60 0.68 0.76 0.81 0.91 0.94 0.94 0.09 0.25 0.38
LoGG3D-Net + $\alpha\text{QE}$ [12] 0.58 0.71 0.78 0.48 0.58 0.60 0.59 0.72
0.79 0.75 0.91 0.95 0.08 0.25 0.35 LoGG3D-Net + TReR 0.69 0.77 0.79 0.55 0.59
0.61 0.68 0.77 0.82 0.91 0.94 0.95 0.11 0.29 0.42 ORCHNet 0.72 0.77 0.79 0.53
0.57 0.58 0.65 0.71 0.73 0.89 0.94 0.95 0.52 0.70 0.76 ORCHNet +
$\alpha\text{QE}$ [12] 0.60 0.72 0.77 0.40 0.49 0.53 0.52 0.68 0.75 0.74 0.83
0.91 0.52 0.68 0.75 ORCHNet + TReR 0.72 0.78 0.81 0.53 0.57 0.58 0.65 0.72
0.74 0.89 0.94 0.95 0.52 0.73 0.78 PointNetVLAD 0.75 0.79 0.81 0.51 0.60 0.65
0.68 0.74 0.77 0.92 0.95 0.96 0.61 0.72 0.77 PointNetVLAD + $\alpha\text{QE}$
[12] 0.58 0.73 0.78 0.42 0.62 0.66 0.64 0.75 0.79 0.79 0.93 0.94 0.57 0.70
0.78 PointNetVLAD + TReR 0.75 0.81 0.82 0.51 0.63 0.66 0.68 0.74 0.78 0.92
0.95 0.97 0.61 0.75 0.80 PoinNetSPoC 0.68 0.76 0.78 0.47 0.56 0.59 0.63 0.70
0.73 0.90 0.93 0.94 0.60 0.74 0.77 PoinNetSPoC + $\alpha\text{QE}$ [12] 0.29
0.56 0.72 0.28 0.52 0.61 0.36 0.67 0.77 0.53 0.83 0.92 0.40 0.65 0.74
PoinNetSPoC + TReR 0.68 0.76 0.79 0.47 0.58 0.62 0.63 0.71 0.76 0.90 0.93 0.95
0.60 0.74 0.82 PointNetGeM 0.68 0.77 0.80 0.49 0.60 0.64 0.63 0.71 0.75 0.91
0.95 0.97 0.63 0.75 0.82 PointNetGeM + $\alpha\text{QE}$ [12] 0.23 0.51 0.68
0.29 0.54 0.63 0.32 0.59 0.73 0.59 0.79 0.90 0.55 0.72 0.79 PointNetGeM + TReR
0.68 0.78 0.81 0.49 0.61 0.66 0.63 0.74 0.78 0.91 0.97 0.97 0.63 0.80 0.84

##  IV EXPERIMENTAL EVALUATION

In this section, we describe the experimental and the implementation parts. We
also present and discuss the obtained empirical results.

###  IV-A Dataset

The proposed approach is evaluated on the KITTI Odometry benchmark [28], a
widely used dataset in various localization and place recognition works. This
dataset comprises $22$ sequences with 3D LiDAR, RGB, and RTK-GPS data from
urban, highway, and rural environments, representing thus a variety of
scenarios that an autonomous vehicle may encounter in real scenarios. Since
this work is partly focused on loop retrieval, from within the $22$ original
sequences, we only used the sequences that contain revisited segments, which
are 00, 02, 05, 06, and 08. Sequence 08 is particularly important because it
is the only sequence that has revisits from the opposing direction. As a
result, sequence 08 promotes an additional challenge for place recognition
methods. In this work, we assume that a loop exists in a given sequence
whenever two point clouds were captured from places within a range of 25 m as
proposed in [22]. Table I contains the number of loops in each sequence under
this assumption and the number of sequence frames.

(a)

(b)

Figure 4: Comparison between TReR, Spectral Geometric Verification (SGV), and
$\alpha$-Query Expansion ($\alpha$QE). LoGG3D-Net was used as a baseline. Key:
a) the results for $Recall@k$ on sequence 00; b) the results for $Recall@k$ on
sequence 08.

###  IV-B Experimental Setup

All experiments were conducted in Python 3.8 using the PyTorch framework with
CUDA 11.6. All models were evaluated using a cross-validation approach:
e.g.the descriptors of sequence 08 were obtained using a model trained on
sequences 00, 02, 05, and 06. As for the training, all models were trained by
using the AdamW optimizer with a learning rate (Lr) of 0.0001 and a weight
decay (Wd) of 0.0005.

####  IV-B1 Baselines

TReR was evaluated on global descriptors with 256 dimensions, which were
generated by five different models: PointNetVLAD [22], ORCHNet [11],
LoGG3D-Net [10], PoinNetSPoC, and PoinNetGeM. PoinNetVLAD and ORCHNet were
originally proposed with PointNet as backbone [29]. SPoC [20] and GeM [30]
were adapted to be implemented on a PointNet-based framework. For clouds with
less than 10 thousand points, preliminary experiments conducted with
PointNetVlAD, ORCHNet, PoinNetSPoC, and PoinNetGeM indicated that the
performance of these models increased with the number of points in the input
point clouds. For point clouds with more than 10 thousand points, the
performance stagnated. Given these findings, we concluded that a point cloud
with 10 thousand points was acceptable for preserving performance and
computational demand, which led us to down-sample all point clouds to 10k
points using a random sampling approach. The weights of PointNetVlAD [22],
ORCHNet [11], PoinNetSPoC, and PoinNetGeM were trained based on the training
protocol described in [9]. The weights of LoGG3D-Net [10] were pre-trained.

####  IV-B2 Re-Ranking

We performed experiments on a TReR architecture with one self-attention head
(i.e. $n=1$) and one transformer encoder (i.e. $C=1$). As for the input, the
descriptors had a size of 256 (i.e. $d=256$), the number of maximum candidates
was 25 (i.e. $k=25$), and $d_{h}=512$. With this architecture, TReR had in
total 396,033 learnable parameters, which is 4% of LoGG3D-Net’s parameters
(8,834,583) and 2% of PoinNetVLAD’s parameters (19,779,145).

####  IV-B3 Evaluation

The recall metric is a popular metric for measuring the performance of methods
not only in place recognition but also in machine learning. The recall is
defined as follows:

$Recall=\frac{\mbox{TP}}{\mbox{TP}+\mbox{FN}}\mbox{,}$ (14)

i.e. the ratio between true positive (TP) and the sum of the true positive and
false negative (FN) loops in the ranking. For evaluating the methods, we use
$Recall@k$, where $k$ is the number of candidates retrieved from the database.

###  IV-C Re-Ranking Evaluation

We next present and discuss the empirical results. Firstly, we give the
results for the baseline methods without re-ranking and with re-ranking, using
TReR (our approach) and $\alpha\text{QE}$ [12]. Secondly, we compare TReR to
the spectral geometrical verification (SGV) method [13] and $\alpha\text{QE}$,
using as place recognition model LoGGNet3D-Net.

####  IV-C1 Global Descriptors Only

We compared the proposed approach TReR with the baselines and
$\alpha\text{QE}$ [12], which takes top-ranking candidates of a query and
generates an updated query. The results are presented in Table II. Overall,
they indicate that adding TReR on top of the baseline methods improves the
overall performance in terms of $Recall@k$ with $k=[1,5,10]$. TReR tended to
have more effect in the middle of the ranking, lifting lower-ranked candidates
while leaving unchanged upper-ranked candidates. The results were consistent
throughout all models and sequences, indicating the robustness of TReR. On the
one hand, TReR had a low impact on ranking estimates that required
substantially fewer re-ranking moves, which was the case for sequence 06. On
the other hand, TReR had a high impact on ranking estimates that required
substantially more re-ranking moves, which was the case for sequence 08. This
might be because, as we mentioned, sequence 08 is the most challenging, due to
having revisits from the opposing direction. Finally, $\alpha\text{QE}$
underperformed in all experiments. For this reason, we concluded that this
approach might not be adequate for this application.

####  IV-C2 Comparison to SGV

Furthermore, we compared TReR to the SGV method [13], which relies on local
features and key points to find local feature correspondence. GV-based
approaches are usually known for their robustness, whereas approaches that use
only global descriptors are usually known for their efficiency. We also
observed such performance in our experiments. In Figure 4, we report the
results on sequences 00 and 08 for the baseline method LoGGNet3D-Net without
re-ranking and LoGGNet3D-Net with re-ranking obtained with TReR, SGV, and
$\alpha\text{QE}$. Sequences 00 and 08 represented two interesting edge cases
for the methods. On sequence 00, SGV outperformed TReR and $\alpha\text{QE}$,
confirming the robustness of GV-based approaches. By comparison, on sequence
08, TReR outperformed SGV and $\alpha\text{QE}$, confirming the efficiency of
global-descriptors-only-based approaches. The fact that SGV performed worse
than TReR on sequence 08 might be explained by the inability of SGV to find
consistencies in pairs of point clouds that are significantly misaligned. In
contrast, TReR does not use such local features and key points and, for this
reason, performed better than SGV on sequence 08.

###  IV-D Runtime Analysis

For each query, TReR re-ranked 25 candidates in a single forward pass, which
took approximately 0.3 s of processing time on average on an AMD Ryzen 9 5900X
12-Core CPU with 64 GB RAM, and 0.001 s of processing time on average on a
GeForce RTX 3090 24GB GPU. These and other runtime results are outlined in
Table III. The approach that achieved the lowest performance was $\alpha QE$.
Regarding SGV, we were not able to run it on our GPU due to memory
constraints. In more detail, SGV required over 27GB of memory when computing
key points and local features extracted from the clouds of 10 thousand points,
whereas the GeForce RTX3090 had only 24GB for storing such points.
Nevertheless, even when accounting just for the CPU time, we could observe
that TReR is substantially more efficient than SGV.

TABLE III: The average processing time per query.

Methods CPU(s) GPU(s) TReR 0.30$\,\pm$ 0.12 0.001 $\pm$0.0005 SGV 18 $\pm$ 2.1
- $\alpha$QE 0.00016 $\pm$0.000002 0.00016 $\pm$0.000002

##  V Conclusion

We proposed a 3D LiDAR-based place recognition re-ranking approach called
TReR. TReR uses a lightweight transformer-based architecture with global
descriptors to re-rank, in a first-retrieve-then-re-ranking paradigm, an
initial ranking estimate from a 3D place recognition model. The experimental
evaluation was conducted on the KITTI Odometry dataset and highlighted the
importance of re-ranking predictions for improving recall over several
baseline methods that use no re-ranking and methods such as $\alpha QE$ that
use re-ranking. The improvement in recall was consistent over the baselines,
showing the robustness of TReR. Similar results were observed when considering
the method SGV. TReR improved place recognition model performance,
specifically when considering challenging sequences such as sequence 08.
Finally, TReR showed a good trade-off between performance and efficiency
compared to the SGV method.

## ACKNOWLEDGMENTS

This work has been partially supported by the project “GreenBotics” (ref.
PTDC/EEI-ROB/2459/2021), funded by Fundação para a Ciência e a Tecnologia
(FCT), Portugal. It was also supported by FCT through grant UIDB/00048/2020
and under the Ph.D. grant with reference 2021.06492.BD. Martin Damyanov
Aleksandrov was supported by the DFG Individual Research Grant on “Fairness
and Efficiency in Emerging Vehicle Routing Problems” (497791398).

## References

  * [1] D. Cattaneo, M. Vaghi, and A. Valada, “LCDNet: Deep loop closure detection and point cloud registration for LiDAR SLAM,” _IEEE Transactions on Robotics_ , vol. 38, no. 4, pp. 2074–2093, 2022.
  * [2] T. Barros, R. Pereira, L. Garrote, C. Premebida, and U. J. Nunes, “Place recognition survey: An update on deep learning approaches,” _arXiv preprint arXiv:2106.10458_ , 2021.
  * [3] F. Tan, J. Yuan, and V. Ordonez, “Instance-level image retrieval using reranking transformers,” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2021, pp. 12 105–12 115.
  * [4] H. Zhang, X. Chen, H. Jing, Y. Zheng, Y. Wu, and C. Jin, “Etr: An efficient transformer for re-ranking in visual place recognition,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2023, pp. 5665–5674.
  * [5] W. Chen, Y. Liu, W. Wang, E. M. Bakker, T. Georgiou, P. Fieguth, L. Liu, and M. S. Lew, “Deep learning for instance retrieval: A survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * [6] Y. Fan, X. Xie, Y. Cai, J. Chen, X. Ma, X. Li, R. Zhang, and J. Guo, “Pre-training Methods in Information Retrieval,” _Foundations and Trends® in Information Retrieval_ , vol. 16, no. 3, pp. 178–317, 2022.
  * [7] M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” _Communications of the ACM_ , vol. 24, no. 6, pp. 381–395, 1981.
  * [8] Z. Zhang, “Iterative point matching for registration of free-form curves and surfaces,” _International journal of computer vision_ , vol. 13, no. 2, pp. 119–152, 1994.
  * [9] 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.
  * [10] K. Vidanapathirana, M. Ramezani, P. Moghadam, S. Sridharan, and C. Fookes, “LoGG3D-Net: Locally guided global descriptor learning for 3d place recognition,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 2215–2221.
  * [11] T. Barros, L. Garrote, P. Conde, M. Coombes, C. Liu, C. Premebida, and U. Nunes, “ORCHNet: A robust global feature aggregation approach for 3D LiDAR-based place recognition in orchards,” _arXiv preprint arXiv:2303.00477_ , 2023.
  * [12] F. Radenović, G. Tolias, and O. Chum, “Fine-tuning CNN image retrieval with no human annotation,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 41, no. 7, pp. 1655–1668, 2018.
  * [13] K. Vidanapathirana, P. Moghadam, S. Sridharan, and C. Fookes, “Spectral geometric verification: Re-ranking point cloud retrieval for metric localization,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 5, pp. 2494–2501, 2023.
  * [14] 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.
  * [15] L. Li, X. Kong, X. Zhao, T. Huang, W. Li, F. Wen, H. Zhang, and Y. Liu, “RINet: Efficient 3D LiDAR-based place recognition using rotation invariant neural network,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 4321–4328, 2022.
  * [16] D. W. Shu and J. Kwon, “Hierarchical bidirected graph convolutions for large-scale 3-D point cloud place recognition,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2023.
  * [17] 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.
  * [18] H. Jégou, M. Douze, C. Schmid, and P. Pérez, “Aggregating local descriptors into a compact image representation,” in _2010 IEEE computer society conference on computer vision and pattern recognition_. IEEE, 2010, pp. 3304–3311.
  * [19] T. Barros, L. Garrote, R. Pereira, C. Premebida, and U. J. Nunes, “AttDLNet: Attention-based deep network for 3D LiDAR place recognition,” in _ROBOT2022: Fifth Iberian Robotics Conference: Advances in Robotics, Volume 1_. Springer, 2022, pp. 309–320.
  * [20] A. Babenko and V. Lempitsky, “Aggregating local deep features for image retrieval,” in _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 1269–1277.
  * [21] M. Leordeanu and M. Hebert, “A spectral technique for correspondence problems using pairwise constraints,” in _Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1_ , vol. 2. IEEE, 2005, pp. 1482–1489.
  * [22] M. A. Uy and G. H. Lee, “PointNetVLAD: Deep Point Cloud Based Retrieval for Large-Scale Place Recognition,” in _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 4470–4479.
  * [23] P. Pobrotyn, T. Bartczak, M. Synowiec, R. Białobrzeski, and J. Bojar, “Context-aware learning to rank with self-attention,” _arXiv preprint arXiv:2005.10084_ , 2020.
  * [24] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [25] J. L. Ba, J. R. Kiros, and G. E. Hinton, “Layer normalization,” _arXiv preprint arXiv:1607.06450_ , 2016.
  * [26] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender, “Learning to rank using gradient descent,” in _Proceedings of the 22nd international conference on Machine learning_ , 2005, pp. 89–96.
  * [27] X. Wang, C. Li, N. Golbandi, M. Bendersky, and M. Najork, “The lambdaloss framework for ranking metric optimization,” in _Proceedings of the 27th ACM international conference on information and knowledge management_ , 2018, pp. 1313–1322.
  * [28] A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? The KITTI vision benchmark suite,” in _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2012.
  * [29] 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.
  * [30] J. Komorowski, “MinkLoc3D: Point cloud based large-scale place recognition,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2021, pp. 1790–1799.