4
\$\begingroup\$

I am trying to figure out how to improve my binary image genetic programming classifier's fitness. It takes images and classifies them if it has some feature X or not in it.

These are the main points:

  1. It takes an image and looks at the first 8 x 8 pixel values (called window).
  2. It saves these 8 x 8 values into an array and runs decodeIndividual on them.
  3. decodeIndividual simply runs the individual's function and retrieves the first and last registers. Last register is the scratchVariable that is updated per each window throughout an image.
  4. The first register is the main identifier per window and it adds it to the y_result which is kept for one image.
  5. When all the windows have been evaluated, y_result is compared to the ground truth and the difference is added to the error. Then the same steps are repeated for another image.

Heres the code:

float GeneticProgramming::evaluateIndividual(Individual individualToEvaluate)
{
    float y_result = 0.0f;
    float error = 0.0f;

    for (int m = 0; m < number; m++)
    {
        int scratchVariable = SCRATCH_VAR;

        for (int row = 0; row <= images[m].rows - WINDOW_SIZE; row += STEP)
        {
            for (int col = 0; col <= images[m].cols - WINDOW_SIZE; col += STEP)
            {
                int registers[NUMBER_OF_REGISTERS] = {0};

                for (int i = 0; i < NUMBER_OF_REGISTERS-1; i++)
                {
                    for (int y = 0; y < row + STEP; y++)
                    {
                        for (int x = 0; x < col + STEP; x++)
                        {
                            registers[i] = images[m].at<uchar>(y,x);
                        }
                    }
                }
                registers[NUMBER_OF_REGISTERS-1] = scratchVariable;
                // we run individual on a separate small window of size 8x8
                std::pair<float, float> answer = decodeIndividual(individualToEvaluate, registers);
                y_result += answer.first;         
                scratchVariable = answer.second;

            }
        }

        float diff = y_groundtruth - y_result;
        // want to look at squared error
        error += pow(diff, 2);
        // restart the y_result per image
        float y_result = 0.0f;
    }

    cout << "Done with individual " << individualToEvaluate.index << endl;
    return error;
}

images is just a vector where I stored all of my images. I also added the decodeIndividual function which just looks at instructions and the given registers from the window and runs the list of instructions.

std::pair<float, float> GeneticProgramming::decodeIndividual(Individual individualToDecode, int *array)
    {   
        for(int i = 0; i < individualToDecode.getSize(); i++)  // MAX_LENGTH
        {
            Instruction currentInstruction = individualToDecode.getInstructions()[i];

            float operand1 = array[currentInstruction.op1];
            float operand2 = array[currentInstruction.op2];
            float result = 0;

            switch(currentInstruction.operation)
            {
                case 0: //+
                    result = operand1 + operand2;
                    break;
                case 1: //-
                    result = operand1 - operand2;
                    break;
                case 2: //*
                    result = operand1 * operand2;
                    break;
                case 3: /// (division)
                    if (operand2 == 0)
                    {
                        result = SAFE_DIVISION_DEF;
                        break;
                    }
                    result = operand1 / operand2;
                    break;
                case 4: // square root
                    if (operand1 < 0)
                    {
                        result = SAFE_DIVISION_DEF;
                        break;
                    }
                    result = sqrt(operand1);
                    break;
                case 5:
                    if (operand2 < 0)
                    {
                        result = SAFE_DIVISION_DEF;
                        break;
                    }
                    result = sqrt(operand2);
                    break;
                default:
                    cout << "Default" << endl;
                    break; 
            }

            array[currentInstruction.reg] = result;
        }
        return std::make_pair(array[0], array[NUMBER_OF_REGISTERS-1]);
    }   

The problem is that I have:

  • 6 grey scale images reduced to size 60 x 80
  • The window size is 8 x 8
  • Step is 2
  • Number of registers is 65

Yet it takes over 3 seconds to evaluate these 6 incredibly small images. How do I improve my code? I would appreciate anyone pointing out some mistakes or at least providing some guidance. I am thinking of using threads to evaluate each individual separately.

