基于智能手機平臺的積分圖像并行算法優化與實現

蔣睿 張素文 汪創

摘要 積分圖像算法是虛擬現實等技術中的一個重要組成部分，廣泛應用于現實生活中。智能手機平臺對虛擬現實應用具有實時性的要求，而目前的研究主要集中在桌面平臺上的并行加速。本文針對智能手機對運行速度要求高的特點，在對兩種前綴加法進行詳細分析的基礎上，提出一種基于移動智能手機的積分圖像并行算法。該算法利用OpenCL框架在Android平臺上實現了積分圖像算法的并行設計。實驗結果表明，積分圖像并行算法實現了算法運行效率的提升。

【關鍵詞】積分圖像 OpenCL 并行

對于一幅灰度的圖像，積分圖像中的任意一點（x，y）的值是指從圖像的左上角這個點的所構成的矩形區域內所有的點的灰度值之和。積分圖像主要用于算法加速，廣泛應用于快速特征檢測中。雖然在過去的十年間，移動處理器有了很大發展，但是相比于桌面處理器的性能還有很大差距。而隨著目前各種異構并行編程模型的成熟，其可以很好的彌補移動平處理器的性能，顯著的提高積分圖像算法的實時性。

GPU（Graphics Process Unit）的概念是NVDIA公司于1999年率先提出的。GPU中設計了大量用于算術邏輯運算的晶體管，這些晶體管的網狀布局賦予了GPU強大的并行數據運算能力。隨著科技的進步，對于智能手機的實時性要求也越來越重要，充分利用智能手機的GPU參與運算是極其必要的。大量的研究者開始進行各平臺上的GPU并行加速研究。Sinha等提出了基于OpenGL的SIFT算法，但是并不適用于移動平臺;Keyombya在智能手機上實現了基于OpenGL的SIFT算法加速，并取得了一定的效果;Guohui Wang等提出了基于OpenCL標準的GPU加速理論，其主要應用在智能手機平臺上，并對OpenCL標準的GPU并行算法的優化進行了闡述。中國科學院的吳再龍、張櫻等對圖像重映射算法、圖像模糊算法等進行了并行優化，并取得了不錯的效果。

對于積分圖像的GPU并行算法，清華大學的王志國采用了分段前綴加法算法，降低了線程間的通訊依賴，提高了GPU線程的工作效率;中國科學院的賈海鵬在采用分而治之策略的前提下，采用雙buffer的方式，消除了bank沖突，取得了不錯的效果。然而遺憾的是，他們的成果主要應用于桌面平臺。本文通過對上述文獻的研究，以OpenCL異構并行編程為基礎，在智能手機平臺上對積分圖像并行算法進行研究。

1 積分圖像原理

積分圖像算法原理基于前綴加法，實際上，積分圖像可以理解為二維的前綴加法。對于一個一維數組a（x），其前綴加法結果b（x）為：

而對于一副圖像I（x，y），其積分圖像可表示為：

我們首先對圖像進行行前綴加法，可以得到：

然后對得到的圖像進行列前綴加法，即可得到積分圖像：

2 并行前綴加法

2.1 Hillis和Steele并行前綴加法

并行前綴加法最早由Hillis和Steele于1986年提出的。該算法的工作方式是假設存在與元素一樣多的處理器，構造一棵高度為log2n的樹結構，對每一層都進行順序掃描，即可得到結果。

如果采用Hillis和Steele的前綴和算法進行并行計算，在每一層的計算中，并不能同時啟動所有線程，因為一旦位于前面的線程計算完畢，則內存就已經發生了改變，后面線程的計算都為錯誤。那么就只能采用層掃描的方式，依次對每個點進行計算，可以很容易的發現其時間復雜度為O（nlOg2n），甚至比串行算法還要高。

解決的方法是定義一個與元素組同樣大的數組，在對原數組進行第一層數組的計算時，將結果數組保存至臨時數組，然后在對臨時數組進行第二層數組的計算，將結果保存至原數組。但這種方式仍然存在很大的弊病，其一是相鄰的線程會去訪問同一個內存，造成bank沖突，其二是在生成臨時數組時，對臨時數組進行初始化需要浪費些許時間，同時會造成空間復雜度從O（l）提高至O（n），造成空間的浪費，特別是對于移動平臺的GPU來說，當圖像過大時，浪費共享內存是及其奢侈的事情，甚至會造成溢出，使程序無法正常運行。由于上述原因，在本文中不采用Hillis和Steele前綴和算法。

2.2 Blelloch并行前綴加法

Blelloch采用了平衡二叉樹的方式，將數組作為平衡二叉樹的葉子節點，采用歸約的方式計算該二叉樹，其計算過程包括上歸約過程和下歸約過程。

在上歸約過程中，將左子樹和右子樹的和保存至父節點，但在實際操作中，我們采用父節點數據覆蓋右子樹數據，留下左子樹數據的方式，不會丟失信息，也可以節省空間。

在下歸約過程中，首先將根節點清零，并將其保存至臨時內存中，然后在每一層，都將父節點與左子樹的和賦予右子樹，將父節點的值賦予左子樹。經過上歸約過程和下歸約過程，對最后一個數據進行特殊處理后，即可得到前綴數組。

