Copyright ⓒ 2016 The Korea Navigation Institute 53 www.koni.or.kr pISSN: 1226-9026 eISSN: 2288-842X http://dx.doi.org/10.12673/jant.2016.20.1.53
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-CommercialLicense(http://creativecommons .org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Received 3 February 2015; Revised 5 February 2016 Accepted (Publication) 19 February 2016 (28 February 2016)
*Corresponding Author; Do-Sik Yoo Tel: +82-2-320-3048
E-mail: [email protected]
영상 기반의 이차 칼만 필터를 이용한 객체 추적
Quadratic Kalman Filter Object Tracking with Moving Pictures
박 선 배 · 유 도 식
*홍익대학교 전자정보통신공학과
Sun-Bae Park · Do-Sik Yoo
*Department of Electronic, Information, and Communication Engineering, Hongik University, Seoul 04066, Korea
[요 약]
우리는 본 논문에서 이차 칼만 필터를 이용한 영상 기반 객체 추적분야의 새로운 알고리즘을 제안한다. 최근에 발표된 이 차 칼만 필터는 영상 기반의 객체의 실제 3차원 공간의 위치를 추적하는 것에는 아직 적용되지 않았다. 2차원 영상 내의 위치 를 3차원 공간상의 위치로 환원시키는 것은 비선형적 변환을 수반하기 때문에 그에 맞는 추적 알고리즘을 사용해야만 한다.
이러한 상황에서, 비선형 수식을 이차식으로 근사화하는 이차 칼만 필터가 선형으로 근사화하는 확장 칼만 필터보다 더 정확 한 성능을 낼 수 있다. 우리는 동일한 상황을 가정하여 확장 칼만 필터, 무향 칼만 필터, 파티클 필터, 그리고 우리가 제안한 이차 칼만 필터를 이용하여 객체를 추적하고, 그 결과를 비교해 본다. 결론적으로 이차 칼만 필터가 발산율이 확장 칼만 필터 에 비해 거의 절반가량 감소하며, 추적 정확도 측면에서 무향 칼만 필터에 비해 1% 가량 우수한 성능을 나타낸다.
[Abstract]
In this paper, we propose a novel quadratic Kalman filter based object tracking algorithm using moving pictures. Quadratic Kalman filter, which is introduced recently, has not yet been applied to the problem of 3-dimensional (3-D) object tracking. Since the mapping of a position in 2-D moving pictures into a 3-D world involves non-linear transformation, appropriate algorithm must be chosen for object tracking. In this situation, the quadratic Kalman filter can achieve better accuracy than extended Kalman filter. Under the same conditions, we compare extended Kalman filter, unscented Kalman filter and sequential importance resampling particle filter together with the proposed scheme. In conculsion, the proposed scheme decreases the divergence rate by half compared with the scheme based on extended Kalman filter and improves the accuracy by about 1% in comparison with the one based on unscented Kalman filter.
Key word :
Kalman filter, Non-linear filtering, Object tracking, Particle filter, Quadratic Kalman filter.http://dx.doi.org/10.12673/jant.2016.20.1.53 54
Ⅰ. 서 론
최근에 화두가 되고 있는 지능형 감시 시스템에서는 각 카메 라를 네트워크로 구성하여 이용하는 것이 필수적이다. 또한 이 러한 시스템을 구성하는데에 있어서 센서를 비롯한 별도의 장 비를 설치하는 것이 아니라 국내에 설치된 다수의 CCTV를 이 용하는 것이 경제적, 효율적인 측면에서 바람직하다고 할 수 있 다. 이러한 측면에서, 카메라 영상에 촬영된 객체의 실제 3차원 세계에서의 위치를 기반으로 하는 추적 알고리즘이 필수적이 라 할 수 있다. 센서 네트워크 상에서 서로간의 좌표를 공유하 여 전체적인 추적 성능을 높일 수 있고, 전체 지도에 객체의 위 치를 표시할 수 있음으로 전체적인 움직임을 관찰하기에 용이 하기 때문이다.
영상 기반의 객체 추적 알고리즘은 수많은 방향에서 진행이 되어 왔는데, 이는 추적의 기반이 되는 특징점을 추출하여 비교 하고, 각 프레임(frame)마다 나타난 객체의 동일성을 인식하는 컴퓨터 비전 (computer vision)분야의 연구가 꾸준히 활발하게 이루어졌기 때문이다. 본 논문에서는 카메라 영상으로부터 객 체의 영상 평면상의 위치를 구한 뒤에 추적을 하는 과정을 중점 적으로 서술하려 한다. 이러한 객체가 촬영된 영상에서 각 프레 임 마다 객체의 실제 위치는 상태(state)로 표현할 수 있고, 영상 평면상의 위치는 관측값(observation)으로 표현할 수 있는 잡음 이 섞인 동역학계로 나타낼 수 있다.
가우시안 잡음이 섞인 동역학계에서 타겟의 위치를 추정 및 추적하는 알고리즘은 대표적으로 칼만 필터 (Kalman filter)가 있다[1]. 칼만 필터는 크게 두 단계로 나뉘는데, 이전 추정값으 로부터 다음 추정값을 구하는 예측 단계 (prediction step)와 예 측된 다음 추정값을 현재 관측된 관측값으로 보정하기 위한 보 정 단계 (correction step)으로 나뉘며, 이 과정에서 칼만 이득 (Kalman gain)을 구하여 이용하게 된다. 칼만 필터는 상태 천이 식과 상태 관측식이 선형일 경우에 가장 최적화된 성능을 보이 며, 구현이 간단하다는 장점이 있다. 그러나 실제 세계의 동역 학계에서는 표현식이 비선형인 경우가 많으며, 이런 경우는 칼 만 필터를 적용할 수 없다. 따라서 이러한 비선형 표현식에 이 용할 수 있도록 하는 추적 알고리즘들이 개발되기 시작하였다.
대표적으로 다음 상태의 추정값 근처에서 테일러 급수 (taylor series)로 상태 천이식, 관측식을 선형으로 근사화한 후 일반적인 칼만 필터와 같은 방식을 사용하는 확장 칼만 필터 (EKF; extended Kalman filter)가 있다[2]. 확장 칼만 필터 또한 구현이 간단하고 비선형계에서 폭넓게 사용할 수 있으며, 적당 한 성능을 낼 수 있기 때문에 GPS를 비롯한 실제 시스템에서도 다수 사용되고 있다[3-4]. 하지만 표현식을 선형으로 근사화를 하는 점 때문에 추정값과 실제값의 오차가 발산하여 추적 성능 이 현저히 떨어지는 문제가 있다. 이어서 시그마 점 (sigma point)이라 불리는 표본을 이용하여 다음 상태에서의 공분산 행 렬 (covariance matrix)를 구하여 칼만 이득을 계산하여 관측값 으로부터 예측값을 보정하는 무향 칼만 필터 (UKF; unscented
Kalman filter)가 있다[5-6]. 무향 칼만 필터는 확장 칼만 필터에 비하여 오차가 발산하는 문제는 줄어들었지만, 여전히 가우시 안 잡음 환경에서만 이용할 수 있다는 단점이 남는다.
이러한 문제를 해결하기 위하여 수치해석적 방법 중 하나인 파티클 필터 (PF; particle filter)가 제안되었는데, 파티클이라 불 리는 다수의 상태변수들을 이용하여 가상의 상태천이를 일으 킨 후 해당 위치에서 현재의 관측값이 나올 확률을 계산하는 방 법이다[7-8]. 파티클 필터는 어떠한 비선형계에서나 이용할 수 있고 더 나아가 잡음 분포가 가우시안이 아닐 경우에도 이용할 수 있으나, 연산량이 많다는 단점이 있다.
최근에는 이차 칼만 필터 (QKF; quadratic Kalman filter)라는 새로운 추적 알고리즘이 발표되었는데, 이것은 표현식을 이차 식(quadratic form)으로 근사화하여 이용하는 것이다[9]. 이때 근사화된 이차식은 보통의 상태 벡터 (state vector)로 표현할 수 없으므로 상태벡터들 사이의 이차항을 추가한 증대된 상태 벡 터 (augmented state vector)로 바꾸어서 나타내게 된다. 이러한 이차 칼만 필터는 표현식이 비선형적일 때 선형으로 근사화하 는 것보다 더 정확히 근사화할 수 있으므로 추적 성능을 높일 수 있다.
본 논문에서는 최근에 발표된 이차 칼만 필터를 이용하여 영 상 기반의 객체 추적을 하는 것과 그 성능을 평가하는 것을 목 표로 한다. 이차 칼만 필터는 상당히 최근에 제안된 것으로 아 직 영상 기반의 객체 추적에 사용된 사례가 없어 이를 적용해보 고 그 성능을 평가하는 것에 상당한 의의가 있다. 또한 비선형 관계식을 선형으로 근사화하는 것 보다 이차식으로 근사화하 는 것이 더 좋은 성능을 보일 수 있다고 기대할 수 있다. 실험에 서는 실제 3차원 세계에서의 객체의 초기 위치를 가정하고, 객 체의 움직임을 모델링하여, 실제의 영상 평면에 투영되는 표현 식을 바탕으로 확장 칼만 필터, 무향 칼만 필터, 파티클 필터, 이 차 칼만 필터를 이용하여 추적해보는 것을 바탕으로 각 알고리 즘의 성능, 즉, 발산율과 평균제곱근오차 (RMSE; root mean square error)를 구하여 성능을 평가하였다.
Ⅱ. 시스템 모델
시스템 모델을 기술하기에 앞서, 우선 실제 3차원좌표계에 위치한 객체가 영상 평면 좌표계에 투영되는 원리를 살펴볼 필 요가 있다. 다음 그림 1은 핀홀 (pin hole) 카메라 모델을 나타낸 것이다[10]. 그림 1의 왼쪽을 보면, 실제의 위치 x에서 나온 광 선이 초점 (camera centre)으로 집중되며, 이때 영상평면 (image plane)에 있는 광학센서를 자극하게 되어 상이 맺히게 된다. 또 한 영상평면에 상이 맺히는 위치는 그림 1의 오른쪽과 같이 초 점 거리 f에 의해 결정되며, 간단한 비례식으로 나타낼 수 있다.
하지만 광학센서가 미세하게 틀어져 있거나, 렌즈의 반경이 비대칭을 이루는 등 제조 공정상에 생길 수 있는 문제로 인하여 영상 평면에 맺히는 상에 왜곡이 일어날 수 있는데, 이 경우 실
55 www.koni.or.kr 그림 1. 실제 3차원 좌표계의 위치가 영상 평면에 투영되는 원리
Fig. 1. The principle of mapping the real 3-D coordinate position into the image plane.
제 3차원 좌표계의 객체가 영상 평면 좌표계에 투영되는 수식 은 다음과 같이 표현할 수 있다.
(1)
여기서 C는 초점거리를 비롯한 카메라 자체의 변수를 나타내 며, R은 영상 평면과 실제 좌표계간의 각도에 의한 회전 변환 행렬, T는 영상 평면의 원점과 초점의 차이만큼을 나타내는 벡 터이다. 본 논문에서는 실험의 편의를 위하여 이상적인 상황을 가정하여 진행하려 한다. 이 경우 (1)은 다음과 같이 나타낼 수 있다.
(2)
(3)
(4)
(5) 이때, f는 초점 거리를 의미하며, 본 논문에서는 0.1로 설정해 두었다. 위 (3)와 같이 부가 잡음이 더해진 식이 관측식이 된다.
이 경우 관측식이 유리식 형태의 비선형식이 되는 것을 볼 수 있으며, 따라서 일반적인 선형 칼만 필터를 적용하는 것이 어려 운 것을 확인할 수 있다. 객체의 이동 모델은 다음과 같이 설정 하였다.
(6)
(7)
(8)
(9)
여기서 객체의 3차원 위치 기준을 객체의 하부 끝 부분으로 가정하였기 때문에 3차원 좌표의 y 좌표는 –10에서 변화하지 않는 것으로 가정하고, 이를 상태 천이식에도 표현하였다. 또한 객체의 3차원 좌표상에서의 속도 등으로 다음 상태의 위치를 어느 정도 알 수 있는 것을 상태 천이 벡터 를 더하는 것으로 반영하며, 이외의 불확정한 요소를 가우시안 잡음 벡터
을 더하는 것으로 설정하였다.
이러한 상황을 가정 해두고, 각각 EKF와 UKF, SIR (sequential importance resampling) PF (1000 particles), 그리고 QKF를 적용하여 객체의 실제 위치를 추적하였다.
Ⅲ. 알고리즘
3-1 기존 알고리즘
일반적으로, 가우시안 부가 잡음이 섞인 비선형 동역학계는 상태 천이식 X와 관측식 Z가 다음과 같이 표현된다.
(10)
(11)
(12)
(13)
(14)
(15) 여기서 EKF는 상태 천이식을 이용하여 다음 상태에서의 위 치를 예측한 후 그 주변에서 테일러 급수를 이용하여 상태 천이 식과 관측식을 선형으로 근사화한 후, 선형 칼만 필터와 같이 잡음들의 공분산 행렬을 이용하여 다음과 같이 칼만 이득을 계 산하고, 이 칼만 이득을 이용하여 관측값으로부터 예측값을 보 정한다. UKF는 Xt와 같은 분산과 평균을 가지며, X의 성분수와 같은 수의 시그마 점을 이용하여 천이식에 대입하여 칼만 이득 을 계산하는데 필요한 공분산 행렬을 구하여 칼만 이득을 계산, 마찬가지로 관측값으로 보정하는 방법을 사용한다. PF는 많은 수의 파티클이라 불리는 표본들을 상태 천이식에 대입하며, 이 때 다음 상태에 있을 확률이 높은 위치에 파티클들이 밀집하게 된다. 이후 모든 파티클들의 위치로부터 현재 상태의 관측값이 나올 확률을 계산하여 현재의 위치를 추정하게 된다.
3-2 이차 칼만 필터
http://dx.doi.org/10.12673/jant.2016.20.1.53 56 이차 칼만 필터는 상태 천이식은 선형이며, 관측식은 상태 벡터 성분들의 이차식과 일차식으로 구성된다. 또한 부가 잡음 은 가우시안으로 구성된다. 이차 칼만 필터의 핵심적인 아이디 어는 ‘이차식은 일차항들의 선형결합으로 나타낼 수 없지만, 이차항과 일차항들의 선형결합으로 나타낼 수 있다’ 이다. 즉, 이차식인 관측식을 표현하기 위하여 이차항이 포함된 증대된 상태 벡터를 구성하여 이 증대된 상태 벡터의 일차식으로 표현 하는 것이다. 상태 천이식과 관측식은 다음과 같다.
(16)
(17)
여기서 X는 n차원 상태 벡터이며, Y는 시간 t에서의 m차원 관 측 벡터이다. μ와 α는 평균 벡터로써, 알고 있다고 가정한다. Φ 와 B는 각각 n×n, m×m 행렬이며 ek는 k번째 성분만 1이며 나머 지 성분은 0인 단위 벡터, C(k)는 대칭 행렬로써, 관측값의 이차 성분을 만들어주는 역할을 한다. ε와 η는 각각 평균이 0이고 공 분산 행렬이 단위행렬인 가우시안 랜덤벡터이며, 여기에 Ω와 D를 이용하여 잡음의 공분산 성분을 만들어준다.
다음으로 증대된 상태 벡터 Z를 구성한다.
(18)
그리고 (18)을 바탕으로 (16)과 (17)을 Z에 관한 식으로 수정 한다. 그럼 다음과 같은 식들로 도출해낼 수 있다.
(19)
(20)
(21)
⊗ ⊗
⊗ (22)
여기서 , 라 하면,
⊗ (23)
이때, 은 n2차 단위행렬이며, 은 n차 자리교체 행렬 (commutation matrix)이고, ⊗는 두 행렬의 크로네커 곱 (kronecker product)을 의미한다. 또한
⋮
(24)
로 표현할 수 있다. 이때, 증대된 상태 벡터들에 대한 식으로 나 타내는 과정에서 가우시안으로 근사화하는 과정이 있다. 결과 적으로, 증대된 상태 벡터를 이용하여 다시 구성한 결과 상태 천이식과 관측식이 모두 선형이 되었으며, 이후 일반적인 선형 칼만 필터를 그대로 이용할 수 있다.
Ⅳ. 시뮬레이션 결과
실험에서는 1에서 50까지의 시간범위까지 객체를 추적하는 것을 1회로 설정하였으며 각각의 상태 잡음과 관측 잡음에서 1000회씩 실험한 결과를 평균내었다. RMSE는 실제 좌표의 x 와 z좌표 오차의 평균으로 아래의 (25)로 계산하였다. 실제 좌 표의 y 좌표는 변화가 없다고 가정하였으므로 추정 오차에서 제외할 수 있기 때문이다.
(25)
(26)
(27) 발산율 부분에서 발산은 RMSE가 100을 넘어가는, 실질적으 로 추적의 의미가 없는 시뮬레이션은 횟수를 따로 기록하여 발 산율계산에 이용하였다. 또한 연산시간은 i7-902 프로세서, 4GB RAM을 탑재한 windows 7 시스템에서 MATLAB을 이용 해 진행한 1회 시뮬레이션동안의 소요시간을 기준으로 하며, 실험 결과는 표1-3에 첨부해 두었다.
표1.
=1,
=0.1 일 때의 추적 결과 Table 1. Tracking result in
=1,
=0.1.EKF UKF PF QKF
divergence
rate 0.0110 0.0020 0 0.0050
RMSE 6.8064 4.8535 5.3985 4.8209
표 2.
=2,
=0.5 일 때의 추적 결과 Table 2. Tracking result in
=2,
=0.5.EKF UKF PF QKF
divergence
rate 0.0200 0.0090 0 0.0120
RMSE 11.7401 10.8353 13.1173 10.2904
표 3. 1 회 시뮬레이션 동안의 소요시간
Table 3. Processing time for 1 time simulation.
EKF UKF PF QKF
time (s) 0.085 0.087 1.375 0.106
57 www.koni.or.kr 실험 결과를 살펴보면 EKF는 연산 시간이 0.085초로 가장
짧지만 결과가 발산하는 비율이 잡음이 비교적 작은 상황에서 는 1.1%, 잡음이 큰 상황에서는 2%로 안정적인 성능을 내기 힘 들며, RMSE 값도 각각 6.8064, 11.7401로 비교적 크게 나오는 것을 볼 수 있다. UKF는 연산시간이 0.087초로, EKF와 거의 같 은 속도이며, 발산률이 각각 0.2%, 0.9%로 안정적이지만 RMSE값이 4.8535, 10.8353으로 QKF에 비해 약간 크게 나오는 것을 볼 수 있다. QKF는 연산시간이 0.106초로, UKF에 비해 연 산시간이 약간 더 걸리고 발산율은 0.5%, 1.2%로 약간 높지만, RMSE값은 각각 4.8029, 10.2904로 상당히 낮게 나오는 것을 확 인할 수 있었다. PF의 경우는 발산하는 경우가 없이 아주 안정 적이지만 연산시간이 1.375 초로 아주 오래 걸리고 RMSE값이 5.3985, 13.1173로 상당히 큰 것을 볼 수 있었다.
Ⅴ. 결 론
본 논문에서는 최근에 새로 제안된 이차 칼만 필터를 영상 기반의 객체의 실제 위치 추적에 적용해보아 성능을 평가하며,
그림 2. 확장 칼만 필터를 이용한 추적에서 발산하는 경우 Fig. 2. Divergence case of tracking using EKF.
그림 3. 이차 칼만 필터를 이용한 추적에서 적절히 찾는 경우 Fig. 3. Proper case of tracking using QKF.
기존의 대표적인 추적 알고리즘과 비교해보았다. 이차 칼만 필 터는 수식을 이차식으로 근사화하기 때문에 선형으로 근사화 하는 확장 칼만 필터보다 좋은 성능을 보이며, 무향 칼만 필터 에 대해서도 상대적으로 실용적인 성능을 보이는 것을 표 1-3 을 통해 확인할 수 있다.
확장 칼만 필터는 비선형 역학계에서 현재까지도 실용적으 로 사용되고 있는 칼만 필터로써, 구현이 간단하지만 결과가 발 산하는 경우는 그림 2와 같이 아예 추적 성능을 기대할 수 없다.
이차 칼만 필터의 경우는 추적 시 발산할 확률이 무향 칼만 필 터에 근접할 정도로 안정적이며 그림 3과 같이 추정 값과 실제 값의 차이가 어느 정도 벌어져도 발산하지 않고 곧 실제의 경로 를 잘 추적할 수 있으며, 또한 발산하지 않을 경우의 RMSE 값 이 더 작은 우수한 성능을 보인다.
지금까지는 실험의 편의를 위하여 이상적인 상황을 가정하 여 진행하였지만, 향후 보다 실제적인 성능을 얻기 위하여 실제 의 카메라 모델에 가까운 상황을 가정하여 연구를 지속할 계획 이다.
감사의 글
본 연구는 2015년도 정부(교육부)의 재원으로 한국연구재단 기본연구지원사업(과제번호: NRF-2015R1D1A1A01060234)의 지원을 받아 수행되었습니다.
참고 문헌
[1] R. E. Kalman, “A new approach to linear filtering and prediction problems,” Transactions of the ASME – Journal of Basic Engineering, Series D, No. 82, pp. 35-45, 1960.
[2] H. W. Sorenson, Kalman Filtering: Theory and Application, 1st ed. New York, NY: IEEE Press, 1985.
[3] S. Rezaei, “Kalman filter-based integration of DGPS and vehicle sensors for localization,” IEEE Transactions on Control Systems Technology, Vol. 15, No. 6, pp. 1080-1088, 2007.
[4] J. E. Guivant and E. M. Nebot, “Optimization of the simultaneous localization and map-building algorithm for real-time implementation,” IEEE Transactions on Robotics and Automation, Vol. 17. No.3, pp. 242-257, 2001.
[5] S. J. Julier and J. K. Uhlmann, “A new extension of the kalman filter to nonlinear systems,” in AeroSense'97 International Society for Optics and Photonics, Orlando: FL pp. 182-193, 1997.
[6] S. J. Julier, J. K. Uhlmann, and H. F. Durrant-Whyte, “A new method for the nonlinear transformation of means and covariances in filters and estimators,” IEEE Transactions on
http://dx.doi.org/10.12673/jant.2016.20.1.53 58 Automatic Control, Vol. 45, No. 3, pp. 477-482, 2000.
[7] M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp,
“A tutorial on particle filters for online nonlinear /non-gaussian bayesian tracking,” IEEE Transactions on Signal Processing, Vol. 2, No. 50, pp. 174-188, 2002.
[8] F. Gustafsson, F. Gunnarsson, N. Bergman, U. Forssell, J.
Jansson, R. Karlsson, and P. J. Nordlund, “Particle filters for positioning, navigation, and tracking,” IEEE Transactions
on Signal Processing, Vol. 50, No. 2, pp.425-437, 2002.
[9] A. Monfort, J. P. Renne, and G. Roussellet, “A quadratic Kalman filter,” Journal of Econometrics, Vol. 1, No. 187, pp. 43-56, 2015.
[10] R. Hartley and A. Zisserman, Camera Models, in Multiple View Geometry in Computer Vision. 2nd ed. Cambridge, UK: Cambridge University Press, ch. 6, pp. 153-177, 2003.
박 선 배 (Sun-Bae Park)
2015년 2월 : 홍익대학교 전자전기공학부 (공학사)
2015년 3월 ~ 현재 : 홍익대학교 대학원 전자정보통신공학과 석사과정
※관심분야 : 신호처리, 패턴인식, 영상처리 및 필터링 이론
유 도 식 (Do-Sik Yoo)
2002년 2월 : 미시간대학교 전자컴퓨터공학과 (공학박사) 2006년 9월 ~ 2011년 3월 : 홍익대학교 전자전기공학부 조교수 2011년 4월 ~ 현재 : 홍익대학교 전자전기공학부 부교수
※관심분야 : 통신 및 신호처리, 정보이론, 어레이신호처리, 영상처리 및 필터링, 신호처리, 변환광학 등
