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

đặ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