cross-correlation을 사용한 신호 상관 관계 테스트 및 source code

본 글은 신호처리에서 신호들의 상관 관계를 파악하는 Cross-correlation에 대해 코드로 구현해 보고 테스트하는 내용을 싣고 있다.

신호처리에서 두 신호가 얼마나 비슷한 지를 측정하는 도구로 cross-correlation을 사용한고 한다.

예를 들어, 특정 패턴의 신호를 찾거나 혹은 이미지 처리에서 특정 패턴의 이미지를 찾을 때도 사용된다고 한다.

위키피디아의 Cross-correlation 페이지를 참조하였으며, 신호를 정규화 하여 사용하는 zero-normalized cross-correlation(ZNCC)을 구현하였다. 외부 환경 요인 등으로 신호 전체의 level등이 커지는 등의 영향을 받으면, 정상적으로 신호의 상관 관계를 파악하기 어렵고, 이를 위해 신호를 정규화 하여 사용한다고 한다. 상관 관계 파악에 사용되는 템플릿 신호와 샘플 신호 모두 정규화 과정을 수행하도록 했다.

ZNCC의 공식은 아래와 같다. 아래 공식은 x,y 좌표를 가진 2차원 이미지에서 사용되는 공식이고, 구현과 테스트는 1차원 신호 환경에 맞게 하였다.

소스 코드

class CCrossCorrelation

{

public:

CCrossCorrelation()

{

m_bUseNormal = TRUE;

m_nTemplateSignalLen = 0;

m_pNormalizedTemplateSignal = NULL;

m_pNormalizedSignal = NULL;

}

~CCrossCorrelation()

{

m_nTemplateSignalLen = 0;

safe_free(m_pNormalizedSignal);

safe_free(m_pNormalizedTemplateSignal);

}

int SetTemplateSignal(double *pTemplateSignal, int nlen, BOOL bUseNormal)

{

if (!pTemplateSignal || !nlen) return -1;

safe_free(m_pNormalizedSignal);

safe_free(m_pNormalizedTemplateSignal);

m_nTemplateSignalLen = nlen;

m_pNormalizedSignal = (double*)malloc(sizeof(double)*m_nTemplateSignalLen);

m_pNormalizedTemplateSignal = (double*)malloc(sizeof(double)*m_nTemplateSignalLen);

if (!m_pNormalizedSignal || !m_pNormalizedTemplateSignal)

{

m_nTemplateSignalLen = 0;

safe_free(m_pNormalizedSignal);

safe_free(m_pNormalizedTemplateSignal);

return -1;

}

memset(m_pNormalizedSignal, 0, sizeof(double)*m_nTemplateSignalLen);

memset(m_pNormalizedTemplateSignal, 0, sizeof(double)*m_nTemplateSignalLen);

m_bUseNormal = bUseNormal;

normalize(pTemplateSignal, m_pNormalizedTemplateSignal, m_nTemplateSignalLen);

return 0;

}

int DoCrossCorrelation(double *pSignal, double *pOut, int nLen)

{

int i = 0;

if (!pSignal || !pOut || !m_pNormalizedSignal || !m_pNormalizedTemplateSignal)

return 0;

memset(pOut, 0, sizeof(double)*nLen);

i = 0;

while (i < nLen - m_nTemplateSignalLen)

{

normalize(&pSignal[i], m_pNormalizedSignal, m_nTemplateSignalLen);

double correl_val = cal_crosscorrelation(m_pNormalizedTemplateSignal, 

m_pNormalizedSignal, m_nTemplateSignalLen);

pOut[i] = correl_val;

i++;

}

return nLen;

}

private:

BOOL m_bUseNormal;

int m_nTemplateSignalLen;

double *m_pNormalizedTemplateSignal;

double *m_pNormalizedSignal;

double cal_crosscorrelation(double *f, double *g, int nlen)

{

int i = 0;

double dval = 0;

while (i < nlen)

{

dval += (f[i] * g[i]);

i++;

}

if (m_bUseNormal) return dval / nlen;

return dval;

}

double normalize(double* pIn, double* pOut, int nSize)

{

int i = 0;

double sum = 0;

double square_sum = 0;

double mean = 0;

double stdv = 0;

if (pIn == NULL || pOut == NULL)

return 0;

if (!m_bUseNormal)

{

memcpy(pOut, pIn, sizeof(double)*nSize);

return 1;

}

while (i < nSize)

{

sum += pIn[i];

square_sum += (pIn[i] * pIn[i]);

i++;

}

mean = sum / nSize;

stdv = sqrt((square_sum / nSize) - (mean*mean));

i = 0;

if (stdv)

{

while (i<nSize)

{

pOut[i] = (pIn[i] - mean) / stdv;

i++;

}

}

else

{

while (i<nSize)

{

pOut[i] = (pIn[i] - mean);

i++;

}

}

return 1;

}

};

사용법은 아래와 같다.

double TemplateSignal[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 0 };

double Signal[70] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

double Correlation[70] = { 0, };

CCrossCorrelation xcorrel;

xcorrel.SetTemplateSignal(TemplateSignal, 10, TRUE);

xcorrel.DoCrossCorrelation(Signal, Correlation, 70);

cross-correlation 실험

위 코드를 사용하여 아래와 같이 테스트용 신호에서 템플릿 신호를 찾는 실험을 진행했다.

위와 두 경우의 테스트를 진행했다.

템플릿 신호와 유사도가 높은 신호 부근에서 cross-correlation값이 높아지는 것을 볼 수 있다. 

다만, 정규화를 사용하지 않은 cross-correlation은 가운데 박스 형태의 신호에서는 바로 옆의 템플릿 신호보다 큰 값이 나온다. 하지만, 정규화를 사용한 ZNCC의 경우에는 템플릿 신호와 같은 신호 위치에서 더 큰 값이 나오는 것을 볼 수 있다.