Unsupervised Object Detection
with Theoretical Guarantees
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.
1 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 is 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 is often costly and time consuming, and in some cases may be impractical or unethical. For example, in medical imaging, unsupervised object detection can help save specialists’ time by automatically flagging suspicious abnormalities schlegl2017anogan , and in autonomous driving it may help automatically detect pedestrians on a collision course with the vehicle dairi2018obstacledetection . 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 we 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 on the encoder and decoder receptive field sizes, the object sizes, and the sizes of the Gaussians used for rendering. This is especially important in sensitive domains such as medicine, where incorrectly detecting an 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 are distinct and the images are reconstructed correctly.
We base our unsupervised object detection method on an autoencoder with a convolutional neural network (CNN) encoder and decoder, and modify it to 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 a theorem that relates the maximum position error of the learned latent variables to the size of the encoder and decoder receptive fields, the size of the objects, and the width of the Gaussian used in the decoder (sec. 4). Next, we derive corollaries describing the exact form of the maximum position error as a 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-based johnson2017clevr experiments to validate our theory (sec. 5). 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 to precisions of individual pixels.
2 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) kirillov2023sam , Mask R-CNN he2017maskrcnn , U-Net ronneberger2015unet and others goldman2019precise . 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 wang2023cutler , Slot Attention locatello2020slotattention , MoNet burgess2019monet and others greff2019multi . These methods aim to learn object-centric representations for object detection and segmentation without using training labels. Finally, unsupervised object localisation methods such as FOUND simeoni2023found and others simeoni2024survey 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 in 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. xi2023identifiabilitycharacterization categorise these assumptions for generative models into constraints on the distribution of the latent variables and constraints on the generator function. Some of their categories include non-Gaussianity of the latent distribution shimizu2006lingam , dependence on an auxiliary variable hyvarinen2016nonlinearica ; hyvarinen_td_2017 , use of multiple views locatello2020multipleviews , use of interventions brehmer2022interventions ; lippe2022citris , use of mechanism sparsity lachapelle2022sparsity , and restrictions on the Jacobian of the generator gresele2021ima . In contrast, in our work we achieve identifiability by making our network equivariant to translations, imposing an interpretable latent space structure, and requiring the data to obey our theorem’s assumptions.
3 Method
In this section we describe the proposed method for unsupervised object detection with guarantees. On a high level, our architecture is based on an autoencoder that is fully equivariant to translations, which we 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 (fig. 1). In the following sections we describe the different parts of the architecture in detail.
Autoencoder with CNN Encoder and Decoder.
We start with an autoencoder, a standard unsupervised representation learning model, consisting of an encoder network that maps an image to a low-dimensional latent variable , followed by a 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 (MLPs) or convolutional neural networks (CNNs) paired with fully-connected (FC) layers, however neither of these parametrisations 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 hornik1989multilayer ). To obtain such guarantees, we would thus like to modify the autoencoder to make it exactly translationally equivariant, that is, a shift of an object in the input image should correspond to a proportional shift of the latent variable , and a shift of the latent variable should correspond to a 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 a filter , defined in one dimension as
(1) |
Intuitively, this corresponds to sliding the filter across the feature map and at each position of the filter computing the dot product between the feature map and the filter . We can prove that convolutional layers are equivariant to translations, since
(2) |
where is the translation operator that translates a feature map by pixels, and we have used the substitution at 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 scalar variables that can be interpreted as object positions that are equivariant to image translations. To do this, we first define a translation of a (1D) feature map and a translation of a scalar as
(3) |
where is the position in the feature map , shifts an image by pixels, and shifts a scalar by units. To relate translations in feature maps to translations in latent variables, we can use a function that computes a scalar property of a feature map , such as , defined as . Using these definitions we can now prove the equivariance of , i.e. that shifting the feature map by corresponds to shifting the latent variable by :
(4) |
where at the first equality we use the definition of , at the second equality we use the definition of (eq. 3, left), at the third equality we use the substitution , at the fourth equality we use the definition of , and at the last equality we use the definition of (eq. 3, right).
However, because the argmax operation is not differentiable, for neural network training we approximate it via a differentiable soft argmax function, defined in 2D as
(5) |
where is the softmax function defined in one dimension as , and is the softmax function evaluated along the first and second dimensions of , is a temperature hyperparameter, is the image index, is the image width, is the image height, and the term ensures that the densities correspond to pixel centres. As the temperature in eq. 5 approaches zero, reduces to the classical function.
From Latent Variables to Decoder Feature Maps.
Similar to mapping from encoder feature maps to latent variables, we would now like to relate shifts in latent variables to shifts of decoder feature maps . To do this, we can invert the action of the operation. Because 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 . We can show that is a pseudo-inverse of because . Now, similar to the function, we can prove that the function is equivariant to the latent variable shift on the input and the feature map shift on the output, i.e.
(6) |
where at the first equality we have used the definition of , at the second equality we have used the definition of (eq. 3, right), at the third equality we have used the definition of , and at the last equality we have used the definition of (eq. 3, left).
Again, because the function is not differentiable, we can approximate it using a differentiable function as
(7) |
where is a Gaussian evaluated at with variance given by the hyperparameter . As the variance in eq. 7 approaches zero, the function reduces to the hard function.
Additionally, because the decoder is translationally equivariant, we also condition it 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 is static. Alternatively, if background is varying, the decoder can be conditioned on a randomly-sampled nearby video frame instead, which will provide information about the background but not the objects’ positions (following Jakab et al. jakab2018keypoints ).
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
(8) |
This is shown in fig. 1. Having designed an exactly translationally equivariant architecture now allows us to obtain theoretical guarantees about the learned latent variables, which we discuss next. 111We note that a similar architecture was proposed by Jakab et al. jakab2018keypoints , with empirical success in keypoint detection. However, we derive our architecture by enforcing strict translation equivariance properties, which makes our theoretical results possible.
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 in terms of the encoder and decoder receptive field sizes, the object size, and the Gaussian standard deviation (thm. 4.1). 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 with objects of size , CNN encoder with receptive field size , CNN decoder with receptive field size , soft argmax function , rendering function with Gaussian standard deviation and , and latent variables , composed as and (fig. 1). 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 correspond to the true object positions up to object permutations and maximum position errors of
(9) |
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. In the encoding process, the maximum error occurs when the encoder and the object are as far away from each other as possible while still overlapping, i.e. (fig. 2(a)). Conversely, in the decoding process, the maximum error occurs when the rendered object and the latent variable are as far away from each other as possible while both still being inside the decoder receptive field, i.e. (fig. 2(b)). Additionally, there is an extra error of as the latent variable is rendered by a 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 to eq. 9. Next, we present corollaries relating this error bound to different factors.
Corollary 4.2 (Error Bound vs. Encoder RF Size).
The maximum position error as a function of the encoder receptive field (RF) size for a given , , , is
For an illustration see fig. 3(a). There are two regions of the curve (separated by a dashed line). In the left-most region, , the error is dominated by the encoder error, and in the right-most region, , the error is dominated by the decoder error. Initially, for , the error is given by , because the 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 is at the centre of the object. As the encoder RF size increases up to , the position error increases linearly with it as , because now any part of the encoder RF can match any part of the object (fig. 2(a)). This bound is deterministic due to the deterministic encoding process.
At (vertical dashed line in fig. 3(a)), the maximum errors from encoder and decoder both become equal to . For , the position error is dominated by the error from the decoder which is constant at with , 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 is distributed normally with variance .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 for a given , , , is
For an illustration see fig. 3(b). Similar to corollary 4.2, there are two regions of the curve, one for (left), where the error is dominated by the decoder error, and another for (right), where the error is dominated by the encoder error. Note that this is opposite to cor. 4.2. Initially, for , the decoder receptive field has the same size as the object, and so to achieve perfect reconstruction it needs to be at the same position as the object, resulting in position error plus any error caused by the non-zero width of the Gaussian. As the decoder RF size increases up to , the position error increases linearly with it as , because now the object can be at an increasing number of positions within the decoder and still achieve perfect reconstructions (fig. 2(b)). At , the maximum errors from encoder and decoder both become equal to . For , the position error is dominated by the error from the encoder which is constant at , and so even though the decoder RF size is increasing, this has no effect as the limiting factor is now the encoder. Similar to corollary 4.2, the results of corollary 4.3 can be extended to objects with multiple different sizes (see appendix B, cor. B.2).
Corollary 4.4 (Error Bound vs. Object Size).
The maximum position error as a function of the object size for a given , , , is
For an illustration see fig. 3(c). Again, there are two regions of the curve, one for (left), where the error is dominated by the encoder error, and one for (right), where the error is dominated by the decoder error. Initially, for , the error is given by , because any pixel of the encoder receptive field can match the px object and so the error can be at most half of the encoder receptive field size. As the object size increases up to , the position error increases linearly with it as , because now any part of the encoder RF can match any part of the object (fig. 2(a)). At , the maximum errors from encoder and decoder both become equal to . For , the position error is dominated by the error from the decoder and decreases linearly as , because now there is a decreasing number of positions where the object can still fit inside the decoder receptive field (fig. 2(b)). At , the object reaches the same size as the decoder, and thus the position error decreases to with an additional error due to the width of the Gaussian, . 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 for a given , , , is
For an illustration see fig. 3(d). Firstly, there is an overall maximum bound for the position error due to the encoder, given by the constant , which is independent of the Gaussian standard deviation. Then, initially for , the rendered Gaussian is effectively a delta function, and so the position error is dominated by the decoder error given by , which describes the maximum distance between the object and the delta function with both of them fitting inside the decoder receptive field (fig. 3(b)). As the Gaussian standard deviation increases, the position error increases linearly as with . Then, depending on what part of the Gaussian the decoder is convolved with, there are different bounds for the maximum position error. If the decoder is convolved with a part of the Gaussian that is within standard deviations of its centre, the maximum position error increases linearly as up to , after which point the position error becomes dominated by the encoder value of . In fig. 3(d), 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.
5 Experimental Results
In this section we validate our theoretical results on synthetic experiments (sec. 5.1) and CLEVR data (sec. 5.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 to sizes of individual pixels. We then apply our method to CLEVR-based johnson2017clevr data containing multiple objects of different sizes in varying scenes (sec. 5.2) and show that compared to current SOTA object detection methods (SAM kirillov2023sam , CutLER wang2023cutler ), 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 a black background. In each experiment we fix all but one of the encoder RF size , decoder RF size , object size , and Gaussian standard deviation , 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 . For more details see appendix C.1.
Position Error vs. Encoder RF Size.
In this experiment we aim to empirically validate corollary 4.2, by measuring the experimental position errors as a function of the encoder receptive field size. We vary the encoder RF sizes and fix and record position errors . We visualise the data points (red) and the theoretical bounds (blue) in fig. 4(a). 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 to 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.
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 and fix and record position errors . We visualise the results in fig. 4(b). 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).
Position Error vs. Object Size.
In this experiment we aim to validate corollary 4.4 by measuring the experimental position errors as a function of the object size. We vary the object sizes and fix and record position errors . We visualise the results in fig. 4(c). As all the data points lie at or below the theoretical boundary, this validates corollary 4.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 , fixing and record position errors . We visualise the data points (red) and the theoretical bounds (blue) in fig. 4(d). 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 we validate our theory on CLEVR-based johnson2017clevr image data of 3D scenes. Our dataset consists of 3 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.1, recording position errors for the learned objects, and compare our results with SAM kirillov2023sam and CutLER wang2023cutler baselines. We compute the theoretical bounds according to our theory in sec. 4 and app. B, and visualise the results in figs. 5(a)-5(c). For details see app. C.2. For experiments with different shapes see app. D.
Once again, the experimental results demonstrate high agreement with our theory, now even for more complex images with multiple objects and a range of object sizes (fig. 5, red, blue). Furthermore, while the SAM and CutLER baselines generally achieve low position errors, this is not guaranteed, and in some cases their errors are much higher than our bound (fig. 5, green, orange). We report the proportion of position errors from fig. 5(c) that lie within 2 standard deviations of our theoretical bound in table 6(b) and fig. 6(a), showing that compared to SOTA object detection methods, only for our method are the position errors always guaranteed to be within our theoretical bound.
Object Size 1.5 (px) | |||||||
---|---|---|---|---|---|---|---|
Method | All | 9 | 12 | 15 | 18 | 21 | 24 |
Ours | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
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 |
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:
-
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. 3(b)).
-
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 a certain point (fig. 3(a)).
-
3.
To minimise the error, the width of the rendering Gaussian should be kept as small as possible while still permitting gradient flow, as increasing it even slightly may result in a dramatic increase to the decoder term of the position error (fig. 3(d)). 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. 4(d)).
-
4.
In the case that one does not know a 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 as close as 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 to the curve in fig. 3(c), 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 if they move in a video or if they appear at multiple locations in images. Secondly, in its current form the method learns representations that can not be used for videos with different backgrounds than the one used at training time; however, this can be overcome by conditioning the decoder on an unrelated video frame instead of the positional encodings, as in Jakab et al. jakab2018keypoints . Thirdly, the guarantees of 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 to 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 to 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 a starting point for more research into object detection methods that possess theoretical guarantees, which are lacking in current practice.
Acknowledgements.
The authors acknowledge the generous support of the Royal Academy of Engineering (RF\201819\18\163), the Royal Society (RG\R1\241385) and EPSRC (VisualAI, EP/T028572/1).
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 representation, 2019.
- [3] Abdelkader Dairi, Fouzi Harrou, Mohamed Senouci, and Ying Sun. Unsupervised obstacle detection in driving environments using deep-learning-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. In 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 representation learning with iterative variational inference. In International conference on machine learning, pages 2424–2433. PMLR, 2019.
- [6] Luigi Gresele, Julius von Kügelgen, 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. In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
- [8] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359–366, 1989.
- [9] Aapo Hyvarinen and Hiroshi Morioka. Unsupervised feature extraction by time-contrastive 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 Jerry Zhu, editors, Proceedings of the 20th International Conference 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 object landmarks through conditional image generation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing 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: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference on 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-Yen Lo, et al. Segment anything. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4015–4026, 2023.
- [14] Sebastien Lachapelle, Pau Rodriguez, Yash Sharma, Katie E Everett, Rémi LE PRIOL, Alexandre Lacoste, and Simon Lacoste-Julien. Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ICA. In First Conference on Causal Learning and Reasoning, 2022.
- [15] Phillip Lippe, Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Stratis Gavves. CITRIS: Causal identifiability from temporal intervened sequences. In 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 Raetsch, Bernhard Schölkopf, Olivier Bachem, and Michael Tschannen. Weakly-supervised disentanglement without compromises. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6348–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 in neural information processing systems, 33:11525–11538, 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–MICCAI 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-Erfurth, and Georg Langs. Unsupervised anomaly detection with generative adversarial networks to guide marker discovery. In International conference on information processing in medical imaging, pages 146–157. 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, 7(72):2003–2030, 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 IEEE/CVF Conference on 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 era 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 Learning Research, pages 6912–6939. PMLR, 25–27 Apr 2023.
Appendix A Proof of Theorem 4.1
Theorem (Maximum Position Error).
Consider a set of images with objects of size , CNN encoder with receptive field size , CNN decoder with receptive field size , soft argmax function , rendering function with Gaussian standard deviation and , and latent variables , composed as and (fig. 1). 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 correspond to the true object positions up to object permutations and maximum position errors of
(10) |
Proof.
By assumption (1), the positions objects in the original image have to be the same as the positions of the objects in the reconstructed image . In practice, this occurs whenever the reconstruction loss is minimised.
By assumption (2) (each object appears at a 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 concatenated with positional encodings or a randomly sampled nearby frame (fig. 1), 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 a 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 , this means that for objects in to be reconstructed at the same positions as in (assumption 1), the encoder needs to match some part of each object in .
Because is equivariant to translations of (sec. 3), and because the encoder has to match some part of each object in (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 is encoded by to the latent variables
(11) |
where the shifts and arise because any part of the encoder filter (of size ) can match any part of the object (of size ). See fig. 2(a) for an illustration.
Next, because is equivariant to translations of (sec. 3), the latent variables are mapped to a predicted image with an object at position
(12) |
where the shifts and arise because any part of the decoder filter (of size ) can match any part of the the rendered Gaussian , where . See fig. 2(b) 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.e.
(13) |
This results in the conditions
(14) |
and therefore
(15) |
In words, the shift in the latent variables acquired from the encoder has to be balanced by an opposite shift of the same magnitude in the decoder in order to reconstruct the object at the same position. Because the shift due to the encoder is of maximum magnitude of and the shift due to the decoder has a maximum magnitude of , 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 correspond to the ground truth latent variables up to
(16) |
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. ∎
Appendix 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 , leading to the following corollary.
Corollary B.1 (Error vs. Encoder RF Size for Multiple Object Sizes).
The maximum position error as a function of the encoder receptive field (RF) size for a given , , , is
For an illustration see fig. 7(a).
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 , leading to the following corollary.
Corollary B.2 (Error vs. Decoder RF Size for Multiple Object Sizes).
The maximum position error as a function of the decoder receptive field (RF) size for a given , , , is
For an illustration see fig. 7(b).
Appendix C 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 px, each with a white square with dimensions px, centered at positions where , where (to prevent unwanted edge effects). We divide the dataset into 4 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 , decoder RF size , object size , and Gaussian standard deviation , 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 as the absolute difference between the learned position and the centre of the object (maximum over horizontal and vertical differences, and over the test set). We discard a result if the reconstruction accuracy of the run is below , to only consider runs where the object has been detected successfully (this is because the square is on the order of px, thus only comprising of the image).
Architecture.
We parametrise both the encoder and the decoder as 5-layer CNNs with Batch Normalisation and ReLU activations, 32 channels, and filter sizes in , such that their receptive field sizes equal and respectively. We train each network for 500 epochs using the Adam optimiser with learning rate and batch size 128. We train each experiment on a single GPU for around 6 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 (fig. 8). For experiments measuring position error as a function of encoder and decoder RF sizes and Gaussian s.d., we use a dataset with object sizes between 6-10 px after perspective distortion (fig. 8(a)). 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. 8(b), 8(c)).
Evaluation.
For each experiment, we fix all but one variable from the following set: encoder RF size , decoder RF size , object size , and Gaussian standard deviation , 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 as the absolute difference between the learned position of each object and the centre of the object (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 as a 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 35 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 a 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.0% for the dataset with object sizes 6-10 px, 98.8% for dataset with sizes 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 ReLU activations, 32 channels, and filter sizes in , such that their receptive field sizes equal and respectively. We train each network until convergence using the Adam optimiser with learning rate 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 and batch size 150 for the experiment measuring position error as a 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-of-the-Art baselines, SAM [13] and CutLER [23]. First, for each of our 6 datasets (containing objects of sizes 6-10 px, …, 17-27 px), we combine its training and test set to create 4 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 as the absolute difference between the predicted position of each object and the centre of the object (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 3 bounding boxes (one for each object), otherwise we discard the prediction. For both methods, we 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 6 datasets.
Appendix D CLEVR Experiments with Different Shapes
To demonstrate that our method applies to objects of any shape, in this section we include experiments on our CLEVR dataset with three distinct objects – a red metallic sphere, a blue rubber cylinder and a 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. 9(a). We perform training and evaluation in the same way as in app. C.2. We plot the position error as a function of the encoder and decoder receptive field sizes in figs. 9(b) and 9(c), 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.
Appendix E Experiments with Real Videos
In this section we present experimental results of applying our 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 a car from an overhead traffic video. The training and test sets for this experiment consist of 25 frames each, from a video of an overhead view of a car moving for a short distance in a single lane (fig. 10(a)). We train the architecture from fig. 1 on this training set and validate it on the test set. It achieves a mean squared error between the ground truth object positions and the learned object positions of (in units normalised by the image size), demonstrating that the object position has been learned successfully with a very low error. We then modify the learned position variable and decode it to generate videos of the car at novel positions (figs. 10(b), 10(c)).
E.2 Mini Pool
In this experiment we aim to learn the positions of balls from a video of a game of mini pool. The training and test sets for this experiment consist of 15 and 11 frames respectively from a video of a game of mini pool, cropped to a portion where two balls are moving at the same time (fig. 11(a)). We train the architecture from fig. 1 on this training set and validate it on the test set, where it achieves a mean squared error between the ground truth object positions and the learned object positions of (in normalised units). This demonstrates that the object positions were learned successfully with a very low error. We then modify the learned position variables and decode them to generate videos of the balls at novel positions (figs. 11(b), 11(c)).
In practice, it was important to set the encoder and decoder receptive field sizes to be greater than but 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.