Implement summed area table integration trick

[sauln]

See https://en.wikipedia.org/wiki/Summed-area_table

[rannbaron]

Do you just want a class that takes an array, computes the summed area table, and has a function sum(x1,y1,x2,y2) that returns the sum with those opposite corners?

[sauln]

@ctralie might have a better idea of how to go about doing this as he introduced me to the trick. I imagine the implementation would replace this code:

persim/persim/persim.py

Lines 110 to 120 in 0978c7d

	# Implement this as a `summed-area table` - it'll be way faster
	spread = self.spread if self.spread else dx
	for point in landscape:
	x_smooth = norm.cdf(xs_upper, point[0], spread) - norm.cdf(
	xs_lower, point[0], spread
	)
	y_smooth = norm.cdf(ys_upper, point[1], spread) - norm.cdf(
	ys_lower, point[1], spread
	)
	img += np.outer(x_smooth, y_smooth) * weighting(point)
	img = img.T[::-1]

Where it is object oriented, a function, or inlined is up to the implementer. Hopefully whatever is easiest.

[rannbaron]

Well, if it helps, here's a quick class that implements the basic algorithm.

class SummedAreaTable:

    def __init__(self,img):
        self.img = img
        self.table = np.zeros_like(self.img)
        rows,cols = self.img.shape
        
        # First row
        self.table[0] = np.cumsum(self.img[0])            
        # First column
        self.table[1:,0] = np.cumsum(self.img[:,0])[1:]
        
        for row in range(1,rows):
            for col in range(1,cols):
                self.table[row,col] = self.img[row,col] + self.table[row,col-1] + self.table[row-1,col] - self.table[row-1,col-1]
                
    def tablesum(self,x1,y1,x2,y2):
        return self.table[x2,y2] + self.table[x1,y1] - self.table[x1,y2] - self.table[x2,y1] 

[ctralie]

Thanks Rann. I'm just going to copy in something inline like what I've done here:
https://github.com/scikit-tda/ripser.py/blob/bottleneck/DGMTools.py#L311