2401/2401.00935.md

Title: Boundary Attention: Learning curves, corners, junctions and grouping

URL Source: https://arxiv.org/html/2401.00935

Markdown Content: Back to arXiv

This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.

Why HTML? Report Issue Back to Abstract Download PDF Abstract 1Introduction 2Related Work 3Representation 4Network Architecture 5Experiments 6Ablations 7Conclusion S1The space of 𝑀 -junctions S2Training Data S3Model Details S4Model Behavior S5Additional Examples for Low-light Images S6Additional Uses of Our Model References

HTML conversions sometimes display errors due to content that did not convert correctly from the source. This paper uses the following packages that are not yet supported by the HTML conversion tool. Feedback on these issues are not necessary; they are known and are being worked on.

failed: axessibility failed: etoc failed: orcidlink

Authors: achieve the best HTML results from your LaTeX submissions by following these best practices.

License: arXiv.org perpetual non-exclusive license arXiv:2401.00935v3 [cs.CV] 16 Sep 2024 1 Boundary Attention: Learning curves, corners, junctions and grouping Mia Gaia Polansky1  Charles Herrmann2  Junhwa Hur2  Deqing Sun2  Dor Verbin2  Todd Zickler2 Much of this work was done while the author was a student researcher at Google. Abstract

We present a lightweight network that infers grouping and boundaries, including curves, corners and junctions. It operates in a bottom-up fashion, analogous to classical methods for sub-pixel edge localization and edge-linking, but with a higher-dimensional representation of local boundary structure, and notions of local scale and spatial consistency that are learned instead of designed. Our network uses a mechanism that we call boundary attention: a geometry-aware local attention operation that, when applied densely and repeatedly, progressively refines a pixel-resolution field of variables that specify the boundary structure in every overlapping patch within an image. Unlike many edge detectors that produce rasterized binary edge maps, our model provides a rich, unrasterized representation of the geometric structure in every local region. We find that its intentional geometric bias allows it to be trained on simple synthetic shapes and then generalize to extracting boundaries from noisy low-light photographs.

1Introduction

Converting a precise contour that is defined mathematically in continuous 2D space to a discrete pixel representation is a common task in computer graphics, and there are established tools for rasterization [7, 17], anti-aliasing [10, 3] and so on. However, the inverse problem in computer vision of robustly inferring precise, unrasterized contours from discrete images remains an open challenge, especially in the presence of noise.

Earlier work by Canny [2] and many others [4, 15, 9, 8, 14] explored the detection of unrasterized parametric edge models, and there are a variety of bottom-up algorithms that try to connect them by encouraging geometric consistency via edge-linking or message-passing. But since the dawn of deep learning, boundaries have almost exclusively been represented using discrete, rasterized maps; and spatial-consistency mechanisms that were previously based on explicit curve geometry have largely been replaced by black-box neural networks.

In this paper, we take inspiration from early computer vision work and revisit the task of finding unrasterized boundaries via bottom-up geometric processing. But unlike early work, we leverage self-attention to learn these processes instead of hand-crafting them, thereby combining the benefits of geometric modeling with the efficiency and representational power of deep learning.

We focus on the low-level task of finding boundaries that separate regions of uniform color, as depicted by the toy problem in Figure 1. This task becomes difficult at high noise levels, especially within local patches, and we address it by creating a model that can learn to exploit a wide range of low-level cues, such as curves being predominantly smooth with low-curvature; curves tending to meet at corner and junction points; contours tending to have consistent contrast polarity throughout their extent; and colors tending to vary smoothly at locations away from boundaries.

The core of our model is a mechanism we call boundary attention. It is a boundary-aware local attention operation that, when applied densely and repeatedly, progressively refines a field of variables that specify the local boundaries within dense (stride-1) patches of an image. The model’s output is a dense field of unrasterized geometric primitives that, as depicted in the right of Figure 1, can be used in a variety of ways, including to produce an unsigned distance function and binarized map for the image boundaries, a boundary-aware smoothing of the input image colors, and a map of spatial affinities between any query point and the pixels that surround it.

An important feature of our model is that its output patch primitives (see Figure 2) have enough flexibility to represent a wide range of local boundary patterns and scales, including thin bars, edges, corners and junctions, all with various sizes, and all without rasterization and so with unlimited resolution. This gives our model enough capacity to learn to localize boundaries with high precision, and to regularize them in the presence of noise without erroneously rounding their corners or missing their junction points.

Figure 1: Pipeline overview. The image unfolds into stride-1 patches, and boundary attention operates iteratively on their embeddings to produce for each patch: (i) a parametric three-way partitioning, and (ii) a parametric windowing function that defines its effective patch size. (Figure 2 shows parameterization details.) This output field implies a variety of global maps, shown in clockwise order: a boundary-aware smoothing of the input colors; an unsigned boundary-distance map; a boundary map; and a map of spatial affinities between any query point and its neighbors.

We intentionally design our model with components that are local and invariant to discrete spatial shifts, enabling it to be trained on small-sized images and then deployed on much larger and differently-shaped ones. By tying the weights across multiple portions of the network, we increase its resilience to noise, which we validate through ablations. Our resulting model is very compact, comprising only 207k parameters, and it runs much faster than comparable optimization-based approaches. Further, our model can be trained to a useful state with very simple synthetic data, made up of random circles and triangles that are uniformly colored and then corrupted by noise. Despite the simplicity of this training data, we find that the model’s learned internal activations exhibit intuitive behavior, and that the model generalizes to real world photographs, including those taken in low-light and have substantial shot noise.

Our main contributions can be summarized as follows:

1.

We introduce a bottom-up, feedforward network that decomposes an image into an underlying field of local geometric primitives that explicitly identify curves, corners, junctions and local grouping.

2.

We do this by introducing a new parameterization for local geometric primitives, and a new self-attention mechanism that we call boundary attention.

3.

We identify the best architecture among a family of candidates, and we show that it generalizes from simple synthetic images to real low-light photographs.

Figure 2: Parameterization details. Left: Each patch 𝑘 is associated with an unrasterized three-way partitioning of its area (colored blue, orange and purple here). The partitioning parameters comprise a vertex ( 𝑢 , 𝑣 ) , orientation 𝜃 , and angles ( 𝜔 1 , 𝜔 2 , 𝜔 3 ) , defined up to scale. A: A walk through junction space by linearly interpolating between junctions is spatially smooth, and can represent edges, bars, corners, Y-junctions, T-junctions and uniform regions. B: Each junction is modulated through a learned windowing function. The windowing parameters 𝐩

( 𝑝 1 , 𝑝 2 , 𝑝 3 ) are convex weights over a dictionary of binary pillboxes. 2Related Work

Early approaches to edge detection rely primarily on low-level or local information. Canny [2] and others (e.g., [4, 15, 9, 8]) use carefully chosen filters, and later ones like pB [14] and gPb [13] combine such filters using a handful of trainable parameters. These methods provide local estimates of straight-edge position and orientation and they can subsequently be filtered and joined using geometry-based processes such as edge-linking [2]. However, they often struggle near corners and junctions due to the difficulty of designing filters for these more complicated structures. Structured edges [6] and other early learning-based methods [5, 12] are able to detect more-complicated structures, but they represent their local outputs using discrete, rasterized boundary maps that are not directly compatible with continuous boundary parameterizations or geometry-based linking.

Recently, the field of junctions (FoJ) [23] introduced a way to detect more-complicated local structures while also representing them parametrically, without rasterization. By using its unrasterized representations in a customized non-convex optimization routine, the method can detect curves, corners and junctions with high precision and with unprecedented resilience to noise. Our model is strongly inspired by this work, and it improves upon it by introducing an enhanced family of parameterized geometric primitives (Figure 2) and by replacing its hand-designed objective and associated non-convex optimization routine with a learned model that is fast, feed-forward and differentiable. We also tackle the challenge of representing images that vary in scale across different areas: whereas FoJ requires setting a single patch size for the entire image, our model learns to choose patch sizes adaptively in response to the input image.

We emphasize that our work is very different from a recent trend in computer vision of using deep networks to detect boundaries that are semantically meaningful (e.g., [21, 18, 27]). These models aim to identify boundaries between semantic concepts, such as people and animals, while ignoring boundaries that are inside of these concepts, such as stripes on a shirt. In contrast to this trend, we follow earlier work by focusing entirely on identifying boundaries from the bottom up, using low-level cues alone. Since our model is trained using simple synthetic data, it does not exploit object familiarity or learn to ignore intra-object contrast. This approach has advantages: It is not specialized to any predetermined set of semantic concepts or tasks, and instead of producing a pixelized boundary map, it produces a field of unrasterized primitives that provide better precision as well as richer information about local grouping. We leave for future work the exploration of how to combine our bottom-up model with other cues that are top-down and semantic.

