双线性插值算法及其并行实现

白香君

摘要：双线性插值算法是放大图像的一种有效算法，但是随着图像放大比例的增加，该算法的处理速度比较慢，所以基于这种现状，该文提出了双线性插值算法的一种并行实现方法，为高效快速的放大图像提供了解决方案。实验结果表明，并行后的算法能够有效的提高处理图像的速度和效率。

关键词：双线性插值；并行；提高；速度和效率

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）27-6494-03

Abstract： Bilinear interpolation algorithm is an efficient algorithm of enlarging image. But with the increase of image magnification， the processing speed of this algorithm is relatively slow. So based on this situation， this paper presents a parallel implementation of bilinear interpolation algorithm. It provides a solution for fast and efficient enlarging image. Experimental results show that the parallel algorithm can effectively improve the image processing speed and efficiency.

Key words： bilinear interpolation； parallel； improve； speed and efficiency

图像是人类获取和交换信息的主要来源，所以，图像处理必然贯穿人类生活和工作的方方面面，如航空航天技术、生物医学工程、军事公安等领域。另外图像处理技术有很多种，图像放大就是其中应用最广泛的一种，它经常被用于航拍图像放大、医学影像的放大、公安机关罪证图片的放大等。笔者下文中主要探讨了图像放大技术中的一种，即双线性插值技术，文章中首先分析了该算法的研究现状，然后探讨该算法的串行和并行实现方法，最后给出实验结果和结论。

1 双线性插值算法研究现状

人们创造了很多图像放大的算法，如最近邻插值法、双线性插值法、双三次插值法等。和其他算法相比较而言，双线性插值算法的实现原理比较简单，易于编程实现，并且这种算法处理之后的图像比较平滑，能够达到令人满意的效果，所以它的实用性很强，成为了一种被人们广泛使用的算法。

另外随着图像放大比例和复杂程度的增加，或者对图像处理速度要求比较高的时候，双线性插值算法的处理速度又不尽如人意，所以本文提出了双线性插值算法的并行实现，有效的提高了该算法的实现速度和效率。

2 双线性插值算法及其并行实现

2.1 双线性插值算法的实现原理

双线性插值算法的核心思想是利用与待插值像素点临近的四个像素点的像素值进行加权平均，最终求得待插值像素点的像素值，其实现原理图如下：

我们假设图像信息存储在一个nW*nH的二维数组里面，并且用n个进程处理该图像，那么令其中一个主进程负责初始化，发送处理前数据以及接收处理后数据等操作，剩下的n-1个从进程负责对图像数据进行插值并将插值后的数据发送给主进程等操作，多个进程就可以同时对图像进行处理，这样显然能够提高图像处理的速度。对于图像的边界处，该文采用重叠一行的方法来处理，即每个进程都多处理边界处一行的数据，这样就能保证多个进程处理的数据能够完全覆盖整个图像。又因为矩阵是按行存储的，所以按行将图像信息分配给n-1个进程的方法处理起来比较简单，但是这样并不一定能保证负载平衡，而且考虑到从进程处理数据时主进程闲置的情况，本算法规定分配给每个从进程nH/n行的数据，分配给主进程nH%n行的数据，这样在尽可能做到负载平衡的同时也提高了处理器的利用率。具体的实现流程如图2所示。

3 实验结果及数据分析

我们假设输入图像的尺寸为cinH *cInW，并且这里cinH *cInW=512*512，输出图像的尺寸为coutH*coutW，运行时间为t，加速比为Sn，效率为En，其中n表示进程数。

算法运行环境：实验室服务器上；

实现算法语言：C语言；

1） 该并行算法处理图像所需时间明显小于串行算法处理图像所需时间，即该并行算法可以有效降低处理图像的时间。

2） 在表1中，第2-4行可以看出：随着进程数的增加，图像处理的速度、加速比和效率都越来越大，说明在一定范围内，随着进程数增加，并行计算可以有效提高图像处理的速度和效率。但是当进程数为17时，图像处理的速度虽然提高了，但是效率却降低了，这是因为随着进程数增加，并行开销所占用的时间在总时间中的比例越来越大，而处理图像的时间在总时间中所占用的比例越来越小，以致效率降低了。也就是说，使用17个进程去按1：2的比例放大图像有些浪费CPU资源，所以我们要根据图像的放大比例适当选择进程数，节约资源的同时使并行效率达到最高。

3） 对比表1和表2，可以看出：表2中使用2、3、5个进程处理图像时，明显比表1中使用相同进程数处理图像的效率低。而表2中使用17个进程处理图像时的加速比和并行效率却比表1中的高。也就是说，随着图像放大比例的增加，我们需要更多的进程去处理图像，才能使并行效率达到最高。

4 结论

根据上述实验结果我们可以得出如下结论：

1） 本文提出的并行实现的双线性插值算法能够有效提高放大图像的速度，为高效快速的处理图像提供了解决方案。

2） 在处理图像的过程中，要根据图像放大的比例选择合适的进程数，当放大比例较小时，使用较少的进程去处理图像，就能有效提高图像处理的速度和效率。

3） 随着图像放大比例的增加，处理图像的进程数也随之增加，才能使该算法的加速比和并行效率达到最高。

参考文献：

[1] 都志辉. 高性能计算并行编程技术[M].北京：清华大学出版社，2001：15-37，81-88.

[2] 张林波，迟学斌. 并行计算导论[M].北京：清华大学出版社，2006：60-181，421-462.

[3] 严蔚敏，吴伟民. 数据结构[M].北京：清华大学出版社，2009：1-17，90-115.

[4] 谭浩强. C语言程序设计[M].北京：清华大学出版社，2006：158-300.

[5] （加拿大）帕科尔，景丽. 图像处理与计算机视觉算法及应用[M].2版.北京：清华大学出版社，2012.

[6] 求是科技. Visual C++数字图像处理典型算法及实现[M].北京：人民邮电出版社，2006.