基于可分解的卷積核和快速傅立葉變換FFT的指紋圖像增強算法*

黃東運 鐘震宇 曹永軍 黎偉權(quán)

（廣東省自動化研究所）

基于可分解的卷積核和快速傅立葉變換FFT的指紋圖像增強算法*

黃東運 鐘震宇 曹永軍 黎偉權(quán)

（廣東省自動化研究所）

指紋識別系統(tǒng)在圖像增強階段涉及很多卷積運算，占用大量的計算時間。在不利用專門的DSP處理器進行指紋圖像增強處理情況下，常規(guī)的卷積運算計算時間非常長。在指紋圖像增強過程中，卷積運算主要集中在方向場估計和高波濾波兩個階段。為此本文提出了一種指紋圖像增強算法，利用可分解的卷積核和快速傅立葉變換來替換常規(guī)的卷積運算，可減少算法的時間復(fù)雜度，快速實現(xiàn)指紋圖像增強。

高斯梯度算子；高波算子；高波濾波；卷積核分解；快速傅立葉變換

1 引言

指紋識別技術(shù)是生物識別領(lǐng)域應(yīng)用最廣的識別技術(shù)，大部分指紋識別系統(tǒng)采用指紋特征點匹配的方式進行個人身份識別。特征點為指紋脊線中的末端點或分叉點?？煽康奶卣鼽c提取在指紋分類和識別中起著非常關(guān)鍵的作用。

指紋圖像增強的主要目的是使脊線盡可能清晰和自然，保持指紋特征點的原始特征。指紋增強過程中，不能產(chǎn)生人為的偽特征或噪聲，不能引起特征點的丟失。目前認(rèn)為最可靠并被普遍接受的圖像增強方法一般采用與局部圖像特征相關(guān)的濾波方法進行，其中最廣泛使用的是高波濾波。使用高波濾波可以連接斷裂的脊線，恢復(fù)由于灰塵或污損引起的質(zhì)量較差區(qū)域的脊線圖像。

高波濾波與局部指紋圖像的空間頻率及方向緊密相關(guān)。在進行濾波操作之前，需要對指紋區(qū)域進行脊線方向和頻率估計，然后根據(jù)指紋局部區(qū)域的方向和頻率信息選擇相應(yīng)的高波濾波器進行卷積運算，達(dá)到圖像增強效果。在局部指紋圖像方向估計過程中，主要利用x和y兩個方向的梯度濾波器分別進行濾波，再根據(jù)兩個方向的梯度信息，對局部區(qū)域進行方向估計。頻率估計在脊線方向估計完成后進行，將局部區(qū)域的指紋圖像在垂直于脊線方向進行投影，計算一維波形圖中峰值之間的平均距離，即可獲得其頻率信息。因此，在圖像增強過程中涉及大量卷積運算，計算量非常大，需要的計算時間非常長，必須選擇合適的算法來代替常規(guī)的卷積運算，減少計算時間，滿足指紋識別系統(tǒng)中實時性要求。

為了降低卷積運算的計算量，本文提出的算法利用可分解的濾波器和傅立葉變換的卷積特性，在方向場估計和高波濾波兩個階段進行算法優(yōu)化，降低時間復(fù)雜度，實現(xiàn)快速指紋圖像增強。

2 指紋圖像增強過程

基于特征點的指紋識別過程一般包括指紋區(qū)域檢測、脊線方向、頻率估計、圖像增強、指紋圖像二值化和脊線細(xì)化、特征點提取和編碼、模式匹配等。在這些處理過程中，大部分計算量集中在指紋特征點提取之前即圖像增強階段。圖1顯示了指紋圖像增強過程中每個階段圖像的處理結(jié)果。

圖1 指紋圖像處理前、后的圖像

圖1中，(b)和(c)在空間結(jié)構(gòu)上與原始圖像(a)稍微發(fā)生形變，這是由于在算法中，采用統(tǒng)一的脊線頻率值即經(jīng)驗值。當(dāng)脊線頻率值與實際的局部指紋圖像脊線頻率有差異時，在高波濾波以后會產(chǎn)生形變。但算法很好地保證了指紋特征點（末端點和分叉點）的完整性，并連接了脊線斷開點。

3 方向場估計

指紋方向場是指紋圖像增強過程中的重要部分，指紋圖像方向場估計的結(jié)果是一個二維浮點數(shù)據(jù)類型矩陣，維度與原始圖像數(shù)據(jù)矩陣一致，每個像素對應(yīng)的方向值，是動態(tài)選擇高波濾波器的依據(jù)。本文采用Lin Hong等[1]提出的最小均方方法來估計指紋脊線的局部方向。給定一個指紋圖像G，方向場估計的主要步驟如下：

② 以像素（i，j）為中心，區(qū)域大小為w×w，計算每個塊的局部脊線方向θ(i,j)：

為了算法優(yōu)化，選用可分解的高斯梯度算子，將二維算子分解成兩個一維的算子，利用快速傅立葉變換以及逆變，實現(xiàn)第一階段需要的卷積運算。

3.1 高斯梯度算子

高斯濾波器在數(shù)字信號處理中被廣泛應(yīng)用。在數(shù)字圖像處理中，通過該濾波器進行濾波可起到消除噪聲、平滑圖像的效果。其二維的高斯濾波器定義如下：

其中，x為原點到水平軸的距離；y為原點到垂直軸的距離；σ為標(biāo)準(zhǔn)的高斯分布標(biāo)準(zhǔn)方差。分別對式（4）進行x和y方向求導(dǎo)，可獲得兩個方向的梯度算子公式。

考慮其對稱性，下面只給出一個方向的梯度算子分解過程。對式（4）進行x方向的求導(dǎo)，可以得該方向的梯度算子：

3.2 傅立葉變換

傅立葉變換是一種線性的積分變換，能將滿足一定條件的某個函數(shù)表示成三角函數(shù)（正弦或余弦函數(shù)）及其積分的線性組合。傅立葉變換具有多種不同變體形式如連續(xù)傅立葉變換、離散傅立葉變換。連續(xù)傅立葉變換將平方可積的函數(shù)f(t)表示成復(fù)指數(shù)函數(shù)的積分或級數(shù)形式：

式（8）將頻率域的函數(shù)F（ω）表示為時間域的函數(shù)f（t）的積分形式。在數(shù)字圖像處理領(lǐng)域，一般采用離散傅立葉變換，變換函數(shù)表示為求和形式：

其中，Xk是傅立葉振幅。

傅立葉變換可以將復(fù)雜的卷積運算轉(zhuǎn)換為簡單的乘積運算，從而提供了一種簡單的方法計算卷積。卷積定理指出：函數(shù)卷積的傅立葉變換是函數(shù)傅立葉變換的乘積。即一個域中的卷積相當(dāng)于另一個域中的乘積，例如時域中的卷積就對應(yīng)于頻域中的乘積。

對于長度為n的序列，在進行離散傅立葉變換的時候，其計算復(fù)雜度為O(n2)，而利用快速傅立葉變換將序列變換到頻域上以后，只需要一組對位乘法，總的計算復(fù)雜度為O(nlog(n) )。

4 圖像增強

在獲取了指紋圖像的方向場和指紋頻率后，需要將指紋圖像與高波濾波器進行卷積運算，對圖像進行濾波，以達(dá)到圖像增強目的。

4.1 高波濾波

高波函數(shù)形成的二維高波濾波器具有在空間域和頻率域同時取得最優(yōu)局部化的特性，能夠很好地描述對應(yīng)的空間頻率及方向選擇性的局部結(jié)構(gòu)信息，在數(shù)字圖像處理領(lǐng)域，常用于紋理圖像的分割和增強。

指紋圖像由很多平行的脊線組成，很好地定義了紋理的頻率和方向，并且在局部區(qū)域，由脊線和間隔區(qū)組成的正弦波形在方向變化上呈連續(xù)性。因此，帶通濾波器仔細(xì)調(diào)整對應(yīng)的頻率和方向，完全可以保持指紋脊線結(jié)構(gòu)，并且可以移除不需要的噪聲。高波濾波器具有的頻率選擇性和方向選擇性非常適合作為帶通濾波核增強指紋圖像。

常用的偶對稱二維高波濾波器可表示為：

其中，θ為高波濾波器的方向；uσ和vσ分別為高斯包絡(luò)在u軸和v軸上的標(biāo)準(zhǔn)差（u軸平行于θ、v垂直于θ）；ω為調(diào)制頻率。圖2是偶對稱的高波濾波核形狀。

對于長度為m、寬度為n的高波濾波器來講，用常規(guī)的卷積方法實現(xiàn)高波濾波的計算復(fù)雜度為其計算量非常大，需要進一步對高波濾波算法進行優(yōu)化。

4.2 高波濾波核分解

陳小光等[2]描述了高波濾波器的正交分解和非正交分解。本文采用了其正交分解的方法。根據(jù)式（11）將二維的高波濾波器進行正交分解：

