Một số thuật 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