3Representation

Our system is depicted in Figure 1. It uses neighborhood cross-attention, a patch-wise variant of cross-attention, with 𝐷 -dimensional, stride-1 embeddings. Critically, each 𝐷 -dimensional embedding explicitly encodes a tuple of values that specifies the geometric structure and spatial extent of the unrasterized local boundaries within a patch.

Our model relies on a learned (linear) mapping from the embedding dimension 𝐷 to a hand-crafted, lower-dimensional space of unrasterized boundary patterns that we call junction space. Junction space has the benefit of specifying per-patch boundary patterns without rasterization and thus with unlimited spatial precision. As depicted in Figure 2 and described in [23], it also has the benefit of including a large family of per-patch boundary patterns, including uniformity (i.e., absence of boundaries), edges, bars, corners, T-junctions and Y-junctions. Different from [23], we additionally modulate the spatial extent of each patch by learning an associated windowing function, to be described in Section 3.1.

To enable communication between patch embeddings, each of which corresponds to a local patch, we leverage the idea that each image point is covered by multiple patches, and that overlapping patches must agree in their regions of overlap. This has the effect of tying neighboring patches together, analogous to cliques in a Markov random field.

We refer to the core mechanism of our model as boundary attention. We introduce it by first defining our hand-crafted parameterization of junction space and some associated operators. Then Section 4 describes the architecture that we use to transform an image into a coherent junction-space representation.

3.1Boundary Primitives

We use parentheses ( 𝑥 ) for continuous signals defined on the 2D image plane [ 0 , 𝑊 ] × [ 0 , 𝐻 ] and square brackets [ 𝑛 ] for discrete signals defined on the pixel grid. We use 𝑐 ⁢ [ 𝑛 ] for the coordinates of the pixel with integer index 𝑛 .

Denote the 𝐶 -channel input image by { 𝐟 ⁢ [ 𝑛 ] } , where 𝐟 ⁢ [ 𝑛 ] ∈ ℚ 𝐶 is the vector image value at the discrete pixel grid index 𝑛 . Our approach is to treat the image as a field of dense, stride-1 overlapping local patches. We use Ω 𝑘 ⁢ ( 𝑥 ) to denote the spatial support of the patch that is centered at the pixel whose integer index is 𝑘 .

There are many ways to partition a local patch Ω 𝑘 ⁢ ( 𝑥 ) , and one can define parametric families of partitions. For example the set of oriented lines provides a two-parameter family of partitions, with each member of the family separating the region into points that lie on one side of a line or the other. This family of partitions would be appropriate for describing edges. Here we define a larger family of partitions that encompasses a greater variety of local boundary structures.

As depicted in the right of Figure 2, our partitions are parameterized by 𝐠 ∈ ℝ 2 × 𝕊 1 × △ 2 , where 𝕊 1 is the unit circle and △ 2 is the standard 2 -simplex. We use the notation 𝐠

( 𝒖 , 𝜃 , 𝝎 ) , where 𝒖

( 𝑢 , 𝑣 ) ∈ ℝ 2 is the vertex, 𝜃 ∈ 𝕊 1 is the orientation, and 𝝎

( 𝜔 1 , 𝜔 2 , 𝜔 3 ) are barycentric coordinates (defined up to scale) for the three relative angles, ordered clockwise starting from 𝜃 . Our convention is to express the vertex coordinates relative to the center of region Ω 𝑘 ⁢ ( 𝑥 ) , which is located at 𝑐 ⁢ [ 𝑘 ] , and we note that the vertex is free to move outside of this region. We also note that up to two angles 𝜔 𝑗 can be zero. This all makes it possible to smoothly represent a variety of partition types, including edges, bars, corners, 3-junctions and uniformity (i.e., trivial or singleton partitions), and do so with unlimited spatial resolution.

Fixing a value for 𝐠 induces three wedge support functions, denoted by

𝑠 𝑘 ⁢ 𝑗 ⁢ ( 𝑥 ; 𝐠 ) ∈ { 0 , 1 } , 𝑗

1 , 2 , 3 .

(1)

These evaluate to 1 for points 𝑥 that are in Ω 𝑘 ⁢ ( 𝑥 ) and in the 𝑗 th wedge defined by 𝐠 ; and 0 otherwise. It also induces an unsigned distance function, denoted by

𝑑 𝑘 ⁢ ( 𝑥 ; 𝐠 ) ≥ 0 ,

(2)

which represents the Euclidean distance from point 𝑥 to the nearest point in the boundary set defined by 𝐠 . Figure 2 uses three colors to visualise the wedge supports 𝑠 𝑘 ⁢ 𝑗 of a junction 𝐠 , and Figure 3 shows the unsigned distance functions for 3 × 3 grids of junction parameters. Analytic expressions for them are included in the supplement.

In order to enable the size of each region Ω 𝑘 to adapt to the local geometry and noise conditions, we equip each one with a parameterized local windowing function 𝑤 𝑘 ⁢ ( 𝑥 ; 𝐩 ) ∈ [ 0 , 1 ] , with parameters 𝐩 ∈ 𝒫

△ 𝑊 − 1 that are the coefficients of a convex combination of 𝑊 square pillbox functions. That is,

𝑤 𝑘 ⁢ ( 𝑥 ; 𝐩 )

∑ 𝑖

1 𝑊 𝑝 𝑖 ⁢ 𝟏 ⁢ [ ‖ 𝑥 − 𝑐 ⁢ [ 𝑘 ] ‖ ∞ ≤ 𝐷 𝑖 ] ,

(3)

where ∥ ⋅ ∥ ∞ is the ℓ ∞ -norm, and 𝟏 ⁢ [ ⋅ ] is the indicator function that returns 1 if the argument is true; and 0 otherwise. In our experiments we use 𝑊

3 and diameters 𝐃

( 3 , 9 , 17 ) . Figure 3 shows some examples.

Figure 3: Example of our model’s output, with examples from two different regions. Top row: Some of each region’s overlapping input patches, their corresponding outputs (visualized in the style of Figure 2), and three types of per-patch attributes that the outputs imply: unsigned distance; boundaries; and gathered wedge colors. Bottom row: Four types of global maps that are implied by accumulating values from the output field and rendered patches. 3.2Gather and Slice Operators

Our network operates by refining the field { ( 𝐠 𝑡 ⁢ [ 𝑘 ] , 𝐩 𝑡 ⁢ [ 𝑘 ] ) } over a fixed sequence of steps 𝑡

1 , … , 𝑇 . It uses two operators that we define here and depict in the right of Figure 4 to facilitate intra-patch communication between pixels within a single patch, and inter-patch communication across different patches representing overlapping image regions. The first operator is a patch-wise gather operator, in which each wedge of each patch computes the weighted average of the image values it contains (recall that 𝑐 ⁢ [ 𝑛 ] are the 𝑛 th pixel’s coordinates, and wedges are indexed by 𝑗 ):

𝐟 𝑘 ⁢ 𝑗

∑ 𝑛 𝐟 ⁢ [ 𝑛 ] ⁢ 𝑤 𝑘 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐩 ⁢ [ 𝑘 ] ) ⁢ 𝑠 𝑘 ⁢ 𝑗 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐠 ⁢ [ 𝑘 ] ) ∑ 𝑛 𝑤 𝑘 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐩 ⁢ [ 𝑘 ] ) ⁢ 𝑠 𝑘 ⁢ 𝑗 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐠 ⁢ [ 𝑘 ] ) .

(4)

The second operation is a global pixel-wise slice operation, where each pixel computes the means and variances, over all regions that contain it, of the per-region distance maps 𝑑 𝑘 ⁢ ( 𝑥 ; 𝐠 ⁢ [ 𝑘 ] ) and gathered wedge features 𝐟 𝑘 ⁢ 𝑗 . The expressions for the means are:

𝑑 ¯ ⁢ [ 𝑛 ]

∑ 𝑘 𝑤 𝑘 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐩 ⁢ [ 𝑘 ] ) ⁢ 𝑑 𝑘 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐠 ⁢ [ 𝑘 ] ) ∑ 𝑘 𝑤 𝑘 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐩 ⁢ [ 𝑘 ] ) ,

(5)

𝐟 ¯ ⁢ [ 𝑛 ]

