Luận văn Thạc sĩ Khoa học máy tính: Công nghệ sinh trắc học và bài toán nhận dạng vân tay

ĐẠI HỌC THÁI NGUYÊN

TR¦êNG §¹I HäC C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG ---------------------

NGUYỄN ANH TÚ

CÔNG NGHỆ SINH TRẮC HỌC VÀ BÀI TOÁN NHẬN DẠNG VÂN TAY

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

THÁI NGUYÊN - 2019

ĐẠI HỌC THÁI NGUYÊN

TR¦êNG §¹I HäC C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG ---------------------

NGUYỄN ANH TÚ

CÔNG NGHỆ SINH TRẮC HỌC VÀ BÀI TOÁN NHẬN DẠNG VÂN TAY Chuyên ngành: Khoa học máy tính Mã số: 8 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: TS. Vũ Vinh Quang

THÁI NGUYÊN - 2019

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

MỤC LỤC

MỤC LỤC ................................................................................................................... i

LỜI CAM ĐOAN .................................................................................................... iii

LỜI CẢM ƠN ........................................................................................................... iv

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT.......................................... v

DANH MỤC CÁC HÌNH ........................................................................................ vi

LỜI MỞ ĐẦU ............................................................................................................ 1

Chương 1: TỔNG QUAN VỀ SINH TRẮC HỌC VÀ BÀI TOÁN NHẬN

DẠNG VÂN TAY ............................................................................................. 3

1.1. Tổng quan về Sinh trắc học và Bài toán nhận dạng vân tay ................................ 3

1.2. Tình hình ứng dụng nhận dạng vân tay tại Việt Nam .......................................... 6

1.3. Mô hình bài toán nhận dạng vân tay .................................................................... 7

1.3.1. Mô hình hệ thống FINDER ............................................................................... 7

1.3.2 Mô hình hệ thống AFIS (Automated Fingerprint Identification System).......... 9

1.4. Thu nhận và lưu trữ ảnh vân tay ........................................................................ 10

1.4.1. Thu nhận ảnh vân tay ...................................................................................... 10

1.4.2. Lưu trữ ảnh và các thông tin đặc trưng của vân tay ........................................ 12

1.5. Tiền xử lý ảnh vân tay ........................................................................................ 13

1.6. Các đặc trưng của vân tay và vấn đề trích chọn đặc trưng ................................ 14

1.7. Vấn đề đối sánh ảnh ........................................................................................... 18

Chương 2: CƠ SỞ KHOA HỌC CỦA BÀI TOÁN NHẬN DẠNG VÂN TAY ...... 20

2.1. Phương pháp tăng cường ảnh ............................................................................. 20

2.1.1. Đặt vấn đề ....................................................................................................... 20

2.1.2. Tăng cường ảnh bằng phương pháp lọc Gabor ............................................... 20

2.2 Phương pháp rút trích đặc trưng ......................................................................... 28

2.2.1. Rút trích các đặc trưng từ ảnh đã được nhị phân hóa ..................................... 29

2.2.2. Rút trích các đặc trưng trực tiếp từ ảnh xám ................................................... 32

2.3 Phương pháp đối sánh vân tay ............................................................................ 33

2.3.1 Đặt vấn đề ........................................................................................................ 33

2.3.2 Đối sánh dựa vào độ tương quan ..................................................................... 35

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

2.3.3 Đối sánh dựa vào đặc trưng ............................................................................. 36

2.3.4 Đối sánh đặc trưng cục bộ và toàn cục ............................................................ 39

2.3.5 Đối sánh dựa vào đặc tính vân ......................................................................... 40

Chương 3: XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÂN TAY ...................... 43

3.1. Tính hướng vân tay cục bộ. ................................................................................ 43

3.2. Chuẩn hóa ảnh. ................................................................................................... 45

3.3. Tăng cường ảnh .................................................................................................. 46

3.4 Tách ngưỡng tự động. ......................................................................................... 47

3.5 Thuật toán tìm xương. ......................................................................................... 48

3.6 Thuật toán tìm kiếm chi tiết. ............................................................................... 50

3.7 Thuật toán Hough ................................................................................................ 51

3.8 Thuật toán đối sánh vân tay ................................................................................ 51

KẾT LUẬN .............................................................................................................. 53

TÀI LIỆU THAM KHẢO ...................................................................................... 54

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

PHỤ LỤC

iii

LỜI CAM ĐOAN

Tôi xin cam đoan đề tài: “Công nghệ sinh trắc học và bài toán nhận dạng

vân tay” là công trình nghiên cứu khoa học của cá nhân. Các kết quả nghiên

cứu và các kết luận trong luận văn là trung thực, khách quan và phù hợp với

thực tiễn của Việt Nam. Các số liệu sử dụng phân tích trong luận văn có

nguồn gốc rõ ràng, đã được công bố theo đúng quy định. Trong quá trình thực

hiện luận văn tôi có tham khảo các tài liệu liên quan nhằm khẳng định thêm

sự tin cậy và tính cấp thiết của đề tài. Việc tham khảo các nguồn tài liệu đã

được thực hiện trích dẫn và ghi nguồn tài liệu tham khảo đúng quy định.

Thái Nguyên, ngày tháng năm 2019

Học viên

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Nguyễn Anh Tú

LỜI CẢM ƠN

Trong quá trình nghiên cứu và thực hiện luận văn, tôi đã nhận được sự

hướng dẫn tận tình của TS. Vũ Vinh Quang và những ý kiến quý báu về

chuyên môn của thầy đã giúp tôi hoàn thành luận văn này. Đến nay, tôi đã

hoàn thành luận văn thạc sĩ với đề tài “Công nghệ sinh trắc học và bài toán

nhận dạng vân tay”, chuyên ngành Khoa học máy tính.

Tôi cũng xin trân trọng cảm ơn các Lãnh đạo và đồng nghiệp trong Khoa

Ngoại ngữ - Đại học Thái Nguyên nơi tôi công tác và làm việc cũng như gia

đình bạn bè và người thân đã quan tâm, ủng hộ, tạo điều kiện thuận lợi nhất

giúp đỡ tôi trong quá trình thực hiện luận văn.

Do trình độ, kinh nghiệm nghiên cứu còn hạn chế cũng như thời gian

nghiên cứu ngắn nên luận văn khó tránh khỏi những thiếu sót, tôi rất mong

nhận được những ý kiến đóng góp của quý thầy cô và bạn đọc. Để luận văn

này có thể hoàn chỉnh hơn nữa.

Xin trân trọng cảm ơn!

Thái Nguyên, ngày tháng năm 2019

Học viên

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Nguyễn Anh Tú

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

STT Tên viết tắt Chú giải

Ridge Count 1 RC

Total Ridge Count 2 TRC

Pattern Intensity 3 PI

Automated Teller Machine 4 ATM

Automated FingerPrint Identification System 5 AFIS

6 CNSTH Công nghệ sinh trắc học

7 NDVT Nhận dạng vân tay

8 DVT Dấu vân tay

9 VT Vân tay

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

10 NPH Nhị phân hóa

DANH MỤC CÁC HÌNH

Hình 1.1: Vân tay trên đèn của người Palettin (400 A. D) ............................... 4

Hình 1.2: Con dấu thương mại của Berwick (1809) ......................................... 4

Hình 1.3: Chữ kí bằng vân tay của người ......................................................... 5

Trung Quốc khi mua bán (1839) ....................................................................... 5

Hình 1.4: Mô hình hệ thống FINDER ............................................................... 8

Hình 1.5: Các ảnh vân tay thu được ................................................................ 11

Hình 1.6: Các điểm đơn .................................................................................. 15

Hình 1.7a: Các điểm đặc trưng cục bộ ............................................................ 16

Hình 1.7b: Các điểm đặc trưng cục bộ ............................................................ 17

Hình 2.1: Các bước lọc Gabor ........................................................................ 21

Hình 2.2: Minh họa kết quả chuẩn hóa ảnh; (a) ảnh gốc, (b) ảnh đã được

chuẩn hóa ........................................................................................ 21

Hình 2.3: a, Ước lượng hướng ảnh mà chưa làm mượt; b, Ước lượng hướng

ảnh đã được làm mượt .................................................................... 23

Hình 2.4: Cửa sổ hướng và X- signature ........................................................ 26

Hình 2.5: Biểu diễn đồ họa của bộ lọc Gabor xác định bởi tham số  = 90, f =

1/5, x = y = 3. ............................................................................... 27

Hình 2.6: Một biểu diễn đồ họa trong một nhóm 24 bộ lọc Gabor (n0 =

8, n1 = 5) với x = y =4. ............................................................. 28

Hình 2.7: Các bước rút trích đặc trưng từ ảnh đã được nhị phân hóa ............ 29

Hình 2.8: Kết quả của việc Nhị phân hóa và Làm mỏng của ảnh đã được

tăng cường ....................................................................................... 30

Hình 2.9: a, Một phần điểm vân tay; b,Điểm kết thúc; c, Điểm rẽ nhánh ...... 30

Hình 2.10: Lỗ và đứt gãy nhỏ trong ảnh vân tay đã được Nhị phân hóa và

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

làm mỏng......................................................................................... 31

vii

Hình 2.11: Các cấu trúc vân lỗi phổ biến được điều chỉnh lại thành các cấu

trúc vân đúng ................................................................................... 31

Hình 2.12: Các đường vân (ridge) và các rãnh (ravine) trên bề mặt vân tay. . 32

Hình 2.13: Điểm cực đại (ic, jc) tương ứng với (is, js). .................................. 33

Hình 2.14: Các đặc tính của cấu trúc cục bộ được dùng bởi Jiang và

Yau (2000). .................................................................................... 40

Hình 2.15: Sơ đồ nhận dạng vân tay dùng kỹ thuật FingerCode .................... 42

Hình 3.1: Hướng vân tay cục bộ ..................................................................... 44

Hình 3.2: Ảnh đã chuẩn hóa ............................................................................ 45

Hình 3.3: Vân tay sau khi tăng cường ............................................................. 46

Hình 3.4: Vân tay sau khi tách ngưỡng tự động ............................................. 47

Hình 3.5: Xương của ảnh vân tay ................................................................... 50

Hình 3.6: Các điểm đặc biệt của vân tay ......................................................... 51

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 3.7: Ảnh 2 vân tay cần so khớp .............................................................. 52

LỜI MỞ ĐẦU

Ngày nay, CNSTH được ứng dụng trong nhiều lĩnh vực khác nhau và

phát triển rộng rãi trên toàn thế giới. Nó đã và đang thu được những thành tựu

to lớn, những ứng dụng thực tiễn ngày càng khẳng định vai trò không thể

thiếu trong cuộc cách mạng công nghiệp 4.0, được áp dụng nhiều trong khoa

học kỹ thuật cũng như trong đời sống thường ngày.

Một bộ phận của CNSTH là Khoa học xử lý ảnh, trong đó có Khoa học

NDVT đã được nghiên cứu từ lâu đời và hiện nay được áp dụng rất nhiều

trong các mảng lĩnh vực xã hội. Đồng thời việc phát triển của các thiết bị

phần cứng cả về phương diện thu nhận, hiển thị, tốc độ xử lý đã mở ra nhiều

hướng mới cho công nghệ nhận dạng nói chung và nhận dạng ảnh vân tay nói

riêng. Nó có thể giải quyết các bài toán như giám sát tự động, bảo mật dữ

liệu, xác thực cá nhân phục vụ trong các cơ quan, ngân hàng …

CNSTH được áp dụng phổ biến và lâu đời nhất là công nghệ nhận dạng

vân tay. Dấu vân tay là một đặc điểm quan để phân biệt giữa người này và

người khác. Công nghệ này đã mang lại nhiều thành quả lớn lao về mặt khoa

học công nghệ nói chung và đời sống con người nói riêng. Hiện nay, vân tay

là một trong những công nghệ mang tính bảo mật tốt nhất và thông dụng nhất.

Nhiều sản phẩm công nghệ đã ứng dụng vân tay để bảo vệ thông tin, tài sản,

dữ liệu như: Máy vi tính, Điện thoại, két sắt, khóa cửa, máy chấm công, …

Các nước phát triển đã bắt đầu triển khai ứng dụng công nghệ NDVT vào

chứng minh, hộ chiếu điện tử.

Xuất phát từ những lý do trên, để góp phần vào công cuộc xây dựng và

bảo vệ Tổ quốc trong tình hình mới cũng như góp phần vào sự phát triển ứng

dụng công nghệ thông tin tại các cơ quan, xí nghiệp. Nhằm đảm bảo trong quá

trình quản lý nhân sự, an toàn bảo mật dữ liệu thông tin nhân sự em đã mạnh

dạn nghiên cứu đề tài : “Công nghệ sinh trắc học và bài toán nhận dạng

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

