连通构件标记算法的优化

Question

我需要一些帮助来优化我的CCL算法实现。我用它来检测图像上的黑色区域。在2000x2000上，它需要11秒，这是相当多的。我需要将运行时间减少到可能达到的最低值。另外，我很高兴知道是否有其他算法可以让你做同样的事情，但比这个算法更快。下面是我的代码：

    //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;
    }

提前感谢！

Answer 1

您可以将图片拆分为多个子图片，并行处理它们，然后合并结果。1遍:4个任务，每个处理1000x1000子图像2遍:2个任务，每个处理来自遍1的2个子图像3遍:1个任务，处理遍2的结果

对于C#，我推荐使用Task Parallel Library (TPL)，它允许轻松地定义相互依赖和等待的任务。下面的代码项目文章为您提供了对第三方物流的基本介绍：The Basics of Task Parallelism via C#。

Answer 2

我会一次处理一条扫描线，跟踪每次运行的黑色像素的开始和结束。

然后，我会在每一条扫描线上，将其与前一条线上的运行进行比较。如果当前行上存在与上一行上的运行不重叠的运行，则表示新的blob。如果前一条线上有一条与当前线上的一条线重叠的管路，则它将获得与前一条线相同的斑点标签。等等，你明白我的意思。

我会尽量不用字典之类的。在我的经验中，随机停止程序表明，这些事情可能会使编程逐渐变得更容易，但由于new-ing，它们可能会带来严重的性能损失。

Answer 3

这个问题是关于GetPixelColor(x，y)的，它需要很长时间来访问图像数据。Set/GetPixel函数在C#中非常慢，所以如果你需要经常使用它们，你应该改用Bitmap.lockBits。

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);
}

下面是访问像素数据的基本代码。

我做了一个函数将它转换成2D矩阵，它更容易操作(但速度稍慢)

    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;
                }
            });               
        }
    }

代码来自"High performance SystemDrawingBitmap"的网站

感谢作者做的非常好的工作！希望这能有所帮助！