Question 2. Integral Images

In image processing, a frequent operation is to compute the average image value (intensity) or some other statistic over a rectangular sub-region of the image. The region of interest can be specified by 4 integer parameters: top, bottom, left and right. Not knowing the sub-region in advance, a naïve method would require O(n) time to compute this average, where n is the number of pixels in the image. One could speed this up by precomputing the average for all possible sub-regions: how much memory would this require?

Instead, we implement a class called IntegralImage, which will allow the average over an arbitrary rectangular sub-image to be computed in O(1) time, using only O(n) memory.

Images will be stored in 2D arrays. We will follow the convention that the first index of the array indicates the row number (vertical position) and the second index indicates the column number (horizontal position). Vertical position is indexed from the top down, and horizontal position is indexed from left to right. Thus image[0][0] is the top left pixel of the image.

You will complete two methods. The constructor method IntegralImage will accept an input integer image and will construct, in O(n) time, a new data structure using O(n) memory that will allow O(1) computation of sub-image averages. If the input array is not rectangular, IntegralImage will throw an InvalidImageException.

The query method meanSubImage(top, bottom, left, right) will return the average of all pixels in the subimage extending from top to bottom bounds vertically and left to right bounds horizontally, in O(1) time. The pixels lying at the bounds are included in this calculation. If any of these 4 parameters is outside the range of the image, a BoundaryViolationException will be thrown. Note that top <= bottom and left <= right. If not, a NullSubImageException is thrown.

For example, meanSubImage(3, 7, 2, 5) will calculate the average value of the 5 x 4 (h x w) image lying between rows 3 and 7 and columns 2 and 5.

Here is a test program testIntegralImage that provides a test case. You should, however, test your program using a broader range of test cases. Pay particular attention to boundary conditions.

All files are part of the package A1Q2, and should be downloaded to a directory of the same name. Note that you only need to submit file IntegralImage.java.