Tom Monnier
email: tom.monnier@enpc.fr

Thibault Groueix
email: thibault.groueix@enpc.fr

Mathieu Aubry
email: mathieu.aubry@enpc.fr

Deep Transformation-Invariant Clustering

Recent advances in image clustering typically focus on learning better deep representations. In contrast, we present an orthogonal approach that does not rely on abstract features but instead learns to predict transformations and performs clustering directly in pixel space. This learning process naturally fits in the gradient-based training of K-means and Gaussian mixture model, without requiring any additional loss or hyper-parameters. It leads us to two new deep transformation-invariant clustering frameworks, which jointly learn prototypes and transformations. More specifically, we use deep learning modules that enable us to resolve invariance to spatial, color and morphological transformations. Our approach is conceptually simple and comes with several advantages, including the possibility to easily adapt the desired invariance to the task and a strong interpretability of both cluster centers and assignments to clusters. We demonstrate that our novel approach yields competitive and highly promising results on standard image clustering benchmarks. Finally, we showcase its robustness and the advantages of its improved interpretability by visualizing clustering results over real photograph collections.

Introduction

Gathering collections of images on a topic of interest is getting easier every day: simple tools can aggregate data from social media, web search, or specialized websites and filter it using hashtags, GPS coordinates, or semantic labels. However, identifying visual trends in such image collections remains difficult and usually involves manually organizing images or designing an ad hoc algorithm. Our goal in this paper is to design a clustering method which can be applied to such image collections, output a visual representation for each cluster and show how it relates to every associated image.

Directly comparing image pixels to decide if they belong to the same cluster leads to poor results because they are strongly impacted by factors irrelevant to clustering, such as exact viewpoint or lighting. Approaches to obtain clusters invariant to these transformations can be broadly classified into two groups. A first set of methods extracts invariant features and performs clustering in feature space. The features can be manually designed, but most state-of-the-art methods learn them directly from data. This is challenging because images are high-dimensional and learning relevant invariances thus requires huge amounts of data. For this reason, while recent approaches perform well on simple datasets like MNIST, they still struggle with real images. Another limitation of these approaches is that learned features are hard to interpret and visualize, making clustering results difficult to analyze. A second set of approaches, following the seminal work of Frey and Jojic on transformation-invariant clustering [START_REF] Frey | Estimating Mixture Models of Images and Inferring Spatial Transformations Using the EM Algorithm[END_REF][START_REF] Frey | Fast, large-scale transformation-invariant clustering[END_REF][START_REF] Frey | Transformation-Invariant Clustering Using the EM Algorithm[END_REF], uses explicit transformation models to align images before comparing them. These approaches have several potential advantages: (i) they enable direct control of the invariances to consider; (ii) because they do not need to discover invariances, they are potentially less data-hungry; (iii) since images are explicitly aligned, clustering process and results can easily be visualized. However, transformation-invariant approaches require solving a difficult joint optimization problem. In practice, they are thus often limited to small datasets and simple transformations, such as affine 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada. transformations, and to the best of our knowledge they have never been evaluated on large standard image clustering datasets.

In this paper, we propose a deep transformation-invariant (DTI) framework that enables to perform transformation-invariant clustering at scale and uses complex transformations. Our main insight is to jointly learn deep alignment and clustering parameters with a single loss, relying on the gradient-based adaptations of K-means [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] and GMM optimization [START_REF] Dempster | Maximum Likelihood from Incomplete Data via the EM Algorithm[END_REF]. Not only is predicting transformations more computationally efficient than optimizing them, but it enables us to use complex color, thin plate spline and morphological transformations without any specific regularization. Because it is pixel-based, our deep transformation-invariant clustering is also easy to interpret: cluster centers and image alignments can be visualized to understand assignments. Despite its apparent simplicity, we demonstrate that our DTI clustering framework leads to results on par with the most recent feature learning approaches on standard benchmarks. We also show it is capable of discovering meaningful modes in real photograph collections, which we see as an important step to bridge the gap between theoretically well-grounded clustering approaches and semi-automatic tools relying on hand-designed features for exploring image collections, such as AverageExplorer [START_REF] Zhu | AverageExplorer: Interactive Exploration and Alignment of Visual Data Collections[END_REF] or ShadowDraw [START_REF] Lee | ShadowDraw: Real-Time User Guidance for Freehand Drawing[END_REF].

We first briefly discuss related works in Section 2. Section 3 then presents our DTI framework (Fig. 1a). Section 4 introduces our deep transformation modules and architecture (Fig. 1b) and discuss training details. Finally, Section 5 presents and analyzes our results (Fig. 1c).

Contributions. In this paper we present:

-a deep transformation-invariant clustering approach that jointly learns to cluster and align images, -a deep image transformation module to learn spatial alignment, color modifications and for the first time morphological transformations, -an experimental evaluation showing that our approach is competitive on standard image clustering benchmarks, improving over state-of-the-art on Fashion-MNIST and SVHN, and provides highly interpretable qualitative results even on challenging web image collections.

Code, data, models as well as more visual results are available on our project webpage1 .

Related work

