Thuật toán SIFT trong thị giác máy tính: Trích xuất và so khớp đặc trưng bất biến tỷ lệ

So khớp đối tượng chính xác từ nhiều góc nhìn khác nhau là bài toán trọng tâm trong xử lý ảnh kỹ thuật số.

SIFT (Scale Invariant Feature Transform) là một trong những giải thuật kinh điển và phổ biến nhất trong lĩnh vực thị giác máy tính (computer vision). Mục tiêu cốt lõi của giải thuật bao gồm phát hiện các điểm đặc trưng (keypoints) của đối tượng, tạo vector mô tả (descriptors) cho các điểm này và thực hiện so khớp chính xác đối tượng trên các ảnh chụp khác nhau.

Đúng như tên gọi, SIFT là giải thuật bất biến theo tỷ lệ (scale-invariant), nghĩa là cùng một đối tượng có thể xuất hiện ở các kích thước và khoảng cách khác nhau trong cặp ảnh, nhưng giải thuật vẫn có khả năng nhận diện thành công các điểm đặc trưng quan trọng.

Bên cạnh đó, SIFT còn có tính chất bất biến theo phép quay (rotation-invariant), cho phép nhận diện và so khớp chính xác các đối tượng ngay cả khi chúng bị xoay nghiêng theo nhiều góc độ.

Cơ chế vận hành chi tiết bên trong giải thuật được triển khai qua các giai đoạn kỹ thuật cụ thể dưới đây.

Lưu ý: Trong bài viết này, phép biến đổi Laplacian of Gaussian (LoG) được đề cập như một kỹ thuật dùng để phát hiện biên cạnh trong ảnh. Nếu chưa quen thuộc với kỹ thuật này, bạn nên tham khảo trước các tài liệu chuyên sâu về phát hiện biên cạnh (edge detection).

Lưu ý: Trong bài viết này, phép biến đổi Laplacian of Gaussian (LoG) được đề cập như một kỹ thuật dùng để phát hiện biên cạnh trong ảnh. Nếu chưa quen thuộc với kỹ thuật này, bạn nên tham khảo trước các tài liệu chuyên sâu về phát hiện biên cạnh (edge detection).

Quy trình này có thể được tiếp cận bài bản từng bước thông qua lộ trình học Machine Learning tương tác.

Trong quy trình xử lý, SIFT xây dựng nhiều phiên bản của ảnh gốc bằng cách áp dụng các phép biến đổi thay đổi kích thước và làm mờ Gauss (Gaussian blur).

Để đơn giản hóa mô hình toán học, giả sử I(x, y) là ảnh gốc ban đầu. Trước tiên, với các giá trị k và σ1 được lựa chọn, SIFT tạo ra nhiều phiên bản của ảnh gốc bằng cách áp dụng phép làm mịn Gauss với các độ lệch chuẩn tăng dần: σ1, k⋅σ1, k^2⋅σ1, k^3⋅σ1, ..., trong đó k > 1.

Quá trình này tạo ra một chuỗi ảnh liên tiếp, trong đó mỗi ảnh kế tiếp có mức độ mờ tăng dần so với ảnh trước đó. Chuỗi ảnh này được định nghĩa là một octave.

Tiếp theo, SIFT tính toán hiệu từng cặp ảnh kế tiếp D1, D2, …, Dn, được gọi là phép sai phân Gauss hay Difference of Gaussians (DoG). Phép trừ này làm nổi bật các điểm ảnh có sự biến thiên cường độ sáng mạnh. Sau đó, thuật toán xếp chồng các lớp Di lên nhau và tìm kiếm các điểm cực trị cục bộ (local extrema) theo không gian ba chiều:

Với mỗi điểm tọa độ tại Di(x, y), SIFT kiểm tra toàn bộ 26 điểm lân cận xung quanh:

• 8 điểm lân cận trực tiếp trên cùng mặt phẳng cấp Di;
• 9 điểm nằm ngay phía trên Di(x, y) (trên mặt phẳng cấp Di+1);
• 9 điểm nằm ngay phía dưới Di(x, y) (trên mặt phẳng cấp Di-1);

8 điểm lân cận trực tiếp trên cùng mặt phẳng cấp Di;

9 điểm nằm ngay phía trên Di(x, y) (trên mặt phẳng cấp Di+1);

9 điểm nằm ngay phía dưới Di(x, y) (trên mặt phẳng cấp Di-1);

Sau khi so sánh, một trong ba trường hợp sau sẽ xảy ra:

• Nếu Di(x, y) có giá trị lớn hơn tất cả 26 điểm lân cận, SIFT xác định điểm đó là cực đại cục bộ (maximum).
• Nếu Di(x, y) có giá trị nhỏ hơn tất cả 26 điểm lân cận, SIFT xác định điểm đó là cực tiểu cục bộ (minimum).
• Các trường hợp còn lại, điểm Di(x, y) sẽ bị loại bỏ.

Nếu Di(x, y) có giá trị lớn hơn tất cả 26 điểm lân cận, SIFT xác định điểm đó là cực đại cục bộ (maximum).

Nếu Di(x, y) có giá trị nhỏ hơn tất cả 26 điểm lân cận, SIFT xác định điểm đó là cực tiểu cục bộ (minimum).

Các trường hợp còn lại, điểm Di(x, y) sẽ bị loại bỏ.

Điểm Di(x, y) cùng 26 điểm lân cận có thể được trực quan hóa dưới dạng một khối lưới 3x3x3 với tâm đặt tại Di(x, y). Quy trình này cho phép sàng lọc và định vị những đặc trưng mạnh nhất trên ảnh.

Các giá trị cực trị tìm được chính là các điểm cần quan tâm (points of interest). Do số lượng điểm ban đầu có thể rất lớn, SIFT sẽ áp dụng ngưỡng lọc (thresholding) hoặc các toán tử phụ trợ để chỉ giữ lại những điểm đặc trưng thể hiện sự biến thiên cường độ rõ rệt nhất.

Để giải quyết sự thay đổi về tỷ lệ hình ảnh, toàn bộ quy trình trên được lặp lại cho một ảnh đã giảm mẫu (downsampled) với chiều rộng và chiều cao giảm đi một nửa. Kết quả tạo ra một chuỗi octave mới với độ nhiễu Gauss lớn hơn, tương ứng với các giá trị σ: σ2, k⋅σ2, k^2⋅σ2, k^3⋅σ2, ..., trong đó σ2 = 2σ1. Tương tự như trước, các điểm cực trị tiếp tục được xác định từ hiệu ảnh DoG thông qua phương pháp lưới 3x3x3.

Ở vòng lặp thứ ba, hình ảnh tiếp tục được giảm mẫu một lần nữa (chiều rộng và chiều cao giảm đi 2 lần) và một octave mới có độ mờ lớn hơn được xây dựng với các giá trị σ là σ3, k⋅σ3, k^2⋅σ3, k^3⋅σ3, ..., trong đó σ3 = 2σ2 = 4σ1.

Toàn bộ chu trình này được thực hiện lặp lại theo số lượng vòng lặp đã cấu hình trước.

Sau khi nắm rõ cơ chế tìm điểm đặc trưng, việc giải đáp một số vấn đề nền tảng sẽ giúp làm sáng tỏ bản chất vận hành của giải thuật.

Tại sao lại sử dụng DoG thay vì LoG?

Toán tử Laplacian of Gaussian (LoG) là một phép biến đổi hiệu quả để xác định biên cạnh trong ảnh. Tuy nhiên, hiệu của hai phép biến đổi LoG áp dụng trên cùng một ảnh ở hai tỷ lệ khác nhau có thể được xấp xỉ chính xác thông qua công thức sau:

DoG = nkσ - nσ ≈ (k - 1)σ2 ⋅ ▽2nσ

Việc tính toán DoG theo công thức trừ ma trận ảnh nhanh hơn rất nhiều và tốn ít chi phí tính toán hơn so với việc phải áp dụng công thức tích chập LoG đầy đủ ở từng cấp độ.

Tại sao phải xây dựng nhiều lớp DoG trong cùng một octave?

Trong cùng một octave, độ mờ của hình ảnh tăng dần đều. Hiệu giữa hai ảnh DoG liên tiếp sẽ làm nổi bật các điểm đặc trưng trên các thang tỷ lệ tương ứng.

Cụ thể, một lớp DoG tạo bởi hai ảnh ít bị mờ (ở đáy của octave) giúp phát hiện dễ dàng các chi tiết kích thước nhỏ. Tuy nhiên, việc nhận diện các đặc trưng kích thước lớn ở tầng này lại gặp khó khăn. Do đó, thuật toán tiếp tục tính toán DoG cho các ảnh mờ hơn (ở đỉnh của octave), nơi các chi tiết siêu nhỏ đã bị triệt tiêu, cho phép giải thuật tập trung hoàn toàn vào các vùng cấu trúc lớn hơn.

Tại sao cần phải tạo nhiều octave?

Khi độ mờ tăng lên, các đặc trưng kích thước lớn hơn sẽ lộ diện. Một câu hỏi đặt ra là tại sao không sử dụng duy nhất một octave và tăng dần mức độ làm mờ từ rất thấp đến rất cao để quét mọi kích thước đặc trưng?

Lý do cho việc phân chia thành nhiều octave xuất phát từ hai yếu tố kỹ thuật:

• Khi độ mờ tăng cao, các chi tiết nhỏ biến mất hoàn toàn. Xét về mặt hiệu năng tính toán, việc giữ nguyên độ phân giải đầy đủ ở các cấp độ mờ cao là không cần thiết. Việc giảm mẫu (downsampling) giúp giảm số lượng điểm ảnh đi 4 lần, đẩy nhanh tốc độ xử lý ma trận.

Khi độ mờ tăng cao, các chi tiết nhỏ biến mất hoàn toàn. Xét về mặt hiệu năng tính toán, việc giữ nguyên độ phân giải đầy đủ ở các cấp độ mờ cao là không cần thiết. Việc giảm mẫu (downsampling) giúp giảm số lượng điểm ảnh đi 4 lần, đẩy nhanh tốc độ xử lý ma trận.

• Việc xấp xỉ các nhân Gauss (Gaussian kernels) kích thước quá lớn sẽ tích lũy sai số tính toán, do đó không nên tăng tham số σ lên mức cực đoan. Đồng thời, quá trình giảm mẫu cũng đóng vai trò tương đương với việc làm mờ ảnh gốc do đã loại bỏ bớt chi tiết mịn. Vì vậy, áp dụng độ mờ cao trên ảnh kích thước lớn tương đương với việc dùng độ mờ nhỏ trên ảnh đã thu nhỏ.

Việc xấp xỉ các nhân Gauss (Gaussian kernels) kích thước quá lớn sẽ tích lũy sai số tính toán, do đó không nên tăng tham số σ lên mức cực đoan. Đồng thời, quá trình giảm mẫu cũng đóng vai trò tương đương với việc làm mờ ảnh gốc do đã loại bỏ bớt chi tiết mịn. Vì vậy, áp dụng độ mờ cao trên ảnh kích thước lớn tương đương với việc dùng độ mờ nhỏ trên ảnh đã thu nhỏ.

Nhờ đó, kỹ thuật giảm mẫu và cấu trúc phân tầng octave mang lại lợi thế vượt trội về mặt tài nguyên.

Tại sao lại dùng cửa sổ 3 chiều?

Cửa sổ trượt 3×3 trên một ảnh đơn lẻ có thể tìm được cực trị cục bộ, nhưng số lượng điểm phát hiện được sẽ quá nhiều và phân mảnh khi ta mở rộng không gian tỷ lệ.

Việc bổ sung chiều thứ ba (chiều tỷ lệ) giúp đảm bảo điểm đặc trưng không chỉ độc nhất trên mặt phẳng 2D mà còn ổn định qua nhiều thang đo tỷ lệ khác nhau, đảm bảo tính bền vững khi kích thước ảnh thay đổi (phóng to hoặc thu nhỏ).

Bản chất của việc tìm cực trị qua các lớp DoG chính là phát hiện điểm biên cạnh nổi bật, bởi vì DoG là dạng xấp xỉ của toán tử LoG dùng trong phát hiện biên cạnh.

Sau khi tập hợp tất cả các điểm ứng viên, SIFT tiến hành loại bỏ các điểm yếu. Một điểm là cực trị toán học vẫn có thể chỉ là nhiễu ảnh. Để duy trì chất lượng, SIFT thiết lập một ngưỡng biến thiên cường độ sáng nhằm loại bỏ hoàn toàn các điểm ứng viên có độ tương phản thấp.

Khi đã cố định tập điểm đặc trưng, SIFT xây dựng vector mô tả đặc trưng (feature descriptors) phục vụ việc so khớp qua các góc nhìn ảnh khác nhau.

Trước hết, các điểm đặc trưng ở các lớp DoG khác nhau được ánh xạ vào các vùng hình tròn có bán kính tỷ lệ thuận với giá trị σ của lớp DoG tương ứng. Sau đó, hướng gradient của tất cả các pixel nằm trong hình tròn đó trên ảnh gốc sẽ được tính toán.

Kế tiếp, SIFT chia vùng hình tròn này thành 4 góc phần tư bằng nhau và thiết lập biểu đồ phân bố hướng gradient (gradient direction distribution) cho từng góc.

Bốn biểu đồ phân bố sau khi xây dựng sẽ được chuyển đổi thành một vector đặc trưng 128 chiều đại diện duy nhất cho điểm đặc trưng đó.

Trong trường hợp vùng lân cận của điểm đặc trưng chứa ít hơn 128 điểm ảnh, cơ chế nội tại của SIFT vẫn có khả năng tính toán đầy đủ vector 128 chiều nhờ việc tích hợp bổ sung thông tin từ các điểm ảnh lân cận xung quanh.

Trong các tình huống thực tế, đối tượng thường bị xoay ở các góc độ khác nhau giữa hai bức ảnh. Để xử lý phép quay, SIFT xác định thêm thông tin về hướng chủ đạo (principal orientation) của gradient, tức hướng xuất hiện nhiều nhất trong phân bố. Hướng này đóng vai trò là điểm chuẩn định hướng của đối tượng, giúp chuẩn hóa tọa độ và loại bỏ các trường hợp so khớp sai lệch, thiết lập tính bất biến đối với phép quay.

So sánh các vector mô tả SIFT

Các vector mô tả SIFT là các vector số học có thể được so sánh định lượng để xác định mức độ tương đồng giữa các điểm. Ứng dụng chính của thao tác này là xác thực xem hai điểm đặc trưng trên hai bức ảnh có cùng đại diện cho một vị trí thực tế của đối tượng hay không.

Khoảng cách chuẩn L2 (Euclidean distance) là độ đo phổ biến nhất:

Khoảng cách L2 càng nhỏ thì độ tương đồng giữa hai điểm càng cao. Khi khoảng cách bằng 0, hai điểm khớp nhau tuyệt đối.

Một độ đo khác thường được sử dụng là độ giao biểu đồ (histogram intersection):

Công thức này duyệt qua từng thành phần của vector và lấy giá trị nhỏ nhất giữa hai vector, biểu thị mức độ tương quan về hướng gradient tổng hợp giữa hai đặc trưng. Giá trị này càng cao, độ tương đồng giữa hai điểm càng lớn.

Thông thường, cùng một đối tượng xuất hiện trên nhiều ảnh sẽ tạo ra hàng loạt cặp điểm tương đồng, cho phép hệ thống nhận dạng chính xác đối tượng đó.

