文摘

在几个机器视觉问题,与之相关的问题是两个不同的观点之间的单应性估计,一组广泛的异常数据。一个方法来找到这样的估计是随机抽样的共识(RANSAC);在这方面,我们的目标是最大化数量的匹配点了允许误差(Pe),根据候选人的模型。然而,这些目标是冲突:Pe低价值增加模型的精度,但降低其泛化能力指的是容忍噪声数据的数量的匹配点,而较高的体育价值提高了噪声模型的宽容但不利驱动器错误检测的过程。这项工作考虑评估过程是一个多目标优化问题,旨在最大化匹配点的数量而Pe同时最小化。为了解决多目标制定、两种不同的进化算法探索:第二Nondominated排序遗传算法(NSGA-II)和Nondominated排序差分进化(NSDE)。原始结果考虑承认质量度量和转换后的图像在一个著名的基准图像显示性能优越的提议算法比随机样本一致。

1。介绍

单应性变换,地图的兴趣点通过考虑运动作为翻译,旋转,倾斜,缩放和投影图像平面中,都包含到一个单一的,可逆矩阵。概括地说,这些位移可以被认为是属于三种情况:前面的物体移动一个静态摄像头,静态场景移动相机,捕捉到多个摄像头从不同的观点。在这两种情况下,这些近似简化构建全景图像序列的利用率(1- - - - - -3),增加解决方案在低质量图像4- - - - - -6),删除相机运动当研究对象的运动视频(7),来控制机器人的位置(8- - - - - -10),在其他用途(11- - - - - -13]。

把一组实验数据为基础,在建模问题存在两种数据类型:那些可以调整有一定概率模型(也称为内围层)和那些不相关的模型(例如,异常值)。有几种算法专业解决分类问题;这样的技术之一是随机样本共识(RANSAC) [14]。

算法,实验数据是随机的最小子集,并提出一个模型和评估根据允许误差(Pe),为了了解模型适应数据(15]。重复这个过程,直到迭代次数完成后,与模型内围层的最大数量。

即使考虑到RANSAC是一个健壮和简单的算法,它有一些缺陷16- - - - - -18),其中两个是高数量的匹配点之间的依赖关系(模型质量)和允许误差。在这个工作中,它被认为是那些缺点属于多目标优化问题。一方面,由于RANSAC的随机性质,实现改善内围层意味着更多的迭代的数量以丢弃未经调整的数据提出的模型。另一方面,匹配点冲突的数量取决于允许误差(Pe)。Pe低价值增加模型的精度,但降低其泛化能力容忍噪声数据(数量的匹配点)。相比之下,高Pe值提高了噪声模型的宽容但不利驱动器错误检测的过程。模型估计过程中的主要误差源来自定义体育价值,没有考虑数据集之间的关系模型。

为了使RANSAC算法效率更高,一些改进建议;例如,在算法称为MLESAC [19)认为内围层到图像会遵循一个高斯分布而离群值视为均匀定位;据,投票过程是通过最大化可能和原来的RANSAC。SIMFIT方法(20.]提出的允许误差的预测,通过迭代reestimation的价值,直到模型调整实验数据。其他一些变异原RANSAC投影寻踪方法,两步估计规模,CC-RANSAC [15,21,22),他们都集中在窗的数量最大化,使更多的搜索数据,因此使完整的流程更加昂贵,计算。在这种意义上,一个算法,试图降低计算成本是在[提出17),内围层的最大化的实现是通过使用一个metaheuristic技术,叫做和谐搜索。

不过提到改进,文章提到的搜索策略用于(例外的17]),更接近随机行走,因此这些方法计算昂贵。此外,在所有的情况下只有一个目标函数是,通常与数量的匹配点,而留下的允许误差。依照,为了克服典型的RANSAC问题,我们建议可视化RANSAC操作作为多目标进化算法来解决问题。在这样的角度来看,在每个迭代中,构建新的候选解决方案通过使用进化运营商考虑的质量之前生成的模型,而不是纯粹的随机的,显著减少迭代的次数。同样,新的目标函数可以将添加其他元素,允许一个准确的评估候选人的质量模型。

