蔣睿 張素文 汪創(chuàng)

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

【關(guān)鍵詞】積分圖像 OpenCL 并行

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

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

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

1 積分圖像原理

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

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

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

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

2 并行前綴加法

2.1 Hillis和Steele并行前綴加法

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

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

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

2.2 Blelloch并行前綴加法

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

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

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

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

3.1 積分圖像并行算法設(shè)計

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

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

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

（1）將原數(shù)組劃分至共享內(nèi)存;

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

（3）進行下歸約操作;

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

3.2 積分圖像并行算法優(yōu)化

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

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

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

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

4 實驗結(jié)果及分析

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

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

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

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

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

5 結(jié)束語

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

參考文獻

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

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

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

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