Recurrent Pixel Embedding for Instance Grouping

Shu Kong, Charless Fowlkes

Introduction

The successes of deep convolutional neural nets (CNNs) at image classification has spawned a flurry of work in computer vision on adapting these models to pixel-level image understanding tasks, such as boundary detection , semantic segmentation , optical flow , and pose estimation . The key ideas that have enabled this adaption thus far are: (1) deconvolution schemes that allow for upsampling coarse pooled feature maps to make detailed predictions at the spatial resolution of individual pixels , (2) skip connections and hyper-columns which concatenate representations across multi-resolution feature maps , (3) atrous convolution which allows efficient computation with large receptive fields while maintaining spatial resolution , and (4) fully convolutional operation which handles variable sized input images.

In contrast, there has been less innovation in the development of specialized loss functions for training. Pixel-level labeling tasks fall into the category of structured output prediction , where the model outputs a structured object (e.g., a whole image parse) rather than a scalar or categorical variable. However, most CNN pixel-labeling architectures are simply trained with loss functions that decompose into a simple (weighted) sum of classification or regression losses over individual pixel labels.

The need to address the output space structure is more apparent when considering problems where the set of output labels isn’t fixed. Our motivating example is object instance segmentation, where the model generates a collection of segments corresponding to object instances. This problem can’t be treated as k-way classification since the number of objects isn’t known in advance. Further, the loss should be invariant to permutations of the instance labels within the same semantic category.

As a result, most recent successful approaches to instance segmentation have adopted more heuristic approaches that first use an object detector to enumerate candidate instances and then perform pixel-level segmentation of each instance . Alternately one can generate generic proposal segments and then label each one with a semantic detector . In either case the detection and segmentation steps can both be mapped to standard binary classification losses. While effective, these approaches are somewhat unsatisfying since: (1) they rely on the object detector and non-maximum suppression heuristics to accurately “count” the number of instances, (2) they are difficult to train in an end-to-end manner since the interface between instance segmentation and detection is non-differentiable, and (3) they underperform in cluttered scenes as the assignment of pixels to detections is carried out independently for each detectionThis is less a problem for object proposals that are jointly estimated by bottom-up segmentation (e.g., MCG and COB ). However, such generic proposal generation is not informed by the top-down semantics..

Here we propose to directly tackle the instance grouping problem in a unified architecture by training a model that labels pixels with unit-length vectors that live in some fixed-dimension embedding space (Fig. 1). Unlike k-way classification where the target vectors for each pixel are specified in advance (i.e., one-hot vectors at the vertices of a k-1 dimensional simplex) we allow each instance to be labeled with an arbitrary embedding vector on the sphere. Our loss function simply enforces the constraint that the embedding vectors used to label different instances are far apart. Since neither the number of labels, nor the target label vectors are specified in advance, we can’t use standard soft-max thresholding to produce a discrete labeling. Instead, we utilize a variant of mean-shift clustering which can be viewed as a recurrent network whose fixed point identifies a small, discrete set of instance label vectors and concurrently labels each pixel with one of the vectors from this set.

This framework is largely agnostic to the underlying CNN architecture and can be applied to a range of low, mid and high level visual tasks. Specifically, we carry out experiments showing how this method can be used for boundary detection, object proposal generation and semantic instance segmentation. Even when a task can be modeled by a binary pixel classification loss (e.g., boundary detection) we find that the grouping loss guides the model towards higher-quality feature representations that yield superior performance to classification loss alone. The model really shines for instance segmentation, where we demonstrate a substantial boost in object proposal generation (improving the state-of-the-art average recall for 10 proposals per image from 0.56 to 0.77). To summarize our contributions: (1) we introduce a simple, easily interpreted end-to-end model for pixel-level instance labeling which is widely applicable and highly effective, (2) we provide theoretical analysis that offers guidelines on setting hyperparameters, and (3) benchmark results show substantial improvements over existing approaches.

Related Work

Common approaches to instance segmentation first generate region proposals or class-agnostic bounding boxes, segment the foreground objects within each proposal and classify the objects in the bounding box . introduce a fully convolutional approach that includes bounding box proposal generation in end-to-end training. Recently, “box-free” methods avoid some limitations of box proposals (e.g. for wiry or articulated objects). They commonly use Faster RCNN to produce “centeredness” score on each pixel and then predict binary instance masks and class labels. Other approaches have been explored for modeling joint segmentation and instance labeling jointly in a combinatorial framework (e.g., ) but typically don’t address end-to-end learning. Alternately, recurrent models that sequentially produce a list of instances offer another approach to address variable sized output structures in a unified manner.

The most closely related to ours is the associative embedding work of , which demonstrated strong results for grouping multi-person keypoints, and unpublished work from on metric learning for instance segmentation. Our approach extends on these ideas substantially by integrating recurrent mean-shift to directly generate the final instances (rather than heuristic decoding or thresholding distance to seed proposals). There is also an important and interesting connection to work that has used embedding to separate instances where the embedding is directly learned using a supervised regression loss rather than a pairwise associative loss. train a regressor that predicts the distance to the contour centerline for boundary detection, while predict the distance transform of the instance masks which is then post-processed with watershed transform to generate segments. predict an embedding based on scene depth and direction towards the instance center (like Hough voting).

Finally, we note that these ideas are related to work on using embedding for solving pairwise clustering problems. For example, normalized cuts clusters embedding vectors given by the eigenvectors of the normalized graph Laplacian and the spatial gradient of these embedding vectors was used in as a feature for boundary detection. Rather than learning pairwise similarity from data and then embedding prior to clustering (e.g., ), we use a pairwise loss but learn the embedding directly. Our recurrent mean-shift grouping is reminiscent of other efforts that use unrolled implementations of iterative algorithms such as CRF inference or bilateral filtering . Unlike general RNNs which are often difficult to train, our recurrent model has fixed parameters that assure interpretable convergent dynamics and meaningful gradients during learning.

Pairwise Loss for Pixel Embeddings

In this section we introduce and analyze the loss we use for learning pixel embeddings. This problem is broadly related to supervised distance metric learning and clustering but adapted to the specifics of instance labeling where the embedding vectors are treated as labels for a variable number of objects in each image.

In the discussion that follows we think of the similarity in terms of the inner product between the projected embedding vectors (e.g., $\frac{x_{i}}{\|x_{i}\|}$ ) which live on the surface of a $(D-1)$ dimensional sphere. Other common similarity metrics utilize Euclidean distance with a squared exponential kernel or sigmoid function . We prefer the cosine metric since it is invariant to the scale of the embedding vectors, decoupling the loss from model design choices such as weight decay or regularization that limit the dynamic range of Euclidean distances.

Our goal is to learn an embedding so that pixels with the same label (positive pairs with $y_{i}=y_{j}$ ) have the same embedding (i.e. $s_{ij}=1$ ). To avoid a trivial solution where all the embedding vectors are the same, we impose the additional constraint that pairs from different instances (negative pairs with $y_{i}\neq y_{j}$ ) are placed far apart. To provide additional flexibility, we include a weight $w_{i}$ in the definition of the loss which specifies the importance of a given pixel. The total loss over all pairs and training images is:

where $N_{k}$ is the number of pixels in the $k$ -th image ( $M$ images in total), and $w^{k}_{i}$ is the pixel pair weight associated with pixel $i$ in image $k$ . The hyper-parameter $\alpha$ controls the maximum margin for negative pairs of pixels, incurring a penalty if the embeddings for pixels belonging to the same group have an angular separation of less than $\cos^{-1}(\alpha)$ . Positive pairs pay a penalty if they have a similarity less than $1$ . Fig. 2 shows a graph of the loss function. argue that the constant slope of the margin loss is more robust, e.g., than squared loss.

We carry out a simple theoretical analysis which provides a guide for setting the weights $w_{i}$ and margin hyperparameter $\alpha$ in the loss function. Proofs can be found in the appendix.

We first examine the role of embedding dimension and instance size on the training loss.

For $n$ vectors $\{{\bf x}_{1},\dots,{\bf x}_{n}\}$ , the total intra-pixel similarity is bounded as $\sum_{i\neq j}{\bf x}_{i}^{T}{\bf x}_{j}\geq-\sum_{i=1}^{n}\|{\bf x}_{i}\|_{2}^{2}$ . In particular, for $n$ vectors on the hypersphere where $\|{\bf x}_{i}\|_{2}=1$ , we have $\sum_{i\neq j}{\bf x}_{i}^{T}{\bf x}_{j}\geq-n$ .

This proposition indicates that the total cosine similarity (and hence the loss) for a set of embedding vectors has a constant lower bound that does not depend on the dimension of the embedding space (a feature lacking in Euclidean embeddings). In particular, this type of analysis suggests a natural choice of pixel weighting $w_{i}$ . Suppose a training example contains $Q$ instances and ${\cal I}_{q}$ denotes the set of pixels belonging to a particular ground-truth instance $q$ . We can write

where the first term on the r.h.s. corresponds to contributions to the loss function for positive pairs while the second corresponds to contributions from negative pairs. Setting $w_{i}=\frac{1}{|{\cal I}_{q}|}$ for pixels $i$ belonging to ground-truth instance $q$ assures that each instance contributes equally to the loss independent of size. Furthermore, when the embedding dimension $D\geq Q$ , we can simply embed the data so that the instance means $\mu_{k}=\frac{1}{|{\cal I}_{q}|}\sum_{i\in{\cal I}_{q}}{\bf x}_{i}$ are along orthogonal axes on the sphere. This zeros out the second term on the r.h.s., leaving only the first term which is bounded $0\leq\sum_{q=1}^{Q}\left\|\frac{1}{|{\cal I}_{q}|}\sum_{i\in{\cal I}_{q}}{\bf x}_{i}\right\|^{2}\leq Q$ , and translates to corresponding upper and lower bounds on the loss that are independent of the number of pixels and embedding dimension (so long as $D\geq Q$ ).

Pairwise weighting schemes have been shown important empirically and class imbalance can have a substantial effect on the performance of different architectures (see e.g., ). While other work has advocated online bootstrapping methods for hard-pixel mining or mini-batch selection , our approach is much simpler. Guided by this result we simply use uniform random sampling of pixels during training, appropriately weighted by instance size in order to estimate the loss.

2 Margin Selection

Proposition 2 gives the maximum margin for a separation of $n$ groups of pixels in a three dimensional embedding space (sphere). For example, if an image has at most $\{4,5,6,7\}$ instances, $\alpha$ can be set as small as $\{0.093,0.274,0.395,0.482\}$ , respectively.

For points in a higher dimension embedding space, it is a non-trivial problem to establish a tight analytic bound for the margin $\alpha$ . Despite its simple description, distributing $n$ points on a $(D-1)$ -dimensional hypersphere is considered a serious mathematical challenge for which there is no general solutions . We adopt a safe (trivial) strategy. For $n$ instances embedded in $n/2$ dimensions one can use value of $\alpha=0.5$ which allows for zero loss by placing a pair of groups antipodally along each of the $n/2$ orthogonal axes. We adopt this setting for the majority of experiments in the paper where the embedding dimension is set to $64$ .

Recurrent Mean-Shift Grouping

While we can directly train a model to predict embeddings as described in the previous section, it is not clear how to generate the final instance segmentation from the resulting (imperfect) embeddings. One can utilize heuristic post-processing or utilize clustering algorithms that estimate the number of instances , but these are not differentiable and thus unsatisfying. Instead, we introduce a mean-shift grouping model (Fig. 3) which operates recurrently on the embedding space in order to congeal the embedding vectors into a small number of instance labels.

Mean-shift and closely related algorithms use kernel density estimation to approximate the probability density from a set of samples and then perform clustering on the input data by assigning or moving each sample to the nearest mode (local maxima). From our perspective, the advantages of this approach are (1) the final instance labels (modes) live in the same embedding space as the initial data, (2) the recurrent dynamics of the clustering process depend smoothing on the input allowing for easy backpropagation, (3) the behavior depends on a single parameter, the kernel bandwidth, which is easily interpretable and can be related to the margin used for the embedding loss.

A common choice for non-parametric density estimation is to use the isotropic multivariate normal kernel $K({\bf x},{\bf x}_{i})=(2\pi)^{-D/2}\exp\Big{(}-\frac{\delta^{2}}{2}\|{\bf x}-{\bf x}_{i}\|^{2}_{2}\Big{)}$ and approximate the data density non-parametrically as $p(x)=\frac{1}{N}\sum K(x,x_{i})$ . Since our embedding vectors are unit norm, we instead use the von Mises-Fisher distribution which is the natural extension of the multivariate normal to the hypersphere , and is given by $K({\bf x},{\bf x}_{i})\propto\exp(\delta{\bf x}^{T}{\bf x}_{i})$ . The kernel bandwidth, $\delta$ determines the smoothness of the kernel density estimate and is closely related to the margin used for learning the embedding space. While it is straightforward to learn $\delta$ during training, we instead set it to satisfy $\frac{1}{\delta}=\frac{1-\alpha}{3}$ throughout our experiments, such that the cluster separation (margin) in the learned embedding space is three standard deviations.

Note that unlike standard mean-shift mode finding, we recompute ${\bf K}$ at each iteration. These update dynamics are termed the explicit- $\eta$ method and were analyzed by . When $\eta=1$ and the kernel is Gaussian, this is also referred to as Gaussian Blurring Mean Shift (GBMS) and has been shown to have cubic convergence under appropriate conditions. Unlike deep RNNs, the parameters of our recurrent module are not learned and the forward dynamics are convergent under general conditions. In practice, we do not observe issues with exploding or vanishing gradients during back-propagation through a finite number of iterations Some intuition about stability may be gained by noting that the eigenvalues of ${\bf K}{\bf D}^{-1}$ lie in the interval $$, but we have not been able to prove useful corresponding bounds on the spectrum of the Jacobian..

Fig. 4 demonstrates a toy example of applying the method to perform digit instance segmentation on synthetic images from MNIST . We learn 3-dimensional embedding in order to visualize the results before and after the mean shift grouping module. From the figure, we can see the mean shift grouping transforms the initial embedding vectors to yield a small set of instance labels which are distinct (for negative pairs) and compact (for positive pairs).

2 End-to-end training

It’s straightforward to compute the derivatives of the recurrent mean shift grouping module w.r.t ${\bf X}$ based on the the chain rule so our whole system is end-to-end trainable through back-propagation. Details about the derivative computation can be found in the appendix. To understand the benefit of end-to-end training, we visualize the embedding gradient with and without the grouping module (Fig. 5). Interestingly, we observe that the gradient backpropagated through mean shift focuses on fixing the embedding in uncertain regions, e.g. instance boundaries, while suggesting small magnitude updates for those errors which will be easily fixed by the mean-shift iteration.

While we could simply apply the pairwise embedding loss to the final output of the mean-shift grouping, in practice we accumulate the loss over all iterations (including the initial embedding regression). We unroll the recurrent grouping module into $T$ loops, and accumulate the same loss function at the unrolled loop- $t$ :

Experiments

We now describe experiments in training our framework to deal a variety of pixel-labeling problems, including boundary detection, object proposal detection, semantic segmentation and instance-level semantic segmentation.

We illustrate the advantages of the proposed modules on several large-scale datasets. First, to illustrate the ability of the instance-aware weighting and uniform sampling mechanism to handle imbalanced data and low embedding dimension, we use the BSDS500 dataset to train a boundary detector for boundary detection ( $>90\%$ pixels are non-boundary pixels). We train with the standard split , using 300 train-val images to train our model based on ResNet50 and evaluate on the remaining 200 test images. Second, to explore instance segmentation and object proposal generation, we use PASCAL VOC 2012 dataset with additional instance mask annotations provided by . This provides 10,582 and 1,449 images for training and evaluation, respectively.

We implement our approach using the toolbox MatConvNet , and train using SGD on a single Titan X GPU. The code and trained models can be found at https://github.com/aimerykong/Recurrent-Pixel-Embedding-for-Instance-Grouping. To compute calibrated cosine similarity, we utilize an L2-normalization layer before matrix multiplication , which also contains random sampling with a hyper-parameter to control the ratio of pixels to be sampled for an image. In practice, we observe that performance does not depend strongly on this ratio and hence set it based on available (GPU) memory.

While our modules are architecture agnostic, we use the ResNet50 and ResNet101 models pre-trained over ImageNet as the backbone. Similar to , we increase the output resolution of ResNet by removing the top global $7\times 7$ pooling layer and the last two $2\times 2$ pooling layers, replacing them with atrous convolution with dilation rate 2 and 4, respectively to maintain a spatial sampling rate. Our model thus outputs predictions at $1/8$ the input resolution which are upsampled for benchmarking.

We augment the training set using random scaling by $s\in[0.5,1.5]$ , in-plane rotation by $[-10^{\circ},10^{\circ}]$ degrees, random left-right flips, random crops with 20-pixel margin and of size divisible by 8, and color jittering. When training the model, we fix the batch normalization in ResNet backbone, using the same constant global moments in both training and testing. Throughout training, we set batch size to one where the batch is a single input image. We use the “poly” learning rate policy with a base learning rate of $2.5e-4$ scaled as a function of iteration by $(1-\frac{iter}{maxiter})^{0.9}$ .

2 Boundary Detection

For boundary detection, we first train a model to group the pixels into boundary or non-boundary groups. Similar to COB and HED , we include multiple branches over ResBlock $2,3,4,5$ for training. Since the number of instances labels is 2, we learn a simple 3-dimensional embedding space which has the advantage of easy visualization as an RGB image. Fig. 7 shows the resulting embeddings in the first row of each panel. Note that even though we didn’t utilize mean-shift grouping, the trained embedding already produces compact clusters. To compare quantitatively to the state-of-the-art, we learn a fusion layer that combines predictions from multiple levels of the feature hierarchy fine-tuned with a logistic loss to match the binary output. Fig. 7 shows the results in the second row. Interestingly, we can see that the fine-tuned model embeddings encode not only boundary presence/absence but also the orientation and signed distance to nearby boundaries.

Quantitatively, we compare our model to COB , HED , CEDN , LEP , UCM , ISCRA , NCuts , EGB , and the original mean shift (MShift) segmentation algorithm . Fig. 6 shows standard benchmark precision-recall for all the methods, demonstrating our model achieves state-of-the-art performance. Note that our model has the same architecture of COB except with a different loss functions and no explicit branches to compute boundary orientation. Our embedding loss by naturally pushes boundary pixel embeddings to be similar which is also the desirable property for detecting boundaries using logistic loss. Note that it is possible to surpass human performance with several sophisticated techniques , we don’t pursue this as it is out the scope of this paper.

3 Object Proposal Detection

Object proposals are an integral part of current object detection and semantic segmentation pipelines , as they provide a reduced search space of locations, scales and shapes for subsequent recognition. State-of-the-art methods usually involve training models that output large numbers of proposals, particularly those based on bounding boxes. Here we demonstrate that by training our framework with 64-dimensional embedding space on the object instance level annotations, we are able to produce very high quality object proposals by grouping the pixels into instances. It is worth noting that due to the nature of our grouping module, far fewer number of proposals are produced with much higher quality. We compare against the most recent techniques including POISE , LPO , CPMC , GOP , SeSe , GLS , RIGOR .

Fig. 8 shows the Average Recall (AR) with respect to the number of object proposalsOur basic model produces $\sim 10$ proposals per image. In order to plot a curve for our model for larger numbers of proposals, we run the mean shift grouping with multiple smaller bandwidth parameters, pool the results, and remove redundant proposals.. Our model performs remarkably well compared to other methods, achieving high average recall of ground-truth objects with two orders of magnitude fewer proposals. We also plot the curves for SharpMask and DeepMask using the proposals released by the authors. Despite only training on PASCAL, we outperform these models which were trained on the much larger COCO dataset . In Table 1 we report the total average recall at IoU $=0.5$ for some recently proposed proposal detection methods, including unpublished work inst-DML which is similar in spirit to our model but learns a Euclidean distance based metric to group pixels. We can clearly see that our method achieves significantly better results than existing methods.

4 Semantic Instance Detection

As a final test of our method, we also train it to produce semantic labels which are combined with our instance proposal method to recognize the detected proposals.

For semantic segmentation which is a k-way classification problem, we train a model using cross-entropy loss alongside our embedding loss. Similar to our proposal detection model, we use a 64-dimension embedding space on top of DeepLab-v3 as our base model. While there are more complex methods in literature such as PSPNet and which augment training with additional data (e.g., COCO or JFT-300M dataset ) and utilize ensembles and post-processing, we focus on a simple experiment training the base model with/without the proposed pixel pair embedding loss to demonstrate the effectiveness.

