13

Java で再帰的な Flood 塗りつぶしアルゴリズムを使用して、画像の一部の領域を塗りつぶしています。イメージが非常に小さい場合は問題なく動作しますが、イメージが大きくなると、JVM からスタック オーバー フロー エラーが発生します。

これが、独自のスタックで Flood Fill を使用してメソッドを再実装する必要がある理由です。（私は、この種の場合にそれを行うための最良の方法であることを読みました）

誰かがそれをコーディングする方法を説明できますか? （手元にコードがない場合は、アルゴリズムの疑似コードで問題ありません）

私はインターネットでたくさん読んだことがありますが、よく理解できませんでした。

編集:再帰コードを追加しました

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;

}

ありがとう！

4

4 に答える 4

17

Queue を使用して、フラッドフィル アルゴリズムから再帰を取り除くことができます。以下にいくつかの基本的な考え方を示します。

  1. 訪問したポイントをマークする方法を用意する
  2. 最初に、開始点をキューに入れます。
  3. キューが空でない間は、その要素のデキューを続行します。そしてそれぞれの要素で
    1. その色を塗りつぶし、キューから取り出されたばかりのポイントを訪問済みとしてマークします
    2. 同じ色を持つ未訪問の隣接ポイントをキューに入れる

以下は、ブロブ検出の同様の異なる問題を解決するための私の Java コードです。ここからいくつかのアイデアを得て、問題に適応できることを願っています。ただし、コードは十分に分解されていません。

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

    }

}

テスト入力:

代替テキスト

于 2010-05-06T18:05:27.007 に答える
1

最後の FloodFill ステートメントを返して、テール コールにする必要があります。これにより、スタック スペースを節約できます。

于 2010-05-06T18:08:15.533 に答える