使用遞歸連接像素

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