转载: http://blog.csdn.net/luoshixian099/article/details/48523267
CSDN-勿在浮沙筑高台
没有时间重新复制代码,只能一股脑的复制,所以代码效果不好。。。。。。
为了满足实时性的要求,前面文章中介绍过快速提取特征点算法Fast,以及特征描述子Brief。本篇文章介绍的ORB算法结合了Fast和Brief的速度优势,并做了改进,且ORB是免费。
Ethan Rublee等人2011年在《ORB:An Efficient Alternative to SIFT or SURF》文章中提出了ORB算法。结合Fast与Brief算法,并给Fast特征点增加了方向性,使得特征点具有旋转不变性,并提出了构造金字塔方法,解决尺度不变性,但文章中没有具体详述。实验证明,ORB远优于之前的SIFT与SURF算法。
-------------------------------------------------------------------------------------------------------------------------------
论文核心内容概述:
1.构造金字塔,在每层金字塔上采用Fast算法提取特征点,采用Harris角点响应函数,按角点响应值排序,选取前N个特征点。
2. oFast:计算每个特征点的主方向,灰度质心法,计算特征点半径为r的圆形邻域范围内的灰度质心位置。从中心位置到质心位置的向量,定义为该特 征点的主方向。
定义矩的计算公式,x,y∈[-r,r]:
质心位置:
主方向:
3.rBrief:为了解决旋转不变性,把特征点的Patch旋转到主方向上(steered
Brief)。通过实验得到,描述子在各个维度上的均值比较离散(偏离0.5),同时维度间相关性很强,说明特征点描述子区分性不好,影响匹配的效果。论文中提出采取学习的方法,采用300K个训练样本点。每一个特征点,选取Patch大小为wp=31,Patch内每对点都采用wt=5大小的子窗口灰度均值做比较,子窗口的个数即为N=(wp-wt)*(wp-wt),从N个窗口中随机选两个做比较即构成描述子的一个bit,论文中采用M=205590种可能的情况:
---------------------------------------------------------------------------------
1.对所有样本点,做M种测试,构成M维的描述子,每个维度上非1即0;
2.按均值对M个维度排序(以0.5为中心),组成向量T;
3.贪婪搜索:把向量T中第一个元素移动到R中,然后继续取T的第二个元素,与R中的所有元素做相关性比较,如果相关性大于指定的阈值Threshold, 抛弃T的这个元素,否则加入到R中;
4.重复第3个步骤,直到R中有256个元素,若检测完毕,少于256个元素,则降低阈值,重复上述步骤;
----------------------------------------------------------------------------------
rBrief:通过上面的步骤取到的256对点,构成的描述子各维度间相关性很低,区分性好;
训练前 训练后
---------------------------------------------------------------------------------------------------------------------------------
ORB算法步骤,参考opencv源码:
1.首先构造尺度金字塔;
金字塔共n层,与SIFT不同,每层仅有一副图像;
第s层的尺度为,Fator初始尺度(默认为1.2),原图在第0层;
第s层图像大小:
;
2.在不同尺度上采用Fast检测特征点;在每一层上按公式计算需要提取的特征点数n,在本层上按Fast角点响应值排序,提取前2n个特征点,然后根据Harris 角点响应值排序, 取前n个特征点,作为本层的特征点;
3.计算每个特征点的主方向(质心法);
4.旋转每个特征点的Patch到主方向,采用上述步骤3的选取的最优的256对特征点做τ测试,构成256维描述子,占32个字节;
,,n=256
4.采用汉明距离做特征点匹配;
----------OpenCV源码解析-------------------------------------------------------
ORB类定义:位置..\features2d.hpp
nfeatures:需要的特征点总数;
scaleFactor:尺度因子;
nlevels:金字塔层数;
edgeThreshold:边界阈值;
firstLevel:起始层;
WTA_K:描述子形成方法,WTA_K=2表示,采用两两比较;
scoreType:角点响应函数,可以选择Harris或者Fast的方法;
patchSize:特征点邻域大小;
[cpp]
/*!
CV_EXPORTS_W ORB : Feature2D
{
:
{ kBytes = 32, HARRIS_SCORE=0, FAST_SCORE=1 };
CV_WRAP ORB( nfeatures = 500, scaleFactor = 1.2f, nlevels = 8, edgeThreshold = 31,
firstLevel = 0, WTA_K=2, scoreType=ORB::HARRIS_SCORE, patchSize=31 );
descriptorSize() ;
descriptorType() ;
operator()(InputArray image, InputArray mask, vector<KeyPoint>& keypoints) ;
operator()( InputArray image, InputArray mask, vector<KeyPoint>& keypoints,
OutputArray descriptors, useProvidedKeypoints= ) ;
AlgorithmInfo* info() ;
:
computeImpl( Mat& image, vector<KeyPoint>& keypoints, Mat& descriptors ) ;
detectImpl( Mat& image, vector<KeyPoint>& keypoints, Mat& mask=Mat() ) ;
CV_PROP_RW nfeatures;
CV_PROP_RW scaleFactor;
CV_PROP_RW nlevels;
CV_PROP_RW edgeThreshold;
CV_PROP_RW firstLevel;
CV_PROP_RW WTA_K;
CV_PROP_RW scoreType;
CV_PROP_RW patchSize;
};
特征提取及形成描述子:通过这个函数对图像提取Fast特征点或者计算特征描述子
_image:输入图像;
_mask:掩码图像;
_keypoints:输入角点;
_descriptors:如果为空,只寻找特征点,不计算特征描述子;
_useProvidedKeypoints:如果为true,函数只计算特征描述子;
[cpp]
/** Compute the ORB features and descriptors on an image
* @param keypoints the resulting keypoints
* @param do_keypoints if true, the keypoints are computed, otherwise used as an input
*/ ORB::operator()( InputArray _image, InputArray _mask, vector<KeyPoint>& _keypoints,
OutputArray _descriptors, useProvidedKeypoints)
{
CV_Assert(patchSize >= 2);
do_keypoints = !useProvidedKeypoints;
do_descriptors = _descriptors.needed();
( (!do_keypoints && !do_descriptors) || _image.empty() )
;
HARRIS_BLOCK_SIZE = 9;
halfPatchSize = patchSize / 2;.
border = std::max(edgeThreshold, std::max(halfPatchSize, HARRIS_BLOCK_SIZE/2))+1;
Mat image = _image.getMat(), mask = _mask.getMat();
( image.type() != CV_8UC1 )
cvtColor(_image, image, CV_BGR2GRAY);
levelsNum = ->nlevels;
( !do_keypoints )
{
levelsNum = 0;
( i = 0; i < _keypoints.size(); i++ )
levelsNum = std::max(levelsNum, std::max(_keypoints[i].octave, 0));
levelsNum++;
}
vector<Mat> imagePyramid(levelsNum), maskPyramid(levelsNum);
( level = 0; level < levelsNum; ++level)
{
scale = 1/getScale(level, firstLevel, scaleFactor);
static inline float getScale(int level, int firstLevel, double scaleFactor)
return (float)std::pow(scaleFactor, (double)(level - firstLevel));
*/ Size sz(cvRound(image.cols*scale), cvRound(image.rows*scale));
Size wholeSize(sz.width + border*2, sz.height + border*2);
Mat temp(wholeSize, image.type()), masktemp;
imagePyramid[level] = temp(Rect(border, border, sz.width, sz.height));
( !mask.empty() )
{
masktemp = Mat(wholeSize, mask.type());
maskPyramid[level] = masktemp(Rect(border, border, sz.width, sz.height));
}
( level != firstLevel )
{
( level < firstLevel )
{
resize(image, imagePyramid[level], sz, 0, 0, INTER_LINEAR);
(!mask.empty())
resize(mask, maskPyramid[level], sz, 0, 0, INTER_LINEAR);
}
{
resize(imagePyramid[level-1], imagePyramid[level], sz, 0, 0, INTER_LINEAR);
(!mask.empty())
{
resize(maskPyramid[level-1], maskPyramid[level], sz, 0, 0, INTER_LINEAR);
threshold(maskPyramid[level], maskPyramid[level], 254, 0, THRESH_TOZERO);
}
}
copyMakeBorder(imagePyramid[level], temp, border, border, border, border,
BORDER_REFLECT_101+BORDER_ISOLATED);
(!mask.empty())
copyMakeBorder(maskPyramid[level], masktemp, border, border, border, border,
BORDER_CONSTANT+BORDER_ISOLATED);
}
{
copyMakeBorder(image, temp, border, border, border, border,
BORDER_REFLECT_101);
( !mask.empty() )
copyMakeBorder(mask, masktemp, border, border, border, border,
BORDER_CONSTANT+BORDER_ISOLATED);
}
}
vector < vector<KeyPoint> > allKeypoints;
( do_keypoints )
{
computeKeyPoints(imagePyramid, maskPyramid, allKeypoints,
nfeatures, firstLevel, scaleFactor,
edgeThreshold, patchSize, scoreType);
for (int level = 0; level < n_levels; ++level)
vector<KeyPoint>& keypoints = all_keypoints[level];
keypoints.clear();
keypoint_end = temp.end(); keypoint != keypoint_end; ++keypoint)
}
{
KeyPointsFilter::runByImageBorder(_keypoints, image.size(), edgeThreshold);
allKeypoints.resize(levelsNum);
(vector<KeyPoint>::iterator keypoint = _keypoints.begin(),
keypointEnd = _keypoints.end(); keypoint != keypointEnd; ++keypoint)
allKeypoints[keypoint->octave].push_back(*keypoint);
( level = 0; level < levelsNum; ++level)
{
(level == firstLevel)
;
vector<KeyPoint> & keypoints = allKeypoints[level];
scale = 1/getScale(level, firstLevel, scaleFactor);
(vector<KeyPoint>::iterator keypoint = keypoints.begin(),
keypointEnd = keypoints.end(); keypoint != keypointEnd; ++keypoint)
keypoint->pt *= scale;
}
}
Mat descriptors;
vector<Point> pattern;
( do_descriptors )
{
nkeypoints = 0;
( level = 0; level < levelsNum; ++level)
nkeypoints += ()allKeypoints[level].size();
( nkeypoints == 0 )
_descriptors.release();
{
_descriptors.create(nkeypoints, descriptorSize(), CV_8U);
descriptors = _descriptors.getMat();
}
npoints = 512;
Point patternbuf[npoints];
Point* pattern0 = ( Point*)bit_pattern_31_;
( patchSize != 31 )
{
pattern0 = patternbuf;
makeRandomPattern(patchSize, patternbuf, npoints);
}
CV_Assert( WTA_K == 2 || WTA_K == 3 || WTA_K == 4 );
( WTA_K == 2 )
std::copy(pattern0, pattern0 + npoints, std::back_inserter(pattern));
{
ntuples = descriptorSize()*4;
initializeOrbPattern(pattern0, pattern, ntuples, WTA_K, npoints);
}
}
_keypoints.clear();
offset = 0;
( level = 0; level < levelsNum; ++level)
{
vector<KeyPoint>& keypoints = allKeypoints[level];
nkeypoints = ()keypoints.size();
(do_descriptors)
{
Mat desc;
(!descriptors.empty())
{
desc = descriptors.rowRange(offset, offset + nkeypoints);
}
offset += nkeypoints;
Mat& workingMat = imagePyramid[level];
GaussianBlur(workingMat, workingMat, Size(7, 7), 2, 2, BORDER_REFLECT_101);
computeDescriptors(workingMat, keypoints, desc, pattern, descriptorSize(), WTA_K);
}
(level != firstLevel)
{
scale = getScale(level, firstLevel, scaleFactor);
(vector<KeyPoint>::iterator keypoint = keypoints.begin(),
keypointEnd = keypoints.end(); keypoint != keypointEnd; ++keypoint)
keypoint->pt *= scale;
}
_keypoints.insert(_keypoints.end(), keypoints.begin(), keypoints.end());
}
}
(1)提取角点:computeKeyPoints
imagePyramid:即构造好的金字塔
[cpp]
/** Compute the ORB keypoints on an image
* @param keypoints the resulting keypoints, clustered per level
computeKeyPoints( vector<Mat>& imagePyramid,
vector<Mat>& maskPyramid,
vector<vector<KeyPoint> >& allKeypoints,
nfeatures, firstLevel, scaleFactor,
edgeThreshold, patchSize, scoreType )
{
nlevels = ()imagePyramid.size();
vector<> nfeaturesPerLevel(nlevels);
factor = ()(1.0 / scaleFactor);
ndesiredFeaturesPerScale = nfeatures*(1 - factor)/(1 - ()pow(()factor, ()nlevels));
sumFeatures = 0;
( level = 0; level < nlevels-1; level++ )
{
nfeaturesPerLevel[level] = cvRound(ndesiredFeaturesPerScale);
sumFeatures += nfeaturesPerLevel[level];
ndesiredFeaturesPerScale *= factor;
}
nfeaturesPerLevel[nlevels-1] = std::max(nfeatures - sumFeatures, 0);
halfPatchSize = patchSize / 2;
vector<> umax(halfPatchSize + 2);
v, v0, vmax = cvFloor(halfPatchSize * sqrt(2.f) / 2 + 1);
vmin = cvCeil(halfPatchSize * sqrt(2.f) / 2);
(v = 0; v <= vmax; ++v)
umax[v] = cvRound(sqrt(()halfPatchSize * halfPatchSize - v * v));
(v = halfPatchSize, v0 = 0; v >= vmin; --v)
{
(umax[v0] == umax[v0 + 1])
++v0;
umax[v] = v0;
++v0;
}
allKeypoints.resize(nlevels);
( level = 0; level < nlevels; ++level)
{
featuresNum = nfeaturesPerLevel[level];
allKeypoints[level].reserve(featuresNum*2);
vector<KeyPoint> & keypoints = allKeypoints[level];
FastFeatureDetector fd(20, );
fd.detect(imagePyramid[level], keypoints, maskPyramid[level]);
KeyPointsFilter::runByImageBorder(keypoints, imagePyramid[level].size(), edgeThreshold);
( scoreType == ORB::HARRIS_SCORE )
{
KeyPointsFilter::retainBest(keypoints, 2 * featuresNum);
HarrisResponses(imagePyramid[level], keypoints, 7, HARRIS_K);
}
KeyPointsFilter::retainBest(keypoints, featuresNum);
sf = getScale(level, firstLevel, scaleFactor);
(vector<KeyPoint>::iterator keypoint = keypoints.begin(),
keypointEnd = keypoints.end(); keypoint != keypointEnd; ++keypoint)
{
keypoint->octave = level;
keypoint->size = patchSize*sf;
}
computeOrientation(imagePyramid[level], keypoints, halfPatchSize, umax);
}
}
(2)为每个角点计算主方向,质心法;
[cpp]
static computeOrientation( Mat& image, vector<KeyPoint>& keypoints,
halfPatchSize, vector<>& umax)
{
(vector<KeyPoint>::iterator keypoint = keypoints.begin(),
keypointEnd = keypoints.end(); keypoint != keypointEnd; ++keypoint)
{
keypoint->angle = IC_Angle(image, halfPatchSize, keypoint->pt, umax);
}
}
[cpp]
static IC_Angle( Mat& image, half_k, Point2f pt,
vector<> & u_max)
{
m_01 = 0, m_10 = 0;
uchar* center = &image.at<uchar> (cvRound(pt.y), cvRound(pt.x));
( u = -half_k; u <= half_k; ++u)
m_10 += u * center[u];
step = ()image.step1();
( v = 1; v <= half_k; ++v)
{
v_sum = 0;
d = u_max[v];
( u = -d; u <= d; ++u)
{
val_plus = center[u + v*step], val_minus = center[u - v*step];
v_sum += (val_plus - val_minus);
m_10 += u * (val_plus + val_minus);
}
m_01 += v * v_sum;
}
fastAtan2(()m_01, ()m_10);
}
(3)计算特征点描述子
[cpp]
static computeDescriptors( Mat& image, vector<KeyPoint>& keypoints, Mat& descriptors,
vector<Point>& pattern, dsize, WTA_K)
{
CV_Assert(image.type() == CV_8UC1);
descriptors = Mat::zeros(()keypoints.size(), dsize, CV_8UC1);
( i = 0; i < keypoints.size(); i++)
computeOrbDescriptor(keypoints[i], image, &pattern[0], descriptors.ptr(()i), dsize, WTA_K);
}
[cpp]
static computeOrbDescriptor( KeyPoint& kpt,
Mat& img, Point* pattern,
uchar* desc, dsize, WTA_K)
{
angle = kpt.angle;
angle *= ()(CV_PI/180.f);
a = ()cos(angle), b = ()sin(angle);
uchar* center = &img.at<uchar>(cvRound(kpt.pt.y), cvRound(kpt.pt.x));
step = ()img.step;
center[cvRound(pattern[idx].x*b + pattern[idx].y*a)*step + \
cvRound(pattern[idx].x*a - pattern[idx].y*b)]
x, y;
ix, iy;
(x = pattern[idx].x*a - pattern[idx].y*b, \
y = pattern[idx].x*b + pattern[idx].y*a, \
ix = cvFloor(x), iy = cvFloor(y), \
x -= ix, y -= iy, \
cvRound(center[iy*step + ix]*(1-x)*(1-y) + center[(iy+1)*step + ix]*(1-x)*y + \
center[iy*step + ix+1]*x*(1-y) + center[(iy+1)*step + ix+1]*x*y))
( WTA_K == 2 )
{
( i = 0; i < dsize; ++i, pattern += 16)
{
t0, t1, val;
t0 = GET_VALUE(0); t1 = GET_VALUE(1);
val = t0 < t1;
t0 = GET_VALUE(2); t1 = GET_VALUE(3);
val |= (t0 < t1) << 1;
t0 = GET_VALUE(4); t1 = GET_VALUE(5);
val |= (t0 < t1) << 2;
t0 = GET_VALUE(6); t1 = GET_VALUE(7);
val |= (t0 < t1) << 3;
t0 = GET_VALUE(8); t1 = GET_VALUE(9);
val |= (t0 < t1) << 4;
t0 = GET_VALUE(10); t1 = GET_VALUE(11);
val |= (t0 < t1) << 5;
t0 = GET_VALUE(12); t1 = GET_VALUE(13);
val |= (t0 < t1) << 6;
t0 = GET_VALUE(14); t1 = GET_VALUE(15);
val |= (t0 < t1) << 7;
desc[i] = (uchar)val;
}
}
( WTA_K == 3 )
{
( i = 0; i < dsize; ++i, pattern += 12)
{
t0, t1, t2, val;
t0 = GET_VALUE(0); t1 = GET_VALUE(1); t2 = GET_VALUE(2);
val = t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0);
t0 = GET_VALUE(3); t1 = GET_VALUE(4); t2 = GET_VALUE(5);
val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 2;
t0 = GET_VALUE(6); t1 = GET_VALUE(7); t2 = GET_VALUE(8);
val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 4;
t0 = GET_VALUE(9); t1 = GET_VALUE(10); t2 = GET_VALUE(11);
val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 6;
desc[i] = (uchar)val;
}
}
( WTA_K == 4 )
{
( i = 0; i < dsize; ++i, pattern += 16)
{
t0, t1, t2, t3, u, v, k, val;
t0 = GET_VALUE(0); t1 = GET_VALUE(1);
t2 = GET_VALUE(2); t3 = GET_VALUE(3);
u = 0, v = 2;
( t1 > t0 ) t0 = t1, u = 1;
( t3 > t2 ) t2 = t3, v = 3;
k = t0 > t2 ? u : v;
val = k;
t0 = GET_VALUE(4); t1 = GET_VALUE(5);
t2 = GET_VALUE(6); t3 = GET_VALUE(7);
u = 0, v = 2;
( t1 > t0 ) t0 = t1, u = 1;
( t3 > t2 ) t2 = t3, v = 3;
k = t0 > t2 ? u : v;
val |= k << 2;
t0 = GET_VALUE(8); t1 = GET_VALUE(9);
t2 = GET_VALUE(10); t3 = GET_VALUE(11);
u = 0, v = 2;
( t1 > t0 ) t0 = t1, u = 1;
( t3 > t2 ) t2 = t3, v = 3;
k = t0 > t2 ? u : v;
val |= k << 4;
t0 = GET_VALUE(12); t1 = GET_VALUE(13);
t2 = GET_VALUE(14); t3 = GET_VALUE(15);
u = 0, v = 2;
( t1 > t0 ) t0 = t1, u = 1;
( t3 > t2 ) t2 = t3, v = 3;
k = t0 > t2 ? u : v;
val |= k << 6;
desc[i] = (uchar)val;
}
}
CV_Error( CV_StsBadSize,
}
参考:
Ethan Rublee et. ORB:An Efficient Alternative to SIFT or SURF
http://www.cnblogs.com/ronny/p/4083537.html