顶级期刊TPAMI论文解读│计算机视觉的几何基础：快速且可解释的单应计算方法

本推文详细介绍了一篇东华大学计算机科学与技术学院蔡棽副教授建立的视觉与几何感知实验室的最新论文《Fast and Interpretable 2D Homography Decomposition: Similarity-Kernel-Similarity and Affine-Core-Affine Transformations》，该论文发表在人工智能领域的顶级期刊《IEEE Transactions on Pattern Analysis and Machine Intelligence》。该论文由东华大学蔡棽副教授、上海交通大学严骏驰教授和中国科学院自动化所申抒含研究员共同指导，学生作者为吴展豪、郭凌希、王佳纯、张斯禹。在本研究中，为了解决传统单应计算方法里需要特殊的基元配置、计算复杂度较高，以及缺乏几何意义、计算效率未得到充分发掘的难点问题，论文提出了两种快速且可解释的二维单应分解方法。其中，所提出的ACA方法仅用85次浮点运算（FLOPs）就可以计算出相差一个比例因子的单应矩阵，甚至不需要任何除法运算。本研究从对比单应求解算法在CPU上的运行时间、基于特征匹配的RANSAC流程中的单应运行时间等多个维度证明了所提出方法的有效性。并且，SKS和ACA方法由于计算高效，可无缝集成到传统的单应估计流程和深度单应估计流程中。相关的代码均已开源。

本推文由王淑婷撰写，审校为蔡棽老师，由蔡棽老师授权分布。

论文链接：https://arxiv.org/abs/2402.18008

代码链接：https://github.com/cscvlab/SKS-Homography

论文主页：http://www.cscvlab.com/research/SKS-Homography/

1.期刊介绍

IEEE Transactions on Pattern Analysis and Machine Intelligence（TPAMI）是人工智能领域的旗舰级学术期刊，由国际电气和电子工程师协会（IEEE）创办于1979年，长期引领模式识别、计算机视觉和机器学习等方向的前沿发展，被公认为人工智能领域最具影响力的顶级期刊之一。TPAMI被中科院JCR分为一区TOP期刊，CCF-A类期刊，近五年影响因子高达22.2。TPAMI期刊以其严苛的学术标准、跨领域的研究深度和广泛的工业影响力，成为全球人工智能研究者追求学术突破的核心阵地。

2.研究背景及主要贡献

(1)研究背景

平面单应，也被称为二维射影变换，是《计算机视觉中的多视图几何》这本经典计算机视觉教材第1-4章主要介绍的基础概念，在各种几何视觉任务中起着至关重要的作用。以往的4点单应计算方法首先遵循直接线性变换（Direct Linear Transformation, DLT）法构建线性方程组，然后采用不同的线性代数求解器进行计算，并提高所构建线性系统的计算效率。但这些方法均有各自的缺陷，比如计算冗余较高，缺乏几何解释，或需要特殊的基元配置等。基于此，本文提出了两种快速可解释的二维单应矩阵分解方法，分别称为相似-相似核-相似（Similariry-Kernel-Similarity, SKS）变换和仿射-仿射核-仿射（Affine-Core-Affine, ACA）变换。这两种方法分别利用若干锚点计算对称的相似变换或仿射变换，再通过剩余点对计算反映图像射影畸变的核变换。其中，分解的各个参数均有明确的几何解释，且仅通过矩阵运算实现对单应的快速高效求解。分析可知，ACA可以在只有85个浮点运算（FLOPs）的情况下计算包含尺度的单应矩阵，且没有任何除法操作。经过实验表明，ACA算法在CPU上每秒可执行约70M次，在GPU上每秒可执行4G次。这一显著的计算优势使得本文提出的算法能够无缝集成到传统的基于特征点的RANSAC流程以及深度单应流程中，替换它们的默认四点单应矩阵求解器。

(2)主要贡献

（1）创新性的提出了用于单应矩阵分解的相似-相似核-相似（SKS）变换和仿射-仿射核-仿射（ACA）变换，并以一种统一的方式计算仿射变换。

（2）在几何方面，SKS或ACA的每个子变换，包括其中的每个参数，都有明确的含义。具体地，SKS或ACA中的源和目标变换分别对称地归一化源平面和目标平面，而中间变换决定了两个归一化平面之间的射影畸变。

