论文部分内容阅读
摘要：在棉花图像分割与识别的基础上，为获得棉花三维空间位置信息，需要对双目采集的棉花图像对进行精确的匹配。采用加速分割检测特征、加速鲁棒性特征和BBF方法匹配棉花图像对。首先采用FAST检测图像角点，并计算各角点的SURF描述向量，然后采用BBF方法搜索匹配点对，最后利用RANSAC和极线约束剔除误匹配点对，为下一步准确定位棉花三维空间位置信息奠定基础。
关键词：FAST；SURF；BBF；RANSAC；外极线约束
中图分类号：S126 文献标志码：A 文章编号：1002-1302（2014）03-0343-03
图像匹配在三维重构、导航图像处理、图像搜索、图像融合等计算机视觉领域应用广泛，基于局部特征的匹配逐渐成为研究的热点。基于特征点的检测算法，如Harris-Affine、SIFT[1-2]算法，能够实现较准确的匹配对，但计算时间较长。2006年，Bay等人提出SURF（speeded-up robust features）特征算子在匹配性能方面接近SIFT算法，但计算时间较快，王海丽[3-4]等人将SURF算法应用于SAR图像等领域，实现匹配的抗视角变换。上述匹配算法特征点的边缘特性较差，在计算时间方面仍然较长。本研究在前人研究的基础上提出基于FAST角点检测、SURF描述向量和BBF搜索匹配点的算法，具有良好的边缘特性与高效的分割速度。
1 研究方法
1.1 FAST角点检测
加速分割检测特征（features from accelerated segment test，FAST）是一种简单快速的角点探测算法，当某个像素点的周围领域内有足够多的像素点与该点处于不同的灰度区域时，该点被确认为一个FAST角点。应用到灰度图像中，即有足够多的像素点的灰度值大于该点的灰度值或者小于该点的灰度值。考虑图像中任意一个像素点和以它为中心的一个区域，通常选择圆形区域，图1给出了以该点为中心的圆形区域的模板情况，该圆形区域为一个半径等于3像素的离散化区域，最外围的像素点按顺时针顺序依次编号为1～16。
一个候选点是否为角点可以用一个角点响应函数来判断，即：
N=∑x（circle（p））|Ix-Ip|>εd
（1）
式中：Ix表示圆周上任意一点的图像灰度值；Ip表示中心像素点的图像灰度值；p表示中心像素点即候选点；εd为给定的一个极小阈值。通过该角点响应函数，计算出圆周上满足公式（1）像素点的个数N。如果N大于给定的一个阈值，就可以确定该候选点为角点。为实现快速计算，一般选择n=12。角点检测可简化为检测像素编号为1、9、5、13的4个像素点，因为在该4个像素点中，有3个均满足公式（1），才能被确认为角点，如此可以快速排除整幅图像中的很多像素点，提高角点检测的时间效率。
1.2 SURF描述向量
SURF描述向量主要是根据特征点邻域范围内的灰度统计信息[5-6]，通过计算主方向和特征向量来得到的，具体步骤如下。
1.2.1 SURF特征点主方向的确定 本研究采取将原图检测到的极值点转换到灰度图像中，利用灰度图像的信息生成特征描述向量。为保证旋转不变性，以特征点为圆心、6σ（σ为特征点所在的尺度值）为半径的圆形区域内的所有像素x和y方向上的Haar小波响应dx和dy，使每个像素点都有一个对应的Haar小波响应点Hp（dx，dy）；然后，通过一个大小为600的扇形滑动窗口对所有小波响应进行求和，选择长度最长的方向作为特征点的主方向。
1.2.2 基于Haar小波响应生成描述向量 SURF特征向量提取是在一个以特征点为中心、与主方向平行的方形区域中进行的：首先确定一个以特征点为中心、大小为20S的方形区域，为使提取到的特征向量具有抗旋转特性，需要旋转该方形区域，使之与特征点的主方向平行；然后，将这个方形区域再均匀细分成4×4个子区域，在每个子区域中统计x和y方向上的Haar小波响应之和及其绝对值之和（∑dx，∑dy，∑|dx|，∑|dy|）。在统计的过程中，仍用以特征点为中心的高斯函数进行赋权处理。如此，每个子区域有一个四维的描述子V4=（∑dx，∑dy，∑|dx|，∑|dy|），整个区域就有4×4×4=64维的特征向量。再进行归一化，形成特征点的描述向量。
1.3 二叉树搜索图像匹配点对
1.3.1 K-D树 K-D树是一棵平衡二叉树，K-D代表 K-Dimension，每个节点即为一个K维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为2个部分，这样递归的从根节点不停的划分，直到没有实例为止[7-8]。
K-D树的最近邻搜索算法如下：
（1）在K-D树中找出包含目标点x的叶结点：从根结点出发，递归地向下搜索K-D树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止。
（2）以此叶结点为“当前最近点”。
（3）递归的向上回溯，在每个结点进行以下操作：（a）如果该结点保存的实例点比当前最近点距离目标点更近，则更新“当前最近点”，也就是说以该实例点为“当前最近点”。（b）当前最近点一定存在于该结点一个子结点对应的区域，检查子结点的父结点的另一子结点对应的区域是否有更近的点。
1.3.2 BBF查询算法 BBF（best bin first）是对K-D树搜索算法的改进。实际上，K-D树搜索算法大部分时间花费在检查节点上，而只有一部分节点满足最近邻条件，因此，可以采用近似的最近邻算法，通过限制K-D树中叶子节点数来缩短搜索时间。优化改进方法是以节点和被查询节点距离递增的顺序来搜索节点。当沿一个方向的分支搜索一节点时，优先级队会被加入一个成员，该成员记录了该节点相关的信息，包括当前节点在树中的位置和该节点与被查询节点之间的距离。当一个叶节点被搜索到后，从队首删除一项；然后，再搜索包括最近节点的其他分支。 1.4 RANSAC与极限约束剔除伪匹配
在匹配点对中仍然存在部分误匹配对以及匹配不准的点，由于匹配点对的正确率在很大程度上决定了后期进行三维重建的精度，因此需要对初始匹配点对集合进行进一步的筛选。本研究利用RANSAC算法在未得到基本矩阵的情况下消除误匹配点对，同时获得优化后的基本矩阵，再利用极线约束进一步得到高精度的匹配点对，为下一步的三维重建打下良好的基础。
（1）归一化八点法解基本矩阵
从n组点匹配的集合可以得到一个线性方程组：
Af=x1′x1x1′y1x1′y1′x1y1′y1y1′x1y11
xn′xnxn′ynxn′yn′xnyn′ynyn′xnyn1=0
利用归一化8点法可以求解上述方程组，可以得到基本矩阵F。具体算法如下：
归一化：根据xi ^=Txi和xi ^′=T′xi′变换图像坐标，其中T和T′是归一化变换，由平移和缩放组成。它将点集Xi变换到新的点集X～i，使得该点集X～i的形心位于原点（0，0）T，并且它原点的平均距离是2。对特征点进行归一化处理，可以提高算法的精度。由对应匹配xi ^xi ^′形成A^，由A^的最小奇异值的奇异矢景，即A^的SVD分解A^=UDVT中矩阵V的最后一列矢量来确定F^。但由于基本矩阵的秩为2，所以必须通过强制惟约束，用SVD法将F^的秩归为2，并以F′代替F使得detF′=0。
解除归一化：令F=TTF^′T。矩阵F是对应于原始数据 xi ^xi ^′ 的基本矩阵。
（2）极线约束
根据对极几何原理，其对应几何关系如图2所示，如果已知空间点M在左图像中的像点m，那么它在右图像中的对应点m′必然约束于对极线l′上，因此存在一个从左视图上的点到右视图上与之对应的对极线的映射：m→l′，这个映射也可表示成矩阵形式，称为基本矩阵F，基本矩阵的本质描述了2个摄像机平面的位置关系。
（3）RANSAC算法与极线约束的匹配点优化
在初始匹配结果中，随机选择8组匹配点构成的一个随机样本，并按归一化八点法来计算基本矩阵F。根据计算得到的F，对每组假设对应计算距离d=xi ^′Fxi ^。根据基本矩阵的定义，理论上xi ^′Fxi ^=0，但是由于有误匹配点对的存在以及匹配点的不准确造成d不为零，因此可以定义d 如图3所示，通过前面所求得的最佳基本矩阵F即可画出对应的极线，左图中的直线为右图中的点在左图中找到的相对应极线。根据对极几何原理，若为精确匹配点对，则极线应该穿过左图中的匹配点，因此可以滤除那些距离极线较远的点，从而保留那些精确匹配的点对[10]。
2 结果与分析
本研究是基于研究采棉机器人视觉系统基金项目，为实现棉花的三维空间定位，在图像分割的基础上实现图像对的精确匹配。
本试验条件为CPU2.80G、内存2G。
FAST角点检测算法是在灰度图像中检测角点，有足够多的像素点的灰度值大于该点的灰度值或者小于该点的灰度值。由图4可以看出，利用FAST检测出的角点均在棉花的边缘或是棉花的形心位置，有很好的边缘特性，利于定位采摘点的位置信息。并且，FAST角点检测出1 339个特征点，而SURF角点检测算法只检测出415个特征点，且部份特征点分布于棉花目标外，不能用于棉花采摘点的定位（图5）。因此本研究采用FAST角点检测算法用于检测棉花图像对的特征点。
由于SURF方法具有良好的抗旋转性，而且SURF向量为64维，相比于SIFT（128维）向量具有更低的维数，具有更快的速度。SURF特征向量如图6所示。
基于上述检测出的特征点与特征向量，建立K-D树，并采用BBF方法搜索图像匹配的对，结果如图7所示。
从图7可以看出，195对匹配点对中仍然存在部分误匹配点对，采用RANSAC剔除误匹配点对，结果如图8所示。
采用RANSAC方法剔除误匹配点对后，采用极限约束准则进一步提高匹配精度，淘汰掉一些匹配精度不高的匹配的对，结果如图9所示。
在图像对匹配中，图像对往往伴随着旋转、缩放等各种复杂情况，在图9中分别就图像缩放、旋转30°、180°条件采用本研究方法进行匹配，仍然可以得到很精确的匹配的对，切特征点均分布在棉花的边缘与棉花的型心位置（图9b、c）。
为评价匹配效果，将本研究的匹配方法分别与SURF和SIFT方法进行比较[11-12]，其对比结果如表1所示。
参考文献：
[1]李玲玲，李翠华，曾晓明，等. 基于Harris-Affine和SIFT特征匹配的图像自动配准[J]. 华中科技大学学报：自然科学版，2008，36（8）：13-16.
[2]谢 凡，秦世引. 基于SIFT的单目移动机器人宽基线立体匹配[J]. 仪器仪表学报，2008，29（11）：2247-2252.
关键词：FAST；SURF；BBF；RANSAC；外极线约束
中图分类号：S126 文献标志码：A 文章编号：1002-1302（2014）03-0343-03
图像匹配在三维重构、导航图像处理、图像搜索、图像融合等计算机视觉领域应用广泛，基于局部特征的匹配逐渐成为研究的热点。基于特征点的检测算法，如Harris-Affine、SIFT[1-2]算法，能够实现较准确的匹配对，但计算时间较长。2006年，Bay等人提出SURF（speeded-up robust features）特征算子在匹配性能方面接近SIFT算法，但计算时间较快，王海丽[3-4]等人将SURF算法应用于SAR图像等领域，实现匹配的抗视角变换。上述匹配算法特征点的边缘特性较差，在计算时间方面仍然较长。本研究在前人研究的基础上提出基于FAST角点检测、SURF描述向量和BBF搜索匹配点的算法，具有良好的边缘特性与高效的分割速度。
1 研究方法
1.1 FAST角点检测
加速分割检测特征（features from accelerated segment test，FAST）是一种简单快速的角点探测算法，当某个像素点的周围领域内有足够多的像素点与该点处于不同的灰度区域时，该点被确认为一个FAST角点。应用到灰度图像中，即有足够多的像素点的灰度值大于该点的灰度值或者小于该点的灰度值。考虑图像中任意一个像素点和以它为中心的一个区域，通常选择圆形区域，图1给出了以该点为中心的圆形区域的模板情况，该圆形区域为一个半径等于3像素的离散化区域，最外围的像素点按顺时针顺序依次编号为1～16。
一个候选点是否为角点可以用一个角点响应函数来判断，即：
N=∑x（circle（p））|Ix-Ip|>εd
（1）
式中：Ix表示圆周上任意一点的图像灰度值；Ip表示中心像素点的图像灰度值；p表示中心像素点即候选点；εd为给定的一个极小阈值。通过该角点响应函数，计算出圆周上满足公式（1）像素点的个数N。如果N大于给定的一个阈值，就可以确定该候选点为角点。为实现快速计算，一般选择n=12。角点检测可简化为检测像素编号为1、9、5、13的4个像素点，因为在该4个像素点中，有3个均满足公式（1），才能被确认为角点，如此可以快速排除整幅图像中的很多像素点，提高角点检测的时间效率。
1.2 SURF描述向量
SURF描述向量主要是根据特征点邻域范围内的灰度统计信息[5-6]，通过计算主方向和特征向量来得到的，具体步骤如下。
1.2.1 SURF特征点主方向的确定 本研究采取将原图检测到的极值点转换到灰度图像中，利用灰度图像的信息生成特征描述向量。为保证旋转不变性，以特征点为圆心、6σ（σ为特征点所在的尺度值）为半径的圆形区域内的所有像素x和y方向上的Haar小波响应dx和dy，使每个像素点都有一个对应的Haar小波响应点Hp（dx，dy）；然后，通过一个大小为600的扇形滑动窗口对所有小波响应进行求和，选择长度最长的方向作为特征点的主方向。
1.2.2 基于Haar小波响应生成描述向量 SURF特征向量提取是在一个以特征点为中心、与主方向平行的方形区域中进行的：首先确定一个以特征点为中心、大小为20S的方形区域，为使提取到的特征向量具有抗旋转特性，需要旋转该方形区域，使之与特征点的主方向平行；然后，将这个方形区域再均匀细分成4×4个子区域，在每个子区域中统计x和y方向上的Haar小波响应之和及其绝对值之和（∑dx，∑dy，∑|dx|，∑|dy|）。在统计的过程中，仍用以特征点为中心的高斯函数进行赋权处理。如此，每个子区域有一个四维的描述子V4=（∑dx，∑dy，∑|dx|，∑|dy|），整个区域就有4×4×4=64维的特征向量。再进行归一化，形成特征点的描述向量。
1.3 二叉树搜索图像匹配点对
1.3.1 K-D树 K-D树是一棵平衡二叉树，K-D代表 K-Dimension，每个节点即为一个K维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为2个部分，这样递归的从根节点不停的划分，直到没有实例为止[7-8]。
K-D树的最近邻搜索算法如下：
（1）在K-D树中找出包含目标点x的叶结点：从根结点出发，递归地向下搜索K-D树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止。
（2）以此叶结点为“当前最近点”。
（3）递归的向上回溯，在每个结点进行以下操作：（a）如果该结点保存的实例点比当前最近点距离目标点更近，则更新“当前最近点”，也就是说以该实例点为“当前最近点”。（b）当前最近点一定存在于该结点一个子结点对应的区域，检查子结点的父结点的另一子结点对应的区域是否有更近的点。
1.3.2 BBF查询算法 BBF（best bin first）是对K-D树搜索算法的改进。实际上，K-D树搜索算法大部分时间花费在检查节点上，而只有一部分节点满足最近邻条件，因此，可以采用近似的最近邻算法，通过限制K-D树中叶子节点数来缩短搜索时间。优化改进方法是以节点和被查询节点距离递增的顺序来搜索节点。当沿一个方向的分支搜索一节点时，优先级队会被加入一个成员，该成员记录了该节点相关的信息，包括当前节点在树中的位置和该节点与被查询节点之间的距离。当一个叶节点被搜索到后，从队首删除一项；然后，再搜索包括最近节点的其他分支。 1.4 RANSAC与极限约束剔除伪匹配
在匹配点对中仍然存在部分误匹配对以及匹配不准的点，由于匹配点对的正确率在很大程度上决定了后期进行三维重建的精度，因此需要对初始匹配点对集合进行进一步的筛选。本研究利用RANSAC算法在未得到基本矩阵的情况下消除误匹配点对，同时获得优化后的基本矩阵，再利用极线约束进一步得到高精度的匹配点对，为下一步的三维重建打下良好的基础。
（1）归一化八点法解基本矩阵
从n组点匹配的集合可以得到一个线性方程组：
Af=x1′x1x1′y1x1′y1′x1y1′y1y1′x1y11
xn′xnxn′ynxn′yn′xnyn′ynyn′xnyn1=0
利用归一化8点法可以求解上述方程组，可以得到基本矩阵F。具体算法如下：
归一化：根据xi ^=Txi和xi ^′=T′xi′变换图像坐标，其中T和T′是归一化变换，由平移和缩放组成。它将点集Xi变换到新的点集X～i，使得该点集X～i的形心位于原点（0，0）T，并且它原点的平均距离是2。对特征点进行归一化处理，可以提高算法的精度。由对应匹配xi ^xi ^′形成A^，由A^的最小奇异值的奇异矢景，即A^的SVD分解A^=UDVT中矩阵V的最后一列矢量来确定F^。但由于基本矩阵的秩为2，所以必须通过强制惟约束，用SVD法将F^的秩归为2，并以F′代替F使得detF′=0。
解除归一化：令F=TTF^′T。矩阵F是对应于原始数据 xi ^xi ^′ 的基本矩阵。
（2）极线约束
根据对极几何原理，其对应几何关系如图2所示，如果已知空间点M在左图像中的像点m，那么它在右图像中的对应点m′必然约束于对极线l′上，因此存在一个从左视图上的点到右视图上与之对应的对极线的映射：m→l′，这个映射也可表示成矩阵形式，称为基本矩阵F，基本矩阵的本质描述了2个摄像机平面的位置关系。
（3）RANSAC算法与极线约束的匹配点优化
在初始匹配结果中，随机选择8组匹配点构成的一个随机样本，并按归一化八点法来计算基本矩阵F。根据计算得到的F，对每组假设对应计算距离d=xi ^′Fxi ^。根据基本矩阵的定义，理论上xi ^′Fxi ^=0，但是由于有误匹配点对的存在以及匹配点的不准确造成d不为零，因此可以定义d 如图3所示，通过前面所求得的最佳基本矩阵F即可画出对应的极线，左图中的直线为右图中的点在左图中找到的相对应极线。根据对极几何原理，若为精确匹配点对，则极线应该穿过左图中的匹配点，因此可以滤除那些距离极线较远的点，从而保留那些精确匹配的点对[10]。
2 结果与分析
本研究是基于研究采棉机器人视觉系统基金项目，为实现棉花的三维空间定位，在图像分割的基础上实现图像对的精确匹配。
本试验条件为CPU2.80G、内存2G。
FAST角点检测算法是在灰度图像中检测角点，有足够多的像素点的灰度值大于该点的灰度值或者小于该点的灰度值。由图4可以看出，利用FAST检测出的角点均在棉花的边缘或是棉花的形心位置，有很好的边缘特性，利于定位采摘点的位置信息。并且，FAST角点检测出1 339个特征点，而SURF角点检测算法只检测出415个特征点，且部份特征点分布于棉花目标外，不能用于棉花采摘点的定位（图5）。因此本研究采用FAST角点检测算法用于检测棉花图像对的特征点。
由于SURF方法具有良好的抗旋转性，而且SURF向量为64维，相比于SIFT（128维）向量具有更低的维数，具有更快的速度。SURF特征向量如图6所示。
基于上述检测出的特征点与特征向量，建立K-D树，并采用BBF方法搜索图像匹配的对，结果如图7所示。
从图7可以看出，195对匹配点对中仍然存在部分误匹配点对，采用RANSAC剔除误匹配点对，结果如图8所示。
采用RANSAC方法剔除误匹配点对后，采用极限约束准则进一步提高匹配精度，淘汰掉一些匹配精度不高的匹配的对，结果如图9所示。
在图像对匹配中，图像对往往伴随着旋转、缩放等各种复杂情况，在图9中分别就图像缩放、旋转30°、180°条件采用本研究方法进行匹配，仍然可以得到很精确的匹配的对，切特征点均分布在棉花的边缘与棉花的型心位置（图9b、c）。
为评价匹配效果，将本研究的匹配方法分别与SURF和SIFT方法进行比较[11-12]，其对比结果如表1所示。
参考文献：
[1]李玲玲，李翠华，曾晓明，等. 基于Harris-Affine和SIFT特征匹配的图像自动配准[J]. 华中科技大学学报：自然科学版，2008，36（8）：13-16.
[2]谢 凡，秦世引. 基于SIFT的单目移动机器人宽基线立体匹配[J]. 仪器仪表学报，2008，29（11）：2247-2252.