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

（廣東省自動(dòng)化研究所）

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

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

（廣東省自動(dòng)化研究所）

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

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

1 引言

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

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

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

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

2 指紋圖像增強(qiáng)過程

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

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

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

3 方向場(chǎng)估計(jì)

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

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

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

3.1 高斯梯度算子

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

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

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

3.2 傅立葉變換

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

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

其中，Xk是傅立葉振幅。

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

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

4 圖像增強(qiáng)

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

4.1 高波濾波

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

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

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

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

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

4.2 高波濾波核分解

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

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

5 實(shí)驗(yàn)結(jié)果

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

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

圖2 偶對(duì)稱的高波濾波核形狀

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

表1 不同方法進(jìn)行指紋圖像增強(qiáng)的實(shí)際測(cè)試結(jié)果

6 結(jié)論

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

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

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

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

[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濾波器的快速實(shí)現(xiàn)[J].自動(dòng)化學(xué)報(bào),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

黃東運(yùn)，男，1975年生，碩士，研究方向：機(jī)器視覺、圖像識(shí)別。

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

曹永軍，男，1981年生，碩士，研究方向：運(yùn)動(dòng)控制、圖像識(shí)別。

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

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