Learning from one and only one shot

We introduce a distortable canvas model, where any image can be thought of as smoothly painted on an elastic (rubber-like) canvas that can be flexibly bent, stretched, and deformed—just like how we naturally “distort” an image in our minds.

Formally, we define a smooth image by a piecewise differentiable \({\mathcal{M}}:{{\mathbb{R}}}^{2}\to {{\mathbb{R}}}_{+}\), where \({{\mathbb{R}}}^{2}\) denotes an infinite canvas and \({{\mathbb{R}}}_{+}\) denotes color (grayscale in this paper). We define a canvas transformation by \(\alpha :{{\mathbb{R}}}^{2}\to {{\mathbb{R}}}^{2}\), which reshapes the underlying canvas of a smooth image. We also define a color transformation by \(\chi :{{\mathbb{R}}}_{+}\to {{\mathbb{R}}}_{+}\), which repaints the color of a smooth image. We simplify color transformation and only use it to adjust image contrast via affine χ(c) := ac + b. In contrast, we do not restrict canvas transformation to any pre-specified types such as translation, rotation, or scaling, but instead allow all possible transformations. Given \({\mathcal{M}},\alpha ,\chi\), the composition \(\chi \circ {\mathcal{M}}\circ \alpha\) denotes the transformed image of \({\mathcal{M}}\) by transformations α, χ.

To mimic human intuition about general-appearance similarity, we introduce canvas distortion \({{\mathcal{D}}}_{V}(\alpha )\) for any canvas transformation α and color distortion \({{\mathcal{D}}}_{C}({\mathcal{M}},{{\mathcal{M}}}^{{\prime} })\) between two smooth images \({\mathcal{M}},{{\mathcal{M}}}^{{\prime} }\). Our idea is to search for a transformation that mimics what humans naturally do to transform one image into another. That is, a low-distorted α which makes little difference in color between \({\mathcal{M}}\) and the transformed \({{\mathcal{M}}}^{{\prime} }\). More precisely, we want to minimize both \({{\mathcal{D}}}_{V}(\alpha )\) and \({{\mathcal{D}}}_{C}({\mathcal{M}},\,\chi \circ {{\mathcal{M}}}^{{\prime} }\circ \alpha )\). This yields two dual variants of our desired general-appearance distance:

• \({{\mathcal{D}}}_{C}\)-distance: minimizes the color distortion \({{\mathcal{D}}}_{C}\) while controlling the canvas distortion \({{\mathcal{D}}}_{V}\)

• \({{\mathcal{D}}}_{V}\)-distance: minimizes the canvas distortion \({{\mathcal{D}}}_{V}\) while controlling the color distortion \({{\mathcal{D}}}_{C}\).

We detail the implementation of our distortable canvas model as a computational framework below.

Digital and smoothed images

An m × n digital image is a discrete \({\mathsf{M}}:[m]\times [n]\to [0,1]\), where [k] := {0, 1, …, k − 1} for any \(k\in {\mathbb{Z}}\). We call [m] × [n] the canvas grid and any z ∈ [m] × [n] a grid point. For any m × n digital image \({\mathsf{M}}\), we smooth it to \({\mathcal{M}}\) via a sum of kernels:

where a kernel \(\kappa :{{\mathbb{R}}}_{+}\to {{\mathbb{R}}}_{+}\) is a decaying function (e.g., linear, polynomial, Gaussian decay) and ρ is a metric on \({{\mathbb{R}}}^{2}\) (e.g., ℓ₁, ℓ₂, ℓ_∞). In this paper, we use linear decay and ℓ_∞, i.e., \(\kappa (\rho (z,x))=1-\frac{1}{{\rho }_{c}}\parallel z-x{\parallel }_{\infty }\) if ∥z − x∥_∞ < ρ_c (for some cutoff radius ρ_c > 0) and κ(ρ(z, x)) = 0 otherwise. Note: \({\mathcal{M}}\) is defined everywhere on \({{\mathbb{R}}}^{2}\). This differs from Gaussian blurring as we do not discretize kernels. It is key to use the smoothed image as input, which allows computing gradients analytically. As such, we always smooth any digital image first and then only manipulate the smoothed image.

Arbitrary canvas transformations

