java - 在黑白图像上查找未连接区域（岛）的算法

Question

我有黑白点（像素）的图像。我需要为每个不同的白色像素簇创建不同的集合，其中包含该白点的 x,y 坐标（例如，如果我有带有三个未连接的白色图像岛的黑色图像，我需要生成三个带有坐标的集合）。任何人都可以为此建议我算法吗？

细胞是连接的，如果abs(x1-x2) <=1 && abs(y1-y2)<=1

Answer 1

连接组件标记算法旨在隔离和枚举此类集群

Answer 2

也许是洪水填充算法。

Answer 3

区域增长，这应该可以解决问题。该链接正在回答一个不同的问题，但基本算法应该正好满足您的需求。你只需要传递另一个参数，它告诉集群的数量。从 1 开始，每当你进入一个新的集群时，增加这个值。

这个新参数将取代前景的 1 和背景的 2。这将为您提供所有集群的总数以及它们的所有位置。

Answer 4

这使用洪水填充算法。查找连接区域的数量 import com.sun.corba.se.spi.presentation.rmi.IDLNameTranslator;

import javax.xml.transform.Source;
import java.awt.*;
import java.awt.font.ImageGraphicAttribute;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;

/**
 * Created by IntelliJ IDEA.
 * User: ruzbeh
 * Date: 6/29/12
 * Time: 12:58 AM
 * To change this template use File | Settings | File Templates.
 */
public class Solution {


    static int[][] img;

    static void compLabel(int i, int j, int m,int  n) {
        if(i<0 || j<0 ||i > n-1||j > n-1) return;
        if (img[i][j] == 1) {
            img[i][j] = m;
            compLabel(i - 1, j - 1, m,n);
            compLabel(i - 1, j, m,n);
            compLabel(i - 1, j + 1, m,n);
            compLabel(i, j - 1, m,n);
            compLabel(i, j + 1, m,n);
            compLabel(i + 1, j - 1, m,n);
            compLabel(i + 1, j, m,n);
            compLabel(i + 1, j + 1, m,n);
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            img = new int[n][n];
            int label = 2;
            for (int i = 0; i < n; i++) {
                int j = 0;
                for (String str : br.readLine().split(" ")) {
                    int value = Integer.parseInt(str);

                    img[i][j] = value;

                    j++;
                }

            }
            for (int y = 0; y < n; y++)
                for (int x = 0; x < n; x++)
                    if (img[x][y] == 1) {
                        compLabel(x, y, ++label,n);
                    }

            System.out.println(label - 2);
        }
    }
}