一种镜像立体匹配改进算法

杨 业, 李宏宁, 冯 洁

(云南师范大学 物理与电子信息学院,昆明 650500 )

一种镜像立体匹配改进算法

杨 业, 李宏宁, 冯 洁

(云南师范大学 物理与电子信息学院,昆明 650500 )

基于图像视差的三维扫描技术中,计算样本外形需要从存在干扰的图像中寻找匹配对应点,提出一种镜像立体匹配改进算法,处理场景存在镜面的情况下物体和镜像的点点对应问题.新算法通过计算像素点与其邻域的灰度值之差,结合变权构建多维判别向量,通过判断物体空间和像空间中对应点的多维向量夹角的大小,来确定两个像素是否匹配.实验结果表明,相比传统的SAD,NSAD,SSD,NSSD立体匹配方法,新算法能够更好地处理有衰减模糊和色差的图像匹配问题,提高重现物体的几何外形精度.

立体匹配; 镜像; 变权

人眼从不同角度对物体进行观察,所得到的两个像之间必然存在视差,人的视觉系统有能够将获取的图像信息转化为三维视图的功能.立体视觉算法模拟人眼的这个功能,通过寻求两幅或多幅二维图像的视差特点,还原物体的三维模型和几何形状.然而根据立体视觉重建一个完整的三维模型,需要找到不同视角下准确的匹配点.

从20世纪70年代中期开始,以Marr,Barrow和Tenenbaum等为代表的研究者提出了一整套视觉计算的理论来描述视觉过程,其中以Marr的理论影响最为深远[1-2].根据匹配所采用的基元以及成像几何的不同,目前,立体匹配算法可以分为3大类:基于区域灰度的匹配算法[3-6]、基于特征的匹配算法[7-10]和基于相位的匹配算法[11-14].Levines算法是在一维的匹配邻域内搜索互相关值最大的匹配点[3];周秀芝等[4]对Kanada等提出的灰度窗口自适应进行了改进;李强等[5]提出一种新的基于图像灰度值的编码表示方法,对像素灰度的变化与噪声具有鲁棒性.周东翔等[8]利用边缘特征检测,得到了边缘部分的准确视差;纪华等[10]提出了结合全局信息的SIFT特征匹配算法,解决了图像中存在多个相似区域的误匹配问题;罗钟铉等[7]提出了一种基于小波变换和投影特征的图像匹配快速算法,提高了运算速度,也保证了匹配精度.李春磊等[11]提出一种基于改进LMedS算法和贪心估计策略的快速相位立体匹配方法,提高了算法效率和鲁棒性;姜宏志等[12]通过极线校正的相位立体匹配,来提高算法速度.以上大部分匹配算法解决的是多相机图像匹配问题,匹配图像颜色变化不大,对于存在明显颜色差异的图像需要重新设计算法来寻找匹配点.

本文提出了一种改进方法,相比传统的SAD (sum of absolute differences),NSAD (normalized sum of absolute differences),SSD (sum of squared differences),NSSD (normalized sum of squared differences)方法,在处理衰减模糊和有色差图像的镜像匹配问题上效果更好.光线通过非理想镜面反射,得到的镜像存在衰减模糊和色差现象,本文采用多维向量结合变权判断向量夹角大小的方法,在平面或像几何的约束下,对不同视角下观察得到的图像进行点匹配计算,并准确找出大部分匹配点.

1 算法原理及具体实现

1.1 图像采集方法

基于镜面的三维采集方法的原理如图1所示.将镜子垂直放置于水平台XM位置;固定相机于水平台正上方O′点,距离水平台的高度为hO,且相机光轴垂直水平台台面.在水平台上放置一个物体S,S′为物体S经过镜面反射产生的镜像;物体表面有一点A,与水平台面的距离为hA,A′为A的虚像.在O′处观察物点A和像点A′分别投影到X面于XA,XA′位置.

