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
75 trang |
Chia sẻ: netpro | Lượt xem: 1660 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Khóa luận 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
đặc trưng của chuỗi truy vấn vào
quá trình tìm kiếm ảnh. Đây là một hướng nghiên cứu mới được sự quan tâm của
nhiều hội nghị quốc tế như: International Journal of Computer Vision, IEEE
conference…
1.5. Một số công trình nghiên cứu liên quan
Các nghiên cứu về tìm kiếm Web đã bắt đầu từ những năm 1990. Cùng với sự cải
tiến không ngừng của các công cụ tìm kiếm Web, các thuật toán tính hạng trang cũng
nhận được sự quan tâm sâu sắc tại các hội nghị quốc tế. Sự ra đời của thuật toán
PageRank [30] đã đánh dấu một bước phát triển nhảy vọt của các máy tìm kiếm Web
mà điển hình của nó là Google, một trong số các máy tìm kiếm hàng đầu hiện nay.
Kéo theo đó là sự ra đời của một loạt các thuật toán tính hạng trang khác [9] [23] [32]
[35] nhằm cải tiến thuật toán PageRank.
Phần lớn các nghiên cứu tìm kiếm Web là tập trung vào tìm kiếm các trang Web
(tài liệu dạng văn bản) và chỉ một số ít trong đó là về tìm kiếm các thông tin đa
phương tiện trên Web (ảnh, video, MP3…). Tuy nhiên, trong những năm gần đây, vấn
đề tìm kiếm và xếp hạng các đối tượng đa phương tiện trên Web (đặc biệt là vấn đề
tìm kiếm và xếp hạng ảnh) đang trở thành một vấn đề thu hút được rất nhiều sự quan
tâm của các nhà khoa học trên thế giới. Bằng chứng là ngày càng có nhiều các công
trình nghiên cứu về các thuật toán tính hạng ảnh được công bố [17] [29] [30] [34] [36]
[38] [39][40]. Bên cạnh đó là sự ra đời của các máy tìm kiếm ảnh và các máy tìm kiếm
thông thường cũng có xu hướng tích hợp thêm dịch vụ tìm kiếm ảnh.
Một hướng phát triển mới cho các máy tìm kiếm Web đang rất được chú ý đó là
các máy tìm kiếm lớp trên (Meta-search engine). Đã có một số công trình nghiên cứu
về máy tìm kiếm lớp trên [11] [14] [18] [28] được công bố cũng như đã có một số máy
tìm kiếm lớp trên (Dogpile, Clussty, KartOO, Google CSE…) được mang vào sử dụng
trong thực tiễn. Tuy nhiên, những công cụ tìm kiếm này vẫn chưa mang lại được thành
tựu nổi bật và chưa cạnh tranh được với Google.
Ở Việt Nam, nghiên cứu và ứng dụng tìm kiếm và xếp hạng Web cũng đang
nhận được nhiều sự quan tâm. Hiện tại, cũng có một số công ty làm về máy tìm kiếm
như Bamboo, Zing, Xalo, Socbay…. Thứ trưởng Bộ TT-TT Nguyễn Minh Hồng1 cho
rằng, các máy tìm kiếm trực tuyến ra đời là sự đóng góp lớn cho nền công nghiệp
1
21
CNTT Việt Nam. Tuy nhiên, những sản phẩm này vẫn chưa thể vượt qua các công cụ
tìm kiếm của các “đại gia” nước ngoài trên thị trường nội địa. Theo ông Lê Ngọc
Quang1, Giám đốc Phát triển Kinh doanh và Công nghệ của IDG Ventures Vietnam,
công cụ tìm kiếm của Việt Nam hiện nay gần như bỏ không, không tạo doanh thu, rất
ít người dùng và như vậy là một sự lãng phí. Ngoài các máy tìm kiếm còn có một số
công trình nghiên cứu về tìm kiếm và xếp hạng đã được công bố. Một số công trình
nghiên cứu bước đầu như cải tiến thuật toán tính hạng trang của Nguyễn Hoài Nam
[2], mô hình học xếp hạng của Nguyễn Thu Trang [4], xây dựng công cụ tìm kiếm
MP3 cho tiếng Việt của Nguyễn Hoàng Trung [5].
Công trình nghiên cứu của Nguyễn Hoài Nam [2] dựa trên cơ sở một số phương
pháp tìm kiếm và xếp hạng trang cơ bản, từ đó đưa ra những đề xuất cải tiến cho thuật
toán PageRank theo chủ đề. Phương pháp mà [2] đưa ra là gán các giá trị quan trọng
khác nhau đối với các liên kết để làm chính xác hơn các kết quả tìm kiếm. Cụ thể như
những liên kết từ các trang trong cùng chủ đề đối với trang được liên kết có thể mang
tới cho trang đó giá trị nhiều hơn những trang không nằm trong cùng chủ đề. Phương
pháp này đã được áp dụng thử nghiệm cho máy tìm kiếm Vietseek và bước đầu đã
mang lại hiệu quả.
Một nghiên cứu khác cũng về vấn đề xếp hạng là nghiên cứu về học xếp hạng
trong tính hạng đối tượng và tạo nhãn cụm tài liệu của Nguyễn Thu Trang [4]. Công
trình của [4] thực hiện khảo sát, phân tích các phương pháp học xếp hạng đang được
quan tâm hiện nay và từ đó đưa ra mô hình xếp hạng thực thể áp dụng vào máy tìm
kiếm thực thể trong tiếng Việt, cụ thể là tìm kiếm thực thể thuốc và học xếp hạng để
tạo nhãn cho cụm tài liệu. Các kết quả thu được đã chứng minh vai trò và hiệu quả của
học xếp hạng áp dụng vào máy tìm kiếm.
Nguyễn Hoàng Trung [5] đã tiến hành xây dựng thử nghiệm một thành phần tìm
kiếm MP3 cho tiếng Việt cho máy tìm kiếm Socbay. Hệ thống này tìm kiếm các file
MP3 dựa vào các trường mô tả file. Phần mềm tìm kiếm này cho kết quả tương đối
chính xác đối với cả những tìm kiếm tiếng Việt không dấu và có dấu trong thời gian
cho phép.
Qua quá trình tìm hiểu về tình hình nghiên cứu trong và ngoài nước, nhận thấy
yêu cầu của thực tế đặt ra là rất cần thiết và cấp bách, trong khóa luận này, tôi tập
trung nghiên cứu về các thuật toán tính hạng ảnh và sau đó áp dụng vào việc xây dựng
1
22
một mô hình máy tìm kiếm lớp trên thử nghiệm cho ảnh. Tôi tin rằng những nghiên
cứu của mình là rất thiết thực và sẽ là nền tảng cho những nghiên cứu tiếp theo của
mình.
Tóm tắt chương một
Trong chương một, khóa luận đã tập trung khảo sát, phân tích một số thuật toán
tính hạng trang điển hình đang được sử dụng rộng rãi hiện nay. Đồng thời khóa luận
cũng đã trình bày sơ bộ về vấn đề xếp hạng đối tượng nói chung và xếp hạng ảnh nói
riêng. Trong chương tiếp theo, khóa luận sẽ giới thiệu chi tiết hơn về các thuật toán
tính hạng ảnh theo nội dung hiển thị.
23
Chương 2. Một số thuật toán tính hạng ảnh phổ biến
2.1. Giới thiệu
Như đã trình bày ở chương trước, xếp hạng ảnh là một bài toán điển hình trong lĩnh
vực xếp hạng thực thể và đang nhận được nhiều sự quan tâm nghiên cứu của các nhà khoa
học. Các nghiên cứu về xếp hạng ảnh hiện nay chủ yếu tập trung vào phân tích các đặc
trưng về nội dung hiển thị của ảnh.
Phương pháp phổ biến là dùng lý thuyết đồ thị để xây dựng mối quan hệ giữa các
bức ảnh. Phương pháp tiếp cận này xây dựng một đồ thị kết nối các ảnh giống nhau, sau
đó sử dụng vector đặc trưng để tìm các ảnh là “trung tâm” của đồ thị. Một hướng tiếp cận
đơn giản và hiệu quả ứng dụng trong việc xử lý các thông tin về nội dung hiển thị của ảnh
đã được đề xuất bởi Yushi Jing và Shumeet Baluja [39][40]. Phương pháp của Jing và
Baluja sử dụng độ đo tương đồng giữa các bức ảnh để xây dựng một đồ thị tương đồng và
dựa trên thuật toán PageRank để tính hạng cho các bức ảnh. Theo hướng tiếp cận này
[34], [29] cũng có một số đề xuất để cải tiến thuật toán mà Jing và Baluja đưa ra.
Một kỹ thuật khác là xây dựng các cụm các bức ảnh và sau đó sử dụng độ tương
đồng trong cùng một cụm hoặc trung tâm cụm để tìm ảnh nổi bật nhất [27] [36]. Nghiên
cứu của T.L.Berg và A.C.Berg mở rộng ý tưởng phân cụm bằng cách tìm các ảnh mà có
một đối tượng nổi bật rõ ràng, và vì thế có nhiều khả năng đại diện nhất. Ngoài ra còn một
số hướng tiếp cận theo hướng người dùng [38] hoặc học bán giám sát [17]. Các phương
pháp này thường kết hợp cả các đặc trưng về văn bản của ảnh.
Chương này sẽ tập trung giới thiệu chi tiết hơn một số thuật toán phổ biến xếp hạng
ảnh dựa trên nội dung hiển thị.
2.2. VisualRank
VisualRank là thuật toán tính hạng ảnh dựa vào việc phân tích độ tương đồng về
nội dung giữa các bức ảnh do Yushi Jing và Shumeet Baluja [39][40] đề xuất. Phương
pháp mà Jing và Baluja đưa ra lấy tư tưởng cơ bản từ thuật toán phân tích liên kết
PageRank. Cũng giống như PageRank, thuật toán VisualRank sử dụng lý thuyết đồ thị
để xây dựng đồ thị ảnh và dùng vector đặc trưng trung tâm để tính hạng cho các ảnh.
Với nhận định trực quan rằng, nếu một người dùng xem một bức ảnh, thì người đó
cũng có thể quan tâm đến các ảnh khác gần giống với ảnh vừa xem. Nghĩa là nếu giữa
các ảnh có các liên kết biểu thị sự giống nhau giữa các ảnh đó thì sẽ có một xác suất
nào đó để người dùng khi xem ảnh này sẽ chuyển sang xem một ảnh gần giống với nó.
24
Xây dựng đồ thị từ tập dữ liệu ảnh với các đỉnh của đồ thị biểu diễn các ảnh
tương ứng trong tập dữ liệu. Các đỉnh được nối với nhau bởi các cạnh có trọng số là độ
tương đồng giữa hai ảnh mà được biểu diễn bởi hai đỉnh của cạnh đó. Các cạnh này
được gọi là các liên kết trực quan (visual hyperlinks) giữa các bức ảnh. VisualRank sử
dụng quá trình duyệt ngẫu nhiên để xếp hạng các ảnh dựa vào các liên kết này. Nếu
một ảnh u có liên kết tới ảnh v, thì sẽ có một xác suất để người dùng chuyển từ u sang
v. Một cách trực quan ta có thể thấy các ảnh phù hợp với truy vấn sẽ có nhiều ảnh khác
trỏ tới, và do đó chúng sẽ được thăm thường xuyên. Các ảnh được thăm thường xuyên
thường được cho là quan trọng. Hơn nữa, nếu một ảnh v là quan trọng và nó có liên kết
tới ảnh w, thì nó sẽ gộp độ quan trọng của nó cho độ quan trọng của w vì bản thân v là
quan trọng. VisualRank được định nghĩa như sau:
ܸܴ ൌ ܵכ ൈ ܸܴ ሺ2.1ሻ
Trong đó, ܵכ là ma trận cắt giảm theo cột của ma trận ܵ, với ܵ௨,௩ là độ tương
đồng giữa hai ảnh u và v. Việc lặp đi lặp lại phép nhân VR với ܵכ sẽ thu được vector
đặc trưng của ma trận ܵכ. Mặc dù VR có kết quả cố định, nhưng theo thực nghiệm, nó
có thể được ước lượng một cách hiệu quả hơn qua phương pháp tiếp cận lặp.
Hình 4. Một minh họa về đồ thị độ tương đồng của ảnh
25
VisualRank hội tụ chỉ khi ma trận ܵכ là không tuần hoàn và tối giản. Cũng giống
như PageRank, Jing đưa vào VisualRank một thừa số hãm d để đảm bảo đồ thị ảnh là
đồ thị liên kết mạnh. Jing cũng chỉ ra rằng, ma trận tương đồng S cũng có thể là ma
trận đối xứng. Trong trường hợp đó, sự xuất hiện của thừa số hãm có thể làm mất tính
đối xứng của ma trận này.
Với tập n ảnh, VisualRank được định nghĩa lại theo công thức sau:
ܸܴ ൌ ݀ܵכ ൈ ܸܴ ሺ1 െ ݀ሻ ݒớ݅ ൌ
1
݊൨ൈଵ
ሺ2.2ሻ
Trong thực nghiệm, d thường được chọn giá trị d > 0.8.
Một độ đo tin cậy của độ tương đồng là yếu tố quyết định tới tính hiệu quả của
VisualRank bởi vì nó ảnh hưởng rất lớn tới cấu trúc của đồ thị. Qua phân tích các đặc
tính của ảnh, Jing và Baluja cho rằng các đặc tính cục bộ của ảnh giàu thông tin hơn và
vẫn giữ được tính ổn định khi qua các phép biến đổi khác nhau. Vì thế, trong nghiên
cứu của mình, Jing và Baluja [40] chọn đặc trưng SIFT [24] [25] và biểu đồ hướng
làm đặc trưng cho các đặc tính của ảnh. Ma trận tương đồng được xây dựng từ độ
tương đồng của các cặp ảnh trong toàn bộ dữ liệu ảnh. Độ tương đồng của mỗi cặp ảnh
có thể là số các thuộc tính cục bộ phù hợp của cặp ảnh đó.
Với khối lượng ảnh khổng lồ trên Web hiện nay, lượng kết quả trả về của máy
tìm kiếm ảnh đối với một truy vấn là rất lớn. Nhận thấy rằng việc tính toán để tạo ra đồ
thị tương đồng S cho hàng tỉ bức ảnh là không thể, trong thực tế thi hành VisualRank,
Jing và Baluja đề xuất phương pháp tiền phân cụm các ảnh Web dựa trên việc sử dụng
các thuộc tính văn bản của ảnh để giảm bớt tập ảnh đầu vào. Việc này có thể thực hiện
thông qua các máy tìm kiếm thương mại bằng cách trích rút tập N ảnh trả về đầu tiên
khi truy vấn vào các máy tìm kiếm thương mại thông thường, sau đó tiến hành xây
dựng đồ thị tương đồng và tính VisualRank chỉ trên tập con N ảnh này.
Thuật toán VisualRank trình bày một kỹ thuật đơn giản để kết hợp các lợi điểm
trong việc sử dụng liên kết và phân tích mạng cho tìm kiếm trang Web vào tìm kiếm
ảnh. Thuật toán đã được các tác giả thử nghiệm và cho kết quả tốt hơn kết quả xếp
hạng của máy tìm kiếm ảnh Google trong phần lớn các truy vấn trong khi vẫn duy trì
được hiệu quả tính toán hợp lý cho việc triển khai quy mô lớn.
26
2.3. Multiclass VisualRank
Multiclass VisualRank là thuật toán xếp hạng ảnh mở rộng ý tưởng từ phương
pháp VisualRank của Jing và Baluja [39] [40] để xếp hạng ảnh cho nhiều phân loại
ảnh, do Misur Ambai và Yuichi Yoshida [29] đề xuất. Multiclass VisualRank chia các
ảnh được trả về từ máy tìm kiếm thành những phân loại khác nhau dựa vào các đặc
trưng nội dung của ảnh và tiến hành xếp hạng trong từng phân loại đó. Multiclass
VisualRank gồm ba bước sau:
o Tính độ tương đồng về nội dung ảnh: Cũng giống như phương pháp VisualRank,
Ambai sử dụng giải thuật SIFT để tính độ tương đồng ݓ, giữa hai ảnh ܫ, ܫ. Thuật
toán VisualRank nguyên thủy sử dụng tỉ số ܥ là số các key points chung giữa hai ảnh
ܫ và ܫ chia cho số key points trung bình lấy được từ ܫ, ܫ làm độ đo tương đồng giữa
hai ảnh đó. Tuy nhiên, các máy tìm kiếm ảnh thường trả về cùng một tập ảnh đối với
cùng một truy vấn. Trong trường hợp này, giá trị ܥ trở nên quá lớn so với các độ đo
tương đồng khác, và có thể làm cho kết quả phân cụm không còn chính xác. Do đó,
phương pháp Multiclass VisualRank áp dụng một hàm xích ma vào ܥ để làm giảm
các giá trị lớn.
o Phân cụm: Bước này tiến hành phân tập các ảnh thành các phân loại khác nhau
dựa vào việc phân cụm các độ đo tương đồng.
Nhận thấy rằng, các ảnh càng gần giống nhau thì độ đo tương đồng càng lớn và
đồ thị tương đồng chứa một số cụm ứng với các phân loại ảnh khác nhau. Do đó, [29]
sử dụng kỹ thuật Nomarlized cut để phân cụm các bức ảnh trong tập dữ liệu bằng cách
phân cụm các độ đo tương đồng trong ma trận tương đồng. Công thức phân cụm được
tính như sau:
ሺܦ െܹሻݒ ൌ λܦݒ ሺ2.3ሻ
Với W là một ma trận kề có các phần tử là các độ đo tương đồng ݓ, D là một
ma trận chéo, λ là giá trị riêng và ݒ là vector riêng.
27
Hình 5. Biến đổi ma trận kề
o Tính hạng: Tương tự như phương pháp của Jing, Wang cũng sử dụng PageRank
để tính hạng cho các ảnh:
ݎ ՚ ሺ1 െ ߙሻܹݎ ߙ ሺ2.4ሻ
Với ݎ ൌ ሺݎଵ, … , ݎேሻ் là vector tính hạng của các ảnh, ߙ là thừa số hãm.
Bởi vì các ảnh được chia thành các phân loại, điểm số tính hạng của một ảnh
thuộc phân loại này không bị ảnh hưởng bởi điểm số tính hạng của các ảnh trong phân
loại khác. Do đó, ta có thể bỏ đi độ đo tương đồng giữa các phân loại khác nhau, tức là
bỏ đi liên kết giữa các ảnh thuộc về các phân loại khác nhau. Khi đó, ma trận kề W
được sửa đổi như sau:
ݓᇱ ൌ ቊ
ݓ ݊ếݑ ܫ ݒà ܫ ݐ݄ݑộܿ ݒề ܿù݊݃ ݉ộݐ ݄â݊ ݈ạ݅
0 ݊݃ượܿ ݈ạ݅
ሺ2.5ሻ
Bằng cách biến đổi ma trận kề W thành ma trận ܹᇱ, công việc tính toán đã được
giảm đi đáng kể. Việc loại bỏ độ đo tương đồng giữa các ảnh thuộc về các phân loại
khác nhau làm cho mỗi ảnh trong một phân loại càng giống với đại diện của phân loại
đó thì có thứ hạng càng cao.
Trong thực nghiệm, Multiclass VisualRank cho kết quả xếp hạng tốt với độ chính
xác xấp xỉ bằng độ chính xác của VisualRank. Độ chính xác của 10 ảnh được xếp hạng
đầu tiên bằng thuật toán Multiclass VisualRank là 0.949 trong khi đó độ chính xác của
VisualRank là 0.953 [29].
Bỏ đi trọng số giữa
các phân loại ảnh
khác nhau
28
Hình 6. Kết quả xếp hạng của 3 phương pháp với truy vấn “Notre Dame”
2.4. Visual contextRank
Phần trên đã trình bày một phương pháp xếp hạng ảnh khá hiệu quả được đề xuất
bởi Jing và các đồng nghiệp, phương pháp này tiến hành xây dựng ma trận tương đồng
của 1000 ảnh và sử dụng VisualRank để tính hạng cho mỗi bức ảnh. Tuy nhiên,
phương pháp của Jing và cộng sự coi các đặc tính cục bộ có độ quan trọng là như nhau
và không quan tâm đến các thông tin về ngữ cảnh. Do đó có thể sẽ gây ra nhiều sai sót
trong việc tính độ tương đồng giữa các bức ảnh. Một phương pháp xếp hạng ảnh được
trình bày dưới đây sử dụng thông tin ngữ cảnh để khắc phục các vấn đề trên.
ContextRank là phương pháp do Shuhui Wang và cộng sự [34] đề xuất, sử dụng
quá trình duyệt ngẫu nhiên Markov giữa các visual words1 trong cùng một ảnh và giữa
các ảnh với nhau nhằm xếp hạng lại (re-ranking) các ảnh là kết quả trả về từ một máy
tìm kiếm ảnh thương mại. Wang và cộng sự đưa ra hai giả định:
i. Có thể di chuyển giữa các visual word lân cận nhau trong cùng một ảnh.
ii. Có thể di chuyển từ một visual word A trong ảnh i tới visual word B trong ảnh
j nếu tồn tại một liên kết giữa hai visual word này.
1 visual word: là một chỉ mục mô tả mẫu của một phân cụm các mô tả thuộc tính cục bộ của ảnh [33]
29
Phương pháp ContextRank coi mỗi visual word là một trạng thái trong không
gian trạng thái Markov. Quá trình duyệt qua các visual word là sự chuyển trạng thái từ
trạng thái hiện tại r đến trạng thái kết thúc s.
Hình 7. Mô hình xếp hạng ảnh sử dụng thuật toán ContextRank
Mô hình xếp hạng ContextRank mà Wang và cộng sự đề xuất gồm các thành phần
như sau:
o Chuẩn bị dữ liệu: Với đầu vào là một chuỗi truy vấn dạng từ khóa, ContextRank
đưa chuỗi truy vấn này vào các máy tìm kiếm ảnh theo các thuộc tính văn bản của
ảnh. Sau đó tiến hành trích rút N kết quả trả về đầu tiên từ máy tìm kiếm để thực
hiện xếp hạng lại cho N ảnh này.
o Mô hình ngữ cảnh nội ảnh (Intra-image Context Modeling): Thành phần này thực
hiện việc xây dựng liên kết giữa các visual word trong cùng một ảnh với tập N
ảnh lấy được từ dữ liệu.
o Mô hình ngữ cảnh ngoại ảnh (Inter-image Context Modeling): Thành phần này
thực hiện việc xây dựng liên kết giữa các visual word trong các ảnh khác nhau
trong tập N ảnh.
o Kết hợp ngữ cảnh nội ảnh (intra-image context) với ngữ cảnh ngoại ảnh (inter-
image context) và dùng lý thuyết đồ thị duyệt ngẫu nhiên để mô hình hóa mối
30
quan hệ nội ảnh (intra-image) và ngoại ảnh (inter-image) của các visual word. Từ
đó tiến hành tính hạng lại cho ảnh dựa vào điểm số (score) của các visual word
trong một ảnh.
Hạng của ảnh được tính theo phương pháp ContextRank như sau:
Cho trước một tập từ vựng trực quan (visual vocabulary) với K visual keywords.
Mỗi thuộc tính cục bộ của ảnh được gán một chỉ mục visual word. Với một tập chứa N
ảnh kết quả trả về đầu tiên thu được từ các máy tìm kiếm ảnh dựa trên văn bản, biểu
diễn các visual word trong tập N ảnh như một đồ thị, mỗi visual word xuất hiện trong
mỗi ảnh được xem như là một đỉnh của đồ thị. Gọi ܸ, với ݅ ൌ 1,…ܰ; ݉ ൌ 1,…ܭ là
biểu diễn của một đỉnh. Vậy ta có tất cả ܭ ൈ ܰ đỉnh. Mục đích của thuật toán là tìm
điểm số ߨሺ ܸ,ሻ của visual word thứ m trong ảnh i.
Biểu diễn đồ thị các visual word bởi ma trận chuyển P,
ߨ ൌ ሼߨሺ ܸ,ሻሽ, ∑ ߨሺ ܸ,ሻ, , ݅ ൌ 1,…ܰ; ݉ ൌ 1,…ܭ, ߨ là vector riêng của ma trận P
với giá trị riêng bằng 1, mỗi phần tử của ߨ là điểm số của một visual word. ߨ được tính
theo công thức:
ߨ ൌ ܲߨ ሺ2.6ሻ
Do tính chất của chuỗi Markov, để tính vector riêng của P, đồ thị visual word
phải là liên thông, tức là với cặp hai visual word i, j bất kì luôn có đường đi từ i tới j và
ngược lại. Tuy nhiên, vẫn tồn tại không ít các visual word không có liên kết đến các
visual word khác. Vì vậy cần phải biến đổi ma trận P để tránh việc khi duyệt các đỉnh
không có liên kết sẽ không duyệt được tiếp. Hơn nữa, để đảm bảo tính phân phối dừng
ổn định (duy nhất) của ߨ, tức là từ một đỉnh trong quá trình duyệt có thể chuyển tới
một đỉnh bất kỳ khác, thì cần phải thêm một nhân tố hãm. Công thức (2.6) được viết
lại như sau:
ߨ ൌ ߙܲߨ ሺ1 െ ߙሻܦ ሺ2.7ሻ
Trong đó:
ߙ là hệ số hãm. Trong thực tế ߙ thường được chọn giá trị 0.8.
D là vector ܭܰ ൈ 1 với tổng các phần tử bằng 1. D có thể được tính theo
công thức:
31
ܦሾሺ݅ െ 1ሻ ൈ ܭ ݉ሿ ൌ ቐ
ܫܵሺ݅ሻ
݊ݑ݉௭ሺሻ
݊ếݑ ݒݓሺ݉ሻ ؿ ݅݉݃ሺ݅ሻ
0 ݊݃ượܿ ݈ạ݅
ሺ2.8ሻ
IS(i) là điểm số khởi tạo của ảnh i, num_nz(m) là số visual word với
tần số không bằng 0.
Nhận thấy rằng P là ma trận rất thưa, phép nhân với các phần tử bằng 0 trong P là
rất đơn giản. Vì thế ta có thể chia P thành các ma trận con. Mỗi ma trận con là một ma
trận dịch chuyển của các visual words trong ảnh i và các visual words trong ảnh j. Gọi
ܤ, là biểu diễn của ma trận con nói trên. P được tổ chức lại thành hai ma trận con:
ܲ ൌ ܾܩ ሺ1 െ ܾሻܥ ሺ2.9ሻ
G là một ma trận bao gồm các ma trận con ܤ,, ݅ ൌ 1,…ܰ và tất cả các ma trận
con khác bằng 0.
C là một ma trận bao gồm các ma trận con ܤ,, ݅ ൌ 1,…ܰ bằng 0 và tất cả các ma
trận con khác khác 0.
G đánh giá xác suất dịch chuyển của các visual word trong cùng một ảnh còn C
đánh giá cho các visual word trong các ảnh khác nhau. Tham số b là nhân tố trọng số.
Sau khi đã tính được vector riêng ߨ của các visual words trong mỗi ảnh, hạng của
ảnh i được tính theo công thức:
ܴሺ݅ሻ ൌ ߨ
ୀଵ
൫ ܸ,൯, ݅ ൌ 1,…ܰ ሺ2.10ሻ
Với ߨሺ ܸ,ሻ là điểm số của visual word thứ m trong ảnh i. Đối với các visual
keyword mà không tồn tại trong ảnh i thì ߨ൫ ܸ,൯ ൌ 0.
32
Hình 8. Một ví dụ về biểu diễn visual words
Trong thực nghiệm, Wang trích xuất khoảng 200 đặc trưng SIFT cho mỗi bức
ảnh và sử dụng một tập khoảng 400 từ vựng để tính toán. Thuật toán được áp dụng thử
nghiệm cho hai tập dữ liệu khác nhau và đã cho kết quả tốt hơn đáng kể đối với
phương pháp VisualRank trong việc xếp hạng lại ảnh.
2.5. Nhận xét
Qua tìm hiểu các phương pháp xếp hạng ảnh ở trên, tôi nhận thấy các phương pháp
này đều áp dụng kỹ thuật phân tích liên kết để phân tích mối quan hệ giữa các ảnh dựa
vào đặc trưng hiển thị. Các phương pháp này là khá đơn giản và cho kết quả xếp hạng
khả quan. Tuy nhiên, các phương pháp nói trên đều chỉ dựa vào nội dụng hiển thị của
ảnh mà không quan tâm đến các dữ liệu dạng văn bản đi kèm với ảnh. Vì các dữ liệu
văn bản này là do người dùng tạo ra nên chúng đều có một ý nghĩa nhất định đối với
nội dung hiển thị của ảnh. Sự thành công của các máy tìm kiếm ảnh dựa trên văn bản
đã khẳng định điều đó. Hơn nữa, những thành tựu trong lĩnh vực phân tích và xử lý
văn bản đã mang lại nhiều thuận lợi trong việc tính độ tương đồng giữa các văn bản.
Dựa vào những ưu điểm, nhược điểm trên, đối với khóa luận này, tôi quyết định
sử dụng phương pháp xếp hạng ảnh áp dụng thuật toán VisualRank cho cả đặc trưng
hiển thị và đặc trưng văn bản của ảnh mà đã được đề xuất trong báo cáo công trình
nghiên cứu khoa học sinh viên của chúng tôi.
Tóm tắt chương hai
Trong chương hai, khóa luận đã giới thiệu chi tiết một số phương pháp xếp hạng
ảnh điển hình dựa trên nội dung hiển thị. Đồng thời, chương này cũng đã đưa ra được
một số nhận xét về ưu điểm, nhược điểm của các phương pháp này và đưa ra phương
pháp xếp hạng ảnh kết hợp giữa nội dung hiển thị và dữ liệu văn bản đi kèm với ảnh sẽ
33
được sử dụng trong phần thực nghiệm của khóa luận. Trong chương tiếp theo, khóa
luận sẽ giới thiệu mô hình chung của máy tìm kiếm lớp trên và một mô hình máy tìm
kiếm ảnh lớp trên, đồng thời trình bày một số vấn đề trong việc xếp hạng ảnh trong
máy tìm kiếm ảnh lớp trên.
34
Chương 3. Mô hình máy tìm kiếm ảnh lớp trên
Meta-search engine (tạm dịch là máy tìm kiếm lớp trên) [18] [28] là một máy tìm
kiếm mà tìm kiếm thông tin dựa trên các máy tìm kiếm khác. Với mỗi truy vấn của
người dùng, máy tìm kiếm lớp trên sẽ chuyển nó đến các máy tìm kiếm khác (gọi là
các máy tìm kiếm nguồn) và sau đó xử lý kết quả trả về từ các máy tìm kiếm này trước
khi đưa ra kết quả cho người dùng trên một giao diện duy nhất. Máy tìm kiếm lớp trên
chủ yếu được sử dụng để mở rộng vùng tìm kiếm nhờ việc sử dụng kết quả tìm kiếm
từ nhiều nguồn dữ liệu của các máy tìm kiếm khác nhau, giúp tăng cơ hội cho người
dùng tìm được thông tin mong muốn.
Chương này sẽ trình bày về kiến trúc chung của máy tìm kiếm lớp trên, đồng thời
giới thiệu một mô hình máy tìm kiếm ảnh lớp trên và sau đó sẽ giới thiệu sơ bộ về vấn
đề xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên.
3.1. Kiến trúc chung của máy tìm kiếm lớp trên
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 [18]
Kiến trúc của một máy tìm kiếm Web lớp trên cũng gần giống với kiến trúc của
một máy tìm kiếm Web thông thường [18]. Sự khác biệt cơ bản đó là máy tìm kiếm
lớp trên không có thành phần cơ sở dữ liệu để lưu trữ các trang Web như máy tìm
kiếm Web thông thường. Thay vào đó là một cơ sở dữ liệu ảo bao gồm: bộ điều vận
(dispatcher), các máy tìm kiếm thông thường khác, và một bộ xử lý kết quả (result
processor). Một máy tìm kiếm lớp trên bao gồm bốn thành phần chính: giao diện
người dùng (user interface), bộ điều vận (dispatcher), bộ xử lý kết quả (result
processor), và mô đun tính hạng (scoring module).
35
3.1.1. Giao diện người dùng
Giao diện người dùng là bộ phận nhận truy vấn đầu vào của người dùng và hiển
thị kết quả đầu ra. Giao diện thường là một trang Web có hộp thoại nhận các mô tả về
thông tin mà người dùng cần tìm kiếm. Một máy tìm kiếm lớp trên thường có một số
tùy chọn như là chọn danh sách các máy tìm kiếm mà máy tìm kiếm lớp trên sẽ lấy dữ
liệu từ đó từ một danh sách các máy tìm kiếm thông thường cho trước, thiết lập độ sâu
tìm kiếm, thời gian tìm kiếm…Một trong những hạn chế của máy tìm kiếm lớp trên là
thời gian kiếm thường chậm vì phải chờ kết quả trả về từ các máy tìm kiếm khác. Nếu
một máy tìm kiếm lớp trên gửi truy vấn đến càng nhiều máy tìm kiếm thì tốc độ của nó
càng chậm.
3.1.2. Bộ điều vận
Bộ điều vận của máy tìm kiếm lớp trên gần giống với bộ xử lý truy vấn của máy
tìm kiếm thông thường. Bộ xử lý truy vấn tạo ra các truy vấn đến cơ sở dữ liệu dựa
trên các truy vấn đầu vào còn bộ điều vận thì tạo ra các truy vấn đến máy tìm kiếm
thông thường từ truy vấn của người dùng. Một bộ điều vận phải xác định được các
máy tìm kiếm mà nó sẽ truy vấn và làm thế nào để truy vấn trên chúng.
Hình 10. Một th
Các file đính kèm theo tài liệu này:
- 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.pdf