Research Trends and Case Study on Keypoint Recognition and Tracking for Augmented Reality in Mobile Devices

본 논문은 한국과학기술연구원 기관고유과제 (Project No. 2E25660)의 지원에 의해 연구되었음.

*주저자：한국과학기술연구원 영상미디어연구단 위촉연구원; e-mail: [email protected]

**공동저자：한국과학기술연구원 영상미디어연구단 책임연구원; e-mail: [email protected]

***교신저자：한국과학기술연구원 영상미디어연구단 책임연구원; e-mail: [email protected]

￭접수일：2015년 7월 13일 / 심사일：2015년 7월 27일 / 게재확정일：2015년 8월 27일

모바일 증강현실을 위한 특징점 인식, 추적 기술 및 사례 연구

Research Trends and Case Study on Keypoint Recognition and Tracking for Augmented Reality in Mobile Devices

최희승, Heeseung Choi*, 안상철, Sang Chul Ahn**, 김익재, Ig-Jae Kim***

요약 최근 증강현실 분야에서 특징점 인식 및 추적 기술은 비마커 기반의 증강 현실 서비스 구현에 중요한 역할을 담당하고 있다. 특징점 인식 및 추적 기술은 오래 전부터 컴퓨터 비전 등 여러 분야의 많은 연구자들에 의해 심도 있게 연구되어 왔으며, 특히 최근 급성장하고 있는 모바일 관련 시스템에 적용하기 위해 모바일 임베디드 환경에 접 목 가능한 특징점 기반의 다양한 인식 및 추적 기술들이 소개되고 있다. 따라서 본 논문에서는 널리 활용되고 있는 특징점 기반의 매칭 및 추적의 다양한 핵심 요소 기술 (특징점 추출, 특징점 기술, 특징점 매칭 및 추적)에 대한 최 신 동향을 분석하고, 본 한국과학기술연구원 연구팀이 수행한 모바일 증강현실 서비스 관련 사례 연구인 관광 지도 인식 및 추적 연구를 소개하고자 한다.

Abstract In recent years, keypoint recognition and tracking technologies are considered as crucial task in many practical systems for markerless augmented reality. The keypoint recognition and technologies are widely studied in many research areas, including computer vision, robot navigation, human computer interaction, and etc. Moreover, due to the rapid growth of mobile market related to augmented reality applications, several effective keypoint-based matching and tracking methods have been introduced by considering mobile embedded systems. Therefore, in this paper, we extensively analyze the recent research trends on keypoint-based recognition and tracking with several core components: keypoint detection, description, matching, and tracking. Then, we also present one of our research related to mobile augmented reality, named mobile tour guide system, by real-time recognition and tracking of tour maps on mobile devices.

핵심어：Augmented reality, keypoint recognition and tracking, keypoint extraction, local descriptor matching, mobile tour guide system.

1. 서론

최근 증강현실 분야에서 객체 인식 및 추적 기술은 비마커 (Markerless) 기반의 증강 현실 서비스 구현에 매우 중요한 역 할을 담당하고 있다. 비마커 기반의 증강 현실 기술은 기존의 사전에 정의된 형태의 마커를 사용하는 방식이 아니라, 영상 및 비디오 상의 다양한 객체 요소 그 자체를 기존의 마커와 같은 형태로 활용하여, 객체와 관련된 디지털 정보를 렌더링하여 디 스플레이에 표현하는 기술이다. 정보 증강을 위해 관심 객체를 인식하고 추적하는 다양한 기술 중 현재 가장 주목받고 있는 특징점 (keypoint 혹은 interest point) 기반의 인식 및 추적 기 술은 이미 오래 전부터 컴퓨터 비전의 다양한 분야 (객체 인식, 파노라마 합성, 3차원 복원, 영상 검색 및 분류, 로봇 네비게이 션 등)에 널리 활용되어 왔다. 특히 최근에는 급속도로 발전한 모바일 컴퓨팅 기술에 의해, 모바일 임베디드 환경에서도 영상 내의 관심 정보를 특징점 기반의 인식 및 추적 알고리즘을 활 용하여 실시간으로 인식하고 관련 콘텐츠를 자동으로 제공 혹 은 증강하여 주는 기술 실현이 가능하게 되어 그 파급효과는 더욱 커질 것이라 전망된다. 그림 1은 증강현실 서비스를 위한 특징점 기반의 영상 인식 및 추적 기술의 흐름도이다.

그림 1. 특징점 기반 인식 및 추적 기술의 흐름도

특징점 기반 인식 및 추적 기술은 크게 오프라인 (학습) 과 정과 온라인 (인식 및 추적) 과정으로 나눌 수 있다. 오프라인 과정에서는 사전에 학습할 대상 영상 (모델)을 분석하여 데이 터베이스를 구성하며, 온라인 과정에서는 입력된 영상을 데이 터베이스에 미리 저장된 영상들과 비교 후 가장 근접한 결과를 검색하여 인식 및 추적을 수행한다. 인식을 위한 주요 단계는 크게 특징점 검출 (detection), 특징점 기술 (description) 및 매 칭 (matching) 단계로 나눌 수 있다. 특징점 검출은, 영상 내의 지역적 특징들 (corner point, blob, salient region 등)을 필터링 등 의 다양한 영상 처리 알고리즘을 통하여 추출하는 과정이며, 특징 점 기술은 검출된 특징점들 주변의 지역 텍스쳐 특징을 고려하고, 영상의 변환 (회전, 위치, 투영 변환 (perspective transform) 등)

