# A Bi-directional Quantum Search Algorithm

Zain Hafeez∗ Department of Physics,
Purdue University, West Lafayette, USA
<EMAIL_ADDRESS>Debanjan Konar∗ and Vaneet Aggarwal  Purdue Quantum
Science and Engineering Institute (PQSEI), and
School of Industrial Eng., Purdue University, West Lafayette, USA
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

Grover’s search algorithms, including various partial Grover searches,
experience scaling problems as the number of iterations rises with increased
qubits, making implementation more computationally expensive. This paper
combines Partial Grover’s search algorithm and Bi-directional Search to create
a fast Grover’s quantum search algorithm, referred to as Bi-Directional Grover
Search (BDGS). We incorporated a bi-directional search tactic with a partial
Grover search, starting from an initial state and a single marked state in
parallel. We have shown in this article that our novel approach requires
$\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$
iterations over regular Grover Search and Partial Grover Search (PGS), which
take $\frac{\pi}{4}\sqrt{\mathcal{N}}\sqrt{1-\frac{1}{b}}$ (here,
$\mathcal{N}=2^{r}$ elements, $b$ is the branching factor of partial search
and $k=\lceil\log_{2}b\rceil$). The proposed BDGS algorithm is benchmarked
against the state-of-the-art Depth-First Grover’s Search (DFGS) and generic
Grover’s Search (GS) implementations for $2$ to $20$ qubits and provides
promising results. The Qiskit Python implementation of the proposed BDGS
algorithm is available on Github∗∗∗https://github.com/hafeezzwiz21/DFGS-BDGS.

###### Index Terms:

Grover’s search algorithm, IBM quantum computer, Quantum Computing, Qubit

${}^{\ast}$${}^{\ast}$footnotetext: These authors contributed equally to this
work

##  I Introduction

Grover’s quantum search algorithm [1] is one of the well-known applications of
quantum computing, enabling quantum computers to perform a database search (an
unsorted array) and quadratically outperform their classical counterparts in
terms of time. Despite the efficient database search for an Oracle model
(black box), researchers have shown several Grover circuit implementations
across various platforms [2, 3, 4, 5, 6], as well as theoretical evidence of
the algorithm’s efficiency [7]. Grover’s Search (GS) technique only requires
O($\sqrt{N}$) [8] evaluations to find an item with a high probability in an
unstructured list. Compared to a classical system, Grover’s approach locates
an entity in an unstructured list in fewer steps [1]. One state out of every
conceivable superposition state is the search entity in quantum processing.
Grover’s quantum search algorithm [1] asserts that in a $r$-qubit network,
there are ${2^{r}}$ = $\mathcal{N}$ states, and the chance of discovering each
state is $\frac{1}{N}$. Each state’s amplitude is therefore
$\frac{1}{\sqrt{N}}$. In the classical system, the identical problem requires
a maximum of O($\mathcal{N}$) [1] trials. Bennett _et al._ [8] states that no
quantum approach can, asymptotically, solve the database search problem in
fewer steps than O($\sqrt{\mathcal{N}}$). Subsequently, Boyer _et al._ [9] has
demonstrated that no quantum algorithm with a $50\%$ success probability can
outperform Grover’s method by over a few percentage points. Grover’s search
can solve collision problems, determine a dataset’s mean and median [1], and
reverse-engineer cryptographic hash algorithms by revealing a victim’s
password to an attacker.
However, generic Grover’s quantum search is computationally expensive in terms
of computational time when the number of qubits or circuit depth increases,
even though its implementation yielded a high success rate. To avoid a
comprehensive (Grover) search and high computational complexity, the search
often focuses on a block or collection of items that include the marked state
rather than the marked state itself, and it is known as a Quantum Partial
Search Algorithm (QPSA) [10]. Heiligman (2000) described a partial quantum
search algorithm to find matches between two databases in
$O(\mathcal{N}^{\frac{3}{4}}log\mathcal{N})$ [11]. Of late, a quantum pattern-
matching method, as presented by P. Niroula _et al._ , matches a search string
(pattern) of length $S$ inside a larger text of length $T$ with time
complexity $O(\sqrt{S})$ [12]. A quantum search method for nearest pattern
matching in $O(\sqrt{S})$, where $S$ is the string’s length, is introduced by
P. Mateus [13]. A. Tulsi introduced a quantum search algorithm, which finds a
single element in common between two sets in $O(\sqrt{\mathcal{N}})$ [14].
Grover and Radhakrishnan introduced a fast algorithm for partial Grover search
relying on local and global searches [15] and attains
$\frac{\pi}{4}\sqrt{\mathcal{N}}\sqrt{1-\frac{1}{b}}$ iterations. Recently,
Guo _et al._ introduced an improved version of QPSA using Depth-First Search
(DFS) referred to as Grover’s Search (DFGS) [16].
However, despite its potential in the faster partial Grover search procedures
regarding iteration, partial Grover search algorithms have been limited in
implementation due to their complex formulation [10]. This paper provides a
bi-directional quantum search algorithm, which draws inspiration from the
Quantum Partial Search Algorithm (QPSA) [15, 10] and Depth-First Grover’s
Search (DFGS) [16]. We incorporated a Bi-directional search tactic with QPSA
starting from an initial state and a single marked state in parallel. The
notable contributions of the article are provided as follows.

  1. 1.

In this research, a faster and scalable bi-directional Grover’s search
algorithm (BDGS) relying on partial Grover’s search for any number of qubits
is introduced.

  2. 2.

Furthermore, we have implemented the Depth-First Grover Search Algorithm
(DFGS) [16] on quantum simulation for the first time and benchmarked with the
proposed BDGS with empirical results.

  3. 3.

On parallelization, our novel Bi-directional approach requires
$\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$
iterations over Depth-First Partial Grover Search (DFGS) and the regular
Grover Search.

##  II Partial Grover’s Search

Grover’s algorithm for quantum searching is primarily concerned with searching
an unstructured data array of $\mathcal{N}$ items [17]. Grover’s quantum
search approach has to locate an element in the collection
$\\{L=L_{1},L_{2},L_{3},\ldots L_{\mathcal{N}}\\}$, where $\mathcal{N}$ is the
total number of elements in the set $L$, to be effective. Finding an element
in the collection is necessary for $\delta(x)\rightarrow[0,1]$ [6]. This is
the responsibility of the Boolean function $\delta$. The full Grover search
algorithm locates the marked state in $\mathcal{I}_{f}$ iterations [15].

$\mathcal{I}_{f}=\frac{\pi}{4}\sqrt{\mathcal{N}},\mathcal{N}\longrightarrow\infty$
(1)

The input qubits are first converted into a superposition with equal
coefficients using a Hadamard gate. The initial quantum state is subjected to
phase inversion and inversion around the mean [6].
Grover’s iteration, also known as Grover’s operator, is used in the quantum
Grover search circuit. Grover’s iteration is divided into two phases [17]. In
a marked state, the oracle function first flips the phase of a single
amplitude. The diffusion layer is said to have done its job when the indicated
state amplitude flips over. The target state is inverted, causing its
amplitude to grow dramatically while the amplitudes of the other states only
slightly decrease. The other states maintain their previous amplitude.

###  II-A Oracle

An Oracle [18] is often shown as a black box that inverts the chosen
coefficient of the target base state after receiving the input state,
$|y\rangle$.
Initialization: Due to creating an equal superposition of base states, the
Hadamard gate ($H$ gate) is utilized in the initial stage of Grover’s search
algorithm to put all of the qubits in superposition [18]. The $|0\rangle$
state, _i.e._ ,$\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, is superposed with
equal probability over the $|0\rangle$ and $|1\rangle$ states when a $H$ gate
is applied to it. The following matrix represents an $H$ gate:

$H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&\phantom{-}1\\\ 1&-1\end{bmatrix}.$ (2)

The uniform superposition of every basis vector in the whole database serves
as the starting point for the Grover search as follows [19]:

$|\mathcal{S}\rangle=\frac{1}{\sqrt{\mathcal{N}}}\sum_{y=0}^{\mathcal{N}-1}|y\rangle,\langle\mathcal{S}|\mathcal{S}\rangle=1.$
(3)

Iteratively, the Grover’s algorithm looks for a single target object
$|x\rangle$. A unitary transform is the Grover iteration:

$\mathcal{I}_{G}=-\mathcal{I}_{s}\mathcal{I}_{x},$ (4)

Two inversions on the marked state $|x\rangle$ are presented as
$\mathcal{I}_{s}$ (Diffusion operator) and $\mathcal{I}_{x}$ (Oracle operator)
as follows:

$\mathcal{I}_{s}=I-2|\mathcal{S}\rangle\langle\mathcal{S}|,$ (5)
$\mathcal{I}_{x}=I-2|x\rangle\langle x|$ (6)

where $I$ is an identity operator.
The marked state undergoes a phase flip using the oracle function. All the
states, including the one that is indicated, have an initial amplitude of
$\frac{1}{\sqrt{\mathcal{N}}}$. All states have a mean amplitude of
$\frac{1}{\sqrt{\mathcal{N}}}$. The initial state $\alpha^{(0)}$ has its
amplitude transformed by the phase flip to $-\frac{1}{\sqrt{\mathcal{N}}}$.
The following is the change in mean amplitude ($\mu$).

$\begin{split}\mu^{(0)}=\frac{(\mathcal{N}-1)\beta^{(0)}+\alpha^{(0)}}{\mathcal{N}}\\\
=\frac{(\mathcal{N}-1)\frac{1}{\sqrt{\mathcal{N}}}-\frac{1}{\sqrt{\mathcal{N}}}}{\mathcal{N}}\\\
=\frac{\mathcal{N}-2}{\mathcal{N}\sqrt{\mathcal{N}}}\end{split}$ (7)

the amplitudes of the marked and unmarked states are denoted by $\alpha$ and
$\beta$, respectively.
The Grover iteration $I_{G}$ rotates at an angle $\omega$ in Hilbert space,
moving from $\mathcal{S}$ to the destination $|x\rangle$, where,
$\sin^{2}\omega=\frac{1}{\mathcal{N}}$ and following $t$ iterations

$\mathcal{I}_{G}^{t}|\mathcal{S}\rangle=\sin((2t+1)\omega)|x\rangle+\frac{\cos((2t+1)\omega)}{\sqrt{\mathcal{N}-1}}\sum_{\mathcal{S}\neq
x}^{\mathcal{N}-1}|\mathcal{S}\rangle.$ (8)

Hence, following $\mathcal{I}_{f}=\frac{\pi}{4\omega}-\frac{1}{2}$
repetitions, the amplitudes of all other items vanish, and the probability
amplitude of $|x\rangle$ becomes unity.

$\mathcal{I}_{G}^{t}|\mathcal{S}\rangle=|x\rangle.$ (9)

###  II-B Diffusion

A diffusion model can be implemented as _HX + Oracle + XH_ , where $H$
represents the Hadamard transform and $X$ represents the $Pauli-X$ gate. This
combination inverts the amplitudes surrounding their mean. According to
Grover’s search, the amplitude of the marked state will rise by
$\frac{1}{\sqrt{\mathcal{N}}}$. The marked state $\alpha^{(1)}$ has a new
amplitude that can be calculated using formula 2.$\alpha^{(0)}$-$\mu^{(0)}$.
We can derive $\alpha^{(1)}$ as follows using $\mu^{(0)}$=
$\frac{\mathcal{N}-2}{\mathcal{N}\sqrt{\mathcal{N}}}$ and $\alpha^{(0)}$=
-$\frac{1}{\sqrt{\mathcal{N}}}$ (from Equation 7):

$\begin{split}\alpha^{(1)}=2\frac{(\mathcal{N}-2)}{\mathcal{N}\sqrt{\mathcal{N}}}+\frac{1}{\sqrt{\mathcal{N}}}\\\
=\frac{3(\mathcal{N}-1)}{N\sqrt{\mathcal{N}}}\end{split}$ (10)

###  II-C Partial Grover Search Algorithm

Grover and Radhakrishnan (GRK) [15] proposed a faster quantum search method
for partial search using the same Oracle as the Grover algorithm. The partial
search also begins with the uniform superposition of all base states. The
generic partial Grover search problem considers the following: A database with
$\mathcal{N}$ items is divided into $b$ identically sized blocks.

$\mathcal{B}=\frac{\mathcal{N}}{b}$ (11)

In partial Grover search, approximately
$\frac{\pi}{4}(1-c(b))\sqrt{\mathcal{N}}$ searches are required to locate the
target block [15]. When the blocks are infinitely large
($\mathcal{B}\longrightarrow\infty$), $c(b)$ is a finite positive number that
depends on $b$.
Every block has concurrent local Grover iterations, $j$, as follows.

$\mathcal{I}_{L}=\bigoplus_{j=1}^{b}\mathcal{I}_{L}^{j}=-(\bigoplus_{j=1}^{b}\mathcal{I}_{s}^{l})\mathcal{I}_{x}$
(12)

where each $\mathcal{I}_{L}^{j}=-\mathcal{I}_{s}^{l}\mathcal{I}_{x}$ and
inversion on the marked state (query to the oracle) $|x\rangle$ is
$\mathcal{I}_{x}$ and the local inversion is presented as
$\mathcal{I}_{s}^{l}$ (Diffusion operator)

$\mathcal{I}_{s}^{l}=I-2|\mathcal{S}_{l}\rangle\langle\mathcal{S}_{l}|,$ (13)

The uniform superposition of items in a block, $|\mathcal{S}_{l}\rangle$, is
represented here as follows.

$|\mathcal{S}_{l}\rangle=\frac{1}{\sqrt{\mathcal{B}}}\sum_{i=0}^{\mathcal{B}-1}|z\rangle.$
(14)

Regional repetition $\mathcal{I}_{L}$ is the Grover iteration carried out
concurrently in every block. Only the target block has a non-trivial operation
[rotation] with a new rotation angle $\omega_{l}$ specified by

$\sin^{2}\omega_{l}=\frac{b}{\mathcal{N}}=\frac{1}{\mathcal{B}}$ (15)

Every item in non-target blocks can have its amplitudes eliminated by applying
one more global iteration [20].

$\mathcal{D}=\mathcal{I}_{G}\mathcal{I}_{L}^{j}\mathcal{I}_{G}^{t}|\mathcal{S}\rangle=\sin\omega|x\rangle+\frac{\cos\omega}{\sqrt{\mathcal{B}-1}}\sum_{\mathcal{S}\neq
x}^{\mathcal{B}-1}|\mathcal{S}\rangle.$ (16)

For GRK partial Grover’s search, we randomly select ($b-1$) blocks and apply
Grover’s quantum search method to $\mathcal{N}(1-\frac{1}{b})$ places inside
the selected blocks. This would need
$\frac{\pi}{4}\sqrt{\mathcal{B}(b-1)}=\frac{\pi}{4}\sqrt{\mathcal{N}}\sqrt{\frac{b-1}{b}}$
inquiries are needed, and it is faster than a standard full Grover’s search
[15].

##  III Bi-directional Grover Search Algorithm

A novel approach combining Bi-directional search (BDS) [21] and Partial Grover
Search (PGS) [15] algorithms is proposed and referred to as Bi-directional
Grover Search (BDGS) for faster convergence. In the proposed quantum circuit,
as shown in Figure 1, $U_{\omega}$ and $U_{s}$ are two functions as the Oracle
and Diffuser, respectively. The main idea of BDGS lies in forward and backward
passes from the initial and target states simultaneously until the two search
frontiers intersect. The entire solution path is then formed by concatenating
the path from the start state with the inverse path from the target state.
Optimal solutions are guaranteed using the proposed bi-directional quantum
search algorithm with a time complexity of $O(\sqrt{\mathcal{N}})$, and each
search only needs to go halfway down the solution depth in parallel.
In this proposed BDGS algorithm,
1\. we recursively traversed each possible solution interval at each layer
using Partial Grover Search (quantum operator $\mathcal{I}_{G}$) for $b$
blocks to identify which intervals among the $b$ (branching factor) equal-size
split sub-interval has a solution.
2\. Finally, a standard Grover Search (using quantum operator
$\mathcal{I}_{f}$) is involved in determining the precise address of the
solution for intervals whose widths are less than or equal to $b$.
The proposed BDGS algorithm incorporates Partial Grover Search [21] to
determine the next $k=\lceil\log_{2}b\rceil$ bits in forward and backward
search in BDGS as follows:

$\begin{split}|\underbrace{X_{0}X_{1}\cdots
X_{i}X_{i+1}}_{Found}\underbrace{\square\square}_{Next~{}k}\cdots\rangle\xrightarrow[Forward]{\text{Partial
Grover Search}}\\\ |\underbrace{X_{0}X_{1}\cdots
X_{i}X_{i+1}}_{Found}\underbrace{X_{i+2}X_{i+3}}_{Next~{}k}\cdots\rangle\end{split}$
(17)
$\begin{split}|\cdots\underbrace{\square\square}_{Prev.~{}k}\underbrace{X_{i}X_{i+1}\cdots
X_{r-1}X_{r}}_{Found}\rangle\xrightarrow[Backward]{\text{Partial Grover
Search}}\\\
|\cdots\underbrace{X_{i-2}X_{i-1}}_{Prev.~{}k}\underbrace{X_{i}X_{i+1}\cdots
X_{r-1}X_{r}}_{Found}\rangle\end{split}$ (18)

Here, $X_{i}\in\\{0,1\\}$. Two auxiliary qubits are placed to store the
following: (1) the bits’ found value; and (2) the bits’ status (checked and
unchecked). The qubits will be initialized into a superposition of this
encoding. Assuming $\mathcal{N}=2^{r}$

$\begin{split}|\underbrace{\cdots\cdots}_{Found~{}l}\rangle\otimes\frac{1}{\sqrt{2^{\lfloor
r/2\rfloor-l-1}}}\bigoplus_{i=0}^{\lfloor
r/2\rfloor-l-1}(|0\rangle+|1\rangle)\end{split}$ (19)
$\begin{split}|\underbrace{\cdots\cdots}_{Found~{}l}\rangle\otimes\frac{1}{\sqrt{2^{\lfloor
r/2\rfloor-l}}}\bigoplus_{i=r-1}^{\lfloor
r/2\rfloor-l}(|0\rangle+|1\rangle)\end{split}$ (20)

As shown in Figure 2, since the first four bits are determined on the second
layer, the first four bits are encoded by the auxiliary qubits, which have the
values $A_{1}$ = $0110\cdots$ and $A_{2}$ = $1111\cdots$ as follows.

$\begin{split}|\underbrace{0110}\rangle\otimes\frac{1}{\sqrt{2^{r/2-4-1}}}\bigoplus_{i=0}^{\lfloor
r/2\rfloor-4-1}(|0\rangle+|1\rangle)\end{split}$ (21)

Figure 1: Quantum Circuit schematic for Bi-directional Grover’s Quantum Search
($U_{\omega}$ and $U_{s}$ are oracle and diffuser, respectively.) Figure 2:
Partial Grover Search with Bi-directional Search (BDGS) with $b=4$. The BDGS
steps with $b=4$ denote dividing the database into four parts for every layer
in a bi-directional search with a partial Grover search to get the next two
bits of the solution address.

We aim to find the next $k$ bits using the Partial Grover Search, but the
determined bits are fixed. A pseudo-code for our BDGS algorithm Procedure BDGS
() has been provided to understand the potential readers better.

Begin

Data: Quantum register $Q$, and a target element $x$

Result: Index of target, $x$ if found, else $-1$

1 Procedure BDGS ($k$, $b$, $r$, $x$)

2 // The input-$k$: Number of bits representing segments of the search space,

3 // $b$: Branching factor of the bi-directional tree search space,

4 // $r$: Total number of bits representing the entire database,

5 // $x$: Target element to find.

6 Initialization of Input Qubits

8 7 Initialize Quantum Register $Q$ with $r$ qubits, set to $|0\rangle^{r}$,
$2^{r}=\mathcal{N}$

10 9 Apply Hadamard gates to all input qubits $Q$: $H^{\otimes
r}|0^{r}\rangle$.

11 Initialization of Auxilary Qubits

13 12 Initialize $k=\lceil\log_{2}b\rceil$ auxiliary qubits, $A$ to
$|0\rangle^{k}$.

14 Forward Search Phase

16 15 for  _$j\leftarrow 0$ to $\lfloor\frac{r}{2}\rfloor-1$_

18 17 $s=[j,min(j+k-1,\lfloor\frac{r}{2}\rfloor)]$

19 // Here, $s$ is a qubits segment selected for the current search.

21 20 $j=j+k$

23 22 Perform PGS ($Q,s,x,|A\rangle$)

24 end

25 Backward Search Phase

27 26 for  _$j\leftarrow r-1$ to $\lfloor\frac{r}{2}\rfloor$_

29 28 $s=[max(j-k+1,\lfloor\frac{r}{2}\rfloor)]$.

31 30 $j=j+k$

33 32 Perform PGS ($Q,s,x,|A\rangle$)

34 // Perform partial Grover search, PGS () targeting $x$ on $2$ qubits at a
time.

35

36 end

38 37Measure all qubits, _i.e._ , qubit register $Q$.

40 39 Procedure PGS ($Q,s,x,|A\rangle$)

42 41 Apply Oracle to mark the state corresponding to $x$.

44 43 Apply Diffusion operator to amplify the marked state.

46 45 return

47

48 End

49

Algorithm 1 Bi-directional Grover Search Algorithm

###  III-A Computational Complexity Analysis

In bi-directional search, if forward ($\mathcal{F}$) and backward
($\mathcal{R}$) passes to meet the satisfaction criteria
$\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$, it is considered the target item
has been found. We can create a database with all r-length pathways
($2^{r}=\mathcal{N}$), $\lambda_{1}-\lambda_{2}-\cdots\lambda_{r}$. The
subpath
$\mathcal{F}=\lambda_{1}-\lambda_{2}-\cdots\lambda_{\lfloor\frac{r}{2k}\rfloor}$
path each vertex once.
The proposed BDGS algorithm’s initial step aims to increase the target blocks’
amplitude using Partial Grover Search iteratively. To make it, in Equation 8
$\sin[(2t+1)\omega]=1$, _i.e._ , $(2t+1)\omega=\frac{\pi}{2}$.
Hence, the maximum number of $\mathcal{I_{G}}$ iterations at level $\lambda$
of the bi-directional tree search is evaluated as [15].

$\mathcal{I_{G}}^{\lambda}=\frac{\pi}{4}\sqrt{\frac{\frac{\mathcal{N}}{2}}{b^{\lambda}}}-\frac{\pi}{4}\sqrt{\frac{\frac{\mathcal{N}}{2}}{b^{\lambda+1}}}.$
(22)

Since $(2t+1)\omega=\frac{\pi}{2}$, $\cos[(2t+1)\omega]\approx 0$, which
implies that regardless of the number of iterations, the amplitudes of non-
target blocks are all set to $0$ (Ref: Equation 8).
For example, as shown in Fig. 2, the database requires representing $8$ qubits
($\mathcal{N}=2^{r}$). $\mathcal{F}$ is the initial $2$ qubits’ satisfaction
condition and $\mathcal{R}$ is the final $2$ qubits’ satisfaction requirement,
with $\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$. Therefore, $b=2^{2}$ and
$\mathcal{B}=\frac{\mathcal{N}/2}{b}=4$.
According to GRK’s partial Grover’s search [15], the total number of queries
required for BDGS for a single partial Grover search in both forward and
backward pass at level $\lambda$ is
$\frac{\pi}{4}(\sqrt{\frac{\mathcal{N}/2}{b^{\lambda}}}-\sqrt{\frac{\mathcal{N}/2}{b^{\lambda+1}}})$,
assuming, on an average, each pass comprises $\lfloor\frac{N}{2}\rfloor$
states.
The BDGS procedure does partial or regular Grover searches for intervals with
a size less than or equal to $b$ for each query at level $\lambda$. Hence, the
total complexity of the proposed BDGS is

$\begin{split}2\sum_{\lambda=0}^{r/2k-1}\mathcal{I}_{G}^{\lambda}+\mathcal{I}_{L}\\\
=\underbrace{2\sum_{\lambda=0}^{r/2k-1}\frac{\pi}{4}(\sqrt{\frac{\mathcal{N}/2}{b^{\lambda}}}-\sqrt{\frac{\mathcal{N}/2}{b^{\lambda+1}}})}_{Partial~{}Grover~{}Search}+\underbrace{\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2}}}}_{GS}\\\
=2\frac{\pi}{4}\sqrt{\mathcal{N}/2}-2\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2k}}}+\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2k}}}\\\
=2\frac{\pi}{4}\sqrt{\mathcal{N}/2}-\frac{\pi}{4}\sqrt{\frac{\mathcal{N}/2}{b^{r/2k}}}\\\
=\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})\leq\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}\approx
O(\sqrt{\mathcal{N}})\end{split}$ (23)

We deduce that the average number of oracle calls of BDGS is
$\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$.
Whereas, our BDGS, the DFGS [16] and the standard Grover Search [17], attains
same the average computational complexity of $O(\sqrt{\mathcal{N}})$.

##  IV Simulation Results

Figure 3: Design of Oracle for the proposed Bi-directional Grover Search for
$b=4$ Figure 4: Plot for Runtime (s) vs. $\\#$Qubit search space for the
proposed BDGS, DFGS [16], and standard GS. Figure 5: Plot for $\\#$Iteration
vs. $\\#$Qubit search space for BDGS, DFGS [16], and standard GS.

We have conducted various trials on quantum simulation on a qubit space
ranging from $4$ to $20$ qubits on the Qiskit Aer
simulator∗∗∗https://qiskit.github.io/qiskit-
aer/stubs/qiskit_aer.AerSimulator.html with $1024$ shots with each execution
on $8$-cores systems with a maximum frequency of 3.5 GHz and $8$-GB RAM. In
our quantum simulation settings, we implemented the Oracle and Diffuser
searching for $k=2$ qubits as a part of a partial search in the forward and
backward direction for the proposed BDGS algorithm. The choice of $k=2$ has
functioned flawlessly in a database with an even distribution. An oracle
design for $k=2$ has been shown in Figure 3. In general, the database
configuration and the quantum resources will significantly impact the value of
$k$. We have also implemented a DFGS [16] algorithm based on a similar partial
search method in a depth-wise manner using the same quantum simulation
settings. We performed $5$ distinct trials in the experiments using the
proposed BDGS, DFGS, and standard GS algorithms [17]. The simulation results
demonstrate a significant improvement in runtime without compromising the
accuracy of the proposed BDGS search algorithm compared with DFGS and standard
GS algorithms, as shown in Table I. It is worth noting that the runtime of
standard GS grows exponentially with an increase in the search space, whereas
DFGS and BDGS grow linearly, as shown in Figure 4. In addition, we have also
visualized the number of iterations required with an increase in the number of
qubits, as shown in Figure 5. Our results indicate that DFGS and BDGS
significantly lower the required iterations, making it far more efficient for
larger search spaces. It may be noted that for $20$ qubits search space, the
standard GS takes $804$ iterations, whereas DFGS and the proposed BDGS require
only $10$ and $5$ iterations, respectively.

TABLE I: Comparative performance analysis of the proposed Bi-directional Grover’s Search (BDGS), standard Grover’s Search (GS) [17], and Depth-First Grover’s Search (DFGS) [16] with $1024$ shots |  |  GS |  DFGS |  BDGS
---|---|---|---|---
Qubits |  Trial |  Acc. |  Time(s) |  Acc. |  Time(s) |  Acc. |  Time(s)
|  1 |  $95.3$ |  $0.00267$ |  $100$ |  $0.00174$ |  $100$ |  $0.00117$
|  2 |  $96.6$ |  $0.00245$ |  $100$ |  $0.00197$ |  $100$ |  $0.00113$
4 |  3 |  $96.2$ |  $0.00222$ |  $100$ |  $0.00174$ |  $100$ |  $0.00108$
|  4 |  $96.7$ |  $0.00263$ |  $100$ |  $0.00251$ |  $100$ |  $0.00104$
|  5 |  $96.3$ |  $0.00300$ |  $100$ |  $0.00135$ |  $100$ |  $0.00104$
|  Avg. |  $96.02$ |  $0.00259$ |  $100$ |  $0.00186$ |  $100$ |  $0.00109$
|  1 |  $100$ |  $0.0148$ |  $100$ |  $0.00255$ |  $100$ |  $0.00147$
|  2 |  $100$ |  $0.0127$ |  $100$ |  $0.00301$ |  $100$ |  $0.00165$
8 |  3 |  $100$ |  $0.0131$ |  $100$ |  $0.00290$ |  $100$ |  $0.00170$
|  4 |  $100$ |  $0.0123$ |  $100$ |  $0.00344$ |  $100$ |  $0.00152$
|  5 |  $100$ |  $0.0133$ |  $100$ |  $0.00332$ |  $100$ |  $0.00163$
|  Avg. |  $100$ |  $0.0132$ |  $100$ |  $0.00304$ |  $100$ |  $0.00159$
|  1 |  $100$ |  $0.206$ |  $100$ |  $0.00676$ |  $100$ |  $0.00224$
|  2 |  $100$ |  $0.152$ |  $100$ |  $0.00737$ |  $100$ |  $0.00256$
16 |  3 |  $100$ |  $0.146$ |  $100$ |  $0.00617$ |  $100$ |  $0.00242$
|  4 |  $100$ |  $0.150$ |  $100$ |  $0.00623$ |  $100$ |  $0.00248$
|  5 |  $100$ |  $0.149$ |  $100$ |  $0.00589$ |  $100$ |  $0.00245$
|  Avg. |  $100$ |  $0.161$ |  $100$ |  $0.00645$ |  $100$ |  $0.00243$
|  1 |  $100$ |  $0.810$ |  $100$ |  $0.00708$ |  $100$ |  $0.00284$
|  2 |  $100$ |  $0.755$ |  $100$ |  $0.00705$ |  $100$ |  $0.00284$
20 |  3 |  $100$ |  $0.774$ |  $100$ |  $0.00799$ |  $100$ |  $0.00283$
|  4 |  $100$ |  $0.780$ |  $100$ |  $0.00833$ |  $100$ |  $0.00261$
|  5 |  $100$ |  $0.767$ |  $100$ |  $0.00786$ |  $100$ |  $0.00274$
|  Avg. |  $100$ |  $0.781$ |  $100$ |  $0.00766$ |  $100$ |  $0.00277$

##  V Discussion

In this study, we explore a class of structured bi-directional search problems
for which the satisfaction criterion
$\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$ can be decomposed to $\mathcal{F}$
and $\mathcal{R}$, the search-based satisfaction conditions. Using smaller
oracles, we introduce the faster quantum partial search method for a single
target item. The BDGS algorithm’s general concept is to parallelly increase
the amplitude of the items in each block that fulfill $\mathcal{F}$ and
$\mathcal{R}$.
The maximum number of Grover iterations
$2\sum_{\lambda=0}^{r/2k-1}\mathcal{I}_{G}^{\lambda}+\mathcal{I}_{L}$ for the
bi-directional quantum search with a smaller oracle we provided in this work
is $\frac{\pi}{4\sqrt{2}}\sqrt{\mathcal{N}}(1-\sqrt{\frac{1}{b^{r/2k}}})$. Our
simulation results show that the proposed BDGS algorithms yielded much shorter
run times than DFGS [16] and standard GS [17] while maintaining similar
measurement accuracy. This is primarily attributed to the efficient usage of
gates and Grover iterations in DFGS and BDGS.
Moreover, owing to the decomposition of the entire problem search space into
two halves (forward and backward passes), the proposed BDGS algorithm only
requires smaller oracles, which is the most significant advantage of the
quantum search with smaller oracles. The circuit depth of oracles will rise as
database size increases. Operating the quantum circuit error-free becomes
increasingly tricky as the circuit depth increases. Our BDGS technique will
mitigate this issue by employing smaller oracles. Smaller oracles are more
straightforward to build and aid in the error-free operation of the quantum
circuit.
However, the proposed BDGS algorithm’s supremacy suffers due to the structured
search problems subject to the requirements of satisfaction of the condition
$\mathcal{C}=\mathcal{F}\wedge\mathcal{R}$. Hence, the procedure is not a
universal search algorithm.

##  VI Conclusion

This article offers the first new attempt to enable the creation of Bi-
directional implementations of partial Grover’s quantum search method with a
reduction in computational complexity. Here, the proposed quantum circuit is
simulated for 2-qubit to 20-qubit circuits and enabled for scalable solutions
for any number of qubits. The proposed framework exhibits a potential solution
for quantum advantage in implementing our Bi-directional Grover’s Search
(BDGS) algorithm without compromising the probability of success in searching
a target. Our unique approach uses amplitude amplification to solve all
problems and achieves the same efficiency as the standard Grover search with a
lesser run time. Hence, our proposed BDGS offers an efficient usage of gates
allowing for significantly smaller run times. In forthcoming research, the
proposed Bi-directional Grover’s Search has the potential to extend to a
multi-solution search using a hybrid quantum-classical approach to enable
solutions for applications across various fields with better performance
waiting to be discovered.

## Acknowledgment

This work was partially supported by the Fulbright-Nehru Visiting Researcher
Grant $\\#2858FNPDR/2022$.

## Code availability

The Qiskit Python implementation of the proposed BDGS algorithm is available
on Github: https://github.com/hafeezzwiz21/DFGS-BDGS.

## References

  * [1] L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” _Physical review letters_ , vol. 79, no. 2, p. 325, 1997.
  * [2] C. Durr and P. Hoyer, “A quantum algorithm for finding the minimum,” _arXiv_ , 1999.
  * [3] G. Brassard, P. HØyer, and A. Tapp, “Quantum cryptanalysis of hash and claw-free functions,” _In proc. LATIN 1998: Theoretical Informatics, Springer, Berlin, Heidelberg_ , vol. 1380, pp. 163–169, 1998.
  * [4] ——, “Quantum counting,” _In proc. Automata, Languages and Programming: ICALP 1998, Springer, Berlin, Heidelberg_ , vol. 1443, pp. 159–164, 1998.
  * [5] N. J. Cerf, L. K. Grover, and C. P. Williams, “Nested quantum search and structured problems,” _Phys. Rev. A_ , vol. 61, p. 032303, 2000.
  * [6] N. Mahmud, B. Haase-Divine, A. MacGillivray, and E. El-Araby, “Quantum dimension reduction for pattern recognition in high-resolution spatio-spectral data,” _IEEE Transactions on Computers_ , vol. 71, no. 1, pp. 1–12, 2022.
  * [7] C. Zalka, “Grover’s quantum searching algorithm is optimal,” _Phys. Rev. A_ , vol. 60, no. 4, pp. 2746–2751, 1999.
  * [8] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and weaknesses of quantum computing,” _SIAM Journal on Computing_ , vol. 26, no. 5, pp. 1510–1523, 1997.
  * [9] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” _Fortschr. Phys._ , vol. 46, no. 4/5, pp. 493–505, 1998.
  * [10] V. Korepin and L. Grover, “Simple algorithm for partial quantum search,” _Quantum Inf Process_ , vol. 5, p. 5–10, 2006.
  * [11] M. Heiligman, “Finding matches between two databases on a quantum computer,” 2000.
  * [12] P. Niroula and Y. Nam, “A quantum algorithm for string matching,” _npj Quantum Inf_ , vol. 7, no. 37, 2021.
  * [13] P. Mateus and Y. Omar, “Quantum pattern matching,” 2005.
  * [14] A. Tulsi, “Optimal quantum searching to find a common element of two sets,” 2012.
  * [15] L. K. Grover and J. Radhakrishnan, “Is partial quantum search of a database any easier?” in _Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures_ , 2005, p. 186–194.
  * [16] H. Guo, “Depth-first grover search algorithm on hybrid quantum-classical computer,” 2022.
  * [17] L. K. Grover, “A fast quantum mechanical algorithm for database search,” _In Proc. 28th Annu. ACM Symp. Theory Comput._ , pp. 212–219, 1996.
  * [18] C. P. Williams, “Explorations in quantum computing,” _Texts in Computer Science, Springer_ , 2011.
  * [19] I. Chuang and M. Nielsen, _Quantum computation and quantum information_ , 2001, vol. 54.
  * [20] V. Korepin and J. Liao, “Quest for fast partial search algorithm,” _Quantum Inf Process_ , vol. 5, p. 209–226, 2006.
  * [21] R. E. Korf, “Search techniques,” in _Encyclopedia of Information Systems_ , 2003, pp. 31–43.


