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

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
 


Chương 4. Thử nghiệm 46
 
4.1.
 
Mô hình thử nghiệm 46
 
4.1.1.
 
Cách tiếp cận 46
 
4.1.2.
 
Mô hình đề xuất và các thành phần trong mô hình 47
 
4.2.
 
Môi trường và các thành phần trong hệ thống phần mềm 50
 
4.2.1.
 
Cấu hình phần cứng 50
 
4.2.2.
 
Các thành phần trong hệ thống phần mềm 50
 
4.3.
 
Xây dựng tập dữ liệu 52
 
4.3.1.
 
Tập truy vấn 52
 
4.3.2.
 
Tập máy tìm kiếm nguồn 53
 
4.3.3.
 
Từ điển 53
 
4.4.
 
Quy trình, các phương án thử nghiệm 53
 
4.5.
 
Kết quả thử nghiệm và đánh giá 54
 
Kết luận 60
 
Tài liệu tham khảo 62
 







Danh sách các bảng

Bảng 1. Ví dụ về bản ghi của một ảnh trong cơ sở dữ liệu 42
 
Bảng 2. Cấu hình phần cứng sử dụng trong thực nghiệm 50
 
Bảng 3. Một số phần mềm sử dụng 50
 
Bảng 4. Một số thư viện sử dụng 50
 
Bảng 5. Độ chính xác trung bình trên 35 truy vấn 56
 





Danh sách hình vẽ

Hình 1. Mô tả tính chất authority và hub 13
 
Hình 2. Mở rộng tập cơ sở T từ tập nhân S 14
 
Hình 3. Một mô hình học xếp hạng trong máy tìm kiếm thực thể 18
 
Hình 4. Một minh họa về đồ thị độ tương đồng của ảnh 24
 
Hình 5. Biến đổi ma trận kề 27
 
Hình 6. Kết quả xếp hạng của 3 phương pháp với truy vấn “Notre Dame” 28
 
Hình 7. Mô hình xếp hạng ảnh sử dụng thuật toán ContextRank 29
 
Hình 8. Một ví dụ về biểu diễn visual words 32
 
Hình 9. Kiến trúc của một máy tìm kiếm lớp trên điển hình 34
 
Hình 10. Một thiết kế của bộ điều vận 35
 
Hình 11. Kiến trúc tổng thể của MetaSEEk 37
 
Hình 12. Giao diện hiển thị của MetaSEEk 39
 
Hình 13. Cấu trúc phân cấp của cơ sở dữ liệu 42
 
Hình 14. Mô hình đề xuất 48
 
Hình 15. Giao diện của chương trình 52
 
Hình 16. Biểu đồ so sánh độ chính xác trung bình giữa các hệ thống 57
 
Hình 17. Biểu đồ độ chính xác mức K của một số truy vấn tiếng Việt 58
 
Hình 18. 10 kết quả đầu tiên của truy vấn “sun” trong các máy tìm kiếm 59
 



Danh sách các từ viết tắt

CSDL Cơ sở dữ liệu
AP Average Precision
Google CSE Google Custom Search Engine
HIST Hypertext Induced Topic Search
MAP Mean Average Precision
SIFT Scale Invariant Feature Transform






Danh sách các thuật ngữ

STT Thuật ngữ tiếng Anh Nghĩa tiếng Việt
1 Content-based Image Ranking Xếp hạng ảnh dựa trên nội dung hiển thị
2 Content-based visual query
Truy vấn trực quan dựa trên nội dung
hiển thị
3 Display interface Thành phần hiển thị
4 Edge Cạnh
5 Image tag Thẻ ảnh
6 Inter-image Context Modeling Mô hình ngữ cảnh ngoại ảnh
7 Intra-mage Context Modeling Mô hình ngữ cảnh nội ảnh
8 Local features Các thuộc tính cục bộ
9 Offline Ngoại tuyến
10 Online Trực tuyến
11 Performance database Cơ sở dữ liệu hiệu suất
12 Performance score Điểm số hiệu suất
13 Query dispatcher Bộ điều vận truy vấn
14 Query translator Bộ dịch truy vấn
15 Random surfer model Mô hình duyệt ngẫu nhiên
16 Re-rank Xếp hạng lại
17 Scoring module Mô đun tính hạng
18 Text-based Image Ranking Xếp hạng ảnh dựa trên văn bản
19 Texture Kết cấu
20 Title Tiêu đề
21 Topic Sensitive PageRank PageRank theo chủ đề
22 Visual hyperlink Siêu liên kết trực quan
23 Visual vocabulary Tập từ vựng trực quan
1

