BlenderCN论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1018|回复: 0

RANSAC算法开发记录

[复制链接]
发表于 2017-5-24 12:23:46 | 显示全部楼层 |阅读模式
背景介绍
    RANSAC (The RANdom Sample Consensus algorithm) 是一种样本筛选算法,在对极几何中,用来剔除错误匹配的对应点,以提高单应矩阵(homography)、基本矩阵(fundamental matrix)、本质矩阵(essential matrix)等参数的估算精度,从而提高相机位置、姿态以及后续三维重建的精度。
    另外,深圳同学对RANSAC算法还有一个见解,即RANSAC算法在大数据量时可以减少计算量。具体而言,假设在计算基本矩阵时,匹配点非常多,例如1000对,按照基本矩阵的估算流程,在SVD分解时,需要进行分解的矩阵为1000*9,考虑在单片机上进行解算程序,这将是一个非常大的矩阵,可能需要花费相当多的时间,直接造成计算频率降低,飞机控制延迟。而解决的办法是从这些匹配点中随机抽取一个小数量样本,以这个样本为基础计算基本矩阵,这种做法类似抽样估计。
基础程序模块
1 随机数生成器
    这里使用Python3版本,对应的随机数使用可以参考博客[Liang, 2016],其推荐使用random库的random()函数,输出数据符合(0-1)的均匀分布。
2 随机选取
   随机选取的应用背景是提高对极几何计算精度,需要从匹配点中进行筛选并剔除误差大或者被错误估计的匹配点。
    以二维平面上的线形拟合为例,在RANSAC算法中,需要从所有点中随机选取两个点。具体算法从获取点的总数开始,假设总数为N,将每一个点按顺序编号(这里从0开始),编号假设为ni;为每一个点赋予一个数字区间,这里设定为[ni,ni+1);使用符合(0-N)均匀分布的随机数生成器产生随机数,该随机数落在哪个区间,就认为哪个区间所对应的点被选取。
    上述算法是随机选取的最基本原理,在选取一个点的时候可以直接使用,但若要选取多个点,如本节所举示例,即选取两个点,或者在本节应用背景,即计算单应矩阵(4对匹配点)、基本矩阵(8对匹配点等)等,都需要选取多个点,在这种应用下,上述算法存在一个问题,即同一点被重复选取,而上述算法中,点不可以重复使用。
    解决方法之一是在每一次选取点之后,对剩余点进行重新排序编号。另外一个解决方法是记录每一次所选取点的编号,在下一次随机数生成时,若得到已被选取的点的编号,则进行重新选取。这两种解决方法需要配合使用,在备选匹配点数量少时,使用第一种方法更好,而在匹配点数量多时,使用第二种方法更好。
p1.png
第二种方法
Blender框架 - Python模块
1 获取场景物体
    目标是场景中的每一个物体,这些物体都在 bpy.context.scene.objects中保管,获取方法见图。
    bpy.context.scene.objects是一个Python列表,在本文计算流程的第一阶段中,直接用这个列表作为物体数据存储和提取的对象。
p2.jpeg


2 提取物体参数
    上文提到,blender场景中的物体数据都保存在bpy.context.scene.objects中,这是一个python列表,保存的数据包括物体名称、物体坐标等。
p3.jpeg


3 设置选中物体 Active Object
    在Blender的3D View中,物体存在一个称为”Active”的状态,图形操作上体现为用鼠标右键点选,出现黄色边框时,即表示该物体为”Active”。处于这种状态的物体可以被执行删除、缩放等操作。
    具体方法如图,首先将物体的数据成员”select”设置为”True”,再将这个物体赋予“bpy.context.scene.objects.active”即可。
p4.jpeg
本文Active Object的应用有清除所有物体的缩放、旋转等,见下图。
p5.jpeg

计算流程
    本文定制的RANSAC的计算流程从引入匹配点入手,分为三个阶段。
1 第一阶段-采集匹配点
    引入所有匹配点。本文的匹配点来自blender建模空间中的所有物体,因此需要遍历每一个物体,采集其坐标,并保存在一个列表中。
    在blender中,物体坐标数据保存在”bpy.context.scene.objects”中,它是一个python列表,等效于C/C++的数组。因此,方便起见,本文在提取坐标时,直接使用这个列表,而不使用另外设置的列表存储这些坐标数据。
2 第二阶段-样本直线拟合和Inlier, Outlier判定
    本阶段进行匹配点随机采样、直线拟合、Inlier, Outlier判定以及拟合结果评价。这一阶段需要被重复进行,以比较不同采样拟合结果,当然,这个比较的工作是下一阶段的任务。
    匹配点随机采样就是前文所介绍的随机选取,这里随机选取两个点。
    直线拟合时,由于只选取两个点,且两点确定一条直线,所以直线方程的确定不需要用估算的方法,而使用直接计算的方法,也就是中学数学所说的直线两点方程。
    Inlier(局内点)和Outlier(局外点)以该点到直线的距离进行评价。
3 第三阶段-评价拟合模型

   
参考文献



您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐上一条 /1 下一条

Blender最新中文教学视频|Blender头条|小黑屋|手机版|Archiver|Blender中国 ( 蜀ICP备17002929号 )360网站安全检测平台

GMT+8, 2019-3-22 09:03 , Processed in 0.017297 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表