基于改进遗传算法的摄像机自标定方法

(西南科技大学 计算机科学与技术学院，四川 绵阳 621010)

0 引言

摄像机标定是计算机视觉领域的关键技术，它是从二维图像恢复到三维图像的必不可少的步骤，被广泛应用到三维测量、三维物体重建、物体识别、工业检测、虚拟现实等领域。目前摄像机标定技术有很多种分类方法，应用最为普遍的是将其分为传统摄像机标定方法、自标定方法和基于主动视觉的标定方法[1]。传统摄像机标定方法需要利用几何参数精确且已知的标定块，其优点是标定精度比较高但是标定过程复杂，计算量大，且需要精密加工的标定参照物。基于主动视觉的标定方法是指在已知的运动轨迹信息下进行摄像机标定，其优点是可以线性求解摄像机的模型，因而算法简单和鲁棒性比较高，但限制了摄像机的运动。以上两种方法均有一些限制条件，对于场景任意，摄像机运动未知的情况则不能实现。自标定技术则无需要求标定板和已知摄像机运动轨迹信息，仅通过图像与图像之间的对应点间的关系直接求解摄像机模型,即求解摄像机的内参数矩阵K，K包含4个未知参数(摄像机的焦距和主点的坐标)。

摄像机自标定方法可以分为以下4种方法：Faugeras[2]提出的直接求解Kruppa方程的方法，利用绝对二次曲线和极线变换推导出Kruppa方程；分层逐步标定方法[3]，首先对图像序列做射影重建再通过绝对二次曲线加以约束，最后求得仿射参数和摄像机内参数；Triggs[4]提出的绝对二次曲面的自标定方法，该方法和基于Kruppa方程的方法都是利用绝对二次曲线在欧式变换下的不变性，但基于绝对二次曲面的方法更有利于多幅图像的标定；可变内参数的摄像机标定方法，Heyden[5]等人证明了内参数可变的情况下可以实现摄像机的自标定。

直接求解Kruppa方程的方法是一个非线性问题。可以利用一些优化算法对Kruppa方程所提供的代价函数进行优化。传统的基于遗传算法的摄像机自标定方法参数优化过程中，易出现过早收敛、停滞现象和解易陷入局部最优的问题。因此，针对传统方法中出现的上述问题，本文提出了一种改进的基于遗传算法的摄像机自标定方法。

1 算法原理

1.1 投影模型

在摄像机模型为针孔模型下，假设三维空间点为X=(x,y,z,1)T对应到二维图像的点为m=(u,υ,1)T。它们的成像关系可以表示为：

m≅K[R|t]X#

(1)

1.2 基础矩阵和Kruppa方程

从两不同的视点获得的同一场景的两幅图像，它们之间存在着一定的约束关系，这就是对极几何关系。基础矩阵F是对极几何关系的代数表达。根据摄像机与图像之间的关系，Faugeras、Luong和Maybank等人提出可用Kruppa方程表示为(具体推导方法可参阅文献[6])：

(2)

在Kruppa方程中，我们只需要已知极点e′和基础矩阵F就可以知道矩阵C即摄像机内参数K。但是极点非常的不稳定，不易确定。因此Hartley提出了一种不需要极点的新的Kruppa方程形式[7]。令基础矩阵F的SVD分解为F=UDVT。其中矩阵U和V的列向量分别为F的左奇异向量和右奇异向量。D是一个对角矩阵，对角线上的元素就是F的奇异值。直接由基础矩阵推导得到Kruppa方程的简化形式：

(3)

其中:Vi和Ui分别表示的是矩阵V和U的第i列向量，r和s是F的奇异值。

(4)

(5)

(6)

设目标函数为:

f(fu,fv,u0,v0)=

(f1-f2)2+(f1-f3)2+(f3-f2)2#

(7)

目标函数f的值最小或趋近为0时，C即为所求的值。

2 基于改进的遗传算法的摄像机自标定

遗传算法是受达尔文进化论的启发，通过模拟自然界和生物进化过程而被提出的用来解决优化问题的有效方法，是一种启发式的搜索方法，也称进化算法[8]。传统的遗传算法操作盲目无方向，所需要的收敛时间长且最优值容易早熟陷入局部最优。

文献[9]证明遗传算法杂交过程的成熟化效应是引起遗传算法过早收敛的主因。过早收敛现象表现出来的特征是种群序列多样性减少。为了使最优值结果避免过早陷入最优解，主要是要使种群序列多样性高。

本文对遗传算法做出了以下改进：结合精英保留策略和随机联赛选择算法作为初始化种群的方法；采用实数编码；改进轮盘赌选择方法；采用自适应杂交概率和变异概率方法。

2.1 编码

本文采用实数编码方式。传统的遗传算法一般采用二进制编码方式，二进制编码使用字符集(0，1)组成，虽然简单易用，但是存在Hamming悬崖问题，在求解最优化问题时缺陷较大。实数编码方式更接近问题空间，在基因型空间和表现型空间中是一致的。

2.2 改进的种群初始化

传统的遗传算法初始化是随机生成个体。这种初始化的种群对于多峰病态复杂函数来说，如后续遗传算子操作不当很容易使算法出现早熟现象。为了使搜索过程中更大概率找到真正最优值的波峰，初始化时结合了随机联赛选择算法和精英保留策略。初始化步骤：

1)按照搜索空间采用线性随机生成方法生成N个个体。

2)计算N个个体的适应度，对N个适应度进行从大到小到排序。

3)选取适应度最大的那个个体作为初始种群的成员。

4)重复上面1)～3)的步骤直到初始种群满员。

这样初始种群本身就会具有较高的适应度，而且种群内个体处在最优解所处波峰附近的概率就会大大地提高。

2.3 改进的轮盘赌选择算法

轮盘赌选择算法选择的依据是目标函数的适应度大小。在进化初期通常会产生一些适应度超常大的个体，这些异常大的个体被选择的概率很大，它们会很大程度地控制选择过程，造成种群的多样性降低。因此，本文算法将每次被选择的个体从总选择序列中拿出，不在参与下一次选择。

改进的轮盘赌选择步骤：

1)将种群全部个体的适应度进行从大到小排序，求得全部个体的适应度总和S。

2)产生一个0～S之间的随机数M。

3)从种群中编号为1的个体开始，将其适应度值与后面个体的适应度值相加，直到累加的和大于M则停止。最后加进去的个体即为被选择出的父代。

4)将被选择的个体从种群中拿出，重复2)、3)步骤直到选择出足够多的父代。

这样避免了哪些异常大的值会被多次选中，丰富了种群的多样性。并且适应度值异常大的值也不会被破坏，从而避免了进化初期适应度异常高个体处于局部最优情况导致的算法收敛于局部最优的情况。

2.4 自适应的杂交和变异概率

杂交是模仿生物自然进化过程中，两个个体间相互配对的染色体按一定方式以杂交概率交换其部分基因，生成两个新个体[10]。杂交概率主要控制种群新群体产生的速度，因为杂交操作进行的是基因重组，生成相对父代波动较大的基因。变异是遗传算法中保持生物多样性的一个重要途径，也是对杂交过程可能丢失的某种遗传基因进行修复和补充，可防止遗传算法尽快收敛到局部最优解[10]。变异概率主要控制基因扰动，在实数编码时更为明显。

为了丰富种群的多样性和加快搜索时间，在遗传算法初期希望种群基因波动范围较大和种群基因型丰富，能够在搜索的种群里面快速的找到包含最优解的波形峰。而在遗传算法后期，大多数的搜索点已经在包含最优解的波形峰的附近，但是没有找到最优解，在这时希望种群能够在波形峰小范围内波动来搜索到最优解。即在遗传算法初期杂交概率大变异概率小，后期杂交概率小变异概率大。概率Pc和Pm表达式为：

(8)

(9)

Pc1和Pm1是杂交概率和变异概率的初始值，i是当前进化次数，n是最高进化次数，count是累积最优解不改变的次数。当count为0的时候，Pc为Pc1，Pm为Pm1/2，杂交概率Pc大变异概率Pm小。当count变大时，杂交概率Pc变小变异概率Pm变大。

