改进基本矩阵计算和优化的多摄像机并行标定算法

　　0引言

　　随着摄像机制造成本的下降，多摄像机系统已经成为目标跟踪及三维重构等领域的发展趋势。多摄像机系统在机器人导航、人体动作捕获、导弹定位和无人机等领域广泛应用。早期多摄像机系统由于受到硬件限制，通常由3～10个摄像机组成[1]。近年来，大规模集成电路迅速发展，多摄像机系统中摄像机的数目也急剧增加。如斯坦福并行128个摄像机组成的大型摄像机阵列[2]，瑞士的360度环绕式多摄像机系统[3]。在大量摄像机组成的多摄像机系统中，传统的摄像机标定技术不再适用[4]。一方面，传统摄像机标定方法针对单个摄像机标定，在多摄像机系统中，如果使用传统标定法对每个摄像机进行单独标定，那么整个标定过程将变得十分繁琐和耗时；另一方面，多摄像机系统着重整体优势，传统的摄像机标定技术研究单个摄像机的性能而忽视整体性能。

　　多摄像机标定技术成为现在摄像机标定的研究热点[5]。摄像机标定的方法依据标定物的维数分为四类：三维立方体标定法、二维平面标定法、一维直线标定法和自标定。由于存在自身的遮挡，三维立方体标定法和二维平面标定法不适用于多摄像机系统标定。一维标定法采用已知彼此距离且共线的标记点组成。一维标定物具有制作简单，而且不会被自身遮挡的优势，已经成为多摄像机系统标定的主要手段[6]。Zhang[7]最早提出一维标定法，但是真正将一维标定法应用于多摄像机系统是deFrance等[8]。在国内，吴朝福[9]提出一维标定物做任意刚体运动，标定多摄像机系统的内外参数的方法；王涛等[10]研究表明一维标定法可以获得同二维平面标定法相同的精度。自标定是基于绝对二次曲线或者对偶绝对二次曲线，理论不成熟，现在还处于研究阶段。就目前而言，自标定理论还没有应用于多摄像机系统的标定中[3]。

　　多摄像机系统在工程中被广泛应用，多摄像机系统标定的理论成为机器视觉的研究热点。但是现在多摄像机系统标定基本都集中在摄像机标定的精度问题上，很少关注标定的时间复杂度。相比于单摄像机标定，多摄像机系统标定的时间是一个不可忽视的问题。由32个摄像机组成的多摄像系统，整个标定过程需要消耗60～90min。目前多摄像机系统标定都是串行的标定算法，这必然使得标定时间会随摄像机数目的增加而递增。一旦多摄像机系统中摄像机数目过多，标定不可能在预定的时间内完成。近年来，已经有学者开始对摄像机的并行标定算法进行探索和研究。国内，熊九龙等[11]结合摄像机成像模型与神经网络技术提出了摄像机标定的并行算法，通过将三维世界坐标分成三个独立分量分别处理实现并行处理；李超等[12]采用GPU技术加快标定所需的图像特征点的计算，实现了摄像机的实时标定。但是，这些算法主要针对单个摄像机而设计，并行化的思路也主要是简单对数据分组处理来实现。在多摄像机系统中随着摄像机数目的增多，传统单摄像机标定算法是低效的；并且传统算法考虑的是单个摄像机的精度，而不是系统整体的精度。国外，现有的摄像机并行标定技术主要针对摄像机的自标定。自标定算法对于噪声比较敏感，计算复杂度高，很少应用于多摄像机系统。本文针对多摄像机系统的标定算法，以系统整体性能最优为目标，改进了多摄像机标定中基本矩阵的计算和迭代优化中增量的计算，降低了多摄像机标定算法的时间复杂度。

　　多摄像机系统标定分为两个阶段：第一阶段，使用线性方法对摄像机标定参数进行初始值估计；第二阶段，利用迭代法对线性算法的结果进行优化。

