Bối cảnh và vấn đề nghiên cứu

Sự phát triển của công nghệ ảnh số và internet đã dẫn tới sự gia tăng nhanh chóng của lượng dữ liệu hình ảnh lưu trữ trên mạng toàn cầu. Theo số liệu thống kê được tác giả trích dẫn vào thời điểm thực hiện nghiên cứu (cuối năm 2008), số lượng ảnh lưu trữ đã đạt tới 10 tỷ ảnh trên Facebook (tháng 10/2008), 3 tỷ ảnh trên Flickr (tháng 11/2008) và 6,2 tỷ ảnh trên Photobucket (tháng 10/2008). Nhu cầu tìm kiếm ảnh của người dùng trở nên cấp thiết, dẫn đến sự ra đời của các công cụ tìm kiếm ảnh thương mại dựa trên văn bản đi kèm (Text-Based Image Retrieval) như Yahoo, MSN, Google Image Search.

Tuy nhiên, phương pháp tìm kiếm dựa trên siêu dữ liệu (metadata) như tiêu đề (title), thẻ phân loại (tags), bình luận (comment) bộc lộ hạn chế lớn:

  • Xảy ra hiện tượng nhập nhằng ngữ nghĩa giữa nội dung truy vấn và nội dung hình ảnh thực tế (ví dụ: truy vấn từ khóa "Apple" khiến máy tìm kiếm trả về biểu trưng của hãng công nghệ Apple thay vì hình ảnh quả táo).
  • Nhiều tập ảnh cá nhân không có thẻ mô tả hoặc văn bản đi kèm, trong khi chi phí gán nhãn thủ công rất tốn kém.

Nhằm giải quyết các nhược điểm này, hướng tiếp cận tìm kiếm ảnh theo nội dung (Content-Based Image Retrieval - CBIR) đã được phát triển, phân tích trực tiếp các đặc trưng thị giác bên trong bức ảnh (màu sắc, kết cấu, hình dạng, điểm đặc trưng cục bộ). Trong bối cảnh đó, khóa luận tập trung giải quyết bài toán tìm kiếm ảnh sản phẩm dựa trên ảnh mẫu (example-based image search).

Mục tiêu và nhiệm vụ nghiên cứu của khóa luận gồm 4 nội dung cụ thể:

  1. Khảo sát, phân tích tổng quan các phương pháp biểu diễn, trích chọn đặc trưng thị giác của ảnh (màu sắc, kết cấu, hình dạng và đặc trưng cục bộ bất biến).
  2. Nghiên cứu các độ đo tương đồng không gian vector và các phương pháp xếp hạng ảnh theo nội dung đã được công bố trên thế giới.
  3. Xây dựng mô hình tìm kiếm $k$ láng giềng gần nhất kết hợp kỹ thuật lượng tử hóa tích (Product Quantization) với tính toán khoảng cách bất đối xứng (ADC) và độ đo khoảng cách Ơclit trên tập vector đặc trưng SIFT.
  4. Tiến hành cài đặt thực nghiệm, đánh giá độ chính xác của mô hình trên tập dữ liệu ảnh sản phẩm thu thập từ Google Product Search và Flickr.

Đối tượng và phạm vi nghiên cứu:

  • Đối tượng nghiên cứu: Các thuật toán trích chọn đặc trưng ảnh (trọng tâm là đặc trưng cục bộ bất biến SIFT), các kỹ thuật lượng tử hóa vector và độ đo khoảng cách trong không gian nhiều chiều.
  • Phạm vi dữ liệu: Tập dữ liệu ảnh sản phẩm thu thập từ Google Product Search và bổ sung ảnh nhiễu từ Flickr, thử nghiệm với 10 câu truy vấn ảnh cụ thể ở mức trả về $k=10$ kết quả tương đồng nhất.

Cơ sở lý thuyết và phương pháp

Khóa luận xây dựng trên các nền tảng lý thuyết thị giác máy tính, xử lý ảnh và thu nhận thông tin (Information Retrieval):

Khung lý thuyết và các mô hình biểu diễn đặc trưng

  • Khái niệm CBIR/QBIC: Thuật ngữ do T. Kato đưa ra năm 1992 về việc tự động thu thập và truy xuất ảnh dựa trên màu sắc và hình dạng.
  • Đặc trưng màu sắc: Biểu diễn trong các không gian màu RGB, HSI, Munsell, CIE. Lược đồ màu RGB $h_{R,G,B}(r,g,b) = N \cdot \text{Prob}(R=r, G=g, B=b)$ được dùng làm bước lọc sơ bộ. Các độ đo tương đồng tương ứng gồm khoảng cách Ơclit (Euclidean distance) và độ phân kỳ Jensen-Shannon (Jensen-Shannon divergence - JSD).
  • Đặc trưng kết cấu (Texture): Phân bố không gian của các mức xám trong láng giềng qua các mô hình biến đổi sóng Gabor (Gabor Wavelet transform), biến đổi đường viền (Contourlet transform), kim tự tháp lái được (Steerable pyramid), ma trận đồng hiện (Co-occurrence matrix) và hệ thống bộ lọc định hướng phức tạp.
  • Đặc trưng hình dạng (Shape): Biểu diễn theo đường biên (contour-based) hoặc theo vùng (region-based), tính toán cạnh qua trường vector Gradient (Gradient Vector Flow - GVF).
  • Đặc trưng cục bộ bất biến SIFT (Scale-Invariant Feature Transform): Do David Lowe đề xuất, gồm 4 bước:
    1. Phát hiện cực trị trong không gian tỉ lệ (Scale-Space extrema detection) sử dụng hàm sai phân Gaussian (Difference of Gaussian - DoG): $$D(x, y, \sigma) = (G(x, y, k\sigma) - G(x, y, \sigma)) * I(x, y) = L(x, y, k\sigma) - L(x, y, \sigma)$$ So sánh mỗi điểm ảnh với 26 điểm láng giềng (8 điểm cùng tỉ lệ, 18 điểm ở hai tỉ lệ liền kề).
    2. Định vị điểm hấp dẫn (Keypoint localization): Loại bỏ điểm có độ tương phản thấp và điểm dọc theo cạnh không ổn định.
    3. Xác định hướng (Orientation assignment): Tính biểu đồ hướng Gradient trong vùng láng giềng theo độ lớn $m(x,y)$ và góc hướng $\theta(x,y)$.
    4. Biểu diễn vector đặc trưng (Keypoint descriptor): Tạo vector đặc trưng 128 chiều ($4 \times 4 \times 8$).

Phương pháp tìm kiếm láng giềng gần nhất bằng lượng tử hóa tích

Khóa luận tiếp cận mô hình của Hervé Jégou và cộng sự (2010):

  • Lượng tử hóa vector (Vector Quantization): Ánh xạ vector $x \in \mathbb{R}^D$ thành $q(x) \in \mathcal{C} = {c_i; i \in I}$ với điều kiện tối ưu Lloyd (phân cụm K-Means).
  • Lượng tử hóa tích (Product Quantization - PQ): Chia vector $D$ chiều thành $m$ vector con $D^* = D/m$ chiều. Mỗi vector con được lượng tử hóa độc lập qua bộ lượng tử hóa thấp $q_j$, tạo ra không gian codebook tích $\mathcal{C} = \mathcal{C}_1 \times \mathcal{C}_2 \times \dots \times \mathcal{C}_m$ với số lượng trọng tâm $k = (k^*)^m$.
  • Tính toán khoảng cách bất đối xứng (Asymmetric Distance Computation - ADC): Vector truy vấn $x$ được giữ nguyên không lượng tử hóa, vector cơ sở dữ liệu $y$ được biểu diễn bằng mã lượng tử $q(y)$: $$d(x, y) \approx d(x, q(y)) = \sqrt{\sum_{j=1}^m d(u_j(x), q_j(u_j(y)))^2}$$
  • Chỉ mục ngược bất đối xứng (IVFADC): Kết hợp lượng tử hóa thô $q_c$ tạo danh sách chỉ mục ngược và lượng tử hóa tích trên vector dư $r(x) = x - q_c(x)$ để tăng tốc độ tìm kiếm không toàn bộ (non-exhaustive search).

Thiết kế và triển khai mô hình tìm kiếm ảnh sản phẩm

Hệ thống tìm kiếm ảnh sản phẩm được thiết kế theo quy trình xử lý hai giai đoạn, kết hợp giữa tốc độ lọc của lượng tử hóa tích và độ chính xác của khoảng cách Ơclit trên vector SIFT:

Giai đoạn Nhiệm vụ chính Phương pháp / Giải thuật Đầu vào Đầu ra
Giai đoạn 1 Trích chọn đặc trưng và lọc thô ứng viên Trích xuất vector SIFT 128 chiều; Lượng tử hóa tích (PQ) kết hợp khoảng cách bất đối xứng (ADC) Ảnh truy vấn và cơ sở dữ liệu ảnh gốc Top $N$ ($N=20$) ảnh tương đồng nhất
Giai đoạn 2 Tái xếp hạng chính xác $k$ láng giềng Tính khoảng cách Ơclit trực tiếp giữa các vector đặc trưng SIFT của ảnh truy vấn và ứng viên $N$ ảnh ứng viên từ Giai đoạn 1 Top $k$ ($k=10$) ảnh tương đồng nhất

Môi trường và công cụ triển khai

  • Cấu hình phần cứng: CPU Intel Pentium IV 3.06 GHz, RAM 1 GB, ổ cứng ngoài 80 GB, hệ điều hành Windows XP Service Pack 2.
  • Môi trường phần mềm: Matlab R2009b.
  • Thư viện mã nguồn mở:
    • SiftDemoV4 (tác giả David Lowe): Trích chọn điểm hấp dẫn và sinh vector đặc trưng SIFT 128 chiều.
    • Pqsearch_matlab và Kmeans_fast.tar (tác giả Hervé Jégou, Matthijs Douze): Phân cụm K-Means nhanh và lượng tử hóa tích.
    • FlickrSearcher (tác giả Nguyễn Cẩm Tú): Thu thập tập dữ liệu ảnh từ dịch vụ chia sẻ ảnh Flickr.
  • Các module tự phát triển trên Matlab:
    • Similar_Euclide.m: Tính toán ma trận khoảng cách Ơclit giữa các tập vector đặc trưng SIFT.
    • Pq_test.m: Module điều khiển trung tâm, tích hợp trích chọn đặc trưng, lượng tử hóa ADC và trả về danh sách $k$ ảnh kết quả.

Quy trình xây dựng dữ liệu

  • Tập huấn luyện (Training Set): Gồm 20 ảnh sản phẩm thu thập từ Google Product Search dùng để học các tham số codebook cho bộ lượng tử hóa tích.
  • Cơ sở dữ liệu thực nghiệm: Với mỗi câu truy vấn, xây dựng tập cơ sở dữ liệu gồm 30 ảnh (kết hợp giữa ảnh sản phẩm chuẩn từ Google Product Search và ảnh gây nhiễu thu thập từ Flickr qua từ khóa tương ứng).
  • Tập truy vấn: 10 ảnh sản phẩm đầu vào được chọn lọc nhằm kiểm tra khả năng phân tách trong các trường hợp có sự nhập nhằng ngữ nghĩa.

Nội dung chính theo từng chương

Chương 1: Khái quát về trích chọn đặc trưng ảnh và tìm kiếm theo đặc trưng ảnh

Chương mở đầu phân tích sự bùng nổ dữ liệu ảnh số trên các nền tảng trực tuyến và đối chiếu hai hướng tiếp cận tìm kiếm ảnh chính: tìm kiếm theo văn bản đi kèm và tìm kiếm theo nội dung ảnh (CBIR). Tác giả chỉ ra nhược điểm cốt lõi của tìm kiếm bằng văn bản qua ví dụ truy vấn "Apple" (trả về logo hãng máy tính thay vì quả táo) và "d-80" (máy ảnh Nikon). Chương này cũng giới thiệu các hệ thống tìm kiếm ảnh nội dung thực nghiệm và thương mại đương thời như Google Image Swirl (phân cụm trực quan ngữ nghĩa trên 200.000 truy vấn), Tiltomo (tìm kiếm dựa trên chủ đề, màu sắc, kết cấu từ dữ liệu Flickr) và Byo Image Search (tìm kiếm theo màu sắc tải lên).

Chương 2: Các phương pháp lựa chọn đặc trưng và độ đo tương đồng giữa các ảnh

