페이지_ 18권 3호 전체-30-36.pdf2.26MB

• 1. 서 론
• 2. 관련연구
• 2.1 SIFT
• 2.2 SURF
• 3. 제안한 알고리즘
• 3.1. Integral image
• 3.2. 관심 영역 검출
• 3.3. 불변 특징점 검출
• 3.4. 적응적 NMS
• 4. 실험 및 분석
• 5. 결 론
• Acknowledgement

1. 서 론

물체를 추적하는 방법에 관한 연구는 여러 방향으로 이루어지고 있으며, 크게 영역, 외곽선, 특징점 및 모델 기반 추적의 네 가지로 분류 할 수 있다^[1,2]. 특히, 최근 다방면에서 적용되고 있는 Markless AR분야에서는 주로 특징점 기반 추적 방식이 사용되고 있으며, 대표적인 방법으로 Lowe의 SIFT 알고리즘^[3]과 Bay의 SURF 알고리즘^[4]이 있다. 

본 논문에서는 SIFT 알고리즘과 비슷한 정합 성능을 가지고 있으며, 빠른 속도를 가지고 있는 SURF 알고리즘을 효율성을 높이는 새로운 특징 추출 알고리즘을 제시한다. 기존의 SURF 알고리즘은 불변 특징점을 보장하기 위해 이미지 피라미드를 이용하는데, 이러한 이미지 피라미드의 구현을 위해 많은 연산을 필요로 하게 된다. 또한 특정 크기의 블록 단위 NMS 기법을 사용함으로써 불필요한 연산이 수행되어 연산량이 많아지는 단점이 발생한다.

제안된 알고리즘은 관심점을 검출하고 검출된 점들에서 특징점을 구하는 기법을 사용하여, 불변 특징점을 보장하면서 불필요한 연산을 줄일 수 있도록 하였다. 또한 적응적 NMS 기법을 적용하여 연산을 줄일 수 있는 효율적인 특징 추출 알고리즘을 개발하였다. 

2. 관련연구

2.1 SIFT

SIFT(Scale Invariant Feature Transform)알고리즘^[3]은 특징점 기반 추적 방법 중의 하나로 불변 특징점을 이용하여 물체를 추적하는 방법이다. SITF 알고리즘은 특징점을 찾는 단계와 특징점의 Descriptor를 찾는 두 단계로 구성되며, 기본 아이디어는 Figure 1과 같이 이미지 피라미드를 구성하여 반복되는 불변특징점을 찾는 것이다. 

Figure 1. Scale pyramid

SIFT 알고리즘은 다음 절차로 수행된다^[3]. 

1) 식 (1)을 사용하여 여러 scale에서 가우시안 이미지를 생성한다 

2) 식 (2)를 사용하여 Figure 2에서 보이는 것과 같은 DoG (Difference-of-Gaussian) 이미지를 생성한다. 

Figure 2. Difference-of-Gaussian

3) DoG 이미지를 이용하여 이미지 피라미드를 구성한 후, Figure 3과 같이 중심점을 기준으로 이웃한 Scale의 26개 픽셀의 비교를 통해 극대값과 극소값을 구하여 특징점 후보를 찾는다. 

Figure 3. Maximum and minimum value detection

4) 문턱치값과 DoG값의 비교를 통해 낮은 contrast를 갖는 특징점 후보를 우선적으로 여과하고, 식 (3)과 같은 Hessian 행렬을 통해 특징점 후보를 다시 여과한다. 

SIFT 알고리즘은 우수한 성능으로 인해 최근 디지털 영상 처리 분야에 많이 사용되고 있지만, 이미지 피라미드를 구성하기 위해 많은 연산이 필요하다는 단점이 존재한다.

2.2 SURF

SURF 알고리즘^[4]은 특징점 기반 추적 방법 중의 하나로 SIFT를 개선하여 고속으로 불변 특징점을 추적하는 방법이다. SURF 알고리즘은 Integral image와 가우시안 2차 미분을 근사화한 사각필터를 이용한 고속 Hessian 검출기를 사용하여 수행시간을 획기적으로 단축하였다. 그 결과, SURF 알고리즘은 SIFT 알고리즘과 비슷한 정합 성능을 가지면서 빠른 속도를 보장하는 장점을 가진다. 

3. 제안한 알고리즘

기존의 SURF 알고리즘^[4]은 이미지 피라미드를 사용하여 불변 특징점을 보장하기 때문에, 이미지 피라미드의 구성을 위해 많은 연산을 필요로 한다. 또한 블록 단위의 NMS방식을 사용하기 때문에 불필요한 연산이 수행되는 단점이 발생한다. 본 논문에서는 이러한 단점을 보완한 효율적인 특징 추출 알고리즘을 제안하였다. 

본 논문에서 제안하는 특징 추출 알고리즘은 다음과 같다. 