vân tay” để tìm hiểu các giải pháp xác thực thông tin qua nhận dạng dấu vân

tay bằng các bài toán nhận dạng ảnh và các thuật toán cơ bản về nhận dạng

DVT. Qua đó xây dựng chương trình thực nghiệm nhận dạng dấu vân tay. Nội

dung chính của đề tài được nghiên cứu tìm hiểu qua 3 chương:

Chương 1:Tổng quan về Sinh trắc học và bài toán nhận dạng vân tay.

Chương 2: Cơ sở khoa học của bài toán nhận dạng vân tay

Chương 3: Xây dựng hệ thống nhận dạng vân tay

Được sự giúp đỡ của thầy Vũ Vinh Quang, tôi đã được nhận và thực hiện

đề tài “ Công nghệ sinh trắc học và bài toán nhận dạng vân tay”. Do kiến

thức còn nhiều hạn chế nên không tránh khỏi sai sót. Đề tài này mới chỉ tập

trung vào tìm hiểu CNSTH và tìm hiểu nghiên cứu nhận dạng DVT qua các

thuật toán, còn nhiều vấn đề cần giải quyết để hoàn thiện đề tài này. Tôi xin

chân thành cảm ơn thầy Vũ Vinh Quang đã hướng dẫn thực hiện đề tài và tôi

cũng mong muốn nhận được những ý kiến đóng góp của các thầy cô, bạn bè

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

và đồng nghiệp để đề tài này hoàn chỉnh hơn nữa.

Chương 1

TỔNG QUAN VỀ SINH TRẮC HỌC VÀ BÀI TOÁN

NHẬN DẠNG VÂN TAY

Nội dung chính của chương 1 trình bày các khái niệm về sinh trắc học

và tổng quan về bài toán NDVT, mô hình của bài toán nhận dạng và các kĩ

thuật cơ bản của mô hình. Các kiến thức cơ bản được tham khảo trong các tài

liệu [2-11].

1.1. Tổng quan về Sinh trắc học và Bài toán nhận dạng vân tay

CNSTH là công nghệ sử dụng những thuộc tính vật lý, đặc điểm sinh

học riêng của mỗi cá nhân như vân tay, mống mắt, khuôn mặt ... để nhận diện.

Đây được coi là công cụ xác thực nhân thân hữu hiệu nhất mà người ta sử

dụng phổ biến vẫn là NDVT bởi đặc tính ổn định và độc nhất của nó. Cho đến

nay NDVT vẫn được xem là một trong những phương pháp sinh trắc tin cậy

nhất. Mỗi người có một đặc điểm sinh học duy nhất. Dữ liệu sinh học của

từng cá nhân với đặc điểm khuôn mặt, ảnh chụp võng mạc, giọng nói sẽ được

kết hợp với nhau bằng phần mềm để tạo ra mật khẩu dành cho những giao

dịch điện tử, phương thức đó là “công nghệ sinh trắc đa nhân tố”. Sự phát

triển của công nghệ đã thay đổi từ việc lăn tay trên mực và lưu trữ trên giấy

sang quét trên máy và lưu trữ kỹ thuật số.

Việc sử dụng DVT và vân chân để nhận dạng đã được người Ấn Độ phát

hiện từ thế kỷ XIV. Trung Quốc Cổ đại, các thương nhân sử dụng dấu ấn của

ngón tay cái trong việc giao dịch. Đến thế kỷ XVI khoa học kỹ thuật hiện đại

phát triển, vân tay được các nhà khoa học trên toàn thế giới nghiên cứu nhiều

hơn và đưa ra các luận thuyết, các chương trình mô tả. Từ đó nhận dạng DVT

mới được phát triển nhanh chóng. Năm 1684, Tiến sĩ Nehemiah Grew (1641-

1712) giới thiệu Finger Prints, Palms and Soles đến Hội Hoàng gia. Năm

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

1788, J.C Mayer đã mô tả chi tiết thông tin giải phẫu của vân tay để đặc tính

hóa, nhận dạng các đặc tính vân tay. Và ông cũng là người đầu tiên đưa ra

thuyết cơ bản về phân tích vân tay và giả thuyết rằng DVT là duy nhất. Năm

1809, Thomas Bewick bắt đầu sử dụng vân tay của mình như là biểu tượng

đăng kí thương mại – đã tạo ra một cột mốc quan trọng trong nghiên cứu khoa

học về NDVT. Năm 1823, Tiến sĩ Jan Purkinje phân loại những chủng trên

các vân tay thành 9 loại: arch, tented arch, ulna loop, radial loop, peacock’s

eye/compound, spiral whorl, elliptical whorl, circular whorl, and double

loop/composite. Năm 1880, Henry Faulds đưa ra lý luận về số lượng vân tay

RC (Ridge Count) để đánh giá mức độ phụ thuộc của vân tay vào gen di

truyền. Năm 1868 nhà bác học Roberts chỉ ra rằng mỗi ngón tay có một môi

trường phát triển vi mô khác nhau. Năm 1968 nhà bác học Holt đã chứng

minh được rằng có thể dự đoán tương đối chính xác tổng số lượng vân tay

TRC (Total Ridge Count) và mức độ phụ thuộc của chúng vào gen di truyền

của mỗi người. Vào thế kỉ XIX, Richard Edward Henry của Scotland Yard

(cơ quan an ninh của Anh) đã phát triển phương pháp phân loại và nhận dạng

DVT. Phương pháp này được Francis Galton (1822 - 1911) cải tiến vào năm

1892, ông là người đầu tiên phát hiện vai trò của vân tay trong lĩnh vực di

Hình 1.1: Vân tay trên đèn của người Palettin (400 A. D)

Hình 1.2: Con dấu thương mại của Berwick (1809)

truyền và sự khác biệt vân tay ở những chủng tộc khác nhau.

Ông đã đơn giản hoá việc phân loại vân tay và chia vân tay thành 3 loại

lớn: Vân sóng (không có tam giác điểm), vân móc (có 1 tam giác điểm), vân

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

xoáy (có 2 tam giác điểm).

Năm 1926 Tiến sĩ Harold Cummins được xem là cha đẻ của ngành

nghiên cứu khoa học DVT đưa ra lí luận chỉ số cường độ vân tay PI (Pattern

Intensity). Giá trị RC (Ridge Count), số lượng tam giác điểm, hình dạng vân

tay, vị trí hình dạng vân tay ở những ngón tay khác nhau có liên quan đến

tiềm năng và trí tuệ của con người. Ông nghiên cứu ra rằng DVT được hình

thành đồng thời với sự hoàn thiện các cấu trúc của não bộ. DVT được khởi

tạo ở thai nhi vào giai đọan từ 13 đến 19 tuần tuổi. Vào giai đoạn trước đó,

thai nhi không có DVT đồng thời não bộ cũng chỉ trong giai đoạn hình thành.

Khi thai nhi được 19 tuần tuổi cũng là lúc các vùng chính của não hình thành

bao gồm cả vỏ đại não.

Việc sử dụng DVT để nhận dạng được áp dụng rộng rãi trong đời sống

của các nước công nghiệp phát triển. DVT không những được sử dụng trong

lĩnh vực hình sự mà còn được sử dụng trong việc xác nhận nhân thân của cá

nhân khi truy cập mạng hoặc mở khoá. Một số ngân hàng đã bắt đầu thanh

toán thẻ ATM sử dụng máy đọc vân tay. Trong y học, dựa trên những bức

Hình 1.3: Chữ kí bằng vân tay của người

Trung Quốc khi mua bán (1839)

tranh vân tay đặc trưng, người ta phát hiện ra những bệnh do sai lệch gen.

Đầu thế kỉ 20, cấu trúc của vân tay mới được mô tả một cách khá đầy đủ.

Các nguyên lý sinh học của vân tay được tổng kết như sau:

- Biểu bì vân có các đặc tính khác nhau trên các vân tay khác nhau

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

(nguyên lý này là cơ sở cho NDVT);

- Cấu hình vân tay có sự thay đổi trên từng cá nhân, nhưng sự thay đổi

nhỏ này vẫn cho phép phân loại một cách có hệ thống các vân tay (nguyên lý

này là cơ sở để tiến hành phân loại vân tay);

- Các chi tiết và cấu hình của mỗi đường vân là ổn định và không thay đổi.

Cũng từ đầu thế kỉ 20, NDVT chính thức được chấp nhận như một

phương pháp nhận dạng cá nhân có giá trị và trở thành chuẩn trong pháp luật.

Ví dụ, năm 1924 FBI đã thiết lập một cơ sở dữ liệu có 810.000 thẻ vân tay.

1.2. Tình hình ứng dụng nhận dạng vân tay tại Việt Nam

Hơn 100 năm qua so sánh DVT vốn được coi là một phương tiện hữu

hiệu hỗ trợ cho các nhà điều tra trong quá trình phá án và xét xử. Người ta có

thể tìm ra tung tích tội phạm cũng như nạn nhân thông qua DVT ở trên hiện

trường. Tuy nhiên phương pháp này vẫn bộc lộ một vài khuyết điểm do tác

động của các yếu tố khách quan như môi trường thời tiết, hiện trường sau khi

khảo sát,…và các yếu tố chủ quan gây nhiễu. Nếu chỉ đơn thuần dựa vào yếu

tố kỹ thuật mà bỏ qua một loạt các biện pháp nghiệp vụ khác, sai số này có

thể lên tới 10%. Mặc dù vậy, phương pháp NDVT hiện vẫn còn phổ biến ở

nhiều nơi và nhiều quốc gia, tuy nhiên phương pháp NDVT vẫn được sử dụng

trong việc điều tra phá án của cơ quan Công an vì thế việc nâng cao sự chính

xác khi NDVT là một vấn để thiết yếu. Ngày nay, người ta cũng lợi dụng các

đặc điểm riêng biệt của vân tay để xây dựng các hệ thống bảo mật các thông

tin riêng tư cho người sở hữu chúng, từ việc dùng các ổ khóa vân tay thay thế

cho các ổ khóa thông thường cho đến việc dùng vân tay thay thế mật khẩu đã

quá phổ biến trong thời đại công nghệ thông tin. Người ta chỉ cần quét DVT

của mình qua các thiết bị chức năng là có thể mở được một cánh cửa, đăng

nhập vào hệ thống máy vi tính, qua một phòng bí mật hay các trạm bảo vệ bí

mật. Đó là giải pháp an ninh tuyệt đối cho những yêu cầu bảo mật của con

người trong nhiều lĩnh vực như: Kiểm soát an ninh trong các cơ quan của Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Chính phủ, trong quân đội, ngân hàng, trung tâm lưu trữ dữ liệu... hoặc để

kiểm soát ra vào của nhân viên tại các trung tâm thương mại, các tập đoàn,

các đại sứ quán,... Trong lĩnh vực quản lý nhân sự, phương pháp NDVT còn

hỗ trợ đắc lực cho việc quản lý và chấm công tại các nhà máy, xí nghiệp, công

ty bằng máy các máy chấm công vân tay. Tuy nhiên, phổ biến nhất có lẽ là

DVT của chúng ta qua mặt sau của chứng minh thư để xác định một cách

nhanh nhất các đặc điểm, hồ sơ của một công dân đã được lưu trong cơ sở dữ

liệu. Trên thế giới hiện nay đã xuất hiện nhiều sản phẩm công nghệ cao sử

dụng phương pháp NDVT như khóa vân tay, máy chấm công vân tay, máy

tính xách tay,... Tuy nhiên đây vẫn là vấn đề còn chưa được nghiên cứu nhiều

ở Việt Nam. Ở nước ta, phương pháp này mới chỉ phổ biến ở việc quản lý

nhân sự thông qua chứng minh thư nhân dân và phục vụ điều tra phá án. Các

sản phẩm công nghệ cao nói trên chúng ta vẫn phải nhập khẩu với giá thành

khá cao, do đó chúng vẫn chưa được phổ biến rộng rãi.

1.3. Mô hình bài toán nhận dạng vân tay

Hiện nay, khi khoa học vân tay ngày càng phát triển với nhu cầu bảo mật

và nhận dạng cá nhân thì nhiều hệ thống tự động nhận dạng ảnh DVT đã được

quan tâm nghiên cứu rộng rãi và ứng dụng trợ giúp con người trong việc phân

tích DVT. Với những tiến bộ về tính toán và công nghệ, nhất là sự phát triển

nhanh chóng của máy tính điện tử, nhiều hệ AFIS đã được công bố hoàn thiện

và đưa vào sử dụng.

1.3.1. Mô hình hệ thống FINDER

Trong số các mô hình được công bố, mô hình hệ thống nhận dạng DVT

tự động do cục điều tra liên bang Mỹ FBI đưa ra vào những năm 70 là một

mô hình khá hoàn chỉnh có tên là hệ thống FINDER. Nó có hiệu quả hơn hẳn

các hệ thống xử lý DVT kiểu quang học, hoặc theo kiểu ngôn ngữ cú pháp

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trước đó.

Hình 1.4: Sơ đồ khối một hệ AFIS

Hình 1.4: Mô hình hệ thống FINDER

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

1.3.2 Mô hình hệ thống AFIS (Automated Fingerprint Identification

System)

Sơ đồ khối của hệ AFIS được mô tả ở hình 1.4:

Mô tả quá trình của hệ thống:

+ Thu nhận ảnh:

Ảnh vân tay thu nhận online hay offline được đưa vào máy tính nhờ

scanner có độ phân giải cao.

+ Tiền xử lý: Ảnh vân tay được nâng cấp và khôi phục nhằm khắc phục

sự xuống cấp của ảnh sau khi thu nhận như các đường vân bị đứt đoạn hay

dính chập vào nhau, ảnh bị mờ… do mực hay nhiều nguyên nhân khác.

+ Trích điểm đặc trưng:

Đây là giai đoạn rất quan trọng trong quá trình xử lý. Khi xây dựng cơ sở

dữ liệu vân tay, khối này trích ra các điểm đặc trưng của ảnh vân tay, mã hóa

chúng và lưu trữ vào cơ sở dữ liệu để phục vụ cho các giai đoạn xử lý sau

này, còn trong quá trình nhận dạng một vân tay cho trước, các đặc điểm trích

chọn được phục vụ cho việc phân loại và đối sánh.

+ Phân loại:

Các ảnh vân tay được phân loại nhằm tăng tốc độ tìm kiếm trong cơ sở

dữ liệu vân tay trong quá trình nhận dạng.

+ Tìm kiếm:

Thông tin về loại của ảnh vân tay được sử dụng để thu hẹp phạm vi tìm

kiếm trong cơ sở dữ liệu.

+ Đối sánh, kiểm tra:

Tiến hành trên các ảnh vân tay đã được phân loại.

Đây là giai đoạn quyết định xem hai ảnh vân tay có hoàn toàn giống nhau

hay không và đưa ra kết quả nhận dạng, tức là ảnh vân tay cần nhận dạng tương

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

ứng với vân tay của cá thể nào đã được lưu trữ trong cơ sở dữ liệu.

Hiện nay có nhiều kỹ thuật đối sánh vân tay, nhưng một cách tổng quát

có thể chia thành hai loại chính:

+ Kỹ thuật dựa trên các điểm đặc trưng: dựa trên các điểm đặc trưng cục

bộ (điểm cuối và điểm rẽ nhánh) của 2 ảnh vân tay để đối sánh.

+ Kỹ thuật dựa trên sự tương quan: là kỹ thuật đối sánh dựa trên cấu trúc

tổng thể của đường vân và rãnh của hai ảnh vân tay.

Ngoài ra có thể sử dụng phương pháp đối sánh khác, ví dụ như đối sánh

bằng bộ lọc băng, đối sánh Hybrid.

1.4. Thu nhận và lưu trữ ảnh vân tay

1.4.1. Thu nhận ảnh vân tay

Tùy thuộc vào quá trình xử lý người ta chia làm hai loại thu nhận ảnh

vân tay đó là trực tiếp và gián tiếp.

 Một ảnh gián tiếp: là ảnh thu được từ các vết mực được thấm trên các

đầu ngón tay, sau đó lăn hoặc dán lên tờ giấy trắng, ảnh vân tay được thu số

hóa bằng các thiết bị quét ảnh như các thiết bị quét ảnh quang học hay các

Camera chất lượng cao. Trong phương pháp này người ta dùng các kiểu như:

+ Phương pháp lăn: Đầu tiên cho vân tay của người cần lấy mẫu, thấm

mực, rồi lăn nhẹ trên tờ giấy trắng để thu được các vết mực, chờ khi mực khô,

sau đó dùng một thiết bị máy ảnh hay Camera để sao chụp bức ảnh này.

Phương pháp này được sử dụng lâu đời nhất, khoảng 100 năm, diện tích ảnh

vân tay thu nhận được rộng vì quá trình lăn, thu được nhiều thông tin trên

ảnh, tuy nhiên chất lượng các ảnh vân tay đôi khi không tốt và ảnh thường bị

sai lệch do tác dụng khi lăn ngón tay.

+ Phương pháp ấn: Trong phương pháp này người ta cho các ngón tay

thấm mực rồi sau đó ấn nhẹ trên giấy mà không lăn, chờ cho mực khô rồi

sao chụp ảnh vân tay bằng máy ảnh hoặc Camera. Rõ ràng phương pháp

này diện tích vùng ảnh nhỏ hơn, thông tin ảnh cũng ít hơn, nhưng độ chính

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

xác cao hơn.

+ Phương pháp ảnh vân tay ảo: Đây là một loại đặc biệt của phương

pháp thu nhận ảnh vân tay gián tiếp. Các ảnh này thường được thu nhận tại

hiện trường. Tại đó khi các đầu ngón tay ấn nhẹ trên các vật dụng ở hiện

trường thì mồ hôi, hoặc chất nhờn do các tuyến bài tiết trên biểu bì da sẽ in

DVT tại hiện trường. Lúc này người ta sử dụng một loại hóa chất đặc biệt phủ

lên vết vân tay đó, làm cho hình ảnh vết vân tay hiện lên, và sử dụng các thiết

bị như Camera hay máy ảnh để thu nhận các ảnh này.

 Một ảnh trực tiếp: Là quá trình thu nhận ảnh vân tay trực tiếp thông

qua các thiết bị cảm nhận mà không cần thông qua các bước trung gian là in

Hình 1.5: Các ảnh vân tay thu được

ảnh vân tay trên giấy.

Đối với quá trình thu nhận ảnh vân tay sống người ta thường dùng cách

đặt các ngón tay trực tiếp vào thiết bị cảm ứng để thu nhận ảnh. Công nghệ

phổ biến nhất để thu nhận các mẫu ảnh vân tay sống là dựa trên sự phản xạ

ánh sáng từ DVT, khi đặt ngón tay và cạnh một tấm gương, các đường vân

của ảnh vân tay sẽ tiếp xúc với tấm gương, trong khi các rãnh đường vân thì

không tiếp xúc, bên cạnh tấm gương người ta đặt một hệ thống các bóng đèn

để phát ra ánh sáng Laser chiếu đến mặt dưới của tấm gương, ánh sáng sẽ

phản xạ trở lại và người ta dùng một Camera để thu các ánh sáng phản xạ đó.

Kết quả thu được là một ảnh vân tay trong Camera.

Các ảnh vân tay, dù trực tiếp hay gián tiếp trong quá trình nhận thì có

một số lượng đáng kể (khoảng 10%) có chất lượng kém như bị vết mờ, nhòe

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

hoặc đứt nét do lăn mực và do nhiều nguyên nhân khác.

1.4.2. Lưu trữ ảnh và các thông tin đặc trưng của vân tay

Lưu trữ ảnh vân tay trong cơ sở dữ liệu là một vấn đề hết sức quan

trọng, có ảnh hưởng sống còn đến hiệu năng tìm kiếm trong các hệ NDVT

cỡ lớn. Đối với các ảnh vân tay, các thông tin đặc trưng cần được lưu trữ

gồm: Véc tơ đặc trưng hướng, tập hợp các điểm đơn, véc tơ mã vân tay

(FingerCode), nhãn các lớp và tập điểm đặc trưng cục bộ. Ngoài ra hệ

thống còn phải lưu trữ các thông tin cá nhân liên quan đến vân tay như:

Tên, tuổi, nơi sinh, màu tóc, thân nhân.

Để lưu trữ các thông tin khác nhau này một cách có hiệu quả và ít tốn

kém, thông thường sử dụng giải pháp đa lưu trữ, nghĩa là phân nhóm thông

tin có cấu trúc hoàn toàn khác nha theo những phương pháp khác nhau, cụ thể

là thông tin về vân tay được chia thành 4 nhóm: Nhóm dữ liệu bình thường có

thể lưu dạng bảng, nhóm dữ liệu dạng véc tơ được lưu trữ tuần tự, nhóm dữ

liệu dạng véc tơ cần lưu trữ bằng cây tìm kiếm và dữ liệu ảnh.

- Nhóm dữ liệu thông thường có thể lưu trữ dạng bảng chính là các thông

tin cá nhân như: Tên, tuổi, nơi sinh, địa chỉ …

- Nhóm dữ liệu véc tơ cần lưu trữ dưới dạng cây tìm kiếm là các véc tơ

đặc trưng tổng thể được dùng ở mức tìm kiếm lọc vân tay trước khi đối sánh

1:1. Quá trình tìm kiếm này dựa trên cơ chế tìm láng giềng gần nên dữ liệu

cần được tổ chức dưới dạng R-tree.

- Nhóm dữ liệu véc tơ được lưu trữ tuần tự các véc tơ đặc trưng cục bộ.

Các véc tơ này được lưu trữ tuần tự là do tại mức đối sánh trên véc tơ đặc

trưng cục bộ, mọi thao tác phải diễn ra tuần tự, tức là tập trung đặc trưng đầu

vào phải lần lượt đối sánh hết với tất cả các tập trung đặc trưng trên bộ nhớ

ngoài. Đường dẫn cụ thể của véc tơ đặc trưng tương ứng với một vân tay

được lưu trong một bảng.

- Riêng đối với nhóm dữ liệu ảnh, tuy chúng không tham gia vào quá

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trình tìm kiếm vân tay, nhưng chúng có thể được sử dụng cho những mục

đích kiểm tra lại hoặc trích chọn lại đặc trưng khi cần. Do vậy, ảnh vân tay

được lưu dạng tệp trên bộ nhớ ngoài và đường dẫn của chúng được lưu vào

một bảng, giống các véc tơ đặc trưng cục bộ.

1.5. Tiền xử lý ảnh vân tay

Sau quá trình thu nhận, hiển thị là giai đoạn tiền xử lý ảnh. Như đã trình

bày, ảnh sau khi thu nhận thường bị giảm cấp do bị lỗi của các thiết bị thu

nhận, hay dấu vết vân tay để lại có chất lượng kém, bị mờ, nhòe … Trong giai

đoạn này việc nâng cấp ảnh có ý nghĩa to lớn. Nó có tác dụng cải thiện độ

tương phản và làm nổi lên những thuộc tính, những đặc điểm cần thiết cho

quá trình nhận dạng như lằn vân (ridge), thung lũng, các điểm cuối, điểm rẽ

nhánh, hướng đường vân … Đồng thời nếu hệ thống xử lý DVT dựa trên cơ

sở hướng tiếp cận cấu trúc thì việc chuyển đổi ảnh đa mức xám thành ảnh nhị

phân và làm mảnh được thực hiện vào cuối giai đoạn này.

Sau khi nâng cấp ảnh DVT có thể loại bỏ được những chỗ bị mờ, tuy

nhiên nó vẫn có thể còn các khuyết tật như đường vân bị đứt đoạn, đường vân

dính chập vào nhau chẳng hạn khi lăn mực bị nhòe, bị thiếu mực,… Quá trình

khôi phục ảnh nhằm phục hồi cấu trúc các khuyết tật thông thường như đứt

nét, dính nét, loại trừ những cấu trúc lằn vân phức tạp do nhiễu sinh ra.

Như chúng ta đã biết, việc đối sánh ảnh vân tay tự động phụ thuộc vào

việc đối sánh các điểm đặc trưng và mối liên hệ giữa chúng để nhận dạng cá

nhân. Một bước quan trọng trong việc đối sánh ảnh vân tay và rút trích các

điểm đặc trưng tự động và chính xác từ các ảnh đầu vào, đây là một công việc

rất khó khăn. Việc tiến hành thuật toán trích chọn các điểm đặc trưng phụ thuộc

vào chất lượng các ảnh vân tay đầu vào. Nếu ảnh đầu vào chất lượng tốt, cấu

trúc ảnh đường vân rõ ràng và ít bị nhiễu thì quá trình phân loại và trích chọn

đặc điểm sẽ diễn ra nhanh chóng và chính xác, nhưng ngược lại nếu ảnh đầu

vào chất lượng kém thì quá trình phân loại và trích chọn đặc điểm sẽ gặp khó

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

khăn và kết quả đầu ra sẽ kém chính xác, gây trở ngại khi cần tìm kiếm, đối

sánh và nhận dạng sau này. Thực tế theo điều tra thì tỷ lệ đáng kể khoảng 10%

các ảnh vân tay thu được là có chất lượng xấu. Vì vậy khâu xử lý nâng cao chất

lượng ảnh là rất quan trọng và phải được thực hiện tốt.

Hiện nay, tiền xử lý ảnh vân tay vẫn đang được các nhà khoa học quan

