Integral image extension to time domain.

integralVolume.py

# Integral Image + Time 

# Ke, Y., Sukthankar, R., & Hebert, M. (2005). Efficient Visual Event Detection 
#     Using Volumetric Features. Tenth IEEE International Conference on Computer
#     Vision ICCV05 Volume 1, 1, 166-173. 


def integral(cube, closest, farthest):
    """
    Compute the sum of pixels in a cube.

    @param cube: nd-array representing a cube of data.
    @param closest: (k,i,j) coordinate of a point closest to the origin.
    @param farthest: (k,i,j) coordinate of a point farthest from the origin.
    @return: the sum of all values in the rectangle defined by the closest and
        farthest points.
    """

    r0, c0, t0 = closest
    r1, c1, t1 = farthest

    # Compute the integral volume.
    I = cube.cumsum(2).cumsum(1).cumsum(0)

    cubeCoordinates = [
        (t0 - 1, r0 - 1, c0 - 1),  # d
        (t0 - 1, r0 - 1, c1),  # c
        (t0 - 1, r1, c0 - 1),  # h
        (t0 - 1, r1, c1),  # g
        (t1, r0 - 1, c0 - 1),  # b
        (t1, r0 - 1, c1),  # a
        (t1, r1, c0 - 1),  # f
        (t1, r1, c1),  # e
        ]

    # Used to avoid boundary wrap arounds.
    def safe_index(field, index):
        if index[0] < 0: return 0
        if index[1] < 0: return 0
        if index[2] < 0: return 0
        return field[index]
    
    # Extract the coordinate values.
    d, c, h, g, b, a, f, e = [safe_index(I,x) for x in cubeCoordinates]
    
    volume = e - a - f - g + b + c + h - d
    
    # compute the volume
    print '{e} - {a} - {f} - {g} + {b} + {c} + {h} - {d} = {volume}'.format(
        **locals()
        )
    
    return volume


# Form a cube of ones.
cube = np.ones((10,10,10))

# Assert that the sums are being computed properly.
assert integral(cube, (0, 0, 0), (1, 1, 1)) == cube[0:2, 0:2, 0:2].sum(), \
    "Sum should equal 8, in a 2x2x2 cube."

assert integral(cube, (1, 1, 1), (3, 3, 3)) == cube[1:4, 1:4, 1:4].sum(), \
    "Sum should equal 27, in a 3x3x3 cube."

assert integral(cube, (2, 2, 2), (7, 7, 7)) == cube[2:8, 2:8, 2:8].sum(), \
    "Sum should equal 216, in a 3x3x3 cube."

The "safe_index" thing is horrible - any suggestions?

I need to write some tests to be sure but I think the integrate function is suitable.

Is there some easy way to compute the intersection of the cube with the one defined by nearest and farthest? That seems to be what you're doing anyway. Then you have an array which I imagine would be easy to sum in C/Numpy rather than doing it in Python.

Also, your tests aren't exercising the case where safe_index is necessary (ie. negative indexes), and you're not considering the case where the points are greater than the cube's indexes.