欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 22:09:09
...

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

一:基本原理

在二值图像处理中有个常用的操作叫做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);