基于圖像轉(zhuǎn)置算法的研究

王小芳 梁蕾

摘要：圖像轉(zhuǎn)置算法是數(shù)字圖像處理的重要領(lǐng)域之一，本文針對圖像轉(zhuǎn)置的前向映射方法和后向映射方法進(jìn)行研究，并針對兩個算法的處理時間，處理圖像清晰度進(jìn)行分析，然后對后向映射處理時間問題提出基于雙線性插值的后向映射方法，改進(jìn)結(jié)果較傳統(tǒng)算法而言，轉(zhuǎn)置全過程所花費平均時間節(jié)省2.16倍。

關(guān)鍵詞：圖像轉(zhuǎn)置;前向映射;后向映射;雙線性插值

中圖分類號：TP317? ? ? ? 文獻(xiàn)標(biāo)識碼：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 引言

數(shù)字圖像又稱數(shù)碼圖像，是將模擬圖像數(shù)字化而得，數(shù)字圖像以像素為基本元素，采用數(shù)字計算機(jī)或數(shù)字電路進(jìn)行存儲和處理[1]。而數(shù)字圖像處理是將圖像信號轉(zhuǎn)換成數(shù)字信號并利用計算機(jī)對其進(jìn)行處理。一般對圖像進(jìn)行處理要達(dá)到提高圖像的視覺質(zhì)量，提取圖像中包含的某些特征或特殊信息以及圖像數(shù)據(jù)變換、編碼和壓縮三方面目的。而圖像數(shù)據(jù)變換是為便于圖像存儲、傳輸和處理。特別是圖像轉(zhuǎn)置，是實現(xiàn)對不同格式圖片、非標(biāo)準(zhǔn)圖片進(jìn)行處理的重要手段之一。本文對圖像轉(zhuǎn)置的前向映射和后向映射算法進(jìn)行研究，并針對算法的不足提出改進(jìn)方法。

2 算法研究

2.1 前向映射

前向映射過程是將原圖像進(jìn)行遍歷，計算每個像素點旋轉(zhuǎn)后的坐標(biāo)，再將此坐標(biāo)平移到輸出圖像中進(jìn)而得到包含旋轉(zhuǎn)后圖像的輸出圖像[2]。

具體體現(xiàn)為：先選取合適的坐標(biāo)系，采用一個多維數(shù)組存儲圖像數(shù)據(jù)（即像素點），數(shù)組以左上角為原點（0，0），向右列數(shù)增加，向下行數(shù)增加，圖像的寬在列坐標(biāo)軸上取值，高在行坐標(biāo)軸上取值，如圖1左[3]。然后對圖像坐標(biāo)系以原點為旋轉(zhuǎn)中心逆時針旋轉(zhuǎn)90度，與平面直角坐標(biāo)系對應(yīng)，如圖1右，將行坐標(biāo)軸對應(yīng)x軸，列坐標(biāo)軸對應(yīng)y軸，得到的結(jié)果。其中，圖像的高是在x軸上取值，而寬在y軸上取值。

如圖2，將圖像旋轉(zhuǎn)θ°，本文為了簡化作圖，采用一條線代替圖像。

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

則利用（5）式可以計算出旋轉(zhuǎn)后的坐標(biāo)，（6）式可計算出在原圖像中的坐標(biāo)。

由于旋轉(zhuǎn)后的圖像是傾斜的，如果輸出圖像與原圖像大小一樣就會有一部分的圖像丟失，所以限定輸出圖像的大小至少為旋轉(zhuǎn)后圖像的外接矩形，如圖3所示。

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

由于計算結(jié)果通常是浮點數(shù)，而圖像的寬和高都是整數(shù)，考慮到圖像的完整性，則對輸出圖像寬和高結(jié)果值向上取整[4]。然后得到了輸出圖像的信息，但其中的像素都是默認(rèn)的黑色，不包含旋轉(zhuǎn)后的圖像。接下來將旋轉(zhuǎn)后圖像的像素對應(yīng)到輸出圖像里。

分別計算旋轉(zhuǎn)后圖像和輸出圖像的中心點的坐標(biāo)，兩坐標(biāo)相減得出偏移量，然后遍歷旋轉(zhuǎn)后的圖像，將每個像素的坐標(biāo)加上此偏移量得到在輸出圖像中的坐標(biāo)，直接賦值，遍歷完后得到最終輸出圖像。

2.2反向映射

2.2.1 方向映射原理

反向映射的思想是假設(shè)輸出圖像已包含旋轉(zhuǎn)后的圖像，然后將輸出圖像你想旋轉(zhuǎn)回去，使其與原圖像進(jìn)行重合[5]。采用的是逆向思維方式，從輸出圖像出發(fā)，將旋轉(zhuǎn)后圖像的像素點坐標(biāo)反向旋轉(zhuǎn)得到在原圖像中的坐標(biāo)，從而解決前向映射輸出圖像的像素點不能與圖像準(zhǔn)確對應(yīng)的問題。

