Region Growing Algorithm

Question

Hey everyone. I'm really struggling to figure out the logic with this one and was hoping you could help me out. Before I continue I just want to let you know that I am amateur programmer and a beginner at that, with no formal Computer Science training of any sort, so please bear with me. :D Also, I'm using Python, but I could use Java or something similar.

Anywho, I am looking to implement a Region Growing for use in a rudimentary Drawbot. Here is an article on region growing: http://en.wikipedia.org/wiki/Region_growing

The way I envision it, the image the draw is based upon will meet the following criteria:

• The image will be at most 3x3 inches in size at an arbitrary Color Depth

• The image will be a black continuous shape on a white background

• The shape can be located anywhere on the background.

I've considered the following solutions to this problem. While some work to an extent, each has some considerable flaws in either their performance or feasibility (at least they don't seem feasible to me). Furthermore, because this is a Drawbot, this needs to be done with a single continuous line. This doesn't mean however that I can't backtrack, it only eliminates the possibility of multiple starting points (seeds).

Considered Approaches:

Random Walk:

Solving this problem with a random walk was my first instinct. A random walk program accomplishing this would, I imagine, look something like this:

pseudo python...

Cells To Visit = Number of Black Cells
Cells Visited = 0
MarkColor = red
While Cells Visited < Cells To Visit:
    if currentcell is black:
        Mark Current Cell As Visited #change pixel to red
        Cells Visited +=1
    neighbors = Get_Adjacent_Cells() #returns cells either black or red
    next cell = random.choose(neighbors)
    currentCell = next cell

While I suppose this is feasible, it seems to me to be highly ineffective and doesn't guarantee good results, but in the interest of actually getting something done I may end up trying this... Is my logic in the pseudocode even vaguely correct?

Sweeping Pattern:

This method to me seemed to be the most trivial to implement. My idea here is that I could choose a starting point at one extreme of the shape (e.g. the lowest most left point). From there it would draw to the right, moving only on the x axis until it hit a white pixel. From here it would move up one pixel on the y axis, and then move left on the x axis until it reached a white pixel. If the pixel directly above it happend to be white, backtrack on the x axis until it finds a black pixel above it.

This method upon further inspection has some major short comings. When faced with a shape such as this:

The result will look like this:

And even if I were to tell it to start sweeping down after awhile, the middle leg would still be overlooked.

4/8 Connected Neighborhood:

http://en.wikipedia.org/wiki/8-connected_neighborhood

This method appears to me to be the most powerful and effective, but at this point I can't figure it out fully, nor can I think of how I would implement it without potentially leaving some overlooked areas

At every cell I would look at the neighboring black cells, devise some method for ranking which one I should visit first, visit all of them, and repeat the process until all cells are covered.

The problems I could see here is first of all dealing with the data structure necessary to accomplish this, and also merely figuring out the logic behind it.

---

Those are the best solutions I've been able to think of. Thank you for taking the time to read this, I realize it is long, but I thought that I should make it as explicit as possible. Any and all suggestions will be greatly appreciated... Thanks!

Edit:

I also looked into maze generating and solving algorithms, but wasn't sure how to implement that here. My understanding of the maze solving algorithms is that they rely on the passages of the maze to be of equal width. I could of course be wrong about that.

Solution 1

Here's a really nice little screencast on writing a recursive maze solver: http://thinkcode.tv/catalog/amazing-python/

I think it might give you some ideas for the problem you are trying to solve.

Also, here's a little recursive maze solving script that I wrote after watching the screencast http://pastie.org/1854582. Equal width passages are not necessary, the only things that are necessary are open space, walls, and some kind of an ending condition, in this case, finding the end of the maze.

If you don't want to go recursive, the other thing you can do is use a "backtracking" method. You can see a little example of it being used in the random generation of mazes on this page: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap (First example on the page).

Is this sounding relevant? If it is, let me know if you want me to explain anything in more detail.

Edit:

This seems like a really good discussion on doing flood fills in python http://www.daniweb.com/software-development/python/threads/148874

Solution 2

Basic region growing, in pseudocode looks something like:

seed_point // starting point
visited // boolean array/matrix, same size as image
point_queue // empty queue

point_queue.enqueue( seed_point )
visited( seed_point ) = true

while( point_queue is not empty ) {
    this_point = point_queue.dequeue()
    for each neighbour of this_point {
        if not visited( neighbour ) and neighbour is black/red/whatever
            point_queue.enqueue( neighbour )
            visited( neighbour ) = true
    }
}

// we are done. the "visited" matrix tells
// us which pixels are in the region

I don't understand where the ranking that you've mentioned comes into it though. Am I missing something?

Solution 3

I'm confused by the very long question.

Are you sure you aren't just trying to do a flood fill?

Solution 4

A simple technique that can help with some maze solving problems, of keeping one hand on the wall, might help.

Note however that if you chose a random starting point, you might chose a point that whichever way you travel from there, you block off a portion. i.e. if you were to start in the middle of an hour-glass shape, you would only be able to fill in one half.

View more solutions

Comments

[danem]

I had been planning on specifying a particular point from which to start, this is already difficult for me and I can't imagine having to deal with all possible starting points... D: To see if I understand you solution, would the method you are suggesting end up with a path that would run next to the outer most edge and therefore end up spiraling in on itself? If that was the case wouldn't there still be the possibility of blocking off a portion as in the case of an hour glass? On the note of maze solving, I had considered that, but couldn't think of how I could implement that here...

[danem]

Are you referring to the ranking I mentioned in the 8 connected cell methods? If so, what I meant was that, based on the assumption that for any eight given neighbors, there is an optimal cell to visit first. Thus, I figure that I need to find which ones are the best to visit and how to rank them.... Or I could be totally wrong haha Also, while trying to understand your example, would the visited array have bool values corresponding with their coordinates? Furthermore, would this solution visit each point sequentially? Thanks for the help. Your example has granted me some insights!

[YXD]

Yes, the visited array would have bool values corresponding to the coordinates. I'll check over the algorithm as it might not be 100% right but the idea is there :) Yes re: ranking. How can the order matter if you need to find the whole black area? Surely any order is as good as any other (hence am I missing something)? To get a feel for how the order works here (breadth first), you can grab an empty crossword and try and perform the algorithm by hand starting at some seed point.

[danem]

Oh thanks a lot. I was initially considering a back tracking method, as I saw a brief description on Wikipedia, but the data structure seemed rather daunting as I am a newbie to programming. I will definitely take a look at those.

[danem]

On a slightly irrelevant note, the demonstration of backtracking in the third link is totally awesome! I'll be spending awhile trying to learn from all this...

[danem]

Ok sure thing. I've got a quite a bit of information to go through at the moment. Ill let you know how I'm doing after I study all the given answers. Thanks so much!

[Stephen Denne]

Yes, spiralling in, filling in the area. I was trying to say that there will always be the possibility that you cannot create a single non-branching path to fill in an arbitrary area.

[Rohan Desai]

This is exactly what Mr E's answer does. I'd just like to point out the very comprehensive Wikipedia article for this problem.

[Stephen Denne]

A particular kind of flood fill - whereby each newly set pixel is adjacent to the previously set pixel.

[so12311]

I would suggest that you try this wall-following method, but with one addition: test if by placing the next pixel you are moving into a 'neck' ie walls on both left and right. If so, reverse direction and follow the wall on the other side. Do this until there is no place to go except through the neck (walls on left, right and behind). This I think will work for the hourglass shape.

[danem]

Just an update on my progress with this.... I've successfully implemented a recursive backtracking method and i works fabulously, but with some severe drawbacks... Those being the fact that, due to the way the algorithm works, each individual cell adds another level of recursion. So when dealing with a 1000x1000 px image...... I'm gonna try to implement your solution

[danem]

Is there a way to deal with the mass level of recursion? While I implemented it correctly (i think...) due to the fact that I'm not making mazes, and tracing images, the nature of the algorithm is such that it adds new level with every pixel. So when dealing with a 400x400 pixel image the recursion limit is hit pretty quickly with the more information dense pictures. Here is my code if you want to take look pastebin.com/Uqf20f4 Thanks for the help!

[Acorn]

I've added a link to a useful looking discussion on implementing flood fills in Python. Also the pastebin link is broken.

[danem]

oops... Hopefully this link works... pastebin.com/Uqf20f4u And I'll be sure to check it out

[YXD]

Yes a recursive method will definitely limit the region size. Good luck with the implementation.