Most recent approaches to image clustering focus on learning deep image representations, or features, on which clustering can be performed. Common strategies include autoencoders [START_REF] Xie | Unsupervised Deep Embedding for Clustering Analysis[END_REF][START_REF] Dizaji | Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization[END_REF][START_REF] Jiang | Variational Deep Embedding: An Unsupervised and Generative Approach to Clustering[END_REF][START_REF] Kosiorek | Stacked Capsule Autoencoders[END_REF], contrastive approaches [START_REF] Yang | Joint Unsupervised Learning of Deep Representations and Image Clusters[END_REF][START_REF] Chang | Deep Adaptive Image Clustering[END_REF][START_REF] Shaham | SpectralNet: Spectral Clustering Using Deep Neural Networks[END_REF], GANs [START_REF] Chen | InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets[END_REF][START_REF] Zhou | Deep Adversarial Subspace Clustering[END_REF][START_REF] Mukherjee | ClusterGAN : Latent Space Clustering in Generative Adversarial Networks[END_REF] and mutual information based strategies [START_REF] Hu | Learning Discrete Representations via Information Maximizing Self-Augmented Training[END_REF][START_REF] Häusser | Associative Deep Clustering: Training a Classification Network with no Labels[END_REF][START_REF] Ji | Invariant Information Clustering for Unsupervised Image Classification and Segmentation[END_REF]. Especially related to our work is [START_REF] Kosiorek | Stacked Capsule Autoencoders[END_REF] which leverages the idea of capsule [START_REF] Hinton | Transforming Auto-Encoders[END_REF] to learn equivariant image features, in a similar fashion of equivariant models [START_REF] Lenc | Understanding image representations by measuring their equivariance and equivalence[END_REF][START_REF] Tai | Equivariant Transformer Networks[END_REF]. However, our method aims at being invariant to transformations but not at learning a representation.

Another type of approach is to align images in pixel space using a relevant family of transformations, such as translations, rotations, or affine transformations to obtain more meaningful pixel distances before clustering them. Frey and Jojic first introduced transformation-invariant clustering [START_REF] Frey | Estimating Mixture Models of Images and Inferring Spatial Transformations Using the EM Algorithm[END_REF][START_REF] Frey | Fast, large-scale transformation-invariant clustering[END_REF][START_REF] Frey | Transformation-Invariant Clustering Using the EM Algorithm[END_REF] by integrating pixel permutations as a discrete latent variable within an Expectation Maximization (EM) [START_REF] Dempster | Maximum Likelihood from Incomplete Data via the EM Algorithm[END_REF] procedure for a mixture of Gaussians. Their approach was however limited to a finite set of discrete transformations. Congealing generalized the idea to continuous parametric transformations, and in particular affine transformations, initially by using entropy minimization [START_REF] Miller | Learning from One Example Through Shared Densities on Transforms[END_REF][START_REF] Learned-Miller | Data Driven Image Models through Continuous Joint Alignment[END_REF]. A later version using least square costs [START_REF] Cox | Least Squares Congealing for Unsupervised Alignment of Images[END_REF][START_REF] Cox | Least-Squares Congealing for Large Numbers of Images[END_REF] demonstrated the relation of this approach to the classical Lukas-Kanade image alignment algorithm [START_REF] Lucas | An Iterative Image Registration Technique with an Application to Stereo Vision[END_REF]. In its classical version, congealing only enables to align all dataset images together, but the idea was extended to clustering [START_REF] Liu | Simultaneous Alignment and Clustering for an Image Ensemble[END_REF][START_REF] Mattar | Unsupervised Joint Alignment and Clustering using Bayesian Nonparametrics[END_REF][START_REF] Li | Transformation invariant subspace clustering[END_REF], for example using a Bayesian model [START_REF] Mattar | Unsupervised Joint Alignment and Clustering using Bayesian Nonparametrics[END_REF], or in a spectral clustering framework [START_REF] Li | Transformation invariant subspace clustering[END_REF]. These works typically formulate difficult joint optimization problems and solve them by alternating between clustering and transformation optimization for each sample. They are thus limited to relatively small datasets and to the best of our knowledge were never compared to modern deep approaches on large benchmarks.

Deep learning was recently used to scale the idea of congealing for global alignment of a single class of images [START_REF] Annunziata | Jointly Aligning Millions of Images with Deep Penalised Reconstruction Congealing[END_REF] or time series [START_REF] Weber | Diffeomorphic Temporal Alignment Nets[END_REF]. Both works build on the idea of Spatial Transformer Networks [START_REF] Jaderberg | Spatial Transformer Networks[END_REF] (STN) that spatial transformation are differentiable and can be learned by deep networks. We also build upon STN, but go beyond single-class alignment to jointly perform clustering. Additionally, we extend the idea to color and morphological transformations. We believe our work is the first to use deep learning to perform clustering in pixel space by explicitly aligning images.

Deep Transformation-Invariant clustering

In this section, we first discuss a generic formulation of our deep transformation-invariant clustering approach, then derive two algorithms based on K-means [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] and Gaussian mixture model [START_REF] Dempster | Maximum Likelihood from Incomplete Data via the EM Algorithm[END_REF]. Notation: In all the rest of the paper, we use the notation a 1:n to refer to the set {a 1 , . . . , a n }.

DTI framework

Contrary to most recent image clustering methods which rely on feature learning, we propose to perform clustering in pixel space by making the clustering invariant to a family of transformations. We consider N image samples x 1:N and aim at grouping them in K clusters using a prototype method. More specifically, each cluster k is defined by a prototype c k , which can also be seen as an image, and prototypes are optimized to minimize a loss L which typically evaluates how well they represent the samples. We further assume that L can be written as a sum of a loss l computed over each sample:

L(c 1:K ) = N i=1 l(x i , {c 1 , . . . , c K }). (1)
Once the problem is solved, each sample x i will be associated to the closest prototype.

Our key assumption is that in addition to the data, we have access to a group of parametric transformations {T β , β ∈ B} to which we want to make the clustering invariant. For example, one can consider β ∈ R 6 and T β the 2D affine transformation parametrized by β. Other transformations are discussed in Section 4.1. Instead of finding clusters by minimizing the loss of Equation 1, one can minimize the following transformation-invariant loss:

L TI (c 1:K ) = N i=1 min β 1:K l(x i , {T β1 (c 1 ), . . . , T β K (c K )}). (2)
In this equation, the minimum over β 1:K is taken for each sample independently. This loss is invariant to transformations of the prototypes (see proof in Appendix B). Also note there is not a single optimum since the loss is the same if any prototype c k is replaced by T β (c k ) for any β ∈ B. If necessary, for example for visualization purposes, this ambiguity can easily be resolved by adding a small regularization on the transformations. The optimization problem associated to L TI is of course difficult. A natural approach, which we use as baseline (noted TI), is to alternatively minimize over transformations and clustering parameters. We show that performing such optimization using a gradient descent can already lead to improved results over standard clustering but is computationally expensive.

