Một thuật toán cải tiến cho đánh giá tần số vân cục bộ của ảnh vân tay

T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1 (45) T ập 2/N¨m 2008 MỘT THU ẬT TOÁN C ẢI TI ẾN CHO ĐÁNH GIÁ TẦN S Ố VÂN C ỤC B Ộ CỦA ẢNH VÂN TAY Ngô Qu ốc T ạo (Vi ện Công ngh ệ Thông tin - Vi ện KH&CN Vi ệt Nam ) Đào Thanh Khi ết - Bùi Đức Giang (Tr ường ĐH Công ngh ệ - ĐHQG Hà N ội) 1. Gi ới thi ệu Ảnh vân tay bao g ồm các đường vân có h ướng, được phân cách b ởi các rãnh vân. Trong một vùng vân tay nh ỏ, n ếu không có s ự xu ất hi ện c ủa các minutiae và các điểm đặ c bi ệt, thì các đường vân và rãnh vân song song v ới nhau, t ạo nên m ột hình sóng có h ướng và t ần s ố ổn đị nh. Do v ậy h ướng vân c ục b ộ và t ần s ố vân c ục b ộ là hai thu ộc tính n ội t ại c ủa ảnh vân tay. Đây là các tham s ố chính cho các quá trình x ử lý vân tay. O’Gorman và Nickerson (1988, 1989) đã dùng các b ộ l ọc d ải thông để nâng cao ảnh vân tay [2, 3]. Hong, Wan, Jain (1998) s ử d ụng b ộ lọc Gabor để nâng cao ảnh [1]. Các thu ật toán này đều l ấy tham s ố là h ướng và t ần s ố vân c ục bộ. N ếu t ần s ố vân c ục b ộ được đánh giá không chính xác, thì s ẽ d ẫn đế n k ết qu ả t ạo ra các đường vân sai, ho ặc làm m ất các chi ti ết c ủa ảnh vân tay. Do đó m ột thu ật toán đánh giá t ần s ố vân tin c ậy là r ất h ữu ích cho quá trình x ử lý vân tay hi ệu qu ả. Hong, Wan, Jain đã đề xu ất thu ật toán s ử d ụng x-signature để đánh giá t ần s ố c ục b ộ c ủa đường vân. Thu ật toán tìm các đỉnh c ủa x-signature và tính kho ảng cách trung bình gi ữa các đỉ nh này, tần s ố c ục b ộ thu được là ngh ịch đả o c ủa kho ảng cách trung bình [1]. Ph ươ ng pháp này đơ n gi ản và có độ ph ức t ạp tính toán th ấp, tuy nhiên r ất khó để tìm các đỉnh c ủa x-signature khi có nhi ễu. Trong bài báo này, chúng tôi đề xu ất m ột thu ật toán c ải ti ến, nh ằm h ạn ch ế t ối đa ảnh h ưởng c ủa nhi ễu. 2. Ph ươ ng pháp đánh giá t ần s ố vân c ục b ộ c ủa Hong, Wan, Jain (1998) Tần s ố vân c ục b ộ là khác nhau v ới các vân tay khác nhau, và c ũng có th ể khác nhau đố i với các vùng khác nhau trong cùng m ột vân tay. Hong, Wan, Jain đã đánh giá t ần s ố vân c ục b ộ bằng cách đế m s ố pixel trung bình gi ữa hai đỉ nh c ấp xám c ủa hai đường vân liên ti ếp nhau [1] (g ọi t ắt là thu ật toán HWJ). T ần s ố fij tại x( i y, j ) được tính nh ư sau: hướng vân c ục b ộ kh ối 16 x 16 cửa s ổ 32 x 16 x-signature Hình 1. Minh h ọa kh ối vân tay và x-signature . 68 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1 (45) T ập 2/N¨m 2008 1. Chia ảnh vân tay thành các kh ối w x w (16 x 16). 2. V ới m ỗi kh ối có tâm là x( i y, j ) , ta định ngh ĩa m ột c ửa s ổ l x w (32x16) có h ướng, cũng có tâm là x( i y, j ) , được đặ t sao cho h ướng chi ều r ộng trùng v ới h ướng c ủa đường vân t ại vùng lân c ận c ủa x( i y, j ) (xoay h ệ t ọa độ sao cho tr ục y trùng v ới h ướng vân c ục b ộ). 3. V ới m ỗi kh ối có tâm là x( i y, j ) , tính x-signature={X 0,X 1,…,X l-1}, là t ổng các c ấp xám được tích l ũy theo tr ục x trong c ửa s ổ. Cách làm này có tác d ụng lo ại b ỏ ảnh h ưởng c ủa các nhi ễu nh ỏ, giúp s ự tích l ũy c ấp xám được làm tr ơn h ơn. C ụ th ể ta có: w− 1 =1 = − Xk ∑ G(u, v), k 0,1,...,l 1 w d= 0 w l u= x + (d − )cosO(x , y ) + (k − )sin O(x , y ) i2 i j 2 i j (1) w l v= y + (d − )sin O(x , y ) − (k − )cosO(x , y ) j2 i j 2 i j với O là b ản đồ h ướng, và O(x i,y j) là h ướng t ại điểm (x i,y j). 4. fij được tính b ằng ngh ịch đả o c ủa kho ảng cách trung bình gi ữa hai đỉ nh liên ti ếp c ủa x-signature. Nếu không có các minutiae và các điểm đặ c bi ệt xu ất hi ện trong c ửa s ổ h ướng, thì x- signature s ẽ hình thành m ột sóng d ạng sin r ời r ạc và có cùng t ần s ố v ới các đường vân và rãnh vân trong c ửa s ổ đó. G ọi T ij là kho ảng cách trung bình gi ữa hai đỉ nh liên ti ếp c ủa x-signature, = 1 khi đó t ần s ố f ij được tính nh ư sau: fij (2) Tij Nếu không có đỉ nh nào được tìm th ấy trong x-signature, thì t ần s ố được gán giá tr ị -1 để phân bi ệt v ới các t ần s ố đúng khác. Thu ật này đơ n gi ản và nhanh. Tuy nhiên, nh ược điểm là khó tìm được hai đỉ nh c ấp xám liên ti ếp nhau trong các ảnh vân tay có nhi ễu. Trong tr ường h ợp này, tác gi ả g ợi ý dùng m ột n ội suy và b ộ l ọc thông th ấp. 3. Nh ận xét và đề xu ất Để th ấy rõ h ơn nh ượ c điểm c ủa thu ật toán đánh giá t ần s ố c ục b ộ HWJ, ta xét m ột ví d ụ đơ n gi ản c ủa x-signature nh ư sau: 8 7 6 5 4 3 x-signature 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 position Hình 2: Bi ểu đồ minh h ọa ví d ụ c ủa x-signature. 69 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1 (45) T ập 2/N¨m 2008 Nhìn hình 3.9, ta th ấy x-signature có d ạng hình sin v ới chu k ỳ là 6, và có m ột điểm nhi ễu ở v ị trí 13. Tuy nhiên theo thu ật toán HWJ, ta s ẽ tìm được 4 đỉ nh ở các v ị trí 4, 10, 13, 16. Nên kho ảng cách trung bình thu được giữa hai đỉ nh liên ti ếp là 4. Nói cách khác chu k ỳ c ủa x- signature thu được t ừ HWJ là 4, không đúng v ới chu k ỳ th ật. b 8 6 4 2 b/2 x-signature 0 x0 1 2 3 4 5 6 7 8 9 10111213141516171819 position Hình 3: Minh h ọa c ửa s ổ K. Nh ằm kh ắc ph ục nh ược điểm c ủa thu ật toán HWJ, tôi đề xu ất m ột thu ật toán c ải ti ến nâng cao độ chính xác c ủa t ần s ố tìm được khi có ảnh h ưởng c ủa nhi ễu. Để thu ận ti ện, ta đặ t f=x-signature. Thu ật toán gi ả s ử f(x) là m ột hàm có d ạng hình sin. Ta s ử d ụng m ột c ửa s ổ K có a) Thu ật toán gửi/nh ận lệnh/d ữ li ệu của PC b )Thu ật toán gửi/nh ận lệnh/d ữ li ệu của nút mạng độ r ộng là b, cho tr ượt trên f(x). V ị trí c ủa c ửa s ổ K là m ột điểm x 0 sao cho v ới ∀ ∈[ − + ] ∈ x x0 b / 2, x 0 b / 2 thì x K. T ại m ỗi v ị trí x 0 của K, g b(x 0) được đị nh ngh ĩa là t ổng t ất c ả các f(x) v ới x ∈K: + x0 b / 2 = gb (x 0 )∑ f (x) (3) − x0 b / 2 Nếu f(x) có d ạng hình sin và v ới b nh ỏ hơn chu k ỳ c ủa f(x), ta có m ột s ố nh ận xét v ề gb(x) nh ư sau: - Hàm g b(x) c ũng có d ạng sin. - Tần s ố c ủa gb(x) gi ống tần s ố của hàm f(x). - Với m ọi x0, nếu gb(x 0) đạt giá tr ị c ực đạ i, thì f(x 0) cũng đạ t giá tr ị c ực đạ i. - gb(x) có hình d ạng tr ơn h ơn f(x), ngh ĩa là gb(x) ít b ị ảnh h ưở ng b ởi nhi ễu h ơn so v ới f(x). - Với b=T/2, T là chu k ỳ c ủa f(x), thì biên độ c ủa gb(x) đạ t giá tr ị c ực đạ i. Để ch ứng minh nh ận xét là đúng đắn, gi ả s ử f(x) là liên t ục, và f(i)=x-signature(i). Hàm f(x) có d ạng nh ư sau: f (x)= a(sin( ω x) + 1) + n(x) (4) Sở d ĩ c ộng thêm 1 để f (x)≥ 0 ∀x . a: biên độ của f(x), a≥ 0 70 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1 (45) T ập 2/N¨m 2008 2π ω: t ần s ố góc c ủa f(x) và ω = , trong đó T là chu k ỳ c ủa f(x). T n(x): nhân t ố nhi ễu Khi đó t ại m ỗi v ị trí x 0, g b(x 0) được tính b ằng công th ức sau: + + + x0 b / 2 x 0 b / 2 x0 b / 2 = = ω + + gb (x 0 )∫ f (x)dx a. ∫ (sin( x) 1)dx ∫ n(x)dx − − − x0 b / 2 x 0 b/ 2 x0 b / 2 + x0 b / 2 = Đặt N(x0 )∫ n(x)dx − x0 b / 2 Ta thu được: −a b b g (x )= (cos( ω (x + )) − cos( ω (x − ))) + ab + N(x ) = b 0ω 02 0 2 0 (5) 2aω b =sin sin( ω x ) + ab + N(x ) ω 2 0 0 2aω b ⇒ g (x)= sin sin( ω x) + ab + N(x) (6) b ω 2 Nh ư v ậy, hàm g b(x) c ũng có d ạng sin, có cùng t ần s ố góc ω và cùng pha v ới f(x). Do đó tần s ố c ủa g b(x) giống tần s ố của hàm f(x), và v ới mọi x0, nếu gb(x 0) đạt giá tr ị c ực đạ i, thì f(x 0) cũng đạ t giá tr ị c ực đạ i. Theo ph ươ ng trình (6), N(x) là nhân t ố nhi ễu c ủa g b(x). Tại m ỗi điểm x 0, g b(x 0) thu được [ − + ] bằng vi ệc tích l ũy các giá tr ị f(x) trong lân c ận x0 b / 2, x 0 b / 2 . Các nhi ễu trong lân c ận th ường bị tri ệt tiêu nhau khi l ấy t ổng, do đó N(x 0) nh ỏ so v ới g b(x 0). Nói cách khác, g b(x) có hình d ạng tr ơn h ơn f(x). 2aω b ωb Ta th ấy g b(x) có biên độ là A= sin , để biên độ đạ t cực đạ i thì sin= ± 1 . b ω 2 2 ωb π =2k π +  2 2 Ngh ĩa là  ωb π  =(2k + 1) π +  2 2  b 1 =2k + 2π T 2 Thay ω = vào, ta được  T b 3  =2k + T 2 71 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1 (45) T ập 2/N¨m 2008 Do b0, do v ậy ch ỉ k=0 là th ỏa mãn. Ta thu được k ết qu ả: T b = (7) 2 T Nh ư v ậy v ới b = , g b(x) s ẽ đạ t biên độ c ực đạ i. 2 Do đó, ta ch ỉ c ần tìm m ột giá tr ị b trong kho ảng [b min , b max ] sao cho biên độ c ủa g b(x) đạt giá tr ị l ớn nh ất, r ồi nhân đôi thì thu được chu k ỳ c ần tìm. V ới ảnh có độ phân gi ải 500 dpi, kho ảng cách gi ữa các vân n ằm trong đoạn [3, 25] [1]. Do v ậy ta ch ỉ c ần cho b ch ạy trong đoạn [1.5,12.5]. Trên th ực t ế, do x-signature bao g ồm các giá tr ị r ời r ạc, nên f(x) và g(x) là các hàm r ời rạc. Do v ậy t ại m ỗi điểm x 0, ta định ngh ĩa l ại g b(x 0) nh ư sau: − + − x0 q b 1 gb(x 0) = ∑ f (x) nếu b=k (8) − x0 q − + − f (x− q − 1) + f (x − q + b) x0 q b 1 0 0 + ∑ f (x) nếu b=k+0.5 − 4 x0 q trong đó q=[b/2] (ph ần nguyên) và k∈ N * . Sở d ĩ ta đị nh ngh ĩa g b(x 0) v ới hai tr ường h ợp b=k và b=k+0.5 là để chu k ỳ T tìm được có th ể nh ận giá tr ị ch ẵn ho ặc l ẻ (vì T=2b). Biên độ c ủa g b(x) được đánh giá nh ư sau: Gọi {p b} là t ập n p đỉnh và thung l ũng liên ti ếp nhau c ủa g b(x), khi đó biên độ trung bình của g b(x) được tính b ằng công th ức sau: 1 np A= p (i) − p (i − 1) (9) b− ∑ b b 2(np 1) i= 2 Gọi posb(i) là v ị trí c ủa đỉ nh p b(i) trên g b(x), ngh ĩa là g b(pos b(i))= pb(i). Độ l ệch bình ph ươ ng c ủa b được đị nh ngh ĩa là: 1 np V= (pos (i) − pos (i − 1) − b) 2 (10) b− ∑ b b np 1 i= 2 Khi b=T/2 (T là chu k ỳ c ần tìm), thì kho ảng cách gi ữa các đỉ nh đề u nhau h ơn và x ấp x ỉ bằng b, do đó V b nh ỏ. G ọi V max là ng ưỡng trên c ủa Vb, ngh ĩa là ch ỉ xét nh ững giá tr ị c ủa b làm cho V b ≤ Vmax . D ựa trên th ực nghi ệm, ta ch ọn Vmax =3. Tr ở lại ví d ụ đầ u, xét các tr ường h ợp v ới b=2, 3, 4, ta có b ảng d ưới đây: 72 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1 (45) T ập 2/N¨m 2008 Bảng 1 b np Ab Vb 2 7 2.83 1.17 3 5 3.75 0.00 4 7 2.67 6.00 Nhìn b ảng 1, ta th ấy v ới b=3, g(x) đạ t biên độ cao nh ất và có độ l ệch gi ữa các đỉ nh là th ấp nh ất. 4. Th ực nghi ệm Ta s ử d ụng c ơ s ở d ữ li ệu ảnh vân tay m ẫu c ủa FVC2002 để đánh giá m ức độ hi ệu qu ả của các thu ật toán đề xu ất. Đây là m ột c ơ s ở d ữ li ệu vân tay được cung c ấp b ởi 11 t ổ ch ức, v ới nhi ều ảnh vân tay khác nhau được quét t ừ nhi ều lo ại c ảm bi ến ( ). Các ảnh vân tay được l ựa ch ọn v ới các lo ại nhi ễu khác nhau nh ư các n ếp g ấp, v ết nhòe, vân tay Nm ho ặc khô. Thu ật toán đề xu ất s ẽ được th ử nghi ệm trên nh ững ảnh này, và so sánh v ới các thu ật toán HWJ. (a) (b) (c) Hình 4: (a) ảnh g ốc DB2_B/107_3; (b) b ản đồ t ần s ố dùng ph ươ ng pháp c ủa HWJ; (c) b ản đồ t ần s ố dùng ph ươ ng pháp c ải ti ến. Hình 4 mô t ả ví d ụ th ực nghi ệm. V ới ảnh đầ u vào (a), thu ật toán tìm t ần s ố c ục b ộ HWJ cho k ết qu ả ở hình (b), và thu ật toán đề xu ất cho k ết qu ả ở hình (c). Các l ỗ h ổng màu đen trên bản đồ t ần s ố là các v ị trí l ỗi mà thu ật toán không tìm được t ần s ố. Rõ ràng b ản đồ t ần s ố (c) có ít t ần s ố l ỗi h ơn và tr ơn h ơn ( độ l ệch gi ữa các t ần s ố th ấp) so v ới b ản đồ t ần s ố (b). 5. K ết lu ận Tần s ố vân c ục b ộ được s ử d ụng trong nhi ều ph ươ ng pháp nâng cao ch ất l ượng ảnh vân tay. Ph ươ ng pháp đánh giá t ần s ố tin c ậy hay không s ẽ làm ảnh h ưởng r ất l ớn đế n giai đoạn nâng cao ảnh và các quá trình x ử lý vân tay sau đó. Bài báo này đư a ra m ột ph ươ ng pháp tìm t ần s ố vân c ục b ộ s ử d ụng x-signature c ải ti ến, giúp vi ệc tìm các đỉnh c ủa x-signature chính xác h ơn. Cơ s ở toán h ọc và th ực nghi ệm đã ch ứng t ỏ thu ật toán c ải ti ến cho k ết qu ả đánh giá t ần s ố c ục bộ t ốt h ơn so v ới thu ật toán c ủa Hong, Wan, Jain (1998). Tóm t ắt Tần s ố vân c ục b ộ là m ột thu ộc tính n ội t ại c ủa ảnh vân tay. Đánh giá t ần s ố vân c ục b ộ là b ước r ất quan tr ọng trong nâng cao ch ất l ượng ảnh vân tay, đặ c bi ệt là v ới nh ững k ỹ thu ật s ử 73 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1 (45) T ập 2/N¨m 2008 dụng các b ộ l ọc theo ng ữ c ảnh. Ph ươ ng pháp c ủa Hong, Wan, Jain (1998) s ử d ụng x-signature để đánh giá t ần s ố vân c ục b ộ [1]. Ph ươ ng pháp này khá đơ n gi ản và có độ ph ức t ạp tính toán th ấp, tuy nhiên không hi ệu qu ả trong tr ường h ợp ảnh có nhi ễu. Ở đây, chúng tôi đề xu ất m ột ph ươ ng pháp c ải ti ến c ũng d ựa trên vi ệc tính toán x-signature, nh ưng h ạn ch ế t ối đa ảnh h ưởng của nhi ễu. K ết qu ả th ực nghi ệm cho th ấy ph ươ ng pháp c ải ti ến cho k ết qu ả tin c ậy h ơn so v ới ph ươ ng pháp c ủa Hong, Wan, Jain (1998) và độ ph ức t ạp tính toán th ấp. Summary An improved algorithm for evaluating local ridge frequency of fingerprint image The local ridge frequency is an intrinsic property of the fingerprint image. Evaluating local ridge frequency is a very important step in fingerprint enhancement, especially in techniques using contextual filters. The method of Hong, Wan, Jain (1998) uses x-signature to evaluate local ridge frequency [1]. This method is quite simple and the performance is low, however it is not effective in case the image has noises. In this article, we propose a method based on computing x-signature, but influences of noises are limited. Experimental results prove that the improved method is better than Hong, Wan, Jain‘s method, with low performance. Tài li ệu tham kh ảo [1] Hong L., Wan Y., Jain A.K., 1998. Fingerprint Image Enhancement: Algorithm and Performance Evaluation. IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 8, pp. 777-789. [2] O’Gorman L., Nickerson J.V., 1988. Matched Filter Design for Fingerprint Image Enhancement. Proc. Int Conf. on Acoustic Speech and Signal Processing, pp. 916-919. [3] O’Gorman L., Nickerson J.V., 1989. An Approach to Fingerprint Filter Design. Pattern Recognition, vol. 22, no.1, pp. 29-38. 74