Chương 2 trình bày chi tiết toán học và giải thuật trích chọn 4 nhóm đặc trưng thị giác:

  • Đặc trưng màu sắc: Lược đồ màu RGB, các độ đo khoảng cách Ơclit và phân kỳ Jensen-Shannon (JSD).
  • Đặc trưng kết cấu: Định nghĩa texel, các phép biến đổi Gabor Wavelet, Contourlet, Steerable pyramid và ma trận đồng hiện.
  • Đặc trưng hình dạng: Biểu diễn biên và biểu diễn vùng; giải thuật trích xuất biên qua Gradient Vector Flow (GVF).
  • Đặc trưng cục bộ bất biến SIFT: Quy trình toán học 4 bước từ lọc DoG trên các Octave, định vị điểm cực trị, khử điểm biên và điểm tương phản thấp, gán hướng gradient tới việc tạo vector 128 chiều.
  • Phương pháp lựa chọn đặc trưng: Đánh giá hai mô hình Filter và Wrapper; so sánh các kỹ thuật phân tích biệt thức (DA, MDA, BDA), BiasMap, SMMS và phương pháp Boosting (Wei Jian & Guihua Er).

Chương 3: Một số phương pháp tìm kiếm ảnh theo nội dung

Chương 3 tổng thuật các công trình nghiên cứu tiêu biểu liên quan đến tìm kiếm và xếp hạng ảnh:

  • Hệ thống PageRank cho ảnh sản phẩm của Yushi Jing và cộng sự: Xây dựng đồ thị liên kết trực quan (visual hyperlinks) dựa trên đặc trưng SIFT và áp dụng thuật toán ImageRank với hệ số hãm $d > 0$. Thực nghiệm trên 2.000 truy vấn sản phẩm cho thấy tỷ lệ ảnh không phù hợp ở top 10 giảm từ 2,82 (Google) xuống 0,47.
  • CueFlik của James Fogarty và cộng sự: Cho phép người dùng định nghĩa quy tắc (rules) tương tác từ tập mẫu tích cực và tiêu cực để xếp hạng lại 1.000 ảnh từ Microsoft Live Search.
  • Phương pháp kết hợp màu sắc, kết cấu và hình dạng của Hiremath & Jagadeesh Pujari: Chia ảnh thành 24 ô vuông không chồng lặp ($4 \times 6$ hoặc $6 \times 4$), đối sánh đồ thị hai phía (bipartite graph) kết hợp cạnh GVF.
  • Phương pháp sử dụng phân vùng ảnh làm mẫu truy vấn của Awang Iskandar James và cộng sự trên tập truyện tranh Groat (30 phân vùng).

Chương 4: Mô hình k láng giềng gần nhất sử dụng bộ lượng tử hóa

Chương 4 thiết lập cơ sở toán học cho bài toán tìm kiếm $k$-NN trong không gian đa chiều. Tác giả phân tích chi tiết kỹ thuật lượng tử hóa tích (Product Quantization) của Hervé Jégou, so sánh hai cơ chế tính toán khoảng cách đối xứng (SDC) và bất đối xứng (ADC), đồng thời mô tả cấu trúc danh sách chỉ mục ngược IVFADC. Trên cơ sở đó, tác giả đề xuất mô hình tìm kiếm hai giai đoạn: Giai đoạn 1 sử dụng vector đặc trưng SIFT 128 chiều kết hợp PQ-ADC để lọc ra $N=20$ ảnh ứng viên gần nhất; Giai đoạn 2 tính toán khoảng cách Ơclit chính xác trên tập vector SIFT để xác định thứ hạng của $k=10$ ảnh đầu ra.

Chương 5: Thực nghiệm và đánh giá

Chương 5 mô tả chi tiết quá trình cài đặt hệ thống trên môi trường Matlab R2009b, cấu hình phần cứng, các thư viện ngoài và cấu trúc tập dữ liệu kiểm thử. Tác giả thiết lập phương pháp đánh giá định lượng sử dụng độ chính xác trung bình (Average Precision - AP) và độ chính xác trung bình tổng thể (Mean Average Precision - MAP). Kết quả thực nghiệm trên 10 truy vấn sản phẩm được thống kê chi tiết, phân tích độ chính xác ở các mức xếp hạng $P@k$ và minh họa kết quả truy vấn thực tế với sản phẩm "Iphone" và "Apple".

Kết quả và đóng góp

Kết quả định lượng từ thực nghiệm

Hiệu năng của hệ thống được đánh giá thông qua chỉ số độ chính xác trung bình (AP) trên 10 kết quả trả về đầu tiên ($k=10$) cho 10 truy vấn sản phẩm thử nghiệm:

  • Chỉ số độ chính xác trung bình tổng thể đạt: $\text{MAP} = 80,4%$ ($0,804$).
  • Độ chính xác ở vị trí đầu tiên ($P@1$) đạt mức tối đa ($1,0$) trên phần lớn các truy vấn.
  • Đối với 10 truy vấn thực nghiệm, có 8/10 truy vấn trả về kết quả ở vị trí số 1 là bức ảnh hoàn toàn trùng khớp với ảnh mẫu truy vấn đầu vào.
  • Với các truy vấn có tính nhập nhằng cao như "Apple" hoặc truy vấn sản phẩm công nghệ "Iphone", hệ thống đã loại bỏ được các ảnh nhiễu không liên quan từ Flickr và trả về đúng nhóm sản phẩm mục tiêu trong top 10 kết quả.

Đóng góp của khóa luận

  1. Hệ thống hóa lý thuyết: Tổng hợp có hệ thống các phương pháp biểu diễn đặc trưng thị giác từ toàn cục (màu sắc, kết cấu) đến cục bộ bất biến (SIFT), phân tích các giải thuật lượng tử hóa vector và độ đo khoảng cách đa chiều.
  2. Đề xuất mô hình kết hợp thực nghiệm: Tích hợp thành công kỹ thuật trích chọn đặc trưng SIFT 128 chiều với cơ chế lượng tử hóa tích tính khoảng cách bất đối xứng (PQ-ADC) và tái xếp hạng bằng khoảng cách Ơclit.
  3. Cài đặt và kiểm chứng ứng dụng: Xây dựng thành công quy trình thử nghiệm trên Matlab, chứng minh tính khả thi của việc ứng dụng đặc trưng cục bộ bất biến vào bài toán tìm kiếm ảnh sản phẩm thương mại khi có sự xuất hiện của ảnh nhiễu.

Hạn chế và hướng nghiên cứu tiếp

Khóa luận ghi nhận các hạn chế và định hướng phát triển dựa trên nội dung thực nghiệm đã triển khai:

  • Quy mô tập dữ liệu: Thực nghiệm mới được tiến hành trên tập dữ liệu nhỏ (30 ảnh cho mỗi truy vấn, 10 truy vấn thử nghiệm và 20 ảnh huấn luyện codebook). Cần mở rộng thử nghiệm trên các tập dữ liệu ảnh quy mô lớn hàng triệu ảnh để đánh giá toàn diện năng lực hệ thống.
  • Cấu trúc chỉ mục: Thực nghiệm hiện tại chủ yếu sử dụng phương pháp tính toán khoảng cách bất đối xứng ADC trực tiếp; chưa triển khai đầy đủ cấu trúc chỉ mục ngược IVFADC trên không gian dữ liệu phân tán để tối ưu hóa triệt để thời gian đáp ứng.
  • Kết hợp đa đặc trưng: Hệ thống hiện chỉ sử dụng đơn lẻ đặc trưng cục bộ SIFT. Hướng nghiên cứu tiếp theo có thể kết hợp SIFT với các đặc trưng toàn cục (màu sắc, kết cấu) hoặc bổ sung thông tin ngữ cảnh văn bản nhằm tăng cường độ chính xác khi đối sánh các sản phẩm có bề mặt ít góc cạnh.

Giá trị tham khảo

