Return to Question

First post on Code Review SE, so here goes.

The Background

I'm working on a real-time, embedded system image processing application for my group engineering capstone in undergrad. I'm receiving data at 60FPS, and have to isolate and detect the location of a flying object in each frame, if it exists, before the next frame. This gives me about 15ms to perform the entire image processing algorithm.

One important step in the process is denoising the image. The input to the denoising function is an M by N image, obtained by background subtraction/frame differencing. Each pixel is represented by a single bit. (Basically we take the frame at time t+1, subtract it from the frame at time t, and if the absolute difference is above some threshold, we set the bit equal to 1.) This means that we store the entire image in M*N/8 bytes.

The Problem

It's too slow. By an order of magnitude. This runs in about 109ms on my hardware for a given image (320x240 in my case). It should be running around 10-12ms.

My Main Questions

• Is the slowness I'm experiencing due to the nature of the job I'm trying to do, or to my implementation?
• How can I speed it up?

Thanks for the help.

I'm working on a real-time, embedded system image processing application for my group engineering capstone in undergrad. I'm receiving data at 60FPS, and have to isolate and detect the location of a flying object in each frame, if it exists, before the next frame. This gives me about 15ms to perform the entire image processing algorithm.

One important step in the process is denoising the image. The input to the denoising function is an \$MxN\$ image, obtained by background subtraction/frame differencing. Each pixel is represented by a single bit. (Basically we take the frame at time \$t+1\$, subtract it from the frame at time \$t\$, and if the absolute difference is above some threshold, we set the bit equal to 1.) This means that we store the entire image in \$\frac{M*N}{8}\$ bytes.

The Problem

It's too slow, by an order of magnitude. This runs in about 109ms on my hardware for a given image (320x240 in my case). It should be running around 10-12ms.

Is the slowness I'm experiencing due to the nature of the job I'm trying to do, or to my implementation? How can I speed it up?

I'm working on a real-time, embedded system image processing application for my group engineering capstone in undergrad. I'm receiving data at 60FPS, and have to isolate and detect the location a flying object in each frame, if it exists, before the next frame. This gives me about 15ms to perform the entire image processing algorithm.

I'm working on a real-time, embedded system image processing application for my group engineering capstone in undergrad. I'm receiving data at 60FPS, and have to isolate and detect the location of a flying object in each frame, if it exists, before the next frame. This gives me about 15ms to perform the entire image processing algorithm.

// bitBuffer is a full image
void Denoise(uint8_t* unsafe bitBuffer)
{

    for (int i = 2; i < IMG_HEIGHT; i++)
    {
         DenoiseRow(
            &bitBuffer[(i-2)*IMG_WIDTH],
            &bitBuffer[(i-1)*IMG_WIDTH],
            &bitBuffer[i*IMG_WIDTH]);
    }
}



// you're never going to get the top, bottom rows in current
void DenoiseRow(
    uint8_t* unsafe top,
    uint8_t* unsafe cur,
    uint8_t* unsafe bot)
{

    // deal with leftmost byte in row.
    cur[0] = DenoiseAndFlipByte(top[0], 0, cur[0], cur[1], bot[0]);

    for (int byte = 1; byte < IMG_WIDTH-1; byte++)
    {
        cur[byte] = DenoiseAndFlipByte(top[byte], cur[byte-1], cur[byte], cur[byte+1], bot[byte]);
    }

    // deal with rightmost byte in row.
    cur[IMG_WIDTH-1] = DenoiseAndFlipByte(top[IMG_WIDTH-1], cur[IMG_WIDTH-2], cur[IMG_WIDTH-1], 0, bot[IMG_WIDTH-1]);
}


uint8_t DenoiseAndFlipByte(
    uint8_t top,
    uint8_t left,
    uint8_t cur,
    uint8_t right,
    uint8_t bot)
{

    // bits
    uint8_t topBit, botBit;
    uint8_t leftBit, curBit, rightBit;

    // final byte to save back
    uint8_t toSaveByte = 0;

    // number of white pixels around current
    uint8_t count = 0;

    // deal with the first bit.
    topBit = top & 0x1;
    top = top >> 1;

    botBit = bot & 0x1;
    bot = bot >> 1;

    rightBit = left & 0x1; // counterintuitive, but this is the orientation: 0 1 2 3 4 5 6 7 ||| 15 14 13 12 11 10 9 8

    curBit = cur & 0x1;
    cur = cur >> 1;

    leftBit = cur & 0x1;
    cur = cur >> 1;

    count = topBit + botBit + leftBit + rightBit;
    count = (count > 2);

    toSaveByte |= count << 7;

    // deal with middle bytes
    for (int i = 1; i < 7; i++)
    {
        topBit = top & 0x1;
        top = top >> 1;

        botBit = bot & 0x1;
        bot = bot >> 1;

        rightBit = curBit;
        curBit = leftBit;
        leftBit = cur & 0x1;
        cur = cur >> 1;

        count = topBit + botBit + leftBit + rightBit;
        count = (count > 2);

        toSaveByte |= count << (7 - i);
    }

    // deal with the last bit
    topBit = top & 0x1;
    botBit = bot & 0x1;

    rightBit = curBit;
    curBit = leftBit;
    leftBit = right & 0x1; // counterintuitive, but this is the orientation: 15 14 13 12 11 10 9 8 ||| 23 22 21 20 19 18 17 16

    count = topBit + botBit + leftBit + rightBit;
    count = (count > 2);

    toSaveByte |= count;

    return toSaveByte;
}

// bitBuffer is a full image
void Denoise(uint8_t* unsafe bitBuffer)
{

    for (int i = 2; i < IMG_HEIGHT; i++)
    {
         DenoiseRow(
            &bitBuffer[(i-2)*IMG_WIDTH],
            &bitBuffer[(i-1)*IMG_WIDTH],
            &bitBuffer[i*IMG_WIDTH]);
    }
}



// you're never going to get the top, bottom rows in current
void DenoiseRow(
    uint8_t* unsafe top,
    uint8_t* unsafe cur,
    uint8_t* unsafe bot)
{

    // deal with leftmost byte in row.
    cur[0] = DenoiseAndFlipByte(top[0], 0, cur[0], cur[1], bot[0]);

    for (int byte = 1; byte < IMG_WIDTH-1; byte++)
    {
        cur[byte] = DenoiseAndFlipByte(top[byte], cur[byte-1], cur[byte], cur[byte+1], bot[byte]);
    }

    // deal with rightmost byte in row.
    cur[IMG_WIDTH-1] = DenoiseAndFlipByte(top[IMG_WIDTH-1], cur[IMG_WIDTH-2], cur[IMG_WIDTH-1], 0, bot[IMG_WIDTH-1]);
}


uint8_t DenoiseAndFlipByte(
    uint8_t top,
    uint8_t left,
    uint8_t cur,
    uint8_t right,
    uint8_t bot)
{

    // bits
    uint8_t topBit, botBit;
    uint8_t leftBit, curBit, rightBit;

    // final byte to save back
    uint8_t toSaveByte = 0;

    // number of white pixels around current
    uint8_t count = 0;

    // deal with the first bit.
    topBit = top & 0x1;
    top = top >> 1;

    botBit = bot & 0x1;
    bot = bot >> 1;

    // Once we arrive here, the leftByte has already been flipped. So now we have this orientation of bytes left/current/right: 0 1 2 3 4 5 6 7 ||| 15 14 13 12 11 10 9 8 | 23 22 ...
    // Therefore, this next command gets bit 7 (the LSB in "left")
    rightBit = left & 0x1; 

    curBit = cur & 0x1;
    cur = cur >> 1;

    leftBit = cur & 0x1;
    cur = cur >> 1;

    count = topBit + botBit + leftBit + rightBit;
    count = (count > 2);

    toSaveByte |= count << 7;

    // deal with middle bytes
    for (int i = 1; i < 7; i++)
    {
        topBit = top & 0x1;
        top = top >> 1;

        botBit = bot & 0x1;
        bot = bot >> 1;

        rightBit = curBit;
        curBit = leftBit;
        leftBit = cur & 0x1;
        cur = cur >> 1;

        count = topBit + botBit + leftBit + rightBit;
        count = (count > 2);

        toSaveByte |= count << (7 - i);
    }

    // deal with the last bit
    topBit = top & 0x1;
    botBit = bot & 0x1;

    rightBit = curBit;
    curBit = leftBit;
 
    // counterintuitive, but this is the orientation of bytes left/cur/right: ... 6 7 | 15 14 13 12 11 10 9 8 | 23 22 21 20 19 18 17 16
    // so this next command gets bit 16.
    leftBit = right & 0x1; 

    count = topBit + botBit + leftBit + rightBit;
    count = (count > 2);

    toSaveByte |= count;

    return toSaveByte;
}