ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG HÀ HẢI NAM

NGHIÊN CỨU KĨ THUẬT SIFT TRONG TRÍCH TRỌN
ĐẶC TRƯNG, XÂY DỰNG ỨNG DỤNG TÌM KIẾM ẢNH

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

Thái Nguyên, 2018


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG HÀ HẢI NAM

NGHIÊN CỨU KĨ THUẬT SIFT TRONG TRÍCH TRỌN
ĐẶC TRƯNG, XÂY DỰNG ỨNG DỤNG TÌM KIẾM ẢNH

Chuyên ngành: Khoa học máy tính
Mã số: 8 480 101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: TS. Vũ Vinh Quang

Thái Nguyên, 2018


LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số
liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố
trong bất kì công trình nào khác.
Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này
đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ
nguồn gốc.
Thái Nguyên, ngày 26 tháng 6 năm 2018
Tác giả luận văn

Hoàng Hà Hải Nam

i


LỜI CẢM ƠN
Trước hết, với lòng kính trọng và biết ơn sâu sắc, tôi xin gửi lời cảm ơn
tới Tiến sĩ Vũ Vinh Quang – người đã tận tình hướng dẫn tôi trong suốt quá
trình tìm hiểu, nghiên cứu và hoàn thiện luận văn.
Tôi xin gửi lời cảm ơn chân thành tới Ban giám hiệu nhà trường và các
thầy cô đã trực tiếp giảng dạy, giúp đỡ tôi trong suốt thời gian học tập, nghiên
cứu khoa học.
Cuối cùng, tôi xin gửi lời cảm ơn đến gia đình, người thân, bạn bè,
đồng nghiệp đã giúp đỡ, tạo mọi điều kiện thuận lợi cho tôi trong suốt thời
gian học tập và hoàn thiện luận văn này.
Thái Nguyên, ngày 26 tháng 6 năm 2018
Tác giả luận văn

Hoàng Hà Hải Nam

ii



DANH MỤC CÁC HÌNH ẢNH
Hình 1.1: Kiến trúc chung của một MMDBMS........................................................ 10
Hình 1.2: Mô hình hệ thống Tra cứu ảnh theo nội dung ........................................... 16
Hình 2.1: Ví dụ hiển thị một ảnh............................................................................... 21
Hình 2.2: Truy vấn của Google “5D3” ..................................................................... 23
Hình 2.3: Truy vấn của Google “Apple” .................................................................. 23
Hình 2.4: Một số loại kết cấu .................................................................................... 24
Hình 2.5: Một kết quả trả về của Google Image ....................................................... 25
Hình 2.6: Một kết quả trả về của Bing ...................................................................... 25
Hình 2.7: Một kết quả trả về của Flickr Images Search............................................ 26
Hình 2.8: Biểu đồ mô phỏng việc tính toán các DoG ảnh từ các ảnh kề mờ ............
35
Hình 2.9: Mỗi điểm ảnh được so sánh với 26 láng giềng của nó.............................. 36
Hình 2.10: Số lượng mẫu tỷ lệ trên mỗi Octave ....................................................... 36
Hình 2.11: Quá trình lựa chọn các điểm hấp dẫn...................................................... 38
Hình 2.12: Biểu diễn các vector đặc trưng................................................................ 41
Bảng 2.13: Một số phương pháp lựa chọn đặc trưng ................................................ 42
Hình 2.14: Mô hình hệ thống IVFADCj; Hệ thống bên trái: chèn một vector vào
danh sách chỉ mục ngược; hệ thống bên phải: tìm kiếm k láng giềng
gần nhất. ................................................................................................ 50
Hình 2.15: Mô hình giải quyết bài toán .................................................................... 52
Hình 3.1: Tập dữ liệu ảnh thử nghiệm ...................................................................... 55
Hình 3.2: Người dùng chọn ảnh truy vấn.................................................................. 56
Hình 3.3: Đặc trưng SIFT của ảnh được trích chọn .................................................. 57
Hình 3.4: 20 ảnh tương đồng với ảnh truy vấn ......................................................... 57
Hình 3.5: Kết quả trả về với truy vấn IphoneX......................................................... 58
Hình 3.6: Kết quả trả về với truy vấn Apple ............................................................. 58
Hình 3.7: Một số kết quả truy vấn khác .................................................................... 59


iii


DANH MỤC CÁC BẢNG BIỂU

Bảng 1.1: Mô tả kích thước kiểu dữ liệu.....................................................................6
Bảng 3.1: Cấu hình phần cứng sử dụng trong thực nghiệm......................................54
Bảng 3.2: Công cụ phần mềm sử dụng trong thực nghiệm.......................................54
Bảng 3.3: Một số thư viện sử dụng trong thực nghiệm ............................................55
Bảng 3.4: Kết quả độ chính xác trung bình của 10 truy vấn.....................................60

iv


DANH MỤC CÁC TỪ VIẾT TẮT
Từ viết tắt

Tiếng Anh

Tiếng Việt

AI

Artificial intelligence

Trí tuệ nhân tạo

AR


Augmented reality

Tương tác thực tại ảo

CSDL

Database

Cơ sở dữ liệu

DBMS

Database Management System Hệ quản trị cơ sở dữ liệu

IoT

Internet of things

Internet vạn vật

Information Retrieval

Hệ thống tự động truy tìm

IR
MIRS
MMDBMS

