[Computer Vision] Blob Detection
Recap: Harris Corner Detector
Harris Corner Detector 에서 이미지에서 코너를 검출해 내기 위해 sliding window 를 사용하였다. Sliding window의 intensity change가 모든 방향으로 크면 corner가 된다라는 접근으로 시작하였다. 어떤 포인트 $(x,y)$ 가 코너인지 아닌지 확인하기 위해서 각 포인트에서 x 방향으로 u 만큼, y 방향으로 v 만큼 이동한 sliding window와 이동하기 전 sliding window의 intensity change를 $E(u,v)$ 함수로 계산하였다. 코너에서는 $E(0,0)$ 이외에 모든 점에서 intensity change가 크기 때문에 E 함수가 peak 을 가지기 때문에 $E(u,v)$를 모든 u,v에 대하여 계산하는 대신 quadratic surface approximation을 하여 빠르게 E 함수를 만들어 낼 수 있다. Taylor series를 사용하여 E 를 전개한 다음 second derivative를 제외한 항들을 0으로 맞추고, 남은 항을 second moment matrix라고 정의한 후 cornerness를 구한다. 이때 불필요하게 많은 점들이 검출되기 때문에 non-maxima suppression을 하여 불필요한 코너들을 제거하면 유의미한 점들만 남게 된다.
Problems with corners
Corner detection을 하는 이유는 이미지 내에서 feature point들을 얻어내기 위함이다. 3D reconstruction이나 recogntion과 같은 작업을 할 때 이미지 픽셀 하나하나를 사용하여 계산하면 시간이 너무 오래걸리기 때문에 이미지를 대표하는 점들을 검출해 내야 하는데 이런 점들을 feature point라고 하고 저번 포스팅에서는 corner를 검출하는 Harris corner detection을 알아봤다. Corner가 유의미한 feature point를 주기는 하지만 큰 문제가 있다. Corner를 확대하면 edge가 되어버린다는 것이다.
예를 들어 어떤 한 물체를 서로 다른 방향에서 촬영하고, 코너들을 잡아 매칭을 시키고 싶은데, 한 사진에서는 코너이지만 다른 사진에서는 코너로 검출이 되지 않을 수 있다. 따라서 이미지에서 코너만 검출하고 매칭을 시킨다면 매칭 결과가 좋지 않을 것이다.
따라서 corner detection은 scale-invariant 하지 않다라고 할 수 있는데, 우리가 원하는 feature point들은 scale-invariant 해야만 feature point들을 이용한 작업들이 정확한 결과를 낼 수 있다 (가까이서 보나 멀리서 보나 같은 특징을 가지고 있어야 하기 때문). 그렇게 생각해 낸 것이 corner 대신 blob을 검출하는 것이다.
Blob Detection
Blob Detection 이란 주변보다 intensity 가 높은 point들을 찾고 사이즈와 모양을 계산하여 feature point를 검출하는 방식이다. 우선 2차원 이미지에서 blob detection을 들어가기 전 1차원에서부터 살펴보자.
1-dimensional edge detection
1차원 그래프에서 edge란 intensity 가 어느 순간 갑자기 올라가는 unit step function 형태의 함수로 표현할 수 있다.
첫번째 그래프가 edge의 signal이고, 두번째 그래프가 Gaussian function을 두번 미분한 함수이다. Edge와 Laplacian of Gaussian 을 convolve를 해주면 세번째 그림과 같은 response가 나오는데, 정확히 edge에서 0이 된다는 것을 볼 수 있다.
정리하자면 1-dimensional edge signal에 Laplacian of Gaussian을 convolve를 하였을때 response에서 0이 되는 점이 edge position 이다라는 것을 알 수 있다.
1-dimensional blob detection
이미지에서 blob은 주변보다 intensity 가 높은 지역을 의미한다. 따라서 1차원에서의 blob은 rising edge와 falling edge가 같이 있는 형태의 signal 이 된다.
LoG convolved signal을 봤을때 falling edge에서는 rising edge에서랑 대칭된 response가 나온다는걸 볼 수 있다. 여기서 blob의 사이즈가 작아질때 response 두개가 superpose 하게 되고, blob의 center에서 response가 가장 크다라는 것을 볼 수 있다.
여기서 한가지 중요한 점은 Gaussian function의 standard deviation을 우리가 조절할 수 있다는 것이다. LoG의 가장 중요한 성질은 scale-normalized LoG convolved signal의 x-intercept가 blob의 x-intercept 와 맞을때, response가 최대가 된다 (scale-normalized LoG 는 LoG에 std squared를 곱해준 함수이다. $ LoG_{sn} = \sigma^2 \nabla^2G $). 아래 그림을 보면 standard deviation이 어떤 optimal 한 값을 가질때 response가 최대가 된다.
따라서 optimal std가 알려주는 것은 blob의 사이즈이다. LoG 함수가
$ \nabla^2G = (-2+\frac{x^2+y^2}{\sigma^2}) \frac{e^-{\frac{x^2+y^2}{2\pi\sigma^4}}}{2\pi\sigma^4} $
이므로 LoG를 0으로 잡으면 $ -2+\frac{x^2+y^2}{\sigma^2} = 0 $ 이 된다. 따라서 $ x^2+y^2=2\sigma^2 $,
$ \sigma_{opt} = \frac{r}{\sqrt{2}} $가 되게 된다. 여러가지 std 값을 조절해가며 maximum scale-normalized LoG response 를 얻었을때의 optimal 값을 찾고, 이 식을 이용하여 blob의 사이즈인 radius 를 찾을 수 있게 된다.
Difference of Gaussian (DoG)
LoG 보다 계산을 조금 더 효율적으로 하기 위해 DoG를 사용한다. LoG 에서는 $ LoG = \sigma^2 (G_{xx}(x,y,\sigma) + G_{yy}(x,y,\sigma))$ 이었지만 이 함수를 $ DoG = G(x,y,k\sigma) - G(x,y,\sigma)$ 로 approximate 할 수 있다. 이러한 방식을 DoG라고 한다. 이때 k는 임의로 정할 수 있는 상수이다. 따라서 이미지를 다른 sigma 값들로 gaussian blurring 처리한 후, 처리된 이미지 두개의 intensity 차이를 구하면 LoG 를 approximate 할 수 있다.
LoG와 마찬차지로 DoG에서 sigma를 바꿔가며 local maximum을 찾고, 그때의 optimal sigma를 활용하여 radius를 찾을 수 있다.
Harris-Laplace
지금까지는 blob을 감지하고 알맞은 scale (radius) 를 계산하여 feature point를 찾았지만 blob 말고도 corner를 검출하고 여기에 scale을 넣어줄 수도 있다. 저번과 마찬가지로 Harris corner detection을 하고 추출된 feature point들을 각각 다른 sigma로 convolve 된 이미지들을 찾는다. 이 이미지들로 DoG를 사용해서 maximum 이 되는 optimal sigma를 찾으면 $ \sigma_{opt} = \frac{r}{\sqrt{2}}$ 를 써서 scale 을 구할 수 있다. 원래 Harris corner detection은 scale invariant 하지 않지만 scale 을 추가해준다면 확대를 해도 그만큼의 scale의 변화가 있기 때문에 scale invariant 하다.
Affine Normalization
지금까지는 blob에 radius를 추가하여 scale invariant한 feature point들을 찾았다. 하지만 카메라가 찍는 각도가 달라진다면 affine transformation이 일어나고 blob이 원으로 한정되어 있다면 올바른 feature point를 찾아 matching 하는게 불가능하다. 따라서 원을 affine normalization을 해주면 원이 타원으로 바뀌게 된다. 이때 타원의 모양은 second moment matrix로 찾을 수 있다. Second moment matrix의 eigenvalue들이 타원의 장축과 단축이 되고, eigenvector가 uv space의 basis를 회전시켜 돌아간 타원을 만든다 (Harris corner detection 포스팅 참고).
References
KAIST MinHKim CS484 Introduction to Computer Vision