Luận văn Truy tìm ảnh vân tay trên cơ sở dữ liệu được gom nhóm

- 3 - Chương 1 . TỔNG QUAN 1.1 Giới thiệu Hiện nay, việc nhận dạng con người tự động được ứng dụng rộng rãi trong nhiều lĩnh vực của cuộc sống cũng như sử dụng trong các cơ quan hành pháp để nhận biết thông tin tội phạm, chẳng hạn nhúng trong các thiết bị điện tử như các thẻ thông minh, thẻ ATM, máy tính xách tay, máy kiểm tra tại cảng hàng không, thiết bị điều khiển truy cập mạng, ngân hàng điện tử, …. Nhận dạng theo cách truyền thống (ví dụ như mật khẩu, hộ chiếu, giấy phép lái xe, thẻ căn cước, …) có thiên hướng bị gian lận bởi vì mật khẩu có thể bị quên, hoặc thẻ có thể bị đánh cắp, làm giả bởi các tên lừa đảo. Vì vậy, nhận dạng theo cách này không đáp ứng được yêu cầu về an ninh trong xã hội kết nối thông tin, hiện đại. Hệ thống nhận dạng hoàn hảo nhất thiết cần dựa vào sinh trắc học. 1.2 Sinh trắc học Sinh trắc học là công nghệ phân tích và đo lường các đặc điểm cơ thể con người (chẳng hạn như dấu vân tay, võng mạc mắt và tròng đen, mẫu giọng nói, bàn tay, gương mặt, dáng đi, gen, chữ ký) cho mục đích chứng thực [3]. Các đặc điểm sinh trắc học là phân biệt duy nhất của mỗi người, không thể bị quên, hay bị mất và việc xác thực một người cần có sự xuất hiện của người đó. Do đó, sinh trắc học là đáng tin cậy hơn so với phương pháp truyền thống. Đặc điểm sinh trắc học gồm có như vân tay, khuôn mặt, bàn tay, võng mạc và tròng mắt, chữ ký, dáng đi, tiếng nói. Trong các đặc điểm này, hệ thống nhận dạng tự động dựa vào đặc điểm vân tay có chi phí thấp và rất đáng tin cậy. 1.3 Vân tay Vân tay là mẫu hình mà nó biểu diễn cấu trúc những đường vân (ridges) và rãnh (valleys) trên đầu ngón tay. Đặc điểm sinh học của vân tay là duy nhất cho mỗi cá - 4 - nhân. Trong nhiều thập kỷ qua, các cơ quan hành pháp đã phân loại và xác định danh tánh của từng vân tay là dựa vào những điểm kết thúc đường vân hoặc điểm nằm trên ngã rẽ đường vân (còn gọi là minutiae - các chi tiết vụn vặt). Bên cạnh đặc trưng cục bộ minutiae, vân tay còn có những đặc trưng khác như đặc trưng toàn cục - mẫu đường vân, đặc trưng đường vân với độ phân giải lớn [19]. Các đặc trưng này là nhất quán theo thời gian và duy nhất đối với cá nhân, nên được sử dụng trong các hệ thống nhận dạng vân tay. 1.3.1 Đặc trưng mức toàn cục Các đặc trưng mức toàn cục được rút ra từ cấu trúc của đường vân. Độ cong của các đường vân tạo thành các hình dạng đường vân khác nhau. Từ đó, có ba đặc trưng phổ biến được rút trích ra ở cấp độ này [1, 2, 19] bao gồm các điểm nổi bật (còn gọi là điểm delta và điểm core, xem Hình 1-1a), điểm nổi bật này kết hợp với đặc trưng hình dáng đường vân để phân lớp vân tay (thường được phân thành thành 5 nhóm chính vòng trái-left loop, vòng phải-right loop, vòng tròn-whorl, vòng cung- arch, vòng cung dạng lều-tented arch, Hình 1-2) và đặc trưng khoảng cách đường vân (xem Hình 1-1b). Các đặc trưng này có chi phí lưu trữ thấp nhưng nhạy cảm đối với ảnh vân tay chất lượng thấp. Hơn nữa, không thể sử dụng các đặc trưng này để phân biệt vân tay. Do vậy, các đặc trưng này thông thường được sử dụng trong việc tìm kiếm ảnh ở mức thô (phân lớp ảnh vân tay). (a) (b) ĐiểmCore Điểm Delta Khoảng cách đường vân Hình 1-1. (a) điểm nổi bật trên vân tay (điểm delta, điểm core). (b) khoảng cách đường vân - 5 - a) b) c) e) d) Hình 1-2. Các lớp vân tay theo phân lớp Henrry. (a) left loop. (b) right loop. (c) whorl. (d) arch. (e) tented arch. 1.3.2 Đặc trưng mức cục bộ a) b) c) e) d) Hình 1-3. Các đặc trưng cục bộ của vân tay. (a) Crossover. (b) Island. (c) Lake. (d) Bifurcation. (e) Ending - 6 - Francis Galton (1822-1911) là người đầu tiên quan sát và phân loại các đặc trưng minutiae, bao gồm các điểm gán đoạn đường vân như điểm kết thúc đường vân (ending), điểm rẽ nhánh (bifurcation), điểm chéo (crossovers), các đảo (islands), các hồ (lakes), các điểm cựa gà (spur), … (xem Hình 1-3). Hai đặc trưng thường dùng nhất là điểm kết thúc đường vân và điểm rẽ nhánh bởi vì các đặc trưng khác tổ hợp từ hai đặc trưng này. Các thuật toán so khớp tinh để đánh giá mức độ giống nhau của vân tay thường căn cứ vào đặc trưng này. 1.3.3 Đặc trưng đường vân với độ phân giải cao Đặc trưng này là các lỗ nằm trên đường vân của vân tay (đặc trưng sweat pore, xem Hình 1-4a) [12]. sweat pore b) a) pore Hình 1-4. Đặc trưng tuyến mồ hôi - (a) sweat pore. (b) pore Các lỗ này tạo ra là từ các tuyến mồ hôi của ngón tay. Để có được những đặc trưng này, vân tay phải được quét với máy có độ phân giải cao (1000 dpi), khi đó các pore này mới có thể xác định dễ dàng. Đặc trưng này không được sử dụng phổ biến. 1.4 Hệ thống nhận dạng vân tay tự động Tùy thuộc vào bối cảnh ứng dụng, nhìn chung, hệ thống nhận dạng vân tay tự động làm việc ở hai chế độ: xác thực vân tay và nhận biết vân tay [19]. 1.4.1 Hệ thống xác thực vân tay tự động Hệ thống xác thực vân tay tự động là hệ thống nhận dạng vân tay hoạt động theo chế độ xác thực vân tay. Trong chế độ này, người cần xác nhận sẽ cung cấp thông - 7 - tin nhận dạng cho hệ thống (ví dụ tên) cùng với vân tay của người đó. dựa vào thông tin nhận dạng , hệ thống sẽ lấy ảnh vân tay mẫu trong cơ sở dữ liệu kiểm tra có trùng khớp với vân tay truy vấn hay không? Nếu trùng khớp thì người này được xác minh đúng thông tin ngoài ra thì bị từ chối. Các giai đoạn xử lý của hệ thống xác thực được minh họa rõ trong Hình 1-5. Bộ cảm biến thu nhận vân tay Rút trích đặc trưng Cơ sở dữ liệu các mẫu vân tay và thông tin nhân dạng tương ứng Bộ cảm biến thu nhận vân tay Rút trích đặc trưng So khớp đặc trưng Chấp nhận / từ chối nhận dạng Thông tin nhận dạng (tên) Thông tin nhận dạng (tên) Giai đoạn xác nhận Giai đoạn lấy mẫu Hình 1-5. Các giai đoạn xử lý của hệ thống xác nhận vân tay 1.4.2 Hệ thống xác định vân tay tự động Hệ thống xác định vân tay vân tay tự động là hệ thống nhận dạng vân tay hoạt động theo chế độ nhận biết vân tay. Trong chế độ này, người cần nhận biết chỉ cung cấp ảnh dấu vân tay, hệ thống sẽ lấy tất cả các ảnh vân tay lưu trữ trong cơ sở dữ liệu ra để so khớp, từ đó xác định mẫu vân tay nào giống nhất trong cơ sở dữ liệu. Nếu mức độ giống nhau lớn hơn một ngưỡng xác định trước thì hệ thống sẽ lấy những thông tin của dấu vân tay mẫu giống nhất này là thông tin của người cần nhận biết. Các giai đoạn xử lý của hệ thống truy tìm ảnh vân tay được minh họa rõ trong Hình 1-6. - 8 - Bộ cảm biến thu nhận vân tay Rút trích đặc trưng Cơ sở dữ liệu các mẫu vân tay và thông tin liên quan Bộ cảm biến thu nhận vân tay Rút trích đặc trưng So khớp đặc trưng Nhận biết thông tin đối tượng nếu có Giai đoạn truy tìm Giai đoạn lấy mẫu Thông tin nhận dạng (tên) Hình 1-6. Các giai đoạn xử lý trong hệ thống truy tìm ảnh vân tay 1.5 Thách thức trong truy tìm ảnh vân tay Hệ thống truy tìm ảnh vân tay đối với cơ sở dữ liệu vân tay lớn, và phần lớn ảnh chất lượng thấp có nhiều thách thức. Các thách thức ban đầu liên quan đến vấn đề ảnh vân tay chất lượng thấp hoặc chỉ có một phần ảnh (xem Hình 1-7) bởi vì ảnh vân tay được thu nhận trong các tình trạng khác nhau: vị trí ấn, áp lực ấn, độ ẩm của da, bụi bẩn, … hoặc do thiết bị thu nhận kém. Dẫn đến, cần phải có các thuật toán hiệu quả để tiền xử lý ảnh vân tay, để thu được ảnh rõ ràng hơn. Đồng thời, cần phải có thuật toán so khớp vân tay hiệu quả đối với ảnh vân tay với nhiều trạng thái khác nhau như dịch chuyển, bóp méo, xoay. Bên cạnh đó, đối với cơ sở dữ liệu vân tay lớn, hệ thống truy tìm ảnh vân tay cần phải có một thuật toán phân lớp vân tay hiệu quả, nhằm thu hẹp không gian tìm kiếm mức so khớp tinh, đồng thời đảm bảo độ chính xác đối với trường hợp phần lớn vân tay trong cơ sở dữ liệu chất lượng thấp. Do vậy, bài toán này còn thu hút rất nhiều sự quan tâm của các nhà nghiên cứu. - 9 - a) b) c) d) Hình 1-7. Ảnh vân tay chất lượng thấp và biến dạng. (a) ảnh vân tay một phần. (b) ảnh vân tay bị nét đứt. (c) ảnh vân tay vị dính dầu. (d) ảnh vân tay bị xoay 1.6 Hiện trạng nghiên cứu về truy tìm ảnh vân tay. Để giải quyết bài toán thu hẹp không gian tìm kiếm đối với cơ sở dữ liệu lớn, hướng tiếp cận tìm kiếm nhiều mức thường được đề xuất. Trong đó, các đặc trưng toàn cục thường được sử dụng để thực hiện tìm kiếm ở mức độ thô nhằm làm giảm không gian tìm kiếm ở mức tinh. Việc tìm kiếm ở mức tinh thường căn cứ vào đặc trưng cục bộ. Vì vậy, cần thiết phải có một giải pháp thực hiện tìm kiếm vân tay ở mức thô vừa giảm không gian tìm kiếm vừa đảm bảo độ chính xác nhận dạng vân tay. Có nhiều giải pháp đã được đề xuất cho bài toán tìm kiếm ở mức độ thô như phân lớp rõ, đánh chỉ mục vân tay, phân lớp liên tục, gom nhóm vân tay. Phân lớp rõ các ảnh vân tay là hướng tiếp cận truyền thống mà nó được đầu tư nghiên cứu rất nhiều [9, 15, 25, 27]. Vân tay được phân vào một trong các lớp được định nghĩa trước chẳng hạn các lớp Henry. Mặc dù nó có những thuận lợi như con người dễ nhận biết, phân chia cơ sở dữ liệu thành một số lớp định nghĩa trước, nhưng thuật toán phân lớp tự động tốt nhất cũng chỉ có thể phân lớp vân tay thành 4 - 10 - hoặc 5 nhóm. Sự phân phối vân tay tự nhiên của 5 lớp của Henrry là 3.7% plain arch, 2.9 % tented arch, 33.8% left loop, 31.7% right loop và 27.9% whorl. Về trung bình, vân tay truy vấn vẫn cần được so sánh tinh với khoảng 29.48% các mẫu trong cơ sở dữ liệu để nhận dạng. Vì vậy, phân lớp rõ không hiệu quả trong việc thu hẹp không gian tìm kiếm trên cơ sở dữ liệu. Thực tế, không cần thiết phải phân lớp các vân tay thành các lớp mà con người có thể nhận biết rõ cho hệ thống nhận dạng vân tay. Đánh chỉ mục vân tay [3] là phương pháp phân chia cơ sở dữ liệu vân tay thành một số khối dựa vào bộ ba minutiae. Hướng tiếp cận này phân lớp các vân tay thành nhiều lớp hơn việc phân lớp riêng biệt bởi vì nó sử dụng những đặc trưng phân biệt như minutiae. Tuy nhiên, các điểm minutia là đặc trưng cục bộ quan trọng nhất và được sử dụng rộng rãi nhất các thuật toán so khớp vân tay mở mức tinh. Do đó, mặc dù hướng tiếp cận này có thể tăng tốc độ tìm kiếm của hệ thống, nhưng độ chính xác trong việc nhận dạng của hệ thống có thể bị suy giảm đáng kể vì các đặc trưng sử dụng trong tìm kiếm thô và so khớp tinh là có liên hệ nhiều với nhau. Phân lớp liên tục [5, 20] được đề xuất để khắc phục các vấn đề số lớp ít của phương pháp phân lớp rõ bằng cách sử dụng vectơ đặc trưng số hóa để biểu diễn vân tay. Tìm kiếm vân tay được thực hiện bằng cách so sánh ảnh vân tay truy vấn với tất cả các mẫu trong cơ sở dữ liệu và nhận ra mẫu gần nhất. Dù cho, việc so sánh giữa vân tay và mẫu nhanh hơn so với việc so khớp tinh, nhưng việc tìm kiếm vân tay một cách đầy đủ này gặp hạn chế với cơ sở dữ liệu lớn. Hơn nữa, việc phân lớp liên tục chỉ xếp hạng các mẫu trong cơ sở dữ liệu dựa vào mức độ giống nhau với ảnh vân tay truy vấn trong khi đó lại xem thường sự giống nhau giữa các mẫu trong cơ sở dữ liệu. Đây là giới hạn của phương pháp này trong việc tìm kiếm. Gom nhóm dữ liệu vân tay [17] là kĩ thuật đầy tìm năng cho thu gọn không gian truy tìm ảnh dựa vào nội dung bằng cách chỉ so sánh ảnh truy vấn với các đại diện của mỗi nhóm thay vì tất cả. Trong phương pháp này, các vân tay được gom nhóm dựa vào hai vector đặc trưng: vector hướng đường vân và vector khoảng cách đường vân. Sau đó, việc tìm kiếm ở mức thô sẽ diễn ra trên nhiều mức, mỗi mức - 11 - dựa vào một vector đặc trưng. Phương pháp này thu hẹp đáng kể không gian tìm kiếm và chính xác hơn so với các phương pháp khác (xem Bảng 1-1). Bảng 1-1. Minh họa tỉ lệ lỗi của việc truy tìm theo hướng tiếp cận phân lớp rõ và hướng tiếp cận gom nhóm được thực hiện trên cơ sở dữ liệu NIST DB4 [17] Phương pháp Tác giả và năm PR=20% 5 lớp PR=29.5 % 5 lớp PR=28% 4 lớp PR=29.7% 4 lớp Tập kiểm tra Candela (1995) — — 11.4 6.1 Phần 2 Karu và Jain (1996) 14.6 11.9 8.6 9.4 Toàn bộ Jain (1999) 10 7.0 5.2 — Phần 2 Jain và Minut (2002) — — 8.8 9.3 Toàn bộ Cappelli (1999) — 12.9 — — Tập 2 Cappelli (1999) 7.9 6.5 5.5 — Phần 2 Senior (2001) — — — 5.1 Phần 2 Yao (2001) 10.7 9.0 6.9 — Phần 2 Marcialis (2001) 12.1 9.6 — — Phần 2 Zhang (2004) 15.7 — 7.3 — Toàn bộ Park (2005) 9.3 — 6.0 — Toàn bộ Gom nhóm của nhóm tác giả Liu, Jiang, Kot (2007) 4.2 2.9 3.1 2.9 Toàn bộ Tuy nhiên, một số hạn chế trong phương pháp này đó là việc rút trích các vector đặc trưng chưa hiệu quả trong trường hợp vân tay chất lượng thấp chẳng hạn vấn đề phát hiện phương bất biến, điểm lõi để rút trích vector hướng và việc tính khoảng cách đường vân cần chính xác hơn. Ngoài ra còn có phương pháp đề xuất kết hợp việc phân lớp liên tục với phân lớp rõ, nhưng các phương pháp này vẫn chưa hiệu quả. Do đó, các nghiên cứu nhằm cải tiến việc tìm kiếm được hiệu quả hơn đối với cơ sở dữ liệu lớn, phần lớn các ảnh vân tay chất lượng thấp là vẫn hấp dẫn đối với các nhà nghiên cứu. 1.7 Đóng góp của luận văn Luận văn trình bày các công đoạn cần thiết để giải quyết bài toán nhận dạng vân tay. Đối với từng công đoạn xử lý, các phương pháp tiến bộ đã được nghiên cứu và chọn để giải quyết. Một số công đoạn, các phương pháp tiến bộ hiện tại vẫn tồn tại - 12 - nhược điểm. Một số phương pháp mới đã được đề xuất trong luận văn để khắc phục các nhược điểm này. Để tiền lọc vân tay hiệu quả, phương pháp gom nhóm vân tay nhiều mức được sử dụng. Để tăng độ chính xác của tiền lọc vân tay, nhiều đặc trưng vân tay được sử dụng như vector khoảng cách đường vân, vector hướng đường vân và vector mật độ minutiae. Điểm tham chiếu đóng vai trò quan trọng trong việc rút trích vector đặc trưng hướng và mật độ minutiae. Nhằm tăng cường độ chính xác của việc rút trích các vector này, một thuật toán phát hiện điểm tham chiếu hiệu quả đã được đề xuất trong luận văn. Hơn nữa, một thuật toán lai để tính toán đường vân chính xác cũng được để xuất. Để giải quyết bài toán ảnh vân tay chất lượng thấp, luận văn đã đề xuất giải pháp nâng cao chất lượng ảnh hiệu quả dựa vào hàm Gabor và cách tính tần số đường vân chính xác. Thực nghiệm được tiến hành trên cơ sở dữ liệu chuẩn FVC2004 DB2 tập A, và cơ sở dữ liệu 10.000 ảnh vân tay chất lượng thấp của người dân Việt Nam, do Bộ công an cung cấp cho thấy các phương pháp tiến bộ được chọn và đề xuất cho bài toán nhận dạng vân tay trên cơ sở dữ liệu lớn, phần lớn ảnh chất lượng thấp là hợp lý. Tóm lại, chương này đã trình bày các vấn đề cơ bản liên quan đến bài toán nhận dạng vân tay. Những thánh thức đặt ra cho bài toán nhận dạng vân tay trên cơ sở dữ liệu lớn phần lớn ảnh chất lượng thấp được nêu ra. Các hướng nghiên cứu liên quan và đóng góp của đề tài cũng được giới thiệu rõ. Phần tiếp theo trình bày chi tiết các công đoạn tiền xử lý vân tay, các phương pháp tương ứng đã được sử dụng phổ biến cho từng công đoạn.