Tài liệu đối sánh vân tay dựa trên thuật toán mcc minutiae cylinder code

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN TUẤN HẢI ĐỐI SÁNH VÂN TAY DỰA TRÊN THUẬT TOÁN MCC MINUTIAE CYLINDER-CODE LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội, 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN TUẤN HẢI ĐỐI SÁNH VÂN TAY DỰA TRÊN THUẬT TOÁN MCC MINUTIAE CYLINDER-CODE Ngành: Chuyên ngành: Mã số: Công nghệ thông tin Hệ thống thông tin 60 48 01 04 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. NGUYỄN NGỌC HOÁ Hà Nội, 2013 1 LỜI CAM ĐOAN Để hoàn thành luận văn này thực sự tôi không thể chỉ dựa vào kiến thức hạn hẹp của bản thân, vì vậy tôi đã tham khảo tài liệu, các công trình nghiên cứu của những ngƣời đi trƣớc. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp. Thực sự tôi rất cảm ơn các tác giả đi trƣớc đã cung cấp cho tôi những kiến thức để tác giả hoàn thành luận văn tốt nghiệp của mình. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, tháng 11 năm 2013 Ngƣời cam đoan Nguyễn Tuấn Hải 2 LỜI CẢM ƠN Để hoàn thành luận văn tốt nghiệp là cả một quá trình đầy khó khăn và thử thách trong học tập và nghiên cứu tại trƣờng Đại học Công nghệ. Và để có đƣợc những thành quả nhƣ ngày hôm nay, ngoài những nỗ lực của bản thân, không thể không nhắc tới là sự động viên, giúp đỡ của các Thầy, Cô giáo, bạn bè, đồng nghiệp và ngƣời thân trong gia đình. Tôi xin chân thành cảm ơn TS. Nguyễn Ngọc Hoá là cán bộ giảng viên của trƣờng Đại học Công Nghệ đã tận tình giúp đỡ tôi cả về chuyên môn, nghiên cứu và định hƣớng phát triển trong suốt quá trình làm luận văn. Tôi xin gửi lời cảm ơn tới các Thầy, Cô giáo của Khoa Hệ Thống Thông Tin đã tận tình giảng dạy và truyền đạt cho tôi những kiến thức quý báu trong những năm học vừa qua. Tôi đã đƣợc tiếp cận một môi trƣờng học thuật cao, hiểu đƣợc sự vất vả cũng nhƣ thành quả đạt đƣợc khi tham gia nghiên cứu khoa học. Sau cùng, tôi xin chân thành cảm ơn gia đình, những ngƣời thân và bạn bè đã giúp đỡ, động viên tôi trong suốt thời gian học tập và làm luận văn tốt nghiệp này. Tôi mong rằng với sự cố gắng học tập nâng cao kiến thức, sau này có thể lĩnh hội nhiều công nghệ, tạo ra nhiều sản phẩm có giá trị sử dụng cao, giúp ích đƣợc trong nhiều lĩnh vực của cuộc sống. Hà Nội, tháng 11 năm 2013 Học viên thực hiện Nguyễn Tuấn Hải 3 TÓM TẮT NỘI DUNG Nhận dạng vân tay đã đƣợc nghiên cứu nhiều năm và đạt đƣợc nhiều tiến triển, rất nhiều nỗ lực vẫn cần thiết để nâng cao hiệu năng của các hệ thống nhận dạng vân tay. Trong hệ thống nhận dạng vân tay, thuật toán đối sánh đóng vai trò quan trọng, quyết định trực tiếp đến chất lƣợng cũng nhƣ hiệu năng của việc nhận dạng. Các thuật toán đối sánh thƣờng sử dụng thêm biểu diễn trung gian đƣợc trích xuất từ bƣớc trích chọn thuộc tính để trả lại độ tƣơng đồng hoặc một quyết định nhị phân khi so sánh hai vân tay. Luận văn tập trung tìm hiểu chi tiết một số thuật toán đối sánh vân tay tiêu biểu, đi sâu vào thuật toán đối sánh cho kết quả cao hiện nay dựa trên biểu diễn MCC (Minutia Cylinder-Code) của Cappelli và cộng sự năm 2010. Từ đó luận văn tiến hành thử nghiệm thuật toán trên bộ dữ liệu vân tay FVC 2002 DB và đánh giá kết quả thu đƣợc khẳng định đƣợc chất lƣợng so khớp vân tay dựa trên biểu diễn MCC. 4 MỤC LỤC LỜI CAM ĐOAN ......................................................................................... 1 LỜI CẢM ƠN ............................................................................................... 2 TÓM TẮT NỘI DUNG ................................................................................ 3 MỤC LỤC ..................................................................................................... 4 DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ................................... 6 DANH MỤC CÁC HÌNH ẢNH ................................................................... 7 DANH MỤC CÁC BẢNG BIỂU ................................................................. 9 MỞ ĐẦU ..................................................................................................... 10 Chƣơng 1. TỔNG QUAN VỀ NHẬN DẠNG VÂN TAY......................... 12 1.1. Giới thiệu ........................................................................................... 12 1.2. Mô hình hệ thống nhận dạng vân tay ................................................ 13 1.3. Đánh giá kết quả của hệ thống nhận dạng......................................... 15 1.4. Quy trình chi tiết nhận dạng vân tay ................................................. 17 1.4.1. Trích chọn thuộc tính từ vân tay .................................................. 17 1.4.2. Quá trình lọc vân tay trƣớc khi đối sánh ..................................... 18 1.4.3. Đối sánh vân tay .......................................................................... 20 1.4.4. Tính toán độ tƣơng đồng ............................................................. 23 1.5. Kết luận.............................................................................................. 23 Chƣơng 2. MỘT SỐ THUẬT TOÁN ĐỐI SÁNH VÂN TAY .................. 25 2.1. Giới thiệu ........................................................................................... 25 2.2. Các phƣơng pháp đối sánh vân tay.................................................... 26 2.2.1. Đối sánh toàn cục......................................................................... 26 2.2.2. Đối sánh cục bộ ........................................................................... 27 2.3. Hạn chế của một số biểu diễn truyền thống ...................................... 31 2.4. Biểu diễn dựa trên MCC.................................................................... 32 2.4.1. Mô tả biểu diễn MCC .................................................................. 32 2.4.2. Tính độ tƣơng đồng giữa các hình trụ ......................................... 37 2.5. Ứng dụng của biểu diễn dựa trên Bit ................................................ 37 2.6. Kết luận.............................................................................................. 38 Chƣơng 3. THỬ NGHIỆM THUẬT TOÁN ĐỐI SÁNH VÂN TAY DỰA TRÊN BIỂU DIỄN MCC.................................................................................... 39 3.1. Mục đích thử nghiệm......................................................................... 39 3.2. Quy trình thử nghiệm ........................................................................ 39 5 3.3. Môi trƣờng thử nghiệm ..................................................................... 40 3.4. Đánh giá kết quả ................................................................................ 42 3.5. Kết luận.............................................................................................. 43 KẾT LUẬN CHUNG .................................................................................. 44 TÀI LIỆU THAM KHẢO ........................................................................... 45 6 DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT Viết tắt MCC EER FMR FNMR PIN FVC Viết đầy đủ Minutia Cylinder Code Equal Error Rate False Match Rate False Not Match Rate Personal Identity Number Fingerprint Verification Competition 7 DANH MỤC CÁC HÌNH ẢNH Hình 1.1. Một số ứng dụng của sinh trắc học............................................. 12 Hình 1.2. So sánh thị phần của sinh trắc học ............................................. 13 Hình 1.3. Các tiến trình của một hệ thống nhận dạng vân tay ................... 15 Hình 1.4. Các loại thông số dùng trong đánh giá hệ thống sinh trắc học .. 16 Hình 1.5. Lựa chọn tỷ lệ FMR và FNMR giữa các ứng dụng ................... 17 Hình 1.6. Một số đặc trƣng của vân tay ..................................................... 18 Hình 1.7. Minh họa kết quả của quá trình trích chọn thuộc tính................ 18 Hình 1.8. Phân lớp vân tay ......................................................................... 19 Hình 1.9. Thuật toán Pointcare sử dụng trong phát hiện điểm tâm ........... 19 Hình 1.10. Đánh chỉ mục vân tay dựa trên các tam giác nối các điểm trạc20 Hình 1.11. Một số thu nhận khác nhau của cùng một vân tay ................... 21 Hình 1.12. Một số vân tay khác nhau có độ tƣơng đồng cao ..................... 22 Hình 1.13. So sánh mức các cách tiếp cận trong đối sánh vân tay [1] ....... 23 Hình 2.1. Các loại điểm trạc và thông tin về điểm trạc .............................. 25 Hình 2.2. Đối sánh các điểm trạc giữa hai vân tay..................................... 25 Hình 2.3. Một số cấu trúc cục bộ sử dụng để mô tả điểm trạc ................... 27 Hình 2.4. Biểu diễn cục bộ sử dụng K-plet ................................................ 28 Hình 2.5. Biểu diễn vân tay sử dụng FingerCode ...................................... 28 Hình 2.6. Bƣớc gia cố liên quan đến việc căn chỉnh biến đổi xoay và dịch chuyển ................................................................................................................. 29 Hình 2.7. Một cặp điểm đối sánh sai có giá trị tƣơng đồng lớn nhất ......... 30 Hình 2.8. Kết quả đối sánh tốt hơn khi bổ xung bƣớc kiểm tra sau khi căn chỉnh .................................................................................................................... 30 Hình 2.9. Cấu trúc không phù hợp do phát hiện điểm trạc thiếu hoặc sai . 31 Hình 2.10. Cấu trúc cục bộ không phù hợp do vấn đề biên ....................... 32 Hình 2.11. Biểu diễn hình trụ MCC cho điểm trạc .................................... 33 Hình 2.12. Chi tiết tính toán cho hình trụ................................................... 33 Hình 2.13. Chi tiết từng tầng trong hình trụ ............................................... 33 Hình 2.14. Tập các điểm trạc đóng góp vào pim, j ......................................... 34 Hình 2.15. Đóng góp theo khoảng cách của mt vào pim, j ............................ 34 Hình 2.16. Đóng góp của mt theo hƣớng tới d k ....................................... 35 Hình 2.17. Hàm sigmoid ............................................................................ 36 8 Hình 2.18. Minh họa các ô của hình trụ thể hiện cho điểm trạc m, ô sáng hơn chỉ giá trị cao hơn ......................................................................................... 36 Hình 2.19. Minh họa ba hình trụ biểu diễn cho ba điểm trạc của vân tay . 37 Hình 2.20. Độ tƣơng đồng giữa các biểu diễn hình trụ .............................. 37 Hình 2.21. Hàm chuyển về giá trị bit ......................................................... 38 Hình 2.22. Đối sánh trên thẻ Match on card sử dụng biểu diễn Bit của MCC .................................................................................................................... 38 Hình 3.1. Các bƣớc tiến hành trong mô hình đánh giá các thuật toán đối sánh ...................................................................................................................... 39 Hình 3.2. Một số ảnh vân tay từ CSDL vân tay FVC2002 ........................ 40 Hình 3.3. Vân tay đƣợc lọc nhiễu và nổi vân sử dụng công cụ VeriFinger41 Hình 3.4. Tập các điểm trạc đƣợc trích xuất từ vân tay sử dụng công cụ VeriFinger ........................................................................................................... 42 Hình 3.5. Độ đo sử dụng trong đánh giá thuật toán ................................... 42 9 DANH MỤC CÁC BẢNG BIỂU Bảng 3.1. So sánh độ chính xác và tốc độ xử lý của các biểu diễn ............ 43 10 MỞ ĐẦU Động lực nghiên cứu Nhận dạng vân tay đƣợc sử dụng rộng rãi trong các ứng dụng pháp lý và dân sự bởi tính duy nhất và ổn định theo thời gian. So sánh với các đặc điểm sinh trắc học khác, sinh trắc học dựa trên vân tay là kỹ thuật đƣợc minh chứng nhiều nhất và có thị phần lớn nhất. Mặc dù nhận dạng vân tay đã đƣợc nghiên cứu nhiều năm và đạt đƣợc nhiều tiến triển, rất nhiều nỗ lực vẫn cần thiết để nâng cao hiệu năng của các hệ thống nhận dạng vân tay. Trong bài toán nhận dạng vân tay, bài toán đối sánh vân tay (fingerprint matching) có vai trò quan trọng liên quan đến tốc độ nhận dạng và độ chính xác của quá trình nhận dạng. Đây cũng là một trong những hƣớng nghiên cứu chủ yếu hiện nay về nhận dạng vân tay. Mục tiêu và nội dung chính Với định hƣớng nêu trên, luận văn có mục tiêu tìm hiểu, nghiên cứu một số thuật toán đối sánh vân tay, trong đó tập trung chính vào thuật toán đối sánh vân tay cho kết quả chính xác cao hiện nay do Cappelli và cộng sự đề xuất vào năm vào năm 2010, dựa trên biểu diễn MCC (Minutia Cylinder-Code) và tiến hành thử nghiệm đánh giá. Mục tiêu này đƣợc cụ thể theo những nội dung chính sau: - Tìm hiểu tổng quan về nhận dạng vân tay, vai trò của đối sánh vân tay trong nhận dạng vân tay. - Khảo sát chi tiết một số thuật toán đối sánh điển hình hiện nay nhƣ đối sánh toàn cục, đối sánh cục bộ, đối sánh dựa trên điểm trạc,… Biểu diễn MCC sẽ đƣợc chú trọng phân tích để thực nghiệm. - Thử nghiệm thuật toán đối sánh vân tay dựa trên biểu diễn MCC và đánh giá kết quả thu đƣợc. Tổ chức luận văn Dựa trên những nội dung đã đạt đƣợc, luận văn đƣợc tổ chức gồm các phần sau: Mở đầu: Đặt ra vấn đề, mục tiêu, nội dung nghiên cứu của luận văn. Chương 1: Giới thiệu tổng quan về bài toán nhận dạng vân tay (fingerprint recognition). Các bƣớc cũng nhƣ các tiến trình đƣợc thực thi trong bài toán nhận dạng vân tay. Chương 2: Trình bày về một số phƣơng pháp đối sánh vân tay và chi tiết về thuật toán đối sánh vân tay cho kết quả tốt hiện nay dựa trên biểu diễn 11 Minutia Cylinder-Code (MCC) đƣợc đề xuất bởi Cappelli và cộng sự vào năm 2010. Chương 3: Trình bày thử nghiệm của thuật toán dựa trên biểu diễn MCC và một số phƣơng pháp khác, và tiến hành đánh giá so sánh các thuật toán trên bộ dữ liệu FVC 2002 DB. Kết luận chung: Tổng kết những kết quả đạt đƣợc và hƣớng nghiên cứu tiếp theo. 12 Chƣơng 1. TỔNG QUAN VỀ NHẬN DẠNG VÂN TAY 1.1. Giới thiệu Nhận dạng vân tay đƣợc ứng dụng phổ biến trong các ứng dụng sinh trắc học nhƣ kiểm soát truy cập, định danh khách hàng thực hiện giao dịch: ví dụ tại ATM, ngân hàng trực tuyến, quản lý thời gian, sự có mặt của nhân viên tại các tổ chức liên quan đến việc tính toán thời gian lao động, tiền lƣơng. Đến các ứng dụng liên quan đến chính phủ nhƣ định danh công dân (hộ chiếu), quản lý xuất nhập cảnh, định danh trong pháp y liên quan đến tội phạm. Hình 1.1 mô tả minh họa một số ứng dụng của sinh trắc học [1, tr.29]. Hình 1.1. Một số ứng dụng của sinh trắc học Trong các ứng dụng sinh trắc học, vân tay đƣợc sử dụng rộng rãi và phổ biến nhất do tính đơn giản và thuận tiện trong lấy mẫu, lƣu trữ và xử lý dữ liệu. Hình 1.2 minh họa sự phổ biến của các ứng dụng sử dụng vân tay trong sinh trắc học so với các đặc trƣng sinh học khác nhƣ: mống mắt, nhận dạng khuôn mặt, tiếng nói,... [1, tr.12] 13 Hình 1.2. So sánh thị phần của sinh trắc học 1.2. Mô hình hệ thống nhận dạng vân tay Quá trình xử lý của một hệ thống nhận dạng vân tay thƣờng trải qua các bƣớc sau: - Lấy mẫu: dựa trên thiết bị điện tử có cảm ứng để thu chụp lại ảnh vân tay, thƣờng có sự đa dạng trong các thiết bị này. - Trích chọn thuộc tính (feature extraction): nhằm mục đích tạo ra tập các thuộc tính có thể đại diện chính xác cho ảnh vân tay thu đƣợc từ bƣớc lấy mẫu. Tập các thuộc tính này sẽ đƣợc sử dụng trong bƣớc đối sánh vân tay. Ảnh vân tay gốc thƣờng đƣợc xử lý bởi bộ phận trích chọn thuộc tính để tạo ra một thể hiện gọn nhẹ nhƣng có tính thể hiện, đại diện cao gọi là tập đặc trƣng. - Tạo bản mẫu (template creation): là quá trình tổ chức một hoặc nhiều tập đặc trƣng vào một bản mẫu và lƣu trữ trên thiết bị lƣu trữ. - Lọc trƣớc khi đối sánh (filtering): là giai đoạn chính đƣợc sử dụng trong một hệ thống định danh khi số lƣợng bản mẫu lƣu trữ là lớn. Vai trò của bƣớc này là giảm số lƣợng bản mẫu cần đối sánh. - Giai đoạn đối sánh (matching): đầu vào là tập đặc trƣng của vân tay cần so sánh và bản mẫu lƣu trữ, bƣớc đối sánh sẽ tính toán độ tƣơng đồng giữa chúng (matching score hay similarity score). Kết quả đối sánh sẽ đƣợc so sánh với ngƣỡng của hệ thống để đƣa ra kết quả cuối cùng. Nếu kết quả đối sánh cao hơn ngƣỡng thì có thể coi hai vân tay là phù hợp, nếu nhỏ hơn sẽ coi hai vân tay là hai vân tay khác nhau. Sử dụng các bƣớc ở trên, hệ thống nhận dạng vân tay có thể bao gồm hai 14 tiến trình chính là: lấy mẫu (enrollment), kiểm tra (verification) hoặc/và định danh (identification). - Lấy mẫu (enrollment): lấy mẫu vân tay ngƣời dùng là quá trình lấy mẫu và lƣu trữ vân tay của cá nhân vào trong hệ thống lƣu trữ sinh trắc học. Trong quá trình lấy mẫu, các đặc tính sinh trắc học đƣợc thu nhận từ thiết bị quét sinh trắc học để tạo ra mẫu. Bƣớc kiểm tra chất lƣợng thƣờng đƣợc tiến hành trong quá trình này để đảm bảo rằng mẫu thu nhận có độ tin cậy để sử dụng trong các bƣớc kế tiếp. Module trích chọn thuộc tính sau đó đƣợc sử dụng để tạo một tập đặc trƣng. Module tạo bản mẫu sẽ sử dụng tập đặc trƣng đó để tạo ra một mẫu lƣu trữ trên thiết bị lƣu trữ. Quá trình lấy mẫu sẽ lƣu trữ mẫu này cũng với các thông tin cá nhân khác của ngƣời sử dụng nhƣ: số định danh, tên, giới tính, nơi trú,...). - Quá trình kiểm tra (verification): quá trình kiểm tra có trách nhiệm xác nhận định danh của chủ thể đã khai báo có chính xác hay không. Trong giai đoạn này, một định danh của chủ thể (nhƣ username hoặc mã PIN [Personal Identification Number]) đƣợc cung cấp để tuyên bố định danh, hệ thống nhận dạng vân tay sẽ thu nhận ảnh vân tay của chủ thể và lấy mẫu, sau đó đƣợc xử lý bởi bƣớc trích chọn thuộc tính để tạo ra tập đặc trƣng. Tập kết quả đặc trƣng sẽ đƣợc đƣa vào bộ đối sánh 1-1 để so sánh với bản mẫu mà chủ thể tuyên bố. Quá trình xác thực đƣa ra quyết định phù hợp hoặc không (match/non-match). - Quá trình định danh (Identification): trong quá trình định danh, chủ thể không trực tiếp khai báo định danh, hệ thống sẽ so sánh tập đặc trƣng đƣợc trích chọn từ ảnh vân tay đƣợc thu nhập với tập các bản mẫu trong hệ thống lƣu trữ. Đây là quá trình so sánh 1-N và kết quả là một định danh đã đƣợc lƣu trữ hoặc thông báo chủ thể chƣa có mẫu, chƣa đăng ký trong hệ thống. Do quá trình định danh với một tập CSDL lớn đòi hỏi việc tính toán lớn, giai đoạn lọc thƣờng đƣợc sử dụng để lọc các mẫu cần so sánh với tập đặc trƣng đầu vào. Hình 1.3 minh họa các tiến trình đƣợc sử dụng trong một hệ thống nhận dạng vân tay [1, tr.4]. 15 Hình 1.3. Các tiến trình của một hệ thống nhận dạng vân tay 1.3. Đánh giá kết quả của hệ thống nhận dạng Một số thông số thƣờng đƣợc sử dụng trong việc đánh giá độ chính xác của một hệ thống nhận dạng đƣợc thể hiện trong Hình 1.4 [1, tr.19]. - False Match Rate (FMR): là tỷ lệ loại lỗi xác định nhầm là cùng của một vân tay khi so sánh hai vân tay khác nhau. Khi thiết lập ngƣỡng t thấp, tỷ lệ lỗi FMR sẽ cao, ngƣợc lại nếu thiết lập ngƣỡng t cao, tỷ lệ lỗi nhận nhầm sẽ giảm xuống. - False Not Match Rate (FNMR): là tỷ lệ lỗi khi xác định hai vân tay của cùng một ngón tay là không phù hợp. Ngƣợc lại với FMR, khi thiết lập ngƣỡng t thấp, tỷ lệ lỗi FNMR sẽ thấp, nếu thiết lập ngƣỡng t cao, tỷ lệ lỗi FNMR sẽ tăng lên. 16 Hình 1.4. Các loại thông số dùng trong đánh giá hệ thống sinh trắc học - Equal-Error Rate (EER): dùng để chỉ tỷ lệ lỗi tại ngƣỡng mà tại đó tỷ lệ lỗi FMR cân bằng với tỷ lệ lỗi FNMR. EER là một chỉ số chính thƣờng đƣợc sử dụng để đánh giá độ chính xác của một hệ thống nhận dạng sinh trắc học. - ZeroFNMR: đƣợc định nghĩa mà tại đó không xảy ra loại lỗi false nonmatches. - ZeroFMR: đƣợc định nghĩa mà tại đó không có lỗi false matches xảy ra. Độ chính xác yêu cầu của một hệ thống sinh trắc học phụ thuộc vào ứng dụng của hệ thống. Trong các ứng dụng pháp lý nhƣ định danh tội phạm, thƣờng quan tâm tới FNMR thấp hơn là tỷ lệ FMR do chúng ta không muốn bỏ xót định danh tội phạm thậm trí nếu cần phải so sánh thủ công số lƣợng lớn vân tay. Trong khi đó với các ứng dụng, ví dụ quản lý truy cập an ninh cao đòi hỏi tỷ lệ FMR thấp. Thi hành hệ thống ở mức FMR rất thấp có thể dẫn đến sự không thuận tiện với ngƣời dùng hợp pháp. Giữa hai điểm cực này, là một vài ứng dụng thƣơng mại mà ở đó cả hai tỷ lệ FNMR và FMR cần đƣợc xem xét. Hình 1.5 minh họa việc lựa chọn giữa tỷ lệ FNMR và FMR trong các loại ứng dụng khác nhau [1, tr.20]. 17 Hình 1.5. Lựa chọn tỷ lệ FMR và FNMR giữa các ứng dụng 1.4. Quy trình chi tiết nhận dạng vân tay 1.4.1. Trích chọn thuộc tính từ vân tay Các thuộc tính đƣợc trích chọn từ vân tay sử dụng trong hệ thống nhận dạng thƣờng có đặc điểm ổn định, bất biến theo thời gian. Hình 1.6 minh họa một số đặc trƣng của vân tay thƣờng đƣợc sử dụng. - Đƣờng giao (crossover): là điểm mà tại đó các đƣờng vân giao với nhau. - Điểm lõi (core): là điểm mà tại đó có sự biến thiên đột ngột về hƣớng của đƣờng vân. - Điểm rẽ nhánh (bifurcation): là điểm mà tại đó, một đƣờng vân đƣợc tách làm hai đƣờng vân khác nhau. - Điểm kết thúc (ridge ending): là điểm mà tại đó, đƣờng vân kết thúc. - Ốc đảo (island): là điểm cô lập so với các đƣờng vân khác. - Tam giác Delta: là nơi hội tụ của các vùng vân có hƣớng khác nhau. Các thuật toán đối sánh vân tay khác nhau có thể lựa chọn các đặc trƣng khác nhau hoặc kết hợp các đặc trƣng này đƣợc sử dụng. Chuẩn ISO/IEC 19794-2 (2005) chỉ sử dụng duy nhất tập đặc trƣng là các điểm kết thúc (ridge ending) và điểm rẽ nhánh (bifurcation) trong việc đối sánh vân tay. Hai điểm đặc trƣng này còn gọi là điểm trạc (minutiae). 18 Hình 1.6. Một số đặc trưng của vân tay Hình 1.7 minh họa quá trình xử lý ảnh để trích chọn ra các thuộc tính từ vân tay. Hình 1.7. Minh họa kết quả của quá trình trích chọn thuộc tính 1.4.2. Quá trình lọc vân tay trƣớc khi đối sánh Đối với các CSDL vân tay lớn, để giảm thời gian tính toán, có thể áp dụng các bƣớc lọc trƣớc đối sánh (pre-matching) để giảm bớt số lƣợng bản mẫu vân tay cần so khớp. Hai kỹ thuật chính thƣờng đƣợc áp dụng là phân lớp vân tay (classification) và đánh chỉ mục (indexing). - Phân lớp vân tay (classification): các vân tay thƣờng đƣợc phân vào một trong sáu lớp vân tay nhƣ minh họa trong Hình 1.8 [1, tr.236]. Một số lớp vân tay đƣợc xác định nhƣ: cung, cung dạng lều, lặp trái, lặp phải, vòng tròn. Việc phân lớp này giúp giảm bớt không gian mẫu vân tay cần so khớp.