基于图像转置算法的研究

王小芳 梁蕾

摘要：图像转置算法是数字图像处理的重要领域之一，本文针对图像转置的前向映射方法和后向映射方法进行研究，并针对两个算法的处理时间，处理图像清晰度进行分析，然后对后向映射处理时间问题提出基于双线性插值的后向映射方法，改进结果较传统算法而言，转置全过程所花费平均时间节省2.16倍。

关键词：图像转置;前向映射;后向映射;双线性插值

中图分类号：TP317        文献标识码：A

文章编号：1009-3044（2020）23-0185-04

Abstract：Image transposition algorithm is one of the important areas of digital image processing. This paper studies the forward mapping method and backward mapping method of image transposition， and analyzes the processing time and image sharpness of the two algorithms. Then， a backward mapping method based on bilinear interpolation is proposed for the processing time of backward mapping. Compared with the traditional algorithm， the average time spent transposing the entire process is saved 2.16 times.

Key words： image transpose; forward mapping; backward mapping; bilinear interpolation

1 引言

数字图像又称数码图像，是将模拟图像数字化而得，数字图像以像素为基本元素，采用数字计算机或数字电路进行存储和处理[1]。而数字图像处理是将图像信号转换成数字信号并利用计算机对其进行处理。一般对图像进行处理要达到提高图像的视觉质量，提取图像中包含的某些特征或特殊信息以及图像数据变换、编码和压缩三方面目的。而图像数据变换是为便于图像存储、传输和处理。特别是图像转置，是实现对不同格式图片、非标准图片进行处理的重要手段之一。本文对图像转置的前向映射和后向映射算法进行研究，并针对算法的不足提出改进方法。

2 算法研究

2.1 前向映射

前向映射过程是将原图像进行遍历，计算每个像素点旋转后的坐标，再将此坐标平移到输出图像中进而得到包含旋转后图像的输出图像[2]。

具体体现为：先选取合适的坐标系，采用一个多维数组存储图像数据（即像素点），数组以左上角为原点（0，0），向右列数增加，向下行数增加，图像的宽在列坐标轴上取值，高在行坐标轴上取值，如图1左[3]。然后对图像坐标系以原点为旋转中心逆时针旋转90度，与平面直角坐标系对应，如图1右，将行坐标轴对应x轴，列坐标轴对应y轴，得到的结果。其中，图像的高是在x轴上取值，而宽在y轴上取值。

如图2，将图像旋转θ°，本文为了简化作图，采用一条线代替图像。

由上图可得三个方程，如式（1）、式（2）、式（3）所示。

则利用（5）式可以计算出旋转后的坐标，（6）式可计算出在原图像中的坐标。

由于旋转后的图像是倾斜的，如果输出图像与原图像大小一样就会有一部分的图像丢失，所以限定输出图像的大小至少为旋转后图像的外接矩形，如图3所示。

由上图容易得到式（7），如下。

由于计算结果通常是浮点数，而图像的宽和高都是整数，考虑到图像的完整性，则对输出图像宽和高结果值向上取整[4]。然后得到了輸出图像的信息，但其中的像素都是默认的黑色，不包含旋转后的图像。接下来将旋转后图像的像素对应到输出图像里。

分别计算旋转后图像和输出图像的中心点的坐标，两坐标相减得出偏移量，然后遍历旋转后的图像，将每个像素的坐标加上此偏移量得到在输出图像中的坐标，直接赋值，遍历完后得到最终输出图像。

2.2反向映射

2.2.1 方向映射原理

反向映射的思想是假设输出图像已包含旋转后的图像，然后将输出图像你想旋转回去，使其与原图像进行重合[5]。采用的是逆向思维方式，从输出图像出发，将旋转后图像的像素点坐标反向旋转得到在原图像中的坐标，从而解决前向映射输出图像的像素点不能与图像准确对应的问题。

坐标系中，由于数组索引机制，原图像和输出图像皆在第一象限，因而需要将输出图像平移到旋转后图像的外接矩形的位置，这个偏移量与前向映射中偏移量相同，之后旋转输出图像（即遍历输出图像），将每个像素的坐标加上此偏移量，利用（6）式计算出逆向旋转后的坐标，然后查看此坐标是否在原图像的范围内，如果在则在原图像中进行插值运算，得到结果并赋值给当前像素，反之，忽略，直至遍历完后输出结果图像。

2.2.2特殊角度的处理

之前的算法中可以处理图像任意角度的旋转，但由于涉及三角函数，计算得到的坐标值几乎是浮点数，不仅降低运算效率，且需要进行插值后才能确定准确的坐标[6]。对于特殊的角度（0°、90°、180°、270°、360°），这些角度可直观看出旋转后仍与原图像同样大小，且旋转后图像不是倾斜的，旋转前后的像素坐标可以直接简单的映射，如果仍使用之前算法将大大降低效率，因此对于此类角度则采用特殊角度处理方法。

对于0°和360°，旋转后图像与原图像完全重合，可看作是没有进行旋转，算法可优化为对0°和360°不进行处理，且延伸为对360°的任意整数倍角度都不处理。

对于180°，由原点对称性，采用式（8）进行计算。

由式（8）可得，将旋转后的图像移位到输出图像，对对应的像素赋值即可。偏移量为x方向的偏移量为原图像的高，y方向的偏移量为原图像的宽。

对于90°，则根据（5）式得到计算处理式（9）。

由式（9）可得，将旋转后的图像移位到输出图像，对对应的像素赋值。x方向的偏移量为原图像的宽，y方向的偏移量为0。

270°理同90°，坐标对应关系如式（10）所示。