当一个优化问题涉及多个目标函数,找到一个或多个最优解的过程被称为多目标优化(MO) [23]。在密苏里州,不同的解决方案产生冲突的场景中目标(24]。与单目标优化,在密苏里州通常很难找到一个最优的解决方案。相反,多目标优化问题的算法试图找到一个家庭的点被称为帕累托最优设置(25]。这些点确认没有不同的可行的解决方案,严格提高目标函数向量的一个分量没有至少一个剩余的恶化。进化算法(EAs)被认为是最适当的方法解决复杂的密苏里州的问题,主要是由于他们能够保持良好的多样性(多次26),可以扩展到多个种群(27),以及可以处理各种各样的问题,如离散的(28]。几个变种nondominated排序的新方法提出了近年来为了解决问题特征选择(29日)、社区检测(30.[]等问题24,31日];然而,Nondominated第二排序遗传算法(NSGA-II) [32]和Nondominated排序差分进化(NSDE) [31日是最具代表性的。

摘要评估过程被认为是一个多目标问题数量的匹配点和允许误差(Pe)同时优化。为了解决多目标制定、两种不同的进化算法探索:第二Nondominated排序遗传算法(NSGA-II)和Nondominated排序差分进化(NSDE)。原始结果考虑承认质量度量和转换后的图像在一个著名的基准图像显示性能优越的提议比随机样本一致算法评估的问题,给好的结果甚至异常值高的水平。

本文的其余部分组织如下:部分2解释图像的单应性考虑多个视图的问题。部分3介绍了RANSAC方法的基础。部分4简要解释了进化的方法用于本文为了解决多目标问题,而部分5给出了该方法。部分6展览实验集及其性能。最后,部分7建立了一些最后的结论。

2。图像之间的单应性

情况的两个图像从不同角度拍摄同一场景的,问题在于找到一个转换,允许像素属于两图像之间的匹配。这计价的图像匹配问题。几何变换的搜索是通过利用从图像对应点对(33,34),这使形成特征向量,也叫图像描述符。即使考虑到这样的描述符是不完全可靠的,所以他们可以产生错误的结果图像匹配,本文使用它们的几何图像通过使用单应性之间的关系,解释了在接下来的段落。

考虑一个点集 这样和位置对给定图像对。

通过一个飞机上,一个单应性建立两个不同视角下拍摄的图像之间的几何关系,可以看到在图1;这允许从飞机上的投影点的图像,通过或。有利于找到一对图像之间的单应性,只需要一套有四个点匹配,构造一个线性系统,必须解决(35]。关于候选人的质量评估单应性,有必要计算点的位置之间的距离第一个图像对第二图像;这个距离是贴上失配误差被定义为 只要和从每个图像各自的错误。

考虑示例如图2,五个通讯进行描述;点的情况,错误是相当大的,因此候选人的质量单应性将排在一个较低的值。

3所示。随机抽样的共识(RANSAC)算法

找到对应的图像通过几何变换(单应性),因此增加的数量正确匹配(窗),使用一个健壮的方法,如RANSAC,是必要的。与内围层相反,局外人是矛盾点相关的候选单应性。

算法背后的思想在于发现最好的假说从一组假设生成的源数据,通常与噪声损坏。建设的候选人的假设实现通过一个示例,最小大小模型的估计。在这篇论文,然后几可以从完整的源数据,因此,一个详尽的搜索将会计算昂贵。

在伪代码1基本家庭显示RANSAC算法的伪代码。

后续步骤包括在寻找最佳人选的假设从所有的构建和评估假设 协议的程度直接关系到内围层的数量,计算了 在哪里是一个允许误差,是源数据中包含的元素的数量吗,和二次错误产生的吗考虑数据的假设;换句话说,它代表产生的误差对应。

在原始RANSAC算法,最好的假说是内围层的最大数量。这一点产生一个错误比允许误差较小被认为是候选人假说的窗吗;否则,它被认为是一个异类。

RANSAC技术搜索整个源数据在最坏的情况下至少一次;通过考虑这种情况下,该算法类似于随机行走。一些策略可以改善这样的搜索,就像进化算法(EAs) (36]。这些技术有能力开发和探索明智的搜索空间,通过考虑新的候选解决方案将包含信息从搜索空间的最佳地点,参观了每一代。

这项工作提出了工作的评估过程是一个多目标问题,同时通过优化匹配点的数量和允许误差(Pe)。为了解决多目标制定、两种不同的进化算法探索:第二Nondominated排序遗传算法(NSGA-II)和Nondominated排序差分进化(NSDE)。公式,该方法采用不同的采样策略比RANSAC生成公认的解决方案。在新的机制下,在每一个迭代生成新的候选解决方案基于先前发现的质量解决方案,避免了在搜索过程中随机漫步,如RANSAC的情况。

4所示。多目标进化算法

莫问题可以表示为最小化或最大化函数(37] 一个解决方案是一个向量的决策变量。最后一组约束称为变量范围,限制每个决策变量在一个较低的价值和上束缚和限制构成的决策空间。有不平等和等式约束,两个相关的问题。为了覆盖目标函数的最小化和最大化,操作员使用两个解决方案和。因此,表示,解决方案比解决方案而意味着解决方案优于或等于解决方案吗。

不同于单目标优化的多目标优化,通常很难找到一个最优的解决方案。相反,多目标优化问题的算法试图找到一群点被称为帕累托最优设置(38]。这些点确认没有其他可行的解决方案,严格提高目标函数向量的一个分量没有至少一个剩余的恶化。帕累托最优和帕累托效率的更正式的定义是这样的。

定义1。如果给出一个解决方案,存在另一个解决方案这样 和这样,那么你会说,解决方案占主导地位解决方案(用),很明显,解决方案永远不会被明智地选择解决问题的办法。如果,,一个会说,解决方案弱主导解决方案并将用 。

定义2。一个解决方案被认为是帕累托最优设置的一部分吗当且仅当这样。

进化算法(EAs)被认为是最适当的方法解决复杂的莫问题和提出了一些面对这样的问题,在第二Nondominated排序遗传算法(NSGA-II)和Nondominated排序差分进化(NSDE)是最具代表性的。

4.1。Nondominated排序遗传算法二世(NSGA-II)

NSGA-II,引入了Deb et al。32),是一种最适用和使用算法基于遗传算法来解决多目标优化问题。NSGA-II开始随机生成一个初始()亲本种群的大小。在连续几代(),客观的价值观进行了评估。然后,人口排名基于nondomination排序过程创建帕累托最优的方面。每个单独的人口在评估获得等级等于nondomination水平(1是最好的水平,2是第二个最好的水平,等等),在第一个前面包含个人最好的排名,第二前面对应的个人第二等级,等等。在下一步中,每个成员之间的拥挤距离前由直线距离计算标准。作为二进制锦标赛选择运营商基于crowded-comparison运营商使用,有必要计算等级和拥挤人群中每个成员的距离。使用此选择算子,选择两个成员的人口。然后,选择较大的拥挤距离的成员如果他们共享一个平等的地位。否则,选择低等级的成员。接下来,一个新的人口规模的后代创建使用随机选择,模拟二进制交叉(19),多项式变异(20.)操作符创建一个人口组成的当前,新的人口的规模。