　　多摄像机系统的标定，首先需要对摄像机进行两两分组，通过基于随机抽样一致性（RANdomSAmpleConsensus，RANSAC）算法求解每组对应的基本矩阵和极点坐标。基本矩阵的计算是整个计算过程中最复杂的部分，串行基于RANSAC算法基本矩阵的计算效率低。因此，改进基本矩阵的计算是提高线性标定算法的有效手段。根据苗青等[13]提出的并行改良随机抽样一致性思想，结合八点法的求解过程，提出计算基本矩阵的并行算法。求得基本矩阵和极点坐标后，利用Kruppa方程计算出摄像机焦距，再联合内参矩阵和基本矩阵求解本质矩阵；对本质矩阵进行分解，即得到摄像机的旋转矩阵和平移向量。在得到所有摄像机参数的初始值后，以第一个摄像机坐标为世界坐标，统一其他摄像机的坐标系。第二步，使用迭代算法求解欧氏重构下极大似然解，在摄像机标定中常使用捆绑调整方法。捆绑调整方法本质是一种基于梯度方向更新自变量值的迭代法，优化过程中自变量值的更新是关键步骤。传统自变量更新是通过解大型线性方程组得到的，在多摄像机组标定中，这个线性方程至少上千维。线性方程组的求解常采用高斯消元法，而高斯消元法的时间复杂度是矩阵维数的三次方，其计算时间会随维数的增加而急剧增加，因此，对大型线性方程进行降维将有效地减少运行时间。根据优化过程中空间点相互独立的特点，结合多摄像机模型，对线性方程组进行合理的分块，分块后的方程不仅求解效率提高，并且容易实现并行化。基本矩阵计算和优化过程的改进，使得标定算法的时间复杂度从O（n3）降为O（n）。采用基于OpenMP的多核编程，其编程的实现相对简单，并且标定时间满足现实的要求。实验数据表明：相比于串行标定算法，并行标定算法在不降低标定精度的同时大幅度缩减了标定时间。

　　2.1基本矩阵并行算法

　　理论上基本矩阵的计算只需要8对独立的点坐标就可求解，但是实际标定过程中存在图像点错误匹配和图像坐标不精确等问题，导致基本矩阵的解误差大。RANSAC算法能有效地消除错误点给模型参数带来的偏差，基于RANSAC算法的八点法成为了基本矩阵计算的经典方法。RANSAC算法通过引入有效点和平均误差来评价模型参数的优劣。首先必须设定一个阈值κ和最低平均误差率ε，将图像匹配点对代入极限约束方程，如在阈值κ范围内满足，则称为有效点；统计所有有效点的平均误差率，如小于最低平均误差率ε，则记录此时有效点数目，并将有效点最多时的解作为基本矩阵。传统RANSAC算法具有很多局限性（样本多、模型复杂或者数据错误率高），计算效率十分低。因为匹配算法总存在大量错误匹配情况，所以计算基本矩阵的样本含有较高的数据错误率。基于RANSAC算法计算基本矩阵能避免错误匹配导致的误差。但是，基于RANSAC算法的基本矩阵计算将变得十分复杂并且效率低，成为线性标定过程中最为耗时的部分。根据基本矩阵计算原理，结合RANSAC基本过程，提出计算基本矩阵的并行RANSAC算法。并行算法克服了传统算法弊端，当图像坐标样本数量大时有可观的效率优势。并行RANSAC的基本矩阵计算主要分为如下三个步骤。

　　因为数据存在一定误差，所以式（7）需要转换成在约束条件rank（F）=2下的最小二乘解。八点法的计算仅依赖于8个样本，而不依赖于总体样本，样本之间也相互独立，所以每个处理单元可以独立地计算基本矩阵。

　　3）用一致性集评估基本矩阵。比较每个处理单元计算的基本矩阵的解。首先将总样本代入式（5）中，计算有效点的个数以及有效点平均误差；接着比较有效点的平均误差是否小于给定的最小平均误差，若满足则保存有效点的个数；在满足给定的平均误差率的条件下，选择有效点个数最大的解作为本次并行计算基本矩阵的最佳解；如果最佳基本矩阵解的有效点个数比当前全局变量保存有效点的个数还要多，则用当前最佳有效点的个数更新全局变量保存点数及基本矩阵。迭代的终止条件有两个：1）有效点占总体样本比例超过给定的值，跳出循环，输出最佳基本矩阵；2）在规定的迭代次数内，还没得到最佳基本矩阵的解，则表明样本受到噪声严重污染，该总体样本集无法在给定的精度范围求解基本矩阵。

　　苗青等[13]的分析表明：当模型计算过程仅依赖于样本，且抽样和检验相互不影响，则并发RANSAC算法过程和传统RANSAC算法等效。本文基本矩阵计算模型过程中抽样和计算步骤仅涉及到抽取的样本，即选取出8个样本组成的子集，所以并行RANSAC算法计算基本矩阵和传统基本矩阵的计算是等效的。

　　论文榜（www.zglwb.com），是一个专门从事期刊推广、投稿辅导的网站。
本站提供如何投稿辅导，寻求投稿辅导代理，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。


期刊鉴别	论文检测	免费论文	特惠期刊	学术答疑	发表流程

搜索

改进基本矩阵计算和优化的多摄像机并行标定算法