Figure 4. Block diagram of the proposed algorithm

SURF알고리즘에서는 integral image와 근사화 된 Hessian detector^[6]에 기반을 둔 고속 Hessian detector^[4]를 사용하여 특징점을 추출한다. 

제안된 알고리즘에서는 관심점 검출에 고속헤이시안 검출기를 사용하여 연산을 최소화하여 빠른 수행속도를 보장한다. 

3.1. Integral image

Integral image는 x,y방향으로의 원본이미지화소 값의 누적 합(cumulative sum)을 계산한 이미지로 정의할 수 있으며, 이 이미지를 이용하면 임의의 크기의 사각형 내부에 대한 화소 값의 합을 크기에 상관없이 일정시간 내에 빠르게 계산할 수 있다. 식 (4)는 x,y 위치에서 integral image의 응답 값을 구하는 과정을 나타내며, I(i, j)는 원본 영상에서의 i,j위치의 화소 값을 의미한다. 

Integral image에서 사각형 영역의 누적 합은 Figure 5의 (b)와 같은 방법으로 계산되기 때문에 일정한 시간 내에 빠른 속도의 연산이 가능하다. 

Figure 5. (a) Integral image (b) Calculation of Integral image (S=A-B-C+D)

3.2. 관심 영역 검출

Hessian detector는 식 (5)에 정의된 Hessian matrix에 기반을 둔 특징점 추출 알고리즘으로 속도와 정확도에서 우수한 성능을 보인다.

제안된 방식에서는 Hessian 행렬식을 사용하는 integral image와 Figure 6과 같이 근사화 된 box filter를 이용한 Hessian 행렬식을 이용한 고속 Hessian detector^[4]를 이용하여 영상의 경계 및 모서리 후보인 관심점을 계산한다. 

Figure 6. Approximated box filter

Integral image와 box filter를 이용한 영상의 관심점 검출은 식(6)과 같은 방식으로 결정되며, 헤이시안 행렬식과 비슷한 결과를 얻기 위해 상대적 가중치 w가 사용된다. 이 때 w는 식 (7)과 같은 방식으로 계산된다. 

제안된 논문에서는 효율적인 관심점 검출을 위해 다양한 크기의 box filter를 사용하였고 Figure 6에서 나타난 것과 같이 9 × 9 box filter를 사용했을 경우 가장 우수한 결과를 얻을 수 있었다. 또한 Figure 7과 같은 근사화된 box filter를 사용하여 σ = 1.2인 가우시안 2차 미분 필터와 유사한 결과를 얻을 수 있었다. 

Figure 7. Result of Hessian detector (a) 9×9 (b) 15×15 (c) 21×21

3.3. 불변 특징점 검출

제안된 알고리즘은 고속 Hessian detector를 이용해 검출된 관심점들에서 강도가 강한 모서리점을 Harris corner detector^[7]를 사용하여 불변 특징점을 추출한다. 

Harris corner detector는 모서리점 검출 방법 중 하나로 지역적 신호의 상호관계를 기반으로 회전과 비율, 조명 및 영상의 잡음에 대해서 매우 강력한 특징 검출 성능을 보여주는 알고리즘이다^[8]. Harris corner detection은 일반적으로 다음과 같은 절차^[9]로 수행된다. 

1) 영상 I에 대한 1차 미분∇I = [I_x, I_y]를 구한다. 

2) 행렬 M을 이용하여 R(x,y)를 구한다. 

3) 문턱치값 T를 정하고, 모든 좌표 (x, y)에 대하여 R(x, y) < T=0 을 수행한다. 

4) 정방형 블록의 크기를 정하고, 전체 이미지를 분할 한 후 각 블록에서 일정한 수의 점을 R(x, y)의 강도로 추출한다. 

제안된 알고리즘은 고속 Hessian detector로 검출된 관심점에서 Harris corner detector를 적용한다. 이 때, 크기와 회전에 강인한 불변 특징점을 보장하기 위해 Harris corner detector의 크기를 3×3, 21×21, 15×15 순으로 변화시키면서 모서리점을 검출하였다. 화소의 모서리 유무를 빠르게 판단하기 위해 초기에 3×3 크기의 최소 창을 사용하였다. 이렇게 최소 창에서 추출된 모서리 점에 대해서만, 21×21 크기의 최대 창으로 모서리를 검출하였다. 최대 창에서도 모서리로 판단된 점은 강한 모서리이므로, 후보 불변 특징점으로 선택된다. 마지막으로 중간 크기의 15×15 창에서는 최소 창에서 검출되고 최대 창에서 모서리로 검출되지 않은 점들에 대해서 모서리 검출을 수행하여 후보 불변 특징점에 추가시킨다. 이 과정에서 모서리 검출에 사용된 창의 크기는 저장되어 뒤의 적응적 NMS에 활용된다. 그러므로, 기존의 SURF 알고리즘은 각 옥타브의 모든 화소에 대해 창의 크기를 계층적 scale로 변화시켜 특징추출을 수행하기 때문에 속도가 느리지만, 제안한 알고리즘은 영상 피라미드 생성을 제거하고 관심점으로 검출된 화소에 대해서 최소 크기의 창을 이용해 빠르게 모서리점을 검출한 뒤, 중복되지 않게 21×21과 15×15 크기의 창으로 후보 불변 특징점을 결정하므로 보다 빠른 결과를 가져온다. 

