CVPR 2023 autofocusformer 核心部分翻译
| 前文摘要引言和部分方法见：乄洛尘的文章 |
| 代码链接见：https://github.com/apple/ml-autofocusformer |
3. 方法
在backbone中，从patch embedding module（2层步长为2的3x3 conv）开始，然后聚类算法（3.1节），然后几个局部注意力的transformerblocks（3.2节），然后新的自适应下采样模块（3.3节）。ps：分割头本文不说。
3.1 聚类和邻域
??一个局部邻域可以方便地通过在2D网格上切出一个正方形窗口来定义。与此形成对比的是,对于一个无序的点集,确定3D点云中的邻域的传统方法依赖于诸如k近邻(kNN)等算法,它计算点之间的成对距离。朴素的kNN算法具有二次时间复杂度。有趣的是,许多加速kNN的算法的第一步都是在给定的点上进行k-means聚类,以减少邻域搜索的空间。受此启发,我们也使用簇来定义局部邻域,即我们将tokens分为若干簇,并将邻域定义为包含几个相邻的簇。不幸的是,传统的聚类算法如k-means或局部敏感哈希并不直接适合我们的目的。首先,它们需要多次迭代或哈希轮数,因此相比深度网的前向传播而言速度较慢。更重要的是,它们导致的簇中点的数量不一。不均匀大小的簇导致需要用零填充的张量,这将浪费内存和时间。注意我们仅对2D位置进行聚类而不是更高的维度,我们提出一种平衡聚类方法来解决上述问题。
3.1.1 平衡聚类
??我们的方法不是采用传统的迭代方法,而是将图像上的2D位置排列成1D数组,然后将数组划分成等大小的组。为此,我们考虑了空间填充曲线,它将2D位置排列在1D线上,同时尽量保留2D距离测度。因此,在线上接近的点在2D空间中也比较接近。然而,由于从2D到1D的转换,完全保留2D度量是不可能的,如果我们直接利用空间填充曲线将tokens划分为簇,就会出现伪影。为了部分减轻这一问题,我们采用了2阶段过程进行聚类。其思想是仅在粗糙级别上利用空间填充曲线来获得稀疏、正则采样的2D图像位置的顺序。然后,根据与这些位置的2D距离对tokens进行排序。
??具体而言,我们首先将图像划分为粗糙的规则网格,其中的正方形补丁数量与预期的簇数量相似。我们将网格中每个正方形补丁的中心称为空间填充锚点。空间填充曲线在锚点之间建立顺序。给定此顺序,对于属于锚点ai ∈ R2的位置p ∈ R2的tokens,我们可以定义其前一个锚点
a
i
?
1
a_{i?1}
ai?1?和下一个锚点
a
i
+
1
a_{i+1}
ai+1?。然后,我们通过对所有tokens
p
p
p计算从tokens
p
p
p到这两个锚点的距离比率r来计算。
r
(
p
)
=
d
i
?
1
(
p
)
d
i
+
1
(
p
)
=
∥
p
?
a
i
?
1
∥
2
∥
p
?
a
i
+
1
∥
2
r(p) = frac{d_{i?1}(p)} {d_{i+1}(p)} = frac{∥p ? a_{i?1}∥_2}{∥p ? a_{i+1}∥_2}
r(p)=di+1?(p)di?1?(p)?=∥p?ai+1?∥2?∥p?ai?1?∥2??
??现在,在每个正方形补丁内,我们按r的升序对tokens进行排序,使得接近前一个锚点的tokens排在前面。此过程因此建立了所有tokens的顺序。最后,为了获得平衡的聚类,我们简单地将数组划分成等大小的组。图3说明了整个算法。
??因为我们可以在O(1)时间内通过简单量化它们的坐标来找到每个tokens对应的空间填充锚点,所以聚类的总体时间复杂度不超过对局部补丁中的所有tokens位置进行一次排序,与网络的时间复杂度相比可以忽略不计,因为没有涉及到特征通道。注意,聚类算法只需要在每个阶段开始时执行一次,簇信息可以用于该阶段的所有注意力块以及末端的下采样模块。与先前的平衡聚类工作不同,该算法不是迭代的,并产生完全平衡的簇。它也保证每个tokens只属于一个簇,不同于RoutingTransformer,其中一些tokens可能不属于任何簇。但是,请注意我们的平衡聚类仅适用于低维点。在这项研究的早期阶段,我们探索了使用嵌入特征而不是仅2D位置进行聚类,但性能差异可以忽略。因此,我们决定仅对位置进行聚类,这使我们能够利用所提出的算法生成完美平衡的簇。
3.1.2 聚类中的邻域
??为了促进整个图像中的信息流动,重要的是注意力不应仅限于同一簇内的位置。例如,在Swin Transformers中,连续层之间的窗口移动允许像素在不同层中关注不同的邻居。然而,在我们的情况下,对每一层重新进行聚类会增加不必要的计算量。因此,我们选择使用较小的簇,并允许每个tokens关注来自附近R个簇的tokens。为实现这一点,我们使用的邻域大小是簇大小的几倍。这是有利的,因为邻域是重叠的,保证了簇之间的信息交换。
3.2 Transformer Attention Blocks
??在任何阶段,设tokens数量为N,每个tokens的邻居数量为M,头数为H,特征通道数为C。具有相对位置嵌入的单个头的局部注意力A通过每个tokens关注其邻域中的所有其他tokens来计算,即
A
=
s
o
f
t
m
a
x
(
Q
K
T
+
P
)
,
A = softmax(QK^T + P),
A=softmax(QKT+P),
??其中
Q
∈
R
N
×
C
/
H
,
K
∈
R
M
×
C
/
H
,
A
∈
R
N
×
M
,
P
∈
R
N
×
M
Q ∈ R^{N×C/H},K ∈ R^{M×C/H},A ∈ R^{N×M},P ∈ R^{N×M}
Q∈RN×C/H,K∈RM×C/H,A∈RN×M,P∈RN×M 分别是查询、键、注意力和位置嵌入矩阵,且
P
i
,
j
=
w
(
p
i
?
p
j
)
.
P_{i,j} = w(pi - pj).
Pi,j?=w(pi?pj).
??这里，
p
i
pi
pi,
p
j
pj
pj是两个相邻tokens的(x,y)坐标,
w
w
w(·)是一个返回该头的标量位置嵌入的函数。对于固定形状邻域的模型,相对位置嵌入可以存储在矩阵中,并在需要时读取。但是对于我们的模型,邻居的位置事先是未知的,因此我们需要通过可学习函数将坐标差投影到位置嵌入中。我们用一个全连接层实现
w
w
w。
3.3 Adaptive downsampling
??在每个阶段的末尾,除了最后一个阶段,我们采用一个下采样模块。下采样模块包含两部分,一个用于选择最重要tokens的可学习评分组件,以及周围选定tokens的邻域合并步骤。
3.3.1 Learnable Importance Score
??我们学习预测每个token i的标量分数si,以指示其相对于任务损失的重要性。学习该分数的主要困难在于下采样限制了选定tokens的数量。如果任务损失仅反向传播到选定的tokens,则未选定的tokens可能不会接收到任何梯度。为了向所有tokens反向传播梯度,我们提出学习每个token的重要性分数与邻域合并过程结合。
??具体而言,假设我们正在合并一个特定位置
p
c
p_c
pc?处token周围的邻域
N
(
p
c
)
N(p_c)
N(pc?)。类似于注意力块的邻域
N
(
p
c
)
N(p_c)
N(pc?)从其最近的R个簇获得,第i个邻居token表示为一个元组
(
p
i
,
f
i
)
(pi, fi)
(pi,fi),其中位置
p
i
=
(
x
i
,
y
i
)
pi = (xi, yi)
pi=(xi,yi),特征
f
i
∈
R
C
fi∈R^C
fi∈RC。在邻域内,合并使用PointConv层的修改版本执行,如下所示:
f
m
e
r
g
e
d
(
p
c
)
=
v
e
c
（
∑
(
p
i
,
f
i
)
∈
N
(
p
c
)
σ
(
l
(
f
i
)
)
?
S
i
?
W
(
p
i
?
p
c
)
f
i
?
）
U
,
f_merged(p_c) = vec（sum_{(pi,fi)∈N (p_c)}overbrace{σ(l(fi))}^{S_i}·W(p_i ? p_c)f_i^?）U,
fm?erged(pc?)=vec（(pi,fi)∈N(pc?)∑?σ(l(fi))