图1 图像采集原理Fig.1 Principle of image acquisition 根据图1中的成像几何关系,可以得到物点A与平台的距离满足以下关系

(1)

(2)式中:uA为S面上点A投影到像素平面的横坐标;f为相机的有效焦距;uo为光轴与像平面交点的横向像素坐标;dx为像素行中相邻两个像素的等效间距.结合式(1)和式(2)可以看出,当相机内部参数、镜子位置以及相机高度都已知时,镜像和物像在像素坐标的位置决定了物体的高度.

当相机的固定高度hO远远大于观测物体的实际高度时,由图1可以看出,AXA的长度近似等于hA,此时可以认为物体A的横坐标为XA,然后由式(1)和式(2)计算物体的高度.以上简要分析了X方向上的物体高度解法,在Y方向上物体高度求解方法类似.

根据以上原理设计了基于平面镜的图像采集和物体轮廓重建的思路:a.分别使用模糊镜面和镀膜镜面,然后利用相机一次拍摄,在二维图像中同时得到物体的镜像和物像;b.确定相机的内部参数、镜子在图像中的像素坐标以及相机距离水平台面的高度hO;c.分析图像,分别使用几种常见的立体匹配算法和本文的改进算法,寻找物点在镜像中匹配对应点;d.根据不同算法的匹配结果使用式(1)和式(2)计算匹配点的高度,然后重建物体的轮廓图并分析.

1.2 基于图像的点匹配算法

使用上文图像采集方法采集样本图像,在一幅图中分别得到物体的镜像和物像.为了获取由物体上众多点构成的轮廓图,需要根据物像和镜像中的对应点来计算视差,确定物像上任意一点在镜像上的位置,并采用基于图像的点匹配算法.为此,本文使用了像素区域匹配,原理如图2所示.fl(x,y)和fr(x,y)分别表示左右离散图像的灰度值,d为视差.在右图像上取一点OR,在左图像上找到其匹配点.由于在物体从三维空间经过相机投影后变成二维图像的过程中,一些表面信息被遮挡,还有一些物体的表面存在重复纹理、低纹理等问题,使得视觉系统必须依靠几何约束才能得到准确的对应点.为了降低匹配难度,引入了多种约束方法,来减少搜索范围,提高匹配成功率.

a. 极线约束. 通过极线约束,使匹配点的搜索空间由二维降低到了一维,减小了搜索区域,提高匹配效率和匹配结果的准确性.

b. 唯一性约束. 在一般情况下,匹配对应点只能一一对应.计算得到的每个匹配点只存在一个视差值.

c. 匹配保序性约束. 图像中匹配点在两幅图中左右顺序一致.

d. 有限视差约束. 根据有限视差原理,在极线上找OR的匹配点OL,设定最大的视差为dmax,则OL点的坐标范围在[x-dmax,x+dmax]之间.

图2 区域匹配Fig.2 Region matching

根据约束关系,可以把匹配点OL的搜索范围由全局降低到一维区间.图像在拍摄和传输过程中会受到环境、相机自身等因素的影响,这些因素往往对匹配结果造成干扰.为了解决这些问题,根据右视图中一点确定一个匹配窗口,然后根据邻域区域相似性,找到左图对应的匹配窗口,分别以OR和OL为中心点确定一个(2n+1)(2m+1)的匹配区域,在匹配范围内寻找最相似的区域,从而得到匹配点.现在常用的匹配方法有SAD(sum of absolute differences ) ,SSD(sum of squared differences),或者基于2个邻域的相似性来匹配.

a. 绝对误差和(SAD)方法.

Csad(x,y,d)=

(3)

b. 归一化SAD相似性函数(NSAD)方法.

Cnsad(x,y,d)=

(4)

c. 像素点灰度差的平方和(SSD)方法.

Cssd(x,y,d)=∑(α,β)[fl(x+α-d,y+β)-

fr(x+α,y+β)]2

