Newer
Older
################################################################
# lg.py - Label Graph Class
# Authors: R. Zanibbi and H. Mouchere, 2012
# Copyright (c) 2012-2014 Richard Zanibbi and Harold Mouchere
################################################################
import csv
import sys
import math
import copy
import compareTools
import os
class Lg(object):
"""Class for bipartite graphs where the two node sets are identical, and
multiple node and edge labels are permited. The graph and individual nodes
and edges have associated values (e.g. weights/probabilities)."""
# Define graph data elements ('data members' for an object in the class)
__slots__ = ('file','gweight','nlabels','elabels','error','absentNodes',\
'absentEdges','hiddenEdges', 'cmpNodes', 'cmpEdges')
##################################
# Constructors (in __init__)
##################################
def __init__(self,*args):
"""Graph data is read from a CSV file or provided node and edge label
dictionaries. If invalid entries are found, the error flag is set to
true, and graph input continues. In .lg files, blank lines are
ignored, and # may be used for comment lines in CSV graph files."""
self.error = False
self.gweight = 1.0
self.nlabels = {}
self.elabels = {}
self.absentNodes = set([])
self.absentEdges = set([])
self.hiddenEdges = {}
self.cmpNodes = compareTools.cmpNodes
self.cmpEdges = compareTools.cmpEdges
fileName = None
nodeLabels = {}
edgeLabels = {}
if len(args) == 1:
fileName = args[0]
self.file = fileName # DEBUG: add filename for debugging purposes.
elif len(args) == 2:
nodeLabels = args[0]
edgeLabels = args[1]
if fileName == None:
# CONSTRUCTOR 1: try to read in node and edge labels.
self.file = None
# Automatically convert identifiers and labels to strings if needed.
for nid in nodeLabels.keys():
if not isinstance(nid, str):
nid = str(nid)
newdict = {}
for label in nodeLabels[nid].keys():
if not isinstance(nid, str):
label = str(label)
# Weights need to be floats.
if not isinstance( nodeLabels[nid][label], float ):
self.error = True
sys.stderr.write(' !! Invalid weight for node ' + nid + ', label \"' \
+ label +"\": " + str(nodeLabels[nid][label]) + "\n")
newdict[ label ] = nodeLabels[nid][label]
self.nlabels[nid] = newdict
# WARNING: self-edges are not detected if edge labels used
# for initialization.
for eid in edgeLabels.keys():
if not isinstance(eid[0], str) or not isinstance(eid[1],str):
eid[0] = str(eid[0])
eid[1] = str(eid[1])
newdict = {}
for label in edgeLabels[eid].keys():
if not isinstance(label, str):
label = str(label)
if not isinstance( edgeLabels[eid][label], float ):
self.error = True
sys.stderr.write(' !! Invalid weight for edge ' + str(eid) + ', label \"' \
+ label +"\": " + str(edgeLabels[eid][label]) + "\n")
newdict[ label ] = edgeLabels[eid][label]
self.elabels[eid] = newdict
else:
# CONSTRUCTOR 2: Read graph data from CSV file.
MIN_NODE_ENTRY_LENGTH = 3
MIN_EDGE_ENTRY_LENGTH = 4
MIN_OBJECT_ENTRY_LENGTH = 5
MIN_OBJECT_EDGE_ENTRY_LENGTH = 5
try:
fileReader = csv.reader(open(fileName))
except:
# Create an empty graph if a file cannot be found.
# Set the error flag.
sys.stderr.write(' !! IO Error (cannot open): ' + fileName + '\n')
self.error = True
return
objectDict = dict([])
for row in fileReader:
# Skip blank lines.
if len(row) == 0 or len(row) == 1 and row[0].strip() == '':
continue
entryType = row[0].strip()
if entryType == 'N':
if len(row) < MIN_NODE_ENTRY_LENGTH:
sys.stderr.write(' !! Invalid node entry length: ' +str(len(row))+\
'\n\t' + str(row) + '\n')
self.error = True
else:
nid = row[1].strip() # remove leading/trailing whitespace
if nid in self.nlabels.keys():
nlabelDict = self.nlabels[ nid ]
nlabel = row[2].strip()
# if nlabel in nlabelDict:
# # Note possible error.
# sys.stderr.write(' !! Repeated node label entry ('\
# + self.file + '): ' \
# + '\n\t' + str(row) + '\n')
# self.error = True
# Add (or replace) entry for the label.
nlabelDict[ nlabel ] = float(row[3])
else:
# New primitive; create new dictionary for
# provided label (row[2]) and value (row[3])
nid = row[1].strip()
nlabel = row[2].strip()
# Feb. 2013 - allow no weight to be provided.
if len(row) > MIN_NODE_ENTRY_LENGTH:
self.nlabels[ nid ] = { nlabel : float(row[3]) }
else:
self.nlabels[ nid ] = { nlabel : 1.0 }
elif entryType == 'E':
if len(row) < MIN_EDGE_ENTRY_LENGTH:
sys.stderr.write(' !! Invalid edge entry length: ' +str(len(row))+\
'\n\t' + str(row) + '\n')
self.error = True
else:
primPair = ( row[1].strip(), row[2].strip() )
#self to self edge = error
if primPair[0] == primPair[1]:
sys.stderr.write(' !! Invalid self-edge (' +
self.file + '):\n\t' + str(row) + '\n')
self.error = True
nid = primPair[0]
if nid in self.nlabels.keys():
nlabelDict = self.nlabels[ nid ]
nlabel = row[3].strip()
# if nlabel in nlabelDict:
# # Note possible error.
# sys.stderr.write(' !! Repeated node label entry ('\
# + self.file + '): ' \
# + '\n\t' + str(row) + '\n')
# Add (or replace) entry for the label.
nlabelDict[ nlabel ] = float(row[4])
#an edge already existing, add a new label
elif primPair in self.elabels.keys():
elabelDict = self.elabels[ primPair ]
elabel = row[3].strip()
# if elabel in elabelDict:
# # Note possible error.
# sys.stderr.write(' !! Repeated edge label entry (' \
# + self.file + '):\n\t' + str(row) + '\n')
# self.error = True
if elabel == '*':# if it uses the old fashion segmentation label, convert it by finding the (only) node label
if primPair[0] in self.nlabels and primPair[1] in self.nlabels and \
self.nlabels[ primPair[0]] == self.nlabels[ primPair[1]]:
elabel = list(self.nlabels[ primPair[0]].keys())[0]
else:
sys.stderr.write(' !! * edge used with ambiguous node labels (' \
+ str(self.nlabels[ primPair[0]]) + ' vs. ' \
+ str(self.nlabels[ primtPair[1]]) + ') in ' \
+ self.file + '):\n\t' + str(row) + '\n')
self.error = True
# Add (or replace) entry for the label.
# Feb. 2013 - allow no weight.
if len(row) > MIN_EDGE_ENTRY_LENGTH:
elabelDict[ elabel ] = float(row[4])
else:
elabelDict[ elabel ] = 1.0
else:
# Add new edge label entry for the new edge label
# as a dictionary.
primPair = ( row[1].strip(), row[2].strip() )
elabel = row[3].strip()
if elabel == '*':# if it uses the old fashion segmentation label, convert it by finding the (only) node label
if primPair[0] in self.nlabels and primPair[1] in self.nlabels and \
self.nlabels[ primPair[0]] == self.nlabels[ primPair[1]]:
elabel = list(self.nlabels[ primPair[0]].keys())[0]
else:
sys.stderr.write(' !! * edge used with ambiguous node labels (' \
+ str(self.nlabels[ primPair[0]]) + ' vs. ' \
+ str(self.nlabels[ primPair[1]]) + ') in ' \
+ self.file + '):\n\t' + str(row) + '\n')
self.error = True
elif entryType == 'O':
if len(row) < MIN_OBJECT_ENTRY_LENGTH:
sys.stderr.write(' !! Invalid object entry length: '+str(len(row))+\
'\n\t' + str(row) + '\n')
self.error = True
else:
rawnodeList = row[4:] # get all other item as node id
oid = row[1].strip()
nlabel = row[2].strip()
nValue = float(row[3].strip())
nodeList = []
# add all nodes
for n in rawnodeList:
nid = n.strip()
nodeList.append(nid)
if nid in self.nlabels.keys():
nlabelDict = self.nlabels[ nid ]
# Add (or replace) entry for the label.
nlabelDict[ nlabel ] = nValue
else:
# New primitive; create new dictionary for
# provided label and value
# Feb. 2013 - allow no weight to be provided.
self.nlabels[ nid ] = { nlabel : nValue }
#save the nodes of this object
objectDict[oid] = nodeList
#add all edges
for nid1 in nodeList:
#nid1 = n1.strip()
for nid2 in nodeList:
#nid2 = n2.strip()
if nid1 != nid2:
primPair = ( nid1, nid2 )
elabel = nlabel#'*' #segmentation
if primPair in self.elabels.keys():
elabelDict = self.elabels[ primPair ]
# Add (or replace) entry for the label.
elabelDict[ elabel ] = nValue
else:
# Add new edge label entry for the new edge label
# as a dictionary.
self.elabels[ primPair ] = { elabel : nValue }
elif entryType == 'R' or entryType == 'EO':
if len(row) < MIN_OBJECT_EDGE_ENTRY_LENGTH:
sys.stderr.write(' !! Invalid object entry length: ' +str(len(row))+\
'\n\t' + str(row) + '\n')
self.error = True
else:
oid1 = row[1].strip()
oid2 = row[2].strip()
elabel = row[3].strip()
eValue = float(row[4].strip())
validRelationship = True
if not oid1 in objectDict:
sys.stderr.write(' !! Invalid object id: "' + oid1+\
'" - IGNORING relationship:\n\t' + str(row) + '\n')
self.error = True
validRelationship = False
if not oid2 in objectDict:
sys.stderr.write(' !! Invalid object id: "' + oid2+\
'" - IGNORING relationship:\n\t' + str(row) + '\n')
self.error = True
validRelationship = False
if validRelationship:
nodeList1 = objectDict[oid1] # get all other item as node id
nodeList2 = objectDict[oid2] # get all other item as node id
for nid1 in nodeList1:
for nid2 in nodeList2:
if nid1 != nid2:
primPair = ( nid1, nid2 )
if primPair in self.elabels.keys():
elabelDict = self.elabels[ primPair ]
# Add (or replace) entry for the label.
elabelDict[ elabel ] = eValue
else:
# Add new edge label entry for the new edge label
# as dictionary.
self.elabels[ primPair ] = { elabel : eValue }
else:
sys.stderr.write(' !! Invalid self-edge (' +
self.file + '):\n\t' + str(row) + '\n')
self.error = True
# DEBUG: complaints about empty lines here...
elif len(entryType.strip()) > 0 and entryType.strip()[0] == '#':
# Ignore lines with comments.
pass
else:
sys.stderr.write(' !! Invalid graph entry type (expected N, E, O, R or EO): ' \
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
+ str(row) + '\n')
self.error = True
# Add any implicit nodes in edges explicitly to the hash table
# containing nodes. The 'nolabel' label is '_'.
anonNode = False
anodeList = []
for elabel in self.elabels.keys():
nid1 = elabel[0]
nid2 = elabel[1]
if not nid1 in self.nlabels.keys():
self.nlabels[ nid1 ] = { '_' : 1.0 }
anodeList = anodeList + [ nid1 ]
anonNode = True
if not nid2 in self.nlabels.keys():
self.nlabels[ nid2 ] = { '_' : 1.0 }
anodeList = anodeList + [ nid2 ]
anonNode = True
if anonNode:
sys.stderr.write(' ** Anonymous labels created for:\n\t' \
+ str(anodeList) + '\n')
##################################
# String, CSV output
##################################
def __str__(self):
nlabelcount = 0
elabelcount = 0
for nid in self.nlabels.keys():
nlabelcount = nlabelcount + len(self.nlabels[nid].keys())
for eid in self.elabels.keys():
elabelcount = elabelcount + len(self.elabels[eid].keys())
return 'Nodes: ' + str(len(self.nlabels.keys())) \
+ ' (labels: ' + str(nlabelcount) \
+ ') Edges: ' + str(len(self.elabels.keys())) \
+ ' (labels: ' + str(elabelcount) \
+ ') Error: ' + str(self.error)
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
def csvObject(self):
"""Construct CSV data file using object-relationship format. Currently
weight values are only placeholders (i.e. 1.0 is always used)."""
outputString = ""
(segmentPrimitiveMap, primitiveSegmentMap, rootSegments, \
segmentEdges) = self.segmentGraph()
# Write the file name.
outputString += "# " + os.path.split(self.file)[1]
outputString += "\n\n"
# Write number of objects and format information.
# Output object information.
outputString += "# " + str(len(segmentPrimitiveMap.keys())) + " Objects"
outputString += "\n"
outputString += "# FORMAT: O, Object ID, Label, Weight, [ Primitive ID List ]"
outputString += "\n"
for objectId in sorted( segmentPrimitiveMap.keys() ):
for label in sorted(segmentPrimitiveMap[objectId][1]):
outputString += "O, " + objectId + ", " + label + ", 1.0"
for primitiveId in sorted( segmentPrimitiveMap[ objectId ][ 0 ] ):
outputString += ", " + primitiveId
outputString += "\n"
# Write number of relationships and format information.
# Write relationship information.
outputString += "\n"
outputString += "# " + str( len(segmentEdges.keys()) ) + " Relationships (Pairs of Objects)"
outputString += "\n"
outputString += "# FORMAT: R, Object ID (parent), Object ID (child), Label, Weight"
outputString += "\n"
for (parentObj, childObj) in sorted( segmentEdges.keys() ):
for relationship in sorted( segmentEdges[ (parentObj, childObj) ].keys() ):
outputString += "R, " + parentObj + ", " + childObj + ", "
outputString += relationship + ", 1.0"
outputString += "\n"
return outputString
def csv(self):
"""Construct CSV data file representation as a string."""
# NOTE: currently the graph value is not being stored...
sstring = ''
nlist = []
elist = []
for nkey in self.nlabels.keys():
nodeLabels = self.nlabels[nkey]
for nlabel in nodeLabels.keys():
nstring = 'N,' + nkey + ',' + nlabel + ',' + \
str(nodeLabels[nlabel]) + '\n'
nlist = nlist + [ nstring ]
for npair in self.elabels.keys():
edgeLabels = self.elabels[npair]
for elabel in edgeLabels.keys():
estring = 'E,' + npair[0] + ',' + npair[1] + ',' + elabel + ',' + \
str(edgeLabels[ elabel ]) + '\n'
elist = elist + [ estring ]
# Sort the node and edge strings lexicographically.
# NOTE: this means that '10' precedes '2' in the sorted ordering
nlist.sort()
elist.sort()
sstring += '# ' + os.path.split(self.file)[1] + '\n\n'
sstring += '# ' + str(len(nlist)) + ' Nodes\n'
sstring += "# FORMAT: N, Primitive ID, Label, Weight\n"
sstring += "\n"
sstring += '# ' + str(len(elist)) + ' Edges\n'
sstring += '# FORMAT: E, Primitive ID (parent), Primitive ID (child), Label, Weight\n'
for estring in elist:
sstring = sstring + estring
return sstring
##################################
# Construct segment-based graph
# for current graph state
##################################
def segmentGraph(self):
"""Return dictionaries from segments to strokes, strokes to segments,
segments without parents, and edges labeled as segment ('*')."""
primitiveSegmentMap = {}
segmentPrimitiveMap = {}
#noparentSegments = []
segmentEdges = {} # Edges between detected objects (segments)
self.hideUnlabeledEdges()
# Note: a segmentation edge in either direction merges a primitive pair.
primSets = {}
for node,labs in self.nlabels.items():
primSets[node] = {}
for l in labs:
(cost,_)=self.cmpNodes([l],[])
if(cost > 0):
primSets[node][l] = set([node])
#if len(primSets[node]) == 0:
# primSets[node]['_'] = set([node]) #at least one empty label
commonLabels = set(self.nlabels[n1].keys()).intersection(self.nlabels[n2].keys(),self.elabels[(n1,n2)].keys())
for l in commonLabels:
#check if this label is interesting or not => compare to 'nothing', if there is not error, it means it is not interesting
(cost,_)=self.cmpNodes([l],[])
if(cost > 0):
primSets[n1][l].add(n2)
primSets[n2][l].add(n1)
# NOTE: Segments can have multiple labels
# A primitive can belong to several different
# segments with different sets of primitives with different labels.
# but there is only one segment with the same label attached to each primitive.
# For each label associated with each primitive, there is a possible object/segment
for primitive,segments in primSets.items():
if not primitive in primitiveSegmentMap:
primitiveSegmentMap[ primitive ] = {}
for lab in segments.keys():
alreadySegmented = False
for j in range(len(segmentList)):
if segments[lab] == segmentList[j]["prim"]:
if not primitive in primitiveSegmentMap:
primitiveSegmentMap[ primitive ] = {}
primitiveSegmentMap[ primitive ][lab] = 'Obj' + str(j)
alreadySegmented = True
if lab not in segmentList[j]["label"]:
segmentPrimitiveMap[ 'Obj' + str(j) ][1].append(lab)
segmentList[j]["label"].add(lab)
break
if not alreadySegmented:
# Add the new segment.
newSegment = 'Obj' + str(i)
segmentList = segmentList + [ {"label":{lab},"prim":primSets[primitive][lab]} ]
segmentPrimitiveMap[ newSegment ] = (segments[lab],[lab])
primitiveSegmentMap[ primitive ][lab] = newSegment
rootSegments.add(newSegment)
i += 1
# Identify 'root' objects/segments (i.e. with no incoming edges),
# and edges between objects. **We skip segmentation edges.
for (n1, n2), elabs in self.elabels.items():
segment2 = primitiveSegmentMap[n2]
#for all possible pair of segments with these two primitives, look for the effective relation labels
possibleRelationLabels = set(elabs.keys()).difference(self.nlabels[n1].keys(),self.nlabels[n2].keys())
if len(possibleRelationLabels) != 0:
#for all pair of labels
for l1,pset1 in segment1.items():
for l2, pset2 in segment2.items():
#if not in the same seg
if pset1 != pset2:
#look for the label which is common for all primitive pair in the two segments
theRelationLab = possibleRelationLabels
for p1 in primSets[n1][l1]:
for p2 in primSets[n2][l2]:
if(p1,p2) in self.elabels:
theRelationLab &= set(self.elabels[(p1,p2)].keys())
else:
theRelationLab = set([]) # it should be a clique !
if len(theRelationLab) == 0:
break
if len(theRelationLab) == 0:
break
# there is a common relation if theRelationLab is not empty
if len(theRelationLab) != 0:
#we can remove seg2 from the roots
if pset2 in rootSegments:
rootSegments.remove(pset2)
#print (str((n1, n2))+ " => " + str(( pset1, pset2)) + " = " + str(theRelationLab))
for label in theRelationLab:
#check if this label is interesting or not => compare to 'nothing', if there is not error, it means it is not interesting
(cost,_)=self.cmpNodes([label],[])
if(cost > 0):
if ( pset1, pset2) in segmentEdges:
if label in segmentEdges[ ( pset1, pset2) ]:
# Sum weights for repeated labels
segmentEdges[ ( pset1, pset2)][label] += \
self.elabels[(n1,n2)][label]
else:
# Add unaltered weights for new edge labels
segmentEdges[ ( pset1, pset2) ][label] = \
self.elabels[(n1,n2)][label]
segmentEdges[ ( pset1, pset2) ] = {}
segmentEdges[ ( pset1, pset2) ][label] = \
self.elabels[(n1,n2)][label]
self.restoreUnlabeledEdges()
return (segmentPrimitiveMap, primitiveSegmentMap, list(rootSegments), \
segmentEdges)
##################################
# Metrics and Graph Differences
##################################
def compareSegments(self, lg2):
"""Compute the number of differing segments, and record disagreements.
The primitives in each graph should be of the same number and names
(identifiers). Nodes are merged that have identical (label,value)
pairs on nodes and all incoming and outgoing edges."""
(sp1, ps1, _, sre1) = self.segmentGraph()
(sp2, ps2, _, sre2) = lg2.segmentGraph()
allNodes = set(ps1.keys())
assert allNodes == set(ps2.keys())
edgeDiffCount = 0
edgeDiffClassCount = 0
correctSegments = set([])
correctSegmentsAndClass = set([])
undirDiffClassSet = set([])
# List and count errors due to segmentation.
# Use cmpNodes to compare the labels of symbols.
# Idea : build the sub graph with the current primitive as center and only
#print("IN---")
edgeFromP1 = {}
edgeFromP2 = {}
for (lab1,seg1) in ps1[primitive].items():
for p in sp1[seg1][0]:
# DEBUG (RZ): this is producing a primitive edge-level count:
# do not count segment edges that are undefined (e.g. in one direction,
# but not the other)
if p != primitive and (p,primitive) in self.elabels.keys() and \
lab1 in self.elabels[ (p,primitive) ].keys():
if p in edgeFromP1:
edgeFromP1[p].append(lab1)
else:
edgeFromP1[p] = [lab1]
for (lab2,seg2) in ps2[primitive].items():
for p in sp2[seg2][0]:
# DEBUG (RZ) - see DEBUG comment above.
if p != primitive and (p,primitive) in lg2.elabels.keys() and \
lab2 in lg2.elabels[ (p, primitive) ].keys():
if p in edgeFromP2:
edgeFromP2[p].append(lab2)
else:
edgeFromP2[p] = [lab2]
# Compute differences in edges labels with cmpNodes (as they are symbol labels)
diff1 = set([])
diff2 = set([])
# first add differences for shared primitives
commonPrim = set(edgeFromP1.keys()).intersection(edgeFromP2.keys())
for p in commonPrim:
(cost,diff) = self.cmpNodes(edgeFromP1[p], edgeFromP2[p])
edgeDiffCount = edgeDiffCount + cost
if cost > 0: # somehow they disagree, thus add in both sets
diff1.add(p)
diff2.add(p)
# RZ: Record edges that are specifically valid merges with disagreeing labels.
# Also record sets of undirected edges that disagree.
for (l1,l2) in diff:
if l1 in self.nlabels[p].keys() and l2 in lg2.nlabels[p].keys():
edgeDiffClassCount += 1
if not (p, primitive) in undirDiffClassSet and not (primitive, p) in undirDiffClassSet:
undirDiffClassSet.add( (primitive, p) )
#then add differences for primitives which are not in the other set
for p in (set(edgeFromP1.keys()) - commonPrim):
(cost,diff) = self.cmpNodes(edgeFromP1[p], [])
edgeDiffCount = edgeDiffCount + cost
diff1.add(p)
for p in (set(edgeFromP2.keys()) - commonPrim):
(cost,diff) = self.cmpNodes(edgeFromP2[p], [])
edgeDiffCount = edgeDiffCount + cost
diff2.add(p)
# Only create an entry where there are disagreements.
if len(diff1) + len(diff2) > 0:
segDiffs[primitive] = ( diff1, diff2 )
# Look for correct segments, ie primitive sets which are the same in both graphs
# NOTE: even if this algorithm is not symmetric, the result is symmetric
for (lab1,seg1) in ps1[primitive].items():
if(seg1, lab1) not in correctSegmentsAndClass: # already found, no need to search
for (lab2,seg2) in ps2[primitive].items():
if sp1[seg1][0] == sp2[seg2][0] and not lab1 == 'ABSENT' and not lab2 == 'ABSENT':
correctSegments.add(seg1)
(cost,_) = self.cmpNodes([lab1],[lab2])
if (cost == 0):
correctSegmentsAndClass.add((seg1, lab1))
# Compute total number of object classifications (recognition targets)
nbSegmClass = 0
for (_,labs) in sp2.items():
nbSegmClass += len(labs[1])
# Compute the specific 'object-level' graph edges that disagree, at the
# level of primitive-pairs.
primRelErrors = 0
correctSegRels = 0
correctSegRelLocations = 0
primRelEdgeDiffs = {}
error = False
misLabeled = False
falsePositive = False
thisParentIds = set(sp1[ thisPair[0] ][0])
thisChildIds = set(sp1[thisPair[1] ][0])
# Check whether the objects are correctly segmented (avoid counting
# over-segmented objects as having valid relationships)
if not ( thisPair[0] in correctSegments and thisPair[1] in correctSegments):
error = True
falsePositive = True # DEBUG - segments must be valid for a false positive.
# A 'correct' edge has the same label between all primitives
# in the two segments.
for parentId in thisParentIds:
for childId in thisChildIds:
# Distinguish relationship edge locations (structure) from label-only errors.
# DEBUG: compare only label sets, not confidence values.
if not (parentId, childId) in lg2.elabels.keys():
falsePositive = True
else:
(cost, diffLabelPairList) = self.cmpEdges(self.elabels[ (parentId, childId) ].keys(), \
lg2.elabels[ (parentId, childId) ].keys())
if not (0,[]) == (cost, diffLabelPairList):
misLabeled = True
# TO DO!! This assumes single labels on primitives.
if falsePositive or misLabeled:
primRelErrors += 1
primRelEdgeDiffs[ thisPair ] = [ ('Error',1.0) ]
# RZ DEBUG: count primitive edge errors separately from segment (i.e whole objects/symbols)
if error:
segRelErrors += 1
else:
correctSegRels += 1
# Count correct edge locations, even if mislabeled.
if not error or falsePositive == False:
correctSegRelLocations += 1
self.error |= error
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
# Compute object counts *without* inserted absent nodes.
lg2.removeAbsent()
self.removeAbsent()
(sp2orig, ps2orig, _, sre2orig) = lg2.segmentGraph()
(sp1orig, ps1orig, _, sre1orig) = self.segmentGraph()
nLg2Objs = len(sp2orig.keys())
nLg1Objs = len(sp1orig.keys())
# For input file, need to compare against all objects after including
# missing/additional absent nodes and edges.
nLg1ObjsAbsent = len(sp1.keys())
lg2.addAbsent(self)
self.addAbsent(lg2)
# RZ (Oct. 2014) Adding indicator variables for different correctness scenarios.
hasCorrectSegments = 1 if len(correctSegments) == nLg2Objs and \
len(correctSegments) == nLg1ObjsAbsent else 0
hasCorrectSegmentsAndLabels = 1 if len(correctSegmentsAndClass) == nLg2Objs and \
len(correctSegmentsAndClass) == nLg1ObjsAbsent else 0
hasCorrectRelationLocations = 1 if correctSegRelLocations == len(sre1.keys()) and \
correctSegRelLocations == len(sre2.keys()) else 0
hasCorrectRelationsAndLabels = 1 if correctSegRels == len(sre1.keys()) and \
correctSegRels == len(sre2.keys()) else 0
hasCorrectStructure = hasCorrectRelationLocations and hasCorrectSegments
# Compile vector of (name, value) metric pairs.
metrics = [
("edgeDiffClassCount", edgeDiffClassCount),
("undirDiffClassCount", len(undirDiffClassSet)),
("nSeg", nLg2Objs),
("detectedSeg", nLg1Objs),
("dSegRelEdges", len(sre1.keys())),
("CorrectSegments", len(correctSegments)),
("CorrectSegmentsAndClass", len(correctSegmentsAndClass)),
("ClassError", nbSegmClass - len(correctSegmentsAndClass)),
("CorrectSegRels",correctSegRels),
("CorrectSegRelLocations",correctSegRelLocations),
("SegRelErrors", segRelErrors),
("hasCorrectSegments", hasCorrectSegments),
("hasCorrectSegLab", hasCorrectSegmentsAndLabels),
("hasCorrectRelationLocations", hasCorrectRelationLocations),
("hasCorrectRelLab", hasCorrectRelationsAndLabels),
("hasCorrectStructure", hasCorrectStructure) ]
return (edgeDiffCount, segDiffs, correctSegments, metrics, primRelEdgeDiffs)
def compare(self, lg2):
"""Returns: 1. a list of (metric,value) pairs,
2. a list of (n1,n2) node disagreements, 3. (e1,e2) pairs
for edge disagreements, 4. dictionary from primitives to
disagreeing segment graph edges for (self, lg2). Node and
edge labels are compared using label sets without values, and
*not* labels sorted by value."""
metrics = []
nodeconflicts = []
edgeconflicts = []
# HM: use the union of all node labels instead of only lg2 ones
# it changes the nlabelMismatch, nodeClassError and so D_C and all rates values
allNodes = set(lg2.nlabels.keys()).union(self.nlabels.keys())
numNodes = len(allNodes)
(sp2, ps2, _, sre2) = lg2.segmentGraph()
nSegRelEdges = len(sre2)
# Handle case of empty graphs, and missing primitives.
# SIDE EFFECT: 'ABSENT' nodes added to each graph.
self.matchAbsent(lg2)
# METRICS
# Node and edge labels are considered as sets.
nlabelMismatch = 0
numEdges = numNodes * (numNodes - 1) # No self-edges.
numLabels = numNodes + numEdges
elabelMismatch = 0
# Mismatched nodes.
nodeClassError = set()
for nid in allNodes: #self.nlabels.keys():
(cost,errL) = self.cmpNodes(self.nlabels[nid].keys(),lg2.nlabels[nid].keys())
#if there is some error
if cost > 0:
# add mismatch
nlabelMismatch = nlabelMismatch + cost
# add errors in error list
for (l1,l2) in errL:
nodeconflicts = nodeconflicts + [ (nid, [ (l1, 1.0) ], [(l2, 1.0)] ) ]
# add node in error list
nodeClassError = nodeClassError.union([nid])
# Two-sided comparison of *label sets* (look from absent edges in both
# graphs!) Must check whether edge exists; '_' represents a "NONE"
# label (no edge).
# Identify the set of nodes with disagreeing edges.
nodeEdgeError = set()
for (graph,oGraph) in [ (self,lg2), (lg2,self) ]:
for npair in graph.elabels.keys():
if not npair in oGraph.elabels \
and (not graph.elabels[ npair ] == ['_']):
(cost,errL) = self.cmpEdges(graph.elabels[ npair ].keys(),['_'])
elabelMismatch = elabelMismatch + cost
nodeEdgeError.update([a,b])
# DEBUG: Need to indicate correctly *which* graph has the
# missing edge; this graph (1st) or the other (listed 2nd).
if graph == self:
for (l1,l2) in errL:
edgeconflicts.append((npair, [ (l1, 1.0) ], [(l2, 1.0)] ) )
for (l1,l2) in errL:
edgeconflicts.append((npair, [ (l2, 1.0) ], [(l1, 1.0)] ) )
# Obtain number of primitives with an error of any sort.
nodeError = nodeClassError.union(nodeEdgeError)
# One-sided comparison for common edges. Compared by cmpEdges
if npair in lg2.elabels.keys():
(cost,errL) = self.cmpEdges(self.elabels[npair].keys(),lg2.elabels[npair].keys())
if cost > 0:
elabelMismatch = elabelMismatch + cost
(a,b) = npair
# Record nodes in invalid edge
nodeEdgeError.update([a,b])
for (l1,l2) in errL:
edgeconflicts.append((npair, [ (l1, 1.0) ], [(l2, 1.0)] ) )
(segMismatch, segDiffs, correctSegs, segmentMetrics, segRelDiffs) \
= self.compareSegments(lg2)
# UNDIRECTED/NODE PAIR METRICS
# Compute number of invalid nodePairs
badPairs = {}
for ((n1, n2), _, _) in edgeconflicts:
if not (n2, n1) in badPairs:
badPairs[(n1, n2)] = True
incorrectPairs = len(badPairs)
# Compute number of mis-segmented node pairs.
badSegPairs = set([])
for node in segDiffs.keys():
for other in segDiffs[node][0]:
if node != other and (other, node) not in badSegPairs:
badSegPairs.add((node, other))
if node != other and (other, node)not in badSegPairs:
badSegPairs.add((node, other))
segPairErrors = len(badSegPairs)
# Compute performance metrics; avoid divisions by 0.
cerror = ("D_C", nlabelMismatch)
lerror = ("D_L", elabelMismatch)
rerror = ("D_R", elabelMismatch - segMismatch)
aerror = ("D_B", nlabelMismatch + elabelMismatch)
# DEBUG:
# Delta E BASE CASE: for a single node, which is absent in the other
# file, set label and segment edge mismatches to 1 (in order
# to obtain 1.0 as the error metric, i.e. total error).
if len(self.nlabels.keys()) == 1 and \
(len(self.absentNodes) > 0 or \
len(lg2.absentNodes) > 0):
elabelMismatch = 1
segMismatch = 1
errorVal = 0.0
if numEdges > 0:
errorVal += math.sqrt(float(segMismatch) / numEdges) + \
math.sqrt(float(elabelMismatch) / numEdges)
if numNodes > 0:
errorVal += float(nlabelMismatch) / numNodes
errorVal = errorVal / 3.0
eerror = ("D_E(%)", errorVal)
# Compile metrics
metrics = metrics + [ aerror, cerror, lerror, rerror, serror, \
eerror, \
("nNodes",numNodes), ("nEdges", numEdges), \
("nSegRelEdges", nSegRelEdges), \
("dPairs",incorrectPairs),("segPairErrors",segPairErrors),
("nodeCorrect", numNodes - len(nodeError)) ]
metrics = metrics + segmentMetrics
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
return (metrics, nodeconflicts, edgeconflicts, segDiffs, correctSegs,\
segRelDiffs)
##################################
# Manipulation/'Mutation'
##################################
def separateTreeEdges(self):
"""Return a list of root nodes, and two lists of edges corresponding to
tree/forest edges, and the remaining edges."""
# First, obtain segments; perform extraction on edges over segments.
(segmentPrimitiveMap, primitiveSegmentMap, noparentSegments, \
segmentEdges) = self.segmentGraph()
# Collect parents and children for each node; identify root nodes.
# (NOTE: root nodes provided already as noparentSegments)
nodeParentMap = {}
nodeChildMap = {}
rootNodes = set(segmentPrimitiveMap.keys())
for (parent, child) in segmentEdges:
if not child in nodeParentMap.keys():
nodeParentMap[ child ] = [ parent ]
rootNodes.remove( child )
else:
nodeParentMap[ child ] += [ parent ]
if not parent in nodeChildMap.keys():
nodeChildMap[ parent ] = [ child ]
else:
nodeChildMap[ parent ] += [ child ]
# Separate non-tree edges, traversing from the root.
fringe = list(rootNodes)
# Filter non-tree edges.
nonTreeEdges = set([])
while len(fringe) > 0:
nextNode = fringe.pop(0)
# Skip leaf nodes.
if nextNode in nodeChildMap.keys():
children = copy.deepcopy(nodeChildMap[ nextNode ])
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
for child in children:
numChildParents = len( nodeParentMap[ child ] )
# Filter edges to children that have more than
# one parent (i.e. other than nextNode)
if numChildParents == 1:
# Child in the tree found, put on fringe.
fringe += [ child ]
else:
# Shift edge to non-tree status.
nonTreeEdges.add((nextNode, child))
nodeChildMap[ nextNode ].remove(child)
nodeParentMap[ child ].remove(nextNode)
# Generate the tree edges from remaining child relationships.
treeEdges = []
for node in nodeChildMap:
for child in nodeChildMap[ node ]:
treeEdges += [ (node, child) ]
return (list(rootNodes), treeEdges, list(nonTreeEdges))
def removeAbsent(self):
"""Remove any absent edges from both graphs, and empty the fields
recording empty objects."""
for absEdge in self.absentEdges:
del self.elabels[ absEdge ]
for absNode in self.absentNodes:
del self.nlabels[ absNode ]
self.absentNodes = set([])
self.absentEdges = set([])
def addAbsent(self, lg2):
"""Identify edges in other graph but not the current one."""
selfNodes = set(self.nlabels.keys())
lg2Nodes = set(lg2.nlabels.keys())
self.absentNodes = lg2Nodes.difference(selfNodes)
# WARN about absent nodes/edges; indicate that there is an error.
if len(self.absentNodes) > 0:
sys.stderr.write(' !! Inserting ABSENT nodes for:\n ' \
+ self.file + ' vs.\n ' + lg2.file + '\n ' \
+ str(sorted(list(self.absentNodes))) + '\n')
self.error = True
# Add "absent" nodes.
# NOTE: all edges to/from "absent" nodes are unlabeled.