[SS] Cross Correlation

입력으로 주어진 두 개의 함수(or signal)의 상관관계(correlation, 또는 similarity 유사성)을 나타내는 함수(or signal)를 반환하는 연산.

Cross correlation (흔히 correlation으로도 불림)의 수식은 다음과 같음 (1D cross-correlation)

$$ x(t)*y(t)= \int_T x(\tau)y(\tau+t) d\tau $$

• $*$를 cross correlation의 연산자 기호로 사용했으나 $\otimes$이 쓰이기도 하는등, 표준 기호가 없음을 주의.
• convolution과 달리 입력 중 한 function에 대한 반전이 이루어지지 않음.
• commutative하지 않음 (convolution과의 차이점 중 하나)

수식의 특성이라던지, 유사한지를 나타내는 상관관계를 결과로 나타내서 sliding inner product라고도 불림.

(inner product의 개념상, vector가 방향이 같은(유사한) 경우 높은 값을 가지는 점이나 수식상 비슷한 점때문에 sliding inner product라고 불리기도 하나, 빈번하진 않음)

---

Convolution과 비교

특정 impulse repsonse를 가지고 있는 Linear Shift Invariant System의 zero-state response를 구하는데 사용되는 convolution과 매우 비슷한 수식을 가지고 있으나, 사용되는 목적이 다름.

• 특정 filter (=point spread function, kernel, impulse response) 처리가 된 입력의 결과를 구하는데 사용됨.

1D convolution의 수식은 다음과 같음.

$$ x(t)\otimes h(t)=\int_T x(\tau)h(\color{red}{-}\tau+t) d\tau$$

• $\otimes$를 convolution의 연산자 기호로 사용했으나 $*$이 쓰이기도 하는등, 표준 기호가 없음을 주의.
• cross correlation의 경우와 달리 한 function이 reflection(반전)이 이루어진 부분을 주의할 것.

다음 동영상은 Cross correlation과 convolution의 차이점을 잘 보여준다.

2D에서의 비교

Cross correlaton 연산. f와 w의 correlation의 결과를 보여줌.

padding은 위아래, 좌우로 1씩 처리함. (kernel의 사이즈가 $3\times3$이므로) : 만약 $5\times 5$라면 결과가 같은 사이즈가 나오게 하기 위해서 위아래, 좌우로 2씩 padding이 필요함. : zero padding을 수행.

stride (kernel이 이동하는 정도)는 1씩 이루어짐.

convolution의 결과: kernel이 좌우상하로 flip됨. (reflection연산)

위에서 보이듯이 두 연산은 사용목적과 구현 모두 차이가 있는 다른 연산임.

• 하지만 impulse response가 대칭인 경우, convolution의 결과는 cross correlation과 차이가 전혀 없기때문에 많은 Deep Learning Library에서 convolution구현은 사실상 cross correlation인 경우가 많음.
  • 구현은 cross correlation이라면, 입력 중 하나를 좌우상하 flip시킬 경우, convolution이 구해진다.
• 이는 image에 적용되는 convolution의 impulse response(point spread function, kernel, mask window등으로도 불림)가 상하좌우 대칭인 경우가 많기 때문이기도 함.

Note that most deep learning frameworks (including TensorFlow) implement cross-correlation but refer to it as convolution, which is a common convention in the deep learning field.

 

References

https://towardsdatascience.com/convolution-vs-correlation-af868b6b4fb5

Convolution Vs Correlation

https://www.tutorialspoint.com/signals_and_systems/convolution_and_correlation.htm

Convolution and Correlation