ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA
MẠNG

BÀI THU HOẠCH MÔN HỌC
CƠ SỞ DỮ LIỆU NÂNG CAO
ĐỀ TÀI
CƠ SỞ DỮ LIỆU ẢNH VÂN MÔIHọc viên thực hiện: Huỳnh Thị Mỹ Hồng
Mã số học viên: CH1101086
TP.HCM, năm 2012
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ
MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA
MẠNG

BÀI THU HOẠCH MÔN HỌC
CƠ SỞ DỮ LIỆU NÂNG CAO
ĐỀ TÀI
CƠ SỞ DỮ LIỆU ẢNH VÂN MÔI

GVHD: PGS.TS. Đỗ Phúc
Học viên thực hiện: Huỳnh Thị Mỹ Hồng
Mã số học viên: CH1101086
TP.HCM, năm 2012
MỤC LỤC
Trang
Chương 1: Mở đầu 1
1.1. Lời mở đầu 1

vân môi truy vấn, sau khi tìm kiếm trong cơ sở dữ liệu, sẽ đưa ra một danh sách các
ảnh vân môi gần giống với ảnh đưa vào với độ chính xác chấp nhận được.
Thành công của đề tài là cơ sở để xây dựng những hệ thống nhận dạng bằng
vân môi lớn hơn nữa, phục vụ trong các lĩnh vực an ninh, y tế,…
Qua đây, tôi xin được gửi lời cảm ơn sâu sắc đến GS.TS. Đỗ Phúc, người đã tận
tâm truyền đạt những kiến thức nền tảng cơ bản cho chúng em về môn học “Cơ sở dữ
liệu nâng cao”. Bên cạnh những kiến thức khoa học, Thầy đã giúp tôi có những phong
cách học tập, làm việc và những kinh nghiệm sống quí báu. Tôi xin bày tỏ lòng biết ơn
đến các chuyên gia cố vấn qua mạng thuộc Trung tâm phát triển CNTT – ĐH Quốc gia
TP.HCM và toàn thể các bạn bè học viên trong lớp.
1.2. Lý do chọn đề tài
Nhận dạng ảnh vân tay là một vấn đề được biết cách đây hơn 100 năm, tuy nhiên
mãi đến khi máy tính ra đời, vấn đề này mới được nghiên cứu sâu và ứng dụng rộng
rãi trong hầu hết các lĩnh vực liên quan đến an ninh, bảo mật, y tế,… Ngày nay có
nhiều nghiên cứu tìm ra các phương pháp khác nhau để phân biệt người này với người
khác. Và vân môi đã trở thành một dữ liệu sinh trắc học quan trọng để xác định tính
duy nhất chỉ mình bạn có mà thôi. Do đó, vân môi cần được nghiên cứu rộng và sâu
hơn nữa.
Trong trường hợp không thể xác định được vân tay (do mất tay, bị bỏng,…) hay
dấu vân tay thiếu độ tin cậy thì vân môi là lựa chọn tối ưu để nhận dạng và định danh
con người.

2
Trong những năm gần đây, những nghiên cứu về các đặc trưng cục bộ SIFT
(Scale-Invariant Feature Transform) dùng cho phân loại và tìm kiếm ảnh mang lại
nhiều kết quả đáng kể.
Với nhu cầu thực tiễn cùng với sự phát triển của công nghệ nhận dạng ảnh thì
việc xây dựng một cơ sở dữ liệu ảnh vân môi dùng để nhận dạng tội phạm, xác định
danh tính, chứng thực,… là cần thiết.
1.3. Ý nghĩa khoa học và thực tiễn đề tài

Theo nghiên cứu của Nguyễn Thành Kiên, đặc trưng sinh trắc được chia làm
hai loại, Hình 2.1 thể hiện những đặc trưng sinh trắc thuộc hai loại này, cụ thể là:
- Đặc trưng sinh lý: là các đặc trưng liên quan đến hình dạng, cấu tạo của
cơ thể. Ví dụ như vân tay, vân môi, khuôn mặt, vân lòng bàn tay, tĩnh mạch ngón
tay, tĩnh mạch lòng bàn tay, tròng mắt, tai, cấu tạo răng, mùi cơ thể, AND,
- Đặc trưng hành vi: là các đặc trưng liên quan đến hành động. Ví dụ như
dáng đi, giọng nói, chữ ký, hình thức gõ phím,…
Hình 2.1: Những đặc trưng sinh trắc dùng để nhận dạng
Đây là những đặc trưng sinh trắc đã được sử dụng từ lâu và rất quen thuộc với
mọi người. Bên cạnh đó, những đặc trưng sinh trắc như tròng mắt, tĩnh mạch lòng bàn

