# Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm
(GOMEA) on the Concatenated Trap Function

Yukai Qiao  0000-0002-9876-4353 School of Information Technology and
Electrical Engineering
University of Queensland1 Thørväld CircleBrisbaneAustralia
<EMAIL_ADDRESS>and  Marcus Gallagher  0000-0002-6694-9572 School of
Information Technology and Electrical Engineering
University of Queensland1 Thørväld CircleBrisbaneAustralia<EMAIL_ADDRESS>
(2024)

###### Abstract.

The Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) is a state of the
art evolutionary algorithm that leverages linkage learning to efficiently
exploit problem structure. By identifying and preserving important building
blocks during variation, GOMEA has shown promising performance on various
optimization problems. In this paper, we provide the first runtime analysis of
GOMEA on the concatenated trap function, a challenging benchmark problem that
consists of multiple deceptive subfunctions. We derived an upper bound on the
expected runtime of GOMEA with a truthful linkage model, showing that it can
solve the problem in $O(m^{3}2^{k})$ with high probability, where $m$ is the
number of subfunctions and $k$ is the subfunction length. This is a
significant speedup compared to the (1+1) EA, which requires
$O(ln{(m)}(mk)^{k})$ expected evaluations.

evolutionary algorithm, recombination, runtime analysis

††journalyear: 2024††copyright: acmlicensed††conference: Genetic and
Evolutionary Computation Conference; July 14–18, 2024; Melbourne, VIC,
Australia††booktitle: Genetic and Evolutionary Computation Conference (GECCO
’24 Companion), July 14–18, 2024, Melbourne, VIC, Australia††doi:
10.1145/3638530.3664158††isbn: 979-8-4007-0495-6/24/07††ccs: Theory of
computation Evolutionary algorithms††ccs: Theory of computation Theory of
randomized search heuristics††ccs: Theory of computation Evolutionary
algorithms††ccs: Computing methodologies Neural networks

##  1\. Introduction

Evolutionary Algorithms (EAs) are a class of optimization algorithms inspired
by the principles of natural evolution. They maintain a population of
candidate solutions and apply selection and variation operators to improve the
solutions over generations. The performance of EAs heavily depends on the
choice of variation operators and the problem structure. Recombination
operators, such as crossover, play a crucial role in exploiting the structure
of the problem by combining partial solutions from different individuals.
However, the effectiveness of recombination is often hindered by the linkage
between problem variables, i.e., the inter-dependencies between different
components of the solution.

To address this issue, the Gene-pool Optimal Mixing Evolutionary Algorithm
(GOMEA)(Thierens and Bosman, 2011) was introduced. GOMEA is a novel EA that
employs a linkage model to capture the dependencies between problem variables
and performs variation by mixing partial solutions according to this model.
The linkage model is represented by a Family of Subsets (FOS), which is a set
of subsets of problem variables that are considered to be interdependent. By
using this linkage knowledge, GOMEA aims to efficiently exploit the problem
structure and avoid disrupting important building blocks during variation.

In this paper, we perform the first rigorous runtime analysis of GOMEA on the
concatenated trap function, a well-known benchmark problem that consists of
multiple deceptive subfunctions. We derive an upper bound on the expected
runtime of GOMEA with a truthful FOS, showing that it can efficiently solve
the problem by recombining optimal subsolutions. We also provide an upper
bound on the simple (1+1) EA, demonstrating the significant speedup achieved
by GOMEA’s informed recombination.

The rest of the paper is organized as follows. Section 2 provides the
necessary definitions and background on the concatenated trap function, the
(1+1) EA, and GOMEA. In Section 3, we present our theoretical analysis of the
runtime of both algorithms on the concatenated trap function. Section 4
reports our experimental results, verifying the derived upper bound for GOMEA.
Finally, Section 5 concludes the paper and discusses potential future work.

##  2\. Definitions

###  2.1. Concatenated Trap Function

The concatenated trap function (Deb and Goldberg, 1993) (Thierens, 2010) is a
concatenation of $m$ of $k$-bit trap functions, each designed to have a local
optimum and a global optimum. The function is defined as follows:

Let $x=(0,1)^{mk}$ be a binary string of length $mk$. The string is divided
into $m$ non-overlapping substrings of equal length $k$.

The fitness of each substring $x^{(i)}$ is evaluated using the trap function
$f_{trap}$:

(1) $f_{trap(k)}(x^{(i)})=\begin{cases}k-u(x^{(i)}),&\text{if }u(x^{(i)})<k\\\
k,&\text{otherwise}\end{cases}$

where $u(x^{(i)})$ is the number of ones in the substring $x^{(i)}$.

The overall fitness of the candidate solution $x$ is the sum of the fitness
values of all the substrings:

(2) $f_{MK}(x)=\sum_{i=1}^{m}f_{trap(k)}(x^{(i)})$

This is an additively separable function, with each subfunction being NP hard
with growing $k$. For each of the trap function, a hill climber is expected to
be either randomly initialized at the global optimum, or to be at the slope
leading to the local optimum. Once trapped at the local optimum, the only way
to get out is by performing a $k$ bits jump, which is exponentially unlikely
with growing $k$.

###  2.2. (1+1) Evolutionary Algorithm

The (1+1) Evolutionary Algorithm, denoted as (1+1) EA, is a simple yet
fundamental evolutionary algorithm. It maintains a population of size one and
applies mutation as the sole variation operator, as described in Algorithm 1.

###  2.3. Family Of Subsets

As a form of substructure representation, a Family Of Subsets (FOS)(Thierens
and Bosman, 2011) $\mathcal{F}$ is a set of subsets of
$\mathcal{S}=\\{0,1,2,..,l-1\\}$ which are the indices of problem parameters
with a size of $l$. Each element $\mathcal{F}_{i}$ is assumed to be relatively
independent of the rest of the parameters $\mathcal{S}-\mathcal{F}_{i}$.

In a Marginal Product FOS, each element is mutually exclusive of the other;
$\mathcal{F}_{i}\cap\mathcal{F}_{j}=\emptyset$ for any
$\mathcal{F}_{i},\mathcal{F}_{j}\in\mathcal{F}$. In its simplest form, each
subset consists of only one parameter which is the univariate FOS.

For the purpose of this paper, we only consider a separable problem that can
be truthfully represented by a Marginal Product FOS. We say a MP FOS is
truthful if each subset contains only inputs of a specific subfunction. For
example, a truthful MP FOS for the concatenated trap function with parameter
$m$ and $k$ would be: $\\{\\{ik,ik+1,...ik+k-1\\}|k\in[m-1]\\}$.

Algorithm 1 (1+1) EA

1:Initialize a candidate solution $x\in\\{0,1\\}^{n}$

2:while termination criterion not met do

3: $x^{\prime}\leftarrow mutate(x,p)$ //Each bit has an independent
probability p of flipping

4: if $f(x^{\prime})\geq f(x)$ then

5: $x\leftarrow x^{\prime}$

6: end if

7:end while

8:return $x$

Algorithm 2 GOMEA with random selection

function GOM($p_{0},P,\mathcal{F}$)

for $\mathcal{F}_{i}$ in $\mathcal{F}$ do

$p_{1}\leftarrow randomSelection(P-p_{0})$

$p_{0}^{new}\leftarrow crossWithMask(p_{0},p_{1},\mathcal{F}_{i})$

$evaluateFitness(p_{0}^{new})$

if $p_{0}^{new}.fitness>p_{0}.fitness$ then

$p_{0}\leftarrow p_{0}^{new}$

end if

end for

Return $p_{0}$

end function

function GOMEA($\mathcal{F}$)

while termination criterion not met do

$P\leftarrow uniformInitialization$

$p_{0}\leftarrow uniformSelection(P)$

$p_{0}\leftarrow GOM(p_{0},P,\mathcal{F})$

end while

Return $p^{*}$ // Return the individual with highest fitness

end function

###  2.4. Gene-pool Optimal Mixing EA

In an Optimal Mixing (OM) operator the FOS is traversed in a random order and
an offspring is produced by two parents swapping genetic material using a
different FOS element as a crossover mask. Specifically, the FOS element
describes a subset of variables to be swapped into the first parent from the
second parent. The offspring is only accepted if it outperforms the first
parent and when it does it will replace the first parent. A pseudo-code is
provided in Algorithm.2.

Figure 1 and Figure 2 provide two examples of a GOM process with or without a
truthful FOS on the concatenated trap function. It can be clear that with a
truthful FOS, an individual will never lose an optimal sub solution on a fully
separable problem, conversely, without a truthful FOS, one risks of trading an
optimal sub solutions with inferior ones but with higher short term fitness
gain.

$\mathcal{F}=\\{\\{1,2,3\\},\\{4,5,6\\},\\{7,8,9\\}\\}$ Donor 1: 111 011 011
fitness = 3 Donor 2: 000 000 110 $\mathcal{F}_{i}=\\{1,2,3\\}$ Offspring: 000
010 011 fitness = 2 discarded Donor 1: 111 011 011 fitness = 3 Donor 3: 101
111 001 $\mathcal{F}_{i}=\\{4,5,6\\}$ Offspring: 111 111 011 fitness = 6
accepted Donor 1: 111 111 011 fitness = 6 Donor 4: 010 111 000
$\mathcal{F}_{i}=\\{7,8,9\\}$ Offspring: 111 111 000 fitness = 8, accepted
Figure 1. A GOM process with a truthful MP FOS on the concatenated trap
function with k=3, m=3 $\mathcal{F}=\\{\\{1,2,3,4,5,6\\},\\{7,8,9\\}\\}$ Donor
1: 111 011 011 fitness = 3 Donor 2: 000 000 110
$\mathcal{F}_{i}=\\{1,2,3,4,5,6\\}$ Offspring: 000 000 011 fitness = 4
accepted Donor 1: 000 000 011 fitness = 4 Donor 4: 010 111 000
$\mathcal{F}_{i}=\\{7,8,9\\}$ Offspring: 000 000 000 fitness = 6, accepted
Figure 2. A GOM process with an untruthful MP FOS on the concatenated trap
function with k=3, m=3

##  3\. Analysis

###  3.1. (1+1) EA runtime on the Concatenated Trap Function

###### Theorem 3.1.

The expected optimization time of (1+1)EA on concatenated trap function with
$m$ substrings of length $k$ is $O(\ln{m}(mk)^{k})$ with a mutation rate of
$\frac{1}{mk}$

###### Proof.

First, we separate the search process into two stages. In stage one, at least
one substring is neither at the local optimum nor the global optimum of the
trap function. In stage two, all substrings are either at the local optimum or
the global optimum and the search finishes when all substrings are at the
global optimum. In the first stage, it only requires a single 1 being flipped
to 0 for an increase of fitness, this is then reduced to a OneMax problem with
a problem size of $m(k-1)$ and mutation probability $\frac{1}{mk}$ since each
local optimum provides a fitness of $k-1$ at most. Without further proving,
the expected time spent in stage 1 is $O(mk\ln{mk})$. For stage two we apply
the multiplicative drift theorem(Lengler, 2020). Let state $s$ be the number
of non-optimal substrings. To make an improvement, a whole substring needs to
be flipped at once, this yields a multiplicative drift of at least:

(3)
$\begin{split}\Delta_{t}(s)\geq&s(\frac{1}{mk})^{k}(1-\frac{1}{mk})^{(m-s)k}\\\
\geq&s(\frac{1}{mk})^{k}(1-\frac{1}{mk})^{mk}\\\
\geq&\frac{s}{e}(\frac{1}{mk})^{k}\\\ =&\delta s\end{split}$

where $\delta=\frac{1}{e(mk)^{k}}$. This gives the bound:

