随机抽样一致

✍ dations ◷ 2025-07-07 08:28:52 #计算机视觉,算法

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

相关

  • 肌筋膜疼痛综合征肌筋膜疼痛症候群(英语:Myofascial pain syndrome,简称MPS)是一类病症,主要呈现为肌肉之慢性疼痛。在一些病例上疼痛甚为剧烈。其与骨骼肌上之激痛点(Trigger points)有关;激痛点为
  • 萨斯基雅·萨森萨斯基雅·萨森(荷兰语:Saskia Sassen,1949年1月5日-),荷兰与美国社会学家,分析全球化和国际人类迁徙。她目前是哥伦比亚大学社会学罗伯特·S·林德教授和伦敦经济学院客座教授。萨
  • 电热膜远红外线辐射电热膜是一种通电后能发热的透明聚酯薄膜,由可传导性碳纤维为主成分的油墨、金属载流条经加工、热压在绝缘聚酯薄膜间制成。不同于传统的电热丝发热,以电热膜为发
  • 默达尔阿尔瓦·米达尔(瑞典语:Alva Myrdal,1902年1月31日-1986年2月1日),瑞典社会学家和政治家。她是瑞典社会民主工人党的资深党员,从1950年到1955年,她是第一位女性在联合国教科文组织其
  • 支持摩根索计划摩根索计划(Morgenthau Plan)是二战期间提出的德国占领计划之一,计划的提出人是美国财政部长小亨利·摩根索。该计划的内容包括将德国分为南、北德;将德国的主要工业区萨尔兰鲁
  • 赤化赤化是自二十世纪初沙俄被苏共推翻后,遗留下来的政治敏感性字眼。由于世界各地的共产党皆以红色作为主色,故赤化就是指“共产化”,因此在一些国家里面共产党被其敌对党称为“赤
  • 学院 (大学)学院(Faculty, College, School),日韩汉字称为学部 ,是大学的分支教学单位,属于一个或一组相关学科主题领域。不同学院负责不同学科的概念追溯到艾资哈尔大学,为一所伊斯兰学校设
  • 贾特拉帕蒂·希瓦吉·摩诃罗阇终点站坐标:27°10′30″N 78°02′32″E / 27.17500°N 78.04222°E / 27.17500; 78.04222贾特拉帕蒂·希瓦吉·摩诃罗阇终点站(马拉提语:छत्रपती शिवाजी महाराज
  • 莉莲·吉什莉莲·戴安娜·吉什(英语:Lillian Diana Gish,1893年10月14日-1993年2月27日)是一名童星出身的美国电影演员,默片年代的银幕标志之一,奥斯卡金像奖终身成就奖得主,肯尼迪中心荣誉奖
  • 南米东吉区南米东吉区(马达加斯加语:Midongy),是马达加斯加的行政区,位于该国东南部,由阿齐莫-阿齐那那那区负责管辖,首府设于米东吉,面积2,700平方公里,2011年人口43,413,人口密度每平方公里16