[Python] How to accelerate the cross-correlation computation of two 2D matrices in Python?

I am using Python to compute the cross-correlation of two 2D matrices, and I have implemented three different methods. Below is my experimental code along with their execution times:

import numpy as np
from scipy.signal import fftconvolve

# Randomly generate 2D matrices
a = np.random.randn(64, 4200)
b = np.random.randn(64, 4200)

# Using np.correlate
def test_1(a, b):
return np.array([np.correlate(s_row, t_row, mode="full") for s_row, t_row in zip(a, b)])[:, len(a[0]) - 1:].sum(axis=0)

# Using scipy.signal.fftconvolve
def test_2(a, b):
return np.array([fftconvolve(s_row, t_row[::-1], mode="full") for s_row, t_row in zip(a, b)])[:, len(a[0]) - 1:].sum(axis=0)

# Using scipy.signal.fftconvolve but for 2D
def test_3(a, b):
return fftconvolve(a, np.fliplr(b), mode="full")[:, len(a[0]) - 1:].sum(axis=0)

# Performance testing
for i in range(100):
x = test_1(a, b) # 19.8 seconds
for i in range(100):
x = test_2(a, b) # 1.1 seconds
for i in range(100):
x = test_3(a, b) # 3.8 seconds


Even if I reverse b in advanced, the cost of time remains unaltered.

My computer configuration is:

Operating System: Windows 11

CPU: i7-12700F

Memory: 16GB

I have already used from concurrent.futures import ThreadPoolExecutor, as_completed to speed up the multiple loops. I am looking for further ways to accelerate this computation.

Are there any other algorithm optimization suggestions that could help reduce the computation time? Thank you.

Continue reading...