ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Lê Thị Kim Dung
MỘT SỐ THUẬT TOÁN PHÂN HẠNG ẢNH PHỔ
BIẾN VÀ ÁP DỤNG TRONG HỆ THỐNG TÌM KIẾM
ẢNH LỚP TRÊN THỬ NGHIỆM
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Lê Thị Kim Dung
MỘT SỐ THUẬT TOÁN PHÂN HẠNG ẢNH PHỔ
BIẾN VÀ ÁP DỤNG TRONG HỆ THỐNG TÌM KIẾM
ẢNH LỚP TRÊN THỬ NGHIỆM
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: PGS.TS Hà Quang Thụy
Cán bộ đồng hướng dẫn: Th.s Nguyễn Cẩm Tú
HÀ NỘI - 2010
Lời cảm ơn
Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư
Tiến sĩ Hà Quang Thụy và Thạc sĩ Nguyễn Cẩm Tú, người đã tận tình chỉ bảo và
hướng dẫn tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp.
Tôi chân thành cảm ơn các thầy, cô đã tạo những điều kiện thuận lợi cho tôi học
tập và nghiên cứu tại trường Đại học Công nghệ.
Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong nhóm
“Khai phá dữ liệu” đã giúp tôi rất nhiều trong việc hỗ trợ kiến thức chuyên môn để
hoàn thành tốt khoá luận.
Cuối cùng, tôi muốn gửi lời cảm vô hạn tới gia đình và bạn bè, những người thân
yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp.
Tôi xin chân thành cảm ơn!
Sinh viên
Lê Thị Kim Dung
Tóm tắt
Sự tăng không ngừng về lượng ảnh trên Web tạo nguồn ảnh phong phú đáp ứng
được nguồn cung ảnh cho nhu cầu của con người. Mặc dù một số máy tìm kiếm ảnh đã
ra đời đáp ứng phần nào nhu cầu tìm kiếm ảnh, song nâng cao chất lượng tìm kiếm
luôn là vấn đề được đặt ra. Bài toán xếp hạng ảnh là bài toán cốt lõi của các máy tìm
kiếm ảnh và nâng cao chất lượng xếp hạng ảnh đã và đang nhận được sự quan tâm
đặc biệt.
Đầu tiên, khóa luận khảo sát các thuật toán tính hạng ảnh, đặc biệt là VisualRank
[39] theo độ đo tương đồng giữa các ảnh được tính theo các đặc trưng nội dung văn
bản và nội dung hiển thị. Sau đó, khóa luận đề xuất một mô hình hệ thống tìm kiếm
ảnh lớp trên (image meta-search engine [18] [11]), trong đó sử dụng thuật toán nói trên
làm thành phần xếp hạng ảnh. Hệ thống tìm kiếm ảnh này sử dụng một cơ sở dữ liệu
lưu trữ các câu truy vấn và các ảnh tương ứng với chúng như một giải pháp nhằm rút
ngắn thời gian đáp ứng yêu cầu truy vấn. Đồng thời, hệ thống sử dụng một bộ từ điển
dùng trong việc hỗ trợ các truy vấn dạng tiếng Việt.
Thực nghiệm do khóa luận tiến hành bước đầu đã thu được những kết quả tương
đối khả quan, độ chính xác của hệ thống khi áp dụng thuật toán với đặc trưng văn bản
và đặc trưng hiển thị đạt 81.2%. Trong phạm vi các thử nghiệm của khóa luận, kết quả
này là tốt hơn so với hai máy tìm kiếm ảnh lớn là Google và Yahoo và đã khẳng định
được tính khả thi của mô hình.
Mục lục
Mở đầu ....................................................................................................................... 1
Chương 1. Khái quát về các thuật toán tính hạng.................................................... 3
1.1. Giới thiệu về bài toán tính hạng ...................................................................... 3
1.2. Tính hạng trang Web ...................................................................................... 4
1.2.1. Tính hạng theo liên kết ............................................................................. 4
1.2.2. Tính hạng định hướng ngữ cảnh ............................................................. 15
1.3. Tính hạng thực thể ........................................................................................ 17
1.4. Sơ bộ về tính hạng ảnh.................................................................................. 18
1.5. Một số công trình nghiên cứu liên quan ........................................................ 20
Tóm tắt chương một ................................................................................................. 22
Chương 2. Một số thuật toán tính hạng ảnh phổ biến ........................................... 23
2.1. Giới thiệu ..................................................................................................... 23
2.2. VisualRank ................................................................................................... 23
2.3. Multiclass VisualRank .................................................................................. 26
2.4. Visual contextRank....................................................................................... 28
2.5. Nhận xét ....................................................................................................... 32
Tóm tắt chương hai .................................................................................................. 32
Chương 3. Mô hình máy tìm kiếm ảnh lớp trên ..................................................... 34
3.1. Kiến trúc chung của máy tìm kiếm lớp trên .................................................. 34
3.1.1. Giao diện người dùng ............................................................................. 35
3.1.2. Bộ điều vận ............................................................................................ 35
3.1.3. Bộ xử lý kết quả ..................................................................................... 36
3.1.4. Mô đun tính hạng ................................................................................... 36
3.2. Mô hình máy tìm kiếm ảnh lớp trên MetaSEEk ............................................ 37
3.2.1. Truy vấn trực quan dựa trên nội dung ..................................................... 38
3.2.2. Giao diện truy vấn .................................................................................. 38
3.2.3. Bộ điều vận ............................................................................................ 40
3.2.4. Thành phần hiển thị................................................................................ 42
3.2.5. Đánh giá................................................................................................. 43
3.3. Xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên............................................. 43
Tóm tắt chương ba ................................................................................................... 45