R中有效区域表/积分图像的有效实现

Question

我试图在给定图像矩阵的情况下构造求和区域表或积分图像.对于那些不知道它是什么的人,来自维基百科:

求和面积表(也称为积分图像)是一种数据结构和算法,用于快速有效地生成网格矩形子集中的值之和

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

我试图在R中实现它.但是,我的代码似乎需要很长时间才能运行.

这是此链接的伪代码.in是输入矩阵或图像,intImg是什么返回

for i=0 to w do
   sum?0

   for j=0 to h do
      sum ? sum + in[i, j]

      if i = 0 then
         intImg[i, j] ? sum
      else
         intImg[i, j] ? intImg[i ? 1, j] + sum
      end if
   end for 
end for

这是我的实施

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

for(i in 1:w){ #x
  sum = 0;
  for(j in 1:h){ #y
    ind = ((j-1)*w)+ (i-1) + 1 #index
    sum = sum + im[ind]
    if(i == 1){
      intImg[ind] = sum
    }else{
      intImg[ind] = intImg[ind-1]+sum
    }
  }
}
intImg = matrix(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