원 저작자는 소스 코드를 http://www.asl.ethz.ch/people/lestefan/personal/BRISK 게시해 놓고 있는 상태이고, 해당 페이지에서 관련 논문과 데모 비디오를 볼 수 있습니다.
앞으로의 몇 차례의 포스팅에 걸쳐 BRISK 알고리즘에 대한 설명과, 소스코드 레벨에서 제가 주의깊게 살펴본 포인트들을 짚어보도록 하겠습니다. 논문들을 두서없이 읽다보면 무엇을 읽었는지 정리가 안된 경우가 많아 스스로 정리하는 차원에서, 차후에 참고용으로 리마인드를 위해 블로깅해 볼 생각입니다. 그럼, 시작합니다!
- feature를 추출
- description을 생성
하는 과정을 설명하기에 앞서, feature가 무엇인지를 짚고 넘어가야 할 것 같네요. 영상에 있어서의 feature란 예를 들어, edge나 corner와 같이 영상을 특징화할 수 있는 요소를 말하는데요. feature의 종류는 다양할 수 있습니다. 영상을 특징화하여 설명할 수 있는 것이면 다 됩니다.
 |
| http://en.wikipedia.org/wiki/Corner_detection |
point 기반의 feature, 또는 area 기반의 feature로 크게 나눠볼 수 있지 않을까 싶은데요. 일단 여기서는 point 기반의 feature로만 한정지어 생각해보도록 하겠습니다. 앞서 언급했었던 edge나 corner가 바로 그 대표적인 예에 해당합니다.
BRISK 논문에서도 corner detection 과정이 적용되어 있는데요. 사실 corner detection의 종류는 참 많습니다. 고전적인 알고리즘인 Harris corner detector(88)부터, Shi와 Tomasi의 corner detector(94), SUSAN corner detector(97), FAST corner detector(06) 까지 그 외에도 참 많죠. BRISK 논문에서는 기본적으로 FAST corner detector를 사용했습니다.
2006년 ECCV에서 나온 FAST corner detector 논문의 원 제목은 "Machine learning for high-speed corner detection" 입니다. 이 논문의 주요 골자는 기존의 eigen value기반 등의 계산적으로 부담이 되는 방법들 외에 보다 단순하면서도 빠른 알고리즘을 지향하고 있습니다.
방법은 단순합니다. 아래의 그림을 확인해보시죠.
 |
| FAST corner detector 알고리즘의 도식적 설명 (논문에서 발췌) |
그림을 보시면 중앙에 p라고 적혀있는 픽셀이 있습니다. 중앙 픽셀 p가 가지는 밝기값 Ip과 주변 16개의 이웃 픽셀들의 밝기값을 비교합니다. 예를 들어, 중앙 픽셀의 밝기값 Ip가 50이라고 합시다. 그리고 threshold t를 20이라고 합시다. 그럼, 16개의 이웃 픽셀들의 밝기값이 중앙 픽셀의 밝기값 Ip과 threshold t를 더한 값(=Ip+t=50+20) 보다 커서 더 밝거나, 중앙 픽셀의 밝기값에서 threshold를 뺀 값(=Ip-t==50-20) 보다 작아서 더 어두운 경우를 셉니다. 이러한 조건을 만족시키는 이웃 픽셀들이 정해진 숫자보다 크면 (단, 이웃 픽셀들끼리는 연속적/즉, 연결된 픽셀들이어야 합니다) 그건 corner 후보가 되는 셈입니다. 그리고 한 가지 더 보태서 얘기하자면 16개의 이웃픽셀들 가운데 중앙 픽셀보다 더 밝거나/어두운 연속적인 픽셀들을 체크하는 데에도 무작정 16개의 픽셀을 다 순회해가며 뒤지는 것이 아닙니다. 이 부분을 어떻게 효율적으로 신속하게 뒤지느냐의 문제도 더 연구해볼 주제일 수 있는데요. 기본적으로 FAST 논문에서는 ID3 알고리즘(86)을 사용하고 있습니다. 본 포스팅에서는 이 부분은 생략하려고 합니다.
FAST 알고리즘으로 corner들을 검출해보면, corner라고 생각했던 위치 주변의 점들의 무리가 대거 corner 후보로 추출되는 걸 살펴볼 수 있는데요. 그래서 corner response가 주변 이웃들 보다 큰 점만 골라내는 non-maximal suppression 과정이 이어질 수 있습니다. 물론 non-maximal suppression 과정이 이어지기에 앞서, corner response가 먼저 구해져야 하겠습니다.
여기서, corner response가 무엇이냐는 질문을 하실 수 있을 것 같은데요. 단어가 의미하는 그대로, corner의 정도가 강하냐/ 약하냐의 정도를 corner response라고 할 수 있습니다. 또다른 말로는 corner score라고 할 수도 있습니다. 그럼 corner response를 무엇으로 재느냐가 그 다음 질문일 수 있겠죠. 이것 또한 단순합니다. 중앙 픽셀에 비해 threshold 보다 더 밝은 픽셀들의 집합을 S_bright이라 하고, 중앙 픽셀에 비해 threshold 보다 더 어두운 픽셀들의 집합을 S_dark라고 합시다.
S_bright에 속한 픽셀들의 밝기값들 (예를 들어, 100, 75, 80) 에서 중앙 픽셀의 밝기값 (예를 들어, 50)을 뺀 값들에서 threshold 를 뺍니다. (예를 이어가자면, 100-50-20, 75-50-20, 80-50-20이 되겠네요). 마찬가지로, 중앙 픽셀의 밝기값 (예를 들어, 50)에서 중앙 픽셀의 밝기값 (예를 들어, 50) S_dark에 속한 픽셀들의 밝기값들 (예를 들어, 20, 10, 10) 을 뺀 값들에서 threshold 를 뺍니다. (예를 이어가자면, 50-20-20, 50-10-20, 50-10-20이 되겠네요). 이렇게 뺀 값들 가운데 maximum값이 중앙 픽셀 p에 대한 corner score (예에서는 30)가 됩니다.
이번 포스팅에서는 BRISK 논문의 feature 추출 부분에서 쓰인 FAST 알고리즘을 살펴봤습니다. 다음 포스팅에서 BRISK의 scale space별 feature 추출과 description code 생성 부분을 이어가도록 하겠습니다.
