RANSAC算法详解：图像分析与自动地图制作的关键技术

随机采样

RANSAC

4星 · 超过85%的资源需积分: 50 127 浏览量更新于2023-03-03 2 收藏 1.2MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

随机采样一致算法（Random Sample Consensus, RANSAC）是计算机图形学和图像处理领域的一项关键技术，由马丁·A·费施勒（Martin A. Fischler）和罗伯特·C·鲍尔斯（Robert C. Bolles）在SRI国际公司提出。该算法的主要目标是解决在实验数据中存在大量明显错误的情况下的模型拟合问题，特别适用于自动化图像分析，其中数据解读往往依赖于可能存在误差的特征检测结果。 RANSAC的核心理念是通过随机选取样本集合，不断尝试建立模型，并基于这些样本进行模型评估。算法的关键步骤包括： 1. **随机抽样**：从原始数据集中抽取少量（通常是少数）样本点，构建一个假设模型。 2. **一致性检验**：检查构建的模型是否能良好地解释这些样本点，即判断该模型与抽样点之间的偏差是否低于某个阈值，通常称为“一致集”。 3. **迭代优化**：重复上述过程，每次选择不同的样本，直到找到一个能够解释大部分数据且满足一致性的最佳模型。 4. **模型确认**：根据一致集的数量和置信度确定最终模型的可靠性，即使只有少数样本支持，只要模型能解释大部分数据，就认为找到了最优解。在文章中，RANSAC的应用被重点聚焦在“位置确定问题”（Location Determination Problem, LDP）上。LDP的目标是从一幅包含已知地标图像中，确定拍摄该图像的相机位置。作者探讨了如何利用RANSAC来解决这个问题，包括计算在保证解的存在性所需的最少地标数量，以及提出求解最小地标数解的封闭形式算法。这些成果对于开发自动化系统，特别是在难以确定精确信息的场景中，如地理定位或视觉SLAM（同时定位与映射）至关重要。RANSAC不仅提供了解决问题的有效方法，还促进了计算机视觉领域的进步，使得系统能够在复杂环境中鲁棒地处理和分析数据。RANSAC是一个强大的工具，它的理论基础和实践应用在当前和未来都将继续影响和推动计算机图形学和机器视觉的研究与实践。

资源详情

资源推荐

cause the above heuristic to fail (for example, see Figure

1). It is our contention that averaging is not an appro-

priate technique to apply to an unverified data set.

In the following section we introduce the RANSAC

paradigm, which is capable of smoothing data that con-

tain a significant percentage of gross errors. This para-

digm is particularly applicable to scene analysis because

local feature detectors, which often make mistakes, are

the source of the data provided to the interpretation

algorithms. Local feature detectors make two types of

errors--classification errors and measurement errors.

Classification errors occur when a feature detector in-

correctly identifies a portion of an image as an occur-

rence of a feature. Measurement errors occur when the

feature detector correctly identifies the feature, but

slightly miscalculates one of its parameters (e.g., its image

location). Measurement errors generally follow a normal

distribution, and therefore the smoothing assumption is

applicable to them. Classification errors, however, are

gross errors, having a significantly larger effect than

measurement errors, and do not average out.

In the final sections of this paper the application of

RANSAC tO the location determination problem is dis-

cussed:

Given a set of "landmarks" ("control points"), whose locations are

known in some coordinate frame, determine the location (relative to

the coordinate frame of the landmarks) of that point in space from

which an image of the landmarks was obtained.

In response to a RANSAC requirement, some new

results are derived on the minimum number of land-

marks needed to obtain a solution, and then algorithms

are presented for computing these minimum-landmark

solutions in closed form. (Conventional techniques are

iterative and require a good initial guess to assure con-

vergence.) These results form the basis for an automatic

system that can solve the LDP under severe viewing and

analysis conditions. In particular, the system performs

properly even if a significant number of landmarks are

incorrectly located due to low visibility, terrain changes,

or image analysis errors. Implementation details and

experimental results are presented to complete our de-

scription of the LDP application.

II. Random Sample Consensus

The RANSAC procedure is opposite to that of conven-

tional smoothing techniques: Rather than using as much

of the data as possible to obtain an initial solution and

then attempting to eliminate the invalid data points,

RANSAC uses as small an initial data set as feasible and

enlarges this set with consistent data when possible. For

example, given the task of fitting an arc of a circle to a

set of two-dimensional points, the RANSAC approach

would be to select a set of three points (since three points

are required to determine a circle), compute the center

and radius of the implied circle, and count the number

of points that are close enough to that circle to suggest

their compatibility with it (i.e., their deviations are small

enough to be measurement errors). If there are enough

compatible points, RANSAC would employ a smoothing

technique such as least squares, to compute an improved

estimate for the parameters of the circle now that a set

of mutually consistent points has been identified.

The RANSAC paradigm is more formally stated as

follows:

Given a model that requires a minimum of n data points to instantiate

its free parameters, and a set of data points P such that the number of

points in P is greater than n [g(P) __- n], randomly select a subset SI of

n data points from P and instantiate the model. Use the instantiated

model M1 to determine the subset SI* of points in P that are within

some error tolerance of Ml. The set SI* is called the consensus set of

S1.

If g (SI*) is greater than some threshold t, which is a function of the

estimate of the number of gross errors in P, use SI* to compute

(possibly using least squares) a new model MI *.

If g (SI*) is less than t, randomly select a new subset $2 and repeat the

above process. If, after some predetermined number of trials, no

consensus set with t or more members has been found, either solve the

model with the largest consensus set found, or terminate in failure.

There are two obvious improvements to the above

algorithm: First, if there is a problem related rationale

for selecting points to form the S's, use a deterministic

selection process instead of a random one; second, once

a suitable consensus set S* has been found and a model

M* instantiated, add any new points from P that are

consistent with M* to S* and compute a new model on

the basis of this larger set.

The RANSAC paradigm contains three unspecified

parameters: (1) the error tolerance used to determine

whether or not a point is compatible with a model, (2)

the number of subsets to try, and (3) the threshold t,

which is the number of compatible points used to imply

that the correct model has been found. Methods are

discussed for computing reasonable values for these pa-

rameters in the following subsections.

A. Error Tolerance For Establishing Datum/Model

Compatibility

The deviation of a datum from a model is a function

of the error associated with the datum and the error

associated with the model (which, in part, is a function

of the errors associated with the data used to instantiate

the model). If the model is a simple function of the data

points, it may be practical to establish reasonable bounds

on error tolerance analytically. However, this straight-

forward approach is often unworkable; for such cases it

is generally possible to estimate bounds on error toler-

ance experimentally. Sample deviations can be produced

by perturbing the data, computing the model, and mea-

suring the implied errors. The error tolerance could then

be set at one or two standard deviations beyond the

measured average error.

The expected deviation of a datum from an assumed

model is generally a function of the datum, and therefore

the error tolerance should be different for each datum.

However, the variation in error tolerances is usually

383

Communications June

1981

of Volume 24

the ACM Number 6

剩余14页未读，继续阅读

lct721521

粉丝: 12
资源: 5

会员权益专享

RANSAC算法详解：图像分析与自动地图制作的关键技术

基于特征匹配和RANSAC的三维点云拼接配准方法，matlab实现

随机抽样一致性算法（matlab）

Matlab粗配准代码和图片

pcl随机采样一致性:ransac圆柱体拟合

SAC-IA算法和Ransac算法的区别

pcl平面拟合算法ransac

改写并扩写“RANSAC是一种能从包含离群值的数据中对数学模型中的参数进行迭代式估计的随机采样算法。”

seg.setOptimizeCoefficients(true); // Mandatory-设置目标几何形状 seg.setModelType(pcl::SACMODEL_PLANE); //分割方法：随机采样法 seg.setMethodType(pcl::SAC_RANSAC);seg.segment(*inliers, *coefficients);

点云RANSAC算法改进

ransac算法图像匹配matlab

基于pcl的ransac算法分割提取球体

为什么 RANSAC 算法本质上是一个拟合问题

使用python完成全景图像拼接，其中ransac算法和image warping算法需要自行实现

使用PCL编写一段改进的RANSAC算法：实现改变RANSAC的选点范围，判断每个点的z坐标，设置一个z轴上下范围，在该范围内进行随机选点，利用RANSAC算法选取内点最多的平面，并将平面显示出来。写出每行代码的中文注释

ransac算法图像匹配python

RANSAC算法拟合圆柱体

FPFH+RANSAC+ICP

匹配度量、变换矩阵解算、ransac算法分析

vs2019 pcl ransac点云分割算法

改写并扩写“本章介绍了图像匹配和SURF算法。首先使用SURF算法实现圆形印章的粗匹配，然后，利用 RANSAC算法对 SURF算法进行了剔除，从而得到了准确的匹配结果，实现印章的精确匹配。”

会员权益专享

最新资源

seg.setOptimizeCoefficients(true); // Mandatory-设置目标几何形状 seg.setModelType(pcl::SACMODEL_PLANE); //分割方法：随机采样法 seg.setMethodType(pcl::SAC_RANSAC);seg.segment(inliers, coefficients);