随机抽样一致

✍ dations ◷ 2025-10-18 16:41:20 #计算机视觉,算法

随机抽样一致算法(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)和估计它们之间的基础矩阵。

相关

  • 俄罗斯苏维埃社会主义共和国全俄中央执行委员会全俄苏维埃代表大会(1917–1938)最高苏维埃(1938–1990)俄罗斯苏维埃联邦社会主义共和国(俄语:Российская Советская Федеративн
  • 精神病房里的正常人罗森汉恩实验(Rosenhan Experiment)是1973年美国心理学家大卫·罗森汉恩关于检验美国精神病患鉴定标准的一项著名实验,并当年发布在《科学》杂志上。这项研究被认为是对精神病
  • 格鲁特岛格鲁特岛(荷兰语:Groote Eylandt)是澳大利亚北领地的卡奔塔利亚湾的最大岛屿,也是澳大利亚全国的第四大岛屿,面积有2326平方公里。位于安海姆地以东50公里。1623年威廉船长(Willem
  • 沼岛沼岛(日语:沼島/ぬしま Nushima */?)是日本淡路岛南方的一座小岛,距淡路岛约5公里。面积2.5平方公里,岛上最高点海拔117.2米,行政上隶属于兵库县南淡路市,常住人口598人。沼岛亦属
  • 威金斯安德鲁·威金斯(英语:Andrew Wiggins,1995年2月23日-),加拿大职业篮球运动员,现效于NBA金州勇士,绰号“枸杞哥”“养生曼巴”。 在2014年NBA选秀上,他以第一轮第1顺位被克利夫兰骑士
  • 艾怡良艾怡良(Eve Ai,1987年3月24日-),知名华语流行音乐创作歌手,毕业于师大附中,国立台湾艺术大学视觉传达设计学系学士。出生于台北市万华区。艾怡良为华语乐坛灵魂乐唱腔的代表。2010
  • 专性厌氧菌专性厌氧菌(obligate anaerobes)是一类仅能进行无氧呼吸,且无法在正常大气(氧含量21%)等富氧环境下存活的微生物。这类生物对氧气的耐受力不同,部分专性厌氧菌可以在氧含量达8%的
  • 2012年NBA季后赛2012年NBA季后赛是国家篮球协会(NBA)于2011-12 NBA赛季结束后所进行的第66届NBA季后赛,赛程共进行2个月。下列日期以美国当地时间计算各联盟的前四名种子由各赛区排名第一的
  • 安东尼·麦考利夫安东尼·克莱门特·麦考利夫(英语:Anthony Clement "Nuts" McAuliffe,1898年7月2日-1975年8月11日),二战军人,美国陆军上将。1944年突出部战役期间,时任第101空降师代理师长的麦考利
  • 劳动党 (韩国)2008年3月16日 (2008-03-16)(进歩新党) 劳动党是韩国的一个左翼社会主义政党。在新进步党、社会党合并之后,它的名字改为劳动党(不同于朝鲜劳动党)。 它于2013年7月21日举行了