ArrayLists堆棧溢出錯誤

Question

我正在嘗試編寫一些代碼來查看圖像文件是否有相同顏色的像素組。

我這樣做的方式是我通過像素遍歷圖像（以顏色的哈希代碼的1d整數數組的形式）來查找我正在搜索的顏色的像素。一旦找到一個，我做一個dfs來找到相同顏色的相鄰像素，並將它們添加到一個我稱爲Blob的新對象中。我使用布爾數組來跟蹤哪些像素已被添加，因此我不添加相同的斑點。

我使用ArrayList爲每個Blob對象跟蹤像素數量。然後我使用另一個Blob ArrayList來存儲不同的組。

當我試圖運行一個簡單的例子，上半部分白色和下半部分底部的圖片時，當我嘗試使用太大的圖片時，出現堆棧溢出錯誤。具體來說，當我嘗試使用320x240圖像進行此操作時，一旦將2752像素添加到blob，我就會獲得堆棧溢出。

我只是沒有使用正確的數據結構來做我想做的事情？我讀過ArrayLists可以在其中存儲Integer.maxValue對象。

我的代碼粘貼在下面。任何幫助是極大的讚賞。

//blobfind tests code to find similar pixels of a minimum size and groups them together for analysis later 
//purpose is to identify color coded objects through the webcam 

//util for ArrayList 
import java.util.*; 
import java.awt.Color; 
import java.io.*; 

public class Blobfind2 { 

    //width and height of image in pixels 
    private int width; 
    private int height; 
    //hash code for the color being searched for 
    private int colorCode; 
    //minimum blob size to be added 
    private int minPixels; 
    //image in form of array of hashcodes for each pixel 
    private int[] img; 
    //keeping track of which pixels have been added to a blob 
    private boolean[] added; 
    //keeping track of which pixels have been visited when looking for a new blob 
    private boolean[] visited; 

    //debugging variable 
    private int count; 

    public Blobfind2(int inwidth, int inheight, int inCCode, int inminPixels, int[] inimage) { 
    width = inwidth; 
    height = inheight; 
    colorCode = inCCode; 
    minPixels = inminPixels; 
    img = inimage; 
    count = 0; 
    }  

    //takes hashCodeof color, minimum pixel number, and an image in the form of integer array 
    public ArrayList findColor() { 
    //makes an arraylist of "blobs" 
    ArrayList bloblist = new ArrayList(); 
    //keep track of which pixels have been added to a blob 
    boolean[] added = new boolean[width * height]; 
    //checks through each pixel 
    for (int i = 0; i < img.length; i++) { 
     //if it matches and is not part of a blob, we run dfs to collect all the pixels in that blob 
     if ((img[i] == colorCode) && (added[i] == false)) { 
     //visited keeps track of which pixels in the blob have been visited 
     //refreshed each time a new blob is made 
     boolean[] visited = new boolean[width*height]; 
     Blob currBlob = new Blob(); 
     dfs(img, currBlob, i, Color.white.hashCode(), added, visited); 
     //adds the blob to the bloblist if it is of a certain size 
     if (currBlob.mass() >= minPixels) { 
      bloblist.add(currBlob);       
     } 
     } 
    } 
    return bloblist; 
    } 

