嵌入式PPC平臺(tái)指紋識(shí)別算法優(yōu)化及實(shí)現(xiàn)_圖文

1、微 處 理 機(jī)M I CROPROCESS ORS嵌入式 PPC 平臺(tái)指紋識(shí)別算法優(yōu)化及實(shí)現(xiàn) 朱禮波 , 付宇卓 , 謝 憬(上海交通大學(xué) , 上海 200240 摘 要 :在現(xiàn)有指紋識(shí)別算法的基礎(chǔ)上 , 根據(jù)嵌入式的特點(diǎn) , 通過(guò)軟件算法的加速以及系統(tǒng)硬 件的配置優(yōu)化來(lái)實(shí)現(xiàn)板級(jí)的指紋識(shí)別系統(tǒng) 。通過(guò)交叉編譯器把二進(jìn)制代碼轉(zhuǎn)化為適合于 power 2 pc405core 類型的數(shù)據(jù) , 采用 S DK 工具 Xilinx XUP V irtex -II Pr o Devel opment Syste m 開發(fā)板協(xié)同仿 真 。 在軟件算法加速優(yōu)化的基礎(chǔ)上速度得到了很大的提高 。關(guān)鍵詞 :指紋識(shí)別

2、 ; PPC 處理器 ; 嵌入式 ; 軟件加速中圖分類號(hào) :TP391 文獻(xiàn)標(biāo)識(shí)碼 :A 文章編號(hào) :1002-2279(2009 05-0082-04The I m p l em en ta ti o n and A rithm e ti c I m p r o en o f F r ti ngu ish o n the P PC P l a tfo r m i n SZ -bo,(School U , Shanghai 200240, China the p arithmetic, according t o the characteristic of e mbed the syste m

3、 of finger p i p le mented . B inary code is converted by cr oss -comp iler t o the kind of data fitful f or pc405core . U sing the t ool of S DK -Xilinx XUP V irtec -II Pr o Devel opment Syste m devel opment board does HW /S W co si m ulati on . The s peedup of s oft w are arith metic and the confi

4、gurati on of hard ware i m p r ove the perf or mance of finger p rint distinguish .Key words:Finger p rint; PPC; Embed; Soft w are s peed -up1 引 言近年來(lái) , 越來(lái)越多的個(gè)人 、 消費(fèi)者 、 公司和政府 機(jī)關(guān)都認(rèn)為現(xiàn)有的基于智能卡 、 身份證號(hào)碼和密碼 的身份識(shí)別系統(tǒng)很繁瑣而且并不十分可靠 。 生物識(shí) 別技術(shù)為此提供了一個(gè)安全可靠的解決方案 。 其中 指紋識(shí)別技術(shù)是目前最為成熟的 、 應(yīng)用也最為廣泛 的生物識(shí)別技術(shù) 。 每個(gè)人的包括指紋在內(nèi)的皮膚紋 路

5、在圖案 、 斷點(diǎn)和交叉點(diǎn)上各不相同 , 也就是說(shuō) , 這 些指紋特征是唯一的 , 并且終生不變 。依靠這種唯 一性和穩(wěn)定性 , 就可以把采集到的指紋同預(yù)存的指 紋對(duì)應(yīng)起來(lái) , 通過(guò)對(duì)采集的指紋和預(yù)先保存的指紋 進(jìn)行比較 , 就可以驗(yàn)證出被檢查人的真實(shí)身份 。雖 然基于 DSP 或者 ARM 的指紋識(shí)別論證系統(tǒng)已經(jīng)在 考勤 、 門禁等領(lǐng)域?qū)崿F(xiàn)商品化 , 但這樣的嵌入式系統(tǒng) 很難實(shí)現(xiàn)小型化集成化 , 更無(wú)法 S OC, 所以本文采用 基于 Xilinx FPG A 來(lái)實(shí)現(xiàn)指紋識(shí)別論證系統(tǒng) , 利用 FPG A 高集成度 , 低功耗 , 短開發(fā)周期等優(yōu)點(diǎn) , 具有 很強(qiáng)的現(xiàn)實(shí)意義和廣闊的市場(chǎng)空間 。

6、 2 指紋識(shí)別技術(shù)原理以及算法介紹指紋識(shí)別技術(shù)的原理與其他生物識(shí)別技術(shù)的原 理類似 。 它是利用人體的指紋特征對(duì)個(gè)體身份進(jìn)行 區(qū)分和鑒定 。 指紋識(shí)別的關(guān)鍵在于識(shí)別指紋的總體 特征和局部特征 。指紋識(shí)別技術(shù)主要涉及四個(gè)功能 :讀取指紋圖 像 、 提取特征 、 保存數(shù)據(jù)和比對(duì) 。在一開始 , 通過(guò)指 紋讀取設(shè)備讀取到人體指紋圖像并對(duì)其進(jìn)行初步的 處理 , 使之更加清晰 。 接下來(lái) , 指紋辨識(shí)軟件建立指 紋的數(shù)字表示 特征數(shù)據(jù) , 一種單方向的轉(zhuǎn)換 , 可 以從指紋轉(zhuǎn)換成為特征數(shù)據(jù) , 但不能從特征數(shù)據(jù)轉(zhuǎn) 換成指紋 , 通常稱其為模版 。最后通過(guò)計(jì)算機(jī)模糊 比較的方法 , 將兩個(gè)指紋的模版進(jìn)行比

7、較 , 計(jì)算出它 們的相似程度 , 最終得到兩個(gè)指紋的匹配結(jié)果 , 具體 的流程如圖 1所示 。指紋識(shí)別算法主要包括如下幾個(gè)步驟 :指紋圖 像導(dǎo)入與格式轉(zhuǎn)換 、 圖像軟化操作 、 計(jì)算指紋圖像脊 線的方向 、 計(jì)算指紋脊線的頻率 、 獲取圖像的有效區(qū)作者簡(jiǎn)介 :朱禮波 (1984- , 男 , 江蘇省響水縣人 , 碩士研究生 , 主研方向 :計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)。 收稿日期 :2008-08-26第 5期 2009年 10月 No . 5 Oct . , 2009 朱禮波等 :嵌入式 PPC 平臺(tái)指紋識(shí)別算法優(yōu)化及實(shí)現(xiàn)域 、 指紋圖像增強(qiáng) 、 圖像二值化 、 細(xì)化指紋圖像 、 從細(xì) 化圖像中提取細(xì)節(jié)

8、點(diǎn)并儲(chǔ)存到集合中 、 在圖像中畫 出細(xì)節(jié)點(diǎn) 、 判斷指紋是否匹配 。 如圖 2所示。 圖 1指紋識(shí)別步驟 圖 2 指紋識(shí)別算法3 系統(tǒng)搭建與算法優(yōu)化系統(tǒng)的搭建與算法優(yōu)化主要包括硬件平臺(tái)搭 建 、 軟件算法介紹 、 算法裁減及加速算法 、 以及算法 實(shí)現(xiàn)優(yōu)化這四部分 。 3. 1 硬件平臺(tái)搭建系統(tǒng)采用 Xilinx X UP V irtex -II Pr o Devel opment Syste m 開發(fā)板搭建。 采用內(nèi)嵌的 po wper pc405core 和相關(guān)的必要外部設(shè)備。 包括 UART, DDRA M 片內(nèi)數(shù) 據(jù)與指令 BRA M, 快速 P LB 總線 , 慢速 OP B 總線。

9、 UART 的作用在于與外界通信 , 負(fù)責(zé)把比特流文件下載到 FPG A 開發(fā)板上 ; DDRA M 負(fù)責(zé)存儲(chǔ)程序 ; 片內(nèi) 的數(shù)據(jù)與指令 BRAM 起到 CACHE 的功能 , 所以把 常需要用到的數(shù)據(jù)與指令放到數(shù)據(jù)與指令 BRAM , 可以加快程序的運(yùn)行 ; 快速總線 P LB 連接快速設(shè) 備 ; 慢速總線 OP B 則連接外圍的慢速設(shè)備 , 這樣可 以降低功耗 , 使接口簡(jiǎn)單化 。 系統(tǒng)結(jié)構(gòu)如圖 3所示 。 3. 2 算法介紹如圖 2所示 , 指紋識(shí)別算法各步驟主要的作用 如下 :步驟一 主要實(shí)現(xiàn)指紋圖像的導(dǎo)入 , 格式轉(zhuǎn)換 , 大小處理 ;步驟二 主要實(shí)現(xiàn)圖像軟化操作 , 對(duì)導(dǎo)入圖像進(jìn)

10、行第一次處理 , 柔化象素值 , 減少部分噪聲;圖 3 硬件結(jié)構(gòu)圖;, 有 , 運(yùn)行速度慢 , 有效區(qū)小 , 速度快 ;步驟六 指紋圖像增強(qiáng)算法 , 該增強(qiáng)算法針對(duì)指 紋圖像設(shè)計(jì) , 它標(biāo)記了指紋圖像中沒(méi)有使用的區(qū)域 , 而其它的區(qū)域 , 在增強(qiáng)后 , 脊線可以被清晰的分離出 來(lái) (使用一個(gè)閾值 。該算法生成了一個(gè)脊線方向 圖 , 一個(gè)掩碼圖 ;步驟七 圖像二值化 , 將圖像數(shù)據(jù)通過(guò)閾值轉(zhuǎn)化 為 0x00和 0xFF 的集合 ;步驟八 細(xì)化指紋圖像 , 使用“ H it and M iss ” 結(jié) 構(gòu)元素 。 圖像必須是二值化過(guò)的 (只包含 0x00或 0xFF , 該算法的缺點(diǎn)是產(chǎn)生很多偽造

11、的線條 (偽特 征 , 必須由另外的算法來(lái)消除 , 后處理非常必要 ; 步驟九 從細(xì)化圖像中提取細(xì)節(jié)點(diǎn) , 并儲(chǔ)存到集 合中 ;步驟十 在圖像中畫出細(xì)節(jié)點(diǎn) , 不改變背景 ; 步驟十一 判斷指紋是否匹配 3. 3 算法裁減及加速算法算法裁減方面包括 :去除步驟四中的低通以及 步驟六的圖像增強(qiáng) , 該增強(qiáng)算法針對(duì)指紋圖像設(shè)計(jì) , 它標(biāo)記了指紋圖像中沒(méi)有使用的區(qū)域 , 而其它的區(qū) 域 , 在增強(qiáng)后 , 利用分析并設(shè)置閾值 , 脊線可以被清 晰的分離出來(lái) 。 首先建立步驟評(píng)估體系 , 主要包括 運(yùn)行時(shí)間以及對(duì)細(xì)節(jié)點(diǎn)數(shù)目的影響程度 。 由于最終 指紋匹配與否是通過(guò)對(duì)比細(xì)節(jié)點(diǎn)來(lái)實(shí)現(xiàn)的 , 因此裁 減的依

12、據(jù)為去掉那些占據(jù)較長(zhǎng)的運(yùn)行時(shí)間并且沒(méi)有 對(duì)最終提取到的細(xì)節(jié)點(diǎn)數(shù)目有明顯影響的步驟 。 另外由于步驟三獲取指紋圖像脊線的方向 , 含 有大量的循環(huán) 、 浮點(diǎn) 、 三角運(yùn)算 ; 步驟四計(jì)算指紋脊38 5期 微 處 理 機(jī) 線的頻率 , 含有大量的循環(huán) 、 數(shù)組 、 浮點(diǎn) 、 三角運(yùn)算 ,是影響系統(tǒng)動(dòng)作速度的主要方面 。 所以在算法裁減 的基礎(chǔ)上 , 通過(guò)對(duì)主要步驟中的核心程序進(jìn)行理解 , 采取算法加速來(lái)提高系統(tǒng)運(yùn)行速度 。加速算法包括 :浮點(diǎn)定點(diǎn)化 , 數(shù)學(xué)函數(shù)重新編 寫 。 由于浮點(diǎn)運(yùn)算在硬件實(shí)現(xiàn)上有相當(dāng)大的難度 , 不僅占用的系統(tǒng)資源較多 , 而且硬件運(yùn)行的速度也 較慢 , 無(wú)法滿足運(yùn)行時(shí)間上

13、的要求 , 所以需要浮點(diǎn)定 點(diǎn)化 。浮點(diǎn)定點(diǎn)化的主要思想是以可以忍受的精度損 失來(lái)點(diǎn)定化以進(jìn)行運(yùn)算 ; 這其中的關(guān)鍵就是由程序 員來(lái)確定一個(gè)數(shù)的小數(shù)點(diǎn)處于 16位中的哪一位 。 這就是數(shù)的定標(biāo) 。數(shù)的定標(biāo)有 Q 表示法 , 不同的 Q 所表示的數(shù)不僅范圍不同 , 而且精度也不相同 。 Q 越大 , 數(shù)值范圍越小 , 但精度越高 ; 相反 , Q 越小 , 數(shù) 值范圍越大 , 但精度就越低。 , Q0-32768到 +1, 為 -1到 0. 。 在 本系統(tǒng)中 , , 最終使用 Q8精度 , 精確到 1/256=0. 00390625。 例如 :浮點(diǎn)數(shù) (x 轉(zhuǎn)換為定點(diǎn)數(shù) (x p :x q =(

14、int x ×2Q定點(diǎn)數(shù) (x q 轉(zhuǎn)換為浮點(diǎn)數(shù) (x :x =(float x q ×2-Q設(shè) x =0. 5001, y =3. 1, 則浮點(diǎn)運(yùn)算結(jié)果為 :z =x +y =0. 5001+3. 1=3. 6001Qx =8, Qy =8, Qz =8則定點(diǎn)加法為 :x =128; y =794; z =922因?yàn)?z 的 Q 值為 9, 所以定點(diǎn)值 z =922即為浮 點(diǎn)值 z =(floa t 922/256=3. 6015625。由于嵌入式中調(diào)用數(shù)學(xué)函數(shù)的能力不強(qiáng) , 所以 在調(diào)用數(shù)學(xué)函數(shù)如 sin ( , cos ( 的地方用自己寫的 sinx ( , cosx

15、 ( 來(lái)替代 。最后系統(tǒng)運(yùn)行的速度得到 很大的提高 , 提高了五倍以上 , 二分鐘可以出來(lái)結(jié) 果 。 3. 4 算法實(shí)現(xiàn)優(yōu)化系統(tǒng)的軟硬件協(xié)同調(diào)試主要使用 Xilinx XPS 和 S DK 工具完成 。軟硬協(xié)調(diào)主要注意的問(wèn)題是 link scri p t 的設(shè)置 。 這是很重要的一步 , 包括設(shè)置程序存 儲(chǔ)位置 , stack, heap 大小和所放位置 。 Stack 主要負(fù) 責(zé)函數(shù)調(diào)用 , 而 heap 負(fù)責(zé)函數(shù)中動(dòng)態(tài)申請(qǐng)內(nèi)存 。考 慮速度的緣故 , 在本系統(tǒng)中使用了如下二種方案 :方案一 程序存放在 BRAM 中 , 經(jīng)過(guò)精簡(jiǎn)優(yōu)化后的程序大小不到 100k, 可以放入 128K 的 BR

16、AM , 由于 BRAM 訪問(wèn)速度比 DDR 的訪問(wèn)速度要快很多 , 并且在運(yùn)行中會(huì)多次調(diào)用該程序 , 因此將程序存放 在 BRAM 中可以提高速度 。方案二 程序 、 stack 、 heap 全都放在 DDR 中 , 這 樣的話 , 保證程序能夠正常運(yùn)行 , 但是速度比較慢 , 在不進(jìn)行算法修改 , 硬件加速的情況下 , 這種方法比 較可行 。4 系統(tǒng)調(diào)試與結(jié)果分析4. 1 系統(tǒng)調(diào)試經(jīng)過(guò)分析各個(gè)步驟的時(shí)間消耗 , 選擇從數(shù)據(jù)讀 圖 , 先 要 從 外 部 , 和 S DRAM 交 換 。由 于 CP U 訪 問(wèn) 片 外 S DRAM 的速度比較慢 , 這一過(guò)程將占用大量的 CP U 時(shí)間

17、。 為了提高識(shí)別速度 , 本系統(tǒng)考慮采用 DMA 方式加速這一過(guò)程 。在系統(tǒng)中加入一個(gè) DMA 控制 器和一塊片內(nèi)的 BRAM , 通過(guò) CP U 控制 DMA 直接 把外部 S DRAM 中的圖像數(shù)據(jù)讀取到片內(nèi) BRAM 中 , 然后對(duì)此數(shù)據(jù)流進(jìn)行處理 。由于 DMA 操作幾 乎不消耗 CP U 時(shí)間 , 而 CP U 訪問(wèn) BRAM 的時(shí)間消 耗明顯小于 CP U 訪問(wèn)片外 S DRAM 的時(shí)間消耗 , 這 一策略將有效提高識(shí)別速度 。在 CP U 對(duì) 指 紋 圖 像 預(yù) 處 理 的 各 個(gè) 步 驟 中 , Gabor 濾 波是圖象增強(qiáng)部分的核心 , 也是圖象增強(qiáng)部 分乃至整個(gè)指紋圖像預(yù)處

18、理過(guò)程中運(yùn)算量最大 、 消 耗 CP U 時(shí)間最多的一步 , 因此考慮將 Gabor 濾波器 硬件化以降低 CP U 時(shí)間開銷 。 4. 2 實(shí)驗(yàn)與結(jié)果分析打開 E DK 工具 , xp s 8. 2i, 加載 test 文件夾中的 syste m. x mp 工程 , 下載 bitstrea m 到 V irtex -II Pr o 開發(fā)板 , 在 cons ole window 有相應(yīng)的提示 , 并在終端 中看到輸出 , 打開 S DK, 并根據(jù) verify 文件夾中的指 紋檢測(cè)程序建立工程 , 對(duì) L inker Scri p t 進(jìn)行配置 , 運(yùn) 行 debug, 并 在 X ML

19、cons ole 框中 輸 入 dow -data 0x0aaa0000out128. txt, 點(diǎn)擊 resu me 鍵 , 并注意終端 中的輸出結(jié)果 , 如圖 4所示 。多次運(yùn)行 , 對(duì)比如圖 5所示 , 給出具體分析內(nèi)容 與結(jié)論 。目前 , 市場(chǎng)上主流的指紋對(duì)比速度為 1. 5S/枚 左右 。 如深圳千里馬出品的指紋考勤門禁機(jī) , 中科 48 2009年 朱禮波等 :嵌入式 PPC 平臺(tái)指紋識(shí)別算法優(yōu)化及實(shí)現(xiàn)院的嵌入式指紋自動(dòng)識(shí)別模塊 。通過(guò)對(duì)比可以發(fā) 現(xiàn) , 經(jīng)過(guò)軟件算法級(jí)加速以及具體實(shí)現(xiàn)的加速 , 指紋 檢測(cè)速度已經(jīng)達(dá)到了與市場(chǎng)上同一數(shù)量級(jí)。 圖4 最終板上運(yùn)行結(jié)果 圖 5 運(yùn)行結(jié)果

20、對(duì)比5 結(jié) 束 語(yǔ)上述比較詳細(xì) 、 系統(tǒng)地闡述了如何在嵌入式中 實(shí)現(xiàn)指紋識(shí)別系統(tǒng) 。 從算法的分析 、 硬件平臺(tái)搭建 、 算法級(jí)優(yōu)化到算法優(yōu)化實(shí)現(xiàn) 。 軟件方面通過(guò)浮點(diǎn)定 點(diǎn)化 、 去除多余步驟 、 數(shù)學(xué)函數(shù)重新編寫來(lái)加快程序 運(yùn)行的速度 ; 硬件中數(shù)據(jù)讀取方面采用加入 DMA 模塊 , 而在數(shù)據(jù)處理方面可以考慮采用一個(gè)流水線 型 16×16位乘法器 , 一個(gè) 32×8位乘法器和一個(gè)流 水線型 32位除法器 , 以提高系統(tǒng)工作效率 。 指紋識(shí) 別系統(tǒng)的應(yīng)用非常廣泛 , 幾乎所有對(duì)安全性有要求 的場(chǎng)合都可以用到 , 具有廣闊的應(yīng)用前景 。參考文獻(xiàn) :1 He, J ie I

21、EEE, L iang L i,and . Analysis of Lo 2rehensive f Finger p rintMatc 2I ons on system s, man, and cyber 2B:cybernetics, 2007, 37(5 :1204-1211. 2 戴平陽(yáng) . 指紋識(shí)別技術(shù)研究進(jìn)展 D.廈門 :廈門大學(xué) ,2002. 3 盧朝陽(yáng) , 張崗山 , 劉琳 . 指紋識(shí)別系統(tǒng)性能評(píng)價(jià)方法D.西安 :西安電子科技大學(xué) , 2002. 4 羅希平 , 田捷 . 自動(dòng)指紋識(shí)別中的圖像增強(qiáng)和細(xì)節(jié)匹配算法 J .軟件學(xué)報(bào) , 2002, 13(5 :946-956. 5 劉

22、旭 , 田捷 . 自動(dòng)指紋識(shí)別算法在嵌入式系統(tǒng)上的實(shí)現(xiàn) J .計(jì)算機(jī)工程與應(yīng)用 , 2002, 38(21 :120-122.(上接第 81頁(yè) 10 Dom ingos P . Pr os pects and challenges f or multi -rela 2ti onal data m ining J .AC M SI GK DD Exp l orati ons Ne wsletter archive vol . 5, Issue 1. Ne w York:AC M Press, 2003:80-83.11 Z HU M iao -liang, Q I U Yu . A Survey

23、 of Mobile AgentSYS TE M J .Journal of Computer Research and Devel opment, 2001, 38(1 :15-25.12 H B l ockeel, L De Raedt . T op -down inducti on of firstorder l ogical decisi on trees J .A rtificial I ntelligence, 1998, 101(1-2 :285-297.13 L De Raedt, H B l ockeel, L Dehas pe,W Van Laer . ThreeCompa

24、ni ons f or Data M ining in First O rder LogicJ .I n 4, 2001. :105-139.14 S Kra mer . Structural regressi on treesC .I n Pr oceedingsof the Thirteenth Nati onal Conference on A rtificial I ntel 2ligence, pages 812-819. M I T Press, Ca mbridge, MA, 1996.15 S Kramer, G W id mer . I nducing Classificat

25、i on andRegressi on Trees in First O rder Logic J .I n 4, 2001:140-159.16 J Quinlan . C4. 5:Pr ogram s f or M achine Learning M.Morgan Kauf mann, San Francisco, CA, 1993.17 張偉 , 楊炳儒 , 宋威 . 多關(guān)系數(shù)據(jù)挖掘研究綜述 J .計(jì)算機(jī)工程與應(yīng)用 , 2006.18 J Knobbe, A Siebes, Van derW allen, D. M. G . Multi -relati onal decisi on tr

26、ee inducti on C .I n Pr oceedings ofthe 3rdEur opean Conference on Princi p les and Practiceof Knowledge D iscovery in Databases, PK DD 99, 1999.19 Fayyad U M , Irani K B. On the handling of continuous -valued attributes in decisi on tree generati onJ .Machine Learning, vol . 8, 1992.20 Quinlan J R. I m p r oved U se of Continuous A ttributes inC4. 5J .Journal of A rtificial I ntelligence Research, vol .