Integral Image for Faster Image Processing
Recently, I was looking into computer vision related technologies. One of the interesting techniques is known as the "integral image" which can enable more advanced techniques, most notably the Viola-Jones object detection framework, which uses a series of simple, Haar-like features, which are rectangular areas with dark and light regions, to find areas that match patterns that correspond with the object you are trying to find.
And that's it! We can now apply this faster computation to a number of interesting problems. For a nice tutorial on this, you may want to check out the following.
To do this computation, you search an image by sliding an imaginary window with the pattern at multiple scales over the entire image, looking for differences between the dark and light areas of the pattern that meet a threshold that is determined by the training algorithm. Doing this can require many computations, so how can we speed this up? Let's frame the question this way: Starting with a gray scale image in which each pixel has a value from 0-255, how can we quickly compute the average color value in a sub-region of an image?
The conventional way would be to write a loop similar the following:
private static int computeSum(BufferedImage image, int regionX1, int regionY1, int regionX2, int regionY2) {
//Compute a sub-region of the image
int sum = 0;
Raster data = image.getData();
for (int x = regionX1; x <= regionX2; x++) {
for (int y = regionY1; y <= regionY2; y++) {
int value = data.getSample(y, x, 0);
sum = sum + value;
}
}
return sum;
}
But we can do better than this, especially if we'll need to compute multiple regions and not constantly recompute the sums. To create an integral image, we make a single pass over the entire image and for each pixel in the original image compute the sum of all the pixels to the left and above of this pixel and add it to the value of the original pixel. The code for that is below.
public class IntegralImage {
private int[][] integralImage = null;
public IntegralImage(BufferedImage image) {
int originalImageHeight = image.getHeight();
int originalImageWidth = image.getWidth();
integralImage = new int[originalImageHeight][originalImageWidth];
Raster originalPixels = image.getData();
int originalPixelValue = 0;
for (int row = 0; row < originalImageHeight; row++) {
for (int column = 0; column < originalImageWidth; column++) {
originalPixelValue = originalPixels.getSample(column, row, 0);
//For the leftmost pixel, just copy value from original
if (row == 0 && column == 0) {
integralImage[row][column] = originalPixelValue;
}
//For the first row, just add the value to the left of this pixel
else if (row == 0) {
integralImage[row][column] = originalPixelValue + integralImage[row][column - 1];
}
//For the first column, just add the value to the top of this pixel
else if (column == 0) {
integralImage[row][column] = originalPixelValue + integralImage[row - 1][column];
}
//For a pixel that has pixels to its left, above it, and to the left and above diagonally,
//add the left and above values and subtract the value to the left and above diagonally
else {
integralImage[row][column] = originalPixelValue + integralImage[row][column - 1] + integralImage[row - 1][column] - integralImage[row - 1][column - 1];
}
}
}
After this pass through the image, we can compute the sum of any region in constant time by doing the following:public int total(int x1, int y1, int x2, int y2) {
int a = x1 > 0 && y1 > 0 ? integralImage[x1-1][y1-1] : 0;
int b = x1 > 0 ? integralImage[x1-1][y2] : 0;
int c = y1 > 0 ? integralImage[x2][y1-1] : 0;
int d = integralImage[x2][y2];
return a + d - b - c;
}
0 TrackBacks
Listed below are links to blogs that reference this entry: Integral Image for Faster Image Processing.
TrackBack URL for this entry: http://www.nearinfinity.com/mt/mt-tb.cgi/1713
Leave a comment