随机采样一致算法RANSAC_边缘检测评判标准资源-CSDN文库

随机采样

RANSAC

4星 · 超过85%的资源需积分: 50 75 浏览量 2010-06-13 11:59:20 上传评论 2 收藏 1.2MB PDF 举报

资源推荐

资源详情

资源评论

Graphics and

Image Processing

J. D. Foley

Editor

Random Sample

Consensus: A

Paradigm for Model

Fitting with

Apphcatlons to

Image

Analysis and

Automated

Cartography

Martin A. Fischler and Robert C. Bolles

SRI International

A new paradigm, Random Sample Consensus

(RANSAC),

for fitting a model to experimental data is

introduced. RANSAC is capable of interpreting/

smoothing data containing a significant percentage of

gross errors, and is thus ideally suited for applications

in automated image analysis where interpretation is

based on the data provided by error-prone feature

detectors. A major portion of this paper describes the

application of RANSAC to the Location Determination

Problem (LDP): Given an image depicting a set of

landmarks with known locations, determine that point

in space from which the image was obtained. In

response to a RANSAC requirement, new results are

derived on the minimum number of landmarks needed

to obtain a solution, and algorithms are presented for

computing these minimum-landmark solutions in closed

form. These results provide the basis for an automatic

system that can solve the LDP under difficult viewing

Permission to copy without fee all or part of this material is

granted provided that the copies are not made or distributed for direct

commercial advantage, the ACM copyright notice and the title of the

publication and its date appear, and notice is given that copying is by

permission of the Association for Computing Machinery. To copy

otherwise, or to republish, requires a fee and/or specific permission.

The work reported herein was supported by the Defense Advanced

Research Projects Agency under Contract Nos. DAAG29-76-C-0057

and MDA903-79-C-0588.

Authors' Present Address: Martin A. Fischler and Robert C.

Bolles, Artificial Intelligence Center, SRI International, Menlo Park

CA 94025.

381

and analysis conditions. Implementation details and

computational examples are also presented.

Key Words and Phrases: model fitting, scene

analysis, camera calibration, image matching, location

determination, automated cartography.

CR Categories: 3.60, 3.61, 3.71, 5.0, 8.1, 8.2

I. Introduction

We introduce a new paradigm, Random Sample

Consensus

(RANSAC),

for fitting a model to experimental

data; and illustrate its use in scene analysis and auto-

mated cartography. The application discussed, the loca-

tion determination problem (LDP), is treated at a level

beyond that of a mere example of the use of the RANSAC

paradigm; new basic findings concerning the conditions

under which the LDP can be solved are presented and

a comprehensive approach to the solution of this problem

that we anticipate will have near-term practical appli-

cations is described.

To a large extent, scene analysis (and, in fact, science

in general) is concerned with the interpretation of sensed

data in terms of a set of predefmed models. Conceptually,

interpretation involves two distinct activities: First, there

is the problem of finding the best match between the

data and one of the available models (the classification

problem); Second, there is the problem of computing the

best values for the free parameters of the selected model

(the parameter estimation problem). In practice, these

two problems are not independent--a solution to the

parameter estimation problem is often required to solve

the classification problem.

Classical techniques for parameter estimation, such

as least squares, optimize (according to a specified ob-

jective function) the fit of a functional description

(model) to

all

of the presented data. These techniques

have no internal mechanisms for detecting and rejecting

gross errors. They are averaging techniques that rely on

the assumption (the smoothing assumption) that the

maximum expected deviation of any datum from the

assumed model is a direct function of the size of the data

set, and thus regardless of the size of the data set, there

will always be enough good values to smooth out any

gross deviations.

In many practical parameter estimation problems the

smoothing assumption does not hold; i.e., the data con-

tain uncompensated gross errors. To deal with this situ-

ation, several heuristics have been proposed. The tech-

nique usually employed is some variation of first using

all the data to derive the model parameters, then locating

the datum that is farthest from agreement with the

instantiated model, assuming that it is a gross error,

deleting it, and iterating this process until either the

maximum deviation is less then some preset threshold or

until there is no longer sufficient data to proceed.

It can easily be shown that a single gross error

("poisoned point"), mixed in with a set of good data, can

Communications June 1981

of Volume 24

the ACM Number 6

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页未读，继续阅读

评论收藏

内容反馈

peipeidd

2013-08-14

很不错比较有用

lct721521

粉丝: 12
资源: 5

随机采样一致算法RANSAC

！！基于随机抽样一致性的多平面区域检测算法

RANSAC.zip_RANSAC_ransac点云_一致性算法_算法_采样一致性

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

基于优化采样的RANSAC图像匹配算法

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

Matlab粗配准代码和图片

随机采样一致性算法拟合直线，效果好

随机等效采样算法在数字存储示波器上的实现.pdf

基于随机采样的多量测目标跟踪算法

基于改进的RANSAC的场景分类点云粗配准算法

论文研究-稀疏分量分析的RANSAC算法.pdf

改进的RANSAC算法在三维点云配准中的应用

基于MATLAB和RANSAC的车道线检测程序

新建文本文档.zip_一致性_随机采样一致性算法概述

RANSAC.rar_RANSAC_RANSAC算法_ransac算法matlab_site:www.pudn.com_算法一致

带 RANSAC 的最小二乘函数：15 个随机创建的点根据最小二乘定理通过应用 RANSAC 算法被分成 2 部分-matlab开发

基于随机下采样和SMOTE的不均衡SVM分类算法

mengtekaluo.zip_蒙 卡 抽样_蒙特卡洛 采样_蒙特卡洛 抽样_蒙特卡洛算法_随机蒙特卡洛

RANSAC算法剔除匹配误配点原理

论文研究-基于改进RANSAC的消防机器人双目障碍检测.pdf

compare_pcl_gpucpu-master.zip_pcl cuda_pcl GPU_pcl GPU加速_pcl gp

SIFT+RANSAC

基于随机抽样一致算法的误匹配标志点校正方法

alohamatlab代码-stochasticGreedyMRI:优化MRI笛卡尔采样的随机贪婪算法

hadoop-imbalanced-preprocessing:MapReduce 使用 Hadoop 实现随机过采样、随机欠采样和“合成少数过采样技术”（SMOTE）算法

ChatGPT的随机采样算法与重要性采样算法的比较.docx

test_particlefilter_20151102.rar_particle filter_重采样_重采样算法_随机重采样

最新资源

mengtekaluo.zip_蒙卡抽样_蒙特卡洛采样_蒙特卡洛抽样_蒙特卡洛算法_随机蒙特卡洛