图像处理之基于泛红算法的二值图像内部区域填充

一：基本原理

在二值图像处理中有个常用的操作叫做Hole Fill意思是填充所有封闭区域的内部，这种算法在二值图像基础上的对象识别与提取有很大作用。基于泛红填充算法实现二值图像内部区域填充是一直快速填充算法。

因为泛红填充通常需要指定从一个点开始，填满整个封闭区域，对一张二值图像来说，我们最好的办法是把背景当成一个封闭区域，从上向下从左到右查到第一个背景像素点，基于扫描线算法实现全部填充成一个非0，255之外的一个像素值，我这里是127。填充完成之后再一次从左到右，从上向下检查每个像素值如果是127的则为背景像素，否则全部设为前景像素。这样就完成二值图像每个封闭区域内部填充。

二：算法实现步骤

1. 读取二值图像

2. 基于扫描线算法对背景像素区域进行泛红填充，填充值为127

3. 循环每个像素对值为127的设为背景像素，其它值设为前景像素

4. 返回填充之后的二值图像像素数据

三：代码实现

package com.gloomyfish.basic.imageprocess;

public class FloodFillAlgorithm extends AbstractByteProcessor {
	private int foreground;
	private int background;
	private byte[] data;
	private int width;
	private int height;

	// stack data structure
	private int maxStackSize = 500; // will be increased as needed
	private int[] xstack = new int[maxStackSize];
	private int[] ystack = new int[maxStackSize];
	private int stackSize;

	public FloodFillAlgorithm(byte[] data) {
		this.data = data;
		this.foreground = 0;
		this.background = 255 - this.foreground;
	}

	public int getColor(int x, int y) {
		int index = y * width + x;
		return data[index] & 0xff;
	}

	public void setColor(int x, int y, int newColor) {
		int index = y * width + x;
		data[index] = (byte) newColor;
	}

	public void floodFillScanLineWithStack(int x, int y, int newColor, int oldColor) {
		if (oldColor == newColor) {
			System.out.println("do nothing !!!, filled area!!");
			return;
		}
		emptyStack();

		int y1;
		boolean spanLeft, spanRight;
		push(x, y);

		while (true) {
			x = popx();
			if (x == -1)
				return;
			y = popy();
			y1 = y;
			while (y1 >= 0 && getColor(x, y1) == oldColor)
				y1--; // go to line top/bottom
			y1++; // start from line starting point pixel
			spanLeft = spanRight = false;
			while (y1 < height && getColor(x, y1) == oldColor) {
				setColor(x, y1, newColor);
				if (!spanLeft && x > 0 && getColor(x - 1, y1) == oldColor)// just
																			// keep
																			// left
																			// line
																			// once
																			// in
																			// the
																			// stack
				{
					push(x - 1, y1);
					spanLeft = true;
				} else if (spanLeft && x > 0 && getColor(x - 1, y1) != oldColor) {
					spanLeft = false;
				}
				if (!spanRight && x < width - 1 && getColor(x + 1, y1) == oldColor) // just
																					// keep
																					// right
																					// line
																					// once
																					// in
																					// the
																					// stack
				{
					push(x + 1, y1);
					spanRight = true;
				} else if (spanRight && x < width - 1 && getColor(x + 1, y1) != oldColor) {
					spanRight = false;
				}
				y1++;
			}
		}

	}

	private void emptyStack() {
		while (popx() != -1) {
			popy();
		}
		stackSize = 0;
	}

	final void push(int x, int y) {
		stackSize++;
		if (stackSize == maxStackSize) {
			int[] newXStack = new int[maxStackSize * 2];
			int[] newYStack = new int[maxStackSize * 2];
			System.arraycopy(xstack, 0, newXStack, 0, maxStackSize);
			System.arraycopy(ystack, 0, newYStack, 0, maxStackSize);
			xstack = newXStack;
			ystack = newYStack;
			maxStackSize *= 2;
		}
		xstack[stackSize - 1] = x;
		ystack[stackSize - 1] = y;
	}

	final int popx() {
		if (stackSize == 0)
			return -1;
		else
			return xstack[stackSize - 1];
	}

	final int popy() {
		int value = ystack[stackSize - 1];
		stackSize--;
		return value;
	}

	@Override
	public void process(int width, int height) {
		this.width = width;
		this.height = height;

		for (int y = 0; y < height; y++) {
			if (getColor(0, y) == background)
				floodFillScanLineWithStack(0, y, 127, 255);
			if (getColor(width - 1, y) == background)
				floodFillScanLineWithStack(width - 1, y, 127, 255);
		}
		for (int x = 0; x < width; x++) {
			if (getColor(x, 0) == background)
				floodFillScanLineWithStack(x, 0, 127, 255);
			if (getColor(x, height - 1) == background)
				floodFillScanLineWithStack(x, height - 1, 127, 255);
		}
		
		int p = 0;
		for (int i = 0; i < data.length; i++) {
			p = data[i]&0xff;
			if (p == 127)
				data[i] = (byte)255;
			else
				data[i] = (byte)0;
		}
	}

}

四：运行结果

图像处理之基于泛红算法的二值图像内部区域填充

使用代码，要先读取二值图像数据到data字节数组：

FloodFillAlgorithm ffa = new FloodFillAlgorithm(data);
		ffa.process(width, height);