引用本文
许岩岩, 陈辉, 刘家驹, 袁金钊. CELL处理器并行实现立体匹配算法. 吉林大学学报(工学版), 2017, 47(3): 952-958
XU Yan-yan, CHEN Hui, LIU Jia-ju, YUAN Jin-zhao. Cell processor stereo matching parallel computation. Journal of Jilin University Engineering and Technology Edition, 2017, 47(3): 952-958  
Doi:10.13229/j.cnki.jdxbgxb201703036
Permissions
Copyright©2017, 吉林大学学报编辑部
版权所有.吉林大学学报编辑部
CELL处理器并行实现立体匹配算法
许岩岩1,2, 陈辉1, 刘家驹1, 袁金钊1
1.山东大学 信息科学与工程学院, 济南 250100
2.麻省理工学院 土木与环境工程系,剑桥 02139
陈辉(1963-),女,教授,博士.研究方向:计算机视觉.E-mail:huichen@sdu.edu.cn

作者简介:许岩岩(1987-),男,在站博士后.研究方向:计算机视觉,城市计算.E-mail:yanyanxu@mit.edu

基金项目:国家自然科学基金重点项目(61332015); 山东省自然科学基金项目(ZR2013FM032)
摘要

提出了适应于IBM CELL BE并行处理器的两种立体匹配算法——动态规划(DP)算法和置信传播(BP)算法的实现方案。改进了BP算法中的数据成本计算方法,采用重叠窗方法保持BP算法原有的匹配效果。实验证明,基于CELL处理器的并行实现极大地提高了生成视差图的运算速度。针对室外场景噪声较大的特点,提出采用Sobel边缘检测和Residual算子对图像进行预处理,实验结果表明,该方法改善了生成视差图的效果。本文算法在低成本硬件设备平台上提升了立体匹配技术的计算效率,在汽车自动和辅助驾驶系统、多媒体视觉技术的硬件一体化中具有重要的应用价值。

关键词: 计算机应用; 人工智能; CELL芯片; 视差图; 计算机视觉; 并行计算
中图分类号:TP391 文献标志码:A 文章编号:1671-5497(2017)03-0952-07
Cell processor stereo matching parallel computation
XU Yan-yan1,2, CHEN Hui1, LIU Jia-ju1, YUAN Jin-zhao1
1.School of Information Science and Engineering, Shandong University, Ji'nan 250100,China
2.Department of Civil & Environmental Engineering, Massachusetts Institute of Technology, Cambridge 02139,USA
Abstract

This paper presents an efficient parallel implementation of belief propagation and dynamic programming algorithms on an IBM CELL BE processor (Sony Playstation3) that speeds up stereo image matching. Overlapping windows and improved data cost with pyramid computation are adopted for implementation of belief propagation algorithms. Considering that real-world images are typically degraded by various types of noise, differing exposures and changes in light etc, Sobel edge and residual operator are used for image pre-processing to improve the stereo matching results. The proposed method has important application on hardware unification of automatic driving binocular computer vision together with multimedia visual technique.

Key words: computer application; artificial intelligence; CELL processor; disparity map; computer vision; parallel computation
0 引言

立体匹配是将现实场景中同一物体在不同视点(摄像机)投影图像中的像素点对应起来。计算机双目技术采用两台平行摄像机模拟人类视觉系统, 使用立体匹配算法在左、右图像中寻找3D环境中物体的对应点。基于计算机视觉技术的自动和辅助驾驶系统通过计算对应点在不同视点图像中的位置差异(视差)感知周围环境, 探测前方障碍物的位置和距离[1]。然而基于全局信息的立体匹配算法运算量巨大, 传统计算架构的串行计算方法无法满足实时应用需要。近年来随着多核处理器的普及, 并行立体匹配算法成为国内外的研究热点。颜瑞[2]采用基于CUDA的GPU并行架构对立体匹配算法进行加速。李金奎[3]采用普通的Intel多核架构, 基于OpenMP对置信传播算法进行改进, 缩短了运算时间。

