Luận văn: Đối sánh vân tay dựa trên thuật toán MCC Minutiae Cylinder Code - ĐH Công Nghệ
Luận văn về đối sánh vân tay sử dụng thuật toán MCC (Minutiae Cylinder Code). Nghiên cứu chuyên sâu về nhận dạng vân tay, bảo mật sinh trắc học.
Trường đại học
Trường Đại học Công nghệChuyên ngành
Công nghệ thông tinNgười đăng
Ẩn danhThể loại
Luận văn thạc sĩPhí lưu trữ
30 PointMục lục chi tiết
Tóm tắt
I. Đối sánh vân tay và Thuật toán MCC Tổng quan và Xu hướng
Nhận dạng vân tay đã được nghiên cứu nhiều năm và đạt được nhiều tiến triển. Rất nhiều nỗ lực vẫn cần thiết để nâng cao hiệu năng của các hệ thống nhận dạng vân tay. Trong hệ thống nhận dạng vân tay, thuật toán đối sánh đóng vai trò quan trọng, quyết định trực tiếp đến chất lượng cũng như hiệu năng của việc nhận dạng. Các thuật toán đối sánh thường sử dụng thêm biểu diễn trung gian được trích xuất từ bước trích chọn thuộc tính để trả lại độ tương đồng hoặc một quyết định nhị phân khi so sánh hai vân tay. Luận văn tập trung tìm hiểu chi tiết một số thuật toán đối sánh vân tay tiêu biểu, đi sâu vào thuật toán MCC đối sánh cho kết quả cao hiện nay dựa trên biểu diễn MCC (Minutiae Cylinder-Code) của Cappelli và cộng sự năm 2010. Từ đó luận văn tiến hành thử nghiệm thuật toán trên bộ dữ liệu vân tay FVC 2002 DB và đánh giá kết quả thu được khẳng định được chất lượng so khớp vân tay dựa trên biểu diễn MCC. Bài toán đối sánh vân tay, bài toán đối sánh vân tay (fingerprint matching) có vai trò quan trọng liên quan đến tốc độ nhận dạng và độ chính xác của quá trình nhận dạng. Đây cũng là một trong những hướng nghiên cứu chủ yếu hiện nay về nhận dạng vân tay.
Với định hướng nêu trên, luận văn có mục tiêu tìm hiểu, nghiên cứu một số thuật toán đối sánh vân tay, trong đó tập trung chính vào thuật toán MCC đối sánh vân tay cho kết quả chính xác cao hiện nay do Cappelli và cộng sự đề xuất vào năm 2010, dựa trên biểu diễn MCC (Minutiae Cylinder-Code) và tiến hành thử nghiệm đánh giá. Mục tiêu này được cụ thể theo những nội dung chính sau: Tìm hiểu tổng quan về nhận dạng vân tay, vai trò của đối sánh vân tay trong nhận dạng vân tay. Khảo sát chi tiết một số thuật toán đối sánh điển hình hiện nay như đối sánh toàn cục, đối sánh cục bộ, đối sánh dựa trên điểm đặc trưng,… Biểu diễn MCC sẽ được chú trọng phân tích để thực nghiệm. Thử nghiệm thuật toán đối sánh vân tay dựa trên biểu diễn MCC và đánh giá kết quả thu được.
1.1. Các phương pháp tiếp cận trong bài toán đối sánh vân tay
Các hệ thống đối sánh vân tay tự động cần chuyển số lượng các điểm đặc trưng có thể đối sánh giữa hai vân tay sang một giá trị chỉ độ tương đồng giữa hai vân tay. Điều này thường được thực hiện bởi công thức sau:
Với k là số lượng điểm đặc trưng có thể đối sánh, m và n là số lượng điểm đặc trưng tương ứng của hai vân tay tham gia quá trình đối sánh. Bên cạnh đó, các thông tin khác có thể được khai thác đặc biệt trong trường hợp ảnh nhiễu và sự hạn chế trong của vùng trùng nhau giữa hai vân tay. Chất lượng điểm đặc trưng có thể sử dụng như trọng số để đánh giá độ tin cậy hay không tin cậy của điểm đặc trưng. Việc đóng góp của các cặp điểm đặc trưng tin cậy nên cao hơn so với đóng góp của các cặp điểm đặc trưng có chất lượng thấp hơn. Chất lượng của điểm đặc trưng có thể được xác định dựa trên chất lượng vùng ảnh mà điểm đặc trưng thuộc vào. Việc chuẩn hóa theo công thức trong hình trên có xu hướng phạt các cặp vân tay có độ chồng lên nhau. Một số đề xuất việc chuẩn hóa hiệu quả hơn, xem xét số lượng điểm đặc trưng thuộc vào vùng giao của hai vân tay sau khi quá trình căn chỉnh tối ưu đã được xác định.
1.2. Tổng quan về bài toán nhận dạng vân tay và vai trò của thuật toán
Nhận dạng vân tay được ứng dụng phổ biến trong các ứng dụng sinh trắc học như kiểm soát truy cập, định danh khách hàng thực hiện giao dịch: ví dụ tại ATM, ngân hàng trực tuyến, quản lý thời gian, sự có mặt của nhân viên tại các tổ chức liên quan đến việc tính toán thời gian lao động, tiền lương. Đến các ứng dụng liên quan đến chính phủ như định danh công dân (hộ chiếu), quản lý xuất nhập cảnh, định danh trong pháp y liên quan đến tội phạm. Trong các ứng dụng sinh trắc học, vân tay được sử dụng rộng rãi và phổ biến nhất do tính đơn giản và thuận tiện trong lấy mẫu, lưu trữ và xử lý dữ liệu.
II. Minutiae Cylinder Code MCC Chi tiết về thuật toán
Đối sánh vân tay dựa trên điểm đặc trưng là cách tiếp cận phổ biến nhất trong các thuật toán đối sánh vân tay. Chuẩn ISO cũng xác định sử dụng các đặc trưng này. Mỗi điểm đặc trưng có thể được mô tả bởi các thuộc tính như vị trí của điểm trong ảnh, hướng của điểm đặc trưng và kiểu của điểm đặc trưng (đường kết thúc - ridge ending hay đường rẽ nhánh - ridge bifurcation), một trọng số chỉ chất lượng của ảnh xung quanh điểm đặc trưng. Hầu hết các thuật toán đối sánh vân tay coi mỗi điểm đặc trưng gồm 3 thông tin (triplet). Vm = { x, y, θ}, với x, y là vị trí của điểm đặc trưng và góc hướng của điểm đặc trưng θ.
Bài toán đối sánh dựa trên điểm đặc trưng là tìm ra phép sắp đặt (alignment) giữa hai tập đặc trưng điểm đặc trưng của hai vân tay sao cho tối đa số lượng các cặp điểm đặc trưng có thể đối sánh. Hiện nay, theo các nghiên cứu khác nhau, biểu diễn cấu trúc cục bộ dựa trên MCC [2] là một trong những mô tả dựa trên điểm đặc trưng chính xác nhất. Ưu điểm chính của biểu diễn này so với các biểu diễn cục bộ khác đó là MCC là cách tiếp cận dựa trên cách tiếp cận sử dụng bán kính cố định (fixed-radius) do đó chịu lỗi tốt hơn đối với tình huống phát hiện thiếu điểm đặc trưng hoặc điểm đặc trưng sai so với cách tiếp cận dựa trên láng giềng gần nhất (neighbor-based). Không giống như các cách tiếp cận sử dụng bán kính cố định truyền thống, MCC dựa vào mã hóa có độ dài cố định, điều này giúp việc tính toán độ tương đồng cục bộ đơn giản.
2.1. Cấu trúc dữ liệu Minutiae Cylinder Code
MCC gán các biểu diễn cục bộ cho mỗi điểm đặc trưng. Mô tả này bao gồm cả quan hệ về khoảng cách và hướng giữa điểm đặc trưng và các điểm đặc trưng lân cận và được biểu diễn như là một hình trụ với đáy và chiều cao liên quan đến khoảng cách và hướng. Hình trụ được rời rạc hóa thành NC = NS x NS x ND hình khối, mỗi khối sẽ có kích thước đáy là S x S và chiều cao là D , trong đó S = 2R/NS và D = 2π/ND. Với mỗi ô (i, j, k), sẽ gán với một giá trị Cm(i, j, k) được tính toán bằng cách tổng hợp các đóng góp của các điểm đặc trưng mt thuộc vào hàng xóm pm (li, j) của x. Các điểm đặc trưng được xác định trong vòng bán kính m3 s so với điểm tâm vl.
2.2. Ưu điểm của thuật toán MCC so với các thuật toán khác
Vấn đề đường bao biên giới được giải quyết đơn giản nhờ kết hợp thêm không gian xung quanh. Cài đặt dựa trên bit giúp việc đối sánh hình trụ nhanh và đơn giản, giúp giảm thời gian và có thể thực thi hiệu quả trên các CPU đơn giản. Với thẻ thông minh, bộ xử lý có hạn chế, thích hợp với xử lý trên dấu phẩy tĩnh, và hạn chế việc tính toán trên dấu phẩy động. Các thuật toán đối sánh sử dụng phổ biến trên môi trường máy tính cá nhân hoặc server thường yêu cầu sử dụng các phép toán trên dấu phẩy động nên không thích hợp với ứng dụng sử dụng trên thẻ thông minh. Biểu diễn MCC hình trụ có thể biểu diễn bởi dãy các bit 0, 1 nhờ vào thay đổi hàm sigmoid bởi hàm chuyển đơn vị. Điều này cho phép so sánh các cấu trúc cục bộ MCC nhanh chóng bởi so sánh giá trị tương đồng giữa các hình trụ quy về việc so sánh một chuỗi các bit.
III. Phương pháp đối sánh vân tay toàn cục Ưu điểm và hạn chế
Bài toán đối sánh tập các điểm đặc trưng trong đối sánh vân tay được quy về lớp đối sánh toàn cục. Có thể giả thiết hai tập điểm có quan hệ bởi vài quan hệ hình học, trong hầu hết các trường hợp, một vài điểm tương ứng được biết trước, 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 bài toán tổ hợp khó. Một số kỹ thuật đối sánh điểm được áp dụng.
Trường hợp ảnh nhiễu và sự hạn chế trong của vùng trùng nhau giữa hai vân tay, Chất lượng điểm đặc trưng có thể sử dụng như trọng số để đánh giá độ tin cậy hay không tin cậy của điểm đặc trưng. Việc đóng góp của các cặp điểm đặc trưng tin cậy nên cao hơn so với đóng góp của các cặp điểm đặc trưng có chất lượng thấp hơn. Chất lượng của điểm đặc trưng có thể được xác định dựa trên chất lượng vùng ảnh mà điểm đặc trưng thuộc vào.
3.1. Ứng dụng của đối sánh toàn cục và các thuật toán liên quan
Ratha và cộng sự (1996) [6] đề xuất cách tiếp cận đối sánh điểm đặc trưng dựa trên phép biến đổi Hough tổng quát. Không gian biến đổi bao gồm các bộ tứ (Δ x, Δ y, θ, s), trong đó mỗi tham số được rời rạc hóa thành các tập giá trị. Một mảng bốn chiều A trong đó mỗi phần tử cho một tham số được rời rạc hóa. Thuật toán sau được sử dụng để tổng hợp việc đề cử cho mỗi bộ giá trị. Để nâng cao độ độ chính xác của biến đổi Hough, một phương pháp thường dùng là không chỉ bầu cho một ô rời rạc mà còn các ô lân cận. Một phương pháp song song hóa thuật toán ở trên được đề xuất bởi Ratha, Rover, và Jain (1995), được cứng hóa bao gồm bộ xử lý dựa trên Field Programmable Gate Array (FPGA).
3.2. So sánh hiệu quả và độ chính xác của thuật toán
Mặc dù phương pháp toàn cục có thể cho kết quả chính xác, nhưng lại tốn kém về mặt tính toán. Việc so sánh đòi hỏi tính toán trên toàn bộ ảnh, dẫn đến thời gian xử lý lâu hơn so với phương pháp cục bộ. Do đó, cần cân nhắc kỹ lưỡng giữa độ chính xác và thời gian xử lý khi lựa chọn phương pháp đối sánh vân tay.
IV. Đối sánh vân tay cục bộ Giải pháp hiệu quả cho độ chính xác cao
Các cấu trúc cục bộ (Local Description Structure) sử dụng các thông tin xung quanh điểm đặc trưng để làm thông tin mô tả cho điểm đặc trưng. Đố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 đặc trưng. Đối sánh cục bộ cho phép nhanh chóng xác định các cặp điểm đặc trưng 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 hai vân tay.
Có khá nhiều các phương pháp được đề xuất để mô tả cấu trúc cục bộ cho điểm đặc trưng: Sử dụng các điểm đặc trưng xung quanh. Ví dụ biểu diễn K-plet (2006) sử dụng K điểm lân cận gần nhất để biểu diễn điểm đặc trưng. Sử dụng các điểm thuộc các đường vân bao quanh, ví dụ Tico (2003) [7]. Kết hợp cả các điểm đặc trưng và đường vân bao quanh, Feng (2008) [5]. Sử dụng thông tin ảnh xung quanh điểm đặc trưng, ví dụ biểu diễn FingerCode [8] sử dụng các biến đổi Gabor để trích xuất các thông tin ảnh xung quanh điểm đặc trưng.
4.1. Các kỹ thuật và phương pháp nâng cao hiệu quả đối sánh cục bộ
Bước tiếp theo đối sánh cục bộ là bước gia cố (consolidation) nhằm mục đích xác thực xem các cấu trúc phù hợp cục bộ còn phù hợp ở mức toàn cục sau khi đã căn chỉnh. Bước này có thể không cần thiết nếu việc đối sánh cục bộ có thể loại bỏ các trường hợp các vân tay có sự khác biệt lớn. Quá trình gia cố liên quan đến các phép biến đổi xoay và dịch chuyển. 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 làm cặp điểm căn chỉnh hai vân tay trong bước đối sánh toàn cục.
4.2. So sánh hiệu quả và độ chính xác của thuật toán
Tuy nhiên, việc biến đổi dựa trên cặp điểm đặc trưng có giá trị tương đồng lớn nhất có thể không là biến đổi tốt nhất ở mức toàn cục. Một vài tác giả đã sử dụng biến đổi dựa trên nhiều cặp ứng cử viên cho quá trình căn chỉnh. Cuối cùng chọn ra biến đổi có số lượng cặp đối sánh ở mức toàn cục là lớn nhất. Ví dụ Medina và cộng sự [8] giảm số cặp đối sánh cục bộ bằng cách với mỗi điểm đặc trưng p và điểm đặc trưng q, chỉ chọn ra các điểm đặc trưng có giá trị tương đồng lớn nhất, sau đó thực hiện phép biến đổi dựa trên tập hạn chế này. Feng và cộng sự [5] sắp xếp các cặp điểm đối sánh cục bộ theo thứ tự giảm dần sau đó chọn ra T cặp điểm đối sánh cho quá trình căn chỉnh. Thông thường, các cách tiếp cận này cho độ chính xác tốt hơn so với cách tiếp cận dựa trên biến đổi đơn. Một cặp điểm đối sánh sai có giá trị tương đồng lớn nhất.
V. Thử nghiệm Đánh giá hiệu năng thuật toán MCC K plet MTK
Trong chương này, luận văn sẽ tiến hành thực nghiệm đánh giá ba biểu diễn vân tay phổ biến, bao gồm: biểu diễn K-plet [3], MTK [9] và MCC trong quá trình đối sánh vân tay để rút ra kết luận. Để đánh giá các thuật toán khách quan, các thử nghiệm với các thuật toán đối sánh vân tay cùng sử dụng một tập dữ liệu để đánh giá, cùng sử dụng tập các đặc trưng được trích xuất từ tập ảnh vân tay và các tham số được sử dụng trong các thuật toán đối sánh.
Các thực nghiệm được tiến hành trên cùng máy laptop với bộ xử lý Intel Celeron Core Duo processor (1.5 GHz), 1GB RAM. Trong bước gia cố, các thuật toán đối sánh đều sử dụng chung các tham số về ngưỡng để coi các điểm đặc trưng có thể đối sánh với nhau. Luận văn sử dụng ngưỡng khoảng cách ts= 12 và ngưỡng góc lệch tθ= π/6 theo đề xuất bởi Miguel và cộng sự [9].
5.1. Mục tiêu của thử nghiệm và so sánh các thuật toán
Mục đích thử nghiệm nhằm đưa ra kết quả so sánh độ chính xác và tốc độ xử lý của biểu diễn MCC so với các biểu diễn K-plet và MTK trên cùng một tập dữ liệu. Như vậy, nếu sau quá trình thử nghiệm, biểu diễn MCC cho kết quả có độ chính xác và tốc độ xử lý cao hơn hai biểu diễn còn lại thì có thể hiểu biểu diễn MCC có thể áp dụng được trong thực tế, còn nếu đạt kết quả thấp hơn cần xem xét lại biểu diễn MCC có phù hợp và thỏa mãn nhu cầu của người sử dụng.
5.2. Thiết lập thử nghiệm và các thông số đánh giá
Kết quả đánh giá được thể hiện thông qua các chỉ số EER, FMR100, FMR1000 và ZeroFMR. Thời gian đối sánh được thể hiện theo milliseconds. False Match Rate (FMR): là tỷ lệ loại lỗi xác định nhầm là cùng của một vân tay khi so sánh hai vân tay khác nhau. False Non-Match Rate (FNMR): là tỷ lệ lỗi khi xác định hai vân tay của cùng một ngón tay là không phù hợp. FMR100 là tỷ lệ lỗi FNMR mà tại đó FMR là 1%. FMR1000 là tỷ lệ lỗi FNMR mà tại đó FMR là 0,1%. FMRZero là tỷ lệ lỗi FNMR mà tại đó FMR là 0%.
VI. Tổng kết và Hướng phát triển của Thuật toán đối sánh MCC
Nội dung Chương 3 với mục đích quan trọng là tiến hành thử nghiệm thuật toán đối sánh dựa vào biểu diễn MCC so với biểu diễn K-plet, MTK. Từ kết quả thử nghiệm đưa ra đánh giá so sánh với các biểu diễn K-plet, MTK. Kết quả thử nghiệm cho thấy biểu diễn cấu trúc cục bộ dựa trên MCC cho độ chính xác cao và tăng tốc độ hơn đáng kể so với hai thuật toán còn lại.
Trong khuôn khổ luận văn tốt nghiệp này, tôi đã nghiên cứu, phân tích và đánh giá một số thuật toán đối sánh vân tay dựa trên điểm đặc trưng phổ biến hiện nay. Từ đó, thuật toán đối sánh vân tay dựa trên biểu diễn K-plet, MTK và Minutiae Cylinder-Code (MCC) đã được chú trọng nghiên cứu, phân tích và thực nghiệm. Dựa trên những khảo sát lý thuyết, luận văn đã tiến hành thử nghiệm thuật toán dựa trên các biểu diễn K-plet, MTK, MCC với bộ dữ liệu vân tay FVC 2002DB.
6.1. Kết quả đạt được và so sánh với các thuật toán khác
Từ bảng kết quả thu được so sánh độ chính xác và tốc độ của các thuật toán cho thấy biểu diễn cấu trúc cục bộ dựa trên MCC cho độ chính xác cao và tăng tốc độ hơn đáng kể so với hai thuật toán còn lại.
6.2. Các hướng nghiên cứu và phát triển tiềm năng cho thuật toán
Nghiên cứu cài đặt và triển khai thuật toán trong thực tế. Nghiên cứu cài đặt thuật toán đối sánh dựa trên MCC theo biểu diễn Bit. Cài đặt áp dụng thuật toán trên thẻ thông minh tiến hành song song thuật toán để tăng tốc độ xử lý của hệ thống.
16/09/2025
