Đồ án Xây dựng hệ thống nhận dạng vân tay (Phần 1)

Nội dung text: Đồ án Xây dựng hệ thống nhận dạng vân tay (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP.HCM KHOA ĐÀO TẠO CHẤT LƯỢNG CAO ĐỒ ÁN TỐT NGHIỆP NGÀNH CÔNG NGHỆ KỸ THUẬT ĐIỆN TỬ TRUYỀN THÔNG XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÂN TAY GVHD: Th.S NGUYỄN VĂN PHÚC SVTH: CAO ÐÌNH HUY MSSV: 13141596 S K L 0 0 4 9 7 2 Tp. Hồ Chí Minh, tháng 07/2017
2. TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUÂṬ THÀ NH PHỐ HỒ CHÍ MINH KHOA ĐÀ O TẠO CHẤT LƯƠNG̣ CAO ĐỒ ÁN TỐT NGHIỆP XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÂN TAY SVTH : CAO ĐÌNH HUY MSSV : 13141596 Khoá : 2013 - 2017 Ngành : CNKT ĐIỆN TỬ- TRUYỀN THÔNG GVHD: Th.S NGUYỄN VĂN PHÚC Tp. Hồ Chi ́ Minh, tháng 07 năm 2017
3. Chương 1: GIỚI THIỆU VỀ ĐỒ ÁN 1.1 Giới thiệu nhận dạng vân tay Nhận dạng vân tay là một bộ phận của nhận dạng sinh học. Khoa học nhận dạng vân tay cũng đã hình thành từ khá lâu. Nhưng tới thời gian gần đây, cùng với sự ra đời của máy tính nó mới đạt được nhiều kết quả quan trọng và trở thành một trong những phương pháp sinh trắc có độ tin cậy nhất. Ảnh vân tay dùng để nhận dạng thường bị ảnh hưởng nhiều bởi điều kiện thu thập số liệu (hình ảnh vân tay không trọn vẹn, bị xoay góc, méo hay có nhiều nhiễu ) nên việc so sánh trực tiếp hai mẫu vân tay sẽ rất phức tạp và khó khăn. Do đó vân tay cần lọc nhiễu, sau đó tạo mã từ một số các đặc tính của nó (có thể phân biệt với vân tay khác) nhằm mục đích giải quyết vấn đề xử lý, lưu trữ vân tay với số lượng lớn mà vẫn đảm bảo chính xác. Các kỹ thuật thực nhận dạng vân tay cũng có khá nhiều. Nhìn chung, quá trình này trải qua ba công đoạn chính: thu nhận vân tay, trích chọn đặc tính vân tay, đối sánh vân tay. Bởi vì ngay trong từng công đoạn này lại có nhiều biện pháp khác nhau, tùy vào ngữ cảnh và vùng ứng dụng các khâu này sẽ thực hiện theo cách cụ thể. Công nghệ nhận dạng vân tay ngày nay đã đạt tới độ chính xác rất cao. Tuy vây, các hệ thống nhận dạng AFIS vẫn còn nhiều mặt hạn chế. Chẳng hạn như IAFIS của FBI có cơ sở dữ liệu lớn tới hàng trăm triệu vân tay, thời gian tìm kiếm hàng chục phút cho một mẫu, độ tin cậy cao nhưng đó là một hệ thống đồ sộ gồm nhiều máy tính xử lý song song và giới hạn trong giám định hình sự. Trong ứng dụng dân sư, các hệ thống nhận dạng thường được giới hạn ở một mức độ ít phức tạp hơn: số mẫu không lớn (khoảng vài trăm), cấu trúc hệ thống kiểu nối tiếp, ảnh đầu vào không có quá nhiều nhiễu (nhằm giảm bớt gánh nặng xử lý tính toán), có vậy mới giải quyết được vấn đề chi phí đồng thời vẫn đảm bảo độ tin cây. Đồ án này sẽ thực hiện nhận dạng vân tay bằng ảnh số theo phương pháp nhận dạng là dựa trên cơ sở phát hiện và sử dụng các điểm nút đặc trưng (gọi là minutiae). Đây là phương pháp thứ hai trong ba phương pháp nhận dạng được áp dụng nhiều hiện nay. Hệ thống AFIS nói chung cũng sử dụng phương pháp này. - Phương pháp thứ nhất, sử dụng đặc trưng tương quan của hai mẫu vân tay. Xếp chồng trực tiếp hai mẫu này và dựa vào tương quan giữa các pixel để tính toán sự khác nhau giữa hai mẫu. 1
4. - Phương pháp thứ hai, sử dụng các đặc trưng về đường vân. Đường vân của các mẫu được trích ra khỏi ảnh ban đầu rồi so sánh giữa chúng. Đồ án sẽ sử dụng bộ mẫu chuẩn các vân tay đã được chuẩn bị trước. Đó là các ảnh số vân tay lấy từ việc tìm kiếm trên mạng. 1.2 Mục đích đề tài Sử dụng phần mềm Matlab để xây dựng một hệ thống nhận dạng vân tay từ các ảnh vân tay có sẵn. 1.3 Nhiệm vụ đề tài - Tìm hiểu thuật toán nhận diện vân tay. - Viết ứng dụng, xây dựng hệ thống nhận dạng từ các ảnh vân tay có sẵn. - Tạo tập mẫu chứa các ảnh vân tay. - Mô phỏng chương trình nhận diện ảnh vân tay bằng phần mềm Matlab. 1.4 Giới hạn đề tài - Không sử dụng phần cứng, chỉ sử dụng phần mềm và ảnh có sẵn. - Kích thước cho phép các ảnh đưa vào tối đa là 640x480. 1.5 Nội dung các chương Đồ án được trình bày theo các chương sau: - Chương 1: Giới thiệu chung về đồ án. Giới thiệu về nhận dạng vân tay. - Chương 2: Xử lý ảnh và vân tay trong sinh trắc học. Giới thiệu về xử lý ảnh. - Chương 3: Hệ thống nhận dạng vân tay. Trình bày sơ đồ khối thiết kế hệ thống. Lưu đồ chương trình. - Chương 4: Kết quả thực hiện. Kết quả thực hiện mô phỏng chương trình trên phần mềm Matlab. - Chương 5: Kết luận và hướng phát triển. Trình bày những việc đã đạt được những kinh nghiệm rút ra trong quá trình thực hiện đồ án, các hạn chế và hướng phát triển đề tài. 2
5. Chương 2: XỬ LÝ ẢNH VÀ VÂN TAY TRONG SINH TRẮC HỌC 2.1 Tổng quan về xử lý ảnh 2.1.1 Giới thiệu về xử lý ảnh Xử lý ảnh là một phân ngành trong xử lý số tín hiệu với tín hiệu xử lý là ảnh mang tính khoa học và công nghệ. Đây là một phân ngành khoa học mới rất phát triển trong những năm gần đây. Hiện nay nó đang là một trong những lĩnh lực được quan tâm. Xử lý ảnh gồm 4 lĩnh vực chính: xử lý nâng cao chất lượng ảnh, nhận dạng ảnh, nén ảnh và truy vấn ảnh. Sự phát triển của xử lý ảnh đem lại rất nhiều lợi ích cho cuộc sống của con người. Ngày nay xử lý ảnh đã được áp dụng rất rộng rãi trong đời sống như: photoshop, nén ảnh, nén video, nhận dạng biển số xe, nhận dạng khuôn mặt, nhận dạng chữ viết, xử lý ảnh thiên văn, ảnh y tế, Xử lý ảnh được đưa vào giảng dạy ở bậc đại học ở nước ta khoảng chục năm nay. Nó là môn học liên quan đến nhiều lĩnh vực và cần nhiều kiến thức cơ sở khác. Đầu tiên phải kể đến Xử lý tín hiệu số là một môn học hết sức cơ bản cho xử lý tín hiệu chung, các khái niệm về tích chập, các biến đổi Fourier, biến đổi Laplace, các bộ lọc hữu hạn Thứ hai, các công cụ toán như Đại số tuyến tính, xác xuất, thống kê. Một số kiến thứ cần thiết như Trí tuệ nhân tao, Mạng nơ ron nhân tạo cũng được đề cập trong quá trình phân tích và nhận dạng ảnh. Các phương pháp xử lý ảnh bắt đầu từ các ứng dụng chính: nâng cao chất lượng ảnh và phân tích ảnh. Ứng dụng đầu tiên được biết đến là nâng cao chất lượng ảnh báo được truyền qua cáp từ Luân đôn đến New York từ những năm 1920. Vấn đề nâng cao chất lượng ảnh có liên quan tới phân bố mức sáng và độ phân giải của ảnh. Việc nâng cao chất lượng ảnh được phát triển vào khoảng những năm 1955. Điều này có thể giải thích được vì sau thế chiến thứ hai, máy tính phát triển nhanh tạo điều kiện cho quá trình xử lý ảnh sô thuận lợi. Năm 1964, máy tính đã có khả năng xử lý và nâng cao chất lượng ảnh từ mặt trăng và vệ tinh Ranger 7 của Mỹ bao gồm: làm nổi đường biên, lưu ảnh. Từ năm 1964 đến nay, các phương tiện xử lý, nâng cao chất lượng, nhận dạng ảnh phát triển không ngừng. Các phương pháp tri thức nhân tạo như mạng nơ ron nhân tạo, các thuật toán xử lý hiện đại và cải tiến, các công cụ nén ảnh ngày càng được áp dụng rộng rãi và thu nhiều kết quả khả quan. Để dễ tưởng tượng, xét các bước cần thiết trong xử lý ảnh. Đầu tiên, ảnh tự nhiên từ thế giới ngoài được thu nhận qua các thiết bị thu (như Camera, máy chụp ảnh). 3
6. Trước đây, ảnh thu qua Camera là các ảnh tương tự (loại Camera ống kiểu CCIR). Gần đây, với sự phát triển của công nghệ, ảnh màu hoặc đen trắng được lấy ra từ Camera, sau đó nó được chuyển trực tiếp thành ảnh số tạo thuận lợi cho xử lý tiếp theo. (Máy ảnh số hiện nay là một ví dụ gần gũi). Mặt khác, ảnh cũng có thể tiếp nhận từ vệ tinh; có thể quét từ ảnh chụp bằng máy quét ảnh. Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Hình 2.1 Quá trình xử lý ảnh Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem như là đặc trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trong không gian và nó có thể xem như một hàm n biến P(c1, c2, , cn). Do đó, ảnh trong xử lý ảnh có thể xem như ảnh n chiều. Sơ đồ tổng quát của một hệ thống xử lý ảnh: Hình 2.2 Các bước cơ bản trong hệ thống xử lý ảnh 2.1.2 Những khái niệm cơ bản trong xử lý ảnh 2.1.2.1 Điểm ảnh (Picture Element) Gốc của ảnh (ảnh tự nhiên) là ảnh liên tục về không gian và độ sáng. Để xử lý bằng máy tính (số), ảnh cần phải được số hoá. Số hoá ảnh là sự biến đổi gần đúng một ảnh liên tục thành một tập điểm phù hợp với ảnh thật về vị trí (không 4
7. gian) và độ sáng (mức xám). Khoảng cách giữa các điểm ảnh đó được thiết lập sao cho mắt người không phân biệt được ranh giới giữa chúng. Mỗi một điểm như vậy gọi là điểm ảnh (PEL: Picture Element) hay gọi tắt là Pixel. Trong khuôn khổ ảnh hai chiều, mỗi pixel ứng với cặp tọa độ (x, y). Định nghĩa: Điểm ảnh (Pixel) là một phần tử của ảnh số tại toạ độ (x, y) với độ xám hoặc màu nhất định. Kích thước và khoảng cách giữa các điểm ảnh đó được chọn thích hợp sao cho mắt người cảm nhận sự liên tục về không gian và mức xám (hoặc màu) của ảnh số gần như ảnh thật. Mỗi phần tử trong ma trận được gọi là một phần tử ảnh. 2.1.2.2 Độ phân giải của ảnh Định nghĩa: Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn định trên một ảnh số được hiển thị. Theo định nghĩa, khoảng cách giữa các điểm ảnh phải được chọn sao cho mắt người vẫn thấy được sự liên tục của ảnh. Việc lựa chọn khoảng cách thích hợp tạo nên một mật độ phân bổ, đó chính là độ phân giải và được phân bố theo trục x và y trong không gian hai chiều. Ví dụ: Độ phân giải của ảnh trên màn hình CGA là một lưới điểm theo chiều ngang màn hình: 320 điểm chiều dọc * 200 điểm ảnh (320*200). Rõ ràng, cùng màn hình CGA 12” ta nhận thấy mịn hơn màn hình CGA 17” độ phân giải 320*200. Lý do: cùng một mật độ (độ phân giải) nhưng diện tích màn hình rộng hơn thì độ mịn (liên tục của các điểm) kém hơn. 2.1.2.3 Mức xám của ảnh Một điểm ảnh (pixel) có hai đặc trưng cơ bản là vị trí (x, y) của điểm ảnh và độ xám của nó. Dưới đây chúng ta xem xét một số khái niệm và thuật ngữ thường dùng trong xử lý ảnh. - Định nghĩa: Mức xám của điểm ảnh là cường độ sáng của nó được gán bằng giá trị số tại điểm đó. - Các thang giá trị mức xám thông thường: 16, 32, 64, 128, 256 (Mức 256 là mức phổ dụng. Lý do: từ kỹ thuật máy tính dùng 1 byte (8 bit) để biểu diễn mức xám: Mức xám dùng 1 byte biểu diễn: 28 =256 mức, tức là từ 0 đến 255). - Ảnh đen trắng: là ảnh có hai màu đen, trắng (không chứa màu khác) với mức xám ở các điểm ảnh có thể khác nhau. 5
8. - Ảnh nhị phân: ảnh chỉ có 2 mức đen trắng phân biệt tức dùng 1 bit mô tả 21 mức khác nhau. Nói cách khác: mỗi điểm ảnh của ảnh nhị phân chỉ có thể là 0 hoặc 1. - Ảnh màu: trong khuôn khổ lý thuyết ba màu (Red, Blue, Green) để tạo nên thế giới màu, người ta thường dùng 3 byte để mô tả mức màu, khi đó các giá trị màu: 28*3 =224 ≈16,7 triệu màu. 2.1.2.4 Định nghĩa ảnh số Ảnh số là tập hợp các điểm ảnh với mức xám phù hợp dùng để mô tả ảnh gần với ảnh thật. 2.1.2.5 Quan hệ giữa các điểm ảnh Một ảnh số giả sử được biểu diễn bằng hàm f(x, y). Tập con các điểm ảnh là S; cặp điểm ảnh có quan hệ với nhau ký hiệu là p, q. Chúng ta nêu một số các khái niệm sau: o Các lân cận của điểm ảnh (Image Neighbors) * Giả sử có điểm ảnh p tại toạ độ (x, y). p có 4 điểm lân cận gần nhất theo chiều đứng và ngang (có thể coi như lân cận 4 hướng chính: Đông, Tây, Nam, Bắc). {(x-1, y); (x, y-1); (x, y+1); (x+1, y)} = N4(p) (2.1) Trong đó: số 1 là giá trị logic; N4(p) tập 4 điểm lân cận của p. Hình 2.3 Lân cận các điểm ảnh của tọa độ (x,y) * Các lân cận chéo: Các điểm lân cận chéo Np(p) (Có thể coi lân cận chéo là 4 hướng: Đông-Nam, Đông-Bắc, Tây-Nam, Tây-Bắc) Np(p) = { (x+1, y+1); (x+1, y-1); (x-1, y+1); (x-1, y-1)} (2.2) 6
9. * Tập kết hợp: N8(p) = N4(p) + NP(p) là tập hợp 8 lân cận của điểm ảnh p. * Chú ý: Nếu (x, y) nằm ở biên (mép) ảnh; một số điểm sẽ nằm ngoài ảnh. o Các mối liên kết điểm ảnh. Các mối liên kết được sử dụng để xác định giới hạn (Boundaries) của đối tượng vật thể hoặc xác định vùng trong một ảnh. Một liên kết được đặc trưng bởi tính liền kề giữa các điểm và mức xám của chúng. Giả sử V là tập các giá trị mức xám. Một ảnh có các giá trị cường độ sáng từ thang mức xám từ 32 đến 64 được mô tả như sau: V={32, 33, , 63, 64}. Có 3 loại liên kết. * Liên kết 4: Hai điểm ảnh p và q được nói là liên kết 4 với các giá trị cường độ sáng V nếu q nằm trong một các lân cận của p, tức q thuộc N4(p) * Liên kết 8: Hai điểm ảnh p và q nằm trong một các lân cận 8 của p, tức q thuộc N8(p) * Liên kết m (liên kết hỗn hợp): Hai điểm ảnh p và q với các giá trị cường độ sáng V được nói là liên kết m nếu. 1. q thuộc N4(p) 2. q thuộc Np(p) o Đo khoảng cách giữa các điểm ảnh. Định nghĩa: Khoảng cách D(p, q) giữa hai điểm ảnh p toạ độ (x, y), q toạ độ (s, t) là hàm khoảng cách (Distance) hoặc Metric nếu: 1. D(p,q) ≥0 (Với D(p,q)=0 nếu và chỉ nếu p=q) 2. D(p,q) = D(q,p) 3. D(p,z) ≤D(p,q) + D(q,z); z là một điểm ảnh khác. Khoảng cách Euclide: Khoảng cách Euclide giữa hai điểm ảnh p(x, y) và q(s,t) được định nghĩa như sau: 2 2 1/2 De(p, q) = [(x - s) + (y - t) ] (2.3) 7
10. Khoảng cách khối: Khoảng cách D4(p, q) được gọi là khoảng cách khối đồ thị (City Block Distance) và được xác định như sau: D4(p,q) = | x - s | + | y - t | (2.4) Giá trị khoảng cách giữa các điểm ảnh r: giá trị bán kính r giữa điểm ảnh từ tâm điểm ảnh đến tâm điểm ảnh q khác. Ví dụ: Màn hình CGA 12” (12”*2,54cm = 30,48cm=304,8mm) độ phân giải 320*200; tỷ lệ 4/3 (Chiều dài/Chiều rộng). Theo định lý Pitago về tam giác vuông, đường chéo sẽ lấy tỷ lệ 5 phần (5/4/3: đường chéo/chiều dài/chiều rộng màn hình); khi đó độ dài thật là (305/244/183) chiều rộng màn hình 183mm ứng với màn hình CGA 200 điểm ảnh theo chiều dọc. Như vậy, khoảng cách điểm ảnh lân cận của CGA 12” là ≈1mm. Khoảng cách D8(p,q) còn gọi là khoảng cách bàn cờ (Chess-Board Distance) giữa điểm ảnh p, q được xác định như sau: D8(p,q) = max (| x-s | , | y-t |) (2.5) 2.1.2.6 Các thành phần cơ bản của hệ thống xử lý ảnh Ảnh vào Hình 2.4 Các thành phần chính của hệ thống xử lý ảnh Một hệ thống xử lý ảnh cơ bản có thể gồm: máy tính cá nhân kèm theo vi mạch chuyển đổi đồ hoạ VGA hoặc SVGA, đĩa chứa các ảnh dùng để kiểm tra các thuật toán và một màn hình có hỗ trợ VGA hoặc SVGA. Nếu điều kiện cho phép, nên có một hệ thống như Hình 2.5 bao gồm một máy tính PC kèm theo thiết bị xử lý ảnh. Nối với cổng vào của thiết bị thu nhận ảnh là một video camera, và cổng ra nối với một màn hình. Thực tế, phần lớn các nghiên cứu của chúng ta 8
11. được đưa ra trên ảnh mức xám (ảnh đen trắng). Bởi vậy, hệ thống sẽ bao gồm một thiết bị xử lý ảnh đen trắng và một màn hình đen trắng. Ảnh mức xám được áp dụng trong nhiều lĩnh vực như sinh vật học hoặc trong công nghiệp. Thực tế chỉ ra rằng bất kỳ ứng dụng nào trên ảnh, mức xám cũng ứng dụng được trên ảnh màu. Với lý do đó, hệ thống ban đầu nên chỉ bao gồm cấc thiết bị thu nhận và hiển thị ảnh đen trắng. Với ảnh màu, nên sử dụng một hệ thống mới như Hình 2.3, trừ trường hợp bạn cần một camera TV màu và một màn hình đa tần số (ví dụ như NEC MultiSync, Sony Multiscan, hoặc Mitsubishi Diamond Scan) để hiển thị ảnh màu. Nếu khả năng hạn chế, có thể dùng PC kèm theo vi mạch VGA và màn hình VGA, để dựng ảnh được. Hình 2.5 Một hệ thống xử lý ảnh 2.1.2.7 Biến đổi ảnh (Image Transform) Trong xử lý ảnh do số điểm ảnh lớn các tính toán nhiều (độ phức tạp tính toán cao) đòi hỏi dung lượng bộ nhớ lớn, thời gian tính toán lâu. Các phương pháp khoa học kinh điển áp dụng cho xử lý ảnh hầu hết không khả thi. Người ta sử dụng các phép toán tương đương hoặc biến đổi sang miền xử lý khác để dễ tính toán. Sau khi xử lý dễ dàng 9
12. hơn được thực hiện, dùng biến đổi ngược để đưa về miền xác định ban đầu, các biến đổi thường gặp trong xử lý ảnh gồm: - Biến đổi Fourier, Cosin, Sin - Biến đổi (mô tả) ảnh bằng tích chập, tích Kronecker (theo xử lý số tín hiệu) - Các biến đổi khác như KL (Karhumen Loeve), Hadamard 2.1.2.8 Nén ảnh Nhằm giảm thiểu không gian lưu trữ. Thường được tiến hành theo cả hai cách khuynh hướng là nén có bảo toàn và không bảo toàn thông tin. Nén không bảo toàn thì thường có khả năng nén cao hơn nhưng khả năng phục hồi thì kém hơn. Trên cơ sở hai khuynh hướng, có 4 cách tiếp cận cơ bản trong nén ảnh: - Nén ảnh thống kê: Kỹ thuật nén này dựa vào việc thống kê tần xuất xuất hiện của giá trịcác điểm ảnh, trên cơsở đó mà có chiến lược mã hóa thích hợp. Một ví dụ điển hình cho kỹ thuật mã hóa này là *.TIF - Nén ảnh không gian: Kỹ thuật này dựa vào vị trí không gian của các điểm ảnh để tiến hành mã hóa. Kỹ thuật lợi dụng sự giống nhau của các điểm ảnh trong các vùng gần nhau. Ví dụ cho kỹ thuật này là mã nén *.PCX - Nén ảnh sử dụng phép biến đổi: Đây là kỹ thuật tiếp cận theo hướng nén không bảo toàn và do vậy, kỹ thuật thường nén hiệu quả hơn. *.JPG chính là tiếp cận theo kỹ thuật nén này. - Nén ảnh Fractal: Sử dụng tính chất Fractal của các đối tượng ảnh, thể hiện sự lặp lại của các chi tiết. Kỹ thuật nén sẽ tính toán để chỉ cần lưu trữ phần gốc ảnh và quy luật sinh ra ảnh theo nguyên lý Fractal Các ứng dụng xử lý ảnh: + Di chuyển của Robot. + Các phương tiện đi lại tự vận hành. + Công cụ hướng dẫn cho người mù. + An ninh và giám sát. + Nhận dạng đối tượng, nhận dạng khuôn mặt. + Ứng dụng trong y học. + Sản xuất, hiệu chỉnh Video. + Chinh phục vũ trụ 10
13. 2.2 Vân tay trong sinh trắc học Trong phần này sẽ trình bày những tiếp cận khởi đầu như: vị trí của nhận dạng vân tay trong sinh trắc học, những tính chất của vân tay để trở thành đối tượng cơ bản của sinh trắc học, hình thức thể hiện và đặc tả của một mẫu vân tay và những khó khan gặp phải khi nhận dạng vân tay. Dựa vào tiêu chuẩn physiological sinh trắc học có: dạng vân tay, mặt, đồng tử, giọng nói Còn dựa vào tiêu chuẩn behavioral sinh trắc học có: nhận dạng chữ viết, chữ ký Hình 2.6 Một số tín hiệu sinh trắc học cơ bản: a) giọng nói; b) đồng tử; c) chữ ký 2.2.1 Tính độc nhất của vân tay Cho tới nay, vẫn chưa có bằng chứng xác thực 100% vân tay trên các ngón tay tuyệt đối mang tính cá nhân và không hề lặp lại. Câu trả lời chính xác chỉ có được khi đem so sánh từng mẫu vân tay của mười đầu ngón người với hơn bảy tỉ người còn lại. Tuy nhiên khi không xét tới phần nhỏ lẻ ấy có thể rút ra một số tính chất cơ bản của vân tay để nó trở thành phổ biến trong ứng dụng nhận dạng và định danh con người: + Tính “phổ thông” mọi người đều có. + Tính cá nhân và không lặp lại. Xác suất trùng khớp với người khác gần bằng không. + Tính “bất biến”. Hình dạng tổng thể của vân tay trên các ngón tay của con người không thay đổi theo thời gian. Ngay cả trường hợp bị chấn thưong nhẹ, dấu vân tay vẫn có khả năng khôi phục lại. 11
14. 2.2.2 Hình thức thể hiện và các đặc tả của vân tay Nhằm mục đích mô tả người ta đã định nghĩa một số hình thức thể hiện vân tay. Mỗi một trường hợp thể hiện thì sẽ có hình thức trích chọn đặc tả vân tay tương ứng. Vì vậy, căn cứ vào ảnh vân tay đầu vào chúng ta có thể lựa chọn được đặc tính cần trích chọn và dự kiến phương án nhận dạng. Hình thức thể hiện vân tay được chia thành ba cấp độ: global (thể hiện tổng thể vân tay), local (thể hiện vân tay bởi một số điểm đặc trưng khi đường vân được làm mảnh đến một pixel), very-fine (thể hiện bởi các vòng xuyến tạo hình nên đường vân - sweat pores). Đối với cấp độ very-fine thì đòi hỏi các phương tiện xử lý tốn kém cũng như các yêu cầu đặc biệt khác mà khó có thể ứng dụng trong dân sự. Chẳng hạn để trích được các pores, ảnh cần có độ phân giải tối thiểu 1000dpi (dots per inch). Sau đây sẽ tìm hiểu sâu hơn các đặc trưng vân tay ở hai cấp độ đầu. Hình 2.7 Vân tay thể hiện trong cấp độ global : a) arch; b) whorl; c) tented arch; d) left loop; e) right loop; hình vuông đánh dấu điểm loop, hình tam giác đánh dấu điểm delta Ở cấp độ global, đặc trưng vân tay liên quan nhiều đến sự tạo hình của đường vân và các điểm kỳ dị (singular), chúng bao gồm: loop (đường vân tạo vòng xoáy hở), delta 12
15. (đường vân tạo hình tam giác). Điểm kỳ dị có vai trò quan trọng trong việc thực hiện phân loại vân tay và tổ chức, xây dựng cơ sở dữ liệu. Ở mức độ cục bộ, các đặc trưng của vân tay được gọi là minutiae. Người ta đã thống kê có tới 150 đặc trưng loại này. Hai đặc trưng cơ bản và nổi trội hơn cả là ridge termination (điểm cụt) và ridge bifurcation (điểm rẽ nhánh) cũng được gọi tắt là minutiae. Hình 2.8 Hai dạng minutiae quan trọng: a) ridge termination; b) ridge bifurcation. 2.3 Khó khăn gặp phải khi nhận dạng vân tay Do điều kiện thu nhận ảnh quyết định nhiều đến chất lượng ảnh thu thập nên nhiều khi các chi tiết trên mẫu vân tay không thể hiện rõ ràng. Có thể liệt kê một số trường hợp dưới đây: - Dry finger (vân tay thu nhận trong điều kiện “khô”): ảnh thu nhận sẽ có nhiều chỗ đường vân bị mờ đi, đường vân bị lẫn với nền ảnh. Lực ấn của tay nhẹ hoặc mực in không đủ (với vân tay lăn trên giấy) là các nguyên nhân chính làm giảm chất lượng ảnh thu thập. - Wet finger (vân tay thu nhận trong điều kiện “ướt”): ảnh thu nhận sẽ có nhiều chỗ đường vân bị dính liền. Lực ấn của ngón tay quá lớn hoặc mực in quá nhiều (với vân tay lăn trên giấy) là các nguyên nhân chính tạo nhiễu trong trường hợp này. - Vân tay thu nhận trong điều kiện bị biến dạng: ảnh thu nhận được có thể thể hiện rõ nét nhưng các đường vân lại bị bóp méo không còn giống với mẫu thực. Lực ấn, kéo và xê dịch tay là các nguyên nhân chính. - Vân tay thu thập không đầy đủ: ảnh thu thập được chỉ có một phần vân tay trên ngón tay. Nguyên nhân chính là do ngón tay đặt không đúng vị trí chuẩn thu thập. 13
16. Chương 3 HỆ THỐNG NHẬN DẠNG DẤU VÂN TAY 3.1 Giới thiệu về hệ thống nhận dạng vân tay Như đã nói, hệ thống nhận dạng dấu vân tay được xây dựng dựa trên công nghệ sinh trắc học. Công nghệ sinh trắc học là công nghệ phân tích, đo lường các đặc điểm của cơ thể người 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, gen, chữ ký và được sử dụng cho mục đích chứng thực. Các đặc điểm sinh trắc học gần như là duy nhất đối với mỗi người, không thể bị quên hay bị mất. Do đó, sinh trắc học đáng tin cậy hơn các phương pháp truyền thống. Hệ thống nhận dạng vân tay dựa vào đặc điểm sinh trắc của vân tay có chi phí thấp và tỷ lệ đáng tin cậy cao. Nhìn chung, các hệ thống nhận dạng vân tay thường bao gồm các bước sau: XXửử lýlý Tiền xử lý Làm mảnh Trích đặc trưng Cơ sở d ữ liệu Kết quả vân tay Đối chứng ảnh Hình 3.1 Sơ đồ chung của các hệ thống nhận dạng vân tay 3.2 Sơ đồ khối hệ thống nhận dạng vân tay Trên cơ sở các phần trên, sau đây là đề xuất cho hệ thống nhận dạng vân tay phù hợp với đồ án. Hệ thống này có khả năng tạo cơ sở dữ liệu, so sánh vân tay mẫu với tập vân tay có trong cơ sở dữ liệu đã tạo. 14
17. Kiểu nhận dạng là identification, nghĩa là một mẫu cần nhận dạng (input) sẽ nhận kết quả bằng cách đối sánh với N mẫu khác trong cơ sở dữ liệu. Kiểu chế độ hoạt động của hệ thống hướng đến là offline. Tức là hệ thống có khả năng nhận diện một ảnh vân tay được đưa vào làm mẫu. Kiến trúc hệ thống thiết kế theo sơ đồ dưới đây: Hình 3.2 Lưu đồ nhận diện vân tay được sử dụng trong đồ án. 15
18. Xử lý ảnh Tiền xử lý Nhị phân hóa Làm mảnh Trích đặc trưng Kết thúc Hình 3.3 Chương trình con xử lý ảnh. Trong sơ đồ trên các khâu hoạt động như sau: 1) Ảnh đầu vào: Đưa ảnh vào hệ thống nhận diện vân tay. 2) Ảnh mẫu: Kiểm tra ảnh vào là ảnh mẫu hay ảnh cơ sở dữ liệu. 3) Tiền xử lý: Tăng cường chất lượng ảnh. 4) Nhị phân hóa: Đưa ảnh về 2 mức 0 và 1. 5) Làm mảnh: Xử lý đường vân về độ dày 1 pixel. 6) Trích đặc trưng: Xác định tọa độ điểm đặc trưng. 7) Cơ sở dữ liệu: tạo cơ sở dữ liệu. 8) So sánh đặc trưng: So sách đặc trưng của ảnh mẫu và ảnh có trong cơ sở dữ liệu. 9) Kết thúc: Đưa ra kết quả so sánh. 3.3 Ảnh nhận dạng vân tay. Vân tay có thể lưu trữ theo hai cách: trên giấy (giấy thường, giấy ảnh ) hoặc file ảnh. Đối với cách thứ nhất vẫn còn được ứng dụng trong giám định, định danh hình sự (các bằng chứng về dấu tay tội phạm cần được thể hiện bằng ảnh in trên 16
19. giấy). Cách thứ hai được ứng dụng phổ biến trong nhận dạng nói chung và ngày càng chiếm được nhiều ưu thế (có thể lưu trữ, tìm kiếm thuận tiện). Đồ án này tập trung đến hình thức lưu trữ ảnh theo file. a) b) c) Hình 3.4: Các loại vân tay. a) vân tay dấu vết. b) vân tay lăn mực. c) vân tay lấy từ máy quét vân tay Ảnh nhận dang vân tay có nhiều định dạng, phổ biến nhất là: jpeg, bmp, tif, png Các thông số bao gồm: độ rộng ảnh, độ phân giải ảnh, số bit dành cho một điểm ảnh, dung lượng ảnh Khi thiết kế hệ thống, các thông số đươc quy chuẩn sao cho phù hợp với hệ thống. Trong hệ thống nhận dạng vân tay bằng ảnh số, ảnh số là đại lượng đầu vào nên hai thông quan tâm hơn cả: kích thước và độ phân giải. Như trình bày ở trên, trong đồ án này sử dụng ảnh vân tay từ dữ liệu máy quét vân tay. Các vân tay lưu theo file ảnh, kích thước là 248x188 pixel, định dạng đuôi .png, sử dụng 8 bit để biêu diễn mỗi điểm ảnh. Ảnh trong cơ sở dữ liệu có tên dạng anh_xx.png, trong đó xx là thứ tự ảnh. 3.4 Tiền xử lý Thu nhận ảnh không phải lúc nào cũng cho kết quả là những ảnh có chất lượng tốt. Hệ thống nhận dạng vân tay phụ thuộc rất nhiều vào chất lượng ảnh đầu vào. Trong các ảnh vân tay có chất lượng thấp, cấu trúc đường vân không rõ ràng vì thế việc phát hiện và trích chọn đặc trưng đường vân sẽ gặp nhiều khó khăn, đồng thời có thể dẫn đến việc tao ra nhiều điểm đặc trưng giả, bỏ qua các điểm đặc trưng thật, định sai vị trí điểm đặc trưng. Vì thế, tiền xử lý là quá trình tăng cường chất lượng ảnh vào nhằm nâng cao hiệu quả của quá trình nhận dạng. Đối với ảnh vân tay lăn mực hoặc ảnh vân tay dấu vết thì bước tiền xử lý là rất cần thiết nhằm khắc phục các sai sót còn tồn tại trong các loại ảnh này. Tuy nhiên 17
20. đối với các vân tay sử dụng ảnh vân tay của máy quét vân tay thì không quá cần thiết dùng các bước này vì chất lượng ảnh thu được có chất lượng khá tốt, đủ đáp ứng yêu cầu hệ thống. Hình 3.5 Sơ đồ tiền xử lý. 3.5 Nhị phân hóa ảnh Nhị phân hóa ảnh là quá trình đưa ảnh đa mức xám (8 bit) về ảnh nhị phân (2 bit). Do khâu tiếp theo là quá trình làm mảnh, đưa độ rộng vân tay về 1 pixel nên việc đưa ảnh về ảnh nhị phân giúp thuật toán làm mảnh trở nên dễ dàng và nhanh hơn. Mức ngưỡng thường được chọn trong quá trình làm mảnh là 128. Với mỗi điểm ảnh (i,j) của ảnh M. Quá trình nhị phân hóa như sau: (3.1) Trong đó |M(i,j)| là giá trị mức xám điểm ảnh (i,j) của ảnh M. 18
21. 3.6 Làm mảnh Làm mảnh là khâu quan trọng trong quá trình nhận dạng vân tay. Như đã nói ở trên, làm mảnh đưa độ rộng của ảnh vân tay về 1 pixel mà không làm mất đặc trưng của ảnh vân tay (vẫn giữ được các điểm đặc trưng). Thuật toán làm mảnh phải đảm bảo được việc xóa các điểm thừa, vừa đảm bảo tính liên kết với các điểm xung quanh. Một trong số các thuật toán đầu tiên được sử dụng là thuật toán của Stentiford, tuy nhiên thuật toán này sử dụng khá nhiều vòng lặp và quá nhiều lần kiểm tra điểm ảnh, cho nên thuật toán này không khả thi khi sử dụng trong đồ án. Nên ta dùng các ma trận W(3x3) để quét hết cả ảnh, cách này làm mảnh có hiệu quả cao hơn: • Bước 1: Ảnh nhị phân được thêm bit “0” làm “bìa” bao bên ngoài ảnh. • Bước 2: Sử dụng một ma trận W(3x3) để quét ảnh. + Lần quét 1: Ảnh đầu vào là ảnh của lần quét thứ 2 hoặc ảnh nhị phân ban đầu với lần quét đầu tiên. Với mỗi điểm (i,j) là trung tâm ma trận W của ảnh, nếu thỏa mãn điều kiện G1, G2, G3 thì xóa điểm ảnh (i,j). + Lần quét 2: Sử dụng ảnh của lần quét 1 làm ảnh đầu vào, tương tự, với mỗi điểm (i,j) là trung tâm ma trận W của ảnh, nếu thỏa mãn điều kiện G1, G2, G3’ thì xóa điểm ảnh (i,j). • Bước 3: Quay lại thực hiện bước 2 cho đến khi ảnh được làm mảnh hoàn toàn. Thông thường ảnh vân tay được làm mảnh với vòng lặp có giá trị bằng 7. W4 W3 W2 W5 W0 W1 W6 W7 W8 Hình 3.6 Ma trận W(3x3) được sử dụng để quét ảnh. 19
22. S K L 0 0 2 1 5 4