【RANSAC】 匹配特征点

RANSAC为RANdom SAmple Consensus的缩写,它是根据一组包含异常数据的样本数据集,计算出数据的数学模型参数,得到有效样本数据的算法。它于1981年由 Fischler和Bolles最先提出[1]。

RANSAC算法基本假设:样本中包含正确数据(inliers,可以被模型描述的数据),也包含异常数据(Outliers,偏离正常范围很远、无法适应数学模型的数据),即数据集中含有噪声(可能是由于错误的测量、错误的假设、错误的计算等产生的)。SO,给定一组正确的数据,存在可以计算出符合这些数据的模型参数的方法。

RANSAC基本思想描述如下:
①考虑一个最小抽样集的势为n的模型(n为初始化模型参数所需的最小样本数)和一个样本集P,集合P的样本数#(P)>n,从P中随机抽取包含n个样本的P的子集S初始化模型M;
②余集SC=P\S中与模型M的误差小于某一设定阈值t的样本集以及S构成S*。S*认为是内点集,它们构成S的一致集(Consensus Set);
③若#(S*)≥N,认为得到正确的模型参数,并利用集S*(内点inliers)采用最小二乘等方法重新计算新的模型M*;重新随机抽取新的S,重复以上过程。
④在完成一定的抽样次数后,若为找到一致集则算法失败,否则选取抽样后得到的最大一致集判断内外点,算法结束。
由上可知存在两个可能的算法优化策略。①如果在选取子集S时可以根据某些已知的样本特性等采用特定的选取方案或有约束的随机选取来代替原来的完全随机选取;②当通过一致集S*计算出模型M*后,可以将P中所有与模型M*的误差小于t的样本加入S*,然后重新计算M*。
RANSAC算法包括了3个输入的参数:①判断样本是否满足模型的误差容忍度t。t可以看作为对内点噪声均方差的假设,对于不同的输入数据需要采用人工干预的方式预设合适的门限,且该参数对RANSAC性能有很大的影响;②随机抽取样本集S的次数。该参数直接影响SC中样本参与模型参数的检验次数,从而影响算法的效率,因为大部分随机抽样都受到外点的影响;③表征得到正确模型时,一致集S*的大小N。为了确保得到表征数据集P的正确模型,一般要求一致集足够大;另外,足够多的一致样本使得重新估计的模型参数更精确。
RANSAC算法经常用于计算机视觉中,主要解决特征点的匹配中的错配问题。

 

搜集各种跟CV,AR相关的代码,如无特别声明,均是c/c++。还是一贯的标准,不求全面,只求质量。

通用库/General Library

无需多言。

Recognition And Vision Library. 线程安全。强大的IO机制。包含AAM。

很酷的一个图像处理包。整个库只有一个头文件。包含一个基于PDE的光流算法。

图像,视频IO/Image, Video IO

AR相关/Augmented Reality

基于Marker的AR库

ARToolKit的增强版。实现了更好的姿态估计算法。

实时的跟踪、SLAM、AR库。无需Marker,模板,内置传感器等。

基于特征点检测和识别的AR库。

局部不变特征/Local Invariant Feature

目前最好的Sift开源实现。同时包含了KD-tree,KD-Forest,BoW实现。

基于Naive Bayesian Bundle的特征点识别。高速,但占用内存高。

基于OpenCV的Sift实现。

目标检测/Object Detection

又一个AdaBoost实现。训练速度快。

基于Centrist和Linear SVM的快速行人检测。

(近似)最近邻/ANN

目前最完整的(近似)最近邻开源库。不但实现了一系列查找算法,还包含了一种自动选取最快算法的机制。

另外一个近似最近邻库。

SLAM & SFM

monoSLAM库。由Androw Davison开发。

图像分割/Segmentation

使用Simple Linear Iterative Clustering产生指定数目,近似均匀分布的Super Pixel。

目标跟踪/Tracking

基于Online Random Forest的目标跟踪算法。

Kanade-Lucas-Tracker

Online Boosting Trackers

直线检测/Line Detection

基于联通域连接的直线检测算法。

基于梯度的,局部直线段检测算子。

指纹/Finger Print

基于感知的多媒体文件Hash算法。(提取,对比图像、视频、音频的指纹)

图像检索/Image Retrieval

Pyramid Matching Algorithm实现。

一个简单的的Vocabulary Tree实现。

视觉显著性/Visual Salience

Ming-Ming Cheng的视觉显著性算法。

FFT/DWT

最快,最好的开源FFT。

轻量级的FFT实现。许可证是亮点。

音频处理/Audio processing

音频处理,音频合成。

音频文件IO。

音频重采样。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

生活在西班牙

自己动手丰衣足食

BlueAsteroid

Just another WordPress.com site

Jing's Blog

Just another WordPress.com site

Start from here......

我的心情魔方

天才遠私廚

希望能做一個分享各種資訊的好地方

语义噪声

西瓜大丸子汤的博客

笑对人生,傲立寰宇

Just another WordPress.com site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision

datarazzi

Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness

槑烎

1,2,∞

Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: