Mục lục

Mục lục............................................................................................................... i

Danh mục các hình vẽ......................................................................................iv

Danh mục một số thuật ngữ thường dùng.......................................................vi

Lời nói đầu......................................................................................................vii

1. Giới thiệu....................................................................................................... 1

2. Vân tay trong sinh trắc học........................................................................... 4

2.1. Vị trí của nhận dạng vân tay trong sinh trắc học................................................................ 4

2.2. Uniqe là một thuộc tính của vân tay..................................................................................... 5

2.3. Hình thức thể hiện và các đặc tả của vân tay....................................................................... 5

2.4. Khó khăn gặp phải khi nhận dạng vân tay.......................................................................... 7

3. Đại cương về ảnh số và xử lý ảnh trong Matlab........................................... 8

3.1. Đại cương về ảnh số .............................................................................................................. 8 3.1.1. Biểu diễn ảnh số............................................................................................................................8 3.1.2. Cơ sở về màu................................................................................................................................9 3.1.3. Chuyển đổi màu..........................................................................................................................12

3.2. Xử lý ảnh số trong Matlab..................................................................................................13 3.2.1. Histogram...................................................................................................................................13 3.2.2. Phân ngưỡng cục bộ ....................................................................................................................14 3.2.3. Biến đổi Fourier-2D rời rạc.........................................................................................................15 3.2.4. Lọc ảnh Sobel.............................................................................................................................16 3.2.5. Phát hiện biên bằng toán tử gradient............................................................................................18 3.2.6. Loang rộng và thu nhỏ đối tượng.................................................................................................20

4. Sơ đồ khối thiết kế hệ thống nhận dạng vân tay.........................................22

4.1. Các nguyên lý nhận dạng vân tay......................................................................................22

4.2. Hệ thống nhận dạng vân tay...............................................................................................23

4.3. Xây dựng hệ thống nhận dạng vân tay bằng ảnh số ..........................................................24

i

5. Tập mẫu ảnh vân tay...................................................................................26

6. Trích chọn minutiae cho đối sánh vân tay..................................................28

6.1. Chuẩn hóa ảnh đầu vào......................................................................................................29 6.1.1. Chuẩn hóa kích thước ảnh...........................................................................................................29 6.1.2. Cân bằng cường độ sáng của ảnh.................................................................................................29

6.2. Tăng cường ảnh chất lượng ảnh.........................................................................................30 6.2.1. Tăng cường ảnh bằng cân bằng histogram...................................................................................30 6.2.2. Tăng cường ảnh bằng biến đổi Fourier-2D...................................................................................31

6.3. Ước lượng orientation image và khoanh vùng ảnh vân tay...............................................32 6.3.1. Ước lượng orientation image.......................................................................................................32 6.3.2. Khoanh vùng ảnh vân tay............................................................................................................34

6.4. Trích chọn minutiae...........................................................................................................35 6.4.1. Nhị phân hóa và làm mảnh đường vân.........................................................................................36 6.4.2. Phát hiện minutiae.......................................................................................................................37 6.4.3. Ước lượng khoảng cách đường vân..............................................................................................39

6.4. Hiệu chỉnh đường vân và lọc minutiae sai.........................................................................39 6.4.1. Hiệu chỉnh đường vân và lọc minutiae sai cấp một.......................................................................39 6.4.2. Lọc minutiae sai cấp hai và tạo mã từ minutiae............................................................................41

7. Phân loại kiểu vân tay.................................................................................43

7.1. Trích chọn đặc tính.............................................................................................................44

7.2. Tạo vec-tơ đặc tính.............................................................................................................45

7.3. Khâu phân loại kiểu vân tay...............................................................................................46

8. Đối chiếu vân tay để định danh mẫu..........................................................48

8.1. Khớp mẫu hai mẫu vân tay................................................................................................49

8.2. Đối sánh vân tay..................................................................................................................50

9. Tổng kết và hướng phát triển......................................................................52

9.1. Kết quả của đồ án...............................................................................................................52

9.2. Những kiến thức bản thân thu được..................................................................................53

9.3. Những hạn chế của đồ án...................................................................................................53

9.4. Hướng phát triển................................................................................................................53

Tài liệu tham khảo..........................................................................................55

ii

Phụ lục............................................................................................................56

Danh sách các script file khác trong đồ án...............................................................................56

Các bước chạy phần mềm mô phỏng........................................................................................57

iii

Danh mục các hình vẽ

Hình-1. Một số tín hiệu sinh trắc học cơ bản..................................................... 4

Hình-2. Đóng góp của các ngành trong sinh trắc học.......................................... 4

Hình-3. Vân tay thể hiện ở cấp độ very-fine....................................................... 5

Hình-4. Vân tay thể hiện trong cấp độ global..................................................... 6

Hình-5. Hai dạng minutiae quan trọng................................................................ 7

Hình-6. Biểu diễn ảnh số .................................................................................... 8

Hình-7. Cảm nhận của các tế bào nhạy sáng trong võng mạc mắt...................... 9

Hình-8. Tổ hợp màu.........................................................................................10

Hình-9. Hệ tọa độ màu.....................................................................................11

Hình-10. Phân tích lược đồ xám.......................................................................14

Hình-11. Giá trị ngưỡng tối ưu.........................................................................15

Hình-12. Các bước thực hiện lọc ảnh trong miền tần số ...................................16

Hình-13. Các bước lọc ảnh bằng toán tử không gian........................................17

Hình-14. Biểu diễn mask..................................................................................18

Hình-15. Loang rộng đối tượng........................................................................20

Hình-16. Thu nhỏ đối tượng.............................................................................21

Hình-17. Tạo mã vân tay..................................................................................22

Hình-18. Sơ đồ khối hệ thống nhận dạng vân tay.............................................24

Hình-19. Các loại vân tay.................................................................................26

Hình-20. Thuật toán trích chọn minutiae..........................................................28

Hình-21. Tăng cường ảnh.................................................................................30

Hình-22. Ước lượng orientation image.............................................................33

Hình-23. Khoanh vùng ảnh vân tay..................................................................35

Hình-24. Thông số của hai dạng minutiae quan trọng.......................................36

Hình-25. Nhị phân hóa và làm mảnh đường vân..............................................36

Hình-26. Phát hiện minutiae.............................................................................38

iv

Hình-27. Số minutiae phát hiện được...............................................................40

Hình-28. Lọc các minutiae...............................................................................40

Hình-29. Các minutiae được trích chọn cuối để tạo mã....................................41

Hình-30. Năm kiểu vân tay trong thực tế..........................................................43

Hình-31. Sơ đồ khối mô tả thuật toán phân loại vân tay...................................44

Hình-32. Phương pháp chỉ số Poincaré.............................................................44

Hình-33. Lấy đặc tính cho phân loại.................................................................46

Hình-34. Kết quả cây quyết định của bài toán phân loại kiểu vân.....................46

Hình-35. Đường cong sai số học và kiểm tra....................................................47

Hình-36. Đối chiếu vân tay dựa trên cơ sở minutiae.........................................48

Hình-37. Khớp mẫu từng đối tượng..................................................................49

Hình-38. Thực hiện matching...........................................................................50

Hình-39. Kết quả nhận dạng.............................................................................51

Hình-40. Cửa sổ giao diện................................................................................57

Hình-41. Mở một file ảnh.................................................................................57

Hình-42. Cân bằng lược đồ xám.......................................................................58

Hình-43. Biến đổi Fourier rời rạc và cân bằng cường độ sáng..........................58

Hình-44. Nhị phân hóa ảnh...............................................................................59

Hình-45. Trường định hướng...........................................................................59

Hình-46. Segmentation.....................................................................................60

Hình-47. Phát hiện core....................................................................................60

Hình-47. Làm mảnh đường vân........................................................................61

Hình-48. Lọc minutiae.....................................................................................61

Hình-49. Hiển thị minutiae...............................................................................62

Hình-50. Đối sánh vân tay................................................................................62

v

Danh mục một số thuật ngữ thường dùng

trong nhận dạng vân tay

• Ridge: Đường vân tay trên ngón tay người. • Vallay: Đường rãnh xen kẽ hai đường vân tay. • Singular: Điểm kỳ dị của vân tay trên ngón tay ng ười, mang đặc điểm

phân loại.

• Core: Điểm “tâm” của vân tay, là một trong những điểm singular. • Minutia: Điểm đặc trưng của vân tay trên ngón tay con người. • Termination: Điểm kết thúc của đường vân, một loại minutia quan trọng. • Bifurcation: Điểm trẽ ba của đường vân, là một loại minutia quan trong. • Sweat pores: Vòng xuyến xếp liên tiếp tạo thành đường vân (thường quan

sát được khi ảnh vân tay ở độ phân giải cao: > 1000dpi).

• Orientation Image : Hình ảnh th ể hi ện các định hướng cục bộ của các

[

]

0,

p

q ij

˛ tại các điểm [i,j]. đường vân tay, bao gồm nhiều phần tử

[

]

0, 2

p

q ij

˛ . • Direction Image: Tương tự như Orientation Image nhưng

• Segmentation: Phân định giữa vùng ảnh thể hiện đường vân và vùng ảnh

nền.

• Varance field: Một các thể hiện vùng ảnh thể hiện đường vân còn thô. • Crossing number: Một phương pháp dùng để phát hiện minutiae. • Poincaré: Một ph ương pháp dùng để phát hi ện core theo tr ường vec-t ơ

và đường bao.

• Ridge map: Ảnh đen trắng chỉ thể hiện các đường vân màu tr ắng nhưng

không nhất thiết các đường vân có độ rộng đồng đều.

• Thinned ridge map : Ảnh đen tr ắng th ể hi ện các đường vân màu tr ắng

nhưng nhất thiết các đường vân có độ rộng đồng đều 1pixel

vi

Xin cảm ơn Công ty TNHH Tin h ọc và Điện tử Thăng Long cùng chú V Ũ

QUANG THÀNH đã tạo điều ki ện giúp đỡ, cho em nhi ều lời khuyên b ổ ích

trong quá trình thực tập tốt nghiệp và làm đồ án.

Hà Nội, ngày 20 tháng 5 năm 2007

Sinh viên thực hiện

Ngô Hồng Việt

viii

1. GIỚI THIỆU

1. Giới thiệu

Nhận dạng vân tay là một bộ phận của nhận dạng sinh học. Khoa học nhận dạng

vân tay cũng đã hình thành từ khá lâu. Nhưng tới thời gian gần đây, cùng với sự

ra đời của máy tính nó m ới đạt được nhiều kết quả quan tr ọng và trở thành một

trong những phương pháp sinh trắc có độ tin cậy nhất.

Ảnh vân tay dùng để nhận dạng thường bị ảnh hưởng nhiều bởi điều kiện thu

thập số liệu (hình ảnh vân tay không tr ọn vẹn, bị xoay góc, méo hay có nhi ều

nhiễu…) nên việc so sánh trực tiếp hai mẫu vân tay sẽ rất phức tạp và khó khăn.

Do đó vân tay cần lọc nhiễu, sau đó tạo mã từ một số các đặc tính của nó (có thể

phân biệt với vân tay khác) nh ằm mục đích giải quyết vấn xử lý, lưu trữ vân tay

với số lượng lớn mà vẫn đảm bảo chính xác.

Các kỹ thuật thực nhận dạng vân tay cũng có khá nhi ều. Tựu trung, quá trình

này trải qua ba công đoạn chính: thu nhận vân tay (i); trích ch ọn đặc tính vân

tay (ii); đối sánh vân tay (iii) [1]. Bởi vì ngay trong t ừng công đoạn này lại có

nhiều biện pháp khác nhau, tùy vào ng ữ cảnh và vùng ứng dụng các khâu này sẽ

thực hiện theo cách cụ thể.

Công nghệ nhận dạng vân tay ngày nay đã đạt tới độ chính xác r ất cao. Tuy

vây, các h ệ th ống nh ận dạng AFIS ( Automated Fingerprint Identification

Systems) vẫn còn nhiều mặt hạn chế. Chẳng hạn như IAFIS của FBI có cơ sở dữ

liệu lớn tới hàng tr ăm triệu vân tay, th ời gian tìm ki ếm tính bằng phút cho m ột