In addition to reporting mean intersection over union (mIoU) over all classes, we also computed mIoU restricted to a narrow band of pixels around the ground-truth boundaries. This partition into figure/boundary/background is sometimes referred to as a tri-map in the matting literature and has been previously utilized in analyzing semantic segmentation performance . Fig. 9 shows the mIoU as a function of the width of the tri-map boundary zone. This demonstrates that with embedding loss yields performance gains over cross-entropy primarily far from ground-truth boundaries where it successfully fills in holes in the segments output (see also qualitative results in Fig. 10). This is in spirit similar to the model in , which considers local consistency to improve spatial precision. However, our uniform sampling allows for long-range interactions between pixels.

To label detected instances with semantic labels, we use the semantic segmentation model described above to generate labels and then use a simple voting strategy to transfer these predictions to the instance proposals. In order to produce a final confidence score associated with each proposed object, we train a linear regressor to score each object instance based on its morphology (e.g., size, connectedness) and the consistency w.r.t. the semantic segmentation prediction. We note this is substantially simpler than approaches based, e.g. on Faster-RCNN which use much richer convolutional features to rescore segmented instances .

Comparison of instance detection performance are displayed in Table 2. We use a standard IoU threshold of 0.5 to identify true positives, unless an ground-truth instance has already been detected by a higher scoring proposal in which case it is a false positive. We report the average precision per-class as well as the average all classes (as in ). Our approach yields competitive performance on VOC validation despite our simple re-scoring. Among the competing methods, the one closest to our model is inst-DML , that learns Euclidean distance based metric with logistic loss. The inst-DML approach relies on generating pixel seeds to derive instance masks. The pixel seeds may fail to correctly detect thin structures which perhaps explains why this method performs 10x worse than our method on the bike category. In contrast, our mean-shift grouping approach doesn’t make strong assumptions about the object shape or topology.

For visualization purposes, we generate three random matrices projections of the 64-dimensional embedding and display them in the spatial domain as RGB images. Fig. 11 shows the embedding visualization, as well as predicted semantic segmentation and instance-level segmentation. From the visualization, we can see the instance-level semantic segmentation outputs complete object instances even though semantic segmentation results are noisy, such as the bike in the first image in Fig. 11. The instance embedding provides important details that resolve both inter- and intra-class instance overlap which are not emphasized in the semantic segmentation loss.

Conclusion and Future Work

We have presented an end-to-end trainable framework for solving pixel-labeling vision problems based on two novel contributions: a pixel-pairwise loss based on spherical max-margin embedding and a variant of mean shift grouping embedded in a recurrent architecture. These two components mesh closely to provide a framework for robustly recognizing variable numbers of instances without requiring heuristic post-processing or hyperparameter tuning to account for widely varying instance size or class-imbalance. The approach is simple and amenable to theoretical analysis, and when coupled with standard architectures yields instance proposal generation which substantially outperforms state-of-the-art. Our experiments demonstrate the potential for instance embedding and open many opportunities for future work including learn-able variants of mean-shift grouping, extension to other pixel-level domains such as encoding surface shape, depth and figure-ground and multi-task embeddings.

Acknowledgement

This project is supported by NSF grants IIS-1618806, IIS-1253538, DBI-1262547 and a hardware donation from NVIDIA. Shu Kong personally thanks Mr. Kevis-Kokitsi Maninis, Dr. Alireza Fathi, Dr. Kevin Murphy and Dr. Rahul Sukthankar for the helpful discussion, advice and encouragement.

References

Analysis of Pairwise Loss for Spherical Embedding

In this section, we provide proofs for the propositions presented in the paper which provide some analytical understanding of our proposed objective function, and the mechanism for subsequent pixel grouping mechanism.

First note that $\|{\bf x}_{1}+\dots+{\bf x}_{n}\|_{2}^{2}\geq 0$ . We expand the square and collect all the cross terms so we have $\sum_{i}{\bf x}_{i}^{T}{\bf x}_{i}+\sum_{i\not=j}{\bf x}_{i}^{T}{\bf x}_{j}\geq 0$ . Therefore, $\sum_{i\not=j}{\bf x}_{i}^{T}{\bf x}_{j}\geq-\sum_{i=1}^{n}\|{\bf x}_{i}\|_{2}^{2}$ . When all the vectors are on the hyper-sphere, i.e. $\|{\bf x}_{i}\|_{2}=1$ , then $\sum_{i\not=j}{\bf x}_{i}^{T}{\bf x}_{j}\geq-\sum_{i=1}^{n}\|{\bf x}_{i}\|_{2}^{2}=-n$ . $\hfill\blacksquare$

We treat all the $n$ vectors as representatives of $n$ different instances in the image and seek to minimize pairwise similarity, or equivalently maximize pairwise distance (referred to as Tammes’s problem, or the hard-spheres problem ).

Let $d=\max\limits_{\{{\bf x}_{i}\}}\min\limits_{i\not=j}\|{\bf x}_{i}-{\bf x}_{j}\|_{2}$ be the distance between the closest point pair of the optimally distributed points. Asymptotic results in show that, for some constant $C>0$ ,

Since $\|{\bf x}_{i}-{\bf x}_{j}\|_{2}^{2}=2-2{\bf x}_{i}^{T}{\bf x}_{j}$ , we can rewrite this bound in terms of the similarity $s_{ij}=\frac{1}{2}\left(1+\frac{{\bf x}_{i}^{T}{\bf x}_{j}}{\|{\bf x}_{i}\|_{2}\|{\bf x}_{j}\|_{2}}\right)$ , so that for any $i\not=j$ :

Therefore, choosing $\alpha\leq 1-\Big{(}\frac{2\pi}{\sqrt{3}N}\Big{)}$ , guarantees that $[s_{ij}-\alpha]_{+}\geq 0$ for some pair $i\not=j$ . Choosing $\alpha>1-\frac{1}{4}\Bigg{(}\Big{(}\frac{8\pi}{\sqrt{3}N}\Big{)}^{\frac{1}{2}}-CN^{-\frac{2}{3}}\Bigg{)}^{2}$ , guarantees the existence of an embedding with $[s_{ij}-\alpha]_{+}=0$ . $\hfill\blacksquare$

Details of Recurrent Mean Shift Grouping

There are two commonly used multivariate kernels in mean shift algorithm. The first, Epanechnikov kernel , has the following profile

where $c_{d}$ is the volume of the unit $d$ -dimensional sphere. The standard mean-shift algorithm computes the gradient of the kernel density estimate given by

and identifies modes (local maxima) where $\nabla p({\bf x})=0$ . The scale parameter $b$ is known as the kernel bandwidth and determines the smoothness of the estimator. The gradient of $p({\bf x})$ can be elegantly computed as the difference between ${\bf x}$ and the mean of all data points with $\|{\bf x}-{\bf x}_{i}\|\leq b$ , hence the name “mean-shift” for performing gradient ascent.

Since the Epanechnikov profile is not differentiable at the boundary, we use the squared exponential kernel adapted to vectors on the sphere:

which can be viewed as a natural extension of the Gaussian to spherical data (known as the von Mises Fisher (vMF) distribution ). In our experiments we set the bandwidth $\delta$ based on the margin $\alpha$ so that $\frac{1}{\delta}=\frac{1-\alpha}{3}$ .

Our proposed algorithm also differs from the standard mean-shift clustering (i.e., ) in that rather than performing gradient ascent on a fixed kernel density estimate $p({\bf x})$ , at every iteration we alternate between updating the embedding vectors $\{{\bf x}_{i}\}$ using gradient ascent on $p({\bf x})$ and re-estimating the density $p({\bf x})$ for the updated vectors. This approach is termed Gaussian Blurring Mean Shift (GBMS) in and has converge rate guarantees for data which starts in compact clusters.

In the paper we visualized embedding vectors after GBMS for specific examples. Figure 12 shows aggregate statistics over a collection of images (in the experiment of instance segmentation). We plot the distribution of pairwise similarities for positive and negative pairs during forward propagation through 10 iterations. We can observe that the mean shift module produces sharper distributions, driving the similarity between positive pairs to 1 making it trivial to identify instances.

