6
\$\begingroup\$

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.

Owing to a quirk of how the background subtraction algorithm was implemented, the LSB of each byte contains the earliest pixel sent by the camera, and the MSB contains the latest pixel sent by the camera. So our input data is ordered something like this in our array:

7 6 5 4 3 2 1 0 | 15 14 13 12 11 10 9 8 | 23 22 21 20 19 18 17 16 | 31 ...

My denoising function performs two operations:

  • Sets a pixel to 0 if there are less than 3 pixels next to it with a 1.
  • Flips the orientation of data to simplify further processing, so that it looks like 0 1 2 3 4 5 6 7 | 8 9 ...

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?

// 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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ What type of cpu are you running this on? Also, something isn't right with your explanation of the bit orientation. It can't be that both rightBit = left & 0x1 and leftBit = right & 0x1. One of those should be 0x80 instead of 0x1. If you think your code is correct, could you clarify which bits appear in which order in terms of (x,y) position? For example, is bit 0 of the first byte at (0,0) or (7,0)? Is bit 0 of the second byte at (8,0) or (15,0)? \$\endgroup\$ – JS1 Mar 5 '17 at 9:39
  • \$\begingroup\$ I'm running this on an XMOS processor (XUF216-512-TQ128). The code actually is xC, a variant of C, but in this section I'm just using straight C. As for the bit: good catch. The original input data is exactly like I've described it. However, because each byte is overwritten by the result of DenoiseAndFlipByte(), once DenoiseAndFlipByte() gets to a new byte, the orientation is 0 1 2 3 4 5 6 7 | 15 14 13 12 11 10 9 8 | 23 22 21 20 19 18 17 16. So rightBit = left & 0x1 obtains 7, while leftBit = right & 0x1 obtains 16. \$\endgroup\$ – tbadams45 Mar 5 '17 at 13:13
  • \$\begingroup\$ In terms of (x, y) position then, if I understand you correctly: bit 0 of first (or "left") byte is (7, 0). Bit 7 (MSB) of first byte is (0, 0). bit 0 of second (or "current") byte is (8, 0), whereas bit 7 is (15, 0). Bit 0 of third byte is (16, 0), and bit 7 is (23, 0). \$\endgroup\$ – tbadams45 Mar 5 '17 at 13:26
3
\$\begingroup\$

Program doesn't produce correct result

At first I was going to write something about how to speed up your program, but as I examined it more closely, I found that it wasn't producing the correct result. I think you first need to address these issues (or clarify that they are not issues) before I can talk about how to fix your speed issues.

Here are the problems I found:

Top and bottom rows unflipped

Your function does two things: denoise and flip the bit orientations. But you never flip the bit orientations of the top and bottom row, so your output image will have a mix of bit orientations.

Incorrect handling of upper row bits

Since your algorithm works from top to bottom and left to right, when you get to a particular pixel, both the upper and the left bytes will already be flipped. You correctly take care of the left side by doing left & 1 instead of left & 0x80 (as mentioned in your comments). However, you didn't do the same for the upper row bits. You handle the upper and lower rows the same way, when you should be dealing with the upper row in a reversed fashion since they have already been flipped.

More fundamental issue

The previous issue points to a more fundamental one. Your algorithm uses "new bits" from the top and left and "old bits" from the bottom and right to compute what happens to the current pixel. I think you should only use "old bits" from the original image to compute the results for each pixel. In other words, I think you should write your results to a copy of the original image instead of doing the work in-place.

If you do the denoising in-place, you will cause an effect to occur where the upper left pixel in the image will have an effect on what happens to the lower right pixel, because each pixel affects its right and bottom neighbors, and then those pixels affect their right and bottom neighbors, etc. There could be cases where you could change a single pixel in the upper left corner and it could cause the output to look entirely different due to a cascading chain of effects.

From your problem specification, it doesn't seem that this cascading effect is intended. However, this effect might not matter to you. I don't really know.

Speed optimization / followup question

I have an idea in mind to speed up your program by using a precomputed lookup table to do the denoising. However, without knowing how you want to handle the previously mentioned issues, I can't really show you an example of what it would look like. If you address those issues and post a followup question, I would be able to give you an answer there.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback. Ignoring the top/bottom rows was anticipated, but I hadn't noticed the cascading effect. I'm going to need to explore my memory constraints more, but if possible I'm going to try to avoid that by following your advice and writing the results to a copy. I've had to set this project aside for a bit, but will hopefully post a follow up question in the next couple of weeks. \$\endgroup\$ – tbadams45 Mar 15 '17 at 1:24
3
\$\begingroup\$

One common way to speed up operations that have as much bit twiddling as you are doing is to examine more than one bit at once. This is commonly done using lookup tables. So, if you were going to say examime a nibble at a time, those 4 bits would have 16 possibilities. If you include the adjacent bits on either end it becomes 64 possibilities.

These 64 possibilities could be pre-computed as to their outcomes. You could then resolve 4 bits with one lookup and not much RAM would be required. The more RAM you have available, the bigger the table you can build, and the more bits you could resolve at one go.

\$\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.