Function iamstseeds

Description

Finds the nodes of a given graph that are connected directly to nodes with different labels. This is used to find seeds on an MST that ensure that on the calculation of the SPF-Max using these seeds, the labels of the nodes will be the same as of input. This is also known as finding the minimal set of seeds for a given segmentation.

Synopse

Create a list of indices that represent the nodes selected as seeds.

  • seeds = iamstseeds(MST, labels)
    • MST: the adjacency matrix of the graph that represents the MST
    • labels: the vector that has the labels of each node of the graph
 1 def iamstseeds(MST, labels):
 2     """
 3     Parameters:
 4         MST: the adjacency matrix of the graph that represents the MST
 5         labels: the vector that has the labels of each node of the graph
 6 
 7     >>> from numpy import array
 8     >>> MST = array([[inf, inf, inf,   4, inf, inf],
 9                      [inf, inf, inf, inf,   4, inf],
10                      [inf, inf, inf, inf,   3, inf],
11                      [  4, inf, inf, inf,   4,   5],
12                      [inf,   4,   3,   4, inf, inf],
13                      [inf, inf, inf,   5, inf, inf]])
14 
15     >>> labels = [1, 2, 2, 1, 2, 1]
16     >>> iamstseeds(MST, labels)
17     [3, 4]
18     >>>
19     """
20 
21     from numpy import where, array
22 
23     n = MST.shape[0]
24     if n != len(labels):
25         return []
26 
27     seeds = []
28 
29     for i in range(n):
30         w = MST[i,:]
31         wix = where(w != float("inf"))[0]
32         l = array(map(lambda x: labels[x], wix))
33         #wl = float(sum(l))/float(len(l))
34         lmin = l.min()
35         lmax = l.max()
36 
37         if l.min()!=l.max():
38            seeds.append(i)
39         elif lmin!= labels[i]:
40             seeds.append(i)
41 
42     return seeds

Examples

Example 1

 1 from numpy import array
 2 from iaOPF import *
 3 inf = float("inf")
 4 MST = array([[inf, inf, inf,   4, inf, inf],
 5              [inf, inf, inf, inf,   4, inf],
 6              [inf, inf, inf, inf,   3, inf],
 7              [inf, inf, inf, inf,   4,   5],
 8              [inf,   4,   3,   4, inf, inf],
 9              [inf, inf, inf,   5, inf, inf]])
10 labels = [1, 2, 2, 1, 2, 1]
11 seeds = iamstseeds(MST, labels)
12 print seeds
[3, 4]

Example 2

 1 from numpy import *
 2 from iaprim import iaprim
 3 from iaadjmxtcreate import iaadjmxtcreate
 4 from iamstseeds import iamstseeds
 5 
 6 adj_matrix = array([[inf,1,3,4],
 7                     [1,inf,2,5],
 8                     [3,2,inf,6],
 9                     [4,5,6,inf]])
10 
11 label_vector = array([0,0,0,1])
12 
13 print 'Adjacent Matrix \n',adj_matrix
14 MST = iaprim(adj_matrix)
15 print 'MST \n',MST
16 mmgraphviz(iaadjmxtcreate(adj_matrix,dist=True), title='Adjacent Matrix')
17 mmgraphviz(iaadjmxtcreate(MST,dist=True),title='MST')
18 
19 seeds = iamstseeds(MST,label_vector)
20 print 'seeds: \n',seeds
Adjacent Matrix 
[[ Inf   1.   3.   4.]
 [  1.  Inf   2.   5.]
 [  3.   2.  Inf   6.]
 [  4.   5.   6.  Inf]]
MST 
[[ Inf   1.  Inf   4.]
 [  1.  Inf   2.  Inf]
 [ Inf   2.  Inf  Inf]
 [  4.  Inf  Inf  Inf]]
seeds: 
[0, 3]
/media/_xsb/iaOPF/iamstseeds/GRVIZ14074_001.png

Adjacent Matrix

/media/_xsb/iaOPF/iamstseeds/GRVIZ14074_002.png

MST

Example 3

 1 from numpy import *
 2 from iaprim import iaprim
 3 from iaadjmxtcreate import iaadjmxtcreate
 4 from iamstseeds import iamstseeds
 5 
 6 adj_matrix = array([[inf,inf,inf,inf,0.88],
 7                     [inf,inf,inf,1.97,1.06],
 8                     [inf,inf,inf,1.97,inf],
 9                     [inf,1.97,1.97,inf,inf],
10                     [0.88,1.06,inf,inf,inf]])
11 
12 label_vector = array([2,1,0,1,2])
13 
14 print 'Adjacent Matrix \n',adj_matrix
15 MST = iaprim(adj_matrix)
16 print 'MST \n',MST
17 mmgraphviz(iaadjmxtcreate(adj_matrix, dist=True), title='Adjacent Matrix')
18 mmgraphviz(iaadjmxtcreate(MST,dist=True),title='MST')
19 
20 seeds = iamstseeds(MST,label_vector)
21 print 'seeds: \n',seeds
Adjacent Matrix 
[[  Inf   Inf   Inf   Inf  0.88]
 [  Inf   Inf   Inf  1.97  1.06]
 [  Inf   Inf   Inf  1.97   Inf]
 [  Inf  1.97  1.97   Inf   Inf]
 [ 0.88  1.06   Inf   Inf   Inf]]
MST 
[[  Inf   Inf   Inf   Inf  0.88]
 [  Inf   Inf   Inf  1.97  1.06]
 [  Inf   Inf   Inf  1.97   Inf]
 [  Inf  1.97  1.97   Inf   Inf]
 [ 0.88  1.06   Inf   Inf   Inf]]
seeds: 
[1, 2, 3, 4]
/media/_xsb/iaOPF/iamstseeds/GRVIZ14074_003.png

Adjacent Matrix

/media/_xsb/iaOPF/iamstseeds/GRVIZ14074_004.png

MST