爲什麼這個洪水填充算法不起作用？

對於這個問題：Is there a proper algorithm for detecting the background color of a figure?，我需要創建一個flood-fill algorithm，以便能夠以相同顏色的組分隔我的所有像素。爲什麼這個洪水填充算法不起作用？

我做了遞歸，但它給了我一個堆棧溢出錯誤。所以我不得不選擇在這裏找到了迭代，基於隊列算法：http://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations

首先，我開始對所有矩陣元素搜索（元素作爲Pixel類的實例）。

private PixelGroup[] generatePixelGroupsFromMatrix(Pixel[][] matrix) { 
    PixelGroup[] tempGroups = new PixelGroups[9999999]; // Nevermind the 9999999.... 
    int groupsFound = 0; 
    Pixel pixel; 

    for (int y = 0; y < matrix.length; ++y) { 
     for (int x = 0; x < matrix[0].length; ++x) { 
      pixel = matrix[y][x]; 
      if (!pixel.evaluated) { 
       // This pixel has never been evaluated 
       // Therefore, it belongs to a new group 
       // First, we make a new group 
       PixelGroup newGroup = new PixelGroup(); 
       // Begin search for connected pixels with the same color. All pixels found will belong to this new group. 
       findPixelsConnectedWith(pixel,newGroup); 
       tempGroups[groupsFound] = newGroup; 
       ++groupsFound; 
      } 
     } 
    } 

    PixelGroup[] result = new PixelGroup[groupsFound]; 
    for (int i = 0; i < groupsFound; ++i) { 
     result[i] = tempGroups[i]; 
    } 

    return result; 
}

所以，Pixel具有下列值：X，Y，評價（布爾值）和顏色（整數）。然後，PixelGroup只是一個能夠保存像素的類（它的工作原理）。

這是給我找麻煩的方法：

private void findPixelsConnectedWith(Pixel pixel, GroupOfPixels group) { 
    QueueOfPixels queue = new QueueOfPixels(); 
    queue.add(pixel); 

    Pixel currentPixel; 
    int x,y; 
    Pixel neighbor; 
    while((currentPixel = queue.nextPixel()) != null) { 
     if (currentPixel.color == pixel.color && !currentPixel.evaluated) { 
      // This pixel has the required color, and has not been evaluated. It meets our needs. 
      // Add to group. 
      group.addPixel(currentPixel); 
      // Flag it as evaluated. So in the future, it will be ignored. 
      currentPixel.evaluated = true; 
      // Evaluate all 8 possible directions to find neighbor pixels 
      int[] xDirections = {0,1,1,1,0,-1,-1,-1}; 
      int[] yDirections = {-1,-1,0,1,1,1,0,-1}; 
      for (int i = 0; i < 8; ++i) { 
       x = xDirections[i]; 
       y = yDirections[i]; 
       if (pixelExists(currentPixel.y + y,currentPixel.x + x)) { 
        // There exists a pixel in this direction! 
        neighbor = getPixel(currentPixel.y + y,currentPixel.x + x); 
        queue.add(neighbor); 
       } 
      } 
     } 
    } 

}

如果你很好奇，這是我QueueOfPixels類。我不得不用自己的載體（學校任務要求）：https://codereview.stackexchange.com/questions/17823/vector-based-flood-fill-algorithm-queue-class（據我所知，它只是起作用）。

有什麼問題嗎？

好吧，我有這個形象，這是5×2像素（你會需要大量的放大才能看到）測試此：http://i.stack.imgur.com/xV0Lf.gif - 第一行只有黑色像素，而且他們第二白色。該方案告訴我，它已經找到6像素組（當它應該是隻有2個！）

有什麼我試着調試問題？

嗯，首先，調用findPixelsConnectedWith之前，我把這個行：

System.out.println("The pixel (" + x + "," + y + ") has not been evaluated. Evaluating now.");

這是結果：

The pixel (0,0) has not been evaluated. Evaluating now. 
The pixel (1,0) has not been evaluated. Evaluating now. 
The pixel (2,0) has not been evaluated. Evaluating now. 
The pixel (3,0) has not been evaluated. Evaluating now. 
The pixel (4,0) has not been evaluated. Evaluating now. 
The pixel (0,1) has not been evaluated. Evaluating now.

所以，你可以看到，好像代碼無法使用第一行（黑色像素），因爲它認爲該行中的每個像素都沒有被評估（我期望它說（0,0）未被評估和完成）。但是當它開始與第二行一起工作時，它似乎按預期工作（find（0,1），然後結束）。

但我仍然無法找出發生了什麼。任何想法？

編輯： 我getPixel和pixelExists功能：

private boolean pixelExists(int y, int x) { 
    return (y > 0 && y < pixelMatrix.length) && (x > 0 && x < pixelMatrix[0].length); 
} 

private Pixel getPixel(int y, int x) { 
    return pixelMatrix[y][x]; 
}

來源

2012-10-23 Voldemort

您應該使用的java.util.Vector PixelGroup代替[]。你在幾個地方說過「矢量」，我認爲你的意思是「陣列」。 PixelGroup []是一個數組，而不是一個向量。 – walrii

使用y，x而不是x，y調用pixelExists（）和getPixel（）方法是很奇怪的。你沒有向我們展示代碼。是y，x有意？並且getPixel引用傳遞給generatePixelGroupsFromMatrix（）的相同矩陣[] []？每次添加到隊列中時都要打印一份。 – walrii

@walrii：啊，對不起。那麼，在這種情況下，我的意思是說數組而不是矢量。 – Voldemort

Your pixelExists方法應該使用y> = 0和x> = 0而不是y> 0和x> 0。

private boolean pixelExists(int y, int x) { 
    return (y >= 0 && y < pixelMatrix.length) && (x >= 0 && x < pixelMatrix[0].length); 
}

這可能不是唯一的問題，但它肯定會阻止你得到正確的答案。

來源

2012-10-23 01:31:13 walrii

它..工作。那麼，到底是什麼...... – Voldemort

也許pixelExists方法具有「Y> 0」的一部分，而它應該具有「Y> = 0」？

來源

2012-10-23 00:46:41

爲什麼這個洪水填充算法不起作用？

回答

相關問題