随机抽样一致

✍ dations ◷ 2025-07-08 17:06:34 #计算机视觉,算法

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

相关

  • 脱氧糖脱氧糖(英语:Deoxy sugars)是指糖分子中有一个羟基被氢原子所替代的糖。例子包括:果聚糖:菊粉 · 果聚糖β2→6甘露聚糖:低聚木糖:半乳聚糖:
  • 瓦尔多斯塔瓦尔多斯塔(英语:Valdosta)是一个位于美国佐治亚州朗兹县的城市。根据2010年美国人口普查,该地共人口54518人,而该地的面积约为78.40平方千米。同时该地也是朗兹县的县治。瓦尔多
  • 山奈酚山柰酚(Kaempferol)是一种天然黄酮类化合物,是存在于茶叶、西兰花、翠雀草、金缕梅、葡萄柚、抱子甘蓝、苹果等植物中植源性物质。山柰酚为黄色结晶体,熔点为276-278℃,微溶于
  • 北京林业大学822万余平方米北京林业大学,简称北林,原名北京林学院,创办于1952年10月16日,是中华人民共和国全国重点大学之一,亦是中华人民共和国教育部直属、教育部与国家林业局共建的农林类
  • 育乐台纬来育乐台,前称纬来洋片台,是纬来电视网旗下结合运动赛事转播及欧美电影与影集于一台的综合性频道。2005年,由于纬来电视网在中华职棒该季季中接手全部的赛事,将当时的纬来洋片
  • 澳洲海狮澳洲海狮(学名:Neophoca cinerea,英语:Australian sea lion)是一种只生活在澳大利亚南部和西部海岸的海狮。新海狮属现存的唯一一种生物。澳大利亚海狮属于鳍足亚目,与海狮科的其
  • 科幻世界《科幻世界》(英语:Science Fiction World,缩写SFW)是总部位于中华人民共和国四川省成都市的中文月刊,创刊于1979年,前身是《奇谈》和《科学文艺》,是中国乃至世界发行量最大的科幻
  • 万亿分率万亿分率,台湾称兆分率,简称ppt(源自英语Parts Per Trillion的简写),定义为万亿分之一,1ppt即是万亿分之一分之一。 1 p p t =
  • 约翰·巴耳末约翰·雅各布·巴耳末(Johann Jakob Balmer,1825年5月1日-1898年3月12日),又译巴尔末,瑞士数学家、物理学家。主要贡献是建立了氢原子光谱波长的经验公式——巴耳末公式。巴耳末18
  • 自反闭包在数学中,集合 上的二元关系 的 自反闭包 是 上包含 的最小的自反关系。例如,若定义 为数的集合,并定义关系 当且仅当 严格小于 ,则 的自反闭包为关系 满足“ 当且仅