Luận án Nghiên cứu nâng cao các kỹ thuật đối sánh vân tay dựa trên đặc trưng điểm chạc

góc của điểm chạc trùng với vector nối giữa các điểm chạc.  𝛽 3 là góc quay để hướng của các điểm chạc trùng nhau. Hình 1.24: Các th n t n v tam tam ác t đ c tạo t 3 đ m chạc p p p3 8 . 48 Công thức tính độ tương đồng giữa 2 tam giác t và r ( ) { ( ( )) ( α( )) ( β( )) ( ) Trong đó , α, β được tính dựa trên sự khác nhau về khoảng cách giữa các cạnh, sự khác nhau về giá trị các góc 𝛼 và các góc 𝛽 của 2 tam giác t và r [48]. Do số lượng các tam giác được tạo từ tập điểm chạc là rất lớn, một số tác giả đề xuất các luật ràng buộc nh m giảm số lượng các tam giác cần xem x t. Ví dụ ch s dụng các tam giác là kết quả của quá tr nh tam giác hóa elaunay trên tập các điểm chạc [55], [18], [74], [72], [16]. Do các tam giác được tạo b i quá tr nh tam giác hóa có thể bị ảnh hư ng b i phát hiện sai hoặc thiếu điểm chạc, để nâng cao tính chịu l i với quá tr nh tam giác hóa, Liang và cộng sự [38], Yang và cộng sự [95 đã đề xuất s dụng thêm với các tam giác là kết quả của quá tr nh tam giác hóa 1-order Delaunay (cho ph p một điểm có thể thuộc vào đường tròn ngoại tiếp của một tam giác lân cận). H nh 1.25 minh họa các tam giác được tạo b i quá tr nh tam giác hóa 1-order elaunay trên tập các điểm chạc của vân tay. Hình 1.25: Tam ác h a -order Delaunay [38] Sau quá tr nh tam giác hóa, các tam giác giữa các vân tay s được đối sánh với nhau dựa trên các thông tin biểu diễn về tam giác ví dụ như biểu diễn m-Triplet). 49 1.4.2.2. Hạn chế của một số biểu diễn truyền thống Các cấu trúc dựa trên láng giềng gần: Các láng giềng của điểm chạc trung tâm được tạo b i K điểm chạc gần nhất. Một hạn chế của lớp thuật toán này là khả năng thay đ i cấu trúc cục bộ do t m thiếu hoặc sai điểm chạc từ ảnh vân tay. Hình 1.26: Sa hác v c u tr c u d ễn do phát h n đ m chạc th u ho c sa Việc phát hiện thiếu hoặc sai điểm chạc thường xảy ra với các ảnh vân tay chất lượng thấp trong quá tr nh lấy mẫu vân tay. Ví dụ: H nh 1.26 minh họa việc cấu trúc cục bộ bên trái bị thay đ i, có sự khác biệt với các cấu trúc biểu diễn bên phải do t m thiếu điểm chạc hay t m ra điểm chạc sai trong quá tr nh trích chọn đặc trưng từ ảnh. Các cấu trúc dựa trên bán kính cố định: Các điểm láng giềng được định nghĩa là tất cả các điểm chạc có khoảng cách với điểm chạc trung tâm nhỏ hơn một bán kính R cho trước. Với biểu diễn dựa trên bán kính cố định, số lượng các điểm chạc xung quanh trong m i biểu diễn có thể khác nhau giữa các điểm chạc, điều này có thể dẫn đến đối sánh giữa các cấu trúc cục bộ phức tạp hơn, tuy nhiên phương pháp dựa trên bán kính cố định chịu l i tốt hơn với trường hợp điểm chạc bị phát hiện sai hoặc thiếu. Đối sánh dựa trên cấu trúc có bán kính cố định có thể dẫn đến l i đường biên bao. Ví dụ do sự khác nhau của sự vặn m o khi lấy mẫu vân tay, sự xác định không 50 chính xác vị trị, có thể dẫn đến cùng một điểm chạc nhưng ngoài vùng biển diễn cục bộ của vân tay thứ hai. H nh 1.27 minh họa một số điểm chạc ngoài vùng biểu diễn cục bộ của hai vân tay dẫn đến việc sai khác trong cấu trúc cục bộ. Hình 1.27: C u tr c cục h n ph h p do v n đ n. 1.4.2.3. Biểu diễn cục bộ dựa trên m trụ MCC Minutia Cylinder-Code) Hiện nay, theo đánh giá của các nghiên cứu khác nhau, biểu diễn cấu trúc cục bộ dựa trên biểu diễn Minutia Cylinder-Code MCC được đề xuất b i Capelli và cộng sự là một trong những biểu diễn cục bộ cho kết quả chính xác nhất [8]. Hình 1.28: C u tr c u d ễn cục M nut a Cy nder Code MCC 8 Trong biểu diễn MCC, m i điểm chạc được thể hiện thông qua một h nh trụ, h nh trụ có tâm tại điểm chạc, bán kính cố định R và chiều cao 2π. H nh trụ được chia 51 thành ô như trong H nh 1.28. Capelli và cộng sự lựa chọn tham số có giá trị 16 và tham số có giá trị 6.T ng số các ô trong h nh trụ là 16x16x6. Các chiều đáy của m i ô có giá trị , , chiều cao của m i ô là . Trong đó và M i ô có giá trị thể hiện xác suất t m thấy điểm chạc tại vị trí đó với góc lệnh ( ) so với điểm chạc m. Đóng góp của m i điểm chạc tới một ô của h nh trụ phụ thuộc vào khoảng cách từ tới tâm của ô và sự khác nhau về hướng giữa và điểm chạc so với hướng của vị trí ô. H nh 1.29 . Điểm chạc càng gần với ô đóng góp giá trị của vào ô càng lớn. Giá trị m i ô của h nh trụ được tính trên t ng xác suất có mặt của điểm chạc gần đó. Trường hợp điểm chạc phát hiện thiếu hoặc sai, giá trị của ô có thể được bù b i các giá trị của các điểm chạc khác xung quanh. Hình 1.29: Các đ n p c a các đ m chạc v o c a hình trụ d a tr n hoản cách v s hác nhau v h n 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, biểu diễn 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 52 đồng cục bộ đơn giản, coi m i biểu diễn là một vector có cùng độ dài. Các vector biểu diễn cùng độ dài thích hợp cho quá tr nh tính toán song song. Các điểm chạc của m i vân tay được biểu diễn thông qua vector mã trụ . có chiều dài là số lượng các ô trong h nh trụ. Tính toán độ tương đồng giữa 2 điểm chạc và dựa trên sự khác nhau giữa 2 vector biểu diễn và . Các vector càng giống nhau th độ tương đồng càng cao. Độ tương đồng giữa 2 vector và thường được tính toán dựa trên công thức sau: 𝑠 ( ) { || || || || || || ( ) ( ) (1.2) Trong đó:  thể hiện toán t XOR trong trường hợp giá trị của vector đã được nhị phân hóa  || ||thể hiện độ dài vector chu n uclidean  ( ) là góc khác giữa hướng của 2 điểm chạc và  Giá trị ngưỡng thường được lựa chọn có giá trị Hình 1.30: So sánh sa số EER c a u d ễn MCC so v m t số u d ễn hác 8 53 H nh 1.30 kết quả đánh giá, so sánh độ chính xác của một số thuật toán đối sánh vân tay dựa trên điểm chạc như biểu diễn MCC, Jiang [34], Ratha [60], Feng [21] s dụng CSDL FVC 2004DB. Thuật toán đối sánh s dụng biểu diễn MCC được thực thi 3 chế độ khác nhau: chế độ 16, 16b và 8. Chế độ 16 được thực thi khi chia m i bán kính của h nh trụ thành 16 ô khác nhau.16b đó các giá trị của các ô trong h nh trụ được nhị phân hóa thành các giá trị 0 hoặc 1 dựa trên ngưỡng xác định. Việc nhị phân hóa giá trị trong biểu diễn MCC giúp tăng tốc quá tr nh tính toán độ tương đồng. Việc tính toán độ tương đồng ch cần s dụng các lệnh XOR trên các thanh ghi. Kết quả so sánh cho thấy các thuật toán dựa trên biểu diễn MCC cho kết quả sai số R thấp hơn so với các biểu diễn Jiang, Ratha, Feng. 1.4.3. Giai đoạn gia cố trong thuật toán đối sánh vân tay dựa trên cấu trúc cục bộ Đối sánh vân tay dựa trên các cấu trúc cục bộ giúp làm t m nhanh ra các cặp điểm chạc có các cấu trúc cục bộ phù hợp. Điều này giúp giảm thời gian tính toán. Các cấu trúc cục bộ của các điểm chạc thường được tính toán trước và lưu trữ trong CSDL vân tay. Sau giai đoạn t m các cặp điểm chạc có cấu trúc cục bộ phù hợp, các thuật toán đối sánh vân tay thường tiến hành thêm bước gia cố nh m mục đích kiểm tra thêm các cặp điểm chạc này còn phù hợp mức toàn cục [56]. Nội dung chương tiếp theo của luận án s tr nh bày chi tiết về các phương pháp gia cố thường được s dụng và đề xuất của luận án giúp nâng cao độ chính xác của giai đoạn đoạn gia cố. 1.5. Kết chƣơng Nội dung chương đã khái quát một số phương pháp tiền x lý giúp trích chọn đặc trưng điểm chạc từ ảnh vân tay hiệu quả. Tiếp đến nội dung chương mô tả bài toán đối sánh vân tay dựa trên điểm chạc và một số khó khăn của bài toán. Luận án cũng đề cập tới phương pháp đối sánh dựa trên các cấu trúc cục bộ được s dụng ph biến hơn trong đối sánh vân tay, giúp t m nhanh các cặp điểm chạc phù hợp. 54 Nội dung chương tiếp theo s mô tả chi tiết các đề xuất của luận án nh m nâng cao độ chính xác của giai đoạn gia cố trong các thuật toán đối sánh vân tay dựa trên các cấu trúc cục bộ. 55 Chƣơng 2: 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 Chương 1 đã đề cập tới một số cấu trúc cục bộ được s dụng ph biến trong các thuật toán đối sánh vân tay dựa trên điểm chạc với mục đích t m nhanh các cặp điểm chạc có cấu trúc cục bộ phù hợp giá trị tương đồng giữa các cấu trúc cục bộ lớn hơn 0). Một trong những bước ảnh hư ng đến độ chính xác của quá tr nh đối sánh này chính là bước gia cố. Trong chương này, luận án s giới thiệu đề xuất cải tiến bước gia cố trong các thuật toán đối sánh vân tay dựa trên điểm chạc. Th nghiệm đánh giá cải tiến bước gia cố đề xuất với các thuật toán đối sánh s dụng biểu diễn K-plet, m-Triplets và MCC trên CS L vân tay VC 2002 1 cho kết quả nâng cao độ chính xác của các thuật toán gốc và không ảnh hư ng đến tốc độ thi hành của các thuật toán. Các kết quả này đã được công bố trong hai công tr nh của nghiên cứu sinh [LHHai1], [LHHai4]. 2.1. Các phƣơng pháp gia cố thƣờng sử dụng ước tiếp theo đối sánh các cấu trúc cục bộ là bước gia cố nh m mục đích kiểm tra 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. Ví dụ trong h nh 2.1 điểm chạc phù hợp với điểm chạc điểm chạc phù hợp với điểm chạc sau khi so sánh các cấu trúc cục bộ của các điểm chạc. Tuy nhiên sau khi căn ch nh tới vị trí , có thể không còn phù hợp với . Hình 2.1: c a cố n quan đ n v c c n ch nh n đổ oay v dịch chuy n 56 Quá tr nh gia cố liên quan đến các ph p biến đ i xoay và dịch chuyển. Sau bước căn ch nh, tất cả các cấu trúc cục bộ được xác định lại xem liệu có còn thỏa mãn các ràng buộc sau: - Khoảng cách giữa hai điểm chạc sau khi căn ch nh không vượt quá ngưỡng ts 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à . [ ] 0 𝑠 𝑠 𝑠 𝑠 1 [ ] [ ] 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ư: - S d ng ph p bi n hình đơn nhất (single transformation): 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 giữa 2 vân tay trong bước gia cố toàn cục [67]. Tuy nhiên, việc biến đ i dựa trên cặp điểm chạc 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. Ví dụ trong h nh 2.2 ch ra một ví dụ một cặp điểm đối sánh có giá trị tương đồng lớn nhất nhưng lại không phải là đối sánh đúng. 57 Hình 2.2: M t c p đ m đố sánh sa c á trị t n đ n n nh t 7 - Thực hiện nhiều ph p bi n hình khác nhau multiple transformations): Một số 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ự [47] giảm số cặp đối sánh cục bộ b ng cách với m i điểm chạc p và điểm chạc q, ch chọn ra các điểm chạc có giá trị tương đồng lớn nhất, sau đó thực hiện ph p biến đ i căn ch nh dựa trên tập cặp điểm đã hạn chế này. eng và cộng sự [21] 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 sau đó chọn ra T cặp điểm phù hợp cục bộ có giá trị tương đồng lớn nhất s dụng 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ập dựa trên biến đ i đơn nhất. - S d ng ph p bi n hình phức hợp (Complex transformation): Để hạn chế tác động của hiện tượng vặn m o không tuyến tính của vân tay do lực ấn vân tay không đồng nhất, sau khi t m ra cặp điểm căn ch nh tối ưu áp dụng gia cố biến h nh các tác giả kết hợp tiếp với ph p nắn ch nh. Bazen và cộng sự [4] áp dụng mô h nh thin-plate spline (TPS) để biến đ i vân tay sau khi đã căn ch nh. Cách tiếp cận tính toán hiệu quả hơn được giới thiệu b i Kwon và cộng sự [35] dựa trên mô h nh tam giác hóa để s a chữa ảnh hư ng của việc vặn m o. H nh 2.3 minh họa so sánh quá tr nh đối sánh s dụng ph p căn ch nh thông thường và kết quả đối sánh sau khi đã kết hợp thêm nắn 58 ch nh dựa trên mô h nh TPS và mô h nh tam giác hóa được đề xuất b i Kwon và cộng sự. 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 p nắn ch nh lại sau khi đã t m ra các cặp điểm chạc phù hợp s dụng ph p căn ch nh dựa trên biến h nh giúp tăng độ chính xác của ph p đối sánh, tuy nhiên s dụng ph p nắn ch nh 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. - S d ng quá trình gia c gia tăng (incremental consolidation): trong cách tiếp cận này s không t m ra tất cả các cặp điểm chạc phù hợp cục bộ ngay mà 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 t m ra là láng giềng của cặp điểm làm gốc. Quá tr nh này s được tiếp tục với các cặp điểm mới thêm vào Kết quả thuật toán s 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]. 59 Hình 2.4: Quá trình ây d n cây đố sánh tron K-plet [6] Theo cách tương tự Conti và cộng sự [90], chia ảnh thành nhiều vùng khác nhau và các kết quả đối sánh trên từng vùng s được nối tiếp với nhau tạo nên kết quả cuối cùng. Cao và cộng sự [91 trong quá tr nh xây dựng cây gia tăng đã áp dụng thêm ph p toán tối ưu để giảm ảnh hư ng của vặn m o vân tay. 2.2. Giải thuật gia cố đề xuất Nội dung mục này s đề cập tới các cải tiến đề xuất của luận án cho 2 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 đã tr nh bày trong mục trước. Các kết quả nghiên cứu được công bố trong [LHHai1], [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 cách truyền thống sau bước căn ch nh trong ph p gia cố dựa trên ph p biến h nh, các cặp điểm phù hợp cục bộ s được kiểm tra với cặp điểm trung tâm dùng làm căn ch nh. Mặc dù các cặp điểm phù hợp cục bộ này có thể phù hợp với cặp điểm căn ch nh, nhưng có thể không phù hợp với nhau. H nh 2.5, minh họa các cặp điểm đối sánh t m ra s dụng thuật toán đối sánh s dụng phương pháp gia cố truyền thống, có thể nhận thấy không phải tất cả các cặp điểm chạc t m ra đều phù hợp. 60 Ví dụ với cặp điểm chạc số 1 được s dụng làm ph p căn ch nh, dù các cặp điểm chạc 1,4 và cặp điểm chạc (1,3) giữa 2 vân tay đều phù hợp với nhau, tuy nhiên cặp điểm chạc (3,4) giữa 2 vân tay là không phù với nhau. Hình 2.5: Đố sánh h n ch nh ác h sử dụn a cố truy n thốn o đó luận án đề xuất, sau khi căn ch nh với cặp điểm làm tâm, các cặp điểm phù hợp cục bộ không ch được kiểm tra xem có phù hợp với cặp điểm làm tâm mà còn kiểm tra xem có phù hợp với các điểm chạc đã căn ch nh khác. Ví dụ, với cặp điểm chạc số 4, không ch kiểm tra phù hợp với cặp điểm chạc s dụng làm ph p căn ch nh số 1 mà còn kiểm tra xem có phù hợp với các cặp điểm chạc số 2 và số 3. Mô tả thuật toán gia cố đề xuất như sau: Đầu tiên, chúng ta sắp xếp tất cả các cặp điểm chạc phù hợp cục bộ còn thỏa mãn sau quá tr nh căn ch nh với điểm chạc làm tâm theo giá trị độ tương đồng giảm dần, sau đó s loại bỏ 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. 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 *( )+ ̣ ậ ứ á ặ đ ể ù ợ đô ộ ớ huật toán: 61 *( )+ ( ) ( ) ( ) is_match =false ( ) ( ) òng lệnh 3, với m i cặp điểm ( ) trước khi được đưa vào tập kết quả s được kiểm tra 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 coi là phù hợp nếu thỏa mãn về ngưỡng khoảng cách và ngưỡng góc . Công thức 2.3). Kết quả cuối cùng tập s chứa các cặp điểm chạc không ch phù hợp với cặp điểm chạc dùng làm căn ch nh mà còn phù hợp với các cặp điểm chạc khác trong tập . Về độ phức tạp của thuật toán 2.2, trong trường hợp tồi nhất không t m được cặp phù hợp nào chúng ta s thu được độ phức tạp về thời gian là O n tương ứng việc phải duyệt tất cả các cặp và K luôn r ng. Trong tường hợp tất cả đều phù hợp, chúng ta có độ phức tạp là ( ) tương ứng với số lần duyệt là n*(n-1)/2. 62 Thông thường số lượng cặp điểm chạc phù hợp với cặp điểm căn ch nh là không nhiều, trung b nh 6 cặp điểm chạc phù hợp giữa 2 vân tay trên CS L VC 2002 1. o đó cần thêm tối đa 36 ph p kiểm tra giữa các cặp điểm chạc. Hình 2.6: K t quả đố sánh h sử dụn a cố đ u t. H nh 2.6 thể hiện kết quả áp dụng quá tr nh gia cố đề xuất, trong quá tr nh gia cố, tất cả các cặp điểm chạc đều được kiểm tra với nhau. Có thể nhận thấy tất cả các cặp điểm chạc t m ra đều phù hợp. Cặp điểm chạc số 4 đã bị loại bỏ do không phù hợp 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ự [6 trong quá tr nh xây dựng đồ thị đối sánh, khi thêm một cặp điểm chạc ( ) vào đồ thị đối sánh, cặp được đưa vào ( ) ch được kiểm tra với cặp điểm liền kề trước đó ( ). 63 Hình 2.7: Quá trình ây d n cây đố sánh tron -plet H nh 2.7 minh họa quá tr nh xây dựng cây đối sánh trong thuật toán K-plet, đ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] ( ) ( ) Thu n *+ *+ *+ ( ) ( ) *+ ( ) ( ) *( )+ ( ) ( ) ( ) ( ) ( ) 64 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, 9.iii s đưa các cặp điểm lận cận ( ) vào cuối hàng đợi nếu ( ) chưa được thăm và phù hợp với ( ), đồ thị s được thăm theo chiều rộng. ề uất n ng cao đ ch nh ác c a uận án Gần với vấn đề đề cập ph p gia cố dựa trên ph p biến h nh, với nhận x t r ng cặp điểm chạc( ) mặc dù phù hợp với cặp điểm liền kề ( ) trong đồ thị nhưng có thể không phù hợp với các cặp điểm đã t m ra phía trước của đồ thị. o đó luận án đề xuất khi một cặp điểm mới ( ) được thêm vào đồ thị, cặp điểm ( ) không ch kiểm tra với cặp điểm liền kề ( ) mà còn kiểm tra với các cặp điểm ( ) đã được thêm vào đồ thị đối sánh trước đó. Thuật toán 2.4: Sửa đổ c 9 c a thu t toán K-plet ( ) ư đượ ệ ( ) ( ) ( ) ( ) ( ) ( ) 65 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 đó. Cặp điểm ( ) ch được thêm vào tập kết quả M nếu ( ) phù hợp với tất cả các cặp điểm ( ) trước đó. o đó kết quả tập M cuối cùng s chứa các cặp điểm chạc phù hợp đôi một với nhau. H nh 2.8 và 2.9 minh họa kết quả trước và sau khi áp dụng bước gia cố cải tiến cho thuật toán K-plet, cho thấy sau khi áp dụng thêm bước kiểm tra sau quá tr nh căn ch nh, kết quả trong h nh 2.9 đã loại bớt được một số cặp điểm chạc không phù hợp với nhau. Hình 2.8: Đố sánh h sử dụn a cố truy n thốn tr n K-plet 66 Hình 2.9: Đố sánh ch nh ác h n h sử dụn a cố đ u t cho K-plet 2.3. Đá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. Thực nghiệm s dụng bộ công cụ Veri inger [75 để tách các đặc trưng điểm chạc từ các ảnh vân tay. CS L FVC 2002 DB1 bao gồm 800 ảnh vân tay được lấy từ 100 vân tay khác nhau m i vân tay được lấy 8 ảnh khác nhau . Các ảnh vân tay có cùng kích thước 500x500 điểm ảnh. Để đánh giá các ch số R, RM, NRM, thực nghiệm thực hiện 2800 đối sánh giữa các ảnh cùng vân tay m i thể hiện của vân tay được so với các thể hiện còn lại, do đó với m i vân tay s bao gồm 8x7 /2 đối sánh, t ng số đối sánh giữa các ảnh thuộc cùng vân tay với 100 vân tay là 100x 8x7 /2 = 2800 đối sánh , thực nghiệm bao gồm 4950 đối sánh giữa các ảnh vân tay từ các vân tay khác nhau m i thể hiện đầu tiên của m i vân tay được đối sánh với với các thể hiện đầu tiên của các vân tay khác kết quả bao gồm 100x99 /2 = 4950 đối sánh trên CSDL. 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 100 FMR 1000 FMR Zero hời gian (ms) K-plet 1.52% 1.61% 2.61% 4.42% 29 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 MCC 1.52% 1.71% 2.42% 3.72% 3.52 MCC cải tiến 1.38% 1.65% 2.14% 2.92% 3.85 Bốn thực nghiệm đánh giá trong bảng 2.1 đều s dụng trên cùng bộ dữ liệu điểm chạc được tách ra từ các ảnh vân tay. Các kết quả đánh giá thuật toán đối sánh dựa trên biểu diễn K-plet và m-Triplets được s dụng trên mã nguồn của các tác giả, thuật toán 67 dựa trên biểu diễn MCC được s dụng b i [57] các kết quả đánh giá có thể khác với các kết quả 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ừ các ảnh vân tay luận án s dụng khác với bộ công cụ tách đặc trưng được s dụng b i các tác giả. Các thuật toán cải tiến quá tr nh gia cố đề xuất b i luận án cho kết quả chính xác hơn thuật toán gốc. Sai số trung b nh R của 3 thuật toán có kết quả cao nhất tại FVC 2002 DB1 là 0.2 [49 , các thuật toán có thể s dụng kết hợp thêm các đặc trưng khác của ảnh vân tay như các thông tin về đường vân, thông tin về các điểm đơn nhất, số đường vân giữa các điểm chạc, s dụng thêm các ph p nắn ch nh sau quá tr nh gia cố. 2.4. Kết chƣơng Trong chương này, luận án đề xuất thuật toán cải tiến quá tr nh gia cố nh m nâng cao độ chính xác của đối sánh vân tay dựa trên điểm chạc và không ảnh hư ng đến tốc độ thực thi của các thuật toán gốc đã được tr nh bày chi tiết. Đề xuất này dựa trên ý tư ng, khi xem x t các cặp điểm chạc trong quá tr nh căn ch nh, không ch kiểm tra độ phù hợp với cặp điểm được chọn làm điểm tâm mà còn cần kiểm tra với các cặp điểm đã được căn ch nh trước đó. Trong phương pháp gia cố dựa trên xây dựng đồ thị đối sánh, phương pháp truyền thống ch kiểm tra cặp điểm thêm vào đồ thị với cặp điểm liền kề. Đề xuất tương tự là kiểm tra cặp điểm thêm đồ thị vào với toàn bộ các cặp điểm thêm vào đồ thị trước đó. Đánh giá các đề xuất cho quá tr nh gia cố trên các thuật toán đối sánh vân tay trên các biểu diễn m-Triplets, MCC và K-plet trên CS L vân tay VC 2002 1 cho kết quả chính xác hơn và không ảnh hư ng đến tốc độ thi hành của thuật toán gốc. Nội dung chương tiếp theo s tr nh bày về phương pháp phát hiện điểm đơn nhất từ ảnh vân tay, giúp tăng tốc độ thi hành các thuật toán đối sánh vân tay. 68 Chƣơng 3: PHÁT HIỆN ĐIỂM ĐƠN NHẤT TỪ ẢNH VÂN TAY Trong chu n dữ liệu vân tay ISO/I C 19794-2, ngoài dữ liệu chính là các điểm chạc, tùy chọn m rộng dữ liệu có thể bao gồm các điểm đặc trưng đơn nhất vân tay. Các điểm đơn nhất có tác dụng làm điểm căn ch nh giúp tăng tốc thực thi cũng như độ chính xác của các thuật toán đối sánh vân tay. Ngoài ra các điểm đơn nhất còn là đặc trưng quan trọng thường được s dụng trong bài toán phân lớp vân tay. Phân lớp vân tay giúp lọc nhanh các ứng viên vân tay trước khi thực hiện quá tr nh đối sánh chi tiết s dụng các thuật toán đối sánh đã đề cập trong chương 2. Luận án đề xuất áp dụng mạng nơ ron tích chập CNN vào nhận dạng các điểm đặc trưng đơn nhất từ ảnh vân tay. Mạng CNN cho kết quả chính xác cao trong nhiều tác vụ trong lĩnh vực thị giác máy hiện nay. Kết quả áp dụng mạng CNN trong phát hiện điểm đơn nhất từ ảnh vân tay được đánh giá trên tập CS L mẫu VC2002 DB cho kết quả nhận dạng chính xác 96 với điểm đặc trưng core và 90 với điểm đặc trưng delta. Kết quả trên của nghiên cứu được công bố trong [LHHai5]. 3.1. Điểm đơn nhất vân tay và ứng dụng Điểm đơn nhất của ảnh vân tay thường chia làm 2 loại điểm h nh 3.1 : - Điểm lõi core : là điểm đó có sự biến thiên đột ngột về hướng của các đường vân. Hình 3.10: Các oạ đ m đ n nh t c a ảnh vân tay đ m core v đ m de ta - Điểm tam phân delta : là điểm hội tụ của các vùng vân có hướng khác nhau. 69 Ứng dụng điểm đơn nhất trong phân lớp vân tay Các vân tay thường được phân vào một trong 6 lớp vân tay như minh họa trong H nh 3.2. Việc phân lớp này giúp giảm bớt không gian mẫu vân tay cần đối sánh. - Vân h nh cung arch : có các đường vân vào từ một phía sau đó nhô lên và đi ra phía đối diện. Vân h nh cung không chứa điểm core và điểm delta. - Vân h nh cung lều tented arch : có ít nhất một điểm core và 1 điểm delta. - Vân h nh quai loop : vân tay có một hay nhiều đường đi vào từ một phía và quay ngược lại cùng phía khi vào. Vân h nh quai thường có điểm core và điểm delta. Vân h nh quai có thể chia thành 2 lớp nhỏ hơn là quai trái left loop v