Ⅰ. 서 론

증강현실(augme reality)은 실(real) 영상에 존재하지 않는 다양한 부가적인 가상(virtual) 정보를 중첩하여 보여주는 기술로서, 사용자의 이해 및 흥미를 크게 개선시켜 줄수 있어 교육, 의료, 방송, 게임 등 다양한 분야에서 활용되고 있다. 특히, 최근에 모바일 기기의 확산과 함께 모바일 증강현실의 잠재력이 크게 주목받고 있어 증강현실 구현 기술에 대한 관심 및 수요가 보다 확대되고 있다.

증강현실 구현을 위한 가장 핵심적인 기술은 입력 영상으로부터 카메라의 위치 및 회전(흔히, 포즈라고 함)을 추정하는 것으로서, 다양한 형태의 방법들이 제안되어 왔으며, 크게 마커 기반과 비마커(markerless) 기반으로 나눌 수 있다. 마커 기반 방법들은 미리 고안된 형태와 색상을 가진 마커를 장면(scene)에 배치해 둠으로써, 카메라 입력 영상으로부터 쉽게 마커를 검출, 인식하여 카메라 포즈를 추정할 수 있다[1-3]. 반면, 비마커 기반 방법들은 원래 장면에 존재하는 주변과 구별되는 점이나 영역인 특징(feature) 정보들을 찾아 두고, 이를 카메라 입력 영상에서 검출, 인식하여 카메라 포즈를 추정한다[4,5]. 그러므로, 특징 검출, 기술(description), 매칭 방법을 필요로 하며, 대부분 특징 주변픽셀의 밝기나 그래디언트(gradient) 정보를 활용한다[6-8]. 마커 기반 방법과 비마커 기반 방법은 서로 대비되는 장단점을 가지고 있어 응용 분야에 따라 선택적으로 사용될 수 있다.

한편, LLAH(Locally Likely Arrangement Hashing)는 특징 사이의 기하 관계를 수학적으로 모델링하여 특징을 기술하는 방법으로[9], 이를 활용하면 랜덤하게 분포하는 점으로 이루어진 마커를 제작하여 마커 기반 증강현실을 구현할 수 있다[10]. 또한, 기존의 특징 기술 방법들은 주변 픽셀의 밝기나 그래디언트 정보를 활용하기 때문에 밝기나 그래디언트 변화가 적은 장면이나 객체(예, 텍스트 문서[11]나 도면[12]), 카메라 시점 변화가 큰 장면에서는 증강현실을 구현하기 힘들었으나, LLAH를 사용함으로써 이러한 장면이나 객체에 대해서도 효과적으로 비마커 기반 증강현실을 구현할 수 있다. 이처럼, LLAH는 기존의 방법과는 차별화된 형태 및 가능성을 가지고 있어, 증강현실의 응용 범위를 보다 확대할 수 있을 것으로 기대된다. 그러나, 사전 단계인 특징 검출 방법의 성능에 크게 의존적인 한계도 가지고 있어 관련 연구가 활발히 수행되지 못했다. 특히, LLAH가 여러 조건에 의해 성능이 결정될 수 있는데, 각 조건에 대한 명확한 성능 분석이 마련되지 못했다.

본 논문에서는 랜덤 점 마커를 추적하는 데 있어 LLAH의 여러 조건 중에 이웃 특징의 수의 변화, 특징 기술에 사용되는 기하 불변자(geometric invariants)의 변화, 특징 사이의 거리의 차이에 따른 성능을 분석하고, 최적의 조건을 찾고자 한다. [9]에서 일부 조건에 대해 문서 인식율에 대한 결과를 제시하고 있으나, 본 논문에서는 보다 다양한 조건에 대한 분석을 통해 명확한 성능 분석 결과를 마련하고, 무엇보다 각 특징의 개별 인식율을 분석함으로써, 랜덤 점마커 추적(및 증강현실)을 포함한 문서 인식 이외 분야에 대한 적용 가능성을 확인할 수 있다.

