立体视觉——NCC视差匹配
深度信息可以通过计算1幅图像和其它图像的特征位置的像素差获得。视差图和深度图很像，因为视差大的像素离摄像机近，而视差小的像素离摄像机远。按以米为单位来计算摄像机距物体多远需要额外的计算。
根据Matlab教程，计算视差图的标准方法是用简单的块匹配（Block Matching）。我们选择右边图像中的1块小区域，并在左边图像中搜索匹配最近的像素区域。同理，当搜索右边图像时，我们从和左边图像的模板相同的坐标处开始，向左和向右搜索至最大距离。视差为右边图像的小区域和左边图像的最近匹配区域的中心像素的水平距离。
左视差图：
右视差图：
归一化相关性，normalization cross-correlation，因此简称NCC，下文中笔者将用NCC来代替这冗长的名称。
NCC，顾名思义，就是用于归一化待匹配目标之间的相关程度，注意这里比较的是原始像素。通过在待匹配像素位置p（px，py）构建3*3邻域匹配窗口，与目标像素位置p’(px+d,py）同样构建邻域匹配窗口的方式建立目标函数来对匹配窗口进行度量相关性，注意这里构建相关窗口的前提是两帧图像之间已经校正到水平位置，即光心处于同一水平线上，此时极线是水平的，否则匹配过程只能在倾斜的极线方向上完成，这将消耗更多的计算资源。
NCC计算公式如下图所示：
其中NCC(p,d) NCC(p,d)NCC(p,d)得到的值得范围将在[−1,1]之间 [-1,1]之间[−1,1]之间。
Wp为之前提到的匹配窗口。
1(x,y) 为原始图像的像素值。
I1(px,py) 为原始窗口内像素的均值。
I2(x+d,y)为原始图像在目标图像上对应点位置在x xx方向上偏移d dd后的像素值。
I2(px+d,py)为目标图像匹配窗口像素均值。
若NCC=−1，则表示两个匹配窗口完全不相关，相反，若NCC=1时，表示两个匹配窗口相关程度非常高。
采集图像：通过标定好的双目相机采集图像，当然也可以用两个单目相机来组合成双目相机。（标定方法下次再说）
极线校正：校正的目的是使两帧图像极线处于水平方向，或者说是使两帧图像的光心处于同一水平线上。通过校正极线可以方便后续的NCC操作。
2.1 由标定得到的内参中畸变信息中可以对图像去除畸变，在OpenCV中有函数对去畸变做了实现
2.2 通过校正函数校正以后得到相机的矫正变换R和新的投影矩阵P，接下来是要对左右视图进行去畸变，并得到重映射矩阵。这里，我们还是用OpenCV函数
2.2 根据上述得到的重映射参数map1,map2，我们需要进一步对原始图像进行重映射到新的平面中才能去除图像畸变，同样，实现方式仍是使用现有的OpenCV函数
2.3 通过上述两步操作，我们成功地对图像去除了畸变，并且校正了图像极线。注意，在立体校正阶段需要设置alpha = 0才能完成对图像的裁剪，否则会有黑边。
特征匹配：这里便是我们利用NCC做匹配的步骤啦，匹配方法如上所述，右视图中与左视图待测像素同一水平线上相关性最高的即为最优匹配。完成匹配后，我们需要记录其视差d，即待测像素水平方向xl与匹配像素水平方向xr之间的差值d = xr - xl，最终我们可以得到一个与原始图像尺寸相同的视差图D。
深度恢复：通过上述匹配结果得到的视差图D，我们可以很简单的利用相似三角形反推出以左视图为参考系的深度图。计算原理如下图所示：
如图，Tx为双目相机基线，f为相机焦距，这些可以通过相机标定步骤得到。而xr - xl就是视差d。通过公式 z = f * Tx / d可以很简单地得到以左视图为参考系的深度图了。
至此，我们便完成了双目立体匹配。倘若只是用于图像识别，那么到步骤3时已经可以结束了。
# -*- coding: utf-8 -*-
from PIL import Image
from pylab import *
import cv2
from numpy import *
from numpy.ma import array
from scipy.ndimage import filters
def plane_sweep_ncc(im_l,im_r,start,steps,wid):
""" 使用归一化的互相关计算视差图像 """
m,n = im_l.shape
# 保存不同求和值的数组
mean_l = zeros((m,n))
mean_r = zeros((m,n))
s = zeros((m,n))
s_l = zeros((m,n))
s_r = zeros((m,n))
# 保存深度平面的数组
dmaps = zeros((m,n,steps))
# 计算图像块的平均值
filters.uniform_filter(im_l,wid,mean_l)
filters.uniform_filter(im_r,wid,mean_r)
# 归一化图像
norm_l = im_l - mean_l
norm_r = im_r - mean_r
# 尝试不同的视差
for displ in range(steps):
# 将左边图像移动到右边，计算加和
filters.uniform_filter(np.roll(norm_l, -displ - start) * norm_r, wid, s) # 和归一化
filters.uniform_filter(np.roll(norm_l, -displ - start) * np.roll(norm_l, -displ - start), wid, s_l)
filters.uniform_filter(norm_r*norm_r,wid,s_r) # 和反归一化
# 保存 ncc 的分数
dmaps[:,:,displ] = s / sqrt(s_l * s_r)
# 为每个像素选取最佳深度
return np.argmax(dmaps, axis=2)
def plane_sweep_gauss(im_l,im_r,start,steps,wid):
""" 使用带有高斯加权周边的归一化互相关计算视差图像 """
m,n = im_l.shape
# 保存不同加和的数组
mean_l = zeros((m,n))
mean_r = zeros((m,n))
s = zeros((m,n))
s_l = zeros((m,n))
s_r = zeros((m,n))
# 保存深度平面的数组
dmaps = zeros((m,n,steps))
# 计算平均值
filters.gaussian_filter(im_l,wid,0,mean_l)
filters.gaussian_filter(im_r,wid,0,mean_r)
# 归一化图像
norm_l = im_l - mean_l
norm_r = im_r - mean_r
# 尝试不同的视差
for displ in range(steps):
# 将左边图像移动到右边，计算加和
filters.gaussian_filter(np.roll(norm_l, -displ - start) * norm_r, wid, 0, s) # 和归一化
filters.gaussian_filter(np.roll(norm_l, -displ - start) * np.roll(norm_l, -displ - start), wid, 0, s_l)
filters.gaussian_filter(norm_r*norm_r,wid,0,s_r) # 和反归一化
# 保存 ncc 的分数
dmaps[:,:,displ] = s / np.sqrt(s_l * s_r)
# 为每个像素选取最佳深度
return np.argmax(dmaps, axis=2)
im_l = array(Image.open(r'F:\Pictures\one/1.png').convert('L'), 'f')
im_r = array(Image.open(r'F:\Pictures\one/2.png').convert('L'),'f')
# 开始偏移，并设置步长
steps = 12
start = 4
# ncc 的宽度
wid = 9
res = plane_sweep_ncc(im_l,im_r,start,steps,wid)
import scipy.misc
scipy.misc.imsave('depth.png',res)
show()
实验过程
（1）实验原图：
运行结果:
窗口值为9：
窗口值为6：
窗口值为3：
（2）实验原图：
运行结果:
窗口值为9：
窗口值为6：
窗口值为3：
由上述对比试验可知，窗口值过小时，匹配代价区分度过低，在低纹理区域容易出现误匹配，匹配精度较低；随着窗口值增大，匹配区分度逐渐清晰，误匹配区域得到矫正，匹配精度随着窗口值增大而变高。但当窗口值过大时，在深度区域容易出现误匹配。因此窗口值的大小应适中，不宜过大也不宜过小。
遇到的问题遇到的问题：
运行NCC算法时运行时间较长，较长时间才可以运行结束出现运行结果
解决办法：
修改图片尺寸和窗口大小可以有效提高算法运行速度
作者：monetvan
