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.
7 trang |
Chia sẻ: dntpro1256 | Lượt xem: 694 | Lượt tải: 0
Bạn đang xem nội dung tài liệu 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ải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008
68
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ố ijf tại )y,x( ji được tính như sau:
Hình 1. Minh họa khối vân tay và x-signature.
x-signature
cửa sổ 32 x 16
khối 16 x 16
hướng vân cục bộ
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008
69
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à )y,x( ji , ta định nghĩa một cửa sổ l x w (32x16) có hướng,
cũng có tâm là )y,x( ji , đượ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 )y,x( ji (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à )y,x( ji , tính x-signature={X0,X1,,Xl-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
k
d 0
i i j i j
j i j i j
1X G(u, v), k 0,1,..., l 1
w
w l
u x (d ) cos O(x , y ) (k )sin O(x , y )
2 2
w l
v y (d )sin O(x , y ) (k )cos O(x , y )
2 2
−
=
= = −
= + − + −
= + − − −
∑
với O là bản đồ hướng, và O(xi,yj) là hướng tại điểm (xi,yj).
4. ijf đượ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 Tij là khoảng cách trung bình giữa hai đỉnh liên tiếp của x-signature,
khi đó tần số fij được tính như sau: ij
ij
1f
T
=
(2)
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:
0
1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
position
x
-
si
gn
at
u
re
Hình 2: Biểu đồ minh họa ví dụ của x-signature.
(1)
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008
70
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.
0
2
4
6
8
1 2 3 4 5 6 7 8 9 10111213141516171819
position
x
-
si
gn
at
u
re
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 x0 sao cho với
[ ]0 0x x b / 2, x b / 2∀ ∈ − + thì x∈K. Tại mỗi vị trí x0 của K, gb(x0) được định nghĩa là tổng tất cả
các f(x) với x∈K:
0
0
x b / 2
b 0
x b / 2
g (x ) f (x)
+
−
= ∑ (3)
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 gb(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(x0) đạt giá trị cực đại, thì f(x0) 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≥
x0
b
b/2
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008
71
ω : tần số góc của f(x) và 2
T
pi
ω = , trong đó T là chu kỳ của f(x).
n(x): nhân tố nhiễu
Khi đó tại mỗi vị trí x0, gb(x0) được tính bằng công thức sau:
0 0 0
0 0 0
x b / 2 x b / 2 x b / 2
b 0
x b / 2 x b / 2 x b / 2
g (x ) f (x)dx a. (sin( x) 1)dx n(x)dx
+ + +
− − −
= = ω + +∫ ∫ ∫
Đặt
0
0
x b / 2
0
x b / 2
N(x ) n(x)dx
+
−
= ∫
Ta thu được:
b 0 0 0 0
0 0
a b bg (x ) (cos( (x )) cos( (x ))) ab N(x )
2 2
2a b
sin sin( x ) ab N(x )
2
−
= ω + − ω − + + =
ω
ω
= ω + +
ω
(5)
b
2a bg (x) sin sin( x) ab N(x)
2
ω
⇒ = ω + +
ω
(6)
Như vậy, hàm gb(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 gb(x) giống tần số của hàm f(x), và với mọi x0, nếu gb(x0) đạt giá trị cực đại, thì f(x0)
cũng đạt giá trị cực đại.
Theo phương trình (6), N(x) là nhân tố nhiễu của gb(x). Tại mỗi điểm x0, gb(x0) thu được
bằng việc tích lũy các giá trị f(x) trong lân cận [ ]0 0x b / 2, x 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(x0) nhỏ so với gb(x0). Nói cách khác, gb(x) có
hình dạng trơn hơn f(x).
Ta thấy gb(x) có biên độ là b
2a bA sin
2
ω
=
ω
, để biên độ đạt cực đại thì bsin 1
2
ω
= ± .
Nghĩa là
b 2k
2 2
b (2k 1)
2 2
ω pi
= pi +
ω pi
= + pi +
Thay 2
T
pi
ω = vào, ta được
b 12k
T 2
b 32k
T 2
= +
= +
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008
72
Do b0, do vậy chỉ k=0 là thỏa mãn. Ta thu được kết quả:
Tb
2
= (7)
Như vậy với Tb
2
= , gb(x) sẽ đạt biên độ cực đại.
Do đó, ta chỉ cần tìm một giá trị b trong khoảng [bmin, bmax] sao cho biên độ của gb(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 x0, ta định nghĩa lại gb(x0) như sau:
gb(x0) =
0
0
x q b 1
x q
f (x)
− + −
−
∑ nếu b=k (8)
0
0
x q b 1
0 0
x q
f (x q 1) f (x q b) f (x)
4
− + −
−
− − + − +
+ ∑ nếu b=k+0.5
trong đó q=[b/2] (phần nguyên) và *k N∈ .
Sở dĩ ta định nghĩa gb(x0) 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 gb(x) được đánh giá như sau:
Gọi {pb} là tập np đỉnh và thung lũng liên tiếp nhau của gb(x), khi đó biên độ trung bình
của gb(x) được tính bằng công thức sau:
pn
b b b
i 2p
1A p (i) p (i 1)
2(n 1)
=
= − −
−
∑ (9)
Gọi posb(i) là vị trí của đỉnh pb(i) trên gb(x), nghĩa là gb(posb(i))= pb(i). Độ lệch bình
phương của b được định nghĩa là:
pn
2
b b b
i 2p
1V (pos (i) pos (i 1) b)
n 1
=
= − − −
−
∑ (10)
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 đó Vb nhỏ. Gọi Vmax là ngưỡng trên của Vb, nghĩa là chỉ xét những giá trị của b làm
cho Vb ≤ 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:
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008
73
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ử
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 1(45) Tập 2/N¨m 2008
74
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.
Các file đính kèm theo tài liệu này:
- brief_840_9321_9_4945_2053249.pdf