본 논문은 다음과 같이 구성된다. II 장에서는 LLAH를 이용하여 랜덤 점을 추적하는 방법에 대해 설명하고, III 장에서는 실험 및 분석을 통해 랜덤 점 추적을 위한 LLAH의 성능을 최적화한다. IV 장에서는 결론 및 향후 과제를 제시한다.

Ⅱ. LLAH를 이용한 랜덤 점 추적

1. LLAH

LLAH는 기본적으로 기존 특징점 기술 방법(특징 주변의 밝기나 그래디언트 정보 활용)을 적용하기 힘든 텍스트 문서를 인식하기 위해 개발된 방법으로, 특징 주변의 밝기나 그래디언트 변화가 작기 때문에 각 특징을 독립적으로 기술할 수 없어, 특징 간의 기하 관계를 활용한다. 촬영 조건에 따라 문서 영상이 어파인(affine) 또는 원근(perspec- tive)변환을 가지거나 각종 잡음, 이상치(outlier) 등을 포함할 수 있으므로, 이러한 다양한 왜곡에 대응하도록 각 특징을 기술할 수 있다.

각 프레임으로부터 높은 반복성을 가지는 특징이 반복적 로 검출되어 있다고 가정했을 때, LLAH는 다음과 같은 과정을 통해 각 프레임의 특징을 기술한다[9]. 우선, 각 특징(그림 1에서의 P)의 주변에서 거리가 가까운 순서대로n개의 이웃 특징(N1,N2,…,Nn)을 찾는다. 다음으로, 선택한 n개의 이웃 특징들로부터 m개의 특징 조합(Combination)을 구성한다(C1,C2,…,Cm). 이 과정은 각 프레임에서 검출된 특징이 잡음 등으로 인해 특징이 추가, 제거되거나 특징의 위치가 크게 변하는 경우에 대응하기 위한 것으로, 모든 조합의 수(nCm)가 각 특징을 기술하기 위해 계산되는 기술자(descriptor)의 개수가 된다. 각 기술자는 각 특징 조합내에서 다시 l개의 특징 조합을 구성한 후, l개의 특징으로 계산되는 삼각형 면적비(area ratio)나 교차비(cross ratio)등과 같은 기하 불변자 값을 계산한다. 결국 mCl개의 기하 불변자 값이 계산된다. 그러나, 이렇게 계산된 특징 기술자는 회전 불변성을 갖지 못하므로, 이웃 특징의 수만큼 계산된 기하 불변자 값들을 순환 시프트하면서 기술자를 생성한다. 특징 매칭의 효율성을 향상시키기 위해 각 mCl개의 기하 불변자 값들은 미리 정의된 해시(hash) 테이블을 이용하여 1차원 인덱스(index)로 변환된다. 그러므로, 특징 매칭은 공통된 인덱스를 가지는 특징을 찾는 과정을 통해 이루어진다.

그림 1.특징 기술을 위한 이웃 특징 선택 (n = 8, m = 5, l = 4인 경우). 특징 P를 기술하기 위해 n개의 이웃 특징(N) 사용 Fig. 1. Neighbor selection for feature description(when n = 8, m = 5, and l = 4)

2. 랜덤 점 추적

LLAH는 특징 좌표만 주어지면 기술될 수 있기 때문에, 그림 2와 같이 랜덤하게 분포하는 점들도 기술될 수 있으며, 증강현실 구현을 위한 마커로서 사용될 수 있다[10]. 또한, 그림 2(b)에서 보는 것처럼 각 점들은 독립적으로 기술되기 때문에 마커 내의 일부 점들이 가려지더라도 증강현실 구현이 가능하다. 랜덤 점의 경우, 카메라 영상 내에서 흰바탕에 검은 점들로 이루어져 있기 때문에 문턱값 처리, 연결요소 분석 등을 통해 쉽게 각 점의 위치를 검출할 수 있으며 반복성 또한 높다. 그러나, 카메라 포즈 변환 및 잡음 등으로 각 점의 위치에 오차가 발생하거나 이상치가 발생할 수 있는데, 이러한 경우n, m 값이나 기하 불변자의 종류에 따라 LLAH의 성능은 크게 달라진다. [10]에서는 n = 7, m = 5로 설정하고 기하 불변자로 삼각형 면적비(l= 4)를 사용하였으나, 이에 대한 구체적인 근거를 제시하지 않았다. LLAH는 특징 사이의 기하 관계를 활용하기 때문에 랜덤점 사이의 거리에 의해서도 성능이 달라질 수 있다[13]. 그러므로, 이에 대한 성능 분석도 마련되어야 한다.