本文的目的是求摄像机的内参数，即目标函数f(fu,fv,u0,v0)，适应度为1/f(fu,fv,u0,v0)，种群大小为N，进化代数为n。

改进遗传算法的具体步骤：

1)初始化相关变量，如Pc1、Pm1、N、n等。

2)初始化种群。用上面改进了的初始化方法生成N个个体。

3)采用改进了的轮盘赌选择算法，选择出N/2个个体作为父代。

4)采用实数编码的方式对种群进行编码，按照公式(8)计算自适应的杂交概率Pc，在Pc的控制下进行杂交，将两个父代进行杂交操作生成两个新的基因。进行完整个杂交操作将参数N/2个新基因。

5)进行变异操作。按照公式(9)计算自适应变异概率Pm，在Pm的控制下选择新产生的基因进行变异操作，最后产生N/2个新基因。

6)计算目前种群个体的适应度，按照适应度从大到小排序。目前种群个体一共有3N/2个个体，包含步骤3)中未被选中的N/2个个体、步骤4)中杂交产生的N/2个新个体、步骤5)中变异产生的N/2个新个体。按照适应度排序选择前N个个体作为新一代种群。

7)选出新一代种群里面最优的个体和上一代最优个体进行比较，较优者替换新一代最差的个体。

8)计算新一代种群的总适应度、平均适应度。保存本代最优个体，判断本代最优个体是否和上一代相同，若相同count=count+1，若不同count不变。

9)终止条件判断。当前运行代数i>n迭代终止；若i

3 实验与分析

为了验证本文说提出的摄像机自标定方法的鲁棒性和实用性，进行了仿真实验和真实图像的实验。

3.1 仿真实验

在仿真实验中，用Matlab合成摄像机仿真图像并加入高斯噪声。摄像机的内参数设置为fu=500,fv=500,u0=250,v0=250。让仿真摄像机生成一个10*20的点阵并改变其外参数，从而得到不同的图像。为了和真实图像相似，所以在仿真实验中向图像点加上了高斯噪声。设置了6种不同的噪声等级，在每种噪声等级下进行了20次实验。其中设定初始时种群规模N=50,进化代数n=200,杂交概率pc1=0.01，变异概率Pm1=0.01。对实验结果进行了分析，实验统计结果如图1所示。

图1 fv的平均误差

图2 fu的平均误差

图3 u0的平均误差

图4 v0的平均误差

通过图1～图4可以看出。本文改进的遗传算法求得的摄像机内参数比传统的遗传算法平均误差要小。另外随着噪声级的不断增高，本文算法求得的摄像机各内参数平均误差变化率逐渐变小。证明基于改进遗传算法求得的摄像机内参数准确度更高，鲁棒性更好。

3.2 真实实验

除了仿真实验外，还进行了真实图像实验。用摄像机拍摄实验标定块的一组图片，对图5两张不同角度的图像进行了标定。

图5 标定块图像序列

其中设定初始时种群规模N=50,进化代数n=200,杂交概率pc1=0.6，变异概率pm1=0.01。自标定结果如表1所示。

表1 对图5的标定结果

由表1可以看出，本文的标定算法和Matlab标定工具箱的标定结果更相近，这证明了本算法的准确性。

从网站http://www.robots.ox.ac.uk/～vgg/data/data-mview.html下载文献[11]和[12]使用的Valbonne church图像用于本实验。其中设定初始时种群规模N=50,进化代数n=300,杂交概率Pc1=0.6，变异概率Pm1=0.01。自标定结果如表2所示。

图6 Valbome church图像

fufvu0v0文献[11]682.84682.84255.99383.92文献[12]670.46667.21245.23355.54本文算法675.81678.15249.31369.21

与文献[11]和[12]的实验结果相比，本文的实验结果与其十分接近，可以证明本算法具有较高的鲁棒性。

4 结论

本文提出的基于改进遗传算法的摄像机自标定方法，能够较好地避免传统遗传算法出现的过早收敛和陷入局部最优解的现象。本文的方法和基于传统遗传算法的摄像机自标定方法进行实验对比，其准确性较好，鲁棒性较高，是一种简单易用的自标定方法。