3

I have an image (an array of 1000 x 1000 pixels) of 1s and 0s. I was asked to do edge detection, so I wrote this program in C to traverse the figure. My idea was to convert every pixel surrounded by like pixels to white (1) and every pixel surrounded by at least one unlike pixel to black (0). And I used recursion.

This worked when the figure was small but I'm getting a "stack overflow" message with larger figures.

Is there some systematic technique to convert this to a "non-recursive" program - simulating recursion using a user defined stack?

TV Mohini
  • 181
  • 3
  • possible duplicate of [Can and do compilers convert recursive logic to equivalent non-recursive logic?](http://programmers.stackexchange.com/questions/202983/can-and-do-compilers-convert-recursive-logic-to-equivalent-non-recursive-logic) – gnat Feb 18 '15 at 16:43
  • @gnat: He's not asking how compilers work. – Robert Harvey Feb 18 '15 at 16:46
  • 1
    @gnat Seems more likely to be a duplicate of http://programmers.stackexchange.com/questions/252591/how-to-convert-this-recursive-problem-to-iterative-line-simplification-algorith – Doval Feb 18 '15 at 16:47
  • @RobertHarvey did you check answers in that question? – gnat Feb 18 '15 at 16:48
  • 1
    @gnat: Yes, but the *question* is not a duplicate. If you want to direct him to an answer that is relevant to his question, then by all means do so, but we don't close questions as duplicates of answers unless the question is a canonical one. – Robert Harvey Feb 18 '15 at 16:49
  • yes I did - but I don't want the compiler to do this for me, I'd like to do it myself (i.e., my program should be written that way). BTW I'm not a he but a she. – TV Mohini Feb 18 '15 at 16:50
  • @TVMohini: "He" is used in its generic sense here. No offense is intended, and people can put anything they want in their identicons, so we have no idea if that's your picture or not. See also http://michaelmaslin.com/inkspill/wp-content/uploads/2013/07/dog-on-the-internet-by-peter-steiner.jpg – Robert Harvey Feb 18 '15 at 16:52
  • @Doval: That one seems too specific. If we haven't answered a question like this in the generic sense on Programmers, now would be a good time. – Robert Harvey Feb 18 '15 at 16:53
  • 2
    @TVMohini the suggestion that gnat was looking at is that if you write your existing recursive algorithim in a way that is tail call optimizable, it won't take up any stack space. The other approach is the more generic "rewrite it with a while loop" which Doval's link provides. Without specifics not much more can be said than that. *With* specifics (the code), the question becomes one more suited to Stack Overflow. (And you might also want to look at [What methods are there to avoid a stack overflow in a recursive algorithm?](http://programmers.stackexchange.com/q/194646/40980)). –  Feb 18 '15 at 16:54
  • @RobertHarvey - no offense taken and love your cartoon :-) – TV Mohini Feb 18 '15 at 16:59
  • 1
    Depending on your situation, a quick fix might be to increase your stack size. (For linux, see http://stackoverflow.com/questions/2279052/increase-stack-size-in-linux-with-setrlimit) This might be useful if you don't need a general solution, just a quick fix for particular data. – Gort the Robot Feb 18 '15 at 19:19

2 Answers2

4

What you are doing is a variation on blob coloring or 8-way connectivity.

The traditional solution for this is recursive, and it can get into trouble with large blobs.

Years ago, a very brilliant young coworker came up with a way to do nonrecursive 8-way connectivity. It used two loops, one over the rows, one of the columns in each row, and a loop body that looked at the four "successor" pixels (East, Southeast, South, Southwest).

There was one catch and one minor gotcha.

The catch was that you had to maintain an auxiliary table of "equivalent colors", to handle the cases where two blobs that you thought were separate turned out to be connected. (Imagine a large letter X. Until you see the center of the X, you could be looking at a backslash and a slash.)

The minor gotcha was that the loop body had to be written in C macros, because subroutine call overhead was eating it alive.

This should give you something to think about.

John R. Strohm
  • 18,043
  • 5
  • 46
  • 56
3

Read about call stack, tail calls, continuations, and continuation-passing style (CPS).

Then read about CPS conversion (or CPS transform). It a s systematic way to tranform a deep call stack into heap allocated structure and control.

There is no magic bullet here, CPS-conversion is just allocating the equivalent of call frames in the heap.

Read also Appel's book Compiling with Continuations and his old paper Garbage Collection can be Faster than Stack Allocation

In practical terms, you might be able to transform your naive C code by allocating most of the data in the heap.

Another way of thinking at that is to "invent" a specialized byte code (for your algorithm) and implement its stack based interpreter.

See also Gabriel Kerneis' Continuation Based C

The (Deutch-) Schorr Waite graph marking algorithm might also be inspirational.

Basile Starynkevitch
  • 32,434
  • 6
  • 84
  • 125