KHÁI QUÁT VỀ ĐỐI SÁNH VÂN TAY DỰA TRÊN ĐIỂM CHẠC
Hệ thống nhận dạng vân tay tự động
Quá tr nh x lý của một hệ thống nhận dạng vân tay tự động thường trải qua các bước sau [MMJ09]:
Quá trình lấy mẫu vân tay thường sử dụng thiết bị điện tử có cảm ứng, với sự đa dạng trong các loại thiết bị cảm ứng này.
Trích chọn thuộc tính là quá trình quan trọng trong việc đối sánh vân tay, trong đó ảnh vân tay gốc được xử lý bởi bộ phận trích chọn thuộc tính Quá trình này tạo ra một tập đặc trưng gọn nhẹ nhưng vẫn thể hiện và đại diện cao cho các đặc điểm của vân tay.
- Tạo bản mẫu: là quá tr nh t chức một hoặc nhiều tập đặc trưng vào một bản mẫu và lưu trữ trên thiết bị lưu trữ
Lọc vân tay trước khi đối sánh là bước quan trọng trong hệ thống định danh, đặc biệt khi số lượng bản mẫu lưu trữ lớn Quy trình này giúp giảm thiểu số lượng bản mẫu cần phải đối sánh, từ đó nâng cao hiệu quả và tốc độ của quá trình xác thực.
Giai đoạn đối sánh vân tay bắt đầu bằng việc so sánh tập đặc trưng của vân tay cần kiểm tra với bản mẫu lưu trữ Trong quá trình này, hệ thống tính toán độ tương đồng giữa các vân tay thông qua chỉ số đối sánh (matching score hay similarity score) Kết quả đối sánh sẽ được so sánh với ngưỡng của hệ thống để xác định xem hai vân tay có phù hợp hay không; nếu cao hơn ngưỡng, chúng được coi là giống nhau, ngược lại sẽ được xem là khác nhau Trong quá trình lấy mẫu, vân tay của người dùng được thu chụp cùng với thông tin cá nhân và lưu trữ trong hệ thống sinh trắc học Các đặc tính sinh trắc học này thường được thu nhận từ thiết bị vật lý chụp ảnh vân tay, và quá trình kiểm tra chất lượng được thực hiện để đảm bảo độ tin cậy của mẫu Mô đun trích chọn thuộc tính sẽ tạo ra tập đặc trưng, trong khi mô đun tạo bản mẫu sẽ sử dụng tập này để tạo mẫu lưu trữ, kèm theo thông tin cá nhân như số định danh, tên, giới tính, và nơi trú Các tiến trình tiếp theo sẽ dựa vào các đặc trưng đã được trích chọn từ quá trình lấy mẫu.
Các giải thuật đối sánh đặc trưng vân tay được sử dụng để so sánh các đặc trưng của hai vân tay khác nhau Kết quả của quá trình đối sánh này được áp dụng trong hai bài toán xác thực sinh trắc học chính là xác minh vân tay (verification) và nhận dạng vân tay (identification).
Bài toán xác minh định danh là quá trình kiểm tra danh tính của một cá nhân, trong đó một định danh như tên người dùng hoặc mã PIN được cung cấp Hệ thống sinh trắc học thu thập các đặc trưng sinh học của cá nhân và xử lý chúng qua mô-đun trích xuất thuộc tính để tạo ra một tập hợp đặc trưng.
Hình 1.1: Quá trình thẩm định vân tay
Kết quả đặc trưng s được đưa vào bộ đối sánh để so sánh với bản mẫu mà chủ thể tuyên bố, nhằm đưa ra quyết định phù hợp Hiện nay, thẻ thông minh rất phổ biến và thường dựa trên công nghệ Java Card Tuy nhiên, Java Card không hỗ trợ một số kiểu dữ liệu như long, double, và float, dẫn đến bài toán đối sánh vân tay trên thẻ có đặc điểm khác biệt so với trên máy tính Các đặc trưng tính toán trên thẻ thường đơn giản hơn và không hỗ trợ các phép tính phức tạp như phép xoay vân tay.
Bài toán định danh (identification) là quá trình mà trong đó chủ thể không cần khai báo định danh trực tiếp Hệ thống sẽ tiến hành so sánh các đặc trưng được trích xuất từ mẫu sinh trắc học đã thu thập với các bản mẫu trong hệ thống lưu trữ Kết quả của quá trình này có thể là một danh sách các mẫu, có thể trống nếu không tìm ra mẫu phù hợp.
Quá trình định danh vân tay trong một cơ sở dữ liệu lớn yêu cầu tính toán mạnh mẽ Để tăng tốc độ, giai đoạn lọc vân tay thường được áp dụng nhằm nhanh chóng xác định các mẫu ứng viên trước khi thực hiện bước đối sánh chi tiết Giai đoạn này thường sử dụng các môi trường tính toán hiệu năng cao như cụm máy tính cluster và bộ xử lý đồ họa GPU.
1.2 Đặc trƣng trích xuất từ ảnh vân tay
Vân tay là những đường cong đặc trưng trên ngón tay, thường chạy song song, có thể thay đổi hướng và kết thúc đột ngột Các đặc điểm của vân tay được phân loại theo các mức độ khác nhau, từ cái nhìn tổng quát đến chi tiết, giúp nhận diện và phân tích chính xác hơn.
Các đặc trưng mức 1 dễ dàng nhận diện bằng mắt thường, bao gồm hướng đường vân tại một điểm ảnh và các điểm đơn nhất từ ảnh vân tay, cụ thể là điểm singular.
Hình 1.3: Thu c t nh m c m th n t n v các h n đ n vân a v th n t n v các đ m đ n nh t m u đ đ m m u anh đ m tam phân
Thông tin về hướng đường vân thường được tính dựa trên thông tin tại điểm ảnh đó và các giá trị lân cận
Ảnh vân tay có hai loại điểm đơn nhất: điểm lõi (core) và điểm tam phân (delta) Điểm lõi là nơi có sự biến đổi đột ngột về hướng của đường vân, trong khi điểm tam phân là điểm hội tụ của các vùng vân với hướng khác nhau Thông thường, một ảnh vân tay chứa từ 1 đến 2 điểm đơn nhất, nhưng trong một số trường hợp, có thể thiếu hoặc khó xác định các điểm này.
Các đặc trưng mức 2 được trích xuất từ ảnh vân tay là các điểm chạc minutiae Các điểm chạc thường được chia làm 2 loại:
- Điểm kết thúc l n ridge ending : là điểm mà tại đó, đường vân kết thúc
- Điểm r nhánh bifurcation : là điểm mà tại đó, một đường vân được tách làm hai đường vân khác nhau H nh 1.4-b).
Đặc trưng trích xuất từ ảnh vân tay
Các đặc trưng mức 3 trong nhận dạng vân tay bao gồm các hạt pore trên các đường vân Để thu thập thông tin mức 3, cần sử dụng các máy quét vân tay có độ phân giải cao Do đó, thông tin này ít được áp dụng trong các hệ thống nhận dạng vân tay hiện nay.
1.2.1 Thu ảnh vân tay từ bộ cảm biến
Các ứng dụng sinh trắc học dựa trên vân tay đang phát triển mạnh mẽ nhờ quy trình lấy mẫu đơn giản Hiện nay, có hai phương pháp lấy mẫu chính: lăn mực và sử dụng bộ cảm biến Sự đa dạng trong các thiết bị cảm ứng này góp phần nâng cao hiệu quả và độ chính xác của quá trình nhận diện vân tay.
Hình 1.5: Hình ảnh m t số th t ị y mẫu vân tay
H nh 1.5 minh họa h nh ảnh một số thiết bị s dụng trong quá tr nh thu nhận ảnh vân tay
Các thiết bị lấy mẫu được phân loại theo nguyên lý hoạt động, bao gồm thiết bị dựa trên quang học, sóng âm, nhiệt và điện.
Các bộ cảm biến quang học thường có giá thành thấp nhưng dễ bị nhiễu tín hiệu Ngược lại, cảm biến sử dụng phản xạ sóng âm mang lại độ chính xác cao hơn và khó bị làm giả, mặc dù giá thành của chúng cao hơn so với các loại cảm biến khác.
1.2.2 Nâng cao chất lƣ ng ảnh vân tay
Chất lượng ảnh vân tay ảnh hưởng lớn đến quá trình trích chọn đặc trưng và thuật toán đối sánh Ảnh vân tay có độ tương phản cao giữa các đường vân và vùng không vân sẽ cho kết quả tốt hơn Hình 1.6 minh họa sự giảm dần chất lượng của ảnh vân tay từ trái sang phải.
Ảnh vân tay có chất lượng thấp thường có độ tương phản kém và nhiều nhiễu, dẫn đến khó khăn trong việc phát hiện các điểm chạc và đặc trưng của vân tay Điều này gây trở ngại cho quá trình đối sánh vân tay Thuật toán nâng cao chất lượng ảnh nhằm tăng cường độ tương phản của các cấu trúc đường vân, từ đó cải thiện khả năng nhận diện và phân tích vân tay.
Hình 1.6: T trá san phả ch t n ảnh vân tay ảm d n
Bộ lọc Gabor là một công cụ hiệu quả để nâng cao chất lượng ảnh, với hai đặc tính chính là chọn lọc tần số và chọn lọc hướng Để áp dụng bộ lọc này, cần xác định bốn tham số quan trọng: (hướng của bộ lọc), f (tần số sóng hình sin), x và y (các hằng số của hàm Gaussian theo trục x và y) Tham số xác định hướng của đường vân, trong khi f liên quan đến số điểm ảnh giữa các đường vân Việc lựa chọn giá trị cho x và y rất quan trọng; nếu hai tham số này quá lớn, có thể loại bỏ nhiều nhiễu nhưng sẽ tạo ra đường vân sai, trong khi nếu quá nhỏ, sẽ không hiệu quả trong việc loại bỏ nhiễu.
Bộ lọc Gabor là công cụ hiệu quả trong việc nâng cao chất lượng ảnh, giúp loại bỏ nhiễu và xác định chính xác cấu trúc đường vân của ảnh Khi áp dụng bộ lọc Gabor tại mỗi điểm ảnh của ảnh vân tay, nó cho phép cải thiện rõ rệt độ rõ nét và độ chính xác của hình ảnh.
Chikkerur và cộng sự đã đề xuất một phương pháp nâng cao chất lượng ảnh dựa trên phân tích Short Time Fourier Transform (STFT) So với các phương pháp sử dụng bộ lọc Gabor, STFT có lợi thế vượt trội vì không yêu cầu tính toán chính xác định hướng cục bộ của đường vân và tần số vân tay Điều này giúp cải thiện khả năng trích xuất các đặc trưng cần thiết cho giai đoạn cuối của hệ thống nhận dạng Ngược lại, các phương pháp bộ lọc Gabor thường gặp khó khăn trong việc xác định tần số ảnh, dẫn đến cấu trúc đường vân không hoàn hảo.
Gần đây, Sahasrabudhe và cộng sự đã áp dụng phương pháp học máy, cụ thể là mô hình mạng CDBN (Convolutional Deep Belief Network), để cải thiện chất lượng ảnh vân tay, mang lại kết quả khả quan.
Hình 1.8: Nân cao ch t n ảnh vân tay t trá qua phả ảnh ốc sử dụn c Ga or c STFT v mạn n ron CD N 65
Nghiên cứu cho thấy rằng việc sử dụng mạng C N để nâng cao chất lượng ảnh vân tay mang lại kết quả tốt hơn so với các phương pháp truyền thống như bộ lọc Gabor và ST T Cụ thể, trong thực nghiệm trên cơ sở dữ liệu vân tay VC2002, phương pháp C N đạt sai số R là 7.40, thấp hơn đáng kể so với sai số R của phân tích ST T và Gabor, lần lượt là 8.79 và 8.47.
1.2.3 Tách đặc trƣng điểm chạc
Có nhiều phương pháp để trích chọn điểm chạc từ ảnh vân tay đã được nâng cao chất lượng Các phương pháp truyền thống thường bao gồm ba bước chính: chuyển đổi ảnh sang dạng nhị phân (binarization), làm mảnh (thinning) và phát hiện điểm chạc.
Quá trình nhị phân hóa chuyển đổi ảnh đa mức xám thành ảnh nhị phân, trong đó màu đen biểu thị đường và màu trắng biểu thị nền Một phương pháp đơn giản để thực hiện nhị phân hóa là sử dụng ngưỡng, nhưng phương pháp này không hiệu quả với các ảnh có nhiễu Do đó, một phương pháp tốt hơn là áp dụng các mặt nạ hình vuông và xoay chúng theo hướng của đường vân.
Mục tiêu của quá trình làm mảnh là điều chỉnh các đường vân về kích thước chính xác của một điểm ảnh, đồng thời giữ nguyên các cấu trúc kết nối quan trọng Tuy nhiên, phương pháp này có thể gây ra việc phát hiện sai các điểm chạc Do đó, các thủ tục hậu xử lý thường được áp dụng để loại bỏ những điểm chạc không chính xác.
Hình 1.9: K t quả quá trình nhị phân h a v m mảnh ảnh vân tay
H nh 1.9 minh họa kết quả của quá tr nh nhị phân hóa ảnh và làm mảnh ảnh vân tay
Điểm chạc trên ảnh nhị phân được xác định dựa vào giá trị cn (crossing number) của các điểm ảnh Giá trị cn cho từng điểm ảnh m i được tính toán theo một công thức cụ thể.
Bài toán đối sánh vân tay dựa trên điểm chạc
Hình 1.14: Các oạ đ m chạc v th n t n v đ m chạc Hình a đ m t th c đ n vân Hình đ m đ đ n vân tách m
Hình 1.14 minh họa hai loại điểm chạc được sử dụng trong thuật toán đối sánh, bao gồm các điểm kết thúc của đường vân và điểm chạc của đường vân r Mỗi điểm chạc được đặc tả bằng ba tham số {x, y, θ}, trong đó x và y là vị trí của điểm chạc, còn θ là góc hướng của điểm chạc.
1.3.1 Phát biểu bài toán ài toán đối sánh vân tay dựa trên điểm chạc là t m ra tập con các điểm trùng khớp lớn nhất có thể từ 2 tập đặc trưng điểm chạc của hai vân tay cho trước.Ví dụ một ph p đối sánh trong h nh 1.15 Chi tiết bài toán đối sánh giữa 2 tập điểm chạc được định nghĩa như sau: ịnh nghĩa bài toán đ i sánh [49]: Cho 2 vân tay và được biểu diễn thông qua các tập điểm chạc
T m ph p căn ch nh biến đ i h nh học () sao cho tối đa các cặp điểm chạc giữa 2 vân tay có thể phù hợp với nhau
Hình 1.15: M nh hoạ đố sánh a t p đ m chạc
Quá tr nh căn ch nh thường liên quan đến ph p dịch chuyển và ph p xoay Và có thể liên quan thêm đến một số ph p biến đ i như :
Tỷ lệ giãn 𝑠 giữa các ảnh vân tay phụ thuộc vào độ phân giải của từng ảnh, vì máy quét vân tay có khả năng thực thi các chế độ phân giải khác nhau.
- iến đ i vặn m o do lực lấy vân tay khác nhau dẫn đến sự vặn m o Các mô tả sau không x t sự biến đ i về t lệ và vặn m o
Công thức hàm dưới đây thực hiện việc ánh xạ điểm chạc từ vân tay vào biện pháp dịch chuyển T với các giá trị cụ thể, đồng thời áp dụng phương pháp xoay R theo chiều ngược kim đồng hồ với góc tính từ tọa độ gốc.
2 điểm chạc và được coi là phù hợp sau quá tr nh căn ch nh s dụng hàm () nếu thỏa mãn các ràng buộc:
- Khoảng cách 𝑠 giữa hai điểm chạc sau khi căn ch nh không vượt quá ngưỡng t s
Sự khác biệt giữa hướng của hai điểm chạc sau khi căn chỉnh không vượt quá ngưỡng t θ Phép toán đối sánh vân tay có thể được mô tả bằng cách tối ưu hóa hàm mục tiêu với bộ tham số ( ) để đạt được giá trị cực đại.
Trong bài toán đối sánh vân tay, hàm không biết trước giữa các điểm chạc là một yếu tố quan trọng Nếu hàm được xác định, việc giải quyết bài toán sẽ trở nên đơn giản hơn, cho phép xác định bộ ba tham số từ cặp điểm đối sánh Tuy nhiên, trong thực tế, các tham số căn bản và hàm thường không được biết trước, khiến cho việc đối sánh giữa hai tập điểm chạc trở thành một thách thức lớn.
Hình 1.16 minh họa một số cặp điểm chạc khoanh tròn phù hợp, đáp ứng ngưỡng khoảng cách t_s và ngưỡng góc t_θ khác nhau Hai tham số t_s và t_θ thể hiện các tiêu chí chịu lỗi cho mỗi phép so sánh tương ứng.
Giá trị của hai tham số t s và t θ có thể được xác định dựa vào kỹ thuật đối sánh Ví dụ, trong thuật toán MTK Modify Tico Kuosmanen, các tác giả đã chứng minh rằng kết quả đối sánh vân tay đạt hiệu quả tốt nhất với ngưỡng khoảng cách t s = 12 và ngưỡng góc t θ = π/6.
Hình 1.16: Các c p đ m đ c co ph h p sau quá trình c n ch nh n u th a mãn các n n v hoản cách v c Các c p đ m đ c hoanh tr n ph h p v n n hoản cách t s v n n c t θ
1.3.2 Một số khó khăn trong quá trình đối sánh
Thuật toán đối sánh vân tay so sánh hai mẫu vân tay và thường trả về giá trị độ tương đồng, thường nằm trong khoảng từ 0 đến 1, hoặc đưa ra quyết định phù hợp hay không Hầu hết các thuật toán này sử dụng các biểu diễn trung gian của vân tay thông qua bước trích chọn đặc trưng Đối sánh vân tay là một thách thức lớn do nhiều nguyên nhân khác nhau.
Vị trí đặt vân tay trên thiết bị lấy mẫu có thể khác nhau, dẫn đến sự dịch chuyển của các vùng vân tay được thu nhận.
- Xoay: cùng một vân tay có thể bị xoay các góc khác nhau trên thiết bị cảm biến thu nhận vân tay
Việc đặt ngón tay không đúng vị trí và xoay vân tay có thể khiến một số phần của vân tay không nằm trong vùng thu nhận của thiết bị cảm ứng, dẫn đến tình trạng trùng lặp một phần giữa các vân tay.
Vặn m o không tuyến tính xảy ra khi ánh xạ hình dạng ba chiều của vân tay vào bề mặt hai chiều của thiết bị cảm biến, dẫn đến phương pháp ánh xạ phi tuyến tính.
Điều kiện của da và lực p khi lấy mẫu vân tay ảnh hưởng lớn đến chất lượng của dấu vân Mức độ khô hoặc ẩm, cùng với lực p khi lấy mẫu, có thể dẫn đến việc thu nhận vân tay không chính xác, với các đường vân bị nhiễu và khác biệt giữa các lần lấy mẫu.
Hình 1.17: M t số thu nh n hác nhau c a c n m t vân tay
Các cặp hình ảnh trong Hình 1.17 minh họa sự khác biệt của cùng một vân tay Sự khác nhau này có thể xuất phát từ việc thay đổi vị trí đặt tay, xoay vân tay hoặc do nhiễu trong quá trình thu thập mẫu vân tay.
H nh 1.18 thể hiện sự khác biệt về vị trí các điểm chạc giữa hai hình ảnh vân tay, do quá trình lấy mẫu bị ảnh hưởng bởi sự khác nhau về lực ép lên vân tay.
Hình 1.18: Ảnh n trá v c n đ u Ảnh n phả ị méo do c m hác nhau
Một số nghiên cứu đối sánh vân tay dựa trên điểm chạc
Hiện nay, có nhiều thuật toán đối sánh vân tay dựa trên điểm chạc, được phân loại theo hai hướng tiếp cận chính: đối sánh toàn cục (global matching) và đối sánh cấu trúc cục bộ (local matching) Trong đó, các thuật toán dựa trên cấu trúc cục bộ thường cho kết quả tốt hơn khi xử lý các biến đổi phi tuyến và trùng lặp một phần so với các phương pháp đối sánh toàn cục.
[56] Các phần tiếp theo s mô tả chi tiết hơn về các hai cách tiếp cận này
Trong cách tiếp cận này, quá trình đối sánh tìm ra phép căn chỉnh cho toàn bộ các điểm cùng lúc, với hàm chuyển đổi giả thiết là toàn cục và giống nhau tại tất cả các điểm của vân tay Bài toán đối sánh tập các điểm chạc có thể được coi là một trường hợp của bài toán đối sánh điểm, trong đó hai tập điểm có thể có quan hệ hình học Thường thì, một số điểm tương ứng được biết trước, khiến bài toán trở thành tìm phép biến đổi hình học tối ưu liên quan đến hai tập Tuy nhiên, trong bài toán đối sánh vân tay, điểm tương ứng giữa hai vân tay thường không được biết, điều này làm cho bài toán đối sánh vân tay trở thành một thách thức khó khăn.
Ratha và cộng sự đã đề xuất một phương pháp đối sánh điểm chạc dựa trên biến đổi Hough tổng quát, áp dụng một số kỹ thuật đối sánh điểm để cải thiện hiệu quả trong việc nhận diện và phân tích dữ liệu.
Gọi * ( )+ là tập hợp các điểm chạc của vân tay thứ nhất và * ( )+ là tập hợp các điểm chạc của vân tay thứ hai Thuật toán s xem x t không gian biến ph p toán dịch chuyển và xoay giữa các cặp điểm chạc, bao gồm các bộ tứ với giá trị Δx, Δy, θ, s Trong đó, Δx và Δy đại diện cho phép dịch chuyển giữa hai vân tay, θ là góc xoay giữa chúng, và s là tham số giãn scale, nhằm điều chỉnh sự khác biệt về kích thước ảnh do các scanner khác nhau.
Thuật toán 1.1: Thu t toán đố sánh to n cục d a tr n n đổ Hou h 60]
Không gian giá trị cho phép xoay được chia thành các giá trị khác nhau Để xác định từng giá trị xoay cho các cặp điểm, ta sử dụng lệnh kiểm tra góc Một phương pháp xoay được coi là phù hợp cho cặp điểm nếu nó đáp ứng ngưỡng góc đã định Tham số giãn scale giữa các ảnh được xác định dựa trên sự khác biệt về kích thước của ảnh từ các scanner khác nhau Sau đó, ta áp dụng phương pháp dịch chuyển và thực hiện xoay góc Cuối cùng, lượng hóa phương pháp dịch chuyển giữa các cặp điểm được lưu trữ vào bộ giá trị, và bộ giá trị này sẽ được tăng đề c theo tham số s.
Bộ tham số tối ưu cuối cùng ∆x * , ∆y * , ∆θ * , ∆s * được xác định bằng bộ giá trị có nhiều đề cử nhất Để cải thiện độ chính xác và xem xét tác động của hiện tượng biến đổi phi tuyến khi lấy mẫu vân tay, một phương pháp cải tiến cho biến đổi Hough thường được áp dụng là xem xét biến đổi cho cặp điểm chạc không chỉ cho một ô rời rạc mà còn cho các ô thuộc không gian biến đổi lân cận Tuy nhiên, nếu chia không gian biến đổi Hough thành quá nhiều bộ giá trị, sẽ yêu cầu quá trình tính toán lớn, trong khi nếu chia thành số ít bộ giá trị, số lượng tính toán sẽ giảm nhưng có thể dẫn đến các đối sánh không chính xác.
Đề xuất một cách tiếp cận biến đổi Hough đa mức, bắt đầu bằng việc sử dụng biến đổi Hough trong không gian có ít bộ giá trị để nhanh chóng tìm kiếm các đối sánh tiềm năng Sau đó, thực hiện biến đổi Hough chi tiết hơn trên các đối sánh đã tìm ra Phương pháp đối sánh toàn cục cho thấy hiệu quả tốt trên dữ liệu nhiễu hoặc không đầy đủ Tuy nhiên, độ phức tạp tính toán của thuật toán yêu cầu thời gian lớn trong quá trình đối sánh, điều này có thể không phù hợp với các hệ thống AFIS có cơ sở dữ liệu lớn Do đó, nhiều phương pháp đối sánh toàn cục thường sử dụng các điểm căn chỉnh trước để làm cơ sở cho các phép dịch chuyển và xoay, trong đó các điểm căn chỉnh thường dựa trên các điểm đơn nhất của vân tay.
Chikkerur và cộng sự đã tích hợp quá trình căn chỉnh dựa trên điểm lõi vào thuật toán đối sánh vân tay, giúp nâng cao tốc độ xử lý của thuật toán lên 43% mà không ảnh hưởng đến độ chính xác Để duy trì độ chính xác, quá trình căn chỉnh chỉ được thực hiện khi điểm đơn nhất phát hiện là tin cậy Tuy nhiên, việc phát hiện các điểm đơn nhất từ ảnh vân tay có thể gặp khó khăn do chất lượng ảnh thấp hoặc do một số vân tay không chứa các điểm đơn nhất.
Phần tiếp theo của luận án trình bày cách tiếp cận phổ biến trong các thuật toán đối sánh vân tay, dựa trên việc đối sánh các cấu trúc cục bộ để mô tả các điểm chạc.
1.4.2 Đối sánh cục bộ Để giảm bớt quá tr nh chuyển đ i giữa tập các điểm chạc của các vân tay trong quá tr nh đối sánh s dụng phương pháp đối sánh toàn cục Phương pháp đối sánh cục bộ s so sánh các điểm chạc của hai vân tay dựa trên các cấu trúc cục bộ của các điểm chạc Các cấu trúc cục bộ được tạo ra dựa trên quan hệ của điểm chạc và các điểm lận cận Các cấu trúc này có thuộc tính bất biến với các ph p biến đ i toàn cục như dịch chuyển và các ph p toán xoay
Đối sánh cục bộ có lợi điểm về sự đơn giản và độ phức tạp tính toán thấp, đồng thời chịu ảnh hưởng của biến đổi mô hình vân tay tốt hơn so với đối sánh toàn cục Tuy nhiên, việc đối sánh cấu trúc cục bộ không đảm bảo rằng các kết quả đạt yêu cầu ở mức cục bộ cũng sẽ thỏa mãn ở mức toàn cục Do đó, sau giai đoạn đối sánh cục bộ, thường cần thêm giai đoạn gia cố để đảm bảo các đối sánh cục bộ vẫn đáp ứng được tiêu chí toàn cục.
1.4.2.1 Một số cấu trúc cục bộ biểu diễn điểm chạc Đối sánh cục bộ bao gồm việc so sánh các cấu trúc cục bộ của các điểm chạc Đối sánh các cấu trúc cục bộ cho ph p nhanh chóng xác định các cặp điểm chạc có thể đối sánh với nhau và s dụng các cặp này như là ứng c viên cho việc căn ch nh 2 vân tay Các cấu trúc cục bộ s dụng các thông tin xung quanh điểm chạc để làm thông tin biểu diễn cho điểm chạc Có khá nhiều các cấu trúc cục bộ đã được đề xuất b i các tác giả khác nhau
H nh 1.21 minh họa một số cấu trúc cục bộ được s dụng để biểu diễn cho các điểm chạc được khảo sát trong [49]
Hình 1.21: M t số c u tr c cục đ c sử dụn đ u d ễn cho đ m chạc 9
Các cấu trúc cục bộ có thể được chia thành một số phương pháp dựa trên một số tiêu chí phân loại như:
- Dựa trên láng giềng gần nhất: S dụng biểu diễn gồm K điểm chạc gần với điểm chạc cần xem x t
Hình 1.22: u d ễn k-p et Ch erurv c n s 6 Các đ m chạc án n đ c a ch n phân phố đ u v o v n un quanh đ m chạc tâm
Nhiễu trong ảnh có thể gây khó khăn trong việc phát hiện điểm chạc, tập trung vào một vùng nhất định Để giảm thiểu nhiễu và đảm bảo sự phân bố đồng đều, Chikkerur và các cộng sự đã đề xuất cấu trúc cục bộ, trong đó K-plet được tạo bởi K điểm chạc gần nhất, được lựa chọn sao cho phân bố đều trong bốn vùng xung quanh điểm chạc.
Một cách tương tự, Kwon và các cộng sự [35 chia không gian xung thành K vùng và chọn các điểm gần nhất trong m i vùng
Dựa trên bán kính cố định, các láng giềng được xác định bởi tất cả các điểm chạc có khoảng cách nhỏ hơn R so với điểm chạc xem xét Sự khác biệt giữa các điểm chạc phụ thuộc vào mật độ điểm chạc xung quanh, điều này có thể dẫn đến việc đối sánh các cục bộ phức tạp hơn Tuy nhiên, phương pháp này có khả năng chịu lỗi tốt hơn trong các tình huống phát hiện sai hoặc thiếu điểm chạc.
Tico và cộng sự đã đề xuất một cấu trúc cục bộ cho điểm chạc, không dựa vào thông tin từ các điểm chạc xung quanh Thay vào đó, họ sử dụng các điểm lấy mẫu từ các hướng của các đường vân xung quanh điểm chạc H, như được mô tả trong hình 1.23.
Hình 1.23: u d ễn đ m chạc d a tr n các đ m tr n các đ n vân h n un quanh đ m chạc T co v c n s 67
CẢI TIẾN GIAI ĐOẠN GIA CỐ CỦA THUẬT TOÁN ĐỐI SÁNH DỰA TRÊN ĐIỂM CHẠC
Các phương pháp gia cố thường s dụng
Bước tiếp theo trong việc đối sánh các cấu trúc cục bộ là gia cố nhằm kiểm tra xem các cấu trúc này còn phù hợp với mức toàn cục sau khi đã được căn chỉnh.
Trong hình 2.1, điểm chạc được so sánh với các cấu trúc cục bộ của các điểm chạc khác để xác định sự phù hợp Tuy nhiên, sau khi điều chỉnh vị trí, sự phù hợp này có thể không còn chính xác nữa.
Hình 2.1: c a cố n quan đ n v c c n ch nh n đổ oay v dịch chuy n
Quá trình gia cố liên quan đến các phương pháp biến đổi xoay và dịch chuyển Sau khi thực hiện bước căn chỉnh, tất cả các cấu trúc cục bộ sẽ được xác định lại để kiểm tra xem chúng có còn đáp ứng các ràng buộc đã đề ra hay không.
- Khoảng cách giữa hai điểm chạc sau khi căn ch nh không vượt quá ngưỡng t s xác định trước
- Sự khác nhau giữa hướng của hai điểm chạc sau khi căn ch nh không vượt quá ngưỡng t θ
Chi ti t công thức bi n đ i
- Gọi, - là ph p dịch chuyển giữa 2 điểm chạc và và là góc quay để hướng của điểm chạc hợp với
- Gọi là vị trí của s dụng ph p biến đ i s dụng tham số căn ch nh , - và
Cặp điểm chạc phù hợp với điểm chạc của sau ph p dịch chuyển nếu:
Khoảng cách từ và nhỏ hơn ngưỡng khoảng cách và góc giữa + ) và nhỏ hơn ngưỡng góc Công thức 1.1)
Có nhiều kỹ thuật gia cố khác nhau được đề xuất b i các tác giả như:
Kỹ thuật gia cố đơn giản nhất sử dụng cặp điểm đối sánh cục bộ có giá trị tương đồng lớn nhất để xác định cặp điểm căn chỉnh giữa hai vân tay trong quá trình gia cố toàn cục.
Việc chọn cặp điểm chạc có giá trị tương đồng lớn nhất không luôn đảm bảo là biến đổi tối ưu ở mức toàn cục Chẳng hạn, như trong hình 2.2, một cặp điểm đối sánh có giá trị tương đồng cao nhưng lại không phải là đối sánh chính xác.
Hình 2.2: M t c p đ m đố sánh sa c á trị t n đ n n nh t 7
Nhiều tác giả đã thực hiện các phương pháp biến đổi khác nhau trong quá trình căn chỉnh bằng cách sử dụng nhiều cặp ứng viên Cuối cùng, họ chọn biến đổi có số lượng cặp đối sánh toàn cục lớn nhất Ví dụ, Medina và cộng sự đã giảm số cặp đối sánh cục bộ bằng cách lựa chọn các điểm chạc p và q có giá trị tương đồng cao nhất, từ đó thực hiện phương pháp biến đổi căn chỉnh dựa trên tập hợp các cặp điểm đã được hạn chế.
Sắp xếp các cặp điểm phù hợp cục bộ theo thứ tự độ tương đồng giảm dần và chọn ra T cặp điểm có giá trị tương đồng lớn nhất để sử dụng cho quá trình căn chỉnh Các phương pháp này thường mang lại độ chính xác cao hơn so với những cách tiếp cận dựa trên biến đổi đơn nhất.
Để giảm thiểu tác động của hiện tượng vặn mỏ không tuyến tính trong vân tay do lực ấn không đồng nhất, các tác giả đã áp dụng phương pháp biến hình phức hợp Bazen và cộng sự sử dụng mô hình thin-plate spline (TPS) để điều chỉnh vân tay sau khi căn chỉnh, trong khi Kwon và cộng sự giới thiệu một phương pháp hiệu quả hơn dựa trên mô hình tam giác hóa nhằm sửa chữa ảnh hưởng của việc vặn mỏ Hình 2.3 so sánh quá trình đối sánh sử dụng phương pháp căn chỉnh thông thường với kết quả đối sánh sau khi kết hợp thêm nắn chỉnh dựa trên mô hình TPS và mô hình tam giác hóa.
Hình 2.3: T trá san c n ch nh h n d n n n ch nh sử dụn n n ch nh T S sử dụn n n ch nh cục d a tr n tam ác 35
Cùng ý tư ng s dụng phương pháp nắn ch nh cục bộ, HTNguyen và cộng sự
[82 đề xuất chia ảnh vân tay làm 9 vùng và tiến hành nắn ch nh TPS các điểm chạc trên 9 vùng đó
Các phương pháp nắn chỉnh sau khi xác định các cặp điểm chạc phù hợp sử dụng phương pháp căn chỉnh dựa trên biến hình có thể nâng cao độ chính xác của phương pháp đối sánh Tuy nhiên, việc áp dụng phương pháp nắn chỉnh cũng có thể ảnh hưởng đến tốc độ thực thi của các thuật toán đối sánh vân tay.
Quá trình gia c gia tăng (incremental consolidation) là một phương pháp trong đó không tìm kiếm tất cả các cặp điểm chạc phù hợp cục bộ ngay lập tức, mà thay vào đó, xem xét một cặp điểm làm gốc Các cặp điểm chạc có cấu trúc cục bộ sẽ được xác định là láng giềng của cặp điểm gốc Quá trình này tiếp tục với việc thêm các cặp điểm mới, dẫn đến việc thuật toán tạo ra một đồ thị các điểm chạc phù hợp với nhau.
H nh 2.4 minh họa một đồ thị các điểm chạc phù hợp được t m ra trong thuật toán K-plet được đề xuất b i Chikkeur và cộng sự [6]
Hình 2.4: Quá trình ây d n cây đố sánh tron K-plet [6]
Theo nghiên cứu của Conti và cộng sự, việc chia ảnh thành nhiều vùng khác nhau và nối kết kết quả đối sánh từ từng vùng giúp tạo ra kết quả cuối cùng Trong khi đó, Cao và cộng sự đã áp dụng phương pháp tối ưu hóa trong quá trình xây dựng cây gia tăng nhằm giảm thiểu ảnh hưởng của vặn m o vân tay.
Giải thuật gia cố đề xuất
Mục này trình bày các cải tiến đề xuất cho hai phương pháp gia cố, bao gồm gia cố dựa trên biến hình transformations và gia cố dựa trên gia tăng incremental, như đã được thảo luận ở mục trước Kết quả nghiên cứu liên quan đã được công bố trong các tài liệu [LHHai1] và [LHHai4].
2.2.1 Đề xuất cải tiến cho phương pháp gia cố dựa trên ph p biến hình
Theo phương pháp truyền thống, sau khi xác định căn chỉnh trong gia cố dựa trên biến hình, các cặp điểm phù hợp cục bộ được kiểm tra so với cặp điểm trung tâm làm căn chỉnh Mặc dù các cặp điểm phù hợp cục bộ có thể tương thích với cặp điểm căn chỉnh, nhưng chúng có thể không tương thích lẫn nhau.
H nh 2.5 minh họa các cặp điểm đối sánh được tạo ra bằng thuật toán đối sánh sử dụng phương pháp gia cố truyền thống Tuy nhiên, không phải tất cả các cặp điểm này đều phù hợp với nhau.
Cặp điểm chạc số 1 được sử dụng làm phép căn chỉnh chính, mặc dù cặp điểm chạc (1,4) và (1,3) giữa hai vân tay đều tương thích, nhưng cặp điểm chạc (3,4) lại không phù hợp với nhau.
Hình 2.5 minh họa sự so sánh hình ảnh sử dụng các cặp điểm làm tâm trong luận án đề xuất Sau khi căn chỉnh với cặp điểm trung tâm, các cặp điểm phù hợp cục bộ không chỉ được kiểm tra tính phù hợp với cặp điểm làm tâm mà còn cần xem xét sự tương thích với các điểm chạc đã được căn chỉnh khác Cụ thể, đối với cặp điểm chạc số 4, việc kiểm tra không chỉ dừng lại ở cặp điểm chạc số 1 mà còn phải xác định tính phù hợp với các cặp điểm chạc số 2 và số 3.
Thuật toán gia cố đề xuất bắt đầu bằng việc sắp xếp tất cả các cặp điểm chạc phù hợp cục bộ theo giá trị độ tương đồng giảm dần Sau đó, các cặp điểm không phù hợp với các điểm có độ tương đồng lớn hơn trong danh sách sẽ được loại bỏ.
Thuật toán 2.2: Tìm các c p đ m ph h p v nhau t t p các c p đ m ph h p v c p đ m c n ch nh
Trong quá trình xử lý dữ liệu, lệnh 3 yêu cầu kiểm tra từng cặp điểm ( ) với tất cả các cặp điểm chạc ( ) đã được đưa vào trước đó Hai cặp điểm chạc được xác định là phù hợp nếu chúng đáp ứng các tiêu chí về ngưỡng khoảng cách và ngưỡng góc theo Công thức 2.3.
Kết quả cuối cùng của tập s bao gồm các cặp điểm chạc không chỉ không phù hợp với cặp điểm chạc làm căn cứ chính, mà còn tương thích với các cặp điểm chạc khác trong tập.
Độ phức tạp của thuật toán 2.2 trong trường hợp tồi nhất là O(n), khi không tìm được cặp phù hợp nào, yêu cầu duyệt tất cả các cặp Ngược lại, nếu tất cả các cặp đều phù hợp, độ phức tạp sẽ là O(n*(n-1)/2), tương ứng với số lần duyệt là n*(n-1)/2.
Số lượng cặp điểm chạc phù hợp với cặp điểm căn ch nh thường không nhiều, trung bình chỉ có khoảng 6 cặp điểm chạc phù hợp giữa hai vân tay trên CS L VC 2002 Do đó, cần thực hiện tối đa 36 phép kiểm tra giữa các cặp điểm chạc để đảm bảo tính chính xác.
Hình 2.6: K t quả đố sánh h sử dụn a cố đ u t
H nh 2.6 trình bày kết quả của quá trình gia cố đề xuất, trong đó tất cả các cặp điểm chạc đều được kiểm tra lẫn nhau Kết quả cho thấy tất cả các cặp điểm chạc tìm ra đều phù hợp, ngoại trừ cặp điểm chạc số 4, đã bị loại bỏ do không tương thích với cặp điểm chạc số 3.
2.2.2 Đề xuất cải tiến cho phương pháp gia cố gia tăng
Trong phương pháp gia cố dựa trên gia tăng, Chikkeur và cộng sự đã nghiên cứu quy trình xây dựng đồ thị đối sánh Khi thêm một cặp điểm chạc vào đồ thị, cặp này sẽ được kiểm tra với các cặp điểm liền kề trước đó để đảm bảo tính chính xác và hiệu quả của đồ thị.
Hình 2.7: Quá trình ây d n cây đố sánh tron -plet
Trong thuật toán K-plet, quá trình xây dựng cây đối sánh được minh họa qua H nh 2.7 Điểm lân cận thuộc vào tập k-plet của s được xem xét để thêm vào đồ thị đối sánh.
Thuật toán 2.3: Thu t toán K-plet [6]
Hàm QU U dòng lệnh 5, 6 s lấy cặp điểm chạc phù hợp ( ) từ danh sách để t m các cặp lân cận phù hợp ( ) đưa vào đồ thị
Hàm NQU U dòng lệnh 9.ii và 9.iii sẽ đưa các cặp điểm lân cận vào cuối hàng đợi nếu chúng chưa được thăm và phù hợp với điều kiện đã định Đồ thị sẽ được thăm theo chiều rộng, đảm bảo hiệu suất và độ chính xác của thuật toán.
Luận án đề xuất phương pháp gia cố dựa trên biến hình, với nhận xét rằng cặp điểm chạc có thể không phù hợp với các cặp điểm đã tìm ra trước đó, mặc dù chúng phù hợp với cặp điểm liền kề trong đồ thị Khi một cặp điểm mới được thêm vào đồ thị, không chỉ cần kiểm tra với cặp điểm liền kề mà còn cần xem xét các cặp điểm đã được thêm vào trước đó để đảm bảo tính chính xác và hiệu quả trong quá trình đối sánh.
Thuật toán 2.4: Sửa đổ c 9 c a thu t toán K-plet
Dòng lệnh 10 b sung s kiểm tra cặp điểm chạc ( ) với tất cả các cặp điểm chạc ( ) đã được thêm vào đồ thị đối sánh trước đó
Đánh giá giải thuật gia cố đề xuất
Thực nghiệm đánh giá trên một số thuật toán đối sánh vân tay s dụng biểu diễn K-plet, m-Triplets, MCC s dụng CS L vân tay FVC 2002 DB1
Bộ công cụ VeriFinger được sử dụng để tách các đặc trưng điểm chạc từ ảnh vân tay Dữ liệu CS L FVC 2002 DB1 bao gồm 800 ảnh vân tay được thu thập từ nhiều nguồn khác nhau.
Trong nghiên cứu này, 100 vân tay khác nhau đã được thu thập, mỗi vân tay được chụp 8 ảnh với kích thước 500x500 điểm ảnh Để đánh giá các chỉ số R, RM, NRM, đã thực hiện 2800 đối sánh giữa các ảnh cùng vân tay, với mỗi vân tay tạo ra 28 đối sánh (8x7/2) Tổng số đối sánh giữa các ảnh thuộc cùng vân tay là 100x28 = 2800 Ngoài ra, còn có 4950 đối sánh giữa các ảnh vân tay từ các vân tay khác nhau, trong đó mỗi thể hiện đầu tiên của một vân tay được đối sánh với các thể hiện đầu tiên của các vân tay khác, dẫn đến tổng số 4950 đối sánh (100x99/2).
Bảng 2.1 mô tả chi tiết kết quả so sánh đánh giá trên CS L VC 2002 1
Bảng 2.1: K t quả sử dụng ph n pháp a cố đ xu t huật toán EER FMR
FMR Zero hời gian (ms)
K-plet cải tiến 1.28% 1.46% 2.14% 2.96% 29 m-Triplets 1.71% 1.79% 2.68% 3.07% 3.95 m-Triplets cải tiến 1.52% 1.71% 2.42% 2.92% 3.99
Bốn thực nghiệm đánh giá trong bảng 2.1 được thực hiện trên cùng một bộ dữ liệu điểm chạc tách ra từ ảnh vân tay Kết quả đánh giá thuật toán đối sánh dựa trên biểu diễn MCC được sử dụng theo [57] Tuy nhiên, các kết quả này có thể khác với những gì các tác giả công bố, do bộ công cụ trích chọn đặc trưng điểm chạc từ ảnh vân tay trong luận án sử dụng khác với bộ công cụ của các tác giả.
Các thuật toán cải tiến quá trình gia cố đã đề xuất những b i luận án mang lại kết quả chính xác hơn so với thuật toán gốc Sai số trung bình R của ba thuật toán có hiệu suất cao nhất tại FVC 2002 DB1 là 0.2 Các thuật toán này có thể kết hợp thêm các đặc trưng khác của ảnh vân tay, bao gồm thông tin về đường vân, các điểm đơn nhất, và số lượng đường vân giữa các điểm chạc Ngoài ra, việc áp dụng các phương pháp nắn chỉnh sau quá trình gia cố cũng được khuyến nghị.
