I. Giới thiệu về cấu trúc cây R Tree và ứng dụng trong tìm kiếm ảnh
Cấu trúc cây R-Tree là một cấu trúc dữ liệu không gian hiệu quả, được sử dụng rộng rãi trong các bài toán tìm kiếm và phân cụm dữ liệu. Trong luận văn này, cấu trúc cây R-Tree được áp dụng để giải quyết bài toán tìm kiếm ảnh dựa trên đặc trưng cấp thấp như màu sắc, hình dạng và kết cấu. Phân cụm không gian là một kỹ thuật quan trọng giúp nhóm các ảnh có đặc trưng tương tự vào cùng một cụm, từ đó tăng hiệu suất tìm kiếm. Luận văn thạc sĩ này đề xuất một cải tiến trong cấu trúc cây R-Tree để tối ưu hóa quá trình tìm kiếm ảnh, đặc biệt là trong các hệ thống cơ sở dữ liệu lớn.
1.1. Cấu trúc cây R Tree nguyên thủy
Cấu trúc cây R-Tree nguyên thủy là một cấu trúc dữ liệu đa chiều, được thiết kế để lưu trữ và truy vấn các đối tượng không gian. Mỗi nút trong cây đại diện cho một hình chữ nhật bao phủ tối thiểu (MBR), giúp giảm thiểu thời gian tìm kiếm. Tuy nhiên, cấu trúc này có một số hạn chế khi áp dụng cho bài toán tìm kiếm ảnh, đặc biệt là khi dữ liệu tăng trưởng nhanh. Thuật toán R-Tree cần được cải tiến để tăng hiệu suất và độ chính xác trong các hệ thống tìm kiếm ảnh hiện đại.
1.2. Ứng dụng R Tree trong tìm kiếm ảnh
Ứng dụng R-Tree trong tìm kiếm ảnh đã được nghiên cứu rộng rãi. Cấu trúc này giúp tăng tốc độ truy vấn bằng cách nhóm các ảnh có đặc trưng tương tự vào cùng một nút. Phân tích dữ liệu không gian cho thấy rằng cấu trúc cây R-Tree có thể giảm đáng kể thời gian tìm kiếm trong các hệ thống cơ sở dữ liệu lớn. Tuy nhiên, việc tách nút trong cây có thể gây ra sự thay đổi lớn trong cấu trúc, làm giảm hiệu suất. Do đó, luận văn đề xuất một cải tiến để hạn chế việc tách nút và tăng hiệu quả tìm kiếm.
II. Phân cụm không gian và tối ưu hóa tìm kiếm ảnh
Phân cụm không gian là một kỹ thuật quan trọng trong tìm kiếm ảnh, giúp nhóm các ảnh có đặc trưng tương tự vào cùng một cụm. Công nghệ tìm kiếm hiện đại đòi hỏi các phương pháp phân cụm hiệu quả để tăng tốc độ và độ chính xác của quá trình tìm kiếm. Luận văn này đề xuất một phương pháp phân cụm dựa trên cấu trúc cây R-Tree, kết hợp với bảng băm để tối ưu hóa quá trình tìm kiếm. Tối ưu hóa tìm kiếm là một yếu tố quan trọng trong các hệ thống cơ sở dữ liệu lớn, đặc biệt là khi xử lý dữ liệu ảnh.
2.1. Kỹ thuật phân cụm K Means và K NN
Phân cụm K-Means và phương pháp láng giềng gần nhất (K-NN) là hai kỹ thuật phổ biến trong phân cụm không gian. Tuy nhiên, các phương pháp này có một số hạn chế khi áp dụng cho bài toán tìm kiếm ảnh, đặc biệt là khi dữ liệu tăng trưởng nhanh. Cấu trúc cây R-Tree được đề xuất để vượt qua các hạn chế này, giúp tăng hiệu suất và độ chính xác của quá trình tìm kiếm.
2.2. Tối ưu hóa tìm kiếm bằng cấu trúc HM RST
Luận văn đề xuất một cấu trúc mới, gọi là HM-RST, kết hợp cấu trúc cây R-Tree với bảng băm để tối ưu hóa quá trình tìm kiếm. Cấu trúc này giúp giảm chi phí tách nút và tăng hiệu suất tìm kiếm. Thuật toán tìm kiếm ảnh tương tự được cải tiến để hoạt động hiệu quả hơn trên cấu trúc HM-RST, đặc biệt là trong các hệ thống cơ sở dữ liệu lớn.
III. Thực nghiệm và đánh giá hiệu quả của cấu trúc HM RST
Luận văn tiến hành thực nghiệm trên các bộ dữ liệu ảnh phổ biến như COREL, OxfordFlowers-17 và MS-COCO để đánh giá hiệu quả của cấu trúc HM-RST. Kết quả thực nghiệm cho thấy rằng cấu trúc này giúp tăng đáng kể độ chính xác và giảm thời gian tìm kiếm so với các phương pháp truyền thống. Hệ thống cơ sở dữ liệu sử dụng cấu trúc HM-RST đạt hiệu suất cao hơn trong việc truy vấn và tìm kiếm ảnh tương tự.
3.1. Thực nghiệm trích xuất đặc trưng ảnh
Quá trình trích xuất đặc trưng ảnh được thực hiện để tạo ra các véc-tơ đặc trưng làm cơ sở cho việc tìm kiếm. Cấu trúc HM-RST được sử dụng để lưu trữ và truy vấn các véc-tơ này, giúp tăng tốc độ tìm kiếm. Kết quả thực nghiệm cho thấy rằng phương pháp này đạt độ chính xác cao hơn so với các phương pháp truyền thống.
3.2. So sánh hiệu suất với các phương pháp khác
Luận văn so sánh hiệu suất của cấu trúc HM-RST với các phương pháp khác như K-Means và K-NN. Kết quả cho thấy rằng cấu trúc HM-RST đạt hiệu suất cao hơn trong việc tìm kiếm ảnh tương tự, đặc biệt là trong các hệ thống cơ sở dữ liệu lớn. Tối ưu hóa tìm kiếm là một yếu tố quan trọng giúp cải thiện hiệu suất của hệ thống.
