改進的軟K段主曲線算法及其在指紋骨架提取中的應(yīng)用

焦 娜

(華東政法大學信息科學與技術(shù)系，上海,201620)

?

改進的軟K段主曲線算法及其在指紋骨架提取中的應(yīng)用

焦 娜

(華東政法大學信息科學與技術(shù)系，上海,201620)

主曲線是一種基于非線性變換的特征提取方法，它是通過數(shù)據(jù)分布“中間”并滿足“自相合”的光滑曲線，能較好抽取出數(shù)據(jù)的結(jié)構(gòu)特征。針對軟K段主曲線算法提取的指紋圖像的骨架結(jié)構(gòu)光滑度較差，而且提取的指紋圖像骨架經(jīng)常出現(xiàn)小圈和短枝的現(xiàn)象，本文在對軟K段主曲線算法和指紋圖像數(shù)據(jù)特點分析的基礎(chǔ)上，引入了一個新的評判函數(shù)，并提出了改進的軟K段主曲線算法，將該算法應(yīng)用在提取指紋圖像骨架上。實驗結(jié)果表明，改進的軟K段主曲線算法在提取指紋圖像骨架的效果和準確率上比原算法都有明顯提高。

指紋骨架提取；主曲線；光滑度

引 言

自動指紋識別技術(shù)已經(jīng)廣泛地應(yīng)用于公安、海關(guān)、銀行、網(wǎng)絡(luò)安全等需要進行身份識別和鑒定的領(lǐng)域[1-3]。典型的自動指紋識別系統(tǒng)主要由指紋圖像采集、指紋圖像預(yù)處理、指紋特征提取、指紋特征匹配和指紋分類識別等幾部分構(gòu)成。指紋特征提取結(jié)果直接影響指紋特征匹配和指紋分類識別的最終結(jié)果。大多數(shù)的指紋特征提取方法都對指紋圖像進行細化操作，主要在細化的指紋圖像或灰度圖像上提取指紋特征點。細化方法需要進行大量掃描、遍歷操作，并用數(shù)學形態(tài)學方法對原圖進行腐蝕、模板匹配等操作得到結(jié)果，細化方法不可避免地會產(chǎn)生錯誤細節(jié)點，最終得到的細化圖不能對指紋圖像進行準確、有效的描述，并且對指紋圖像上的指紋信息進行了有損壓縮，因此不能較好地保留指紋圖像的信息。而灰度圖像由于存在大量噪音，因此基于它提取的特征點錯誤率較高。同時，細化圖和灰度圖都以位圖形式存儲，不僅占空間，且給指紋特征點提取和辨別真?zhèn)螏碇T多不便?；谝陨显颍疚睦弥髑€方法來提取指紋圖像的信息。主曲線概念[4]是Hastie 和Stuetzle于1984年提出的，在1989年發(fā)表新的解決方案。主曲線是通過數(shù)據(jù)分布“中間”并滿足“自相合”的光滑曲線，主曲線的理論基礎(chǔ)是尋找嵌入高維空間的非歐氏低維流形，也是線性主成分的非線性推廣。主曲線可以被認為是通過數(shù)據(jù)分布“中間”的曲線，能真實反映數(shù)據(jù)的形態(tài)，即數(shù)據(jù)集合的“骨架”。如果將指紋圖像作為數(shù)據(jù)點集，那么通過數(shù)據(jù)點集的主曲線，即指紋骨架就可以較準確地描述指紋信息。

由于主曲線的這些性質(zhì)和優(yōu)點，自90年代以來在國外取得了較快的發(fā)展。1992年Banfield 和Raftery提出了 BR主曲線[5]，1999年Kegl提出了PL主曲線[6]，2000年Verbee K給出了K段主曲線算法[7]，2001 Delicado 提出了D主曲線[9]。雖然在主曲線的原理中使用了較復雜的數(shù)學知識，但由于其廣泛的應(yīng)用前景，在90年代后期已引起國外計算機科學家的關(guān)注，現(xiàn)在已報道了許多主曲線在計算機方面的應(yīng)用，如線性對撞機中對電子束運行軌跡的控制[10]、圖像處理中辨識冰原輪廓[11]、圖形檢測[12]、脫機手寫體的主曲線模板化[13]、數(shù)據(jù)可聽化[14]、模式分類[15]、票據(jù)識別[16]和智能交通[17]等。

圖1 多邊形算法和HS算法提取數(shù)據(jù)的主曲線Fig．1 PL principal curve and HS principal curve

HS主曲線算法、PL主曲線算法、BR主曲線算法和T主曲線算法共同存在的問題是：都由與固定拓撲結(jié)構(gòu)相關(guān)的局部模型的組合組成，因此當數(shù)據(jù)分布在彎曲度很大或相交曲線周圍時，這些算法性能就差，所得結(jié)果不能正確反映數(shù)據(jù)的拓撲結(jié)構(gòu)。這是由在“局部模型”中的固定拓撲結(jié)構(gòu)和差的初始化造成的。因為預(yù)先不知道需要多少“局部模型”，所以在設(shè)計算法時，只能估計“局部模型”的數(shù)量，同HS算法明確規(guī)定主曲線是不相交的。同樣，多邊形算法和T算法也由于其差的初始化，使得它們通常不能正確提取出分布在彎曲度很大或相交曲線周圍的數(shù)據(jù)的主曲線，如圖1所示。脫機手寫字符圖像具有彎曲度大和相交等特點，所以HS主曲線算法、多邊形算法和T算法都不適用來提取指紋的骨架結(jié)構(gòu)。軟K段主曲線算法[8]能克服“局部模型”的缺點，對提取出分布在彎曲度很大或相交曲線周圍的數(shù)據(jù)的主曲線效果較好。但是，軟K段主曲線算法提取的指紋圖像的骨架結(jié)構(gòu)光滑度較差，會使求取出的骨架經(jīng)常出現(xiàn)小圈和短枝的現(xiàn)象。這主要是由于：(1)軟K段主曲線算法需要預(yù)先定義線段的數(shù)量，線段的數(shù)量會直接影響提取的指紋圖像骨架結(jié)構(gòu)的效果，然而，在運行軟K段主曲線算法以前很難確切知道線段的數(shù)量,只能憑借以往的經(jīng)驗推算一個估計值；(2)指紋數(shù)據(jù)有著數(shù)據(jù)量巨大、分布分散且彎曲度很大或自相交的特點，簡單的設(shè)定線段數(shù)量較難提取光滑的指紋圖像骨架結(jié)構(gòu)。因此，本文重新定義了一個評判函數(shù)代替原軟K段主曲線算法中的預(yù)設(shè)線段數(shù)量，通過該評判函數(shù)是否收斂和目標函數(shù)共同來決定軟K段主曲線算法是否結(jié)束。實驗結(jié)果表明，改進的軟K段主曲線算法在得到的指紋圖像骨架效果上明顯優(yōu)于原軟K段主曲線算法，不僅有更光滑的指紋骨架結(jié)構(gòu)，而且能夠避免小圈和短枝且更準確地描述指紋圖像。

1 主曲線定義及原軟K段主曲線算法

1.1 主曲線定義

定義1 假設(shè)隨機向量Y=(Y1,Y2,…,Yp)的概率密度為gy(y)，則通過Y數(shù)據(jù)分布中間的一條曲線f(s)如果滿足

(1)

則稱f(s)為Y的一條主曲線。其中sf(y)為數(shù)據(jù)點y投影到曲線f(s)上s點的值，即

(2)

由主曲線定義可知：主曲線上每個點是所有投影至該點的數(shù)據(jù)點的條件均值，它滿足自相合性。主曲線的理論基礎(chǔ)是尋找嵌入高維空間的非歐氏低維流形，也是線性主成分的非線性推廣，它能真實地反映數(shù)據(jù)的形態(tài)。圖2是一個簡單的例子，從該圖中可發(fā)現(xiàn)主曲線與第一主成分相比具有兩個明顯的優(yōu)點：一方面對數(shù)據(jù)的信息保持性好；另一方面它與數(shù)據(jù)間的距離均方差小，較好地勾畫出了原始信息的輪廓。

圖2 數(shù)據(jù)第一主成份與主曲線的對照圖Fig．2 Comparison between first principal component and principal curves

1.2 原軟K段主曲線算法

算法主要有以下幾個步驟組成。

圖3 軟K段主曲線算法流程圖Fig．3 Flow-chart of soft K-segments algorithm for principal curves

步驟1 初始化

(1)讀入數(shù)據(jù)點集;(2)計算其第一主成分線;(3)設(shè)定k_max。

步驟2 插入一條新線段

如果k>k_max，則程序結(jié)束。

否則

(1)計算點xq，則求出點xq的Voronoi區(qū)域，Voronoi區(qū)域為Vq={x∈X|‖x-xq‖≤mind(x,sj),j=1,2,…，k}。

(2)計算Vq的第一主成分線，取3σ長作為新插入線段，σ2為第一主成分線的方差。

(3)k=k+1，令新插入線段為sk，sk的Voronoi區(qū)域為Vk=Φ。

步驟3 調(diào)整

調(diào)整新線段與其他線段。

步驟4 構(gòu)造優(yōu)化

2 改進的軟K段主曲線算法

2.1 原軟K段主曲線算法分析

在原軟K段主曲線算法中，線段數(shù)量的預(yù)設(shè)在整個算法中起著至關(guān)重要的作用。圖4是一個線段數(shù)量k不同導致在數(shù)據(jù)中提取骨架不同的例子，從圖4中可發(fā)現(xiàn)，在原軟K段主曲線算法中，線段數(shù)量的設(shè)定將直接影響在數(shù)據(jù)中提取骨架的效果。然而，在運行原軟K段主曲線算法以前很難確切知道線段的數(shù)量，由于初始線段數(shù)量設(shè)定的不準確，會導致得到的指紋圖像骨架結(jié)構(gòu)不夠光滑甚至出現(xiàn)小圈和短枝，不能較好地描述原始指紋數(shù)據(jù)的輪廓。

2.2 指紋圖像數(shù)據(jù)的特點

指紋數(shù)據(jù)作為一種特殊的信息載體，有很多自身的屬性，主要特點如下：(1)指紋圖像中包含大量的數(shù)據(jù)信息，一張指紋圖中經(jīng)過預(yù)處理后一般包含上萬個數(shù)據(jù)點;(2)指紋圖像中包含的數(shù)據(jù)信息分布比較分散;(3)指紋圖像中的數(shù)據(jù)形態(tài)呈現(xiàn)高彎曲度,大部分的指紋數(shù)據(jù)彎曲度都較大;(4)指紋圖像中的部分數(shù)據(jù)出現(xiàn)自相交現(xiàn)象,指紋的端點往往會出現(xiàn)這種現(xiàn)象。

圖4 不同線段數(shù)量數(shù)據(jù)設(shè)定決定不同提取骨架效果Fig．4 Structural extraction according to different line numbers

2.3 改進的軟K段主曲線算法

由于指紋數(shù)據(jù)自身的特點及原軟K段主曲線算法需要預(yù)先設(shè)定線段數(shù)量等原因，導致原軟K段主曲線算法提取的指紋圖像的骨架結(jié)構(gòu)光滑度較差，經(jīng)常出現(xiàn)小圈和短枝的現(xiàn)象。因此，本文重新定義了一個評判函數(shù)代替原軟K段主曲線算法中的預(yù)設(shè)線段數(shù)量，通過該評判函數(shù)是否收斂和目標函數(shù)共同決定軟K段主曲線算法是否結(jié)束。

算法主要由以下幾個步驟組成。

(1)初始化

?讀入數(shù)據(jù)點集X=(x1,x2,…,xn)。

?計算其第一主成分線，設(shè)初始線段s1為3σ作為初始線段的長度，s1的Voronoi區(qū)域為V1={x1,…,xn}，k=1；σ2為第一主成分線的方差。

(2)插入一條新線段

?計算點xq，該點滿足

dist(xi)-d(xi,xj)>0

dist(xi)-d(xi,xj)≤0; 1≤i,j≤n

(3)

Vq={x∈X|x-xq≤mind(x,sj)；j=1,2,…,k}

(4)

?計算Vq的第一主成分線，取3σ長作為新插入線段，σ2是第一主成分線的方差。

?K=K+1，令新插入線段為sk，sk的Voronoi區(qū)域為Vk=Φ。

(3)調(diào)整

調(diào)整新線段與其他線段。具體算法如下。

?設(shè)每條線段舊的Voronoi區(qū)域(V1,V2,…,Vk)。

?求出每條線段新的Voronoi區(qū)域。?si，i=1,…,k,求

‖xj-st‖}

(5)

圖5 子哈密爾頓路徑角度懲罰圖Fig．5 Angle penalty of sub Hamilton path

(4)構(gòu)造優(yōu)化

將k條線段構(gòu)造成一條哈密爾頓路徑，并進行優(yōu)化，算法如下：

?令p=k(p為子哈密爾頓路徑的個數(shù))，則p個子哈密爾頓路徑有2p個端點，2p個邊。

?如果p<2，停止。否則，求2p個邊的代價值c(ei)，其中c(ei)=l(ei)+λ1a(ei)；ei=(vl,vm)(vl,vm分別是兩個不同子哈密爾頓路徑的端點)；0≤λ1∈R為用戶定義的參數(shù)；l(ei)為邊ei的長度，a(ei)為角度懲罰，a(ei)=α+β，如圖5所示，連接使c(ei)最小的邊的端點，p=p-1，返回第?步。

?用2-opt的TSP(城市推銷員問題)優(yōu)化方案來優(yōu)化所形成的HP(哈密爾頓路徑)。

圖6 改進的軟K段主曲線算法流程圖 Fig．6 Flow-chart of improved soft K-segments algorithm for principal curves

(5)計算評判函數(shù)

(6)

(7)

2.4 改進的軟K段主曲線算法優(yōu)點

原軟K段主曲線算法需要預(yù)先設(shè)定線段數(shù)量，預(yù)先設(shè)定線段的數(shù)量需要人為設(shè)置或憑借經(jīng)驗值預(yù)設(shè)線段數(shù)量。不同的圖片預(yù)先設(shè)定線段數(shù)量不同，不同的人對同一張圖像預(yù)先設(shè)定的值也不同。因此原軟K段主曲線算法提取指紋的骨架圖與預(yù)先設(shè)定的線段數(shù)量密切相關(guān)。改進的軟K段主曲線算法不需要預(yù)先設(shè)定線段的數(shù)量，通過評判函數(shù)是否收斂和目標函數(shù)共同來決定軟K段主曲線算法是否結(jié)束，而不需要預(yù)先設(shè)定初始線段數(shù)量，因此減少了人為干預(yù)因素。

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

本文從FVC2000[18]指紋庫中的指紋圖片，經(jīng)過Gabor濾波和二值化處理后作為測試對象。利用改進的軟K段主曲線算法對指紋骨架進行提取，并與原軟K段主曲線算法進行了分析比較。圖7為改進的軟K段主曲線算法和原軟K段主曲線算法在自相交的指紋線交叉點、彎曲度大的指紋線的實驗結(jié)果。從效果上可以看出，利用原軟K段主曲線算法得到的指紋骨架的光滑度較差，并且小圈和短枝較多。而改進的軟K段主曲線算法在得到的指紋圖像骨架效果上明顯優(yōu)于原軟K段主曲線算法，不僅有更光滑的指紋骨架結(jié)構(gòu)，而且能夠避免小圈和短枝、更準確地描述指紋圖像。

圖7 提取指紋骨架圖的對比Fig．7 Comparison between different algorithms

4 結(jié)束語

本文以主曲線為基礎(chǔ)，對軟K段主曲線算法和指紋所分別具有的特點進行分析，提出改進的軟K段主曲線算法，并將其應(yīng)用到提取指紋骨架上去。從實驗結(jié)果看，改進的軟K段主曲線算法相對于原軟K段主曲線算法，不僅有光滑性強、準確性高等優(yōu)點，而且提取的指紋骨架中包含大量的有效信息。但還有不盡如人意的地方，如在改進的軟K段主曲線算法中的角度懲罰函數(shù)需要使用三角函數(shù)，計算量有所增加，在下一步的工作中將進行改進。

[1] 劉帥,李士進,馮鈞. 多特征融合的遙感圖像分類[J]. 數(shù)據(jù)采集與處理, 2014, 29(1):108-115.

Liu Shuai, Li Shijin, Feng Jun. Remote sensing image classification based on adaptive fusion of multiple features[J]. Journal of Data Acquisition and Processing, 2014, 29(1):108-115.

[2] 王彩云,孔一薈. 基于稀疏表示字典優(yōu)化的雷達高分辨距離像目標識別[J]. 南京航空航天大學學報, 2013, 45(6):837-842.

Wang Caiyun, Kong Yihui. Radar high-resolution range profile target recognition based on sparse representation of dictionary optimized[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2013, 45(6):837-842.

[3] Pan Feng, Wang Jiandong, Song Guangwei. Fast feature ranking and its application to face recognition[J]. Transactions of Nanjing University of Aeronautics and Astronautics, 2013, 30(4):389-396.

[4] Hastie T. Principal curves[J]. Journal of the American Statistical Association, 1989, 84(406):502-516.

[5] Banfield J D, Raftery A E. Ice floe identification in satellite images using mathematical morphology and clustering about principal curves[J]. Journal of the American Statistical Association, 1992, 87(417): 7-16.

[6] Kegl B, Krzyzak A, Linder T, et al. A polygonal line algorithm for constructing principal curves[C]∥Proceedings of Neural Information Processing System. Denver Colorado, USA: Computer Press, 1999:501-507.

[7] Verbeek J J, Vlassis N, Krose B. A K-segments algorithm for finding principal curves[J]. Computer Science of Institute, University of Amsterdam, Technical Report: Pattern Recognition Letters, 2002, 23 (8): 1009-1017.

[8] Verbeek J J, Vlassis N, Kr?se B. A soft K-segments algorithm for principal curves[J].Lecture Notes in Computer Science,2001,17(3):450-456.

[9] Delicado P. Another look at principal curves and surfaces[J]. Journal of Multivariate Analysis, 2001, 7(1):84-116.

[10]張軍平,王玨. 主曲線綜述[J]. 計算機學報, 2003, 26(2):129-146.

Zhang Junping, Wang Jue. An overview of principal curves[J]. Chinese Journal of Computers, 2003, 26(2):129-146.

[11]Bas E, Erdogmus D. Principal curves as skeletons of tubular objects: Locally characterizing the structures of axons[J]. Neuroinformatics, 2011, 9 (2/3): 181-191.

[12]Wang H N, Thomas C M L. Extraction of curvilinear features from noisy point patterns using principal curves[J]. Pattern Recognition Letter, 2008, 29 (16): 2078-2084.

[13]焦娜, 遲呈英, 苗奪謙. 基于軟K段主曲線算法的字符特征提取研究及實現(xiàn)[J]. 計算機科學, 2006, 33 (1): 229-231.

Jiao Na, Chi Chengying, Miao Duoqian. Research and implementation of structural features of characters based on a soft K-segments algorithm for principal curves[J]. Chinese Journal of Computer Science, 2006, 33 (1): 229-231.

[14]Reinhard K, Niranjan M. Parametric subspace modeling of speech transitions[J]. Speech Communication, 1999, 27 (1): 19-42.

[15]Zhang J P, Wang X D, Kruger U,et al. Principal curve algorithms for partitioning high-dimensional data spaces[J]. IEEE Transactions on Neural Networks, 2011,22 (3): 367-380.

[16]Zhang H Y, Miao D Q, Xia F C, et al. Automatic recognition system of bills based on principal curves[J]. Journal of Information and Computational Science, 2004, 1 (2): 199-204.

[17]Zhang J P, Chen D W, Kruger U. Adaptive constraint K-segment principal curves for intelligent transportation systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2008, 9 (4): 666-677.

[18]Fingerprint verification competition(FVC2000)[EB/OL]. http://bias.csr.unibo.it/fvc2000/download.asp， 2000-9-14.

Improved Soft K-Segments Algorithm for Principal Curves and Its Applications on Fingerprint Skeletonization Extraction

Jiao Na

(Department of Information Science and Technology, East China University of Political Science and Law, Shanghai, 201620, China)

Principal curves are a feature extraction method based on the nonlinear transformation. Meanwhile, they are smooth self-consistent curves that pass through the ″middle″ of the distribution and satisfy the ″self coincidence″. Thus, structural features of the data can be extracted. Based on the soft K-segments algorithm for principal curves, the skeletonization extraction of the fingerprint image is not smooth enough, which often appears small circle and short branches. To solve this proplem, the soft K-segments algorithm for principal curves and the specialties of fingerprint are analyzed. A new evaluation function is also proposed. And an improved soft K-segments algorithm for principal curves is put forward. Compared with those of the original algorithms, the smoothness and the accuracy of the proposed algorithm can be illustrated by experiments.

fingerprint skeletonization extraction; principal curves; smoothness

國家社科基金(13CFX049)資助項目；上海高校青年教師培養(yǎng)資助計劃(hdzf10008)資助項目。

2014-03-25；

2014-05-15

TP391.4

A

焦娜(1977-)，女,博士,講師,研究方向：模式識別、人工智能、數(shù)據(jù)挖掘、粗糙集等，E-mail:zdx.jn@163.com。