    //recursive algorithm to find other members of a blob 
    public void dfs (int[] img, Blob blob, int currPixel, int colorCode, boolean[] added, boolean[] visited) { 
    //System.out.print(currPixel + " - " + count + " "); 
    count++; 
    //check current pixel, this only happens on the first pixel 
    if (visited[currPixel] == false) { 
     blob.add(img[currPixel]); 
     added[currPixel] = true; 
     visited[currPixel] = true; 
    } 
    //checks down pixel 
    if ((currPixel + width < height*width) && (visited[currPixel + width] == false)) { 
     if (img[currPixel + width] == colorCode) { 
     blob.add(img[currPixel + width]); 
     currPixel = currPixel + width; 
     added[currPixel] = true; 
     visited[currPixel] = true; 
     dfs(img, blob, currPixel, colorCode, added, visited); 
     } 
    } 
    //checks up pixel 
    if ((currPixel - width > 0) && (visited[currPixel - width] == false)) { 
     if (img[currPixel - width] == colorCode) { 
     blob.add(img[currPixel - width]); 
     currPixel = currPixel - width; 
     added[currPixel] = true; 
     visited[currPixel] = true; 
     dfs (img, blob, currPixel, colorCode, added, visited); 
     } 
    } 
    //checks right pixel 
    if ((currPixel + 1 < width * height) && (visited[currPixel + 1] == false) && (((currPixel + 1) % width) != 0)) { 
     if (img[currPixel + 1] == colorCode) { 
     blob.add(img[currPixel + 1]); 
     currPixel = currPixel + 1; 
     added[currPixel] = true; 
     visited[currPixel] = true; 
     dfs(img, blob, currPixel, colorCode, added, visited); 
     } 
    } 
    //checks left pixel 
    if ((currPixel - 1 > 0) && (visited[currPixel - 1] == false) && (((currPixel - 1) % width) != width - 1)) { 
     if (img[currPixel - 1] == colorCode) { 
     blob.add(img[currPixel - 1]); 
     currPixel = currPixel - 1; 
     added[currPixel] = true; 
     visited[currPixel] = true; 
     dfs(img, blob, currPixel, colorCode, added, visited); 
     } 
    } 
    return; 
    } 

    //test case, makes a new image thats half black and half white 
    //should only return one blob of size width*height/2 
    public static void main(String[] args) { 
    int width = 320; 
    int height = 240; 
    //builds the image 
    int[] img = new int[width * height]; 
    for (int i = 0; i < img.length; i++) { 
    if (i < img.length/4) { 
     img[i] = Color.white.hashCode(); 
    } else { 
     img[i] = Color.black.hashCode(); 
    } 
    } 

    //runs blobfind 
    Blobfind2 bf = new Blobfind2(width, height, Color.white.hashCode(), 1, img); 
    ArrayList bloblist = bf.findColor(); 
    System.out.println(bloblist.size()); 
    //need to typecast things coming out of arraylists 
    Blob firstblob = (Blob)bloblist.get(0); 
    System.out.println(firstblob.mass()); 
    } 

private class Blob { 
    private ArrayList pixels = new ArrayList(); 
    private Blob() { 
    } 
    private int mass() { 
    return pixels.size(); 
    } 
    private void add(int i) { 
    pixels.add(i); 
    } 
    private ArrayList getBlob() { 
    return pixels; 
    } 
} 

} 

Answer 1

堆棧溢出錯誤無關，與是否使用List，或Map，或任何其他特定的數據結構。這些結構被分配在堆上。你看到你的堆棧溢出錯誤，因爲你進行遞歸函數調用。每個遞歸函數調用都會在堆棧中分配內存。你可以增加你的-Xss值(e.g java -Xss8m HelloWorld)或者你可以重寫你的算法是非遞歸的（假設你的算法是正確的）。

Answer 2

這看起來非常類似於flood-fill算法。遞歸實現可能會導致堆棧（例如，進行太多的遞歸調用）出現大塊，這是因爲您必須爲每個像素探索4個鄰居。最壞的情況是一個圖像都在同一個blob！

我會嘗試使堆棧顯式。您想要避免遞歸，並使用簡單的基於循環的方法。

public void dfs() { 
    Stack<Pixel> pixels = new Stack<Pixel>(); 
    pixels.push(currentPixel); 

    while (!pixels.isEmpty()) { 
     Pixel x = pixels.pop(); 

     // Do whatever processing on this pixel 
     Pixel upPixel = getUpPixel(); 
     if (upPixel == colorCode) { 
      pixels.push(upPixel); 
     } 

     // And so on 
    } 

}