ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ DƯƠNG HOÀNG HUYÊN
MỘT SỐ KỸ THUẬT
TÌM KIẾM ẢNH THEO NỘI DUNG
TRONG CƠ SỞ DỮ LIỆU ĐA PHƯƠNG TIỆN LUẬN VĂN THẠC SĨ


Mã số : 1.01.10
LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS ĐẶNG VĂN ĐỨC
Hà Nội - 2005 Mục lục
Mục lục 1
Các thuật ngữ và các từ viết tắt 3
Danh sách các hình trong luậ 4
Mở ầu 5
Chương 1 7
Tổng quan về cơ sở dữ liệương tiện 7
1.1 Các khái niệm cơ bản 7
1.2 Nguyên lý thiết kế ương tiện 8

2.5 Kết luận 56
Chương 3 58
ặt và thử nghiệm 58
3.1 Tìm kiếm ảnh dựặc trưng màu 58
3.1.1 Phương pháp dùng biểồ màu cục bộ 58
3.1.2 Phương pháp dùng biểồ màu toàn cục 62
3.1.3 Phương pháp dùng moment màu 62
3.2 Tìm kiếm dựặc trưng texture sử dụng ma trậồng hiện 66
3.3 Tìm kiếm dựặc trưng hình dạng sử dụng các moment bất biến 69
Kết luận 72
Tài liệu tham khảo 73
Tiếng Việt 73
Tiếng Anh 73
Các thuật ngữ và các từ viết tắt
CBIR Content-Based Image Retrieval

Hình 2.5 Khoảng cách dạng toàn phương 31
Hình 2.6 Biểồ màu của 3 ảnh A, B, C 32
Hình 2.7 Khoảng cách hai ảnh A và B 34
Hình 2.8 Khoảng cách hai ảnh A và C 35
Hình 2.9 Khoảng cách hai ảnh B và C 35
Hình 2.10 ảnh D sau khi xoay 900 36
Hình 2.11 Ví dụ về ồ thị  38
Hình 2.12 Phương pháp xây dựồ thị  39
ồ thị ối có trọng số 39
Hình 2.14 Tậược có giá trị nhỏ nhất củồ thị  40
Hình 2.15 ảnh trước và sau khi chuyển thành ảnh xám 42
Hình 2.16 Một số texture tiêu biểu 43
Hình 2.17 Ví dụ ma trậồng hiện 44
Hình 2.18 Ví dụ phương pháp mẫu nhị phân cục bộ 47
Hình 2.19 Ví dụ hàm tương quan tự ộng 48
Hình 2.20 Ví dụ biểu diễn hình dạng theo vùng 53
Hình 3.1 Kết quả thực nghiệm phương pháp LCH với lưới 16?16 61
Hình 3.2 Kết quả thực nghiệm phương pháp LCH với lưới 8?8 61
Hình 3.3 Kết quả thực nghiệm phương pháp GCH 65
Hình 3.4 Kết quả thực nghiệm phương pháp moment màu 65
Hình 3.5 Kết quả thực nghiệm ma trậồng hiện với d(0,1) 68
Hình 3.6 Kết quả thực nghiệm ma trậồng hiện với d(1,1) 68
Hình 3.7 Kết quả thực nghiệm moment bất biến 71


mảnh giấy nhỏều này thường hay bị mất thông tin, hoặc thông tin dễ bị mờ.
Xu thế gầế giới người ta cho rằện tử ngày càng phát
triển trong tương lai. Người sử dụng sẽ dùng các thiết bị ện tử ể ghi chép và
lưu trữ các ghi chú cá nhân. Mặc dù có nhiều ghi chép có thể chuyể
ASCII bằng kỹ thuật phân tích chữ viết tay, nhưng có rất nhiều ghi chú không thể
thực hiệược bởi vì các ghi chú thường chứa cả các nét loằng ngoằng hay các
biểồ khối.
Các kiểu dữ liệu liệỉ là một phần trong rất nhiều hình thức biểu
hiện của dữ liệu phát sinh tự nhiên trong các ứng dụng khác nhau. Từ những dữ
liệu mới phát sinh trên, ta thấy rằng các CSDL truyền thống không thể quản lý
các kiểu dữ liệượần phải có có một hệ thống quản lý tất cả các
loại dữ liệương tiệược hình thành.
Trong khuôn khổ của luận vột số vấề cơ bản của
một hệ quản trị ương tiện chẳng hạn các khái niệm, kiến trúc hệ
thống và mô hình dữ liệương tiệập trung nghiên cứu và cài
ặt thử nghiệm một số phương pháp tìm kiếm theo nội dung trên dữ liệ
phương tiện, cụ thể là dữ liệu ảnh.

Chương 1
Tổng quan về cơ sở dữ liệương tiện
1.1 Các khái niệm cơ bản
Dữ liệu Media là các kiểu thông tin hoặc biểu diễn của các kiểu thông tin như các
kí tự, ảnh, audio và video. Multimedia là tập hợp các kiểược sử dụng
với nhau. Hệ quản trị cơ sở dữ liệươ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à chèn, cập nhật, xóa và tìm kiếm mộối tượng trong

sơ ồ nguyên lý tổ chức lai.
Cả ều có những ưu và nhượểm riêng. Nguyên lý tự trị 
hỏi phải tạo ra các thuật toán và cấu trúc dữ liệu cho mỗi media riêng và cần
phải có kỹ thuật kết nối giữa các dữ liệu khác nhau. Ngược lại tổ chức dữ liệu
theo nguyên lý tự trị có thể dẫn tới thời gian xử lý nhanh. Hơn nữa, trong nhiều
trường hợp cấu trúc dữ liệu và thuật toán cho kho dữ liệu cụ thể ồn tại,
nguyên lý tự trị là một lựa chọn tốt.
Hình 1.1 Sơ ồ nguyên lý tự trị

Hình 1.2 Sơ ồ nguyên lý thống nhất

Hình 1.3 Sơ ồ nguyên lý tổ chức lai
Ngược lại với nguyên lý tự trị, nguyên lý thống nhấỏi chúng ta tìm ra cấu
trúc dữ liệể có thể lưu trữ thông tin về ảnh, video, audio, tài liệu ,
ềỏi phải khảo sát nội dung mỗi loại thông tin và cố gắưa ra các
phần chung củỉ số hóa trên các phầợi thế của
nguyên lý thống nhất là dễ ặt và thuật toán thường chạy nhanh. Trong công
nghiệp, nguyên lý thống nhấược sử dụng rộết bị chú
giải (metadata). Bất lợi là chú giải thườược tạo một cách thủ công. Tiến
trình tạo ra bằng tay thường mất nhiều thời gian và kinh phí. Hơn nữa một số
thông tin có thể bị mất nếu ngôn ngữ chú giảầủ ể mô tả
mọi khía cạnh của nội dung. Ví dụ, ngôn ngữ chú thích nội dung ảnh có thể làm
mất thông tin của từểm ảnh. Tương tự, ngôn ngữ chú thích âm thanh có
thể làm mất thông tin về ộ và tần số tín hiệu tại một số ểm.
Nguyên lý tổ chức dữ lai tận dụược các lợi thế của hai kiến trúc trướ
hạn chế ược các bất lợi của nó. Giả sử ta muốn tạo ra một MMDBMS có các
kiểu M1, , Mn. Ta sẽ chia các kiểu thành 2 tập hợp: những kiểu media có sẵn và


Hình 1.4 Kiến trúc tổng quát của MMDBMS
Trong thao tác tìm kiếm, ngườưa ra truy vấn thông qua giao diện người
dùng. Truy vấn có thể là mộặc dữ liệược nhập vào thông qua
các thiết bị ngoại vi. Giao diện ngườễối
tượng trong CSDL, người dùng có thể chọn mộối tượể làm truy
vấn. Nếối tượng trong truy vấặc trưng chính của
ối tượược trích chọn và gởến server thông qua khối truyền thông.
Khối chỉ số hóa và tìm kiếối tượng tương tự nhất và gởi
ối tượến giao diện người dùng thông qua khối truyền thông, giao
diện người dùng sẽ trình diễối tượ
1.3.2 Mô hình dữ liệu
Mô hình dữ liệu trong CSDL cung cấp một ngôn ngữ mô tả tính chất của dữ liệu
ể lưu trữ và tìm kiếm. Ngôn ngữ này phải cho ngườị
chèn, xóa, sửổi và tìm kiếối tượng trong CSDL. Mô hình dữ liệ
phương tiện nắm bắt các tính chấộủa dữ liệương tiện và
cung cấp các dạng cơ bảể phát triển các công cụ sử dụng dữ liệương
tiện. Các tính chấể ối tượng tạo ra dữ liệương tiện,
các mối liên hệ giữối tượng và các tính chất củối tượng. Các tính chất
ộng của dữ liệu có thể là sự tương tác giữối tượối
tượng. Các mô hình dữ liệu phương tiện phảứng các yêu cầu cơ bản như
sau:
- Mô hình dữ liệu phải có khả ở rộối tượng mới có thể
ược bổ sung.
- Mô hình dữ liệu phải có khả ểu diễn các kiểu media cơ bản và các mối
quan hệ không gian và thời gian củối tượng.
- Mô hình dữ liệu phải cho phép lưu trữ và tìm kiếm hiệu quả.
Một mô hình dữ liệu tổng quát thể hiện trong hình 1.5. Tầối tượng chỉ rõ các
mối quan hệ về không gian, thời gian và sự tích hợp giữối tượng. Tầng
các kiểu media chứa các kiểu media chung như text, image, audio và video. Tại

ràng. Truy vấn nhiều loại là vì người dùng có thể ặc tả truy vấn trong nhiều
cách khác nhau. Truy vấn là không rõ ràng bởi vì người dùng có thể chỉ biết
những gì mà họ thấy nhưng không mô tả một cách chính xác hoặc các thông tin
cần thiếượị
Tìm kiếm là một thao tác rất quan trọng trong các hệ quản trị CSDL, trong
MMDBMS thông thường có hai dạng tìm kiếm: tìm kiếm bằặc tả và tìm
kiếm theo mẫu. Giao diện người dùng cần phải hỗ trợ hai phương pháp tìm
kiếm này. Tìm kiếm bằặc tả là người dùng chỉ ra các từ khóa và các
tham số mô tả ặc trưng hoặc các thuộc tính chính của thông tin cần thiết.
Có hai loại truy vấn hỗ trợ cho các thao tác tìm kiếm bằặc tả 
- Truy vấn dựa vào metadata: metadata là các dạng thuộc tính của các mục dữ
liệu trong CSDL ví dụ nó có thể là tên tác giả và ngày tạo lập của mộối tượng
tài liệu, hoặc có thể là tên file dữ liệu.
- Truy vấn dựa vào chú thích: chú thích là các chuỗản mô tả nội dung của
một mục dữ liệu. Truy vấn là các từ khóa hoặc là các chuỗản, Việc tìm
kiếm dựa vào tính chính xác giữa nội dung truy vấn và các chú thích.
ối với tìm kiếm bằng mẫu, giao diện ngườặc tả truy vấn với các kiểu
media khác nhau hoặc kết hợp của các kiểu dữ liệu media. Truy vấưa ra một
ối tượng mẫu và hệ thống sẽ ối tượng tương tự vớối
tượng mẫện người dùng phải hỗ trợ các chứập dữ liệu
ể người dùng mô tả các mẫu, chẳng hạn như microphone, camera, scanner.
Tuy nhiên, ngườể sử dụối tượồn tại trong CSDL
ể làm truy vấể ượều này, giao diện phải có chứễn
ối tượười dùng có thể chọn mộối tượ
trình diễể làm truy vấn. Một lý do nữể giao diện phải hỗ trợ chứ
trình diễười dùng nhiều khi không biết chính xác những gì họ
muốn, họ chỉ có thể nhận ra nó khi họ thấứễn sẽ
hiển thị tất cả hoặc là một số ối tượng, ngườẽ chọn ra một
ối tượng thích hợể làm truy vấn.
Một vấề quan trọng trong giao diệấề trình diễn các kết quả truy

thấp bao gồm âm sắc, phân phối tầng sốặc trưng mức thấp
của ảnh bao gồm phân phối màu, kết cấu bề mặt, hình dạối tượng và các
mối quan hệ ặc trưng mức thấp của video bao gồm tham số
thời gian và một số ặc trưng giống như ảiểm thuận lợi củặc trưng
mức thấp là nó có thể ược trích chọn một cách tự ộng.
ặc trưng mức cao cố gắng nhận dạng và hiểối tượng. Ngoại trừ nhận
dạản và tiếng nói, rấể có thể nhận dạược các mẫu audio và
ối tượng trực quan khác.
ọặc trưng, các kỹ thuật chỉ số hóa giúp tổ chứặc
trưể tìm kiếm hiệu quả. Mỗối tượng có thể có nhiềặc trưể biểu
diễn và mỗặc trưng lại có nhiều tham sốần phải có cơ chế chỉ số hóa
tốể tổ chứặc trưng này.
Thao tác tìm kiếm trong dữ liệương tiện thường dựa vào tính tương tự
thay vì tìm kiếm chính xác giữa các mục trong CSDL. Tính tương tự ược tính
toán dựặc trưng và thuộọn. Tuy nhiên, sự thích hợp
của kết quả tìm kiếm là nh giá chủ quan của con ngườầu chính
củộ ương tự là giá trị tương tự ược tính phải phù hợp nhận xét của con
người.
1.4 Cơ sở dữ liệu ảnh
ảnh số có một vị trí vượt trội so với các dữ liệu media khác như video, audio,
ống như dữ liệược sử dụng rộ
trong các ngành công nghiệp giải trí và tin tức), ảnh là một phần quan trọng
trong nhiềực như nghệ thuật, lịch sử, y tếầu khí, dự báo thời
tiết v.ảnh số ất quan trọng các hoạộng của con người
như nông nghiệp, quản lý rừng, khoa họất, quy hoạị, xa hơn nữa
ể thao và giải trí. Trước khi giới thiệu về CSDL ảnh, chúng tôi giới thiệu
khái quát một số CSDL truyền thống.
1.4.1 Các cơ sở dữ liệu truyền thống
ịột cách không hình thức CSDL quan hệ là một bảng gồm các cột và
các dòng, mỗược gọi là một bộ, mỗi cột gọi là một thuộc tính, mỗi thuộc