mẫu, độ tin cậy cao… nhưng đó là một hệ thống đồ sộ gồm nhiều máy tính xử lý

song song và gi ới hạn trong giám định hình sự. Trong ứng dụng dân sư, các hệ

thống nhận dạng thường được giới hạn ở một mức độ ít ph ức tạp hơn: số mẫu

không lớn (kho ảng vài nghìn), c ấu trúc h ệ th ống ki ểu nối ti ếp, ảnh đầu vào

không có quá nhi ều nhiễu (nhằm giảm bớt gánh nặng xử lý tính toán),… có v ậy

mới giải quyết được vấn đề chi phí đồng thời vẫn đảm bảo độ tin cây.

Đồ án này s ẽ th ực hi ện nh ận dạng vân tay bàng ảnh số theo h ướng có th ể

triển khai trong dân s ư. Chính vì vây ph ương pháp nh ận dạng là dựa trên cơ sở

phát hi ện và s ử dụng các điểm nút đặc tr ưng (g ọi là minutiae) [2]. Đây là

1

1. GIỚI THIỆU phương pháp thứ hai trong ba ph ương pháp nhận dạng được áp dụng nhiều hiện

nay [1], ch. 4. Hệ thống AFIS nói chung cũng sử dụng phương pháp này [11].

• Phương pháp th ứ nh ất, sử dụng đặc tr ưng tương quan c ủa hai m ẫu vân

tay. Xếp ch ồng tr ực ti ếp hai m ẫu này và d ựa vào t ương quan gi ữa các

pixel để tính toán s ự khác nhau gi ữa hai m ẫu. Ph ương pháp này không

thích hợp với đồ án vì đòi hỏi khối lượng tính toán lớn mà chất lượng ảnh

phải đảm tốt.

• Phương pháp thứ ba, sử dụng các đặc trưng về đường vân. Đường vân của

các mẫu được trích ra kh ỏi ảnh ban đầu rồi so sánh gi ữa chúng. Ph ương

pháp này không thích h ợp với đồ án vì nó ch ỉ thích hợp với các mẫu có

chất lượng xấu (chẳng hạn như vân tay tội phạm để lại hiện trường sau vụ

án).

Đồ án sẽ sử dụng bộ mẫu chuẩn các vân tay đã được chuẩn bị trước. Đó là

các ảnh số vân tay l ấy trong FVC200 (m ột bộ dữ liệu chuẩn quốc tế xây d ựng

bởi phòng thí nghiêm hệ thống sinh trắc, đại học Bologna).

Trong tâm của đồ án tập trung vào hai phần:

• Tạo vec-tơ đặc tính cho mục đích phân loại kiểu vân tay và cho đối sánh

vân tay (feature extraction).

• Sử dụng các điểm minutea đã trích ch ọn bước tr ước để đối sánh nh ận

dạng vân tay (minutiae matching).

Đồ án trình bày theo cấu trúc:

• Chương 1: Giới thiệu chung. • Chương 2: Vân tay trong sinh tr ắc học. Đề cập một số bộ phận của sinh

trắc học (trong đó có nhận dạng vân tay) và nh ững tính chất gì quyết định

vân tay được ứng dụng nhiều nhất trong sinh trắc học.

• Chương 3: Đại cương về ảnh và xử lý ảnh trong Matlab, trình bày khái

quát về ảnh số và một số thuật toán xử lý ảnh trong Matlab sử dụng trong

đồ án.

2

1. GIỚI THIỆU • Chương 4: Sơ đồ khối thiết kế hệ thống. Đề cập một số mô hình hệ thống

nhận dạng vân tay và xây d ựng sơ đồ kh ối hệ th ống nhận dạng vân tay

bằng ảnh số.

• Chương 5: Bộ dữ liệu ảnh sử dụng trong đồ án. Đây là bộ dữ liệu ảnh vân

tay trích ra t ừ FVC2000 (c ơ sở dữ liệu ảnh vân tay chu ẩn, hiện nay được

nhiều nhà khoa học chọn để nghiên cứu và kiểm nghiệm kết quả).

• Chương 6: Trích ch ọn đặc tính vân tay và đối sánh vân tay. Đây một

trong những công đoạn quan trọng nhất của đồ án. Giai đoạn này áp dụng

các thuật toán xử lý ảnh để tạo mã vân tay.

• Chương 7: Đối sánh vân tay. M ẫu vân tay được tạo mã t ừ minutiae ở

công đoạn trước được đối sánh trong công đoạn này.

• Chương 8: Phân loại kiểu vân tay. Trình bày về vấn đề tạo vec-tơ đặc tính

cho khâu phân loại kiểu vân tay và thực hiện phân loại kiểu vân tay.

• Chương 9: Tổng kết và hướng phát triển. Trình bày những kết quả của đồ

án, những kiến thức bản thân thu được, các h ạn chế và hướng phát tri ển

đề tài.

• Tài liệu tham kh ảo. Liệt kê một số tài li ệu dùng tham kh ảo chính trong

đồ án.

• Phụ lục. Bao gồm danh sách các script file của phân mềm mô ph ỏng và

các bước thực hiện chạy phần mềm mô phỏng nhận dạng vân tay.

3

2. VÂN TAY TRONG SINH TRẮC HỌC

2. Vân tay trong sinh trắc học

Trong phần này sẽ trình bày nh ững tiếp cận khởi đầu, như: vị trí của nhận dạng

vân tay trong sinh tr ắc học; những tính ch ất của vân tay để trở thành đối tượng

cơ bản của sinh tr ắc học; hình th ức thể hiện và đặc tả của một mẫu vân tay và

a)

b)

c)

Hình-1. Một số tín hiệu sinh trắc học cơ bản: a) giọng nói; b) đồng tử; c) chữ ký.

những khó khăn gặp phải khi nhận dạng vân tay.

2.1. Vị trí của nhận dạng vân tay trong sinh trắc học

Dựa vào tiêu chu ẩn physiological sinh tr ắc học có: dạng vân tay, m ặt, đồng tử,

giọng nói… Còn dựa vào tiêu chu ẩn behavioral sinh trắc học có: nhận dạng chữ

viết, chữ ký… Dưới đây là biểu đồ tương quan ứng dụng sinh trắc (số liệu thống

kê của International Biometric Group, 2002).

Hình-2. Đóng góp của các ngành trong sinh trắc học. (vân tay đứng vị trí hàng đầu trong các ứng dụng nhận dạng)

4

2. VÂN TAY TRONG SINH TRẮC HỌC

2.2. Uniqe là một thuộc tính của vân tay

Cho tới nay, vẫn chưa có bằng chứng xác th ực 100% vân tay trên các ngón tay

tuyệt đối mang tính cá nhân và không h ề lặp lại. Câu tr ả lời chính xác ch ỉ có

được khi đem so sánh từng mẫu vân tay của mười đầu ngón người với hơn sáu tỉ

người còn lại. Tuy nhiên khi không xét t ới phần nhỏ lẻ ấy có th ể rút ra m ột số

tính chất cơ bản của vân tay để nó trở thành phổ biến trong ứng dụng nhận dạng

và định danh con người [2, 11]:

• Tính “phổ thông”, mọi người đều có. • Tính cá nhân và không l ặp lại. Xác su ất trùng kh ớp với người khác gần

bằng không.

• Tính “bất biến”. Hình dạng tổng thể của vân tay trên các ngón tay c ủa con

người không thay đổi theo thời gian. Ngay c ả trường hợp bị chấn thưong

nhẹ, dấu vân tay vẫn có khả năng khôi phục lại.

2.3. Hình thức thể hiện và các đặc tả của vân tay

Nhằm mục đích mô tả người ta đã định nghĩa một số hình thức thể hiện vân tay.

Mỗi một trường hợp thể hiện thì sẽ có hình thức trích chọn đặc tả vân tay tương

ứng. Vì vậy, căn cứ vào ảnh vân tay đầu vào chúng ta có th ể lựa chọn được đặc

Hình-3. Vân tay thể hiện ở cấp độ very-fine: các sweat pores được khoanh tròn,

điểm vân chẽ ba (bifurcation) và vân cụt (termination) đánh dấu hình tròn.

tính cần trích chọn và dự kiến phương án nhận dạng.

5

2. VÂN TAY TRONG SINH TRẮC HỌC

Hình thức thể hiện vân tay được chia thành ba c ấp độ: global (thể hiện tổng

thể vân tay), local (thể hiện vân tay bởi một số nút đặc trưng khi đường vân làm

mảnh đến một pixel), very-fine (thể hiện bởi các vòng xuyến tạo hình nên đường

vân - sweat pores) [1], tr. 28-31, 83-85.

Đối với cấp độ very-fine thì đòi hỏi các phương tiện xử lý tốn kém cũng như

các yêu cầu đặc biệt khác mà khó có th ể ứng dụng trong dân s ự. Chẳng hạn để

trích được các pores, ảnh cần có độ phân gi ải tối thiểu 1000dpi. Sau đây sẽ tìm

a)

b)

c)

d)

e)

Hình-4. Vân tay thể hiện trong cấp độ global: a) arch; b) whorl; c) tented arch; d) left loop;

e) right loop; hình vuông đánh dấu điểm loop, hình tam giác đánh dấu điểm delta.

hiểu sâu hơn các đặc trưng vân tay ở hai cấp độ đầu.

Ở cấp độ global, đặc tr ưng vân tay liên quan nhi ều đến sự tạo hình c ủa

đường vân và các điểm kỳ dị (singular), chúng bao g ồm: loop (đường vân tạo

vòng xoáy hở), delta (đường vân tạo hình tam giác). Điểm kỳ dị có vai trò quan

trọng trong việc thực hiện phân loại vân tay và tổ chức, xây dựng cơ sở dữ liệu.

6

2. VÂN TAY TRONG SINH TRẮC HỌC

Ở mức độ cục bộ, các đặc trưng của vân tay được gọi là minutiae. Người ta

đã thống kê có t ới 150 đặc trưng loại này. Hai đặc trưng cơ bản và nổi trội hơn

a)

b)

Hình-5. Hai dạng minutiae quan trọng: a) ridge termination; b) ridge bifurcation.

cả là ride temination và ridge bifurcation (cũng được gọi tắt là minutiae)

2.4. Khó khăn gặp phải khi nhận dạng vân tay

Do điều kiện thu nh ận ảnh quy ết định nhi ều đến chất lượng ảnh thu th ập nên

nhiều khi các chi tiết trên mẫu vân tay không thể hiện rõ ràng. Có thể liệt kê một

số trường hợp dưới đây:

• Dry finger (vân tay thu nh ận trong điều kiện “khô”): ảnh thu nh ận sẽ có

nhiều chỗ đường vân bị mờ đi, đường vân bị lẫn với nền ảnh. Lực ấn của

tay nhẹ ho ặc mực in không đủ (với vân tay l ăn trên gi ấy) là các nguyên

nhân chính làm giảm chất lượng ảnh thu thập.

• Wet finger (vân tay thu nh ận trong điều kiện “ướt”): ảnh thu nh ận sẽ có

nhiều chỗ đường vân bị dính liền. Lực ấn của ngón tay quá l ớn hoặc mực

in quá nhi ều (v ới vân tay l ăn trên gi ấy) là các nguyên nhân chính t ạo

nhiễu trong trường hợp này.

• Vân tay thu nh ận trong điều kiện bị biến dạng: ảnh thu nh ận được có th ể

thể hiện rõ nét nh ưng các đường vân lại bị bóp méo không còn gi ống với

mẫu thực. Lực ấn, kéo và xê dịch tay là các nguyên nhân chính.

• Vân tay thu th ập không đầy đủ: ảnh thu th ập được chỉ có một phần vân

tay trên ngón tay. Nguyên nhân chính là do ngón tay đặt không đúng vị trí

chuẩn thu thập.

Tuy vậy trong thực tế cũng có nhiều mẫu vân tay thu thập trong điều kiện tốt

nên có chất lượng cao

7

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

3. Đại cương về ảnh số và xử lý ảnh trong Matlab

Đồ án này không xây d ựng bộ thu th ập mẫu vân tay mà s ử dụng bộ mẫu chuẩn

