3. SIFT part 1: Harris Corner detection

Mở đầu

Corner Detection được sử dụng trong hệ thống Computer Vision để trích xuất một số features đặc thù cho nội dung hình ảnh

Corner Detection được sử dụng nhiều cho motion detection, image registration, video tracking, ... Và ta sẽ tập trung khai thác Corner detection cho việc tìm hiểu SIFT SUFT algorithm

Ta tìm hiểu về các khía cạnh sau của Corner detection: công dụng và nguyên lí hoạt động cũng như sự khác nhau của các algorithms

Harris Corner Detector

Không mất tính tổng quát, ta giả sử có 1 hình 2D ban đầu I (1 ma trận 2 chiều được viết theo hệ tọa độ ban đầu (u, v), ta tịnh tiến nó theo vector (x, y). Từ đó ta có công thức sum of squared differences (SSD) giữa 2 hình (kí hiệu S):

$S(x,y)=\sum _{u}\sum _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$

w là window chứa điểm đang xét ( lấy điểm đang xét làm tâm)

Theo khai triển Taylor cho phương trình đạo hàm 2 biến, ta có:

$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$

Vì vậy: $S(x,y)\approx \sum _{u}\sum _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2},$

Ta phân tích các đạo hàm riêng của I là I_x và I_ymỗi đạo hàm sẽ lấy giá trị strong positive value và strong negative value của ma trận ảnh (đạo hàm 1 điểm dựa vào giá trị các điểm xung quanh) , hình thành các đường để xác định Edge và Corner

Ta có thể viết thành $S(x,y)\approx {\begin{bmatrix}x&y\end{bmatrix}}A{\begin{bmatrix}x\\y\end{bmatrix}},$

Có thể nhìn thấy rằng bây giờ là phương trình chéo hóa ma trận A (hay covariance matrix) ( A = $Q^{-1}BQ$ )

Với

A=\sum _{u}\sum _{v}w(u,v){\begin{bmatrix}I_{x}(u,v)^{2}&I_{x}(u,v)I_{y}(u,v)\\I_{x}(u,v)I_{y}(u,v)&I_{y}(u,v)^{2}\end{bmatrix}}={\begin{bmatrix}\langle I_{x}^{2}\rangle &\langle I_{x}I_{y}\rangle \\\langle I_{x}I_{y}\rangle &\langle I_{y}^{2}\rangle \end{bmatrix}}

Vì A là matrix 2x2, ta có thể mườn tượng A là 1 elip đối với trục tọa độ có tâm là điểm cần xét

Khi đó ta có 2 tham số để biểu diễn hình elip (bán trục lớn và bán trục bé) tương ứng với 2 vector giá trị riêng của ma trận A (Λ₁ và λ₂ )

Từ giá trị của Λ₁ và λ₂ , ta có 3 trường hợp:

- Nếu cả 2 lambda tiệm cận 0, thì điểm đang xét là 1 điểm bình thường

- Nếu 1 lambda tiệm cận 0 và 1 lambda có giá trị lớn, điểm đang xét nằm trên 1 edge với lambda lớn là phương của edge còn lambda nhỏ vuông góc với phương của edge

- Nếu 2 lambda đều có giá trị lớn thì điểm đang xét là điểm góc với 2 lambda vuông góc với 2 edge chính dẫn đến điểm corner

Từ đó trở thành bài toán classification dựa vào giá trị 2 lambda

Tuy nhiên, người ta thấy rằng tính trực tiếp các vector riêng là khó (giá trị tính toán lớn) trong nhiều trường hợp thực tế, vì vậy, có một giá trị riêng khác để xác định corner chỉ dựa vào det và trace (2 giá trị này không đổi trong quá trình chéo hóa)

M_{c}=\lambda _{1}\lambda _{2}-\kappa \left(\lambda _{1}+\lambda _{2}\right)^{2}=\det(A)-\kappa \operatorname {trace} ^{2}(A)

Với k là tuning parameter

Theo các nghiên cứu, lấy giá trị k thuộc (0.04, 0.15) là phù hợp nhất

Từ đó ta có thể so sánh giá trị M_c với 1 threshold để kiểm tra xem có phải corner không

Ngoài ra, ta có thể tránh chọn k bằng cách sử dụng Noble's corner. Ý tưởng là lấy đạo hàm, ta có:

M_{c}'=2{\frac {\det(A)}{\operatorname {trace} (A)+\epsilon }},

Với ∋ là giá trị dương rất nhỏ

Non-Maximal Suppression

Cũng giống như các bài toán CV khác, có khả năng chúng ta xác định được những object cần thiết quá gần nhau

Trong bài toán này là việc các điểm được xác định là Corner (giá trị M_c lớn hơn threshold). Vì vậy cần dùng NMS để xác định điểm Corner chính xác. Ý tưởng là xét trong window có size = k, chỉ xác định điểm sáng nhất (maximum) nếu các điểm này kề nhau