snaag
commented
10 months ago 멋진 글이네요 다만 제가 이해를 못할뿐... 블러 처리가 되어가는 룩말이가 기억에 남습니다요 🦓
Open mingnuj opened 10 months ago
snaag
commented
10 months ago 멋진 글이네요 다만 제가 이해를 못할뿐... 블러 처리가 되어가는 룩말이가 기억에 남습니다요 🦓
[01-04] 이미지 특징 추출#1에 이어서 쓰는 2편이다. SIFT에 대해 다루고자 한다. 제대로 분석하려니 오래 걸려서 오늘은 SIFT 중간까지 작성.. 너무 길다....
SIFT
Scale-Invariant Feature Transform: 이미지의 크기와 회전에 불변하는 특징을 추출한다.
추출 알고리즘
1. Scale-space extrema detection (scale-invariance)
이미지의 크기를 변환 시켜 극대점, 극소점을 찾는다. (keypoint candidates)
이미지의 scale-space $L(x, y, σ)$는 아래와 같이 정의된다. $$L(x, y, σ)=G(x, y, σ)*I(x,y)$$
입력 된 $σ$에 따라서 filter의 정도가 달라지는데, 해당 논문에서는 좀 더 안정적인
keypoint를 찾기 위해 Gaussian 필터를 확장해서 사용한다. 논문에서는difference-of-Gaussian(이하 DoG)에scale-space extrema(extrema는 극값을 나타내는 것으로 보임)를 적용했다고 기술되어 있다. Gaussian 필터의 극값을 $D(x,y,σ)$라고 하면, $$D(x,y,σ) = (G(x,y,kσ) - G(x,y,σ))*I(x,y) = L(x,y,kσ)-L(x,y,σ)$$ 상수 곱셈 인자 $k$로 분리 된 가까운 이미지 2개로부터 계산해낼 수 있다.예를 들어, 아래는 변환한 이미지의 크기에 따라서 놓은 집합체이다. 이미지 크기($k$) 별로 Octave 1, 2, 3, 4를 가지고, 각 Octave 별로 가우시안 필터를 이용하여 bluring한 5개의 이미지를 만든다
$D(x,y,σ)$를 사용하는 이유는 몇 가지 있는데,
Smoothed이미지L은 어떤 경우에도scale-space feature description을 위해서는 계산 되어야 하므로,D는 간단하게 이미지를 뺌으로써 계산할 수 있다.DoG함수는scale-normalized Laplacian of Gaussian에 거의 근접한 값을 보인다.scale-normalized Laplacian of Gaussian: Laplacian은 벡터장 내에서 벡터의 흐름이 균일하지 못한 정도를 나타낸다. 따라서 이는 Gaussian이 균일하지 못한 정도를 크기에 따라 정규화 해서 나타낸 값으로 해석된다. 읽으면서 쓰는 것이라 틀릴 수 있으니 자세한 내용은 Scale-space theory: A basic tool for analysing structures at different scales(Lindeberg, 1994) 참고.. 결론적으로는 $G(x, y, kσ) − G(x, y, σ) ≈ (k − 1)σ^2∇^2G$라고 한다. 여기서 $σ^2∇^2G$는 Laplacian이다. 이는DoG가 상수 인자( $k$ )만큼 다른 스케일을 가질 때,scale-invariant Laplacian에 필요한 $σ^2$ 스케일 정규화를 이미 내재하고 있음을 보여준다. 방정식의 계수 $(k-1)$은 모든 scale에 걸쳐 상수이므로 극값에는 영향을 주지 않는다.아래는
같은 octave 내에서 초기 이미지는 Gaussian과 반복적으로 convolution 되어 왼쪽에 표시된 scale-space 이미지를 만든다. 인접한 두 개의 이미지를 추출, 우측의
DoG연산을 직관적으로 나타낸 그림이다.DoG이미지가 생성된다. 각 Octave를 만든 후, 2배 downsampling 하고 반복한다.극대값 또는 극소값을 얻기 위해서 각각의 octave에서 scale이 다른 3개의 이미지를 아래 그림처럼 겹친다.
현재 scale의 인접 픽셀 8개와, 인접 scale의 픽셀 9개를 비교할 수 있게 된다. 픽셀은 이웃 모두보다 크거나, 작을 때만 선택되며, 처음 몇 번의 검사 후에 대부분의 sample point가 제거되므로 cost가 합리적으로 낮아진다.
지금까지는 픽셀 단위로 계산하였으나, 극값은 픽셀 사이에 존재할 수 있다.
하지만, 진짜 극값의 위치에 접근할 수 없으므로 subpixel의 위치를 수학적으로 찾아내야 한다. 어떻게 찾아내는가? => 테일러 2차 전개
2. Keypoint localization
Feature matching 시 불안정할 keypoint 제거 및 위치를 정확히 한다.
scale-space함수 $D(x, y, σ)$에 대해서 $$D(x) = D + {{∂D^T \over ∂x} x} + {{1\over2}{x^T}{{{∂^2}D\over∂x^2}x}}$$미분 해서 0이 되는 지점이 극값이 된다 => 알고리즘이 좀 더 안정적인 성능을 냄위의 방법을 적용한 keypoint 중
bad keypoint를 제거 하기 위해특정 threshold보다 낮은 keypoint를 제거한다.3. Orientation assigment
Scale-invariant를 만족 시키는 keypoint에 대해 방향을 할당해주는 역할을 한다. 각 keypoint 주변 gradient의 크기와 방향을 수식을 통해 알아내는 것으로 시작한다.
가우시안 블러를 적용 후 아래 수식을 통해 크기와 방향을 구한다.
Gradient magnitudes: 크기 $$m(x,y) = \sqrt{(L(x+1, y) - L(x-1, y))^2 + (L(x, y+1) - L(x, y-1))^2}$$Gradient orientations: 방향 $$θ(x, y) = tan^{−1}((L(x, y + 1) − L(x, y − 1))/(L(x + 1, y) − L(x − 1, y)))$$Gradient의 크기에는 가우시안 가중 함수를 이용,
keypoint에 가까울 수록 큰 값을 가지고 멀 수록 작은 값을 가지도록 한다.위 2개 수식을 통해 얻은 크기와 방향으로
가로축이 방향,세로축이 크기인 Histogram을 그린다.360도의 방향을 0~9, 10~19, ..., 350~359도로 36개로 쪼갠다. 각각을 bin이라고 한다.
4. Keypoint descriptor
1 ~ 3의 방법으로 드디어 keypoint를 결정했으니, 이들을 식별하기 위한 정보를 부여하는 과정이 필요하다. 각 keypoint를 식별하는 descriptor를 만드는 방법을 기술해보자.
pixel gradient의 크기와 방향을 계산 => 8개의 bin을 가진 histogram을 그린다.128개의 feature vector를 얻는다.드디어 정리 마무리... 아무튼 위와 같은 과정을 거치면서
scale-invariant한 특징을 추출할 수 있게 된다. 꽤나 느리지만 다른 알고리즘의 기반이 되므로 익혀두는 것이 좋을 듯 하다.참고