本文提出采用IBM公司开发的具备特殊计算架构的CELL BE处理器, 实现对传统算法的并行改进。由于提供了SIMD和向量编程等高级计算功能, CELL BE非常适用于需要极高密度海量计算和数据吞吐的应用。通过与传统CPU的比较, 展示了该架构对置信传播(BP)[4]和动态规划(DP)[5]立体匹配算法的加速效果。本文的创新之处在于:首次将DP算法在CELL BE架构上并行实现; 采用两种新方法对BP算法进行并行化改进, 并与串行算法计算结果进行比较[6]; 同时, 本文采用Sobel和Residual算子对图像进行预处理[7, 8], 有效地降低了室外场景中的不均匀光照对立体匹配算法的影响。

1 Cell broadband engine(CELL BE)

与普通PC编程不同, BP和DP算法在CELL BE上实现需要考虑CELL的特殊结构。由于SPE只有256 kB本地存储, 这对BP算法是非常严峻的挑战。图1为CELL芯片的总体结构。

图1 CELL BE总体结构Fig.1 Architecture of CELL BE

本文采用一台索尼公司出产的装有CELL BE芯片的游戏机PlayStatio3作为测试用的主机。CELL架构芯片由一个Power架构的控制单元PPE以及8个能够执行SIMD操作的协处理器单元SPE(只有6个提供给用户做计算使用, 另外2个PS保留), 所有计算单元通过高速环形数据总线— EIB(Element interconnect bus)相连。

PPE是一个64 bit兼容PowerPC 架构的两路并发多线程处理器, 主频为3.2 GHz。包含一个32 kB的L1 Cache(32 kB数据cache和32 kB指令cache); 512 kB的L2 Cache。如图2所示, 它支持SIMD和浮点处理, 也支持DMA和存储映像输入/输出(MMIO)。PPE在CELL中的地位就像指挥部, 一方面为操作系统的运行提供环境; 另一方面指挥其他硬件工作, 如为SPE分配任务, 启停线程。

图2 PPE架构图Fig.2 PPE block diagram

图3 SPE架构图Fig.3 SPE block diagram

SPE是协处理器单元, 主频为3.2 GHz, 采用128 bit精简指令集, 特别适用于大数据量和高计算密度的SIMD应用。SPE架构如图3所示, 是Cell BE的真正优势所在, 每颗Cell芯片有8个SPE, 但在PlayStation中, 只有6个开放给第三方开发使用。SPE只能访问本地存储(LS), 它通过DMA方式访问主存(Main memory), 由DMA负责将指令和数据搬到LS。这种方式能够有效地减小内存读写延迟对处理器利用率的影响。

为了协调多颗芯片之间的工作, CELL BE提供几种消息机制供SPE与PPE之间通信使用。其中最常用的是mailbox, 每个SPE单元都有一个四接口32 bit接入信箱和两个单接口32 bit输出信箱。信箱机制常用来协调不同SPE之间的工作, SPE只需向PPE的输入信箱发送特定消息, 就可以使PPE中断操作, 使PPE短暂中止特定的SPE线程。此外, 信箱机制还能够“ 唤醒” 或者“ 沉睡” 空闲的SPE。

2 测试数据

用于测试的图像Tsukuba选自Middlebury大学的立体图像数据库, 图像规格为384× 288[9], 作为算法的综合测试数据; 同时, 用测试车辆(HAKA1)在新西兰拍摄的室外场景(图像规格为640× 480)作为测试图像, 如图4所示。这些图像中含有各种噪声, 包括光线变化、模糊、镜面和内部反射等。

图4 测试图像Fig.4 Test image sequences

3 基于CELL架构的并行算法

首先分析DP和BP算法的并行潜力, 然后提出两种算法在CELL多核芯片上并行实施方案。

3.1 动态规划实施方法

由于DP算法逐行处理图像, 特别适合CELL架构处理方式。每行由一个线程处理, 每个SPE处理一个线程。如果图像有N行, 在整个图像处理过程中, 每个SPE要执行N/6行。虽然DMA传输数据的限制是每行数据必须少于16 kB, 但足够用来处理本文中的测试图像。并行实现的算法步骤如下所示。

Step1 PPE创建SPE上下文, 并启动SPE线程。

Step2 PPE将数据从硬盘读入到Main memory中。

Step3 PPE通过使用消息机制Mailbox, 将要选取数据的Main memory地址传递给SPE。

Step4 SPE通过直接内存访问方式(DMA), 将尚未计算的数据从主存下载到自己的局部存储(LS)中。步骤如下:

Step4.1 六个SPE同时启动6线程, 计算图像对应点的差值, 即同时有6行图像在进行计算。每一行在计算时都采用矢量编程的方法进一步加强并行度。