We experimentally show it is faster and actually better to instead learn K (deep) predictors f 1:K for each prototype, which aim at associating to each sample x i the transformation parameters f 1:K (x i ) minimizing the loss, i.e. to minimize the following loss:

L DTI (c 1:K , f 1:K ) = N i=1 l(x i , {T f1(xi) (c 1 ), . . . , T f K (xi) (c K )}), (3)
where predictors f 1:K are now shared for all samples. We found that using deep parameters predictors not only enables more efficient training but also leads to better clustering results especially with more complex transformations. Indeed, the structure and optimization of the predictors naturally regularize the parameters for each sample, without requiring any specific regularization loss, especially in the case of high numbers N of samples and transformation parameters.

In the next section we present concrete losses and algorithms. We then describe differentiable modules for relevant transformations and discuss parameter predictor architecture as well as training in Section 4.

Application to K-means and GMM

K-means. The goal of K-means algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] is to find a set of prototypes c 1:K such that the average Euclidean distance between each sample and the closest prototype is minimized. Following the reasoning of Section 3.1, the loss optimized in K-means can be transformed into a transformationinvariant loss:

L DTI K-means (c 1:K , f 1:K ) = N i=1 min k x i -T f k (xi) (c k ) 2 . (4)
Following batch gradient-based trainings [START_REF] Bottou | Convergence Properties of the K-Means Algorithms[END_REF] of K-means, we can then simply jointly minimize L DTI K-means over prototypes c 1:K and deep transformation parameter predictors f 1:K using a batch gradient descent algorithm. In practice, we initialize prototypes c 1:K with random samples and predictors

f 1:K such that ∀k, ∀x, T f k (x) = Id.
Gaussian mixture model. We now consider that data are observations of a mixture of K multivariate normal random variables X 1:K , i.e. X = k δ k,∆ X k where δ is the Kronecker function and ∆ ∈ {1, . . . , K} is a random variable defined by

P (∆ = k) = π k , with ∀k, π k > 0 and k π k = 1.
We write µ k and Σ k the mean and covariance of X k and G( . ; µ k , Σ k ) associated probability density function. The transformation-invariant negative log-likelihood can then be written:

L DTI GMM (µ 1:K , Σ 1:K , π 1:K , f 1:K ) = - N i=1 log K k=1 π k G x i ; T f k (xi) (µ k ), T * fk(xi) (Σ k ) , (5)
where T * is slightly modified version of T . Indeed, T may include transformations that one can apply to the covariance, such as spatial transformations, and other that would not make sense, such as additive color transformations. We jointly minimize L DTI GMM over Gaussian parameters, mixing probabilities, and deep transformation parameters f 1:K using a batch gradient-based EM procedure similar to [START_REF] Hosseini | Matrix Manifold Optimization for Gaussian Mixtures[END_REF][START_REF] Greff | Neural Expectation Maximization[END_REF][START_REF] Gepperth | Gradient-based training of Gaussian Mixture Models in High-Dimensional Spaces[END_REF] and detailed in Algorithm 1. In practice, we assume that pixels are independent resulting in diagonal covariance matrices.

In such gradient-based procedures, two constraints have to be enforced, namely the positivity and normalization of mixing probabilities π k and the non-negativeness of the diagonal covariance terms.

Algorithm 1: Deep Transformation-Invariant Gaussian Mixture Model Input: data X, number of clusters K, transformation T Output: cluster assignations, Gaussian parameters µ 1:K , Σ 1:K , deep predictors f 1:K Initialization: µ 1:K with random samples, Σ 1:K = 0.5, η 1:K = 1 and ∀k, ∀x, T f k (x) = Id while not converged do i. sample a batch of data points x 1:N ii. compute mixing probabilities:

π 1:K = softmax(η 1:K ) iii. compute per-sample Gaussian transformed parameters: ∀k, ∀i, μki = T f k (xi) (µ k ) and Σki = T * f k (xi) (Σ k ) + diag(σ 2 min ) iv. compute responsibilities: ∀k, ∀i, γ ki = π k G(xi ;μ ki , Σki ) j πj G(xi ;μji, Σji) (E-step) v. minimize expected negative log-likelihood w.r.t to {µ 1:K , Σ 1:K , η 1:K , f 1:K }: E[L DTI GMM ] = - N i=1 K k=1 γ ki log G(x i ; μki , Σki ) + log(π k ) (M-step) end
For the mixing probabilities constraints, we adopt the approach used in [START_REF] Hosseini | Matrix Manifold Optimization for Gaussian Mixtures[END_REF] and [START_REF] Gepperth | Gradient-based training of Gaussian Mixture Models in High-Dimensional Spaces[END_REF] which optimize mixing parameters η k used to compute the probabilities π k using a softmax instead of directly optimizing π k , which we write π 1:K = softmax(η 1:K ). For the variance non-negativeness, we introduce a fixed minimal variance value σ 2 min which is added to the variances when evaluating the probability density function. This approach is different from the one in [START_REF] Gepperth | Gradient-based training of Gaussian Mixture Models in High-Dimensional Spaces[END_REF] which instead use clipping, because we found training with clipped values was harder. In practice, we take σ min = 0.25.

Learning image transformations 4.1 Architecture and transformation modules

We consider a set of prototypes c 1:K we would like to transform to match a given sample x. To do so, we propose to learn for each prototype c k , a separate deep predictor which predicts transformation parameters β. We propose to model the family of transformations T β as a sequence of M parametric transformations such that, writing β = (β 1 , . . . , β M ),

