The Savitzky–Golay method essentially performs a local polynomial regression (of degree k) on a series of values (of at least k+1 points which are treated as being equally spaced in the series) to determine the smoothed value for each point.
""

Savitzky–Golay 필터는 일정한 간격으로 주어진 데이터들이 있을 때(이들 데이터는 원래의 정보와 노이즈를 같이 포함한다), 각각의 점에서 주변의 점들을 가장 잘 피팅하는 k-차의 다항식을 최소자승법을 이용해서 찾아서 그 지점에서의 데이터 값을 결정하는 필터이다. 이 필터는 주어진 데이터에서의 극대나 극소, 또는 봉우리의 폭을 상대적으로 잘 보존한다.(주변 점들에 동등한 가중치를 주는 Moving Average Filter와 비교해 볼 수 있다).

간단한 예로, 2차의 다항식과 5개의 데이터 점

{(-2, d0), (-1, d1), (0, d2), (1, d3), (2, d4)}

을 이용해서 중앙에서의 값을 결정하는 방법을 살펴보자. 사용하려고 하는 다항식은

p[x] = a0 + a1*x + a2*x2

이다. 다항식의 계수들은 다항식의 값과 실제 데이터의 값과의 차이를 최소화시키는 것들로 잡아야 한다.. 즉, 최소자승의 원리를 적용하여서 구하면 된다. 계산된 다항식의 값과 실제 데이터 값 사이의 차의 제곱을 구하면:

L = |a0-2*a1+4*a2-d0|2+|a0 -a1+ a2-d1|2+|a0-d2|2+|a0+a1+a2-d3|2
                          
+|a0+2*a1+4*a2-d4|2

이 식의 a0, a1, a2에 대한 극값을 가질 조건은

5*a0 + 10*a2 = d0 + d1 + d2 + d3 + d4

10*a1 = -2d0– d1 + d3+ 2d4

10*a0 + 34*a2 = 4d0 + d1+ d3 + 4d4        

이 식을 만족시키는 a
0를 구하면, 필터의 출력값 (원도우 중앙에서 값)이 결정된다.

필터출력 = a0 = (-3*d0 + 12*d1 + 17*d2 + 12*d- 3*d4) / 35;

위에서 계수 a0, a1, a2를 결정하는 방정식은 행렬로 정리하면 아래의 식과 같이 표현할 수 있다.

""

좌변의 5행3열 행렬을 A, a = [a0, a1, a2]T, d = [d0, d1, d2, d3, d4]T로 놓으면, 이 행렬방정식은 A.a = d 형태로 쓸 수 있고, 양변에 AT를 곱해서 왼쪽을 대칭행렬로 바뀌면

(AT.A).a = AT.d

따라서 해는,

a = (AT.A)-1.(AT.d)

이 식은 임의의 k-차 다항식을 이용한 경우에도 사용할 수 있다. 이 경우에 행렬 (ATA) 는 (k+1)x(k+1)의 대칭행렬이 된다. 행렬 A는 다항식의 찻수와 피팅에 사용이 될 데이터의 구간의 크기가 주어지면 정해지므로,  윗 식에서 (AT.A)-1.AT의 첫행 (a0을 d로 표현하는 식의 계수들)을 구해서 프로그램상에서는 lookup table를 만들어서 사용할 수 있다. 아래표는 mathematica 를 이용해서 윈도우 크기가 7 (7개 점)인 경우 2차 다항식을 사용할 때 계수를 구하는 과정이다.

 

""

2차 다항식일 때, 같은 방식으로 다양한 윈도우 크기에 따른 계수를 구할 수 있다.
*크기(n)에 따른 필터값 결정계수 (중앙에 대해 좌우대칭이다);

n=5;  W[] = {-3, 12, 17, 12, -3};
n=7;  W[] = {-2, 3,  6, 7, 6, 3. -2};
n=9;  W[] = {-21, 14. 39, 54, 59, 54, 39, 14, -21};
n=11; W[] = {-36, 9, 44, 69, 84, 89, 84, 69, 44, 9, -33};

필터출력 =   ∑ W[i]d[i] / ∑ W[i]

'Image Recognition' 카테고리의 다른 글

Adaboost  (0) 2010.12.28
Blur Detection  (0) 2010.05.25
Savitzky-Golay smoothing filter  (2) 2010.03.24
Watershed Algorithm Code  (0) 2010.03.19
Retinex 알고리즘  (11) 2010.02.03
Gaussian Mixture Model & KMeans  (4) 2010.01.30
Posted by helloktk

댓글을 달아 주세요

  1. 꾸왁꾸왁 2010.12.07 15:54 신고  댓글주소  수정/삭제  댓글쓰기

    정말 큰 도움이 되었습니다. 감사합니다.
    다음에 또 필요한 사람을 위해
    L=~~~에서 마지막 항의 a2-->a1으로 바꿔야 할 것 같네요.
    감사합니다~~~