Diff of /bwlabels.js [000000] .. [b86468]

Switch to side-by-side view

--- a
+++ b/bwlabels.js
@@ -0,0 +1,278 @@
+export class BWLabeler {
+  // port of https://github.com/rordenlab/niimath/blob/master/src/bwlabel.c
+  // return voxel address given row A, column B, and slice C
+  idx(A, B, C, DIM) {
+    return C * DIM[0] * DIM[1] + B * DIM[0] + A
+  } // idx()
+
+  // determine if voxels below candidate voxel have already been assigned a label
+  check_previous_slice(bw, il, r, c, sl, dim, conn, tt, nabo, tn) {
+    let nr_set = 0
+    if (!sl) {
+      return 0
+    }
+    const val = bw[this.idx(r, c, sl, dim)]
+    if (conn >= 6) {
+      const idx = this.idx(r, c, sl - 1, dim)
+      if (val === bw[idx]) {
+        nabo[nr_set++] = il[idx]
+      }
+    }
+    if (conn >= 18) {
+      if (r) {
+        const idx = this.idx(r - 1, c, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+      if (c) {
+        const idx = this.idx(r, c - 1, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+      if (r < dim[0] - 1) {
+        const idx = this.idx(r + 1, c, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+      if (c < dim[1] - 1) {
+        const idx = this.idx(r, c + 1, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+    }
+    if (conn === 26) {
+      if (r && c) {
+        const idx = this.idx(r - 1, c - 1, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+      if (r < dim[0] - 1 && c) {
+        const idx = this.idx(r + 1, c - 1, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+      if (r && c < dim[1] - 1) {
+        const idx = this.idx(r - 1, c + 1, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+      if (r < dim[0] - 1 && c < dim[1] - 1) {
+        const idx = this.idx(r + 1, c + 1, sl - 1, dim)
+        if (val === bw[idx]) {
+          nabo[nr_set++] = il[idx]
+        }
+      }
+    }
+    if (nr_set) {
+      this.fill_tratab(tt, nabo, nr_set, tn)
+      return nabo[0]
+    } else {
+      return 0
+    }
+  } // check_previous_slice()
+
+  // provisionally label all voxels in volume
+  do_initial_labelling(bw, dim, conn) {
+    const naboPS = new Uint32Array(32)
+    const tn = new Uint32Array(32)
+    let label = 1
+    const kGrowArrayBy = 8192
+    let ttn = kGrowArrayBy
+    let tt = new Uint32Array(ttn).fill(0)
+    const il = new Uint32Array(dim[0] * dim[1] * dim[2]).fill(0)
+    const nabo = new Uint32Array(27)
+    for (let sl = 0; sl < dim[2]; sl++) {
+      for (let c = 0; c < dim[1]; c++) {
+        for (let r = 0; r < dim[0]; r++) {
+          let nr_set = 0
+          const val = bw[this.idx(r, c, sl, dim)]
+          if (val === 0) {
+            continue
+          }
+          nabo[0] = this.check_previous_slice(bw, il, r, c, sl, dim, conn, tt, naboPS, tn)
+          if (nabo[0]) {
+            nr_set += 1
+          }
+          if (conn >= 6) {
+            if (r) {
+              const idx = this.idx(r - 1, c, sl, dim)
+              if (val === bw[idx]) {
+                nabo[nr_set++] = il[idx]
+              }
+            }
+            if (c) {
+              const idx = this.idx(r, c - 1, sl, dim)
+              if (val === bw[idx]) {
+                nabo[nr_set++] = il[idx]
+              }
+            }
+          }
+          if (conn >= 18) {
+            if (c && r) {
+              const idx = this.idx(r - 1, c - 1, sl, dim)
+              if (val === bw[idx]) {
+                nabo[nr_set++] = il[idx]
+              }
+            }
+            if (c && r < dim[0] - 1) {
+              const idx = this.idx(r + 1, c - 1, sl, dim)
+              if (val === bw[idx]) {
+                nabo[nr_set++] = il[idx]
+              }
+            }
+          }
+          if (nr_set) {
+            il[this.idx(r, c, sl, dim)] = nabo[0]
+            this.fill_tratab(tt, nabo, nr_set, tn)
+          } else {
+            il[this.idx(r, c, sl, dim)] = label
+            if (label >= ttn) {
+              ttn += kGrowArrayBy
+              const ext = new Uint32Array(ttn)
+              ext.set(tt)
+              tt = ext
+            }
+            tt[label - 1] = label
+            label++
+          }
+        }
+      }
+    }
+    for (let i = 0; i < label - 1; i++) {
+      let j = i
+      while (tt[j] !== j + 1) {
+        j = tt[j] - 1
+      }
+      tt[i] = j + 1
+    }
+    return [label - 1, tt, il]
+  } // do_initial_labelling()
+
+  // translation table unifies a region that has been assigned multiple classes
+  fill_tratab(tt, nabo, nr_set, tn) {
+    // let cntr = 0
+    //tn.fill(0)
+    const INT_MAX = 2147483647
+    let ltn = INT_MAX
+    for (let i = 0; i < nr_set; i++) {
+      let j = nabo[i]
+      // cntr = 0
+      while (tt[j - 1] !== j) {
+        j = tt[j - 1]
+        /* cntr++
+        if (cntr > 100) {
+          console.log('\nOoh no!!')
+          break
+        } */
+      }
+      tn[i] = j
+      ltn = Math.min(ltn, j)
+    }
+    for (let i = 0; i < nr_set; i++) {
+      tt[tn[i] - 1] = ltn
+    }
+  } // fill_tratab()
+
+  // remove any residual gaps so label numbers are dense rather than sparse
+  translate_labels(il, dim, tt, ttn) {
+    const nvox = dim[0] * dim[1] * dim[2]
+    let ml = 0
+    const l = new Uint32Array(nvox).fill(0)
+    for (let i = 0; i < ttn; i++) {
+      ml = Math.max(ml, tt[i])
+    }
+    const fl = new Uint32Array(ml).fill(0)
+    let cl = 0
+    for (let i = 0; i < nvox; i++) {
+      if (il[i]) {
+        if (!fl[tt[il[i] - 1] - 1]) {
+          cl += 1
+          fl[tt[il[i] - 1] - 1] = cl
+        }
+        l[i] = fl[tt[il[i] - 1] - 1]
+      }
+    }
+    return [cl, l]
+  } // translate_labels()
+
+  // retain only the largest cluster for each region
+  largest_original_cluster_labels(bw, cl, ls) {
+    const nvox = bw.length
+    const ls2bw = new Uint32Array(cl + 1).fill(0)
+    const sumls = new Uint32Array(cl + 1).fill(0)
+    for (let i = 0; i < nvox; i++) {
+      const bwVal = bw[i]
+      const lsVal = ls[i]
+      ls2bw[lsVal] = bwVal
+      sumls[lsVal]++
+    }
+    let mxbw = 0
+    for (let i = 0; i < cl + 1; i++) {
+      const bwVal = ls2bw[i]
+      mxbw = Math.max(mxbw, bwVal)
+      // see if this is largest cluster of this bw-value
+      for (let j = 0; j < cl + 1; j++) {
+        if (j === i) {
+          continue
+        }
+        if (bwVal !== ls2bw[j]) {
+          continue
+        }
+        if (sumls[i] < sumls[j]) {
+          ls2bw[i] = 0
+        } else if (sumls[i] === sumls[j] && i < j) {
+          ls2bw[i] = 0
+        } // ties: arbitrary winner
+      }
+    }
+    const vxs = new Uint32Array(nvox).fill(0)
+    for (let i = 0; i < nvox; i++) {
+      vxs[i] = ls2bw[ls[i]]
+    }
+    return [mxbw, vxs]
+  }
+
+  // given a 3D image, return a clustered label map
+  // for an explanation and optimized C code see
+  // https://github.com/seung-lab/connected-components-3d
+  bwlabel(img, dim, conn = 26, binarize = false, onlyLargestClusterPerClass = false) {
+    const start = Date.now()
+    const nvox = dim[0] * dim[1] * dim[2]
+    const bw = new Uint32Array(nvox).fill(0)
+    if (![6, 18, 26].includes(conn)) {
+      console.log('bwlabel: conn must be 6, 18 or 26.')
+      return [0, bw]
+    }
+    if (dim[0] < 2 || dim[1] < 2 || dim[2] < 1) {
+      console.log('bwlabel: img must be 2 or 3-dimensional')
+      return [0, bw]
+    }
+    if (binarize) {
+      for (let i = 0; i < nvox; i++) {
+        if (img[i] !== 0.0) {
+          bw[i] = 1
+        }
+      }
+    } else {
+      bw.set(img)
+    }
+    let [ttn, tt, il] = this.do_initial_labelling(bw, dim, conn)
+    if (tt === undefined) {
+      tt = new Uint32Array(0)
+    }
+    const [cl, ls] = this.translate_labels(il, dim, tt, ttn)
+    console.log(conn + ' neighbor clustering into ' + cl + ' regions in ' + (Date.now() - start) + 'ms')
+    if (onlyLargestClusterPerClass) {
+      const [nbw, bwMx] = this.largest_original_cluster_labels(bw, cl, ls)
+      return [nbw, bwMx]
+    }
+    return [cl, ls]
+  } // bwlabel()
+}