quốc tế FVC2000 do phòng thí nghi ệm hệ thống sinh tr ắc, đại học Bologna tạo

ra. Trong cơ sở dữ liệu ấy, các mẫu được lưu dữ dưới dạng ảnh số. Bởi vậy, quá

trình xử lý tính toán th ực hi ện đồ án ph ải làm vi ệc chính với dạng số li ệu đó.

Cho nên, trong ph ần này sẽ trình bày tóm t ắt về ảnh số và một số thuật toán xử

lý ảnh số trong Matlab.

3.1. Đại cương về ảnh số

Ảnh có th ể biểu diễn dưới dạng tín hi ệu tương tự ho ặc số. Trong ph ần sẽ tập

trung vào biểu diễn ảnh số, cơ sở về mầu và việc chuyển đổi màu.

3.1.1. Biểu diễn ảnh số

Ảnh xám cũng như các ảnh số khác là tập hợp các phần tử ảnh hay còn gọi là

j . Ảnh được bi ểu diễn nh ư một ma-tr ận hai chi ều cỡ W H·

các pixel, [, ]i , hai

j [, ] Ii

thông số này cho bi ết thông tin v ề độ rộng và chi ều cao ảnh. Giá tr ị của mỗi

phần tử của ma-tr ận biểu diễn cho mức xám hay c ường độ ảnh tại vị trí

của phần tử đó.

f(1,1)f(1,2)f(1,N)

L

f(2,1)f(2,2)f(2,N)

L

=

f

M

MM

f(M,1)f(M,2)f(M,N)

L

b)

a)

Hình-6. Biểu diễn ảnh số: a) hệ trục tọa độ trong Image Processing Toolbox;

b) ma-trận biểu diễn ảnh số

Ø ø Œ œ Œ œ Œ œ Œ œ º ß

8

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

Tùy theo yêu c ầu lưu tr ữ, các pixel sẽ được mã hóa b ằng 8-bit, 16-bit,…

tương ứng với ảnh xám 256, 65536 mức.

[

j [,]0,1 Ii

˛ Với ảnh đen trắng, các pixel này được lưu trữ bằng 1-bit. Cường độ ảnh I chỉ ] . Ứng với giá trị 0 đó là các điểm đen, có thể là một trong hai giá tr ị,

còn với giá trị 1 đó là điểm trắng.

Với ảnh màu, cách biểu diễn cũng tương tự như với ảnh xám, chỉ khác là các

giá trị tại mỗi phần tử của ma-trận biểu diễn ba màu riêng biệt gồm: đỏ (Red-R),

lục (Green-G) và lam (Blue-B). Để biểu diễn cho ba màu riêng rẽ cần 24-bit, 24-

bit này được chia thành ba kho ảng 8-bit. M ỗi khoảng này bi ểu diễn cho cường

độ sáng của một trong các màu chính.

3.1.2. Cơ sở về màu

Ánh sáng màu là tổ hợp các ánh sáng đơn sắc. Mắt người có thể cảm nhận được

một số màu nhất định nhưng lại có thể phân biệt được rất nhiều màu (trong vùng

). Cảm nh ận màu c ủa con quang nhìn th ấy, có d ải bước sóng 400750nmnm‚

người phụ thuộc vào ba thuộc tính B, H, S.

B (brightness): độ chói,

H (hue): sắc lượng,

Hình-7. Cảm nhận của các tế bào nhạy sáng trong võng mạc mắt với các màu ánh sáng phụ

thuộc vào chiều dài bước sóng ánh sáng.

S (saturation): độ bão hòa.

9

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH Trong võng m ạc mắt ng ười có các t ế bào c ảm th ụ hình nón nh ạy với ánh

sáng. Có kho ảng 6 ‚ 7 triệu tế bào lo ại này trong mắt, chúng chia làm ba nhóm

nhạy với ba màu ánh sáng khác nhau: 65% t ế bào nh ạy với ánh sáng đỏ (red),

32% tế bào nhạy với ánh sáng xanh lục (green) và 2% còn lại nhạy với ánh sáng

xanh lơ (blue).

Tổ hợp B, H, S đối với từng ánh sáng màu trong ba màu này giúp m ắt con

người có thể phân biệt được hàng ngàn màu. R, G, B còn được gọi là các màu cơ

sở.

Phân bổ phổ năng lượng của một nguồn sáng màu có bước sóng l ký hiệu là

1S ,

2S ,

3S ) mô tả bằng sơ đồ khối sau:

Hình-8. Tổ hợp màu.

)

( )C l và vi ệc tổ hợp màu theo ba màu c ơ sở (có các đường cong cảm nhận

( i Ca

l

max

Đáp ứng phổ sẽ được tính như sau trong dải bước sóng

i =

1,3 .

( ) all l= (cid:242) CSc

i

i

l

min

d ()( ) ,

k =

1,3

) ( kp x ,

x

max

Với phân phối xác xuất của ba màu nên có:

x

min

= 1 . (cid:242) pxdx () k

10

)

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

i =

1,3

( kb l ,

3

(

()( )

Giả sử ba màu cơ bản được tổ hợp theo tỉ lệ . Để tạo ra một màu

)C l sẽ bằng

b l k

p x k

= 1

k

(cid:229) có phân bố phổ năng lượng .

l 3

Thay giá trị vào phương trình về đáp ứng phổ:

=

,

maxmax l 33 == cSxpxdxxSpxdxx a ()()()()()()()( ) b albbl iikkkikki k == 11

kk

minmin

l

= 1 k l

max

l

a

(cid:230) (cid:246) (cid:229) (cid:229) (cid:229) (cid:231) (cid:247) (cid:242) (cid:242) Ł ł

= (cid:242)

i, k

()( ) Spxdx l i

k

min

l

trong đó: .

ia là hệ số tổ hợp theo công

Như vậy có thể tổ hợp màu theo phép cộng màu với

thức tổng quát sau:

=+ XRG + Baa 12 a 3

Tổ chức quốc tế về chẩn hóa màu CIE đã đưa ra một số không gian màu nh ư:

RGB, CMY, CMYK, HIS,… Trong đó mô hình RGB có vai trò quan trọng.

red

x

= ΠPgreen

blue

a)

b)

Hình-9. Hệ tọa độ màu: a) mô hình màu RGB;

b) biểu diễn điểm ảnh trong hệ tọa độ màu RGB.

Ø ø Œ œ œ Œ œ º ß

11

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

3.1.3. Chuyển đổi màu

Hệ tọa độ màu do CIE quy định như một hệ quy chi ếu và trên th ực tế không

thể biểu diễn hết các màu. Tùy thu ộc vào các ứng dụng khác nhau ng ười ta đưa

ra thêm một số hệ tọa độ khác nh ư NTSC, CMY, YIQ... phù h ợp với yêu c ầu

hiển thị màu sắc. Việc chuyển đổi giữa các không gian bi ểu diễn màu thực hiện

theo nguyên tắc sau:

= PA P

x

x

* · ,

xP : không gian biểu diễn màu ban đầu,

xP* : không gian biểu diễn màu mới,

A : ma-trận phép biến đổi.

trong đó:

Ảnh dùng trong đồ án này là ảnh xám. M ức xám là k ết quả của sự mã hóa

tương ứng một cường độ sáng c ủa điểm ảnh với một tr ị số. Giá tr ị của nó ph ụ

thuộc vào mức độ lượng tử hóa ảnh, như các ảnh dùng làm cơ sở dữ liệu đã lấy

8-bit để mã hóa ảnh (ứng với 256 mức xám, trong đó mức xám 0 là màu đen,

mức xám 255 là màu trắng).

=+ grayscaleRG

+ Baa

Khi chuyển đổi từ ảnh màu RGB sang ảnh xám có thể dùng công thức sau:

12

a 3

,

ia lần lượt như dưới đây [6].

==

=

aa 12

0,2989;0,5870;0,1140 a 3

các hệ số

12

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

3.2. Xử lý ảnh số trong Matlab

Đứng về mặt xử lý tín hi ệu nói chung và x ử lý ảnh nói riêng, Matlab là công c ụ

rất mạnh. Hầu hết các thuật toán về ảnh và xử lý ảnh đều đã được thể hiện trong

các hàm của Matlab nh ư các hàm đọc, ghi ảnh, chuyển đổi giữa các hệ màu của

ảnh, các thuật toán phát hi ện biên, tách đối tượng, khớp mẫu, các phép bi ến đổi

ảnh như xoay ảnh, chuẩn kích th ước, tịnh tiến,... Các th ư viện ngày càng được

mở rộng, các hàm ứng dụng có thể được lập bởi người sử dụng. Ứng dụng phần

mềm Matlab trong xử lý ảnh sẽ có được nhiều tiện ích và trợ giúp.

Câu l ệnh Matlab được gần với các thu ật ng ữ mô tả kỹ thuật, câu lệnh ngắn

gọn và có thể tra cứu nhanh trong chức năng Help.

Trong Matlab có nhi ều Toolbox h ỗ tr ợ các ứng dụng chuyên sâu. V ới bài

toán nhận dạng hình ảnh, các Toolbox thường được sử dụng gồm:

• Image Processing Toolbox • Image Acqusition Toolbox • Wavelet Toolbox • Signal Processing • Statistics Toolbox • Neural Network Toobox

Các thuật toán xử lý trong đồ án đều được viết bằng ngôn ngữ lập trình phần

mềm Matlab. Các chương trình có sử dụng một một số thư viện của Matlab (chủ

yếu trong Image Processing Toolbox, Statistics Toolbox). Sau đây là m ột số

công cụ xử lý và thuật toán xử lý ảnh chính được ứng dụng trong đồ án.

3.2.1. Histogram

Histogram (lược đồ xám) th ể hi ện tần suất xuất hi ện mỗi mức xám trong ảnh.

Lược đồ xám bi ểu diễn trong hệ tọa độ Oxy: trục hoành bi ểu diễn N mức xám

(tùy theo s ố bit mã hóa pixel), tr ục tung bi ểu diễn số điểm ảnh một mức xám

tương ứng.

13

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH Lược đồ xám cung cấp thông tin về phân bố mức xám của ảnh. Nó cho phép

phân tích trong kho ảng nào đó phân b ố ph ần lớn mức xám c ủa ảnh. Nếu ảnh

sáng thì lược đồ xám lệch về phía bên trái, n ếu ảnh tối thì lược đồ xám lệch về

a)

b)

c)

d)

Hình-10. Phân tích lược đồ xám: a) ảnh sáng và b) lược đồ xám của (a) lệch phải;

c) ảnh tối và d) lược đồ xám của (c) lệch trái.

bên phải so với điểm quy chiếu (giữa mức xám N).

3.2.2. Phân ngưỡng cục bộ

Phân ngưỡng với mục đích làm tăng độ tương phản các đối tượng cần quan tâm

đông thời loại bớt nhiễu. Nếu phân ng ưỡng toàn bộ ảnh nhiều khi tỏ ra không

hiệu quả, nhất là khi c ường độ sáng của ảnh không đồng đều. Phân ng ưỡng cục

bộ cũng gi ống nh ư phân ng ưỡng nh ưng ch ỉ khác ở điểm: ng ưỡng được ch ọn

thích nghi với từng vùng cục bộ của ảnh. Điều này rất có ý nghĩa trong khâu nh ị

phân hóa ảnh vân tay. Vùng c ục bộ thường dùng có th ể là các block dạng hình

vuông hay hình chữ nhật.

14

fxy (,

)

T‡

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH Ảnh xám khi phân ng ưỡng thì kết quả phân ng ưỡng đi đôi với nhị phân hóa

ảnh. Một điểm bất kỳ (x, y) thuộc ảnh f khi có thì được gọi là object

point (điểm trên nền), trường hợp còn lại gọi là background point (điểm nền).

Đối tượng ưu tiên trích ch ọn từ phân ng ưỡng không quan tr ọng là

bachground point hay object point. Đấy chỉ là các tên g ọi quy ước và chúng có

Hình-11. Giá trị ngưỡng tối ưu.

gx y (, )

thể chuyển đổi dễ dàng cho nhau nhờ biến đổi âm bản.

Kết quả phân ngưỡng được ảnh thì nó được định nghĩa liên hệ

1:(,

)

= (cid:237)

( gx y ,

0:(,

) fxy fxy )

T < T

‡ (cid:236)

(cid:238)

3.2.3. Biến đổi Fourier-2D rời rạc

Biến đồi Fourier r ời rạc trong x ử lý ảnh số nh ằm mục đích lọc lấy các thành

phần tín hi ệu ảnh có tần số tr ội. Với ảnh vân tay vùng ảnh co các đường vân

đóng vai trò làm tín hiệu có tần số trội.

fx y (,

)

x

M= 0,

1

y

N= 0,

1

Fu v (, )

- - , với và là một ảnh số cỡ M N· . Bi ến đổi Có

Fourier rời rạc của f là .

M N 1

1

)

( + / 2/ juxMvy N p

u

M= 0,

1

v

N= 0,

1

= (cid:229) ) Fuvfxy e (,)(,

=

=

0

x

0

y

- - - - - (cid:229) , , .

15

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

Bi ến đổi ngược Fourier rời rạc định nghĩa bởi công thức:

M N 1

1

)

( + / 2/ juxMvy N p

x

M= 0,

1

y

N= 0,

1

= (cid:229) fxyFuv e (,)(, )

=

=

0

u

0

v

- - - - - (cid:229) , , .

),

( f- ju v

= (,)(, ) FuvFuv e

Biến đổi Fourier rời rạc của ảnh f còn được viết dưới dạng:

Fu v (, )

),u vf (

,

trong đó là góc pha, là phổ Fourier.

Các b ước thực hiện lọc ảnh trong mi ền tần số bằng biến đổi Fourier rời rạc

Hình-12. Các bước thực hiện lọc ảnh trong miền tần số.

có thể mô tả bởi sơ đồ dưới đây.

3.2.4. Lọc ảnh Sobel

Lọc Sobel là m ột trường hợp của lọc số tuyến tính. Ngh ĩa là b ộ lọc dùng m ột

convolution-mask (cửa sổ dùng để nhân chập, gọi tắt mask), rồi lấy tổng có trọng

số các điểm lân cận với điểm ở chính gi ữa trong mask đó. Di chuy ển mask trên

toàn bộ miền tín hiệu ảnh, mỗi bước một pixel, cuối cùng thu ảnh kết quả.

16

m n·

Tổng quát, lọc tuyến tính của ảnh số f cỡ M N· 3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH với convolution-mask có cỡ

(

)

(

)

(,),

b + ,

định bởi như sau

a =+ gxywstfxsy =-=- sat

t b

(cid:229) (cid:229) ,

( a m=

)1/ 2

b

( n=

)1/ 2

x

M= 0,

1

y

N= 0,

1

Hình-13. Các bước lọc ảnh bằng toán tử không gian.

- - - - trong đó: , và , .

17

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

( +

)

(

)

z

2

Đáp ứng lọc số tại từng điểm (x,y) là R, đối với lọc Sobel sẽ là

xxi

2 78913

4

9 ==++-+ Rwzzzzzz i = 1 i

( +

)

(

)

z

2

(cid:229) ,

yyi

2 36914

7

9 ==++-+ Rwzzzzzz i = 1 i

(cid:229) ,

iz là mức xám của ảnh.

trong đó

;

a) Hình-14. Biểu diễn mask: a) các hệ số của mask cỡ 3 3·

b) các hệ số của cặp mask dùng cho lọc Sobel

b)

3.2.5. Phát hiện biên bằng toán tử gradient

Sử dụng toán tử gradient trong mi ền 2D là một trong các ph ương pháp dùng để

phát hiện biên. Toán tử định nghĩa như là một vec-tơ hai thành phần

f

x

(cid:209)=

Ø ø ¶ ¶ Ø ø

f

G x =ΠG

f

y

y

œ Œ œ ¶ ¶ º ß º ß

1/ 2

Toán tử xác định mô-đun và góc của gradient lần lượt như sau

(cid:209)=(cid:209)=

(

)

Ø ø

+ f fmagG G

2 x

2 y

1/ 2

2

º ß

=¶

¶+¶

(

(

)

) 2 y

,

)

(

)

fxf // ( = xyarctgG G ,

.

a

x

y

Ø ø ¶ º ß

18

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH Thông th ường thành ph ần mô-đun chỉ cần tính xấp xỉ là đã đạt yêu c ầu độ

+

chính xác của bài toán đặt ra. Hai công th ức gần đùng hay sử dụng là tổng các

fG

+ 2 fG G x

2 y

G x

y

(cid:209) » (cid:209) » bình phương và tổng các giá trị tuyệt đối .

19

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH

3.2.6. Loang rộng và thu nhỏ đối tượng

Loang rộng (dilation) và thu nhỏ (erosion) đối tượng là hai toán tử cơ của nhóm

thuật toán x ử lý morphology. Cả hai toán t ử này ch ỉ áp d ụng cho các ảnh nh ị

phân và mô t ả toán học của morphology là các phép toán t ập hợp [3]. Đồ án sẽ

vận dụng nhi ều hai thu ật toán trong công đoạn: khoanh vùng ảnh, làm m ảnh

a)

c)

b)

d)

Hình-15. Loang rộng đối tượng. a) ảnh ban đầu với đối tượng hình chữ nhật; b) strel có ba pixel xếp thành dạng đoạn thẳng, chéo 450 so với phương ngang; c) strel di chuyển khắp ảnh và các điểm bị tác động; d) ảnh kết quả.

biên, và hiệu chỉnh đường vân.

Ph ần tử cơ bản để th ực hi ện loang r ộng hay thu h ẹp gọi là structuring

element (viết tắt là strel). Căn cứ vào ảnh gốc cộng với độ lớn và hình dạng của

20

3. ĐẠI CƯƠNG VỀ ẢNH VÀ XỬ LÝ ẢNH strel, đối tượng bị cắt bớt ho ặc thêm vào t ừng điểm ảnh (phù h ợp với khuôn

hình của strel)

Tr ường hợp đặc biệt, áp d ụng toán tử thu hẹp liên ti ếp đủ số lần thì có quá

a)

c)

b)

d)

Hình-16. Thu nhỏ đối tượng. a) ảnh ban đầu với đối tượng hình chữ nhật;

b) strel có ba pixel xếp thành dạng đoạn thẳng vuông góc với phương ngang;

c) strel di chuyển khắp ảnh và các điểm bi tác động; d) ảnh kết quả.

trình làm mảnh đối tượng tới một pixel.

21

4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG

4. Sơ đồ khối thiết kế hệ thống nhận dạng vân tay

Trong phần nay sẽ giới thiệu một số phương pháp nhận dạng vân tay. Ti ếp theo

là các hình hệ thống nhận dạng đa năng. Ở mỗi phần, sẽ lựa chọn ra phương án

thực hiện trong đồ án. Đây là hai tiền đề xây dựng nên sơ đồ hệ thống nhận dạng

vân tay cho đồ án này.

4.1. Các nguyên lý nhận dạng vân tay

Các nguyên lý nh ận dạng vân tay thì liên quan ch ặt chẽ đến cách thức tìm ra sự

tương đồng giữa ảnh vân tay đầu vào với một template trong cơ sở dữ liệu vân

tay. Dưới đây là ba ph ương pháp chính l ần lượt dựa trên các c ơ sở là đối sánh

minutiae, correlation và ridge feature [1], ch. 4.

a)

b)

Hình-17. Tạo mã vân tay: a) ảnh ban đầu; b) trích chọn minutiae quan trọng

(các minutie được đánh dấu O)

• Minutiae-base matching, • Correlation-base matching, • Ridge feature-base matching.

22

4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG Phương pháp đầu tiên ph ổ biến hơn cả và được ứng dụng rất rộng rãi. Hai

vân tay sẽ được so sánh b ằng các điểm minutiae trích ra t ừ các vân tay đó. Giai

đoạn thứ nhất này còn goi là t ạo mã [11], các minutiae tạo thành tập hợp điểm

đặc trưng và được lưu trữ trong t ừng mảng 2D. Giai đoạn thứ hai s ẽ tìm vị trí

khớp phù hợp giữa template và input-image sao cho s ố các minutiae tao thanh

cặp tương đồng là lớn nhất.

Còn hai nguyên lý còn l ại không phù h ợp với đồ án. Correlation-based thực

hiện bằng cách xếp chồng hai mẫu vân tay lên nhau để tìm ra t ương quan gi ữa

chúng, ph ương pháp này g ặp hạn chế khi quá trình thu nh ận ảnh vân tay g ặp

phải các bi ến dạng méo. Còn ridge feature-base là một ph ương pháp cao c ấp,

đòi hỏi các bước xử lý ph ức tạp và th ường dùng cho ứng dụng nhận dạng với

các vân tay có chất lượng rất xấu (chẳng hạn như vân tay latent).

Đồ án này l ựa chọn phương án đầu tiên vì đó là một phương pháp c ơ bản,

phù hợp với điều kiện hiện tại cho phép và cũng hứa hẹn cho kết quả khả quan.

4.2. Hệ thống nhận dạng vân tay

Nhận dạng vân tay là m ột bộ phận của sinh tr ắc học. Vì th ế phân lo ại hệ thống

nhận dạng sinh tr ắc học cũng bao hàm cho h ệ th ống nh ận dạng vân tay nói

riêng. Có hai hình th ức phân loại hệ thống nhận dạng vân tay: dựa trên kiến trúc

của hệ thống và cách xử lý dữ liệu trong hệ thống [1], tr. 237-240.

a) Phân loại hệ thống theo kiến trúc:

• Hệ thống có kiến trúc song song • Hệ thống có kiến trúc nối tiếp • Hệ thống có kiến trúc thứ bậc

b) Phân loại hệ thống theo các xử lý dữ liêu:

• Hệ thống có khâu hợp nhất sau trích chọn đặc tính • Hệ thống có khâu hợp nhất sau đối sánh • Hệ thống có khâu hợp nhất sau tổng hợp kết quả

Với khuôn khổ đồ án, sẽ chọn hệ thống cấu trúc nối tiếp làm nền tảng.

23

4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG

4.3. Xây dựng hệ thống nhận dạng vân tay bằng ảnh số

Trên cơ sở các phân tích đã nêu, sau đây là đề xuất về sơ đồ khối hệ thống nhận

dạng vân tay bằng ảnh số. Hệ thống này có khả năng phân loại vân tay, tạo cơ sở

dữ liệu và nhận dạng vân tay.

• Kiểu nhận dạng là identification, nghĩa là một mẫu cần nhận dạng (input)

sẽ nhận kết quả bằng cách đối sánh với N mẫu khác trong c ơ sở dữ liệu

(template).

• Kiểu ch ế độ ho ạt động của hệ th ống hướng đến là online. Ngh ĩa là h ệ

thống có th ể ho ạt động liên t ục, có kh ả năng ghép với khâu thu th ập số

liệu sử các ph ương pháp thu nh ận ảnh live-scan (b ằng máy scan,

sensor,…) và quan tr ọng hơn có thể vừa thu th ập số liệu vừa có th ể nhận

dạng.

• Kiến trúc hệ th ống thi ết kế theo h ướng xử lý d ữ li ệu nối tiếp, gồm tám

Hình-18. Sơ đồ khối hệ thống nhận dạng vân tay.

khâu chính trình bày trong Hình-18.

Tám khâu này có cá chức năng hoạt động như sau:

1) Khâu số 1: thực hiện thu nhận ảnh.

24

4. THIẾT KẾ SƠ ĐỒ KHỐI HỆ THỐNG 2) Khâu số 2: th ực hiện trích ch ọn đặc tính vân tay để phân lo ại. Đặc tính

trích chọn là góc định hướng, orientation.

3) Khâu số 3: thực hiện tạo vec-tơ đặc tính để phân loại.

4) Khâu số 4: thực hiện phân loại vân tay làm năm nhóm.

5) Khâu số 5: làm cơ sở dữ liệu, lưu trữ các template-image.

6) Khâu số 6: thực hiện trích chọn minutiae. Đặc tính trích chọn là miutiae.

7) Khâu số 7: thực hiện đối sánh input-image với template-image.

8) Khâu số 8: thực hiện đưa ra kết quả nhận dạng.

25

5. TẬP MẪU ẢNH VÂN TAY

5. Tập mẫu ảnh vân tay

Vân tay có th ể lưu trữ theo hai cách: trên gi ấy (giấy thường, giấy ảnh...) hoặc

file ảnh. Đối với cách th ứ nh ất vẫn còn được ứng dụng trong giám định, định

danh hình sự (các bằng chứng về dấu tay tội phạm cần được thể hiện bằng ảnh in

trên giấy). Cách thứ hai được ứng dụng phổ biến trong nhận dạng nói chung và

ngày càng chiếm được nhiều ưu thế (có thể lưu trữ, tìm kiếm thuận tiện). Đồ án

a)

b)

c)

Hình-19. Các loại vân tay: a) vân tay latent; b) vân tay lăn mực;

c) vân tay trong Db2b-FVC2000.

này tập trung đến hình thức lưu trữ ảnh theo file.

Có nhiều định dạng ảnh vân tay khác nhau, phổ biến hơn cả là: jpeg, bmp, tif,

gif, png,... Các thông số ảnh bao gồm: độ rộng của ảnh, độ phân giải, số bit dành

cho một pixel, độ chính xác hình h ọc, méo,... Khi thi ết kế hệ thống nhận dạng

vân tay, các thông s ố ảnh thông thường được quy chuẩn theo giải giá trị nào đó

sao cho phù hợp với hệ thống. Hệ thống nhận dạng vân tay bằng ảnh số, ảnh số

là đại lượng đầu vào nên hai thông quan tâm h ơn cả: kích thước và độ phân giải.

Như đã trình bày ở trên, đồ án này s ử dụng dữ liệu ảnh FVC2000 để tạo cơ sở

364·

256

dữ liệu hệ thống nhận dạng và kiểm tra kết quả nhận dạng. Các mẫu vân tay lưu

theo file ảnh, có ph ần mở rộng .tif, kích th ước của ảnh pixel. Mỗi mẫu

vân tay gồm bảy ảnh khác nhau và được lưu tên theo quy ước xx_y. Trong đó xx

là chỉ số về thứ tự của bộ mẫu (còn gọi là chỉ bản) trong tập dữ liệu ảnh, y là thứ

26

5. TẬP MẪU ẢNH VÂN TAY tự của ảnh trong một bộ mẫu. Bộ mẫu sẽ đươc chia làm hai: m ột phần dùng để

thực hiện trích ch ọn và tạo mã cho vân tay thông qua các thu ật toán xử lý ảnh

(mục đích cuối là tạo ra các template xây dựng cơ sở dữ liệu); phần còn lại dùng

để kiểm tra, đánh giá thuật toán xử lý.

27

6. TRÍCH CHỌN MINUTIAE

6. Trích chọn minutiae cho đối sánh vân tay

Đồ án này được thiết kế bằng cách chia nh ỏ các công đoạn chính trên thành các

mô-đun nh ỏ hơn. Hướng chung là ch ọn các ph ương pháp mà có th ể tận dụng

được các mô-đun chương trình ở công đoạn này và áp dụng được cho công đoạn

khác. Nhưng các phương pháp lựa chọn phải đạt yêu cầu cho bài toán nhận dạng

Hình-20. Thuật toán trích chọn minutiae.

cuối cùng. Vì vậy, tạo tính mở cho hệ thống và tiết kiệm thời gian thiết kế.

Với sơ đồ này thấy rằng, trích chọn minutiae thực hiện qua tám khâu.

• Khối tiền xử lý ảnh thực hiện chuẩn hóa kích thước ảnh. • Khối tăng cường chất lượng ảnh thực hiện làm nổi rõ đường vân. • Khối orientation image thực hiện ước lượng trường định hướng. • Khối segmentation (khoanh vùng ảnh vân tay) thực hiện tách vùng ảnh

cần quan tâm nhiều trong xử lý trích chọn đặc tính.

• Khối tạo ridge map (ảnh nhị phân với đường vân có giá trị logic 1). • Khối làm mảnh đường vân. Đường vân làm m ảnh tới độ rộng đồng

nhất một pixel từ ridge map.

• Khối hiệu chỉnh đường vân và lọc minutiae sai cấp một. Đường vân sẽ

được làm “tr ơn”, minutiae sai ki ểu lake (d ạng hình xuy ến nhỏ), dạng

điểm, chẽ ngắn, đoạn vân ngắn sẽ loại bỏ.

• Lọc minutiae sai cấp hai và tạo mã vân tay bằng minutiae.

Kết thúc khâu này các template sẽ được tạo ra.

28

6. TRÍCH CHỌN MINUTIAE

6.1. Chuẩn hóa ảnh đầu vào

Chuẩn hóa ảnh đầu vào là bước cần thiết trước khi vào b ước tiền xử lý ảnh. Do

ảnh dùng cho trích tr ọn đặc tính có th ể không phù h ợp về kích th ước cũng như

phân bố mức xám. Trong đồ án, giai đoạn này gồm: chuẩn hóa kích th ước ảnh

và đồng đều hóa cường độ sáng giữa các ảnh đầu vào khác nhau.

6.1.1. Chuẩn hóa kích thước ảnh

364 ·

256

Ảnh chuẩn đầu vào có kích th ước pixel. Các thu ật toán xử lý ảnh vân

tay về sau thường áp dụng cho từng từng block vuông trên ảnh (thường sử dụng

352·

256

các block vuông cạnh 16 pixel, 32 pixel,…). Nên kích th ước ảnh chuẩn hóa hợp

lý hơn là pixel. Để thực hiện điều này sẽ “cắt” đi vùng dữ liệu ảnh kích

thước 12256· pixel. Phần này cũng không ảnh hưởng quá nhiều tới kết quả nhận

dạng cuối cùng vì đối với bộ dữ liệu đã chọn, các vùng ảnh ở gần khung thường

đóng vai trò làm background.

Hàm th ực hiện chuẩn hóa kích thước ảnh đầu vào là norsizfv.

gns = norsizfv(g, bs),

trong đó:

: ảnh số đầu vào có kích thước cần được chuẩn hóa, g

bs : kích thước của block mà ảnh đầu ra sẽ được làm tròn theo,

gns : ảnh đầu ra có kích thước đã chuẩn hóa.

6.1.2. Cân bằng cường độ sáng của ảnh

Do điều kiện thu th ập ảnh khác nhau v ới mỗi lần lấy mẫu vân tay; do k ỹ thuật

thu nhận ảnh (sử dụng sensor, scanner ,…) khác nhau nên độ sáng ảnh vân tay

không gần nhất. Vì vậy cần làm đồng đều cường độ sáng c ủa các ảnh vân tay

trong bộ dữ liệu. Phương pháp th ực hiện: dùng một ảnh mẫu có cường độ sáng

đồng đều, rồi chu ẩn hóa độ sáng c ủa các ảnh khác theo ảnh này b ằng bình

[ Ii

] = ,128 j

phương cực tiểu. Trong đồ án s ử dụng ảnh có cùng kích th ước cường độ sánh

các điểm ảnh (là mức xám trung trung bình trong 255 mức).

29

6. TRÍCH CHỌN MINUTIAE

Hàm thực hiện cân bằng cường độ sáng của ảnh là briequfv.

gbb = briequfv(g,ref),

trong đó:

: ảnh số đầu vào cần được chuẩn hóa cường độ sáng, g

ref : ảnh số làm mẫu

gbb : ảnh đầu ra có cường độ sáng gần với ảnh mẫu.

6.2. Tăng cường ảnh chất lượng ảnh

Thu nhận ảnh không phải lúc nào c ũng cho những ảnh với chất lượng tốt. Tăng

cường ảnh sẽ giúp cải thiện chất lượng ảnh trước khi thực hiện các thuật toán xử

lý ảnh tiếp theo nh ằm gia tăng hiệu quả xử lý. Hai thu ật toán s ử dụng để tăng

cường ảnh chất lượng ảnh ở đây là: histogram equalization (cân b ằng lược đồ

a)

b)

c)

Hình-21. Tăng cường ảnh: a) ảnh ban đầu; b) ảnh sau cân bằng histogram;

c) ảnh sau biến đổi Fourier rời rạc.

xám) và biến đổi Fourier rời rạc [1], tr. 104-113.

6.2.1. Tăng cường ảnh bằng cân bằng histogram

Histogram của ảnh xám là m ột biểu đổ thể hiện quan hệ giữa cường độ ảnh và

số pixel có cùng cùng c ường độ ảnh đó. Cân b ằng histogram sẽ làm đồng đều

cường độ sáng trong bản thân ảnh đó.

30

6. TRÍCH CHỌN MINUTIAE

Hàm thực hiện tăng cường ảnh bằng cân bằng lược đồ xám là hisequfv.

ghe = hisequfv(g),

trong đó:

: ảnh số đầu vào, g

ghe : ảnh đầu ra đã được tằng cường bằng cân bằng lược đồ xám.

6.2.2. Tăng cường ảnh bằng biến đổi Fourier-2D

Sử dụng lọc Gabor và bi ến đổi Fourier là hai n ền tảng chính để thực hiện tăng

cường ảnh trong xử lý ảnh vân tay. Ảnh sau khi đã được tăng cường chất lượng

bằng histogram equalization, th ực hi ện bước kế ti ếp là t ăng cường ảnh bằng

thuật toán biến đổi Fourier [1, 8, 9, 10].

So với các ph ương pháp trên c ơ sở lọc Gabor, nó l ợi thế hơn ở ch ỗ không

yêu cầu việc tính toán chính xác định hướng cục bộ của đường vân và tần số vân

tay phục vụ cho mục đích cuối công đoạn tạo ridge-map.

Công thức tính toán cho thuật toán tăng cường ảnh bằng biến đổi Fourier rời

1

{

(

}k

)

= -

rạc có dạng như sau:

I

( yxIFF

,[

) ]

,[ yxIF

]

enh

(cid:215)

trong đó:

]

)

( [ FIx,y

k : hệ số mũ của phổ Fourier,

: phổ Fourier.

32·

32

Đồ án thực hiện tăng cường chất lượng ảnh bằng biến đổi Fourier rời rạc cho

từng block có kích thước pixel. Theo cách này, các thành phần ảnh có tần

số trội sẽ được giữ lại, đó là các vùng ảnh thể hiện làm đường vân. Ảnh sau biến

đổi Fourier rời rạc có các đường vân “nổi” hơn, sự phân tách giữa các đường

vân cũng thể hiện rõ ràng hơn. Đồng thời các vùng ảnh nhiễu sẽ loại bớt đi.

31

6. TRÍCH CHỌN MINUTIAE

6,0=k

Số mũ của ph ổ Fourier, k đóng vai trò làm h ệ số điều ch ỉnh. Trong [1],

k =

0,35

khuyến nghị đặt khi tính toán v ới kích th ước block như trên. Tuy nhiên,

trong quá trình th ực hiện, đặt thì cho k ết quả tốt hơn so với việc chọn

giá trị khác. Vì phổ Fourier đóng vai trò làm hàm lọc, do đó: k càng nhỏ hàm lọc

tiến tới 1 (ảnh gốc và ảnh sau khi tăng cường không khác nhau nhiều); với k lớn,

các đoạn vân c ục bộ có th ể bị biến dạng không còn kh ả năng xử lý cho công

đoạn tiếp nữa.

Hàm thực hiện tăng cường ảnh bằng biến đổi Fourier rời rạc là fouenhfv.

gfe = fouenhfv(g,k),

trong đó:

: ảnh số đầu vào, g

: hệ số, k

gfe : ảnh đầu ra đã được tăng cường bằng biến đổi Fourier.

6.3. Ước lượng orientation image và khoanh vùng ảnh vân tay

Trong phần này sẽ trình bày các ước lượng định hướng vân tay c ục bộ. Đây là

cần thi ết để ch ọn được các thông s ố thích h ợp để lọc ảnh về sau (l ọc nhi ễu,

khoanh vùng ảnh...). Vì orientation image (trường định hướng) mang tính mô tả

góc định hướng đường vân, nên kết quả này còn được áp dụng để phân loại kiểu

vân tay (quyết định bởi sự tạo hình của các đường vân).

6.3.1. Ước lượng orientation image

Trường định hương thể hiện bản chất tự nhiên của đường vân và các rãnh đường

vân. Trường định hướng cung cấp nhiều thông tin quan trong cho các bước xử lý

tiếp theo. Phần này sẽ trình bày về ước lượng orientation image D, phần tử định

ijq và mô-đun định hướng). Có sự

hướng ijq (tương ứng với nó là góc định hướng

phân biệt khác nhau gi ữa các thu ật ng ữ mô t ả phần tử định hướng orientation

[

]

[

]

0,

0, 2

p

p

ijq

ijq

˛ ˛ (có ), direction (có ) khi tính toán trường định hướng [1].

32

ww·

Nguyên lý th ực hiện tính định hướng: chia ảnh thành các kh ối 6. TRÍCH CHỌN MINUTIAE , sau đó

khảo sát l ần lượt định hướng cục bộ của đường vân trong t ừng kh ối đó.

a)

b)

Hình-22. Ước lượng orientation image: a) ảnh vân tay ban đầu;

b) orientation image tương ứng

Orientation image sẽ được ước lượng bằng phương pháp Gradient [3, 4]

+

+

i

j

w 2

w 2

)

(

(

)

=

,

j

) vugvug

,

,

Các công thức tính toán:

( iG n

y

x

-= iu

-= jv

2 w 2

w 2

+

+

j

i

w 2

w 2

)

)

(cid:229) (cid:229) ,

) )

=

,

j

-

( ( vug

,

( vug

,

( iG d

2 x

2 y

-= iu

-= jv

w 2

w 2

(cid:229) (cid:229) ,

j

,

(

q

) )

1 ) = ijarctg , 2

( ( j

,

Gi n Gi d

,

)j

,

)j

)j

(cid:230) (cid:246) (cid:231) (cid:247) . (cid:231) (cid:247) Ł ł

( ig y

( ig x

Ở đây: , là các gradient tại ( i, theo các tr ục x, y và tính b ằng

toán tử Sobel [5, 6].

33

6. TRÍCH CHỌN MINUTIAE

Hàm thực hiện ước lượng trường định hướng là oriimafv.

[iD, iC, DF] = oriimafv(g,bs),

trong đó:

g : ảnh số đầu vào,

bs : kích thước block vuông ước lượng định hướng,

iD : ma-trận lưu đính hướng của mỗi block,

iC : ma-trân lưu level-certenty của mỗi block,

DF : ma-trân lưu định hướng và tọa độ tâm của mỗi block.

6.3.2. Khoanh vùng ảnh vân tay

Khoanh vùng ảnh vân tay nh ằm mục đích phân chia các vùng khác nhau trên

ảnh vân tay. Ở đây, chúng ta quan tâm đến foreground/background (ảnh nền và

ảnh trên n ền) cùng với biên ảnh vân tay. Trong nh ận dạng vân tay, vùng ảnh

mang thông tin h ữu ích gi ới hạn bởi vùng có các đường vân (đóng vai trò làm

foreground). Vùng ảnh còn l ại th ường là các nhi ễu tạo ra trong quá trình thu

nhận, sao chép, l ưu trữ ảnh… (đóng vai trò làm background) cần được tách ra

khỏi foreground. Khoanh vùng ảnh vân tay n ằm trong nhóm thu ật toán

segmentation. Tổng quát, nó d ựa vào hai tính ch ất của ảnh số liên quan đến

cường độ sáng để thực hiện, đó là: sự không liên tục và sự tương tự nhau [3].

Ảnh vân tay trong đồ án sẽ khoanh vùng lấy vùng hữu ích dựa vào cả hai tính

chất kể trên. Tiêu chí đánh giá là certainty level (m ột giá tr ị th ể hi ện sự bi ến

thiên của cường độ sáng theo các đường vân). Theo cách này vùng ảnh đóng vai

trò background và foreground được phân tách nhờ một ngưỡng đặt trước [2].

],i

Công th ức tính certainty level cho từng block kích th ước w w· , tr ọng tâm

j như sau:

2

)

,

,

j

( iG n

)

=

( iC

,

j

tương ứng của block có tọa độ [

1 ww

( iG d )j ,

) 2 + j ( iG s

·

34

6. TRÍCH CHỌN MINUTIAE

cT được đặt ra và block đó định nghĩa làm

)

<

( iC

,

j

Một ngưỡng

cT

)

, • background nếu

( iC

,

j

cT

‡ • foreground nếu .

Phương pháp này có l ợi thế kế th ừa được các k ết quả tính toán trong ph ần

a)

b)

c)

Hình-23. Khoanh vùng ảnh vân tay: a) ảnh ban đầu; b) variance field;

c) ảnh đã khoanh vùng đường vân.

ước lượng orientation image.

Hàm thực hiện khoanh vùng ảnh có các đường vân tay là segimafv.

area = segimafv(iC,k),

trong đó:

: ma-trận lưu giá trị level-certenty cục bộ, iC

: kích thước block, bs

area : vùng ảnh vân tay đã được khoanh.

6.4. Trích chọn minutiae

Giai đoạn này bao g ồm: nh ị phân hóa ảnh bằng thuật toán local threshold với

ảnh đã được tăng cường kết hợp với kết quả khoanh vùng ảnh vân tay ở phần

35

6. TRÍCH CHỌN MINUTIAE trên; sau đó với ảnh có các đường vân đã được làm mảnh đến độ rộng một pixel

a)

b)

Hình-24. Thông số của hai dạng minutiae quan trọng: a) bifurcation; b) termination.

thì thực hiện tìm minutiae bằng thuật toán crossing number [1], ch. 4.

6.4.1. Nhị phân hóa và làm mảnh đường vân

Sau tăng cường ảnh bằng biến đổi Fourier rời rạc, đường vân tây đã nổi rõ hơn

so với ảnh ban đầu. Đây là lúc s ử dụng thu ật toán local threshold chuy ển đổi

a)

b)

Hình-25. Nhị phân hóa và làm mảnh đường vân: a) ridge-map; b) thinned ridge-map.

32 ·

32

ảnh xám đã tăng cường chất lượng đó thành ảnh đen trắng.

Kích thước cửa sổ pixel trong bi ến đổi Fourier rời rạc thì kích th ước

block cho phân ng ưỡng cục bộ có th ể là: 3232· , 3216· ,1616· ,16 8· pixel… Thử

nghiệm với block 1616· pixel thì cho kết quả tốt hơn (các đường vân tách biệt rõ

36

6. TRÍCH CHỌN MINUTIAE ràng hơn). Ảnh này tiếp tục được làm mảnh bằng thuật toán morphology cho ảnh

đen trắng sau cùng v ới đường vân th ể hiện bằng đường màu tr ắng (giá tr ị logic

1) có độ rộng đồng nhất một pixel.

Hàm thực hiện nhị phân hóa ảnh vân tay là locthrfv.

glt = locthrfv(g,bs,adj),

trong đó:

: ảnh đầu vào, g

bs : kích thước block,

adj : hệ số hiệu chỉnh,

glt : ảnh đầu ra đã được nhị phân hóa.

6.4.2. Phát hiện minutiae

Vân tay sau khi đã làm mảnh có th ể bắt đầu tìm các minutiae. Thuật toán dùng

để phát hiện minutiae sử dụng trong đồ án là crossing number. Nó dùng một cửa

],i

pixel, lấy tất cả các điểm ảnh trong cửa sổ, sau đó khảo sát giá

j ở chính gi ữa cửa sổ đó.

sổ kích thước 3 3· trị logic c ủa các điểm ảnh xung quanh điểm ảnh [

j đang xét là một điểm phân nhánh, điểm cụt hay đang nằm trên một đường

Tùy vào kết quả tính toán của biểu thức crossing number thì kết luận rằng: điểm ],i [

vân.

8

Công thức tính như sau:

(

)

(

)

=

pcn (

)

val

p

val

p

i

1

i

8mod

1 2

= 1

i

(

val

) { ˛p

}1,0

- (cid:229) -

,

...,

p

Ảnh sử dụng phát hiện các minutiae phải là ảnh nhị phân, do đó .

pp , 1

2

7

Các biến thứ tự tạo thành các điểm lân cận điểm giữa cửa sổ đang

khảo sát xét theo một chiều thuận hoặc ngược kim đồng hồ.

37

],i

6. TRÍCH CHỌN MINUTIAE

j đang xét là:

Khi đó định nghĩa điểm [

• trên đường vân nếu cp(n) = 2, • termination minutiae nếu cn(p) = 1, • bifurcation minutiae nếu cn(p) = 3.

Thuật toán tìm kiếm và giá tr ị crossing number có vai trò quan tr ọng. Không

những được dùng trong vi ệc phát hi ện minutiae mà nó còn giúp lo ại bỏ các

a) cn(p) = 2

b) cn(p) = 2

a) cp(n) = 3

d) cn(p) = 1

Hình-26. Phát hiện minutiae: a), b) pixel trên đường vân; c) bifurcation minutiae;

d) termination minutiae.

minutiae sai (được cho là nhiễu).

Hàm thực hiện phát hiện minutiae là finminfv.

[ter, bif] = finminfv(g),

trong đó:

: ảnh đầu vào có độ rộng đường vân một pixel, g

ter : ma-trận lưu tọa độ của termination minutia,

bif : ma-trận lưu tọa độ của bifurcation minutia.

38

6. TRÍCH CHỌN MINUTIAE

6.4.3. Ước lượng khoảng cách đường vân

Vân tay trên ngón tay không gi ống nhau giữa mỗi người. Ngay cả trường hợp ở

một ng ười, các đường vân c ũng th ể hi ện sự khác bi ệt trên t ừng ngón tay. Do

vậy, ước lượng kho ảng các đường vân được hiểu là d ải tr ị trung bình kho ảng

cách giữa hai đường vân song song và g ần nhau. Đây là một thông tin làm ti ền

đề cho công đoạn lọc minutiae về sau.

Ảnh nhị phân có các đường vân đã được làm mảnh đến 1 pixel tạo ra từ khâu

làm mảnh đã có, tỏ ra rất thuận tiện với phương pháp scan trong việc ước lượng

khoảng cách đường vân. Theo cách này, s ẽ quét một số dòng và một số cột trên

ảnh (thinned ridgemap ), lưu lại vị trí điểm trên đường vân, sau đó tính giá tr ị

trung bình khoảng cách điểm là được kết quả cần tìm.

Hàm thực hiện phát hiện ước lượng độ rộng đường vân là mearidfv.

rd = mearidfv(g),

trong đó:

: ảnh đầu vào có độ rộng đường vân môt pixel, g

rd : độ rộng trung bình của đường vân.

6.4. Hiệu chỉnh đường vân và lọc minutiae sai

Trong ph ần này s ẽ trình bay v ề vấn vân đề lo ại bỏ các minutiae sai. Nh ững

nhiễu này ch ủ yếu được tao ra t ừ quá trình làm m ảnh đường vân, và c ũng có

những nhiễu từ khâu thu nhận ảnh

Các công vi ệc thực hiện: làm “tr ơn” đường vân, “nối” các đường vân bị đứt

trong ngưỡng gi ới hạn, “tách” các đường vân bị dính, cu ối cùng là t ạo mã vân

tay từ minutiae.

6.4.1. Hiệu chỉnh đường vân và lọc minutiae sai cấp một

Giai đoạn này th ực hi ện hi ệu ch ỉnh các vân tay và các tín hi ệu cho là nhi ễu

(đoạn vân ngắn, chẽ nhánh cụt, vòng xuy ến nhỏ…) sẽ được loại đi. Như vậy sẽ

39

6. TRÍCH CHỌN MINUTIAE làm tăng tính xác th ực của các minutiae đã trích ch ọn được so với ảnh vân tay

a)

c)

Hình-27. Số minutiae phát hiện được: a) ngay sau làm mảnh vân; b) sau lọc minutiae.

(vùng ảnh đánh dấu vuông và tròn thể hiện điển hình một số minutiae sai được loại bỏ)

gốc ban đầu.

Khi th ực hiện hai nhiêm v ụ này, thông tin c ần cần biết trước là kho ảng các

trung bình gi ữa các đường vân rd. Nó đã được ước lượng từ bước scan ảnh vân

tay làm mảnh trình bày ở trên. Sau đó, việc lọc minutiae sẽ căn cứ theo rd cộng

a)

b)

Hình-28. Lọc các minutiae. a) minutiae sai; b) các minutiae sai bị loại bỏ

thêm các điểm “nút” tìm thấy bằng thuật toán crossing number.

40

6. TRÍCH CHỌN MINUTIAE Hàm thực hiện phát hiện thuật toán hiệu chỉnh đường vân tay và lọc minutiae

cấp một là smoridfv.

[gs, ster, sbif] = smoridfv (g),

trong đó:

: ảnh đầu vào có độ rộng đường vân một pixel, g

: ảnh đầu ra đã được làm “trơn” đường vân, gs

ster : ma-trận lưu tọa độ của termination minutia,

sbif : ma-trận lưu tọa độ của bifurcation minutia.

6.4.2. Lọc minutiae sai cấp hai và tạo mã từ minutiae

Khi các đường vân đã làm “trơn”, các điểm minutiae được tìm kiếm một lần nữa

và số lượng các điểm sai cũng đã được giảm đáng kể. Tuy nhiên còn hai l ỗi mà

quá trình trên ch ưa khắc phục được là “n ối” các đường vân bị đứt (khoảng các

giữa hai đầu mút < rd ) và “c ắt” đoạn vân nối hai đường vân dạng cầu chữ H

(khoảng cách cầu < rd).

Giải pháp th ực khắc phục là so sánh kho ảng cách định giữa hai điểm nút và

,d q

D D góc định hướng của chúng theo ng ưỡng ( ) để loại bỏ. Trong đồ án ch ọn

]

6,

6

[ qp p

D =

D ˛ - (kho ảng góc rộng hơn hoặc hẹp hơn tỏ ra ít có hi ệu quả trong

Hình-29. Các minutiae được trích chọn cuối để tạo mã.

khi thưc hiện đồ án), còn drd .

41

6. TRÍCH CHỌN MINUTIAE

Hàm thực hiện sai cấp hai và tạo mã từ minutiae là extminfv

[eter, ebif] = extminfv (g),

trong đó:

: ảnh đường vân môt pixel đã làm “trơn”. g

eter : ma-trận lưu tọa độ của termination minutiae,

ebif : ma-trận lưu tọa độ của bifurcation minutiae.

Các minutiae trích chọn cuối cùng này sẽ được lưu trữ thành file tạo template

cho cơ sở dữ liệu. Thông tin l ưu trữ là tọa độ, định hướng minutiae. Quá trình

tạo mã từ minutiae hoàn tất khâu trích chọn đặc tính để định danh.

42

7. PHÂN LOẠI VÂN TAY

7. Phân loại kiểu vân tay

Hệ thống nhận dạng identification, cơ sở dữ liệu có th ể lên đến hàng tri ệu chỉ

bản nên quá trình đối chiếu 1:N dĩ nhiên tốn rất nhiều thời gian [1], tr.173. Phân

loại vân tay nh ằm mục đích tổ ch ức các template theo t ừng category (nhóm

phân loại) để tiết kiệm thời gian nh ận dạng (cho một input-image khi hệ thống

a)

b)

c)

d)

e)

Hình-30. Năm kiểu vân tay trong thực tế: a) arch ; b) whorl ; c) tented arch;

d) left loop ; e) right loop.

hoạt động).

Mặc dù đồ án giới hạn trong số lượng mẫu ít để thực hiện xử lý dữ liệu đó và

thử nghiệm. Nhưng hệ thống nhận dạng vân tay trong đồ án này được thiết kế

theo kiểu identification (có kh ả năng đối chiếu 1:N). Tuân th ủ kiểu nhận dạng

của hệ thống và hướng thiết kế mở đặt ra ban đầu thì phân lo ại vân tay là khâu

không th ể bỏ qua. Gi ải pháp phân lo ại vân tay ở đây sử dụng cây quy ết định

(treefit), như vậy sẽ kế thừa được nhiều kết quả của phần trích chọn đặc tính vân

tay cho đối chiếu ở trên.

43

7. PHÂN LOẠI VÂN TAY

Quá trình phân lo ại vân tay được thực hiện qua ba khâu chính

1) trích chọn đặc tính định hướng cục bộ,

2) tạo vec-tơ đặc tính,

3) bộ phân loại.

Các vân tay được phân lo ại vào năm category: A, L, R, T, W, t ương ứng với

Hình-31. Sơ đồ khối mô tả thuật toán phân loại vân tay.

arch, left loop, right loop, tented arch và whorl [1], ch.5.

7.1. Trích chọn đặc tính

Phân loại vân tay thì ph ụ thuộc nhiều vào các điểm kỳ dị (singular point ), bao

gồm điểm delta và điểm core. Khi đã có orientation image các điểm kỳ dị có thể

xác định thuân lợi bằng phương pháp Poincaré. Đặc tính c ần trính ch ọn là góc

,i jq [1, 3, 8].

a)

b)

Hình-32. Phương pháp chỉ số Poincaré: a) trong miền liên tục; b) trong ảnh số.

định hướng cục bộ

44

],i

Ch ỉ số Poincaré c ủa tr ường định hướng tại điểm ảnh [ 7. PHÂN LOẠI VÂN TAY j theo một đường

N

=

bao kín tính như sau:

)

( Poincarij é,

( ) ,

1 2 p = k

k 0

D (cid:229)

<

)

(

)

k ,

,

( dkd d

d

( D=+

(

)

(

)

) kdkd

,

,

k pd

d

)

( )

( dkd

k ,

,

pd

d

p 2 p 2 p 2

=++

(cid:236) (cid:239) (cid:239) (cid:239) ‡ (cid:237) (cid:239) (cid:239) - £ - (cid:239) (cid:238)

( )

(

(

( )

(

)

(

)

(

)

-

(

)

)

) .

( ) dkDFLkLLkLDFLkL k 1mod,1mod, d j

iji

],i j ,

iL và

jL tạo hệ trục tọa độ

Trong đó L là một đường bao kín l ấy điểm [

hướng hàng và hướng cột tại điểm đang xét. Chỉ số Poincaré bằng 0,5 nếu điểm

- nếu điểm đó là delta. Đồ án thực hiện thuật toán phát hiện

],i j .

đó là core, bằng 0,5 core với đường bao L có chiều dài 16 pixel và bao quanh điểm [

7.2. Tạo vec-tơ đặc tính

Sau khi phát hi ện được điểm core, vec-tơ đặc tính được tạo ra bằng các khoanh

1111·

vùng lấy 1111· định hướng cục bộ mà điểm này làm tr ọng tâm. Một ma-trận cỡ

],i

không thích hợp làm vec-tơ đầu vào cho khâu phân lo ại nên nó được điều

j .

=

)

V

q

chỉnh lại kích th ước thành vec-t ơ 121 thành ph ần. Mỗi thành ph ần này là góc định hướng định hướng cục bộ của block có tọa độ [

( 12121,,...,,..., qqq

k

f

,

[

] = 0,,1,121 k p

q k

˛ .

]0,1 .

fV là –fV có các thành phần thuộc đoạn [

Vec-tơ chuẩn hóa của

qq

q

q k

f

1 = (cid:231) = V,,...,,..., fV pppp

12121 p

(cid:230) (cid:246) – . (cid:247) Ł ł

45

7. PHÂN LOẠI VÂN TAY

Dưới hình ảnh mô tả quá trình tạo vec-tơ đặc tính

q

q

1,11,11

K

V

= (cid:231)

MO M

q

q

11,111,11

L

b)

a)

Hình-33. Lấy đặc tính cho phân loại: a) vùng tạo vec-tơ đặc tính;

b) vec-tơ đặc tính tương ứng.

(cid:230) (cid:246) (cid:231) (cid:247) (cid:247) (cid:231) (cid:247) Ł ł

7.3. Khâu phân loại kiểu vân tay

Giải pháp thực hiện khâu phân lo ại vân tay dùng cây quy ết định (treefit), đây là

một giải pháp tốt cho bài toán phân lo ại kiểu vân tay (th ể hiện ở kết quả nhận

Hình-34. Kết quả cây quyết định của bài toán phân loại kiểu vân.

dạng).

46

7. PHÂN LOẠI VÂN TAY ố nút trong cây quy ết định không bi ết tr ước. Cây quy ết định cũng cần Do s

xác định cấu trúc tối ưu. Tiêu chí để đánh giá dùng cặp sai số học và sai số kiểm

tra (là các hàm c ủa số nút) để tìm ra s ố nút đầu cuối mà có sai s ố kiểm tra bé

nhất. Cấu trúc cây đánh giá là tốt nếu nó thật đơn giản (có ít nhánh nh ất), nhưng

vẫn phải đảm bảo độ chính xác.

Trong khâu phân lo ại này, bộ mẫu sử dụng trích ra t ừ 175 ảnh và ti ến hành

xây dựng cây t ối ưu thông qua thu ật toán cross-validation. Theo cách này, s ẽ

dùng 90% m ẫu ng ẫu nhiên để xây d ựng cây và dùng 10% s ố mẫu còn lại để

kiểm tra sai số. Sai số cho quá trình xây dựng cây được gọi là resubstitution.

Hình-35 th ể hiện đường cong sai s ố kết quả của bài toán phân lo ại vân tay.

Cấu trúc tối ưu của cây gồm sáu nút.

Hình-35. Đường cong sai số học và kiểm tra.

Sai s ố học là 1,14%. Sai số kiểm tra là 9,14%.

47

8. ĐỐI CHIẾU VÂN TAY

8. Đối chiếu vân tay để định danh mẫu

Cũng giống như phân lo ại vân tay, có r ất nhiều các để thực hiện đối chiếu vân

tay. Tuy nhiên có thể chia làm nhóm phương pháp [1], tr. 131-168.

• Correlation-based • Minutiae-based • Ridge feature-based

Vì ngay từ ban đầu đã lựa chọn phương pháp nhận dạng vân tay trên cơ sở là

minutiae. Nên khâu th ực hi ện đối chi ếu vân tay s ẽ dựa vào các điểm nút đặc

trưng nay. Vi ệc đối chiếu dựa trên hai b ộ số liệu: I của input-image và T của

}

template-image.

}

{ = TTmm

,

p= 1,

i

, q

m ,,..., 2

1

p

iii

, .

¢ ¢ ¢ ¢ ¢

}

, }

{ = IImm

,

q= 1,

j

, q

m¢ ,,..., 2

1

q

{ = imx y { ¢= mx y j jjj

, , .

Hình-36 dưới đây th ể hi ện sự đối sánh hai m ẫu vân tay trên c ơ sở các

minutiae đã được trích chọn ở bước trên. Hai minutiae ở mỗi mẫu được nối với

Hình-36. Đối chiếu vân tay dựa trên cơ sở minutiae.

nhau bằng đường liền nét thì thể hiện sự trùng khớp với nhau.

Sau đây sẽ trình bày thuật toán đối sánh vân tay, bao gồm cả hai công đoạn:

khớp mẫu (alignment) và đối sánh (matching) [3], ch. 6.

48

8. ĐỐI CHIẾU VÂN TAY

8.1. Khớp mẫu hai mẫu vân tay

Khớp mẫu vân tay được hiểu là “đặt” một mẫu vân tay cần đối sánh với mẫu mà

nó cần sẽ đối sánh ở một vị trí sao cho có s ự phù h ợp gi ữa chúng theo m ột

ngưỡng. Vì v ậy các toán t ử dùng để kh ớp mẫu gồm có: ma-tr ận quay, t ịnh

tiến…

Thuật toán alignment bao gồm các bước

1) chọn lấy một cặp minutiae của input và template,

2) xoay các đối tượng của template theo các đối tượng của input,

pS của hai mẫu input và template cho đến khi đạt

3) tính mức độ phù hợp

rT .

một ngưỡng đặt trước

Các đối tượng của template và input ở đây chính là các đoạn vân tay mà có điểm

minutiae đã trích chọn, độ dài của các đoạn vân này được lấy bằng khoảng cách

rT lấy giá tr ị