相對于Hillis和Steele的并行前綴加法，Blelloch的并行前綴加法有2次歸約的過程，在每層都并行執行的情況下，計算的層數是前者的兩倍，但使用這種算法的好處是，每個線程所訪問的兩個數據別的線程一定不會訪問，不會造成bank沖突，也不需要生成額外的數組，僅需要申請一個數據空間保存根節點數據，符合本文基于移動平臺GPU的設計方式。3積分圖像并行算法設計與優化

3.1 積分圖像并行算法設計

積分圖像算法主要包括一次行前綴加法和一次列前綴加法，在實際的工作中，進行列前綴算法時，線程訪問按列訪問，則會導致訪問的不連續，影響程序性能，因此，在進行列前綴加法前，我們對行前綴算法的結果進行一次轉置，然后進行第二次行前綴加法，再對輸出結果進行一次轉置，即可得到積分圖像。在并行算法下，一次矩陣轉置只需要每個線程進行一次操作，時間損耗極小。

圖1為圖像中每行進行的并行行前綴加法流程，圖像中每行數據都并行計算。

并行行前綴加法流程包括：

（1）將原數組劃分至共享內存;

（2）進行上歸約操作，并將塊和保存至全局塊和數組，對塊和清零;

（3）進行下歸約操作;

（4）將下歸約塊與塊和數組合并，保存至全局目標數組。值得一提的是，在塊合并時，采用行并行列串行的方式，合并不可避免的會影響程序的執行效率。

3.2 積分圖像并行算法優化

對于行前綴加法的并行化，本文針對智能手機的硬件條件做出了以下優化方式：

（1）算法優化。行前綴加法原理是基于平衡二叉樹的，它要求計算數據量一定為2k個，如果對原數據進行補齊，補齊的數據量會極大，所以在本文中，我們采用先分而治之再合并的方式，將數據分為數個2n個數據的子塊，則補齊的數據不會太大，同時，分治法也讓比全局內存更快的共享內存有了用武之地。

（2）內存優化。對于每個子塊，線程在歸約過程中會進行頻繁的數據訪問，所以在實際工作中，本文將這些子塊傳至共享內存，以加快訪問速度。對于智能手機的硬件條件，每個group的共享內存的可分配大小不能超過256，因此，本文以256*1的方式來劃分數據。

（3）指令優化。盡量減少分支語句，使用三目運算符代替條件判斷語句。④內核優化。在實際的工作中，為了減少CPU與GPU之間過多的數據傳輸而大大增加并行算法運行的時間，本文在進行積分圖像并行算法的設計時，采用了在一個內核中執行行前綴加法和矩陣轉置的方案。只需要調用兩次該內核，即可得到目標矩陣。

4 實驗結果及分析

本次實驗的軟件平臺為Android5.1，硬件平臺為Adren0 510，該平臺最高支持OpenCL2.0標準。APP編譯平臺為Windows10，主要使用Android Srudi0 2.2對軟件進行編譯，采用NDK技術將C++源碼編譯生成本地庫，然后由JNI在Java層中實現本地庫中積分圖像并行算法的調用。

本次實驗對三種算法進行了測試，第一種是OpenCV中的標準串行算法;第二種優化前的積分圖像并行算法，即不使用分而治之策略，不使用共享內存等方法進行優化的算法;第三種是使用本文中優化策略的優化后算法。

本次實驗中對多組圖片進行了測試，這些樣本圖片的尺寸不一，能夠體現本算法在不同大小數據處理時的運行速度。為了提高加速比的可信度，在進行積分圖像并行算法測試的時候，將使用變量控制法，進行內核運行粒度設置統一、保持并行算法外其他算法不變等措施。然后每組圖片都進行多次實驗，取其平均值，以降低隨機概率事件的影響。

如表1所示，由實驗數據可知，相對于標準串行算法，當圖像不大時，優化后的并行算法并不能取得優勢，這是由CPU與GPU的數據傳輸導致的。隨著圖像的增大，加速比逐漸上升，數據傳輸時間被掩蓋。但圖像大到一定程度時，塊合并的代價升高，使得加速比有所下降。

而對于優化前的積分圖像并行算法，因為在未使用優化策略的情況下，需要非常多次的全局內存同步，以及全局內存的訪問速度很慢的問題，導致了該算法運行效率極低，從側面上反映了本文優化策略的有效性。

5 結束語

本文重點對兩種前綴加法進行了分析，設計了積分圖像并行算法，并進行了優化。并取得了不錯的效果。但是受到宿主機數據傳輸、GPU中內存數據讀取速度和算法中塊合并的影響，本算法的加速效果還有待提高。今后對宿主機數據傳輸的優化以及對塊合并部分的優化應該是本算法隨后應該改進的方向。

參考文獻

[1]吳再龍，張云泉，龍國平等.基于OpenCL的圖像重映射算法優化研究[J].科研信息化技術與應用，2013，4（01）：57-66.

[2]張櫻，張云泉，龍國平，基于OpenCL的圖像模糊化算法優化研究[J]，計算機科學，2012， 39 （03）： 260-264.

[3]王志國，王貴錦，施陳博等，積分圖像的快速GPU計算[J].計算機應用研究，2011， 28 （10）： 3913-3916.

[4]賈海鵬，張云泉，徐建良，基于OpenCL的圖像積分圖算法優化研究[J].計算機 科學，2013 （02）：1-7.