图像处理之积分图算法

图像处理之积分图算法

一：积分图来源与发展

积分图像是Crow在1984年首次提出，是为了在多尺度透视投影中提高渲染速度。随后这种技术被应用到基于NCC的快速匹配、对象检测和SURF变换中、基于统计学的快速滤波器等方面。积分图像是一种在图像中快速计算矩形区域和的方法，这种算法主要优点是一旦积分图像首先被计算出来我们可以计算图像中任意大小矩形区域的和而且是在常量时间内。这样在图像模糊、边缘提取、对象检测的时候极大降低计算量、提高计算速度。第一个应用积分图像技术的应用是在Viola-Jones的对象检测框架中出现。

二：积分图像概念

在积分图像(Integral Image - ii)上任意位置(x, y)处的ii(x, y)表示该点左上角所有像素之和，表示如下：

从给定图像I从上到下、从左到右计算得到和的积分图像公式如下：

其中(x<0 || y<0) 时ii(x,y)=0, i(x,y)=0

得到积分图像之后，图像中任意矩形区域和通过如下公式计算：

三：代码实现：

积分图像算法的Java代码实现如下：

package com.gloomyfish.ii.demo;

public class IntIntegralImage extends AbstractByteProcessor {
	// sum index tables
	private int[] sum;
	private int[] squaresum;
	// image
	private byte[] image;
	private int width;
	private int height;

	public byte[] getImage() {
		return image;
	}

	public void setImage(byte[] image) {
		this.image = image;
	}
	
	public int getBlockSum(int x, int y, int m, int n) {
		int swx = x + n/2;
		int swy = y + m/2;
		int nex = x-n/2-1;
		int ney = y-m/2-1;
		int sum1, sum2, sum3, sum4;
		if(swx >= width) {
			swx = width - 1;
		}
		if(swy >= height) {
			swy = height - 1;
		}
		if(nex < 0) {
			nex = 0;
		}
		if(ney < 0) {
			ney = 0;
		}
		sum1 = sum[ney*width+nex];
		sum4 = sum[swy*width+swx];
		sum2 = sum[swy*width+nex];
		sum3 = sum[ney*width+swx];
		return ((sum1 + sum4) - sum2 - sum3);
	}
	
	public int getBlockSquareSum(int x, int y, int m, int n) {		
		int swx = x + n/2;
		int swy = y + m/2;
		int nex = x-n/2-1;
		int ney = y-m/2-1;
		int sum1, sum2, sum3, sum4;
		if(swx >= width) {
			swx = width - 1;
		}
		if(swy >= height) {
			swy = height - 1;
		}
		if(nex < 0) {
			nex = 0;
		}
		if(ney < 0) {
			ney = 0;
		}
		sum1 = squaresum[ney*width+nex];
		sum4 = squaresum[swy*width+swx];
		sum2 = squaresum[swy*width+nex];
		sum3 = squaresum[ney*width+swx];
		return ((sum1 + sum4) - sum2 - sum3);
	}

	@Override
	public void process(int width, int height) {
		this.width = width;
		this.height = height;
		sum = new int[width*height];
		squaresum = new int[width*height];
		// rows
		int p1=0, p2=0, p3=0, p4;
		int offset = 0, uprow=0, leftcol=0;
		int s=0;
		for(int row=0; row<height; row++ ) {
			offset = row*width;
			uprow = row-1;
			for(int col=0; col<width; col++) {
				leftcol=col-1;
				p1=image[offset]&0xff;// p(x, y)
				p2=(leftcol<0) ? 0:sum[offset-1]; // p(x-1, y)
				p3=(uprow<0) ? 0:sum[offset-width]; // p(x, y-1);
				p4=(uprow<0||leftcol<0) ? 0:sum[offset-width-1]; // p(x-1, y-1);
				s = sum[offset]= p1+p2+p3-p4;
				squaresum[offset]=s*s;
				// System.out.print("\t[" + offset+"]=" + s);
				offset++;
			}
			// System.out.println();
		}
	}
	
	public static void main(String[] args) {
		byte[] data = new byte[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
		IntIntegralImage ii = new IntIntegralImage();
		ii.setImage(data);
		ii.process(7, 3);
		
		int sum = ii.getBlockSum(3, 2, 3, 3);
		System.out.println("sum = " + sum);
	}
}