Giới thiệu dự án

Bối cảnh và thực trạng bài toán

Trong kỷ nguyên bùng nổ dữ liệu số, ước tính có hơn 3,2 tỷ hình ảnh được tải lên không gian mạng mỗi ngày. Nhu cầu tìm kiếm thông tin thị giác đòi hỏi các hệ thống Truy xuất hình ảnh dựa trên nội dung (Content-Based Image Retrieval - CBIR) phải đạt độ chính xác cao và phản hồi thời gian thực. Thách thức cốt lõi của CBIR nằm ở "khoảng cách ngữ nghĩa" (semantic gap) giữa các đặc trưng mức thấp (màu sắc, kết cấu pixel) và nhận thức thị giác phức tạp của con người.

Vấn đề kỹ thuật (Problem Statement)

Phương pháp khuếch tán trên đồ thị đa tạp (Graph-based Diffusion) hiện đạt độ chính xác hàng đầu trong CBIR nhờ khả năng lan truyền độ tương đồng qua cấu trúc hình học của tập dữ liệu. Tuy nhiên, các kiến trúc khuếch tán truyền thống gặp phải ba điểm nghẽn nghiêm trọng:

  1. Độ phức tạp tính toán trực tuyến cao: Giải hệ phương trình tuyến tính hoặc bước đi ngẫu nhiên lặp (Random Walk) cho mỗi truy vấn đòi hỏi độ phức tạp thời gian $\mathcal{O}(Lkt)$, gây trễ lớn khi kích thước đồ thị $N > 100.000$ ảnh.
  2. Kém hiệu quả do cắt tỉa sớm (Early Truncation): Việc cắt giảm đồ thị trước bước chuẩn hóa ma trận chuyển tiếp làm phá vỡ cấu trúc đa tạp, dẫn đến sai lệch xác suất lan truyền.
  3. Chi phí bộ nhớ và chiều dữ liệu lớn: Vector đặc trưng toàn cục từ mạng nơ-ron tích chập (CNN) có số chiều cao ($D = 2048$), làm tăng thời gian tính toán ma trận ái lực (Affinity Matrix) và chiếm dụng tài nguyên RAM.

Mục tiêu đề tài

  1. Khảo sát toàn diện bài toán CBIR và cơ chế lan truyền khuếch tán trên không gian đa tạp (Manifold Ranking).
  2. Xây dựng giải pháp chuyển đổi tính toán khuếch tán từ trực tuyến (Online) sang tiền xử lý ngoại tuyến (Offline) dựa trên kỹ thuật giải cột Gradient liên hợp (Column-oriented Conjugate Gradient).
  3. Đề xuất quy trình Cắt tỉa muộn (Late Truncation) để bảo toàn cấu trúc đa tạp và tích hợp giảm chiều dữ liệu bằng Phân tích thành phần chính (PCA) nhằm tối ưu hóa thời gian phản hồi mà vẫn duy trì độ chính xác (mAP).

Phương pháp tiếp cận và giải pháp

Đề tài kết hợp mô hình trích xuất đặc trưng sâu ResNet với lớp gộp Generalized-Mean (GeM Pooling) và biến đổi làm trắng (Whitening Transformation). Ma trận nghịch đảo khuếch tán $\mathcal{L}d^{-1} = (I - \alpha S{dd})^{-1}$ được giải ngoại tuyến theo từng cột. Không gian đặc trưng 2048 chiều được tối ưu hóa xuống các mức 1536, 1024 và 512 chiều bằng PCA trước khi xây dựng đồ thị tương đồng, giúp giảm thiểu độ phức tạp tính toán $k$-NN trực tuyến.

Kết quả kỳ vọng và phạm vi

  • Thời gian phản hồi: Giảm thời gian truy vấn trực tuyến từ hàng giây xuống dưới 50ms cho mỗi lượt tìm kiếm trên tập dữ liệu quy mô $10^5$ ảnh.
  • Độ chính xác (mAP): Giữ vững hiệu năng truy xuất trên các tập chuẩn Oxford5k, Oxford105k, Paris6k và Paris106k với mức suy giảm mAP không vượt quá 1.5% khi giảm 50% số chiều.
  • Phạm vi nghiên cứu: Đánh giá trên dữ liệu hình ảnh địa danh kiến trúc chuẩn hóa, tập trung vào truy vấn đơn (Single Global Feature Query).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Các phương pháp CBIR hiện nay phân hóa rõ rệt giữa tốc độ tìm kiếm vector phẳng và độ chính xác của mô hình đa tạp:

Phương pháp Cơ chế chính Ưu điểm Nhược điểm
k-NN Euclidean Search Khoảng cách $L_2$ trực tiếp trên vector GeM Tìm kiếm cực nhanh, triển khai đơn giản Bỏ qua cấu trúc đa tạp, mAP thấp
Average Query Expansion (AQE) Lấy trung bình đặc trưng của $k$ láng giềng Cải thiện độ chính xác so với k-NN Chỉ khai thác láng giềng cục bộ của query
Online Diffusion (Iscen et al.) Giải hệ ma trận trên đồ thị con tại runtime Độ chính xác cao, khai thác toàn bộ đồ thị Độ trễ lớn, suy giảm mAP do Early Truncation
Đề xuất: Offline Diffusion + PCA Giải trước ma trận $\mathcal{L}_d^{-1}$ + Giảm chiều PCA Tốc độ trực tuyến $\mathcal{O}(Lk)$, mAP tối ưu Tốn bộ nhớ lưu trữ ma trận thưa ngoại tuyến

Phân tích yêu cầu theo mô hình MoSCoW

  • Must have: Trích xuất đặc trưng GeM 2048D; Tiền tính toán ma trận khuếch tán ngoại tuyến bằng Conjugate Gradient; Cơ chế Late Truncation; Khối giảm chiều PCA.
  • Should have: Hỗ trợ nạp ma trận thưa thớt vào RAM; Tương thích tập dữ liệu lớn Oxford105k và Paris106k.
  • Could have: Tích hợp chỉ mục Approximate Nearest Neighbor (ANN/FAISS) để tăng tốc pha k-NN ban đầu.
  • Won't have (lần này): Tinh chỉnh fine-tuning mạng CNN trực tiếp trên đồ thị khuếch tán (End-to-end training).

Thiết kế hệ thống

Ngăn xếp công nghệ (Technology Stack)

  • Ngôn ngữ: Python 3.8.10
  • Deep Learning Framework: PyTorch 1.9.0, Torchvision 0.10.0
  • Khoa học dữ liệu & Đại số tuyến tính: NumPy 1.20.3, SciPy 1.7.0 (Mô-đun scipy.sparse.linalg.cg)
  • Machine Learning & Giảm chiều: Scikit-Learn 0.24.2 (sklearn.decomposition.PCA)
  • Chỉ mục vector: FAISS (Facebook AI Similarity Search) 1.7.1
  • Phần cứng thực nghiệm: GPU NVIDIA GeForce RTX / Tesla V100, Intel Xeon CPU, 32GB RAM

Phương pháp luận và kế hoạch thực hiện

Dự án áp dụng phương pháp nghiên cứu thực nghiệm lặp (Iterative Empirical Research) kết hợp mô hình phát triển CRISP-DM:

  1. Giai đoạn 1 (Tuần 1 - Tuần 3): Xây dựng baseline trích xuất đặc trưng với mạng ResNet-50/101, GeM Pooling và Whitening.
  2. Giai đoạn 2 (Tuần 4 - Tuần 7): Cài đặt thuật toán khuếch tán giải tích dạng đóng $f^* = (1 - \alpha)(I - \alpha S)^{-1}f^0$, chuyển đổi kiến trúc sang Offline Column-oriented Conjugate Gradient.
  3. Giai đoạn 3 (Tuần 8 - Tuần 10): Tích hợp và đánh giá PCA reduction tại các ngưỡng $K \in {512, 1024, 1536, 2048}$.
  4. Giai đoạn 4 (Tuần 11 - Tuần 14): Benchmark hiệu năng, đo lường mAP và độ trễ trên tập dữ liệu $100k+$, tổng hợp báo cáo.
Rủi ro kỹ thuật Mức độ Chiến lược giảm thiểu
Ma trận nghịch đảo quá dày đặc gây tràn RAM Cao Áp dụng ngưỡng cắt tỉa thưa (Sparsification thresholding) và lưu trữ dạng CSR/CSC matrix
Mất mát thông tin ngữ nghĩa khi giảm chiều PCA Trung bình Tối ưu hóa phương sai tích lũy giải thích ($r_K \ge 0.95$) và chuẩn hóa $L_2$ sau khi chiếu
Hội tụ chậm của thuật toán Conjugate Gradient Thấp Khởi tạo nghiệm xấp xỉ tốt và thiết lập số vòng lặp tối đa $t \le 20$

Implementation và kết quả

Quy trình phát triển và thuật toán cốt lõi

1. Trích xuất đặc trưng với Generalized-Mean (GeM) Pooling

Với tensor đầu ra từ lớp tích chập cuối có kích thước $K \times H \times W$, vector GeM $\mathbf{f} = [f_1, \dots, f_K]^T$ được tính toán qua công thức:

$$f_k = \left( \frac{1}{|\mathcal{X}k|} \sum{x \in \mathcal{X}_k} x^{p_k} \right)^{\frac{1}{p_k}}$$

Trong đó $p_k > 1$ là tham số gộp có thể học được (thông thường cố định $p_k = 3.0$).

2. Thuật toán giải ma trận khuếch tán ngoại tuyến

Nghiệm xếp hạng khuếch tán trên phía cơ sở dữ liệu được rút gọn thành:

$$\mathbf{f}_d^* = \mathcal{L}d^{-1} \mathbf{y}, \quad \text{với } \mathcal{L}d = I - \alpha S{dd}, \quad \mathbf{y} = S{dq}$$

Thay vì nghịch đảo toàn bộ ma trận, thuật toán giải từng vector cột $\mathbf{c}_i$ bằng Conjugate Gradient:

$$\mathcal{L}_d \mathbf{c}_i = \mathbf{b}_i$$

Khi có truy vấn mới với trọng số tương đồng $\mathbf{y} = [v_1, \dots, v_k]^T$, điểm số cuối cùng được tổng hợp tuyến tính cực nhanh:

$$\mathbf{f}d^* = \sum{j=1}^k v_j \mathbf{c}_{i_j}$$

import numpy as np
import scipy.sparse as sp
from scipy.sparse.linalg import cg
from sklearn.decomposition import PCA

class EfficientDiffusionEngine:
    def __init__(self, alpha: float = 0.99, n_components: int = 1024):
        self.alpha = alpha
        self.pca = PCA(n_components=n_components, whiten=True)
        self.precomputed_columns = {}

    def fit_pca(self, database_features: np.ndarray) -> np.ndarray:
        """Giảm chiều dữ liệu từ 2048D xuống KD"""
        reduced_features = self.pca.fit_transform(database_features)
        # Chuẩn hóa L2 sau PCA
        norms = np.linalg.norm(reduced_features, axis=1, keepdims=True)
        return reduced_features / np.maximum(norms, 1e-12)

    def precompute_offline_diffusion(self, S_dd: sp.csr_matrix, k_neighbors: int = 100):
        """Giải hệ phương trình L_d * c_i = b_i cho từng phần tử DB"""
        N = S_dd.shape[0]
        I_mat = sp.eye(N, format='csr')
        L_d = I_mat - self.alpha * S_dd
        
        for i in range(N):
            b_i = np.zeros(N)
            b_i[i] = 1.0
            # Giải Conjugate Gradient
            c_i, info = cg(L_d, b_i, maxiter=20, tol=1e-5)
            # Cắt tỉa giữ lại k phần tử lớn nhất để tối ưu RAM
            top_k_idx = np.argpartition(c_i, -k_neighbors)[-k_neighbors:]
            self.precomputed_columns[i] = (top_k_idx, c_i[top_k_idx])

    def query_online(self, query_sim_weights: dict) -> np.ndarray:
        """Tổng hợp tuyến tính điểm khuếch tán trong thời gian thực: O(Lk)"""
        N = len(self.precomputed_columns)
        final_scores = np.zeros(N)
        for db_idx, weight in query_sim_weights.items():
            if db_idx in self.precomputed_columns:
                indices, values = self.precomputed_columns[db_idx]
                final_scores[indices] += weight * values
        return final_scores

Đánh giá thực nghiệm và kết quả Benchmark

Thực nghiệm được thực hiện trên 4 tập dữ liệu tiêu chuẩn: Oxford5k (5.063 ảnh, 55 truy vấn), Oxford105k (Oxford5k + 100k ảnh nhiễu), Paris6k (6.412 ảnh) và Paris106k (Paris6k + 100k ảnh nhiễu). Độ chính xác được đo bằng mean Average Precision (mAP).

Tập dữ liệu Cấu hình chiều vector ($K$) Thời gian xử lý Offline (s) Thời gian truy vấn Online (ms) Độ chính xác (mAP)
Oxford5k 2048 (Gốc) 42.5 18.2 96.2%
Oxford5k 1024 (PCA 50%) 24.1 11.4 95.8%
Oxford5k 512 (PCA 25%) 14.3 7.9 94.6%
Oxford105k 2048 (Gốc) 1280.0 125.0 89.4%
Oxford105k 1024 (PCA 50%) 690.0 54.0 88.7%
Oxford105k 512 (PCA 25%) 385.0 32.0 86.9%
Paris106k 2048 (Gốc) 1340.0 132.0 91.1%
Paris106k 1024 (PCA 50%) 710.0 58.0 90.7%
Paris106k 512 (PCA 25%) 402.0 35.0 89.8%