坐標(biāo)系中，由于數(shù)組索引機(jī)制，原圖像和輸出圖像皆在第一象限，因而需要將輸出圖像平移到旋轉(zhuǎn)后圖像的外接矩形的位置，這個偏移量與前向映射中偏移量相同，之后旋轉(zhuǎn)輸出圖像（即遍歷輸出圖像），將每個像素的坐標(biāo)加上此偏移量，利用（6）式計算出逆向旋轉(zhuǎn)后的坐標(biāo)，然后查看此坐標(biāo)是否在原圖像的范圍內(nèi)，如果在則在原圖像中進(jìn)行插值運算，得到結(jié)果并賦值給當(dāng)前像素，反之，忽略，直至遍歷完后輸出結(jié)果圖像。

2.2.2特殊角度的處理

之前的算法中可以處理圖像任意角度的旋轉(zhuǎn)，但由于涉及三角函數(shù)，計算得到的坐標(biāo)值幾乎是浮點數(shù)，不僅降低運算效率，且需要進(jìn)行插值后才能確定準(zhǔn)確的坐標(biāo)[6]。對于特殊的角度（0°、90°、180°、270°、360°），這些角度可直觀看出旋轉(zhuǎn)后仍與原圖像同樣大小，且旋轉(zhuǎn)后圖像不是傾斜的，旋轉(zhuǎn)前后的像素坐標(biāo)可以直接簡單的映射，如果仍使用之前算法將大大降低效率，因此對于此類角度則采用特殊角度處理方法。

對于0°和360°，旋轉(zhuǎn)后圖像與原圖像完全重合，可看作是沒有進(jìn)行旋轉(zhuǎn)，算法可優(yōu)化為對0°和360°不進(jìn)行處理，且延伸為對360°的任意整數(shù)倍角度都不處理。

對于180°，由原點對稱性，采用式（8）進(jìn)行計算。

由式（8）可得，將旋轉(zhuǎn)后的圖像移位到輸出圖像，對對應(yīng)的像素賦值即可。偏移量為x方向的偏移量為原圖像的高，y方向的偏移量為原圖像的寬。

對于90°，則根據(jù)（5）式得到計算處理式（9）。

由式（9）可得，將旋轉(zhuǎn)后的圖像移位到輸出圖像，對對應(yīng)的像素賦值。x方向的偏移量為原圖像的寬，y方向的偏移量為0。

270°理同90°，坐標(biāo)對應(yīng)關(guān)系如式（10）所示。

由式（10）可得，將旋轉(zhuǎn)后的圖像移位到輸出圖像，對對應(yīng)的像素賦值。x方向的偏移量為0，y方向的偏移量為原圖像的高。

最后進(jìn)行整理，90°、180°和270°的處理在方法上相同，僅有偏移量不同。算法中可以優(yōu)化為：通過坐標(biāo)變換得到旋轉(zhuǎn)后圖像的坐標(biāo)值，然后加上偏移量得到輸出圖像的坐標(biāo)值，最后進(jìn)行賦值。延伸至對加上360°的任意整數(shù)倍角度做相同處理。

2.4 雙線性插值

雙線性插值（Bilinear Interpolation）法是利用待求像素四個鄰象素的灰度在兩個方向上作線性內(nèi)插得到待求像素[7]。如圖4，待求像素點P的坐標(biāo)為（x，y），其周圍四個鄰像素分別為Q11（x1，y1）、Q21（x2，y1）、Q12（x1，y2）和Q22（x2，y2）。

首先，在X方向上進(jìn)行兩次線性插值，得到R1、R2，如式（11）所示。

然后，在Y方向上以R1和R2再進(jìn)行一次線性插值，如式（12）所示。

結(jié)合圖像，將一個像素的邊長設(shè)為單位1，將么（11）式和（12）式可以分別簡化為式（13）和式（14）。

3 算法分析與改進(jìn)

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

本文選取1972年11月期的《花花公子》雜志中的Lena圖像作為原圖像，對圖像轉(zhuǎn)置的前向映射、反向映射算法進(jìn)行驗證，驗證結(jié)果如圖5、圖6和圖7所示。

從上圖可知，前向映射的成像結(jié)果有很多噪點，并且呈規(guī)律性。而反向映射的成像效果要優(yōu)于前向映射，反向映射圖像沒有噪點出現(xiàn)，但細(xì)節(jié)上存在一些鋸齒比較明顯。

3.2 傳統(tǒng)算法運算速度分析

本文分別對前向映射（forward）、反向映射（reverse）和PIL庫中圖像的Rotate方法（Image.roate）在轉(zhuǎn)置過程中的24°、30°、90°、180°、270°以及360°角的處理全過程的處理速度進(jìn)行分析，并對結(jié)果時間保留小數(shù)點后4位，分析結(jié)果如表1所示。

