Cross-Correlation

Properties of Fourier Transform

Cross-Correlation

$$R_{x,y}(t) \triangleq \int^{\infty}{\infty}x(\tau)y(\tau - t)d\tau = \int^{\infty}{\infty}x(t+\tau)y(\tau)d\tau$$

Conjugate and reversal

Conjugation and Reversal

$$\bar{x} \leftrightarrow \mathsf{flip}(\bar{X})\\ \mathsf{flip}(\bar{x}) \leftrightarrow \bar{X}$$

Convolution Theorem

$$\mathcal{F}[x(t)*y(t)] = X(jw)Y(jw) \\\mathcal{F}[x(t)y(t)] = X(jw)*Y(jw)$$

하지만 실제 사용시 차이가 있다.

Cross correlation with FFT and fftshift

: time domain에서의 cross-correlation은 linear(aperiodic) convolution이어서 다음과 같은 인덱스를 가지게 된다.

$$w=x⊗y=(w[−(N−1)],w[−(N−2)],…,w[−1],w[0],w[1],…,w[N−2],w[N−1]).$$

하지만 frequency domain에서의 multiplication은 cyclic(periodic, circular) convolution 이기에

$$\hat{w}=(w[0],w[1],…,w[N−1],w[−(N−1)],w[−(N−2)],…,w[−2],w[−1])$$

이 된다. 따라서 일반적으로 사용하는 인덱스로 변환하기 위해서 fftshift를 해주어야한다.

자세한 내용은 다음의 구현된 코드를 확인하라

Implementation

• python

kooBH/prac

• C++

kooBH/align