Computer Vision

[Image Search Engine] Mô hình Bag of Visual Words

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về mô hình Bag of Visual Words (BOVW) – một khái niệm quan trọng trong Computer Vision.

Từ các bài viết về Local Feature Descriptor, chúng ta đã biết cách trích xuất vector đặc trưng từ các keypoint có trong bức ảnh, nhưng mỗi bức ảnh có số lượng keypoint khác nhau, vậy làm thế nào để phân loại các bức ảnh dựa trên Local Feature Vectors? Hãy đọc bài viết này thật kỹ nhé.


BAG OF VISUAL WORDS

Trước khi đi vào tìm hiểu mô hình BOVW, chúng ta sẽ làm quen với một mô hình đơn giản hơn là Bag of Words được sử dụng khi phân tích nội dung các đoạn văn bản.

Khi phân tích nội dung, các từ khóa (keywords) có trong đoạn văn bản sẽ được thu thập và đưa vào một tập hợp mà không cần quan tâm đến thứ tự xuất hiện của chúng. Những văn bản có nhiều keywords chung thì sẽ có mối liên hệ với nhau. Việc biểu diễn các văn bản dưới dạng một histogram của tần xuất xuất hiện của các keywords cho phép chúng ta phân tích và so sánh chúng một cách dễ dàng.

Trong Computer Vision, khái niệm Bag of Visual Words cũng tương tự như vậy với keyword sẽ là Feature Vector của các Keypoint có trong từng bức ảnh.

Tuy nhiên việc áp dụng BOVW trong Computer Vision không đơn giản như việc phân tích một đoạn văn bản. Vấn đề ở đây là chúng ta không có một “tiêu chuẩn” để có thể đếm tần xuất xuất hiện của các Feature Vector có trong bức ảnh, vì không có Feature Vector nào giống nhau 100% cả.

Để giải quyết vấn đề trên, chúng ta cần phải xây dựng một bộ “từ điển” (có thể gọi là codebook) nhằm gom nhóm các Feature Vector vào các cluster phù hợp, với các cluster centers được gọi là Visual Keywords. Lúc này chúng ta có thể biểu diễn các bức ảnh dưới dạng histogram tần xuất xuất hiện của các Visual Keywords.

Để xây dựng một mô hình BOVW chúng ta cần thực hiện các bước sau:

  1. Trích xuất vector đặc trưng của tập dữ liệu;
  2. Xây dựng bộ codebook nhằm tổng quát hóa tập vector đặc trưng vừa nhận được;
  3. Biểu diễn các bức ảnh dưới dạng histogram tần xuất xuất hiện của các Visual Keywords, còn được gọi là Vector Quantization.

TRÍCH XUẤT VECTOR ĐẶC TRƯNG

Vector đặc trưng của image set có thể được trích xuất bằng cách phối hợp các Keypoint Detector (FAST, BRISK, DoG, MSER, Dense,…) và các Local Feature Descriptor như SIFT, SURF. Từ mỗi bức ảnh sẽ nhận được nhiều Feature Vector, hình 1.

bovw_multiple_feature_vectors
Hình 1 – Feature Extraction

Vì các Feature Vector có thể tiếp tục được sử dụng sau này nên chúng ta cần lưu giữ chúng ở dạng database. Khi số lượng Feature Vector rất lớn, lưu trữ với CSV format sẽ không hiệu quả, chúng ta sẽ cần đến cPickle format hoặc HD5F format.


XÂY DỰNG CODEBOOK

Để xây dựng codebook từ tập hợp các Feature Vector đã trích xuất được, chúng ta sử dụng K-mean clustering để gom nhóm chúng vào K clusters phù hợp. Các cluster centers chính là các Visual Keywords của codebook, điều này có nghĩa là số lượng Visual Keyword sẽ bằng với số lượng cluster.

Việc chọn số lượng cluster (tương đương với số lượng Visual Word và kích thước của codebook) để gom nhóm cũng không hề đơn giản. Nếu số lượng cluster quá nhỏ thì sẽ không đủ để phân biệt nội dung giữa các bức ảnh. Ngược lại, nếu số lượng cluster quá lớn cũng ảnh hưởng xấu đến hiệu suất của hệ thống. Trên thực tế, để chọn được số lượng cluster phù hợp cần dựa vào kinh nghiệm và quá trình đánh giá hiệu năng.

Nói chung, khi cần áp dụng Machine Learning để phân loại các categories, chúng ta sẽ sử dụng codebook có kích thước nhỏ. Khi cần giải quyết bài toán Instance Recognition thì chúng ta sẽ sử dụng codebook có kích thước lớn.

Khi xây dựng codebook, chúng ta chỉ cần chọn ngẫu nhiên từ 10% đến 25% số Feature Vector đã trích xuất.


VECTOR QUANTIZATION

Với một bức ảnh bất kỳ, chúng ta có thể biểu diễn nó ở dạng histogram tần xuất xuất hiện của các Visual Keywords với các bước sau:

  1. Trích xuất các vector đặc trưng của bức ảnh;
  2. Với mỗi vector đặc trưng, tìm ra Visual Keyword tương đồng với nó nhất có trong codebook bằng cách áp dụng Euclidean Distance;
  3. Xây dựng histogram tần xuất xuất hiện của các Visual Keyword. Histogram này sẽ có kích thước bằng với số lượng Visual Keyword có trong codebook.

Khi các bức ảnh đã được biểu diễn ở dạng histogram (cũng chính là một vector), chúng ta có thể sử dụng các thuật toán Machine Learning hoặc CBIR để phân loại/truy xuất hình ảnh dựa trên nội dung của chúng.


SUMMARY

Đến đây thì câu hỏi ở đầu bài viết đã được trả lời. Với mô hình Bag of Visual Words chúng ta có thể biểu diễn các bức ảnh (nói chính xác hơn là các Local Feature Vectors có trong bức ảnh) ở dạng một vector duy nhất (chính là histogram tần xuất xuất hiện của các Visual Keywords có trong codebook), từ đó có thể áp dụng Machine Learning hoặc các giải thuật khác để tiếp tục xử lý.

Cảm ơn các bạn đã theo dõi bài viết.

Thân ái và quyết thắng.

Reference:
[1] Infomation Retrieval.
[2] Vector quantization.

One thought on “[Image Search Engine] Mô hình Bag of Visual Words

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s