由表1所知，轉(zhuǎn)置360°角所花費的時間是所有轉(zhuǎn)置角度中所花費時間最短的。前向映射的處理時間在24°角和100°角這特殊角度上，時間明顯比后向映射短，在處理正常90°、180°、270°及360°角上，前向映射的處理時間明顯比后向映射所花費的時間長，因而，在處理正常角度的處理時間上后向映射擁有絕對的處理優(yōu)勢，在處理特殊角度上，前向映射處理時間具有優(yōu)勢，此外，不管是前向映射還是后向映射，其處理速度都遠(yuǎn)不及PIL的Rotate方法，究其原因是：首先，PIL庫本身使用C語言編寫，但接口面向Python，在調(diào)用PIL庫時運行的是已編譯好的系統(tǒng)底層運行庫，其效率自然是使用純Python編寫程序所花費的時間短。其次，實現(xiàn)的算法本身存在許多導(dǎo)致效率低下的地方，如在插值處理以及坐標(biāo)變換時存在大量的浮點數(shù)運算，圖像遍歷的時間復(fù)雜度會隨圖像分辨率以其平方倍的數(shù)量增加，處理時間會大大提升。

3.3改進(jìn)算法與分析

針對以上提出的程序中大部分的運行時間花費在進(jìn)行坐標(biāo)變換和插值運算問題，本文提出基于雙線性插值的后向映射算法。對于在遍歷圖像的過程中，首先是坐標(biāo)變換，由于有三角函數(shù)參與需要進(jìn)行浮點運算，而浮點運算遠(yuǎn)慢于整數(shù)運算，再加上乘法運算慢于加法，所以需要減少此處的浮點運算。通常用兩層循環(huán)來遍歷圖像，由（5）、（6）式可知變換后的X或Y值都需要變換前的X和Y值同時參與計算，考慮到第二層循環(huán)運行時，第一層的變量值x保持不變，可以將涉及x的一部分運算在第一層計算好，然后進(jìn)行插值運算，而由（15）式可知對于同一個待求像素點系數(shù)項是不變的，且像素是多通道的，每個通道都要進(jìn)行插值，因此將（15）式中的系數(shù)項，以及每個通道中坐標(biāo)相同的部分提前計算好，然后再遍歷通道進(jìn)行雙線性插值計算，然后得到處理結(jié)果。

經(jīng)改進(jìn)算法處理后，對算法的處理時間進(jìn)行分析，對處理時間取小數(shù)點后4位，分析結(jié)果如表2所示。

由表1和表2對比可知，改進(jìn)算法對24°、90°、100°、180°、270°、360°角度的轉(zhuǎn)置處理上，其處理時間有大大提升，處理的平均時間提升約2.16倍，處理時間復(fù)雜度有大大降低。

4 結(jié)論

本文針對圖像轉(zhuǎn)置的前向映射和后向映射算法進(jìn)行研究與分析，并針對算法的處理時間進(jìn)行改進(jìn)，改進(jìn)后算法的運行時間在一定程度上得到降低，但對于處理后圖像的清晰度問題，并未涉及，這是后期研究的方向及目標(biāo)。

參考文獻(xiàn)：

[1] 趙娜.量子圖像壓縮制備與信息隱藏[D].北京：北京工業(yè)大學(xué)，2017.

[2] 王春明.Delphi下圖像快速轉(zhuǎn)置算法的研究[J].包鋼科技，2015，41（2）：49-52.

[3] 楊勇.異構(gòu)多核SoC中存儲與轉(zhuǎn)置結(jié)構(gòu)研究[D].合肥：合肥工業(yè)大學(xué)，2013.

[4] 張立，周凡，胡銀豐.面向高速數(shù)碼印花機(jī)的實時圖像數(shù)據(jù)轉(zhuǎn)置方法[J].計算機(jī)工程與應(yīng)用，2014，50（6）：35-39，60.

[5] 鮑勝榮，周海斌.SAR實時成像高效矩陣轉(zhuǎn)置研究和實現(xiàn)[J].現(xiàn)代雷達(dá)，2013，35（3）：24-27.

[6] 沈煌輝，王貞松，鄭為民.面向圖像轉(zhuǎn)置和分塊處理的一種高效內(nèi)存訪問策略[J].計算機(jī)研究與發(fā)展，2013，50（1）：188-196.

[7] Rafael C.Gonzalez，Richard E.Woods.數(shù)字圖像處理[M].阮秋琦，阮宇智，譯.北京：電子工業(yè)出版社，2017.

[8] Kenneth A.Reek.C和指針[M].徐波，譯.北京：人民郵電出版社，2008.

[9] Wesley Chun著 孫波翔，李斌，李晗譯.Python核心編程[M].北京：人民郵電出版社，2016.

[10] 羅成，陳加洋，陳耀武.基于多核處理器與FPGA的高速數(shù)碼印花系統(tǒng)[J].計算機(jī)工程與應(yīng)用，2015，51（17）：265-270.

【通聯(lián)編輯：唐一東】