# Size Effects in Periodic Metamaterials

Victor V. Gozhenko  Institute of Physics, Natl. Acad. of Sciences of Ukraine,
46 Nauky Ave., Kyiv 03680, Ukraine<EMAIL_ADDRESS>
###### Abstract

The optical properties of periodic electromagnetic metamaterials are
considered as functions of their relative unit cell size $d/\lambda$. The
reflection $R$ and transmission $T$ coefficients are numerically calculated
for some realistic metamaterials in a wide range of their relative unit cell
size values that comprises different operating regimes of the metamaterials.
Peculiarities in $R$ and $T$ behavior are discussed and the causes of those
peculiarities are outlined. The obtained results support the opinion on
inapplicability of the very homogenization concept to metamaterials whose unit
cell size is comparable to the incident wavelength, in contrast to some
previously published results.

##  I Introduction

Most of the electromagnetic metamaterials are periodic structures, and their
unit cells consist of artificial inclusions designed to get a specific
electromagnetic response (e.g., negative refraction or selective reflectivity)
of the metamaterial sample as a whole. Periodic metamaterial can be treated as
a continuous and homogeneous medium if its unit cell size $d$ (the lattice
constant) is much smaller then its operating wavelength $\lambda$,
$d\ll\lambda$. In such a case, the metamaterial can be characterized by its
effective parameters—the effective permittivity $\varepsilon_{\textrm{eff}}$,
permeability $\mu_{\textrm{eff}}$, and index of refraction (the refractive
index) $n_{\textrm{eff}}=\sqrt{\varepsilon\mu}$, see Fig. 1.

Figure 1: The concept of metamaterials homogenization. A periodic metamaterial
with unit cells of size $d$ is lit by an incident electromagnetic wave whose
wavelength is $\lambda$. If $d\ll\lambda$, then the incident wave cannot
“feel” the metamaterial inhomogenities, and metamaterial behave itself like a
continuous and homogeneous medium, whose parameters are
$\varepsilon_{\textrm{eff}}$, $\mu_{\textrm{eff}}$, $n_{\textrm{eff}}$.
Representation of a metamaterial by the corresponding homogeneous medium is
correct if the optical properties (e.g., reflectance and transmittance) of the
metamaterial and the medium are the same.

Calculation of the effective parameters values for a given metamaterial (with
given shape, size, and material of its inclusions, as well as the size and
geometry of its unit cell) is important, for example, for predicting the
optical properties the metamaterial will reveal in experiments and
applications, and is based on calculating the local electric and magnetic
fields within the unit cell and proper averaging of those fields over the
cell. Sometimes—in case of simple inclusions—it can be done analytically; in
general case, numerical computations are required.

To facilitate calculation of the effective parameters of periodic
metamaterials, a number of homogenization theories and methods were proposed
(see, e.g., Refs. 1, 2, 3, 4, 5, 6). Those methods differ from each other by,
particularly, the way they calculate the average values of the local fields in
the metamaterials.

In metamaterials applications, condition $d\ll\lambda$ (say, $d=0.01\lambda$)
is not always met. For example, optical applications (where $\lambda\approx
400\ldots 800$ nm) implies that the unit cell size should be of the order of
50 nm or less. However, metamaterials with $d=200\ldots 300$ nm (i.e.,
$d/\lambda\approx 0.25\ldots 0.5$) are often used there because the less the
unit cell size, the more expensive manufacturing process of the metamaterial
sample. On the other hand, some applications—most notably the negative index
of refraction—require for a metamaterial to work in the resonant regime (where
the negative $n$ is achieveable) meaning $d/\lambda\approx 0.5\ldots 1.0$.
Therefore, some authors tried to elaborate homogenization methods suitable for
an extended range of $d/\lambda$ values, and not only for small $d$. Some of
them believe that their methods are valid for metamaterials with substantial
or even arbitrary unit cell size (e.g., Refs. 1, 3, 6).

Strictly speaking, any homogenization method can give plausible results for
metamaterials working in the long wavelength (quasistatic) regime only, where
the condition $d\ll\lambda$ is satisfied. In the opposite case of short
(relative to the unit cell size) waves, $d\gg\lambda$, the very homogenization
concept should fail, and metamaterials cannot be treated as homogeneous media.
In this case, propagation of incident waves through a metamaterial obeys the
geometrical optics laws, and reflection of an incident wave from the
metamaterial inclusions plays a crucial role. Last, in the intermediate
regime, where $d\approx\lambda$, homogenization methods should not work since
they do not account for the diffraction effects (e.g., the Bragg’s reflection)
which are significant in this case.

Earlier [4], it was shown that different homogenization methods give more and
more diverging results as the relative unit cell size of metamaterials
increases from zero to approximately $d/\lambda=0.4$. At larger $d/\lambda$
values, calculations of homogenized effective parameters of a metamaterial can
still formally be performed, but those parameters cannot describe correctly
the optical properties of the metamaterial.

In the present paper, the optical properties of periodic metamaterials are
considered in a wider range of their relative unit cell sizes $d/\lambda$, and
the effects of the cell size on the optical behaviour of the matematerials is
discussed in more details.

##  II Basic formulae

We are interested in calculating the observable quantities—transmittance $T$
and reflectance $R$ of a metamaterial—which are dimensionless coefficients
defined as

$T=\frac{I_{\textrm{tr}}}{I_{0}},\qquad R=\frac{I_{\textrm{ref}}}{I_{0}},$

where $I_{0},I_{\textrm{tr}},I_{\textrm{ref}}$ are the intensities of
incident, transmitted through the metamaterial, and reflected waves. The
intensities are the energy flux densities of the corresponding waves and can
be calculated as time-averaged values of the Poynting vector $\mathbf{S}$ of
those waves (indices are omitted below for simplicity):

$I=\langle\mathbf{S}\rangle=\frac{1}{\tau}\int\limits_{t}^{t+\tau}\mathbf{S}(t^{\prime})dt^{\prime}$

In case of monochromatic incident plane wave

$\displaystyle\mathbf{E}=\mathbf{E}_{0}e^{[i(\mathbf{k}\cdot\mathbf{r}-\omega
t)]},$ (1)
$\displaystyle\mathbf{H}=\mathbf{H}_{0}e^{[i(\mathbf{k}\cdot\mathbf{r}-\omega
t)]}$ (2)

all the waves involved are also monochromatic and their intensities can be
calculated from

$I=\frac{1}{2}\textrm{Re}(\mathbf{E}\times\mathbf{H^{*}}),$

where the asterisk denotes the complex conjugation. From the energy
conservation law applied to the interaction of electromagnetic waves with a
lossy medium, it follows

$T+R+A=1,$

where $A$ is the absorptance (the absorption coefficient) of the medium which
define the rate of electromagnetic energy absorption inside it. If $T$ and $R$
values for a medium are known (i.e., are experimentally measured or
theoretically calculated), its absorptance can be found as

$A=1-T-R.$

##  III Numerical results and discussion

Numerical simulations are carried out for metamaterials with cubic lattice and
consisted of inclusions of various shapes that are often used in metamaterial
science and applications—spheres, rods, Split-Ring Resonators (SRRs), and
$\Omega$-like inclusions (“omegas”). Optical reflectance $R$ and transmittance
$T$ of the simulated metamaterials are calculated in a wide range of their
relative unit cell size $d/\lambda$ at several values of the incidence angle
$\theta$. Calculations of $R$ and transmittance $T$ are complemented with the
local $E$ field distributions across the unit cells in different regimes the
metamaterials operate in. All the calculations are performed with COMSOL
Multiphysics software. Presented below are exemplary calculation results.

Schematics of the unit cells of the simulated metamaterials are shown in Fig.
2. The materials are primarily infinite monolayers of thickness $d$ and that
in Fig. 2d is a triple layer of thickness $3d$. The unit cell size $d=500$ nm
is the same for all the materials and remains unchangeable in all the
calculations. Variations in the relative unit cell size $d/\lambda$ are made
by changing the wavelength $\lambda$ of the incident wave.

Figure 2: Unit cells of the simulated metamaterials: (a) a monolayer of
spherical particles; (b) a monolayer of omegas; (c) a monolayer of SRRs and
rods; (d) a triple layer of spherical particles. All the inclusions are made
of gold, and the size of the individual unit cells is $d=500$ nm.

From Fig. 3 one can see that all the inclusions give a prominent response to
the incident wave even at normal incidence, the response of spherical
inclusions being dipole-like (see panel (a), the field distribution in the
middle plane), while those of “SRRs with rods” system and “omegas” are more
tricky.

Figure 3: Local distributions of the absolute value of the electric field
$\mathbf{E}$ inside the unit cells of the metamaterials shown in Fig. 2a–c.
Left column, the field on the unit cell boundaries; right column, the field in
the middle plane of the cells. $\lambda=1000$ nm, normal incidence
($\theta=0$). Directions of $\mathbf{E}$ and $\mathbf{H}$ vectors of the
incident wave are depicted in panel (a). Distribution of $|\textbf{E}|$ allows
one to easily determine those places where the electric energy is
concentrated.

The incidence angle $\theta$ also affects the electromagnetic field
distribution inside metamaterials: even for simple spherical inclusions in the
quasistatic regime ($\lambda=10d$) the electric fields in the unit cell differ
substantially at normal and oblique incidence, see Fig. 4.

Figure 4: Local distribution of $|\mathbf{E}|$ over the unit cell boundaries
in a monolayer of golden spheres at $\lambda=5000$ nm. (a) $\theta=0$; (b)
$\theta=45^{\circ}$.

Shown in Figs. 5–7 are the transmission and reflection spectra numerically
calculated for the metamaterials depicted in Fig. 2a,c,d.

Figure 5: Transmission and reflection spectra of a monolayer of golden spheres
at normal and oblique incidence, $\theta=0$ and $\theta=45^{\circ}$.

According to Fig. 5, at normal incidence of a long enough wave with
$\lambda=3000$ nm (which is six times the unit cell size $d$) onto the
monolayer of golden spheres, the metamaterial behaves itself as a transparent
sheet: its reflection coefficient $R$ in this regime is close to zero, and its
transmission coefficent $T$ is near unity. If $\lambda$ decreases and
approaches the unit cell size $d$, the metamaterial gradually looses its
transparency and becomes more and more reflective. The reflection coefficient
has its maximum $R=0.45$ at $\lambda=1.2d=600$ nm, and the transmission
coefficient is minimal ($T=0.3$) at this point. Further decrease of $\lambda$
results in monotonic increase of the material transparency (with the peak
value $T\approx 0.77$ at $\lambda=d=500$ nm) and monotonic decrease of its
reflectance up to $R\approx 0$. The radical change in the behavior of $R$ and
$T$ at $\lambda\leq 600$ nm (when $d/\lambda\geq 0.83)$ is probably due to the
onset of the diffraction and interference effects in the periodic
metamaterial.

Note that the sum $T+R$ becomes distinctly less then unity at $\lambda\leq
650$ nm, or $d/\lambda\geq 0.77$. It means that light absorption by the
metamaterial is substantial in this case. The minimum value of the absorption
coefficient $A=1-T+R\approx 0.67$ is observed at $\lambda=550$ nm, which
implies that about one third of the incident energy flux is absorbed by the
metamaterial inclusions. The absorption can be ascribed to electric currents
induced in individual inclusions (golden spheres) by the incident wave as well
scattered waves from neighboring particles.

