Tài liệu Nhận dạng vân tay sử dụng mạng nơron nhân tạo

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHÙNG THẾ HUÂN NHẬN DẠNG VÂN TAY SỬ DỤNG MẠNG NƠRON NHÂN TẠO LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Mẫu 3. Trang phụ bìa luận văn (title page) Thái Nguyên - 2012 1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHÙNG THẾ HUÂN NHẬN DẠNG VÂN TAY SỬ DỤNG MẠNG NƠRON NHÂN TẠO Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. Phạm Việt Bình Mẫu 3. Trang phụ bìa luận văn (title page) Thái Nguyên - 2012 2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i LỜI CẢM ƠN Trƣớc hết, tôi xin bày tỏ lòng kính trọng và lòng biết ơn sâu sắc tới thầy giáo NGƢT.TS. Phạm Việt Bình, ngƣời đã tận tình hƣớng dẫn, chỉ bảo và cung cấp những tài liệu rất hữu ích để tôi có thể hoàn thành luận văn. Xin trân trọng cảm ơn Ban lãnh đạo Trƣờng Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã tạo điều kiện giúp đỡ tôi về mọi mặt trong suốt quá trình học tập và thực hiện luận văn. Tôi xin bày tỏ lòng biết ơn tới các thầy, cô giáo Viện Công nghệ Thông tin và trƣờng Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã truyền đạt kiến thức, phƣơng pháp nghiên cứu khoa học trong suốt những năm học vừa qua. Xin chân thành cảm ơn các anh chị em học viên lớp cao học K9A và các bạn đồng nghiệp đã động viên, khích lệ tôi trong quá trình học tập, nghiên cứu. Tôi xin bày tỏ lòng biết ơn sâu sắc đến gia đình, ngƣời thân, những ngƣời luôn động viên, khuyến khích và giúp đỡ về mọi mặt để tôi có thể hoàn thành công việc nghiên cứu. Thái Nguyên, tháng 08 năm 2012 Tác giả luận văn Phùng Thế Huân 3Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii LỜI CAM ĐOAN Tôi xin cam đoan: Những nội dung trong luận văn này là do tôi thực hiện dƣới sự hƣớng dẫn trực tiếp của thầy giáo hƣớng dẫn NGƢT.TS. Phạm Việt Bình. Mọi tham khảo dùng trong luận văn đều đƣợc trích dẫn rõ ràng tác giả, tên công trình, thời gian, địa điểm công bố. Tôi xin chịu trách nhiệm với lời cam đoan của mình. Thái Nguyên, tháng 08 năm 2012 Tác giả luận văn Phùng Thế Huân 4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii DANH MỤC CÁC HÌNH VẼ TRONG LUẬN VĂN Hình Tên hình Trang 1.1 Vân lồi và vân lõm của một ngón tay 3 1.2 Các điểm singularity core và delta 4 1.3 Một số loại core thƣờng gặp 4 1.4 Các điểm điểm kết thúc điểm rẽ nhánh 5 1.5 Sơ đồ các bƣớc nhận dạng vân tay 5 1.6 a) Ƣớc lƣợng hƣớng ảnh chƣa làm mƣợt; b) Ƣớc lƣợng hƣớng ảnh đã làm mƣợt 8 1.7 Cách tính chỉ số poincare tại điểm (i, j ) với N p  8 9 1.8 Các bƣớc rút trích đặc trƣng từ ảnh đã đƣợc nhị phân hóa 10 1.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 11 1.10 Các đƣờng vân và các rãnh trên bề mặt vân tay 11 1.11 Điểm cực đại tƣơng ứng với 12 1.12 Dịch chuyển một đoạn μ theo đƣờng vân 13 1.13 Thiết diện của đƣờng vân 14 1.14 Minh họa kết quả chuẩn hóa ảnh 16 1.15 Kết quả lọc ảnh vân tay bằng hàm gabor 17 1.16 Minh họa việc bắt cặp của các mảnh vụn 23 1.17 Các đặc tính của cấu trúc cục bộ 24 1.18 Sơ đồ nhận dạng vân tay dùng kỹ thuật FingerCode 27 2.1 Cấu trúc cơ bản của nơron sinh học 28 2.2 Nơron nhân tạo 30 2.3 Mô hình toán học mạng nơron nhân tạo 33 2.4 Nơron 1 đầu vào với hàm hoạt hoá là hàm hardlimit 35 2.5 Một số dạng hàm hoạt hóa trong mạng nơron nhân tạo 35 2.6 Liên kết bên trên lớp cạnh tranh 37 2.7 Kiến trúc mạng Kohonen 38 5Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv Hình Tên hình Trang 2.8 Học có giám sát 39 2.9 Học không có giám sát 40 2.10 Học tăng cƣờng 40 2.11 Kiến trúc mạng Perceptron 43 2.12 Biên quyết định trong không gian mẫu 45 2.13 Không gian mẫu khả tách tuyến tính 46 2.14 Không gian mẫu không khả tách tuyến tính 47 2.15 Phân tách không gian mẫu với mạng Perceptron 2 nơron lớp ra 48 2.16 Mạng Perceptron đa lớp (MLP) 48 2.17 Mạng MLP giải quyết bài toán XOR 49 2.18 Không gian mẫu 54 2.19 Phân lớp mẫu với mạng MLP 3 lớp 54 2.20 Quan hệ lân cận trong lớp Kohonen 55 2.21 Mã hoá vectơ đầu vào với mạng SOFM 57 3.1 Sơ đồ đối sánh vân tay bằng mạng nơron 59 3.2 Mô hình mạng Perceptron một lớp 61 3.3 Mô hình mạng Perceptron 2 lớp (1 lớp ẩn và 1 đầu ra) 63 3.4 Giao diện chính của chƣơng trình 65 3.5 Huấn luyện mạng nơron 66 6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v MỤC LỤC MỞ ĐẦU .................................................................................................................... 1 CHƢƠNG 1: TỔNG QUAN VỀ NHẬN DẠNG VÂN TAY.................................... 3 1.1 Các điểm đặc trƣng trên ảnh vân tay .................................................................... 3 1.2 Sơ đồ các bƣớc xử lý trong quá trình nhận dạng .................................................. 5 1.2.1 Quá trình xử lý ảnh (image processing) .................................................... 6 1.2.2 Quá trình đối sánh vân tay (matching) ...................................................... 6 1.3 Trích các điểm đặc trƣng ...................................................................................... 7 1.3.1 Trích các điểm Singularity ........................................................................ 7 1.3.2 Trích các điểm Minutiae ............................................................................ 9 1.3.2.1 Rút trích các đặc trƣng từ ảnh đã đƣợc nhị phân hóa ....................... 10 1.3.2.2 Rút trích các đặc trƣng trực tiếp từ ảnh xám ................................... 11 1.4 Làm nổi ảnh vân tay ........................................................................................... 14 1.5 Một số thuật toán đối sánh vân tay……………………………………………148 1.5.1 Đối sánh dựa vào độ tƣơng quan ............................................................. 19 1.5.2 Đối sánh dựa vào đặc trƣng mảnh vụn .................................................... 20 1.5.2.1 Hƣớng tiếp cận ................................................................................. 20 1.5.2.2 Đối sánh đặc trƣng cục bộ và toàn cục ............................................. 23 1.5.3 Đối sánh dựa vào đặc tính vân ................................................................ 25 CHƢƠNG 2: MẠNG NƠRON VỚI BÀI TOÁN NHẬN DẠNG ẢNH ................. 28 2.1 Các khái niệm chung về mạng nơron ................................................................. 28 2.1.1 Mạng nơron sinh học ............................................................................... 28 2.1.2 Mạng nơron nhân tạo ............................................................................... 30 2.1.2.1 Nơron nhân tạo ................................................................................. 30 7Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi 2.1.2.2 Mạng nơron nhân tạo ........................................................................ 31 2.1.2.3 Các ứng dụng của mạng nơron ......................................................... 31 2.2 Mô hình toán học và kiến trúc mạng nơron........................................................ 32 2.2.1 Mô hình toán học của mạng nơron .......................................................... 32 2.2.1.1 Mô hình toán học của một nơron nhân tạo ....................................... 32 2.2.1.2 Cấu trúc mạng nhân tạo .................................................................... 34 2.2.1.3 Hàm truyền (Hàm hoạt hoá) ............................................................. 34 2.2.2 Kiến trúc mạng ........................................................................................ 36 2.3 Huấn luyện mạng ................................................................................................ 38 2.3.1 Hoạt động của mạng ................................................................................ 38 2.3.2 Huấn luyện mạng ..................................................................................... 39 2.3.2.1 Học có giám sát ................................................................................ 39 2.3.2.2 Học không có giám sát ..................................................................... 40 2.3.2.3 Học tăng cƣờng................................................................................. 40 2.3.3 Một số luật học ........................................................................................ 41 2.4 Mạng Perceptron................................................................................................. 43 2.4.1 Kiến trúc mạng ........................................................................................ 43 2.4.2 Huấn luyện mạng ..................................................................................... 44 2.4.3 Khả năng ứng dụng cho nhận dạng ảnh .................................................. 47 2.5 Mạng perceptron đa lớp ...................................................................................... 48 2.5.1 Kiến trúc mạng ........................................................................................ 48 2.5.2 Huấn luyện mạng ..................................................................................... 49 2.5.3 Khả năng ứng dụng cho nhận dạng ảnh .................................................. 53 2.6 Mạng Kohonen ................................................................................................... 55 8Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii 2.6.1 Kiến trúc mạng ........................................................................................ 55 2.6.2 Huấn luyện mạng ..................................................................................... 56 2.6.3 Khả năng ứng dụng cho nhận dạng ảnh ................................................. 57 CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM................................................... 59 3.1 Bài toán nhận dạng vân tay bằng mạng nơron nhân tạo..................................... 59 3.2 Phƣơng pháp đề nghị .......................................................................................... 59 3.2.1 Lựa chọn mạng sử dụng cho bài toán ...................................................... 59 3.2.2 Xây dựng tập mẫu ngõ vào ...................................................................... 60 3.2.3 Số lớp sử dụng ......................................................................................... 61 3.3 Thuật toán huấn luyện mạng nơron .................................................................... 61 3.3.1 Mạng Perceptron một lớp ........................................................................ 61 3.3.2 Mạng Perceptron 2 lớp ............................................................................ 62 3.4 Chƣơng trình nhận dạng vân tay ........................................................................ 64 3.4.1 Chức năng của chƣơng trình.................................................................... 64 3.4.2 Sử dụng chƣơng trình .............................................................................. 66 3.4.3 Thực nghiệm ............................................................................................ 67 3.4.4 Đánh giá kết quả ...................................................................................... 72 KẾT LUẬN .............................................................................................................. 73 TÀI LIỆU THAM KHẢO ........................................................................................ 74 9Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU Ngày nay, công nghệ sinh trắc học đƣợc ứng dụng rộng rãi trong đời sống. Trong đó công nghệ nhận dạng vân tay là đƣợc ứng dụng nhiều nhất. Ngƣời ta nhận thấy các đặc trƣng vân tay không thể dễ dàng bị thay thế, chia sẻ, hay giả mạo, … Ngoài ra dấu vân tay của con ngƣời không ai giống ai, kể cả là sinh đôi cùng trứng xác suất trùng lặp dấu vân tay giữa ngƣời này với ngƣời kia gần nhƣ là 0%, và không đổi trong suốt cuộc đời. Do vậy trong việc nhận dạng một ngƣời, công nghệ này đƣợc xem là đáng tin cậy hơn so với các phƣơng pháp truyền thống nhƣ dùng mật khẩu, mã thẻ, ... Con ngƣời đã ứng dụng công nghệ nhận dạng vân tay từ rất lâu. Tuy nhiên, trong khoảng một thời gian dài con ngƣời chỉ thực hiện việc đối sánh giữa hai dấu vân tay bằng kỹ thuật truyền thống mang nặng tính thủ công. Các kết quả của lĩnh vực này gần nhƣ không đƣợc ứng dụng trong các lĩnh vực dân sự thông thƣờng của đời sống mà chủ yếu đƣợc sử dụng trong lĩnh vực hình sự. Với sự phát triển ngày càng nhanh chóng của ngành công nghệ thì việc sử dụng dấu vân tay để nhận dạng đƣợc áp dụng rộng rãi trong đời sống. Công nghệ này không những đƣợc ứng dụng trong lĩnh vực hình sự mà còn đƣợc ứng dụng đa dạng trong lĩnh vực dân sự, thƣơng mại,… cụ thể là: Việc xác nhận nhân thân của cá nhân khi truy cập mạng, hồ sơ cá nhân, khóa phòng trộm, thẻ ngân hàng, hệ thống chấm công, hệ thống bảo mật,… Với nguyện vọng muốn tìm hiểu về lý thuyết nhận dạng vân tay cũng nhƣ những lĩnh vực ứng dụng thực tế, em đã chọn đề tài “Nhận dạng vân tay sử dụng mạng nơron nhân tạo” làm Luận văn tốt nghiệp của mình. Mục đích của đề tài là tìm hiểu cơ sở các phƣơng pháp nhận dạng vân tay, cách giải quyết bài toán nhận dạng vân tay sử dụng mạng nơron nhân tạo và xây dựng chƣơng trình ứng dụng. Luận văn gồm 3 chƣơng không kể phần mở đầu và phần kết luận với các nội dung chính sau: 10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 Chƣơng 1: Luận văn trình bày tổng quan về nhận dạng vân tay bao gồm các đặc trƣng của vân tay, giới thiệu các bƣớc xử lý trong quá trình nhận dạng. Ngoài ra luận văn cũng trình bày một số thuật toán rút trích các đặc trƣng của ảnh vân tay từ ảnh nhị phân và ảnh đa cấp xám. Đặc biệt là nghiên cứu một số thuật toán đối sánh ảnh vân tay. Chƣơng 2: Luận văn trình bày những kiến thức cơ bản về mạng nơron nhân tạo, các phƣơng pháp huấn luyện mạng,…Ngoài ra luận văn cũng trình bày mô hình kiến trúc của một số mạng nơron nhân tạo. Đặc biệt trình bày khả năng áp dụng cho bài toán nhận dạng ảnh. Chƣơng 3: Luận văn đƣa ra bài toán nhận dạng vân tay sử dụng mạng nơron nhân tạo, đề nghị phƣơng pháp và thuật toán huấn luyện mạng. Cuối cùng là một số hình ảnh, cách thức sử dụng và đánh giá chƣơng trình nhận dạng vân tay. Trong luận văn cũng đƣa ra các thực nghiệm tính toán kiểm tra độ chính xác của các thuật toán dựa trên các phần mềm chạy trên máy tính. 11Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 CHƢƠNG 1 TỔNG QUAN VỀ 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 các bước xử lý tiêu biểu trong nhận dạng vân tay. Ngoài ra chương này cũng đề cập đến một số thuật toán rút trich đặc trưng, đối sánh ảnh vân tay. 1.1 Các điểm đặc trƣng trên ảnh 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 1.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ũ. Hình 1.1 Vân lồi và vân lõm của một ngón tay 12Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Trên các ảnh vân tay có các điểm đặc trƣng (là những điểm đặc biệt mà vị trí của nó không trùng lặp trên các vân tay khác nhau) đƣợc phân thành hai loại: singularity và minutiae.  Singularity (Điểm kì dị): Trên vân tay có những vùng có cấu trúc khác thƣờng so với những vùng bình thƣờng khác (thƣờng có cấu trúc song song), những vùng nhƣ vậy goi là singularity. Có hai loại singularity là core và delta. Hình 1.2 Các điểm singularity core và delta Core thƣờng có một số dạng nhƣ sau: Hình 1.3 Một số loại core thƣờng gặp  Minutiae (Điểm vụn vặt): Vân lồi và vân lõm thƣờng nằm song song với nhau nhƣng khi dò theo từng đƣờng vân ta sẽ thấy chúng tạo thành những 13Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 điểm kết thúc (Ridge Ending) hoặc rẽ nhánh (Bifurcation), những điểm này đƣợc gọi chung là minutiae. Hình 1.4 Các điểm điểm kết thúc điểm rẽ nhánh 1.2 Sơ đồ các bƣớc xử lý trong quá trình nhận dạng Hình 1.5 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). Hình 1.5 Sơ đồ các bƣớc nhận dạng vân tay 14Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 1.2.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; do vậy, bƣớc này là một trong các bƣớc quan 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. 1.2.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ƣng của vân tay (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 15Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 tiếp tuyến của đƣờng vân tại đặc trƣng và trục ngang) để 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. 1.3. Trích các điểm đặc trƣng 1.3.1 Trích các điểm Singularity 1.3.1.1 Trƣờng định hƣớng Ảnh vân tay là ảnh định hƣớng, các đƣờng vân là các đƣờng cong theo các hƣớng xác định. Góc hợp bởi phƣơng của một điểm trên đƣờng vân với phƣơng ngang đƣợc gọi là hƣớng của điểm đó. Tập hợp các hƣớng của các điểm trên ảnh vân tay gọi là trƣờng định hƣớng của ảnh vân tay đó. Phƣơng pháp xác định trƣờng định hƣớng nhƣ sau:  Chia ảnh vân tay thành các khối nhỏ hơn kích thƣớc w  w  Tính gradient theo hai hƣớng x , y là Gx , G y tại mỗi điểm (pixel) trong khối  Khi đó hƣớng của điểm chính giữa của khối đƣợc xác định theo công thức:  w w    2Gx (i, j )Gy (i, j )  1    tan 1  wi 1 wj 1 2   2 2   Gx (i, j )  Gy (i, j )   i 1 j 1  16Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (1.1) http://www.lrc-tnu.edu.vn 8 Hình 1.6 a) Ƣớc lƣợng hƣớng ảnh chƣa làm mƣợt; b) Ƣớc lƣợng hƣớng ảnh đã làm mƣợt 1.3.1.2 Xác định các điểm singularity bằng chỉ số Poincare (Poincare index) Giả sử (i, j ) là một điểm bất kỳ trên ảnh vân tay, C là một đƣờng cong khép kín xung quanh (i, j ) thì chỉ số Poincare tại (i, j ) là tổng đại số các độ sai lệch hƣớng của các điểm liền kề nhau trên đƣờng cong C . Poincare(i, j )  N p 1  ( k ) (1.2) k 0 | d (k ) |  / 2  d (k ),  (k )   d (k )   , d (k )   / 2 d (k )    d (k )    xk 1 , yk 1     xk , yk  Trong đó: N p là tổng số điểm trên đƣờng cong “số” C  ( x, y) là hƣớng tại điểm ( x, y) 17Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Dựa vào chỉ số Poincare ta có thể xác định các điểm singularity nhƣ sau: Hình 1.7 Cách tính chỉ số poincare tại điểm (i, j) với N p  8 1.3.2 Trích các điểm Minutiae 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, rút trích đặc trƣng một cách đú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. 18Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 1.3.2.1 Rút trích các đặc trƣng từ ảnh đã đƣợc nhị phân hóa Hình 1.8 Các bƣớc rút trích đặc trƣng từ ảnh đã đƣợc nhị phân hóa Hình 1.8 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 (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ó. Phƣơng pháp rút trích đặc trƣng đƣợc mô tả nhƣ sau: Giả sử ( x, y) là một điểm trên đƣờng vân đã đƣợc làm mỏng và N 0 , N1 , …, N 7 là 8 điểm xung quanh nó thì:  7 ( x, y ) là một điểm kết thúc nếu  Ni  1; i 0  7 ( x, y ) là một điểm rẽ nhánh nếu  Ni  2. i 0 19Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Hình 1.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 1.3.2.2 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). 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.  Thuật toán 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 2.12. Hình 1.10 Các đƣờng vân (ridge) và các rãnh (ravine) trên bề mặt vân tay 20Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn