Effective implementation of the table of total area / integrated image in R

Question

I am trying to build a table of the total area or the whole image taking into account the image matrix. For those of you who don’t know what it is, from Wikipedia:

The summarized regions table (also known as the integrated image) is a data structure and algorithm for quickly and efficiently generating the sum of values ​​in a rectangular grid subset

In other words, it is used to sum the values ​​of any rectangular region in the image / matrix in constant time.

I am trying to implement this in R. However, my code seems to work too long.

Here is the pseudocode from this link . in is the input matrix or image, and intImg is what returned

  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

And here is my implementation

  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)

Example input and output matrix:

However, on a 480x640 matrix, this takes ~ 4 seconds. In the document, they describe it for the order of milliseconds for these measurements.

Am I doing something inefficient in my loops or indexing?

I thought about writing it in C ++ and wrapping it in R, but I'm not very familiar with C ++.

thanks

Answer 1

You can try using apply (no faster than your for-loops if you previously allocated memory):

 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