，

(信息工程學(xué)院，浙江 杭州 310023)

自動(dòng)指紋識(shí)別系統(tǒng)在過(guò)去的50年里不斷地被研究開(kāi)發(fā)，其中仍然有很多開(kāi)放性的研究課題，特別是當(dāng)獲取的指紋圖像質(zhì)量較差，指紋特征不明顯的時(shí)候.為了能夠準(zhǔn)確地從指紋圖像中獲取指紋特征，指紋圖像增強(qiáng)成為了自動(dòng)指紋識(shí)別系統(tǒng)中必不可少的一個(gè)步驟.已知自適應(yīng)指紋圖像增強(qiáng)系統(tǒng)在等誤差率、認(rèn)假率和不匹配率等方面都有很好的表現(xiàn)[1-2].其中局部指紋頻譜特性估計(jì)是該指紋圖像增強(qiáng)系統(tǒng)的核心組成部分，由于其需要對(duì)大量的局部指紋圖像進(jìn)行頻譜特性估計(jì)，因此僅僅利用CPU進(jìn)行運(yùn)算需要消耗較長(zhǎng)時(shí)間.

近年來(lái)，GPU已經(jīng)發(fā)展演變成了一種高并行度，多線程的多核處理器，它強(qiáng)大的計(jì)算能力和極大的內(nèi)存帶寬讓其不再局限于傳統(tǒng)的3D圖像處理，而是更多地被廣泛用于通用并行計(jì)算[3-5].由英偉達(dá)公司開(kāi)發(fā)的CUDATM運(yùn)算平臺(tái)為開(kāi)發(fā)人員提供了一套針對(duì)GPU的編程模型，使得GPU具備了解決復(fù)雜計(jì)算問(wèn)題的能力，同時(shí)大大簡(jiǎn)化了GPU編程[6].如今通過(guò)CUDA的GPU編程已經(jīng)在信號(hào)處理領(lǐng)域，特別是圖像處理領(lǐng)域被廣泛應(yīng)用[7-9].此外，由于不同局部指紋的頻譜估計(jì)之間具有高度的獨(dú)立性，非常適合多線程實(shí)現(xiàn).因此，將該基于GPU的并行實(shí)現(xiàn)方法，應(yīng)用于已知指紋增強(qiáng)系統(tǒng)，以提高已知指紋增強(qiáng)系統(tǒng)局部指紋頻譜估計(jì)的運(yùn)算速度.

1 局部指紋頻譜特性估計(jì)

由于局部指紋在頻譜特性上相似于一個(gè)帶噪聲的正弦信號(hào)，因此只需要模擬正弦信號(hào)尋找主頻率的方式便可以估計(jì)出局部指紋的紋線頻率及其方向，即局部指紋的頻譜特性.所要優(yōu)化的局部指紋頻譜特性估計(jì)大致可以分為3個(gè)步驟[1]：

步驟1采用SMQT對(duì)局部指紋進(jìn)行動(dòng)態(tài)范圍調(diào)整，增強(qiáng)局部指紋的對(duì)比度，以解決局部指紋可能存在的對(duì)比度較差問(wèn)題[10]，即

IH(m1,m2)=SMQT{IL(m1,m2)}

(1)

式中：IL(m1,m2)為一張M1×M2的局部指紋圖像；IH(m1,m2)為對(duì)比度增強(qiáng)后的局部指紋圖像，其中m1∈[0,M1-1]，m2∈[0,M2-1].

步驟2對(duì)增強(qiáng)后局部指紋圖像IH(m1,m2)進(jìn)行幅度譜計(jì)算，即

G(ω1,ω2)=|J{IH(m1,m2)}|

(2)

式中J{IH(m1,m2)}為對(duì)局部指紋圖像IH(m1,m2)的二維傅里葉變換.

步驟3遍歷幅度譜G(ω1,ω2)，獲得幅度峰值Pi，從而篩選獲得最大峰值PD及其對(duì)應(yīng)的頻率ωD,x與ωD,y，然后利用峰值計(jì)算峰度因子，用于判斷局部指紋噪聲大小，即

(3)

式中N為幅度譜中所含的峰值數(shù).由于每個(gè)局部指紋含有一組頻譜特征，因此整個(gè)指紋圖像可以用特征圖PD(n1,n2)，ωD,x(n1,n2)，ωD,y(n1,n2)和Q(n1,n2)來(lái)表示.

2 CUDA架構(gòu)及其編程模型

從圖像處理到通用并行計(jì)算，GPU強(qiáng)大的運(yùn)算能力得益于其單指令多線程的體系架構(gòu)，這種體系架構(gòu)能夠讓程序員直接為線程編寫(xiě)程序，從而能夠?qū)崿F(xiàn)線程間獨(dú)立計(jì)算，同時(shí)也能進(jìn)行線程之間的相互協(xié)調(diào)通信，英偉達(dá)公司推出的CUDATM便是一種通用的并行計(jì)算架構(gòu).在CUDA架構(gòu)中，GPU可以被看成是一組流處理器，配備有多種形式的內(nèi)存，如全局內(nèi)存、局部?jī)?nèi)存、紋理內(nèi)存和共享內(nèi)存等.一個(gè)多線程程序被劃分成多個(gè)CUDA程序塊，不同程序塊之間相互獨(dú)立，被自動(dòng)平均分配給GPU的不同流處理器，如圖1所示.

圖1 多線程CUDA編程與GPU流處理器Fig.1 Multi-threaded CUDA programing with GPU streaming multiprocessors

此外CUDA運(yùn)算平臺(tái)還為GPU提供了一套編程模型(圖2)，在CUDA編程模型中，程序員可以在CPU端以調(diào)用核函數(shù)的方式來(lái)來(lái)訪問(wèn)GPU，并且可以指定需要調(diào)用的線程塊數(shù)量以及線程塊中的線程數(shù)量.這些線程會(huì)組織成三級(jí)層次結(jié)構(gòu)，線程組成線程塊，線程塊在線程格上運(yùn)行，每一個(gè)線程和線程塊都會(huì)有相應(yīng)的內(nèi)置標(biāo)識(shí)符threadId和blockId來(lái)進(jìn)行標(biāo)識(shí).

圖2 CUDA編程模型Fig.2 CUDA programing model

3 基于GPU的指紋局部特性估計(jì)的實(shí)現(xiàn)方法

首先將整個(gè)指紋圖像劃分成一定數(shù)量的局部指紋圖像，然后調(diào)用相應(yīng)數(shù)量的CUDA線程塊來(lái)實(shí)現(xiàn)并行處理不同局部指紋的功能.此外，對(duì)于其中某一塊，相應(yīng)CUDA線程塊中的多個(gè)線程會(huì)被調(diào)用，來(lái)對(duì)其中的SMQT，2DFFT和特性估計(jì)進(jìn)行并行優(yōu)化.由于整個(gè)處理過(guò)程中指紋圖像具備只讀的屬性，因此采用CUDA紋理內(nèi)存來(lái)存儲(chǔ)指紋圖像以提高讀取效率.圖3簡(jiǎn)略地表示了線程塊B(i,j)處理相應(yīng)局部指紋圖像IL(i,j)的過(guò)程，采用(i,j)標(biāo)識(shí)線程塊和局部指紋圖像，即i和j分別表示局部指紋圖像所在行數(shù)與列數(shù).

圖3 局部頻譜特性估計(jì)模型Fig.3 The model of local spectrum estimation

3.1 SMQT的并行優(yōu)化

針對(duì)SMQT中大量的平均值計(jì)算[10]，采用順序?qū)ぶ返腃UDA并行歸約算法來(lái)對(duì)其中的求和過(guò)程進(jìn)行優(yōu)化，圖4簡(jiǎn)要地闡述了8個(gè)數(shù)并行規(guī)約求和的過(guò)程，首先利用4個(gè)線程將數(shù)據(jù)兩兩求和，并將求和結(jié)果存儲(chǔ)于共享內(nèi)存中.然后再利用其中兩個(gè)線程將求和結(jié)果再次兩兩相加，以此類推，最后這8個(gè)數(shù)的和被存儲(chǔ)于共享內(nèi)存的第一塊單元中.顯然，如果需要對(duì)N個(gè)值進(jìn)行求和，求和的步驟便可以從單線程的N-1次縮減到log2N次.

圖4 順序?qū)ぶ返牟⑿幸?guī)約算法Fig.4 The model of local spectrum estimation

3.2 2DFFT的并行優(yōu)化

由于CUDA提供的cuFFT庫(kù)是一個(gè)只能在主機(jī)端調(diào)用的應(yīng)用接口，并不能在設(shè)備端調(diào)用，因此只能重新實(shí)現(xiàn)設(shè)備端的2DFFT，圖5簡(jiǎn)要地闡述了多線程2DFFT的實(shí)現(xiàn)過(guò)程.每一個(gè)CUDA線程塊中的線程都會(huì)對(duì)局部指紋的某一行數(shù)據(jù)進(jìn)行一維FFT運(yùn)算，并將運(yùn)算結(jié)果按轉(zhuǎn)置的方式存儲(chǔ).等到所有線程都完成運(yùn)算，再一次并行地對(duì)每一行數(shù)據(jù)進(jìn)行一次一維FFT，其轉(zhuǎn)置后的運(yùn)算便是最終2DFFT的結(jié)果.

圖5 2DFFT的并行實(shí)現(xiàn)過(guò)程Fig.5 The model of local spectrum estimation

3.3 特性估計(jì)的并行優(yōu)化

利用CUDA線程塊中的多線程，對(duì)局部指紋圖像的幅度函數(shù)進(jìn)行并行峰值遍歷搜索.每個(gè)線程都會(huì)定義一個(gè)3×3的矩陣，用以判斷幅度值在其領(lǐng)域內(nèi)是否為最大值，從而獨(dú)立完成對(duì)一行數(shù)據(jù)的峰值搜索.因此對(duì)于一個(gè)N1×N2的二維幅度函數(shù)，CUDA線程塊中的N1個(gè)線程被充分調(diào)用.圖6闡述了一個(gè)線程完成一行數(shù)據(jù)峰值遍歷搜索的過(guò)程，其中每一行的最大峰值都會(huì)被保存下來(lái)，用于獲得最終的頻譜峰值及其坐標(biāo)的同時(shí)計(jì)算峰度因子.峰度因子的計(jì)算式為

(4)

圖6 一行數(shù)據(jù)的峰值搜索過(guò)程Fig.6 Peak search for a row of magnitude values

式中PD,M為每行最大峰值PD,i的最大值.由于整個(gè)過(guò)程對(duì)局部指紋的幅度函數(shù)只存在讀取操作，因此不同線程之間完全并行，不需要進(jìn)行內(nèi)存加鎖使得不同線程之間串行化.

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)在Intel Xeon E5-1620 3.5 GHz 的CPU，NVIDIA Geforce GTX 1080 的GPU以及8G DDR4 內(nèi)存的硬件環(huán)境下完成，利用Visual Studio將基于GPU的局部指紋頻譜估計(jì)接入完整的指紋圖像增強(qiáng)系統(tǒng)并生成可執(zhí)行文件.然后通過(guò)Matlab調(diào)用的方式，將FVC2000數(shù)據(jù)庫(kù)中不同傳感器來(lái)源的指紋圖像輸入測(cè)試.結(jié)果顯示：將該基于GPU的局部指紋頻譜估計(jì)應(yīng)用于已知指紋增強(qiáng)系統(tǒng)中，指紋增強(qiáng)效果顯著[1].以其中3個(gè)樣本為例，效果如圖7所示，其中圖7(a～c)為原始指紋圖像，圖7(d～f)為分別對(duì)應(yīng)的增強(qiáng)指紋圖像.

圖7 基于GPU指紋圖像樣本增強(qiáng)效果Fig.7 The examples of the fingerprint enhancement based on GPU

實(shí)驗(yàn)還對(duì)數(shù)據(jù)庫(kù)中所有指紋的局部頻譜估計(jì)執(zhí)行時(shí)間進(jìn)行統(tǒng)計(jì)，根據(jù)3種尺寸進(jìn)行分類，得出相同尺寸指紋樣本局部頻譜特性估計(jì)執(zhí)行時(shí)間的平均值，結(jié)果如表1所示， 其中加速比是指CPU平均執(zhí)行時(shí)間與GPU平均執(zhí)行時(shí)間的比值.實(shí)驗(yàn)結(jié)果表明：采用該基于GPU的實(shí)現(xiàn)方法，局部指紋頻譜特性估計(jì)的計(jì)算時(shí)間顯著減少，并且隨著指紋尺寸的增加，效果越明顯.

表1局部指紋CPU頻譜估計(jì)與GPU的執(zhí)行時(shí)間比較

Table1ThecomparisonoftheCPUbasedlocalfingerprintspectrumestimatorwithGPUbasedlocalfingerprintspectrumestimator

指紋尺寸CPU平均執(zhí)行時(shí)間/msGPU平均執(zhí)行時(shí)間/ms加速比324×2401 664.43989.701.68300×3002 089.731 099.611.90364×2562 144.611 065.922.01

5 結(jié) 論

針對(duì)已知指紋圖像增強(qiáng)系統(tǒng)基于CPU實(shí)現(xiàn)執(zhí)行時(shí)間較長(zhǎng)的缺點(diǎn)[1]，提出了一種基于GPU的局部指紋頻譜特征估計(jì)的實(shí)現(xiàn)方法，利用GPU多核心多線程的特點(diǎn)對(duì)不同局部指紋圖像進(jìn)行并行化處理，并對(duì)其中單個(gè)局部指紋處理中的SMQT，2DFFT以及特性估計(jì)3部分進(jìn)行了并行優(yōu)化，最后利用CUDA平臺(tái)成功將其實(shí)現(xiàn). 實(shí)驗(yàn)結(jié)果表明：通過(guò)該基于GPU并行運(yùn)算的實(shí)現(xiàn)方法，已知指紋圖像增強(qiáng)系統(tǒng)局部指紋頻譜特性估計(jì)的執(zhí)行時(shí)間顯著減少，因此將該方法應(yīng)用于這個(gè)已知指紋圖像增強(qiáng)系統(tǒng)，可以提高其運(yùn)行效率，使得該指紋圖像增強(qiáng)系統(tǒng)有更大的應(yīng)用前景.