关于可分离与非可分离滤波器卷积计算成本的澄清问询

先明确计算前提：我们统计的是乘法运算的次数（这是衡量卷积计算成本的常用方式，和你给出的非可分离滤波器成本M²·N²的统计逻辑一致），图像尺寸为M×M，可分离的N×N滤波器拆分为一个N维垂直列滤波器和一个N维水平行滤波器。

分步计算运算量 #

• 第一步：垂直卷积（列滤波器与原图像卷积）
  图像共有M列，每一列包含M个像素。对每一列的每个像素做卷积时，需要用N个滤波器权重分别和对应位置的像素相乘，也就是每个像素需要N次乘法。
  这一步的总运算量为：M（列数） × M（每列像素数） × N（单像素乘法次数） = M²·N

• 第二步：水平卷积（行滤波器与第一步结果卷积）
  经过垂直卷积后，输出的仍然是M×M尺寸的图像（默认采用same padding，保证输出尺寸和输入一致）。此时对每一行的每个像素做卷积，同样每个像素需要N次乘法。
  这一步的总运算量为：M（行数） × M（每行像素数） × N（单像素乘法次数） = M²·N

总运算量 #

将两步的运算量相加：M²·N + M²·N = 2·N·M²，这就是你预期的结果。

对比非可分离滤波器的M²·N²，可分离滤波器的计算成本优势会随着N的增大而愈发明显——比如当N=5时，非可分离需要25M²次乘法，而可分离仅需要10M²，运算量直接降到原来的40%。

内容的提问来源于stack exchange，提问作者Judy