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Ế

ửa

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

LUẬN ÁN TIẾN SĨ NGÀNH KHOA HỌC MÁY TÍNH

HUẾ, NĂM 2023

ĐẠ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

PGS. TS. LÊ MẠNH THẠNH

TS. VĂN THẾ THÀNH

HUẾ, NĂM 2023

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các nội dung tham

khảo từ các công trình khác đều được trích dẫn rõ ràng. Các kết quả viết chung với các

tác giả khác đều được sự đồng ý trước khi đưa vào luận án. Các kết quả của luận án là

trung thực và chưa được công bố trong các công trình khác ngoài các công trình của

tác giả.

Tác giả

Nguyễn Thị Định

LỜI CÁM ƠN

Đầu tiên, tôi xin chân thành gửi lời cảm ơn đến Thầy PGS. TS. Lê Mạnh Thạnh

và Thầy TS. Văn Thế Thành đã tận tình hướng dẫn, động viên, giúp đỡ tôi trong suốt

quá trình nghiên cứu để hoàn thành luận án này. Bên cạnh đó, tôi còn nhận được sự hỗ

trợ đầy nhiệt tình của các Thầy, Cô Khoa Công nghệ Thông tin đã trang bị thêm kiến

thức, góp ý cho tôi thực hiện các chuyên đề và trao đổi các ý kiến quý báu cho bản

thảo của luận án. Tôi xin ghi nhận và cảm ơn sâu sắc đến sự giúp đỡ quý báu này.

Tôi xin chân thành cảm ơn đến Phòng Đào tạo Sau Đại học, Ban Giám hiệu của

Trường Đại học Khoa học, Đại học Huế đã tạo điều kiện thuận lợi cho tôi trong suốt

quá trình học tập, nghiên cứu và thực hiện luận án.

Tôi xin gửi lời cảm ơn đến Ban Giám hiệu Trường Đại học Công nghiệp Thực

phẩm Tp. HCM; Ban Chủ nhiệm Khoa Công nghệ Thông tin, các đồng nghiệp là cán

bộ, giảng viên Trường Đại học Công nghiệp Thực phẩm Tp. HCM đã luôn tạo điều

kiện, cổ vũ động viên tôi trong quá trình học tập và nghiên cứu. Tôi xin gửi lời cảm ơn

đến tất cả bạn bè và những người xung quanh đã chia sẻ, động viên trong những lúc

khó khăn.

Xin bày tỏ lòng biết ơn vô hạn đến gia đình thân yêu, Ba mẹ hai bên, chồng và

các con đã hỗ trợ, ủng hộ, động viên để con/em/mẹ yên tâm quá trình học tập, nghiên

cứu.

Tác giả

Nguyễn Thị Định

MỤC LỤC

LỜI CAM ĐOAN ......................................................................................................... i

LỜI CÁM ƠN .............................................................................................................. ii

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ............................................................. v

DANH MỤC HÌNH ẢNH ....................................................................................... viii

DANH MỤC BẢNG BIỂU ......................................................................................... x

PHẦN MỞ ĐẦU .......................................................................................................... 1

1.1. Giới thiệu ........................................................................................................................ 9

1.2. Tìm kiếm ảnh theo nội dung ......................................................................................... 11

1.2.1. Đặc trưng hình ảnh và trích xuất véc-tơ đặc trưng ................................................ 11

1.2.2. Độ tương tự giữa hai hình ảnh ............................................................................... 17

1.3. Tìm kiếm ảnh theo tiếp cận ngữ nghĩa ......................................................................... 18

1.3.1. Đặc trưng ngữ nghĩa .............................................................................................. 18

1.3.2. Mối quan hệ ngữ nghĩa .......................................................................................... 20

1.3.3. Các phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa ...................................... 21

1.4. Tìm kiếm ảnh dựa trên cấu trúc KD-Tree..................................................................... 22

1.4.1. Cấu trúc KD-Tree cho tìm kiếm ảnh ..................................................................... 22

1.4.2. Phân lớp hình ảnh dựa trên cấu trúc KD-Tree ....................................................... 23

1.4.3. Phân lớp mối quan hệ ngữ nghĩa dựa trên cấu trúc KD-Tree ................................ 24

1.4.4. Tìm kiếm ảnh dựa trên cấu trúc KD-Tree ............................................................. 24

1.5. Phương pháp thực nghiệm và đánh giá ......................................................................... 26

1.5.1. Môi trường và dữ liệu thực nghiệm ....................................................................... 26

1.5.2. Các đại lượng đánh giá hiệu suất ........................................................................... 27

1.6. Tổng kết chương ........................................................................................................... 29

CHƯƠNG 1. TỔNG QUAN VỀ TÌM KIẾM ẢNH VÀ CẤU TRÚC KD-TREE ............................................................................................................ 9

2.2. Cấu trúc KD-Tree đa nhánh cân bằng .......................................................................... 31

2.2.1. Xây dựng cấu trúc KD-Tree .................................................................................. 32

2.2.2. Thuật toán xây dựng cấu trúc KD-Tree ................................................................. 36

2.2.3. Quá trình gán nhãn nút lá ...................................................................................... 37

2.2.4. Huấn luyện trọng số trên cấu trúc KD-Tree .......................................................... 38

2.2.5. Tìm kiếm trên cấu trúc KD-Tree ........................................................................... 41

2.2.6. Hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree ......................................................... 41

2.3. Cấu trúc iKD_Tree ....................................................................................................... 46

CHƯƠNG 2. TÌM KIẾM ẢNH DỰA TRÊN CẤU TRÚC KD-TREE ............ 30 2.1. Giới thiệu ...................................................................................................................... 30

iii

2.3.1. Mô tả cấu trúc iKD_Tree ....................................................................................... 46

2.3.2. Xây dựng cấu trúc iKD_Tree ................................................................................ 47

2.3.3. Hệ tìm kiếm ảnh dựa trên cấu trúc iKD_Tree ....................................................... 50

2.4. Cấu trúc KD-Tree lồng nhau ........................................................................................ 54

2.4.1. Mô tả cấu trúc KD-Tree lồng nhau ........................................................................ 54

2.4.2. Xây dựng cấu trúc KD-Tree lồng nhau ................................................................. 55

2.4.3. Hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree lồng nhau ........................................ 56

2.5. Đánh giá các hệ tìm kiếm ảnh ....................................................................................... 63

2.6. Tổng kết chương ........................................................................................................... 66

3.1. Giới thiệu ...................................................................................................................... 67

3.1.1. Xây dựng cấu trúc RF KD-Tree ............................................................................ 68

3.1.2. Huấn luyện RF KD-Tree ....................................................................................... 69

3.2. Ontology cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa .................................................... 70

3.2.1. Cấu trúc Re KD-Tree ............................................................................................. 70

3.2.2. Phân lớp mối quan hệ các đối tượng bằng Re KD-Tree ........................................ 73

3.2.3. Mô tả cấu trúc và xây dựng Ontology ................................................................... 73

3.2.4. Phân cấp và bổ sung dữ liệu vào Ontology ........................................................... 77

3.2.5. Tìm kiếm trên Ontology ........................................................................................ 79

3.3. Hệ tìm kiếm ảnh dựa trên Re KD-Tree và Ontology .................................................... 81

3.3.1. Mô hình tìm kiếm ảnh dựa trên Re KD-Tree và Ontology.................................... 81

3.3.2. Thực nghiệm và đánh giá ...................................................................................... 83

3.4. Hệ tìm kiếm ảnh dựa trên RF KD-Tree ........................................................................ 85

3.4.1. Mô hình tìm kiếm ảnh dựa trên RF KD-Tree ........................................................ 85

3.4.2. Thực nghiệm và đánh giá ...................................................................................... 87

3.5. Hệ tìm kiếm ảnh dựa trên KD-Tree và Ontology ......................................................... 89

3.5.1. Mô hình tìm kiếm ảnh dựa trên KD-Tree và Ontology ......................................... 89

3.5.2. Thực nghiệm và đánh giá ...................................................................................... 91

3.6. Tổng kết chương ........................................................................................................... 97

CHƯƠNG 3. PHÁT TRIỂN CẤU TRÚC KD-TREE THEO TIẾP CẬN NGỮ .......................................................................................................... 67 NGHĨA

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................... 98

TÀI LIỆU THAM KHẢO ...................................................................................... 101

PHỤ LỤC ................................................................................................................. 108

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT

Diễn giải tiếng Anh Diễn giải tiếng Việt Ký hiệu viết tắt

BST Binary Search Tree Cây tìm kiếm nhị phân

CBIR Content-Based Image Retrieval Tìm kiếm ảnh theo nội dung

CDF Centroid Distance Function Hàm tính khoảng cách trọng tâm

CEO Create Extended Ontology Hàm xây dựng Ontology mở rộng

CiKDT Create iKD_Tree Thuật toán tạo iKD_Tree

CKDT Create KD-Tree Thuật toán tạo KD-Tree

CLiKD Classification on iKD_Tree Hàm phân lớp ảnh trên iKD_Tree

CLRKD Relationship

Classification using Relationship KD-Tree Hàm phân lớp mối quan hệ bằng Re KD- Tree

CNKDT Create Nested KD-Tree Thuật toán tạo KD-Tree lồng nhau

CNN Convolutional Neural Network Mạng nơ-ron tích chập

CRFKD Thuật toán tạo RF KD-Tree Create Random Forest KD- Tree

Create SPARQL Query Hàm tạo câu truy vấn SPARQL CSQ

DCD Dominant Color Descriptor Bộ mô tả màu chủ đạo

DCL Deep Convolutional Learning Mạng tích chập học sâu

DNN Deep Neural Network Mạng nơ-ron học sâu

DoG Difference of Gaussian Đạo hàm Gaussian

GLCM Co-occurrence Ma trận đồng xuất hiện mức xám Gray-level Matrix

HOG of Oriented Biểu đồ định hướng Gradients Histograms Gradients

iKD_Tree Cấu trúc KD-Tree cải tiến Improvement k-Dimensional Tree

IR Image Retrieval Tìm kiếm ảnh

KD-Tree k-Dimensional Tree Cấu trúc cây đa chiều

KG Knownledge Graph Đồ thị tri thức

kMiKDT K-Means on iKD_Tree Hàm tích hợp K-Means trên iKD_Tree

k-NN k - Nearest Neighbors Thuật toán tìm kiếm theo k láng giềng gần nhất

LoG Laplace of Gaussian Phép biến đổi Laplace Gaussian

MAP Mean Average Precision Độ chính xác trung bình

MRI Magnetic Resonance Imaging Ảnh y khoa MRI

NN Nearest Neighbors Láng giềng gần nhất

R-CNN Region-based Convolutional Neural Networks Mạng Nơ-ron tích chập dựa trên vùng đối tượng

Re KD-Tree Relationship k-Dimensional Cấu trúc KD-Tree phân lớp mối quan hệ Tree

RF Relevance Feedback Phương pháp phản hồi liên quan

RF KD-Tree Random Forest KD-Tree Cấu trúc rừng ngẫu nhiên KD-Tree

RNN Range Nearest Neighbors Kỹ thuật tìm kiếm láng giềng theo vùng

ROC Operating Đồ thị đặc tính Receiver Characteristic

SB-iKDT Image Hệ tìm kiếm ảnh sử dụng iKD_Tree

Semantic-based Retrieval using iKD_Tree

SBIR Image Tìm kiếm ảnh theo ngữ nghĩa Semantic-Based Retrieval

SB-KDT Image Hệ tìm kiếm ảnh sử dụng KD-Tree Semantic-based Retrieval using KD-Tree

SB-NKDT Hệ tìm kiếm ảnh sử dụng KD-Tree lồng nhau Semantic-based Image Retrieval using Nested KD- Tree

SG Scene Graph Đồ thị ngữ cảnh

SIFT Invariant Features Đặc trưng bất biến SIFT Scale Transform

SiKDT Search on iKD_Tree Thuật toán tìm kiếm ảnh trên iKD_Tree

SKDO on KD-Tree and Search Ontology Thuật toán tìm kiếm trên KD-Tree và Ontology

SKDT Search on KD-Tree Hàm tìm kiếm trên KD-Tree

SL2L Set Label To Leaf Hàm gán nhãn nút lá

SNKDT Search on Nested KD-Tree Thuật toán tìm kiếm trên KD-Tree lồng nhau

SO-KDT Hệ tìm kiếm ảnh theo ngữ nghĩa sử dụng KD-Tree và Ontology Semantic-based Image Retrieval using KD-Tree and Ontology

Image Hệ tìm kiếm ảnh sử dụng RF KD-Tree SR-KDF

Semantic-based Retrieval using RF KD-Tree

SR-KDT

Hệ tìm kiếm ảnh theo ngữ nghĩa sử dụng Re KD-Tree Image Semantic-based Retrieval using Relationship KD-Tree

SRKO

Thuật toán tìm kiếm ảnh sử dụng Re KD-Tree và Ontology Semantic-based Image Retrieval using KD-Tree and Ontology

SRRE Thuật toán tìm kiếm ảnh sử dụng Re KD-Tree Semantic-based Image Retrieval using Relationship KD-Tree

SRRF Thuật toán tìm kiếm ảnh sử dụng RF KD-Tree Semantic-based Image Retrieval using Random Forest KD-Tree

Support Vector Machine Máy véc-tơ hỗ trợ SVM

Text-Based Image Retrieval Tìm kiếm ảnh theo từ khóa TBIR

TVKD Training Véc-tơ on KD-Tree

Thuật toán huấn luyện véc-tơ trọng số trên KD-Tree

TWRF

Train Weight Random Forest KD-Tree Hàm huấn luyện trọng số trên RF KD- Tree

WWW Word Wide Web Mạng toàn cầu

vii

DANH MỤC HÌNH ẢNH

Hình 1.1. Minh họa trích xuất véc-tơ đặc trưng 81 chiều [CT1] ................................ 15

Hình 1.2. Minh họa trích xuất véc-tơ đặc trưng 189, 225 và 513 chiều ..................... 17

Hình 1.3. Mô tả đặc trưng ngữ nghĩa của hình ảnh [48] ............................................. 19

Hình 1.4. Xác định mối quan hệ không gian giữa các đối tượng bằng SG [46] ......... 20

Hình 1.5. Xác định mối quan hệ không gian giữa các đối tượng bằng KD-Tree ....... 21

Hình 1.6. Mô hình tìm kiếm ảnh theo nội dung dựa trên cấu trúc KD-Tree ............... 25

Hình 1.7. Mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên KD-Tree ............. 25

Hình 2.1. Mô tả các thành phần nút gốc, nút trong và nút lá trên KD-Tree ............... 33

Hình 2.2. Minh họa quá trình tạo nhánh con tại 𝐍𝐨𝐝𝐞𝐢 .............................................. 34

Hình 2.3. Cấu trúc KD-Tree đa nhánh, cân bằng ........................................................ 35

Hình 2.4. Mô hình xây dựng và huấn luyện KD-Tree theo từng 𝐄𝐩𝐨𝐜𝐡 dữ liệu ....... 39

Hình 2.5. Minh họa tập véc-tơ phân lớp trên KD-Tree cho bộ ảnh COREL ...... 40

Hình 2.6. Mô hình tìm kiếm ảnh dựa trên KD-Tree (SB-KDT) ........................... 42

Hình 2.7. Minh họa quá trình xây dựng tập từ thị giác ............................................... 43

Hình 2.8. Minh họa câu truy vấn SPARQL ................................................................ 44

Hình 2.9. Hệ tìm kiếm ảnh SB-KDT ........................................................................... 44

Hình 2.10. Kết quả tập ảnh tương tự của ảnh COREL101.jpg hệ SB-KDT ............... 45

Hình 2.11. Minh họa cấu trúc iKD_Tree .................................................................... 47

Hình 2.12. Minh họa thuật toán K-Means trên iKD_Tree .......................................... 47

Hình 2.13. Mô hình tìm kiếm ảnh dựa trên cấu trúc iKDTree [CT3] ......................... 50

Hình 2.14. Hệ tìm kiếm ảnh SB-iKDT ........................................................................ 52

Hình 2.15. Kết quả tập ảnh tương tự với ảnh 52011.jpg (Wang) hệ SB-iKDT .......... 52

Hình 2.16. Minh họa cấu trúc KD-Tree lồng nhau [CT4] .......................................... 54

Hình 2.17. Mô hình tìm kiếm ảnh dựa trên KD-Tree lồng nhau (SB-NKDT) [CT4] . 56

Hình 2.18. Hệ tìm kiếm ảnh SB-NKDT ...................................................................... 58

Hình 2.19. Tập ảnh tương tự với ảnh 500.jpg [20] hệ SB-NKDT .............................. 58

Hình 2.20. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh COREL của hệ tìm kiếm ảnh SB-KDT và SB-NKDT ......................................................................... 61

Hình 2.21. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Wang của hệ tìm kiếm ảnh SB-KDT, SB-iKDT và SB-NKDT .............................................................. 61

Hình 2.22. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Caltech-101 của hệ tìm kiếm ảnh SB-KDT, SB-iKDTvà SB-NKDT .................................................... 62

viii

Hình 2.23. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Caltech-256 của hệ tìm kiếm ảnh SB-KDT và SB-iKDT ...................................................................... 62

Hình 3.1. Mô tả cấu trúc RF KD-Tree ........................................................................ 68

Hình 3.2. Mô tả cấu trúc Re KD-Tree ......................................................................... 72

Hình 3.3. Minh họa ảnh đối tượng trích xuất từ ảnh gốc 1001773457.jpg (Flickr) .... 72

Hình 3.4. Minh họa cấu trúc Ontology ........................................................................ 74

Hình 3.5. Cách tổ chức dữ liệu phân cấp lớp và lớp con trong bộ ảnh MS-COCO .... 75

Hình 3.6. Cấu trúc Class, SuperClass được bổ sung vào Ontology ............................ 75

Hình 3.7. Cấu trúc ảnh đối tượng sau khi phân đoạn và phân lớp ...................... 76

Hình 3.8. Minh họa cấu trúc ảnh đối tượng theo phân lớp ......................................... 76

Hình 3.9. Mô tả các thành phần ảnh đối tượng trên bộ ảnh Flickr ............................. 76

Hình 3.10. Cấu trúc Class, SuperClass trên bộ ảnh MS-COCO ................................. 77

Hình 3.11. Mô hình bổ sung dữ liệu vào Ontology tập ảnh đa đối tượng .................. 78

Hình 3.12. Minh họa Ontology bộ ảnh MS-COCO dạng N3 ...................................... 78

Hình 3.13. Minh họa câu truy vấn SPARQL từ ảnh đối tượng và mối quan hệ ......... 79

Hình 3.14. Tìm kiếm cho các ảnh đối tượng thuộc một cụm ................................ 80

Hình 3.15. Tìm kiếm cho các ảnh đối tượng thuộc nhiều cụm ................................... 80

Hình 3.16. Một kết quả tìm kiếm trên Ontology theo ID ảnh ..................................... 81

Hình 3.17. Mô hình tìm kiếm ảnh dựa trên Re KD-Tree và Ontology (SR-KDT) ..... 82

Hình 3.18. Hệ tìm kiếm ảnh SR-KDT ......................................................................... 83

Hình 3.19. Kết quả tập ảnh tương tự hệ SR-KDT (000000183675.jpg, MS-COCO) . 84

Hình 3.20. Mô hình tìm kiếm ảnh dựa trên RF KD-Tree (SR-KDF) .......................... 86

Hình 3.21. Hệ tìm kiếm ảnh SR-KDF ......................................................................... 87

Hình 3.22. Kết quả tập ảnh tương tự hệ SR-KDF (000000100510.jpg, MS-COCO) . 88

Hình 3.23. Mô hình tìm kiếm ảnh dựa trên KD-Tree và Ontology (SO-KDT) .......... 90

Hình 3.24. Hệ tìm kiếm ảnh SO-KDT ........................................................................ 92

Hình 3.25. Kết quả tập ảnh tương tự hệ SO-KDT (11205420.jpg, Flickr) ................. 92

Hình 3.26. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh MS-COCO của hệ tìm kiếm ảnh SR-KDT, SR-KDF và SO-KDT ....................................................... 94

Hình 3.27. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Flickr của hệ tìm kiếm ảnh SR-KDT, SR-KDF và SO-KDT .................................................................. 94

DANH MỤC BẢNG BIỂU

Bảng 1.1. Các giá trị véc-tơ đặc trưng hình ảnh (81 chiều) ........................................ 15

Bảng 1.2. Các giá trị véc-tơ đặc trưng được trích xuất (225 và 513 chiều) ................ 16

Bảng 1.3. Mô tả các bộ dữ liệu ảnh thực nghiệm ........................................................ 27

Bảng 1.4. Mô tả bộ ảnh đa đối tượng .......................................................................... 27

Bảng 2.1. Chi phí huấn luyện KD-Tree trên các bộ ảnh thực nghiệm ........................ 41

Bảng 2.2. Kết quả tìm kiếm ảnh tương tự hệ SB-KDT [CT2] .................................... 45

Bảng 2.3. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh COREL (SB-KDT) ......... 45

Bảng 2.4. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-KDT) ............ 45

Bảng 2.5. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-KDT) .. 46

Bảng 2.6. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-256 (SB-KDT) .. 46

Bảng 2.7. Kết quả tìm kiếm ảnh của hệ SB-iKDT ...................................................... 53

Bảng 2.8. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-iKDT) ........... 53

Bảng 2.9. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-iKDT) . 53

Bảng 2.10. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-256 (SB-iKDT) 53

Bảng 2.11. Điều kiện để nút lá phát triển thành SubTree ........................................... 55

Bảng 2.12. Kết quả tìm kiếm ảnh của hệ SB-NKDT .................................................. 59

Bảng 2.13. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh COREL (SB-NKDT) .... 59

Bảng 2.14. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-NKDT) ........ 59

Bảng 2.15. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-NKDT) ..................................................................................................................................... 60

Bảng 2.16. So sánh độ chính xác trung bình giữa các cải tiến cấu trúc KD-Tree ...... 63

Bảng 2.17. So sánh thời gian tìm kiếm trung bình (ms) giữa các cải tiến KD-Tree ... 63

Bảng 2.18. So sánh các phương pháp tìm kiếm ảnh sử dụng KD-Tree với những đề xuất trong luận án ........................................................................................................ 65

Bảng 3.1. Kết quả tìm kiếm ảnh hệ SR-KDT [CT5] ................................................... 84

Bảng 3.2. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh MS-COCO (SR-KDT) .... 84

Bảng 3.3. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Flickr (SR-KDT) ............ 85

Bảng 3.4. Kết quả thực nghiệm hệ tìm kiếm ảnh SR-KDF ......................................... 88

Bảng 3.5. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh MS-COCO (SR-KDF) .... 88

Bảng 3.6. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Flickr (SR-KDF) ............. 89

Bảng 3.7. Kết quả thực nghiệm hệ tìm kiếm ảnh SO-KDT ........................................ 91

Bảng 3.8. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh MS-COCO (SO-KDT) .... 92

Bảng 3.9. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Flickr (SO-KDT) ............ 93

Bảng 3.10. So sánh kết quả giữa các hệ tìm kiếm ảnh đề xuất .................................. 93

Bảng 3.11. So sánh độ chính xác tìm kiếm ảnh giữa các phương pháp đề xuất ........ 95

Bảng 3.12. So sánh các phương pháp tìm kiếm ảnh theo ngữ nghĩa với những đề xuất trong luận án ................................................................................................................ 96

PHẦN MỞ ĐẦU

1. Tính cấp thiết của luận án

Việc số hóa dữ liệu đa phương tiện đã tạo ra các dữ liệu lớn là thách thức cho

bài toán tìm kiếm ảnh về các yêu cầu khả năng lưu trữ, độ chính xác và thời gian tìm

kiếm. Điều đó đã thúc đẩy sự ra đời của nhiều hệ tìm kiếm ảnh được thực hiện theo

nhiều phương pháp khác nhau nhằm nâng cao độ chính xác, thời gian tìm kiếm ổn

định đáp ứng nhu cầu người dùng [75], [77].

Sự đa dạng của ảnh số về thể loại cũng là một thách thức cho bài toán tìm kiếm

ảnh. Vì vậy, một số cấu trúc được đề xuất như KD-Tree [84], S-Tree [38], C-Tree

[52], v.v. đáp ứng nhu cầu đa dạng của dữ liệu là cấp thiết cho bài toán tìm kiếm ảnh.

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 về 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 đa chiều và

thời gian tìm kiếm ổn định. Quá trình đưa các kỹ thuật học máy vào cấu trúc KD-

Tree đã mang lại hiệu quả tìm kiếm ảnh cao hơn so với một số phương pháp khác.

2. Tổng quan tình hình nghiên cứu

Bài toán tìm kiếm ảnh đã được nghiên cứu và thực hiện bởi nhiều phương pháp

khác nhau nhằm nâng cao độ chính xác đáp ứng nhu cầu người dùng. Một số công

trình tìm kiếm ảnh được khảo sát trong luận án, bao gồm:

Tìm kiếm ảnh sử dụng các kỹ thuật phân lớp và phân cụm

Erwin và cộng sự [26] đề xuất hệ thống nhận dạng trái cây qua hình ảnh bằng

cách kết hợp các thuật toán K-Means, k-NN để thực hiện phân lớp và gom cụm đặc

trưng hình ảnh trước khi nhận diện đối tượng. Kết quả thực nghiệm phân lớp hình

ảnh đạt được độ chính xác 92,5% cho ảnh đơn đối tượng và 90% cho ảnh đa đối

tượng. Tuy nhiên, hệ thống chỉ nhận diện trên các bộ ảnh về trái cây; thuật toán K-

Means được áp dụng theo phương pháp cập nhật tâm cụm khi dữ liệu thay đổi, chưa

xử lý trường hợp số lượng láng giềng có số phân lớp bằng nhau trong thuật toán k-

NN. Vì vậy, Shichao Kan và cộng sự [34] đã đề xuất phương pháp học có giám sát

dùng thuật toán k-NN cải tiến để phân lớp hình ảnh, quá trình gán lại nhãn cho các

ảnh huấn luyện được đề xuất nhằm thiết lập mối quan hệ giữa các nhãn lớp. Kết quả

thực nghiệm của hệ thống dùng phương pháp học có giám sát để tạo chỉ mục cho kết

quả tốt hơn mô hình sử dụng phương pháp học không giám sát trên cùng bộ dữ liệu

thử nghiệm. Sau đó, Shuang Jia và cộng sự [33] sử dụng thuật toán gom cụm K-

Means để thực hiện tìm kiếm ảnh. Mỗi hình ảnh đầu vào được trích xuất đặc trưng và

tính độ tương tự dựa trên đặc trưng túi từ để tìm tập ảnh tương tự. Trong phương pháp

này, các túi từ là độc lập và chưa phân lớp được theo nội dung của mỗi ảnh đầu vào.

Kỹ thuật học sâu được ứng dụng cho nhiều công trình tìm kiếm ảnh, cụ thể là:

