《基于并行计算的图像灰度匹配1.doc》由会员分享，可在线阅读，更多相关《基于并行计算的图像灰度匹配1.doc（5页珍藏版）》请在三一办公上搜索。
1、精品论文基于并行计算的图像灰度匹配1宗亮，邬延辉 宁波大学信息科学与工程学院，浙江宁波（315211） E-mail: kevzong摘要：灰度匹配是数字图像处理中一项重要的技术，以往的匹配方法虽然精确度高，但计算量大、时间长。针对这一问题，将基于 MPI(Message Passing Interface)的集群并行处理思 想引入到图像灰度匹配中，对待匹配的图像采用数据分割处理，结合并行处理的一般步骤对 图像灰度匹配进行并行建模、实现，对传统的图像灰度匹配算法进行并行化改进，试验结果 表明并行化处理能显著地缩短灰度匹配时间，达到较高的加速比和效率。通过对图像灰度匹 配的并行化处理，验证了并行
2、计算的高性能。关键词：MPI；并行计算；灰度匹配；集群 中图分类号：TP3111. 引言在数字图像处理中，图像匹配是根据已知一幅图像在陌生图像中寻找对应子图像的过 程，它在计算机视觉、航空遥感、医学图像、飞行器制导等领域具有广泛的应用。目前，图 像匹配算法很多，基于灰度匹配算法简单、精度高，但计算量大、对旋转形变等敏感1。基 于特征匹配方法计算量小，对灰度变化、形变及遮挡等有较好的适应性，但它取决于特征提 取的质量，匹配精度不是很理想2。基于神经网络和遗传算法具有良好的并行性和非线性全 局作用，良好的容错和记忆能力，但计算代价高、参数选取对结果影响大34。其中经典的 灰度相关算法具有匹配精度高
3、，易于硬件实现等特点，但计算量大、速度慢，应用受到限制。现今针对灰度相关匹配改进的算法较多，如灰度归一化相关匹配，基本上是从相似性度 量的函数着手进行算法的改进5，但很多是基于串行处理。随着近几年硬件的飞速发展，使 得传统的大型工作站可由多微机的集群系统代替，从而使得计算量大的问题可由后者解决。 在图像处理的研究中，并行处理的引入极大地缩短了计算时间，成为图像处理中的一种重要 手段4。本文基于灰度相关匹配进行并行化处理、改进，提高运算速度。2. 灰度相关匹配匹配的图像称为模板，记为T (m, n) ，大小为 N N ，被匹配的陌生图像为 S (m, n) ， 大小为 M M ，其中陌生图像被模
4、板覆盖的部分称为子图，记 S (m, n)i , j ，在陌生图像中起始位置为 (i, j) ，匹配的过程是由模板从源图像左下角开始逐点匹配。灰度相关匹配常见的方法有平均绝对误差，平均平方差，归一化相关等算法5。本文讨论的并行处理采用平均平 方差作为试验的基本算法。公式如下：- 5 -N ND(i0, j0 ) = m=1 n =12S (m, n)ij T (m, n)（1）其中 D(i0 , j0 ) 为平均平方差，上式展开为：D ( i0 , j 0 ) =NN m = 1 n = 1S 2 ( m , n ) + T 2 ( m , n ) 2 S ( m , n )ij T ( m
5、, n ) （2）1本课题得到宁波大学科研基金（200582，XK200583）的资助。从（1）式可知，当 D(i0 , j0 ) 最小时，T (m, n) 与 S (m, n)ij 匹配精度最高。由（2）式知前二项为模板对应陌生图像子图的平方和以及模板的平方和。S (m, n)ij T (m, n) 为模板与子图的互相关，为使 D(i0 , j0 ) 最小， 为：S (m, n)ij T (m, n) 须最大，则子图与模板的相似性测度定义N N T (m, n) S (m, n)ij N NR(i, j) = m =1 n =1 （3）ij m=1 n=1S 2 (m, n)R(i, j)
6、值越大，相似度越高。上式标准化后为：N N T (m, n) S (m, n)ij R(i, j) = m =1 n =1 N NN N（4）ijT 2 (m, n) S 2 (m, n)m=1 n =1m=1 n=1由上可知，当 R(i, j) 取最大值是， D(i0 , j0 ) 最小，此时，最精确的匹配位置为 (i, j) 。3. 并行处理并行处理的环境需要软、硬件的搭配以及网络的支持，近几年，硬件价格的降低、性能 的提高，软件性能的改善以及网络传输速度的提高，使得并行处理的环境易于构建。3.1 MPIMPI 是一个消息传递接口标准，用于开发基于消息传递的并行程序，其目的是为用户提 供一
7、个实际可用的、可移植的、高效和灵活的消息传递接口库6。MPI 支持 C 和 FORTRAN， 使得它成为现今最流行的并行程序开发标准。MPICH 是 MPI 一个重要的实现，它是由美国 ARGONNE 国家实验室和 MSU 共同开发 维护的。目前最新的版本是 MPICH2-1.0.7，它支持最新的 MPI2 标准，可以从相关网站免费 获得，按照下载提供的文档安装。3.2 集群系统近些年，计算机硬件的高速发展以及网络性能的不断改善，使得并行计算从传统的超级 计算机转移到由一组高性能节点（可以是个人计算机）构成的集群系统。所谓的集群系统是 一组独立的计算机的集合，它们通过网络进行连接，每个计算机可
8、以单独作为一个计算机也 可以协同其它计算机表现成为一个单独的集中的计算资源，供并行任务使用7。由于 Linux 的开源和稳定性，使得它成为构建集群系统的最佳操作系统。选择一台计算 机为主节点，其余为分节点，集群系统的构建大致分为：1、NFS 配置，2、NIS 配置，3、 RSH 配置，具体过程参考相关资料78。最后用 lamboot 命令启动集群系统中各个节点。3.3 并行模型及实现并行环境下必须考虑待处理问题并行处理的可行性。对问题的并行求解必须将问题的并 行特性充分体现出来。结合一般并行模型的建立9，根据图像的数据特点可分析如下：（1）对图像灰度匹配串行处理的分析，找出计算量最大的部分，分
9、析可知可采用分割数据块的方法进行并行处理。（2）将计算量最大的部分分块，发送数据到计算节点。根据计算结果和数据分块的关 系决定采用并行处理中的主从模式。（3）各计算节点进行计算，发送计算结果到主节点。（4）主节点接受计算结果得出问题的解，对比单机处理时间。 因为图像的存储是一个二维数组，因此灰度相关匹配对像素值的逐点处理可以并行处理。过程如下：（1）灰度相关匹配计算量最大的是求 R，则可以将陌生图像分成 p 块，每块有连续 r行向量，r= M 。 p （2）将 p 块数据用 MPI_Send（）发送到标记为 0，1， p-1 的 p 个计算节点，各块求 R 是独立的与分块数据无关，故采用主从模
10、式。0 节点为主节点，负责发送 p 块数据、接 受计算结果，并计算出第 0 块的结果。由于求 R 是完全搜索，故 0 到 p-2 计算节点需传递 r+N-1 行。（3）计算分节点 1,2,3 p-1 用 MPI_Recv（）接受从主节点发送过来的数据,其中节点1,2,3p-2 接受 r+N-1 行,最后的分节点 p-1 接受M-(p-1)*r行。各节点计算 R，并将结果保 存，用 MPI_Send（）发送给主节点。(4)主节点用 MPI_Recv（）接受计算结果并比较 R，得出最精确匹配位置。4. 实验结果及分析Tppp并行计算性能常由加速比 S 和并行效率 f 来衡量，其中 S = TspS
11、 p， f p = p，Ts 为单节点运行时间（即串行运行时间），Tp 为 p 个节点运行的时间， p 为节点数。本文试验操 作系统为 Red Hat 9.0，集群系统由 4 台电脑构建，配置为：（1）主节点 CPU:Celeron 2.00GHz， 内存为 384M。（2）其余分节点 CPU:P4 1.5GHz，内存为 256M。MPICH 为 MPICH-1.2.7。作为对照，陌生图像大小分别采用 256 256 像素、512 512 像素、1024 1024 像素，模板 为 32 32 像素、64 64 像素。(a)陌生图像(b)模板 32 32(c) 模板 64 64图 1 待匹配图像
12、和模板表 1 模板为 32 32 时间（单位：秒）表 2 模板 64 64 时间（单位：秒）节点节点图像大小1234图像大小1234256 2561.530.830.590.42256 2564.312.741.621.23512 5126.814.712.531.91512 51223.8613.428.647.181024 102432.5118.0312.019.341024 1024116.2972.5948.6334.73表 3 模板 32 32 的加速比和并行效率( S p / f p )表 4 模板 64 64 的加速比和并行效率( S p / f p )节点节点图像大小234图
13、像大小234256 2561.84/0.922.59/0.863.64/0.91256 2561.57/0.792.67/0.893.48/0.87512 5121.45/0.722.69/0.893.56/0.89512 5121.78/0.892.76/0.923.32/0.831024 10241.80/0.902.71/0.903.48/0.871024 10241.60/0.802.39/0.803.35/0.83图 2 模板为 32 32 的加速比图 3 模板为 64 64 的并行效率在图 2、图 3 中，a、b、c 分别对应陌生图像为 256 256 像素、512 512 像素、
14、1024 1024像素。图 2 显示的加速比随节点数的增加近似线性增加，图 3 显示并行效率接近 1。实验R(i, j) 值都为 1。理论上结点数趋近无穷大时加速比也线性地趋近无穷大，并行效率为 1， 但实际过程中结点之间相互传递数据和结果耗费了一定的时间。不难看出在集群环境中，结 点数增加时，计算时间相对单机将大大减少，这就是并行计算的优势所在。总体上并行处理 相对串行（单节点）处理可以明显减少计算时间，提高计算速度。5. 结束语本文基于并行计算的灰度图像匹配可以很好解决计算时间长问题，匹配精度高。可以作 为以后并行处理图像匹配的参考，也可作为视频图像进行并行化处理的基础。但是该算法在 计算
15、量非常大的情况下，仍然需要较长的时间，以后的工作可以围绕对算法改进、优化展开， 然后进行并行化处理。参考文献1 Fadlallah G, Lavoie M. Parallel computing environments and methods A. International Conference onParallel Computing in Electrical EngineeringC. 2000 ,8. 2-7.2 陈沈轶, 钱徽, 等. 模板图像匹配中互相关的一种快速算法J. 传感技术学报, 2007,20(6):1325-1329.3石争 浩 , 黄士坦 , 冯亚 宁 , 等 .
16、 遗传算 法和 BP 算法相结合进 行图像匹配 J. 武汉大学 学 报,2003,36(3):91-94.4徐建斌 , 洪文 , 吴戎 . 一种基于距离变换 和遗传 算法的遥感图像匹 配算法 J. 电子与信息学 报,2005,27(7):1009-1012.5张贵明 . 基于 PVM 平 台的图 像模板 匹配并 行化 处理 J. 贵 州师范 大学 学报 ( 自然 科学版 ),2005,23(4):92-96.6 都志辉. 高性能计算之并行编程技术MPI 并行程序设计M. 北京:清华大学出版社,2001.7 陈国良, 安虹, 陈崚. 并行算法实践M. 北京:高等教育出版社,2004. 8 车静光
17、. 微机集群组建、优化和管理M. 北京:机械工业出版社,2004.9 吕捷, 张天序, 张必根. MPI 并行计算在图像处理方面的应用J. 红外与激光,2004,33(5):496-499.Image Gray Scale Matching Based on Parallel ComputingZong Liang, Wu YanhuiFaculty of Information Science and Engineering, Ningbo University, Ningbo（315211）AbstractGray scale matching in digital image proce
18、ssing is an important technology. Although the previousgray scale matching methods can get high precision, these solutions spend much time on massive computing tasks. For this question, MPI (Message Passing Interface) is introduced. The idea of cluster parallel processing is taken in image gray scal
19、e matching. Data division processing is applied to source image gray scale matching. With the general steps of parallel processing, image gray scale matching parallel modeling and implementation are finished. Traditional image gray scale matching algorithm is improved by parallel computing. Experime
20、nt results show that parallel processing can shorten the time of gray scale matching significantly, and high speedup and efficiency can be acquired. It is validated that the parallel processing of the image gray scale matching can reach high performance.Key words: MPI; parallel computing; gray scale matching; cluster
