OpenCV Block Matching
#
OpenCV BM 算法
OpenCV 用于计算视差图(disparity map)的块匹配算法(OpenCV Block Matching algorithm)
是 Kurt Konolige 的小视觉系统算法的一种实现(Small Vision System algorithm).
OCV BM 算法计算非常快速, 每秒钟可以处理数张图像, 只是如果没有很好调整参数时效果较差.
可以处理得到视差值的类型为 16 位整数类型(默认, 即 CV_16S CV_16SC1),
最终要得到真实的视差值还需要转换为浮点类型(CV_32F CV_32FC1),
也可以直接处理生成浮点类型视差图(非原OpenCV库, 需要先修改算法实现才能正常使用非固定浮点类型
即 cv::Mat_<float>).
[1] [2]
OpenCV BM 算法计算视差图流程
立体匹配并行数量计算
所需内存计算
关于 COST
在立体匹配时计算, 用于 cv::validateDisparity()(左右视差检查),
在 disp12MaxDiff >= 0 时才计算和使用.
参考立体匹配和再滤波: COST 就是 最小 SAD.
参考:
– 左右视差检查参数
– disp12MaxDiff
– cv::validateDisparity()
OpenCV BM 使用的几个滤波
按处理流程顺序:
1. 预处理滤波: 亮度归一化和增加纹理: X-Sobel 或 Normalized Response:
– 预处理滤波和归一化图像参数
– 1 预处理滤波
2. 置信度滤波: 滤除低纹理:
– 置信度滤波
– 再滤波参数
– 立体匹配和再滤波
– 3 再滤波
3. 左右滤波: 一致性检查, 解决相关窗口跨越图像深度边界时导致匹配的二义性:
– 左右滤波
– 左右视差检查参数
– cv::validateDisparity()
4. 滤除散斑
– 滤除散斑参数
– 立体匹配和再滤波
– cv::filterSpeckles()
OpenCV BM 算法参数
See also OpenCV BM 算法分析
预处理滤波和归一化图像参数
预处理滤波类型
即 Pre-filter type.
作用:
OpenCV BM算法有两个预处理滤波选项: X-Sobel 和 Normalized Response.
X-Sobel算子(在原图像上通过进行 X 方向 Sobel算子运算以加强图像 X 方向纹理).
取值:
– 预处理滤波类型:
– 0: Normalized Response (cv::StereoBM::PREFILTER_NORMALIZED_RESPONSE)
TODO
– 1: X-Sobel (默认 cv::StereoBM::PREFILTER_XSOBEL)
– 示例使用 1: X-Sobel
– 算法实现参数名: pre_filter_type
参考:
– cv::StereoBM, enum of cv::StereoBM in opencv2/calib3d/calib3d.hpp:
enum {
PREFILTER_NORMALIZED_RESPONSE = 0,
PREFILTER_XSOBEL = 1,
};
预处理滤波窗口大小
即 Pre-filter size
作用: Normalized Response 预处理滤波时使用 (TODO)
取值:
– [5, 255] 一般应该在 5×5..21×21 之间 且 必须为奇数值
– 默认 9
– 示例使用 41
预处理滤波截断值
即 Pre-filter cap (capture?).
作用:
– 预处理的输出值仅保留 [-preFilterCapture, preFilterCapture] 范围内的值 ??
– 用于生成”X-Sobel值到归一化值的映射表”
– 当 preFilterCapture <= 31 并且 SAD 窗口大小 <= 21 才可以使用 SIMD128
取值:
– [1, 63]
– 默认 31
– 示例使用 31
参考:
– 1 预处理滤波
– 预处理滤波X-Sobel实现
– SAD 窗口大小
SAD 立体匹配参数
SAD 窗口大小
即 SAD window size / block size.
作用:
– 重要参数
– The linear size of the blocks compared by the algorithm
– SAD 窗口越大越平滑但是精度会降低(Larger block size implies smoother,
though less accurate disparity map)
– Smaller block size gives more detailed disparity map,
but there is higher chance for algorithm to find a wrong correspondence.
取值:
– [5, 255] 即一般应该在 5×5 至 21×21 之间的窗口
– 必须是奇数
(The size should be odd, as the block is centered at the current pixel)
– 默认 21
– 示例使用 9
最小视差值
即 min disparity.
确定匹配搜索从哪里开始, 默认为 0.
作用:
– 确定匹配搜索从哪里开始 TODO
– 计算左边图像向右偏移: int const lofs = max(nDisp - 1 + minDisp, 0);
– 右边图像向左或者不偏移: int const rofs = -std::min(nDisp - 1 + minDisp, 0);
(因为以左边图像为基础向右匹配, 所以右边图像向左或者不偏移)
– 计算无效视差值:
int const FILTERED = (minDisp - 1) << kDisparityShift16S;
取值:
– 参考计算视差中的检查视差和图像宽度的限制
– 默认 0.
– 示例使用 0
视差窗口
即 disparities number or numDisparities. 表示最大视差值与最小视差值之差.
作用:
– 重要参数
– 在该数值确定的视差范围内进行搜索
(The disparity search range.
For each pixel algorithm will find the best disparity from 0
(default minimum disparity) to numDisparities.
The search range can then be shifted by changing the minimum disparity.)
– NOTE 视差越大 距离越近!!
取值:
– 必须大于 0 并且是 16 的整数倍
– 默认 64
– 计算: ((width / 8) + 15) & (~0xfl);
– 示例使用 80 for 640, 128 for 1024, 160 for 1224
参考: 2 立体匹配
再滤波参数
低纹理区域的判断阈值
即 texture threshold.
作用:
– 保证有足够的纹理以克服噪声
– 如果纹理和小于这个阈值则视差无效:
如果当前 SAD 窗口内所有邻居像素点的 x-导数绝对值之和小于指定阈值,
则该窗口对应的像素点的视差值为 0
(That is, if the sum of absolute values(SAD) of x-derivatives computed over
SADWindowSize by SADWindowSize pixel neighborhood is smaller than the
parameter, no disparity is computed at the pixel). (minimum allowed!)
取值:
– 该参数不能为负值
– 默认 10
– 示例使用 20
视差唯一性百分比
即 uniqueness ratio.
作用:
– 重要参数
– 用于匹配之后的后过滤处理: 去除坏的匹配点, 预防虚匹配
– 视差窗口范围内最低代价是次低代价的 (1 + uniquenessRatio / 100) 倍时,
最低代价对应的视差值才是该像素点的视差, 否则该像素点的视差为 0
(the minimum margin in percents between the best (minimum) cost function
value and the second best value to accept the computed disparity,
that is, accept the computed disparity
d^ only if SAD(d) >= SAD(d^) x (1 + uniquenessRatio / 100)
for any d != d*+/-1 within the search range)
取值:
– 不能为负值
– 一般 5-15 左右的值比较合适
– 默认 15
– 示例使用 10
参考: 3 再滤波
滤除散斑参数
Over the correspondence window area.
检查视差连通区域变化度的窗口大小
即 speckle window size.
作用:
– 检查视差连通区域变化度的窗口大小值 <= 0 时取消 speckle 检查
– 匹配最后, 由于匹配窗口捕捉的是物体一侧的前景和另一侧的背景,
基于块匹配在物体边界附近会有一些问题, 这会导致同时产生大小视差的局部区域(散斑).
为了避免出现这种边界匹配 可以通过设置参数 speckleWindowSize 来在散斑窗口
(5×5 ~ 21×21) 上设置一个散斑探测器.
在散斑窗口内部 只有探测到的最大最小视差在 speckleRange 范围内的匹配才被接受.
(The maximum speckle size to consider it a speckle.
Larger blobs are not affected by the algorithm.)
取值:
– 默认 0
– 示例使用 100
– do cv::filterSpeckles only when:
if ((speckleRange >= 0) && (speckleWindowSize > 0))
参考: cv::filterSpeckles()
视差变化阈值
即 speckle range.
作用:
– 视差变化阈值: 当窗口内视差变化大于阈值时, 该窗口内的视差清零.
Maximum difference between neighbor disparity pixels to put them into the
same blob.
Note that since StereoBM, StereoSGBM and may be other algorithms return a
fixed-point disparity map,
where disparity values are multiplied by 16,
this scale factor should be taken into account when specifying this parameter
value.
取值:
– 默认: 0
– 示例使用 32
– Do cv::filterSpeckles only when:
if ((speckleRange >= 0) && (speckleWindowSize > 0))
参考: cv::filterSpeckles()
左右视差检查参数
即 left-right check, 参考 cv::validateDisparity
disp12MaxDiff
左视差图和右视差图之间的最大容许差异
作用:
– 超过该阈值的视差值将被清零.
– 注意在程序调试阶段最好保持该值为 -1, 以便查看不同视差窗口生成的视差效果:
– “BM SGBM: disp12MaxDiff 都要设置为 -1, 使左右视图视差检测功能失效,
才能保证顺利得到边界延拓后的视差图.
否则在程序运行过程中, 若增大 numDisparities 后又减少其值, 就会提示出错”
– 具体请参见 “使用 OpenGL 动态显示双目视觉三维重构效果示例”
– 默认为 -1 即不执行左右视差检查.
参考:
– cv::validateDisparity()
– 立体匹配和再滤波
– 滤波
– 左右滤波
OpenCV BM 算法分析
OpenCV BM对于处理非畸变的立体图像, 主要有以下 3 个步骤:
1. 预处理滤波: 使图像亮度归一化并加强图像纹理
2. 立体匹配: 沿着水平极线用 SAD 窗口进行匹配搜索
3. 再滤波: 去除坏的匹配点.
匹配之后, 如果左右视差检查使能了 disp12MaxDiff >= 0, 还有使用
cv::validateDisparity进行左右视差检查.
最后, 由于匹配窗口捕捉的是物体一侧的前景和另一侧的背景, 基于块匹配在物体边界附近会有一些问题.
这会导致同时产生大小视差的局部区域(散斑). 可以通过 filterSpeckles 滤除散斑.
1 预处理滤波
预处理滤波(Pre-filter), 左右两个矫正过的图像并行计算, 使图像亮度归一化并加强图像纹理.
- 在预处理滤波中 输入图像被归一化处理, 从而减少了亮度差异, 也增强了图像纹理. 算法:
- X-方向 Sobel运算, 可以加强 X 方向图像纹理, 同时归一化图像亮度
(计算图像亮度梯度的近似值, 然后归一化到 [0, 2ftzero], ftzero: 预处理滤波截断值). - “Normalized Response” TODO
- X-方向 Sobel运算, 可以加强 X 方向图像纹理, 同时归一化图像亮度
- 这个过程通过在整幅图像上移动窗口实现, 窗口大小 [5×5, 7×7 … 21×21].
- 最后得到两张滤波后图像, 然后用于下一步匹配
预处理滤波流程图:
预处理滤波X-Sobel实现
See also
struct PreFilterInvokerPreFilterInvoker::PreFilterInvoker()PreFilterInvoker::operator()PreFilterInvoker::xSobel()
2 立体匹配
即 Stereo correspondence.
立体匹配: 沿着水平极线用 SAD 窗口进行匹配搜索 多路并行计算
结果: 生成视差图.
对左图像的每个特征而言, 搜索右图像中对应行以找到最佳匹配.
校正之后, 每一行就是一条极线, 因此右图像上的匹配位置就一定会在左图像的相同行上
(即具有同样的 y 坐标).
如果特征有足够多的可检测纹理, 并且位于右相机视图内, 就可以找出该匹配位置 如图:
如果左特征像素位于 \( (x _ 0, y _ 0) \) 那么对于水平前向平行的相机排列,
它的匹配点(若有)就一定与 \(x _ 0\) 在同一行,
或者在 \(x _ 0\) 的左边 见图: 
立体匹配和再滤波
See also:
– 所需内存计算
– 立体匹配并行数量计算
3 再滤波
或后滤波即 Post-filters, knock out bad matches.
在立体匹配后开始后滤波成处理, 仅在视差唯一性百分比(uniqueness_ratio)大于 0 时才执行,
去除坏的匹配点, 预防虚匹配.
由于匹配值经常有一个特点 — 强烈的中央峰被副瓣包围 ??,
因此视差窗口范围内最低代价是次低代价的 (1 + uniquenessRatio / 100) 倍时,
最低代价对应的视差值才是该像素点的视差, 否则该像素点的视差为 0. 即 SAD 的阈值为:
int const thresh = minsad + (minsad * uniquenessRatio / 100);.
因此检查 idx in [0, nDisp) 共 nDisp 个 SADs,
如果idx 不在 [minDispIdx – 1, minDispIdx + 1] 范围内,
并且SAD 值小于或等于 thresh 则视差无效:
for (d = 0; d < nDisp; ++d) {
if (((d < minDispIdx - 1) || (d > minDispIdx + 1)) && (sad[d] <= thresh)) {
break;
}
}
if (d < nDisp) {
dptr[y * dstep] = FILTERED;
continue;
}
滤除散斑
最后, 由于匹配窗口捕捉的是物体一侧的前景和另一侧的背景, 基于块匹配在物体边界附近会有一些问题.
这会导致同时产生大小视差的局部区域(散斑).
为了避免出现这种边界匹配, 可以通过设置参数 speckleWindowSize 来在散斑窗口 (5×5 ~ 21×21)
上设置一个散斑探测器来滤除小的噪声斑点(散斑).
(Filters off small noise blobs (speckles) in the disparity map).
参考:
– 检查视差连通区域变化度的窗口大小
– 视差变化阈值
– 立体匹配和再滤波
实现代码
imgproc
TODO
cv::filterSpeckles()分析cv::validateDisparity()分析
滤波
Stereo processing will generally contain incorrect matches.
There are two major sources for these errors:
lack of sufficient image texture for a good match(没有足够的纹理),
and ambiguity in matching when the correlation window straddles a depth
boundary in the image(相关窗口跨越图像深度边界时导致匹配的二义性).
The SVS stereo processing has two filters to identify these mismatches:
a confidence measure for textureless areas,
and a left/right check for depth boundaries.
Areas that are filtered appear black in the displayed disparity image.
To distinguish them from valid disparity values,
they have the special values 0xffff (confidence rejection)
and 0xfffe (left/right rejection).
Dense range images usually contain false matches that must be filtered,
although this is less of a problem with multiple-image methods.
Table 2 lists some of the post-filters that have been discussed in
the literature.
The correlation surface shape can be related to the uncertainty in the match.
An interest operator gives high confidence to areas that are textured in
intensity,
since flat areas(平坦的区域) are subject to ambiguous matches.
The left/right check looks for consistency in matching from a fixed left image
region to a set of right image regions,
and back again from the matched right region to a set of left regions.
It is particularly useful at range discontinuities(不连续),
where directional matching(定向匹配) will yield different results.
Table 2
Range filtering operations
| Post-filter Method | Since |
|---|---|
| Correlation surface: peak width, peak height, number of peaks | Matthies 1993, Nishihara 1984 |
| Mode filter | |
| Left/Right check | Fua 1993, Bolles and Woodfill 1993 |
| Interest Operator | Moravec 1984 |
| Interpolation | Nishihara 1984 |
置信度滤波
Confidence Filter
The confidence filter eliminates stereo matches that have a low probability of
success because of lack of image texture.
There is a threshold, the confidence threshold, that acts as a cutoff.
Weak textures give a confidence measure below the threshold,
and are eliminated by the filter.
A good value can be found by pointing the stereo cameras at a textureless
surface such as a blank wall, and starting the stereo process.
There will be a lot of noise in the disparity display if the confidence
threshold is set to 0.
Adjust the threshold until the noise just disappears,
and is replaced by a black area.
The computational cost of the confidence filter is negligible(可以忽略不计的),
and it is usually active in a stereo application.
See also 低纹理区域的判断阈值
左右滤波
Left/Right Filter
Each stereo camera has a slightly different view of the scene,
and at the boundaries of an object there will be an area that can be viewed
by one camera but not the other.
Such occluded(闭塞) areas cause problems for stereo matches.
Fortunately, they can be detected by a consistency check(一致性检查) in which
matching is done first by using the left image as a fixed base,
and then repeating the match using the right image as the base.
Disparity values for the same point that are not the same fail the
left/right check.
Typically, this will occur near the boundaries of objects.
A third option is to perform the check,
but instead of discarding disparity values that are inconsistent,
use the one that is smaller (further away).
This option can fill in the areas around object borders in a reasonable way.
It is not currently available under MMX processing.
The left/right check adds about 20% to the computational cost of the stereo
process, but is usually worth the effort.
See also 左右视差检查参数
小视觉系统
Small Vision System
多尺度视差
Multiscale Disparity
Multiscale processing can increase the amount of information available in the
disparity image, at a nominal cost in processing time.
In multiscale processing,
the disparity calculation is carried out at the original resolution,
and also on images reduced by 1/2.
The extra disparity information is used to fill in dropouts in the original
disparity calculation (Figure 3-8 in Section 2.4.8):
参考:
– Small Vision System User’s manual
– imgproc
– imgproc: StereoImgProc::mergeDispartyMaps()
参考
opencv branch master 99a9c10b577bc340c323251185698bd87cea05a2 Thu Dec 28 01:26:14 2017 +0000opencv branch master 70bbf17b133496bd7d54d034b0f94bd869e0e810 tag 3.2.0- 1 OpenCV Block Matching OCV-BM 2015
- 2 OpenCV Block Matching OCV-BM with post-processing OCV-BM-post 2013
- Small Vision System User’s manual
- Small Vision System: Hardware and Implementation