(4) $\begin{split}O(\frac{1+\ln{m}}{\delta})=&O(e(mk)^{k}+e\ln{m}(mk)^{k})\\\
=&O(\ln{m}(mk)^{k})\end{split}$

∎

The runtime in stage 1 is absorbed by stage 2, thus the final upper bound is
$O(\ln{m}(mk)^{k})$.

###  3.2. GOMEA runtime on the Concatenated Trap Function

The proof consists of two parts. First, we show that the initial population
will contain all optimal substrings most of the time for a large enough
population size. Then, assuming a truthful MP FOS is given, we show that GOMEA
can recombine the optimal substrings across the population efficiently by
approximating this process as a diffusion process.

###### Lemma 3.2.

The probability of all $m$ optimal substrings to occur at least once in a
population size $\mu=cm2^{k}$ is $1-\epsilon$ where $\epsilon=me^{-cm}$ which
is exponentially small with $m$ and $c=\Omega(1)$.

###### Proof.

Let $X_{i}$ denote the number of optimal substrings for the $i$-th trap
function in the population. It is clear that $E[X_{i}]=\mu\frac{1}{2^{k}}$ as
the probability of a uniformly initiated bitstring with size of $k$ being all
ones is $\frac{1}{2^{k}}$. Applying the Chernoff bound to the probability that
$X_{i}=0$ i.e. none of the substring at subfunction $i$ is all ones.

$P(X_{i}=0)\leq e^{\frac{-\mu}{2^{k}}}$

Using the union bound, the probability that at least one subfunction has no
optimal strings for $\mu$ individuals is at most:

$P\left(\bigcup_{i=1}^{m}P(X_{i}=0)\right)\leq me^{\frac{-\mu}{2^{k}}}$

The probability for each subfunction optimal string to appear at least once in
the population is then at least $1-me^{\frac{-\mu}{2^{k}}}$. Let
$\mu=cm2^{k}$, the probability becomes $1-me^{-cm}$ with the second term being
exponentially small with m. ∎

###### Theorem 3.3.

The expected optimization time of GOMEA with a truthful FOS on concatenated
trap function with $m$ substrings of length k is $O(m^{3}2^{k})$ with a
probability of $1-\epsilon$ where $\epsilon=me^{-cm}$ which is exponentially
small with $m$, if the population size $\mu=cm2^{k}$ where $c=\Omega(1)$

###### Proof.

The property of the Gene Pool Optimal Mixing operator determines that when a
trap function optimum is obtained by an individual, it will never be lost from
recombination given that the FOS is truthful, since the mixing is done one
subset at a time and only an improvement is accepted. This means that there is
no hitchhiking where optimal genes are out-competed by numerous non-optimal
genes. When a uniform selection is used, the spreading rate of an optimal
substring depends solely on its current concentration in the population.This
also means the portion of optimal substrings at a timestep for each
subfunction are i.i.d. Formally, let $E(P_{t})$ denote the expected portion of
individuals containing an optimal substring for a subfunction at the $t$th
GOM. At each GOM an offspring is produced using each subset in the FOS as a
crossover mask with a random donor each time (i.e. $m$ times for this
problem), and the probability of a randomly selected parent gaining an optimal
substring is $(1-E(P_{t}))E(P_{t})$. The expected change is then:

$E(P_{t+1})-E(P_{t})=\frac{(1-E(P_{t}))E(P_{t})}{\mu}$

For the purpose of asymptotic analysis, this stochastic process can be
estimated by a continuous-time diffusion process where $p_{t}$ denotes the
portion of optimal substrings at time step $t$, location $i$:

$\frac{p_{t}}{dt}=\frac{(1-p_{t})p_{t}}{\mu}$

This is a logistic differential equation, and has a known solution with
$p_{0}=\frac{1}{\mu}$:

$p_{t}=\frac{1}{1+(\mu+1)e^{-(\frac{t}{\mu})}}$

Let $t=\mu m$

$p_{t}=\frac{1}{1+(\mu+1)e^{-m}}$

substitute $\mu=cm2^{k}$ in

$p_{t}=\frac{1}{1+(cm2^{k})e^{-m}}$

Assume $m$ grows faster than $k$, i.e. $m>ck$ where $c$ is a constant greater
than $\log_{2}^{e}$, $p_{t}$ is exponentially close to 1 as $m$ grows, which
also means that the portion of individuals with all optimal substrings
$\prod_{1}^{m}p_{t}$ is exponentially close to 1. Thus, it takes
$O(m^{2}2^{k})$ GOM operations for the optimal solution of concatenated trap
function to take over the population, note that each GOM contains $m$
evaluations, resulting in an take over time of $\Theta(m^{3}2^{k})$.
$O(m^{3}2^{k})$ is then an upper bound of the first hitting time of the
occurrence of the optimal solution.

∎

This is a significant speed-up compared to the 1+1 EA for $k>3$ since we
avoided the expensive $(mk)^{k}$ term, which corresponds to the time
complexity of jumping $k$ bits by mutation only. This shows the tremendous
advantage that can be achieved by having a diverse population and a
recombination operator that preserves optimal subsolutions.

This analysis does not consider the affect of mutation. However, if the
mutation is applied after a crossover with an FOS element as mask and is
limited to the FOS element only, it does not change the fact that an optimal
substring will not be lost during this process i.e. no hitchhiking. The
probability of a selected parent gaining an optimal substring will then be
multiplied by some constant greater than $\sqrt[m]{\frac{1}{e}}$ as the
probability of mutation flips no bits, as a consequence, $t$ will need to be
at most $\sqrt[m]{e}$ times larger for $p_{t}$ to converge to 1 at the same
speed as no mutation. For a randomly initialized population, mutation is still
necessary in case the population does not contain all optimal subsolutions,
even though it would mean a $\Omega((mk)^{k})$ runtime in this case. For a
very short time window, a less than $k$ bit jump might also result in a gain
of optimal substring before the selective pressure eliminate the number of
ones in the sub-optimal substrings.

This upper bound can be expanded to any separable function consist of $m$
subfunctions with $k$-bit bitstrings as domain, if replacing any subfunction
value to the optimal value yields an improvement in the total fitness.
Formally:

$f_{i}:[0,1]^{k}\mapsto\mathbb{R},f_{i}(\hat{x})\geq f_{i}(x)\text{ for
}x\in[0,1]^{k},G:\mathbb{R}^{m}\mapsto\mathbb{R}$
$F(x_{1},x_{2},...,x_{m})=G(f_{1}(x_{1}),f_{2}(x_{2}),...,f_{m}(x_{m}))$
$G(f_{1}(x_{1}),f_{2}(x_{2}),...,f_{m}(x_{m})\leq
G(...f_{i}(\hat{x}_{i}),...,f_{m}(x_{m}))\text{ for }i\in[m]$

##  4\. Experiment

###  4.1. Verification of Theorem 3.3

To verify the upper bound we initialize a population of size $m2^{k}$, with
bitstrings length $mk$ with all 0 bits, and for each FOS element, a random
individual receives a substring of all ones. This is to simulate the worst
case scenario while not considering the case where the population does not
contain all the optimal substrings. All results are averaged over 100 runs.

|
---|---
|

(a)

(b)

(c)

(d)

---

(e)

Figure 3. (a) to (d) Upper bound vs worst case performance (e) Comparison with
(1+1) EA with k=4 in logarithmic scale

The results are shown in Figure 3. It is clear that the upper bound is valid
in most cases, except for when $m$ is too small compared with $k$, as we have
discussed that $m$ needs to outgrow $k$ by a constant for the bound to be
accurate. The bound is also tight when $m$ is small, and the gap between the
bound and the actual runtime increases as $m$, which is expected, since the
bound is an estimation of take over time of the optimal solution rather than
the hitting time. The effect of including a local mutation where only the bits
in the current FOS element are mutated, agrees with our analysis before, and
appears to multiply the runtime by a factor that reduces with $m$.

###  4.2. Success Rate with Constant $c$

We have shown that the probability of a population containing all optimal
substrings is exponentially close to 1 with $c$, when $\mu=cm2^{k}$. To verify
this empirically, we run GOMEA 1000 times on the concatenated trap function
with $k=4$, $m=6$. To show the capability of GOM to preserve optimal genes, we
also run a ($\mu$+1) GA with deterministic crowding(Louis, 1993), uniform
crossover and uniform selection. GOM and deterministic crowding shares the
property where an offspring directly competes with its closest parent, thus it
is only for a fair comparison for GA to apply this diversity preserving
mechanism. A run is considered successful, if the optimal solution is found
within $2cm^{3}k^{2}$. For ($\mu$+1) GA, this limit is increased by 10 times.

The results in Figure 4 suggest that as $c$ increases, the success rate does
approach 1 exponentially with GOMEA. With a local mutation, the success rate
is also constantly higher. The reason is as we have discussed, that before the
non-optimal substrings are pushed to the local minimum, some optimal strings
might be gained by mutation at a much higher probability than $k$-bits jump.
Consequentially, the runtime is higher since the optimal substrings gained
from mixing might be disrupted by mutation. The ($\mu$+1) GA on the other
hand, even with all optimal substrings available in the population, only found
optimal solution around half of the time at $c=2$, with 10 times higher
runtime limit.

|
---|---

(a)

(b)

---

(c)

Figure 4. (a) The success rate of GOMEA and ($\mu$+1)EA with deterministic
crowding (b) Corresponding average runtime of succeeded runs.$k=4$ ,$m=6$,
over 1000 runs (c) Average runtime including ($\mu$ \+ 1) GA in logarithmic
scale

##  5\. Future Work

The theoretical and empirical results presented in this paper demonstrate the
effectiveness of GOMEA on the concatenated trap function, a problem with a
clear modular structure and deceptive subfunctions. Our analysis shows that
GOMEA can efficiently exploit this problem structure by recombining optimal
subsolutions using a truthful linkage model. This leads to several promising
directions for future research.

It would be interesting to investigate the performance of GOMEA on other
classes of modular problems, such as the NK-landscape. These problems exhibit
a more complex structure, with dependencies between subproblems at different
levels of hierarchy. Although empirical results exist, analyzing GOMEA’s
runtime on these problems could provide further insights into its ability to
deal with more challenging problem structures.

Our analysis assumes a truthful linkage model, where the FOS perfectly
captures the dependencies between problem variables. In practice, however, the
linkage model may not be known a priori and needs to be learned from the
population. Analyzing the impact of linkage learning on GOMEA’s performance
and developing efficient linkage learning techniques for problems with unknown
structure is an important direction for future work.

The concatenated trap function is particularly interesting because it
represents a class of problems that can be decomposed into NP hard
subproblems. The insights we gained on studying this problem thus might
potentially transfer into problems sharing similar properties, for example,
optimization of a mixture of experts system, which is now a backbone of Large
Language Models, or the optimization of neural network weights, which has been
shown to have a modular inter-dependency(Qiao and Gallagher, 2023).

##  6\. Conclusion

We presented the first runtime analysis of the Gene-pool Optimal Mixing
Evolutionary Algorithm (GOMEA) on the concatenated trap function. By
leveraging a truthful linkage model, GOMEA is able to efficiently exploit the
modular problem structure and recombine optimal subsolutions. We derived an
upper bound of $O(m^{3}2^{k})$ on the expected runtime, showing a significant
speedup compared to the simple (1+1) EA, which requires $O(\ln m(mk)^{k})$
evaluations.

Our empirical results verified the derived upper bound and demonstrated
GOMEA’s ability to find the optimal solution with high probability when the
population size is set appropriately. The experiments also highlighted the
importance of the Optimal Mixing operator in preserving important building
blocks during variation, as evident from the comparison with a $(\mu+1)$ GA
using deterministic crowding.

This work provides new theoretical insights into the behavior of GOMEA and its
ability to exploit problem structure through linkage learning and optimal
mixing. The analysis of the concatenated trap function, a problem consisting
of multiple deceptive subfunctions, showcases GOMEA’s potential for solving
optimization problems with modular interdependencies.

Future research directions include extending the analysis to more complex
modular problems, such as NK-landscapes, and investigating the impact of
linkage learning on GOMEA’s performance when the problem structure is unknown.
Furthermore, the insights gained from studying the concatenated trap function
could potentially transfer to real-world optimization problems with similar
properties, such as the optimization of mixture of experts systems or neural
network weights.

In conclusion, this paper contributes to the theoretical understanding of
GOMEA and highlights its effectiveness in exploiting problem structure through
informed variation operators. The runtime analysis on the concatenated trap
function serves as a foundation for further investigations into the behavior
and performance of GOMEA on a broader class of optimization problems.

##  7\. Continuation

###  7.1. Definitions

####  7.1.1. Generalized trap function

Following the definition in (Deb and Goldberg, 1993). A generalized trap
function has three extra parameters. $a$ is the local optimal, $b$ is the
global optimal, and $z$ defines the starting point of both slopes leading to
the local optimal and global optimal.

(5)
$f_{gen\\_trap(k)}(x^{(i)})=\begin{cases}\frac{a}{z}(z-u(x^{(i))}),&\text{if
}u(x^{(i)})\leq z\\\ \frac{b}{k-z}(u(x^{(i))}-z),&\text{otherwise}\end{cases}$

The trap function we have discussed above is a special case where
$a=k-1,b=k,z=k-1$.

####  7.1.2. Optimal Region

We define the optimal region $\bar{X_{*}}$ of a generalized trap function to
be the set of all bitstrings which has a function value greater than the local
optimal $a$.

(6) $\bar{X_{*}}=\\{x|f_{gen\\_trap(k)}(x)>a\\}$

In terms of $u$, this is a region between $[\lceil\frac{a(k-z)}{b}\rceil+z,k]$

The probability of a bitstring being uniformly initialized in the optimal
region is thus
$Pr(x\in\bar{X_{*}})=Pr(Bin(k,0.5)\geq\lceil\frac{a(k-z)}{b}\rceil+z)$

###  7.2. GOMEA with local mutation runtime on concatenated generalized trap
function

The strategy is similar as above. First, we calculate the population size
required for each of the optimal region for each subproblem to occur at least
once. Then, we show that GOMEA can effectively recombine those optimal regions
and perform hill-climbing afterward.

For simplicity, we refer $Pr(x\in\bar{X_{*}})$ as $p_{*}$

###### Lemma 7.1.

The probability of all $m$ optimal regions to occur at least once in a
population size $\mu=\frac{c}{p_{*}}m$ is $1-\epsilon$ where
$\epsilon=me^{-cm}$ which is exponentially small with $m$ and $c=\Omega(1)$.

###### Proof.

Same as the proof in Lemma 3.2, as we only need to replace $\frac{1}{2^{k}}$
to $p_{*}$ ∎

###### Theorem 7.2.

The expected optimization time of GOMEA with a truthful FOS and a local
mutation with mutation rate of $\frac{1}{k}$ on concatenated generalized trap
function with $m$ substrings of length k with parameters $a,b,z$ is at most
$\lfloor\frac{(b-a)(k-z)}{b}\rfloor(m\ln{m})(ek(1+\frac{c}{p_{*}})+\frac{ce}{p_{*}}m\ln{m})+\frac{c}{p_{*}}m^{3}$
which is $O(\frac{1}{p_{*}}m^{3})$ with a probability of $1-\epsilon$ where
$\epsilon=me^{-cm}$ which is exponentially small with $m$, if the population
size $\mu=\frac{c}{p_{*}}m$ where $c=\Omega(1)$

###### Proof.

Since the GOM operator will never lose a substring in the optimal region to a
substring not in the optimal region, we can safely apply the same strategy in
the previous proof of Theorem 3.3. We consider $m$ i.i.d optimization process,
with a level definition:
$l(X)=max(0,max(u(X))-(\lfloor\frac{(b-a)(k-z)}{b}\rfloor))$. $l$ tells us how
far has the best substring traveled along the slope toward the global
optimal.There are $\lfloor\frac{(b-a)(k-z)}{b}\rfloor$ levels at most and we
will estimate the time spent in each level.

We separate each level to two stages, in stage one, The best substring spread
to a constant portion of the population. In stage two, the local mutation
operator climb towards the global optimum by adding a 1.

In the worst case, the population only contain one substring at level $l$, the
spreading of such substring with time can be again modeled as a diffusion
process where $p_{t}$ denotes the portion of substring at level $l$ at time
step $t$. This time, however, the effect of mutation will put a coefficient of
approximately $\frac{1}{e}$ to the diffusion rate since the probability of
mutation not changing any bit is:$(1-\frac{1}{k})^{k}\approx\frac{1}{e}$ as
$k$ approaches infinity.

$\frac{p_{t}}{dt}=\frac{(1-p_{t})p_{t}}{e\mu}$

With $p_{0}=\frac{1}{\mu}$

$p_{t}=\frac{1}{1+(\mu+1)e^{-(\frac{t}{e\mu})}}$

Let $t=e\mu\ln{m}$

(7) $\begin{split}p_{t}&=\frac{1}{1+(\mu+1)e^{-\ln{m}})}\\\
&=\frac{1}{1+\frac{\frac{c}{p_{*}}m+1}{m}}\\\
&\approx\frac{1}{1+\frac{c}{p_{*}}}\\\ \end{split}$

