Rotation-Invariant Vectorized Shape Representations
Hamid Shafieasl, Jeff M. Phillips · 2026
Read Rotation-Invariant Vectorized Shape Representations by Hamid Shafieasl, Jeff M. Phillips (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27498.txt.
Introduction
Hamid Shafieasl and Jeff Phillips build a vector code for flat shapes that stays the same under rotation. For star-shaped objects in standard form they sketch a short vector that tracks shape distance, letting search and grouping run directly in shape space. The code maps distinct shapes to distinct vectors up to rotation and a mirror-flip step called reverse of complement.
Catalog record
| CREATOR | Hamid Shafieasl, Jeff M. Phillips |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94271 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.27498
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rotation-Invariant Vectorized Shape Representations Hamid Shafieasl, Jeff M. Phillips Abstract We introduce a rotation-invariant representation of planar shapes. In particular, this representation encodes shapes as vectors such that the Euclidean distance between them serves as a valid shape distance. For standardized, star-shaped objects, we can deterministically create a sketched vector of dimension O ( 1 / ε ) O(1/\varepsilon) in O ( ( 1 / ε ) log ( 1 / ε ) ) O((1/\varepsilon)\log(1/\varepsilon)) time that approximates this shape distance to within ε \varepsilon . Moreover, because the representation is a standard Euclidean vector, we can directly and efficiently perform various data analyses, such as nearest neighbor search and clustering, in shape space, inherently invariant to the rotation of the shapes. We demonstrate this through a series of simple experiments. The key technical contribution operates on functions over 𝕊 1 \mathbb{S}^{1} , which we use to encode standardized objects. The most general rotation-invariant representation of these functions works through a map to an infinite-dimensional function space, parameterized by an offset parameter. By analyzing special discretized cases of these functions, we show that the representation is strictly injective up to the desired rotation and a mirror-flip-type operation we call reverse of complement (RoC). While RoC status can be controlled by how the function is defined, it is inherent to the representation and required to be handled in the analysis. Regardless, the vectorized representation is robust to small shape perturbations, and hence discretizing the angles leads to the efficient approximation and algorithm. 1 Introduction The shape of an object (a compact set X\subset\mathbb{R}^{d} ) refers to its properties modulo position and orientation. A core challenge when working in shape spaces [ 19 , 27 ] is defining a proper distance between shapes, notably, this distance must not depend on the specific positional embedding of the shape. That is, the comparison between two shapes should return the same value under any allowable transformation of one of the shapes. There have been three major approaches to this challenge. First, and perhaps most popular in computational geometry [ 24 , 44 ] , is to compute a shape distance \texttt{{d}}(X_{1},X_{2})=\min_{t\in\mathbb{R}^{d},R\in\mathbb{SO}(d)}\texttt{{d}}^{\prime}(X_{1},R(X_{2}+t)) where t is a translation [ 1 , 11 , 13 ] , R a rotation [ 3 , 14 , 12 ] , and \texttt{{d}}^{\prime} is a traditional distance between sets (e.g., Hausdorff [ 15 ] or largest polygon placement [ 2 ] ) which relies on the positional embedding of sets X_{1} and X_{2} . For some L_{2} variants where an alignment is known, the Procrustes approach [ 23 , 6 , 21 , 20 ] offers closed-form solutions. However, the minimization over choices of t and R is typically computationally challenging, although it has been carefully studied and formalized as in the citations above. The second approach is to compute intrinsic shape characteristics that do not depend on positional information, and define a distance between these characteristics. Such approaches include, for instance, the turning function between curves [ 5 ] , the Gromov-Hausdorff distance [ 31 , 32 , 42 ] , and the Persistent Homology Transform [ 7 , 17 ] . These distances again typically require optimizing an alignment between the characteristic-bearing parts of the shapes, making them computationally demanding. The third category comprises machine learning-driven heuristics [ 45 ] that compute rotation-invariant representations [ 37 ] . Classic examples include those based on spherical harmonics [ 26 ] , while modern methods often use the PointNet architecture [ 39 , 40 ] . While these representations are empirically robust and translation/rotation invariant, they lack formal analysis regarding which metric properties they preserve and how fine a resolution is needed to distinguish different objects. A major advantage of these heuristic approaches is that they encode the shape as a vector [ 38 ] , allowing for fast downstream computation without the need to optimize an alignment. This paper introduces a new representation for planar shapes that is: 1. rotation invariant; 2. a vector, and the shape distance is Euclidean distance between the sketched vectors; 3. up to a controlled level of discretization, the Euclidean vector distance is a metric between the base shapes, modulo rotation and an inherent \mathsf{RoC} operation; and 4. can \varepsilon -approximate standardized star shapes in O(\frac{1}{\varepsilon}) dimensions in O(\frac{1}{\varepsilon}\log\frac{1}{\varepsilon}) time. Power of vectors. We reiterate that the second property means we can embed shapes as (high-dimensional) vectors, and then no longer need to worry about optimizing an alignment between them. The ability to directly use the Euclidean distance means that this can immediately plug into all of the amazing infrastructure built for this setting. This includes recent advances in fast nearest neighbor search [ 8 ] using NHSW structures [ 28 , 18 ] (or LSH [ 4 ] if one prefers stronger guarantees). Moreover one can create mean shape representations using the sketch representation, and thus directly apply k -means clustering. Further this representation is the standard input for any machine learning library for classification or regression. While a full exploration of this power is beyond the scope of this paper, we do demonstrate the stability and convenience of this representation through some simple retrieval and clustering applications on 2 -dimensional shapes. Another important aspect of such sketched representations is the computational cost to construct them. As with any Euclidean vectors, the dimensionality can be reduced to O((1/\varepsilon^{2})\log n) dimensions to preserve relative (1+\varepsilon) error among n shapes, and our method allows us to directly compute such a randomized approximate embedding akin to Rahimi-Recht random Fourier features (RFFs) [ 41 ] for the kernel methods [ 22 ] . However, more interestingly, we show how to deterministically create representations efficiently with a fast Fourier transform [ 16 ] . This leads to an \varepsilon -approximate representation in O((1/\varepsilon)\log(1/\varepsilon)) time. Rotationally discretizing shapes. The core analysis of our method operates in \mathbb{S}^{1} , and in fact a discrete version of it \mathbb{S}^{1}_{m} . We convert a shape into a function on \mathbb{S}^{1}_{m} by considering standardized star shapes , which are objects where every point in the shape can be connected to the origin by a line segment fully contained within its interior. We discretize shapes by their polar coordinates uniformly in m wedges, and each distance maps to one value in \mathbb{S}^{1}_{m} ; this mapping is common in shape analysis [ 29 , 10 , 34 , 43 ] . Sketching discrete \mathbb{S}^{1} . The core technical result is a rotation-invariant sketch for functions f on \mathbb{S}^{1}_{m} mapped to V_{f}\in\mathbb{R}^{m} . In this setting we can index f:[m]\to\mathbb{R} (more generally f:[m]\to\mathbb{R}^{w} ) by an integer j\in[m]=\{0,1,2,\ldots,m-1\} . The k th coordinate of V_{f} , denoted V_{f}(k)\in\mathbb{R} , encapsulates all pairs of entries in f with a difference of k in their index. We set V_{f}(k)=\sum_{j=1}^{m}\Phi(f(j)-f(j+k)) where typically \Phi(z)=\exp(-z) . The characteristic nature of \Phi ensures that the finite sum of the terms in V_{f}(k) must originate from a unique set \Delta_{f}(k) of distances. Moreover, since this only compares offsets, it is invariant to rotation. The challenging aspect is showing that in whole (using each V_{f}(k) for k\in[m] ) this sketch is only invariant up to rotation, and no other transformations; so