def persistence(im):
h, w = im.shape
- # Get indices orderd by value from high to low
+ # Get indices orderd by value from high to low. As a tie-breaker, we use
+ # (value, index) as key.
indices = [(i, j) for i in range(h) for j in range(w)]
- indices.sort(key=lambda p: get(im, p), reverse=True)
+ # We add p as a secondary key to have an unambiguous total order below when
+ # we enumerate neighboring cells of cells and consistency regarding
+ # "oldest" component.
+ indices.sort(key=lambda p: (get(im, p), p), reverse=True)
# Maintains the growing sets
uf = union_find.UnionFind()
for i, p in enumerate(indices):
v = get(im, p)
ni = [uf[q] for q in iter_neighbors(p, w, h) if q in uf]
+ # Sort by (value, index) as key. Note that this is the same sorting
+ # order as for indices. Otherwise we have an inconsistence notion of
+ # the "older" component!
nc = sorted([(get_comp_birth(q), q) for q in set(ni)], reverse=True)
if i == 0:
# Merge all others with oldp
for bl, q in nc[1:]:
if uf[q] not in groups0:
- #print(i, ": Merge", uf[q], "with", oldp, "via", p)
+ # print(i, ": Merge", uf[q], "with", oldp, "via", p)
groups0[uf[q]] = (bl, bl-v, p)
uf.union(oldp, q)