Merging Segments in an Image

I'll walk though some code for merging segments in an image using a two classes, Segment and Segments. The first class is for 


class Segment:
    def __init__( self, elements, neighbors, class ):
        self.elements = [ elements ] # tuple addresses
        self.neighbors = neighbors # class labels
        self.class = class # personal class
        self.quality = None # either textured or smooth
        self.mean = None # mean reflectance
        self.texture = None # texture vector


<< OTHER CODE >>

    def merge( self, a, b ):

        # enhance readabilityness

        newclass = a.class

        oldclass = b.class

        # a subsumes b's elements 

        a.elements += b.elements 

        # set of class labels

        # the class labels neighboring a and the class label of a

        mine = set( a.neighbors + [ newclass ] )

        # set of class labels

        # the class labels neighboring b and the class lebel of b

        theirs = set( b.neighbors + [ oldclass ] )

        # set of class labels for elements of a (after adding b to a)

        ours = set( [ self.element_segment[i] for i in a.elements ] )

        # update a's new neighbors

        a.neighbors = list( mine.union( theirs ) - ours ) 

        # update class elementship of b's elements

        for m in b.elements:

            self.element_segment[ m ] = newclass 

            self.segment_element[ newclass ].append( m ) 

        # remove the oldclass from the dict of classes

        del self.segment_element[ oldclass ] 

        # remove the oldclass from the dict of segments

        del self.segments[ oldclass ]

        # update old neighbors of the oldclass

        for s in self.segments:

            if oldclass in self.segments[s].neighbors:

                while oldclass in self.segments[s].neighbors:

                    self.segments[s].neighbors.remove( oldclass )

                if newclass not in self.segments[s].neighbors:

                    self.segments[s].neighbors.append( newclass )

        

What the merge() function does, is figure out the new elements of the new segment (easy), figure out the new neighbors of the new segment (harder), and then do some cleaning operations.

In the merge() function, newclass = a.class and oldclass = b.class take the class labels of the segments to be merged, a and b. In this implementation, a is dominant, and subsumes b's class label.

Then, with a.elements += b.elements, we add the elements of b to the elements of a. These elements are tuple addresses for image chips, or individual pixels.

Imagine the following setup:

|---|---|---|---|

| 3 | 8 | 8 | 8 |

|---|---|---|---|

| 3 | 1 | 2 | 7 |

|---|---|---|---|

| 4 | 1 | 2 | 7 |

|---|---|---|---|

| 4 | 4 | 5 | 6 |

|---|---|---|---|

Here, segment a is denoted by the ones, and segment b is denoted by the twos. The line mine = set( a.neighbors + [ newclass ] ) is just the set {3,4,2,8,1}, the class labels for the n,s,e,w neighbors of segment a, which are {3,4,2,8}, and the class label for a, which is {1}. Similarly for theirs we have the class labels for the neighbors of b, and the class label for b, and this ends up being the set {1,8,7,5,2}. Then ours is the class labels in the new segment, which will be the set {1,2}, since 1 and 2 are the class labels of segment a and segment b.

Then the new neighbors of the new segment will be found by taking the union of mine and theirs, which is {3,8,4,7,5,1,2}, and then tossing ours, giving us the set {3,4,8,7,5}, and these are the tiles ordinally neighboring the tiles labeled 1 and 2. Note that tile 6 is not considered a neighbor because it is to the south-east of tile 2; only tiles that share a whole side are counted as neighbors.

After cleaning up the requisite dictionaries that keep track of these things, we should have the following diagram,

|---|---|---|---|

| 3 | 8 | 8 | 8 |

|---|---|---|---|

| 3 | 1 | 1 | 7 |

|---|---|---|---|

| 4 | 1 | 1 | 7 |

|---|---|---|---|

| 4 | 4 | 5 | 6 |

|---|---|---|---|