We consider all 2D transformations (including those without a formula), but how do we represent them in a computer? With respect to the standard grid [m] × [n], we use the transformed grid α([m] × [n]) to represent α digitally. Thus, any canvas transformation α is digitally represented by (\(\mathop{=}\limits^{d}\)) a matrix \({\boldsymbol{\alpha }}\in {{\mathbb{R}}}^{(mn)\times 2}\) whose ith row is the 2D coordinate of the transformed ith grid point. We use the lexicographical order of a 2D grid, e.g., with respect to [2] × [3], the identify transformation \({\rm{id}}\mathop{=}\limits^{d}{\bf{id}}=[[0,0],[0,1],[0,2],[1,0],[1,1],[1,2]]\). Any transformed image \({\mathcal{M}}\circ \alpha \mathop{=}\limits^{d}{\mathcal{M}}({\boldsymbol{\alpha }}):=(\,{\mathcal{M}}({{\boldsymbol{\alpha }}}_{0}),\,\ldots ,\,{\mathcal{M}}({{\boldsymbol{\alpha }}}_{(mn-1)}))\in {{\mathbb{R}}}^{(mn)}\), i.e., a (vectorized) digital image sampled from \({\mathcal{M}}\) at the transformed grid α.

Color and canvas distortions

The color distortion \({{\mathcal{D}}}_{C}\) measures the color discrepancy between \({\mathcal{M}}({\bf{id}})\) and \({{\mathcal{M}}}^{{\prime} }({\boldsymbol{\alpha }})\) up to an affine color transformation χ. The canvas distortion \({{\mathcal{D}}}_{V}\) measures the distortion between the original grid id and the transformed grid α. Formally,

Here, B_E comprises all pairs of neighboring edges in a canvas lattice (introduced below). Eq. (3) is derived from the mathematical definition of distortion of a function by discretizing it across the canvas lattice. This formula measures how far an arbitrary transformation is from being conformal, which is flexible for local isometries and scaling. Given a canvas grid [m] × [n], its corresponding canvas lattice is an undirected graph L = (V, E), with the set of vertices V = [m] × [n] and the set of edges obtained by connecting neighboring vertices in the ℓ_∞ sense: E = {{i, j}∣∥v_i − v_j∥_∞ = 1for v_i, v_j ∈ V}. We say two edges are neighbors if they form a 45^∘ angle (Fig. 7).

General-appearance distance via distortion minimization

To minimize color and canvas distortions (2) and (3), we consider two dual views: minimizing \({{\mathcal{D}}}_{C}\) among low-distorted αs or minimizing \({{\mathcal{D}}}_{V}\) among best-matching αs. We write the two views as the following two constrained optimization problems, together with their respective unconstrained equivalents: with ϵ → 0₊ and μ → 0₊,

We let the optima \({{\mathcal{D}}}_{C}^{\star }\) for (4) and \({{\mathcal{D}}}_{V}^{\star }\) for (5) denote two versions of our general-appearance distance that mimics human innate intuition. We call them \({{\mathcal{D}}}_{C}\)–distance and \({{\mathcal{D}}}_{V}\)–distance, respectively.

Transformation flow

Besides the final optimal solution, we apply the minimal-distortion principle throughout the entire optimization process⁴², i.e., we aim to keep canvas/color distortions small at every optimization step. Gradient descent (or projected gradient descent for constrained minimization) naturally fits this goal, since it always follows the steepest descent direction. The iterative gradient steps not only give us an optimal transformation α^⋆ as an end result but also a transformation flow id = α⁽⁰⁾ → α⁽¹⁾ → ⋯ → α^⋆. The resulting sequence of transformed images \({{\mathcal{M}}}^{{\prime} }={{\mathcal{M}}}^{{\prime} }\circ {\alpha }^{(0)}\to {{\mathcal{M}}}^{{\prime} }\circ {\alpha }^{(1)}\to \cdots \to {{\mathcal{M}}}^{{\prime} }\circ {\alpha }^{\star }\approx {\mathcal{M}}\) (we omit χ for simplicity) makes up an animation (Fig. 1), which simulates human intuition on smoothly transforming \({{\mathcal{M}}}^{{\prime} }\) to \({\mathcal{M}}\). For example, our mind does not treat translations as sudden jumps from one location to another, but instead tends to auto-complete a translation path that is continuous and desirably short.

In summary, our model outputs the optimal transformation α^⋆, its associated distance \({{\mathcal{D}}}_{C}^{\star }\) or \({{\mathcal{D}}}_{V}^{\star }\), and the corresponding transformation flow α⁽⁰⁾ → ⋯ → α^⋆ leading to the optimal solution. This achieves our goal of making both the transformation and the transformation process human-like and interpretable, thus rendering the entire model white-box.

However, ordinary (projected) gradient descent on (4) or (5) has a problem: the curse of local minima. Our solution is to lift gradient descent to multiple levels of abstraction via multiscale canvas lattices and color blurring, mimicking human abstraction capabilities that are extremely flexible in multiscale optimization. We name this technique the abstracted multi-level gradient descent (AMGD), controlled by an anchor-grid system \(\hat{G}\) and a blurring parameter ρ_c. AMGD outputs a \((\hat{G},{\rho }_{c})\)-solution path that forms the backbone of a desired transformation flow. We detail AMGD in the sequal.

The canvas distortion \({{\mathcal{D}}}_{V}\) is invariant under a variety of transformations (e.g., \({{\mathcal{D}}}_{V}(\alpha )=0\) for any conformal α), which nicely mimics humans’ flexible transformation options. But this also implies numerous local/global minima and other critical points where the gradient is 0. How much the color distortion \({{\mathcal{D}}}_{C}\) fluctuates as a function of α depends on the images \({\mathcal{M}},{{\mathcal{M}}}^{{\prime} }\). But in most cases, \({{\mathcal{D}}}_{C}\) also has many local/global minima, the majority of which represent unwanted “short cuts”—unnatural transformations that make \({{\mathcal{D}}}_{C}\to 0\) but would break the rubber canvas or create holes in it. The curse of vanishing gradients can freeze gradient descent. To unfreeze it, we lift gradient descent to higher levels, once again mimicking humans’ abstraction power, as our internal optimization system is quite flexible in pursuing “gradient-descent” moves at multiple levels of abstraction. We design two abstraction techniques: a chain of anchor lattices to make hierarchical abstractions of canvas transformations and a chain of color blurring to make hierarchical abstractions of image painting.

Anchor grids and lattices

An anchor grid and its corresponding anchor lattice offer a simpler parameterization (i.e., an abstraction) of canvas transformations. Without such an abstraction, any transformed [m] × [n] grid \({\boldsymbol{\alpha }}\in {{\mathbb{R}}}^{(mn)\times 2}\) consists of 2mn free parameters. So, the optimization problems (4) and (5) are 2mn + 2 dimensional, which is not only computationally inefficient for large images but also has too much room for vanishing gradient. We use a simpler α-parameterization that regularizes transformation, lowers distortion, and agrees with our intuition on rubber transformations.

Formally, an anchor system \((G,\hat{G})=(M\times N,\hat{M}\times \hat{N})\) uses two layers of grids: an underlying grid G and an anchor grid \(\hat{G}\) atop, satisfying \(\hat{M}\subseteq M,\hat{N}\subseteq N\), and \(G\subseteq {\rm{ConvexHull}}(\hat{G})\). Figure 8a shows one example, where G = [5] × [6] = {0, …, 4} × {0, …, 5} and \(\hat{G}=\{0,2,4\}\times \{0,2,5\}\). Under an anchor system, we can uniquely represent any grid point g ∈ G via four anchors \({A}_{g},{B}_{g},{C}_{g},{D}_{g}\in \hat{G}\) via proportional interpolation, or more precisely, the following double convex combination

Here, A_gB_gD_gC_g can be uniquely selected as the smallest rectangle in \(\hat{G}\)’s lattice containing g; the two weight parameters λ_g, ν_g are computed based on relative position, e.g., as in Fig. 8a. The relation between grid points and anchors can be summarized by a weight matrix \(W\in {{\mathbb{R}}}^{| G| \times | \hat{G}| }\). Its ith row stores weights for the ith grid point (say g in (6)) and contains at most four non-zero entries (i.e., coefficients in (6)) located at the columns corresponding to A_g, B_g, C_g, D_g, respectively.

Given an anchor system \((G,\hat{G})\), any canvas transformation \(\alpha \mathop{=}\limits^{d}{\boldsymbol{\alpha }}\in {{\mathbb{R}}}^{| G| \times 2}\) under G and \(\mathop{=}\limits^{d}\hat{{\boldsymbol{\alpha }}}\in {{\mathbb{R}}}^{| \hat{G}| \times 2}\) under \(\hat{G}\). \(\hat{{\boldsymbol{\alpha }}}\) is a submatrix of α, which induces an equivalence relation on the set of all canvas transformations: α, β are equivalent iff \(\hat{{\boldsymbol{\alpha }}}=\hat{{\boldsymbol{\beta }}}\), and \(\hat{{\boldsymbol{\alpha }}}\) abstracts the equivalence class \(\{{\boldsymbol{\beta }}| \hat{{\boldsymbol{\beta }}}=\hat{{\boldsymbol{\alpha }}}\}\). Based on the maximum entropy principle⁴³, a reasonable selection of a representative of this equivalence class is \(W\hat{{\boldsymbol{\alpha }}}\), because \(W\hat{{\boldsymbol{\alpha }}}\in \{{\boldsymbol{\beta }}| \hat{{\boldsymbol{\beta }}}=\hat{{\boldsymbol{\alpha }}}\}\) and evenly distributes the transformed grid points. Figure 8b illustrates this type of even distribution, which agrees with human intuition on how a rubber surface would naturally react when transforming forces are applied at anchors.

Using an anchor system in optimization problems (4) and (5) adds very little to computing distortions and gradients: we reuse the computation with \({\boldsymbol{\alpha }}=W\hat{{\boldsymbol{\alpha }}}\) and perform only one additional chain-rule step \(\partial {\boldsymbol{\alpha }}/\partial \hat{{\boldsymbol{\alpha }}}=W\). By doing so, however, the number of optimization variables in (4) or (5) reduces from ∣G∣ + 2 to \(| \hat{G}| +2\) (e.g., if G = [28] × [28] and \(\hat{G}=\{0,27\}\times \{0,27\}\), the number reduces from 1570 to 10). It is important to note that using a simpler anchor grid is not the same as downsampling. If it were, one would plug in \(\alpha \leftarrow \hat{{\boldsymbol{\alpha }}}\), but we plug in \(\alpha \leftarrow W\hat{{\boldsymbol{\alpha }}}\). In our case, image colors are still sampled from the underlying grid rather than downsampled from the anchor grid. So, using our anchor system is not information lossy while still benefiting from reduced optimization size. Running gradient descent (w.r.t. anchors) in abstracted optimization spaces effectively bypasses critical points.

Blurring

Another view to lifting gradient descent to a high-level, abstracted optimization space, is to blur the image. Intuitively, blurring ignores low-level fluctuation, similar to how humans naturally abstract an image. Blurring helps remedy vanishing gradients and is done in our image smoothing process. The cutoff radius ρ_c in κ in (1) controls the blurring extent: larger ρ_c means more blurred.

Algorithm 1

Traverse the anchor-lattice chain and the blurring chain in a solution path.

Abstracted multi-level gradient descent

Mixing the two abstraction techniques yields our AMGD technique proceeding from higher- to lower-level abstractions. Given an anchor grid \(\hat{G}\) and a cutoff radius ρ_c, we denote the corresponding (4) and (5) by \(DC(\hat{G},{\rho }_{c})\) and \(DV(\hat{G},{\rho }_{c})\), respectively. For either, we solve for a \((\hat{G},{\rho }_{c})\)-solution path, from coarser \(\hat{G}\) and larger ρ_c to finer \(\hat{G}\) and smaller ρ_c. Let \({\hat{G}}_{k}\) be a k × k evenly distributed anchor grid and \({\hat{L}}_{k}\) be its corresponding lattice. Figure 8c shows a chain of anchor lattices \({\mathcal{L}}={\{{\hat{L}}_{{3}^{i}+1}\}}_{i = 0,1,2,\ldots }\) and a chain of cutoff radii \({\mathcal{R}}={\{{\eta }^{j}{\rho }_{{c}_{0}}\}}_{j = 0,1,2,\ldots }\). The pseudocode in Algorithm 1 shows an example of traversing the two chains in a solution path. The procedure starts from the coarsest lattice and traverses the blurring chain first (from the most blurred to the least blurred image) and then, with the clearest image fixed, traverse the lattice chain (from coarsest to finest). It is easy initially to align two blurred blobs via small canvas adjustments, implying a small number of iterations to converge to \({{\mathcal{D}}}_{C}\approx {{\mathcal{D}}}_{V}\approx 0\). As we proceed along the solution path, the images restore more detail but the finer \({\hat{L}}_{k}\) helps manage that detail. In a solution path, an earlier solution is used to warm start the subsequent solve step, which further alleviates the curse of vanishing gradients. Notably, even the starting \({\hat{L}}_{2}\) comprising only four corner anchors parameterizes a large family of transformations containing all affine transformations. Finer anchor grids/lattices express more flexible transformations (including local, global, piecewise affine, and more), approaching human-level flexibility.

Interpretability makes our model configuration intuitive, avoiding the black art of hyperparameter tuning in many ML methods. Consider a 28 × 28 image as an example. Both the anchor lattice list and the cutoff radius list can be set as geometric sequences, with their granularity flexibly controlled by the sequence length. For the anchor lattices, we start from the smallest possible grid, i.e., 2 × 2, and gradually refine it to the full grid 28 × 28. The cutoff radii can be configured intuitively because they have a physical meaning, e.g., a radius of 4 defines the extent of blurring, where each pixel blurs into a 4-pixel radius neighborhood, forming a 9 × 9 blob, or superpixel. This represents considerable blurring for a 28 × 28 image, which is easy to visualize. The stopping criterion for gradient descent can be controlled by the color distortion threshold ϵ, which has a physical meaning too, e.g., a distortion of 1 can correspond to flipping a pixel from black (0) to white (1). Thus, setting ϵ = 5 represents a small color-distortion tolerance for a 28 × 28 grayscale image.

The number of parameters in our model scales linearly with the size of the input image, implying linear memory requirements. As a comparison, ViT scales linearly with number of tokens, which itself depends not only on image size but also patch size and architecture details such as embedding dimension and number of layers. Our runtime depends on the number of gradient-descent steps, which is small for visually similar images and large for dissimilar ones. For the two examples in Fig. 1c, transforming “1” to “7” to compute their distance took 65 gradient-descent steps and 235 ms on a MacBook Pro (M1 Max), whereas transforming “6” to “7” took 196 steps and 452 ms.

We next detail k-means-style clustering in our general-appearance similarity space. As in other non-Euclidean metric learning settings⁴⁴, it is unrealistic to run k-means on explicitly computed distances. Learning a distance in our model requires solving an optimization problem, which is much more expensive than computing Euclidean distances. Further, computing a centroid in a non-Euclidean space requires solving another optimization problem (minimizing the sum of within-cluster distances), which is much more expensive than an arithmetic mean. What is more challenging is that the two optimizations are nested, yielding an optimization problem of optimization problems.

To address these challenges, we generalize our idea of a transformation flow between two images into multi-flows among multiple images. Under this generalization, we do not explicitly compute pairwise distances, meaning we do not solve the inner optimizations first. Instead, we solve the inner and outer optimizations at the same time, where we flatten the nested optimizations into a single one.

More specifically, to group N smooth images \({{\mathcal{M}}}_{1},\ldots ,{{\mathcal{M}}}_{N}\) into K clusters, we solve the following optimization problem:

where C_k denotes the kth cluster, \({\overline{{\mathcal{M}}}}_{k}\circ {\overline{\alpha }}_{k}\) denotes the kth centroid, and \({{\mathcal{M}}}_{i}\circ {\alpha }_{i}\) denotes the ith transformed image flowing to its corresponding centroid together with all other N − 1 transformed images. One can check that (7) is an extension of (4) where we omitted χ for simplicity. Solving (7) is similar to k-means via alternating refinement:

• the assignment step assigns each transformed image \({{\mathcal{M}}}_{i}\circ {\alpha }_{i}\) to \({C}_{{k}^{\star }}\) according to

  $${k}^{\star }=\mathop{{\rm{arg}}\,{\rm{min}}}\limits_{k=1,\ldots ,K}{{\mathcal{D}}}_{C}({\overline{{\mathcal{M}}}}_{k}\circ {\overline{\alpha }}_{k},\,{{\mathcal{M}}}_{i}\circ {\alpha }_{i});$$

• the update step solves (7) for one gradient-descent step given the C_ks.

Upon convergence, we obtain \({C}_{1}^{\star },\ldots ,{C}_{K}^{\star }\) as clusters and \({\overline{{\mathcal{M}}}}_{1}\circ {\overline{\alpha }}_{1},\ldots ,{\overline{{\mathcal{M}}}}_{K}\circ {\overline{\alpha }}_{K}\) as centroids.