使用QueueLinearFloodFillAlgorithm在着色中留有空白 [英] White spaces left in coloring using QueueLinearFloodFillAlgorithm
本文介绍了使用QueueLinearFloodFillAlgorithm在着色中留有空白的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在尝试在android中实现泛洪填充算法。它的运行速度非常慢，因此我根据此链接尝试了队列线性填充算法
我使用了以下代码：
公共类QueueLinearFloodFiller {
受保护的位图图像= null;
保护的int []公差= new int [] {0，0，0};
protected int width = 0;
protected int height = 0;
protected int [] pixel = null;
protected int fillColor = 0;
protected int [] startColor = new int [] {0，0，0};
protected boolean [] pixelChecked;
受保护的队列< FloodFillRange>范围
//使用图像进行构造并复制一个副本，
//使用BufferedImage和泛洪填充进行构造将直接写入
//提供BufferedImage
public QueueLinearFloodFiller（Bitmap img）{
copyImage（img）;
}
public QueueLinearFloodFiller（Bitmap img，int targetColor，int newColor）{
useImage（img）;
setFillColor（newColor）;
setTargetColor（targetColor）;
}
public void setTargetColor（int targetColor）{
startColor [0] = Color.red（targetColor）;
startColor [1] = Color.green（targetColor）;
startColor [2] = Color.blue（targetColor）;
}
public int getFillColor（）{
return fillColor;
}
public void setFillColor（int value）{
fillColor = value;
}
public int [] getTolerance（）{
返回容限；
}
public void setTolerance（int [] value）{
tolerance = value;
}
public void setTolerance（int value）{
tolerance = new int [] {value，value，value};
}
public Bitmap getImage（）{
返回图片；
}
public void copyImage（Bitmap img）{
//将数据从提供的Image复制到BufferedImage以写入泛洪填充
//，使用getImage检索
//将数据缓存在成员变量中以减少属性调用的开销
width = img.getWidth（）;
height = img.getHeight（）;
image = Bitmap.createBitmap（width，height，Bitmap.Config.RGB_565）;
Canvas canvas = new Canvas（image）;
canvas.drawBitmap（img，0，0，null）;
像素= new int [width * height];
image.getPixels（pixels，0，width，1，1，width-1，height-1）;
}
public void useImage（Bitmap img）{
//使用预先提供的BufferedImage并直接写入其中
//将数据缓存在成员变量中减少属性调用的开销
width = img.getWidth（）;
height = img.getHeight（）;
image = img;
像素= new int [width * height];
image.getPixels（pixels，0，width，1，1，width-1，height-1）;
}
protected void prepare（）{
//在开始洪水填充之前调用
pixelChecked = new boolean [pixels.length];
range = new LinkedList< FloodFillRange>（）;
}
//用当前选定的填充
//颜色填充位图上的指定点。
// int x，int y：填充
的起始坐标
public void floodFill（int x，int y）{
//设置
prepare（）;
if（startColor [0] == 0）{
// ***获取起始颜色。
int startPixel =像素[（宽度* y）+ x];
startColor [0] =（startPixel>> 16）& 0xff;
startColor [1] =（startPixel>> 8）& 0xff;
startColor [2] = startPixel& 0xff;
}
// ***请先致电充水。
LinearFill（x，y）;
//调用洪水填充例程，而洪水填充范围仍在
//排队
FloodFillRange范围内；
while（ranges.size（）> 0）{
// **使队列脱离下一个范围
range = range.remove（）;
// **检查Floodfill范围内每个像素的上方和下方
int downPxIdx =（width *（range.Y + 1））+ range.startX;
int upPxIdx =（宽度*（范围.Y-1））+ range.startX;
int upY = range.Y-1; //所以我们可以通过ref
int downY = range.Y + 1来传递y坐标。
for（int i = range.startX; i< = range.endX; i ++）{
// *开始向上填充
//如果我们不在上面位图的顶部和
上方的像素// //如果（range.Y> 0&&（！pixelsChecked [upPxIdx]）
& ;& CheckPixel（upPxIdx））
LinearFill（i，upY）;
// *开始向下填充
//如果我们不低于位图的底部，并且像素
//不低于位图的颜色，则位于颜色公差$ b之内$ b if（range.Y<（height-1）&&（！pixelsChecked [downPxIdx]）
&& CheckPixel（downPxIdx））
LinearFill（i，downY）;
downPxIdx ++;
upPxIdx ++;
}
}
image.setPixels（pixels，0，width，1，1，width-1，height-1）;
}
//从给定的x坐标开始，在给定的y坐标上找到填充区域
//的最左边界和右边界，填充为
//过去了。
//将结果水平范围添加到洪水范围队列中，
//在主循环中进行处理。
// int x，int y：起始坐标
受保护的void LinearFill（int x，int y）{
// ***查找颜色区域的左边缘
int lFillLoc = x; //检查/填充左侧的位置
int pxIdx =（width * y）+ x;
而（true）{
// **填充颜色
pixel [pxIdx] = fillColor;
// **表示该像素已被检查并填充
pixelChecked [pxIdx] = true;
// **减少
lFillLoc--; //减少计数器
pxIdx--; //减少像素索引
// **如果我们位于位图或颜色区域
的边缘，则退出循环，如果（lFillLoc< 0 ||（pixelsChecked [pxIdx]） ||！CheckPixel（pxIdx））{
break;
}
}
lFillLoc ++;
// ***查找颜色区域的右边缘
int rFillLoc = x; //检查/填充左侧的位置
pxIdx =（width * y）+ x;
而（true）{
// **填充颜色
pixel [pxIdx] = fillColor;
// **表示该像素已被检查并填充
pixelChecked [pxIdx] = true;
// **递增
rFillLoc ++; //递增计数器
pxIdx ++; //递增像素索引
// **如果我们位于位图或颜色区域
的边缘，则退出循环if（rFillLoc> = width || pixelChecked [pxIdx] ||！ CheckPixel（pxIdx））{
休息；
}
}
rFillLoc--;
//将范围添加到队列
FloodFillRange r =新的FloodFillRange（lFillLoc，rFillLoc，y）;
range.offer（r）;
}
//查看像素是否在颜色公差范围内。
受保护的布尔CheckPixel（int px）{
int red =（pixels [px]>>>> 16）& 0xff;
int green =（pixels [px]>>> 8）& 0xff;
int blue = pixel [px]& 0xff;
返回（红色> =（startColor [0]-公差[0]）
&&红色< =（startColor [0] +公差[0]）
&& green> =（startColor [1]-公差[1]）$ b $ b& green< ==（startColor [1] +公差[1]）$ b $ b& &蓝色> =（startColor [2]-公差[2]）&&蓝色< =（startColor [2] +公差[2]））;
}
//表示要填充和分支的线性范围。
受保护的类FloodFillRange {
public int startX;
public int endX;
public int Y;
public FloodFillRange（int startX，int endX，int y）{
this.startX = startX;
this.endX = endX;
this.Y = y;
}
}
}
我尝试增加公差值但是仍然留有一些空白，如果我增加很多值，那么整个图像就会变色。
请帮助我！
解决方案
白色/灰色像素是抗锯齿的结果，通常用于平滑线条的边缘。为了避免这些伪像，您可以在创建图像时根本不使用抗锯齿，否则可以使用两步公差：较低的公差值用于传播泛洪填充，较高的公差值用于对像素着色而不传播
但是，这两种方法都会破坏图像中的抗锯齿，从而降低图像质量。另一种方法是对图像进行另一遍处理，并处理填充边界的像素（其中 pixelsChecked 为假，但至少有一个邻居为 pixelChecked 为true），并计算出消除锯齿的像素值，假设像素针对黑线进行了消除锯齿。
public boolean isFilled（int x，int y）
{
if（（x< 0）||（y< 0） ||（x> =宽度）||（y> =高度））
返回false;
返回pixelChecked [（width * y）+ x];
}
public boolean isNeighbourFilled（int x，int y）
{
//如果至少一个邻居被填充，则返回true：
for（ int offsetY = -1; offsetY <= 1; offsetY ++）
{
for（int offsetX = -1; offsetX <= 1; offsetX ++）
{
if（ （offsetX！= 0）&&（offsetY！= 0）&&
isFilled（x + offsetX，y + offsetY））
返回true;
}
}
返回false；
}
public void antiAliasFillOutline（）
{
for（int y = 0; y< height; y ++）
{
for（int x = 0; x< width; x ++）
{
// //如果像素未被邻居填充，则它位于边界
if（！isFilled（x，y ）&& isNeighbourFilled（x，y））
{
//计算抗锯齿像素值：
antiAliasPixel（x，y）;
}
}
}
}
public void antiAliasPixel（int x，int y）
{
int pixel =像素[（宽度* y）+ x];
int red =（pixel>>> 16）& 0xff;
int green =（pixel>>> 8）& 0xff;
int blue =像素& 0xff;
int fillred =（fillColor>>> 16）& 0xff;
int fillgreen =（fillColor>>> 8）& 0xff;
int fillblue = fillColor& 0xff;
//计算从0到256的抗锯齿量：
int量=（（红色+绿色+蓝色）* 256）/
（startColor [0 ] + startColor [1] + startColor [2]）;
if（金额> 256）
金额= 256;
红色=（实心*金额）>> 8;
green =（fillgreen *数量）>> 8;
blue =（fillblue *数量）>> 8;
pixels [（width * y）+ x] = 0xff000000 | （红色<< 16）| （绿色<< 8）|蓝色;
}
致电 antiAliasFillOutline（）
您可以通过内联一些函数调用并删除边界检查来加快它的速度（以可读性为代价）。 on pixelsChecked ：
public void antiAliasFillOutlineFaster（）
{
for（int y = 1; y< height-1; y ++）
{
int i =（y *宽度）+ 1;
for（int x = 1; x< width-1; x ++）
{
//如果像素未被邻居填充，则它位于边界
if（ ！pixelsChecked [i]&&
（pixelsChecked [i-1] || pixelChecked [i + 1] ||
pixelChecked [i-width-1] || pixelChecked [i-width] || pixelChecked [i-width + 1] ||
pixelChecked [i + width-1] || pixelChecked [i + width] || pixelChecked [i + width + 1]））
{
//计算抗锯齿像素值：
antiAliasPixel（x，y）;
}
i ++;
}
}
}
您也可以尝试检查4个相邻像素，而不是包括对角线的8个相邻像素。此外，诸如 fillred 等和（startColor [0] + startColor [1] + startColor [2]）的值可以计算一次并存储在成员变量中。
I am trying to implement flood fill algorithm in android. It was working very slow, so I tried queue linear flood fill algorithm according to this link
How to use flood fill algorithm in Android?
It is working fast but the portion is not completely colored. There are some white spaces left on the edgeslike in this picture.
I used the following code:
public class QueueLinearFloodFiller {
protected Bitmap image = null;
protected int[] tolerance = new int[] { 0, 0, 0 };
protected int width = 0;
protected int height = 0;
protected int[] pixels = null;
protected int fillColor = 0;
protected int[] startColor = new int[] { 0, 0, 0 };
protected boolean[] pixelsChecked;
protected Queue<FloodFillRange> ranges;
// Construct using an image and a copy will be made to fill into,
// Construct with BufferedImage and flood fill will write directly to
// provided BufferedImage
public QueueLinearFloodFiller(Bitmap img) {
copyImage(img);
}
public QueueLinearFloodFiller(Bitmap img, int targetColor, int newColor) {
useImage(img);
setFillColor(newColor);
setTargetColor(targetColor);
}
public void setTargetColor(int targetColor) {
startColor[0] = Color.red(targetColor);
startColor[1] = Color.green(targetColor);
startColor[2] = Color.blue(targetColor);
}
public int getFillColor() {
return fillColor;
}
public void setFillColor(int value) {
fillColor = value;
}
public int[] getTolerance() {
return tolerance;
}
public void setTolerance(int[] value) {
tolerance = value;
}
public void setTolerance(int value) {
tolerance = new int[] { value, value, value };
}
public Bitmap getImage() {
return image;
}
public void copyImage(Bitmap img) {
// Copy data from provided Image to a BufferedImage to write flood fill
// to, use getImage to retrieve
// cache data in member variables to decrease overhead of property calls
width = img.getWidth();
height = img.getHeight();
image = Bitmap.createBitmap(width, height, Bitmap.Config.RGB_565);
Canvas canvas = new Canvas(image);
canvas.drawBitmap(img, 0, 0, null);
pixels = new int[width * height];
image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
}
public void useImage(Bitmap img) {
// Use a pre-existing provided BufferedImage and write directly to it
// cache data in member variables to decrease overhead of property calls
width = img.getWidth();
height = img.getHeight();
image = img;
pixels = new int[width * height];
image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
}
protected void prepare() {
// Called before starting flood-fill
pixelsChecked = new boolean[pixels.length];
ranges = new LinkedList<FloodFillRange>();
}
// Fills the specified point on the bitmap with the currently selected fill
// color.
// int x, int y: The starting coords for the fill
public void floodFill(int x, int y) {
// Setup
prepare();
if (startColor[0] == 0) {
// ***Get starting color.
int startPixel = pixels[(width * y) + x];
startColor[0] = (startPixel >> 16) & 0xff;
startColor[1] = (startPixel >> 8) & 0xff;
startColor[2] = startPixel & 0xff;
}
// ***Do first call to floodfill.
LinearFill(x, y);
// ***Call floodfill routine while floodfill ranges still exist on the
// queue
FloodFillRange range;
while (ranges.size() > 0) {
// **Get Next Range Off the Queue
range = ranges.remove();
// **Check Above and Below Each Pixel in the Floodfill Range
int downPxIdx = (width * (range.Y + 1)) + range.startX;
int upPxIdx = (width * (range.Y - 1)) + range.startX;
int upY = range.Y - 1;// so we can pass the y coord by ref
int downY = range.Y + 1;
for (int i = range.startX; i <= range.endX; i++) {
// *Start Fill Upwards
// if we're not above the top of the bitmap and the pixel above
// this one is within the color tolerance
if (range.Y > 0 && (!pixelsChecked[upPxIdx])
&& CheckPixel(upPxIdx))
LinearFill(i, upY);
// *Start Fill Downwards
// if we're not below the bottom of the bitmap and the pixel
// below this one is within the color tolerance
if (range.Y < (height - 1) && (!pixelsChecked[downPxIdx])
&& CheckPixel(downPxIdx))
LinearFill(i, downY);
downPxIdx++;
upPxIdx++;
}
}
image.setPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
}
// Finds the furthermost left and right boundaries of the fill area
// on a given y coordinate, starting from a given x coordinate, filling as
// it goes.
// Adds the resulting horizontal range to the queue of floodfill ranges,
// to be processed in the main loop.
// int x, int y: The starting coords
protected void LinearFill(int x, int y) {
// ***Find Left Edge of Color Area
int lFillLoc = x; // the location to check/fill on the left
int pxIdx = (width * y) + x;
while (true) {
// **fill with the color
pixels[pxIdx] = fillColor;
// **indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
// **de-increment
lFillLoc--; // de-increment counter
pxIdx--; // de-increment pixel index
// **exit loop if we're at edge of bitmap or color area
if (lFillLoc < 0 || (pixelsChecked[pxIdx]) || !CheckPixel(pxIdx)) {
break;
}
}
lFillLoc++;
// ***Find Right Edge of Color Area
int rFillLoc = x; // the location to check/fill on the left
pxIdx = (width * y) + x;
while (true) {
// **fill with the color
pixels[pxIdx] = fillColor;
// **indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
// **increment
rFillLoc++; // increment counter
pxIdx++; // increment pixel index
// **exit loop if we're at edge of bitmap or color area
if (rFillLoc >= width || pixelsChecked[pxIdx] || !CheckPixel(pxIdx)) {
break;
}
}
rFillLoc--;
// add range to queue
FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
ranges.offer(r);
}
// Sees if a pixel is within the color tolerance range.
protected boolean CheckPixel(int px) {
int red = (pixels[px] >>> 16) & 0xff;
int green = (pixels[px] >>> 8) & 0xff;
int blue = pixels[px] & 0xff;
return (red >= (startColor[0] - tolerance[0])
&& red <= (startColor[0] + tolerance[0])
&& green >= (startColor[1] - tolerance[1])
&& green <= (startColor[1] + tolerance[1])
&& blue >= (startColor[2] - tolerance[2]) && blue <= (startColor[2] + tolerance[2]));
}
// Represents a linear range to be filled and branched from.
protected class FloodFillRange {
public int startX;
public int endX;
public int Y;
public FloodFillRange(int startX, int endX, int y) {
this.startX = startX;
this.endX = endX;
this.Y = y;
}
}
}
I tried increasing the tolerance value but some white spaces are still left and if i increase the value a lot then the whole image gets colored. Please help me!
解决方案
The white/grey pixels are a result of anti-aliasing, which is used to smooth the edges of the lines. To avoid these artifacts, you could simply not use anti-aliasing when creating the images, or else you could use a two-step tolerance: a lower tolerance value for propagating the flood fill, and a higher one for coloring the pixels but not propagating the fill any further.
However both of these approaches will destroy the anti-aliasing in the image, which will reduce image quality. Another approach is to do another pass over the image and process the pixels bordering the fill (those where pixelsChecked is false but there is at least one neighbour where pixelsChecked is true) and compute an anti-aliased pixel value, assuming that the pixels are being anti-aliased against a black line.
public boolean isFilled(int x, int y)
{
if((x < 0) || (y < 0) || (x >= width) || (y >= height))
return false;
return pixelsChecked[(width * y) + x];
}
public boolean isNeighbourFilled(int x, int y)
{
// return true if at least one neighbour is filled:
for(int offsetY = -1; offsetY <= 1; offsetY++)
{
for(int offsetX = -1; offsetX <= 1; offsetX++)
{
if((offsetX != 0) && (offsetY != 0) &&
isFilled(x + offsetX, y + offsetY))
return true;
}
}
return false;
}
public void antiAliasFillOutline()
{
for(int y = 0; y < height; y++)
{
for(int x = 0; x < width; x++)
{
// if pixel is not filled by neighbour is then it's on the border
if(!isFilled(x, y) && isNeighbourFilled(x, y))
{
// compute an anti-aliased pixel value:
antiAliasPixel(x, y);
}
}
}
}
public void antiAliasPixel(int x, int y)
{
int pixel = pixels[(width * y) + x];
int red = (pixel >>> 16) & 0xff;
int green = (pixel >>> 8) & 0xff;
int blue = pixel & 0xff;
int fillred = (fillColor >>> 16) & 0xff;
int fillgreen = (fillColor >>> 8) & 0xff;
int fillblue = fillColor & 0xff;
// work out how much to anti-alias from 0 to 256:
int amount = ((red + green + blue) * 256) /
(startColor[0] + startColor[1] + startColor[2]);
if(amount > 256)
amount = 256;
red = (fillred * amount) >> 8;
green = (fillgreen * amount) >> 8;
blue = (fillblue * amount) >> 8;
pixels[(width * y) + x] = 0xff000000 | (red << 16) | (green << 8) | blue;
}
Call antiAliasFillOutline() at the end of the flood fill.
You could speed it up a bit (at the expense of readability) by inlining some of the function calls and removing the bounds checks on pixelsChecked:
public void antiAliasFillOutlineFaster()
{
for(int y = 1; y < height - 1; y++)
{
int i = (y * width) + 1;
for(int x = 1; x < width - 1; x++)
{
// if pixel is not filled by neighbour is then it's on the border
if(!pixelsChecked[i] &&
(pixelsChecked[i-1] || pixelsChecked[i+1] ||
pixelsChecked[i-width-1] || pixelsChecked[i-width] || pixelsChecked[i-width+1] ||
pixelsChecked[i+width-1] || pixelsChecked[i+width] || pixelsChecked[i+width+1]))
{
// compute an anti-aliased pixel value:
antiAliasPixel(x, y);
}
i++;
}
}
}
You could also try just checking the 4 neighbouring pixels instead of the 8 neighbours including diagonals. Also, values like fillred etc and (startColor[0] + startColor[1] + startColor[2]) could be computed once and stored in member variables.
这篇关于使用QueueLinearFloodFillAlgorithm在着色中留有空白的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