Analogous behavior is observed at oblique incidence (see the respective curves
in Fig. 5 for the case of $\theta=45^{\circ}$): with decreasing $\lambda$, the
region of insufficient changes in $R$, $T$ passes (starting from
$\lambda\approx 1.8d=900$ nm) to the region of their abrupt changes and
oscillating behavior. Note, however, that the metamaterial in this case is
semi-transparent even at large $\lambda$: $R+T\approx 0.62$ at $\lambda=3000$
nm.

Figure 6: Transmission and reflection spectra of a monolayer of golden
inclusions “SRRs plus rods” at normal and oblique incidence, $\theta=0$ and
$\theta=45^{\circ}$.

The plots in Fig. 6 refer to the monolayer of golden inclusions “SRR plus rod”
and have three distinct regions at both normal and oblique incidence. With
decrease in $\lambda$ from its maximum value 5000 nm to approximately 3200 nm,
the optical properties of the monolayer change monotonically. Further, up to
$\lambda\approx 1400$ nm, there is the region of oscillations, where one can
observe peaks and dips of $R$ and $T$ at wavelenghts that are nearly multiples
of $d=500$ nm. Those peaks and dips can be ascribed to the grating resonances
occurred in periodic systems as a result of interaction between their
structural elements excited by the incident wave. With further decrease in
$\lambda$, the oscillations of $R$ and $T$ become more chaotic. As in the case
of spherical inclusions, the layer of SRRs and rods looks translucent even at
large enough wavelenghts: $T+R<0.6$ at $\lambda=10d=5000$ nm.

Figure 7: Transmission and reflection spectra of a triple layer of golden
spheres at normal and oblique incidence, $\theta=0$ and $\theta=45^{\circ}$.

The peculiarities in the optical behavior of monolayers of golden spheres and
SRRs with rods can also be observed in a thicker triple layer of golden
spheres, see Fig. 7. In this case, notice the two peaks in $R$ (at normal and
oblique incidence) and the dip in $T$ (at normal incidence) which are all
located exactly at $\lambda=1000$ nm, which is two times the lattice constant
$d$. Obviously, they can be ascribed to the above mentioned grating
resonances.

##  IV Conclusions

The obtained results confirm the opinion [4] that any metamaterial
homogenization method should be used with care in the intermediate operating
regimes, when the metamaterial unit cell size is of the order of the operating
wavelength. The value of the relative unit cell size $d/\lambda$ at which
homogenization methods fail to predict the optical properties of periodic
metamaterials depends on the geometry and material parameters of their
inclusions. For the metamaterials we considered here, abrupt and substanial
changes in the optical properties (as compared to their longwavelength values)
occur at different values of $d/\lambda$: near 0.56 for the monolayer of
golden spheres at oblique incidence, 0.4 for the triple layer of golden
spheres at normal incidence, and near 0.16 for the monolayer of SRRs with
rods. For larger $d/\lambda$ values, a crucial role in the optical properties
formation play the diffraction and interference effects in the metamaterials,
so the properties exhibit an oscillating behavior which cannot be predicted
within the homogenization concept.

## References

  * [1] Pendry J.B., Holden A.J., Robbins D.J. and Stewart W.J. IEEE Trans. Microw. Theory Tech. 47 2075–84 (1999).
  * [2] D. Smith and J. Pendry, J. Opt. Soc. Am. B 23 391-403 (2006).
  * [3] I. Tsukerman, J. Opt. Soc. Am. B 28 577–86 (2011).
  * [4] V.V. Gozhenko, A.K. Amert, and K.W. Whites , New J. Phys. 15 043030 (2013).
  * [5] S. Yoo et al., Nanophotonics 8 (6) 1063–1069 (2019).
  * [6] O. Rybin and V. Khardikov, Optik 268 169768 (2022).


# Hilbert Flattening: a Locality-Preserving Matrix Unfolding Method for Visual
Discrimination

Qingsong Zhao
Tongji University, China
<EMAIL_ADDRESS>
& Yi Wang
Shanghai AI Laboratory, China
<EMAIL_ADDRESS>
& Zhipeng Zhou
Chinese Academay of Sciences, Beijing, China
<EMAIL_ADDRESS>
& Duoqian Miao
Tongji University, China
<EMAIL_ADDRESS>
& Yu Qiao
Shanghai AI Laboratory, China
<EMAIL_ADDRESS>
& Limin Wang
Nanjing University, China
<EMAIL_ADDRESS>
& Cairong Zhao ✉
Tongji University, China
<EMAIL_ADDRESS>

###### Abstract

Flattening is essential in computer vision by converting multi-dimensional
feature maps or images into one-dimensional vectors. However, existing
flattening approaches neglect the preservation of local smoothness, which can
impact the representational learning capacity of vision models. In this paper,
we propose Hilbert curve flattening as an innovative method to preserve
locality in flattened matrices. We compare it with the commonly used Zigzag
operation and demonstrate that Hilbert curve flattening can better retain the
spatial relationships and local smoothness of the original grid structure,
while maintaining robustness against the input scale variance. And, we
introduce the Localformer, a vision transformer architecture that incorporates
Hilbert token sampling with a token aggregator to enhance its locality bias.
Extensive experiments on image classification and semantic segmentation tasks
demonstrate that the Localformer outperforms baseline models consistently. We
also show it brings consistent performance boosts for other popular
architectures (e.g. MLP-Mixer).

##  1 Introduction

Flattening is a crucial operation in computer vision, converting a multi-
dimensional feature map or image into a one-dimensional vector. In deep
learning, when needing to extract semantics from the learned feature maps or
tokens, we flatten these high-dimensional inputs into a vector of high-level
representation, neglecting local smoothness.

Though local smoothness descriptions in flattened results are usually
oblivious, the specific flattening approaches still contain some of them. As
an example, most feature points in zigzag flattened vectors are spatially
neighboring (1 pixel away) in their original 2-D formation, except for turning
points in zigzag scanning. With the size increase of the feature map for
flattening, these 1-D distances to the neighboring points of these outcast
ones in vector format would be more distorted. However, in visual models, the
local smoothness (aka locality bias, i.e., adjacent pixels are more likely to
belong to the same object than distant pixels (Liu et al., 2021a)) of shallow
texture features frequently exerts an impact on the model’s capacity for
representational learning. For instance, Hassani et al. (2022) employs the
neighborhood attention technique to introduce locality bias into the vision
transformer for enhancing classification performance. Intuitively, we suppose
the fancy equivariant image flattening designs will bring non-trivial
performance gains at a negligible cost.

From this perspective, we are examining the potential for a new method to
flatten matrices that may surpass the existing Zigzag operation in preserving
locality. Ideally, this innovative method would push the boundaries of or even
reach the theoretical maximum for locality preservation capabilities. If such
an advanced flattening process could retain more of the original grid
structure’s locality, it might substantially improve existing ViT-like
architectures. Moreover, this method might lead to a significant shift in
research approaches by transforming input signals of any dimension into a 1-D
vector for processing. This highlights the critical role of 1-D operators,
such as pointwise convolution and depthwise separable 1-D convolution.

Figure 1:  Token similarity of ViT-L and our Localformer-L trained on
ImageNet-1K. Specifically, we calculate the similarity (i.e., cosine distance)
between a picked token and the others in one layer and plot them as heat maps,
in which the $x$ and $y$ axes index the tokens of the networks. We sampled a
total of $32$ examples without replacement, repeating this process $10$ times
and calculating the average. We also tried to change the sample size $m$, but
it had no notable effect on the results. For clarity, we focus on specific
layers for demonstration, including the patch embedding layer, Block1,
Block11, and the final Block23. And, we mark consecutive and similar blocks of
tokens learned by the network using colored rectangular boxes.

Inspired by geometric $Fractal$ theories (Gotsman and Lindenbaum, 1996), we
propose Hilbert curve flattening as an alternative for sequence ordering in
computer vision. Our investigation provides a detailed analysis of its
theoretical guarantees for locality preservation and derives its scale
robustness accordingly in computer vision compared to other flattening curves.
Further, we validate the practical effectiveness of HF by finding its
applications as Hilbert token sampling, beyond its theoretical merits. We also
propose a new vision transformer, as it introduces Hilbert token sampling with
a token aggregator into the vanilla ViT to enhance its locality bias, we name
it Localformer. By inspecting the proposed Localformer, as illustrated in Fig.
1, we reveal a surprising connection between the patch flattening operation
and transformer-like architecture representation learning as well as the
recognition performance in image classification. Our contributions can be
summarized as follows:

  * •

Through theoretical analysis and experimental support, we attempt to give one
alternative flattening approach named Hilbert curve flattening in the current
vision community. It can preserve much more local smoothness than the other
SFCs and show robustness in dimension scaling.

  * •

Our proposed Localformer amalgamates the benefits of Hilbert curve flattening
with the vanilla vision transformer, resulting in several merits for
representation learning. We conducted extensive experiments on image
classification and semantic segmentation tasks, the results demonstrate that
Localformer outperforms the baseline consistently.

##  2 Related Works

In this section, we first overview the applications of Hilbert curves
respectively according to their motivations. Then, we provide a review of the
development of the ViT and MLP-Only architectures, which serve as the
backbones of our experimental section. Specifically, this work aims at the
length extrapolation challenge. We also introduce the definition and some
research works on it at the end.

###  2.1 Hilbert Curves

Such prominent works in Mathematics as (Jagadish, 1990; Gotsman and
Lindenbaum, 1996; Moon et al., 2001) have evidenced that the locality between
objects in multi-dimensional space is preserved in linear space. Recent works
consisting of (Bappy et al., 2019; Zhang et al., 2021a) introduce the Hilbert
curves into a specific computer vision (CV) task aim of obtaining better
performance. By contrast, in this paper, we present the first theoretical
analysis and empirical evidence to support the use of HF rather than the
default ZF method when performing matrix unfolding operations for visual
tasks. Specifically, Bappy et al. (2019) noted that the order of the image
patches has a significant impact on the performance of the detection of image
forgeries. Similarly, to extract better generalizable forgery detection,
(Zhang et al., 2021a) employ the Hilbert curves to flatten image patches
before feeding them into the Gated Recurrent Unit (GRU) network. And,
Tsinganos et al. (2019) employed the Hilbert curves to generate 2-D image
representations from 1-D surface electromyography (sEMG) signals for better
gesture recognition.

###  2.2 ViTs and MLPs

Vision Transformer (Dosovitskiy et al., 2020) inspires a new paradigm
architecture that differs from CNNs by utilizing patch embedding instead of
taking images directly as input. Swin Transformer (Liu et al., 2021b) proposes
shifted windows to solve larger variations of the input image caused by the
multi-scale and different resolutions. By contrast, Tolstikhin et al. (2021)
proposed a new architecture named MLP-Mixer that differs from CNNs and
Transformers by eliminating the need for convolution and self-attention, which
relies only on the repeated implementations of MLPs across the spatial or
feature channels. Those works all employed Zigzag flattening to expand 2-D
images or features into 1-D patch or token sequences. In this paper, we
explore the effects of different patch flattening methods on those model
structures, including locality bias, length extrapolation, representation
structure, and ultimate performance.

###  2.3 Length Extrapolation

The length extrapolation is a significant challenge for Transformer models in
natural language processing (NLP), leading to inconsistencies between training
and inference lengths (Press et al., 2021; Kiyono et al., 2021). This
challenge is also particularly relevant in visual tasks, where good length
extrapolation can naturally improve performance. The inconsistency may stem
from two factors: 1) the use of an untrained position embedding weight in
predictions, and 2) the number of tokens processed by the attention mechanism
at inference far exceeds the number at training. The vision transformer with
relative position encoding (Su et al., 2021; Chi et al., 2022) has cleverly
solved the above two problems and become a strong baseline model. Some
researches demonstrate that (Zhang et al., 2021b; Liu et al., 2021c) relative
positional encoding outperforms absolute positional encoding in the image
classification task, but recent work (Wu et al., 2021) claims that the
relative positional encoding can not work equally well as the absolute
positional encoding in dense prediction visual tasks (e.g., semantic
segmentation). By contrast, without the relative positional encoding, we aim
to enhance the length extrapolation capability of absolute position encoding
from a generic perspective. And, we are the first to introduce the properties
of SFC into the vanilla vision transformer to enhance its length
extrapolation.

Figure 2: Multi-scale transformation of dimensional space with Zigzag curve
and Hilbert curve flattening/folding, respectively. Specifically, suppose that
two points separated by $d_{L}\in(0^{+},1)$ are taken at random on the real
number axis in the interval $I=[0,1]$, which can always be taken if
$2^{n}\times 2^{n}$ ($n\in\\{3,4,5,6,7\\}$) points are equally spaced on the
number axis. By dividing the interval of the numerical axis by $2^{6}$ equal
parts and using different unfolding operations (ZF and HF), we find that the
distance $d_{L}$ between two points changes to $d_{Z}^{6}$ and $d_{H}^{6}$.
Similarly, if $2^{8}$ equal divisions are performed, the distance between the
two points again changes to $d_{Z}^{8}$ and $d_{H}^{8}$. The two points with
fixed distance $d_{L}$ on $[0,1]$ mapped to 2-D space under different types of
unfolding operations will have various distances.

##  3 Hilbert Flattening

The proposed Hilbert flattening is inspired by the Hilbert curve of space-
filling curves (SFC) from the geometric theory of Fractals (Sprecher and
Draghici, 2002), just like Zigzag one mimics how people read text from left to
right, row by row. Hilbert curves preserve the most locality of the input
features among all candidates when flattening such a multi-dimensional matrix
input into a 1-D vector. In this section, we first introduce the definition of
SFC and how it can be introduced into image unfolding operations. Next, we
analyze the properties of HF, in the comparison with existing unfolding
operations. With the property analysis of HF, we show how to apply it to
popular models in practical applications.

###  3.1 Preliminaries

##### Space-Filling Curves

A continuous curve is called space-filling curve if it can pass through every
point of a closed square (Peano, 1890). More precisely, as shown in Fig. 2, a
space-filling curve (Simmons, 1963) is a continuous mapping from a closed unit
interval $I=[0,1]$ to a closed unit square $[0,1]\times[0,1]$. The definitions
and known theorems used in this paper mainly come from Sagan (2012), please
refer to it for more details.

##### Matrix Unfolding

In computer vision, the matrix unfolding operation takes place when a tensor
undergoes a dimensional change. For example, as illustrated in Fig. 2, the
flattening of 2-dimensional grid data into 1-dimensional linear data is a
matrix unfolding operation. We can observe that it is precisely the inverse of
SFC operation. In this paper, three SFCs will be introduced, namely Hilbert
curves, Morton curves, and Zigzag curves. Each of the three SFCs corresponds
to a specific matrix flattening method: HF for Hilbert curves, MF for Morton
curves, and ZF for Zigzag curves. The Hilbert curves (Hilbert, 1935) is the
first generic geometric program that allows the construction of entire classes
of space-filling curves. The Morton curves (aka, Z-order (Lebesgue, 2003)) map
multidimensional data to one dimension while preserving the locality of the
data points in data structures. And, the Zigzag curve is the default operation
for flattening tensors in deep learning (i.e., torch.flatten()). Please refer
to the Appendix for detailed definitions of the aforementioned SFCs and
corresponding matrix flattening methods.

###  3.2 Properties

We analyzed locality preserving and scale robustness about the three
aforementioned unfolding methods using toy examples, respectively. We find
that the HF not only demonstrates effective locality-preserving capability but
also retains this property when dealing with feature maps of neural networks,
as visualized in Section 4.4. That is especially pertinent considering the
essential role that locality biases (Sun et al., 2022) play within visual
domains. Specifically, by preserving the 2-D geometric structure in a 1-D
format, we believe the HF can enhance ViT-like architectures in visual
discriminations, as evidenced in Section 4.1.

####  3.2.1 Locality Preserving

Theoretically, we demonstrate that HF maximizes the preservation of 2-D
topological structure among the other flattening methods, notably surpassing
the orthodox Zigzag method. This holds true whether flattening 2-D matrixes
into 1-D vectors or folding 1-D vectors into 2-D matrixes, confirming symmetry
in dimension reduction or expansion.

##### Flattening 2-D to 1-D

Flattening techniques can transform high-dimensional data such as matrices or
tensors into flattened representations that can be processed by neural
networks, highlighting its significance in deep learning. Indeed, the
transformation process inevitably disrupts the original grid structure. For
instance, when applying the ZF operation, only the neighboring pixel points
within each row maintain their adjacency, while the structural coherence
across rows is lost. To facilitate the learning of locality representations in
images, it is essential to ensure the local smoothness of the input data
matrix. This concept often referred to as locality bias, is a widely adopted
assumption in computer vision. And the locality bias assumes that nearby
pixels or regions in an image exhibit similar characteristics or share common
patterns. By retaining the spatial relationships between pixels or regions,
the model can better capture local dependencies and patterns, leading to
improved performance in various computer vision tasks (Sun et al., 2022;
Nguyen et al., 2020).

Figure 3:  Suppose we compute the DeGrid at each point on a $8\times 8$ grid
structure data with $K=2$. The results are expressed as a heat map, in which
the brightness of the pixels indicates the grid structure info preservation.
The closer the pixels are to black, the better. Table 1:  The percentage of
grid structure preservation with the given DeGrid threshold $\epsilon$, where
we set $K=2$. Indexing pixel points within the same 2-D neighborhood, the
larger the percentage indicates the better structure preservation.

$\epsilon$ | 0.043 | 0.045 | 0.047 | 0.053 | 0.055 | 0.057 | 0.059 | 0.069 | 0.070 | 0.071 | 0.077 | 0.086 | 0.087 | 0.120
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
HF | 60.16% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00% | 100.00%
MF | 0.39% | 0.39% | 62.89% | 62.89% | 62.89% | 69.14% | 69.14% | 81.64% | 81.64% | 87.89% | 91.02% | 91.02% | 92.58% | 92.58%
ZF | 0.00% | 0.20% | 0.20% | 87.89% | 87.89% | 87.89% | 87.89% | 87.89% | 87.89% | 87.89% | 87.89% | 87.89% | 87.89% | 87.89%

Now we explore how much the flattened 1-D sequence can preserve the original
2-D structure info. As depicted in Fig. 3, the process begins by selecting a
neighborhood with a radius of $K=2$ from the flattened 1-D data. Within this
neighborhood, a central node $p$ is identified, i.e., the points circled in
cyan. The degree of deformation of this neighborhood is determined by
calculating the sum of the squares of the distances between each pixel (i.e.,
the points circled in green) and the central node $p$ over the 2-D grid data.
This measure provides insight into how much the neighborhood has been altered
or transformed. To describe the degree of destruction of the grid structure
within this neighborhood, the ratio of the degree of deformation to the sum of
the elements in the neighborhood is computed, we call it the Deformation Value
of 2-D Grid Structure (DeGrid, see the Appendix for details). A higher DeGrid
indicates a lower degree of retention of the grid structure, while a lower
ratio suggests a less significant deformation or disruption of the original
grid structure.

Table 2: Theoretical derivation of the dilation factor and limits for the
three space-filling curves.

Flattening Methods | Dilation Factor Lower Bound | Limits
---|---|---
Zigzag curves | $4^{n}-2^{n+1}+2$ | $+\infty$
Morton curves | $2^{n}-2^{-n}$ | $+\infty$
Hilbert curves |  $6$ (refer to Bauman (2006a)) | $6$

Lastly, as presented in Table 1, we establish a threshold for the DeGrid.
Nodes with a DeGrid below this threshold $\epsilon$ are deemed to have a
manageable deformation. The grid structure preservation within the DeGrid
threshold is determined by the ratio between the total number of these points
and the total number of nodes in the flattened 2-D grid data. Indeed, as
illustrated in Fig. 3, it is evident that when the $\epsilon$ exceeds $0.045$,
the grid structure preservation of the HF can surpass that of other SFCs
entirely.

##### Folding 1-D to 2-D

When performing a folding operation on a 1-D vector, it leads to an expansion
of the spatial distance between the original data points, i.e., loss of local-
range correlation info. As depicted in Fig. 2, when transforming 1-D sequence
data into a 2-D grid using unfolding methods, the distance between two points
(i.e., $d_{L}$) is expanded, resulting in an increased spatial distance of
$d_{Z}$ and $d_{H}$, respectively. We want the process to increase $d_{L}$ by
as small a factor (i.e., $d_{\cal F}/{d_{L}}$, where ${\cal F}$ denotes a
matrix flattening method) as possible to preserve the locality info. Similar
to Estevez-Rams et al. (2015), we formulate this dilation factor (DF) to
describe the preservation of the 1-D local-range correlation information.

For elaboration, let’s consider folding the interval $I=[0,1]$ into a
$2^{n}\times 2^{n}$ grid data. As depicted in Fig. 2, when using the ZF
method, the original distance between two points is indefinitely and
continuously enlarged as the dimension of the 2-D grid increases. Instead,
that distance converges to a definite value with the HF method. In Table 2, we
also provide the dilation factor expressions for the above three flattening
methods, along with their corresponding limit values. We find that as $n$
tends to positive infinity, only the limit of HF is a constant (i.e., the
$\mathbb{C}$ is equal to 6 (Bauman, 2006a)) for all three expansion methods
(turn to the Appendix for derivations).

Figure 4:  A toy dataset owning 18 synthetic images to measure scale
robustness empirically.

####  3.2.2 Scale Robustness of Folding

The scale robustness of folding refers to the extent to which the relationship
between two chosen points changes in different folding scales. Generally, we
suppose HF is robust to the folding scale while ZF is not. Referring to Fig.
2, assume that the interval $I$ is folded into $2^{n}\times 2^{n}$ grid data
again. As $n$ increases, if the distance $d_{\cal F}^{2n}$ between the two
selected points converges to a nonzero constant value (i.e.,
$\lim\limits_{n\rightarrow\infty}{d_{\cal F}^{2n}}\in\mathbb{C}^{+}$), which
makes the ratio (i.e., $\lim\limits_{n\rightarrow\infty}{d_{\cal
F}^{2n}}/{d_{\cal F}^{2(n+1)}}$) between the distances after multiscale
folding is $1$, we suppose this folding process is robust to scale.
Specifically, when performing a multiscale folding operation using the ZF, the
ratio between the two distances becomes indeterminate, i.e.,
$\lim\limits_{n\rightarrow\infty}{d_{Z}^{2n}}/{d_{Z}^{2(n+1)}}\neq
1,s.t.,\lim\limits_{n\rightarrow\infty}{d_{Z}^{2n}}=\infty$. In contrast, when
applying the same operation using the HF, that ratio tends to become
convergent, i.e.,
$\lim\limits_{n\rightarrow\infty}{d_{H}^{2n}}/{d_{H}^{2(n+1)}}=1,s.t.,\lim\limits_{n\rightarrow\infty}{d_{H}^{2n}}=6$.
See the Appendix for the theoretical derivations and definitions.

Table 3:  The DTW distance for different flattening methods on the proposed
toy dataset (consisting of multiple scale object and image resolutions), Lower
is better. As presented in Fig. 4, “L32" means Large scale object with a
resolution of $32\times 32$ and “S128" means Small scale one with a resolution
of $128\times 128$.

Scale | L32 vs S32 | L32 vs L64 | L64 vs S64 | L64 vs L128 | L128 vs S128 | L32 vs S128
---|---|---|---|---|---|---
Methods | HF | MF | ZF | HF | MF | ZF | HF | MF | ZF | HF | MF | ZF | HF | MF | ZF | HF | MF | ZF
Circle | 5.19 | 5.71 | 8.61 | 4.13 | 4.97 | 14.32 | 6.14 | 7.86 | 16.28 | 6.74 | 7.29 | 28.71 | 9.13 | 10.20 | 33.31 | 3.95 | 4.38 | 18.52
Square | 3.40 | 4.06 | 8.14 | 5.42 | 5.49 | 17.16 | 6.60 | 7.26 | 15.53 | 7.39 | 7.61 | 35.47 | 10.58 | 12.23 | 31.03 | 8.67 | 7.61 | 29.67
Triangle | 4.61 | 4.59 | 9.60 | 3.63 | 4.27 | 16.03 | 6.93 | 6.99 | 18.83 | 6.06 | 6.64 | 31.55 | 7.99 | 9.37 | 38.07 | 4.30 | 4.76 | 10.28

We show how ZF, MF, and HF respond to flattening 2-D toy examples in scale
robustness. A toy dataset comprising three common shapes (circles, squares,
and triangles) with two scales (small and large) is constructed, as
illustrated in Fig. 4. Further, to compute the correlation between different
1-D folding vectors, dynamic time warping (DTW) distance (Berndt and Clifford,
1994; Fang et al., 2020) is employed as it allows for the comparison and
alignment of sequences with variable lengths. The computed DTW distances for
various sequence pairs are presented in Table 3, providing insights into the
pairwise dissimilarity of the flattened images. When the resolution of image
pairs is increased, the DTW distance between large and small targets also
increases. This observation indicates that higher resolution amplifies the
differences between multi-scale targets within an image. It is worth noting
that the variation in HF is relatively small when comparing the DTW distance
of different strategies. This suggests that the HF is more robust to
resolution changes and preserves the structural consistency of the flattened
sequences.

###  3.3 Applications

We apply HF to vision transformers and MLP-only models, constructing
Localformer and MLP-FPN. As depicted in Fig. 5, the HF can be readily applied
in various deep-learning operations whenever there is a need for matrix
resampling or alignment, e.g., it was employed in the patch embedding module
of ViT.

Figure 5:  The illustration of our Localformer. It consists of two critical
modules, i.e., the Hilbert token sampling (HTS) and a token aggregator (TA).
Notably, the HTS would not move the semantically related patches away from
each other, e.g., the head of the cat remained clustered together after
slicing,

##### Localformer

We propose a vision backbone named Locality-Preserving Vision Transformer
(Localformer) by incorporating the Hilbert token sampling (HTS) module, in
which the HTS replaces the default Zigzag flattening in the token sampling
processing. Same as vanilla ViT, Localformer applies a universal flat
structure that makes feature maps at a single scale. Although the flat
structure is not well adapted to the down-stream detection task, it does not
under-perform in the pre-train classification task and is more efficient
compared to the progressive pyramid structure (e.g., Liu et al. (2021c); Fan
et al. (2021)). And the ViT is still the backbone of choice for the
fundamental models (e.g., Radford et al. (2021)). As illustrated in Fig. 5, we
take our HTS module into the shallower patch embedding block, and adopt the
simple yet effective token aggregator before the self-attention blocks, while
the others remain the same. We also give multiple-scale architectures similar
to ViT models (e.g., Localformer-B or Localformer-L).

Specifically, after our HTS processing the similar patches are close in the
sampled 1-D token sequence. We introduce a generalized token aggregator to
capture the relationship between neighboring patches, which allows the network
to exploit the local smoothness property and enhance its performance. For one
input token sequence ${\cal X}\in\mathbb{R}^{n\times d}$, where $n,d$ means
the number of patches and the embedded dimensions, respectively. We employ a
depthwise separable convolution operation on ${\cal X}$ along the dimension
$n$ and then put it into the next self-attention blocks to aggregate the local
representations. Generally, we set the kernel size and step size of the
convolution to be equal to $3$ and $1$ respectively, and then go through a
layer normalization after the operation.

Figure 6:  The illustration of the proposed MLP-FPN.

##### MLP-FPN

Intuitively, we believe that the scale robustness property of HTS can enhance
the multi-scale representation of the network containing a feature pyramid
network (FPN) branch, resulting in improved performance gains. To this end, we
devised a network architecture solely based on the MLP module, while
incorporating an FPN branching structure, namely MLP-FPN as presented in Fig.
6. The FPN was originally introduced to address the challenge of multi-scale
variation in object detection (Lin et al., 2017; Min et al., 2022). It
accomplishes this by effectively integrating features that possess strong
semantic information at lower resolutions and features with abundant spatial
details at higher resolutions. Inspired by this, The residual branch of our
MLP-FPN is formed by stacking down-sampling pyramid modules, which include our
HTS algorithm and 1-D convolutional neural networks (Conv1-D). The MLP
consisting of Conv1-D is then assembled into the backbone network.

##  4 Experiments

This section first presents image classification and semantic segmentation
experiments, in which the results support the observation that different
unfolding methods do affect the performance of the model. And, we conduct
ablation experiments and internal inspections to analyze the potential factors
contributing to the observed performance gain. These analyses provide further
evidence that the HF serves as a reliable matrix unfolding method in computer
vision.

Table 4:  Recognition accuracy of different models on ImageNet-1K with
multiple settings. The ${\dagger}$ indicates the best results from our own
replication of (Dosovitskiy et al., 2020). “Ave. Pool." means all tokens are
pooled on average as the output of the classifier.

Models | Res. | Ave. | #Param | Top-1 | Top-5
---|---|---|---|---|---
Pool. | (M) | (%) | (%)
ViT-S/16 (Dosovitskiy et al., 2020) | 2242 | $\times$ | 22.1 | 78.10 | -
ViT-B/16 (Dosovitskiy et al., 2020) | 2242 | $\times$ | 86 | 79.80 | -
ViT-L/16 (Dosovitskiy et al., 2020) | 2242 | $\times$ | 304 | 81.10 | -
DeiT-S (Touvron et al., 2021) | 2242 | $\times$ | 22.1 | 79.90 | 95.00
DeiT-B (Touvron et al., 2021) | 2242 | $\times$ | 86 | 81.80 | 95.60
DeiT-B (Touvron et al., 2021) | 3842 | $\times$ | 87 | 82.90 | 96.20
T2T-ViT-14 (Yuan et al., 2021) | 2242 | $\times$ | 21.5 | 80.70 | -
Swin-T (Liu et al., 2021c) | 2242 | $\checkmark$ | 28.3 | 81.30 | -
Swin-S3-T (Chen et al., 2021) | 2242 | $\checkmark$ | 28.1 | 82.10 | 95.80
ViT-T/16† | 2242 | $\times$ | 5.7 | 70.38 | 88.75
Localformer-T/16 | 2242 | $\times$ | 5.7 | 70.91 | 89.22
ViT-S/14† | 2242 | $\checkmark$ | 22 | 80.10 | 95.19
Localformer-S/14 | 2242 | $\checkmark$ | 22 | 80.41 | 95.33
ViT-B/16† | 2242 | $\times$ | 86 | 81.19 | 95.40
Localformer-B/16 | 2242 | $\times$ | 86 | 81.78 | 95.63
ViT-B/16† | 2242 | $\checkmark$ | 86 | 82.02 | 95.78
Localformer-B/16 | 2242 | $\checkmark$ | 86 | 82.47 | 96.00
ViT-L/14† | 2242 | $\checkmark$ | 304 | 82.98 | 96.17
Localformer-L/14 | 2242 | $\checkmark$ | 304 | 83.43 | 96.44

##### Experimental Setup

We utilized the common settings to compare the performance for fairness.
Notably, the settings including software (i.e., the virtual environment of
Python 3.7 and Torch 1.7.1) and hardware (i.e., 4 NVIDIA A100 GPUs) are
strictly consistent. More results can be found in the Appendix.

###  4.1 Image Classification

We utilized the widely recognized codebase111PyTorch Image Models:
https://github.com/huggingface/pytorch-image-models.git called timm for our
experiments, and the current baseline we established presents a significant
challenge in comparison to the original ViT (Dosovitskiy et al., 2020). The
models are trained 300 epochs with a fixed input resolution (i.e., $224\times
224$) on the ImageNet-1K dataset (Deng et al., 2009) from scratch. We follow
the same settings in DeiT (Touvron et al., 2021) by default, which consists of
data augmentation, comparison protocols, and regularization. Specifically, we
employ the “AdamW" optimizer and the cosine learning rate schedule, and set
the drop path rate as 0.1/0.35/0.45 for our small/base/large models, while the
first 10 epochs are applied for linear warm-up. The weight decay, learning
rate, and batch size are set to 0.05, 1e-3, and 256 respectively.

We performed experiments at multiple scales of the model, and the results are
summarized in Table 4. One can see that the Localformer achieves performance
improvements over the ViT baseline, with accuracy gains of 0.53% on ViT-T,
0.31% on ViT-S, 0.59% on ViT-B, and 0.45% on ViT-L. Those gains are clear and
consistent regardless of model size and whether or not average pooling (AP) is
used. Intuitively, those results supported our claim in Section 3.2.1, i.e.,
preserving the original local smoothness when flattening the image patches
benefits performance. It is worth noting that our Localformer would bring more
gains if the network classifier does not employ the average pooling layer
(i.e., from 0.45% to 0.59% on ViT-B). Intuitively, we believe that the network
utilizing AP can leverage the local information learned by each token,
mitigating the limitation of shallow networks in aggregating locality info.
This observation also suggests that our HTS operates independently from the
average pooling.

Table 5:  Semantic segmentation with Upernet 80K (Xiao et al., 2018) framework
on ADE20K (Zhou et al., 2017). †denotes the test input size is $512\times
2048$ and the model was trained with Upernet 160K iterations. ∗ denotes
without adding deconvolution.

Backbone | Tune | #Param. | FLOPs | mIoU
---|---|---|---|---
Res. | (M) | (G) | (%)
ResNet-50 (Chen et al., 2021) | 5122 | 67 | 951 | 42.05†
DeiT-B∗ (Chen et al., 2021) | 5122 | 121 | 2772 | 44.09†
Swin-S3-T (Chen et al., 2021) | 5122 | 60 | 954 | 44.87†
Swin-T (Liu et al., 2021c) | 5122 | 60 | 945 | 44.50†
Focal-T (Yang et al., 2021) | 5122 | 62 | 998 | 45.80†
StructToken-CSE (Lin et al., 2023) | 5122 | 30 | - | 45.86†
Twins-S (Chu et al., 2021) | 5122 | 54 | 901 | 46.20†
ViT-S/14-336 (Dosovitskiy et al., 2020) | 5042 | 58 | 326 | 44.05
Localformer-S/14-336 | 5042 | 58 | 326 | 44.76
ViT-B/16-384 (Dosovitskiy et al., 2020) | 5122 | 144 | 395 | 45.48
Localformer-B/16-384 | 5122 | 144 | 395 | 46.34

###  4.2 Semantic Segmentation

We adopt the popular Upernet framework (based on mmseg codebase (Contributors,
2020)) to conduct the semantic segmentation experiments on the ADE20K dataset
(Zhou et al., 2017). We mainly follow the settings of the Swin Transformer
(Liu et al., 2021c) and train the models for 80k iterations. The drop path
rates are set to 0.15/0.35 for small/base variants with Upernet respectively.
The backbone networks were pre-trained on ImageNet-1k, in which the number of
input tokens was set to $24\times 24$ and it increased to $32\times 32$ when
fine-tuned on ADE20K. The variable number of tokens handled by the attention
mechanism presents a challenge during model training. The results and example
demonstration are reported in Table 5 and Fig. 7, respectively. Compared with
the ViT baseline, our Localformer yields stable gains (e.g., 0.71% mIoU on
ViT-S and 0.86% mIoU on ViT-B). We hypothesize that the HTS can enhance the
Localformer’s ability to handle variable token lengths, improving its length
extrapolation.

Figure 7: Qualitative results of semantic segmentation on ADE20K (Zhou et al.,
2017) Table 6:  The experimental results regarding the length extrapolation of
image classification models on the ImageNet-1K.

Models | Train | Tune | Val. | Tune | W/o Tune
---|---|---|---|---|---
Res. | Res. | Top-1 | Top-1 | Top-1
ViT-S/14 | $224^{2}$ | $336^{2}$ | 80.10 | 81.99 | 69.89
Localformer-S/14 | $224^{2}$ | $336^{2}$ | 80.41 | 82.91 | 78.61
ViT-B/16 | $224^{2}$ | $384^{2}$ | 82.02 | 83.37 | 66.03
Localformer-B/16 | $224^{2}$ | $384^{2}$ | 82.47 | 83.70 | 69.69

###  4.3 Ablation Study

We conducted a series of ablation experiments to evaluate the generalizability
of HTS. These experiments included validating the effectiveness of each
component of Localformer, assessing its length extrapolation, and exploring
the applicability of HTS on MLP-Mixer (Tolstikhin et al., 2021), the proposed
FPN-MLP, and Swin transformer (Liu et al., 2021c) networks.

##### Length Extrapolation

To verify our hypothesis that HTS can enhance length extrapolation in ViT, we
conducted additional experiments on ImageNet-1K. The only difference from the
experimental setup in Section 4.1 is that we intentionally set the number of
input tokens during training (e.g., $16\times 16$) to be different from the
number of tokens used for fine-tuning (e.g., $24\times 24$). We report three
different inference results, including 1) testing with constant token lengths
without tuning, 2) changing the token length, fine-tuning it first then
testing it, and 3) changing the token length but testing it directly.
Specifically, during the fine-tuning phase, the weight decay, learning rate,
batch size, warm-up epoch, and total epoch are set to $0.1,1e^{-5},256,10$,
and $30$ respectively. The results are reported in Table 6, we can see that
the Localformer consistently maintained a leading position. As an example,
when varying the token length, our Localformer demonstrates absolute gains of
0.92% and 8.72% on ViT-S with and without tuning, respectively. Also, we find
that the boost on ViT-S to be better than on ViT-B. Intuitively, we attribute
this disparity to the difference in model size.

##### Validity of Different Components

Similar to the experimental setup in Section 4.1, we performed additional
experiments on ImageNet-1K and CIFAR-10 (Krizhevsky et al., 2014) datasets,
affirming the validity of the Localformer structure design. From the results
(Table 7), we see that both HTS and TA could achieve non-negligible gains over
the ViT baseline, e.g., HTS gets 0.17% on ImageNet-1K and 2.47% on CIFAR-10,
TA gets 0.12% on ImageNet-1K and 1.40% on CIFAR-10. Also, we find that the
combination of HTS and TA modules can enhance the classification performance.
Notably, the best CIFAR-10 accuracy score is achieved only using HTS. We
conjecture that training a Transformer model from scratch on the tiny dataset
is prone to the local optimization trap.

Table 7:  Validation of the effectiveness of HTS and TA on image
classification models.

Models | Dataset | HTS | TA | Top-1% | Top-5%
---|---|---|---|---|---
Localformer-B/16 | ImageNet-1K | $\times$ | $\times$ | 82.02 | 95.78
$\checkmark$ | $\times$ | 82.19 | 95.82
$\times$ | $\checkmark$ | 82.14 | 95.81
$\checkmark$ | $\checkmark$ | 82.47 | 96.00
Localformer-T/2 | CIFAR-10 | $\times$ | $\times$ | 83.85 | 99.00
$\times$ | $\checkmark$ | 85.25 | 99.08
$\checkmark$ | $\times$ | 86.32 | 99.15
$\checkmark$ | $\checkmark$ | 85.71 | 99.10

Table 8:  Image classification experiments with MLP-only and local self-
attention architectures

Models | Dataset | HTS | Top-1% | Top-5%
---|---|---|---|---
MLP-Mixer-B/4 (Tolstikhin et al., 2021) | CIFAR-10 | $\times$ | 80.48 | 98.32
MLP-Mixer-B/4 (Tolstikhin et al., 2021) | CIFAR-10 | $\checkmark$ | 81.68 | 98.57
MLP-Mixer-B/8 (Tolstikhin et al., 2021) | CIFAR-10 | $\times$ | 83.58 | 98.71
MLP-Mixer-B/8 (Tolstikhin et al., 2021) | CIFAR-10 | $\checkmark$ | 84.52 | 98.83
FPN-MLP | CIFAR-10 | $\times$ | 81.42 | 99.18
FPN-MLP | CIFAR-10 | $\checkmark$ | 85.71 | 99.58
Swin-S3-T (Chen et al., 2021) | ImageNet-1K | $\times$ | 82.08 | 95.63
Swin-S3-T (Chen et al., 2021) | ImageNet-1K | $\checkmark$ | 82.34 | 95.85

##### Validation of HTS on MLP-only Architecture

MLP-Mixer (Tolstikhin et al., 2021) is a simpler all-MLP architecture than
ViT. And, it also slices the images and then performs the patch embedding
operations. we conducted additional experiments on CIFAR-10 with the common
protocols and the data augmentation (Lee et al., 2015) to verify whether the
HTS is beneficial to the MLP-only networks, the experimental setup was
described above. These experiments involved the validation of the proposed
FPN-MLP network, supporting the hypothesis that HTS can enhance the multi-
scale representation of the networks. The results are presented in Table 8
(above), we see that the MLP-Mixer with the HTS achieves clear gaps over the
baseline (e.g., 1.2% on MLP-Mixer-B/4). We also find the FPN-MLP using the HTS
can outperform the baseline by an obvious margin (i.e., 4.29% earnings).

##### Validation of HTS on Local Window Self-attention Architecture

As discussed earlier, HTS has the potential to enhance the locality info
aggregation of the ViT’s shallow layers. But, when it comes to networks with a
local self-attention structure, the gains from incorporating HTS may vary. To
this end, We provide ablation experiments with the Swin transformer (i.e., a
pyramid architecture using local self-attention) on ImageNet-1K to verify this
claim, the experimental setup is also similar to Section 4.1. The results are
reported in Table 8 (below), One can see that HTS also brings gains to the
advanced local-window-based architecture.

###  4.4 Inspecting Localformer

Localformer is not a state-of-the-art visual network architecture. In
particular, it struggles with incorporating local info at lower layers and
good length extrapolation. To better understand how Localformer learns
representations from images, we analyzed its internal representation
structures. That may provide insights into the interpretability of
Localformer’s internal representations and shed light on the underlying
mechanisms.

##### Token Pattern

We have discussed in Section 3.2.1 that the HTS exhibits superior preservation
of 2-D topological structure compared to other SFCs. Intuitively, the capacity
of HTS to capture local patterns has a profound effect on the learning of
representations in ViT. Aim for this, we visualized the token pattern of the
ViT and our Localformer networks by calculating the token similarity. As
presented in Fig. 1, we can see that the token pattern of ViT (top) and our
Localformer (bottom) present significant differences, in which the Localformer
has a relatively uniform pattern (like a self-similarity Sierpiński gasket
(Ida and Sambonsugi, 1998)) throughout the model, while the ViT suggests a
much lower similarity between shallower and deeper layers. We also find that
the Localformer shows the rectangular block structure with the locality in
patch embedding and the shallow layers. These phenomena reveal a surprising
connection between token patterns and the flattening methods. Intuitively,
this means that our Localformer can capture more local patterns between
tokens, while ViT can not.

##### Representation Structure

Through the analysis above, we hypothesize that our Localfomrer can enhance
the aggregation of local information at lower layers of ViT. This improvement
makes the representation structure of its shallow network more similar to that
of a CNN, and leading to a more uniform representation and performance gains.
To this end, we employ representational similarity and centered kernel
alignment (CKA) metric to study the layer representations, in which the CKA
could compare the representations of different neural networks in a meaningful
way. This allows us to make quantitative comparisons within and across
networks, and the visualization and analysis are reported in Fig. 8.

Figure 8:  Representation Similarity and CKA metric of ViT, our Localformer,
and CNN models (i.e., ResNet and Wide-ResNet (Zagoruyko and Komodakis, 2016))
architectures trained on ImageNet-1K. We follow (Nguyen et al., 2020; Hao et
al., 2021) to calculate the CKA and exhibit them as heat maps, in which the x
and y axes index the layers of the model. Similar to settings of Token
Pattern, we sampled a total of $32$ examples too, repeating this process $10$
times and calculating the average.

As can be seen from Fig. 8 (a)$-$(d), there are significant differences
between the representational structures of ViTs and CNNs. Specifically, the
overall representation of ViTs is highly similar, while there is a disconnect
between the shallow and deep layers of the CNNs model. We also find that the
Localformer has a more homogeneous layer similarity structure than ViT, i.e.,
it has a clearer grid-like pattern and a larger similarity between the shallow
and deep layers. From Fig. 8 (e)$-$(h), we see that the deepest ViT layers are
dissimilar to all ResNet layers. In contrast, not only the deepest one-sixth
of our Localformer layers are similar to all ResNet layers, but also the
overall representations of the two are more similar. We also see that not only
the shallower three-quarters of Localformer layers are similar to all Wide-
ResNet layers, but also the deepest one-sixth of Wide-ResNet layers are
similar to all Localformer layers. These phenomena support the hypothesis we
claimed above.

##  5 Conclusion

We investigate the potential of an alternative matrix unfolding approach
namely Hilbert token sampling, and demonstrate its remarkable properties that
can be flexibly applied to current popular visual network structures. We
further shed light on the inadequacies of utilizing ZF as the default matrix
unfolding operation in computer vision through a series of validations and
internal explorations of the proposed Localformer. Moreover, the internal
investigation offers valuable insights into the efficacy of our Localformer
and reveals the impact of different flattening methods on image understanding
capabilities. Future work will be aimed at how to use the SFCs to empower the
architecture design specifically for the Transformer-like networks. We will
also explore the performance of the Loacalformer on the self-supervised large-
scale pre-training tasks, e,g, DINO (Caron et al., 2021). The code will be
released soon.

## References

  * Liu et al. [2021a] Wenfeng Liu, Maoguo Gong, Zedong Tang, A Kai Qin, Kai Sheng, and Mingliang Xu.  Locality preserving dense graph convolutional networks with graph context-aware node representations.  _Neural Networks_ , 143:108–120, 2021a.
  * Hassani et al. [2022] Ali Hassani, Steven Walton, Jiachen Li, Shen Li, and Humphrey Shi.  Neighborhood attention transformer.  _arXiv preprint arXiv:2204.07143_ , 2022.
  * Gotsman and Lindenbaum [1996] Craig Gotsman and Michael Lindenbaum.  On the metric properties of discrete space-filling curves.  _IEEE Trans. Image Process._ , 5(5):794–797, 1996.
  * Jagadish [1990] H. V. Jagadish.  Linear clustering of objects with multiple atributes.  In _Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, USA_ , pages 332–342. ACM Press, 1990.
  * Moon et al. [2001] Bongki Moon, H. V. Jagadish, Christos Faloutsos, and Joel H. Saltz.  Analysis of the clustering properties of the hilbert space-filling curve.  _IEEE Trans. Knowl. Data Eng._ , 13(1):124–141, 2001.
  * Bappy et al. [2019] Jawadul H. Bappy, Cody Simons, Lakshmanan Nataraj, B. S. Manjunath, and Amit K. Roy-Chowdhury.  Hybrid LSTM and encoder-decoder architecture for detection of image forgeries.  _IEEE Trans. Image Process._ , 28(7):3286–3300, 2019.
  * Zhang et al. [2021a] Xueqi Zhang, Shuo Wang, Chenyu Liu, Min Zhang, Xiaohan Liu, and Haiyong Xie.  Thinking in patch: Towards generalizable forgery detection with patch transformation.  In _PRICAI 2021: Trends in Artificial Intelligence - 18th Pacific Rim International Conference on Artificial Intelligence_ , volume 13033, pages 337–352, 2021a.
  * Tsinganos et al. [2019] Panagiotis Tsinganos, Bruno Cornelis, Jan Cornelis, Bart Jansen, and Athanassios Skodras.  A hilbert curve based representation of semg signals for gesture recognition.  In _International Conference on Systems, Signals and Image Processing, IWSSIP 2019, Osijek, Croatia, June 5-7, 2019_ , pages 201–206. IEEE, 2019.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Liu et al. [2021b] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _ICCV_ , pages 10012–10022, 2021b.
  * Tolstikhin et al. [2021] Ilya O. Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy.  Mlp-mixer: An all-mlp architecture for vision.  _CoRR_ , abs/2105.01601, 2021.
  * Press et al. [2021] Ofir Press, Noah A Smith, and Mike Lewis.  Train short, test long: Attention with linear biases enables input length extrapolation.  _arXiv preprint arXiv:2108.12409_ , 2021.
  * Kiyono et al. [2021] Shun Kiyono, Sosuke Kobayashi, Jun Suzuki, and Kentaro Inui.  Shape: Shifted absolute position embedding for transformers.  _arXiv preprint arXiv:2109.05644_ , 2021.
  * Su et al. [2021] Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu.  Roformer: Enhanced transformer with rotary position embedding.  _arXiv preprint arXiv:2104.09864_ , 2021.
  * Chi et al. [2022] Ta-Chung Chi, Ting-Han Fan, Peter J Ramadge, and Alexander Rudnicky.  Kerple: Kernelized relative positional embedding for length extrapolation.  _Advances in Neural Information Processing Systems_ , 35:8386–8399, 2022.
  * Zhang et al. [2021b] Pengchuan Zhang, Xiyang Dai, Jianwei Yang, Bin Xiao, Lu Yuan, Lei Zhang, and Jianfeng Gao.  Multi-scale vision longformer: A new vision transformer for high-resolution image encoding.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 2998–3008, 2021b.
  * Liu et al. [2021c] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10012–10022, 2021c.
  * Wu et al. [2021] Kan Wu, Houwen Peng, Minghao Chen, Jianlong Fu, and Hongyang Chao.  Rethinking and improving relative position encoding for vision transformer.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10033–10041, 2021.
  * Sprecher and Draghici [2002] David A Sprecher and Sorin Draghici.  Space-filling curves and kolmogorov superposition-based neural networks.  _Neural Networks_ , 15(1):57–67, 2002.
  * Peano [1890] Giuseppe Peano.  Sur une courbe, qui remplit toute une aire plane.  _Mathematische Annalen_ , 36(1):157–160, 1890\.
  * Simmons [1963] George F Simmons.  _Introduction to topology and modern analysis_ , volume 44.  Tokyo, 1963.
  * Sagan [2012] Hans Sagan.  _Space-filling curves_.  Springer Science & Business Media, 2012.
  * Hilbert [1935] David Hilbert.  Über die stetige abbildung einer linie auf ein flächenstück.  In _Dritter Band: Analysis· Grundlagen der Mathematik· Physik Verschiedenes_ , pages 1–2. Springer, 1935\.
  * Lebesgue [2003] Henri Lebesgue.  _Leçons sur l’intégration et la recherche des fonctions primitives_ , volume 267.  American Mathematical Soc., 2003.
  * Sun et al. [2022] Weixuan Sun, Zhen Qin, Hui Deng, Jianyuan Wang, Yi Zhang, Kaihao Zhang, Nick Barnes, Stan Birchfield, Lingpeng Kong, and Yiran Zhong.  Vicinity vision transformer.  _arXiv preprint arXiv:2206.10552_ , 2022.
  * Nguyen et al. [2020] Thao Nguyen, Maithra Raghu, and Simon Kornblith.  Do wide and deep networks learn the same things? uncovering how neural network representations vary with width and depth.  _arXiv preprint arXiv:2010.15327_ , 2020.
  * Bauman [2006a] Konstantin Evgen’evich Bauman.  The dilation factor of the peano-hilbert curve.  _Mathematical Notes_ , 80:609–620, 2006a.
  * Estevez-Rams et al. [2015] E Estevez-Rams, C Perez-Demydenko, B Aragón Fernández, and R Lora-Serrano.  Visualizing long vectors of measurements by use of the hilbert curve.  _Computer Physics Communications_ , 197:118–127, 2015.
  * Berndt and Clifford [1994] Donald J Berndt and James Clifford.  Using dynamic time warping to find patterns in time series.  In _KDD workshop_ , volume 10, pages 359–370. Seattle, WA, USA:, 1994\.
  * Fang et al. [2020] Huihui Fang, Jianjun Zhu, Danni Ai, Yong Huang, Yurong Jiang, Hong Song, Yongtian Wang, and Jian Yang.  Greedy soft matching for vascular tracking of coronary angiographic image sequences.  _IEEE Transactions on Circuits and Systems for Video Technology_ , 30(5):1466–1480, 2020.  doi:10.1109/TCSVT.2019.2903883.
  * Fan et al. [2021] Haoqi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li, Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer.  Multiscale vision transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 6824–6835, 2021.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Lin et al. [2017] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2117–2125, 2017.
  * Min et al. [2022] Kyungseo Min, Gun-Hee Lee, and Seong-Whan Lee.  Attentional feature pyramid network for small object detection.  _Neural Networks_ , 155:439–450, 2022.
  * Touvron et al. [2021] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In _International Conference on Machine Learning_ , pages 10347–10357. PMLR, 2021.
  * Yuan et al. [2021] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan.  Tokens-to-token vit: Training vision transformers from scratch on imagenet.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 558–567, 2021.
  * Chen et al. [2021] Minghao Chen, Kan Wu, Bolin Ni, Houwen Peng, Bei Liu, Jianlong Fu, Hongyang Chao, and Haibin Ling.  Searching the search space of vision transformer.  _Advances in Neural Information Processing Systems_ , 34:8714–8726, 2021.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _CVPR_ , pages 248–255. Ieee, 2009.
  * Xiao et al. [2018] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun.  Unified perceptual parsing for scene understanding.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 418–434, 2018.
  * Zhou et al. [2017] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Scene parsing through ade20k dataset.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 633–641, 2017.
  * Yang et al. [2021] Jianwei Yang, Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao.  Focal self-attention for local-global interactions in vision transformers.  _arXiv preprint arXiv:2107.00641_ , 2021.
  * Lin et al. [2023] Fangjian Lin, Zhanhao Liang, Sitong Wu, Junjun He, Kai Chen, and Shengwei Tian.  Structtoken: Rethinking semantic segmentation with structural prior.  _IEEE Transactions on Circuits and Systems for Video Technology_ , 2023.
  * Chu et al. [2021] Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen.  Twins: Revisiting the design of spatial attention in vision transformers.  _Advances in Neural Information Processing Systems_ , 34:9355–9366, 2021.
  * Contributors [2020] MMSegmentation Contributors.  MMSegmentation: Openmmlab semantic segmentation toolbox and benchmark.  https://github.com/open-mmlab/mmsegmentation, 2020.
  * Krizhevsky et al. [2014] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  The cifar-10 dataset.  _online: http://www. cs. toronto. edu/kriz/cifar. html_ , 55(5), 2014.
  * Lee et al. [2015] Chen-Yu Lee, Saining Xie, Patrick Gallagher, Zhengyou Zhang, and Zhuowen Tu.  Deeply-supervised nets.  In _Artificial intelligence and statistics_ , pages 562–570. PMLR, 2015.
  * Ida and Sambonsugi [1998] Takashi Ida and Yoko Sambonsugi.  Image segmentation and contour detection using fractal coding.  _IEEE transactions on circuits and systems for video technology_ , 8(8):968–975, 1998.
  * Zagoruyko and Komodakis [2016] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  _arXiv preprint arXiv:1605.07146_ , 2016.
  * Hao et al. [2021] Fusheng Hao, Fengxiang He, Jun Cheng, and Dacheng Tao.  Global-local interplay in semantic alignment for few-shot learning.  _IEEE Transactions on Circuits and Systems for Video Technology_ , 32(7):4351–4363, 2021.
  * Caron et al. [2021] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 9650–9660, 2021.
  * Chen et al. [2022] Wanli Chen, Xinge Zhu, Guojin Chen, and Bei Yu.  Efficient point cloud analysis using hilbert curve.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part II_ , pages 730–747. Springer, 2022.
  * Bauman [2006b] Konstantin Bauman.  The dilation factor of the peano-hilbert curve.  _Mathematical Notes_ , 80:609–620, 11 2006b.
  * Bronstein et al. [2021] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković.  Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021.
  * Wang et al. [2022] Zhenyu Wang, Xuemei Xie, Qinghang Zhao, and Guangming Shi.  Filter clustering for compressing cnn model with better feature diversity.  _IEEE Transactions on Circuits and Systems for Video Technology_ , 2022.
  * Raghu et al. [2021] Maithra Raghu, Thomas Unterthiner, Simon Kornblith, Chiyuan Zhang, and Alexey Dosovitskiy.  Do vision transformers see like convolutional neural networks?  _Advances in Neural Information Processing Systems_ , 34:12116–12128, 2021.
  * Zhang et al. [2006] Jian Zhang, Sei-ichiro Kamata, and Yoshifumi Ueshige.  A pseudo-hilbert scan algorithm for arbitrarily-sized rectangle region.  In _International Workshop on Intelligent Computing in Pattern Analysis and Synthesis_ , pages 290–299. Springer, 2006.
  * Tautenhahn [2003] Lutz Tautenhahn.  Draw a space-filling curve of arbitrary size.  http://lutanho.net/pic2html/draw_sfc.html, 2003.