R. Rani và cộng sự [64] đã xây dựng mô hình tìm kiếm ảnh sử dụng kỹ thuật học sâu

Deep Learning. Hình ảnh được trích xuất đặc trưng và phân lớp đối tượng bằng kỹ

thuật DBN (Deep Belief Network). Phương pháp đề xuất được thực nghiệm thông qua

mô phỏng so sánh, kết quả cho thấy độ lệch dương rất lớn với hiệu suất của hệ thống.

Bên cạnh đó, Maria Tzelepi và cộng sự (2018) [70] đã tiếp cận kỹ thuật DCL cho bài

toán tìm kiếm ảnh. Mô hình CNN được sử dụng để huấn luyện lại cho tập dữ liệu

thực nghiệm. Kết quả huấn luyện trên các bộ dữ liệu độc lập đã chứng minh tính hiệu

quả của phương pháp đề xuất là khá tốt. Pouria Sadeghi-Tehran [63] đã thực hiện một

phương pháp đánh chỉ mục cho cơ sở dữ liệu tìm kiếm dựa vào kỹ thuật Deep

Learning và cấu trúc cây phân cấp lồng nhau. Ngoài ra, tác giả đưa ra sơ đồ tối ưu

hóa tìm kiếm dựa vào cấu trúc phân cấp lồng nhau và độ đo tương tự [63].

Tìm kiếm ảnh dựa trên cấu trúc cây

Một số cấu trúc cây sử dụng cho bài toán tìm kiếm ảnh với hiệu suất cao như C-

Tree [52], S-Tree [38], KD-Tree [30], [59]. Trong đó, cấu trúc KD-Tree được đề xuất

ở một số công trình như: Wenfeng Hou và cộng sự (2018) [30] thực hiện phân lớp dữ

liệu bằng thuật toán láng giềng k-NN trên cây KD-Tree. Để cải thiện những nhược

điểm của thuật toán k-NN, tác giả đã kết hợp k-NN và cấu trúc dữ liệu KD-Tree nhằm

giảm thời gian tìm kiếm và nâng cao độ chính xác tìm kiếm gọi là cấu trúc kNN-

KDTree. Kết quả thực nghiệm trên 11 bộ dữ liệu ảnh cho thấy sự kết hợp giữa k-NN

và KD-Tree đã mang lại hiệu suất cao hơn so với việc dùng kỹ thuật k-NN đơn lẻ.

Parikshit Ram và cộng sự [59] sử dụng kỹ thuật tìm kiếm láng giềng k-NN dựa

trên cấu trúc KD-Tree. Việc kết hợp này nhằm cải tiến hiệu suất tìm kiếm bằng cách

xây dựng cây phân vùng không gian ngẫu nhiên để thực hiện các lược đồ tìm kiếm

theo cấu trúc KD-Tree. Yewang Chen và cộng sự [16] đã sử dụng hai kỹ thuật tìm

kiếm láng giềng RNN (Range Nearest Neighbors) và NN (Nearest Neighbors) dựa

trên cây KD-Tree. Trong đó, kỹ thuật RNN nhằm giảm các tính toán khoảng cách

không cần thiết bằng cách kiểm tra vị trí của đối tượng đang xét nằm bên trong hay

bên ngoài vùng lân cận của điểm cần tìm. Kỹ thuật NN được sử dụng để giảm các nút

truy cập dư thừa bằng cách lưu chỉ số truy cập các điểm láng giềng. Thực nghiệm

chứng minh cho việc kết hợp các thuật toán tìm kiếm láng giềng RNN, NN và k-NN

trên cấu trúc KD-Tree hiệu quả.

Fengquan Zhang [83] và cộng sự đã xây dựng cấu trúc Vocabulary-KDTree

nhằm thực hiện bài toán đối sánh hình ảnh. Cấu trúc này được chia thành hai nhóm:

(1) nhóm chứa các đặc trưng hình ảnh; (2) nhóm các nút lá cùng với việc điều chỉnh

các trọng số liên quan quá trình huấn luyện để xây dựng cấu trúc Vocabulary-KDTree.

Reid Pinkham và cộng sự (2020) [54] đã thực hiện một phương pháp tối ưu bộ

nhớ và tăng tốc độ tìm kiếm trên KD-Tree. Cấu trúc KD-Tree được xây dựng gồm

các bước: (1) dữ liệu được lưu vào bộ nhớ đệm nhằm tạo điều kiện tìm kiếm nhanh;

(2) quá trình đọc ghi trên bộ nhớ đệm được thêm vào để thực hiện truy cập ngẫu nhiên

để chuyển thành truy cập tuần tự; (3) xây dựng cấu trúc KD-Tree và tìm kiếm được

thực hiện xen kẽ với các luồng truy cập dư thừa, băng thông được tối ưu hóa hỗ trợ

quá trình tìm kiếm.

Mahesha D. M và cộng sự [43] thực hiện bài toán tìm kiếm ảnh theo nội dung

sử dụng cấu trúc Distributed KD-Tree là cấu trúc đa nhánh, cân bằng trên cơ sở phát

triển KD-Tree nhị phân. Distributed KD-tree được xây dựng trên cơ sở phân tách nút

gốc thành các nhánh con và đệ quy đến các tầng kế tiếp. Quá trình tìm kiếm trên

Distributed KD-tree được thực hiện từ nút gốc đến nút lá dựa vào 𝑘 láng giềng của

phần tử tìm kiếm để xác định nút lá chứa tập ảnh tương tự với ảnh đầu vào. Bên cạnh

đó, dữ liệu lưu trữ trên Distributed KD-tree theo phương pháp lập chỉ mục nên quá

trình tìm kiếm nhanh và hiệu quả.

Tìm kiếm ảnh theo tiếp cận ngữ nghĩa

Tìm kiếm ảnh theo tiếp cận ngữ nghĩa sử dụng ontology là một trong những

hướng tiếp cận mang lại nhiều kết quả khả quan trong thập niên vừa qua, một số công

trình tiêu biểu như: Manzoor và công sự [44] đã đề xuất một phương pháp tìm kiếm

ảnh theo ngữ nghĩa dựa trên ontology để truy 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 cũng như các đặc

trưng thị giác dựa trên đồ thị. Kết quả thực nghiệm cho thấy hệ thống đã có những

cải tiến so với phương pháp tìm kiếm ảnh dựa trên nội dung, góp phần làm tăng độ

chính xác. Bên cạnh đó, Zahid Medmood và cộng sự [46], thực hiện bài toán tìm kiếm

ảnh dựa trên nội dung và phân tích ngữ nghĩa hình ảnh; từ đó, nhóm tác giả sử dụng

tập từ thị giác nhằm mô tả ngữ nghĩa hình ảnh. Trong công trình này, nhóm tác giả

ứng dụng kỹ thuật từ điển dữ liệu để ánh xạ giữa ngữ nghĩa thị giác và đặc trưng hình

ảnh. Tuy nhiên, nhóm tác giả chưa thực hiện tìm kiếm bằng cách tạo câu truy vấn

SPARQL.

Binbin Yu và cộng sự [81], đã đề xuất một cấu trúc ontology cho lưu trữ và truy

xuất tài liệu văn bản dựa trên phân tích ngữ nghĩa văn bản. Nhóm tác giả đã thực

nghiệm bằng cách trích xuất các khái niệm từ (word concepts) dựa vào 1000 bài báo

khoa học để đưa vào ontology, tạo ra các khái niệm, literals gồm 10 nhóm, mỗi nhóm

có 100 bài báo. Tuy nhiên, công trình chưa áp dụng cho bài toán tìm kiếm hình ảnh,

chưa đề xuất mô hình xây dựng ontology nhằm khai thác dữ liệu. Đồng thời, M. N.

Asim và cộng sự [7], đã thực hiện bài toán truy xuất thông tin văn bản và dữ liệu đa

phương tiện (hình ảnh, video, audio) dựa trên ontology. Nhóm tác giả đã so sánh hiệu

suất với các phương pháp tiếp cận trước đó về tìm kiếm văn bản, dữ liệu đa phương

tiện. Tác giả sử dụng ngôn ngữ bộ ba RDF để lưu trữ dữ liệu và truy vấn trên ontology.

Tuy nhiên, tác giả mới đề xuất mô hình sử dụng onotology để tìm kiếm dữ liệu ảnh

đa đối tượng, chưa đề cập đến kết quả thực nghiệm để so sánh với các công trình

trước đó.

Botao Zhong và cộng sự [86] đã đề xuất phương pháp xác định mối quan hệ

giữa các đối tượng trên hình ảnh thông qua chú thích và đặc trưng của hình ảnh.

Nhóm tác giả đã xây dựng một khung ontology để truy xuất mối quan hệ của hình

ảnh thực hiện trên protégé nhằm phân lớp các ảnh đối tượng, phân lớp các thuộc tính,

xác định mối quan hệ giữa các lớp hình ảnh và lớp đối tượng; đồng thời kết hợp các

nguyên tắc phân lớp để xây dựng mối quan hệ giữa các đối tượng trên hình ảnh. Đây

chính là cơ sở xây dựng ontology mở rộng cho bài toán tìm kiếm ảnh đa đối tượng

dựa trên mối quan hệ giữa các đối tượng hình ảnh.

Ở Việt Nam có một số nhóm nghiên cứu về tìm kiếm ảnh đã có nhiều công bố

với kết quả tốt về tìm kiếm ảnh thực hiện bằng phương pháp phản hồi liên quan, ứng

dụng học sâu để huấn luyện mô hình phân lớp ảnh và dự đoán bệnh trên cây trồng

bằng hình ảnh, tìm kiếm ảnh sử dụng ontology [51]. Một số công trình đã ứng dụng

vào các lĩnh vực của đời sống con người như chẩn đoán bệnh ung thư qua hình ảnh

và một số lĩnh vực khác.

Trên cơ sở khảo sát các công trình nghiên cứu liên quan, một số ưu và nhược

điểm đó là:

(1) Thực hiện bài toán tìm kiếm ảnh dựa trên các kỹ thuật học máy, cấu trúc

cây và ontology với hiệu quả khá cao; ứng dụng được cho nhiều bộ ảnh thực nghiệm

trong nhiều lĩnh vực;

(2) Sự kết hợp nhiều kỹ thuật học máy trên mỗi công trình còn hạn chế;

(3) Số công trình kết hợp một cấu trúc dữ liệu lưu trữ và học máy còn giới hạn;

(4) Sự kết hợp ontology với các kỹ thuật khác để thực hiện qua nhiều bộ lọc

nhằm nâng cao độ chính xác tìm kiếm ảnh chưa thực hiện ở nhiều công trình.

Trên cơ sở này, 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, kết hợp các kỹ thuật

học máy và Ontology cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa được triển khai trong

đề tài luận án.

3. Định hướng nghiên cứu

Trên cơ sở phân tích các công trình nghiên cứu liên quan bài toán tìm kiếm ảnh

được thực hiện theo nhiều tiếp cận khác nhau. Số lượng công trình kết hợp nhiều kỹ

thuật còn hạn chế. Vì vậy, định hướng nghiên cứu của luận án tập trung vào các vấn

đề liên quan gồm:

− Nghiên cứu cấu trúc dữ liệu đa chiều KD-Tree cho tìm kiếm ảnh, cải tiến và

đề xuất các thuật toán thao tác trên cấu trúc KD-Tree.

− Phát triển Ontology và áp dụng cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa.

− Đề xuất các mô hình tìm kiếm ảnh, phương pháp kết hợp các kỹ thuật học

máy và cấu trúc KD-Tree để nâng cao độ chính xác tìm kiếm ảnh.

4. Mục tiêu nghiên cứu của luận án

Mục tiêu của luận án là phát triển mô hình tìm kiếm ảnh tương tự dựa trên cấu

trúc dữ liệu KD-Tree kết hợp với tiếp cận ngữ nghĩa của đặc trưng thị giác hình ảnh

nhằm nâng cao độ chính xác tìm kiếm ảnh.

Mục tiêu cụ thể, 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 trên các cấu trúc đã đề xuất.

