1

I am trying to simulate a matlab function "imfill" for flood filling a binary image (2D matrix of 1's and zeros).

I want to specify a starting point in the matrix, and flood fill like a 4 connected version of imfill would do.

Does this already exist out there somewhere in the C++ world? If not, what would be the most efficient way to implement this?

Derek
  • 11,715
  • 32
  • 127
  • 228
  • 1
    Look into "Breadth first search": http://stackoverflow.com/questions/2505431/breadth-first-search-and-depth-first-search – Pablo May 09 '11 at 19:31

4 Answers4

4

If you want to do image processing in C++, you must take a look into OpenCV (Open Source Computer Vision).

It's a great cross-platform library for image/video processing and it has what you are looking for. Check this question:

Fill the holes in OpenCV

Community
  • 1
  • 1
karlphillip
  • 92,053
  • 36
  • 243
  • 426
4

If your images are just 2D arrays of 1s and 0s, then I don't think you need an actual graphics library.

When I've filled in simple grids in the past, I just used the STL queue to store a list of points, and then worked through those. The queue would start with the initial point, then I'd test the adjacent points. If the adjacent points need to be included in the 'flood', then add those to the queue. Kind of like this:

// using this data structure
struct Point {
  int x;
  int y;
};

// 
void fillGrid(Point orig, byte** grid, int width, int height) {
  std::queue<Point> q;
  q.push(orig);

  // the main flood loop
  while(!q.empty()) {
    Point pnt = q.front();
    q.pop();

    // grab adjacent points
    Point adj[4];
    adj[0].x = pnt.x;   adj[0].y = pnt.y-1;   // up
    adj[1].x = pnt.x+1; adj[1].y = pnt.y;     // right
    adj[2].x = pnt.x;   adj[2].y = pnt.y+1;   // down
    adj[3].x = pnt.x-1; adj[3].y = pnt.y;     // left

    for(int i = 0; i < 4; i++) {
      // don't forget boundaries!
      if(adj[i].x < 0 || adj[i].x >= width ||
         adj[i].y < 0 || adj[i].y >= height)
        continue;

      // if adjacent point meets some criteria, then set
      // its value and include it in the queue
      if(includePoint(adj[i], grid)) {
        setPoint(adj[i], grid);
        q.push(adj[i]);
      }
    }
  }
}
Steve Blackwell
  • 5,904
  • 32
  • 49
  • Ended up using something along these lines. Think the other stuff was going to be overkill. Thanks for the tips! – Derek May 10 '11 at 17:49
  • 1
    Side note: If you're optimizing for speed, the boundary check inside the for loop can be quite a killer. It's quite a bit faster (and quite a bit more code) to handle the image interior without this check (as it will always evaluate to `false` inside) and then perform the check on the outside. There are various ways to avoid it, but they all involve more code. – Chris A. May 23 '11 at 12:30
1

See the code examples on this page ('QuickFill: An efficient flood fill algorithm')

In the first few code examples, a pixel is checked whether has the the fill (or border) color and the function calls itself recursively for all four (or eight) neighbouring pixels (actually, I claim that the first few examples are slightly wrong because the first recursive call should rather be a call to a function setting the new pixel instead of calling the function itself again with the very same parameters).

The next few examples describe the a recursive scan line method, which first fills a (horizontal) line as far as possible before going to adjacent lines (the line above and below), thus visiting each pixel less often.

Finally, it proposes QuickFill which to me looks like an optimized variant of the scan line method.

Andre Holzner
  • 18,333
  • 6
  • 54
  • 63
  • 1
    Great link, but a summary would be nice, especially if it gives some key terms to search for if the link ever breaks. – Mark Ransom May 09 '11 at 19:59
0

Aforge Library has the following function

AForge.Imaging.Filters.FillHoles(...)

It does the same thing as imfill in Matlab.

Umair
  • 111
  • 1
  • 10