CHOU

[Image Processing] 칼만 필터(Kalman Filter)란 무엇인가? 본문

Tech/Technical Tips

[Image Processing] 칼만 필터(Kalman Filter)란 무엇인가?

chobabo 2009. 3. 15. 21:51

 칼만 필터는 R.E.Kalman (Kalman, Rudolph, Emil)이 1960년에 작성한 논문 "A New Approach To Linear Filtering and Prediction Problems" 에 기초하고 있습니다. 칼만 필터 알고리즘은 과거, 현재, 미래의 상태를 예측하며 명확하게 관측되어 지지 않은 자연계를 예측하는 모델시스템에도 활용되고 있습니다. 워낙에 유명한 필터 알고리즘이라 다양한 곳에서 활용되고 있지만 실제로 활용을 해 본적이 없어서 이번에 작업하는 프로젝트에 활용해 보고자 알아보았습니다.

 우선 인터넷에서 칼만필터를 검색하면 가장 많이 검색되는 예제를 통해서 칼만필터에 대해 알아보겠습니다. 담임 선생님이 자신의 반 시험평균을 알아보기 위한 방법을 생각해 보면 가장 저 떠오르는 건 전체 반 학생들의 점수를 더한 뒤 학생인원으로 나누어 알아보는 것 입니다. 하지만 성격이 급한 담임 선생님은 학생들이 1명씩 교탁위로 나와서 점수를 알려줄때 마다 현재까지 들은 학생들의 점수로 평균을 예측해 보려할때 아래와 같은 공식을 유도 할 수 있습니다.

X'(1) = X1
X'(2) = (X1 + X2)/2 = (X'(1) * 1 + X2)/2
X'(3) = (X1 + X2 + X3)/3 = (X'(2)*2 + X3)/3
X'(4) = (X1 + X2 + X3 + X4)/4 = (X'(3)*3 + X4)/4
....
X'(n) = (X1 + X2 + ......+ Xn)/n = (X'(n-1)*(n-1) + Xn)/n

 마지막에 유도된 공식처럼 n번째 평균을 구할때 현재 학생의 점수( Xn ), 현재 몇번째 학생인지( n ), 그리고 이전에 구해놓은 평균값( X'(n-1) )만 알고 있으면 쉽게 현재까지 점수를 바탕으로 평균을 구할 수 있게 됩니다. 이런 기법을 "Recursive Data Processing" 이라고 하는데 이론이 처음 밝혀진 1960년대의 상황을 생각하면 쉽게 이해를 할 수 있습니다. 당시만 해도 컴퓨터 환경이 지금으로 따지면 걸음마 수준도 안되는 시기였기 때문에 자료의 저장, 처리가 매우 느려서 좀 더 빠르게 들어오는 자료를 그때 그떄마다 처리해 주려고 했던 거 같습니다.

 위에 유도된 공식은 매우 훌륭하기는 하지만 일반화 하기에는 무리가 있는데 데이터의 중요도를 무시하고 학생의 점수 데이터에 대한 가중치를 ( 1/n )으로 주었기 때문 입니다. 실제로 평균을 구하다 보면 시험이 100점 만점이라고 가정할 경우 0 ~100점까지 고루 점수가 분포되어 있는것이 아니라 특정 점수대에 분포가 되어 있는 경우가 많이 때문입니다. 이때 ( x ) 명의 학생이 같은 점수를 가지고 있다면 가중치를 ( x/n ) 으로 두어 계산해야 할 것입니다. 이와 같이 데이터가 가지고 있는 평균에 대한 중요도"경중률" 이라고 합니다. 

 "측량학에서 관측값의 경중률은 각 값이 가지고 있는 표준편차를 기준으로 정해지는데, 관측지에 대한 경중률은 표준편차 제곱에 반비례하게 됩니다. 따라서 표준편차가 크면 클수록 값의 경중률은 떨어지고 평균에 대한 기여도는 작아지게 됩니다."

 예를들어 아까 담임 선생님이 교실의 길이를 측정하라고 두명의 학생에게 이야기 했는데 한명의 학생은 줄자를 이용하여 10m를 측정했고, 다른 한명의 학생은 자신의 보폭을 이용하여 12m 라는 측정값을 얻고 담임에게 말씀드렸다. 그렇다면 담임 선생님은 (12 + 10) / 2 = 11m 라는 생각을 하기 보다는 줄자로 잰 학생의 값을 더 신뢰하고 단순히 11m가 교실의 길이라고는 믿지 않게 될 것이다. 그러면 이때 어떻게 값을 산출해야 할까? (이때, 표준편차는 줄자가 0.1m, 보행이 1.0m라고 가정한다.)

 Avg = (10 * (1.0)^2 + 12 * (0.1)^2) / ( (0.1^2) + (1.0^2) ) = 10.02m (10.198...나오는데 10.02 라고 적습니다.)

위의 식을 다시 일반화 해보면

X = (X1*(sd2)^2 + X2*(sd1)^2) / ((sd1)^2+(sd2)^2)
     = (X1*(sd1)^2 - X1*(sd1)^2 + X1*(sd2)^2 + X2*(sd1)^2) / ((sd1)^2+(sd2)^2)
    = X1 + (X2-X1)* [(sd1)^2 / ((sd1)^2+(sd2)^2)]

X : 상태변수 (state variables)
sd : 표준편차 (stanard deviation)

 이처럼, 시스템 출력값(X1)과 새로운 입력 값 (X2)을 이용하여 새로운 최적값 (Optimized State Variables)을 계산하는 "관측 생신 알고리즘(Measurement Update Algorithm)"의 스칼라 형태 입니다. 실제 논문에에서는 칼만 필터의 기본식은 행렬 or 벡터 형태로 기술되고 있습니다. 또한 새로운 최적값 X의 표준 편차는 아래와 같습니다.

(sd)^2 = [(sd1)^2 + (sd2)^2] / [(sd1)^2 * (sd2)^2] 

 이렇게 새로운 최적값과 표준편차를 알아 보았습니다. 여기서 다시 새로운 관측값을 추가적으로 측정을 하고 새로운 최적값을 구할때도 같은 방법을 쓰면 된다. 이때 이전 값은 X1, sd1이 되고 새로운 관측값은 X2, sd2가 된다.

Recursive Data Processing 을 통해 Optimal Value를 추적하는 것이 칼만 필터의 기본 개념 입니다.

우선 여기까지 이해했기 때문에 글을 올리고 좀 더 자세한 내용은 공부를 더 하고 올리겠습니다^^. 

 아래 첨부파일은 칼만필터를 C소스로 구현해 놓은 것 입니다. 적절한 데이터 값을 넣어서 측정해 보세요^^. 실제로 해보니 잘되네요. 바로 컴파일 하면 안되고 데이터 소스를 적절히 대입해 줘야하는거 아시죠?^^

참고문헌
1. http://blog.empas.com/icewater47/2747037

2. An Introduction to the Kalman Filter <Greg Weich & Gray Bishop> TR 95-041


3. http://www.programmersheaven.com/zone3/cat714/20687.htm (Kalman Filter C Source code)


4. http://www.aistudy.com/control/kalman_filter.htm (AI 에 관한 각종 정보를 모아놓은 사이트)

5. http://www.cs.unc.edu/~welch/kalman/

6. An Introduction to the Kalman Filter