基于圖像轉置算法的研究

王小芳 梁蕾

摘要：圖像轉置算法是數字圖像處理的重要領域之一，本文針對圖像轉置的前向映射方法和后向映射方法進行研究，并針對兩個算法的處理時間，處理圖像清晰度進行分析，然后對后向映射處理時間問題提出基于雙線性插值的后向映射方法，改進結果較傳統算法而言，轉置全過程所花費平均時間節省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.

【通聯編輯：唐一東】