Tóm tắt luận án Tiến sĩ Công nghệ thông tin: Nâng cao độ chính xác tra cứu ảnh dựa vào nội dung sử dụng kỹ thuật điều chỉnh trọng số của hàm khoảng cách

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

Thêm vào BST

Báo xấu

28
lượt xem 5
download

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

Luận án nghiên cứu đề xuất một số phương pháp tra cứu ảnh nhằm nâng cao độ chính xác tra cứu. Các phương pháp này sẽ hướng tới giải quyết các vấn đề về giảm khoảng cách ngữ nghĩa giữa đặc trưng mức thấp và khái niệm mức cao của ảnh.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận án Tiến sĩ Công nghệ thông tin: Nâng cao độ chính xác tra cứu ảnh dựa vào nội dung sử dụng kỹ thuật điều chỉnh trọng số của hàm khoảng cách

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… ĐÀO THỊ THÚY QUỲNH NÂNG CAO ĐỘ CHÍNH XÁC TRA CỨU ẢNH DỰA VÀO NỘI DUNG SỬ DỤNG KỸ THUẬT ĐIỀU CHỈNH TRỌNG SỐ CỦA HÀM KHOẢNG CÁCH 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Ĩ CÔNG NGHỆ THÔNG TIN Hà Nội – 2019
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. Ngô Quốc Tạo Ngƣời hƣớng dẫn khoa học 2: PGS.TS. Nguyễn Hữu Quỳnh Phản biện 1: Phản biện 2: Phản biện 3: 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 … 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
MỞ ĐẦU 1. Tính cấp thiết của luận án Cơ sở dữ liệu ảnh ngày càng trở nên phổ biến trong các lĩnh vực ứng dụng khác nhau như viễn thám, phòng chống tội phạm, y học,… Sự tiến triển của các kỹ thuật thu, truyền và lưu trữ ảnh đã cho phép xây dựng các cơ sở dữ liệu ảnh rất lớn. Các nhân tố này đã thúc đẩy sự quan tâm nghiên cứu các phương pháp khai thác hiệu quả cơ sở dữ liệu ảnh này. Các kỹ thuật tra cứu ảnh dựa vào văn bản mô tả ảnh tốn nhiều thời gian, chi phí cao và phụ thuộc vào cảm nhận chủ quan của chuyên viên kỹ thuật. Hơn nữa, hệ thống dựa vào từ khoá rất khó thay đổi về sau này. Để khắc phục khó khăn này, tra cứu ảnh dựa vào nội dung (Content-based image retrieval-CBIR) đã ra đời vào đầu những năm 90. Ý tưởng cơ bản của cách tiếp cận này là sử dụng kỹ thuật trích rút đặc trưng trực quan một cách tự động để cho ra các mô tả nội dung từ ảnh như đặc trưng màu sắc, kết cấu, và hình dạng làm chỉ số ảnh. Có nhiều hệ thống tra cứu ảnh dựa vào nội dung đã được đề xuất. Tuy nhiên, nhiều thực nghiệm trên các hệ thống CBIR chỉ ra rằng các nội dung mức thấp thường thất bại trong mô tả các khái niệm ngữ nghĩa mức cao trong ý nghĩ của người dùng. Do đó, hiệu năng của hệ thống CBIR vẫn còn xa so với các kỳ vọng của người dùng. Do đó, luận án chọn đề tài “Nâng cao độ chính xác tra cứu ảnh dựa vào nội dung sử dụng kỹ thuật điều chỉnh trọng số của hàm khoảng cách” để góp phần giải quyết các vấn đề đặt ra. 2. Mục tiêu của luận án Luận án nghiên cứu đề xuất một số phương pháp tra cứu ảnh nhằm nâng cao độ chính xác tra cứu. Các phương pháp này sẽ hướng tới giải quyết các vấn đề về giảm khoảng cách ngữ nghĩa giữa đặc trưng mức thấp và khái niệm mức cao của ảnh. 3. Các đóng góp của luận án Đề xuất phương pháp SRIR (Semantic–Related Image Retrieval method) và phương pháp AWEIGHT (An efficient image retrieval method using adaptive weights). 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 trình bày phương pháp tra cứu ảnh liên quan ngữ nghĩa được tác giả đề xuất, có tên là SRIR. Chương 3 trình bày phương pháp tra cứu ảnh sử dụng trọng số thích nghi được tác giả đề xuất, có tên là AWEIGHT. 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. 1
Chƣơng 1. TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG 1.1. Giới thiệu Các dạng nguồn đa phương tiện khác nhau đang tăng lên nhanh chóng, chẳng hạn dữ liệu trực quan trong các điện thoại thông minh, các ứng dụng 2D/3D, nội dung web,... Do đó, nhu cầu về các dịch vụ ảnh trở nên quan trọng hơn bao giờ hết. Tuy nhiên, phương tiện trực quan yêu cầu một lượng xử lý và lưu trữ đáng kể, cần có các phương pháp hiệu quả để đánh chỉ số, lưu trữ, phân tích và tra cứu thông tin trực quan từ các cơ sở dữ liệu ảnh. Do đó, tra cứu các ảnh nhanh, chính xác và hiệu quả cho các loại tập ảnh trở thành một trong những nhiệm vụ thách thức. 1.1.1. Tra cứu ảnh dựa vào văn bản Cách tiếp cận ban đầu cho tra cứu ảnh là dựa vào văn bản, trong đó các ảnh được đánh chỉ số bằng các từ khóa, chủ đề hoặc mã phân loại. Các từ khóa, chủ đề hoặc mã phân loại này được sử dụng trong quá trình tra cứu. Tuy nhiên, với các cơ sở dữ liệu ảnh lớn, các khó khăn phải đối mặt của cách tiếp cận tra cứu dựa vào văn bản ngày càng trở nên nghiêm trọng hơn và quá trình này tốn nhiều nhân lực và thời gian. Để khắc phục các vấn đề này, các nội dung của ảnh (gồm mầu, kết cấu và hình dạng) được trích rút tự động từ bản thân các ảnh đã được sử dụng cho tra cứu ảnh. 1.1.2. Tra cứu ảnh dựa vào nội dung Trong tra cứu ảnh dựa vào nội dung, các ảnh có thể được tra cứu thông qua các đặc trưng mức thấp (tức là màu, hình dạng, và kết cấu) hoặc sử dụng các đặc trưng ngữ nghĩa mức cao hay các đặc trưng ngữ nghĩa. Hình 1.1. Minh họa khoảng cách ngữ nghĩa. Kiến trúc hệ thống tra cứu ảnh dựa vào đặc trưng thị giác được chỉ ra như Hình 1.2. Trích rút đặc trưng Cơ sở dữ liệu Tập ảnh đặc trưng Độ tương tự Kết quả tra cứu Sắp xếp Đầu ra Trích rút đặc trưng Véc tơ Ảnh truy vấn đặc trưng Hình 1.2. Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung. 2
Hình 1.3 chỉ ra cơ chế hoạt động của phản hồi liên quan trong CBIR. Khi có kết quả tra cứu khởi tạo, người dùng chọn các ảnh liên quan trong danh sách kết quả này để làm các mẫu có nhãn (dương hay âm). Dựa trên tập mẫu huấn luyện này, một thuật toán máy học được thực hiện để điều chỉnh các tham số. Dựa trên các tham số vừa được học, tra cứu ảnh được thực hiện. Quá trình tra cứu được lặp lại cho đến khi người dùng thỏa mãn. Hình 1.3: Sơ đồ phản hồi liên quan. 1.1.3. Một số nghiên cứu về tra cứu ảnh dựa vào nội dung Một số phương pháp tra cứu ảnh dựa vào nội dung đã được đưa ra, chẳng hạn: VisualSeek, SIMPLicity, Blobwworld, WebSeek, Image Rover…. 1.2.Trích rút đặc trƣng, 1.2.1. Đặc trƣng màu Đặc trưng màu được sử dụng rất hiệu quả cho tra cứu các ảnh màu trong cơ sở dữ liệu ảnh. Các mô tả màu được trích rút và so sánh thuận lợi, do đó đặc trưng màu thích hợp cho tra cứu ảnh dựa vào đặc trưng trực quan. 1.2.2. Đặc trƣng kết cấu Kết cấu ảnh là một đặc trưng ảnh quan trọng để mô tả các thuộc tính bề mặt của một đối tượng và mối quan hệ của nó với các vùng xung quanh. 1.2.3. Đặc trƣng hình Đặc trưng hình dạng ảnh mang thông tin ngữ nghĩa và có thể được phân thành hai loại: dựa trên đường bao và dựa trên vùng. 3
1.2.4. Thông tin không gian Thông tin không gian biểu thị vị trí không gian tuyệt đối và vị trí không gian tương đối của các vùng. Các vùng hoặc đối tượng với các đặc trưng màu tương tự có thể được phân biệt tốt hơn bằng việc tận dụng các thông tin không gian. 1.3. Đo khoảng cách Việc lựa chọn xác định loại độ đo khoảng cách mà sử dụng để so sánh độ tương tự của từng cặp ảnh còn phụ thuộc vào cấu trúc của các véc tơ đặc trưng mô tả chúng. Một số độ đo tương tự được sử dụng phổ biến nhất: Khoảng cách Minkowski, Mahalanobis, Cosine, Hamming, Earth Mover … 1.4. Phân cụm Tiếp nối quá trình biểu diễn và trích rút đặc trưng, các phương pháp phân cụm nhằm nhóm các mô tả ảnh thành các cụm khác nhau với các ngữ nghĩa khác nhau. Các phương pháp phân cụm phổ biến như: K-means, GMM (Gaussian mixture models) và phân cụm mờ (chẳng hạn fuzzy c-means), MPCK-mean… 1.5. Giảm khoảng cách ngữ nghĩa Có nhiều cách tiếp cận để giảm khoảng cách ngữ nghĩa trong tra cứu ảnh dựa vào nội dung. Luận án lựa chọn theo hướng tiếp cận học máy để đưa ra đề xuất giảm khoảng cách này. 1.6. Đánh giá hiệu năng Để đánh giá một ứng dụng tra cứu ảnh, một cơ sở dữ liệu ảnh và một tập các truy vấn được yêu cầu. Các truy vấn được thực hiện để thu được các kết quả tra cứu. Sau đó, phương pháp đánh giá hiệu năng được sử dụng để so sánh các kết quả được tra cứu này với các ảnh liên quan đến ảnh truy vấn trong cơ sở dữ liệu. 1.7. Kết luận Chƣơng 1 và định hƣớng nghiên cứu Trong chương này, luận án đã trình bày về các đặc trưng mức thấp của ảnh, cấu trúc hệ thống tra cứu ảnh dựa vào đặc trưng mức thấp và phân tích một số phương pháp tra cứu ảnh dựa vào đặc trưng mức thấp. Bên cạnh đó, luận án cũng đã trình bày một số phương pháp giảm khoảng cách ngữ nghĩa theo cách tiếp cận phản hồi liên quan. Một số kỹ thuật tra cứu ảnh với ngữ nghĩa mức cao đã được phân tích. Ở thời điểm hiện nay, khi chúng ta đề xuất một thuật toán hiệu quả cho CBIR, một số vấn đề cần phải được giải quyết. Vấn đề đầu tiên đó là giảm gánh nặng cho người dùng, tức là không yêu cầu người dùng phải cung cấp đồng thời nhiều ảnh truy vấn đa dạng. Vấn đề thứ hai đó là các ảnh liên quan ngữ nghĩa không thuộc về cùng một cụm mà nằm rải rác trong không gian đặc trưng. Do đó để tăng độ chính xác, cần thiết phải có cách thức lấy được các ảnh nằm rải rác trong không gian đặc trưng. Vấn đề thứ ba đó là vùng chứa các điểm truy vấn tối ưu khác nhau có thể rất khác nhau. Do đó, để nâng cao độ chính xác, cần khai thác thông tin địa phương của mỗi vùng. 4
Trong luận án này, tác giả sẽ tập trung vào vấn đề nâng cao độ chính xác tra cứu ảnh theo hướng tiếp cận giảm khoảng cách ngữ nghĩa. Thứ nhất, luận án sẽ đề xuất phương pháp tra cứu ảnh liên quan ngữ nghĩa để thu được tập ảnh kết quả có sự đa dạng nằm rải rác trong toàn bộ không gian đặc trưng mà không yêu cầu người dùng tạo truy vấn phức tạp [CT5]. Thứ hai, luận án sẽ đề xuất phương pháp tra cứu ảnh sử dụng bộ trọng số thích nghi. Thay vì sử dụng chung một bộ trọng số cho các cụm chứa ảnh truy vấn tối ưu, phương pháp xác định trọng số cho từng cụm cụ thể [CT6]. 5
Chƣơng 2. PHƢƠNG PHÁP TRA CỨU ẢNH LIÊN QUAN NGỮ NGHĨA 2.1. Giới thiệu Các cách tiếp cận đối với CBIR giả thiết rằng, trong một không gian nào đó, vị trí của các ảnh liên quan gần với ảnh truy vấn. Giả thiết này phù hợp với bài toán mà ở đó người dùng chỉ muốn tìm những ảnh có cùng đặc trưng mức thấp, chẳng hạn: tìm những bông hồng màu đỏ. Tuy nhiên, với bài toán mà ở đó người dùng đặt ra yêu cầu là tìm ra những ảnh có thể có đặc trưng mức thấp khác nhau nhưng cùng ngữ nghĩa, chẳng hạn: tìm tất cả những bông hồng (bao gồm cả hoa hồng màu đỏ, màu vàng, màu trắng) trong cơ sở dữ liệu ảnh, thì giả thiết này không phù hợp. Chương này và chương sau của luận án sẽ đề xuất các phương pháp giải quyết bài toán tìm ra những ảnh có thể có đặc trưng mức thấp khác nhau nhưng cùng ngữ nghĩa (tức là cùng một chủ đề). Sự tương tự giữa các ảnh mà con người nhận thức (các ảnh liên quan về mặt ngữ nghĩa) lại khác với sự tương tự 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 duy nhất. Trong trường hợp này, cách tiếp cận phản hồi liên quan truyền thống [2,29,61,74] không làm việc tốt (do họ sử dụng cách tiếp cận một điể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. Các phương pháp được trình bày theo cách tiếp cận phản hồi liên quan với truy vấn tách rời đều có ưu điểm cho kết quả là 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. Tuy nhiên, những phương pháp này có những hạn chế: (1) Yêu cầu người dùng phải cung cấp đồng thời các ảnh truy vấn đa dạng, chẳng hạn, để truy vấn chủ đề hoa hồng, người dùng phải cung cấp các ảnh hoa hồng đỏ, hoa hồng vàng, hoa hồng trắng,... làm truy vấn. Nếu điều kiện này không được thỏa mãn, kết quả tra cứu khởi tạo sẽ là các ảnh nằm trong một vùng nào đó chứ không bao gồm các ảnh liên quan nằm trong các vùng khác nhau. Nếu người dùng cung cấp cho hệ thống các ảnh truy vấn là các ảnh hoa hồng màu vàng, kết quả tra cứu khởi tạo chỉ có thể trả về các ảnh hoa hồng màu vàng mà bỏ qua các ảnh hoa hồng màu trắng và màu đỏ. Lý do của việc này là vì trong các hệ thống tra cứu ảnh truyền thống, các ảnh có véc tơ đặc trưng mức thấp tương tự nhau sẽ nằm gần nhau (hay trong cùng một cụm đặc trưng mức thấp). Trên danh sách kết quả khởi tạo gồm có các bông hồng màu vàng, người dùng chỉ có thể chọn được các bông hồng màu vàng. Hệ thống dựa vào các phản hồi là các bông hồng màu vàng để tiếp tục tra cứu. Các pha tra cứu tiếp theo sẽ dịch chuyển đến các vùng màu vàng. Kết quả của hệ thống chỉ có thể thu được các bông hồng màu vàng. Vì vậy, các vùng hoa hồng màu đỏ và trắng sẽ bị bỏ qua, do đó độ chính xác của hệ thống sẽ bị giới hạn cho dù pha tra cứu sau đó có ưu việt đến đâu. 6
(2) Số lần truy vấn cho lần lặp tiếp theo phụ thuộc vào số ảnh liên quan do người dùng cung cấp, do đó có hai khả năng không thuận lợi xảy ra: Khả năng thứ nhất, người dùng chọn quá ít ảnh phản hồi (ít hơn số cụm trong không gian đặc trưng). Trong khả năng này, độ chính xác của hệ thống sẽ không được đảm bảo vì theo lý thuyết phân cụm, nhiều truy vấn sẽ phủ nhiều cụm hơn. Khả năng thứ hai là người dùng chọn quá nhiều ảnh phản hồi. Khả năng này sẽ làm tăng gánh nặng cho pha gộp các danh sách kết quả (mỗi truy vấn sẽ có một danh sách kết quả). Ngoài ra, quá nhiều truy vấn cũng không cải tiến nhiều độ chính xác của hệ thống (thực nghiệm trong [49] đã chỉ ra rằng độ chính xác tăng nhanh từ 1 đến 8 truy vấn và tăng chậm khi số truy vấn từ 8 đến 20). Chẳng hạn, trong cơ sở dữ liệu Corel với chủ đề hoa hồng, mỗi ảnh truy vấn hoa hồng cũng chỉ nằm rải rác trong 4 cụm (mỗi cụm tương ứng với một màu của hoa hồng). (3) Sử dụng các trọng số của các truy vấn ngang bằng nhau, tức là, độ quan trọng của các truy vấn là như nhau cho dù mỗi truy vấn có lân cận khác nhau. (4) Các đặc trưng có trọng số như nhau cho dù mỗi thành phần đặc trưng có một độ quan trọng khác nhau. Những hạn chế này là nguyên nhân chính dẫn đến độ chính xác của hệ thống tra cứu chưa cao. Trên cơ sở phân tích các hạn chế của các phương pháp đã có, luận án đề xuất một phương pháp tra cứu ảnh liên quan ngữ nghĩa. Phương pháp đề xuất có ưu điểm là: (1) Chỉ sử dụng một truy vấn để tạo ra kết quả tra cứu khởi tạo đa dạng, gồm các ảnh nằm trong các vùng khác nhau (giảm gánh nặng cho người dùng trong việc không phải chọn nhiều ảnh truy vấn). (2) Phân cụm các ảnh liên quan với thời gian thấp. (3) Xác định được độ quan trọng ngữ nghĩa của từng truy vấn. (4) Xác định độ quan trọng theo từng đặc trưng. Bốn ưu điểm này đã được thể hiện trong phương pháp đã được công bố trong [CT5, CT6]. 2.2. Sơ đồ phƣơng pháp đề xuất Trên cơ sở các phân tích ở mục 2.1 ở trên, luận án đề xuất sơ đồ của phương pháp như trên Hình 2.5. 7
Ảnh truy vấn Các biểu diễn Kết quả Véc tơ đặc trưng Sắp xếp Tập ảnh được Phản hồi Tập phản Phân cụm Độ tương tự gia tăng Các cụm tra cứu hồi Truy vấn Cơ sở dữ liệu đặc Độ quan trọng truy vấn Tính toán trưng Các điểm Tính toán Độ quan trọng truy vấn đặc trưng Đại diện cụm Hình 2.5. Cấu trúc phƣơng pháp đề xuất. Phần tiếp theo của luận án sẽ trình bày chi tiết phương pháp đề xuất. Phần tiếp theo cần có một số định nghĩa, do đó luận án đưa ra một số định nghĩa ở đây. Định nghĩa 2.1 (Tập đặc trƣng). Một tập đặc trưng F gồm có N bộ đặc trưng, mỗi bộ gồm m thành phần, mỗi thành phần là một giá trị thực. (2.1) Định nghĩa 2.2 (Không gian đặc trƣng). Một không gian đặc trưng FS gồm m chiều, mỗi chiều tương ứng với một thành phần thực của bộ đặc trưng t (t=1..N) thuộc tập đặc trưng F, mỗi điểm pt (t=1..N) trong không gian FS tương ứng với một bộ đặc trưng trong F. (2.2) Định nghĩa 2.3 (Không gian đặc trƣng thứ i). Một không gian đặc trưng thứ i, ký hiệu là , là một không gian đặc trưng gồm n chiều, mỗi điểm trong không gian này được ký hiệu là (t=1..N) có n tọa độ. (2.3) Định nghĩa 2.4 (Đo khoảng cách giữa hai điểm trong không gian đặc trƣng FSi). Đo khoảng cách giữa hai điểm và (k,l=1..N) và kl ,được ký hiệu là ( ), là độ đo khoảng cách nào đó. Ý tƣởng chính của phƣơng pháp đề xuất là không đặt các ảnh (bao gồm cả ảnh cơ sở dữ liệu và ảnh truy vấn) trong cùng một không gian đặc trưng mà đặt trong nhiều không gian đặc trưng (trong ngữ cảnh của chương này, luận án ánh xạ mỗi một biểu diễn của ảnh vào một không gian đặc trưng tương ứng), sau đó thực hiện tra cứu bằng việc truy vấn trên mỗi không gian đặc trưng này và nhập các kết quả tương ứng với các không gian đặc trưng thành một kết quả cuối cùng. Lý do mà phương pháp trong luận án có thể lấy được các ảnh nằm rải rác trong không gian đặc trưng màu gốc là vì các ảnh được chuyển về biểu diễn xám. Theo biểu diễn này, các đặc trưng hình dạng và kết cấu sẽ không bị át bởi màu. Một ảnh hoa hồng (biểu diễn xám) sẽ được ánh xạ thành một điểm trong không gian 8
đặc trưng. Trong không gian này, do đặc trưng mầu không được bao gồm cho nên các ảnh cùng chủ đề (chẳng hạn: bông hoa hồng vàng, trắng và đỏ) sẽ có vị trí gần nhau. Do vậy, phương pháp đề xuất có thể lấy ra được các ảnh hoa hồng màu đỏ, màu hồng và màu vàng tương ứng với ảnh truy vấn màu đỏ. Đến đây, quá trình tra cứu sẽ đối sánh giữa ảnh truy vấn và ảnh cơ sở dữ liệu trong mỗi một không gian đặc trưng riêng lẻ để có được một danh sách kết quả. Như vậy, ta sẽ có 4 danh sách kết quả. Tiếp theo, bốn danh sách kết quả sẽ được gộp lại để được một danh sách kết quả cuối cùng. 2.3. Phản hồi liên quan với truy vấn đa điểm Cách tiếp cận ban đầu đối với tra cứu ảnh dựa vào nội dung không thích ứng với tra cứu dựa vào nhận thức của người dùng về độ tương tự trực quan. Để khắc phục vấn đề này, một số phương pháp tra cứu ảnh sử dụng phản hồi liên quan được đề xuất. Có hai thành phần để học phản hồi liên quan đó là hàm khoảng cách và điểm truy vấn mới. Hàm khoảng cách được thay đổi thông qua việc học các trọng số của các thành phần đặc trưng và điểm truy vấn mới thu được bằng việc học điểm mong muốn mà người dùng tìm kiếm. 2.4. Thuật toán tra cứu ảnh đề xuất Định nghĩa 2.5 (Truy vấn đa điểm): Một truy vấn đa điểm MQ=, với nMQ biểu thị số các điểm truy vấn trong MQ, PMQ={PMQ1,…,PMQn} là tập nMQ điểm truy vấn trong không gian tìm kiếm DB, WMQ={wMQ1,…,wMQn} là tập các trọng số được kết hợp với PMQ (luận án giả thiết rằng các trọng số được chuẩn hóa tức là ∑ ), DMQ là khoảng cách mà khi được cho hai điểm bất kỳ pi và pj trong không gian đặc trưng sẽ trả lại khoảng cách giữa chúng và k là số các điểm được tra cứu trong mỗi lần lặp. 2.4.1. Phân cụm tập ảnh phản hồi Thuật toán 2.1 dưới đây là thuật toán phân cụm sử dụng k véc tơ riêng CISE (Clustering Images Set using Eigenvectors) thực hiện việc phân cụm tập các ảnh thành k cụm. Thuật toán 2. . Thuật toán phân cụm sử dụng k véc tơ riêng 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 1. Xây dựng ma trận affinity for i1 to n do for j1 to n do ‖ ‖ if (ij) e p else  2. Xây dựng ma trận đường chéo và ma trận Laplace L for i1 to n do ∑ 9
L  D-1/2 A D-1/2 3. Tìm k véc tơ riêng lớn nhất 1, x2 k của ma trận Laplace L for i1 to k do  X  [x1T ,x2T kT ] 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/ ∑ )1/2 Y  [y1 ,y2 yk ] 5. Phân thành k cụm thông qua K-Means  for i1 to n do   K-Mean(P) 6. Gán các si vào các cụm for i1 to n do if .. Return C1, C2 Ck 2.4.2. Thuật toán đề xuất cho phân cụm gia tăng Sau khi thực hiện phân cụm tập ảnh phản hồi của người dùng, để tránh việc phận cụm lại toàn bộ tập ảnh phản hồi. Luận án thực hiện phân cụm gia tăng cho mỗi cụm. Giả sử dữ liệu có phân phối Gauss. Trong thuật toán này, ta coi mỗi cụm như một nhóm. Khi huấn luyện, ta sẽ ước lượng tâm và ma trận hiệp phương sai. Công việc xác định cụm của một đối tượng được tác giả qui về bài toán tìm một ước lượng sao cho: với một đầu vào được cho , nhãn cụm của nó sẽ được xác định theo: ŷ0 y (2.8) Tuy nhiên, rất khó tính toán, do đó thay vì tính toán , ta sẽ ước lượng qua và Y . Theo luật Bayes, với i là nhãn của nhóm, ta có công thức: (2.9) ∑ (2.10) Giả sử rằng là phân phối chuẩn đa biến với hàm mật độ: ∑ = ∑ (2.11) Trong đó: 10
Trung bình của nhóm i ∑ : ma trận hiệp phương sai gộp chung của tất cả các nhóm Giả sử rằng ta biết: (2.12) (2.13) Lưu ý: công thức (2.13) là tỉ số của các mẫu huấn luyện của nhóm i trên tổng số mẫu huấn luyện. Đến đây, chúng ta thu được công thức: (2.14) Vì mẫu số trong (2.14) không phụ thuộc vào i, nên chúng ta có thể coi nó là một hằng số C và thu được công thức. (2.15) Thay từ (2.11) vào (2.15), ta được: ∑ ∑ (2.16) Vì 2 ∑ trong (2.16) không phụ thuộc vào i nên ta đặt ∑ bằng hằng số và ta có: ∑ (2.17) và lấy logarit của cả hai vế của (2.17), ta được: log log log ∑ (2.18) Giá trị của vế phải (2.18) đúng với mọi nhóm i nên ta chỉ quan tâm đến: log ∑ (2.19) =log [ ∑ ∑ ] ∑ (2.20) Như vậy, mục tiêu của ta là cực đại công thức (2.20) theo i. Do ∑ trong (2.20) không phụ thuộc vào i nên ta coi nó là một hằng số nên (2.20) biến đổi thành log ∑ ∑ (2.21) Bỏ qua hằng số , ta có hàm mục tiêu: log ∑ ∑ (2.22) Với một đầu vào x, chúng ta dự đoán nhãn của nó là i nếu cao nhất. 2.4.3. Công thức đề xuất cho tính khoảng cách cải tiến Luận án đề xuất công thức tính khoảng cách từ một ảnh đến truy vấn đa điểm MQ = (Q1, Q2,..Qn). Khoảng cách này (2.23) là cực tiểu của các khoảng cách có trọng số từ một ảnh đến mỗi truy vấn Qi: ( ) .. (2.23) ớ  ... 11
Trong công thức (2.23), Dist( ,Qi ) với i=1..n, j=1..k là khoảng cách từ một ảnh đến một truy vấn Qi với trọng số đặc trưng (xác định theo thuật toán IF ), là trọng số ngữ nghĩa kết hợp với khoảng cách dij (xem cách tính trọng số ngữ nghĩa trong công thức (2.24)). 2.4.4. Công thức đề xuất cho tính trọng số ngữ nghĩa của truy vấn Đề xuất được dựa trên nhận thức rằng, trong một cụm chứa nhiều ảnh liên quan ngữ nghĩa sẽ quan trọng hơn các cụm còn lại. Do đó, truy vấn được tạo ra từ cụm đó sẽ có trọng số ngữ nghĩa cao hơn các cụm còn lại. Vì vậy, tác giả đề xuất tính trọng số ngữ nghĩa wij kết hợp với khoảng cách dij từ ảnh đến truy vấn Qi (thuộc cụm ngữ nghĩa i) là tỉ số giữa số ảnh liên quan ngữ nghĩa trong cụm i và tổng số các ảnh liên quan của n cụm ngữ nghĩa. ụ ∑ ụ ớ  (2.24) Các trọng số cần thỏa mãn điều kiện ∑ ớ  ... 2.4.5. Thuật toán đề xuất cho tính độ quan trọng đặc trƣng Ý tưởng chính của việc xác định độ quan trọng đặc trưng là dựa vào sự phản hồi của người dùng và độ phân tán của các điểm dữ liệu. Khi người dùng phản hồi một số ảnh liên quan ngữ nghĩa với ảnh truy vấn, phương pháp đề xuất sẽ phân cụm các ảnh này thành các cụm và xét mỗi cụm trong số các cụm này như sau: mỗi ảnh trong một cụm sẽ là một điểm trong không gian đa đặc trưng và các điểm này sẽ có vị trí gần nhau trong không gian đa đặc trưng. Một hình bao các điểm này sẽ được chiếu xuống các trục tương ứng với các đặc trưng, sau đó tính phương sai của các điểm này theo mỗi trục (độ phân tán dữ liệu theo một trục trong không gian đặc trưng lớn có nghĩa là độ quan trọng theo trục đó nhỏ). Do đó, độ quan trọng của mỗi đặc trưng trong không gian đa đặc trưng là nghịch đảo của phương sai của các điểm theo trục đó. 2.4.6. Thuật toán đề xuất cho gộp các danh sách kết quả Với mỗi điểm truy vấn, hệ thống sẽ cho ra một danh sách kết quả. Các danh sách này cần được gộp lại để có một danh sách kết quả cuối cùng. Thuật toán gộp thực hiện công việc này. Mệnh đề 1. [Độ phức tạp của thuật toán Combination]: Độ phức tạp của thuật toán Combination là . với n là số danh sách cần kết hợp và k là số ảnh trả về của mỗi danh sách. 2.4.7. Thuật toán đề xuất chung cho tra cứu ảnh liên quan ngữ nghĩa Ở phần này, luận án đề xuất một thuật toán, có tên SRIR (Semantic – Related Image Retrieval), không đòi hỏi người dùng phải cung cấp đồng thời nhiều truy vấn đa dạng. Dưới đây là mô tả thuật toán tra cứu các ảnh liên quan ngữ nghĩa SRIR. Thuật toán 2.5. Thuật toán SRIR Input: Tập các ảnh cơ sở dữ liệu DB Ảnh truy vấn Q 12
Số các ảnh được tra c u sau mỗi lần lặp k Không gian đặc trưng F Số đặc trưng m Ouput: Tập ảnh kết quả R C+Q; PMQFC+  ; WMQFC+ ; DMQFC+ (  ) s1 ; C-  ; PMQFC-  ; WMQFC- ; DMQFC- (  ) s2 ; G+  2 ; PMQFG+  ; WMQFG+ ; DMQFG+ (  ) s3 ; G-  ; PMQFG-  ; WMQFG- ; DMQFG- (  ) s4 ; ( ) US ; repeat USUS ; CL ; for i1 to n do  ; ci (CiCL); PMQici for j1 to k do ụ WMQi∑ ụ DMQid (  ); Ri; SR until User dừng phản hồi return R; Mệnh đề 2. [Độ phức tạp của thuật toán SRIR]: Độ phức tạp của thuật toán SRIR là với N là số các ảnh có trong CSDL. 2.5. Đánh giá thực nghiệm 2.5.1 Môi trƣờng thực nghiệm 13
Cơ sở dữ liệu được sử dụng cho thử nghiệm là tập con của Corel gồm 3.400 ảnh. 2.5.3. Thực hiện truy vấn và đánh giá Để kiểm tra độ chính xác của phương phấp đề xuất Tất cả 3400 ảnh trong tập ảnh được dùng làm các truy vấn. Độ chính xác1 trung bình ở mức 150 ảnh trả về được sử dụng để đánh giá. Trong Bảng 2.2, thể hiện độ chính xác trung bình của bốn phương pháp là Basic C+, JF, MMRF và phương pháp đề xuất SRIR tại các mức 1,4 ,8 ,12, 16 và 20 truy vấn, với số cụm cũng chính là số truy vấn. Bảng 2.2. Bảng kết quả của 3 phƣơng pháp theo số truy vấn trong một lần phản hồi. Độ chính xác theo số truy vấn Phƣơng pháp 1 truy 4 truy 8 truy 12 truy 16 truy 20 truy vấn vấn vấn vấn vấn vấn Basic C+ 0.20 0.22 0.23 0.24 0.245 0.25 JF 0.24 0.29 0.31 0.33 0.34 0.35 MMRF 0.243 0.31 0.315 0.323 0.334 0.365 SRIR 0.36490 0.39789 0.40035 0.40241 0.40360 0.40385 Các kết quả thực nghiệm được chỉ ra trong Hình 2.11. Trục ngang chỉ ra số cụm (có thể là 1, 4, 8, 12, 16, 20). Trục đứng chỉ ra độ chính xác. Ba phương pháp khác nhau gồm Basic C+ , JF, MMRF và SRIR được chỉ ra bởi 3 đường cong. Hình 2.11 với Độ chính xác của các hệ thống tăng lên (trục đứng) cùng với sự tăng của trung ngang (số các cụm). Nhiều cụm được sử dụng trong tra cứu, độ chính xác hệ thống sẽ cao hơn. Dễ thấy, độ chính xác của phương pháp SRIR tốt hơn khi số cụm trong khoảng từ 1 đến 8, cụ thể là 36.490% ở mức 1, 39.789% ở mức 4 và 40.035% ở mức 8. 0.45 0.4 0.35 0.3 Độ chính xác 0.25 Basic C+ 0.2 JF 0.15 MMRF 0.1 SRIR 0.05 0 1 4 8 12 16 20 Số truy vấn phản hồi . Hình 2.11. So sánh độ chính xác. 1 Độ chính xác (precision) 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ề. 14
Trong phương pháp SRIR, đường cong độ chính xác tăng nhanh từ 1 đến 8 cụm (đặc biệt là từ 1 đến 4) và tăng chậm trong khoảng từ 12 đến 20 cụm, do 8 cụm đã phủ hầu hết các cụm trong không gian đặc trưng. Dù phương pháp JF cũng tăng nhanh trong khoảng từ 1 đến 8 truy vấn [49] nhưng phương pháp đề xuất SRIR có độ chính xác cao hơn hẳn mà không làm tăng thời gian tra cứu. Lý do chính của việc này là trong phương pháp đề xuất, dù số cụm trong khoảng từ 1 đến 8 nhưng tận dụng được thông tin ngữ nghĩa từ số phản hồi của người dùng nhiều hơn 8. 2.6. Kết luận Chƣơng 2 Luận án đã tập trung vào việc phân tích các ưu điểm và hạn chế của các phương pháp đã có. Trên cơ sở đó đề xuất phương pháp, có tên là SRIR, giải quyết bốn vấn đề chính đó là: (1) Chỉ sử dụng một truy vấn để tạo ra kết quả tra cứu khởi tạo đa dạng, gồm các ảnh nằm trong các vùng khác nhau (giảm gánh nặng cho người dùng trong việc không phải chọn nhiều ảnh truy vấn); (2) Phân cụm các ảnh liên quan với thời gian thấp; (3) xác định được độ quan trọng ngữ nghĩa của từng truy vấn và (4) xác định độ quan trọng theo từng đặc trưng. Kết quả thực nghiệm trên cơ sở dữ liệu đặc trưng gồm 3400 ảnh đã chỉ ra rằng phương pháp được đề xuất SRIR cung cấp một độ chính xác cao hơn hẳn so với các phương pháp Basic C+, MMRF và phương pháp JF. 15
Chƣơng 3. PHƢƠNG PHÁP TRA CỨU ẢNH SỬ DỤNG TRỌNG SỐ THÍCH NGHI 3.1. Giới thiệu Chương 2 của luận án đã trình bày phương pháp tra cứu ảnh [CT5] có thể lấy được các điểm ảnh cơ sở dữ liệu nằm rải rác trong toàn bộ không gian đặc trưng và cho kết quả tra cứu cao hơn những phương pháp được so sánh. Tuy nhiên, phương pháp này và những phương pháp hiện có chưa giải quyết được hai hạn chế sau: Thứ nhất, không khai thác đầy đủ thông tin phản hồi (mức độ liên quan của mỗi ảnh) để xác định các điểm truy vấn tối ưu. Chẳng hạn, Hình 3.1 là giao diện chung của các hệ thống hiện có. Giao diện này cho chúng ta thấy, người dùng chỉ có thể tích chọn vào ô ở phía trên của ảnh (nếu ảnh là liên quan) và không tích chọn (nếu ảnh không liên quan), Trong khi người dùng đánh giá ảnh có ID pl_flower\84059 cao hơn ảnh có ID pl_flower\476083. Hình 3.1: Giao diện điển hình của hệ thống CBIR với phản hồi liên quan. Thứ hai, các phương pháp ở trên coi các vùng chứa các điểm truy vấn tối ưu khác nhau là ngang bằng nhau và gán cùng trọng số cho tất cả các điểm lân cận của truy vấn tối ưu. Điều này là không thích hợp vì các vùng khác nhau thường có những thuộc tính riêng biệt. Hình 3.2. Minh họa vùng truy vấn tối ƣu ngang bằng nhau. (a) Hình bên trái: điểm truy vấn thứ nhất. (b) Hình bên phải: điểm truy vấn thứ hai. 16
Dựa trên quan sát này, luận án đã đề xuất một phương pháp tra cứu ảnh thông qua trọng số thích nghi, có tên là AWEIGH (An efficient image retrieval method using adaptive weights) [CT6]. Trong phương pháp này, thay vì sử dụng một véc tơ trọng số giống nhau cho các vùng chứa các điểm truy vấn tối ưu khác nhau, phương pháp tự động tính toán các điểm truy vấn tối ưu và các véc tơ trọng số tối ưu tương ứng với các vùng mà chứa các điểm truy vấn tối ưu dựa vào phản hồi của người dùng. Bên cạnh đó, các phương pháp trước đây thực hiện phân cụm tất cả các ảnh phản hồi, do đó độ phức tạp tính toán của các phương pháp đó sẽ cao. Để giải quyết hạn chế này, phương pháp đề xuất chỉ phân cụm các phản hồi trong lần lặp đầu tiên (từ lần lặp thứ hai, phương pháp chỉ phân lớp các phản hồi vào các cụm) (xem mục 2.3 của Chương 2). Hình 3.3 ở dưới chỉ ra sơ đồ của phương pháp đề xuất trong luận án. Sự khác biệt chính giữa đề xuất này trong luận án và các phương pháp tra cứu ảnh phản hồi liên quan đã có nằm ở ba thành phần chính (thuộc đường biên nét đứt hình chữ nhật bao): (a) Xác định các điểm truy vấn tối ưu, (b) tính toán các véc tơ trọng số và (c) Tính toán các hàm khoảng cách cải tiến. Các thành phần này có thể nhúng vào bất kỳ một hệ thống tra cứu ảnh sử dụng phản hồi liên quan nào, do đó luận án sẽ thực hiện mô tả mỗi thành phần này một cách tách biệt ở các mục tiếp sau. AWEIGHT Xác định các điểm Ảnh truy vấn truy vấn tối ưu Xác định các Máy tìm kiếm trọng số Tính toán hàm Tập kết quả khoảng cách cải tiến Tập phản hồi Máy tìm kiếm Phân cụm Tập kết quả các ảnh Tập phản hồi Tập huấn Gia tăng luyện cụm Hình 3.3. Sơ đồ của tra cứu ảnh sử dụng các trọng số thích nghi. 17
3.2. Thuật toán xác định điểm truy vấn tối ƣu và bộ trọng số thích nghi của hàm khoảng cách cải tiến. Trong phần này, luận án trình bày kỹ thuật đề xuất để xác định điểm truy vấn tối ưu và trọng số thích nghi của hàm khoảng cách. Kỹ thuật xác định điểm truy vấn tối ưu và các trọng số thích nghi theo một cụm các ảnh được cho. Trong trường hợp nhiều cụm, kỹ thuật này được thực hiện cho từng cụm. Ở đây, ta giả sử đã có cụm i (i=1,…,g) nào đó, mỗi ảnh trong cụm i được biểu diễn bởi img img img img với j=1…n , ma trận M img img (n là số các phần tử trong cụm i) biểu diễn các ảnh trong cụm i. Giả thiết véc tơ truy vấn tối ưu đối với cụm i là q q q q . Giả sử thông tin đánh giá của người dùng dưới dạng mức độ liên quan cho mỗi img (j=1,..,n ) được ký hiệu là lr (ở đây lr  2 , lr cao thì khoảng cách nhỏ hay độ tương tự cao), véc tơ L lr lr . lr sẽ biểu diễn thông tin đánh giá của người dùng dưới dạng mức độ liên quan của cụm M img img . Bài toán tìm điểm truy vấn tối ưu q và ma trận trọng số được đưa về bài toán tối ưu có ràng buộc như sau: min ∑ lr (img q ) img q (3.1) Với ràng buộc det( )=1 Ở đây det( ) là định thức của ma trận (ràng buộc det( )=1 để tránh trường hợp ma trận là ma trận không). Để tìm được nghiệm q và của bài toán trong (3.1), ta sử dụng phương pháp nhân tử Lagrange để giải: - Điểm truy vấn tối ưu q : ∑ q với q m . d (3.2) ∑ ∑ - Ma trận trọng số : det C C (3.3) Với ma trận hiệp phương sai có trọng số của các ảnh trong cụm i: C c với: c ∑ lr img ̅̅̅̅̅ mg img ̅̅̅̅̅ mg (3.4) Từ véc tơ truy vấn tối ưu q và ma trận trọng số W, hàm khoảng cách được xác định như sau: d (img q ) (img q ) (img q ) (3.5) Cho Cpf (q ) là danh sách các điểm trong cụm các mẫu phản hồi dương tương ứng với điểm truy vấn tối ưu thứ i (q tức là danh sách các điểm trong 18