From: Stefan Huber <shuber@sthu.org>
Date: Wed, 17 Apr 2024 14:27:09 +0000 (+0200)
Subject: Fix big for peaks of equal height
X-Git-Url: https://git.sthu.org/?p=persistence.git;a=commitdiff_plain;h=26d1810af5cd5f75048645a89145e736faf534a9

Fix big for peaks of equal height

The order of pixels on the pixel value was ambiguous and possibly
inconsistent with the order of neighborhood pixels. Make it a
unambiguous total order.
---

diff --git a/imagepers.py b/imagepers.py
index 3d03475..a4cf21e 100644
--- a/imagepers.py
+++ b/imagepers.py
@@ -33,9 +33,13 @@ def iter_neighbors(p, w, h):
 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()
@@ -49,6 +53,9 @@ def persistence(im):
     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:
@@ -63,7 +70,7 @@ def persistence(im):
             # 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)