Which is a constant. The time spent in this stage is thus
$t=\frac{ce}{p_{*}}m\ln{m}$

In stage two, with a constant portion of the population at level $l$, the
probability of a local mutation improve a level $l$ substring is at least:

$\frac{1}{1+\frac{c}{p_{*}}}(\frac{1}{k})(1-\frac{1}{k})^{k-1}>\frac{1}{(ek)(1+\frac{c}{p_{*}})}$

The time spent in this stage is then at most: $ek(1+\frac{c}{p_{*}})$

The expected time for the $i^{th}$ of the $m$ processes to reach maximum level
is thus
$E(T_{i})=\lfloor\frac{(b-a)(k-z)}{b}\rfloor(ek(1+\frac{c}{p_{*}})+\frac{ce}{p_{*}}m\ln{m})$

However, as we are solving for a concatenation of such subproblems, the
expected time for optimal subsolutions to occur at least once for all
subproblems is $E(\max\limits_{m}(T_{i}))$. Assuming $T_{i}$ follows
exponential distribution and given they are i.i.d, $E(\max\limits_{m}(T_{i}))$
can be approximated(David and Nagaraja, 2004) as $E(T_{i})\ln(m)$. Each GOM
operator also consists of $m$ function evaluations. The expected time spent on
finding all optimal subsolutions is in the end
$\lfloor\frac{(b-a)(k-z)}{b}\rfloor(m\ln{m})(ek(1+\frac{c}{p_{*}})+\frac{ce}{p_{*}}m\ln{m})$.
This can be reduced to $O(mk\ln{m}+\frac{1}{p_{*}}m^{2}\ln^{2}{m})$

Finally, GOMEA need to recombine the optimal subsolutions present at this
point, using the same argument in the previous proof, the time is bounded by
$\mu m^{2}=\frac{c}{p_{*}}m^{3}=O(\frac{1}{p_{*}}m^{3})$. Assuming $m$ grows
faster than $k$, the bound of the previous level climbing process is absorbed,
thus the final upper bound is $O(\frac{1}{p_{*}}m^{3})$ asymptotically. ∎

Again, this bound can be generalized to any subproblems with a given
probability $p_{*}$ of being initialized in an optimal region, if an hill
climber can efficiently optimize to the global optimum from any point within
the optimal region. Including a hill climbing process provides a much deeper
understanding of how GOMEA works on a much broader set of problems.

###  7.3. Experiment

####  7.3.1. Verification of Theorem 7.2

For convenience, we set $a=1$ and $b=k$, as we only need to change $z$ in
order to control the starting point of the optimal region which is just $z+1$.
We then run experiments with different settings and different resulting
$p_{*}$ on the worst case population, where for each subproblem, a substring
with $z+1$ ones occurs only once, with the rest of substrings being zeros.

We compare the worst case performance to the upper bound of the full expected
runtime $E(T)$, and only the last term of $E(T)$, $\frac{1}{p_{*}}m^{3}$,
excluding the hill climbing process. The results in Figure.5(a) to (e) showed
that the runtime of the hill climbing is generously overestimated and the last
term $\frac{1}{p_{*}}m^{3}$ seems to contribute the majority of the runtime.
Figure.5(f) supported our hypothesis that the difficulty of the problem to
GOMEA is dominated by $p_{*}$, regardless of the actual size of the problem.

|
---|---
|
|

(a)

(b)

(c)

(d)

(e)

(f)

Figure 5. (a) to (e) Upper bound vs worst case performance (e) Comparison
between different $p_{*}$

####  7.3.2. Success rate with c and comparison to GA

A similar experiment is run on GOMEA and GA with deterministic crowding,
verifying GOMEA’s ability of maintaining successful subsolutions. 1000 runs
are performed on the concatenated generalized trap function with $m=8$, $k=6$,
$z=4$ with a $p_{*}=0.1094$ consequently. From the previous experiment, we see
$\frac{c}{p_{*}}m^{3}$ is actually a pretty accurate estimation rather than
the complete $E(T)$, thus the success condition for GOMEA is within 2 times of
$\frac{c}{p_{*}}m^{3}$ and 20 times for GA.

The result in Figure.6(c) and (e) confirmed that GOMEA required a much smaller
population size with the concept of optimal region, as we only need substrings
in the optimal region rather than be at the global optimal. Surprisingly, GA
seems to perform pretty well on this problem as well. This may be because the
problem is no longer deceptive, since we keep the local optimum at the value
1, the average schema fitness with more zeroes are going to be lower than the
average schema fitness with more ones, resulting in benign hitchhiking, where
the crossover favor one good gene over several bad genes. For example, if an
existing optimal substring with a fitness value of 6 is to be disrupted during
a crossover in GA with deterministic crowding, the offspring will only be
accepted if it gains extra fitness value of 6 else where, and it is almost
impossible with the local optimum having a low fitness value of 1. In other
words, the optimal substrings are maintained even through a disruptive
crossover.

We then designed a tailed trap function shown in Fig.6(b), where the local
optimum has a much higher fitness value but the optimal region has the same
size. This is however, not a fully deceptive problem since the schemas with
the size of $k-1$ are not misleading. With the same $p_{*}$, the performance
of GOMEA is identical for these two problems, in fact, the expect runtime
would be the same for a hill climber, as the number of bit flips required to
escape the local optimum is the same. For GA with deterministic crowding
however, the problem is suddenly impossible to solve, unless with extremely
lucky initialization.

|
---|---
|
|

(a)

(b)

(c)

(d)

(e)

(f)

Figure 6. (a)(c)(e) Results of concatenated generalized trap function
(b)(d)(f) Results of concatenated tailed trap function

## References

  * (1)
  * David and Nagaraja (2004) Herbert A David and Haikady N Nagaraja. 2004.  _Order statistics_.  John Wiley & Sons.
  * Deb and Goldberg (1993) Kalyanmoy Deb and David E Goldberg. 1993.  Analyzing deception in trap functions.  In _Foundations of genetic algorithms_. Vol. 2. Elsevier, 93–108.
  * Lengler (2020) Johannes Lengler. 2020.  Drift analysis.  _Theory of evolutionary computation: Recent developments in discrete optimization_ (2020), 89–131.
  * Louis (1993) Sushil John Louis. 1993.  _Genetic algorithms as a computational tool for design_.  Indiana University.
  * Qiao and Gallagher (2023) Yukai Qiao and Marcus Gallagher. 2023.  Modularity based linkage model for neuroevolution. In _Proceedings of the Companion Conference on Genetic and Evolutionary Computation_. 675–678.
  * Thierens (2010) Dirk Thierens. 2010.  The linkage tree genetic algorithm. In _International Conference on Parallel Problem Solving from Nature_. Springer, 264–273.
  * Thierens and Bosman (2011) Dirk Thierens and Peter AN Bosman. 2011.  Optimal mixing evolutionary algorithms. In _Proceedings of the 13th annual conference on Genetic and evolutionary computation_. 617–624.


# ZeroShape: Regression-based Zero-shot Shape Reconstruction

Zixuan Huang1∗ Stefan Stojanov2∗ Anh Thai2 Varun Jampani3 James M. Rehg1
1University of Illinois at Urbana-Champaign,
2Georgia Institute of Technology, 3Stability AI

###### Abstract

We study the problem of single-image zero-shot 3D shape reconstruction. Recent
works learn zero-shot shape reconstruction through generative modeling of 3D
assets, but these models are computationally expensive at train and inference
time. In contrast, the traditional approach to this problem is regression-
based, where deterministic models are trained to directly regress the object
shape. Such regression methods possess much higher computational efficiency
than generative methods. This raises a natural question: is generative
modeling necessary for high performance, or conversely, are regression-based
approaches still competitive? To answer this, we design a strong regression-
based model, called ZeroShape, based on the converging findings in this field
and a novel insight. We also curate a large real-world evaluation benchmark,
with objects from three different real-world 3D datasets. This evaluation
benchmark is more diverse and an order of magnitude larger than what prior
works use to quantitatively evaluate their models, aiming at reducing the
evaluation variance in our field. We show that ZeroShape not only achieves
superior performance over state-of-the-art methods, but also demonstrates
significantly higher computational and data efficiency.111Project website at:
https://zixuanh.com/projects/zeroshape.html

**footnotetext: Both authors contributed equally to this work.

##  1 Introduction

Inferring the properties of individual objects such as their category or 3D
shape is a fundamental task in computer vision. The ultimate goal is to do
this accurately for any object, generally referred to as zero-shot
generalization. For machine learning methods, this means high accuracy on data
distributions that may be significantly different from the training set, such
as images of novel types of objects like machine parts or images from uncommon
visual contexts like underwater imagery. An object representation capable of
zero-shot generalization, therefore, needs to accurately capture the visual
properties that are shared across all objects in the world—an extremely
ambitious goal.

Figure 1: We outperform SOTA methods for zero-shot 3D shape reconstruction,
while having faster inference time and less training data. Circle size
indicates the number of 3D assets used for training, with biggest being
3M333We use 3M as a reference value. Point-E [33] and Shape-E [19] state a
dataset size of “several million”.. F-Score with threshold 0.05 is averaged
over Octroc3D [47], Pix3D [48] and OmniObject3D [62]. Figure 2: ZeroShape
reconstructions from in-the-wild images. Our method produces detailed and
accurate object reconstructions from single-view images on a diverse set of
objects.

Recent work in computer vision has taken the broader challenge of zero-shot
generalization head-on, with impressive developments for 2D vision tasks like
segmentation [23, 38], visual question answering [3, 24], image generation
[44, 1, 45], and in training general vision representations that can be easily
adapted for any vision task [39, 34]. This progress has largely been enabled
by increasing model size and scaling training dataset size to the order of
tens to hundreds of millions of images.

These developments have inspired efforts which aim at zero-shot generalization
for single image 3D object shape reconstruction [27, 28, 33, 19]. This is a
classical and famously ill-posed problem, with important applications like
virtual object placement in scenes in AR and object manipulation in robotics.
These works aim to learn a “zero-shot 3D shape prior” by relying on generative
diffusion models for 3D point clouds [33], NeRFs [19], or for 2D images fine-
tuned for novel-view synthesis [28, 27], enabled by million-scale 3D data
curation efforts such as Objaverse [9, 10]. While these methods show
impressive zero-shot generalization ability, it comes at a great compute cost
due to large model parameter counts and the inference-time sampling required
by diffusion models. Using expensive generative modeling for zero-shot 3D
shape from single images diverges from the approach of early deep learning-
based works on this task [46, 66, 52, 59, 63]. These works define the task as
a 3D occupancy or signed distance regression problem and predict the shape of
objects in a single forward pass. This raises a natural question: is
generative modeling necessary for high performance at learning zero-shot 3D
shape prior, or conversely, can a regression-based approach still be
competitive?

In this work, we find that regression approaches are indeed competitive if
designed carefully, and computationally more efficient by a large margin
compared to the generative counterparts. We propose ZeroShape: a regression-
based 3D shape reconstruction approach that achieves state-of-the-art zero-
shot generalization, trained entirely on synthetic data, while requiring a
fraction of the compute and data budget of prior work (see Footnote 3). We
build our model upon key ingredients that facilitate generalization based on
prior works: 1) usage of intermediate geometric representation (e.g. depth)
[30, 60, 66, 52, 63], 2) explicit reasoning with local features [64, 5, 59].
Specifically, we decompose the reconstruction into estimating the shape of the
visible portion of the object, and then predicting the complete 3D object
shape based on this initial prediction. The accurate estimation of the visible
3D surface is enabled by a joint modeling of camera intrinsics and depth,
which we find to be essential for high accuracy.

Another thrust of our work is a large benchmark for evaluating zero-shot
reconstruction performance. The 3D vision community is working on developing a
zero-shot 3D shape prior, but what is the correct way to evaluate our
progress? Currently we lack a well-defined benchmark, which has lead to well-
curated qualitative results and small scale quantitative results444On the
order of hundreds of objects from tens of categories at best, to just a few
dozen objects at worst. on different datasets across different papers. This
makes it difficult to track progress and identify directions for future
research. To resolve this and standardize evaluation, we develop a protocol
based on data generated from existing datasets of 3D object assets. Our
benchmark includes thousands of common objects from hundreds of different
categories and multiple data sources. We consider real images paired with 3D
meshes [48, 47], and also generate photorealistic renders of 3D object scans
[62]. Our large scale quantitative evaluation provides a rigorous perspective
on the current state-of-the-art.

In summary, our contributions are:

  * •

ZeroShape: A regression-based zero-shot 3D shape reconstruction method with
state-of-the-art performance at a fraction of the compute and data budget of
prior work.

  * •

A unified large-scale evaluation benchmark for zero-shot 3D shape
reconstruction, generated by standardized processing and rendering of existing
3D datasets.

##  2 Related Work

Estimating the 3D shape of an object from a single is a complex inverse
problem: while the shape of the visible object can be estimated from shading,
estimating the shape of the occluded portion requires prior knowledge about
object geometry. This is one of the marvels of human perception and achieving
it computationally is a major goal for our field. We review regression and
generative methods for this task.

Regression-based Methods. These works investigate different ways to represent
3D object shapes and the architectures to produce them from a single image,
e.g., meshes [20, 54, 58] or implicit representations like discrete [8, 50] or
continuous [32, 35] occupancy, signed distance fields [64, 52], point clouds
[14, 2], or sets of parametric surfaces [15, 65]. A major limitation of these
works is the limited generalization beyond the categories of the training set.
The improvements of decomposing the problem into predicting the depth and then
estimating the complete shape [46, 66, 52, 60, 63], and representing 3D in a
viewer centered rather than object centered reference frame [46, 66, 52]
allowed for improved zero-shot generalization. Most architectures follow an
encoder/decoder design, where the encoder produces a feature map from which
the decoder predicts the 3D shape. While early works produced a single feature
vector for the entire image, it was later identified that using local features
from a 2D feature map improved the detail of the predicted shapes [54, 64] and
improved generalization to unseen categories [63, 5]. This culminated with the
current state-of-the art regression method, MCC [59], which takes an RGB-D
image as input, and uses a transformer-based encoder-decoder setup to produce
a “shell occupancy” prediction 555Traditionally occupancy is formulated as
predicting whether a point in 3D is inside/outside a watertight mesh, whereas
MCC predicts whether it is within an $\varepsilon$ wide shell representing the
surface of the object.. Our approach incorporates all these prior findings for
improved generalization, and builds upon them with a new module for estimating
the visible shape of the object that estimates depth and camera intrinsics,
which is processed with a cross attention-based decoder to produce an
occupancy prediction.

3D Generative Methods This category of methods does zero-shot 3D shape
reconstruction using a learned 3D generative prior, where the 3D generation is
conditioned on one or few input images. Given image or text conditioning,
early work [61] used GANs to generate voxels, whereas more recent works use
diffusion models to generate point clouds [33], or function parameters for
implicit 3D representations [19]. Another related type of generative framing
is conditional view synthesis. Works in this direction fine-tune 2D generative
models [28], or train them from scratch [56, 67], to synthesize novel views
conditioned on single images and viewing angles. This results in an implicit
3D prior, from which a 3D shape can then be extracted by fitting a 3D neural
representation to the synthesized images, or predicting its parameters [27].

3D from 2D Generative Models There have been efforts to use the real-world 2D
image prior from text-to-2D generative models [44, 45, 40, 1] to reconstruct
3D shape from a single image. This category of works [31, 11, 49] often uses
techniques such as the SDS loss [36, 53] and generates 3D assets from images
by optimizing for each object separately. The prolonged optimization time
prevents these works from being evaluated at scale or applied in many real-
world applications. Orthogonal to the optimization-based approaches, we focus
on learning a 3D shape prior that generalizes across instance. We do not
perform any per-instance optimization at test time.

##  3 Method

Our goal is to achieve state of the art zero-shot performance for estimating
the complete 3D shape of an object from a single image. Formally, given an
object-centric single-view RGB image $I\in\mathbb{R}^{h\times w\times 3}$, we
regress a function that takes $I$ as input and predicts the shape. We
represent shape using an implicit occupancy representation, where we model the
shape surface as the isosurface of occupancy function
$f(\boldsymbol{x}|I;\theta)$. Here, $\boldsymbol{x}\in\mathbb{R}^{3}$ denotes
the query point’s coordinates—when the query point lies within the surface
$f(\boldsymbol{x}|I;\theta)=1$, otherwise $f(\boldsymbol{x}|I;\theta)=0$.

###  3.1 Architecture

Figure 3: Overview of our model. Our consists of three modules: a depth and
camera estimator, a geometric unprojection unit and a projection-guided shape
reconstructor. The depth and camera estimator predicts the depth and camera
intrinsics from the input image with a DPT backbone. The geometric
unprojection unit converts the depth and intrinsics estimation into a
normalized 3D visible surface, which is parameterized by a three-channel
projection map. The shape reconstructor finally reconstructs the full
occupancy field by fetching localized information from projection map through
cross attention.

We now present our architecture (see Fig. 3) for shape reconstruction. Our
architecture is based on two established practices from prior works in this
field: 1) usage of intermediate geometric representation [30, 60, 66, 52, 63]
and 2) explicit reasoning with spatial feature maps [64, 5, 59]. Specifically,
our model consists of three submodules: a depth and camera estimator, a
geometric unprojection unit and a projection-guided shape reconstructor.

Depth and camera estimator. We propose to estimate the 3D visible object
surface as an intermediate representation. To infer the full shape of an
object, one must understand the visible surface—not only because the visible
surface is often a large part of the full surface, but also because an
accurate visible surface facilitates geometric reasoning of the full object
reconstruction. This is because cues for reconstruction that allow for
generalization, such as symmetry, curvature, and repetition, can be more
effectively detected and leveraged in the 3D space. For example, if an object
is symmetric, then accurately inferring the 3D symmetry planes from a partial
3D surface is much easier than from 2D RGB or relative depth.