에 강인한 특징점 기술자 (descriptor)를 생성하는 과정을 의미 한다. 특징점 매칭은 계산된 기술자 집합 간의 효율적인 매칭을 수행하기 위한 과정으로, NN (Nearest Neighbor) 매칭을 위한 기본적인 Brute force 매칭뿐만 아니라 효율적인 매칭 구조 (트 리, 해시 구조 등) 생성을 통해 수행이 가능하다. 특징점 매칭을 통하여, 입력 영상과 관련된 대상 혹은 속성이 인식되면, 다양 한 환경의 비디오 상에서 해당 객체를 추적하고 객체의 위치 및 방향을 추정하여 추적 객체의 방향에 따라 가상 객체를 렌 더링하여 증강현실 서비스를 구현할 수 있게 된다. 따라서 본 논문에서는 널리 활용되고 있는 특징점 기반의 매칭 및 추적의 다양한 핵심 요소 기술들에 대한 최신 동향을 분석하고, 모바일 증강현실 서비스를 위한 본 연구팀의 사례 연구인 실시간 모바 일 관광 지도 인식 시스템을 소개한다.

본 논문의 구성은 다음과 같다. 2절에서는 특징점 기반 매칭 및 추적을 위한 다양한 요소 기술들에 대해 기술 분야별로 중 요 연구를 살펴볼 것이며, 3절에서는 본 연구팀의 사례 연구에 대해 설명하고, 마지막으로 4절에서는 결론 및 향후 연구 방향 에 대해서 말하고자 한다.

2. 관련 연구 동향

본 절에서는 특징점 기반 관심 객체 인식 및 추적을 위한 연 구 흐름 및 최신 동향을 특징점 검출, 특징점 기술, 특징점 매칭, 추적 분야로 나누어 기술하며 모바일 시스템 구현을 위해 고려 할 사항에 대해 언급한다.

2.1 특징점 검출 (Keypoint Detection)

객체 인식 및 추적을 위한 이상적인 특징점의 조건에는 적용 분야에 따라 수 가지가 존재하지만, 기본적으로 아래의 두 조건 을 만족하여야한다[1].

•재현성 (Repeatability): 동일 관심 객체의 영상을 각기 다른 환경에서 획득하여 물체의 형태, 크기, 위치 등이 변 하는 경우라도 관심 객체의 동일 영역에서 특징점이 반복 적으로 강건하게 추출되어야 한다.

•구분성 (Distinctiveness): 추출된 특징점 주변의 패턴은 다른 특징점 주변의 패턴과 명백히 구분되어, 카메라의 시 점, 조명 등이 변하는 경우에도 해당 특징점을 쉽고 강건 하게 찾을 수 있어야 한다.

위의 조건을 만족하는 특징점을 검출하기 위해, 다양한 방식 의 특징점 검출기가 제안되었다. 특징점 검출기는 대략적으로 기하학 구조 및 템플릿 기반의 코너 검출기 (corner detector) 와 스케일, 어파인 변화에 강인한 지역 검출기로 나눌 수 있다.

코너 검출기 중 가장 널리 알려진 Harris 코너 검출기는 영상의 그레디언트 및 SSD (sum of squared distance) 값에 기반을 둔

행렬을 eigen decomposition하여 코너 응답 (corner response) 값을 계산한 후, 해당 영역을 코너점, 에지, 플랫 영역으로 판단 하였다[그림 2].

그림 2. Harris 코너 검출기의 개념 [2]

Harris 코너 검출기는 알고리즘의 특성상 영상의 회전, 조명 변화에 강인함을 보여 오랜 기간 널리 활용되었고, 이후 변형된 형태의 다양한 코너 검출기가 제안되었다(예, Shi와 Tomasi의 코너 검출기[3]). 하지만 상기 방식들은 코너 값 계산 시, 고정 스케일 상에서 Gaussian derivative를 계산하였기 때문에 영상 의 크기 변화에 민감한 문제가 발생하여 이를 해결하기 위해 Lindeberg에 의해 제안된 스케일 스페이스 이론[4]을 접목한, Harris-Laplacian, Hessian-Laplacian 검출기[5] 등이 제안되었 다. 이는 여러 영상 스케일에서 Harris 코너 검출기를 통해 코너 후보 점을 검출한 후, 이들 중 스케일 변화에 대해 Laplacian 값 이 극대인 점을 선택하는 방식으로 구성되어 있다[그림 3].

그림 3. LoG 함수 기반 검출기 개념도 [1]

또한 LoG (Laplacian-of-Gaussian) 계산의 속도 향상을 위 해 SIFT (Scale Invariant Feature Transform) 등 여러 연구에 서는 각 스케일 별 Laplacian을 DoG (Difference of Gaussian) 를 통하여 근사적으로 계산하였다[6]. 이밖에도 스케일 변화뿐 만 아니라 극심한 Affine 포즈 변화에 강인한 특징점을 추출하 기 위한 Harris-Affine, Hessian-Affine 검출기 등이 제안되었 다[7]. 한편 Smith와 Brady는 노이즈에 강건하게 동작하고 계

산 속도를 향상시키기 위해 그레디언트를 계산하여 코너점을 찾 는 방식이 아닌, 영상의 morphological 특성을 활용한 SUSAN (Smallest Univalue Segment Assimilating Nucleus) 코너 검출 기를 제안하였다[8]. 이는 영상의 각 픽셀을 중심으로 고정된 크기의 주변 영역을 설정한 후, 주변 픽셀의 밝기 값에 따라 해 당 픽셀의 코너점 여부를 판단하는 템플릿 기반의 방식이다.

최근에는 모바일 환경에 적용하기 위한 효율적인 특징점 검출 방식들이 제안되고 있다. 2005년 Rosten과 Drummond가 제안한 FAST (Features from Accelerated Segment Test)[9] 알고리 즘은 SUSAN 검출 방식에 기반을 두어 코너 여부를 판단하기 위 해, 중심점을 기반으로 임계치 (threshold) 이상 밝은 픽셀들이 n개 이상 연속되어 있거나, 임계치 이하 어두운 픽셀들이 n개 이 상 연속되어 있으면 중심점을 코너점으로 판단하는 알고리즘이 다[그림 4]. 빠른 처리를 위해 주변 값과의 비교를 decision tree 구조를 통하여 계산하고, non-maximal suppression 후처리를 통 해 특징점 정제를 수행하였다. FAST는 타 방식 대비 뛰어난 속 도 및 재현성으로 현재 PTAM (Parallel Tracking And Mapping)[10]

등의 소프트웨어에 적용 중이다.

그림 4. FAST 코너 검출기의 예 [9]

이 밖에도 FAST의 검출 속도를 개선하기 위해 AGAST (Adaptive and Generic Accelerated Segment Test) 방식이 2010년에 제안되었으며, 이는 adaptive tree switching 방식을 사용하여 FAST의 효율을 향상시켜 최근의 모바일 기반 연구 에서 널리 사용 중에 있다[11].

그림 5. AGAST의 tree switching 구조

이후 연구에서는 스케일 변화에 강건한 정확한 위치의 특징 점을 검출하기 위해, FAST 알고리즘과 스케일 스페이스 이론

을 접목한 multi-scale FAST 방식이 제안되어, 특징점 추출의 정확도를 향상시켰다[그림 6].

그림 6. Multi-scale FAST score를 활용한 특징점 localization [12]

이밖에도 영상의 코너점이나 blob을 검출하는 것이 아닌, 영 상의 구조적 유사도를 판단하여 로컬 영역을 검출하는 MSER (Maximally Stable Extremal Regions) 방식[13], Superpixels 방식[14]들이 제안되었으며, 상기 방식들과 유기적으로 조합되 어 특징점 추출의 신뢰도를 향상시키는데 활용중이다.

2.2 특징점 기술 (Keypoint description)

특징점 검출이 이루어지면, 구분력 (discriminative) 있는 매 칭을 위해 검출된 특징점 주변의 정보는 다양한 영상 변환 (회 전, 위치 이동, 투영 변환 등)에 강인하게 인코딩되어야 한다.

이를 위해 다양한 특징점 기술자(descriptor)들이 제안되었으 며, Lowe에 의해 제안된 SIFT 알고리즘 이후로 특징 기술자에 대한 연구는 급속도로 이루어졌다. SIFT 알고리즘은 특징점 주변의 영역 패치에 대해 그레디언트 히스토그램을 구해, 전체 적으로 픽셀들이 갖는 방향 (orientation) 성분을 예측한 후 방 향 성분을 정규화 하여 영상 회전에 대한 강인함을 보장하였다.

특징점 기술을 위해 회전 정규화 된 패치에서 특징점을 중심으 로 128차원의 방향성 히스토그램을 벡터로 구성하여 SIFT 기 술자를 생성한다.

그림 7. SIFT 서술자 [6]

이후 SIFT 기술자와 유사한 여러 형태의 실수 기반 기술자

들이 제안되었으며, 히스토그램 구성 방식을 SIFT의 사각형 (rectangular) 방식이 아닌 log-polar 방식으로 구현한 Gradient location-orientation histogram (GLOH) 기술자[18], 주성분분 석 (Principal component analysis)을 활용하여 매칭 성능 및 매 칭 속도를 향상시킨 PCA-SIFT 기술자[17], 특징점 기술 시 Gaussian weighting 과 circular symmetrical kernel 방식을 사 용하여 wide baseline stereo 매칭에 사용한 DAISY 서술자[19]

등이 SIFT와 유사한 대표적인 실수 기반 특징점 기술자의 예 이다.

다른 대표적인 특징점 기술자로는 2006년 제안된 SURF (Speeded Up Robust Features) 기술자가 있다[15]. SIFT 알 고리즘의 속도를 개선하기 위하여 적분 영상(integral image) 과 2차원 박스 필터를 사용하여 특징점 검출의 속도를 향상시 켰으며, 스케일 스페이스 구성 시 영상의 사이즈를 조절하는 것 이 아닌 필터의 사이즈를 조절하여 계산 시간을 단축시켰다. 하 르 웨이블릿 (Haar wavelet) 필터를 사용하여 특징점 주변의 그레디언트 값을 예측한 후, 특징점 위치를 중심으로 하는 부채 꼴 모양의 슬라이딩 윈도우가 360도 회전하면서 계산된 방향 값 중 가장 큰 값을 특징점의 대표 방향으로 설정하여 특징점 을 기술하였다[그림 8]. SURF 알고리즘은 SIFT 알고리즘과 유사한 성능을 보이지만, 상대적으로 빠른 계산 속도에 의해 현 재 여러 시스템에서 널리 사용되고 있으며, GPU를 활용하여 SURF 알고리즘 속도를 최적화시키는 연구도 발표되었다[16].

그림 8. SURF 서술자 [15]

한편 최근 모바일 환경 적용을 위해 인식 성능을 보장하면서 고속으로 매칭 가능한 이진 기술자 (binary descriptor)들이 제 안되었다. 이진 기술자는 특징점 위치를 중심으로 주변 픽셀간 의 명암 차이를 0과 1로 표현하여 기술자를 생성하므로, SIFT 등의 실수 기반 서술자에 비해 적은 양의 메모리로 기술자 생성 이 가능하고, XOR 비트 연산과 해밍 (Hamming) 거리 계산을 통해 매칭을 수행하므로 고속 처리가 가능하다는 장점이 있다.

2010년 Calonder가 제안한 BRIEF (Binary Robust Independent Elementary Features)는 특징점 주변의 임의 샘플링 (random sampling) 패턴을 기반으로 주변 pair 간의 명암 비교를 통해 SIFT 등의 실수 기반 서술자들에 비해 매우 빠른 속도로 인식 을 수행할 수 있음을 보였다[20].

그림 9. BRIEF의 random sampling의 예 [20]

2011년 Rublee는 BRIEF 기술자를 기반으로 회전과 노이즈 에 강인한 ORB (Oriented FAST and Rotated BRIEF) 기술자 를 제안하였다[21]. 관련 논문에서는 ORB 기술자가 데스크톱 환경뿐만 아니라 모바일 임베디드 환경에서 실시간 처리가 가 능하며, 기술자 생성 시 학습을 통해 구분력 있는 pair를 선택하 여 매칭 성능을 향상시켰음을 증명하였다.

