Một phương pháp tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/319236116 MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN Article · August 2017 CITATIONS 0 READS 163 8 authors, including: Some of the authors of this publication are also working on these related projects: Ngô Quốc Tajo and Phạm Việt Bình View project Content-based image retrieval View project Quynh Dao Thi Thuy Posts and Telecommunications Institute of Technology 4 PUBLICATIONS   2 CITATIONS    SEE PROFILE Quynh Nguyen Huu Electric Power University 34 PUBLICATIONS   65 CITATIONS    SEE PROFILE Canh Phuong Van Electric Power University 4 PUBLICATIONS   2 CITATIONS    SEE PROFILE Tao Quoc Ngo Institute of Information Technology/Vietnamese Academy of Scienc 33 PUBLICATIONS   42 CITATIONS    SEE PROFILE All content following this page was uploaded by Quynh Nguyen Huu on 23 August 2017. The user has requested enhancement of the downloaded file. Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN Đào Thị Thúy Quỳnh *, Nguyễn Hữu Quỳnh **, Phương Văn Cảnh **, Ngô Quốc Tạo*** *Trường Đại học Khoa học, Đại học Thái Nguyên, ** Khoa Công nghệ thông tin, Trường Đại học Điện lực, ** *Viện Công nghệ thông tin, Viện Hàn Lâm Khoa học và Công nghệ Việt Nam, quynhdtt@tnus.edu.vn, quynhnh@epu.edu.vn, canhpv@epu.edu.vn, nqtao@ioit.ac.vn TÓM TẮT- Nhiều kỹ thuật tra cứu ảnh dựa vào nội dung được thiết kế để lấy ra các ảnh trong một lân cận nào đó của ảnh truy vấn và do đó bỏ qua các ảnh liên quan nằm trong toàn bộ không gian đặc trưng. Trong bài báo này, chúng tôi đề xuất một phương pháp tra cứu ảnh, gọi là SCRF (spectral clustering in relevant feedback) có ưu điểm là không yêu cầu người dùng phải xây dựng truy vấn phức tạp mà vẫn lấy được ảnh nằm rải rác trong toàn bộ không gian đặc trưng. Bên cạnh đó, phương pháp khai thác được đầy đủ thông tin tương tự giữa các ảnh phản hồi của người dùng hình thành các cụm liên quan ngữ nghĩa để xây dựng truy vấn đa điểm ở lần truy vấn tiếp theo. Hơn nữa, thời gian tra cứu của phương pháp cũng không tăng theo số lượng ảnh phản hồi từ người dùng. Chúng tôi cũng cung cấp các kết quả thực nghiệm để minh chứng độ chính xác của phương pháp. Từ khóa- Tra cứu ảnh dựa vào nội dung, phản hồi liên quan, truy vấn đa điểm, phân cụm phổ. I.GIỚI THIỆU Tra cứu ảnh dựa vào nội dung (CBIR-Content Based Image Retrieval) đã nhận được nhiều sự quan tâm trong thập kỷ qua, do nhu cầu xử lý hiệu quả lượng dữ liệu đa phương tiện khổng lồ và tăng nhanh chóng. Nhiều hệ thống CBIR đã được phát triển, gồm QBIC, Photobook, MARS, NeTra, PicHunter, Blobworld, VisualSEEK, SIMPLIcity và những hệ thống khác. Trong một hệ thống CBIR tiêu biểu, các đặc trưng ảnh trực quan mức thấp (tức là màu, kết cấu và hình dạng) được trích rút tự động cho mục tiêu đánh chỉ số và mô tả ảnh. Đối với cách tiếp cấn truy vấn bởi mẫu, một ảnh truy vấn đưa vào hệ thống sẽ được xử lý tương tự như ảnh cơ sở dữ liệu để sinh ra một véc tơ thích hợp. Tra cứu tiếp theo được thực hiện bằng việc sinh ra một danh sách các ảnh được phân hạng theo thứ tự giảm dần của độ đo tương tự so với ảnh truy vấn. Là một vấn đề quan trọng trong CBIR, độ đo tương tự lượng hóa sự giống nhau về nội dung giữa từng cặp ảnh. Phụ thuộc vào kiểu đặc trưng mà chúng ta lựa chọn độ đo tương tự thích hợp. Tất cả các kỹ thuật tra cứu dựa vào nội dung hiện nay đều thừa nhận thông tin tương hỗ giữa độ đo tương tự ảnh và ngữ nghĩa của ảnh. Bằng các cách khác nhau, độ đo tương tự cố gắng nắm được một khía cạnh nào đó của nội dung ảnh, đó là ngữ nghĩa kế thừa từ độ tương tự hay đặc trưng mức thấp. Tuy nhiên, ngữ nghĩa kế thừa từ độ tương tự nhiều khi không giống với khái niệm mức cao được truyền tải bởi một ảnh (ngữ nghĩa của ảnh). Đó chính là khoảng cách ngữ nghĩa [7], nó phản ánh sự khác biệt giữa năng lực mô tả hạn chế của đặc trưng trực quan mức thấp và khái niệm mức cao. Cách tiếp cận dựa vào phản hồi liên quan đối với tra cứu ảnh dựa vào nội dung là một lĩnh vực nghiên cứu tích cực trong mấy năm qua nhằm rút ngắn khoảng cách ngữ nghĩa. Một số nghiên cứu tốt theo cách tiếp cận này có thể tìm thấy trong [1; 3; 8; 10; 11; 13; 14; 16]. Hầu hết các hệ thống CBIR đã có biểu diễn các ảnh bằng các véc tơ đặc trưng sử dụng các đặc trưng trực quan, trong đó hai véc tơ được coi là gần nhau nếu hai ảnh tương ứng với hai véc tơ đó sẽ tương tự nhau hơn. Khi các hệ thống CBIR đưa ra một tập các ảnh được xem là tương tự với một ảnh truy vấn đã cho, người dùng có thể lấy ra các ảnh liên quan nhất đối với truy vấn đã cho và hệ thống điều chỉnh lại truy vấn sử dụng các ảnh liên quan mà người dùng vừa chọn. Các kỹ thuật CBIR dựa vào phản hồi liên quan không yêu cầu người dùng cung cấp các truy vấn khởi tạo chính xác nhưng yêu cầu người dùng xây dựng truy vấn lý tưởng thông qua đánh giá các ảnh là liên quan hay không. Các cách tiếp cận đối với CBIR giả thiết rằng, về nguyên tắc các ảnh liên quan gần với ảnh truy vấn trong không gian đặc trưng nào đó. Tuy nhiên, sự tương tự giữa các ảnh mà con người nhận thức lại có sự khác biệt với khoảng cách giữa chúng trong không gian đặc trưng. Tức là, các ảnh liên quan về mặt ngữ nghĩa có thể nằm phân tán trong toàn bộ không gian đặc trưng và nằm rải rác ở một số cụm chứ không phải một cụm. Trong trường hợp này, các cách tiếp cận phản hồi liên quan truyền thống [1; 3; 5; 8; 10; 11; 14; 16; 18; 19] không làm việc tốt khi dịch chuyển tâm truy vấn. Thực hiện phản hồi liên quan đề cập đến việc tính toán một hoặc nhiều điểm truy vấn mới trong không gian đặc trưng và thay đổi hàm khoảng cách. Như được chỉ ra trong Hình 1(a), các nghiên cứu theo hướng tiếp cận ban đầu [1; 5; 8; 16] biểu diễn một truy vấn mới bằng một điểm đơn và thay đổi các trọng số của các thành phần đặc trưng để tìm một điểm truy vấn tối ưu và một hàm khoảng cách tối ưu. Trong trường hợp này, một điểm đơn được tính toán sử dụng trung bình trọng số của tất cả các ảnh liên quan trong không gian đặc trưng. Các đường viền biểu diễn các đường có độ tương tự tương đương. Trong khi đó, một cách tiếp cận nghiên cứu sau đó [7; 20; 21; 22; 24] biểu diễn một truy vấn mới bằng nhiều điểm để xác định hình của đường viền như Hình 1(b). Cách tiếp cận này sử dụng một phương pháp phân cụm [23] để tính toán các điểm truy vấn mới sử dụng các các kết quả truy vấn (các ảnh liên quan) dựa vào đánh giá phản hồi của người dùng. Với giả thiết rằng các ảnh liên quan được ánh xạ sang các điểm gần nhau theo độ đo tương tự. Một đường viền rộng được xây dựng để phủ tất cả các điểm truy vấn và hệ thống tìm các ảnh tương tự với các truy vấn này. Tuy nhiên, nếu không gian đặc trưng và hàm khoảng cách rất khác so với nhận thức của người dùng, các ảnh liên quan được ánh xạ sang các vùng có hình dạng bất kỳ tách rời trong không gian đặc trưng. Tức là, các ảnh liên quan có thể được phân hạng dưới các ảnh được tra cứu khác theo một truy vấn đã cho. Để hội tụ nhanh đến nhu MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN cầu thông tin ở mức ngữ nghĩa cao hơn, hệ thống sẽ tìm các ảnh tương tự với bất kỳ các điểm truy vấn nào như trong Hình 1(c). Một truy vấn mà tra cứu các ảnh tương tự với bất kỳ các điểm truy vấn nào được gọi là truy vấn tách rời hay truy vấn đa điểm. Đặc biệt, một truy vấn ảnh phức tạp được biểu diễn bằng nhiều vùng tách rời do các ảnh liên quan ngữ nghĩa có thể nằm rải rác trong một số vùng trực quan hơn là một vùng. Hình 1.1. Hình dạng truy vấn. (a) Dịch chuyển điểm truy vấn (b) Hình dạng lồi (đa điểm) (c) Hình dạng lõm (đa điểm) Tất cả các kỹ thuật CBIR hiện nay đều chắc chắn thừa nhận thông tin tương hỗ giữa độ đo tương tự và ngữ nghĩa của ảnh. Một hệ thống CBIR điển hình xếp hạng các ảnh mục tiêu theo độ đo tương tự đối với ảnh truy vấn nên chỉ lấy được các ảnh nằm trong lân cận của ảnh truy vấn và bỏ qua những ảnh liên quan nằm rải rác trong toàn bộ không gian đặc trưng. Các hạn chế ở trên là động lực để chúng tôi đề xuất phương pháp cải thiện được sự tương tác người dùng với các hệ thống tra cứu ảnh bằng cách khai thác đầy đủ thông tin độ tương tự giữa các ảnh trong tập phản hồi. Bên cạnh đó không cần đòi hỏi người dùng phải đưa vào nhiều ảnh truy vấn đa dạng thích hợp để biểu diễn nhu cầu thông tin của mình. Thời gian tra cứu cũng không tăng theo số lượng ảnh phản hồi của người dùng. Phần còn lại của bài báo này được tổ chức như sau: trong phần 2, trình bày chi tiết phương pháp tra cứu ảnh sử dụng phân cụm phổ trong phản hồi liên quan. Phần 3, mô tả các kết quả thực nghiệm và cuối cùng là kết luận được đưa ra trong phần 4. II. PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN Trong phần này, chúng tôi sẽ giới thiệu chung hệ thống đề xuất. Tiếp theo, chúng tôi mô tả chi tiết từng thành phần của hệ thống. Cuối cùng, thuật toán tra cứu đề xuất được trình bày. 2.1. Mô tả chung về phương pháp Hình 2.1. Cấu trúc của phương pháp đề xuất. Phương pháp SCRF được mô tả bởi sơ đồ trên hình 2.1., quá trình tra cứu bắt đầu từ việc trích rút đặc trưng của ảnh truy vấn. Các đặc trưng của ảnh cơ sở dữ liệu thường được trích rút và lưu trữ thành tập các véc tơ đặc trưng. Sử dụng các đặc trưng này với một độ đo tương tự đặc trưng, sự tương đồng giữa ảnh truy vấn và ảnh cơ sở dữ liệu được so sánh và phân hạng. Tiếp theo, một tập ảnh lân cận với ảnh truy vấn khởi tạo được trả về cho người dùng. Người dùng sẽ chọn những ảnh liên quan tới mong muốn của họ để hình thành lên tập ảnh phản hồi. Một thuật toán phân cụm sẽ được áp dụng lên tập ảnh phản hồi để hình thành lên các cụm liên quan ngữ nghĩa. Với mỗi cụm vừa tìm được phương pháp của chúng tôi sẽ thực hiện tìm đại diện cho mỗi cụm để hình thành truy vấn đa điểm đưa vào thực hiện tra cứu ở lần lặp sau. Quá trình được lặp lại cho đến khi người dùng ngừng phản hồi và phương pháp đưa ra tập kết quả. SCRF Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo 2.2. Phương pháp đề xuất Phương pháp của chúng tôi thay vì tìm một truy vấn trung tâm cho các mẫu tích cực mà người dùng chọn, chúng tôi sẽ thực hiện phân cụm tập ảnh phản hồi của người dùng. Sau khi có được các cụm ngữ nghĩa đó, chúng tôi tìm đại diện cho mỗi cụm. Mỗi đại diện đó được dùng để hình thành lên truy vấn đa điểm ở lần lặp tra cứu tiếp theo. Phương pháp sẽ tìm các ảnh tương tự với bất kỳ điểm nào hay đại diện nào của truy vấn đa điểm để trả về danh sách ảnh đa dạng nằm rải rác trong toàn bộ không gian đặc trưng. Thuật toán phân cụm tập ảnh phản hồi từ người dùng Trong tập ảnh lân cận được trả về bởi truy vấn khởi tạo người dùng sẽ chọn n ảnh liên quan. Để khai thác thông tin tương tự giữa các ảnh trong tập ảnh phản hồi chúng ta gọi thuật toán CRISE để hình thành lên các các cụm ngữ nghĩa. Mỗi ảnh được chọn để đại diện cho mỗi cụm phải là ảnh mà tương tự nhất với tất cả các ảnh trong cụm. Các đại diện của các cụm sẽ hình thành lên truy vấn đa điểm ở lần lặp tra cứu tiếp theo. Quá trình trên được lặp lại cho đến khi người dùng dừng phản hồi. Biểu diễn và phân cụm tập ảnh phản hồi Dưới một biểu diễn đồ thị, phân cụm có thể được phát biểu tự nhiên như một bài toán phân hoạch đồ thị. Trong số nhiều phương pháp phân hoạch đồ thị phổ [4; 15; 9; 17] đã được áp dụng thành công với nhiều lĩnh vực trong thị giác máy tính gồm phân tích chuyển động [5], phân đoạn ảnh [9; 17] và nhận dạng đối tượng [15]. Trong bài báo này, chúng tôi sử dụng phương pháp sử dụng k véc tơ riêng và tính trực tiếp phân hoạch k-way trong [2]. So với phương pháp sử dụng một véc tơ riêng tại một thời điểm và gọi đệ qui [9], phương pháp sử dụng k véc tơ riêng được chỉ ra là tốt hơn về mặt thực hành. Nói chung, một phương pháp phân hoạch đồ thị cố gắng tổ chức các nút thành các nhóm sao cho độ tương tự trong phạm vi nhóm là cao, và/hoặc độ tương tự giữa các nhóm là thấp. Một đồ thị đã cho G=(V,E) với ma trận affinity A, một cách đơn giản để định lượng giá cho các nút phân hoạch thành hai tập rời nhau C1 và C2 (C1C2= và C1C2=V) là tổng có trọng số của các cạnh mà kết nối hai tập. Tiếp theo, chúng tôi trình bày ngắn gọn phương pháp dựa trên nghiên cứu của A. Y. Ng và cộng sự (xem chi tiết hơn tại [2]). Đầu tiên, từ n điểm dữ liệu ảnh, phương pháp xây dựng ma trận affinity A theo 𝑎𝑖𝑗 = 𝑒 −‖𝑠𝑖−𝑠𝑗‖ 2 2𝜎2 (i ≠ j), aii=0) (1). Ở đây tham số tỉ lệ 2 điều khiển mức độ ái lực aij giảm nhanh thế nào với khoảng cách giữa si và sj, phương pháp chọn tự động có thể xem trong [2]. Một giá trị aij giữa hai ảnh là “cao” nếu hai ảnh là rất tương tự. Xây dựng ma trận đường chéo D trong đó phần tử (i,i) là tổng hàng thứ i của ma trận A. D là một ma trận chéo với 𝐷𝑖𝑖 = ∑ 𝑎𝑖𝑗𝑗=1,,𝑛 . Tính ma trận Laplace chuẩn hóa : L = D-1/2 A D-1/2. Tìm k véc tơ riêng x1,x2,xk lớn nhất của ma trận L, trong đó x1=(x11, x12, x13, , x1n), x2=(x21, x22, x23, , x2n), .xk=(xk1, xk2, xk3, , xkn) và xây dựng ma trận X = [x1T ,x2T ,,xkT ] Є Rn x k , cụ thể: x1T x2T x3T xkT x11 x21 x31 xk1 x12 x22 x32 xk2 x13 x23 x33 xk3 x1n x2n x3n xkn Xây dựng ma trận Y từ X bằng việc chuẩn hóa mỗi dòng của X là chiều dài đơn vị của ma trận Y (Yij = Xij (∑ Xij 2 )j 1 2 ) y1 y11 y12 y13 y1k y2 y21 y22 y32 y2k y3 y31 y32 y33 y3k yk yn1 yn2 ynk MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN Mỗi dòng của ma trận Y được xem như là một điểm trong không gian véc tơ k chiều. Đến đây, sẽ có n điểm trong không gian Rk, phân cụm (yi)i=1n trong không gian Rk thành k cụm C1,C2,,Ck thông qua K-Means. Cuối cùng, gán điểm si tới cụm j nếu và chỉ nếu hàng thứ i của ma trận Y tưởng ứng với cụm j. Hình 2 dưới đây là thuật toán phân cụm sử dụng k véc tơ riêng CRISE (Clustering Relevant Images Set using Eigenvectors) thực hiện việc phân cụm tập các ảnh liên quan mà người dùng chọn thành k cụm. Thuật toán CRISE Input: -Tập các ảnh S={s1,s2,,sn} với si Rn - Số cụm k Output: k cụm: C1,C2,,Ck Bước 1: Xây dựng ma trận affinity for i1 to n do for j1 to n do if (ij) 𝑎𝑖𝑗 exp( −‖𝑠𝑖−𝑠𝑗‖ 2 2𝜎2 ) else 𝑎𝑖𝑗0 Bước 2: Xây dựng ma trận đường chéo và ma trận Laplace L for i1 to n do 𝑑𝑖𝑖∑ 𝑎𝑖𝑗𝑗=1,,𝑛 L  D-1/2 A D-1/2 Bước 3: Tìm k véc tơ riêng lớn nhất x1,x2,,xk của ma trận Laplace L for i1 to k do 𝑥𝑖𝐿𝑎𝑟𝑔𝑒𝑠𝑡_𝑒𝑖𝑔𝑒𝑛_𝑣𝑒𝑐𝑡𝑜𝑟𝑠(𝐿) X  [x1T ,x2T ,,xkT ] Bước 4 : Xây dựng ma trận Y từ X for i1 to n do for j1 to k do yij  xij/ (∑ 𝑥𝑖𝑘 2 𝑘 ) 1/2 Y  [y1 ,y2 ,,yk ] Bước 5: Phân thành k cụm thông qua K-Means 𝑃 for i1 to n do 𝑝𝑖𝑦𝑖 𝑃𝑃𝑝𝑖 K-Mean(P) Bước 6: Gán các si vào các cụm for i1 to n do if 𝑝𝑖 ∈ (𝐶𝑗)𝑖=1,..𝑘 𝐶𝑗 ← 𝐶𝑗 ∪ 𝑠𝑖 Return C1,C2,,Ck Hình 2.2: Thuật toán CRISE. Tìm ảnh đại diện cho cụm Để thực hiện việc tra cứu ảnh hiệu quả, một ảnh đại diện thích hợp phải thu được cho mỗi cụm. Ở đây, một ảnh được chọn là đại diện cho một cụm phải là ảnh mà tương tự nhất với tất cả các ảnh trong cụm. Phát biểu này được minh họa bằng toán học như sau : Với một biểu diễn đồ thị của các ảnh được cho G=(V,E) với ma trận affinity A, cho tập các cụm ảnh là {C1,C2,,Ck} (tập các cụm này cũng này cũng là một phân hoạch của V, tức là Ci ∩ Cj = ∅, i ≠ 𝑗 và ⋃ 𝐶𝑖 𝑘 𝑖=1 = 𝑉) thì ảnh đại diện của 𝐶𝑖 là 𝑎𝑟𝑔 max 𝑗∈𝐶𝑖 ∑ 𝑎𝑗∈𝐶𝑖 𝑗𝑡 (2) Như vậy, với một cụm, ảnh đại diện là ảnh mà có tổng độ tương tự trong phạm vi cụm là cực đại. Khoảng cách từ một ảnh đến truy vấn đa điểm Khác với các phương pháp tra cứu ảnh khác , phương pháp của chúng tôi sẽ hình thành lên truy vấn truy vấn đa điểm MQ=(Q1, Q2,..Qk) từ các đại diện của mỗi cụm. Khi đó, khoảng cách từ một ảnh 𝐷𝐼𝑖 đến truy vấn đa điểm MQ=(Q1, Q2,..Qk) là cực tiểu của các khoảng cách có trọng số từ một ảnh 𝐷𝐼𝑖 đến mỗi Qj trong truy vấn đa điểm và được tính theo công thức (3): 𝐷(𝐷𝐼𝑖 , 𝑀𝑄) = 𝑚𝑖𝑛𝑗=1..𝑘𝒅𝒊𝒔𝒕(𝐷𝐼𝑖 , 𝑄𝑗) (3) Trong công thức (3), 𝒅𝒊𝒔𝒕(𝐷𝐼𝑖 , 𝑄𝑗) với i=1..N, j=1..k là khoảng cách từ một ảnh 𝐷𝐼𝑖 đến một điểm truy vấn Qj trong truy vấn đa điểm MQ. Thuật toán tra cứu ảnh sử dụng phân cụm phổ trong phản hồi liên quan Hình 2.2 dưới đây mô tả Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi, có tên SCRF. Khi người dùng thực hiện truy vấn, phương pháp sẽ sử dụng thuật toán MQMRBR [12] để tra cứu trên tập các ảnh cơ Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo sở dữ liệu DI và cho kết quả là tập các ảnh S. Người dùng thực hiện việc chọn tập các ảnh liên quan E trong tập S thông qua hàm 𝑼𝒔𝒆𝒓_𝑪𝒉𝒐𝒐𝒔𝒆_𝑹𝒆𝒍𝒆𝒗𝒂𝒏𝒄𝒆𝑰𝒎𝒂𝒈𝒆(), phương pháp sẽ phân cụm tập E này thành k cụm thông qua thuật toán CRIES và tìm đại diện cho k cụm đó thông qua hàm 𝑪𝒐𝒎𝒑𝒖𝒕𝒆_𝑹𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒗𝒆() và gán cho tập đại diện. Khoảng cách giữa ảnh cơ sở dữ liệu DIi và truy vấn đa điểm MQ được tính theo công thức (3). Quá trình này tiếp tục cho đến khi người dùng dừng việc chọn các ảnh liên quan. Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan Input: Tập N ảnh cơ sở dữ liệu DI Ảnh truy vấn Q Ouput: Tập ảnh kết quả S’ MQMRBR(DI, Q, S) // Thực hiện trên tập ảnh DI với truy vấn Q để cho ra tập kết quả S Repeat 𝐸𝑼𝒔𝒆𝒓_𝑪𝒉𝒐𝒐𝒔𝒆_𝑹𝒆𝒍𝒆𝒗𝒂𝒏𝒄𝒆𝑰𝒎𝒂𝒈𝒆(S, n) // người dùng chọn các ảnh liên quan từ tập ảnh S 𝐶𝑪𝑹𝑰𝑬𝑺(E, k) // phân tập ảnh liên quan E thành k cụm RI𝑪𝒐𝒎𝒑𝒖𝒕𝒆_𝑹𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒗𝒆(C, M) For i←1 to N do For j1 to k do Tính disi theo công thức sau : 𝑑𝑖𝑠𝑖 = 𝑚𝑖𝑛𝑗=1..𝑘𝑑𝑖𝑠𝑖𝑗 Sort(DI) // sắp xếp các ảnh trong tập ảnh cơ sở dữ liệu DI theo thứ tự tăng dần của khoảng cách so với truy vấn đa điểm MQ. Return S’ // danh sách ảnh có khoảng cách nhỏ nhất với MQ Until (User dừng phản hồi) Hình 2.3: Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan SCRF. 3. THỰC NGHIỆM 3.1. Môi trường thực nghiệm Cơ sở dữ liệu ảnh: Cơ sở dữ liệu được sử dụng cho thử nghiệm được chúng tôi tổ chức lại từ tập con của Corel Photo Gallery. Tập này gồm 80 loại1, ví dụ như là: mùa thu, hàng không, cây cảnh, lâu đài, đám mây, chó, voi, núi băng, linh trưởng, tàu, nhũ đá, hỏa tiến, hổ, tàu hỏa, thác nước,. Tất cả các ảnh trong tập ảnh này có tính chất là đều chứa đối tượng tiền cảnh nổi bật. Đa số nhóm đều gồm 100 ảnh, có một vài nhóm có hơn 100 hình ảnh. Cỡ của các ảnh có max(chiều rộng, chiều cao)=120 và min(chiều rộng, chiều cao)=80. Véc tơ đặc trưng: Các đặc trưng được chia làm hai loại là: các đặc trưng màu và các đặc trưng kết cấu (xem Bảng 1 ở dưới). Bảng 1. Các loại đặc trưng. Các loại đặc trưng Tên đặc trưng Độ dài Loại đặc trưng màu Lược đồ màu hsvHistogram 32 Tương quan màu color auto correlogram 64 Gắn kết màu colorMoments 6 Loại đặc trưng kết cấu Biến đổi wavelet waveletTransform 40 gabor Wavelet gaborWavelet 48 Biểu diễn ảnh: Mỗi ảnh được sử dụng biểu diễn bởi năm đặc trưng trực quan gồm ba đặc trưng màu và hai đặc trưng kết cấu. Các véc tơ đặc trưng tương ứng với mỗi kênh là một bảng hai chiều gồm 10800 dòng (mỗi dòng chứa một véc tơ đặc trưng của ảnh) và 190 cột (độ dài tổng của một véc tơ đặc trưng). Tập tin cậy nền (ground truth): Tập tin cậy nền Corel được sử dụng rộng rãi trong đánh giá CBIR, do đó chúng tôi cũng sử dụng phân loại Corel làm tin cậy nền, tức là chúng tôi xem tất cả các ảnh trong cùng loại Corel là liên quan. Tập tin cậy nền này gồm 3 cột (có tiêu đề: ID ảnh truy vấn, ID ảnh và Sự liên quan) và gồm 1,981,320 dòng. 3.2. Chiến lược mô phỏng phản hồi liên quan Để bắt chước hành vi của con người, chúng tôi thực hiện mô phỏng phản hồi liên quan trong thử nghiệm. Đầu tiên, truy vấn khởi tạo sẽ được thực hiện để tạo ra kết quả truy vấn. Chúng tôi mô phỏng tương tác người dùng bằng việc chọn n ảnh liên quan từ kết quả tra cứu khởi tạo dựa vào tập tin cậy nền (ground truth). Những ảnh liên quan từ 1 https://sites.google.com/site/dctresearch/Home/content-based-image-retrieval (Download lúc 6:32 AM ngày 25/12/2016) MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN lần lặp phản hồi đầu tiên sẽ được phân thành k cụm và thực hiện tìm đại diện cho k cụm này. Sau đó k đại diện được dùng để xây dựng truy đa điểm phục vụ cho tra cứu tiếp theo. Sau đó những kết quả tra cứu được gộp lại để tạo ra một danh sách kết quả tổng hợp theo chiến lược truy vấn đa điểm tách rời. Phản hồi liên quan được thực hiện theo chiến lược chọn những ảnh liên quan đầu tiên (dựa vào tập tin cậy nền) trong danh sách kết quả. Trong chiến lược này, trường hợp xấu nhất là không có ảnh liên quan nào ngoài ảnh truy vấn và trường hợp tốt nhất là có n-1 ảnh liên quan ngoài ảnh truy vấn. Do đó, số lượng ảnh liên quan có thể dao động từ 1 đến n ảnh (bao gồm cả ảnh truy vấn). Chiến lược này được sử dụng để mô phỏng người dùng thực tế trong thực nghiệm của chúng tôi. 3.3. Thực hiện truy vấn và đánh giá Trong thực nghiệm của chúng tôi, các yếu tố đó được lựa chọn như sau: Một truy vấn khởi tạo được đưa vào hệ thống, kết quả tương ứng với truy vấn đó được hiển thị cho người dùng. Sau đó, người dùng sẽ phản hổi trên danh sách kết quả tương ứng với truy vấn khởi tạo để hình thành danh sách ảnh phản hồi. Hệ thống sẽ thực hiện phân cụm danh sách ảnh phản hồi và tìm đại diễn cho mỗi cụm. Đại diện của mỗi cụm sẽ xây dựng lên truy vấn đa điểm ở lần lặp truy vấn tiếp theo. Trong pha tính khoảng cách, khoảng cách từ một ảnh trong cơ sở dữ liệu đến truy vấn đa điểm là giá trị cực tiểu của các khoảng cách từ ảnh cơ sở dữ liệu tới một đại diện của truy vấn đa điểm để lấy được các ảnh nằm rải rác trong toàn bộ không gian đặc trưng. Quá trình sẽ dừng lại khi người dùng không tiếp tục phản hồi. Mô hình hệ thống thực hiện quá trình này được thể hiện trên Hình 3.3. Hình 3.3. Mô hình hệ thống Độ chính xác2 trung bình ở mức 100 ảnh trả về được sử dụng để đánh giá. Bốn thiết lập phản hồi được sử dụng để so sánh là 1, 2, 3, 4 số đại diện của một truy vấn đa điểm và một chiến lược phản hồi, do đó sẽ có 4 cấu hình. Ba phương pháp khác nhau được sử dụng để so sánh bao gồm Jin&French (phương pháp sử dụng truy vấn tách rời) [6], hệ thống ERIN [12] với hệ thống SCRF mà chúng tôi đề xuất. Bảng 2. Bảng kết quả của 3 phương pháp số đại diện của truy vấn đa điểm trong một lần phản hồi. Phương pháp Độ chính xác theo số đại diện của truy vấn đa điểm 1 2 3 4 Jin&French 0.24 0.266 0.28 0.29 ERIN 0.24 0.29 0.31 0.33 SCRF 0.35168 0.43178 0.48154 0.48278 Trong Bảng 2, thể hiện độ chính xác trung bình của ba phương pháp là Jin&French, ERIN và phương pháp SCRF của chúng tôi tại các mức 1, 2, 3, 4 số đại diện của truy vấn đa điểm với phương pháp của chúng tôi số cụm cũng chính là số truy vấn. IV. Kết luận Chúng tôi đã tập trung vào đề xuất phương pháp, có tên là SCRF, giải quyết hai vấn đề chính đó là: (1) tìm các ảnh liên quan ngữ nghĩa nằm rải rác trong toàn bộ không gian đặc trưng với độ chính xác cao và (2) thời gian tra cứu không tăng theo số phản hồi của người dùng. Để giải quyết được hai vấn đề này, chúng tôi đã tận dụng sự đánh giá của người dùng để hình thành tập ảnh liên quan và phân cụm chúng thành các cụm ngữ nghĩa nằm rải rác trong toàn bộ không gian đặc trưng và đại diện của mỗi cụm hình thành lên truy vấn đa điểm. Phương pháp sử dụng một thuật toán phân cụm phổ có ưu điểm phân cụm các ảnh được kết nối với nhau nhưng không nhất thiết phải nhóm vào trong một đường bao lồi nên thực hiện tốt hơn các thuật toán phân cụm truyền thống. Từ đó có thể tra cứu được các ảnh nằm rải rác trong toàn bộ không gian đặc trưng và nâng cao độ chính xác. Kết quả thực nghiệm của chúng tôi trên cơ sở dữ liệu đặc trưng gồm 10.800 ảnh đã chỉ ra rằng phương pháp được đề xuất SCRF cung cấp một độ chính xác cao hơn hẳn so với các phương pháp Jin&French và phương pháp ERIN. 2 Độ chính xác là tỉ số giữa số các ảnh liên quan với ảnh truy vấn trong tập kết quả trả về trên tổng số các ảnh trả về. Q R Phân cụm các ảnh phản hồi Tìm đại diện Q1 Q2 Qk Máy tìm kiếm Máy tìm kiếm S Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo Chúng tôi xin chân thành cảm ơn đề tài: “Nghiên cứu phương pháp tra cứu ảnh dựa vào đa truy vấn”, mã số PTNTDD17.04 đã hộ trợ. TÀI LIỆU THAM KHẢO [1] Andre B, Vercauteren T, Buchner AM, Wallace MB, Ayache N (2012). Learning semantic and visual similarity for endomicroscopy video retrieval. IEEE Transactions on Medical Imaging. 31(6):1276–88. [2] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and algorithm. In Proceedings Of Neural Information Processing Systems (NIPS), 2001. [3] A.W.M. Smeulders, M. Worring, A. Gupta, R. Jain, Content-based image retrieval at the end of the early years, IEEE Trans. Pattern Anal. Mach. Intell. 22 (12) (2000) 1349–1380. [4] Bartolini, I., Ciacci, P., Waas, F., (2001). Feedbackbypass: A new approach to interactive similarity query processing. In: Proceedings of the 27th VLDB Conference, Roma, Italy, pp. 201–210. [5] J. Costeira and T. Kanade,“A multibody factorization method for motion analysis,”inProc. Int. Conf. Computer Vision, 1995, pp. 1071–1076. [6] Jin, X., & French, J.C, (2005). "Improving Image Retrieval Effectiveness via Multiple Queries," Multimedia Tools and Applications, vol. 26, pp. 221-245. [7] K. A. Hua, N. Yu, and D. Liu (2006). Query Decomposition: A Multiple Neighborhood Approach to Relevance Feedback Processing in Content-based Image Retrieval. InProceedings of the IEEE ICDE Conference. [8] Ishikawa, Y., Subramanya, R., Faloutsos, C., (1998). Mind Reader: Querying databases through multiple examples. In: Proceedings of the 24th VLDB Conference, New York, USA, pp. 218–227. [9] J. Shi and J. Malik,“Normalized cuts and image segmentation,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888–905, Aug. 2000. [10] Norton, D.; Heath, D.; and Ventura, D. (2016). Annotating images with emotional adjectives using features that summarize local interest points.IEEE Transactions on Affective Computing, Under Review. [11] M. Ortega-Binderberger and S. Mehrotra (2004). Relevance feedback techniques in the MARS image retrieval systems. Multimedia Systems, 9(6):535–547. [12] Quynh N.H., Quynh D.T.T., Tao N.Q., Dung C.V., Canh P.V., Sơn A.H. (2016). Một phương pháp tra cứu ảnh biểu diễn nhu cầu thông tin người dùng hiệu quả, Kỷ yếu hội nghị Quốc gia lần thứ 9 về Nghiên cứu cơ bản và ứng dụng trong Công nghệ thông tin (FAIR). [13] Rui, Y., Huang, T., Ortega, M., Mehrotra, S., (1998). Relevance feedback: A power tool for interactive content- based image retrieval. IEEE Transactions on Circuits and Systems for Video Technology 8 (5), pp. 644–655. [14] Rui, Y., Huang, T., Chang, S.F., (1999). Image Retrieval: current techniques, promising directions and open issues. Journal of Visual Communication and Image Representation 10, 39–62. [15] S. Sarkar and P. Soundararajan,“Supervised learning of large percep-tual organization: graph spectral partitioning and learning automata,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 5, pp. 504–525,May 2000. [16] T. Gevers and A. Smeulders (2004). Content-based image retrieval: An overview. In G. Medioni and S. B. Kang, editors, Emerging Topics in Computer Vision. Prentice Hall. [17] Y. Weiss,“Segmentation using eigenvectors: a unifying view,”inProc. Int. Conf. Computer Vision, 1999, pp. 975– 982. [18] Flickner, M., Sawhney, H., Niblack, W., et al., (1995). Query by image and video content: The QBIC system. IEEE Computer Magazine 28 (9), 23–32. [19] Rocchio, J.J., (1971). Relevance feedback in information retrieval. In: Salton, G. (Ed.), The SMART Retrieval System—Experiments in Automatic Document Processing. Prentice Hall, Englewood Cliffs, NJ, pp. 313–323. [20] O. Chum, J. Philbin, J. Sivic, M. Isard, and A. Zisserman (2007). Total recall: Automatic query expansion with a generative feature model for object retrieval. In Proc. ICCV. [21] Porkaew, K., Chakrabarti, K., (1999). Query refinement for multimedia similarity retrieval in MARS. In: Proceedings of the 7th ACM Multimedia Conference, Orlando, Florida, pp. 235–238. [22] R. Arandjelovi´c and A. Zisserman (2012). Three things everyone should know to improve object retrieval. In Proc. CVPR. [23] Charikar, M., Chekuri, C., Feder, T., Motwani, R., (1997). Incremental clustering and dynamic information retrieval. In: Proceedings of the ACM STOC Conference, pp. 626–635. MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN [24] Quynh Dao Thi Thuy, Quynh Nguyen Huu, Canh Phuong Van, Tao Ngo Quoc (2017), An efficient semantic – Related image retrieval method, Expert Systems with Applications, Volume 72, pp. 30-41. AN EFFICIENT IMAGE RETRIEVAL METHOD USING SPECTRAL CLUSTERING IN RELEVANT FEEDBACK Nguyen Huu Quynh*, Dao Thi Thuy Quynh**, Phương Văn Cảnh*, Ngo Quoc Tao*** *Information Technology Faculty, Electric Power University, **Thainguyen University of Science, ** *Institute of Information Technology, Vietnamese Academy of Science and Technology, quynhnh@epu.edu.vn, quynhdtt@tnus.edu.vn, canhpv@epu.edu.vn, nqtao@ioit.ac.vn Abstract - Many previous techniques were designed to retrieve images in a certain neighborhood of the query image, thus bypassing the related images in the whole feature space. Besides, some designed techniques only care about similarity between query image and data image that neglects similarities among data images. In this paper, we propose an efficient image retrieval method using spectral clustering in relevant feedback (SCRF) which has advantages that do not require the user to provide initial queries correctly but also retrieve relevant images in the entire feature space. In addition, our method fully exploit the similarity information of feedback image and contrust multipoints query in next query. Furthermore, the retrieval time of our method also is not increase with the number of user feedback. We also provide experimental results to demonstrate the effectiveness of our method. Keywords- Content based image retrieval, relevant feedback, multiponts query, spectral clustering. View publication stats