(5)

d. 归一化SSD相似性函数(NSSD)方法.

Cnssd(x,y,d)=

(6)

式(3)～(6)中:C为匹配代价函数;α为匹配区域x方向上的取值,α∈[-n,n];β为匹配区域y方向上的取值,β∈[-m,m].从这4个公式中可以看出,它们都是通过比较左右图像中像素点的差值来判断匹配点是否为对应点.在左右图像颜色差别不大或者已知衰减值的情况下,可以使用这些方法来解决图像的点匹配问题.当左右图像明显存在不同程度的色差和衰减模糊等问题,且衰减模糊程度和色差值未知时,如果依然按照左右图两像素点的差别来判断是否对应相同点,需要考虑由对应像素点之差生成一个阈值,当阈值不确定或者不固定时,匹配效果并不是特别好.通常匹配区间的选择也是影响图像匹配结果的一个关键因素.当匹配区域选择的比较大,且图中的物像形变不大的时候,匹配区域对匹配结果不会产生太大的影响;反之,匹配区域的选择对匹配结果影响特别大,这种情况也是这4个公式不能解决的.由于以上4种算法不能很好地解决所描述的这类问题,本文使用了改进匹配代价函数.

(7)

(8)

式(7)中,α∈[-n,n],β∈[-m,m],比较的是中间像素点与周围像素点的区别,当左右像存在变化的时候,一般情况下像素点周围小区域的噪声变化不是特别大.根据中间点像素值与周围像素值之差,可以消除一部分噪声,然后利用差值构成左右像空间中对应点的多维向量,通过比较向量夹角的大小来进行匹配.式(7)和式(8)中ωi为变权,取决于相关窗口周围像素点与中心像素点的距离.当周围像素点距离中心像素点越近,此时可以认为这些比较近的像素点与中心像素点关系很密切,它们之间相互影响很强烈,此时权值相对而言会比较大;当周围像素点距离中心像素点越远,这些点对中心像素点的影响会比较小,此时权值相对而言也会比较小.假设像素点距离中心点像素无穷远,此时灰度值乘上一个无穷小的权值就等于0,对中心点像素几乎没有影响.式(7)中,C(x,y,d)的大小决定2个匹配窗口的相似性,在匹配过程中取C(x,y,d)的最大值,此时匹配最佳.相比式(3)～(6)也可以很好地解决匹配图像有干扰的问题.式(3)～(7)都是基于图像灰度匹配,对于彩色图像的匹配问题,可以把公式中的灰度转换为色差计算公式来获取准确匹配点.

2 实验结果及分析

2.1 实验方法

分别使用机器镀膜和手工贴上一层高反膜用做反光镜面,相机为IPhone 5s手机相机,拍摄环境为自然环境条件.固定相机于一个水平的架子上,上下移动并调节相机镜头,离拍摄物体的距离为20～25 cm,使镜头与水平面平行,并拍出清晰的图片.采用图1中所提的系统采集图像.使用镀膜镜面做反光镜面,拍摄到的半个乒乓球样本如图3(a)所示(样本1);使用高反膜镜面做反光镜面,拍摄得到的长方体盒子样本如图3(b)所示(样本2).比较图3(a)中的左边镜像与右边物像可以看出,镜像略带一层红色(镀膜材料引起),且颜色明显比物像中的颜色要暗.从图3(b)中对比左边镜像和右边物像可以看出,镜像存在衰减模糊现象(高反膜表面不是很光滑).然后使用算法对两个样本图像进行处理,并进行下一步匹配工作.

图3 采集样本Fig.3 Sample collection

2.2 实验结果分析

分别用SAD,NSAD,SSD,NSSD和本文的改进算法进行右边物像与左边镜像的相匹配实验.随机选取图3样本1和样本2的连续三行像素进行匹配,采用c#结合opengl使用点重建法分析匹配结果[2].如图4所示,使用本文改进算法得到结果(a)(f),使用SAD算法得到结果(b)(g),使用NSAD算法得到结果(c)(h),使用SSD算法得到的结果(d)(i),使用NSSD算法得到的结果(e)(j).

