I am writing a function to label the connected component in an image (I know the

Question

I am writing a function to label the connected component in an image (I know there are several libraries outside, I just wanted to play with the algorithm).

To do this I label the connected regions with different labels and create an equivalence table that contain information on the labels belonging to the same connected component.

As an example if my equivalence table (vector of vector) looks something like:

1:    1,3
2:    2,3
3:    1,2,3
4:    4
It means that in the image there are 2 different regions, one made of elements that are labelled 1,2,3 and an other made of elements labelled 4.

What is an easy and efficient way to resolve the equivalences and end up with something that looks like:

1: 1,2,3
2: 4
that I can use to "merge" the different connected regions belonging to the same connected component?

Thanks a lot for the help!

Explanation / Answer

You probably want a disjoint set datastructure. This yields near-constant amortized performance per operation, and can be made very efficient for the kind of task you describe.

Briefly, each equivalence class is stored as an "inverted tree": each node has a parent link, but no child links. A "query" follows the parent links until they reach the root (which can be marked by having itself as a parent). Note that every node in the same tree will yield the same root, which is the "exemplar" representing that equivalence class.

Nodes typically start out as their own equivalence class (that is, they are initialized as a tree consisting of just the root). To merge two equivalence classes, find the root of each, and make one the parent of the other.

By adding two simple optimizations (always "collapse" query paths to point directly to the root, and always choose the root of the deeper tree as merge parent), you gain "near-constant" amortized worst case performance for your operations.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.