以下4.4.1。模拟二进制交叉

这个算子模拟单点交叉的行为在二进制字符串。作为父母和,他们生成th组件()的后代个体如下: 在哪里一个随机数在吗。的参数决定之间的分离后代个体相比,他们的父母。

4.1.2。多项式变异

这个操作符使用多项式分布在以下方式: 在哪里和分别是低和上界的吗决策变量,而代表指数分布。

4.2。Nondominated排序差分进化(NSDE)

NSDE [31日)算法是一个扩展的原始微分进化(DE) [39)方法解决多目标问题。NSDE作品以类似的方式德除了选择操作修改为了与nondominated标准一致。

该算法首先初始化人口维认为个人和之间随机分布参数值指定的较低的初始参数和上面的初始参数。为了生成一个审判个人(解决方案),DE算法首先变异当前个体从人口中通过添加两个向量的不同比例从当前人口: 与变异个体。索引和随机选择的条件,它们是不同的个体指数和没有关系任何(例如,)。突变的比例因子是一个正实数,通常小于1。为了增加的多样性参数元素,突变个体之间的交叉操作应用和最初的个人。试验结果是个体考虑一个元素元素计算的操作如下: 在哪里。下标的和分别参数和单个索引。交叉参数控制参数的突变体的一部分个人贡献个人的最终审判。此外,试验个体总是继承了突变个体参数根据随机选择的指数,确保审判个人不同的至少一个参数。最后,用于构建nondominated选择帕累托最优。因此,如果个人审判主导目标个体,审判个人复制到下一代的人口;否则,个人目标复制:

5。该方法

5.1。个人表示

在评估过程中,每个候选人单应性计算通过使用四个不同的点对应。候选人单应性因此,在整个数据集评估从数据集,将所有元素内围层和异常值,根据一项允许误差(Pe)。

为了建立一个候选解决方案或个人,四个指标,,,,从集合中选择的对应关系。因此,单应性在计算两个视图通过求解线性系统产生四个点集的匹配,,,。此外,允许误差与个人相关联注册为决策变量。因此,在该算法中,一个个人或候选方案是五个决策变量编码为一个向量所定义的

在我们的方法中,候选的解决方案提供了相同的功能,即假设在最初的RANSAC算法。

5.2。多目标问题公式化

在建议的方法,评估过程被认为是一个多目标问题,匹配点的数量和允许误差同时优化。在这种情况下,多目标问题可以定义如下: 考虑到和;在哪里代表了最大能较量的错误产生的候选单应性。虽然可以是任何值高,一个足够小的值显著降低帕累托的搜索方面。在这工作,已经设置为25。

5.3。计算程序

为了解决多目标制定、两种不同的进化算法探索:第二Nondominated排序遗传算法(NSGA-II)和Nondominated排序差分进化(NSDE)。在本节中,这两种方法的计算过程是描述当他们面临多目标问题中描述(12)。

(一)Nondominated第二排序遗传算法(NSGA-II)(1)生成随机人口的五维的个人。每个个体的决策变量()生产,考虑他们的搜索范围之间的一个随机数。(2)产生的后代人口从通过使用模拟二进制交叉和多项式变异。(3)创建一个新的人口的组合和()。(4)执行一个nondominated排序和识别不同的方面:,,等等。(5)设置新的人口和柜台。(6)执行和增量 。(7)假设代表中包含的元素的个数,重复步骤,直到。(8)假设,明确的初始距离()的每个元素从。(9)为每个目标函数,一组在更糟的顺序。因此,包含目标函数的元素排序。(10)为分配一个大距离边界的元素 。对于所有其他元素分配一个距离计算如下: 在哪里代表的元素从排序集。和象征的最大和最小值(11)选择的元素最长的,包括他们是谁的距离。(12)如果已经达到最大迭代次数,这个过程就完成了;否则,回到步骤。(13)最终的人口包含了帕累托最优。

(b) Nondominated排序差分进化(NSDE)(1)设置DE参数和。(2)生成随机人口的五维的个人。每个个体的决策变量()生产,考虑他们的搜索范围之间的一个随机数。(3)生成一个审判人口与个人()的五个维度()程序1。(4)选择的元素(未来人口的)下程序2。(5)如果已经达到最大迭代次数,这个过程就完成了;否则,回到步骤。(6)最终的人口包含了帕累托最优。

6。实验结果

论文的这一部分处理几个实验进行对真实图像的集合。结果表现出的性能NSGA-II和解决NSDE估计问题是一个多目标优化任务RANSAC相比。在实验中,两个性能指标是:均方误差(MSE)和峰值信噪比(PSNR)。这种索引允许适当评估估计的准确性。

单应性估计的问题在于找到一个几何变换映射点的第一个视图()第二个视图(),从不同的观点。这个投影变换有关飞机的对应点投射到第一和第二的观点或。为了计算MSE和PSNR,定义了两个不同的图像:估计图像(EI)和实际的图像(人工智能)。的EI从第一个视图是由像素映射的估计单应性 。另一方面,实际的图像(人工智能)对应于第二种观点的形象。

均方误差(MSE)评估方的像素之间的区别EI和人工智能。考虑到代表了MSE图像尺寸,可以计算如下:

峰值信噪比(PSNR)通常被用来衡量图像的重建质量,经历一些过程。信号在这种情况下是原始数据(人工智能),引入的噪声误差转换H(EI)。当比较图像PSNR值是一个近似近似人类的感知质量。更高的PSNR值通常表明,更高质量的评估。PSNR值主要是通过定义均方误差(MSE)。鉴于形象,PSNR值被定义为 马克斯是最大可能的像素值中包含的图像。

在实验中使用的图片是来自[40)包含两个视图图像不同的对象,考虑640×480像素的尺寸。同样,一组实验测试中使用的图像呈现在图3。

两种算法,测试NSGA-II NSDE,已经配置考虑下200人200次迭代。为了进行公平比较RANSAC和多目标方法,RANSAC一直在40000次迭代操作。这样的数量计算(200×200)对应的最大数量评估投资NSGA-II和NSDE期间执行。

图4显示了帕累托最优设置通过NSGA-II和NSDE在估计过程中,考虑到数据5(一个)和5 (b)分别作为第一个和第二个观点。在图4,最好的RANSAC估计还包括作为参考,验证多目标方法的性能。

为了说明结果,图5显示所有产生的估计方法估计的结果图像。RANSAC展所产生的单一的评估数据5 (c)和5 (d)。在多目标方法的情况下,帕累托最优设置三个解决方案选择:边界的解决方案边界的解决方案和中值的解决方案。这样的解决方案提出了数字5 (e)- - - - - -5 (f)和5 (g)- - - - - -5 (h)分别NSGA-II和NSDE。

表1介绍了性能结果NSGA-II和NSDE的均方误差(MSE)和峰值信噪比(PSNR)超过三双图像。结果显示平均获得的结果在30种不同的死刑。只为了欣赏差异,结果报告获得边界解决方案和。最好的结果突出显示在表在每个实验1。

为了评估两种算法的鲁棒性,添加的异常值是通过选择一组对应随机点在空间范围内。在测试中,异常值的比例从85%到95%不等。图6显示所有产生的估计方法估计的结果图像,考虑对人物形象3 (k)和3(左)。表2介绍了性能结果RANSAC、NSGA-II NSDE的均方误差(MSE)图像的三双。结果显示平均获得的结果在30种不同的死刑。

从表2,它可以很容易地看到,随着离群值的数量的增加,每个算法的性能也降低。然而,NSDE算法获得最佳的性能在几乎所有情况下,尽管离群值上升95%以上。

经过实验测试的方法考虑一组基准实验。方法的效率评估的均方误差(MSE)和峰值信噪比(PSNR)测量。实验结果,考虑真实图像提供证据的显著性能提出古典RANSAC方法相比。

魏克森讯号等级测试(41)是一种非参数检验用于定量地比较一些实验数据并确定是否存在一个有意义的差异。通过应用测试中包含的数据表2,发现算法NSGA-II NSDE 5%的意义有很大的不同,因此可以认为NSDE给出更好的结果比NSGA-II两种算法应用于单应性问题。顺序相同的思想,相同的测试是用来比较NSGA-II和RANSAC算法,导致第一个算法比第二个好。

7所示。结论

在这个工作的使用两个多目标进化算法结合点通讯提出了估计图像之间的单应性对。在这种方法下,估计过程被认为是一个多目标问题的数量匹配点和允许误差同时优化。在这种情况下,有能力找到最佳的方法这两个目标之间的平衡。

仔细检查标准的偏离表1表明NSGA-II维护一个大分散在其解决方案。这方面主要是强调MSE指数。这种矛盾的结果NSGA-II在其执行能力产生类似的解决方案。相反,比NSGA-II NSDE产生更好的解决方案的准确性和一致性(MSE)。另一方面,作为一个更高的PSNR值表明,更高质量的评估,结果由NSDE算法表现出最好的性能。

为了解决多目标制定、两种不同的进化算法探索:第二Nondominated排序遗传算法(NSGA-II)和Nondominated排序差分进化(NSDE)。

经过几次测试,发现NSDE给出更好的结果在解决图像匹配问题,根据已知的统计检验一组实验结果。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

这项工作得到了Consejo Nacional de Ciencia y Tecnologia CONACYT,各种补贴。