T β = T M β M • . . . • T 1 β 1 .
In the following, we describe the architecture of transformation parameter predictors f 1:K , as well as each family of parametric transformation modules we use. Figure 1b shows our learned transformation process on a MNIST example.

Parameters prediction network.

For all experiments, we use the same parameter predictor network architecture composed of a shared ResNet [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] backbone truncated after the global average pooling, followed by K × M Multi-Layer Perceptrons (MLPs), one for each prototype and each transformation module. For the ResNet backbone, we use ResNet-20 for images smaller than 64 × 64 and ResNet-18 otherwise. Each MLP has the same architecture, with two hidden layers of 128 units.

Spatial transformer module. To model spatial transformations of the prototypes, we follow the spatial transformers developed by Jaderberg et al. [START_REF] Jaderberg | Spatial Transformer Networks[END_REF]. The key idea is to model spatial transformations as a differentiable image sampling of the input using a deformed sampling grid. We use affine T aff β , projective T proj β and thin plate spline T tps β [START_REF] Bookstein | Principal Warps: Thin-Plate Splines and the Decomposition of Deformations[END_REF] transformations which respectively correspond to 6, 8 and 16 (a 4x4 grid of control points) parameters.

Color transformation module. We model color transformation with a channel-wise diagonal affine transformation on the full image, which we write T col β . It has 2 parameters for greyscale images and 6 parameters for colored images. We first used a full affine transformation with 12 parameters, however the network was able to hide several patterns in the different color channels of a single prototype (Appendix C.4). Note that a similar transformation was theoretically introduced in capsules [START_REF] Kosiorek | Stacked Capsule Autoencoders[END_REF], but with the different goal of obtaining a color-invariant feature representation. Deep feature-based approaches often handle color images with a pre-processing step such as Sobel filtering [START_REF] Caron | Deep Clustering for Unsupervised Learning of Visual Features[END_REF][START_REF] Ji | Invariant Information Clustering for Unsupervised Image Classification and Segmentation[END_REF][START_REF] Kosiorek | Stacked Capsule Autoencoders[END_REF]. We believe the way we align colors of the prototypes to obtain color invariance in pixel space is novel, and it enables us to directly work with colored images without using any pre-processing or specific invariant features.

Morphological transformation module. We introduce a new transformation module to learn morphological operations [START_REF] Haralick | Image Analysis Using Mathematical Morphology[END_REF] such as dilation and erosion. We consider a greyscale image x ∈ R D of size U × V = D, we write x[u, v] the value of the pixel (u, v) for u ∈ {1, . . . , U } and v ∈ {1, . . . , V }. Given a 2D region A, the dilation of x by A, D A (x) ∈ R D , is defined by

D A (x)[u, v] = max (u ,v )∈A x[u + u , v + v ] and its erosion by A, E A (x) ∈ R D , is defined by E A (x)[u, v] = min (u ,v )∈A x[u + u , v + v ].
Directly learning the region A which parametrizes these transformations is challenging, we thus propose to learn parameters (α, a) for the following soft version of these transformations:

T mor (α,a) (x)[u, v] = (u ,v )∈W x[u + u , v + v ] • a[u + u , v + v ] • e αx[u+u ,v+v ] (u ,v )∈W a[u + u , v + v ] • e αx[u+u ,v+v ] , ( 6
)
where W is a fixed set of 2D positions, α is a softmax (positive values) or softmin (negative values) parameter and a is a set of parameters with values between 0 and 1 defined for every position (u , v ) ∈ W . Parameters a can be interpreted as an image, or as a soft version of the region A used for morphological operations. Note that if a

[u , v ] = 1 {(u ,v )∈A} , when α → +∞ (resp. -∞), it successfully emulates D A (resp. E A ).
In practice, we use a grid of integer positions around the origin of size 7 × 7 for W . Note that since morphological transformations do not form a group, transformation-invariant denomination is slightly abusive.

Training

We found that two key elements were critical to obtain good results: empty cluster reassignment and curriculum learning. We then discuss further implementation details and computational cost.

Empty cluster reassignment. Similar to [START_REF] Caron | Deep Clustering for Unsupervised Learning of Visual Features[END_REF], we adopt an empty cluster reassignment strategy during our clustering optimization. We reinitialize both prototype and deep predictor of "tiny" clusters using the parameters of the largest cluster with a small added noise. In practice, the size of balanced clusters being N/K, we define "tiny" as less than 20% of N/K.

Curriculum learning. Learning to predict transformations is a hard task, especially when the number of parameters is high. To ease learning, we thus adopt a curriculum learning strategy by gradually adding more complex transformation modules to the training. Given a target sequence of transformations to learn, we first train our model without any transformation -or equivalently with an identity module -then iteratively add subsequent modules once convergence has been reached. We found this is especially important when modeling local deformations with complex transformations with many parameters, such as TPS and morphological transformations. Intuitively, prototypes should first be coarsely aligned before attempting to refine the alignment with more complex transformations.

Implementation details. Both clustering parameters and parameter prediction networks are learned jointly and end-to-end using Adam optimizer [START_REF] Kingma | A Method for Stochastic Optimization[END_REF] with a 10 -6 weight decay on the neural network parameters. We sequentially add transformation modules at a constant learning rate of 0.001 then divide the learning rate by 10 after convergence -corresponding to different numbers of epochs depending on the dataset characteristics -and train for a few more epochs with the smaller learning rate. We use a batch size of 64 for real photograph collections and 128 otherwise.

Computational cost. Training DTI K-means or DTI GMM on MNIST takes approximately 50

minutes on a single Nvidia GeForce RTX 2080 Ti GPU and full dataset inference takes 30 seconds. We found it to be much faster than directly optimizing transformation parameters (TI clustering) for which convergence took more than 10 hours of training.

Experiments

In this section, we first analyze our approach and compare it to state-of-the-art, then showcase its interest for image collection analysis and visualization.

Analysis and comparisons