Step4.2 将运算结果回写至主存中。

Step4.3 取下一行像素, 返回步骤Step4.1迭代运算。

Step5 PPE负责将计算得到的视差图输出至外围存储设备。

在编程实现时, 采用双缓存(Double cache)技术进一步对算法加速。双缓存类似诊所候诊室, 病患大部分时间都是在等待叫号, 为了提高效率会在等待时做一些其他工作。CELL处理器同样适用这种方法, 在编写代码时, 可以一次申请两块内存, 一块用来处理数据; 另一块利用这段时间采用DMA方式传输数据。另外, 为了避免上文Step4在抽取数据时遗漏或重复, 使用Mailbox和MFC机制同步协调不同的SPE。

DP算法极易受噪声影响, 沿行传播匹配误差, 形成条纹瑕疵。为此, 考虑采用一种空间域传递方法DP-spatial(DPs)修正算法[10]。fy和fy-1分别为当前计算的行和先前计算的行的视差图。hy修正后的视差图如下:

hy=1-λ1fy+λ1fy-11

式中:λ 1为修正参数。

图5为两种算法的测试结果。在Cell处理器上图像会被SPE等分, 6个SPE各处理一部分, 且各部分同时进行。因此修正效果仅限每一块内, 并不是特别理想。

图5 两种算法在CELL芯片上计算的视差图Fig.5 Disparity image by DP and DPs on CELL

3.2 置信传播的并行实现

BP算法是一种信息在网络中传播的迭代推理算法, 能有效解决计算机视觉领域的早期视觉问题。本文将Felzenszwalb等[4]提出的基于普通PC的BP立体匹配算法改进并移植到CELL并行系统中。BP算法是二维能量最小化问题[11], 其能量方程为:

Ef=∑p∈PDpfp+∑(p, q)∈NVfp-fq（2）

式中:Dp(fp)为像素p在视差为fp时的代价函数, 本文采用对应点像素灰度值之差的绝对值作为匹配代价; V(· )为指示函数, 即当fp=fq时, V=0, 否则, V=d, 其中d为常量, 用来控制代价D的上限, 本文设置d=20; P代表图像中所有像素点; N为像素图像中上、下、左、右4个方向像素集合; fp为像素p的视差值; f表示一幅完整的视差图, 整个计算的目标是为每一个像素点分配一个视差值, 使式(2)代表的能量值最小[7]。

文献[6]提出采用红黑格法和金字塔法两种方法加速BP算法。红黑格法将像素点分割成黑点和红点, 在第t个迭代阶段, 信息从黑点传送到红点, 红点只接受信息不发送信息; 在t+1个迭代阶段信息从红点传送到黑点, 同样黑点只接受红点发送的信息不发送信息, 所以在每个迭代阶段只需计算一半信息传输量。

金字塔算法兼顾运算速度和运算精度, 在满足精度要求的同时极大地加快了运算速度。本文使用的是通用高斯金字塔, 金字塔的上一层像素点数量是下一层像素点数量的1/4, 缩短了像素点之间的距离, 使信息传播得更快速、高效, 将上一层的迭代结果传给下一层作为迭代的初始值。这样可以尽快完成尽可能多的迭代次数, 算法的全局性也越好。

BP算法以高密度运算为代价获得高精度视差图。因此本文采用CELL芯片做并行化处理。

3.2.1 方法一

由于每个SPE只有256 kB局部存储单元, 而DMA每次只能传递16 kB的数据, 所以SPE无法处理一幅完整图像。为此, 对图像进行切割, 每一块有 M^行 N^列, 每个像素点采用20 byte进行信息传递, 每一个视差值都需要窗口的空间存放数据, 窗口大小由式(3)决定:

4︷float×5×nM^N^︷image_data< LDMA（3）

式中:LDMA为DMA的运量, 限制为16× 1024 bytes。

从式(3)得出窗口的大小取决于视差值的范围。以Tsukuba为例, 若设定视差范围值n=16, 则 M^=32, N^=16比较合适。

CELL BE提供了3种方法(MailBox, DMA和notice)进行SPE和PPE之间的通信。MailBox只有32 bit, 用来为DMA传送数据块地址, 或者传递一些特殊的标号, 通知PPE唤醒或关闭哪个SPE。将整幅图裁成不连续的图像对, 每对图像块之间有部分重叠区域, 重叠窗口如图6所示。