Inspired by this, we estimate 3D visible surface as our intermediate
representation instead of the commonly used depth maps [60, 66, 52]. MCC [59]
also uses visible surface to estimate the full shape, but they assume the
visible surface to be given as input. When inferring on in-the-wild images,
they use fixed intrinsics to unproject depth maps into the 3D surface.
Erroneous intrinsics lead to skewed 3D visible surfaces (see Fig. 4),
resulting in inaccurate 3D cues for the complete object shape. Therefore, we
propose to jointly estimate depth and intrinsics before predicting the full
shape. Note that learning to estimate depth and intrinsics can be fully
supervised with synthetic data. Specifically, our depth and camera estimator
estimates the depth map of the object $D\in\mathbb{R}^{h\times w}$ and the
camera intrinsics $K\in\mathbb{R}^{3\times 3}$ from the image $I$. We used a
shared DPT [42] backbone for the depth and camera estimator, and use two
different shallow heads to predict $D$ from the local tokens and $K$ from the
global token.

Geometric unprojection unit. Given the intrinsics $K$ and the depth map $D$,
the geometric unprojection unit unprojects them into a projection map
$P\in\mathbb{R}^{h\times w\times 3}$. The projection map encodes the visible
surface of the object, where each pixel value $P_{ij}$ represents the
coordinate of the unprojected 3D point at the pixel location $(i,j)$.
Formally, the geometric unprojection can be written as

$P_{ij}=D_{ij}K^{-1}{[i,j,1]}^{T}.$ (1)

We use a view-centric coordinate system, because prior works show that view-
centric learning is beneficial to generalization [51, 52]. Therefore the
camera coordinate frame is the “world” coordinate frame for shape
reconstruction, which means that only the camera intrinsics matrix is required
to unproject pixels to 3D. Note that unprojection is fully differentiable
w.r.t. $D$ and $K$, so we can easily use it as a module in an end-to-end
learning-based model. Additionally, the projection maps are foreground-
segmented, and the represented visible surface is normalized in the 3D space
to be zero-mean and unit-scale before being fed into the next module.

Figure 4: Effect of Intrinsics. Unprojecting an accurate depth map into a 3D
surface surface with erroneous intrinsics leads to skewed shape with wrong 3D
aspect ratio.

Projection-guided shape reconstructor. Using the estimated projection map $P$,
our projection-guided shape reconstructor recovers the full object shape.
Specifically, the projection-guided shape reconstructor first uses a ResNet
[16] encoder to encode and reshape the projection map $P$ into a set of
$d$-dimensional vectors, $\boldsymbol{t}\in\mathbb{R}^{k\times d}$. Each of
the $k$ vectors encodes a localized patch in the projection map. To facilitate
an explicit spatial reasoning, we use the cross-attention-based approach
proposed in MCC [59]. We linearly map every query point
$\boldsymbol{x}\in\mathbb{R}^{3}$ to the same dimension of feature vectors,
$d$. Then we use two cross attention layers to fetch relevant patch encodings
from $\boldsymbol{t}$ and fuse them with each query separately. Finally, the
reconstructor predicts the occupancy value of each $\boldsymbol{x}$ using the
fused feature vector via an MLP.

###  3.2 Loss

We use a two-stage training paradigm for our model, where we first pretrain
the depth and camera estimator and then fine-tune the whole model with 3D
supervision. For depth and camera pretraining, we use a depth loss
$\mathcal{L}_{depth}$ and projection-based intrinsics loss
$\mathcal{L}_{proj}$. For the depth loss, we use the SSIMAE loss from [41].
Note that the SSIMAE loss is scale-invariant, meaning that the depth estimator
trained using this loss will be metrically correct up to an unknown scale
factor. Therefore, directly regressing the absolute intrinsics is suboptimal
due to the uncertainty in the absolute scale. Instead, we observe that the
only factor that impacts shape reconstruction is whether the visible surface
recovered using Eq. 1 is accurate. Therefore, we directly minimize the MSE
loss between the predicted projection map $P$ and the ground truth projection
map $P^{*}$, and backpropagate to the camera and depth estimators.

Once the depth and camera estimator are learned, we jointly train the whole
model using the 3D occupancy loss $\mathcal{L}_{occ}$, which is a standard
binary cross entropy between the predicted occupancy values
$f(\boldsymbol{x}|I;\theta)$ and ground truth in the viewer-centric coordinate
frame.

###  3.3 Implementation Details

We train our model with the Adam [22] optimizer. During depth and camera
pretraining, we use a learning rate of $3\times 10^{-5}$, a batch size of 44,
a weight decay of 0.05 and momentum parameters of (0.9, 0.95). We train our
model for 15 epochs and initialize the depth estimator with the Omnidata [13]
weights. During the joint training stage, we use a learning rate of $3\times
10^{-5}$ for the projection-guided shape reconstructor, and a learning rate of
$10^{-5}$ for the pretrained depth and camera estimator (geometric
unprojection unit does not have learnable parameters). We use a batch size of
28, a weight decay of 0.05 and momentum parameters of (0.9, 0.95). At every
iteration, we randomly sample 4096 points to compute the occupancy loss. We
train our model on $4\times$ NVIDIA GeForce RTX 2080 Ti, which takes $\sim$2
days for pretraining and $\sim$3 days for joint training.

##  4 Data Curation

###  4.1 Training Dataset

We use all the 55 categories of ShapeNetCore.v2 [6] for a total of about 52K
meshes, as well as over 1000 categories from the Objaverse-LVIS [9] subset.
This subset of Objaverse has been manually filtered by crowd workers to
primarily include meshes of objects instead of other assets like scans of
large scenes and buildings. After filtering Objaverse-LVIS to remove objects
with minimal geometry (e.g. objects consisting of a single plane) this dataset
has 42K meshes. Pooling these two data sources gives us a total of over 90K 3D
object meshes from over 1000 categories.

We use Blender [37] to generate synthetic images from the 3D meshes, and to
extract a variety of useful annotations: depth maps, camera intrinsics, and
object and camera pose. Because the object distribution of ShapeNet is highly
skewed (67% of data is 7 categories), we generate 1 to 20 images per object,
scaled inversely from the number of meshes in the category of the object,
resulting in a total of 159K images. For Objaverse we generate 25 images per
object resulting in 939K images. Our traning set consists of slightly less
than 1.1M images.

We generate images with varying focal lengths, from 30mm to 70mm for a 35mm
image sensor size equivalent. We generate diverse object-camera geometry:
rather than the common approach of always pointing the camera at the middle of
the object at a fixed distance, we vary the object camera distance and vary
the LookAt point of the camera. This allows us to capture a wide range of
variability in how 3D shape projects to 2D. We follow the convention to use
center cropped and foreground segmented images for training and testing. We
provide more details in the supplement.

###  4.2 Evaluation Benchmark

We use three different real-world dataset evaluation: OmniObject3D [62],
Ocrtoc3D [47], and Pix3D [48]. Because our testing images images come from the
real world, or are renders of real 3D object scans distinct from our training
set, they are a good test set for zero-shot generalization.

OmniObject3D. OmniObject3D is a large and diverse dataset of 3D scans and
videos of objects from 216 categories, including household objects and
products, food and toys. Because the foreground segmentations are noisy, we
follow convention and render the 3D scans to generate test images [27, 28]. We
improve the default material shader which generates glass-like surface
appearance to appear more natural. We use Blender and HDR environment maps to
generate realistic images with diverse lighting. We randomly sample camera
viewpoint, distance and focal length.

Ocrtoc3D. Ocrtoc3D is a real-world object dataset that contains object-centric
videos and full 3D annotations from 15 coarse categories. Some coarse
categories contain many subcategories (e.g. toy animals contain various
species). For each video the mesh (3D scan) and the viewpoint information are
provided. We clean up this dataset by manually removing outliers (e.g. empty
meshes/wrong object scales) and use the full filtered dataset consisting of
749 unique image-object pairs.

Figure 5: Qualitative results. We compare ZeroShape to other SOTA methods on
our curated benchmark (first three columns are from Ocrtoc3D [47], last three
are from OmniObject3D [62]). Our reconstruction not only better aligns with
the visible surfaces from images, but also recovers a faithful global
structure of the reconstructed objects.

Pix3D. Pix3D is a real-world object dataset that contains 3D annotations from
9 categories. For each image in this dataset, an object mask, a CAD model, and
the input viewpoint information are provided. These 3D annotations come from
manual alignment between shapes and images. We follow the split of [17] and
use 1181 images.

Benchmark curation. To create an easy-to-use benchmark, we convert the three
heterogeneous datasets into a unified format. This includes aligning and
converting the camera intrinsics and extrinsics, and object poses, to a
standardized convention across the test datasets and our synthetic dataset.
This is often a tedious obstacle in 3D vision research. We also organize
images, masks and other metadata in a standardized manner. The release of our
training data, data generating pipeline, and benchmark will benefit the
community by providing a unified setup for large scale training on synthetic
data and large scale testing on real data.

##  5 Experiments

In this section we present our experiments, which include state-of-the-art
comparisons and ablations. We first describe the baselines we implemented on
our benchmark, and then show detailed quantitative and qualitative results.

###  5.1 Metrics

We evaluate the shape reconstruction models using Chamfer Distance (CD) and
F-score as our quantitative metrics following [25, 15, 51, 52, 17, 18].

Chamfer Distance. Chamfer Distance (CD) measures the alignment between two
pointclouds. Following [18], CD is defined as an average of accuracy and
completeness. Denoting pointclouds as $X$ and $Y$, CD is defined as:

$\small\text{CD}(X,Y)=\frac{1}{2|X|}\sum_{x\in X}\min_{y\in
Y}\|x-y\|_{2}+\frac{1}{2|Y|}\sum_{y\in Y}\min_{x\in X}\|x-y\|_{2}$ (2)

F-score. F-score measures the pointcloud alignment under a classification
framing. By selecting a rejection threshold $d$, F-score@$d$ (FS@$d$) is the
harmonic mean of precision@$d$ and recall@$d$. Specifically, precision@$d$ is
the percentage of predicted points that lies close to GT point cloud within
distance $d$. Similarly, recall@$d$ is the percentage of ground truth points
that have neighboring predicted points within distance $d$. FS$@d$ can be
intuitively interpreted as the percentage of surface that is correctly
reconstructed under a certain threshold $d$ that defines correctness.

Evaluation protocol. To compute CD and F-score, we grid-sample the implicit
function and extract the isosurface via Marching Cubes [29] for methods using
implicit representation. Then we sample 10K points from the surfaces for the
evaluation of CD and F-scores. Because most methods cannot predict view-
centric shapes, we use brute-force search to align the coordinate frame of
prediction with ground truth before calculating the metrics. This evaluation
protocol ensures a fair comparison between methods with different shape
representation and coordinate conventions.

###  5.2 Baselines

We consider five state-of-the-art baselines for shape reconstruction, SS3D
[4], MCC [59], Point-E [33], Shap-E [19] and One-2-3-45 [27].

SS3D learns implicit shape reconstruction by first pretraining on ShapeNet GT,
and then finetuning on real-world single-view images. The finetuning is
performed in a category specific way, and then a single unified model is
distilled from all category-specific experts. We compare our model with their
final distilled model.

MCC learns shell occupancy reconstruction using multi-view estimated point
clouds from CO3D [43]. Their model assumes known depth and intrinsics during
inference. To evaluate their model on RGB images, we use the DPT-estimated
depth and fixed intrinsics as MCC’s input following their pipeline.

