Luận văn Xây dựng thư viện phần mềm trên họ ARM phục vụ bài toán nhận dạng vân tay

Trang 33 Chương 3 Một số thuật toán nhận dạng vân tay " Nội dung của chương này sẽ cho một cái nhìn tổng quan về các thuật toán nhận dạng vân tay đã được nghiên cứu từ trước đến nay. Ngoài ra, chương này còn trình bày một số nhận xét và so sánh giữa các thuật toán với nhau. 3.1 Một số thuật toán Tăng cường ảnh 3.1.1 Đặt vấn đề Trong một ảnh vân tay, chất lượng của cấu trúc vân tay là một đặc tính rất quan trọng, vì các vân tay mang thông tin của đặc tính của các đặc trưng, mà các đặc tính của đặc trưng này rất cần thiết cho bước rút trích đặc trưng vân tay. Trong trường hợp lý tưởng, ảnh vân tay có chất lượng tốt, các vân lồi và vân lõm uốn cong đều với nhau theo cùng một hướng, cho phép các đặc trưng được rút trích một cách chính xác. Tuy nhiên, trên thực tế, ảnh vân tay luôn có chất lượng không được tốt bởi vì các thông tin nhiễu4 của ảnh làm sai lệch các đặc trưng, dẫn đến làm ảnh hưởng đến quá trình rút trích đặc trưng. Như vậy, mục đích của bước Tăng cường ảnh là làm giảm các thông tin nhiễu, làm rõ các cấu trúc vân tay, và đánh dấu các vùng có thể khôi phục hay không có thể khôi phục. 3.1.2 Tăng cường ảnh bằng phương pháp lọc Gabor Phương pháp lọc Gabor được triển khai bởi Lin Hong [12] là một trong những phương pháp Tăng cường ảnh vân tay phổ biến nhất hiện nay. Phương pháp này dựa vào bộ lọc Gabor mà bộ lọc này là sự hòa hợp của hướng vân và tần số vân cục bộ. Các bước chính của phương pháp này bao gồm: Chuẩn hóa ảnh (normalization), Ước lượng hướng ảnh (orientation image estimation), Ước lượng tần số ảnh (frequency 4 Ảnh vân tay bị nhiễu hay không rõ là do các thiết bị đầu đọc vân tay> không lấy ảnh tốt, hay do vân tay của người dùng trong lúc lấy bị hao mòn hay dơ bẩn, hay do lực ấn ngón tay trong lúc lấy vân tay [15]. Trang 34 image estimation), Tạo các vùng mặt nạ (region mask generation) và Lọc Gabor (filtering), xem hình 3.1. Hình 3.1 Các bước tăng cường ảnh của phương pháp lọc Gabor [32]. 3.1.2.1 Chuẩn hóa ảnh Mục đích của bước này là làm giảm độ khác biệt các giá trị mức xám giữa các vân tay với nhau nhằm tạo thuận lợi cho các bước xử lý tiếp theo. Nguyên nhân của sự khác biệt giá trị mức xám này là do quá trình lấy dấu vân tay từ thiết bị đã tạo nên sự không đồng đều màu, có chổ màu lợt màu đậm. Đặc biệt, ảnh vân tay sau khi được chuẩn hóa, các vân tay sẽ được làm rõ hơn mà không làm thay đổi cấu trúc của vân tay (hình 3.2). Công thức thuật toán của Chuẩn hóa ảnh: ⎪⎩ ⎪⎨ ⎧ =Ψ >Ι −Ι+ −Ι− Mjiif VAR MjiVARM otherwise VAR MjiVARM ji ),( ,)),(( . ,)),(( 2 0 0 2 0 0 ),( Trong đó I(i,j) là giá trị mức xám tại điểm ảnh (i,j), M và VAR tương ứng là mean và variance của I, ),( jiΨ là giá trị mức xám tại điểm (i,j) sau khi đã được chuẩn hóa, M0 và VAR0 tương ứng là mean và variance mong muốn. Trang 35 Hình 3.2 Minh họa kết quả chuẩn hóa ảnh; (a) ảnh gốc; (b) ảnh đã được chuẩn hóa (M0 = 100, VAR0 = 100). 3.1.2.2 Ước lượng hướng ảnh Mục đích của bước này là xác định hướng của các đường vân tay; nhằm phục vụ cho bước Ước lượng tần số ảnh và Lọc Gabor. Đây được xem là một trong những bước quan trọng nhất trong phần Tăng cường ảnh; vì nếu việc Ước lượng hướng không đúng sẽ dẫn đến việc Ước lượng tần số và Lọc Gabor sai; kết quả này làm ảnh sau khi tăng cường không tốt, thậm chí còn xấu hơn rất nhiều so với ảnh ban đầu; dẫn đến việc rút trích đặc trưng không đúng. Các bước chính của Ước lượng hướng ảnh [25, 34, 24, 8]: • Chia Ψ thành nhiều ô có kích thước ww× (giá trị w đề nghị là 16). • Ở mỗi ô, có tâm điểm (i,j), dùng toán tử Sobel để tính gradient ),( jix∂ và ),( jiy∂ tại mỗi điểm (i,j). Toán tử Sobel ngang được dùng để tính ),( jix∂ . ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ − − − 101 202 101 (3.1) Toán tử Sobel dọc được dùng để tính ),( jiy∂ . Trang 36 ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ −−− 121 0 0 0 1 2 1 (3.2) • Ước lượng hướng ở mỗi ô có tâm điểm (i,j) theo phương trình sau: ∑ ∑ + −= + −= ∂∂= 2 2 2 2 ),(),(2),( Wi Wiu Wj Wjv yxx vuvujiV (3.3) ∑ ∑ + −= + −= ∂∂= 2 2 2 2 22 ),(),(),( Wi Wiu Wj Wjv yxy vuvujiV (3.4) ),( ),( tan 2 1),( 1 jiV jiV ji x y−=θ (3.5) Trong đó ),( jiθ là hướng cục bộ của ô có tâm điểm là (i,j). • Sử dụng lọc Gaussian làm mượt các trường hướng của ô căn cứ vào thông tin của các ô lân cận, vì các điểm gây nhiễu, vân bị đứt, hay các đặc trưng vân tay, … trong ảnh vân tay; làm cho việc xác định hướng cục bộ của ô không đúng (hình 3.3a). Ngoài ra, tính chất hướng của các ô thay đổi một cách từ từ so với các ô lân cận của nó, nên một lọc thông thấp (low-pass) được dùng để chỉnh sửa những hướng vân cục bộ sai. Để thực hiện lọc thông thấp, hướng của các ô được chuyển về các trường véc tơ liên tục: )),(2cos(),( jijix θ=Φ (3.6) )),(2sin(),( jijiy θ=Φ (3.7) Trong đó ),( jixΦ và ),( jiyΦ là các trường véc tơ tương ứng với x và y. Áp dụng bộ lọc thông thấp lên các trường véc tơ ta có: ∑ ∑ Φ Φ Φ Φ−= −= −−Φ=Φ′ 2 2 2 2 ),(),(),( w wu w wv xx vwjuwivuGji (3.8) ∑ ∑ Φ Φ Φ Φ−= −= −−Φ=Φ′ 2 2 2 2 ),(),(),( w wu w wv yy vwjuwivuGji (3.9) Trang 37 Trong đó G là lọc thông thấp Gaussian của kích thước ΦΦ ×ww . Hướng sau khi được làm mượt ở mỗi ô: ),( ),( tan 2 1),( 1 ji ji ji x y Φ′ Φ′=Ο − (3.10) Hình 3.3 a) Ước lượng hướng ảnh mà chưa có được làm mượt; b) Ước lượng hướng ảnh mà đã có làm mượt. 3.1.2.3 Ước lượng tần số ảnh Mục đích của bước này là xác định tần số của vân tay; nhằm phục vụ cho bước lọc Gabor. Tần suất vân cục bộ tại điểm (i,j) là nghịch đảo của số vân trên một đơn vị chiều dài dọc theo đoạn có tâm tại (i,j) và vuông góc với hướng vân cục bộ. Các bước chính của ước lượng tần số ảnh [32]: • Chia G thành các ô có kích thước w×w (16×16). • Ở mỗi tâm điểm (i,j) của ô, tính giá trị trong cửa sổ hướng (oriented window) có kích thước l×w (32×16), xem hình 3.4. • Ở mỗi tâm điểm (i,j) của ô, tính x-signature, X[0], X[1], … X[l – 1], của vân lồi và vân lõm trong phạm vi cửa sổ hướng. Trang 38 ∑− = −=Ψ= 1 0 1...,,1,0),,(1][ w d lkvu w kX (3.11) ),(sin) 2 (),(cos) 2 ( jilkjiwdiu Ο−+Ο−+= (3.12) ),(cos) 2 (),(sin) 2 ( jikljiwdjv Ο−+Ο−+= (3.13) Nếu trong cửa sổ hướng không chứa đặc trưng vân tay nào thì hình dạng của x-signature là một hình sin rời rạc có biên độ gần bằng nhau; do đó, tần số của vân có thể được ước lượng từ x-signature. Đặt T(i,j) là khoảng cách trung bình của cặp đỉnh liền kề trong x-signature. Tần số vân, ),( jiΩ , được tính như sau: ),(/1),( jiTji =Ω (3.14) • Đối ảnh vân tay có độ phân giải không thay đổi, thì giá trị của tần số vân cục bộ là một khoảng giá xác định nào đó. Như đối với ảnh 500 dpi, giá trị tần số là [1/3, 1/25]; do đó, nếu giá trị ước lượng tần số nằm ngoài phạm vi của tần số thì được gán giá trị là -1 để xác định đây là ô không thể xác định được tần số. • Đối những cửa sổ hướng có chứa những đặc trưng vân tay thì hình dạng của x-signature là một hình sin có các giá trị của đỉnh biên độ trên lệch nhau nhiều. Giá trị tần số của ô được suy ra từ các giá trị tần số của các ô lân cận. Ta có thuật toán sau: (i) Với mỗi ô có tâm (i,j), ⎪⎪⎩ ⎪⎪⎨ ⎧ +−−Ω −−Ω −≠ΩΩ =Ω′ ∑ ∑ ∑ ∑ Ω Ω Ω Ω Ω Ω Ω Ω −= −= −= −= otherwise vwjuwivuW vwjuwivuW jiifji ji w wu w wv g w wu w wv g 2/ 2/ 2/ 2/ 2/ 2/ 2/ 2/ )1),((),( )),((),( 1),(),,( ),( δ μ (3.15) Trong đó: ⎩⎨ ⎧ ≤= otherwisex xif x , 0,0 )(μ Trang 39 ⎩⎨ ⎧ ≤= otherwise xif x ,1 0,0 )(δ Wg là một nhân Gaussian rời rạc (discrete Gaussian kernel) mà trong đó giá trị của mean là 0 và giá trị của variance là 9 khi kích thước nhân 7=ΩW . (ii) Nếu tồn tại ít nhất một ô có giá trị tần số là -1, thì hoán đổi giữa Ω và Ω′ . Sau đó quay lại bước (i). • Khoảng cách giữa các tâm của vân thay đổi rất ít trong cùng một vùng lân cận cục bộ; do vậy, một lọc thông thấp có thể được dùng để xóa outliner trong f’: ),(),(),( 2/ 2/ 2/ 2/ vwjuwivuWjiF l lw wu w wu l −−Ω′= ∑ ∑ Ω Ω−= −= (3.16) Trong đó: Wt là một lọc thông thấp hai chiều và kích thước của bộ lọc wt = 7. Hình 3.4 Cửa sổ hướng và x-signature. Trang 40 3.1.2.4 Tạo các vùng mặt nạ Mục đích của bước này là xác định các vùng điểm của ảnh vân tay đầu vào nào có khả năng được phục hồi5, và vùng điểm nào không thể được phục hồi6. Việc phân loại các điểm ảnh vào vùng có khả năng được phục hồi hay không thể được phục hồi là dựa vào hình dạng sóng của vân tay cục bộ. Ba yếu tố sau được dùng là đặc tính của sóng hình dạng sin của tần số: biên độ (α ), tần số (β ), độ khác biệt (γ ). Thuật toán: Đặt X[1], X[2], …, X[l] là x-signature của ô có tâm (i,j). Ba đặc tính được tính như sau: • α = (chiều cao trung bình của các đỉnh – bề sâu trung bình của các đáy của sóng hình sin). • ),(/1 jiT=β ; trong đó, T(i,j) là số điểm ảnh trung bình giữa 2 đỉnh đỉnh kề nhau. • ∑ ∑= =−= li li iXliXl 1 21 ))][1(][(1γ . Nếu sự kết hợp của ba đặc tính trên mà lớn hơn một ngưỡng nào đó, thì ô có tâm (i,j) có khả năng được phục hồi, ngược lại thì không thể được phục hồi. 3.1.2.5 Lọc Gabor Cấu trúc song song của vân tay cùng với một tần số vân và hướng trong một ảnh vân tay cung cấp thông tin hữu ích cho việc loại bỏ các nhiễu ra khỏi ảnh vân tay; do đó, việc dùng bộ lọc Gabor mà dựa vào tần số và hướng vân giúp làm rõ ảnh vân tay một cách hiệu quả. Một bộ lọc đối xứng hai chiều Gabor có dạng sau: 5 Vùng có khả năng được phục hồi: là các vân được phân biệt rõ ràng với các vân khác hay các vân bị hư hỏng bởi các đường đứt gãy nhỏ, thâm sẹo… nhưng chúng vẫn có khả năng nhìn được và các vùng xung quanh cung cấp thông tin đủ để khôi phục cấu trúc ban đầu của chúng. 6 Vùng không thể được phục hồi là nơi các vân bị hư hại bởi các nhiễu nghiêm trọng, không có vân nào nhìn thấy được và các vùng xung quanh không cho phép chúng được xây dựng lại. Trang 41 ).2(. 2 1exp),:,( 2 2 2 2 θ θθ πσσθ xfCos yxfyxg yx ⎪⎭ ⎪⎬ ⎫ ⎪⎩ ⎪⎨ ⎧ ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ +−= Trong đó θ là hướng của bộ lọc, và [xθ, yθ] là ảnh của [x,y] sau khi quay quanh trục Cartesian một góc ( 90o – θ ): ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ÷⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ÷−=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ÷⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ÷−−− −−=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ÷ y x y x y x oo oo )sin()cos( )cos()sin( )90cos()90sin( )90sin()90cos( θθ θθ θθ θθ θ θ Trong biểu thức ở trên, f là tần suất của sóng phẳng hình sin, xσ , yσ là độ lệch chuẩn Gaussian tương ứng dọc theo trục x và trục y. Hình 3.5 Biểu diễn đồ họa của bộ lọc Gabor xác định bởi tham số 3,5/1,90 ==== yxo f σσθ . Để áp dụng các bộ lọc Gabor tới một ảnh, cần xác định 4 tham số (θ, f, xσ , yσ ). Tần số của bộ lọc hoàn toàn được quyết định bởi tần số vân cục bộ và hướng của bộ lọc được quyết định bởi hướng vân cục bộ. Việc chọn các giá trị xσ và yσ có thể hoán đổi cho nhau. Nếu chọn giá trị lớn thì bộ lọc sẽ chịu nhiễu nhiều hơn, nhưng lại tạo ra sự nhầm lẫn giữa vân lồi và vân lõm. Ngược lại nếu chọn giá trị nhỏ, thì các bộ lọc ít nhầm lẫn giữa vân lồi và vân lõm; nhưng sau đó, chúng sẽ ít hiệu quả trong việc loại bỏ các nhiễu. Trong thực tế, từ hàm Modulation Transfer Function (MFT) của bộ lọc Gabor, có thể nhận thấy tăng xσ , yσ làm giảm dải thông của bộ lọc và ngược lại. Dựa trên dữ liệu kinh nghiệm của Hong, Wan và Jain đặt xσ = yσ = 4, để làm nhanh Trang 42 quá trình cải thiện; thay vì tính bộ lọc ngữ cảnh thích hợp nhất cho mỗi điểm ảnh “on the fly”, một tập {gij (x,y)| I = 1…no, j = 1…nf } của các bộ lọc được tạo ra và lưu trữ từ trước; trong đó, n0 là số các hướng rời rạc {θi| I = 1…no } và nf là số các tần số rời rạc {fj | j = 1…nf}. Sau đó mỗi điểm ảnh [x,y] của ảnh được quấn lại trong miền không gian, với bộ lọc gij (x,y), với θi là hướng được rời rạc hóa gần nhất với θxy và fj là tần số được rời rạc hóa gần nhất với fxy. Hình 3.6 thể hiện một ví dụ về tập bộ lọc cho n0 = 8 và nf = 3. Hình 3.6 trình bày ứng dụng Gabor dựa trên lọc ngữ cảnh trên các ảnh chất lượng trung bình và thấp: Hình 3.6 Một biểu diễn đồ họa trong một nhóm 24 bộ lọc Gabor (n0 = 8 và n1 = 5) với xσ = yσ = 4. Bằng cách giảm giá trị của xσ tương ứng với yσ , quá trình lọc tạo ra vài vân sai và dễ bị nhiễu. Đầu ra của một ảnh chuẩn hóa có thể là một ảnh mức xám, hay là một ảnh nhị phân; nói chung phụ thuộc vào các tham số được chọn và các bộ lọc thích hợp. Lưu ý rằng, mục đích không phải là cung cấp một sự xuất hiện tốt bề ngoài của ảnh nhưng là để làm thuận tiện hơn cho các bước rút trích đặc tính thành công. Nếu các bộ lọc được chỉnh sửa để làm tăng độ tương phản và khử các nhiễu, ước lượng cục bộ (hướng và tần số) có thể lỗi trên các vùng chất lượng thấp, và quá trình lọc chỉ cung cấp các cấu trúc sai lầm (Jiang, 2000). Ví dụ, một ứng dụng lặp dùng bộ lọc Gabor đã được sử dụng bởi Cappeli, Maio, và Maltoni (2000) để tạo ra một mẫu vân tay tổng hợp; trong trường hợp này, các bộ lọc sinh ra các mẫu vân hoàn toàn không tồn tại trong thực tế. Trang 43 3.1.3 Kết luận Với các đặc điểm nổi trội của phương pháp lọc Gabor, hầu hết các bước tăng cường ảnh vân tay hiện nay dùng phương pháp này; do vậy, phương pháp này cũng được cài đặt trên Hệ thống nhúng; mặc dù, việc triển khai phương pháp này gặp một số khó khăn khi đưa lên Hệ thống nhúng, xem trong mục 6.2. 3.2 Một số thuật toán Rút trích đặc trưng 3.2.1 Đặt vấn đề Ngày nay, đa số các hệ thống nhận dạng vân tay tự động so sánh các vân tay dựa trên đối sánh đặc trưng; vì vậy, việc rút trích đặc trưng đúng đắn là một nhiệm vụ cực kỳ quan trọng. Có hai phương pháp chính để tìm các đặc trưng: rút trích các đặc trưng từ ảnh đã được nhị phân hóa và rút trích các đặc trưng trực tiếp từ ảnh xám. 3.2.2 Rút trích các đặc trưng từ ảnh đã được nhị phân hóa Hình 3.7 Các bước rút trích đặc trưng từ ảnh đã được nhị phân hóa [16]. Hình 3.7 Mô tả các bước chính của phương pháp này. Từ ảnh xám ban đầu, các bộ lọc thích hợp được dùng để phát hiện và làm mỏng đường vân về dạng một điểm ảnh, biến đổi ảnh xám ban đầu thành ảnh được nhị phân hóa (có giá trị là 0 hoặc 1) tương ứng. Cuối cùng, các đặc trưng sẽ được rút trích dựa vào điểm lân cận xung quanh của nó. Trang 44 3.2.2.1 Phương pháp Nhị phân hóa Một trong những kỹ thuật dễ dàng nhất là sử dụng ngưỡng toàn cục t và được thực hiện bằng cách thiết lập các điểm ảnh có mức xám nhỏ hơn t về 0 và các điểm ảnh còn lại về 1. Nhưng các phần khác nhau của ảnh có thể được đặc tính hóa bởi độ tương phản và cường độ khác nhau; do vậy, một ngưỡng đơn là không đủ để nhị phân hóa chính xác. Một kỹ thuật khác là dùng ngưỡng cục bộ t, bằng cách điều chỉnh giá trị của nó theo cường độ cục bộ trung bình. Trong trường hợp ảnh vân tay có chất lượng thấp, kỹ thuật ngưỡng cục bộ không phải lúc nào cũng cho ra một kết quả tốt; vì có sự xuất hiện các lỗ, các đứt gãy nhỏ và các cầu giữa các vân trên ảnh nhị phân hóa (hình 3.10). Để giải quyết vấn đề này ta cần có thêm bước Lọc đặc trưng. 3.2.2.2 Phương pháp Làm mỏng (thinning) Phương pháp này nhằm làm mỏng bề dày của vân tay về còn một điểm ảnh mà các cấu trúc vân tay vẫn được đảm bảo (hình 3.8). Hình 3.8 Kết quả của việc Nhị phân hóa và Làm mỏng của ảnh đã được Tăng cường. 3.2.2.3 Phương pháp Rút trích Giả sử (x,y) là một điểm trên đường vân đã được làm mỏng và N0, N1, …, N7 là 8 điểm xung quanh nó thì: • (x,y) là một điểm kết thúc nếu ∑ = = 7 0 1 i iN ; Trang 45 • (x,y) là một điểm rẽ nhánh nếu∑ = > 7 0 2 i iN . Hình 3.9 a) một phần điểm của vân tay; b) điểm kết thúc; c) điểm rẽ nhánh. 3.2.2.4 Lọc đặc trưng (minutiae filtering) Sự xuất hiện các lỗ, các đứt gãy nhỏ và các cầu giữa các vân trên ảnh vân tay đã được nhị phân hóa làm ảnh hưởng đến việc rút trích sai các đặc trưng. Như vậy một bước tiền xử lý trước khi rút trích các đặc trưng sẽ hữu ích cho việc loại bỏ các đặc trưng lỗi. Hình 3.10 Lỗ và đứt gãy nhỏ trong ảnh vân tay đã được nhị phân hóa và làm mỏng. Có hai loại xử lý để loại bỏ các đặc trưng lỗi: xử lý dựa vào cấu trúc vân (structural post-processing) và lọc đặc trưng theo miền mức xám ảnh (minutiae filtering in the gray-scale domain) [31]. • Xử lý dựa vào cấu trúc vân: để phát hiện các đặc trưng lỗi, có thể sử dụng vài luật cấu trúc đơn giản. Xiao xác định các cấu trúc đặc trưng lỗi và đưa ra phương pháp loại bỏ chúng [41]. Thuật toán sử dụng dựa trên các luật đơn giản; xác định Trang 46 các đặc tính số học liên quan đến các đặc trưng: chiều dài các vân, góc đặc trưng, và số các đặc trưng đối diện gần kề trong lân cận. Hình 3.11 Các cấu trúc vân lỗi phổ biến được điều chỉnh lại thành các cấu trúc vân đúng. • Lọc đặc trưng theo miền mức xám ảnh: để phát hiện các đặc trưng thực sự, thuật toán rà soát lại dựa vào các đặc trưng gần kề xung quanh nó. 3.2.3 Rút trích các đặc trưng trực tiếp từ ảnh xám Ý tưởng của phương pháp này là dựa vào thuật toán Dò theo đường vân (rigde line following) [30]. Từ ảnh vân tay đã được tăng cường, thuật toán sẽ dò các đường vân để tìm ra các đặc trưng rẽ nhánh và các đặc trưng kết thúc. Mặc dù độ phức tạp khái niệm của phương pháp này nhiều hơn, nhưng phương pháp này có độ tính toán ít phức tạp hơn so với phương pháp rút trích các đặc trưng từ ảnh đã được nhị phân hóa. 3.2.3.1 Dò theo đường vân (ridge line following) Giả sử I là một ảnh xám có kích thước là a×b, và z là giá trị mức xám tại điểm (i,j) thì bề mặt của ảnh vân tay I có dạng như trong hình 3.12. Trang 47 Hình 3.12 Các đường vân (ridge) và các rãnh (ravine) trên bề mặt vân tay. Về mặt toán học, đường vân là tập hợp các điểm cực đại dọc theo cùng một hướng xác định. Việc rút trích các đặc trưng trực tiếp từ ảnh xám dựa vào thuật toán Dò theo đường vân. Trong đó, thuật toán này dựa vào việc xác định các điểm cực đại trực giao với hướng của đường vân. Các bước chính rút trích đặc trưng bằng thuật toán Dò theo đường vân được thực hiện như sau: • Lấy một điểm bất kỳ (is,js) trên ảnh I. • Xác định hướng ϕs tại điểm (is,js). • Tìm điểm cực đại (ic,jc) mà gần với (is,js) nhất (hình 3.13). • Xác định hướng ϕc tại điểm (ic,jc). • Dịch chuyển một đoạn μ theo hướng ϕc (hình 3.14). • Điều chỉnh lại điểm cực đại (ic,jc) và hướng ϕc. • Tiếp tục dò theo đường vân cho đến khi không phát hiện được điểm cực đại (ic,jc) thì đó là điểm đặc trưng (có thể là điểm kết thúc hay điểm rẽ nhánh). Trang 48 • Tiếp theo chọn một điểm (is,js) khác và thực hiện lại quá trình trên cho đến khi dò hết tất cả các đường vân. Hình 3.13 Điểm cực đại (ic,jc) tương ứng với (is,js). Trang 49 Hình 3.14 Dịch chuyển một đoạn μ theo đường vân. Thuật toán xác định điểm cực đại: Giả sử ),),,(( σφtt jiΩ là thiết diện của đường vân có điểm chính giữa là (it, jt), hướng của thiết diện φ = ϕt +π / 2 (ϕt là hướng của đường vân tại (it, jt) và bề rộng của thiết diện m = 2σ +1 điểm ảnh (hình 3.15). Khi đó, Ω được xác định như sau: ( )( ) ( ) ( ) ( )( ){ }endendstartstart jijisegmentjiIjiji ,,,,,,, ∈∈=Ω ( ) ( ) ( )( )φσσ sin.,, −−= ttstartstart jroundiroundji ( ) ( ) ( )( )φσσ sin.,, ++= ttendend jroundiroundji Trang 50 Điểm cực đại được xác định bằng cách so sánh mức xám giữa các điểm trong Ω. Hình 3.15 Thiết diện của đường vân. 3.2.4 Kết luận Trong luận văn, phương pháp rút trích các đặc trưng từ ảnh đã được nhị phân hóa được áp dụng để cài đặt lên Hệ thống nhúng. 3.3 Một số thuật toán Đối sánh vân tay 3.3.1 Đặt vấn đề Thuật toán đối sánh vân tay so sánh hai ảnh vân tay và cho ra độ tương tự (có giá trị nằm trong khoảng 0 và 1). Kết luận của việc đối sánh, khớp hay không khớp, phụ thuộc vào ngưỡng t (mục 2.4.2). Hầu hết các thuật toán nhận dạng vân tay đều dựa vào việc đối sánh các điểm đặc trưng; chỉ có một vài thuật toán đối sánh trực tiếp trên ảnh xám. Ngoài ra việc đối sánh hai ảnh vân tay là một bài toán vô cùng khó. Có rất nhiều yếu tố ảnh hưởng đến việc đối sánh. Sau đây là các yếu tố chính [31]: • Sự dịch chuyển (displacement): cùng một ngón tay cho mỗi lần lấy mẫu, dấu vân tay có thể đặt ở các vị trí khác nhau trên bộ cảm biến làm tịnh tiến ảnh vân tay. Một ngón tay nếu dịch chuyển 2mm sẽ làm tịnh tiến khoảng 40 điểm ảnh trong cùng một vân tay được quét ở độ phân giải 500dpi. Trang 51 • Sự quay (rotation): cùng một ngón tay cho mỗi lần lấy mẫu, dấu vân tay có thể quay ở các góc khác nhau trên bề mặt thiết bị đầu đọc vân tay; mặc dù, bộ hướng dẫn ngón tay được gắn trên các máy quét thương mại, nhưng trong thực tế tồn tại sự quay không cố ý lên tới ± 20 độ theo chiều đứng. • Sự chồng chéo từng phần (partial overlap): sự dịch chuyển và sự quay vân tay thường làm cho một phần vân tay nằm ra ngoài vùng nhìn thấy của bộ cảm biến. Kết quả là xuất hiện sự chồng chéo giữa các vùng cận cạnh của mẫu vân và các vân tay đầu vào. • Sự biến dạng phi tuyến (non-linear distortion): do sự mềm dẻo của ngón tay, việc ánh xạ hình ảnh ba chiều sang hình ảnh hai chiều trên bề mặt bộ cảm biến gây ra biến dạng phi tuyến trong việc đọc vân tay. • Lực ấn và tình trạng của da (pressure and skin condition): cấu trúc vân của một ngón tay sẽ được lấy chính xác nếu như phần ngón tay được tiếp xúc đúng quy cách với bề mặt bộ cảm biến. Một số yếu tố khác như: áp lực ngón tay, ngón tay khô, bệnh ngoài da, ướt, bẩn, độ ẩm không khí, … gây ra sự tiếp xúc không đúng quy cách; hệ quả là, ảnh vân tay được lấy có chất lượng không tốt. • Các lỗi rút trích đặc trưng (feature extraction errors): các thuật toán rút trích đặc trưng chưa hoàn hảo. Các lỗi có thể được tạo ra trong bất kỳ giai đoạn nào của quá trình rút trích đặc trưng như: Ước lượng hướng và Ước lượng tần số, Phân đoạn vùng vân tay từ nền, ...). Cho đến nay, có rất nhiều thuật toán đối sánh vân tay đã được đề xuất để làm giảm ảnh hưởng các yếu tố trên. Hầu hết các thuật toán này không gặp khó khăn trong đối sánh các ảnh vân tay chất lượng tốt. Nhưng trong ảnh chất lượng thấp, đối sánh vân tay vẫn còn là một thách thức. Các phương pháp đối sánh vân tay có thể được phân thành ba: Đối sánh dựa vào độ tương quan, Đối sánh dựa vào đặc trưng, và Đối sánh dựa vào đặc tính vân. Trang 52 3.3.2 Đối sánh dựa vào độ tương quan 3.3.2.1 Giới thiệu Kỹ thuật đối sánh của phương pháp này sẽ chồng hai ảnh vân tay lên nhau và xem xét sự tương quan giữa các điểm ảnh được tính dựa trên độ khác biệt giữa các điểm ảnh trong hai ảnh vân tay: khác biệt về vị trí, hướng vân tại điểm ảnh, … [31]. 3.3.2.2 Phát biểu bài toán Đặt T và I là hai ảnh vân tay tương ứng với vân tay mẫu (template) và vân tay đầu vào (input). Một độ đo trực quan về sự sai biệt được tính bằng tổng các bình phương khác nhau (SSD) của các cường độ các điểm ảnh tương ứng: SSD(T,I) = ||T – I||2 =( T – I )T(T – I) = ||T||2 + ||I||2 – 2TTI (3.17) Trong đó chỉ số T ký hiệu sự hoán vị của một véc tơ. Nếu ||T||2 và ||I||2 là hằng số thì sự sai biệt giữa hai ảnh được tối thiểu khi độ tương quan chéo (CC) giữa T và I được cực đại: CC(T,I ) = TTI (3.18) Đại lượng –2 ∗CC(T,I) xuất hiện như là đại lượng thứ ba trong biểu thức 3.17. Độ tương quan chéo là độ đo tương tự giữa hai ảnh. Do luôn có sự dịch chuyển và sự quay trong các ảnh vân tay, nên độ tương tự giữa chúng không thể đơn giản được tính bằng cách đặt chồng T và I và áp dụng biểu thức (3.18). Đặt I(Δx,Δy,θ ) là một sự quay của ảnh đầu vào I với một góc θ so với điểm trung tâm ảnh và dịch một đoạn Δx, Δy dọc theo trục x và y; khi đó, độ tương tự giữa hai ảnh T và I có thể được đo như sau: S(T,I) = max CC(T, I(Δx,Δy,θ )) (3.19) Việc ứng dụng biểu thức 3 vẫn chưa cho ra một kết quả tốt vì một số vấn đề sau: Trang 53 1. Các biến dạng phi tuyến làm cho các vết ấn của cùng một ngón tay khác nhau trong cấu trúc toàn cục; do vậy, khi chồng hai ảnh lên nhau sẽ có độ tương quan khác nhau. 2. Tình trạng da và áp lực ấn ngón tay làm cho độ sáng, độ tương phản, và độ dày vân thay đổi trong các vết ấn khác nhau. Hatano (2002) sử dụng độ tương quan khác nhau, được tính như là độ tương quan lớn nhất trừ đi độ tương quan nhỏ nhất, trong một lân cận điểm nơi mà độ tương quan là lớn nhất. Trong thực tế, do tính tuần hoàn của các mẫu vân tay, nếu hai phần tương ứng của cùng một vân tay không được điều chỉnh tương ứng với vị trí đối sánh tối ưu, giá trị độ tương quan sẽ thấp trong khi hai vị trí không tương quan thể hiện một giá trị tương quan phẳng hơn trong lân cận của vị trí đối sánh tối ưu. Hantano báo cáo một sự cải thiện độ chính xác tương ứng với phương pháp độ tương quan truyền thống [11]. 3. Việc tính toán của biểu thức 3 tốn rất nhiều chi phí; ví dụ: với ảnh có kích thước 400×400, thì việc tính toán chéo của biểu thức 2 cho (Δx, Δy, θ ) cần tới 16,000 phép nhân và 16,000 phép cộng. Nếu Δx, Δy dịch chuyển mỗi lần 1 điểm ảnh trong phạm vi [–200, 200], và θ xoay mỗi lần một độ trong một khoảng [–30o, 30o] thì khoảng 1569 tỷ phép nhân và phép cộng. 3.3.3 Đối sánh dựa vào đặc trưng 3.3.3.1 Giới thiệu Đây là kỹ thuật được sử dụng phổ biến và rộng rãi nhất. Các đặc trưng được rút trích từ hai ảnh vân tay được lưu trữ như là tập các điểm trong một bề mặt hai chiều. Sau đó, đối sánh vân tay sẽ dùng các đặc trưng này để đối sánh với nhau [31]. 3.3.3.2 Phát biểu bài toán Đặt T và I là hai ảnh vân tay tương ứng với vân tay mẫu và vân tay đầu vào. Không giống như phương pháp đối sánh dựa vào độ tương quan; phương pháp này đối sánh Trang 54 hai ảnh vân tay dựa vào các đặc trưng. Mỗi đặc trưng có thể được mô tả bằng một số các thuộc tính, bao gồm: vị trí trong ảnh vân tay, hướng, loại đặc trưng (điểm kết thúc vân hay điểm rẽ nhánh), một trọng số dựa trên chất lượng của ảnh vân tay trong một lân cận của đặc trưng, … Hầu hết các thuật toán đối sánh đặc trưng xem xét mỗi đặc trưng như là một một nhóm bộ ba m = {x, y, θ } thể hiện vị trí chi tiết ở vị trí x, y và góc đặc trưng θ : T = {m1, m2, …mm}; mI = {xi, yi, θ i}, i = 1…m I = {m1’, m2’…mn’}; mj’ = {xj’, yj’, jθ′}, j = 1…n Trong đó m và n tương ứng là số các đặc trưng trong T và I. Một đặc trưng mj’ trong I và một đặc trưng mi trong T được xem là đối sánh với nhau nếu khoảng cách không gian (sd) giữa chúng là nhỏ hơn mức độ sai (tolerance) cho trước ro và sự khác nhau về hướng (dd) giữa chúng là nhỏ hơn góc độ sai θ o: ( ) ( ) 022),( ryyxxmmsd ijijij ≤−′+−′=′ (3.20) ( ) ( ) 00360,min, θθθθθ ≤−′−−′=′ ijijij mmdd (3.21) Biểu thức 3.21 lấy giá trị nhỏ nhất của ijij θθθθ −′−−′ 0360, bởi vì tính chu kỳ của góc (sự lệch góc nhau giữa 2o và 358o chỉ là 4o). Độ sai ro và θ o được định nghĩa để bù vào các lỗi không thể tránh khỏi do các thuật toán rút trích đặc trưng và các nhiễu mềm dẻo làm cho vị trí các đặc trưng thay đổi. Canh lề hai vân tay là bước bắt buộc để cực đại hóa số các đặc trưng. Để canh lề chính xác hai vân tay cần phải dịch chuyển (theo x và y), và quay góc (θ ), được gọi là các biến đổi hình học: 4. Co giản ảnh vân tay khi độ phân giải của hai vân tay có sự khác nhau (như: hai ảnh vân tay được lấy từ các đầu đọc vân tay khác nhau). 5. Các biến đổi hình học hữu ích cho đối sánh đặc trưng trong trường hợp một hay cả hai vân tay bị biến dạng. Trang 55 Đặt map(.) là hàm ánh xạ một đặc trưng m'j (từ I) vào trong m"j theo công thức biến đổi hình học cho trước; ví dụ, xem xét sự dịch chuyển của [Δx, Δy] và một góc quay ngược chiều kim đồng hồ θ quanh điểm gốc7: { }( ) { }θθθθ +′′′′′=′′=′′′=′ΔΔ jjjjjjjyx yxmyxmmap ,,,,, (3.22) Trong đó: ⎥⎦ ⎤⎢⎣ ⎡ Δ Δ+⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ′ ′ ⎥⎦ ⎤⎢⎣ ⎡ −=⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ′′ ′′ y x y x y x j j j j θθ θθ cossin sincos Đặt mm(.) là hàm chỉ thị trả về 1 trong trường hợp đặc trưng m"j và mi đối sánh theo biểu thức 3.20 và 3.21: ( ) ⎩⎨ ⎧ ≤′≤′=′′ lainguoc mmddrmmsdkhi mmmm ijijij 0 ),(&&),(1 , 00 θ Sau đó bài toán đối sánh có thể được công thức như sau: ∑ = ΔΔΔΔ ′= m i iipyxPyx mmmapmmimize 1 )(,,,,, ),((max θθ (3.23) Trong đó, P(i) là một hàm không biết trước quyết định cặp đôi giữa các đặc trưng I và T: nghĩa là mỗi đặc trưng có một cặp đôi tương ứng trên vân tay khác hoặc không có cặp đôi tương ứng nào: 1. P(i ) = j: nghĩa là cặp đôi tương ứng của mi trong T là đặc trưng m’j trong I. 2. P(i) = null: nghĩa là đặc trưng mi trong T không có đặc trưng tương ứng trong I. 3. Một đặc trưng m’j trong I, với mọi i = 1…m không có đặc trưng tương ứng trong T. 7 Điểm gốc thường được chọn như là đặc trưng trung tâm; trước khi đối sánh, tọa độ của các đặc trưng được điều chỉnh bằng việc trừ tọa độ điểm gốc. Trang 56 4. Mọi i = 1..m, k = 1..m, I ≠ k ⇒P(i) ≠ P(k) hay P(i) = P(k) = null (điều này yêu cầu mỗi đặc trưng trong I được liên hệ tối đa với một đặc trưng trong T). Thường p(i) = j không có nghĩa là đặc trưng m’j và mi khớp nhau theo biểu thức 3.20 và 3.21 mà nghĩa là các cặp này tương tự nhau theo công thức biến đổi hiện tại. Biểu thức 3.23 yêu cầu số các đặc trưng tương ứng được cực đại, độc lập với các giới hạn của các đặc trưng tương ứng này: nghĩa là nếu hai đặc trưng thỏa mãn biểu thức 3.20 và 3.21. Sau đó, đưa chúng vào biểu thức 3.23 thì tạo ra sự độc lập về khoảng cách và về sự khác nhau của hướng. Một công thức khác biểu thức 3.23 được đưa ra với phần dư (nghĩa là khoảng cách và sự khác nhau về hướng giữa các đặc trưng) được xem xét cho canh chỉnh tối ưu. Giải quyết bài toán đối sánh đặc trưng (biểu thức 3.23) là dễ khi canh chỉnh đúng (Δx, Δy, θ) đã được biết. Trong thưc tế, việc ghép cặp (nghĩa là hàm P) có thể được quyết định bằng cách thiết lập riêng cho mỗi i = 1…m: • jiP =)( nếu )(,, jyxj mmapm ′=′′ ΔΔ θ có giá trị gần mi nhất giữa đặc trưng { }1),(,..1)(,, =′′=′=′′ ΔΔ ikkyxk mmmmnkmmapm θ ; • P(i) = null nếu ( )( ) 0,,..1 ,, =′=∀ ΔΔ ikyx mmmapmmnk θ . Để thỏa mãn với ràng buộc 4 ở trên, mỗi đặc trưng jm ′′ đã bắt cặp phải được đánh dấu, để tránh bắt cặp hai lần. Hình 3.16 thể hiện về các đặc trưng được bắt cặp cho bởi các canh chỉnh vân trước. Trang 57 Hình 3.16 Các đặc trưng của I được ánh xạ về hệ toạ độ của T. Các đặc trưng của I ký hiệu là os còn các đặc trưng của T ký hiệu là xs. Chú ý các đặc trưng của I ở trên hình được tham chiếu đến như m”, vì chúng đã được ánh xạ về hệ tọa độ của T. Vòng gạch liên tiếp chỉ khoảng cách lớn nhất, vòng xám chỉ các cặp đặc trưng bắt cặp thành công. Để đạt được sự bắt cặp tối ưu (theo biểu thức 3.23), một lược đồ phức tạp hơn được chọn: trên thực tế, trong trường hợp khi một đặc trưng ở I rơi vào độ sai của hơn một đặc trưng của T, việc gán tối ưu là cực đại số các cặp đặc trưng (xem hình 3.16 như là một ví dụ đơn giản). Hình 3.17 Trong ví dụ này, nếu m1 bắt cặp với 2m ′′ (đặc trưng gần nhất), m2 sẽ không được bắt cặp; tuy nhiên, việc bắt cặp m1 với 1m ′′ , cho phép m2 được bắt cặp với m2, làm cực đại biểu thức 3.23. Sự cực đại trong biểu thức 3.23 có thể được giải quyết dễ dàng nếu hàm P (phù hợp đặc trưng) được biết trước. Trong trường hợp này, một canh chỉnh (Δx, Δy, θ) có thể Trang 58 được xác định trong hình vuông hai chiều nhỏ nhất. Nhưng trong thực tế, tất cả các tham số canh chỉnh và hàm tương ứng P đều không được biết trước; do đó, giải quyết bài toán đối sánh là một vấn đề rất khó khăn. Một phương pháp khác đã được đưa; ví dụ, Huvananda, Kim và Hwang (2000) đã giả sử một cách thô là lượng tử các vị trí đặc trưng và thực hiện tìm kiếm vét cạn để tìm ra canh chỉnh tối ưu. Vậy vấn đề của bài toán đối sánh đặc trưng là bài toán đối sánh mẫu điểm (point pattern matching). Đối sánh mẫu điểm là hướng được nghiên cứu mở rộng, được biết tới nhiều như: các phương pháp hồi phục (relaxation methods) [36], các giải pháp đại số và nghiên cứu hoạt động (operational research solutions) [9], các phương pháp tỉa cây (tree- prunning approaches) [3], các phương pháp tối thiểu năng lượng (energy- minimization methods) [2], biến đổi Hough [39], … 3.3.3.3 Đối sánh đặc trưng cục bộ và toàn cục Đối sánh đặc trưng cục bộ (local minutiae matching) bao gồm việc so sánh hai dấu vân tay căn cứ vào các cấu trúc đặc trưng cục bộ; các cấu trúc cục bộ được đặc tính hóa độc lập với các phép biến đổi trên toàn cục (như sự dịch chuyển, sự quay, ...); do đó, không cần canh chỉnh trên toàn cục trước khi đối sánh vân tay. Việc đối sánh cục bộ và toàn cục làm cho việc đối sánh sẽ trở nên đơn giản, độ phức tạp tính toán giảm; phù hợp với những hình vân tay bị biến dạng (méo mó hay bị co giản), và độ phân biệt cao với các ngón tay khác. Jiang và Yau (2000) [21] và Ratha (2000) [37] đã đề nghị một vài kỹ thuật cho loại đối sánh này. Cấu trúc cục bộ của Jaing và Yau đưa ra có dạng là một đặc trưng trung tâm cùng với hai đặc trưng láng giềng gần nó nhất; véc tơ vi là đặc tính của đặc trưng mi, mj là đặc trưng láng giềng gần mi nhất, mk là đặc trưng láng giềng gần mi thứ nhì. Vi = [dij, dik, θij, θik, ijϕ , ikϕ , nij, nik, ti, tj, tk], Trong đó dab là khoảng cách giữa đặc trưng ma và mb, θab là độ lệch hướng giữa góc θa và θb của ma và mb, abϕ độ lệch hướng giữa góc θa của ma và hướng của cạnh nối từ ma đến mb, nab là số vân giữa ma và mb, và ta là loại đặc trưng của ma (hình 3.18). Trang 59 Hình 3.18 Các đặc tính của cấu trúc cục bộ được dùng bởi Jiang và Yau (2000). Việc đối sánh đặc trưng cục bộ được thực hiện bằng việc tính toán mỗi cặp đặc trưng mi và m’j, i = 1..m, j = 1..n, một khoảng cách trọng số giữa các véc tơ vi và v’j. Cặp đối sánh tốt nhất được chọn và được dùng làm điểm tham chiếu (reference point) cho hai dấu vân tay. Các véc tơ đặc tính của các cặp còn lại được canh chỉnh theo điểm tham chiếu để đối sánh và kết quả đối sánh được tính toán dựa vào độ khác biệt của các cặp đối sánh này. Ratha (2000) định nghĩa khái niệm của cấu trúc cục bộ bằng việc sử dụng ghi chú đồ thị (graph notation). Cho trước một khoảng cách dmax, một đồ thị Si sẽ là các đặc trưng có khoảng cách nhỏ hơn hay bằng dmax của đặc trưng mi. Si = (Vi, Ei). Trong đó Vi chứa tất cả các đặc trưng mj mà khoảng cách của nó tính từ mi nhỏ hơn hay bằng dmax: Vi = {mj | sd(mi, mj) <= dmax}. Ei là tập các cạnh Ei = {eij}; trong đó, eij là cạnh nối từ mi tới mj trong Vj, eij được đánh nhãn với 5 trường (i, j, d(mi, mj), rc(mi, mj), ijϕ ), rc(mi, mj) là số vân giữa mi và mj, ijϕ là góc tạo thành bởi cạnh với trục x. 3.3.4 Đối sánh dựa vào đặc tính vân Việc rút trích các đặc trưng sẽ gặp rất nhiều khó khăn trong các ảnh vân tay chất lượng thấp. Trong khi các đặc tính (feature) khác của mẫu vân (ridge pattern), hướng Trang 60 và tần số cục bộ, hình dạng vân, thông tin kết cấu, có thể được rút trích một cách tin cậy hơn các đặc trưng; do vậy, kỹ thuật này dựa vào các đặc tính được rút trích từ các mẫu vân để đối sánh vân tay. Về nguyên lý, đối sánh dựa độ tương quan và đối sánh dựa vào đặc trưng có thể được xem như là một phần của đối sánh dựa đặc tính vân, theo cách hiểu mật độ điểm ảnh, vị trí đặc trưng là những đặc tính của mẫu vân ngón tay [31]. Ba lý do chính dùng kỹ thuật này để đối sánh vân tay: 1. Các đặc trưng được rút trích từ vân tay chất lượng thấp thì có độ tin cậy thấp. Mặc dù các đặc trưng có thể mang hầu hết các thông tin đúng đắn, nhưng chúng không phải lúc nào cũng đáp ứng được sự chính xác và tốc độ. 2. Rút trích đặc trưng rất tốn thời gian. Ngày nay, các máy tính đã chạy rất nhanh, nên đây không còn là vấn đề. Dù vậy tốc độ đối sánh vân tay vẫn được quan tâm bởi vì nhu cầu nhúng các thuật toán nhận dạng giá thành hạ vào trong các hệ thống chạy độc lập, hay các hệ thống nhúng ngày càng tăng. 3. Các đặc tính thêm vào có thể sử dụng cùng với các đặc trưng để tăng sự chính xác và tốc độ. Các đặc tính khác thường được sử dụng để đối sánh: 1. Kích thước của vân tay và hình dạng ngoài của vân tay. 2. Số lượng, loại vân tay, và vị trí các điểm đơn (core, delta). 3. Mối liên hệ không gian và các thuộc tính hình học của đường vân. 4. Các đặc tính hình dạng được đưa ra bởi Takeda. 5. Thông tin kết cấu toàn cục và cục bộ của vân tay. 6. Các lỗ chân lông. 7. Các đặc tính nhỏ được đưa ra bởi Polikarpova. Nói chung, các đặc trưng ở 1 và 2 thường không ổn định, và chúng thay đổi theo phần ngón tay tiếp xúc lên bộ cảm biến. Các lỗ chân lông rất rõ ràng, nhưng phải cần Trang 61 các máy quét đắt tiền có độ phân giải cao mới có thể phát hiện chúng. Việc dùng mối liên hệ không gian của các vân lập thành các phương pháp cấu trúc cơ bản được đưa ra bởi Moayer và Fu (1986), Isenor và Zaky (1986). Phương pháp Moayer dùng các ngữ pháp cây để phân loại các mẫu đường vân sau khi chúng được nhị phân hóa và làm mỏng vân. Phương pháp Flu đối sánh đồ thị tăng dần được thực hiện để so sánh một tập các vân được sắp xếp trong các cấu trúc đồ thị. Ceguerra và Koprinska (2002) đưa ra các đặc tính dựa vào hình dạng (shape-base), bao gồm chữ ký hình dạng một chiều mã hóa hình dạng chung của vân tay được tạo ra từ ảnh vân tay hai chiều sử dụng trục tham chiếu. Đối sánh dựa vào hình dạng sau đó được áp dụng cùng với đối sánh dựa vào đặc trưng để đưa ra quyết định cuối cùng. Thông tin cấu trúc toàn cục và cục bộ là đặc tính khác quan trọng cho việc đối sánh vân tay dựa vào cấu trúc và đặc trưng vân đang là hướng nghiên cứu. Các cấu trúc được định nghĩa bằng quan hệ không gian giữa các thành phần cơ bản và đặc trưng hóa bởi các thuộc tính như độ co giãn, hướng vân, tần số vân, … Jain [17] đề nghị kỹ thuật phân tích cấu trúc cục bộ trong vùng vân tay quan tâm chứa điểm core (hình 3.19). Thông tin cấu trúc cục bộ trong mỗi phần (sector) được phân rã thành các kênh (channels) riêng biệt bằng việc sử dụng Gabor filterbank. Kỹ thuật này còn được gọi là FingerCode. Trang 62 Hình 3.19 Sơ đồ nhận dạng vân tay dùng kỹ thuật FingerCode. 3.3.5 So sánh hiệu năng của các phương pháp đối sánh vân tay Các phương pháp đối sánh vân tay đều có ưu và khuyết điểm cho riêng mình. Đâu mới là thuật toán tốt nhất cho đối sánh vân tay. Để so sánh hiệu năng của các phương pháp đối sánh vân tay là rất khó vì hai lý do chính sau [31]: 1. Hiệu năng của một phương pháp nhận dạng vân tay liên quan đến nhiều độ đo hiệu năng khác nhau: độ chính xác (FMR, FNMR, …), độ hiệu quả (thời gian đăng ký và thời gian xác nhận), tính mềm dẻo trong nhận dạng 1:N, kích cỡ của mẫu, … Các ứng dụng khác nhau có yêu cầu hiệu năng cũng khác nhau; ví dụ, các ứng dụng khác nhau có thể sử dụng một thuật toán đối Trang 63 sánh vân tay với độ chính xác thấp hơn nhưng lại có cõ mẫu nhỏ hơn so với thuật toán chính xác cao hơn nhưng sử dụng cỡ mẫu lớn hơn. 2. Hầu hết các kết quả khoa học được công bố trong các bài báo là các kết quả thực nghiệm được thực hiện trên cơ sở dữ liệu sử dụng các giao thức khác nhau, mà thường không chia sẻ với cộng đồng nghiên cứu. Chính điều này tạo khó khăn để so sánh các phương pháp khác nhau; hiệu năng đo được không có một điểm chuẩn để so sánh. 3.3.6 Kết luận Trong ba phương pháp đối sánh vân tay, phương pháp đối sánh dựa vào đặc trưng được sử dụng nhiều nhất. Trong các cuộc thi nhận dạng vân tay (FVC8), điển hình là FVC2006 [7], hầu hết các thuật toán tham dự cuộc thi đều dựa vào các đặc trưng để đối sánh vân tay, và hiệu năng của các thuật toán dùng phương pháp này có thứ hạng ở vị trí cao nhất trong bảng tổng sắp; ngoài ra, phương pháp này cũng phù hợp với tính chất của hệ thống nhúng nhất so với hai phương pháp còn lại. Do vậy trong luận văn này, phương pháp đối sánh dựa vào đặc trưng đã được cài đặt lên Hệ thống nhúng, xem trong mục 6.4.3.2. 8 Fingerprint verification competition (FVC) là cuộc thi uy tín nhằm đánh giá hiệu năng của các thuật toán Nhận dạng vân tay.