图6 重叠窗口示例Fig.6 Sample of overlapping windows

3.2.2 方法二

由图7可见, 将整个图像分解为小图块进行处理效果并不理想, 所以考虑采用其他并行处理方式。不同于方法一将图片分成若干块, 方法二将BP整个运行过程分成计算数据成本、生成金字塔、信息传递[6]和计算深度(视差)4个阶段, 如图8所示。

图7 Tsukuba的结果Fig.7 Results on Tsukuba

图8 BP算法流程Fig.8 Sketch of BP procedure on CELL BE

由图8可见, PPE将数据发送到数个SPE之后, 再将中间阶段结果传回主存储单元。方法二可以最大程度地保证图像的完整性, 这对全局算法非常重要。

与文献[6]相比, 本文的第1点贡献是数据成本计算方法。将图像在Main memory中的地址分配给多个SPE, SPE根据地址取的像素数量s由式(4)决定:

2s+n︷image_data+sn︷data_cost×4︷float< LDMA（4）

解得：

s< LDMA-4n4n+2（5）

通过式(5)可见, 当视差值n=16时(Tsukuba的最大视差), s取值192较为合适, 对于真实室外环境图像n=32(更远距离对于周围环境探测没有意义), s取值为160。本文使用Mailboxes机制协调6个SPE确保不遗漏也不重复计算。

本文的第2点贡献是构建金字塔的方法。当使用金字塔算法加速时, 在完成第l层最后一次迭代计算时, 将上、下、左、右4个方向的值的地址通过Mailboxes发送到4个SPE中, SPE从Main memory中取值而后生成l-1层的数据, 再将结果返回。SPE一次取像素点的数量满足式(6):

s< minLDMA-4n4n+2, Lwidthl（6）

这样可以同时构建4个金字塔, 从而大大缩短了计算时间。

由图9可见, 并行算法与传统串行算法相比, 结果无明显差别。BP算法与DP算法(图5)相比, 生成的视差图更精确、细节反映更细腻。进一步实验, 采用方法二对HAKA1拍摄的图片进行处理。直接采用原始图像计算, 结果并不理想。原因是室外实拍图像受到各种噪声的影响, 尤其当两台摄像机光照条件不同时, 同一物体得到的图像灰度值不同, 从而造成误匹配。通过分析大量的实验数据发现, 尽管物体的灰度值不同, 但是物体的边缘轮廓并不随光照变化而改变。可见, 光噪声更多地影响图像的低频部分而较少影响高频部分, 故采用Sobel边缘检测和Residual算子对图像进行预处理, 保留对光照变化不敏感的高频成分。

图10(a)为经Sobel算子处理后的图像, 作为BP算法的输入处理对象[7]。图10(b)为残差图[8], 指从一幅原始图像中减去自身模糊图像而得到的锐化图像, 自身模糊图像是由平滑原图像得到的。文献[8]的实验结果表明, 在众多方法中, 效果最好的是均值滤波法, 故选择3× 3均值滤波器。均值滤波器近似一个优质低通滤波器, 所得残差图像含有高频部分用来进行匹配运算(即纹理部分), 可以通过迭代选择留下的信息量。

图9 BP并行算法结果和实际视差图Fig.9 BP result when following strategy 2 and ground truth

图10 图像预处理Fig.10 Image preprocessing

4 实验结果

采用具备CELL处理器的PlayStation3(PS3)作为实验平台。该平台提供1个3.2 GHz的Cell处理器、6个SPEs(只用了其中4个)和1个PPE, 运行在fedora操作系统之上, 同时还使用了IBM公司提供的CellSDK 3.1[12]工具箱。图11为原始图像、经Sobel和Residual预处理之后使用BP算法的结果, 通过对比可见采用两种方法预处理之后, 效果明显改善。

图11 BP不同图像上运行的结果Fig.11 BP results when using different image data

对于DP算法, 采用主频3 GHz的传统PC处理一幅图像需要4.3 s; 采用CELL并行处理, 在使用4个SPE时需要0.09 s, 6个SPE时需要0.06 s, 即1 s可以处理超过15帧。在CELL处理器与传统PC主频大致相等的情况下, 性能提升70倍以上。对于BP算法, 用标准的Tsukuba图像(384× 288), 整幅图像采用五层金字塔, 每层迭代5次, 最大视差为16, 输入图像的平滑常数σ 为0.7; truncation-of-discontinuity-costs参数为1.7; truncation-of-data-cost参数为15; 数据成本权重λ 为0.07。按照以上设置在普通PC上BP算法的运行时间为25.2 s, 在CELL上采用方法一运行为4.1 s, 方法二运行为2.1 s。与传统串行算法相比, 性能提升了12倍。理论上在6个SPE上采用SIMD方式消耗的时间应该是实验值的两倍, 这主要得益于本文在PS上采用了适量的编程技术和恰当的内存管理方式(比如double buffer)。需要注意的是, 与文献[6]相比, 本文算法改进效果更明显(本文速度提升12倍, 文献[6]提升7倍)。文献[6]并没有给出算法详细的参数设置, 所以很难直接进行评价。

BP算法中方法二的效果远优于方法一, 如图7和图9所示。需要注意的是, 在PS中SPE只有256 kB本地内存, DMA一次只能传送16 kB内存, 这制约了计算性能。

5 结束语

采用SIMD理念对DP和BP立体匹配算法进行并行化改进, 采用重叠窗口、改进的数据成本计算和金字塔构建方法, 在多核处理器CELL上对本文算法进行了实验验证。实验结果表明:采用Sobel边缘检测和Residual算子对输入图像进行预处理改善了输出结果; 与传统架构的CPU相比, 本文算法大幅提高了运算速度。本文算法对低成本视觉方法的实现有重要应用价值, 也为在移动计算平台上实现自动和辅助驾驶系统以及多媒体视觉技术奠定了基础。本文所采用的并行化分析方法同样适用于其他计算机视觉算法。

The authors have declared that no competing interests exist.

参考文献
[1] Khan W, Klette R. Stereo accuracy for collision avoidance for varying collision trajectories[C]//IEEE Intelligent Vehicles Symposium, Gold Coast City, Australia, 2013: 1259-1264. [本文引用:1]
[2] 颜瑞. 基于CUDA的立体匹配及去隔行算法[D]. 杭州: 浙江大学信息与电子工程学院, 2010.
Yan Rui. The stereo matching and de interlacing algorithm based on CUDA[D]. Hangzhou: College of Information and Science and Electronic Engineering, Zhejiang University, 2010. [本文引用:1]
[3] 李金奎. 一种分层置信传播立体匹配并行算法[J]. 通信技术, 2012, 45(7): 57-61.
Li Jin-kui. Parallel HBP algorithm for stereo matching[J]. Communications Technology, 2012, 45(7): 57-61. [本文引用:1]
[4] Felzenszwalb P F, Huttenlocher D P. Efficient belief propagation for early vision[J]. International Journal of Computer Vision, 2006, 70(1): 41-54. [本文引用:2]
[5] Ohta Y, Kanade T. Stereo by two-level dynamic programming[C]//Proceedings of the 9th International Joint Conference on Artificial Intelligence, Los Angeles, USA, 1985: 120-1126. [本文引用:1]
[6] Lai Chi-Hua, Hsieh Kun-Yuan, Lai Shang-hon, et al. Parallelization of belief propagation method on embedded multicore processors for stereo vision[DB/OL]. [2015-12-26]. http://pllab.cs.nthu.edu.tw/act/ESWeek2008/ESWeek_files/estimedia2008-kyhsieh.pdf. [本文引用:2]
[7] Guan S S, Klette R. Belief-propagation on edge images for stereo analysis of image sequences[J]. Lecture Notes in Computer Science, 2008, 4931: 291-302. [本文引用:3]
[8] Vaudrey T, Klette R. Residual images remove illumination artifacts![J]. Lecture Notes in Computer Science, 2009, 5748: 472-481. [本文引用:2]
[9] Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[DB/OL]. [2015-12-29]. http://vision.middlebury.edu/stereo/taxonomy-IJCV.pdf. [本文引用:1]
[10] Klette R. Concise Computer Vision[M]. London: Springer, 2014. [本文引用:1]
[11] Sun Jian, Shum Heung-yeung, Zheng Nan-ning. Stereo matching using belief propagation[J]. IEEE Trans Pattern Analysis Machine Intelligence, 2003, 25: 787-800. [本文引用:1]
[12] IBM. CBE programmer's guide v3. 1[DB/OL]. [2015-12-30]. http://www.ibm.com/developerworks/power/cell. [本文引用:1]