12/08/2018, 10:43

Giới thiệu về Scale-Invariant Feature Transform

Scale-Invariant Feature Transform (SIFT) là giải thuật trong lĩnh vực Computer Vision, dùng để nhận dạng và miêu tả những điểm đặc trưng(local features) trong ảnh. Giải thuật lần đầu được giới thiệu bởi David Lowe năm 1999. Giải thuật này(cùng với giải thuật anh em là SURF) được ứng dụng rộng rãi ...

Scale-Invariant Feature Transform (SIFT) là giải thuật trong lĩnh vực Computer Vision, dùng để nhận dạng và miêu tả những điểm đặc trưng(local features) trong ảnh. Giải thuật lần đầu được giới thiệu bởi David Lowe năm 1999. Giải thuật này(cùng với giải thuật anh em là SURF) được ứng dụng rộng rãi trong Nhận dạng đối tượng(object recognition), mô hình hóa 3D(3D modeling),...

Điểm đặc biệt của SIFT nằm ngay trong cái tên của nó Scale-Invariant, tức là nó sẽ đưa ra các kết quả ổn định với những scale của ảnh khác nhau, bên cạnh đó cũng có thể nói giải thuật này có tính rotation-invariant.

Trong bài báo khoa học "Distinctive Image Features from Scale-Invariant Keypoints", SIFT được đặc tả rõ nét dưới bốn giai đoạn(stages) chính sau:

  • Scale-space extrema detection.

  • Keypoint localization.

  • Orientation assignment.

  • Keypoint descriptor.

Sau đây, tôi sẽ trình bày tư tưởng chung của từng giai đoạn:

1. Scale-space extrema detection

Chúng ta cùng xem xét ví dụ dưới đây:

sift_scale_invariant.jpg

Note: Trong computer vision, chúng ta thường định nghĩa kích cỡ các cửa sổ(window) rồi quét ảnh với các cửa sổ đó để tìm những đặc tính(feature) của ảnh.

Phía bên trái chúng ta có 1 góc(corner) với kích thước nhỏ, và cửa sổ(window) có kích thước hợp lý để nhận ra các keypoint, nhưng với cùng kích cỡ cửa sổ và một góc có kích thước lớn thì sẽ trở nên bất hợp lý. Do đó, scale-space filtering được sử dụng để giải quyết vấn đề này. SIFT tính DoG (Difference of Gaussians) trên từng pixel bằng cách lấy diff của Gaussian Blur với 2 sigma khác nhau. Sau khi tính được DoG của toàn ảnh, xét trên từng pixel so sánh với 8 neighbors và 9 pixels tương ứng của scale ảnh ngay trên và 9 pixels tương ứng ở scale dưới, nếu pixel đó là local extrema (lớn nhất) thì nó sẽ được coi như là 1 keypoint ở scale đó. (potiental keypoint).

2. Keypoint localization

Khi đã lấy được tất cả những potential keypoints của ảnh, việc cần làm tiếp theo là lọc để ra những kết quả chính xác hơn, SIFT sử dụng chuỗi Taylor mở rộng để lấy vị trí của extrema chính xác hơn, rồi sau đó xét xem nếu intensity của extrema đó nhỏ hơn giá trị ngưỡng (0.03) thì sẽ loại keypoint đó.

Bên cạnh đó, DoG rất nhạy cảm với edge(đường), để loại bỏ edge keypoint, SIFT dùng concept giống Haris corner detector, nó dùng ma trận Hessian 2x2 để tính ra những đường cong chính. Khi eigen value lớn hơn threshold nào đó thì keypoint đó sẽ bị loại.

Như trên, SIFT có thể loại được keypoints có tương phản thấp, edge keypoint và giữ lại những keypoint hợp lý hơn.

3. Orientation assignment

Một hoặc nhiều orientation (hướng) sẽ được gắn cho từng vị trí keypoint dựa trên image gradient. Các phép tính sau đó trên ảnh sẽ tương ứng với từng orientation, scale và vị trí từng feature.

4. Keypoint descriptor

SIFT sẽ tính Keypoint descriptor bằng cách lấy 16x16 neighborhood(điểm liền kề) của keypoint đó, rồi chia thành 16 sub-blocks với kích thước 4x4. Với mỗi sub-block, ta sẽ tạo được 8 bin oritation (như hình dưới). Do đó tất cả sẽ có 128 bin giá trị tương ứng với 1 vector biểu hiện cho keypoint descriptor.

keypointDescriptor.png

SIFT trong OpenCV

Trong OpenCV có hỗ trợ của SIFT và SURF (một giải thuật có mục đích giống SIFT, hiệu năng tốt hơn),

SIFT::operator()(InputArray img, InputArray mask, vector<KeyPoint>& keypoints, OutputArray descriptors, bool useProvidedKeypoints=false)

Parameters:

img – Input 8-bit grayscale image

mask – Optional input mask that marks the regions where we should detect features.

keypoints – The input/output vector of keypoints

descriptors – The output matrix of descriptors. Pass cv::noArray() if you do not need them.

useProvidedKeypoints – Boolean flag. If it is true, the keypoint detector is not run. Instead, the provided vector of keypoints is used and the algorithm just computes their descriptors.

References

  1. http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_feature2d/py_sift_intro/py_sift_intro.html
  2. Distinctive Image Features from Scale-Invariant Keypoints

** Trong bài report lần tới, tôi sẽ tạo ứng dụng thực tế sử dụng SIFT/SURF giới thiệu đến mọi người. **

Bài liên quan

Giới thiệu về Scale-Invariant Feature Transform

Scale-Invariant Feature Transform (SIFT) là giải thuật trong lĩnh vực Computer Vision, dùng để nhận dạng và miêu tả những điểm đặc trưng(local features) trong ảnh. Giải thuật lần đầu được giới thiệu bởi David Lowe năm 1999. Giải thuật này(cùng với giải thuật anh em là SURF) được ứng dụng rộng rãi ...

Trịnh Tiến Mạnh viết 10:43 ngày 12/08/2018

Giới thiệu về knockout js ( Phần 2)

Ở phần một chúng ta đã biết tổng quan về knockout js (KO), cách tạo viewModel với observables và làm việc với observable arrays. Phần này chúng ta tiếp tục tìm hiểu về một trong những thành phần khá quan trọng của KO đó là Biding. Binding trong KO có một số điểm đáng chú ý như sau: Controlling ...

Trịnh Tiến Mạnh viết 23:47 ngày 11/08/2018

Giới thiệu về framework mã nguồn mở Apache Hadoop

I. Giới thiệu Framework Hadoop Hadoop là gì? Apache Hadoop là một framework dùng để chạy những ứng dụng trên 1 cluster lớn được xây dựng trên những phần cứng thông thường. Hadoop hiện thực mô hình Map/Reduce, đây là mô hình mà ứng dụng sẽ được chia nhỏ ra thành nhiều phân đoạn khác nhau, ...

Trịnh Tiến Mạnh viết 23:41 ngày 11/08/2018

[Network] Giới thiệu về PfSense

Để bảo vệ hệ thống mạng thì ta có nhiều giải pháp như sử dụng router cisco, dùng firewall cứng, firewall mềm của microsoft như ISA … Những thiết bị như trên rất tốn kinh phí vì vậy đối với các doanh nghiệp vừa và nhỏ thì giải pháp firewall mềm mã nguồn mở là một phương án hiệu quả. Pfsense ...

Bùi Văn Nam viết 23:12 ngày 11/08/2018

Giới thiệu về knockout js ( Phần 1)

Giới thiệu chung Mô hình của Knockout js(MVVM) Hướng dẫn cài đặt Observables trong Knockout js Giới thiệu chung Knockout(KO) là một thư viện của Javascript, nó giúp bạn tạo, hiển thị hay hiệu chỉnh User Interface(UI) với một data model được định nghĩa sẵn. Bất cứ khi nào bạn có phần ...

Bùi Văn Nam viết 22:57 ngày 11/08/2018
0