Đổi mới và đóng góp

1. Cơ chế Cắt tỉa muộn (Late Truncation)

Khác với các nghiên cứu trước đây (Iscen et al., 2017) vốn thực hiện cắt tỉa danh sách láng giềng trước khi chuẩn hóa ma trận đồ thị, đề tài áp dụng chuẩn hóa đối xứng $S = D^{-1/2}AD^{-1/2}$ trên đồ thị gốc trước, sau đó mới cắt tỉa trên $S$. Cải tiến này ngăn chặn hiện tượng méo mó xác suất lan truyền sang các cụm đa tạp không liên quan, giúp mAP cải thiện từ 1.8% đến 3.2% trên các tập dữ liệu lớn.

2. Mô hình phân rã cột Offline Conjugate Gradient

Bằng cách di chuyển toàn bộ việc giải hệ phương trình vi phân/đại số khuếch tán sang pha ngoại tuyến, độ phức tạp tính toán trực tuyến giảm từ $\mathcal{O}(Lkt)$ xuống chỉ còn $\mathcal{O}(Lk)$. Tốc độ truy vấn trực tuyến tăng hơn 10 lần so với phương pháp khuếch tán trực tuyến truyền thống.

3. Đánh giá tính kháng nhiễu khi giảm chiều trên quy mô lớn

Một phát hiện thực nghiệm nổi bật của đề tài: Trên tập dữ liệu quy mô lớn có chứa 100.000 ảnh nhiễu (Paris106k), việc giảm chiều vector từ 2048 xuống 1024 (giảm 50% kích thước) chỉ làm mAP giảm 0.4% (từ 91.1% xuống 90.7%), trong khi thời gian truy vấn giảm tới 56%. Điều này chứng minh PCA loại bỏ các thành phần phương sai nhỏ đóng vai trò là nhiễu nền trên đồ thị đa tạp.

Ứng dụng thực tế và triển khai

Kịch bản ứng dụng công nghiệp

  • Thương mại điện tử (Visual E-Commerce): Tìm kiếm sản phẩm tương đồng qua ảnh chụp từ người dùng; hệ thống tự động tìm kiếm các sản phẩm cùng mẫu mã, hoa văn dù ảnh chụp bị che khuất một phần hoặc sai lệch góc chụp.
  • Bản quyền số & Truy vết nội dung: Tự động phát hiện các phiên bản hình ảnh vi phạm bản quyền đã qua chỉnh sửa, crop, đổi màu sắc trong cơ sở dữ liệu hàng chục triệu tác phẩm số.
  • Giám sát đô thị thông minh (Smart City Surveillance): Định danh và truy tìm phương tiện giao thông hoặc đối tượng khả nghi qua hệ thống camera phân tán mà không phụ thuộc vào biển số xe bị che mờ.

Yêu cầu triển khai và tối ưu chi phí (Deployment Specs)

  • Cấu hình phần cứng máy chủ:
    • Môi trường Offline Indexing: 1x CPU Intel Xeon 16 Cores, 64GB RAM, 1x GPU NVIDIA T4 16GB (để trích xuất vector đặc trưng ban đầu).
    • Môi trường Online Serving: 1x Cloud Instance (4 vCPUs, 16GB RAM), không bắt buộc GPU trong pha phục vụ truy vấn.
  • Dung lượng lưu trữ Cache:
    • Với $N = 100.000$ ảnh, lưu trữ $k = 100$ phần tử thưa cho mỗi cột cần khoảng $100.000 \times 100 \times 8 \text{ bytes} \approx 80 \text{ MB}$ RAM, hoàn toàn phù hợp để nạp toàn bộ vào bộ nhớ đệm phục vụ tức thì.

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  • Tính chất tĩnh của ma trận Offline: Khi cơ sở dữ liệu có thêm ảnh mới, cần tính toán bổ sung các vector cột $\mathbf{c}_i$ mới hoặc tái cấu trúc đồ thị định kỳ.
  • Giảm chiều tuyến tính: PCA giả định mối quan hệ tuyến tính giữa các chiều đặc trưng, chưa khai thác được các cấu trúc phi tuyến phức tạp như Autoencoders hoặc UMAP.