EDIT: So I have adjusted my code.

float GeneticProgramming::evaluateIndividual(Individual individualToEvaluate)
    {
        float y_result = 0.0f;
        float error = 0.0f;

        for (int m = 0; m < number; m++)
        {
            int scratchVariable = SCRATCH_VAR;

            for (int row = 0; row <= images[m].rows - WINDOW_SIZE; row += STEP)
            {
                for (int col = 0; col <= images[m].cols - WINDOW_SIZE; col += STEP)
                {

                    cv::Rect windows(col, row, WINDOW_SIZE, WINDOW_SIZE);
                    cv::Mat roi = images[m](windows);
                    std::pair<float, float> answer = decodeIndividual(individualToEvaluate, roi, scratchVariable);

                    y_result += answer.first;
                    scratchVariable = answer.second;

                }
            }

            float diff = y_groundtruth - y_result;
            // want to look at squared error
            error += pow(diff, 2);
            // restart the y_result per image
            float y_result = 0.0f;
        }

        cout << "Done with individual " << individualToEvaluate.index << endl;
        return error;
    }

I also changed the decodeIndividual() so that it takes the roi and a scratchVariable as follows:

std::pair<float, float> GeneticProgramming::decodeIndividual(Individual individualToDecode, cv::Mat &registers, int &scratchVariable)

{   

        int array[NUMBER_OF_REGISTERS];

        unsigned char* p;
        for(int ii = 0; ii < WINDOW_SIZE; ii++)
        {
                p = registers.ptr<uchar>(ii);
                for(int jj = 0; jj < WINDOW_SIZE; jj++)
                {
                        array[ii*WINDOW_SIZE+jj] = p[jj];
                }
        }

        array[NUMBER_OF_REGISTERS-1] = scratchVariable;
            for(int i = 0; i < individualToDecode.getSize(); i++)  // MAX_LENGTH
            {
                Instruction currentInstruction = individualToDecode.getInstructions()[i];

                float operand1 = array[currentInstruction.op1];
                float operand2 = array[currentInstruction.op2];
                float result = 0;

                switch(currentInstruction.operation)
                {
                    case 0: //+
                        result = operand1 + operand2;
                        break;
                    case 1: //-
                        result = operand1 - operand2;
                        break;
                    case 2: //*
                        result = operand1 * operand2;
                        break;
                    case 3: /// (division)
                        if (operand2 == 0)
                        {
                            result = SAFE_DIVISION_DEF;
                            break;
                        }
                        result = operand1 / operand2;
                        break;
                    case 4: // square root
                        if (operand1 < 0)
                        {
                            result = SAFE_DIVISION_DEF;
                            break;
                        }
                        result = sqrt(operand1);
                        break;
                    case 5:
                        if (operand2 < 0)
                        {
                            result = SAFE_DIVISION_DEF;
                            break;
                        }
                        result = sqrt(operand2);
                        break;
                    default:
                        cout << "Default" << endl;
                        break; 
                }

                array[currentInstruction.reg] = result;
            }
            return std::make_pair(array[0], array[NUMBER_OF_REGISTERS-1]);
    }   

Yet I am still receiving unsatisfying results. Any ideas?

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you using OpenCV here? If so, images[m].at<uchar>(y,x) would be quite slow, I believe. Usually people get a pointer to an image row, and loop over the row using that. Also, the inner two loops do a lot of redundant work, they overwrite each other's work, with the next loop out producing the same result for each of the elements in registers. Are you sure that you are getting correct results? \$\endgroup\$ – Cris Luengo Apr 22 at 17:26
  • 1
    \$\begingroup\$ No, my results are actually not satisfying at all. But I was following another tutorial, thats how I got my current code. \$\endgroup\$ – Gabriele Apr 26 at 6:39
  • 1
    \$\begingroup\$ This is the tutorial I followed: funvision.blogspot.com/2015/12/… \$\endgroup\$ – Gabriele Apr 26 at 7:41
