Tracking algorithm(쓰는 중.)

Consensus-based Matching and Tracking of Keypoints for Object Tracking - 2014  VOT(visual object tracking) award winning algorithm

CMT알고리즘은 기본적으로 Detector(영상 특징점) 로는 FAST algorithm Descriptor(영상 기술자) 로는 BRISK 를 사용하고 있다.

그 전에 기본적으로 영상 특징점과 영상 기술자에 대해서 간단하게 알아야 한다.

영상 특징점(Key point)이란?

(FAST 알고리즘 사용한 KeyPoints)

- 보통 물체의 Scale, size, orientation이 변해도 식별 가능한 점.

- 물체를 바라보는 시점이나 조명이 변해도 변하지 않는 물체의 고유한 특징 점.

- 다각형의 꼭지점, 선분의 끝 점.

보통 위의 특징에 해당하는 점은 코너에 해당하고, 대부분 KeyPoint를 뽑아 내는 알고리즘은 이미지 내의 코너들을 검출한다. (코너나 끝 점을 검출하는 것만 해도, 많은 알고리즘들이 들어있고 여기서는 과감히 패스합니다.)

영상 기술자(Descriptor)란?

찾고자 하는 영역 혹은 점등 특정 이미지 영역에 대한 부분을 서로 비교하기 위해, 동일한 방법을 통해 이미지에서의 특징을 하나의 비교대상으로 만들어 줍니다.

가령 추출된 KeyPoint를 중심으로 Patch 사이즈를  해석하여, 특징점의 지역적 특징을 설명해주며, 특징점 간의 비교를 가능하게 해준다. 

영상 기술자는 몇가지 조건을 가지게 되는데 보통 3가지를  필수조건으로 가져야 한다.

- 분별력 : 서로 다른 점의 기술자는 분별 가능해야 함 (a점에 대해선 a기술자가 b점에 대해서는 b기술자라 분별한다)

- 불변 : 회전, 축소, 변형 등이 발생해도 변하지 않는 성질

    

            [왼쪽 그림과 같이 Rotation된 상,하 이미지가 같다는 것을 알려 주는 것이 기술자가 하는 역할이다.]

- 크기 : 데이터의 크기가 작을수록 좋음

영상 기술자가 동일한 이미지라고 판단 하기까지 크게 4가지 과정이 있습니다.

1. 이미지 두 장에서 특징점을 찾습니다 (이부분을 Detector가 해줍니다.)

2. 특징점의 Patch를 비교하여 일치 여부를 판단합니다.

3. 일치 한다면, 유사성을 계산합니다.

4. 유사성이 일정 Threshold를 넘게 된다면, 첫번째의 이미지 위치를 두번째로 이동합니다.

FAST(Feature from Accelerated Segment Test)는 영상에서 KeyPoint를 뽑아 내는 알고리즘이다.

[FAST라는 이름에서 알 수 있듯이 극도의 빠름을 추구한 특징점 추출 방법입니다. 하지만 FAST가 정말 뛰어난 점은 FAST가 속도에 최적화되어 설계된 기술임에도 불구하고 그 특징점의 품질(repeatability: 다양한 영상 변화에서도 동일한 특징점이 반복되어 검출되는 정도) 또한 기존의 방법들(Harris, DoG, ...)을 상회한다는 점에 있습니다.]            출처: http://darkpgmr.tistory.com/131 [다크 프로그래머]

그림에서는 픽셀 P에서 원의 둘레가 16이 되는 원이 있다고 하나 가정한다. 픽셀 P의 Intensity를 Ip라고 결정하고, 적절한 Threashold 값을 t라고 지정한다. 

lp + t = 더 밝은 경우, lp - t = 더 어두운 경우가 되게 된다. 16개로 이뤄져 있는 원안의 픽셀들 중에 lp + t가 연속으로 n개가 나오거나, 혹은 lp -t 가 연속으로 n개가 나온다면 p를 코너로 판단한다. n은 9,10,11 ... , 16이 될 수 있고, 논문에서는 12로 지정했음으로 FAST-12로 부른다.

여기서 속도를 높이기 위해 픽셀 P가 코너인지 간단히 검사를 진행하는데, 첫째로 1, 9번의 픽셀을 보고 5, 13번의 픽셀을 보게 되는데 이 이유는 코너인 부분은 결과적으로 1,5,9,13 픽셀 중 3개의 값은 p의 Intensity보다 작거나 클 수 밖에 없다. 따라서 앞에 조건으로 수 많은 후보군들을 제외 시키고, 계산을 한다. 이것을 고속 테스트라고 부른다.

여기까지만 해도 잘 작동하지만, 몇 가지 한계 점이 존재한다.

• 1. It does not reject as many candidates for n < 12. (n이 12개 아래면 많은 후보들이 제외시키지 않아, 결과적으로는 계산량이 늘게 되는 것.)
• 2. The choice of pixels is not optimal because its efficiency depends on ordering of the questions and distribution of corner appearances. (코너의 외형이나 분포에 의지하기 때문에, 최적의 선택은 아니게 되는 것)
• 3. Results of high-speed tests are thrown away. (고속 테스트의 결과를 버리는 것)
• 4. Multiple features are detected adjacent to one another. (코너에서 인접한 특징점이 많이 발견 되는 것)

1~3 번은 머신러닝을 통해 해결하고 4번은 비 최대 억류 (Non-Maximal-Suppression)를 사용하여 해결한다.

앞에 내용은 깊게 보지 않아서 논문을 참고하는 것을 추천합니다.

4번의 비 최대 억류를 사용 하는 이유는 여러 점들이 코너 점으로 검출 된 경우에는 코너의 특징이 가장 큰 확실한 점만 남기고 나머지를 제거하기 위함입니다.(ex : object detection, edge detection etc.)

검출된 점의 코너성을 수치화하여 스코어 함수 V를 계산합니다.

코너같다고 생각되는 점 P를 둘러 쌓고 있는 픽셀 값을 전부 더한 뒤, P의 값을 뺀 절대 값을 스코어로 이용하여 인접한 2개의 코너 같다고 생각되는 후보군에 대해 V를 계산하고 값이 작은 쪽을 버려 가장 값이 가장 크게 되는 한 점만을 남깁니다.

FAST는 But it is not robust to high levels of noise. It is dependant on a threshold.

Threshold에 의존하기 때문에 노이즈가 많은 곳에서는 강인하지 못합니다.