文档介绍：10126—30713013
分类号密级
U D C 编号

论文题目
最佳邻域匹配图像恢复算
法的改进与并行化研究

研究生: 张艳燕
指导教师: 李文教授
专业: 计算机系统结构
研究方向: 并行处理与网格计算
所在学院: 计算机学院

2010 年 6 月 9 日
原创性声明

本人声明:所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究
成果。除本文已经注明引用的内容外,论文中不包含其他人已经发表或撰写过的研究成果,
也不包含为获得内蒙古大学及其他教育机构的学位或证书而使用过的材料。与我一同工作
的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。

学位论文作者签名: 指导教师签名:
日期: 日期:

在学期间研究成果使用承诺书

本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:内蒙古大学有权
将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘,
允许编入有关数据库进行检索,也可以采用影印、缩印或其他复制手段保存、汇编学位论
文。为保护学院和导师的知识产权,作者在学期间取得的研究成果属于内蒙古大学。作者
今后使用涉及在学期间主要研究内容或研究成果,须征得内蒙古大学就读期间导师的同意;
若用于发表论文,版权单位必须署名为内蒙古大学方可投稿或公开发表。

学位论文作者签名: 指导教师签名:
日期: 日期:
内蒙古大学硕士学位论文
最佳邻域匹配图像恢复算法的改进与并行化研究

摘要

现实世界中的通信链路经常会产生传输错误,传输错误常常导致图像的坏
损,而图像恢复可以通过差错掩盖(Error concealment)技术将这些坏损图像恢复
为人眼可接受的图像。最佳邻域匹配(Best Neighborhood Matching , BNM)算法
是一种优秀的图像恢复算法,它利用图像自身的信息冗余和块内相似性对受损
的图像像素进行恢复。BNM 算法能得到很高的图像恢复质量,但算法计算量
大,运行效率低,很难满足实时处理和大规模图像处理的要求。因此,本文从
串行和并行两个方面对 BNM 算法进行了优化,以提高算法效率。
本文首先在分析了 BNM 算法特点的基础上,提出了一种螺旋最佳邻域匹
配(Rotate-based BNM, R_BNM)算法。R_BNM 算法在为受损的坏块寻找最佳匹
配块时,改变了传统的顺序搜索模式,从受损块的周围开始按螺旋方式搜索,
尽快找到最佳匹配块,提前结束搜索。同时 R_BNM 算法还使用了动态阈值调
整的方法。在破坏率为 15%时,R_BNM 算法的加速比为 19,恢复后图像的
PSNR 值比使用原始 BNM 算法时大约降低了 1dB,但仍在可接受范围内,视
觉差异并不大。R_BNM 算法在破坏率越低时,加速比越高,恢复后图像的 PSNR
值越接近原始 BNM 算法。
其次,本文中在集群系统和 GPU 两种不同的并行平台上对 BNM 算法进
行了并行化研究。在集群系统上利用 MPI 实现了 BNM 算法的并行化算法,该
并行 BNM 算法在使用多个进程执行时,算法效率提高而恢复质量没有下降,
同时,实验证明该算法具有良好的可扩展性。
I
最佳邻域匹配图像恢复算法的改进与并行化研究
而在 GPU 上则利用了 CUDA 编程,同时使用了合并访问、共享存储器的
使用等优化手段,并且讨论和比较了这些优化手段的性能。同样在破坏率为
15%时,不对 BNM 算法的恢复过程做任何改动,加速比为 22,恢复后图像的
PSNR 值几乎与原始 BNM 算法完全相同。若缩小算法在恢复时的搜索范围,
加速比可达到 66,恢复后图像 PSNR 值虽略有下降,但不影响恢复质量。
本文中所进行的模拟实验显示,这三种方法都明显降低了 BNM 算法的运
行时间,大大提高了算法的效率,保证了图像的恢复质量。

关键字:图像恢复,差错掩盖,最佳邻域匹配,并行处理

II
内蒙古大学硕士学位论文
Research on Optimization and Parallelization of
Best Neighborhood Matching Image Restoration Algorithm
ABS