(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 và rừng ngẫu nhiên để 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.

5. Phương pháp nghiên cứu

Phương pháp lý thuyết

− 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, đặc biệt quan tâm đến kết quả của các công trình sử dụng 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. Phân tích ưu nhược điểm

của các công trình, đặc điểm của cấu trúc KD-Tree và các biến thể của KD-Tree;

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 dựa trên Ontology.

− Đề xuất mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa và căn cứ vào đá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

− Trên cơ sở mô hình và kỹ thuật đề xuất trong luận án, các chương trình được

viết bằng ngôn ngữ cấp cao (C#), cài đặt thuật toán trên máy tính có cùng cấu hình.

− 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ả, sẽ được đối sánh với dữ liệu thực nghiệm. Một số

công việc bổ sung cho các bộ dữ liệu này, bao 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 cho bộ

ảnh đa đối tượng MS-COCO [21], Flickr [22].

− Xây dựng cấu trúc dữ liệu, cài đặt các 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 kết quả các công trình đã công bố, đồng thời 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. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu

− Các phương pháp phân cụm và phân lớp dữ liệu. − Cấu trúc phân cụm dữ liệu đa chiều. − Cấu trúc Ontology và phương pháp xây dựng, phát triển Ontology. − Các tập ảnh đơn đối tượng và đa đối tượng.

Phạm vi nghiên cứu

− Các phương pháp học máy: học có giám sát, không giám sát và bán giám sát. − Cấu trúc dữ liệu đa chiều KD-Tree. − Các cải tiến: iKD_Tree, KD-Tree lồng nhau, Re KD-Tree, RF KD-Tree. − Cấu trúc Ontology và ngôn ngữ truy vấn SPARQL. − Các tập ảnh: COREL, Wang, Caltech-101, Caltech-256, MS-COCO, Flickr.

7. Nội dung và bố cục của luận án

Nội dung chính của luận án được tổ chức thành ba chương như sau:

Chương 1 giới thiệu cơ sở lý thuyết cho bài toán tìm kiếm ảnh; các đối tượng

cơ sở (đặc trưng hình ảnh, phương pháp trích xuất đặc trưng, đặc trưng ngữ nghĩa,

mối quan hệ ngữ nghĩa, một số khái niệm cơ bản cho bài toán tìm kiếm ảnh); tổng

quan cấu trúc KD-Tree cho tìm kiếm ảnh; môi trường thực nghiệm; mô tả dữ liệu

thực nghiệm và các giá trị đánh giá hiệu suất tìm kiếm ảnh, phân lớp ảnh.

Chương 2 trình bày một số cải tiến cấu trúc KD-Tree như KD-Tree đa nhánh

cân bằng, iKD_Tree, KD-Tree lồng nhau. Một số thuật toán thao tác trên cấu trúc

KD-Tree gồm: thuật toán xây dựng cấu trúc KD-Tree, huấn luyện trọng số và tìm

kiếm trên KD-Tree. Đề xuất mô hình và thực nghiệm tìm kiếm ảnh trên các cấu trúc

KD-Tree, iKD_Tree và KD-Tree lồng nhau. Cuối chương, đánh giá độ chính xác và

thời gian tìm kiếm trên từng cải tiến cấu trúc KD-Tree với các bộ ảnh COREL, Wang,

Caltech-101, Caltech-256; đồng thời so sánh với một số phương pháp khác thực

nghiệm trên cùng bộ ảnh.

Chương 3 phát triển cấu trúc KD-Tree theo tiếp cận ngữ nghĩa, cấu trúc Re KD-

Tree được sử dụng để phân lớp mối quan hệ giữa các đối tượng trên mỗi hình ảnh;

phát triển Ontology trên các bộ dữ liệu ảnh đa đối tượng. Cấu trúc RF KD-Tree được

xây dựng, huấn luyện và tổng hợp thành KD-Tree cho tìm kiếm ảnh. Cuối cùng, các

mô hình tìm kiếm ảnh dựa trên sự kết hợp Re KD-Tree, RF KD-Tree và Ontology

được đề xuất, thực nghiệm trên các bộ ảnh đa MS-COCO, Flickr.

8. Đó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ác đóng góp 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

Chương này trình bày một số nội dung cơ bản về bài toán tìm kiếm ảnh, cấu

trúc dữ liệu đa chiều KD-Tree áp dụng cho bài toán tìm kiếm ảnh; mô hình hệ tìm

kiếm ảnh dựa trên cấu trúc KD-Tree; môi trường thực nghiệm, mô tả tập dữ liệu thực

nghiệm và các giá trị đánh giá độ chính xác tìm kiếm ảnh, độ phủ và độ dung hòa.

1.1. Giới thiệu

Bài toán tìm kiếm ảnh trong luận án được xác định là tìm ra tập các hình ảnh có

độ tương tự gần nhất với ảnh đầu vào dựa trên độ đo tương tự giữa hai hình ảnh [38],

[71]. Một số thuật ngữ tương tự cho khái niệm này xuất phát từ thuật ngữ tiếng Anh

“retrieval” như “truy vấn”, “tra cứu”, “truy hồi”. Tuy nhiên, để phù hợp với thuật ngữ

đã sử dụng trong các công trình liên quan và không ảnh hưởng đến nội dung, thuật

ngữ “tìm kiếm ảnh” được sử dụng trong luận án này.

Một kỹ thuật quan trọng được sử dụng cho các bài toán tìm kiếm ảnh là học

máy. Có nhiều kỹ thuật học máy khác nhau được sử dụng để truy xuất hình ảnh với

việc sử dụng các đặc trưng hình ảnh như màu sắc, kết cấu, hình dạng, đặc trưng không

gian, v.v. [5]. Chất lượng đặc trưng của hình ảnh được trích xuất là một trong những

yếu tố ảnh hưởng trực tiếp đến quá trình nhận diện các đối tượng trên ảnh và kết quả

bài toán tìm kiếm ảnh theo nội dung CBIR [64]. Ngoài ra, các kỹ thuật sắp xếp tổ

chức lưu trữ dữ liệu hình ảnh cũng đóng vai trò quan trọng trong việc nâng cao hiệu

quả tìm kiếm ảnh [52], [83]. Trong những năm gần đây, ảnh số đã gia tăng với tốc độ

khá nhanh thông qua việc chia sẻ hình ảnh bằng các phương tiện thông tin đại chúng,

mạng xã hội, v.v. đã tạo nên một kho dữ liệu khổng lồ. Vì vậy, việc tìm kiếm một tập

hình ảnh liên quan với ảnh đầu vào là thật sự khó khăn nếu dữ liệu chưa được tổ chức

theo một quy tắc hoặc chưa có phương tiện, công cụ đáp ứng nhu cầu tìm kiếm của

người dùng. Vì vậy, một yêu cầu đặt ra là cần kết hợp giữa trích xuất đặc trưng hình

ảnh và một cấu trúc lưu trữ là những yếu tố quan tâm hàng đầu cho bài toán tìm kiếm

ảnh theo nội dung.

Nội dung đặc trưng của hình ảnh bao gồm màu sắc, kết cấu, vị trí tương đối,

chu vi, diện tích, hình dạng, v.v. đôi khi cũng chưa mô tả hết ý nghĩa cần thể hiện trên

mỗi hình ảnh. Một phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa SBIR ra đời

trong thập kỷ vừa qua với những thành tích đột phá nhằm cải tiến những hạn chế còn

tồn tại trong phương pháp tìm kiếm ảnh theo nội dung. Tìm kiếm ảnh theo tiếp cận

ngữ nghĩa đáp ứng được nhu cầu người dùng thông qua việc mô tả nội dung hình ảnh

kết hợp với mô tả mối quan hệ giữa các đối tượng trên ảnh [28]. Đặc trưng ngữ nghĩa

của hình ảnh được mô tả bằng văn bản để nêu lên đặc điểm nhận diện đối tượng, mô

tả vị trí tương đối giữa các đối tượng hoặc mô tả mối quan hệ giữa các đối tượng trên

mỗi hình ảnh. Vì vậy, phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa là sự kết

hợp giữa đặc trưng hình ảnh và đặc trưng ngữ nghĩa đã góp phần nâng cao độ chính

xác cho quá trình tìm kiếm được thực hiện trong luận án này.

Hiện nay, có nhiều phương pháp thực hiện bài toán tìm kiếm ảnh theo tiếp cận

ngữ nghĩa như: (1) sử dụng các kỹ thuật học máy để trích xuất đặc trưng hình ảnh,

liên kết các đặc trưng hình ảnh với các từ vựng trực quan để mô tả ngữ nghĩa các đối

tượng hình ảnh [6]; (2) sử dụng ontology để xác định ngữ nghĩa cấp cao của hình ảnh,

từ đó trích xuất tập ảnh tương tự với mô tả ảnh đầu vào [69]; (3) sử dụng phương

pháp phản hồi liên quan để xác định mức độ quan trọng từng câu truy vấn [56] và

một số phương pháp khác. Mỗi phương pháp tiếp cận có những ưu điểm và nhược

điểm riêng, dựa trên mục tiêu hướng đến trong mỗi bài toán để có giải pháp kết hợp

và lựa chọn phương pháp phù hợp. Phương pháp sử dụng các kỹ thuật học máy đôi

khi tìm được những hình ảnh tương tự theo đặc trưng hình ảnh nhưng lại khác xa về

mặt ngữ nghĩa. Phương pháp phản hồi liên quan còn phụ thuộc vào cảm tính người

dùng đầu cuối, đôi khi kết quả tìm kiếm chưa thực sự khách quan. Trong khi đó,

hướng tiếp cận tìm kiếm ảnh theo ngữ nghĩa dựa vào ontology giúp tìm được những

hình ảnh khá gần với đặc trưng ngữ nghĩa của người dùng mô tả. Trên cơ sở phân

tích này, nội dung luận án thực hiện bài toán tìm kiếm ảnh theo đặc trưng hình ảnh

kết hợp với đặc trưng ngữ nghĩa mô tả đối tượng và mối quan hệ giữa các đối tượng

trên ảnh được thực hiện dựa trên cấu trúc KD-Tree nhằm nâng cao độ chính xác tìm

kiếm ảnh tương tự, cải thiện thời gian tìm kiếm trong các tập dữ liệu ảnh lớn.

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ữ nhằm giảm chi phí

về bộ nhớ 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ó. Hệ thống CBIR khắc phục được những hạn chế của phương pháp tìm

kiếm ảnh theo từ khóa TBIR [41]. Tuy nhiên, một số hạn chế của tìm kiếm ảnh theo

nội dung là chỉ sử dụng các đặc trưng hình ảnh, chưa sử dụng các đặc trưng ngữ nghĩa

cũng như mô tả ngữ cảnh của ảnh đầu vào. Vì vậy, kết quả đánh giá thực nghiệm của

các mô hình tìm kiếm ảnh theo nội dung còn phụ thuộc vào kỹ thuật trích xuất đặc

trưng, chất lượng hình ảnh và một số yếu tố khác.

Một số công trình đã thực hiện phương pháp tìm kiếm ảnh theo nội dung chịu

ảnh hưởng khá lớn vào kỹ thuật trích xuất đặc trưng hình ảnh như: Mutasem K.

Alsmadi (2020) [5] đã thực hiện bài toán tìm kiếm ảnh theo nội dung dựa trên đặc

trưng màu sắc, hình dạng, kết cấu và kết hợp các nhóm đặc trưng với hiệu suất khá

cao trên bộ ảnh COREL. Lakshmi R. Nair và cộng sự [48] thực hiện tìm kiếm ảnh

theo nội dung dựa trên các đặc trưng màu sắc, hình dạng, kết cấu, đặc trưng không

gian vị trí, các đặc trưng cục bộ và sự kết hợp các nhóm đặc trưng này với nhau để

thực nghiệm trên bộ ảnh COREL. Trong công trình này, tác giả cũng đề cập đến mối

quan hệ giữa đặc trưng hình ảnh và đặc trưng ngữ nghĩa và trình bày phương pháp

liên kết giữa đặc trưng này với nhau. Điều này cho thấy, đặc trưng hình ảnh là yếu tố

ảnh hưởng lớn đến kết quả tìm kiếm trên các hệ tìm kiếm ảnh theo nội dung.

1.2.1. Đặc trưng hình ảnh và trích xuất véc-tơ đặc trưng

Đặc trưng của 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. đặc trưng hình ảnh được mô tả như sau:

Phân đoạn ảnh (Image segmentation): Phân đoạn ảnh là công việc đầu tiên trong

trích xuất đặc trưng. Việc phân đoạn ảnh màu được thực hiện bằng cách phân chia

hình ảnh thành các vùng riêng biệt dựa trên từng đối tượng được nhận diện để từ đó

trích xuất đặc trưng trên từng vùng. Phương pháp phân vùng ảnh dựa trên độ tương

phản giữa ảnh nền và ảnh đối tượng, việc phân biệt ảnh nền và ảnh đối tượng sẽ bị

nhập nhằng trong một số hình ảnh khó phân biệt. Để làm giảm độ nhiễu giữa các

vùng quá sáng hoặc quá tối, một số điểm ảnh nằm trong vùng lân cận của giá trị lớn

nhất và giá trị nhỏ nhất thuộc độ tương phản thì được quy về giá trị tương đương [42].

Đặc trưng màu sắc (Color feature): Màu sắc là một trong những đặc điểm quan

trọng nhất trong trích xuất đặc trưng hình ảnh mà mắt người có thể phân biệt giữa các

hình ảnh trên cơ sở màu sắc. Màu sắc có mối quan hệ chặt chẽ với các đối tượng và

ảnh nền. Đặc điểm màu sắc là không thay đổi đối với kích thước, tỷ lệ, phép dịch

chuyển, xoay và hướng của đối tượng [42]. Những hình ảnh của đối tượng trong thế

giới thực được thực hiện trong phạm vi quang phổ hình ảnh để phân biệt trên cơ sở

sự khác biệt về màu sắc [14]. Tính năng màu sắc sử dụng bộ mô tả màu chủ đạo

(DCD) [45] tổng thể thông tin màu sắc của hình ảnh có thể được thay thế bằng một

lượng màu đại diện. Do đó, màu sắc dễ dàng phân tích và trích xuất bằng cách sử

dụng mô men màu (Color Moment), biểu đồ màu (Color Histogram), không gian màu

(Color Space), v.v. Luận án sử dụng đặc trưng màu sắc được trích xuất theo hệ màu

MPEG-7 và Newton [81]. Đối với đặc trưng màu sắc, mỗi điểm ảnh được gom cụm

theo các màu sắc cơ bản của dãy màu Newton (Red, Green, Blue, Yellow, Orange,

Purple). Vì vậy, mỗi điểm ảnh là một véc-tơ dữ liệu trong không gian RGB.

Đặc trưng hình dạng (Shape feature): Hình dạng đối tượng là một trong những

đặc trưng cơ bản trong đặc trưng hình ảnh. Đặc trưng hình dạng được sử dụng để phát

hiện các đối tượng tương tự từ cơ sở dữ liệu mà không phụ thuộc vào vị trí, góc quay

[35]. Các phương pháp trích xuất đặc trưng hình dạng thường được chia thành hai

loại: dựa theo đường biên và dựa theo vùng ảnh. Kỹ thuật xác định đường biên đối

tượng có thể dùng phương pháp Gradient và Laplacian. Vì vậy, để trích xuất các đặc

trưng hình dạng, trước hết các đối tượng ảnh cần phải được phân đoạn thành những

thành phần có cùng tính chất tương đồng dựa trên đường biên hay các vùng lân cận.

Sau đó sử dụng các kỹ thuật phát hiện đường biên ảnh để xác định hình dạng cho đối

tượng đã được tách ra khỏi hình nền [35].

Đặc trưng kết cấu (Texture feature): Kết cấu của một hình ảnh cho biết dữ liệu

liên quan đến sự sắp xếp theo một hướng cụ thể và liên quan đến cường độ màu của

hình ảnh. Các thuộc tính bao gồm đặc trưng kết cấu là kích thước, sắc thái, độ chiếu

sáng và hình dạng. Kết cấu quy định độ mịn, độ đồng đều, độ thô, độ nhám và tính

đồng nhất hay đều đặn của các đối tượng hiện diện trong một hình ảnh. Các bộ mô tả

kết cấu có thể là bộ lọc Gabor, phép biến đổi Wavelet và tính năng Tamura [48]. Các

đặc trưng kết cấu khác nhau có thể được áp dụng trong các lĩnh vực truy xuất hình

ảnh khác nhau. Đặc trưng kết cấu đại diện cho một nhóm pixel ảnh, do đó đặc trưng

này có ý nghĩa hơn về mặt ngữ nghĩa so với đặc trưng màu sắc. Nhược điểm chính

của các đặc trưng kết cấu là độ nhạy với nhiễu hình ảnh và biểu diễn ngữ nghĩa cũng

phụ thuộc vào hình dạng của các đối tượng trong ảnh [5].

Đặc trưng SIFT (Scale-invariant Feature Transform) được trích chọn các điểm

đặc trưng (keypoint), các điểm này kèm theo các mô tả và một véc-tơ lấy keypoint

làm điểm gốc. Đặc trưng SIFT được biểu thị bởi một cấu trúc hoặc thiết kế phân biệt

hiện có trong một hình ảnh; có thể là một cạnh, điểm hoặc vùng ảnh. Đặc trưng này

được liên kết với một vùng hình ảnh cùng cường độ và kết cấu. Các bộ mô tả đặc

trưng cục bộ có thể là SIFT, SURF, biểu đồ định hướng vị trí gradient, v.v. [48].

Đặc trưng SIFT được trích xuất số lượng thuộc tính từ một hình ảnh phụ thuộc

vào tác động chiếu sáng và phối cảnh cùng với các góc nhìn khác nhau. Bộ mô tả đặc

trưng SIFT sẽ phân biệt các yếu tố lân cận của một hình ảnh. Các giai đoạn chính để

trích xuất đặc trưng SIFT là: (1) phát hiện cực đại không gian quy mô cục bộ và bộ

lọc; (2) định vị các điểm đặc trưng; (3) mô tả điểm đặc trưng [48].

Đặc trưng HOG (Histograms of Oriented Gradients) được tính toán trên một

lưới các ô (cell) và chuẩn hóa sự tương phản giữa các khối (block) để nâng cao độ

chính xác. HOG được sử dụng chủ yếu để mô tả hình dạng và sự xuất hiện của một

đối tượng trong ảnh [47]. Đặc trưng HOG trích xuất các thông tin về hình dạng và

nét bề ngoài của các đối tượng cục bộ trong ảnh có thể được mô tả bằng cách sử dụng

thông tin về sự phân bố của các cường độ gradient (intensity gradients) hoặc các

hướng biên (edge directions). Một véc-tơ đặc trưng HOG được tạo ra bằng cách kết

hợp tính toán gradient của mỗi pixel, tạo biểu đồ cho từng khối bằng cách sử dụng

giá trị gradient, tính toán chuẩn hóa biểu đồ dưới dạng lược đồ được hiển thị. Cuối

cùng là tổng hợp các đặc trưng theo từng khối ảnh được phân đoạn [47].

Phương pháp trích xuất đặc trưng: Để trích xuất đặc trưng màu sắc, phương

pháp phát hiện biên đối tượng bằng phép biến đổi LoG (Laplacian of Guassian) cho

ảnh màu được sử dụng. Phép biến đổi LoG bất biến đối với sự biến đổi cường độ ảnh

cũng như sự biến đổi tỉ lệ, phép quay, phép biến đổi affine. Vì vậy, giá trị Gaussian

được xác định bởi công thức (1.1) [47].

𝑥2+𝑦2 2.𝜎2 )

(1.1) 𝐺(𝑥, 𝑦, 𝜎) =

√2𝜋𝜎2 × 𝑒𝑥𝑝 (− là đạo hàm chuẩn, biểu diễn không gian tỷ lệ Gaussian 𝐿(𝑥, 𝑦, 𝜎)

Trong đó

của ảnh 𝑓(𝑥, 𝑦) theo công thức (1.2) [47].

(1.2) 𝐿(𝑥, 𝑦, 𝜎) = 𝑓(𝑥, 𝑦) ∗ 𝐺(𝑥, 𝑦, 𝜎)

Trong công thức (1.2), phép toán là phép tích chập (convolution); (𝑥, 𝑦) là

tọa độ điểm ảnh. Toán tử Laplacian được tính toán theo công thức (1.3) [47].

𝜕2 𝑓 𝜕𝑥2 +

𝜕2 𝑓 𝜕𝑦2

(1.3) ∇2=

Toán tử LoG được tính toán đầu tiên và sau đó được đối sánh với ảnh để tạo ra biểu diễn không gian tỷ lệ LoG theo công thức (1.4) [47].

𝑥2+ 𝑦2− 2𝜎2 𝜋𝜎4

𝑥2+𝑦2 2𝜎2 )

∇2𝐺(𝑥, 𝑦) = exp (− (1.4)

Phương pháp LoG nhằm xác định đường biên, đặc trưng của đối tượng được trích xuất gồm chu vi đối tượng, vị trí tương đối của đường viền.

Ngoài ra, để nhận dạng đối tượng dựa trên biên và làm mịn bề mặt, phép lọc Sobel [4] được sử dụng. Phép lọc Sobel là toán tử Gradient dựa trên vùng láng giềng kích thước 3x3. Mặt nạ tích chập cho toán tử Sobel trên ảnh số tỷ lệ xám Sobelx và Sobely được xác định trong công thức (1.5) [4] như sau:

] (1.5) Sobelx = [ ] ; Sobely = [

−1 0 1 −2 0 2 −1 0 1 −1 −2 −1 0 0 0 1 2 1

𝑗=3

𝑖=3

Các vị trí trên hai mặt nạ được áp dụng riêng biệt trên ảnh đầu vào để tạo thành phần Gradient Gx, Gy theo hướng ngang và dọc tương ứng với công thức (1.6) [4].

𝑖=1

𝑗=1

𝐺𝑥 = ∑ ∑ 𝑆𝑜𝑏𝑙𝑒𝑥𝑖,𝑗. 𝑓𝑥+1−2.𝑦+𝑗−2

𝑖=3 𝑖=1

𝑗=3 𝑗=1

(1.6) 𝐺𝑦 = ∑ ∑ 𝑆𝑜𝑏𝑙𝑒𝑦𝑖,𝑗. 𝑓𝑥+1−2.𝑦+𝑗−2

Độ lớn Gradient được tính bởi công thức (1.7) [4].

(1.7) 𝐺[𝑓(𝑥, 𝑦)] = √𝐺𝑥2 + 𝐺𝑦2

Để xác định vị trí tương đối của đối tượng theo trục X và trục Y, hàm khoảng cách trọng tâm CDF (Centroid Distance Function) được sử dụng. CDF tính toán khoảng cách từ tâm (𝑥0, 𝑦0) đến các điểm đường viền của một hình dạng và được biểu diễn bằng công thức (1.8) [4].

(1.8)

𝑟(𝑛) = √(𝑥(𝑛) − 𝑥0)2 + (𝑦(𝑛) − 𝑦0)2 Quá trình trích xuất véc-tơ đặc trưng hình ảnh được thực hiện như Hình 1.1. Quá trình tạo mặt nạ phân đoạn ảnh dựa trên độ tương phản; dò biên theo phương pháp LoG; trích xuất màu sắc theo thuật toán gom cụm màu K-Means. Trên cơ sở này, một véc-tơ đặc trưng hình ảnh 81 chiều gồm các thành phần được trình bày trong Bảng 1.1 [CT1].

Hình 1.1. Minh họa trích xuất véc-tơ đặc trưng 81 chiều [CT1]

Bảng 1.1. Các giá trị véc-tơ đặc trưng hình ảnh (81 chiều)

Mô tả

Đặc trưng màu sắc theo MPEG-7 Kích thước 25

Phép lọc tần số cao để lấy ảnh đường nét Lấy cường độ ảnh theo phép lọc Gaussian Đặc trưng cường độ các điểm ảnh theo láng giềng Đặc trưng cường độ của đối tượng Đặc trưng cường độ của hình nền Đặc trưng diện tích đối tượng Đặc trưng hình dạng của đường biên ảnh Đặc trưng vị trí tương đối của đối tượng theo trục X, Y Đặc trưng vị trí tương đối của hình nền theo trục X, Y Đặc trưng chu vi của đối tượng Đặc trưng chu vi của đối tượng theo phép lọc Sobel Đặc trưng cường độ điểm ảnh láng giềng theo phép lọc Sobel Đặc trưng chu vi của đối tượng theo phép lọc Laplacian Đặc trưng dò biên đối tượng dùng phép Laplacian 9 9 9 9 9 1 1 2 2 1 1 1 1 1

Đặc trưng hình ảnh được sử dụng cho các thực nghiệm với bộ ảnh đơn đối tượng

khá hiệu quả. Tuy nhiên, nếu áp dụng cho các tập ảnh đa đối tượng đồng thời kết hợp

với ngữ nghĩa người dùng thì kết quả chưa cao. Vì vậy, cải tiến quá trình trích xuất

đặc trưng; đồng thời kết hợp mô tả của người dùng để xây dựng đặc trưng ngữ nghĩa

của hình ảnh trong các bộ ảnh đa đối tượng được thực nghiệm trên các nhóm đặc

trưng được minh họa như Hình 1.2. Đối với bộ ảnh đa đối tượng MS-COCO và

Flickr, sau khi phân đoạn ảnh đối tượng là quá trình trích xuất đặc trưng. Mỗi ảnh đối

tượng được trích xuất bằng các đặc trưng mô tả trong Bảng 1.2 [CT3] như sau:

Bảng 1.2. Các giá trị véc-tơ đặc trưng được trích xuất (225 và 513 chiều)

Mô tả đặc trưng Kích thước

Đặc trưng Shi MPEG7 25

Đặc trưng SHIF MPEG7 25

Đặc trưng màu sắc MPEG7 25

Đặc trưng màu sắc Newton 6

Đặc trưng HOG 36/144

Đặc trưng Laplace HOG 36/144

Đặc trưng Sobel HOG 36/144

Đặc trưng Prewitt HOG 36

Hình 1.2. Minh họa trích xuất véc-tơ đặc trưng 189, 225 và 513 chiều

Từ cơ sở lý thuyết này, đặc trưng hình ảnh được trích xuất minh họa bởi Hình

1.1 – 1.2 [CT3]. Mỗi bộ ảnh thực nghiệm trong các công trình được chọn những loại

đặc trưng riêng với số đặc trưng khác nhau để có kết quả phù hợp từng bộ dữ liệu.

Mỗi hình ảnh được trích xuất bởi một véc-tơ đặc trưng thị giác làm dữ liệu đầu

vào. Đặc trưng hình ảnh là một trong những yếu tố ảnh hưởng đến kết quả của hệ tìm

kiếm ảnh; nếu véc-tơ đặc trưng mô tả chính xác nội dung hình ảnh cần phản ảnh thì

kết quả tìm kiếm có độ chính xác càng cao và ngược lại. Đối với bộ ảnh MS-COCO,

Flickr thì việc trích xuất đặc trưng của ảnh đối tượng gồm những thành phần: khoảng

cách giữa các đối tượng; độ lệch ∆x, ∆y; tọa độ góc trên, dưới, trái, phải; diện tích;

chu vi, tỷ lệ diện tích chồng lắp; chiều dài; chiều rộng.

1.2.2. Độ tương tự giữa hai hình ảnh

Độ đo khoảng cách được áp dụng để tính khoảng cách giữa những véc-tơ đặc

trưng hình ảnh, từ đó tính toán độ tương tự của ảnh đầu vào với các hình ảnh trong

kho lưu trữ ảnh. Độ đo khoảng cách được chọn theo cấu trúc của véc-tơ đặc trưng và

chỉ ra mức độ giống nhau nhiều hay ít giữa hai hình ảnh. Hiệu quả tìm kiếm ảnh phụ

thuộc vào độ đo khoảng cách hay còn gọi là độ đo tương tự vì phụ thuộc vào các vùng

đối tượng, hình nền, hình dạng các đối tượng trong ảnh và đặc trưng từng bộ ảnh.

Việc lựa chọn độ đo khoảng cách là một thách thức, ảnh hưởng đến kết quả tìm kiếm

của hệ thống. Ngoài ra, việc lấy TopK số ảnh đại diện theo kết quả tìm kiếm cũng

làm ảnh hưởng đến kết quả độ chính xác và độ phủ trong bài toán tìm kiếm ảnh.

Hiện nay, có nhiều độ đo để xác định độ tương tự giữa hai hình ảnh như độ đo

Euclide [82], độ đo Minkowski [61], độ đo EMD [38], v.v. Một số công trình sử dụng

các độ đo để đánh giá độ tương tự giữa hai hình ảnh là khác nhau, chẳng hạn như:

EO Rodrigues và cộng sự (2018) [61] đã thực hiện kết hợp giữa hai độ đo Minkowski

và Chebyshev để đề xuất ra độ đo mới xác định mức độ tương tự giữa hai hình ảnh

trong hệ CBIR. Xiong Zenggang và cộng sự [82] đã thực hiện tìm kiếm ảnh theo nội

dung dựa trên đặc trưng hình ảnh và khoảng cách Euclide để xác định độ tương tự

giữa hai hình ảnh. Điều này cho thấy sự đa dạng trong việc lựa chọn độ đo khoảng

cách nhằm xác định độ tương tự giữa hai hình ảnh. Trong luận án, độ đo tương tự

được tính theo khoảng cách Euclide để đánh giá độ tương tự giữa hai hình ảnh,

khoảng cách Euclide giữa hai véc-tơ đặc trưng hình ảnh càng nhỏ thì độ tương tự giữa

hai ảnh này càng lớn và ngược lại. Giá trị của véc-tơ đặc trưng hình ảnh sau khi trích

xuất với các thành phần là giá trị thực được chuẩn hóa trên đoạn [0, 1]. Vì vậy, độ đo

Euclide sử dụng để tính độ tương tự giữa hai hình ảnh được thực hiện trong luận án.

1.3. Tìm kiếm ảnh theo tiếp cận ngữ nghĩa

Để đáp ứng nhu cầu người dùng về độ chính xác và thời gian tìm kiếm, mô hình

tìm kiếm ảnh theo tiếp cận ngữ nghĩa được nhiều công trình công bố [52], [44], [4].

Với 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 tương tự dựa trên mô tả ngữ nghĩa

ảnh đầu vào. Hệ tìm kiếm ảnh theo ngữ nghĩa đã khắc phục được những hạn chế của

phương pháp tìm kiếm ảnh theo nội dung. Đồng thời mô tả ngữ nghĩa nội dung hình

ảnh giúp cho quá trình tìm kiếm ảnh mang lại độ chính xác cao, đáp ứng nhu cầu thực

tế người dùng ngày càng phổ biến. Đây là một phương pháp được nhiều nhóm nghiên

cứu quan tâm và được triển khai trong thực tế.

1.3.1. Đặc trưng ngữ nghĩa

Một bước phát triển so với tìm kiếm ảnh theo nội dung là không chỉ thực hiện

so sánh độ đo tương tự giữa hai hình ảnh bằng khoảng cách Euclide mà dựa trên đặc

trưng ngữ nghĩa của hình ảnh. Trong tìm kiếm ảnh theo tiếp cận ngữ nghĩa việ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. Trong khi đó, véc-tơ đặc trưng mô tả nội dung hình ảnh chỉ biểu diễn bằng

các tính năng như màu sắc, hình dạng, vị trí, chu vi, v.v. Điều này dẫn đến, có những

hình ảnh giống nhau về mặt nội dung chẳng hạn như hai ảnh chứa cùng hai đối tượng

con người (person) và xe cộ (vehicle) nhưng ảnh thứ nhất mô tả “người ngồi trên xe”;

ảnh thứ hai mô tả “người ở bên trái xe” chỉ có đặc trưng ngữ nghĩa hình ảnh mới diễn

đạt chính xác các nội dung hình ảnh [48]. Đặc trưng hình ảnh mô tả được hai ảnh này

tương tự nhau nhưng không giống nhau về mặt ngữ nghĩa. Vì vậy, luôn có một sự

khác biệt về ngữ nghĩa hình ảnh thông qua mô tả bằng đặc trưng ngữ nghĩa. Thách

thức cho bài toán tìm kiếm ảnh theo ngữ nghĩa là chuyển từ đặc trưng hình ảnh, liên

kết các đặc trưng để xây dựng ngữ nghĩa mô tả hình ảnh. Để thực hiện điều này, cấu

trúc Ontology lưu trữ và mô tả ngữ nghĩa hình ảnh được xây dựng dựa trên các bộ dữ

liệu thực nghiệm. Quá trình xây dựng đặc trưng ngữ nghĩa mô tả hình ảnh dựa trên

các đặc trưng hình ảnh và khái niệm người dùng minh họa như Hình 1.3.

Hình 1.3. Mô tả đặc trưng ngữ nghĩa của hình ảnh [48] Đặc trưng ngữ nghĩa được xây dựng trên cơ sở các đặc trưng hình ảnh kết hợp

với mối quan hệ giữa các đối tượng và khái niệm đặc trưng ngữ nghĩa của người

dùng. Vị trí không gian được mô tả vị trí tương đối trái, phải, trên, dưới và trước, sau

theo vị trí của từng đối tượng của hình ảnh. Chẳng hạn trên một hình ảnh có biển và

bầu trời có thể có màu sắc và kết cấu giống nhau nhưng đặc trưng không gian lại

không giống nhau. Bầu trời trong bất kỳ hình ảnh nào được thể hiện ở trên cùng của

hình ảnh trong khi biển ở phần dưới của hình ảnh [48].

1.3.2. Mối quan hệ ngữ nghĩa

Mối quan hệ ngữ nghĩa theo đặc trưng không gian giữa các đối tượng trên mỗi

hình ảnh được sử dụng trong các công trình về tìm kiếm ảnh theo tiếp cận ngữ nghĩa.

Các mối quan hệ này được xác định bằng cách xây dựng đồ thị SG hoặc KG để xác

định vị trí tương đối giữa các đối tượng trên ảnh như một số công trình đã công bố

[80], [62] được minh họa như Hình 1.4. Trên cơ sở xác định và trích xuất từng đối

tượng thuộc ả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 giữa các đối tượng trên ảnh. Từ đó, mối quan

hệ ngữ nghĩa này gồm: 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 đượ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]. Trong đó cặp đối

tượng , được xác định một mối quan hệ không gian là , từ đó

hình thành nên bộ ba (Triple) mô tả mối quan hệ ngữ nghĩa là “people on chair”.

Ngoài ra, một số mối quan hệ ngữ nghĩa khác được xác định như: “people in

mountain”, “people left people”.

Hình 1.4. Xác định mối quan hệ không gian giữa các đối tượng bằng SG [46]

Hình 1.5. Xác định mối quan hệ không gian giữa các đối tượng bằng KD-Tree

1.3.3. Các phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa

Hiện nay, một số phương pháp để tìm kiếm ảnh theo tiếp cận ngữ nghĩa, đó là:

(1) Sử dụng ontology để xác định đặc trưng ngữ nghĩa cho bài toán tìm kiếm

ảnh theo tiếp cận ngữ nghĩa [81];

(2) Sử dụng các kỹ thuật học máy để liên kết các đặc trưng hình ảnh với ngữ

nghĩa bằng các nhãn ngữ nghĩa hay từ vựng trực quan [44], [4], [45];

(3) Sử dụng phản hồi liên quan nhằm tìm hiểu ý nghĩ người dùng [69];

(4) Tạo các mẫu ngữ nghĩa để truy xuất ảnh dựa trên ngữ nghĩa [40].

Trong đó, phương pháp phản hồi liên quan phụ thuộc vào cảm tính của người

dùng nên kết quả chưa khách quan. Mặt khác, phương pháp sử dụng nhiều nguồn

thông tin như văn bản thu được từ Web và tạo mẫu ngữ nghĩa thu được với độ chính

xác chưa cao. Trong luận án này, phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa

sử dụng Ontogoly được đề xuất. Ontology được phát triển trên nền tảng bổ sung thông

tin ảnh đối tượng, phân lớp ảnh, phân lớp con và mối quan hệ giữa các đối tượng trên

ảnh để áp dụng cho quá trình tìm kiếm theo bộ ba mô tả hình ảnh. Đây là một điểm

cải tiến trong quá trình xây dựng và tìm kiếm ảnh trên Ontology.

1.4. Tìm kiếm ảnh dựa trên cấu trúc KD-Tree

Hiện nay, có nhiều phương pháp tổ chức dữ liệu đa chiều như sử dụng cấu trúc

cây [52], [30] cấu trúc đồ thị [71], [51]; trong đó, cấu trúc dữ liệu đa chiều KD-Tree

được tiếp cận và sử dụng trong luận án cho bài toán tìm kiếm ảnh.

1.4.1. Cấu trúc KD-Tree cho tìm kiếm ảnh

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 cây 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. KD-

Tree cũng là cấu trúc 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á (𝐿𝑒𝑎𝑓). Tại mỗi nút chỉ có tối đa hai nhánh con, chia

cây thành hai phần gồm cây con trái và cây con phải. Phần các điểm ở bên trái nút

gốc biểu thị bằng cây con trái và các điểm ở bên phải nút gốc biểu thị bằng cây con

phải. Cấu trúc KD-Tree ứng dụng khá hiệu quả trong nhiều lĩnh vực như: biểu diễn

cơ sở dữ liệu không gian và thời gian, biểu diễn các hệ cơ sở dữ liệu lớn nhằm giảm

không gian lưu trữ và tìm kiếm nhanh, v.v. Vì cấu trúc KD-Tree lưu trữ được dữ liệu

đa chiều, trong khi đó dữ liệu đa phương tiện như video, hình ảnh, v.v. sau khi trích

xuất là véc-tơ đặc trưng đa chiều. Do đó, một cấu trúc dữ liệu đa chiều được sử dụng

để lưu trữ véc-tơ đặc trưng là cần thiết cho bài toán tìm kiếm ảnh. Trong đó, cấu trúc

dữ liệu đa chiều KD-Tree được sử dụng nhiều trong các công trình tìm kiếm ảnh đã

công bố ngoài những cấu trúc dữ liệu như S-Tree [38], C-Tree [52], v.v. Bên cạnh

đó, 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 mà vẫn đảm bảo được số nút lá cần thiết, khi đó thời gian tìm kiếm từ

nút gốc đến nút lá là ổn định [CT1]. Vì vậy, cấu trúc dữ liệu KD-Tree là một lựa chọn

đúng đắn và phù hợp trong bối cảnh dữ liệu ảnh số gia tăng nhanh như hiện nay.

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 nhánh cho dữ liệu khi thêm vào

cây được duyệt từ gốc đến lá. Đề xuất này được áp dụng hiệu quả cho bài toán phân

lớp hình ảnh và tìm kiếm ảnh. Đề xuất cải tiến cấu trúc KD-Tree gồm: (1) quá trình

gom cụm thì mỗi nút lá là một cụm dữ liệu tương đồng [CT7]; (2) quá trình phân lớp

thì mỗi nút lá là một phân lớp hình ảnh [CT8].

1.4.2. Phân lớp hình ảnh dựa trên cấu trúc KD-Tree

Phân lớp hình ảnh là quá trình phân lớp đối tượng trên ảnh thuộc một hay nhiều

nhãn lớp nhờ một mô hình phân lớp [75]. Mô hình phân lớp được xây dựng dựa trên

một tập dữ liệu trước đó có gán nhãn gọi là tập huấn luyện; quá trình phân lớp là quá

trình gán nhãn cho đối tượng dữ liệu mới dựa trên mô hình đã xây dựng. Nhiệm vụ

của bài toán phân lớp hình ảnh là cần xây dựng một mô hình để khi có dữ liệu mới

thì có thể xác định được nhãn lớp cho dữ liệu đầu vào. Hiện nay, có những bài toán

phân lớp dữ liệu như phân lớp nhị phân (binary classification), phân lớp đa lớp

(multiclass classification) [75].

Bài toán phân lớp dữ liệu sử dụng các thuật toán học có giám sát để xây dựng

mô hình phân lớp. Hiện nay có nhiều kỹ thuật để phân lớp hình ảnh như k-NN [24],

CNN [35], Decision Tree [37], v.v. Bài toán phân lớp hình ảnh được ứng dụng vào

hai mảng chính là phân lớp đối tượng bằng hình ảnh và ứng dụng vào bài toán tìm

kiếm ảnh. Trong luận án, một phương pháp phân lớp dữ liệu hình ảnh theo tiếp cận

KD-Tree [CT8], quá trình phân lớp ảnh được thực hiện theo các bước:

1) Chuẩn bị tập dữ liệu huấn luyện (Training dataset) và trích xuất véc-tơ đặc

trưng.

2) Xây dựng và huấn luyện mô hình phân lớp ảnh dựa trên tập dữ liệu huấn

luyện.

3) Kiểm tra mô hình với dữ liệu kiểm thử (Testing dataset). 4) Đánh giá mô hình phân lớp và chọn bộ trọng số tốt nhất.

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.

Phân lớp ảnh bằng cấu trúc KD-Tree là quá trình phân lớp một đối tượng khi 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 sau

khi huấn luyện đã mang lại kết quả phân lớp hình ảnh cao.

Kết quả đánh giá mô hình phân lớp ảnh bằng KD-Tree sử dụng phương pháp

thống kê theo tỷ lệ tập ảnh được phân lớp đúng nhãn trong tổng số ảnh thực nghiệm.

Vì vậy, một hướng tiếp cận phát triển nhiều cấu trúc KD-Tree độc lập để hình thành

rừng ngẫu nhiên nhằm nâng cao độ chính xác phân lớp hình ảnh trước khi thực hiện

cho bài toán tìm kiếm ảnh.

1.4.3. Phân lớp mối quan hệ ngữ nghĩa dựa trên cấu trúc KD-Tree

Phân lớp mối quan hệ ngữ nghĩa các đối tượng ảnh là bài toán được thực hiện