tâm và tiếp tục nghiên cứu. Đã có rất nhiều cách giải quyết và nhiều thuật

toán khác nhau được đưa ra. Trong tài liệu này ta chỉ tiếp cận vấn đề tiền xử

lý một cách sơ bộ, cụ thể là cài đặt thủ tục cải thiện ảnh dựa vào kỹ thuật kéo

giãn lược đồ mức xám và thủ tục tự động nâng cấp, nhị phân hóa tự động bảo

toàn những đặc điểm cơ bản nhằm phục vụ tốt cho các giai đoạn trích chọn

đặc trưng và phân loại sau này.

1.6. Các đặc trưng của vân tay và vấn đề trích chọn đặc trưng

Những kết quả nghiên cứu của giải phẫu học cho biết chỉ những phần

không có lông của cơ thể như lòng bàn tay và gan bàn chân được bao phủ bởi

các mẫu vân được hình thành từ những lằn nổi tạo ma sát. Các vân này rất

quan trọng vì chúng được hình thành từ trong bào thai 4 tháng và không thay

đổi cho đến khi chết.

Các mẫu vân không được cấu tạo từ mặt ngoài da mà được xác định bởi

nhiều phần tử khác nhau bên dưới (chẳng hạn các tuyến mồ hôi, dây thần

kinh, mạch máu...) Các vết cắt sâu có thể nằm chèn lên mẫu vân nhưng phần

còn lại của mẫu vân không thay đổi. Tóm lại DVT có hai đặc điểm cơ bản:

 Vân tay là do các gai da đội lớp biểu bì lên mà tạo thành. Đó là nơi

tập kết miệng các tuyến mồ hôi, tuyến bã nhờn ... Nó đã định hình khi con

người là cái thai 4 tháng trong bụng mẹ. Khi đứa bé chào đời, lớn lên, vân tay

được phóng đại nhưng vẫn giữ nguyên hình dạng cho đến khi về già. Nếu tay

bị bỏng, bị thương, bị bệnh thì khi lành, vân tay lại tái lập như cũ. Chỉ khi có

tổn thương sâu, hủy hoại hoàn toàn, sẹo chằng chịt mới xóa mất DVT. Vân

tay không thay đổi từ khi con người ra đời đến khi chết. Đó là tính bất biến

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

theo thời gian của DVT.

 Vân tay mỗi người khác nhau, nó là duy nhất (và cả đối với mỗi ngón

tay). Tính chất này đã được thừa nhận qua việc kiểm tra hàng triệu mẫu vân

tay. Trong trường hợp vân tay của các cặp sinh đôi, mặc dù phần lớn là có

quan hệ giống nhau. Chẳng hạn, nếu vân tay của một người là dạng hình vòm,

thì vân tay của người kia cũng là dạng hình vòm, nhưng các đặc trưng cục bộ

như điểm cuối, điểm rẽ nhánh sẽ khác nhau. Xác suất trùng lặp một vân tay là 10-6. Một người với hai bàn tay có mười ngón đầy đủ thì xác suất trùng lặp cả

hai mươi ngón trở nên rất nhỏ đến lúc có thể coi bằng không. Do đó, không

có hai người khác nhau có các DVT trùng nhau. Không có hai người nào có

tất cả mười vân tay giống hệt nhau. Đó là tính cá thể của DVT.

Đối với bất kỳ một hệ thống xử lý ảnh nào, quá trình trích chọn đặc tính

luôn có vai trò quan trọng. Đối với ảnh vân DVT, đây là một loại ảnh có

những tính chất đặc thù riêng của nó nên công việc trích chọn đòi hỏi những

kiến thức chuyên môn nhất định về vân tay. Dựa vào những đặc trưng vật lý

của vân tay, hệ thống tin học có nhiệm vụ tìm ra các đặc trưng riêng nhờ đó

có thể phân loại và xác định chính xác từng DVT, đồng thời phải biểu diễn

chúng một cách hợp lý dưới dang các thông tin để máy tính có thể hiểu và xử

lý một cách nhanh chóng.

Ảnh vân tay thuộc lớp ảnh có cấu trúc, đường nét nên có những đặc

trưng về hướng, độ cong, điểm kết thúc, điểm rẽ nhánh …

Các đặc trưng của ảnh vân tay được chia thành hai loại: Đặc trưng cục

bộ và đặc trưng tổng thế.

 Đặc trưng tổng thể: Đây là loại đặc trưng biểu diễn cấu trúc chung

của toàn bộ ảnh vân tay. Có rất nhiều loại đặc trưng tổng thể phong phú, ví dụ

Hình 1.6: Các điểm đơn

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

như : Đặc trưng hướng, các điểm đơn, mã vân tay …

Các điểm đơn được định nghĩa như là nơi mà độ cong đường vân đạt giá

trị cực đại, hướng của đường vân thay đổi với tốc độ nhanh, bao gồm: điểm

Core và điểm Delta:

- Điểm Core: Là điểm trung tâm của ảnh vân tay. Nó là điểm hội tụ của

các đường vân, nó giúp trong việc định hướng ảnh vân tay.

- Điểm Delta: Là trung tâm của tam giác nơi 3 đường vân gặp nhau.

Điểm đơn thường được sử dụng trong việc tách lớp các ảnh vân tay,

cũng như tiến hành loại sơ bộ quá trình tìm kiếm vân tay.

Đối với các đặc trưng tổng thể có nhiều phương pháp để trích chọn. Trên

thực tế, mỗi kỹ thuật khác nhau có những ưu điểm khác nhau và thích hợp

cho từng loại ảnh ở đầu vào. Thông thường với các đặc trưng hướng người ta

xử dụng kỹ thuật tính Gradient rồi lấy trung bình đạo hàm trong một số lân

cận. Đối với các điểm đơn,kỹ thuật trích chọn là tìm kiếm điểm không liên tục

trong đặc trưng hướng bằng cách đánh giá chỉ số Pointcare. Đối với mã vân

tay thì thường sử dụng bộ lọc Gabor.

 Đặc trưng cục bộ: Là các điểm đặc biệt trên đường vân của ảnh vân

tay. Nó chỉ đại diện cho đường vân trong lân cận cục bộ với nó mà thôi.

Chính vì vậy, tập hợp các điểm đặc trưng cục bộ, tức là mỗi tập các đặc trưng

cục bộ chỉ xuất hiện trong một vân tay duy nhất. Có nhiều kiểu điểm đặc

trưng cục bộ, nhưng có thể biểu diễn thành hai loại: Điểm kết thúc đường vân

Hình 1.7a: Các điểm đặc trưng cục bộ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

(Ridge Ending), điểm rẽ nhánh (Ridge Bifurcation).

Hình 1.7b: Các điểm đặc trưng cục bộ

Người ta dựa vào các đặc điểm đặc trưng cục bộ này để đối sánh trong

hệ thống NDVT. Hiện nay trên thế giới đang có hai hướng giải quyết bài toán

trích chọn đặc trưng của vân tay:

+ Hướng thứ nhất là tiếp tục phát triển và cải tiển phương pháp cấu

trúc. Phương pháp cấu trúc dựa trên quan điểm ảnh vân tay thuộc vào loại ảnh

đường nét, do đó dựa vào thông tin cấu trúc và đặc điểm hình học của đường

vân (như tính liên tục của đường vân hoặc tính song song của chúng…) có thể

trích ra những đặc tính của nó. Theo phương pháp này trước khi trích chọn

đặc điểm, ảnh vân tay được chuyển về dạng nhị phân và làm mảnh để làm nổi

tính chất đường nét của vân tay. Từ ảnh nhị phân đã được làm mảnh, có thể

trích chọn các điểm kết thúc và các điểm rẽ nhánh theo các đặc điểm hình học

của chúng một cách dễ dàng. Phương pháp này có ưu điểm là nhanh, cho kết

quả chính xác nếu trong ảnh nhị phân, thông tin về các điểm đặc trưng không

bị suy giảm nhiều.

Khó khăn chính của cách tiếp cận cấu trúc là chất lượng ảnh vân tay

thường quá thấp, khi quá trình nhị phân hóa được áp dụng cho ảnh nhiễu và

có độ tương phản thấp sẽ đem lại những kết quả không như mong muốn.

+ Một hướng nghiên cứu khác mới xuất hiện là trích chọn thông tin

trực tiếp từ ảnh đa mức xám. Tư tưởng của phương pháp này là xác định ra

các ridge points. Đây là các cực đại địa phương dọc theo hướng của một trong

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

những chỗ uốn cong chính của lằn vân là 0. Đường vân được coi như một

chuỗi tuần tự các điểm, và do vậy có thể xây dựng lại được đường vân từ các

điểm này dựa vào các thuật toán khôi phục.

Trong luận văn, để thực hiện công việc trích chọn, hướng tiếp cận

nghiên cứu phương pháp truyền thống là phương pháp cấu trúc. Phương pháp

này đã được nghiên cứu trong thời gian dài và đã có những thuật toán và kết

quả ổn định được công bố.

1.7. Vấn đề đối sánh ảnh

Đối sánh vân tay là công việc cuối cùng của quá trình NDVT, nó trả lời

câu hỏi “Vân tay này là của ai trong số những người đó”. Bài toán NDVT

(tìm kiếm một vân tay đầu vào trong một cơ sở dữ liệu có N vân tay) có thể

được thực hiện như là thực hiện tuần tự đối sánh một - một giữa các cặp vân

tay. Sự phân loại vân tay và các kĩ thuật đánh chỉ số thường được sử dụng để

tăng tốc độ tìm kiếm trong các bài toán NDVT. Một lượng lớn các thuật toán

đối sánh vân tự động đã được đề nghị trong các tài liệu nhận dạng mẫu. Hầu

hết các thuật toán này không gặp khó khăn trong đối sánh các ảnh vân tay

chất lượng tốt. Nhưng trong đối sánh vân tay tồn tại thách thức ở các ảnh chất

lượng thấp và vấn đề đối sánh từng vùng vân tay. Trong trường hợp hệ thống

trợ giúp con người AFIS, một thuật toán kiểm tra chất lượng được sử dụng để

chỉ lấy và chèn vào cơ sở dữ liệu các ảnh vân tay tốt. Hơn nữa, quá trình xử lý

các mẫu vân khó có thể được quản lý. Dù sao, sự can thiệp là không thể trong

các hệ thống nhận dạng trực tuyến tự động - những hệ thống này đang có nhu

cầu ngày càng tăng trong các ứng dụng thương mại. Các phương pháp đối

sánh vân tay có thể được phân loại thành ba loại:

+ Đối sánh dựa độ tương quan: Hai ảnh vân tay được đặt chồng lên và

độ tương quan giữa các điểm ảnh tương ứng được tính với sự canh chỉnh khác

nhau (ví dụ với các vị trí và độ quay khác nhau).

+ Đối sánh dựa vào điểm đặc trưng: Đây là kĩ thuật phổ biến nhất và

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

được sử dụng rộng rãi nhất, do các chuyên gia pháp lý so sánh các vân tay

và chấp nhận phương pháp như là bằng chứng định danh trong các phiên tòa

ở hầu hết các quốc gia. Điểm đặc trưng được trích chọn từ hai vân tay được

lưu giữ như là tập các điểm trong một bề mặt hai chiều. Đối sánh dựa vào

điểm đặc trưng cơ bản bao gồm tìm kiếm sự căn chỉnh giữa tập điểm đặc

trưng mẫu và tập điểm đặc trưng đầu vào dẫn tới sự so khớp lớn nhất các cặp

điểm đặc trưng.

+ Đối sánh dựa đặc tính vân: Trong các ảnh vân tay chất lượng thấp,

việc trích chọn chi tiết rất khó khăn. Khi các đặc trưng khác của mẫu vân tay

(ví dụ: hướng và tần suất cục bộ, hình dạng vân, thông tin kết cấu) có thể

được trích chọn một cách tin cậy hơn chi tiết, sự khác biệt của chúng là không

cao. Các phương pháp thuộc họ này so sánh các vân tay với các đặc trưng

được trích chọn từ các mẫu vân. Về nguyên lý, đối sánh dựa độ tương quan và

đối sánh dựa vào chi tiết có thể xem như là một phần của đối sánh dựa đặc

trưng vân, theo cách hiểu mật độ điểm ảnh, vị trí chi tiết là nhưng đặc trưng

của mẫu vân ngón tay Nhiều kĩ thuật khác cũng đã được đề nghị chính thức,

về nguyên lý, có thể được xếp vào các loại trên theo các đặc trưng được sử

dụng, nhưng chúng ta đề cập để phân loại chúng tách biệt trên cơ sở các kĩ

thuật đối sánh. Chúng bao gồm các phương pháp dựa mạng thần kinh và các

