3 """A simple implementation of persistent homology on 2D images."""
5 __author__
= "Stefan Huber <shuber@sthu.org>"
15 def iter_neighbors(p
, w
, h
):
19 neigh
= [(y
+j
, x
+i
) for i
in [-1, 0, 1] for j
in [-1, 0, 1]]
21 # neigh = [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]
36 # Get indices orderd by value from high to low
37 indices
= [(i
, j
) for i
in range(h
) for j
in range(w
)]
38 indices
.sort(key
=lambda p
: get(im
, p
), reverse
=True)
40 # Maintains the growing sets
41 uf
= union_find
.UnionFind()
45 def get_comp_birth(p
):
48 # Process pixels from high to low
49 for i
, p
in enumerate(indices
):
51 ni
= [uf
[q
] for q
in iter_neighbors(p
, w
, h
) if q
in uf
]
52 nc
= sorted([(get_comp_birth(q
), q
) for q
in set(ni
)], reverse
=True)
55 groups0
[p
] = (v
, v
, None)
63 # Merge all others with oldp
65 if uf
[q
] not in groups0
:
66 #print(i, ": Merge", uf[q], "with", oldp, "via", p)
67 groups0
[uf
[q
]] = (bl
, bl
-v
, p
)
70 groups0
= [(k
, groups0
[k
][0], groups0
[k
][1], groups0
[k
][2]) for k
in groups0
]
71 groups0
.sort(key
=lambda g
: g
[2], reverse
=True)