# The Best of Both Worlds: Combining Model-based and Nonparametric Approaches
for 3D Human Body Estimation

Zhe Wang
University of California, Irvine
<EMAIL_ADDRESS>Jimei Yang
Adobe Research
<EMAIL_ADDRESS>Charless Fowlkes
University of California, Irvine
<EMAIL_ADDRESS>
###### Abstract

Nonparametric based methods have recently shown promising results in
reconstructing human bodies from monocular images while model-based methods
can help correct these estimates and improve prediction. However, estimating
model parameters from global image features may lead to noticeable
misalignment between the estimated meshes and image evidence. To address this
issue and leverage the best of both worlds, we propose a framework of three
consecutive modules. A dense map prediction module explicitly establishes the
dense UV correspondence between the image evidence and each part of the body
model. The inverse kinematics module refines the key point prediction and
generates a posed template mesh. Finally, a UV inpainting module relies on the
corresponding feature, prediction and the posed template, and completes the
predictions of occluded body shape. Our framework leverages the best of non-
parametric and model-based methods and is also robust to partial occlusion.
Experiments demonstrate that our framework outperforms existing 3D human
estimation methods on multiple public benchmarks.

Figure 1: From left to right: Original image our mesh prediction overlay and
alternative views mesh visualization. Images are from 3DOH [52], and LSP [10]
datasets. (Best viewed in Color)

##  1 Introduction

The 3d estimation of the human body pose and shape from a monocular image is a
fundamental task for various applications such as VR/AR, virtual try-on,
metaverse and animations. It is challenging mostly due to the depth ambiguity
and lack of evidence from single image. There are several ways to solve this
ambiguity such as leveraging multi-view or video data to fuse image evidence
from more images and infer occluded parts. For the case of single images,
researchers used parametric models such as SMPL [23] to fit 2D image evidence
[15] or use human pose prior [12, 32, 13] to penalize problematic human pose /
mesh prediction in combination with modern deep learning techniques. However,
these model-based methods are prone to produce corrupted results when severe
occlusion happens.

Nonparametric methods use non-compressed representations like voxels [33],
heatmaps [30] and joint location [37, 19, 21] as the target for modern deep
learning. However, to estimate dense meshes they are computationaly expensive
and consume lots of memory. They either use integral methods to estimate
normalized joint location [30] or simplify meshes [21] to reduce the number of
vertices. Without post-processing, these methods also generate qualitatively
non-pleasing results. The dense correspondence methods [47, 46, 48], which are
based on template SMPL human mesh surface and have been proven for various
tasks.

Connecting nonparametric methods and model-based methods is hard due to the
difficulty in localizing the corresponding feature. [6, 51, 30] utilize
bounding boxes or keypoints location to find the related features to estimate
necessary SMPL parameters. While [14, 19] learn the feature-parameter
correspondence (attention) implicitly through neural networks. [46, 49]
consider the correspondence between the mesh representation and pixel
representation based on human surface mapping (UV coordinate system). However,
they estimate the SMPL parameter through a light weight FC network and treat
this simple optimization process as a post process. Their methods also do not
convey the advantages of nonparametric methods such as robustness to
occlusion.

To leverage the advantages from both worlds, we propose a 3d human body
estimation framework that consists of three modules: Dense Map Prediction
module (DMP), Inverse Kinematics module (IK) and UV Inpainting module (UVI).
DMP explicitly predicts per-pixel human 3d joint location, 3d surface location
in root relative coordinates, 3d displacement between the joint location and
surface location, and also predicts UV coordinates which represent the human
surface in a 2D grid. This module is robust to partial occlusion when
predicting joint, as all the image evidence belongs to this part will
contribute to the prediction explicitly. IK module connects the nonparametric
prediction to model-based method. We first warp the DMP dense prediction to UV
space and get the joint prediction based on the part-segmentation in UV space.
Then we use a two-stage multi-layer perceptron, where the first stage inpaints
and refines the joint prediction, while the second stage estimates SMPL
parameters and eventually produces a posed mesh. With all the predictions in
UV space from DMP and IK, UVI inpaints and refines the 3d body pose and mesh
in UV space.

In summary, our contributions are three fold:
$\bullet$ We propose a 3d body estimation framework from single image that
seamlessly leverages the best of the both worlds (model-based and
nonparametric).
$\bullet$ The method is robust to occlusions and can self-correct wrong poses
from Dense Map Prediction module.
$\bullet$ We achieve state-of-the-art performance on H36M and 3DOH datasets.

##  2 Related Work

#### 3D human shape estimation from monocular images

SMPL [23] has been widely used for 3D human mesh reconstruction. To boost its
power in practice, a number of deep learning frameworks have been proposed by
using SMPL as regression targets [12, 15, 32, 46, 30, 24]. [12] regresses SMPL
parameters directly from input images by end-to-end training. Following this
research direction, [30] add spherical Gaussian attention joint based on
initial joint estimation, and the use the the attended feature to learn the
vertices location. [15] combine learning and optimization[32] in the same
framework but cannot handle occlusions. [46] uses the template UV mapping from
SMPL and transforms 3d mesh reconstruction to decomposed UV estimation and
position map inpainting problems. However, the way to get 3d human joint from
SMPL mesh is based on the pre-trained joint regressor, which will induce
intrinsic errors and usually does not generalize to other datasets.

#### 3D human pose estimation from monocular images

Deep learning approaches have shown success in regressing 3D pose from a
single image [29, 36, 44, 27, 53, 33, 41, 25, 42, 50]. Basically, most current
models can be categorized into two frameworks. The first is to directly
estimate 3D pose from images, based on volumetric representation [33, 29]. But
these approaches may involve in high memory consumption and complex post-
processing steps. Based on the explosive improvement in 2D pose estimation
[44], another framework is to estimate 2D pose from images and then lift 2D
pose to 3D pose [53, 27]. Since these approaches take 2D joint locations as
input, 3D human pose estimation simply focuses on learning depth of each
joint. This releases learning difficulty and leads to better 3D pose. However,
there are few methods on systematically handling occlusion in the first
framework while the second framework cannot recover information if the joint
detector fails. Additionally, how to get human surfaces from the joint
prediction remains a problem.

#### Inverse Kinematics

The inverse kinematics (IK) problem has been extensively studied in robotics
[1, 43] and graphics [4] and its techniques have been used in 3d human pose
estimation [40, 17, 14, 54, 55]. Numerical solutions [1, 4, 43] rely on time-
consuming iterative optimization. [40] uses temporal sequence to resolve IK
ambiguity. [17] decomposes the IK rotation to the product of swing rotation
and twist rotation and solve swing rotation analytically from predicted joint
locations. Feed forward solution like [55, 54] propose BodyIKNet to regress
SMPL [23] pose and shape parameters from 3d joint location, However, it leads
to a sub-optimal solution when partial occlusion happens.

Figure 2: Our 3d body estimation framework consists of three part: Dense Map
Prediction module (DMP), Inverse Kinematics and SMPL module (IK) and UV
Inpainting Module (UVI).

#### Occlusion

[38] presented a systematic study of various types of synthetic occlusions in
3D human pose estimation from a single RGB image. Since synthetic data can not
fully depict the real occlusion, [5] learns from real data and uses grammar
models with explicit occluding templates to reason about occluded people. To
avoid specific design for occlusion patterns, [3] presents a method for
modeling occlusion that aims at explicitly learning the appearance and
statistics of occlusion patterns. They also synthesizes a large corpus of
training data by compositing segmented objects at random locations over a base
training image. [2] utilizes a cylinder model and confidence maps to filter
out the occluded joints and uses flow warped joint in the same video to
approximate the missing joints. [34] integrates depth information about
occluded objects into 3D pose estimation. To provide full-geometry information
to handle occlusion scenarios, [41] and [7] provide 3d scene geometry as
multi-layer depth maps or signed distance fields into the inference stage.
[35] proposes a simple but effeive self-training framework to adapt the model
to highly occluded observations. To fully utilize the holistic human body
model (e.g. SMPL [23]), [52] represents the target SMPL human mesh as UV
location map and converts the full-body human estimation as an image
inpainting problem. However, these frameworks either rely on nonparametric
estimation or pure model-based regression, how to leverage the best of both
worlds seamlessly remain an unexplored problem.

##  3 Method

As shown in Fig 2, our framework consists of three consecutive modules,
including a dense map prediction module (DMP), which extract dense semantic
maps (e.g. 3d joint location, surface location and their displacements) and
correspondence UV position, an inverse kinematics and SMPL module (IK), which
inpaint 3d joint location and estimate the smpl parameters, as well as a UV
map inpainting module, which estimate the final joint location and mesh
location in UV space.

###  3.1 Dense Map Prediction Module

Our dense map prediction module is an encoder-decoder architecture and is used
to extract the IUV images $M_{i}$, as well as dense semantic maps including
dense joint map $M_{j}$, dense location map $M_{l}$ and dense displacement
maps $M_{d}$. They are further illustrated in Fig 3. $M_{i}$ is generated from
the continuous UV map from [46], it is continuous in both image space and UV
space, thus, easier to learn compared with original UV map [23]. It is used to
convert the dense local features as well as these semantic maps to UV space.
For location map $M_{l}$, it represents the position of each vertices from the
SMPL human mesh surface in root-relative coordinates. To construct $M_{l}$
groundtruth, we first use the SMPL model, SMPL parameters and camera
parameters to generate the vertices location in root-relative coordinate, and
generate the full UV space location map $UV_{l}$ using barycentric
interpolation (The mesh faces correspondence is defined by [46]). After that
we use the $M_{i}$ to fetch values from $UV_{l}$ to get the dense location map
in image space. For the generation of dense joint map $M_{j}$, we first rely
on T-pose SMPL mesh and assign each vertex to the nearest joints (14 LSP
joints setting), after that we use barycentric interpolation to get the UV
space assignment, and further refine the assignment by make it symmetric in UV
space (e.g. left hip and right hip has symmetric shape in UV space, as
illustrated in Fig 4). We term the part assignment in UV space as $A_{uv}$ .
After setting the assignment in UV space, we use the $M_{i}$ to query values
from $UV_{j}$ to get the dense joint map in image space. $UV_{j}$ stores the
root-relative joint location. We define displacement as the residual between
vertex location and the assigned joint location, thus $UV_{d}=UV_{l}-UV_{j}$
and $M_{d}=M_{l}-M_{j}$. As our human are left-right symmetric (e.g. left hand
has symmetric shape with right hand and the size and the distance between
joint and surface is almost the same.), the magnitude of left part and right
part of $UV_{d}$ should be the same.

