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?
11
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.
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.