Adventures with WriteableBitmap and Bit Manipulation

Published on: January 4, 2013

Look at the following images and think about how a user could toggle this change back and forth in an application.

The task is simple, create borders between countries. A border is drawn whenever there are two differing pixels that are adjacent to each other. This implicitly implies that two passes of the image must be made, as all horizontally adjacent pixels have to be checked and all vertically adjacent have to be checked. When a border has been detected, the current pixel and the adjacent pixel are turned black.

The goal is to achieve the task in O(n) time and O(1) space.

First instincts suggest that this would be relatively simple to code as all one would need is a for-loop to iterate the pixels and a couple conditionals to detect if neighboring pixels differ. This is wrong. The entire image will end up black. To give an example, imagine processing the image left to right and top to bottom. If two horizontally adjacent pixels differ, according to the algorithm you turn both black. However the next pixel being evaluated is now the newly turned black neighbor, which will obviously differ from its horizontal neighbor, as its neighbor can’t be black. This causes all subsequent pixels to be turned black. Quick thinkers may reply that this problem can be fixed by either skipping the newly turned black horizontal pixel on the next loop iteration or keeping around a temp value that denotes the original horizontal color. The first idea is wrong as it produces inaccuracies. By skipping a pixel there is a chance that the subsequent pixel will erroneously not be marked black because it had a different color than the skipped pixel. A temporary value would work if only one pass of the image was needed; however, since horizontal and vertical neighbors must be checked, there is no feasible way without violating the O(1) space constraint, as an array the size of the picture width would have to allocated to keep track of all the temporary values for the row below.

This is where the WriteableBitmap Class comes into play. When working with 24-bit files, WriteableBitmap handles them as if they are 32 bit images. Normally I would be disappointed with the wasted 8 bits, as the alpha channel is useless for my purposes, but this case is different. Working with 32 bits (4 bytes) allows for faster iteration through the image as instead of traversing pixels byte by byte, traversal by int pointer is possible. Another benefit is that with the use of clever bit manipulation, it is possible for O(1) space.

The original image had a pixel depth of 24 bits, but the WriteableBitmap class stores it as 32 bits. The first byte of every pixel in the WriteableBitmap is guaranteed to be 255, denoting the pixel is entirely opaque, as the original image was up-converted from 24 to 32 bits. Subsequently, this extra byte can be taken advantage by temporarily setting the alpha channel while processing the image and then restoring the original 255 value once finished. The solution should now appear simple. When reading the image and comparing colors, compare only the last 24 bits of the colors. If the colors are different, then set the appropriate pixels to the extracted colors, which has the effect of setting the first 8 bits to 0. This does not modify any of the last 24 bits of any pixels, so the algorithm can continue extracting the underlying color of following pixels even if marked black. After scanning the image and marking the appropriate pixels with the first 8 bits being 0, the image is scanned again with the marked pixels reverting to 255 alpha and having the color of black.

I gave myself a pat on the back after coming up with this idea.