c# - por - flood fill java
Algoritmos de relleno de inundación (5)
El artículo de Wikipedia es bastante bueno. Mientras sus cuadrículas sean pequeñas, cualquier cosa funcionará.
A principios de este otoño realicé algunas inundaciones con imágenes escaneadas de 10 megapíxeles. (El problema era eliminar los bordes negros de las páginas de los libros que se habían escaneado en una fotocopiadora). En ese caso, solo hay dos colores, así que básicamente traté el problema como una búsqueda en un gráfico no dirigido, con cada píxel conectado a sus vecinos a lo largo las cuatro direcciones de la brújula Mantuve un mapa de bits separado para realizar un seguimiento de los píxeles que se han visitado .
Los principales hallazgos fueron
No intente la búsqueda recursiva en profundidad . Realmente quieres una estructura de datos explícita.
Una cola auxiliar utiliza mucho menos espacio que una pila . Alrededor de cuarenta veces menos espacio . En otras palabras, prefiera la búsqueda de amplitud a la de profundidad de búsqueda.
Una vez más, estos hallazgos se aplican solo a las cuadrículas con múltiples megapíxeles . En una cuadrícula pequeña y agradable como la que se muestra en su pregunta, cualquier algoritmo simple debería funcionar.
Es el fin de semana de nuevo, y eso significa que puedo jugar con mi proyecto de hobby .
Me cansé de crear niveles de prueba a mano, así que pensé en tomarme un descanso del desarrollo del motor y trabajar en un editor de niveles:
Editor de niveles http://gfilter.net/junk/Editor.JPG
Me gustaría implementar un algoritmo de relleno de inundación en el editor, que funcionaría como en un programa de pintura. ¿Alguien tiene alguna sugerencia sobre qué técnica funcionaría bien aquí?
El nivel es solo una matriz de 2d, por lo que podría considerarse lo mismo que un mapa de bits realmente.
¡Gracias!
Para ser justos, debería ser bastante simple. Como tiene la estructura básica de los mosaicos, el algoritmo sería bastante simple:
Select Tile To Fill:
Fill Till
Check neighbouring Tiles - If Empty Then Fill
Repeat, for all filled tiles.
Descargo de responsabilidad: Lo anterior es una descripción muy básica. Hay muchas referencias en la web que lo explican mucho mejor que yo.
Tuvimos que programar eso para la escuela:
1: stuff the start pixel into a queue, note its color. note it as added.
2: begin picking a pixel off the queue. If it''s similar to the start pixel:
2: put all its neighbours into the queue
for each added pixel, note it''s added. if already noted for a pixel, don''t
add it anymore.
3: color it with the destination color.
3: nonempty => jump back to 2
4: empty => we are finished
Dependiendo de si hacemos 8-neighbor o 4-neighbor, comprobamos los 8 píxeles vecinos, o solo los píxeles left / right o above / below un cierto pixel. Aquí está el código (usando ImageJ. He eliminado algún código no relevante). Espero que tenga sentido, es Java. Solo pide preguntas:
public class Uebung1_2 implements PlugInFilter, MouseListener {
private ImageProcessor ip;
boolean[] state;
int[] pixels;
Queue<Integer> nextPixels;
int threshould;
/**
* adds one pixel to the next-pixel queue only if it''s not
* already added.
*/
void addNextPixel(int p) {
if(!state[p]) {
nextPixels.add(p);
state[p] = true;
}
}
boolean pixelsSimilar(int color1, int color2) {
int dr = Math.abs(((color1 >> 16) & 0xff) -
((color2 >> 16) & 0xff));
int dg = Math.abs(((color1 >> 8) & 0xff) -
((color2 >> 8) & 0xff));
int db = Math.abs(((color1 >> 0) & 0xff) -
((color2 >> 0) & 0xff));
return ((double)(dr + dg + db) / 3.0) <= threshould;
}
/**
* actually does the hard work :)
* @param x the x position from which to start filling
* @param y the y position from which to start filling
*/
private void doFill(int x, int y, boolean connect8) {
// first, add the start pixel
int width = ip.getWidth(),
height = ip.getHeight();
/* for 8bit, we just gonna take the median of rgb */
Color colorC = ij.gui.Toolbar.getForegroundColor();
int color = colorC.getRGB();
int firstPixel = ip.get(x, y);
// go on with the mainloop
addNextPixel(y * width + x);
while(!nextPixels.isEmpty()) {
int nextPixel = nextPixels.remove();
int pixel = pixels[nextPixel];
if(pixelsSimilar(pixel, firstPixel)) {
// yay it matches. put the neighbours.
int xN = nextPixel % width,
yN = nextPixel / width;
/* the three pixels above */
if(yN - 1 >= 0) {
if(connect8) {
if(xN + 1 < width) {
addNextPixel(nextPixel - width + 1);
}
if(xN - 1 >= 0) {
addNextPixel(nextPixel - width - 1);
}
}
addNextPixel(nextPixel - width);
}
/* pixels left and right from the current one */
if(xN > 0) {
addNextPixel(nextPixel - 1);
}
if(xN + 1 < width) {
addNextPixel(nextPixel + 1);
}
/* three pixels below */
if(yN + 1 < height) {
if(connect8) {
if(xN + 1 < width) {
addNextPixel(nextPixel + width + 1);
}
if(xN - 1 >= 0) {
addNextPixel(nextPixel + width - 1);
}
}
addNextPixel(nextPixel + width);
}
/* color it finally */
pixels[nextPixel] = color;
}
}
}
@Override
public void run(ImageProcessor ip) {
ij.WindowManager.getCurrentImage().getCanvas().addMouseListener(this);
this.ip = ip;
this.pixels = (int[])ip.getPixels();
this.state = new boolean[ip.getPixelCount()];
this.nextPixels = new LinkedList<Integer>();
}
@Override
public int setup(String arg0, ImagePlus arg1) {
return DOES_RGB;
}
@Override
public void mouseClicked(MouseEvent e) {
ij.WindowManager.getCurrentWindow().getCanvas().removeMouseListener(this);
ij.gui.GenericDialog g = new GenericDialog("Please enter parameters");
g.addChoice("connection", new String[]{"4-connect", "8-connect"}, "8-connect");
g.addNumericField("Threshould (0..255)", 0.0, 3);
g.showDialog();
boolean connect8 = g.getNextChoice().equals("8-connect");
threshould = (int) g.getNextNumber();
doFill(e.getX(), e.getY(), connect8);
ij.WindowManager.getCurrentImage().draw();
}
}
Wikpedia proporciona algunos ejemplos de pseudocódigo de diferentes técnicas de relleno de inundación en su artículo de relleno de Inundación . La técnica que elija depende de la aplicación.
Recuerde que el relleno de inundación se puede enhebrar fácilmente (de forma similar a cómo puede ser el quicksort).