그림 2.랜덤 점 마커 (a) 및 증강현실 구현 예 (b). (b)에서 좌측 상단 영상부터 입력 영상, 이진화 영상, 특징 검출 결과 영상, 각 마커의 위치를 보여주는 증강현실 결과 영상 Fig. 2. Example of Random dot marker (a) and augmented reality implementation (b). In (b), from left-top image, input image, binarization result, feature detection result, and augmented reality result that shows the location of each marker

Ⅲ. 가우시안 잡음을 가지는 랜덤 점 추적을 위한 LLAH의 성능 평가 및 분석

1. 실험 환경

논문에서는 가우시안 잡음에 의한 랜덤 점의 좌표 변환에 따른 LLAH의 성능(특징의 매칭률 및 매칭 시간)을 분석한다. 잡음에 의한 점(특징)의 좌표 변환은 실제 카메라영상에서 발생하는 어파인 및 원근 왜곡, 환경 잡음 등에 의한 좌표 변환을 부분적으로 포함하므로, 카메라 시점이나 환경 잡음의 영향을 간접적으로 파악할 수 있다1). 물론, 잡음에 의한 좌표 변환은 어파인 변환이나 원근 변환과는 상이하고 보다 열악한 조건이므로, 실험 조건에 따른 상대적인 성능 차이를 분석하는 데 보다 초점을 둔다.

앞서 설명한 대로, LLAH의 성능에 영향을 줄 수 있는 조건으로 이웃 특징의 수(n, m)과 기하 불변자의 종류, 특징사이의 거리가 고려된다. 기하 불변자로 선분 길이/각도비(LR), 삼각형 면적비(AR), 삼각형 교차비(CR)가 고려되며, 각각 l = 3, 4, 5개의 특징을 필요로 하며, 다음과 같이 계산된다[9,12].

여기서, 는 두 이웃 특징(Nk, Nk+1)을 잇는 선분을 나타내며, | · |는 선분의 거리, ∠( ·, · )는 선분 사이의 각도를 나타낸다. Δ( ·, ·, · )는 세 특징으로 이루어진 삼각형의 면적을 나타낸다.

성능 평가를 위해 700*700의 크기를 가지는 영상에 각각 30개(점 사이 평균 거리 약 150픽셀), 60개(점 사이 평균 거리 약 100픽셀), 120개(점 사이 평균 거리 약 70픽셀)의 점을 랜덤하게 배치한 영상을 참조 영상으로 두고, 각 점의x,y 좌표 값에 일정한 가우시안 잡음(표준 편차 = σ)을 더하여 변화시킨 영상들을 입력 영상으로 하였다. 참조 영상과 입력영상 내 점을 문턱값 처리와 연결요소 분석을 통해 검출한후, 특정 조건을 가진 LLAH를 사용하여 기술한 후 서로 매칭하였다. 입력 영상내의 각 특징과올바르게 매칭되는 참조영상 내 특징의 비율 및 매칭 시간을 측정하였다. 동일한 과정의 실험을 100번 반복 수행하였다. 모든 알고리즘은 코드 최적화 및 병렬처리 없이 C++을 사용하여 구현되었으며, i33.3GHz CPU와 4GB RAM을 가지는 PC에서 실행되었다.

2. 실험 결과

표 1, 2, 3은 각각 서로 다른 기하 불변자, 이웃 특징 수, 특징 사이의 거리를 사용한 LLAH의 가우시안 잡음 크기증가에 의한 매칭률 변화를 보여주고, 그림 3, 4, 5는 서로 다른 기하 불변자를 사용한 LLAH의 단일 특징을 매칭하는데 걸리는 시간을 보여준다. 여기서, 매칭 시간은 특징을 기술하는 데 걸리는 시간을 포함한다.