qua nhiều giai đoạn; từ phân lớp từng đối tượng trên ảnh đến xác định quan hệ các

đối tượng này để xây dựng mối quan hệ ngữ nghĩa. Hiện nay, có nhiều phương pháp

để thực hiện bài toán phân lớp mối quan hệ giữa các đối tượng trên ảnh như sử dụng

mạng học sâu Deep Learning [63], đồ thị ngữ cảnh [80], đồ thị tri thức [62], v.v. đã

mang lại những kết quả khác nhau. Trong luận án, một phương pháp phân lớp mối

quan hệ các đối tượng trên ảnh bằng cấu trúc KD-Tree được gọi là Re KD-Tree.

Đối với những bộ ảnh đa đối tượng, mỗi ảnh gồm nhiều đối tượng có các mối quan hệ về vị trí tương đối cần được xác định và phân lớp. Để phát huy những ưu

điểm của cấu trúc KD-Tree phân lớp ảnh, cấu trúc Re KD-Tree được xây dựng nhằm

thực hiện phân lớp mối quan hệ về giữa các đối tượng trên một hình ảnh. Cấu trúc Re

KD-Tree được xây dựng gồm một nút gốc, tập nút trong và nhiều nút lá. Nút gốc và

nút trong lưu trữ véc-tơ phân lớp; nút lá lưu trữ từ vựng chỉ mối quan hệ giữa hai đối

tượng. Mục đích của quá trình xây dựng cấu trúc Re KD-Tree là nhằm phân loại mối

quan hệ giữa các đối tượng trên ảnh; từ đó làm cơ sở bổ sung vào khung ontology để

thực hiện bài toán tìm kiếm ảnh theo tiếp cận ngữ nghĩa. Sau khi xây dựng và huấn

luyện bộ trọng số trên cấu trúc Re KD-Tree là quá trình phân lớp mối quan hệ giữa

các đối tượng trên ảnh đầu vào được thực hiện [CT5].

1.4.4. Tìm kiếm ảnh dựa trên cấu trúc KD-Tree

Trên cơ sở cấu trúc KD-Tree được xây dựng cho bài toán tìm kiếm ảnh bằng

cách phát triển các nút lá lưu trữ tập véc-tơ đặc trưng, nút gốc và tập nút trong lưu véc-tơ trọng số. Quá trình hình thành một đường đi từ nút gốc đến nút lá là một cụm chứa tập ảnh có độ tương tự gần nhất [CT1]. Vì vậy, một mô hình tìm kiếm ảnh theo nội dung dựa trên cấu trúc KD-Tree được đề xuất như Hình 1.6 gồm hai pha:

Pha tiền xử lý: (1) trích xuất đặc trưng hình ảnh thành tập véc-tơ đặc trưng; (2)

xây dựng cấu trúc dữ liệu KD-Tree lưu trữ véc-tơ đặc trưng hình ảnh; (3) huấn luyện

KD-Tree để thu được bộ trọng số với kết quả phân cụm hình ảnh tại nút lá cao nhất.

Pha tìm kiếm: (1) trích xuất véc-tơ đặc trưng của ảnh đầu vào; (2) thực hiện tìm kiếm trên cấu trúc KD-Tree sau khi huấn luyện để tìm vị trí nút lá chứa ảnh đầu vào; (3) trích xuất tập ảnh tương tự là tập các ảnh tại nút lá tìm được.

Hình 1.6. Mô hình tìm kiếm ảnh theo nội dung dựa trên cấu trúc KD-Tree

Đối với các bộ ảnh đa đối tượng, mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa

dựa trên cấu trúc KD-Tree được minh họa như Hình 1.7.

Hình 1.7. Mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên KD-Tree

Mô hình chung cho hệ tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên cấu trúc

KD-Tree gồm hai pha:

Pha tiền xử lý thực hiện các bước: (1) phân đoạn ảnh gốc thành các ảnh đối

tượng; (2) trích xuất véc-tơ đặc trưng của ảnh đối tượng; (3) xây dựng và huấn luyện cấu trúc KD-Tree lưu trữ ảnh đối tượng; (4) xây dựng và huấn luyện cấu trúc Re KD- Tree; [36] xây dựng Ontology cho ảnh đối tượng và mối quan hệ.

Pha tìm kiếm thực hiện các bước: (1) phân đoạn ảnh gốc thành các ảnh đối

tượng; (2) trích xuất véc-tơ đặc trưng của ảnh đối tượng; (3) xây dựng bộ ba mô tả

mối quan hệ giữa các đối tượng trên mỗi hình ảnh; (4) xây dựng câu truy vấn

SPARQL dựa trên bộ ba; [36] tìm kiếm trên ontology trích xuất tập ảnh tương tự theo

ngữ nghĩa với ảnh đầu vào.

Hệ tìm kiếm ảnh theo tiếp cận ngữ nghĩa được thực hiện trên các bộ ảnh đa đối

tượng trên cơ sở phân đoạn ảnh gốc thành các ảnh đa đối tượng và xác định mối quan

hệ trực quan theo vị trí giữa các đối tượng này. Vì vậy, cấu trúc Re KD-Tree được đề

xuất xây dựng và áp dụng cho mô hình tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên

cấu trúc KD-Tree và Ontology. Bên cạnh đó, tìm kiếm ảnh theo tiếp cận ngữ nghĩa

cần phải xác định được ngữ nghĩa của ảnh đầu vào. Ngữ nghĩa này có thể được mô tả

bằng văn bản hoặc thông qua đặc trưng ngữ nghĩa của hình ảnh được chuyển đổi từ

đặc trưng hình ảnh [CT5].

1.5. Phương pháp thực nghiệm và đánh giá

1.5.1. Môi trường và dữ liệu thực nghiệm

Để đánh giá hiệu quả của các mô hình tìm kiếm ảnh được đề xuất, các thực

nghiệm được thực hiện với nền tảng dotNET Framework 4.8, ngôn ngữ lập trình C#;

các đồ thị được xây dựng trên Mathlab 2015. Cấu hình máy tính của thực nghiệm tìm

kiếm ảnh: Intel(R) CoreTM i7- 5200U, CPU 2,50GHz, RAM 16GB và hệ điều hành

Windows 10 Professional. Cấu hình máy server dùng để huấn luyện cấu trúc KD-

Tree, iKD_Tree, KD-Tree lồng nhau, Re KD-Tree và rừng ngẫu nhiên là: CPU

Xeon(R) Gold 6258R CPU 2.70Ghz, ổ cứng SSD 1024GB, Ram 16GB, hệ điều hành

Server Datacenter 2019. Các bộ ảnh tiêu chuẩn sử dụng cho thực nghiệm được mô tả

trong Bảng 1.3.

Bảng 1.3. Mô tả các bộ dữ liệu ảnh thực nghiệm

STT Tên tập ảnh

1 2 3 4 5 6 COREL Wang Caltech-101 Caltech-256 MS-COCO Flickr Số lượng ảnh 1,000 10,800 1,344 30,607 163,957 31,783 Số thư mục ảnh 10 80 102 257 79 78 Số chủ đề ảnh 10 80 102 257 79 79 Dung lượng 30.3 MB 69.2 MB 131 MB 1.2 GB 26.7 GB 8.58 GB

Bộ ảnh COREL gồm 1,000 ảnh JPEG chia thành 10 chủ đề khác nhau bao gồm: beach, bus, castle, dinosour, elephant, flower, horse, meal, moutain, people. Mỗi chủ đề gồm 100 ảnh, mỗi ảnh trong tập ảnh COREL chỉ thuộc về một chủ đề. Bộ ảnh Wang cũng là tập ảnh đơn đối tượng, gồm 10,800 ảnh chia làm 80 chủ đề. Số lượng ảnh của mỗi chủ đề là khác nhau, ít nhất là 100 ảnh, nhiều nhất là 545 ảnh.

Bộ ảnh Caltech-101 gồm 9,144 ảnh JPEG chia thành 102 chủ đề khác nhau. Mỗi chủ đề chứa từ 40 đến 800 ảnh, mỗi ảnh trong tập ảnh Caltech-101 chỉ thuộc về một chủ đề. Bộ ảnh Caltech-256 là một cải tiến so với người tiền nhiệm Caltech-101, kích thước danh mục lớn hơn và độ khó tổng thể tăng lên; có 30,607 hình ảnh trong tập dữ liệu này bao gồm 257 chủ đề đối tượng. Mỗi chủ đề chứa từ 80 đến 827 hình ảnh, với giá trị trung bình là 100 hình ảnh cho mỗi chủ đề.

Ngoài ra, một số bộ ảnh đa đối tượng cũng được sử dụng đánh giá mô hình đề xuất trong luận án này gồm MS-COCO và Flickr. Trong đó, tỷ lệ tập ảnh huấn luyện, kiểm thử và thực nghiệm được trình bày trong Bảng 1.4.

Bảng 1.4. Mô tả bộ ảnh đa đối tượng

Bộ dữ liệu ảnh MS-COCO Flickr Tổng số lượng ảnh 163,957 31,783 Số ảnh huấn luyện 118,287 29,000 Số ảnh kiểm thử 40,670 1,783 Số ảnh thực nghiệm 5,000 1,000

1.5.2. Các đại lượng đánh giá hiệu suất

Các kết quả cần được đánh giá hiệu suất gồm: Kết quả phân lớp hình ảnh và

độ chính xác tìm kiếm ảnh.

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 lớp đúng đối với tổng số hình ảnh thực nghiệm theo công thức (1.9).

∑(𝑓𝑘𝑖) ∑(𝑓𝑚𝑖)

(1.9) 𝑃 =

Trong đó: ∑(𝑓𝑘𝑖) là tổng số véc-tơ được phân lớp nhãn lớp đúng theo mô

hình.

∑(𝑓𝑚𝑖) là tổng số véc-tơ cùng nhãn lớp thuộc tập dữ liệu kiểm thử mô hình.

|𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑚𝑎𝑔𝑒𝑠 ∩𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 𝑖𝑚𝑎𝑔𝑒𝑠|

Độ chính xác tìm kiếm ảnh đánh giá trên từng bộ dữ liệu thực nghiệm. Bài toán tìm kiếm ảnh được thực hiện trên một cơ sở dữ liệu, kết quả là một tập hợp các ảnh tương tự, nhằm xác định các ảnh trong tập kết quả thuộc về các chủ đề. Do đó, thước đo để đánh giá hiệu suất trong tìm kiếm ảnh là độ chính xác (precision), độ phủ (recall) và độ dung hoà (F-measure) [67]. Độ chính xác là tỷ lệ giữa số hình ảnh có liên quan trong kết quả đầu tiên với tổng số hình ảnh tìm kiếm được, độ phủ và độ dung hòa được tính toán theo các công thức sau:

|𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 𝑖𝑚𝑎𝑔𝑒𝑠|

|𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑚𝑎𝑔𝑒𝑠 ∩𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 𝑖𝑚𝑎𝑔𝑒𝑠|

(1.10) 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =

|𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑚𝑎𝑔𝑒𝑠|

(𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 × 𝑟𝑒𝑐𝑎𝑙𝑙)

(1.11) 𝑟𝑒𝑐𝑎𝑙𝑙 =

(𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 + 𝑟𝑒𝑐𝑎𝑙𝑙)

(1.12) 𝐹 − 𝑚𝑒𝑎𝑠𝑢𝑟𝑒 = 2 ×

Trong đó, relevant images là tập ảnh tương tự với ảnh tra cứu thuộc tập dữ liệu ảnh, retrieved images là tập ảnh đã tìm kiếm được. Độ phủ recall là tỷ lệ của các hình ảnh có liên quan được truy xuất với số lượng các hình ảnh có liên quan trong cơ sở dữ liệu ảnh. F-measure là độ dung hòa cho giá trị precision và recall được thể hiện trong công thức (1.12). Giá trị F-measure càng cao, cho thấy khả năng dự đoán của hệ thống càng tốt. Các giá trị precision, recall và F-measure được tính theo tỉ lệ % và quy đổi thành giá trị trên đoạn [0, 1]. Ngoài ra, độ chính xác trung bình MAP (Mean Average Precision) được tính toán theo công thức (1.13) [67] là độ chính xác của mỗi ảnh truy vấn so với số ảnh tập dữ liệu thực nghiệm.

𝑛 ∑ 𝑃𝑖 𝑖=1 𝑛

(1.13) 𝑀𝐴𝑃 =

Để mô tả kết quả của hệ tìm kiếm ảnh, đường cong ROC cho biết tỷ lệ kết quả truy vấn đúng (True positive rate) và kết quả truy vấn sai (False positive rate) được thực hiện bằng ngôn ngữ Matlab 2015.

Kết quả về trích xuất đặc trưng hình ảnh, tìm kiếm ảnh dựa trên cấu trúc KD- Tree, phân lớp ảnh bằng cấu trúc KD-Tree được trình bày trong các bài báo [CT1], [CT7], [CT8] trong danh mục công trình liên quan đến luận án của tác giả.

1.6. Tổng kết chương

Nội dung chủ yếu của chương bao gồm: các vấn đề liên quan tìm kiếm ảnh như đặc trưng hình ảnh, phương pháp trích xuất đặc trưng, đặ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á hiệu suất tìm kiếm ảnh. Nội dung của chương làm cơ sở cho các nghiên cứu tiếp theo sẽ được trình bày trong các chương sau.

CHƯƠNG 2. TÌM KIẾM ẢNH DỰA TRÊN CẤU TRÚC

KD-TREE

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 cấu trúc KD-Tree đa nhánh cân bằng;

sau đó, một số cải tiến là iKD_Tree và 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. Thực nghiệm được triển khai và so sánh với

một số phương pháp khác trên cùng tập ảnh. Kết quả cho thấy các cải tiến cấu trúc

KD-Tree áp dụng cho bài toán tìm kiếm ảnh có thời gian tìm kiếm ổn định và độ

chính xác cao hơn một số công trình đã công bố trước đây.

2.1. Giới thiệu

Trích xuất tập ảnh tương tự với ảnh đầu vào từ tập dữ liệu lớn có số lượng ảnh

nhiều nhất là vấn đề cần được quan tâm trong bài toán tìm kiếm ảnh. Hiện nay, có

nhiều kỹ thuật và phương pháp để thực hiện bài toán tìm kiếm ảnh theo các tiếp cận

khác nhau. Dữ liệu ảnh số gia tăng cần phải có một phương pháp lưu trữ và sắp xếp

sao cho quá trình tìm kiếm nhanh và hiệu quả.

Những công trình về tìm kiếm ảnh trong những năm gần đây sử dụng cấu trúc

dữ liệu đa chiều KD-Tree được công bố rộng rãi [49], [51], [8]. Điều này cho thấy

tính thời sự của KD-Tree áp dụng cho tìm kiếm ảnh, cụ thể là: Fengquan Zhang [83]

và cộng sự đã xây dựng cấu trúc Vocabulary-KDTree là một biến thể của KD-Tree

nhằm thực hiện đối sánh hình ảnh. Mô hình tìm kiếm ảnh được thực hiện theo hai pha

online và offline; kết quả thu được với hiệu suất đối sánh ảnh ổn định. Bên cạnh đó,

Y Narasimhulu [49] đã đề xuất một mô hình phân lớp hình ảnh dựa vào KD-Tree.

Quá trình phân lớp ảnh dựa trên số láng giềng nhiều nhất; sau đó độ đo khoảng cách

được sử dụng để phân lớp tập dữ liệu hình ảnh huấn luyện. Mô hình này được đánh

giá tốt đối với bài toán phân lớp ảnh dựa trên cấu trúc KD-Tree.

Trên cơ sở phân tích những công trình liên quan về tìm kiếm ảnh sử dụng KD-

Tree cho thấy có một số biến thể và cải tiến để nâng cao khả năng lưu trữ, tìm kiếm

ảnh và phân lớp hình ảnh có độ chính xác cao. Cấu trúc KD-Tree nguyên thủy [10]

chỉ để lưu trữ dữ liệu đa chiều; sau đó phát triển KD-Tree cho bài toán tìm kiếm ảnh

và hiện nay đã có nhiều đề xuất cải tiến trên KD-Tree nhằm tăng khả năng lưu trữ khi

dữ liệu tăng trưởng theo thời gian. Khi các bộ dữ liệu thực nghiệm tăng lên đến hàng

chục gigabyte thì việc tổ chức và lưu trữ là một thách thức lớn. Trong chương này,

cấu trúc KD-Tree đa nhánh cân bằng được đề xuất xây dựng và một số cải tiến là

iKD_Tree, KD-Tree lồng nhau; đồng thời thực nghiệm tìm kiếm ảnh được xây dựng

với các bộ ảnh đơn đối tượng COREL, Wang, Caltech-101, Caltech-256.

2.2. Cấu trúc KD-Tree đa nhánh cân bằng

Để thực hiện bài toán tìm kiếm ảnh, mỗi hình ảnh được trích xuất thành một

véc-tơ đa chiều gồm các đặc trưng thị giác như hình dạng, màu sắc, kích thước, diện

tích, tỷ lệ, kết cấu bề mặt, v.v. Cấu trúc KD-Tree sau khi xây dựng và huấn luyện sẽ

thực hiện quá trình phân lớp ảnh và tìm kiếm tập ảnh tương tự với ảnh đầu vào. Một

số thao tác trên cấu trúc KD-Tree gồm: xây dựng KD-Tree, gán nhãn nút lá, huấn

luyện trọng số, tìm kiếm trên KD-Tree. Trong quá trình xây dựng cây, việc xóa các

phần tử tại nút lá không ảnh hưởng đến cấu trúc KD-Tree; việc xóa một số phần tử

tại nút lá thì không ảnh hưởng đáng kể đến độ chính xác trung bình của bài toán. Việc

tách nút lá trên KD-Tree không cần thiết phải thực hiện vì mỗi nút lá không giới hạn

số phần tử tối đa. Một nút trong không thể xóa vì nút trong chỉ đóng vai trò trung

gian để xây dựng cây và không chứa dữ liệu. Quá trình chèn dữ liệu vào cây theo các

thứ tự khác nhau sẽ dẫn đến số phần tử tại các cụm nút lá thay đổi; tuy nhiên sau khi

hình thành số cụm nút lá có thể áp dụng thuật toán K-Means tại các cụm nút lá thì kết

quả các cụm sẽ ổn định và không làm giảm độ chính xác tìm kiếm ảnh. Cây được tạo

ra không duy nhất là do một số ít phần tử bị sai cụm nút lá trong quá trình xác định

đường đi trên KD-Tree. Vì vậy, kết quả tìm kiếm ảnh tổng thể của hệ tìm kiếm ảnh

có sự chênh lệch nhỏ. Tuy nhiên, để cho kết quả tìm kiếm ảnh là tốt nhất thì sau khi

hình thành các cụm tại nút lá thì tiến hành áp dụng thuật toán gom cụm K-Means với

số cụm là số nút lá và tâm cụm là giá trị trung bình của tập véc-tơ tại mỗi cụm. Tuy

nhiên, kết quả này chưa thực sự có sự ảnh hưởng lớn đến luận án, thực nghiệm đề

cập đến các cải tiến chính trên iKD_Tree và KD-Tree lồng nhau.

2.2.1. Xây dựng cấu trúc KD-Tree

KD-Tree được đề cập đến trong luận án là cây đa nhánh, cân bằng gồm một nút

gốc, tập nút trong và nhiều nút lá, được mô tả như sau:

1) 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à có một mức trên cây ℎ0 (𝑙𝑒𝑣𝑒𝑙 = ℎ0). Ký hiệu: 𝑅𝑜𝑜𝑡 = < 𝑤0, {𝑙𝑒𝑓𝑡}, {𝑟𝑖𝑔ℎ𝑡}, ℎ0 >;

2) Nút trong (𝑁𝑜𝑑𝑒𝑖) là nút 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: 𝑁𝑜𝑑𝑒𝑖 = < 𝑝𝑎𝑟𝑒𝑛𝑡, 𝑤𝑖, {𝑙𝑒𝑓𝑡}, {𝑟𝑖𝑔ℎ𝑡}, ℎ𝑖 > ;

3) 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, … , 𝑓𝑚}, 𝑙𝑒𝑣𝑒𝑙, 𝑙𝑎𝑏𝑒𝑙 > ;

4) Hai nút 𝑁𝑜𝑑𝑒𝑖 và 𝑁𝑜𝑑𝑒𝑗 có quan hệ anh em nếu 𝑁𝑜𝑑𝑒𝑖 và 𝑁𝑜𝑑𝑒𝑗 có cùng

một nút cha: 𝑁𝑜𝑑𝑒𝑖. 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑁𝑜𝑑𝑒𝑗. 𝑝𝑎𝑟𝑒𝑛𝑡 ;

5) Hai nút 𝑁𝑜𝑑𝑒𝑖 và 𝑁𝑜𝑑𝑒𝑗 có quan hệ cha con nếu 𝑁𝑜𝑑𝑒𝑗. 𝑝𝑎𝑟𝑒𝑛𝑡 =

𝑁𝑜𝑑𝑒𝑖 hoặc 𝑁𝑜𝑑𝑒𝑖. 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑁𝑜𝑑𝑒𝑗 ;

6) Hai nút 𝑁𝑜𝑑𝑒𝑖 và 𝑁𝑜𝑑𝑒𝑗 là đồng cấp nếu 𝑁𝑜𝑑𝑒𝑖. 𝑙𝑒𝑣𝑒𝑙 = 𝑁𝑜𝑑𝑒𝑗. 𝑙𝑒𝑣𝑒𝑙 7) 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ẻ. Ký hiệu (𝑁𝑜𝑑𝑒𝑖. {𝐿𝑒𝑓𝑡}) ≠ (𝑁𝑜𝑑𝑒𝑖. {𝑅𝑖𝑔ℎ𝑡})

8) Khi mỗi véc-tơ 𝑓𝑗 = (𝑥𝑗1, … , 𝑥𝑗𝑛) là giá trị đầu vào (input) tại mỗi 𝑁𝑜𝑑𝑒𝑖 thì kết quả đầu ra (output) được xác định bởi công thức (2.1) [55]; giá trị hàm truyền 𝑆𝑖𝑔𝑚𝑜𝑖𝑑() được xác định bởi công thức (2.2) [55]. Trong đó 𝑤𝑖 là véc-tơ trọng số lưu trữ tại 𝑁𝑜𝑑𝑒𝑖.

(2.1) 𝑦𝑖𝑗 = 𝑆𝑖𝑔𝑚𝑜𝑖𝑑(𝑤𝑖 ∗ 𝑓𝑗)

1+𝑒−(𝑤𝑖∗ 𝑓𝑖)

(2.2) S𝑖𝑔𝑚𝑜𝑖𝑑 (𝑤𝑖 ∗ 𝑓𝑗) =

“Đa nhánh” trong quá trình xây dựng KD-Tree được xác định số nhánh (𝑏; 𝑏 > 2) khởi tạo nhằm làm giảm chiều cao (ℎ) trên cùng một bộ dữ liệu thực nghiệm. “Cân bằng” trên KD-Tree luôn được tạo ra các nút lá đồng cấp (𝑙𝑒𝑣𝑒𝑙) do quá trình xây dựng KD-Tree là tạo một khung cây trước khi chèn dữ liệu vào cây.

Hình 2.1. Mô tả các thành phần nút gốc, nút trong và nút lá trên KD-Tree

Điểm cải tiến trong cấu trúc KD-Tree là đưa kỹ thuật học máy vào quá trình xây

dựng theo phương pháp học bán giám sát, mỗi nút trên KD-Tree là một mạng nơ-ron

một nút để thực hiện phân lớp hình ảnh một lần; quá trình khởi tạo ngẫu nhiên và sau

đó huấn luyện tập véc-tơ trọng số nhằm tăng kết quả phân lớp và gom cụm tại nút lá.

Trong khi đó, cấu trúc KD-Tree nguyên thủy [10], dữ liệu được lưu tại tất cả các nút

trên cây và chưa huấn luyện trọng số theo phương pháp học bán giám sát để hình

thành gom cụm và chưa thực hiện phân lớp đối tượng dựa trên cây. Các thành phần

KD-Tree mô tả như Hình 2.1.

Mô tả thuật toán xây dựng cấu trúc KD-Tree

Mỗi cấu trúc KD-Tree được xây dựng dựa trên từng bộ ảnh thực nghiệm riêng

biệt nên số nhánh (𝑏), chiều cao (ℎ) và số nút lá khác nhau. Cấu trúc KD-Tree được

khởi tạo là một khung cây gồm một nút gốc, các nút trong lưu véc-tơ trọng số, nút lá

rỗng; khung cây được tính toán theo số tầng, số nhánh tối đa tại mỗi nút trong để hình

thành số nút lá tối đa cần thiết cho lưu trữ dữ liệu trên từng bộ ảnh, quá trình xây

dựng KD-Tree thực hiện theo thứ tự các bước:

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à 𝑏. Khi đó số nút lá tối đa trên KD-Tree được tạo ra là 𝑏ℎ. Chẳng hạn như

𝑏 = 3; khi đó số nút lá hình thành là 𝑏ℎ = 34 = 81.

bộ ảnh Wang có 81 phân lớp, cần tạo ra 81 nút lá thì chiều cao cây là ℎ = 4 và số nhánh

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 Nodei. 𝑙𝑒𝑓𝑡 = 0.5 và ngưỡng phải

Nodei. 𝑟𝑖𝑔ℎ𝑡 = 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; giá trị đầu ra của

véc-tơ 𝑓𝑗 tại 𝑁𝑜𝑑𝑒𝑖 được tính theo công thức (2.2) và xác định đường đi cho 𝑓𝑗 đến

nhánh con thuộc tầng kế tiếp theo quy tắc (2).

Bước 5. Lặp lại bước 3, bước 4 đến khi gặp nút lá 𝑙𝑒𝑎𝑓𝑘 thì ghi 𝑓𝑗 vào 𝑙𝑒𝑎𝑓𝑘

Hình 2.2. Minh họa quá trình tạo nhánh con tại 𝐍𝐨𝐝𝐞𝐢

Quá trình tạo nhánh con trái, con phải và tìm nhánh con gần nhất cho véc-tơ đầu

vào 𝑓𝑗 được minh họa bởi Hình 2.2, trong đó tập véc-tơ trọng số < 𝑤0, … , 𝑤ℎ−1 > từ

gốc đến các nút trong được lưu trữ tại Nodei để tạo thành phân cụm tại nút lá. Việc

chọn nhánh cho véc-tơ đầu vào thực hiện theo quy tắc (2) như sau:

1. Nếu yij > Nodei. right thì 𝑓𝑗 chọn nhánh con phải; đồng thời cập nhật ngưỡng

phải Nodei. right = yij;

2. Nếu yij < Nodei. left thì 𝑓𝑗 chọn nhánh con trái; đồng thời cập nhật ngưỡng

trái Nodei. left = yij;

3. Nếu Nodei. 𝑙𝑒𝑓𝑡 ≤ 𝑦𝑖𝑗 ≤ Nodei. 𝑟𝑖𝑔ℎ𝑡 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 𝑓𝑗.

