引用本文

张伟, 黄卫民. 基于种群分区的多策略自适应多目标粒子群算法. 自动化学报, 2022, 48(10): 2585−2599 doi: 10.16383/j.aas.c200307

Zhang Wei, Huang Wei-Min. Multi-strategy adaptive multi-objective particle swarm optimization algorithm based on swarm partition. Acta Automatica Sinica, 2022, 48(10): 2585−2599 doi: 10.16383/j.aas.c200307

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200307

关键词

计算机视觉，PnL问题，位姿估计，视觉导航 

摘要

现有Perspective-n-line (PnL)问题求解算法无法在获得高求解精度的同时保证高求解效率. 为解决这个缺点, 提出了同时兼具求解效率和求解精度算法EPnL. 该方法首先将PnL问题转换为求二次曲面方程组交点的问题, 然后利用单位四元数中变量不同时为零的特性, 分类参数化PnL问题中的旋转矩阵. 最后, 为克服常规优化方法可靠性和效率较低的问题, 同时兼具求解效率和求解精度算法利用二次曲面方程组自身的结构信息, 采用低次项参数化高次项的方式将二次曲面方程组的求解问题转换为单变量多项式的求解问题. 实验表明, 相比于现有算法, 该算法在具有高求解精度的同时也兼具有高求解效率.

文章导读

基于直线特征的摄像机绝对位姿估计问题在计算机视觉领域称之为Perspective-n-line (PnL)问题, 目的是通过目标物体上的n条已知直线和其所对应的图像投影来计算相机和目标之间的相对位置和姿态关系. PnL问题是视觉导航[1-2]、机器人视觉定位[3]、传感器标定[4]、现实增强[5] 等领域中的关键核心问题之一. 到目前为止, 现有解决PnL问题的方法可以粗略分为迭代法和非迭代法:

迭代法将PnL求解问题转换为非线性最优化问题, 并利用Gauss-Newton法或Levenberg-Mar-quardt法[6]迭代求解这个非线性最优化问题. 然而, 迭代法对初值的选取比较敏感, 初值选择不合理将导致迭代法收敛速度较慢, 影响算法的实时性. 除此之外, 当使用特征直线较少的时候, 迭代法容易陷入局部最优, 影响PnL问题求解的精度和可靠性.

在非迭代法中, 最直接的当属直接线性变换(Direct linear transformation, DLT)方法[7]. DLT方法简单高效, 但抗噪能力不强, 在空间参考直线较少的情况下求解精度不高. Přibyl等[8]通过将直线在欧氏空间的坐标表示转换到普吕克(Plücker)空间, 提出了解决PnL问题的DLT-Plücker-lines方法. 相比于DLT算法, DLT-Plücker-lines算法具有更好的抗噪能力和求解精度, 但其求解时需要至少9条以上的空间参考直线. 随后, Xu等[9]通过借鉴Perspective-n-point (PnP)算法原理, 提出了一系列线性求解PnL的方法, 但这些方法仍需要6条以上的空间参考直线才可以求解. 最近, Přibyl等[10]基于DLT的方法, 提出了DLT-combined-lines的方法, 该方法将线性求解PnL问题的直线数目缩减到了5条. DLT-combined-lines方法求解效率高, 在直线数目较多的时候, 具有很高的求解精度, 但是在直线数目较少的情况下, 求解精度较差.

虽然直接线性求解PnL的方法具有简单、效率高的特点. 但是由于其抗噪能力差、不适合参考直线较少的情况(尤其不适合参考直线少于6条以下的情况). 为了克服这些问题, Ansar等[11]将PnL问题转换为非迭代优化 开发了一种通用的PnL求解算法, 该算法能够处理从4到n条所有的空间参考直线. 然而, 文献[11]算法在空间直线较少的时候求解精度不高, 这主要是因为其最优化求解过程中采用了线性化的策略. 为了提高PnL算法的求解精度, Mirzaei等[12]提出了一种直接求解PnL问题全局最优解的方法, 通过Cayley参数的方式参数化旋转矩阵, 然后通过矩阵分解和合成的方式, 将PnL位姿测量问题转换为最优化问题, 最后通过矩阵合成技术求解这个最优化问题, 得到PnL问题的解. 然而, 文献[12]的方法由于使用了Cayley参数表示旋转矩阵, 求解过程中容易出现矩阵奇异值, 导致求解稳定性不好. 为了克服这个问题, Zhang等[13]提出了RPnL方法求解PnL问题, 该方法将空间参考直线三条线为一组, 然后利用Perspective-3-line (P3L)约束构建多项式方程组来求解PnL问题. 然而, RPnL是一种次优化的方法, 其求解精度还有提升的空间. 2017年, Xu等[9]改进了RPnL方法, 提出了ASPnL算法. 到目前为止, ASPnL是求解精度最高, 最稳定的PnL算法之一. 然而, ASPnL随着直线数量的增加, 其求解消耗时间将快速增长, 不利于其应用在实时性较高的任务中. 2019年, Wang等[14]对RPnL算法增加优化步骤, 并且使用矩阵化的方式替代RPnL算法中的循环步骤, 提出了改进的SRPnL算法, 该算法求解精度和可靠性类似于ASPnL算法, 但效率远高于ASPnL算法.

从以上文献分析可以看出, 线性求解PnL问题的方法效率高, 但精度低, 通常无法适用于直线数量小于6的情况. 非线性求解PnL的方法适应性较广(适应4 ~ n条直线求解), 求解精度高, 但是求解过程复杂, 效率低下. 针对以上问题, 本文提出了一种同时兼具求解效率和求解精度的方法(命名为EPnL方法). 本文的主要贡献有:

1)提出了分类表示旋转的方法: 最近的PnL问题求解中多使用Cayley参数[13-15]和四元数表示[16]旋转, 然而利用Cayley参数求解PnL问题容易出现奇异值, 导致求解结果不稳定. 利用四元数表示旋转则存在解的符号模糊问题, 会增加PnL问题求解的复杂性, 降低求解效率. 针对以上缺点, 本文基于四元数参数中变量不同时为零的特性, 提出了分类表示旋转的方法, 在保证不损失旋转正交约束信息的前提下, 避免了Cayley参数求解奇异性和四元数参数对解符号模糊的问题, 提升了求解PnL问题的可靠性和效率.

2)将PnL问题转换为了二次曲面(曲线)方程组求交点的问题: 本文首先通过矩阵变化的方式统一求解参数的度量空间, 消除求解参数度量空间不同可能引起的算法不稳定因素. 然后, 不同于现有文献[12-14]直接最优化求解PnL问题的方式, 本文基于1)中分类表示旋转的方法, 将PnL问题转换为二次曲面(或曲线)求交点的问题来解决, 有效地降低了PnL问题求解的复杂度.

3)利用方程组低次项参数化高次项的方式将复杂二次曲面(曲线)方程组求交点问题转换为单变量多项式求解问题: 针对迭代法求解耗时且容易陷入局部最优, 而Gröbner基方法[17]求解复杂, 无法保障可靠性的问题. 本文利用二次曲面方程组自身的结构信息, 将方程组划分为高次项和低次项部分, 并通过引入恒等式的方式将高次项用低次项表示, 最终将复杂的多变量二次曲面求解问题转换为简单的单变量多项式(最高为8次)求解问题来解决. 同时, 本文利用少量Gauss-Newton法对结果进行精定位, 以进一步提升最终的求解精度.

4)本文提出的算法实现了求解精度和效率的统一. 实验部分选择和主流及最新的PnL算法对比, 结果表明, EPnL适用于3 ~ n条直线的位姿求解, 具有通用性. 在所有对比算法中, EPnL算法求解精度最高, 效率仅次于线性DLT的方法(排名第2). 本文中所有方法的源代码已公布1, 读者可以下载验证.

图 1  PnL问题

图 2  当直线数目变化时旋转和平移误差的均值和中值

图 4  最小情况下(n = 3)旋转和平移误差的均值和中值

本文提出了一种精确且高效的PnL问题求解算法(EPnL算法). EPnL首先通过矩阵变化的方式统一PnL问题的度量空间, 并将PnL求解问题转换为求二次曲面(曲线)交点的问题. 然后, 针对现有Cayley参数和四元数参数表示旋转时存在的问题, 本文提出了基于四元数的旋转分类表示方法, 该表示法在不损失旋转正交约束的前提下, 能够有效提升求解PnL问题的可靠性和效率. 最后, 针对现有迭代法和Gröbner基法求解问题效率不高且无法保障可靠性的问题. 本文提出利用二次项曲面方程组低次项参数化高次项的方法, 将二次项曲面方程组求交点问题转换为单变量多项式求解问题解决. 仿真和实际实验表明, 相比于现有的PnL算法, 本文算法在具有高求解精度的同时兼具高求解效率.

作者简介

王平

兰州理工大学电气工程与信息工程学院讲师. 2019年获南京航空航天大学博士学位. 主要研究方向为计算机视觉, 机器学习和信号处理. 本文通信作者. E-mail: pingwangsky@163.com

何卫隆

兰州理工大学电气工程与信息工程学院硕士研究生. 主要研究方向为机器视觉和视觉测量. E-mail: heweilongd@163.com

张爱华

兰州理工大学电气工程与信息工程学院教授. 2005年获西安交通大学博士学位. 主要研究方向为检测技术和模式识别与智能系统. E-mail: zhangaihua@lut.edu.cn

姚鹏鹏

中国香港理工大学纺织与制衣学系博士研究生. 主要研究方向为多光谱颜色测量, 相机矫正和图像检索. E-mail: p.p.yao@connect.polyu.hk

徐贵力

南京航空航天大学自动化学院教授. 2002年获江苏大学博士学位. 主要研究方向为光电检测, 计算机视觉和智能系统. E-mail: guilixu2002@163.com