Click here to Skip to main content
13,146,739 members (91,575 online)
Click here to Skip to main content
Add your own
alternative version

Stats

3.9K views
Posted 15 Sep 2016

Flattening the Recursive Call in the Canny Edge Detector Algorithm

, 15 Sep 2016
Rate this:
Please Sign up or sign in to vote.
This tutorial describes how to convert the recursive method call in said algorithm into a flat loop call, to save memory in restricted environments.

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

discompsys
United Kingdom United Kingdom
This member doesn't quite have enough reputation to be able to display their biography and homepage.

You may also be interested in...

Pro
Pro

Comments and Discussions

 
Questionwhere's the code ? Pin
BillWoodruff17-Sep-16 9:29
mentorBillWoodruff17-Sep-16 9:29 
AnswerRe: where's the code ? Pin
discompsys18-Sep-16 23:51
memberdiscompsys18-Sep-16 23:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170915.1 | Last Updated 15 Sep 2016
Article Copyright 2016 by discompsys
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid