基于LSC图像分割的LBP立体匹配算法

计算机工程

Computer Engineering

文章编号：1000-3428(2018)06-0259-04

文献标志码：A

2018年6月

June 2018

中图分类号：TP391

基于LSC图像分割的LBP立体匹配算法

杨艳，许道云

(贵州大学计算机科学与技术学院，贵阳550025)

要：在传统的全局立体匹配方法中，基于像素点的置信传播存在计算量大、单个像素点容易导致误差等缺点。为

此，在图像分割处理方法的基础上，提出基于简单线性迭代聚类图像分割的循环置信度传播（LBP)立体匹配算法。运 用LSC算法对图像进行分割，并利用一组平面模型进行建模，使每个分割区域至少对应一个视差平面标签。引人自适 应匹配代价计算视差，获取可靠匹配像素点，通过最小二乘法平面拟合进行视差平面估计，并运用LBP算法优化视差平面 标签。实验结果表明，与GC + 〇CC、MultiCamGC等算法相比，该算法具有较高的匹配精度，能够处理低纹理区域和遮挡 区域。

摘

关键词：立体匹配；简单线性迭代聚类；自适应匹配代价;平面拟合;循环置信度传播

中文引用格式：杨艳，许道云.基于LSC图像分割的LBP立体匹配算法[J].计算机工程，2018,44(6) :259-262,269. 英文引用格式：YANG Yan，XU Daoyun. LBP stereo matching algorithm based on LSC image segmentation [J]. Computer Engineering , 2018 ,44 (6) ： 259 -262,269.

LBP Stereo Matching Algorithm Based on LSC Image Segmentation

YANG Yan,XU Daoyun

(School of Computer Science and Technology,Guizhou University,Guiyang 550025,China)

[Abstract] In the traditional global stereo matching methods, pixel-based belief propagation has a large amount of computation and a single pixel point can easily cause errors. Therefore,on the basis of the image segmentation processing methods,a Loopy Belief Propagation ( LBP) stereo matching algorithm based on Simple Linear Iterative Clustering (SLIC) image segmentation is proposed. The image is segmented using the LSC algorithm and modeled using a set of plane models so that each segmentation region corresponds to at least one parallax plane label. The self-adapting matching cost calculation parallax is introduced to obtain reliable matching pixels, and the parallax plane estimation is performed by least squares plane fitting,and the LBP algorithm is used to optimize the parallax plane label. Experimental results show that compared with GC + occ, MultiGC and other algorithms, the algorithm has high matching accuracy and can handle low texture areas and occlusion areas.

[Keywords] stereo matching; Simple Linear Iterative Clustering ( SLIC); self-adapting matching cost; plane fitting; Loopy Belief Propagation (LBP)

DOI：10. 19678/j. issn. 1000-3428.0048455

〇概述

立体匹配是立体视觉领域的一个重要的研究 方向[1_2]，也是整个立体视觉系统中的核心部 分[3_5]，其目的是找出两幅或多幅不同视点图像中 像素的对应关系，这种关系可用视差来表示[6_8]。 视差是指当同一个三维空间点投影到不同的两台 或多台摄像机图像上时，对应点在图像上的位置 差。但是，由于形变、遮挡、低纹理区域误匹配等情 况的影响，到目前为止，立体匹配要获得较高精度 的视差图仍具有很大的挑战。文献[9]给出了有

关立体匹配算法的综述，通常，立体匹配方法可以 分为局部立体匹配方法和全局立体匹配方法。局 部立体匹配方法侧重匹配值的计算和匹配值的累 积。匹配值计算是指计算左右图像中两像素间的 相似度，由于受到噪声等因素的影响，依靠单个像 素的匹配值直接求取视差并不可靠，此时一般在某 个窗口中对匹配值进行积分来尽可能地消除噪声， 这个过程就称为匹配值累积。全局立体匹配方法 的核心是视差选择与优化。局部立体匹配方法采 用取最小匹配累积值所对应的视差（WTA)的方式 来选取视差，而全局立体匹配方法则是通过最小化

基金项目：国家自然科学基金（61762019 ,61262006 ,61462001);贵州大学研究生创新基金（20170S0) 作者简介：杨艳（1990 —），女，硕士研究生，主研方向为图像处理；许道云，教授、博士生导师。

收稿日期：2017-08-24 修回日期=2017-09-26 E-mail：dyxu@ gzu. edu. cn

260计算机工程2018年6月15日

能量方程来选取视差。全局立体匹配方法的研究 内容主要有两方面：一方面是能量方程的求解，当 前流行的能量方程优化方法有动态规划[传播[13_15]等；另一方面则是能量方程的构造通常是 1 ° _12 ]、置信 在方程中引人遮挡惩罚项、可视约束项等使立体匹 配算法能够更好地处理遮挡情况。

近年来，基于图像分割的立体匹配方法由于其 良好的性能受到广泛的关注，这类方法假设视差在 分割区域内平滑变化，而分割区域边界与视差边界 保持一致。基于图像分割的立体匹配方法通常有以 下4个步骤：图像分割，将图像分割成颜色均匀、大 小规则、分割边界与物体边界保持一致的不同分割 区域;视差计算，使用基于固定窗口的局部立体匹配 方法来确定分割区域内可靠的匹配像素点的视差； 平面拟合，获取与分割区域相对应的视差平面标签 集;优化视差平面，用贪心算法或图割优化算法近似 得到最优视差平面分配（即最优视差标签集）。

在上述研究的基础上，本文利用图像分割的处 理方法，提出一种基于简单线性迭代聚类图像分割 的循环置信度传播（Loopy Belief Propagation，LBP) 立体匹配算法。

1算法流程及处理环节分析

按照基于图像分割的立体匹配方法步骤，本文

提出基于LSC图像分割的LBP立体匹配算法，其算 法步骤如下：

算法1基于LSC图像分割的LBP立体匹配算法

步骤1对立体图像对进行图像分割。步骤2

计算视差，确定每个分割区域内的可靠

匹配像素点。

步骤3运用最小二乘法平面拟合进行视差平面 估计。

步骤4

运用LBP算法优化视差平面。

算法整体流程如下：1) 使用LSC算法对图像进行分割，将图像看作 所有分割区域的集合。2) 用一组平面模型对场景进行建模，每个分割

区域对应一个视差平面标签。3) 引人自适应匹配代价计算视差，获取可靠匹 配像素点。

4) 使用最小二乘法平面拟合进行视差估计。5) 利用LBP算法优化视差平面标签。本节给出算法每一个阶段的处理过程与分析， 第2节将对该算法进行实验验证。1.1

LSC图像分割

LSC算法将立体图像对分割成颜色均匀、大小

规则、分割边界与物体边界保持一致的分割区域。

本文算法选择LSC算法[16]对图像进行分割。

基于图像分割的立体匹配算法主要存在2个问 题:一是分割算法[17_18]速度太慢，严重影响算法整体 的实时性；二是分割区域不能保证其内部像素在同 一个视差平面，最终导致匹配准确率下降。为了保 证实际场景中视差在分割区域内平滑，深度不连续 只出现在分割区域边界的这一假设尽可能成立，本 文选用文献[16]应用于图像分割的LSC算法对图 像进行分割。

LSC算法是基于标准化割（normalized cuts)与 加权K-means的目标函数间的关系，提出的一种线 性迭代聚类超像素分割算法，其核心是在高维特征 空间中用简单的加权K-means聚类去化归一化割的 目标函数，较大程度上降低算法的复杂度，提高算法 的速度。另外，LSC分割算法的最大优点是考虑了 图像的边缘信息，因此，提高了图像分割的准确率。

1.2视差计算

在本文算法中，将实际场景表示成一组视差平 面标签的集合，每个视差平面由CpCpCj个参数唯 一确定，对于参考图像上的每个像素点（x，)0有d = Clx+C2y+c3。由于视差搜索空间巨大，通过像素级 的局部立体匹配和视差平面估计来选取一组能够代 表真实场景的视差平面，定义局部立体匹配的代价 计算和代价聚合窗口 [9]。本文引人相似性度量来进 行代价计算，最常见的相似性度量是像素强度的平 方值差（SD)和像素强度的绝对值差（AD)，这2种 方法均满足一致性约束假设。而其他像基于梯度和 非参数度量的相似性度量，在低分辨率的情况下，对 相机增益，偏置或非朗伯曲面的变化较为鲁棒。因 此，本文结合AD和基于梯度的度量，提出新的自适 应相似性度量，定义如下：

C(x,y,d) =(l-w) xCSAD(x,y,d) +w xCGRAD(x,y,d)

(1)

CSAD(x,y,d) = (ij) 1sN{x, y)

h-hii+dj) (2)

C_(x，;y，£〇 =

(ij) sINx {x,y)

yjAU) -yj2(i +dj) | +

(ij) s1Ny {x,y)

\\VyI1(iJ)-VyI2(i+dJ')\\ (3)

其中，w是一个常数参数，用来权衡CSAD和之间 的比例关系，(x，y)是以像素点（x，y)为中心的大小 为3x3的固定窗口，K(x，)〇是不包含最右一列像素 的固定窗口，％ (x，)〇是不包含最后一行像素的固定 窗口，、'分别是水平方向上和垂直方向上的梯度。 然后，利用交叉验证和winner-take-all策略，找到左右 匹配一致的像素点作为可靠的匹配像素点。

1.3视差平面估计

本文利用可靠的匹配像素点，采用平面拟合和视

第44卷第6期杨艳，许道云:基于LSC图像分割的LBP立体匹配算法261

差优化方法，获取代表实际场景的视差平面。尽管在第

2节中得到每个分割区域内可靠的匹配像素点，但仍存 在异常值对视差平面估计的影响〇因为最小二乘法对 异常值敏感且其解值鲁棒所以采用最直接的求解最小 二乘法[19]的方式来确定视差平面s同时，q、c2、c3 3个 参数单独分开来求解，这样能够减小误差，使本文的方 法更为鲁棒。首先，对每个分割区域，利用位于分割区 域内同水平线上的所有可靠匹配像素点来估计水乎 方向的斜率，将导数似/你存入列表并进行排序然后结 合高斯卷积，估计出水平方向上的斜率。其次，对于位 于分割区域内同一垂直方向上的所有可靠匹配像素点， 用同样的方法估计出垂直方向上的斜率。最后，根据确 定的水平方向上的斜率和垂直方向上的斜率得到对应 分割区域的视差值平面估计,

1.4视差平面优化

本文为每个分割区域寻找对应的最优视差平

面，将立体匹配问题转化为能量函数最小化的问题。 假设图像的每个分割区域为X，S E /?，分割区域对应 的视差平面标签为/，/U) ED，定义视差平面标签的 能量函数为：

_

=K/) + W/)

⑷

Edata(f) -s ^ R

lCSEG(s,f(s))

(5)

^smooth

(/) = E

了

A — ( \\

) (6)

其中，‘为所有相邻的分割区域的集合，A_(\\，~)为 相邻分割区域间的不连续性惩罚[15]。利用相邻分割区

域间信息间的循环置信度传播（LBP)[16]来近似最小化 视差平面标签能量函数，从而得到最优的视差平面 标签g

2实验结果与分析

本文在Middlebury测试平合上对算法进行测 试。图1分别是Middlebury立体匹配数据集中的 Tsukba、Venus、Teddy和Cones 4个立体图像对的左 图、右图及它们对应的理想视差图和实际匹配误差 图。其中，匹配误差图由视差的绝对误差大于一个 像素的所有像素点构成。图2分别是Middlebury立 体匹配数据集中的Tsukba、Venus、Teddy、Cones 4个 立体图像对的左图、右图及它们对应的理想视差图、 实际视差图和匹配误差图。其中，左图为原始图，右 图为本文算法的立体匹配实验结果。表1给出了本 文算法与其他算法的定量对比结果，针对图像非遮 挡区域、完整图像以及图像不连续区域，用视差值的 绝对误差大于一个像素的百分比作为衡量标准从 表1可以看出，本文算法优于其他算法，尤其在低纹 理区域和遮挡区域。为了使实验结果容易理解，单 独在Tsukba数据集上进行实验，图3是不同算法在 低纹理区域及遮挡区域的实验结果。其中，图3(a)

是Tsukba立体图像对的左图，图3(b)是Tsukba立 体图像对的右图，图3 ( a)中白色框a、b标注的部分 是图像重复纹理区域和低纹理区域，白色框c标注 的部分是存在遮挡的区域。算法实验得到的视差图 中，不同灰度区域代表物体在实际场景中所处的不 同平面，灰度越小表现为颜色越亮，代表物体离摄像 头越近，反之离摄像头越远。对应表1中的不同算 法，将算法得到的实际视差图与理想视差图进行对 比，实验结果表明，本文算法得到的视差图最接近于 理想视差图，其余算法得到的视差图误差较大，位于 同一视差平面的物体灰度却不一样，尤其图中用框 标注的低纹理区域和遮挡区域。其中，效果最差的 是RealtimeBP算法，其次是DP算法、MultiCamGc 算法和GC+occ算法g此外，DP算法得到的视差图 不仅效果差且出现明显横条纹6实验过程中算法的 参数固定不变，实验使用单个的CPU (3.20 GHz, i5)，不使用任何并行化、GPU以及专用硬件。实验 得到算法的计算时间为13 s〜24 s，其中，LSC图像 分割耗时最多。

國國卜|[^

⑷左图 （b)右图 （c)理想视差图 （d)匹配误差图

图1 Middlebury立体匹配数据集

⑻左图 （b)右图 （c)理想视差图（d)实际视差图（e)匹配误差图

图2本文算法实验结果

262

表1

Tsukba

算法

完整

本文货法GC +occ算法MultiCamGC算法DP算法

RealtimeBP 算濟

1. 121. 191.271.381.49

1.372.011.991.853.40

+迮续5.806.246.486.907.87

计算机工程

不同算法的Middlebury立体评估结果

Venus

非遮挡0. 181.2.790.710.77

^幣0.252. 193. 131. 191.90

不连续1.506.753.606. 139.00

非遮挡4.2111.2017.007.888.72

Teddy完整7.5017.4017.6013.3013.20

+迮续11.6019.8022.0018.6017.20

2018年6月15日

Cones

非遮捫2.485.3.3.974.61

完整7.8012.4011.809.7911.60

不连续7.3213.0012. 108.2612.40

⑷Tsukuba左图 （b)Tsukuba右图 （c)理想视差图 （d)本文算法

(e)GC+occ 算法 （f)MultiCamGc 算法 （g)DP 算法 （h)RealtimeBP 算法

图3不同算法在低纹理区域及遮挡区域的实验结果

learning-based confidence measures [ C ]//Proceedings

of Computer Vision and Pattern Recognition. Washington D. C. ,USA：IEEE Press,2015 ： 101-109.

3结束语

本文提出一种新的基于LSC图像分割的LBP

立体匹配算法。该算法对场景进行平面建模，利用

LSC超像素分割算法进行图像分割，使每个分割区

[6] 王新艳，潘巍，王月莲，等.基于全局差错能量函数

的立体匹配算法[J ].计算机工程，2017，43 ( 7 ):

244-249.

[7] 陈华，张志娟，，等.基于局部纹理特性和图像 分割的分步立体匹配[J].计量学报，2017,38 ( 1 ):

73-77.

域对应一个视差平面。通过引入自适应匹配代价计

算获取可靠匹配像素点，运用最小二乘法平面拟合 进行视差平面估计，并使用LBP算法优化视差平面。 实验结果表明，本文算法匹配精度高，能较好地处理 低纹理区域和遮挡区域9

参考文献

[1 ]

HOSNI A, BLEYER M, GELAUTZ M, et al. Local stereo matching using geodesic support weights [ C! ]// Proceedings of IEEE International Conference on Image

Processing. Washington D. C. , USA： IEEE Press,2010： 2093-2096.

[2 ]

GEIGER A,ROSER M, URTASUN R. Efficient large- scale stereo matching [ C ]//Proceedings of Europe Conference on Computer Vision. Berlin, Germany： Springer-V erlag, 2010 ： 25 -3 8.

[3 ]

YANG Q. Stereo matching using tree filtering [ I]. IEEE Transactions on Pattern Analysis & Machine Intel­ligence ,2015 ,37 (4) ： 834-842.

[4 ]

MOZEROV M G,van D W J. Accurate stereo matching by two-step energy minimization [ J ]. IEEE Transactions on Image Processing,2015 ,24(3) ：1153-1165.

[5 ]

PARK G,YOON K J. Leveraging stereo matching with

[8 ][9 ]

汤春明，蒋昂.基于跨尺度代价聚合的改进立体匹

配算法[J] •计算机工程,2016，42( 11) :272-276 ,280.SCHARSTEIN D, DANIEL R, SZELISSKI R, et al. A taxonomy and evaluation of dense two-frame Stereo correspondence algorithms [ J ]. International Journal of Computer Vision,2002,47(1-3) ：7-42.

[10] HU T, QI B, WU T, et al. Stereo matching using

weighted dynamic programming on a single-direction four-connected tree [ J ]. Computer Vision & Image Understanding, 2012,116 (8) ： 908 -921.

[11] LIU J,LI C,MEI F,et al. 3D entity-based stereo matching

with ground control points and joint second-order smoothness prior[J]»Visual Computer,2015,31(9) ：1253-1269.

[12] BAEK E T,HO Y S. Occlusion and error detection for

stereo

matching

and

hole-filling

using

dynamic

programming [ J ]. Electronic Imaging ,2016(5) ： 1 -6.

