快速滤波器近似已经研究了很长时间，特别是用于实现 IIR 滤波器，如高斯及其导数。您可能希望使用积分图像、面积求和表、 框过滤器、递归过滤等关键字重用这些概念。您可以从最近的评论开始：

• 高斯卷积算法综述，2013

并挖掘其他被引用的论文。

我正在考虑将脉冲响应近似为盒子的总和，在其他盒子之上。下一个可能很有趣“我们提出了一种通过箱形滤波器自动逼近任意二维滤波器的方法”

• 用箱形过滤器逼近图像过滤器，2011
• 扩展盒滤波高斯卷积的理论基础
• 用于快速线性滤波的 Sum-box 技术, 2002
• Boxlets：一种用于信号处理和神经网络的快速卷积算法，1998
• 有一些八度代码

我不确定您是否可以获得很多操作，至少对于可分离过滤器而言。

免责声明：
我是“R”的新手，所以我不知道稀疏的 FFT 库（SE、MIT、Berk）。这东西已经出版了~2年。如果它不存在，我会感到惊讶 - 如果它不存在，它应该并且将是对语言的有价值的补充。如果我有很高的积极性（目前不是），我会自己做。

问题是：
您想要非常快速地将一个大概是零填充的 3x3 到 11x11 矩阵与一个 200x200 到 1000x1000 矩阵进行卷积。

免责声明：
对不起，我对这方面的最新技术并不“时髦”。

我在上面的评论：
人们可能会使用压缩感知非常稀疏的狄利克雷样本云的感觉的想法。我想知道是否有一种每次采样的方法，一旦结果变化低于阈值就可以停止。那可能很快。

我所说的来自稀疏 Dirichlet 样本的压缩感知的意思是：
在大图上均匀随机地采样单个像素，并一次一个地添加到您的卷积结果中。

假设您正在屏幕图像中寻找“pac-man”。

这里是吃豆人

这是游戏画面：

如何使用卷积在图像中找到“吃豆人”？

这是rev0代码：

library(png)             #image load
library(pracma)          #matlab like matrix utils
library(microbenchmark)  #for very tight timing
library(spatstat)        #for gaussian blur

#raw data
im1 <- readPNG(source = "./data/pacman1.png",native=F) #pac man
im2 <- readPNG(source = "./data/pac_game.png")         #game board

#convert to grayscale (aka 2d matrix)
im1.g <- rot90(0.2126*im1[,,1] + 0.7152*im1[,,2] + 0.0722*im1[,,3],k=-1)
im2.g <- rot90(0.2126*im2[,,1] + 0.7152*im2[,,2] + 0.0722*im2[,,3],k=-1)

#normalize
im1.g <- im1.g/max(im1.g)
im2.g <- im2.g/max(im2.g)

#housekeeping on original 
rm(im1,im2)

# #check images
# image(im1.g,col = gray.colors(256))
# image(im2.g,col = gray.colors(256))

#classic method for image registration using convolution

#make low intensity values negative, 
# (improves curvature for subpixel approaches.)
im1.g <- im1.g - 0.1
im2.g <- im2.g - 0.1

#    zero pad the smaller
im1b <- 0 * im2.g
temp <- size(im1.g)

im1b[1:temp[1],1:temp[2]] <- im1.g

#convolute
fim1 <- fft(im1b)
fim2 <- fft(im2.g)
im12 <- Re(fft(fim1*fim2,inverse=T))

#ground negatives
im12[which(im12<0)] <- 0

#scale to height
im12 <- im12/max(im12)

#plot the result
image(im12, col = terrain.colors(256), new = TRUE)

drape.plot(1:nrow(im12), 1:ncol(im12), (im12), border = NA, theta = 25, phi = 55, )

生成的二维图像是：

悬垂图是：

虽然我并不完全喜欢正在发生的事情，但我有理由相信，最高的 6 个山峰之一发生在实际的“packman”身上。就个人而言，我更喜欢使用带有高斯模糊的边缘，这样我就不会将“Speedy”与 Pac-Man 混淆，但您关心的是计算速度，而不一定是注册。

所以我可以将“卷积”部分包含在基准测试中并获得计算时间

# benchmark convolute
mybench <- microbenchmark({
                           fim1 <- fft(im1b);
                           fim2 <- fft(im2.g);
                           im12 <- Re(fft(fim1*fim2,inverse=T));}, 
                          times=100)
#display value
print(mybench)

显示的结果是：

Unit: milliseconds
...
     min       lq     mean   median       uq      max neval
 9.33394 9.665923 10.00031 9.816518 9.940719 14.81459   100

现在我们的图像中有 64512 个像素。对于更大的图像，我们可能有数百万像素。在那里执行卷积可能非常昂贵。

让我们均匀地随机选择 10% 的像素，并使用稀疏 fft 变换对它们执行卷积。

#make empty
im2b <- matrix(0, nrow = nrow(im2.g), ncol = ncol(im2.g))

#uniformly randomly sample 10% of pixels
idx2b <- sample(x = 1:length(im2.g), size = floor(length(im2.g)/10),replace = FALSE)
im2b[idx2b] <- im2.g[idx2b]

fim1 <- fft(im1b);
fim2 <- fft(im2b);
im12 <- Re(fft(fim1 * fim2, inverse = T));

只有 10% 的像素，卷积的配准特性实际上得到了改善。

即使删除了大部分数据，真实位置在卷积中仍保持其高值。

--> INSERT UPDATED BENCHMARK from SPARSE FFT HERE <-- 注意：以下是正在进行的工作

我们可以将子采样“im2.g”的每个像素视为自己的图像，其总和构成完整背景。

然后我们寻找的是一种进行连续卷积的方法。第一种方法可能更贵，但是我们想找到一种方法让它更便宜。我象征性地知道我们可以将其视为狄拉克三角洲。正向变换将非常便宜。我知道空间紧方差函数在波数上有很大的变化。