그림 10. ORB 서술자 및 영상 매칭의 예 [21]

2011년 제안된 BRISK (Binary Robust Invariant Scalable Keypoints) 서술자는 BRIEF, ORB에서 사용된 무작위 pair 선 택이 아닌, DAISY 기술자와 유사한 구조적 샘플링 패턴을 사 용하여 특징점을 기술하였다[12]. 특징점을 중심으로 pair의 집 합을 long pair와 short pair의 두 그룹으로 구성하여 long pair 는 주방향 예측, short pair는 기술자 생성에 사용하는 방식을 채택하여 매칭 성능을 향상시켰다.

2012년 발표된 FREAK (Fast Retina Keypoint)는 인간의 시각 구조를 모방한 망막 샘플링 패턴을 적용하여 기술자를 생 성하였으며, 매칭 단계별 pair 구성을 통하여 매칭 단계에서의 속도를 타 이진 기술자에 비해 향상시켰다[22].

그림 11. BRISK (좌) 및 FREAK (우) 샘플링 패턴

특징점 기술자는 실수 기반의 특징 기술자, 속도를 개선한 이진 기술자 등과 관련한 다양한 연구가 수행되었으며, 인식 시 스템 구현 시에는 적용 환경 및 상황에 따라 알맞은 형태의 기

술자를 선택하여 사용하는 것이 중요하다. 계산 복잡도와 메모 리 공간을 고려한 특징 기술자의 분류는 아래 그림과 같다.

그림 12. 특징 기술자 특성 분류 (참고문헌 [51] 재구성)

2.3 특징점 매칭 (Keypoint matching)

학습 (모델) 영상의 로컬 특징들이 기술자 집합의 형태로 데 이터베이스에 저장된 후, 새로이 입력된 영상의 인식을 위해서 는 입력 영상에서 추출한 기술자 집합과 데이터베이스 내의 기 술자 집합 간의 유사도 비교를 수행하여 매칭 후보군을 선정하 고 스코어를 계산하는 과정이 필요하다[그림 13]. 가장 직관적 인 매칭 방식은 학습 영상의 모든 서술자 집합과 입력 영상의 서술자 집합을 모두 비교하는 것이다(Brute Force 매칭 방식).

유사도 비교 시에는, 실수 기반 서술자의 경우 특징벡터 간의 유클리디언 (Euclidean) 거리, 마할라노비스 (Mahalanobis) 거 리 등을 사용할 수 있고, 이진 서술자의 경우 해밍 거리를 사용 하여 계산 속도를 단축시킬 수 있지만, 학습 대상 영상의 수가 늘어나고 영상에서 추출되는 특징점의 개수가 많은 경우 비교 대상이 기하급수적으로 증가하여 매칭 효율이 떨어지는 문제 가 발생하여 매칭의 신뢰도를 유지하면서 효율을 향상시킬 수 있는 다양한 방식들이 제안되었다.

그림 13. 기술자 매칭의 개념도 [23]

대표적인 매칭 방식으로는 KD-tree 구조 기반 매칭이 있다.

KD-tree는 실수 기반 특징 벡터의 매칭에서 널리 사용되는 기 법으로 최근까지 연구가 활발히 지속되고 있다[24-26]. 기본적 인 개념은 오프라인 학습 단계의 특징 벡터를 활용하여 트리 형태의 매칭 구조를 형성한 후 입력 영상의 특징 벡터 집합이 주어졌을 때, 전체 특징 벡터 데이터베이스를 검색하는 것이 아 니라, 트리를 순회하여 가장 가까운 특징 벡터를 검색하여 매칭 을 수행하는 것이다.

그림 14. KD-tree 데이터 구조의 예 [27]

다른 예로는 특징점 매칭을 특징점 분류(classification) 문제 로 해석한 Randomized tree와 Random fern 매칭 방식이 있다.

Randomized tree 방식은 트리 구조의 각 스플릿 노드를 특징점 을 중심으로 구성된 패치 내 두 점 사이의 간단한 밝기 값의 비 교를 통해 구성한다. 각 스플릿 노드는 밝기 특징 값의 양과 음 의 값에 따라 분기를 수행하여, 특징점 분류 시 트리의 순회가 패치 내의 여러 두 점 사이의 밝기 비교를 통해 이루어지게 된 다. 인식 대상의 다양한 어파인 변환을 고려한 학습을 통해, 특 징점 인식의 신뢰도를 향상시켰으며 이 때 입력되는 특징점의 분류는 리프 노드의 클래스 확률의 평균값을 계산하여 어떤 클 래스에 특징점이 속해있는지를 판단하게 된다. 단일 트리 구조 기반의 인식의 신뢰도를 향상시키기 위해 다수의 트리 구조를 사용한 Random forest 기법이 추가적으로 연구되었다.

그림 15. 패치 내 밝기 값 비교를 통한 Randomized tree 기반 특징점 인식 [28]

Random fern 방식은 트리 구조를 Semi-Naive 베이지안 방 식으로 설계하여, 같은 깊이의 노드들에는 같은 구분자를 적용 함으로써 특징간의 독립성을 유지한 방식이다[29]. 트리보다는

리스트의 형태로 구현이 가능하므로 속도가 향상됨을 증명하 였으며, 클래스 식별 시 각 클래스 별 확률 값의 곱을 통하여 randomized tree 방식에 비해 특징점 인식 성능을 향상시켰다.

그림 16. tree와 fern 구조의 비교 [29]

또 다른 대표적인 매칭 방법으로는 LSH (Locality sensitive hashing) 방법이 있다. 이는 임의의 해시 함수를 사용하여 해시 테이블을 생성하고, 주어진 특징점을 각 해시 함수의 결과에 따 라 버킷에 저장한다. 실시간 매칭 과정에서 인식하고자 하는 특 징점이 주어지면, 이를 동일한 해시 함수를 이용하여 저장될 버 킷을 찾고, 해당 버킷에 저장된 특징점들의 집합과 선형 검색을 수행한다. Brute force 검색 방식에 비해, 버킷에 저장된 특징점 들과의 비교만을 수행함으로 검색 속도의 향상이 가능하지만, 동일한 버킷에 많은 수의 특징점이 저장된다면 검색에 소요되 는 시간이 오래 걸린다는 단점이 있어, 해시 함수를 설계하는 기술이 무엇보다 중요하다[30].

그림 17. Locality sensitive hashing의 개념 [31]

특징점 매칭이 수행된 후, 객체 인식 및 추적을 위한 전단계 로 물체의 기하학 구조 (geometric configuration)를 고려한 이 상점 (outlier) 제거와 관심 객체가 강체 대상(rigid object)인 경우에는 호모그래피 (homography) 계산을 통한 포즈 예측을 수행할 수 있다. 이상점 제거의 대표 방법으로는 통계적 파라미 터 추정 방법인 RANSAC (RANdom SAmple Consensus)이 있으며 GHT (Generalized Hough Transform)를 이용한 객체 인식 및 이상점 제거를 수행한 연구도 제안되었다[32-33].

2.4 추적 (Tracking)

추적은 연속된 프레임에서 관심 대상의 위치 변화를 계속적으

로 추정하는 것이라 할 수 있다. 인접한 프레임 사이의 시간적, 공간적, 형태적 유사성을 이용하여 관심 대상을 추적하며, 다양 한 영상 변화 (가림(Occlusion), 모션 블러(Motion blur), 조명 변화(Illumination changes), 형태 변화(shape deformation) 등) 에 강인한 추적 알고리즘 개발을 위해 현재에도 계속적인 연구가 진행되고 있다[34-37]. 또한 추적 방식은 객체의 표현 (visual representation)을 위해 사용되는 특징의 형태에 따라 크게 점 기반 추적[38-41], 커널 (kernel) 기반 추적[42-43], 외곽형태 (silhouette) 기반 추적[44] 방식으로 구분할 수 있으며 아래에 서는 점 기반 추적의 대표적인 방식들에 대해 설명한다.

점 기반 추적의 경우, 가장 널리 사용되는 방법으로는 칼만 (Kalman) 필터[45]와 파티클 (particle) 필터[47]가 있다. 칼만 필터는 측정 가능 변수와 예측 변수를 추정하여 최적의 예측 값을 계산하는 방법으로 표준편차에 따라 가중치를 계산하여 위치 및 데이터를 추적하는 방법이다. 칼만 필터의 장점은 연속 적인 선형 데이터에 대해 Gaussian 밀도를 통하여 예측하기가 쉽고, 업데이트가 간단한 방식으로 이루어져 있다. 예측 값과 측정 값 모두가 추적에 사용되기 때문에 현재 상태를 보완하여 추적하는데 용이하지만 밀도를 추정하여 추정하는 방식이므로 입력 영상의 조명의 변화와 노이즈에 민감하다는 문제가 존재 한다.

그림 18. 칼만 필터의 처리 과정 [46]

칼만 필터의 단점을 보완하기 위해 이를 발전시킨 형태인 EKF (Extended Kalman Filter)[48], UKF (Unscented Kalman Filter)[49] 등이 소개되었고, 다양한 움직임을 추정하기 위해 또 다른 알고리즘인 파티클 필터가 제안되었다. 파티클 필터는 연속적인 Markov Chain에 연결되는 Bayesian Model을 추정하 는 방식으로 추적하려는 객체에 대해 임의의 밀도로 표현하기 때문에 객체 및 데이터의 움직임에 다양한 방향에 대한 모델을 생성할 수 있다.

영상의 단순한 픽셀 정보뿐만 아니라 물체의 이동량을 계산하 여 모션 벡터를 활용한 Optical flow 알고리즘으로도 추적이 가 능하다[38]. Optical flow는 연속된 프레임 간의 위치/색상 차이 를 통해 움직임을 추정하는 방법으로 영상에서 발생하는 움직임 의 방향과 속도를 벡터적으로 나타내는 방식이다. 대표적 알고리 즘으로는 LK (Lucas-Kanade) 알고리즘이 있으며, 패치 단위의

위치 추정 기법을 사용한다. 이는 주변 픽셀의 움직임은 같은 모 션 벡터를 가진다는 가정으로 연속된 프레임에서 물체를 추정하 는 방식으로 LK 알고리즘 기반 KLT (Kanade-Lucas-Tomasi) 추적기가 여러 연구에서 널리 사용되고 있다[50].

최근에는 안정적인 물체 추적을 위해 통계적 모델 (Statistical model) 기반 추적 방식들이 제안되고 있다[34-37]. 통계적 모델 기반 추적 방식은 객체의 검출 확률을 GMM (Gaussian Mixture Modeling)과 같이 데이터를 결합 확률로 표현하는 생성 (Generative) 모델과 SVM (Support Vector Machine)과 같은 분류기의 결과 값을 최대화 시키는 조건부 확률로 모델을 표현 하는 판별 (Discriminative) 모델로 나눌 수 있다. 이러한 개념은 이전부터 존재하였지만, 학습 기반 추적 방식이 제안되면서 보 다 많은 연구에 적용되고 있으며, 대표적인 학습 기반 추적 에는 Kalal이 제안한 TLD (Tracking-Learning- Detection)[34] 추 적 프레임워크가 있다.

그림 19. Tracking-Learninig-Detection 구조[34]

TLD 에서는 검출기와 추적기를 병렬적으로 구성하여 추적 기에서는 Optical flow 기반의 추적기를, 검출기에서는 ferns를 사용하였다. 추적이 성공했다면 물체의 일정 영역이 검출기의 학습 데이터로 활용되어 업데이트 된다. 검출기가 찾은 영역들 중에서 추적 결과와 일치하지 않은 영역들은 오검출로 분류되 어 검출기를 업데이트하기 위한 negative 샘플이 된다. 만약, 추 적이 실패한 경우 물체가 다시 검출 될 때까지 추적기는 동작 하지 않고, 검출이 성공되면, 검출된 위치를 기준으로 추적을 시작하는 방식을 사용하였다.

2.5 실시간 모바일 시스템 구현을 위한 연구 동향 상기 절에서는 특징점 검출, 특징점 기술, 특징점 매칭, 추적 분야에 대한 연구 동향을 소개하였다. 본 절에서는 모바일 임베 디드 시스템에서의 실시간 증강현실을 위한 특징점 인식 및 추 적 알고리즘의 최신 연구 추세에 대해 정리한다. 적용 어플리케 이션 및 모바일 프로세서의 저장 공간, 처리 속도에 따라 이는 달라질 수 있음을 명시한다.

그림 22. 관광 지도 인식 및 추적 알고리즘 흐름

표 1. 실시간 모바일 시스템 구현을 위한 연구 동향

요소 기술 연구 동향

특징점 검출 FAST, AGAST 방식 고도화 (스케일 등 환경 변화 고려) 특징점 기술 저장 공간 및 속도를 고려한 이진 기술자 고도화 특징점 매칭 효율적 매칭을 위한 트리 등 매칭 구조체 사용 특징점 추적 추적 성능 향상을 위한 온라인 학습 방식 사용

3. 사례 연구：모바일 기반 관광 지도 인식 시스템

본 절에서는 모바일 증강 현실 서비스와 관련하여 본 한국과 학기술연구원 연구팀이 수행한 모바일 기반 관광 지도 인식 및 추적 연구를 소개하고자 한다. 모바일 기반 관광 지도 인식은, 관광객에게 부가적인 관광 정보를 제공하기 위해, 관광객이 소 지하고 있는 오프라인 관광지도를 학습하여 사용자가 추가적인 관광 정보를 요청할 시, 오프라인 관광지도를 스마트폰 등의 모 바일 기기로 비추면, 관광지도 위에 부가적인 관광 정보 (POI (point of interests) 등)가 2차원 혹은 3차원으로 증강되는 증강 현실 투어 가이드 시스템을 위한 것이다.

그림 20. 모바일 기반 관광 지도 인식 시스템

그림 20은 모바일 기반 관광 지도 인식 시스템의 전체적인 흐름도이며, 인식을 위해 모바일 기기의 카메라를 통해 영상이 입력되면 영상의 특징점을 추출하여 저장된 영상 특징점 데이 터베이스와 비교하여, 관련 정보를 인식한다.

그림 21. 인식 대상인 관광 지도의 예

모바일 기반의 관광 지도 인식 시스템을 구성하기 위해 다음 과 같은 사항이 고려되었다. 우선 인식 대상인 관광 지도 책자 [그림 21]는 각 페이지마다 서로 다른 관광지에 대한 정보를 포함하고 있지만, 일반적인 객체 영상에 비해 단순하고 중복적 인 아이콘, 패턴이 다수 발생하여 오인식 (false match)의 가능 성이 높다. 또한 stand-alone 모바일 인식 환경을 고려하여, 매 칭 속도 및 데이터베이스의 사이즈도 고려하여야 한다. 따라서 본 연구에서는 모바일 환경에서의 실시간성을 보장하기 위해 이진 기술자를 통한 데이터베이스 생성 및 매칭을 수행하였고, 오인식의 문제를 해결하기 위해서는 대칭 (symmetric) 매칭 방식을 제안하였으며, 추적 성능을 향상시키기 위해서는 특징 점 재생산 (reproduction) 방식 알고리즘을 추가적으로 제안하 였다.

본 모바일 기반 관광 지도 인식 및 추적 알고리즘의 간략한 알고리즘은 아래와 같다[그림 22].

•데이터베이스 사이즈 및 매칭 속도를 고려하여 학습 및 입 력 영상에서 Multi-scale AGAST를 통한 특징점 검출 및 BRISK 기술자를 통한 영상 기술을 수행한다.

•특징점 오인식을 줄이기 위한 1차 과정으로 NN (Nearest Neighbor) 매칭 및 최근접 거리 비율 (ratio) 매칭을 통한 대응점 검출을 수행한다.

•추가적인 오인식 제거를 위해 학습 영상 및 입력 영상간의 비교 순서를 변화시켜, 동일한 특징점이 매칭될 때의 결과 만을 채택하는 대칭 (symmetric) 매칭을 수행한다.

•지도 인식 시, 입력 영상과 매칭되는 특징점의 개수가 가

장 높은 학습 영상을 인식 대상으로 선정한다.

•매칭 완료 후, RANSAC 알고리즘을 이용하여 이상점 제 거 및 지도의 포즈를 계산하고, 일정 프레임 이상 동일 영 상이 인식되는 경우 이후에는 KLT 추적기를 사용하여 추 적을 수행한다.

•추적 시, 특징점이 소실되는 현상을 방지하기 위해 일정 개 수 이하의 특징점이 매칭되는 경우 (본 논문의 경우 6개), 특징점 검출 모드와 추적 모드 간의 모드 전환 (context switch)을 통한 관심 영역 (Region of interest) 내의 특징점 재생산 (재검출)을 통하여, 특징점의 추가 매칭 및 추적을 통하여 포즈 계산 및 추적의 성능을 향상시킨다[그림 23].

그림 23. 특징점 재생산을 통한 추적 성능 향상

그림 24. 관광 지도 인식의 예

그림 25. 3차원 객체 증강의 예

그림 24와 25는 상기 설명한 알고리즘을 바탕으로, 모바일 기기 상에서의 관광 지도 인식 및 추적을 통한 3차원 객체 증강 의 예를 보여준다. 그림에서 보는 바와 같이, 다양한 지도 영상 (서울시 관광 지도, 총 16장)에 대한 인식을 이진 서술자와 대 칭 매칭을 통해 성공적으로 수행하였으며, 추적 시에는 iPhone 5S 모바일 기기에 대하여 약 25fps 이상의 속도를 달성하였다.

4. 결론

본 논문에서는 모바일 기반 마커리스 증강 현실 서비스 구현 을 위한 핵심 요소 기술 중, 특징점 기반의 객체 인식 및 추적 기술 동향에 대해 살펴보았다. 모바일 증강 현실 서비스 시장의 급속한 성장과 더불어 국내에서도 다양한 서비스들이 제공되 고 있지만, 국내 대부분의 증강현실 서비스는 외산 플랫폼 (퀄 컴의 Vuforia, 애플의 Metaio 등)에 기반을 두어 개발되고 있는 실정이다. 따라서 향후 시장 확보를 위한 국내 기술의 경쟁력의 증대를 위해서는 증강현실 콘텐츠 개발뿐만 아니라, 핵심 인식 및 추적 엔진의 지속적인 개발과 고도화가 필요한 실정이다. 본 논문에서는 이를 위해 특징점 인식 및 추적 기술에 대한 연구 동향, 사례 연구인 모바일 기반 관광 지도 인식 시스템을 설명 하였으며, 관련 내용이 증강 현실 분야의 연구자 및 개발자들에 게 많은 도움이 되길 기대한다.

참고문헌

[1] Tuytelaars, T. and Mikolajczyk, K. Local Invariant Feature Detectors: A Survey. Foundations and Trends in Computer Graphics and Vision. Vol. 3.

No. 3. pp. 177~280. 2007.

[2] Harris, C. and Stephens, M. A combined corner and edge detector. Proceedings of the 4th Alvey Vision Conference. pp. 147~151. 1988.

[3] Shi, J. and Tomasi, C. Good Features to Track.

Computer Vision and Pattern Recognition. 1994.

[4] Lindeberg, T. Feature Detection with Automatic Scale Selection. International Journal of Computer Vision. Vol. 30. No. 2. pp. 79~116. 1998.

[5] Mikolajczyk, K. and Schmid, C. Indexing based on Scale Invariant Interest Points. Proceedings of the International Conference on Computer Vision. pp.

525~531. 2001.

[6] Lowe, D. G. Distinctive Image Features from Scale Invariant Keypoints. International Journal of Computer Vision. Vol. 60. No. 2. pp. 91~110. 2004.

[7] Mikolajczyk, K. and Schmid, C. Scale & Affine Invariant Interest Point Detectors. International Journal of Computer Vision. Vol. 60. No. 1. pp.

63~86. 2004.

[8] Smith, S. M. and Brady, J. M. SUSAN- A New Approach to Low Level Image Processing. International Journal of Computer Vision. Vol. 23. No. 1. pp. 45~78.

1997.

[9] Rosten, E. and Drummond, T. Fusing points and lines for high performance tracking. Proceedings of the International Conference on Computer Vision.

pp. 1508~1511. 2005.

[10] Klein, G. and Murray, D. Parallel Tracking and Mapping on a Camera Phone. Proceedings of International Symposium on Mixed and Augmented Reality. pp. 83~86. 2009.

[11] Mair, E., Hager, G. D., Burschka, D., Suppa, M.

and Hirzinger, D. Adaptive and Generic Corner Detection Based on the Accelerated Segment Test.

European Conference on Computer Vision. 2010.

[12] Leutenegger, S., Chli, M. and Siegwart, R. Y.

BRISK: Binary robust invariant scalable keypoints.

International Conference on Computer Vision. 2011.

[13] Matas, J., Chum, O., Urban, M. and Pajdla, T.

Robust wide-baseline stereo from maximally stable extremal regions. Proceedings of the British Machine Vision Conference, pp. 384–393, 2002.

[14] Ren X. and Malik, J. Learning a classification model for segmentation. Proceedings of the International Conference on Computer Vision. pp. 10–17, 2003.

[15] Bay, H., Tuytelaars, T., Van Gool, and L. SURF:

Speeded Up Robust Features. European Conference on Computer Vision. 2006.

[16] Cornelis, N. and Van Gool, L. Fast scale invariant feature detection and matching on programmable graphics hardware. Computer Vision and Pattern Recognition Workshops. 2008.

[17] Ke, Y. and Sukthankar, R. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors.

Computer Vision and Pattern Recognition. 2004.

[18] Mikolajczyk, K. and Schmid, C. A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol.

10, No. 27, pp. 1615~1630. 2005.

[19] Tola, E., Lepetit, V. and Fua, P. DAISY: An Efficient Dense Descriptor Applied to Wide Baseline Stereo. IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 32, No. 5, pp. 815~830.

2010.

[20] Calonder, M., Lepetit, V., Strecha, C. and Fua, P.

Brief: Binary robust independent elementary features.

European Conference on Computer Vision. 2010.

[21] Rublee, E., Rabaud, V., Konolige, K. and Bradski, G. ORB: an efficient alternative to SIFT or SURF.

Proceedings of the International Conference on Computer Vision. pp. 2564~2571. 2011.

[22] Alahi, A., Ortiz, R. and Vandergheynst, P. FREAK:

Fast retina keypoints. Computer Vision and Pattern Recognition. 2012.

[23] Grauman, K. and Leibe, B. Visual Object Recognition.

Morgan & Claypool Publisher. 2010.

[24] Freidman, J., Bentley, J. and Finkel, A. An

Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software. Vol. 3, No. 3, pp. 209~226. 1997.

[25] Muja, M. and Lowe, D. Fast approximate nearest neighbors with automatic algorithm configuration.

International Conference on Computer Vision Theory and Application. 2009.

[26] Silpa-Anan, C. and Hartley, R. Optimised kd-trees for fast image descriptor matching, Computer Vision and Pattern Recognition. 2008.

[27] Lecture on Kd-tree.

www.cise.ufl.edu/class/cot5520fa09. July 10. 2015.

[28] Lepetit, V. and Fua, P. Keypoint Recognition using Randomized Trees. IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol.

28, No. 9, pp. 1465~1479. 2006.

[29] Ozuysal, M., Calonder, M., Lepetit, V. and Fua, P.

Fast Keypoint Recognition Using Random Ferns.

IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 32, No. 3, pp. 448~461. 2010.

[30] Shakhnarovich, G., Darrell, T. and Indyk, P.

Nearest-Neighbor Methods in Learning and Vision:

Theory and Practice. MIT Press. 2006.

[31] Locality sensitive hashing.

https://micvog.files.wordpress.com/2013/08/lsh1.pn g. July 10. 2015.

[32] Fischler, M. and Bolles, R. Random Sampling Consensus: A Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography. Communications of the ACM. Vol. 24.

No. 6. pp. 381~395. 1981.

[33] Ballard, D. H. Generalizing the Hough Transform to Detect Arbitrary Shapes. Pattern Recognition, Vol.13. No.2. pp.111~122. 1981.

[34] Kalal, Z., Mikolajczyk, K. and Matas, J. Tracking- learning-detection. IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 34. No. 7 pp. 1409~1422. 2012.

[35] Hare, S., Saffari, A. and Torr, P. Efficient online structured output learning for keypoint-based object tracking. Computer Vision and Pattern Recognition. 2012.

[36] Zhang, K., Zhang, L. and Yang, M. Real-time compressive tracking. European Conference on Computer Vision. 2012.

[37] Bouachir, W. and Bilodeau, G. Structure-aware keypoint tracking for partial occlusion handling.

IEEE Winter Conference on Applications of Computer Vision. 2014.

[38] Lucas, B. D. and Kanade, T. An iterative image registration technique with an application in stereo

vision. International Joint Conferences on Artificial Intelligence. 1981.

[39] Yu, Q., Dinh, T. B. and Medioni, G. Online tracking and reacquisition using co-trained generative and discriminative trackers. European Conference on Computer Vision. 2008.

[40] Zhou, H., Yuan, Y. and Shi, C. Object tracking using sift features and mean shift. Computer Vision and Image Understand. Vol. 113. No. 3. pp.

345~352. 2009.

[41] He, W., Yamashita, T., Lu, H. and Lao, S. Surf tracking. International Conference on Computer Vision. 1586–1592. 2009.

[42] Comaniciu, D., Ramesh, V. and Meer, P. Kernel- based object tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 25. No. 5.

pp. 564~577. 2003.

[43] Li, M., Zhang, Z., Huang, K. and Tan, T. Robust visual tracking based on simplified biologically inspired features. International Conference on Image Processing. 2009.

[44] Ronfard, R. Region-based strategies for active contour models, International Journal of Computer Vision, Vol. 13 No. 2. pp. 229~251. 1994.

[45] Kalman, R. A new approach to linear filtering and prediction problems. Journal of Fluids Engineering.

Vol. 82 No. 1 pp. 35~45. 1960.

[46] Welch, G. and Bishop, G. An introduction to the Kalman filter. University of North Carolina at Chapel Hill Chapel Hill. Technical Report TR95041.

2000.

[47] Arulampalam, M., Maskell, S., Gordon, N. and Clapp, T. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing. Vol. 50. No. 2 pp. 174~188. 2002.

[48] Julier, S. J. and Uhlmann, J. K. A new extension of the Kalman filter to nonlinear systems. International Symposium on Aerospace Defense Sensing, Simulations and Controls, 1997.

[49] Wan, E. and Merwe, R. The unscented Kalman filter for nonlinear estimation. Adaptive Systems for Signal Processing, Communications, and Control Symposium. 2000.

[50] Tomasi, C. and Kanade, T. Detection and tracking of point features. Carnegie Mellon University. 1991.

[51] Heinly, J., Dunn, E. and Frahm, J. Comparative evaluation of binary features. European Conference on Computer Vision. 2012.

최 희 승

2000년 3월~ 2004년 2월 연세대학교 전기 전자공학과 졸업(공학사). 2004년 3월 ~ 2006년 2월 연세대학교 대학원 전기전자공 학과 졸업(공학석사). 2006년 3월 ~ 2011년 2월 연세대학교 대학원 전기전자공학과 졸 업(공학박사). 2011년 ~ 2012년 미국 미시간 주립대 박사 후 연 구원. 2013년 ~ 현재 한국과학기술연구원 영상미디어연구단 위 촉연구원. 관심분야는 컴퓨터 비전, 패턴 인식, 바이오 인식, 증강현실임

안 상 철

1984년 3월 ~ 1988년 2월 서울대학교 제어 계측공학과 졸업(공학사). 1988년 3월 ~ 1990년 2월 서울대학교 제어계측공학과 졸 업(공학석사). 1990년 3월~ 1996년 2월 서 울대학교 제어계측공학과 졸업(공학박사).

1996년~ 1997년 미국 USC Computer Science Dept. (Visiting Scholar). 1997년~2004년 KIST 영상미디어연구센터 선임연구 원. 2004년~현재 KIST 영상미디어연구센터 책임연구원. 2011~

현재 KIST 영상미디어연구단 단장. 관심분야는 Mixed Reality, Vision based Human Computer Interaction, Telemeeting, IBMR임

김 익 재

1992년 3월 ~ 1996년 2월 연세대학교 전기 공학과 졸업(공학사). 1996년 3월 ~ 1998년 2월 연세대학교 대학원 졸업(공학석사).

2003년 9월~ 2009년 2월 서울대학교 대학 원 졸업 (공학박사). 2009년~2010년 MIT Media Lab 박사후연구원. 1998년 3월~현재 한국과학기술연구 원 영상미디어연구단 책임연구원. 관심분야는 컴퓨터 그래픽스, 컴퓨터 비전, 얼굴 인식, 증강ㆍ가상현실임