Thạc Sĩ Nghiên cứu phương pháp tra cứu ảnh sử dụng các cây dấu hiệu

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

iv
LỜI CẢM ƠN

Trong quá trình thực hiện luận văn này, em luôn nhận được sự hướng
dẫn, chỉ bảo tận tình của TS Nguyễn Hữu Quỳnh, Khoa Công nghệ Thông tin
thuộc trường Đại học Điện lực là cán bộ trực tiếp hướng dẫn khoa học cho
em. Thầy đã dành nhiều thời gian trong việc hướng dẫn cách nghiên cứu, đọc
tài liệu, cài đặt các thuật toán và giúp đỡ về xây dựng hệ thống thực nghiệm.
Em xin chân thành cảm ơn các Thầy, Cô giáo trong trường Đại học Công
nghệ Thông tin và Truyền Thông, Đại học Thái Nguyên đã luôn nhiệt tình
giúp đỡ và tạo điều kiện tốt nhất cho em trong suốt quá trình học tập tại
trường.
Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học
- Trường Đại học Công nghệ Thông tin và Truyền Thông thuộc Đại học Thái
Nguyên đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh
nghiệm học tập, công tác trong suốt khoá học.
Tôi cũng xin chân thành cảm ơn các vị lãnh đạo và các bạn đồng nghiệp
tại Trường Dự bị Đại học Dân tộc Sầm Sơn đã luôn tạo mọi điều kiện tốt nhất
để tôi có thể hoàn thành tốt đẹp khoá học Cao học này.
Thái nguyên, ngày tháng năm 2015
Lê Thị Hà
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

v
DANH MỤC CÁC CHỮ VIẾT TẮT

Ký hiệu Diễn giải
QBE Query by Example (Truy vấn bởi ảnh mẫu)
RGB Red Green Blue (Đỏ, Xanh lục, Xanh lơ)
HSV Hue, Saturation, Value (Màu, sắc nét, cường độ)
CCV Color Coherence Vectors (Véc tơ gắn kết màu)
CBIR Content Based Image Retrieval (Tra cứu ảnh dựa vào nội dung)
QBIC Query By Image Content ( virus cổ điển trong tra cứu ảnh)
GCH Global Color Histogram ( lược đồ màu toàn cục)
S-tree signature tree ( Cây dấu hiệu)
JPEG Joint Photographic Experts Group (ảnh nén)
MPEG Moving Picture Experts Group ( các tiêu chuẩn cho việc truyền
tải âm thanh và video.
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

vi
DANH MỤC CÁC BẢNG

Bảng 2. 1: Tín hiệu chi tiết của hình ảnh trong Hình 2.2 22
Bảng 2. 2: Các dấu hiệu minh họa sai số của độ đo tương tự . 26
Bảng 3.1 : Bảng Images 45
Bảng 3.2 : Bảng FeatureColor . 45
Bảng 3.3 : Chủ đề ảnh trong tập ảnh CSDL 48
Bảng 3.4 : Bảng đánh giá độ chính xác của hệ thống . 49
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

vii
DANH MỤC CÁC HÌNH
Hình 1.1. Không gian màu RGB và HSV. . 6
Hình 1.2. Hình dạng và độ đo được sử dụng để tính đặc trưng. 12
Hình 2.1. Lấy truy vấn qua một ảnh mẫu [27]. . 19
Hình 2.2. Tập ảnh mẫu. 21
Hình 2.3. Minh họa một S-tree và tách nút. . 28
Hình 2.4 Các tệp dấu hiệu và một cây nhị phân 29
Hình 2.5 Vết sinh cây dấu hiệu. . 32
Hình 2.6.Chèn một nút v vào cây T. 33
Hình 2.7.Tìm kiếm cây dấu hiệu 33
Hình 2.8. Một cây dấu hiệu bị lệch. 34
Hình 2.9 Một cây dấu hiệu cân bằng. . 35
Hình 2.10. Sinh các cây dấu hiệu cân bằng. . 37
Hình 2.11 Minh họa tìm kiếm cây dấu hiệu. . 38
Hình 3.1. Kiến trúc chung của hệ thống tra cứu ảnh dựa vào nội dung. . 41
Hình 3.2. Biểu đồ Use Case hệ thống 42
Hình 3.3. Biểu đồ trình tự thêm 1 ảnh vào CSDL . 44
Hình 3.4. Biểu đồ trình tự thêm 1 tập ảnh vào CSDL . 44
Hình 3.6. Giao diện tra cứu ảnh. 46
Hình 3.7. Giao diện kết quả sau khi tra cứu ảnh. 47
Hình 3.8. Giao diện quản lý cơ sở dữ liệu. 47



MỤC LỤC
Mở đầu . 2
CHƯƠNG 1 :TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG 4
1.1. Đặc trưng . 4
1.2. Trích rút và biểu diễn đặc trưng 5
1.2.1.Trích rút và biểu diễn đặc trưng màu 6
1.2.2. Trích rút và biểu diễn đặc trưng kết cấu 9
1.2.3. Trích rút và biểu diễn đặc trưng hình dạng 11
1.3. Yêu cầu đối với các hệ thống tra cứu ảnh dựa vào nội dung 13
1.4. Một số nghiên cứu liên quan . 14
1.5. Kết luận chương 1 . 17
CHƯƠNG 2 : SỬ DỤNG CÂY DẤU HIỆU TRONG TRA CỨU ẢNH DỰA
VÀO MÀU . 18
2.1. Các thành phần của mô hình tra cứu 18
2.2.Lược đồ cho các dấu hiệu ảnh 20
2.3. Các cây dấu hiệu S-tree . 27
2.3.1. Định nghĩa về các cây dấu hiệu . 27
2.3.2. Xây dựng các cây dấu hiệu 30
2.3.3. Tìm kiếm trên các cây dấu hiệu . 32
2.3.4. Các cây dấu hiệu cân bằng . 35
2.3.5. Số trung bình các nút được kiểm tra 38
2.4. Kết luận chương 2 . 39
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

1
CHƯƠNG 3 :ỨNG DỤNG 40
3.1. Bài toán tra cứu ảnh 40
3.2. Thiết kế hệ thống . 40
3.2.1. Biểu đồ Use Case của hệ thống 42
3.2.2. Biểu đồ trình tự 43
3.2.3. Thiết kế CSDL . 45
3.3. Mô tả chương trình 46
3.4. Đánh giá 47
3.5. Kết luận chương 3 . 49

















Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

2

Mở đầu

Sự phát triển nhanh chóng các hồ sơ ảnh đã làm tăng đáng kể nhu cầu
cho các cố gắng nhằm mục tiêu tìm các ảnh tương tự hiệu quả trong cơ sở dữ
liệu ảnh lớn. Một chiến lược phổ biến tìm kiếm các ảnh trong một cơ sở dữ
liệu được gọi là truy vấn theo ví dụ (Query by Example - QBE), trong đó truy
vấn được biểu diễn như một mẫu ảnh hoặc một phác thảo của nó và thường
được sử dụng để đưa ra các truy vấn trong hầu hết các hệ thống tra cứu ảnh
dựa vào nội dung (CBIR) như QBIC của IBM, VIR của Virage, và hệ thống
tra cứu ảnh vệ tinh của IBM/NASA.
Một hệ thống CBIR trích rút các đặc trưng trực quan từ một ảnh truy vấn
được cho, sau đó các đặc trưng được sử dụng để so sánh với các đặc trưng của
các ảnh khác được lưu trữ trong cơ sở dữ liệu. Vì thế, hàm tương tự dựa vào
tóm tắt nội dung ảnh hơn là bản thân ảnh. Một điều cần lưu ý rằng một lượng
dữ liệu ảnh tăng nhanh theo thời gian là sẵn có, cách tiếp cận dựa vào chú
thích được hỗ trợ bởi con người như một phương tiện tóm tắt ảnh là không
khả thi. Phân bố màu toàn cục của một ảnh là một đặc trưng được ứng dụng
để tính toán tóm tắt nội dung ảnh. Các đặc trưng mong muốn như độ phức tạp
trích rút thấp, bất biến với quay và dịch chuyển. Thực tế, lược đồ màu toàn
cục (GCH) thường được sử dụng để biểu diễn phân bố màu trong một ảnh.
Khi sử dụng cách tiếp cận GCH, lưu trữ các véc tơ n chiều của một lược
đồ màu cho mỗi ảnh trong cơ sở dữ liệu có thể chiếm không gian lưu trữ đáng
kể. Để cực tiểu các yêu cầu không gian, luận văn sử dụng biểu diễn nén của
các véc tơ này (các dấu hiệu nhị phân).
Song hành với việc sử dụng dấu hiệu nhị phân ở trên, vấn đề hiệu quả
(tìm kiếm các ảnh tương tự nhanh trong cơ sở dữ liệu lớn) là điểm nhấn của
luận văn. Ánh xạ các lược đồ màu lên các điểm trong không gian n chiều là
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

3
một cách để giải quyết vấn đề, nhưng có một hạn chế nghiêm trọng đó là làm
cho vấn đề tìm kiếm các ảnh tương tự sử dụng cấu trúc truy cập dựa vào đĩa
khó hơn nhiều khi giá trị của n lớn lên. Thực tế, không thông thường để sử
dụng các giá trị của n vượt quá 64. Điều này làm cho việc sử dụng các cấu
trúc truy cập không gian truyền thống như R-tree ít được sử dụng. Để giải
quyết vấn đề này, luận văn sử dụng cây dấu hiệu (S-tree) và thuật toán truy
vấn lân cận gần nhất nhanh trên cây S-tree.
Nội dung luận văn gồm 3 chương:
Chương 1: Giới thiệu tổng quan về tra cứu ảnh dựa vào nội dung
Chương 2: Sử dụng cây dấu hiệu trong tra cứu ảnh dựa vào màu
Chương 3: Ứng dụng.