Code Optimization / Image Processing

5

I'm doing a C-class work on image processing. And I need to find an alternative to optimize a particular piece of code. Here's how:

/* 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];
                    }
                }
            }
        }
    }
/* ================================================================================================================================ */  

Operation

The operation is in the multi-pass algorithm, scanning the array of the image by checking the neighborhood. For the foward stage, the above and the left neighbors go from the [1,1] < [X,Y] indexes, to the backward neighbors of the right and the lower going from [X-2,Y-2] > [0,0] . Ignoring the edges because they are not reliable. Here is an example image:

Whattodo?

Ineedtofindawaytooptimizethishugenestedif/else,whichaccordingtotheteachertherearebetterwaystodo.I'vebeenpullingmyhairformorethantwohoursthinkingaboutasolution,butsofarIhavenotbeenabletocomeupwithasolutionthatismorefeasibleandwithalowercomputationalcost,alltheroutesleadmetonestedwithif/else.>

Edit

Fowardroutineresult:

AftertheFowardperformstheBackwardRoutine.

ResultRoutineBackward:

    
asked by anonymous 14.06.2017 / 00:06

4 answers

1

I would first like to thank everyone, @Lacobus, @Renan and @Wtrmute.

After analyzing the suggestions given by everyone, using a little bit of each one I put 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;
                }
            }
        }
    }

Thank you guys! Using the code in this way I realized a considerable performance gain, reducing the execution of the complete routine in some images by almost 3 seconds.

    
19.06.2017 / 04:51
5

Here is 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;
                }
            }
        }
    }
}
    
14.06.2017 / 16:19
4

Although I think my answer is correct, Lacobus's 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 that you may have to use alloc , malloc , calloc to declare the vizinhos vector, and maybe even use pointer to access the positions. I just wanted to get the idea out here. I'm more rusty in C than shipwreck.

If you refer 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];

... This makes it easy to read. Again, I may have missed the specific syntax of C, but this idea is valid in C and virtually all of its parent languages.

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

    
14.06.2017 / 16:07
4

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

First, if you want to avoid% nested% s, you can transform 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 memoing the current pixel and neighbors, suggested by Renan, is not bad: you do not need to allocate a new vector at each iteration, you can use it and overwrite it with 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 more important item is the fact that you are checking out the neighbors whose coordinates you have already swept . This usually means that the algorithm is meant to be executed in-place, that is, you do not need an array of result if array % separated from the array entry out . With this you save the space of an entire image - although temporarily the algorithm continues O (height × width) .

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

    
14.06.2017 / 18:35