Binary genetic programming image classifier's fitness function

Question

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?

Answer 1

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.

Answer 2

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.