Table 1: Quantitative comparison on OmniObject3D. Our method performs favorably to other state-of-the-art methods.  Methods | FS@1$\uparrow$ | FS@2$\uparrow$ | FS@5$\uparrow$ | CD$\downarrow$
---|---|---|---|---
SS3D [4] | 0.1515 | 0.3482 | 0.6618 | 0.482
MCC [59] | 0.1362 | 0.3215 | 0.6015 | 0.551
One-2-3-45 [27] | 0.1532 | 0.3585 | 0.6882 | 0.446
Point-E [33] | 0.1505 | 0.3598 | 0.6932 | 0.448
Shap-E [19] | 0.1483 | 0.3650 | 0.7029 | 0.434
ZeroShape (ours) | 0.2297 | 0.4927 | 0.8169 | 0.310

Point-E is a point cloud diffusion model that generates point clouds from text
prompts or RGB images. They additionally train a separate model that converts
point clouds into meshes. We compare our model with Point-E by combining their
image-to-point and point-to-mesh models.

Shap-E is another diffusion model that learns conditioned shape generation
from text or images. Different from Point-E, Shap-E uses a latent diffusion
setup and can directly generate implicit shapes. The final mesh reconstruction
are extracted with marching cubes.

Table 2: Quantitative comparison on Pix3D. Our method performs favorably to other state-of-the-art methods.  Methods | FS@1$\uparrow$ | FS@2$\uparrow$ | FS@5$\uparrow$ | CD$\downarrow$
---|---|---|---|---
SS3D [4] | 0.1326 | 0.2998 | 0.6316 | 0.485
MCC [59] | 0.1754 | 0.3386 | 0.6165 | 0.514
One-2-3-45 [27] | 0.1364 | 0.3137 | 0.6666 | 0.443
Point-E [33] | 0.1779 | 0.3830 | 0.7255 | 0.403
Shap-E [19] | 0.2016 | 0.4287 | 0.7833 | 0.340
ZeroShape (ours) | 0.1928 | 0.4290 | 0.7759 | 0.345

One-2-3-45 learns implicit shape reconstruction by breaking it down into a
generative view synthesis step and a multiview-to-3D reconstruction step. The
view synthesis is achieved with Zero-123 [28], a diffusion model that
generates novel-view images conditioned on the original images and poses.
Based on the synthesized multi-view images, a cost-volume-based module
reconstructs the full 3D mesh of the object.

###  5.3 Comparison to SOTA Methods

We compare our approach to other state-of-the-art methods on the benchmark we
curated. We now present and analyze the quantitative results for each dataset.

Results on OmniObject3D. We present our main quantitative comparison results
on OmniObject3D, which covers a great variety of object types. The results are
shown in Tab. 1. Comparing with other SOTA zero-shot 3D reconstruction
methods, we see our approach achieves significantly better performance.

Results on Ocrtoc3D.

Table 3: Quantitative comparison on Ocrtoc3D. Our method performs favorably to other state-of-the-art methods.  Methods | FS@1$\uparrow$ | FS@2$\uparrow$ | FS@5$\uparrow$ | CD$\downarrow$
---|---|---|---|---
SS3D [4] | 0.1271 | 0.2910 | 0.5963 | 0.543
MCC [59] | 0.1994 | 0.4098 | 0.7135 | 0.411
One-2-3-45 [27] | 0.1323 | 0.3076 | 0.6325 | 0.492
Point-E [33] | 0.1589 | 0.3591 | 0.6968 | 0.423
Shap-E [19] | 0.1725 | 0.3939 | 0.7315 | 0.395
ZeroShape (ours) | 0.2410 | 0.5091 | 0.8459 | 0.286

We present additional quantitative comparison results on Ocrtoc3D. Ocrtoc is
smaller than OmniObject, but still covers many object types, and the input
images are real photos. The results are shown in Tab. 3. Similar to the
results on OmniObject3D, our approach outperforms previous SOTA methods by a
large margin.

Results on Pix3D. We also present quantitative comparison results on Pix3D.
Unlike OmniObject3D and Ocrtoc3D, the object variety of this evaluation
dataset is much lower — all objects are furniture and more than two third of
the images are chairs and sofas. Therefore, the evaluation results are highly
bias towards this specific class of objects. The results are shown in Tab. 2,
and our method still achieves state-of-the-art performance. It is worth noting
that Point-E and Shap-E also perform well on this dataset. We hypothesize this
is might relate to the abundance of similar furniture categories in their
training set.

###  5.4 Qualitative Results

We show qualitative results of different methods in Fig. 5. Generative
approaches such as Point-E and Shap-E tend to have sharper surfaces and
contain more details in their generation. However, many details are erroneous
hallucination that do not accurately follow the input image, and the visible
surfaces are often reconstructed incorrectly. Previous regression-based
approaches such as MCC better follow the input cues in the input images, but
the hallucination of the occluded surfaces is often inaccurate. We observe
that One-2-3-45 and SS3D cannot always accurately capture details and
concavities. Comparing with prior arts, the reconstruction of ZeroShape not
only faithfully capture the global shape structure, but also accurately
follows the local geometry cues from the input image. More qualitative results
are included in the supplement.

Table 4: Ablation study on OmniObject3D. The design choices of our architecture are quantitatively justified: enforcing explicit geometric reasoning, and implementing it through unprojection with estimated depth and intrinsics is essential. Methods | FS@1$\uparrow$ | FS@2$\uparrow$ | FS@5$\uparrow$ | CD$\downarrow$
---|---|---|---|---
Ours w/o geo | 0.2110 | 0.4572 | 0.7797 | 0.347
Ours w/o unproj | 0.2135 | 0.4738 | 0.8053 | 0.323
Ours w/o intr | 0.2158 | 0.4742 | 0.8039 | 0.324
Ours | 0.2297 | 0.4927 | 0.8169 | 0.310

###  5.5 Ablation Study

We analyze our method by ablating the design choices we made. We consider
baselines by modifying different modules correspondingly. The results are
shown in Tab. 4.

Explicit geometric reasoning. We first consider the baseline without any
geometric reasoning (Ours w/o geo). We remove the projection unit together
with the depth and camera pretraining losses. The number of parameters is
controlled to be the same, and we train the model for the same number of total
iterations. Comparing the first row to the last row, we see that enforcing
explicit geometric reasoning in our model positively affects performance.

Alternative intermediate representations. Prior works [60, 61, 52] typically
consider depth as the 2.5D intermediate representation. To compare this to our
projection-based representation, we consider a baseline where the latent
vectors directly come from the depth map instead of a 3D projection map. As
shown in Tab. 4 (Ours w/o unproj), depth leads to inferior performance to our
intrinsic-guided projection map representation.

Intrinsic-guided projection. We propose joint learning of intrinsics with
depth to more accurately estimate the 3D shape of the visible object surface.
To study the impact of this, we compare our full model with a baseline without
intrinsics learning, where the unprojection to 3D is done via a fixed
intrinsics during both training and testing. This baseline (Ours w/o intr)
leads to indifferent performance to using depth intermediate representation
and is worse than our full model. We also show qualitative examples of the
estimated surface using our pretrained intrinsics estimator in Fig. 6.
Compared with fixed intrinsics, unprojection with our estimated intrinisics
leads to more accurate reconstruction of the visible surface.

##  6 Limitations and Discussion

Due to computational resource limitations, we are not able to process and
train our model on the full Objaverse dataset. Currently, the meshes from
Objaverse we use only consist of 5% of Objaverse and 0.4% of Objaverse-XL
objects. Based on the promising scaling properties of recent foundation models
[12, 21, 57], we believe it will be valuable to explore the scaling properties
of method.

Figure 6: Benefits of intrinsics learning. We show the reconstructed visible
surfaces for two real image inputs. The visible surface is unprojected from
estimated depths, with either fixed intrinsics or predicted intrinsics. Using
fixed intrinsics cause unrealistic deformations in the 3D aspect ratio of the
visible object surface (e.g. objects appear to be compressed).

Another limitation of our work is that we have not considered the modeling of
object texture. Predicting textures of unseen surfaces is highly ill-posed and
can greatly benefit from a strong 2D prior. Given the recent success of 2D
diffusion models [44] and their application in optimization-based 3D
generation methods [36, 31, 11, 26, 7, 55], we think it will be promising to
initialize or regularize these methods with our shape prior, potentially
boosting both the optimization efficiency and generation quality.

##  7 Conclusion

We present a strong regression-based model for zero-shot shape reconstruction.
The core of our model is an intermediate representation of the 3D visible
surface which facilitates effective explicit 3D geometric reasoning. We also
curate a large real-world evaluation benchmark to test zero-shot shape
reconstruction methods. Our benchmark pools data from three different real-
world 3D datasets and has an order of magnitude larger scale than the test
sets used by prior work. Tested on our benchmark, our model significantly
outperforms other SOTA methods and achieves higher computational efficiency,
despite being trained with much less 3D data. We hope our effort is a
meaningful step towards building zero-shot generalizable 3D reconstruction
models.

Acknowledgement. This work was supported by NIH
R01HD104624-01A1.

## References

  * [1] Midjourney: https://www.midjourney.com/showcase/recent/.  Accessed: May 5, 2023.
  * Achlioptas et al. [2018] Panos Achlioptas, Olga Diamanti, Ioannis Mitliagkas, and Leonidas Guibas.  Learning representations and generative models for 3d point clouds.  In _International conference on machine learning_ , pages 40–49. PMLR, 2018.
  * Alayrac et al. [2022] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al.  Flamingo: a visual language model for few-shot learning.  _Advances in Neural Information Processing Systems_ , 35:23716–23736, 2022.
  * Alwala et al. [2022] Kalyan Vasudev Alwala, Abhinav Gupta, and Shubham Tulsiani.  Pre-train, self-train, distill: A simple recipe for supersizing 3d reconstruction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3773–3782, 2022.
  * Bechtold et al. [2021] Jan Bechtold, Maxim Tatarchenko, Volker Fischer, and Thomas Brox.  Fostering generalization in single-view 3d reconstruction by learning a hierarchy of local and global shape priors.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15880–15889, 2021.
  * Chang et al. [2015] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al.  Shapenet: An information-rich 3d model repository.  _arXiv preprint arXiv:1512.03012_ , 2015.
  * Chen et al. [2023] Rui Chen, Yongwei Chen, Ningxin Jiao, and Kui Jia.  Fantasia3d: Disentangling geometry and appearance for high-quality text-to-3d content creation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2023.
  * Choy et al. [2016] Christopher B Choy, Danfei Xu, JunYoung Gwak, Kevin Chen, and Silvio Savarese.  3d-r2n2: A unified approach for single and multi-view 3d object reconstruction.  In _European conference on computer vision_ , pages 628–644. Springer, 2016.
  * Deitke et al. [2022] Matt Deitke, Dustin Schwenk, Jordi Salvador, Luca Weihs, Oscar Michel, Eli VanderBilt, Ludwig Schmidt, Kiana Ehsani, Aniruddha Kembhavi, and Ali Farhadi.  Objaverse: A universe of annotated 3d objects.  _arXiv preprint arXiv:2212.08051_ , 2022.
  * Deitke et al. [2023] Matt Deitke, Ruoshi Liu, Matthew Wallingford, Huong Ngo, Oscar Michel, Aditya Kusupati, Alan Fan, Christian Laforte, Vikram Voleti, Samir Yitzhak Gadre, et al.  Objaverse-xl: A universe of 10m+ 3d objects.  _arXiv preprint arXiv:2307.05663_ , 2023.
  * Deng et al. [2022] Congyue Deng, Chiyu Jiang, Charles R Qi, Xinchen Yan, Yin Zhou, Leonidas Guibas, Dragomir Anguelov, et al.  Nerdi: Single-view nerf synthesis with language-guided diffusion as general image priors.  _arXiv preprint arXiv:2212.03267_ , 2022.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Eftekhar et al. [2021] Ainaz Eftekhar, Alexander Sax, Jitendra Malik, and Amir Zamir.  Omnidata: A scalable pipeline for making multi-task mid-level vision datasets from 3d scans.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10786–10796, 2021.
  * Fan et al. [2017] Haoqiang Fan, Hao Su, and Leonidas J Guibas.  A point set generation network for 3d object reconstruction from a single image.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 605–613, 2017.
  * Groueix et al. [2018] Thibault Groueix, Matthew Fisher, Vladimir G. Kim, Bryan Russell, and Mathieu Aubry.  AtlasNet: A Papier-Mâché Approach to Learning 3D Surface Generation.  In _Proceedings IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Huang et al. [2022] Zixuan Huang, Stefan Stojanov, Anh Thai, Varun Jampani, and James M Rehg.  Planes vs. chairs: Category-guided 3d shape learning without any 3d cues.  In _European Conference on Computer Vision_ , pages 727–744. Springer, 2022.
  * Huang et al. [2023] Zixuan Huang, Varun Jampani, Anh Thai, Yuanzhen Li, Stefan Stojanov, and James M Rehg.  Shapeclipper: Scalable 3d shape learning from single-view images via geometric and clip-based consistency.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023.
  * Jun and Nichol [2023] Heewoo Jun and Alex Nichol.  Shap-e: Generating conditional 3d implicit functions.  _arXiv preprint arXiv:2305.02463_ , 2023.
  * Kanazawa et al. [2018] Angjoo Kanazawa, Shubham Tulsiani, Alexei A Efros, and Jitendra Malik.  Learning category-specific mesh reconstruction from image collections.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 371–386, 2018.
  * Kaplan et al. [2020] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kirillov et al. [2023] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan-Yen Lo, Piotr Dollár, and Ross Girshick.  Segment anything.  _arXiv:2304.02643_ , 2023.
  * Li et al. [2023] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.  _arXiv preprint arXiv:2301.12597_ , 2023.
  * Lin et al. [2020] Chen-Hsuan Lin, Chaoyang Wang, and Simon Lucey.  Sdf-srn: Learning signed distance 3d object reconstruction from static images.  _arXiv preprint arXiv:2010.10505_ , 2020.
  * Lin et al. [2023] Chen-Hsuan Lin, Jun Gao, Luming Tang, Towaki Takikawa, Xiaohui Zeng, Xun Huang, Karsten Kreis, Sanja Fidler, Ming-Yu Liu, and Tsung-Yi Lin.  Magic3d: High-resolution text-to-3d content creation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 300–309, 2023.
  * Liu et al. [2023a] Minghua Liu, Chao Xu, Haian Jin, Linghao Chen, Zexiang Xu, Hao Su, et al.  One-2-3-45: Any single image to 3d mesh in 45 seconds without per-shape optimization.  _arXiv preprint arXiv:2306.16928_ , 2023a.
  * Liu et al. [2023b] Ruoshi Liu, Rundi Wu, Basile Van Hoorick, Pavel Tokmakov, Sergey Zakharov, and Carl Vondrick.  Zero-1-to-3: Zero-shot one image to 3d object.  _arXiv preprint arXiv:2303.11328_ , 2023b.
  * Lorensen and Cline [1987] William E Lorensen and Harvey E Cline.  Marching cubes: A high resolution 3d surface construction algorithm.  _ACM siggraph computer graphics_ , 21(4):163–169, 1987.
  * Marr [2010] David Marr.  _Vision: A computational investigation into the human representation and processing of visual information_.  MIT press, 2010.
  * Melas-Kyriazi et al. [2023] Luke Melas-Kyriazi, Christian Rupprecht, Iro Laina, and Andrea Vedaldi.  Realfusion: 360 reconstruction of any object from a single image.  In _CVPR_ , 2023.
  * Mescheder et al. [2019] Lars Mescheder, Michael Oechsle, Michael Niemeyer, Sebastian Nowozin, and Andreas Geiger.  Occupancy networks: Learning 3d reconstruction in function space.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4460–4470, 2019.
  * Nichol et al. [2022] Alex Nichol, Heewoo Jun, Prafulla Dhariwal, Pamela Mishkin, and Mark Chen.  Point-e: A system for generating 3d point clouds from complex prompts.  _arXiv preprint arXiv:2212.08751_ , 2022.
  * Oquab et al. [2023] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al.  Dinov2: Learning robust visual features without supervision.  _arXiv preprint arXiv:2304.07193_ , 2023.
  * Peng et al. [2020] Songyou Peng, Michael Niemeyer, Lars Mescheder, Marc Pollefeys, and Andreas Geiger.  Convolutional occupancy networks.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part III 16_ , pages 523–540. Springer, 2020.
  * Poole et al. [2022] Ben Poole, Ajay Jain, Jonathan T Barron, and Ben Mildenhall.  Dreamfusion: Text-to-3d using 2d diffusion.  _arXiv preprint arXiv:2209.14988_ , 2022.
  * [37] Blender Project.  Blender, https://blender.org/.
  * Qi et al. [2023] Lu Qi, Jason Kuen, Tiancheng Shen, Jiuxiang Gu, Wenbo Li, Weidong Guo, Jiaya Jia, Zhe Lin, and Ming-Hsuan Yang.  High quality entity segmentation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 4047–4056, 2023.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , pages 8748–8763. PMLR, 2021.
  * Ramesh et al. [2022] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ , 1(2):3, 2022.
  * Ranftl et al. [2020] René Ranftl, Katrin Lasinger, David Hafner, Konrad Schindler, and Vladlen Koltun.  Towards robust monocular depth estimation: Mixing datasets for zero-shot cross-dataset transfer.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(3):1623–1637, 2020.
  * Ranftl et al. [2021] René Ranftl, Alexey Bochkovskiy, and Vladlen Koltun.  Vision transformers for dense prediction.  _ArXiv preprint_ , 2021.
  * Reizenstein et al. [2021] Jeremy Reizenstein, Roman Shapovalov, Philipp Henzler, Luca Sbordone, Patrick Labatut, and David Novotny.  Common objects in 3d: Large-scale learning and evaluation of real-life 3d category reconstruction.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10901–10911, 2021.
  * Rombach et al. [2021] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models, 2021.
  * Saharia et al. [2022] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  _Advances in Neural Information Processing Systems_ , 35:36479–36494, 2022.
  * Shin et al. [2018] Daeyun Shin, Charless C Fowlkes, and Derek Hoiem.  Pixels, voxels, and views: A study of shape representations for single view 3d object shape prediction.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3061–3069, 2018.
  * Shrestha et al. [2022] Rakesh Shrestha, Siqi Hu, Minghao Gou, Ziyuan Liu, and Ping Tan.  A real world dataset for multi-view 3d reconstruction.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part VIII_ , pages 56–73. Springer, 2022.
  * Sun et al. [2018] Xingyuan Sun, Jiajun Wu, Xiuming Zhang, Zhoutong Zhang, Chengkai Zhang, Tianfan Xue, Joshua B Tenenbaum, and William T Freeman.  Pix3d: Dataset and methods for single-image 3d shape modeling.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2974–2983, 2018.
  * Tang et al. [2023] Junshu Tang, Tengfei Wang, Bo Zhang, Ting Zhang, Ran Yi, Lizhuang Ma, and Dong Chen.  Make-it-3d: High-fidelity 3d creation from a single image with diffusion prior.  _arXiv preprint arXiv:2303.14184_ , 2023.
  * Tatarchenko et al. [2017] Maxim Tatarchenko, Alexey Dosovitskiy, and Thomas Brox.  Octree generating networks: Efficient convolutional architectures for high-resolution 3d outputs.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2088–2096, 2017.
  * Tatarchenko et al. [2019] Maxim Tatarchenko, Stephan R Richter, René Ranftl, Zhuwen Li, Vladlen Koltun, and Thomas Brox.  What do single-view 3d reconstruction networks learn?  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3405–3414, 2019.
  * Thai et al. [2021] Anh Thai, Stefan Stojanov, Vijay Upadhya, and James M Rehg.  3d reconstruction of novel object shapes from single images.  In _2021 International Conference on 3D Vision (3DV)_ , pages 85–95. IEEE, 2021.
  * Wang et al. [2023a] Haochen Wang, Xiaodan Du, Jiahao Li, Raymond A Yeh, and Greg Shakhnarovich.  Score jacobian chaining: Lifting pretrained 2d diffusion models for 3d generation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12619–12629, 2023a.
  * Wang et al. [2018] Nanyang Wang, Yinda Zhang, Zhuwen Li, Yanwei Fu, Wei Liu, and Yu-Gang Jiang.  Pixel2mesh: Generating 3d mesh models from single rgb images.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 52–67, 2018.
  * Wang et al. [2023b] Zhengyi Wang, Cheng Lu, Yikai Wang, Fan Bao, Chongxuan Li, Hang Su, and Jun Zhu.  Prolificdreamer: High-fidelity and diverse text-to-3d generation with variational score distillation.  _arXiv preprint arXiv:2305.16213_ , 2023b.
  * Watson et al. [2022] Daniel Watson, William Chan, Ricardo Martin-Brualla, Jonathan Ho, Andrea Tagliasacchi, and Mohammad Norouzi.  Novel view synthesis with diffusion models.  _arXiv preprint arXiv:2210.04628_ , 2022.
  * Wei et al. [2022] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_ , 2022.
  * Wen et al. [2019] Chao Wen, Yinda Zhang, Zhuwen Li, and Yanwei Fu.  Pixel2mesh++: Multi-view 3d mesh generation via deformation.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 1042–1051, 2019.
  * Wu et al. [2023a] Chao-Yuan Wu, Justin Johnson, Jitendra Malik, Christoph Feichtenhofer, and Georgia Gkioxari.  Multiview compressive coding for 3d reconstruction.  _arXiv preprint arXiv:2301.08247_ , 2023a.
  * Wu et al. [2017] Jiajun Wu, Yifan Wang, Tianfan Xue, Xingyuan Sun, Bill Freeman, and Josh Tenenbaum.  Marrnet: 3d shape reconstruction via 2.5 d sketches.  _Advances in neural information processing systems_ , 30, 2017.
  * Wu et al. [2018] Jiajun Wu, Chengkai Zhang, Xiuming Zhang, Zhoutong Zhang, William T Freeman, and Joshua B Tenenbaum.  Learning shape priors for single-view 3d completion and reconstruction.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 646–662, 2018.
  * Wu et al. [2023b] Tong Wu, Jiarui Zhang, Xiao Fu, Yuxin Wang, Jiawei Ren, Liang Pan, Wayne Wu, Lei Yang, Jiaqi Wang, Chen Qian, et al.  Omniobject3d: Large-vocabulary 3d object dataset for realistic perception, reconstruction and generation.  _arXiv preprint arXiv:2301.07525_ , 2023b.
  * Xiang et al. [2022] Yongqin Xiang, Julian Chibane, Bharat Lal Bhatnagar, Bernt Schiele, Zeynep Akata, and Gerard Pons-Moll.  Any-shot gin: Generalizing implicit networks for reconstructing novel classes.  In _2022 International Conference on 3D Vision (3DV)_. IEEE, 2022.
  * Xu et al. [2019] Qiangeng Xu, Weiyue Wang, Duygu Ceylan, Radomir Mech, and Ulrich Neumann.  Disn: Deep implicit surface network for high-quality single-view 3d reconstruction.  _Advances in neural information processing systems_ , 32, 2019.
  * Yang et al. [2018] Yaoqing Yang, Chen Feng, Yiru Shen, and Dong Tian.  Foldingnet: Point cloud auto-encoder via deep grid deformation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 206–215, 2018.
  * Zhang et al. [2018] Xiuming Zhang, Zhoutong Zhang, Chengkai Zhang, Josh Tenenbaum, Bill Freeman, and Jiajun Wu.  Learning to reconstruct shapes from unseen classes.  _Advances in neural information processing systems_ , 31, 2018.
  * Zhou and Tulsiani [2022] Zhizhuo Zhou and Shubham Tulsiani.  Sparsefusion: Distilling view-conditioned diffusion for 3d reconstruction.  _arXiv preprint arXiv:2212.00792_ , 2022.

Figure 7: Additional qualitative results and comparison on OmniObject3D.
Figure 8: Additional qualitative results and comparison on Ocrtoc3D. Figure 9:
Qualitative results and comparison on Pix3D. Figure 10: Qualitative results on
images generated with DALL$\cdot$E 3. These results demonstrate the zero-shot
generalization ability of ZeroShape to complex novel images.

##  Appendix A Additional Qualitative Comparison

We show additional qualitative results on OmniObject3D, Ocrtoc3D and Pix3D in
Fig. 7, Fig. 8 and Fig. 9, respectively. Comparing with prior arts, the
reconstruction of ZeroShape better captures the global shape structure and
visible geometric details.

##  Appendix B Inference on AI-generated Images

We present additional results of ZeroShape using images generated with
DALL$\cdot$E 3. To test the out-of-domain generalization ability, we generate
images of imaginary objects as the input to our model (see Fig. 10). Despite
the domain gap to realistic or rendered images, ZeroShape can faithfully
recover the global shape structure and accurately follow the local geometry
cues from the input image. These results also demonstrate the potential of
using ZeroShape in a text-based 3D generation workflow.

##  Appendix C Data Curation Details

In this section we describe our data generation procedure for training and for
rendering the object scans from OmniObject3D to generate one of our benchmark
test sets.

###  C.1 Synthetic Training Dataset Generation

Image Rendering. For an arbitrary 3D mesh asset, our Blender-based rendering
pipeline first loads it into a scene and normalizes it to fit inside a unit
cube. Our scene consists of a large rectangular bowl with a flat bottom, a
common scene setup that 3D artists use for rendering to allow for realistic
shading, and 4 point light sources and one area light source. We randomly
place cameras around the object with 30mm to 70mm focal length for a 35mm
sensor size equivalent. We randomly vary the distance, elevation (from 5 to 65
degrees), the LookAt point of the camera and generate images of $600\times
600$ resolution (see Fig. 11). This variation in object/camera geometry allows
capturing the variability of projective geometry in real world scenarios,
coming from different capture devices and camera poses. This is in contrast
with prior work that uses fixed intrinsics, fixed distance, and LookAt pointed
at the center of the object.

In addition to RGB images, we extract segmentation masks, depth maps,
intrinsics, extrinsics and object pose. We center crop the objects, mask out
the background, resize images to $224\times 224$ and process the additional
annotations to account for the crop, segmentation and resize.

Ground Truth Occupancy Extraction. To obtain ground truth occupancy, we first
extract watertight meshes using the code from occupancy networks
666https://github.com/autonomousvision/occupancy_networks, and then extract
SDF for $32^{3}$ query points per mesh following DISN
777https://github.com/laughtervv/DISN. The SDF is converted to occupancy
during training.

###  C.2 Generating the OmniObject3D Testing Set

The original videos released by the OmniObject3D dataset have noisy foreground
masks and are mostly taken indoor on a tabletop. To improve the lighting
variability and ensure accurate segmentations, we follow the rendering
procedure described in the previous section to generate testing data.
Different from our training set generation, we use HDRI environment maps to
generate scene lighting, which results in high lighting quality and diversity
(see Fig. 12).

Figure 11: Synthetic Training Data Generation. We render training images with
varying lighting, camera intrinsics and extrinsics. The images are center-
cropped, foreground-segmented and resized before being used as training input.
Figure 12: OmniObject3D Testing Data Generation. For OmniObject3D, we generate
realistic testing images with varying lighting, camera intrinsics and
extrinsics. To increase rendering realism and diversity, we use diverse HDRI
environment maps for scene lighting.


* McEwen et al. [2015] J. D. McEwen, M. Büttner, B. Leistedt, H. V. Peiris, Y. Wiaux,  A novel sampling theorem on the rotation group,  IEEE Sig. Proc. Let. 22 (2015) 2425--2429.
  * Górski et al. [2005] K. M. Górski, E. Hivon, A. J. Banday, B. D. Wandelt, F. K. Hansen, M. Reinecke, M. Bartelmann,  Healpix -- a framework for high resolution discretization and fast analysis of data distributed on the sphere 622 (2005) 759--771.
  * Schaeffer [2013] N. Schaeffer,  Efficient spherical harmonic transforms aimed at pseudospectral numerical simulations,  Geochemistry, Geophysics, Geosystems 14 (2013) 751--758.
  * Newman and Penrose [1966] E. T. Newman, R. Penrose,  Note on the Bondi-Metzner-Sachs group 7 (1966) 863--870.
  * Goldberg et al. [1967] J. N. Goldberg, A. J. Macfarlane, E. T. Newman, F. Rohrlich, E. C. G. Sudarshan,  Spin-$s$ spherical harmonics and $\eth$ 8 (1967) 2155--2161.
  * Kamionkowski et al. [1997] M. Kamionkowski, A. Kosowsky, A. Stebbins,  Statistics of cosmic microwave background polarization D55 (1997) 7368--7388.
  * Varshalovich et al. [1989] D. A. Varshalovich, A. N. Moskalev, V. K. Khersonskii, Quantum theory of angular momentum, World Scientific, Singapore, 1989.
  * Khalid et al. [2016] Z. Khalid, S. Durrani, R. A. Kennedy, Y. Wiaux, J. D. McEwen,  Gauss-legendre sampling on the rotation group,  IEEE Sig. Proc. Let. 23 (2016) 207--211.
  * McEwen et al. [2013] J. D. McEwen, P. Vandergheynst, Y. Wiaux,  On the computation of directional scale-discretized wavelet transforms on the sphere,  in: Wavelets and Sparsity XV, SPIE international symposium on optics and photonics, invited contribution, volume 8858, 2013. doi:10.1117/12.2022889. arXiv:arXiv:1308.5706.
  * Leistedt et al. [2013] B. Leistedt, J. D. McEwen, P. Vandergheynst, Y. Wiaux,  S2LET: A code to perform fast wavelet analysis on the sphere,  Astron. & Astrophys. 558 (2013) 1--9.
  * Khalid et al. [2014] Z. Khalid, R. A. Kennedy, J. D. McEwen,  An optimal-dimensionality sampling scheme on the sphere with fast spherical harmonic transforms,  IEEE Trans. Sig. Proc. 62 (2014) 4597--4610.
  * Healy et al. [2003] D. M. J. Healy, D. Rockmore, P. J. Kostelec, S. S. B. Moore,  FFTs for the 2-sphere -- improvements and variations 9 (2003) 341--385.
  * Skukowsky [1986] W. Skukowsky,  A quadrature formula over the sphere with application to high resolution spherical harmonic analysis 60 (1986) 1--14. 10.1007/BF02519350.
  * Kostelec and Rockmore [2008] P. Kostelec, D. Rockmore,  FFTs on the rotation group 14 (2008) 145--179.
  * Bradbury et al. [2018] J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, Q. Zhang, JAX: composable transformations of Python+NumPy programs, 2018. URL: http://github.com/google/jax.
  * Risbo [1996] T. Risbo,  Fourier transform summation of Legendre series and $D$-functions 70 (1996) 383--396.
  * Trapani and Navaza [2006] S. Trapani, J. Navaza,  Calculation of spherical harmonics and Wigner d functions by FFT. Applications to fast rotational matching in molecular replacement and implementation into AMoRe,  Acta Crystallographica Section A 62 (2006) 262--269.
  * Gautschi [1967] W. Gautschi,  Computational aspects of three-term recurrence relations,  SIAM review 9 (1967) 24--82.
  * Prézeau and Reinecke [2010] G. Prézeau, M. Reinecke,  Algorithm for the evaluation of reduced wigner matrices,  The Astrophysical Journal Supplement Series 190 (2010) 267.
  * Reinecke and Seljebotn [2013] M. Reinecke, D. S. Seljebotn,  Libsharp--spherical harmonic transforms revisited,  Astronomy & Astrophysics 554 (2013) A112.
  * Cooley and Tukey [1965] J. W. Cooley, J. W. Tukey,  An algorithm for the machine calculation of complex fourier series 19 (1965) 297--301.
  * McEwen et al. [2011] J. D. McEwen, G. Puy, J.-P. Thiran, P. Vandergheynst, D. V. D. Ville, Y. Wiaux,  Sampling theorems and compressive sensing on the sphere,  in: Wavelets and Sparsity XIV, SPIE international symposium on optics and photonics, invited contribution, volume 8138, 2011. doi:10.1117/12.893481. arXiv:arXiv:1110.6297.
  * Ocampo et al. [2023] J. Ocampo, M. A. Price, J. D. McEwen,  Scalable and equivariant spherical CNNs by discrete-continuous (DISCO) convolutions,  in: International Conference on Learning Representations (ICLR), 2023. arXiv:arXiv:2209.13603.
  * Press et al. [1992] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Fannery, Numerical recipes in Fortran 77, 2nd ed., Cambridge University Press, Cambridge, 1992.
  * Cohen et al. [2018] T. S. Cohen, M. Geiger, J. Koehler, M. Welling,  Convolutional networks for spherical signals,  in: ICML, Springer, 2018\. arXiv:arXiv:1709.04893.
  * Wengert [1964] R. E. Wengert,  A simple automatic derivative evaluation program,  Communications of the ACM 7 (1964) 463--464.
  * Baydin et al. [2018] A. G. Baydin, B. A. Pearlmutter, A. A. Radul, J. M. Siskind,  Automatic differentiation in machine learning: a survey,  Journal of Marchine Learning Research 18 (2018) 1--43.
  * Rumelhart et al. [1986] D. E. Rumelhart, G. E. Hinton, R. J. Williams,  Learning representations by back-propagating errors,  nature 323 (1986) 533--536.
  * McEwen et al. [2013] J. D. McEwen, G. Puy, J.-P. Thiran, P. Vandergheynst, D. V. D. Ville, Y. Wiaux,  Sparse image reconstruction on the sphere: implications of a new sampling theorem,  IEEE Trans. Image Proc. 22 (2013) 2275--2285.
  * Wallis et al. [2017] C. G. R. Wallis, Y. Wiaux, J. D. McEwen,  Sparse image reconstruction on the sphere: analysis vs synthesis,  IEEE Trans. Image Proc. 26 (2017) 5176--5187.
  * Price et al. [2021] M. A. Price, L. Pratley, J. D. McEwen,  Sparse image reconstruction on the sphere: a general approach with uncertainty quantification,  IEEE Trans. Image Proc., submitted (2021).
  * BICEP2 Collaboration [2014] BICEP2 Collaboration,  Detection of B-Mode Polarization at Degree Angular Scales by BICEP2 112 (2014) 241101\.
  * Bronstein et al. [2021] M. M. Bronstein, J. Bruna, T. Cohen, P. Veličković,  Geometric deep learning: Grids, groups, graphs, geodesics, and gauges,  arXiv preprint arXiv:2104.13478 (2021).