Connected-component labeling algorithm optimization

Question

I need some help with optimisation of my CCL algorithm implementation. I use it to detect black areas on the image. On a 2000x2000 it takes 11 seconds, which is pretty much. I need to reduce the running time to the lowest value possible to achieve. Also, I would be glad to know if there is any other algorithm out there which allows you to do the same thing, but faster than this one. So here is my code:

    //The method returns a dictionary, where the key is the label
    //and the list contains all the pixels with that label
    public Dictionary<short, LinkedList<Point>> ProcessCCL()
    {
        Color backgroundColor = this.image.Palette.Entries[1];
        //Matrix to store pixels' labels
        short[,] labels = new short[this.image.Width, this.image.Height];
        //I particulary don't like how I store the label equality table
        //But I don't know how else can I store it
        //I use LinkedList to add and remove items faster
        Dictionary<short, LinkedList<short>> equalityTable = new Dictionary<short, LinkedList<short>>();
        //Current label
        short currentKey = 1;
        for (int x = 1; x < this.bitmap.Width; x++)
        {
            for (int y = 1; y < this.bitmap.Height; y++)
            {
                if (!GetPixelColor(x, y).Equals(backgroundColor))
                {
                    //Minumum label of the neighbours' labels
                    short label = Math.Min(labels[x - 1, y], labels[x, y - 1]);
                    //If there are no neighbours
                    if (label == 0)
                    {
                        //Create a new unique label
                        labels[x, y] = currentKey;
                        equalityTable.Add(currentKey, new LinkedList<short>());
                        equalityTable[currentKey].AddFirst(currentKey);
                        currentKey++;
                    }
                    else
                    {
                        labels[x, y] = label;
                        short west = labels[x - 1, y], north = labels[x, y - 1];
                        //A little trick:
                        //Because of those "ifs" the lowest label value
                        //will always be the first in the list
                        //but I'm afraid that because of them
                        //the running time also increases
                        if (!equalityTable[label].Contains(west))
                            if (west < equalityTable[label].First.Value)
                                equalityTable[label].AddFirst(west);
                        if (!equalityTable[label].Contains(north))
                            if (north < equalityTable[label].First.Value)
                                equalityTable[label].AddFirst(north);
                    }
                }
            }
        }
        //This dictionary will be returned as the result
        //I'm not proud of using dictionary here too, I guess there 
        //is a better way to store the result
        Dictionary<short, LinkedList<Point>> result = new Dictionary<short, LinkedList<Point>>();
        //I define the variable outside the loops in order 
        //to reuse the memory address
        short cellValue;
        for (int x = 0; x < this.bitmap.Width; x++)
        {
            for (int y = 0; y < this.bitmap.Height; y++)
            {
                cellValue = labels[x, y];
                //If the pixel is not a background
                if (cellValue != 0)
                {
                    //Take the minimum value from the label equality table 
                    short value = equalityTable[cellValue].First.Value;
                    //I'd like to get rid of these lines
                    if (!result.ContainsKey(value))
                        result.Add(value, new LinkedList<Point>());
                    result[value].AddLast(new Point(x, y));
                }
            }
        }
        return result;
    }

Thanks in advance!

@L.B Yes, that's what I used in the first time and it works even slower, so I had to write my own implementation. — Cracker
– Cracker, Commented Aug 28, 2012 at 19:05

DELUXEnized · Accepted Answer · 2012-08-28 19:31:13Z

1

You could split your picture in multiple sub-pictures and process them in parallel and then merge the results. 1 pass: 4 tasks, each processing a 1000x1000 sub-picture 2 pass: 2 tasks, each processing 2 of the sub-pictures from pass 1 3 pass: 1 task, processing the result of pass 2

For C# I recommend the Task Parallel Library (TPL), which allows to easily define tasks depending and waiting for each other. Following code project articel gives you a basic introduction into the TPL: The Basics of Task Parallelism via C#.

answered Aug 28, 2012 at 19:31

DELUXEnized

1,27816 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Cracker Over a year ago

But CCL relies on the result of previous scans, that's how the equivalence table is created. I do not think that the algorithm you suggested will work.

Mike Dunlavey · Accepted Answer · 2012-08-28 20:32:23Z

1

I would process one scan line at a time, keeping track of the beginning and end of each run of black pixels.

Then I would, on each scan line, compare it to the runs on the previous line. If there is a run on the current line that does not overlap a run on the previous line, it represents a new blob. If there is a run on the previous line that overlaps a run on the current line, it gets the same blob label as the previous. etc. etc. You get the idea.

I would try not to use dictionaries and such. In my experience, randomly halting the program shows that those things may make programming incrementally easier, but they can exact a serious performance cost due to new-ing.

answered Aug 28, 2012 at 20:32

Mike Dunlavey

40.8k15 gold badges95 silver badges140 bronze badges

Comments

TGuerin · Accepted Answer · 2015-02-15 10:58:17Z

The problem is about GetPixelColor(x, y), it take very long time to access image data. Set/GetPixel function are terribly slow in C#, so if you need to use them a lot, you should use Bitmap.lockBits instead.

private void ProcessUsingLockbits(Bitmap ProcessedBitmap)
{
    BitmapData bitmapData = ProcessedBitmap.LockBits(new Rectangle(0, 0, ProcessedBitmap.Width, ProcessedBitmap.Height), ImageLockMode.ReadWrite, ProcessedBitmap.PixelFormat);
    int BytesPerPixel = System.Drawing.Bitmap.GetPixelFormatSize(ProcessedBitmap.PixelFormat) / 8;
    int ByteCount = bitmapData.Stride * ProcessedBitmap.Height;
    byte[] Pixels = new byte[ByteCount];
    IntPtr PtrFirstPixel = bitmapData.Scan0;
    Marshal.Copy(PtrFirstPixel, Pixels, 0, Pixels.Length);
    int HeightInPixels = bitmapData.Height;
    int WidthInBytes = bitmapData.Width * BytesPerPixel;
    for (int y = 0; y < HeightInPixels; y++)
    {
        int CurrentLine = y * bitmapData.Stride;
        for (int x = 0; x < WidthInBytes; x = x + BytesPerPixel)
        {
            int OldBlue = Pixels[CurrentLine + x];
            int OldGreen = Pixels[CurrentLine + x + 1];
            int OldRed = Pixels[CurrentLine + x + 2];
            // Transform blue and clip to 255:
            Pixels[CurrentLine + x] = (byte)((OldBlue + BlueMagnitudeToAdd > 255) ? 255 : OldBlue + BlueMagnitudeToAdd);
            // Transform green and clip to 255:
            Pixels[CurrentLine + x + 1] = (byte)((OldGreen + GreenMagnitudeToAdd > 255) ? 255 : OldGreen + GreenMagnitudeToAdd);
            // Transform red and clip to 255:
            Pixels[CurrentLine + x + 2] = (byte)((OldRed + RedMagnitudeToAdd > 255) ? 255 : OldRed + RedMagnitudeToAdd);
        }
    }
    // Copy modified bytes back:
    Marshal.Copy(Pixels, 0, PtrFirstPixel, Pixels.Length);
    ProcessedBitmap.UnlockBits(bitmapData);
}

Here is the basic code to access pixel data.

And I made a function to transform this into a 2D matrix, it's easier to manipulate (but little slower)

    private void bitmap_to_matrix()
    {
        unsafe
        {
            bitmapData = ProcessedBitmap.LockBits(new Rectangle(0, 0, ProcessedBitmap.Width, ProcessedBitmap.Height), ImageLockMode.ReadWrite, ProcessedBitmap.PixelFormat);
            int BytesPerPixel = System.Drawing.Bitmap.GetPixelFormatSize(ProcessedBitmap.PixelFormat) / 8;
            int HeightInPixels = ProcessedBitmap.Height;
            int WidthInPixels = ProcessedBitmap.Width;
            int WidthInBytes = ProcessedBitmap.Width * BytesPerPixel;
            byte* PtrFirstPixel = (byte*)bitmapData.Scan0;

            Parallel.For(0, HeightInPixels, y =>
            {
                byte* CurrentLine = PtrFirstPixel + (y * bitmapData.Stride);

                for (int x = 0; x < WidthInBytes; x = x + BytesPerPixel)
                {
                    // Conversion in grey level                       
                    double rst = CurrentLine[x] * 0.0721 + CurrentLine[x + 1] * 0.7154 + CurrentLine[x + 2] * 0.2125;

                    // Fill the grey matix
                    TG[x / 3, y] = (int)rst;
                }
            });               
        }
    }

And the website where the code comes "High performance SystemDrawingBitmap"

Thanks to the author for his really good job ! Hope this will help !

Collectives™ on Stack Overflow

Connected-component labeling algorithm optimization

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related