（3）在代数方面，SKS在计算效率上显著优于之前所有的4点单应计算方法。此外，ACA只需要97个FLOPs，分别是最先进（SOTA）方法GPT-LU和NDLT-SVD的5%和0.4%。

（4）SKS或ACA可以集成到传统的基于特征点提取与匹配的RANSAC流程中，以替换其默认的4点单应求解器。同时，张量化的ACA（TensorACA）由于其简洁的单应表达式和少量的向量操作，也适用于深度单应估计流程的集成。

3.方法

(1)总体思路

图1 以往的四点单应计算方法与本文提出的SKS、ACA方法思路的比较

如图1所示，以往的4点单应计算方法首先通过叉乘运算消除点对应关系中的齐次等式约束，根据每个点对应关系可推导出两个关于单应矩阵的线性方程  ，通过将四个点对应关系提供的八个线性方程进行组合，即可构建出一个线性方程组  。随后，可以使用一种矩阵分解方法来求解此线性系统。而本文提出的方法是使用2或3个点计算相似变换或仿射变换，剩余的点则用于处理残存的射影畸变，通过直接解析单应矩阵内部的子变换实现突破性创新，无需构造线性方程组，且涉及的计算量也非常少。

（2）SKS分解

图2 SKS分解中的子变换

具体来说，SKS方法的第一步是分别利用两组点，例如  和  ，在各自的平面上计算出唯一的相似变换，如图2的左半部分。由  和  上的这两组点对应关系所计算出的相似变换分别记为  和  。在相似变换下，这两组点将被变换为齐次坐标下定义的两个标准点  （默认将M和N分别设置为x轴的负方向和正方向）。所选取的这两组点被称为两个锚点（TAP），因为它们在将所有平面点归一化到一个新的平面直角坐标系中起到了重要作用，这两个点  被称为标准TAP。单应矩阵中剩余的未知分量被称为相似核变换  ，在  的作用下标准TAP  应保持不变。此外，可以利用另外两组对应点来计算同样具有4个自由度的  。 和  不会改变两个平面上四边形的形状。因此，  变换引入了实际的射影畸变，这里  表示一个初等变换，将标准点变为直角双曲点；  表示双曲相似变换，并可分解为两个平移，及表示双曲尺度和旋转的  。

（3）ACA分解

图3 ACA分解中的子变换

ACA变换与上述SKS变换类似。设定标准三锚点为  ，源平面  和目标平面  上的三个点可分别用于计算各自平面上具有6个自由度的仿射变换。与SKS类似，在获得源平面和目标平面上的仿射变换后，可以得到一个包含三个子变换的单应分解。如图3所示，在  和  作用下，平面  和  分别变换为两个新平面  和  。  和  之间的射影变换记为   。具有2个自由度的  可通过第四组点对应  在  和  作用下的  变换结果计算得到。因此，在两个仿射归一化平面之间引入了射影畸变，也称作仿射核变换。

（4）计算量（浮点运算次数）统计

图4 SKS方法的浮点运算次数统计及各主要步骤的次数示例

图5 ACA方法的浮点运算次数统计及各主要步骤的次数示例

由于本文所提出的方法求解单应表达式和计算过程简洁，SKS的每个步骤仅需少量浮点运算，具体数值如图4所示。SKS中这些步骤的FLOPs总和为157次。若需要进行单应矩阵归一化，则需额外进行一次除法和八次乘法运算，总计增12次FLOPs。与对SKS方法的分析类似，在图5中给出了ACA方法各步骤的浮点运算次数。若不考虑最终归一化步骤，ACA仅需85次 FLOPs 即可计算出含比例因子的单应矩阵。

4.实验及结果

（1）实验配置

由于论文所提出的SKS和ACA方法针对最小条件下的单应矩阵计算问题，因此实验主要集中在评估4点单应求解器在不同场景下的运行时间。这里给出了CPU计算单个单应的运行时间和在合成数据集和真实数据集下RANSAC流程估计单应的时间。下表列出了详细的硬件和软件配置。

表1 实验环境配置信息

（2）实验结果

表2 四点单应计算求解器的CPU平均运行时间（单位：微秒）

第一个实验利用四组对应点对单应求解器于CPU上的运行时间进行测试。程序在CPU上以Release模式运行，并结合编译器优化选项Od、O1与O2开展测试工作。优化选项O1和O2借助包含向量化技术在内的多种优化策略，分别达成代码的最小化及运行速度的最大化目标。向量化作为一种单指令多数据的处理形式，可实现数据的并行处理，提升运算效率。而Od选项则是关闭所有编译器优化功能，程序代码按顺序逐一执行。鉴于过往求解器代码常采用双精度浮点数或单精度浮点数，本文所提出的SKS与ACA方法同样运用这两种浮点数，并分别以符号(**)和(*)表示。

表2展示了所有算法在CPU上运行10M次的平均运行时间。结果表明：

（1）与三种鲁棒方法NDLT-SVD、HO-SVD和GPT-LU相比，SKS(**)和ACA(**)在O2优化下分别实现了{488×, 477×, 29×}和{731×, 713×, 43×}的实际加速比，远超理论上FLOPs的加速比，主要因为三种鲁棒方法涉及大量条件判断、数据拷贝等操作拖慢了执行速度；

（2）SKS(*)在O2优化下明显快于RHO-GE，而ACA(*)耗时仅为RHO-GE的一半，实现了约70M次/秒的单应矩阵计算。SKS和ACA的运行时间与理论FLOPs结果基本一致。无论是在传统基于特征的RANSAC单应估计流程中，还是在深度学习单应估计流程中，这种显著的加速对于图像间的单应估计任务具有重要意义。

表3 特征提取与匹配框架中各阶段的平均运行时间（单位：微秒）

第二个实验将SKS与ACA作为插件模块集成至传统RANSAC单应估计流程，分五阶段进行性能评估（特征提取、描述子匹配、RANSAC迭代中的单应计算和验证、全局优化）。表3展示了在三种特征点提取方法和两种外点剔除框架的6种组合下的平均运行时间。总体而言，在4点单应计算阶段，相较于默认的求解器NDLT-SVD和GPT-LU，SKS和ACA极大缩短了运行时间。但SKS和ACA对整体流程的加速效果较为有限，因为运行速度的主要瓶颈在于特征提取和粗匹配，且MS-COCO数据集中的合成图像对通常具有较高的内点比率和较少的单应计算循环次数。当采用ORB特征点提取方法和经典RANSAC框架时，替换默认求解器NDLT-SVD为ACA可节省约204微秒。相比于原始总运行时间6.20k微秒，改进后的流程实现了约3%的加速效果，相应的运行时间比为97%。

图6 真实动态数据集与合成数据集关于内点比率与运行时间比率的对比

针对MS-COCO数据集中高内点率（理想光照/纹理条件）的局限性，本研究进一步在动态真实数据集（33个视频/2024对图像）上测试算法鲁棒性。采用ORB-SLAM3使用的ORB+RANSAC组合，对比ACA与NDLT-SVD求解器性能。

图6展示了真实动态数据集与合成数据集的内点比率和运行时间比率的分布情况。从图中可以看出，相较于MS-COCO数据集，真实动态数据集中的内点比率和运行时间比率显著降低，此时应用本文提出的快速单应计算方法具有较明显的实际价值。

5.总结与展望

论文创新性地提出两种基于几何的单应矩阵分解方法——SKS分解与ACA分解，实现了计算效率的突破性提升，同时赋予每个参数明确的几何意义。ACA分解相较SKS分解进一步提高了单应计算效率，只需要97个FLOPs（若与尺度无关则仅需85个FLOPs）。实验表明，本文提出的ACA算法可以在CPU上执行大约70M次，在GPU上执行4G次。这种巨大的计算优势使所提出的算法能够集成到传统基于特征的RANSAC和深度单应估计流程中，取代其默认的4点单应求解器。此外，所提出的基于锚点的方法为平面基元提供了统一的解决方案，如SAP分解的扩展和二维仿射变换的计算。其他优点的实际应用，例如将每个单应元素的直接表达式作为输入坐标的多项式及其几何参数化，值得在未来的工作中进行研究，并将继续探索SKS/ACA在n点单应估计、多视图几何等视觉任务中的应用。

如希望进一步了解论文的基本原理，您可以观看论文的解读视频。