Introduction
Languages like C# and Java are very easy to use, and they present a lot of features for Application Layer development. This means that they could easily access peripheral devices and at the same time, make GUI (Graphical user interface) development much easier. However it is always said that they are not good for signal processing applications because of the overhead and limited possibility of optimization. In such applications, the code usually runs much more slowly when compared to C/C++ code. We know this is a natural result. However, there are certain applications which are not very speed-demanding. Some examples may include educational software, algorithm test software, or integration with existing applications. For these reasons, signal, or in this case image processing in C# may be a good idea. In this article I won't describe complicated image processing algorithms but I will describe how one can implement these algorithms in C# in an efficient way, using simple examples such as thresholding, gray scale conversion and connected component analysis. This will sort of be like an introduction to people who like signal processing and at the same time want to write test codes in C# to make things easier.
Background
Thresholding
Thresholding is binarizing the image in such a way that the values bigger than a threshold will be 255 (maximum pixel value in bytes) and pixels with smaller intensities will be set to 0 (black). It is a very important operation that is often used to prepare images for vectorization, further segmentation or use as guide layers in the creation of drawings. It can be used with raster data images to set off ranges of values that may then be used for subsequent analysis or as selection masks. Some people refer to it as foreground and background separation. Here is a result of Lena thresholded:
Gray Scale Conversion
Gray scale conversion is setting of all pixels of an image to a weighted average of the values in different color channels. The conversion is done through the mapping:
GRAY= (byte)(.299 * R + .587 * G + .114 * B);
Connected Component Analysis
Connected component labeling is used in computer vision to detect unconnected regions in binary digital images, although color images and data with higher-dimensionality can also be processed. When integrated into an image recognition system or human-computer interaction interface, connected component labeling can operate on a variety of information. (Wikipedia definition).
Connected component labeling works by scanning an image, pixel-by-pixel (from top to bottom and left to right) in order to identify connected pixel regions, i.e. regions of adjacent pixels which share the same set of intensity values V. (For a binary image V={1}; however, in a graylevel image V will take on a range of values, for example: V={51, 52, 53, ..., 77, 78, 79, 80}.)
Pointer Arithmetic
Image pixels are represented in a 1D array in memory. We access it through pointers. While reading the rest of the code, one should keep in mind that pointers are actually only addresses. Even though the image is a 2D structure, for convenience and ease of processing & speed, it is a common technique to represent it as a 1D structure. In such a case, the image can be indexed as:
[y*ImageWidth*ChannelCount+x*ChannelCount]
Because of the linear structure of the memory, a pointer is used linearly to index the image using the given formula. Languages like C/C++/C# and even assembler allow us to use arithmetic operation on pointers. For example:
int x[5];
int* p =&x[0]; // Get address of x
p=p+2; // This line increments the pointer by 2 memory addresses and hence
//we could access x[2]
Using the Code
Now we will go step by step showing how we could write a simple image processing routine in C#: This code is very easy and yet undesired of writing an image processing routine. GetPixel and SetPixel functions have several drawbacks. First of all they are functions. We have the function overhead of accessing and modifying a pixel value. However, in many cases we would want to modify the image through a pointer operation not a function call. The next example utilizes the “unsafe” block in C#. Inside unsafe blocks, we have access to pointers from C#. But don't mix it with the idea of pointers that you are familiar from C/C++. These pointers don't address the unmanaged code directly. What they address is related to intermediate language. You can read about it more in many articles. It has its own instructions (soft instructions of course) and own language. The conclusion is that pointers in unsafe blocks are not as fast as native pointers. Here is how one can implement it:
You see three important issues here:
Lockbits and UnlockBits functionsbyte* accessp[0] operation
Notice that we have a loop from 0 to Width*ChannelCount*Height which is the total amount of bytes that are stored in the memory. Then we increment the pointer by ptr+=3 so that we can process each color pixel. When using GDI, one should be careful about two important facts:
- Pixels are ordered as BGRBGRBGRBGRBGRBGR… instead of RBGRBGRBGRBG… This is one of the strange things Microsoft has come up with.
- The image is flipped. This is not so crucial when using techniques described in this article, but it is important when one needs to go more native.
Most of the people who do some work on image processing with C# use the coding convention that I described above. Unfortunately, this style has some unoptimized operations. For example, we have a y value counting from 0 to imageSize, but it is not used inside the loop. Also, the pointer is incremented by 3 each time while y is also incremented. To overcome this problem, we could go ahead and use further pointer arithmetic. Here is an example:
private void Convert2GrayScaleFast(Bitmap bmp)
{
BitmapData bmData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height),
ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
unsafe
{
byte* p = (byte*)(void*)bmData.Scan0.ToPointer();
int stopAddress = (int)p + bmData.Stride * bmData.Height;
while ((int)p != stopAddress)
{
p[0] = (byte)(.299 * p[2] + .587 * p[1] + .114 * p[0]);
p[1] = p[0];
p[2] = p[0];
p += 3;
}
}
bmp.UnlockBits(bmData);
}
In this example, we calculate the start and end addresses of the image structure, thinking that it is a 1D linear array. We increment the pointer from start to end addresses and get values in between. If one measures the computation time of these three algorithms (slow, well known and new), he/she will see that there is a huge difference between each of them. If you download the code, you will see the measured times in messageboxes.
Connected Component Labeling Algorithm
This algorithm is the stack implementation of general recursive connected component labeling algorithm. You can use it for many applications and get good results. I am not pretty sure that it's the best implementation but the results seem satisfactory. The implementation is very similar to Trajan's strongly connected component algorithm. However it has been generalized for images. The pseudo-code is as follows:
Input: Graph G = (V, E), Start node v0
index = 0 // DFS node number counter
S = empty // An empty stack of nodes
tarjan(v0) // Start a DFS at the start node
procedure tarjan(v)
v.index = index // Set the depth index for v
v.lowlink = index
index = index + 1
S.push(v) // Push v on the stack
forall (v, v') in E do // Consider successors of v
if (v'.index is undefined) // Was successor v' visited?
tarjan(v') // Recurse
v.lowlink = min(v.lowlink, v'.lowlink)
elseif (v' in S) // Is v' on the stack?
v.lowlink = min(v.lowlink, v'.lowlink)
if (v.lowlink == v.index) // Is v the root of an SCC?
print "SCC:"
repeat
v' = S.pop
print v'
until (v' == v)
Conclusion
I hope this article will help anyone to speed up their image processing algorithms. I don't know if this will happen or not but if Microsoft can integrate inline assembler (Not intermediate language assembler but native assembler) in C#, we will be able to write algorithms almost as fast as C++ code if not faster.
History
- 16th November, 2008: Initial post