Thư viện OpenCV cung cấp sẵn module triển khai thuật toán SIFT thông qua hàm khởi tạo cv2.SIFT_create() với các tham số quan trọng:

• nfeatures: Số lượng đặc trưng tốt nhất cần giữ lại, được xếp hạng theo điểm số đánh giá của thuật toán SIFT.
• nOctaveLayers: Số lớp trong mỗi octave. Giá trị chuẩn trong bài báo khoa học gốc là 3.
• contrastThreshold: Ngưỡng tương phản dùng để loại bỏ các đặc trưng yếu ở những vùng có độ tương phản thấp. Ngưỡng càng lớn thì số lượng đặc trưng giữ lại càng ít.
• edgeThreshold: Ngưỡng lọc bỏ các đặc trưng dạng biên cạnh. Ngưỡng càng lớn thì càng ít đặc trưng biên bị loại bỏ (giữ lại nhiều đặc trưng hơn).
• sigma: Giá trị sigma của phép làm mờ Gauss áp dụng cho ảnh đầu vào ở octave đầu tiên.

nfeatures: Số lượng đặc trưng tốt nhất cần giữ lại, được xếp hạng theo điểm số đánh giá của thuật toán SIFT.

nOctaveLayers: Số lớp trong mỗi octave. Giá trị chuẩn trong bài báo khoa học gốc là 3.

contrastThreshold: Ngưỡng tương phản dùng để loại bỏ các đặc trưng yếu ở những vùng có độ tương phản thấp. Ngưỡng càng lớn thì số lượng đặc trưng giữ lại càng ít.

edgeThreshold: Ngưỡng lọc bỏ các đặc trưng dạng biên cạnh. Ngưỡng càng lớn thì càng ít đặc trưng biên bị loại bỏ (giữ lại nhiều đặc trưng hơn).

sigma: Giá trị sigma của phép làm mờ Gauss áp dụng cho ảnh đầu vào ở octave đầu tiên.

Các điểm đặc trưng sau khi trích xuất có thể được trực quan hóa trực tiếp trên ảnh bằng đoạn mã nguồn dưới đây:

import cv2
image = cv2.imread('data/input/image.jpg')
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
sift = cv2.SIFT_create()
keypoints = sift.detect(gray, None)
output = cv2.drawKeypoints(
    image,
    keypoints,
    None,
    flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS
)
cv2.imwrite('data/output/image.jpg', output)

Kết quả hiển thị đặc trưng thu được:

Trên thực tế, đối với các bức ảnh phức tạp hơn, số lượng điểm đặc trưng được phát hiện có thể đạt mức rất lớn:

Nhờ tính ổn định cao, SIFT được áp dụng rộng rãi trong nhiều tác vụ xử lý thị giác máy tính thực tế.

So khớp ảnh (Image matching)

Các vector mô tả đặc trưng đóng vai trò cốt lõi trong bài toán so khớp ảnh. Thử nghiệm được thực hiện trên cặp ảnh dưới đây:

Trước tiên, cặp ảnh được nạp vào hệ thống và chuyển đổi sang không gian mức xám (grayscale) trước khi đưa vào mô hình SIFT:

import cv2
IMAGE_ONE_PATH = "data/input/image_1.jpg"
IMAGE_TWO_PATH = "data/input/image_2.jpg"
OUTPUT_PATH = "data/output/matches.png"
image_one = cv2.imread(IMAGE_ONE_PATH)
image_two = cv2.imread(IMAGE_TWO_PATH)
gray_one = cv2.cvtColor(image_one, cv2.COLOR_BGR2GRAY)
gray_two = cv2.cvtColor(image_two, cv2.COLOR_BGR2GRAY)

Sau đó, các vector mô tả đặc trưng được trích xuất cho từng ảnh:

sift = cv2.SIFT_create()
keypoints_one, descriptors_one = sift.detectAndCompute(gray_one, None)
keypoints_two, descriptors_two = sift.detectAndCompute(gray_two, None)

Nguồn: Towards Data Science