Khóa luận là tài liệu tham khảo cho sinh viên, học viên cao học và các nhà nghiên cứu thuộc các chuyên ngành Công nghệ Thông tin, Khoa học Máy tính, Thị giác Máy tính và Xử lý Ảnh:

  • Tham khảo thuật toán SIFT: Phần trình bày chi tiết về giải thuật trích chọn đặc trưng cục bộ SIFT qua không gian tỉ lệ DoG (Mục 2.6) cung cấp đầy đủ công thức toán học và quy trình xử lý điểm hấp dẫn.
  • Nghiên cứu kỹ thuật Lượng tử hóa tích: Chương 4 là tài liệu phân tích cụ thể về phương pháp Product Quantization (PQ), phân định rõ cơ chế tính toán đối xứng (SDC) và bất đối xứng (ADC) phục vụ bài toán tìm kiếm láng giềng gần nhất đa chiều.
  • Kỹ thuật thực nghiệm Matlab: Quy trình kết hợp các bộ công cụ mã nguồn mở (SiftDemoV4, pqsearch_matlab) với các đoạn mã tự xây dựng (Similar_Euclide.m, Pq_test.m) cung cấp khung mẫu thực nghiệm hữu ích cho các đồ án xử lý ảnh tương tự.

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

1. Tại sao khóa luận lựa chọn đặc trưng cục bộ bất biến SIFT thay vì các đặc trưng màu sắc hay kết cấu toàn cục?
Đặc trưng màu sắc và kết cấu mang tính toàn cục, dễ bị ảnh hưởng bởi sự thay đổi góc chụp, ánh sáng và không phân biệt được các chi tiết cục bộ của sản phẩm. Đặc trưng SIFT biểu diễn các điểm hấp dẫn dưới dạng vector 128 chiều có khả năng bất biến đối với phép co giãn tỉ lệ, phép quay, thay đổi góc nhìn, thay đổi cường độ chiếu sáng và khả năng chống nhiễu ảnh cao, rất phù hợp cho việc nhận dạng sản phẩm.

2. Kỹ thuật lượng tử hóa tích (Product Quantization - PQ) giải quyết vấn đề gì trong mô hình?
Trong tìm kiếm ảnh, việc tính toán khoảng cách Ơclit trực tiếp trên hàng ngàn vector SIFT 128 chiều đòi hỏi chi phí tính toán và bộ nhớ rất lớn. PQ chia vector 128 chiều thành $m$ vector con chiều thấp và lượng tử hóa riêng biệt. Nhờ đó, hệ thống có thể xấp xỉ khoảng cách nhanh chóng thông qua phương pháp tính khoảng cách bất đối xứng (ADC) và bảng tra cứu, giúp giảm đáng kể thời gian tìm kiếm trên tập dữ liệu lớn.

3. Cơ sở dữ liệu thử nghiệm trong khóa luận được tổ chức như thế nào?
Cơ sở dữ liệu gồm 3 nhóm: (1) Tập huấn luyện gồm 20 ảnh từ Google Product Search để học tham số codebook; (2) Tập dữ liệu tìm kiếm cho mỗi câu truy vấn gồm 30 ảnh (trộn giữa ảnh sản phẩm chuẩn từ Google Product Search và ảnh gây nhiễu từ Flickr); (3) Tập truy vấn gồm 10 ảnh sản phẩm do người dùng nhập vào.

4. Kết quả độ chính xác của hệ thống đạt được cụ thể là bao nhiêu?
Thực nghiệm trên 10 câu truy vấn cho thấy hệ thống đạt độ chính xác trung bình tổng thể $\text{MAP} = 80,4%$ đối với top 10 ảnh trả về. Đặc biệt, độ chính xác ở vị trí đầu tiên ($P@1$) đạt mức cao, trong đó có 8/10 truy vấn trả về bức ảnh đầu tiên trùng khớp với ảnh truy vấn.

Kết luận

Khóa luận tốt nghiệp của tác giả Nguyễn Thị Hoàn đã hệ thống hóa các phương pháp trích chọn đặc trưng thị giác và đề xuất mô hình tìm kiếm ảnh sản phẩm hai giai đoạn kết hợp giữa đặc trưng cục bộ SIFT, lượng tử hóa tích (PQ-ADC) và khoảng cách Ơclit. Kết quả thực nghiệm trên môi trường Matlab với dữ liệu từ Google Product Search và Flickr đạt độ chính xác trung bình $\text{MAP} = 80,4%$ cho top 10 ảnh trả về. Công trình là tài liệu tham khảo có giá trị học thuật về mặt phương pháp luận trích chọn đặc trưng và kỹ thuật lượng tử hóa vector trong bài toán thu nhận thông tin hình ảnh.