r - R中求和面积表/积分图像的有效实现

Question

我正在尝试构建一个 summed area table or integral image给定一个图像矩阵。对于那些不知道它是什么的人，来自维基百科:

A summed area table (also known as an integral image) is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid

换句话说，它用于在恒定时间内对图像/矩阵中任何矩形区域的值进行求和。

我正在尝试在 R 中实现它。但是，我的代码似乎需要很长时间才能运行。

这是来自 this link 的伪代码. in是输入矩阵或图像和 intImg返回的是什么

对于 i=0 到 w 做
总和←0

对于 j=0 到 h 做
sum ← sum + in[i, j]

如果 i = 0 那么
intImg[i, j] ← sum
别的
intImg[i, j] ← intImg[i − 1, j] + 总和
万一
结束于
结束于


这是我的实现

w = ncol(im)
h = nrow(im)
intImg = c(NA)
长度(intImg)= w*h

for(i in 1:w){ #x
总和 = 0;
for(j in 1:h){ #y
ind = ((j-1)*w)+ (i-1) + 1 #index
总和 = 总和 + im[ind]
如果(我== 1){
intImg[ind] = 总和
}别的{
intImg[ind] = intImg[ind-1]+sum
}
}
}
intImg = 矩阵(intImg，h，w，byrow=T)

输入输出矩阵示例:



但是，在 480x640 上矩阵，这需要大约 4 秒。在论文中，他们将这些维度描述为毫秒级。

我在循环或索引中做了什么低效的事情吗？

我考虑过用 C++ 编写它并用 R 包装它，但我对 C++ 不是很熟悉。

谢谢

Answer 1

您可以尝试使用 apply (如果您预先分配内存，则不会比您的 for 循环快):

areaTable <- function(x) {
  return(apply(apply(x, 1, cumsum), 1, cumsum))
}

areaTable(m)
#      [,1] [,2] [,3] [,4]
# [1,]    4    5    7    9
# [2,]    4    9   12   17
# [3,]    7   13   16   25
# [4,]    9   16   22   33