如何在二维矩阵中找到blob的个数

Question

如何在二维矩阵中找到blob的数量?SIZE MxN

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

XOOOXO
OXOXOX
XXOOXO

我想使用8邻域(见这里)。所以我希望在上面的例子中找到2个blobs。

Answer 1

想法很简单:标记每个连续的blob，并计算标记了多少blob。

下面是一些伪代码(你没有指定编程语言)让你开始:

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

Visit函数/方法如下:

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

你所要做的就是实现其他的函数/方法，但是它们非常简单。

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