To backpropagate gradients through an iteration of GBMS, we break the calculation into a sequence of steps below where we assume the vectors in the data matrix $X$ have already been normalized to unit length.

2 Toy Example of Mean Shift Backpropagation

In the paper we show examples of the gradient vectors backpropagated through recurrent mean shift to the initial embedding space. Backpropagation through this fixed model modulates the loss on the learned embedding, increasing the gradient for initial embedding vectors whose instance membership is ambiguous and decreasing the gradient for embedding vectors that will be correctly resolved by the recurrent grouping phase.

If running GBMS for unsupervised clustering on these data with the default setting (bandwidth is 0.2), we can see they are grouped into three piles, as shown in Figure 13 (b). If updating the data using gradient descent without GBMS inserted, we end up with three visible clusters even though the data move towards the ideal embedding in terms of classification. Figure 13 (c) and (d) depict the trajectories of 100 random data points during the 30 updates and the final result, respectively.

Now we insert the GBMS module to update these data with different loops, and compare how this effects the performance. We show the updated data distributions and those after five loops of GBMS grouping in column (e) and (f) of Figure 13, respectively. We notice that, with GBMS, all the data are grouped into two clusters; while with GBMS grouping they become more compact and are located exactly on the “ideal spot” for mapping into label space (i.e. 3 and 5) and achieving zero loss. On the other hand, we also observe that, even though these settings incorporates different number of GBMS loops, they achieve similar visual results in terms of clustering the data. To dive into the subtle difference, we randomly select 100 data and depict their trajectories in column (g) and (h) of Figure 13, using a single loss on top of the last GBMS loop or multiple losses over every GBMS loops, respectively. We have the following observations:

By comparing with Figure 13 (c), which depicts update trajectories without GBMS, GBMS module provides larger gradient to update those data further from their “ideal spot” under both scenarios.

From (g), we can see the final data are not updated into tight groups. This is because that the updating mechanism only sees data after (some loops of) GBMS, and knows that these data will be clustered into tight groups through GBMS.

A single loss with more loops of GBMS provides greater gradient than that with fewer loops to update data, as seen in (g).

With more losses over every loops of GBMS, the gradients become even larger that the data are grouped more tightly and more quickly. This is because that the updating mechanism also incorporates the gradients from the loss over the original data, along with those through these loops of GBMS.

To summarize, our GBMS based recurrent grouping module indeed provides meaningful gradient during training with back-propagation. With the convergent dynamics of GBMS, our grouping module becomes especially more powerful in learning to group data with suitable supervision.

Additional Boundary Detection Results

We show additional boundary detection resultsPaper with high-resolution figures can be found at the Project Page. on BSDS500 dataset based on our model in Figure 15, 16, 17 and 18. Specifically, besides showing the boundary detection result, we also show 3-dimensional pixel embeddings as RGB images before and after fine-tuning using logistic loss. From the consistent colors, we can see (1) our model essentially carries out binary classification even using the pixel pair embedding loss; (2) after fine-tuning with logistic loss, our model captures also boundary orientation and signed distance to the boundary. Figure 14 highlights this observation for an example image containing round objects. By zooming in one plate, we can observe a “colorful Mobius ring”, indicating the embedding features for the boundary also capture boundary orientation and the signed distance to the boundary.

Additional Results on Instance-Level Semantic Segmentation

We show more instance-level semantic segmentation results on PASCAL VOC 2012 dataset based on our model in Figure 19, 20 and 21. As we learn 64-dimensional embedding (hyper-sphere) space, to visualize the results, we randomly generate three matrices to project the embeddings to 3-dimension vectors to be treated as RGB images. Besides showing the randomly projected embedding results, we also visualize the semantic segmentation results used to product instance-level segmentation. From these figures, we observe the embedding for background pixels are consistent, as the backgrounds have almost the same color. Moreover, we can see the embeddings (e.g. in Figure 19, the horses in row-7 and row-13, and the motorbike in row-14) are able to connect the disconnected regions belonging to the same instance. Dealing with disconnected regions of one instance is an unsolved problem for many methods, e.g. , yet our approach has no problem with this situation.