∑ 𝑘 𝑤 𝑘 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐩 ⁢ [ 𝑘 ] ) ⁢ ∑ 𝑗 𝐟 𝑘 ⁢ 𝑗 ⁢ 𝑠 𝑘 ⁢ 𝑗 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐠 ⁢ [ 𝑘 ] ) ∑ 𝑘 𝑤 𝑘 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐩 ⁢ [ 𝑘 ] ) ⁢ ∑ 𝑗 𝑠 𝑘 ⁢ 𝑗 ⁢ ( 𝑐 ⁢ [ 𝑛 ] ; 𝐠 ⁢ [ 𝑘 ] ) .

(6)

Here, the sums are over { 𝑘 ∣ Ω 𝑘 ∋ 𝑐 ⁢ [ 𝑛 ] } so that only patches that contain 𝑐 ⁢ [ 𝑛 ] contribute to the sum. Similar expressions for pixel-wise distance map variance 𝜈 𝑑 ⁢ [ 𝑛 ] and feature variance 𝜈 𝑓 ⁢ [ 𝑛 ] , which is computed across patches containing 𝑛 and across their 𝐾 channels, are included in the supplement. Intuitively, slicing represents an accumulation of regional information into a pixel, as dictated by the partitions of all of the patches that contain the pixel.

3.3Visualizing Output