##  Appendix A Definition of Space-Filling Curves

We start this section with a Mathematical definition of the Space-Filling
curves, then give the expressions of the Hilbert curve, Zigzag curve, and
Morton curve among them.

##### SFCs

As described in Section 3.1 Space-Filling Curves, we give the formal
definition of the space-filling curves as follows::

###### Definition A.1

A mapping $f$: $I\rightarrow E^{n}(n\geq 2)$ is continuous and $f(I)$ has a
positive Peano–Jordan measure, then $f(I)$ is called a space-filling curve,
where $E^{n}$ denotes an n-dimensional Euclidean space.

##### Hilbert Curve

We assume $\mathcal{I}$ and $\mathcal{Q}$ as the interval $[0,1]$ and square
$[0,1]\times[0,1]$ respectively. The generating process of the Hilbert curve
is driven by the following:

$\displaystyle\mathcal{H}:t$
$\displaystyle\in[0,1]\mapsto\mathcal{H}(t)\in[0,1]\times[0,1],$ (1)
$\displaystyle t$ $\displaystyle=0.q_{1}q_{2}\cdots,0\leq q_{j}\leq 3,$
$\displaystyle\mathcal{H}(t)$ $\displaystyle=\left(\begin{aligned}
&\mathcal{R}e\\\
&\mathcal{I}m,\end{aligned}\right)\lim\limits_{n\rightarrow\infty}T_{q_{1}}T_{q_{2}}\cdots
T_{q_{n}}\mathcal{Q},$

where $t$ is represented in quaternary form. The definition of $\\{T_{i}|0\leq
i\leq 3\\}$ is defined as follows:

$\displaystyle T_{i}z=\frac{1}{2}H_{i}z+h_{i},0\leq i\leq 3,$ (2)
$\displaystyle\begin{aligned}
&H_{0}z=\bar{z}i,H_{1}z=z,H_{2}z=z,H_{3}z=-\bar{z}i,\\\
&h_{0}=0,h_{1}=\frac{i}{2},h_{2}=\frac{1+i}{2},h_{3}=\frac{2+i}{2},\end{aligned}$

where we consider complex numbers $z\in\mathbb{C}$ as $(Re(z),$
$Im(z))\in\mathcal{Q}$. The transformations $\\{T_{i}|0\leq i\leq 3\\}$
defined above correspond to different geometric deformations. Take
transformation $T_{0}$ as an example, we first shrink the original
$\mathcal{Q}$ towards the original point under the ratio $\frac{1}{2}$, then
reflect on the imaginary axis by multiplying with $-1$ and rotate the square
through $90^{\circ}$ by multiplying with imaginary number $i$.

During the generating process of the Hilbert curve, the sub-squares shrink
into points, which claims that $\mathcal{H}(t)$ is a point in
$\mathbb{R}^{2}$. We construct the $n$-th approximation of the Hilbert curve
by $n$-th iteration, which is denoted as $\mathcal{H}_{n}$,

$\displaystyle\mathcal{H}_{n}(0.q_{1}q_{2}\cdots q_{n})$
$\displaystyle=\left(\begin{aligned} &\mathcal{R}e\\\
&\mathcal{I}m\end{aligned}\right)\sum\limits_{j=1}^{n}\frac{1}{2^{j}}H_{q_{0}}H_{q_{1}}H_{q_{2}}\cdots
H_{q_{j-1}}h_{q_{j}},$ (3)
$\displaystyle=\sum\limits_{j=1}^{n}\frac{1}{2^{j}}(-1)^{e_{0j}}\text{sgn}(q_{j})\left(\begin{aligned}
&(1-d_{j})q_{j}-1\\\ &1-d_{j}q_{j}\end{aligned}\right)$
$\displaystyle\text{sgn}(x)$ $\displaystyle=\left\\{\begin{aligned} &1,\text{
if }x>0,\\\ &0,x=0.\end{aligned}\right.$ $\displaystyle e_{kj}$
$\displaystyle=\\#(\text{ ''k" preceding }q_{j})\mod 2,$ $\displaystyle d_{j}$
$\displaystyle=e_{0j}+e_{3j}\mod 2,$

where $\\#$ is the counting function and $k\in\\{0,3\\}$. We have drawn the
image points of finite quaternary ($2\leq n\leq 3$) connected by straight
lines in Figure flattening curves left. Note that the order $n$ approximation
of the Hilbert curve originates in the lower-left sub-square and terminates in
the lower-right sub-square. The exit point from each sub-square coincides with
the point that goes into the following sub-square.

##### Zigzag curve

We study the Zigzag curve on the image with a size of $H\times W$. For
convenience, we assume that both $H$ and $W$ are equal to 1 and divided
uniformly into $2^{n}$ parts. Given a real number $t\in[0,1]$ which can be
represented in quaternary form with finite length: $t=0.q_{1}q_{2}\cdots
q_{n}$, it is defined by $\mathcal{Z}$ as follows:

$\mathcal{Z}:0.q_{1}q_{2}\cdots q_{n}\mapsto\left(\begin{aligned}
&(\sum\limits_{k=1}^{n}q_{k}4^{n-k}\%2^{n})*\frac{1}{2^{n}}+\frac{1}{2^{n+1}}\\\
&\lfloor\frac{\sum\limits_{k=1}^{n}q_{k}4^{n-k}}{2^{n}}\rfloor*\frac{1}{2^{n}}+\frac{1}{2^{n+1}}\end{aligned}\right)$
(4)

##### Morton Curve

The generating process of the Morton curve is similar to the Hilbert curve’s.
We first denote the $n$-th approximation of the Morton curve as
$\mathcal{M}_{n}$. Morton curve is the limit of $\mathcal{M}_{n}$ as $n$ goes
to infinity. The conversion function from binary to decimal is denoted by
$\mathcal{B}$. The generating process of the Morton curve is driven as
follows:

$\displaystyle\mathcal{M}_{n}:t\in\mathcal{I}\mapsto\mathcal{M}_{n}(t)\in\mathcal{Q}$
(5) $\displaystyle\mathcal{M}_{n}(\frac{\mathcal{B}(q_{1}q_{2}\cdots
q_{n})}{2^{n}-1})=\left(\begin{aligned} &\frac{\mathcal{B}(q_{1}q_{3}\cdots
q_{n})}{2^{n/2}}\\\ &\frac{\mathcal{B}(q_{2}q_{4}\cdots
q_{n-1})}{2^{n/2}}\end{aligned}\right)\triangleq p\in\mathcal{Q}$
$\displaystyle\mathcal{M}_{n}(t)=p_{0}*(1-s)+p_{1}*s,t\in[\mathcal{M}_{n}^{-1}(p_{0}),\mathcal{M}_{n}^{-1}(p_{1})]$
$\displaystyle\text{where
}s=\frac{t-\mathcal{M}_{n}^{-1}(p_{0})}{\mathcal{M}_{n}^{-1}(p_{1})-\mathcal{M}_{n}^{-1}(p_{0})}\in[0,1],q_{i}\in\\{0,1\\}$

##  Appendix B Expressions for Matrix Flattening

As discussed in Section 3.1 Matrix Unfolding, we give the expressions for the
three matrix unfolding methods as follows.

##### Hilbert Flattening

Hilbert flattening is built upon the Hilbert curve, with the approximation of
the Hilbert curve of order $n$, we defined its operation. Consider an image
with resolution $n\times n$, the inverse map of the approximation of Hilbert
curve at order $n$ provides the mechanism of HF:

$\mathcal{H}_{n}^{-1}:\left(\begin{aligned}
&\frac{i}{2^{n}}+\frac{1}{2^{n+1}}\\\
&\frac{j}{2^{n}}+\frac{1}{2^{n+1}}\end{aligned}\right)\mapsto=0.q_{1}q_{2}\cdots
q_{n},$ (6)

where $\mathcal{H}_{n}(0.q_{1}q_{2}\cdots
q_{n})=(\frac{i}{2^{n}}+\frac{1}{2^{n+1}},\frac{j}{2^{n}}+\frac{1}{2^{n+1}})^{T}$.
Then the pixel on the image contains point
$(\frac{i}{2^{n}}+\frac{1}{2^{n+1}},\frac{j}{2^{n}}+\frac{1}{2^{n+1}})^{T}$
will be assigned the value $0.q_{1}q_{2}\cdots q_{n}$. All the pixels on the
images will be ordered by their values, which in fact gives the definition of
Hilbert Flattening.

##### Zigzag Flattening

Same as HF, given a real number $t\in[0,1]$ which can be represented in
quaternary form with finite length: $t=0.q_{1}q_{2}\cdots q_{n}$, the ZF is
defined by $\mathcal{Z}^{-1}$ as follows:

$\mathcal{Z}^{-1}:[\frac{i}{2^{n}},\frac{j}{2^{n}}]\mapsto 0.q_{1}q_{2}\cdots
q_{n}=\mathcal{Z}^{-1}([\frac{i}{2^{n}},\frac{j}{2^{n}}]),$ (7)

where $0\leq i,j\leq 2^{n}-1$.

##### Morton Flattening

According to the definition of Morton Curve in Equation (5), we define the
Morton Flattening of order $n$ by

$\mathcal{M}_{n}^{-1}:\left(\begin{aligned}
&\frac{\mathcal{B}(q_{1}^{0}q_{2}^{0}\cdots q_{n-1}^{0})}{2^{n/2}}\\\
&\frac{\mathcal{B}(q_{1}^{1}q_{2}^{1}\cdots q_{n-1}^{1}}{2^{n/2}}\\\
\end{aligned}\right)\mapsto\frac{\mathcal{B}(q_{1}^{0}q_{1}^{1}\cdots
q_{n-1}^{0}q_{n-1}^{1})}{2^{n}-1}$ (8)

where $\mathcal{M}_{n}^{-1}$ is the inverse mapping of $\mathcal{M}_{n}$.

##  Appendix C Proof of the Matrix Flattening Properties

The properties of different matrix flattening have been discussed in Section
3.2, where we derived some qualitative remarks. Here, we give formal
definitions and proofs of these claims as follows.

##### Dilation Factor and Limits

We introduce a definition of the limit, namely the dilation factor.
Specifically, given two points $t_{1},t_{2}\in[0,1]$, the quanternary form are
represented as $t^{1}=0.q_{1}^{1}q_{2}^{1}\cdots$ and
$t^{2}=0.q_{1}^{2}q_{2}^{2}\cdots$ when these two points are close. It means
that for an large integer $j$ such that $q_{k}^{1}=q_{k}^{2},\forall 1\leq
k\leq j$. By applying the formula in Equation 3, we obtain the distance
between points of $\mathcal{H}(t^{1}),\mathcal{H}(t^{2})$ as follows:

$|\mathcal{H}(t^{1})-\mathcal{H}(t^{2})|^{2}\leq\sum\limits_{k=j+1}\frac{8}{2^{k}}\leq\frac{8}{2^{j}}.$
(9)

The dilation bound of the Hilbert curve is shown in Theorem C.1, We find that
HF operation can obtain a sequence ordering of the image/feature map which
guarantees that consecutive parts in sequence are close in the original image.

Now we study the dilation factor of the ZF operation on an image with a size
of $H\times W$. Let $t^{1}=0.\underbrace{00\cdots
0}_{\frac{n}{2}}\underbrace{33\cdots 3}_{\frac{n}{2}}$ and
$t^{2}=0.\underbrace{00\cdots 0}_{\frac{n}{2}-1}1\underbrace{00\cdots
0}_{\frac{n}{2}}$, which are consecutive points in the interval $[0,1]$ with
distance $\frac{1}{4^{n}}$. We have
$\frac{|\mathcal{Z}(t^{1})-\mathcal{Z}(t^{2})|^{2}}{\frac{1}{4^{n}}}=\frac{(1-\frac{1}{2^{n}})^{2}+\frac{1}{4^{n}}}{\frac{1}{4^{n}}}=4^{n}-2^{n+1}+2$.
Then we get Remark C.2. And, our proposed Remark has been cited in the point
cloud classification and segmentation tasks [Chen et al., 2022].

For Morton flattening, let $p_{0}=\left(\begin{aligned}
&\mathcal{B}(0\underbrace{1\cdots 1}_{\frac{n}{2}-1})/2^{n/2}\\\
&\mathcal{B}(\underbrace{1\cdots 1}_{\frac{n}{2}})/2^{n/2}\\\
\end{aligned}\right)$ ,$p_{1}=\left(\begin{aligned}
&\mathcal{B}(1\underbrace{0\cdots 0}_{\frac{n}{2}-1})/2^{n/2}\\\
&\mathcal{B}(\underbrace{0\cdots 0}_{\frac{n}{2}})/2^{n/2}\\\
\end{aligned}\right)$, we have
$\mathcal{M}_{n}^{-1}(p_{0})=\frac{2^{n/2}}{2^{n}-1}$ and
$\mathcal{M}_{n}^{-1}(p_{1})=\frac{2^{n/2}-1}{2^{n}-1}$. So we have

$\frac{|p_{0}-p_{1}|^{2}}{|\mathcal{M}_{n}^{-1}(p_{0})-\mathcal{M}_{n}^{-1}(p_{1})|}=\frac{\frac{1}{2^{n}}+1}{\frac{1}{2^{n}-1}}=2^{n}-2^{-n}.$
(10)

Then we get Remark C.3.

###### Theorem C.1

The square-to-linear dilation factor of the Peano-Hilbert curve is equal to 6
[Bauman, 2006b], which means that the maximum value of
$\frac{|\mathcal{H}(t^{1})-\mathcal{H}(t^{2})|^{2}}{|t^{1}-t^{2}|}\leq 6$.

###### Remark C.2

The square-to-linear dilation factor of the ZF curve is $\infty$.
($\lim\limits_{n\rightarrow\infty}4^{n}-2^{n+1}+2=\infty$).

###### Remark C.3

The square-to-linear dilation factor of the MF curve is $\infty$.
($\lim\limits_{n\rightarrow\infty}2^{n}-2^{-n}=\infty$).

As mentioned in Section 3.2 Scale Robustness of Folding, as
$n\rightarrow\infty$, we employ the value of the ratio between the distances
after multiscale folding to indicate the scale robustness. Below we give the
steps for calculating the ratios for HF and ZF, respectively.

$\displaystyle\lim\limits_{n\rightarrow\infty}\frac{d_{H}^{2n}}{d_{H}^{2(n+1)}}=\lim\limits_{n\rightarrow\infty}\frac{d_{H}^{2n}}{d_{L}}\lim\limits_{n\rightarrow\infty}\frac{d_{L}}{d_{H}^{2(n+1)}}=6\times\frac{1}{6}=1$
(11)

$\displaystyle\lim\limits_{n\rightarrow\infty}\frac{d_{Z}^{2n}}{d_{Z}^{2(n+1)}}=\lim\limits_{n\rightarrow\infty}\frac{d_{Z}^{2n}}{d_{L}}\lim\limits_{n\rightarrow\infty}\frac{d_{L}}{d_{Z}^{2(n+1)}}=\lim\limits_{n\rightarrow\infty}\frac{4^{n}-2^{n+1}+2}{4^{n+1}-2^{n+2}+2}=\frac{1}{4}$
(12)

##### Formal Definition of DeGrid

The steps for calculating the DeGrid have been given in Section 3.2 Grid
Structure Preservation, and we give its formal expression as follows. Suppose
we have a sequence of points of length $N$. For each point $p$ at position $i$
$(1\leq i\leq N)$, we collect the neighbors which are $K$ steps away from $p$.
The DeGrid definition of these pixel points with respect to $p$ is

$\textbf{DeGrid}(p)=\frac{\sum\limits_{\genfrac{}{}{0.0pt}{2}{i-K\leq k\leq
i+K}{1\leq p+k\leq
N}}\|\mathcal{F}^{-1}(p_{k})-\mathcal{F}^{-1}(p)\|_{2}}{\\#(K\text{ step
neighbors})}.$ (13)

