How to implement the equivalence table in connected component labeling c++ Qt

[wassim24]

I'm sorry !
Yes ! I'm looking for a data structure to represent an equivalence relation efficiently.

Suppose i have a binary image, this image contains blobs (Connected White regions), i have to label them, but when labeling i have some issues where a same regions gets two labels, at this time i should put the the two different labels in a table, the equivalence table.

As an output the labeled image but all labels have been replaced by the minimum equivalent labels in the table.

The problem why i ask my question in the Qt forums is to know if there is a data structure right in Qt that can help me make this table ?

Thank you in advance and sorry for my bad english !

Have a good night or a nice day

[wysota]

For each point you can have a list where you can add and remove labels. You can use QSet for that.

[d_stranz]

You could also use QMap and QList like this:

// Assuming your IDs are ints:
 
typedef QMap< int, QList< int > >  EquivalenceTable;
 
EquivalenceTable  eqTable;
 
eqTable[1] << 1 << 2;  
 
QList< int >  oneEquivalents = eqTable[1];  // returns a QList containing 1, 2
 
// etc

// Assuming your IDs are ints:

typedef QMap< int, QList< int > >  EquivalenceTable;

EquivalenceTable  eqTable;

eqTable[1] << 1 << 2;  

QList< int >  oneEquivalents = eqTable[1];  // returns a QList containing 1, 2

// etc

To copy to clipboard, switch view to plain text mode 

[yeye_olive]

If, given a pixel, you want to determine the largest connected monochrome region of the image containing that pixel, then this is just a graph traversal in an undirected graph, and a simple depth-first search suffices. In particular, there is no need to merge several regions.

If, however, you have a clever way to delimit regions in an image and later want to merge some of them, then this looks to me like the perfect application for a union-find data structure.

An union-find data structure maintains an equivalence relation on a set. It supports two operations:
- find(x): returns a canonical representative of x's equivalence class;
- union(x, y): merge x's and y's equivalence classes.
In other words, the equivalence relation represented by the union-find is the smallest equivalence relation containing the pair (x, y) for all calls to union(x, y) since the beginning.

A union-find can be represented efficiently by associating a "last computed representative" to each non-isolated element in the set. A plain C array can do if the set is small, or a QHash if it is larger. union(x, y) makes x's representative be represented by y's representative (or the opposite), but lazily leaves all other representatives untouched. find(x) follows the chains of "last computed representatives" from x until it finds the current representative c, and takes the opportunity to compress the data structure by remapping all the visited elements to c, thus speeding up subsequent lookups.

You can probably find the details online.

Again, this is just a shot in the dark as you still haven't explained in details what you are trying to achieve.

[wassim24]

Hi Guys !
Sorry for my late answer as i've been a bit busy these days.

Thank you for all your answers !

@wysota, the problem with this solution is that sometimes you need to insert a label in a particular "position", for exemple list[label] = equiValentLabel, which can generate some errors.
@d_stranz i will try your solution as soon as possible and keep you in touch, it seems that it may work very well !

@yeye_olive, this is exactly what i'm trying to do, a union-find.

Thank you very much guys !