Soft Superpixel Neighborhood Attention
Authors: Kent Gauen
Stanley H. Chan
Venue: NeurIPS 2024 poster (2024)
Keywords: attention module
superpixels
image denoising
deep learning
Primary area: machine_vision
TL;DR: This paper proposes a novel deep learning attention module, named soft superpixel neighborhood attention (SNA), to reweight a local attention map according to the deformable boundaries of real-world images.

Abstract: Images contain objects with deformable boundaries, such as the contours of a human face, yet attention operators act on square windows. This mixes features from perceptually unrelated regions, which can degrade the quality of a denoiser. One can exclude pixels using an estimate of perceptual groupings, such as superpixels, but the naive use of superpixels can be theoretically and empirically worse than standard attention. Using superpixel probabilities rather than superpixel assignments, this paper proposes soft superpixel neighborhood attention (SNA), which interpolates between the existing neighborhood attention and the naive superpixel neighborhood attention. This paper presents theoretical results showing SNA is the optimal denoiser under a latent superpixel model. SNA outperforms alternative local attention modules on image denoising, and we compare the superpixels learned from denoising with those learned with supervision.

Soft Superpixel Neighborhood Attention
Kent Gauen Purdue University gauenk@purdue. edu
Stanley Chan Purdue University stanchanGpurdue. edu
Abstract
Images contain objects with deformable boundaries, such the contours of hu- man face, yet attention operators act on square windows. This mixes features from perceptually unrelated regions, which can degrade the quality of denoiser. One can exclude pixels using an estimate of perceptual groupings, such as superpixels, but the naive use of superpixels can be theoretically and empirically worse than standard attention. Using superpixel probabilities rather than superpixel assign- ments, this paper proposes soft superpixel neighborhood attention (SNA) which interpolates between the existing neighborhood attention and the naive superpixel neighborhood attention. This paper presents theoretical results showing SNA is the optimal denoiser under a latent superpixel model. SNA outperforms alternative lo- cal attention modules on image denoising, and we compare the superpixels learned from denoising with those learned with superpixel supervision
Introduction
The attention mechanism is attributed meaningful benchmark improvements in deep neural networks []]. While the initial attention mechanism acted globally, recent methods operate local neighborhoods, which requires less computation and reduces the chance of learning spurious correlations [2]. Neighborhood attention (NA) transforms each pixel using its surrounding square neighborhood of pixels. In reality, this square neighborhood is merely an implementation convenience. Natural images contain objects with non-rigid boundaries, such as the contours of human face the outlines of text. To account for these deformations, this paper proposes a new local attention module that re-weights the attention map according low-level perceptual groups, or "superpixels" 3) named soft superpixel neighborhood attention (SNA).
Theory from vision science posits that humans view scenes according to perceptual groups (e.g. Gestalt principles) 4 Superpixels are one such formulation of perceptual groupings, and they create deformable, boundary-preserving segmentation of image 3. Since deep learning models can learn spurious correlations, operations that utilize perceptual groups should principally help a network learn desirable correlations. Despite the deformable neighborhood shapes, applying attention with superpixel estimate is straightforward. However, this naive approach is theoretically worse than NA for some superpixel shapes and sensitive to errors in the superpixel estimate. To address these issues, we propose thinking beyond using a single superpixel estimate.
While recent works use the maximum likelihood (ML) superpixel estimate 6 7. many superpixel formations are equally likely. [ three samples from a (slightly modified) recent BASS superpixel model [5). Many of the boundaries seem arbitrary and change among the samples, while some remain fixed. No single superpixel segmentation the absolute "best". This not a deficiency of the particular method to estimate superpixels, but rather drawback of using a point estimate.
!Code for this project is available at utlhtps:/// /ttp//ggttttb.tt/ hott///auen/spix_paap Forr educational value, hyperparameters are modified to create more boundaries.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Original Image
Three Superpixel Estimates
Different Superpixels
Similar Superpixels
Figure I: The Ambiguity of Superpixels. This figure compares three superpixel estimates from recent method named BASS. [5 While three samples achieve a similar segmentation quality, some regions are different, and some almost identical. Since no single segmentation is the "best", this suggests that superpixel assignments are not as important as superpixel probabilities.
This paper presents theoretically grounded approach to account for the ambiguity of superpixel assignments within an attention module. We consider this ambiguity in our derivation by re-weighting the empirical data distribution with superpixel probabilities. While standard superpixel models assume a fixed prior probability, this paper supposes each pixel has a separate prior superpixel probability. Under this new model, find the optimal denoiser is the proposed SNA module.
Contributions. In summary, this paper presents a rigorous way to incorporate superpixels into an attention module. By modeling image pixels with distinct superpixel probabilities, we find the soft superpixel neighborhood attention (SNA) module the optimal denoiser. We empirically show the SNA module outperforms NA within single-layer denoising network by 1 - dB PSNR. We compare the superpixels learned for denoising with superpixels learned using supervised training [
2 Related Works
Non-Local Methods, Classical image restoration methods transform a pixel using its neighborhood based on pairwise similarities [9]1]. Some early deep learning models incorporate non-local modules with deep learning models for image restoration [2 Once attention was introduced to the computer vision community, later methods drew analogies between attention and non-local methods 20)
Attention. While attention modules followed the same form non-local methods, they were origi- nally presented as a disconnected idea [ 21). Attention's primary issuc was originally computation, and subsequent research efforts proposed efficient alternatives 222 2 These alternatives often compute attention across smaller region, and use a deep network's 's depth to disperse information globally. Neighborhood attention (NA) is implemented with efficient, custom CUDA kernel to search a square window and is among the fastest methods [2]. The square window is theoretically
more desirable than asymmetrical alternatives, such as SWIN 22
Superpixels. Superpixels embody the concept of perceptual groupings, which suggests that humans first group smaller objects together and then aggregate this information to understand the whole image [3]. There are many methods to model these superpixels 226 27]. SLIC is a state-of- state-of-the-ar,, classical superpixel method and is explained in Section 3.1 226.. Superpixels have been applied extensively outside of deep learning literature [28-22] Superpixels have not been employed as widely since the advent of deep learning, but recent methods have started incorporating them 66 7]. A recent method, referred to as the superpixel sampling network (SSN), presents a supervised learning method
to sample using segmentation labels (8) The loss function of SSN is related to the idea of superpixel
pooling, which we use to evaluate superpixel probabilities in Section 5.3 B3 34].
The derivation of the optimal denoiser using latent superpixels closely resembles the problem of mixtur-haased parameemerrii density estimation (35). This paper does not address important statistical issues, such as identifiability.
Non-Parametric Density Estimation.

---

Image
Image
Superpixel Means (Centroids)
H
Superpbxl Center
H
H/S.
Sep
W/S
w
W
Figure 2: Each Pixel is Connected to Nine Superpixels. This figure illustrates the anatomy of the SLIC superpixels. The left-most figure illustrates how superpixels are conceptually distributed across grid on the input image with stride Spp The right figure illustrates a single pixel is connected to (at most) nine centroids.
Preliminaries
3.1 SLIC Superpixels
In this paper, an image (œ) has height (H), width (W), and features (F) with shape HW x F.
Conceptually, superpixels evenly spaced across the image according the stride denoted S.p- The superpixel stride (Sxp) determines the number of superpixels, S HW/ (see Fig 2b. SLIC superpixels consist of superpixel means (fi with shape $ x F), intra-superpixel precision (r) (rpp Mstuee] with shape S x 2), the probability each pixel belongs to each superpixel (#r with shape HW x S), and the superpixel assigned to each pixel (& with shape HW)). SLIC estimates these quantities using Lloyd's s algorithm (similar to k-means) [6]] Following recent works, each pixel connected to at most nine superpixels (
Presently, we describe how SLIC superpixel probabilities are computed. Let the distances between pixels and superpixel means be written matrix D of shape HW S and let ((t.)) ||a: |4, 11 if the two are connected and infinity otherwise. difference between the indices is written D (1.*) i ky]
[8 sy]1l Superpixel probabilities are computed as,
+ = a a:p ( sha B(0))
where app shape > 0 enforce consistency across appearance (app) and shape. The estimated superpixel probabilities are the conditional probability pixel is assigned to superpixel p(s; s|æ::) (1.e), A superpixel segmentation (&) is formed by assigning each pixel's cluster label to their most similar superpixel; & arg max, (1.2), These quantities are estimates (note the hats) of latent parameters, which is modeling assumption discussed in Section
3.2 Superpixel Pooling
The attention module proposed in this paper will learn superpixel probabilities, but standard superpixel evaluation only considers a point estimate. To augment the standard superpixel benchmarks, we follow recent works and compare superpixel probabilities with superpixel pooling & 5 34
matrix has
size HWV> x C' for C segmentation classes, and superpixel probabilities (#) have size HW x S. Then, HW
the probabilities are re- re-normalized, (1,s) = ((.+)) / Ej=1 ((i+), Finally, the superpixel pooling operation is written.
Exp Sop-pooled = Í
In this paper, the vector z is either an image (C F is the number of channels) segmentation label. A recent method, named the Superpixel Sampling Network (SSN), proposes learning task- specific superpixels with this superpixel pooling loss [ Their loss function trains network to estimate superpixel probabilities by comparing the original and pooled vectors. In Section compare the quality of superpixels learned within an SNA-denoising network and those learned using the SSN loss on the BSD500 dataset (36).
5.3) 5.3 we
3

---

Nelghbbrroood Attention (NA)
Hard Superpixel Neighbarhood Attention (H-SNA)
Soft Superpixel Nei Neighborhood Attention (SNA)
Figure 3: Superpixel Neighborhood Attention, The yellow region represents the attention window and the red contours are superpixel boundary. NA considers all pixels, mixing the dissimilar orange and blue pixels. H-SNA considers only pixels within its superpixel, which is too few pixels for denoising. SNA excludes the dissimilar blue pixels but retains the similar orange pixels.
3.3 Neighborhood Attention
Let noisy input image be denoted with shape HW F. The queries (q), keys (k),, and values (v) project the image æ from dimension F to D, written as x W q. k x W Neighborhood attention (NA) computes the output of the attention operator using pixels within square neighborhood around pixel denoted N [2]. A standard neighborhood of size 7 x is among the fastest available attention methods. The attention scale controls the shape the attention weights, Am 2 0. The output and attention weights are computed below,
x W.. e.
exp (Aard (K,)))))))) EyeN() exp (Aar( k.y)))
(x) = E Wi xx
Wh
JEN(()
As an additional baseline, this paper augments the standard NA by learning the attention parameter for each pixel. Specifically, each pixel's attention scale is the output of deep network, X Further details are described in Section
Dos (z)).
Approach
4.1 Superpixel Neighborhood Attention
Hard Superpixel Neighborhood Attention (H-SNA), Perceptual groupings, such as superpixels, segment pixels into boundary-preserving partition of the image. These boundaries account for sharp changes in pixel intensity, so using these segmentations as masks can remove perceptually unrelated information. Supplemental Section A.2 formalizes this intuition. H-SNA is naive implementation of this concept. For fixed query pixel (t), a neighboring pixel ( is masked its estimated superpixel does not match the query's superpixel, & + 8y. The function written as,
[ = 8,] exp (Am k;)) Wi.i EveN( [[ = 854 eepp (Aail kz))
( (x; = Σ Di
(4)
JEV(()
Soft Superpixel Neighborhood Attention (SNA). There are two problems with H-SNA. First, H-SNA is unstable when the number of pixels sharing the same superpixel label within the local neighborhood small. Examples include snake-like tendrils and superpixels that consist of small, disconnected regions (see Section A.2). The second problem with H-SNA is its high sensitivity to improper superpixel estimation. Erroneous ML estimates superpixels have a dramatic effect on quality. To mitigate both issues, propose soft superpixel neighborhood attention (SNA), which uses superpixel probabilities instead of superpixel assignments,
exp (Am dq. k2)) ES (1.s)) (1.s)
(1) SNA (z:; 7)
Σ (EN(()
Wi.
Wi.j Everio exp (Dael k;))) Ege A (1')))
(5)

---

Figure 4: The Latent Superpixel Model. The latent superpixel model assumes superpixel probabilities are sampled for each image pixel. This figure illustrates the sata-geenrating process. The leftmost image al- lows the reader to visually compare the similarities among superpixels by representing each pixel by its most likely superpixel means, Informally, this looks like a "low-resolution image". The superpixels and image pixels are sampled as usual.
π r p(T)
Si (a)(
X ~ p(x(s)
Step 1
Step 2
Step 3
Importantly, the sum over all superpixels contains only 9 non-zero terms (see Section 3.1 The shape of the superpixel probabilities allows SNA interpolate between NA and H-SNA. To be specific, the superpixel probabilities may be flat to match NA, (6,s) 9. or the superpixel may be sharp to match H-SNA, (6.s) = 1 = s*]. This control over the shape of the superpixel probabilities allows SNA to be better than both H-SNA and NA average.
4.2 The Latent Superpixel Model
Properly incorporating superpixels into attention requires rethinking the relationship between super- pixels and images. While superpixels are usually presented with a generative model for images, this model is used only to estimate superpixel assignments. In contrast, this paper uses the data-generating process itself to derive the form of our proposed attention module. Our process is slightly different from standard literature. Ordinarily, all pixels share single prior superpixel probability. In this paper, the superpixel probabilities are sampled for each image pixel.
For each image pixel, our generative model samples (I) superpixel probabilities π ~ p(T), (2) superpixel assignments ~ pT ( (+)), and (3) pixel values æ| p(x(s). 4 illustrates this proposed latent variable model. Note that SLIC estimated these quantities (recall the hats: 8, #). but assumes different data generating model. While the distribution of pixels given the superpixel assignments unknown, the new model is useful for theoretical analysis. We use to derive the form of our proposed attention module (Sec 4.3) and to compare the theoretical error between SNA, NA, and H-SNA (Sec A.2).
4.3
SNA is the Optimal Denoiser under the Latent Superpixel Model
The optimal denoiser is the function that minimizes the mean-squared error between the denoised pixel and the original pixel value. Following similar derivations (37), minimizing this expectation with respect unknown denoiser (D) is possible because of our chosen model for the unknown data density, Say we have a sample, x, 8, π ~ p(æ, 8, тT. Then we approximate p(æ,(s:),
M
M
p(2.(8)) = Σ p(mls:) p(mss m==
Σ m=1
p(.. - 0m)
(6)
M
By re-weighting with superpixel probabilities, rather than superpixel assignments, our estimate does not depend on ambiguous superpixel labels. The expected loss of a denoiser is computed over the factorized joint density of the Gaussian-corrupted pixels, noise- free pixels, superpixel assignments, and superpixel probabilities: (( (s.)p.ssssspsss..)))))))ps))) ( ((()).
since p(s;) 9 and p(m)
The optimal denoiser to the following optimization problem is soft superpixel neighbor- hood attention (SNA) when the faa--rrassorms are identity, the attention scale is fixed to Xut I and the samples used to estimate the data density come from a neighborhood surrounding pixel i,
Claim
( (2; = D (ā = arg min E [[e,; o) E n,
=2:1?2]
(7)
5

---

Doep
Each superp sel,
Piobebility
SLII
Ench S. pperptir
H
H
hop
Tchage
SLI Renulaas
H
H
SUI Paramettos
W
Figure 6: Estimating Superpixel Probabilities. The superpixel probabilities are learned during training using one of these two methods. The left method uses shallow UNet followed by softmax layer with nine channels (gs.Deep). The right method estimates hyperparameters to be used within SLIC iterations (ga,sLIC).
See Supplemental Section A.1 for the proof. practice, the error of a denoiser depends on the sampled data, and in this paper, the data is limited to a neighborhood surrounding the query point. Section A.2 analyzes this limited neighborhood.
(1s) x (
4.4 Normalization for Restricted Connectivity
SLIC [26] and SNN g connect each pixel to (at most) nine superpixels. Therefore, some pixels within a neigh- borhood may only connect to subset of superpixels that connect to the query index. This sharp cut-off in con- nectivity creates artifacts within the attention map since the number of non-zero superpixel probabilities for some neighbors is fewer than nine. These artifacts due our choice of superpixel algorithms [26]. 8) rather than limitation of our attention module. To correct these ar- tifacts for the attention map associated with pixel i, we re-normalize the adjacent superpixel probabilities one; ((i+)) (i++) Exec()) T(,*", where C(t) the set of superpixels connected pixel index the attention maps with and without the normalization
Figure 5: Artifacts in Attention. This attention map visualizes the unnormal- ized superpixel weights for neighbors, j E N(i.. The restricted connectivity leads to sharp cut-offss in the superpixel weights. To create this figure, π (k..)) 1/9 if pixel & is connected to superpix- cls and zero otherwise. White pixels indicate the region sums to 1, while grey regions sum to values less than 1.
step.
4.5 Estimating Superpixel Probabilities
SNA re-weights the attention map using superpixel probabilities, which are estimated from noisy images, π = g. (æ). This paper forgoes considering theoretical concerns (such as identifiability) and uses ad-hoc estimates of these probabilities with two deep networks, depicted in Figure
The first method estimates the marginal probabilitics directly from deep network, म 96. Deep (x). The second method estimates the superpixel parameters controlling the balance between appearance and shape with a deep network, which then fed into differentiable SLIC iterations [8] (Section 3.1):
# = Je.sLIC xz. f)) where Mupp nahape 0g.SLIC(z)) This model is abbreviated as मे Jo.sLIC
The number of SLIC iterations fixed following a recent paper (7). These networks are two-layer UNets [88
4.6 Learnable Attention Scale
Using a network similar to the ones used estimate superpixel probabilities, all attention modules are augmented to serve as another baseline. The augmentation replaces the fixed attention scale with learnable attention scales for each pixel, A.: = Au.Aum(a)) The network architecture is identical to De.Deep except for the final layer, which outputs one channel rather than nine. This baseline empirically demonstrates the theoretical argument from Supplemental Section A.3 even when modulating the attention scale, NA cannot robustly reject dissimilar pixels.

---

Experiments
This section demonstrates the impressive benefit of superpixel neighborhood attention compared to standard neighborhood attention. To verify whether the improvement is due to the proposed method, we compare several variations of both attention methods. Section 5.2 compares different attention modules within a simple network architecture on Gaussian denoising, which empirically verifies the theoretical findings in Sections 4.3 and A.2 Section (5.3ioon333300 compares the superpixel probabilities learned from the denoising loss function with superpixels learned through supervised training. Supplemental experniee
Section B.1 includes ablation experiments.
5.1 Experimental Setup
Our experiments use simple denoising network with larger auxiliary networks to highlight the role of the learned superpixel probabilities and attention scale parameters. The denoising network contains only projection layers and single attention module. To keep the extracted features simple, the only interaction between neighboring pixels through the attention layer. The project matrices project the input RGB image from three to six dimensions dimension. The full network is written,
DDeoo Simple Network,, (xx) = fAum (x go(wWo) W1 + W1
(8)
The primary network parameters are denoted 0 = [,, W1). and (.(() is the auxiliary deep network from Section 4.5 The primary network consists of only 200 parameters (0), and the auxiliary networks contain about 4.4k or 8.8k parameters (o). We train each network for 800 epochs using a batch size of on the BSD500 dataset (36] using a learning rate of 2. 10 with a decay factor of 1 1/2 at epochs 300 and 600. The network is optimized with Adam (39] The code is implemented in Python using Pytorch, Numpy, Pandas, and CUDA and run using two NVIDIA Titan RTX GPUs and one RTX 3090 Ti GPU 40 43 Testing datasets are Set5 [4], BSD 100 (36), Urban
45 and Mangal09 [46).
5.2 Gaussian Denoising
This subsection empirically verifies the utility of SNA on Gaussian denoising. The Charbonnier loss used for denoiser training, Deno = / DDDeo - y| + z² (e 10 10-3) 147. By default, the window size is 15 x 15, the fixed SLIC precision is ten, and the fixed attention scale is one.
Table presents the quantitative results. The SNA module achieves far better denoising quality than NA, even when NA can learn its attention scale. As an extreme example, the PSNR at o = 30 of the left-most SNA column is about 2.8 dB better than standard NA (2nd NA column). If comparison is restricted to models with the same number of parameters, the PSNR at a = 30 of the the fourth SNA column is about 1.8 dB better than the augmented NA (Ist NA column). For a fixed budget of network parameters, SNA yields a higher quality denoiser than NA.
Figure 7 shows SNA is qualitatively superior to NA. The first row shows that SNA produces less grainy images than NA. The bottom two rows show that NA mixes perceptually unrelated information. In the second row, NA outputs a red-orange semi-transparent mist surrounding the orange-ret rock. In the third row of the NA results, the white zebra stripes are shaded darker than the clean image when the attention scale is learned, and contain white speckles if fixed. See Section B.2 for more examples.
Learning the attention scale improves standard NA and SNA+ga. at higher noise intensities. How- ever, it degrades model quality when superpixels are estimated with SLIC iterations (SNA+go.st. Perhaps this quality drop is simply due to network architecture and/or the flow of information. Since the network that learns the attention parameter is only given noisy image, the simple model strug- gles to coordinate with the denoising network, which uses multiple SLIC iterations. SLIC iterations explicitly compute pairwise distances, which cannot be learned with the shallow model.
limitation of the proposed SNA module is the additional computation compared to NA. SNA amounts to re-weighting the attention map produced by neighborhood search, so SNA is necessarily more compute-intensive than NA. The bottom four rows of Table [ show SNA is 15 22 times slower than NA. While this increase is significant, we believe the numbers reported in this paper are overly pessimistic. Our implementation of SNA has not been optimized, and future development can dramatically reduce the wall-clock time. One way to reduce wall-clock time is read more efficiently
7

---

Table 1: Image Denoising [PSNR The denoising quality of each network averaged across images from Set5 [4], BSDIO0 [36], Urban [45], and Mangal09 [46.. The SNA module quantitatively superior to NA, even when NA's attention scales are learned with a deep network. However, NA is over 20 times faster than SNA and consumes 13 times less memory. A major contribution of NA is efficiency, while the code for this paper's proposed SNA module not been optimized. Time and memory usage reported for single image of size 128 x 128.
Attn.
SNA
H-SNA
NA
Learn Aat Sp. Model
9á. Deep
SLC
Deep
S6.SLIC
S6.SLIC
31.96
32.08
32.07
32.19
30.88
30.87
31.10
10
0,869
0,871
0.865
0.871
0.810
0.850
0.850
29.01
28.72
28.77
29.08
25.56
27.12
26.96
20
0.838
0.815
0.819
0.804
0.630
0.774
0.743
27.70
26.94
27.25
27.51
22.37
25.69
24.91
30
0.805
0.777
0.764
0.763
0.512
0.743
0.687
Deno Params (8)
195
195
195
195
195
195
195
Aux Params (Ø)
8.8k
8.8k
4.4k
4.4k
4.4k
Fwd Time (ms)
30.20
45,05
27,06
40.58
28,86
4.64
2.08
Bwd Time (ms)
38.72
80.93
40.00
51.35
32.54
6.06
4.67
Fwd Mem (GB)
1.90
2.30
1.87
2.28
1.96
0.23
0.21
Bwd Mem (GB)
3.27
3.68
3,25
3.66
3.13
0.27
0.25
SNA
Noisy
Clean
Learn Aat
Fix Aat
Learn Aat
Fix Aut
Cast Cast
22.09
27.19
28.15
25.36
24.81
22.07
27.17
27.29
25.75
22.63
27.38
28
21.89
25 65.64
Figure 7: Denoised Examples [PSNR[]. This figure compares the quality of denoised images using the Simple Network and noise intensity a = 20. The attention scale (Aur) is either fixed or learned with deep network. In both cases, the NA module mixes perceptually dissimilar information, while the SNA module excludes dissimilar regions. See Section B.2 for more examples.
from global CUDA memory Anecdotally, the naive implementations of NA are 500% 1500% slower than their recently optimized alternatives.
5.3 Inspecting the Learned Superpixel Probabilities
This subsection investigates how the superpixels learned from denoising compare with superpixels learned from explicit supervised superpixel training [8]. We observe a collaborative relationship between superpixel probabilities for denoising and superpixel pooling. We observe adversarial relationship between the superpixels for denoising and boundary adherence. Generally, learning
superpixels that improve superpixel benchmarks decreases their utility for denoising.

---

Table 2: Supervised Superpixel Training Impacts Denoiser Quality. This table compares the denoising quality of SNA networks trained with both a denoising loss term and an SSN loss term, Tiimal = Deno + LSSN. The SSN Label "None" indicates only a denoising loss is used. Pixel labels marginally improve the denoising quality, suggesting cooperative relationship between these optimization problems. Segmentation labels degrade the denoising, suggesting the best superpixels for boundary adherence are not the best superpixels for image denoising. Time and memory usage
are reported for a single 128 x 128 image.
SSN Label
PSNR/SSIM
Fwd/Bwd Time (ms)
Fwd/Bwd Mem (GB)
None
32.77/0.879
33
0.5
Pix 32.78/0.889
62
6.3
Seg
30.14/0.798
86
6.3
Table 3: Evaluating Superpixel Quality. Training an SNA attention module on denoising learns
superpixel probabilities with comparable quality to explicitly training superpixels. The ASA and BR metrics evaluate the ML superpixel estimate. The PSNR and SSIM metrics evaluate the quality of the superpixel pooled image. SSNTabe
Image Pixels
Segmentation
Loss
Deno
SSN
LSSN
LSSN + Deno
LSSN
Lsss
LSSN + Deno
10
10
10
10
10
ASA
0.954
0.952
0.946
0.947
0.961
0.958
0.95I
BR
0.771
0.774
0.752
0.751
0.855
0.824
0.754
PSNR
27.08
31.02
29.89
29.41
21.56
22.20
25.31
SSIM
0.811
0.934
0.886
0.883
0.553
0.574
0.737
To compare the different training regimes for learning superpixel probabilities, an SNA network is fully trained with combination of two loss functions. One loss the denoising loss (Leen)). The second loss is the SSN loss function, which computes the difference between a target vector and its superpixel-pooles transformation (see Section for super-pixel pooling) [8]. Specifically, LSsN = L( spppo- x) where L is the cross cross-entropy loss for a segmentation label and the mean- squared-error for image pixels. The superpixel stride for all methods is fixed to S.p 14. Each network estimates superpixels using SLIC iterations, and the attention scale is fixed to one (if applicable). Evaluation is computed on the test set of BSD500 (36].
The Achievable Segmentation Accuracy (ASA) and Boundary Recall (BR) scores evaluate the quality of the maximum likelihood superpixel assignment. The ASA score measures the upper bound on the achievable accuracy of any segmentation method, and the BR measures the boundary align- ment between the superpixels and a segmentation. The superpixels are processed with a connected components algorithm before computing ASA and BR scores. To qualitatively compare the learned superpixel probabilities, we follow recent literature and compare the superpixel pooled images (5). Images are compared against their superpixel pooled images using PSNR and SSIM.
Table 2 evaluates the denoising quality, 3 quantitatively evaluates the superpixel quality, and Figure qualitatively evaluates the superpixel pooling quality. We observe a harmony between the denoising loss and pixel pooling loss terms. Combining the two terms yields slightly improved denoising, as reported in the first two rows of Table The first, third, and fourth columns of Table 3 show the ML superpixel quality is similar, but the boundary recall is slightly worse when combining the two. The superpixel pooling quality increases by 2.33 dB PSNR when combined compared to only denoising. The second and last columns Figure qualitatively compare the pooled images.
We observe a disharmony between the superpixel probabilities useful for denoising and those trained segmentation labels. Table 2 reports 2.6 dB PSNR drop in denoising quality. The first two rows of Table 3 report training with segmentation labels yields the best ML superpixel estimates, matching related works (8) However, the superpixel pooling quality is poor. This suggests boundary detection is distinct from denoising and pixel pooling.

---

SSN Label
Segmentation
Image Pixels
Loss
Deno 10
LSS
LSNN
LASN
LOSN + Deno
28. .88
24.05
31.63
30.63
30.64
29 29.00
79
31.99
31.09
30.90
Trained for Image
Superpixel Pooling?
Figure Comparing Superpixel Probabilites via Superpixel Pooling [PSNR]]. This figure uses superpixel pooling to qualitatively compare superpixel probabilities learned with different loss functions. Learning superpixel probabilities with only a denoising loss yields better superpixel pooling than supervised learning with segmentation labels. However, jointly training superpixel probabilities for denoising and image superpixel pooling improves denoising and pooling quality, which suggests a useful relationship between the two tasks.
SNA
NA
Expression
FL.PS
Memory
FLOPs
Menory
explAu Rg]
OFF-RW- K3)
0 K²)
O(F-3WW
O(OPP-3)
explAu of S (os
NW
O12 NW-
Way Eireni ond Na
O/HW- K*)
O(HW K?)
O(DV-.K))
Eyexc my
OFF. HW
OFF HOV)
NW JC)
OLF HPW)
Total FLOPSs Pesk Memory
012 10 NOV K²) O[F-10 10V R2) O1E24 NOV .2). D(F-100 2-W (F)
Table 4: Computational Complexity. This table reports the FLOPs and memory consumption for Equations 3 and [ Constant terms are retained to clarify the differences between SNA and NA.
The second re-weights the attention map using superpixel probabilities, and is the extra step distinguishing SNA from NA. This incurs an extra (9. HW- K2) FLOPPs and requires O(2-HWW K²) memory. However, SNA's additional complexity does not scale with the number of features (F).
5.4 Comparing Computational Complexity
Table compares the FLOPs and memory consumption of SNA and NA from Equations 3 and Let the neighborhood window size be written [N(i) = K2_ In summary, the FLOPs estimate for SNA and HWK33
NA O(2 -10)H3 and O[2F+11] HWK?), respectively. The peak memory consumption for SNA and NA is O(HWF + 2HWK²) and O(NF F HWK²), respectively. Importantly, SNA's additional complexity does not scale with the number of features (F). Since the number of features is significant factor in the computational cost of an attention operator, it is sensible to believe SNA can be used efficiently within large-scale deep neural networks. To be concrete, if the number of features is 128, then there is less than a 4% percent increase in FLOPs from NA to SNA.
6 Discussion
This paper presents the soft superpixel neighborhood attention (SNA) module as an alternative to neighborhood attention (NA). SNA accounts for deformable boundaries of objects. The key modeling assumption is that superpixel probabilities vary per pixel, and we find SNA is the optimal denoiser under this model. For a fixed budget of network parameters, SNA achieves a significantly better denoising quality than NA within single-layer neural network. While SNA does require more computation than NA, SNA's computation does not scale with features which suggests SNA can be used efficiently within large-scale deep neural networks.
10

---

7 Acknowledgments
This work is supported, in part, by the National Science Foundation under the awards 2030570, 2134209, and 2133032. The authors thank Drs. Vinayak Rao and David Inouye for their valuable feedback and support.
References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[2] Ali Hassani, Steven Walton, Jiachen Li, Shen Li, and Humphrey Shi. Neighborhood attention transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6185-6194, 2023.
[3] Xiaofeng Ren and Jitendra Malik. Learning a classification model for segmentation. In Proceedings ninth IEEE international conference on computer vision, pages 10-17. IEEE, 2003.
[4] Max Wertheimer. Laws of organization in perceptual forms. A Source Book of Gestalt Psychology. pages 71-88, 1938.
[5] Roy Uziel, Meitar Ronen, and Oren Freifeld. Bayesian adaptive superpixel segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8470-8479, 2019.
[6] Fengting Yang, Qian Sun, Hailin Jin, and Zihan Zhou, Superpixel segmentation with fully convolutional networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 13964-13973, 2020.
[7] Aiping Zhang, Wenqi Ren, Yi Liu, and Xiaochun Cao. Lightweight image super-resolution with superpixel token interaction. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 12728-12737, 2023.
[8] Varun Jampani, Deqing Sun, Ming- Yu Liu, Ming- Hiuan Yang, and Jan Kautz. Superpixel sampling networks. In Proceedings of the European Conference on Computer Vision (ECCV), pages 352-368, 2018.
[9] Antoni Buades, Bartomeu Coll, and Jean-Michel Morel. Non-local means denoising. Image Processing On Line, 1:208-28 212, 2011.
[10] Marc Lebrun. An analysis and implementation of the bm3d image denoising method. Image Processing On Line, 2.135-213, 2012.
[11] Shuhang Gu. Lei Zhang, Wangmeng Zuo, and Xiangchu Feng. Weighted nuclear min- imization with application to image denoising. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2862-2869, 2014.
[12] Ding Liu, Bihan Wen, Yuchen Fan, Chen Change Loy, and Thomas Huang. Non-local recurrent network for image restoration. Advances in Neural Information Processing Systems, 31, 2018
[13] Tobias Plötz and Stefan Roth. Neural nearest neighbors networks. Advances in Neural Informa- tion Processing Systems, 31, 2018.
[14] Ding Liu, Bihan Wen, Yuchen Fan, Chen Change Loy, and Thomas S Huang. Non-local recurrent network for image restoration. Advances in neural information processing systems, 31, 2018.
[15] Hunsang Lee, Hyesong Choi, Kwanghoon Sohn, and Dongbo Min. Knn local attention for image restoration. Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition, pages 2139-21 2449, 2022.

---

[16] Gregory Vaksman, Michael Elad, and Peyman Milanfar. Lidia: Lightweight learned image denoising with instance adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition Workshops, pages 524-525, 2020.
[17] Diego Valsesia, Giulia Fracastoro, and Enrico Magli. Deep IEEE Transactions on Image Processing, 29:8226-288 82776-8237,22 2020.
image denoising.
[18] Yiqun Mei, Yuchen Fan, Yuqian Zhou, Lichao Huang, Thomas S. Huang, and Honghui Shi. Image super-resolution with cross-scale non-local attention and exhaustive self-exemplars min- ing. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[19] Chong Mou, Jian Zhang, Xiaopeng Fan, Hangfan Liu, and Ronggang Wang. Cola-net: Col- laborative attention network for image restoration. IEEE Transactions on Multimedia, 24: 1 1366 1377, 2021.
[20] Chong Mou, Jian Zhang, and Zhuoyuan Wu. Dynamic attentive graph learning for image restoration. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4328 4228-4337.20 2021.
[21] 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 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
[22] 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, 2021.
[23] Jingyun Liang. Jiezhang Cao, Guolei Sun, Kai Zhang, Lue Van Gool, and Radu Timofte. Swinir: Image restoration using swin transformer. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1833-1844, 2021.
[24] Chun-Fu Richard Chen, Quanfu Fan, and Rameswar Panda. Crossvit: Cross-attention multi- scale vision transformer for image classification. In Proceedings of the IEEE/CVF international conference on computer vision, pages 357-366, 2021.
[25] Alaaeldin Ali, Hugo Touvron, Mathilde Caron, Piotr Bojanowski, Matthijs Douze, Armand Joulin, Ivan Laptev, Natalia Neverova, Gabriel Synnaeve, Jakob Verbeek, et al. Xcit: Cross- covariance image transformers. Advances in neural information processing systems, 34:20014- 20027, 2021.
[26] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels. Technical report, 2010.
[27] Olga Veksler, Yuri Boykov, and Paria Mehrani. Superpixels and supervoxels in an energy optimization framework. In Computer Vision-ECCV 2010: 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5-11, 2010, Proceedings, Part V 11, pages 211-224. Springer, 2010.
[28] Greg Mori, Xiaofeng Ren, Alexei Efros, and Jitendra Malik. Recovering human body configurations: Combining segmentation and recognition. In Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004, CVPR 2004., volume 2, pages II-II. IEEE, 2004.
[29] Jian Sun, Wenfei Cao, Zongben Xu, and Jean Ponce. Learning a convolutional neural network for non-uniform motion blur removal. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 769-777, 2015.
[30] Kun Li, Yanming Zhu, Jingyu Yang, and Jianmin Jiang. Video super-resolution using an adaptive superpixel-guided auto-regressive model. Pattern Recognition, 51:59-71, 2016.
12

---

[31] Yiding Liu, Siyu Yang, Bin Li, Wengang Zhou, Jizheng Xu, Houqiang Li, and Yan Lu. Affin- ity derivation and graph merge for instance segmentation. In Proceedings of the European conference on computer vision (ECCV), pages 686-703, 2018.
[32] Sree Ramya S. P. Malladi, Sundaresh Ram, and Jeffrey J. Rodríguez. Image denoising using superpixel-basee pea. IEEE Transactions on Multimedia, 23:2297-2309, 2021. doi: 10.1109/ TMMM22200.009955
[33] Wei-Chih Tu, Ming- Yu Liu, Varun Jampani, Deqing Sun, Shao-Y Yi Chien, Ming-Hsuan Yang, and Jan Kautz. Learning superpixels with segmentation-awarc affinity loss. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 568-576, 2018.
[34] Moshe Eliasof, Nir Ben Zikri, and Eran Treister. Rethinking unsupervised neural superpixel segmentation. In 2022 IEEE International Conference on Image Processing (ICIP), pages 3500-3504. IEEE, 2022.
[35] Constantinos Goutis. Nonparametric estimation of mixing density via the kernel method. Journal of the American Statistical Association, 92(440):1445-14 1997.
[36] David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik. A database of human seg- mented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, volume 2, pages 416-423. IEEE, 2001.
[37] Tero Karras, Mika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- generative models. Advances in Neural Information Processing Systems, 35: 26565-26577 2022.
[38] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical image computing and computer-assisted intervention 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pages 234-241. Springer, 2015.
[39] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6980, 2014.
[40] Adam Paszke, Sam Gross, Franeisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, piih-peeffrmance deep learning library. Advances in neural information processing systems, 32, 2019.
[41] Charles R. Harris, K. Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, Robert Kern, Matti Picus. Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río. Mark Wiebe, Pearu Peterson, Pierre Gérard-Marcham Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585:357-362 2020. doi: 10. (0.1038/441566-02 011--002226660 2649-2.
[42] Wes McKinney et al. Data structures for statistical computing in python. Proceedings of the 9th Python in Science Conference, volume 445, pages 51 51-56. Austin, TX, 2010.
[43] NVIDIA, Péter Vingelmann, and Frank H.P. Fitzek. Cuda, release: 10.2.89, 2020. URL httpps//deveeoperr nvidia. com/ cuda
[44] Marco Bevilacqua, Aline Roumy, Christine Guillemot, and Marie Line Alberi-Morel. Low- complexity single-image super-resolution based on nonnegative neighbor embedding. 2012.
[45] Jia-Bin Huang, Abhishek Singh, and Narendra Ahuja. Single image super-resolution from transformed self-exemplars. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5197-5206, 2015.
[46] Yusuke Matsui, Kota Ito, Yuji Aramaki, Azuma Fujimoto, Toru Ogawa, Toshihiko Yamasaki, and Kiyoharu Aizawa. Sketch-based manga retrieval using manga109 dataset. Multimedia Tools and Applications, 76:21811-211 2017.
13

---

[47] Pierre Charbonnier, Laure Blanc-Feraude Gilles Aubert, and Michel Barlaud. Two determin- istic half-quadratic regularization algorithms for computed imaging, In Proceedings of 1st international conference image processing, volume 2, pages 168-172. IEFE, 1994.
14

---

A Additional Method Details and Proofs
A.1
Soft Superpixel Attention is the Optimal Denoiser
The latent superpixel model assumes the following data-generating process for each image pixel,
Sample superpixel probabilities
π p(
(9)
Sample the superpixel assignment given the probabilities Sample the image pixel given the superpixel assignment
8:
( 8 π (3)
(10)
x
(11)
We will construct denoiser that depends on the superpixel probabilities rather than the superpixel assignment. Our derivation inspired by [37]. Only the form of p(s (+)) Categorical s T()) is known, and p( T will not impact our final answer. So we only need to estimate the unknown density, p(zls)) To do this, we approximate p(az|s) from a sample (x, 8, T),
M
M Σ
{() = Σ p(mals)p(a..lm)
p (m) - 3m)
(12)
M
m=1
where pm):/m)) = ग (m)) By re-weighting the empirical density with superpixel probabilities, rather than superpixel assignments, our estimate does not depend the ambiguous superpixel labels. Notice the superpixel probabilities are independent of the sample index, then the usual weighting is recovered, p(m(s;) ( p(m) 3/2 Next, the pixels corrupted with Gaussian noise,
Po (ā.()));) [0(-18)) N(;50,0110 (ār)) / p( Nx) 0
(13)
9 M
p(s.lm) /
9 M
8(10 am (aro; s3,, 0² dddo
02I)
(14)
Let the denoiser be a function of the noise intensity and superpixel probabilities, D(ā,; a, T). The expected error of the denoiser is taken with respect to the density Po (ā.(s.))) p((T).
[[) x3
(15)
s
M Σ m=1
Ep(r)
p(s/T((1) (6))
p(slm) ãi, o2 - 3m 1m
(16)
M
M
9
(p(())
p(s [pslm))((s am, o²
- xmml dı:
(17)
M
RF
m=
a=1
Note p(s; ()) + (() for clarity. The expectation can be minimized by minimizing each integrand for fixed a fixed noisy pixel (æ) and superpixel probability (ær) Since the integrand is sum of convex functions, the problem is convex and the solution is the point where the gradient is equal to zero.
0 = V (( TT) =
Σ m=1
V( m, o²
Σ
p(s π )((smm))))))))))))))))))(())))) [D" xm]]
(18)
15

---

In general, the optimal denoiser is written as,
M
(i, Tm: 0²) Ei p(s/ p((mm))
D' 0)) = Σ Im Em/=1 N (i am,, o²) Ex p( ppssmm)
(19)
By construction, the probability of particular sample's superpixel assignment is written p(s]m) = (m..)) When the samples are restricted to a neighborhood surrounding pixel i, one can write the denoiser as the following expression,
D" D'(
E 2j JEN(()
exp
2n |
æ;il) E. π (1.))) (i.e)
(20)
EyEN() exp I0= [ By Ex=1 (1'.)))
This is soft superpixel neighborhood attention when the samples are restricted to neighborhood surrounding pixel i, the gkv-transforms are identity, and the attention scale fixed, Au: 1
Presently, we highlight where our per-pixel superpixel probabilitics are used in the proof. In Equa- tion 19 the probability p(s( depends the sampled superpixel probabilities π. When denoising image pixel index i, have p(s[Tr) (B,s), However, under the standard model with shape superpixel probability prior, p(5(T) does not depend on the particular pixel index. This reduces Equation 20 to superpixel re-weighting term that does not depend superpixel information from pixel i, which would be strange. We did experimentally try out this alternative re-weighting scheme, and its denoising quality matches NA.
Finally, we discuss a conceptual rationale for sampling superpixel probabilities for each image pixel. The introduction (Sec D explains that superpixel assignment is ambiguous classification task. There are many qualitatively "good" superpixel assignments, and often superpixel boundaries can be modified without impacting the overall quality. This suggests superpixel probabilities are more important than superpixel assignments. However, working with p(z| m is more challenging than working with p(x: s). So in this paper, still work with p( ((z)s) but design the denoiser to depend on the probabilities π to circumvent using the ambiguous superpixel assignments.
A.2 Expected Denoising Error for a Fixed Neighborhood
states that SNA is the optimal denoiser, but in practice, samples are limited neighbor- hood surrounding a query pixel. To analyze the impact of this restriction, this subsection computes the expected error the image pixels and noise for fixed superpixel sample. For expedient analysis, the number of features is one (F = 1, x; - x²)). The image pixels conditioned on the superpixel information modeled with Gaussian distribution, Iy 12 1,, NNus, n²). We will analyze the attention modules by studying a denoiser the following form,
Section 4.3
D.(T)= =
Σ mjL
(21)
JEN(()
This denoiser corresponds using flat attention scale Au 0 and using only prior superpixel probabilities as attention weights wj. Analysis of attention weights, in general, is difficult, and this approach removes the challenge. The expected error computed over the Gaussian-coruupted and noise-free data density conditioned by the superpixel information, p(ā (x)))((()) (s, μ,, 1)). The expected error is split into the classic bias- variance decomposition. See Section A.4 for the proof.
16

---

Claim 2 The expected error of the denoiser 'D over the joint density p(ă, a p, 1) is written,
E (D((a) 21)
0²
Σ JEN()
w
+
Σ JEN(()
wy(Me, - Hos)
(22)
Variance
Bias
The NA modulc's flat weights achieve the minimum variance of wo where W [W(()] is the window size. However, NA's bias depends entirely on the superpixel's neighbors and can large if the neighborhood happens contain pixels from superpixels with different means. For example, the bias will be large for pixels along the sharp orange edge in Figure since their neighborhoods include the dissimilar blue region. Section A.3 shows that even when the attention scale is non-zero, NA cannot robustly reject dissimilar regions.
H-SNA has the opposite problem of NA. H-SNA's sharp weights achieve the minimum possible bias of zero. However, H-SNA's variance depends entirely on the size of the superpixel. In Figure the snake-like superpixel reduces the number of included pixels, increasing the variance term of the error. This observation that thin and small superpixels are undesirable matches existing assumptions from superpixel literature [26 5].
SNA's modulation of the superpixel weights allows it to be better than both NA and H-SNA. In Figure 3 SNA excludes the dissimilar blue region (unlike NA) and includes the similar orange regions (unlike H-S.).. Said another way, SNA excludes only dissimilar regions.
A.3 Exclude Dissimilar Regions Instead of Dissimilar Pixels
Section A.2 showed SNA yields a smaller theoretical error than NA because SNA can exclude dissimilar regions via superpixel probabilities. The previous analysis fixed the attention scale to zero (Aur 0). and one may wonder if the attention scale might be used to exclude dissimilar regions well. This subsection shows the attention scale excludes dissimilar pixels rather than dissimilar regions, which is less robust under noise. In this analysis, the qk- uk-trrasforms are fixed to identity, the feature dimension is fixed to 1, and the distances function the negative squared difference: d(y,, 3y) = (v: 2
We first show the attention scale excludes dissimilar pixels rather than regions. Weights of pixels within similar region should be similar, Waj x Wi,i, while weights of pixels within dissimilar regions should be zero, W O. The decay of dissimilar regions will only occur for NA when the scale increases (Aur > 0), but this growth also decays the weights associated with similar regions. Noting Aad(().3)) = 1, the ratio of two weights for NA is as follows:
log
Whit wi.s
Aan -0;)²
yi R
(23)
Two noisy pixel values must be approximately equal for their attention weights to be approximately equal. In other words, excluding dissimilar regions with the attention weights also excludes non- identical noisy pixels. This strict condition limits NA's ability to exclude dissimilar regions.
Compare this with SNA, which we argue excludes regions more robustly. Say all but single region should be excluded, so Xyp can be large. The inclusion of the single (useful) region depends on the most likely estimated superpixel matching the latent probabilities, sf 8,. Using Section 3.1 formulation, the argmax terms match when the following condition is met,
(pe; - u1)² < (Ms, - y;)², #
(24)
In other words, SNA properly rejects dissimilar regions when a noisy pixel is more similar to its true mean than another superpixel mean. Comparing two noisy differences is more robust than comparing two noisy pixels. So we claim SNA rejects dissimilar regions more robustly than NA.
17

---

A.4 The Estimated Expected Denoising Error
This subsection presents more detailed version of Claim from Section A.2 and its proof.
Claim 3 The expected error of the denoiser over the joint density p(æ æ 8, pe n) is written,
E (D: -x:)² N1, (1 2w;) +
Σ
w)(0² - naa) + wi(Mss - Mar)
(25)
JEN(()
JEN((
Varionce
The following proves the above claim. The first step is expand the square,
E(D (+)] + +[x]] 2 [[(D(()) ==)=====[]
(26)
Each expectation is evaluated separately,
Ei = 2 + u
(27)
[T)] = Σ 33 +2
Σ
wy wy
(28)
jEN(()
k<jJEN()
Σ w (0² + 1135 + +12,)) +2
Σ
WyWkMs,
(29)
JEN(()
k<iJEN(1
Σ JEN(()
W (0² + +1,,)= +
Σ
Wh. WiHHWHkkas
(30)
(.KEN(()
E E(D(()),)]
Σ
wyBBi,æ We
Σ
WiggMeMes
(31)
JEN(()
JEN(
Then all terms are put together and rearranged,
[[(D(() - x1:3] =me - -2wi, +
Σ
2 woz + ne,)
SEN(s)
+ 2e, +
Σ
wy WyWkHe,HHs -2 Σ
WigHe,
(32)
(.kEN(()
JEN(()
nh
2wan
2
Σ
u + m
JEN(1)
Wy WyHk +
WyWkHor -
Σ
WyWkPesHa
(33)
(.kEN(()
j.EN(())
j.kEN(i)
1 (1 -ww;)= +
Σ
wi(o² + n1,,)
Σ
wy(Ms, May))
(34)
JEN(()
JEN(O
Using E[X² Var + E[X] the birianee terms can be identified. Since the [[[ term is simple to compute and exactly matches the right-hand side, we can label those terms as the bias and assign the remaining terms to the variance.
18

---

10
d=20
33.2
20.7
27.9
28.4
76.3
PSNR
31.7-
27.2
24.8
Method
SNA Doap
25.0
23.2
MA.Fixed
H-SNA
30.2
24.6
21.7
3'
gP
15'
212
9P
15'
212
9'
15
21
Neighborhood (pixels)
Neighborhood (pixels)
Neighborhood Size (pixels)
Figure 9: Neighborhood Window Size. Increasing the neighborhood window size includes more samples to decrease the variance but also adds bias since the noisy samples can be weighted improperly. This trade-off is illustrated by the increasing optimal window size as the noise intensity increases. Since the bias of H-SNA is nearly zero, the increasing neighborhood size only increases the denoising quality within the selected grid.
32.7
29.8
28.5
32.2
29.1
27.8
Idb)
SNA-SUIC
28.5
Learn
31.3
27.8
26.4
30.9
27.1
40
70
150
70
150
70
150
Aux Not Size (10? Params)
Aux Not Size (10? Params)
Aux Net Size (10? Params)
Figure 10: Number of Auxiliary Parameters. This ablation experiment expands the size of the auxiliary network by increasing the number of UNet channels. The x-axis plots the number of parameters in the auxiliary network (løl). The y-axis plots the PSNR of several denoiser networks. Generally, parameters improve the denoising quality. The drop in denoising quality for the final network may be due to trainng..ining.
==
0= 20
=0
SNA-SSUI
PSNR (dB)
$2.15
SMA-Deeg
29.9
27.5
32.07
28.0
27.3
31.90
28.7
27.1
10 12
17
10 12
17
6
10 12
17
Num, of Superpixels (10?)
Num. of Superpixels (10F)
Num. of Superpixels (10*)
Figure 11: Number of Superpixels. The number of superpixels has a limited effect on the denoising quality when compared with other hyperparameters. Generally, increasing the number of superpixels increases the denoising quality. When the noise is low (a = 10) the number of superpixels seems irrelevant. As the noise increases, the benefit of more superpixels becomes more apparent. Generally, using explicit SLIC iterations is more effective than predicting superpixel probabilities directly.
B
Additional Experiments
B.1
Ablation Experiments
This subsection explores the impact of hyperparameters related to the proposed SNA. This includes the neighborhood window size (Fig(9. the size of the auxiliary network (Fig TOp, and the number of superpixels (Fig ITp. All networks are trained and tested according to Section 5.2 Both the size of the auxiliary network and the neighborhood window size have significant impact on the denoiser quality (over dB). The number superpixels has a smaller overall impact (less than 0.5 dB).
19

---

B.2
Additional Denoising Results
SNA
NA
Noisy
Clean
Learn At
Fix Aat
Learn Aat
Fix Aat
23.39
32.38
31.71
29.11
29.33
22.22
29.08
29.57
26.66
27.91
22.35
29.03
29.77
27.08
27.44
22.26
30.48
30.37
29.03
28.08
23.08
28.13
28.81
23.02
27.55
22.93
24.77
26.38
24.17
23.25
22.15
29.44
29.46
28.12
27.02
Figure 12: Additional Denoised Examples [PSNR]]. This figure compares the quality of denoised 20. The attention scale (Aa)) is either
images using the Simple Network and noise intensity fixed or learned with a deep network. In both cases, the NA module mixes perceptually dissimilar information, while the SNA module excludes dissimilar regions.
20

---

Justification: Table [ Section 5.2 reports the proposed SNA module requires more computa- tion than the existing baseline method (NA). We note the implementation of SNA has not been optimized, which can dramatically reduce wall-clock time. The primary optimization is to more efficiently read from global CUDA memory, which may have dramatic impact on states SNA is the optimal denoiser, but assumes the corrupting NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
This paper presents soft superpixel neighborhood attention (SNA), which extends standard neighborhood attention to account for deformable boundaries within natural images. Sections 4.3 and cllic and prove SNA is the optimal denoiser under the latent superpixel model. Section 5.2 empirically demonstrates SNA outperforms alternative methods on Gaussian denoising, validating theoretical finding. Section [5.3] compares the superpixels learned from the denoising task to superpixels learned with explicit supervision.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
wall-clock time. Section 4.3 noise Gaussian.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
21

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledgee judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
in the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Section includes the main theoretical contribution of this paper. All as- sumptions are stated the statement of the proof. Intuition for an important assumption described in Section 4.2 and visualized in Figure Section A. includes the formal proof of
the statement.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Section 4.1 writes the proposed attention module using standard notation. The experiment set-up described in Section [.1 explains the important parameters used to run the denoising and superpixel-loss experiments. The denoising experiment uses the random seed 123 across all test samples. The code is provided in the supplemental material and will be made publicly available upon acceptance.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
22

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b)
If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes]
Justification: The code is provided in the supplemental material and will be made publicly available upon acceptance. The code implemented in Python using Pytorch, Numpy, Pandas, and CUDA and run using two NVIDIA Titan RTX GPUs and one RTX 3090 Ti GPU [3). The code includes readme, and requirements files to setup the environment. Testing datasets are Sct5 44) BSD 100 [36], Urban100 45 and Mangal09 [46].
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https /tspps.ccppullcc/////cccc hwtpollccgggiidee wtt.g//dee/eooeeuuniiieeeee SCt///odeeeuieeeeceeee
sobbbbmssssooi ssi wwwssssoisiiioeeeeeo.. onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The experiment set-up described in Section 5.1 explains the important parame- ters used to run the denoising and superpixel- experiments. We train each network for 800 epochs using a batch size of on the BSD500 dataset (36) using a learning rate of 2 10-4 with a decay factor of 1/2 at epochs 300 and 600. These hyperparameters were chosen using an informal grid search. The code provided the supplemental material and will be made publicly available upon acceptance.
23

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Error bars are not usually reported for the benchmarks used in this paper, and we believe including them will add unnecessary clutter to the report. If requested by the reviewers, the 95% confidence interval of the average PSNR/SSIM can be added to the experiments. However, generating error bars to assess the impact training requires re- running all of the experiments several times, which significantly increases the computational cost of this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Section 5.1 states the workstation used to run the experiments includes two NVIDIA Titan RTX GPUs and one GeForce RTX 3090 Ti GPU. Each experiment takes about hours run, and all experiments together take less than 72 hours to run. This paper did require additional computing to determine if using the simple deep learning network was necessary, given the computing budget. This entailed training several larger deep networks and iteratively pruning network layers to reduce the wall-clock training time. Ultimately, using very simple network enabled clear, simple experiment to demonstrate this paper's major claims.
Guidelines:
The answer NA means that the paper does not include experiments.
24

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents a module for deep neural networks and applies the module single-image denoising. While this module may improve generic deep neural networks, this specific paper is not tied to any direct application.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
25

---

Answer: [NA]
Justification:
This paper proposes a module for denoising and is not at risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The code is implemented in Python (PSF) using Pytorch (BSD3), Numpy (BSD), Pandas (BSD3), and CUDA (NVIDIA Software License) 43 The testing
Justification:
datasets are Set5 [44], BSD100 (36). Urban100 [45), and Mangal09 46 These datasets are properly referenced with their supporting paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of license (e.g., CC-BY 4.0) should included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: This paper proposes code for new attention module, and the code is provided the zip file. Within the zipped code file, the new asset is located directory. Two important files within the directory are superpixel_ hatppp/ee_pppp/llissppppppeeeee pixel paper//ib/superpxeel paper/ssna/attn appee//sn//at__ewwweihp.pp reweight.py. The code will be released under the BSD-3-Claus license.
within the
and super-
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
26

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjeets
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "Mspq3uEyEx", "reviewer": "Reviewer_XzEJ", "summary": "This paper proposes an attention module in which the dot product weights are modified with\nsuperpixel probabilities, named Superpixel Neighborhood Attention (SNA). By doing so, the\noptimization process is arguably made easier by letting attention avoid learning spurious\ninteractions, which prior work into the attention module has found to be somewhat common. \nOne key difference to prior works in superpixels is modelling superpixels as probabilities instead\nof naive binary interactions, which in theory allows a flexible interpolation between standard\nattention and superpixel attention. The proposed module is shown to improve the baseline approach\nwithout superpixels by around 1 to 3 dB PSNR, and qualitative results support this claim as well.", "questions": "1. Is there any metric through which SNA's cost or resource requirement can be compared against\nstandard neighborhood attention with more certainty? The seemingly large performance gap in terms of\nactual runtime and memory footprint, while necessary, is unsurprising, and only really reveals that\nas part of future efforts, SNA could use performance optimization. However, it is completely unclear\nhow far that optimization could go. My suggestion is at the very least providing some other proxy\nfor that, be it in the form of time and space complexity, or any other relevant analysis of the\nsteps required by the algorithm and how easy / difficult they will be to parallelize and performance\noptimize.\n\n2. Can you elaborate Eq (1)? Softmax is an operation over a set or vector, and I would assume it\nwould be over N values per pixel, assuming each pixel has N superpixels.\n\n3. This is just out of curiosity, but as of recently the neighborhood attention package does support\nnon-square kernels. Does that change in assumptions with regard to neighborhood attention change\nanything about the significance of SNA over NA, or is that just a minor detail?\n\n4. How are the efficiency performance metrics (runtime and memory usage) evaluated? Were standard\npractices followed? (i.e. locking power and frequency, benchmarking without external factors such as I/O,\ncommunication, framework-level optimizations such as caching allocators and memory planning,\nmeasuring metrics iteratively and reporting an average, and the like)\n\n5. Do either of SNA / H-SNA use the original neighborhood attention implementation, or is the\nimplementation done in this paper completely specific to superpixels? I'm trying to understand\nwhether SNA or its future application could also use additional performance optimizations done to\nneighborhood attention, or whether it would require its own independent development and in turn face\nsimilar issues in terms of extensibility as any other such approach.", "limitations": "While the reported performance gap is a limitation of the proposed approach at the moment, I think\nit is very insignificant when taking into account the rest of the contributions of the paper.\n\nHowever, I cannot be sure of that without evidence that would suggest the performance gap is simply\ndue to a lack of performance optimization. It could very well be the case that SNA in its current\nform cannot scale easily beyond the scope of this paper, which would be in my opinion a far greater\nlimitation.\n\nThis is therefore either a limitation (meaning it is simply not possible or extremely difficult to\nanalyze SNA's computational cost and compare against standard neighborhood attention) or a weakness\n(it was just not included in the paper.)", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Unique approach for injecting superpixel information directly into an attention operator. From \nmy point of view, this is among the most significant contributions of the paper, which would enable\nimproved achievable performance with attention in the context of larger resolution problems, of\nwhich denoising is one. I think the impact of this approach extends beyond denoising and super\nresolution applications.\n\n2. Significant improvement from the baseline approach, neighborhood attention. By allowing\nirrelevant local interactions to be avoided, SNA provides considerably better denoising quality than\nthe standard neighborhood attention.", "weaknesses": "1. From my point of view, the most considerable weakness is a lack of discussion on the\ncomputational complexity of the proposed approach. Note that I am not referring to the reported\nperformance gap, but generally to the fact that it is unclear from reading the paper how complex the\nSNA attention algorithm is, and whether or not it can scale beyond the scope of the experiments done\nin this paper. While metrics such as time and space complexity, and similar metrics such as FLOPs\ndon't necessarily translate into actual efficiency, they do provide a rough idea of whether or not\ntwo operations are at least comparable in terms of resource requirement in theory. Given that the\nbaseline, neighborhood attention, is seemingly so much more efficient in runtime and memory usage,\nand the fact that it has been performance optimized to some extent over time, and that these are\nboth operations in complex deep neural networks implemented primarily by a deep learning framework\nwith a different standard of implementation, I think the reported numbers are simply not that\ninformative. The disclosure and clarity is certainly appreciated, but stating that the proposed\napproach's performance levels are \"likely overly pessimistic\" is not informative, and could be\neasily reworded by providing some evidence that there isn't such a significant difference in\nperformance levels in theory.\n\n2. Lack of comparison to other relevant approaches. I think limiting the use of dot product\nattention to just one local pattern, namely neighborhood attention, is worth a discussion. Is there\na reason why self attention itself is not considered here, given that the superpixel probabilities\neffectively serve as an implicit attention mask. It may also be true that one can map superpixel\nprobabilities directly to attention weights and define attention differently. I think while the\npaper is mostly complete as is, this is something that merits at least a paragraph.\n\n3. The citation for neighborhood attention is incorrect; the reference (\"Neighbor2neighbor\") does\nnot mention neighborhood attention. The correct reference is:\n\n>Hassani, A., Walton, S., Li, J., Li, S. and Shi, H., 2023. Neighborhood attention transformer. \n>In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 6185-6194).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are encouraged by your positive feedback. Thank you for pointing out the incorrect citation; we will update the reference in our paper. We note that we do not compare with self-attention because the computational complexity of a global search makes self-attention impractical.\n\n**Q1.** Thank you for this detailed comment. We agree a more concrete comparison is needed. Since your comment is similar to reviewer 4VnB’s comment about SNA's implementation, we address this concern in more detail in the “Global Rebuttal”. In summary, we find SNA’s additional complexity does not scale with the number of features (F). This suggests SNA can be used efficiently within deep neural networks, since the number of features is a major factor of a network’s overall computational burden.\n\n**Q2.** Your summary is correct. The softmax expression in Equation 1 is applied over the superpixels connected to pixel i.\n\n**Q3.** I would not expect the non-square kernels of NA to significantly change this paper’s findings. Using the non-square kernels of NA would be similar to Hard-SNA. However, the non-square NA is restricted to rectangular regions rather than Hard-SNA’s deformable regions.\n\n**Q4.**  To evaluate runtime and memory usage, no other processes on the computer are running. The procedure is executed for each operator (SNA or NA), and the reported times are averaged over three runs. No major IO communication is included in the timed section of the program. Our procedure is as follows:\n```\na. The CUDA context is initialized with a non-measured CUDA function.\nb. The CUDA memory usage is reset and the CUDA cache is emptied.\nc. The CUDA device is synchronized with the host\nd. A timer is started\ne. The operator of interest (SNA or NA) is executed\nf. The CUDA device is synchronized with the host\ng. The timer is stopped. The time difference and peak memory usage are recorded\n```\n\nWe are open to modifying our benchmark procedure. For example, we will empty the CUDA Caching Allocator in step (b) by executing a `torch.cuda.memory.empty_cache()` command for our Pytorch script.\n\n**Q5.** Our implementation of SNA uses two operators within the NA package. First, the attention map is computed using code from NA. Second, the attention map is then re-weighted using SNA's superpixel weights. Third, the attention map is aggregated using code from NA. The dependency of SNA on NA modules suggests that SNA's performance will improve as NA's performance improves.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xsP6Oq0XKz", "reviewer": "Reviewer_4VnB", "summary": "This paper proposes a soft superpixel neighborhood attention (SNA). It proves that SNA is the optimum denoiser under Gaussian noise. Experiments show that SNA outperforms other local attention modules for the image denoising task.", "questions": "I am not sure that I understand the training process. It is claimed that the network is trained on BSD500, but do you train by adding noise to the image, and targeting the network to produce the clean, original image?", "limitations": "The hypothesis for the theory are clearly stated, and the limitation are acknowledged.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This is an interesting theoretical study, backed up with experiments.\n- It is refreshing to see some theoretical work submitted to Neurips\n- Using non-rigid boundaries instead of square neighborhood makes sense. \n- Results are promising", "weaknesses": "- Experiments are limited. The network that has been tested is written in Eq. (10).\n- The current implementation is slow. Some effort is needed to program an efficient version, but this is left for future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are encouraged by your positive feedback. We acknowledge our current prototype implementation of SNA is slower than NA. Your comment is similar to reviewer XzEJ’s comment about computational complexity, so we address this weakness in the “Global Rebuttal.”\n\n**Q1.** Your summary is correct. Gaussian noise is added to an image which is fed into the network. The network’s output is a denoised image, which is compared to the clean image using the Charbonnier loss (see the inline equation on line 191).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EBa1fOZnYq", "reviewer": "Reviewer_nsbe", "summary": "The paper proposes a new attention mechanism based on Soft Superpixel Attention. The main idea is to use superpixel segmentations directly in the attention module. The paper proposes rigorous proof that the proposed mechanism is the optimal denoiser. Results show an improved denoising performance.", "questions": "How difficult is it to incorporate the proposed attention mechanism in other downstream tasks?", "limitations": "Yes, this is discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* The paper presents an elegant and novel idea to use superpixels in the attention module.\n* It is well-written with clear explanations. I appreciate that parts that are less important for paper understanding are moved to the supplementary materials (e.g. proofs).\n* The experiments are sufficient with an improved performance over the state-of-the-art.", "weaknesses": "* The performance improvement is relatively small.\n* The paper would be much stronger if it could show how this attention module could be used in other tasks than only on denoising. For instance, deblurring, object detection, tracking, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are grateful for your positive feedback.\n\n**Q1.** In principle, SNA can directly replace (or augment, depending on your perspective) current NA modules for applications beyond image denoising. The practical restriction is our prototype (and slower) implementation of SNA, which makes training/fine-tuning networks needlessly expensive. Please see our “Global Rebuttal” for more details.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6ECdJKlLkG", "reviewer": "Reviewer_dwem", "summary": "The paper proposes soft superpixel neighborhood attention, with the motivation that attention is more efficient when it is local, and superpixels are better for local attention as patches, and furthermore, soft superpixels are more robust to errors than hard superpixels.", "questions": "see above", "limitations": "Limitations are addressed.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The idea of soft superpixel neighborhood attention makes sense. \n\nIllustrations in the paper are good and appropriate.", "weaknesses": "The technical novelty in the paper is not major.\n\nThe application (denoising) is not very appealing in the sense that it is not such an important application in the computer vision. It would be best to evaluate the proposed approach on some applications that are more widely used, such as semantic segmentation.\n\nThere is a theoretical contribution of optimality of the proposed denoiser is proven, but it assumes the proposed latent superpixel model, and it is not clear how true of the reality this proposed model is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments. We are encouraged to learn that you find our proposed method makes sense and that our illustrations are good and appropriate. \n\nWe are disappointed to learn you find image denoising not a significant enough task for publication.\n\nWe are also disappointed to learn you believe “the technical novelty of the paper is not major.” This belief appears to stem from your comment expressing concern about the reality of a latent superpixel model. In general, modeling assumptions do not match reality, so we do not understand why you find non-realistic modeling assumptions troubling. And without a reference, we are unsure why you find this paper lacking novelty.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Summary.**

We thank the reviewers for their thoughtful feedback. We are encouraged by the positive comments. 

Two reviewers comment favorably on the novelty of the paper. One reviewer states the approach is “unique” [XzEJ] and another reviewer states the idea is “elegant and novel” [nsbe]. Of the remaining two reviewers, one states the paper is an “interesting theoretical study” [4VnB] and both state our proposed method “makes sense” [4VnB,dwem]. One reviewer, dwem, claims “the technical novelty in the paper is not major”. However, dwem provides no direct explanation for their opinion and does not provide an alternative reference.

Three reviewers find the experimental results sufficient for publication. One reviewer notes our method is a “significant improvement from the baseline approach” [XzEJ]. Reviewer 4VnB states the “results are promising”, and reviewer nsbe states the “experiments are sufficient”.

**Compute Complexity.**

There is interest about the compute complexity of SNA. XzEJ states “the most considerable weakness is a lack of discussion on the computational complexity of the proposed approach”. A related comment from 4VnB states the “current implementation is slow”. To address these concerns about computation, we provide an analysis of SNA’s compute complexity in the attached pdf.

Table 1 in the attached pdf breaks down the computational complexity of each step in NA and SNA (equations 3 and 5). In summary, the FLOPs estimate for NA is O($[2F + 1]\cdot NK^2$) and for SNA it is O($[2F + 10]\cdot NK^2$). The peak memory consumption for NA is O($NF + NK^2$) and for SNA it is O($NF + 2\cdot NK^2$). Importantly, SNA’s additional complexity does not scale with the number of features (F). Since the number of features is a significant factor in the computational cost of an attention operator, it is sensible to believe SNA can be used efficiently within large-scale deep neural networks. To be concrete, if the number of features is 128 then there is less than a 4% percent increase in FLOPs from NA to SNA.

We will include Table 1 in the supplemental section of the paper.

**Why is SNA Only Demonstrated on Image Denoising?**

XzEJ notes “the impact of this approach extends beyond denoising and super-resolution applications”. This sentiment is echoed by nsbe and dwen, who express interest in applications of SNA beyond image denoising. They recommend incorporating SNA into deep neural networks for other computer vision tasks, such as “deblurring, object detection, tracking” [nsbe] and “semantic segmentation” [dwem]. Reviewer nsbe asks directly: “How difficult is it to incorporate the proposed attention mechanism in other downstream tasks?”

In principle, SNA can directly replace (or augment, depending on your perspective) current NA modules. The practical restriction is our slower, prototype implementation of SNA. This proof-of-concept implementation makes the already expensive task of training/fine-tuning needlessly more expensive. We believe properly optimizing SNA’s implementation is a worthy, separate research effort, and this optimization should be completed before investing resources into large-scale training. By demonstrating a significant improvement on image denoising, we hope to stimulate the community to work with us and make SNA possible for other tasks.

Meta-review: The paper has received three strong support, but one borderline reject rating that has concerns about the technical novelty, significance and impact of the topic. But the reviewer did not elaborate the concerns and interact with the authors. More discussions, explanations and clarifications have been provided to largely the satisfactions of the relevant reviewers.
Decision: Accept (poster)