i


LỜI CẢM ƠN

Trong thời gian học tập tại trường em đã được quý Thầy, Cô của Trường Đại Học
Khoa học Tự Nhiên TP. Hồ Chí Minh đã hết lòng trong công tác giảng dạy và tận
tình truyền đạt kiến thức không những chuyên môn mà còn cả kinh nghiệm sống,
làm việc và nghiên cứu khoa học. Đặc biệt, em chân thành cám ơn thầy Lê Hoàng
Thái đã tận tình hướng dẫn em thực hiện đề tài.
Xin chân thành cám ơn các bạn đồng nghiệp đã động viên tinh thần, góp ý, xây
dựng những hướng đi trong quá trình thực hiện.
Và cuối cùng, cám ơn tất cả những người thân trong gia đình và bạn bè, đồng
nghiệp đã giúp em hoàn thành luận văn này.

Hà Nhật Tâm
- 1 -


MỞ ĐẦU
1. Lời nói đầu
Nhận dạng vân tay được xem là một phương pháp nhận dạng đáng tin cậy nhất để
nhận dạng một người trong số các phương pháp nhận dạng sinh trắc học [13]. Nhiều
nghiên cứu cho thấy vân tay của mỗi người là duy nhất và bất biến với thời gian.
Nhờ đặc trưng này mà vân tay ngày càng được sử dụng rộng rãi để nhận dạng một
cá nhân. Nhiều phương pháp khoa học đã được đề xuất để giải quyết vấn đề lựa
chọn đặc trưng cho việc nhận dạng vân tay. Nhiều hệ thống nhận dạng vân tay tự
động (Automatic Fingerprint Identification System - AFIS) cũng đã được phát triển
để giải quyết bài toán tự động hóa trong nhận dạng. Hiện nay, hệ thống này được sử
dụng rộng rãi trong nhiều lĩnh vực an ninh, thương mại .v.v…Tuy nhiên, hệ thống

nhận dạng vân tay mà trong đó mẫu vân thu nhận bị mất mát thông tin vẫn còn là
bài toán khó và nhiều thách thức. Do đó, trong thời gian gần đây, nhiều phương
pháp mới vẫn đang tiếp tục được nghiên cứu sao cho hệ thống đạt được hiệu quả
cao hơn
Luận văn đề xuất phương pháp xác thực ảnh vân tay dùng mô hình tổng hợp mẫu
vân. Trong đó, các ảnh vân tay mẫu ban đầu của một đối tượng được tổng hợp để
tạo ra một ảnh mới đại diện cho tất cả các ảnh mẫu sử dụng cho quá trình so khớp.
Ảnh đại diện này được bổ sung các đặc trưng từ các ảnh mẫu nên giảm thiểu bớt sự
mất mát thông tin. Thực nghiệm được tiến hành trên cơ sở dữ liệu vân tay chuẩn
trên thế giới - cơ sở dữ liệu (CSDL) FVC2004 DB4, tập A. Kết quả thực nghiệm
cho thấy tính khả thi của phương pháp đề xuất.
2. Bố cục của đề tài
Luận văn trình bày gồm 5 chương. Chương 1 giới thiệu tổng quan về quá trình hình
thành và phát triển của phương pháp sinh trắc học mà trong đó nhận dạng vân tay là
một trong những phương pháp hứa hẹn, các dạng đặc trương của vân tay, các giai
đoạn xử lý trong hệ thống nhân dạng vân tay tự động và đóng góp của luận văn.
- 2 -


Chương 2 trình bày khảo sát của tác giả về một số phương pháp đối sánh ảnh vân
tay. Chương 3 trình bày nội dung nghiên cứu chính của luận văn về hướng đề xuất
xác thực ảnh vân tay dùng mô hình tổng hợp mẫu vân. Chương 4 thể hiện kết quả
thực nghiệm được triển khai trên cơ sở dữ liệu chuẩn FVC2004 DB4, tập A.
Chương 5 là kết luận chung và hướng phát triển của đề tài. Phần Tài liệu tham khảo
trình bày các bài báo, sách, được tham khảo, trích dẫn trong luận văn. Các phần phụ
lục trình bày giao diện chương trình, một số lý thuyết liên quan, các bảng dữ liệu và
bài báo liên quan đến đề tài.

ii



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

DANH MỤC CÁC BẢNG vi

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ vii

BẢNG CHÚ GIẢI xi

MỞ ĐẦU - 1 -

Chương 1 .

TỔNG QUAN - 3 -

1.1

Giới thiệu - 3 -

1.2

Vài nét sơ lược về lịch sử khoa học nhận dạng vân tay - 3 -

1.3

Các đặc trưng của vân tay - 4 -

1.4


Sinh trắc học và ứng dụng - 6 -

1.5

Các bước xử lý trong hệ thống chứng thực vân tay tự động - 7 -

1.5.1

Tiền xử lý ảnh vân tay - 7 -

1.5.2

Làm mỏng đường vân - 8 -

1.5.3

Rút trích đặc trưng - 9 -

1.5.4

Chứng thực vân tay - 11 -

1.6

Đóng góp của luận văn - 12 -

Chương 2 .

TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP ĐỐI SÁNH ẢNH
VÂN TAY - 13 -


2.1

Giới thiệu - 13 -

2.2

Các thuật toán đối sánh dựa trên sự tương quan (Correlation-based
Matching) - 13 -

2.2.1

Thuật toán của tác giả Davide Maltoni và các cộng sự [14] - 14 -

2.2.2

Thuật toán của tác giả Abdullah [6] - 14 -

2.3

Đối sánh dựa trên đặc trưng vân (Ridge feature-based Matching) - 17 -

2.3.1

Thuật toán của tác giả Anil K. Jain [14] - 17 -

2.3.2

Hướng tiếp cận - 17 -


iii


2.4

Các thuật toán đối sánh dựa trên đặc trưng mảnh vụn (Minutiae-based
Matching) - 18 -

2.4.1

Thuật toán đối sánh dựa trên đặc trưng mảnh vụn - 18 -

2.4.2

Thuật toán so khớp vân tay dựa trên cấu trúc cục bộ và toàn cục của
minutiae. - 22 -

2.5

Kết luận chương 2 - 25 -

Chương 3 .

MÔ HÌNH TỔNG HỢP MẪU VÂN - 27 -

3.1

Giới thiệu - 27 -

3.2


Mô hình tổng hợp mẫu vân - 27 -

3.2.1

Giai đoạn tiền xử lý - 28 -

3.2.2

Tìm kiếm tập tham số - 29 -

3.2.3

Tổng hợp mẫu vân - 30 -

3.2.4

Hậu xử lý - 32 -

3.3

Kết luận chương 3 - 33 -

Chương 4 .

KẾT QUẢ THỰC NGHIỆM - 34 -

4.1

Giới thiệu - 34 -


4.2

Sơ lược về cơ sở dữ liệu thử nghiệm - 34 -

4.3

Ước lượng miền giá trị - 35 -

4.3.1

Ước lượng miền giá trị và ngưỡng cho GA - 35 -

4.3.2

Ước lượng giá trị cho giai đoạn tổng hợp - 36 -

4.4

Kiểm tra mô hình tổng hợp - 39 -

4.5

Ước lượng độ chính xác của phương pháp xác thực ảnh vân tay dùng mô
hình tổng hợp mẫu vân - 47 -

4.6

Kết luận chương 4 - 49 -


Chương 5 .

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN - 50 -

5.1

Kết luận - 50 -

5.2

Hướng phát triển - 51 -

Phụ Lục A

: GIAO DIỆN CHƯƠNG TRÌNH - 54 -

A.1

Giao diện mặc định của chương trình - 54 -

iv


A.2

Các bước xử lý của chương trình - 55 -

A.3

Kết quả của từng giai đoạn - 59 -


Phụ Lục B

: CÁC BẢNG DỮ LIỆU - 61 -

B.1

Bảng dữ liệu kết quả thực nghiệm xác định ngưỡng bán kính lọc nhiễu- 61
-

B.2

Bảng dữ liệu ngưỡng so khớp - 62 -

Phụ Lục C

: ĐỐI SÁNH ẢNH VÂN TAY DÙNG THUẬT GIẢI DI
TRUYỀN CỦA XUEJUN TAN-BIR BHANU VÀ CẢI TIẾN CỦA
TÁC GIẢ MAI CHIẾM TUẤN - 64 -

C.1

Giới thiệu - 64 -

C.2

Phương pháp của Xuejun Tan và Bir Bhanu - 64 -

C.3


Cải tiến của tác giả Mai Chiếm Tuấn - 70 -

Phụ Lục D

: BÀI BÁO KHOA HỌC ĐÃ ĐĂNG CỦA LUẬN VĂN- 73
-

D.1

Thông tin bài báo - 73 -

D.2 Chứng nhận bài báo đã được đăng - 73 -


v


DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
AFIS Automatic Fingerprint Identification System
GA Genetic Algorithm
CSDL Cơ sở dữ liệu

vi


DANH MỤC CÁC BẢNG

Bảng 4-1 Bảng giá trị các tham số cho GA - 36 -

Bảng 4-2 Giá trị trung bình độ thích nghi của ảnh mẫu trước và sau khi bổ sung

thông tin từ các ảnh mẫu khác - 39 -

Bảng 4-3 Kết quả của 3 lần kiểm thử về tỉ lệ chứng thực đúng, tỉ lệ từ chối sai . - 48 -

Bảng B-1 Bảng qui ước độ đo và các giá trị tương ứng sử dụng trong xác đinh
ngưỡng bán kính lọc nhiễu - 61 -

Bảng B-2 Bảng kết quả thực nghiệm xác định ngưỡng bán kính lọc nhiễu - 61 -

Bảng B-3 Bảng dữ liệu ngưỡng so khớp giống trên CSDL FVC2004, DB4, tập A
khi áp dụng thuật giải di truyền cho việc đối sánh ảnh vân tay của tác giả Mai
Chiếm Tuấn [5] - 62 -

Bảng B-4 Bảng dữ liệu thể hiện số ánh xạ tìm được trong quá trình tổng hợp của 1
lần kiểm thử - 63 -

Bảng C-1 Giá trị các tham số của GA trong hướng tiếp cận của X.Tan và Bhanu
2006 - 69 -

Bảng C-2 Bảng giá trị các tham số cho GA - 71 -

Bảng C-3 Bảng so sánh tỷ lệ chứng thực, từ chối của GA và Xiping Luo, 2000 - 72 -

Bảng C-4 Bảng 10 đối sánh tốt nhất của GA và Xiping Luo, 2000 - 72 -

vii


DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ
Hình 1-1 Đường gợn và rãnh trên ảnh vân tay (trái) và mặt cắt của một vùng da trên

ngón tay (phải) - 5 -

Hình 1-2 Các vùng đặc biệt (hình vuông trắng) và điểm core trong ảnh vân tay . - 5 -

Hình 1-3 (a) Điểm vụn dạng kết thúc đột ngột (terminal) (b) Điểm vụn dạng rẽ
nhánh (c) các điểm vụn trên cùng ảnh vân tay - 6 -

Hình 1-4 Các bước xử lý trong hệ thống chứng thực vân tay tự động - 7 -

Hình 1-5 Ảnh gốc và ảnh sau khi được tăng cường - 8 -

Hình 1-6 Tính chất 8-simple của pixel P không phải 8-simple (trái), 8-simple (phải)-
8 -

Hình 1-7 Ảnh trước (trái) và sau (phải) khi làm mỏng - 9 -

Hình 1-8 (a) ảnh ban đầu (b) minh họa đặc trưng được rút trích từ a - 10 -

Hình 1-9 Minh họa giá trị Crossing Number đối với từng loại đặc trưng - 11 -

Hình 2-1 Một số hình vân tay có điểm core khó tìm - 17 -

Hình 2-2 Ảnh vân tay bị méo, biến đổi phi tuyến khi thu nhận - 19 -

Hình 2-3 So khớp 2 ảnh vân tay - 19 -

Hình 2-4 Minh hoạ việc bắt cặp của các mảnh vụn - 21 -

Hình 3-1 Mô hình tổng hợp mẫu vân - 28 -


Hình 3-2 Giai đoạn tiền xử lý trong mô hình tổng hợp - 28 -

Hình 3-3 (a) ảnh mẫu (b) ảnh trung gian meanF và hàm biến đổi F(s,
θ
, t
x
, t
y
) - 30 -

Hình 3-4 Ảnh trung gian trước và sau khi bổ sung - 33 -

Hình 4-1 Mẫu vân tay trong cơ sở dữ liệu FVC2004, DB4 tập A - 35 -

Hình 4-2 Sự tương quan giữa độ nhiễu và độ hở của một tập ảnh - 36 -

Hình 4-3 Các ảnh sau tổng hợp từ trái sang phải từ trên xuống dưới tương ứng với
giá trị r = 0 9 - 38 -

Hình 4-4 Đồ thị thể hiện giá trị trung bình số lượng điểm vụn tương đồng của ảnh
mẫu trước và sau khi tổng hợp - 39 -

viii


Hình 4-5 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 1 - 41 -

Hình 4-6 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 2 - 41 -


Hình 4-7 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 3 - 41 -

Hình 4-8 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 4 - 42 -

Hình 4-9 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 5 - 42 -

Hình 4-10 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 6 - 42 -

Hình 4-11 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 7 - 43 -

Hình 4-12 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 8 - 43 -

Hình 4-13 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 9 - 43 -

Hình 4-14 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 10 - 44 -

Hình 4-15 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 11 - 44 -

Hình 4-16 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 12 - 44 -


Hình 4-17 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 13 - 45 -

Hình 4-18 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 14 - 45 -

ix


Hình 4-19 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 15 - 45 -

Hình 4-20 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 16 - 46 -

Hình 4-21 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 17 - 46 -

Hình 4-22 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 18 - 46 -

Hình 4-23 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 19 - 47 -

Hình 4-24 Đồ thị thể hiện kết quả so sánh giữa ngưỡng so khớp và tỉ lệ so khớp của
phương pháp đề xuất – Tập ảnh 20 - 47 -

Hình 4-25 Ảnh không nhiễu (trái) và ảnh nhiễu tạo thành các đặc trưng giả (phải)
của cùng ngón tay - 49 -


Hình 5-1 Đồ thị thể hiện số lượng ánh xạ tìm được của mỗi tập ảnh trong quá trình
kiểm thử - 51 -

Hình A-1 Giao diện bắt đầu của chương trình - 54 -

Hình A-2 Hướng dẫn chọn tập ảnh cần tổng hợp - 55 -

Hình A-3 Chọn và mở tập ảnh cần tổng hợp - 55 -

Hình A-4 Kết quả tìm kiếm tập tham số - 56 -

Hình A-5 Kết quả tổng hợp ảnh vân tay - 57 -

Hình A-6 Kết quả so khớp của ảnh tổng hợp với một ảnh trong tập mẫu - 58 -

Hình A-7 Tập ảnh thô ban đầu - 59 -

Hình A-8 Tập ảnh đã qua tiền xử lý - 60 -

Hình A-9 Ảnh trung gian sau khi tổng hợp - 60 -

Hình C-1 Sơ đồ thuật giải di truyền cho bài toán đối sánh ảnh vân tay - 65 -

Hình C-2 Minh họa của
).(
ˆ
ˆ
•
e

F
(Mảnh vụn trong vùng lưu trữ (Template minutiae),
mảnh vụn của vân tay cần chứng nhận (Query minutae)). - 66 -

Hình C-3 Tam giác điểm vụn đã được gán nhãn các đỉnh - 67 -

x


Hình C-4 Sự so sánh đường cong ROC của hai hướng tiếp cận trên CSDL NIST-4 . -
69 -

Hình D-1 Bìa tạp chí IJCSI - 73 -

Hình D-2 Giấy chứng nhận bài báo đã được đăng - 74 -


- 3 -


Chương 1 . TỔNG QUAN
1.1 Giới thiệu
Nhận dạng vân tay là một trong những phương pháp sinh trắc học phổ biến và có độ
chính xác cao nhờ vào tính duy nhất, sự bất biến của các đặc trưng mẫu vân tay ứng
với từng đối tượng. Mặc dù kỷ thuật này đã được sử dụng trong nhiều ứng dụng
thực tế nhưng các vấn đề của nó vẫn chưa được giải quyết triệt để đặc biệt đối với
các ảnh vân tay kém chất lượng và mất thông tin.
Có hai hệ thống nhận dạng vân tay: chứng thực ảnh vân tay và nhận diện ảnh vân
tay. Trong hệ thống chứng thực ảnh vân tay, kết quả là đúng hoặc sai giữa ảnh
chứng thực và ảnh đã đăng ký. Trong hệ thống nhận diện ảnh vân tay, kết quả là

một danh sách các ảnh vân tay đồng dạng. Nhìn chung, giai đoạn quan trọng ảnh
hưởng đến tính chính xác của cả hai hệ thống là giai đoạn so khớp giữa các ảnh. Có
rất nhiều công trình nghiên cứu với mục đích tăng độ chính xác của giai đoạn này
([13], [15], [16]). Các thuật toán so khớp có thể phân thành 3 nhóm chính: (1) đối
sánh dựa trên sự tương quan, (2) đối sánh dựa trên đặc trưng đường vân và (3) đối
sánh dựa trên các đặc trưng điểm vụn.
1.2 Vài nét sơ lược về lịch sử khoa học nhận dạng vân tay
Con người đã sử dụng vân tay vào việc xác minh đặc trưng riêng của mỗi cá nhân
cách đây rất lâu. Tuy nhiên các bằng chứng này chỉ cho thấy người xưa đã quan tâm
đến những đặc trưng duy nhất của vân tay nhưng chưa xem xét nghiên cứu một
cách khoa học và có hệ thống. Đến cuối thế kỷ 16, khoa học vân tay hiện đại được
khởi xướng. Năm 1788, Mayer đã nghiên cứu trên phương diện giải phẩu học của
vân tay và đưa ra một số lượng lớn các đặc tính của đường vân được nhận biết và
định tính. Năm 1809, Thomas Bewick đã bắt đầu sử dụng vân tay của mình như một
nhãn hiệu đã đăng ký của mình và sự kiện này được xem là một trong những cột
- 4 -


mốc quan trọng nhất của ngành khoa học nghiên cứu về vân tay. Purkinje đã đưa ra
một cơ chế phân lớp ảnh vân tay vào năm 1823. Cơ chế này dựa vào cấu trúc của
các đường vân khác nhau và đã phân ra gồm chín lớp. Năm 1864, Nehemiah Grew
đã công bố một báo cáo khoa học đầu tiên một cách hệ thống về nghiên cứu các cấu
trúc đường vân, rãnh vân và tuyến mồ hôi trên vân tay. Từ đó nhiều nhà khoa học
trên thế giới đã tập trung nghiên cứu về vân tay. Năm 1899, Edward Henry đã xây
dựng “Hệ thống Henry” nhằm phân lớp ảnh vân tay đây là một bước tiến quan trọng
trong ngành nhận dạng vân tay. Đầu thế kỹ 20, cơ chế hình thành vân tay đã được
nghiên cứu và hiểu rõ. Nhận dạng vân tay được chính thức chấp nhận là một
phương pháp để nhận dạng cá nhân có hiệu quả và là một chuẩn được sử dụng trong
các thủ tục pháp lý. Các cơ sở dữ liệu ảnh vân tay đã được hình thành để thực hiện
nhiệm vụ quản lý nhân thân và tội phạm. Các cơ sở dữ liệu này ngày cành lớn một

cách nhanh chóng khiến cho việc nhận dạng vân tay bằng phương pháp thủ công
gần như không thể thực hiện được. Vì lý do này, người ta bắt đầu nghiên cứu và
phát triển các hệ thống nhận dạng tự động. Nhiều nhà khoa học tham gia vào nghiên
cứu các phương pháp nhận dạng vân tay khác nhau, nhằm nâng cao độ chính xác
của hệ thống chứng thực, nhận dạng vân tay và nhiều công trình nghiên cứu khoa
học về chứng thực, nhận diện vân tay khác được đề xuất.
1.3 Các đặc trưng của vân tay
Theo các kết quả nghiên cứu, vùng da trên ngón tay là một cấu trúc gồm các vùng
da lồi (đường gợn - ridge) và vùng da lõm (rãnh - valley) đan xen nhau tạo thành
các đường vân cong, xoắn mà ta hay gọi là vân tay [14].
- 5 -



Hình 1-1 Đường gợn và rãnh trên ảnh vân tay (trái) và mặt cắt của một vùng da trên ngón tay (phải)

Ảnh vân tay là ảnh của lớp biểu bì đầu ngón tay, được tạo ra khi ấn ngón tay lên
một mặt phẳng. Các đường gợn và rãnh thường xen kẻ, song song nhau nhưng đôi
lúc cũng có thể rẽ nhánh hoặc kết thúc đột ngột.
Phân tích ở mức tổng quát, vân tay bao gồm một hoặc nhiều vùng mà tại đó các
đường gợn tạo nên những hình dạng riêng biệt. Các vùng này có thể chia làm 3 loại:
vòng (loop), delta và xoắn (whorl). Một số thuật toán so khớp thực hiện canh chỉnh
ảnh vân tay dựa trên điểm trung tâm gọi là điểm lõi (core - điểm cao nhất của
đường gợn trong cùng).

Hình 1-2 Các vùng đặc biệt (hình vuông trắng) và điểm core trong ảnh vân tay

- 6 -



Xét ở mức chi tiết, một đặc trưng quan trọng gọi là điểm vụn (minutiae) được phát
hiện trong ảnh vân tay. Nó được tạo ra tại những vị trí mà ở đó, đường gợn và rãnh
rẽ nhánh hoặc kết thúc đột ngột. Đây là một đặc trưng quan trọng trong việc đối
sánh vân tay. Mỗi mảnh vụn được biểu diễn bởi toạ độ x,y và góc giữa đường gợn
tại vị trí điểm vụn và trục nằm ngang


Hình 1-3 (a) Điểm vụn dạng kết thúc đột ngột (terminal) (b) Điểm vụn dạng rẽ nhánh (c) các điểm vụn
trên cùng ảnh vân tay

1.4 Sinh trắc học và ứng dụng
Sinh trắc học là công nghệ phân tích và đo lường các đặc điểm cơ thể con người
như dấu vân tay, võng mạc mắt và tròng đen, mẫu giọng nói, bàn tay, gương mặt,
dáng đi, gen, chữ ký và được ứng dụng nhiều cho mục đích chứng thực. Các đặc
điểm sinh trắc học là duy nhất đối với mỗi người, không thể bị quên, hay bị mất và
việc xác thực một người cần có sự xuất hiện của người đó. Do đó, sinh trắc học là
đáng tin cậy hơn so với phương pháp truyền thống. Trong các đặc điểm này, hệ
thống nhận dạng tự động dựa vào đặc điểm vân tay có chi phí thấp và rất đáng tin
cậy.



- 7 -


1.5 Các bước xử lý trong hệ thống chứng thực vân tay tự động
Nhìn chung, các hệ thống chứng thực ảnh vân tay tự động thường bao gồm các
bước sau:

Hình 1-4


Các bước xử lý trong hệ thống chứng thực vân tay tự động
1.5.1 Tiền xử lý ảnh vân tay
Một ảnh vân tay khi đưa vào hệ thống qua một số giai đoạn trước khi các đường vân
được làm mỏng và rút trích các đặc trưng minutiae. Đầu tiên là vùng vân trong ảnh
vân tay phải được xác định. Tiếp theo đó, một số thao tác như: chuẩn hoá đường
vân, ước lượng, tính khoản cách đường vân sẽ được thực hiện và cuối cùng là tăng
cường ảnh. Đây là một bước quan trong trong giai đoạn tiền xử lý
Hiệu quả thực hiện của các thuật toán trích chọn đặc trưng và đối sánh sẽ phụ thuộc
rất nhiều vào chất lượng của ảnh vân tay đầu vào. Trong các ảnh vân tay chất lượng
thấp, cấu trúc đường vân sẽ không được rõ ràng vì thế việc phát hiện và trích chọn
đường vân cũng như các chi tiết đặc trưng sẽ gặp nhiều khó khăn, đồng thời có thể
sẽ dẫn đến một số lỗi như tạo ra các điểm chi tiết đặc trưng giả, bỏ sót một số chi
tiết đặc trưng thật, định vị sai vị trí các chi tiết đặc trưng. Vì thế nhằm làm tăng hiệu
- 8 -


quả và độ tin cậy của các hệ thống nhận dạng vân tay, thuật toán nâng cao chất
lượng ảnh có thể được sử dụng.

Hình 1-5 Ảnh gốc và ảnh sau khi được tăng cường
Đối với các loại ảnh nhập là ảnh vân tay lăn mực hoặc ảnh vân tay dấu vết thì bước
thực hiện nâng cao chất lượng ảnh là rất cần thiết nhằm khắc phục các sai sót tồn tại
trong các loại ảnh này. Tuy nhiên đối với các hệ thống sử dụng ảnh vân tay quét
trực tuyến thì có thể không cần dùng các thuật toán này vì chất lượng ảnh kết quả
thu được từ các phương pháp này sẽ có chất lượng khá tốt, đủ đáp ứng yêu cầu của
hệ thống.
1.5.2 Làm mỏng đường vân
Sau giai đoạn tăng cường ảnh, ảnh vân tay được làm mỏng cho đến khi độ dày
đường gợn bằng 1 pixel. Rosenfeld và Kak [17] đưa định nghĩa 8-simple để chỉ tính

chất của 1 pixel P có thể bị xoá mà không làm mất tính liên thông các pixel trong
lân cận 8 với P, nói cách khác, các pixel trong lân cận 8 với P vẫn liên thông với
nhau mà không cần có P. Giá trị của từng pixel trong ảnh là 0 hay 1 sẽ dựa trên
vùng lân cận 8 của pixel đó.

Hình 1-6 Tính chất 8-simple của pixel P không phải 8-simple (trái), 8-simple (phải)
- 9 -




Hình 1-7 Ảnh trước (trái) và sau (phải) khi làm mỏng
1.5.3 Rút trích đặc trưng
Để có thể xác định chính xác 2 ảnh vân tay khác nhau có phải xuất phát từ cùng một
ngón tay hay không thì nhất thiết phải dựa trên những đặc trưng bất biến và có tính
duy nhất. Có nhiều loại đặc trưng được sử dụng nhưng nhìn chung thì có thể phân
chúng dưới 2 loại: đặc trưng toàn cục và đặc trưng cục bộ. Đặc trưng toàn cục là các
đặc tính mang tính tổng thể của ảnh vân tay và thường được xác định bằng cách
xem xét toàn bộ ảnh vân tay. Đặc trưng cục bộ thường là một tập bao gồm nhiều
thành phần, mỗi thành phần được trích chọn ra từ một phạm vi ảnh vân tay giới hạn.
Các đặc trưng toàn cục thường được dùng để tạo chỉ mục cho một cơ sở dự liệu vân
tay trong khi các đặc trưng cục bộ được dùng để đối sánh hai ảnh vân tay. Đặc trưng
toàn cục quan trọng được sử dụng là lớp của ảnh vân tay. Mẫu hình dạng tổng thể
của ảnh vân tay có thể được phân thành một số lượng hữu hạn nhỏ cá lớp khác
nhau. Đặc trưng cục bộ được sử dụng trong hầu hết các trường hợp là các điểm vụn
(minutiae). Các điểm vụn trên một ảnh vân tay có thể tạo nên duy nhất của ảnh vân
tay đó, chứa đựng nhiều thông tin đặc trưng cá biệt cho từng cá nhân. Loại chi tiết
đặc trưng được sử dụng phổ biến bao gồm điểm kết thúc và điểm rẽ nhánh. Ngoài ra
thông tin của một điểm chi tiết đặc trưng còn có thể mang một số thuộc tính khác
như hướng của đường vân tại vị trí đó. Đặc trưng cục bộ dựa trên vị trí của các

tuyến mồ hôi cũng được nghiên cứu và sử dụng, tuy nhiên vì do thông tin loại này
khó thu nhận về mặt kỹ thuật nên độ chính xác và hiệu quả mang lại không cao.
- 10 -



Hình 1-8 (a) ảnh ban đầu (b) minh họa đặc trưng được rút trích từ a
Phương pháp rút trích đặc trưng phổ biến nhất hiện nay là phương pháp Crossing
Number (CN) [14]. Phương pháp này do 2 tác giả Arcelli và Baja giới thiệu vào
năm 1984. Phương pháp này sử dụng cấu trúc của các đường gợn trong ảnh vân tay
đã được làm mỏng. Các mảnh vụn sẽ được rút trích dựa trên lân cận 8 của các pixel
trên các đường gợn bằng cách sử dụng cửa sổ 3x3. Và giá trị CN được tính bằng
một nửa tổng số lần chuyển tiếp màu (trắng và đen) giữa các cặp pixel kề nhau
trong lân cận 8. Với từng pixel trên đường gợn, giá trị CN của pixel P được tính
theo công thức sau:
||
1
8
2
1
)(
1+
−
=
=
∑
ii
PP
i
PCN


(1.1)
với P
i
(i = 1 8) là giá trị độ xám của pixel i trong lân cận 8 của pixel P.
P8 P1 P2
P7
P
P3
P6 P5 P4
- 11 -


+ Nếu CN(P) = 1 : pixel p là điểm kết thúc (endings)
+ Nếu CN(P) = 3 : pixel p là điểm rẽ nhánh (bifurcations)
+ Nếu CN(P) = 2 hay CN(P) > 3 : pixel p không phải là điểm minutiae.

1.5.4 Chứng thực vân tay
Sau quá trình rút trích đặc trưng, ảnh mẫu và ảnh cần chứng thực được đại diện bởi
các tập dữ liệu đặc trưng. Như vậy, thay vì chứng thực trên ảnh vân tay, chúng ta sẽ
thực hiện kiểm tra xem hai tập dữ liệu này có cùng xuất phát từ cùng một ngón tay
hay không. Nếu gọi S là độ tương đồng của hai tập dữ liệu thì việc hai tập dữ liệu
này có xuất phát cùng một ngón tay không sẽ phụ thuộc vào S có lớn hơn ngưỡng T
cho trước hay không
Tuy nhiên trong quá trình lấy mẫu và ảnh truy vấn, hai ảnh này thường có nhưng sai
lệch tuyến tính ( độ co giản, lệch nhau về vị trí hoặc xoay v.v ) và có thể do thiết bị
lấy mẫu kém chất lượng mà thông tin bị mất mát. Do đó, trong giai đoạn này, ngoài
việc thực hiện thao tác canh chỉnh hai ảnh sao cho độ tương đồng là cao nhất, ta cần
khắc phục thông tin mất mát. Vì vậy, phương pháp chứng thực phải đáp ứng được
các yêu cầu trên

Có một số phương pháp khác nhau để thực hiện việc canh chỉnh giữa 2 ảnh vân tay
nhưng điển hình là phương pháp dùng một phần của đường vân cộng với thông tin
về vị trí của các điểm chi tiết đặc trưng, hướng của chi tiết đặc trưng không đóng

Hình
1
-
9

M
inh h
ọa giá trị Crossing Number
đ
ối với từng loại
đ
ặc tr
ưng

- 12 -


một vai trò quan trọng trong giai đoạn này vì giá trị của chúng thường bị nhiễu.
Ngoài ra do tác động của nhiễu nên sẽ có sự tồn tại của các chi tiết đặc trưng giả
hoặc sự biến mất của một số chi tiết đặc trưng thật, đồng thời vị trí của các điểm chi
tiết đặc trưng cũng có thể bị sai lệch nhau một ít. Vì thế thuật toán đối sánh sẽ yêu
cầu cần phải có khả năng thích ứng với các yếu tố trên trong quá trình tìm và đối
sánh từng cặp chi tiết đặc trưng đối ứng trước khi đưa ra một chỉ số độ đo cuối
cùng.
1.6 Đóng góp của luận văn
Luận văn đề xuất phương pháp xác thực ảnh vân tay dựa trên mô hình tổng hợp

mẫu vân trên cơ sở lý thuyết của thuật giải di truyền trong bài toán đối sánh ảnh vân
tay được trình bày trong [5],[16]. Từ các ảnh mẫu kém chất lượng, mất mát thông
tin ban đầu qua mô hình tổng hợp sẽ tạo ra một không gian ảnh mới đại diện cho tập
ảnh phục vụ cho giai đoạn so khớp. Đối với những phương pháp so khớp thông
thường, nếu vùng giao nhau của ảnh mẫu và ảnh truy vấn quá nhỏ, việc so khớp sẽ
kém hiệu quả ( tỉ lệ nhận dạng thấp, không so khớp được ) . Chẳng hạn như trong
điều tra tội phạm, việc lấy dấu vân tay của đối tượng tại hiện trường vụ án là rất
khó, ảnh kém chất lượng và vùng vân không nằm ở vị trí chuẩn ( lệch sang trái hoặc
sang phải quá nhiều v.v ) làm cho ảnh vân tay thu được và vân tay mẫu được lưu
trữ có thể giao nhau rất ít dẫn đến so khớp không chính xác và không tìm được đối
tượng. Mục đích của việc tổng hợp mẫu vân là tạo ra một không gian ảnh mới rộng
hơn từ các không gian ảnh mẫu cũ, chứa nhiều thông tin hơn nhằm nâng cao độ
chính xác cũng như khả năng nhận diện trong bài toán đối sánh khắc phục nhược
điểm của các phương pháp so khớp đối với các ảnh vân tay kém chất lượng, mất
mát thông tin . Thực nghiệm được tiến hành trên cơ sở dữ liệu vân tay chuẩn thế
giới - cơ sở dữ liệu FVC2004, DB4 tập A và kết quả thực nghiệm cho thấy phương
pháp đề xuất là khả thi.
- 13 -


Chương 2 . TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP ĐỐI
SÁNH ẢNH VÂN TAY
2.1 Giới thiệu
Đối sánh hai ảnh của dấu vân tay là bước quan trọng nhất trong quá trình nhận dạng
dấu vân tay. Hệ thống này hoạt động dựa theo những nguyên tắc sau: trước hết ảnh
dấu vân tay được đưa vào hệ thống và sau đó đối sánh trên cơ sở dữ liệu mẫu. Kết
quả của việc đối sánh là ảnh vân tay đầu vào có phù hợp với ảnh vân tay trong cơ sở
dữ liệu mẫu hay không. Có rất nhiều nghiên cứu liên quan đến bài toán so khớp ảnh
vân tay, và có nhiều giải pháp đã được đề xuất [13], [15], [16]. Trong chương này,
chúng tôi trình bày sơ lược khảo sát một số phương pháp đối sánh ảnh vân tay nhằm

định hướng lựa chọn kỹ thuật cho đề tài nghiên cứu. Nhìn chung, thuật toán đối
sánh ảnh vân tay được chia thành các hướng tiếp cận như sau: (1) Đối sánh dựa trên
sự tương quan (2) Đối sánh dựa trên cơ sở đặc trưng đường vân (3) Đối sánh dựa
trên cơ sở mảnh vụn. Chi tiết của từng hướng tiếp cận được trình bày ở các phần sau
2.2 Các thuật toán đối sánh dựa trên sự tương quan (Correlation-based
Matching)
Đối sánh dựa trên cơ sở sự tương quan, đối sánh trực tiếp giữa hai ảnh vân tay thì
phải được thực hiện bằng cách hai ảnh vân tay chồng lên nhau chính xác về vị trí,
góc quay. Những yếu tố tương đồng được xem như kết quả đối sánh của ảnh vân
tay. Nói cách khác giá trị tương quan là những yếu tố tương đồng giữa hai ảnh

- 14 -


2.2.1 Thuật toán của tác giả Davide Maltoni và các cộng sự [14]
2.2.1.1 Hướng tiếp cận
Gọi T là biểu diễn của ảnh mẫu và I là biểu diễn của ảnh đầu vào, thì ta có công
thức tính độ khớp giữa 2 ảnh như sau [13]:
SSD(T,I)= ||T-I||
2
= (T-I)
T
(T-I)= ||T||
2
+ ||I||
2
- 2T
T
I (2.1)
Trong đó ||T||

2
và ||I||
2
là các hằng số. Vì vậy, sự khác biệt giữa ảnh mẫu và ảnh đầu
vào là nhỏ nhất khi độ tương quan chéo (CC) giữa T và I lớn nhất:
CC(T,I)=T
T
I (2.2)
Vì ảnh thu nhận đầu vào I có thể bị dịch chuyển và xoay so với ảnh mẫu T của cùng
một ngón tay. Do đó, để tính được độ tương quan chéo tốt nhất, ta cần phải biến đổi
dịch chuyển x và y, quay ảnh một góc θ với tâm quay là tâm của ảnh đầu vào
để gần giống nhất với ảnh mẫu T. Sau khi biến đổi ảnh đầu vào, ta có ảnh I(x,
y, θ). Tiếp theo, tính độ tương đồng giữa 2 ảnh theo công thức:

),(),(
),,(
,,
θ
θ
yx
yx
ITCCMaxITS
∆∆
∆∆
=
(2.3)
2.2.1.2 Nhận xét
Để tính độ tương đồng giữa 2 ảnh vân tay theo hướng tiếp cận này hiếm khi dẫn đến
kết quả có thể chấp nhận được vì một số nguyên nhân sau:
- Do ảnh vân tay bị bóp méo tạo nên khác biệt đáng kể về cấu trúc tổng quát

trong các ảnh vân tay của cùng một ngón tay.
- Do điều kiện của da tay, áp lực ấn làm thay đổi độ sáng, độ tương phản, và
độ dày của vân trong các ảnh vân tay khác nhau của cùng một ngón tay.
- Chi phí tính toán của phương trình trên rất lớn.
2.2.2 Thuật toán của tác giả Abdullah [6]
Nhằm khắc phục những nhược điểm của thuật toán do tác giả Davide Maltoni và
các cộng sự [14] đề xuất ở trên. Abdullah, 2007 [6] đã đề xuất một hướng tiếp cận
mới dựa vào điểm tham chiếu. Điểm tham chiếu được xác định là điểm trung tâm