Kết hợp kỹ thuật gom nhóm và phản hồi tương đồng trong tìm kiếm ảnh

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

17
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tìm kiếm ảnh là lĩnh vực đang nhận được rất nhiều sự quan tâm của cộng đồng khoa học máy tính, xu hướng nghiên cứu hiện nay là kết hợp các thuật toán và các phương pháp trích đặc trưng dữ liệu để làm tăng hiệu quả tìm kiếm. Nghiên cứu đề xuất sử dụng kết hợp kỹ thuật gom nhóm để lấy phản hồi tương đồng, với đặc trưng ảnh là đặc trưng cục bộ và đặc trưng văn bản.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kết hợp kỹ thuật gom nhóm và phản hồi tương đồng trong tìm kiếm ảnh

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019 DOI: 10.15625/vap.2019.00029 KẾT HỢP KỸ THUẬT GOM NHÓM VÀ PHẢN HỒI TƯƠNG ĐỒNG TRONG TÌM KIẾM ẢNH Nguyễn Tí Hon1, Hà Thị Phƣơng Anh2, Phạm Thế Phi3 1 Khoa Phát triển Nông thôn, Trƣờng Đại học Cần Thơ 2 Khoa Công nghệ thông tin, Trƣờng Đại học Bạc Liêu 3 Khoa Công nghệ thông tin và Truyền thông, Trƣờng Đại học Cần Thơ nthon@ctu.edu.vn, htpanh52@gmail.com, ptphi@cit.ctu.edu.vn TÓM TẮT: Tìm kiếm ảnh là lĩnh vực đang nhận được rất nhiều sự quan tâm của cộng đồng khoa học máy tính, xu hướng nghiên cứu hiện nay là kết hợp các thuật toán và các phương pháp trích đặc trưng dữ liệu để làm tăng hiệu quả tìm kiếm. Một trong những phương pháp được sử dụng hiệu quả đó là kỹ thuật phản hồi tương đồng để con người xác định một ảnh kết quả là phù hợp hoặc không phù hợp với ảnh truy vấn thông qua đó điều chỉnh truy vấn gốc sao cho gần hơn các kết quả cần tìm. Bên cạnh đó, người ta còn sử dụng kỹ thuật gom nhóm để làm tăng hiệu quả lấy phản hồi, thay vì mỗi lần phản hồi, người dùng chỉ chọn một ảnh thì với phương pháp này, người dùng sẽ chọn một nhóm ảnh, tất cả ảnh trong nhóm sẽ được coi là tương đồng hoặc không tương đồng. Trong tìm kiếm ảnh, đặc trưng cục bộ thường xuyên được sử dụng bởi vì đặc trưng này phù hợp để xác định các đối tượng bên trong ảnh, đồng thời không bị ảnh hưởng bởi kích thước, góc quay và độ sáng của hình ảnh cũng như các đối tượng trong ảnh. Ngoài ra, ảnh trên internet thường được kèm theo những ghi chú hoặc mô tả ngắn (gọi chung là mô tả), có giá trị rất lớn trong việc thể hiện nội dung bên trong bức ảnh. Sử dụng đồng thời đặc trưng ảnh và đặc trưng văn bản là một hướng tiếp cận mới và đã được chứng minh hiệu quả trong các nghiên cứu về máy học. Từ thực tế đó, nghiên cứu đề xuất sử dụng kết hợp kỹ thuật gom nhóm để lấy phản hồi tương đồng, với đặc trưng ảnh là đặc trưng cục bộ và đặc trưng văn bản. Nghiên cứu được cài đặt và đánh giá trên tập dữ liệu “Di sản văn hoá phi vật thể khu vực Đồng bằng sông Cửu Long” được thu thập tự động từ internet bằng công cụ Web crawler, kết quả thực nghiệm cho thấy phương pháp được đề xuất đã mang lại hiệu quả tốt trong việc nâng cao hiệu quả phản hồi cũng như kết quả tìm kiếm. Từ khóa: Tìm kiếm ảnh, phân loại ảnh, gom cụm, phản hồi tương đồng, kết hợp đặc trưng. I. GIỚI THIỆU Truy hồi ảnh là một trong những lĩnh vực quan trọng của ngành khoa học máy tính đã đƣợc chú trọng từ thập niên 90 của thế kỷ XX [7, 14]. Truy hồi ảnh không chỉ cần thiết cho các ứng dụng liên quan đến an ninh quốc phòng, y tế, khoa học và giáo dục mà còn cần thiết cho nhu cầu giải trí hàng ngày của con ngƣời [10]. Hiện tại có rất nhiều hệ thống truy hồi ảnh đƣợc phát triển và sử dụng, các phƣơng thức thực hiện cũng hết sức đa dạng nhƣ nhập từ khoá, sử dụng hình ảnh để tìm kiếm. Hầu hết kết quả trả về là một danh sách các hình ảnh đƣợc sắp xếp dựa trên một tiêu chuẩn nhất định, chẳng hạn nhƣ hình ảnh giống với hình ảnh cần tìm nhất đƣợc xếp trƣớc tiên. Vấn đề đặt ra là tiêu chuẩn để sắp xếp kết quả trả về cho ngƣời dùng, đôi khi hình ảnh ngƣời dùng thật sự cần không nằm ở đầu danh sách kết quả, ngƣời dùng có thể phải xem đến trang kết quả thứ hai hoặc thứ ba mới thấy hình ảnh cần thiết. Trong khi đó tâm lý chung của ngƣời dùng khi tìm kiếm là thƣờng chỉ xem khoảng 10 kết quả đầu, ít khi xem đến trang kết quả thứ hai. Hƣớng giải quyết vấn đề này rất đa dạng [1], trong đó nổi bật là kỹ thuật lấy phản hồi tƣơng đồng từ phía ngƣời dùng và mở rộng truy vấn. Có rất nhiều phƣơng pháp để tăng hiệu quả lấy phản hồi tƣơng đồng, tiêu biểu là kỹ thuật gom nhóm kết quả trả về trƣớc khi hiển thị cho ngƣời dùng phản hồi [8, 9, 12]. Bên cạnh đó, trong bài toán phân loại ảnh (có liên quan mật thiết với bài toán tìm kiếm ảnh vì cùng dựa trên cơ sở đặc trƣng ảnh) việc kết hợp các loại đặc trƣng để tăng hiệu quả cũng đƣợc chú trọng, bởi vì hình ảnh trên internet thƣờng kèm theo các văn bản ngắn mô tả nội dung bên trong hình ảnh [10, 17]. Nội dung của nghiên cứu là tập trung vào sử dụng kỹ thuật gom nhóm hình ảnh để lấy phản hồi tƣơng đồng từ phía ngƣời dùng. Đồng thời sử dụng hai loại đặc trƣng của hình ảnh là: đặc trƣng ảnh (kiểu dáng các đối tƣợng trong ảnh) và đặc trƣng văn bản (mô tả đi kèm theo ảnh). Hƣớng tới làm tăng hiệu quả phản hồi tƣơng đồng và kết quả tìm kiếm, góp phần khẳng định giá trị đặc trƣng văn bản trên tập dữ liệu thực nghiệm. II. CÁC NGHIÊN CỨU LIÊN QUAN Phản hồi tƣơng đồng là phƣơng pháp dựa trên sự xác nhận của ngƣời dùng về một hoặc nhiều kết quả tìm kiếm, từ đó điều chỉnh lại truy vấn ban đầu (truy vấn gốc) để nâng cao hiệu quả tìm kiếm. Trong nghiên cứu “Evaluating Document Clustering for Interactive Information Retrieval” [12] tác giả Anton Leuski đã đƣa sử dụng phƣơng pháp gom nhóm tài liệu để lấy phản hồi tƣơng đồng từ phía ngƣời dùng. Đồng thời tác giả cũng khẳng định việc lấy phản hồi trên nhóm và mở rộng truy vấn mang lại hiệu quả cao hơn so với phƣơng pháp tổ chức kết quả bằng danh sách tài liệu đã đƣợc sắp xếp. Ở một khía cạnh khác, trong nghiên cứu “Cluster-Based Retrieval of Images by Unsupervised Learning” [9], nhóm tác giả Yixin Chen, James Z. Wang và Robert Krovetz sử dụng kỹ thuật gom nhóm (Hierarchical Clustering) để
226 KẾT HỢP KỸ THUẬT GOM NHÓM VÀ PHẢN HỒI TƢƠNG ĐỒNG TRONG TÌM KIẾM ẢNH gom nhóm ảnh và lấy phản hồi tƣơng đồng trên nhóm sau đó mở rộng truy vấn dựa trên kết quả phản hồi. Hƣớng tiếp cận này giúp tăng hiệu quả phản hồi và cải thiện kết quả tìm kiếm. Song song đó, nhóm tác giả Gang Wang, Derek Hoiem và David Forsyth đã đề xuất giải pháp phân loại ảnh dựa trên sự kết hợp giữa đặc trƣng ảnh (Visual Features: SIFT, GIST, COLOR, GRADIENT) với đặc trƣng văn bản (Textual Features) trong nghiên cứu “Building Text Features For Object Image Classification”. Theo tác giả, ảnh trên internet thƣờng đi kèm với một vài mô tả ngắn (tag, group name,...), những mô tả này có giá trị rất lớn trong việc nói lên nội dung của ảnh, đồng thời chứng minh việc kết hợp các đặc trƣng ảnh và đặc trƣng văn bản cải thiện hiệu quả phân loại ảnh. Đặc biệt, trong nghiên cứu “Semantic Combination of Textual and Visual Information in Multimedia Retrieval”, nhóm nghiên cứu đến từ Trung tâm Nghiên cứu của Xerox, đứng đầu là Stéphane Clinchant đã so sánh các phƣơng pháp kết hợp đặc trƣng hình ảnh và đặc trƣng văn bản giúp nâng cao độ tƣơng đồng trong kết quả tìm kiếm ảnh. Nghiên cứu khẳng định phƣơng pháp kết hợp muộn (Late Fusion) mang đến hiệu quả rất tốt khi kết hợp giữa đặc trƣng ảnh và đặc trƣng văn bản. Nghiên cứu “Kết hợp kỹ thuật gom nhóm và phản hồi tƣơng đồng trong tìm kiếm ảnh” tập trung vào gom nhóm kết quả tìm đƣợc hƣớng tới mục tiêu nâng cao hiệu quả phản hồi tƣơng đồng, sử dụng kết hợp đặc trƣng ảnh và đặc trƣng văn bản để nâng cao độ chính xác, đồng thời cũng khảo sát các giá trị khác nhau của tham số kết hợp độ tƣơng đồng giữa hai loại đặc trƣng đối với tập dữ liệu ảnh thực nghiệm “Di sản văn hoá phi vật thể khu vực Đồng bằng sông Cửu Long”. III. ĐẶC TRƢNG A. Đặc trưng ảnh 1. Các loại đặc trƣng ảnh Về cơ bản để so sánh hai bức ảnh có giống nhau hay không ta có hai phƣơng pháp chính là so sánh từng pixel hoặc sử dụng các loại đặc trƣng nhƣ: màu sắc, hình dáng các đối tƣợng, khung cảnh, bề mặt hình ảnh. Trong đó phƣơng pháp so sánh từng pixel đòi hỏi tiêu tốn nhiều tài nguyên máy tính và chịu ảnh hƣởng bởi sự thay đổi kích thƣớc, màu sắc, độ sáng tối của ảnh, độ xoay của vật thể trong ảnh nên ít đƣợc sử dụng hơn phƣơng pháp sử dụng các đặc trƣng ảnh. Các nhà khoa học máy tính đã đƣa ra rất nhiều phƣơng pháp trích đặc trƣng ảnh trong đó có ba nhóm chính là: đặc trƣng về màu sắc - lƣợc đồ màu (colour histogram), đặc trƣng về hình dáng vật thể trong ảnh - đƣờng biên của vật thể (edge), góc trên vật thể (corner) và đặc trƣng bề mặt hình ảnh (texture). Đối với loại đặc trƣng về hình dáng vật thể trong ảnh lại có hai nhóm chính là đặc trƣng cục bộ và đặc trƣng toàn cục. Trong đó các đặc trƣng cục bộ chú trọng tới các chi tiết góc, một phần cạnh liền kề góc tạo nên dáng của vật thể trong ảnh nhƣ đặc trƣng SIFT; đặc trƣng toàn cục chú trọng đến các đƣờng biên và khung đƣờng biên trên toàn bộ ảnh (nói lên thần thái ảnh) nhƣ đặc trƣng GIST. Mỗi đặc trƣng nhƣ vậy đƣợc mô tả bởi một vector đặc trƣng, ví dụ mỗi đặc trƣng SIFT đƣợc mô tả bởi một vector 128 chiều [13]. 2. Đặc trƣng SIFT Đặc trƣng SIFT (The Scale Invariant Feature Transform) thuộc loại đặc trƣng cục bộ do David G. Lowe đề xuất trong nghiên cứu “Distinctive Image Features from Scale - Invariant Keypoints” năm 2004. Điểm nổi bật của đặc trƣng SIFT là bất biến (không bị ảnh hƣởng) đối với kích thƣớc ảnh, phép quay ảnh và độ chiếu sáng. Mỗi điểm nổi bật đƣợc mô tả bằng cửa sổ 4x4, mỗi khung gồm 8 vector, nhƣ vậy mỗi đặc trƣng SIFT đƣợc mô tả bởi một vector 128 chiều. Hình 1 minh hoạ cửa sổ 2x2 theo nhƣ bài báo SIFT (Distinctive Image Features from Scale-Invariant Keypoints). Hình 1. Cửa số 2x2 mô tả đặc trƣng SIFT
Nguyễn Tí Hon, Hà Thị Phƣơng Anh, Phạm Thế Phi 227 (Nguồn: Bài báo Distinctive Image Features from Scale-Invariant Keypoints) B. Đặc trưng văn bản 1. Đặc điểm của văn bản Tiếng Việt Văn bản Tiếng Việt ngoài những từ đơn (có một tiếng) ra còn có những từ ghép (có hai hoặc ba tiếng). Nhƣ vậy để xác định đƣợc một từ không chỉ tách các từ theo khoảng trắng mà còn phải dựa vào ngữ nghĩa của từ đó trong văn bản, bên cạnh đó trong tìm kiếm thông tin các từ ghép có ý nghĩa rất lớn [1], do đó nghiên cứu sử dụng phƣơng pháp tách từ dựa trên ngữ nghĩa. Để tách từ theo ngữ nghĩa trong văn bản Tiếng Việt ngƣời ta sử dụng các phƣơng pháp chủ yếu là dựa vào từ điển và phƣơng pháp thống kê. Nghiên cứu sử dụng phƣơng pháp thống kê đƣợc đề xuất bởi tác giả Phạm Nguyên Khang và các đồng sự trong nghiên cứu “Sự ảnh hƣởng của phƣơng pháp tách từ trong bài toán phân lớp văn bản Tiếng Việt”. Theo tác giả, với một đoạn văn bản , mô hình dùng để tính xác suất ( ) đƣợc xác định theo công thức (1): ( ) ( ) ( | ) ( | ) ( | ) ∏ ( | ) (1) Ứng dụng giả thuyết của Markov rằng dự đoán kế tiếp chỉ phụ thuộc vào lịch sử gần đây thay vì toàn bộ lịch sử, chúng ta có thể biểu diễn công thức (1) bằng công thức ( ) ∏ ( | ) (2) với N chỉ ra lịch sử gần nhất hay cụ thể hơn là số lƣợng từ gần nhất đứng trƣớc từ thứ k hiện tại. Mô hình này thƣờng đƣợc gọi là mô hình n-grams. Việc ƣớc lƣợng ( | ) hay ( | ) đƣợc thực hiện theo công thức (3): ( ) ( | ) (3) ( ) với ( ) là số lần xuất hiện của các dãy từ trong tập dữ liệu huấn luyện; ( ) là số lần xuất hiện của các từ trong tập dữ liệu huấn luyện. 2. Mô hình túi từ Trong bài toán phân loại văn bản cũng nhƣ tìm kiếm văn bản, mô hình túi từ (Bag of Words - BoW) đƣợc sử dụng với mục đích chuyển đổi văn bản về dạng vector, qua đó thực hiện tính độ tƣơng đồng (độ gần nhau) giữa các vector để suy ra độ tƣơng đồng giữa các văn bản. Trong mô hình túi từ, tập hợp tất cả các từ trong tập dữ liệu tạo thành từ điển, với mỗi tài liệu ngƣời ta tạo thành một vector đặc trƣng cho tài liệu đó, nhƣ vậy vector đặc trƣng này có số chiều bằng với số từ trong từ điển, giá trị thành phần của vector là số lần xuất hiện (tần số) của từ trong tài liệu và vị trí thành phần của vector là vị trí của từ trong từ điển. Thông qua việc chuyển đổi văn bản thành vector, những văn bản càng có nhiều từ giống nhau (càng giống nhau) thì vector của chúng càng gần nhau, nói cách khác độ tƣơng đồng giữa các vector của chúng càng lớn. Mô hình này cũng có thể áp dụng cho đặc trƣng ảnh. C. Kết hợp đặc trưng Khi sử dụng hai loại đặc trƣng (đặc trƣng ảnh và đặc trƣng văn bản), ngƣời ta cần phải kết hợp các độ tƣơng đồng tính đƣợc để đƣa ra kết quả là độ tƣơng đồng cuối cùng. Hai phƣơng pháp cơ bản nhất là kết hợp sớm và kết hợp muộn [10, 18]. Kết hợp sớm là phƣơng pháp ghép trực tiếp vector đặc trƣng ảnh sau vector đặc trƣng văn bản (hoặc ngƣợc lại) tạo thành một vector đặc trƣng mới. Mặc dù phƣơng pháp này kết hợp đƣợc sự đóng góp của hai loại đặc trƣng nhƣng về mặt dữ liệu đặc trƣng ảnh và đặc trƣng văn bản là không giống nhau nên sẽ ảnh hƣởng đến kết quả bài toán. Kết hợp muộn là phƣơng pháp tính toán độ tƣơng đồng trên hai loại đặc trƣng riêng biệt nhau, sau đó tổng hợp hai kết quả này theo tham số kết hợp độ tƣơng đồng ( ), giả sử là độ tƣơng đồng theo đặc trƣng ảnh, là độ tƣơng đồng theo đặc trƣng văn bản thì độ tƣơng đồng tổng hợp đƣợc xác định theo công thức (4): ( ) (4)
228 KẾT HỢP KỸ THUẬT GOM NHÓM VÀ PHẢN HỒI TƢƠNG ĐỒNG TRONG TÌM KIẾM ẢNH IV. PHẢN HỒI TƢƠNG ĐỒNG VÀ MỞ RỘNG TRUY VẤN Phản hồi tƣơng đồng là phƣơng pháp làm tăng kết quả tìm kiếm dựa trên cơ sở phản hồi từ phía ngƣời dùng đối với kết quả tìm kiếm ban đầu. Để lấy phản hồi ngƣời ta ghi nhận phản hồi trực tiếp bằng cách để ngƣời dùng chọn kết quả tƣơng đồng và kết quả không tƣơng đồng. Hoặc lấy phản hồi gián tiếp bằng cách “âm thầm” ghi nhận các kết quả đƣợc ngƣời dùng chọn (click) để xem tiếp và coi đó là kết quả tƣơng đồng. Do phản hồi gián tiếp đòi hỏi thời gian và lƣợng ngƣời dùng lớn nên nghiên cứu sử dụng phƣơng pháp lấy phản hồi trực tiếp. Kỹ thuật mở rộng truy vấn là sự kết hợp không thể thiếu của kỹ thuật phản hồi tƣơng đồng, dựa vào kết quả phản hồi tƣơng đồng và truy vấn gốc, kỹ thuật này sinh ra một truy vấn mới có tính chất “gần” hơn với tài liệu/hình ảnh tƣơng đồng và “xa” hơn những tài liệu/hình ảnh không tƣơng đồng. Từ đó cải thiện kết quả tìm kiếm của hệ thống bằng cách trả về kết quả của việc thực thi lại truy vấn mở rộng. Phƣơng pháp “Rocchio query expansion” có nhiều ƣu thế trong mở rộng truy vấn đối với mô hình không gian vector (tính độ tƣơng đồng trên vector đặc trƣng). Công thức (5) xác định truy vấn mở rộng bằng phƣơng pháp này. ⃗⃗⃗⃗⃗ ⃗⃗⃗⃗ ∑⃗ ∑ ⃗ (5) | | | | ⃗⃗⃗ ⃗⃗⃗ Trong đó: ⃗⃗⃗⃗⃗ : vector truy vấn mở rộng, ⃗⃗⃗⃗ : vector truy vấn gốc, : tập vector đặc trƣng của kết quả tƣơng đồng, : tập vector đặc trƣng của kết quả không tƣơng đồng, ⃗ : vector đặc trƣng thứ và và : trọng số tin cậy. V. CÀI ĐẶT THỰC NGHIỆM Nghiên cứu sử dụng công cụ crawler để tải ảnh kèm văn bản từ hệ thống Google Image, tập ảnh nhận về đƣợc sử dụng làm tập dữ liệu ảnh. Sau đó chia tập dữ liệu ảnh thành tập huấn luyện, tập điều chỉnh tham số và tập đánh giá; trích và lƣu trữ đặc trƣng của tập huấn luyện. Với mỗi ảnh trong tập đánh giá (gọi là ảnh truy vấn), trích đặc trƣng, tính độ tƣơng đồng của ảnh truy vấn với từng ảnh trong tập dữ liệu và sắp xếp (rank) theo độ tƣơng đồng giảm dần. Lấy k ảnh có độ tƣơng đồng cao nhất trong danh sách để gom nhóm nhƣ mô tả ở hình 2. Hình 2. Quy trình tổng quát của nghiên cứu Sau khi gom nhóm, các nhóm đƣợc sắp xếp theo độ tƣơng đồng giảm dần so với ảnh tìm kiếm, ảnh có độ tƣơng đồng cao nhất trong nhóm đƣợc dùng làm ảnh đại diện nhóm [12]. Ngƣời dùng duyệt qua các nhóm và đánh giá là nhóm tƣơng đồng hay không tƣơng đồng; hoặc đánh giá một lƣợt nhiều nhóm dựa trên ảnh đại diện nhƣ mô tả ở hình 3. Từ kết quả phản hồi tƣơng đồng, thực hiện mở rộng truy vấn và thực thi lại truy vấn đã mở rộng. Trong đó đặc trƣng đƣợc sử dụng bao gồm đặc trƣng ảnh (SIFT) và đặc trƣng văn bản. Độ tƣơng đồng của hai loại đặc trƣng trên đƣợc tính theo giá trị cosin và kết hợp bằng phƣơng pháp kết hợp muộn. Gom nhóm k ảnh bằng kỹ thuật Hierarchical Agglomerative Clustering (HAC) bởi vì kỹ thuật này cho phép giới hạn số nhóm (clusters) tối đa, nếu bản chất dữ liệu trong quá trình gom nhóm cho ra số lƣợng clusters ít hơn giới hạn thì số clusters kết quả sẽ ít hơn giới hạn; điều này làm nổi bật bản chất dữ liệu; quá trình gom nhóm ảnh để lấy phản hồi chỉ thực hiện trên đặc trƣng ảnh bởi vì số chiều trong vector đặc trƣng văn bản rất lớn (2397 chiều) dẫn đến thời gian gom nhóm không đáp ứng đƣợc nhu cầu lấy phản hồi theo phƣơng pháp thủ công. Đánh giá kết quả thực nghiệm theo độ đo Average Precision (AP).
Nguyễn Tí Hon, Hà Thị Phƣơng Anh, Phạm Thế Phi 229 VI. KẾT QUẢ THỰC NGHIỆM A. Tập dữ liệu thực nghiệm Tập dữ liệu “Di sản văn hoá phi vật thể ở khu vực Đồng bằng Sông Cửu Long” đƣợc sƣu tập bao gồm hình của 17 Di sản đƣợc chia thành 17 lớp, sau quá trình tiền xử lý tập dữ liệu đƣợc chia thành 3 tập nhỏ nhƣ trình bày ở bảng 1. Trong tập dữ liệu, số lƣợng ảnh giữa các lớp không đồng đều nhau, các lớp 1, 7, 17 có số lƣợng ảnh vƣợt trội hẳn so với các lớp còn lại, bên cạnh đó một số lớp có số lƣợng ảnh rất ít nhƣ lớp 8, 12, 13 và 16. Bảng 1. Tập dữ liệu đánh giá STT Tập dữ liệu Số ảnh 1 Huấn luyện 8979 2 Điều chỉnh tham số 602 3 Kiểm thử 547 Chú thích: - T1…T32: tab hiển thị ảnh đại diện. - U (Unset): nhóm chƣa/không chọn phản hồi. - R (Relevant): nhóm đƣợc chọn là tƣơng đồng. - IR (Irrelevant): nhóm đƣợc chọn là không tƣơng đồng. - More: hiển thị tất cả ảnh trong nhóm tƣơng ứng. Hình 3. Giao diện phản hồi tƣơng đồng B. Môi trường thực nghiệm Cấu hình máy tính chạy thực nghiệm: CPU Intel(R) Core(TM) i3-6100, 3.70 GHz; Ram 16 GB, 2133 MHz. Hệ điều hành Microsoft Windows 10 Version 1703. Các phiên bản phần mềm sử dụng: Python 2.7.13; Numpy 1.12.1; Scipy 0.19.0; Scikit-learn 0.18.2; Nltk 3.2.3; Pillow 4.1.1; OpenCV 2.4.13. Tham số kết hợp độ tƣơng đồng đặc trƣng ảnh và đặc trƣng văn bản [10]. Quá trình thực nghiệm ghi nhận các thông tin: lớp dữ liệu của ảnh truy vấn, thứ tự lƣợt rank, giá trị AP, số click phản hồi, số ảnh thật sự trong tập tƣơng đồng và tập không tƣơng đồng, đƣờng dẫn ảnh kết quả đã sắp xếp theo độ tƣơng đồng giảm dần so với ảnh truy vấn. Mỗi ảnh trong tập kiểm thử sẽ đƣợc rank 7 lần, trong đó lần rank thứ hai trở đi dựa trên kết quả phản hồi tƣơng đồng từ lần rank trƣớc. Số dòng kết quả là 3829, chi tiết đƣợc trình bày ở mục kết quả thực nghiệm. Bảng 2. Giá trị trung bình AP theo lớp dữ liệu Lớp Trung bình AP (%) Lớp Trung bình AP (%) 1 10,24 10 14,70 2 18,57 11 5,75 3 14,94 12 14,71 4 13,15 13 41,65 5 14,82 14 28,54 6 10,23 15 5,46 7 12,09 16 0,00 8 12,02 17 28,03 9 16.20
230 KẾT HỢP KỸ THUẬT GOM NHÓM VÀ PHẢN HỒI TƢƠNG ĐỒNG TRONG TÌM KIẾM ẢNH C. Kết quả thực nghiệm 1. Trung bình AP theo lớp dữ liệu Giá trị trung bình AP trên toàn tập dữ liệu là 15,36%, chi tiết trung bình AP của các lớp đƣợc thể hiện ở bảng 2 và biểu đồ hình 4. Hình 4. Trung bình AP theo lớp dữ liệu Theo biểu đồ hình 4 lớp 13 có giá trị trung bình AP cao nhất tuy nhiên giá trị này không đại diện cho toàn tập dữ liệu, bởi vì lớp 13 chỉ có 5 ảnh trong tập huấn luyện có GT = True. Lớp 16 có giá trị trung bình AP bằng 0 vì lớp này không có ảnh trong tập kiểm thử. Lớp 14 và 17 có giá trị trung bình AP cao là vì các lớp này có lƣợng ảnh trong tập huấn luyện lớn. 2. Trung bình AP theo lần rank Biểu đồ hình 5 thể hiện giá trị trung bình AP theo số lần rank. Ở lần rank đầu tiên chƣa lấy phản hồi tƣơng đồng và chƣa kết hợp đặc trƣng văn bản, kết quả trung bình AP chỉ đạt 0,72%, kết quả này tƣơng đối thấp một phần do vector đặc trƣng ảnh chỉ có 512 chiều (trong thực nghiệm số chiều lớn hơn không cải thiện kết quả ở những lần rank sau nhƣng tốn rất nhiều thời gian để gom nhóm top k kết quả). Ở lần rank thứ hai kết quả trung bình AP tăng vọt do có kết hợp phản hồi tƣơng đồng và đặc trƣng văn bản. Ở những lần rank tiếp theo giá trị trung bình AP tăng chậm dần do số ảnh tƣơng đồng và không tƣơng đồng tăng dần và gần đến giá trị bảo hoà đối với tập dữ liệu thực nghiệm. Ở lần rank thứ bảy giá trị trung bình AP hầu nhƣ không thay đổi nhiều. Phần tiếp theo sẽ xác định tham số kết hợp độ tƣơng đồng ( ) tác động đến kết quả AP. Hình 5. Trung bình AP theo lƣợt rank 3. Trung bình AP theo tham số kết hợp độ tƣơng đồng Do việc lấy phản hồi tƣơng đồng bằng tay mất rất nhiều thời gian nên nghiên cứu chƣa thể so sánh đƣợc kết quả khi thay đổi tham số kết hợp độ tƣơng đồng ( ) giữa đặc trƣng ảnh và đặc trƣng văn bản. Một phƣơng pháp thay thế là cài đặt hệ thống phản hồi tự động (phản hồi ngẫu nhiên dựa trên tập Ground Truth), cài đặt hệ thống chạy 10 lần cùng tham số với phản hồi thủ công, sau đó lấy trung bình kết quả để so sánh nhƣ mô tả ở hình 6. Hình 6. Trung bình AP theo phƣơng pháp lấy phản hồi
Nguyễn Tí Hon, Hà Thị Phƣơng Anh, Phạm Thế Phi 231 Nhận thấy rằng kết quả phản hồi tự động có trung bình AP là 15,13% so với phản hồi thủ công là 15,36% có khác biệt không nhiều, nên có thể sử dụng phản hồi tự động trên các giá trị khác nhau của . Hình 7. Trung bình AP theo tham số kết hợp độ tƣơng đồng Biểu đồ hình 7 trình bày kết quả trung bình AP của tập dữ liệu huấn luyện trên cơ sở điều chỉnh tham số . Kết quả thực nghiệm cho thấy giá trị trung bình AP có xu hƣớng càng cao khi tham số càng thấp, điều này chứng tỏ đóng góp của văn bản về nội dung ảnh trong tập dữ liệu “Di sản văn hoá phi vật thể khu vực Đồng bằng sông Cửu Long” là rất lớn. Tuy vậy đặc trƣng ảnh vẫn đóng vai trò quan trọng trong quá trình gom nhóm và hiển thị trực quan để lấy phản hồi tƣơng đồng. Mục đích của việc gom nhóm kết quả truy vấn trƣớc khi hiển thị để lấy phản hồi là để tăng hiệu quả phản hồi, hay nói cách khác trong một lần ta chọn đƣợc nhiều ảnh tƣơng đồng hoặc không tƣơng đồng. Do chất lƣợng tập dữ liệu thực nghiệm không đồng đều nên mục này lấy trung bình số ảnh theo click phản hồi đối với từng lớp để dễ so sánh. Vì các ảnh phản hồi chỉ đƣợc lấy vào tập tƣơng đồng hoặc không tƣơng đồng một lần nên có trƣờng hợp một ảnh đƣợc chọn nhiều lần ở những đợt phản hồi khác nhau dẫn đến số click tăng lên nhƣng số ảnh đƣợc chọn không tăng, điều này cũng ảnh hƣởng tới tỉ lệ ảnh/click, ngoài ra tỉ lệ ảnh/click còn bị ảnh hƣởng rất nhiều bởi việc giới hạn số cluster khá lớn trong quá trình gom nhóm top k ảnh kết quả. Biểu đồ hình 8 cho thấy trong mỗi click phản hồi nhận đƣợc số ảnh không nhiều, cao nhất là lớp 17 với trung bình 1,48 ảnh/click và thấp nhất là lớp 11 với trung bình 1,05 ảnh/click. Trên toàn tập dữ liệu giá trị này là 1,31. 4. Trung bình AP giữa các phƣơng pháp Biểu đồ hình 9 thể hiện kết quả so sánh giữa các phƣơng pháp sử dụng: đặc trƣng văn bản không phản hồi, đặc trƣng văn bản có phản hồi, đặc trƣng ảnh không phản hồi, đặc trƣng ảnh có phản hồi, kết hợp đặc trƣng không phản hồi và kết hợp đặc trƣng có phản hồi. Trong đó sử dụng đặc trƣng văn bản cùng với phản hồi tƣơng đồng cho kết quả tốt nhất (34,53%), tuy nhiên cũng chỉ cao hơn một chút so với việc không phản hồi (33,58%). Do đặc tính tập dữ liệu không đồng nhất nên sử dụng đặc trƣng ảnh chẳng những không cải thiện mà còn làm giảm kết quả truy vấn, điều này thể hiện rõ trong kết quả sử dụng kết hợp đặc trƣng và phản hồi tƣơng đồng thì kết quả tốt nhất chỉ đạt 32,54% khi tham số kết hợp (khi đó đặc trƣng ảnh chỉ đƣợc sử dụng cho quá trình hiển thị nhóm để lấy phản hồi), thấp hơn sử dụng đặc trƣng văn bản cùng với phản hồi tƣơng đồng đạt 34,53%. VII. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN Về mặt lý thuyết kỹ thuật gom nhóm kết quả trƣớc khi lấy phản hồi giúp tăng số lƣợng ảnh đƣợc chọn trong mỗi lƣợt phản hồi, cải thiện hiệu quả phản hồi. Bên cạnh đó kỹ thuật phản hồi tƣơng đồng và mở rộng truy vấn làm tăng hiệu quả tìm kiếm. Ngoài ra đặc trƣng văn bản có giá trị quan trọng trong bài toán tìm kiếm ảnh. Hình 8. Trung bình số ảnh mỗi click phản hồi theo lớp dữ liệu
232 KẾT HỢP KỸ THUẬT GOM NHÓM VÀ PHẢN HỒI TƢƠNG ĐỒNG TRONG TÌM KIẾM ẢNH Về mặt thực nghiệm do tập dữ liệu có rất nhiều lớp chứa các hình ảnh gần giống nhau, nên trong cài đặt thực nghiệm phải cắt cây phân cấp ở mức thấp dẫn đến số lƣợng nhóm (clusters) lớn (cho phép tối đa 800 nhóm, trong khi k kết quả cần gom nhóm chỉ có giá trị là 1000), do đó số ảnh tăng lên trong mỗi lƣợt chọn không nhiều (khoảng từ 1 đến 3 ảnh). Văn bản trong tập dữ liệu “Di sản văn hoá phi vật thể ở khu vực Đồng bằng Sông Cửu Long” có giá trị rất lớn trong việc nói lên nội dung của hình ảnh mà nó đi kèm. Nghiên cứu hƣớng tới thực hiện đánh giá thực nghiệm trên các loại đặc trƣng ảnh khác nhƣ đặc trƣng GIST, đặc trƣng màu sắc - COLOR; đánh giá thực nghiệm khi thay đổi các trọng số tin cậy , và trong công thức Rocchio. Đồng thời đánh giá thực nghiệm khi thay đổi các kiểu liên kết gom nhóm (liên kết đơn, liên kết tâm, liên kết toàn phần) và các loại khoảng cách (Euclid, cosine). Hình 9. Trung bình AP giữa các phƣơng pháp TÀI LIỆU THAM KHẢO [1] Trƣơng Quốc Định, Ngô Bá Hùng, Trƣơng Quốc Bảo, Các Hệ Thống Tìm Kiếm Thông Tin Văn Bản, NXb Đại học Cần Thơ, Cần Thơ, 2014 [2] Phạm Nguyên Khang, Phạm Thế Phi, Đỗ Thanh Nghị, Trần Nguyễn Minh Thƣ, “Sự ảnh hƣởng của phƣơng pháp tách từ trong bài toán phân lớp văn bản tiếng Việt”, Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR 2016, tr.668-677, 2016. [3] Đỗ Thanh Nghị, Phạm Nguyên Khang, Nguyên lý máy học, NXb Đại Học Cần Thơ, Cần Thơ, 2012. [4] Đỗ Thanh Nghị, Trần Cao Đệ, “Kết hợp ngữ nghĩa với mô hình túi từ để cải tiến giải thuật k láng giềng trong phân lớp văn bản ngắn”, Tạp chí Khoa học Trƣờng Đại học Cần Thơ, 34, tr.66-73, 2014. [5] James Allan, “Incremental relevance feedback for information filtering”, Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 19, pp.270-278, 1996. [6] Mghana M Chavan, Asawari Patil, Lata Dalvi, Ajinkya Patil, “Mini batch K-Means clustering on large dataset”, International Journal of Scientific Engineering and Technology Research, 4(7), pp.1356-1358, 2015. [7] Hsin-Liang Chen, Edie M. Rasmusse, “Intellectual Access to Images”, Library Trends, 48(2), pp.291-302, 1999. [8] Yixin Chen, James Z. Wang, Robert Krovetz, “Content-based Image Retrieval by Clustering”, Proceedings of the 5th ACM SIGMM International Workshop on Multimedia Information Retrieval, 3, pp.193-200, 2003. [9] Yixin Chen, James Z. Wang, Robert Krovetz, “CLUE: Cluster-Based Retrieval of Images by Unsupervised Learning”, Ieee transactions on image Processing, 14(8), pp.1187-1201, 2005. [10] Stéphane Clinchant, Julien Ah-Pine, Gabriela Csurka, “Semantic Combination of Textual and Visual Information in Multimedia Retrieval”, Proceedings of the 1st ACM International Conference on Multimedia Retrieval, 11(44), pp.1-8, 2011. [11] Ritendra Datta, Jia Li, James Z. Wang, “Content-based image retrieval: approaches and trends of the new age”, Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, 5, pp.253-262, 2005. [12] Anton Leuski, “Evaluating Document Clustering for Interactive Information Retrieval”, International Conference on Information and Knowledge Management, 10, pp.33-40, 2001. [13] David G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60(2), pp.91-110, 2004. [14] Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze, An Introduction to Information Retrieval, Cambridge University Press, New York, USA, 2008. [15] Banireddy Prasaad, Amar Gupta, Hoomin Toong, Stuart Madnick, “Amicrocomputer-based image database management system”, IEEE Transactionson Industrial Electronics, 34(1), pp.83-88, 1987.
Nguyễn Tí Hon, Hà Thị Phƣơng Anh, Phạm Thế Phi 233 [16] Ricardo da Silva Torres, Alexandre Xavier Falcão, “Content-Based Image Retrieval: Theory and Applications”, RITA, 13(2), pp.161-185, 2006. [17] D. Sculley, “Web-scale k-means clustering”, Proceedings of the 19th international conference on world wide web, pp.1177-1178, 2010. [18] Gang Wang, Derek Hoiem, David Forsyth, “Building text features for object image classification”, CVPR, pp.1367-1374, 2009. THE COMBINATION OF CLUSTERING AND RELEVANT FEEDBACK IN IMAGES RETRIEVAL Nguyen Ti Hon, Ha Thi Phuong Anh, Pham The Phi Abstract: Image retrieval is a field that is receiving a lot of attention from the computer science community. The current research trend is to combine algorithms and feature extraction methods to increase query efficiency. One of the most well-used methods is the relevant feedback technique, which people determine whether a resulting image is appropriate or inconsistent with the query image, then to modify the original query to increase relevant results. In addition, clustering is usually used to increase the efficiency of feedback, instead of each response the user only selects one image, with this method, the user will select a group of images, all images in that group will be considered relevant or not irrelevant. In image retrieval, local feature is frequently used because of suitable to identify objects within the image, and is not affected by the size, rotation, and brightness of the objects in images. In addition, images on the Internet are often accompanied by short notes or descriptions (collectively referred to as descriptions), which are of great value in expressing the content within the image. Simultaneous use of image feature and text feature is a new approach and has been proven effective in machine learning studies. From that fact, the study proposes to use a combination of clustering techniques to get feedback, the feature is local image feature and text feature. The study was evaluated on the data set of "Intangible Cultural Heritage in the Mekong River Delta", which was collected automatically from the Internet using the Web crawler tool, the experimental results showed that the method was The proposal has brought good results in improving the feedback efficiency as well as query results. Keywords: Image retrieval, image classification, clustering, relevant feedback, feature combinations.