Self-Similarity Priors: Neural Collages as Differentiable Fractal Representations
Authors: Michael Poli
Winnie Xu
Stefano Massaroli
Chenlin Meng
Kuno Kim
Stefano Ermon
Venue: NeurIPS 2022 Accept (2022)
Keywords: implicit representations
compression
deep equilibrium models
generative models
fractal
fixed-point

Abstract: Many patterns in nature exhibit self-similarity: they can be compactly described via self-referential transformations. Said patterns commonly appear in natural and artificial objects, such as molecules, shorelines, galaxies, and even images. In this work, we investigate the role of learning in the automated discovery of self-similarity and in its utilization for downstream tasks. To this end, we design a novel class of implicit operators, Neural Collages, which (1) represent data as the parameters of a self-referential, structured transformation, and (2) employ hypernetworks to amortize the cost of finding these parameters to a single forward pass. We detail how to leverage the representations produced by Neural Collages in various tasks, including data compression and generation. Neural Collage image compressors are orders of magnitude faster than other self-similarity-based algorithms during encoding and offer compression rates competitive with implicit methods. Finally, we showcase applications of Neural Collages for fractal art and as deep generative models.

Self-Similaris Priors: Neural Collages as Differentiable Fractal Representations
Michael Poli" Stanford University MIL
Winnie Xu University of Toronto
Stefano Massaroli* Mila DI
Chenlin Meng Stanford University
Kuno Kim Stanford University
Stefano Ermon
Stanford University
CZ Biohub
Abstract
Many patterns in nature exhibit self-similarity; they can be compactly described via self-referential transformations. Said patterns commonly appear in natural and artificial objects, such molecules, shorelines, galaxies and even images. this work, we investigate the role of learning in the automated discovery self-similarii and in its utilization for downstream tasks. To this end, design novel class of implicit neural operators, Neural Collages, which (1) represent data the parameters of seff-referential, structured transformation, and (2) employ hypernetworks to amortize the cost of finding these parameters to a single forward pass. We detail how leverage the representations produced by Neural Collages in various tasks, including data compression and generation. Neural Collage image compressors
orders of magnitude faster than other self-similarity-based algorithms during encoding and offer compression rates competitive with implicit methods. Finally, we showcase applications of Neural Collages in fractal art and as deep generative models.
Introduction
Given specified image, can one come up with dynamical system with it its attractor? (Welstead, 1999)
Scientific fields are underpinned by search for structure. Geometry, sparsity and invariances, when appropriately introduced in mechanistic model, allow us to concisely describe phenomena. To this end, machine learning has been introduced as a means to fix partial priors in model, and discover the rest through data (Rackauckas et al., 2020; Dao et al., 2020; Bronstein et al., 2021). In general, the notion of structure is also essential for compression: through a suitable choice of language, one can explain phenomena in fewer symbols, yielding shorter representations of the observables (Tishby et al., 2000; Lee al., 2007). Objects exhibiting self-similarity structure are composed of patterns that appear similar to themselves at multiple scales, as shown in Figure 1. This type of structure frequently appears in nature, at different degrees: shorelines, molecules, plants, turbulent flows and basins of attraction of dynamical systems all display elements of self-similarit (Mandelbrot and Mandelbrot, 1982; Song et al., 2005; Vulpiani et al., 2009; Barnsley, 2014). In this work, we explore the role of learning in the automatic discovery of self-similaritt structure in data, and how it can serve as an inductive bias machine learning models.
The mathematical embodiment of this idea is found in fractal patterns, which often arise by charac- terizing limit sets nonlinear maps e.g. iterations of complex numbers for Julia and Mandelbrot
Equual contribution authors. Contact email: poli@stanford.edt
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sets (Julia, 1918; Mandelbrot, 1980). Fractals are ocale-invariang they can be "zoomed in" by increasing the resolution of the limit sets, and manifest arbitrarily similar patterns at different scales. Despite their apparent infinite complexity, fractal can be uniquely and compactly described by its generating nonlinear map.
A method to discover self-similar structure in data (not necessarily of fractal nature) can then be formalized as an optimization problem: after
2
SSS 2.5
choosing an appropriate class of contractive, pa- rameterized maps, one searches for parameters such that a given data point can be (approxi- mately) recovered as the (unique) fixed-pon point of the chosen map. This approach, pioneered in (Barnsley et al., 1986). paved the way for one of the most successful algorithmic appli- cations of self-similarity, fractal image com- pression (Jacquin et al., 1992; Jacquin, 1993; Barnsley et al., 1996; Welstead, 1999; Fisher, 2012). First, an encoding step carries out a search to solve the inverse problem of data to operator parameters via extensive search, or by restricting the class of operators such that closed-form solution may be found. Then, given the parameters, the decoding step solves for the exed-point of the operator, corresponding a corrupted version of the original data. The quality of decoded images i.e. the loss of the fractal compression method is directly tied with the expressivity of the class of operators considered, which are often designed seek self-similarities in pixel space. Yet, larger classes induce more challenging optimization problems, leading to long encoding times.
2222
Figure 1: [Top] MNIST digit fractalized via Collage.
The image is represented as the coefficients of a Collage. and decoded as its attractor. Magnification is done by decoding at higher resolutions. [Bottom] The Mandelbrot set (Mandelbrot, 1980). example of fractal displaying self-similarity.
Here, we propose novel beaninggbasse technique to extract and utilize self-similar representations of data. We develop Neural Collages, a family of differentiable, parametrized operators structured to capture self- self-similarity between partitions of data. The inverse problem of Neural Collages is solved with a single forward pass of a hypernetwork (Ha ct al., 2016) trained to generate a set of parameters the fractal code. This amortized approach is orders of magnitude faster than traditional search based methods. Collage operators are composable with neural network architectures and have wide applicability beyond compression, as they can be optimized end-to-end for variety of tasks including generative modeling.
In data compression, Neural Collages preserve advantages of fractal compression methods, with up to 10x (accounting for training time) and 100x (at test time) speedups during encoding. Further, we investigate deep generative models based Neural Collages, where Collage parameters assume the role of latent variables of a hicrarchical variational autoencoder (VAE) (Kingma and Welling, 2013). Collage VAEs can sample at resolutions unseen during training by decoding at higher resolutions through their Collage operator, revealing additional detail over upsampling via interpolation. Finally, we showcase applications for fractal art, where an image can be "fractalized" ie. reconstructed as a collage of smaller copies of itself at different scales (see Figure 1, top).
2 Problem Setting
We start with an example related core idea behind fractal compression and Neural Collages: representing data as the parameters of a function that converges to it.
2.1 Representing Data as Fixed-Poie of an Iterated Function
Consider a value x that happens be of interest for a downstream task, for example regression. Rather than performing computation on it directly, we can use the parameters w of a contractive map with x as its fixed-point, for example simple affine function with parameters w == (a. b).
a E IR, b E R:
xk+1 = azk + b, |a| << 1
2

