孫立超，張盛兵，程訓燾，張 萌

(西北工業(yè)大學計算機學院，陜西 西安 710129)

0 引言

隨著計算機科技的發(fā)展，新的信息技術(shù)和媒體手段不斷出現(xiàn)，這使得包括人臉分析在內(nèi)的智能人機交互不僅成為可能，而且飛速發(fā)展。人臉檢測作為人臉分析的第一步，負責數(shù)字圖像中人臉的檢測和定位，是目標檢測技術(shù)的一個特例。2001年劍橋大學的Viola和Jones提出了第一種快速實時的目標檢測方法——Viola－Jones級聯(lián)分類器［1］，其主要貢獻是將 3個關(guān)鍵方法和概念應用在人臉檢測中:積分圖、Ada－Boost算法［2］和分類器級聯(lián)。雖然此方法在CPU上已經(jīng)實現(xiàn)了很快的檢測速度，但隨著圖像分辨率的不斷提高和人臉檢測應用的發(fā)展，CPU平臺已經(jīng)無法滿足快速檢測的需求。

基于GPU的并行計算正被廣泛應用于各種計算密集型的應用中。針對人臉檢測內(nèi)在并行性的特點，越來越多的人考慮運用并行計算的方法來加速人臉檢測。隨著高性能GPU的快速發(fā)展，Nvidia公司在2007年推出 CUDA 計算平臺［3－5］，研究者很快將目光轉(zhuǎn)向基于CUDA平臺的人臉檢測。

文獻［6］在FPGA上實現(xiàn)了人臉檢測系統(tǒng)的并行加速，對于640×480像素的視頻流實現(xiàn)了6.96幀每秒的檢測速率，但是當圖像尺寸變化時，系統(tǒng)需重新修改，設計開銷較大。文獻［7－9］設計的GPU加速人臉檢測方法，取得了一定的加速效果，但其存在GPU負載不均衡的問題，加速效果并不理想。針對上述情況，本文在CUDA平臺下實現(xiàn)一種基于Viola－Jones級聯(lián)分類器的并行人臉檢測方法，顯著提高了檢測速率，而且通過降低并行粒度，有效地解決了負載不均衡的問題。

1 人臉檢測算法

人臉檢測的方法可以大致分為基于特征和基于圖像兩類?；谔卣鞯姆椒ㄊ且阅撤N特征為處理對象，而基于圖像的方法是以圖像中的像素為處理對象。

1.1 Haar-like特征矩形

Viola－Jones級聯(lián)分類器方法是一種基于 Haarlike特征的人臉檢測算法。本文采用的5種Haarlike特征矩形如圖1所示，白色區(qū)域像素值的和減去黑色區(qū)域像素值的和得到的差值稱為特征矩形的特征值。由于人臉五官相互之間在顏色、形狀和位置分布上都有著明顯的差異，而且人臉本身和外界非人臉的雜亂信息相比具有極高的規(guī)律性，因此可用特征矩形的特征值作為人臉判斷的依據(jù)。

圖1 Haar－like 特征矩形

1.2 積分圖

特征矩形的特征值計算是人臉檢測過程中的重要一環(huán)。通過引入積分圖，可將一個矩形區(qū)域內(nèi)像素值和的計算簡化為固定次數(shù)的加減運算。積分圖上點ii(x，y)和矩形區(qū)域內(nèi)像素值和S的計算如公式(1)、公式(2)所示:

其中，i(x＇，y＇)表示源圖像(x＇，y＇)點的像素值，(xA，yA)、(xB，yB)、(xC，yC)和(xD，yD)分別為矩形區(qū)域左上、右上、左下和右下角的坐標。

1.3 Adaboost算法

