Algorithms in C#: Connected Component Labeling

re: Algorithms in C#: Connected Component Labeling

Kirill Osenkov — Tue, 13 May 2008 08:27:34 GMT

Brian, a developer on the F# team, has posted the F# solution which uses the Union-Find algorithm:

http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!220.entry

It's much faster than my algorithm :) And looks shorter. Highly recommended.

re: Algorithms in C#: Connected Component Labeling

Morgan Cheng — Wed, 21 May 2008 13:16:41 GMT

I happens to investigate this algorithm recently.

I have to adimit that the track row instead of point is a ingenious idea, but there is a lot collections are created and then released. So, I tried to implement it in other ways to validate the performance.

The result is interesting:

For most of the time the pixel-by-pixel algorithm is much faster than span-by-span algorithm. Pixel-by-pixel is not defeated when color blob is sparse. That is, "White percentage" bar is to very left or very right.

re: Algorithms in C#: Connected Component Labeling

Kirill Osenkov — Thu, 22 May 2008 04:00:43 GMT

Interesting! Thanks Morgan. I'll have to implement the classic pixel-by-pixel algorithm next time to measure the performance difference.

re: Algorithms in C#: Connected Component Labeling

Morgan Cheng — Thu, 22 May 2008 05:35:11 GMT

I'm in rush yesterday and have no time to analyze the reason. Now, I believe that the reason is that the randomly generated graph is not appropriate for span-by-span detection. Since it is random, black and white pixels are even distributed. So, there is not long span there; each span has only few pixels. In worst case, each span has only one pixel. As a result, the power of span is not utilized.

I use the two different way on real image. It turns out that span-by-span way is better than pixel-by-pixel way, since in real photo, same color is generally in blob. In average, the time cost ratio is 3:1. So, the span-by-span algorithm is really helpful! thanks.

The 3-generation way like .net GC is really brilliant idea! But I implement span-by-span in traditional way. Each span is assigned a blobID . For each span, if there is no intersection with up row, a new blob id is assigned; if there is only one intersection, the up span blob ID is reused; if there is more than one intersection, use the smallest blob id, and a boundTo mapping of id-to-id is updated. After the parsing, we can get the directBoundTo from boundTo, then each blob has a unique blob ID.

Below is just some sample code. The performance is better than 3-gen way. Perhaps mainly due to less function call and collection used.

var boundTo = new Dictionary<int, int> ();

int blobID = 0;

for (int y = 0; y < height; ++y)

{

var rowSet = new StrikeList<Color>();

allStrikes.Add(rowSet);

{

Strike<Color> strike = null;

Color prevPixel = Color.Empty;

for (int x = 0; x < width; ++x)

{

Color currPixel = field[x, y];

if (currPixel != prevPixel)

{

if (strike != null)

{

strike.EndX = x - 1;

rowSet.Add(strike);

strike = null;

}

prevPixel = currPixel;

if (currPixel != Color.Empty)

{

strike = new Strike<Color> { StartX = x, Color = currPixel, Y = y };

}

if (strike != null)

{

strike.EndX = width - 1;

rowSet.Add(strike);

}

StrikeList<Color> prevRowSet = (y > 0) ? allStrikes[y - 1] : new StrikeList<Color>();

foreach (var strike in rowSet)

{

List<Strike<Color>> insected = prevRowSet.Where(s => s.IntersectWith(strike)).ToList();

if (insected.Count == 0)

{

strike.BlobID = (++blobID);

boundTo[blobID] = blobID;

}

else if (insected.Count == 1)

{

strike.BlobID = insected[0].BlobID;

}

else

{

var minBlob = insected[0];

for (int i = 0; i < insected.Count; ++i)

{

if (insected[i].BlobID < minBlob.BlobID)

{

minBlob = insected[i];

}

strike.BlobID = minBlob.BlobID;

foreach (var s in insected)

{

if (s != minBlob)

{

boundTo[s.BlobID] = minBlob.BlobID;

}

var directBoundTo = new Dictionary<int, int>();

foreach (var key in boundTo.Keys)

{

int target = boundTo[key];

while (boundTo[target] != target)

{

target = boundTo[target];

}

directBoundTo[key] = target;

}

re: Algorithms in C#: Connected Component Labeling

Kirill Osenkov — Wed, 18 Jun 2008 01:17:13 GMT

Morgan, thanks so much for sharing this, this is really interesting. It's great that you've found a way to improve performance and I think you're right - span tracking isn't really shining on random images.

I like your idea, it saves up memory because you don't have to initialize throw away collections every time.