单应计算加速数十倍、计算量减少95%！SKS和ACA矩阵分解被提出

本文由东华大学蔡棽副教授、上海交通大学严骏驰教授和中国科学院自动化所申抒含研究员共同指导并撰写，四名学生作者为东华大学视觉与几何感知实验室的吴展豪、郭凌希、王佳纯、张斯禹。

一、论文简介

东华大学、上海交通大学、中科院自动化所的研究团队最新提出：两种基于几何的单应矩阵分解，极大地减少了四点求解单应的计算量（相比目前通用的求解稀疏线性方程组方法减少 95% 以上），可在二维码扫描等典型视觉应用中显著减少计算消耗，并有望应用于其他射影几何、计算机视觉和图形学问题中。

论文已被 IEEE T-PAMI 期刊接收。

• 论文标题：Fast and Interpretable 2D Homography Decomposition: Similarity-Kernel-Similarity and Affine-Core-Affine Transformations
• 论文主页链接（含论文、代码、视频介绍、奖金激励）：http://www.cscvlab.com/research/SKS-Homography

二、问题介绍

以往的直接线性变换（Direct Linear Transformation, DLT）方法利用上述约束构建稀疏线性方程组进行单应求解，其中常用的一种非齐次线性方程组构建方法为：

三、本文方法

核心思想

基于几何变换的层次性（相似 - 仿射 - 射影），逐步利用部分点求出子变换，从而将单应矩阵分解为多个子变换完成分别求解并相乘。

• 【相似 - 相似射影核 - 相似（Similariry-Kernel-Similarity, SKS）变换】

ACA 变换是极其高效的，其计算单应矩阵的浮点运算次数统计见下表。在相差一个比例因子下单应计算共计 85 次浮点运算。表下方同时给出了一些计算量统计的细节（可通过其中加、减、乘号的数目进行统计）。

• 【正方形模板的简化】

当四个源点构成一个特殊形状，ACA 算法的计算过程可以进一步简化。以下算法展示了矩形（或正方形）模版与其图像间单应的计算过程，分别需要 47 和 44 次浮点运算。

四、实验结果

实验主要集中在评估 4 点单应求解器在不同场景下的运行时间，下面给出了 CPU 和 GPU 计算一个单应的平均运行时间对比。

更多的实验结果，如集成在 RANSAC 流程、集成在深度单应估计网络中求取单应，详见论文原文。

结果显示，使用双精度浮点数，ACA 分解完成一次四点单应计算的平均时间仅为 17 纳秒。与 DLT+LU 相比，SKS 和 ACA 在开启编译器默认的 O2 优化下分别实现了 29 倍和 43 倍的实际加速比。这两个数值远超理论上 FLOPs 的 11 倍和 20 倍比值，部分因为以往方法的实现涉及条件判断、数据拷贝等操作拖慢了执行速度，而这些操作并没有被 FLOPs 统计所覆盖。

五、总结与展望

作为一项几何视觉理论研究，本文提出的 SKS 与 ACA 方法可广泛应用于基于平面的视觉或图形学任务中。目前，研究团队在深度学习估计单应的几何参数、基于平面单应的 P3P 姿态估计、N 维单应矩阵分解等问题开展了后续研究，取得了一些初步成果。