thông tin
Multimedia Indexing &


Hệ thống chỉ mục và truy tìm

Retrieval System

thông tin đa phương tiện

Multimedia Database

Hệ thống quản trị cơ sở dữ

Management System

liệu đa phương tiện

MRI

Magnetic Resonance Imaging

VR

Virtual reality

WWW

World Wide Web

Thực tế ảo

v



MỤC LỤC

LỜI CAM ĐOAN ............................................................................................. i
LỜI CẢM ƠN .................................................................................................. ii
DANH MỤC CÁC HÌNH ẢNH .................................................................... iii
DANH MỤC CÁC BẢNG BIỂU .................................................................. iv
DANH MỤC CÁC TỪ VIẾT TẮT ................................................................ v
MỤC LỤC ....................................................................................................... vi
MỞ ĐẦU .......................................................................................................... 1
CHƯƠNG 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU ĐA PHƯƠNG TIỆN 2
1.1. Tổng quan về hệ quản trị cơ sở dữ liệu đa phương tiện .......................................
2
1.1.1.
Giới
thiệu
.........................................................................................................2
1.1.2.
Các
kiểu
truyền
.......................................................................5
1.1.3. Hệ quản trị cơ
..........................................7

sở

dữ


thông
liệu

đa

1.1.4.
Truy
tìm
thông
tin
............................................................................8

chung
và

phương
tài

multimedia

tiện

(MMDBMS)

liệu

văn

1.1.5.
Truy

xuất
và
chỉ
multimedia..........................................................................9

số

bản
hoá

1.2. Kiến trúc tổ chức nội dung của một hệ thống cơ sở dữ liệu Multimedia........... 10
1.2.1. Kiến trúc hệ thống quản trị cơ sở dữ liệu đa phương tiện
.....................................10
1.2.2. Tổ chức dữ liệu đa phương tiện trên cơ sở nguyên lý thống
nhất.........................12
1.2.3.
Cấu
trúc
tóm
.............................................................................................14

tắt

media

1.3. Tổng quan về tra cứu ảnh ...................................................................................
15
1.3.1.
Mô
hình

hệ
thống
.........................................................16
1.3.2. Một số hệ thống
biểu.............................................17

tra

tra

cứu

cứu
ảnh

ảnh
theo

theo
nội

nội
dung

dung
tiêu

CHƯƠNG 2. TRÍCH CHỌN ĐẶC TRƯNG ẢNH .................................... 20
vi



2.1. Tổng quan về trích chọn đặc trưng ảnh.............................................................. 20
2.1.1. Đặc trưng văn bản đi kèm ảnh và tìm kiếm ảnh theo văn bản đi kèm ảnh
..........20
2.1.2. Đặc trưng nội
dung..............................23

dung

ảnh

và

tìm

kiếm

theo

đặc

trưng

nội

2.2. Các phương pháp trích chọn đặc trưng ảnh và độ đo tương đồng giữa các ảnh 26
2.2.1.
Đặc
trưng
sắc....................................................................................................27

2.2.2.
Đặc
trưng
kết
.....................................................................................................29
2.2.3.
Đặc
trưng
dạng.................................................................................................30

vi

màu
cấu
hình


2.2.4. Đặc trưng cục bộ bất biến SIFT
..............................................................................31
2.2.5. Lựa chọn đặc trưng ..................................................................................................42
2.3. Mô hình k láng giềng gần nhất sử dụng bộ lượng tử hóa .................................. 44
2.3.1. Cơ sở lý thuyết .........................................................................................................45
2.3.2. Thuật toán K láng giềng
..........................................................................................50
2.3.3. Mô hình bài toán ......................................................................................................51

CHƯƠNG 3. THỰC NGHIỆM VÀ ĐÁNH GIÁ ....................................... 54
3.1. Bài toán truy vấn ảnh ......................................................................................... 54
3.1.1. Phát biểu bài toán
.....................................................................................................54

3.1.2. Cách giải quyết bài
toán...........................................................................................54
3.2. Môi trường và các công cụ sử dụng cho thực nghiệm ....................................... 54
3.2.1. Cấu hình phần cứng .................................................................................................54
3.2.2. Công cụ phần mềm sử dụng
....................................................................................54
3.2.3. Thư viện sử dụng......................................................................................................55
3.3. Xây dựng tập dữ liệu ảnh ................................................................................... 55
3.4. Quy trình, phương pháp thực nghiệm ................................................................ 56
3.5. Kết quả thực nghiệm .......................................................................................... 59

KẾT LUẬN .................................................................................................... 62
TÀI LIỆU THAM KHẢO ............................................................................ 63

vii


MỞ ĐẦU
Cuộc cách mạng công nghiệp lần thứ tư diễn ra từ những năm 2000
được gọi là cuộc cách mạng số, thông qua các công nghệ như Internet vạn vật
(IoT), trí tuệ nhân tạo (AI), thực tế ảo (VR), tương tác thực tại ảo (AR), mạng
xã hội, điện toán đám mây, di động, phân tích dữ liệu lớn... để chuyển hóa
toàn bộ thế giới thực thành thế giới số.
Sự phát triển mạnh mẽ của công nghệ ảnh số đã làm lượng ảnh lưu trữ
tăng lên một cách nhanh chóng đòi hỏi phải có các công cụ hỗ trợ tìm kiếm
ảnh hiệu quả và tiện lợi. Mặc dù các công cụ tìm kiếm ảnh theo văn bản đi
kèm ảnh ra đời cho phép người dùng tìm kiếm ảnh với thời gian đáp ứng khá
nhanh, tuy nhiên, các công cụ này vẫn còn hạn chế trong việc giải quyết sự
không thống nhất giữa nội dung câu truy vấn và nội dung hiển thị của ảnh trả
về. Sự ra đời của các công cụ tìm kiếm ảnh theo nội dung ảnh đã giải quyết

được những hạn chế nêu trên. Từ những lí do trên, tôi chọn đề tài Nghiên cứu
kĩ thuật SIFT trong trích trọn đặc trưng, xây dựng ứng dụng tìm kiếm ảnh.

Mục tiêu của luận văn là nghiên cứu đặc trưng SIFT để tối ưu hóa chất
lượng tìm kiếm ảnh. Nội dung chính của luận văn tập trung khảo sát phương
pháp trích chọn đặc trưng ảnh trong tìm kiếm và xếp hạng ảnh. Trên cơ sở
ứng dụng phương pháp lượng tử hóa tích của Hervé Jégou và cộng sự [3],
luận văn nghiên cứu mô hình tìm kiếm K láng giềng gần nhất kết hợp độ đo
tương đồng về khoảng cách giữa các vector đặc trưng, từ đó tiến hành xây
dựng mô hình thực nghiệm tìm kiếm ảnh sản phẩm trên phần mềm Matlab.
Luận văn bao gồm các nội dung sau:
Chương 1: Tổng quan về cơ sở dữ liệu đa phương tiện
Chương 2: Trích chọn đặc trưng ảnh
Chương 3: Thực nghiệm và đánh giá

1


CHƯƠNG 1
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU ĐA PHƯƠNG TIỆN
1.1. Tổng quan về hệ quản trị cơ sở dữ liệu đa phương tiện

1.1.1. Giới thiệu chung
Thế giới đang bước vào cuộc cách mạng công nghiệp lần thứ tư – một
cuộc cách mạng sản xuất mới gắn liền với những đột phá chưa từng có về
công nghệ, liên quan đến kết nối Internet, điện toán đám mây, in 3D, công
nghệ cảm biến, thực tại ảo... Bản chất của cách mạng công nghiệp lần thứ tư
là dựa trên nền tảng công nghệ số và tích hợp tất cả các công nghệ thông minh
để tối ưu hóa quy trình, phương thức sản xuất. Trong những năm gần đây, nhu
cầu về khai thác và xử lý dữ liệu vô cùng lớn, điều đó không dễ dàng diễn tả

được chỉ với việc sử dụng các ký tự. Các kiểu dữ liệu có thể là hình ảnh,
video, tài liệu, âm thanh (dữ liệu Media). Multimedia là tập hợp các kiểu
media được sử dụng với nhau (dữ liệu đa phương tiện).
Hệ quản trị cơ sở dữ liệu (CSDL) đa phương tiện (Multimedia
DataBase Management System – MMDBMS) là một hệ thống giúp người
dùng thao tác trên các dữ liệu media một cách thích hợp và hiệu quả. Các thao
tác cơ bản của hệ quản trị CSDL thường là cập nhật, chèn, xoá và tìm kiếm
một đối tượng trong CSDL. Như vậy, có thể nói rằng CSDL đa phương tiện là
tập hợp các dữ liệu đa phương tiện có liên quan với nhau [1]. Các kiểu dữ liệu
thông thường của một CSDL đa phương tiện bao gồm:
Dữ liệu hình ảnh (Image data): Bao gồm ảnh đen trắng, ảnh xám, ảnh
màu. Dữ liệu hình ảnh có nhiều định dạng khác nhau (bmp, jpg, gif, png…).
Ví dụ, một học viên phẫu thuật muốn thực hành một ca phẫu thuật trên một
bệnh nhân ảo có những triệu chứng sinh lý nào đó. Trong thực tế, để tìm ra
bệnh nhân với những triệu chứng mong muốn, học viên phẫu thuật phải truy
vấn CSDL ảnh phân tán và kích thước lớn chứa ảnh X quang hay MRI
(Magnetic Resonance Imaging) của các bệnh nhân với các triệu chứng tương
tự.
2


Dữ liệu Video (Video data): Là một chuỗi các hình ảnh liên tục nhau,
đòi hỏi dung lượng lưu trữ lớn. Cùng với sự phát triển bùng nổ của các thiết
bị nghe nhìn hiện đại như: Máy tính bảng, máy ảnh kĩ thuật số, điện thoại
thông minh… thì kiểu dữ liệu Video đang ngày càng phổ biến khắp mọi nơi.
Bên cạnh đó, sự bùng nổ của mạng xã hội cùng các hệ thống chia sẻ video
trực tuyến như Youtube1, Vimeo2, DailyMotion3… giúp cho việc lưu trữ các
dữ liệu Video không còn là bài toán khó. Do đó, việc truy xuất dữ liệu để tìm
kiếm thông tin theo yêu cầu trong kho dữ liệu khổng lồ như vậy là một vấn đề
rất đáng quan tâm.