Similar to previous work on image clustering, we evaluate our approach with global classification accuracy (ACC), where a cluster-to-class mapping is computed using the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF], Comparison on standard benchmarks. In Table 1, we report our results on standard image clustering benchmarks, i.e. digit datasets (MNIST [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF], USPS [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF]), a clothing dataset (Fashion-MNIST [START_REF] Xiao | Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms[END_REF]) and a face dataset (FRGC [START_REF] Phillips | Overview of the Face Recognition Grand Challenge[END_REF]). We also report results for SVHN [START_REF] Netzer | Reading Digits in Natural Images with Unsupervised Feature Learning[END_REF] where concurrent methods use pre-processing to remove color bias. In the table, we separate representation-based from pixel-based methods and mark results using data augmentation or manually selected features as input. Note that our results depend on initialization, we provide detailed statistics in Appendix C.1. Our DTI clustering is fully unsupervised and does not require any data augmentation, ad hoc features, nor any hyper-parameter while performing clustering directly in pixel space. We report average performances and performances of the minimal loss run which we found to correlate well with high performances (Appendix C.2). Because this non-trivial criterion allows to automatically select a run in a fully unsupervised way, we argue it can be compared to average results from competing methods which don't provide such criterion. First, DTI clustering achieves competitive results on all datasets, in particular improving state-ofthe-art by a significant margin on SVHN and Fashion-MNIST. For SVHN, we first found that the Table 2: Augmented and specific datasets. Clustering accuracy (%) with standard deviation for methods applied on raw images (no pre-processing). We used 10 runs for our method and 5 for the baselines. prototypes quality was harmed by digits on the side of the image. To pay more attention to the center digit, we weighted the clustering loss by a Gaussian weight (σ = 7). It led to better prototypes and allowed us to improve over all concurrent methods by a large margin. Compared to representationbased methods, our pixel-based clustering is highly interpretable. Figure 2a shows standard GMM prototypes and our prototypes learned with DTI GMM which appear to be much sharper than standard ones. This directly stems from the quality of the learned transformations, visualized in Figure 2b.

Our transformation modules can successfully align the prototype, adapt the thickness and apply local elastic deformations. More alignment results are available on our project webpage.

Augmented and specific datasets. DTI clustering also works on small, colored and misaligned datasets. In Table 2, we highlight these strengths on specifics datasets generated from MNIST: MNIST-1k is a 1000 images subset, MNIST-color is obtained by randomly selecting a color for the foreground and background and affNIST-test2 is the result of random affine transformations. We used an online implementation 3 for VaDE [START_REF] Jiang | Variational Deep Embedding: An Unsupervised and Generative Approach to Clustering[END_REF] and official ones for IMSAT [START_REF] Hu | Learning Discrete Representations via Information Maximizing Self-Augmented Training[END_REF] and IIC [START_REF] Ji | Invariant Information Clustering for Unsupervised Image Classification and Segmentation[END_REF] to obtain baselines. Our results show that the performances of DTI clustering is barely affected by spatial and color transformations, while baseline performances drop on affNIST-test and are almost chance on MNIST-color. Figure 2a shows the quality and interpretability of our cluster centers on affNIST-test and MNIST-color. DTI clustering also seems more data-efficient than the baselines we tested.

Ablation on MNIST. In Table 3, we conduct an ablation study on MNIST of our full model trained following Section 4.2 with affine, morphological and TPS transformations. We first explore the effect of transformation modules. Their order is not crucial, as shown by similar minLoss performances, but can greatly affect the stability of the training, as can be seen in the average results. Each module contributes to the final performance, affine transformations being the most important. We then validate our training strategy showing that both empty cluster reassignment and curriculum learning for the different modules are necessary. Finally, we directly optimize the loss of Equation 2 (TI clustering) by optimizing the transformation parameters for each sample at each iteration of the batch clustering algorithm, without using our parameter predictors. With rich transformations which have many parameters, such as TPS and morphological ones, this approach fails completely. Using only affine transformations, we obtain results clearly superior to standard clustering, but worse than ours.

Application to web images

One of the main interest of our DTI clustering is that it allows to discover trends in real image collections. All images are resized and center cropped to 128×128. The selection of the number of clusters is a difficult problem and is discussed in Appendix C.3.

In Figure 1c, we show examples of prototypes discovered in very large unfiltered sets (15k each) of Instagram images associated to different hashtags4 using DTI GMM applied with 40 clusters. While many images are noise and are associated to prototypes which are not easily interpretable, we show prototypes where iconic photos and poses can be clearly identified. To the best of our knowledge, we believe we are the first to demonstrate this type of results from raw social network image collections. Comparable results in AverageExplorer [START_REF] Zhu | AverageExplorer: Interactive Exploration and Alignment of Visual Data Collections[END_REF], e.g. on Santa images, could be obtained using ad hoc features and user interactions, while our results are produced fully automatically. Figure 3 shows qualitative clustering results on MegaDepth [START_REF] Li | MegaDepth: Learning Single-View Depth Prediction from Internet Photos[END_REF] and WikiPaintings [START_REF] Karayev | Recognizing Image Style[END_REF]. Similar to our results on image clustering benchmarks, our learned prototypes are more relevant and accurate than the ones obtained from standard clustering. Note that some of our prototypes are very sharp: they typically correspond to sets of photographs between which we can accurately model deformations, e.g. scenes that are mostly planar, with little perspective effects. On the contrary, more unique photographs and photographs with strong 3D effects that we cannot model will be associated to less interpretable and blurrier prototypes, such as the ones in the last two columns of Figure 3b. In Figure 3b, in addition to the prototypes discovered, we show examples of images contained in each cluster as well as the aligned prototype. Even for such complex images, the simple combination of our color and spatial modules manages to model real image transformations like illumination variations and viewpoint changes. More web image clustering results are shown on our project webpage.

Conclusion

We have introduced an efficient deep transformation-invariant clustering approach in raw input space.

Our key insight is the online optimization of a single clustering objective over clustering parameters and deep image transformation modules. We demonstrate competitive results on standard image clustering benchmarks, including improvements over state-of-the-art on SVHN and Fashion-MNIST.

We also demonstrate promising results for real photograph collection clustering and visualization. Finally, note that our DTI clustering framework is not specific to images and can be extended to other types of data as long as appropriate transformation modules are designed beforehand.

Broader Impact

The impact of clustering mainly depends on the data it is applied on. For instance, adding structure in user data can raise ethical concerns when users are assimilated to their cluster, and receive targeted advertisement and newsfeed. However, this is not specific to our method and can be said of any clustering algorithm. Also note that while our clustering can be applied for example to data from social media, the visual interpretation of the clusters it returns via the cluster centers respects privacy much better than showing specific examples from each cluster.

Because our method provides highly interpretable results, it might bring increased understanding of clustering algorithm results for the broader public, which we think may be a significant positive impact. [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF] 10,000 10 1×28×28 aff-morpho-tps USPS [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF] 9,298 10 1×16×16 col-aff-tps Fashion-MNIST [START_REF] Xiao | Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms[END_REF] 70,000 10 1×28×28 col-aff-tps FRGC [START_REF] Phillips | Overview of the Face Recognition Grand Challenge[END_REF] 2,462 20 3×32×32 col-aff-tps SVHN [START_REF] Netzer | Reading Digits in Natural Images with Unsupervised Feature Learning[END_REF] 99,289 + unlabeled extra -MNIST and MNIST-test [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF] which respectively correspond to full and test subset of MNIST dataset. They depict binary white handwritten digits centered over a black background. -USPS [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF] is a handwritten digit dataset from USPS composed of greyscale images.

A Dataset descriptions

