Results 1 to 10 of 10

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

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1

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

    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

  2. #2
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,368
    Thanks
    3
    Thanked 5,018 Times in 4,794 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

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

    For each point you can have a list where you can add and remove labels. You can use QSet for that.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  3. #3
    Join Date
    Jan 2008
    Location
    Alameda, CA, USA
    Posts
    5,323
    Thanks
    316
    Thanked 871 Times in 858 Posts
    Qt products
    Qt5
    Platforms
    Windows

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

    You could also use QMap and QList like this:

    Qt Code:
    1. // Assuming your IDs are ints:
    2.  
    3. typedef QMap< int, QList< int > > EquivalenceTable;
    4.  
    5. EquivalenceTable eqTable;
    6.  
    7. eqTable[1] << 1 << 2;
    8.  
    9. QList< int > oneEquivalents = eqTable[1]; // returns a QList containing 1, 2
    10.  
    11. // etc
    To copy to clipboard, switch view to plain text mode 

  4. #4
    Join Date
    Oct 2009
    Posts
    483
    Thanked 97 Times in 94 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows

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

    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.

  5. #5

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

    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 !

Similar Threads

  1. Replies: 3
    Last Post: 9th September 2013, 01:52
  2. Replies: 1
    Last Post: 10th May 2011, 18:58
  3. Replies: 0
    Last Post: 4th May 2011, 12:33
  4. Best way to implement a table in a QGraphicsScene?
    By roband915 in forum Qt Programming
    Replies: 3
    Last Post: 31st March 2011, 11:56
  5. Replies: 4
    Last Post: 26th October 2009, 22:25

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Qt is a trademark of The Qt Company.