TỔNG QUAN BÀI TOÁN TÌM KIẾM ẢNH THEO NỘI DUNG
Giới thiệu
Trong thập niên qua, một kho dữ liệu ảnh khổng lồ đã được chia sẻ trên Internet, dẫn đến việc các nhà khoa học nghiên cứu nhiều phương pháp truy vấn hình ảnh để nâng cao hiệu quả và tính chính xác của tìm kiếm Phương pháp tìm kiếm hình ảnh chủ yếu dựa vào từ khóa, sử dụng danh sách từ khóa để mô tả nội dung thông tin và khớp với tìm kiếm văn bản của người dùng Tuy nhiên, các hạn chế như tính chủ quan của mô tả và sự mơ hồ của ngôn ngữ tự nhiên có thể dẫn đến kết quả không chính xác Để khắc phục, các nhà nghiên cứu đã phát triển hệ thống tìm kiếm hình ảnh dựa trên nội dung (CBIR), sử dụng các tính năng trực quan như màu sắc, kết cấu, hình dạng và vị trí để tìm kiếm và phân tích hình ảnh.
Tìm kiếm hình ảnh dựa trên nội dung (CBIR) đã được nghiên cứu trong nhiều năm, tập trung vào việc trích xuất và so sánh các tính năng từ hình ảnh Các tính năng này được tự động trích ra từ điểm ảnh thông qua màu sắc, kết cấu và hình dạng, nhằm phục vụ cho việc tìm kiếm hình ảnh tương tự một cách hiệu quả.
Tìm kiếm ảnh là quá trình tra cứu hình ảnh liên quan từ một tập dữ liệu hình ảnh Kỹ thuật tìm kiếm ảnh theo nội dung sử dụng các phương pháp để xác định hình ảnh dựa trên việc trích xuất các đặc trưng như màu sắc, cấu trúc, hình dạng và vị trí của hình ảnh.
Tra cứu ảnh dựa vào văn bản
Trước khi công nghệ Tìm kiếm ảnh dựa vào nội dung ra đời, việc tìm kiếm hình ảnh chủ yếu dựa vào các chú thích văn bản được gán nhãn bởi cộng đồng Tuy nhiên, do tính chất gán nhãn tùy ý, việc sử dụng nhãn này để tra cứu ảnh gặp nhiều khó khăn, dẫn đến độ chính xác không cao và khó khăn trong việc tin tưởng vào kết quả tìm kiếm.
Việc sử dụng công nghệ đa phương tiện và thiết bị điện tử có máy ảnh đã dẫn đến sự gia tăng đáng kể của cơ sở dữ liệu hình ảnh kỹ thuật số, với hàng tỷ bức ảnh được tải lên mạng xã hội Truy xuất hình ảnh dựa trên văn bản (TBIR) là phương pháp phổ biến nhất, tuy nhiên, nó giả định rằng tất cả hình ảnh đều được chú thích, điều này không đúng với các cơ sở dữ liệu lớn nơi người dùng tải lên ảnh mà không có nhãn cụ thể Mặc dù ghi nhãn thủ công có thể là một giải pháp, nhưng nó tốn thời gian và không khả thi cho các bộ sưu tập lớn Thêm vào đó, phương pháp TBIR còn gặp khó khăn do khoảng cách ngữ nghĩa giữa truy vấn văn bản của người dùng và thuộc tính hình ảnh.
Hệ thống tìm kiếm dựa trên văn bản thường yêu cầu dữ liệu được chú thích bằng tay, cho phép người dùng tìm kiếm thông qua mô tả văn bản về dữ liệu đa phương tiện Tìm kiếm kết hợp giữa yêu cầu của người dùng và chú thích từ khoá TBIR, sử dụng các đặc trưng trực quan cấp thấp như màu sắc, kết cấu, hình dạng và vị trí để lấy dữ liệu, đặc biệt là hình ảnh Những đặc trưng này được trích xuất tự động từ hình ảnh Google và Bing áp dụng kỹ thuật tìm kiếm dựa trên từ khoá, mang lại sự nhanh chóng và hiệu quả trong quá trình tìm kiếm.
Dữ liệu thường được mô tả qua một tập hợp từ khóa hoặc siêu văn bản do người dùng cung cấp, điều này phụ thuộc vào tính chủ quan của họ Hệ thống tìm kiếm dữ liệu đa phương tiện dựa trên văn bản có thể trả về kết quả không liên quan, dẫn đến việc người dùng nhận được thông tin không mong muốn Do đó, một trong những nhược điểm lớn nhất của các hệ thống này là khả năng trả lại dữ liệu dự phòng hoặc không liên quan, khiến kết quả trở nên đơn giản và kém hiệu quả.
Tra cứu ảnh dựa vào nội dung
Truy xuất hình ảnh dựa trên nội dung (CBIR) là một phương pháp hiệu quả để lấy các hình ảnh liên quan Hệ thống CBIR cho phép người dùng cung cấp hình ảnh truy vấn và tìm kiếm hình ảnh tương tự Quá trình này bao gồm việc mã hóa và lập chỉ mục hình ảnh dựa trên các tính năng hình ảnh của chúng, với các hình ảnh được trả về dựa trên sự tương đồng về các tính năng này Hiệu suất của quá trình truy xuất phụ thuộc vào việc lựa chọn các tính năng trực quan cấp thấp.
Tra cứu ảnh dựa vào nội dung ra đời nhằm khắc phục nhược điểm của phương pháp dựa trên văn bản Phương pháp này phân tích hình ảnh nguồn thành các đặc trưng như màu sắc, độ sâu, kết cấu, hình dạng và các đối tượng trong ảnh Bằng cách sử dụng thuật toán để so sánh độ tương đồng với các ảnh có sẵn, độ chính xác trong truy vấn được nâng cao và đáng tin cậy hơn so với các phương pháp truyền thống.
Tìm kiếm ảnh dựa trên nội dung (CBIR) tập trung vào việc trích xuất và so sánh các đặc trưng từ hình ảnh, văn bản và âm thanh Các đặc trưng dữ liệu thường được lấy từ các yếu tố cấp thấp như màu sắc, hình dạng và âm sắc Trong suốt thập kỷ qua, các nhà nghiên cứu đã chứng minh hiệu quả và độ chính xác của các kỹ thuật CBIR.
Trích xuất đặc trưng ảnh
Màu sắc là một đặc trưng quan trọng trong tìm kiếm ảnh, với mỗi điểm ảnh được biểu diễn trong không gian màu sắc ba chiều như RGB, Munsell, CIE và HSV Tìm kiếm ảnh dựa trên màu sắc yêu cầu tính toán biểu đồ màu để xác định tỉ trọng các điểm ảnh có giá trị màu sắc đặc biệt Nghiên cứu hiện tại tập trung vào việc phân vùng ảnh theo màu sắc và mối quan hệ giữa các vùng này, đồng thời trích xuất màu sắc chủ đạo để tăng độ chính xác trong việc đối sánh hình ảnh Các điểm ảnh được gom cụm theo dãy màu Newton và sử dụng thuật toán K-Means để phân loại theo sáu cụm màu Về đặc trưng kết cấu, việc trích xuất nội dung ảnh nhằm phát hiện mô hình trực quan của ảnh thông qua các texel, xác định vị trí và loại kết cấu trong ảnh Cuối cùng, đặc trưng hình dạng là yếu tố quan trọng trong nhận dạng mẫu, giúp đo lường thuộc tính hình học của đối tượng để phục vụ cho phân lớp và nhận diện.
Trong bộ dữ liệu hình ảnh của ImageCLEF, mỗi bức ảnh được phân tích thành một vector đặc trưng với 27 thuộc tính, được phân loại thành các nhóm khác nhau.
▪ Đặc trưng vùng: diện tích, chiều rộng và chiều cao.
▪ Đặc trưng vị trí: giá trị trung bình và độ lệch chuẩn theo trục x và trục y.
▪ Đặc trưng về hình dạng (shape): boundary/area, convexity.
▪ Đặc trưng màu sắc trong không gian RGB và CIE-Lab: trung bình, độ lệch chuẩn và độ nghiêng.
1 Diện tích vùng (số pixel/tổng số pixel của hình ảnh)
2 Chiều rộng: số pixel theo chiều rộng của vùng/số pixel của chiều rộng ảnh
3 Chiều cao: số pixel theo chiều cao của vùng/số pixel của chiều cao ảnh
4 Giá trị trung bình theo trục x: giá trị trung bình theo trục x của các pixel trong vùng
5 Độ lệch chuẩn theo trục x
6 Giá trị trung bình theo trục y: giá trị trung bình theo trục y của các pixel trong vùng
7 Độ lệch chuẩn theo trục y
9 Convexity: số pixel phần lõm của vùng/tổng số pixel của vùng
10 Trung bình theo màu R (RGB)
11 Độ lệch chuẩn theo màu R (RGB)
12 Độ nghiêng theo màu R (RGB)
13 Trung bình theo màu G (RGB)
14 Độ lệch chuẩn theo màu G (RGB)
15 Độ nghiêng theo màu G (RGB)
16 Trung bình theo màu B (RGB)
17 Độ lệch chuẩn theo màu B (RGB)
18 Độ nghiêng theo màu B (RGB)
19 Trung bình theo màu L (CIE-Lab)
20 Độ lệch chuẩn theo màu L (CIE-Lab)
21 Độ nghiêng theo màu L (CIE-Lab)
22 Trung bình theo màu a (CIE-Lab)
23 Độ lệch chuẩn theo màu a (CIE-Lab)
24 Độ nghiêng theo màu a (CIE-Lab)
25 Trung bình theo màu b (CIE-Lab)
26 Độ lệch chuẩn theo màu b (CIE-Lab)
27 Độ nghiêng theo màu b (CIE-Lab)
Độ đo tương đồng giữa 2 vector đặc trưng
Nghiên cứu này áp dụng phương pháp tính độ đo tương đồng giữa hai vector đặc trưng dựa trên Khoảng cách Euclide Theo định nghĩa, khoảng cách Euclidean là chiều dài của đường thẳng nối hai điểm Trong mặt phẳng, khoảng cách giữa hai điểm (x1, y1) và (x2, y2) được xác định theo định lý Pythagorean.
Ta có công thức tổng quát cho khoảng cách Euclide giữa 2 vector đặc trưng: v 1 : vector thứ nhất v 2 : vector thứ hai d (v 1 , v 2 ) = √∑ 27 =1 ( 1 − 2 ) 2
Thuật toán gom cụm K-Means
K-Means là thuật toán rất quan trọng và được sử dụng phổ biến trong kỹ thuật phân cụm Tư tưởng chính của thuật toán K-Means là tìm cách phân nhóm các đối tượng (objects) đã cho vào K cụm (K là số các cụm được xác định trước, K nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối tượng đến tâm nhóm
Thuật toán K-Means thực hiện qua các bước chính sau:
1 Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster) Mỗi cụm được đại diện bằng các tâm của cụm.
2 Tính khoảng cách giữa các đối tượng (objects) đến K tâm (thường dùng khoảng cách Euclidean)
3 Nhóm các đối tượng vào nhóm gần nhất
4 Xác định lại tâm mới cho các nhóm
5 Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối tượng
Thuật toán K-Means nổi bật với tính đơn giản, dễ hiểu và dễ cài đặt Tuy nhiên, nó cũng gặp phải một số hạn chế, bao gồm sự phụ thuộc vào việc xác định số nhóm K trước và chi phí tính toán cao khi số cụm K và dữ liệu phân cụm lớn.
HỆ TRA CỨU ẢNH DỰA TRÊN CẤU TRÚC CÂY R-TREE
Các khái niệm cơ bản về cây R-Tree [20]
Quản lý dữ liệu không gian đã được nghiên cứu chuyên sâu trong hơn ba thập kỷ, với các vấn đề quan trọng như mô hình dữ liệu, cơ chế lập chỉ mục và xử lý truy vấn Cấu trúc cây R-Tree, do Guttman đề xuất năm 1984, là một trong những phương pháp truy xuất nổi bật, giúp lập chỉ mục hiệu quả cho các đối tượng không gian trong ứng dụng VLSI Từ đó, nhiều biến thể của R-Tree đã được phát triển nhằm cải thiện hiệu suất truy xuất và xử lý các đối tượng đa chiều.
Với sự phát triển của công nghệ, các phương pháp truy xuất dữ liệu mới đã được đề xuất và cải tiến, trong đó có cấu trúc cây R-Tree Cấu trúc này được ứng dụng để xử lý các loại dữ liệu hình học như điểm, đoạn thẳng, bề mặt, khối lượng và thể tích cong trong không gian Cây R-Tree hoạt động tương tự như cây B-Tree, nhưng trong khi cây R-Tree phục vụ cho cơ sở dữ liệu không gian, cây B-Tree lại được sử dụng cho các kiểu dữ liệu chữ và số.
Cây R-Tree được ứng dụng rộng rãi trong việc xử lý dữ liệu đa chiều, đặc biệt trong các cơ sở dữ liệu không gian và hệ thống thông tin địa lý Hiện nay, các cơ sở dữ liệu đa phương tiện đang được thiết kế để xử lý nhiều loại dữ liệu mới như hình ảnh, giọng nói, âm thanh và video R-Tree đóng vai trò quan trọng trong việc lưu trữ và truy xuất dữ liệu cho các ứng dụng này, bao gồm cơ sở dữ liệu không gian, hình ảnh và video.
Cây R-Tree, được giới thiệu bởi Guttman vào năm 1984, là một cấu trúc dữ liệu đa nhánh cân bằng dùng để phân vùng dữ liệu thành các khối có thể lồng nhau hoặc chồng lên nhau Trong cây này, dữ liệu được lưu trữ tại các nút lá, mỗi nút là một vùng không gian hình chữ nhật hoặc đa giác chứa các vùng không gian con và các liên kết đến các nút con Mỗi nút có số phần tử tối thiểu là m và tối đa là M, trong khi các nút lá chứa các liên kết trỏ đến các đối tượng dữ liệu, giúp phân chia dữ liệu thành các cụm trong không gian k-chiều.
Hình 3 Mô tả vùng không gian lưu trữ và các dữ liệu bên trong nó
Hình 4 Cây R-Tree tương ứng
R-Tree là một cấu trúc dữ liệu cây được sử dụng để lưu trữ các chỉ mục dữ liệu không gian một cách hiệu quả R-Tree rất hữu ích cho việc truy vấn và lưu trữ dữ liệu không gian Một số ứng dụng thực tế được đề cập dưới đây:
▪ Lập chỉ mục thông tin đa chiều.
▪ Xử lý tọa độ không gian địa lý.
▪ Thực hiện bản đồ ảo.
▪ Xử lý dữ liệu trò chơi.
Các tính chất của cây R-Tree:
▪ Bao gồm một gốc duy nhất (rootNode), tập các nút trong (inNodes) và tập các nút lá (leafNodes).
▪ Root chứa con trỏ đến vùng lớn nhất trong miền không gian.
▪ Các nút cha chứa các con trỏ tới các nút con trong đó vùng của các nút con nằm bên trong vùng của các nút cha.
▪ Các nút lá chứa dữ liệu các đối tượng.
▪ Vùng giới hạn tối thiểu là vùng nhỏ nhất chứa đối tượng đang xem xét.
Cây R ban đầu có hai nhược điểm quan trọng:
Truy xuất một điểm trong cây R có thể yêu cầu xem xét nhiều đường dẫn từ gốc đến lá, điều này có thể làm giảm hiệu suất, đặc biệt khi có sự chồng lấp giữa các vùng không gian.
Các khu vực lưu trữ lớn có thể gây ra tình trạng chồng lấp dữ liệu, làm giảm hiệu suất khi thực hiện các truy vấn trong không gian do sự tồn tại của không gian trống.
3.1.3 R-Tree trong dữ liệu không gian
Các hệ thống cơ sở dữ liệu không gian tích hợp các yếu tố không gian và thời gian của dữ liệu, phục vụ cho nhiều ứng dụng quan trọng Việc xử lý hiệu quả các truy vấn không gian là cần thiết trong các lĩnh vực như hệ thống thông tin di động, kiểm soát giao thông, và giám sát không lưu trong ngành hàng không, cũng như trong hệ thống thông tin địa lý GIS.
Hệ thống Thông tin Địa lý (GIS) và Dịch vụ Dựa trên Vị trí (LBS) là những ứng dụng quan trọng trong việc xử lý dữ liệu không gian và thời gian Các ứng dụng này dựa trên việc xác định vị trí hoặc hình dạng của dữ liệu theo thời gian, giúp tối ưu hóa việc khai thác thông tin địa lý.
Các phương pháp truy cập và kỹ thuật xử lý truy vấn cho cơ sở dữ liệu không gian thường được phân loại trong các lĩnh vực sau:
Các kỹ thuật xử lý truy vấn cho vị trí trong quá khứ của đối tượng bao gồm việc lưu trữ và truy vấn các vị trí này thông qua các phương thức truy cập nhiều phiên bản hoặc các phương thức chuyên biệt cho quỹ đạo của đối tượng.
Kỹ thuật xử lý truy vấn cho các vị trí hiện tại và tương lai của đối tượng cho phép xác định vị trí tương lai dựa trên các đặc điểm hiện tại của chuyển động, bao gồm vị trí tham chiếu và vectơ vận tốc Mỗi đối tượng chuyển động được biểu diễn dưới dạng hàm của thời gian, giúp nâng cao khả năng dự đoán và theo dõi chuyển động một cách chính xác.
Các biến thể của cây R-Tree được ứng dụng trong các lĩnh vực này là: Cây RT-
Tree, cây 3D R-Tree, cây RST-Tree, Cây TB-tree, Cây Q+R-Tree, Cây VCI R-Tree…
Cây RT-Tree kết hợp thông tin thời gian vào phương pháp truy cập cây R-Tree, tạo ra một cấu trúc dữ liệu mạnh mẽ hơn Cây RT-Tree được tăng cường với thông tin thời gian ở mỗi nút lá, tuy nhiên, quá trình xây dựng cây vẫn bị chi phối bởi thông tin không gian Điều này dẫn đến việc xử lý các truy vấn trở nên tốn thời gian hơn.
▪ Cây 3D R-Tree, được đề xuất trong, coi thời gian là một chiều thứ 3 và biểu thị các vùng dữ liệu không gian hai chiều.
Cây RST có khả năng lập chỉ mục dữ liệu không gian thời gian thực với các phạm vi không gian thay đổi riêng biệt Khác với các cấu trúc lập chỉ mục trước đây, cây RST hỗ trợ dữ liệu với hai kích thước thời gian và hai kích thước không gian.
Cây TB-Tree được phát triển nhằm tối ưu hóa việc truy cập lịch sử của các đối tượng Đặc điểm nổi bật của cây TB-Tree là khả năng giảm thiểu các yêu cầu truy cập không gian, đảm bảo rằng các đối tượng lân cận được lưu trữ trong cùng một nút lá.
▪ Cây Q + R là sơ đồ lập chỉ mục cho các đối tượng chuyển động, giúp giảm đáng kể chi phí cập nhật.
Cây VCI R-Tree là một công cụ quan trọng để lập chỉ mục các đối tượng chuyển động Sơ đồ lập chỉ mục của cây này được điều chỉnh nhằm tối ưu hóa việc thao tác với các vật thể di chuyển, giúp nâng cao hiệu quả xử lý dữ liệu.
3.1.4 R-Tree trong dữ liệu đa phương tiện
Một phương pháp cải tiến cho bài toán tìm kiếm ảnh dựa trên cây R-Tree
Theo L.T.V Thanh (2020), RG-Tree (Region Growth Tree) là một cải tiến của cây R-Tree, được phát triển để tìm kiếm ảnh tương tự theo nội dung Trong RG-Tree, các véc-tơ đặc trưng của hình ảnh được lưu trữ tại các nút lá theo quy tắc phân hoạch đã đề xuất Cây RG-Tree cho phép tăng trưởng để lưu trữ các vùng dữ liệu, phân bố trên các nút lá và tạo thành các cụm dữ liệu, với việc phân nhóm các phần tử tương đồng vào các nhánh con Đặc biệt, RG-Tree giải quyết vấn đề tái tạo toàn bộ cây khi xóa một phần tử Dựa trên lý thuyết này, một mô hình tìm kiếm ảnh đã được thiết kế dựa trên cấu trúc của cây RG-Tree.
3.2.1 Cấu trúc cây RG-Tree
Cấu trúc cây RG-Tree là một cây đa nhánh dùng để phân cụm dữ liệu theo vùng Nó bao gồm một nút gốc, các nút trong và nút lá Mỗi nút trong liên kết đến các nút con, tạo ra đường dẫn từ nút gốc đến nút lá, trong khi các nút lá lưu trữ các vector đặc trưng tương đồng Phân bổ các phần tử tại mỗi nút được thực hiện theo bán kính (theta – ngưỡng trên) và (slack – ngưỡng dưới).
Gọi E = là một thành phần trong nút của cây, với f = (v1, …, vk) và id là các số hiệu của vector đặc trưng ảnh Cây RG-Tree lưu trữ tập hợp các vector đặc trưng ảnh T = {Ei | i = 1, …, N}, trong đó N là số lượng ảnh trong bộ dữ liệu Cây RG-Tree được sử dụng để phân cụm các vector đặc trưng của ảnh dựa trên khoảng cách Euclide.
Gọi f I , f J lần lượt là hai vector đặc trưng của hai ảnh I, J Hai ảnh là tương tự nhau được định nghĩa như sau:
17 Định nghĩa 1: Hai ảnh I, J được gọi là tương tự nhau nếu ( , ) < Trong đó ( , ) là khoảng cách Euclide giữa hai ảnh I và J.
Cây RG-Tree xây dựng mô hình phân cụm cho tập vector đặc trưng của ảnh, hỗ trợ hiệu quả trong việc tìm kiếm ảnh tương tự Quá trình tạo cây dẫn đến việc hình thành các nút trong và nút lá, trong đó nút trong chứa liên kết đến các nút con, còn nút lá lưu trữ các vector đặc trưng có sự tương đồng với nhau.
Gọi là một bộ mô tả một thành phần của một nút trong với lần lượt là phần tử và liên kết đến các nút kế cận
Cây phân cụm RG-Tree được định nghĩa là một cây đa nhánh, bao gồm một nút gốc (root) liên kết với các nhánh con và một tập hợp các nút trong (inNode) cùng với một tập hợp các nút lá (lvNode) Nút gốc được biểu diễn dưới dạng root = {, trong khi tập nút trong được định nghĩa là inNode = { | k = 1…K} với điều kiện d(fci, fctb) ≤ fctb = 1 ∑ 1 Tập nút lá được mô tả là lvNode = { | k = 1…K}, trong đó lvE = và thoả mãn điều kiện d(f i , f c ).
Cây RG-Tree ban đầu chỉ có một nút gốc với các liên kết rỗng Khi thêm các phần tử E i vào cây, các nhánh được hình thành tương ứng với các nút lá dựa trên độ đo Euclide Quy tắc phân bố các phần tử trong cây được xác định như sau: bắt đầu từ nút gốc, thực hiện theo Quy tắc 1 là chọn hướng đi từ nút hiện hành đến các nút của nhánh kế cận, ưu tiên nhánh có khoảng cách d(f i , f ci ) gần nhất Nếu khoảng cách d(f i , f ci ) ≤ một ngưỡng nhất định, ta sẽ đi theo nhánh đó và tiếp tục tìm nhánh con phù hợp cho đến khi gặp nút lá, với ba trường hợp khác nhau có thể xảy ra.
▪ Nếu d(f i , f ci ) < , đưa phần tử f i vào nút lá hiện hành (có tâm f ci )
▪ Nếu ≤ d(f newLeaf i , f ci ) ≤ , tạo một nút lá mới (newLeaf) để chứa f i ; một nút cha mới (inNode) chứa nút lá cũ (có tâm f ci ) và nút
▪ Nếu d(f i , f ci ) > , tạo một nút newLeaf để chứa f i có cùng cha với nút lá hiện hành
18 c) Quy tắc 3 : Nếu d(f i , f ci ) > , tạo một nút newLeaf để chứa f i có cùng cha với nút hiện hành.
Với sự gia tăng nhanh chóng của dữ liệu ảnh, cây RG-Tree cần có khả năng mở rộng để đáp ứng nhu cầu lưu trữ Các định lý dưới đây sẽ chứng minh tính khả thi của sự phát triển này trong cây RG-Tree.
• Định lí 1: Cây RG-Tree tăng trưởng từ gốc đến lá
Theo Định nghĩa 3, khi thêm một vector đặc trưng vào cây RG-Tree, nó sẽ chọn hướng đi phù hợp và được thêm vào một nút lá có sẵn hoặc một nút lá mới, chứng minh rằng RG-Tree là một cây tăng trưởng Mỗi phần tử được thêm vào RG-Tree theo thứ tự, do đó cần có một nút để chứa phần tử này Định lý sau đây sẽ chứng minh tính tồn tại và duy nhất của một nút trên cây RG-Tree để lưu trữ các phần tử.
• Định lí 2: Cho một vector đặc trưng f i , thì vector này thuộc vào một nút trên cây.
Để chứng minh, hãy gọi f i là vector cần thêm vào một nút trên cây RG-Tree Theo Định nghĩa 3 [8], khi thực hiện quy tắc tạo cây, phần tử f i sẽ thuộc về một nút lá hiện tại hoặc tạo ra một nút lá mới phù hợp Do đó, luôn tồn tại một nút để lưu trữ vector f i.
• Định lí 3: Một vector đặc trưng f i chỉ được lưu trữ trong một nút duy nhất trên cây RG-Tree.
Giả sử có hai vector f i và f j cùng thuộc một nút, điều này chứng tỏ rằng chúng là hai phần tử trong cùng một cụm Do đó, ta có d(f i , f c ) = d(f j , f c ), và vì một nút là một phâm cụm phẳng, ta suy ra rằng f i ≡ f j Điều này có nghĩa là mỗi vector đặc trưng f i chỉ được lưu trữ trong một nút duy nhất trên cây RG-Tree Khi phân bố từng phần tử, phần tử đó phải thuộc về cụm phù hợp nhất, tức là các phần tử trong cùng một cụm sẽ có độ tương tự cao nhất theo tiêu chí đã được chọn Định lý sau đây sẽ chứng minh tính phân bố phù hợp của một phần tử trên cây RG-Tree.
• Định lí 4: Một vector đặc trưng v được phân bố vào cụm phù hợp nhất theo độ đo Euclide.
Trường hợp 1 chứng minh rằng vector đặc trưng thuộc về nút lá hiện hành, tức là ( , ) < , cho thấy chúng ta có thể xác định một cụm tại nút lá với độ tương tự cao nhất.
Trong trường hợp tất cả khoảng cách giữa các tâm với vector f i đều vượt ngưỡng cho trước, tức là không có nút nào trên cây phù hợp với vector f i, chúng ta sẽ tạo ra một nút lá mới (newLeaf) Nút mới này sẽ được xây dựng theo quy tắc tại Định nghĩa 3, và sẽ chứa các phần tử có đặc tính gần giống với vector f i.
Từ 2 trường hợp trên, ta có một vector đặc trưng f i được phân bố vào cụm phù hợp nhất theo độ đo Euclide.
Cây RG-Tree tạo ra phân hoạch đa tầng, giúp tăng độ chính xác khi tìm kiếm cụm trong bán kính nhất định Trong phạm vi này, cây phân chia vector đặc trưng vào một nhánh, dẫn đến các phân hoạch đều đặn Các phần tử khác biệt sẽ không thuộc cùng một nhánh, do đó cây RG-Tree có xu hướng trở thành cây đa nhánh cân bằng.
3.2.2 Một cải tiến cấu trúc cây RG-Tree
Việc xác định đường đi của một phần tử p được giới hạn bởi khoảng cách từ p đến cụm R i Nếu tồn tại một cụm R j khác mà có khoảng cách tương đương, việc xác định cụm chứa p sẽ gặp khó khăn Để khắc phục vấn đề này, chúng tôi đã xây dựng cây KNN_R-Tree với cấu trúc tương tự như cây RG-Tree, đồng thời cải tiến bằng cách kết hợp kỹ thuật KNN để tìm K láng giềng gần nhất trong quá trình xây dựng và tìm kiếm ảnh tương tự trên cây.
Trong bài toán này, chúng tôi áp dụng kỹ thuật học máy KNN để xác định số láng giềng gần nhất của phần tử p theo Định nghĩa 4 Cụ thể, Eps-neighborhood của phần tử p, ký hiệu là NEps(p, D), được xác định bởi tập hợp các phần tử trong cơ sở dữ liệu D mà khoảng cách đến p không vượt quá ngưỡng Eps đã được chỉ định.
Cài đặt cấu trúc cây KNN_R-Tree
Trên cơ sở các Định lí 1, 2, 3 [9] Một vector đặc trưng và một nút trên cây KNN_R-Tree được cài đặt theo mã giả C# như sau: class FeatureVector
{ int ID { get; set; } int Label { get; set; } List Features { get; set; } } class NODE
NODE ParentNode { get; set; }List CenterNode { get; set; }
Các thuật toán xử lý trên cây KNN_R-Tree
3.4.1 Thuật toán chèn một phần tử vào cây KNN_R-Tree
Mỗi phần tử E i = được chèn vào cây dựa trên quy tắc chọn hướng đi theo cụm với khoảng cách Euclide nhỏ hơn một ngưỡng (theta) đã định Quá trình này sẽ tiếp tục cho đến khi tìm thấy nút lá phù hợp để chèn vào, hoặc khi vượt qua ngưỡng sẽ tạo ra một nhánh mới.
Khi thêm một phần tử E i = vào cây KNN_R-Tree, quá trình chèn bắt đầu từ nút gốc, tiếp tục duyệt qua các nút con và tính toán khoảng cách ReDiff giữa E i và từng tâm cụm Cuối cùng, chọn cụm có khoảng cách r min để thực hiện việc chèn.
Để tìm giá trị nhỏ nhất của ReDiff(f i, fc j) với j từ 1 đến M, nếu r min lớn hơn một giá trị nhất định, hãy tạo một nhánh mới để lưu trữ E i Ngược lại, nếu không, hãy tiếp tục theo nhánh hiện tại và duyệt qua tất cả các nhánh trong cây KNN_R-Tree cho đến khi hoàn tất.
Khi gặp nút lá, chúng ta sẽ tính khoảng cách E i với tâm của nút lá Nếu khoảng cách ReDiff(E i, leaf) nhỏ hơn một ngưỡng nhất định, E i sẽ được đưa vào nút lá Ngược lại, nếu khoảng cách lớn hơn ngưỡng, một nút lá mới sẽ được tạo ra cùng cấp với nút lá hiện tại để lưu trữ E i.
Khi một vector đặc trưng được thêm vào cây, cần phải cập nhật tâm của nút lá chứa vector đó và đồng thời cập nhật tâm cho tất cả các nút từ lá đến gốc Đầu vào bao gồm phần tử, nút gốc và giá trị ngưỡng.
If ( = ) then // when running the first time Initialize = { |
UCKNNRT (lvnode); // update the center node for this leaf node Else // 2 nd time and so on…
If (N.links = null) then // leafNode
Thuật toán IKNNRT có độ phức tạp O(M x h^2) khi chèn một vector đặc trưng vào cây KNN_R-Tree, trong đó h là chiều cao của cây và M là số phần tử tối đa trong một nút.
Thuật toán IKNNRT thực hiện duyệt từ gốc đến lá của cây, và mỗi lần duyệt qua M phần tử, nó cập nhật tâm từ nút lá đến nút gốc Do đó, độ phức tạp của thuật toán này được xác định là O(M x h^2).
3.4.2 Thuật toán cập nhật tâm cụm
Quá trình cập nhật tâm cụm nhằm tạo ra một lộ trình từ nút N đến nút gốc, giúp cải thiện thời gian tìm kiếm ảnh cho người dùng Việc cập nhật này được thực hiện dựa trên thuật toán UCKNNRT, bắt đầu từ nút N và hướng về nút gốc.
If (N.Elements_parent != null) then fcN = avg{N.E[i].f | i=1 count};
Mệnh đề 2: Thuật toán UCKNNRT có độ phức tạp là O(M x h) Với h, M lần lượt là chiều cao của cây và số phần tử tối đa trong một nút của cây
Trong trường hợp xấu nhất, thuật toán UCKNNRT cần cập nhật tâm cụm từ nút lá đến nút gốc, với mỗi lần cập nhật tâm, thuật toán sẽ duyệt qua M phần tử của mỗi nút Do đó, độ phức tạp của thuật toán UCKNNRT được xác định là O(M x h).
3.4.3 Thuật toán Tìm kiếm ảnh tương tự trên cây KNN_R-Tree
Mỗi ảnh sẽ được chia thành nhiều vùng theo phương pháp của Hugo Jair
Escalante trích xuất mỗi vùng thành một vector đặc trưng, bao gồm các yếu tố như diện tích, chiều rộng và chiều cao Ngoài ra, nó còn tính toán các đặc trưng vị trí với giá trị trung bình và độ lệch chuẩn theo trục x và y Các đặc trưng về hình dạng và màu sắc trong không gian RGB và CIE-Lab cũng được xem xét để tạo ra một mô tả toàn diện cho mỗi vùng.
Hình 9 Mô tả ảnh gốc và các phân vùng của nó 2 Thuật toán tìm kiếm
Mục đích chính của việc áp dụng cấu trúc cây KNN_R-Tree là tìm kiếm ảnh tương tự Quá trình bắt đầu bằng việc phân vùng và trích xuất các vector đặc trưng từ ảnh mà người dùng cung cấp Từ tập hợp các vector này, mỗi vector được duyệt qua cây KNN_R-Tree cho đến khi đến nút lá, tại đó sẽ thu thập toàn bộ các vector có trong nút lá trước khi tiếp tục với vector khác.
Gọi: S là ảnh cần truy vấn. Đầu vào: vector đặc trưng f i của ảnh S cần truy vấn, cây KNN_R-Tree, ngưỡng , , , Đầu ra: tập các ảnh tương tự với S.
If (N.links = null) then // nút lá, l y m i vector c a node nàyấ ọ ủ
If (r ≤ ) then // nút trong n m trong kho ngằ ả
Mệnh đề 3: Thuật toán KNNRTIR có độ phức tạp O(h x M) Với h, M lần lượt là chiều cao và số phần tử tối đa của một nút trong cây KNN_R-Tree.
Thuật toán KNNRTIR thực hiện việc duyệt các phần tử từ gốc đến lá, và trong mỗi lần duyệt, nó sẽ đi qua M phần tử của nút hiện hành Do đó, độ phức tạp của KNNRTIR được xác định là O(h x M).
Hình 10 Mô hình truy vấn ảnh
Quá trình tìm kiếm ảnh dựa trên mô hình đề xuất bao gồm hai pha: pha đầu tiên là gom cụm dữ liệu và lưu trữ trên cây KNN_R-Tree, trong khi pha thứ hai là tìm kiếm các hình ảnh tương tự theo nội dung.
Pha tiền xử lý bao gồm hai bước chính nhằm xây dựng cây gom cụm RG-Tree dựa trên vector đặc trưng của tập dữ liệu ảnh Kết quả của quá trình này là một cấu trúc dữ liệu hiệu quả, giúp tổ chức và phân tích thông tin hình ảnh một cách hợp lý.
Bước 1 : Thực hiện việc trích xuất tập véc-tơ đặc trưng f i của tập dữ liệu ảnh ban đầu.
Bước 2: Dựa trên độ đo tương tự được đề xuất, xây dựng cấu trúc cây gom cụm chỉ mục Mỗi nút lá của cây KNN_R-Tree sẽ chứa tập hợp các véc-tơ f i, đại diện cho các đặc trưng thị giác của hình ảnh.
Kết quả thực nghiệm
Kết quả thực nghiệm được thực hiện trên máy PC với CPU 2.3GHz 8-core 9th-generation Intel Core i9, 16GB 2666MHz RAM và 1TB flash storage Pha tìm kiếm được thực hiện trên máy PC với CPU Intel Core i7-6500U @ 2.50GHz và 8.0GB RAM, sử dụng hệ điều hành Windows 10 Pro 64 bit Bộ dữ liệu imageCLEF, chứa 20,000 ảnh được phân chia thành 276 lớp và lưu trữ trong 41 thư mục (từ thư mục 0 đến thư mục 40), có kích thước 1.64 GB Để đánh giá hiệu quả của phương pháp tìm kiếm ảnh, các giá trị được xem xét bao gồm độ chính xác (precision), độ phủ (recall) và độ đo dung hòa F-measure, với công thức tính toán cụ thể cho từng giá trị.
Trong bài viết này, chúng ta sẽ tìm hiểu về hai khái niệm quan trọng trong việc xử lý hình ảnh: "relavant images" là tập hợp các bức ảnh tương tự với ảnh truy vấn có trong tập dữ liệu, trong khi "retrieved images" là tập hợp các bức ảnh đã được tìm kiếm Độ chính xác, độ phủ và độ do dung hòa của các hình ảnh này được tính toán theo tỷ lệ phần trăm và được quy đổi thành các giá trị cụ thể trong đoạn văn.
Số lượng ảnh tương tự được xác định dựa trên các ảnh đã truy vấn để tính toán giá trị Top K, nhằm đánh giá độ chính xác và độ phủ Dựa trên kết quả truy vấn này, chúng tôi tiến hành đánh giá và so sánh với các công trình nghiên cứu gần đây.
Bằng việc áp dụng công nghệ “C# dotNet Windows Form”, chương trình thực nghiệm gồm các Forms có thể thực hiện các chức năng:
• Tạo cây KNN_R-Tree, xuất cây KNN_R-Tree
• Truy vấn ảnh theo nội dung dựa trên cây KNN_R-TREE
• Thực hiện việc xuất kết quả thực nghiệm theo từng bộ ảnh Một số hình ảnh mô tả quá trình thực thi được trình bày ngay sau đây.
3.5.2 Các giao diện thực nghiệm
Để tạo cây KNN_R-Tree, người dùng cần thiết lập các thông số như bộ ảnh, loại cây và ngưỡng phù hợp Sau khi hoàn tất việc chọn lựa, chỉ cần nhấn nút Start để bắt đầu quá trình tạo cây.
Hình 12 Giao diện đọc dữ liệu các vector từ DataSet và tiền xử lý
Hình 13 Giao diện thêm các vector từ DataSet vào cây KNN_R-Tree
Hình 14 Giao diện tìm kiếm ảnh tương tự dựa trên cây KNN_R-Tree.
Hình 15 Giao diện xuất kết quả thực nghiệm với DataSet
Hình 16 Giao diện kết quả tìm kiếm ảnh tương tự
3.5.3 Phân tích kết quả thực nghiệm
Trong bài viết này, chúng tôi giới thiệu một cải tiến cho thuật toán tạo cây KNN_R-Tree, nhằm mục đích phân cụm dữ liệu và tăng cường số lượng cụm theo bộ dữ liệu Để đạt được điều này, chúng tôi áp dụng các giá trị ngưỡng đo độ tương tự giữa các đối tượng dữ liệu.
Bảng 1 Các giá trị ngưỡng áp dụng cho chương trình thực nghiệm
Ngưỡng đánh giá hiệu quả của phương pháp tìm kiếm ảnh bao gồm các chỉ số quan trọng như độ chính xác (precision), độ phủ (recall) và độ đo dung hòa (F-measure) Những giá trị này giúp xác định mức độ hiệu quả của hệ thống tìm kiếm trong việc cung cấp kết quả phù hợp và đầy đủ.
F-measure Kết quả thực nghiệm được thể hiện như trong Hình 17.
Hình 17 Giá trị trung bình của Precision, Recall, F-measure của tập dữ liệu
Hiệu suất của thuật toán đề xuất trong việc truy vấn được trình bày rõ ràng trong Bảng 1 và Bảng 2 Để đánh giá hiệu quả của hệ thống tìm kiếm ảnh tương tự, chúng tôi đã so sánh kết quả với các nghiên cứu trước đây trên cùng một tập dữ liệu, như được mô tả trong bảng.
Bảng 2 Hiệu suất truy vấn ảnh của phương pháp đề xuất trên tập ảnh ImageCLEF
Bảng 3 Hiệu suất truy vấn ảnh trung bình trên tập ảnh ImageCLEF
Bảng 4 So sánh độ chính xác giữa các phương pháp trên bộ dữ liệu ImageCLEF