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

[wassim24]

I'm trying to implement the Connected Components Labeling in C++ with Qt but i'm struggling in implementing the equivalence table and having some problems to understand how to work with it.
Here is what i've done so far :

for (int x = 0; x < image.width(); ++x) {
    for (int y = 0; y < image.height(); ++y) {
 
        color = image.pixel(x,y);
 
        if(color.red() == 0)
            imageLabeled.setPixel(x,y, qRgb(0,0,0));
 
        else{
            color1 = imageLabeled.pixel(x, y-1);
            color2 = imageLabeled.pixel(x-1, y);
 
            if(color1.red() == 0 && color2.red() == 0)
            {
                imageLabeled.setPixel(x,y, qRgb(label, label, label));
                label+=1;
 
            }else if(color1.red() == 0 && color2.red() != 0)
                imageLabeled.setPixel(x,y,color2.rgb());
 
 
            else if(color1.red() != 0 && color2.red() == 0)
                imageLabeled.setPixel(x,y, color1.rgb());
 
            else if(color1.red() != 0 && color2.red() != 0)
            {
                if(color1.red() < color2.red())
                    imageLabeled.setPixel(x,y, color1.rgb());
                else
                    imageLabeled.setPixel(x,y, color2.rgb());
            }
 
        }
 
    }
}

for (int x = 0; x < image.width(); ++x) {
    for (int y = 0; y < image.height(); ++y) {

        color = image.pixel(x,y);

        if(color.red() == 0)
            imageLabeled.setPixel(x,y, qRgb(0,0,0));

        else{
            color1 = imageLabeled.pixel(x, y-1);
            color2 = imageLabeled.pixel(x-1, y);

            if(color1.red() == 0 && color2.red() == 0)
            {
                imageLabeled.setPixel(x,y, qRgb(label, label, label));
                label+=1;

            }else if(color1.red() == 0 && color2.red() != 0)
                imageLabeled.setPixel(x,y,color2.rgb());


            else if(color1.red() != 0 && color2.red() == 0)
                imageLabeled.setPixel(x,y, color1.rgb());

            else if(color1.red() != 0 && color2.red() != 0)
            {
                if(color1.red() < color2.red())
                    imageLabeled.setPixel(x,y, color1.rgb());
                else
                    imageLabeled.setPixel(x,y, color2.rgb());
            }

        }

    }
}

To copy to clipboard, switch view to plain text mode 

In this block of instructions i'm just searching for pixels to be labeled. There is no equivalence table or so.

Thanks you for your help !
Cheers !

[wysota]

What exactly is the question?

BTW. Is this some kind of school project?

[wassim24]

Sorry for not being clear

My question was : If i was to implement the equivalence table, which is a table containing all sets having a relation with other sets, what qt object should i use ?
Here is an example :
The label equivalence relationships generated are,

Set ID	Equivalent Labels
1         1,2
2	  1,2
3	  3,4,5,6,7
4	  3,4,5,6,7
5	  3,4,5,6,7
6	  3,4,5,6,7
7	  3,4,5,6,7

Set ID	Equivalent Labels
1         1,2
2	  1,2
3	  3,4,5,6,7
4	  3,4,5,6,7
5	  3,4,5,6,7
6	  3,4,5,6,7
7	  3,4,5,6,7

To copy to clipboard, switch view to plain text mode 

Actually it is a part of a school project, i've made all the previous parts and i'm stuck just with annoying table :P

Thank your for your help !

[yeye_olive]

You do realize that we have no idea what you are talking about, right? What are these "sets"? Are you looking for a data structure to represent an equivalence relation efficiently?

Please state the problem you are trying to solve in terms of:
- the information you receive as input;
- what you are supposed to output.

By the way, we have yet to understand what this has to do with Qt.

[wysota]

In wikipedia there is a description of an algorithm you should implement. I don't know what is your input data but I don't think Qt is going to be helpful here that much. Of course you could use Qt types such as QGenericMatrix but I don't see many benefits over other (e.g. pure c++) types.

[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 !