Nâng cao độ chính xác của tra cứu ảnh theo nội dung dựa trên tiếp cận học đa tạp từ thông tin phản hồi của người dùng

Nội dung tài liệu: Nâng cao độ chính xác của tra cứu ảnh theo nội dung dựa trên tiếp cận học đa tạp từ thông tin phản hồi của người dùng

1. BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ . CÙ VIỆT DŨNG NÂNG CAO ĐỘ CHÍNH XÁC CỦA TRA CỨU ẢNH THEO NỘI DUNG DỰA TRÊN TIẾP CẬN HỌC ĐA TẠP TỪ THÔNG TIN PHẢN HỒI CỦA NGƯỜI DÙNG Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01 TÓM TẮT LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH Hà Nội – 2023
2. Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học 1: PGS. TS. Nguyễn Hữu Quỳnh Người hướng dẫn khoa học 2: PGS. TS. Ngô Quốc Tạo Phản biện 1: Phản biện 2: Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi giờ ’, ngày tháng năm 202 Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam
3. 1 LỜI MỞ ĐẦU 1. Tính cấp thiết của luận án Tra cứu ảnh dựa vào nội dung (Content base image retrieval - CBIR) đã thu hút nhiều sự quan tâm trong những thập kỷ qua. Nó là thách thức to lớn do khoảng trống giữa các đặc trưng mức thấp và các khái niệm ngữ nghĩa mức cao. Để thu hẹp khoảng trống này, phản hồi liên quan (Relevant feedback - RF) được giới thiệu như một công cụ mạnh để tăng cường hiệu năng của CBIR. Chúng ta thấy rằng, bài toán tra cứu ảnh với phản hồi liên quan có một số vấn đề sau: (1) chỉ khám phá các cấu trúc Euclide toàn cục, hoặc chỉ xem xét cấu trúc cục bộ của các mẫu trong cùng một lân cận; (2) số lượng mẫu thu được từ phản hồi của người dùng thường nhỏ và mất cân bằng giữa hai lớp dương và lớp âm; (3) Chưa quan tâm đến nhiều khía cạnh khác nhau của đối tượng dữ liệu ảnh. Do đó, độ chính xác của các phương pháp tra cứu ảnh sử dụng học máy cho phản hồi thường kém hiệu quả. Do vậy, việc đề xuất phương pháp tra cứu ảnh hiệu quả để giải quyết các hạn chế trên là một nhu cầu cần thiết, chính vì thế mà luận án chọn đề tài “Nâng cao độ chính xác của tra cứu ảnh theo nội dung dựa trên tiếp cận học đa tạp từ thông tin phản hồi của người dùng”. 2. Mục tiêu của luận án Mục tiêu chung của luận án: Nâng cao độ chính xác của tra cứu ảnh dựa trên học đa tạp để giảm chiều từ thông tin phản hồi của người dùng. Mục tiêu cụ thể của luận án: Đề xuất được một số kỹ thuật tra cứu ảnh để nâng cao độ chính xác tra cứu ảnh bao gồm:
4. 2 -Đề xuất phương pháp tìm ma trận chiếu tối ưu theo tiếp cận học đa tạp. -Đề xuất phương pháp tự động bổ sung mẫu dương vào tập huấn luyện, giải quyết vấn đề mất cân bằng của tập huấn luyện. Đồng thời tận dụng các khía cạnh khác nhau của đối tượng để tạo ra một bộ phân lớp mạnh. 3. Các đóng góp của luận án Luận án có các đóng góp sau: (1) Đề xuất phương pháp tìm ma trận chiếu tối ưu theo tiếp cận học đa tạp [CT5]. Phương pháp này xem xét cấu trúc cục bộ của các mẫu dương và âm thuộc hai lân cận khác nhau để học một phép chiếu mà dữ liệu có thể phân biệt trên không gian chiếu, dẫn đến cải tiến độ chính xác cho tra cứu ảnh. (2) Đề xuất phương pháp tự động bổ sung các mẫu dương vào tập huấn luyện để giải quyết vấn đề mất cân bằng tập huấn luyện [CT4]. Phương pháp này có thể: (a) bổ sung một số mẫu dương vào tập huấn luyện; (b) tận dụng các khía cạnh khác nhau của đối tượng để tạo ra một bộ phân lớp mạnh 4. Bố cục của luận án Luận án này được bố cục thành ba chương: Chương 1 giới thiệu tổng quan về tra cứu ảnh dựa vào nội dung. Chương 2 mô tả phương pháp tìm ma trận chiếu tối ưu theo tiếp cận học đa tạp trong tra cứu ảnh, gọi là chiếu phân biệt lớp ngữ nghĩa cho tra cứu ảnh (SCDPIR - Semantic class discriminant projection for image retrieval). Chương 3 trình bày phương pháp cân bằng tập mẫu phản hồi và kết hợp tra cứu ảnh đa khía cạnh. Cuối cùng, luận án đưa ra một số kết luận và định hướng nghiên cứu trong tương lai
5. 3 CHƯƠNG 1. TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG 1.1. Giới thiệu về tra cứu ảnh Nhiệm vụ của hệ thống CBIR sử dụng nội dung trực quan được trích rút tự động thành các đặc trưng nhiều chiều và tìm ra một số hình ảnh tương tự với hình ảnh truy vấn trong cơ sở dữ liệu lớn. Hình 1.1. Sơ đồ tra cứu ảnh dựa vào nội dung truyền thống 1.2. Giới thiệu về phản hồi liên quan 1.2.1. Cơ chế phản hồi liên quan Trong CBIR thường đưa người dùng vào mỗi vòng lặp tra cứu, cơ chế này được gọi là “phản hồi liên quan” (relevant feedback - RF). Hình 1.6. Sơ đồ tra cứu ảnh với phản hồi liên quan
6. 4 1.2.2. Học đa tạp trong tra cứu ảnh dựa vào nội dung Việc học đa tạp với mục tiêu là tạo ra một không gian con nơi các ảnh liên quan được chiếu gần nhau trong khi các ảnh không liên quan được chiếu cách xa nhau bằng cách học cấu trúc cục bộ được hình thành bởi lân cận của ảnh truy vấn và ảnh được phản hồi. Điều này đạt được bằng cách nhúng ảnh truy vấn và tập ảnh phản hồi như tập điểm dữ liệu (các nút) trong đồ thị k láng giềng gần nhất có trọng số. Ánh xạ tối ưu được tìm thấy dựa trên ma trận trọng số trên mỗi cạnh, sao cho các điểm lân cận trong đồ thị được ánh xạ với nhau bằng cách tối thiểu hàm chi phí. Mỗi ảnh cơ sở dữ liệu sau đó cũng được ánh xạ sang không gian chiếu mới, thu được kết quả tra cứu mới là tập hàng xóm gần nhất với ảnh truy vấn. Sau mỗi vòng phản hồi, cấu trúc cục bộ của không gian đa tạp lại được học lại. 1.2.3. Rà soát một số nghiên cứu liên quan Ban đầu, cách tiếp cận tra cứu ảnh với RF giả thiết rằng, tồn tại của một điểm truy vấn lý tưởng mà nếu tìm thấy được sẽ cho kết quả phù hợp với mong muốn của người dùng. Cách tiếp cận này được gọi là “dịch chuyển điểm truy vấn” (QPM - Query Point Movement). Trong RF, các mẫu do người dùng cung cấp thường rất nhỏ so với chiều của đặc trưng, do đó chúng ta phải giải quyết bài toán gọi là “lời nguyền về số chiều - curseof dimensionality”. Khi số chiều đặc trưng quá lớn so với số lượng mẫu trong tập huấn luyện, các mô hình học máy có thể rơi vào tình trạng quá khớp. Để giải quyết vấn đề này, một số tác giả đề xuất các kỹ thuật giảm chiều như phân tích thành phần chính (PCA- Principal Components Analysis) [53, 54] và phân tích phân biệt tuyến tính (LDA - Linear Discriminant Analysis) [55]. Trong những năm gần đây, có nhiều thuật toán học đa tạp để giảm chiều đã được đề xuất để khám phá cấu trúc đa tạp. Có thể kể đến một số phương pháp
7. 5 đa tạp như Locality Preserving Projections, Augmented Relation Embedding, Maximum Margin Projection, Locally Linear Embedding và Laplacian Eigenmaps. Tuy nhiên, các phương pháp này chỉ thực hiện được với các điểm dữ liệu trong tập huấn luyện, và nó không đưa ra rõ ràng phép chiếu có thể thực hiện cho các điểm dữ liệu kiểm tra mới. Bên cạnh đó, các phương pháp này chỉ xem xét tính chất hình học trong một lớp, trong khi bỏ qua mối liên hệ của các mẫu từ các lớp khác nhau. Mặt khác, các phương pháp thường không quan tâm đến các ảnh thuộc lân cận khác nhau mặc dù chúng có thể vẫn liên quan với truy vấn. Do đó, các phương pháp tra cứu ảnh này thường có hiệu quả hạn chế 1.3. Lý thuyết liên quan đến luận án Trong phần này, trình bày tổng quan ngắn gọn về lý thuyết đồ thị, độ đo khoảng cách và máy véc tơ hỗ trợ, nhân Radial Basis Function và sử dụng nó làm cơ sở cho cơ chế phân hạng cho pha phản hồi trong hệ thống đề xuất được giới thiệu trong các chương sau. 1.4. Đánh giá độ chính xác CBIR 1.4.1. Độ chính xác và độ chính xác trung bình Để đánh giá hiệu quả của các hệ thống CBIR, độ chính xác được sử dụng. Độ chính xác (precision) là tỷ lệ của số lượng ảnh liên quan với ảnh truy vấn và số lượng tất cả ảnh được hiển thị hàng đầu trả về gọi là phạm vi (scope) cụ thể K, thường được gọi là P@K. Hiệu quả chính xác tra cứu chung của một hệ thống được đo bằng trung bình tất cả độ chính xác. AP được tính toán như sau: ∑ 푒 푖푠푖표푛(푖) AP = 푖=1 (1.1) N Với 푒 𝑖푠𝑖표푛(𝑖) là độ chính xác của mỗi truy vấn và N là số lượng ảnh được đưa lần lượt làm ảnh truy vấn.
8. 6 1.4.2. Một số tập ảnh dữ liệu dùng cho tra cứu ảnh dựa vào nội dung Tên tập dữ liệu Số chủ đề Số ảnh COREL 80 10800 SIMPLIcity 10 1000 Oxford 11 5062 Caltech 101 101 8742 1.4.3. Kịch bản phản hồi liên quan trong thực nghiệm Trong hệ thống tra cứu ảnh thực tế, một ảnh truy vấn thường không có trong cơ sở dữ liệu ảnh do đó luận án sử dụng bốn phần kiểm chứng chéo để đánh giá các thuật toán. Việc lựa chọn thông tin phản hồi được mô phỏng tự động dựa trên thông tin từ tập tin cậy nền. Với mỗi truy vấn được gửi, hệ thống tra cứu và phân hạng các ảnh trong cơ sở dữ liệu. Tập kết quả khởi tạo gồm K ảnh hàng đầu sau khi phân hạng được lựa chọn làm các ảnh phản hồi. Người dùng tương tác với hệ thống thông qua đánh dấu trong tập kết quả tra cứu khởi tạo các ảnh có cùng chủ đề (cùng khái niệm) với ảnh truy vấn làm ảnh liên quan (mẫu phản hồi dương) và những ảnh còn lại không đánh dấu làm ảnh không liên quan (mẫu phản hồi âm) và lấy thêm K/2 ảnh tiếp theo được xếp hạng ngay sau tập kết quả tra cứu khởi tạo làm mẫu chưa được gán nhãn 1.5. Kết luận chương 1. Trong chương 1, luận án đã trình bày lý thuyết tổng quan về một hệ thống tra cứu ảnh dựa vào nội dung và phản hồi liên quan. Bên cạnh đó, cũng phân tích một số phương pháp phản hồi liên quan nhằm giảm khoảng trống ngữ nghĩa. Qua đó, phân tích, đánh giá ưu nhược điểm một số phương pháp CBIR hiện có để đề xuất một số phương pháp nhằm giải quyết những hạn chế đã phân tích.
9. 7 CHƯƠNG 2. PHƯƠNG PHÁP HỌC CHIẾU PHÂN BIỆT LỚP NGỮ NGHĨA CHO TRA CỨU ẢNH VỚI PHẢN HỒI LIÊN QUAN Trong chương 2 này, luận án sẽ đề xuất phương pháp học chiếu phân biệt lớp ngữ nghĩa cho giảm chiều trong tra cứu ảnh [CT5] để giải quyết hạn chế: số chiều của đặc trưng thường cao hơn rất nhiều so với số mẫu trong tập phản hồi và các mẫu nằm ở hai không gian con (hai lân cận) khác nhau chưa được xét đến. 2.1. Giới thiệu Các hình ảnh trong CBIR được thể hiện bằng vectơ đặc trưng thường có kích thước rất cao từ hàng chục đến hàng trăm trong hầu hết các trường hợp nên gặp phải vấn đề “curse of dimensionality”. Các phương pháp giảm chiều có thể được áp dụng để giải quyết vấn đề đó bằng cách chiếu các điểm không gian chiều cao sang một không gian khác chiều thấp hơn. Các phương pháp không giám sát xử lý dữ liệu không có nhãn, bao gồm phân tích thành phần chính (PCA), chiếu bảo toàn cục bộ (LPP), nhúng tuyến tính cục bộ (LLE), nhúng bảo toàn lân cận (Neighborhood Preserving Embedding - NPE), và Supervised Isomap (S-Isomap). Các phương pháp học có giám sát tiêu biểu gồm phân tích phân biệt tuyến tính (LDA), chiếu bảo toàn cục bộ tối ưu có giám sát (Supervised Optimal Locality Preserving Projection - SoLPP), phân tích lề Fisher (Marginal Fisher Analysis - MFA), nhúng láng giềng phân biệt (discriminant neighborhood embedding - DNE), chiếu phân biệt phân lớp hồi quy tuyến tính (Linear Regression Classification Steered Discriminative Projection - LRCDP), và nhúng đồ thị bảo toàn phân biệt toàn cục và cục bộ (Discriminative Globality And Locality Preserving Graph Embedding - DGLPGE). Các phương pháp bán giám sát tiêu biểu bao gồm nhúng quan hệ gia tăng
10. 8 (Augmented Relation Embedding - ARE), chiếu cực đại lề (Maximum margin projection - MMP), và phân tích phân biệt bán giám sát (Semisupervised Discriminant Analysis - SDA) Các phương pháp kể trên chỉ quan tâm đến nén và tách biệt các điểm thuộc cùng một lân cận mà bỏ qua việc nén và tách biệt các điểm khác lân cận, tức là không đảm bảo các điểm liên quan ngữ nghĩa mà ở các lân cận khác nhau là gần ảnh truy vấn trong không gian con chiều thấp hơn. Bên cạnh đó, các phương pháp nêu trên chỉ thực hiện được với các điểm dữ liệu trong tập huấn luyện, và nó không đưa ra rõ ràng phép chiếu có thể thực hiện cho các điểm thử mới. Do đó, chúng không hiệu quả cho tra cứu ảnh. Để khắc phục vấn đề trên, luận án đề xuất một phương pháp học chiếu phân biệt lớp ngữ nghĩa (Semantic Class Discriminant Projection - SCDP) [CT5]. Trong SCDP, có thể bảo toàn trung thực cấu trúc cục bộ của các điểm dữ liệu trong không gian đặc trưng trực quan nhiều chiều gốc, quan tâm đến cả điểm khác lân cận và tìm một ma trận chiếu tốt cho chúng. 2.2. Nghiên cứu liên quan Trong phần này, rà soát ngắn gọn DNE, ARE, MMP, và DAG- DNE, chúng là cơ sở cho phương pháp đề xuất. 2.3. Đề xuất phương pháp học chiếu phân biệt lớp ngữ nghĩa trên dữ liệu đa tạp Xây dựng hàm mục tiêu 푛 Cho một tập 퐱1, 퐱2, 퐱 trong ℝ , tìm một ma trận biến đổi 퐔 = (퐮1, 퐮2, , 퐮 ) mà ánh xạ điểm này thành một tập 퐲1, 퐲2, 퐲 trong ℝ ( ≪ 푛) sao cho 퐲푖 biểu diễn 퐱푖, ở đây 퐲푖 = 퐔 퐱푖 Cho ℚ ⊂ ℝ푛 là một không gian đặc trưng ảnh 푛 chiều, và 𝜎: ℚ × ℚ → ℝ là một hàm khoảng cách nào đó. Cho ma trận 퐗 =
11. 9 푛× [퐱1, 퐱2, 퐱 ] ∈ ℝ biểu diễn ảnh trong tập ảnh và điểm dữ liệu {퐱1, 퐱2, 퐱N} được lấy mẫu từ đa tạp con cơ bản . Giả sử rằng chúng ta có 1 điểm được gán nhãn, và 2 điểm còn lại là chưa có nhãn, ở đây 1 + 2 = . Để mô hình cấu trúc hình học cục bộ của , đầu tiên chúng ta xây dựng một đồ thị quan hệ đặc trưng G퐹. Với mỗi điểm dữ liệu 퐱i, chúng ta tìm lân cận gần nhất của nó và đặt một 푭 × cạnh giữa 퐱i và các lân cận của nó thu được ma trận 퐖 ∈ ℝ , được xác định như sau: 𝜌2(퐱 ,퐱 ) − 푖 푗 푒 휏 , nếu 퐱 ∈ − (퐱 ) 퐹 푖 푗 푤푖푗 = (2.1) hoặc 퐱푗 ∈ − (퐱푖) { 0, ngược lại; 2 ở đây 𝜌 (퐱푖, 퐱푗) là độ đo khoảng cách Euclide (퐿2), 휏 là một số vô hướng dương nào đó, và − là ký hiệu cho lân cận cận gần nhất. Với phản hồi liên quan, tôi sử dụng IR để biểu thị tập các ảnh không liên quan đến ảnh truy vấn, R gồm các ảnh liên quan đến ảnh truy vấn và tập UL gồm các ảnh chưa có nhãn. Để khám phá cả thông tin phân biệt và hình học của đa tạp dữ liệu, xây dựng hai đồ thị quan hệ tương tự liên quan 푅 và không tương tự G 푅. Các ma trận trọng số 퐖푹 ∈ ℝ × và 퐖푰푹 ∈ ℝ × của G푅 và G 푅 tương ứng được định nghĩa như sau: 퐹 퐹 훼, nếu (푤푖푗 > 0 ∧ 푤푖푗 ≤ 1) ∧ (퐱푖 ∈ 퐑 ∧ 퐱푗 ∈ 퐑) 퐹 퐹 푅 1, nếu (푤 > 0 ∧ 푤 ≤ 1) ∧ (퐱푖 ∈ 퐔퐋 ∧ 퐱푗 ∈ 퐔퐋) 푤푖푗 = 푖푗 푖푗 (2.2) 0, ngược lại; { 퐹 퐹 1, nếu (푤푖푗 > 0 ∧ 푤푖푗 ≤ 1) ∧ (퐱푖 ∈ 퐑 ∧ 퐱푗 ∈ 퐈퐑) 푅 퐹 퐹 푤푖푗 = { hoặc (푤푖푗 > 0 ∧ 푤푖푗 ≤ 1) ∧ (퐱푖 ∈ 퐈퐑 ∧ 퐱푗 ∈ 퐑) (2.3) 0, ngược lại;
12. 10 Trong (2.2), khi hai ảnh i và j thuộc cùng một lân cận và cùng nhãn dương, chúng nên nhận một giá trị trọng số cao 훼. Chúng ta xác định ma trận 퐒_퐒 ∈ ℝ × lưu trữ thông tin giống nhau về ngữ nghĩa liên quan với truy vấn giữa hai mẫu 퐱푖 và 퐱푗 (lưu ý rằng hai mẫu 퐱푖 và 퐱푗 không cần thiết thuộc cùng một lân cận): 1, nếu 퐱 ∈ R ∧ 퐱 ∈ R 푠_푠 = { 푖 푗 (2.4) 푖푗 0, ngược lại; Cho 퐔 là một chiếu mà ánh xạ một mẫu x푖 trong không gian gốc thành một mẫu tương ứng 퐲푖 trong một không gian chiều thấp hơn. 퐲푖 = 퐔 퐱푖 (2.5) Hiển nhiên trong lân cận cục bộ của một mẫu 퐱푖, trung bình của các mẫu thuộc cùng lân cận và cùng nhãn được tính như sau: 푅 퐦푖 = ∑푗 퐱푗푤푖푗 (2.6) Sau khi chiếu, trung bình của các mẫu thuộc cùng lân cận và cùng nhãn có thể được tính từ (2.6) và (2.7) (퐲) 푅 퐦푖 = ∑푗 퐲푗푤푖푗 (2.7) Một tiêu chuẩn cho chọn một ánh xạ tốt là tối ưu hai hàm mục tiêu dưới các ràng buộc thích hợp. 2 2 푅 (퐲) (퐲) min퐔 ∑푖푗(‖퐲푖 − 퐲푗‖ 푤푖푗 + ‖퐦푖 − 퐦푗 ‖ 푠_푠푖푗) (2.8) 2 2 푅 (풚) (풚) 푼 ∑푖푗(‖풚푖 − 풚푗‖ 푤푖푗 + ‖ 푖 − 푗 ‖ (1 − 푠_푠푖푗)) (2.9) Phép chiếu tối ưu Bài toán (2.8) được viết lại như sau: 𝑔 𝑖푛퐔T퐔=퐈 푡 푒(퐔 퐂퐔) (2.10) trong đó 퐂 = 퐂퐱 + 퐂퐦 tương ứng trong 풔_풔 Bài toán tối ưu (2.9) có thể viết lại như sau: 𝑔 퐔 퐔=퐈 푡 푒(퐔 퐁퐔) (2.11) 푰푹 trong đó 퐁 = 퐁퐱+ 퐦, tương ứng trong 풘
13. 11 Từ hàm mục tiêu (2.11) và (2.12), vấn đề tìm phép chiếu 퐲 = 퐔 퐱 sẽ được đưa về bài toán tối ưu sau: 푡 푒(퐔 퐁퐔) 퐔 = 𝑔 (2.12) 퐔 푡 푒(퐔 퐂퐔) Vậy ma trận 퐔 = (퐮1, 퐮2, , 퐮 ) gồm véc tơ lớn nhất tương ứng −1 với các trị riêng ∧= 𝑖 𝑔 (휆1, 휆2, , 휆 ) của ma trận (퐂 . 퐁) với điều kiện 퐂 khả nghịch. Do đó, để nhúng một ảnh truy vấn 퐪(x) ∈ ℚ, chúng ta ánh xạ nó vào đa tạp bởi 퐪(퐲) = 퐔푻퐪(x). Tìm các điểm lân cận của 퐪(퐲) sử dụng khoảng cách Euclide, và phân hạng ở đỉnh trong danh sách trả về. Thuật toán 2.1. Thuật toán chiếu phân biệt lớp ngữ nghĩa (SCDP). 푛 Input: 퐗 = {퐱1, 퐱2, 퐱 } ∈ ℝ gồm N ảnh với R, IR, UL ⊂X, R : tập ảnh có nhãn dương, IR: tập ảnh có nhãn âm, UL: tập ảnh không có nhãn, d: số chiều không gian chiếu và k, α: các tham số. Output: Ma trận chiếu 퐔 = (퐮1, 퐮2, , 퐮 ) 𝜎2(퐱 ,퐱 ) − 푖 푗 푒 휏 , nếu 퐱 ∈ − (퐱 ) 퐹 푖 푗 Bước 1: 푤푖푗 hoặc 퐱푗 ∈ − (퐱푖) { 0, ngược lại; Bước 2: 퐹 퐹 훼, nếu (푤푖푗 > 0 ∧ 푤푖푗 ≤ 1) ∧ (퐱푖 ∈ 퐑 ∧ 퐱푗 ∈ 퐑) 푅 퐹 퐹 푤푖푗 {1, nếu (푤푖푗 > 0 ∧ 푤푖푗 ≤ 1) ∧ (퐱푖 ∈ 퐔퐋 ∧ 퐱푗 ∈ 퐔퐋) 0, ngược lại; 퐹 퐹 1, nếu (푤푖푗 > 0 ∧ 푤푖푗 ≤ 1) ∧ (퐱푖 ∈ 퐑 ∧ 퐱푗 ∈ 퐈퐑) 푅 퐹 퐹 푤푖푗  { hoặc (푤푖푗 > 0 ∧ 푤푖푗 ≤ 1) ∧ (퐱푖 ∈ 퐈퐑 ∧ 퐱푗 ∈ 퐑) 0, ngược lại; 1, if 퐱 ∈ 퐑 ∧ 퐱 ∈ 퐑 푠_푠  { 푖 푗 푖푗 0, ngược lại;
14. 12 Bước 3: 푅 퐁 (퐱푖 − 퐱푗)(퐱푖 − 퐱푗) + (퐦푖 − 퐦푗)(퐦푖 − 퐦푗) với 퐱푖, 퐱푗 ∈ 푤푖푗 푅 và 퐦푖 = ∑푗 퐱푗푤푖푗 푅 퐂(퐱푖 − 퐱푗)(퐱푖 − 퐱푗) + (퐦푖 − 퐦푗)(퐦푖 − 퐦푗) với 퐱푖, 퐱푗 ∈ 푤푖푗 푅 và 퐦푖 = ∑푗 퐱푗푤푖푗 푡 푒(퐔 퐁퐔) Bước 4: U= 𝑔 với (퐔 퐂퐔) = 퐈 푼 푡 푒(퐔 퐂퐔) 퐔 = (퐮1, 퐮2, , 퐮 ) với mỗi cột là véc tơ riêng tương ứng với các trị riêng 휆1 > 휆2 > ⋯ > 휆 . Độ phức tạp của thuật toán SCDP là ((푛 + )푛2 trong đó n là số đặc trưng, d là số chiều trong không gian chiếu 2.4. Tra cứu ảnh với học chiếu phân biệt lớp ngữ nghĩa Thuật toán 2.2. Tra cứu ảnh với học chiếu phân biệt lớp ngữ nghĩa (SCDPIR). Input: 퐃퐁: Tập ảnh dữ liệu, q: Ảnh truy vấn khởi tạo, N: Số lượng ảnh trả về tại mỗi lần lặp, d: số chiều không gian chiếu Output: S: Tập ảnh kết quả Bước 1: X Retrieval-Init(q, DB, N>; Bước 2: Repeat Bước 2.1: IRFeedback(퐗, −1); Bước 2.2 RFeedback(퐗, 1); Bước 2.3 퐔퐋퐗 − (퐈퐑 ∪ 퐑)
15. 13 Bước 2.4 퐔SCDP( 퐗, 퐑, 퐈퐑, , , 훼); Bước2.5 퐃퐁(퐲)푴 풑풑풊풏품(퐃퐁, 퐔); 퐪(퐲)푴 풑풑풊풏품(퐪, 퐔) Bước 2.6 퐒Retrieval ; until (Người dùng dừng phản hồi); Bước 3. Return S; Độ phức tạp là (푙 + (n + d)n2) trong đó 푙 là số ảnh, n là số chiều của không gian đặc trưng gốc và d là số chiều của không gian chiếu. 2.5. Đánh giá hiệu năng tra cứu ảnh với học chiếu phân biệt lớp ngữ nghĩa u năng tra cứu ảnh 2.5.1. Độ chính xác tra cứu ảnh So sánh độ chính xác của thuật toán tra cứu ảnh đề xuất với baseline, MMP, DSSA và DAG-DNE dùng tham số =12, 훼 = 50. Kết quả của tập ảnh dữ liệu Corel Hình 2.8. Độ chính xác 5 phương pháp ở top 20 ảnh trả về
16. 14 a) lần lặp phản hồi thứ nhất (b) lần lặp phản hồi thứ hai Hình 2.9. Các đường cong precision-scope trung bình của các thuật toán khác nhau cho hai lần lặp đầu tiên. Kết quả của tập dữ liệu ảnh SIMPLIcity Với tập Corel 10K8 cho ta thấy hiệu năng của phương pháp đề xuất đã cải thiện đáng kể, nhưng để trực quan hóa phép chiếu phương pháp đề xuất tập Corel không tối ưu vì số lượng ảnh quá nhiều. Do đó trong phần này, các thực nghiệm được thực hiện trên tập dữ liệu ảnh
17. 15 SIMPLIcity có 1000 ảnh để trình bày việc trực quan hóa kết quả của bốn phương pháp MMP, DSSA, DAG-DNE và SCDPIR 2.5.2. Chiều của không gian chiếu phân biệt lớp ngữ nghĩa (a) Chiều của không gian (SCDP) (b) Chiều của không gian (MMP) (c) Chiều không gian(DAG-DNE) (d) Chiều không gian (DSSA) Hình 2.11. Hiệu năng của bốn phương pháp theo số chiều Chúng ta thấy rằng hiệu năng của MMP luôn nhận được hiệu năng tốt nhất tại hai chiều (Hình 2.11 (b)), hiệu năng của SCDP luôn có hiệu năng tốt nhất tại sáu chiều (Hình 2.11 (a)), DSSA đạt hiệu năng tốt nhất tại số chiều rất lớn là 8 chiều (Hình 2.11 (d)), và DAG-DNE đạt hiệu năng tốt nhất tại số chiều rất lớn là 12 chiều (Hình 2.11 (c)). Như vậy, số chiều chiếu tối ưu của SCDPIR cao hơn của MMP nhưng thấp hơn của DAG-DNE và DSSA. Nhưng, hiệu suất của SCDPIR cao hơn nhiều so với MMP khi nó ở số chiều tương đối thấp và điều này có thể
18. 16 chấp nhận được trong các ứng dụng thực tế. Ngoài ra, với thuật toán DAG-DNE, hiệu năng đạt được tốt nhất với số chiều tương đối lớn cao và nó sẽ bị vấn đề quá khớp khi áp dụng trong các ứng dụng tại thế giới thực 2.6. Kết luận chương 2 Trong chương này, luận án trình bày phương pháp SCDP có thể khám phá được cấu trúc phi tuyến của dữ liệu trên không gian gốc để tìm được ma trận chiếu. Bên cạnh đó, trong chương 2 đã đánh giá thực nghiệm trên hai tập dữ liệu Corel 10K8 và SIMPLIcity đã thể hiện độ chính xác của phương pháp đề xuất đã được cải thiện và đáng tin cậy
19. 17 CHƯƠNG 3. CÂN BẰNG TẬP MẪU PHẢN HỒI VÀ KẾT HỢP TRA CỨU ẢNH ĐA KHÍA CẠNH 3.1. Giới thiệu Các bài toán phản hồi liên quan rất khác so với bài toán phân lớp truyền thống bởi vì các phản hồi được cung cấp bởi người dùng thường bị giới hạn trong các hệ thống tra cứu ảnh thực. Do đó, các phương pháp học mẫu nhỏ là hứa hẹn cho RF. Tuy nhiên, hầu hết các cách tiếp cận không quan tâm đến những ảnh chưa được gán nhãn dương hoặc âm dù chúng rất là hữu ích cho quá trình học phản hồi hay giảm chiều để nâng cao độ chính xác tra cứu. Bên cạnh đó, chúng còn bỏ qua sự cân bằng số mẫu dương và âm trong tập phản hồi. Trong chương 3, đề xuất một phương pháp cân bằng tập mẫu phản hồi và kết hợp tra cứu ảnh đa khía cạnh (CIR) [CT4] thực hiện (a) bổ sung một số mẫu dương nhằm xây dựng tập mẫu cân bằng (BSFG - balanced sample feedback based on the graph); (b) tận dụng thông tin hình học trong việc giảm chiều hiệu quả (SCDP) (đã trình bày trong chương 2); (c) tận dụng các khía cạnh của đối tượng để xây dựng bộ phân lớp mạnh (CMAC). 3.2. Kỹ thuật cân bằng tập mẫu phản hồi sử dụng học bán giám sát đồ thị Cho đồ thị lân cận gần nhất G = (X, S) là một đồ thị vô hướng với 푛 tập đỉnh X = {x1, x2, x } ∈ 푅 . N đỉnh (ảnh) này là kết quả của việc thực hiện truy vấn trước đấy. Giả sử rằng đồ thị G được đánh trọng số, tức là mỗi cạnh giữa hai đỉnh x푖 và x푗 mang một trọng số không âm s푖푗 ≥ 0. Ma trận kề có trọng số của đồ thị là ma trận 푆 = (푠푖푗)푖,푗=1, .
20. 18 Gọi (x푖) là lân cận gần nhất của điểm x푖. Nếu x푖 ∈ (x푗) (hoặc x푗 ∈ (x푖)), s푖푗 = 1. Ngược lại, s푖푗 = 0. Do G là vô hướng chúng ta yêu cầu s푖푗 = s푗푖. Giả sử có điểm đã được người dùng gán nhãn (bao gồm cả ảnh 푛 truy vấn gốc) 퐿 = {x1, x2, x } ∈ 푅 và − điểm chưa được 푛 người dùng gán nhãn 푈 = {x − +1, x − +2, x − } ∈ 푅 . Để phục cho việc xác định điểm x푖, nơi mà lớp dương có mật độ cao xung quanh điểm đó, xây dựng đồ thị 푙 푒푙. Đồ thị 푙 푒푙 có các đỉnh giống như các đỉnh của đồ thị và có 푙 푒푙 ma trận trọng số 푆 . Cho 푙 푒푙(x푖) là nhãn của điểm x푖 (nhãn này hoặc là liên quan hoặc là không liên quan). Với mỗi điểm x푖, tập 푙 푒푙 (x푖) bao gồm các điểm lân cận của x푖 mà có cùng nhãn với x푖 hoặc chưa có nhãn. Lý do của việc này là chúng ta xem những điểm đủ gần với x푖 dường như là có liên quan đến x푖. Cụ thể: 푙 푒푙 (x푖) = {x| 푙 푒푙(x) == 푙 푒푙(x푖) ℎ표ặ x ∈ 푈 } (3.1) Chúng ta xác định 푆푙 푒푙 là ma trận trọng số của 푙 푒푙 như sau: 훽 , nếu 푙 푒푙(x ) == 푙 푒푙(x ) 푖 푗 푙 푒푙 푙 푒푙 1, nếu x푖 và x푗 ∈ 푈 nhưng x푖 ∈ (x푗) 푠푖푗 = (3.2) ℎ표ặ x ∈ 푙 푒푙(x ) 푗 푖 {0, ngược lại Trong (3.2), giá trị 훽 cao hàm ý hai ảnh có cùng nhãn và do đó có cùng ngữ nghĩa. 푙 푒푙 Trên đồ thị , bậc của đỉnh x푖 ∈ được xác định bằng: 푙 푒푙 푙 푒푙 푖 = ∑푗=1 푠푖푗 (3.3) Với mỗi điểm chưa được gán nhãn x푖 ∈ 푈 , tìm điểm có bậc 푙 푒푙 푙 푒푙 푖 cao nhất trong số các điểm thuộc lân cận (x푖) và lấy nhãn của điểm đó làm nhãn tạm thời của x푖. Cụ thể: Nhãn tạm thời của ∗ ∗ x푖 sẽ được gán là nhãn của x với x được xác định như sau:
21. 19 ∗ 푙 푒푙 x = argmax ( 푗 ) (3.4) 푙 푒푙 x푗∈ (x푖) Thủ tục xác định nhãn tạm thời này được minh họa trên Hình 3.5. Hình 3.5. Minh họa xác định nhãn tạm thời Ý tưởng để xác định nhãn cuối cùng của một điểm x푖 như sau. Đầu tiên, phân hoạch đồ thị theo Ncut thành hai lớp: lớp âm và lớp dương. Sau đó, kiểm tra xem điểm x푖 thuộc lớp nào Hình 3.6. Đồ thị 푙 푒푙 được phân chia theo tiêu chí Ncut. Hiệu năng của BSFG Hình 3.7. Độ chính xác của ba phương pháp O-SVM, SVM- MSMOTE, và SVM-BSFG.
22. 20 3.3. Kỹ thuật kết hợp các bộ phân lớp theo khía cạnh Vấn đề cân bằng mẫu đã giải quyết được thông qua học bán giám sát dựa vào đồ thị. Tuy nhiên, nó chưa khám phá được thuộc tính thống kê cho phân lớp dữ liệu. Với nhận định rằng, không có một bộ phân lớp nào có thể biểu diễn được tất cả các khía cạnh hữu ích của dữ liệu đầu vào. Với các khía cạnh khác nhau của một mẫu đang xét, các bộ phân lớp này có thể được huấn luyện độc lập trên tập mẫu theo khía cạnh đã có nhãn. Các bộ phân lớp con có thể được tổ hợp thành một bộ phân lớp mạnh theo kỹ thuật bầu cử đa số. Trong luận án, một khía cạnh được xác định là một đặc trưng: màu, hình dạng hoặc kết cấu. Bài toán được phát biểu thành thuật toán tổ hợp các bộ phân lớp theo khía cạnh (Combine Multiple Aspect Classiers - CMAC). Thuật toán 3.2 Thuật toán kết hợp bộ phân lớp theo khía cạnh (CMAC) Input: reduced_Aspect푖, i = 1, , k : Các tập mẫu theo khía cạnh đã giảm chiều: Output: 훽: Bộ phân lớp được kết hợp: Bước 1: For i=1, , k 푖  Aspect Classifiers (reduced_Aspect푖); Bước 2: 훽( ) = argmax ∑ 훿 푠 푛( 푖( )), ∈{−1, 1} Hiệu năng của CMAC Hình 3.8. Độ chính xác của O-SVM và SVM-CMAC
23. 21 3.4. Phương pháp tra cứu ảnh kết hợp chiếu phân biệt lớp ngữ nghĩa đa khía cạnh. Hình 3.9. Sơ đồ tra phương pháp tra cứu ảnh kết hợp chiếu phân biệt lớp ngữ nghĩa đa khía cạnh
24. 22 3.5. Đánh giá độ chính xác của phương pháp CIR 0.6 0.5 0.4 O-SVM 0.3 HMR 0.2 DMINTIR Độ chínhxác 0.1 DSSA 0 CIR 1 2 3 4 5 Số lần lặp Hình 3.10. Độ chính xác của năm phương pháp 3.6. Kết luận chương 3 Trong luận án đã đề xuất phương pháp CIR nâng cao độ chính xác của hệ thống tra cứu sử dụng RF có thể: (1) tận dụng được thông tin của các mẫu chưa có nhãn; (2) khai thác được cấu trúc phi tuyến của dữ liệu đa tạp và (3) tận dụng được các khía cạnh hữu ích khác nhau của đối tượng. Các kết quả thực nghiệm trên tập dữ liệu ảnh ảnh Corel đã chỉ ra rằng phương pháp đề xuất đã cải tiến đáng kể độ chính xác tra cứu
25. 23 KẾT LUẬN Độ chính xác của một hệ thống tra cứu ảnh dựa vào nội dung đã và đang được cộng đồng nghiên cứu quan tâm cải tiến. Nhiều phương pháp đã được đề xuất trong thời gian qua. Tuy nhiên, sự chênh lệch giữa đặc trưng mức thấp của ảnh và cảm nhận trực quan từ người dùng về nội dung ảnh làm cho độ chính xác của hệ thống tra cứu ảnh vẫn còn khoảng cách với nhu cầu của người dùng. Các đóng góp chính trong luận án này cũng theo định hướng sử dụng cơ chế phản hồi liên quan để thu hẹp sự chênh lệch khoảng cách này. Luận án đã có các đóng góp sau: (1) Đề xuất phương pháp tìm ma trận chiếu tối ưu theo tiếp cận học đa tạp [CT5]. Phương pháp này xem xét cấu trúc cục bộ của các mẫu dương và âm thuộc hai lân cận khác nhau để học một phép chiếu mà dữ liệu có thể phân biệt trên không gian chiếu, dẫn đến cải tiến độ chính xác cho tra cứu ảnh. (2) Đề xuất phương pháp tự động bổ sung các mẫu dương vào tập huấn luyện để giải quyết vấn đề mất cân bằng tập huấn luyện [CT4]. Phương pháp này có thể: (a) bổ sung một số mẫu dương vào tập huấn luyện; (b) tận dụng các khía cạnh khác nhau của đối tượng để tạo ra một bộ phân lớp mạnh Một số vấn đề cần được nghiên cứu tiếp trong tương lai: - Nghiên cứu mạng nơ ron tích chập để nâng cao độ chính xác tra cứu trên tập ảnh lớn hơn. - Nghiên cứu áp dụng cơ chế băm sâu để nâng cao tốc độ tra cứu. - Từng bước tiến đến việc đưa hệ thống vào áp dụng một số lĩnh vực trong cuộc sống.
26. 24 NHỮNG ĐÓNG GÓP MỚI CỦA LUẬN ÁN Nhằm mục tiêu nâng cao độ chính xác của tra cứu ảnh sử dụng học máy để giảm chiều từ thông tin phản hồi của người dùng, luận án có các đóng góp sau: (1) Đề xuất phương pháp tìm ma trận chiếu tối ưu theo tiếp cận học đa tạp [CT5]. Phương pháp này xem xét cấu trúc cục bộ của các mẫu dương và âm thuộc hai lân cận khác nhau để tìm phép chiếu, đảm bảo tính phân biệt trên không gian chiếu, đồng thời cải tiến độ chính xác tra cứu ảnh. (2) Đề xuất phương pháp tự động bổ sung mẫu dương vào tập huấn luyện, giải quyết vấn đề mất cân bằng của tập huấn luyện [CT4]. Phương pháp này bổ sung các mẫu dương vào tập huấn luyện đồng thời tận dụng các khía cạnh khác nhau của đối tượng để tạo ra một bộ phân lớp mạnh.
27. DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ Trong nước: [CT1] Cù Việt Dũng, Nguyễn Hữu Quỳnh, An Hồng Sơn, Đào Thị Thúy Quỳnh, Cải tiến tra cứu ảnh thông qua kết hợp các bộ phân lớp không gian con ngẫu nhiên, 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, 2018, 72- 78 [CT2] Cù Việt Dũng, Nguyễn Hữu Quỳnh, Ngô Quốc Tạo, Trần Thị Minh Thu, Một phương pháp tra cứu ảnh học biểu diễn và học đa tạp cho giảm chiều với thông tin từ người dùng, 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, 2019, 307-314 [CT3] Cù Việt Dũng, An Hồng Sơn, Nguyễn Hữu Quỳnh, Ngô Quốc Tạo, Đào Thị Thúy Quỳnh, Phương pháp học bán giám sát dựa vào đồ thị xây dựng tập mẫu cân bằng cho tra cứu ả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, 2021, 143-149 Quốc tế: [CT4] Nguyen Huu Quynh, Cu Viet Dung, Dao Thi Thuy Quynh, Ngo Quoc Tao, Phuong Van Canh, Graph-based semisupervised and manifold learning for image retrieval with SVM-based relevant feedback, Journal of Intelligent & Fuzzy Systems(SCIE,IF=1.637), 2019, 37, 711–722 [CT5] Nguyen Huu Quynh, Cu Viet Dung, Dao Thi Thuy Quynh, (2021), Semantic class discriminant projection for image retrieval with relevance feedback. Multimedia Tools and Applications (SCIE, IF = 2.313, Q1), 2021, 80, 15351–15376