[13] 刘忠艳，周波，张兴华，等.一种基于置信度传播的 立体匹配算法[I〕.自动化与仪器仪表，2010 ( 1 ):

111-113.

(下转第269页）

第44卷第6期

[5

] 李成龙，钟

凡

，马

昕

闵秋莎，刘能，陈雅婷，等:基于面部特征点定位的头部姿态估计

，等.基于卡尔曼滤波和随机

269

部姿态识别方法[J].信号处理，2〇l3,29 (10): 1354-1361.

[16] 占艳，韦昌法，萍，等.基于Hough变换的虹膜

图像预处理研究[J].软件导刊，2〇16, 15 (10): 167-169.

[17]

张

静

回归森林的实时头部姿态估计[J].计算机辅助设计 与图形学学报,2017 ,29(12) :2309-2316.

[6] 吴福华，汪同庆.利用深度信息检测驾驶员头部姿态[J].

烟台大学学报（自然科学与工程版），2017,30(2) :155- 159,166.

[7 ]

PAPAZOV C,MARKS T K, JONES M. Real-time 3D head pose and facial landmark estimation from depth images using triangular surface patch features [ C ] // Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D. C. , USA： IEEE Press,2015：4722 ^730.

[8 ]

LI Xinghua, CHEN Haiyang,CHEN Qinglei. A head pose detection algorithm based on template match [ C]// Proceedings of the 5 th International Conference on Advanced Computational Intelligence. Washington D. C., USA：IEEE Press,2012：673-677.

[9] 郭知智，周前祥，柳忠起.基于自适应线性回归的头部

姿态计算[J].计算机应用研究，2〇16, 33 (10): 3181-3184.

[10]

MABingpeng, CHAI Xiujuan, WANG Tianjiang. A novel feature descriptor based on biologically inspired feature for head pose estimation [ J ]. Neurocomputing, 2013,115(8) ：1-10.

[U][12]

陈书明，陈美玲.头部姿态估计技术研究综述[J].泉 州师范学院学报，2015 ,33(6) :78-85.RAHAYFEH A A, FAEZIPOUR M. Eye tracking and head movement detection： a state-of-art survey [J]. IEEE Journal of Translational Engineering in Health and 210-212.Medicine,2013,1(1) ：

[13]

CHUN J,KIM W. 3D face pose estimation by a robust real time tracking of facial features [ J ]. Multimedia Tools & Applications ,2016,75 (23) ：1-16.

[14] 刘春生，常发亮，陈振学，等.基于AAM和T型结构的人

脸3D姿态估计[J].计算机工程与应用，2012,48(25): 163-167.

[15] 陈

喆

，杨兵兵，殷福亮.使用眼睛定位的平面角度头

[23] [22] [21] [19] [18]

，叶学义，张维笑，等.

一

种新的挖掘眼部结构

特征的人眼精定位方法[J].计算机工程与应用， 2016,52(12) ：158-162,

ZIA M A, ANSARI U, JAMIL M, et al. Face and eye detection in images using skin color segmentation and circular

Hough

transform

[ C ] //Proceedings

of

International Conference on Robotics and Emerging Allied Technologies in Engineering. Washington D. C., USA：IEEE Press,2014：211-213.

FITRIYANI N L, YANG C K, SYAFRUDIN M. Real­time eye state detection system using Haar cascade classifier

and

circular

Hough

transform [ C ]//

Proceedings of the 5th Global Conference on Consumer Electronics. Washington D. C. ,USA： IEEE Press,2016： 1-3.

[20]

毕雪芹，惠婷.基于肤色分割与Adaboost算法的人 脸检测[J].国外电子测量技术，2015 ,34(12) :82-86.VIOLA P, JONES M. Rapid object detection using a boosted cascade of simple features[ C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington D. C. ,USA： IEEE Press,2003：511-518.

HSU R L, ABDEL-MOTTALEB M,JAIN A K. Face detection in color images [ J ]. IEEE Transactions on

Pattern Analysis and Machine Intelligence,2002,24(5)：

696-706.

DERKACHD, RUIZ A, SUKNO F M. Head pose estimation based on 3-D facial landmarks localization and regression [ C ]//Proceedings of IEEE International Conference on Automatic Face & Gesture Recognition. Washington D. C. ,USA：IEEE Press,2017 ：820-827.

编辑顾逸斐

(上接第262页）[14]李晶皎，马

Patchmatch及 切片采样粒子置信度传播的立体匹配算法[J].东北

利

，王爱侠，等.基于改进

USA：IEEE Press,2015： 1356-1363.

[17]

张

勇

，袁家政，刘宏哲，等.基于结构张量的GmbCut

图像分割算法[J].计算机工程，2017,43 ( 8 ) :258- 265,271.

[18] 孙劲光，赵欣.一种基于耦合对象相似度的阈值分

割算法[J].计算机工程，2016 ,42(10) :255-260.

[19] 李

伟

，孙元超，李宗春，等.

一

大学学报（自然科学版），2016,37(5) :609-613.

[15 ]

HU H P,ZHU M. Fast stereo matching based on seed pixel propagation [ J ]. Guangxue Jingmi Gongcheng/ optics and Precision Engineering,2015 ,23(3) ：887-4.

[16]

LI Z,CHEN J. Superpixel segmentation using linear spectral clustering [ C ]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D. C.,

种改进的最小二乘平

编辑索书志

面拟合算法[J].测绘科学，2017，42( 1) : 15-19.