Code Optimization / Image Processing

Asked

Viewed 224 times

5

I’m doing a C-level college paper on image processing.
And I need to find an alternative to optimize a particular piece of code. Here:

/* Backward Rotina */
/* -------------------------------------------------------------------------------------------------------------------------------- */
        for (altura = img->altura - 2; altura >= 0; altura--)
        {
            for (largura = img->largura - 2; largura >= 0; largura--)
            {

                if (aux->dados[0][altura][largura] != 0)
                {
                    if (   aux->dados[0][altura + 1][largura + 1] != 0
                        && aux->dados[0][altura + 1][largura + 1] < aux->dados[0][altura][largura])
                    {
                        out->dados[0][altura][largura] = aux->dados[0][altura + 1][largura + 1];
                    }
                    else if (   aux->dados[0][altura + 1][largura] != 0
                             && aux->dados[0][altura + 1][largura] < aux->dados[0][altura][largura])
                    {
                        out->dados[0][altura][largura] = aux->dados[0][altura + 1][largura];
                    }
                    else if (   aux->dados[0][altura + 1][largura - 1] != 0
                             && aux->dados[0][altura + 1][largura - 1] < aux->dados[0][altura][largura])
                    {
                        out->dados[0][altura][largura] = aux->dados[0][altura + 1][largura - 1];
                    }
                    else if (   aux->dados[0][altura][largura + 1] != 0
                             && aux->dados[0][altura][largura + 1] < aux->dados[0][altura][largura])
                    {
                        out->dados[0][altura][largura] = aux->dados[0][altura][largura + 1];
                    }
                }
            }
        }
    }
/* ================================================================================================================================ */

Functioning

The function is in the algorithm multi-pass, scanning the image matrix checking the neighborhood. For step foward check the neighbors above and left by going index [1,1] < [X,Y], to the backward the right and lower neighbours going from [X-2,Y-2] > [0,0]. Ignoring the edges because they are unreliable.
Following image of exemplification: Multi-pass processo

What to do?

I need to find a way to optimize this immense nestled if/else, that according to the teacher there are better ways to do.
I’ve been plucking my hair for over two hours thinking of a solution, but so far I haven’t been able to come up with a solution that is more viable and at a lower computational cost, all routes lead me to nested if/else.

Edit

Foward routine result: Foward

After Foward performs the Backward Routine.

Result Backward Routine: Backward

c

  • To understand, the algorithm needs to put in out->dados[0][altura][largura] one of the neighbors to the "southwest", "south", "southeast" and "east" (assuming that the height grows to the "south" and the width grows to the "east"), the first that is less than the current value, looking in the order "southeast"->"south"->"southwest"->"east", provided that no value of these is zero. Am I right? What does zero mean?

  • Correct, the value zero means that that component is a background, and should be ignored. Anything that is non-zero is an image element that is interconnected, this change by a smaller value means that this point is interconnected and are the same component

4 answers

5

Follow another solution using a "static" mapping of neighbors' coordinates:

int masc[4][2] = { {1,1}, {1,0}, {1,-1}, {0,1} };

for( altura = img->altura - 2; altura >= 0; altura-- )
{
    for( largura = img->largura - 2; largura >= 0; largura-- )
    {
        if( aux->dados[0][altura][largura] != 0 )
        {
            for( i = 0; i < 4; i++ )
            {
                if( (aux->dados[0][altura + masc[i][0]][largura + masc[i][1]] != 0) &&
                    (aux->dados[0][altura + masc[i][0]][largura + masc[i][1]] < aux->dados[0][altura][largura]))
                {
                    out->dados[0][altura][largura] = aux->dados[0][altura + masc[i][0]][largura + masc[i][1]];
                    break;
                }
            }
        }
    }
}

4

Although I think my answer is correct, Lacobus is better, more concise and more efficient.

/* Backward Rotina */
/* -------------------------------------------------------------------------------------------------------------------------------- */
int[] vizinhos = int[4];
for (altura = img->altura - 2; altura >= 0; altura--)
{
    for (largura = img->largura - 2; largura >= 0; largura--)
    {
        vizinhos[0] = aux->dados[0][altura + 1][largura + 1];
        vizinhos[1] = aux->dados[0][altura + 1][largura];
        vizinhos[2] = aux->dados[0][altura + 1][largura - 1];
        vizinhos[3] = aux->dados[0][altura][largura + 1];

        for (int i = 0; i < 4; i++)
        {
            int valorVizinho = vizinhos[i];
            if (valorVizinho != 0 && valorVizinho < aux->dados[0][altura][largura])
            {
                aux->dados[0][altura][largura] = valorVizinho;
                break; // Eis o pulo do gato
            }
        }
    }
}
/* ================================================================================================================================ */

And yes, I know you may have to alloc, malloc, calloc to declare the vector vizinhos, and maybe even use pointer to access the positions. I just wanted to give the idea here. I’m more rusty in C than wreck hull.

If you make a reference to aux->dados[0], i.e.: point, something like:

int* ponto = &aux->dados[0];

...you can shorten the code even more, because instead of:

vizinhos[0] = aux->dados[0][altura + 1][largura + 1];

...you could write:

vizinhos[0] = ponto[altura + 1][largura + 1];

...Which makes it easier to read. Again, I may have missed the specific syntax of C, but this idea is valid in C and pretty much every language related to it.

p.s.: I admire everyone who has the courage to study signal processing. It’s not an easy area.

  • First, I thank you for the suggestion and time available to answer me. This idea also occurred to me, but taking into account the computational cost, allocating an array to each iteration and executing a new loop of repetition, even with stop criteria, ends up being more expensive for the machine. The attempt is to try to get ideas on how to optimize and decrease the cost, but everything is leading me to believe that there is no other way :/

  • I understand. If the intention is to actually brush bits, I’ll edit the answer to something more efficient.

  • One of the difficulties here is the fact that routine is very generic, there’s almost not much to do, but the teacher almost hit me when I said: "I didn’t find any way more suitable than this!" Saying he: "Yeah, get off your lazy ass and go think!"

  • That’s evil on your teacher’s part. By the way, if bit brushing is important, @Lacobus has just given what I believe is the best possible answer.

4

Okay, given the code snippet shown and the characteristics of the algorithm I was able to apprehend, there are some observations that you can make:

First, if you want to avoid the ifs nested, you can turn the first

if (aux->dados[0][altura][largura] != 0) {
    /* outros ifs... */
}

in

if (aux->dados[0][altura][largura] == 0) continue;
/* outros ifs... */

and ensure that the current pixel is not background.

Second, the idea of memoizing the current pixel and neighbors, suggested by Renan, is not bad: you do not need to allocate a new vector to each iteration, you can use the same and overwrite with the new data:

int pixel;
int vizinhos[4];
for (altura = img->altura - 2; altura >= 0; altura --) {
    for (largura = img->largura - 2; largura >= 0; largura --) {
        if ((pixel = aux->dados[0][altura][largura]) == 0) continue;

        vizinhos[0] = aux->dados[0][altura + 1][largura + 1];
        vizinhos[1] = aux->dados[0][altura + 1][largura];
        vizinhos[2] = aux->dados[0][altura + 1][largura - 1];
        vizinhos[3] = aux->dados[0][altura][largura + 1];

        for (int i = 0; i < 4; i ++) {
            if (vizinhos[i] < pixel) {
                out->dados[0][altura][largura] = vizinhos[i];
                break;
            }
        }
    }
}

Now, the possibly most important item is the fact that you are checking the neighbors whose coordinates you already swept. That normally means that the algorithm is made to be executed in-place, I mean, you don’t need a array as a result out separate from the array incoming aux. This saves you the space of an entire image - although temporally the algorithm continues O(height width).

So take a look at the algorithm to see if you can actually perform the in-place algorithm, and possibly you’ll get a good space gain and possibly much less Misses cache.

1


First of all I would like to thank you for your help, @Lacobus, @Renan and @Wtrmute.

After analyzing the suggestions given by all, using a little piece of each one I put together the code as follows:

    /* Backward Rotine */
    for (altura = img->altura - 2; altura > 0; altura--)
    {
        for (largura = img->largura - 2; largura > 0; largura--)
        {

            if ((pixel = out->dados[0][altura][largura]) == 0) continue;

            vizinho[0] = out->dados[0][altura + 1][largura + 1];
            vizinho[1] = out->dados[0][altura + 1][largura];
            vizinho[2] = out->dados[0][altura + 1][largura - 1];
            vizinho[3] = out->dados[0][altura][largura + 1];

            for(i = 0; i < 4; i++)
            {
                if(vizinho[i] < pixel && vizinho[i] != 0)
                {
                    out->dados[0][altura][largura] = vizinho[i];
                    break;
                }
            }
        }
    }

Personal thank you!
Using the code in this way I noticed a considerable performance gain, decreasing in almost 3 seconds the execution of the complete routine in some images.

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.