Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Phát triển mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree

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

Thêm vào BST

Báo xấu

11
lượt xem 4
download

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

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "Phát triển mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree" được nghiên cứu với mục tiêu là: Nghiên cứu cấu trúc dữ liệu đa chiều KD-Tree; xây dựng các thuật toán thao tác trên KD-Tree tổ chức lưu trữ véc-tơ đặc trưng hình ảnh; Phát triển cấu trúc KD-Tree, đồng thời xây dựng và bổ sung ngữ nghĩa cho các bộ dữ liệu thực nghiệm nhằm thực hiện mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa.

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ĩ Khoa học máy tính: Phát triển mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ ĐỊNH PHÁT TRIỂN MÔ HÌNH TÌM KIẾM ẢNH DỰA TRÊN CẤU TRÚC KD-TREE Ngành: Khoa học máy tính Mã số: 9480101 LUẬN ÁN TIẾN SĨ NGÀNH KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học 1. PGS. TS. Lê Mạnh Thạnh 2. TS. Văn Thế Thành HUẾ, NĂM 2023
Công trình được hoàn thành tại: Khoa Công nghệ Thông tin, Trường Đại học Khoa học, Đại học Huế. Người hướng dẫn khoa học: PGS. TS. Lê Mạnh Thạnh TS. Văn Thế Thành Phản biện 1: PGS. TS. Trần Đăng Hưng, Trường Đại học Sư phạm Hà Nội. Phản biện 2: PGS. TS. Hồ Sỹ Đàm, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội. Phản biện 3: TS. Hoàng Bảo Hùng, Trung tâm Công nghệ thông tin, tỉnh Thừa Thiên Huế. Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp Đại học Huế họp tại: ………………………………………... ……………………………………………………………….. 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: Trung tâm thông tin thư viện, Trường Đại học Khoa học, Đại học Huế.
1 MỞ ĐẦU 1. Tính cấp thiết của luận án Dữ liệu ảnh số được ứng dụng trong một số bài toán như phân loại bệnh nhân qua hình ảnh MRI [75], nhận diện đối tượng bằng hình ảnh [77], v.v. Vì vậy, ảnh số đã trở nên cần thiết và đóng vai trò quan trọng trong lĩnh vực tra cứu thông tin và nhận diện đối tượng bằng hình ảnh. Một cấu trúc dữ liệu lưu trữ được đề xuất đáp ứng nhu cầu gia tăng dữ liệu là cần thiết cho bài toán tìm kiếm ảnh, chẳng hạn như S-Tree [38], C-Tree [52], KD-Tree [84], v.v. Trong luận án, cấu trúc dữ liệu đa chiều KD-Tree được nghiên cứu và xây dựng cho bài toán tìm kiếm ảnh đã mang lại kết quả khả quan, đáp ứng khả năng lưu trữ khi dữ liệu tăng trưởng theo thời gian, phù hợp với dữ liệu véc-tơ đặc trưng hình ảnh, thời gian tìm kiếm ổn định. 2. Tổng quan tình hình nghiên cứu Tìm kiếm ảnh sử dụng các kỹ thuật gom cụm và phân lớp đã mang lại những kết quả khả quan trong thập niên vừa qua; trong đó một số công trình đã sử dụng kết hợp các kỹ thuật học máy k-Means, k-NN, DNN, CNN, v.v [26], [63], [64]. Hầu hết các công trình này đều sử dụng kỹ thuật phân lớp và gom cụm thành các nhóm dữ liệu tương đồng trước khi thực hiện tìm kiếm ảnh. Tuy nhiên, quá trình kết hợp các kỹ thuật học máy cho bài toán tìm kiếm ảnh còn những hạn chế về một số yếu tố như: mở rộng khả năng lưu trữ theo nhu cầu dữ liệu tăng trưởng, giảm thời gian tìm kiếm trên các tập dữ liệu ảnh lớn. Tìm kiếm ảnh theo tiếp cận ngữ nghĩa sử dụng ontology là một hướng tiếp cận đã mang lại nhiều kết quả khả quan trong thập niên vừa qua. Cụ thể như Manzoor và cộng sự (2015) [44] đã đề xuất một phương pháp tìm kiếm ảnh theo ngữ nghĩa dựa trên ontology để truy
2 xuất ngữ nghĩa hình ảnh có liên quan đến nội dung tìm kiếm của người dùng. Olfa Allani và cộng sự (2016) [4] đề xuất một hệ thống tra cứu ảnh tích hợp ngữ nghĩa với các đặc trưng thị giác để xây dựng một ontology cho việc tra cứu và tổ chức các thông tin ngữ nghĩa hình ảnh. Trên cơ sở tổng quan tình hình nghiên cứu và các hướng tiếp cận bài toán tìm kiếm ảnh; một số định hướng được đề xuất và cải tiến nhằm nâng cao độ chính xác cho bài toán tìm kiếm ảnh dựa trên cấu trúc KD-Tree. Cuối cùng, kết hợp KD-Tree và Ontology để tìm kiếm ảnh theo tiếp cận ngữ nghĩa được thực hiện. 3. Mục tiêu của luận án Mục tiêu cụ thể của luận án gồm: (1) nghiên cứu cấu trúc dữ liệu đa chiều KD-Tree; xây dựng các thuật toán thao tác trên KD-Tree tổ chức lưu trữ véc-tơ đặc trưng hình ảnh; (2) phát triển cấu trúc KD- Tree, đồng thời xây dựng và bổ sung ngữ nghĩa cho các bộ dữ liệu thực nghiệm nhằm thực hiện mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa; (3) phát triển mô hình tìm kiếm ảnh bằng cách kết hợp các phương pháp học có giám sát, bán giám sát để tạo ra mô hình phân lớp hình ảnh, gom cụm dữ liệu dựa trên cấu trúc KD-Tree. 4. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu: (1) các phương pháp phân cụm và phân lớp dữ liệu; (2) cấu trúc phân cụm dữ liệu đa chiều; (3) cấu trúc Ontology và phát triển Ontology; (4) các tập ảnh đơn đối tượng, đa đối tượng. Phạm vi nghiên cứu: (1) các phương pháp học máy: học có giám sát, và bán giám sát; (2) cấu trúc dữ liệu đa chiều KD-Tree; (3) các cải tiến: iKD_Tree, KD-Tree lồng nhau, Re KD-Tree, RF KD-Tree; (4) cấu trúc Ontology và ngôn ngữ truy vấn SPARQL; (5) các tập ảnh COREL, Wang, Caltech-101, Caltech-256, MS-COCO, Flickr. 5. Phương pháp nghiên cứu
3 Phương pháp lý thuyết: (1) Tổng hợp các công trình nghiên cứu liên quan đến tìm kiếm ảnh trong thời gian gần đây, quan tâm đến kết quả của các công trình sử dụng mô hình học máy, tìm kiếm ảnh theo ngữ nghĩa và các cấu trúc lưu trữ dạng cây. Nghiên cứu phương pháp làm giàu Ontology và phát triển mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa. (2) Đề xuất mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa, đánh giá thực nghiệm, so sánh độ chính xác tìm kiếm ảnh với các công trình cùng lĩnh vực để có sự điều chỉnh và cải tiến thích hợp. Phương pháp thực nghiệm: (1) Các chương trình được viết bằng ngôn ngữ cấp cao cho các thuật toán và trên hệ thống máy tính có cùng cấu hình. (2) Dữ liệu thực nghiệm là các bộ dữ liệu ảnh chuẩn đã được công bố và sử dụng trong các công trình có kết quả. Một số công việc gồm: trích xuất đặc trưng hình ảnh cho các bộ dữ liệu ảnh tiêu chuẩn: COREL [19], Wang [20], Caltech-101 [12], Caltech-256 [13], phát hiện, phân đoạn ảnh đối tượng và trích xuất véc-tơ đặc trưng bộ ảnh MS-COCO [21], Flickr [22]. (3) Xây dựng cấu trúc dữ liệu, cài đặt thuật toán và mô hình đề xuất để thực nghiệm trên các bộ dữ liệu ảnh chuẩn; so sánh kết quả thực nghiệm trên cùng bộ dữ liệu với các công trình đã công bố, so sánh kết quả thực nghiệm của cùng một bộ dữ liệu trên các mô hình đề xuất để minh chứng tính đúng đắn và hiệu quả của cơ sở lý thuyết. 6. Bố cục của luận án Luận án được trình bày trong 139 trang, mở đầu (08 trang), kết luận và hướng phát triển (02 trang), danh mục các công trình khoa học của tác giả liên quan đến luận án (1 trang), tài liệu tham khảo (07 trang), luận án chia thành 3 chương. Chương 1 (21 trang) trình bày cơ sở lý thuyết cho tìm kiếm ảnh và cấu trúc KD-Tree. Chương 2 (36 trang) trình bày một số cải tiến cấu trúc KD-Tree cho tìm kiếm. Chương 3
4 (34 trang) phát triển KD-Tree theo tiếp cận ngữ nghĩa, xây dựng Ontology và xây dựng thực nghiệm trên các bộ ảnh đa đối tượng. Phần phụ lục (19 trang) là các hình ảnh chi tiết về biểu đồ precision, recall và đường cong ROC chi tiết cho các bộ ảnh thực nghiệm theo từng chương; biểu đồ thời gian truy vấn trên các tập ảnh thực nghiệm. 7. Đóng góp của luận án Đóng góp chính của luận án là phát triển cấu trúc KD-Tree bằng phương pháp tích hợp mạng Nơ-ron vào mỗi nút trên cây để cải tiến KD-Tree nhằm nâng cao độ chính xác tìm kiếm ảnh, cụ thể bao gồm: - Xây dựng cấu trúc KD-Tree đa nhánh cân bằng và các cấu trúc cải tiến iKD_Tree; cấu trúc KD-Tree lồng nhau, đồng thời đề xuất mô hình tìm kiếm ảnh dựa trên các cấu trúc này. - Phát triển cấu trúc KD-Tree theo tiếp cận ngữ nghĩa; xây dựng rừng ngẫu nhiên; phát triển Ontology cho các tập ảnh thực nghiệm; đề xuất mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên sự kết hợp Ontology, Re KD-Tree và RF KD-Tree. Chương 1. TỔNG QUAN VỀ TÌM KIẾM ẢNH VÀ CẤU TRÚC KD- TREE 1.1. Giới thiệu Luận án tiếp cận các phương pháp tìm kiếm ảnh dựa trên các cải tiến cấu trúc KD-Tree gồm KD-Tree đa nhánh cân bằng, iKD_Tree và KD-Tree lồng nhau. Sau đó xây dựng rừng ngẫu nhiên gồm nhiều KD- Tree, phát triển KD-Tree theo tiếp cận ngữ nghĩa và phát triển Ontology để thực hiện bài toán tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên sự kết hợp các đặc trưng hình ảnh với đặc trưng ngữ nghĩa, đồng thời tìm kiếm trên Ontology nhằm nâng cao độ chính xác. Như vậy, bài toán tìm kiếm ảnh được thực hiện dựa trên cấu trúc KD-Tree và Ontology.
5 1.2. Tìm kiếm ảnh theo nội dung Phương pháp tìm kiếm ảnh theo nội dung được thực hiện bằng cách trích xuất nội dung hình ảnh thành véc-tơ đặc trưng đa chiều, tổ chức lưu trữ và thực hiện tìm kiếm tập ảnh có độ tương tự gần nhất dựa trên cơ sở dữ liệu ảnh đã có. Một số độ đo tương tự giữa hai hình ảnh được sử dụng gồm độ đo Euclide [82], độ đo Minkowski [61], v.v. Trong luận án này, độ đo Euclide để đánh giá độ tương tự giữa hai hình ảnh. Đặc trưng hình ảnh là đặc điểm sử dụng để nhận diện sự xuất hiện các đối tượng trực quan trên ảnh, bao gồm hình dạng, màu sắc, kết cấu bề mặt, vị trí tương đối, chu vi và diện tích đối tượng, v.v. Trong luận án các đặc trưng cấp thấp được trích xuất và gom nhóm thành 81, 183 và 255 chiều được sử dụng cho các thực nghiệm. 1.3. Tìm kiếm ảnh theo ngữ nghĩa Một mô hình tìm kiếm ảnh theo ngữ nghĩa, ngoài việc sử dụng đặc trưng hình ảnh còn kết hợp đặc trưng ngữ nghĩa để tìm kiếm tập ảnh dựa trên mô tả ngữ nghĩa ảnh đầu vào. Trong tìm kiếm ảnh theo tiếp cận ngữ nghĩa được đối sánh độ tương tự giữa hai hình ảnh thông qua đặc trưng ngữ nghĩa. Ngữ nghĩa này được diễn đạt qua các khái niệm, mô tả, nhận thức của con người về đối tượng cần tìm kiếm. Mối quan hệ ngữ nghĩa dựa trên đặc trưng không gian giữa các đối tượng trên mỗi hình ảnh được ứng dụng phổ biến trong các công trình về tìm kiếm ảnh theo tiếp cận ngữ nghĩa [80], [62]. Trên cơ sở xác định và trích xuất từng đối tượng trên ảnh đầu vào, mối quan hệ giữa từng cặp đối tượng được xác định thông qua tọa độ vị trí, khoảng cách tương đối khi trích xuất từng đối tượng trên ảnh. Từ đó, mối quan hệ ngữ nghĩa giữa từng cặp đối tượng của mỗi hình ảnh (bên trái, bên phải, phía trước, phía sau, ở trên, ở dưới,, v.v.) được xác định bằng KD-Tree và áp dụng cho bài toán tìm kiếm ảnh theo tiếp cận ngữ nghĩa
6 được thực hiện trong luận án này. Mối quan hệ ngữ nghĩa mô tả đặc trưng không gian cho ảnh đầu vào được minh họa như Hình 1.5 [CT5]. Hình 1.5. Xác định mối quan hệ giữa các đối tượng bằng KD-Tree 1.4. Tìm kiếm ảnh dựa trên cấu trúc KD-Tree Cấu trúc KD-Tree nguyên thủy được Bentley (1975) [10] đề xuất là một dạng cây tìm kiếm nhị phân (BST). Trên cơ sở phát triển BST với mỗi nút trên cây lưu trữ một điểm không gian đa chiều hình thành nên cấu trúc mới, gọi là KD-Tree. Cấu trúc KD-Tree là cây tìm kiếm nhị phân bao gồm một nút gốc (𝑅𝑜𝑜𝑡), các nút trong (𝑁𝑜𝑑𝑒) và nhiều nút lá (𝐿𝑒𝑎𝑓). Cấu trúc KD-Tree có khả năng tăng trưởng số nhánh tại mỗi nút trên cây nên chiều cao cây được giới hạn, khi đó thời gian tìm kiếm từ nút gốc đến nút lá là ổn định [CT1]. Trong phạm vi luận án một cấu trúc KD-Tree được cải tiến từ việc lưu trữ dữ liệu tại tất cả các nút trên cây thành cấu trúc KD-Tree chỉ lưu dữ liệu hình ảnh tại các nút lá; các nút trong và nút gốc chỉ đóng vai trò phân lớp và chọn nhánh cho dữ liệu khi thêm vào cây được duyệt từ nút gốc đến nút lá. Đề xuất cải tiến cấu trúc KD-Tree là quá trình gom cụm thì mỗi nút lá là một cụm dữ liệu tương đồng [CT3];
7 Ngoài ra, cấu trúc KD-Tree được xây dựng theo phương pháp phân lớp hình ảnh, các nút trong lưu trữ véc-tơ trọng số đã được huấn luyện theo phương pháp học có giám sát để thu được kết quả phân lớp tại nút lá. Phân lớp bằng cấu trúc KD-Tree là quá trình phân lớp một đối tượng khi đi qua mỗi tầng nút trong thực hiện một lần phân lớp. Tại mỗi nút trên KD-Tree là mạng nơ-ron một nút dùng để phân lớp đối tượng hình ảnh một lần. Vì vậy, cấu trúc KD-Tree đã mang lại kết quả phân lớp hình ảnh cao sau khi huấn luyện. Quá trình phân lớp thì mỗi nút lá là một phân lớp hình ảnh [CT2]. 1.5. Phương pháp thực nghiệm và đánh giá Để xác định hiệu quả của các mô hình được đề xuất, các phương pháp tổ chức thực nghiệm và đánh giá trong luận án bao gồm: môi trường thực nghiệm, các tập ảnh và các giá trị đánh giá hiệu suất gồm độ chính xác (precision), độ phủ (recall) và độ dung hoà (F-measure) [58]. Kết quả phân lớp ảnh số được đánh giá dựa trên mô hình phân lớp. Trong giai đoạn này, bài toán thực hiện xây dựng cấu trúc KD- Tree, huấn luyện mô hình phân lớp theo tiếp cận KD-Tree, tính kết quả phân lớp (P) dựa trên tổng số lượng hình ảnh được phân loại đúng so với tổng số hình ảnh thực nghiệm. 1.6. Tổng kết chương Nội dung của chương bao gồm các vấn đề liên quan tìm kiếm ảnh như đặc trưng cấp thấp, phương pháp trích xuất đặc trưng hình ảnh, đặc trưng ngữ nghĩa, mối quan hệ ngữ nghĩa giữa các đối tượng trên ảnh. Cấu trúc dữ liệu đa chiều và cấu trúc KD-Tree cho bài toán tìm kiếm ảnh và mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree được đề xuất. Ngoài ra, các phương pháp tổ chức thực nghiệm được trình bày bao gồm: môi trường thực nghiệm, tập dữ liệu thực nghiệm và các giá trị đánh giá kết quả tìm kiếm ảnh.
8 Chương 2. TÌM KIẾM ẢNH DỰA TRÊN CẤU TRÚC KD- TREE 2.1. Giới thiệu Chương này trình bày một số cải tiến trên cấu trúc KD-Tree cho tìm kiếm ảnh. Đầu tiên là cải tiến KD-Tree nhị phân thành KD-Tree đa nhánh cân bằng; sau đó, một số cải tiến là iKD_Tree, KD-Tree lồng nhau được đề xuất cùng với các thuật toán thao tác trên các cải tiến này và thực nghiệm trên các bộ ảnh tiêu chuẩn. 2.2. Cấu trúc KD-Tree đa nhánh cân bằng 2.2.1. Xây dựng cấu trúc KD-Tree Cấu trúc KD-Tree đa nhánh cân bằng gồm các thành phần: • Nút gốc (𝑅𝑜𝑜𝑡) là nút không có nút cha, lưu trữ một véc-tơ trọng số (w0), có tập nút con trái {𝑙𝑒𝑓𝑡}, tập nút con phải {𝑟𝑖𝑔ℎ𝑡} và thuộc một mức trên cây là ℎ0 (𝑙𝑒𝑣𝑒𝑙 = ℎ0 ). Ký hiệu: 𝑅𝑜𝑜𝑡 = < 𝑤0 , {𝑙𝑒𝑓𝑡}, {𝑟𝑖𝑔ℎ𝑡}, ℎ0 >; • Nút trong (𝑁𝑜𝑑𝑒 𝑖 ) là nút trong có một nút cha (parent), lưu trữ một véc-tơ trọng số (𝑤 𝑖 ), có tập nút con trái {𝑙𝑒𝑓𝑡}, tập nút con phải {𝑟𝑖𝑔ℎ𝑡} và có một mức trên cây (𝑙𝑒𝑣𝑒𝑙 = ℎ 𝑖 ). Ký hiệu: 𝑁𝑜𝑑𝑒 𝑖 = < 𝑝𝑎𝑟𝑒𝑛𝑡, 𝑤 𝑖 , {𝑙𝑒𝑓𝑡}, {𝑟𝑖𝑔ℎ𝑡}, ℎ 𝑖 >; • Nút lá (𝐿𝑒𝑎𝑓 𝑘 ) là nút có một nút cha (𝑝𝑎𝑟𝑒𝑛𝑡), không có nút con, lưu trữ tập véc-tơ đặc trưng hình ảnh {𝑓1 , … , 𝑓 𝑚 }, có một mức trên cây (𝑙𝑒𝑣𝑒𝑙 = ℎ) và được gán một nhãn (𝑙𝑎𝑏𝑒𝑙). Ký hiệu: 𝐿𝑒𝑎𝑓 𝑘 = < 𝑝𝑎𝑟𝑒𝑛𝑡, {𝑓1 , … , 𝑓 𝑚 }, 𝑙𝑒𝑣𝑒𝑙, 𝑙𝑎𝑏𝑒𝑙 >; • Hai nút 𝑁𝑜𝑑𝑒 𝑖 và 𝑁𝑜𝑑𝑒 𝑗 có quan hệ anh em nếu 𝑁𝑜𝑑𝑒 𝑖 và 𝑁𝑜𝑑𝑒 𝑗 có cùng một nút cha: 𝑁𝑜𝑑𝑒 𝑖 . 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑁𝑜𝑑𝑒 𝑗 . 𝑝𝑎𝑟𝑒𝑛𝑡; • Hai nút 𝑁𝑜𝑑𝑒 𝑖 và 𝑁𝑜𝑑𝑒 𝑗 có quan hệ cha con nếu 𝑁𝑜𝑑𝑒 𝑗 . 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑁𝑜𝑑𝑒 𝑖 hoặc 𝑁𝑜𝑑𝑒 𝑖 . 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑁𝑜𝑑𝑒 𝑗 ; • Hai nút 𝑁𝑜𝑑𝑒 𝑖 và 𝑁𝑜𝑑𝑒 𝑗 là đồng cấp nếu 𝑁𝑜𝑑𝑒 𝑖 . 𝑙𝑒𝑣𝑒𝑙 = 𝑁𝑜𝑑𝑒 𝑗 . 𝑙𝑒𝑣𝑒𝑙;
9 • Số nút con trái 𝑁𝑜𝑑𝑒 𝑖 . {𝑙𝑒𝑓𝑡} và số nút con phải 𝑁𝑜𝑑𝑒 𝑖 . {𝑟𝑖𝑔ℎ𝑡} tại 𝑁𝑜𝑑𝑒 𝑖 là khác nhau vì số nút con tại mỗi nút trong có thể là số lẻ. Hình 2.1. Mô tả thành phần nút gốc, nút trong và nút lá trên KD- Tree Cấu trúc KD-Tree được xây dựng lưu dữ liệu tại nút lá, nút gốc và nút trong chỉ lưu véc-tơ trọng số đóng vai trò phân lớp và liên kết đến nút con kế tiếp. 2.2.2. Các nguyên tắc xây dựng cấu trúc KD-Tree Bước 1. Khởi tạo chiều cao KD-Tree bằng ℎ, khởi tạo số nhánh tối đa tại mỗi nút trong là 𝑏. Bước 2. Khởi tạo tập véc-tơ trọng số ngẫu nhiên vừa đủ để phân bổ vào các nút trong 𝑊 𝑘𝑡 =< 𝑤0 , … , 𝑤ℎ−1 >, 𝑤 𝑖 = (𝑤 𝑖0 , … , 𝑤 𝑖𝑛 ); mỗi véc-tơ 𝑤 𝑖 lưu trữ tại 𝑁𝑜𝑑𝑒 𝑖 . Bước 3. Tại 𝑁𝑜𝑑𝑒 𝑖 khởi tạo các ngưỡng trái, phải 𝑁𝑜𝑑𝑒 𝑖 . 𝑙𝑒𝑓𝑡 = 𝑁𝑜𝑑𝑒 𝑖 . 𝑟𝑖𝑔ℎ𝑡 = 0.5 để KD-Tree cân bằng. Bước 4. Lần lượt cho véc-tơ 𝑓𝑗 đi vào KD-Tree từ nút gốc; xác định giá trị đầu ra của véc-tơ 𝑓𝑗 tại 𝑁𝑜𝑑𝑒 𝑖 và đường đi cho 𝑓𝑗 đến nhánh thuộc tầng kế tiếp theo quy tắc (2). Bước 5. Lặp lại bước 3, 4 khi gặp nút lá 𝑙𝑒𝑎𝑓 𝑘 thì ghi 𝑓𝑗 vào 𝑙𝑒𝑎𝑓 𝑘 .
10 Quá trình tạo nhánh con trái, con phải và tìm nhánh gần nhất được thực hiện theo qui tắc (2) như sau: 1. Nếu yij > Nodei . right thì 𝑓𝑗 đi theo nhánh con phải; cập nhật 𝑁𝑜𝑑𝑒i . right = yij ; 2. Nếu yij < Nodei . left thì 𝑓𝑗 đi theo nhánh con trái; cập nhật Nodei . left = yij ; 3. Nếu 𝑁𝑜𝑑𝑒 𝑖 . 𝑙𝑒𝑓𝑡 ≤ 𝑦 𝑖𝑗 ≤ 𝑁𝑜𝑑𝑒 𝑖 . 𝑟𝑖𝑔ℎ𝑡 thì tìm nhánh có khoảng cách nhỏ nhất (𝑑 𝑚𝑖𝑛 ) từ vị trí 𝑦 𝑖𝑗 đến các giá trị ngưỡng trái, phải để xác định đường đi cho 𝑓𝑗 . 2.2.3. Quá trình gán nhãn nút lá Quá trình gán nhãn cho nút lá được thực hiện theo các bước: Bước 1: Mỗi 𝑙𝑒𝑎𝑓𝑖 , đếm tần số xuất hiện của tất cả véc-tơ cùng nhãn. Bước 2: Biểu diễn tần số xuất hiện theo từng nhãn 𝑙𝑎𝑏𝑙𝑒 𝑖 cho mỗi nút lá 𝑙𝑒𝑎𝑓𝑗 . Bước 3: Tìm giá trị lớn nhất của ma trận 𝑀𝑇(𝑛, 𝑚) là 𝑉𝑇𝑖,𝑗 tại dòng 𝑙𝑎𝑏𝑒𝑙 𝑖 và cột 𝑙𝑒𝑎𝑓𝑗 . Gán nhãn 𝑙𝑎𝑏𝑒𝑙 𝑖 cho nút lá 𝑙𝑒𝑎𝑓𝑗 là giá trị 𝑉𝑎𝑙𝑢𝑒(𝑉𝑇𝑖,𝑗 ). Bước 4: Chuyển tất cả giá trị thuộc dòng 𝑖, cột 𝑗 thành 0. Bước 5: Lặp lại bước 3, 4 khi gán hết các nhãn cho tất cả nút lá. 2.2.4. Huấn luyện trọng số trên cấu trúc KD-Tree Ban đầu bộ trọng số khởi tạo ngẫu nhiên thì kết quả phân lớp trên KD-Tree chưa cao. Vì vậy, cần điều chỉnh véc-tơ phân lớp lưu trữ tại các 𝑁𝑜𝑑𝑒 𝑖 nhằm nâng cao kết quả phân lớp tại nút lá, quá trình này gọi là huấn luyện véc-tơ trọng số. Để giảm chi phí cho quá trình xây dựng KD-Tree và huấn luyện tập véc-tơ phân lớp, tập dữ liệu ảnh ban đầu gồm 𝑛 phần tử được chia thành nhiều 𝐸𝑝𝑜𝑐ℎ dữ liệu ngẫu nhiên, mỗi 𝐸𝑝𝑜𝑐ℎ 𝑖 chứa 𝑚 phần tử (𝑚 < 𝑛) xây dựng KD-Tree và huấn luyện véc-tơ phân lớp tốt nhất 𝐹 𝑚𝑎𝑥𝑖 . Từ tập 𝐹 𝑚𝑎𝑥𝑖 tiếp tục xây dựng
11 và huấn luyện KD-Tree cho 𝐸𝑝𝑜𝑐ℎ(𝑖+1) tìm 𝐹max(𝑖+1). Kết quả thu được bộ véc-tơ phân lớp tốt nhất (𝐹 𝑚𝑎𝑥 ) trên từng bộ ảnh thực nghiệm. 2.2.5. Tìm kiếm trên cấu trúc KD-Tree Quá trình tìm kiếm trên KD-Tree là tìm nút lá chứa véc-tơ ảnh đầu vào. Vì vậy, với mỗi ảnh đầu vào (𝐼) trích xuất véc-tơ đặc trưng 𝑓𝑖 tìm kiếm trên KD-Tree chiều cao ℎ, số nhánh 𝑏. Nếu ảnh (𝐼) được tìm thấy tại 𝑙𝑒𝑎𝑓 𝑘 thì tập ảnh tương tự là tập ảnh lưu trữ tại 𝑙𝑒𝑎𝑓 𝑘 . 2.2.6. Hệ tìm kiếm ảnh trên cấu trúc KD-Tree Hình 2.6. Mô hình tìm kiếm ảnh dựa trên KD-Tree (SB-KDT) Bảng 2.2. Kết quả tìm kiếm ảnh hệ SB-KDT [CT2] Thời gian tìm Tập ảnh Precision Recall F-measure kiếm (ms) COREL 0.7998 0.7043 0.7484 96.77 Wang 0.7810 0.6508 0.6869 114.42 Caltech-101 0.7101 0.6609 0.6846 122.25 Caltech-256 0.7020 0.6291 0.6627 136.89 2.3. Cấu trúc iKD_Tree Cấu trúc iKD_Tree là một cải tiến từ KD-Tree được xây dựng bằng cách áp dụng thuật toán k-Means tại các nút trong nhằm mở rộng
12 khoảng cách giữa hai nhánh một hệ số α trong quá trình xác định nhánh con so với khoảng cách giữa các nhánh trên KD-Tree. Điều này làm mở rộng phạm vi gom các véc-tơ hình ảnh có độ tương tự vào cùng một cụm; đồng thời kết hợp thuật toán phân lớp k-NN tại nút lá. Dựa trên giá trị đầu ra tại mỗi nút trong việc xác định đường đi cho véc-tơ 𝑓𝑗 bất kỳ thuộc tầng tiếp theo trên iKD_Tree được thực hiện theo thuật toán k-Means. Tại các nút lá thực hiện phân lớp ảnh theo thuật toán k- NN [CT3]. 2.3.1. Xây dựng cấu trúc iKD_Tree Thuật toán k-Means để xác định đường đi cho véc-tơ 𝑓𝑗 chèn vào iKD_Tree. Mỗi nút trên iKD_Tree được xác định vị trí bằng giá trị tâm 𝑦 𝑖𝑗 thỏa điều kiện khi tạo 𝑁𝑜𝑑𝑒 𝑖 . Tuy nhiên, quá trình thêm phần tử vào iKD_Tree thực hiện cập nhật tâm của 𝑁𝑜𝑑𝑒 𝑖 thông qua cập nhật các giá trị ngưỡng trái (𝑁𝑜𝑑𝑒 𝑖 . 𝑙𝑒𝑓𝑡) và ngưỡng phải (𝑁𝑜𝑑𝑒 𝑖 . 𝑟𝑖𝑔ℎ𝑡). Số cụm để phần tử 𝑓𝑗 thuộc về tại mỗi 𝑁𝑜𝑑𝑒 𝑖 chính là số nhánh con của 𝑁𝑜𝑑𝑒 𝑖 . Giá trị 𝑦 𝑖𝑗 là cơ sở xác định đường đi cho 𝑓𝑗 theo các quy tắc sau: 1. Nếu 𝑦 𝑖𝑗 > 𝑁𝑜𝑑𝑒 𝑖 . 𝑟𝑖𝑔ℎ𝑡 + 𝛼 thì 𝑓𝑗 đi theo nhánh con phải; cập nhật 𝑁𝑜𝑑𝑒 𝑖 . 𝑟𝑖𝑔ℎ𝑡 = 𝑦 𝑖𝑗 2. Nếu 𝑦 𝑖𝑗 − 𝛼 < 𝑤 𝑖 . 𝑙𝑒𝑓t thì 𝑓𝑗 đi nhánh con trái; cập nhật 𝑁𝑜𝑑𝑒 𝑖 . 𝑙𝑒𝑓𝑡 = 𝑦 𝑖𝑗 3. Nếu 𝑁𝑜𝑑𝑒 𝑖 . 𝑙𝑒𝑓𝑡 − 𝛼 ≤ 𝑦 𝑖𝑗 ≤ 𝑁𝑜𝑑𝑒 𝑖 . 𝑟𝑖𝑔ℎ𝑡 + 𝛼 tìm nhánh có khoảng cách ngắn nhất (dmin) tính từ vị trí 𝑦 𝑖𝑗 đến các giá trị ngưỡng 𝑁𝑜𝑑𝑒 𝑖 . 𝑙𝑒𝑓𝑡 − 𝛼 ; 𝑁𝑜𝑑𝑒 𝑖 . 𝑟𝑖𝑔ℎ𝑡 + 𝛼 thuộc mỗi nút 𝑁𝑜𝑑𝑒 𝑖 để xác định đường đi cho véc-tơ 𝑓𝑗 . 2.3.2. Hệ tìm kiếm ảnh dựa trên cấu trúc iKD_Tree Bảng 2.7. Kết quả tìm kiếm ảnh của hệ SB-iKDT
13 Thời gian tìm Tập ảnh Precision Recall F-measure kiếm (ms) Wang 0.8010 0.7404 0.7695 101.36 Caltech-101 0.7769 0.6915 0.7317 109.84 Caltech-256 0.7228 0.5828 0.6453 134.91 Hình 2.13. Mô hình tìm kiếm ảnh dựa trên cấu trúc iKDTree 2.4. Cấu trúc KD-Tree lồng nhau Quá trình xây dựng cấu trúc KD-Tree lồng nhau gồm hai giai đoạn: (1) xây dựng cấu trúc iKD_Tree từ tập dữ liệu ban đầu; (2) một số nút lá 𝐿𝑒𝑎𝑓 𝑘 được phát triển thành một cây con SubTree. Kết hợp cấu trúc iKD_Tree và SubTree tạo nên cấu trúc KD-Tree lồng nhau [CT4]. Bảng 2.12. Kết quả tìm kiếm ảnh của hệ SB-NKDT [CT4] Thời gian tìm Tập ảnh Precision Recall F-measure kiếm (ms) COREL 0.8120 0.7164 0.7612 109.49 Wang 0.8029 0.7083 0.7526 121.67 Caltech-101 0.7889 0.6688 0.7239 151.92
14 Hình 2.17. Mô hình tìm kiếm ảnh dựa trên cấu trúc KD-Tree lồng nhau Bảng 2.16. So sánh độ chính xác trung bình giữa các cải tiến KD-Tree Hệ tìm COREL Wang Caltech-101 Caltech-256 kiếm ảnh SB-KDT 0.7998 0.7810 0.7101 0.7020 SB-iKDT - 0.8010 0.7769 0.7228 SB-NKDT 0.8120 0.8029 0.7889 - Bảng 2.17. So sánh thời gian tìm kiếm trung bình các cải tiến KD-Tree Hệ tìm COREL Wang Caltech-101 Caltech-256 kiếm ảnh SB-KDT 96.77 87.00 122.25 136.89 SB-iKDT - 101.36 109.84 134.91 SB-NKDT 109.49 121.67 151.92 - Hình 2.20 – 2.22 là precision, recall và đường cong ROC của các tập ảnh thực nghiệm trên các hệ SB-KDT, SB-iKDT và SB-NKDT. Hình 2.20. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh COREL, Wang trên các hệ tìm kiếm ảnh
15 Hình 2.22. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Caltech-101, Caltech-256 trên các hệ tìm kiếm ảnh 2.5. Tổng kết chương Trong chương này, một số kết quả đạt được là đề xuất các cải tiến cấu trúc KD-Tree cho bài toán tìm kiếm ảnh gồm: cấu trúc KD-Tree đa nhánh cân bằng, iKD_Tree và KD-Tree lồng nhau. Một số thuật toán xây dựng, huấn luyện, tìm kiếm trên các cấu trúc KD-Tree, iKD_Tree và KD-Tree lồng nhau cũng được đề xuất. Từ đó xây dựng các hệ tìm kiếm ảnh SB-KDT, SB-iKDT và SB-NKDT. Chương 3. PHÁT TRIỂN KD-TREE THEO TIẾP CẬN NGỮ NGHĨA 3.1. Giới thiệu Chương này trình bày mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa trên các bộ ảnh đa đối tượng dựa trên ảnh phân đoạn và mối quan hệ đối tượng. Để thực hiện công việc này cấu trúc KD-Tree được phát triển theo tiếp cận ngữ nghĩa gọi là Re KD-Tree nhằm phân lớp mối quan hệ giữa các đối tượng, từ đó làm cơ sở phát triển Ontology. Cấu trúc Ontology được xây dựng và bổ sung dữ liệu dựa trên các thuộc tính ảnh đối tượng và mối quan hệ giữa các đối tượng. 3.1.1. Xây dựng cấu trúc RF KD-Tree Rừng ngẫu nhiên RF KD-Tree [CT6] được xây dựng gồm các bước: (1) tạo các bộ dữ liệu 𝐷𝑎𝑡𝑎 𝑖 gồm 𝑛 𝑖 phần tử ngẫu nhiên từ tập
16 dữ liệu gốc có 𝑛 phần tử; (2) xây dựng KD-Tree cho từng bộ 𝐷𝑎𝑡𝑎 𝑖 ; (3) tổng hợp 𝑁 cấu trúc KD-Tree hình thành RF KD-Tree. 3.1.2. Huấn luyện RF KD-Tree Quá trình huấn luyện trọng số trên RF KD-Tree giúp cho kết quả phân lớp hình ảnh thu được tốt hơn. Huấn luyện RF KD-Tree được thực hiện theo quá trình huấn luyện trọng số song song trên nhiều cấu trúc KD-Tree độc lập. Mỗi KD-Tree được huấn luyện theo phương pháp giảm sai số trung bình phân lớp ảnh. Sau khi huấn luyện RF KD- Tre là quá trình tổng hợp thành KD-Tree cho tìm kiếm ảnh giúp nâng cao độ chính xác tìm kiếm ảnh. 3.2. Ontology cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa 3.2.1. Cấu trúc Re KD-Tree Hình 3.2. Mô tả cấu trúc Re KD-Tree Cấu trúc Re KD-Tree cho phân lớp mối quan hệ các đối tượng trên ảnh được minh họa như Hình 3.2. 3.2.2. Phân lớp mối quan hệ các đối tượng bằng Re KD-Tree
17 Mỗi ảnh (𝐼) được phân đoạn thành các ảnh đối tượng (𝐼1 , . . , 𝐼 𝑘 ) và trích xuất véc-tơ đặc trưng (𝑓𝐼1 , . . , 𝑓𝐼𝑘 ); kết hợp từng cặp thành véc-tơ 𝑓𝐼𝑗𝑘 = (𝑓𝐼𝑗 , 𝑓𝐼𝑘 ) làm dữ liệu đầu vào Re KD-Tree và lưu trữ tại nút lá. Mỗi nút lá lưu một từ chỉ mối quan hệ, từ đó làm cơ sở trích xuất mối quan hệ ngữ nghĩa các đối tượng trên ảnh bằng Re KD-Tree [CT5]. 3.2.3. Mô tả cấu trúc và xây dựng Ontology Mỗi hình ảnh được phân đoạn theo số đối tượng trên ảnh tạo thành các ảnh đối tượng. Cấu trúc Ontology được xây dựng gồm thuộc tính ảnh đối tượng và mối quan hệ giữa các đối tượng theo các bước sau: Bước 1. Phân đoạn ảnh thành ảnh đối tượng (Object Image). Bước 2. Phân lớp ảnh đối tượng theo các lớp (Class) và phân cấp lớp (Classes – SuperClass). Bước 3. Trích xuất thông tin ảnh đối tượng (Object Properties). Bước 4. Bổ sung các mối quan hệ giữa các cặp đối tượng vào Ontology (Relationships). 3.3. Hệ truy tìm kiếm ảnh dựa trên Re KD-Tree và Ontology Hình 3.17. Mô hình tìm kiếm ảnh dựa trên Re KD-Tre và Ontology
18 Bảng 3.1. Kết quả tìm kiếm ảnh hệ SR-KDT [CT5] Thời gian tìm Tập ảnh Precision Recall F-measure kiếm (ms) MS-COCO 0.6972 0.6636 0.6799 215 Flickr 0.7794 0.6788 0.7256 126 3.4. Hệ tìm kiếm ảnh dựa trên RF KD-Tree Hình 3.20. Mô hình tìm kiếm ảnh dựa trên RF KD-Tree (SR-KDF) Bảng 3.4. Kết quả thực nghiệm hệ tìm kiếm ảnh SR-KDF [CT6] Tập ảnh Precision Recall F-measure Query time (ms) MS-COCO 0.9028 0.8273 0.8634 101.61 Flickr 0.9163 0.8975 0.9068 72.28 3.5. Hệ tìm kiếm ảnh dựa trên KD-Tree và Ontology Bảng 3.7. Kết quả thực nghiệm hệ tìm kiếm ảnh SO-KDT Tập ảnh Precision Recall F-measure Query time (ms) MS-COCO 0.9218 0.8372 0.8774 105.90 Flickr 0.9370 0.8939 0.9149 89.20