[Computer Vision / Image Precessing] SURF (Speeded-Up Robust Features)

SURF(Speeded Up Robust Features)는 영상의 지역과 유사성 불변(invariant)을 나타내고 비교하기 위한 빠르고 강력한(robust) 알고리즘입니다. SURF의 주 목적은 박스 필터를 사용하여 연산자를 빠르게 계산함으로써, 추적이나 객체 인식과 같이 실시간 응용이 가능하게 하는 데 있습니다.

 

 

 

SURF는 다음 두 단계로 구성됩니다.

• 특징 추출 (Feature Extraction)
• 특징 기술 (Feature Description)

 

 

특징 추출 (Feature Extraction)

특징점 검출을 위한 접근법은 가장 기본적인 헤시안 행렬 근사(Hessian matrix approximation)를 이용합니다.

 

적분 영상 (Integral Images)

적분 영상 혹은 합산 영역 테이블의 개념은 1984년에 소개되었습니다. 적분 영상은 주어진 영상 또는 격자 내 사각형 부분 집합의 합(픽셀 값)을 빠르고 효과적으로 계산하기 위한 방법으로 사용됩니다. 또한 주어진 영상 내 평균 강도(intensity)를 계산하는 데 사용되기도 합니다.

 

이는 박스 형태의 컨볼루션 필터를 빠르게 계산할 수 있도록 만듭니다. x = (x, y)^T 위치에서의 적분 영상 I_∑(x)의 입력은 원점과 x에 의해 형성된 직사각형 영역 내의 입력 영상 I에 있는 모든 픽셀의 합을 나타냅니다.

 

 

I_∑를 계산하고나면, 영상의 크기에 관계없이 사각형 영역에 대한 강도의 합을 계산하는데 네 개의 부분 영상만이 사용됩니다. (참고 : https://vision0814.tistory.com/172)

 

헤시안 행렬 기반 관심점 (Hessian matrix-based interest points)

SURF는 연산 시간과 정확성 측면에서 좋은 성능을 보이기 때문에 헤시안 행렬을 사용합니다. 위치와 스케일(헤시안-라플라스 검출기, Hessian-Laplace detector)을 선택하기 위해 다른 측정법을 사용하는 대신, SURF는 위치, 스케일 모두에 대해 헤시안 행렬의 행렬식을 사용합니다. 픽셀이 주어졌을 때, 해당 픽셀의 헤시안 행렬은 다음과 같습니다.

 

 

모든 스케일에 적용하기 위해 가우시안 커널을 사용해 영상을 필터링하였고, 따라서 X = (x, y) 점이 주어졌을 때 스케일 σ의 점 x에서의 헤시안 행렬 H(x, σ)는 다음과 같이 정의됩니다.

 

 

여기서 L_xx(x, σ)는 점 x에서의 영상 I와 2차 미분한 가우시안 커널을 컨볼루션한 것이고, L_xy(x, σ), L_yy(x, σ)도 같은 연산을 적용한 결과입니다. 가우시안 커널은 스케일 공간에 대한 분석에는 최적이지만, 실제로는 가우시안 함수의 연속적인 값을 이산화시키고(discretized), 잘라내야(cropped) 합니다. 이로 인해 π/4(45º)의 홀수 배수만큼 영상 회전 시 재현성(다른 시점에서 동일한 특징점을 찾을 수 있는지에 대한 신뢰도)이 손실됩니다. 그러나 이는 헤시안 기반 검출기의 일반적인 취약점에 해당하며, 그럼에도 불구하고 검출기의 성능은 여전히 우수하고, 이러한 성능 저하가 이산화 및 잘라냄(cropping)으로 인한 빠른 컨볼루션에 대한 장점에 미치는 영향은 미미합니다.

 

헤시안 행렬의 행렬식을 계산하기 위해서는 먼저 가우시안 2차 미분 커널을 적용해야 합니다. SIFT 알고리즘을 개발한 데이비드 로우(David G. Lowe) 가 LoG(Laplacian of Gaussian) 근사를 통해 성공한 이후, SURF는 박스 필터를 사용하여 근사치(컨볼루션과 2차 미분 모두)를 더욱 강화시킵니다. 이러한 가우시안 2차 미분 커널의 근사는 크기에 상관없이 적분 영상을 이용하여 매우 적은 비용으로 평가할 수 있으며, 이것이 SURF가 빠른 이유 중 하나입니다.

 

xy 방향 가우시안 편미분 함수

 

y 방향 가우시안 편미분 함수

 

위 이미지의 9 x 9 박스 필터는 σ = 1.2인 가우시안 2차 미분 함수에 대한 근사입니다. 이와 같이 Dxx, Dyy, Dxy에 대한 근사도 표현할 수 있습니다. 이제 헤시안(근사) 행렬식을 다음과 같이 나타낼 수 있습니다.

 

w = 0.9 (논문에서 제안된 값)

 

스케일 공간 표현 (Scale-space representation)

스케일 공간은 보통 영상 피라미드(image pramids)로 구현됩니다. 영상은 가우시안 커널을 통해 반복적으로 필터링(smoothing)되고, 그 다음 서브 샘플링(sub-sampled) 되어 더 높은 단계의 피라미드를 구성합니다. 그러나 SURF는 박스 필터와 적분 영상을 사용하기 때문에 이전에 필터링된 레이어의 출력에 동일한 커널을 반복적으로 적용할 필요가 없으며, 대신 정확하게 동일한 속도로 원본 영상에 직접, 혹은 병렬로 커널을 적용할 수 있습니다. 따라서 영상 크기를 반복적으로 줄이는 대신 커널의 크기(9 x 9 → 15 x 15 → 21 x 21 → 27 x 27 → · · ·)를 업스케일링(up-scaling)하는 방식으로 스케일 공간을 분석합니다. 이에 따라 각각의 새로운 옥타브(octave)에 대해 커널의 크기 증가량은 두 배가 되고, 동시에 관심점의 추출을 위한 샘플링 간격도 두 배가 될 수 있어 일정한 비용으로 커널을 업스케일링 할 수 있습니다. 영상 및 스케일에 걸쳐 관심점을 지역화(localize : 위치를 측정)하기 위해 3 x 3 x 3 영역의 이웃(neighborhood)에 비최대치 억제(nonmaximum suppression)가 적용됩니다.

 

 

 

특징 기술 (Feature Description)

SURF 기술자(descriptor)는 두 단계로 만들어집니다. 첫 번째 단계는 특징점 주변 원 영역의 정보를 기반으로 재현 가능한(reproducible : 측정한 결과가 다시 나타나는 성질) 방향(orientation)을 고정하는 작업으로 구성됩니다. 그 다음, 선택된 방향에 맞춰 정렬된 정사각형 영역을 구성하고 해당 영역에서 SURF 기술자를 추출합니다.

 

방향 할당 (Orientation Assignment)

회전에 불변하기 위해 SURF는 관심점에 대해 재현 가능한 방향을 식별합니다. 이를 위해 다음과 같은 단계를 진행합니다.

1. 먼저 x및 y 방향으로 Haar-wavelet 응답(responses)의 합을 계산하는데, 이는 특징점이 검출된 스케일 s에서 특징점 주변 반경 6s(scale)의 원 내부 이웃에서 계산합니다. 또한 샘플링 단계는 s로 선택된 스케일에 따라 달라지며, wavelet 응답은 현재 스케일 s에서 계산됩니다. 따라서 높은 스케일의 wavelet 크기는 큽니다. 그러므로 빠른 필터링을 위해 적분 영상이 다시 사용됩니다.
2. 스캔 영역에서 수직 및 수평 wavelet 응답의 합을 계산한 다음, 가장 큰 합을 가진 방향을 찾을 때까지 스캔 방향을 변경하고(+π/3) 다시 계산합니다. 이 방향이 특징 기술자의 주 방향 성분입니다.

 

 

기술자 구성 요소 (Descriptor Components)

이제 기술자를 추출할 차례입니다.

1. 첫 번째 단계는 특징점을 중심으로 이전 과정을 통해 얻은 방향을 따라 정사각형 영역을 구성합니다. 이 윈도우의 크기는 20s입니다.
2. 해당 영역은 균등하게 4 x 4 하위 영역으로 분할됩니다. 각 하위 영역에 대해 일정한 간격의 5 x 5 샘플 포인트에서 몇가지 간단한 특징을 계산합니다. 단순성의 이유로, dx를 수평 방향의 Harr wavelet 응답으로 부르고, dy를 수직 방향의 Haar wavelet 응답이라고 부르겠습니다(필터 크기 2s). 기형적인 기하학적 변형(deformations)과 지역화 오류에 대한 강건성(robustness)을 높이기 위해, dx와 dy 응답은 먼저 특징점 중심의 가우시안 커널(σ = 3.3s)로 가중치를 부여받습니다.

 

 

그러면 dx, dy wavelet 응답이 각 하위 영역에 걸쳐 합산(summed up)되고, 특징 벡터에 대한 첫 번째 성분 집합을 형성합니다. 강도 변화의 극성에 대한 정보를 갖기 위해, 응답의 절댓값의 합인 |dx|와 |dy|를 추출합니다. 따라서, 각 하위 영역은 각각의 기본 강도 구조인 V = (∑dx, ∑dy, ∑|dx|, ∑|dy|)에 대한 4차원 기술자를 갖습니다. 이는 길이 64의 모든 4 x 4 하위 영역에 대한 기술자 벡터를 만들어냅니다.(SIFT에서 기술자는 128차원 벡터입니다. 이것이 SURF가 SIFT보다 더 빠른 이유입니다.)

 

 

(원 저작자에게 이용 허락을 받고 옮긴 글입니다.)

https://medium.com/data-breach/introduction-to-surf-speeded-up-robust-features-c7396d6e7c4e

Introduction to SURF (Speeded-Up Robust Features)