从图4可以看出,图4(f)表面有些变化幅度,一部分原因是由于高反膜镜面为手工制作,精度不高所致.除此之外,改进算法基本能重现物体的轮廓.然而,使用传统算法到的结果不是特别好(本文除了算法不同之外,其它条件均未改变).从图4(a),(b),(c),(d),(e)可以看出,图像的右边匹配结果比左边匹配结果要好,再从右往左观察样本1的镜像可以看出,色差在一点点减弱(观察视角不一样,看到的膜的颜色会有差别).当观察到镜像色差特别小的地方,此时镜像左边图像与物像右边图像的颜色极为相似,因此使用传统算法能够得到大致的结果;但是当物像左边部分与镜像右边部分匹配,匹配效果不是特别好.因为使用传统算法需要考虑相同对应点色差值的大小,如果色差值是变化的,则需要根据左右像素点之差附加一个变化的阈值来作为匹配代价函数.因此传统算法具有一定的局限性.

图4 匹配结果Fig.4 Matching result

使用不同算法得到的样本(b)匹配结果,如图4(f),(g),(h),(i),(j)所示.样本(b)中镜像与物像相对比,存在衰减模糊现象,这是由于高反膜表面不光滑所致.从相机上观察到的镜像,由于不同光通过高反膜镜面会产生不同程度的模糊现象.如果在物像上看到的是亮光,经过镜面模糊后可能在镜像上看到的光要暗一些;如果在物像上观察到的是暗光,由于镜面模糊,可能在镜像上观察到的是亮一些的光.模糊使得镜像和物像中对应点的像素差值不固定,使用传统算法也不能很好地解决这些问题.

在图像存在衰减模糊和色差的情况下,本文改进算法比较的是周围像素点与中间像素点的差值,这个差值可以消除一部分镜面成像所带来的噪声影响,然而引入向量夹角和变权在一定程上解决了衰减模糊和色差问题.在图像深度跳变的地方,采用本文改进算法进行匹配仍然存在较多错误匹配点,这是由于物体从三维经过相机投影后变成二维,表面一些信息被遮挡造成的,也是本文算法需要进一步改进的地方.

采用c#语言编写程序,在图3(a),(b)物体表面高度连续区域随机采集1 200个像素点,得到算法匹配的1 200个像素点的坐标,然后通过人眼观察并准确找到1 200个像素点对应的坐标,按顺序记录在算法匹配点的后面.如果匹配得到的点与正确的对应点的空间误差小于3个像素,则认为匹配正确;否则匹配错误.用匹配正确点的数量除以总的匹配像素点数目,得到算法的匹配率,结果如表1所示.

表1 算法结果Tab.1 Results by the algorithm

从表1可知,本文改进算法匹配率比传统算法匹配率高.在图像存在衰减模糊和色差的情况下,本文算法比较的是周围像素点与中间像素点的关系,引入了向量夹角和变权,有效地解决了衰减模糊和色差图像的点匹配问题.虽然SAD,NSAD,SSD和NSSD算法可以引入阈值解决图像的衰减模糊和色差问题,但是当图像衰减模糊程度和色差值不确定或者不固定时(样本的衰减程度未知,阈值都设为0),引入阈值也不是十分可靠.通过以上结果分析可知,本文算法对处理衰减模糊、有色差的镜像和物像的点匹配问题,相比传统的立体匹配方法更为有效.本文设计算法的初衷是为了获得较高精度的物体轮廓,因此在运行速度上要比SAD,NSAD,SSD和NSSD算法要慢,需要进一步优化.

3 结 论

针对衰减模糊和有色差图像的镜像匹配问题,提出了一种向量结合变权然后求夹角的立体匹配改进算法.实验表明,本文算法相比传统的SAD,NSAD,SSD,NSSD算法在匹配衰减模糊、有色差的镜像时效果要好.算法引入了向量夹角和变权能一定程度上解决图像的衰减模糊和色差问题,得到大部分正确匹配点,对研究这类问题,具有重要意义.

[1] MARR D.Vision:a computational investigation into the human representation and processing of visual information[M].California:University of California Press,1994:107-111.

[2] BARTOLI A,LAPRESTÉ J T.Triangulation for points on lines[J].Image and Vision Computing,2008,26(2):315-324.

[3] LEVINE M D,O′HANDLEY D A,YAGI G M.Computer determination of depth maps[J].Computer Graphics and Image Processing,1973,2(2):131-150.

[4] 周秀芝,文贡坚,王润生.自适应窗口快速立体匹配[J].计算机学报,2006,29(3):473-479.

[5] 李强,张钹.一种基于图像灰度的快速匹配算法[J].软件学报,2006,17(2):216-222.

[6] 陈皓,马彩文,陈岳承,等.基于灰度统计的快速模板匹配算法[J].光子学报,2009,38(6):1586-1590.

[7] 罗钟铉,刘成明.灰度图像匹配的快速算法[J].计算机辅助设计与图形学学报,2005,17(5):966-970.

[8] 周东翔,蔡宣平,孙茂印.一种基于特征约束的立体匹配算法[J].中国图象图形学报,2001,6(7):653-656.

[9] 张羽,朱丹,王玉良.一种改进的快速SIFT特征匹配算法[J].微计算机信息,2008,24(33):220-222.

[10] 纪华,吴元昊,孙宏海,等.结合全局信息的SIFT特征匹配算法[J].光学精密工程,2009,17(2):439-444.

[11] 李春磊,常智勇,莫蓉.基于改进LMedS算法和贪心估计的相位立体匹配[J].计算机辅助设计与图形学学报,2014,26(11):2046-2055.

[12] 姜宏志,赵慧洁,梁宵月,等.基于极线校正的快速相位立体匹配[J].光学精密工程,2011,19(10):2520-2525.

[13] 肖志涛,卢晓方,耿磊,等.基于极线校正的亚像素相位立体匹配方法[J].红外与激光工程,2014,43(S):225-230.

[14] 刘盛夏.基于相位信息的立体图像匹配研究[D].上海:上海交通大学,2010.

(编辑:丁红艺)

Improved Algorithm for Image Stereo Matching

YANG Ye, LI Hongning, FENG Jie

(SchoolofPhysicsandElectronicInformation,YunnanNormalUniversity,Kunming650500,China)

In the three-dimensional scanning technique based on image parallax,in order to calculate the shape of objects,it is required to match two points at different positions in images polluted by noises.An improved method for image matching was proposed to locate the object point and its corresponding image point in a mirror.By calculating the difference between the gray values of the pixel and its neighborhood,with a variable weight,by the algorithm a multidimensional discriminant vector was constructed and the angle between two discriminant vectors determines whether a pixel in object space matches another pixel in mirror space.The experiment results show that,compared with the traditional SAD,NSAD,SSD and NSSD,the algorithm is better to deal with the image matching problem involving the attenuation,fuzzy and chromatic aberration,and it is capable of improving the geometric shape precision of the reconstructed object.

stereomatching;image;variableweight

1007-6735(2017)03-0269-06

10.13255/j.cnki.jusst.2017.03.011

2016-12-26

国家自然科学基金仪器专项(2127013);国家自然科学基金资助项目(60968001,60768002);云南省自然科学基金资助项目(2011FZ079)

杨业(1991-),男,硕士研究生.研究方向:三维成像、图像处理.E-mail:1012114362@qq.com

李宏宁(1975-),男,副教授.研究方向:计算机视觉.E-mail:lihongning_ynnu@yahoo.com.cn

TP 391

A