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 19 Chương 2 Tổng quan nhận dạng vân tay " Nội dung của chương này trình bày tổng quan nhận dạng vân tay, giới thiệu mô hình cùng với sơ đồ các bước xử lý tiêu biểu trong nhận dạng vân tay. Đặc biệt ở cuối chương này sẽ trình bày cách đánh giá một hệ thống nhận dạng vân tay. 2.1 Một số loại đặc trưng vân tay Dấu vân tay được hình thành dưới tác động của hệ thống gen di truyền mà thai nhi được thừa hưởng và tác động của môi trường thông qua hệ thống mạch máu và hệ thống thần kinh nằm giữa hạ bì và biểu bì. Một dấu vân tay được sao chép lại từ lớp biểu bì da khi ấn ngón tay vào một bề mặt phẳng. Cấu trúc của vân tay là các vân lồi và vân lõm (hình 2.1). Vân lồi có màu tối trong khi vân lõm có màu sáng. Vân lồi thường có độ rộng từ 100 mμ đến 300 mμ . Độ rộng của một cặp vân lồi lõm cạnh nhau là 500 mμ . Các chấn thương như: bỏng nhẹ, mòn da, ... không ảnh hưởng đến cấu trúc bên dưới của vân tay, khi da mọc lại cấu trúc này khôi phục lại như cũ [31]. Hình 2.1 Vân lồi và vân lõm của một ngón tay. Trang 20 Vân lồi và vân lõm thường nằm song song với nhau, nhưng đôi lúc chúng tạo thành điểm rẽ nhánh (bifurcation point) hay điểm kết thúc (ending point). Ở mức độ tổng thể, các mẫu vân tay thể hiện các vùng vân khác nhau mà ở đó các đường vân có hình dạng khác biệt. Những vùng này (gọi là các vùng đơn) có thể được phân loại thành các dạng: loop, delta và whorl (hình 2.2) và được ký hiệu tương ứng là ΩΔ∩ ,, . Vùng whorl có thể được mô tả bởi hai vùng loop đối diện nhau. Hình 2.2 Hình vuông màu trắng vùng đơn chứa điểm đặc biệt và vòng tròn màu trắng là điểm core. Một vài thuật toán đối sánh vân tay căn lề ảnh vân tay theo một điểm trung tâm gọi là điểm core. Vào năm 1900, Henrry đã định nghĩa điểm core là “điểm nằm về phía bắc nhất của đường vân nằm trong cùng nhất”. Thực tế, điểm core là điểm trung tâm của vùng loop nằm về phía bắc nhất. Nếu vân tay không chứa các vùng loop hay whorl thì điểm core là điểm mà tại đó độ cong của đường vân là lớn nhất. Định nghĩa các vùng đơn (singular region) thường được sử dụng để phân loại vân tay, với mục đích làm đơn giản hóa các quá trình tìm kiếm (hình 2.3). Trang 21 Hình 2.3 5 phân lớp chính của một vân tay Ở mức độ cục bộ, các đặc tính quan trọng, gọi là các đặc trưng (minutiae), được tìm thấy trong các mẫu vân tay. Các đặc trưng là điểm kết thúc, hay điểm rẽ nhánh, … Francis Galton (1822-1911) là người đầu tiên phân loại đặc trưng và phát hiện chúng không thay đổi trong suốt cuộc đời của một cá nhân. Vào năm 1986, viện chuẩn quốc gia Mĩ (ANSI) đề nghị phân loại đặc trưng theo bốn loại gồm: điểm kết thúc, điểm rẽ hai, điểm rẽ ba, và điểm không xác định. Trong khi đó mô hình đặc trưng của cục điều tra liên bang Mĩ (FBI) chỉ phân thành hai loại: là điểm kết thúc và điểm rẽ hai. Mỗi đặc trưng được xác định bằng hệ tọa độ (x,y), và góc tạo bởi tiếp tuyến của đường vân tại đặc trưng và trục ngang. Hình 2.4 Các loại đặc trưng phổ biến. Trong các ảnh vân tay, các điểm kết thúc và rẽ hai có thể tráo đổi cho nhau và ở cùng vị trí, ở ảnh âm bản2 điểm kết thúc xuất hiện như là điểm rẽ hai và ngược lại (hình 2.5). 2 Ảnh âm bản (negative image) trong hình vân tay là ảnh có màu của vân lồi và vân lõm đảo lại cho nhau. Trang 22 Hình 2.5 b) là ảnh âm bản của hình a). 2.2 Mô hình hệ thống nhận dạng vân tay Kiến trúc của hệ thống thống nhận dạng vân tay trong hình 2.6 là một mô hình tiêu biểu. Kiến trúc này bao gồm 4 thành phần chính: • Phần người dùng (user interface): Cung cấp cơ chế cho người dùng đưa dấu vân tay của mình vào hệ thống. • CSDL hệ thống (system database): Dùng để lưu trữ các mẫu vân tay của người dùng vào CSDL. • Phần đăng ký (enroll module): Cho phép đăng ký các dấu vân tay của người dùng vào CSDL của hệ thống. • Phần xác nhận (authentication module): Cho phép xác nhận một người đã có đăng ký vào trong một hệ thống hay chưa. Khi người dùng cần đăng ký dấu vân tay của mình vào hệ thống. Đầu tiên thiết bị sẽ lấy dấu vân tay của người dùng; tiếp đó, người dùng cung cấp các thông tin cá nhân của mình cho hệ thống. Sau đó hệ thống dùng thuật toán rút trích đặc trưng (minutiae extraction) để rút trích các đặc trưng của vân tay người dùng. Một thuật toán kiểm định chất lượng ảnh vân tay trước khi hệ thống đưa các đặc trưng này vào CSDL. Khi người dùng cần xác thực dấu vân tay của mình trong hệ thống. Đầu tiên, thiết bị sẽ lấy dấu vân tay của người dùng; tiếp đó, hệ thống dùng thuật toán rút trích đặc Trang 23 trưng để rút trích đặc trưng vân tay của người dùng. Sau đó, hệ thống sẽ đối sánh các đặc trưng dấu vân tay người dùng đưa vào với tất cả các đặc trưng vân tay có trong CSDL của hệ thống. Cuối cùng, hệ thống sẽ trả kết quả ra cho người dùng. Hình 2.6 Kiến trúc của hệ thống nhận dạng vân tay tự động. 2.3 Sơ đồ các bước xử lý trong quá trình nhận dạng Hình 2.6 là một sơ đồ tiêu biểu của các bước xử lý trong quá trình nhận dạng vân tay. Quá trình xử lý nhận dạng này được chia ra làm hai quá trình lớn: quá trình xử lý ảnh (image processing) và quá trình đối sánh vân tay (matching). 2.3.1 Quá trình xử lý ảnh (image processing) Mục đích của quá trình này là tăng cường ảnh vân tay. Sau đó, rút trích đặc trưng vân tay từ ảnh đã được tăng cường. Quá trình này được thực hiện qua các bước nhỏ sau: • Tăng cường ảnh (image enhancement): ảnh được lấy từ thiết bị đầu đọc vân tay sẽ được làm rõ. 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, dơ bẩn, hay do lực ấn ngón tay trong lúc lấy vân tay [15]; do vậy, bước này là một trong các bước quan Trang 24 trọng nhất của quá trình này để làm rõ ảnh vân tay để rút trích các đặc trưng đúng và đầy đủ. • Phân tích ảnh (image analysis): thông qua phân tích ảnh, ảnh sẽ được loại bỏ những thông tin nhiễu hay những thông tin không cần thiết. • Nhị phân hóa (binarization): nhị phân hóa ảnh vân tay thành ảnh trắng đen. Bước này phục vụ cho bước Làm mỏng vân tay. • Làm mỏng (thinning): làm mỏng các đường vân lồi của ảnh vân tay. Bước này nhằm mục đích cho việc rút trích đặc trưng của vân tay. • Rút trích đặc trưng (minutiae extraction): rút trích những đặc trưng cần thiết cho quá trình đối sánh vân tay. 2.3.2 Quá trình đối sánh vân tay (matching) Mục đích của quá trình này là đối sánh vân tay dựa trên các đặc trưng đã được rút trích. Quá trình này được thực hiện qua các bước nhỏ sau: • Phân tích đặc trưng (minutiae analysis): phân tích các đặc điểm cần thiết của các đặc trưng để phục vụ cho việc đối sánh vân tay. • Xét độ tương tự cục bộ (local similarity): thuật toán đối sánh vân tay sẽ dựa vào các thông tin cục bộ của các đặc trưng3 của vân tay để tìm ra các cặp đặc trưng giống nhau giữa hai vân tay. • Xét độ tương tự toàn cục (global similarily): từ những khu vực tương tự nhau trên cục bộ, thuật toán sẽ tiếp tục mở rộng đối sánh trên toàn cục. • Tính điểm đối sánh (calculate matching score): tính toán tỷ lệ độ giống nhau giữa các cặp đặc trưng. Điểm đối sánh này sẽ cho biết độ giống nhau của hai ảnh vân tay là bao nhiêu. 3 Thông tin cục bộ của một đặc trưng là: tọa độ (x,y), hướng của đặc trưng, góc tạo bởi tiếp tuyến của đường vân tại đặc trưng và trục ngang. Trang 25 Hình 2.7 Sơ đồ các bước nhận dạng vân tay. 2.4 Cách đánh giá hệ thống nhận dạng vân tay 2.4.1 Đặt vấn đề Cách đánh giá một hệ thống nhận dạng vân tay tương tự như cách đánh giá của một hệ thống sinh trắc. Nhóm tác giả Phillips định nghĩa ba kiểu đánh giá của hệ thống sinh trắc [35]: • Đánh giá công nghệ (technology evaluation): đánh giá này nhằm mục đích so sánh các thuật toán với nhau. Việc kiểm tra các thuật toán được thực hiện trên một hay nhiều CSDL (CSDL này thường là CSDL chuẩn dành cho các cuộc thi quốc tế). • Đánh giá toàn cảnh (scenario evaluation): đánh giá này nhằm mục đích xác định toàn bộ hiệu năng hệ thống nhận dạng trong một ứng dụng giả lập dùng để kiểm tra. Hệ thống nhận dạng được kiểm tra giống hệt như trong một môi trường thế giới thực. • Đánh giá hoạt động (operational evaluation): đánh giá này nhằm mục đích xác định hiệu năng của một hệ thống sinh trắc hoàn thiện trong một môi Trang 26 trường ứng dụng cụ thể với một dữ liệu được thu thập trực tiếp từ thiết bị để kiểm tra; do đó, kết quả kiểm tra của mỗi lần sẽ là khác nhau. Trong đánh giá toàn cảnh và đánh giá hoạt động, độ chính xác của một hệ thống sinh trắc phụ thuộc rất nhiều vào các yếu tố như: bộ dữ liệu kiểm tra, môi trường thử nghiệm, chế độ hoạt động của hệ thống, sự ràng buộc của ứng dụng dùng hệ thống sinh trắc, … 2.4.2 Các lỗi hệ thống sinh trắc Để đánh giá độ chính xác của một hệ thống sinh trắc, ta sẽ căn cứ vào điểm đối sánh giữa hai mẫu, gọi là điểm đối sánh s. Điểm đối sánh, có giá trị nằm trong [0,1], được dùng để lượng hóa độ tương tự giữa một mẫu đặc trưng đầu vào và một mẫu đặc trưng đã được lưu trong CSDL. Nếu hai mẫu đặc trưng này càng giống nhau thì điểm đối sánh s càng có khả năng gần giá trị 1, ngược lại hai mẫu càng không giống nhau thì điểm đối sánh s càng gần giá trị 0. Quyết định của hệ thống được điều khiển bởi ngưỡng t. Với điểm đối sánh s, ta có [31]: • Nếu s ≥ t: cặp đối sánh (nghĩa là hai mẫu của cùng một người). • Nếu s ≤ t: cặp không đối sánh (nghĩa là hai mẫu không của cùng một người). • Thông thường một hệ thống xác thực sinh trắc xem xét hai lỗi sau: o Kiểm tra độ đo sinh trắc từ hai mẫu hoàn toàn khác nhau nhưng kết quả xác thực lại cho là chúng cùng một mẫu (ta gọi là đối sánh sai). o Kiểm tra độ đo sinh trắc từ hai mẫu giống nhau nhưng kết quả xác thực lại cho là hai mẫu hoàn toàn khác nhau (ta gọi là không-đối sánh sai). Trong môi trường thương mại, hai lỗi trên tương ứng được dùng là tỷ lệ chấp nhận sai (false acceptance rate (FAR)) và tỷ lệ từ chối sai (false rejection rate (FRR)). Trang 27 2.4.3 Các lỗi hệ thống xác thực Gọi T là mẫu sinh trắc của một người đã được lưu trữ trước đó, I là mẫu sinh trắc đầu vào cần được xác thực. Các giả thuyết đặt ra là: • H0: I ≠ T, mẫu sinh trắc đầu vào và mẫu sinh trắc đã được lưu trước không phải của cùng một người. • H1: I = T, mẫu sinh trắc đầu vào và mẫu sinh trắc đã được lưu trước là của cùng một người. Tương ứng có các kết luận: • D0: người này không phải là người có mẫu sinh trắc đã được lưu trữ trong hệ thống. • D1: người này đúng là người có mẫu sinh trắc đã được lưu trữ trong hệ thống. Đối sánh trong xác thực T và I sử dụng điểm độ tương tự s(T,I). Nếu điểm độ tương tự nhỏ hơn ngưỡng t thì kết quả là D0, nếu điểm độ tương tự lớn hơn hoặc bằng ngưỡng t thì cho kết luận D1. Từ các giả thuyết trên, một hệ thống xác thực có hai loại lỗi sau: • Dạng I: đối sánh sai (kết luận là D1 khi H0 đúng). • Dạng II: không-đối sánh sai (kết luận là D0 khi H1 đúng). Vậy tỷ lệ đối sánh sai (FMR) là xác suất của lỗi loại I, tỷ lệ không-đối sánh sai (FNMR) là xác suất của lỗi loại II: • FMR = P(D1| H0 đúng). • FNMR = P(D0| H1 đúng). Để đánh giá độ chính xác của một hệ thống sinh trắc, ta phải thống kê các điểm đối sánh s của các cặp mẫu giống nhau (phân bố p(s|H1 đúng) - thường được gọi là phân bố đích thật), và điểm đối sánh s của các cặp mẫu khác nhau (phân bố p(s|H0 sai) - Trang 28 thường được gọi là phân bố mạo danh). Hình 2.8 minh họa cách tính FNMR và FMR. Trong đó cho trước một ngưỡng t. FMR là phần trăm của các cặp mạo danh có điểm đối sánh lớn hơn hay bằng t và FNMR là phần trăm các cặp chân thật có điểm đối sánh nhỏ hơn t. ∫ == t dstrueHspFNMR 0 1 )|( , ∫ == 1 0 )|( t dstrueHspFMR . Hình 2.8 Minh họa cách tính FMR và FNMR. Cả FMR và FNMR thực ra là hàm của ngưỡng hệ thống theo t; do đó, chúng ta có thể được viết tương ứng là FMR(t) và FNMR(t). Nếu t giảm thì hệ thống sẽ bỏ qua nhiều lỗi và FMR(t) sẽ tăng, ngược lại khi tăng t hệ thống sẽ an toàn hơn nhưng FNMR(t) sẽ tăng tương ứng. Một người thiết kế hệ thống xác thực thường không biết trước hệ thống của mình sẽ ứng dụng ở lĩnh vực nào; do đó, họ báo cáo hiệu năng hệ thống ở tất cả các điểm hoạt động (ngưỡng t) bằng cách xây dựng đường cong đặc tính hoạt động (receiver operating characteristic (ROC)). Đường cong này biểu diễn các giá trị FNMR và FMR theo ngưỡng t. Trang 29 Bên cạnh các phân bố và đồ thị trên, một vài chỉ số khác được dùng để đánh giá độ chính xác của một hệ thống xác thực. • Tỉ lệ lỗi trung bình (EER): là tỷ lệ lỗi tại ngưỡng t mà FMR(t) = FNMR(t). Trên thực tế, vì các phân bố điểm đối sánh không liên tục nên điểm EER có thể không tồn tại (hình 2.9). Trong trường hợp này, thay vì đưa ra một giá trị đơn duy nhất, người ta đưa ra một khoảng [29]. Mặc dù EER là một chỉ số quan trọng, nhưng các hệ thống kiểm tra vân tay ít khi dùng EER làm ngưỡng hoạt hoạt động của hệ thống, mà thường dùng một ngưỡng nghiêm ngặt hơn sao cho FMR thấp, và chấp nhận FNMR cao hơn một chút. • ZeroFNMR là giá trị FMR nhỏ nhất mà tại đó không xảy ra không-đối sánh sai. • ZeroFMR là giá trị FNMR nhỏ nhất mà tại đó không xảy ra đối sánh sai. • Tỉ lệ thất bại trong việc lấy mẫu sinh trắc (FTC) là tỷ lệ phần trăm mà thiết bị đầu đọc sinh trắc không thể tự động lấy mẫu sinh trắc từ người dùng. • Tỷ lệ thất bại trong lúc đăng ký (FTE) là tỷ lệ phần trăm mà người dùng không đăng ký với hệ thống. Có mối liên hệ giữa FTE và độ chính xác (FMR và FNMR) của một hệ thống. Nếu việc đăng ký lấy mẫu cho hệ thống có chất lượng tốt thì độ chính xác của hệ thống (FMR và FNMR) sẽ tăng lên. • Tỷ lệ thất bại trong đối sánh (FTM) là tỷ lệ phần trăm mẫu đầu vào không thể được xử lý hay đối sánh với một mẫu sinh trắc đã được lưu trước đó nhưng không đủ chất lượng. Trang 30 Hình 2.9 Đánh giá của thuật toán xác thực vân tay qua CSDL DB1 của FVC2002: a) các phân bố chân thật và mạo danh được tính trên 2800 cặp chân thật và 4950 cặp mạo danh; b) FMR(t) và FNMR(t) được tính từ các phân bố ở a); c) đường cong ROC dẫn xuất từ FMR(t) và FNMR(t) ở b) [31]. Trang 31 Hình 2.10 Minh họa EER, ZeroFNMR và ZeroFMR theo đường cong FMR(t) và FNMR(t) [31]. 2.4.4 Các lỗi hệ thống nhận dạng Các lỗi hệ thống nhận dạng được mở rộng từ định nghĩa Các lỗi hệ thống xác thực. Hình 2.11 Các điểm hoạt động hệ thống tiêu biểu của các ứng dụng trình bày trên đường cong ROC. Trang 32 Giả sử hệ thống không dùng các cơ chế đánh chỉ mục trong truy tìm (nghĩa là hệ thống sẽ tìm kiếm vét cạn trên toàn bộ tập dữ liệu chứa N mẫu sinh trắc), và mỗi người chỉ có một mẫu sinh trắc được lưu trữ. Tương ứng ký hiệu FNMRN và FMRN là tỷ lệ không-đối sánh sai và tỷ lệ đối sánh sai trong một hệ thống nhận dạng thì: • FNMRN = FNMR: xác suất của lỗi không-đối sánh [6]; • FMRN = 1 – (1 – FMR)N: một lỗi đối sánh sai xảy ra khi mẫu sinh trắc đầu vào đối sánh nhầm với một hay nhiều mẫu sinh trắc đã được lưu trong CSDL. (1 – FMR) là xác suất không xảy ra đối sánh sai với một mẫu sinh trắc đã được lưu trong CSDL, và (1 – FMR)N là xác suất không xảy ra đối sánh sai với toàn bộ CSDL mẫu. Nếu FMR nhỏ thì FMRN tương đương với N. Vậy FMR tỷ lệ đối sánh sai tăng tuyến tính với kích thước CSDL mẫu. Kết quả này hàm ý quan trọng cho những hệ thống nhận dạng lớn. Thông thường tốc độ xử lý được xem là vấn đề lớn trên các hệ thống dạng này. Nhưng thực ra, độ chính xác mới là vấn đề lớn hơn. Xét một hệ thống có 10,000 người dùng. Để tăng tốc độ xử lý người ta có thể kết hợp thuật toán nhanh cùng với một kiến trúc hệ thống mạnh (xử lý song song). Đối với độ chính xác, nếu hệ thống cần độ chính xác ở 10-5 (chỉ sai 1 trên 100,000 lần đối sánh), thì FMRN gần là 10%. Nếu trong trường hợp các mẫu sinh trắc trong CSDL được phân loại và đánh chỉ mục, thì trong quá trình nhận dạng chỉ có một phần CSDL được lấy ra để xác thực. Khi đó: • FNMRN = RER + (1 – RER). FNMR; trong đó, RER (tỷ lệ lỗi truy xuất) là xác suất mẫu sinh trắc cần được tìm trong CSDL nhưng bị bỏ qua khi truy tìm; • FMRN = 1 – (1 – FMR)N–P; trong đó, P là tỷ lệ phần trăm trung bình các mẫu trinh trắc được tìm kiếm trong CSDL trong quá trình nhận dạng [6].