cố gắng thực hiện đối sánh vân sử dụng các bộ xử lý song song hoặc với các

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

kiến trúc dành riêng khác.

Chương 2

CƠ SỞ KHOA HỌC CỦA BÀI TOÁN NHẬN DẠNG VÂN TAY

Nội dung của chương này sẽ tìm hiểu cơ sở khoa học của về vấn đề

NDVT đã được nghiên cứu từ trước đến nay, các phương pháp cơ bản từ đó

đưa ra một số nhận xét và so sánh giữa các phương pháp với nhau. Các kiến

thức cơ bản được tham khảo từ các tài liệu [1-11].

2.1. Phương pháp tăng cường ảnh

2.1.1. Đặt vấn đề

Trong một ảnh vân tay, chất lượng của cấu trúc vân tay là một đặc

tính quan trọng, vì vân tay mang thông tin của đặc tính của các đặc trưng,

mà các đặc tính của các đặc trưng này rất cần thiết cho bước rút trích đặc

trưng vân tay. Trong trường hợp lý tưởng, ảnh vân tay có chất lượng tốt,

các vân lồi và vân lõm uốn cong đều với nhau theo cùng một hướng, cho

phép các đặc trưng được rút trích một cách chính xác, tuy nhiên trên thực

tế, ảnh vân tay luôn có chất lượng không được tốt bởi vì các thông tin

nhiễu của ảnh làm sai lệch các đặc trưng, dẫn đến làm ảnh hưởng quá trình

rút trích đặc trưng. Như vậy, mục đích của bước tăng cường ảnh là làm

giảm các thông tin nhiễu, làm rõ các cấu trúc vân tay, và đánh dấu các

vùng có thể khôi phục hay không có thể khôi phục.

2.1.2. Tăng cường ảnh bằng phương pháp lọc Gabor

Phương pháp lọc Gabor là một trong những phương pháp Tăng cường

ảnh vân tay phổ biến nhất hiện nay. Phương pháp này dựa vào bộ lọc Gabor

mà bộ lọc này là sự hòa hợp của hướng vân và tần số vân cục bộ. Các bước

chính của phương pháp này bao gồm: Chuẩn hóa ảnh (normalization), ước

lượng hướng ảnh (orientation image estimation), Ước lượng tần số ảnh

(frequency image estimation), Tạo các vùng mặt nạ (region mask generation)

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

và lọc Gabor (filtering), (Hình 2.1).

 Chuẩn hóa ảnh

Mục đích của bước này là làm giảm độ khác biệt các giá trị mức xám

giữa các vân tay với nhau nhằm tạo thuận lợi cho các bước xử lý tiếp theo.

Nguyên nhân của sự khác biệt giá trị mức xám này là do quá trình lấy DVT từ

thiết bị đã tạo nên sự không đồng đều màu, chỗ màu nhạt màu đậm. Đặc biệt,

ảnh vân tay sau khi được chuẩn hóa, các vân tay sẽ được làm rõ hơn mà

Hình 2.1: Các bước lọc Gabor

Hình 2.2: Minh họa kết quả chuẩn hóa ảnh; (a) ảnh gốc, (b) ảnh đã được chuẩn hóa

(M0 = 100, VAR0 = 100)

không làm thay đổi cấu trúc của vân tay (Hình 2.2).

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Để chuẩn hóa ảnh, ta sử dụng công thức:

Trong đó I(i, j) là giá trị mức xám tại điểm ảnh (i, j), M và VAR tương

ứng là mean và variance của I, Ѱ(i, j) là giá trị mức xám tại điểm (i, j) sau khi

đã được chuẩn hóa, M0 và VAR0 tương ứng là mean và variance mong muốn.

 Ước lượng hướng ảnh

Mục đích của bước này là xác định hướng của các đường vân tay. Đây

được coi là một trong những bước quan trọng nhất trong phần Tăng cường

ảnh vì nếu việc Ước lượng không đúng sẽ dẫn đến việc Ước lượng tần số và

Lọc Gabor sai. Kết quả này làm ảnh xấu sau khi tăng cường không tốt, thậm

chí còn xấu hơn rất nhiều so với ảnh ban đầu; dẫn đến việc rút trích đặc trưng

không đúng.

Các bước chính của Ước lượng hướng ảnh gồm có:

+ Chia Ѱ thành nhiều ô có kích thước w x w (giá trị w đề nghị là 16).

+ Ở mỗi ô, có tâm điểm (i, j), dùng toán tử Sobel để tính gradient

∂x(i, j) và

∂y(i, j) tại mỗi điểm (i, j). Toán tử Sobel ngang được dùng để tính ∂x(i, j).

Toán tử Sobel dọc được dùng để tính ∂y(i, j).

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

+ Ước lượng hướng ở mỗi ô có tâm điểm (i, j) theo các công thức:

Trong đó θ(i, j) là hướng cục bộ của ô có tâm điểm là (i, j).

+ Sử dụng lọc Gaussian làm mượt các trường hướng của ô căn cứ vào

thông tin của các ô lân cận, vì các điểm gây nhiễu, vân bị đứt, hay các đặc

trưng vân tay,... trong ảnh vân tay; làm cho việc xác định hướng cục bộ của ô

không đúng (Hình 2.3a).

làm mượt

Hình 2.3: a, Ước lượng hướng ảnh mà chưa làm mượt; b, Ước lượng hướng ảnh đã được

Ngoài ra tính chất của các ô thay đổi một cách từ từ so với các ô lân

cận của nó, nên một lọc thông thấp được dùng để chỉnh sửa những hướng vân

cục bộ sai. Để thực hiện lọc thông thấp, hướng của các ô được chuyển về các

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trường véc tơ liên tục:

Trong đó Фx (i, j) và Фy (i, j) là các trường véc tơ tương ứng với x và y.

Áp dụng bộ lọc thông thấp lên các trường véc tơ ta có:

Hướng sau khi được làm mượt ở mỗi ô:

Trong đó G là lọc thông thấp Gaussian của kích thước

 Ước lượng tần số ảnh

Mục đích của bước này là xác định tần số của vân tay, nhằm phục vụ

cho bước lọc Gabor. Tần suất vân cục bộ tại điểm (i, j) là nghịch đảo của số

vân trên một đơn vị chiều dài dọc theo đoạn có tâm tại (i, j) và vuông góc với

hướng vân cục bộ, các bước chính của ước lượng tần số ảnh:

+ Ở mỗi tâm điểm (i, j) của ô, tính giá trị trong cửa sổ hướng (oriented

+ Chia G thành các ô có kích thước w x w (16 x 16).

windows) có kích thước 1 x w (32 x 16).

+ Ở mỗi tâm điểm (i, j) của ô, tính x-signature, X[0], X[1], ..., X[n-1],

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

của vân lồi và vân lõm trong phạm vi cửa sổ hướng theo công thức:

Đặt T(i, j) là khoảng cách trung bình của cặp đỉnh liền kề trong x-

Ω(i, j) = 1/T(i, j)

signature. Tần số vân Ω(i, j) được tính theo công thức:

Khi đó ta có thuật toán

B1: Với mỗi ô có tâm (i,j), tính:

Trong đó:

Trong đó giá trị Wg là một nhân Gaussian rời rạc.

B2: Nếu tồn tại ít nhất một ô có giá trị tần số là -1, thì hoán đổi giữa Ω

và Ω’. Sau đó quay lại bước B1.

B3: tính

 Trong đó: Wt là một lọc thông thấp hai chiều và kích thước của bộ lọc

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Wt = 7

Hình 2.4: Cửa sổ hướng và X- signature

 Tạo các vùng mặt nạ

Mục đích của bước này là xác định các vùng điểm của ảnh vân tay đầu

vào nào có khả năng được phục hồi (vùng có khả năng được phục hồi là các

vân được phân biệt rõ ràng với các vân khác hay các vân bị hư hỏng bởi các

đường đứt gãy nhỏ, thâm sẹo... nhưng chúng vẫn có khả năng nhìn được và

các vùng xung quanh cung cấp thông tin đủ để khôi phục cấu trúc ban đầu của

chúng), và vùng điểm nào không thể được phục hồi. Việc phân loại các điểm

ảnh vào vùng có khả năng được phục hồi hay không thể được phục hồi là dựa

vào hình dạng sóng của vân tay cục bộ. Ba tham số sau được dùng là đặc tính

của sóng hình dạng sin của tần số: biên độ (), tần số (), độ khác biệt ().

Đặt X[1], X[2], ... , X[n] là x-signature của ô có tâm (i,j). Giá trị 3 tham số

được tính như sau:

  = (chiều cao trung bình của các đỉnh – bề sâu trung bình của các đáy

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

của sóng hình sin).

  = 1/ T(i,j); trong đó, T(i,j) là số điểm ảnh trung bình giữa 2 đỉnh kề

nhau.

Nếu sự kết hợp của ba đặc tính trên mà lớn hơn một ngưỡng nào đó, thì

ô có tâm (i,j) có khả năng được phục hồi, ngược lại thì không thể được phục

hồi.

 Lọc Gabor

Việc dùng bộ lọc Gabor dựa vào tần số và hướng vân tay sẽ giúp làm rõ

ảnh vân tay một cách hiệu quả. Một bộ lọc đối xứng hai chiều Gabor có dạng

Trong đó  là hướng của bộ lọc, và [x, y] là ảnh của [x, y] sau khi

quay quanh trục Cartesian một góc (90o - ):

Trong biểu thức ở trên, f là tần suất của sóng phẳng hình sin, x , y là độ lệch

Hình 2.5: Biểu diễn đồ họa của bộ lọc Gabor xác định bởi tham số  = 90, f = 1/5, x = y = 3.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

chuẩn Gaussian tương ứng dọc theo trục x và trục y.

Để áp dụng các bộ lọc Gabor tới một ảnh, cần xác định 4 tham số (, f,

x , y). Tần số của bộ lọc hoàn toàn được quyết định bởi tần số vân cục bộ và

hướng của bộ lọc được quyết định bởi hướng vân cục bộ. Việc chọn các giá

trị x và y có thể hoán đổi cho nhau. Nếu chọn giá trị lớn thì bộ lọc sẽ chịu

nhiễm nhiều hơn, nhưng lại tạo ra sự nhầm lẫn giữa vân lồi và vân lõm.

Ngược lại nếu chọn giá trị nhỏ, thì các bộ lọc ít nhầm lẫn giữa vân lồi và vân

lõm: nhưng sau đó, chúng sẽ ít hiệu quả trong việc loại bỏ các nhiễu. Hình 2.6

trình bày ứng dụng Gabor dựa trên lọc ngữ cảnh trên các ảnh chất lượng trung

Hình 2.6: Một biểu diễn đồ họa trong một nhóm 24 bộ lọc Gabor (n0 = 8, n1 = 5) với x =

y =4.

bình và thấp:

Bằng cách giảm giá trị của x tương ứng với y , quá trình lọc tạo ra vài

vân sai và dễ bị nhiễu. Đầu ra của một ảnh chuẩn hóa có thể là một ảnh mức

xám, hay là một ảnh nhị phân; nói chung phụ thuộc vào các tham số được

chọn và các bộ lọc thích hợp.

Như vậy với các đặc điểm nổi trội của phương pháp lọc Gabor, hầu hết

các bước tăng cường ảnh vân tay hiện nay dùng phương pháp này. Do vậy,

phương pháp này cũng thường được cài đặt trên các Hệ thống nhúng.

2.2 Phương pháp rút trích đặc trưng

Ngày nay, đa số các hệ thống NDVT tự động so sánh các vân tay dựa

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trên đối sánh đặc trưng; vì vậy, việc rút trích đặc trưng đúng đắn là một nhiệm

vụ cực kỳ quan trong. Có hai phương pháp chính để tìm các đặc trưng: rút

trích các đặc trưng từ ảnh đã được nhị phân hóa và rút trích các đặc trưng trực

tiếp từ ảnh xám.

Hình 2.7: Các bước rút trích đặc trưng từ ảnh đã được nhị phân hóa

2.2.1. Rút trích các đặc trưng từ ảnh đã được nhị phân hóa

Hình 2.7 Mô tả các bước chính của phương pháp này. Từ ảnh xám ban

đầu, các bộ lọc thích hợp được dùng để phát hiện làm mỏng đường vân về

dạng một điểm ảnh, biến đổi ảnh xám ban đầu thành ảnh nhị phân hóa (có giá

trị là 0 hoặc 1) tương ứng. Cuối cùng, các đặc trưng sẽ được rút trích dựa vào

điểm lân cận xung quanh của nó.

 Bước 1: Nhị phân hóa

Một trong những kỹ thuật dễ dàng nhất là sử dụng ngưỡng toàn cục t và

được thực hiện bằng cách thiết lập các điểm ảnh có mức xám nhỏ hơn t về 0