##### Symmetry Group Definition of Scale Robustness

According to the general equivariant [Bronstein et al., 2021, Wang et al.,
2022] of the convolution operator which is defined in Definition C.4, we give
a corollary about $\mathcal{S}$-robust of the flattening operator. Take
$\Omega=\mathbb{Z}_{2^{n}}\times\mathbb{Z}_{2^{n}}$ to be a 2-D grid, and
$\Omega^{\prime}=\mathbb{Z}_{2^{n+n}}$ to be a 1-D sequence. Consider the
$n$-th order and $(n+1)$-th order approximation of Hilbert flattening as
reported in Eq. 3, geometrically, the HF operation just divides the $n$-th
order approximation Hilbert curve uniformly between every pair of endpoints
into three parts, then moves the second part away from the original curve with
distance $\frac{1}{2^{n+1}}$. Finally, it connects the moving part with the
endpoints of the second part (please turn to Fig. 2 for details).

Given an image $I$ with size $2^{n+1}\times 2^{n+1}$, we utilize the
$(n+1)$-th order HF to unfold it. We denote the pixel set after flattening as
$\mathcal{H}_{n+1}(I)$. Also, we first scale down the image $I$ into image
$I_{{1}/{2}}$ with size $2^{n}\times 2^{n}$. We denote the pixel set after
$n$-th order HF as $\mathcal{H}_{n}(I_{{1}/{2}})$. According to the previous
two paragraphs, $\mathcal{H}_{n}(I_{{1}/{2}})$ and $\mathcal{H}_{n+1}(I)$
satisfy the following condition:

$(\mathcal{H}_{n+1}(I))_{{1}/{2}}\approx\mathcal{H}_{n}(I_{{1}/{2}}),$ (14)

where ${{1}/{2}}$ means that image scaling ratio. Consider the scale operation
group $\mathcal{S}=\\{(\cdot)_{2^{-m}}|m\in\mathbb{Z}\\}$, we have

$(\mathcal{F}_{n+m}(I))_{2^{-m}}\approx\mathcal{F}_{n}(I_{2^{-m}}),$ (15)

where $\mathcal{F}$ is a flattening operator, and we get the Corollary C.5. In
conclusion, as $n$ approaches a sufficiently large number (i.e.,
$n\rightarrow+\infty$), we only find the Hilbert flattening is
$\mathcal{S}$-robust.

###### Definition C.4

A function $f:\mathcal{X}(\Omega)\rightarrow\mathcal{X}(\Omega)$ is
$\mathcal{G}$-robust if $f(\rho(g)x)\approx\rho(g)f(x)$ for all
$g\in\mathcal{G}$, i.e., group action on the input affects the output in the
same way, where $\rho$ is a representation of group $\mathcal{S}$,
$\mathcal{X}(\Omega)$ denotes all signals on domain $\Omega$.

###### Corollary C.5

A flattening function
$\mathcal{F}:\mathcal{X}(\Omega)\rightarrow\mathcal{X}(\Omega^{\prime})$ is
$\mathcal{S}$-robust if
$\mathcal{F}(\rho(g)x)\approx\rho^{\prime}(g)\mathcal{F}(x)$ for all
$g\in\mathcal{S}$, i.e., group action on the input affects the output in the
same way with input and output spaces having different domains
$\Omega,\Omega^{\prime}$ and representations $\rho,\rho^{\prime}$ of the same
group $\mathcal{S}$.

##  Appendix D Additional Results and Analysis

Due to space constraints, we present some additional experimental results and
analysis here.

##### Additional CKA Visualization

We provide the additional representation structure within and across ViT-L,
ResNet50, and our Localformer-L networks, and the results are reported in Fig.
9. One can see that not only the shallowest layers of Localformer-L are
similar to the shallower third of ResNet50 layers, but also the overall
representations of Localformer-L and ResNet50 are more similar. Intuitively,
upon comparing Fig. 8 and 9, we posit that our HTS works better on large-scale
ViT networks. This implies that the large-scale model’s locality aggregation
capability remains vital for representation learning.

Figure 9:  The representation similarity and CKA metric of ViT-L and our
Localformer-L trained on ImageNet-1K. We also give the cross-model
visualization results comparing all layers of both models with ResNet50. Those
results serve as a complement to Fig. 8 in the main text.  Figure 10:  We
refer to Dosovitskiy et al. [2020] to calculate the similarity of position
embeddings for different ViTs. The brightness of a pixel indicates the cosine
similarity between one patch with the other patches. For clarity, we
intercepted the middle patch position (i.e., $4\times 4$ in (a) and (c),
$6\times 6$ in (b) and (d)) from all the patches (i.e., $14\times 14$ in (a)
and (c), $24\times 24$ in (b) and (d)). The heat maps of (b) and (d) are
obtained from the original position embedding (a) and (c) by linear
interpolation respectively.

##### Position Embedding

The proposed HTS and TA do not change the parameters and calculation steps of
the original position encoding module, much less a new position encoding
method. To check that our method has better positional encoding capability
than vanilla ViT, we refer to [Dosovitskiy et al., 2020, Raghu et al., 2021]
to visualize the similarity of position embeddings, and the results are shown
in Fig. 10. We see that the absolute position learned by our Localformer is
more accurate, which may be one reason for the performance improvement
achieved by the Localformer on ImageNet-1K. As an example, please compare
columns $6$ and $9$ in Fig. 10 (a) and (c). We also plot the magnified
position embeddings after the linear interpolation, see Fig. 10 (b) and (d).
And, we find that compared to the original ViT, our Localformer retains most
of the position info.

Figure 11:  Thanks to [Zhang et al., 2006, Tautenhahn, 2003], we present here
examples of arbitrary Hilbert flattening. The left panel shows a resolution of
$14\times 14$, while the right panel at $16\times 9$.

##  Appendix E Arbitrary Hilbert Flattening

For clarity, we focus on the grid with equal size of height and width
($2^{n}$). As shown in Fig. 11, following a simple recursive algorithm
proposed in [Tautenhahn, 2003, Zhang et al., 2006], the general Hilbert
flattening can cover the grid with arbitrary size.