使用递归连接像素

Question

我正在编写一个程序，它读入图像并计算有多少个连接的像素。图像包含4个白色背景上的黑色像素形状。

最后，我应该有count = 4;

我无法编写通过每个像素，并检查读取如果是黑色或白色的递归方法。如果是黑色，我需要检查周围是否还有其他黑色像素，如果没有，请将计数增加1。

任何想法？

试图递归方法：

public int recursive(int[][] g, int i,int j){ 
     //pseudo code 
     if(it is white) 
      return 0; 
     int north = recursive(g,i,j+1); 
     int south = recursive(g,i,j-1); 
     int west = recursive(g,i-1,j); 
     int east = recursive(g,i+1,j); 
     int nw = recursive(g,i-1,j+1); 
     int ne = recursive(g,i+1,j+1); 
     int sw = recursive(g,i-1,j-1); 
     int se = recursive(g,i+1,j-1); 
     return north+south+west+east+nw+ne+sw+se+1; 
    } 

即得到数的另一种方法：

int[][] grid = new int[width][height]; 

     for(int i = 0; i < width; i++){ 
      for(int j = 0; j < height; j++){ 
       recursive(grid,i,j); 
      } 
     } 

Answer 1

我想出了下面的递归解决方案：

public class Picture { 

    private static final int[][] PICTURE = new int[][] { 
    { 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1 }, 
    { 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 }, 
    { 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 }, 
    { 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1 }, 
    { 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 }, 
    { 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0 }, 
    { 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0 } 
    }; 

    private boolean[][] visited; 
    private int[][] picture; 

    public Picture(int[][] picture) { 
    this.picture = picture; 
    } 

    public int countBlobs() { 
    if (picture.length == 0) { 
     return 0; 
    } 
    int blobCount = 0; 
    visited = new boolean[picture.length][picture[0].length]; 
    for (int i = 0; i < picture.length; i++) { 
     for (int j = 0; j < picture[i].length; j++) { 
     if (!visited[i][j]) { 
      if (!isWhite(i, j)) { 
      countHelper(i, j); 
      blobCount++; 
      } 
      visited[i][j] = true; 
     } 
     } 
    } 
    return blobCount; 
    } 

    private void countHelper(int i, int j) { 
    visited[i][j] = true; 
    if (!isWhite(i, j)) { 
     for (int deltaI = -1; deltaI <= 1; deltaI++) { 
     for (int deltaJ = -1; deltaJ <= 1; deltaJ++) { 
      int adjI = i + deltaI; 
      int adjJ = j + deltaJ; 
      if (inBounds(adjI, adjJ) && !visited[adjI][adjJ]) { 
      countHelper(adjI, adjJ); 
      } 
     } 
     } 
    } 
    } 

    private boolean inBounds(int i, int j) { 
    return i >= 0 && j >= 0 && i < picture.length && j < picture[i].length; 
    } 

    private boolean isWhite(int i, int j) { 
    return inBounds(i, j) && picture[i][j] == 0; 
    } 

    public static void main(String[] args) { 
    System.out.println(new Picture(PICTURE).countBlobs()); 
    } 
} 

Answer 2

在我看来，你想要做的是数是图像中分离形状的数量，而不是连接像素的数量。连接像素的数量可能会比四个要高得多。

我看到它的方式是，最好的方法是创建一个单独的数组，用于跟踪天气或不是一个像素已包含在一个形状，以便确保没有包含像素在一个形状两次。要计算形状数量，您只需使用递归方法遍历图像中的每个像素即可查找连续形状，并标记包含在形状中的每个像素。

//Pass an array if integers as arguments 
//Counts the number of distinct continuous "shapes"(blocks of non-zero integers). 
public static int countShapes(int[][] image){ 
    //this boolean array keeps track of what pixels have been included in a shape 
    boolean[][] pixelsInShape = new boolean[image.length][image[0].length]; 
    int shapeCount=0; 
    for(int i = 0; i < image.length; i++){ 
     for(int j = 0; j < image[0].length; j++){ 
      if(image[i][j]!=0 && !pixelsInShape[i][j]){ 
       shapeCount++; 
       findShape(image,pixelsInShape,i,j); 
      } 
     } 
    } 
    return shapeCount; 
} 

public static void findShape(int[][] image, boolean[][] pixelsInShape, int row, int col){ 
    //before being included in a shape, a pixel must be withing the bounds of the image, not zero, and not already in a shape 
    if(row >= 0 && row < image.length && col >= 0 && col < image[0].length && image[row][col]!=0 && !pixelsInShape[row][col]){ 
     //marks the pixel included in the inclusion array 
     pixelsInShape[row][col]=true; 
     //recursive calls to all neighboring pixels. 
     findShape(image,pixelsInShape,row,col+1); 
     findShape(image,pixelsInShape,row,col-1); 
     findShape(image,pixelsInShape,row-1,col); 
     findShape(image,pixelsInShape,row+1,col); 
     findShape(image,pixelsInShape,row-1,col+1); 
     findShape(image,pixelsInShape,row+1,col+1); 
     findShape(image,pixelsInShape,row-1,col-1); 
     findShape(image,pixelsInShape,row+1,col-1); 
    } 
}