使用 QueueLinearFloodFillAlgorithm 着色时留下的空白
White spaces left in coloring using QueueLinearFloodFillAlgorithm
我正在尝试在 android 中实现洪水填充算法。它工作得非常慢，所以我根据这个 link
尝试了队列线性洪水填充算法
How to use flood fill algorithm in Android?
它工作得很快，但部分没有完全着色。就像这张图一样，边缘有一些空白。
我使用了以下代码：
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;
}
}
}
我尝试增加公差值，但仍然有一些空白，如果我增加了很多值，那么整个图像都会变色。
请帮助我！
white/grey 像素是抗锯齿的结果，用于平滑线条的边缘。为了避免这些伪像，您可以在创建图像时简单地不使用抗锯齿，或者您可以使用两步容差：较低的容差值用于传播洪水填充，而较高的容差值用于为像素着色但不传播进一步填充。
但是这两种方法都会破坏图像中的抗锯齿功能，从而降低图像质量。另一种方法是对图像进行另一次传递并处理填充边界的像素（pixelsChecked 为假但至少有一个邻居 pixelsChecked 为真的像素）并计算抗锯齿像素值，假设针对黑线消除像素锯齿。
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;
}
在洪水填充结束时调用antiAliasFillOutline()。
您可以通过内联一些函数调用并删除 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++;
}
}
}
您也可以尝试只检查 4 个相邻像素而不是 8 个相邻像素（包括对角线）。此外，fillred 等值和 (startColor[0] + startColor[1] + startColor[2]) 可以计算一次并存储在成员变量中。
我正在尝试在 android 中实现洪水填充算法。它工作得非常慢，所以我根据这个 link
尝试了队列线性洪水填充算法How to use flood fill algorithm in Android?
它工作得很快，但部分没有完全着色。就像这张图一样，边缘有一些空白。
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;
}
}
}
我尝试增加公差值，但仍然有一些空白，如果我增加了很多值，那么整个图像都会变色。 请帮助我！
white/grey 像素是抗锯齿的结果，用于平滑线条的边缘。为了避免这些伪像，您可以在创建图像时简单地不使用抗锯齿，或者您可以使用两步容差：较低的容差值用于传播洪水填充，而较高的容差值用于为像素着色但不传播进一步填充。
但是这两种方法都会破坏图像中的抗锯齿功能，从而降低图像质量。另一种方法是对图像进行另一次传递并处理填充边界的像素（pixelsChecked 为假但至少有一个邻居 pixelsChecked 为真的像素）并计算抗锯齿像素值，假设针对黑线消除像素锯齿。
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;
}
在洪水填充结束时调用antiAliasFillOutline()。
您可以通过内联一些函数调用并删除 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++;
}
}
}
您也可以尝试只检查 4 个相邻像素而不是 8 个相邻像素（包括对角线）。此外，fillred 等值和 (startColor[0] + startColor[1] + startColor[2]) 可以计算一次并存储在成员变量中。