給定一個訓練集和一個特征矩形集合，任何機器學習方法都可以從中學習并生成一個分類器函數(shù)f=(X，θ)，X為特征矩形，θ為閾值，函數(shù) f的返回值由X的特征值與θ的大小關(guān)系決定。由于尺寸和位置的變化多樣，特征矩形的數(shù)目眾多，但是大部分特征矩形覆蓋的均是非人臉特性。Adaboost算法被用于挑選覆蓋人臉特性的特征矩形，構(gòu)成弱分類器，并將若干個弱分類器級聯(lián)構(gòu)成一個強分類器，通過迭代學習獲得合適的閾值和分類函數(shù)返回值，從而得到簡單高效的分類器，進而大幅提高人臉檢測速度。

1.4 級聯(lián)分類器

由于本文重點在于人臉檢測過程的并行加速，因此未自行訓練生成分類器，采用 OpenCV［10－11］開源軟件自帶的正向人臉級聯(lián)分類器，可通過軟件安裝獲得。該分類器由20級強分類器級聯(lián)構(gòu)成，每級強分類器由若干個弱分類器組成，每個弱分類器包含兩個特征矩形，窗口大小為20×20。級聯(lián)的強分類器構(gòu)成了一個決策樹，每一級的強分類器盡可能多地排除確定非人臉的掃描窗口，只有通過所有級的強分類器的掃描窗口才被檢測為人臉，整個運行過程如圖2所示。通過將級聯(lián)分類器設定為前級簡單后級復雜的結(jié)構(gòu)，可有效地減少運算量，從而提高檢測速率。

圖2 級聯(lián)分類器

2 基于CUDA的人臉檢測算法實現(xiàn)

人臉檢測可以大體分為5部分:分類器和源圖像的加載、積分圖的計算、掃描窗口的檢測、分類器的放大修正和人臉窗口的合并，其中積分圖的計算、掃描窗口的檢測和分類器的放大修正均可在CUDA平臺下實現(xiàn)并行加速。

2.1 積分圖計算的CUDA實現(xiàn)

對于積分圖的計算，本文采用先行后列的積分算法，有效避免了數(shù)據(jù)相關(guān)性。行積分和列積分分別由兩個Kernel實現(xiàn)。每個線程負責一行或一列的積分，線程直接沒有相關(guān)性，不需要線程同步，具有較高的并行效率。但是由于CUDA中線程是以warp(32個線程)為單位調(diào)度的，行積分中同一warp內(nèi)的線程需要按列訪問源圖像數(shù)據(jù)，數(shù)據(jù)不連續(xù)，需拆分成多次訪問，效率較低，積分結(jié)果寫回也存在相同的問題。如圖3所示，本文利用共享存儲器對行積分過程進行訪存優(yōu)化。

圖3 行積分共享存儲器優(yōu)化圖

圖3中，源圖像的寬度為M，block內(nèi)線程數(shù)為N，共享存儲器規(guī)模為N×N，block負責的N行M列數(shù)據(jù)被分為個N×N個數(shù)據(jù)塊。對于每個數(shù)據(jù)塊，首先block內(nèi)線程將其按行讀入到共享存儲器，然后對共享存儲器按列訪存做行積分，最后將共享存儲器中的積分結(jié)果按行寫回全局存儲器。由于共享存儲器可實現(xiàn)高效列訪存，共享存儲器均為行訪存，因此訪存效率得到了有效的改善。

2.2 掃描窗口檢測的CUDA實現(xiàn)

人臉檢測過程中掃描窗口的檢測相互獨立，每個掃描窗口的檢測可由一個線程完成，GPU可以保證大量線程的同時執(zhí)行，理論上說可以取得非?？捎^的并行加速效果，但實際并不理想。因為級聯(lián)分類器的設計思想是通過前級簡單分類器盡可能多地排除非人臉窗口，減少后級復雜分類器的任務量，從而減少檢測時間，而GPU上的執(zhí)行單元采用的是SIMD結(jié)構(gòu)，線程以warp為單位進行調(diào)度，同一warp內(nèi)不同線程負責的掃描窗口分類器執(zhí)行級數(shù)差距很大，warp總的執(zhí)行時間由執(zhí)行級數(shù)最大的線程決定，負載非常不均衡，大大降低了GPU的加速效果。

本文通過降低線程并行粒度為分類器，引入重映射數(shù)組均衡線程負載，盡可能地發(fā)揮GPU的并行性能。具體過程如圖4所示，GPU上線程只負責一級分類器(Stage)的檢測，線程i負責執(zhí)行掃描窗口RemapIndex［i］的檢測任務，F(xiàn)acialResult［i］是線程 i的檢測結(jié)果。GPU每執(zhí)行完一級分類器后，CPU根據(jù)檢測結(jié)果，是將人臉的掃描窗口編號依次存入重映射數(shù)組RemapIndex，然后調(diào)用GPU進行下一級分類器檢測，重復上述過程，直到分類器全部執(zhí)行完畢或掃描窗口全為非人臉為止。

圖4 掃描窗口重映射圖

雖然并行粒度的降低有效地減少了掃描時間，但也引入主機端(CPU)和設備端(GPU)之間額外的數(shù)據(jù)通信開銷。相對于設備端而言，該部分額外開銷包括重映射數(shù)組的寫入和檢測結(jié)果的傳出，均可通過零拷貝技術(shù)［12］優(yōu)化掉。零拷貝技術(shù)是指存在于主機端的映射內(nèi)存同時擁有主機端和設備端兩個地址，設備端程序可以直接訪問映射內(nèi)存，而不再需要數(shù)據(jù)拷貝。由于映射內(nèi)存資源較少，分配太多反而會導致系統(tǒng)性能下降，本文只對檢測結(jié)果進行零拷貝技術(shù)優(yōu)化。

2.3 分類器放大修正的CUDA實現(xiàn)

為檢測不同大小的人臉圖像，需將圖像分解為不同尺寸的多批掃描窗口，對每批掃描窗口分別進行檢測，最終通過人臉重復窗口合并得到人臉的相關(guān)信息。分類器窗口的原始尺寸為20×20，檢測完一批掃描窗口后，分類器窗口需按比例放大，實際是放大分類器中特征矩形，由于舍入誤差，放大后的特征矩形中矩形面積與權(quán)值乘積之和可能不再為零，需要進行權(quán)值修正處理。

分類器的放大修正相互獨立，每個特征矩形由一個線程負責，負載任務均衡，具有很好的并行性能。因為分類器放大修正的執(zhí)行結(jié)果直接保存在GPU全局存儲器內(nèi)，所以不僅減少了運算時間，而且還消除了分類器從CPU到GPU的傳輸時間，從而進一步提高了人臉檢測速率。

3 實驗與結(jié)果分析

本文采用CMU人臉庫［13］對人臉檢測程序進行了檢測率和誤檢率的測試，采用不同尺寸的同幅圖像測試人臉檢測程序的檢測速率。CMU人臉庫是卡耐基梅隆大學提供的用于評估正向人臉檢測算法性能的公開人臉數(shù)據(jù)集。測試環(huán)境如表1所示。

表1 測試環(huán)境信息表

3.1 檢測精度結(jié)果與分析

本文選用CMU人臉庫中的130幅非傾斜圖像，其中人臉數(shù)目為489個，其中一幅圖像的檢測結(jié)果如圖5所示。

圖5 人臉檢測結(jié)果

圖5中共有57個人臉，檢測程序給出了58個標記，其中1個為非人臉，則程序的人臉檢測率為100%(57/57)，誤檢率為1.72%(1/58)。本文利用CMU人臉庫分別對CUDA版本、CPU版本和OpenCV版本的人臉檢測程序進行測試，其中CPU版本為自行編寫的串行程序，OpenCV版本為開源代碼，采用Intel公司的 TBB(Threading Building Blocks)［14］技術(shù)進行多核優(yōu)化。得到的檢測率和誤檢率結(jié)果如表2所示。

表2 人臉檢測率和誤檢率

表2中3個版本程序的誤檢率相當，CUDA版本的檢測率與CPU版本相近，比OpenCV版本略低一些，但仍在可接受范圍之內(nèi)。存在差異的原因是本文為提高檢測速率，在CUDA和CPU版本中采用了兩種不同于OpenCV版本的處理方式:(1)將程序中的一些浮點中間變量由雙精度改為單精度;(2)將掃描窗口檢測部分中的一些重復操作合并轉(zhuǎn)移到分類器放大修正部分，使得一些先乘后除的操作變?yōu)橄瘸蟪瞬僮?，形成了一定的積累誤差。

3.2 檢測速率結(jié)果及分析

本文采用不同尺寸的同一幅人臉圖像對3個版本的人臉檢測程序進行測試，執(zhí)行時間如表3所示，時間單位為秒。

表3 人臉檢測速率表

CUDA和OpenCV版本相對于CPU版本程序的加速比如圖6所示。

圖6 CUDA和OpenCV版本的加速比圖

從圖6中可以看出，隨著圖像尺寸的增大，OpenCV版本相對于CPU版本的加速比一直保持在5左右，而CUDA版本的加速比不斷增加，效果明顯好于OpenCV版本。這說明TBB技術(shù)的加速性能是非常有限的，相比而言，CUDA技術(shù)更適合高清圖像的實時檢測。

4 結(jié)束語

本文實現(xiàn)了基于Viola－Jones級聯(lián)分類器的CUDA人臉檢測程序，有效解決了級聯(lián)分類器造成的GPU負載不均衡的難題，取得了非常好的加速性能，與OpenCV開源庫程序相比實現(xiàn)了1.58～4.56倍的加速比。

雖然本文有效地實現(xiàn)了GPU負載均衡，但是同級分類器中分支較多的問題還沒得到有效解決。今后，筆者將通過修改分類器結(jié)構(gòu)和改進實現(xiàn)方法來減少分支，從而進一步提高檢測速率。

［1］Viola P，Jones M.Rapid object detection using a boosted cascade of simple feature［C］//Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2001:511－518.

［2］Freund Yoav，Schapire Robert E.A short introduction to boosting［J］.Journal of Japanese Society for Artificial Intelligence，1999，14(5):771－780.

［3］Rob Farber.高性能CUDA應用設計與開發(fā)［M］.于玉龍，唐堃譯.北京:機械工業(yè)出版社，2012:2－16.

［4］NVIDIA.CUDA_C Programming Guide［EB/OL］.http://docs.nvidia.com/cuda/cuda－c－programming－guide/，2013－04－02.

［5］Jason Sanders，Edward kandrot.GPU高性能編程CUDA實戰(zhàn)［M］.聶雪軍，等譯.北京:機械工業(yè)出版社，2011:27－41.

［6］Junguk Cho，Shahnam Mirzaei，Jason Oberg，et al.FPGA－based face detection system using Haar classifiers［C］//Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays.2009:103－112.

［7］Kong Jiangang，Deng Yangdong.GPU accelerated face detection［C］//International Conference on Intelligent Control and Information Processing.2010:584－588.

［8］Sharma B，Thota R，Vydyanathan N，et al.Towards a robust，real－time face processing system using CUDA－enabled GPUs［C］//International Conference on High Performance Computing.2009:368－377.

［9］Bayazit M，Couture－Beil A，Mori G.Real－time motionbased gesture recognition using the GPU［C］//Proceedings of the IAPR Conference on Machine Vision Applications.2009:9－12.

［10］OpenCV.The OpenCV Reference Manual 2.3.0［EB/OL］.http://opencv.org/documentation.html，2012－02－05.

［11］Bradski G，Keahler A.Learning OpenCV:Computer Vision with the OpenCV Library［M］.O’Reilly，2008:506－516.

［12］張舒，褚艷利，趙開勇，等.GPU高性能運算之CUDA［M］.北京:中國水利水電出版社，2009:152－163.

［13］CMU.Frontal Face Images［DB/OL］.http://vasc.ri.cmu.edu//idb/html/face/frontal_images/index.html，1998－01－08.

［14］Wikipedia.Intel Threading Building Blocks［EB/OL］.http://en.wikipedia.org/wiki/Intel_Threading_Building_Blocks，2013－01－08.