随机抽样一致

✍ dations ◷ 2025-10-26 11:52:55 #计算机视觉,算法

随机抽样一致算法(RANdom SAmple Consensus,RANSAC)。它采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。RANSAC是一个非确定性算法,在某种意义上说,它会产生一个在一定概率下合理的结果,而更多次的迭代会使这一概率增加。此RANSAC算法在1981年由Fischler和Bolles首次提出。

RANSAC的基本假设是

这里用一个简单的例子来说明,在一组数据点中找到一条最适合的线。假设,此有一组集合包含了内群以及离群,其中内群为可以被拟合到线段上的点,而离群则是无法被拟合的点。如果我们用简单的最小二乘法来找此线,我们将无法得到一条适合于内群的线,因为最小二乘法会受离群影响而影响其结果。而RANSAC,可以只由内群来计算出模型,而且概率还够高。然而,RANSAC无法保证结果一定最好,所以必须小心选择参数,使其能有足够的概率。

包含许多离群的一组数据,要找一条最适合的线。

RANSAC找到的线,离群值对结果没影响(蓝色点为内群,红色点为离群)

这里有几个问题

假设每个点是真正内群的几率是 w {\displaystyle w} ,则:

通常我们不知道 w {\displaystyle w} 是多少, w n {\displaystyle w^{n}} 是所选择的 n {\displaystyle n} 个点都是内群的几率, 1 w n {\displaystyle 1-w^{n}} 是所选择的 n {\displaystyle n} 个点至少有一个不是内群的几率, ( 1 w n ) k {\displaystyle (1-w^{n})^{k}} 是表示重复 k {\displaystyle k} 次都没有全部的 n {\displaystyle n} 个点都是内群的几率,假设算法跑 k {\displaystyle k} 次以后成功的几率是 p {\displaystyle p} ,那么:

所以如果希望成功几率高, p = 0.99 {\displaystyle p=0.99} ,当 n {\displaystyle n} 不变时, k {\displaystyle k} 越大, p {\displaystyle p} 越大,当 w {\displaystyle w} 不变时, n {\displaystyle n} 越大,所需的 k {\displaystyle k} 就越大,通常 w {\displaystyle w} 未知,所以 n {\displaystyle n} 选小一点比较好。

RANSAC算法经常用在计算机视觉领域,例如,对于一对立体相机,同时求解其对应点问题(英语:Correspondence_problem)和估计它们之间的基础矩阵。

相关

  • 拉特兰宫拉特朗宫(意大利语:Palazzo Laterano)位于意大利罗马市区东南方的拉特朗圣若望广场,毗邻罗马的主教座堂拉特朗圣若望大殿,自4世纪以后的一千年中一直是教宗的主要驻地。目前开设
  • 购买力平价国内生产总值这是按照各国国内生产总值(GDP)排序的列表。页面上提供的美元估算的国内生产总值,都根据购买力平价(PPP)的计算产生。因各机构统计模型不同,所以得出的数据与排名也略有差异。当比
  • 大气标高标高(scale height),又译特性高、尺度高、标尺高、比高,是一个长度,可用来比较同一个物理量在不同环境的减少率。如果一个物理量每经过一段距离 H
  • 郭斐蔚郭斐蔚(Frederick Rogers Graves,1858年-1940年)是美国圣公会传教士。上海第五任主教(1893-1937)。郭斐蔚参与创建了中华圣公会,1915年至1926年担任主教院主席。继任者为罗培德。郭
  • 过一硫酸过氧一硫酸,也称为过氧硫酸、过硫酸,化学式H2SO5,无色固体,熔点45°C。这种酸中硫的氧化态为VI,可以表示为HO-O-S(O)2-OH。虽然已经制得了过一硫酸的苯甲酰衍生物,但过一硫酸却是
  • 图书分类法图书分类法(英语:Library classification)是图书馆为方便图书典藏和借阅而采取的一种分类方法,一般分类法分为基本法(按主题分类)和附加法(按年代、地域、语言分类),还可以人为按版本
  • 伊斯迈·马扬伊斯迈·马扬(马来语:Ismail bin Marjan,1920年-1991年1月25日),马来亚/新加坡前男子羽毛球运动员,他在1940年代至1950年代赢得许多国内和国际比赛的单打和双打冠军。当伊斯迈参加D
  • 高地德语高地德语(德语:Hochdeutsche Sprachen)泛指今日的标准德语及各种德语方言,包括:卢森堡语及意第绪语,以及各种在德国中、南部和奥地利、列支敦士登、瑞士、卢森堡等地、邻近德国的
  • 保罗·约翰逊保罗·马歇尔·约翰逊, Jr.(Paul Marshall Johnson, Jr.,1955年5月8日-2004年6月18日)是一名居住在沙特阿拉伯的美国直升机工程师,出生于新泽西州,他在沙特阿拉伯遭武装分子劫持后
  • 皇家陆军工兵博物馆英国陆军工兵博物馆、图书馆和档案馆(英语:Royal Engineers Museum, Library and Archive)是一座位于英国肯特郡吉林汉姆的军事工程博物馆和图书馆。它讲述了英国皇家工程兵团