- PHÂN LOẠI DẤU VÂN TAY VỚI RỪNG NGẪU NHIÊN XIÊN PHÂN VÀ PHƯƠNG PHÁP BIỂU DIỄN. - ĐẶC TRƯNG KHÔNG ĐỔI. - Nghiên cứu trình bày một phương pháp phân loại ảnh vân tay mới và đáng tin cậy dựa trên sự kết hợp giữa phương pháp biểu diễn ảnh bằng các nét đặc trưng không đổi (SIFT) và rừng ngẫu nhiên xiên phân (RF-ODT). - Sau bước tiền xử lý, ảnh được biểu diễn bởi một véctơ có số chiều rất lớn, do đó chúng tôi đề nghị mở rộng và sử dụng rừng ngẫu nhiên xiên phân - được biết đến như một trong những lựa chọn tốt để học và phân loại dữ liệu có số chiều lớn. - Để đánh giá hiệu quả, chúng tôi sử dụng thiết bị đọc dấu vân tay để thu thập 480 ảnh vân tay từ 15 đồng nghiệp ở trường Đại học Cần Thơ.. - Sau khi tiến hành tiền xử lý dựa trên cơ sở véctơ mô tả SIFT, giải thuật rừng ngẫu nhiên xiên phân của chúng tôi đã phân loại chính xác đến 99.79% (chỉ nhầm lẫn duy nhất 1 ảnh, với nghi thức kiểm tra chéo). - Kết quả này cho thấy hệ thống rất đáng tin cậy. - Hơn nữa, giải thuật mở rộng của rừng ngẫu nhiên xiên phân như đã đề nghị cho kết quả phân lớp ảnh vân tay chính xác hơn một số giải thuật học khác.. - Từ khóa: phân loại ảnh vân tay, véctơ mô tả SIFT, rừng ngẫu nhiên xiên phân. - Nhận dạng vân tay là ứng dụng phổ biến trong ngành nhân trắc học. - Đã từ lâu, dấu vân tay đã được sử dụng để nhận dạng một cá nhân nào đó do tính duy nhất và nhất quán của nó. - Thói quen sử dụng dấu vân tay để nhận dạng cá nhân được sử dụng từ thế kỷ XIX khi mà Francis Galton xác định được một số đặc điểm của dấu vân tay. - Đến thập niên 1960, khi các công nghệ máy tính phát triển rầm rộ thì cũng là lúc vân tay được xác định một cách tự động. - Năm 1969, Cục điều tra liên bang (Federal Bureau of Investigation - FBI) phát triển hệ thống tự động hóa qui trình nhận dạng vân tay. - Vì vậy, FBI ký hợp đồng với Viện tiêu chuẩn và công nghệ (National Institute of Standards and Technology - NIST) để nghiên cứu quá trình phân loại, tìm kiếm và so sánh vân tay tự động. - Năm 1975, FBI tài trợ việc phát triển các máy quét vân tay để phân loại tự động và công nghệ rút trích các chi tiết quan trọng để chế tạo một thiết bị đọc thử nghiệm. - NIST tập trung vào phát triển các phương pháp số hóa tự động dấu vân tay in trên giấy, ảnh hưởng của chất lượng hình ảnh, phân loại, rút trích các chi tiết quan trọng và phương pháp so sánh.. - Hình 1: Đặc trưng của ảnh vân tay dùng cho nhận dạng. - Hầu hết các hệ thống nhận dạng dấu vân tay hiện nay như Libfprint [7] và Fingerprint SDK [9] đều dựa trên hai loại đặc trưng chính của ảnh vân tay: (i) điểm kỳ dị (singularity) gồm vùng xoáy (core), vùng tam giác (delta), đảo (island), điểm giao nhau (crossover), lỗ hổng (pore) và (ii) điểm chi tiết (minutiae) gồm điểm kết thúc (ridge ending), điểm rẽ nhánh (ridge bifurcation) (xem Hình 1). - Chi tiết về nhận dạng vân tay và các công trình liên quan có thể tìm thấy trong . - Tuy nhiên, việc sử dụng các chi tiết đặc trưng như hiện nay vẫn còn khó khăn vì ảnh thu được thường kém chất lượng, kết quả nhận dạng không tốt khi ảnh bị biến đổi hình học hay bị lệch.. - Hệ thống phân loại vân tay mà chúng tôi muốn trình bày ở đây có thể cho kết quả tốt hơn, được tiếp cận hoàn toàn khác từ sự kết hợp giữa phương pháp biểu diễn ảnh bằng các nét đặc trưng không đổi SIFT và sự mở rộng của giải thuật học rừng ngẫu nhiên xiên phân RF-ODT [6]. - Trước tiên, ảnh vân tay được chuyển qua dạng mức xám. - Bước tiền xử lý sẽ cho ra các tập dữ liệu có số chiều lớn (thường lớn hơn 1000). - Do vậy chúng tôi sử dụng giải thuật phân lớp rừng ngẫu nhiên xiên phân RF-ODT, giải thuật này thường phù hợp với các bộ dữ liệu có số chiều rất lớn. - Hơn nữa, chúng tôi cũng thay thế luật quyết định bình chọn số đông ở nút lá của cây xiên phân bởi luật quyết định cục bộ cho phép làm việc hiệu quả cho phân lớp ảnh vân tay. - Kết quả thử nghiệm chỉ ra rằng hệ thống phân loại vân tay của chúng tôi đạt được độ chính xác đến 99.79%. - Kết quả này cho thấy hệ thống phân loại ảnh vân tay của chúng tôi rất đáng tin cậy. - Hơn nữa, giải thuật mở rộng của rừng ngẫu nhiên xiên phân do chúng tôi đề nghị cho phân lớp ảnh vân tay chính xác hơn các giải thuật học khác, bao gồm cây quyết định C4.5 [19], rừng ngẫu nhiên [3] của cây quyết định CART [4] (RF-CART), AdaBoost [8] của C4.5, máy học véctơ hỗ trợ [21] (SVM) và k-láng giềng (kNN).. - Phần 2 mô tả phương pháp biểu diễn ảnh vân tay và véctơ mô tả SIFT. - Sau đó, giải thuật rừng ngẫu nhiên xiên phân RF-ODT và sự mở rộng của giải thuật lần lượt được giới thiệu tóm tắt trong phần 3. - Cuối cùng, kết quả thực nghiệm được trình bày trong phần 4 trước khi nêu kết luận và hướng phát triển trong phần 5.. - Bước này có ảnh hưởng rất lớn đến kết quả phân loại cuối cùng. - Vì vậy, phương pháp của chúng tôi sử dụng các nét đặc trưng cục bộ để biểu diễn ảnh được chụp trong nhiều điều kiện khác nhau. - Nghiên cứu của chúng tôi dựa trên một mô hình trong phân tích văn bản: mô hình túi từ (bag of words model). - Các điểm đặc trưng (Hình 1) được tính trên những ảnh này bằng cách sử dụng các giải thuật phát hiện điểm đặc trưng cục bộ (local feature detector) như là Harris-Affine, Hessian-Affine [16].. - Sau đó, vùng xung quanh các điểm đặc trưng được xác định và mô tả bằng các véctơ mô tả cục bộ. - Hình 2: Các điểm đặc trưng được phát hiện bởi giải thuật Hessian affine. - Hình 2 minh hoạ một ví dụ của véctơ mô tả SIFT được xây dựng từ vùng cục bộ xung quanh một điểm đặc trưng. - Lúc này, mỗi ảnh được biểu diễn bởi một tập các véctơ mô tả SIFT.. - 3 RỪNG NGẪU NHIÊN XIÊN PHÂN. - Bước tiền xử lý ảnh vân tay sẽ tạo ra tập dữ liệu có số chiều rất lớn (hơn 1000 chiều). - Giải thuật phân lớp được chọn tiếp theo phải có khả năng xử lý tốt dữ liệu có số chiều lớn. - Một nghiên cứu trước đây trong [6], chúng tôi đã đề nghị dùng giải thuật rừng ngẫu nhiên xiên phân (RF-ODT) được biết đến như là một giải thuật hiệu quả cho việc phân lớp dữ liệu có số chiều lớn. - Giải thuật RF-CART được phát triển trên ý tưởng của Bagging [2], phương pháp tiếp cận không gian con ngẫu nhiên của [1, 10]. - Sau đó kết hợp kết quả dự đoán của các cây, bầu chọn số đông cho vấn đề phân loại. - Amit và Geman [1] dùng việc chọn ngẫu nhiên các thuộc tính để tìm kiếm phân hoạch tốt nhất tại mỗi nút. - Cuối cùng, các tiếp cận này được mở rộng và chính thức được dùng trong rừng ngẫu nhiên của Breiman [3]. - Giải thuật RF-CART của Breiman xây dựng một tập hợp các cây quyết định hiệu quả cao nhưng có sự tương quan thấp giữa các cây thành viên. - Để giữ tính tương quan giữa các cây ở mức thấp, ông đề nghị sử dụng việc lấy mẫu có hoàn lại (bootstrap) từ tập dữ liệu ban đầu để xây dựng cây thành viên và chọn ngẫu nhiên một tập con các thuộc tính để tính phân hoạch tốt nhất ở các nút trong của cây. - Xét một tác vụ phân loại với m phần tử dữ liệu x i (i = 1,m) và n chiều (thuộc tính), một cây quyết định (ký hiệu là DT) trong rừng ngẫu nhiên gồm k cây (ký hiệu RF = {DT i } i=1,k ) được xây dựng như sau. - Rừng ngẫu nhiên RF-CART cho độ chính xác cao so với các giải thuật phân lớp tốt nhất hiện nay bao gồm Boosting [8] và SVM [21]. - Để khắc phục nhược điểm trên, nhiều giải thuật xây dựng cây quyết định sử dụng phân hoạch đa thuộc tính (xiên phân) tại các nút được đề nghị. - Rừng ngẫu nhiên xiên phân RF-ODT của chúng tôi trong [6] xây dựng các cây xiên phân ngẫu nhiên dựa trên siêu phẳng tối ưu (phân hoạch hiệu quả cao, khả năng chịu đựng nhiễu tốt) thu được từ huấn luyện SVM [21]. - Hình 5: Phân lớp tuyến tính với máy học véctơ hỗ trợ. - Xét ví dụ phân lớp nhị phân tuyến tính như hình 5. - SVM có thể sử dụng hàm nhân để phân lớp phi tuyến tính. - RF-ODT của chúng tôi xây dựng một tập hợp các cây quyết định xiên (trình bày trong hình 6), tương tự như trong RF-CART của Breiman [3]. - Điều khác biệt chủ yếu là mỗi cây quyết định xiên ngẫu nhiên trong rừng (RF-ODT ={ODT i } i=1,k ) sử dụng SVM cho phân hoạch xiên phân đa chiều thay vì là phân hoạch một chiều như CART. - Kết quả thực nghiệm của chúng tôi khi phân lớp dữ liệu có số chiều rất lớn trong [6] cho thấy RF-ODT hiệu quả hơn rừng ngẫu nhiên thông thường [3]. - Hình 6: Giải thuật rừng ngẫu nhiên xiên phân. - Hơn nữa, trong bài viết này chúng tôi cũng cải tiến thêm độ chính xác của RF- ODT bằng việc thay thế luật quyết định bình chọn số đông ở nút lá của cây xiên phân bởi luật quyết định cục bộ cho phép làm việc hiệu quả cho phân lớp ảnh vân tay. - Chẳng hạn như các giải thuật cây quyết định trước đây, khi học đến nút lá thì gán nhãn cho nút lá dựa vào luật bình chọn số đông. - Hiệu quả phân lớp không cao (phần tử p có thể sai).. - Hình 7: Luật bình chọn số đông (trái), nút lá có nhãn là vuông, nên điểm p và q đều được phân lớp vuông. - Với việc thay thế luật quyết định này, RF-ODT cho độ chính xác cao khi phân lớp ảnh vân tay.. - 4 KẾT QUẢ THỰC NGHIỆM. - Chúng tôi rất quan tâm đến độ chính xác của hệ thống phân loại vân tay đề nghị trong nghiên cứu. - Do đó chúng tôi đã tiến hành thử nghiệm trên dữ liệu thực tế để đánh giá hiệu quả của phương pháp đề nghị. - Chúng tôi đã thu thập 480 ảnh dấu vân tay (như được mô tả trong bảng 1) của 15 đồng nghiệp bằng thiết bị đọc Microsoft ® Fingerprint và bộ công cụ libfprint [7]. - Sau đó, chúng tôi cũng sử dụng thư viện [16] để tiền xử lý ảnh, rút trích các điểm đặc trưng từ giải thuật phát hiện Hessian Affine và véctơ mô tả SIFT. - Sau đó, giải thuật k-means [15] được áp dụng để gom nhóm các véctơ mô tả SIFT vào 2000 clusters tương ứng với 2000 từ vựng. - Nghi thức kiểm tra chéo (10-fold) được áp dụng để đánh giá hiệu quả của các giải thuật phân lớp. - Kết quả được tổng hợp từ 10 lần thực thi như vừa mô tả.. - Bảng 1: Dữ liệu ảnh vân tay. - Chúng tôi muốn so sánh hiệu quả của giải thuật RF-ODT mà chúng tôi đề nghị với các giải thuật khác, bao gồm cây quyết định C4.5 [19], RF-CART [3], AdaBoost [8] của C4.5, SVM [21] và k láng giềng (kNN). - Để thực hiện mục tiêu này, chúng tôi đã cài đặt giải thuật RF-ODT của chúng tôi bằng ngôn ngữ C/C. - Các giải thuật khác đã có trong các thư viện phần mềm miễn phí, như LibSVM [5], thư viện Weka [22] có sẵn các giải thuật C4.5, RF-CART, AdaBoost-C4.5 và kNN. - Mỗi giải thuật đều có các tham số được chọn cho kết quả cao nhất. - Cuối cùng chúng tôi thu được kết quả phân lớp của các giải thuật như bảng 2.. - Khi so sánh, chúng ta có thể thấy RF-ODT cho kết quả cao nhất với độ chính xác là 99,79%. - LibSVM với hàm nhân RBF cũng cho kết quả 99,38% gần bằng RF- ODT. - Hai giải thuật tiếp theo là RF-CART và AdaBoost-C4.5 cho kết quả khá tốt.. - Tuy nhiên, kNN và C4.5 lại cho kết quả thấp cách biệt so với RF-ODT.. - Bảng 2: Kết quả phân lớp ảnh vân tay. - Tham số Giải thuật Chính xác. - Để xét chi tiết kết quả thu được từ RF-ODT, chúng tôi trình bày kết quả trong ma trận confusion mà ở đó dòng trình bày cho cá thể trong tập dữ liệu và cột là kết quả phân lớp của RF-ODT. - Trong hình 8, ta có thể thấy rằng RF-ODT chỉ có sai duy nhất 1 ảnh vân tay của Binh Nguyen (lớp 7) được dự đoán vào Nghi Do (lớp 1).. - Tất cả 479 ảnh còn lại đều phân lớp đúng, đạt độ chính xác 99,79%. - Chúng tôi tin tưởng rằng, hệ thống phân lớp vân tay dựa vào véctơ SIFT và RF-ODT có thể áp dụng vào thực tiễn.. - Hình 8: Kết quả phân lớp của rừng ngẫu nhiên xiên phân. - Chúng tôi trình bày một hệ thống phân loại vân tay mới và hiệu quả. - Để áp dụng mô hình này lên ảnh, chúng tôi cho sử dụng các từ trực quan và mô hình hóa ảnh như túi các từ trực quan. - Các từ trực quan được xây dựng bằng cách phân nhóm các đặc trưng cục bộ SIFT bằng giải thuật k-means. - Theo mô hình này ảnh vân tay được biểu diễn bằng một véctơ tần suất mô tả phân phối của các từ trực quan trên ảnh. - Trong giai đoạn phân lớp, chúng tôi đề xuất sử dụng và mở rộng giải thuật rừng ngẫu nhiên xiên phân. - hình ảnh dấu vân tay từ 15 đồng nghiệp của chúng tôi tại Khoa Công nghệ Thông tin &. - Hệ thống phân loại vân tay của chúng tôi đã đạt được độ chính xác 99,79% (chỉ nhận dạng sai 1 ảnh).. - Với các kết quả khả quan thu được, chúng tôi dự định triển khai phương pháp này vào các ứng dụng thực tế như: chấm công tự động, nhận dạng tội phạm. - Chúng tôi cũng sẽ tiến hành nhiều thử nghiệm nữa trên một số lượng dữ liệu lớn và cũng có thể so sánh với các phương pháp tiếp cận khác [7, 9] trong tương lai.