Заливка с помощью стека
Я использую рекурсивный алгоритм Заливки в Java для заполнения некоторых областей изображения. С очень маленькими изображениями это хорошо работает, но когда изображение de становится больше, JVM дает мне Стек По Ошибке Потока.
Это - причина, почему я должен повторно реализовать метод с помощью Заливки с моим собственным стеком. (Я читал, это - лучший способ сделать это в подобных случаях),
Кто-либо может объяснить меня, как кодировать его? (если у Вас не будет кода под рукой, то с псевдокодом алгоритма будет прекрасен),
Я читал много в Интернете, но я не понял это очень хорошо.
Править: Я добавил свой рекурсивный код
public void floodFill(int x, int y, Color targetColor,Color replacementColor) {
if (img.getRGB(x, y) != targetColor.getRGB()) return;
img.setRGB(x, y, replacementColor.getRGB());
floodFill(x - 1, y, targetColor, replacementColor);
floodFill(x + 1, y, targetColor, replacementColor);
floodFill(x, y - 1, targetColor, replacementColor);
floodFill(x, y + 1, targetColor, replacementColor);
return;
}
Спасибо!
2 ответа
Вы можете использовать Queue для удаления рекурсии из алгоритма заполнения. Вот несколько основных идей:
- Придумайте способ отмечать посещенные точки
- Вначале поставьте в очередь начальную точку.
- Пока очередь не пуста, продолжить удаление ее элемента из очереди. И с каждым элементом
- Залейте его цветом и пометьте только что удаленную точку как посещенную
- Поставьте в очередь непосещенные соседние точки того же цвета
Ниже приведен мой код Java для решить похожую, но другую задачу обнаружения blob . Я надеюсь, что вы почерпнете из этого некоторые идеи и сможете адаптировать их к проблеме. Однако код не очень хорошо продуман.
package blobdetector;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import javax.imageio.ImageIO;
import javax.management.Query;
public class Main {
public Main() {
}
public static boolean isBlack(BufferedImage image, int posX, int posY) {
int color = image.getRGB(posX, posY);
int brightness = (color & 0xFF) + ((color >> 2) & 0xFF)
+ ((color >> 4) & 0xFF);
brightness /= 3;
return brightness < 128;
}
public static void main(String[] args) {
if (args.length != 1) {
System.err.println("ERROR: Pass filename as argument.");
return;
}
String filename = args[0];
// String filename =
// "C:\\Users\\Natthawut\\Desktop\\blob.jpg";
try {
BufferedImage bimg = ImageIO.read(new File(filename));
boolean[][] painted = new boolean[bimg.getHeight()][bimg.getWidth()];
for (int i = 0; i < bimg.getHeight(); i++) {
for (int j = 0; j < bimg.getWidth(); j++) {
if (isBlack(bimg, j, i) && !painted[i][j]) {
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(j, i));
int pixelCount = 0;
while (!queue.isEmpty()) {
Point p = queue.remove();
if ((p.x >= 0)
&& (p.x < bimg.getWidth() && (p.y >= 0) && (p.y < bimg
.getHeight()))) {
if (!painted[p.y][p.x]
&& isBlack(bimg, p.x, p.y)) {
painted[p.y][p.x] = true;
pixelCount++;
queue.add(new Point(p.x + 1, p.y));
queue.add(new Point(p.x - 1, p.y));
queue.add(new Point(p.x, p.y + 1));
queue.add(new Point(p.x, p.y - 1));
}
}
}
System.out.println("Blob detected : " + pixelCount
+ " pixels");
}
}
}
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
Тестовый ввод:
Вы должны вернуть последний оператор floodFill, превратив его в хвостовой вызов. Это сэкономит место в стеке.