Scipy NDimage 关联：慢得令人难以忍受

Question

我运行代码使用 Python 3.3。目标是将 data_3d（一个 1000x1000x1000 布尔型 ndarray）与内核（一个 35x35x35 浮点型 ndarray）相关联。

然后我执行另一个相关性以对之前的结果求和。因此，我将另一个 1000x1000x1000 布尔型 ndarray 与 35x35x35 浮点型 ndarray 相关联——这与上一步完全相同。

这是我感到困惑的地方：第一个关联在 70 秒内完成；第二个（看似相同的）过程从未完成（即等了一个多小时...）。

我尝试减小第二个相关的大小（例如，与 5x5x5 数组相关），结果相同。

据推测，这不是内存问题；在第二个过程中内存稳定在 18 GB（但我仍然有 14 GB 可用...）。

怎么回事？

这是我的代码：

import numpy as np
from scipy import ndimage as im

A 部分：

t1 = time.time()
# Used to time the process`
# a is a np.ndarray of dtype = bool
a = im.correlate(data_3d, kernel) > threshold 
t2 = time.time()
print(t2 - t1) # About 70 seconds

B 部分：下一部分永远不会完成！

b = im.correlate(a, np.ones((35, 35, 35)))
t3 = time()`

编辑：我找到了解决方案。 A 部分的内核非常稀疏，而 B 部分的内核已完全填充。 Scipy 必须有一些幕后魔法来修改稀疏矩阵的过滤器大小...这使得 A = O(N^3) 和 B = O(N^3 * n^) 的时间复杂度3)，其中 N = 图像的一维大小，n = 内核的一维大小。

Answer 1

不是相关算子慢，而是你的问题很大

大小为 N 的 3D 数组与大小为 n 的核的直接相关（或卷积）涉及大致N**3*(2*n**3) 浮点运算。因此，对于最近的 CPU，每个内核 10 GFLOP，这个大小的问题至少需要 2.4 小时，即使不考虑内存复制开销。

其他因素也可以加快计算速度，例如多线程，以及是否使用稀疏内核。在后一种情况下，复杂性可以从 O(N**3*n**3) 降低到 O(N**3) ，这可以解释步骤 1 和步骤 2 之间执行时间的差异（正如问题作者所指出的）。

对于第 2 步，使用 scipy.signal.fftconvolve 的基于 FFT 的方法（需要翻转内核以执行互相关）可能会更快，特别是如果问题大小 N可以等于 2 的幂（例如 1024）。

Scipy NDimage 关联：慢得令人难以忍受

Scipy NDimage correlate: unbearably slow

python

memory

numpy

scipy

ndimage