---

Given w, the value x can be recovered by repeatedly applying the map starting from any other initial condition, that is
ax" b.
Parameters w can then replace an alternative representation, using two values (a, b) instead of
Other classes of functions, if chosen appropriately, can represent data with less parameters than its dimensionality, In general, encoding through function is lossy process: the original data is recovered up to a degree of accuracy. The insight behind fractal compression and Neural Collages is to view data sets, and define iterated functions ensembles of simple scalar linear functions acting on different subsets. Below, we introduce background required to make these notions precise.
2.2 Fractal Compression Background
We proceed by formalizing, fracttaa data encoding as an optimization problem (Barnsley and Demko, 1985; Fisher, 2012; Barnsley, 2014).
Let (X, d) be a complete metric space and (H((),, dx) its corresponding Haussdorff metric space, Le. H(X) {A C X A is compact). We represent data point as set S H(X). This choice of space supports an data modality-agnosti treatment of fractal data encoding. A concrete realization is discussed for image domains in Section 3. Results metric spaces provided as reference in Appendix A.
Example 1. Consider binary images square domain. Then, X is finite compact subset of R.2 An image S is the finite set of coordinates of either black or white pixels. Further, each image corresponds a point in H(X).
Let {f1, fe..... + fK} be a collection of maps on X. fs x iterated function system (IFS) (Barnley, 2014). We can then define a map F: H(X) + H(X) by
X. This is colloquially referred as
F(A) U (A( VA E HXX)
where (A) is intended as fA) (fx E A). An interpretation is the following: F produces as output a composition, or collage, of transformations applied to a subset A of X.
2.3 The Inverse Problem: Data to IFS
Given data S, can we find map F with S as its fixed point? This can be achieved by identifying a collection of maps fk X + X such that the following conditions hold
i. F H( + H(X); A + U (A) is contractive;
i. S is the fixed point of F, F(S) - (s);
Note that, F is contractive w.r. the Hausdorff metric with Lipsichitz constant < iff all the maps fk are contractive w.r.t d with constant lg < 1. In such a case it holds L = max {& and F admits unique fixed point. A classical result provides an indirect method to find such F. Theorem (Collage Theorem (CT) (Barnsley and Demko, 1985)). Let (X, d) be a complete metric space and let f X + % be E-Lipschitz contractive map with fixed point x² E X. Then,
1 d(x, x²) S 1 d(x, f())
(2.1)
By applying the CT directly to F using the Hausdorff metric dH. we have dH(S, A*) <
-- (s. data S and attractor A of F via d(S, F(S)), which requires a single application of F and is thus cheaper to evaluate. Even if it is not possible to stitch together transformed copies f& (S) to perfectly
This means that we can upper bound the distance du (S, A*) between
S * F(S)), a smaller IFS Lipschitz reconstruct the data S, i.c. du (s.UK_ fx()) + O (++
constant of the IFS implies a lower distance between the data S and the attractor A" of F, given a mismatch dx (S. F(S)). This, in turn, implicitly promotes the use of "very contractive" maps fx (i.e. with low f.). We refer to the procedure of searching for an F that minimizes the rhs of the CT bound as the fractal data encoding problem.
3

---

A learning perspective of fractal data encoding Fractal data encoding problem can be translated into finding parametric representation fx( wk). w R" for functions fx(-) (e.g. neural networks with parameters wx)) where w = (W1,.... wx) E W are optimized to minimize a Hausdorff metric loss function dx((S F(S; w)) naturally induced by the CT,
min wEW
dH U Sk wx))
(2.2)
To decode the data encoded in parameters w of F encodes in one samples any initial condition As. and iterates Ac+1 = ((Ae) until convergence to A R S.
IFS, PIFS and Beyond Partitioned iterated function systems (PIFS) (Jacquin et al., 1992) are a generalization of IFSs that can capture localized self-similarity by allowing each domain a contraction map f& to be different subset As C S. his introduces significant challenge in 2.2: the optimization problem need now determine optimal (as measured by dx²) domains A₂ for each f& by searching across all possible subsets of S, yielding exploding combinatorial problem.
Solving for affine IFS As with traditional approximation problems, there is a tension in the objective of fractal data encoding between the "expressiveness" of the class of functions, and the tractability of the optimization problem. The solution w of (2.2) is an equivalent representation for (up dx (S, A*) )))
Existing methods based on the idea of (Barnseey and Demko, 1985) resolve this tension by considering (a) compression a task, such that should be encodeable in the least number of bits possible and (b) affine functions {2; wx) = Ozæ + by- With these choices, a solution to (2.2) can be found in closed-form (Fisher, 2012), and the parametrization w results compact enough to be valid compression code- only two floats for each fo in F, i.e. w/ = (ak, by) E RR?.
There are number of limitations we aim to address:
Fractal data encoding is only considered as an intermediate step towards compression. We develop learning- based approach the solution of (2.2) for tasks beyond compression.
Solving (2.2) on collection of data as per (Fisher, 2012) is computationally expensive. We directly solve a collection of fractal data encoding problems in parallel via hypernetworks (Ha et al., 2016), effectively amortizing the cost.
As noted by (Welstead, 1999; Fisher, 2012), for an (affine) IFS provide a satisfactory solution to (2.2), the self-similarity property has to be global across the set S. That is, the entire set $ is made up of smaller copies of itself, most images are only self- self-similar to degree. To alleviate these restrictions, we develop Collage operators, a generalization of IFSs which can be broadly categorized as a soft-partitioned iterated function system (PIFS) (Jacquin et al., 1992).
part of itself, property that is rather rare in natural data: indeed,
3 Neural Collages
Moving forward, we treat Neural Collages algebraically. This allows us to discuss in detail the properties of Neural Collage, including algorithmic differences with other iterated function systems. To do so we consider, instead of generic sets, data that can be expressed as simple ordered sets: in other words, as vectors. Images will be our recurring example, with the understanding that the entire discussion can readily be adapted to other modalities e.g. sequences.
From generic sets to vectors Following the PIFS treatment of Øien and Lepsøy (1995), we focus analysis on Collage composed of affine maps, operating on the space of discrete images of given resolution with a total number m of pixels each taking values in R. Pixels of different channels treated without loss of generality different elements. This allows us to collect all pixel values in an ordered vector z E Imm.
A type of subsets on images involves the formation of square patches. Let us assume that each image is partitioned into (1) K non-overlapping range cells and (2) N ressibly-overlapping domain cells.
2 with specific predefined criterion, e.g. row-major ordering.

---

A range cell R3 is then of size 7r X Rr, such that m = Σx= k= n k. and domain cells D, are of size dd X d,n- With such coordinatization, the (affine) fixed-point map reduces to a structured affine contraction on m
Definition 1 (Neural Collage Operator). Consider a m-pixel image represented by the ordered vector E R Then, Collage Operator is defined as the parametric linear map:
F(z:w)=
Σ 12
Mhin 0k, T
Σ Rr
Jeabsa T
(3.1)
Sn R=a, xm selects a domain cell Dn, of Adn x Od,m pixels.
Pr.n R is pooling operator that shrinks the domain cell Dj into the size of the corresponding range cell Rg, i.e. from nd. Bd, to 0r x 0r pixels;
Tk E Bmxx positions the pooled domain cell in the correct range cell location and zerves out the rest:
ak,.n ban E R. scales and translates the value each pixel of the pooled domain cell, respectively.
Tk,n IR; convex combination of affine outputs produced from all N domains.
The parameters is the collection of all 0kens bu.n and the mixing weights "M...
Collage operators represent each range cell R3 convex combination of pooled and scaled versions of domain cells D, translated block-wise by bn. On individual range cells comprising the output, symbolic representation can be given
R Σ akn Dr + Σ Nk Y2
(3.2)
In the generic formulation, these maps correspond to functions f& of F. Differently from PIFS, each ft does not act on a different subset (domain cell) to produce R₁- Instead, all fk aggregate affine transformations parametrized by 4k,n, bb,n domains via 7,.n- However, each f& equipped with different mixing weights and different affine maps. Hence, Collage in this form can be seen soft-PIFS.
Introducing auxiliary domains A Collage step maps mixtures of all domains to each range, and assembles the ranges into its output. As Neural Collages often optimized datasets, rather than single data points, we posit that improvements in the expressiveness can be readily achieved by mixing additional dataset-level information through auxiliary domains Up-
Definition (Collage operator with auxiliary domains).
R2
R2 + Σ Tk Uk
In coordinates this translates to
K
F(2, u: (2;
Ok, To. Pk.
where F. (z) is (3.1) and Rg is (3.2), and the parameters w include the coefficients Tik.v ak,o of the auxiliary domains Us, as well as Tk.n ag,,, DR
We consider different variants of U.. including: deterministic transformations of domain cells D, e.g. rotations as per (Jacquin et al., 1992), learned cells directly parametrized and optimized for an objective, similar to feature maps in (Jaegle et al., 2021), and U, produced by neural network encoder. Specifies are provided in Section 4. schematic of a single step of Collage is given in Fig. 3.
5

---

3.1 The Forward Problem: Collage to Data
Given parametrization for the Collage operator Fw and an initial image 2u, the attractor 2" 2" = (z") can be recovered by iterating the fixed-point map
2++1 F(2; w)) A(w)z; + b(w)
assuming F to be a contraction w.r.t. the standard Fuclidean metric on R This can be ensured by appropriate choice of the coefficients dk,n " In particular, if all the mixing weights such that Em=1 7e.n = and lax.nl < 1, then contractivity of the collage operator follows as in standard PIFS (sec c.g. Fisher (2012)).
Note that the attractor of a Collage can be also computed in closed-form as =" [T A(w) [(()) A similar discussion follows for a general Collage with auxiliary domains. Note that auxiliary domains U across iterations are to be chosen such that the sequence {Ur)r= converges e.g. constant functions.
Pseudocode for a single step of Collage shown below. Figure 2 provides visualization of the convergence of Collage to its fixed-point (after repeated application of the operator).
def collage operator (self, collage. weight, collage_bise).
*o"Collage Operator (decoding). Performs the steps descrsbed in Def. 3.1, Figure 2. Split the current iterate 'z' into source patches according to the partétsoning scheme. domaina = ing_to_patcheate domains (pre csgnentation) range patch sises. apoled_domsiag
poel (domaine)
If needed, produce additional candidate source patches as augmentations of existing domsins, concalenate austliary patches paranetrized and optinised directly. if welf.n_ang_trame t__am__raansfomm
pooled_domsina self wwg.ggattnaaadiiiiee aaa.ttcccccdddeeepppeee.dd mooled_domaina repeat(poooldd (pmiiedd_ommais, "b c d ->->>> -> o d 9¹, r=self r=gelf-nun rang_
Apply offine saps
patches
dingeedd - ('beun(",erbbx, bedr -> berhw'' pooled_ donaine, collage_reight)
range_donainng range_ ranga_domaine collage_bias [..., Nons, Nono]
Reconstruct data compeasng the output patches back together.
z patches_tooinge wtt.etoooooorooooooiiiiii.
Decoding at higher resolutions A Collage can be applied, without change, to images of different resolutions. Consider scaling the resolution by factor > 1, (s E N). Then the magnified image representation is made up of s² images 2º R", The Collage operator can then be thought to act singularly on each z obtaining a forward fixed-point iteration
Enhn
a Tk Pk + Ehan Tg
2++1
k,m
When solving by unrolling the fixed-point iteration, the second term can be precomputed as it does not depend on zt.
3.2 Amortized Solution of the Inverse Problem
Iterations
Although the CT suggests a constructive pro- cedure via (2.2) to find valid fractal represen- tation w. there are no guidelines in case other objectives of interest. Further, the class of PIFS without modifications does not lend it- self well to numerical optimization it involves the combinatorial problem of matching domains to ranges. With their soft aggregation, Neural Collages can instead be used for task-based optimization. Given an input image z 18. we can optimize the parameters w (and pixel values u of the auxiliary domains) of the Neu- ral Collage operator minimize an objective Ju (Ix, 2n (w, u)) by solving a nonlinear program ming, Jun (v., (w, u)) with = 2w, u) obtained by the fixed point iteration on F(2, u; w). Choosing Ju to be a reconstruction objective yields problem similar to fractal data encoding (2.2).
Source
Figure 2: Collage forward problem: given w, different initial conditions decoded to the same z".

---

Suppose instead to be given an image dataset whose distribution is known only through i.i.d. samples I E IR, 2 p(z). In this context, the fractal data encoding problem in standard form needs to be solved for each sample Instead, we introduce an hypernetwork (Ha et al., 2016) & with weights 0, generating fractal code w given an input image x, i.e. parametrizing a map x - wo(
Vx p(x) (g(xx) (x;;))
The hypernetork is trained to solve the following empirical risk minimization problem, effectively amortizing the cost over the full dataset:
min Bx)((x) [J 2 (0,
8,8
subject to uz( =x;;;
(3.3)
2' (0.u) = f( (0, u), u; wo(x))
e U.
Collages in Learning Tasks
We showcase applications of Neural Collages as decoders for deep generative models, as neural compressors for images and as method to gen- erate fractal art. All variants of the model share common structure, outlined in Figure The code is available at github. com/ ermongroup/ self similarittyyyy tetttty-prirrr
encoder
Collage
decoder
Figure 3: Schematic of Neural Collage. In yellow, computation unique to the compres- sor variant; deterministically encoded into Collage parameters then used to decode. Similarly. blue indicates computation done by the fractalizer, and red by the generative variant, where w takes the role of a latent variable.
4.1 Generative Neural Collages
We investigate application of Neural Collages as deep generative models for distributions p(x:) of images. In this context, assume the role of latent variables. In particular, we consider hierarchical variational autoencoder (VDVAE) (Kingma and Welling, 2013; Child, 2020) model based on Neural Collages.
Magnifying samples via Collage VAEs such that the following lower bound (ELBO) on data log- likelihood be maximized
VAE models seek to data x into a latent representation w
Egg (lgg pa (x/[w)
D (lr S log 0)
distortion
where approximate posterior qo (w)z), prior (w)) and generator Pe (w) are implemented neural networks. A multiplicative hyperparameter ,3 is often introduce to control the relative weight between
Rate Distortion Curve 8 E 0.7, 12, 1.5]
Resolution: (28 28)
Resolution: (1120 1120)
07627 2 7
b 07 6
5
0
6 O | + 2 3
2
7
0.10
VIVAE
0.4
VDVAE
6607 9
6
6
7
9
Distortion
0.08
Collage VAE
0.3
0.06
0.2
Collage VAE
7 7 4 4
8
0.04
0.02
0.1
6 3 7
2
2
5
0.0
0.05
0.15
0.20
0.30
Direct Sample
Sample + interp.
Rate
Figure 4: [Left] Samples obtained from VDVAFs and Collage VAFS on dynamically binarized MNIST. agllage VAEs can generate samples at resolutions unseen during training, adding detail that cannot be obtained by (1) sampling first (2) upscaling via bicubic interpolation, first row. [Right] Rate-distortion curve on dynamically binarized MNIST, with a curve obtained by sweeping 3 in range. Collage VAEs are less sensitive the tuning of 3, and pay marginal price in Pareto suboptimality to gain the ability to sample at different resolutions.
done in the
7

---

rate and distortion (Higgins et al., 2016). In Collage VAE, qu(w[z) and (w) are parameterized as per (Child, 2020), except the approximate posterior qu (w[z) need not produce large feature maps but scalar Collage codes w. Moreover, pa (z/w) is a Collage such that by leveraging the consideration of Section 3.1, samples can be decoded at any resolution.
To investigate the properties of Collage VAEs, including quality of magnified samples, we compare VDVAEs and Collage VAEs on dynamically binarized MNIST. We report both test rate and distortion, following the analysis of (Alemi et al., 2018). This supports more detailed evaluation of model behavior at different 3 weights for the rate. We train several Collage VAËs and VDVAFs with 33 ranging in (0.5, 0.7, 1.0, 1.2. 1.5], and report the rate-distortion curve in Figure 4 (right), Collage VAEs are only marginally Pareto suboptimal, but are shown to be less sensitive to training under different 8, which is common strategy employed to stabilize VAE training ("KL warmup"). Furthermore, Collage VAEs can generate samples at resolution unseen during training, as showcased in Figure 4 (left). Direct samples at magnification factor of 40x reveal additional details over VDVAE samples that are magnified via bicubic interpolation. We note that as discussed in Section 5.1, the detail introduced by magnification is entirely dependent on the Collage class; future designs may be developed to introduce types of detail expected in a given dataset.
Results
4.2 Neural Collage Compressors
Next, we apply Neural Collage to image compression. We store images as the parameters of an affine Collage produced by a neu- ral encoder. After training, the en- coder can be used to compress ad- ditional images in parallel with single forward pass by producing the corresponding w. Figure 3 pro- vides an overview of the compu- tation done by a Neural Collage compressor. Collage compres- sors employ learned feature maps as auxiliary domains.
Method
t PSNR
bpp
Fractal (no aug.)
31.06
0.14
31.68
0.36
Fractal (augment.)
30.51
0.15
30.80
0.39
COIN
25.74
0.17
27.34
0.33
Neural Collage (ours)
31.30
0.13
32.12
0.31
block-DCT
33.22
0.13
34.65
0.32
Table Average peak signal-to-noise ratio (PSNR) at low (== 0.15) and medium (>= 0.30) bits-per-pixel (bpp) budgets of baselines (baseline fractal, implicit, spectral) and Neural Collages compressors. Neural Collages introduces less visi- ble artifacts than other self-similarity or implicit compression schemes, narrowing the gap with spectral compression methods such as JPEG.
For compression, the main desider- atum is visual fidelity: regular do- mains D,, allow Neural Collages to capture intra-image self-similarity, whereas auxiliary domains U optimized for image quality complement them by focusing on inter-image patterns.
Compression of high-resolution aerial images DOTA sarge-scale acrial images dataset (Xia et al., 2018). From the DOTA training set, produce
We consider compressing images obtained from the
Source
Fractal Compression
COIN
Newral Collage
Figure Visual comparison of decoded images from 1200 x 1200 crops of the DOTA dataset, obtained from different compression methods (= 0.30) bpp. Images decoded from Neural Collage codes exhibit less noticeable artifacts, with improved color preservation over COIN and more detail than fractal compression.
8

---

80000 random 40 x 40 crops as our training dataset. We optimize convolutional encoder parameters 0 27 (9. u))² + | The model is trained on the 40 x 40 crops and evaluated on 10 held-out 1200 x 1200 images. This possible as an image of any resolution can be first broken up into blocks of appropriate size, in this case the training resolution, 40 x 40, passed through the encoder to obtain the corresponding parameters, then concatenated to construct a valid code for the entire image. This operation can be performed in parallel by treating each block as an element of a pseudo-batch. Neural Collage compressor can thus be used to compress images of any resolution at test time, without retraining.
and auxiliary sourees on the reconstruction objective J(z, = (0, u)) = >i=1(x; (x;
Results We compare peak signal-to-noise ratio (PSNR), in addition encoding and decoding mea- surements for a variety of compression basclines. We contextualize our results with comparisons to both non-neural as well as another implicit neural compressor. In particular, we evaluate the perfor- mance of a standard PIFS-based fractal compression as per (Jacquin, 1993), implemented to exploit parallelization GPU, and COIN (Dupont et al., 2021). Fractal compression baselines and Collage both use non-adaptive tiling partitioning schemes. We evaluate two variants of fractal compression, one where domain cells are augmented via rotations and color flips (Welstead, 1999), and one without augmentations. We further compare with block-DCT, the spectral lossy compression backbone of most JPEG codecs. All compression methods are evaluated at low and medium bpps, with metrics provided in Table 1. Figure 5 provides a visual comparison of images obtained by decoding the lossy code of each method. Neural Collages show less noticeable artifacts and improved color retention.
Finally, Table provides wall-clock time mea- surements of all methods during the respective per image encoding and decoding procedures. Results for COIN and Neural Collage measure encoding times (including the training proce- dure), and encoding times after training. Neural Collages are orders of magnitude faster than fractal compression and, test-time, of COIN. Although spectral lossy compressors common in state-of-the-an codecs perform with best PSNR in medium and high bpp settings, Collages nar- rows the gap in terms of reconstruction quality as well as encoding speed.
Wall-clock measurements
e Decoding
Encoding <Encoding (test)
10
seconds
10a
10a
101
100
10-1
Block Fractal COIN Collage
Figure 6: Wall-clock time (s) measurements of compression methods applied to the held-out set of DOTA. For neural compressors, we report encod- ing times including training, as well as encoding times on unseen images (after training). At test time, encoding for Neural Collage compressors is x00x faster than fractal compression.
Code length of a Collage The total bits-per- pixel (bpp) cost of the code w corresponding to the parameters of a Collage depends on the coding scheme used to store each numeric entry. We exploit bounds on a, b, 7, enforced via tanh and softmax, as well as regularization to reduce the total cost. The L2 regularization term on is introduced to shrink the range of values assumed by elements of w, ensuring that less bits can be used for storage. We do not use lossless coding schemes to store parameters of Collages and other baselines. Further details provided in the Appendix.
4.3 Neural Collages for Fractal Art
When data is represented through the parameters w of a Collage, it can be arbitrarily magnified by decoding at any resolution. The type of patterns revealed through magnification need not be corresponding to real detail missing from the image. particular, the patterns found depend on how one generates domains, auxiliary domains and class of operator Fw. Similar phenomena have been observed in the literature of fractal compression (Mitra et al., 2000). As an example, consider Figure 7, where the fractal pattern of snowflakes within snowflakes does not correspond to reality. We call this type of globally self-referential magnification as fractalization of an image. Here, we use Neural Collage fractalizers to generate fractal art
We solve the inverse problem of a Collage, namely image x to w, via a convolutional architecture parametrized by 0. The objective of the inverse problem (3.3) is reconstruction objective J(x, 2" 20000" u)) = "0= (x; - 2 (0, u))² where 2" is the fixed-point of the Neural Collage with parameters computed through the encoder w Ez)).. We choose the single
Experimental details

---

domain D to be the entire image. Before applying Fw. we augment the domain via rotations of itself, utilizing those as auxiliary domains. Figure 1 and show example fractalizations possible with Neural Collages, on greyscale and RGB images. The images can be magnified to any resolution (up to memory limits), revealing multiple fractal levels.
5 Related Work and Conclusion
Implicit representations and models Repre- sentation of data implicitly through functions is extensively used in simulation (Osher et al., 2004). (Sitzmann et al., 2020; Mildenhall et al., 2020; Dupont et al., 2021) parametrize the im- plicit functions via neural networks for use in downstream tasks such compression. Implicit models, on the other hand, solve optimization problems within their forward pass (Poli et al., 2020). Neural Collages belong to both classes of methods: fixed-point iteration with param- eters defining data implicitly. In particular, Neu- ral Collages can be framed
Figure Fractalization of greyscale and RGB images via Collage. The images are compressed as the coefficients of a Collage, and decoded as its attractor. Note that the above is a showcase of global fractalization: no partitioning is performed. and the entire image itself is taken as the source.
compactly- parametrized operator variant of deep equilib- rium networks (DEQs) (Bai et al., 2019), with parameters produced by a hypernetwork (Ha al., 2016).
Fractal compression The idea of representing images through iterated function systems (IFS) dates back to (Bamsley and Demko, 1985; Barnsley, 1986). Jacquin et al. (1992) introduces more flexible fractal compression schemes for images based on partitioned iterated function systems (PIFSs). Since then, alternative partitioning schemes i.e. adaptive quadtrees have been proposed. We refer to (Fisher, 2012) for an overview of the main variants. Additional references are provided in the Appendix.
Conclusion This work builds a framework for a learning -aased approach to automated discovery of self-similarity. We introduce Neural Collages, implicit models designed to represent and manipulate data as the parameters of a structured fixed-point iteration, and showcase their application to compression and deep generative modeling of images. We envisage future use of Neural Collage with other data modalities with naturally occurring self similarit, such as audio, sequences, or turbulent flows.
Acknowledgments
This work is supported by NSF (1651565), AFOSR (FA95501910024), ARO (W911NF-21-1-0155)) ONR, DOE, CZ Biohub, and Sloan Fellowship.
References
A. Alemi, B. Poole, I. Fischer, J. Dillon, R. A. Saurous, and K. Murphy. Fixing broken elbo. In International Conference on Machine Learning, pages 159-168. PMLR, 2018.
S. Bai, J. Z. Kolter, and V. Koltun. Deep equilibrium models. arXiv preprint arXiv: 2019.
M. F. Barnsley. Fractal functions and interpolation. Constructive approximation, 2(1):303-329, 1986.
M. F. Barnsley. Fractals everywhere. Academic press, 2014.
M. F. Barnsley and S. Demko. Iterated function systems and the global construction of fractals. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 399(1817) 243-275, 1985.
M. F. Barnsley and L. P. Hurd. Fractal image compression, volume 366. AK peters Wellesley, 1993.
10

---

M. F. Barnsley, V. Ervin, D. Hardin, and J. Lancaster. Solution of an inverse problem for fractals and other sets. Proceedings of the National Academy of Sciences of the United States of America, 83 (7):1975, 1986.
M. F. Barnsley et al. Fractal image compression. Notices of the AMS, 43(6):657-662, 1996.
M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković. Geometric deep learning: Grids, groups, graphs. geodesics, and gauges. arXiv preprint arXiv:2104.13778 2021.
R. Child. Very deep vaes generalize autoregressive models and can outperform them on images. arXiv preprint arXiv:201 101650, 2020.
T. Dao, N. S. Sohoni, A. Gu, M. Eichhor,, A. Blonder, M. Leszezynski, A. Rudra, and C. Ré. Kaleidoscope: An efficient, learnable representation for all structured linear maps. arXiv preprint arXiv:2012.11966, 2020.
A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghann, M. Minderer, G. Heigold, S. Gelly, et al. An image is worth 16x16 words: Transformers for image
recognition scale. arXiv preprint arXiv:2010. 1929, 2020.
E. Dupont, A. Goliñski, M. Alizadeh, Y. W. Teh, and A. Doucet. Coin: Compression with implicit neural representations. arXiv preprint arXiv:2103.0311 2021.
Y. Fisher. Fractal image compression: theory and application. Springer Science Business Media, 2012.
R. C. Guido, I.. S. Vieira, S. B. Junior, F. L. Sanchez, M. B. A. Guilherme, K. I. C. Sergio, T. L. Scarpa, E. S. Fonseca, J. C. Pereira, and M. Monteiro. A fractal and wavelet-based approach for audio coding. In Eighth IEEE International Symposium on Multimedia (ISM'06), pages 253-256.
IEEE, 2006.
D. Ha, A. Dai, and Q V. Le. Hypemetworks. arXiv preprint arXiv:1609.09106 2016.
I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner. beta-vae: Learning basic visual concepts with a constrained variational framework. 2016.
A. E. Jacquin. Fractal image coding: A review. Proceedings of the IEEE, 81(10):1451-1465, 1993.
A. E. Jacquin et al. Image coding based on a fractal theory of iterated contractive image transforma- tions. JEEE Transactions on image processing, 181):18-3,, 1992.
A. Jaegle, S. Borgeaud, J.-B. Alayrac, C. Doersch, C. Ionescu, D. Ding, S. Koppula, Zoran, A. Brock, F. Shelhamer, et al. Perceiver io: A general architecture for structured inputs & outputs. arXiv preprint arXiv:2107.147900 2021.
G. Julia. Mémoire sur I l'itération des fonctions rationnelles. J. Math. Pures Appl., 8:47-245, 1918.
D. P. Kingma and M. Welling. Auto-encoding variational bayes. arXiv preprint arXiv: 1xXiv:1312.00 131.66114, 2013.
H. Lee, A. Battle, R. Raina, and A. Y. Ng. Efficient sparse coding algorithms. In Advances in neural information processing systems, pages 801-808, 2007.
I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint arX1v:1711.05101, 2017.
B. B. Mandelbrot, Fractal aspects of the iteration of z- Az (1-z) for complex À and Annals of the New York Academy of Sciences, 357(1):249-255 1980.
B. B. Mandelbrot and B. B. Mandelbrot. The fractal geometry nature, volume 1. WH freeman New York, 1982.
B. Mildenhall, P. P. Srinivasan, M. Tancik, J. T. Barron, R. Ramamoorthi, and R. Ng. Nerf: Repre- senting scenes as neural radiance fields for view synthesis. In European conference on computer vision, pages 405-421. Springer, 2020.
S. K. Mitra. C. Murthy, and M. K. Kundu. A technique for image magnification using partitioned iteratixdupom:2222conn function system. Pattern recognition, 33(7):119-1113, 2000.
G. E. Øien and S. Lepsdy. A Class of Fractal Image Coders with Fast Decoder Convergence, page 153-175. Springer-Verie Verlag, Berlin, Heidelberg, 1995. ISBN 03879421 14.
Osher, R. Fedkiw, and K. Piechor. Level set methods and dynamic implicit surfaces. Appl. Mech. Rev. 57 15-B11, 2004.
11

---

M. Poli, S. Massaroli, A. Yamashita, H. Asama, and J. Park. Torchdyn: A neural differential equations library. arXiv preprint arXiv:2009.09446 2020.
C. Rackauckas, Y. Ma, J. Martensen, C. Warner, K. Zubov, R. Supekar, D. Skinner, A. Ramadhan, and A. Edelman. Universal differential equations for scientific machine learning. arXiv preprini arXiv:2001. 04435, 2020.
V. Sitzmann, J. N. Martel, A. W. Bergman, D. B. Lindell, and G. Wetzstein. Implicit neural representations with periodic activation functions. arXiv preprint arXiv:2006.09661 2020.
C. Song. S. Havlin, and H. A. Makse. Self-similarity of complex networks. Nuture, 433(7024): 392-395, 2005.
K. Sun, S. Lee, and P. Wu. Neural network approaches to fractal image compression and decompres- sion. Neurocomputing, 41(1-4)911-177, 2001.
N. Tishby, F. C. Pereira, and W. Bialek. The information bottleneck method. arXiv preprint physics/0004057, 2000.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L.. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 900886008, 2017.
A. Vulpiani, F. Cecconi, and M. Cencini. Chaos: from simple models to complex systems, volume 17. World Scientific, 2009.
T. Welstead. Fractal and wavelet image compression techniques, volume 40. Spie Press, 1999.
G.-S. Xia, Bai, J. Ding, Z. Zhu, Belongie, Luo, M. Datcu, Pelillo, and L. Zhang. Dota: large-scale dataset for object detection in aerial images. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 3974-3983, 2018.
Z. Zha, X. Yuan, J. Zhou, C. Zhu, and Wen. Image restoration simultaneous nonlocal self-similarity priors. IEEE Transactions on Image Processing, 29:8561-8576, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix B.2
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proof' of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)?
[Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No]
(d) Did you include the total amount of compute and the type resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're re
ing/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "uC2c3DFWjF", "reviewer": "Reviewer_zn4B", "summary": "This paper studies using learning algorithms to improve fractal compression. The fractal compression leverages self-similarities to compress the data, which happens in many common signals, such as images. However, the expressiveness of the compression is constrained by the model families it uses. Traditional methods use affine transformations, which is limited. This paper consider a learning-based method, which they call Collage. They also propose a hypernetwork to tackle the potential optimization difficulties. \n", "questions": "- It seems we need some conditions to ensure the convergence when solving the optimization problem. However, I don’t see it to be explicitly imposed in the algorithm design. Do I miss it in the paper anywhere?\n\n- When solving the optimization problem below line 228, usually how many iterations do we need to get z*? And if the iteration is a lot, would that create any issues? (i.e. RNN with many time stamps.) \n\n- There are many algorithms proposed to use a single feedforward pass of a neural network to solve different optimization problems. However, many problems are not really solved well by neural networks. How about the case of the hypernetwork here? \n\n", "limitations": "No. The authors mention in Appedix B.2, however, there is only Appendix B.1.  Also, it would be great to discuss the limitation too. As it's a new attempt on this compression method, I tend to believe there are still rooms to improve. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strong \n\nA new learning- based method to improve a classic compression algorithm with significant performance improvements as shown numerically and visually in the experiments. \n\n# Weak\n\n- The paper is not easy to follow to be honest as a paper in a machine learning venue. Although the authors spend quite an amount of effort describing fractal compression in Section 2, and covers some theoretical results. In the end, I have to read other papers first to understand the idea.  I would suggest the author to provide more illustrative examples to guide readers not in compression background to understand the task and shortens some mathematical properties by moving to the appendix, as they are proven by previous literature and not really mentioned in the main algorithm design.  I want to note that I’m criticizing the paper working on applications from other domains. It would be better if the authors make the problem more clear to the readers as it is in a ML venue not in the signal processing venue.   This comment might be biased as I’m not an expert in this domain. \n\n- It would be nice to provide more methodology details. For example, what is J here in the final equation which depends on d_H, also what’s the hypernetwork architecture and the output .. etc. Providing more algorithm details would greatly help reader to capture the idea of the proposed method.  \n\n- The related works are shortened too much. It would be great if the authors provide a better overview of the recent progress of learning-based compression methods in the related works. For example, in addition to the very first NeRF paper, there are many great follow-up works worth mentioning.  A suggestion is the same as above by moving some non-necessary results from the prior works to the appendix to gain more space. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ONO1sRAv2Bb", "reviewer": "Reviewer_d8rc", "summary": "This paper proposes a collage function which is parameterized to be able to generate variable-resolution images according to a fractal pattern.  To be able to handle datasets/distributions, this collage function is parameterized using a hypernetwork which takes the entire example as its input.  This is used to achieve improved image compression and variable-resolution image generation.  \n\nNotes: \n\n  -Natural patterns described using \"self-similarity\", self-referential transformation.  \n\n  -Represent data with self-referential transform, in single forward pass.  \n\n  -Collage VAE can generalize over multiple possible image resolutions.  \n\n  -Given an image z, iterate fixed point map: z[t+1] = A(w)z[t] + b(w)\n\n  -Constrain collage function to be a contraction.  \n\n  -We can fit this separately for each image, or use hypernet based on a full-image encoder.  \n", "questions": "To what extent do datasets in machine learning really have a fractal structure?  I feel like this paper is somewhat split between completely artificial examples (like the snowflake made of snowflake images) and natural image datasets where the existence of fractal structure is non-obvious.  It would be nice if there were more datasets with a fractal structure which is somewhat organic.  Perhaps satellite images of weather patterns?  ", "limitations": "Yes I don't think there is an ethical issue, and the limitations are fairly straightforward.  ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n  -The ability to generate with dynamics resolutions is an interesting property.  \n\n  -The improvements on image compression are nice but the baselines all use either implicit representations, fractals, or non-neural (if I read it correctly).  \n\n  -The subject of the paper is fairly creative and seems unique.  \n\nWeakness:   \n\n-(Minor): In Figure 1, it might be more compelling to give a natural machine learning example on the top row.  Although I suppose the fact that the fractal structure is exact is perhaps worth something.  \n\n  -(Minor): In Figure 5, the red/blue outlines around the sub-images should be much thicker.  Many readers will miss it currently.  \n\n  -Constructing the parameters of the collage function F may be a lot to ask an encoder network to do.  If I understand it correctly, this means compressing the entire object's information into a single vector (or a small set of vectors, independent of the size of the object) which is used to parameterize F?  \n\n  -The experimental strategy is a bit odd to me.  It seems like the best result to show would be that the method improves the generative modeling of data with a clear fractal structure (either hand-designed or natural).  Then, it would be interesting to show that other deep learning methods fail to generalize over this fractal structure (which I suppose they are limited due to having a fixed resolution, but could be interesting to study over some range of resolutions).  \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-XKn_ly40Pe", "reviewer": "Reviewer_4iU4", "summary": "Fractal compression represents data (for example an image) as the fixed point of a parameterized operator. Encoding the image requires finding the parameters of the operator (typically done via an explicit search algorithm), while decoding the image requires iterating the operator to recover the fixed point.\n\nThis paper proposes neural collages, which as in fractal compression represent data as the fixed point of a parameterized map, but uses hypernetworks to amortize the cost of finding these parameters.\n\nThe paper introduces the method, and uses it as the decoder for deep generative models, for image compression, and to generate fractal art.", "questions": "- What was the architecture used for the hypernetwork? Is there any intuition or heuristics for how to design that architecture? I don't have any intuition for what one might expect to work there.\n- Could you add a little more detail about the auxiliary domains? How much do those affect the overall performance?", "limitations": "yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The core idea is original, and an interesting way of leveraging neural networks for fractal image compression.\n- The applications nicely demonstrate the wide applicability of the method.\n- The presentation of the method could be clearer, with more intuition to accompany the idea, and some clearer distinction between what is prior background vs. new ideas.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept