Unsupervised Object Detection with Theoretical Guarantees
Authors: Marian Longa
Joao F. Henriques
Venue: NeurIPS 2024 poster (2024)
Keywords: unsupervised object detection
object detection
unsupervised learning
representation learning
Primary area: machine_vision
TL;DR: We propose the first unsupervised object detection method that we prove has theoretical guarantees of recovering the true object positions up to small shifts.

Abstract: Unsupervised object detection using deep neural networks is typically a difficult problem with few to no guarantees about the learned representation. In this work we present the first unsupervised object detection method that is theoretically guaranteed to recover the true object positions up to quantifiable small shifts. We develop an unsupervised object detection architecture and prove that the learned variables correspond to the true object positions up to small shifts related to the encoder and decoder receptive field sizes, the object sizes, and the widths of the Gaussians used in the rendering process. We perform detailed analysis of how the error depends on each of these variables and perform synthetic experiments validating our theoretical predictions up to a precision of individual pixels. We also perform experiments on CLEVR-based data and show that, unlike current SOTA object detection methods (SAM, CutLER), our method's prediction errors always lie within our theoretical bounds. We hope that this work helps open up an avenue of research into object detection methods with theoretical guarantees.

Unsupervised Object Detection with Theoretical Guarantees
Marian Longa
João F. Henriques Visual Geometry Group University of Oxford j joao&robots. ox. ac uk
Visual Geometry Group University of Oxford
mlonga@robotss. ox. ac. uk
Abstract
Unsupervised object detection using deep neural networks is typically a difficult problem with few to no guarantees about the learned representation. In this work we present the first unsupervised object detection method that is theoretically guaranteed recover the true object positions up quantifiable small shifts. We develop an unsupervised object detection architecture and prove that the learned variables correspond the true object positions up small shifts related the encoder and decoder receptive field sizes, the object sizes, and the widths of the Gaussians used in the rendering process. We perform detailed analysis of how the error depends on each of these variables and perform synthetic experiments validating our theoretical predictions up to a precision of individual pixels. We also perform experiments on LLEVR-based data and show that, unlike current SOTA object detection methods (SAM, CutLER), our method's prediction errors always lie within our theoretical bounds. We hope that this work helps open up avenue research into object detection methods with theoretical guarantees.
Introduction
Unsupervised object detection using deep neural networks is a long-standing area of research at the intersection of machine learning and computer vision. Its aim to learn to detect objects from images without the use of training labels. Learning without supervision has multiple advantages, as obtaining labels for training data often costly and time consuming, and in some cases may be impractical unethical. For example, in medical imaging, unsupervised object detection
help save specialists' time by automatically flagging suspicious abnormalities [9)] and in autonomous driving may help automatically detect pedestrians collision course with the vehicle [3]. It is thus important to understand and develop better unsupervised object detection methods.
While successful, current object detection methods are often empirical and possess few to no guarantees about their learned representations. In this work we aim to address this gap by designing the first unsupervised object detection method that prove is guaranteed to learn the true object positions up to small shifts, and performing a detailed analysis of how the maximum errors of the learned object positions depend the encoder and decoder receptive field sizes, the object sizes, and the sizes the Gaussians used for rendering. This is especially important in sensitive domains such medicine, where incorrectly detecting object could be costly. Our method guarantees to detect any object that moves in a video or that appears at different locations in images, as long as the objects distinct and the images reconstructed correctly.
We base our unsupervised object detection method on an autoencoder with a convolutional neural network (CNN) encoder and decoder, and modify it make it exactly translationally equivariant (sec. 3. This allows us to interpret the latent variables as object positions and lets us train the network without supervision. We then use the equivariance property to formulate and prove theorem that relates the maximum position error of the learned latent variables to the size of the encoder and
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

decoder receptive fields, the size of the objects, and the width of the Gaussian used in the decoder (sec. D. Next, we derive corollaries describing the exact form of the maximum position error function of these four variables. These corollaries can be used as guidelines when designing unsupervised object detection networks, as they describe the guarantees of the learned object positions that can be obtained under different settings. We then perform synthetic and CLEVR-basee [[2] experiments to validate our theory (sec. []. Finally, we discuss the implications of our results for designing reliable object detection methods (sec. 6).
Concretely, the contributions of this paper are:
1. An unsupervised object detection method that is guaranteed to learn the true object positions up to small shifts.
2. A proof and detailed theoretical analysis of how the maximum position error of the method depends on the encoder and decoder receptive field sizes, object sizes, and widths of the Gaussians used in the rendering process.
3. Synthetic experiments, CLEVR- -based experiments, and real video experiments validating our theoretical results up precisions of individual pixels.
Related Work
Object Detection. Object detection is an area of research in computer vision and machine learning, dealing with the detection and location of objects in images. Popular supervised approaches to object detection include Segment Anything (SAM) [13]. Mask R-CNN 77. U-Net [18] and others [4]. While successful, these methods typically require large amounts of annotated segmentation masks and bounding boxes, which may be costly or impossible to obtain in certain applications. Popular unsupervised and self-supervised object detection methods include CutLER [23], Slot Attention 17]. MoNet (2) and others [5). These methods aim learn object-centric representations for object detection and segmentation without using training labels. Finally, unsupervised object localisation methods such FOUND (2 and others [22] aim to localise objects in images, typically using vision transformer (ViT) self-supervised features. Compared to both current supervised and unsupervised object detection and localisation methods, our work is the only one that has provable theoretical guarantees of recovering the true object positions up to small shifts. It also requires no supervision.
Identifiability Representation Learning. Identifiability in representation learning refers to the issue of being able to learn a latent representation that uniquely corresponds to the true underlying latent representation used in the data generation process. Some recent works aim to reduce the space of indeterminacies of the learned representations, and thus achieve identifiability, by incorporating various assumptions into their models. Xi et al. [24] categorise these assumptions for generative the distribution of the latent variables and constraints the generator
models into constraints function. Some of their categories include non-Gause non-Gaussianity of the latent distribution
(20), dependence on auxiliary variable [9 10), of multiple views [16], use of interventions [1]], of
mechanism sparsity [4], and restrictions on the Jacobian of the generator (6). In contrast, in our
work we achieve identifiability by making our network equivariant translations, imposing an
interpretable latent space structure, and requiring the data to obey our theorem's 's assumptions.
Method
In this section describe the proposed method for unsupervised object detection with guarantees. On a high level, our architecture is based on an autoencoder that is fully cquivariant to translations, which we achieve by making the encoder consist of CNN followed by soft argmax function to extract object positions, and making the decoder consist of a Gaussian rendering function followed by another CNN to reconstruct image from the object positions (fig. Tp. In the following sections we describe the different parts of the architecture detail.
Autoencoder with CNN Encoder and Decoder. We start with an autoencoder, standard unsuper- vised representation leamnigg model, consisting of an encoder network té that maps an image x to a low-dimensional latent variable z, followed by decoder network é that maps this variable back to an image é, with the objective of minimising the difference between and á. Typically, the encoder and decoder networks are parametrised by multi-layer perceptrons (MIPs) or convolutional neural networks (CNNs) paired with fully-connected (FC) layers, however neither of these parametrisations

---

Input Image
Embedding Maps
Latent Variables
Rendered Gaussians
Predicted Image
CNN
Soft Argmaa
Render Gaussians
21x Z1y
Φ
Ze,xi Znny
X
C1 -.. Cn
En
X
Reconstruction Loss
Positional Encodings
NW
x(,,x)
Figure 1: Network architecture. Encoder: (1) an image x is passed through a CNN 1 to obtain n embedding maps C1,-..; C22 (2) a maximum of each map is found using softargmax to obtain latent variables [21,a, 21, Zn,z, 2n. Decoder: (1) Gaussians é én are rendered at the positions given by the latent variables, (2) the Gaussian maps are concatenated with positional encodings and
passed through a CNN Φ to obtain the predicted image 2. Finally, x and & are used to compute reconstruction loss I.)
by default can guarantee that the learned latent variables will correspond to the true object positions (because of the universal approximation ability of MLPs and FC layers ()). To obtain such guar- antees, we would thus like to modify the autoencoder to make it exactly translationally equivariant, that is, shift of an object the input image x should correspond to a proportional shift of the latent variable 2, and shift of the latent variable should correspond to shift in the predicted image å.
We start with an autoencoder where the encoder and decoder are both CNNs. CNNs consist of layers computing the convolution between a feature map and filter F, defined in one dimension as
(x * F) Σ, xbj]F[i-- -
Intuitively, this corresponds to sliding the filter F across the feature map x and each position of the filter computing the dot product between the feature map x and the filter F. We can prove that convolutional layers equivariant translations, since
((T o x) F) = Σ xأء F[F - 1] = Σ +[iFF - (1-t)) = ro F)
(2)
where 7 is the translation operator that translates a feature map by t pixels, and we have used the substitution + j f the second equality. Therefore, the encoder and decoder are both equivariant to translations, but this property only holds for translations of feature maps (i.e. spatial tensors).
From Encoder Feature Maps to Latent Variables. So far we have only worked with images and feature maps, but the latter do not directly express positions of any detected objects. It would be preferable to convert these feature maps into sealar variables that can be interpreted as object positions that are equivariant to image translations. To do this, we first define translation of a (1D) feature map x and translation 7' of a scalar z as
[x)
zzii t). 7(()) = 2 +
where is the position in the feature map x. 7 shifts an image by pixels, and 7' shifts a scalar by t units. To relate translations in feature maps to translations in latent variables, that computes a scalar property of a feature map x, such as argmax, defined as argmax(x) = {i x[i]] < x[i] Vj}. Using these definitions shifting the feature map x by corresponds to shifting the latent variable argmax(x) by r':
function
prove the equivariance of argmax, i.e. that
argmax(7 x) (i To < r a[i Vj} {i : æij 1] S x t] Vj}
(i +i+t:afj < x11 Vj} argmax(x)
====-a argmax(x)
(4)
where at the first equality we use the definition of argmax, at the second equality we use the definition of (eq. 3 left), the third equality we use the substitution i - i + f, the fourth equality the definition of argmax, and at the last equality we use the definition of 7' (eq. 3 right).
However, because the argmax operation is not differentiable, for neural network training approxi- mate via differentiable soft argmax function, defined in 2D as
T-1J=1 ΣΣ
1 (122
softargmax(x)
i
a
[i
j
02
[i:]]]
(5)
e
J
2
1=0 1=
3

---

where o is the softmax function defined in one dimension as [xx){1] = exp(=/i)) Σ, exp(x<i]).
(2) and (2(x) is the softmax function evaluated along the first and second dimensions of z, θ is temperature hyperparameter, [ is the image index, is the image width, J is the image height, and the term 1/2 ensures that the densities correspond to pixel centres. As the temperature O in eq. approaches zero, softargmax reduces to the classical argmax function.
From Latent Variables Decoder Feature Maps. Similar to mapping from encoder feature maps to latent variables, we would now like to relate shifts in latent variables z to shifts of decoder feature maps z. To do this, we can invert the action of the argmax operation. Because argmax is a many-to one function, finding an exact inverse is not possible, but we can obtain a pseudo-inverse using the Dirac delta function defined as delta(z) of argmax because argmax o delta. argmax function, we can prove that the delta function is equivariant to the latent variable shift 7 on the input and the feature map shift r on the output, i.e.
5(i 2). We can show that delta a pseudo-inverse i: ő(j =) I 5(i - 2) Vj = 2. Now, similar to the
(6) where at the first equality we have used the definition of delta, at the second equality we have used the definition of 7' (eq. 3 right), at the third equality we have used the definition of delta, and at the last equality we have used the definition of 7 (eq. left).
delta(r's o = = 8(i - 7' a 2) 8(i - 1) = delta(=){ - 1 = delta(=)[(
Again, because the delta function is not differeentable, we can approximate using a differentiable render function as
render (z) = (i 2,
(7)
where Mii - 2, 2²) is a Gaussian evaluated at - = with variance given by the hyperparameter o². As the variance 2² in eq. approaches zero, the render function reduces to the hard delta function.
Additionally, because the decoder is translationally equivariant, we also condition on positional encodings of the size of the images to provide it with sufficient information to reconstruct different parts of the background, assuming the background statie. Alternatively, if background is varying, saaooolel-s nearby video frame instead, which will
the decoder can be conditioned on provide information about the background but not the objects' positions (following Jakab et al.
We also note that since the latent variables & are ordered, this allows the encoder and decoder to learn to associate each variable with the semantics of each object and achieve successful reconstruction.
We thus now have all the elements we need to create an equivariant architecture where the encoder and decoder are defined, respectively, by
2 = softargmax o s/ o x, ft = Φ o render o 24-
(8)
This is shown in fig. | Having designed an exactly translationally equivariant architecture now allows us to obtain theoretical guarantees about the learned latent variables, which we discuss next.
4 Theoretical Results
In this section we present our main theorem stating the maximum bound on the position errors of the latent variables learned with our method terms of the encoder and decoder receptive field sizes, the object size, and the Gaussian standard deviation (thm. I. We continue by deriving specialised corollaries relating the maximum position error to the encoder receptive field size (cor. 4.2) decoder
receptive field size (cor. 4.3) object size (cor. 4.4), and Gaussian standard deviation (cor. 4.5)
Theorem 4.1. Error Bound. Consider a set of images d with receptive field size sg. CNN decoder & with receptive field size $6. soft argmax function softargmax, rendering function render with Gaussian standard deviation OG and AG ~ (0 o² and latent variables composed z softargmax v T and i Φ render c (fig. [ Assuming (1) the objects are reconstructed at the same positions as in the original images, (2) each object appears in at least two different positions in the dataset, and (3) there are no two identical objects in any image, then the learned latent variables z correspond to the true object positions up to object permutations and maximum position errors A of
X with objects of size So, CNN encoder
A min 8/
S6
So
+AG)
We note that a similar architecture was proposed by Jakab et al. [1. with empirical success in keypoint detection. However, we derive our architecture by enforcing strict translation equivariance properties, which makes theoretical results possible.

---

Decoder
Encoder
Object
2
Object
2
ZGT Z
5
ZGT
2
(a) Encoder Error
(b) Decoder Error
Figure 2: Position errors. (a) Maximum position error due to encoder, given by s + s,/2 The maximum error occurs when the encoder and the object are far away from each other as possible while still overlapping by one pixel. (b) Maximum position error due to decoder, given by s2/2 8,/2 + Ag. The maximum error occurs when some part of the Gaussian at position = Ag is within the decoder receptive field (RF) but is as far away from the rendered object as possible.
For proof see appendix A Intuitively, the assumptions ensure that each latent variable corresponds to the position of each object in the image. The error in the learned object positions then arises from both the encoding and decoding process. the encoding process, the maximum error occurs when the encoder and the object are far away from each other possible while still overlapping, i.e. su/2 + s - 1 (fig. 2ab. Conversely, in the decoding process, the maximum error occurs when the rendered object and the latent variable are far away from each other possible while both still being inside the decoder receptive field, i.e. 86 8 (fig. 2b). Additionally, there is an extra error of Ag as the latent variable is rendered by Gaussian and the decoder can capture any part of this Gaussian. Finally, because we assume each object is reconstructed at the same position as in the original image, the errors from the encoder and decoder must cancel each other out. Therefore, the overall maximum position error is given by the lower of the two expressions for the encoder and the decoder, leading eq. Next, we present corollaries relating this error bound to different factors.
Corollary 4.2. Error Bound vs. Encoder RF Size. The maximum position error a function of the encoder receptive field (RF) size Se for a given Se, So, OG. is
80
if 1 S 28o + 2, AG if 8 5 28, 2.
(ss))
2
40
For an illustration see fig. 3a There are two regions of the curve (separated by a dashed line). In
the left-most region, Sy Se 2s, + 2. the error is dominated by the encoder error, and in the
right-most region, 8 2 8 2s, + 2, the error is dominated by the decoder error. Initially, for
Sy = 1, the error is given by s./2 1/2, because the x 1 px encoder can match any pixel that is part of the object and so can be at most half of the object size away from the true object position that the centre of the object. As the encoder RF size increases up S 2s, + the position error increases linearly with it as /2/2 + so/2 - 1, because now any part of the encoder RF can match any part of the object (fig. 2a) This bound is deterministic due to the deterministic encoding process.
At sg = 5o - 2s, + (vertical dashed line in fig. 3a the maximum errors from encoder and decoder both become equal to /2 so/2. For su 8. 2s. + 2, the position error is dominated by the error from the decoder which is constant at 8 so 2 + Ag with Ag NN00, og), and so even though the encoder RF size is increasing, this has no effect as the limiting factor is now the decoder. Due to the Gaussian rendering step in the decoding process, this bound is now probabilistic, and distributed normally with variance o²x The results of corollary 4.2 can be extended to multiple
objects with different sizes (see appendix B cor. B.1)
Corollary 4.3. Error Bound vs. Decoder RF Size. The maximum position error as a function of the decoder receptive field (RF) size s6 for a given 8ig, S TG, is
+ AG if So < 36
< S6) + +so 2,
(
if
80 86 + 2s,- - 2.
For an illustration see fig. 3b Similar to corollary 4.2 there are two regions of the curve, one
for 86 < 83 + 2s, 2 (left), where the emror is dominated by the decoder error, and another for
86 2 K8t + 2s, 2 (right), where the error is dominated by the encoder error. Note that this
opposite to cor.
4.2 Initially, for s so. the decoder receptive field has the same size the object,
5

---

Paacon (pp
Po Portion Emorr & (po)
Poonton Ernor (od
4
25, +-2
5o. Sy 25g -
1
4/
Encodor RF Sibe 1961
Decoder RF Size (PA)
Object Size S. 1000
Caussian S.D. (pX)
(a) Error vs. Encoder RF. (b) Error vs. Decoder RF.
(c) Error vs. Object Size.
(d) Error vS. Gaussian S.D.
Figure 3: Theoretical bounds for the maximum position error function of the encoder receptive field size sy, decoder receptive field size Se, object size So. and Gaussian standard deviation oG, as the remaining factors are fixed. Each bound consists of region due to the encoder error (solid line) and the decoder error (probabilistic bound). Standard deviations are represented by shades of blue.
and so to achieve perfect reconstruction it needs to be at the same position as the object, resulting in O position error plus any error Ag caused by the non-zero width of the Gaussian. As the decoder RF size increases up to S + 28. 2, the position error increases linearly with it as 52/2- - 8o/2 2 2 Ag. because now the object can be an increasing number of positions within the decoder and still achieve perfect reconstructions (fig. (b). At 86 86 + 28, - 2, the maximum errors from encoder and decoder both become equal to 5// so/2 1. For sø 5.) + 2s, 2. the position error is dominated by the error from the encoder which is constant at / + s. 2 1, and so even though the decoder RF size increasing, this has no effect as the limiting factor now the encoder. Similar to corollary 4.2, the results of corollary 4.3 can be extended to objects with multiple different sizes (see appendıx B cor. [B.2].
Corollary 4.4. Error Bound Object Size, The maximum position error a function of the object size so for a given Sy, Sd. OG, is
if
1 8, < 66 82 +
86 + 1, 2
Ass
2
AG
if
80
S 84.
For an illustration see fig. 3c Again, there are two regions of the curve, one for 80 82/2 8 /2+ (left), where the error is dominated by the encoder error, and one for 2 88/2 /2/2 (right), where the error is dominated by the decoder error. Initially, for s, = 1, the error is given by s2/2 1/2, because any pixel of the encoder receptive field can match the 1 x px object and so the error can be at most half the encoder receptive field size. As the object size increases up because now
to /2 / + 1, the position error increases linearly with it s / s any part of the encoder RF can match any part of the object (fig. 2a At 8, = s2/2 s//2 /2- + 1, the maximum eπrors from encoder and decoder both become equal / s 1/2. For 8, > s /2/2+ 1. the position error is dominated by the error from the decoder and decreases linearly 82/2 8o/2 + Ag, because
there is decreasing number of positions where the object can still fit inside the decoder receptive field (fig. 2b) At 8, = 8g. the object reaches the same size the decoder, and thus the position decreases to 0 with additional error due the width of the Gaussian, Ac. Interestingly, the triangular shape of the error curve means that small and large objects will both incur small position errors, while medium sized objects will incur higher errors.
Corollary 4.5. Error Bound vs. Gaussian Size. The maximum position error as a function of the Gaussian standard deviation ag for a given Sug, 8gg So, is
8u
Ag
if GG
<
8g
86
+ So -1,
( =
2
2
2 oG
OG
56
2
86
+ + -
For an illustration see fig. 3d Firstly, there is an overall maximum bound for the position error due to the encoder, given by the constant / so/2- 12211 1. which is independent of the Gaussian standard deviation. Then, initially for OG = 0, the rendered Gaussian effectively delta function, and so the position error is dominated by the decoder error given by sa/2 so 2,, which describes the maximum distance between the object and the delta function with both of them fitting inside the decoder receptive field (fig. 3bp. As the Gaussian standard deviation increases, the position error increases linearly as / 8 + Ag with AG ~ ()) Then, depending on what part of the Gaussian the decoder is convolved with, there different bounds for the maximum

---

Theoretical Bound
Experimental Data
8-
Post Encr (00)
Post Encr (H0
Pouesin Erte
Poston
4
0-
13
Encodor RF Sizc Sy (80)
Occodor RF Sizz Sq (D00
Objest S2z 1657
Geucdian S.D. du (px)
(a) Error vs. Encoder RF (b) Error vs. Decoder RF.
(c) Error vs. Object Size.
(d) Error vs. Gaussian S.D.
Figure 4: Synthetic experiment results showing position error as function of the encoder receptive field size Sg, decoder receptive field size Se, object size So, and Gaussian standard deviation og. as the remaining factors are fixed Sy 9, 25, 8, = 9, og 0.8 (in a,b,c) or to Sy 9, s 11, so = 7 (in d). Theoretical bounds are denoted by a blue line (with 4 shaded regions denoting to 4 standard deviations of the probabilistic bound) and experimental results by red dots.
position error. If the decoder is convolved with a part of the Gaussian that is within n standard deviations of its centre, the maximum position error increases linearly s2/2 8./2 + nog up to aG = (s./2 - s 2 + 5, 1)/n, after which point the position error becomes dominated by the encoder value of sw/2 2 + s. 2 --1 In fig. 33d the maximum position error bound when the decoder is convolved with a part of the Gaussian within its first and second standard deviations, is denoted by darker and lighter shades of blue, respectively.
Experimental Results
In this section we validate our theoretical results synthetic experiments (sec. 5.1) and CLEVR data (sec. (.2). Additional real video experiments are in app. E We first validate corollaries 4.2 4.4 via synthetic experiments in sec. [5.1 demonstrating very high agreement up sizes of individual pixels. We then apply our method to CLEVR-based [12] data containing multiple objects of different sizes in varying scenes (sec. (.2) and show that compared to current SOTA object detection methods
(SAM 13
CutLER 23 ), only our method predicts positions within theoretical bounds.
5.1 Synthetic Experiments
In this section we validate corollaries 4.2 4.5 via synthetic experiments. Our dataset consists of a small white square on black background. In each experiment we fix all but one of the encoder RF size 8g. decoder RF size 8g, object size 8,, and Gaussian standard deviation dg. and vary the remaining variable. We perform each experiment 20 times, corresponding to 20 random initializations of the trained parameters, and record the position error as the difference between the predicted object position and the ground truth object position zgr- For more details see appendix C.I
Position Error vs. Encoder RF Size. In this experiment we aim to empirically validate corollary by measuring the experimental position errors function of the encoder receptive field size. We vary the encoder RF sizes Sy E errors A. We visualise the data points (red) and the theoretical bounds (blue) in fig. 4a We can observe that all the data points lie at or below the theoretical boundary, which validates corollary 4.2 In particular, we observe that the deterministic boundary in the region the left of the dashed line (corresponding to the encoder bound) is well respected, with some of the trained networks achieving exactly the maximum error predicted by theory.
31} and fix Sø 25, 8 = 9, GG = _8 and record position
Position Error vs. Decoder RF Size. In this experiment we aim to validate corollary 4.3 by measuring the experimental position errors as a function of the decoder receptive field size. We vary the decoder RF sizes $o E f1, 3.... ............... and fix s 9, s. = 9. Og = .8 and record position errors A. We visualise the results in fig. 4b The figure shows the theory to be a strong fit to the data, validating corollary 4.3 In particular, we note that the data points fit the Gaussian distribution in the decoder part of the curve (left of the dashed line) and are very close to (1 px below) the deterministic upper bound in the encoder part of the curve (right).
7

---

Theoretical Bound
Experimental Data
Baseline (SAM)
Baseline (CutLER)
Positon Frree (o0
Poskon Liter (ox)
post or End (PC)
Post Encr (p0)
20
Encosor RF Sicc (pX)
Dccodor RF Size Qp00
Object Size (ax)
Gaussian S.D. 19x1
(a) Error vs. Encoder RE (b) Error vs. Decoder RF. (c) Error vs. Object Size.
(d) Error vs. Gaussian S.D.
Figure 5: CLEVR experiment results showing position error as a function of the encoder receptive
field size ss, decoder receptive field size sΦ, and object size So. and Gaussian standard deviation OG. as the remaining factors are fixed to Sy 9, S9 25, 8, E [6. 10]. og 0.8 for (a)-(c) and to
So = 5, sg = 13. So E [6, 10] for (d). Theoretical bounds are denoted by blue, experimental results in red, SAM baseline in green, and CutLER baseline in orange.
Position Error vs. Object Size. In this experiment we aim to validate corollary 4.4 by measuring the experimental position errors
function of the object size. We vary the object sizes s, (1.3.... } and fix 82 = 9, 8g = 25, ag = .8 and record position errors A. We visualise the results in fig. Acc As all the data points lie or below the theoretical boundary, this validates corollary [4.] We note that the empirical distribution of errors follows very closely the shape of the theoretical bound, very strictly on the left side of the dashed line (encoder bound) and according to the distribution predicted on the right side (decoder bound).
Position Error vs. Gaussian Size. In this experiment we aim to validate corollary 4.5 by measuring the experimental position errors as a function of the Gaussian standard deviation. We vary the Gaussian standard deviations og E 0.2, ..... 2.1, 2.25,
5). fixing sy 9,
11,
7 and record position errors A. We visualise the data points (red) and the theoretical bounds (blue) in fig. 4d As all the data points lie at or below the theoretical boundary, this validates corollary 4.5 In particular, we note that all the data points lie below the encoder bound (solid blue line), and all the data points lie within the bound denoted by four standard deviations away from the Gaussian. This means that in practice, the decoder can be convolved with any part of the Gaussian that lies within 4 standard deviations (corresponding to 3.2 px) from its centre. We also note that as the Gaussian standard deviation increases, the position error increases as expected, denoted by the positive slope of the data points between the third and fourth standard deviations (lightest shade of blue).
5.2 CLEVR Experiments
In this section validate our theory on CLEVR-based 12 image data of 3D scenes. Our dataset consists of spheres of different colours at random positions, with a range of sizes due to perspective distortion. We train and evaluate each experiment similarly to those in sec. 5. recording position
errors for the learned objects, and compare our results with SAM [13 and Cutl LIREERR (23 baselines.
We compute the theoretical bounds according to our theory in sec. 4 and app. B and visualise the
results in figs. 5a 5c
For details see app. C.2 For experiments with different shapes see app. D
Once again, the experimental results demonstrate high agreement with theory, complex images with multiple objects and a range of object sizes (fig. 5 red, blue). Furthermore, while the SAM and CutLER basclines generally achieve low position errors, this is not guaranteed, and in some cases their errors are much higher than our bound (fig. S green, orange). We report the proportion of position errors from fig. 5c that lie within 2 standard deviations of our theoretical bound in table (6b and fig. [6a] showing that compared to SOTA object detection methods, only for our method are the position errors always guaranteed to be within our theoretical bound.
even for more
6 Discussion
In light of our theoretical results, in this section we present some conclusions that can be drawn when designing new unsupervised object detection methods:
8

---

OULLER
100
ErTors Within Bound (%)
80
Object Size + 1.5 (px)
60
Method
All
9
12
15
18
21
40
Ours
100.0
100.0
100.0
100.0
100.0
100.0
100.0
20
CutLER
78.4
100.0
100.0
75.0
57.1
83.3
37.5
SAM
43.5
83.3
60.0
54.5
23.1
0.0
16.7
12
15
19
21
24
Object
1p00
(a) Results visualisation.
(b) Results table.
Figure 6: Proportion of position errors within 2 standard deviations of the theoretical bound (%), reported for different object sizes and methods. Results from table (b) are visualised in plot (a).
1. If the size of the objects that will be detected is known, to minimise the error on the learned object positions, one should aim to design the decoder receptive field size to be as small as possible while still encompassing the object. As the decoder RF grows beyond the object size, the error bound increases linearly with it up to a certain point (fig. 3b).
2. To minimise the error stemming from the encoder for a given object size, the encoder RF size should be kept as small as possible while still detecting the object (the RF size may be smaller than the object size), as again the error bound grows linearly with it up to certain point (fig, [a).
3. To minimise the error, the width of the rendering Gaussian should be kept small possible while still permitting gradient flow, as increasing it even slightly may result in a dramatic increase the decoder term of the position error (fig. 3d). This is because, in practice, the decoder is able to detect parts of the Gaussian that are even 4 standard deviations away from its centre (fig. [4d].
4. In the case that does not know priori the exact size of the objects to be detected, one can still design a network that minimises the position errors for a given range of sizes. In that case, one should set up the decoder RF size to be close possible to the size of the largest object, and keep the encoder RF size as small as possible while still detecting all objects. The position errors for different object sizes will then be distributed according the curve in fig. [3c where the smallest and largest objects will achieve lowest errors and medium- size objects will achieve the greatest error, approximately given by a half of the average of the encoder and decoder RF sizes.
Finally, we discuss some limitations of our method. Firstly, the method can only detect dynamic objects, for example they move in vidco or if they appear at multiple locations in images. Secondly, in its current form the method learns representations that can not be used for vidcos with different backgrounds than the one used at training time; however, this can be overcome by conditioning the decoder unrelated video frame instead of the positional encodings, as in Jakab et al. [.]. Thirdly, the guarantees our method are conditional on the images being successfully reconstructed, which depends on the network architecture and optimisation method.
7 Conclusion
We have presented the first unsupervised object detection method that is provably guaranteed to recover the true object positions up small shifts. We proved that the object positions are learned up to a maximum error related to the encoder and decoder receptive field sizes, the object sizes, and bandwidth of the Gaussians used to render the objects. We derived expressions for how the position error depends on each of these factors and performed synthetic experiments that validated our theory up sizes of individual pixels. We then performed experiments on CLEVR-based data, showing that unlike current SOTA methods, the position errors our method are always guaranteed to be within our theoretical bounds. We hope our work will provide starting point for more research into object detection methods that possess theoretical guarantees, which are lacking in current practice.
The authors acknowledge the generous support of the Royal Academy of Engineering (RF920181918811)) the Royal Society (RGIR11241385) and EPSRC (VisualAT, EP/T028572/1).
Acknowledgements.

---

References
[1] Johann Brehmer, Pim De Haan, Phillip Lippe, and Taco Cohen. Weakly supervised causal representation learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[2] Christopher P. Burgess, Loic Matthey, Nicholas Watters, Rishabh Kabra, Irina Higgins, Matt Botvinick, and Alexander Lerchner. Monet: Unsupervised scene decomposition and representa- tion, 2019.
[3] Abdelkader Dairi, Fouzi Harrou, Mohamed Senouci, and Ying Sun. Unsupervised obsta- cle detection in driving environments using deep-learning-base based stereovision. Robotics and Autonomous Systems, 100:287-301, 2018.
[4] Eran Goldman, Roei Herzig, Aviv Eisenschtat, Jacob Goldberger, and Tal Hassner. Precise detection in densely packed scenes. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5227-5236, 2019.
[5] Klaus Greff, Raphaël Lopez Kaufman, Rishabh Kabra, Nick Watters, Christopher Burgess, Daniel Zoran, Loic Matthey, Matthew Botvinick, and Alexander Lerchner. Multi-object repre- sentation learning with iterative variational inference. In International conference on machine learning, pages 2424-2433. PMLR, 2019.
[6] Luigi Gresele, Julius von Kügelgenn Vincent Stimper, Bernhard Schölkopf, and Michel Besserve. Independent mechanism analysis, a new concept? In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 28233-28248. Curran Associates, Inc., 2021.
[7] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. Proceedings of the IEEE international conference on computer vision, pages 2961-2969, 2017.
[8] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural networks, 2(5):359-366, 1989.
[9] Aapo Hyvarinen and Hiroshi Morioka. Unsupervised feature extraction by contrasste learning and nonlinear ica. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016
[10] Aapo Hyvarinen and Hiroshi Morioka. Nonlinear ICA of Temporally Dependent Stationary Sources. In Aarti Singh and Jemry Zhu, editors, Proceedings of the 20th International Confer- ence on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 460-469. PMLR, 20-22 Apr 2017.
[11] Tomas Jakab, Ankush Gupta, Hakan Bilen, and Andrea Vedaldi. Unsupervised learning of ob- ject landmarks through conditional image generation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, Cesa-Bianchi, and Garnett, editors, Advances in Neural Information Pro- cessing Systems, volume 31. Curran Associates, Inc., 2018.
[12] Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2901-2910, 2017.
[13] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yer Lo, et al. Segment anything. In Proceedings of the JEFF/CVF International Conference on Computer Vision, pages 4015-4026, 2023.
[14) Sebastien Lachapelle, Pau Rodriguez, Yash Sharma, Katie E Everett, Rémi LE PRIOL, Alexan- dre Lacoste, and Simon Lacoste-Julien. Disentanglement via mechanism sparsity regularization: new principle for nonlinear ICA. In First Conference on Causal Learning and Reasoning, 2022.
10

---

[15] Phillip Lippe, Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Stratis Gavves. CITRIS: Causal identifiability from temporal intervened sequences. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 13557-13603, PMLR, 17-23 Jul 2022.
[16] Francesco Locatello, Ben Poole, Gunnar Ractsch, Bernhard Schölkopf, Olivier Bachem, and Michael Tschannen. Weakly-supervised disentanglement without compromises. In Hal Daumé IIII and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6348-63888 6359. PMLR, 13-18 Jul 2020.
[17] Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf. Object-centric learning with slot attention. Advances neural information processing systems, 33:11525-11536 2020.
[18) Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical image computing and computer-assisted intervention-MICCAA. 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pages 234-241. Springer, 2015.
[19] Thomas Schlegl, Philipp Seeböck, Sebastian M Waldstein, Ursula Schmidt-EEfurthh and Georg Langs. Unsupervised anomaly detection with generative adversarial networks to guide marker discovery. In International conference information processing in medical imaging, pages 156-157.50 Springer, 2017.
[20] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 20000,0003-2000, 2006.
[21] Oriane Siméoni, Chloé Sekkat, Gilles Puy, Antonín Vobecký, Éloi Zablocki, and Patrick Pérez. Unsupervised object localization: Observing the background to discover objects. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pages 3176-3186. 2023.
[22] Oriane Siméoni, Éloi Zablocki, Spyros Gidaris, Gilles Puy, and Patrick Pérez. Unsupervised object localization in the of self-supervised vits: A survey. International Journal of Computer Vision, pages 1-28, 2024.
[23] Xudong Wang, Rohit Girdhar, Stella X Yu, and Ishan Misra. Cut and learn for unsupervised object detection and instance segmentation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3124-3134, 2023.
[24] Quanhan Xi and Benjamin Bloem-Reddy, Indeterminacy in generative models: Characterization and strong identifiability. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Leurning Research, pages 6912-6939. PMLR, 25-27 Apr 2023.

---

A Proof of Theorem 4.1
Theorem Maximum Position Error. Consider set of images x X with objects of size So, CNN encoder v with receptive field size Sg. CNN decoder & with receptive field size sg, soft argmax function softargmax, rendering function render with Gaussian standard deviation og and Ag ~ (0, and latent variables 2, composed as softargmax o o z and 2 = & render oz (fig. D. Assuming (1) the objects are reconstructed at the same positions as in the original images, (2) each object appears in at least two different positions in the dataset, and (3) there are no two identical objects any image, then the learned latent variables correspond to the true object positions up to object permutations and maximum position errors A of
88 2
80
1 86
80 + Ao) 2
A min
+
(10)
2
2
Proof. By assumption (1), the positions (z1, 22) objects in the original image x have to be the same the positions (21, 22) of the objects in the reconstructed image ž. In practice, this occurs whenever the reconstruction loss is minimised.
By assumption (2) (each object appears at minimum of 2 different positions), the latent variables used by the decoder have to contain some information about each object, and thus the encoder has to learn to match all the objects. This is because the decoder CNN & takes as its input the rendered Gaussians = renderoz z concatenated with positional encodings or a randomly sampled nearby frame (fig. D. and if some object in the dataset only appeared at a single position the model could achieve perfect reconstruction solely by using the positional encodings or the conditioned image without having to use the Gaussian maps é. However, because the dataset contains each object at minimum of 2 positions, relying purely on positional encodings or on the conditioned image is now not sufficient, as without any information about the object passed to the decoder, it would be impossible for it to predict where to render the object. More formally, because c = & o render o softargmax o 1f a,, this means that for objects in be reconstructed the same positions in å (assumption 1), the encoder & needs to match some part of each object in æ.
Because softargmax o is equivariant to translations of x (sec. 3 and because the encoder & has to match some part of each object in x (as shown previously), and also each image consists of distinct objects (assumption 3) on a known background, the image æ with an object at the position (u1, U2) is encoded by softargmax o z to the latent variables
(z1, z2) (u Apt; u2 + A22),
A 12
S6
8o
(11)
2
where the shifts A&t and A 22 arise because any part of the encoder filter (of size 8v) can match any part of the object (of size 8,). See fig. 2a for an illustration.
Next, because & = ø a render 2 is equivariant to translations of (sec. 3 the latent variables
2 (ui + Av1, u2 A22) are mapped to predicted image & = á render o z with an object at position
(81,22) (w1 + A41 + AøI, U2 + A82 + A92),
A A221
S
86
8a
AG
(12)
2
2
where the shifts Aet and As2 arise because any part of the decoder filter (of size 8&) can match any part of the the rendered Gaussian é render where Ag ~ (N oz). See fig. 2b for illustration.
Finally, by assumption (1), the position of each object in the original image æ has to be equal to the position of the object in the reconstructed image, i...
(u, u2) = (ui + Asi + AsI, u2 + Aw2 + As2)
(13)
This results in the conditions
Ap1 + Ao1 = 0,
Ag2 + A 62 0
(14)
and therefore
A = A
A = A
(15)
In words, the shift in the latent variables acquired from the encoder AS has to be balanced by an opposite shift of the same magnitude in the decoder Ag in order to reconstruct the object at the
12

---

same position. Because the shift due to the encoder is of maximum magnitude of se. s so/2 1 and the shift due to the decoder has a maximum magnitude of sa/2 s,/2 Ag. this means that the maximum magnitude of the shift of the latent variables has to be the minimum of these two expressions, i.e. the learned latent variables (21, #2) correspond to the ground truth latent variables (u1, u2) up to
(z1, 22) = (n) + 11, u2 + A2), | - min
-/4 2
8v
+
80 -
36 2
80
+
Aa).
(16)
2
Additionally, because the order in which the objects get mapped to each latent variable is arbitrary. there is an additional indeterminacy arising due to variable permutations.
B Theoretical Results for Multiple Object Sizes
The results of corollary 4.2 can be extended to objects with a range of different sizes. The bound can be obtained by taking the maximum over all the bounds for objects with sizes 8o psp. leading to the following corollary.
mox" 8
Corollary B.1. Error vs. Encoder RF Size for Multiple Object Sizes. The maximum position error function of the encoder receptive field (RF) size Sip for a given Se, 8o E Ismin So gmaz) OG.
if 1 S 82 S 5 22 +
2
(8$)) =
+ AG
s6 25
+ Sv S 86
25 + 2,
4
8c
+
Ag
s6 > 88 2262 + 2.
2
2
For an illustration see fig.
7a
Similar to corollary 4.2
the results of corollary 4.3 can be extended to objects with a range of different
sizes by taking the maximum over the bounds for objects with sizes so E [smann ,88 maa) leading to the following corollary.
Corollary B.2. Error vs. Decoder RF Size for Multiple Object Sizes. The maximum position error a function of the decoder receptive field (RF) size s6 for given sy, So E [s , maa) GG. is
88
8
min
+
AG
if %
< 86 S 86 + 28 2,
2
2
(ss))
86
A
if Sw 2s
86 I s6 ma - 2
mex
if s6 > + 25 2.
2
For an illustration see fig. 7b
2s
+
25
Pocition Firor [px]
Position Errar (o0c)
2
2
2-
2
2
1
56"
2m
ag 5y 2u
Encoder (px]
Decader Size sy (px)
(a) Position error vs. encoder RF size for range of object
(b) Position error vs. decoder RF size for range of object sizes.
sizes.
Figure 7: Theoretical bounds for the maximum position eтror function of the encoder receptive field size su and the decoder receptive field size Sy for objects sizes ranging from smi to s taa as the remaining factors are kept constant. Each theoretical bound consists of two regions separated by dashed line. one where the maximum error is due to the encoder (deterministie, represented by solid line), and one where the maximum error is due to the decoder (probabilistic, represented by a solid line and shaded regions). Areas within one and two standard deviations of the mean are represented by a darker and lighter shades of blue respectively.
13

---

Experiment Training Details
C.1 Synthetic Experiments
Dataset. In all of the synthetic experiments, we use the following setup. The dataset consists of black images of size Sing 8ing = 80 80 px, each with a white square with dimensions so 8o px, centered at positions (x, y) where æ, E {xpad + 8 Spad + 8 1,..., -img Spod 6 /2/ where Spad max s&) (to prevent unwanted edge effects). We divide the dataset into quadrants and assign images from 3 quadrants to the training set and the remaining quadrant to the test set.
Evaluation. For each experiment, we fix all but one variable from the following set: encoder RF size Sy, decoder RF size Sg, object size S., and Gaussian standard deviation og, and vary the remaining variable. For each value of the investigated variable we perform 20 experiments with different random seeds, noting down the learned position error A the absolute difference between the learned position and the centre of the object &GT (maximum over horizontal and vertical differences, and over the test set). We discard result if the reconstruction accuracy the run is below 99.9%, to only consider runs where the object has been detected successfully (this is because the square is on the order of? 7 x px, thus only comprising 0.8% of the image).
Architecture. We parametrise both the encoder ab and the decoder á as 5-layer CNNs with Batch Normalisation and ReLU activations, 32 channels, and filter sizes {1 1, 3, 5, x 7}, such that their receptive field sizes equal 8 and 86 respectively. We train each network for 500 epochs using the Adam optimiser with learning rate 10 and batch size 128. We train each experiment on single GPU for around hours with <6GB memory on an internal cluster.
C.2 CLEVR Experiments
Dataset. Our CLEVR experiments use data generated with the CLEVR 12 image generation script. Our training and test sets consist of 150 and 50 images respectively, containing red, green and blue metallic spheres on a random background, at random positions, and with a different range of sizes For experiments measuring position eтrоr as function of encoder and decoder RF sizes and Gaussian s.d., we use dataset with object sizes between 6- 10 px after perspective distortion (fig. Sa).
(fig. ().
For the experiment measuring position error as a function of object size, we use 5 datasets with object
sizes 9-14 px, 11-17 px, 13-19 px, 15-24 px, 17-27 px after perspective distortion (figs. 8b 8c
(a) Object sizes 6-10 px.
(b) Object sizes 9-14 px.
(c) Object sizes 17-27 px.
Figure 8: Samples from our CLEVR datasets, with object sizes (a) 6-10 px, (b) 9-14 px, (c) 17-27 px.
Evaluation. For each experiment, fix all but variable from the following set: encoder RF size decoder RF size 8g. object size 8,, and Gaussian standard deviation og. and vary the remaining variable. For each value of the investigated variable we perform experiments with different random seeds, noting down the learned position errors A as the absolute difference between the learned position of each object and the centre of the object zGT (maximum over horizontal and vertical differences and over the test set, for each object). We only consider results for objects that have been learned successfully. For experiments measuring position error function of encoder and decoder RF sizes and Gaussian s.d., we consider an object to be learned if the position error is less than px, and if only a single variable corresponds to the object, and if the position error is stable over consecutive training iterations. For the experiment measuring position error as function of object size, we only consider runs where all 3 objects have been learned, i.e. where the reconstruction accuracy is higher than 98.08 0% for the dataset with object sizes 6-10 px, 98.8% for dataset with sizes
14

---

11-17 px, 98.0% for dataset with sizes 13-19 px. 97.5% for dataset with sizes 15-24 px, and 98.0% for dataset with sizes 17-27 px.
Architecture. We parametrise both the encoder & and the decoder ó as 5-layer CNNs with Batch Normalisation and ReI.U activations, 32 channels, and filter sizes in (1 x 1,3 x 3, x 5, 7 x 7), such that their receptive field sizes equal 8y. and & respectively. We train each network until convergence using the Adam optimiser with learning rate 10-2 and batch size 128 for the experiments measuring position error as a function of encoder and decoder RF size and Gaussian s.d., and with learning rate 10-3 3 and batch size 150 for the experiment measuring position error function of object size. We train each model on a single GPU for less than day with <8GB memory on an internal cluster.
Baselines. We also evaluate the results for two State-oftthe-re Art baselines, SAM [13 and CutLER [23]. First, for each of our datasets (containing objects of sizes 6-10 px, .... 17-27 px), we combine its training and test set to create sets of 50 images each. We then apply SAM and CutLER to all images in each 50-image set, noting down the learned position errors A as the absolute difference between the predicted position z of each object and the centre of the object ²GT (maximum over horizontal and vertical differences and over the 50-image set, for each object). For SAM, we take the predicted object positions to be the centres of the bounding boxes corresponding to the second, third and fourth predicted masks (first mask corresponding to the background). For CutLER, we take the predicted object positions to be the centres of the predicted bounding boxes if the method predicts bounding boxes (one for each object), otherwise discard the prediction. For both methods, discard any result where position error is greater than 35 px, to be consistent with the evaluation for our method. Finally, this results in 12 position error values (3 objects 4 data splits), for each method and each of our datasets.
D CLEVR Experiments with Different Shapes
To demonstrate that our method applies to objects of any shape, in this section include experiments on our CLEVR dataset with three distinct objects - a red metallic sphere, a blue rubber cylinder and green rubber cube. The dataset has objects of size 9-19 px after perspective distortion, and a sample from the dataset is shown in fig. Da We perform training and evaluation in the same way as in app.
C.2 We plot the position error a function of the encoder and decoder receptive field sizes in figs. 9b Snb respectively. We can observe that all our experimental data (red) lies within the bounds predicted by our theory (blue), successfully validating our theory for objects with different shapes.
Theoretical Bound
Experimental Data
Baseline (SAM)
Baseline (CutLER)
10
12
10
Position A (px)
Position &
4-
Encoder Size Sp (px)
Decader RF Size Sq (px)
(a) Dataset Sample.
(b) Error vs. Encoder RF.
(c) Error vs. Decoder RF.
Figure 9: CLEVR experiment results using (a) a dataset with 3 objects of different shapes (a sphere, a cube, and cylinder), showing position error function of (b) the encoder receptive field size 8, and (c) decoder receptive field size 8s, as the remaining factors are fixed to 8, = 9, s 25, object size s, E [9, 19) and Gaussian s.d. ag 0.8. Theoretical bounds are denoted by blue, experimental results in red, SAM baseline in green, and CutLER bascline in orange.
15

---

E
Experiments with Real Videos
In this section present experimental results of applying method to real YouTube videos, including overhead traffic footage and mini pool game footage.
E.1 Traffic Data
In this experiment we aim to learn the position of car from an overhead traffic video. The training and test for this experiment consist 25 frames each, from a video of an overhead view of car moving for short distance in a single lane (fig. Toap. We train the architecture from fig, on this training set and validate it on the object positions and the learned object positions of 7.2 10-5 (in units normalised by the image size), demonstrating that the object position has been learned successfully with very low error. We then modify the learned position variable and decode it to generate videos of the car at novel positions (figs. 10b 10cl.
It achieves mean squared error between the ground truth
(a) Training data.
(b) Generated data (steady speed in different lane).
(c) Generated data (lane change and acceleration).
Figure 10: Road traffic video used for training, together with two videos generated after training by modifying and decoding the learned latent variables (video frames superimposed), The car object is detected successfully and is used to generate realistic videos with objects at unseen positions.
E.2
Mini Pool
In this experiment we aim learn the positions of balls from video of game of mini pool. The training and test sets for this experiment consist of 15 and I1 frames respectively from a video of game mini pool, cropped to a portion where two balls are moving at the same time (fig. Taa.. We train the architecture from fig. [ on this training set and validate it on the test set, where it achieves mean squared error between the ground truth object positions and the learned object positions of 8.2 10- (in normalised units). This demonstrates that the object positions were learned successfully with very low error. We then modify the learned position variables and decode them to generate videos of the balls at novel positions (figs. 11b 1lc
In practice, close to the size of the objects, as for larger RF sizes the position error increased unnecessarily and the images were rendered further away from the position given by the latent variables. Also, for large receptive field sizes, the decoder filter contained too much background which caused low quality reconstructions when rendering the balls near the mini pool table edges.
important to set the encoder and decoder receptive field sizes be greater than but
(a) Training data.
Generated data (linear motion at unseen positions).
(c) Generated data (collision and slowing down).
Figure 11: Mini pool video used for training, together with two videos generated after training by modifying and decoding the learned latent variables (video frames superimposed). Both ball objects are detected successfully and are used to generate realistic videos.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly state our contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in sec. 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
We provide proof assumptions and sketch in sec. and full proof in appendix
A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provide training details in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [No]
Justification:
We will release the code upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeeee //nips.com /ttc: ssiniiiiccypyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We provide experimental setting details in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide uncertainty ranges for all Gaussian distributions and error bars for data points where appropriate (figs. 3 5).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide information about compute resources in appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform. in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We preserve anonymity in the paper submission and adhere to other points in the NeurIPS Code Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper focuses on fundamental research and theory and does not present
direct malicioussuuinteedde uses etc.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our models and data do not pose risks for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our paper does not use existing assets; we the authors of all code.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "KIEbGd1MQV", "reviewer": "Reviewer_YrtR", "summary": "This paper presents the first unsupervised object detection approach that is theoretically shown to recover the true object positions up to quantifiable small deviations that are related to the encoder and decoder receptive field sizes, the object sizes, and the widths of the Gaussians used in the rendering process. The authors conduct a thorough analysis of how the error depends on each of these variables and conduct synthetic experiments that validate our theoretical predictions up to a precision of individual pixels. \nOn a high level, their architecture is based on an autoencoder that is fully equivariant to translations, which they achieve by making the encoder consist of a CNN followed by a soft argmax function to extract object positions, and making the decoder consist of a Gaussian rendering function followed by another CNN to reconstruct an image from the object positions. \nThe authors also conducted synthetic experiments, CLEVR-based experiments, and real video experiments that validated their theoretical findings up to a precision of individual pixels.", "questions": "Please check the weakness section", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I do like the analysis of the current state-of-the-art detection models SAM and CutLER and it is interesting to find that in some cases their errors are much higher than the bound derived by this method.\n\nThis paper is well-written and easy to follow.", "weaknesses": "1. It is interesting to learn that SAM and CutLER's errors are sometimes much higher than the bound derived by the proposed method. I would be interested to hear from the authors if they have any insights on how this finding could be used to improve these methods, especially CutLER, which is also an unsupervised object detection and instance segmentation model.\n\n2. The majority of the experiments in this paper are conducted on synthetic datasets, and it is questionable whether the findings can be generalized to real images and videos. Could the authors provide some experiments on real images or videos? \n\n3. Continuing on the previous point, most objects in the synthetic datasets are rigid and have very consistent shapes. However, the challenges in object detection are often in detecting the non-rigid objects or partially occluded objects. I am curious to see if the proposed method can be used to handle these cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It is interesting to learn that SAM and CutLER's errors are sometimes much higher than the bound derived by the proposed method.\n\nWe note that all the error plots in the paper contain the maximum position errors, as opposed to average position errors (as described in Appendix C). So, while SAM and CutLER do well in the average case, they are much worse (unbounded) than our method in the worst case. We do this to show that even in the worst case our method is able to contain the errors within our bounds unlike other methods.\n\n> I would be interested to hear from the authors if they have any insights on how this finding could be used to improve these methods, especially CutLER, which is also an unsupervised object detection and instance segmentation model.\n\nFor our method, deriving theoretical bounds was possible due to the exact equivariance property of the encoder and the decoder, and the restricted form of our latent space. However, because both SAM and CutLER are relatively complex transformer-based models, it is difficult to derive theoretical bounds for these methods. However, we speculate that to obtain guarantees for these methods, one might have to replace parts of their architectures with equivariant or invariant elements and introduce tight bottlenecks, in order to reduce the solution space sufficiently to enable the kind of theoretical analysis we have performed. We hope that our contribution will open up the possibility for such guarantees in future work.\n\n> The majority of the experiments in this paper are conducted on synthetic datasets, and it is questionable whether the findings can be generalized to real images and videos. Could the authors provide some experiments on real images or videos?\n\nWe perform experiments on real videos in Appendix D of the paper, which are based on real YouTube videos of overhead road traffic and a game of mini pool. In these experiments we show that the objects are learned with high precision and the latent space can be intervened on to generate realistic videos with the objects at previously unseen positions. We will be happy to add more if requested.\n\n> Continuing on the previous point, most objects in the synthetic datasets are rigid and have very consistent shapes. However, the challenges in object detection are often in detecting the non-rigid objects or partially occluded objects. I am curious to see if the proposed method can be used to handle these cases.\n\nAs this is the first paper to propose any theoretical guarantees for object detection, we decided to focus on producing a detailed analysis of the common case of rigid, non-occluded objects. However, while not discussed in the paper, we observe in our experimental data that the method is relatively robust to partial occlusions (e.g. one sphere covering part of another sphere in CLEVR). Regarding non-rigidity, we believe that as long as the deformed object fits within the receptive field, the method should also be able to detect those objects as long as they are sufficiently similar to the original object. For more complex cases of occlusions and non-rigidity, one might have to amend the method to deal with these cases explicitly (e.g. by modeling the order in which objects are rendered, and modeling the explicit geometry of non-rigid objects). We leave these for future work, to maintain the conciseness and clarity of the current proofs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CPS2DRGmxz", "reviewer": "Reviewer_x9ub", "summary": "The paper proposes a new idea for unsupervised object detection where an CNN based auto-encoder architecture is employed and the latent representation is trained to learn position of objects in images. They further provide theoretical analysis of the proposed idea under strong assumption about the input data and model characteristics. Results from on synthetic data experiments is also provided", "questions": "- Can the authors provide more clarification on the training procedure and the important aspects that are necessary for the model work?\n- Given that the latent space is learning the position encoding for the object, how is it possible to learn to model semantics for reconstruction loss?\n- how does the model performance change relative to diversity of object shape and appearance in a single image?\n- why is it important to use positional encoding?\n- how the reconstruction quality can be guaranteed, especially in a realistic setting?", "limitations": "- The work is limited by its assumptions on the characteristics of the input data and model architecture. \n- The theoretical analysis is dependant on strong assumptions like \"the objects are reconstructed at the same positions\" which itself is not guaranteed. \n- Furthermore, the evaluations do not provide insight into what challenges one should address to successfully train a model based on the proposed idea. \n- Please see the Weaknesses for more details.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The idea presented in the paper is interesting as it tries to solve the object detection problem in an unsupervised manner by modeling the latent space such that it explicitly learns object positions.", "weaknesses": "The paper lacks results and discussion on the experimental details on how the idea can be effectively implemented. This is particularly important to understand the merits of the proposed idea as it has strong assumption on model architecture and input data (e,g, size of objects). For example, it is not clear how the authors processes input data during training, how the min-batch sampling is done, what input-target pairs are?, what regulations are important to use if at all, how the over-fitting is prevented given the very simplified experimental setting.\nFurthermore, it is not clear from the paper how the latent space can learn any semantic information to reconstruct the images as it modeled to learn the position of the objects.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Can the authors provide more clarification on the training procedure and the important aspects that are necessary for the model work? For example, it is not clear how the authors processes input data during training, how the min-batch sampling is done, what input-target pairs are?, what regulations are important to use if at all\n\nWe provide all training details for our experiments in Appendix C. To directly address the reviewer’s questions, in our synthetic experiments we train on images containing white squares of size 7x7 px at different positions on a background of size 80x80 px, with mini-batch size of 128 and learning rate $10^{-3}$, and the input-target pairs both being the same image. In our CLEVR experiments, we train on images containing spheres with different range of sizes (from 4 to 27 px) and at different positions, on a background of size 106x80 px, with mini-batch size of 150 and learning rates $10^{-2}$ and $10^{-3}$. In both cases we do not use any regularisation and train until convergence, discarding any result where an object has not been learned.\n> how the over-fitting is prevented given the very simplified experimental setting.\n\nOverfitting is prevented by the translation equivariance property of the architecture: an equivariant encoder and decoder, with a small receptive field, must reconstruct well at every possible sub-window of the image (as they are applied convolutionally). Equivariant models can thus learn from very few images compared to other architectures.\n\n> Given that the latent space is learning the position encoding for the object, how is it possible to learn to model semantics for reconstruction loss?\n\nSemantics are encoded in the ordering of the objects’ positions in the latent space: it is not an unordered list, but rather each position corresponds to a single object identity. Therefore, the encoder and decoder learn to associate each latent position to a different object, which allows the decoder to successfully reconstruct each object.\n\n> how does the model performance change relative to diversity of object shape and appearance in a single image?\n\nWe found the model to be robust to lighting and perspective distortions of the objects in the CLEVR dataset (objects becoming larger/smaller when they are closer/further away). Although not included in the paper, the model was also successful in detecting different shapes (spheres, cubes, cylinders) at different orientations – please see figure 12 of the rebuttal PDF.\n\n> why is it important to use positional encoding?\n\nWe use positional encodings as one input to the decoder to reconstruct a static background. Because the decoder is translation equivariant, the positional encodings provide it with the positional information necessary to successfully reconstruct different parts of the background. For dynamic backgrounds, an unrelated frame from the same video can be passed instead of the positional encoding (as mentioned in section 3).\n\n> The work is limited by its assumptions on the characteristics of the input data and model architecture.\n\nThe assumptions on the input data and model architecture are necessary for our proof of the theoretical bounds of the method – it is impossible to derive any guarantees with no assumptions. We believe these assumptions are not very restrictive and apply to many common use cases for object detection such as traffic monitoring, surveillance, etc, where there are moving objects and a static background (we also mention an extension for dynamic backgrounds in section 3).\n\n\n> how the reconstruction quality can be guaranteed, especially in a realistic setting?\n> The theoretical analysis is dependant on strong assumptions like \"the objects are reconstructed at the same positions\" which itself is not guaranteed.\n\nThis is guaranteed by the Universal Approximation Theorem: a sufficiently-large neural network can approximate any function. If the reconstruction error is high, we simply need a larger network, until the error is low enough.\n\n> Furthermore, the evaluations do not provide insight into what challenges one should address to successfully train a model based on the proposed idea.\n\nIn practice, successful training requires videos with a static camera, objects that fit the receptive field of the autoencoder, that stay in-frame for the duration of a video, and no large perspective changes during motion. We provide further training details in Appendix C.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "v1fpXhZeoS", "reviewer": "Reviewer_pKP5", "summary": "This paper explores Unsupervised Object Detection with Theoretical Guarantees. This method is a significant advancement in the field of object detection as it provides theoretical guarantees on the accuracy of the detected object positions. By introducing a new approach that ensures reliable object localization, the research contributes to enhancing the robustness and accuracy of unsupervised object detection systems.", "questions": "1. In the experiments, the datasets for evaluation is the CLEVR data, please explain why choose it, not other popular object detection datasets?\n2. This work validate the theoretical results using lots of experimental results, however only few experiments are carried out for the comparison with SOTA.\n3. In object detection, the popular model is about YOLO, and also the metric including accuracy, mAP, and IoU, etc are also the common in supervised object detection.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method provides theoretical guarantees on recovering true object positions up to small shifts, which is a significant strength compared to traditional empirical approaches in object detection. The ability to interpret the latent variables as object positions enhances the interpretability of the model and facilitates understanding of the learned representations. The use of an autoencoder with a convolutional neural network (CNN) encoder and decoder, modified to be translationally equivariant, offers a unique and innovative approach to unsupervised object detection.", "weaknesses": "This work explores the unsupervised object detection, and theoretical analysis. However, the dataset for the experiment is not common, and few comparative experiments with common SOTA object detection model. Besides, although this work provides the theoretical guarantees to recover the true object positions up to quantifiable small shifts, there is no analysis whether it only exists in the unsupervised domain,.or can be adopted in the supervised domain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In the experiments, the datasets for evaluation is the CLEVR data, please explain why choose it, not other popular object detection datasets?\n\nWe chose to base our dataset on CLEVR because it is a dataset commonly used in unsupervised learning, and because it allows us to generate images of the same object at different positions and with different sizes on a static background, which are the assumptions in our model. These assumptions do not necessarily hold in other datasets such as MS COCO or PASCAL VOC, which normally do not contain the same object twice, contain varying backgrounds, and do not have any bounds on the object sizes. In general, our method is more suitable for dynamic object detection from videos (where objects keep their identity but change position) rather than detecting single objects in images. \n\n> This work validate the theoretical results using lots of experimental results, however only few experiments are carried out for the comparison with SOTA.\n\nThe aim of our paper is to present the first unsupervised object detection method with theoretical guarantees, and therefore our priority was to prove and validate our theoretical claims in detail. Our focus was less on the current SOTA methods, as, to the best of our knowledge, none of them possess any theoretical guarantees and thus are not directly comparable. We have compared with two current SOTA methods SAM and CutLER, but if the reviewer has any other particular method in mind, we are open to performing a comparison with that method.\n\n> there is no analysis whether it only exists in the unsupervised domain,.or can be adopted in the supervised domain\n\nFor our method, deriving theoretical bounds was possible due to the exact equivariance property of the encoder and the decoder, and the restricted form of our latent space. In the supervised domain, many approaches are based on relatively complex transformer-based models, which do not possess any such guarantees. However, we speculate that to obtain guarantees for these methods, one might have to replace parts of their architectures with equivariant or invariant elements and introduce tight bottlenecks, in order to reduce the solution space sufficiently to enable the kind of theoretical analysis we have performed. We hope that our contribution will open up the possibility for such guarantees in future work.\n\n> In object detection, the popular model is about YOLO, and also the metric including accuracy, mAP, and IoU, etc are also the common in supervised object detection.\n\nCompared to YOLO, our method is fully unsupervised and possesses theoretical bounds on the detection errors, while theirs requires supervision and does not possess any such guarantees. While in our paper we prove bounds for the maximum position errors, these can be related to other metrics such as IoU by considering the overlap instead of the distance between the ground truth object and its detection (intuitively, the IoU bounds would be related to the square of the position bounds). We thank the reviewer for this suggestion and will add this to the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6lJvjUapel", "reviewer": "Reviewer_ghv9", "summary": "This paper proposes an autoencoder based object detection model that makes predictions about object positions in an unsupervised manner. Imporantly, the authors can provide theoretical guarantees/ bounds about the degree of the model's detection error.", "questions": "see above", "limitations": "see above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and it is easy to follow the authors motivation and structure of the work. I also find the idea very valuable to investigate the theoretical bounds of such models.", "weaknesses": "I have summarized my questions and issues and limitations that I see here: \n\nIn the context of the CLEVR experiments, I am wondering why the authors don’t evaluate concerning the Gaussian standard deviation as they did for the first dataset?\n\nThe authors claim the method requires dynamic objects, but they never mention this in main text. Can the authors provide more justification of this? I.e. why this is/ what part of the approach requires this?\n\nI don’t understand how the decoder can learn to reconstruct complex shapes other than spheres (due to the Gaussian assumption). Also the authors mainly evalaute on data with objects that are spherical. Thus, is it possible to evaluate on other shape forms? If so what is the error here compared to spherical shapes? I do not mention this as a limitation, but it seems quite important to put the method into context. What would be potential ideas to mitigate handling more complex objects?\n\nI do not have enough knowledge about the details of the CutLer and SAM models, but why should the theoretical bound of this work hold for these works as well (the authors compare these in Fig. 6)? Specifically, the authors state \"only for our\nmethod are the position errors always guaranteed to be within our theoretical bound.\" so my question is: why should the other methods lie within this theoretical guarantee?\n\nI am a little confused by the related works section. The authors discuss object-centric representation methods whose goal, unlike that of their method, is to learn a full representation of an object. This includes much more information than just position. In other words, it seems the method of this paper focuses “only” on the learning the position of an object. While this does not diminish the significance of the work, I think the work could benefit from discussing more on this difference between these works, to make the comparisons more fair and also focus more on works that focus on unsupervisedly localising object in images (i.e., works that only focus on position and not on the other aspects of object reperesentations), e.g., [1,2]. So in the end I am also wondering if the authors should actually narrow down the title/contribution claims to \"Unsupervised Object Localisation with Theoretical Guarantees\"?\n\nIf the authors can remark on these issues above, I am happy to consider raising my score.\n\n[1] Siméoni, Oriane, Chloé Sekkat, Gilles Puy, Antonín Vobecký, Éloi Zablocki, and Patrick Pérez. \"Unsupervised object localization: Observing the background to discover objects.\" In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3176-3186. 2023.\n[2] https://github.com/valeoai/Awesome-Unsupervised-Object-Localization", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In the context of the CLEVR experiments, I am wondering why the authors don’t evaluate concerning the Gaussian standard deviation as they did for the first dataset?\n\nWe thank the reviewer for their suggestion and have performed this experiment – please see fig. 11 of the rebuttal PDF. As all our data points lie within our theoretical bounds, this successfully validates our theory.\n\n> The authors claim the method requires dynamic objects, but they never mention this in main text. Can the authors provide more justification of this? I.e. why this is/ what part of the approach requires this?\n\nWe mention this in the Introduction: “Our method guarantees to detect any object that moves in a video or that appears at different locations in images”, and later in assumption 2 of Theorem 4.1: “each object appears in at least two different positions in the dataset”. We will reinforce it further throughout the paper that this is equivalent to requiring dynamic objects. This prevents the object being learned as part of the background – if it did not move, then the encoder would not need to communicate its position to the decoder to reconstruct every image in the dataset, and the object would not be detected. The proof in Appendix A has more details on how this assumption is used.\n\n> I don’t understand how the decoder can learn to reconstruct complex shapes other than spheres (due to the Gaussian assumption).\n\nThe decoder takes as input binary maps containing Gaussians centered at the object positions given by the latent variables ($\\hat{e}$ in fig. 1). The decoder, consisting of multiple convolution blocks, then iteratively convolves these Gaussians with its kernels (which are not Gaussian, but arbitrary/learned) until it reaches its receptive field size. For example, if the decoder contains 3 7x7 convolutions and the Gaussian bandwidths are narrow, this will result in the receptive field size of $1 + 3 \\times (7-1) = 19$, allowing it to reconstruct any object of size up to 19x19 px, regardless of its shape (not just Gaussians). \n\n> Also the authors mainly evalaute on data with objects that are spherical. Thus, is it possible to evaluate on other shape forms? If so what is the error here compared to spherical shapes? I do not mention this as a limitation, but it seems quite important to put the method into context. What would be potential ideas to mitigate handling more complex objects?\n\nWhile in our CLEVR experiments in the paper we have used spherical objects, the method works on objects of any shape (see answer to previous question). We have performed CLEVR experiments using 3 different shapes – a sphere, a cube, and a cylinder – and show the results in fig. 12 of the rebuttal PDF. As all our data points lie within our theoretical bounds, this shows that our method is applicable to objects of any shape, not just spheres.\n\n> I do not have enough knowledge about the details of the CutLer and SAM models, but why should the theoretical bound of this work hold for these works as well (the authors compare these in Fig. 6)? Specifically, the authors state \"only for our method are the position errors always guaranteed to be within our theoretical bound.\" so my question is: why should the other methods lie within this theoretical guarantee?\n\nThe CutLER and SAM methods do not possess any theoretical guarantees on their object detections, and so there is no theoretical bound for their errors. We have only included this comparison to show that, even in the worst case (maximum over the position errors), the errors of our method are always bounded by our theoretical bound while the errors for CutLER and SAM are not, and are much higher than our bound in some settings. The experiment is meant to illustrate how worst-case unbounded errors can occur for such state-of-the-art methods, which can be a safety concern.\n\n> I think the work could benefit from discussing more on this difference between these works, to make the comparisons more fair and also focus more on works that focus on unsupervisedly localising object in images (i.e., works that only focus on position and not on the other aspects of object reperesentations), e.g., [1,2].\n\nWe thank the reviewer for their suggestion and will discuss these works in the related work section of the paper. Briefly, works such as [1] and other works in [2] rely on vision transformer (ViT) self-supervised features for unsupevised object detection and segmentation, without possessing any theoretical guarantees for their detection errors. In contrast, our method uses a translationally equivariant CNN-based encoder and decoder with a structured bottleneck, which allows us to prove theoretical bounds for our detection errors.\n\n[1] Siméoni, Oriane, Chloé Sekkat, Gilles Puy, Antonín Vobecký, Éloi Zablocki, and Patrick Pérez. \"Unsupervised object localization: Observing the background to discover objects.\" In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3176-3186. 2023.\n\n[2] https://github.com/valeoai/Awesome-Unsupervised-Object-Localization", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
In response to reviewer’s ghv9 question, we have performed CLEVR experiments showing the position error as a function of the Gaussian standard deviation (see fig. 11 in the rebuttal PDF). As all our data points (red) lie within our theoretical bounds (blue), this successfully validates our theory.

Additionally, in response to reviewers’ x9ub and ghv9 questions, we have performed CLEVR experiments using a dataset containing 3 different shapes (a sphere, a cube, and a cylinder), showing that our method works for objects of any shape, not just spheres (see fig. 12 in the rebuttal PDF).

We hope that these experiments address the reviewers’ concerns.

Meta-review: This paper is about unsupervised object detection, the authors propose a way to build an unsupervised object detection with theoretical guarantees, meaning known bounds on position errors, via an autoencoder architecture with latent variables.

The paper contributes to the start of the art with a unsupervised object localization architecture that can recover true object positions to a known error bound, and theoretical analysis to demonstrate error bounds, and how these bounds depend on encoder/decoder receptive field sizes, object size, and gaussian variance during rendering. Experiments are made on synthetic data generated by the authors and on CLEVR dataset, and show the validity of the bounds.

All reviewers agree that the paper is very well written and mostly easy to understand/follow, there is a good evaluation and a comparison to previous methods (SAM and cutLER), and the approach is in the right direction to solve the unsupevised object detection problem, with an innovative and novel approach.

One minor weakness is that all experiments are made on synthetic data, and its not clear how this method would perform in real data.

Some minor improvements are suggested for this paper, the proposed method actually performs object localization, as the whole theoretical guarantee is about object localization, and object detection also includes object classification which is not considered in this approach, clarify the training process, and the limitations and assumptions of the proposed approach. Also please consider the many small details mentioned by the reviewers.

Overall this paper is above the acceptance threshold, and should be accepted.
Decision: Accept (poster)