Transformer模型可以捕获长距离依赖和全局信息。引入计算机视觉任务后，大部分都取得了显着的性能提升。但是Transformer的缺点还是无法避免：时间和空间复杂度太高，都是输入序列长度的二次方。通常，输入图像被划分为小块，然后这些小块被展平成令牌序列并发送给Transformer。序列越长，复杂度越高。因此，为了在许多视觉任务中使用Transformer，选择将其应用于低分辨率或将注意力机制限制在局部图像上。但是，在高分辨率下应用Transformer可以带来更广阔的应用前景和性能提升。因此，许多工作都在研究和设计有效的Transformer，以降低计算的复杂度。有学者提出了线性逼近Transformer，用线性的方法逼近标准Transformer。然而，实验结果表明，这些线性Transformer在视觉任务中的表现相对较差。为了降低计算成本，PVT使用下采样的键和值，这降低了模型捕获像素级细节的能力。相比之下，SwinTransformer通过限制全局注意力的交互信息来减少计算量。与之前的工作不同，西蒙弗雷泽大学和阿里巴巴AI实验室的研究人员提出了一种新的注意力机制QuadTreeattention，建立了一种由粗到细的注意力机制，可以同时包含全局交互和细粒度信息，并将时间复杂度降低到线性。论文已被ICLR2022录用。论文地址：https://arxiv.org/abs/2201.02767代码地址：https://github.com/Tangshitao/QuadTreeAttention当我们看一张图的时候，我们可以发现大部分图像领域是无关紧要的。所以我们可以构建一个代币金字塔，以由粗到细的方式计算注意力。这样，如果相应的粗层次区域不相关，我们也可以快速跳过细层次无关区域。例如，第一层计算图像A中蓝色区域的attention，即计算图像A中蓝色patch和图像B中所有patch的attention，选择前K个patch，同时对这些patch进行标记蓝色表示它们是相关区域。在第二层，对于图像A中第一层蓝色块的四个子块，我们只计算它们与第一层图像B中前K个块对应的子块的注意力，而注意力所有其他色调的子补丁都被跳过以减少计算。我们用黄色和绿色表示图像A中的两个块，它们在图像B中对应的前K个块也以相同的颜色突出显示。整个过程在第三层迭代进行，这样既可以获得精细的注意力又可以保留长距离依赖连接。最重要的是，整个过程只需要计算少量注意力。因此，该方法具有较低的内存消耗和计算成本。在实现上，研究人员使用四叉树的数据结构来构建注意力机制。和传统的attention机制一样，embeddings先被映射到Q，K，V。然后用一个poolinglayer或者卷积层，kernelsize为2x2对它们进行多次downsample，构建tokenpyramid。从最厚的层开始，每一层只选择注意力得分最高的K个patches参与下一层的计算。根据不同的计算方法，设计了两种机制：QuadTree-A和QuadTree-B。在QuadTree-B方法中，对于最厚的层，只需要根据attention公式计算即可。对于剩余的层，从上一层中选择注意力得分最高的k个patch，然后计算消息传递。最后，可以合并每一层的信息，其中w_i是第i层的可学习参数。实验结果寻找不同图像之间的特征对应关系是经典的3D计算机视觉任务，通常的评估方法是相机位姿估计在对应点的准确性。研究人员使用了最近提出的SOTA框架LoFTR，其中包括基于CNN的特征提取器和基于Transformer的匹配器。为了验证QuadTreeTransformer的效果，研究人员将LoFTR中的线性transformer换成了QuadTree。此外，文章中实现了新版本的LoFTR，用于与空间缩减（SR）注意力进行比较。研究人员在包含1513个场景的ScanNet上进行了实验。QuadTreeTransformer的参数采用三层金字塔，最粗分辨率为15×20像素。参数K在最精细的级别设置为8，在较粗略的级别加倍。对于SR注意力，值和关键令牌平均池化为8×8的大小，以确保与QuadTree注意力相似的内存消耗和触发器。从（5°，10°，20°）相机位姿误差的AUC实验结果可以看出，SRattention与linearTransformer取得了相似的结果。相比之下，QuadTreeA和QuadTreeB在很大程度上优于线性Transformer和SRattention，而Quadtree-B的整体表现优于Quadtree-A。为了进一步提升结果，研究人员还训练了一个K=16的模型，可以看出模型的性能得到了进一步提升。在双目视差估计（立体匹配）任务中，目标是找到两幅图像之间对应线上的像素。最近的工作STTR将Transformer应用于对极线之间的特征点，并实现了SOTA性能。在将STTR中的标准Transformer替换为QuadTreeTransformer后，在SceneFlowFlyingThings3D合成数据集上进行了实验，该数据集包含25,466张图像，分辨率为960×540。研究人员建立了一个四层金字塔来评估QuadTreeAttention。实验结果可以看到非遮挡区域的EPE（End-Point-Error）和遮挡区域的IOU（Intersection-over-Union）。该表还包括计算复杂性。并且还报告了内存使用情况。与基于标准Transformer的STTR相比，QuadTreeTransformer实现了相似的EPE（0.45pxvs0.46px）和更高的遮挡估计IOU，但计算和内存成本低得多，只有52%的FLOP和63%的内存消耗。研究人员还测试了QuadTreeTransformer在基本自注意力任务上的性能。首先，从图像分类任务在ImageNet上的实验结果可以看出，基于PVTv2模型，用四叉树attention代替spatialreductionattention可以在ImageNet上达到84.0%的top1准确率。该模型比PVTv2高出0.4-1.5个百分点。从COCO目标检测数据集的实验结果可以看出，对于QuadTreeAttention来说，很小的K就足以捕捉到从coarse-to-fine的信息。因此，在使用高分辨率图像时可以减少更多的计算。而QuadTree-B实现了更高的性能，同时flops比PVTv2少得多，性能也超过了ResNet和ResNeXt。QuadTree-B-b2的性能分别比ResNet101和ResNeXt101-32x4d高7.7AP和6.3AP，主干flops减少了约40%。在ADE20K的语义分割实验中，在相似的参数量和flops下，比PVTv2高0.8-1.3。作者介绍唐诗涛，目前是西蒙弗雷泽大学三年级博士生。他的主管是谭平。他的研究方向是深度学习和3D视觉。在ECCV、ICCV、CVPR、ICML、ICLR等会议上发表多篇论文。合著者张家辉目前是阿里巴巴的一名算法工程师。2020年，他将获得博士学位。来自清华大学。研究方向为3D重建和3D深度学习。博士期间曾在英特尔中国研究院和香港科技大学实习或交换生。在ECCV、ICCV、CVPR、ICLR、TPAMI、TVCG等会议或期刊发表多篇论文。阿里云人工智能实验室算法组组长朱思宇博士。他获得了博士学位。来自香港科技大学。在攻读博士学位期间，他与他人共同创立了3D视觉公司Altizure。朱思雨博士在ICCV、CVPR、ECCV、PAMI等国际计算机视觉学术会议和期刊发表论文30余篇。谭平，目前在阿里巴巴XR实验室工作，曾任西蒙弗雷泽大学终身副教授，新加坡国立大学副教授。主要研究兴趣包括计算机视觉、计算机图形学、机器人学、3D重建、基于图像的建模、图像和视频编辑、照明和反射建模。