4
tay, tĩnh mạch ngón tay gần đây nhận đựợc nhiều sự quan tâm và đang trên đường trở
thành những giải pháp nhận dạng nhanh chóng hơn, chính xác hơn. Tuy nhiên đặc trưng
sinh trắc về vân môi vẫn chưa được nghiên cứu và ứng dụng nhiều.
2.1.2. Cấu tạo của một hệ thống nhận dạng sinh trắc học
Hình 2.2 trình bày các cấu tạo cơ bản của một hệ thống nhận dạng sinh trắc học
bao. Nó gồm các thành phần sau:
Hình 2.2: Cấu tạo hệ thống nhận dạng sinh trắc
-Thu nhận ảnh: thường sử dụng những thiết bị tương tác với người dùng
nhằm thu nhận các đặc điểm sinh trắc của người đó. Ví dụ một số loại thiết bị thu
nhận điển hình như: camera nhằm chụp ảnh khuôn mặt, tròng mắt, hình dáng tai;
micro dùng thu âm giọng nói; máy đọc vân tay; thiết bị thu nhận tĩnh mạch; thiết bị
phân tích AND,…
-
Xử lý: đây là khối nhằm trích và chọn ra các đặc trưng riêng biệt của
người và lưu lại thành các mẫu. Mỗi người có một mẫu riêng, chính sự duy nhất của
mỗi đặc trưng sinh trắc của mỗi người được thể hiện ở sự duy nhất của mẫu tạo ra
này. Nếu là lần đầu tiên người sử dụng đăng ký với hệ thống, mẫu tạo ra sẽ đựợc
cập nhật vào cơ sở dữ liệu mẫu. Nếu là những lần đăng nhập sau, mẫu này sẽ được

một phương tiện an toàn để xác thực danh tính tội phạm. Một trong các ứng dụng
này là thu thập vân tay tại hiện trường trong các vụ án, so sánh với các mẫu vân tay có
sẵn trong cơ sở dữ liệu để xác định danh tính của người cần điều tra.
- Giám sát: các hệ thống nhận dạng sinh trắc học được sử dụng để tự động
định vị, theo dõi và định danh người trong một khu vực nhất định. Hiện nay, các hệ
thống này bao gồm một số camera giám sát kết hợp với các đặc trưng sinh trắc để
giám sát. Khuôn mặt là đặc trưng sinh trắc được sử dụng nhiều nhất trong loại này.
Những hệ thống giám sát gần đây nhất đã có thể xác định được danh tính của người
từ khoảng cách 200m sử dụng khuôn mặt. Tròng mắt cũng đang được ứng dụng để xác
định danh tính từ khoảng cách xa. So với khuôn mặt, tròng mắt cho độ chính xác cao

6
hơn nhưng vì kích thước nhỏ nên việc thu nhận tròng mắt yêu cầu khoảng cách gần hơn.
Những hệ thống gần đây đã cho phép nhận dạng người sử dụng tròng mắt từ khoảng cách
15m.
-Xuất nhập cảnh: việc tự động hóa và tăng cường an ninh trong việc xác
thực danh tính của người xuất nhập cảnh đang ngày càng đựợc quan tâm khi số
lượng người xuất nhập cảnh đang tăng lên nhanh chóng. Hiện nay, hộ chiếu điện tử
đã trở thành một tiêu chuẩn quốc tế ICAO (International Civil Aviation Organization) và
được áp dụng rộng rãi tại hơn 70 nước bao gồm Mỹ, Liên minh Châu Âu (Anh, Pháp,
Đức, Italia, Hà Lan,…), Úc, Hàn Quốc, Singapore,… Hộ chiếu điện tử là một loại thẻ
thông minh có bộ nhớ lưu trữ các thông tin về đặc trưng sinh trắc của cá nhân có thể bao
gồm vân tay, khuôn mặt, tròng mắt.
-Chống gian lận: công nghệ nhận dạng sinh trắc học có thể được sử dụng
trong các ứng dụng công cộng nhằm kiểm soát việc một cá nhân hưởng lợi từ việc
đăng ký nhiều danh tính khác nhau. Hiện nay, Liên Hiệp Quốc đã và đang sử dụng
vân tay để kiểm soát việc trợ cấp lương thực tránh trường hợp một người có thể
gian lận trong việc nhận trợ cấp nhiều lần khi khai báo nhiều danh tính khác nhau.
-Khách du lịch tin cậy: các ứng dụng này cho phép khách du lịch đăng ký
các đặc trưng sinh trắc nhờ vân tay, tròng mắt với chương trình giúp cho những lần

