块匹配算法求助

图象的如下：基于灰度相关，基于特征，基于关系三个层次，基于灰度相关团迟的图像匹配较常用，基于特征团或手匹配效果最好，但是算法复杂，耗时长，难以实现实时性，基于关系塌嫌的匹配算法建立语义的网络，是人工智能技术在图像处理中的应用，目前为止无突破性的进展。 其他的是数据库?

最近在做双目视差估计算法，在OpenCV里有一些算法，其中半全局块匹配（Semi-Global Block Matching，SGBM）算法具有视差效果好速度快的特点，因此常常被广泛应用。本文主要讨论的就是SGBM算法。OpenCV的SGBM算法主要参考了《Stereo Processing by Semiglobal Matching and Mutual Information》这篇论文。

原论文使用的方法是利用互信息熵，而OpenCV使用的是Birchfield和Tomasi的方法（参照《Depth Discontinuities by Pixel-to-Pixel Stereo》）。这里我们分别介绍一下。

所谓的熵，是用来表示随机变量的不确定性，熵的值越大，信息的不确定性也越大。熵H和互信息MI的定义分别如下：

其中，P I 代表某个点i的概率分布，也就是灰度直方图为i的点出现的概率；对应地，P I 1 ,I 2 就是两个图对应点i 1 和i 2 的联合概率分布，也就是：

Kim等人将上式做了一个改进：利用泰勒展开把H I 1 ,I 2 的计算转化为求和问题（参见论文《Visual Correspondence Using Energy Minimization and Mutual Information》）。

其中圈中带叉表示卷积运算，g(i,k)为高斯卷积核。

相应地，巧正边缘熵以及边缘概率的计算如下：

这样的话，互信息的定义为：

MI匹配代价C MI 为：

其中 q 是点 p 在视差为d的情况下的对应校正点。

原作者使用分层互信息（HMI）进行计算，每一层尺寸减少一半。单次计算的时间复杂度是O(WHD)，即width×height×disparity range，所以上次迭代将会是当前迭代速度的1/8。

这里1/16 3 要乘3的原因是小尺寸的随机视差图不靠谱，需要迭代3次。我们可以看到，相比于后文的BT方法仅仅慢了14%

对于一个匹配序列M，其代价函数γ(M)表示匹配结果 不 准确的程度，其值越小越好。

其中，κ occ 表示未匹配的惩罚项(constant occlusion penalty)，κ r 表示匹配的奖励项，N occ 和N r 分别表示未匹配和匹配的点数。

我们为视差设置一孝橘悔个能量函数E(D)

其中P 1 和P 2 分别表示视差差值为1和视差差值大于1的惩罚系数，一般P 1 <P 2 。添加两个正则化项一是为了保持视差图平滑，二是为了保持边缘。我们伍缓要做的是找到D使得能量函数E(D)最小，但是不幸的是，在二维图像的这个问题是一个NP-完全问题。为了解决这个问题，原文选择沿着一圈8个或者16个方向进行优化。

选取使代价聚合最小的视差值min d S[e mb ( q ,d),d]即可。

我们看一下stereoSGBM类的参数。

简单地试了一下：

function J=matgraf(W)

n=size(W,1)

J=zeros(n,n)

while sum(sum(W))~=0

a=find(W~=0)

t1=mod(a(1),n)

if t1==0

t1=n

end

if a(1)/n>floor(a(1)/n)

t2=floor(a(1)/n)+1

else

t2=floor(a(1)/n)

end

J(t1,t2)=1,J(t2,t1)=1

W(t1,:)=0W(t2,:)=0

W(:,t1)=0W(:,t2)=0

end

J

---