Hình 2.3. Cấu trúc KD-Tree đa nhánh, cân bằng

Quá trình xây dựng cấu trúc KD-Tree được minh họa bởi Hình 2.3. Kết quả của

quá trình này là hình thành nên các phân cụm (Cluster) tại mỗi nút lá, đồng thời mỗi

nút lá cũng là một phân lớp gồm các ảnh có cùng nhãn lớp.

Cấu trúc KD-Tree được thực hiện một số thao tác gồm: xây dựng, gán nhãn nút

lá, huấn luyện trọng số và tìm kiếm trên KD-Tree được trình bày ở các mục 2.2.2 –

2.2.5. Đối với một nút lá có số lượng véc-tơ lớn thì thực hiện quá trình phát triển

thành cây con được trình bày ở mục 2.4.

2.2.2. Thuật toán xây dựng cấu trúc KD-Tree

Thuật toán 2.1. xây dựng cấu trúc KD-Tree dựa vào các mô tả ở mục 2.2.1 ở trên. Các biến sử dụng trong thuật toán gồm: 𝐹 tập véc-tơ cần xây dựng KD-Tree, ℎ chiều cao, 𝑏 số nhánh tại mỗi nút trong, 𝑊𝑘𝑡 là tập véc-tơ trọng số ngẫu nhiên.

Thuật toán 2.1. Xây dựng cấu trúc KD-Tree đa nhánh, cân bằng

1. Input: Tập 𝐹 = {𝑓𝑖:𝑓𝑖 = (𝑥𝑖0, 𝑥𝑖1, …,𝑥𝑖𝑛); i = 1, ..., k}; chiều cao ℎ; số nhánh tối đa 𝑏. Bộ trọng số khởi tạo 𝑊𝑘𝑡 = {𝑊𝑖: 𝑊𝑖= (𝑥𝑖0, 𝑥𝑖1, …,𝑥𝑖𝑛); i = 0… h-1};

Khởi tạo khung cây KD-Tree theo chiều cao ℎ, số nhánh 𝑏; Khởi tạo cận trái, cận phải tất cả 𝑁𝑜𝑑𝑒𝑖 𝑙à 𝑁𝑜𝑑𝑒𝑖.𝑙𝑒𝑓𝑡 = 𝑁𝑜𝑑𝑒𝑖.𝑟𝑖𝑔ℎ𝑡 = 0.5; Gán nhãn nút lá ngẫu nhiên theo 𝑙𝑎𝑏𝑒𝑙 bộ ảnh thực nghiệm; For (𝑑𝑢𝑦ệ𝑡 𝑑𝑎𝑛ℎ 𝑠á𝑐ℎ 𝑐á𝑐 𝑣é𝑐 − 𝑡ơ 𝑓𝑖 𝑡ℎ𝑢ộ𝑐 𝑡ậ𝑝 𝐹) do For (int j = 0; j <= h-1; j++) do

If (Sigmoid (𝑓𝑖, 𝑊𝑗) < 𝑁𝑜𝑑𝑒𝑗.𝑙𝑒𝑓𝑡 then

𝑓𝑖 đi theo nhánh trái và cập nhật ngưỡng trái của 𝑁𝑜𝑑𝑒𝑗;

EndIF; If (Sigmoid (𝑓𝑖, 𝑊𝑗) > 𝑁𝑜𝑑𝑒𝑗.𝑟𝑖𝑔ℎ𝑡) then

𝑓𝑖 đi theo nhánh phải và cập nhật ngưỡng phải của 𝑁𝑜𝑑𝑒𝑗;

2. Output: KD-Tree; 3. Function CKDT (F, 𝑊𝑘𝑡, h, b); 4. Begin 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

EndIf; IF (𝑁𝑜𝑑𝑒𝑗.𝑙𝑒𝑓𝑡 <= Sigmoid (𝑓𝑖, 𝑊𝑗) and Sigmoid (𝑓𝑖, 𝑊𝑗) <= 𝑁𝑜𝑑𝑒𝑗.𝑟𝑖𝑔ℎ𝑡) then Chọn nhánh gần nhất để đi đến tầng tiếp theo;

EndIf; EndFor;

If (𝑁𝑜𝑑𝑒𝑖.𝑙𝑒𝑣𝑒𝑙 = ℎ − 1) then // kiểm tra Nodei là nút lá IF (𝑓𝑖.𝑙𝑎𝑏𝑒𝑙 = 𝐿𝑒𝑎𝑓𝑘.𝑙𝑎𝑏𝑒𝑙) then ghi 𝑓𝑖 𝑣à𝑜 𝐿𝑒𝑎𝑓𝑘; Else

Tìm nhánh gần nhất 𝐿𝑒𝑎𝑓𝑘+1 và ghi 𝑓𝑖 𝑣à𝑜 𝐿𝑒𝑎𝑓𝑘+1; EndIf;

17. 18. 19. 20. 21. 22. 23. 24. 25. EndIf; 26. EndFor; 27. Return KD-Tree; 28. End.

Trong thuật toán 2.1, độ phức tạp lớn nhất ở bước (8) – (26) thực hiện 2 vòng

𝐹𝑜𝑟 lồng nhau. Vòng 𝐹𝑜𝑟 thứ nhất duyệt 𝑛 phần tử cần thêm vào cây. Vòng 𝐹𝑜𝑟 thứ

hai duyệt qua chiều cao cây ℎ. Do đó, tổng độ phức tạp là 𝑂(𝑛 × ℎ), ℎ là hằng số có

giá trị tối đa là 6 cho bộ ảnh Caltech-256 (các bộ ảnh COREL, Wang, Caltech-101

thì ℎ < 6) . Vì vậy, độ phức tạp của thuật toán 2.1 là 𝑂(𝑛).

Trong quá trình xây dựng cấu trúc KD-Tree luôn được xác định trước số nút lá

bằng cách dựa vào số phân lớp trên bộ ảnh thực nghiệm để khởi tạo số nhánh 𝑏 và

chiều cao ℎ của cây; khi đó số nút lá tối đa trên KD-Tree là 𝑏ℎ. Tuy nhiên, trong

trường hợp tập dữ liệu tăng thêm số phân lớp, lúc này số nút lá buộc phải tăng theo

bằng cách thay đổi số nhánh trên KD-Tree hoặc thay đổi chiều cao KD-Tree. Cấu

trúc KD-Tree tăng trưởng được nút lá là do quá trình xây dựng các tham số 𝑏, ℎ thay

đổi theo từng bộ ảnh thực nghiệm.

Đóng góp của thuật toán 2.1 là quá trình xây dựng KD-Tree tại mỗi nút trên cây

được tính toán như mạng Nơ-ron một tầng để thực hiện phân loại đối tượng ảnh đầu

vào. Trong đó, mỗi giá trị đầu ra tại mỗi nút được xác định bằng hàm truyền 𝑆𝑖𝑔𝑚𝑜𝑖𝑑.

Trên cơ sở này, dữ liệu đầu vào được xác định đường đi theo quy tắc xây dựng cây

tìm kiếm. Kết quả của thuật toán là sự kết hợp giữa học máy và cấu trúc dữ liệu đã

mang lại kết quả tốt cho bài toán tìm kiếm ảnh dựa trên KD-Tree.

2.2.3. Quá trình gán nhãn nút lá

Mục đích của gán nhãn nút lá là để tính số lượng véc-tơ cùng một nhãn lớp lưu

trữ tại một nút lá, từ đó tính kết quả phân lớp trên KD-Tree. Mỗi nút lá (𝑙𝑒𝑎𝑓𝑗) lưu

trữ tập véc-tơ đặc trưng hình ảnh thuộc nhiều phân lớp với số lượng khác nhau; vì

vậy 𝑙𝑒𝑎𝑓𝑗 cần gán một nhãn (𝑙𝑎𝑏𝑒𝑙) dựa trên tần số xuất hiện của 𝑙𝑎𝑏𝑒𝑙 nhiều nhất,

thứ tự thực hiện gồm 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ởi ma trận 𝑀𝑇(𝑛, 𝑚): {𝑛 = 𝑠ố 𝑛ℎã𝑛 𝑙ớ𝑝; 𝑚 = 𝑠ố 𝑛ú𝑡 𝑙á};

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, bước 4 cho đến khi gán hết các nhãn cho tất cả nút lá.

Hàm gán nhãn nút lá SL2L được mô tả quá trình thực hiện như sau: Dữ liệu đầu

vào là (KD-Tree, danh sách nhãn 𝐿𝑖𝑠𝑡𝐿𝑎𝑏𝑒𝑙𝑠, danh sách nút lá 𝐿𝑖𝑠𝑡𝐿𝑒𝑎𝑣𝑒𝑠 chưa được

gán nhãn); giá trị đầu ra là danh sách nút lá đã gán nhãn 𝐿𝑖𝑠𝑡𝐿𝑒𝑎𝑣𝑒𝑠𝐴𝑑𝑑𝑒𝑑𝐿𝑎𝑏𝑒𝑙.

// Xây dựng ma trận vuông theo số nút lá 𝑛 và số nhãn 𝑚; For (int 𝑖 = 0; 𝑖 < 𝑛; 𝑖 + +) do

For (int 𝑗 = 0; 𝑗 < 𝑚; 𝑗 + +) do

𝑀𝑇(𝑛, 𝑚) = 𝐶𝑟𝑒𝑎𝑡𝑒𝑀𝑎𝑡𝑟𝑖𝑥(𝑛, 𝑚);

EndFor;

EndFor; // Duyệt qua ma trận tìm giá trị lớn nhất và gán nhãn cho từng nút lá; For (int 𝑖 = 0; 𝑖 < 𝑛; 𝑖 + +) do

For (int 𝑗 = 0; 𝑗 < 𝑚; 𝑗 + +) do

𝑉𝑇𝑀𝑎𝑥 = 𝑉𝑇𝑖,𝑗; 𝑀𝑎𝑥𝑙𝑎𝑏𝑒𝑙 = 𝑉𝑇𝑖,𝑗; 𝐿𝑒𝑎𝑓𝑗. 𝑙𝑎𝑏𝑒𝑙 = 𝑆𝑒𝑡𝑙𝑎𝑏𝑒𝑙(𝐿𝑒𝑎𝑓𝑗, 𝐿𝑎𝑏𝑒𝑙𝑖, 𝑀𝑎𝑥𝑙𝑎𝑏𝑒𝑙); EndFor;

EndFor; Bổ sung nút lá đã gán nhãn vào 𝐿𝑖𝑠𝑡𝐿𝑒𝑎𝑣𝑒𝑠𝐴𝑑𝑑𝑒𝑑𝐿𝑎𝑏𝑒𝑙; Return Danh sách nút lá đã gán nhãn; 1. Function SL2L (𝐾𝐷 − 𝑇𝑟𝑒𝑒, 𝐿𝑖𝑠𝑡𝐿𝑎𝑏𝑒𝑙𝑠) 2. Begin 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. End.

2.2.4. Huấn luyện trọng số trên cấu trúc KD-Tree

Ban đầu bộ véc-tơ 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 bộ 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 và lấy đều trên các phân lớp, 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 bổ sung dữ liệu 𝐸𝑝𝑜𝑐ℎ(𝑖+1) để xây dựng và huấn luyện KD-Tree cho 𝐸𝑝𝑜𝑐ℎ(𝑖+1) tìm 𝐹max(𝑖+1). Kết quả của quá trình này là thu được bộ véc-tơ phân lớp tốt nhất (𝐹𝑚𝑎𝑥) trên từng bộ ảnh thực nghiệm. Mỗi véc-tơ trọng số 𝑤𝑖 = (𝑤𝑖0, … , 𝑤𝑖𝑛) được huấn luyện theo đạo hàm ngược hướng Gradient nhằm giảm sai số trung bình dựa trên hàm truyền 𝑆𝑖𝑔𝑚𝑜𝑖𝑑( ) = 𝜎( ). Giá trị véc-tơ 𝑤𝑖 tại 𝑁𝑜𝑑𝑒𝑖 được cập nhật theo công thức Gradient (2.3) được đề xuất, hệ số học 𝑛 = 0.005 là hằng số cho trước. Quá trình

huấn luyện trọng số trên KD-Tree minh họa như Hình 2.4.

𝑤𝑖 = 𝑤𝑖 − 𝜎(𝑤𝑖 ∗ 𝑓𝑖) ∗ 𝑛 ∗ = 𝑤𝑖 − 𝜎(𝑤𝑖 ∗ 𝑓𝑖) ∗ 𝑛 ∗ 𝜎(𝑤𝑖 ∗ 𝑓𝑖) ∗ (1 −

𝜕(𝜎(𝑤𝑖∗𝑓𝑖)) 𝜕(𝑤𝑖)

(2.3) 𝜎(𝑤𝑖 ∗ 𝑓𝑖))

Hình 2.4. Mô hình xây dựng và huấn luyện KD-Tree theo từng 𝐄𝐩𝐨𝐜𝐡 dữ liệu

Thuật toán 2.2. Huấn luyện tập véc-tơ trọng số trên KD-Tree 1. Input: Bộ véc-tơ khởi tạo ngẫu nhiên 𝐼𝑛𝑖𝑡𝑊𝑒𝑖𝑔ℎ𝑡; tập dữ liệu 𝐸𝑝𝑜𝑐ℎ𝑖 có 𝑛 phần tử;

2. Output: Bộ véc-tơ huấn luyện 𝑇𝑟𝑎𝑖𝑛𝑊𝑒𝑖𝑔ℎ𝑡; 3. Function TVKDT (𝐼𝑛𝑖𝑡𝑊𝑒𝑖𝑔ℎ𝑡, 𝐸𝑝𝑜𝑐ℎ𝑖) 4. Begin 5. 𝑇𝑟𝑎𝑖𝑛𝑊𝑒𝑖𝑔ℎ𝑡 = 𝐼𝑛𝑖𝑡𝑊𝑒𝑖𝑔ℎ𝑡; 6. Repeat 7. 8. 9. 10. 11.

12. 13. 14. 15. 16. 17. 18. 19. 20.

// Tạo KD-Tree với bộ trọng số ngẫu nhiên 𝐼𝑛𝑖𝑡𝑊𝑒𝑖𝑔ℎ𝑡 CKDT (𝐸𝑝𝑜𝑐ℎ𝑖,𝐼𝑛𝑖𝑡𝑊𝑒𝑖𝑔ℎ𝑡, h, b); // Gán nhãn nút lá; SL2L (𝐾𝐷 − 𝑇𝑟𝑒𝑒, 𝐿𝑖𝑠𝑡𝐿𝑎𝑏𝑒𝑙𝑠); 𝑃𝑖 = (số véc-tơ đúng nhãn/tổng số véc-tơ thực nghiệm) với bộ véc-tơ 𝐼𝑛𝑖𝑡𝑊𝑒𝑖𝑔ℎ𝑡; Xác định đường đi sai của những véc-tơ 𝑓𝑘 trên KD-Tree; Xác định đường đi đúng của những véc-tơ 𝑓𝑘; Tìm vị trí 𝑛𝑜𝑑𝑒𝑖 làm sai đường đi của véc-tơ 𝑓𝑘; 𝑇𝑟𝑎𝑖𝑛𝑊𝑒𝑖𝑔ℎ𝑡 = điều chỉnh véc-tơ lưu tại 𝑛𝑜𝑑𝑒𝑖 để 𝑓𝑘 đúng đường đi; // Tạo lại KD-Tree với Train𝑊𝑒𝑖𝑔ℎ𝑡; CKDT (𝐸𝑝𝑜𝑐ℎ𝑖,Train𝑊𝑒𝑖𝑔ℎ𝑡, h, b); // Gán nhãn nút lá; SL2L (𝐾𝐷 − 𝑇𝑟𝑒𝑒, 𝐿𝑖𝑠𝑡𝐿𝑎𝑏𝑒𝑙𝑠); 𝑃𝑗= (số véc-tơ đúng nhãn/tổng số véc-tơ thực nghiệm) với bộ véc-tơ 𝑇𝑟𝑎𝑖𝑛𝑊𝑒𝑖𝑔ℎ𝑡;

21. Until (𝑃𝑗< 𝑃𝑖); 22. 𝑇𝑟𝑎𝑖𝑛𝑊𝑒𝑖𝑔ℎ𝑡 = Tập véc-tơ trọng số đã điều chỉnh; 23. Return 𝑇𝑟𝑎𝑖𝑛𝑊𝑒𝑖𝑔ℎ𝑡; 24. End.

Thuật toán 2.2. được thực hiện lần lượt các bước (1) đến (16) gồm:

(1) Tạo KD-Tree độ phức tạp 𝑂(𝑛), với 𝑛 là số phần tử tham gia tạo KD-Tree;

(2) Duyệt trên từng véc-tơ, độ phức tạp là 𝑂(𝑛);

(10) Trường hợp xấu nhất, tất cả véc-tơ đều sai với gán nhãn ban đầu, phải duyệt qua tất cả véc-tơ từ nút lá trở về gốc (chiều cao ℎ) thì chi phí là O(𝑛);

(11) Trường hợp xấu nhất phải duyệt qua tất cả các véc-tơ từ nút lá trở về gốc nên số phép toán là (ℎ ∗ 𝑛);

(12) Trường hợp xấu nhất, vị trí 𝑁𝑜𝑑𝑒𝑖 sai là nút gốc nên số phép toán là (ℎ ∗ 𝑛);

(13) Trường hợp xấu nhất, cần điều chỉnh hết các véc-tơ trọng số thì số phép toán là 𝑂(𝑛);

(14) Lặp lại bước (1), độ phức tạp 𝑂(𝑛);

(16) Lặp lại bước (2), độ phức tạp là 𝑂(𝑛);

Số phép toán sau một quá trình từ bước (1) đến (16) là 𝑂(𝑛). Các lệnh thực hiện từ bước (1) đến (16) trong vòng lặp Repeat … Until. Vì vậy độ phức tạp của thuật toán 2.2 là 𝑂(𝑛2).

Đóng góp của thuật toán 2.2 là quá trình huấn luyện trọng số phân lớp tại mỗi nút trên KD-Tree hoàn toàn khả thi với cấu hình máy tính server đã thực hiện với thời gian chấp nhận được. Kết quả huấn luyện trọng số đã nâng cao kết quả phân cụm tại các nút lá trên KD-Tree.

Hình 2.5 là kết quả tập véc-tơ phân lớp cho bộ ảnh COREL sau khi đã huấn

luyện để kết quả phân lớp đạt 0.8687 chiều cao cây bằng 2 và số nhánh tối đa tại mỗi

nút là 4. Trong khi đó, với bộ trọng số khởi tạo ngẫu nhiên ban đầu thì kết quả phân

lớp là 0.5200.

Hình 2.5. Minh họa tập véc-tơ phân lớp trên KD-Tree cho bộ ảnh COREL

Chi phí huấn luyện bộ trọng số trên cấu trúc KD-Tree ứng với từng bộ ảnh thực

nghiệm được trình bày trong Bảng 2.1 như sau:

Bảng 2.1. Chi phí huấn luyện KD-Tree trên các bộ ảnh thực nghiệm

Tập ảnh Kết quả phân lớp chưa huấn luyện Kết quả phân lớp đã huấn luyện Thời gian huấn luyện

COREL 0.5200 0.8687 04:11:00

Wang 0.3904 0.8020 06:15:56

Caltech-101 0.4806 0.7705 07:45:45

Caltech-256 0.5509 0.7572 11:28:09

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 tại

𝑙𝑒𝑎𝑓𝑘. Hàm tìm kiếm trên KD-Tree (SKDT) được mô tả dữ liệu đầu vào là véc-tơ đặc

trưng 𝑓𝑖 của ảnh 𝐼, 𝐾𝐷 − 𝑇𝑟𝑒𝑒; giá trị cần trả về là nút lá 𝑙𝑒𝑎𝑓𝑘 chứa véc-tơ 𝑓𝑖;

Duyệt qua nút gốc và nút trong theo chiều cao KD-Tree; Tìm nhánh gần nhất cho đường đi của 𝑓𝑖; Nút lá 𝑙𝑒𝑎𝑓𝑘 là vị trí cần tìm của 𝑓𝑖; Return 𝑙𝑒𝑎𝑓𝑘; 1. Function SKDT (𝑓𝑖, 𝐾𝐷 − 𝑇𝑟𝑒𝑒) 2. Begin 3. 4. 5. 6. 7. End.

Trên cơ sở lý thuyết về xây dựng, huấn luyện và các phép toán thực hiện trên

KD-Tree, một hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree được thực nghiệm với bộ

ảnh COREL, Wang, Caltech-101, Caltech-256 được trình bày trong Mục 2.2.6.

2.2.6. Hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree

Trong mô hình tìm kiếm ảnh dựa trên KD-Tree Hình 2.6 thì ontology được kế

thừa từ công trình [51] và bổ sung thêm dữ liệu thực nghiệm Caltech-101, Caltech-

256. Trong đó, khung ontology được xây dựng bán tự động từ công trình [51] là một

Framework làm nền tảng để phát triển, bổ sung thêm các tập ảnh thực nghiệm. Trong

mô hình này, thuật toán 2.1 được sử dụng để xây dựng KD-Tree; thuật toán 2.2 dùng

để huấn luyện trọng số trên từng bộ ảnh và thuật toán 2.3 được sử dụng tìm kiếm tập

ảnh tương tự với ảnh đầu vào.

Hình 2.6. Mô hình tìm kiếm ảnh dựa trên KD-Tree (SB-KDT)

Mô hình tìm kiếm ảnh đề xuất gồm pha tiền xử lý và pha tìm kiếm. Trong đó, cấu

trúc KD-Tree và pha tìm kiếm ảnh là phần đề xuất; phần ontology là kế thừa từ công

trình [51] sau khi bổ sung dữ liệu thực nghiệm bộ ảnh Caltech-101, Caltech-256. Mô

hình này gồm các bước như sau:

Bước 1. Trích xuất véc-tơ đặc trưng gồm 81 chiều tập dữ liệu ảnh thực nghiệm (1).

Bước 2. Xây dựng cấu trúc KD-Tree (2).

Bước 3. Bổ sung dữ liệu ảnh từ WWW và tập ảnh thực nghiệm vào ontology (7)

Bước 4. Trích xuất véc-tơ đặc trưng ảnh đầu vào (3).

Bước 5. Tìm kiếm tập ảnh tương tự theo nội dung dựa trên cấu trúc KD-Tree (4).

Bước 6. Trích xuất tập ảnh tương tự và tập từ thị giác; tạo câu truy vấn SPARQL

dựa trên tập từ thị giác (5).

Bước 7. Tìm kiếm trên ontology tập ảnh tương tự theo ngữ nghĩa với ảnh đầu vào

bằng câu truy vấn SPARQL (8).

Bước 8. Trích xuất tập ảnh tương tự (9).

Cấu trúc KD-Tree và ontology đã xây dựng ở pha tiền xử lý. Quá trình tìm kiếm

tập ảnh tương tự với ảnh đầu vào 𝐼 được thực hiện bởi Thuật toán 2.3.

Thuật toán 2.3. Tìm kiếm ảnh tương tự trên hệ SB-KDT 1. Input: Ảnh truy vấn 𝐼; KD-Tree, ontology 2. Output: Tập ảnh tương tự 𝑆𝐼 của ảnh 𝐼; 3. Function SKDO (Ảnh I, KD-Tree, Ontology) 4. Begin 5. 6. 7. 8. 9.

Ban đầu gán tập ảnh tương tự 𝑆𝐼 là rỗng; Trích xuất véc-tơ đặc trưng 𝑓𝑖 của ảnh 𝐼 có 81 thành phần; // Tìm kiếm trên KD-Tree trích xuất tập ảnh 𝑆𝐶 tại nút lá; 𝑆𝐶 = 𝑺𝑲𝑫𝑻(𝑓𝑖, 𝐾𝐷 − 𝑇𝑟𝑒𝑒); Trích xuất tập từ thị giác từ tập 𝑆𝐶 theo số ảnh thuộc cùng một phân lớp nhiều nhất; Tạo câu truy vấn SPARQL từ tập từ thị giác; Tìm kiếm trên ontology bằng câu truy vấn SPARQL; Trích xuất tập ảnh tương tự 𝑆𝐼 với ảnh 𝐼; 10. 11. 12. 13. Return 𝑆𝐼; 14. End.

Thuật toán 2.3. thực hiện các bước:

(1) Tìm kiếm trên KD-Tree trích xuất tập ảnh tương tự tại nút lá mất chi phí là 𝑂(ℎ × 𝑏) = 𝑂(1); vì ℎ, 𝑏 (hằng số nhỏ) lần lượt chiều cao và số nhánh của KD-Tree;

(2) Tìm kiếm trên ontology mất chi phí 𝑂(1);

Vậy độ phức tạp của thuật toán 2.3 là 𝑂(1).

Quá trình tìm kiếm trên KD-Tree để tìm tập ảnh tương tự theo nội dung 𝑆𝐶 tại nút lá chứa véc-tơ ảnh đầu vào. Tập từ thị giác được trích xuất dựa trên tần số xuất hiện nhiều nhất của các ảnh thuộc cùng một phân lớp trong tập 𝑆𝐶. Quá trình xây dựng tập từ thị giác được minh họa như Hình 2.7 [CT4] như sau:

Hình 2.7. Minh họa quá trình xây dựng tập từ thị giác

Sau khi xây dựng tập từ thị giác, câu truy vấn SPARQL được xây minh họa như Hình 2.8. Trong phần này, câu truy vấn SPARQL được xây dựng bởi hai phép toán hội (UNION), phép toán và (AND) dựa trên tên phân lớp của ảnh truy vấn đã phân lớp [CT4].

Hình 2.8. Minh họa câu truy vấn SPARQL

Hình 2.9. Hệ tìm kiếm ảnh SB-KDT

Hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree được (SB-KDT) minh họa bởi Hình

2.9. Kết quả tìm kiếm tập ảnh tương tự theo nội dung 𝐶𝐼 của ảnh đầu vào 𝐼 dựa trên

KD-Tree là quá trình trích xuất tập từ thị giác. Tập từ thị giác được xây dựng dựa trên

những ảnh cùng phân lớp thuộc tập 𝐶𝐼 có tần số xuất hiện nhiều nhất. Từ đó, câu truy

vấn SPARQL được xây dựng để tìm tập ảnh tương tự theo ngữ nghĩa dựa trên ontology. Kết quả trích xuất tập ảnh tương tự theo ngữ nghĩa với ảnh đầu vào (COREL101.jpg) được minh họa bởi Hình 2.10 [CT2].

Hình 2.10. Kết quả tập ảnh tương tự của ảnh COREL101.jpg hệ SB-KDT

Bảng 2.2. Kết quả tìm kiếm ảnh tương tự hệ SB-KDT [CT2]

Tập ảnh Precision Recall F-measure Thời gian tìm kiếm trung bình (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

Bảng 2.3. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh COREL (SB-KDT)

Phương pháp MAP

B_SHIFT, (Douik, Ali. et al.), 2016 [23] 0.7200

Shape and Texture Features, (Abdulkadhem, et al.), 2019 [1] 0.7286

ORB 8-dimensions with MPL, (P. Chhabra et al.), 2020 [17] 0.6656

C-Tree, (Nhi, N. T. U. et al. ), 2021 [50] 0.6777

0.7998 SB-KDT

Bảng 2.4. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-KDT)

MAP Phương pháp

0.6320 ORB and SIFT features, (P. Chhabra et al.), 2020 [17]

0.6072 SBIR-CT, (Nhi N.T.U et al.), 2021 [50]

0.5590 SVM, (Das et al.), 2017 [18]

0.5970 8D-GLCM+GSF+ HSVCM, (Bella & Vasuki), 2019 [9]

0.7810 SB-KDT

Bảng 2.5. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-KDT)

