Computer Vision

[Image Search Engine] 4 bước để xây dựng một Image Search Engine

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu các bước cần thực hiện để có thể xây dựng cho mình một Công cụ tìm kiếm hình ảnh (Image Search Engine).


HIỂU VỀ IMAGE SEARCH ENGINE

Khác với các Search Engine chúng ta sử dụng hàng ngày như Google hay Bing, Image Search Engine sử dụng dữ liệu ở dạng hình ảnh thay vì text để tìm kiếm thông tin. Image Search Engine phân tích dữ liệu bằng cách định lượng nội dung của bức ảnh. Để xây dựng được một Image Search Engine chúng ta cần thực hiện các bức sau:

  1. Xác định và xây dựng bộ mô tả hình ảnh (Image Descriptor) cần dùng để định lượng nội dung của các bức ảnh;
  2. Sử dụng bộ mô tả hình ảnh ở bước 1 để trích xuất vector đặc trưng (Feature Vector) của các bức ảnh và tạo thành một bộ cơ sở dữ liệu;
  3. Xác định phương pháp để so sánh các vector đặc trưng giữa các bức ảnh;
  4. Áp dụng bộ mô tả hình ảnh để trích xuất vector đặc trưng cho bức ảnh cần tìm kiếm, sau đó so sánh với cơ sở dữ liệu để cho ra kết quả phù hợp nhất

Ở phần tiếp theo của bài viết chúng ta sẽ tìm hiểu kỹ từng bước trên.


XÁC ĐỊNH VÀ XÂY DỰNG BỘ MÔ TẢ HÌNH ẢNH

Để có thể xây dựng được một bộ mô tả hình ảnh phù hợp, chúng ta cần xác định rõ đặc điểm nào của các bức ảnh sẽ được sử dụng để phân biệt chúng, có thể là màu sắc chủ đạo, hình dạng của đối tượng trong bức ảnh, kết cấu, hoa văn hoặc là kết hợp các đặc điểm này lại.

MÀU SẮC

Để mô tả đặc trưng về màu sắc cho bức ảnh chúng ta thường sử dụng Color Histogram. Một ưu điểm của phương pháp này là kết quả nhận được không bị ảnh hưởng vào kích thước và góc quay của bức ảnh. Bất biến đối với sự thay đổi kích thước và góc quay của bức ảnh là đặc tính rất cần thiết của bất kỳ Image Search Engine nào.

HÌNH DẠNG

Hình dạng của một đối tượng cụ thể trong bức ảnh cũng có thể được sử dụng như đặc trưng của bức ảnh. Bức ảnh sẽ được nhị phân hóa để tìm ra Contour của đối tượng, sau đó áp dụng các phương pháp như Hu MomentsZernike Moments để trích xuất vector đặc trưng của đối tượng.

KẾT CẤU – HOA VĂN

Các đặc trưng về kết cấu, hoa văn có trong bức ảnh (xù xì, trơn nhẵn,…) có thể được trích xuất với các phương pháp như Haralick Texture, Local Binary PatternHistogram Of Gradient.


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

Trích xuất vector đặc trưng là quá trình áp dụng Image Descriptor để định lượng bức ảnh, từ đó nhận được các đặc trưng của bức ảnh đó.

KHỞI TẠO IMAGE DESCRIPTOR

Để đảm bảo tính nhất quán khi áp dụng Image Descriptor (các tham số được sử dụng) cho tất cả các bức ảnh trong dataset, Image Descriptor nên được xây dựng thành một class thay vì function, với các tham số được truyền vào Constructor.

Cấu trúc tổng quát để xây dựng Image Descriptor như sau:

class GenericDescriptor:
	def __init__(self, paramA, paramB):
		# put some parameters here.
		self.paramA = paramA
		self.paramB = paramB

	def describe(self, image):
		# put your code here.
		pass

Vì tất cả các tham số đều được truyền vào Constructor nên method describe sẽ sử dụng chúng một cách nhất quán với tất cả bức ảnh được đưa vào.

TUẦN TỰ HAY SONG SONG

Việc trích xuất vector đặc trưng cho một lượng dữ liệu lớn (tầm vài chục GB) sẽ tốn khá nhiều thời gian, do đó chúng ta sẽ nghĩ đến phương án sử dụng multiple threads/processes. Tuy nhiên, đừng lạm dụng multiple threads, nhất là khi lượng dữ liệu của chúng ta không nhiều, vì việc debug cho multiple threads khó khăn hơn nhiều so với single thread.

LƯU TRỮ DỮ LIỆU

Sau khi đã trích xuất được vector đặc trưng của bức ảnh, chúng ta cần lưu nó vào một file để sử dụng sau này, cách đơn giản nhất là lưu vào file với định dạng CSV (Comma Seperated Value). Nếu khối lượng dữ liệu quá lớn, chúng ta có thể sử dụng các thư viện như cPickle và h5py để lưu trữ dữ liệu.


XÁC ĐỊNH PHƯƠNG PHÁP SO SÁNH

Đến bước này chúng ta đã có bộ cơ sở dữ liệu chứa vector đặc trưng của toàn bộ bức ảnh trong dataset, nhưng làm thể nào để so sánh chúng với vector đặc trưng của Query Image (bức ảnh được sử dụng để tìm kiếm) để tìm ra mức độ tương đồng?

Nhớ lại thời học cấp 3, chắc hẳn chúng ta đều đã được học cách tính khoảng cách giữa hai vector trong hình học phẳng, chẳng hạn: cho vector A(1, 3), vector B (4, -1), khoảng cách giữa hai vector A, B sẽ là d(A, B) = 5.

Vector đặc trưng cũng tương tự như thế, chỉ khác một điểm là nó có số chiều không gian nhiều hơn so với vector trong hình học phẳng thôi. Khi khoảng cách giữa hai vector bằng 0 thì hai vector đó trùng nhau (hoàn toàn giống nhau).

Tất nhiên khoảng cách giữa hai vector phải thỏa mãn các điều kiện sau:

  1. d(A, B) ≥ 0;
  2. d(A, B) = 0 khi và chỉ khi A = B;
  3. d(A, B) = d(B, A);
  4. d(A, C) ≤ d(A, B) + d(B, C), với C là một vector bất kỳ.

Bây giờ chúng ta sẽ tìm hiểu qua một số Distance Metric thường dùng trong Computer Vision.

EUCLIDEAN DISTANCE

Khoảng cách Euclidean được dùng để xác định khoảng cách giữa hai điểm bất kỳ trong không gian.

sim_metric_euclideanFigure 1 – Khoảng cách Euclidean

Công thức:euclidean

Example 1:

>>> from scipy.spatial import distance as dist
>>> A = [1, 3]
>>> B = [4, -1]
>>> dist.euclidean(A, B)
5.0

MANHATTAN/CITYBLOCK DISTANCE

Khác với khoảng cách Euclidean, khoảng cách Manhattan (còn được gọi là khoảng cách Cityblock) giữa hai điểm là tổng giá trị tuyệt đối của chênh lệch tọa độ theo từng chiều của không gian.

sim_metric_manhattan

Figure 2 – Khoảng cách Manhattan

Công thức:manhattan

Example 2:

>>> from scipy.spatial import distance as dist
>>> A = [1, 3]
>>> B = [4, -1]
>>> dist.cityblock(A, B)
7

HISTOGRAM INTERSECTION

Histogram Intersection được dùng để so sánh hai histogram, nó chính là phần giao nhau của hai histograms. Phần giao nhau này càng lớn thì hai histogram càng tương đồng.

histintersect

Figure 3 – Histogram Intersection

Công thức:

intersection

Example 3:

>>> import numpy as np
>>> def histogram_intersection(H1, H2):
...     return np.sum(np.minimum(H1, H2))
...
>>> A = [1,2,3,4,5,6,7,8,9]
>>> B = [9,8,7,6,5,4,3,2,1]
>>> histogram_intersection(A, B)
25
>>> histogram_intersection(A, A)
45

CHI-SQUARED DISTANCE

Một phương pháp phổ biến khác để so sánh hai histogram là Chi-square Distance.

Công thức:

chisquared

Example 4:

>>> import numpy as np
>>> def chi2_distance(histA, histB, eps=1e-10):
...     return 0.5 * np.sum(((histA - histB) ** 2) / (histA + histB + eps))
...
>>> A = np.array([1,2,3,4,5,6,7,8,9])
>>> B = np.array([9,8,7,6,5,4,3,2,1])
>>> chi2_distance(A, B)
11.99999999988
>>> chi2_distance(B, B)
0.0

COSINE SIMILARITY

Giá trị cosine giữa hai vector cũng có thể được dùng để mô tả sự tương đồng giữa chúng.

sim_metric_cosine

Công thức: “Tích vô hướng chia cho tích độ dài”

cosine

Tuy nhiên, để không bị nhầm lẫn, thư viện Scipy sẽ tích cosine theo công thức:

scipycosine

Lúc này, hai vector sẽ hoàn toàn tương đồng nếu cosine = 0.

Example 5:

>>> from scipy.spatial import distance as dist
>>> A = [1, 3]
>>> B = [4, -1]
>>> dist.cosine(A,B)
0.9233035011152629
>>> dist.cosine(A,B)
0.0

HAMMING DISTANCE

Hamming Distance được sử dụng để đánh giá sự tương đồng giữa hai vector nhị phân (Binary Vector), bằng cách tính tổng các giá trị khác biệt giữa hai vector rồi chia cho số chiều của vector đó.

Example 6:

>>> from scipy.spatial import distance as dist
>>> A = [1,0,0,1,1,1,0,0]
>>> B = [1,1,0,0,1,0,1,0]
>>> dist.hamming(A,B)
0.5
>>> dist.hamming(B,B)
0.0

ÁP DỤNG

Khi sử dụng các Search Engine như Google hay Bing, chúng ta cần cung cấp các từ khóa liên quan đến chủ đề cần tìm kiếm. Tương tự đối với Image Search Engine, chúng ta cần một “Query Image”.

Query Image có thể được tải lên từ máy tính hoặc smartphone để Image Search Engine xử lý. Sau khi trích xuất, vector đặc trưng của Query Image sẽ được so sánh với cơ sở dữ liệu đã được tạo ở bước 2, từ cơ sở đó cho ra những kết quả liên quan nhất. Kết quả tìm kiếm cần được hiển thị một cách trực quan nhất đối với người dùng.


SUMMARY

Qua bài viết này chúng ta đã có cái nhìn cơ bản về các bước để xây dựng một Image Search Engine. Cảm ơn các bạn đã theo dõi bài viết.

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

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