Mở đầu
Tính hạng các đối tượng trên Web (trang Web, thực thể nói chung và tính hạng
ảnh nói riêng) là bài toán có ý nghĩa quan trọng trong lĩnh vực tìm kiếm. Sự hình thành và
phát triển không ngừng của máy tìm kiếm gần hai thập kỷ qua đã kéo theo một số lượng
không nhỏ các công trình nghiên cứu về tính hạng trang Web được công bố, trong đó
thuật toán PageRank đã trở thành một trong mười thuật toán khai phá dữ liệu điển hình
nhất. Thời gian gần đây, các công bố công trình nghiên cứu về tính hạng thực thể cũng
như tính hạng ảnh có xu thế tăng nhanh.
Thuật toán tính hạng ảnh thường được phát triển trên cơ sở các thuật toán tính hạng
trang Web, bao gồm cả các giải pháp hướng ngữ cảnh, hướng người dùng hoặc chỉ dựa
trên đồ thị liên kết. Chúng tôi cũng đã tiến hành một số nghiên cứu liên quan trong công
trình nghiên cứu khoa học sinh viên.
Khóa luận tốt nghiệp với đề tài 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 nhằm khảo sát, phân tích các giải
pháp phân hạng ảnh, đồng thời trình bày một mô hình máy tìm kiếm ảnh lớp trên và thi
hành giải pháp phân hạng ảnh trong máy tìm kiếm ảnh lớp trên thử nghiệm.
Khóa luận gồm những nội dung chính cơ bản như sau:
Chương 1: Khái quát về các thuật toán tính hạng trình bày một số thuật toán tính
hạng trang điển hình đã và đang được sử dụng rộng rãi trong các máy tìm kiếm. Cùng với
đó, chương này cũng nêu lên một số nét cơ bản về bài toán xếp hạng thực thể và xếp hạng
ảnh. Đồng thời, chương 1 cũng đề cập đến một số công trình nghiên cứu liên quan ở trong
nước và trên thế giới.
Chương 2: Giới thiệu một số thuật toán tính hạng ảnh phổ biến tập trung trình
bày một số thuật toán tính hạng ảnh dựa trên nội dung hiển thị của ảnh. Mỗi thuật toán đều
được phân tích, đánh giá, đưa ra các ưu nhược điểm. Từ đó, khóa luận đề xuất thuật toán
tính hạng ảnh áp dụng VisualRank cho các đặc trưng hiển thị và đặc trưng văn bản của
ảnh.
Chương 3: Mô hình máy tìm kiếm ảnh lớp trên trình bày mô hình tổng quan của
một máy tìm kiếm lớp trên. Đồng thời, chương 3 đi chi tiết vào một mô hình tìm kiếm ảnh
lớp trên MetaSEEk để tìm hiểu các thành phần cần thiết trong hệ thống máy tìm kiếm ảnh
2

lớp trên. Từ đó, định hình ra những thành phần cần phải xây dựng mô hình máy tìm kiếm
ảnh lớp trên định xây dựng.
Chương 4: Thực nghiệm đưa ra mô hình máy tìm kiếm ảnh lớp trên áp dụng thử
nghiệm thuật toán đã được đề xuất ở chương 2. Chương này trình bày các thành phần của
mô hình và các công việc thực nghiệm mà khóa luận đã tiến hành. Từ những kết quả đạt
được, tiến hành đánh giá, so sánh với các hệ thống khác.
Phần kết luận tóm lược các kết quả đã đạt được và nêu rõ đóng góp của khóa luận,
đồng thời định hướng một số hướng nghiên cứu tiếp theo trong thời gian sắp tới.

3

Chương 1. Khái quát về các thuật toán tính hạng
Xếp hạng là một bài toán phổ biến, có ý nghĩa quan trọng và có nhiều ứng dụng
trong thực tế. Chương này tập trung làm rõ khái niệm về bài toán tính hạng tổng quát,
đồng thời trình bày một số thuật toán tính hạng trang điển hình và giới thiệu sơ bộ về bài
toán tính hạng ảnh.
1.1. Giới thiệu về bài toán tính hạng
Xếp hạng các đối tượng theo tiêu chí nào đó (đơn giản như xếp hạng các học sinh
trong một lớp theo điểm trung bình, xếp hạng các trường đại học…) là công việc hết sức
cần thiết trong nhiều ứng dụng, đặc biệt là việc xếp hạng các kết quả trả về của máy tìm
kiếm. Xếp hạng các đối tượng là sắp xếp các đối tượng theo độ phù hợp với tiêu chí tùy
vào từng ứng dụng cụ thể. Do đó cần phải xác định phép đo về độ phù hợp của một đối
tượng tìm được với yêu cầu của người dùng theo các tiêu chí đã đặt ra [1] [2] [3] [4].
Một điển hình của bài toán xếp hạng đối tượng là việc xếp hạng các đối tượng trả về
của máy tìm kiếm. Trong các máy tìm kiếm thông thường (như Google, Yahoo) độ quan
trọng hay còn gọi hạng trang (PageRank) là đại lượng cơ sở để xếp hạng. Giá trị cơ sở của
hạng trang được tính toán dựa trên việc phân tích mối liên kết giữa các trang Web. Xếp
hạng là công việc cuối cùng trong một máy tìm kiếm nhưng cũng không kém phần quan
trọng. Với tập các tài liệu 

