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

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 thiết kế của bộ điều vận [18] Một bộ điều vận có thể bao gồm bốn thành phần: Source Selector: Thành phần này sẽ lựa chọn các máy tìm kiếm thông thường để truy vấn trên nó. Nếu bộ điều vận gửi yêu cầu đến quá nhiều máy tìm kiếm thì có thể sẽ làm quá tải tài nguyên mạng và do đó sẽ mất nhiều thời gian để hoàn tất công việc tìm kiếm. Việc quyết định gửi yêu cầu đến máy tìm kiếm nào là rất quan trọng, bởi vì mỗi máy tìm kiếm khác nhau sẽ cho tập dữ liệu khác nhau và sẽ ảnh hưởng đến kết quả tìm kiếm của máy tìm kiếm lớp trên. Nếu máy tìm kiếm X cho kết quả trả về quá tốt, hơn hẳn máy tìm kiếm Y và Z, thì máy tìm kiếm lớp trên kết hợp cả ba máy này 36 chưa chắc đã có kết quả tìm kiếm tốt hơn kết quả của X. Tuy nhiên, nếu kết hợp các kết quả của các máy tìm kiếm khác không quá tốt lại có thể giúp cho kết quả tốt hơn. Query Generator: thực hiện việc sửa đổi các truy vấn sao cho phù hợp với mỗi máy tìm kiếm nguồn. Mỗi máy tìm kiếm thường chỉ làm việc hiệu quả trên một số dạng truy vấn nhất định. Do đó, một truy vấn không thích hợp sẽ mang lại kết quả tìm kiếm không tốt. Request Generator: Thành phần tạo yêu cầu kết hợp truy vấn của người dùng với máy tìm kiếm nguồn được lựa chọn và lựa chọn truy vấn sửa đổi để tạo một yêu cầu hợp lệ. Request Submitter: Thành phần này nhận các yêu cầu từ request generator và thực thi chúng. Request submitter phải tương tác với các giao thức cấp thấp và đảm bảo rằng các lỗi xảy ra được ghi lại một cách thích hợp. 3.1.3. Bộ xử lý kết quả Bộ xử lý kết quả của một máy tìm kiếm lớp trên nhận kết quả tìm kiếm của các máy tìm kiếm thông thường và xử lý chúng để chuyển sang cho mô đun tính hạng. Các kết quả gửi tới mô đun tính hạng từ bộ xử lý kết quả cũng giống với các kết quả nhận được từ cơ sở dữ liệu trong máy tìm kiếm thông thường. Bộ xử lý kết quả nhận các hồi đáp từ máy tìm kiếm và trích xuất chúng từ các kết quả đơn lẻ. Trang phản hồi từ một máy tìm kiếm chỉ chứa thông tin tối thiểu về mỗi kết quả. Và thông tin được cung cấp trong đầu ra của các máy tìm kiếm khác nhau cũng rất đa dạng, theo nghĩa mỗi máy tìm kiếm có một dạng đầu ra khác nhau. Ví dụ một máy tìm kiếm có thể cung cấp tên, địa chỉ URL, bản tóm tắt, trong khi một máy tìm kiếm khác có thể cung cấp tên, ngày tháng, địa chỉ URL, ngữ cảnh của truy vấn…. Cùng một trang Web được trả về từ hai máy tìm kiếm khác nhau có thể trông sẽ khác nhau. Một bộ xử lý kết quả tiên tiến có thể thực hiện hành động thu thập thông tin để bổ sung thêm dữ liệu vào mỗi kết quả nhằm làm giàu cho dữ liệu. Hơn nữa, trong các kết quả trả về từ các máy tìm kiếm nguồn khác nhau có thể có những kết quả giống nhau. Vì vậy, bộ xử lý kết quả cần phải nhận biết các kết quả trùng lặp này và loại bỏ bớt những kết quả thừa, chỉ giữ lại một kết quả duy nhất. 3.1.4. Mô đun tính hạng Cũng giống như mô đun tính hạng trong các máy tìm kiếm thông thường, mô đun tính hạng của một máy tìm kiếm lớp trên thực hiện việc tính hạng cho mỗi kết quả 37 trong nguồn dữ liệu nhận được từ bộ xử lý kết quả. Máy tìm kiếm lớp trên cần phải có các thuật toán hiệu quả để có thể hiểu được đâu là kết quả phù hợp nhất với người dùng trong tập hợp kết quả tìm kiếm từ nhiều nguồn khác nhau, từ đó trả về kết quả theo thứ tự xếp hạng mới. Không giống như các máy tìm kiếm thông thường, máy tìm kiếm lớp trên bị giới hạn thông tin về các kết quả nhận được. Sự thiếu thốn thông tin này làm cho việc tính hạng trở nên khó khăn hơn. 3.2. Mô hình máy tìm kiếm ảnh lớp trên MetaSEEk Trong những năm gần đây, cùng với sự phát triển không ngừng của các dịch vụ trên Internet, các máy tìm kiếm mới ra đời ngày càng nhiều với chức năng ngày càng phong phú và đa dạng. Đặc biệt trong đó có sự ra đời của các máy tìm kiếm lớp trên. Một số máy tìm kiếm lớp trên điển hình phải kể đến như là: Google CSE, Helios, Dogpile, VisualSEEk, WebSEEk, MetaSEEk, …. Trong đó MetaSEEk [11] là một máy tìm kiếm lớp trên chuyên tìm kiếm các ảnh trên Web dựa vào nội dung của ảnh. Phần này sẽ tập trung trình bày mô hình của máy tìm kiếm ảnh lớp trên MetaSEEk. Hình 11. Kiến trúc tổng thể của MetaSEEk [11] 38 Cũng giống như các máy tìm kiếm lớp trên khác, mô hình của MetaSEEk gồm có ba thành phần chính: bộ dịch truy vấn (query translator), bộ điều vận (query dispatcher) và giao diện hiển thị (display interface). Khi nhận được một câu truy vấn từ phía người dùng, bộ điều vận sẽ chọn các máy tìm kiếm nguồn thích hợp dựa trên cơ sở dữ liệu về khả năng thực thi của từng truy vấn đã thực hiện trước đó. Cơ sở dữ liệu này chứa các điểm số chỉ ra khả năng thực thi tốt hay kém của từng truy vấn trong quá khứ đối với mỗi tùy chọn tìm kiếm. Các điểm số này được gọi là các điểm số hiệu năng (performance score) của các tùy chọn tìm kiếm đối với mỗi truy vấn, và cơ sở dữ liệu chứa các điểm số như vậy được gọi là cơ sở dữ liệu hiệu năng (performance database). Sau khi đã chọn được các máy tìm kiếm nguồn, bộ dịch truy vấn chuyển các truy vấn sang dạng thích hợp và gửi tới các máy tìm kiếm nguồn đã được chọn. Cuối cùng, thành phần hiển thị kết hợp và xếp hạng lại các kết quả nhận được từ các máy tìm kiếm và hiển thị cho người dùng. MetaSEEk đánh giá chất lượng của các kết quả trả về bởi mỗi tùy chọn tìm kiếm dựa trên các phản hồi từ phía người sử dụng. 3.2.1. Truy vấn trực quan dựa trên nội dung Như đã nói ở các chương trước, đầu vào của một máy tìm kiếm ảnh có thể là một từ khóa hay một bức ảnh. Người sử dụng có thể đưa vào máy tìm kiếm ảnh một truy vấn có dạng là một ảnh được lấy từ một tập ảnh mẫu ngẫu nhiên hoặc từ một tập các ảnh trả về bởi một truy vấn dạng từ khóa, hoặc truy vấn có thể là một URL của một ảnh trên Web. Các truy vấn có dạng như vậy được gọi là các truy vấn trực quan dựa trên nội dung (Content-based visual query). Với truy vấn là một ảnh, máy tìm kiếm tính toán các đặc trưng của ảnh đầu vào này và sử dụng các đặc trưng này để tìm các ảnh gần giống với ảnh truy vấn nhất trong cơ sở dữ liệu. Tìm kiếm ảnh dựa trên từ khóa có thể được sử dụng để phân nhóm các ảnh theo chủ để và do đó làm giảm phạm vi tìm kiếm. Để có thể xử lý hiệu quả các truy vấn trực quan trong cơ sở dữ liệu ảnh lớn, các máy tìm kiếm cũng cần phải sử dụng các kỹ thuật phân cụm và đánh chỉ mục trên các vector đặc trưng của ảnh. 3.2.2. Giao diện truy vấn MetaSEEk tìm kiếm ảnh dựa trên bốn máy tìm kiếm nguồn là: VisualSEEk, WebSEEk, QBIC, và Virage. Mỗi máy tìm kiếm nguồn đều có các tính năng cũng như các hạn chế riêng. VisualSEEk, QBIC và Virage cung cấp các phương thức cho việc tìm kiếm ảnh số dựa trên các đặc trưng trực quan bằng việc sử dụng các mẫu. QBIC và 39 VisualSEEk cho phép tùy chỉnh các tìm kiếm bằng việc sử dụng các phác thảo trực quan (ví dụ như chỉ định bảng màu) hoặc đưa vào một ảnh mẫu, trong khi đó Virage cho phép người dùng xác định trọng số độ quan trọng của mỗi đặc trưng trong tìm kiếm. Ngoài ra, QBIC còn cung cấp dịch vụ tìm kiếm ảnh dựa trên từ khóa. WebSEEk là một máy tìm kiếm và phân loại ảnh bán tự động. Nó hỗ trợ tìm kiếm cả dựa trên nội dung hiển thị và dựa trên văn bản, tuy nhiên MetaSEEk chỉ sử dụng khả năng tìm kiếm ảnh dựa trên văn bản của WebSEEk. Hình 12. Giao diện hiển thị của MetaSEEk MetaSEEk cung cấp giao diện cho phép tìm kiếm ảnh dựa trên cả nội dung hiển thị và từ khóa. Với truy vấn trực quan dựa trên nội dung hiển thị, người dùng có thể chọn bất kỳ ảnh mẫu nào từ các cơ sở dữ liệu được hỗ trợ, hoặc đưa vào một URL của một ảnh trên Web. Giao diện của MetaSEEk cho phép người dùng tùy chọn các đặc trưng để tìm kiếm. Hai đặc trưng có sẵn cho người dùng lựa chọn là: màu sắc và kết cấu. Người dùng có thể lựa chọn tìm kiếm ảnh dựa trên màu sắc hoặc dựa trên kết cấu hoặc dựa trên cả hai đặc trưng này. Như đã nói ở trên, với mỗi tùy chọn sẽ chỉ có một số máy tìm kiếm nguồn được sử dụng. Bộ điều vận nhận biết được khả năng tìm kiếm của mỗi cơ sở dữ liệu và sẽ quyết định gửi truy vấn tới các máy tìm kiếm nào. Ngoài ra, người sử dụng còn có thể chỉ định thời gian tìm kiếm tối đa, số lượng các tùy chọn tìm kiếm, và thể loại quan tâm. Người sử dụng cũng có thể điểu chỉnh số lượng các truy vấn được gửi đến các công cụ tìm kiếm riêng rẽ tùy thuộc vào tải mạng. 40 Trong thời gian lưu lượng mạng thấp, người sử dụng có thể làm tăng các truy vấn đồng thời. Việc chờ đợi trong một khoảng thời gian tối đa ngăn không cho hệ thống bị chậm trễ từ việc hồi đáp chậm trễ của các máy tìm kiếm nguồn. 3.2.3. Bộ điều vận Mỗi khi nhận được một truy vấn từ phía người dùng, bộ điều vận chọn các máy tìm kiếm nguồn và tùy chọn tìm kiếm nguồn để gửi câu truy vấn đến. Một tùy chọn tìm kiếm là một phương pháp truy vấn trên một công cụ tìm kiếm cụ thể. Ví dụ, một truy vấn gửi tới VisualSEEk yêu cầu tìm kiếm ảnh dựa trên kết cấu là một tùy chọn tìm kiếm. Bộ điều vận tạo quyết định dựa trên loại truy vấn được gửi đến máy tìm kiếm lớp trên và cơ sở dữ liệu chứa điểm số chỉ khả năng thực thi của các truy vấn trong quá khứ. Nếu người dùng yêu cầu một ảnh mẫu ngẫu nhiên hay một từ khóa truy vấn, hệ thống đơn giản chỉ đặt ra các câu hỏi tới các máy tìm kiếm mà hỗ trợ những hành động này (QBIC, Virage và VisualSEEk hỗ trợ truy vấn mẫu ngẫu nhiên, QBIC và WebSEEk hỗ trợ truy vấn dạng từ khóa). Với các truy vấn trực quan dựa trên nội dung, việc lựa chọn máy tìm kiếm nguồn là dựa trên cơ sở dữ liệu hiệu năng. Cơ sở dữ liệu này chứa điểm số chỉ ra thế nào là tốt hay thế nào là xấu với mỗi tùy chọn tìm kiếm đã được thực hiện trong quá khứ trên các máy tìm kiếm với mọi ảnh truy vấn. Một truy vấn trực quan được xác định bởi một ảnh, một nhóm các đặc trưng, và một chủ đề. Khi nhận được một truy vấn, MetaSEEk tìm kiếm trong cơ sở dữ liệu hiệu năng và tìm kiếm điểm số hiệu năng của ảnh truy vấn. Trong cấu trúc của cơ sở dữ liệu nói trên, mỗi hàng tương ứng với một truy vấn đã được thực hiện trước đó. Mỗi cột điểm số tương ứng với một tùy chọn tìm kiếm. Bộ điều vận sẽ quyết định chọn các tùy chọn tìm kiếm có điểm số cao nhất mà phù hợp với những yêu cầu của người dùng. MetaSEEk đánh giá chất lượng của các kết quả trả về của mỗi tùy chọn tìm kiếm dựa trên phản hồi của người dùng. Một thủ tục thăm dò tự động được thực hiện để thiết lập điểm số hiệu năng ban đầu nhằm xây dựng một cơ sở dữ liệu hiệu năng dựa trên một số mẫu huấn luyện. Đối với các truy vấn mới không có điểm số hiệu năng được ghi trong cơ sở dữ liệu, các tác giả đưa ra một giải pháp đơn giản nhất là chọn ngẫu nhiên một tùy chọn tìm kiếm để thực hiện truy vấn. Ngoài ra, hệ thống còn xét tới một hướng tiếp cận khác là liên hệ các truy vấn mới với các truy vấn trong quá khứ mà ta đã có thông tin về hiệu suất thực thi. Các ảnh trong cơ sở dữ liệu được phân thành các chủ đề dựa trên nội dung hiển thị của chúng. Mỗi chủ đề gồm các nhóm đặc trưng: màu sắc, kết cấu và 41 cả hai loại đặc trưng trên. Khi truy vấn của người dùng là một truy vấn mới, hệ thống tải ảnh về và kết hợp nó với các cụm tương ứng để nhận được một danh sách các cụm phù hợp nhất. Các ảnh được chọn từ một số cụm gần giống nhất sẽ được hiển thị cho người dùng. Bộ điều vận có thể chọn các máy tìm kiếm phù hợp dựa trên điểm số hiệu năng trung bình của cụm được chọn bởi người sử dụng. Cuối cùng, ảnh mới sẽ được lưu vào cơ sở dữ liệu để sử dụng cho những truy vấn lần sau. MetaSEEk sử dụng thuật toán phân cụm K-means để phân cụm các ảnh trong cơ sở dữ liệu. Cứ sau mỗi khi có 10 ảnh mới được lưu vào cơ sở dữ liệu thì hệ thống sẽ thực hiện thuật toán phân cụm. Màu sắc và kết cấu là các đặc trưng được sử dụng cho việc phân cụm. Phân loại theo chủ đề Hệ thống phân nhóm các ảnh theo chủ đề để ràng buộc phạm vi tìm kiếm. Cơ sở dữ liệu của các máy tìm kiếm nguồn thường có một số loại riêng biệt. Ví dụ, cơ sở dữ liệu của QBIC bao gồm phần lớn là ảnh về con người, trong khi đó cơ sở dữ liệu của Virage có nhiều thể loại khác. Nếu người dùng quan tâm tìm kiếm ảnh của một em bé, có nhiều khả năng QBIC sẽ mang lại kết quả thích hợp hơn trong thời gian ngắn hơn. Hệ thống tận dụng lợi thế của thực tế này bằng cách cung cấp khả năng tìm kiếm trong một phạm vi của một chủ đề cụ thể. Nếu người sử dụng chọn một chù đề cụ thể, thì người đó giả định rằng chỉ tìm kiếm các ảnh trong chủ đề đó. Cấu trúc cơ sở dữ liệu Cơ sở dữ liệu của MetaSEEk chứa các vector đặc trưng (màu sắc và kết cấu), điểm số hiệu suất, các phân cụm, và các chủ đề cho tất cả các ảnh mà đã được truy vấn trên MetaSEEk. Tất cả những thông tin này là cần thiết cho bộ điều vận trong việc lựa chọn các máy tìm kiếm thích hợp cho các truy vấn đầu vào. Cơ sở dữ liệu được tổ chức theo cấu trúc phân cấp. Đầu tiên các ảnh được phân loại theo chủ đề dựa trên ngữ nghĩa của chúng (ví dụ như loài vật, con người). Việc phân loại ảnh vào chủ đề nào là do người dùng thực hiện. Thuật toán K-means được sử dụng để phân cụm các ảnh trong mỗi chủ đề vào các lớp dựa trên các đặc trưng về màu sắc, kết cấu hoặc cả hai loại đặc trưng. 42 Hình 13. Cấu trúc phân cấp của cơ sở dữ liệu Tại tầng thấp nhất của cơ sở dữ liệu, mỗi ảnh có một bản ghi chứa thông tin như trong bảng 1. Trong đó cột bên trái là các tùy chọn tìm kiếm còn cột bên phải là điểm số tương ứng đối với mỗi tùy chọn. Các điểm số này được cập nhật mỗi khi ảnh đó được truy vấn dựa vào phản hồi của người sử dụng. Bảng 1. Ví dụ về bản ghi của một ảnh trong cơ sở dữ liệu 3.2.4. Thành phần hiển thị Mỗi khi các kết quả được lấy về từ các máy tìm kiếm nguồn, chúng được tổ chức lại và hiển thị cho người dùng bởi thành phần hiển thị. Quá trình này phụ thuộc vào truy vấn của người sử dụng: truy vấn là một ảnh mẫu ngẫu nhiên, hay truy vấn là từ 43 khóa hay là ảnh. Nếu truy vấn là một ảnh mẫu ngẫu nhiên hoặc là từ khóa thì các kết quả trả về từ các máy tìm kiếm nguồn sẽ được trộn lẫn và hiển thị cho người sử dụng một cách ngẫu nhiên. Trong trường hợp này, thứ tự hiển thị của các kết quả là không quan trọng. Đối với các truy vấn trực quan dựa trên nội dung, các ảnh được xếp hạng trước khi hiển thị cho người dùng. Tìm kiếm ảnh dựa trên nội dung hiển thị trả về một danh sách các ảnh được sắp xếp theo thứ tự gần giống nhất đối với ảnh truy vấn. MetaSEEk thực hiện việc xếp hạng những ảnh này bằng cách sử dụng điểm số hiệu năng trong cơ sở dữ liệu. Các ảnh được trả về bởi mỗi tùy chọn tìm kiếm sẽ được xen vào trước khi hiển thị chúng cho người sử dụng. Điểm số hiệu năng của ảnh truy vấn sẽ xác định thứ tự hiển thị và số các ảnh trong mỗi nhóm xen vào kết quả của mỗi tùy chọn tìm kiếm. Ví dụ, chúng ta giả sử rằng các ảnh nhận được từ hai tùy chọn tìm kiếm với điểm số hiệu năng là 2 và 1. Thành phần hiển thị sẽ hiển thị 2 ảnh từ tùy chọn tìm kiếm có điểm số là 2, và 1 ảnh từ tùy chọn tìm kiếm với điểm số là 1 cho đến khi tất cả các ảnh trả về được hiển thị hết. 3.2.5. Đánh giá Hệ thống tìm kiếm ảnh lớp trên MetaSEEk đã được các tác giả tiến hành một số thử nghiệm để đánh giá hiệu suất thực hiện của nó [11]. Các thử nghiệm này được thực hiện với các loại câu truy vấn khác nhau và với mỗi thử nghiệm thì được thực hiện hai lần để đánh giá sự cải thiện của việc sử dụng điểm số hiệu năng trong tìm kiếm. Sau đó các kết quả thực nghiệm cũng được so sánh với phiên bản trước của MetaSEEk (phiên bản không phân loại ảnh theo chủ đề) và với một máy tìm kiếm lớp trên không sử dụng việc đánh giá hiệu năng. Kết quả so sánh cho thấy rằng MetaSEEk có khả năng tìm kiếm tốt hơn hai hệ thống còn lại. Qua các kết quả thực nghiệm, ta thấy rằng hiệu suất của một hệ thống tìm kiếm lớp trên có thể được cải thiện rất nhiều nếu công cụ tìm kiếm tích hợp và lựa chọn thông minh bởi việc đánh giá hiệu năng cho các lớp truy vấn khác nhau và sử dụng phản hồi của người dùng trong việc xếp hạng các kết quả trả về. 3.3. Xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên Sau khi nhận được các kết quả trả về từ các máy tìm kiếm nguồn, máy tìm kiếm lớp trên cần phải tổng hợp và sắp xếp các kết quả này thành một danh sách ảnh duy nhất và trả về cho người sử dụng. Danh sách này được sắp xếp theo thứ tự những ảnh phù hợp với 44 truy vấn của người dùng hơn thì có thứ hạng cao hơn. Việc sắp xếp các ảnh như vậy còn được gọi là xếp hạng lại. Tuy nhiên, việc xếp hạng lại các kết quả này là một thách thức lớn đối với máy tìm kiếm lớp trên bởi vì tính không đồng nhất giữa các máy tìm kiếm nguồn. Các kết quả nhận được từ mỗi máy tìm kiếm nguồn thường được xếp hạng dựa trên những đặc trưng khác nhau của ảnh. Một số máy tìm kiếm ảnh thông thường tìm kiếm và xếp hạng ảnh chỉ dựa trên các đặc trưng về văn bản của ảnh trong khi một số máy tìm kiếm khác tìm kiếm dựa vào các đặc trưng về nội dung hiển thị. Ví dụ Google Image Search, Yahoo Image Search và Bing tìm kiếm ảnh dựa trên văn bản trong khi Byo Image Search tìm kiếm ảnh dựa trên màu sắc còn Tiltomo thì tìm kiếm dựa trên màu sắc và kết cấu. Vì thế, tập các ảnh nhận được từ các máy tìm kiếm nguồn thường rất đa dạng. Do đó khó khăn ở đây là làm thế nào để tổng hợp các ảnh này trong một danh sách duy nhất và các ảnh được sắp xếp một cách hợp lý. Tuy nhiên, khó khăn này cũng chính là một lợi thế bởi vì các ảnh được trả về từ một máy tìm kiếm nguồn thường có xu hướng nhóm thành một cụm dựa theo đặc trưng tìm kiếm của máy tìm kiếm nguồn đó. Hơn nữa chúng ta còn có thể tận dụng được kết quả xếp hạng sẵn có của các ảnh này ở máy tìm kiếm nguồn. Một thách thức khác đối với việc xếp hạng trong máy tìm kiếm ảnh lớp trên chính là vấn đề thời gian. Bởi vì quá trình từ lúc nhận truy vấn của người dùng, gửi yêu cầu và nhận kết quả trả về từ các máy tìm kiếm nguồn, xếp hạng các kết quả nhận được đến lúc trả về một danh sách ảnh đã được sắp xếp cho người dùng là một quá trình được thực hiện trực tuyến nên các máy tìm kiếm ảnh lớp trên cần phải có các thuật toán xếp hạng hiệu quả, đảm bảo yêu cầu về mặt thời gian. Từ những phân tích về những khó khăn và thuận lợi ở trên, có một số phương pháp xếp hạng đã được áp dụng trong các máy tìm kiếm ảnh lớp trên. Một phương pháp đã được sử dụng trong máy tìm kiếm ảnh lớp trên MetaSEEk [11] là phân cụm các ảnh theo chủ đề và theo các đặc trưng hiển thị cùng với việc dựa vào các tùy chọn tìm kiếm và phản hồi của người dùng để tìm ra tập ảnh thích hợp nhất. Sau đó thứ hạng của một ảnh trong tập ảnh này được tính bằng cách kết hợp giữa thứ hạng của ảnh đó ở máy tìm kiếm nguồn với đánh giá về chất lượng của tập ảnh nhận được từ máy tìm kiếm nguồn mà chứa ảnh đó. Bo Luo và cộng sự trong nghiên cứu về việc sử dụng các đặc trưng của ảnh [14] cũng đã đề xuất hai phương pháp xếp hạng dựa trên cả đặc trưng văn bản và đặc trưng hiển thị của ảnh. Một phương pháp là phân cụm các ảnh dựa trên các đặc trưng về màu sắc, hình dáng từ tập ảnh khởi tạo thu được từ các máy tìm kiếm chỉ dựa trên văn bản. Phương pháp thứ hai sử dụng phản hồi của người sử dụng để xếp hạng các ảnh. Phương 45 pháp này chọn ra một số ảnh mẫu từ các cụm (các cụm này có thể thu được từ việc tìm kiếm ảnh dựa trên văn bản) và hiển thị cho người dùng lựa chọn. Dựa vào mối quan tâm của người sử dụng, hệ thống tiến hành tìm các ảnh gần giống nhất với ảnh đã được lựa chọn và sắp xếp chúng theo thứ tự giảm dần về độ tương đồng. Nhận thấy lợi ích từ việc kết hợp giữa nội dung hiển thị và văn bản của ảnh, trong khóa luận này, tôi sử dụng thuật toán xếp hạng ảnh VisualRank cho cả hai đặc trưng trên của ảnh như đã được đề cập đến ở chương hai. Tuy nhiên, quan tâm đến vấn đề thời gian thực hiện thuật toán, tôi phân các câu truy vấn thành hai trạng thái: các truy vấn cũ và truy vấn mới. Truy vấn cũ là truy vấn đã được truy vấn ở máy tìm kiếm lớp trên. Truy vấn mới là truy vấn chưa gặp bao giờ hoặc không gần giống với câu truy vấn nào có trước. Đối với một truy vấn mới, tôi tiến hành xếp hạng chỉ dựa trên văn bản rồi trả về kết quả cho người dùng. Sau đó, tôi xếp hạng lại cho các ảnh này dựa trên cả văn bản và nội dung hiển thị để sử dụng cho lần tìm kiếm sau. Quá trình xếp hạng lại này được thực hiện ngoại tuyến. Vì tận dụng được lợi thế về mặt tốc độ của việc phân tích và xử lý văn bản nên thời gian đáp ứng của hệ thống luôn ở mức cho phép. Tóm tắt chương ba Khóa luận đã trình bày về mô hình chung máy tìm kiếm lớp trên, đồng thời giới thiệu chi tiết một mô hình máy tìm kiếm ảnh lớp trên và một số phương pháp xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên. Trong chương này, tôi cũng đã đưa ra một cách giải quyết vấn đề thời gian xếp hạng trong máy tìm kiếm ảnh lớp trên. Trong chương tiếp theo, khóa luận sẽ giới thiệu một mô hình tìm kiếm ảnh lớp trên ứng dụng thuật toán xếp hạng ảnh đã được trình bày ở trên và những vấn đề liên quan đến việc thử nghiệm mô hình này. 46 Chương 4. Thử nghiệm 4.1. Mô hình thử nghiệm 4.1.1. Cách tiếp cận Quá trình khảo sát và đánh giá các phương pháp xếp hạng ảnh cho thấy thuật toán VisualRank [39] [40] là một thuật toán xếp hạng ảnh đơn giản và cho hiệu quả khá cao. Tuy nhiên, cách làm của Jing và Baluja là chỉ dựa trên độ tương đồng về nội dung hiển thị của ảnh. Một cách trực quan, chúng ta có thể thấy rằng các ảnh có nội dung hiển thị gần giống nhau thì thường được người dùng đặt tên gần giống nhau, và các bình luận cũng thường về chủ đề mà nó hiển thị. Do đó, có thể thấy rằng vùng văn bản đi kèm ảnh có thể mô tả được phần nào nội dung hiển thị của ảnh. Vì vậy, trong khóa luận này, tôi sử dụng thuật toán xếp hạng ảnh VisualRank cho cả đặc trưng hiển thị và đặc trưng văn bản của ảnh. Tuy nhiên, nhận thấy rằng đặc trưng hiển thị của ảnh vẫn phản ánh nội dung ảnh một cách chân thực nhất nên trong thực nghiệm các đặc trưng hiển thị vẫn được gán cho một trọng số cao hơn. Hơn nữa, Y.Jing và S.Baluja [39] [40] chỉ ra rằng không thể tính ma trận tương đồng cho hàng tỉ bức ảnh trên web. Một cách giải quyết đơn giản là chỉ xây dựng ma trận tương đồng cho một tập N ảnh trả về đầu tiên của các máy tìm kiếm thương mại. Vì thế, tôi thực hiện áp dụng thuật toán VisulRank cho mô hình máy tìm kiếm ảnh lớp trên được đề xuất trong khóa luận. Mô hình mà khóa luận trình bày dưới đây sẽ tìm kiếm ảnh dựa trên một số máy tìm kiếm ảnh thông thường, sau đó trích xuất N ảnh trả về đầu tiên từ các máy tìm kiếm nguồn này và sử dụng thuật toán nói trên để xếp hạng lại cho chúng. Một nhược điểm lớn của việc xếp hạng dựa trên nội dung hiển thị của ảnh là thời gian tính hạng. Bởi vì việc tải các ảnh từ Web về, trích xuất các thành thành phần đặc trưng, xây dựng đồ thị tương đồng là tốn rất nhiều thời gian. Do đó, để có thể áp dụng thuật toán một cách hiệu quả vào máy tìm kiếm lớp trên, khóa luận sử dụng các cách xếp hạng khác nhau đối với mỗi trạng thái khác nhau của câu truy vấn người dùng. Câu truy vấn của người dùng được chia thành hai trạng thái: câu truy vấn mới và câu truy vấn cũ. Một câu truy vấn được xem là mới nếu nó chưa được bất kỳ người dùng nào truy vấn một lần nào trên máy tìm kiếm. Hay nói cách khác là câu truy vấn đó chưa có trong cơ sở dữ liệu. Ngược lại, câu truy là cũ nếu nó đã tồn tại trong cơ sở dữ liệu của máy tìm kiếm. Đối với câu truy vấn mới, máy tìm kiếm xếp hạng các ảnh chỉ dựa trên đặc trưng văn bản. Sau 47 đó, máy tìm kiếm lưu câu truy vấn này vào cơ sở dữ liệu và tiến hành xếp hạng lại cho các ảnh tìm được ứng với câu truy vấn dựa trên cả nội dung hiển thị và nội dung văn bản của ảnh để sử dụng cho các lần truy vấn sau. Với cách làm như vậy, máy tìm kiếm lớp trên luôn đảm bảo yêu cầu về mặt thời gian tìm kiếm cho người dùng. Để đảm bảo kết quả trả về cho người dùng luôn được cập nhật, sau một khoảng thời gian nhất định, máy tìm kiếm sẽ lấy tất cả các câu truy vấn đã có trong cơ sở dữ liệu và gửi đến các máy tìm kiếm nguồn để cập nhật cơ sở dữ liệu ảnh. Sau đó tiến hành tính hạng lại cho tập các ảnh này. Khi tính lại ma trận tương đồng cho các ảnh, để tối ưu hóa việc tính toán, ta chỉ tính ma trận tương đồng cho các ảnh mới tải về với nhau và cho các ảnh mới tải về với các ảnh đã sẵn có trong cơ sở dữ liệu. Sau đó kết hợp các ma trận này với ma trận tương đồng của các ảnh đã có từ trước thành một ma trận duy nhất. Như vậy, chúng ta đã tiết kiệm được thời gian tính ma trận tương đồng cho các ảnh đã có trong cơ sở dữ liệu. Khi số lượng câu truy vấn của người dùng là rất nhiều, việc lưu trữ các truy vấn trở thành một vấn đề cần phải được quan tâm. Nếu lưu trữ tất cả các câu truy vấn thì chi phí cho việc lưu trữ là rất lớn và việc xếp hạng lại cho tất cả các câu truy vấn có thể sẽ tốn quá nhiều thời gian và không thể kiểm soát nổi. Hơn nữa, việc lưu trữ mãi một câu truy vấn rất ít khi được sử dụng là không hiệu quả. Do đó, một giải pháp được đề ra là chỉ lưu các câu truy vấn được cho là phổ biến và cơ sở dữ liệu các câu truy vấn sẽ thường xuyên được làm mới. Có thể đặt ra một ngưỡng về số lần được sử dụng trong một khoảng thời gian của một câu truy vấn để xác định xem nó có là phổ biến hay không. Trong thời gian đầu, khi số lượng các câu truy vấn còn ít, tất cả các câu truy vấn có thể đều được coi là phổ biến. Nhằm mục đích hướng tới nhóm người dùng Việt Nam, mô hình máy tìm kiếm ảnh mà khóa luận đề xuất có tích hợp một bộ từ điển để hỗ trợ cho các truy vấn tiếng Việt. Với các truy vấn tiếng Việt, máy tìm kiếm sẽ dịch nó sang tiếng Anh rồi mới gửi đến các máy tìm kiếm nguồn. Với việc hỗ trợ cho cả truy vấn tiếng Việt và tiếng Anh, mô hình máy tìm kiếm ảnh mà khóa luận đề xuất là rất thân thiện với người dùng Việt Nam. Dưới đây là mô hình máy tìm kiếm ảnh lớp trên áp dụng phương pháp và các kỹ thuật đã được nêu ở trên. 4.1.2. Mô hình đề xuất và các thành phần trong mô hình ™ Đầu vào: Một truy vấn có dạng là một chuỗi các từ khóa. ™ Đầu ra: Một danh sách các ảnh đã được sắp xếp theo thứ tự giảm dần về độ phù hợp với truy vấn. 48 ™ Mô hình đề xuất Hình 14. Mô hình đề xuất ™ Các thành phần trong mô hình ‐ Giao diện hiển thị o Là thành phần giao tiếp với người dùng, thực hiện hai chức năng chính: ƒ Nhận chuỗi từ khóa truy vấn từ phía người dùng để gửi cho bộ điều vận. 49 ƒ Nhận danh sách các ảnh đã được sắp xếp từ mô đun xếp hạng hoặc từ CSDL và hiển thị chúng cho người sử dụng. ‐ Bộ điều vận o Kiểm tra xem câu truy vấn là tiếng Anh hay tiếng Việt. Nếu là một câu truy vấn tiếng Việt thì sử dụng từ điển để dịch nó sang tiếng Anh. o Tiền xử lý câu truy vấn: đưa về chữ thường, loại bỏ từ dừng và các ký tự đặc biệt, đưa về từ gốc. o Lấy các truy vấn đã có trong CSDL (đường dữ liệu (1)) để kiểm tra xem câu truy vấn nhận được là một câu truy vấn mới hay là một truy vấn cũ. ƒ Nếu là một truy vấn mới: • Chọn các máy tìm kiếm nguồn sẽ gửi yêu cầu đến. Sửa đổi câu truy vấn về dạng phù hợp với dạng truy vấn của từng máy tìm kiếm nguồn đã được chọn rồi gửi yêu cầu tới các máy tìm kiếm này. ƒ Nếu là một truy vấn cũ: Gửi thông báo và id của truy vấn đến giao diện hiển thị (đường dữ liệu (2)). o Sau một khoảng thời gian nhất định, bộ điều vận sẽ lấy các truy vấn có sẵn từ CSDL và gửi yêu cầu đến các máy tìm kiếm nguồn để cập nhật CSDL (đường dữ liệu (3)). ‐ Bộ xử lý kết quả o Nhận kết quả trả về từ các máy tìm kiếm nguồn, tổng hợp các kết quả này lại thành một danh sách duy nhất và xử lý các kết quả trùng lặp. o Trích xuất các ảnh và các thông tin cần thiết liên quan đến các ảnh để gửi cho mô đun xếp hạng. ‐ Mô đun xếp hạng o Nếu truy vấn của người dùng là một truy vấn mới: ƒ Nhận các thông tin cần thiết về các ảnh từ bộ phận xử lý kết quả, thực hiện tính hạng cho ảnh dựa theo nội dung văn bản rồi trả lại kết quả cho thành phần hiển thị. ƒ Sau đó đánh chỉ mục lại cho các ảnh, kết hợp giữa các đặc trưng về nội dung hiển thị và đặc trưng văn bản của ảnh để tính hạng lại cho ảnh. Lưu kết quả tính hạng vào CSDL để sử dụng cho lần truy vấn sau ‐ Cơ sở dữ liệu o Lưu trữ các ảnh và các thông tin về ảnh. Các ảnh trong CSDL được phân cụm theo tập câu hỏi người dùng. 50 o Lưu trữ tập các câu hỏi mà người dùng đã truy vấn đến máy tìm kiếm lớp trên và kết quả xếp hạng của các câu hỏi này. 4.2. Môi trường và các thành phần trong hệ thống phần mềm 4.2.1. Cấu hình phần cứng Bảng 2. Cấu hình phần cứng sử dụng trong thực nghiệm Thành phần Chỉ số CPU 1 Pentium IV 3.06 GHz RAM 1GB OS WindowsXP Service Pack 2 Bộ nhớ ngoài 80GB 4.2.2. Các thành phần trong hệ thống phần mềm • Công cụ phần mềm sử dụng: Bảng 3. Một số phần mềm sử dụng STT Tên phần mềm Tác giả Nguồn 1 eclipse-SDK- 3.4.1-win32 2 XAMPP 1.7.3 windows.html#522 3 Apache Tomcat 6.0.26 60.cgi • Các thư viện sử dụng: Bảng 4. Một số thư viện sử dụng STT Tên thư viện Tác giả Nguồn 1 Lire-0.8 Caliph & Emir 51 2 Jama-1.0.2 Geoffrey Fox 3 Json-simple-1.1 Douglas Crockford 4 nusoap NuSphere & Dietrich Ayala 5 google-api- translate-java- 0.92.jar translate-java/downloads/list Ngoài các công cụ trên, tôi tiến hành cài đặt các mô đun xử lý dựa trên ngôn ngữ Java, bao gồm các gói phần mềm chính như sau: ‐ searcher: Sử dụng cho việc thu thập dữ liệu từ các máy tìm kiếm ảnh Google và Yahoo. ‐ CBIRMetaSearch: Thực hiện các nhiệm vụ như đối với các thành phần của máy tìm kiếm lớp trên: xử lý truy vấn, xử lý kết quả, tính hạng. ‐ Translator: Kiểm tra ngôn ngữ của truy vấn. Nếu là truy vấn tiếng Việt thì gửi nó đến Google Translate để dịch sang tiếng Anh. Ngoài ra, mô đun giao diện được viết dựa trên ngôn ngữ PHP bao gồm một file ImageMetaSearch.php hiển thị giao diện cho phép người dùng nhập vào một chuỗi truy vấn và hiển thị kết quả. Tôi tạo một web service để thực hiện giao tiếp giữa mô đun giao diện và mô đun xử lý. 52 • Giao diện chương trình Hình 15. Giao diện của chương trình 4.3. Xây dựng tập dữ liệu 4.3.1. Tập truy vấn Để tạo tập truy vấn mẫu phục vụ cho việc đánh giá chất lượng hệ thống, tôi tiến hành tìm các truy vấn được sử dụng thường xuyên nhất. Nhận thấy rằng người dùng thường sử dụng các thẻ ảnh để tìm kiếm ảnh một cách chính xác. Vì thế tôi thực hiện trích rút tập truy vấn từ các thẻ ảnh phổ biến mà người dùng hay sử dụng đã được Flickr1 liệt kê. Trong khóa luận này, tôi chú trọng vào việc tìm các ảnh có nội dung hiển thị gần giống nhau. Qua quá trình khảo sát thực tế, tôi thấy rằng đối với một truy vấn về sự kiện như là “autumn festival” hay một truy vấn mang nghĩa chung chung như là “architecture” thì các ảnh thuộc về những chủ đề như thế này thường rất đa dạng. Đối với các ảnh này, đặc trưng văn bản thường biểu diễn được chủ đề của ảnh nhiều hơn 1 53 đặc trưng hiển thị. Do đó việc sử dụng đặc trưng hiển thị để xếp hạng cho các ảnh thuộc những chủ đề như vậy là không hiệu quả. Vì vậy, trong các thẻ ảnh phổ biến và các thẻ liên quan đến chúng, tôi chỉ lấy các thẻ về các vật, nơi chốn… cụ thể để làm các truy vấn mẫu. Theo cách làm như trên, tôi trích rút được một tập 35 truy vấn từ các thẻ ảnh phổ biến và các thẻ ảnh liên quan đến những thẻ này để sử dụng vào việc đánh giá hệ thống. 4.3.2. Tập máy tìm kiếm nguồn Tập máy tìm kiếm nguồn mà tôi sử dụng để gửi yêu cầu đến và lấy dữ liệu từ đó là hai máy tìm kiếm ảnh Google và Yahoo. Việc chọn hai máy tìm kiếm này để tìm kiếm trên nó là vì hai lý do. Thứ nhất, Google và Yahoo là hai máy tìm kiếm ảnh dựa trên văn bản lớn nhất hiện nay và có chất lượng tìm kiếm khá tốt. Thứ hai, vì cả hai máy tìm kiếm này đều nhận đầu vào là một từ khóa truy vấn, do đó việc truy vấn trên chúng là rất dễ dàng. 4.3.3. Từ điển Bộ từ điển được sử dụng trong thực nghiệm là bộ công cụ Google dịch. Google dịch là một công cụ trực tuyến miễn phí của Google, hỗ trợ phát hiện ngôn ngữ và chức năng dịch đa ngôn ngữ (trong đó có dịch từ tiếng Việt sang tiếng Anh). Bộ công cụ này tương đối dễ sử dụng và có chất lượng dịch từ tiếng Việt sang tiếng Anh khá tốt. 4.4. Quy trình, các phương án thử nghiệm Quy trình thử nghiệm được tiến hành như sau: Thực hiện truy vấn: Lần lượt thực hiện các truy vấn mẫu vào máy tìm kiếm. Mỗi câu truy vấn được thực hiện hai lần để đánh giá chất lượng của hai phương pháp xếp hạng dựa trên văn bản và xếp hạng dựa trên nội dung hiển thị và nội dung văn bản. Thu thập dữ liệu: Với mỗi truy vấn, hệ thống trích rút 64 ảnh trả về đầu tiên từ máy tìm kiếm ảnh Google1 và 50 ảnh trả về đầu tiên từ máy tìm kiếm ảnh Yahoo2. Sau đó tổng hợp các ảnh này trong một danh sách duy nhất và tiến hành xếp hạng lại cho tập các ảnh này. 1 2 54 Xếp hạng: Quá trình xếp hạng được chia thành hai giai đoạn: Giai đoạn 1: Đối với truy vấn mới, xếp hạng dựa trên đặc trưng văn bản. Giai đoạn này được thực hiện trực tuyến. Sử dụng độ đo khoảng cách giữa 2 xâu ký tự để tính độ tương đồng cho các chuỗi văn bản. Các đặc trưng văn bản được sử dụng trong khóa luận này là: tên file ảnh, nhan đề ảnh (title) và vùng văn bản nhỏ đi kèm mô tả ảnh (content). Qua quá trình thực nghiệm, trọng số cho tên file ảnh là 0.3, nhan đề ảnh là 0.1 và trọng số cho vùng văn bản đi kèm ảnh là 0.6 cho kết quả xếp hạng tốt nhất. Thực hiện thuật toán visualRank cho các độ đo tương đồng dựa trên văn bản với số vòng lặp là 100, hệ số hãm là d = 0.85. Ngoài ra, qua khảo sát thực tế, tôi nhận thấy rằng thứ hạng của ảnh do máy tìm kiếm nguồn xếp hạng cũng có một tầm quan trọng rất lớn, và hơn nữa chất lượng tìm kiếm của Google tốt hơn hẳn chất lượng tìm kiếm của Yahoo. Vì thế, với mỗi ảnh tôi cộng thêm một điểm số thứ hạng cũ (là thứ hạng do các máy tìm kiếm nguồn tính được) với tỉ lệ là 0.2 cho điểm số thứ hạng cũ và 0.8 cho điểm số mới tính được dựa trên độ đo tương đồng giữa các ảnh. Các hệ số trên có được từ quá trình thực nghiệm. Giai đoạn 2: Xếp hạng lại cho tập các ảnh. Giai đoạn này được thực hiện ngoại tuyến. Tải các ảnh về và loại bỏ các ảnh trùng lặp rồi lưu vào cơ sở dữ liệu. Sử dụng Lire để trích xuất các đặc trưng hiển thị của ảnh, đánh chỉ mục cho ảnh dựa vào các đặc trưng này. Các đặc trưng hiển thị được sử dụng là: màu sắc và đặc trưng cạnh (edge). Tính độ tương đồng giữa các ảnh dựa trên các đặc trưng nói trên. Kết hợp độ đo tương đồng dựa trên đặc trưng văn bản và độ đo tương đồng dựa trên nội dung hiển thị với tỉ lệ: 0.3 cho độ đo dựa trên đặc trưng văn bản và 0.7 cho độ đo dựa trên nội dung hiển thị. Với hệ số tỉ lệ này sẽ cho kết quả xếp hạng tốt nhất. Thực hiện các tính toán tiếp theo như giai đoạn 1 đối với độ đo tương đồng tổng hợp. 4.5. Kết quả thử nghiệm và đánh giá Khóa luận sử dụng độ chính xác trung bình (Average Precision) [4] để đánh giá kết quả xếp hạng của hệ thống so với kết quả xếp hạng của hai máy tìm kiếm nguồn 55 Google và Yahoo. Khóa luận cũng so sánh kết quả giữa hai lần xếp hạng của cùng một truy vấn. Tôi thử nghiệm với tập 35 truy vấn và sau đó đánh giá độ chính xác cho 50 ảnh trả về đầu tiên. Giả sử ta có 5 đối tượng là: a, b, c, d, e Trong đó a, b, c là các đối tượng phù hợp và d, e là các đối tượng không phù hợp. Một xếp hạng của các đối tượng cần đánh giá là: c, a, d, b, e Độ chính xác trung bình được định nghĩa như sau: ܣܲ ൌ ∑ ܲ@ܭ ൈ ܫሺܭሻ௡௞ୀଵ ∑ ܫሺ݆ሻ௡௝ୀଵ Trong đó: n là số đối tượng được xét. ܲ@ܭ ൌ ெ௔௧௖௛@௄ ௄ (Match@K = số các đối tượng phù hợp ở K vị trí đầu tiên) I(K) = 1 nếu đối tượng ở vị trí K là phù hợp, ngược lại I(K) = 0 Ví dụ: P@1 = 1/1, P@2 = 2/2, P@3 = 2/3, P@4 = 3/4. Thì độ chính xác trung bình là: ܣܲ ൌ 1 1 ൈ 1 ൅ 2 2 ൈ 1 ൅ 3 4 ൈ 1 3 ൌ 0.92 Giá trị trung bình trên m xếp hạng (với bài toán tìm kiếm thì đó là giá trị trung bình của AP trên các truy vấn): ܯܣܲ ൌ ∑ ܣܲ௜௠௜ୀଵ ݉ Bảng thống kê độ chính xác của 50 ảnh đầu tiên của mỗi truy vấn trên các máy tìm kiếm cho thấy hệ thống có độ chính xác trung bình khá cao (MAP=81.2%). Đặc biệt là đối với các truy vấn về một vật thể có hình dạng, màu sắc xác định như “candle” (AP=100%), “guitar” (AP=90.1%), “iphone” (AP=93.0%)…. Ngoài ra, độ chính xác của hệ thống khi sử dụng thuật toán xếp hạng chỉ dựa trên đặc trưng văn bản 56 cũng khá cao (MAP=79.7%) trong khi đó MAP của Google là 76.1% và của Yahoo là 66.8%. Điều đó cho thấy rằng hệ thống hoạt động tốt cho cả truy vấn mới và cũ. Tuy nhiên, đối với các truy vấn mà đối tượng tìm kiếm không rõ ràng như truy vấn “cloud”, “wave” thì kết quả xếp hạng của hệ thống chưa thực sự tốt. Đối với “wave”, độ chính xác của hệ thống khi xếp hạng dựa trên nội dung hiển thị là 43.0% trong khi độ chính xác khi xếp hạng dựa trên nội dung văn bản là 60.7% và độ chính xác của Google là 55.5 %. Bảng 5. Độ chính xác trung bình trên 35 truy vấn Google Yahoo MS_Text MS_Content ball 53.8 24.0 71.8 76.0 beach 95.5 40.4 97.4 88.5 bicycle 71.5 68.3 86.0 88.8 bike 53.5 41.1 81.2 79.0 bird 70.0 60.1 66.8 82.8 bridge 91.3 85.5 81.7 91.8 cake 76.8 92.0 84.9 92.3 candle 89.2 84.0 94.9 100 car 92.6 76.9 91.1 94.2 cat 97.2 81.5 86.2 97.1 christmas tree 95.7 91.3 100 96.3 church 69.1 34.7 65.2 76.9 cloud 56.9 49.6 42.5 40.8 cloud gate 86.9 55.4 73.1 70.5 cup 33.1 51.4 39.4 52.0 drums 87.7 70.2 95.5 90.5 duck 70.4 72.8 79.0 82.8 feathers 56.0 57.3 65.0 63.7 guitar 76.2 73.0 80.2 90.1 iphone 95.4 96.6 96.3 93.0 kids 51.2 82.0 70.9 75.1 kitten 83.8 93.9 91.4 82.9 lake 93.1 65.5 95.8 87.7 leaves 84.3 80.1 82.6 95.0 lemon 70.9 38.7 79.4 79.5 monkey 86.2 83.1 89.2 95.6 railway 61.2 92.5 72.4 68.0 river 72.7 66.5 69.7 78.3 road 78.9 81.2 91.3 83.0 snow 87.6 91.7 86.8 80.3 sun 70.1 45.1 70.9 73.6 57 sunrise 85.2 17.6 91.1 78.6 train 92.5 86.5 78.1 85.6 tree 70.6 74.6 84.4 88.4 wave 55.5 34.1 60.7 43.0 MAP 76.1 66.8 79.7 81.2 Hình 16. Biểu đồ so sánh độ chính xác trung bình giữa các hệ thống Để đánh giá khả năng tìm kiếm và xếp hạng của hệ thống đối với các từ khóa tiếng Việt, tôi thử nghiệm với 5 truy vấn tiếng Việt và đo độ chính xác của 50 kết quả đầu tiên của mỗi truy vấn. Các truy vấn tiếng việt được chọn là: “Bác Hồ”, “quả táo”, “con ong”, “máy bay”, “hoa hồng”. 0% 20% 40% 60% 80% 100% Sun Guitar Bicycle Cat Car Leaves Google Yahoo MS_Text MS_Content 58 Hình 17. Biểu đồ độ chính xác mức K của một số truy vấn tiếng Việt Biểu đồ trên thể hiện độ chính xác mức K của một số truy vấn tiếng Việt khi được thực hiện trên hệ thống tìm kiếm ảnh lớp trên. Biểu đồ cho thấy hệ thống xếp hạng khá chính xác cho 20 ảnh đầu. Tuy độ chính xác trung bình cho 50 ảnh đầu tiên không thực sự tốt nhưng người dùng thường chỉ quan tâm 10 đến 20 kết quả đầu tiên. Do đó tập 20 ảnh đầu là quan trọng. Để đánh giá tốc độ thực thi của hệ thống, tôi đo thời gian xếp hạng của các truy vấn thử nghiệm. Thời gian xếp hạng trung bình cho mỗi truy vấn là 40 giây. Khoảng thời gian này bao gồm thời gian trích xuất các thành phần đặc trưng, tìm và xử lý các ảnh trùng lặp, tính ma trận tương đồng dựa trên nội dung hiển thị và nội dung văn bản, tính hạng cho các ảnh và ghi kết quả vào file. Tôi cũng đo thời gian phản hồi của hệ thống đối với các truy vấn mới. Thời gian này được tính từ lúc hệ thống nhận được câu truy vấn đến lúc trả lại kết quả cho người dùng. Thời gian hồi đáp trung bình cho mỗi truy vấn mới là 20 giây. Như vậy, có thể thấy rằng thời gian thực thi của hệ thống là trong mức cho phép đối với một máy tìm kiếm ảnh. 0% 20% 40% 60% 80% 100% P@5 P@10 P@20 P@30 P@40 P@50 Bác Hồ Quả táo Con ong Máy bay Hoa Hồng 59 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 60 Kết luận Với lượng dữ liệu ảnh đa dạng và phong phú trên Internet, nhu cầu về một hệ thống xếp hạng ảnh là rất cần thiết. Tuy những nghiên cứu về tìm kiếm và xếp hạng ảnh trên Web đã được quan tâm từ lâu, nhưng lĩnh vực này vẫn còn nhiều vấn đề cần phải giải quyết. Nắm bắt được nhu cầu đó, khóa luận đã tíến hành nghiên cứu một thuật toán xếp hạng ảnh dựa trên các văn bản đi kèm ảnh và chính nội dung hiển thị của ảnh và tiến hành áp dụng thử nghiệm trên một mô hình máy tìm kiếm ảnh lớp trên. Các kết quả chính đạt được ‐ Tìm hiểu các thuật toán xếp hạng trang Web và các thuật toán xếp hạng ảnh điển hình. Từ đó đề xuất áp dụng thuật toán VisualRank cho cả đặc trưng văn bản và đặc trưng hiển thị của ảnh trong xếp hạng. ‐ Đư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 đã đề xuất. Mô hình máy tìm kiếm này quan tâm đến trạng thái câu hỏi người dùng và hỗ trợ các truy vấn tiếng Việt. Do đó, những nghiên cứu này là rất hữu ích cho người dùng Việt Nam. ‐ Tiến hành thử nghiệm mô hình với tập 35 câu truy vấn được trích rút từ các thẻ phổ biến trên Flickr. Kết quả của mô hình là khả quan đối với cả hai phương pháp xếp hạng ảnh được sử dụng. Độ chính xác của phương pháp xếp hạng chỉ dựa trên nội dung văn bản là 79.7% và độ chính xác của phương pháp xếp hạng dựa trên cả nội dung hiển thị và nội dung văn bản là 81.2%, tốt hơn so với độ chính xác của Google (76.1%) và của Yahoo (66.8%). Khóa luận cũng đã thử nghiệm với một số câu truy vấn tiếng Việt. Kết quả thử nghiệm cho thấy mô hình có thể xếp hạng khá tốt cho tập 20 ảnh đầu tiên. Từ những kết quả ban đầu đó cho thấy tính đúng đắn của mô hình. Một số vấn đề cần tiếp tục giải quyết ‐ Tuy mô hình đã bước đầu đạt được một số kết quả khả quan trên tập dữ liệu thử nghiệm, nhưng đối với các truy vấn về sự kiện hoặc về các đối tượng không cụ thể thì thuật toán xếp hạng chưa giải quyết được tốt. ‐ Hơn nữa, vấn đề thời gian xếp hạng lại và không gian lưu trữ ảnh cũng cần được quan tâm khi cơ sở dữ liệu của hệ thống được mở rộng. Cần có một giải pháp thích hợp để vừa có thể lưu trữ được dữ liệu cho càng nhiều câu truy 61 vấn càng tốt, vừa có thể thực hiện xếp hạng lại cho tất cả các câu truy vấn này. ‐ Một vấn đề khác là đối với các truy vấn tên riêng (tên người, tên địa danh,…) bằng tiếng Việt thì việc dịch các truy vấn này sang tiếng anh sẽ làm cho kết quả tìm kiếm không còn đúng nữa. Hơn nữa, nếu kết quả dịch của từ điển không chính xác thì sẽ dẫn đến nhiều sai lệch trong việc tìm kiếm. Do đó, nếu tìm kiếm trực tiếp bằng tiếng Việt thì có thể sẽ có những kết quả tốt hơn. Hướng nghiên cứu tiếp theo Trong thời gian tới, ngoài việc tiếp tục giải quyết các vấn đề còn tồn tại, tôi định hướng một số nghiên cứu tiếp theo: ‐ Nghiên cứu thêm về các thuật toán trích xuất các thành phần đặc trưng ảnh để nâng cao hiệu quả trong việc tính độ tương đồng giữa các ảnh. ‐ Nghiên cứu các phương pháp xử lý tiếng Việt để tìm kiếm ảnh trực tiếp bằng tiếng Việt. ‐ Sử dụng phản hồi của người dùng để nâng cao chất lượng hệ thống. 62 Tài liệu tham khảo Tiếng Việt [1] Đỗ Thị Diệu Ngọc, Nguyễn Hoài Nam, Nguyễn Thu Trang, Nguyễn Yến Ngọc (2004). Giải pháp tính hạng trang Modified Adaptive PageRank trong máy tìm kiếm. Chuyên san “Các công trình nghiên cứu về CNTT và Truyền thông”, Tạp chí BCVT, 14: 65-71, 4-2005. [2] Nguyễn Hoài Nam (2004). Thuật toán tính hạng trang và xây dựng mô đun thử nghiệm. Khóa luận đại học, Trường ĐHKHTN, ĐHQGHN. [3] Nguyễn Thu Trang (2006). Link spam với đồ thị Web và hạng trang Web. Khóa luận đại học, Trường ĐHCN, ĐHQGHN. [4] Nguyễn Thu Trang (2009). Học xếp hạng trong tịnh hạng đối tượng và phân cụm tài liệu. Luận văn Thạc sỹ, Trường ĐHCN, ĐHQGHN. [5] Nguyễn Hoàng Trung (2009). Xây dựng search engine. Luận văn Thạc sỹ, Trường ĐHCN, ĐHQGHN. Tiếng Anh [6] Mehmet S. Aktas, Mehmet A. Nacar, Filippo Menczer (2004). Personalizing PageRank based on domain profiles. WebKDD 2004: 83-90. [7] Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas (2005). Link analysis ranking: algorithms, theory, and experiments. ACM Trans. Inter. Tech., 5(1):231-297. [8] Amy N.Langville and Carl D.Meyer (2005). Deeper inside pagerank. Internet Mathematics Journal, 1(3):335-380. [9] Amy N.Langville, Carl D. Meyer (2004). A Reodering for the PageRank problem. SIAM J. Sci. Comput., 27(6): 2112-2120. [10] Anselm Spoerri (2004). RankSpiral: Toward Enhancing Search Results Visualizations. IEEE Symposium on Information Visualization: 215.18. [11] Benitez A.B., Beigi M., Shih-Fu Chang (1998). Using relevance feedback in content-based image metasearch. IEEE Internet Computing, 2(4): 59-69. 63 [12] B. Uygar Oztekin, George Karypis, Vipin Kumar (2002). Expert agreement and content based reranking in a meta search environment using Mearf. WWW 2002: 333-344. [13] Baoning Wu and Brian D. Davison (2005). Identifying link farm spam pages. WWW (Special interest tracks and posters) 2005: 820-829. [14] Bo Luo, Xianogang Wang, and Xiaoou Tang (2003). A World Wide Web Based Image Search Engine Using Text and Image Content Features. IS&T/SPIE Electronic Imaging 2003, Internet Imaging IV, 5018: 123-130. [15] Chik Ching Yiu, Ip Che Yin (2002). Image Ranking Schemes Using Link- Structure Analysis Algorithm. WWW2002, 114/ [16] Cam-Tu Nguyen, Xuan-Hieu Phan, Susumu Horiguchi, Thu-Trang Nguyen, Quang-Thuy Ha (2009). Web Search Clustering and Labeling with Hidden Topics. ACM Trans. Asian Lang. Inf. Process. 8(3): 1-40. [17] Eva Horster, Malcolm Slaney, Marc’ Aurelio Ranzato, Kilian Weinberger (2009). Unsupervised image ranking. LS-MMRM '09: 81-88. [18] Eric J. Glover (2001). Using Extra-Topical User Preferences To Improve Web- Based Metasearch. PhD Thesis, The University of Michigan. [19] G. Park, Y. Baek, and H. Lee (2003). Majority based ranking approach in web image retrieval. CIVR 2003: 111-120. [20] Hsinchun Chen, Haiyan Fan, Michael Chau, and Daniel Zeng (2001). MetaSpider: Meta-Searching and Categorization on the Web. JASIST, 52(13):1134–1147. [21] Hervé Jégou, Matthijs Douze, Cordelia Schmid (2010). Product quantization for nearest neighbor search. 2010 IEEE TPAMI, people/jegou/publications.php [22] Herve Jegou, Matthijs Douze, Cordelia Schmid (2008). Recent Advances in Large Scale Image Search. ETVC 2008: 305-326. [23] Jon M. Kleinberg (1999). Authoritative Sources in a Hyperlinked Environment. J.ACM, 46(5): 604-632. 64 [24] Kamarul Hawari Ghazali (2007). Feature Extraction technique using SIFT keypoints descriptors. The International Conference on Electrical and Engineering and Informatics Institut technology, Bandung, Indonesia, June 17-19, 2007. [25] Lowe David (2004). Distinctive image features from scale-invariant keypoints. Inter. J. Computer Vision 2004, 60(2):91–110. [26] Liangliang Cao, Andrey Del Pozo, Xin Jin, Jiebo Luo, Jiawei Han and Thomas S. Huang (2010). RankCompete: simultaneous ranking and clustering of web photos. WWW 2010: 1071-1072. [27] L.S. Kennedy and M. Naaman (2008). Generating diverse and representative image search results for landmarks. ACM Multimedia 2008: 349-358. [28] Manoj M., Elizabeth Jacob (2008). Information retrieval on Internet using meta- search engines: A review. J. Scientific & Industrial Research, 67(10):739-746. [29] Mitsuru Ambai, Yuichi Yoshida (2009). Multiclass VisualRank: Image Ranking Method in Clustered Subsets Based on Visual Features. SIGIR 2009: 732-733. [30] Page, L., Brin, S., Motwani, R. and Winograd, T. (1998). The PageRank citation ranking: bringing order to the Web. Technical report, Stanford University. [31] Ritendra Datta, Dhiraj Joshi, Jia Li, and James Z. Wang (2008). Image Retrieval: Ideas, Influences, and Trends of the New Age. ACM Computing Surveys, 40(2), April 2008. [32] Sepandar Kamvar, Taher Haveliwala, and Gene Golub (2003). Adaptive Methods for the Computation of PageRank. Technical report, Stanford University. [33] Shiliang Zhang, Qi Tian, Gang Hua, Qingming Huang, Shipeng Li (2009). Descriptive Visual Words and Visual Phrases for Image Applications. ACM Multimedia 2009: 75-8484. [34] Shuhui Wang, Quingming Huang, Shuqiang Jiang, Lei Qin, Qi Tian (2009). Visual ContextRank for web image re-ranking. The First ACM workshop on Large-scale multimedia retrieval and mining: 121-128. [35] Taher H. Haveliwala (2002). Topic-sensitive PageRank. Technical report, Stanford University. May 7–11, 2002, Honolulu, Hawaii, USA. 65 [36] T.L. Berg, A.C. Berg (2009). Finding iconic images. The 2nd Internet Vision Workshop at Conference on Computer Vision and Pattern Recognition (CVPR):1- 8. [37] Viswanathan, M., Chang, C.-K., Moon, J.-H. Patlolla, A., (2009). Goggle (or Gist on the Google Phone): A Content-Based Image Retrieval System for the gPhone. CSCI-546 Project. Google.pdf [38] Xinmei Tian, Dacheng Tao (2010). Active Reranking for Web Image Search. IEEE Transactions on Image Processing, 19(3): 805-820 (2010). [39] Yushi Jing, Shumeet Baluja (2008). Pagerank for product image search, WWW08:307-316. [40] Yushi Jing, Shumeet Baluja (2008). VisualRank: Applying PageRank to Large- Scale Image Search. IEEE Trans. Pattern Anal. Mach. Intell., 30(11): 1877-1890. [41] Z. Gyongyi and H. Garcia-Molina (2005). Web Spam Taxonomy. AIRWeb 2005: 39-47. [42] Z. Gyongyi, H. Garcia-Molina, and J. Pendersen (2004). Combating Web Spam with TrustRank. VLDB 2004: 576-587.