Giả sử, cảnh sát giao thông muốn tìm kiếm những tư liệu băng hình về
một vụ tai nạn giao thông nào đó tại vị trí có camera theo dõi được lưu trữ
trong máy chủ. Như vậy, đòi hỏi phải truy vấn thư viện băng hình mà nó bao
gồm tập hợp vô số các băng hình tại vị trí đó.
Dữ liệu âm thanh (Audio data): Dữ liệu âm thanh được sử dụng trong
những ứng dụng, thiết bị như nhận dạng giọng nói, xử lý âm thanh, điều khiển
thiết bị bằng giọng nói. Ví dụ: hệ thống điều khiển xe lăn cho người tàn tật.
Trong trường hợp này cần phải tập hợp các đoạn audio là các lệnh điều khiển
cho xe di chuyển bằng giọng nói.
Dữ liệu tài liệu (Document data): Là loại dữ liệu có mặt hầu hết trong
các ứng dụng đa phương tiện nhằm giải thích thêm cho các dữ liệu không
phải văn bản, bao gồm: Các từ, câu, đoạn văn... Một CSDL tài liệu khác văn
bản ở chỗ nó không chỉ chứa các thông tin dạng văn bản thô mà còn chứa
đựng cả cấu trúc và hình ảnh nhúng. Ví dụ: khi ta xem sách, trong sách không
chỉ có dữ liệu văn bản mà còn bao gồm cả hình ảnh. Giả sử, khi người đọc
muốn tìm một bức ảnh nào đó nhưng không thể tìm trong CSDL ảnh. Tuy
nhiên, nếu có một thư viện điện tử số để truy cập thì việc tìm thấy bức ảnh
1

Youtube.com
Vimeo.com
3
Dailymotion.com
2

3


mong muốn là rất dễ dàng. Như vậy, dữ liệu tài liệu bao gồm các phương
tiện quan trọng mà trong đó các thông tin có thể được lưu trữ dưới dạng điện

tử [2].
Những năm trước đây, nhiều dữ liệu dạng văn bản (text) được lưu trữ
dưới khuôn dạng máy tính có thể lưu trữ và xử lý. Từ đó dẫn tới phát triển các
hệ thống quản trị CSDL mà ngày nay được sử dụng trong hầu hết các cơ
quan, tổ chức. Tuy nhiên, các hệ quản trị CSDL này không thể quản lý dữ liệu
đa phương tiện một cách hiệu quả bởi vì tính chất của dữ liệu văn bản và dữ
liệu đa phương tiện là khác nhau, và CSDL đa phương tiện với các dữ liệu
ảnh, video, âm thanh... thường là rất lớn. Do vậy, việc nghiên cứu phát triển
hệ thống quản trị CSDL có khả năng quản lý dữ liệu đa phương tiện với các
kỹ thuật truy tìm và chỉ mục mới là rất cần thiết. MMDBMS là một khung
làm việc để quản lý các kiểu dữ liệu khác nhau mà chúng được thể hiện trong
rất nhiều khuôn dạng khác nhau. Để làm việc thành công thì một MMDBMS
phải có các khả năng sau:
Có khả năng truy vấn đồng bộ dữ liệu (dữ liệu media và dữ liệu văn
bản) được thể hiện trong các định dạng khác nhau. Ví dụ: một MMDBMS sẽ
có khả năng truy vấn và tích hợp dữ liệu mà nó được lưu trong các CSDL
khác nhau mà có thể sử dụng các lược đồ khác nhau, cũng như việc truy vấn
tệp và dữ liệu lưu trữ trong DBMS hướng đối tượng hay DBMS không gian.
Việc xử lý các truy vấn như vậy là khá phức tạp vì trên thực tế việc nhận biết
được nội dung của các kiểu media là vấn đề thách thức, nó phụ thuộc rất
nhiều vào kiểu dữ liệu và cách thức lưu trữ chúng. Cuối cùng, truy vấn có thể
mở rộng đối với nhiều kiểu vật mang (media) dữ liệu và MMDBMS phải có
khả năng kết hợp các kết quả từ các nguồn dữ liệu khác nhau và các kiểu
media khác nhau.
Có khả năng truy vấn dữ liệu biểu diễn trong media khác nhau. Ví dụ:
một MMDBMS phải có khả năng truy vấn không chỉ trong CSDL hình ảnh

4



mà còn cả trong CSDL âm thanh và CSDL quan hệ, sau đó kết hợp các kết
quả với nhau.
MMDBMS phải có khả năng khai thác các đối tượng mang tin (media)
từ một thiết bị lưu trữ cục bộ một cách trơn tru bởi vì các đối tượng mang tin
(video, âm thanh…) thường chiếm một không gian vô cùng lớn.
MMDBMS phải có khả năng tạo ra các câu trả lời từ truy vấn và có
khả năng trình diễn các câu trả lời này bằng các phương tiện nghe nhìn.
Mỗi một hệ thống có đầy đủ các đặc tính yêu cầu trên là chưa đủ mà
còn cần phải có khả năng phân phối các trình diễn theo một cách nào đó nhằm
thoả mãn các yêu cầu khác nhau về chất lượng thể hiện của các thiết bị.

1.1.2. Các kiểu truyền thông và multimedia
Đa phương tiện (multimedia) là một lĩnh vực của Công nghệ thông tin
có mục đích nghiên cứu và đề xuất các công cụ trợ giúp việc xử lý lưu trữ,
truyền các dữ liệu thích hợp như: văn bản (text), biểu đồ, đồ thị (graphic),
hoạt hình (animation), ảnh (image), video, audio, hoặc kết hợp các media với
nhau (video + audio + văn bản diễn giải)...
Người ta thường phân media thành hai loại dựa trên quan hệ của chúng
với thời gian, đó là:
Đa phương tiện tĩnh (Static media): Không có chiều thời gian. Thông tin
không liên quan tới thời gian. Ví dụ cho loại này là văn bản, hình họa, ảnh
chụp.
Đa phương tiện động (Dynamic media): Có chiều thời gian. Thông tin
có quan hệ chặt chẽ với thời gian và thông tin phải được trình diễn với thời
gian xác định. Ví dụ các loại audio, video, animation...
So với dữ liệu truyền thống như văn bản và số, dữ liệu đa phương tiện
có một số đặc điểm rất khác biệt, đó là:
Kích thước dữ liệu lớn: dữ liệu đa phương tiện có kích thước lớn hơn
nhiều so với các kiểu dữ liệu số và văn bản thông thường. Một văn bản thô có
200 từ (khoảng 1000 ký tự) chỉ có kích thước là 1kByte, nhưng nếu lưu văn

5


bản đó bằng định dạng ảnh GIF thì kích thước gấp khoảng 10 lần. Một giọng
nói đơn sắc được lưu với định dạng .WAV trong thời gian 1 phút có kích
thước khoảng 2640 kByte (đã nén) hoặc xấp xỉ 6 -8 MB (chưa nén). Một
cảnh video rất ngắn chứa hàng trăm bức ảnh với kích thước có thể lên đến
vài chục MB...
Cụ thể, có thể xem bảng minh họa sau:
Bảng 1.1: Mô tả kích thước kiểu dữ liệu
Kiểu

Mô tả

Kích thước

Plain text

khoảng 200 từ (1000 ký tự)

1 Kb

Tệp Word

khoảng 200 từ (1000 ký tự)

15 Kb

Ảnh GIF


khoảng 200 từ (1000 ký tự, 210 x 100mm) 10 Kb

Âm thanh WAVE

giọng nói (1 phút, 22KHz, 16 bit, mono)

2640 Kb

Video

Video (1 phút, độ phân giải 740*480)

20 Mb

Số lượng dữ liệu đồ sộ: người ta ước tính, chỉ riêng trên WWW có số
lượng lên đến hàng tỉ ảnh, hàng trăm triệu bài hát MP3 và vài chục triệu
phim video.
 Một số dữ liệu đa phương tiện phụ thuộc thời gian
Audio và video có thêm chiều thời gian. Khi trình diễn audio và video
thì chất lượng của chúng phụ thuộc chặt chẽ vào tốc độ trình diễn.
Ví dụ: video phải được trình diễn với tốc độ 25 đến 30 hình/giây để có
thể cảm nhận được hình ảnh chuyển động tốt.
 Tìm kiếm dựa trên cơ sở tương tự
Trong cơ sở dữ liệu quan hệ, phương pháp tìm kiếm truyền thống đối
với dữ liệu dạng văn bản và số là tìm kiếm chính xác. Đối với dữ liệu đa
phương tiện, người dùng thường đặt ra yêu cầu tìm kiếm một đối tượng tương
tự theo nội dung mà họ đưa ra.
6



1.1.3. Hệ quản trị cơ sở dữ liệu đa phương tiện (MMDBMS)
Trung tâm của một hệ thống thông tin multimedia chính là hệ quản trị
CSDL MULTIMEDIA (MDBMS). Theo truyền thống, một CSDL bao gồm
một bộ các dữ có liên quan về một thực thể cho trước hoặc một hệ quản trị
CSDL (DBMS) là một bộ các dữ liệu có liên quan đến nhau với một tập hợp
các chương trình được dùng để khai báo, tạo lập, lưu trữ, và khai thác CSDL.
Tương tự như vậy, chúng ta có thể xem một CSDL MULTIMEDIA là một tập
các loại dữ liệu multimedia như văn bản, hình ảnh, video, âm thanh, các đối
tượng đồ hoạ… Một hệ quản trị CSDL MULTIMEDIA (MDBMS) cung cấp
hỗ trợ cho các loại dữ liệu MULTIMEDIA trong việc tạo lập, lưu trữ, truy
cập, truy vấn và kiểm soát [2].
Sự khác nhau của các kiểu dữ liệu trong CSDL MULTIMEDIA có thể
đòi hỏi các phương thức đặc biệt để tối ưu hoá việc lưu trữ, truy cập, chỉ số
hoá và khai thác. MDBMS cần phải cung cấp các yêu cầu đặc biệt này bằng
cách cung cấp các cơ chế tóm tắt bậc cao để quản lý các kiểu dữ liệu khác
nhau cũng như các giao diện thích hợp để thể hiện chúng.
Các yêu cầu của MDBMS:
 Các phương pháp tìm kiếm dựa theo mô tả: ví dụ, người dùng có thể đưa
ra một mô tả để tìm kiếm “tiếng chuông điện thoại”.
 Giao diện người dùng độc lập với thiết bị: người dùng không cần biết cách
thức lưu trữ dữ liệu đa phương tiện như thế nào.
 Giao diện người dùng độc lập với các định dạng: các truy vấn dữ liệu đa
phương tiện có thể độc lập với định dạng dữ liệu. Nó cho phép có thể sử
dụng các kỹ thuật lưu trữ mới mà không cần thay đổi ứng dụng cơ sở dữ
liệu hiện có.
 Cho phép thực hiện nhiều truy cập dữ liệu đồng thời: dữ liệu đa phương
tiện có thể truy cập đồng thời qua nhiều câu truy vấn khác nhau bởi một số

7



ứng dụng. Cách truy cập nhất quán nhằm chia sẻ dữ liệu có thể được thực
hiện và cần có cơ chế để thỏa mãn, tránh việc tạo ra các xung đột.
 Quản lý một lượng dữ liệu lớn: hệ thống cần phải có khả năng lưu trữ,
quản lý một lượng dữ liệu lớn và thỏa mãn các truy vấn đối với các quan
hệ của dữ liệu.
 Vấn đề truyền dữ liệu đa phương tiện dựa trên thời gian thực: điều khiển
việc đọc/ghi dữ liệu liên tục phải được thực hiện dựa trên thời gian thực.
Do lượng dữ liệu có thể là rất lớn (ví dụ: truyền video) nên việc truyền dữ
liệu có thể tốn nhiều thời gian và đòi hỏi phải được thực hiện một cách
chính xác.

1.1.4. Truy tìm thông tin tài liệu văn bản
Truy tìm thông tin – Information Retrieval (IR) là kỹ thuật tìm kiếm
thông tin được lưu trữ trên máy tính. Đối với dữ liệu đa phương tiện, việc truy
tìm thông tin hiệu quả là dựa trên tìm kiếm tương tự. Hệ thống lưu trữ một tập
các đối tượng đa phương tiện trong cơ sở dữ liệu. Người dùng đưa ra các truy
vấn và hệ thống tìm ra các đối tượng tương tự truy vấn trong cơ sở dữ liệu đã
lưu trữ thỏa mãn yêu cầu của người dùng. Truy tìm thông tin trong
MMDBMS có một số đặc điểm sau đây:
 Sử dụng một khối lượng dữ liệu đặc tả lớn và phức tạp.
 Việc tiếp cận IR chủ yếu dựa trên các đặc trưng.
 Các dữ liệu thường có kích thước lớn.
 Sự cần thiết phải có các kỹ thuật chỉ mục dữ liệu kích thước lớn để xử
lý các truy vấn một cách hiệu quả và thực hiện nhanh hơn so với
phương pháp tìm kiếm tuần tự.
 Sự cần thiết phải tích hợp các đặc trưng media phức tạp một cách
thường xuyên (ví dụ, dữ liệu ảnh có thể chứa các đặc trưng như: hình
dạng, biểu đồ màu, kết cấu...).
8



Ý tưởng của phương pháp tìm kiếm tương tự đưa ra như sau:
Cho một tập các đối tượng đa phương tiện trong MMDBMS.
Tìm ra một hoặc một số K đối tượng tương tự (giống) nhất với đối
tượng truy vấn mong muốn một cách nhanh chóng.

1.1.5. Truy xuất và chỉ số hoá multimedia
Các DBMS truy xuất các khoản mục dựa trên số liệu có cấu trúc khi sử
dụng kết nối chính xác. IR cũng được gọi là truy xuất dựa trên văn bản. Việc
truy xuất dựa vào nội dung đề cập đến việc truy xuất dựa trên những nét đặc
trưng truyền thống hiện nay như là màu sắc, hình dạng thay cho lời giải thích
văn bản về khoản mục truyền thông đó.
Việc truy xuất dựa trên nội dung là chuẩn dựa trên sự đồng dạng thay vì
một kết nối chính xác giữa một truy vấn và một tập các khoản mục dữ liệu.
MIRS đề cập đến một hệ thống cơ sở cung cấp việc truy xuất thông tin
multimedia khi sử dụng một tổ hợp DBMS, IR và các kỹ thuật truy xuất dựa
trên nội dung. Trong một MIRS, một vài vấn đề như phiên bản và điều khiển
an toàn có thể không thực hiện được đầy đủ. Một MIRS đủ bản lĩnh ra đời
được gọi là MDBMS.
Ví dụ: một video tài liệu cần phải sử dụng video, hình ảnh, văn từ, âm
thanh, lời nói và những thứ tương tự như vậy. Vì vậy phương tiện dò tìm phải
kết nối các câu hỏi với các mục cơ sở dữ liệu. Các loại truyền thông khác
nhau cần các kỹ nghệ phục hồi và cách biểu thị khác nhau.
Để việc truy tìm có hiệu quả, cần có một cấu trúc các khoản mục hợp
lý. Bởi vì các vector đặc trưng đều đa dạng về kích cỡ và việc truy tìm các
khoản mục trong các MIRS dựa trên sự tương đồng thay cho việc kết nối
chính xác, cấu trúc mục lục được sử dụng trong các DBMS không thích hợp
với các MIRS.
Trong các DBMS, tiến hành chính liên quan đến hiệu quả (thời gian trả

lời câu hỏi) rất quan trọng bởi kích cỡ lớn của multimedia. Ngoài ra, hiệu quả

9


truy tìm cũng rất quan trọng bởi các MIRS truy tìm các mục chọn dựa trên cơ
sở đo sự tương đồng, sử dụng luật tương ứng thay thế cho kết nối chính xác.
1.2. Kiến trúc tổ chức nội dung của một hệ thống cơ sở dữ liệu Multimedia

1.2.1. Kiến trúc hệ thống quản trị cơ sở dữ liệu đa phương tiện
Phát triển một MMDBMS bao gồm các bước sau:
 Bước 1. Thu thập media: Các dữ liệu media được thu thập từ các
nguồn khác nhau như Camera, CD, DVD, Internet...
 Bước 2. Xử lý media: Mô tả các đoạn trích media và các đặc trưng
của chúng, bao gồm cả lọc nhiễu và tách thô...
 Bước 3. Lưu trữ media: Dựa vào yêu cầu cụ thể của ứng dụng để lưu
dữ liệu và các đặc trưng của chúng vào hệ thống.
 Bước 4. Tổ chức media: Tổ chức các đặc trưng để phục vụ việc truy
tìm. Ví dụ: chỉ mục các đặc trưng với các cấu trúc giúp khai thác hiệu quả.
 Bước 5. Xử lý truy vấn media: Là quá trình làm cho thích nghi với
cấu trúc chỉ mục. Thiết kế các giải thuật tìm kiếm hiệu quả.
Kiến trúc chung cho một MMDBMS được minh họa như sau:

10


Trích
chọn đặc
trưng


Xây dựng
truy vấn đặc
trưng

truy vấn

Chỉ
mục

Các đối tượng media

MM

Search
engine

kết

Người
dùng

DB
MS

Hìnhnén1.1: Kiến trúc chung của
một

phản hồi
Xây dựng
truy vấn

MMDBM

chức năng khác
S phản hồi
Hệ thống cơ sở dữ liệu đa phương tiện có nhi
ều môđun
nhau nhằm hỗ trợ các thao tác trên dữ liệu đa phương tiện. Hệ thống bao gồm
các môđun chính sau đây:

11


- Giao diện người dùng
- Bộ trích chọn đặc trưng
- Chỉ số hóa và tìm kiếm
- Quản lý truyền thông
Trong đó, có hai thao tác cơ bản là:
 Bổ sung dữ liệu đa phương tiện mới
Thao tác bổ sung được thực hiện theo trình tự các bước như sau:
- Bước 1: Dữ liệu đa phương tiện mới được bổ sung thông qua nhiều
cách khác nhau như nhập trực tiếp từ bàn phím, từ microphone, camera hay từ
bất kỳ thiết bị nhập kỹ thuật số khác. Dữ liệu đa phương tiện cũng có thể
được lấy từ các tệp đã lưu sẵn.
- Bước 2: Sau khi dữ liệu đa phương tiện được bổ sung, nội dung của
chúng được trích chọn bằng công cụ trích chọn đặc trưng.
- Bước 3: Các dữ liệu đa phương tiện được bổ sung cùng với các đặc
trưng của nó, thông qua bộ quản lý truyền tin sẽ được gửi về máy chủ.
- Bước 4: Tại máy chủ, các đặc trưng sẽ được bố trí về các vị trí phù
hợp dựa vào lược đồ chỉ số hóa.
- Bước 5: Các dữ liệu đa phương tiện bổ sung cùng với các đặc trưng

và chỉ số hóa phát sinh được lưu vào bộ quản lý lưu trữ.
 Truy vấn
Thao tác truy vấn được thực hiện theo trình tự các bước như sau:
- Bước 1: Tại giao diện người dùng, người sử dụng truy vấn thông tin
thông qua một thiết bị nhập nào đó, thông qua tệp đã được lưu trước đó hoặc
có thể lấy trực tiếp từ cơ sở dữ liệu MMDBMS.
- Bước 2: Nếu truy vấn của người sử dụng không được lấy trực tiếp từ
cơ sở dữ liệu trong MMDBMS thì thực hiện như sau:
+ Thực hiện trích chọn đặc trưng truy vấn
+ Gửi các trích chọn đặc trưng đó đến máy chủ


+ Chỉ số hóa để tìm kiếm các mục dữ liệu phù hợp với truy vấn trong
cơ sở dữ liệu.
+ Hiển thị kết quả đến người sử dụng thông qua giao diện người dùng.

1.2.2. Tổ chức dữ liệu đa phương tiện trên cơ sở nguyên lý thống nhất
Xét ví dụ sau:
Bức ảnh photo1.jpg có sự xuất hiện của đối tượng A, đối tượng B và
một đối tượng chưa được xác định được chụp tại sân bóng đá trường Đại học
CNTT&Truyền thông Thái Nguyên vào ngày 24/10/2017.
Đoạn video video1.mpg có hình ảnh của đối tượng A đưa cho đối tượng
B một chiếc cặp (trong frames 20-50). Đoạn video này thu được từ sự theo
dõi Camera tại quán Cafe Z, thành phố Thái Nguyên, nước Việt Nam vào
tháng 11 năm 2017.
Văn bản B.docx có chứa các thông tin chi tiết về dối tượng B được thu
thập từ dữ liệu của cơ quan an ninh.
Bản thân mỗi đối tượng trên cũng đã nói lên phần nào nội dung của
từng đối tượng cụ thể (hình ảnh, video, văn bản). Tuy nhiên, thông tin đưa ra
ở đây chỉ nói lên nội dung về mặt ngữ nghĩa hơn là đề cập đến các tính chất

cụ thể của mỗi loại đối tượng. Một cách tiếp cận hiệu quả nhất đối với CSDL
multimedia và đã được sử dụng rộng rãi trong thực tế là sử dụng các đối
tượng được phát biểu ở trên như là siêu dữ liệu (metadata).
Giả sử chúng ta có một tập các đối tượng media o1,…..,on chúng ta kết
hợp các đối tượng media 01,….0n tương ứng sẽ là md(o1),……,md(on), ta sẽ
phải tiến hành việc chỉ số hóa các metadata này với một cách thức nhằm cung
cấp các phương thức triển khai hiệu quả đối với các yêu cầu truy cập từ phía
người dùng.
Có thể thấy rằng, sự thành công của phương pháp này phụ thuộc cơ bản
vào việc chúng ta đảm bảo được rằng với mỗi đối tượng media 0 i thì metadata


tương ứng của nó md(oi) là cô đọng và phản ánh đúng chỉ những gì mà người
dùng yêu cầu. Với một số lượng tối thiểu các metadata được dùng chúng ta sẽ
dễ dàng hơn trong việc chỉ số hóa cũng như thực hiện các thao tác khai thác dữ
liệu. Tuy nhiên, nếu số lượng metadata sử dụng ít thì có thể người sử dụng sẽ
phải mất thời gian hơn trong việc thiết lập các câu hỏi của mình. Có thể lấy
trường hợp sau làm ví dụ:
Người dùng: hãy tìm cho tôi tất cả các đoạn video hoặc ảnh chụp mà
đối tượng A và đối tượng B trao đổi với nhau một gói hành lý.
Hệ thống: Không tìm được mặc dù hệ thống đã có đoạn video ghi lại
đối tượng A và đối tượng B trao đổi với nhau một chiếc cặp nhưng hệ thống
vẫn trả lời là không tìm thấy vì nó không hiểu rằng một chiếc cặp cũng có thể
coi là một gói hành lý.
Người dùng: hãy tìm cho tôi tất cả các đoạn video hoặc ảnh chụp mà
đối tượng A và đối tượng B trao đổi với nhau một vật gì đó.
Hệ thống: tìm thấy frames 20-50 của đoạn video video1.mpg thỏa mãn
yêu cầu của bạn.
Mặc dù có một vài nhược điểm như sử dụng metadata không biểu diễn
hết được các khía cạnh của đối tượng media trong CSDL nhưng cách tiếp cận

dựa trên nguyên lý đồng nhất có một số ưu điểm nổi bật sau:
- Metadata thường được lưu trữ dưới dạng các cấu trúc có liên quan
đến tính chất quan hệ hoặc hướng đối tượng và có thể truy vấn một cách dễ
dàng thông qua việc mở rộng các ngôn ngữ (chẳng hạn như SQL).
- Việc viết mã để thao tác với metadata thường dễ dàng.
- Việc viết các chương trình để tạo ra metadata là đơn giản đối với các
lập trình viên có năng lực.
Chúng ta đã xem xét đến nội dung của dữ liệu media dưới các dạng
khác nhau. Một câu hỏi đặt ra ở đây: Đâu là phần chung nhất của các loại dữ


liệu này? Mục đích của chúng ta là tìm kiếm một cấu trúc chung nhất cho tất
cả các loại dữ liệu mà qua đó ta có thể thể hiện được nội dung của các loại dữ
liệu đó. Tóm tắt media là một cấu trúc toán học cho phép diễn đạt nội dung
của các media này, sự tóm tắt media có thể được triển khai thông qua một cấu
trúc dữ liệu duy nhất.

1.2.3. Cấu trúc tóm tắt
media
Một cấu trúc media tóm tắt là một tập gồm 8 tuple (S, f e, ATTR, λ, R,
F, Var1, Var2). Trong đó :
- S là một tập các đối tượng gọi là các trạng thái.
- Fe là một tập các đối tượng gọi là các đặc trưng.
- ATTR là một tập các đối tượng gọi là các giá trị thuộc tính.
- λ: S--> 2fe là một ánh xạ từ các trạng thái sang tập các đặc trưng.
- R là một tập các quan hệ trên fei x ATTRj x S với i,j ≥ 0.
- F là một tập các quan hệ của S.
- Var1 là một tập các đối tượng gọi là các biến, thuộc S.
- Var2 là một tập các biến, thuộc fe.
- Một trạng thái là đoạn (chunk) nhỏ nhất của dữ liệu media mà ta

mong muốn. Ví dụ: trong một CSDL hình ảnh, mỗi ảnh có thể được xem như
là một trạng thái. Nếu quan điểm này được chấp nhận, chúng ta sẽ coi như tất
cả các ảnh như là các đối tượng đơn lẻ cơ bản và tất cả các đặc tính của nó sẽ
được quan tâm. Khi đó, chúng ta sẽ không quan tâm đến các đặc tính đơn lẻ
như là các đặc tính của từng điểm ảnh. Trong trường hợp dữ liệu video, một
trạng thái có thể được xem là một chuỗi liên tiếp các frame có dạng (10 x i, 10
x (i+1)) thể hiện một đoạn gồm 10 frame bắt đầu từ frame có số thứ tự chia
hết cho 10.
- Một đặc trưng là bất kỳ đối tượng nào trong một trạng thái mà nó sẽ
được quan tâm. Một đặc trưng có thể gao gồm cả các đối tượng và các phạm