Đề tài 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 trong khoảng [ x1, x2] là nhỏ, sự biến thiên có thể được mô tả như là hàm của biên độ trung bình αm và tần số trung bình f ( xem hình3.12 ) V(h) = ( x2 – x1 ). 2αm..f Do vậy, tần số không biết được ước lượng như sau: Maio và Maltoni ( 1998a ) đề nghị một phương pháp thực hành dựa trên định lý trên. Sự biến thiên và biên độ trung bình của một mẫu vân hai chiều được ước lượng từ phần dẫn xuất đầu tiên và thứ hai và tần suất vân cục bộ được tính từ biểu thức (3). Kovacs-Vajina và Frazzoni ( 2000 ) đã đề nghị thủ tục hai bước: đầu tiên, khoảng cách vân trung bình được ước lượng cho từng khối ảnh con 64x64 có chất lượng đủ và thông tin này được lan truyền, theo đẳng thức truyền tin, tới những miền còn lại. Hai phương pháp được xem xét trong bước đầu tiên: hình học và quang phổ. Với phương pháp hình học, những điểm trung tâm của vân được tính trên lưới chính quy và những khoảng cách giữa các vân được đo trên đường thẳng nối qua những điểm này. Không giống như phương pháp chữ kí –x, các khoảng cách được đo trực tiếp trên ảnh hai chiều; vài ước lượng trên cùng một khối ảnh được thực hiện để khắc phục các nhiễu.Phương pháp thứ hai dựa trên việc tìm kiếm các phổ năng lượng Fourier của mỗi khối con. Ở đây, phương pháp thực hiện trên các tín hiệu hai chiều. Sự không thay đổi tương ứng với các hướng vân cục bộ được nhận được bằng việc tìm kiếm lớn nhất xung quanh: trong thực tế, tất cả các thành phần có cùng khoảng cách từ bắt đầu thể hiện cùng tần suất. 2.5.Tăng cường ảnh: Hiệu quả sử dụng của các thuật toán trích chọn đặc tính và các kĩ thuật nhận dạng vân tay khác phụ thuộc rất lớn vào chất lượng của ảnh vân tay đầu vào. Trong trường hợp ảnh vân tay, vân lồi và vân lõm thay thế nhau và hướng theo một hướng cố định. Trong những tình huống thế này, các vân có thể dễ dàng được phát hiện và các chi tiết có thể xác định một cách chính xác trên ảnh. Hình 3.23a thể hiện một ví dụ về ảnh vân tay chất lượng tốt Nhưng trong thực tế, do điều kiện da ( như khô hay ướt, bị cắt… ), nhiễu cảm biến, ấn vân tay không đúng, và các ngón tay chất lượng thấp, một phần không nhỏ các ảnh vân tay ( khoảng 10% ) là có chất lượng thấp như trong hình 3.23b và 3.23c. Hình 2.2: a) ảnh vân tay chất lượng tốt, b) vân tay với các nếp đứt, gãy c) Vân tay có rất nhiều nhiễu Trong nhiều trường hợp, một ảnh vân tay chứa nhiều vùng gồm có cả chất lượng tốt, trung bình và xấu .Nói chung, có vài dạng mất giá trị liên hệ với các ảnh vân tay: các vân không liên tục,có vài nếp đứt các vân song song không tách biệt rõ ràng do tồn tại của nhiễu liên kết các vân song song, khiến chúng tách biệt kém bị cắt, có nếp gấp, hay thâm sẹo Ba dạng bị vân mất giá trị này làm cho việc trích chọn đặc tính cực kì khó khăn. Chúng dẫn tới các vấn đề sau trong việc trích chọn đặc tính: Trích chọn các chi tiết sai lệch Bỏ qua các chi tiết đúng Gây lỗi về hướng và vị trí của chi tiết Để bảo đảm hiệu quả tốt trong các thuật toán trích chọn chi tiết trên các ảnh vân tay chất lượng kém, cần một thuật toán tăng cường để nâng cao sự rõ ràng trong cấu trúc vân. Một chuyên gia vân tay thường có thể nhận dạng chính xác các chi tiết bằng cách sử dụng nhiều manh mối nhìn được như hướng vân tay, tính liên tục của vân, xu hướng vân…Trong lý thuyết, có thể phát triển một thuật toán tăng cường sử dụng các manh mối nhìn được này để cải thiện chất lượng hình ảnh. Nói chung, với một ảnh vân tay cho trước, các cùng vân tay đã được phân đoạn có thể chia vào ba hạng mục: Vùng được định nghĩa tốt: các vân được phân biệt rõ ràng với các vân khác Vùng có khả năng phục hồi: các vân bị hư hỏng bởi các đường đứt gãy nhỏ, thâm sẹo… nhưng chúng vẫn có khả năng nhìn được và các vùng xung quanh cung cấp thông tin đủ để khôi phục cấu trúc ban đầu của chúng Vùng không thể phục hồi, nơi các vân bị hư hại bởi các nhiễu nghiêm trọng, không có vân nào nhìn thấy được và các vùng xung quanh không cho phép chúng được xây dựng lại Các vùng chất lượng tốt, có thể phục hồi và không thể phục hồi có thể được nhận dạng qua vài tiêu chuẩn: độ tương phản, tính đầy đủ của hướng, tần suất vân, và các đặc tính cục bộ khác có thể kết hợp để định nghĩa chỉ số chất lượng. Mục đích của một thuật toán tăng cường là để cải thiện tính rõ ràng của các cấu trúc vân trong các vùng có khả năng khôi phục và đánh dấu các vùng không thể khôi phục vì quá nhiễu cho các xử lý tiếp theo. Thông thường,đầu vào của thuật toán tăng cường là một ảnh cấp xám. Đầu ra có thể là ảnh cấp xám hay một ảnh đen trắng, tùy thuộc vào thuật toán. Nhiều kết quả khi sử dụng các phương pháp dàn trải tương phản, thực thi biểu đồ, chuẩn hóa ( Hong, Wan và Jain, 1998 ) và lọc Winer ( Greenberrg et al, 2000 ) đã thể hiện hiệu quả như là bước xử lý đầu tiên trong một thuật toán tăng cường ảnh vân tay phức tạp hơn Phương pháp chuẩn hóa sử dụng bởi Hong, Wan, và Jain ( 1998 ) quyết định giá trị cường độ của mỗi điểm ảnh như: Trong đó m và v là kì vọng và phương sai ảnh, còn mo và vo là kì vọng và phương sai mong muốn sau khi chuẩn hóa. Quá trình chuẩn hóa được thực hiện trên từng điểm ảnh ( giá trị của mỗi điểm ảnh chỉ phụ thuộc vào các giá trị trước và một vài tham số toàn cục ) và không làm thay đổi cấu trúc vân. Cụ thể hơn, chuẩn hóa không làm phủ đầy các đứt gãy nhỏ, các lỗ, hay tách các vân song song bị chạm vào nhau. Hình 2.3 thể hiện một ví dụ: Hình 2.3: Một ví dụ về chuẩn hoá với m0 = 50 và v0 = 200 Hong, Wan và Jain ( 1998 ) đưa ra một phương pháp hiệu quả dựa trên bộ lọc Gabor. Bộ lọc Gabor có các thuộc tính chọn tần suất và chọn hướng và có độ phân giải tùy chọn trong cả miền không gian và miền tần số ( Daugman ( 1995 ) và Jain và Farrokhnia ( 1991 ) ). Như đã trong hình 3.28, một bộ lọc Gabor được định nghĩa bởi một sóng phẳng hình sin ( đại lượng thứ hai của biểu thức (5 ) hẹp lại bởi một Gauss ( thành phần đầu của (5) ). Một bộ lọc đối xứng hai chiều Gabor có dạng sau: Trong đó θ là hướng của bộ lọc, và [xθ, yθ] là ảnh của [x,y] sau khi quay quanh trục Cartesian một góc ( 90o – θ ): trong biểu thức ở trên, f là tần suất của sóng phẳng hình sin, σx , σy là độ lệch chuẩn Gauss tương ứng dọc theo trục x và trục y. Hình 2.4 :Biểu diễn đồ họa của bộ lọc Gabor xác định bởi tham số Để áp dụng các bộ lọc Gabor tới một ảnh,cần xác định bốn tham số ( θ, f, σx, σy ) . Tần suất của bộ lọc hoàn toàn được quyết định bởi tần suất vân cục bộ và hướng của bộ lọc được quyết định bởi hướng vân cục bộ. Việc chọn các giá trị σx và σy có thể hoán đổi cho nhau. Nếu chọn giá trị lớn thì bộ lọc sẽ chịu nhiễu nhiều hơn, nhưng lại tạo ra sự nhầm lẫn giữa vân lồi và vân lõm. Ngược lại nếu chọn giá trị nhỏ, thì các bộ lọc ít nhầm lần giữa vân lồi và vân lõm nhưng sau đó chúng sẽ ít hiệu quả trong việc loại bỏ các nhiễu. Trong thực tế, từ hàmModulation Transfer Function ( MFT ) của bộ lọc Gabor, có thể nhận thấy tăng σx , σy làm giảm dải thông của bộ lọc và ngược lại. Dựa trên dữ liệu kinh nghiệm, Hong, Wan và Jain đặt σx = σy = 4. Để làm nhanh quá trình cải thiện, thay vì tính bộ lọc ngữ cảnh thích hợp nhất cho mỗi điểm ảnh “on the fly”, một tập { gij ( x, y )| I = 1…no, j = 1…nf } của các bộ lọc được tạo ra và lưu trữ từ trước, trong đó no là số các hướng rời rạc { θi| I = 1…no } và nf là số các tần suất rời rạc { fj | j = 1…nf }. Sau đó mỗi điểm ảnh [x, y] của ảnh được quấn lại, trong miền không gian, với bộ lọc gij ( x, y ), với θi là hướng được rời rạc hóa gần nhất với θxy và fj là tần số được rời rạc hóa gần nhất với fxy. Hình 3.29 thể hiện một ví dụ về tập bộ lọc cho n0 = 8 và nf = 3. Hình 3.30 trình bày ứng dụng Gabor dựa trên lọc ngữ cảnh trên các ảnh chất lượng trung bình và thấp: Hình 2.5: Một biểu diễn đồ họa trong một nhóm 24 bộ lọc Gabor ( n0=8 và n1=5) với =4 Greenberg et al ( 2000 ) đã lưu ý rằng: bằng cách giảm giá trị của σx tương ứng với σy, quá trình lọc tạo ra vài vân sai và dễ bị nhiễu. Trong thực hành, giảm σx gây kết quả tăng dải thông tần suất, độc lập với dải thông góc không đổi; điều này cho phép bộ lọc bỏ qua tốt hơn các lỗi trong ước lượng tần suất cục bộ. Một cách tương tự, giảm σy để tăng dải thông góc như đã chỉ ra bởi Sherlok, Monro, và Millard ( 1994 ). Phương pháp của họ tăng dải thông góc gần với các vùng đơn mà các vân được đặc tính hóa bởi đường cong cao hơn và hướng thay đổi nhanh. Hình 2.6: Các ví dụ của tăng cường ảnh vân tay dựa vào lọc Gabor. Ở bên phải các vùng có khả năng khôi phục đã được tăng cường Đầu ra của một ảnh chuẩn hóa có thể là một ảnh cấp xám, gần ảnh hai cấp, hay là một ảnh nhị phân, và nói chung phụ thuộc vào các tham số được chọn, khi chọn tập các bộ lọc thích hợp, chỉnh sửa các tham số. Lưu ý rằng, mục đích không phải là cung cấp một sự xuất hiện tốt bề ngoài của ảnh nhưng là để làm thuận tiện hơn cho các bước trích họng đặc tính thành công. Nếu các bộ lọc được chỉnh sửa để làm tăng độ tương phản và khử các nhiễu, ước lược điều kiện cục bộ ( hướng và tần suất ) có thể lỗi trên các vùng chất lượng thấp, và qúa trình lọc chỉ cung cấp các cấu trúc sai lầm ( Jiang, 2000 ). Ví dụ, một ứng dụng lặp dùng bộ lọc Gabor đã được sử dụng bởi Cappeli, Maio, và Maltoni ( 2000b ) để tạo ra một mẫu vân tay tổng hợp; trong trường hợp này, các bộ lọc sinh ra các mẫu vân hoàn toàn không tồn tại trong thực tế. Nhu cầu của một sự chuẩn hóa hiệu quả rất quan trọng trong các ảnh vân tay chất lượng thấp, chỉ có các vùng có khả năng khôi phục mang thông tin cần thiết cho đối sánh. Nói một cách khác, tính toán thông tin cục bộ với tính tin cậy đầy đủ từ các ảnh vân tay chất lượng thấp là một thách thức và rủi ro cao. Để vượt qua vấn đề này, Kamei và Mizoguchi ( 1995 ), Hong ( 1996 ) và Bernard ( 2002 ) đã đề nghị áp dụng tất cả tập bộ lọc cho trước tại mỗi điểm của ảnh. Một bộ tuyển áp sau đó được chọn có đáp ứng tốt nhất trong tất cả các đáp ứng lọc. Trong phương pháp của Kamei và Mizoguchi ( 1995 ), quá trình chọn được thực hiện bằng cách giảm thiểu hóa hàm năng lượng có các tham số yêu cầu hướng và tần suất được làm mượt. Dù sao, không như các phương pháp dựa Gabor khác, thông tin từ phần thực và phần ảo của bộ lọc Gabor còn được sử dụng cho chuẩn hóa ảnh cuối cùng. Nhưng các phương pháp này nhân chập một ảnh với một lượng lớn các bộ lọc nên rất đắt, vì vậy không tìm thấy ứng dụng này trong các hệ thống trực tuyến trong thực tế. 2.6. Phát hiện chi tiết. Hầu hết các hệ thống tự động so sánh các vân tay dựa trên đối sánh chi tiết; vì vậy việc trích chọn chi tiết đáng tin cậy là một nhiệm vụ cực kì quan trọng, nhiều nghiên cứu đã được tiến hành theo hướng này. Dù các phương pháp khá khác nhau nhưng hầu hết chúng đều yêu cầu ảnh cấp xám vân tay được chuyển vào ảnh nhị phân. Trong các bước chuẩn hóa đã chuẩn bị một số giai đoạn để làm thuận tiện quá trình nhị phân hóa về sau.Một vài thuật toán chuẩn hóa cung cấp đầu ra là ảnh nhị phân, vì vậy sự phân biệt giữa chuẩn hóa và nhị phân hóa đôi khi bị xóa nhòa. Ảnh nhị phân nhận được bởi quá trình nhị phân hóa thường được qua giai đoạn làm mảnh làm cho độ dày của đường vân giảm xuống một điểm ảnh ( hình 3.31 ). Cuối cùng qua quá trình quét ảnh cho phép phát hiện các điểm ảnh tương ứng với các chi tiết. Hình 2.7: a)ảnh cấp xám của một vân tay, b) ảnh nhận được khi nhị phân hóa ảnh a), c)ảnh nhận được khi làm mảnh ảnh b). Vài tác giả đưa ra các phương pháp trích chọn chi tiết làm việc trực tiếp trên các ảnh cấp xám mà không cần nhị phân hóa và làm mảnh. Lựa chọn này được đưa ra do các điều kiện sau: Tập các thông tin quan trọng có thể bị mất trong quá trình nhị phân hóa Nhị phân hóa và làm mảnh rất mất thời gian; Làm mảnh có thể đưa ra một lượng lớn các chi tiết sai lệch nếu thiếu bước chuẩn hóa, hầu hết các kĩ thuật nhị phân hóa không cung cấp các kết quả tốt khi áp dụng với các ảnh chất lượng thấp. Phương pháp dựa nhị phân hóa Vấn đề chung của nhị phân hóa được nghiên cứu rộng rãi trong xử lý ảnh và nhận dạng mẫu. Phương pháp dễ dàng nhất sử dụng ngưỡng toàn cục t và được thực hiện bằng cách thiết lập các điểm ảnh có cấp xám nhỏ hơn t về 0 và các điểm ảnh còn lại về 1. Nói chung, các phần khác nhau của ảnh có thể được đặc tính hóa bởi độ tương phản và cường độ khác nhau, vì vậy một ngưỡng đơn là không đủ để nhị phân hóa chính xác. Vì lí do này, kĩ thuật ngưỡng cục bộ thay đổi t một các cục bộ, bằng cách điều chỉnh giá trị của nó theo cường độ cục bộ trung bình. Trong trường hợp ảnh vân tay chất lượng thấp, phương pháp ngưỡng cục bộ không phải lúc nào cũng bảo đảm một kết quả chấp nhận được, và các giải pháp đặc biệt là cần thiết. Với mục đích cải thiện chất lượng ảnh nhị phân, vài nhà nghiên cứu giới thiệu các kĩ thuật chính quy phủ đầy các lỗ, lọa bỏ các đứt gãy nhỏ, lọa bỏ các cầu giữa các vân. Coetzee và Botha ( 1993 ) xác định các lỗ và kẽ hở bằng cách theo dõi các đường vân từ các cửa sổ điều hợp và loại bỏ chúng bằng cách sử dụng thuật toán màu-blob. Hung ( 1993 ) sử dụng kĩ thuật lọc điều hợp để cân bằng độ rộng vân. Một khi ảnh xương đã nhận được, một bước quét ảnh đơn giản cho phép phát hiện các điểm ảnh tương ứng với các chi tiết: trong thực tế các điểm ảnh tương ứng với các chi tiết được đặc tính hóa bằng số điểm đi qua. Số điểm đi qua cn( p ) của một điểm ảnh p trong ảnh nhị phân được xác định bằng một phần hai tổng các sai khác giữa các cặp điểm ảnh trong 8 lân cận của p Trong đó p0, p1…p7 là các điểm ảnh láng giềng lân cận của điểm ảnh p và val( p ) thuộc { 0, 1 } là giá trị của điểm ảnh. Điểm p là: là điểm vân trung gian nếu cn(p) = 2 là điểm kết thúc nếu cn(p) = 1; là các chi tiết phức tạp hơn ( điểm rẽ nhánh, điểm giao cắt.. ) nếu cn(p) >=3; Hình 2.8 thể hiện hai ví dụ của quá trình trích chọn đặc tính từ ảnh nhị phân Hình: Các ví dụ về phát hiện chi tiết trên xương. Các vòng tròn màu trắng và các hộp trắng tương ứng là điểm kết thúc và điểm rẽ hai; Các vòng tròn màu đen và các hộp màu đen tương ứng là các chi tiết đã được lọc 2.7.Lọc chi tiết Để phát hiện các chi tiết sai làm ảnh hưởng đến các ảnh vân tay nhị phân được làm mảnh, có thể sử dụng vài luật cấu trúc đơn giản. Xiao ( 1991b) xác định hầu hết các cấu trúc chi tiết sai và đưa ra phương pháp loại bỏ chúng. Thuật toán sử dụng dựa trên các luật, yêu cầu các đặc tính số học liên quan đến các chi tiết: chiều dài các vân liên quan ( s ), góc chi tiết, và số các chi tiết đối diện gần kề trong lân cận. Hình2.9: Các cấu trúc sai cơ bản ( hàng đầu tiên ) và cấu trúc sau khi sửa lỗi ( hàng thứ hai ) Farina, Kovacs-Vajina, và Leone ( 1999 ) đã đưa ra vài luật và thuật toán tiền xử lý chi tiết. Các cầu bị loại bỏ khi nhìn nhận chúng trong một điểm chẻ hai sai, chỉ có hai nhánh được căn chỉnh, còn nhánh thứ ba thường vuông góc với hai nhánh còn lại Các vân quá ngắn được loại bỏ dựa vào khi so sánh chiều dài vân với khoảng cách trung bình giữa các vân Các điểm kết thúc và rẽ hai được kiểm tra: chúng được loại bỏ nếu không thỏa mãn tính hình học topo Hình 2.10: Tiền xử lý chi tiết theo phương pháp của Farina, Kovacs-vajina, và Leone( 1999). Ở ảnh bên phải, hầu hết các chi tiết sai đã bị loại bỏ từ ảnh ảnh vân bên trái CHƯƠNG 3:ĐỐI SÁNH VÂN TAY 3.1.Đặt vấn đề Một thuật toán đối sánh vân tay so sánh hai vân tay cho trước và trả về độ tương tự ( không làm mất tính tổng quát, có giá trị giữa 0 và 1 ) hoặc một quyết định hai ngôi ( khớp hoặc không khớp ). “Chỉ một vài thuật toán hoạt động trực tiếp trên ảnh vân cấp xám; hầu hết chúng yêu cầu một biểu diễn vân trung gian được dẫn xuất qua gia đoạn trích chọn đặc trưng (đề cập đến ở chương 3 ). Không làm mất tính tổng quát, từ đây về sau chúng ta kí hiệu biểu diễn của vân tay có được qua quá trình tuyển chọn như là mẫu ( T ) và biểu diễn của vân tay được đối sánh như là đầu vào ( I ). Trong trường hợp không có giai đoạn trích chọn đặc trưng, biểu diễn vân tay đồng nhất với chính ảnh cấp xám vân tay.Chúng ta kí hiệu cả ảnh vân tay và các vector đặc trưng ảnh ( như các chi tiết ) là T và I Trích chọn đặc trưng vân tay và các thuật toán đối sánh khá giống nhau cho các bài toán nhận dạng và kiểm tra vân tay. Bới vì bài toán nhận dạng vân tay ( tìm kiếm một vân tay đầu vào trong một cơ sở dữ liệu có N vân tay ) có thể được thực hiện như là thực hiện tuần tự đối sánh một - một ( kiểm tra ) giữa các cặp vân tay. Sự phân loại vân tay và các kĩ thuật đánh chỉ số thường được sử dụng để tăng tốc độ tìm kiếm trong các bài toán nhận dạng vân tay. Đối sánh hai ảnh vân tay là một bài toán cực kì khó, chủ yếu do sự thay đổi dấu in của cùng một vân tay. Các yếu tố chính làm các dấu in khác nhau được tổng kết dưới đây: Sự đổi chỗ: một ngón tay có thể đặt ở các vị trí khác nhau trên bộ cảm biến làm tịnh tiến ảnh vân tay. Một ngón tay thay đổi chỉ 2mm làm tịnh tiến khoảng 40 điểm ảnh trong cùng một vân tay được quét ở độ phân giải 500dpi Sự quay: cùng một vân tay có thể quay ở các góc khác nhau trên bề mặt bộ cảm biến. Mặc dù bộ hướng dẫn ngón tay được gắn trên các máy quét thương mại, nhưng trong thực tế tồn tại sự quay không cố ý lên tới +-20 độ theo chiều dọc. Sự chồng chéo từng phần: sự đổi chỗ và sự quay vân tay thường làm cho một phần vân tay bị đổ ra ngoài vùng nhìn thấy của bộ cảm biến, kết quả là xuất hiện sự chồng chéo giữa các vùng cận cạnh của mẫu vân và các vân tay đầu vào Sự nhiễu phi tuyến: liên quan đến việc ánh xạ hình ảnh ba chiều sang hình ảnh hai chiều trên bề mặt bộ cảm biến. Ánh xạ này gây ra nhiễu phi tuyến trong việc đọc vân tay do sự mềm dẻo của ngón tay. Thông thường, các thuật toán đối sánh vân tay không quan tâm đến các đặc tính như ánh xạ, và xem một ảnh vân tay là không bị nhiễu bằng cách cho rằng: ảnh vân tay được cung cấp khi người dùng đặt đúng vị trí ngón tay; 1.-Tiếp cận ngón tay vuông góc với bộ cảm biến 2.-Khi ngón tay chạm bề mặt bộ cảm biến, người dùng không ấn mạnh hay xoắn ngón tay Do sự mềm dẻo của bề mặt da,các phần lực không vuông góc với bề mặt bộ cảm biến gây ra các nhiễu không tuyến tính ( nén lại hay kéo dãn ra ) trong quá trình lấy vân. Nhiễu làm mất khả năng đối sánh các vân tay như là các mẫu cứng Điều kiện áp lực và da: cấu trúc các vân của một vân tay có thể thu được chính xác nếu như phần ngón tay được lấy ảnh tiếp xúc đúng quy cách với bề mặt bộ cảm biến. Một số điều kiện như áp lực ngón tay, ngón tay khô, bệnh ngoài da, ướt, bẩn, độ ẩm không khí – gây ra sự tiếp xúc không đúng quy cách. Hệ quả là, ảnh vân tay lấy được rất nhiễu và mức độ các nhiễu này phụ thuộc vào mức độ các nguyên nhân nêu trên; Các lỗi trích chọn đặc trưng: các thuật toán trích chọn đặc trưng là không hoàn hảo và thường có các lỗi số đo. Các lỗi có thể tạo ra ở trong bất kì giai đoạn nào trong quá trình trích chọn đặc trưng ( chẳng hạn: ước lượng ảnh hướng và tần suất, phát hiện số lượng, dạng, vị trí các vùng đơn, phân đoạn vùng vân tay từ nền..). Cặp ảnh trong hình 3.1 thể hiện tính thay đổi cao có thể đặc tính hóa hai vết hằn khác nhau của cùng một ngón tay Hình 3.1: Các dấu vân tay thu được của cùng một ngón tay không đối sánh được với nhau do nhiễu phi tuyến ở cặp đầu tiên và do các điều kiện da ở cặp thứ hai bên dưới Các ảnh vân tay từ các ngón tay khác nhau có thể xuất hiện khá giống nhau ( tính thay đổi thấp ), đặc biệt trong bối cảnh cấu trúc tổng thể ( vị trí các vùng đơn, hướng vân cục bộ…) Mặc dù khả năng một lượng lớn các chi tiết từ các vết ấn của hai vân tay khác nhau có thể so khớp là cực kì nhỏ , những người đối sánh vân tay hướng tới việc sử dụng các phép căn chỉnh tốt nhất. Họ thường xuyên có ý định khai báo các cặp chi tiết so khớp thậm chí ngay cả khi chúng không trùng khớp hoàn hảo. Một lượng lớn các thuật toán đối sánh vân tự động đã được đề nghị trong các tài liệu nhận dạng mẫu. Hầu hết các thuật toán này không gặp khó khăn trong đối sánh các ảnh vân tay chất lượng tốt. Nhưng trong đối sánh vân tay tồn tại thách thức ở các ảnh chất lượng thấp và vấn đề đối sánh từng vùng vân tay. Trong trường hợp hệ thống trợ giúp con người AFIS, một thuật toán kiểm tra chất lượng được sử dụng để chỉ lấy và chèn vào cơ sở dữ liệu các ảnh vân tay tốt. Hơn nữa, quá trình xử lý các mẫu vân khó có thể được quản lý. Dù sao, sự can thiệp là không thể trong các hệ thống nhận dạng trực tuyến tự động-những hệ thống này đang có nhu cầu ngày càng tăng trong các ứng dụng thương mại Thống kê các lỗi không đối sánh sai xuất hiện nhiều trong các thuật toán đối sánh tham dự vào FVC2000 cho thấy hầu hết các lỗi được tạo ra trên 15-20% các ảnh vân tay chất lượng kém. Nói một cách khác, 20% mẫu trong cơ sở dữ liệu chịu trách nhiệm cho khoảng 80% các lỗi không-đối sánh sai. Vài cải tiến trong công nghệ nhận dạng vân tay được chứng minh sau đó hai năm ở FVC2002, nơi mà vài thuật toán được đưa ra đối sánh đúng nhiều ảnh vân tay chất lượng kém. Tuy vậy vẫn có nhu cầu tiếp tục phát triển các hệ thống mạnh có khả năng làm việc với các ảnh vân tay chất lượng kém. Các phương pháp đối sánh vân tay có thể được phân loại thô vào ba họ: Đối sánh dựa độ tương quan: Hai ảnh vân tay được đặt chồng lên và độ tương quan giữa các điểm ảnh tương ứng được tính với sự căn chỉnh khác nhau ( ví dụ với các vị trí và độ quay khác nhau ). Các kĩ thuật dựa độ tương quan được mô trả trong phần 4.2 Đối sánh dựa vào chi tiết: Đây là kĩ thuật phổ biến nhất và được sử dụng rộng rãi nhất.Chi tiết được trích chọn từ hai vân tay được lưu giữ như là tập các điểm trong một bề mặt hai chiều. Đối sánh dựa chi tiết cơ bản bao gồm tìm kiếm sự căn chỉnh giữa tập chi tiết mẫu và tập chi tiết đầu vào dẫn tới sự so khớp lớn nhất các cặp chi tiết. Đối sánh dựa đặc tính vân: trong các ảnh vân tay chất lượng thấp, việc trích chọn chi tiết rất khó khăn. Khi các đặc trưng khác của mẫu vân tay ( ví dụ: hướng và tần suất cục bộ, hình dạng vân, thông tin kết cấu ) có thể được trích chọn một cách tin cậy hơn chi tiết, sự khác biệt của chúng là không cao. Các phương pháp thuộc họ này so sánh các vân tay với các đặc trưng được trích chọn từ các mẫu vân. Về nguyên lý, đối sánh dựa độ tương quan và đối sánh dựa vào chi tiết có thể xem như là một phần của đối sánh dựa đặc trưng vân, theo cách hiểu mật độ điểm ảnh, vị trí chi tiết là nhưng đặc trưng của mẫu vân ngón tay Nhiều kĩ thuật khác cũng đã được đề nghị chính thức, về nguyên lý, có thể được xếp vào các họ trên theo các đặc trưng được sử dụng, nhưng chúng ta đề cập để phân loại chúng tách biệt trên cơ sở các kĩ thuật đối sánh. Chúng bao gồm các phương pháp dựa mạng thần kinh và các cố gắng thực hiện đối sánh vân sử dụng các bộ xử lý song song hoặc với các kiến trúc dành riêng khác 3.2. Các kĩ thuật dựa độ tương quan Để T và I là hai ảnh vân tay tương ứng với vân tay mẫu và vân tay đầu vào. Một số đo trực quan về sự đa dạng ( SSD ) được tính bằng tổng các bình phương khác nhau của các cường độ các điểm ảnh tương ứng: SSD(T,I) = ||T-I||2 =( T-I )T(T-I) = ||T||2 + ||I||2 -2TTI (1) Trong đó chỉ số trên T kí hiệu sự hoán vị của một vector. Nếu ||T||2 và ||I||2 là hằng số, sự đa dạng giữa hai ảnh được tối thiểu khi độ tương quan ( CC )) giữa T và I được cực đại CC(T,I ) = TTI. (2) Đại lượng -2.CC(T,I ) xuất hiện như là đại lượng thứ ba của biểu thức (1). Độ tương quan chéo ( hay gọi đơn giản độ tương quan ) là độ đo tính tương tự giữa hai ảnh. Do sự đổi chỗ và sự quay là không thể tránh khỏi, đặc tính vết ấn của một ngón tay cho trước, tính tương tự giữa chúng không thể đơn giản được tính bằng cách đặt chồng T và I và áp dụng biểu thức (2). Kí hiệu I(∆x,∆y,) thể hiện một sự quay của ảnh đầu vào I bởi một góc quanh điểm đầu ( thường là trung tâm ảnh ) và dịch một đoạn ∆x., ∆y dọc theo trục x và y; khi đó độ tương tự giữa hai ảnh T và I có thể được đo như sau: S(T,I) = max CC(T, I(∆x,∆y,)). (3) Ứng dụng trực tiếp của đẳng thức (3) hiếm khi dẫn tới các kết quả chấp nhận được chủ yếu là do các vấn đề sau: Các nhiễu phi tuyến làm cho các vết ấn của cùng một ngón tay khác nhau trong cấu trúc toàn cục; Sự nhiễu mềm dẻo không thay thế mẫu vân tay ở các vị trí cục bộ, nhưng các hiệu ứng của nhiễu được tích hợp trong không gian ảnh, mẫu vân tay toàn cục không thể được tương quan một cách đáng tin cậy Điều kiện da và áp lực ngón tay làm cho độ sáng, độ tương phản, độ giày vân thay đổi trong các vết ấn khác nhau. Sử dụng các số đó độ tương quan phức tạp hơn như độ tương quan chéo được chuẩn hóa hay độ tương quan chéo được chuẩn hóa 0-Trung bình có thể bỏ qua sự thay đổi độ sáng, độ tương phản để áp dụng các bước tăng cường ảnh, nhị phân hóa và làm mảnh ( thực hiện trên cả ảnh T và I ) có thể hạn chế độ dày vân. Hatano ( 2002 ) đã đưa ra giả thuyết sử dụng độ tương quan khác nhau, được tính như là độ tương quan lớn nhất trừ đi độ tương quan nhỏ nhất, trong một lân cận điểm nơi mà độ tương quan là lớn nhất. Trong thực tế, do tính chu kì của các mẫu vân tay, nếu hai phần tương ứng của cùng một vân tay không được căn chỉnh tương ứng với vị trí đối sánh tối ưu, giá trị độ tương quan hạ thấp trong khi hai vị trị không tương quan thể hiện một giá trị tương quan phẳng hơn trong lân cận của vị trí so khớp tối ưu. Hantano đã báo cáo một sự cải thiện độ chính xác tương ứng với phương pháp độ tương quan truyền thống Để ứng dụng trực tiếp biểu thức (3) đòi hỏi chi phí rất lớn. Ví dụ xem xét hai ảnh 400x400, sau đó sự tính toán độ tương quan ở đẳng thức (2) cho một giá trị đơn của ( ∆x,∆y, ) yêu cầu 16000 phép nhân và 16000 phép cộng. Nếu ∆x, ∆y cả hai được lấy mẫu trong miền [-200, 200] và được lấy mẫu từng 1 độ trong miền [-30o, 30o] chúng ta phải tính 401x401x61 độ tương quan, kết quả là gần 1569 tỉ phép nhân và phép cộng ( vậy là cần hơn 1h với máy tính 500MIPS ) Vấn đề nhiễu ảnh vân tay ( điểm 1 trong danh sách trên ) thường được đặt ra khi tính độ tương quan cục bộ thay vì toàn cục: một tập các miền cục bộ ( mà cỡ điển hình có thể là 24x24 hoặc 32x32 ) được trích chọn từ ảnh mẫu T và mỗi chúng được tương quan độc lập với toàn bộ ảnh đầu vào I ( Bazen 2000 ). Các miền cục bộ có thể được x bằng vài cách: Hợp của chúng hoàn toàn che phủ T và giao của chúng là rỗng hợp của chúng hoàn toàn che phủ T và chúng cục bộ đè chồng Chỉ các vùng “thú vị” được lựa chọn từ T. Ví dụ, Yahagi, Igaki.. chọn các cửa sổ nhỏ quanh các chi tiết, trong khi Bazen ( 2000 ) xem xét các miền được chọn phân biệt cục bộ trên ảnh đầu vào( phù hợp ở vị trí bên phải, nhưng không phù hợp với các vị trí khác ). Các hạng mục được đưa ra bởi Bazen để nhận dạng các vùng được chọn này trong ảnh mẫu: Các vùng quanh chi tiết, các vùng có các vân có độ cong cao, và các vùng thể hiện độ tương quan thấp ở các vị trí trong chính ảnh mẫu Khi độ tương quan được tính một cách cục bộ, ước lượng độ tương quan ở các vùng khác có thể được tính bằng cách kết hợp để nhận được độ đo tính tương tự ( ví dụ, số các ước lượng vượt qúa một ngưỡng cho trước được chia ra bởi tổng các ước lượng ). Bổ sung vào giá trị của độ tương quan, sự đồng bộ của các điểm nơi mà mỗi vùng có độ tương quan lớn nhất có thể được sử dụng để tăng cường đối sánh: trong thực tế, mối liên hệ không gian ( khoảng cách, góc… ) giữa các vùng trong mẫu và các vùng tương ứng trong ảnh đầu vào được giữ lại . Trong bất kì trường hợp nào, không có sử bảo đảm khi sử dụng bước hợp nhất là thực sự thuận lợi Để tính độ phức tạp của kĩ thuật dựa độ tương quan, các phương pháp thông minh có thể được sử dụng để đạt được sử thi hành hiệu quả: Định lý độ tương quan ( Gonzales và Woods, 1992 ) phát biểu rằng: tính toán độ tương quan trên các miền không gian ( toán tử …) là tương đương với thực hiện một phép nhân miền điểm trên miền Fourier, trong thực tế ( 4 ) Trong đó F(.) là biến đổi fourier của một ảnh, F-1( . ) là biến đổi Fourier ngược, * kí hiệu liên hợp phức, và “x” kí hiệu nhân điểm với điểm của hai vector. Kết quả của đẳng thức ( 4 ) là ảnh độ tương quan mà các giá trị ở các điểm [x,y] thể hiện độ tương quan giữa T và I trong khi sự đổi chỗ là ∆x=x, ∆y=y. Đẳng thức (4) không xem xét sự quay , phải được giải quyết tách ra; trong bất kì trường hợp nào, tiết kiệm tính toán là rất cao trong khi độ tương quan được thực hiện một cách toàn cục ( Coezteen và Botha, 1993 ) và khả năng xem xét khi nó được thực hiện một cách cục bộ bằng cách sử dụng các miền cỡ trung bình Tính toán độ tương quan lớn nhất không cần phải thực hiện tuần tự, theo cách vét cạn, các phương pháp đa phân giải, các kĩ thuật tìm kiếm không gian ( Gradient Descent ), và vài kinh nghiệm có thể được chấp nhận để làm giảm số các đánh giá Biến đổi Fourier-Mellin ( Sujan và Mulqueen ) có thể được sử dụng thay cho biến đổi Fourier để đánh giá được sự không thay đổi trong phép quay để bổ sung vào sự không thay đổi trong chuyển dịch; nói một cách khác, vài bước thêm vào ( như chuyển đổi log ) phải được thực hiện, nhưng chúng có thể làm giảm sự chính xác của giải pháp Phương pháp đưa ra bởi Wilson, Watson, và Paek ( 1997 ) phân hoạch cả T và I vào trong các miền cục bộ và tính toán độ tương quan lớn nhất ( trong miền Fourier ) giữa các cặp vùng. Phương pháp này bị ảnh hưởng bởi hiệu ứng viền do sự đè chồng không gian giữa các khối khác nhau, nhưng có thể được xem xét để tăng tốc độ của toàn bộ quá trình đối sánh độ tương quan giữa hai tín hiệu có thể được tính bởi một hệ thống quan sử dụng thấu kính để dẫn xuất biến đổi Fourier của một ảnh và kết hợp các độ tương quan biến đổi cho sự đối sánh giữa chúng. Vài hệ thống đã được đưa ra trên thực tế cho đối sánh vân tay quang học: 3.3. Các phương pháp dựa chi tiết Đối sánh chi tiết là phương pháp nổi tiếng và được sử dụng rộng rãi nhất trong đối sánh vân tay, do các chuyên gia pháp lý so sánh các vân tay và chấp nhận phương pháp như là bằng chứng định danh trong các phiên tòa ở hầu hết các quốc gia. Phát biểu bài toán: Kí hiệu T và I là các biểu diễn của vân tay mẫu và vân tay đầu vào. Không như các kĩ thuật dựa độ tương quan, nơi mà các biểu diễn vân tay trùng khớp với ảnh vân tay, ở đây biểu diễn vân tay bởi một vector đặc trưng ( của chiều dài biến thiên ) mà các phần tử là các chi tiết vân tay. Mỗi chi tiết có thể được mô tả bằng một số các thuộc tính, bao gồm vị trí trong ảnh vân tay, hướng, kiểu ( ví dụ điểm kết thúc vân hay điểm rẽ nhánh ), một trọng số dựa trên chất lượng của ảnh vân tay trong một lân cận của chi tiết…Hầu hết các thuật toán đối sánh chi tiết xem xét mỗi chi tiết như là một một nhóm bộ ba m = { x, y, ) thể hiện vị trí chi tiết ở vị trí x, y và góc chi tiết : T = { m1, m2, …mm }; mI = { xi, yi, i }, i = 1…m I = { m1’, m2’…mn’ }; mj’ = { xj’, yj’, j’ } j = 1…n Trong đó m và n là số các chi tiết trong T và I Một chi tiết mj’ trong I và một chi tiết mi trong T được xem là so khớp nếu khoảng cách không gian ( sd ) giữa chúng là nhỏ hơn mức dung sai cho trước ro và sự khác nhau về hướng ( dd ) giữa chúng là nhỏ hơn góc dung sai o: đẳng thức (6) lấy giá trị nhỏ nhất của | , và 360o - | bởi vì tính chu kì của góc ( sự khác nhau giữa 2o và 358o chỉ là 4o ). Chúng ta cần một hộp dung sai được định nghĩa qua ro và o để bù vào các lỗi không thể ngăn ngừa do các thuật toán trích chọn đặc trưng và các nhiễu mềm dẻo làm cho vị trí các chi tiết thay đổi Căn lề hai vân tay là bước bắt buộc để cực đại hóa số các chi tiết đối sánh. Căn lề chính xác hai vân tay yêu cầu phải tịnh tiến ( theo x và y ) , quay ( góc ) do vậy liên quan đến biến đổi hình học: phải co giản ảnh vân tay khi độ phân giải của hai vân tay có sự khác nhau( ví dụ: hai ảnh vân tay được thu nhận bởi các máy quét hoạt động ở các độ phân giải khác nhau ) các biến đổi hình học dung sai cho nhiễu có thể có ích trong đối sánh chi tiết trong trường hợp một hoặc cả hai vân tay bị ảnh hưởng bởi vài nhiễu Trong bất kì trường hợp nào, dung sai cho một lượng lớn các biến đổi làm cho độ tự do trong các bộ đối sánh chi tiết tăng lên: khi một bộ đối sánh được thiết kế, vấn đề này cần cẩn thật đánh giá, mỗi độ tự do lại gây ra một số lượng lớn các căn chỉnh mới và làm tăng tỉ lệ đối sánh sai giữa hai vân từ các ngón tay khác nhau. Kí hiệu map(.) là hàm ánh xạ một chi tiết ( từ I ) vào trong theo công thức biến đổi hình học cho trước; ví dụ, bằng cách xem xét sự chuyển dịch của ( ∆x, ∆y ) và một góc quay ngược chiều kim đồng hồ quanh điểm đầu: Kí hiệu mm(.) là hàm chỉ thị trả về 1 trong trường hợp chi tiết và mi so khớp theo công thức (5) và ( 6): Sau đó bài toán đối sánh có thể được công thức như sau: Trong đó P(i ) là một hàm không biết trước quyết định cặp đôi giữa các chi tiết I và T; nghĩa là mỗi chi tiết có một chi tiết tương ứng trên vân tay khác hoặc không có chi tiết tương ứng nào: P(i ) = j nghĩa là chi tiết tương ứng của mi trong T là chi tiết trong I P(i) = null nghĩa là chi tiết mi trong T không có chi tiết tương ứng trong I một chi tiết trong I, với mọi i = 1…m không có chi tiết tương ứng trong T; mọi i = 1…m, k = 1…m, i k => P(i ) P ( k ) hay P ( i ) = P ( k ) = null ( điều này yêu cầu mỗi chi tiết trong I được liên kết với tối đa một chi tiết trong T ) Khi p ( i ) = j không có nghĩa rằng chi tiết và mi so khớp theo đẳng thức ( 5 ) và ( 6 ) mà chỉ với nghĩa rằng các cặp này tương tự nhau theo công thức chuyển đổi hiện tại Biểu thức ( 7 ) yêu cầu số lượng các chi tiết tương ứng được cực đại, độc lập với các giới hạn của các chi tiết tương ứng này. Nghĩa là, nếu hai chi tiết thỏa mãn đẳng thức ( 5) và ( 6 ) sau đó phân phối chúng vào đẳng thức ( 7 ) thì tạo ra sự độc lập về khoảng cách không gian và về sự khác nhau của hướng. Một công thức thay thế cho biểu thức ( 7 ) được đưa ra với phần dư( nghĩa là khoảng cách không gian và sự khác nhau về hướng giữa các chi tiết ) được xem xét cho căn chỉnh tối ưu Giải quyết bài toán đối sánh chi tiết ( biểu thức (7 ) là tầm thường khi căn chỉnh đúng ( ∆x, ∆y, θ ) được biết đến; trong thưc tế, ghép cặp ( nghĩa là hàm P ) có thể được quyết định bằng cách thiết lập riêng cho mỗi i = 1…m: P(i) = j nếu gần mi nhất trong các chi tiết P(i)=null nếu Để thỏa mãn với ràng buộc 4 ở trên, mỗi chi tiết đã được kết bạn phải được đánh dấu, để ngăn ngừa kết hợp hai lần . Hình 3.2 thể hiện ví dụ về các chi tiết được ghép cặp cho bởi các căn chỉnh vân cho trước Để đạt được ghép cặp tối ưu ( theo đẳng thức (7), một lược đồ phức tạp hơn một ít được chấp nhận: thực tế, trong trường hợp khi một chi tiết ở I rơi vào hộp dung sai của hơn một chi tiết của T, cấp phát tốt nhất là cực đại số các chi tiết tương ứng ( xem hình 3.3 như là một ví dụ đơn giản ) Sự cực đại trong ( 7 ) có thể dễ dàng giải quyết nếu hàm P ( phù hợp chi tiết ) được biết trước; trong trường hợp này, một căn chỉnh không biết trước (∆x, ∆y, θ) có thể được quyết định ít nhất bởi hình vuông hai chiều. Trong thực tế, cả các tham số căn chỉnh và hàm tương ứng P đều không được biết trước ,vì vậy, giải quyết vấn đề đối sánh là rất khó khăn. Một phương pháp cưỡng bức, đánh giá mọi giải pháp có thể ( sự tương ứng và căn chỉnh ) bị ngăn ngừa. Một vài phương pháp cưỡng bức đã được đưa ra trong tài liệu; ví dụ, Huvananda, Kim và Hwang ( 2000 ) đã giả sử một cách thô là lượng tử các vị trí chi tiết và thực hiện tìm kiếm vét cạn để tìm ra căn chỉnh tối ưu Hình 3.2 :Các chi tiết của I được ánh xạ hệ toạ độ T. Các chi tiết của I kí hiệu là o còn các chi tiết của T kí hiệu là x. Vòng gạch liên tiếp chỉ khoảng cách không gian lớn nhất, vòng xám chỉ các cặp chi tiết ghép cặp thành công Hình3.3: Trong ví dụ này, nếu m1 ghép cặp với m2’’ ( chi tiết gần nhất ), m2 sẽ không được ghép cặp. Vì vậy nếu ghép các cặp m1 và m1’ cho phép m2 được ghép cặp với m2’’ làm cực đại đẳng thức 7 Trong tài liệu nhận dạng mẫu, bài toán đối sánh chi tiết được đặt ra như là bài toán đối sánh mẫu điểm. Thậm chí do sự tồn tại của một hướng liên hệ với mỗi điểm chi tiết, hai vấn đề có thể được tiếp cận tương tự nhau. Bởi vì vài trò trung tâm trong nhiều ứng dụng nhận dạng mẫu và các nhiệm vụ quan sát máy tính ( ví dụ, đối sánh đối tượng, cảm biến từ xa, ước lượng chuyển động ), đối sánh mẫu điểm là hướng được nghiên cứu mở rộng, được biết tới nhiều trong: các phương pháp hồi phục, các giải pháp đại số và nghiên cứu hoạt động, các phương pháp tỉa cây, các phương pháp tối thiểu năng lượng, biến đổi Hough… Các phương pháp dựa biến đổi Houg cho đối sánh chi tiết: Ratha ( 1996 ) đề nghị một phương pháp đối sánh chi tiết dựa biến đổi Hough với các biến đổi căn chỉnh, bên cạnh phép tịnh tiến và phép quay, còn gồm cả phép co giãn. Không gian biến đổi là không gian bốn chiều ( ∆x, ∆y, θ, s ) trong đó mỗi tham số được rời rạc hóa ( kí hiệu bởi dấu + ) vào tập các giá trị: ∆x+ є { ∆x1+, ∆x2+,…,∆xa+| };∆y+ є { ∆y1+, ∆y2+,…,∆yb+| }; θ+ є { θ1+, θ2+,…,θc+ } ; s+ є { s1+, s2+,…,sd+ } Một mảng bốn chiều A, với điểm vào cho mỗi tham số rời rạc, được khởi tạo và thuật toán sau được sử dụng để tích lũy: Với mỗi mi, i = 1..m Với mỗi m’j, j = 1..n Với mỗi + {+1, +2, …, +c} Nếu khoảng cách trực tiếp(’j + +, i) < 0 Với mỗi s+ {s+1, s+2, …, s+d} { x+, y+ = lượng tử hoá của x, y tới tập gần nhất A[x+, y+, +, s+] = A[x+, y+, +, s+] + 1 } Ở cuối quá trình tích lũy, biến đổi có căn chỉnh tốt nhất ( ∆x+, ∆y+, θ+, s+ ) nhận được như sau (x*, y*, *, s*) = arg max A[x+, y+, +, s+] Và các cặp chi tiết được thực hiện theo thuật toán trên ( trong “công thức vấn đề” ). Để tăng cường sức mạnh của biến đổi Hough, thông thường không chỉ sử dụng rời rạc hóa, còn sử dụng các láng giềng gần nhất; vì vậy, trong đoạn giả mã ở trên , bộ cập nhật tích lũy có thể được thay thế bởi một thủ tục đơn giản để cập nhật toàn bộ điểm vào trong các láng giềng của tập được chọn Một thực thi song song hiệu quả của thuật toán trên, với độ phức tạp là O ( m.n.c.d ) được giới thiệu bởi Ratha, Rover, và Jain ( 1995 ) , trong đó phần cứng được dành riêng bao gồm bộ xử lý đối sánh mẫu điểm dựa vào mảng cổng có thể lập trình ( FPGA ) đã được thiết kế 3.4.Các kĩ thuật đối sánh dựa đặc trưng vân Ba lý do chính thuyết phục các nhà thiết kế các kĩ thuật nhận dạng tìm kiếm các đặc trưng khác ngoài các chi tiết là: Sự tin cậy từ quá trình trích chọn chi tiết từ các vân tay chất lượng thấp là rất khó khăn. Mặc dù các chi tiết có thể mạng hầu hết các thông tin đúng đắn, chúng không phải lúc nào cũng thỏa mãn sự chính xác và tốc độ Trích chọn chi tiết rất tốn thời gian. Đó là vấn đề nghiêm trọng trong quá khứ, khi sức mạnh tính toán của các máy tính để bàn là thấp. Mặc dù các máy tính ngày nay đã nhanh hơn, tốc độ đối sánh vẫn được quan tâm bởi vì nhu cầu nhúng các thuật toán nhận dạng giá thành hạ vào trong các hệ thống ngày càng tăng Các đặc trưng thêm vào có thể sử dụng cùng với các chi tiết để tăng sự chính xác và tốc độ Các đặc trưng thay thế thường được sử dụng là: 1.Cỡ của vân tay và hình dạng ngoài của bóng vân tay 2.Số lượng, kiểu và vị trí các vùng đơn 3.Mối quan hệ không gian và các thuộc tính hình học của đường vân 4.Đặc trưng hình dạng 5.Thông tin kết cấu toàn cục và cục bộ 6.Các lỗ chân lông 7.Các đặc trưng nhỏ Các đặc trưng ở 1 và 2, nói chung không ổn định, chúng thay đổi theo phần ngón tay đặt vào bộ cảm biến. Các lỗ chân lông rất rõ ràng nhưng phát hiện chúng đòi hỏi nhứng máy quét đắt tiền có độ phân giải cao Sử dụng mối liên hệ không gian của các dạng vân là phương pháp cấu trúc cơ bản đưa ra bởi Moayer và Fu ( 1986 ), Isenor và Zaky ( 1986 ). Trong phương pháp đưa ra bởi Moayer các ngữ pháp cây được đưa ra để phân loại các mẫu đường vân sau khi chúng được nhị phân hóa và làm mảnh. Ở phương pháp sau, đối sánh đồ thị tăng dần được thực hiện để so sánh một tập các vân được sắp xếp theo cấu trúc đồ thị Ceguerra và Koprinska ( 2002 ) đưa ra các đặc trưng dựa hình dạng, ở đó bao gồm chữ kí hình dạng một chiều mã hóa hình dạng chung của vân tay được tạo ra từ ảnh vân tay hai chiều sử dụng trục tham chiếu. Đối sánh dựa hình dạng sau đó được sử dụng cùng với đối sánh dựa chi tiết để đưa ra quyết định cuối cùng Thông tin cấu trúc toàn cục và cục bộ là thay thế quan trong cho các chi tiết , đối sánh vân tay dựa cấu trúc đang là hướng nghiên cứu tích cực. Các cấu trúc được định nghĩa bằng quan hệ không gian giữa các phần tử cơ bản. và đặc trưng hóa bởi các thuộc tính như độ co giãn, hướng, tần suất...Các đường vân chủ yếu được mô tả bằng hướng vân trơn và tần suất, ngoại trừ các vùng đơn. Các vùng đơn là không liên tục trong các mẫu thông thường bao gồm lặp ( s ) và ở độ phân giải thấp và là các chi tiết ở độ phân giải cao. Coetzee và Botha ( 1993 ) đưa ra các phân tích cấu trúc vân tay trong miền Fourier. Mặc dù các vân trong miền không gian biến đổi tới một tần suất không đổi ( trong miền tần suất ), các đặc trưng phân biệt của vân tay như hướng vân cụ thể và các chi tiết tự kê khai chính nó như là các độ chệc từ tần suất không gian chính của các vân. Một “bộ phát hiện nêm-vòng “ sau đó được sử dụng để thực hiện phân tích trên miền tần số; Các hàm điều hòa trong mỗi vùng đơn của bộ phát hiện được tích lũy, kết quả là một vector đặc trưng chiều dài cố định thể hiện sự tịnh tiến, quay và không giãn nỡ. Phân tích cấu trúc toàn cục kết hợp các phân phối từ các miền đặc tính khác nhau vào một số đo toàn cục, vì vậy hầu hết các thông tin không gian có sẵn bị mất đi Các phân tích cấu trúc cục bộ đã chứng minh là hiệu quả hơn phân tích đặc trưng toàn cục; mặc dù hầu hết thông tin cấu trúc cục bộ được nhớ bằng các ảnh hướng và tần suất, hầu hết các phương pháp đưa ra trích chọn cấu trúc bằng cách sử dụng một ngân hàng đặc biệt các bộ lọc. 3.5. So sánh hiệu năng của các thuật toán đối sánh Qua chương này, vài kĩ thuật cho đối sánh vân tay đã được khảo sát và vài phương pháp chuyên nghiệp đã được nhấn mạnh. Dù sao, một câu trả lời rõ ràng không được cung cấp cho câu hỏi: Đâu là thuật toán tốt nhất cho đối sánh vân tay? Có hai lý do chính giải thích tại sao quyết định hiệu năng tương đối giữa các thuật toán khác nhau là khó khăn: Hiệu năng của một phương pháp nhận dạng vân tay liên quan đến nhiều độ đo hiệu năng khác nhau: độ chính xác ( FMR, FNMR …), hiệu quả ( thời gian thu thâp, thời gian kiểm tra ), tính mềm dẻo cho nhận dạng 1:N, cỡ của mẫu…Các ứng dụng khác nhau có thể sử dụng một thuật toán đối sánh vân tay với độ chính xác thấp hơn nhưng lại có cõ mẫu nhỏ hơn so với thuật toán chính xác cao hơn nhưng sử dụng cỡ mẫu lớn hơn. Hầu hết các kết quả khoa học được xuất bản trong các tài liệu bao gồm các kết quả thực nghiệm thực hiện trên cơ sở dữ liệu độc quyền sử dụng các giao thức khác nhau, và không chia sẻ trên các kênh nghiên cứu. Điều này tạo khó khăn để so sánh các phương pháp khác nhau, hiệu năng đo được không có một điểm chuẩn để so sánh. Trước khi cuộc thi kiểm tra vân tay FVC2000 và FVC2002, chỉ có tập dữ liệu vân tay miền công cộng là cơ sở dữ liệu NISt. Mặc dù các cơ sở dữ liệu này là điểm chuẩn tốt cho phát triển AFIS, chúng không thích hợp tốt để đánh giá hoạt động thuật toán với các ảnh quét trực tiếp. Sau đây là vài cách trách lỗi thông thường trong đánh giá hiệu năng của các thuật toán đối sánh: Không sử dụng cùng một tập dữ liệu cho huấn luyện, hợp lệ hóa và kiểm tra một thuật toán Không tính hiệu năng trên một tập cơ sở dữ liệu rất nhỏ Không làm sạch cơ sở dữ liệu bằng cách loại bỏ các mẫu có sự từ chối hoặc không được phân loại bởi hệ thông; Về nguyên lý, bằng cách lặp loại bỏ các mẫu như vậy có thể đạt tới độ chính xác mong muốn Không kết luận độ chính xác của một hệ thống tốt hơn hệ thống khác khi chũng được đánh giá trên các tập dữ liệu khác nhau Không dấu điểm yếu của thuật toán, nhưng lại tài liệu hóa các thất bại CHƯƠNG 4:CÁC THUẬT TOÁN VÀ THỰC NGHIỆM 4.1 Giới thiệu. Chương này sẽ tập trung vào việc mô tả chi tiết các thuật toán đã đuợc sử dụng và kết quả thực thi của chúng. Nó mô tả các bước cần thiết để có thể so sánh hai vân tay với nhau. Từ việc tính hướng cục bộ, chuẩn hóa, tăng cường,… đến việc đối sánh vân tay. Chương trình được viết bằng ngôn ngữ hướng đối tượng Visual C#. Lớp ImageData chứa dữ liệu ảnh và tất cả các thuật toán lên quan đến việc xử lý ảnh vân tay. Lớp Minutiae chứa dữ liệu về chi tiết và một số phương thức xử lý chi tiết như quay và tịnh tiến. Lơp Functions chưa một số hàm tĩnh để xử lý giữa các ảnh và các chi tiết như so sánh chi tiết, so sánh ảnh, khoảng cách các chi tiết,…. Các form của chương trình đuợc thiết kế đơn giản, đầy đủ chức năng và khá thân thiện Để thực thi một số thuật toán như tính hướng vân tay cục bộ, chuẩn hóa ảnh, tăng cường ảnh, nhị phân hóa, tìm xương vân, tìm chi tiết. Bạn có thể vào Công cụ->Kiểm nghiệm thuật toán . Khi đó sẽ hiện ra form để bạn có thể tiến hành từng bước một. Click vào nút “Mở ảnh” để chọn ảnh bạn muốn kiểm nghiệm. Còn việc đối sánh được thực hiện ngay ở form chính của chương trình. 4.2 Các thuật toán được sử dụng. 4.2.1 Thuật toán tính hướng vân tay cục bộ. 4.2.1.1 Phương pháp. Để tính hướng vân tay cục bộ tại vị trí điểm ảnh [ xi, yj ]. Xét một ô vuông có kích thước tùy ý( theo khuyến cáo thì nên chọn là 17x17 tuy nhiên có thể chọn kích thước ô vuông nhỏ hơn để tăng tốc độ xử lý). Tính Gxy theo công thức: Tính Gxx theo công thức: Tính Gyy theo công thức: Cuối cùng hướng cụa bộ tại vị trí điểm ảnh [ xi, yj ] được tính bởi công thức: Ở đây x và y được là thành phần gradient được tính qua mặt nạ (3x3)Sobel 4.2.1.2 Kết quả thực thi. Để kiểm nghiệm kết quả, bạn click vào bất kỳ vị trí nào trên ảnh vân tay. Chương trình sẽ vẽ ra hướng vân tay cục bộ tại điểm đó. Hình dưới là kết quả của việc click một số lần lên ảnh vân 4.2.2 Thuật toán chuẩn hóa ảnh. 4.2.2.1 Phương pháp. Đầu tiên tính kỳ vọng của ảnh theo công thức Tiếp đến là tính giá trị phương sai của ảnh theo công thức. Tiếp theo tính giá trị mức xám mới theo công thức 4.2.2.2 Kết quả thực thi Click vào nút “Chuẩn hóa” ta được kết quả thực thi như sau 4.2.3 Thuật toán tăng cường ảnh 4.2.3.1 Phương pháp Tìm mặt nạ tại mỗi điểm theo công thức. Trong đó q chính là hướng vân tay cục bộ tại điểm đó. Và f là tần suất vân tay cục bộ tại điểm đó. Nhưng do việc tính toán tần suất vân tay cục bộ tại mỗi điểm ảnh là rất phức tạp nên có thể ước lượng giá trịcủa f phù hợp (1/5,1/7,1/9,…) . Đông thới [xθ, yθ] có thể được tính theo công thức. Thực hiện nhân chập mặt nạ thu được với ma trân ảnh. Giá trị cấp xám mới của điểm ảnh chính là giá trị tại điểm đó của kết quả nhân chập. 4.2.3.2 Kết quả thực thi. Click vào nút “Tăng cường” ta thu được kết quả của ảnh vân tay sau khi tăng cường như sau. 4.2.4 Thuật toán tách ngưỡng tự động. 4.2.4.1 Phương pháp Tìm ngưỡng bằng cách. Gọi t(g) là số điểm ảnh có giá trị £ g, m(g) là giá trị trung bình của các điểm ảnh có giá trị £ g: Gọi G là số cấp xám được xét, P là số điểm ảnh được xét: Giá trị ngưỡng cần tìm là q, sao cho ¦(q) = max ¦(g) Rồi tách ngưỡng. I(x,y) = 1 nếu I(x,y)³q 0 nếu I(x,y)<q 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. Click vào nút “Nhị phân hóa” ta sẽ ra kết quả của việc tách ngưỡng nhờ tìm ngưỡng tự động như sau 4.2.5 Thuật toán tìm xương. 4.2.5.1 Phương pháp. Tìm các điểm biên. Kiểm tra điểm biên nào có thể xóa được thì thực hiện xóa Thuật toán kiểm tra điểm (x,y) có là điểm biên hay kô thực hiện như sau: BOOL IsBorder(int x, int y) { If ( Image[x-1 ][y] ==0 || Image[x-1 ][y] ==0 || Image[x-1 ][y] ==0 || Image[x-1 ][y] ==0) return TRUE; return FALSE; } Điều kiện xoá điểm biên phải đảm bảo: Không làm mất tính chất lưu thông Không tạo ra lỗ hổng Không làm mất điểm cụt Các điểm còn lại thuộc trục trung vị Bất biến với phép quay tịnh tiến Với các điều kiện trên, ta có thể xoá các điểm P như sau: A: các điểm có giá trị bằng P B: các điểm có giá trị khác P *: các điểm tuỳ ý Thuật toán kiểm tra điều kiện xóa của điểm (x,y) được thực hiện như sau: BOOL IsDeletable(int x, int y) { BOOL P0 = Image[x+1][y], P1 = Image[x+1][y-1], P2 = Image[x][y-1], P3 = Image[x-11][y-1], P4 = Image[x-1][y], P5 = Image[x-1][y+1], P6 = Image[x][y+1], P7 = Image[x+1][y+1]; if (P1*P2*P3 == 1 && P5+P6+P7==0) return TRUE; if (P0*P1*P2 == 1 && P4+P5+P6==0) return TRUE; if (P0*P1*P7 == 1 && P3+P4+P5==0) return TRUE; //... return FALSE; } Và cuối cùng việc tìm xương được thực hiện như sau: void MakeBone() { BOOL Manh = FALSE; Stack S; S.Empty(); // Khởi tạo ngăn xếp rỗng while (!Manh) { Manh = TRUE; for (int i=0; i<M; i++) for (int j=0; j<N; j++) if (IsBorder(i,j)) if (IsDeletable(i,j)) //Đẩy các điểm có thể xoá được { S.Push(i,j); //vào ngăn xếp Manh = FALSE; } while (!S.IsEmpty) //Xoá tất cả các điểm trong ngăn xếp { S.Pop(i,j); Image[i][j] = 0; } } } 4.2.5.2 Kết quả thực thi. Click vào nút “Tìm xương” ta sẽ thu được kết quả tìm xương như sau. 4.2.6 Tìm kiếm chi tiết. 4.2.6.1 Phương pháp. Chi tiết ảnh chính là những điểm những điểm ảnh đặc biệt năm trên xương của vân và hướng vân cục bộ tại điểm đó. Điểm đặc biệt chính là điểm kết thúc hoặc rẽ nhánh của đường vân. Việc kiểm tra một điểm có là điểm rẽ nhánh hay điểm kết thúc hay không được thực hiện bằng các tính tổng các trị tuyệt đối của hiệu các cặp điểm liên tuc xung quanh điểm đang xét (tất nhiên việc xử lý này được thực hiện trên ảnh vân tay đã được làm mảnh). Nếu tổng bằng 1 thì đó là điểm kết thúc, và bằng 3 nếu nó là điểm rẽ nhánh. Cụ thể cho điểm ảnh (x,y) như sau; BOOL IsMinutiae(int x, int y) { If ( Image[x ][y] ==0)) { sum = |image[x-1,y-1]-image[x-1,y]| + |image[x-1,y+1]-image[x,y+1]| + |image[x+1,y+1]-image[x+1,y]| + |image[x+1,y+1]-image[x+1,y]| + |image[x+1,y-1]-image[x,y-1]| If(sum==1orsum==3) return true; } return FALSE; } 4.2.6.1 Kết quả thực thi: Click và nút “Xem chi tiết” sẽ hiện ra các chi tiết của vân tay tìm được. 4.2.7 Thuật toán Hough 4.2.7.1 Phương pháp. Thuật toán Hough là thuật toán tìm ra các gái trị tịnh tiến theo trục x, trục y, góc quay ngược chiều kim đồng hồ va đổ nở của vân ( ∆x, ∆y, θ, s ) sao cho khi thực hiện các phép biến đổi đó thực hiện trên tập chi tiết của vân tay này sẽ thu được tập chi tiết mới mà có số lượng chi tiết trùng khớp với tập chi tiết của vân tay kia là lớn nhất. Thuật toán dựa trên các tập giới hạn của ∆x là { ∆x1+, ∆x2+,…,∆xa+| }, của ∆y là { ∆y1+, ∆y2+,…,∆yb+| }, của θ là { θ1+, θ2+,…,θc+ } và của s là {s1+, s2+,…,sd+} Thuật toán phát biểu như sau. Với mỗi mi, i = 1..m Với mỗi m’j, j = 1..n Với mỗi + {+1, +2, …, +c} Nếu khoảng cách trực tiếp(’j + +, i) < 0 Với mỗi s+ {s+1, s+2, …, s+d} { x+, y+ = lượng tử hoá của x, y tới tập gần nhất A[x+, y+, +, s+] = A[x+, y+, +, s+] + 1 } Ở đây A chính là mảng bốn chiều mà gái trị của A[x+, y+, +, s+] thể hiện số cặp chi tiết ủng hộ cho [x+, y+, +, s+]. Ở cuối quá trình tích lũy, biến đổi có căn chỉnh tốt nhất (x*, y*, *, s*) nhận được như sau (x*, y*, *, s*) = arg max A[x+, y+, +, s+] Đó chính là giá trị mà ta muốn tìm. 4.2.7.2 Kết quả thực thi. Để thực thi thuật toán trước hết bạn mở form chính của chương trình mở 2 ảnh vân tay ra. Form hiển thị như sau Vào “Xử lý->Thông tin so sánh” sẽ hiện ra form hiển thị kết quả của thuật toán Hough như sau 4.2.8 Thuật toán đối sánh vân tay 4.2.8.1 Phương pháp. Phương pháp này sẽ tiến hành đối sánh hai tập chi tiết của hai ảnh vân tay. Nếu số lượng ảnh vân trùng khớp lơn hon một giá trị giới hạn nào đây thi hai vân tay la trung khớp. Trước hết chúng ta tiến hành tịnh tiến và quay tập chi tiết của ảnh hai theo các đại lượng chúng ta thu được từ thuật toán Hough. Tiến hành đối sánh lần lượt từng chi tiết của tập chi tiết ảnh vân tay 1 với tập chi tiết thu được Hai chi tiết mI = { xi, yi, Өi } và mj’ = { xj’, yj’, Өj’ } được gọi là so khớp nếu: Với r0 và là các giá trị giới hạn. Dựa theo công thức trên sẽ đếm số lượng cặp chi tiết so kớp với nhau. Tư đó rút ra kết luận 4.2.8.2 Kết quả thực thi. Với hai ảnh vân tay như sau Chọn “Xử lý->So sánh vân tay” Se đưa ra thông báo như sau KẾT LUẬN Khoá luận tốt nghiệp “nghiên cứu và phát triển ứng dụng nhận dạng vân tay” đã đạt được một số kết quả sau: Nghiên cứu một số thuật toán xử lý ảnh vân tay như chuẩn hoá, tăng cường ảnh vân tay và một số thuật toán trong việc trích chọn đặc trưng vân tay như tính hướng cục bộ, trích chọn chi tiết, tần suất vân tay. Nghiên cứu một số kỹ thuật đối sánh vân tay như kỹ thuật dựa trên độ tương quan, kỹ thuật dựa trên chi tiết, kỹ thuật dựa trên đặc trưng vân. Cài đặt thành công một số thuật toán xử lý ảnh như chuẩn hóa, tăng cường ảnh vân và một số thuật toán trích chọn đặc trưng vân. Cài đặt thành công các thuật toán dựa trên chi tiết. Chương trình đã có thể đối sánh hai vân tay. Tuy nhiên, do lần đầu tiếp cận và thời gian hạn chế, khoá luận không tránh khỏi những sai sót. Khoá luận mới chỉ dừng lại ở mức nghiên cứu và tổng hợp các thuật toán đã có. Xác suất sai số trong khi đối sánh vân tay là khá lớn. Chúng tôi sẽ cố găng nghiên cứu và phát triển để chương trình ngày càng hoàn thiện. TÀI LIỆU THAM KHẢO Tiếng Việt [1] Lương Mạnh Bá, Nguyễn Thanh Thuỷ. Nhập môn xử lý ảnh số. Nhà xuất bản khoa học kỹ thuật, 1999. [2] Ngô Quốc Tạo. Tập bài giảng “Nhập môn xử lý ảnh”. Tiếng Anh [1] Handbook of fingerprint Recognition – Davide malhoni,Dario Maio, Anil K.Jain, Salil Prabhakar. [2] Fingerprint verification competition. [3] Nist fingerprint vendor technology evaluation ( [4] Registration of images with geometric distortions. Transactions on Geoscience and Remote Sensing, 26(1), 1988. [5] New York American National Standards Institute. American national standard for information systems, data format for the interchange of fingerprint information, 1993. ANSI/NIST-CSL 1-1993. [6] Orit Baruch. Line thinning by line following. Pattern Recognition Letters, 8:271–276, 1988. [7] A. M. Baze, G. T. B Verwaaijen, S. H. Garez, L. P. J. Veelunturf, and B. J. van der Zwaag. A correlation-based fingerprint verification system. In ProRISC2000 Workshops on Circuits, Systems and Signal Processing, Nov 2000. [8] A. M. Bazen and S.H. Gerez. Extraction of singular points from directional fields of fingerprints. February 2001. [9] Asker M. Bazen and Sabih H. Gerez. Fingerprint matching by thin-plate spline modeling of elastic deformations. Pattern Recognition, 36:1859–1867, 2003. 97 [10] B.G.Sherlock and D.M.Monro. A model for interpreting fingerprint topology. Pattern Recognition, 26(7):1047–1055, 1993. [11] B.G.Sherlock, D.M.Monro, and K.Millard. Fingerprint enhancement by directional fourier filtering. In Visual Image Signal Processing, volume 141, pages 87–94, 1994. [12] Ruud Bolle, J. H. Connell, S. Pankanti, N. K. Ratha, and A. W. Senior. Guide to Biometrics. Springer Verlag, 2003. [13] L. Brown. A survey of image registration techniques. ACM Computing Surveys, 1992.