Đồ án Thiết kế hệ thống nhận dạng vân tay từ ảnh số

2S , 3S ) mô tả bằng sơ đồ khối sau: Hình-8. Tổ hợp màu. Đáp ứng phổ ( )i Ca sẽ được tính như sau trong dải bước sóng ( ) max min ( ) ( )i iC S c d l l a l l l= ò , 1,3i = . Với phân phối xác xuất của ba màu ( )kp x , 1,3k = nên có: max min ( ) 1 x k x p x dx =ò . 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 11 Giả sử ba màu cơ bản được tổ hợp theo tỉ lệ ( )kb l , 1,3i = . Để tạo ra một màu có phân bố phổ năng lượng ( )C l sẽ bằng 3 1 ( ) ( )k k k p xb l = å . Thay giá trị vào phương trình về đáp ứng phổ: max max3 3 3 , 1 1 1min min ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )i i k k k i k k i k k k k c S x p x dx x S p x dx x a l l l l a l b b l b = = = æ ö = = =ç ÷ è ø å å åò ò trong đó: max i, k min ( ) ( )i kS p x dx l l a l= ò . Như vậy có thể tổ hợp màu theo phép cộng màu với ia là hệ số tổ hợp theo công thức tổng quát sau: 1 2 3X R G Ba a a= + + Tổ chức quốc tế về chẩn hóa màu CIE đã đưa ra một số không gian màu như: RGB, CMY, CMYK, HIS,… Trong đó mô hình RGB có vai trò quan trọng. x red P green blue é ù ê ú= ê ú ê úë û a) b) Hình-9. Hệ tọa độ màu: a) mô hình màu RGB; b) biểu diễn điểm ảnh trong hệ tọa độ màu RGB. 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 12 3.1.3. Chuyển đổi màu Hệ tọa độ màu do CIE quy định như một hệ quy chiếu và trên thực tế không thể biểu diễn hết các màu. Tùy thuộc vào các ứng dụng khác nhau người ta đưa ra thêm một số hệ tọa độ khác như NTSC, CMY, YIQ... phù hợp với yêu cầu hiển thị màu sắc. Việc chuyển đổi giữa các không gian biểu diễn màu thực hiện theo nguyên tắc sau: x xP A P *= ´ , trong đó: xP : không gian biểu diễn màu ban đầu, xP * : không gian biểu diễn màu mới, A : ma-trận phép biến đổi. Ảnh dùng trong đồ án này là ảnh xám. Mức xám là kết quả của sự mã hóa tương ứng một cường độ sáng của điểm ảnh với một trị số. Giá trị của nó phụ thuộc vào mức độ lượng tử hóa ảnh, như các ảnh dùng làm cơ sở dữ liệu đã lấy 8-bit để mã hóa ảnh (ứng với 256 mức xám, trong đó mức xám 0 là màu đen, mức xám 255 là màu trắng). Khi chuyển đổi từ ảnh màu RGB sang ảnh xám có thể dùng công thức sau: 1 2 3grayscale R G Ba a a= + + , các hệ số ia lần lượt như dưới đây [6]. 1 2 30,2989; 0,5870; 0,1140a a a= = = 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 13 3.2. Xử lý ảnh số trong Matlab Đứng về mặt xử lý tín hiệu nói chung và xử lý ảnh nói riêng, Matlab là công cụ rất mạnh. Hầu hết các thuật toán về ảnh và xử lý ảnh đều đã được thể hiện trong các hàm của Matlab như các hàm đọc, ghi ảnh, chuyển đổi giữa các hệ màu của ảnh, các thuật toán phát hiện biên, tách đối tượng, khớp mẫu, các phép biến đổi ảnh như xoay ảnh, chuẩn kích thước, tịnh tiến,... Các thư viện ngày càng được mở rộng, các hàm ứng dụng có thể được lập bởi người sử dụng. Ứng dụng phần mềm Matlab trong xử lý ảnh sẽ có được nhiều tiện ích và trợ giúp. Câu lệnh Matlab được gần với các thuật ngữ mô tả kỹ thuật, câu lệnh ngắn gọn và có thể tra cứu nhanh trong chức năng Help. Trong Matlab có nhiều Toolbox hỗ trợ các ứng dụng chuyên sâu. Với bài toán nhận dạng hình ảnh, các Toolbox thường được sử dụng gồm: · Image Processing Toolbox · Image Acqusition Toolbox · Wavelet Toolbox · Signal Processing · Statistics Toolbox · Neural Network Toobox Các thuật toán xử lý trong đồ án đều được viết bằng ngôn ngữ lập trình phần mềm Matlab. Các chương trình có sử dụng một một số thư viện của Matlab (chủ yếu trong Image Processing Toolbox, Statistics Toolbox). Sau đây là một số công cụ xử lý và thuật toán xử lý ảnh chính được ứng dụng trong đồ án. 3.2.1. Histogram Histogram (lược đồ xám) thể hiện tần suất xuất hiện mỗi mức xám trong ảnh. Lược đồ xám biểu diễn trong hệ tọa độ Oxy: trục hoành biểu diễn N mức xám (tùy theo số bit mã hóa pixel), trục tung biểu diễn số điểm ảnh một mức xám tương ứng. 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 14 Lược đồ xám cung cấp thông tin về phân bố mức xám của ảnh. Nó cho phép phân tích trong khoảng nào đó phân bố phần lớn mức xám của ảnh. Nếu ảnh sáng thì lược đồ xám lệch về phía bên trái, nếu ảnh tối thì lược đồ xám lệch về bên phải so với điểm quy chiếu (giữa mức xám N). a) b) c) d) Hình-10. Phân tích lược đồ xám: a) ảnh sáng và b) lược đồ xám của (a) lệch phải; c) ảnh tối và d) lược đồ xám của (c) lệch trái. 3.2.2. Phân ngưỡng cục bộ Phân ngưỡng với mục đích làm tăng độ tương phản các đối tượng cần quan tâm đông thời loại bớt nhiễu. Nếu phân ngưỡng toàn bộ ảnh nhiều khi tỏ ra không hiệu quả, nhất là khi cường độ sáng của ảnh không đồng đều. Phân ngưỡng cục bộ cũng giống như phân ngưỡng nhưng chỉ khác ở điểm: ngưỡng được chọn thích nghi với từng vùng cục bộ của ảnh. Điều này rất có ý nghĩa trong khâu nhị phân hóa ảnh vân tay. Vùng cục bộ thường dùng có thể là các block dạng hình vuông hay hình chữ nhật. 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 15 Ảnh xám khi phân ngưỡng thì kết quả phân ngưỡng đi đôi với nhị phân hóa ảnh. Một điểm bất kỳ (x, y) thuộc ảnh f khi có ( , )f x y T³ thì được gọi là object point (điểm trên nền), trường hợp còn lại gọi là background point (điểm nền). Đối tượng ưu tiên trích chọn từ phân ngưỡng không quan trọng là bachground point hay object point. Đấy chỉ là các tên gọi quy ước và chúng có thể chuyển đổi dễ dàng cho nhau nhờ biến đổi âm bản. Hình-11. Giá trị ngưỡng tối ưu. Kết quả phân ngưỡng được ảnh ( , )g x y thì nó được định nghĩa liên hệ ( ) 1 : ( , ), 0 : ( , ) f x y T g x y f x y T ³ì = í <î 3.2.3. Biến đổi Fourier-2D rời rạc Biến đồi Fourier rời rạc trong xử lý ảnh số nhằm mục đích lọc lấy các thành phần tín hiệu ảnh có tần số trội. Với ảnh vân tay vùng ảnh co các đường vân đóng vai trò làm tín hiệu có tần số trội. Có ( , )f x y , với 0, 1x M= - và 0, 1y N= - là một ảnh số cỡ M N´ . Biến đổi Fourier rời rạc của f là ( , )F u v . ( ) 1 1 2 / / 0 0 ( , ) ( , ) M N j ux M vy N x y F u v f x y e p - - - + = = = åå , 0, 1u M= - , 0, 1v N= - . 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 16 Biến đổi ngược Fourier rời rạc định nghĩa bởi công thức: ( ) 1 1 2 / / 0 0 ( , ) ( , ) M N j ux M vy N u v f x y F u v e p - - - + = = = åå , 0, 1x M= - , 0, 1y N= - . Biến đổi Fourier rời rạc của ảnh f còn được viết dưới dạng: ( ),( , ) ( , ) j u vF u v F u v e f-= , trong đó ( ),u vf là góc pha, ( , )F u v là phổ Fourier. Các bước thực hiện lọc ảnh trong miền tần số bằng biến đổi Fourier rời rạc có thể mô tả bởi sơ đồ dưới đây. Hình-12. Các bước thực hiện lọc ảnh trong miền tần số. 3.2.4. Lọc ảnh Sobel Lọc Sobel là một trường hợp của lọc số tuyến tính. Nghĩa là bộ lọc dùng một convolution-mask (cửa sổ dùng để nhân chập, gọi tắt mask), rồi lấy tổng có trọng số các điểm lân cận với điểm ở chính giữa trong mask đó. Di chuyển mask trên toàn bộ miền tín hiệu ảnh, mỗi bước một pixel, cuối cùng thu ảnh kết quả. 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 17 Tổng quát, lọc tuyến tính của ảnh số f cỡ M N´ với convolution-mask có cỡ m n´ định bởi như sau ( ) ( )( , ) , , a b s a t b g x y w s t f x s y t =- =- = + +å å , trong đó: ( )1 / 2a m= - , ( )1 / 2b n= - và 0, 1x M= - , 0, 1y N= - . Hình-13. Các bước lọc ảnh bằng toán tử không gian. 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 18 Đáp ứng lọc số tại từng điểm (x,y) là R, đối với lọc Sobel sẽ là ( ) ( ) 9 7 8 9 1 3 4 1 2 2x xi i i R w z z z z z z z = = = + + - + +å , ( ) ( ) 9 3 6 9 1 4 7 1 2 2y yi i i R w z z z z z z z = = = + + - + +å , trong đó iz là mức xám của ảnh. a) b) Hình-14. Biểu diễn mask: a) các hệ số của mask cỡ 3 3´ ; b) các hệ số của cặp mask dùng cho lọc Sobel 3.2.5. Phát hiện biên bằng toán tử gradient Sử dụng toán tử gradient trong miền 2D là một trong các phương pháp dùng để phát hiện biên. Toán tử định nghĩa như là một vec-tơ hai thành phần x y G f x G f y é ù ¶ ¶é ù Ñ = =ê ú ê ú¶ ¶ë ûë û f Toán tử xác định mô-đun và góc của gradient lần lượt như sau ( ) ( ) ( ) ( ) ( ) 1/ 22 2 1/ 22 2/ / , , . x y x y f mag G G f x f y x y arctg G Ga é ùÑ = Ñ = +ë û é ù= ¶ ¶ + ¶ ¶ë û = f 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 19 Thông thường thành phần mô-đun chỉ cần tính xấp xỉ là đã đạt yêu cầu độ chính xác của bài toán đặt ra. Hai công thức gần đùng hay sử dụng là tổng các bình phương 2 2x yf G GÑ » + và tổng các giá trị tuyệt đối x yf G GÑ » + . 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 20 3.2.6. Loang rộng và thu nhỏ đối tượng Loang rộng (dilation) và thu nhỏ (erosion) đối tượng là hai toán tử cơ của nhóm thuật toán xử lý morphology. Cả hai toán tử này chỉ áp dụng cho các ảnh nhị phân và mô tả toán học của morphology là các phép toán tập hợp [3]. Đồ án sẽ vận dụng nhiều hai thuật toán trong công đoạn: khoanh vùng ảnh, làm mảnh biên, và hiệu chỉnh đường vân. a) c) b) d) Hình-15. Loang rộng đối tượng. a) ảnh ban đầu với đối tượng hình chữ nhật; b) strel có ba pixel xếp thành dạng đoạn thẳng, chéo 450 so với phương ngang; c) strel di chuyển khắp ảnh và các điểm bị tác động; d) ảnh kết quả. Phần tử cơ bản để thực hiện loang rộng hay thu hẹp gọi là structuring element (viết tắt là strel). Căn cứ vào ảnh gốc cộng với độ lớn và hình dạng của 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH 21 strel, đối tượng bị cắt bớt hoặc thêm vào từng điểm ảnh (phù hợp với khuôn hình của strel) Trường hợp đặc biệt, áp dụng toán tử thu hẹp liên tiếp đủ số lần thì có quá trình làm mảnh đối tượng tới một pixel. a) c) b) d) Hình-16. Thu nhỏ đối tượng. a) ảnh ban đầu với đối tượng hình chữ nhật; b) strel có ba pixel xếp thành dạng đoạn thẳng vuông góc với phương ngang; c) strel di chuyển khắp ảnh và các điểm bi tác động; d) ảnh kết quả. 4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG 22 4. Sơ đồ khối thiết kế hệ thống nhận dạng vân tay Trong phần nay sẽ giới thiệu một số phương pháp nhận dạng vân tay. Tiếp theo là các hình hệ thống nhận dạng đa năng. Ở mỗi phần, sẽ lựa chọn ra phương án thực hiện trong đồ án. Đây là hai tiền đề xây dựng nên sơ đồ hệ thống nhận dạng vân tay cho đồ án này. 4.1. Các nguyên lý nhận dạng vân tay Các nguyên lý nhận dạng vân tay thì liên quan chặt chẽ đến cách thức tìm ra sự tương đồng giữa ảnh vân tay đầu vào với một template trong cơ sở dữ liệu vân tay. Dưới đây là ba phương pháp chính lần lượt dựa trên các cơ sở là đối sánh minutiae, correlation và ridge feature [1], ch. 4. · Minutiae-base matching, · Correlation-base matching, · Ridge feature-base matching. a) b) Hình-17. Tạo mã vân tay: a) ảnh ban đầu; b) trích chọn minutiae quan trọng (các minutie được đánh dấu O) 4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG 23 Phương pháp đầu tiên phổ biến hơn cả và được ứng dụng rất rộng rãi. Hai vân tay sẽ được so sánh bằng các điểm minutiae trích ra từ các vân tay đó. Giai đoạn thứ nhất này còn goi là tạo mã [11], các minutiae tạo thành tập hợp điểm đặc trưng và được lưu trữ trong từng mảng 2D. Giai đoạn thứ hai sẽ tìm vị trí khớp phù hợp giữa template và input-image sao cho số các minutiae tao thanh cặp tương đồng là lớn nhất. Còn hai nguyên lý còn lại không phù hợp với đồ án. Correlation-based thực hiện bằng cách xếp chồng hai mẫu vân tay lên nhau để tìm ra tương quan giữa chúng, phương pháp này gặp hạn chế khi quá trình thu nhận ảnh vân tay gặp phải các biến dạng méo. Còn ridge feature-base là một phương pháp cao cấp, đòi hỏi các bước xử lý phức tạp và thường dùng cho ứng dụng nhận dạng với các vân tay có chất lượng rất xấu (chẳng hạn như vân tay latent). Đồ án này lựa chọn phương án đầu tiên vì đó là một phương pháp cơ bản, phù hợp với điều kiện hiện tại cho phép và cũng hứa hẹn cho kết quả khả quan. 4.2. Hệ thống nhận dạng vân tay Nhận dạng vân tay là một bộ phận của sinh trắc học. Vì thế phân loại hệ thống nhận dạng sinh trắc học cũng bao hàm cho hệ thống nhận dạng vân tay nói riêng. Có hai hình thức phân loại hệ thống nhận dạng vân tay: dựa trên kiến trúc của hệ thống và cách xử lý dữ liệu trong hệ thống [1], tr. 237-240. a) Phân loại hệ thống theo kiến trúc: · Hệ thống có kiến trúc song song · Hệ thống có kiến trúc nối tiếp · Hệ thống có kiến trúc thứ bậc b) Phân loại hệ thống theo các xử lý dữ liêu: · Hệ thống có khâu hợp nhất sau trích chọn đặc tính · Hệ thống có khâu hợp nhất sau đối sánh · Hệ thống có khâu hợp nhất sau tổng hợp kết quả Với khuôn khổ đồ án, sẽ chọn hệ thống cấu trúc nối tiếp làm nền tảng. 4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG 24 4.3. Xây dựng hệ thống nhận dạng vân tay bằng ảnh số Trên cơ sở các phân tích đã nêu, sau đây là đề xuất về sơ đồ khối hệ thống nhận dạng vân tay bằng ảnh số. Hệ thống này có khả năng phân loại vân tay, tạo cơ sở dữ liệu và nhận dạng vân tay. · Kiểu nhận dạng là identification, nghĩa là một mẫu cần nhận dạng (input) sẽ nhận kết quả bằng cách đối sánh với N mẫu khác trong cơ sở dữ liệu (template). · Kiểu chế độ hoạt động của hệ thống hướng đến là online. Nghĩa là hệ thống có thể hoạt động liên tục, có khả năng ghép với khâu thu thập số liệu sử các phương pháp thu nhận ảnh live-scan (bằng máy scan, sensor,…) và quan trọng hơn có thể vừa thu thập số liệu vừa có thể nhận dạng. · Kiến trúc hệ thống thiết kế theo hướng xử lý dữ liệu nối tiếp, gồm tám khâu chính trình bày trong Hình-18. Hình-18. Sơ đồ khối hệ thống nhận dạng vân tay. Tám khâu này có cá chức năng hoạt động như sau: 1) Khâu số 1: thực hiện thu nhận ảnh. 4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG 25 2) Khâu số 2: thực hiện trích chọn đặc tính vân tay để phân loại. Đặc tính trích chọn là góc định hướng, orientation. 3) Khâu số 3: thực hiện tạo vec-tơ đặc tính để phân loại. 4) Khâu số 4: thực hiện phân loại vân tay làm năm nhóm. 5) Khâu số 5: làm cơ sở dữ liệu, lưu trữ các template-image. 6) Khâu số 6: thực hiện trích chọn minutiae. Đặc tính trích chọn là miutiae. 7) Khâu số 7: thực hiện đối sánh input-image với template-image. 8) Khâu số 8: thực hiện đưa ra kết quả nhận dạng. 5. TẬP MẪU ẢNH VÂN TAY 26 5. Tập mẫu ảnh vân tay Vân tay có thể lưu trữ theo hai cách: trên giấy (giấy thường, giấy ảnh...) hoặc file ảnh. Đối với cách thứ nhất vẫn còn được ứng dụng trong giám định, định danh hình sự (các bằng chứng về dấu tay tội phạm cần được thể hiện bằng ảnh in trên giấy). Cách thứ hai được ứng dụng phổ biến trong nhận dạng nói chung và ngày càng chiếm được nhiều ưu thế (có thể lưu trữ, tìm kiếm thuận tiện). Đồ án này tập trung đến hình thức lưu trữ ảnh theo file. a) b) c) Hình-19. Các loại vân tay: a) vân tay latent; b) vân tay lăn mực; c) vân tay trong Db2b-FVC2000. Có nhiều định dạng ảnh vân tay khác nhau, phổ biến hơn cả là: jpeg, bmp, tif, gif, png,... Các thông số ảnh bao gồm: độ rộng của ảnh, độ phân giải, số bit dành cho một pixel, độ chính xác hình học, méo,... Khi thiết kế hệ thống nhận dạng vân tay, các thông số ảnh thông thường được quy chuẩn theo giải giá trị nào đó sao cho phù hợp với hệ thống. Hệ thống nhận dạng vân tay bằng ảnh số, ảnh số là đại lượng đầu vào nên hai thông quan tâm hơn cả: kích thước và độ phân giải. Như đã trình bày ở trên, đồ án này sử dụng dữ liệu ảnh FVC2000 để tạo cơ sở dữ liệu hệ thống nhận dạng và kiểm tra kết quả nhận dạng. Các mẫu vân tay lưu theo file ảnh, có phần mở rộng .tif, kích thước của ảnh 256364´ pixel. Mỗi mẫu vân tay gồm bảy ảnh khác nhau và được lưu tên theo quy ước xx_y. Trong đó xx là chỉ số về thứ tự của bộ mẫu (còn gọi là chỉ bản) trong tập dữ liệu ảnh, y là thứ 5. TẬP MẪU ẢNH VÂN TAY 27 tự của ảnh trong một bộ mẫu. Bộ mẫu sẽ đươc chia làm hai: một phần dùng để thực hiện trích chọn và tạo mã cho vân tay thông qua các thuật toán xử lý ảnh (mục đích cuối là tạo ra các template xây dựng cơ sở dữ liệu); phần còn lại dùng để kiểm tra, đánh giá thuật toán xử lý. 6. TRÍCH CHỌN MINUTIAE 28 6. Trích chọn minutiae cho đối sánh vân tay Đồ án này được thiết kế bằng cách chia nhỏ các công đoạn chính trên thành các mô-đun nhỏ hơn. Hướng chung là chọn các phương pháp mà có thể tận dụng được các mô-đun chương trình ở công đoạn này và áp dụng được cho công đoạn khác. Nhưng các phương pháp lựa chọn phải đạt yêu cầu cho bài toán nhận dạng cuối cùng. Vì vậy, tạo tính mở cho hệ thống và tiết kiệm thời gian thiết kế. Hình-20. Thuật toán trích chọn minutiae. Với sơ đồ này thấy rằng, trích chọn minutiae thực hiện qua tám khâu. · Khối tiền xử lý ảnh thực hiện chuẩn hóa kích thước ảnh. · Khối tăng cường chất lượng ảnh thực hiện làm nổi rõ đường vân. · Khối orientation image thực hiện ước lượng trường định hướng. · Khối segmentation (khoanh vùng ảnh vân tay) thực hiện tách vùng ảnh cần quan tâm nhiều trong xử lý trích chọn đặc tính. · Khối tạo ridge map (ảnh nhị phân với đường vân có giá trị logic 1). · Khối làm mảnh đường vân. Đường vân làm mảnh tới độ rộng đồng nhất một pixel từ ridge map. · Khối hiệu chỉnh đường vân và lọc minutiae sai cấp một. Đường vân sẽ được làm “trơn”, minutiae sai kiểu lake (dạng hình xuyến nhỏ), dạng điểm, chẽ ngắn, đoạn vân ngắn sẽ loại bỏ. · Lọc minutiae sai cấp hai và tạo mã vân tay bằng minutiae. Kết thúc khâu này các template sẽ được tạo ra. 6. TRÍCH CHỌN MINUTIAE 29 6.1. Chuẩn hóa ảnh đầu vào Chuẩn hóa ảnh đầu vào là bước cần thiết trước khi vào bước tiền xử lý ảnh. Do ảnh dùng cho trích trọn đặc tính có thể không phù hợp về kích thước cũng như phân bố mức xám. Trong đồ án, giai đoạn này gồm: chuẩn hóa kích thước ảnh và đồng đều hóa cường độ sáng giữa các ảnh đầu vào khác nhau. 6.1.1. Chuẩn hóa kích thước ảnh Ảnh chuẩn đầu vào có kích thước 256364´ pixel. Các thuật toán xử lý ảnh vân tay về sau thường áp dụng cho từng từng block vuông trên ảnh (thường sử dụng các block vuông cạnh 16 pixel, 32 pixel,…). Nên kích thước ảnh chuẩn hóa hợp lý hơn là 256352´ pixel. Để thực hiện điều này sẽ “cắt” đi vùng dữ liệu ảnh kích thước 12 256´ pixel. Phần này cũng không ảnh hưởng quá nhiều tới kết quả nhận dạng cuối cùng vì đối với bộ dữ liệu đã chọn, các vùng ảnh ở gần khung thường đóng vai trò làm background. Hàm thực hiện chuẩn hóa kích thước ảnh đầu vào là norsizfv. gns = norsizfv(g, bs), trong đó: g : ảnh số đầu vào có kích thước cần được chuẩn hóa, bs : kích thước của block mà ảnh đầu ra sẽ được làm tròn theo, gns : ảnh đầu ra có kích thước đã chuẩn hóa. 6.1.2. Cân bằng cường độ sáng của ảnh Do điều kiện thu thập ảnh khác nhau với mỗi lần lấy mẫu vân tay; do kỹ thuật thu nhận ảnh (sử dụng sensor, scanner,…) khác nhau nên độ sáng ảnh vân tay không gần nhất. Vì vậy cần làm đồng đều cường độ sáng của các ảnh vân tay trong bộ dữ liệu. Phương pháp thực hiện: dùng một ảnh mẫu có cường độ sáng đồng đều, rồi chuẩn hóa độ sáng của các ảnh khác theo ảnh này bằng bình phương cực tiểu. Trong đồ án sử dụng ảnh có cùng kích thước cường độ sánh các điểm ảnh [ ], 128I i j = (là mức xám trung trung bình trong 255 mức). 6. TRÍCH CHỌN MINUTIAE 30 Hàm thực hiện cân bằng cường độ sáng của ảnh là briequfv. gbb = briequfv(g,ref), trong đó: g : ảnh số đầu vào cần được chuẩn hóa cường độ sáng, ref : ảnh số làm mẫu gbb : ảnh đầu ra có cường độ sáng gần với ảnh mẫu. 6.2. Tăng cường ảnh chất lượng ảnh Thu nhận ảnh không phải lúc nào cũng cho những ảnh với chất lượng tốt. Tăng cường ảnh sẽ giúp cải thiện chất lượng ảnh trước khi thực hiện các thuật toán xử lý ảnh tiếp theo nhằm gia tăng hiệu quả xử lý. Hai thuật toán sử dụng để tăng cường ảnh chất lượng ảnh ở đây là: histogram equalization (cân bằng lược đồ xám) và biến đổi Fourier rời rạc [1], tr. 104-113. a) b) c) Hình-21. Tăng cường ảnh: a) ảnh ban đầu; b) ảnh sau cân bằng histogram; c) ảnh sau biến đổi Fourier rời rạc. 6.2.1. Tăng cường ảnh bằng cân bằng histogram Histogram của ảnh xám là một biểu đổ thể hiện quan hệ giữa cường độ ảnh và số pixel có cùng cùng cường độ ảnh đó. Cân bằng histogram sẽ làm đồng đều cường độ sáng trong bản thân ảnh đó. 6. TRÍCH CHỌN MINUTIAE 31 Hàm thực hiện tăng cường ảnh bằng cân bằng lược đồ xám là hisequfv. ghe = hisequfv(g), trong đó: g : ảnh số đầu vào, ghe : ảnh đầu ra đã được tằng cường bằng cân bằng lược đồ xám. 6.2.2. Tăng cường ảnh bằng biến đổi Fourier-2D Sử dụng lọc Gabor và biến đổi Fourier là hai nền tảng chính để thực hiện tăng cường ảnh trong xử lý ảnh vân tay. Ảnh sau khi đã được tăng cường chất lượng bằng histogram equalization, thực hiện bước kế tiếp là tăng cường ảnh bằng thuật toán biến đổi Fourier [1, 8, 9, 10]. So với các phương pháp trên cơ sở lọc Gabor, nó lợi thế hơn ở chỗ không yêu cầu việc 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 phục vụ cho mục đích cuối công đoạn tạo ridge-map. Công thức tính toán cho thuật toán tăng cường ảnh bằng biến đổi Fourier rời rạc có dạng như sau: ( ) ( ){ }kenh yxIFyxIFFI ],[],[1 ×= - trong đó: k : hệ số mũ của phổ Fourier, [ ]( )F I x,y : phổ Fourier. Đồ án thực hiện tăng cường chất lượng ảnh bằng biến đổi Fourier rời rạc cho từng block có kích thước 3232´ pixel. Theo cách này, các thành phần ảnh có tần số trội sẽ được giữ lại, đó là các vùng ảnh thể hiện làm đường vân. Ảnh sau biến đổi Fourier rời rạc có các đường vân “nổi” hơn, sự phân tách giữa các đường vân cũng thể hiện rõ ràng hơn. Đồng thời các vùng ảnh nhiễu sẽ loại bớt đi. 6. TRÍCH CHỌN MINUTIAE 32 Số mũ của phổ Fourier, k đóng vai trò làm hệ số điều chỉnh. Trong [1], khuyến nghị đặt 6,0=k khi tính toán với kích thước block như trên. Tuy nhiên, trong quá trình thực hiện, đặt 0,35k = thì cho kết quả tốt hơn so với việc chọn giá trị khác. Vì phổ Fourier đóng vai trò làm hàm lọc, do đó: k càng nhỏ hàm lọc tiến tới 1 (ảnh gốc và ảnh sau khi tăng cường không khác nhau nhiều); với k lớn, các đoạn vân cục bộ có thể bị biến dạng không còn khả năng xử lý cho công đoạn tiếp nữa. Hàm thực hiện tăng cường ảnh bằng biến đổi Fourier rời rạc là fouenhfv. gfe = fouenhfv(g,k), trong đó: g : ảnh số đầu vào, k : hệ số, gfe : ảnh đầu ra đã được tăng cường bằng biến đổi Fourier. 6.3. Ước lượng orientation image và khoanh vùng ảnh vân tay Trong phần này sẽ trình bày các ước lượng định hướng vân tay cục bộ. Đây là cần thiết để chọn được các thông số thích hợp để lọc ảnh về sau (lọc nhiễu, khoanh vùng ảnh...). Vì orientation image (trường định hướng) mang tính mô tả góc định hướng đường vân, nên kết quả này còn được áp dụng để phân loại kiểu vân tay (quyết định bởi sự tạo hình của các đường vân). 6.3.1. Ước lượng orientation image Trường định hương thể hiện bản chất tự nhiên của đường vân và các rãnh đường vân. Trường định hướng cung cấp nhiều thông tin quan trong cho các bước xử lý tiếp theo. Phần này sẽ trình bày về ước lượng orientation image D, phần tử định hướng ijq (tương ứng với nó là góc định hướng ijq và mô-đun định hướng). Có sự phân biệt khác nhau giữa các thuật ngữ mô tả phần tử định hướng orientation (có [ ]0,ijq pÎ ), direction (có [ ]0, 2ijq pÎ ) khi tính toán trường định hướng [1]. 6. TRÍCH CHỌN MINUTIAE 33 Nguyên lý thực hiện tính định hướng: chia ảnh thành các khối ww´ , sau đó khảo sát lần lượt định hướng cục bộ của đường vân trong từng khối đó. Orientation image sẽ được ước lượng bằng phương pháp Gradient [3, 4] a) b) Hình-22. Ước lượng orientation image: a) ảnh vân tay ban đầu; b) orientation image tương ứng Các công thức tính toán: ( ) ( ) ( )å å + -= + -= = 2 2 2 2 ,,2, wi wiu wj wjv yxn vugvugjiG , ( ) ( ) ( )( )å å + -= + -= -= 2 2 2 2 22 ,,, wi wiu wj wjv yxd vugvugjiG , ( ) ( )( ) ,1, 2 , n d G i j i j arctg G i j q æ ö = ç ÷ç ÷ è ø . Ở đây: ( )jig x , , ( )jig y , là các gradient tại ( )ji, theo các trục x, y và tính bằng toán tử Sobel [5, 6]. 6. TRÍCH CHỌN MINUTIAE 34 Hàm thực hiện ước lượng trường định hướng là oriimafv. [iD, iC, DF] = oriimafv(g,bs), trong đó: g : ảnh số đầu vào, bs : kích thước block vuông ước lượng định hướng, iD : ma-trận lưu đính hướng của mỗi block, iC : ma-trân lưu level-certenty của mỗi block, DF : ma-trân lưu định hướng và tọa độ tâm của mỗi block. 6.3.2. Khoanh vùng ảnh vân tay Khoanh vùng ảnh vân tay nhằm mục đích phân chia các vùng khác nhau trên ảnh vân tay. Ở đây, chúng ta quan tâm đến foreground/background (ảnh nền và ảnh trên nền) cùng với biên ảnh vân tay. Trong nhận dạng vân tay, vùng ảnh mang thông tin hữu ích giới hạn bởi vùng có các đường vân (đóng vai trò làm foreground). Vùng ảnh còn lại thường là các nhiễu tạo ra trong quá trình thu nhận, sao chép, lưu trữ ảnh… (đóng vai trò làm background) cần được tách ra khỏi foreground. Khoanh vùng ảnh vân tay nằm trong nhóm thuật toán segmentation. Tổng quát, nó dựa vào hai tính chất của ảnh số liên quan đến cường độ sáng để thực hiện, đó là: sự không liên tục và sự tương tự nhau [3]. Ảnh vân tay trong đồ án sẽ khoanh vùng lấy vùng hữu ích dựa vào cả hai tính chất kể trên. Tiêu chí đánh giá là certainty level (một giá trị thể hiện sự biến thiên của cường độ sáng theo các đường vân). Theo cách này vùng ảnh đóng vai trò background và foreground được phân tách nhờ một ngưỡng đặt trước [2]. Công thức tính certainty level cho từng block kích thước w w´ , trọng tâm tương ứng của block có tọa độ [ ],i j như sau: ( ) ( ) ( )( )jiG jiGjiG ww jiC s dn , ,,1, 22 + ´ = 6. TRÍCH CHỌN MINUTIAE 35 Một ngưỡng cT được đặt ra và block đó định nghĩa làm · background nếu ( ) cTjiC <, , · foreground nếu ( ) cTjiC ³, . Phương pháp này có lợi thế kế thừa được các kết quả tính toán trong phần ước lượng orientation image. a) b) c) Hình-23. Khoanh vùng ảnh vân tay: a) ảnh ban đầu; b) variance field; c) ảnh đã khoanh vùng đường vân. Hàm thực hiện khoanh vùng ảnh có các đường vân tay là segimafv. area = segimafv(iC,k), trong đó: iC : ma-trận lưu giá trị level-certenty cục bộ, bs : kích thước block, area : vùng ảnh vân tay đã được khoanh. 6.4. Trích chọn minutiae Giai đoạn này bao gồm: nhị phân hóa ảnh bằng thuật toán local threshold với ảnh đã được tăng cường kết hợp với kết quả khoanh vùng ảnh vân tay ở phần 6. TRÍCH CHỌN MINUTIAE 36 trên; sau đó với ảnh có các đường vân đã được làm mảnh đến độ rộng một pixel thì thực hiện tìm minutiae bằng thuật toán crossing number [1], ch. 4. a) b) Hình-24. Thông số của hai dạng minutiae quan trọng: a) bifurcation; b) termination. 6.4.1. Nhị phân hóa và làm mảnh đường vân Sau tăng cường ảnh bằng biến đổi Fourier rời rạc, đường vân tây đã nổi rõ hơn so với ảnh ban đầu. Đây là lúc sử dụng thuật toán local threshold chuyển đổi ảnh xám đã tăng cường chất lượng đó thành ảnh đen trắng. a) b) Hình-25. Nhị phân hóa và làm mảnh đường vân: a) ridge-map; b) thinned ridge-map. Kích thước cửa sổ 3232´ pixel trong biến đổi Fourier rời rạc thì kích thước block cho phân ngưỡng cục bộ có thể là: 32 32´ ,32 16´ ,16 16´ ,16 8´ pixel… Thử nghiệm với block 16 16´ pixel thì cho kết quả tốt hơn (các đường vân tách biệt rõ 6. TRÍCH CHỌN MINUTIAE 37 ràng hơn). Ảnh này tiếp tục được làm mảnh bằng thuật toán morphology cho ảnh đen trắng sau cùng với đường vân thể hiện bằng đường màu trắng (giá trị logic 1) có độ rộng đồng nhất một pixel. Hàm thực hiện nhị phân hóa ảnh vân tay là locthrfv. glt = locthrfv(g,bs,adj), trong đó: g : ảnh đầu vào, bs : kích thước block, adj : hệ số hiệu chỉnh, glt : ảnh đầu ra đã được nhị phân hóa. 6.4.2. Phát hiện minutiae Vân tay sau khi đã làm mảnh có thể bắt đầu tìm các minutiae. Thuật toán dùng để phát hiện minutiae sử dụng trong đồ án là crossing number. Nó dùng một cửa sổ kích thước 3 3´ pixel, lấy tất cả các điểm ảnh trong cửa sổ, sau đó khảo sát giá trị logic của các điểm ảnh xung quanh điểm ảnh [ ],i j ở chính giữa cửa sổ đó. Tùy vào kết quả tính toán của biểu thức crossing number thì kết luận rằng: điểm [ ],i j đang xét là một điểm phân nhánh, điểm cụt hay đang nằm trên một đường vân. Công thức tính như sau: ( ) ( )å = --= 8 1 18mod2 1)( i ii pvalpvalpcn Ảnh sử dụng phát hiện các minutiae phải là ảnh nhị phân, do đó ( ) { }1,0Îpval . Các biến 721 ...,,, ppp thứ tự tạo thành các điểm lân cận điểm giữa cửa sổ đang khảo sát xét theo một chiều thuận hoặc ngược kim đồng hồ. 6. TRÍCH CHỌN MINUTIAE 38 Khi đó định nghĩa điểm [ ],i j đang xét là: · trên đường vân nếu cp(n) = 2, · termination minutiae nếu cn(p) = 1, · bifurcation minutiae nếu cn(p) = 3. Thuật toán tìm kiếm và giá trị crossing number có vai trò quan trọng. Không những được dùng trong việc phát hiện minutiae mà nó còn giúp loại bỏ các minutiae sai (được cho là nhiễu). a) cn(p) = 2 b) cn(p) = 2 a) cp(n) = 3 d) cn(p) = 1 Hình-26. Phát hiện minutiae: a), b) pixel trên đường vân; c) bifurcation minutiae; d) termination minutiae. Hàm thực hiện phát hiện minutiae là finminfv. [ter, bif] = finminfv(g), trong đó: g : ảnh đầu vào có độ rộng đường vân một pixel, ter : ma-trận lưu tọa độ của termination minutia, bif : ma-trận lưu tọa độ của bifurcation minutia. 6. TRÍCH CHỌN MINUTIAE 39 6.4.3. Ước lượng khoảng cách đường vân Vân tay trên ngón tay không giống nhau giữa mỗi người. Ngay cả trường hợp ở một người, các đường vân cũng thể hiện sự khác biệt trên từng ngón tay. Do vậy, ước lượng khoảng các đường vân được hiểu là dải trị trung bình khoảng cách giữa hai đường vân song song và gần nhau. Đây là một thông tin làm tiền đề cho công đoạn lọc minutiae về sau. Ảnh nhị phân có các đường vân đã được làm mảnh đến 1 pixel tạo ra từ khâu làm mảnh đã có, tỏ ra rất thuận tiện với phương pháp scan trong việc ước lượng khoảng cách đường vân. Theo cách này, sẽ quét một số dòng và một số cột trên ảnh (thinned ridgemap), lưu lại vị trí điểm trên đường vân, sau đó tính giá trị trung bình khoảng cách điểm là được kết quả cần tìm. Hàm thực hiện phát hiện ước lượng độ rộng đường vân là mearidfv. rd = mearidfv(g), trong đó: g : ảnh đầu vào có độ rộng đường vân môt pixel, rd : độ rộng trung bình của đường vân. 6.4. Hiệu chỉnh đường vân và lọc minutiae sai Trong phần này sẽ trình bay về vấn vân đề loại bỏ các minutiae sai. Những nhiễu này chủ yếu được tao ra từ quá trình làm mảnh đường vân, và cũng có những nhiễu từ khâu thu nhận ảnh Các công việc thực hiện: làm “trơn” đường vân, “nối” các đường vân bị đứt trong ngưỡng giới hạn, “tách” các đường vân bị dính, cuối cùng là tạo mã vân tay từ minutiae. 6.4.1. Hiệu chỉnh đường vân và lọc minutiae sai cấp một Giai đoạn này thực hiện hiệu chỉnh các vân tay và các tín hiệu cho là nhiễu (đoạn vân ngắn, chẽ nhánh cụt, vòng xuyến nhỏ…) sẽ được loại đi. Như vậy sẽ 6. TRÍCH CHỌN MINUTIAE 40 làm tăng tính xác thực của các minutiae đã trích chọn được so với ảnh vân tay gốc ban đầu. a) c) Hình-27. Số minutiae phát hiện được: a) ngay sau làm mảnh vân; b) sau lọc minutiae. (vùng ảnh đánh dấu vuông và tròn thể hiện điển hình một số minutiae sai được loại bỏ) Khi thực hiện hai nhiêm vụ này, thông tin cần cần biết trước là khoảng các trung bình giữa các đường vân rd. Nó đã được ước lượng từ bước scan ảnh vân tay làm mảnh trình bày ở trên. Sau đó, việc lọc minutiae sẽ căn cứ theo rd cộng thêm các điểm “nút” tìm thấy bằng thuật toán crossing number. a) b) Hình-28. Lọc các minutiae. a) minutiae sai; b) các minutiae sai bị loại bỏ 6. TRÍCH CHỌN MINUTIAE 41 Hàm thực hiện phát hiện thuật toán hiệu chỉnh đường vân tay và lọc minutiae cấp một là smoridfv. [gs, ster, sbif] = smoridfv (g), trong đó: g : ảnh đầu vào có độ rộng đường vân một pixel, gs : ảnh đầu ra đã được làm “trơn” đường vân, ster : ma-trận lưu tọa độ của termination minutia, sbif : ma-trận lưu tọa độ của bifurcation minutia. 6.4.2. Lọc minutiae sai cấp hai và tạo mã từ minutiae Khi các đường vân đã làm “trơn”, các điểm minutiae được tìm kiếm một lần nữa và số lượng các điểm sai cũng đã được giảm đáng kể. Tuy nhiên còn hai lỗi mà quá trình trên chưa khắc phục được là “nối” các đường vân bị đứt (khoảng các giữa hai đầu mút < rd) và “cắt” đoạn vân nối hai đường vân dạng cầu chữ H (khoảng cách cầu < rd). Giải pháp thực khắc phục là so sánh khoảng cách định giữa hai điểm nút và góc định hướng của chúng theo ngưỡng ( ,d qD D ) để loại bỏ. Trong đồ án chọn [ ]6, 6q p pD Î - (khoảng góc rộng hơn hoặc hẹp hơn tỏ ra ít có hiệu quả trong khi thưc hiện đồ án), còn d rdD = . Hình-29. Các minutiae được trích chọn cuối để tạo mã. 6. TRÍCH CHỌN MINUTIAE 42 Hàm thực hiện sai cấp hai và tạo mã từ minutiae là extminfv [eter, ebif] = extminfv (g), trong đó: g : ảnh đường vân môt pixel đã làm “trơn”. eter : ma-trận lưu tọa độ của termination minutiae, ebif : ma-trận lưu tọa độ của bifurcation minutiae. Các minutiae trích chọn cuối cùng này sẽ được lưu trữ thành file tạo template cho cơ sở dữ liệu. Thông tin lưu trữ là tọa độ, định hướng minutiae. Quá trình tạo mã từ minutiae hoàn tất khâu trích chọn đặc tính để định danh. 7. PHÂN LOẠI VÂN TAY 43 7. Phân loại kiểu vân tay Hệ thống nhận dạng identification, cơ sở dữ liệu có thể lên đến hàng triệu chỉ bản nên quá trình đối chiếu 1:N dĩ nhiên tốn rất nhiều thời gian [1], tr.173. Phân loại vân tay nhằm mục đích tổ chức các template theo từng category (nhóm phân loại) để tiết kiệm thời gian nhận dạng (cho một input-image khi hệ thống hoạt động). a) b) c) d) e) Hình-30. Năm kiểu vân tay trong thực tế: a) arch ; b) whorl ; c) tented arch; d) left loop ; e) right loop. Mặc dù đồ án giới hạn trong số lượng mẫu ít để thực hiện xử lý dữ liệu đó và thử nghiệm. Nhưng hệ thống nhận dạng vân tay trong đồ án này được thiết kế theo kiểu identification (có khả năng đối chiếu 1:N). Tuân thủ kiểu nhận dạng của hệ thống và hướng thiết kế mở đặt ra ban đầu thì phân loại vân tay là khâu không thể bỏ qua. Giải pháp phân loại vân tay ở đây sử dụng cây quyết định (treefit), như vậy sẽ kế thừa được nhiều kết quả của phần trích chọn đặc tính vân tay cho đối chiếu ở trên. 7. PHÂN LOẠI VÂN TAY 44 Quá trình phân loại vân tay được thực hiện qua ba khâu chính 1) trích chọn đặc tính định hướng cục bộ, 2) tạo vec-tơ đặc tính, 3) bộ phân loại. Các vân tay được phân loại vào năm category: A, L, R, T, W, tương ứng với arch, left loop, right loop, tented arch và whorl [1], ch.5. Hình-31. Sơ đồ khối mô tả thuật toán phân loại vân tay. 7.1. Trích chọn đặc tính Phân loại vân tay thì phụ thuộc nhiều vào các điểm kỳ dị (singular point), bao gồm điểm delta và điểm core. Khi đã có orientation image các điểm kỳ dị có thể xác định thuân lợi bằng phương pháp Poincaré. Đặc tính cần trính chọn là góc định hướng cục bộ ,i jq [1, 3, 8]. a) b) Hình-32. Phương pháp chỉ số Poincaré: a) trong miền liên tục; b) trong ảnh số. 7. PHÂN LOẠI VÂN TAY 45 Chỉ số Poincaré của trường định hướng tại điểm ảnh [ ],i j theo một đường bao kín tính như sau: ( ) ( ) 0 1é , , 2 N k Poincar i j k p = = Då ( ) ( ) ( ) ( ) ( ) ( ) ( ) , , 2 , , 2 , , 2 d k d k k d k d k d k d k p d d p p d d pp d d ì <ï ï ïD = + ³í ï ï - £ -ïî ( ) ( )( ) ( )( )( ) ( ) ( )( )1 mod , 1 mod , .i j i jd k DF L k L L k L DF L k L kd = + + - Trong đó L là một đường bao kín lấy điểm [ ],i j , iL và jL tạo hệ trục tọa độ hướng hàng và hướng cột tại điểm đang xét. Chỉ số Poincaré bằng 0,5 nếu điểm đó là core, bằng 0,5- nếu điểm đó là delta. Đồ án thực hiện thuật toán phát hiện core với đường bao L có chiều dài 16 pixel và bao quanh điểm [ ],i j . 7.2. Tạo vec-tơ đặc tính Sau khi phát hiện được điểm core, vec-tơ đặc tính được tạo ra bằng các khoanh vùng lấy 11 11´ định hướng cục bộ mà điểm này làm trọng tâm. Một ma-trận cỡ 11 11´ không thích hợp làm vec-tơ đầu vào cho khâu phân loại nên nó được điều chỉnh lại kích thước thành vec-tơ 121 thành phần. Mỗi thành phần này là góc định hướng định hướng cục bộ của block có tọa độ [ ],i j . ( )1 2 121, , ..., , ...,f kV q q q q= , [ ]0, , 1,121k kq pÎ = . Vec-tơ chuẩn hóa của fV là ±fV có các thành phần thuộc đoạn [ ]0,1 . ± 1 2 121f 1V , , ..., , ...,kfV qq q q p p p p p æ ö= = ç ÷ è ø . 7. PHÂN LOẠI VÂN TAY 46 Dưới hình ảnh mô tả quá trình tạo vec-tơ đặc tính 1,1 1,11 11,1 11,11 V q q q q æ ö ç ÷= ç ÷ ç ÷ è ø K M O M L a) b) Hình-33. Lấy đặc tính cho phân loại: a) vùng tạo vec-tơ đặc tính; b) vec-tơ đặc tính tương ứng. 7.3. Khâu phân loại kiểu vân tay Giải pháp thực hiện khâu phân loại vân tay dùng cây quyết định (treefit), đây là một giải pháp tốt cho bài toán phân loại kiểu vân tay (thể hiện ở kết quả nhận dạng). Hình-34. Kết quả cây quyết định của bài toán phân loại kiểu vân. 7. PHÂN LOẠI VÂN TAY 47 Do số nút trong cây quyết định không biết trước. Cây quyết định cũng cần xác định cấu trúc tối ưu. Tiêu chí để đánh giá dùng cặp sai số học và sai số kiểm tra (là các hàm của số nút) để tìm ra số nút đầu cuối mà có sai số kiểm tra bé nhất. Cấu trúc cây đánh giá là tốt nếu nó thật đơn giản (có ít nhánh nhất), nhưng vẫn phải đảm bảo độ chính xác. Trong khâu phân loại này, bộ mẫu sử dụng trích ra từ 175 ảnh và tiến hành xây dựng cây tối ưu thông qua thuật toán cross-validation. Theo cách này, sẽ dùng 90% mẫu ngẫu nhiên để xây dựng cây và dùng 10% số mẫu còn lại để kiểm tra sai số. Sai số cho quá trình xây dựng cây được gọi là resubstitution. Hình-35 thể hiện đường cong sai số kết quả của bài toán phân loại vân tay. Cấu trúc tối ưu của cây gồm sáu nút. Sai số học là 1,14%. Sai số kiểm tra là 9,14%. Hình-35. Đường cong sai số học và kiểm tra. 8. ĐỐI CHIẾU VÂN TAY 48 8. Đối chiếu vân tay để định danh mẫu Cũng giống như phân loại vân tay, có rất nhiều các để thực hiện đối chiếu vân tay. Tuy nhiên có thể chia làm nhóm phương pháp [1], tr. 131-168. · Correlation-based · Minutiae-based · Ridge feature-based Vì ngay từ ban đầu đã lựa chọn phương pháp nhận dạng vân tay trên cơ sở là minutiae. Nên khâu thực hiện đối chiếu vân tay sẽ dựa vào các điểm nút đặc trưng nay. Việc đối chiếu dựa trên hai bộ số liệu: I của input-image và T của template-image. { }1 2, ,..., pT T m m m= , { }, ,i i i im x y q= , 1,i p= . { }1 2, ,..., qI I m m m¢ ¢ ¢= , { }, ,j j j jm x y q¢ ¢ ¢ ¢= , 1,j q= . Hình-36 dưới đây thể hiện sự đối sánh hai mẫu vân tay trên cơ sở các minutiae đã được trích chọn ở bước trên. Hai minutiae ở mỗi mẫu được nối với nhau bằng đường liền nét thì thể hiện sự trùng khớp với nhau. Hình-36. Đối chiếu vân tay dựa trên cơ sở minutiae. Sau đây sẽ trình bày thuật toán đối sánh vân tay, bao gồm cả hai công đoạn: khớp mẫu (alignment) và đối sánh (matching) [3], ch. 6. 8. ĐỐI CHIẾU VÂN TAY 49 8.1. Khớp mẫu hai mẫu vân tay Khớp mẫu vân tay được hiểu là “đặt” một mẫu vân tay cần đối sánh với mẫu mà nó cần sẽ đối sánh ở một vị trí sao cho có sự phù hợp giữa chúng theo một ngưỡng. Vì vậy các toán tử dùng để khớp mẫu gồm có: ma-trận quay, tịnh tiến… Thuật toán alignment bao gồm các bước 1) chọn lấy một cặp minutiae của input và template, 2) xoay các đối tượng của template theo các đối tượng của input, 3) tính mức độ phù hợp pS của hai mẫu input và template cho đến khi đạt một ngưỡng đặt trước rT . Các đối tượng của template và input ở đây chính là các đoạn vân tay mà có điểm minutiae đã trích chọn, độ dài của các đoạn vân này được lấy bằng khoảng cách trung bình giữa các đường vân rd tính từ điểm minutiae làm mốc. rT lấy giá trị bằng 0,8 [3], tr. 117. 1 0 0 1 0 0 1 x R T y Dæ ö ç ÷= Dç ÷ ç ÷ è ø Hình-37. Khớp mẫu từng đối tượng: a) toán tử ma-trận tịnh tiến; b) quay và tịnh tiến đối tượng Còn pS tính theo công thức: 2 2 0 0 rd rd p i i i i i i S d D d D = = = å å Cuối cùng sẽ tìm được điểm minutiae tham chiếu ( )ef , ,rIT x y q cho bước tiếp theo là matching. 8. ĐỐI CHIẾU VÂN TAY 50 8.2. Đối sánh vân tay Khi đã khớp được hai mẫu vân tay, việc tiếp theo là làm phù hợp giữa T và I. Đầu tiên sẽ thực hiện quay toàn bộ các minutiae của template theo điểm tham chiếu đã chọn được ở bước khớp mẫu. Toán tử quay RA định nghĩa như sau: os sin 0 sin os 0 0 0 1 c RA c q q q q æ ö ç ÷= -ç ÷ ç ÷ è ø Tiếp theo, sẽ đếm các cặp minutiae thỏa mãn sai lệch về vị trí và góc trong giới hạn e . Để đánh giá mức độ giống nhau sẽ dùng thang điểm cf NS q= , với cN là số cặp điểm minutiae thỏa mãn lân cân e ; q là tổng số minutiae của input a) b) Hình-38. Thực hiện matching: a) khớp các minutiae; b) ngưỡng lân cận để tính điểm (score). Hàm thực hiện phát hiện đối sánh vân tay là matimafv. score = matimafv(f,g,e ), trong đó: f : mẫu input-image, g : mẫu template-image, e : giá trị lân cận, score : điểm kết quả của đối sánh hai mẫu. 8. ĐỐI CHIẾU VÂN TAY 51 Thử nghiệm với hai ảnh đầu của mỗi bộ mẫu (xx_1.tif và xx_2.tif) với tất cả các mẫu còn lại của bộ dự liệu (gồm 125 ảnh đánh số xx_3.tif đến xx_7. tif, tổng cộng có 6250 phép thử nghiệm) nếu lấy kết quả so sánh có score cao nhất thì chính xác đạt 100%. Tuy nhiên bộ số liệu này còn có khả năng mở rộng thêm nên hình thức thể hiện kết quả minh bạch hơn là một dải kết quả chính xác từ cao đến thấp. Việc hiển thị 1, 2, 5 hay nhiều kết quả đều có thể thực hiện không khó khăn. Trong đồ án thể hiện ra bốn kết quả sát với ảnh đầu vào nhất. Ví dụ: Hình-39 cho thấy khi nhận dạng ảnh 7_2 (của người 7, mẫu số 2) thì cả bốn mẫu gần nhất đều của người 7, trong đó mẫu 5 giống 100%. 7_5.tif 100score » 7_6.tif 86,67score » 7_7.tif 71,11score » 7_3.tif 71,11score » 7_2.tif a) b) Hình-39. Kết quả nhận dạng: b) vân tay đầu vào; a) các vân tay được nhận dạng theo (b). Các chương trình chạy trong Matlab phiên bản 7.0; cấu hình phần cứng: CPU Pentium IV 1,8Ghz, RAM 512MB, FSB 333Mhz. Thời gian tạo cơ sở dữ liệu: cho tất cả đầu vào gồm 175 ảnh cần thời gian khoảng 10 phút. Nên thời gian trung bình tạo một template khoảng 3,4 giây. Thời gian thực hiện đối sánh: thử nghiệm với 6250 lần đối sánh ( 25 2´ mẫu kiểm tra với 25 5´ mẫu còn lại) thì mất khoảng 2,5 giờ. Nên thời gian trung bình một lần thực hiện đối sánh khoảng 1,4 giây. 9.TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN 52 9. Tổng kết và hướng phát triển Nhận dạng vân tay là một trong những lĩnh vực nghiên cứu chuyên sâu. Các tài liệu, thuật toán, mô-đun chương trình rất hạn chế vì bản quyền tác giả. Kết thúc đồ án, đã xây dựng được phần mềm mô phỏng các bước thực hiện nhận dạng trong hệ thống nhận dạng vân tay. Các mô-đun chương trình cần thiết cũng đã được hoàn thành. Sau đây là phần tổng kết chi tiết và hướng phát triển mở rộng của đồ án. 9.1. Kết quả của đồ án · Đã thực hiện nhận dạng được ảnh số vân tay đầu vào với độ chính xác cao. Nếu chỉ lấy một giá trị có điểm đánh giá cao nhất trong các kết quả so sánh thì nhận dạng dược 100%. Tuy nhiên con số này còn bị giới hạn bởi số lượng mẫu khảo sát còn ít. · Hệ thống xây dựng theo như kiểu dự kiến ban đầu, đó là nhận dạng identification (1:N), chính vì vậy kết quả nhận dạng thể hiện minh bạch bằng một dải giá trị sắp xếp theo tiêu chí: giống với mầu đầu vào nhiều cho tới ít · Thực hiện phân loại kiểu vân tay có độ chính xác khá cao, đạt 90,86%. Điều này khẳng định sự khả thi mở rộng cở sở dữ liệu ảnh. Phân loại kiểu vân tay tốt đồng nghĩa với việc hạn chế tìm kiếm so sánh vân tay ở một nhóm template (thay vì toàn bộ) mà vân đảm bảo chính xác. · Chương trình xử lý thuật toán trong đồ án thiết kế theo mô-đun và có thể tận dụng cho các khâu khác cùng hệ thống. · Hệ thống thiết kế có tính mở. Có khả năng thay thế các mô-đun thực hiện thuật toán. Cơ sở dữ liệu ảnh có thể bổ sung thêm dễ dàng. Những kết quả trên cho thây hệ thống nhận dạng trong đồ án có thể triển khai vào thực tế. 9.TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN 53 9.2. Những kiến thức bản thân thu được · Đã nắm được đại cương về xử lý ảnh, biết được các thuật toán cơ bản của xử lý ảnh. · Biết cách phân tích và trích chọn các đặc tính của đối tượng thông các thuật toán về xử lý ảnh. · Các chương trình thực hiện các thuật toán xử lý hầu hết do bản thân viết trong Matlab, các thư viện chuẩn và các script file hỗ trợ người sử dụng chỉ mang ý nghĩa tham khảo. 9.3. Những hạn chế của đồ án · Về bộ mẫu: các ảnh dùng làm cơ sở dữ liệu còn ít, được trích ra từ Db-2a và Db-2b của FVC2000. Các ảnh trong mẫu này có chất lượng tương đối tốt, các mẫu chất lượng xấu vẫn còn là khó khăn với đồ án này. · Các thuật toán xử lý: với hạn chế về kiến thức, tài liệu cũng như hạn chế về thời gian và phương tiện xử lý nên còn có các thuật toán (được tác giả nghiên cứu lâu năm trong lĩnh vực này đánh giá tốt, đồng thời cũng khó khăn trong triển khai) chưa được áp dụng trong đồ án. Như trong khâu tăng cường ảnh và tạo ridge-map thuật toán biến đổi Fourier tỏ ra kém hiệu quả với các ảnh vân tay bị đứt gãy liên tục. Quá trình post-processing dừng lại ở việc loại bỏ được một số dạng minutiae sai thường có nhưng không được tất cả. 9.4. Hướng phát triển · Tiếp cận với thuật toán xử ảnh bằng công cụ lọc Gabor nhằm giải quyết vấn đề xử lý các ảnh vân tay bị đứt gãy liên tục. Tuy nhiên đi với điều này sẽ phải giải quyết khó khăn về việc ước lượng chính xác tần số vân tay và định hướng cục bộ vân tay. · Giảm thời gian xử lý xuống thấp hơn nữa bằng cách tối ưu một số chương trình thực hiện thuật toán xử lý ảnh. 9.TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN 54 · Tiếp cận với thuật toán nhận dạng đường vân để phân loại chính xác hơn các dạng vân tay. · Các chương trình được thiết kế theo mô-đun, tính mở của hệ thống là xuyên suốt do đó không gặp khó khăn nhiều trong việc mở rộng cơ sở dữ liệu. Điều này cũng có nghĩa là bộ số liệu học có thể tăng thêm dễ dàng, góp phần cải thiện độ chính xác nhận dạng. Và cả việc thay thế nâng cấp các mô-đun chương trình cũng sẽ không gặp nhiều khó khăn. · Đóng gói thành sản phẩm hoàn thiện. PHỤ LỤC 55 Tài liệu tham khảo [1] Maltoni D., Maio D., Jain A. K., Prabhakar S., Handbook of Fingerprint Recognition, Springer, 2003. [2] Hoover J. E., The Science of Fingerprints Classification and Uses, United States Department of Justice, 2006. [3] Hong L., Automatic Personal Identification using Fingerprints, Michigan State Univesity, 1998. [4] Ratha N. K., Chen S., Jain A. K., Adaptiveow orientation based feature extraction in Fingerprint Recognition, Michigan State Univesity, 1995. [5] Gonzalez R C., Woods R. E., Digital Image Processing, 2nd Edition, Prentice Hall 2002. [6] Gonzalez R C., Woods R. E., Eddins S. L., Digital Image Processing using MATLAB, Prentice Hall 2004. [7] Neto H. V., Borges L. D.,Fingerprint Classification with Neural Networks. [8] Park H. C., Park H., Fingerprint Classification using Fast Fourier Transform and Nonlinear Discriminant Analysis, University of Minnesota. [9] Chickkerur S., Wu C., Govindaraju V., Cartwright A. N., Fingerprint Image Enhancement Using STFT Analysis. University at Buffalo. [10] Chickkerur S., Wu C., Govindaraju V., A systemmatic approach for feature extraction fingerprint images, University at Buffalo. [11] Komarinski P., Automated Fingerprint Identification Systems (AFIS), Elsevier, 2005. [12] Trần Hoài Linh. Bài giảng “Mạng nơ-ron nhân tạo và ứng dụng trong xử lý tín hiệu”. [13] Wuzhili, Fingerprint Recognition, Hong Kong Baptist University, 2002. PHỤ LỤC 56 Phụ lục Danh sách các script file khác trong đồ án STT Tên hàm Chức năng 1 angbiffv Tính góc định hướng của bifurcation minutiae 2 angterfv Tính góc định hướng của termination minutiae 3 arecarfv Khoanh vùng để tính chỉ số Poincaré 4 briequfv Cân bằng cường độ sáng 5 cronumfv Tính crosssing number 6 delboufv Xóa nhiễu ở ngoài đường bao tao ra bởi segmentation 7 delshofv Xóa các đoạn vân ngắn 8 fincorfv Tìm điểm core 9 finshofv Tìm đoạn vân ngắn 10 inpcatfv Lấy catogory 11 inpimafv Lấy input 12 leasqufv Ước lượng bình phương cực tiểu 13 loaimafv Load ảnh vào để xử lý 14 mearidfv Ước lượng khoảng cách trung bình của các đường vân 15 norsizfv Hiệu chỉnh kích thước ảnh 16 plominfv Hiển thị các minutiae 17 rotallfv Xoay tất các đối tượng để tìm cặp minutiae 18 rotridfv Xoay các đối tượng để khớp mẫu 19 genvecfv Tạo vector dữ liệu để phân loại 20 sortttfv Sắp xêp kết quả 21 thirid1fv Làm mảnh đường vân cấp một 22 thirid2fv Làm mảnh đường vân cấp hai PHỤ LỤC 57 Các bước chạy phần mềm mô phỏng Bước 1: Chuyển thư mục hiện hành tới thư mục Finger. Sử dụng lệnh: >> myGuifv để có cửa sổ giao diện trong Hình-40 Hình-40. Cửa sổ giao diện. Bước 2: Click vào nút Open, chon một file ảnh vân tay để bắt đầu trích chọn đặc tính. Hình-41. Mở một file ảnh. PHỤ LỤC 58 Bước 3: Click vào nút HE Enhancement để thực hiện tăng cường ảnh bằng cân bằng lược đồ xám. Hình-42. Cân bằng lược đồ xám. Bước 4: Click vào nút FB Enhancement để thực hiện tăng cường ảnh bằng biên đổi Fourier rời rạc và cân bằng cường độ sáng của ảnh. Hình-43. Biến đổi Fourier rời rạc và cân bằng cường độ sáng. PHỤ LỤC 59 Bước 5: Click vào nút Binarization để thực hiện phân ngưỡng cục bộ-nhị phân hóa ảnh. Hình-44. Nhị phân hóa ảnh. Bước 6: Click vào nút Orientation Image để ước lượng trường định hướng. Hình-45. Trường định hướng. PHỤ LỤC 60 Bước 7: Click vào nút Segmentation để khoanh lây vùng ảnh vân tay. Hình-46. Segmentation. Bước 8: Click vào nút Detection Core để tìm điểm core. Hình-47. Phát hiện core. PHỤ LỤC 61 Bước 9: Click vào nút Thinning để làm mảnh đường vân. Hình-47. Làm mảnh đường vân. Bước 10: Click vào nút Post-processing để lọc các minutiae. Hình-48. Lọc minutiae. PHỤ LỤC 62 Bước 11: Click vào nút Display Minutiae để hiện thị các minutiae sẽ tạo mã. Hình-49. Hiển thị minutiae. Bước 12: Click vào nút Matching để đối sánh vân tay. Hình-50. Đối sánh vân tay.