These semantic maps are aligned with the human in the images. Thus we are able
to train a encoder-decoder network to estimate directly from image space.
Dense image space joint prediction shares the similar flavor with [45, 31].

The objective for the dense map prediction module is

${\ell_{DMP}}={\ell_{M_{i}}}+{\ell_{M_{l}}}+{\ell_{M_{j}}}+{\ell_{M_{d}}}$ (1)

$\ell_{M_{i}}$ is composed of two parts: a binary mask loss $\ell_{M_{i}b}$ of
human body, which distinguishes pixels from those at the background, and the
human pixels. The loss function of $\ell_{M_{i}b}$ is binary cross entropy
loss. our CNN further outputs the UV coordinates and uses L1 loss
$\ell_{M_{iuv}}$ .

${\ell_{M_{i}}}={\ell_{M_{ib}}}+{\ell_{M_{iuv}}}$ (2)

For $\ell_{M_{l}}$, $\ell_{M_{j}}$ and $\ell_{M_{d}}$, we use L1 loss to
directly regress the real value. As these values are already in root-relative
coordinate and in unit meters, thus their data range is $-1$ to $+1$, we do
not further normalize them.

Our dense map prediction module not only predicts these semantic maps, but
also extracts both global feature to estimate camera parameter and local
feature for the UV impainting module.

Figure 3: Semantic maps aligned with image space. From left to right: IUV
image $M_{i}$, Dense jointmap $M_{j}$, dense location map $M_{l}$ and dense
displacement map $M_{d}$. (Best viewed in Color)

Figure 4: Warped Images in UV space based on IUV images $M_{i}$. From left to
right: Part segmentation in UV space $A_{uv}$, UV space jointmap $UV_{j}$, UV
space location map $UV_{l}$ and UV space displacement map $UV_{d}$. (Best
viewed in Color)

Figure 5: Full groundtruth in UV space. From left to right: UV space jointmap
$UV_{j}$, UV space location map $UV_{l}$ and UV space displacement map
$UV_{d}$. (Best viewed in Color)

###  3.2 Inverse Kinematics Module

#### Estimate Joint Location from DMP

After warping the semantic maps ($M_{l},M_{j},M_{d}$) from image space to uv
space, we get the incomplete uv joint map $UV_{j}$. Based on the uv space
joint assignment $A_{uv}$ (as shown in Fig 4), we aggregate the dense
prediction $UV_{j}$ for each joint and average them if they are not fully
occluded. Thus we have a coarse prediction for each joint $J_{initial}$.

#### Joint Inpaint and Refine Module

Even though each human pixel contributes to joint prediction, there are still
cases that some joints have no assigned vertex/pixel available from the image
evidence. Thus we propose the joint inpainting module to inpaint these missing
joints. This network is pretty flexible and can be MLP [27], GCN [53] or even
modern transformers [20]. For the ease of implementation we use simple multi-
layer perceptron. Our joint inpainting net is inspired by [27], which is
simple, deep and a fully-connected network with six linear layer with 256
output features. It includes dropout after every fully connected layer, batch-
normalization and residual connections. The model contains approximately 400k
training parameters. The goal of this network is not only to inpaint the
joints but also to refine the joints prediction that is not occluded. It takes
the $J_{initial}$ as input and the output of the network is the joint in root-
relative coordinates $J_{refine}$. We use L1 loss $L_{ji}$ to train joint
inpaint and refine module. The structure of the joint inpainting and refine
module is shown in Fig 6.

#### Inverse Kinematics Module

After getting the sparse 3d human keypoints. We want to repose the template
SMPL meshes based on the predicted joints location. To solve this problem we
leverage inverse kinematics (IK). Typically, the IK task is tackled with
iterative optimization methods [1, 4, 43], which requires a good
initialization, more time and case-by-case optimization method. Here we
propose a global inverse kinematics neural network GIK-Net. This network is
constructed by the basic fully connected neural network module with residual
connection, batch normalization and relu activation similar to [27]. In
particular, GIK-Net takes the refined keypoint coordinates $J_{refine}$ in
root-relative space and outputs joint rotations $\theta$ and $\beta$ which
serve as the input for SMPL layer. As we also use the Mocap dataset (AMASS
[26], SPIN[15] and AIST++ [18]), our GIK-Net can implicitly learn the
realistic distribution of human kinematics rotation and human shape. The use
of the additional Mocap dataset serves the same purpose as the factorized
adversarial prior [12], variational human pose prior [32] and motion
discriminator [13]. We use L1 loss $L_{\theta}$ and $L_{\beta}$ to train GIK-
Net. The structure of GIK-Net is shown in Fig 6.

#### SMPL revisits and Reposing Module

SMPL [23] represents the body pose and shape by pose $\theta\in R^{72}$ and
shape $\beta\in R^{10}$ parameter. Here we use the gender-neural shape model
following previous work [14, 12, 15]. Given these parameters, the SMPL module
is a differentiable function that outputs a posed 3D mesh $M(\theta,\beta)\in
R^{6890\times 3}$. The 3D joint locations $J_{3D}=WM\in R^{J\times 3}$, while
J are computed with a pretrained linear regressor $W$. After getting the
$\theta$ and $\beta$ from the GIK-Net we send them to SMPL layer to get the
body mesh prediction.

We also augment the joints input for GIK-Net from Mocap dataset with guassian
noise and random synthetic occlusion (30%). The augmentation helps our GIK-Net
generalize to more realistic noisy input. We use L1 loss $L_{vi}$ to train the
mesh prediction from SMPL module.

Figure 6: Structure of GIKNet. (Best viewed in Color)

The objective for the inverse kinematics and smpl module is

${\ell_{IK}}={\ell_{\theta}}+{\ell_{\beta}}+{\ell_{ji}}+{\ell_{vi}}$ (3)

###  3.3 UV Inpainting Module

The goal of UV inpainting module is to regress 3d joint and mesh location
directly based on the feature / semantic output ($UV_{l},UV_{j},UV_{d}$) from
DMP and semantic output ($UV_{l},UV_{j},UV_{d}$) from IK.

#### Inevitable Fitting Error introduced by SMPL model and Joint regressor

The advantage of directly regressing joint/mesh location over model-based
method is that model-based method will introduce intrinsic fitting error.
Specifically, we use the SMPL layer, groundtruth SMPL parameters (from Mosh),
and the joint-regressor [15] to obtain fitted joint for the whole Human3.6M
dataset. We get average fitting error as 24.1 mm (MPJPE) when compared with
the Human3.6M joint from Mocap system. It means that even we predict perfect
SMPL mesh we still have about 24.1 mm fitting error. Thus we argue directly
train and estimate joint location from UV space is a better alternative
solution.

#### UV inpainting module

After getting the refined joint location $J_{refine}$ from IK module, we
distribute the refined joint location in UV space based on UV space joint
assignment map $A_{uv}$ and generate refine UV joint map $UV_{jrefine}$. We
also have the reposed template mesh and the corresponding reposed UV location
map $UV_{l}$ (through barycentric interpolation). Additionally, we have
features $UV_{f}$, location map $UV_{l}$, joint map $UV_{j}$ and displacement
$UV_{d}$ from DMP. We combine the best of both worlds ( DMP and IK) feature
through aggregation and send it to our UV inpainting module. The UV inpainting
module is a light UNet with skip connections. We can see the Fig 5 is the
complete version of Fig 4 and serves as the groundtruth for the UV inpainting
module.

For the training of the UV inpainting module, we have

${\ell_{map}}=\|{\hat{UV}_{map}}-UV_{map}\|_{1}$ (4)

Note the ‘map’ represents location map, joint map and displacement map in uv
space. Addtionally, we have 3d joints and 2d joint loss based on the predicted
camera parameter. Our camera parameters consist of scale and offset parameter
to map the xy in $J_{3d}$ to $J_{2d}$.

${\ell_{j3d}}=\|{\hat{J}_{3d}}-J_{3d}\|_{1}$ (5)
${\ell_{j2d}}=\|{\hat{J}_{2d}}-J_{2d}\|_{1}$ (6)

As we know, the distance between the human surface to the joints are left-
right symmetric, thus we also apply symmetric loss on the magnitude of
displacement.

${\ell_{dismag}}=\|\|{\hat{UV}_{d}}\|-\|{\hat{UV}^{flip}_{d}}\|\|_{1}$ (7)

To align the predicted mesh surface with image aligned IUV images $M_{i}$, we
also adopt consistent loss from [46]. It is enabled by the camera parameter
predicted by our model (scaling and offset parameter).

The objective for the uv inpainting module is

${\ell_{UVI}}={\ell_{dismag}}+{\ell_{j2d}}+{\ell_{j3d}}+{\ell_{map}}+{\ell_{con}}$
(8)

Thus we have all the losses as

${\ell_{all}}={\ell_{DMP}}+{\ell_{IK}}+{\ell_{UVI}}$ (9)

#### Inference

We do inference of 3d joint location from $UV_{j}$ and based on the uv
assignment $A_{uv}$ for each joint. We average all the prediction for the
specific joints if this pixel prediction is valid. For human mesh prediction
we use the barycentric interpolation from the UV space location map $UV_{l}$.

###  3.4 Implementation Details

The proposed framework is trained on the ResNet-50 [8] backbone pre-trained on
ImageNet. It takes a 224 $\times$ 224 image as input, and input resolution for
UVI is 64 $\times$ 64 and the output resolution is 128 $\times$ 128\. We train
three modules separately. We first train our DMP, and based on the output of
DMP and Mocap data we train our IK; We finally fix and concat DMP and IK, and
train UVI module. We apply synthetic occlusion [39] when train DMP. The
training data is augmented with randomly scaling, rotation, flipping and RGB
channel noise. We use the Adam optimizer. The training data for each module is
illustrated in Table 1.

##  4 Experiments

###  4.1 Dataset and Evaluation Metric

Stages | Training Datasets
---|---
DMP | H36M, MPI-INF-3DHP, MPII, COCO, LSP
IK | H36M, MPI-INF-3DHP, AMASS, AIST++
UVI | H36M, 3DOH
Table 1: Training datasets for each module.

#### Human3.6M

[9] is commonly used as the benchmark dataset for 3D human pose estimation,
consisting of 3.6 millions of video frames captured in the controlled
environment. It has 11 subjects, 15 kinds of action sequences and 1.5 million
training images with accurate 3D annotations. Similar to [12], we use MoSH to
process the marker data in the original dataset, and obtain the ground truth
SMPL parameters to generate the groundtruth for $UV_{l}$. For a fair
comparison, we use 300K data in S1, S5, S6, S7, S8 for network training, and
test in S9, S11.
3DOH [52] utilize multi-view SMPLify-X [32] to get the 3d ground truth. The
dataset is designed to have object occlusion for subjects. It contains 50,310
training images and 1,290 test images. It provides 2D, 3D annotations and SMPL
parameters to generate meshes. We use the test set for evaluation purposes and
the training set to train the UVI module.
LSP [10] dataset is a 2D human pose estimation benchmark. In our work, we use
the [16] SMPL parameter to render the $M_{i}$ to train DMP module.
MPI-INF-3DHP [28] is a dataset captured with a multi-view setup mostly in
indoor environments. No markers are used for the capture, so 3D pose data tend
to be less accurate compared to other datasets. We use the provided training
set (subjects S1 to S8) for training. We use the it to train DMP and IK
module.
Mocap dataset We use [26] AMASS, AIST++ [18] and SPIN [15] dataset to train
our occlusion aware GIKNet.
Evaluation We evaluate our method on H36M [9] dataset and 3DOH [52] datasets.
We report Procrustes-aligned mean per joint position error (MPJPE-PA) and mean
per joint position error (MPJPE) in mm. For 3DOH we also report mean per
vertex error (MPVE) in mm.