使用按照公式（13）和（14）生成不同方向的濾波核，對指紋圖像分別進行兩次一維濾波，其時間復(fù)雜度為

5 實驗結(jié)果

在系統(tǒng)中，對指紋頻率估計階段進行簡化。根據(jù)指紋傳感器的分辨率，采用經(jīng)驗值，對頻率進行估計。在指紋脊線方向估計階段，采用可分的卷積核，將二維卷積核分解為一維卷積核，然后使用快速傅立葉變換以及逆運算實現(xiàn)普通的卷積運算，降低時間復(fù)雜度。

在高波濾波階段，將二維高波濾波器進行正態(tài)分解為兩個一維濾波器。卷積運算中，根據(jù)像素對應(yīng)的脊線方向動態(tài)選擇對應(yīng)的濾波核進行濾波。大于180°的卷積運算與反方向小于180°的方向運算結(jié)果相同，在實際卷積核制作中，只需考慮0°～180°的卷積模板的計算，從而減少系統(tǒng)的空間復(fù)雜度。每隔3度生成一對卷積核，總共生成60對卷積核。

圖2 偶對稱的高波濾波核形狀

實驗主要分成3組進行，分別使用二維卷積運算；分解后卷積運算；快速傅立葉變換三種不同的卷積方法。實驗在WINDOWS XP操作系統(tǒng)的PC機上進行，該機基本配置為2.0G主頻，512M物理內(nèi)存。實驗結(jié)果如表1所示。

表1 不同方法進行指紋圖像增強的實際測試結(jié)果

6 結(jié)論

使用具有各向異性的高波濾波器進行指紋圖像濾波，達(dá)到指紋圖像增強是指紋識別系統(tǒng)中廣泛采用的圖像增強方法。該圖像增強方法涉及大量的卷積運算，本文利用可分解的濾波器和快速傅立葉變換代替常規(guī)的卷積運算，實現(xiàn)指紋圖像的快速增強。本文提出的算法在下面幾個方面進行了優(yōu)化：

(1) 使用可分解的高斯梯度算子和快速傅立葉變換代替常規(guī)的卷積運算，有效地對指紋圖像的方向場進行估計，降低了時間復(fù)雜度；

(2) 高波濾波器帶有明顯的方向選擇性，雖然在分解后無法直接使用快速傅立葉變換實現(xiàn)常規(guī)卷積運算，但根據(jù)像素所在的脊線方向，動態(tài)選擇分解后的一維高波濾波器進行兩次濾波，同樣極大地減少了計算時間。

實驗結(jié)果表明，在經(jīng)過指紋方向場估計和高波濾波兩個階段優(yōu)化以后，本文提出的算法是非常有效的，達(dá)到了快速指紋圖像增強目的。

[1] Lin Hong, Yifei Wan, Anil Jain. Finger Image Enhancement: Algorithm And Performance Evaluation. Pattern Recognition and Image Processing Laboratory. Department of Computer Science, Michigan State University,1998: 10-11.

[2] 陳小光,封舉富.Gabor濾波器的快速實現(xiàn)[J].自動化學(xué)報,2007,33(5):457-458.

Fingerprint Image Enhancement Based on Decomposable Kernels and Fast Fourier Transforms

Huang Dongyun Zhong Zhenyu Cao Yongjun Li Weiquan
(Institute of Automation, Guangdong)

In a fingerprint verification system, enhancing fingerprint images needs lots of convolutions which take plenty of computation. Without help of any specialized digital signal processor to tackle this task, it takes a very long time for generic convolutions. There are two stages in the fingerprint image enhancement involved with heavy convolution. In this article, instead of classic methods, we use decomposable kernels and fast Fourier transforms to realize convolutions in the stages of estimating orientation field and Gabor filtering for fingerprint image enhancement, which enable us to reduce the time complexity and achieve a faster computation.

Gaussian Gradient Operator; Gabor Operator; Gabor Filtering; Convolutional Kernel Decomposition; Fast Fourier Transforms

黃東運，男，1975年生，碩士，研究方向：機器視覺、圖像識別。

鐘震宇，男，1971年生，博士，研究方向：運動控制、嵌入式系統(tǒng)。

曹永軍，男，1981年生，碩士，研究方向：運動控制、圖像識別。

黎偉權(quán)，男，1982年生，碩士，研究方向：運動控制、圖像識別。

廣東省科技計劃項目（2010A040306005，2011B010300021）；廣東省中國科學(xué)院全面戰(zhàn)略合作項目（2011B090300054）；廣東省科學(xué)院青年基金項目（qnjj20097、qnjj201014）。