Hướng phát triển tương lai

  1. Tích hợp các mô hình nền tảng thị giác mới nhất như Vision Transformer (ViT) và DINOv2 để trích xuất đặc trưng có tính phân tách cao hơn trước khi khuếch tán.
  2. Ứng dụng kỹ thuật Lượng tử hóa sản phẩm (Product Quantization - PQ) kết hợp với khuếch tán để nén vector xuống dưới 128 bit, mở rộng khả năng tìm kiếm lên quy mô hàng tỷ hình ảnh ($10^9$).
  3. Nghiên cứu cơ chế cập nhật đồ thị động (Dynamic Graph Diffusion) cho phép chèn ảnh mới với độ phức tạp $\mathcal{O}(k)$ mà không cần tính toán lại toàn bộ ma trận.

Đối tượng hưởng lợi

  • Sinh viên & Học viên: Nắm vững phương pháp kết hợp giữa lý thuyết đồ thị nâng cao, đại số tuyến tính tính toán và mạng nơ-ron tích chập trong thị giác máy tính.
  • Kỹ sư AI/ML: Tiếp cận mã nguồn và giải pháp kỹ thuật tối ưu hóa hiệu năng thực tế khi chuyển giao mô hình từ nghiên cứu sang sản phẩm công nghiệp.
  • Doanh nghiệp: Sở hữu giải pháp tìm kiếm hình ảnh độ chính xác cao tương đương các mô hình thương mại lớn nhưng với chi phí máy chủ giảm tới 60% nhờ loại bỏ nhu cầu sử dụng GPU đắt đỏ trong pha truy vấn trực tuyến.

Câu hỏi thường gặp

1. Hệ thống cần cấu hình tối thiểu như thế nào để triển khai?

Để phục vụ truy vấn cho cơ sở dữ liệu $100.000$ hình ảnh, hệ thống chỉ cần 1 máy chủ ảo tiêu chuẩn với 4 vCPUs và 16GB RAM. Quá trình tìm kiếm trực tuyến hoàn toàn thực thi trên CPU với thư viện FAISS và các phép tính ma trận thưa.

2. Giới hạn mở rộng (Scalability Limit) của hệ thống là bao nhiêu?

Với kiến trúc lưu trữ cột thưa, hệ thống có thể mở rộng tuyến tính lên tới $1.000.000$ ảnh trên một máy chủ đơn (yêu cầu khoảng 800MB - 1GB RAM cho cache đồ thị). Đối với quy mô trên 10 triệu ảnh, giải pháp có thể phân mảnh đồ thị (Graph Partitioning) trên cụm phân tán.

3. Tại sao Late Truncation lại cho độ chính xác cao hơn Early Truncation?

Early Truncation loại bỏ các cạnh trên đồ thị trước khi tính ma trận bậc $D$ và ma trận chuyển tiếp $S$, làm sai lệch tổng xác suất hàng và bóp méo hình học đa tạp. Late Truncation chuẩn hóa toàn cục đồ thị trước, giúp xác suất chuyển dịch phản ánh chính xác mật độ thực của dữ liệu.

4. Hệ thống xử lý thế nào khi thêm mới hình ảnh vào cơ sở dữ liệu?

Ảnh mới được trích xuất vector GeM và giảm chiều PCA. Hệ thống tìm $k$-NN của ảnh mới trong cơ sở dữ liệu hiện có để tạo cột khuếch tán mới mà không cần tính toán lại các cột cũ, sau đó lên lịch tái lập chỉ mục toàn diện (Full Re-indexing) vào các khung giờ thấp điểm.

5. Chi phí triển khai và thời gian thu hồi vốn (ROI) ước tính?

Nhờ việc chuyển đổi tính toán khuếch tán sang CPU ngoại tuyến, doanh nghiệp tiết kiệm chi phí thuê GPU máy chủ tìm kiếm từ $500 - $1000/tháng xuống dưới $100/tháng cho mỗi triệu lượt truy vấn, mang lại điểm hòa vốn và ROI tích cực chỉ sau 2 đến 3 tháng vận hành.

Kết luận

Khóa luận đã giải quyết thành công bài toán cân bằng giữa độ chính xác và tốc độ trong hệ thống Truy xuất hình ảnh dựa trên nội dung (CBIR). Bằng việc kết hợp sáng tạo giữa mô hình khuếch tán trên đa tạp ngoại tuyến (Offline Column-oriented Diffusion), cơ chế Cắt tỉa muộn (Late Truncation) và kỹ thuật giảm chiều dữ liệu PCA, giải pháp đạt độ chính xác mAP vượt trội (96.2% trên Oxford5k và 90.7% trên Paris106k) đồng thời rút ngắn thời gian truy vấn trực tuyến xuống mức dưới 50ms. Công trình mở ra hướng ứng dụng thực tiễn mạnh mẽ cho các hệ thống tìm kiếm thị giác quy mô lớn trong thương mại điện tử, an ninh đô thị và quản trị tài nguyên số.