Khóa luận Nghiên cứu và phát triển ứng dụng nhận dạng vân tay

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Đức Luân NGHIÊN CỨU VÀ PHÁT TRIỂN ỨNG DỤNG NHẬN DẠNG VÂN TAY KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI-2006 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Đức Luân NGHIÊN CỨU VÀ PHÁT TRIỂN ỨNG DỤNG NHẬN DẠNG VÂN TAY KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: ThS Trần Quốc Long HÀ NỘI-2006 LỜI CẢM ƠN Em xin chân thành cảm ơn toàn thể các thầy cô giáo trong trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã hết lòng dạy dỗ, chỉ bảo, tạo điều kiện tốt cho em trong suốt quá trình học tập cũng như trong thời gian thực hiện khoá luận tốt nghiệp này. Đặc biệt, em gửi lời cám ơn chân thành và sâu sắc tới ThS Trần Quốc Long – Bộ môn khoa học máy tính – trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội, người đã trực tiếp quan tâm, tận tình hướng dẫn, giúp đỡ và tạo điều kiện hết sức thuận lợi cho em trong quá trình thực hiện khoá luận. Cảm ơn các bạn đồng khoá và gia đình đã động viên, giúp đỡ tôi rất nhiều trong quá trình học tập tại Khoa Công nghệ cũng như trong thời gian thực hiện khoá luận. Hà nội, ngày24 tháng 05 năm 2006 Nguyễn Đức Luân TÓM TẮT KHÓA LUẬN Nghiên cứu và ứng dụng sinh trắc vào cuộc sông là một những xu hướng quan trọng và có thực tiễn cao. Do nhu cầu nhận dạng cá nhân trong các tổ chức chính phủ và dân sự để đảm bảo an ninh. Có nhiều đặc trưng sinh trắc có thể được sử dụng để nhận dạng cá nhân. Trong đó vân tay là một đặc trưng sinh trắc được nhiều người chấp nhận và sử dụng nhờ tính ổn định, phân biệt cao của nó Khóa luận sẽ tập trung vào nghiên cứu các thuật toán hỗ trỡ cho việc đối sánh vân tay để nhận dạng một cá nhân nào đó MỤC LỤC Chương 1: GIỚI THIỆU 7 1.1.Sự cần thiết của nhận dạng bằng ảnh sinh trắc 7 1.2.Lịch sử của vân tay: 7 1.3.Các hệ thống xác thực 9 1.4.So sánh các đặc trưng sinh trắc 10 1.5.Các loại lỗi của hệ thống sinh trắc: 11 1.5.1.Các lỗi của hệ thống kiểm tra: 12 1.5.2.Các loại lỗi của hệ thống nhận dạng: 16 Chương 2. PHÂN TÍCH VÀ BIỂU DIỄN VÂN TAY 18 2.1.Phân tích cấu trúc vân tay: 18 2.2.Biểu diễn hình ảnh vân tay. 19 2.3.Ước lượng hướng vân cục bộ 19 2.4.Ước lượng tần suất vân cục bộ 21 2.5.Tăng cường ảnh: 23 2.6. Phát hiện chi tiết 29 2.7.Lọc chi tiết 32 CHƯƠNG 3:ĐỐI SÁNH VÂN TAY 34 3.1 Đặt vấn đề 34 3.2. Các kĩ thuật dựa độ tương quan 37 3.3. Các phương pháp dựa chi tiết 41 3.4 Các kĩ thuật đối sánh dựa đặc trưng vân 46 3.5 So sánh hiệu năng của các thuật toán đối sánh. 47 Chương 4: CÁC THUẬT TOÁN VÀ THỰC NGHIỆM 49 4.1 Giới thiệu 49 4.2 Các thuật toán được sử dụng. 49 4.2.1 Thuật toán tính hướng vân tay cục bộ. 49 4.2.1.1 Phương pháp. 49 4.2.1.2 Kết quả thực thi. 50 4.2.2 Thuật toán chuẩn hóa ảnh. 50 4.2.2.1 Phương pháp. 50 4.2.2.2 Kết quả thực thi 51 4.2.3 Thuật toán tăng cường ảnh 51 4.2.3.1 Phương pháp 51 4.2.3.2 Kết quả thực thi. 52 4.2.4 Thuật toán tách ngưỡng tự động. 53 4.2.4.1 Phương pháp 53 4.2.4.2 Thực nghiêm phương pháp tác ngưỡng theo cơ chế tìm ngưỡng tự động. 53 4.2.5 Thuật toán tìm xương. 54 4.2.5.1 Phương pháp. 54 4.2.5.2.Kết quả thực thi 57 4.2.6 Tìm kiếm chi tiết. 57 4.2.6.1 Phương pháp. 57 4.2.6.1 Kết quả thực thi: 58 4.2.7 Thuật toán Hough 58 4.2.7.1 Phương pháp. 59 4.2.7.2 Kết quả thực thi. 59 4.2.8 Thuật toán đối sánh vân tay 60 4.2.8.1 Phương pháp. 60 4.2.8.2 Kết quả thực thi. 61 KẾT LUẬN:…………………………………………………………………………63 TÀI LIỆU THAM KHẢO…………………………………………………………...64 CHƯƠNG 1: GIỚI THIỆU 1.1.Sự cần thiết của nhận dạng bằng ảnh sinh trắc Nhận dạng sinh trắc đề cập đến việc sử dụng các đặc tính hành vi và thể chất ( ví dụ: vân tay, gương mặt, chữ kí…) có tính chất khác biệt để nhận dạng một người một cách tự động. Trong các tổ chức, cơ sở hành chính, khoa học…luôn có nhu cầu kiểm tra và trả lời các câu hỏi: “một người có được quyền vào và sử dụng các thiết bị hay không”, “một cá nhân có quyền truy cập thông tin mật”… Người ta nhận thấy các đặc trưng sinh trắc không thể dễ dàng bị thay thế, chia sẻ hay giả mạo.., chúng được xem là đáng tin cậy hơn trong nhận dạng một người so với các phương pháp dựa vào thẻ bài truyền thống ( ví dụ dùng chìa khóa…), phương pháp dựa vào trí thức ( ví dụ dùng mật khẩu ). Nhận dạng sinh trắc ngày càng cung cấp mức độ an toàn cao hơn, tính hiệu quả cao hơn, và càng thuận tiện cho người dùng. Vì vậy, các hệ thống sinh trắc đang được triển khai và thử nghiệm ngày càng nhiều trong các khu vực quản lý thuộc chính phủ ( chứng minh thư, bằng lái xe…), khu vực dân sinh( thẻ thông minh, đăng nhập mạng máy tính, …). Nhiều công nghệ sinh trắc đã và đang được phát triển, một số chúng đang được sử dụng trong các ứng dụng thực tế. Các đặc trưng sinh trắc thường được sử dụng là vân tay, gương mặt, mống mắt, tiếng nói. Mỗi đặc trưng sinh trắc có điểm mạnh và điểm yếu riêng, nên việc sử dụng đặc trưng sinh trắc cụ thể là tùy thuộc vào yêu cầu của mỗi ứng dụng nhất định.Các đặc trưng sinh trắc có thể được so sánh dựa vào các yếu tố sau: tính phổ biến, tính phân biệt, tính ổn định, tính thu thập, hiệu quả, tính chấp nhận. Vân tay-được biết tới với tính phân biệt ( tính chất cá nhân ) và ổn định theo thời gian là đặc trưng sinh trắc được sử dụng rộng rãi nhất. 1.2.Lịch sử của vân tay: Trên các mẫu khảo cổ học và các mẫu vật lịch sử, người ta đã tìm thấy nhiều mẫu vân tay. Điều này cung cấp bằng chứng rõ ràng là người xưa đã nhận ra tính cá nhân của vân tay, nhưng không xuất hiện bất kì cơ sở khoa học nào. Mãi đến thế kỉ 16 các kĩ thuật vân tay khoa học hiện đại mới xuất hiện và từ đó các lí thuyết và chương trình mô tả, nhận dạng vân tay mới phát triển mau chóng: Hình 1.1: một số bằng chứng vân tay tìm được thời xưa Năm 1964:Nehemiah Grew nhà sinh thái học thực vật xuất bản những trang sách đầu tiên các nghiên cứu có tính hệ thống của ông về vân tay Năm 1788: Mayer đã mô tả chi tiết thông tin giải phẫu của vân tay để đặc tính hóa, nhận dạng các đặc tính vân tay Năm 1809, Thomas Bewick bắt đầu sử dụng vân tay của mình như là biểu tượng đăng kí thương mại – đã tạo ra một cột mốc quan trọng trong nghiên cứu khoa học về nhận dạng vân tay. Năm 1880: Henrry Fauld đã đưa ra giả thuyết khoa học khẳng định tính cá nhân của vân tay dựa vào các nhận thức kinh nghiệm Năm 1888, Ngài Francis Galton giới thiệu các đặc trưng chi tiết phục vụ cho đối sánh vân tay Đầu thế kỉ 20, cấu trúc của vân tay mới được mô tả một cách khá đầy đủ. Các nguyên lý sinh học của vân tay được tổng kết như sau: a. Biểu bì vân có các đặc tính khác nhau trên các vân tay khác nhau b. Cấu hình vân tay có sự thay đổi trên từng cá nhân, nhưng sự thay đổi nhỏ này vẫn cho phép phân loại một cách có hệ thống các vân tay. c.Các chi tiết và cấu hình của mỗi đường vân là ổn định và không thay đổi Nguyên lý a) là cơ sở cho nhận dạng vân tay, nguyên lý b) là cơ sở để tiến hành phân loại vân tay. Cũng từ đầu thế kỉ 20, nhận dạng vân tay chính thức được chấp nhận như một phương pháp nhận dạng cá nhân có giá trị và trở thành chuẩn trong pháp luật. Ví dụ, năm 1924 FBI đã thiết lập một cơ sở dữ liệu có 810000 thẻ vân tay. 1.3.Các hệ thống xác thực. Một hệ thống sinh trắc cơ bản là một hệ thống nhận dạng mẫu để nhận ra một người bằng cách quyết định tính xác thực của một đặc tính sinh học hay hành vi thuộc về người đó. Trong thiết kế một hệ thống sinh trắc, một vấn đề quan trọng đặt ra là xác định cách một người được nhận dạng. Một hệ thống sinh trắc có thể là một hệ thống kiểm tra hay một hệ thống nhận dạng. Hệ thống kiểm tra: là hệ thống xác thực một người bằng cách so sánh đặc tính sinh trắc của người này với mẫu sinh trắc của chính người đó đã được lưu trữ trước trong hệ thống. Hệ thống nhận dạng:là hệ thống xác thực một cá nhân bằng cách tìm kiếm và đối sánh đặc tính sinh trắc của người này với toàn bộ các mẫu sinh trắc được lưu giữ trong cơ sở dữ liệu. Ngoài ra một hệ thống sinh trắc có thể được phân loại theo một số đặc tính của ứng dụng: Phối hợp hoặc không phối hợp: đề cập đến hành vi của kẻ giả mạo tương tác với hệ thống. Ví dụ ở ngân hàng điện tử,là trường hợp có phối hợp kẻ mạo danh phải đăng nhập hệ thống để sử dụng tài khoản, còn ở hệ thống không phối hợp trong kiểm tra hộ chiếu đi máy bay, những kẻ khủng bố có thể bị phát hiện khi sử dụng hộ chiếu Công khai và bí mật: hệ thống là công khai nếu người sử dụng biết mình đang được xác thực bởi hệ thống, còn khi người sử dụng không biết mình đang được xác thực bởi hệ thống thì hệ thống là bí mật. Thường xuyên và không thường xuyên: chỉ mức độ thường xuyên mà người dùng sử dụng hệ thống sinh trắc. Ví dụ, ứng dụng đăng nhập máy tính là một hệ thống sinh trắc thường xuyên bởi vì ứng dụng này được sử dụng đều đặn, còn ứng dụng làm bằng lái xe là hệ thống không thường xuyên do mỗi bằng lái xe chỉ được làm mới sau vài năm. Được thực hiện bởi con người và được thực hiện tự động: nếu được thực hiện bởi con người thì dữ liệu sinh trắc sẽ được thu thập khi có sự hướng dẫn, quản lý bởi một người. Môi trường điều hành chuẩn hay phi chuẩn: Môi trường điều hành là chuẩn nếu hệ thống được hoạt động trong môi trường được điều khiển ( các yếu tố nhiệt độ, độ ẩm…) Là ứng dụng công cộng hay ứng dụng kín: nếu là ứng dụng kín thì người sử dụng hệ thống sinh trắc là khách hàng hay nhân viên của tổ chức triển khai hệ thống; Ứng dụng mở và ứng dụng đóng: Ứng dụng mở sử dụng chung các mẫu sinh trắc của một người với các ứng dụng khác, còn ứng dụng đóng phải sử dụng các mẫu sinh trắc thích hợp dành riêng 1.4.So sánh các đặc trưng sinh trắc: Một đặc tính sinh học hoặc hành vi của con người có thể được sử dụng như là một đặc trưng sinh trắc trong nhận dạng một người nếu nó có các yêu cầu sau: Tính phổ biến: mọi người đều có đặc trưng sinh trắc này Tính phân biệt: hai người khác nhau thì đặc trưng sinh trắc này phải khác nhau Tính ổn định: đặc trưng sinh trắc này không thay đổi theo từng giai đoạn thời gian ( tương ứng với hạng mục đối sánh nhất định ) Tính thu thập: nghĩa là đặc trưng này có thể đo được và lượng hóa Hiệu năng: khả năng nhận dạng chính xác, tốc độ nhận dạng; các tài nguyên cần thiết để đạt được tốc độ và độ chính xác mong muốn; các nhân tố môi trường và hoạt động ảnh hưởng đến tốc độ và độ chính xác trong nhận dạng Tính chấp nhận: mọi người vui lòng chấp nhận các đặc trưng sinh trắc trong đời sống hàng ngày của họ Khả năng phá hoại: là mức độ khó hay dễ để đánh lừa hệ thống bởi các phương pháp lừa dối. Sau đây là một số đặc trưng sinh trắc thông dụng: DNA, tai, mặt, dáng đi, đồ hình bàn tay và ngón tay, mống mắt…. Hình 1.2: Một số đặc trưng sinh trắc: a) gương mặt, b)vân tay, c) đồ hình bàn tay d)Mống mắt, e)võng mạc f)chữ kí, g) tiếng nói 1.5.Các loại lỗi của hệ thống sinh trắc: Đối sánh trong một hệ thống nhận dạng vân tay dựa vào điểm đối sánh s( không mất tính tổng quát, chúng ta giả sử giá trị của điểm này nằm trong [0,1] ). Điểm đối sánh được dùng để lượng hóa độ tương tự giữa biểu diễn của đầu vào và biểu diễn của mẫu cơ sở dữ liệu. Điểm này càng có giá trị gần 1 thì khả năng cả hai vân tay đều của cùng một ngón tay càng cao, ngược lại điểm này càng có giá trị gần 0 thì khả năng hai vân tay là của hai ngón tay khác nhau càng lớn. Quyết định của hệ thống được điều khiển bởi ngưỡng t. Với điểm s của hai vân tay: nếu s t: kết luận là cặp so khớp ( nghĩa là hai vân tay của cùng một ngón tay ) nếu s t: kết luận là cặp không so khớp ( nghĩa là hai vân tay đến từ hai ngón tay khác nhau ) Một hệ thống kiểm tra chấp nhận hai lỗi sau đây: Kiểm tra các số đo sinh trắc từ hai ngón tay khác nhau với kết quả là của cùng một ngón tay ( ta gọi là so khớp sai ) Kiểm tra các số đo sinh trắc của cùng một ngón tay với kết quả là của hai ngón tay khác nhau ( ta gọi là không- so khớp sai ) Hai lỗi trên tương ứng còn được gọi là chấp nhận sai và từ chối sai. Bởi vì kẻ giả mạo có thể được chấp nhận sử dụng thiết bị hay hệ thống…nếu có sự so khớp sai, và người có đủ thẩm quyền đăng nhập, sử dụng thiết bị hay hệ thống lại bị từ chối nếu xảy ra sự không so khớp sai. Chúng ta lượng hóa hai lỗi trên bằng các đại lượng: tỉ lệ chấp nhận sai và tỉ lệ từ chối sai. Chúng ta sẽ đi sâu hơn vào các lỗi trong những hệ thống kiểm tra và trong các hệ thống nhận dạng 1.5.1.Các lỗi của hệ thống kiểm tra: Phát biểu bài toán: Kí hiệu T là mẫu sinh trắc của một người đã được lưu trữ, I là biểu diễn sinh trắc đầu vào cần được kiểm tra. Các giả thuyết đặt ra là: H0: I T, đầu vào và mẫu không của cùng một người H1: I = T, đầu vào và mẫu của cùng một người Tương ứng với các giả thuyết là các kết luận: D0: người nay không có mẫu sinh trắc được lưu trữ trong hệ thống D1: người này đã có mẫu sinh trắc được lưu trữ trong cơ sở dữ liệu Đối sánh trong kiểm tra T và I sử dụng độ tương tự s(T,I). Nếu s nhỏ hơn ngưỡng t thì kết quả là D0, nếu s 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, chúng ta định nghĩa hai loại lỗi trong một hệ thống kiểm tra: 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 ) Khi đó, 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á tính chính xác của một hệ thống sinh trắc chúng ta phải thống kê các điểm đối sánh s của các cặp vân tay của cùng một ngón tay( phân bố p ( s|H1 đúng )-thường được gọi là phân bố chân chính ) và điểm đối sánh s của các cặp vân tay từ hai ngón tay khác nhau( phân bố p(s|H0 sai)-thường được gọi là phân bố giả mạo ) FNMR = p ( s|H1 đúng )ds FMR = p ( s | H0 đúng )ds Hình 1.3: FMR và FNMR với một ngưỡng t thể hiện phân bố chân chính và phân bố giả mạo. Trong hình vẽ FMR là phần trăm các cặp giả mạo 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 chính có điểm đối sánh nhỏ hơn t. Thực tế, cả FMR và FNMR đều là hàm của ngưỡng hệ thống t nên chúng ta có thể viết chú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 để cho hệ thống an toàn hơn thì FNMR(t) sẽ tăng tương ứng. Người thiết kế hệ thống kiểm tra 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, vì vậy 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. Đường cong này biểu diễn các giá trị FNMR và FMR ở theo ngưỡng hệ thống t. 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á tính chính xác của một hệ thống kiểm tra. Tỉ lệ lỗi cân bằng( EER): là tỉ lệ lỗi tại ngưỡng t mà FMR(t) = FNMR(t). Trong thực tế, do chúng ta có một số hữu hạn các cặp vân để so sánh và do sự lượng tự hóa giá trị nên EER không tồn tại. Vì vậy thay vì đưa ra một giá trị đơn duy nhất, người ta đưa ra một khoảng.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 hoạt động ở ngưỡng tương ứng với EER mà hoạt động ở các ngưỡng có FMR thấp 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 thu thập(FTC): là tỉ lệ phần trăm mà thiết bị không thể tự động thu thập đặc trưng sinh trắc khi đặc trưng sinh trắc được đưa vào bộ cảm biến Tỉ lệ thất bại trong kiểm tra ( FTE ) là tỉ lệ phần trăm mà người dùng không được xử lý bởi hệ thống Tỉ lệ thất bại trong đối sánh ( FTM ) là tỉ lệ biểu diễn đầu vào không thể được xử lý hoặc đối sánh với một mẫu sinh trắc có giá trị, bởi các biểu diễn sinh trắc không đủ chất lượng Hình 1.4: Đánh giá thuật toán kiểm tra vân tay trong cuộc thi nhận dạng vân tay 2002 (FVC2002) a) các phân bố chân chính và giả mạo được tính trên 2800 cặp chân chính và 4950 cặp giả mạo 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) error FMR(t) FNMR(t) ZeroFNMR ZeroFMR Hình 1.5: Một ví dụ của đồ thị FMR ( t ) và FNMR ( t ), với các điểm tương ứng là EER, ZeroFNMR và ZeroFMR EER 1.5.2.Các loại lỗi của hệ thống nhận dạng: Từ định nghĩa các loại lỗi trong một hệ thống kiểm tra, chúng ta mở rộng để định nghĩa các loại lỗi trong một hệ thống nhận dạng. Giả sử hệ thống không dùng các cơ chế đánh chỉ số/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 vân tay ), và mỗi người chỉ có một mẫu vân tay được lưu trữ. Kí hiệu FNMRN và FMRN tương ứng 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 FMRN = 1 – ( 1-FMR )N : trong biểu thức này ( 1 – FMR ) là xác suất không xảy ra đối sánh sai với một mẫu vân tay và ( 1 – FMR )N là xác suất không xảy ra đối sánh sai với toàn bộ cơ sở dữ liệu mẫu. Nếu FMR nhỏ thì FMRN N.FMR, ta có thể nói tỉ lệ đối sánh sai tăng tuyến tính với kích thước cơ sở dữ liệu mẫu Trong trường hợp cơ sở dữ liệu mẫu được phân loại và chỉ số hóa, thì trong quá trình nhận dạng chỉ có một phần cơ sở dữ liệu được kiểm tra. Khi đó: FNMRN = RER + ( 1 – RER ).FNMR trong đó RER ( tỉ lệ lỗi truy tìm ) là xác suất mẫu vân tay cần tìm trong cơ sở dữ liệu bị bỏ qua do cơ chế 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 được tìm kiếm trong cơ sở dữ liệu mẫu trong quá trình nhận dạng CHƯƠNG 2. PHÂN TÍCH VÀ BIỀU DIỄN VÂN TAY 2.1.Phân tích cấu trúc vân tay: Khi ấn ngón tay vào một bề mặt trơn, một vân tay được sao chép lại từ lớp biểu bì da. Cấu trúc dễ nhận thấy nhất của vân tay là các vân lồi và vân lõm; trong ảnh vân tay, vân lồi có màu tối trong khi vân lõm có màu sáng. Vân lồi có độ rộng từ 100m đến 300m. Độ rộng của một cặp vân lỗi lõm cạnh nhau là 500m. 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, khi da mọc lại sẽ khôi phục lại đúng cấu trúc này. Vân lồi và vân lõm thường chạy song song với nhau; chúng có thể rẽ thành hai nhánh, hoặc kết thúc. Ở 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 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. 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 nhân. Henrry (1900 ) đã định nghĩa điểm nhân 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 nhân 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 nhân 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 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. Ở mức độ cục bộ, chúng ta tìm kiếm các đặc tính quan trọng, gọi là các chi tiết. Các chi tiết mô tả cách mà các vân bị đứt quãng. Ví dụ vân có thể đi tới điểm kết thúc, hay rẽ thành hai nhánh…. Ngài Francis Galton ( 1822-1911 ) là người đầu tiên phân loại chi tiết và khẳng định chúng không thay đổi trong suốt cuộc đời một cá nhân. Viện các chuẩn quốc gia Mĩ đề nghị phân loại chi tiết 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 chi tiết của cục điều tra liên bang Mĩ chỉ có hai loại chi tiết là điểm kết thúc và điểm rẽ hai. Mỗi chi tiết được đặc trưng bởi phân lớp, hệ tọa độ xy , góc tạo bởi tiếp tuyến của đường vân tại chi tiết và trục ngang. 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ản điểm kết thúc xuất hiện như là điểm rẽ hai và ngược lại. Ở các ảnh vân tay có độ phân giải cao ( trên 1000dpi), chúng ta có thể xác định được các lỗ chân lông ( kích thước từ 60m. đến 250m). Thông tin của lỗ chân lông ( số lượng, vị trí, hình dạng ) có sự khác biệt rất cao, nhưng ít kĩ thuật đối sánh sử dụng các lỗ chân lông bởi vì để xử lý hình ảnh các lỗ chân lông đòi hỏi các ảnh có độ phân giải cao và chất lượng tốt. 2.2.Biểu diễn hình ảnh vân tay. Hầu hết các thuật toán phân loại và nhận dạng vân tay yêu cầu giai đoạn trích chọn đặc trưng để xác định các đặc trưng nổi bật. Hình ảnh vân tay thường được biểu diễn như là một bề mặt hai chiều. Kí hiệu I là ảnh vân tay cấp xám với cấp xám g. I[x,y] là cấp xám của điểm ảnh [x,y]. Kí hiệu z = S(x,y) là bề mặt rời rạc tương ứng với ảnh I: S(x,y) = I[x,y]. Bằng cách chọn các điểm ảnh màu sáng có cấp xám là 0, và các điểm ảnh có màu tối có cấp xám là g-1, thì các đường vân ( xuất hiện có màu tối trong I ) tương ứng với bề mặt vân lồi còn khoảng không gian giữa các vân lồi ( có màu sáng ) tương ứng là bề mặt vân lõm. Hình 2.1: Bề mặt S của một vùng vân tay. 2.3.Ước lượng hướng vân cục bộ Một đặc tính quan trọng của vân tay là hướng vân cục bộ tại các vị trí trong ảnh vân tay. Hướng vân cục bộ tại [x,y] là góc xy tạo bởi trục ngang và đường thẳng nối qua một số điểm láng giềng của [x,y]. Do các đường vân không được định hướng, xy là góc vô hướng nằm trong đoạn . Thay vì tính hướng vân cục bộ tại mỗi điểm ảnh, hầu hết các phương pháp trích chọn đặc trưng và xử lý vân tay ước lượng hướng vân cục bộ tại các vị trí rời rạc ( để làm giảm gánh nặng tính toán và cho phép thực hiện các ước lượng còn lại nhờ phép nội suy ). Ảnh hướng vân tay, là một ma trận D mà mỗi phần tử mang thông tin về hướng vân cục bộ của các đường vân. Mỗi phần tử ij, tương ứng với nốt [i,j] trong lưới ô vuông chứa điểm ảnh [xi, yj ], biểu diễn hướng trung bìnhcủa đường vân trong lân cận của [xi, yj ]. Người ta thêm vào một giá trị rij liên kết với ij để biểu diễn tính tin cậy ( hay toàn vẹn ) của hướng. Giá trị của rij là nhỏ ở các vùng bị nhiễu và hư hại, có giá trị lớn ở các vùng có chất lượng tốt. Hình 2.1:Một ảnh vân hướng vân tay được tính trên một lưới 16x16. Mỗi phần tử là hướng cục bộ của đường vân; chiều dài tương ứng với tính tin cậy Để tính hướng vân cục bộ, phương pháp đơn giản nhất là tính toán gradient trên ảnh vân tay.Gradient ( xi, yj ) ở điểm [ xi, yj ] của I là một véc tơ hai chiều [x ( xi, yj ), y ( xi, yj ) ] trong đó thành phần x và y là đạo hàm theo x và y của I tại điểm [ xi,, yj ] tương ứng với hướng x và y. Góc pha gradient biểu thị hướng thay đổi mật độ điểm ảnh lớn nhất. Vì vậy, hướng θij của một góc giả định qua vùng có tâm tại [ xi,, yj ] là trực giao với góc pha gradient tại [ xi,, yj ] . Ratha, Chen và Jain ( 1995) đã tính hướng vân cục bộ θij bằng cách kết hợp nhiều ước lượng gradient trong một cửa sổ 17x17 có tâm tại [ xi,, yj ] . Trong đó là các thành phần gradient theo hướng x, và y được tính qua mặt nạ Sobel. 2.4.Ước lượng tần suất vân cục bộ Tần suất vân cục bộ ( hay mật độ ) fxy tại điểm [ x, y ] là nghịch đảo của số vân trên một đơn vị chiều dài dọc theo dọc theo đoạn có tâm tại [ x, y ] và vuông góc với hướng vân cục bộ θxy. Một ảnh tần suất F, tương tự với ảnh hướng D, có thể được xác định nếu tần suất được ước lượng ở các vị trí rời rạc và được sắp xếp vào trong một ma trận. Tần suất vân cục bộ thay đổi trên các ngón tay khác nhau, và thay đổi trên các vùng khác nhau của cùng một vân tay. Hong, Wan và Jain ( 1998 ) ước lượng tần suất vân cục bộ bằng cách tính trung bình số điểm ảnh giữa hai đỉnh liên tiếp của mức xám dọc theo hướng thông thường với hướng vân cục bộ. Cho mục đích này, bề mặt S tương ứng với vân tay được phân chia bằng một cặp đường song song với trục z và vuông góc với hướng vân cục bộ. Tần suất fxy tại điểm [ xi, yj ] được tính như sau: Một cửa sổ có hướng 32 x 16 có tâm tại [ xi , yj ] được chọn trong hệ tọa độ vân ( nghĩa là quay để căn chỉnh trục y với hướng vân cục bộ ) chữ kí x ( x-signature ) của mức xám được nhận được bởi tích lũy, cho mỗi cột x, những mức xám của điểm ảnh tương ứng trong cửa sổ hướng. Đây là sắp xếp trung bình để tạo cho mặt nghiêng mức xám mượt hơn và ngăn ngừa các đỉnh vân bị mờ do các đứt gãy của vân fij là nghịch đảo của khoảng cách trung bình giữa hai đỉnh liên tiếp của x-signature Phương pháp rất đơn giản và có thể thực hiện nhanh chóng. Nhưng, khó khăn của phương pháp này phát hiện một cách tin tưởng các đỉnh liên tiếp của các mức xám trong miền không gian của các ảnh vân tay bị nhiễu. Trong trường hợp này, các tác giả đề nghị sử dụng phép nội suy và lọc thông thấp Jiang ( 2000 ) cũng tính tần suất vân cục bộ nhờ vào x-signatures. Dù sao, thay vì đo khoảng cách trong không gian, ông sử dụng kĩ thuật phổ có thứ tự cao gọi là mix-spectrum. Các mẫu vân trong một hình ảnh vân tay là các tín hiệu nhiễu tuần hoàn; khi chúng chệch hướng với hình sin thuần tuý, năng lượng của chúng được phân phối theo tần số và có tính điều hoà. Kĩ thuật mix-spectrum tăng cường tần số cơ bản của tín hiệu bằng cách dùng thông tin chứa trong phần điều hoà thứ hai và thứ ba. Trong phương pháp đưa ra bởi Maia và Maltoni ( 1998a ), mẫu vân một cách cục bộ được mô hình như là một bề mặt hình sin, và định lý thay đổi được sử dụng để ước lượng tần sô không xác định. Sự thay đổi V của hàm h trong khoảng [ x1, x2 là tổng của thay đổi theo chiều dọc trong h : nếu hàm h tuần hoàn trong khoảng [x1, x2 ] hoặc biên độ thay đổi