표 1-1.선분 길이/각도비 사용, 점(특징) 사이 거리가 150 픽셀일 때의 매칭률 (단위: %) Table 1-1. Using LR, matching rate when the distance between dots(features) is 150 pixels (unit: %)

표 1-2.선분 길이/각도비 사용, 점(특징) 사이 거리가 100 픽셀일 때의 매칭률 (단위: %) Table 1-2. Using LR, matching rate when the distance between dots(features) is 100 pixels (unit: %)

표 1-3.선분 길이/각도비 사용, 점(특징) 사이 거리가 70 픽셀일 때의 매칭률 (단위: %) Table 1-3. Using LR, matching rate when the distance between dots(features) is 70 pixels (unit: %)

표 2-1.삼각형 면적비 사용, 점(특징) 사이 거리가 150 픽셀일 때의 매칭률(단위: %) Table 2-1. Using AR, matching rate when the distance between dots(features) is 150 pixels (unit: %)

표 2-2삼각형 면적비 사용, 점(특징) 사이 거리가 100 픽셀일 때의 매칭률(단위: %) Table 2-2 Using AR, matching rate when the distance between dots(features) is 100 pixels (unit: %)

표 2-3삼각형 면적비 사용, 점(특징) 사이 거리가 70 픽셀일 때의 매칭률 (단위: %) Table 2-3 Using AR, matching rate when the distance between dots(features) is 70 pixels (unit: %)

표 3-1삼각형 교차비 사용, 점(특징) 사이 거리가 150 픽셀일 때의 매칭률 (단위:%) Table 3-1 Using CR, matching rate when the distance between dots(features) is 150 pixels (unit: %)

표 3-2삼각형 교차비 사용, 점(특징) 사이 거리가 100 픽셀일 때의 매칭률 (단위:%) Table 3-2 Using CR, matching rate when the distance between dots(features) is 100 pixels (unit: %)

표 3-3삼각형 교차비 사용, 점(특징) 사이 거리가 70 픽셀일 때의 매칭률 (단위:%) Table 3-3 Using CR, matching rate when the distance between dots(features) is 70 pixels (unit: %)

그림 3.선분 길이/각도비를 사용한 LLAH의 단일 특징 기술/매칭 시간 Fig. 3. Time for describing/matching a feature using LLAH with LR

그림 4.삼각형 면적비를 사용한 LLAH의 단일 특징 기술/매칭 시간 Fig. 4. Time for describing/matching a feature using LLAH with AR

그림 5.삼각형 교차비를 사용한 LLAH의 단일 특징 기술/매칭 시간 Fig. 5. Time for describing/matching a feature using LLAH with CR

기본적으로 선분 길이/각도비, 삼각형 면적비, 삼각형 교차비를 사용할 경우, 각각 m = 4, 5, 6 이상이어야 하며, n = 5, 6, 7 이상이어야 한다. 그러나, n,m이 일정 크기 이상이 되면 매칭 시간이 너무 길어져서 실시간 처리가 어려워지기 때문에 관련 결과는 생략했다. 가우시안 잡음 크기의 경우, 다른 조건에 따라 약간의 차이는 있으나 일정 크기 이상이 되면 매칭률이 급격히 감소하여 유의미한 분석 자료라고 볼 수 없어 관련 결과를 생략했다.

3. 결과 분석

이웃 특징 수에 대한 분석: 기본적으로, 잡음의 크기, 기하 불변자의 종류, 특징 사이의 거리에 상관없이 n과 m 값의 차이가 클수록 매칭률은 증가했다. 이는 n과 m의 차이값은 이론적으로 허용되는 이상치(outlier)의 수를 의미하기 때문에[10], 차이 값이 클수록 잡음에 의한 이상치 증가에 효과적으로 대응할 수 있기 때문인 것으로 판단된다. 같은 맥락으로, 동일한 n에 대해 m이 클수록 매칭률은 저하되며, 반대로 동일한 m에 대해 n이 증가할수록 매칭률은 증가했다. 그러므로, 매칭률을 향상시키기 위해서는 n 의 값을 크게 하고, m의 값은 작게 하는 것이 유리할 수 있다. m과 n 값의 차가 같을 경우, m 값을 작게 하는 것의 효과가 더 컸다.

그러나, n과 m 값이 증가함에 따라 매칭률은 빠르게 포화상태에 이르렀다. 또한, 그림 3, 4, 5에서 보는 것처럼 n과 m 값이 증가하면 매칭 시간이 급격하게 증가했다. 즉, 동일한 n에 대해 m이 증가하거나 동일한 m에 대해 n이 증가할 경우 매칭 시간은 크게 증가했다. 결국, 선분 길이/각도비를 사용할 경우 n = 8, m = 5 이상, 삼각형 면적비를 사용할 경우 n = 9, m = 5 이상, 삼각형 교차비를 사용할 경우 n = 9, m = 6 이상이 되면, 특징의 수가 30개 이상만 되어도 실시간 동작을 보장할 수 없었다.

결과적으로, n과 m값이 증가함에 따라 특징의 매칭률과 매칭 속도(매칭 시간의 역수)는 상충 관계에 있기 때문에, 적당한 값을 선택해야 한다. 실험을 통해, 선분 길이/각도비를 사용할 경우 n = 7, m = 4일 때, 삼각형 면적비를 사용할 경우 n = 8, m = 5일 때, 삼각형 교차비를 사용할 경우 n = 8, m = 6일 때 가장 우수한 성능을 보임을 알 수 있었다. 부가적으로, 기존 랜덤 점 마커 논문[10]에서 사용된 설정(n = 7, m = 5)은 매칭 사이의 거리가 일정 이상일 경우(표 2-1 참조)에는 n = 8, m = 5에 비해 속도 면에서 우수하기 때문에, 실시간 객체 인식/추적, 증강현실 분야의 특성을 고려했을 때 적절한 설정이었음을 알 수 있다. 그러나, 특징사이의 거리가 가까워질 경우(표 2-2, 2-3, 참조), 매칭률 저하가 크기 때문에 이에 대한 고려가 필요하다.

기하 불변자에 대한 분석: 이웃 특징의 수가 같은 경우 (각 표에서 n = 6, 7, 8, m = 5일 때 선분 길이/각도비 결과와 삼각형 면적비 결과 비교, n = 7, 8, 9, m = 6일 때 삼각형 면적비 결과와 삼각형 교차비 결과 비교) 가우시안 잡음의 크기 및 특징 사이의 거리에 상관없이 삼각형 교차비, 삼각형 면적비, 선분 길이/각도비 순으로 매칭률이 좋았다. 이는 이론적인 배경(각각 불변성이 보장되는 왜곡의 범주가 다름)과 일치하는 결과였다. 또한, 속도 면에서도 같은 순서를 보였다.

그러나, 이웃 특징의 수가 달라질 경우 기하 불변자의 영향은 축소되었다. 앞서 언급한 대로, 각 기하 불변자를 사용한 LLAH의 성능은 이웃 특징의 수에 따라 크게 달라지는데, 선분 길이/각도비를 사용하는 경우 같은 이웃 특징 수를 사용하면 삼각형 면적비를 사용하는 것에 비해 성능이 떨어지지만, 작은 m 값을 사용함으로써, 성능이 크게 향상될 수 있었다. 이론적으로, 삼각형 면적비는 선분 길이/각도비에 비해 특징 기술을 위해 하나의 이웃 특징을 더 필요로 하기때문에, m이 항상 같거나 클 수 밖에 없다. 이러한 경향은 삼각형 면적비와 삼각형 교차비 비교에서도 마찬가지이다.

주목할 점은 기하 불변자의 차이보다 이웃 특징 수의 차이에 의한 LLAH의 성능 변화가 더 컸다는 점이다. 실제 결과를 보면, 삼각형 면적비를 사용하는 경우 이웃 특징 수를 줄임으로써 매칭률이 삼각형 교차비를 사용하는 경우의 매칭률과 근접해졌으며, 동시에 매칭 속도가 크게 향상되었다. 또한, 선분 길이/각도비를 사용하는 경우에는 이웃 특징수를 줄임으로써 매칭률과 매칭 속도 모두 삼각형 면적비나 삼각형 교차비를 사용하는 것에 비해 크게 향상되었다.

