Transformers have been successful in many vision tasks, thanks to their
capability of capturing long-range dependency. However, their quadratic
computational complexity poses a major obstacle for applying them to vision
tasks requiring dense predictions, such as object detection, feature matching,
stereo, etc. We introduce QuadTree Attention, which reduces the computational
complexity from quadratic to linear. Our quadtree transformer builds token
pyramids and computes attention in a coarse-to-fine manner. At each level, the
top K patches with the highest attention scores are selected, such that at the
next level, attention is only evaluated within the relevant regions
corresponding to these top K patches. We demonstrate that quadtree attention
achieves state-of-the-art performance in various vision tasks, e.g. with 4.0%
improvement in feature matching on ScanNet, about 50% flops reduction in stereo
matching, 0.4-1.5% improvement in top-1 accuracy on ImageNet classification,
1.2-1.8% improvement on COCO object detection, and 0.7-2.4% improvement on
semantic segmentation over previous state-of-the-art transformers. The codes
are available at this https URL

通过部分 Attention 性能的提升，QuadTree Attention 可以有效实现对密集预测的视觉任务，如物体检测和特征匹配，将计算复杂度从二次降至线性，具有比以往转换器更高的性能。