Espaces blancs laissés en couleur en utilisant QueueLinearFloodFillAlgorithm

Question

J'essaye d'implémenter l'algorithme de remplissage d'inondation dans android. Il travaillait très lent, donc j'ai essayé la file d'attente inondation linéaire algorithme de remplissage selon ce lien

How to use flood fill algorithm in Android?

Il travaille vite, mais la partie n'est pas complètement colorée. Il y a quelques espaces blancs sur les bords comme sur cette image.

J'ai utilisé le code suivant:

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; 
     } 
    } 
} 

J'ai essayé d'augmenter la valeur de la tolérance, mais certains espaces blancs sont toujours à gauche et si j'augmente la valeur beaucoup alors l'image entière se colore. S'il vous plaît aidez-moi!

Answer 1

Les pixels blancs/gris sont le résultat de l'anti-crénelage, qui est utilisé pour lisser les bords des lignes. Pour éviter ces artefacts, vous pouvez simplement ne pas utiliser l'anti-crénelage lors de la création des images, sinon vous pouvez utiliser une tolérance en deux étapes: une valeur de tolérance inférieure pour propager le remplissage, et une valeur plus élevée pour colorier les pixels sans les propager le remplir plus loin. Cependant, ces deux approches vont détruire l'anti-aliasing dans l'image, ce qui réduira la qualité de l'image. Une autre approche consiste à faire un autre passage sur l'image et traiter les pixels qui bordent le remplissage (ceux où pixelsChecked est faux mais il y a au moins un voisin où pixelsChecked est vrai) et calculer une valeur de pixel anti-alias, en supposant que les pixels sont étant anti-aliasé contre une ligne noire.

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; 
} 

Appel antiAliasFillOutline() à la fin du remplissage d'inondation.

Vous pouvez accélérer un peu (au détriment de la lisibilité) par inline certains des appels de fonction et la suppression des contrôles des limites sur 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++; 
     } 
    } 
} 

Vous pouvez également essayer simplement de vérifier les 4 pixels voisins au lieu des 8 voisins y compris les diagonales. En outre, des valeurs telles que fillred etc. et (startColor[0] + startColor[1] + startColor[2]) pourraient être calculées une fois et stockées dans des variables membres. Pourquoi les régions internes sont colorées?