PHÂN LỚP HÌNH ẢNH DỰA TRÊN CẤU TRÚC KD-TREE

Nguyễn Thị Định và CS. Tập 131, Số 2A, 2022 112 Thuật toán 2 được thực hiện lần lượt các bước (1) đến (10) gồm: (1) Tạo KD-Tree độ phức tạp O(N), trong đó N là số phần tử tham gia tạo KD-Tree (2) Số nút lá kh cần gán nhãn, độ phức tạp là O(kh) (3) Duyệt trên từng vector, độ phức tạp là O(N) (4) Trong trường hợp xấu nhất, tất cả vector đều sai so với gán nhãn ban đầu, phải duyệt qua tất cả các vector từ nút lá trở về gốc (chiều cao h) nên số phép toán là h × N (5) Trong trường hợp xấu nhất, phải duyệt qua tất cả các vector từ nút lá trở về gốc nên số phép toán là h × N (6) Trong trường hợp xấu nhất, vị trí Nodei sai là nút gốc, nên số phép toán là h × N (7) Trong trường hợp xấu nhất, cần điều chỉnh hết các vector trọng số thì số phép toán là: 1 0 1 1 1 T ( ... ) * ( ) * ( ) *( 1) O(k ) 1 1 h n h h k n k k k n n k k k + + − = + + + = = −  − − (8) Lặp lại bước (1), độ phức tạp O(N) (9) Lặp lại bước (2), độ phức tạp là O(kh) (10) Lặp lại bước (3), độ phức tạp là O(N) Số phép toán sau một quá trình là: (N * * * N ) (3h 4)* N 2 k (k )h h h h k N h N h N h N T k N T O + + + + + + + + + = + + +  Vì vậy, độ phức tạp của thuật toán 2 là: ( )h O k Trong thực nghiệm, bộ ảnh Caltech256 có số phân lớp nhiều nhất là 257 nên chọn k = 5 và h = 4 tức là có thể tạo ra 625 phân lớp; điều này là khả thi. Sau khi huấn luyện, tập véc-tơ phân lớp trên KD-Tree cho mỗi bộ ảnh thực nghiệm là khác nhau. Hình 3 minh họa tập véc-tơ phân lớp cho bộ ảnh COREL sau khi đã huấn luyện để hiệu suất phân lớp đạt 0,8672 trên KD-Tree với chiều cao bằng 2 và số nhánh bằng 4.

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