,…

và truy vấn  của người dùng, máy tìm kiếm cần
tìm những tài liệu trong  phù hợp với . Quá trình xếp hạng là quá trình sắp xếp các tài
liệu mà máy tìm kiếm đã tìm được theo độ phù hợp với truy vấn và độ quan trọng giảm
dần. Việc xác định hàm tính hạng đóng vai trò quan trọng và quyết định đối với chất
lượng của máy tìm kiếm. Liên quan tới việc xác định hàm tính hạng, người ta quan tâm tới
hai hướng giải quyết:
• Hướng thứ nhất sử dụng hạng trang của trang Web làm độ phù hợp với yêu cầu
người dùng. Hầu hết các nghiên cứu đều thừa nhận một giả thiết là nếu một trang
Web mà có nhiều trang Web khác liên kết tới thì trang Web đó là trang Web quan
trọng. Trong trường hợp này, hạng trang được tính toán chỉ dựa trên mối liên kết
giữa các trang Web với nhau. Một số thuật toán điển hình theo hướng này là
PageRank, Modified Adaptive PageRank.
• Hướng thứ hai coi độ phù hợp của trang Web với câu truy vấn của người dùng
không chỉ dựa trên giá trị hạng trang Web mà còn phải tính đến mối liên quan
4

giữa nội dung trang Web đó với nội dung truy vấn theo yêu cầu của người dùng.
Khi đó, hàm tính hạng là hàm kết hợp của giá trị độ tương tự giữa tài liệu với truy
vấn ,

 và hạng trang. Các thuật toán xếp hạng theo hướng này
được gọi là các thuật toán xếp hạng định hướng ngữ cảnh. Một thuật toán xếp
hạng định hướng ngữ cảnh điển hình là PageRank theo chủ đề (Topic Sensitive
PageRank).
Với các ứng dụng mà kết quả trả về là một danh sách các đối tượng cần được sắp
xếp, xếp hạng giúp người dùng nhanh chóng tiếp cận với kết quả gần với yêu cầu của
mình nhất có thể. Điều đó cho thấy, xếp hạng là một bài toán quan trọng và có ý nghĩa.
Sau đây, chúng ta sẽ nghiên cứu một số phương pháp tính hạng trang Web, các phương
pháp này hoặc là phương pháp cơ bản đầu tiên, hoặc là đang được áp dụng trên một số
máy tìm kiếm điển hình trên Internet như Google, Yahoo!
1.2. Tính hạng trang Web
Như đã nói ở trên, liên quan tới vấn đề xác định độ đo quan trọng của một trang
Web với yêu cầu người dùng người ta quan tâm tới hai hướng giải quyết: hướng giải
quyết thứ nhất không quan tâm tới vai trò của câu hỏi trong xếp hạng, ngược lại hướng
giải quyết thứ hai liên quan trực tiếp với câu hỏi của người dùng. Tương ứng với hai
hướng giải quyết trên là các thuật toán xếp hạng dựa theo liên kết giữa các trang Web và
các thuật toán xếp hạng định hướng ngữ cảnh. Phần này sẽ trình bày một số thuật toán
điển hình của cả hai hướng trên.
1.2.1. Tính hạng theo liên kết
1.2.1.1. PageRank
PageRank [30] là một thuật toán phân tích liên kết (link) được Lary Page và cộng
sự phát triển tại trường đại học Stanford (Mỹ) và được sử dụng cho máy tìm kiếm
Google. Một cách trực giác, chúng ta có thể thấy rằng trang chủ của Yahoo! thì quan
trọng hơn trang chủ của một cá nhân A nào đó. Điều này được phản ánh qua số lượng
các trang có liên kết đến trang chủ của Yahoo! nhiều hơn số trang có liên kết tới trang
chủ của cá nhân A. Do đó, ta có thể dùng số lượng các liên kết đến một trang để tính
độ quan trọng của trang đó. Tuy nhiên, cách này sẽ không hoạt động tốt khi người ta
có thể dễ dàng tạo ra các trang Web có liên kết đến một trang Web nào đó và như vậy
hạng của trang này sẽ trở nên cao hơn.
PageRank phát triển thêm vào ý tưởng cũ bằng cách chú ý đến độ quan trọng của
các trang Web liên kết đến trang Web mà ta đang xét. Phương pháp này thừa nhận nếu

Xem chi tiết: 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