3.4. 적응적 NMS

SURF 알고리즘은 블록 단위 NMS방식^[11]을 사용하기 때문에 대부분의 특징점들이 분포되어 있는 중심영역이 아닌 주변영역에서도 연산을 수행한다. 

제안된 알고리즘에서는 경계를 기반으로 한 모서리점을 이용해 불변 특징점을 추출하기 때문에 핵심 특징이 많이 분포되어 있는 중심영역에서 NMS를 수행한다. 또한, 고정되어 있는 크기의 블록단위 NMS가 아니라 모서리점이 검출된 Harris corner detector의 filter size와 모서리점의 방향성을 이용하여 NMS를 수행함으로써 빠른 연산 속도를 보장하였다.

4. 실험 및 분석

실험은 최근 가장 많이 사용되는 특징점 추출 알고리즘인 SURF^[4]알고리즘과 제시한 알고리즘을 비교하는 실험과 다양한 scale과 rotation된 영상을 제안된 알고리즘에 적용한 결과를 비교하는 실험을 수행하였다. 사용된 컴퓨터는 Intel(R) Core(TM)2 Duo CPU 3.00GHz 이며 실험영상으로는 Figure 8에서 보이는 것과 같이 건물과 해바라기 이미지를 사용하였다. 

Figure 8. (a) Building (457×630) (b) Sunflower (640×437)

첫 번째 실험은 동일한 영상을 SURF 알고리즘과 제안된 알고리즘에 적용하여 수행시간과 특징점의 수를 비교하는 형태로 수행되었으며, 실험결과는 Table 1에 나타난 것과 같다. 제안된 알고리즘은 수행시간에서 우수한 성능을 나타내었으며, SURF 알고리즘과 비교할 때 적은 수의 특징점을 추출하였다.

Table 1. Result of experiments

제안된 알고리즘은 SURF 알고리즘에서 이미지 피라미드를 만들기 위해 영상의 확대 및 축소와 크기 보상(interpolation)을 수행하는 과정이 없으며, 핵심 영역에서만 적응적 NMS를 수행하기 때문에 수행속도 측면에서 상대적으로 우수한 성능을 보였다. 

Figure 9는 실험영상에 SURF와 제안된 알고리즘을 적용한 결과 영상이다. SURF 알고리즘과 비교할 때 제안된 알고리즘에서 검출된 특징점의 수가 상대적으로 적지만 핵심영역에서는 비슷한 형태의 특징점들이 검출되는 결과를 확인 할 수 있었다. 

Figure 9. Result images (a) and (c) : proposed algorithm (b) and (d) : SURF algorithm

두 번째 실험은 영상의 크기를 변화시키거나 회전시킨 후 제안된 알고리즘을 적용하였을 때의 결과를 분석하는 형태로 수행되었으며, 실험 결과는 Figure 10과 같이 영상의 크기를 변화시키거나 회전시켰을 경우에도 유사한 형태로 특징점이 발견됨을 알 수 있었다. 

Figure 10. Result images (a) double-size Sunflower image with the proposed algorithm (b) double-size Sunflower image with SURF algorithm (c) half-size Sunflower image with the proposed algorithm (d) half-size Sunflower image with SURF algorithm (e) rotated Sunflower image with the proposed algorithm (f) rotated Sunflower image with SURF algorithm

5. 결 론

본 논문에서는 이미지 피라미드와 블록 단위 NMS로 인해 많은 연산을 필요로 하는 기존의 SURF알고리즘을 개선하여 연산과 속도에서 우수한 효율적인 불변 특징 추출 알고리즘을 제시하였다. 

관심점을 기반으로 한 모서리검출기법을 통해 연산을 줄이면서 불변 특징점 검출을 보장하였으며, 적응적 NMS를 이용하여 연산과 속도를 개선하였다. 그 결과 기존의 SURF 알고리즘과 핵심 영역에서는 비슷한 특징 추출 성능을 보장하면서 연산량과 속도면에서 우수한 결과를 얻을 수 있었다. 

향후 특징점의 추출과 정합이 연속적으로 이루어질 수 있는 완벽한 알고리즘의 개발을 위해 descriptor 생성에 관한 연구가 필요하다고 할 수 있다.

Acknowledgement

이 연구는 금오공과대학교학술연구비에 의하여 지원된 논문임