Thực hiện Flood Fill

Question

Đây là triển khai C# của tôi về thuật toán lấp đầy dựa trên stack (dựa trên định nghĩa của wikipedia). Trước đó trong khi viết mã, tôi chỉ muốn thấy nó hoạt động. Và nó đã làm. Sau đó, tôi muốn biết số lượng pixel thực sự là được điền. Vì vậy, trong mã của tôi, tôi đã thay đổi kiểu trả về thành int và trả lại biến số "ctr". Nhưng sau đó ctr hóa ra là xấp xỉ gấp đôi số pixel thực tế (tôi đã thực hiện một chức năng riêng biệt với mục đích duy nhất là đếm các pixel đó - chỉ để biết chắc chắn).

Bất kỳ ai có thể khai sáng về cách thức và lý do biến số "ctr" được tăng gấp đôi số tiền phải có?

* Pixel lớp chỉ đóng vai trò là vùng chứa cho các giá trị x, y và màu của pixel từ bitmap.

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor) 
{ 
    Bitmap result = new Bitmap(image.Width, image.Height); 
    Stack<Pixel> pixels = new Stack<Pixel>(); 
    Color oldColor = image.GetPixel(x, y); 
    int ctr = 0; 

    pixels.Push(new Pixel(x, y, oldColor)); 

    while (pixels.Count > 0) 
    { 
     Pixel popped = pixels.Pop(); 

     if (popped.color == oldColor) 
     { 
      ctr++; 
      result.SetPixel(popped.x, popped.y, newColor); 

      pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y)); 
      pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y)); 
      pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1)); 
      pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1)); 
     } 
    } 

    return result; 
} 

Answer 1

Bạn làm kiểm tra màu sắc của điểm ảnh ở đây:

if (popped.color == oldColor) 

Nhưng popped.color có thể (và apperently là trong 50% các trường hợp) lỗi thời. Bởi vì bạn không kiểm tra trùng lặp khi chèn pixel vào ngăn xếp của mình, bạn sẽ có bản sao. Khi popping những bản sao này, thuộc tính màu sắc sẽ được lưu một thời gian dài trước đây.

Có lẽ nó được rõ ràng hơn với một bản vẽ:

Như một ví dụ tôi mất một bitmap với 9 pixel. Trên ô đầu tiên bạn có đánh số các điểm ảnh, và ở bên phải bạn có ngăn xếp của bạn.

Bạn bắt đầu với pixel không có 5. và đẩy pixel 2, 4, 6 và 8 lên ngăn xếp. Sau đó, bạn lấy điểm ảnh 2 tắt và đẩy 1 và 3. Trong bước tiếp theo bạn bật 1 và đẩy 2 và 4 (một lần nữa!). Sau đó, bạn có thể mất 2 và nhận ra nó đã nhận được màu sắc mới khi nó được đẩy. (Một chút trễ, nhưng tốt hơn muộn hơn không bao giờ) tuy nhiên: pixel không. 4 có hai lần và đã nhớ màu cũ hai lần. Vì vậy, bạn lấy điểm ảnh số 4 và tô màu nó.

Một số bước sau bạn đã điền hình ảnh và vẫn còn một số mục trên ngăn xếp của bạn. Bởi vì giá trị màu cũ vẫn được lưu trữ bên trong các mục này, chúng được tính lại.

Mặc dù tôi có thể có thứ tự sai trong ngăn xếp, điểm vẫn hợp lệ.

Giải pháp cho vấn đề của bạn: Nhanh chóng và bẩn (vì nó nó vẫn không hiệu quả)

if (image.GetPixel(popped.x, popped.y) == oldColor) 

nó đếm pixel chỉ khi màu hiện nay là sai, không phải là màu nhớ.

Được đề xuất: Kiểm tra các điểm ảnh của bạn xem chúng có cần tô màu hay không trước khi đẩy chúng vào ngăn xếp.

Answer 2

Nếu tất cả Pixel đều giữ màu được truyền cho hàm tạo, nó sẽ không cập nhật màu sau khi lấp đầy pixel, do đó có thể tăng ctr nhiều lần trên mỗi pixel.

Nếu bạn thay đổi Pixel để đưa con trỏ đến hình ảnh trong hàm dựng của nó, bạn có thể đọc lại màu (ví dụ: làm cho màu trở thành thuộc tính đọc màu hiện tại) hoặc theo dõi tọa độ đã điền và không đẩy những người đó lần thứ hai.

[Chỉnh sửa]

Trong trường hợp không rõ ràng từ câu trả lời được chấp nhận, GetPixel trả về màu - một loại giá trị. Hãy suy nghĩ về nó như là một int mã hóa giá trị RGB của điểm ảnh tại thời điểm đó.

Nếu bạn muốn thực hiện điền nhanh, hãy tra cứu ví dụ Graphics.FloodFill.

Nếu bạn đang học mục đích, tôi khuyên bạn nên sao chép dữ liệu hình ảnh của bạn vào một mảng để xử lý và quay lại - hầu hết các thuật toán hình ảnh cổ điển không vui lắm khi sử dụng GetPixel().