Source-linked AI summary
DeepPermNet: Visual Permutation Learning
Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, Stephen Gould
TL;DR
Visual permutation learning asks how to recover structure from shuffled visual data, where exact permutation matrices are difficult to optimize with gradients. DeepPermNet uses a Sinkhorn layer to produce differentiable doubly-stochastic approximations in an end-to-end CNN. It performs strongly on relative attributes and self-supervised representation learning benchmarks.
Problem
Recovering meaningful order or spatial structure from shuffled visual data is difficult because permutation matrices are discrete and unsuitable for direct gradient-based optimization.
Method
DeepPermNet uses an end-to-end CNN with Sinkhorn iterations to convert standard predictions into doubly-stochastic approximations of permutation matrices.
Results
DeepPermNet achieves state-of-the-art performance on Public Figures and OSR relative-attribute benchmarks and on PASCAL VOC classification and segmentation tasks.
Takeaways & Limitations
Visual permutation learning provides a generic framework for recovering order and learning useful visual representations across multiple computer-vision tasks.
Takeaways & Limitations
The formulation assumes unique permutations, so it cannot explicitly handle equality cases in relative attributes; performance also depends on sequence length and dataset.
Abstract
from arXiv · showhide
We present a principled approach to uncover the structure of visual data by solving a novel deep learning task coined visual permutation learning. The goal of this task is to find the permutation that recovers the structure of data from shuffled versions of it. In the case of natural images, this task boils down to recovering the original image from patches shuffled by an unknown permutation matrix. Unfortunately, permutation matrices are discrete, thereby posing difficulties for gradient-based methods. To this end, we resort to a continuous approximation of these matrices using doubly-stochastic matrices which we generate from standard CNN predictions using Sinkhorn iterations. Unrolling these iterations in a Sinkhorn network layer, we propose DeepPermNet, an end-to-end CNN model for this task. The utility of DeepPermNet is demonstrated on two challenging computer vision problems, namely, (i) relative attributes learning and (ii) self-supervised representation learning. Our results show state-of-the-art performance on the Public Figures and OSR benchmarks for (i) and on the classification and segmentation tasks on the PASCAL VOC dataset for (ii).
1. Introduction
The paper formulates visual permutation learning as recovering meaningful order or spatial structure from shuffled visual data, using structure as supervision without human annotations. DeepPermNet combines CNNs with a Sinkhorn layer to learn permutations end-to-end and performs strongly on relative attributes and self-supervised representation learning.
- 1. Introduction: DeepPermNet learns visual permutations from shuffled images or image regions, targeting both meaningful image ordering and recovery of spatial layout.The framework jointly learns visual features and predictors for permutation recovery.
- 1. Introduction: Visual permutation learning can use shuffled natural images as abundant, annotation-free training data, with spatial structure providing the supervisory signal for self-supervised representation learning.This is useful for deep models that require large amounts of human-annotated data.
- 1. Introduction: The proposed DeepPermNet is an end-to-end CNN framework whose Sinkhorn layer converts standard CNN predictions into doubly-stochastic approximations of permutation matrices for backpropagation.The continuous approximation makes permutation prediction efficiently learnable despite the discreteness of exact permutation matrices.
- 1. Introduction: The method is evaluated on relative attributes and self-supervised representation learning, with reported best performance over existing approaches for object classification and segmentation in the latter setting.The introduction also reports application to relative attributes and representation learning as the framework's two main uses.
2. Related Work
Related work frames permutation learning as ordering images or regions by a criterion and connects it to jigsaw reconstruction, visual attributes, and self-supervised representation learning. The paper distinguishes its generic permutation framework from methods specialized to one pretext task or a small subset of permutations.
- 2. Related Work: Permutation learning broadly seeks a meaningful order for collections of images or image regions based on a predetermined criterion.Related formulations also arise in graphics, biology, and archaeology.
- 2. Related Work: Visual attributes support applications including image search, fine-grained recognition, and zero-shot learning, with relative attributes modeling comparative strength rather than binary presence.Parikh and Grauman formulate relative attributes as pairwise learning-to-rank constraints.
- 2. Related Work: Prior self-supervised methods use cues such as patch colocation, object tracking, ego-motion, odd-one-out questions, or missing-image context, but typically target representation learning alone.The paper contrasts this narrower objective with its broader set of permutation-learning applications.
- 2. Related Work: Other pretext tasks can be useful directly, but several are highly engineered for their training task and are not easily extended to other applications.Examples include visual grouping, colorization, and generative modeling.
- 2. Related Work: Noroozi and Favaro [32] use only 100 of 362k possible 3 × 3 grid permutations, whereas the proposed method handles the full permutation set and finer grids.The comparison highlights the paper's broader permutation coverage and scalability claim.
3. Learning Visual Permutations
Visual permutation learning predicts the permutation that restores an ordered image sequence, using a CNN and differentiable doubly-stochastic relaxation. DeepPermNet combines shared AlexNet branches with Sinkhorn normalization and discrete inference to recover the original order.
- 3.1. Task: DeepPermNet predicts the permutation matrix that shuffled an ordered image sequence, enabling recovery of the original sequence from the permuted input.The task is defined by applying random permutations to sequences ordered by a predetermined visual criterion, then predicting the shuffling matrix.
- 3.2. Learning: The CNN learns visual representations jointly with permutation prediction, aiming to capture semantic concepts, structure, and shared patterns transferable to related vision tasks.The authors apply this framework to relative attribute learning and representation learning.
- 3.2. Learning: Permutation matrices are discrete, so the method relaxes inference to doubly-stochastic matrices, which form a convex surrogate suitable for gradient-based optimization.A doubly-stochastic matrix has nonnegative entries with every row and column summing to one.
- 3.3. Model: DeepPermNet uses shared AlexNet branches through fc6, concatenates their outputs into fc7, and produces predictions through a Sinkhorn layer after fc8.Each branch processes one image from the permuted sequence, while shared weights support joint sequence processing.
- 3.3.1. Sinkhorn Normalization: Sinkhorn normalization repeatedly rescales matrix rows and columns to produce doubly-stochastic outputs, while unrolling these operations enables efficient gradient computation.A small value of approximately 10^-3 is added to each matrix entry before normalization to avoid numerical instability.
- 3.4. Inference: At inference, the method approximates the closest permutation matrix to the predicted doubly-stochastic matrix and uses it to recover the original sequence.The discrete approximation is obtained by solving a mixed-boolean optimization problem with branch-and-bound methods.
4. Experiments
Experiments evaluate DeepPermNet's permutation prediction, relative attribute learning, and self-supervised representation learning across public-figure, OSR, ImageNet, and PASCAL VOC settings.
- 4.1. Permutation Prediction: Sinkhorn normalization yields better Kendall-Tau and Hamming similarity than the naïve approach while keeping normalization error nearly unchanged for longer sequences.The naïve approach works for short sequences but degrades as sequence length increases, whereas Sinkhorn predictions remain stable.
- 4.1. Permutation Prediction: Sinkhorn predictions remain stable across permutations as sequence length increases, while the naïve approach becomes unstable, motivating its adoption in DeepPermNet.The evaluation varies sequence lengths and enumerates or samples permutations because the number of possible permutations grows factorially.
- 4.2. Relative Attributes: DeepPermNet outperforms state-of-the-art relative-attribute models by 3% pairwise accuracy on Public Figures, while its VGG variant also surpasses prior methods on OSR.On OSR, the AlexNet-based model performs slightly worse than [42], whereas the VGG variant achieves better results than the state-of-the-art methods.
- 4.2. Relative Attributes: Training on longer image sequences improves relative-attribute accuracy, while training only on pairs reduces Public Figures average pairwise accuracy by 7%.The formulation also cannot explicitly handle equality cases because it assumes each permutation is unique.
- 4.2. Relative Attributes: DeepPermNet-derived saliency maps localize attribute-related features without bounding-box or segmentation supervision, suggesting unsupervised attribute localization.The maps are obtained from the derivative of the estimated permutation matrix with respect to the input, followed by channel-wise max pooling.
- 4.3. Self-Supervised Representation Learning: DeepPermNet outperforms self-supervised competitors in PASCAL VOC object classification and segmentation and ranks second for detection, although supervised pre-training remains ahead.Using finer 4 × 4 grid cells does not improve recognition performance; a 3 × 3 partition and selected permutations suffice for strong representation learning.
5. Conclusion
The paper introduces visual permutation learning and an end-to-end CNN framework that recovers permutations using doubly-stochastic approximations. Experiments show the framework supports both order recovery and standard CNN initialization, while exact optimization remains a future direction.
- Visual permutation learning formulates recovery of the permutation matrix that generated a shuffled image sequence according to a predefined visual criterion.
- DeepPermNet uses a CNN layer with Sinkhorn normalization to produce doubly-stochastic approximations of permutation matrices and supports end-to-end training.
- Experiments indicate the framework can recover order and generate good initializations for training standard CNN models.
- Replacing unrolled Sinkhorn iterations for gradient propagation with more standard and exact optimizers is identified as future work.