Flattening the Recursive Call in the Canny Edge Detector Algorithm

Introduction

This tutorial describes one situation where it was necessary to flatten a recursive method call, to remove the program call stack and allow it to be run in a more restricted mobile environment. The problem is that the recursive call can extend the call stack to beyond what a restricted or shared memory might allow. If this can be flattened so that only one level of method invocation is required, then the memory requirements are for a single loop only and it can be run when much less ram is available. A recursive structure is similar to a stack data structure, where the last element, or method call placed on the stack would be the first one to give its result, or be popped off the stack, for further processing.

Background

The Canny Edge Detector algorithm is very good for finding the edges of objects in an image processing application and was developed by John F. Canny in 1986. The version used here was written by Tom Gibara. As described on Wikipedia, edge detection includes a variety of mathematical methods that aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities. The points at which image brightness changes sharply are typically organized into a set of curved line segments termed edges.

Using the Code

Two methods of the original code needed to be altered to flatten the calling structure, where this section describes how that was done. An edge in an image may point in a variety of directions, so the Canny algorithm uses four filters to detect horizontal, vertical and diagonal edges in the blurred image. As part of this process, the follow method is invoked from the performHysteresis method. This is a recursive call, where follow invokes follow again, with each set of parameters particular to the current recursive state. The following code segments are from the original Java code implementation:

private void performHysteresis(int low, int high) {
    ...
    Arrays.fill(data, 0);

    int offset = 0;
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (data[offset] == 0 && magnitude[offset] >= high) {
                follow(x, y, offset, low);
            }
            offset++;
        }
    }
}

private void follow(int x1, int y1, int i1, int threshold) 
{
    int x0, x2, y0, y2;
    ...
    
    for (int x = x0; x <= x2; x++) 
    {
        for (int y = y0; y <= y2; y++) 
        {            
            ...
            
            follow(x, y, i2, threshold);
            return;
        }
    }
}

The input parameters for the next recursive call depend on the current instance and so it is difficult to set them outside of the recursive process. Therefore to flatten the process, the parameter values need to be stored in a global structure and then retrieved when appropriate. As a recursive structure can be translated over to a stack structure, the parameter list can be stored on a stack data structure. For this particular algorithm, only 3 parameters needed to be stored, as follows:

private class HystStruct
{
    public int x1, y1, i1;

    public HystStruct()
    {
        ...
    }
}

The recursive structure can then be replaced with a single level loop, where each new instance retrieves its parameter list from the stack data structure. The performHysteresis and follow methods can be re-written as follows:

private void performHysteresis(int low, int high)
{
    HystStruct hystStruct;
    Stack<HystStruct> stack;

    Arrays.fill(data, 0);
    stack = new Stack<HystStruct>();

    int offset = 0;
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if ((x >= cropX) && (x <= (cropX + cropWidth)) 
            && (y >= cropY) && (y <= (cropY + cropHeight)))
            {
                if (data[offset] == 0 && magnitude[offset] >= high)
                {
                    follow(x, y, offset, low, stack);
                }
            }
            else
            {
                magnitude[offset] = 0;
            }
            offset++;

            while (!stack.isEmpty())
            {
                hystStruct = stack.pop();
                follow(hystStruct.x1, hystStruct.y1, hystStruct.i1, low, stack);
            }
        }
    }
}

private void follow(int x1, int y1, int i1, int threshold, Stack<HystStruct> stack)
{
    HystStruct hystStruct;

    int x0 = x1 == 0 ? x1 : x1 - 1;
    int x2 = x1 == width - 1 ? x1 : x1 + 1;
    int y0 = y1 == 0 ? y1 : y1 - 1;
    int y2 = y1 == height - 1 ? y1 : y1 + 1;

    data[i1] = magnitude[i1];
    for (int x = x0; x <= x2; x++)
    {
        for (int y = y0; y <= y2; y++)
        {
            int i2 = x + y * width;
            if ((x >= cropX) && (x <= (cropX + cropWidth)) 
            && (y >= cropY) && (y <= (cropY + cropHeight)))
            {
                if ((y != y1 || x != x1)
                        && data[i2] == 0
                        && magnitude[i2] >= threshold)
                {
                    hystStruct = new HystStruct();
                    hystStruct.x1 = x;
                    hystStruct.y1 = y;
                    hystStruct.i1 = i2;
                    stack.push(hystStruct);
                    return;
                }
            }
            else
            {
                magnitude[i2] = 0;
            }
        }
    }
}    

With the new code, when the follow method finds an appropriate point, it stores the result on the stack and returns, instead of building up the method call stack with another follow invocation. As strict ordering is maintained, the parameter values can be popped off the stack data structure and used to invoke the next follow method at any time. The parameter values are all independent of each other which is probably a requirement for the process.

Points of Interest

Also interestingly in this case, the stack data structure appears to be used for storing only 1 data object. When the process pushes a data object onto the stack, the next code part pops it off again. So it is essentially replicating the return of the current parameter list, to the parent method, exactly.

History

• Version 1.0