由式（10）可得，将旋转后的图像移位到输出图像，对对应的像素赋值。x方向的偏移量为0，y方向的偏移量为原图像的高。

最后进行整理，90°、180°和270°的处理在方法上相同，仅有偏移量不同。算法中可以优化为：通过坐标变换得到旋转后图像的坐标值，然后加上偏移量得到输出图像的坐标值，最后进行赋值。延伸至对加上360°的任意整数倍角度做相同处理。

2.4 双线性插值

双线性插值（Bilinear Interpolation）法是利用待求像素四个邻象素的灰度在两个方向上作线性内插得到待求像素[7]。如图4，待求像素点P的坐标为（x，y），其周围四个邻像素分别为Q11（x1，y1）、Q21（x2，y1）、Q12（x1，y2）和Q22（x2，y2）。

首先，在X方向上进行两次线性插值，得到R1、R2，如式（11）所示。

然后，在Y方向上以R1和R2再进行一次线性插值，如式（12）所示。

结合图像，将一个像素的边长设为单位1，将么（11）式和（12）式可以分别简化为式（13）和式（14）。

3 算法分析与改进

3.1前向映射与反向映射分析

本文选取1972年11月期的《花花公子》杂志中的Lena图像作为原图像，对图像转置的前向映射、反向映射算法进行验证，验证结果如图5、图6和图7所示。

从上图可知，前向映射的成像结果有很多噪点，并且呈规律性。而反向映射的成像效果要优于前向映射，反向映射图像没有噪点出现，但细节上存在一些锯齿比较明显。

3.2 传统算法运算速度分析

本文分别对前向映射（forward）、反向映射（reverse）和PIL库中图像的Rotate方法（Image.roate）在转置过程中的24°、30°、90°、180°、270°以及360°角的处理全过程的处理速度进行分析，并对结果时间保留小数点后4位，分析结果如表1所示。

由表1所知，转置360°角所花费的时间是所有转置角度中所花费时间最短的。前向映射的处理时间在24°角和100°角这特殊角度上，时间明显比后向映射短，在处理正常90°、180°、270°及360°角上，前向映射的处理时间明显比后向映射所花费的时间长，因而，在处理正常角度的处理时间上后向映射拥有绝对的处理优势，在处理特殊角度上，前向映射处理时间具有优势，此外，不管是前向映射还是后向映射，其处理速度都远不及PIL的Rotate方法，究其原因是：首先，PIL库本身使用C语言编写，但接口面向Python，在调用PIL库时运行的是已编译好的系统底层运行库，其效率自然是使用纯Python编写程序所花费的时间短。其次，实现的算法本身存在许多导致效率低下的地方，如在插值處理以及坐标变换时存在大量的浮点数运算，图像遍历的时间复杂度会随图像分辨率以其平方倍的数量增加，处理时间会大大提升。

3.3改进算法与分析

针对以上提出的程序中大部分的运行时间花费在进行坐标变换和插值运算问题，本文提出基于双线性插值的后向映射算法。对于在遍历图像的过程中，首先是坐标变换，由于有三角函数参与需要进行浮点运算，而浮点运算远慢于整数运算，再加上乘法运算慢于加法，所以需要减少此处的浮点运算。通常用两层循环来遍历图像，由（5）、（6）式可知变换后的X或Y值都需要变换前的X和Y值同时参与计算，考虑到第二层循环运行时，第一层的变量值x保持不变，可以将涉及x的一部分运算在第一层计算好，然后进行插值运算，而由（15）式可知对于同一个待求像素点系数项是不变的，且像素是多通道的，每个通道都要进行插值，因此将（15）式中的系数项，以及每个通道中坐标相同的部分提前计算好，然后再遍历通道进行双线性插值计算，然后得到处理结果。

经改进算法处理后，对算法的处理时间进行分析，对处理时间取小数点后4位，分析结果如表2所示。

由表1和表2对比可知，改进算法对24°、90°、100°、180°、270°、360°角度的转置处理上，其处理时间有大大提升，处理的平均时间提升约2.16倍，处理时间复杂度有大大降低。

4 结论

本文针对图像转置的前向映射和后向映射算法进行研究与分析，并针对算法的处理时间进行改进，改进后算法的运行时间在一定程度上得到降低，但对于处理后图像的清晰度问题，并未涉及，这是后期研究的方向及目标。

参考文献：

[1] 赵娜.量子图像压缩制备与信息隐藏[D].北京：北京工业大学，2017.

[2] 王春明.Delphi下图像快速转置算法的研究[J].包钢科技，2015，41（2）：49-52.

[3] 杨勇.异构多核SoC中存储与转置结构研究[D].合肥：合肥工业大学，2013.

[4] 张立，周凡，胡银丰.面向高速数码印花机的实时图像数据转置方法[J].计算机工程与应用，2014，50（6）：35-39，60.

[5] 鲍胜荣，周海斌.SAR实时成像高效矩阵转置研究和实现[J].现代雷达，2013，35（3）：24-27.

[6] 沈煌辉，王贞松，郑为民.面向图像转置和分块处理的一种高效内存访问策略[J].计算机研究与发展，2013，50（1）：188-196.

[7] Rafael C.Gonzalez，Richard E.Woods.数字图像处理[M].阮秋琦，阮宇智，译.北京：电子工业出版社，2017.

[8] Kenneth A.Reek.C和指针[M].徐波，译.北京：人民邮电出版社，2008.

[9] Wesley Chun著 孙波翔，李斌，李晗译.Python核心编程[M].北京：人民邮电出版社，2016.

[10] 罗成，陈加洋，陈耀武.基于多核处理器与FPGA的高速数码印花系统[J].计算机工程与应用，2015，51（17）：265-270.

【通联编辑：唐一东】