如何找到二维矩阵中的斑点数？

Question

如何找到二维矩阵中的斑点数？尺寸 MxN

斑点是连续的 X 像素块。其中矩阵包含 X 和 O

XOOOXO
OXOXOX
XXOOXO

我想使用 8 邻域（参见 here）。所以我希望在上面的示例中找到 2 个 blob。

Answer 1

想法很简单：标记每个连续的斑点并计算标记了多少个斑点。

这是一些伪代码（您没有指定编程语言）来帮助您入门：

numBlobs = 0;
foreach(item in matrix)
{
    res = Visit(item);
    if(res > 0) 
    {
        numBlobs = numBlobs + 1;
    }
}
return numBlobs;

访问 function/method 看起来像这样：

Visit(item)
{
    marked = 0;
    if(item.IsX() && !IsItemMarked(neighbour))
    {
        MarkItemAsVisited(item);
        marked = 1;
        foreach(neighbour in GetNeighbours(item))
        {
            marked = marked + Visit(neighbour);
        }
    }
    return marked;
}

您所要做的就是实现另一个 fucntions/methods，但它们非常简单。

Answer 2

public static void main(String[] args) {
        int[][] matrix = new int[6][5];
        System.out.println(matrix.length);
        for (int i=0; i < matrix.length; i++) {
            for (int j=0; j < matrix[i].length; j++) {
                matrix[i][j] = 0;
            }
        }

        matrix[0][3] = 1;
        matrix[1][1] = 1;
        matrix[1][3] = 1;
        matrix[2][1] = 1;
        matrix[2][2] = 1;
        matrix[2][3] = 1;
        matrix[4][0] = 1;
        matrix[4][4] = 1;
        matrix[5][2] = 1;
        matrix[5][3] = 1;
        matrix[5][4] = 1;

        System.out.println(findBlobCount(matrix, matrix.length, matrix[0].length));
    }

    static int findBlobCount (int matrix[][], int rowCount, int colCount)
    {
        int visited[][] = new int[rowCount][colCount]; // all initialized to false

        int count=0;

        for (int i=0; i<rowCount; i++)
        {
            for (int j=0; j<colCount; j++)
            {
                if (matrix[i][j] == 1 && visited[i][j] == 0) // unvisited black cell
                {
                    markVisited (i,j, matrix, visited, rowCount, colCount);
                    count++;
                }
            }
        }

        return count;
    }


    static int markVisited (int i, int j, int [][]matrix, int [][]visited, int rowCount, int colCount)
    {
        if (i < 0 || j < 0)
            return 0;

        if (i >= rowCount || j >= colCount)
            return 0;

        if (visited[i][j] == 1) // already visited
            return 1;

        if (matrix[i][j] == 0) // not a black cell
            return 0;

        visited[i][j] = 1;

        // recursively mark all the 4 adjacent cells - right, left, up and down
        return  markVisited (i+1, j, matrix, visited, rowCount, colCount) 
                + markVisited (i-1, j, matrix, visited, rowCount, colCount) 
                + markVisited (i, j+1, matrix, visited, rowCount, colCount) 
                + markVisited (i, j-1, matrix, visited, rowCount, colCount);
    }

如何找到二维矩阵中的斑点数？

How to find the number of blobs in a 2d matrix?

algorithm

multidimensional-array

neighbours