SIFT, SURF

SIFT (Scale-Invariant Feature Transform) is a classic and fundamental algorithm in computer vision that extracts and describes robust feature points invariant to image rotation, scale changes, and even slight viewpoint or illumination variations.

Scale-Invariant refers to the invariance to scale, meaning that a feature can be recognized even if the object's size in pixels changes due to it moving closer to or further from the camera.

Feature Transform means converting the image's pixel data into a 128-dimensional feature vector that is independent of scale and rotation.

Problem SIFT Aimed to Solve and Its Solution #

Traditional corner detectors like Harris Corner had a critical flaw: if an image was magnified, a corner might appear as a flat edge and no longer be recognized as a feature point. This meant that if two images were taken at different distances or magnifications, the same object could not be matched.

Therefore, the idea was mathematically implemented that if the object's size differs, one can compare images by progressively reducing their size.

By gradually applying blur to the original image and reducing its size, multiple resolution spaces (scale spaces) are created.

By calculating the differences between these spaces, prominent extrema are found regardless of scale, thus securing scale-invariant feature points.

Detailed Component Operation Principles and Structure #

The SIFT pipeline is largely structured into 4 stages.

Scale-space Extrema Detection #

First, a Scale Space is constructed. A set (octave) is created by progressively applying stronger Gaussian blur to an image, and this process is repeated by halving the image's resolution to create the next set. This is a Gaussian Pyramid.
DoG (Difference of Gaussians) images are generated by subtracting the pixel values of two adjacent Gaussian blurred images. $D(x, y, \sigma) = L(x, y, k\sigma) - L(x, y, \sigma)$
For extrema detection, a specific pixel in a DoG image is selected as a candidate Local Extrema feature point if it is either greater than or smaller than all 8 surrounding pixels in the same layer, and all 18 surrounding pixels in the layers above and below, totaling 26 pixels.

Keypoint Localization #

Among the found candidates, points corresponding to noise or unfavorable for matching are filtered out.
Precise sub-pixel locations are calculated using Taylor expansion.
Unstable points located in flat regions or on edges (lines) are discarded through principal curvature analysis.

Orientation Assignment (Ensuring Rotation Invariance) #

The gradient direction and magnitude of pixels around the feature point's location are calculated.
A histogram is created by dividing 360 degrees into 36 bins (intervals), and the direction with the highest frequency (the strongest gradient direction) is set as the reference orientation for that feature point.

Keypoint Descriptor Generation #

A 16 x 16 pixel region around the feature point is extracted.
This region is rotated by the previously determined reference orientation, ensuring it always faces the same upright direction even if the original image is rotated (rotation invariance).
The 16 x 16 region is divided into 16 sub-blocks of 4 x 4 size.
For each block, an 8-direction gradient histogram is calculated.
As a result, a 128-dimensional floating-point vector (16 blocks x 8 directions) is completed.

While SIFT is powerful, it requires operations on 128-dimensional floating-point vectors, so unlike ORB's binary Hamming distance, it must use L2 Euclidean distance for matching.

import cv2
import numpy as np

def extract_sift_features(image_path):
    # 1. 이미지 로드 (연산량 감소를 위해 Grayscale 변환)
    img = cv2.imread(image_path)
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

    # 2. SIFT 객체 생성
    # 파라미터 튜닝이 가능하지만 보통 기본값을 사용합니다.
    # nfeatures: 추출할 최대 특징점 수 (0은 무제한)
    # nOctaveLayers: 각 옥타브(해상도 단계)별 블러 이미지 수
    # contrastThreshold: 이 값이 클수록 대비가 낮은 약한 특징점은 무시됨
    sift = cv2.SIFT_create(nfeatures=500, contrastThreshold=0.04)

    # 3. 특징점 검출(Detection) 및 기술자 추출(Description) 동시에 수행
    keypoints, descriptors = sift.detectAndCompute(gray, None)

    print(f"SIFT 추출된 특징점 개수: {len(keypoints)}개")
    
    if descriptors is not None:
        # Descriptor의 Shape은 (N, 128)이며 데이터 타입은 float32 입니다.
        print(f"Descriptor 행렬 형태: {descriptors.shape}")
        print(f"Descriptor 데이터 타입: {descriptors.dtype}")
        
        # 첫 번째 특징점의 128차원 실수 벡터 확인
        print("\n첫 번째 특징점의 128차원 벡터 중 앞부분 10개 값:")
        print(descriptors[0][:10])

    # 4. 시각화 (특징점의 크기와 방향을 화면에 표시)
    # DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS 플래그를 사용하면
    # 각 특징점의 Scale(원의 크기)과 Orientation(원의 내부 선 방향)이 함께 그려집니다.
    img_with_keypoints = cv2.drawKeypoints(gray, keypoints, img.copy(), 
                                           flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
    
    return img_with_keypoints, keypoints, descriptors

# 매칭을 할 때 주의점: SIFT는 이진 벡터가 아니므로 cv2.NORM_HAMMING이 아닌 cv2.NORM_L2를 사용합니다.
# bf = cv2.BFMatcher(cv2.NORM_L2, crossCheck=True)
# matches = bf.match(des1, des2)

Therefore, while its performance is excellent, it suffers from slow computation speed. To address this SIFT computation bottleneck, a concept called SURF emerged, which solves it with a mathematical trick (integral images).

SURF Speeded Up Robust Features #

SURF, like SIFT, is an algorithm that extracts feature points invariant to image scale changes and rotation.

However, its characteristic feature is that it dramatically improved processing speed by 3 to 7 times compared to SIFT by introducing powerful mathematical approximation techniques, namely Integral Image and BoxFilter, to overcome SIFT's limitation of extremely slow computation.

Speeded Up: Emphasizes that the computational bottleneck of SIFT was resolved, and speed was significantly boosted through the mathematical approximations mentioned earlier.
Robust Features: Means that even with simplified computations, it still finds the same feature points without being affected by disturbances such as scale changes, rotation, illumination changes, and slight viewpoint variations.

Problem SURF Aimed to Solve and Its Solution #

Enormous computational load of Gaussian blur: SIFT had to repeatedly perform Gaussian blur operations on the original image to create the scale space. The process of multiplying and adding complex normal distribution weights for each pixel consumed too much CPU.

Cost of image resizing: SIFT compared images by halving them into multiple octaves, and the physical reduction of images itself incurred memory copying and additional computational costs.

Heavy 128-dimensional vector: SIFT's 128-dimensional descriptor was too heavy during the matching phase.

Therefore, the problem was solved by approximating the complex curved Gaussian with simple rectangular box filters, and instead of reducing the image, increasing the size of the filter.

SURF drastically simplifies the bell-shaped kernel of the Gaussian function into a rectangular box filter. It also achieves O(1) constant filtering speed by using the integral image data structure, which calculates the sum of pixels in a specific rectangular region with just 4 additions and subtractions. Furthermore, it completely eliminated the cost of image resizing by progressively increasing the filter size (9x9, 15x15, 21x21) instead of shrinking the image.

How it Works #

Integral Image Operation #

The concept is that the integral image value $I_{\Sigma}(x, y)$ at position (x, y) is the sum of all pixel values within the rectangular region from the origin (0, 0) to (x, y) of the original image.

Once an integral image is created in memory, even for very large rectangular filter (Box Filter) operations, the sum of a region can be found with just 3 arithmetic operations using only the values of its 4 corners. The computation speed becomes constant regardless of the filter size.

Fast Hessian-based Feature Point Detection #

The Hessian Matrix uses the determinant of the Hessian matrix, a second-order partial derivative matrix, instead of SIFT's DoG, to find extrema where pixel value changes are most extreme compared to their surroundings.

The Gaussian second-order derivative operators of the Hessian matrix are replaced with rectangular Box Filters ( $D_{xx}, D_{yy}, D_{xy}$ ) for immediate computation on the integral image.

Orientation Assignment #

Unlike SIFT, which calculates complex gradient histograms, SURF calculates Haar Wavelet Responses in a circular region around the feature point.

Simply put, it measures the change in brightness by applying rectangular patterns along the x and y axes. This is also calculated instantly thanks to the integral image, and the reference orientation is set based on the sector with the strongest response.

64-dimensional Descriptor Generation #

The region around the feature point is divided into 4 x 4 sub-regions, totaling 16 areas.

For each area, horizontal/vertical Haar Wavelet responses are calculated, and their directional components, sum, and sum of absolute values ( $\sum d_x, \sum d_y, \sum |d_x|, \sum |d_y|$ ) are extracted.

A 64-dimensional floating-point vector (16 areas x 4 values) is completed, and the descriptor size is halved from SIFT's 128 to 64, making matching speed more than twice as fast.

Example #

The SURF algorithm was protected by patent for a long time, so

it is not included in the basic opencv-python package but is isolated in the xfeatures2d module of the extended opencv-contrib-python package. Although the patent has recently expired, usage may vary depending on the version environment.

import cv2
import numpy as np

def extract_surf_features(image_path):
    # 1. 이미지 로드 및 Grayscale 변환
    img = cv2.imread(image_path)
    if img is None:
        raise ValueError("이미지를 찾을 수 없습니다.")
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

    try:
        # 2. SURF 객체 생성
        # hessianThreshold: 헤시안 행렬식의 임계값. 이 값이 클수록 더 강한 특징점(선명한 코너)만 추출됩니다.
        # 기본값은 보통 300 ~ 500 사이로 설정합니다.
        # 주의: OpenCV 버전에 따라 cv2.SURF_create() 또는 cv2.xfeatures2d.SURF_create()를 사용해야 합니다.
        surf = cv2.xfeatures2d.SURF_create(hessianThreshold=400)
        
        # 64차원이 아닌 128차원 벡터(Extended SURF)를 원할 경우 파라미터 변경
        # surf.setExtended(True) 

        # 3. 특징점 검출 및 디스크립터 계산
        keypoints, descriptors = surf.detectAndCompute(gray, None)

        print(f"SURF 추출된 특징점 개수: {len(keypoints)}개")
        
        if descriptors is not None:
            # 기본 SURF의 Descriptor Shape은 (N, 64)이며 데이터 타입은 float32 입니다.
            print(f"Descriptor 행렬 형태: {descriptors.shape}")
            
            # 첫 번째 특징점의 64차원 벡터 중 앞부분 일부 확인
            print("\n첫 번째 특징점의 64차원 벡터 중 앞 10개 값:")
            print(descriptors[0][:10])

        # 4. 시각화 
        # DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS를 통해 특징점의 크기(Scale)와 방향 표시
        img_with_keypoints = cv2.drawKeypoints(gray, keypoints, img.copy(), 
                                               flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
        
        return img_with_keypoints, keypoints, descriptors

    except cv2.error as e:
        print("\n[오류] 현재 설치된 OpenCV 버전에서 SURF를 지원하지 않습니다.")
        print("SURF는 특허 문제로 opencv-contrib-python 패키지의 특정 버전에서만 사용 가능할 수 있습니다.")
        print(f"상세 에러: {e}")
        return None, None, None

# 매칭 단계에서는 SIFT와 동일하게 유클리디안 거리(NORM_L2)를 사용해야 합니다.
# bf = cv2.BFMatcher(cv2.NORM_L2, crossCheck=True)
# matches = bf.match(des1, des2)

DoG vs Hessian Matrix #

DoG and Hessian Matrix are core mathematical components that determine which points SIFT and SURF, respectively, recognize as extrema feature points in an image. Both methods aim to find blobs (point-like clusters) or corners where image brightness changes abruptly, but their approaches differ.

DoG Difference of Gaussian - SIFT #

DoG is a method that approximates the change in the first derivative (Gradient) by subtracting blurred images.

The concept is to take an image with a weak Gaussian blur and subtract it from an image with a strong Gaussian blur.

Blurring removes fine noise from the image, leaving only large structures.
Subtracting two images blurred with different strengths causes flat backgrounds to become zero, leaving only edges or corners with prominent brightness changes, like outlines. This acts as a band-pass filter.
In the DoG image space thus obtained, extrema points that are uniquely larger or smaller than surrounding pixels are found as feature points.

D(x, y, \sigma) = L(x, y, k\sigma) - L(x, y, \sigma)

Here, L can be thought of as a Gaussian blurred image.

Its implementation is intuitive and accurate, but it has the characteristic of high computational cost because multiple blurred images must be created.

Hessian Matrix - SURF #

The Hessian matrix method finds feature points by calculating the second-order partial derivative (curvature) of the pixel brightness function.

Assuming image brightness as the height of a 3D terrain, it measures how convex or concave that terrain is.

At a specific pixel location, the second-order derivative in the $x$ direction ( $L_{xx}$ ), the second-order derivative in the $y$ direction ( $L_{yy}$ ), and the diagonal derivative ( $L_{xy}$ ) are calculated.
These values form a 2x2 matrix.

H = \begin{bmatrix} L_{xx} & L_{xy} \\ L_{xy} & L_{yy} \end{bmatrix}

The determinant of this matrix, $\det(H) = L_{xx}L_{yy} - (L_{xy})^2$ , is calculated. If the determinant value is positive and large, it mathematically guarantees that the point is a distinct blob feature point, convex or concave in all directions.

SURF applied this for acceleration purposes: it replaces this complex second-order derivative Gaussian operation with simple black and white rectangular box filters, and by using integral images to process box filter operations in O(1) time, it achieves overwhelmingly faster speeds than DoG.

In summary, SIFT's DoG finds outlines by subtracting two blurred images, while SURF's Hessian Matrix is a mathematical optimization approach that measures the curvature of the terrain through second-order derivatives, but approximates the computation with rectangular boxes.