Our network’s output is a field of tuples representing the junction and windowing parameters { ( 𝐠 [ 𝑘 ] , 𝐩 [ 𝑘 ] } for all stride-1 patches of the input image. We visualize them in Figure 3 by rasterizing the continuous windowing functions 𝑤 𝑘 ⁢ ( 𝑥 ; 𝐩 ) (second column) and binary wedge supports 𝑠 𝑘 ⁢ 𝑗 ⁢ ( 𝑥 ; 𝐠 ) , which are colored purple, orange, and blue (third column). To the left, we show the input image and the regions from which the patches were extracted.

Additionally, we can use the output junction parameters to rasterize unsigned distance patches 𝑑 𝑘 ⁢ ( 𝑥 ; 𝐠 ) (fourth column), boundary patches 𝑏 𝑘 ⁢ ( 𝑥 ; 𝐠 ) (fifth column), and wedge supports 𝑠 𝑘 ⁢ 𝑗 ⁢ ( 𝑥 ; 𝐠 ) that are re-colored with their respective wedge features 𝐟 𝑘 ⁢ 𝑗 (sixth column). Note that all of these are defined continuously, so can be rasterized at any resolution.

We expect the shapes of junction boundaries in overlapping regions to agree, so that the variances 𝜈 𝑑 ⁢ [ 𝑛 ] , 𝜈 𝑓 ⁢ [ 𝑛 ] are small at every pixel. Then, the fields of means { 𝑑 ¯ ⁢ [ 𝑛 ] } , { 𝐟 ¯ ⁢ [ 𝑛 ] } can be interpreted, respectively, as a global unsigned distance map for the image boundaries (bottom row, fourth column) and a boundary-aware smoothing (bottom row, last column) of its input channel values. Figure 3 shows an example (bottom row, fifth column), where we visualize the zero-set of the global unsigned distance map—we call this the global boundaries—by gathering boundary patches 𝑏 𝑘 defined as:

𝑏 𝑘 ⁢ ( 𝑥 ; 𝐠 )

( 1 + ( 𝑑 𝑘 ⁢ ( 𝑥 ; 𝐠 ) / 𝜂 ) 2 ) − 1 ,

(7)

setting 𝜂

0.3 .

For any query pixel 𝑘 , we can also probe the containing wedge supports { 𝑠 𝑘 ⁢ 𝑗 ⁢ ( ⋅ ; 𝐠 ⁢ [ 𝑘 ] ) } and windowing functions { 𝑤 𝑘 ⁢ ( ⋅ , 𝐩 ⁢ [ 𝑘 ] ) } to compute a spatial affinity map 𝑎 𝑘 ⁢ ( 𝑥 ) that surrounds the query pixel. This represents the affinity between point 𝑐 ⁢ [ 𝑘 ] and a surrounding neighborhood with diameter that is twice that of Ω ⁢ ( 𝑥 ) . It is also the boundary-aware spatial kernel that turns the neighborhood of input features { 𝐟 ⁢ [ ⋅ ] } into the gathered value 𝐟 ¯ ⁢ [ 𝑛 ] via

𝐟 ¯ ⁢ [ 𝑛 ]

∑ 𝑘 𝑎 𝑛 ⁢ ( 𝑐 ⁢ [ 𝑘 ] ) ⁢ 𝐟 ⁢ [ 𝑘 ] .

(8)

The expression for 𝑎 𝑛 ⁢ ( 𝑥 ) follows from inserting Equation 4 into 6. The spatial affinity maps for two probed points are shown in the leftmost image of the bottom row of Figure 3. Like slicing, querying the affinity map at a pixel is a form of regional accumulation from patches to a pixel.

Figure 4: Model Architecture. All blocks are invariant to discrete spatial shifts, and only colored blocks are learned. Orange blocks operate at individual locations 𝑛 , while blue ones operate on small spatial neighborhoods. Symbol ⊕ is concatenation, and gather and slice operators (Eqs. 4–6) are depicted at right. The first iteration uses 𝜸 0 ⁢ [ 𝑛 ]

𝜸 0 ⁢ [ 𝑛 ] , 𝐟 ¯ 0 ⁢ [ 𝑛 ]

𝐟 ⁢ [ 𝑛 ] , and 𝝅 0 ⁢ [ 𝑛 ]

𝝅 𝑜 with 𝝅 𝑜 learned across the training set. Boundary attention repeats 𝑇

8 times, with one set of weights for the first four iterations and a separate set of weights for the last four iterations, resulting in 207k trainable parameters total. 4Network Architecture

We seek a differentiable architecture that can effectively initialize and then refine the fields { ( 𝐠 𝑡 ⁢ [ 𝑘 ] , 𝐩 𝑡 ⁢ [ 𝑘 ] ) } using a manageable number of iterations. This approach is motivated by the edge localization and edge-linking steps of early edge detectors like Canny’s, but has a more sophisticated local boundary model, and mechanisms for spatial consistency that are learned instead of designed. It is also analogous to the original field of junctions algorithm [23], which uses coordinate descent for initialization and iterations of gradient descent for refinement. We want to replace both steps with something that is differentiable, faster, and able to scale to larger images.

After considering a variety of alternatives, we settled on a particular family of architectures based on dot-product self-attention; and within this family, we performed an extensive set of ablations to determine the best performing model. We describe our final model here, and we provide the ablation details in Section 6. Importantly, all of our model’s components are invariant to discrete spatial shifts of the image, operating either on individual locations 𝑘 , or on small neighborhoods of locations with spatially-shared parameters. This means that our model can be trained on small images and then deployed on much larger ones. Also, our model has only 207 , 000 learnable parameters, making it orders of magnitude smaller than most deep semantic boundary detectors. As a point of reference, Diffusion Edge, a recent diffusion-based semantic boundary detection model uses on the order of 300 million parameters [26].

Our model is depicted in Figure 4. It represents the field elements as higher-dimensional embeddings 𝜸 𝑡 ⁢ [ 𝑘 ] ∈ ℝ 𝐷 𝛾 and 𝝅 𝑡 ⁢ [ 𝑘 ] ∈ ℝ 𝐷 𝜋 , which can be decoded at any iteration using the learned linear mappings 𝜸 ↦ 𝐠 and 𝝅 ↦ 𝐩 . Our final model uses 𝐷 𝛾

64 and 𝐷 𝜋

8 which we show in our experiments provides enough capacity to learn a smooth latent representation of junction space. Using separate embeddings for the junction and windowing fields provides a disentangled representation of both.

Given an input image, the network first applies a “neighborhood MLP-mixer”, which is a modified MLP-Mixer [22] that replaces the global spatial operations with convolutions of kernel size 3 . The other change is that we map the input pixels to the hidden state size with a pixel-wise linear mapping rather than taking patches of the input. This block transforms the input image into a pixel-resolution map with 𝐷 𝛾 channels. We denote this by 𝛾 0 ⁢ [ 𝑛 ] and refer to it as the initial “hidden state”. This hidden state is then refined by a sequence of eight boundary attention iterations, which we describe next. (See our experiments for a visualization of the decoded hidden states as they evolve.)

The eight iterations of refinement are broken into two blocks, each with learned weights. In each iteration, we first add a linear mapping of the initial hidden state to the current hidden state, which acts as a skip connection. Next, we clone our hidden state, concatenating a dimension 8 learned windowing embedding to one of the copies and the input image plus the current estimate of the smoothed global features to the other. We treat the copies as the inputs to neighborhood cross-attention: each pixel in the first copy does two iterations of cross attention with a size 11 patch of the second copy. We add a learned 11 × 11 positional encoding to the patch, which allows our network to access relative positioning, even though global position cues are absent. We follow each self attention layer with a small MLP.

To transform our output or intermediary hidden state into junction space and render patch visualizations, we use a simple linear mapping. We separate the windowing embedding (the last 8 dimensions) from the junction embedding (the first 64 dimensions) and project each through a linear layer. We map the junction embedding to 7 numbers that represent 𝐠

( 𝒖 , sin ⁡ ( 𝜃 ) , cos ⁡ ( 𝜃 ) , 𝝎 ) . These serve as the inputs to our gather and slice operators.

To extract 𝐩 from the windowing embedding, we linearly project the windowing embedding to a length 3 vector, which we use as coefficients in a weighted sum of three square pillbox functions with widths 3 , 9 , and 17 . This implementation of the windowing function ensures spatial overlap between neighboring patches by limiting the minimum patch size to 3 .

4.1Training

Estimating the best junctions for noisy image patches is a non-convex optimization that is prone to getting stuck in local minima [23]. We find that training our network in three stages with increasingly complex synthetic training data produces the best model. First we train the network on small 21 × 21 images containing a single junction corrupted by low amounts of Gaussian noise. Upon convergence, we retrain the network on larger 100 × 100 images containing a single circle and triangle corrupted by moderate Gaussian noise. Finally, we retrain the network on a high-noise synthetic dataset containing 125 × 125 images consisting of many overlapping triangles and circles. (See supplement for examples.)

We calculate our loss using the outputs of the two final iterations of our network, where the loss of the final output is weighted three times as much as the loss applied to the output before it. This encourages the network to allocate capacity to producing high quality outputs, while still providing supervision to intermediate junction estimates.

We train our model using a combination of four global losses applied to global (i.e. sliced) fields, and two patch-wise losses applied to individual patches. The first two losses are supervision losses penalizing mismatches between our network’s predictions and the ground truth feature and distance maps:

ℒ 𝑓

∑ 𝑛 𝛼 ⁢ [ 𝑛 ] ⁢ ‖ 𝐟 ¯ ⁢ [ 𝑛 ] − 𝐟 GT ⁢ [ 𝑛 ] ‖ 2 ,

(9)

ℒ 𝑑

∑ 𝑛 𝛼 ⁢ [ 𝑛 ] ⁢ ( 𝑑 ¯ ⁢ [ 𝑛 ] − 𝑑 GT ⁢ [ 𝑛 ] ) 2 ,

(10)

where 𝐟 GT and 𝑑 GT are the ground truth features and distance maps, respectively, and 𝛼 ⁢ [ 𝑛 ] is a pixel importance function defined as

𝛼 ⁢ [ 𝑛 ]

𝑒 − 𝛽 ⋅ ( 𝑑 GT ⁢ [ 𝑛 ] + 𝛿 ) + 𝐶 ,

(11)

with 𝛽 and 𝐶 controlling how much weight to give pixels near boundaries. We set 𝛽

0.1 , 𝛿

1 , and 𝐶

0.3 . (The supplement contains additional tests with a more involved importance mask.) Using noiseless feature maps for supervision in Equation 9 has the effect of encouraging windowing functions to be as large as possible, because larger regions imply averaging over a greater number of noisy input pixel values.

On top of the two supervision losses we apply two consistency losses borrowed from [23], which minimize the per-pixel variances 𝜈 𝑓 ⁢ [ 𝑛 ] and 𝜈 𝑏 ⁢ [ 𝑛 ] . Here, we weight them by 𝛼 ⁢ [ 𝑛 ] from Equation 11. These consistency losses encourage the junction shapes 𝐠 in overlapping regions to agree. Minimizing 𝜈 𝑓 ⁢ [ 𝑛 ] also provides a second mechanism to encourage windowing functions to be large. Larger windows increase gather area, thereby reducing noise in wedge features 𝐟 𝑛 ⁢ 𝑗 that are sliced to compute variance 𝜈 𝑓 ⁢ [ 𝑛 ] at each pixel 𝑛 .

Finally, we use two patch-wise losses to encourage individual feature and distance patches to agree with the supervisory ones:

ℓ 𝑓

∑ 𝑘 𝜒 ⁢ [ 𝑘 ] ⁢ ∑ 𝑛 ∈ Ω 𝑘 𝛼 ⁢ [ 𝑛 ] ⁢ ‖ 𝐟 ¯ ⁢ [ 𝑛 ] − 𝐟 GT ⁢ [ 𝑛 ] ‖ 2 ,

(12)

ℓ 𝑑

∑ 𝑘 𝜒 ⁢ [ 𝑘 ] ⁢ ∑ 𝑛 ∈ Ω 𝑘 𝛼 ⁢ [ 𝑛 ] ⁢ ( 𝑑 ¯ ⁢ [ 𝑛 ] − 𝑑 GT ⁢ [ 𝑛 ] ) 2 ,

(13)

where 𝜒 ⁢ [ 𝑘 ] is a patch importance function defined as:

𝜒 ⁢ [ 𝑘 ]

( ∑ 𝑛 ∈ Ω 𝑘 ( 𝑑 GT ⁢ [ 𝑛 ] + 𝛿 ′ ) ) − 1 ,

(14)

with 𝛿 ′

1 . These per-patch losses provide a more direct signal for adjusting model weights, compared to per-pixel losses which average over multiple patches.

Figure 5: Left: ODS F-score for our method and multiple baselines at different noise levels computed on noisy synthetic data. The bottom inset show example patches at representative PSNR values. Our method outperforms all baselines at low noise and is better or competitive with other techniques at high noise. Right: Comparing the F-score for different techniques with their runtime. Our method has the best average F-score while also being much faster than the second best method Field of Junctions. Figure 6: Left: Qualitative comparison of our model versus other methods for a noisy crop from the ELD dataset [24]. See the supplement for more examples. Our method provides more detail than other techniques at low noise and is more robust to high levels of noise. Right: Repeatability of the estimated boundaries of crops from the ELD dataset over increasing noise. Over multiple levels of real sensor noise, our method is the most consistent in predicting edges. 5Experiments Implementation details.

In the final stage of training, we use noisy synthetic data of many randomly-colored overlapping triangles and circles. We render 240 × 320 images containing 15 to 20 shapes each, but use 125 × 125 crops for training. To those crops we add Gaussian or Perlin noise [16], and with probability 0.1 we average over the color channels to produce grayscale inputs. Our dataset contains 10 5 images, 90 % of which are used for training, and the rest for validation.

Baselines.

Since we focus on bottom-up edge and corner detection, we compare against other techniques with a similar focus and that, like us, do not train on large semantic datasets: Canny [2], gPb [13], Structured Edges (SE) [6], and Field of Junctions (FoJ) [23].

Quantitative results.

For quantitative evaluation we cannot use semantic edge detection benchmarks like BSDS500 [1], because our model and the comparisons are designed to predict all edges, including those that are not semantically meaningful. We instead rely on synthetic data, where the ground truth edges can be determined with perfect precision, and inputs can be controllably noised. Our evaluation data comprises geometric objects and per-pixel additive Gaussian noise with a random variance.

Figure 5 compares the performance and inference time of our method and baselines under different noise levels. The tuneable parameters for Field of Junctions were chosen to maximize its performance on noisy images with 17 × 17 patches. Notably our method’s adaptive windowing function gives it an edge compared to the Field of Junctions at low noise, enabling it to capture finer details, with only slightly worse performance under extreme noise conditions. Our method is also orders of magnitude faster than FoJ, as shown at right.

Qualitative results on real images.

As shown in Figure 6, despite being trained on synthetic data, our method can detect edges in real photographs with multiple levels of real sensor noise present in ELD [24]. Our method produces crisp and well-defined boundaries despite high levels of noise. The supplement includes additional examples that show that our method makes reasonable boundary estimates for other captured images.

Repeatability on real images.

We quantify each method’s noise resilience on real low-light images by measuring the repeatability of its boundaries over a collection of scenes from the ELD dataset. For each scene, we run the model on the lowest-noise image and then measure, via ODS F-score, how much its predictions change with increasing noise level. Figure 6 shows the averages of these scores across the collection. Our model provides more consistent results for increasingly noisy images than other methods, in addition to capturing fine details that other methods miss.

Properties of learned embedding.

We find that our model learns a spatially smooth embedding 𝜸 ∈ ℝ 𝐷 𝛾 of junction space 𝐠 ∈ 𝒢 . In Figure 7 we generate equally-spaced samples 𝜸 𝑖 by linearly interpolating from a particular 𝜸 𝑎 to 𝟎 and then to a particular 𝜸 𝑏 ; and then to each sample we apply the learned embedding to compute and visualize the implied junction 𝐠 𝑖 . We see that the embedding space is smooth, and interestingly, that it learns to associate its zero with nearly-equal angles and a vertex close to the patch center. For visual comparison, we show an analogous geometric interpolation in junction space 𝒢 (see the supplement for expressions) from 𝐠 𝑎 to 𝐠 0 ≜ ( 𝟎 , 0 , 1 / 3 ⋅ 𝟏 ) and then to 𝐠 𝑏 .

Figure 7: Top: Linear interpolation in our network’s learned embedding space ℝ 𝐷 𝛾 from value 𝜸 𝑎 to zero and then to 𝜸 𝑏 . Bottom: A geometric interpolation in junction space 𝐠 ∈ 𝒢 that passes through 𝐠 0

( 𝟎 , 0 , 1 / 3 ⋅ 𝟏 ) . The embedding has learned to be smooth and have an intuitive zero. Figure 8: Evolution of boundaries during iterations, in reading order. Early iterations are exploratory and unstructured, while later iterations feature consistent per-patch boundaries, resulting in clean average boundary maps. NM BA-1 BA-2 Tied ​ Low Noise ↑ ​ Med-Noise ↑ ​ High Noise ↑

✓ ✗ ✗ N/A 0.355

0.189

0.179

✓ ✓ ✗ ✗ 0.837

0.582

0.293

✓ ✓ ✓ ✗ 0.874 0.658

0.327

✓ ✓ ✓ ✓ 0.872 0.673 0.348 Table 1: Ablations: impact of component combinations and weight-tying on F-score (higher is better). Our reported model is boxed. Evolution.

Figure 8 shows an example of how the distance map 𝑑 ¯ ⁢ [ 𝑛 ] evolves during refinement. Specifically, we visualize the result of slicing 𝑏 𝑘 ⁢ ( 𝑥 ; 𝐠 ) , to which we apply a non-linearity that amplifies less-prominent boundaries. We see that early iterations are exploratory and unstructured, and that later iterations agree.

6Ablations

Table 1 shows what happens when the initial per-patch Neighborhood MLP-mixer [NM] is used alone, versus combining it with one boundary attention block [BA-1] or two such blocks [BA-2]. Tying the attention weights across iterations provides a slight advantage at higher noise levels, with only a slight penalty in accuracy at lower noise. Our final model (boxed) provides the best overall performance, accepting slightly lower accuracy at low noise in exchange for better accuracy at higher noise levels.

Table 2 compares many other variations of the boxed model from Tab. 1, with asterisks indicating the model specifications used in the paper. Iterations varies the number of attention-iterations within each block, and Neighborhood varies the attention neighborhood size. MLP Input varies the features concatenated to the hidden state prior to the pre-attention MLP and shows that replacing the gathered colors 𝐟 ¯ 𝑡 with a constant array or the input image values 𝐟 performs worse. Windowing shows that using fixed, square windowing functions 𝑤 𝑛 ⁢ ( 𝑥 ) of any size performs equal (at low noise) or worse than inferring them adaptively. Somewhat intuitively, a small 9 × 9 patch size performs well at low noise, but performance lags under noisy conditions where using a larger patch size increases the spatial extent of the communication across patches.

    ​ Low Noise

↑ ​ Med-Noise ↑ ​ High Noise ↑

Iterations 3 0.867

0.647

0.329

4* 0.872 0.673 0.348 5 0.871

0.663

0.337

Neighborhood 7 × 7

0.869

0.637

0.313

9 × 9

0.871

0.658

0.325

11 × 11

• 0.872	0.673	0.348
  

13 × 13

0.871

0.655

0.324

MLP Input Constant 0.870

0.650

0.317

Input features 0.868

0.657

0.316

Avg. features* 0.872 0.673 0.348 Windowing Fixed 0.872 0.662

0.328

Inferred* 0.872 0.673 0.348 Table 2: Ablations: variations of our reported model. We compare the number of iterations of boundary attention, the attention neighborhood size, the features concatenated to the hidden state as input to the MLP, and a fixed versus learned windowing function. Asterisks indicate our reported choices. 7Conclusion

We have introduced a differentiable model that uses boundary attention to explicitly reason about geometric primitives such as edges, corners, junctions, and regions of uniform appearance in images. Our bottom-up, feedforward network can encode images of any resolution and aspect ratio into a field of geometric primitives that describe the local structure within every patch. This work represents a step to the goal of synergizing the benefits of low-level parametric modeling with the efficiency and representational power of deep learning.

Supplemental Material for Boundary Attention: Learning curves, corners, junctions and grouping

Contents 1Introduction 2Related Work 3Representation 4Network Architecture 5Experiments 6Ablations 7Conclusion S1The space of 𝑀 -junctions S2Training Data S3Model Details S4Model Behavior S5Additional Examples for Low-light Images S6Additional Uses of Our Model S1The space of 𝑀 -junctions

Here we provide the expressions for the support functions 𝑠 𝑗 ⁢ ( 𝑥 ; 𝐠 ) and the unsigned distance function 𝑑 ⁢ ( 𝑥 ; 𝐠 ) from Section 3 of the main paper. We also describe the differences between our parameterization of junction space and the original one in the field of junctions [23], with the new parameterization’s main advantages being the avoidance of singularities and the ability to define mechanisms for smooth interpolation. Our descriptions of these require introducing a few additional mathematical details. We provide these details for the general case of geometric primitives (junctions) 𝐠 that have 𝑀 angular wedges 𝝎

( 𝜔 1 , … , 𝜔 𝑀 ) , for which the paper’s use of 𝑀

3 is a special case.

To begin, consider a local region Ω ⁢ ( 𝑥 ) ⊂ ℝ 2 and fix a positive integer value for the maximum number of angular wedges 𝑀 > 0 (the paper uses 𝑀

3 ). Our partitions are parameterized by 𝐠 ∈ ℝ 2 × 𝕊 1 × △ 𝑀 − 1 , where 𝕊 1 is the unit circle and △ 𝑀 − 1 is the standard ( 𝑀 − 1 ) -simplex (i.e., the set of 𝑀 -vectors whose elements are nonnegative and sum to one). We use the notation 𝐠

( 𝒖 , 𝜃 , 𝝎 ) , where 𝒖

( 𝑢 , 𝑣 ) ∈ ℝ 2 is the vertex, 𝜃 ∈ 𝕊 1 is the orientation, and 𝝎

( 𝜔 1 , 𝜔 2 , … , 𝜔 𝑀 ) are barycentric coordinates (defined up to scale) for the 𝑀 relative angles, ordered clockwise starting from 𝜃 . As noted in the main paper, our convention is to express the vertex coordinates relative to the center of region Ω ⁢ ( 𝑥 ) , and we note again that the vertex is free to move outside of this region. We also note that up to 𝑀 − 1 of the angles 𝜔 𝑗 can be zero. When necessary, we use notation 𝝎 ~

( 𝜔 ~ 1 , 𝜔 ~ 2 , … , 𝜔 ~ 𝑀 ) to represent angles that are normalized for summing to 2 ⁢ 𝜋 :

𝝎 ~

2 ⁢ 𝜋 ⁢ 𝝎 ∑ 𝑗

1 𝑀 𝜔 𝑗 .

(15)

As an aside, we note that there are some equivalences in this parameterization. First, one can perform, for any 𝑘 ∈ { 1 ⁢ … ⁢ ( 𝑀 − 1 ) } , a cyclic permutation of the angles 𝝎 and adjust the orientation 𝜃 without changing the partition. That is, the partition does not change under the cyclic parameter map

𝜔 𝑗

→ 𝜔 𝑗 + 𝑘 ⁢ ( mod ⁢ 𝑀 )

(16)

𝜃
→ 𝜃 − ∑ 𝑗

𝑀 + 1 − 𝑘 𝑀 𝜔 𝑗

(17)

for any 𝑘 ∈ { 1 ⁢ … ⁢ ( 𝑀 − 1 ) } . Also, an 𝑀 -junction ( 𝒖 , 𝜃 , ( 𝜔 1 , … , 𝜔 𝑀 ) ) provides the same partition as any 𝑀 ′ -junction, 𝑀 ′

𝑀 , that has the same vertex and orientation along with angles ( 𝜔 1 ⁢ … ⁢ 𝜔 𝑀 , 0 ⁢ … ) . This captures the fact that 𝑀 -junction families are nested for increasing 𝑀 .

Fig. S1:Anatomy of an 𝑀 -junction 𝐠

( 𝐮 , 𝜃 , 𝝎 ) with 𝑀

3 . Left: Boundary directions 𝜙 𝑗 and central directions 𝜓 𝑗 are determined directly from relative angles 𝝎 and orientation 𝜃 (which is equal to 𝜙 1 ). Middle panels: Unsigned distance function for a boundary ray 𝑑 3 ⁢ ( 𝑥 ; 𝐠 ) and overall unsigned distance function 𝑑 ⁢ ( 𝑥 ; 𝐠 ) , which is the minimum of the three per-ray ones. Right: Associated boundary function 𝑏 𝜂 ⁢ ( 𝑥 ; 𝐠 ) using 𝜂

0.7 .

As shown in Figure S1, other geometric features of a junction can be directly derived from the orientation and angles. The central directions 𝝍

( 𝜓 1 , … , 𝜓 𝑀 ) are

𝜓 𝑗

𝜃 + 𝜔 ~ 𝑗 2 + ∑ 𝑘

1 𝑗 − 1 𝜔 ~ 𝑘 , 𝑗 ∈ { 1 ⁢ … ⁢ 𝑀 } ,

(18)

and the boundary directions 𝜙

( 𝜙 1 , … , 𝜙 𝑀 ) are given by 𝜙 1

𝜃 and

𝜙 𝑗

𝜃 + ∑ 𝑘

1 𝑗 − 1 𝜔 ~ 𝑘 , 𝑗 ∈ { 2 ⁢ … ⁢ 𝑀 } .

(19)

A key difference between our new parameterization of 𝑀 -junctions and the original one [23] is that the latter comprises ( 𝒖 , 𝜙 ) and requires enforcing constraints 0 ≤ 𝜙 1 ≤ 𝜙 2 ≤ ⋯ ≤ 𝜙 𝑀 ≤ 2 ⁢ 𝜋 (or somehow keeping track of the permutations of wedge indices that occur when these constraints are not enforced). The new ( 𝒖 , 𝜃 , 𝝎 ) -parameterization eliminates the need for such constraints.

As noted in the main paper’s Section 3, we define the 𝑗 th support 𝑠 𝑗 ⁢ ( 𝑥 ; 𝐠 ) as the binary-valued function that indicates whether each point 𝑥 ∈ Ω is contained within wedge 𝑗 ∈ { 1 ⁢ … , 𝑀 } . Its expression derives from the inclusion condition that the dot product between the vector from the vertex to 𝑥 and the 𝑗 th central vector ( cos ⁡ 𝜓 𝑗 , sin ⁡ 𝜓 𝑗 ) must be smaller than the cosine of half the angle 𝜔 ~ 𝑗 . Using Heaviside function 𝐻 ⁢ ( ⋅ ) we write

𝑠 𝑗 ⁢ ( 𝑥 ; 𝐠 )

𝐻 ⁢ ( ( 𝑥 − 𝐮 ) ⋅ ( cos ⁡ 𝜓 𝑗 , sin ⁡ 𝜓 𝑗 ) − cos ⁡ ( 𝜔 ~ 𝑗 / 2 ) ⁢ ‖ 𝑥 − 𝐮 ‖ ) .

(20)

As an aside, observe that this expression remains consistent for the case 𝑀

1 , where there is a single wedge. In this case, 𝝎 ~

𝜔 ~ 1

2 ⁢ 𝜋 by Equation 15, and the support reduces to 𝑠 1 ⁢ ( 𝑥 )

1 for all vertex and orientation values.

The unsigned distance 𝑑 ⁢ ( 𝑥 ; 𝐠 ) represents the Euclidean distance from point 𝑥 to the nearest point in the boundary set defined by 𝐠 . It is the minimum over 𝑀 sub-functions, with each sub-function being the unsigned distance from a boundary ray that extends from point 𝐮 in direction 𝜙 𝑗 . The unsigned distance from the 𝑗 th boundary ray is equal to the distance from its associated line for all points 𝑥 in its containing half-plane; and for other points it is equal to the radial distance from the vertex. That is,

𝑑 𝑗 ⁢ ( 𝑥 ; 𝐠 )

{ | ( 𝑥 − 𝐮 ) ⋅ ( − sin ⁡ 𝜙 𝑗 , cos ⁡ 𝜙 𝑗 ) | ,

if  ⁢ ( 𝑥 − 𝐮 ) ⋅ ( cos ⁡ 𝜙 𝑗 , sin ⁡ 𝜙 𝑗 )

0

‖ ( 𝑥 − 𝐮 ) ‖ ,

otherwise .

(21)

Then, the overall distance function is

𝑑 ⁢ ( 𝑥 ; 𝐠 )

min 𝑗 ∈ 1 ⁢ … ⁢ 𝑀 ⁡ 𝑑 𝑗 ⁢ ( 𝑥 ; 𝐠 ) .

(22)

Finally, analogous to Equation 7 in the main paper, we define a junction’s boundary function 𝑏 𝜂 ⁢ ( 𝑥 ; 𝐠 ) as the result of applying a univariate nonlinearity to the unsigned distance:

𝑏 𝜂 ⁢ ( 𝑥 ; 𝐠 )

( 1 + ( 𝑑 ⁢ ( 𝑥 ; 𝐠 ) / 𝜂 ) 2 ) − 1 .

(23)

Figure S1 shows an example of a junction’s distance function and its associated boundary function with 𝜂

0.7 .

S1.1 Interpolation

Another advantage of the present parameterization compared to that of the original [23] is that it is a simply-connected topological space and so allows for defining mechanisms for smoothly interpolating between any two junctions 𝐠

( 𝒖 , 𝜃 , 𝝎 ) and 𝐠 ′

( 𝒖 ′ , 𝜃 ′ , 𝝎 ′ ) . In our implementation we define interpolation variable 𝑡 ∈ [ 0 , 1 ] and compute interpolated junctions 𝐠 ⁢ ( 𝑡 )

{ 𝒖 ⁢ ( 𝑡 ) , 𝜃 ⁢ ( 𝑡 ) , 𝝎 ⁢ ( 𝑡 ) } using a simple combination of linear and spherical linear interpolation:

𝒖 ⁢ ( 𝑡 )

( 1 − 𝑡 ) ⁢ 𝒖 + 𝑡 ⁢ 𝒖 ′

(24)

𝝎 ~ ⁢ ( 𝑡 )

( 1 − 𝑡 ) ⁢ 𝝎 ~ + 𝑡 ⁢ 𝝎 ~ ′ ,

(25)

and

𝜃 ⁢ ( 𝑡 )

𝜃 + 𝑡 ⁢ Δ ⁢ 𝜃 ,

(26)

with

Δ ⁢ 𝜃

{ 𝜃 ′ − 𝜃 − 2 ⁢ 𝜋 ,

if  ⁢ 𝜃 ′ − 𝜃

𝜋

𝜃 ′ − 𝜃 + 2 ⁢ 𝜋 ,

if  ⁢ 𝜃 ′ − 𝜃 < − 𝜋

𝜃 ′ − 𝜃 ,

otherwise ,

assuming 𝜃 , 𝜃 ′ ∈ [ 0 , 2 ⁢ 𝜋 ) . The bottom row of Figure 7 in the main paper visualizes a set of samples from smooth trajectories in junction space using this mechanism.

S2Training Data Fig. S2: Columns 1 to 5: Examples of the synthetic data used to train our model using supervision with ground-truth boundaries. Column 6: Rendered distance maps corresponding to column 5. The training data contains random circles and triangles that each have a random RGB color, and the images are corrupted by various types and amounts of noise. Each noiseless image has an unrasterized, vector-graphics representation of its shapes and colors, which specify the clean image and exact boundary-distance map with unlimited resolution.

We find that we can train our model to a useful state using purely synthetic data, examples of which are depicted in Figure S2. In fact, we find it sufficient to use very simple synthetic data that consists of only two basic shapes—circles and triangles—because these can already produce a diverse set of local edges, thin bars, curves, corners, and junctions, in addition to uniform regions. We generate an image by randomly sampling a set of circles and triangles with geometric parameters expressed in continuous, normalized image coordinates [ 0 , 1 ] × [ 0 , 1 ] . We then choose a random depth ordering of the shapes, and we choose a random RGB color for each shape. Importantly, the shape and color elements are specified using a vector-graphics representation, and the shape elements are simple enough to provide an exact, symbolic expression for each image’s true boundary-distance map, without approximation or rasterization. They also allow calculating the precise locations, up to machine precision, for all of the visible corners and junctions in each image.

At training time, an input image is rasterized and then corrupted by a random amount and type of noise, including some types of noise that are spatially-correlated. This forces our model to only use color as its local cues for boundaries and grouping; and it forces it to rely heavily on the topological and geometric structure of curves, corners and junctions, as well as their contrast polarities. The highly-varying types and amounts of noise also encourages the model to use large window functions 𝑤 ⁢ ( 𝑥 ; 𝐠 ) when possible, since that reduces noise in the gather operation and reduces variance 𝜈 𝑓 ⁢ [ 𝑛 ] .

Our dataset, which we call Kaleidoshapes, is available publicly, along with the code for generation, training and evaluation.

Shapes and colors. For our experiments, we rasterized each image and its true distance map at a resolution of 240 × 320 images, with each one containing between 15 and 20 shapes. We used a 40 : 60 ratio of circles to triangles. In terms of normalized coordinates, circles had radii in the range [ 0.05 , 0.2 ] and triangles had bases in the range [ 0.02 , 0.5 ] and heights in the range [ 0.05 , 0.3 ] . This allows triangles to be quite thin, so that some of the local regions Ω ⁢ ( 𝑥 ) contain thin bar-like structures. Additionally, we included a minimum visibility threshold, filtering out any shapes whose visible number of rasterized pixels is below a threshold. Colors were selected by uniformly sampling all valid RGB colors. During training, batches consisted of random 125 × 125 crops.

Noise. For noise types, we used combinations of additive zero-mean Gaussian noise; spatially average-pooled Gaussian noise; Perlin noise [16], and simulated photographic sensor noise using the simplified model from [24]. The total noise added to each image was sampled uniformly to be between 30% and 80% of the maximum pixel magnitude, and then noise-types were randomly combined with associated levels so that they produced the total noise level. Since zero-mean noise can at times result in values below 0 or above the maximum magnitude threshold, we truncate any pixels outside of that range.

S3Model Details

Our model is designed to be purely local and bottom up, with all of its compositional elements operating on spatial neighborhoods in a manner that is invariant to discrete spatial shifts of an image. Its design also prioritizes having a small number of learnable parameters. Here we provide the details of the two blue blocks in the main paper’s Figure 3: Neighborhood MLP-Mixer and Neighborhood Cross-attention. Our model was implemented with JAX and its code and trained weights are available publicly.

S3.1 Neighborhood MLP-Mixer

Our neighborhood MLP-mixer is a shift invariant, patch-based network inspired by MLP-mixer [22]. It replaces the image-wide operations of [22] with patch-wise ones. Given an input image, we first linearly project its pixels from ℝ 3 to dimension ℝ 𝐷 𝛾 (we use 𝐷 𝛾

64 ), which is followed by two neighborhood mixing blocks. Each neighborhood mixing block contains a spatial patch mixer followed by a channel mixer. The spatial patch mixer is implemented as two 3 × 3 spatial convolutions with weights tied across channels. It thereby combines spatial patches of features with all channels (and patches) sharing the same weights. Following [22], we use GELU [11] activations. The channel mixer is a per-pixel MLP with spatially-tied weights. To handle border effects in our neighborhood MLP-mixer, we apply zero-padding after the initial projection from ℝ 3 to ℝ 64 , and then we crop to the input image size after the second neighborhood mixing block to remove features that correspond to patches without full coverage, i.e., patches that contain pixels outside of the original image.

S3.2 Neighborhood Cross-attention

The neighborhood cross-attention block similarly enforces shift-invariance and weight sharing across spatial neighborhoods. Inside this block are two transformer layers whose cross-attention components are replaced with neighborhood cross-attention components that are restricted to a spatial neighborhood of pixels. We use 11 × 11 neighborhoods in our implementation, which our ablations showed produced the best performance. In each neighborhood containing a query token, we add a learned positional encoding to the key/value tokens which is relative to the neighborhood’s center and is the same for all neighborhoods. Then the query is updated using standard cross-attention with its neighborhood of key/values. We use 4 cross-attention heads. Like the standard transformer, each neighborhood cross attention component is followed by an MLP, dropout layer, and additive residual. To handle border effects, we zero-pad the key and value tokens so that every query attends to an 11 × 11 neighborhood, and then zero-out any attention weights involving zero-padded tokens.

S3.3 Training Details

During the first two stages of training where we train our model on junction images and simplified circle triangle images, we omit the global losses of Equations  9 and 10 . This primes the network to learn meaningful hidden states 𝜸 ⁢ [ 𝑛 ] and prevents the “collapsing” of junctions, where the boundary-consistency loss (i.e. the sum over pixels of variance of distance 𝜈 𝑑 ⁢ [ 𝑛 ] ) dominates and the network learns to predict all-boundaryless patches that are globally consistent but inaccurate. Because of data imbalance—only a small fraction of regions Ω 𝑛 ⁢ ( 𝑥 ) contain corners or junctions—we add an additional spatial importance mask to prioritize the regions that contain a corner (i.e., a visible triangle vertex) or a junction (i.e., an intersection between a circle and a triangle’s edge). Our data generation process produces a list of all non-occluded vertices and intersections in each image, and we use these values to create a spatial importance mask with gaussians centered at each of these points. In practice, we use gaussians with a standard deviation of 7 pixels. This mask is added to the loss constant 𝐶 .

The final stage of training adds a second boundary attention block with weights that are initialized using a copy of the pretrained weights of the first boundary attention block. We use 100 ⁢ 𝑘 crops of size 125 × 125 from our Kaleidoshape images (10% withheld for testing) and the full set of losses; and we optimize all of the model’s parameters, including those of the neighborhood MLP-mixer and the first boundary attention block. Like in pretraining, we add a spatial importance that prioritizes region containing a corner (i.e., a visible triangle vertex) or a junction (i.e., a visible intersection between the boundaries of any two shapes).

S4Model Behavior S4.1 Qualitative Results for Natural Images Fig. S3: Qualitative behavior of our model’s output boundaries 𝑏 ¯ 𝜂 ⁢ [ 𝑛 ] on noiseless natural images, compared to those of end-to-end models EDTER [18] and Pidinet [21] that are trained to match human annotations; and compared to two bottom-up methods that, like our model, are not trained to match human annotations: Canny [2], and the field of junctions (FoJ) [23] with patch size 11 .

In Figures S4 and S3, we show how the model behaves on noiseless natural images that contain texture and recognizable objects. In particular, Figure S3 emphasizes how the boundary maps produced by our model qualitatively differ from other methods. Here, in addition to showing the results those of classical bottom-up edge-detectors, we include results learned, end-to-end models that have been trained to match human annotations as another point of reference. It is important to remember that these methods are trained to identify boundary structures that are defined by semantic variations, whereas our method and other low-level methods divide regions based on variations in color.

Figure  S3 compares our output to that from Canny [2], the field of junctions (FoJ) [23] with a patch size of 11 , Pidinet [21], and EDTER [18], the latter two being networks trained on human annotated data. (Note that inputs for all models besides EDTER [18] were 300 × 400 . Input to EDTER was down-sampled to 225 × 300 due to its input size constraint.)

We find that our model produces finer structures than the end-to-end learned models [6, 18] because it is trained to only use local spatial averages of color as its cue for boundaries and grouping. It does not include mechanisms for grouping based on local texture statistics, nor based on non-local shape and appearance patterns that have semantic meaning to humans. Compared to the bottom-up methods of Canny [2] and the field of junctions [23], our model has the advantage of automatically adapting the sizes of its output structures across the image plane, through its prediction of windowing field 𝐩 ⁢ [ 𝑘 ] . In contrast, the the field of junctions and Canny both operate at a single pre-determined choice of local size, so they tend to oversegment some places while undersegmenting others.

Fig. S4: Qualitative behavior of our model on noiseless natural images. From left to right: Input image 𝐟 ⁢ [ 𝑛 ] , output distance map 𝑑 ¯ ⁢ [ 𝑛 ] , output boundary map 𝑏 ¯ ⁢ [ 𝑛 ] , and output boundary-smoothed features 𝐟 ¯ ⁢ [ 𝑛 ] . S5Additional Examples for Low-light Images

Figure S5 shows examples of applying our model to indoor images taken by an iPhone XS in low light conditions.

Figure S6 provides additional comparisons for a sample of varying-noise images from the ELD dataset [24]. We include results from other low level methods and as a point of comparison, the outputs of several methods trained to parse semantic boundaries.

When detecting boundaries at low signal-to-noise ratios, it is difficult to accurately discern finer structures as the noise level increases. Some algorithms, such as the field of junctions (FoJ) [23], have tunable parameters such as patch-size that provide control over the level of detection. A small patchsize allows recovering fine structures in lower noise situations, but it causes many false positive boundaries at high noise levels. Conversely, a large patchsize provides more resilience to noise but has not ability to recover fine structure at all. Our model reduces the severity of this trade-off by automatically adapting its local windowing functions in ways that have learned to account for both the amount of noise and the local geometry of the underlying boundaries.

In Figure S6 we see that our model is able to capture the double-contour shape of the curved, thin black bars, and that it continues to resolve them as the noise level increases, more than the other low-level methods. We also note that only the low-level models resolve this level of detail in the first place: The models trained on human annotations—UAED [27], EDTER, HED, Pidinet, and Structured Forests—miss the double contour entirely, estimating instead a single thick curve. We emphasize again that a user can adjust the behavior of Canny and the field of junctions by tuning their local size parameters, either the filter size for Canny or the patchsize for the field of junctions. Increasing the local size improves their resilience to noise but reduces their spatial precision. Neither system provides the ability to estimate fine grained details and withstand noise, like our model does.

Figure S7 contains additional examples of images cropped from the ELD dataset. Here we include examples with even higher levels of noise to show the complete degradation of our algorithm and others.

Fig. S5: Visualization of our model’s output for low-light images captured by an iPhone XS. From left to right: Input image 𝐟 ⁢ [ 𝑛 ] , output distance map 𝑑 ¯ ⁢ [ 𝑛 ] , output boundary map 𝑏 ¯ 𝜂 ⁢ [ 𝑛 ] with 𝜂

0.7 , and output boundary-smoothed features 𝐟 ¯ ⁢ [ 𝑛 ] . Fig. S6: Qualitative comparison between our model’s output boundaries 𝑏 ¯ 𝜂 ⁢ [ 𝑛 ] and those of other methods, for a crop from the ELD dataset under increasing amounts of photographic noise. We compare to end-to-end models that are trained to match human annotations (UAED [27], EDTER [18], HED [25], Pidinet [21], and Structured Edges (SE) [6]) in addition to low-level models that are not (Canny [2], gPb [13], and the field of junctions (FoJ-17) [23]) with patch size 17. Fig. S7: Fig. S7: (cont.) Fig. S7: (cont.) Fig. S7: (cont.) Additional qualitative comparisons between our model’s output boundaries 𝑏 ¯ 𝜂 ⁢ [ 𝑛 ] and those of other methods, using crops from the ELD dataset under increasing amounts of photographic noise, including very high levels of noise. S6Additional Uses of Our Model

Here we demonstrate to uses of our model that follow directly from its output: hole-filling in RGBD images and non-photorealistic stylization.

S6.1 Color-based Depth Completion

Figure S8 shows an example of using our model for simple hole-filling in the depth channels of RGBD images from the Middlebury Stereo Datasets [19, 20]. We run our model on the RGB channels, and then for each pixel 𝑛 that has a missing depth value, we use our model’s output local attention kernels 𝑎 𝑛 ⁢ ( 𝑥 ) to fill in that pixel’s value using an attention-weighted average of the observed depth values around it. This simple algorithm can be applied whenever the hole sizes are smaller than the maximum diameter of our attention maps, which is 34 × 34 in our current implementation).

Fig. S8: Using our model for depth completion in RGBD images. Left: Input RGB channels. Middle: Input depth channel, with dark blue indicating missing values. Right: Completed depth using our model’s output attention kernels. S6.2 Application: Photo Stylization

Figure S9 shows examples of using our model’s output for image stylization, by superimposing an inverted copy of the output boundary map 𝑏 ¯ 𝜂 ⁢ [ 𝑛 ] onto the smoothed colors 𝐟 ¯ ⁢ [ 𝑛 ] .

Fig. S9: Examples of stylized natural photographs, created by imposing our method’s output boundary map onto the output smoothed colors. References [1] ↑ Arbelaez, P., Maire, M., Fowlkes, C., Malik, J.: Contour detection and hierarchical image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 33(5), 898–916 (2010) [2] ↑ Canny, J.: A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. (6), 679–698 (1986) [3] ↑ Catmull, E.E.: A subdivision algorithm for computer display of curved surfaces. The University of Utah (1974) [4] ↑ Concetta Morrone, M., Burr, D.: Feature detection in human vision: A phase-dependent energy model. Proc. Royal Soc. B 235(1280), 221–245 (1988) [5] ↑ Dollar, P., Tu, Z., Belongie, S.: Supervised learning of edges and object boundaries. In: IEEE Conf. Comput. Vis. Pattern Recog. vol. 2, pp. 1964–1971 (2006) [6] ↑ Dollár, P., Zitnick, C.L.: Fast edge detection using structured forests. IEEE Trans. Pattern Anal. Mach. Intell. 37(8), 1558–1570 (2014) [7] ↑ Foley, J.D., Van Dam, A.: Fundamentals of interactive computer graphics. Addison-Wesley Longman Publishing Co., Inc. (1982) [8] ↑ Freeman, W.T.: Steerable filters and local analysis of image structure. Ph.D. thesis, Massachusetts Institute of Technology (1992) [9] ↑ Freeman, W.T., Adelson, E.H.: The design and use of steerable filters. IEEE Trans. Pattern Anal. Mach. Intell. 13(9), 891–906 (1991) [10] ↑ Heckbert, P.S.: Fundamentals of texture mapping and image warping. Citeseer (1989) [11] ↑ Hendrycks, D., Gimpel, K.: Bridging nonlinearities and stochastic regularizers with gaussian error linear units. CoRR abs/1606.08415 (2016), http://arxiv.org/abs/1606.08415 [12] ↑ Lim, J.J., Zitnick, C.L., Dollár, P.: Sketch tokens: A learned mid-level representation for contour and object detection. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 3158–3165 (2013) [13] ↑ Maire, M., Arbelaez, P., Fowlkes, C., Malik, J.: Using contours to detect and localize junctions in natural images. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 1–8 (2008) [14] ↑ Martin, D.R., Fowlkes, C.C., Malik, J.: Learning to detect natural image boundaries using local brightness, color, and texture cues. IEEE Trans. Pattern Anal. Mach. Intell. 26(5), 530–549 (2004) [15] ↑ Parent, P., Zucker, S.W.: Trace inference, curvature consistency, and curve detection. IEEE Trans. Pattern Anal. Mach. Intell. 11(8), 823–839 (1989) [16] ↑ Perlin, K.: An image synthesizer. ACM Siggraph Computer Graphics 19(3), 287–296 (1985) [17] ↑ Pineda, J.: A parallel algorithm for polygon rasterization. In: Proceedings of the ACM on Computer Graphics and Interactive Techniques. pp. 17–20 (1988) [18] ↑ Pu, M., Huang, Y., Liu, Y., Guan, Q., Ling, H.: EDTER: Edge detection with transformer. In: IEEE Conf. Comput. Vis. Pattern Recog. (2022) [19] ↑ Scharstein, D., Szeliski, R.: High-accuracy stereo depth maps using structured light. In: 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. vol. 1, pp. I–I (2003). https://doi.org/10.1109/CVPR.2003.1211354 [20] ↑ Scharstein, D., Pal, C.: Learning conditional random fields for stereo. In: 2007 IEEE Conference on Computer Vision and Pattern Recognition. pp. 1–8 (2007). https://doi.org/10.1109/CVPR.2007.383191 [21] ↑ Su, Z., Liu, W., Yu, Z., Hu, D., Liao, Q., Tian, Q., Pietikäinen, M., Liu, L.: Pixel difference networks for efficient edge detection. In: Proceedings of the IEEE/CVF international conference on computer vision. pp. 5117–5127 (2021) [22] ↑ Tolstikhin, I.O., Houlsby, N., Kolesnikov, A., Beyer, L., Zhai, X., Unterthiner, T., Yung, J., Steiner, A., Keysers, D., Uszkoreit, J., et al.: MLP-Mixer: An all-MLP architecture for vision. Adv. Neural Inform. Process. Syst. 34, 24261–24272 (2021) [23] ↑ Verbin, D., Zickler, T.: Field of junctions: Extracting boundary structure at low SNR. In: Int. Conf. Comput. Vis. (2021) [24] ↑ Wei, K., Fu, Y., Yang, J., Huang, H.: A physics-based noise formation model for extreme low-light raw denoising. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 2758–2767 (2020) [25] ↑ Xie, S., Tu, Z.: Holistically-nested edge detection. In: Int. Conf. Comput. Vis. pp. 1395–1403 (2015) [26] ↑ Ye, Y., Xu, K., Huang, Y., Yi, R., Cai, Z.: Diffusionedge: Diffusion probabilistic model for crisp edge detection (2024), https://arxiv.org/abs/2401.02032 [27] ↑ Zhou, C., Huang, Y., Pu, M., Guan, Q., Huang, L., Ling, H.: The treasure beneath multiple annotations: An uncertainty-aware edge detector. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 15507–15517 (2023) Report Issue Report Issue for Selection Generated by L A T E xml Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.

Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.