Trờng Đại học Bách Khoa Hà Nội
Khoa Công Nghệ Thông Tin

báo cáo
thực tập chuyên ngành
Đề tài: tìm hiểu về bài toán nhận dạng
vân tay

Giáo viên hớng dẫn:P.Gs-T.s Nguyễn Thanh Thuỷ
Sinh viên thực hiện:
Lớp:

Hà Nội 6-2004


Báo cáo thực tập chuyên ngành

Lời cảm ơn
Báo cáo thực tập trên là kết quả em học hỏi đợc sau một thời gian đợc
thực tập tại Trung tâm tính toán hiệu năng cao Trờng đại học Bách Khoa
Hà Nội .Trong đợt thực tập vừa rồi ,em đã nhận đựoc nhiều sự giúp đỡ của
các thầy cô ,và các anh chị trên trung tâm.
Em xin gửi lời cảm ơn chân thành nhất tới Thầy giáo Phó giáo sTiến sỹ Nguyễn Thanh Thuỷ trởng bộ môn Các hệ thống thông tin ,trờng
đai học Bách Khoa Hoà Nội Giám đốc trung tâm,đã cho em cơ hội đợc
thực tập tai trung tâm .Đồng thời thầy cũng là ngời đa ra ý tởng ,định hớng
cho em.
Báo cáo thực tập này là kết quả thu nhận ban đầu ,em rất hi vọng
trong thời gian tới sẽ phát triển đợc các ý tởng còn dang dở.

đặt vấn đề
hiện nay các bài toán định danh một cá nhân đang đợc rất nhiều nhà

S dng trong lnh vc an ninh: S dng trong vic sn bt ti phm.
I.Mô hình chung của một hệ thống nhân dạng vân
tay:
Sau thế chiến thứ 2 ,khi có máy tính điện tử ra đời ngời ta bắt đâu xây
dựng các hệ thống nhận dạng vân tay tự động ( Automatic fingerprint
Identification Systems ) gọi tắt là các hệ thống AFIS. Các hệ thống này
ngày càng đợc hoàn thiện hơn cả về phần cứng ( các máy quét vân tay ,các
máy xử lý chuyên dụng ) và về phần mềm ( các thuật toán nhận dạng vân
tay ,tìm kiếm ảnh vân tay trong cở sở dữ liệu cỡ lớn , các thuật toán phân
lớp.) Bên cạnh đó các cở sở dữ liệu lớn và rất lớn tầm cỡ quốc gia và
quốc tế đang đợc xây dựng.

Lớp Tin-Pháp K44

3


B¸o c¸o thùc tËp chuyªn ngµnh

H×nh 1. m« h×nh chung cña hÖ thèng nh©n d¹ng v©n tay
Có thể nói, mọi hệ thống xử lý vân tay tự động đều có sơ đồ tương tự
như sơ đồ minh hoạ trên hình 1. Hệ thống gồm các môđun chính sau đây:
• Làm nổi đường biên ảnh và tăng cường chất lượng ảnh
(Image Enhancement): Bước này có ý nghĩa lớn trong việc xử lý vân tay
do chất lượng của các ảnh vân tay phụ thuộc nhiều vào quá trình lấy mẫu
ảnh cũng như trạng thái của da tay tại thời điểm lấy mẫu. Các ảnh lấy
bằng mực (lăn tay) hay lấy được trên các vật dụng có chất lượng kém hơn
so với các ảnh thu được từ các máy quét chuyên dụng. Khi tay khô, ướt,
dính dầu hay thậm chí là khi ta lấy mẫu ở các vị trí khác nhau cũng thu
được các ảnh vân tay tương đối khác nhau (nếu chỉ quan sát bằng mắt

Vic i sỏnh cỏc nh võn tay l quỏ trỡnh tỡm kim trong c s d liu cú
sn, vỡ vy thng s dng cỏc heuristic tỡm kim d dng v nhanh
chúng hn. Cú nhiu kiu heuristic khỏc nhau. Hin nay, ngi ta thng
tỡm kim võn tay vi mt chớnh xỏc nht nh v kt qu tr v l mt
danh sỏch cỏc võn tay c sp xp theo giỏ tr tng ng.
Kim tra li bng phng phỏp th cụng (Manual
Verification): Nh ó núi trờn, nh võn tay b nh hng nhiu do cỏc
yu t mụi trng. Do ú, ngi ta thng tỡm kim ra mt danh sỏch hu
hn cỏc ng c viờn trong c s d liu. Vic kim tra li cui cựng c
thc hin th cụng xỏc nh nhn dng trong cỏc ng c viờn ú. õy
l pha tu chn ca h thng x lý võn tay t ng.
Tu thuc vai trũ, chc nng, mc ớch ca tng h thng c th, mt
s mụun s c chỳ trng hoc loi b. Mi mụun cng c thit k
v ci t rt khỏc nhau, to nờn s a dng cho th trng cỏc h thng
x lý võn tay t ng hin ti.
II.Tiền xử lý và trích trọn các đặc trng

Lớp Tin-Pháp K44

5


Báo cáo thực tập chuyên ngành
Trên thc tế các mẫu vân tay thu đơc không phải lúc nào cung đợc nh mong
muốn .Vd :các mâu vân tay thu đợc tại hiện trờng (thờng mờ ,chồng chéo
lên các vật thể khác ..),các mẫu vân tay lăn mực chỉ đợc một phần .
Do đó trớc khi trích trọn các đăc trng tổng thể(Global feature ) ,đặc trng
cục bộ ( Local feature) và các đặc trng khác ,chúng ta phải trải qua một số
công đoạn xử lý ảnh nh:
+ lọc ảnh

võn tay cn nhn dng hay nh võn tay vo) vi mt nh cú sn trong c
d liu (gi l nh mu). T ú a ra mc ging nhau ca nh vo so
vi nh mu. V cui cựng tr li cho cõu hi hai nh võn tay cú phi
cựng mt võn tay hay khụng

Lớp Tin-Pháp K44

7


B¸o c¸o thùc tËp chuyªn ngµnh

Hình 4: (a) và (b) là hai ảnh của cùng một vân tay
(c) và (d) hai ảnh của hai vân tay khác nhau
Từ mô hình của hệ thống, ta nhận thấy pha đối sánh được thực hiện
sau pha trích chọn đặc trưng. Điều này có nghĩa là một ảnh vân tay cần đối
sánh trước tiên phải được trích ra các thuộc tính. Như vậy việc đối sánh
hai ảnh vân tay được đưa về việc đối sánh hai tập thuộc tính Cũng chính
vì vậy pha đối sánh phụ thuộc rất nhiều vào pha trích chọn đặc trưng
Hiện nay trên thế giới có rất nhiều kỹ thuật đối sánh vân tay, nhưng
nhìn chung quá trình đối sánh ảnh vân tay gồm hai giai đoạn chính: Căn
chỉnh (Alignment) và Đối sánh dựa trên kết quả căn chỉnh (Matching)

Hình 5: Sơ đồ khối của quá trình Đối sánh

Líp Tin-Ph¸p K44

8



Neural

Xây dựng hệ
toạ độ trong

Đối sánh có
căn chỉnh

Đối sánh trên hai
tập minutia và
các thông tin
khác

Đối
sánh
trên
hai
tập minutia

Hình 6 : Các kĩ thuật đối sánh

1.Các kĩ thuật đối sánh có căn chỉnh :

Lớp Tin-Pháp K44

9


Báo cáo thực tập chuyên ngành
Với cách tiếp cận này ,đầu vào là các tập minutia và có thể có các

-do sử dụng khối giới hạn có kích thớc thay đổi nên giải
thuật trên đối sánh đợc các ảnh vân tay có biến dạng khác nhau.
-Ngoài việc sử dụng các minutia ,giải thuật còn sử dụng
thông tin về đờng vân .Cách tiếp cận này làm tăng độ chính xác khi đối
sánh.
+Nhợc điểm :
-Phải lu trữ nhiều thông tin
-Trong quá trình căn chỉnh phải tính khối lợng giới hạn cho
từng điểm minutia trong tập mẫu ,do đó thời gian đối sánh tăng.
*Giải thuật đối sánh dựa trên sự tăng cờng lỗi: (Fingerprint matching
based on error propagation ).
Đây là thuật toán của Ying Hao ,Tieniu Tan ,Yunhong Wang .
Do nhiễu và sự co dãn khoong tuyến tính có thể làm cho quá trình căn
chỉnh không chính xác .Đồng thời ta không thể biểu diễn nhiễu và sự co
dãn không tuyến tính này nh là thuộc tính của minutia .Thuât toán này
gồm ba bớc chính :
-Mỗi minutia trong tập mẫu đợc đối sánh với các minitia
trong tập vào .
-Những cặp minutia trong quá trình đối sánh có kết quả nhỏ
hơn ngỡng sẽ đợc dùng vao MatchedSet
-Điều chỉnh các cặp minutia không khớp .
Giống nh giải thuật trên ,giải thuật này sử dụng thông tin về đờng vân để
xác định hai minutia có khớp nhau không .Tuy nhiên giải thuật này đờng
vân đợc chia thành hai loại tơng ứng với điểm đờng vân có điểm kết thúc
và đờng vân rẽ nhánh .

Lớp Tin-Pháp K44

10


Arun Ross,Sali Prabhakar.
*Giải thuật đối sánh nhanh (Fast algorithm for point matching) của
S-H .Chang ,F-h.Cheng.

2.Kỹ thuật đối sánh không căn chỉnh :

Với cách tiếp cận trên ,trớc khi đối sánh hai tập mẫu phải đợc căn chỉnh
.Đây chính là pha gây tốn kém chi phí nhiều nhất trong thuật toán đối sánh
.Để có thể giảm thời gian tính toán ,cần giảm nhẹ bớc căn chỉnh này. Hiện
nay ,có hai phơng pháp chính là:
Dùng mạng Neural ,và xây dụng hệ toạ độ trong.
Tuy nhiên cả hai cách tiếp cận này đều khá phức tạp và khó cài đặt.
*Kĩ thuật sử dụng mạng Neural :
Thông tin đa vào đối sánh là các trờng hớng ,FingerCode hoặc các minutia
theo cách tiếp cận của V.Vinod and S.Ghose.
*Kĩ thuật xây dựng hệ toạ độ trong:
H to trong (Intrinsic Coordinate System) c xỏc nh t ma
trn c trng hng v cỏc im n. Nú cú mt trc to chy song
song vi cu trỳc ca cỏc ng võn trong nh võn tay, trc cũn li vuụng
gúc vi cỏc ng võn.
Lớp Tin-Pháp K44

11


B¸o c¸o thùc tËp chuyªn ngµnh
Trước hết, người ta tiến hành phân vùng ảnh vân tay nhờ đặc trưng
hướng, điểm tâm và điểm tam giác. Có thể dễ dàng rút ra luật phân vùng
từ hình minh hoạ 2.14a. Từ điểm tâm, ta vẽ đường song song với đường
vân tại đó. Từ điểm tam giác, ta vẽ các đường vuông góc với các đường

õy l mt cỏch tip cn rt mi i vi bi toỏn nhn dng võn tay (cụng
b nm 2001). Kt qu th nghim ca cỏc tỏc gi cho thy thụng thng,
to vuụng gúc vi c trng hng c bo ton chớnh xỏc sau mi
phộp quay v phộp dch chuyn, tuy nhiờn, to song song thỡ cú th b
thay i vựng gn tõm. Khi biu din cỏc im c trng cc b, k c
loi c trớch chn t ng v loi c chuyờn gia phỏt hin, kt qu
cỏc cp im c biu din ging nhau lờn ti 90%. So sỏnh vi tiờu
chun i sỏnh thụng thng (hai nh tay cú khong 80% im c trng
cc b ging nhau c coi l thuc cựng mt võn tay) thỡ õy l kt qu

Hỡnh 8. Tp im c trng cc b ca 2 nh thuc cựng mt võn tay biu
din trong h to trong v kt qu i sỏnh.
Rất đáng khả quan.

Lớp Tin-Pháp K44

13