Figure 7: Different part segmentation choice in UV space. (Best viewed in Color)  | H36M
---|---
Method | MPJPE | MPJPE-PA
HMR [12] | 88.0 | 56.8
DaNet [48] | 61.5 | 48.6
HoloPose [6] | 60.3 | 46.5
SPIN [15] | 62.5 | 41.1
I2L [30] | 55.7 | 41.1
DetNet [54] | 64.8 | 50.3
PHMR [17] | - | 41.2
DecoMR [46] | 60.5 | 39.3
PyMaf [49] | 57.7 | 40.5
Ours DMP-14 | 69.7 | 51.7
Ours IK-14 | 67.3 | 50.6
Ours UVI-14 | 54.7 | 38.4
Table 2: Reconstruction errors on Human3.6M dataset. | 3DOH
---|---
Method | MPJPE | MPJPE-PA | MPVE
SMPLify-X | - | 156.4 | 177.3
OOH [47] | - | 58.5 | 63.3
SPIN [15] | 104.3 | 68.3 | 113.4
PyMAF[49] | 96.2 | - | 107.3
HMR-EFT⋆ [11] | 75.2 | 53.1 | -
PARE⋆ [14] | 63.3 | 44.3 | -
Ours DMP-14 | 128.4 | 109.8 | -
Ours IK-14 | 112.9 | 80.8 | 133.5
Ours UVI-14 | 58.3 | 44.6 | 72.3
Table 3: Comparison with SOTA performance on 3DOH dataset. $\star$ denotes the
model trained on better ground truth data from EFT [11].  Figure 8: Pose and
shape prediction from DMP module, IK module and UVI module. (Best viewed in
Color)

###  4.2 Quantitative Results

#### Comparison with SOTA performance

We can see our final stage (UVI-14) in Table 2 achieve state-of-the-art
performance on common H36M benchmark. Our SOTA performance demonstrates the
usefulness of proposed combination of model-based and nonparametric
approaches. In Table 3, as our methods focus on both pose and mesh while [47]
focus more on meshes, they achieve SOTA performance on 3DOH dataset; PARE [14]
uses the EFT dataset [11] with improved groundtruth thus outperforms us on
MPJPE-PA metric.

#### 14 joints vs 24 joints setting

Another way to get 24 joints prediction from DMP is to have a 24 joints
segmentation $A_{uv}$ in UV space following SMPL setting. As shown in Fig 7 we
define 14 joints setting and 24 joints setting. We run DMP-24 and DMP-14 and
evaluate on the predicted $J_{initial}$. We observe the error of DMP-24 is
much higher than DMP-14 as in Table 4. The main reason is that over-segment of
body parts may distribute less visible pixels to certain parts (feet, hand)
and will lead to higher error.

#### Occlusion vs Non-occlusion

When computing the MPJPE for $J_{initial}$, the results for visible parts
(part with any pixel belong to them visible) and invisible parts differ a lot.
We compare the DMP-14 and DMP-14-Nonoccluded in Table 4. We find visible parts
with 87.3 mm MPJPE while the MPJPE counting invisible parts yield 128.4 mm. It
tells us if the joints are visible, our DMP can predict relative good initial
results. Thus, synthetic occlusion helps for our DMP module. When we remove
the data augmentation techniques like synthetic occlusion [39], DMP-14
increase to 135.4 mm.

| 3DOH
---|---
Method | MPVE | MPJPE | PMPJPE
DMP-24 | - | 246.4 | 208.5
DMP-14 w/o synthetic occlusion | - | 135.4 | 115.7
DMP-14-Nonoccluded | - | 87.3 | 64.7
DMP-14 | - | 128.4 | 109.8
IK-14 w/o gaussian noise | 138.2 | 115.7 | 82.8
IK-14 w/o random zero | 139.5 | 116.8 | 83.2
IK-14 | 133.5 | 112.9 | 80.8
UVI-14 w/o IK-14 | 82.9 | 69.4 | 58.1
UVI-14 w/o DMP-14 | 80.1 | 67.8 | 55.1
UVI-14 w/o $\ell_{dismag}$ | 75.5 | 63.8 | 47.3
UVI-14 | 72.3 | 58.3 | 44.6
Table 4: Ablation study about reconstruction errors on 3DOH test set. 14 and
24 denotes the number of joints setting for training and evaluations.
Nonoccluded denotes when we calculate error we are not counting the part
without any visible image evidence.

####  GIK-Net data augmentations

We also try to remove the gaussian noise or random mask out joints data
augmentation techniques for MOCAP data, which serve as input for the GIK-Net,
to see how is the MPJPE varying. As shown in Table 4, IK-14 w/o gaussian noise
and IK-14-w/o random zero yield larger error (2.8 mm and 3.9 mm ) compared
with IK-14. It demonstrate these data augmentation makes the GIK-Net more
robust to noise and helps generalize to real data input.

####  UVI ablations

As the magnitude of our $UV_{d}$ should be symmetric, we introduce the
magnitude error for $UV_{d}$ and its flip version. We run a model without this
$\ell_{dismag}$ and observe there is 4.5 mm error increase in MPJPE metric.
This is shown in Table 4.

#### Each stage performance

DMP module is a nonparametric method, while IK module is a model-based method
relying on the output of DMP and then correct it. UVI module relies on both
nonparametric output and model-based output, and predict the final body joint
and mesh. Based on Table 4, DMP-14 estimate from raw images and gives inferior
performance. IK-14 corrects the output from DMP-14 and reduce the error by
15.5 mm. UVI-14 relies on both IK-14 and DMP-14 and further reduce MPJPE to
58.3 mm. However, if any of the previous stage output is missing, MPJPE
increase by 11.1 mm (w/o IK-14) or 8.5 mm (w/o DMP-14).

###  4.3 Qualitative Results

We present qualitative results in Fig 8 including the joints prediction from
DMP, IK, UVI modules and mesh prediction from IK, UVI modules.

#### Limitations

We also show failure cases in Fig 9. Typical failure cases can be attributed
to challenging poses (a,b,d), and crowded scenarios (c).

Figure 9: Failure cases. (Best viewed in color)

##  5 Conclusion

We propose a framework that combine the best of both worlds (nonparametric and
SMPL model-based method). It predicts the initial 3d body pose from DMP
module, refine the predicted pose and repose the template SMPL meshes using IK
module. Based on the nonparametric prediction from DMP module and model-based
prediction from IK module, the UVI module inpaint and refine the prediction.
To alleviate the intrinsic error introduced by joint regressor (fitting), we
regress joint ($UV_{j}$) and mesh ($UV_{l}$) separately in different maps in
UV space. We also introduce the magnitude loss $\ell_{dismag}$ to enforce the
symmetric property of human ($UV_{d}$). Our framework achieves state-of-the-
art performance among 3D mesh-based methods on several public benchmarks.
Future work can focus on extending the framework to the reconstruction of full
body surfaces including hands and faces.

## References

  * [1] A Balestrino, Giuseppe De Maria, and L Sciavicco.  Robust control of robotic manipulators.  In IFAC Proceedings Volumes, 1984.
  * [2] Yu Cheng, Bo Yang, Bo Wang, Wending Yan, and Robby T. Tan.  Occlusion-aware networks for 3d human pose estimation in video.  In ICCV, 2019.
  * [3] Golnaz Ghiasi, Yi Yang, Deva Ramanan, and Charless C. Fowlkes.  Parsing occluded people.  In CVPR, 2014.
  * [4] Michael Girard and Anthony A Maciejewski.  Computational modeling for the computer animation of legged figures.  In SIGGRAPH, 1985.
  * [5] Ross B. Girshick, Pedro F. Felzenszwalb, and David McAllester.  Object detection with grammar models.  In Neurips, 2020.
  * [6] Riza Alp Guler and Iasonas Kokkinos.  Holopose: Holistic 3d human reconstruction in-the-wild.  In CVPR, 2019.
  * [7] Mohamed Hassan, Vasileios Choutas, Dimitrios Tzionas, and Michael J. Black.  Resolving 3d human pose ambiguities with 3d scene constraints.  In ICCV, 2019.
  * [8] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [9] Catalin Ionescu, Dragos Papava, Vlad Olaru, and Cristian Sminchisescu.  Human3.6m: Large scale datasets and predictive methods for 3d human sensing in natural environments.  In PAMI, 2014.
  * [10] Sam Johnson and Mark Everingham.  Clustered pose and nonlinear appearance models for human pose estimation.  In BMVC, 2010.
  * [11] Hanbyul Joo, Natalia Neverova, and Andrea Vedaldi.  Exemplar fine-tuning for 3d human pose fitting towards in-thewild 3d human pose estimation.  In Arxiv, 2020.
  * [12] Angjoo Kanazawa, Michael J. Black, David W. Jacobs, and Jitendra Malik.  End-to-end recovery of human shape and pose.  In CVPR, 2018.
  * [13] Muhammed Kocabas, Nikos Athanasiou, and Michael J. Black.  Vibe: Video inference for human body pose and shape estimation.  In CVPR, 2020.
  * [14] Muhammed Kocabas, Chun-Hao P. Huang, Otmar Hilliges, and Michael J. Black.  Pare: Part attention regressor for 3d human body estimation.  In ICCV, 2021.
  * [15] Nikos Kolotouros, Georgios Pavlakos, Michael J Black, and Kostas Daniilidis.  Learning to reconstruct 3d human pose and shape via model-fitting in the loop.  In ICCV, 2019.
  * [16] Christoph Lassner, Javier Romero, Martin Kiefel, Federica Bogo, Michael J. Black, and Peter V. Gehler.  Unite the people – closing the loop between 3d and 2d human representations.  In CVPR, 2017.
  * [17] Jiefeng Li, Chao Xu, Zhicun Chen, Siyuan Bian, Lixin Yang, and Cewu Lu.  Hybrik: A hybrid analytical-neural inverse kinematics solution for 3d human pose and shape estimation.  In CVPR, 2021.
  * [18] Ruilong Li, Shan Yang, David A. Ross, and Angjoo Kanazawa.  Ai choreographer: Music conditioned 3d dance generation with aist++.  In ICCV, 2021.
  * [19] Kevin Lin, Lijuan Wang, and Zicheng Liu.  End-to-end human pose and mesh reconstruction with transformers.  In CVPR, 2021.
  * [20] Kevin Lin, Lijuan Wang, and Zicheng Liu.  End-to-end human pose and mesh reconstruction with transformers.  In CVPR, 2021.
  * [21] Kevin Lin, Lijuan Wang, and Zicheng Liu.  Mesh graphormer.  In ICCV, 2021.
  * [22] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [23] Matthew Loper, Naureen Mahmood, Javier Romero, Gerard Pons-Moll, and Michael J. Black.  Smpl: A skinned multi-person linear model.  In siggraph, 2015.
  * [24] Tianyu Luan, Yali Wang, Junhao Zhang, Zhe Wang, Zhipeng Zhou, and Yu Qiao.  Pc-hmr: Pose calibration for 3d human mesh recovery from 2d images/videos.  In AAAI, 2021.
  * [25] Haoyu Ma, Liangjian Chen, Deying Kong, Zhe Wang, Xingwei Liu, Hao Tang, Xiangyi Yan, Yusheng Xie, Shih-Yao Lin, and Xiaohui Xie.  Transfusion: Cross-view fusion with transformer for 3d human pose estimation.  In BMVC, 2021.
  * [26] Naureen Mahmood, Nima Ghorbani, Nikolaus F. Troje, Gerard Pons-Moll, and Michael J. Black.  AMASS: Archive of motion capture as surface shapes.  In ICCV, 2019.
  * [27] Julieta Martinez, Rayat Hossain, Javier Romero, and James J. Little.  A simple yet effective baseline for 3d human pose estimation.  In ICCV, 2017.
  * [28] Dushyant Mehta, Helge Rhodin, Dan Casas, Pascal Fua, Oleksandr Sotnychenko, Weipeng Xu, and Christian Theobalt.  Monocular 3d human pose estimation in the wild using improved cnn supervision.  In 3DV, 2017.
  * [29] Gyeongsik Moon, Juyong Chang, and Kyoung Mu Lee.  Camera distance-aware top-down approach for 3d multi-person pose estimation from a single rgb image.  In ICCV, 2019.
  * [30] Gyeongsik Moon and Kyoung Mu Lee.  I2l-meshnet: Image-to-lixel prediction network for accurate 3d human pose and mesh estimation from a single rgb image.  In ECCV, 2020.
  * [31] George Papandreou, Tyler Zhu, Liang-Chieh Chen, Spyros Gidaris, Jonathan Tompson, and Kevin Murphy.  Personlab: Person pose estimation and instance segmentation with a bottom-up, part-based, geometric embedding model.  In ECCV, 2018.
  * [32] Georgios Pavlakos, Vasileios Choutas, Nima Ghorbani, Timo Bolkart, Ahmed A. A. Osman, Dimitrios Tzionas, and Michael J. Black.  Expressive body capture: 3d hands, face, and body from a single image.  In CVPR, 2019.
  * [33] Georgios Pavlakos, Xiaowei Zhou, Konstantinos G Derpanis, and Kostas Daniilidis.  Coarse-to-fine volumetric prediction for single-image 3D human pose.  In CVPR, 2017.
  * [34] Umer Raf, Juergen Gall, and Bastian Leibe.  A semantic occlusion model for human pose estimation from a single depth image.  In CVPRW, 2015.
  * [35] Chris Rockwell and David Fouhey.  Full-body awareness from partial observations.  In ECCV, 2020.
  * [36] Gregory Rogez, Philippe Weinzaepfel, and Cordelia Schmid.  Lcr-net++: Multi-person 2d and 3d pose detection in natural images.  In PAMI, 2019.
  * [37] Xiao Sun, Bin Xiao, Fangyin Wei, Shuang Liang, and Yichen Wei.  Integral human pose regression.  In ECCV, 2018.
  * [38] István Sárándi, Timm Linder, Kai O. Arras, and Bastian Leibe.  How robust is 3d human pose estimation to occlusion?  In Arxiv, 2018.
  * [39] István Sárándi, Timm Linder, Kai O. Arras, and Bastian Leibe.  Synthetic occlusion augmentation with volumetric heatmaps for the 2018 eccv posetrack challenge on 3d human pose estimation.  In Arxiv, 2018.
  * [40] Ruben Villegas, Jimei Yang, Duygu Ceylan, and Honglak Lee.  Neural kinematic networks for unsupervised motion retargetting.  In CVPR, 2018.
  * [41] Zhe Wang, Liyan Chen, Shaurya Rathore, Daeyun Shin, and Charless Fowlkes.  Geometric pose affordance: 3d human pose with scene constraints.  In arxiv, 2019.
  * [42] Zhe Wang, Daeyun Shin, and Charless Fowlkes.  Predicting camera viewpoint improves cross-dataset generalization for 3d human pose estimation.  In ECCV 3DPW workshop, 2020.
  * [43] William A Wolovich and H Elliott.  A computational technique for inverse kinematics.  In CDC, 1984.
  * [44] Bin Xiao, Haiping Wu, and Yichen Wei.  Simple baselines for human pose estimation and tracking.  In ECCV, 2018.
  * [45] Fu Xiong, Boshen Zhang, Yang Xiao, Zhiguo Cao, Taidong Yu, Joey Tianyi Zhou, and Junsong Yuan.  A2j: Anchor-to-joint regression network for 3d articulated pose estimation from a single depth image.  In ICCV, 2019.
  * [46] Wang Zeng, Wanli Ouyang, Ping Luo, Wentao Liu, and Xiaogang Wang.  3d human mesh regression with dense correspondence.  In CVPR, 2020.
  * [47] Tianshu Zhan, Buzhen Huang, and Yangang Wangu.  Object-occluded human shape and pose estimation from a single color image.  In CVPR, 2020.
  * [48] Hongwen Zhang, Jie Cao, Guo Lu, Wanli Ouyang, and Zhenan Sun.  Learning 3d human shape and pose from dense body parts.  PAMI, 2020.
  * [49] Hongwen Zhang, Yating Tian, Xinchi Zhou, Wanli Ouyang, Yebin Liu, Limin Wang, and Zhenan Sun.  Pymaf: 3d human pose and shape regression with pyramidal mesh alignment feedback loop.  In ICCV, 2021.
  * [50] Junhao Zhang, Yali Wang, Zhipeng Zhou, Tianyu Luan, Zhe Wang, and Yu Qiao.  Learning dynamical human-joint affinity for 3d pose estimation in videos.  In TIP, 2021.
  * [51] Jason Y. Zhang, Sam Pepose, Hanbyul Joo, Deva Ramanan, Jitendra Malik, and Angjoo Kanazawa.  Perceiving 3d human-object spatial arrangements from a single image in the wild.  In ECCV, 2020.
  * [52] Tianshu Zhang, Buzhen Huang, and Yangang Wang.  Object-occluded human shape and pose estimation from a single color image.  In CVPR, 2020.
  * [53] Long Zhao, Xi Peng, Yu Tian, Mubbasir Kapadia, and Dimitris N. Metaxas.  Semantic graph convolutional networks for 3d human pose regression.  In CVPR, 2019.
  * [54] Yuxiao Zhou, Marc Habermann, Ikhsanul Habibie, Ayush Tewari, Christian Theobalt, and Feng Xu.  Monocular real-time full body capture with inter-part correlations.  In CVPR, 2021.
  * [55] Yuxiao Zhou, Marc Habermann, Weipeng Xu, Ikhsanul Habibie, Christian Theobalt, and Feng Xu.  Monocular real-time hand shape and motion capture using multi-modal data.  In CVPR, 2020.

## Appendix

##  Appendix A Qualitative Results

We show more qualitative results on COCO [22] in Fig 10, and 3DOH [52] in Fig
11.

Figure 10: More qualitative results on COCO dataset. (Best viewed in Color)
Figure 11: More qualitative results on 3DOH dataset. (Best viewed in Color)

##  Appendix B Part Segmentation in UV Space

We first use the reference T-pose mesh and the LSP joint regressor provided by
[15, 46] to get the T-pose 14 joint location. Then we calculate the joint-
vertex euclidean distance and assign vertex to joint based on the smallest
distance. After that, we use the barycentric interpolation (mapping between
vertex triangle and UV space triangles) to get the UV space assignment
probability ($128\times 128\times 14$). Following these operations, we use
argmax to get the final assignment for each UV grid to the joint location.

##  Appendix C Implementation Details

For AMASS [26] data, we only get SMPL-H [32] fitting instead of SMPL fitting
data, however, SMPL-H does not included hands rotations as in SMPL. We sample
random rotations from SPIN [15] fitting or the predictions from our DMP stages
for its training data. For AIST++ [18], it does not included $\beta$
parameters, we sample $\beta$ from SPIN [15] fitting or the predictions from
our DMP stages for its training data. We use the original rotation
representation from SMPL [23] (axis-angle representation) for the fast
training purpose.


# Efficient Medical Image Segmentation with Intermediate Supervision Mechanism

Di Yuan1,2, Junyang Chen3, Zhenghua Xu1,2,†, Thomas Lukasiewicz4, Zhigang Fu5,
Guizhi Xu1,2 1State Key Laboratory of Reliability and Intelligence of
Electrical Equipment, Hebei University of Technology, China.2Tianjin Key
Laboratory of Bioelectromagnetic Technology and Intelligent Health, Hebei
University of Technology, China.3Faculty of Science and Technology, University
of Macau, China.4Department of Computer Science, University of Oxford, United
Kingdom.5Department of Health Management Center, 983 Hospital of Joint
Logistics Support Force, China.†Corresponding author, email:
<EMAIL_ADDRESS>
###### Abstract

Because the expansion path of U-Net may ignore the characteristics of small
targets, intermediate supervision mechanism is proposed. The original mask is
also entered into the network as a label for intermediate output. However,
U-Net is mainly engaged in segmentation, and the extracted features are also
targeted at segmentation location information, and the input and output are
different. The label we need is that the input and output are both original
masks, which is more similar to the refactoring process, so we propose another
intermediate supervision mechanism. However, the features extracted by the
contraction path of this intermediate monitoring mechanism are not necessarily
consistent. For example, U-Net’s contraction path extracts transverse
features, while auto-encoder extracts longitudinal features, which may cause
the output of the expansion path to be inconsistent with the label. Therefore,
we put forward the intermediate supervision mechanism of shared-weight decoder
module. Although the intermediate supervision mechanism improves the
segmentation accuracy, the training time is too long due to the extra input
and multiple loss functions. For one of these problems, we have introduced
tied-weight decoder. To reduce the redundancy of the model, we combine shared-
weight decoder module with tied-weight decoder module.

###### Index Terms:

Medical Image Segmentation, U-Net, Intermediate Supervision Mechanism, Tied-
Weight Decoder Module.

##  I Introduction

Although U-Net [1] and its variants have already achieved some great
successes, their segmentation accuracies for small objects in medical images
are still unsatisfaction. Specifically, in the context of medical images, the
objects of interest are often relatively small, e.g., early tumor lesion [2].
Moreover, in the down-sampling of U-Net, more and more abstract or coarse
feature maps will be generated layer by layer [3]. Therefore, in the deepest
feature maps, the features of these important small objects may become
invisible or even be lost [4], which thus results in inaccurate segmentation
for small objects.

Consequently, to solve this problem, we propose the intermediate supervision
mechanism to enhance the small objects learning capability of U-Net based deep
segmentation models. Intuitively, we believe this enhancement can be achieved
by adding some additional intermediate supervision signals for the coarse
small object features [5]. We denote the deep model that integrates U-Net with
intermediate supervision mechanism as _Inter-U-Net_.

Despite achieving better accuracies than U-Net, Inter-U-Net is very time-
consuming in practice, mainly due to the need for computing multiple
additional intermediate supervision losses and taking the segmentation masks
as additional inputs. Besides, the learning signals in Inter-U-Net become
minuscule and insignificant when they are back-propagated to the first layers,
resulting into numerous training epochs needed to reach model convergence.
Therefore, to enhance the training efficiency, we further propose to integrate
a tied-weight decoder module with Inter-U-Net (denoted as _TW-Inter-U-Net_).
Our experiment results demonstrate that the tied-weight decoder module can
greatly reduce the model’s training time-cost, while maintaining similar (and
sometimes even better) training quality and segmentation accuracies.

Please note that the above intermediate supervision mechanism and tied-weight
decoder module can be applied to all U-Net based deep segmentation models.
Therefore, as an example, we further illustrate the way of integrating them
with a state-of-the-art U-Net variant, U-Net++.

The contributions of this paper are briefly as follows:

$\bullet$ We discover the limitation of the existing U-Net based deep models
in small objects segmentation, and propose a novel intermediate supervision
mechanism to resolve this problem by using additional intermediate supervision
signals to help strengthen the coarse small object features and prevent
information loss in deep layers.

$\bullet$ A tied-weight decoder module is further introduced to enhance the
deep model’s training efficiency, while maintaining similar (and sometimes
even better) training quality and segmentation accuracies.

$\bullet$ Besides U-Net, we demonstrate that the proposed intermediate
supervision mechanism and tied-weight decoder can also be applied in other
U-Net based deep segmentation models, e.g., U-Net++.

$\bullet$ Extensive experiments are conducted on three real-world datasets,
the results show that our proposed method can not only significantly
outperform the state-of-the-art baselines in small objects segmentation, but
also provide efficient model explanations.

Figure 1: Overview of Inter-U-Net.

##  II Related Work

Deep learning has already been successfully applied in medical image
segmentation. However, most models encounter the problem of poor segmentation
performance of small objects. Therefore, we propose the intermediate
supervision mechanism to enhance the small objects learning capability of deep
learning based segmentation models. Besides, to ensure the scalability in
practice, we further introduce a tied-weight decoder module to improve our
model’s training efficiency.

There also exists some other works that utilize additional supervision signals
to improve the performance of deep learning models. Specifically, DSN [5] is
proposed that simultaneously minimizes classification error and improves the
directness and transparency of the hidden layer learning process. However,
different from our work, the additional supervision signals in these solutions
are not used to solve the problem of inaccurate segmentation of medical
images, nor the problem of inaccurate segmentation of small objects. Besides,
in order to enhance the model’s learning efficiency, Myronenko et al. [6] add
a variational auto-encoder branch to the encoder endpoint to reconstruct the
original image to regularize the tied decoder and impose additional
constraints on its layers. However, these works are based on the variational
decoder, and we introduce the tied-weight decoder module. We believe that the
tied-weight decoder module is better than the variational decoder for
improving model efficiency.

##  III Inter-U-Net

Figure 2: Overview of AE-U-Net.

Although U-Net [1] has already achieved some good successes in medical image
segmentation, the segmentation accuracies for small objects are still
unsatisfaction. In the contracting path of U-Net, the features of these
important small objects become less and less visible or even disappear,
leading to inaccurate segmentation for the small objects [4]. Consequently, in
this paper, we propose five different intermediate supervision mechanisms to
overcome the problem of existing U-Net and its variants, and to enhance the
segmentation performance of them for medical images with small objects.
Intuitively, we believe this enhancement can be achieved by adding some
additional intermediate supervision signals for the abstract or coarse small
object feature maps.

In this section, we propose the first intermediate supervision mechanism based
on U-Net (_Inter-U-Net_). Figure 1 shows an overview of Inter-U-Net. Briefly,
Inter-U-Net takes the original medical images and the corresponding
segmentation masks, $x$ and $m$, as inputs and generate the segmentation
outputs at the last layer, denoted $y$ and $y^{\prime}$. Besides, $x$ and $m$
generate the intermediate outputs and intermediate masks respectively at the
model’s deepest layer and the expanding path, denoted $y_{j}$ and
$y^{\prime}_{j}$ (where $j=\\{0,1,2,3,4\\}$), respectively. For the sake of
description, the intermediate outputs and intermediate masks in this paper
refer to the outputs produced by the deepest layer of the model and each layer
of the actual expansion path. Finally, the loss function between $y$ and the
corresponding segmentation masks $m$ is denoted as $L_{image}$, and the loss
function between $y^{\prime}$ and $m$ is denoted as $L_{mask}$. Moreover, we
regard $y^{\prime}_{j}$ as the segmentation masks corresponding to the $j$th
layer of $y_{j}$, and the intermediate supervision losses between $y_{j}$ and
$y^{\prime}_{j}$ are denoted as $L_{j}$.

Formally, given the original medical images $x$, the corresponding
segmentation masks $m$, and their outputs in the last layer of the model,
denoted as $y$ and $y^{\prime}$, the loss functions of them are defined as
follows:

$\displaystyle L_{image}=L_{BD}(y,m),$ (1)

$\displaystyle L_{mask}=L_{BD}(y^{\prime},m),$ (2)

where $L_{BD}$ is the combination of Binary Cross-Entropy Loss (BCE Loss) and
DICE Loss (also known as F1 score).

Then, the intermediate outputs of $x$ and $m$ of the segmentation model are
denoted as $y_{j}$ and $y^{\prime}_{j}$ respectively, and the loss function in
the deepest layer of them are denoted as follows:

$\displaystyle L_{j}=L_{M}(y_{j},y^{\prime}_{j}),$ (3)

where $L_{M}$ is Mean Square Error (MSE Loss), $j\in\\{0,1,2,3,4\\}$. Finally,
the hybrid loss function ($L_{h}^{1}$) designed by us can be considered as the
sum of $L_{image}$, $L_{mask}$, and $L_{j}$. Therefore, the model’s learning
ability for the small objects and the segmentation details in medical images
can be enhanced. $L_{h}^{1}$ is defined as follows:

$\displaystyle L_{h}^{1}=\alpha\cdot L_{image}+\gamma\cdot
L_{mask}+\lambda\cdot\sum_{j=0}^{4}\omega_{j}\cdot L_{j},$ (4)

where $\alpha$, $\gamma$, $\lambda$, and $\omega_{i}$ respectively represent
the weight of each loss function, which are independent parameters that can be
adjusted as required.

##  IV AE-U-Net

However, U-Net is mainly engaged in segmentation, and the extracted feature is
also the position information for precise positioning, and the input and
output of U-NET are different images. Our intermediate monitoring mechanism
requires both the original mask input and output, which is more similar to the
reconstruction process of auto-encoder (AE) [7]. Therefore, we combine AE with
U-Net and propose the second intermediate supervision mechanism (AE-U-NET).
The structure is shown as Figure 2. Different from the first intermediate
supervision mechanism, Inter-U-NET directly inputs corresponding segmentation
masks into the model, and the intermediate output generated by them is taken
as corresponding ground truths, while our AE-U-NET inputs segmentation masks
into another auto-Encoder model, and takes the intermediate output generated
in AE as corresponding ground truths. AE-U-Net and its loss function are
described as follows.

##  V SAE-U-Net

However, the features extracted by the contracting path of AE-U-Net are not
necessarily consistent. For example, U-Net extracts transverse features in
contracting path, while AE extracts longitudinal features, which may cause the
output of the expanding path to be inconsistent with the label. Therefore, we
put forward the intermediate supervision mechanism with a shared-weight
decoder (_SAE-U-Net_). The structure is shown as Figure 3.

Figure 3: Overview of SAE-U-Net. Figure 4: Overview of TWI-U-Net. Figure 5:
Overview of TWAE-U-Net.

##  VI Tied-weight decoder module

Intermediate supervision mechanism can improve the model’s segmentation
accuracy for the small objects. Nevertheless, its training is usually very
time-consuming, mainly because i) it has additional loss functions and
additional inputs. ii) The learning signals become minuscule and insignificant
when they are backpropagated to the first few layers, which results in very
slow learning progress and excessive training epochs for model convergence
[8]. Therefore, in this paper, to enhance model’s training efficiency, we
propose to use a tied-weight decoder module to generate additional learning
signals based on reconstruction errors. The model of Intermediate supervision
mechanism with tied-weight decoder module is called _TWI-U-Net_. The structure
is shown as Figure 4. To reduce the redundancy of the model, we combine SAE-U-
Net with tied-weight decoder (_TWAE-U-Net_). The structure is shown as Figure
5.

Formally, the definition of layers in encoder are the same as the ones in
Inter-U-Net. As for the decoder, the outputs of the tied-weight decoder module
are denoted as $\widetilde{x_{j}}$ (where $j=\\{0,1,2,3,4\\}$), and the
reconstructed loss function of this module is defined as:

$\displaystyle L_{t}=$ $\displaystyle\ L_{B}(\widetilde{x},x),$ (5)

where $L_{B}$ is BCE Loss. Finally, the reconstruction loss function is
combined with the loss function in Inter-U-Net to form an efficiency deep
learning signal for model training, and the total loss function is formally
defined as:

$\displaystyle L_{h}=L_{h}^{1}+\beta\cdot L_{t},$ (6)

where $\beta$ is an independent variable, which can be adjusted independently
as needed. The experiments show that TW-Inter-U-Net not only achieves much
better segmentation performance for the small objects than the state-of-the-
art U-Net models, but also has much quicker converging speed in model
training.

##  VII Experiments

In this section, we first introduce our experimental implementations,
including data preprocessing, baseline models, evaluation metrics, and so on.
Then, we validate the performance of our models with the task of medical image
segmentation from both quantitative and qualitative aspects. Finally, we
further evaluate the effectiveness of our models in the model convergence
speeds. Moreover, we also prove that the combination of the intermediate
supervision mechanism and the tied-weight decoder module will not weaken the
effects of each other, but improve each other. After that, we also verify that
our proposed methods are effective in both U-Net and U-Net variants.

###  VII-A Datasets

The empirical studies over three real datasets confirm that our models beat
other baseline models. We use three medical imaging datasets for model
evaluation, covering lesions/organs from different medical imaging modalities.
These datasets contain the characteristics of small datasets, small objects,
and unbalanced classes, and are more representative of the characteristics of
current medical images. For all datasets, there are 70% of the datasets for
training, 10% for validating, and 20% for testing.

###  VII-B Baseline Models

The descriptions of the baseline models can be divided into two groups: _U-Net
as the backbone,_ and _U-Net ++ as the backbone._

###  VII-C Experiment settings

We implement our network in PyTorch and trained it on NVIDIA TITAN XP 12GB GPU
using three datasets. Our experiments use the _early-stop_ mechanism, which
means the training stops when the model converges or reaches the maximum
training epochs. Moreover, we use Adam optimizer with an initial learning rate
of $\alpha_{0}=\emph{3e-4}$ and progressively decrease it for every three
training epochs according to: $\alpha=\alpha_{0}\ast 0.9$.

Figure 6: Visualization of segmentation results of all models on three
datasets.

###  VII-D Main Results

We also prove the validity of the proposed method from qualitative.
Specifically, the first, second, and third rows of Figure 6 present the
results of BraTS (2019), Cardiac, and Spleen datasets, respectively. Also, the
left and right panels of Figure 6 denote, respectively, ground truths, U-Net
and U-Net-based enhancement models, and U-Net++ and its enhancement models.

##  VIII Conclusions and Future Work

The segmentation accuracy of U-Net and its variants is not good for small
targets. Therefore, we propose different intermediate supervision mechanisms
to solve this problem. In addition, we introduced tied-weight decoder module
to improve the model’s training efficiency.

## Acknowledgment

This work was supported in part by the National Natural Science Foundation of
China under grant 61906063, in part by the Natural Science Foundation of
Tianjin, China, under grant 19JCQNJC00400, in part by the Yuanguang Scholar
Fund of Hebei University of Technology, China, and in part by the National
Natural Science Foundation of China under grant 51737003.

## References

  * [1] O. Ronneberger, P. Fischer, T. Brox, U-net: Convolutional networks for biomedical image segmentation, in: Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention, 2015, pp. 234–241.
  * [2] J. Zhang, D. Su, J. Fujimoto, L. Ying, C.-W. Chow, W. Sun, J. Zhang, J. Hu, C. Behrens, M. Antonoff, et al., Multiregion whole exome seuquencing of pre-and early neoplastic lung lesions, 2017.
  * [3] R. Hamaguchi, A. Fujita, K. Nemoto, T. Imaizumi, S. Hikosaka, Effective use of dilated convolutions for segmenting small object instances in remote sensing imagery, in: Proceedings of the IEEE Winter Conference on Applications of Computer Vision, 2018, pp. 1442–1450.
  * [4] J. Fu, Y. Wu, T. Mei, J. Wang, H. Lu, Y. Rui, Relaxing from vocabulary: Robust weakly-supervised deep learning for vocabulary-free image tagging, in: Proceedings of the IEEE International Conference on Computer Vision, 2015, pp. 1985–1993.
  * [5] C.-Y. Lee, S. Xie, P. Gallagher, Z. Zhang, Z. Tu, Deeply-supervised nets, in: Proceedings of the International Conference on Artificial Intelligence and Statistics, 2015, pp. 562–570.
  * [6] A. Myronenko, 3d mri brain tumor segmentation using autoencoder regularization, in: Proceedings of the International Conference on MICCAI Brainlesion Workshop, 2018, pp. 311–320.
  * [7] L. Deng, Three classes of deep learning architectures and their applications: a tutorial survey, APSIPA Transactions on Signal and Information Processing, 2012\.
  * [8] Z. Xu, T. Lukasiewicz, C. Chen, Y. Miao, X. Meng, Tag-aware personalized recommendation using a hybrid deep model, Proceedings of AAAI Press/International Joint Conferences on Artificial Intelligence, 2017.