-Fashion-MNIST [START_REF] Xiao | Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms[END_REF] is a 10-class clothing dataset composed of greyscale images of cloth over black background. Classes are: T-shirt, trouser, pullover, dress, coat, sandal, shirt, sneaker, bag, ankle boot. -FRGC [START_REF] Phillips | Overview of the Face Recognition Grand Challenge[END_REF] is a colored face dataset. We use a subset of this dataset introduced in [START_REF] Yang | Joint Unsupervised Learning of Deep Representations and Image Clusters[END_REF], where 20 subjects are selected and each image is cropped and resized to a constant size of 32×32. -SVHN [START_REF] Netzer | Reading Digits in Natural Images with Unsupervised Feature Learning[END_REF] is composed of digits extracted from house numbers cropped from Google Street View images. Following standard practice for clustering, we use both labeled samples (99,289) and unlabeled extra samples (~530k) for training and evaluate on the labeled subset only. -affNIST-test is the test split of affNIST (https://www.cs.toronto.edu/ tijmen/affNIST/) an augmented dataset of MNIST where random affine transformations are applied. -MNIST-1k: we randomly sampled 1,000 images from the test split of MNIST.

-MNIST-color: we augmented MNIST with random colors for background and foreground.

B Transformation invariance

We consider N image samples x 1:N , K prototypes c 1:K and a group of parametric transformations {T β , β ∈ B}. For β 1 , β 2 ∈ B, we write β 1 β 2 ∈ B the element such that T β1β2 = T β1 • T β2 . We have, for any α 1 , . . . , α K ∈ B:

L TI ({c 1 , . . . , c K }) = L TI ({T α1 (c 1 ), . . . , T α K (c K )}). Indeed: L TI ({T α1 (c 1 ), . . . , T α K (c K )}) = N i=1 min {β1,...,β K }∈B K l(x i , {T β1 • T α1 (c 1 ), . . . , T β K • T α K (c K )}) = N i=1 min {β1,...,β K }∈B K l(x i , {T β1α1 (c 1 ), . . . , T β K α K (c K )}) = N i=1 min {β 1 ,...,β K }∈B K l(x i , {T β 1 (c 1 ), . . . , T β K (c K )}) = L TI ({c 1 , . . . , c K }),
using the variable change β k = β k α k , which is possible because for any α ∈ B, αB = B as we assumed to have a group of transformations.

In some specific cases, the loss is also invariant to the samples, in particular when the loss l is invariant to joint transformation of the prototype and the samples, i.e. for any β ∈ B, l(x i , {c 1 , . . . , c K } = l(T β (x i ), {T β (c 1 ), . . . , T β (c K )}. This is the case for example for K-means with a group of isometric transformations (e.g. rigid transformations), and it is also the case for GMM with the group of affine transformations applied to both the mean and covariance mixture parameters.

Note that we also tried to transform the samples to match the prototypes, which would lead to an invariance to sample transformation. However, a trivial solution to corresponding optimization problem is to learn "empty" prototypes and transformations of the samples into empty images. For examples, for the MNIST case with affine transformations, we observed that completely black prototypes were learned and any digit was transformed into a black image. Although a regularization term could have prevented such behaviour, we argue that keeping raw samples as target and transforming the prototypes is simpler and effective. Similar to standard K-means and GMM, there is a variation in performances depending on the random initialization. We experimentally found that: (i) runs seem to be mainly grouped into distinct modes, each corresponding to roughly the same clustering quality; (ii) a run with a low loss usually leads to high clustering performances. We launched 100 runs on MNIST-test dataset and plot the loss with respect to the accuracy for each run in Figure 4. Except 2 outliers for the 100 runs, the runs with lower loss correspond to the runs with better performances. This is verified in most of our experiments, where the minLoss criterion clearly improves over the average performance.

C Analysis C.1 Statistics on standard clustering benchmarks

C.3 Effect of the number of clusters K

Similar to many clustering methods, the selection of the number of clusters is a challenge. We investigated if a purely quantitative analysis could be applied to select K. In Figure 5a, we plot the loss of DTI-Kmeans as a function of the number of clusters for MNIST-test (left) and Notre-Dame (right). For MNIST-test, it is clear an elbow method could be applied to select the good number of clusters. For Notre-Dame, the quantitative analysis is not as conclusive but in this case, the correct number of clusters is not clearly defined. In practice, we did not find the qualitative results on internet photo collections to be very sensitive to this choice, as shown in Figure 5b where learned prototypes are mostly consistent across the different clustering results.

C.4 Constraining color transformation

While evaluating our approaches on real photograph collections, we experimentally observed that a full affine color transformation module (12 parameters) was too flexible and as a result, prototypes were able to learn different patterns hidden in each color channel. In Figure 6, we show each R, G and B channel as a greyscale image for two prototypes learned using a full affine color transformation module. One can see that a second pattern is hidden in particular in the green channels. To avoid this effect, we restricted the color transformation module to be a diagonal affine transformation corresponding to 6 parameters in total.

  (a) Classical versus Deep Transformation-Invariant clustering (b) Deep transformation module T f k (c) Prototypes learned from unfiltered Instagram images associated to different hashtags

Figure 1 :

 1 Figure 1: Overview. (a) Given a sample x i and prototypes c 1 and c 2 , standard clustering such as K-means assigns the sample to the closest prototype. Our DTI clustering first aligns prototypes to the sample using a family of parametric transformations -here rotations -then picks the prototype whose alignment yields the smallest distance. (b) We predict alignment with deep learning. Given an image x i , each parameter predictor f k predicts parameters for a sequence of transformations -here affine T aff βaff , morphological T mor βmor , and thin plate spline T tps βtps -to align prototype c k to x i . (c) Examples of interpretable prototypes discovered from large images sets (15k each) associated to hashtags in Instagram using our DTI clustering with 40 clusters. Each cluster contains from 200 to 800 images.

  (a) Prototypes learned for different datasets (b) Transformations predicted for all prototypes for 4 MNIST images

Figure 2 :

 2 Figure 2: Qualitative results. (a) compares prototypes learned from GMM and our DTI GMM, (b) shows transformed prototypes given query samples from MNIST and highlight the closest prototype. and Normalized Mutual Information (NMI). Datasets and corresponding transformation modules we used are described in Appendix A.

Figure 3 :

 3 Figure 3: Qualitative results on real photographs. (a) Clustering results from photographs of different locations in [35] (1,089 Sacre Coeur top-left, 1,688 Trevi fountain top-right, 2,625 Notre-Dame bottom-left) and 980 Baroque portraits from [26] (bottom-right). (b) Clustering results from 1,892 Florence cathedral images from [35]. Top row shows learned prototypes while the three bottom rows show examples of images from each cluster and aligned prototypes. These clusters contain respectively 44, 154, 134, 64, 71, 133, 85 and 64 images. The left six examples are successful clusters while the two right clusters are relative failure cases.

Figure 4 :

 4 Figure 4: Accuracy/loss correlation. We report loss and accuracy for DTI Kmeans on MNIST-test.

  Loss w.r.t varying numbers of clusters for MNIST-test (left) and Notre-Dame (right) (b) Prototypes learned on Notre-Dame for different numbers of clusters

Figure 5 :

 5 Figure 5: Effect of K. (a) We report the loss of DTI K-means for different numbers of clusters. For MNIST-test (left), the loss is averaged over 5 runs and for Notre-Dame (right), the loss corresponds to a single run. (b) We show the prototypes learned on Notre-Dame for even numbers of clusters.

Figure 6 :

 6 Figure 6: Learned prototypes and RGB decomposition. Two examples of learned prototypes (first column) on Florence cathedral collection from [35] using a full color transformation module (12 parameters). The 3 right columns correspond to R, G and B channels rescaled between 0 and 1. Note how the green channel is used to hide a completely different pattern from the other 2 channels.

Table 1 :

 1 Comparisons. We report ACC and NMI in % on standard clustering benchmarks. Symbols mark methods that use data augmentation ( ) and manually selected features as input ( § for pretrained features from best VaDE run, † for GIST features, ‡ for Sobel filters) and are thus not directly comparable. For SVHN, we also report our results with our Gaussian weighted loss ( ). Eval column refers to the aggregate used: best run (max), average (avg) or run with minimal loss (minLoss). 96.6 94.6 86.4 88.2 61.2 63.7 39.6 48.7 36.4 / 44.5 10 minLoss 97.2 93.8 98.0 95.3 89.8 89.5 57.4 64.1 41.1 49.7 39.6 / 62.6

				MNIST	MNIST-test	USPS	F-MNIST	FRGC		SVHN
	Method	Runs Eval	ACC NMI ACC NMI ACC NMI ACC NMI ACC NMI	ACC
	Clustering on a learned feature
	DEC [48, 50]	9	max	86.3 83.4 85.6 83.0 76.2 76.7 51.8 54.6 37.8 50.5	-
	InfoGAN [6, 41]	5	max	89.0 86.0	-	-	-	-	61.0 59.0	-	-	-
	VaDE [25, 50]	10	max	94.5 87.6	-	-	56.6 51.2 57.8 63.0	-	-	-
	ClusterGAN [41] 5	max	95.0 89.0	-	-	-	-	63.0 64.0	-	-	-
	JULE [49]	3	avg	96.4 91.3 96.1 91.5 95.0 91.3 56.3 60.8 46.1 57.4	-
	DEPICT [10]	5	avg	96.5 91.7 96.3 91.5 96.4 92.7 39.2 39.2 47.0 61.0	-
	DSCDAN [50]	10	avg	97.8 94.1 98.0 94.6 86.9 85.7 66.2 64.5	-	-	-
	Clustering on a learned feature with data augmentation and/or ad hoc data representation
	SpectralNet [44]	5	avg	97.1 § 92.4 § -	-	-	-	-	-	-	-	-
	IMSAT [22]	12	avg	98.4	-	-	-	-	-	-	-	-	-	57.3 †
	ADC [18]	20	avg	98.7	-	-	-	-	-	-	-43.7	-	38.6
	SCAE [28]	5	avg	98.7	-	-	-	-	-	-	-	-	-	55.3 ‡
	IIC [24]	5	avg	98.4	-	-	-	-	-	-	-	-	-	-
		5 minLoss 99.2	-	-	-	-	-	-	-	-	-	-
	Clustering on pixel values
	K-means [38]	10	avg	54.8 50.2 55.9 51.2 65.3 61.2 54.1 51.4 22.7 26.5	12.2
	GMM [9]	10	avg	54.2 51.7 55.6 54.7 66.0 60.9 49.7 51.2 24.2 27.9	11.6
	DTI K-means	10	avg	97.3 94.0

DTI GMM 10 avg 95.9 93.2 97.8 94.7 84.5 87.2 59.6 62.2 40.1 48.9 36.7 / 57.4 10 minLoss 97.1 93.7 98.0 95.1 87.3 89.0 68.2 66.3 41.6 51.1 39.5 / 63.3

Table 3 :

 3 Ablation study on MNIST. Clustering accuracy (%) over 10 runs.

						Method	Avg	MinLoss
						DTI clustering (aff-morpho-tps)	97.3	97.2
	Method	Eval	MNIST-1k	MNIST-color	affNIST-test	ordering: aff-tps-morpho	95.5	96.9
	VaDE [25] IMSAT [22] IIC [24]	avg avg avg minLoss	49.6 (5.6) 67.9 (2.3) 63.4 (0.4) 63.2	11.9 (1.2) 10.6 (0.1) 10.6 (0.0) 10.6	Div. 18.2 (2.6) 57.6 (0.0) 57.6	ordering: morpho-aff-tps w/o morphological w/o thin plate spline w/o affine affine only	27.5 94.8 90.0 85.1 90.1	97.0 95.8 82.5 96.8 90.5
	DTI K-means	avg	79.8 (6.9)	96.7 (0.1)	95.5 (3.3)	w/o empty cluster reassignment	80.9	78.6
		minLoss	90.5	96.8	97.0	w/o curriculum learning	83.9	78.9
	DTI GMM	avg	80.8 (7.2)	96.0 (0.2)	93.3 (5.9)	TI clustering (aff-morpho-tps, 1 run)	26.3	26.3
		minLoss	87.1	95.8	97.0	TI clustering (affine only)	73.0	73.1

Table 4 :

 4 Datasets and transformation sequences used

	Dataset	Samples	Classes Dimension Transformation sequence
	Standard
	MNIST [31]	70,000	10	1×28×28	aff-morpho-tps
	MNIST-test

Table 4

 4 summarizes dataset characteristics as well as the transformation sequences used. Datasets are:

Table 5 :

 5 Detailed results. We report statistics of our results on standard clustering benchmarks. For SVHN, we also report results with our Gaussian weighted loss ( ).

				MNIST MNIST-test	USPS	F-MNIST	FRGC	SVHN
	Method	Runs	Stat	ACC NMI ACC NMI ACC NMI ACC NMI ACC NMI	ACC
	DTI K-means 10	avg	97.3 94.0 96.6 94.6 86.4 88.2 61.2 63.7 39.6 48.7 36.4 / 44.5
		10	std	0.1 0.1 4.1 1.5 4.1 1.6 2.0 0.3 1.7 2.2 1.9 / 9.6
		10	min	97.1 93.8 84.9 90.4 83.2 87.1 57.4 63.2 35.9 43.9 34.5 / 37.0
		10 median 97.3 94.0 97.9 95.1 85.0 87.4 61.9 63.3 40.2 49.3 35.8 / 39.6
		10	max	97.5 94.2 98.0 95.3 96.4 92.0 63.3 64.2 41.1 51.4 39.6 / 62.6
		10 minLoss 97.2 93.8 98.0 95.3 89.8 89.5 57.4 64.1 41.1 49.7 39.6 / 62.6
	DTI GMM	10	avg	95.9 93.2 97.8 94.7 84.5 87.2 59.6 62.2 40.1 48.9 36.7 / 57.4
		10	std	3.9 1.5 0.1 0.2 2.0 0.8 4.7 2.4 1.4 1.5 2.3 / 5.1
		10	min	84.7 89.1 97.7 94.4 82.0 86.3 56.1 59.7 38.4 46.8 34.0 / 49.9
		10 median 97.1 93.7 97.8 94.7 84.3 87.1 57.2 60.9 39.6 49.1 36.4 / 57.4
		10	max	97.3 93.9 98.0 95.1 87.3 89.0 68.2 66.3 41.9 51.1 39.5 / 64.6
		10 minLoss 97.1 93.7 98.0 95.1 87.3 89.0 68.2 66.3 41.6 51.1 39.5 / 63.3
	C.2 Accuracy and loss correlation
						7.0
						6.9
					Loss (x 1e3)	6.6 6.7 6.8
						6.5
						6.4	0.75	0.80	0.85	ACC	0.90	0.95	1.00

http://imagine.enpc.fr/~monniert/DTIClustering/

https://www.cs.toronto.edu/~tijmen/affNIST/

https://github.com/GuHongyang/VaDE-pytorch

https://github.com/arc298/instagram-scraper was used to scrape photographs

Acknowledgements

This work was supported in part by ANR project EnHerit ANR-17-CE23-0008, project Rapid Tabasco, gifts from Adobe and HPC resources from GENCI-IDRIS (Grant 2020-AD011011697). We thank Bryan Russell, Vladimir Kim, Matthew Fisher, François Darmon, Simon Roburin, David Picard, Michaël Ramamonjisoa, Vincent Lepetit, Elliot Vincent, Jean Ponce, William Peebles and Alexei Efros for inspiring discussions and valuable feedback.