Return to Computer Vision Notebooks

Bi-dimensional Discrete Correlation

---

• Author: Diego Inácio
• GitHub: github.com/diegoinacio
• Notebook: 2D_discrete_correlation.ipynb

---

Naive implementation of bi-dimensional discrete correlation.

%matplotlib inline
# Visualization
import matplotlib as mpl
import matplotlib.pyplot as plt
import matplotlib.patches as patches

# Math and matrix operations
import numpy as np

# Image IO
import imageio

# Performance
from numba import jit, prange

# Utils
from _utils import *

import warnings
warnings.filterwarnings('ignore')

Cross-correlation

---

$$ \large \displaystyle (h \star x)[n_1, n_2]=\sum_{k_1=-\infty}^{\infty}\sum_{k_2=-\infty}^{\infty}h(k_1, k_2)x(n_1+k_1,n_2+k_2) $$

M, N = 7, 7
x = np.zeros((M, N))
x[M//2, N//2] = 1
h = np.arange(9).reshape(3, 3) + 1

@jit(nopython=True, parallel=True)
def xcorrelate(x, h):
    xh, xw = x.shape
    hh, hw = h.shape
    # Kernel radius
    rh, rw = np.array(h.shape)//2
    # Init output
    output = np.zeros(x.shape)
    for n1 in prange(rh, xh-rh):
        for n2 in prange(rw, xw-rw):
            value = 0
            for k1_ in prange(hh):
                for k2_ in prange(hw):
                    k1 = rh - k1_
                    k2 = rw - k2_
                    value += h[k1_, k2_]*x[n1 + k1, n2 + k2]
            output[n1, n2] = value
    return output

print(x, end=' input\n\n')
print(h, end=' kernel\n\n')
print(xcorrelate(x, h), end=' cross correlation\n\n')

[[0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]] input

[[1 2 3]
 [4 5 6]
 [7 8 9]] kernel

[[0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 2. 3. 0. 0.]
 [0. 0. 4. 5. 6. 0. 0.]
 [0. 0. 7. 8. 9. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0.]] cross correlation