SURF는 2008년 Herbert Bay가 제안한 방법입니다.

[Bay 08] Bay, Herbert, et al. "Speeded-up robust features (SURF)." Computer vision and image understanding 110.3 (2008): 346-359.

2004년 SIFT의 등장 이후 물체의 descriptor에 대한 관심이 높아진 이후로 많은 연구가 있었습니다.

SIFT의 최대 단점인 연산의 복잡성을 해소 하기 위한 방법으로 한때 많은 관심(성능)을 보인 

SURF 기술자를 정리해 봅시다.

위 논문에서는 SIFT 외에도 다른 방법들과 비교를 했지만 SIFT 못지 않게 성능을 유지하며 계산 속도를

향상 시키고자 했습니다.

그래서 속도 향상을 위해 제안한 방법을 요약하면 크게 총 3가지로 정리할 수 있습니다.

1. Integral Image(적분 이미지) 이용

 SURF에서는 SIFT와는 다르게 적분 영상을 사용하여 관심점과 영역을 찾습니다. 관심점 계산을 위해 

고속 헤시안 검출(Fast Hessian Detector)를 사용하는데, 이때 적분 영상을 사용합니다.

적분 영상이란 말 그대로 영상을 적분하는것을 말합니다.

적분이란? 고등학교 학생 때의 기억을 더듬어 보면 어떤 영역의 넓이를 구했던 것을 생각해 볼 수 있습니다.

그렇다면 영상의 적분이란 영상이 갖는 영역의 넓이(밝기의 합)을 구하는 것을 추론할 수 있습니다.

영상의 밝기의 합은 그냥 선형으로 영역을 계산하면 되지 않을까 생각하기 쉽지만 많은 영역을

n^2으로 계산하면 연산속도가 매우 느립니다. 따라서 적분 영상을 처음에 하나 만들어 두고 영상의 부분합을

구하면 빠른 속도로 계산할 수 있습니다.

그렇다면 영상의 Integral Image는 어떻게 계산할까요?

아래 그림을 보면 한눈에 이해 할 수 있습니다.

위 그림의 왼쪽 이미지는 기존 이미지를 의미하고, 오른쪽은 적분 이미지를 의미합니다.

적분 이미지는 (0,0)부터 현재 좌표점까지의 밝기값의 누적으로 계산할 수 있습니다.

만약 (1,1)를 구할때는 (0,0) + (0,1) + (1,0) + (1,1)의 총합을 (1,1)에 저장하면 됩니다.

영상의 적분 이미지를 생성해 두고 영상의 부분 합을 계한하려고 하면 

D = D + A - B - C

3번의 더하기 빼기로 영역의 밝기 부분합을 구할 수 있습니다.

빨강 부분에 관한 합을 적분 부분합 식을 이용하면

 D = 21 + 4 - 11 - 11 = 3 

를 빠른 속도로 계산할 수 있습니다.

2. 축소한 detector와 descriptor를 사용하여 빠른 (차원수 축소)

 관심점을 계산하기 위해 SURF는 헤시안(Hessian) 행렬을 사용합니다.

논문에서는 정확성이 좋고 determinant가 최대값인 위치의 blob 구조를 검출하기 위해서라고 나와 있습니다.

[그림출처 : http://www.quora.com/What-are-the-benefits-of-calculating-the-eigenvector-of-a-Hessian-matrix-in-image-processing]

 만약 determinant(행렬식)가 음수이고 eigenvalue가 서로 다른 부호이면 해당 좌표는 관심점이 아니고

determinant가 양수이고, eigenvalue가 둘 다 음수 혹은 양수이면 해당 좌표는 관심점으로 판단합니다.

SURF의 경우 2차 미분을 Gaussian을 사용하는데, Scale-space를 분석하는데 가우시안이 가장 최적이라고

판단하여 사용함을 논문에 명시하였습니다. 따라서 x,y,xy에 대한 헤시안 행렬을 계산하면 관심점(Interest Point)

로 판단합니다.

또한 가우시안 분포 헤시안 행렬을 계산할때 계산을 좀 더 단순화 시키기 위해 근사화한 Dxx와 Dyy 박스필터를 

사용합니다.

 위 사진과 같이 근사화한 박스 필터를 사용하므로써 적분이미지 계산으로 영역의 넓이를 빠르게 구하고 

구한 넓이로 헤시안 행렬을 계산해 관심점을 판단합니다.

논문에서 weight값은 0.9를 사용했습니다. 

 SURF도 스케일에 robust하기 위해 SIFT와 비슷하게 여러 스케일에서 관심점을 추출합니다. 

아래 그림을 보면 SIFT 필터 사이즈를 고정시키고, 이미지 사이즈를 줄여 관심점을 검출하는 반면, 

SURF는 SIFT와는 반대로 이미지 스케일을 고정시키고 필터 사이즈를 키워가며 관심점을 추출합니다.

SIFT와 다른 차이점을 둔 이유는 계산의 효율성 때문일 것 같습니다. 적분 이미지를 사용하기 때문에

위치를 변경하는것 만으로 필터 사이즈를 조절할 수 있기 때문입니다. 또한 down sampling하지 않기 

때문에 aliasing이 없는 장점이 있습니다.(scale invariance 가 제한적일 수 있음 - 단점)

아래 그림을 보면 3계의 옥타브가 있고 점점 스케일이 증가하는것을 확인할 수 있습니다. 

옥타브가 증가하면 필터 사이즈가 2배로 증가하는 것을 볼 수 있습니다.

(논문에서는 하나의 옥타브에 4번 scale up)

 선정한 관심점을 비 최대치 억제(non maximum suppression)을 통해 크기 공간에 대한 극대값(검출된 관심점)

을 선정합니다. 또한 이 극대값에 대해 보간법을 적용하여 보간된 관심점을 특징 벡터로 저장하여 사용합니다.

(Sub-Pixel로 보간)

 최종 보간된 관심점을 중심으로 6s(scale)의 원 안에 있는 이웃들에 관해 x, y 방향의 Haar wavelet response를 

계산합니다. 오른쪽 원 안의 파란 점이 response값의 분포입니다. 그리고 빨간 화살표는 부채꼴 모양 안의 영역에 있는

response의 합을 벡터로 표현한 것입니다. 60도 크기의 window를 슬라이딩 하면서 x,y축의 response의 합을 계산해서

벡터를 생성시키고 벡터 길이가 가장 긴 것이 orientation으로 할당됩니다.

이때 Haar wavelet filter를 이용하기 때문에 적분 이미지의 장점을 적용할 수 있습니다.(빠른 계산)

 위 그림을 보면 descriptor를 생성하기 위해 관심점 주위 20scale 크기의 window를 구성해 이미지를 회전에 

invariant 하기 위해 회전시킨 뒤 계산합니다. 이때 앞에서 구한 orientation를 활용하면 됩니다.

또한 descriptor window를 4×4로 나눈뒤, 나눠진 구역은 5×5 haar wavelet로 구성합니다.

 논문에서는 또한 contrast에 invariant하다는 것을 보여주기 위해 단순히 x, y 축에 대한 response값을 

합한 것이 아니라, 각 값에 대한 절대값을 합하여 contrast에 강하다는것을 증명하고 있습니다.

3. Contrast를 이용한 빠른 매칭

 hessian 행렬을 계산한 라플라시안 부호를 비교해 간단히 매칭을 시도합니다.(부호 비교)

HOG descriptors

이전 포스팅 에서 영상의 기술자에대해서 정리하였습니다.

이번에는 HoG(Histograms of Oriented Gradients)에 정리해봅니다.

HoG는 대표 기술자로 잘 알려져 있는 SIFT[1], SURF[2], GLOH[3]등 다양한 곳에서 사용하고 

있습니다. 그중 가장 친숙한?(혹은 잘 알려진) SIFT에서 사용되는 HoG에 대해 알아보겠습니다.

SIFT는 1999년 캐나다 대학 UBC(University of British Columbia) 교수인 David Lowe가 발표한 논문에서

소개되었습니다. SIFT에서는 두개의 Keypoint(관심점)과 Descriptor(기술자)를 사용하여 두 사진을 매칭 하였습니다.

특징점 추출은 건너 뛰고 기술자 생성에 관한 내용만 정리해 보겠습니다.

첫번째로 SIFT에서는 Scale에 불변한 Keypoint를 찾은후, keypoint위치를 warp 하여 16x16 사이즈의 윈도우를 

만들었습니다.

다음으로 각 픽셀에 대해 기울기를 계산합니다.(Orientation and magnitude) 

각 픽셀에 대하여 아래 사진과 같이 16개의 4x4픽셀 사각형에 포함된 영역에 대한 기울기를 계산합니다.

각각의 사각형에 대해 8방향의 히스토그램을 계산합니다.

위와 같은 방법으로 히스토그램을 구하면 16개의 히스토그램을 8방향으로 표현한 128차원(16*8)의 

벡터를 얻을 수 있습니다.

요약하자면 아래 사진과 같습니다.

위와 같이 히스로그램의 방향을 통해 기술자로 사용하는 방법이 HoG입니다.

SIFT는 illumination(조명)의 변화에 불변(강건) 하며, 물체의 방향에 상관없는 기술자(회전에 불변)를 

생성할 수 있습니다.

References :

[1] Lowe, David G. “Object recognition from local scale-invariant features.”Computer vision, 1999. The proceedings of the seventh IEEE international conference on. Vol. 2. Ieee, 1999.‏

[2] Bay, Herbert, Tinne Tuytelaars, and Luc Van Gool. “Surf: Speeded up robust features.” Computer Vision–ECCV 2006. Springer Berlin Heidelberg, 2006. 404-417.‏

[3] Mikolajczyk, Krystian, and Cordelia Schmid. “A performance evaluation of local descriptors.” Pattern Analysis and Machine Intelligence, IEEE Transactions on27.10 (2005): 1615-1630.‏

사진(영상) 에서의 descriptor(기술자)란?

만약 아래 두 사진을 비교한다고 할때 가장 쉽게 생각할 수 있는 방법이 무엇일까요?

아래 두 사진이 같은 사진인지? 아니면 다른 사진인지를 판단하는 방법은 같은 위치에 있는

두 영역(patch)가 모두 같으면 같은 사진일것이고, 다르면 다른 사진일 것 입니다.

위와 같이 가장 간단하면서 쉬운 방법은 영상에서의 다양한 위치에 존재하는 patch를 비교하면 

비교 문제를 해결 할 수 있습니다.

영상처리 및 컴퓨터비전에서도 마찬가지로 다양한 부분을 비교하여 많은 부분이 일치하면

동일한 사진이라고 판단하는 방법이 물체의 위치를 찾는데 사용되고 있습니다.

과정은 총 4가지로 이루어져 있습니다.

위 사진에서 기술자 함수란 사진에서 특정 영역에 대한 부분을 서로 비교하기 위해

동일한 방법을 통해 사진에서의 특징을 하나의 비교 대상으로 만드는 것을 말합니다.

기술자 함수는 단순하게 영역을 비교하기 위해 설계되어야 하지만 간단한 문제같지만 매우 복잡한

문제일 수도 있습니다. 사진이 회전되었을 경우 혹은 잡음이 섞여 있을 경우, 조명이나 외곡이 있을 경우에도

강건한(robust)한 특징 추출이 가능해야 합니다.

따라서 회전 및 잡음에도 강건한 기술자를 만들기 위해 비교할 좌표(keypoint) 선정에 있어서

코너를 선택하는 경우가 많으며 코너로 부터 기술자를 생성하여 두 이미지를 비교합니다.

칼만 필터는 부정확한 측정값(관찰, 혹은 예측값)으로부터 오차를 최소화 하는 추정치를 반복적으로 

계산하는 방법이다. 가우시안 잡음(Gaussian noise)인 경우에 최적의 추정량을 구할 수 있다.

Wan, Eric A., and Rudolph Van Der Merwe. "The unscented Kalman filter for nonlinear estimation." 

Adaptive Systems for Signal Processing, Communications, and Control Symposium 2000. AS-SPCC. 

The IEEE 2000. IEEE, 2000.

칼만 필터 프로세스 방정식과 측정 방정식은 다음과 같다.

칼만 필터는 초기화 이후 예측(predict) 위 단계를 계속 반복하면서 추정치를 구한다.

측정 잡음의 공분산 R이 아주 크면, 칼만이득 K가 작아져서 다음 단계의 추정치를 계산할 때 현재의 측정값이 무시된다.

움직임 추적에서 보통 많이 사용하는 mean-shift와 cam-shift에 대해 정리해본다.

1. mean-shift(민시프트)

mean-shift 알고리즘은 데이터 집합의 밀도 분포에서 지역 극값(local extrema)을 찾아내는 방법이다.

언덕오르기 알고리즘과 비슷한 방법으로 생각할 수 있다. 

데이터 집합이 있을때 보통 mean-shift는 데이터의 이상치(outlier)를 무시한다. 쉽게 말하면 데이터의

정점(peak)으로부터 너무 멀리 떨어진 데이터는 무시한다는 것을 의미한다. 

따라서 특정 지역내의 윈도우 안에 존재하는 데이터 점들만을 사용하여 윈도우를 움직인다.

mean-shift 알고리즘은 다음과 같이 동작한다.

보통 윈도우 내의 데이터들로 부터 무게중심을 구할때 가우시안 분포(Gaussian distribution)을 사용한다.

보통 중심으로 부터 가까이 있는 데이터에 가중치를 좀더 높여 주는 방식이 좋다.

위 그림은 mean-shift 알고리즘의 이동 분포를 표현한 것이다. 사진을 보면 데이터의 중심(많은 픽셀이 분포한 점)

으로 윈도우가 이동하는것을 확인할 수 있다.

mean-shift알고리즘은 지역적 정점을 찾기 때문에 여러 지점에서 정점이 발견 될 수도 있다.

이런 움직임으로 인하여 윈도우 아래 존재하는 데이터들이 바뀌게 되고, 반복적으로 중심 이동 작업을 수행할 

수행할 수 있다. 중심 이동이 반복되면 mean-shift 벡터가 0이 되는 경우가 생기면 이때 수렴하는 순간이라고

판단하면 된다.

OpenCV는 mean-shift 함수를 제공한다.

probImage는 역투영 히스토그램 이미지를 입력으로 받는다. calcBackProject()함수를 이용하면 된다.

window는 커널 윈도우 초기위치, 크기를 나타낸다. criteria는 반복연산의 종료조건을 입력하면 된다.

2. camshift(캠시프트)

[Bradski98] Bradski, Gary R. "Computer vision face tracking for use in a perceptual user interface." (1998).

예를 들어 얼굴 특징을 이용하여 추적하는 경우, 카메라로부터 사람이 가까워지거나 멀어짐에

따라 얼굴 크기에 맞게 자동으로 윈도우 크기를 변화시킨다. 

mean shift와 cam shift 알고리즘은 색상 특징값을 이용하는 추적 알고리즘이라고 생각하기 쉬운데, 

이 생각은 잘못된 생각일 수 있다. 이 두 알고리즘은 확률적 분포에서 표현되는 모든 종류의 특징 분포를 추적한다.

현재 가장 많이 사용하고 있는 옵티컬 플로우 방법은 Lucas와 Kanade방법이다.

[Lucas81] Lucas, Bruce D., and Takeo Kanade. "An iterative image registration technique with an application 

to stereo vision." IJCAI. Vol. 81. 1981.

위 영상을 보면 추적 영상의 외곡에도 상당히 추적을 잘하는 것을 볼수 있다.

각 화소에 대하여 특정 범위 안 윈도우 크기 내의 이웃 화소 들에 대해서 광류식(Optical Flow Equation)의 에러 제곱을

최소화하는 벡터를 구하기 위해 벡터를 지역 최소자승법(local least squares)로 계산한다.

예를 들면 윈도우 크기 3x3일 떄 9개의 화소에 대하여 에러 제곱을 최소화하는 (u,v)을 의사 역행렬(pseudo inverse matrix)을

최소자승법으로 계산한다.

위와 같이 광류식을 새워놓고 에러 제곱을 최소화 하는 광류 벡터(u,v)를 구하이 위해 u와 v로 각각 미분한다.

(에러 제곱을 최소화 하는 광류 벡터)

각각 미분한 식을 0으로 놓고 계산하면 아래 수식을 얻을 수 있다.

을 아래 수식으로 변형한다.

OpenCV에는 Lucas와 Kanade의 Optical Flow함수를 2가지 제공한다.

첫번째는 위 수식을 그대로 적용한 기본 방법이고,

소스 참조 : http://lueseypid.tistory.com/archive/20130122

지금 소개할 Optical Flow는 Horn이 1981년 

[Horn81] Horn, Berthold K., and Brian G. Schunck. "Determining optical flow." 1981 Technical Symposium East. 

International Society for Optics and Photonics, 1981. 

논문에서 소개한 방법이다.

Horn과 Schunck는 밝기값 패턴에서 임의의 화소에서의 발기값이 시간에 따라 변화하지 않는 상수로 가정하고, 

속도 분포가 영상의 모든 화소에서 부드럽게(smooth) 변화한다라는 제약조건을 추가했다. 쉽게 말하면 프레임 간의

간격은 매우 짧은 시간이므로 픽셀의 움직임이 크지 않다는 것을 가정한 것이다.

따라서 제곱에러 e^2를 최소화하는 속도 벡터 u와 v를 반복적으로 계산한다. (아래 수식)

Ex, Ey, Et를 2x2윈도우를 사용하여 다음과 같이 계산한다.

위 방법은 모든 화소에서 광류 계산을 수행하기 때문에 좀 느린 단점이 있다.

어떤 물체를 추적할때 가장 간단한 방법이 해당 블록(영역)을 다음 프레임에서 어딨을지 찾아가는
방법이 가장 간단한 추적 방법일 것이다.

OpenCV에서는 이 방법을 하나의 메소드 형태로 제공한다.

파라메타로 prev는 이전프레임으로 (8비트, 1채널 영상)을 입력받으며, curr는 현재 프레임으로 

이전 프레임과 동일하게 8비트 1채널 영상을 입력 받는다.

block_size는 두 영상에서 비교할 블록의 크기를 의미하며, shift_size는 탐색할 영역 크기를 나타낸다.

velx와 vely는 속도 벡터를 나타내는 변수로 1채널 32비트 실수 영상이다. 

max_range는 curr에서 최대 탐색 범위를 나타내고 usePreviosu가 1이면 velx와 vely에 있는 이전 결과를 사용한다.

입력 영상 및 결과 영상

 결과 영상      (vely)   (velx)