và các điểm ảnh còn lại về 1. Nhưng các phần khác nhau của ảnh có thể được

đặc tính hóa bởi độ tương phản và cường độ khác nhau; do vậy, một ngưỡng

đơn là không đủ để nhị phân hóa chính xác. Một kỹ thuật khác là dùng

ngưỡng cục bộ t, bằng cách điều chỉnh giá trị của nó theo cường độ cục bộ

trung bình.

 Bước 2: Làm mỏng

Phương pháp này nhằm làm mỏng bề dày của vân tay về còn một điểm

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

ảnh mà các cấu trúc vân tay vẫn đảm bảo (Hình 2.8).

Hình 2.8: Kết quả của việc Nhị phân hóa và Làm mỏng của ảnh đã được tăng cường

 Bước 3: Rút trích

Giả sử (x, y) là một điểm trên đường vân đã được làm mỏng và N0, N1,

…, N7 là 8 điểm xung quanh nó thì:

 (x,y) là một điểm rẽ nhánh nếu

Hình 2.9: a, Một phần điểm vân tay; b,Điểm kết thúc; c, Điểm rẽ nhánh

 (x,y) là một điểm kết thúc nếu

 Bước 4. Lọc đặc trưng

Sự xuất hiện các lỗ, các đứt gãy nhỏ và các cầu giữa các vân trên ảnh

vân tay đã được nhị phân hóa làm ảnh hưởng đến việc rút trích sai các đặc

trưng. Như vậy một bước tiền xử lý trước khi rút trích các đặc trưng sẽ hữu

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

ích cho việc loại bỏ các đặc trưng lỗi.

Hình 2.10: Lỗ và đứt gãy nhỏ trong ảnh vân tay đã được Nhị phân hóa và làm mỏng.

Có hai loại xử lý để loại bỏ các đặc trưng lỗi: xử lý dựa vào cấu trúc vân

và lọc đặc trưng theo miền xám ảnh.

 Xử lý dựa vào cấu trúc vân: để phát hiện các đặc trưng lỗi, có thể sử

dụng vài luật cấu trúc đơn giản. Xiao xác định các cấu trúc đặc trưng lỗi và

đưa ra phương pháp loại bỏ chúng. Thuật toán sử dụng dựa trên các luật đơn

giản; xác định các đặc tính số học liên quan đến các đặc trưng: chiều dài các

vân, góc đặc trưng, và số các đặc trưng đối diện gần kề trong lân cận.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 2.11: Các cấu trúc vân lỗi phổ biến được điều chỉnh lại thành các cấu trúc vân đúng

 Lọc đặc trưng theo miền mức xám ảnh: để phát hiện các đặc trưng

thực sự, thuật toàn rà soát lại dựa vào các đặc trưng gần kề xung quanh nó.

2.2.2. Rút trích các đặc trưng trực tiếp từ ảnh xám

Ý tưởng của phương pháp này là dựa vào thuật toán Dò theo đường vân.

Từ ảnh vân tay đã được tăng cường, thuật toán sẽ dò các đường vân để tìm ra

các đặc trưng rẽ nhánh và các đặc trưng kết thúc. Mặc dù sử dụng các khái

niệm phức tạp hơn nhưng phương pháp này có độ tính toán ít phức tạp hơn so

với phương pháp rút trích đặc trưng từ ảnh đã được nhị phân hóa. Các bước

cơ bản được thực hiện như sau:

Bước 1: Dò theo đường vân

Giả sử I là một ảnh xám có kích thước là a x b, và z là giá trị mức xám

Hình 2.12: Các đường vân (ridge) và các rãnh (ravine) trên bề mặt vân tay.

tại điểm (i, j) thì bề mặt của ảnh vân tay I có dạng như trong hình 2.12.

Về mặt toán học, đường vân là tập hợp các điểm cực đại dọc theo cùng

một hướng xác định. Việc rút trích các đặc trưng trực tiếp từ ảnh xám dựa vào

thuật toán Dò theo đường vân. Trong đó, thuật toán này dựa vào việc xác định

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

các điểm cực đại trực giao với hướng của đường vân.

Các bước chính rút trích đặc trưng bằng thuật toán Dò theo đường vân

được thực hiện như sau:

 Lấy một điểm bất kỳ (is, js) trên ảnh I.

 Xác định hướng φs tại điểm (is, js).

 Tìm điểm cực đại (ic, jc) mà gần với (is, js) nhất. (Hình 2.13)

 Xác định hướng φc tại điểm (ic, jc).

 Dịch chuyển một đoạn µ theo hướng φc . (Hình 2.14).

 Điều chỉnh lại điểm cực đại (ic, jc) và hướng φc.

 Tiếp tục dò theo đường vân cho đến khi không phát hiện được điểm

cực đại (ic, jc) thì đó là điểm đặc trưng ( có thể là điểm kết thúc hay điểm rẽ

nhánh).

 Tiếp theo chọn một điểm (is, js) khác và thực hiện lại quá trình trên cho

Hình 2.13: Điểm cực đại (ic, jc) tương ứng với (is, js).

đến khi dò hết tất cả các đường vân.

Trong luận văn, phương pháp rút trích các đặc trưng từ ảnh đã được

nhị phân hóa được áp dụng để cài đặt lên Hệ thống.

2.3 Phương pháp đối sánh vân tay

2.3.1 Đặt vấn đề

Thuật toán đối sánh vân tay so sánh hai ảnh vân tay và cho ra độ tương

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

tự (có giá trị nằm trong khoảng 0 và 1). Kết luận của việc đối sánh, khớp hay

không khớp, phụ thuộc vào ngưỡng t. Hầu hết các thuật toán NDVT đều dựa

vào việc đối sánh các điểm đặc trưng; chỉ có một vài thuật toán đối sánh trực

tiếp trên ảnh xám. Ngoài ra việc đối sánh hai ảnh vân tay là một bài toán vô

cùng khó. Có rất nhiều yếu tố ảnh hưởng đến việc đối sánh. Sau đây là các

yếu tố chính:

 Sự dịch chuyển: cùng một ngón tay cho mỗi lần lấy mẫu, DVT có thể

đặt ở các vị trị khác nhau trên bộ cảm biến làm tịnh tiến ảnh vân tay. Một

ngón tay nếu dịch chuyển 2mm sẽ làm tịnh tiến khoảng 40 điểm ảnh trong

cùng một vân tay được quét ở độ phân giải 500dpi.

 Sự quay: cùng một ngón tay cho mỗi lần lấy mấu, DVT có thể quay ở

các góc khác nhau trên bề mặt thiết bị đầu đọc vân tay; mặc dù, bộ hướng dẫn

ngón tay được gắn trên các máy quét thương mại, nhưng trong thực tế tồn tại

sự quay không cố ý lên tới ±20 độ theo chiều đứng.

 Sự chồng chéo từng phần: sự dịch chuyển và sự quay vân tay thường

làm cho một phần vân tay nằm ra ngoài vùng nhìn thấy của bộ cảm biến. Kết

quả là xuất hiện sự chồng chéo giữa các vùng cận cạnh của mẫu vân và các

vân tay đầu vào.

 Sự biến dạng phi tuyến: do sự mềm dẻo của ngón tay, việc ánh xạ

hình ảnh ba chiều sang hình ảnh hai chiều trên bề mặt bộ cảm biến gây ra biến

dạng phi tuyến trong việc đọc vân tay.

 Lực ấn và tình trạng của da: cấu trúc vân của một ngón tay sẽ được

lấy chính xác nếu như phần ngón tay được tiếp xúc đúng quy cách với bề mặt

bộ cảm biến. Một số yếu tố khác như: áp lực ngón tay, ngón tay khô, bệnh

ngoài da, ướt, bẩn, độ ẩm không khí, … gây ra sự tiếp xúc không đúng quy

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

cách; hệ quả là ảnh vân tay được lấy có chất lượng không tốt.

 Các lỗi rút trích đặc trưng: các thuật toán rút trích đặc trưng chưa

hoàn hảo. Các lỗi có thể được tạo ra trong bất kỳ giai đoạn nào của quá trình

rút trích đặc trưng như: Ước lượng hướng và Ước lượng tần số, phân đoạn

vùng vân tay từ nền, …).

Cho đến nay, có rất nhiều thuật toán đối sánh vân tay đã được đề xuất

làm giảm ảnh hưởng các yếu tố trên. Hầu hết các thuật toán này không gặp

khó khăn trong đối sánh các ảnh vân tay chất lượng tốt. Nhưng trong ảnh chất

lượng thấp, đối sánh vân tay vẫn còn là một thách thức. Các phương pháp đối

sánh vân tay có thể được phân thành 3 loại: Đối sánh dựa vào độ tương quan,

Đối sánh dựa vào đặc trưng, và Đối sánh dựa vào đặc tính vân.

2.3.2 Đối sánh dựa vào độ tương quan

Tư tưởng chính phương pháp này sẽ chồng hai ảnh vân tay lên nhau và

xem xét sự tương quan giữa các điểm ảnh được tính dựa trên độ khác biệt

giữa các điểm ảnh trong hai ảnh vân tay: khác biệt về vị trí, hướng vân tại

điểm ảnh, …

Đặt T và I là hai ảnh vân tay tương ứng với vân tay mẫu và vân tay đầu

vào. Một độ đo trực quan về sự sai biệt được tính bằng tổng các bình phương

khác nhau (SSD) của các cường độ các điểm ảnh tương ứng:

SSD(T,I) = ||T-I||2 = (T-I)T(T-I) = ||T||2 + ||I||2 – 2TTI (BT 2.1)

Trong đó chỉ số T kí hiệu sự hoán vị của một véc tơ. Nếu ||T||2 và ||I||2 là

hằng số thì sự sai biệt giữa hai ảnh được tối thiểu khi độ tương quan chéo

(CC) giữa T và I được cực đại:

CC(T,I) = TTI (BT 2.2)

Đại lượng -2*CC(T,I) xuất hiện như là đại lượng thứ ba trong biểu thức

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

(2.1). Do luôn có sự dịch chuyển và sự quay trong các ảnh vân tay, nên độ

tương tự giữa chúng không thể đơn giản được tính bằng cách đặt chồng T và I

và áp dụng biểu thức (2.2).

Đặt I (Δx, Δy, θ) là một phép quay của ảnh đầu vào I với một góc θ so với

điểm trung tâm ảnh và dịch một đoạn Δx, Δy dọc theo trục x và y; khi đó, độ

tương tự giữa hai ảnh T và I có thể được đo như sau:

S(T,I) = max CC(T,I(Δx, Δy, θ)) (BT 2.3)

Việc ứng dụng biểu thức 3 vẫn chưa cho ra kết quả tốt vì một số vấn

đề sau:

1. Các biến dạng phi tuyến làm cho các vết ấn của cùng một ngón tay

khác nhau trong cấu trúc toàn cục; do vậy, khi chồng hai ảnh lên nhau sẽ có

độ tương quan khác nhau.

2. Tình trạng da và áp lực ấn ngón tay làm cho độ sang, độ tương

phản, và độ dày vân thay đổi trong các vết ấn khác nhau.

3. Việc tính toán của biểu thức 3 tốn rất nhiều chi phí; ví dụ: với ảnh

có kích thước 400x400, thì việc tính toán chéo của biểu thức 2 cho (Δx, Δy, θ)

cần tới 16.000 phép nhân và 16.000 phép cộng. Nếu Δx, Δy dịch chuyển mỗi

lần 1 điểm ảnh trong phạm vi [-200, 200], và θ xoay mỗi lần một độ trong

một khoảng [-300, 300] thì khoảng 1569 tỷ phép nhân và phép cộng.

2.3.3 Đối sánh dựa vào đặc trưng

Đây là kỹ thuật được sử dụng phổ biến và rộng rãi nhất. Các đặc trưng

được rút trích từ hai ảnh vân tay lưu trữ như là tập các điểm trong một bề mặt hai

chiều. Sau đó, đối sánh vân tay sẽ dùng các đặc trưng này để đối sánh với nhau.

Đặt T và I là hai ảnh vân tay tương ứng với vân tay mẫu và vân tay đầu

vào. Không giống như phương pháp đối sánh dựa vào độ tương quan, phương

pháp này đối sánh hai ảnh vân tay dựa vào các đặc trưng. Mỗi đặc trưng có

thể được mô tả bằng một số các thuộc tính, bao gồm: vị trí trong ảnh vân tay,

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

hướng, loại đặc trưng (điểm kết thúc vân hay điểm rẽ nhánh), một trọng số

dựa trên chất lượng ảnh của vân tay trong một lân cận của đặc trưng, … Hầu

hết các thuật toán đối sánh đặc trưng xem xét mỗi đặc trưng là một nhóm bộ

ba m = {x, y, θ} thể hiện vị trí chi tiết ở vị trí x, y và góc đặc trưng θ:

T = {m1, m2, …mm}; mi = {xi, yi, θi}, i = 1…m

I = {m1’, m2’, …mn’}; mj’ = {xj’, yj’, θi’}, j = 1…n

Trong đó m và n tương ứng là số các đặc trưng trong T và I.

’ trong I và một đặc trưng mi trong T được xem là đối

Một đặc trưng mj

sánh với nhau nếu khoảng cách không gian (sd) giữa chúng là nhỏ hơn mức

độ sai cho trước ro và sự khác nhau về hướng (dd) giữa chúng là nhỏ hơn góc

(BT 2.4)

độ sai θo:

’ – θi|, 360o - |θj

’ – θi| bởi

Biểu thức trên (2.4) lấy giá trị nhỏ nhất của |θj

vì tính chu kỳ của góc (sự lệch góc nhau giữa 20 và 3580 chỉ là 40). Độ sai

ro và θo được định nghĩa để bù vào các lỗi không thể tránh khỏi do các thuật

toán rút trích đặc trưng và các nhiễu mềm dẻo làm cho vị trí các đặc trưng

thay đổi.

Canh lề hai vân tay là bước bắt buộc để cực đại hóa số các đặc trưng. Để

canh lề chính xác hai vân tay cần phải dịch chuyển (theo x và y), và quay góc

(θ), được gọi là các biến đổi hình học:

Đặt map(.) là hàm ánh xạ một đặc trưng mj’ (từ I) vào trong m”j theo

công thức biến đổi hình học cho trước; ví dụ, xem xét sự dịch chuyển của

[Δx, Δy] và một góc quay ngược chiều kim đồng hồ θ quanh điểm gốc. (Điểm

gốc thường được chọn như là đặc trưng trung tâm; trước khi đối sánh, tọa độ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

của các đặc trưng được điều chỉnh bằng việc trừ tọa độ điểm gốc):

Trong đó:

Đặt mm(.) là hàm chỉ thị trả về 1 trong trường hợp đặc trưng m”j và mi

đối sánh theo biểu thức (2.4):

(BT 2.5)

Sau đó bài toán đối sánh có thể được xác định bởi công thức như sau:

Trong đó, P(i) là một hàm không biết trước quyết định cặp đôi giữa các

đặc trưng I và T: nghĩa là mỗi đặc trưng có một cặp đôi tương ứng trên vân

tay khác hoặc không có cặp đôi tương ứng nào:

1. P(i) = j: nghĩa là cặp đôi tương ứng của mi trong T là đặc trưng m’j

trong I.

2. P(i) = null: nghĩa là đặc trưng mi trong T không có đặc trưng tương

ứng trong I.

3. Một đặc trưng m’j trong I, với mọi i = 1…m không có đặc trưng tương

ứng trong T.

4. Mọi i = 1…m, k = 1…m, I ≠ k => P(i) ≠ P(k) hay P(i) = P(k) = null

(điều này yêu cầu mỗi đặc trưng trong I được liên hệ tối đa với một đặc trưng

trong T).

Thường P(i) = j không có nghĩa là đặc trưng m’j và mi khớp nhau theo

biểu thức (2.4) mà nghĩa là các cặp này tương tự nhau theo công thức biến đổi

hiện tại.

Biểu thức (2.5) yêu cầu số các đặc trưng tương ứng được cực đại, độc

lập với các giới hạn của các đặc trưng tương ứng này: nghĩa là nếu hai đặc Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trưng thỏa mãn biểu thức (2.4). Sau đó, đưa chúng vào biểu thức (2.5) thì tạo

ra sự độc lập về khoảng cách và về sự khác nhau của hướng. Một công thức

khác biểu thức (2.5) được đưa ra với phần dư (nghĩa là khoảng cách và sự

khác nhau về hướng giữa các đặc trưng) được xem xét cho canh chỉnh tối ưu.

Giải quyết bài toán đối sánh đặc trưng (biểu thức 2.5) là dễ khi canh

chỉnh đúng (Δx, Δy, θ) đã được biết. Trong thực tế, việc ghép cặp (nghĩa là

hàm P) có thể được quyết định bằng cách thiết lập riêng cho mỗi i = 1…m:

j = mapΔx, Δy, θ (m’j) có giá trị gần mi nhất giữa đặc trưng

 P(i) = j nếu mn

Để thỏa mãn với ràng buộc 4 ở trên, mỗi đặc trưng đã bắt cặp phải

được đánh dấu, để tránh bắt cặp hai lần.

2.3.4 Đối sánh đặc trưng cục bộ và toàn cục

Đối sánh đặc trưng cục bộ bao gồm việc so sánh hai DVT căn cứ vào các

cấu trúc đặc trưng cục bộ; các cấu trúc cục bộ được đặc tính hóa độc lập với

các phép biến đổi trên toàn cục (như sự dịch chuyển, sự quay, …); do đó,

không cần canh chỉnh trên toàn cục trước khi đối sánh vân tay. Việc đối sánh

cục bộ và toàn cục làm cho việc đối sánh sẽ trở nên đơn giản, độ phức tạp tính

toán giảm; phù hợp với những hình vân tay bị biến dạng (méo mó hay bị co

giản), và độ phân biệt cao với các ngón tay khác. Các tác giả Jiang và Yau

đưa ra có dạng là một đặc trưng trung tâm cùng với hai đặc trưng láng giềng

gần nó nhất; véc tơ vi là đặc tính của đặc trưng mi, mj là đặc trưng láng giềng

gần mi nhất, mk là đặc trưng láng giềng gần mi thứ nhì.

Vi = [dij, dik, θij, θik, φij, φik, nij, nik, ti, tj, tk],

Trong đó dab là khoảng cách giữa đặc trưng ma và mb, θab là độ lêch

hướng giữa góc θa và θb của ma và mb, φab độ lệch hướng giữa góc θa của ma

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

.(Hình 2.14)

Hình 2.14: Các đặc tính của cấu trúc cục bộ được dùng bởi Jiang và Yau (2000).

Việc đối sánh đặc trưng cục bộ được thực hiện bằng việc tính toán mỗi cặp

đặc trưng mi và m’j, i = 1…m, j = 1…n, một khoảng cách trọng số giữa các

véc tơ vi và v’j. Cặp đối sánh tốt nhất được chọn và được dùng làm điểm tham

chiếu cho hai DVT. Các véc tơ đặc tính của các cặp còn lại được canh chỉnh

theo điểm tham chiếu để đối sánh và kết quả đối sánh được tính toán dựa vào

độ khác biệt của các cặp đối sánh này.

2.3.5 Đối sánh dựa vào đặc tính vân

Việc rút trích các đặc trưng sẽ gặp nhiều khó khăn trong các ảnh

vân tay chất lượng thấp. Trong khi các đặc tính khác của mẫu vân, hướng và

tần số cục bộ, hình dạng vân, thông tin kết cấu, có thể được rút trích một cách

tin cậy hơn các đặc trưng; do vậy, kỹ thuật này dựa vào các đặc tính được rút

trích từ các mẫu vân để đối sánh vân tay. Về nguyên lý, đối sánh dựa độ

tương quan và đối sánh dựa vào đặc trưng có thể được xem như là một phần

của đối sánh dựa vào đặc tính vân, theo cách hiểu mật độ điểm ảnh, vị trí đặc

trưng là những đặc tính của mẫu vân ngón tay.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Các đặc tính khác thường được sử dụng để đối sánh:

1. Kích thước của vân tay và hình dạng ngoài của vân tay.

2. Số lượng, loại vân tay, và vị trí các điểm đơn.

3. Mối liên hệ không gian và các thuộc tính hình học của đường vân.

4. Các đặc tính hình dạng được đưa ra bởi Takeda.

5. Thông tin kết cấu toàn cục và cục bộ của vân tay.

6. Các lỗ chân long.

7. Các đặc tính nhỏ được đưa ra bởi Polikarpova.

Nói chung, các đặc trưng ở 1 và 2 thường không ổn định, và chúng thay

đổi theo phần ngón tay tiếp xúc lên bộ cảm biến. Các lỗ chân lông rất rõ ràng,

nhưng phải cần các máy quét đắt tiền có độ phân giải cao mới có thể phát hiện

chúng. Việc dùng mối liên hệ không gian của các vân lập thành các phương

pháp cấu trúc cơ bản được đưa ra bởi Moayer và Flu (1986), Isenor và Zaky

(1986). Phương pháp Moayer dùng các ngữ pháp cây để phân loại các mẫu

đường vân sau khi chúng được nhị phân hóa và làm mỏng vân. Phương pháp

Flu đối sánh đồ thị tăng dần được thực hiện để so sánh một tập các vân được

sắp xếp trong các cấu trúc đồ thị.

Ceguerra và Koprinska (2002) đưa ra các đặc tính dựa vào hình dạng, bao

gồm chữ ký hình dạng một chiều mã hóa hình dạng chung của vân tay được

tạo ra từ ảnh vân tay hai chiều sử dụng trục tham chiếu. Đối sánh dựa vào

hình dạng sau đó được áp dụng cùng với đối sánh dựa vào đặc trưng để đưa ra

quyết định cuối cùng. Thông tin cấu trúc toàn cục và cục bộ là đặc tính khác

quan trọng cho việc đối sánh vân tay dựa vào cấu trúc đặc trưng vân đang là

hướng nghiên cứu. Các cấu trúc được định nghĩa bằng quan hệ không gian

giữa các thành phần cơ bản và đặc trưng hóa bởi các thuộc tính như độ co

giãn, hướng vân, tần số vân, …

Jiang đề nghị kỹ thuật phân tích cấu trúc cục bộ trong vùng vân tay quan tâm

chứa điểm core (Hình 2.15). Thông tin cấu trúc cục bộ trong mỗi phần

(sector) được phân rã thành các kênh (channels) riêng biệt bằng việc sử dụng

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Gabor filterbank. Kỹ thuật này còn được gọi là FingerCode.

Hình 2.15: Sơ đồ nhận dạng vân tay dùng kỹ thuật FingerCode

Kết luận: Trong các phương pháp đối sánh vân tay, phương pháp đối

sánh dựa vào đặc trưng được sử dụng nhiều nhất. Phương pháp này cũng phù

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

hợp với tính chất của hệ thống nhúng nhất so với các phương pháp còn lại.

Chương 3

XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÂN TAY

Xuất phát từ các cơ sở toán học của bài toán NDVT, trong chương này

luận văn sẽ tập trung vào việc mô tả chi tiết các thuật toán đã đuợc sử dụng và

kết quả thực nghiệm các thuật toán trên bộ dữ liệu mẫu. Các thuật toán sẽ lần

lượt thực hiện lần lượt các bước để đối sánh vân tay theo lưu đồ thuật toán.

Các thuật toán được thử nghiệm trên phần mềm được viết bằng ngôn ngữ

hướng đối tượng Visual Matlab trong đó:

 Lớp ImageData chứa dữ liệu ảnh và tất cả các thuật toán liên quan

đến việc xử lý ảnh vân tay.

 Lớp Minutiae chứa dữ liệu về chi tiết và một số phương thức xử lý

chi tiết như quay và tịnh tiến.

 Lớp Functions chứa một số hàm tĩnh để xử lý giữa các ảnh và các chi

tiết như so sánh chi tiết, so sánh ảnh, khoảng cách các chi tiết,….

Các form của chương trình đuợc thiết kế đơn giản, đầy đủ chức năng mô

phỏng việc thực hiện các thuật toán (tính hướng vân tay cục bộ, chuẩn hóa

ảnh, tăng cường ảnh, nhị phân hóa, tìm xương vân, tìm chi tiết…). Người

dùng có thể vào Công cụ->Kiểm nghiệm thuật toán . Khi đó sẽ hiện ra form

để bạn có thể tiến hành từng bước một. Click vào nút “Mở ảnh” để chọn ảnh

bạn muốn kiểm nghiệm. Còn việc đối sánh được thực hiện ngay ở form chính

của chương trình.

3.1. Tính hướng vân tay cục bộ.

Thuật toán

Để tính hướng vân tay cục bộ tại vị trí điểm ảnh [xi, yj ]. Xét một ô

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

vuông có kích thước tùy ý, tính Gxy theo công thức:

Tính Gxx theo công thức:

Tính Gyy theo công thức:

Cuối cùng hướng cụa bộ tại vị trí điểm ảnh [ xi, yj ] được tính bởi

công thức:

Ở đây x và y được là thành phần gradient được tính qua mặt nạ (3x3)

Sobel.

Để kiểm nghiệm kết quả, click vào bất kỳ vị trí nào trên ảnh vân tay, ta

sẽ nhận được hướng vân tay cục bộ tại điểm đó. Hình 3.1 là kết quả của việc

click một số lần lên ảnh vân được thực hiện bởi hệ thống.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 3.1: Hướng vân tay cục bộ

3.2. Chuẩn hóa ảnh.

Trong gian đoạn này bao 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. Chúng ta xét vấn đề

chuẩn hóa kích thước ảnh: ảnh đầu vào có kích thước 256 x 256 pixel.

Thuật toán

Bước 1: tính kỳ vọng của ảnh theo công thức:

Bước 2: tính giá trị phương sai của ảnh theo công thức.

Bước 3: tính giá trị mức xám mới theo công thức

Kết quả thực hiện: Chọn nút “Chuẩn hóa” trên hệ thống, ta được kết

quả thực hiện như sau:

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 3.2: Ảnh đã chuẩn hóa

3.3. Tăng cường ảnh

Hai thuật toán sử dụng dùng để tăng cường 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.

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 đó.

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.

Thuật toán

Bước 1: Tính [ ] theo công thức.

Bước 2: Tìm mặt nạ tại mỗi điểm theo công thức.

Trong đó  chính là hướng vân tay cục bộ tại điểm đó. Và f là tần suất

vân tay cục bộ tại điểm đó.

Bước 3: Thực hiện nhân chập mặt nạ thu được với ma trận ảnh. Giá trị

cấp xám mới của điểm ảnh chính là giá trị tại điểm đó của kết quả nhân chập.

Kết quả thực hiện: Chọn nút “Tăng cường” ta thu được kết quả của

ảnh vân tay sau khi tăng cường.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 3.3: Vân tay sau khi tăng cường

3.4 Tách ngưỡng tự động.

Thuật toán

Xác định ngưỡng bằng cách: Gọi t(g) là số điểm ảnh có giá trị  g, m(g)

là giá trị trung bình của các điểm ảnh có giá trị  g:

Gọi G là số cấp xám được xét, P là số điểm ảnh được xét, Khi đó

Giá trị ngưỡng cần tìm là , sao cho () = max (g). Khi đó ta tách

ngưỡng.

1 nếu I(x,y)

I(x,y) =

0 nếu I(x,y)<

Kết quả thực hiện: Chọn nút “Nhị phân hóa” ta sẽ ra kết quả của việc

tách ngưỡng nhờ tìm ngưỡng tự động như sau:

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 3.4: Vân tay sau khi tách ngưỡng tự động

3.5 Thuật toán tìm xương.

Để xác định xương của ảnh vân tay, chúng ta phải qua hai bước

Bước 1: Xác định các điểm biên

Điểm (x,y) là điểm biên nếu thỏa mãn điều kiện có ít nhất 1 điểm láng

riềng trong 4 điểm có giá trị Image()=0. Điều kiện thỏa mãn điểm biên được

kiểm tra bằng hàm logic sau:

BOOL IsBorder(int x, int y)

{If ( Image[x-1 ][y] ==0 || Image[x+1 ][y] ==0 ||

Image[x][y-1]==0||Image[x][y+1] ==0) return TRUE; else return

FALSE;

}

Bước 2: Xóa điểm biên

Để xóa điểm biên phải đảm bảo các điều kiện

+ Không làm mất tính chất liên thông

+ Không tạo ra lỗ hổng

+ Không làm mất điểm cụt

+ Các điểm còn lại thuộc trục trung vị

+ Bất biến với phép quay tịnh tiến

Hàm kiểm tra điểm (x,y) đủ điều kiện xóa được mô tả bằng hàm logic

sau đây:

BOOL IsDeletable(int x, int y)

{ BOOL P0 = Image[x+1][y], P1 = Image[x+1][y-1],

P2 = Image[x][y-1], P3 = Image[x-11][y-1],

P4 = Image[x-1][y], P5 = Image[x-1][y+1],

P6 = Image[x][y+1], P7 = Image[x+1][y+1];

if (P1*P2*P3 == 1 && P5+P6+P7==0) return TRUE;

if (P0*P1*P2 == 1 && P4+P5+P6==0) return TRUE;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

if (P0*P1*P7 == 1 && P3+P4+P5==0) return TRUE;

//...

return FALSE;}

Khi đó việc tìm xương được thực hiện bằng thủ tục sau đây:

void MakeBone()

{ BOOL Manh = FALSE;

Stack S;

S.Empty(); // Khởi tạo ngăn xếp rỗng

while (!Manh)

{ Manh = TRUE;

for (int i=0; i

for (int j=0; j

if (IsBorder(i,j))

if (IsDeletable(i,j)) //Đẩy các điểm có thể xoá được

{ S.Push(i,j); //vào ngăn xếp

Manh = FALSE;}

while (!S.IsEmpty) //Xoá tất cả các điểm trong ngăn xếp

{ S.Pop(i,j);

Image[i][j] = 0;}

}}

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Kết quả thực hiện: Chọn nút “Tìm xương” ta sẽ thu được kết quả

Hình 3.5: Xương của ảnh vân tay

3.6 Thuật toán tìm kiếm chi tiết.

Chi tiết vân tay chính là những điểm ảnh đặc biệt nằm trên xương của

vân tay và hướng vân cục bộ tại điểm đó. Điểm đặc biệt chính là điểm kết

thúc hoặc rẽ nhánh của đường vân. Việc kiểm tra một điểm có là điểm rẽ

nhánh hay điểm kết thúc hay không được thực hiện bằng các tính tổng các trị

tuyệt đối của hiệu các cặp điểm liên tục xung quanh điểm đang xét. Nếu tổng

bằng 1 thì đó là điểm kết thúc, và bằng 3 nếu nó là điểm rẽ nhánh.

Cụ thể cho điểm ảnh (x,y), việc kiểm tra điểm (x,y) là điểm đặc biệt

được mô tả bằng hàm logic sau:

BOOL IsMinutiae(int x, int y)

{If ( Image[x ][y] ==0))

{ sum = |image[x-1,y-1]-image[x-1,y]|+ |image[x-1,y+1]-

image[x,y+1]|

+ |image[x+1,y+1]-image[x+1,y]|+ |image[x+1,y+1]-image[x+1,y]|

+ |image[x+1,y-1]-image[x,y-1]|

If(sum==1orsum==3) return true;}

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

return FALSE;}

Kết quả thực hiện: Chọn nút “Xem chi tiết” sẽ hiện ra các chi tiết của

vân tay tìm được.

Hình 3.6: Các điểm đặc biệt của vân tay

3.7 Thuật toán Hough

Thuật toán Hough là thuật toán tìm ra các giá trị tịnh tiến theo trục x,

trục y, góc quay ngược chiều kim đồng hồ và độ nở của vân tay (∆x, ∆y, θ, s )

sao cho khi thực hiện các phép biến đổi đó thực hiện trên tập chi tiết của vân

tay này sẽ thu được tập chi tiết mới mà có số lượng chi tiết trùng khớp với tập

chi tiết của vân tay kia là lớn nhất. (chi tiết của thuật toán xem [4]).

3.8 Thuật toán đối sánh vân tay

Thuật toán sẽ tiến hành đối sánh hai tập chi tiết của hai ảnh vân tay.

Nếu số lượng ảnh vân trùng khớp lớn hơn một giá trị giới hạn cho cho trước

thì 2 vân tay là trùng khớp. Trước hết chúng ta tiến hành tịnh tiến và quay tập

chi tiết của ảnh hai theo các đại lượng chúng ta thu được từ thuật toán Hough.

Tiến hành đối sánh lần lượt từng chi tiết của tập chi tiết ảnh vân tay 1 với tập

chi tiết thu được.

Hai chi tiết mI = {xi, yi, θi} và mj’ = {xj’, yj’, θj’} được gọi là so khớp

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

nếu thỏa mãn:

Với r0 và θ0 là các giá trị giới hạn.

Dựa theo công thức trên sẽ đếm số lượng cặp chi tiết so khớp với nhau.

Từ đó rút ra kết luận.

Kết quả thực hiện: Với hai ảnh vân tay như sau:

Hình 3.7: Ảnh 2 vân tay cần so khớp

Chọn “Xử lý->So sánh vân tay” , hệ thống sẽ đưa ra thông báo trùng

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

khớp hay không trùng khớp.

KẾT LUẬN

Nội dung chính của luận văn là tìn hiểu cơ chế về bài toán NDVT, cơ sở

toán học của bài toán nhận dạng và các thuật toán NDVT trên thế giới. Kết

quả chính của luận văn gồm:

1. Đã tìm hiểu tổng quan về sinh trắc học, mô hình của bài toán NDVT,

tầm quan trọng của bài toán.

2. Tìm hiểu các kĩ thuật cơ bản của bài toán NDVT

3. Các thuật toán cơ bản (tiền xử lý, rút trích đặc trưng, đối sánh vân tay)

4. Mô tả chi thiết các thuật toán theo từng bước của quá trình NDVT

5. Xây dựng hệ thống kiểm nghiệm độ chính xác của mô hình nhận dạng

trên môi trường Matlab.

Hướng phát triển tiếp theo là phát triển và nâng cao chất lượng của hệ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

thống nhận dạng với các thuật toán chính xác hơn.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Lương Mạnh Bá, Nguyễn Thanh Thuỷ. Nhập môn xử lý ảnh số. Nhà

xuất bản khoa học kỹ thuật, 1999.

[2] Nguyễn Hoàng Huy (2010), Nhận dạng vân tay, Trung tâm thông tin

thư viện, ĐH QG HCM.

[3] Ngô Tứ Thành, Nguyễn Thế Dũng (2008), Một số vấn đề về hướng

của điểm đặc trưng ảnh vân tay, Kỉ yếu Hội thảo Quốc gia.

Tiếng Anh

[4] Orit Baruch, Line thinning by line following. Pattern Recognition

Letters, 8:271–276, 1988.

[5] A. M. Baze, G. T. B Verwaaijen, S. H. Garez, L. P. J. Veelunturf, and B.

J. van der Zwaag. A correlation-based fingerprint verification system. In

ProRISC2000 Workshops on Circuits, Systems and Signal Processing, Nov 2000.

[6] A .M. Bazen and S.H. Gerez. Extraction of singular points from

directional fields of fingerprints. February 2001.

[7] Asker M. Bazen and Sabih H. Gerez. Fingerprint matching by thin-

plate spline modeling ofelastic deformations. Pattern Recognition, 36:1859–

1867, 2003.97

[8] B.G.Sherlock and D.M.Monro. A model for interpreting fingerprint

topology. Pattern Recognition, 26(7):1047–1055, 1993.

[9] B.G.Sherlock, D.M.Monro, and K.Millard. Fingerprint enhancement

by directional fourier filtering. In Visual Image Signal Processing, volume

141, pages 87–94, 1994.

[10] Ruud Bolle, J. H. Connell, S. Pankanti, N. K. Ratha, and A. W.

Senior. Guide to Biometrics.Springer Verlag, 2003.

[11] L. Brown. A survey of image registration techniques. ACM

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Computing Surveys, 1992.

Luận văn Thạc sĩ Khoa học máy tính: Công nghệ sinh trắc học và bài toán nhận dạng vân tay

TR¦êNG §¹I HäC C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG ---------------------

NGUYỄN ANH TÚ

CÔNG NGHỆ SINH TRẮC HỌC VÀ BÀI TOÁN NHẬN DẠNG VÂN TAY

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

TR¦êNG §¹I HäC C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG ---------------------

NGUYỄN ANH TÚ

CÔNG NGHỆ SINH TRẮC HỌC VÀ BÀI TOÁN NHẬN DẠNG VÂN TAY Chuyên ngành: Khoa học máy tính Mã số: 8 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: TS. Vũ Vinh Quang

THÁI NGUYÊN - 2019

MỤC LỤC

MỤC LỤC ................................................................................................................... i

LỜI CAM ĐOAN .................................................................................................... iii

LỜI CẢM ƠN ........................................................................................................... iv

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT.......................................... v

DANH MỤC CÁC HÌNH ........................................................................................ vi

LỜI MỞ ĐẦU ............................................................................................................ 1

Chương 1: TỔNG QUAN VỀ SINH TRẮC HỌC VÀ BÀI TOÁN NHẬN

DẠNG VÂN TAY ............................................................................................. 3

Chương 2: CƠ SỞ KHOA HỌC CỦA BÀI TOÁN NHẬN DẠNG VÂN TAY ...... 20

Chương 3: XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÂN TAY ...................... 43

KẾT LUẬN .............................................................................................................. 53

TÀI LIỆU THAM KHẢO ...................................................................................... 54

LỜI CAM ĐOAN

LỜI CẢM ƠN

LỜI MỞ ĐẦU

Chương 1

TỔNG QUAN VỀ SINH TRẮC HỌC VÀ BÀI TOÁN

NHẬN DẠNG VÂN TAY

Chương 2

Chương 3

XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÂN TAY

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok