SS-tree và similarity search gần đúng cho ảnh

Giới thiệu

Bài này học tìm ảnh giống nhau bằng cây siêu cầu. Dùng để truy xuất ảnh nhanh khi nhiều chiều.

Kiến thức cần nhớ

Vì sao cần SS-tree

• Mỗi ảnh là 1 điểm trong không gian nhiều chiều.
• k-d tree cắt theo trục nên ôm cụm xiên kém.
• Hộp R-tree nhiều góc thừa ở chiều cao lớn.
• Ví dụ đời thường: như hộp vuông đựng bóng tròn phí chỗ.
• Siêu cầu ôm cụm ảnh khít hơn hộp chữ nhật.

Siêu cầu và chèn

• Mỗi nút là 1 cầu gồm tâm và bán kính bao.
• Tâm là trung bình điểm con, bán kính bao hết.
• Chèn chọn cầu nới ít nhất rồi cập nhật ngược lên.
• Ví dụ đời thường: như chọn vòng dây nới ít nhất.
• Nút lưu trung bình và phương sai để tách sau.

Tách xóa và truy vấn

• Tràn thì tách theo chiều phương sai lớn nhất.
• Chọn điểm cắt trên chiều đó sao cho tổng phương sai của hai nửa nhỏ nhất, mỗi nửa đủ số điểm tối thiểu.
• Xóa thì thu cầu, vơi quá thì chèn lại mồ côi.
• Truy vấn xấp xỉ cho dừng sớm để lấy nhanh.
• Nới ngưỡng càng mạnh càng nhanh nhưng dễ sót.

SS+-tree

• Siêu cầu vẫn chồng lên nhau nhiều ở chiều cao, làm truy vấn phải lặn nhiều nhánh.
• SS+-tree cải thiện bằng cách dùng tâm là tâm cầu bao nhỏ nhất (thay cho trung bình), tách nút bằng heuristic tốt hơn (ví dụ gom cụm 2 nhóm), và định kỳ chèn lại để giảm chồng lấn.

Ví dụ

• Input: 6 điểm 2 cụm rõ -> Output: 2 cầu ôm khít hơn 2 hộp.
• Giải thích: cầu tròn ít góc chết nên ít vào nhánh rỗng.

# Kiểm cầu có giao truy vấn không
import math
d = math.dist(tam, diem_hoi)  # khoảng tới tâm
print(d <= ban_kinh + nguong)  # True thì vào nhánh

💻 Bài tập

Ngôn ngữ: C++ (hoặc Python với NumPy). Nộp vào day-119/. Điểm có D chiều (D = 64 cho vector ảnh).

Bài 1: SS-tree

struct SSNode {
  std::vector<float> centroid; float radius;
  bool leaf; std::vector<std::vector<float>> points; std::vector<SSNode*> children;
};
class SSTree {
 public:
  SSTree(int D, int M = 16, int m = 6);
  void insert(const std::vector<float> &p);
  std::vector<int> knn(const std::vector<float> &q, int k) const;   // chính xác
  bool check() const;   // mọi điểm con nằm trong cầu cha
};

10^4 điểm ngẫu nhiên D=8 -> check = true; knn khớp quét tuyến tính trên 1000 truy vấn

Bài 2: Tìm ảnh tương tự

1. Biến 5000 ảnh (CIFAR-10 hoặc thư mục ảnh của bạn) thành vector 64 chiều: histogram màu 4x4x4 chuẩn hóa. (Ngày 140 sẽ dùng CNN.)
2. Nạp vào SS-tree. Với 5 ảnh truy vấn, hiện 8 ảnh gần nhất thành 1 lưới ảnh.
3. So thời gian truy vấn với quét tuyến tính và k-d tree ngày 69.

Bài 3: Tìm kiếm xấp xỉ (nâng cao)

1. Thêm tham số epsilon: bỏ nút khi dist - radius > (khoảng cách thứ k) / (1 + epsilon).
2. Thêm giới hạn số lá được thăm max_leaves.
3. Đo recall@10 (tỉ lệ kết quả trùng với đáp án chính xác) và thời gian với epsilon = 0, 0.1, 0.5, 1 và max_leaves = 5, 20, 100. Vẽ đường recall theo thời gian.

✅ Tiêu chí hoàn thành

• check() đúng và k-NN chính xác khớp quét tuyến tính.
• Có lưới ảnh kết quả cho 5 truy vấn.
• Bảng thời gian 3 cách tìm.
• Đường recall-thời gian của bản xấp xỉ.

❓ Câu hỏi ôn tập

• Siêu cầu gồm gì?
• Chèn chọn nhánh nào?
• Tách nút theo gì?
• Xấp xỉ đánh đổi gì?

🌕 Bạn đã hoàn thành ngày 119. Làm hết bài tập phía trên rồi sang ngày tiếp theo.