trung bình gi ữa các đường vân rd tính từ điểm minutiae làm mốc.

bằng 0,8 [3], tr. 117.

1

0

x

=

0

1

y

RT

00

1

Hình-37. Khớp mẫu từng đối tượng: a) toán tử ma-trận tịnh tiến;

b) quay và tịnh tiến đối tượng

D (cid:230) (cid:246) (cid:231) (cid:247) D (cid:231) (cid:247) (cid:231) (cid:247) Ł ł

pS tính theo công thức:

2

2

Còn

piii

i =

=

rdrd = (cid:229) SdDd D 0 i

0

i

)

,

(cid:229)

q cho bước tiếp ,

( rITx y

ef

Cuối cùng sẽ tìm được điểm minutiae tham chi ếu

theo là matching.

49

8. ĐỐI CHIẾU VÂN TAY

8.2. Đối sánh vân tay

Khi đã khớp được hai mẫu vân tay, vi ệc tiếp theo là làm phù h ợp giữa T và I.

Đầu tiên s ẽ thực hiện quay toàn b ộ các minutiae của template theo điểm tham

chiếu đã chọn được ở bước khớp mẫu. Toán tử quay RA định nghĩa như sau:

0 q

=

RA

c 0

q

ossin c q sinos q 00

1

(cid:230) (cid:246) (cid:231) (cid:247) - (cid:231) (cid:247) (cid:231) (cid:247) Ł ł

N

c

=

S

Tiếp theo, sẽ đếm các cặp minutiae thỏa mãn sai lệch về vị trí và góc trong gi ới

f

cN là

q

hạn e . Để đánh giá mức độ giống nhau sẽ dùng thang điểm , với

a)

b)

Hình-38. Thực hiện matching: a) khớp các minutiae; b) ngưỡng lân cận để tính điểm (score).

số cặp điểm minutiae thỏa mãn lân cân e ; q là tổng số minutiae của input

Hàm thực hiện phát hiện đối sánh vân tay là matimafv.

score = matimafv(f,g,e ),

trong đó:

: mẫu input-image, f

: mẫu template-image, g

e

: giá trị lân cận,

score : điểm kết quả của đối sánh hai mẫu.

50

8. ĐỐI CHIẾU VÂN TAY Th ử nghiệm với hai ảnh đầu của mỗi bộ mẫu (xx_1.tif và xx_2.tif) với tất cả

các mẫu còn lại của bộ dự liệu (gồm 125 ảnh đánh số xx_3.tif đến xx_7. tif, tổng

cộng có 6250 phép th ử nghi ệm) nếu lấy kết quả so sánh có score cao nh ất thì

chính xác đạt 100%. Tuy nhiên b ộ số liệu này còn có kh ả năng mở rộng thêm

nên hình th ức thể hiện kết quả minh bạch hơn là một dải kết quả chính xác t ừ

cao đến thấp. Việc hiển thị 1, 2, 5 hay nhi ều kết quả đều có thể thực hiện không

khó khăn. Trong đồ án thể hiện ra bốn kết quả sát với ảnh đầu vào nhất.

Ví d ụ: Hình-39 cho th ấy khi nh ận dạng ảnh 7_2 (của người 7, mẫu số 2) thì

7_5.tif

7_6.tif

7_2.tif

cả bốn mẫu gần nhất đều của người 7, trong đó mẫu 5 giống 100%.

score »

score »

100

7_7.tif

7_3.tif

86,67

score »

score »

a)

b)

Hình-39. Kết quả nhận dạng: b) vân tay đầu vào; a) các vân tay được nhận dạng theo (b).

71,11 71,11

Các chương trình chạy trong Matlab phiên bản 7.0; cấu hình phần cứng: CPU

Pentium IV 1,8Ghz, RAM 512MB, FSB 333Mhz.

Thời gian tạo cơ sở dữ li ệu: cho tất cả đầu vào gồm 175 ảnh cần thời gian

khoảng 10 phút. Nên thời gian trung bình tạo một template khoảng 3,4 giây.

Thời gian th ực hiện đối sánh: th ử nghiệm với 6250 lần đối sánh ( 25 2· mẫu

kiểm tra với 25 5· mẫu còn lại) thì mất khoảng 2,5 giờ. Nên thời gian trung bình

một lần thực hiện đối sánh khoảng 1,4 giây.

51

9.TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN

9. Tổng kết và hướng phát triển

Nhận dạng vân tay là m ột trong nh ững lĩnh vực nghiên cứu chuyên sâu. Các

tài liệu, thuật toán, mô- đun chương trình rất hạn chế vì bản quyền tác gi ả. Kết

thúc đồ án, đã xây d ựng được ph ần mềm mô ph ỏng các b ước th ực hi ện nh ận

dạng trong hệ thống nhận dạng vân tay. Các mô-đun chương trình cần thiết cũng

đã được hoàn thành.

Sau đây là phần tổng kết chi tiết và hướng phát triển mở rộng của đồ án.

9.1. Kết quả của đồ án

• Đã thực hi ện nhận dạng được ảnh số vân tay đầu vào với độ chính xác

cao. Nếu chỉ lấy một giá tr ị có điểm đánh giá cao nh ất trong các k ết quả

so sánh thì nh ận dạng dược 100%. Tuy nhiên con s ố này còn b ị giới hạn

bởi số lượng mẫu khảo sát còn ít.

• Hệ th ống xây d ựng theo nh ư ki ểu dự ki ến ban đầu, đó là nh ận dạng

identification (1:N), chính vì v ậy kết quả nhận dạng thể hiện minh b ạch

bằng một dải giá tr ị sắp xếp theo tiêu chí: gi ống với mầu đầu vào nhi ều

cho tới ít

• Thực hi ện phân lo ại kiểu vân tay có độ chính xác khá cao, đạt 90,86%.

Điều này khẳng định sự khả thi mở rộng cở sở dữ liệu ảnh. Phân loại kiểu

vân tay tốt đồng nghĩa với việc hạn chế tìm ki ếm so sánh vân tay ở một

nhóm template (thay vì toàn bộ) mà vân đảm bảo chính xác.

• Chương trình xử lý thuật toán trong đồ án thiết kế theo mô-đun và có th ể

tận dụng cho các khâu khác cùng hệ thống.

• Hệ thống thiết kế có tính mở. Có khả năng thay thế các mô-đun thực hiện

thuật toán. Cơ sở dữ liệu ảnh có thể bổ sung thêm dễ dàng.

Những kết quả trên cho thây hệ thống nhận dạng trong đồ án có thể triển khai

vào thực tế.

52

9.TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN • Tiếp cận với thuật toán nh ận dạng đường vân để phân lo ại chính xác hơn

các dạng vân tay.

• Các ch ương trình được thi ết kế theo mô- đun, tính m ở của hệ th ống là

xuyên suốt do đó không gặp khó khăn nhiều trong việc mở rộng cơ sở dữ

liệu. Điều này cũng có ngh ĩa là bộ số liệu học có th ể tăng thêm dễ dàng,

góp phần cải thiện độ chính xác nh ận dạng. Và cả việc thay thế nâng cấp

các mô-đun chương trình cũng sẽ không gặp nhiều khó khăn.

• Đóng gói thành sản phẩm hoàn thiện.

54

PHỤ LỤC

Tài liệu tham khảo

[1] Maltoni D., Maio D., Jain A. K., Prabhakar S., Handbook of Fingerprint

Recognition, Springer, 2003.

[2] Hoover J. E., The Science of Fingerprints Classification and Uses , United

States Department of Justice, 2006.

[3] Hong L., Automatic Personal Identification using Fingerprints, Michigan

State Univesity, 1998.

[4] Ratha N. K., Chen S., Jain A. K., Adaptiveow orientation based feature

extraction in Fingerprint Recognition, Michigan State Univesity, 1995.

[5] Gonzalez R C., Woods R. E ., Digital Image Processing , 2nd Edition,

Prentice Hall 2002.

[6] Gonzalez R C., Woods R. E ., Eddins S. L., Digital Image Processing

using MATLAB, Prentice Hall 2004.

[7] Neto H. V., Borges L. D., Fingerprint Classification with Neural

Networks.

[8] Park H. C., Park H., Fingerprint Classification using Fast Fourier

Transform and Nonlinear Discriminant Analysis , University of

Minnesota.

[9] Chickkerur S., Wu C., Govindaraju V., Cartwright A. N., Fingerprint

Image Enhancement Using STFT Analysis. University at Buffalo.

[10] Chickkerur S., Wu C., Govindaraju V., A systemmatic approach for

feature extraction fingerprint images, University at Buffalo.

[11] Komarinski P., Automated Fingerprint Identification Systems (AFIS) ,

Elsevier, 2005.

[12] Trần Hoài Linh. Bài giảng “Mạng nơ-ron nhân tạo và ứng dụng trong xử

lý tín hiệu”.

[13] Wuzhili, Fingerprint Recognition, Hong Kong Baptist University, 2002.

55

PHỤ LỤC

Phụ lục

Danh sách các script file khác trong đồ án

Chức năng

STT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Tên hàm angbiffv Tính góc định hướng của bifurcation minutiae angterfv Tính góc định hướng của termination minutiae arecarfv Khoanh vùng để tính chỉ số Poincaré briequfv Cân bằng cường độ sáng cronumfv Tính crosssing number delboufv Xóa nhiễu ở ngoài đường bao tao ra bởi segmentation delshofv Xóa các đoạn vân ngắn fincorfv Tìm điểm core finshofv Tìm đoạn vân ngắn inpcatfv Lấy catogory inpimafv Lấy input leasqufv Ước lượng bình phương cực tiểu loaimafv Load ảnh vào để xử lý mearidfv Ước lượng khoảng cách trung bình của các đường vân norsizfv Hiệu chỉnh kích thước ảnh plominfv Hiển thị các minutiae rotallfv Xoay tất các đối tượng để tìm cặp minutiae rotridfv Xoay các đối tượng để khớp mẫu genvecfv Tạo vector dữ liệu để phân loại sortttfv Sắp xêp kết quả thirid1fv Làm mảnh đường vân cấp một thirid2fv Làm mảnh đường vân cấp hai

56

PHỤ LỤC

Các bước chạy phần mềm mô phỏng

Bước 1: Chuyển thư mục hiện hành tới thư mục Finger. Sử dụng lệnh:

>> myGuifv

Hình-40. Cửa sổ giao diện.

để có cửa sổ giao diện trong Hình-40

Bước 2: Click vào nút Open, chon một file ảnh vân tay để bắt đầu trích chọn đặc

Hình-41. Mở một file ảnh.

tính.

57

PHỤ LỤC Bước 3: Click vào nút HE Enhancement để thực hiện tăng cường ảnh bằng cân

Hình-42. Cân bằng lược đồ xám.

bằng lược đồ xám.

Bước 4: Click vào nút FB Enhancement để thực hiện tăng cường ảnh bằng biên

Hình-43. Biến đổi Fourier rời rạc và cân bằng cường độ sáng.

đổi Fourier rời rạc và cân bằng cường độ sáng của ảnh.

58

PHỤ LỤC Bước 5: Click vào nút Binarization để thực hiện phân ng ưỡng cục bộ-nhị phân

Hình-44. Nhị phân hóa ảnh.

hóa ảnh.

Hình-45. Trường định hướng.

Bước 6: Click vào nút Orientation Image để ước lượng trường định hướng.

59

PHỤ LỤC

Hình-46. Segmentation.

Bước 7: Click vào nút Segmentation để khoanh lây vùng ảnh vân tay.

Hình-47. Phát hiện core.

Bước 8: Click vào nút Detection Core để tìm điểm core.

60

PHỤ LỤC

Hình-47. Làm mảnh đường vân.

Bước 9: Click vào nút Thinning để làm mảnh đường vân.

Hình-48. Lọc minutiae.

Bước 10: Click vào nút Post-processing để lọc các minutiae.

61

PHỤ LỤC

Hình-49. Hiển thị minutiae.

Bước 11: Click vào nút Display Minutiae để hiện thị các minutiae sẽ tạo mã.

Hình-50. Đối sánh vân tay.

Bước 12: Click vào nút Matching để đối sánh vân tay.

62