특징 사이 거리에 대한 분석: 잡음의 크기, 기하 불변자의 종류, 이웃 특징의 수에 상관없이 특징 사이의 평균 거리가 감소하면 매칭률이 크게 감소했다. 이는 특징 사이의 평균 거리가 짧아지면 잡음의 영향이 상대적으로 커지기 때문인 것으로 판단된다. 그러므로, 특징 사이의 거리가 일정 이상이 되도록 하거나 특징 수를 제한하는 것이 필요할 것이다[13].

한편, 그림 6에서 보는 것처럼 가우시안 잡음의 크기가 클수록 매칭률의 저하도는 더 높았다. 그리고, 특징 사이 거리 감소로 인한 매칭률의 저하도는 이웃 특징의 수 n과m의 차가 클수록 낮았으며, m 값이 작을수록 낮았다. 또한, 선분길이/각도비를 사용할 경우 삼각형 면적비나 삼각형 교차비를 사용할 경우보다 특징 사이의 거리 감소로 인한 영향력이 낮았다. 결과적으로, 매칭률이 좋을수록 특징 사이 거리에 덜 민감한 것으로 분석된다.

그림 6.특징 사이 거리 감소로 인한 매칭률 저하도. 표 1, 2, 3의 결과를 평균한 결과 Fig. 6. Decreasing rate of matching rate caused by the reduction of distance between features. Average of the results in Tables 1, 2, and 3

랜덤 점 추적을 위한 LLAH의 성능 최적화: 실험 결과 및 분석을 통해 LLAH의 성능을 최적화하기 위한 이웃 특징 수, 기하 불변자의 종류, 특징 사이의 거리를 설정할 수 있다. 우선, 특징 사이의 거리가 작으면 영상 왜곡이나 잡음에 더 크게 영향을 받기 때문에 클수록 좋을 것이다. 그러나, 일정한 크기의 마커 내에 특징 사이의 거리를 크게 하기위해서는 특징 수를 제약해야 하는데, 특징 수가 제약되면 마커 사이의 분별성이 떨어지기 때문에 특징 사이의 거리를 무한정 크게 할 수는 없다. 다만, 이웃 특징 수나 기하 불변자 종류의 최적 설정을 통해 매칭률을 향상시킴으로써 특징사이 거리에 의한 영향을 크게 줄일 수 있다.

다음으로, 기하 불변자의 경우, 동일한 조건에서는 삼각형 교차비가 가장 우수한 성능을 가진다. 그러나, 이웃 특징의 수가 달라지면 각 기하 불변자의 성능은 크게 달라지며, 작은 m을 가지는 선분 길이/각도비가 보다 우수한 성능을 가진다. 마지막으로, 이웃 특징의 수는 m과 n 값의 차를 크게 하고, m 값을 작게 하는 것이 좋으며, 기하 불변자에 따라 다르게 설정되어야 한다. 결과적으로, 랜덤 점 추적을 위해 LLAH의 성능을 최적화하기 위해서는 n = 7, m = 4로 설정하고, 선분/길이 각도비를 사용해야 한다.

Ⅳ. 결론 및 향후 과제

본 논문에서는 랜덤 점 추적을 위한 LLAH의 성능을 최적화하기 위해 가우시안 잡음 하에서 이웃 특징의 수, 기하불변자의 종류, 특징 사이의 거리에 따른 각 점(특징)의 매칭률 및 속도를 분석했다. 또한, 실험 결과를 바탕으로 최적조건을 제시했다. 제시된 최적 조건 하에서는 특징점 사이의 평균 거리의 10% 이내의 크기 변화를 가지는 영상 왜곡 및 잡음 에 대해 각 특징이 80% 이상의 매칭률을 가지고, 실시간으로 매칭 및 추적이 가능하기 때문에 문서인식이나 증강현실을 포함한 다양한 응용 분야에 활용될 수 있을 것으로 기대된다.

향후, 랜덤 점 이외의 객체(특징 검출의 반복성이 높지않음) 추적에 대한 LLAH의 성능을 분석하고, 이를 최적화하거나 개선하기 위한 연구를 수행할 계획이다.