連接組件標記算法優化

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級的任務，每個處理一個1000×1000的副圖像 2通：2級的任務，從通所述子畫面的每個處理2 1 3通：1級的任務，處理經過2

的結果對於C＃我推薦Task Parallel Library (TPL)，它允許根據和等待對方輕鬆定義任務。以下代碼項目articel爲您提供了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); 
} 

這是訪問像素數據的基本代碼。

而且我做了一個功能轉換成二維矩陣這一點，它更容易操作（但速度稍慢）

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"

感謝作者的網站爲他的工作做得非常好！ 希望這會有所幫助！