快速BnB算法：三维点云配准的平移-旋转分离优化

本文主要探讨了在三维刚性点云配准这一关键任务中的高效全局优化方法，特别关注于基于平移搜索的快速分支定界(BnB)算法。三维点云配准在计算机视觉、机器人学以及数字医学等领域具有广泛应用，特别是在SLAM和计算机辅助定位与映射中，当相对运动大或重叠区域小，局部方法往往难以胜任，这时就需要全局优化策略。 文章的主要创新点在于将复杂的六维SE(3)参数空间优化分解为两个独立的过程：首先，针对全局平移参数，提出了一种快速的BnB算法进行优化，这种方法有效解决了传统BnB优化在高维空间中时间复杂度呈指数增长的问题。接着，通过利用BnB算法得到的全局最优平移，引入一种新的旋转不变特征，实现了平移和旋转的分离优化。这种方法避免了在高维空间中直接优化带来的效率瓶颈，使得在处理具有挑战性数据集时，能够在速度和准确性上超越现有最先进的全局方法。 作者团队，包括刘银龙、王晨、宋志坚和王曼宁，来自复旦大学基础医学院数字医学研究中心及上海市医学影像计算与计算机辅助介入重点实验室，他们在三维点云配准技术上有深入研究。他们借鉴了先前工作[6]中关于SE(3)分解优化的思路，但在此基础上，他们发展出更为高效的策略，以适应实际应用中的性能需求。 总结来说，本文的核心贡献是提出了一种通过解耦旋转和平移优化，结合新设计的旋转不变特征和快速BnB算法，显著提升三维点云配准的全局优化效率。这不仅在理论上提升了算法的理论效率，而且在实际应用中也展示了优越的性能，对于推动计算机视觉和机器人领域的研究具有重要意义。