MAP Phương pháp

0.6314 CE and Valleys with SVM, (Rajesh, M. B., et al.), 2020 [58]

0.6942 CBIR Multi-trend Structure, (Sathiamoorthy, S., et al.), 2020 [65]

0.6200 Feature Detector, (Ahmed, K. T., et al.), 2021 [2]

0.6450 CBIR with features, (Soumya Prakash Rana, et al.), 2019 [60]

0.7101 SB-KDT

Bảng 2.6. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-256 (SB-KDT)

MAP Phương pháp

0.4630 Visual Words FVFF, (Mehmood, Z., et al.), 2018 [45]

0.4752 SVM, (Uzma Sharif, et al.), 2019 [66]

0.5726 Ensembles of deep learning (Safa Hamreras), 2020 [29] (50 classes)

0.6985 CBIR, (Khawaja Tehseen Ahmed), 2019 [3] (TopK = 25)

0.7020 SB-KDT

Hệ tìm kiếm ảnh SB-KDT với độ chính xác tìm kiếm ảnh cao hơn các công

trình khác thực nghiệm trên cùng bộ dữ liệu vì:

(1) Quá trình xây dựng KD-Tree song song huấn luyện trọng số giúp cho kết

quả gom cụm tại các nút lá cao;

(2) Kết hợp một cấu trúc dữ liệu lưu trữ và ontology giúp nâng cao độ chính

xác tìm kiếm ảnh do thực hiện qua hai lần bộ lọc gom cụm và phân lớp.

2.3. Cấu trúc iKD_Tree

2.3.1. Mô tả 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 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ó độ đo tương tự vào cùng một cụm là nhiều nhất; đồ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. Cấu trúc iKD_Tree minh họa bởi Hình 2.11 [CT3].

Hình 2.11. Minh họa cấu trúc iKD_Tree

2.3.2. Xây dựng cấu trúc iKD_Tree

Thuật toán K-Means áp dụng trong xây dựng cấu trúc iKD_Tree [CT3] được minh họa như Hình 2.12.

Hình 2.12. Minh họa thuật toán K-Means trên 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 thuộc nhánh con tầng kế tiếp với các quy tắc sau:

tạo nhánh con phải; cập nhật 𝑁𝑜𝑑𝑒𝑖. 𝑟𝑖𝑔ℎ𝑡 = 𝑦𝑖𝑗 < 𝑁𝑜𝑑𝑒𝑖. 𝑙𝑒𝑓t tạo nhánh con trái; cập nhật 𝑁𝑜𝑑𝑒𝑖. 𝑙𝑒𝑓𝑡 = 𝑦𝑖𝑗

1. Nếu 𝑦𝑖𝑗 > 𝑁𝑜𝑑𝑒𝑖. 𝑟𝑖𝑔ℎ𝑡 + 𝛼 2. Nếu 𝑦𝑖𝑗 − 𝛼 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ơ 𝑓𝑗. 𝛼 ; 𝑁𝑜𝑑𝑒𝑖. 𝑟𝑖𝑔ℎ𝑡 + 𝛼

Thuật toán K-Means trên cấu trúc iKD_Tree được mô tả bằng Hàm kMiKDT với dữ liệu đầu vào là véc-tơ 𝑓𝑗 ∈ F, F là tập véc-tơ xây dựng iKD_Tree; đầu ra là xác định nhánh thứ 𝑘 được chọn làm đường đi cho véc-tơ 𝑓𝑗 đến tầng kế tiếp của 𝑁𝑜𝑑𝑒𝑖;

2∗𝑐

∗ 𝑝;

Gán số phân lớp tập ảnh là 𝑐; hiệu suất phân lớp trên KD-Tree là 𝑝; Khởi tạo hệ số 𝛼 = Mỗi véc-tơ đầu vào 𝑓𝑗 thì tính

Tính 𝑦𝑖𝑗 = giá trị đầu ra của véc-tơ 𝑓𝑗 tại 𝑁𝑜𝑑𝑒𝑖; Tính khoảng cách từ 𝑦𝑖𝑗 đến các tâm là nhánh con của 𝑁𝑜𝑑𝑒𝑖 + 𝛼; Chọn nhánh con gần nhất để xác định đường đi cho 𝑓𝑗;

Return nhánh thứ 𝑘 của 𝑁𝑜𝑑𝑒𝑖; 1. Function kMiKDT (𝑓𝑗, 𝑁𝑜𝑑𝑒𝑖) 2. Begin 3. 4. 5. 6. 7. 8. 9. 10. End.

Khi thêm một hệ số khoảng cách α vào quá trình chọn nhánh trên iKD_Tree có

những đặc điểm: (1) tăng khoảng cách giữa hai nhánh bất kỳ tức là khoảng cách các

tâm cụm tăng thêm một lượng α, dẫn đến quá trình gom các phần tử tương tự có xu

hướng tốt hơn; (2) độ rộng các nhánh toàn bộ cấu trúc iKD_Tree được tăng lên giúp

quá trình phân bổ các phần tử tránh hiện tượng một số nút lá chứa quá nhiều dữ liệu.

Số nhánh và chiều cao iKD_Tree cũng được xác định trước để tạo một khung cây

trước khi chèn dữ liệu vào iKD_Tree. Vì vậy, chất lượng phân cụm trên iKD_Tree

tốt hơn kết quả gom cụm trên KD-Tree và vẫn giữ được tính cân bằng.

Một số hạn chế khi thêm hệ số mở rộng α trên iKD_Tree cũng có những hạn

chế, cụ thể là: (1) khi chọn hệ số α quá lớn sẽ dẫn đến hiện tượng khoảng cách chồng

chéo nhau giữa các nhánh, nghĩa là xuất hiện vùng giao nhau cho hai nhánh nên việc

xác định đường đi cho những véc-tơ trong trường hợp này là khó khăn, có thể dẫn

2∗𝑐

đến việc chọn sai nhánh; (2) hệ số α được xác định theo biểu thức 𝛼 = ∗ 𝑝; trong

đó 𝑝 là hiệu suất phân lớp bộ ảnh thực nghiệm trước khi thêm hệ số 𝛼, 𝑐 là số phân

lớp của bộ ảnh thực nghiệm. Vì vậy, ban đầu khởi tạo các hệ số 𝛼 là (0.001, 0.0028,

0.003, 0.026) tương ứng với bộ ảnh (Caltech-256, Caltech-101, Wang, COREL). Việc

huấn luyện nhiều lần nên chi phí xây dựng iKD_Tree cần phải kiểm soát tốt, nếu chọn

hệ số α không phù hợp thì chi phí huấn luyện cao hơn so với việc tích hợp thêm các

kỹ thuật học máy khác trên KD-Tree mà kết quả gom cụm là tương đương.

Thuật toán k-NN thực hiện phân lớp tại nút lá 𝑙𝑒𝑎𝑓𝑘 theo các quy tắc sau:

1. Mỗi nút lá 𝑙𝑒𝑎𝑓𝑘 duyệt qua các véc-tơ, đếm tần số xuất hiện của tất cả các

véc-tơ cùng nhãn, gán nhãn cho 𝑙𝑒𝑎𝑓𝑘 là nhãn của véc-tơ có tần suất nhiều nhất.

2. Nếu hai nút lá 𝑙𝑒𝑎𝑓𝑘, 𝑙𝑒𝑎𝑓𝑙 có cùng nhãn thì thực hiện gán nhãn cho nút lá có số véc-tơ cùng label nhiều nhất.

3. Mỗi label chỉ được gán một lần cho một nút lá.

Thuật toán 2.4. Xây dựng cấu trúc iKD_Tree 1. Input: Tập véc-tor F = {𝑓𝑖:𝑓𝑖 = (𝑥𝑖0, 𝑥𝑖1, …,𝑥𝑖𝑛); i = 1, ..., k}; chiều cao ℎ; số nhánh tối 𝑏; bộ trọng số khởi tạo 𝑊𝑘𝑡 = {𝑊𝑖: 𝑊𝑖= (𝑥𝑖0, 𝑥𝑖1, …,𝑥𝑖𝑛); i = 0 … h- 1};

Khởi tạo 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒 là rỗng; For (duyệt qua số phần tử 𝑓𝑖 𝑡𝑟𝑜𝑛𝑔 𝐹) do

Tính giá trị đầu ra cho véc-tơ 𝑓𝑖 tại 𝑛𝑜𝑑𝑒𝑗; Gọi hàm kMiKDT xác định đường đi cho 𝑓𝑖; Khi đến tầng nút lá thì ghi 𝑓𝑖 vào nút lá;

EndFor; For (duyệt qua các nút lá 𝐿𝑒𝑎𝑓𝑘) do

Áp dụng thuật toán k-NN xác định nhãn lớp cho mỗi nút lá 𝐿𝑒𝑎𝑓𝑘;

EndFor; Return 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒;

2. Output: Cấu trúc 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒; 3. Function CiKDT (𝐹, 𝑊𝑘𝑡, h, b) 4. Begin 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. End.

Thuật toán 2.4 thực hiện các bước:

(1) Mỗi véc-tơ 𝑓𝑖 thuộc 𝐹 (gồm 𝑛 phần tử) sử dụng hàm kMiKDT để xác định

đường đi cho nhánh con tiếp theo nên độ phức là 𝑂(𝑛);

(2) Tại mỗi lá 𝐿𝑒𝑎𝑓𝑘 thực hiện gán nhãn, độ phức tạp là 𝑂(𝑏ℎ) = 𝑂(1); (3) Tổng độ phức tạp là 𝑀𝑎𝑥(𝑂(𝑛), 𝑂(1)); Vậy độ phức tạp của Thuật toán

2.4 là 𝑂(𝑛).

Đóng góp của thuật toán 2.4 là tích hợp thuật toán K-Means và k-NN vào quá trình xây dựng iKD_Tree. Với thuật toán này đã cho kết quả phân lớp ảnh trên iKD_Tree tốt hơn thuật toán phân lớp ảnh bằng k-NN thuần túy.

Duyệt từ gốc đến tầng nút trong sát nút lá tìm nhánh con cho véc-tơ 𝑓𝑖; Nếu (véc-tơ 𝑓𝑖 thuộc nút lá 𝑙𝑒𝑎𝑓𝑘) thì 𝐶𝐿I = 𝑙𝑒𝑎𝑓𝑘. 𝑙𝑎𝑏𝑒𝑙 Return 𝐶𝐿𝐼; Quá trình phân lớp ảnh dựa trên iKD_Tree được thực hiện bằng hàm CLiKD với dữ liệu đầu vào là véc-tơ đặc trưng 𝑓𝑖 của ảnh 𝐼, 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒; giá trị đầu ra là tên phân lớp 𝐶𝐿I của ảnh 𝐼. 1. Function CLiKD (𝑓𝑖, 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒) 2. Begin 3. 4. 5. 6. End.

2.3.3. Hệ tìm kiếm ảnh dựa trên cấu trúc iKD_Tree

Hình 2.13. Mô hình tìm kiếm ảnh dựa trên cấu trúc iKDTree [CT3]

Mô hình tìm kiếm ảnh dựa trên cấu trúc iKD_Tree và ontology gồm hai pha:

Pha tiền xử lý (Pre-processing phase) và pha tìm kiếm (Image retrieval phase). Trong

đó, cấu trúc iKD_Tree và pha tìm kiếm ảnh là phần đề xuất; phần ontology là kế thừa

từ công trình [51] sau khi bổ sung dữ liệu thực nghiệm. Trong mô hình này, thuật

toán 2.4 được sử dụng để xây dựng iKD_Tree và thuật toán 2.5 được sử dụng tìm

kiếm tập ảnh tương tự với ảnh đầu vào.

Bước 1: Trích xuất véc-tơ đặc trưng gồm 189 chiều của tập dữ liệu ảnh (1).

Bước 2: Xây dựng iKD_Tree theo phương pháp kết hợp K-Means, k-NN (2).

Bước 3: Trích xuất đặc trưng ảnh đầu vào (3), phân lớp ảnh bằng iKD_Tree (4).

Bước 4: Trích xuất phân lớp ảnh đầu vào và tạo câu truy vấn SPARQL (5).

Bước 5:Tìm kiếm trên ontology (7) trích xuất URIs và tập dữ liệu metadata của

hình ảnh (8); trích xuất tập ảnh tương tự theo ngữ nghĩa với ảnh đầu vào (9).

Quá trình tìm kiếm tập ảnh tương tự trên iKD_Tree thực hiện bởi Thuật toán 2.5.

Ban đầu gán tập ảnh tương tự 𝑆𝐼 𝑐ủ𝑎 ả𝑛ℎ 𝐼 𝑙à 𝑟ỗ𝑛𝑔; Trích xuất véc-tơ đặc trưng 𝑓𝑖 của ảnh 𝐼; // Phân lớp ảnh 𝐼; CLI = CLiKDT (𝑓𝑖, 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒); // Tạo câu truy vấn SPARQL từ phân lớp ảnh 𝐼; SPARQL = CreateSPARQL(𝐶𝐿𝐼); Tìm kiếm trên Ontology tập ảnh tương tự 𝑆𝐼 của ảnh 𝐼 bằng SPARQL; Return 𝑆𝐼; Thuật toán 2.5: Tìm kiếm tập ảnh tương tự trên hệ SB-iKDT 1. Input: Ảnh truy vấn I; 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒, ontology 2. Output: Tập ảnh tương tự 𝑆𝐼 của ảnh 𝐼; 3. Function SiKDT (Ả𝑛ℎ 𝐼, 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒, 𝑜𝑛𝑡𝑜𝑙𝑜𝑔𝑦) 4. Begin 5. 6. 7. 8. 9. 10. 11. 12. 13. End.

Thuật toán 2.5 thực hiện các bước:

(1) Phân lớp ảnh đầu vào với độ phức tạp là 𝑂(ℎ × 𝑏) = 𝑂(1); ℎ, 𝑏 lần lượt là

hằng số chiều cao và số nhánh tối đa tại mỗi nút trong.

(2) Tạo câu truy vấn SPARQL mất chi phí 𝑂(1); Tìm kiếm trên ontology mất chi

phí 𝑂(𝑙), 𝑙 là số phân lớp bộ ảnh thực nghiệm. Vì vậy, độ phức tạp của Thuật toán 2.5 là 𝑂(1).

Hệ tìm kiếm ảnh SB-iKDT minh họa như Hình 2.14 và thực hiện tìm kiếm trên

ontology để trích xuất tập ảnh tương tự minh họa như Hình 2.15 [CT3].

Hình 2.14. Hệ tìm kiếm ảnh SB-iKDT

Hình 2.15. Kết quả tập ảnh tương tự với ảnh 52011.jpg (Wang) hệ SB-iKDT

Kết quả tìm kiếm ảnh của hệ SB-iKDT được trình bày trong Bảng 2.7 [CT3].

Bảng 2.7. Kết quả tìm kiếm ảnh của hệ SB-iKDT

Recall Query time (ms)

Tập ảnh Wang Caltech-101 Caltech-256 Precision 0.8010 0.7769 0.7228 0.7404 0.6915 0.5828 F-measure 0.7695 0.7317 0.6453 101.36 109.84 134.91

Để minh chứng tính hiệu quả cho mô hình tìm kiếm ảnh theo ngữ nghĩa đề xuất

là hiệu quả, kết quả thực nghiệm được so sánh với một số công trình gần đây trên

cùng bộ dữ liệu trong các Bảng 2.8 - 2.10. Kết quả so sánh này cho thấy, việc kết hợp

cấu trúc KD-Tree với các kỹ thuật học máy nhằm tăng kết quả phân lớp ảnh và ứng dụng cho bài toán tìm kiếm ảnh theo ngữ nghĩa là hoàn toàn khả thi và hiệu quả.

Bảng 2.8. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-iKDT)

Phương pháp

ORB and SIFT features, (P. Chhabra), 2020 [17] SBIR-CT, (Nhi N.T.U et al.), 2021 [50] SVM, (Das et al.), 2017 [18] 8D-GLCM+GSF+ HSVCM, (Bella & Vasuki), 2019 [63]

MAP 0.6320 0.6072 0.5590 0.5970 DSFH (low feature + deep feature VGG-16), (Liu G. H., , et al.), 2021 [42] 0.7894 0.7800 Fusion feature ResNet-34 + PCA + CNN, (Kanwal K., et al.), 2020 [35] 0.8010 SB-iKDT

Bảng 2.9. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-iKDT)

Phương pháp SVM, (M. Bennet Rajesh et al.), 2020 [58] MTSD, (S. Sathiamoorthy, et al.), 2020 [65] DPOF, (Ahmed, K. T., et al.), 2021 [2] CBIR, (Soumya Prakash Rana, et al.), 2019 [60] CBIR, (Khawaja Tehseen Ahmed), 2019 [3] (TopK = 20)

MAP 0.6314 0.6942 0.6200 0.6450 0.6980 0.7769 SB-iKDT

Bảng 2.10. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-256 (SB-iKDT)

Phương pháp

Visual Words FVFF, (Mehmood, Z., et al.), [45]

SVM, (Uzma Sharif, et al.), 2019 [66]

Ensembles of deep learning (Safa Hamreras), (50 classes), 2020 [29]

CBIR, (Khawaja Tehseen Ahmed), 2019 [3] (TopK = 20) CBIR on n Significant Regions with Global CNN, (Jie Xu et al.), 2019 [78] SB-iKDT MAP 0.4630 0.4752 0.5726 0.7130 0.6490 0.7228

Kết quả thực nghiệm cho thấy, hệ tìm kiếm ảnh SB-iKDT với độ chính xác tìm

kiếm cao hơn nhiều công trình cùng bộ dữ liệu là bởi các lý do: (1) Hệ tìm kiếm ảnh

SB-iKDT thực hiện phân lớp ảnh trước khi tìm kiếm; (2) quá trình phân lớp trên cấu

trúc iKD_Tree thực hiện nhiều lần cho từng đối tượng, tại mỗi tầng được phân lớp

một lần nên kết quả phân lớp cao; (3) kết hợp một cấu trúc dữ liệu lưu trữ và ontology

nên bài toán đã tăng thêm bộ lọc phân lớp cho một đối tượng đầu vào.

2.4. Cấu trúc KD-Tree lồng nhau

2.4.1. Mô tả cấu trúc KD-Tree lồng nhau

Trong một số trường hợp nút lá chứa số lượng véc-tơ đặc trưng hình ảnh khá lớn và thuộc nhiều lớp khác nhau, từ đó dẫn đến kết quả phân lớp tại nút lá này chưa cao. Vì vậy, thay vì phải thêm chi phí huấn luyện iKD_Tree để tăng kết quả phân lớp thì tách nút lá này thành một cấu trúc KD-Tree để hình thành cấu trúc KD-Tree lồng nhau. Khi tạo cây con SubTree tại nút lá cùng tính chất cây KD-Tree đã xây dựng về chiều cao, số nhánh nên cấu trúc KD-Tree lồng nhau vẫn giữ được đa nhánh và cân bằng trên từng cây con riêng biệt.

Hình 2.16. Minh họa cấu trúc KD-Tree lồng nhau [CT4]

Cấu trúc KD-Tree lồng nhau được xác định gồm:

1) Một cấu trúc iKD_Tree được xây dựng với chiều cao ℎ, mỗi 𝑁𝑜𝑑𝑒 có số nhánh

𝑏 từ tập dữ liệu ban đầu gồm nút gốc (𝑅𝑜𝑜𝑡), tập trong {𝑁𝑜𝑑𝑒}, tập nút lá {𝑙𝑒𝑎𝑓}.

2) Một số nút lá 𝐿𝑒𝑎𝑓𝑘 có số phần tử và số lớp thỏa điều kiện xác định trong

Bảng 2.11 thì phát triển thành một cây con SubTree cùng tính chất iKD_Tree.

Quá trình xây dựng cấu trúc KD-Tree lồng nhau gồm hai giai đoạn:

Giai đoạn 1: Xây dựng cấu trúc iKD_Tree từ tập dữ liệu ban đầu.

Giai đoạn 2: Một số nút lá 𝐿𝑒𝑎𝑓𝑘 được phát triển thành một cây con SubTree. Sự 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. Điều kiện để phát triển 𝐿𝑒𝑎𝑓𝑘 thành SubTree trong thực nghiệm được trình bày như Bảng 2.11 [CT4]. Cơ sở để xác định điều kiện cho các nút lá phát triển thành SubTree là

căn cứ vào số lượng ảnh của từng phân lớp thuộc bộ ảnh thực nghiệm đã được mô tả

trong Bảng 1.3. Vì vậy, các giá trị thực nghiệm trên từng bộ ảnh để phát triển nút lá

thành SubTree được trình bày trong Bảng 2.11.

Bảng 2.11. Điều kiện để nút lá phát triển thành SubTree

Số phần tử tại nút lá (M) Số phân lớp tại nút lá (N) Bộ ảnh

COREL M > 200 N > 2

Wang M > 250 N > 2

Calttech101 M > 400 N > 2

2.4.2. Xây dựng 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 bước: (1) xây dựng

iKD_Tree từ tập dữ liệu ban đầu; (2) phát triển một số nút lá thành SubTree. Để phát triển nút lá 𝐿𝑒𝑎𝑓𝑘 thành SubTree cần đếm số lượng phần tử tại nút lá hàm Count {𝑓𝑗 𝑖𝑛 𝐿𝑒𝑎𝑓𝑘} và đếm số nhãn lớp hàm Count {𝑙𝑎𝑏𝑒𝑙 𝑖𝑛 𝐿𝑒𝑎𝑓𝑘} được lưu trữ tại nút lá này. Quá trình xây dựng KD-Tree lồng nhau trình bày ở Thuật toán 2.6.

Thuật toán 2.6. Xây dựng cấu trúc KD-Tree lồng nhau 1. Input: Tập F = {𝑓𝑖:𝑓𝑖 = (𝑥𝑖0, 𝑥𝑖1, …,𝑥𝑖𝑛); i = 1, ..., k}; chiều cao ℎ, số nhánh tối đa 𝑏. Bộ trọng số khởi tạo 𝑊𝑘𝑡 = {𝑊𝑖: 𝑊𝑖= (𝑥𝑖0, 𝑥𝑖1, …,𝑥𝑖𝑛); i = 0 … h-1};

2. Output: KD-Tree lồng nhau 3. Function CNKDT (F, 𝑊𝑘𝑡, ℎ, 𝑏) 4. Begin 5. 6. 7. 8. 9. Khởi tạo KD-Tree lồng nhau là rỗng; Tạo iKD_Tree với bộ véc-tơ 𝐹, trọng số 𝑊𝑘𝑡, chiều cao ℎ, số nhánh 𝑏; // Xây dựng SubTree tại 𝐿𝑒𝑎𝑓𝑘 thoả điều kiện Khởi tạo ngưỡng các M, N theo Bảng 2.11; For (𝐿𝑒𝑎𝑓𝑘 thuộc 𝑖𝐾𝐷_𝑇𝑟𝑒𝑒) do

𝑚 = Count {𝑓𝑗 𝑖𝑛 𝐿𝑒𝑎𝑓𝑘}; 𝑛 = Count {𝑙𝑎𝑏𝑒𝑙 𝑖𝑛 𝐿𝑒𝑎𝑓𝑘}; If (𝑚 ≥ M and 𝑛 ≥ 𝑁) then tạo SubTree tại 𝐿𝑒𝑎𝑓𝑘; EndFor;

10. 11. 12. 13. 14. KD-Tree lồng nhau = iKD_Tree ∪ SubTree tại 𝐿𝑒𝑎𝑓𝑘; 15. Return KD-Tree lồng nhau; 16. End.

Thuật toán 2.6 thực hiện:

Bước 6 xây dựng iKD_Tree với bộ véc-tơ 𝐹 mất chi phí là 𝑂(𝑛).

Vòng lặp từ bước [83] – (13) duyệt qua số nút lá là 𝑏ℎ thỏa điều kiện số phần tử

tại 𝑙𝑒𝑎𝑓𝑘 lớn hơn M thì xây dựng KD-Tree tại 𝑙𝑒𝑎𝑓𝑘 mất chi phí là 𝑂(1). Vậy độ phức tạp của Thuật toán 2.6 là 𝑂(𝑛);

Đóng góp của thuật toán 2.6 là phát hiện một số nút lá tập trung khá nhiều dữ liệu.

Thay vì phải mất chi phí huấn luyện tại các nút lá này thì phát triển thành SubTree sẽ

tốn ít chi phí thời gian hơn, đồng thời hiệu quả gom cụm tại nút lá mịn hơn. Từ đó,

độ chính xác tìm kiếm ảnh tốt hơn so với iKD_Tree.

2.4.3. Hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree lồng nhau

Hình 2.17. Mô hình tìm kiếm ảnh dựa trên KD-Tree lồng nhau (SB-NKDT) [CT4]

Mô hình hệ tìm kiếm ảnh dựa trên cấu trúc KD-Tree lồng nhau bao gồm pha tiền

xử lý và pha tìm kiếm: Trong đó, cấu trúc KD-Tree lồng nhau và pha tìm kiếm ảnh

là phần đề xuất; phần ontology là kế thừa từ công trình [51] sau khi bổ sung dữ liệu

thực nghiệm bộ ảnh Caltech-101, Caltech-256. Trong mô hình này, thuật toán 2.6 để xây dựng KD-Tree lồng nhau, thuật toán 2.7 tìm kiếm tập ảnh tương tự.

Bước 1. Trích xuất véc-tơ đặc trưng gồm 225 chiều của tập dữ liệu ảnh (1).

Bước 2. Xây dựng cấu trúc KD-Tree lồng nhau (2).

Bước 3. Bổ sung vào ontology dữ liệu thực nghiệm và ảnh từ WWW (3), (4).

Bước 4. Trích xuất véc-tơ đặc trưng ảnh cần truy vấn (5); thực hiện tìm kiếm tập

ảnh tương tự theo nội dung dựa trên cấu trúc KD-Tree lồng nhau (6).

Bước 5. Trích xuất tập ảnh tương tự theo nội dung và tập từ thị giác (7); đồng

thời tạo câu truy vấn SPARQL (8) dựa trên tập từ thị giác.

Bước 6. Tìm kiếm trên ontology tập ảnh tương tự theo ngữ nghĩa bằng câu truy

vấn SPARQL (9).

Bước 7. Trích xuất tập ảnh tương tự với ảnh đầu vào (10).

Cấu trúc KD-Tree lồng nhau và ontology đã xây dựng ở pha tiền xử lý. Quá trình

tìm kiếm tập ảnh tương tự với ảnh đầu vào được thực hiện bởi Thuật toán 2.7.

Thuật toán 2.7. Tìm kiếm ảnh tương tự trên hệ SB-NKDT

1. Input: Ảnh truy vấn 𝐼; KD-Tree lồng nhau, ontology; 2. Output: Tập ảnh tương tự 𝑆𝐼; 3. Function SNKDT (Ả𝑛ℎ 𝐼, 𝑂𝑛𝑡𝑜𝑙𝑜𝑔𝑦, 𝑁𝑒𝑠𝑡𝑒𝑑 𝐾𝐷 − 𝑇𝑟𝑒𝑒) 4. Begin 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. End.

Ban đầu gán tập ảnh tương tự 𝑆𝐼 là rỗng; Trích xuất véc-tơ 𝑓𝑖 ảnh truy vấn 𝐼; // Tìm trên KD-Tree lồng nhau tập ảnh tương tự 𝑆𝐶 với ảnh 𝐼; 𝑆𝐶 = 𝑺𝑲𝑫𝑻(𝑓𝑖, 𝐾𝐷 − 𝑇𝑟𝑒𝑒 𝑙ồ𝑛𝑔 𝑛ℎ𝑎𝑢); Trích xuất tập từ thị giác 𝑉𝑊 từ tập ảnh 𝑆𝐶 theo tần xuất nhãn lớn nhất; // Tạo câu truy vấn SPARQL từ tập từ thị giác; SPARQL = CreateSPARQL(𝑉𝑊); Tìm kiếm trên Ontology bằng câu truy vấn SPARQL; Trích xuất tập ảnh tương tự 𝑆𝐼 của ảnh truy vấn 𝐼; Return 𝑆𝐼;

Thuật toán 2.7. thực hiện các bước: (1) Tìm kiếm trên KD-Tree lồng nhau trích xuất tập ảnh tương tự tại nút lá mất

chi phí là 𝑂(1);

(2) Trích xuất tập từ thị giác mất chi phí 𝑂(1); (3) Tạo câu truy vấn SPARQL mất chi phí 𝑂(1); (4) Tìm kiếm trên ontology mất chi phí 𝑂(𝑙) = 𝑂(1), 𝑙 là số phân lớp bộ ảnh thực

nghiệm; Vì vậy, độ phức tạp của Thuật toán 2.7 là 𝑂(1).

Hình 2.18. Hệ tìm kiếm ảnh SB-NKDT

Hình 2.19. Tập ảnh tương tự với ảnh 500.jpg [19] hệ SB-NKDT

Hệ tìm kiếm ảnh SB-NKDT thực nghiệm trên các bộ ảnh COREL, Wang,

Caltech-101. Hình 2.18, mô tả thực nghiệm tìm kiếm ảnh tương tự với ảnh 500.jpg

[19]. Kết quả tập ảnh tương tự theo ngữ nghĩa của ảnh đầu vào như Hình 2.19.

Kết quả thực nghiệm hệ tìm kiếm SB-NKDT được trình bày trong Bảng 2.12 [CT4]. Mỗi bộ ảnh khác nhau có số phân lớp nên chiều cao và số nhánh là khác nhau. Kết quả thực nghiệm bộ COREL chiều cao cây bằng 2, số nhánh bằng 4 nên thời gian

tìm kiếm nhanh hơn so với bộ dữ liệu Wang và Caltech-101.

Bảng 2.12. Kết quả tìm kiếm ảnh của hệ SB-NKDT

Bộ ảnh Precision Recall F-measure Query time (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

Kết quả hệ tìm kiếm ảnh SB-NKDT là cao, bởi các lý do sau: (1) quá trình

huấn luyện trọng số trên KD-Tree lồng nhau tốn chi phí nhưng được kết quả phân lớp

cao; (2) kết quả phân lớp làm cơ sở tìm kiếm tập ảnh tương tự theo nội dung nên được

lọc qua một lần; (3) thực hiện tìm kiếm tập ảnh tương tự trên ontology.

Bảng 2.13. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh COREL (SB-NKDT)

Phương pháp B_SHIFT, (Douik, Ali. et al.), 2016 [23] Shape and Texture Features, (Abdulkadhem, et al.), 2019 [1] ORB 8-dimensions with MPL, (P. Chhabra et al.), 2020 [17] C-Tree, (Nhi, N. T. U. et al. ), 2021 [50] Multi-feature and SVM, (Gonçalves F. M. F., et al.), 2018 [27] Multi-feature with neural network, (Raja R., et al.), 2020 [57]

SB-NKDT MAP 0.7200 0.7286 0.6656 0.6777 0.7657 0.7941 0.8120

Bảng 2.14. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Wang (SB-NKDT)

MAP 0.6320 0.6072 0.5590 0.5970 0.7894 0.7800 Phương pháp ORB and SIFT features, (P. Chhabra et al.), 2020 [17] SBIR-CT, (Nhi N.T.U et al.), 2021 [50] SVM, (Das, R., et al.), 2017, [18] 8D-GLCM+GSF+ HSVCM, (Bella et al.), 2019 [9] DSFH (low feature + deep feature VGG-16), (Liu G. H., , et al.), 2021 [42] Fusion feature ResNet-34 + PCA + CNN, (Kanwal K., et al.), 2020 [35]

C-Tree, (Nhi, N. T. U. et al. ), 2021 [50] Combined feature HSV+LBP+Canny + SOM, (Pavithra L. K., et al.), 2019 [53]

0.6072 0.7894 0.8029 SB-NKDT

Bảng 2.15. So sánh độ chính xác tìm kiếm ảnh trên bộ ảnh Caltech-101 (SB-NKDT)

Phương pháp

CE and Valleys with SVM, (Rajesh, M. B., et al.), 2020 [58] CBIR Multi-trend Structure, (Sathiamoorthy, S., et al.), 2020 [65] Feature Detector, (Ahmed, K. T., et al.), 2021 [2] CBIR with features, (Soumya Prakash Rana, et al.), 2019 [60] CBIR, TopK = 10, (Khawaja Tehseen Ahmed), 2019 [3] CBIR on n Significant Regions with Global CNN, (Jie Xu et al.), 2019 [78]

MAP 0.6314 0.6942 0.6200 0.6450 0.6980 0.7910 0.7889 SB-NKDT

Kết quả thực nghiệm được so sánh với một số công trình gần đây cùng bộ dữ

liệu trong Bảng 2.3 – 2.6 (hệ SB-KDT); 2.8 – 2.10 (hệ SB-iKDT); 2.13 – 2.15 (hệ

SB-NKDT). Kết quả so sánh cho thấy, việc ứng dụng cấu trúc KD-Tree cho bài toán

tìm kiếm ảnh là hoàn toàn khả thi và hiệu quả. Các cải tiến sau dựa trên những hạn

chế của đề xuất trước là có cơ sở, vì vậy các kết quả về độ chính xác về sau thì cao

hơn các kết quả trước đó. Các kết quả so sánh độ chính xác tìm kiếm cho thấy số công

trình được so sánh tăng lên đối với hệ SB-NKDT chứng tỏ những cải tiến này là khả

thi và đúng đắn.

Theo kết quả thực nghiệm, kết quả tìm kiếm ảnh trên các bộ dữ COREL, Wang,

Caltech-101, Caltech-256 cao hơn các công trình khác bởi các lý do: (1) Bài toán thực

hiện phân lớp ảnh trước khi thực hiện tìm kiếm ảnh tương tự; (2) Phân lớp ảnh theo

cấu trúc KD-Tree lồng nhau và huấn luyện trọng số nên độ chính xác phân lớp cao; (3) Sự kết hợp giữa cấu trúc KD-Tree lồng nhau và ontology nhằm nâng cao độ chính

xác tìm kiếm ảnh. Tuy nhiên, kết quả thời gian tìm kiếm trung bình của hệ SB-KDT,

SB-iKDT, SB-NKDT được trình bày nhưng không được so sánh với các công trình khác vì cấu hình máy tính không đồng nhất. Giá trị này được đưa vào để minh chứng tính khả thi của hệ thống tìm kiếm ảnh trên cấu hình máy tính cụ thể, kết quả thời

gian tìm kiếm trung bình trên từng thực nghiệm cũng cho thấy thời gian thực thi của thuật toán được đề xuất là không quá lớn. Đây không phải là giá trị chính, mà mục tiêu của luận án là đánh giá về độ chính xác tìm kiếm ảnh tương tự. Do đó, các kết luận về tính hiệu quả của cấu trúc, mô hình đều được đánh giá tập trung dựa trên độ chính xác của tập ảnh tương tự.

Đồ thị biểu diễn precision, recall và đường cong ROC được thực hiện trên từng

bộ dữ liệu ứng với các hệ tìm kiếm ảnh SB-KDT, SB-iKDT và SB-NKDT được trình

bày trong các Hình 2.20 – 2.23; điều này cho thấy độ chính xác của hệ tìm kiếm ảnh

đề xuất sau dựa trên các yếu điểm trước đó là đúng đắn, khả thi. Các đường cong trên đồ thị tạo ra một khoảng cách chênh lệch về độ chính xác trên các hệ tìm kiếm ảnh đề xuất là rõ ràng và cụ thể, đặc biệt là với hệ SB-NKDT có kết quả độ chính xác cao

hơn hai hệ tìm kiếm ảnh SB-KDT và SB-iKDT.

Hình 2.20. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh COREL của hệ tìm kiếm ảnh SB-KDT và SB-NKDT

Hình 2.21. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Wang của hệ tìm kiếm ảnh SB-KDT, SB-iKDT và SB-NKDT

Hình 2.22. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Caltech-

101 của hệ tìm kiếm ảnh SB-KDT, SB-iKDTvà SB-NKDT

Hình 2.23. Biểu đồ so sánh precision-recall, đường cong ROC bộ ảnh Caltech-

256 của hệ tìm kiếm ảnh SB-KDT và SB-iKDT

Để minh họa kết quả tìm kiếm ảnh chi tiết cho tập ảnh thực nghiệm, đồ thị ROC

và thời gian tìm kiếm minh họa chi tiết cho các bộ ảnh từ hình PL1 – PL21 (phần

phụ lục). Mỗi đường cong trên đồ thị mô tả kết quả tìm kiếm với độ chính xác

(precision) và độ phủ (recall) một chủ đề ảnh. Đường cong tương ứng trong đồ thị

ROC cho biết tỷ lệ kết quả tìm kiếm đúng và sai, nghĩa là diện tích dưới đường cong

này đánh giá tính đúng đắn của kết quả tìm kiếm ảnh tương tự.

2.5. Đánh giá các hệ tìm kiếm ảnh

Bảng 2.16 – 2.17 so sánh độ chính xác và thời gian tìm kiếm trung bình trên hai

bộ ảnh Wang, Caltech-101 được trình bày tương ứng với hai cấu trúc iKD_Tree và

KD-Tree lồng nhau. Điều này cho thấy định hướng cải tiến của trên cấu trúc KD-Tree

đúng đắn theo hướng nâng cao độ chính xác tìm kiếm ảnh trên cấu trúc KD-Tree lồng

nhau thì thời gian tìm kiếm tăng lên do chiều cao KD-Tree lồng nhau gấp đôi tại một

số nút lá nên thời gian tìm kiếm trung bình tăng.

Bảng 2.16. So sánh độ chính xác trung bình giữa các cải tiến cấu trúc KD-Tree

Hệ tìm kiếm ảnh COREL Wang Caltech-101 Caltech-256

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 (ms) giữa các cải tiến KD-Tree

Hệ tìm kiếm ảnh COREL Caltech-101 Caltech-256 Wang

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 -

So sánh độ chính xác trung bình từ các hệ tìm kiếm ảnh đề xuất dựa trên các cải

tiến KD-Tree cho thấy độ chính xác cao nhất từ hệ SB-NKDT dựa trên cấu trúc KD-

Tree lồng nhau trên cùng bộ ảnh thực nghiệm COREL, Wang, Caltech-101. Đồng

thời, thời gian tìm kiếm trung bình cao hơn so với các hệ SB-KDT và SB-iKDT do

cấu trúc KD-Tree lồng nhau phát triển nút lá thành SubTree nên chiều cao của KD-

Tree lồng nhau tại một số vị trí có chiều cao gấp đôi so với cấu trúc iKD_Tree. Trong

trường hợp đặt mục tiêu nâng cao độ chính xác tìm kiếm ảnh thì sử dụng hệ SB-

NKDT; trường hợp đặt mục tiêu tìm kiếm nhanh thì sử dụng hệ SB-iKDT.

So sánh độ chính xác tìm kiếm ảnh giữa hai cấu trúc KD-Tree và C-Tree [26]

trên cùng bộ ảnh COREL, Wang cho thấy: (1) độ chính xác hệ tìm kiếm ảnh dựa trên

KD-Tree là cao hơn thực nghiệm trên C-Tree; (2) chi phí huấn luyện KD-Tree cao

hơn so với C-Tree; (3) thời gian tìm kiếm trên KD-Tree cao hơn C-Tree do quá trình

tìm luôn thực hiện từ gốc đến lá với chiều cao KD-Tree, tuy nhiên độ phức tạp của

thuật toán không tăng, vẫn là 𝑂(𝑛).

Bảng 2.18 trình bày một số nội dung được so sánh giữa các công trình đã công

bố. Trong đó, một số công trình đã thực hiện tìm kiếm ảnh thực nghiệm trên cùng bộ

ảnh COREL, Wang, Caltech-101, Caltech-256 có sự tương đồng với các phương pháp

đề xuất trong luận án là: (1) cùng sử dụng các nhóm đặc trưng hình ảnh được trích

xuất như màu sắc, hình dạng, kết cấu, đặc trưng SIFT; (2) sử dụng các thuật toán K-

Means, k-NN để thực hiện gom cụm và phân lớp dữ liệu. Tuy nhiên, các công trình

này chỉ thực hiện trên một bộ ảnh riêng biệt, việc thực nghiệm trên nhiều bộ ảnh với

mỗi đề xuất còn hạn chế, điều này cũng chưa phản ánh được tính tổng quan cho

phương pháp đề xuất trước đây và chưa phân tích những hạn chế còn tồn tại để có

những cải tiến tiếp theo. Bên cạnh đó, độ chính xác tìm kiếm ảnh còn phụ thuộc vào

nhóm đặc trưng được trích xuất, trong khi đó các công trình được so sánh thì các

nhóm đặc trưng kết hợp chưa nhiều như các hệ SB-KDT, SB-iNKDT, SB-NKDT đã

kết hợp đa đặc trưng như HOG, màu sắc, hình dạng, kết cấu, v.v. Độ chính xác tìm

kiếm ảnh trên các bộ ảnh thực nghiệm của những phương pháp đề xuất trong luận án

cao hơn các công trình khảo sát là ảnh hưởng của sự kết hợp cấu trúc dữ liệu lưu trữ,

đa đặc trưng và ontology. Một kết quả tìm kiếm đã thực hiện qua nhiều bộ lọc gom

cụm và phân lớp nên kết quả thu được cao hơn. Điều này cho thấy các phương pháp

kết hợp giữa cấu trúc lưu trữ với kỹ thuật học máy và ontology đã góp phần nâng cao

hiệu quả tìm kiếm ảnh trong chương này.

Bảng 2.18. So sánh các phương pháp tìm kiếm ảnh sử dụng KD-Tree với những đề xuất trong luận án

Bộ ảnh Cấu trúc lưu trữ Đặc trưng Kết hợp Ontology

Phương pháp (Công trình) k-NN KD-Tree [1] COREL k-NN - KD-Tree nhị phân cân bằng Đặc trưng Texture, Shape

ORB and SIFT features [17] Wang ORB and SIFT K-Means Giảm chiều dữ liệu Giảm chiều đặc trưng bằng SVD - - Decision tree, Random Forest và MLP classifiers

Caltech-101 - Đặc trưng Texture, Shape HSV Color - - - Fused Information Feature- based Image Retrieval System [9]

Caltech-256 KD-Tree đa nhánh - k-NN Distributed KD-Tree [43] cân bằng Đặc trưng SIFT, HOG

Giảm chiều đặc trưng bằng PCA 81 chiều ontology KD-Tree SB-KDT [CT2] KD-Tree đa nhánh cân bằng - Đặc trưng Texture, Shape; SIFT và HOG;

183 chiều ontology

iKD_Tree SB-iKDT [CT3] kNN K-Means COREL, Wang, Caltec-101, Caltech-256 Wang, Caltec-101, Caltech-256 KD-Tree đa nhánh cân bằng thêm hệ số alpha Đặc trưng MPEG-7, SIFT, SITOMASHI, HOG, Sobel HOG, Laplace HOG

KD-Tree lồng nhau Đặc trưng Texture, 81 chiều ontology KD-Tree lồng nhau SB-NKDT [CT4] kNN K-Means COREL, Wang, Caltec-101 Shape; SIFT và HOG;

Khi thực hiện tìm kiếm ảnh dựa trên KD-Tree thực chất là tìm kiếm ảnh dựa

trên các phân cụm. Bởi vì quá trình xây dựng cấu trúc KD-Tree để lưu trữ véc-tơ đặc

trưng hình ảnh là quá trình gom cụm tại các nút lá. Tuy nhiên, để hình thành các cụm

này thì quá trình phân lớp trên KD-Tree theo mô hình nhiều tầng bắt đầu từ nút gốc

được thực hiện và huấn luyện trọng số tại mỗi tầng trên KD-Tree. Cấu trúc KD-Tree

được xây dựng là cấu trúc đa tầng, mỗi nút trên KD-Tree là mạng Nơ-ron một nút.

Vì vậy, cần mất một chi phí huấn luyện trọng số trên KD-Tree ở pha huấn luyện một

lần và sử dụng nhiều lần ở pha tìm kiếm ảnh. Do đó, kết quả tìm kiếm ảnh dựa trên

KD-Tree và KD-Tree lồng nhau có độ chính xác cao hơn các phương pháp gom cụm

thuần túy như K-Means, DBSCAN, v.v.

Kết quả về tìm kiếm ảnh dựa trên cấu trúc KD-Tree (hệ SB-KDT), iKD_Tree

(hệ SB-iKDT), KD-Tree lồng nhau (hệ SB-NKDT) được tác giả lần lượt trình bày

trong các bài báo [CT2], [CT3] và [CT4] trong danh mục các công trình liên quan

đến luận án của tác giả.

2.6. Tổng kết chương

Các cải tiến cấu trúc KD-Tree được đánh giá là hiệu quả cho bài toán tìm kiếm

ảnh. Cấu trúc KD-Tree được xây dựng theo phương pháp học bán giám sát để hình

thành mỗi nút lá là một cụm đồng thời là một phân lớp. 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 theo

ngữ nghĩa như SB-KDT, SB-iKDT và SB-NKDT dựa trên ontology, nhưng chỉ dừng

lại ở việc tìm kiếm những hình ảnh có phân lớp thuộc ontology và chỉ thực nghiệm

trên các bộ ảnh đơn đối tượng. Trong khi đó, mối quan hệ ngữ nghĩa theo vị trí được

xác định giữa các đối tượng trên mỗi hình ảnh có thể bổ sung được vào ontology

nhằm thực hiện tìm kiếm những ảnh thỏa điều kiện này. Vì vậy, cấu trúc KD-Tree có

khả năng phát triển theo tiếp cận ngữ nghĩa để xây dựng ontology cho bộ ảnh đa đối

tượng cũng cần được thực hiện trong chương tiếp theo.

CHƯƠNG 3. PHÁT TRIỂN CẤU TRÚC KD-TREE THEO

TIẾP CẬN NGỮ NGHĨA

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 với ảnh phân đoạn và mối quan hệ giữa các đố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 nhằm

phân lớp mối quan hệ giữa các đối tượng làm cơ sở phát triển một Ontology, gọi là

Re KD-Tree. Ontology được phát triển 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. Đồng thời, để nâng cao độ chính xác

tìm kiếm ảnh trên cấu trúc RF KD-Tree cũng được xây dựng bằng cách tổng hợp và

huấn luyện nhiều KD-Tree độc lập. Thực nghiệm trên các hệ tìm kiếm ảnh SR-KDT,

SR-KDF, SO-KDT đã cho thấy tính đúng đắn và hiệu quả cho cơ sở lý thuyết đề

xuất.

3.1. Giới thiệu

Bài toán tìm kiếm ảnh đa đối tượng phức tạp hơn đối với tập ảnh đơn đối tượng

bởi vì các thao tác tiền xử lý như xác định số đối tượng trên ảnh, phân đoạn ảnh đối

tượng, xác định mối quan hệ giữa các đối tượng theo vị trí, mô tả đối tượng, v.v. Mục

tiêu chương này là cải tiến những hạn chế đề xuất từ Chương 2 nhằm nâng cao độ

chính xác tìm kiếm ảnh bằng cách xây dựng nhiều cấu trúc KD-Tree độc lập tạo thành

rừng ngẫu nhiên gọi là RF KD-Tree trên bộ ảnh đa đối tượng. Đồng thời, mối quan

hệ của các đối tượng trong ảnh cần được xác định bằng cấu trúc Re KD-Tree; phát

triển Ontology từ ảnh đối tượng và các mối quan hệ để tìm kiếm tập ảnh tương tự

theo ngữ nghĩa dựa trên bộ ba mô tả ảnh đầu vào.

Tìm kiếm ảnh theo tiếp cận ngữ nghĩa dựa trên mối quan hệ giữa các đối tượng

được xác định bằng SG hoặc KG và công bố bởi một số công trình [80], [62]. Luận

án phát triển cấu trúc Re KD-Tree theo tiếp cận ngữ nghĩa để phân lớp mối quan hệ

giữa các đối tượng hình ảnh được đề xuất với kết quả khả quan, có thể so sánh với

các phương pháp khác trên cùng bộ dữ liệu thực nghiệm.

Dựa trên cơ sở lý thuyết đề xuất, một số mô hình tìm kiếm ảnh theo tiếp cận

ngữ nghĩa bằng cách kết hợp RF KD-Tree, Re KD-Tree và Ontology được thực hiện

trong chương này.

3.1.1. Xây dựng cấu trúc RF KD-Tree

Hiện nay, việc xây dựng và phân lớp hình ảnh bằng rừng ngẫu nhiên dựa trên

các kỹ thuật Bagging, Boosting, v.v. và một số kỹ thuật khác đã mang lại kết quả

phân lớp ảnh cao [80], [74]. Rừng ngẫu nhiên được ứng dụng khá nhiều vào các công

trình phân lớp hình ảnh [72] bởi kết quả phân lớp đối tượng cao hơn một số kỹ thuật

học máy đơn lẻ như k-NN [74], máy véc-tơ hỗ trợ SVM [75] v.v. Chi phí cho thời

gian xây dựng và huấn luyện mô hình rừng ngẫu nhiên được thực hiện một lần ở pha

tiền xử lý; kết quả sau huấn luyện trọng số được sử dụng nhiều lần ở pha tìm kiếm

ảnh. Sau khi xây dựng và huấn luyện rừng ngẫu nhiên, kết quả thu được là RF KD-

Tree dựa trên nhiều cấu trúc KD-Tree; từ đó cấu trúc KD-Tree tổng hợp bởi RF KD-

Tree áp dụng cho bài toán tìm kiếm ảnh được đánh giá là hiệu quả về độ chính xác

tìm kiếm ảnh. Minh họa rừng ngẫu nhiên RF KD-Tree kết hợp kỹ thuật Bagging được

minh họa trong Hình 3.1 [CT6], 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 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.

Hình 3.1. Mô tả cấu trúc RF KD-Tree

Quá trình xây dựng cấu trúc RF KD-Tree theo Thuật toán 3.1.

Thuật toán 3.1. Xây dựng cấu trúc RF KD-Tree

Khởi tạo 𝑅𝐹 𝐾𝐷 − 𝑇𝑟𝑒𝑒 là rỗng; Tạo tập dữ liệu 𝑆𝑖 gồm 𝑛𝑖 phần tử lấy ngẫu nhiên từ tập S, (𝑛𝑖 < 𝑛); 𝐅𝐨𝐫𝐞𝐚𝐜𝐡 (𝑖 ∈ 𝑁) 𝐝𝐨

𝐾𝐷 − 𝑇𝑟𝑒𝑒 𝑡ℎứ 𝑖 = 𝐂𝐊𝐃𝐓 (𝑆𝑖, 𝑊𝑘𝑡, ℎ, 𝑏); 𝑅𝐹 𝐾𝐷 − 𝑇𝑟𝑒𝑒 = 𝑅𝐹 𝐾𝐷 − 𝑇𝑟𝑒𝑒 ∪ 𝐾𝐷 − 𝑇𝑟𝑒𝑒 𝑡ℎứ 𝑖;

1. Input: Tập dữ liệu huấn luyện 𝑆 có 𝑛 𝑝ℎầ𝑛 𝑡ử, 𝑁 là số KD-Tree cần xây dựng; 2. Output: 𝑅𝐹 𝐾𝐷_𝑇𝑟𝑒𝑒; 3. Function 𝑪𝑹𝑭 (𝑆, 𝑁) 4. Begin 5. 6. 7. 8. 9. 10. 𝐄𝐧𝐝𝐅𝐨𝐫each; 11. 𝐑𝐞𝐭𝐮𝐫𝐧 𝑅𝐹 𝐾𝐷 − 𝑇𝑟𝑒𝑒; 12. End.

Thuật toán 3.1 xây dựng N cấu trúc KD-Tree. Mỗi cấu trúc KD-Tree mất chi phí xây dựng là 𝑂(𝑛𝑖), với 𝑛𝑖 là số phần tử trích ngẫu nhiên từ tập dữ liệu thực nghiệm gồm 𝑛 phần tử. Vậy độ phức tạp thuật toán 3.1 khi huấn luyện tập dữ liệu 𝑛 phần tử

cho 𝑁 cấu trúc KD-Tree là 𝑂(𝑛).

Đóng góp của thuật toán 3.1 là xây dựng và huấn luyện RF KD-Tree đã sử dụng

bộ trọng số chọn lọc để phát triển thành KD-Tree tổng hợp cho hệ tìm kiếm ảnh SR-

KDF. Thay vì phải mất chi phí huấn luyện nhiều KD-Tree tuần tự thì chi phí thời gian

xây dựng và huấn luyện RF KD-Tree song song là thấp hơn.

3.1.2. Huấn luyện RF KD-Tree

Cấu trúc RF KD-Tree được xây dựng trên bộ dữ liệu ngẫu nhiên. Sau đó, bộ dữ liệu này được cố định để thực hiện huấn luyện RF KD-Tree. Việc xây dựng và huấn luyện KD-Tree được thực hiện trên bộ dữ liệu không đổi. Vì vậy, các cấu trúc KD-Tree trong rừng ngẫu nhiên vẫn ổn định. Quá trình huấn luyện mô hình phân lớp ảnh bằng RF KD-Tree chính là 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 của quá trình phân lớp ảnh được trình bày bởi Thuật toán 2.2. Quá trình huấn luyện trọng số trên RF KD-Tree được trình bày bởi hàm TWRF với dữ liệu đầu vào là RF KD − Tree với bộ véc-tơ trọng số chưa huấn luyện; giá trị đầu ra là bộ trọng số của RF KD − Tree đã huấn luyện. Mục đích xây dựng RF KD-Tree là tạo nhiều KD- Tree độc lập dựa trên các tập Sampling Data ngẫu nhiên từ tập dữ liệu ban đầu để đảm bảo tính khách quan. Đồng thời quá trình huấn luyện nhiều cây KD-Tree song song nên giảm chi phí thời gian so với huấn luyện một cây KD-Tree mà vẫn đảm bảo

độ chính xác. Mỗi cây KD-Tree trong RF KD-Tree vẫn giữ được tính cân bằng. Sau khi xây dựng RF KD-Tree và huấn luyện để tìm bộ trọng số tốt nhất để xây dựng KD- Tree tổng hợp cho hệ tìm kiếm ảnh SR-KDF.

1. Function TWRF (𝑅𝐹 𝐾𝐷 − 𝑇𝑟𝑒𝑒 chưa huấn luyện) 2. Begin 3. 4.

Huấn luyện trọng số cho mỗi 𝐾𝐷 − 𝑇𝑟𝑒𝑒; Bộ trọng số 𝑅𝐹 𝐾𝐷 − 𝑇𝑟𝑒𝑒 đã huấn luyện = tập các trọng số đã huấn luyện trên tất cả 𝐾𝐷 − 𝑇𝑟𝑒𝑒;

5. 𝐑𝐞𝐭𝐮𝐫𝐧 Bộ trọng số 𝑅𝐹 𝐾𝐷 − 𝑇𝑟𝑒𝑒 đã huấn luyện; 6. End.

3.2. Ontology cho tìm kiếm ảnh theo tiếp cận ngữ nghĩa

Một phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa bằng cách sử dụng

Ontology được thực hiện trong luận án. Ontology được xây dựng, phát triển dựa trên

tập ảnh đối tượng và mối quan hệ giữa các đối tượng theo phương pháp bán tự động.

Ảnh đa đối tượng ban đầu được phân đoạn thành ảnh đối tượng; trích xuất các thành

phần của ảnh đối tượng và xây dựng mối quan hệ giữa các đối tượng. Từ đó Ontology

được xây dựng và bổ sung thuộc tính ảnh đối tượng và mối quan hệ này. Trong luận

án, ảnh đối tượng được xây dựng từ kỹ thuật dò tìm và phân đoạn đối tượng bằng

mạng R-CNN [11]; mối quan hệ giữa các đối tượng trên ảnh được xác định bằng cấu

trúc Re KD-Tree. Trong phạm vi luận án, mỗi hình ảnh thực nghiệm có số đối tượng

khác nhau, do đó mô hình mạng R-CNN được sử dụng để nhận diện, phân đoạn ảnh

gốc thành các ảnh đối tượng. Quá trình ứng dụng mạng R-CNN được thực hiện trên

cơ sở kế thừa mô hình đã có để từ đó nhận diện, phân đoạn các đối tượng khác nhau

trên mỗi hình ảnh gốc [11].

3.2.1. Cấu trúc Re KD-Tree

Xác định mối quan hệ ngữ nghĩa các đối tượng trên ảnh là bài toán được thực

hiện qua các giai đoạn gồm: phân lớp từng đối tượng trên ảnh; xác định quan hệ các

cặp đối tượng; xây dựng mối quan hệ ngữ nghĩa mô tả hình ảnh. Hiện nay, có nhiều

phương pháp để thực hiện bài toán phân lớp mối quan hệ giữa các đối tượng trên ảnh

như sử dụng mạng học sâu Deep Learning [35], SG [80], KG [62], v.v. và một số

phương pháp khác đã mang lại những kết quả khác nhau. Một phương pháp xác định

mối quan hệ các đối tượng bằng cấu trúc Re KD-Tree được đề xuất nhằm phát triển

những ưu điểm của cấu trúc KD-Tree đã xây dựng. Cấu trúc Re KD-Tree được minh

họa như Hình 3.2 gồm các thành phần như sau:

1) Nút gốc 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à mức nút gốc là ℎ0 (𝑙𝑒𝑣𝑒𝑙 = ℎ0);

2) 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 (𝑙𝑒𝑣𝑒𝑙 = ℎ𝑖);

3) Nút lá có một nút cha (𝑝𝑎𝑟𝑒𝑛𝑡), không có nút con, lưu trữ tập véc-tơ đặc trưng

sau khi đã ghép hai ảnh đối tượng {(𝑓𝑖𝑗, 𝑓𝑖𝑘), … , (𝑓𝑚𝑗, 𝑓𝑚𝑘)}, có một mức trên cây

(𝑙𝑒𝑣𝑒𝑙 = ℎ) và được gán nhãn là một từ chỉ mối quan hệ trong tập ảnh thực nghiệm

(𝑊𝑜𝑟𝑑 𝑜𝑓 𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐 𝑅𝑒𝑙𝑎𝑡𝑖𝑜𝑛𝑠ℎ𝑖𝑝).

Quá trình xây dựng Re KD-Tree được thực hiện như sau:

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à 𝑏; số nút lá tối đa trên KD-Tree được tạo ra là 𝑏ℎ. Số nút lá phụ thuộc vào

tập từ chỉ mối quan hệ trên từng bộ ảnh thực nghiệm.

2) Khởi tạo tập véc-tơ trọng số ngẫu nhiên và phân bổ vào các nút trong.

3) Tại 𝑁𝑜𝑑𝑒𝑖 khởi tạo các ngưỡng trái, ngưỡng phải 𝑁𝑜𝑑𝑒𝑖. 𝑙𝑒𝑓𝑡 = 0.5;

𝑁𝑜𝑑𝑒𝑖. 𝑟𝑖𝑔ℎ𝑡 = 0.5.

4) Lần lượt cho cặp véc-tơ 𝑓𝐼𝑗𝑘 = (𝑓𝑖𝑗, 𝑓𝑖𝑘) đi vào Re KD-Tree từ nút gốc và

xác định đường đi cho (𝑓𝑖𝑗, 𝑓𝑖𝑘) đến tầng kế tiếp.

5) Lặp lại bước (3), (4) đến khi gặp nút lá 𝑙𝑒𝑎𝑓𝑘 thì ghi 𝑓𝐼𝑗𝑘 vào 𝑙𝑒𝑎𝑓𝑘.

Ảnh đối tượng (Object image) là ảnh phân đoạn dựa trên từng đối tượng của

ảnh gốc (Original image). Mỗi ảnh gốc được phân đoạn thành nhiều ảnh đối tượng,

tùy thuộc vào diện tích của đối tượng mà bộ ảnh thực nghiệm MS-COCO, Flickr được

sử dụng số lượng ảnh đối tượng khác nhau để đạt được độ chính xác tốt nhất. Sau khi

phân đoạn ảnh, mỗi vùng ảnh đặc trưng được trích xuất dưới dạng véc-tơ đặc trưng

cho quá trình xây dựng cấu trúc KD-Tree. Ảnh đối tượng của ảnh 1001773457.jpg

(Flickr) được minh họa như trong Hình 3.3 [CT5].

Hình 3.2. Mô tả cấu trúc Re KD-Tree

Hình 3.3. Minh họa ảnh đối tượng trích xuất từ ảnh gốc 1001773457.jpg (Flickr)

Trên cơ sở các thành phần của Re KD-Tree được mô tả, thuật toán xây dựng Re KD-Tree kế thừa thuật toán 2.1 xây dựng KD-Tree đa nhánh cân bằng. Tuy nhiên quá trình gán nhãn nút lá sử dụng hàm SL2L và thay thế tập nhãn (label) bằng tập từ chỉ mối quan hệ giữa các đối tượng trên ảnh được trích xuất từ bộ dữ liệu thực nghiệm gồm: In, On, Under, Above, Left, Right, Front of, Behind, v.v. Quá trình điều chỉnh bộ véc-tơ phân lớp tại các nút trong để nâng cao độ chính xác phân lớp mối quan hệ bằng Re KD-Tree tại nút lá [CT5]. Cấu trúc Re KD-Tree được xây dựng từ một khung cây khởi tạo trước nên về tính cân bằng vẫn giữ nguyên. Cấu trúc Re KD- Tree cũng được huấn luyện trọng số theo phương pháp học bán giám sát kế thừa từ chương 2. Quá trình này được mô tả như sau:

(1) Tính kết quả phân lớp mối quan hệ cho tập ảnh với bộ véc-tơ trọng số khởi tạo.

(2) Tìm những cặp ảnh đối tượng phân lớp sai mối quan hệ.

(3) Tìm vị trí 𝑁𝑜𝑑𝑒𝑖 làm sai quá trình phân lớp mối quan hệ của cặp ảnh đối tượng.

(4) Điều chỉnh véc-tơ trọng số tại 𝑁𝑜𝑑𝑒𝑖 để cặp đối tượng (𝐼𝑖, 𝐼𝑘) đúng nút lá.

(5) So sánh kết quả phân lớp mối quan hệ sau khi đã điều chỉnh véc-tơ trọng số và

kết quả phân lớp khi sử dụng bộ véc-tơ trọng số ngẫu nhiên.

(6) Quá trình này lặp lại cho đến khi đạt được kết quả mục tiêu.

3.2.2. Phân lớp mối quan hệ các đối tượng bằng Re KD-Tree

Mỗi ảnh 𝐼 được phân đoạn thành các ảnh đối tượng (𝐼1, . . , 𝐼𝑘), 𝑘 = 1. .5; 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á. Kết quả thực nghiệm chọn mỗi ảnh gốc có tối đa 5 ảnh đối tượng sau khi thực hiện R-CNN vì đây là kết quả thực nghiệm tốt nhất. Tuy nhiên với những ảnh có số đối tượng nhỏ hơn 5 thì lấy hết các đối tượng này. 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 giữa các đối tượng trên ảnh bằng Re KD-Tree [CT5]. Vì vậy, quá trình phân lớp mối quan hệ giữa các đối tượng được trình bày bởi hàm C𝐋𝐑𝐊𝐃 có dữ liệu đầu vào là véc-tơ 𝑓𝑖𝑚, 𝑓𝑖𝑛 của ảnh đối tượng 𝐼𝑚 , 𝐼𝑛 thuộc ảnh 𝐼; 𝑅𝑒 𝐾𝐷 − 𝑇𝑟𝑒𝑒. Giá trị đầu ra là mối quan hệ giữa hai ảnh đối tượng 𝐼𝑚, 𝐼𝑛;

𝐍ế𝐮 (𝑓𝐼𝑚 ∈ 𝐿𝑒𝑎𝑓𝑘) và (𝑓𝐼𝑛 ∈ 𝐿𝑒𝑎𝑓𝑘) 𝐭𝐡ì Gán từ quan hệ là 𝑆𝑊𝐼 = 𝐿𝑒𝑎𝑓𝑘. 𝑙𝑎𝑏𝑒𝑙; Mối quan hệ = 𝑓𝐼𝑚. 𝑙𝑎𝑏𝑒𝑙 + 𝑆𝑊𝐼 + 𝑓𝐼𝑛. 𝑙𝑎𝑏𝑒𝑙;

1. Function C𝐋𝐑𝐊𝐃 (𝑓𝐼𝑚, 𝑓𝐼𝑛, 𝑓𝐼𝑚.𝑙𝑎𝑏𝑒𝑙, 𝑓𝐼𝑛.𝑙𝑎𝑏𝑒𝑙, 𝑅𝑒 𝐾𝐷 − 𝑇𝑟𝑒𝑒) 2. Begin 3. 𝑓𝐼 = 𝑓𝐼𝑚 ⊕ 𝑓𝐼𝑛; 4. 5. 6. 7. 𝐑𝐞𝐭𝐮𝐫𝐧 𝑀ố𝑖 𝑞𝑢𝑎𝑛 ℎệ; 8. End.

3.2.3. Mô tả cấu trúc và xây dựng Ontology

Trong chương này, Ontology được thiết kế dựa trên ảnh đối tượng và mối quan

hệ giữa các đối tượng trên ảnh; sau đó bổ sung mối quan hệ giữa từng cặp đối tượng

theo bộ ba “Objecti – relationship – Objectj”, kết hợp với cấu trúc Re KD-Tree để xác

định mối quan hệ giữa các đối tượng, chú giải cho mỗi hình ảnh nhằm nâng cao độ

chính xác tìm kiếm ảnh tương tự. Trên cơ sở kế thừa khung Ontology từ các hệ tìm

kiếm ảnh SB-KDT, SB-iKDT và SB-NKDT; quá trình thiết kế các thuộc tính cho ảnh

đối tượng, mối quan hệ giữa các đối tượng được bổ sung vào Ontology để tăng số

lượng hình ảnh tương tự được tìm kiếm trên Ontology, từ đó tăng độ chính xác.

Khi dữ liệu ảnh số gia tăng thì việc tìm kiếm một đối tượng trên tập dữ liệu

Metadata thì chi phí thời gian lớn và khó thực thi. Vì vậy, giải pháp xây dựng

Ontology để đáp ứng cho quá trình tìm kiếm ảnh nhanh, hiệu quả và ứng dụng cho

bài toán tìm kiếm ảnh theo tiếp cận ngữ nghĩa là cấp thiết. Phần này trình bày cấu

trúc, phương pháp xây dựng và tìm kiếm ảnh trên 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 minh họa như Hình 3.4 đượ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. Quá trình xây dựng và bổ sung dữ liệu

vào Ontology được thực hiện theo các bước sau:

Bước 1. Phân đoạn tập ảnh thực nghiệm 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

(Relationship).

Hình 3.4. Minh họa cấu trúc Ontology

Cấu trúc Ontology được xây dựng gồm những thành phần đã mô tả trên ảnh

đối tượng như Hình 3.4, mỗi đối tượng được lưu trữ gồm các thành phần: địa chỉ lưu

trữ (IRI), định danh đối tượng (ObjectId), thuộc tính (Attributes), tên ảnh đối tượng

(Name), định danh ảnh đối tượng (ImageId), chiều rộng (Width), chiều cao (Height),

định danh Wordnet ảnh đối tượng (SynsetId), tọa độ trục hoành (CoorX), tọa độ trục

tung (CoorY), mô tả Wordnet đối tượng (Wordnet), mô tả đối tượng (Description).

Giữa hai ảnh đối tượng có một mối quan hệ (Relationship), mỗi mối quan hệ cần lưu

trữ các thành phần: tên mối quan hệ (Name), ID mối quan hệ (ID), cấu trúc mối quan

hệ (SynsetID) và mô tả mối quan hệ (Description).

Hình 3.5. Cách tổ chức dữ liệu phân cấp lớp và lớp con trong bộ ảnh MS-COCO

Hình 3.6. Cấu trúc Class, SuperClass được bổ sung vào Ontology

Mỗi ảnh đối tượng thuộc một lớp (Class) và phân cấp lớp cha (SuperClass)

được minh họa như Hình 3.5 – 3.6.

Cấu trúc lớp (Class) và lớp cha (SuperClass) trên bộ ảnh thực nghiệm MS-

COCO và Flickr tổ chức theo cấu trúc sau:

Hình 3.7. Cấu trúc ảnh đối tượng sau khi phân đoạn và phân lớp

Hình 3.8. Minh họa cấu trúc ảnh đối tượng theo phân lớp

Hình 3.9. Mô tả các thành phần ảnh đối tượng trên bộ ảnh Flickr

Cấu trúc Ontology được đề xuất và xây dựng áp dụng cho bài toán tìm kiếm ảnh theo tiếp cận ngữ nghĩa trên các bộ ảnh đa đối tượng MS-COCO và Flickr. Hàm CEO mô tả quá trình xây dựng Ontology dựa trên ảnh đối tượng và mối quan hệ giữa các đối tượng, dữ liệu đầu vào là 𝑂𝑛𝑡𝑜𝑙𝑜𝑔𝑦_𝐹𝑟𝑎𝑚𝑒𝑤𝑜𝑟𝑘; giá trị đầu ra là Ontology đã bổ sung dữ liệu 𝐸𝑂;

𝐸𝑂 = 𝑂𝑛𝑡𝑜𝑙𝑜𝑔𝑦_𝐹𝑟𝑎𝑚𝑒𝑤𝑜𝑟𝑘; Bổ sung 𝐶𝑙𝑎𝑠𝑠𝑒𝑠, 𝑆𝑢𝑏𝐶𝑙𝑎𝑠𝑠𝑒𝑠 từ bộ ảnh 𝑀𝑆 𝐶𝑂𝐶𝑂, 𝐹𝐿𝑖𝑐𝑘𝑟 vào 𝐸𝑂; Bổ sung các mối quan hệ vào 𝐸𝑂; Bổ sung các thành phần ảnh đối tượng vào 𝐸𝑂; 𝐑𝐞𝐭𝐮𝐫𝐧 𝐸𝑂;

1. Function 𝑪𝑬𝑶 (𝑂𝑛𝑡𝑜𝑙𝑜𝑔𝑦_𝐹𝑟𝑎𝑚𝑒𝑤𝑜𝑟𝑘) 2. Begin 3. 4. 5. 6. 7. 8. End.

Điểm cải tiến trong cấu trúc Ontology được đề xuất trong chương này là: (1) Ontology được xây dựng dựa trên ảnh đối tượng, bổ sung thuộc tính ảnh đối tượng và mối quan hệ giữa các đối tượng trên ảnh; (2) quá trình tìm kiếm trên Ontology được thực hiện mối quan hệ theo bộ ba < 𝑂𝑏𝑗𝑒𝑐𝑡𝑖 > < 𝑅𝑒𝑙𝑎𝑡𝑖𝑜𝑛𝑠ℎ𝑖𝑝 > < 𝑂𝑏𝑗𝑒𝑐𝑡𝑗 >; (3) Câu truy vấn SPARQL được xây dựng từ bộ ba mô tả hình ảnh. Cấu trúc Ontology sử dụng trong các hệ tìm kiếm ảnh SB-KDT, SB-iKDT, SB- NKDT ở Chương 2 là bổ sung thêm lớp, phân lớp trên các bộ ảnh thực nghiệm; quá trình tìm kiếm trên Ontology dựa trên tên phân lớp ảnh đầu vào để tạo câu truy vấn SPARQL với hai phép toán AND, UNION.

3.2.4. Phân cấp và bổ sung dữ liệu vào Ontology

Hình 3.10. Cấu trúc Class, SuperClass trên bộ ảnh MS-COCO

Phân cấp thư mục các bộ ảnh đa đối tượng MS-COCO, Flickr minh họa như Hình 3.10; quá trình bổ sung dữ liệu cho các bộ ảnh vào Ontology với tập dữ liệu MS-COCO, Flickr minh họa như Hình 3.11.

Mỗi ảnh đa đối tượng, sau khi phân đoạn đối tượng để hình thành nên các ảnh phân vùng đối tượng (Object images); mỗi đối tượng được lưu trữ bằng một tên (ObName) và giữa các đối tượng có mối quan hệ (Relationship) được phân lớp bằng cấu trúc Re KD-Tree. Trên cơ sở này, quá trình bổ sung đối tượng và mối quan hệ giữa các đối tượng trên ảnh để xây dựng Ontology.

Hình 3.11. Mô hình bổ sung dữ liệu vào Ontology tập ảnh đa đối tượng

Kết quả Ontology dạng N3 sau khi xây dựng và bổ sung dữ liệu theo ảnh đối tượng trên bộ ảnh MS-COCO như Hình 3.12.

Hình 3.12. Minh họa Ontology bộ ảnh MS-COCO dạng N3

3.2.5. Tìm kiếm trên Ontology

Sau khi xây dựng Ontology là quá trình tìm kiếm ảnh theo ngữ nghĩa, dữ liệu đầu vào là câu truy vấn SAPRQL [81]. Hiện nay, có nhiều ngôn ngữ để thực hiện truy vấn trên Ontology, trong luận án này ngôn ngữ truy vấn được lựa chọn là ngôn ngữ truy vấn SPARQL. Câu truy vấn SPARQL được xây dựng từ ảnh đối tượng và mối quan hệ giữa các ảnh đối tượng. Mục đích xây dựng câu truy vấn SPARQL là để thực hiện quá trình tìm kiếm trên Ontology nhanh và hiệu quả. Xây dựng câu truy vấn SPARQL dựa trên bộ ba mô tả ảnh đầu vào được thực hiện bằng hàm CSQ dữ liệu đầu vào là bộ ba (t𝑟𝑖𝑝𝑙𝑒); giá trị đầu ra là câu truy vấn 𝑆𝑃𝐴𝑅𝑄𝐿;

𝑛 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑐𝑙𝑎𝑠𝑠 𝑛𝑎𝑚𝑒𝑠 𝑜𝑓 𝑖𝑛𝑝𝑢𝑡 𝑖𝑚𝑎𝑔𝑒 𝐼 ; 𝑆𝑃𝐴𝑅𝑄𝐿 = "𝑆𝐸𝐿𝐸𝐶𝑇 𝐷𝐼𝑆𝑇𝐼𝑁𝐶𝑇 ? 𝐼𝑚𝑔 𝑊𝐻𝐸𝑅𝐸{"; 𝑭𝒐𝒓 𝑖 = 1 𝒕𝒐 𝑛 𝒅𝒐

𝑆𝑃𝐴𝑅𝑄𝐿+=< 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 >: 𝑂𝑏𝑗𝑒𝑐𝑡_𝑖 + "𝑟𝑑𝑓: 𝑡𝑦𝑝𝑒"+< 𝑜𝑏𝑗𝑒𝑐𝑡 > : +? 𝐼𝑚𝑔 + " 𝑹𝒆𝒍𝒂𝒕𝒊𝒐𝒏𝒔𝒉𝒊𝒑 𝒘𝒐𝒓𝒅" + : 𝑂𝑏𝑗𝑒𝑐𝑡 _j+"rdf:type"+

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

LUẬN ÁN TIẾN SĨ NGÀNH KHOA HỌC MÁY TÍNH

HUẾ, NĂM 2023

ĐẠ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

PGS. TS. LÊ MẠNH THẠNH

TS. VĂN THẾ THÀNH

HUẾ, NĂM 2023

LỜI CAM ĐOAN

LỜI CÁM ƠN

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT

DANH MỤC HÌNH ẢNH

DANH MỤC BẢNG BIỂU

PHẦN MỞ ĐẦU

CHƯƠNG 1.

TỔNG QUAN VỀ TÌM KIẾM ẢNH

VÀ CẤU TRÚC KD-TREE

CHƯƠNG 2. TÌM KIẾM ẢNH DỰA TRÊN CẤU TRÚC

KD-TREE

CHƯƠNG 3. PHÁT TRIỂN CẤU TRÚC KD-TREE THEO

TIẾP CẬN NGỮ NGHĨA

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

DANH MỤC CÔNG TRÌNH NGHIÊN CỨU CỦA TÁC GIẢ LIÊN

QUAN ĐẾN LUẬN ÁN

TÀI LIỆU THAM KHẢO

Erwin, E. (2017), Similarity-Content Based Image Retrieval for Multi-Objects Fruits Recognition using k-Means and k-Nearest Neighbor.

PHỤ LỤC

Có thể bạn quan tâm

Luận án Tiến sĩ: Nghiên cứu các yếu tố ảnh hưởng đến sự phát triển nguồn nhân lực du lịch trong các cơ sở lưu trú tại Hà Nội

Tóm tắt Luận án Tiến sĩ: Nghiên cứu các yếu tố ảnh hưởng đến sự phát triển nguồn nhân lực du lịch trong các cơ sở lưu trú tại Hà Nội

Luận án Tiến sĩ: Giáo dục đạo đức sinh thái cho sinh viên các trường đại học tại Thành phố Hồ Chí Minh hiện nay

Tóm tắt Luận án Tiến sĩ: Giáo dục đạo đức sinh thái cho sinh viên các trường đại học tại Thành phố Hồ Chí Minh hiện nay

Luận án Tiến sĩ: Công tác hoằng pháp và hoạt động của đạo tràng Phật giáo tỉnh Lào Cai hiện nay

Luận án Tiến sĩ: Hành vi nguy cơ ảnh hưởng đến sức khỏe tâm thần của học sinh trung học phổ thông tại Hà Nội hiện nay

Tóm tắt Luận án Tiến sĩ: Hành vi nguy cơ ảnh hưởng đến sức khỏe tâm thần của học sinh trung học phổ thông tại Hà Nội hiện nay

Luận án Tiến sĩ: Đảng bộ tỉnh Đồng Nai lãnh đạo công tác bảo tồn và phát huy giá trị các di tích lịch sử - văn hóa từ năm 1996 đến năm 2015

Tóm tắt Luận án Tiến sĩ: Đảng bộ tỉnh Đồng Nai lãnh đạo công tác bảo tồn và phát huy giá trị các di tích lịch sử - văn hóa từ năm 1996 đến năm 2015

Luận án Tiến sĩ: Thực hiện Pháp lệnh thực hiện dân chủ ở xã, phường, thị trấn vùng dân tộc thiểu số tỉnh Quảng Nam hiện nay

Tóm tắt Luận án Tiến sĩ: Thực hiện Pháp lệnh thực hiện dân chủ ở xã, phường, thị trấn vùng dân tộc thiểu số tỉnh Quảng Nam hiện nay

Tóm tắt Luận án Tiến sĩ: Công tác hoằng pháp và hoạt động của đạo tràng Phật giáo tỉnh Lào Cai hiện nay

Luận án Tiến sĩ: Nghiên cứu chất lượng dịch vụ viễn thông di động tại Tổng công ty viễn thông Viettel

Luận án Tiến sĩ: Nâng cao chất lượng cơ sở vật chất các trường đại học tư thục trên địa bàn thành Hà Nội

Luận án Tiến sĩ: Năng lực cạnh tranh của doanh nghiệp nhỏ và vừa trên địa bàn tỉnh Phú Thọ

Luận án Tiến sĩ: Nghiên cứu các yếu tố ảnh hưởng tới sự thành công trong khởi sự kinh doanh của phụ nữ khu vực miền Bắc

Luận án Tiến sĩ: Kiểm soát nội bộ tại Tập đoàn xăng dầu Việt Nam

Tóm tắt Luận án Tiến sĩ: Kiểm soát nội bộ tại Tập đoàn xăng dầu Việt Nam

Luận án Tiến sĩ: Nghiên cứu giải pháp phát triển trung tâm logistics quốc tế cho khu vực kinh tế trọng điểm phía Bắc

Luận án Tiến sĩ: Nghiên cứu các nhân tố ảnh hưởng đến mức độ công bố thông tin trên báo cáo thường niên của các ngân hàng thương mại Việt Nam

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu