图像处理之基于泛红算法的二值图像内部区域填充
一：基本原理
在二值图像处理中有个常用的操作叫做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);