- Vân máu: Các nhà khoa học sau khi phát hiện ra máu người gồm 4 nhóm
(O, A, B, AB), còn phát hiện thêm trong máu người có mấy trăm vật chất sinh hóa
do gen di truyền xác định, có thể dùng để phân biệt huyết dịch khác nhau. Các nhà
khoa học nhờ kỹ thuật xung mạch điện tử tiến hành kiểm tra tổ chức huyết dịch
trong cơ thể con người, có thể thấy đựợc những vòng giải điện mạch, tức là vân máu.
Vân máu của mỗi người cũng không giống nhau, là một yếu tố giúp phân biệt đựợc
người này với người khác.
- Vân mùi: Bởi ai cũng có mùi hơi cơ thể, khi đi khỏi, phân tử mùi hơi còn
lưu lại trong không khí nơi đã đến. Căn cứ vào hiện tượng này, cảnh sát có thể thu
lượm không khí mang về phân tích thành phần hóa học, sẽ tìm ra vân mùi mà đối
tựợng cần nhận diện để lại, sau đó “gói” vân mùi thu đựợc vào trong một miếng vải
sạch sẽ không mùi và bảo quản nơi kín đáo để cung cấp cho chó săn phân biệt, từ đó tìm
ra đối tượng nghi vấn.
- Vân tiếng: Vân thanh học là môn khoa học tương tự như môn vân tay
học. Khi phát âm, khí quản âm thanh của mỗi người một khác nhau, có những hình
dạng khác nhau và dung lượng khác nhau. Khoa học kỹ thuật hiện đại biến âm
thanh thành sóng điện, biến sóng điện thành âm thanh, thông qua phân tích, miêu tả
âm thanh dưới dạng đồ án, qua so sánh nhiều lần có thể tìm ra tiếng nói của người

8
cần tìm trong vô vàn tiếng nói khác nhau. Do đó vân tiếng có thể trở thành căn cứ
để xác định nhân thân.
2.2.1. Các công trình nghiên cứu về vân môi
Theo nghiên cứu của Võ Huỳnh Trang và Lê Văn Cường trong khoa
học hình sự, để xác định cá thể người dựa vào các đặc điểm sinh trắc học cung cấp
như: nhóm máu, giới tính, mô hình răng,… đặc biệt là dấu vân tay đã mang lại
nhiều thành công mỹ mãn. Tuy nhiên trong những trường hợp không còn đầy đủ
các bộ phận như: nạn nhân bị cắt mất tay, chân, hoặc bị bỏng mất vân tay, hay
không có hồ sơ về răng,… thì việc xác định cá thể gặp rất nhiều khó khăn. Thêm vào
đó, từ những sai lầm chết người mà chứng cứ là dấu vân tay trong một số vụ án xảy

Utsuno 2005 ở Nhật.
Các kết quả nghiên cứu đều xác nhận: giống như vân tay, vân môi ở mỗi người
mang tính đặc trưng riêng biệt. Nó củng cố cho việc sử dụng vân môi để xác định tội
phạm, nhưng lại chưa được công nhận như một bằng chứng khoa học trên tòa án. Cần có
nhiều nghiên cứu về vân môi hơn nữa nhằm tập hợp, giải thích, và chứng minh tính duy
nhất của vân môi.
2.2.2. Các dạng hình thái vân môi
Các môi trên và dưới gặp nhau tại các mép môi, còn hai đầu của khe miệng (khe
giữa các môi) gọi là góc miệng. Rãnh dọc ở giữa mặt da của môi trên gọi là “nhân
trung”. Môi không bằng phẳng mà có nhiều vết nhăn lồi, lõm, nông, sâu mà người ta gọi
là vân môi.
Theo Võ Huỳnh Trang và Lê Văn Cường [8], thì vân môi có 8 dạng đi cùng với 8
dạng viền vân môi và 3 cấu trúc đi kèm dạng rãnh.
Hình 2.3: Các dạng vân môi
Trong hình 2.3 các dạng vân môi chiếm tỷ lệ từ cao đến thấp như sau: dạng
I rãnh thẳng, dạng II rãnh phân nhánh, dạng V có hình sao, dạng VII rãnh chạy không

10
theo qui luật, dạng IV lưới rãnh, dạng III giao rãnh, dạng VI có rãnh ngang, dạng VIII
là trường hợp phần trung tâm vùng môi đỏ không có rãnh hoặc có 1-2 rãnh thẳng.
* Các dạng viền vân môi
Có 8 dạng viền vân môi như hình 2.4 chiếm tỷ lệ cao nhất là dạng lưỡi rãnh, dạng
không có rãnh hoặc ít rãnh ngang hay dọc mờ chiếm tỷ lệ thấp nhất.
Hình 2.4: Các dạng viền vân môi
* Cấu trúc đi kèm các dạng rãnh môi
Hình 2.5: Cấu trúc đi kèm dạng rãnh

11
2.3. Các phương pháp lưu trữ và nhận dạng dấu vân môi
Hai dạng thể hiện của dấu vân môi đã dẫn đến hai hướng tiếp cận vấn đề nhận dạng

lớn gần như không chấp nhận được.

13
Chương 3: KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU ĐỒ THỊ
3.1. Khái quát về đồ thị
Đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi
các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ
dưới dạng một tập các điểm (các đỉnh) nối với nhau bẳng các đoạn thẳng (các cạnh).
3.1.1. Đồ thị vô hướng
Đồ thị vô hướng G là một cặp có thứ tự (ordered pair) G:=(V, E), trong đó:
• V: tập các đỉnh hoặc nút.
• E: tập các cặp không thứ tự chứa các đỉnh phân biệt, được gọi là cạnh.
Hai đỉnh thuộc một cạnh được gọi là các đỉnh đầu cuối của cạnh đó.
Trong nhiều tài liệu, tập các cạnh bao gồm cả các cặp đỉnh không phân biệt,
các cạnh này được gọi là các khuyên. V (và E) thường là các tập hữu hạn, phần
lớn các kết quả nghiên cứu đã biết không đúng (hoặc khác) khi áp dụng cho đồ thị
vô hạn (infinite graph) vì nhiều luận cứ không dùng được trong trường hợp vô
hạn.
3.1.2. Đồ thị có hướng
Đồ thị có hướng G là một cặp có thứ tự G:=(V, A), trong đó:
• V: tập các đỉnh hoặc nút.
•
A: tập các cặp có thứ tự chứa các đỉnh, được gọi là các cạnh có hướng
hoặc
cung. Một cạnh e = (x, y) được coi là có hướng từ x tới y; x được
gọi là điểm
đầu/gốc và y được gọi là điểm cuối/ngọn của cạnh.
3.1.3. Đơn đồ thị và Đa đồ thị
Đơn đồ thị: là đồ thị mà giữa hai đỉnh chỉ có tối đa một cạnh.
Đa đồ thị: là đồ thị mà giữa hai đỉnh có thể có nhiều hơn một cạnh.

một đồ thị có hướng như sau: các đỉnh là các trang web hiện có tại
website, tồn tại
một cạnh có hướng nối từ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết tới B.
Do vậy, sự phát triển của các thuật toán xử lý đồ thị là một trong các mối quan tâm
chính của khoa học máy tính.
Trong lý thuyết phạm trù (category theory) một phạm trù có thể được coi là
một
đa đồ thị có hướng với các đối tượng là các đỉnh và các morphism là các
cạnh có
hướng. Khi đó, các hàm tử (functor) giữa các phạm trù là một số (nhưng không nhất
thiết tất cả) digraph morphism.
Trong Khoa học máy tính đồ thị có hướng được dùng để biểu diễn các ô-tô-
mát hữu hạn (finite state machine) và nhiều cấu trúc rời rạc khác.
Một quan hệ đôi (binary relation) R trên tập X là một đồ thị đơn có hướng. Hai
đỉnh x,y của X được nối với nhau bởi một cung nếu xRy.

15
3.2. Cơ sở dữ liệu đồ thị
3.2.1. Đồ thị có nhãn
Đồ thị có nhãn là một bộ sáu G = (V, E, V
L
, λ, V
I
, δ), trong đó:
• V là tập các đỉnh.
• E là tập các cạnh.
• V
L
là tập các nhãn đỉnh.
• V

i
là một đồ thị có nhãn. Hình sau định nghĩa một cơ sở dữ liệu
đồ thị:

16
Hình 3.2: Một cơ sở dữ liệu đồ thị
3.2.3. Đồ thị con
Cho G và G’ là hai đồ thị:
G = (V, E, V
L
, λ, V
I
, δ) và G’ = (V’, E’, V
L
’, λ’, V
I
’δ’) G’ là đồ thị con của G, ký
hiệu là G’
⊆
G, nếu:
• V’
⊆
V
• E’
⊆
E
•
∀
 v
∈

F là điều kiện truy vấn (chọn) và F có thể là đẳng cấu đồ thị, đẳng cấu đồ thị con,
bao hàm đồ thị, tương đồng đồ thị hoặc các điều kiện khác.

18
3.3.2. Phép chiếu đồ thị
Đồ thị rút gọn: Cho G = (V, E) là một đồ thị và X
⊂
V, đồ thị rút gọn của G trên
X được định nghĩa là một đồ thị G’(V’, E’) , trong đó:
V’ = X
E’ = V’×V’
∩
E
Phép chiếu đồ thị: Cho GD là một cơ sở dữ liệu đồ thị, và X là một tập các
đỉnh truy vấn (X
⊂
V). Phép chiếu đồ thị trên GD sẽ trả về một tập các đồ thị,
trong đó:
Π
x (GD) = {G’ | G’ là đồ thị rút gọn của G trên X}
3.3.3. Phép hợp đồ thị
Hợp của hai đồ thị G1, G2 (G = G1
∪
G2) với những đỉnh phân biệt V1, V2
(V1
∩
V2 =
φ
) sẽ sinh ra một đồ thị G với tập đỉnh V = V1
∪

φ
), phép kết đồ thị G = G1+G2 được định nghĩa là

19
hợp của G1 và G2 với tất cả các cạnh được tạo ra bằng cách kết hợp tất cả đỉnh V1 với
tất cả đỉnh V2 với nhau.
3.4. Ứng dụng của cơ sở dữ liệu đồ thị
Cơ sở dữ liệu đồ thị giúp các đối tượng rời rạc được gắn kết và mô hình hóa trong
không gian đa chiều. Theo đó, việc truy vấn dữ liệu không chỉ dựa trên các vector
thông số đơn thuần mà chủ yếu dựa trên các đặc điểm của mô hình không gian được tạo
nên bới sự liên kết của các đối tượng. Điều này rất hữu ích trong việc nhận dạng mẫu,
dự đoán tính chất thông qua kết cấu, khai phá dữ liệu,…
Việc đồ thị hóa những dữ liệu hình ảnh, văn bản cũng giúp tiết kiệm đáng kể
không gian lưu trữ, rút ngắn thời gian truy xuất và xử lý. Đồng thời những thông tin
dưới dạng đồ thị hữu ích hơn nhiều so với dữ liệu thô 2 chiều, tăng hiệu năng tính toán
đồng thời tạo ra thêm nhiều ứng dụng cho khối thông tin này.
3.4.1. Hệ thống thông tin địa lý
Hệ thống thông tin địa lý là hệ thống quản lý, phân tích và hiển thị tri thức địa lý,
tri thức này được thể hiện qua các tập thông tin:
- Các bản đồ: giao diện trực tuyến với dữ liệu địa lý để tra cứu, trình bày kết quả
và sử dụng như là một nền thao tác với thế giới thực.
- Các tập thông tin địa lý: thông tin địa lý dạng file và dạng cơ sở dữ liệu gồm
các yếu tố, mạng lưới, topology, địa hình, thuộc tính.
- Các mô hình xử lý: tập hợp các quy trình xử lý để phân tích tự động.
- Các mô hình dữ liệu: GIS cung cấp công cụ mạnh hơn là một cơ sở dữ liệu
thông thường bao gồm quy tắc và sự toàn vẹn giống như các hệ thông tin
khác. Lược đồ, quy tắc và sự toàn vẹn của dữ liệu địa lý đóng vai trò quan
trọng.
- Metadata: hay tài liệu miêu tả dữ liệu, cho phép người sử dụng tổ chức, tìm
hiểu và truy nhập được tới tri thức địa lý.

dạng một đồ thị, trong đó đỉnh là các đối tượng (khái niệm) còn các cung cho biết mối
quan hệ giữa các đối tượng (khái niệm) này.
Do mạng ngữ nghĩa là một loại đồ thị cho nên nó thừa hưởng được tất cả những
mặt mạnh của công cụ này. Nghĩa là ta có thể dùng những thuật toán của đồ thị trên
mạng ngữ nghĩa như thuật toán tìm liên thông, tìm đường đi ngắn nhất, để thực hiện
các cơ chế suy luận. Điểm đặc biệt của mạng ngữ nghĩa so với đồ thị thông thường
chính là việc gán một ý nghĩa (có, làm, là, biết, ) cho các cung. Trong đồ thị tiêu
chuẩn, việc có một cung nối giữa hai đỉnh chỉ cho biết có sự liên hệ giữa hai đỉnh đó và
tất cả các cung trong đồ thị đều biểu diễn cho cùng một loại liên hệ. Trong mạng ngữ