2
\$\begingroup\$

I'm concerned with this bit of code, the inner 3 loops:

int registers[NUMBER_OF_REGISTERS] = {0};
for (int i = 0; i < NUMBER_OF_REGISTERS-1; i++)
{
    for (int y = 0; y < row + STEP; y++)
    {
        for (int x = 0; x < col + STEP; x++)
        {
            registers[i] = images[m].at<uchar>(y,x);
        }
    }
}

The inner loop writes into the same array element registers[i] every time. Therefore it can be simplified to:

int registers[NUMBER_OF_REGISTERS] = {0};
for (int i = 0; i < NUMBER_OF_REGISTERS-1; i++)
{
    for (int y = 0; y < row + STEP; y++)
    {
        int x = col + STEP - 1;
        registers[i] = images[m].at<uchar>(y,x);
    }
}

Again, the new inner loop does nothing:

int registers[NUMBER_OF_REGISTERS] = {0};
for (int i = 0; i < NUMBER_OF_REGISTERS-1; i++)
{
    int y = row + STEP - 1;
    int x = col + STEP - 1;
    registers[i] = images[m].at<uchar>(y,x);
}

And this we can simplify to:

int registers[NUMBER_OF_REGISTERS];
int y = row + STEP - 1;
int x = col + STEP - 1;
int value = images[m].at<uchar>(y,x);
for (int i = 0; i < NUMBER_OF_REGISTERS-1; i++)
{
    registers[i] = value;
}

This of course does not look like anything you might have intended to write.

I think your code does not do what you intended it to do. Don't worry with speed until your code works as intended.

\$\endgroup\$
  • \$\begingroup\$ What do you mean "code does not do what you intended it to do"? \$\endgroup\$ – Gabriele Apr 26 at 6:31
  • \$\begingroup\$ After I followed your changes, it seems to work much faster but it does not produce satisfying results. \$\endgroup\$ – Gabriele Apr 26 at 6:47
  • \$\begingroup\$ @Gabriele: it seems from your description that you want to copy the pixels within the window into registers, but your code copies the same pixel into each element of that array. The transformations I show here don’t affect the result of your code, hence demonstrate that your code does not do what you want it to do. \$\endgroup\$ – Cris Luengo Apr 26 at 13:12
  • \$\begingroup\$ @Gabrielle: what you want to do is keep the two loops over x and y, and get rid of the loop over i. You need to increment i every time you write a value to the registers array. \$\endgroup\$ – Cris Luengo Apr 26 at 13:13
  • \$\begingroup\$ I have completely removed the inner loops and added this rectangle (see the original post). I made sure that the real image's window is the same one as in the rectangle when I pass it to the decodeIndividual(). However, I am still getting unsatisfying results. \$\endgroup\$ – Gabriele Apr 27 at 12:15
1
\$\begingroup\$

Since I'm unable to compile your program (there is no full working code), my review will be a little limited. But consider at least the following points.

  • Do not pass Individual by-value when it is not necessary. This can be very costly. Instead, prefer passing by const-ref as in const Individual& individualToEvaluate.

  • It seems that y_result should go inside the first of the for-loops, then you don't have to set it to zero at the end.

  • You can try replacing a call to pow(error, 2) by your own squaring function that just returns x * x; I have noticed this to be a little faster than std::pow sometimes in the past (but maybe things are different nowadays).

  • Make diff const. There are many more local variables that you should mark const as well. It makes errors less likely to happen and improves readability.

  • Doing I/O operations like cout and endl will slow down your program. Get rid of them if you need speed. Also, don't use endl when \n suffices.

  • It won't hurt to precompute images[m].rows - WINDOW_SIZE (and images[m].cols - WINDOW_SIZE) as const variables before the for-loop. This can speed up your execution by a tiny margin. You can also precompute row + STEP and col + STEP.

  • Your decoding function is quite messy. You could borrow an idea from this answer to make it prettier.

This is still quite superficial and you can't hope to get much more unless you isolate your issue and post more details, I believe.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.