双向立体匹配（通用6篇）
双向立体匹配 篇1
立体匹配是计算机视觉领域的一个技术难题，其实质是在一定匹配约束条件下寻找同一目标图像在不同拍摄角度上相应像素点间的一一对应关系。从研究的现状来看，学者们提出了许多种立体匹配算法，根据匹配约束条件的差异性，可将立体匹配算法[1,2]分为两种，一种针对像素小邻域进行局部约束匹配的方法[3,4,5]，其特点是运行速度快、精度较高，但在遮挡区域的匹配效果较差;针对这一问题，一些学者提出了另一种全局匹配算法，即通过对整幅图像进行全局约束，相较而言，此类算法能够实现较低的误匹配率，但计算的复杂度较高。全局匹配算法主要包括:置信度传播(Belief Propagation,BP)[6,7]、动态规划(Dynamic Programming,DP)[8,9,10,11]、图切割(Graph Cuts,GC)[12]等。此类匹配算法由于计算复杂度比较高，导致算法无法达到实时性的要求。因此在实时性要求较高的情况下，一般会选用DP算法，DP是全局算法中一种较典型的优化方法，它避免了非确定多项式(Non-Deterministic Polynomial,NP)问题，同时具有匹配效果良好、运行效率较高的特点。
但是，大部分DP算法有一个较为明显的不足，即视差图容易出现横向的“条纹”瑕疵，究其原因是缺少行、列方向上连续视差结果的融合。针对上述问题，诸多学者做了一些有建设性的研究。Birchfield等人[13]提出将竖直方向匹配度较高的区域视差拓展到低可信度区域的做法，该算法虽然实现了较快的运行速率，但扫描线间的视差结果较差，另外在算法优化部分可能会造成错误视差扩散到全局的不利影响;Gong and Yang[14]则提出了一种提高二通道DP算法可靠性的做法，即通过在垂直和水平两个方向上分别进行动态规划计算搜索路径，该算法确保了较高的匹配精度，但要借助编程图形显示卡来获取视差图的实时效果;另外Leung等人[15]提出了一种迭代动态规划(Iterative Dynamic Programming,IDP)算法，其通过多次迭代算法，来增强视差图的连续性，而导致的较长运行时间不利于实验操作。
鉴于此，本文提出一种基于改进双向动态规划的视差图获取算法，以修正后的ASCF为代价函数，并构建新的全局能量函数，通过改进双向动态规划寻径来得到最终的稠密视差图。经验证，所提算法的匹配效果良好，并获得了稠密视差图。
1 新型视差图获取算法的研究
DP算法的实质是将对应点的匹配问题转化为寻找某一能量函数的全局最优解，而构造出合适的像素间匹配的代价函数是构建全局能量函数的重要前提，所构建的代价函数优劣与否直接影响着立体匹配算法的运行速率和精确度，其中代价函数主要包含有差值绝对值和函数(Sum of Absolute Differences,SAD)、差值绝对值(Absolute Difference,AD)、差值平方(Squared Differences,SD)等，此类代价函数在算法构造上相对简单、易于操作，但由于忽视了不同区域间跃变的影响，会产生较高的误匹配率。为了克服在交叉深度不连续区域的匹配问题，学者们在不连续区域为每一个像素选择自适应匹配窗口，其中Yoon等人[16]将几何数学的邻近性和像素色度空间融入到权值计算当中，此举有效地抑制了立体匹配中的不确定性，但在构建ASCF的过程中，导致视差非连续区域的误匹配率有所增加。
针对这一问题，提出了一种新型视差图获取算法即改进动态规划双向约束算法，即采用修正后的ASCF，进一步增强原始代价值在视差非连续区域的比重，以确保这一区域的误匹配率有所降低，从而改变构建ASCF的传统方法所导致总体误匹配率高的状况，并参照经典Potts模型[17]构建全局能量函数，考虑到相邻像素视差值保持的一致性准则，增加了视差平滑约束项的比重，提高所构建的全局能量函数的精确度。由于传统的DP算法在求取全局能量函数最优解时存在一个很大的局限性，即易出现“条纹”瑕疵的现象。为了克服这一问题，此算法提出采用扫描线行列双向动态规划来寻找最小匹配代价路径，并对初始视差图的数据项和平滑约束项分别制定了相应的奖励策略。最后，针对出现的错误孤立视差点，通过简单的滤波方法和遵循相关的3个准则予以消除。此算法流程如图1所示。
1.1 修正后的ASCF
Yoon等人[16]基于空间几何距离的相关性和像素间颜色相似性对ASCF进行了详细分析，即将几何数学的邻近性和像素色度空间融入到权值计算当中，其计算公式为
式中:γc和γp分别为控制权值的参数;Δgpq为对应像素的空间几何距离的相关性，即窗口中心像素p和匹配窗口中像素q之间空间坐标的欧几里德距离。
许多学者提出了不同的Δcpq构造方法，其中Salmen等人[18]根据像素点RGB值的内在联系，将Δcpq设定为窗口中心像素p与匹配窗口像素q的RGB值的加权欧几里德距离。由于获得该参数需要通过实验反复测试，以致代价函数的精确度相对较差，图像对的误匹配率也不低。Yang等人[19]对两像素点彩色差值求平均，尽管该构造方法在一定程度上减轻了算法的运算量，但由于忽略了像素点间彩色像素值的相关性，导致代价函数的自适应约束能力减弱，视差保持特性有所降低。
本算法仍采用将图像像素点的彩色像素值转化为CIELab值，Δcpq为窗口中心像素p和像素q的CIELab值的欧几里德距离。另外，对应像素为，待匹配像素为p，相应的代价函数的计算公式为
式中:为目标图像窗口的代价权值;w(p,q)为参考图像窗口的代价权值;为两个匹配窗口视差为d的对应像素的原始代价函数，截断绝对值的计算式如下
式中:Ic为RGB颜色空间的亮度值;Ti为截断门限值，即当亮度值之差大于门限值时取值为门限值。为了减少视差非连续区域的“条纹”瑕疵和错误匹配点，该算法对式(3)做了以下改进，即增加原始代价值在这区域的比重，新的原始代价函数的计算公式为
式中:Ti为截断门限值;Td为视差非连续区域的判断门限，当对应像素的彩色像素值差值的绝对值之和大于或等于在非连续区域的截断门限值时，原始代价值取为截断门限值，反之，取值为差值的绝对值与截断门限值之和中的最小值。
1.2 构建新的全局能量函数
本文构建的全局能量函数仍然只包含平滑项和数据项，其计算表达式如下
式中:为数据项，该代价函数采用的是式(2)中的ASCF，选取最小的视差值为其代价值。其中V(dp,dq)为视差平滑约束项，用来确保相邻像素视差值的一致性，该算法构建新的全局能量函数的思路是在参照经典Potts模型[17]，即
式中:ρI(ΔI)为相邻像素p与q之间的视差值。
梯度ΔI的函数ρI(ΔI)表达式为
式中:s为惩罚项;T为阈值;P是用来增大梯度处的惩罚项。
在构建的新的全局能量函数中，针对平滑约束项作了以下修正
式中:p1为小于p的常参数。
1.3 改进双向动态规划寻径
由式(5)构建的新的全局能量函数可知，立体匹配问题转化为求解一个视差分配d*，即使能量函数E(d)的取值最小
d*=arg min E(d)(9)
求解式(9)所述的能量最小化问题，传统的DP算法忽略了核线间的影响，致使核线与核线间的约束不够，即只是进行单一的行方向上的DP运算，如图1所示为在行方向上进行DP求解示意图，其中图2a是以x,y分别为横、纵坐标，视差搜索范围为d的视差空间图像(DSI)，图2b为只在行方向DP求解的示意图，其目的是为了搜索得到一条从左至右的最小代价路径，而每条路径的长度[20]为。
显然，这种缺少行、列方向上连续视差结果融合的DP算法不能保证全局最优，为了增强纵向像素间视差的约束项，以确保视差图横向条纹“瑕疵”的减少，故提出基于行、列双向的动态规划算法，具体过程如图3所示。
本算法提出了一种由行匹配初试结果来确定相应的奖励策略，即通过减小d*所对应代价函数的比重，以提高其在列匹配中被选中的可能性，初始匹配结果依靠第一次行DP求解得到，同时需在确定的窗口区间内，对数据项制定了合理的奖励策略:情况1，若列方向初始视差梯度变化出现明显错误的视差值点时，其用原来的代价值来赋值;情况2，若在列方向初始视差梯度未出现异常的情况下，而在行动态规划中能够得到匹配的视差值点，那么其值应该赋予较大的奖励值;情况3，其他视差值点则使用较小的奖励值。其表达式为
式中:Ti为截断门限值，如式(4)所述;r一般取相对较小的正数，当r取值过小时，奖励值过小，会造成行方向上的DP效果不明显;当r取值过大时，会使得列方向上的视差值点被选中的概率过大，导致列方向上的DP失去了意义。经过多次实验测试得知，r取值为7时，所得匹配结果较为理想。另外，能量函数的数据项的计算方法与上述平滑项一致，这里就不再累述。
1.4 去除孤立的错误视差点
针对所获取视差图中出现的一些较为明显的噪声点，该算法采用易于操作的滤波方法来去掉孤立点。一般遵循以下3个可靠性准则:1)若该像素点上下邻域像素的视差值相等，则赋予该点视差值与上下邻域点一致;2)若该像素点左右邻域像素的视差值相等，则赋予该点视差值与左右邻域点一致;3)若该像素点周围邻域点的视差值都不相等，则赋予该点视差值为其邻域所有点的视差值均值。
2 实验结果
本算法的实验平台和参考图像来自于Middlebury大学数据库，对其中的Cones,Venus,Tsukuba,Teddy这4幅图像进行了测试，实验中的各个参数k，γc，γp,Ti,Td,T,p,r,s分别取值1,5,19,25,30,5,3,10,3。实验结果如图4所示。此算法以修正后的ASCF为代价函数，并构建新的全局能量函数，通过改进双向动态规划寻径来得到最终的稠密视差图，分别与以ASCF作为代价函数、基于行列双向动态规划(DoubleDP)算法和以SAD作为代价函数的DP算法所获取视差图进行比较。实验视差图在所有区域(All)、非遮挡区域(Non_occ)、视差非连续区域(disc)的错误率做了记录，实验结果如表1所示。从表中分析可知，在优化策略一致的情况下，相较于SAD，采用ASCF来获取视差图误匹配率要低很多，而此算法相对于其他3种算法，误匹配率最低，“条纹”瑕疵方面最少，所获得的视差图效果最好。
%
3 小结
提出一种基于改进双向动态规划的视差图获取算法，以修正后的ASCF为代价函数，并构建新的全局能量函数，通过改进双向动态规划寻径来得到最终的稠密视差图。实验结果表明，该算法能够取得较为理想的效果，与其他3种DP算法相比明显降低了误匹配率，减少了图像中的“条纹”瑕疵。
虽然该算法在降低误匹配率和减少“条纹”瑕疵方面有显著的改善效果，但由于需要计算每个像素在确定窗口的自适应代价值，以致执行时间较长。故今后将使用GPU[21]和多线程[22]的处理方式，以便大幅度地提高算法运行速度，满足实际应用的要求。
摘要：提出一种基于改进双向动态规划的立体图像匹配算法,选用修正后的自适应加权代价函数(Adaptive Support Weight Cost Function,ASCF),然后构建新的全局能量函数,并通过改进双向动态规划来寻径,最后采用简单的滤波方法和遵循3个可靠性准则去除孤立的错误视差点,以获得稠密视差图。实验结果表明,该算法在降低误匹配率和减少“条纹”瑕疵方面有显著的改善效果。
关键词：视差图,动态规划,立体匹配,自适应加权代价函数
双向立体匹配 篇2
一种新的信号采集技术压缩感知(Compressed Sensing, CS)[1],因其高效的采集效率逐渐吸引人们的学习研究兴趣。 它采用边采集边压缩的模式,在数据采集过程中就进行适当的压缩,这样能保证信号采样速度低于奈奎斯特采样速率, 减少不必要的资源浪费[2,3]。CS理论主要内容是可压缩信号的少量线性投影包含了原始信号的主要信息,利用全局的线性测量可以精确重构出原信号[4]。假设一个长度为N的一维信号x ∈ RN,x中非零原始个数K≪ N ,或者在某个正交基 ψ 稀疏表示 θ 中有K个非零值,x = ψθ ,CS理论框架下,信号测量过程表示为
式中:y是长度为M的观测信号;Φ =[Φ1,Φ2,...,ΦN] 是测量矩阵,大小为M×N;x为K阶稀疏信号,长度为N,K<M<N。这个过程相当于把原始信号x投影到 [Φ1,Φ2,...,ΦN] 张成的空间上,信号从N维降到M维。压缩感知中重构算法是核心内容,是从测量矩阵 Φ 和观测信号y中恢复原始稀疏信号x。 从测量矩阵和原始信号维数可以看出式(1)是欠定的,求解原始信号是一个病态问题。但是当原信号只有有限的非零元素时,可以精确求解x 。Candes和Donoho指出当测量矩阵和稀疏信号满足一定条件可以求助于非线性凸优化方法, 如基追踪(BP)进行求解。但是BP算法复杂度O(M2N3/2) 太高,极大影响了它的实际应用。贪婪算法因为结构简单,运行速度快吸引了人们的广泛关注。带有回溯思想的贪婪算法因其重构精度较高备受人们关注。根据前向原子选择和后向原子删除步长,算法可分为步长为恒定值的算法和步长可变的算法。步长恒定算法包括子空间追踪算法(Subspace Pursuit,SP)[5]前向步长每次跟新K,后向删除步长也为K;压缩采样匹配追踪算法(Comprssive Sampling Matching Pursuit, Co Sa MP)[6]前向步长每次跟新2K,后向删减步长也为2K;FBP[7]算法每次迭代前向跟新步长为 α ,后向删减步长为 β ,其中 α > β 。步长变化算法包括:自适应稀疏度匹配追踪算法 (Adaptive Sparse Matching Pursuit,ASMP)[8]前向步长根据信号相关阈值得出,不是一个固定值,后向删减部分和SP类似, 保留当前估计信号幅值最大K的索引;自适应阈值回溯正交匹配追 踪算法(Adaptive Threshold Backtracking OMP,ATBOMP)[9]前向步长和信号相关,通过相关性求出阈值,再根据阈值选出原子,步长是变化的,后向删减步长是通过正则化完成的,步长也是变化的。
文献[7]提出了前向后向追踪算法(Forward-backward Pursuit),首先算法不需要稀疏度条件,其次算法重构精度相对较高。大部分情况,原信号的稀疏度是未知的,因此FBP相对于OMP[10,11],SP算法占有很大优势,其次FBP算法带有回溯机制,可以在迭代过程中自主纠错。虽然FBP算法相对于经典的几种算法占据优势,但是也存在缺点,首先是算法的时间复杂度,因为前向和后向步长是固定值,没有考虑迭代过程中信号的变化,所以执行效率比较低;其次算法重构精度还是有待进一步提高。本文提出双向阈值匹配追踪算法 (OTMP)。实验证明,OTMP在一定条件下,重构精度和时间复杂度均优于FBP。
1 FBP
首先简单说明本文涉及的符号。 supp(x) 表示向量x中非零元素的位置。K表示稀疏度。 ΦT表示 Φ 的转置,T0定义为初始的支撑集,r0表示初始的残差,Tl表示第l次迭代得出的支撑集,|Tl|表示Tl中元素个数。 rl表示第l次迭代得出的信号残差,xTl表示x对应Tl位置上的元素集合。 δK+ 1为K+ 1阶RIP常数,hl= ΦTrl- 1表示第l次迭代的代理信号,hl(i )=< Φei,rl- 1> 表示代理信号中的元素, 其中 < ∙ > 表示内积运算,ei为单位矩阵的第i列。
FBP算法每次迭代过程有两个核心过程,在原子添加步骤,首先计算当前迭代过程的代理信号hl= ΦTrl- 1,然后选出代理信号中最大 α 个值对应的索引加入到支撑集中;在原子删减步骤,首先把观测信号y正交投影到已选支撑集张成的空间上得到投影系数w ,接着删减w中 β 个最小值对应的索引。最后再次把观测信号正交投影到新的支撑集张的空间上,并求出信号残差。因为 α > β ,所以每次迭代的支撑集Tl原子个数不断增加。当信号稀疏度相对较小时,信号残差随着迭代过程不断减小,直到满足算法终止条件;当信号稀 疏度相对 较大时 ,算法通过|Tl|≥lmax终止条件退出迭代。算法1给出FBP的伪代码。
算法1:FBP算法
输入:测量矩阵 Φ ,测量向量y 。
设置:前向步长 α ,后向步长 β ,最大迭代次数lmax,算法终止阈值ε。
初始化:
迭代:k = k + 1。
前向更新
后向更新
投影
如果,迭代终止,否则继续迭代。
迭代终止后令,输出
文献[7]指出,当稀疏信号中的非零元素不为一个常数值随机信号(Constant Amplitude Random Signal,CARS)时,FBP重构性能高于OMP,SP,BP算法。同时当稀疏信号非零值取值范围增大时,FBP重构精度相对BP将更加精确。文献还提出如果减小 α,β 的取值,将会减小算法运行时间,但是通过实验结果可以发现时间复杂度降低是用信号重构精度降低为代价换来的。
2OTMP算法
FBP每次迭代选取原子的数量为一个固定的常数,而不考虑信号的性质(准确为残差信号性质),其次在后向更新过程,FBP每次迭代删减支撑集数量也为一个固定的常数,同样没有考虑迭代过程中信号的变化。FBP执行效率比较低;其次算法重构精度还是有待进一步提高。鉴于FBP缺点,本文提出OTMP。
2.1OTMP算法介绍
OTMP在支撑集选取过程充分考虑残差信号的特点选取满足条件的原子,随后把选出的原子加入到候选支撑集中。 在原子筛选过程,首先计算测量向量y在候选支撑集张成空间上的正交投影,然后在所有投影系数中找出当前迭代新添加支撑集上的投影系数,并求和筛选阈值 σ2,最后根据所求阈值剔除可能错误的原子。
算法2 OTMP算法
输入:测量矩阵 Φ ,测量向量y ,最大迭代次数lmax,迭代终止阈值ε;
初始化 :迭代次数l= 0 ,残差r0= y ,估计支撑 集,原信号非零值估计
循环:令l=l+1,执行步骤1)~2)直到满足迭代终止条件。
1)支撑集选取:计算相关值,选定索引集w ,使,计算支撑集选取阈值,选择Tf使, 令,更新,合并支撑 集, 最后利用 最小二乘 法求
支撑集筛选:当l= 1 ,计算删减阈值,在中筛选出可能错误的集合Tb,满足;当l> 1 ,计算删减阈值,在中筛选出可能错误的集合Tb,满足
2)支撑集更 新 :第l次迭代选 出的支撑 集。 最后利用 最小二乘 法求并计算
3)迭代终止条件:
停止循环,令原信号估计,输出
2.2OTMP算法分析
2.2.1预备知识
1)限制等距性质(RIP)[5]定义
如果矩阵 Φ ∈ RM×N满足参数为(K,δ )的有限等距性质,K M ,0 ≤ δ< 1 。对于任意的K阶稀疏信号x ∈RN有:
2)引理
引理1[12]对于任意的两个正整数m≤ n ,有 δm≤ δn。
引理2[13]设
2.2.2σ1阈值
当l=1,贪婪算法大部分是通过代理信号的幅值选择原子。假设矩阵 Φ ∈ RM×N满足参数为(K,δ )的有限等距性质,根据引理2有:
同理当l> 1
在没有噪声前提下,如果RIP常数满足那么OMP可以精确重构出原始稀疏信号。同时存在测量矩阵RIP常数满足时,不能保证OMP精确重构[14]。因此,的界相对比较宽松,相对于测量矩阵容易满足,。通过上面推到可以发现,如果根据上面推导出的阈值进行支撑集选取,那么选出的代理信号幅值会比真实的代理信号大。原因是阈值推导过程进行了一系列的放缩。
同时 Φ 进过归一 化处理 ,因此,所以把式(2)、式(3)式中的分别换为。最后求出 σ1。
2.3.3支撑集筛选原理
由于测量矩阵不是完全正交,因此通过支撑集选取过程得出候选原子并非一定完全正确。OTMP通过当前迭代产生的或者进行原子筛选,从物理意义上可理解为当前迭代选出原子的重构水平。如果本次迭代之前产生的正交投影系数幅值小于当前迭代重构水平(筛选阈值 σ2需要当前重构水平乘以 μ ),那么可以认为之前选择的原子是错误的。通过这个原理可以剔除部分错误原子。随着迭代过程,原子不断被选入支撑集,当残差rl充分小或者迭代达最大次数lmax,算法终止,输出估计信号。
3实验
本文基于MATLAB仿真平台,对一维信号和二维信号都进行了相关实验。在一维信号部分,选择了三种不同类型的稀疏信号分别为高斯信号,“0-1”信号和均匀分布信号。二维信号则是标准的256 × 256的Lena测试图像。测量矩阵 Φ 的元素服从均值为0,方差为1 N的高斯分布。
3.1一维信号仿真实验
测量次数M=128,信号长度N=256。稀疏度K取值应该满足K≤ M/2 。OMP和OTMP迭代停止阈值相同,均取ε = 10-6,OTMP的最大迭代次数lmax= M ,δ'= 0.1(δ'是 δK+ 1所求值放缩后的取值,这里不表示RIP常数),μ = 0.18 。BP算法重构是通过cvx工具箱实现的。FBP算法给前长步分别为 α = 30 、20、2与之对应的后退步长 β = 29 ,19,1。停止阈值 ε = 10-6,最大迭代 次数lmax= M/2 。 重构成功 条件 :,重建误差用平均归一化最小均方误差(Average Normalized Mean-Squared-Error,ANMSE)来表示均方误差,其中500表示独立的500次实验。
图1表示不同稀疏度条件下,各种算法对高斯信号重构效果。图1的第2幅曲线表示重构百分比和稀疏度之间关系,它可以衡量算法的稳定性。稀疏度较小时,所有算法都能保证100%重构出原信号。随着稀疏度不断增大,部分算法开始出现重构失败情况,而出现失败的临界点对算法评价具有重要意义。从曲线不难看出OMP算法在K= 30之前就出现失败情况(为了突出重点,截去原曲线的前面部分内容),当K≥ 35 ,BP开始出现重构失败情况;当K≥ 43 ,FBP (2,1)开始出现重构失败;K 45 ,FBP(20,19)和FBP(30, 29)也出现失败情况。但是对于OTMP,只有当K≥ 56才出现重构失败情况,而且当K= 61时其他算法重构概率几乎都降到0,OTMP却依然保持96%左右的水平。图1第3幅图表示重构的均方误差,它可以衡量算法重构的精确性,从图中可以明显看出OTMP重构的均方误差低于其他任何一种算法,而且在整个稀疏度区间都保持较低的值。最后分析图1的第1幅图,它表示重构时间和稀疏度之间的关系。OTMP算法在稀疏度1~51区间保持较低的运行时间,略高于OMP,SP,从K= 51开始,随着稀疏度增加算法运行时间增长很快,当K= 61,运行时间已经超过FBP(2,1)情况。但是从另一方面来看,如果只关心开始出现重构失败的临界点之前所有稀疏度对应的重构性能,OTMP时间复杂度相对于FBP还是较低的。
图2表示不同稀疏度条件下,各种算法对“0-1”信号重构效果。图2中间曲线可以看出,稀疏度K取26~28左右,FBP出现重构失败现象,SP在K≥ 29出现失败,而OTMP重构100%重构一直保持到K= 36左右,这和BP算法十分相近。 图2右边曲线表示重构的均方误差,OTMP重构误差仅次于BP算法,明显优于其他所有算法。最后在分析算法的时间复杂度,和高斯信号结果相似,在稀疏度相对较小时,OTMP保持较低的重构时间,与SP,OMP相当。但是当K= 35时,随着稀疏继续增大,OTMP运行时间增长十分迅速,到K= 40时,重构时间已经超过所有算法(不考虑BP时间)。同样, 如果只关心开始出现重构失败的临界点之前所有稀疏度对应的重构性能,OTMP重构时间还是比较低的。最后是图3的均匀信号重构情况,性能分析与高斯信号相似,这里不再赘述。
3.2二维图像信号仿真实验
为了衡量 算法对图 像信号重 构性能 ,选择标准 的256 × 256 Lena测试图像。首先对图像信号进行小波变换,选择sym6小波基。保留小波变换后系数矩阵每列最大的q个小波系数 ,其余置零 。 计算 :。算法参数设置与一维信号相同。
图4和表1反映了q= 45条件下,几种算法重构结果。重构的精度上OTMP的PSNR为34.4 d B,在其他所有算法中最大,即重构最精确;重构时间上OTMP的TIME是3.1 s,在其他所有算法中最小,即重构最快。二维图像经过二维小波变换,得出一系列小波系数,然后取出每列中最大的q个系数,其余置零,这样一方面可以节约重构时间,另一方面可以降低小的小波系数对重构的影响,即可提高重构精度,经过这样处理,图像信号每列的小波系数变为严格,且稀疏度已知的一维信号。对于一维信号,仿真结果显示,信号稀疏度在相对较小时,OTMP重构的均方误差很小,同时重构时间很短,接近SP,OMP。在二维实验中q取45对应OTMP稀疏较小,所以不仅能精确重构而且重构所需时间很短。 因此OTMP算法在二维图像信号重构上性能相比其他算法更加优越。
4结论
立体匹配技术发展研究 篇3
1 局部匹配算法
局部匹配的方法所选择的匹配基元基本上分为三类, 据此局部算法分为区域匹配算法、特征匹配算法、相位匹配算法。
区域匹配算法用基准图像中点的邻域的窗口内像素的灰度值的某种分布如常用的SAD来表征待匹配点, 以在此表征下的相关程度为标准, 在对准图寻找对应的一个匹配像素点。区域匹配算法能够在平坦的丰富纹理区域获得稠密的视差图, 这是区域匹配最显著的优点。
邻域窗口选取越小, 在视差不连续区域匹配精度越高, 但在低纹理区域不能覆盖足够的灰度变化匹配, 匹配效果不好;大窗口在重复纹理区域取得较好的效果, 而在弱纹理区域中的深度差不连续的区域易造成误匹配。所以通过自适应的窗口大小[2]或自适应权重的聚合方式来改进匹配效果。为了解决弱纹理区域的匹配问题, 一些研究提出了利用图像分割区域信息对其进行改进的算法。该类方法将亮度和颜色相似的像素聚类成一个分割块, 位于同一个分割块的像素的深度进行整体求解。由于自动分割往往会出现一些错误, 所以一些方法提出采用过分割或软分割技术来试图解决不正确分割所带来的问题。
区域匹配算法仅依赖于视图中灰度信息的变化, 使得其对噪声和图像的畸变敏感。
基于特征的匹配算法在左右立体视图上把分别由同一关键场景点投影所得像素点的对应关系找出来。特征点可以是图像中灰度梯度极值或边缘线交点的角点, 也可以是直线段, 面等结构特征。
特征匹配处理算法的优点包括: (1) 匹配准确度高。特征点属于高级图像结构信息, 鲁棒性强, 受光线和噪声等方面的影响小。 (2) 由于视差的深度不连续多会反映在包括了边缘, 梯度等信息的特征算子里, 所以其对于深度视差不连续区域的匹配效果好。 (3) 由于特征点数量有限, 所以匹配速度快。
由于特征在图像中的稀疏性, 提出的特征点的数量在整图中分布比较稀疏。这使得特征匹配算法不能得到稠密的视差图;而且特征点的提取和定位效果的好坏, 将很大程度上影响匹配的精度。
特征匹配常与同其他立体匹配算法相结合使用。例如分级特征匹配算法的思想是根据图像自身的结构特点分层提取边缘特征, 逐级构建特征分组。最终算法将所有信息融合。这样逐层分级的策略减少了搜索空间, 从而减少了计算复杂度。
最晚提出的局部匹配方法是相位匹配算法, 包括相位相关法和相位差-频率法。相位匹配算法的实质是寻找局部相位相等的对应点。与上述两类传统的方法相比较, 像素的相位信息本身反映了信号的结构信息, 对图像的高频噪声和畸变都不敏感。此匹配方法主要优点是适于并行处理高效实现, 可获得亚像素级精度的致密视差.但由于其对相位的各种扰动较为敏感, 一般只能得到景物的粗糙结构。
相位匹配算法需要解决相位奇点匹配问题和相位卷绕问题。通过相位奇点的检测和去除以及最邻点视差填补的办法可以解决相位奇点的匹配问题。徐彦君在研究中选择低冗余度的质数序列作为Gabor滤波器组的波长, 将相位匹配算法的收敛范围扩大, 实现了高效的尺度自适应选择算法, 克服了相位卷绕的问题。
2 全局匹配方法
2.1 态规划的匹配算法
基于动态规划的立体匹配算法将匹配过程看成是在左右图像对应扫描线上寻找最小匹配代价路径的过程, 规划出的路径由趋于具有最小匹配代价的匹配点的集合构成, 即正确匹配点的集合。
但传统的得到的视差图中存在水平条纹瑕疵。原因是动态规划是基于扫描线进行处理, 缺乏水平连续性约束和垂直连续性。半全局的立体匹配算法被提出来, 用多个一维平滑约束来近似匹配像素的二维平滑约束, 在多个方向上进行动态规划。该算法改进了条状瑕疵现象, 但依然不能利用图像中的绝大部分像素来计算视差。例如在低纹理区域, 可能没有一条路径能够搜索到足够的纹理信息就会导致错误匹配。
2.2 图割法和置信度传播立体匹配算法
图割法和置信度传播算法本质上都是运用马尔科夫随机场来进行全局匹配的优化, 仅仅是在构图时和构造能量函数时所采用的方法不同。
置信度传播 (BP) 算法是一种基于消息传递机制的马尔科夫随机场最小化能量估计方法。置信传播算法利用最大积算法求解整幅图像全局能量最小值时的视差分布。置信传播算法的优点是能很好地处理深度不连续区域和低纹理区域。这是由于其消息传输能够适应图像中区域的特点自动调节消息传输时的距离的远近, 计入了相邻像素点以及不相邻像素点
基于Matlab Builder JA的QPSK调制解调在线仿真
程赛
(云南大学信息学院, 云南昆明650091)
摘要:阐述了基于Java Web和Matlab Builder JA开发的一般模式, 将Matlab强大的仿真计算能力应用到Web环境中。在浏览器中输入Matlab程序参数并提交给服务器, 服务器结合Web Figure图形方式的使用, 将实验结果直观地返回, 实现了交互式操作。通过这种B/S方式, 完成了二进制数字信号的QPSK调制与解调的模拟仿真。
关键词:Matlab;Builder;JA;Java;Web;QPSK;调制;解调
中图分类号:TN911.3文献标识码:A
0引言
Matlab以其强大的矩阵处理能力和丰富的图形渲染能力在工程计算和教育科研领域有着广泛的应用。其中基于Web的应用也越来越受到重视。但是, Matlab 2006b之后的版本却不再支持Matlab Web Server功能[5]。官方推荐使用Matlab Builder NE/JA来取代Web Server的功能[8]。
Matlab Builder JA用来将M函数文件创建成一个Java组件, 它支持Matlab的所有功能。将生成的Java组件作为Servlet或其他Java程序的外部添加库, 通过访问这些库中类的方法来调用MCR产生处理结果[1]。
1系统构架
Matlab的Java Web应用, 包括J2EE服务器, Matlab Build-
对目标像素点的影响。置信度传播算法不足体现在:由于基于逐个像素点之间的消息传输, 使计算量很大, 优化过程需要通过多次的迭代获得最终结果;二是单个像素点的颜色的畸变, 如在实际场景中, 由于噪声、颜色效应等原因, 造成的某些像素点颜色的突变, 从这种突变点进行消息传输, 算法精度将受到影响。
针对计算效率低下的问题, Felzenszw alb等人提出了一种分层的置信传播的方法, 缩短了一般的置信度传播算法的收敛时间。HBP得到的效果同标准BP算法相近, 运算的实时性方面可以同一些局部的方法相当。
图割方法是由Vladimir Kolmogorov等提出的将图论中的最小割算法运用到立体匹配的优化过程中, 通过求得最短路径的过程得出整幅图像的视差。步骤包括建立匹配能量函数, 构造网格图, 利用最大流求解能量函数的最小值。
图切割算法具有解决组合优化问题的良好性能, 在低纹
文章编号:1673-1131 (2012) 05-0045-02
er JA产生的Java组件和Matlab Compiler Runtime (MCR) 。MCR是一套运行经编译过的Matlab代码的库, 它允许在服务器端集成。终端用户通过Web浏览器发送请求到服务器, 服务器端程序调用Matlab Builder JA创建的Java组件, 调用MCR, 执行Matlab程序, 得到所需的结果并返回。图1显示了基于Java的Matlab Web应用的框架。
2 QPSK调制解调技术
QPSK (Quadrature Phase Shift Keying, 正交频移键控) 广泛应用于无线通信中, 是一种重要的调制解调方式。它利用载波的四种不同相位差来表征输入的数字信息, 分别有/4, 3/4, 5/4, 7/4四种载波相位, 调制时输入的是二进制数字序列, 为了配合四进制的载波相位, 则需把二进制数据变换为四进制数据, 也就是将二进制数字序列中每两个比特分成一组, 共有四种组合, 即00, 01, 10, 11, 其中每一组合称为双比特码元。每一个双比特码元是由两位二进制信息比特组成, 它们分别代表四进制四个符号中的一个符号。QPSK中每次调制可传输2个信息比特, 这些信息比特是通过载波的四种相位来传递的。解调时则根据星座图及接收到的载波信号的相位来判断发送端发送的信息比特[7]。
在QPSK调制中, 串/并变换器将输入的二进制序列分为速率减半的两个并行序列, 经电平变换后成双极性序列, 然后分别对cos t和sin t调制, 两路信号相加后得到QPSK调制信号。QPSK同相支路和正交支路可分别采用相干解调方式解调, 得到I (t) 和Q (t) 。经抽样判决和并/串变换器, 将上、下支
理区域、遮挡区域以及深度不连续区域, 能够获得相对其他方法更高的匹配精度, 因而能生产高精度的稠密视差图。另外图割方法在优化过程中收敛速度也相对更快。图割算法的计算量是非常大的, 应用中必须提高其时间效率。
摘要：比较分析了各种立体匹配算法的基本思想和各自的优点和局限性。为各种算法的融合和改进研究提供了分析指导。
关键词：立体匹配,局部匹配,全局匹配
参考文献
[1]Scharstein D, Szeliski R.A Taxonomy and Evaluation of Dense Two frame Stereo Correspondence Algorithms[J].International Journal of Computer Vision, 2002
双向立体匹配 篇4
立体视觉是由摆放于不同位置的2个摄像头获得同一场景的图片,通过计算视差,获取物体的深度信息。其在机器人导航和三维建模等热点领域有着广泛的应用。而立体匹配一直是立体视觉中的核心和难点,其主要任务是找到2幅图像之间对应的匹配点。到目前为止,还没有算法能够完美解决这一问题,因此如何快速、准确地进行匹配仍然具有重要的意义。根据文献[1]的分类标准,现有的立体匹配算法可以分为全局立体匹配算法[2,3,4]和区域立体匹配算法[5,6,7,8,9]2大类。全局立体匹配算法要综合考虑整个图像的特征,能够得到精确的视差图,缺点是算法复杂,迭代过程非常耗时,不适合进行实时处理。基于区域的立体匹配算法是将为每一个待匹配的像素分配窗口,用窗口内的信息作为特征,从而找到匹配的像素点,能够产生稠密的视差图,且匹配时间较之全局算法大大降低。目前较为前沿的有基于联合匹配代价的立体匹配[6]、自适应加权立体匹配[7]等算法。虽然取得了较好的匹配效果,但与传统区域匹配算法相比算法复杂。其60 s左右的运行时间在现有硬件条件,特别是闭环系统中,适用范围依然较小。
1 加权匹配代价和色彩分割
本文算法主要基于色彩分割的视差假设,同一分割区域内视差变化平滑,一定范围内同属某分割区域的像素视差相等[10,11]。而在实际情况中,特别当图像过分割的情况下,色彩突变总是伴随着深度边界同时出现[6]。基于这个假设可以将立体匹配过程转化为寻找同一分割区域内视差值的问题。算法主要由计算初始视差及最终视差优化2个部分组成。在初始视差计算中采用了综合灰度差及灰度梯度的相似性测度函数。随后采用目前使用较为广泛的Mean-Shift算子对原图像进行分割[12],生成优化模板,对初始视差图像进行滤波。算法流程如图1所示。
1. 1 加权匹配代价
计算相似性测度函数是匹配算法的基础,目前比较常用的相似性测度函数有灰度差的绝对值之和( SAD) 、灰度差的平方之和( SSD) 、GRAD和归一化相关系数( NCC) 等。通过表达式对比发现,SAD的计算复杂度最小。而GRAD算子通过计算像素点梯度,有效地提高了匹配的准确度。将二者结合在提匹配精度的同时,降低了算法的复杂度。SAD和GRAD的表达式为:
式中,N( x,y) 是以点 ( x,y) 为中心的窗口; I1( i,j)为参考图像中像素点的灰度值; I2( i,j) 为匹配图像中像素点的灰度值; d为左右视图中对应像素点的视差。
式中,"x是水平方向的梯度; ▽y是垂直方向梯度;Nx( x,y) 和Ny( x,y) 分别是以点 ( x,y) 为中心的水平方向和垂直方向上的邻域窗口。
在相似性测度函数中窗口的选择一直是最核心的问题。较大的窗口会在全局上改善匹配精度,同时也会增加匹配时间及视差不连续区域的误匹配率。本文算法为解决这一问题,对原有相似性测度函数做了简化,取消了原有的窗口,只计算对应像素点的灰度值之差。从而降低算法的计算量,避免了视差不连续区域的膨胀效应。
简化后的SAD和GRAD表达式为:
将SAD算法和GRAD算法结合作为匹配代价,计算方法为:
式中,ω1和ω2分别为CSAD( x,y,d) 和CGRAD( x,y,d)的权重因子。通过大量实验发现,当ω1和ω2的绝对和为1,即︱ω1+ ω2︱= 1时匹配效果较好,反之误差数会增多。
1. 2 Mean-Shift 图像分割
Mean-Shift算子最早由Fukunaga[13]提出,核心是一个算法迭代过程。首先计算出初始点的偏移均值,并使该点移动到其偏移均值。随后将该点作为新的起始点并继续移动,直到满足一定的约朿条件迭代结朿。假设xi( i = 1,…,n)为给定d维空间Rd的n个样本点,那么基本Mean-Shift向量的定义为:
式中,Sh表示半径为h的d维球形区域,满足以下关系的y点的集合,
式中,( xi- x) 表示落在球形Sh区域内的样本点相对于起始点x的偏移向量; k表示在这n个样本点xi中,有k个点落入Sh区域中。由于Mean-Shift图像分割算法和人眼对图像的分析特性非常相似,经过分割后的图像可以很好地区分不连续点与弱纹理区域。这也是本文选择Mean-Shift算子进行图像分割的根本原因。Mean-Shift图像分割步骤为: 1初始化起始点并开始迭代过程; 2记录每一个像素点收敛的位置,将收敛于同一点的像素点归为一类,并赋予标号; 3当所有像素点都满足约束条件,分割结束。
1. 3 初始视差优化
在完成了初始视差计算及图像分割后,算法便简化为在初始视差矩阵中以分割后图像为优化模板,寻找相同区域内视差值的问题。优化步骤为:1将分割得到的图像灰度化,计算分割区域内像素的灰度平均值,并将其赋给相同区域内所有像素点;2以处理后的图像作为模板优化初始视差图像,统计分割区域内出现次数最多的视差值并将其作为该区域的视差,得到最终结果。
2 实验结果及分析
为了验证本文算法的匹配效果,在Intel Core i52. 5 GHz、4 G内存的Windows平台下用Matlab实现算法,采用来自Middlebury的国际标准图像Tsukuba进行测试,取得了较好效果,并将本文算法与SSD算法进行比较。算法对标准图像的实际处理结果如图2所示。窗口分别为3* 3、5* 5和7* 7时SSD算法匹配得到的视差图像及本文算法结果,如图3所示。
表1列出了Middlebury提供的非遮挡区域误匹配率( nonocc) 、所有区域误匹配率( all) 和视差不连续区域误匹配率( disc) 这3个定量参数的量化评价结果,并与传统算法做了比较。可以看出随着SSD算法窗口的增大,其总体误匹配率降低,但在视差不连续区域并没有太大改善。而本文算法在提高所有区域匹配效果的同时,其在视差不连续区域的匹配效果较之SSD算法有了很大程度的改善。误匹配率由最高46. 9% 降至22. 9% 。
2种算法的计算效率的比较如表2所示,可以看出本文算法计算速率较传统算法提高了2 ~ 3倍。
通过对表1、表2和图3中本文算法及传统立体匹配算法的匹配结果的分析可知,由于本文算法简化了相似性测度函数,匹配复杂度与传统算法相比明显降低,匹配速率有较大提高,能够很好地处理视差不连续区域,没有出现边界的膨胀效应。同时,视差优化解决了简化相似性测度函数带来的大片弱纹理区域的误匹配问题,使最终的匹配精度较之传统算法有了很大改善。
3 结束语
在深入研究了加权匹配代价和色彩分割的视差假设后,提出了基于加权匹配代价和Mean-Shift图像分割的立体匹配算法。首先运用加权匹配代价计算初始视差矩阵,随后将经过色彩分割后的图像作为模板优化初始视差。实验结果表明本文算法有效改善了视差不连续区域的匹配精度,同时大幅度地降低了匹配时间,可作为一种实用的算法投入应用,同时为后续算法的优化提供参考。
摘要：针对现有立体匹配算法复杂、耗时较长的特点,提出了一种基于加权匹配代价和色彩分割的立体匹配算法。算法引入一种基于梯度差算子与绝对差算子加权的匹配代价计算初始视差。根据基于色彩分割的视差假设,采用Mean-Shift算子对图像进行分割,用分割后的图像作为模板优化初始视差。实验结果表明,该算法提高匹配精度和速度,具有良好的实用价值。
双向立体匹配 篇5
公安机关日常工作中采集到的数据, 大多为碎片化数据, 具多源、量大、且又离散如何有效提取这些非结构化数据中的有效信息以方便警务应用系统进行进一步分析处理, 为案件侦破、情报分析等提供服务, 关键技术就是利用中文分词算法将这些描述性的中文语句转变为结构化数据。
2 中文分词技术简介
2.1 中文分词算法分类
中文分词技术属于自然语言处理技术范畴, 现有分词算法分为基于规则的分词方法、基于统计的分词算法和基于理解的分词方法。
基于规则的分词方法中占主流地位的是正向最大匹配法和逆向最大匹配法。由于汉语单字成词的特点, 正向最小匹配和逆向最小匹配一般很少使用。逆向匹配的切分精度一般高于正向匹配, 遇到的歧义现象也比较少。由大数据量的统计表明正向和逆向最大匹配的错误率分别为1/ 169 和1/ 245, 但这种精度还远远不能满足实际的需要。实际使用的分词系统, 都是把机械分词作为一种初分手段, 还需通过利用各种其它的语言信息来进一步提高切分的准确率。
基于统计的方法是基于多个汉字同时出现的概率, 通过对语料库有监督或无监督的学习, 得到描述一种语言的语言模型 ( 常用一阶隐马尔可夫模型 ( 1st HMM) ) , 该方法优点是只要有足够的训练文本即可降低未登录词的影响。
2.2 Jieba分词算法
Jieba分词算法基于规则与统计相结合, 利用前缀词典实现高效的词图扫描, 生成句子中所有可能成词情况所构成的有向无环图 (DAG) , 要生成有向无环图必须有语料库的辅助, 语料库中每条记录会包含词、词频、词性等属性。Jieba分词试图查找树结构中的最大概率路径, 找出基于词频的最大切分组合;对于未登录词, 采用基于汉字成词能力的HMM模型, 使用Viterbi算法。
Jieba分词在HMM中有两种状态, 一种是具有决定性的隐含状态, 另一种的显性输出的状态。在Jieba分词中状态有4 种, 分别是B, M, E, S, 对应于一个汉字在词语中的地位即是B (开头) , M (中间) , E (结尾) , S (独立成词) , 而输出就是一个汉字。
在HMM中还有三种概率分别是状态分布概率, 状态转移概率和发射概率 (发射概率是一个条件概率, 表示在某一状态下得到某一输出的概率) 。图1 为二状态的马尔科夫模型。
要对一串汉字进行分词, 首先使用Viterbi算法判断这串汉字最有可能的BMES组合形式。在Jieba分词中作者经过大量的实验在文件中中预存好了汉语的一些概率值。prob_start.py中预存了每种状态的概率。
对于一个中文语句, 第一个汉字的状态概率称为初始概率, 可以用贝叶斯公式得到:
其中P (i) 表示状态的概率, 在文件prob_start.py中可以找到, 即发射概率, 而P (k) 即某个汉字出现的概率, 忽略不计。则有:
第二个字的状态概率是:
其中P (i1) 表示第一个字的状态概率, P (i2) 表示第二个字的状态概率, P (i2|i1) 表示状态i1到i2的转移概率, P (k2|i2) 表示发射概率。
以此类推, 由于每一个状态都有4 种选择, 所以根据每种选择导致的状态转移路径计算得出的概率值也不同, Viterbi算法的目的是找出概率最大的一种转移路径。如果语句长度为2, 那么算法的目的就是使上面的P (i2) 最大化。到达某一种中间状态的路径可能有多条, 如在第三个节点到达状态M可能路径有S->B->M、B->M->M等, Viterbi算法在中间这一步中就进行“剪枝”, 只记住路径中概率最大的那条。
3 警务应用系统中对Jieba分词算法的改进
警务应用系统对分词算法准确度的要求远远高于对分词算法速度的要求。本文基于Python3.4+Jieba0.37 分词包, 选择在中文词库、最大匹配算法等方面进行改进以提高分词准确度。
3.1 词库优化
词库是中文自动分词的基础, 词库机制的优劣直接影响到分词的速度和准确度。
(1) 枪械, 盗窃, 抢劫这些事警务应用中的常见词汇, 通过合理调高这些词的比重, 能够快速将其识别提取。
(2) 利用二次分词法可以提高城市名、路名、车牌号、时间等警务应用中较为关心的词汇的识别度。在基本词库中添加当地地名和地址库, 地名地址词库保存城市特有地名、路名、机构名、小区名、兴趣点和大地名。通用词主要用于对词典中有重复的词或是分词后的具有歧义或不准确的词进行修复, 如“华夏二路”在词典并不存在, 但是“华夏”却在词典中, “二”为数量词, 所以自动分词结果为华夏/ 二/ 路。这时可对地址进行二次查找, 当有单字存在于地名通名词典中时, 将其与前面未登录单词合并。如“路”存在于通用地址库中, 可将其和前面的单词“二”合并, 分词结果为华夏/ 二路。同理, 对于某些特殊格式的词, 如车牌“沪XXXXXX”、时间等, 由于词库不能枚举所有车牌或日期, 同样可采取二次提取, 将特定格式的字符串整合。如“沪XXXXXX”按常规分词会分为“沪/XXXXXX”, 利用二次提取, 将所有省简称与后面跟着非汉字字符串长度为7 的字符串合在一起成为新词, 即可被识别为车牌信息。
3.2 双向最大匹配法
最大匹配算法主要原理是切分出单字串, 然后和词库进行比对, 如果确定是一个词就记录下来, 否则通过增加或者减少一个单字, 继续比较, 直到剩下一个单字为止, 如果该单字串无法切分, 则作为未登录词处理。
据Sun M.S. 和Benjamin K.T.的研究表明, 中文中90.0% 左右的句子, 正向最大匹配法和逆向最大匹配法完全重合且正确, 只有大概9.0% 的句子两种切分方法得到的结果不一样, 但其中必有一个是正确的 (歧义检测成功) , 只有不到1.0% 的句子, 或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的, 或者正向最大匹配法和逆向最大匹配法切分不同但两者都错 (歧义检测失败) 。
本文提出的双向最大匹配法将正向和逆向最大匹配法得到的分词结果进行比较, 决定正确的分词方向。首先对语句正反向各进行切分, 然后根据大颗粒度词越多越好, 单字词越少越好的原则, 选择一种合适的方式输出。即在切分数不同时, 优先取切分数少的那一个结果;切分数相同时, 优先取单字少的那种;在切分数, 单字数都相同时, 因为逆向最大匹配法统计来说相对准确率较高, 取逆向为结果。流程图如图2 所示。
以下两例是双向最大匹配法的应用场景:
例一:“我们在野生动物园玩” (如表1)
例二:“我是北大学生” (如表2)
可以看出在使用双向最大匹配算法可以在单纯使用正向与逆向匹配算法结果不同时, 选择更合适的一个, 保证了更高的分词准确度。
3.3 性能测试
根据国际中文分词测评的标准中对汉语分词进行测试的方法, 在第二届国际汉语分词测评中共使用了四家单位提供的测试语料 (Academia Sinica、 City University 、Peking University 、Microsoft Research) , 本文基于Peking University提供的语料, 利用语料库自带的分词脚本进行测试。以下的测试结果显示双向最大匹配法比起Jieba算法的最大逆向匹配, 虽然消耗更多计算时间和计算资源, 却提升了分词准确度 (如表3) 。
召回率指在分词标答中, 分出正确的词语所占的比例;准确率指分词结果中, 分出正确的词语所占的比例。召回率和准确率一般是此消彼长的关系, 所以常用11 种召回率下准确率的平均值 (综合指标) 来衡量一个分词系统的精度。将这两个度量值融合成一个度量值, 如F度量, 如图3、图4 所示。
对于警务应用系统, 针对警用词汇的词库改进后, 能以更准确的提取所需词汇。以接警信息作为对象进行测试, 例如在接警信息中出现“报警人”、“虹口分局”、地址、日期等词汇时, 在原程序下会变成“报警人”“虹口分局”无法正确识别。摘取部分实际测试结果如图5、图6。
4 小结
本文针对警用领域的分词进行了一定的研究, 寻找在杂乱无序的碎片文件中以较高准确度提取关键词的方法。中文分词是识别、提取出关键词进行分析应用的基础, 本文提出的词库优化和匹配算法改进能够提升原Jieba算法的准确度, 由于语料库规模限制以及参数设置等因素的影响, 实验结果还存在可提高的空间。
摘要：中文分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、自然语言理解等中文信息处理领域的基础。目前中文分词依然是中文信息处理的瓶颈之一, 本文对常见中文分词算法进行研究, 并针对警务应用的场景, 在经典的Jieba中文分词算法的逆向匹配法基础上提出双向最大匹配法, 最后验证改进后的算法在中文分词准确度方面的提升。
关键词：中文分词,双向最大匹配法,警务应用
参考文献
[1]冯书晓, 徐新, 杨春梅.国内中文分词技术研究新进展[J].情报杂志, 2002 (11) :29-30.
[2]宗成庆.统计自然语言处理[M].北京:清华大学出版社, 2013 (08) .
[3] (美) Wesley J.Chun (陈仲才) 著, 杨涛, 王建桥, 杨晓云, 高文雅, 等译.python核心编程[M].北京:机械工业出版社, 2001 (08) .
双向立体匹配 篇6
立体匹配问题是计算机视觉研究的热点问题之一，它是利用计算机来模仿人类通过眼睛线索感知距离的一种方法。其中关键的一点是解决图像上的视差计算问题，以此来恢复点的三维坐标，进而试图重建物体的三维表面信息。目前所采用的立体匹配方法大致可以分为两类： (1) 基于区域灰度相关性的方法[1][2]，该方法可以得到稠密的视差图，但是其匹配的精确度要受到窗口大小、纹理和光照反射的影响，而且具有可观的时间复杂度； (2) 基于图像特征的匹配[3][4]，该方法更多地强调利用空间景物的结构信息来解决匹配的歧义性，匹配特征主要为线状特征、角特征、区域特征等，该方法只能得到稀疏可靠的视差图。动态规划法在立体匹配中得到了普遍的应用，文献[5]参考了语音信号处理中的时间规整算法 (Dynamic Time Warping, DTW) ，以灰度段作为匹配的基元，算法简便，利于匹配，但其灰度分段在遮挡、光照不均和畸变的情况下会产生误分段；文献[6]采用一种模糊逻辑的方法先是进行边缘点的检测，把极线上边缘点之间的像素都划分为一个段，然后做左右图像相容段上像素的匹配，这样特征点匹配的准确性对整个视差图的准确性起着至关重要的作用, 且在噪声、遮挡及透视等因素影响比较严重的情况下，特征点的精确匹配会受到干扰；文献[7]提出一种基于自适应窗口的时间规整算法，但是没有利用像素的彩色信息和梯度信息，而且也只是采用效果不好的比较灰度大小来分段。Koschan和Rodehorst (1997) 认为用彩色信息代替灰度信息，立体匹配结果的准备率能够提高20%-25%，为了得到精确度更高的视差图，本文提出一种基于区域生长的时间规整立体匹配算法，先用边缘点对极线初分段，再把待匹配图像的边缘点分段结果用区域生长方法分割为大小不等的匹配区域序列，类似于待匹配的模板。在图像对中的另一幅图像的视差范围的窗口中利用区域生长方法生成若干个匹配序列，再利用颜色极小选择最佳的匹配序列，以此两个区域作为匹配基元，再利用DTW算法对匹配序列进行基于动态规划的整体匹配。
1、区域生长方法的匹配序列划分与获取
本文基于颜色段的立体匹配算法，是将图像对中对应极线上的图像信息按颜色信息进行分段，以颜色段作为匹配基元，利用DTW (dynamic time warping) 方法进行匹配。以颜色段作为匹配基元比点基元覆盖的图像空间要大，可以减少误匹配发生的几率，更容易进行匹配，而且这种方法比基于特征线段、二次曲线或任意平面代数曲线的方法计算起来要简便得多。我们希望能够得到图像对中视差值比较相近的区域来进行匹配，这两个区域可以称之为左右"匹配序列"。因为存在遮挡的问题，所以左右匹配序列的尺寸并不一定相同，不可能也不应该试图找到大小全部相等的匹配序列区域。本文算法的设计和实现遵循如下视觉理论的约束条件：外极线约束；匹配惟一性约束；视差连续性约束。
考虑二种得到匹配序列的方法： (1) 利用像素点的灰度信息与灰度均值的差小于设定阈值的方法对图像的像素行进行分段； (2) 通过基于特征的边界检测来确定匹配序列。文献[6]首先获得边缘特征点的视差, 然后在这些特征点视差图的约束下, 对非特征点利用灰度大小进行分段, 既缩小了匹配空间, 又保证了匹配的相对准确性, 获得了较好的效果, 但带来的问题是, 由于特征点的视差图对整个视差图的准确性起着至关重要的作用, 且在噪声、遮挡及透视等因素影响比较严重的情况下, 特征点的精确匹配会受到干扰。文献[7]设定自适应窗口，但是没有利用颜色信息，也只是利用灰度信息进行分段，相比来说没有利用颜色信息的区域生长的分段方法对极线的分割效果好。
1.1 边缘特征点匹配
边缘特征点的匹配就是要找到一幅图像中某一扫描线上的某个边缘特征点在另一幅图像中的对应边缘特征点，但由于在外极线的约束下，在另一幅图像中相应扫描线上，仍然存在多个可能匹配的边缘点，因而匹配过程具有不确定性和模糊性。匹配之前先要进行边缘特征点的检测，按照图像边缘检测所利用的图像信息, 边缘检测方法可分为两大类：基于梯度信息的图像边缘检测和基于相位信息的图像边缘检测。相位检测计算复杂度比较高，实时性不好；灰度梯度信息对图像中大量的噪声非常敏感，且随着图像的对比度和亮度的改变而发生改变。我们采用Canny算子，同时加入色彩梯度信息，检测的准确率得到很大提高。
我们定义颜色梯度如下：
像素总的颜色梯度可以定义为：
我们采用经典的Canny算子提取图像对的色彩边缘特征，以边缘点的色彩梯度大小、方向、边缘点的色彩梯度大小相关系数以及边缘点的颜色相关系数等4个因素作为边缘点相似性的度量要素。然后我们利用文献[6]的方法采用模糊理论来解决边缘点的匹配问题，它的出发点正在于能有效地处理这种不确定性问题的模糊性。
1.2 极线分段
在文献[8]中列出了所有的12种颜色相似度计算方法，所有的计算方法都输入两个矢量，计算得到一个在[0.0, 1.0]之间的结果，1.0表示两种颜色完全相同，0.0表示两种颜色完全不相同。[9]对这12种方法进行了对比实验，证明了绝对值指数方法是最优的。绝对值指数方法定义如下：
fi和fj是两个P维颜色矢量，在RGB颜色空间中每个点的颜色由红绿蓝三个元素的矢量表示，所以p=3, S (fi, fj) ，是颜色相似度，其中β>0。为了减小计算的复杂度，而且不影响计算结果，本文中我们对绝对值指数方法进行一些改变，直接用绝对值差的和来表征两个像素颜色的相似性。即：
区域生长方法[10]将图像以像素为基本单位来进行操作。分割步骤如下：
1、对图像进行逐行扫描，找出尚没有归属的像素；
2、以该像素为中心检查它的领域像素，即将领域中的像素逐个与它比较，如果颜色差小于预先确定的阈值，将它们合并；
3、以新合并的像素为中心，返回到步骤2，检查新像素的领域，直到区域不能进一步扩张；
返回到步骤1，继续扫描直到不能发现没有归属的像素，刚结束整个生长过程。
采用上述方法得到的结果对区域生长起点的选择有较大的依赖性。为了克服这个问题可以我们采用下面的改进方法：
1、设颜色差的阈值为0，用上述方法进行区域扩张，使颜色相同像素合并；
2、求出所有领接区域之间的平均颜色差，并合具有最小颜色差的邻接区域；
3、设定终止准则，通过反复进行上述步骤2中的操作将区域依次合并直到终止准则满足为止。
另外，当图像中存在缓慢变化的区域时，上述方法有可能将不同区域逐步合并而产生错误，为了克服这个问题，不用新像素的颜色值去与领域像素的颜色值比较，而用新像素所在区域的平均颜色去与各个领域像素的颜色进行比较。
在实际应用区域生长方法时需要解决3个问题：选择或确定一组能正确代表所需区域的种子像素；确定在生长过程中能将相邻像素包括进来的准则；制定让生长过程停止的条件或准则。图像经过边缘特征点匹配后，得到图像极线各线段的的大体分布，可以利用代表各线段分布的边界信息自动获得种子点。同时这些边界点还可以作为生长停止的约束条件为生长过程提供潜在的线段模型。具体的生长过程如下：（1）对应用边缘特征匹配后的图像进行标记，取同一极线上两个边缘点的中心为种子点，计算该种子点与其左右像素（x, y）的颜色距离，如果该距离小于阈值T且生长还未到该线段的边界，则使其与种子点相同，同时将（x, y）压入堆栈；（2）从堆栈中取出1个像素，把它当作种子点，重复步骤（1），直到堆栈为空时，该区域生长过程结束。阈值T的选择则与种子点的选择有关，以每个线段的种子点为中心取一个小窗口，窗口的大小可调，分别计算窗口中像素点与中心像素点的颜色距离，统计最大颜色距离值和方差，阈值则为最大颜色距离值与方差之差。每两个边缘点中间一次生长后剩下的部分再用其中心点作种子点生长出新的线段。
1.3匹配序列获取
对右目图像某一极线进行分割后，接下来在左目图像对应极线上寻找像素段的相容匹配区域。设矢量f (x, y) 是右目图像 (x, y) 点处的RGB矢量，即：
R=fjr, frj+1, …, frj+M为右目图像某一极线上分割出的一个颜色段，设匹配最大视差为d，在左目图像中定义窗口L=fjl, flj+1, …, flj+m, …, flj+m+d，所以与右图像中R颜色段相容的左图像中的匹配序列一定是L的一个子集。我们同样对L进行区域生长分割，得到几个颜色段，记为Lk, Lk就是与R相容的匹配序列的候选序列族。我们取Lk中与R最相关的序列就是与R相容的匹配序列，相容匹配序列的方法通过段之间的颜色相似性来进行。
最相关序列L由 (L=min‖S (Lk-R) 2‖，k=0, 1，….K) 确定。有的图形利用边缘特征点分出来的段在某一区域都是像素很少的段，在这种情况我们就要先进行段的合并，保证段在某一长度之内。
2、基于DWT的颜色段匹配
得到了右图像中的序列R和它在左图像上的相容序列L，我们利用DWT算法对这两个序列进行匹配。对右图像中极线上的所有分割，首先我们选取长度最长的段先进行匹配，这样做不仅可以尽可能地避免匹配过程中的遮挡情况，而且可以缩小剩余段的匹配搜索范围，剩余段的匹配在该段的左、右部分分别进行，也同样先选长度最长的段进行匹配，像这样一直循环下去，直到所有颜色段都完成匹配过程为止。
为了使颜色段的匹配达到最佳效果，本文采用DTW算法，其核心思想是对匹配过程进行动态规划。设一个二维直角匹配坐标系，把右匹配序列R作为横坐标，坐标范围为 (0，…，M) ；把左匹配序列L作为纵坐标，坐标范围为 (0，…，N) 。横坐标和纵坐标上各点所组成的网格中，每一个交叉点表示左右匹配序列中可能匹配的一个点对 (m, n) 。DP算法可以归结为寻找一条通过此网格中若干匹配交叉点的连续的路径。路径不是随意选择的，根据约束条件中的连续性原则，匹配序列内各点的先后次序不必改变，因此所选的路径必定从左下角某点出发，在右上角某点结束。
在使用DTW算法进行匹配之前，我们要定义两个像素点的失真距离，失真距离越小颜色相似度就越高。设和分别是R和L上的两个像素，根据（5）式，这两个像素的失真距离可以计算为：
为了减少时间复杂度，防止过多地搜索匹配概率不大的路径，可以对路径中各点的斜率的最大和最小值给以限制，另外，左右两上匹配序列是通过区域生长得到的，不能保证匹配的起点和终点为固定点，所以无论是起点还是终点都采用松驰点，可以进一步克服不精确造成的误匹配，但是也增加了计算开销。
这样，求最佳匹配的DP算法可以归结为求一个最佳匹配路P，使得沿匹配路径P的积累失真距离达到最小值，为了方便表达，这里使用坐标 (m, n) 来代表R和L的匹配关系，使用距离d (m, n) 来代表失失真距离，为了满足路径的斜率在一个小的范围内，如果路径已经通过了 (mi-1, ni-1) 匹配点，那么下一个匹配点 (mi, ni) 可以是下列三种情况之一：
易证明，限定范围内的任一匹配点只可能有一条搜索路径通过，通过该点的最佳路径与以后的路径无关，那么，若匹配路径P通过节点通过‖mi-1, ni-1‖，并延伸到下一节点‖mi, ni‖，则此路径的累积失真表示为d‖mi, ni‖=d‖mi, ni‖+d‖mi-1, ni-1‖，这样动态规划的基本运算可以归结为：
最后得到的匹配路径P的总的失真距离为：
搜索到 (mk, nk) 时，已经生成并保留一条最佳路径，通过逐点向前回溯，可以求得整条路径P，回溯的起点即（下转第86页）为累计失真距离等于上式结果的匹配点，已知匹配路径P及L和R的起始坐标，不难得到各匹配像素的视差值，遍历图像后，即可以得到整个图像对的视差图。
3、实验结果及结论
在Matlab环境下，图1是对Teedy图像和Cones图像本文算法匹配结果。视差图中灰度级低 (亮度低) 的地方表示视差小，也即距视点较远，深度值大；反之，灰度级高 (亮度高) 的地方表示视差大，距视点较近，深度值小。从图中还可以看出匹配获得很好的效果，从而说明本文提出的算法是有效的。与采用基于区域的灰度相似算法的实验结果相比，本文算法明显改善了匹配效果，而且其运行时间大为减少，比基于区域的灰度相关算法的运行时间平均减少10～15倍。
通过理论分析和实验结果可以得出如下结论：（1）本文方法是基于区域生长的左右匹配序列的整体匹配处理算法，改善了匹配效率；（2）采用区域生长的算法提高了极线分割的准确性，也能够寻找到更准确的匹配序列；（3）采用绝对值指数的颜色相似测度，增加了像素的颜色信息，匹配更为准确。采用颜色作为匹配基元的优势在于，相对于点基元，覆盖了更大的图像空间，从而减少了误匹配发生的几率，更容易进行匹配，本文算法在虚拟现实和机器人视觉领域具有实用价值。
摘要：针对立体匹配过程中存在的不确定性和模糊性, 本文提出先利用匹配的边缘特征点对极线进行初分割, 然后利用区域生长算法进行颜色分段, 在颜色段的基础上进行时间规整的立体匹配算法。根据外极线约束, 在视差范围窗口内采用颜色相似极大得到长度不相等的两个像素段作为相容的匹配序列, 利用动态规划方法及连续性约束寻找一条最佳的匹配路径, 根据回溯得到匹配路径及其坐标值得到高密度视差图。实验结果表明该算法具有良好的匹配效果。
关键词：区域生长,立体匹配,DWT,动态规划
参考文献
[1]O.Veksler, "Fast variable window for stereo correspondence using inte-gral images, "in IEEE Conference on Computer Vision and Pattern Recog-nition, vol.1, 2003, pp.556-561.
[2]K.-J.Yoon and I.S.Kweon, "Adaptive support-weight approach forcorrespondence search, "IEEE Transactions on Pattern Analysis and Ma-chine Intelligence, vol.28, no.4, pp.650-656, 2006.
[3]D.G.Lowe, "Distinctive image features from scale-invariant key-points, "International Journal of Computer Vision, vol.60, no.2, pp.91-110, 2004.
[4]X.Lu and R.Manduchi, "Wide baseline feature matching using thecrossepipolar ordering constraint, "in IEEE Conference on Computer Visionand Pattern Recognition, vol.1, 2004, pp.16-23.
[5]周东翔, 蔡宣平等。基于灰度段的立体匹配算法, 软件学报, 2001, 13 (7) :1101-1106。
[6]Dongxiang Zhou, Qiongyu Wu.A Stereo Matching Algorithm Based onFuzzy Identification, Proceedings of the 2003 IEEE Intemational Confer-ence on Robotics.intelligent Systems.Changsha, China-October 2003.
[7]刘正东, 杨静宇。自适应窗口的时间规整立体匹配算法, 计算机辅助设计与图形学学报, 2005, 17 (2) :291-294。
[8]S.Barnard and M.Fischler.Computational stereo.Computing Surveys, 14 (4) :553-572, Dec 1982.
[9]K.N.Plataniotis and A.N.Venetsanopoulos.Color Image Processing and Applocations, pringer-Verlag, berlin, 2000.