Motus burst-finder for Sensorgnome

README.md

Find-bursts stand-alone test program

The purpose of this burst finder is to parse Lotek tag pulses emitted by the pulse finder plugin to VAMP and output detected bursts. The bursts are detected by matching against a tag database provided in CSV format and applying default frequency, signal strength and timing slop.

While this test program outputs bursts the actual intended function is to filter pulses, i.e. to remove all pulses that do not correspond to a burst. Filtering pulses instead of outputting bursts is expected to reduce the output volume when there is aliasing and, more importantly, allows subsequent server-side processing to apply different burst detection criteria. For the latter reason it is most likely desirable to set the slop values somewhat larger to provide more leeway in tuning the burst & tag finder settings server-side.

Operation

This test program includes the actual burst finder classes and a main application all in one file. It is written in Javascript and can be run using node.js. The example here are for Linux and expect to find node at /usr/local/bin/node so the command line will need tweaking on other OSes. To run the program specify the tag definition file as argument and pipe the pulses in via stdin:

> ./find-bursts.mjs two-tags.csv <sgv2-1BA7RPI47F3A-046-2024-06-
30T17-04-53.703Z-all.txt                                                                  
Tag count: 2                                                                              
B1,1719767212.837,2,22.0,24.4,43.9,22,25,44                                               
P1,1719767212.837,4.2,-47                                                                 
P1,1719767212.859,4.2,-45                                                                 
P1,1719767212.883,4.3,-47                                                                 
P1,1719767212.927,4.2,-47                                                                 
B1,1719767238.535,2,22.0,24.4,43.9,22,25,44                                               
P1,1719767238.535,4.2,-45                                                                 
P1,1719767238.557,4.2,-47                                                                 
P1,1719767238.582,4.3,-48                                                                 
P1,1719767238.625,4.3,-48                                                                 
B1,1719767570.239,2,22.0,24.4,43.9,22,25,44                                               
P1,1719767570.239,4.2,-46                                                                 
P1,1719767570.261,4.2,-46                                                                 
P1,1719767570.285,4.3,-48                                                                 
P1,1719767570.329,4.2,-45                                                                 
B1,1719767595.937,2,22.0,24.4,43.9,22,25,44                                               
P1,1719767595.937,4.2,-45                                                                 
P1,1719767595.959,4.2,-47                                                                 
P1,1719767595.984,4.3,-45                                                                 
P1,1719767596.027,4.3,-47

Each line starting with B denotes a burst with the port number, the timestamp of the first pulse, the tag ID, the three intervals measured between the pulses. and the three intervals specified for the tag ID in the tag definition. The B line is followed by a printout of the actual pulses.

The test program also included some simple test cases to (partially) verify correctness, these can be run by providing two arguments (the value of the second doesn't matter). Sample run:

> ./find-bursts.mjs two-tags.csv test
Tag count: 2
Test one burst
PASS
Test two overlapping bursts
PASS
Test overlapping burst with wrong freq
PASS
Test overlapping burst with wrong signal
PASS
Test overlapping burst with wrong port
PASS
Test overlap thanks to to time slop
PASS
Test overlap with too much time slop
PASS

find-bursts.mjs

#! /usr/local/bin/node
// code to find pulse bursts
import * as fs from 'node:fs'
import * as process from 'node:process'

// parameters to match pulses, taken from the way tag-finder is run on Sensorgnomes
const FREQ_SLOP = 2  // freq range (kHz) for a burst
const SIGNAL_SLOP = 10 // signal range (dB) for a burst
const TIME_SLOP = 1.5 // max time diff from measured interval in ms

// max total time a burst can take, used to discard older pulses
const MAX_BURST_TIME = 134+156+156+3*TIME_SLOP + 10

let history = [] // array of ports, each element being an array of pulses, most recent first
let tagCount = 0
let burstCount = 0

// Each tag definition (3 intervals) is turned into a search tree with a TreeNode for each level
// The root node holds children for each possible last interval (last because the search is done
// backwards when the last pulse is received).
// Each of those child nodes holds further nodes for the middle interval.
// The third level holds TagNodes that represent decoded tags.
class TreeNode {
  constructor() { this.children = {}; this.max_iv = 0; }

  // add a tag with the specified intervals left and the tag id
  // the intervals are specified "forwards" in time order, and add() pops off the last one
  add(intervals, tagid) {
    const iv = intervals.pop()
    if (iv > this.max_iv) this.max_iv = iv
    if (intervals.length == 0) {
      // no more intervals past this, so child needs to be a TagNode
      if (iv in this.children) {
        if (this.children[iv].tagid != tagid) console.log("Oops, duplicate!", tagid)
      } else {
        this.children[iv] = new TagNode(tagid)
      }
    } else {
      if (!(iv in this.children)) this.children[iv] = new TreeNode()
      this.children[iv].add(intervals, tagid)
    }
  }

  // try to match all history pulses against the intervals we have tags for
  // ix is the index into the history where to start searching
  match(ix, suffix) {
    const s0 = suffix[0] // oldest pulse so far
    const hist = history[s0.port]
    for (; ix<hist.length; ix++) {
      const p = hist[ix]
      const dt = s0.ts - p.ts
      if (dt - TIME_SLOP > this.max_iv+1) return // nothing past this can match anymore
      if (!compatible(p, suffix)) continue
      for (let iv = Math.ceil(dt-TIME_SLOP); iv <= Math.floor(dt+TIME_SLOP); iv += 1) {
        if (iv in this.children) {
          const s = ([p]).concat(suffix)
          this.children[iv].match(ix+1, s)
        }
      }  
    }
  }
}

// A TagNode represents the endpoint of a match and corresponds to a unique tag
class TagNode {
  static cb = undefined // callback when burst found

  constructor(tagid) { this.tagid = tagid; tagCount++ }

  match(ix, suffix) {
    if (suffix.length != 4) {
      console.log("Oops, burstlen != 4", suffix.length, suffix, this.tagid)
    } else {
      const s0 = suffix[0]
      const s1 = suffix[1]
      const s2 = suffix[2]
      const s3 = suffix[3]
      const intv = ([ s1.ts-s0.ts, s2.ts-s1.ts, s3.ts-s2.ts ]).map(v=>v.toFixed(1))
      const info = [ s0.port, (s0.ts/1000).toFixed(3), this.tagid, ...intv, ...tags[this.tagid] ]
      for (const s of suffix) s.keep = true
      if (TagNode.cb) {
        TagNode.cb(info, suffix)
        burstCount++
      } else {
        console.log("B" + info.join(','))
        // console.log("Burst:", suffix)
        // if (++burstCount == 10) process.exit(0)
      }
    }
  }
}

// compatible returns true if the new pulse is compatible with the pulses so far in terms of
// frequency and signal strength
function compatible(p, suffix) {
  for (const p2 of suffix) {
    if (Math.abs(p2.freq - p.freq) > FREQ_SLOP) return false
    if (Math.abs(p2.sig - p.sig) > SIGNAL_SLOP) return false
  }
  return true
}

// prune the history of pulses for a port, eliminating those that are too old to fit into any burst
// note that history is ordered most recent first
function pruneHistory(port, ts) {
  let hist = history[port]
  let deadline = ts - MAX_BURST_TIME
  let ix = hist.findIndex(e => e.ts < deadline)
  if (ix >= 0) {
    for (let i=hist.length-1; i>=ix; i--) {
      const pls = hist[i]
      if (pls.keep) {
        console.log(`P${port},${(pls.ts/1000).toFixed(3)},${pls.freq.toFixed(1)},${pls.sig.toFixed(0)}`)
      }
    }
    hist.splice(ix) // delete starting at ix
  }
}

// parse a pulse line
function parsePulse(line) {
  const ll = line.split(',')
  if (ll.length < 5) console.log("Ooops, bad line", line)
  return {port:ll[0].slice(1), ts:parseFloat(ll[1])*1000, freq:parseFloat(ll[2]), sig:parseFloat(ll[3]), keep:false}
}

// ===== main "runner"

const tree = new TreeNode()
const tags = {}

if (process.argv.length < 3) {
  console.error("usage:", process.argv0, "<tag-database.csv>")
  console.error("oops")
  process.exit(1)
}

// read tag database from CSV
(()=>{
  const csv = fs.readFileSync(process.argv[2], {encoding: 'utf8'}).split('\n')
  let param1 = 15 // field number in csv
  let mfgID = 2 // field number
  for (const t of csv) {
    const fields = t.split(',')
    if (fields.length < param1+3) continue
    if (parseInt(fields[0]) > 0) {
      // parse data line
      const intervals = fields.slice(param1, param1+3).map(i => Math.round(i))
      // console.log("tag", fields[mfgID], intervals)
      if (!(fields[mfgID] in tags)) {
        tree.add(intervals.concat(), fields[mfgID])
        tags[fields[mfgID]] = intervals
      }
    } else {
      // parse header line
      const p1 = fields.indexOf("param1")
      if (p1 >= 0) param1 = p1
      const mi = fields.indexOf("mfgID")
      if (mi >= 0) mfgID = mi
    }
  }
  console.log("Tag count:", tagCount)
})();

// process a line from vah pulse-finder
function processLine (line) {
  if (! line.startsWith('p')) return
  const pulse = parsePulse(line) // {port, ts, freq, sig}
  if (pulse.port in history) {
    pruneHistory(pulse.port, pulse.ts)
    // console.log(line)
    tree.match(0, [pulse])
  } else {
    history[pulse.port] = []
  }
  history[pulse.port].unshift(pulse)
}

let buffer = ""
function bufferLine(data) {
  buffer += data
  const lines = buffer.split(/\r?\n/)
  buffer = lines.pop()
  for (const l of lines) processLine(l)
  // warning: expects last line of input to be properly terminated
}

if (process.argv.length == 3) {
  // process pulse-finder lines from stdin
  process.stdin.on('data', bufferLine)
  process.stdin.on('end', ()=>{
    for (const p of Object.keys(history)) pruneHistory(p, Number.POSITIVE_INFINITY)
  })
} else {
  // run test suite ===== everything after this is test cases

  // record detected bursts
  let bursts = []
  TagNode.cb = (info, pulses) => bursts.push({port: info[0], ts: info[1], tag: info[2], pulses})

  // add pulse to the matcher
  function addPulse(pulse) {
    if (pulse.port in history) {
      pruneHistory(pulse.port, pulse.ts)
      tree.match(0, [pulse])
    } else {
      history[pulse.port] = []
    }
    history[pulse.port].unshift(pulse)
  }

  // compare matched bursts with expectations
  function expect(exp) {
    function dump() {
      console.log(`Expected ${exp.length} bursts`)
      for (const b of exp) console.log("  " + JSON.stringify(b))
      console.log(`Got ${bursts.length} bursts`)
      for (const b of bursts) {
        const pp = b.pulses
        console.log("  " + JSON.stringify({...b, pulses:undefined}))
        let t = b.pulses[0].ts
        for (const p of pp) {
          console.log(`    ${JSON.stringify(p)} dt=${p.ts-t}`)
          t = p.ts
        }
      }
    }
    if (exp.length != bursts.length) { dump(); return false }
    for (let i=0; i<exp.length; i++) {
      const e = exp[i], b = bursts[i]
      if (e.port != b.port || e.ts != b.ts || e.freq != b.freq || e.sig != b.sig) {
        dump()
        return false
      }
    }
    console.log("PASS")
    return true
  }

  // generate one burst
  let now = 1719360000000 // 2024-06-26 (UTC)
  const tag1 = tags[1], tag2 = tags[2]

  console.log("Test one burst")
  let base = {port:0, freq:0, sig:-55}
  let exp = [ {port:0, ts:now/1000, tag:1} ]
  addPulse({...base, ts:now}); now += tag1[0]
  addPulse({...base, ts:now}); now += tag1[1]
  addPulse({...base, ts:now}); now += tag1[2]
  addPulse({...base, ts:now})
  expect(exp)

  console.log("Test two overlapping bursts")
  exp.push({port:0, ts:now/1000, tag:2})
  let n2 = now
  /* share last pulse of first burst */ now += tag2[0]
  addPulse({...base, ts:now}); now += tag2[1]
  addPulse({...base, ts:now}); now += tag2[2]
  addPulse({...base, ts:now})
  expect(exp)

  console.log("Test overlapping burst with wrong freq")
  /* share last pulse of prev burst */ now += tag1[0]
  base.freq += FREQ_SLOP*2
  addPulse({...base, ts:now}); now += tag1[1]
  addPulse({...base, ts:now}); now += tag1[2]
  addPulse({...base, ts:now})
  expect(exp)

  console.log("Test overlapping burst with wrong signal")
  /* share last pulse of prev burst */ now += tag1[0]
  base.sig -= 2*SIGNAL_SLOP
  addPulse({...base, ts:now}); now += tag1[1]
  addPulse({...base, ts:now}); now += tag1[2]
  addPulse({...base, ts:now})
  expect(exp)

  console.log("Test overlapping burst with wrong port")
  /* share last pulse of prev burst */ now += tag1[0]
  base.port = 1
  addPulse({...base, ts:now}); now += tag1[1]
  addPulse({...base, ts:now}); now += tag1[2]
  addPulse({...base, ts:now})
  expect(exp)

  bursts = []; exp = []; now += 2000

  console.log("Test overlap thanks to to time slop")
  base = {port:0, freq:0, sig:-55}
  exp = [ {port:0, ts:now/1000, tag:1}, {port:0, ts:now/1000, tag:1} ]
  addPulse({...base, ts:now}); now += tag1[0]
  addPulse({...base, ts:now}); now += tag1[1]
  addPulse({...base, ts:now}); now += tag1[2]
  addPulse({...base, ts:now})
  addPulse({...base, ts:now+TIME_SLOP/2})
  expect(exp)

  console.log("Test overlap with too much time slop")
  addPulse({...base, ts:now+1.1*TIME_SLOP})
  expect(exp)



}

sgv2-1BA7RPI47F3A-046-2024-06-30T17-04-53.703Z-all.txt

C,1719767093703,3,0
# 21 21.97 117.19 131.84 8.09930038452148
p1,1719767093.7030,0.080,-46.6,-57.1
p1,1719767093.7250,0.055,-46.8,-56.5
p1,1719767093.8422,0.098,-46.3,-57.4
p1,1719767093.9740,0.094,-45.8,-56.2
p1,1719767101.8023,0.038,-45.5,-57.8
p1,1719767101.8243,0.023,-47.8,-57.7
p1,1719767101.9415,0.094,-45.1,-55.8
p1,1719767102.0733,0.027,-46.0,-56.9
# 8 21.97 53.71 29.3 8.09980010986328
p1,1719767153.2700,2.156,-46.1,-56.2
p1,1719767153.2920,2.183,-47.8,-55.6
p1,1719767153.3457,2.103,-45.4,-56.1
p1,1719767153.3750,2.177,-46.9,-56.2
p1,1719767161.3698,2.140,-47.6,-57.3
p1,1719767161.3918,2.149,-47.5,-55.6
p1,1719767161.4455,2.175,-45.2,-55.2
p1,1719767161.4748,2.200,-46.4,-57.6
# 2.2 21.973 24.414 43.945 25.6982002258301
p1,1719767212.8370,4.208,-47.3,-55.7
p1,1719767212.8590,4.208,-45.1,-55.4
p1,1719767212.8834,4.266,-47.3,-58.0
p1,1719767212.9273,4.230,-46.8,-57.5
p1,1719767238.5352,4.202,-45.2,-55.6
p1,1719767238.5572,4.221,-46.6,-57.5
p1,1719767238.5816,4.253,-47.8,-56.3
p1,1719767238.6255,4.255,-47.5,-56.4
# 14 21.97 83.01 63.48 8.0999002456665
p1,1719767272.4040,0.010,-47.2,-57.9
p1,1719767272.4260,0.023,-47.4,-57.9
p1,1719767272.5090,0.019,-47.9,-55.1
p1,1719767272.5725,0.094,-46.9,-57.5
p1,1719767280.5039,0.093,-46.1,-56.6
p1,1719767280.5259,0.091,-47.1,-56.1
p1,1719767280.6089,0.073,-47.0,-56.5
p1,1719767280.6724,0.037,-47.5,-57.1
# 4.1 21.973 34.18 73.242 25.0972995758057
p1,1719767331.9710,2.198,-46.3,-55.0
p1,1719767331.9930,2.190,-46.6,-56.3
p1,1719767332.0272,2.102,-47.3,-56.3
p1,1719767332.1004,2.114,-45.4,-55.4
p1,1719767357.0683,2.150,-47.4,-57.1
p1,1719767357.0903,2.106,-45.9,-56.0
p1,1719767357.1245,2.121,-46.8,-57.4
p1,1719767357.1977,2.118,-47.1,-57.9
# 3 21.973 29.297 58.594 24.0969009399414
p1,1719767391.5380,4.251,-47.2,-56.4
p1,1719767391.5600,4.218,-45.7,-57.7
p1,1719767391.5893,4.252,-46.1,-56.9
p1,1719767391.6479,4.289,-45.1,-57.6
p1,1719767415.6349,4.224,-47.1,-56.3
p1,1719767415.6569,4.200,-45.3,-57.0
p1,1719767415.6862,4.201,-45.2,-55.9
p1,1719767415.7448,4.214,-45.8,-56.6
# 23 26.86 19.53 68.36 8.0999002456665
p1,1719767451.1050,0.035,-47.3,-55.8
p1,1719767451.1319,0.088,-46.2,-56.6
p1,1719767451.1514,0.063,-47.6,-57.8
p1,1719767451.2198,0.096,-45.6,-56.1
p1,1719767459.2049,0.006,-45.6,-57.7
p1,1719767459.2318,0.062,-45.4,-55.8
p1,1719767459.2513,0.007,-46.3,-56.1
p1,1719767459.3197,0.019,-47.9,-56.7
# 4 21.97 34.18 73.24 5.29979991912842
p1,1719767510.6720,2.103,-47.0,-55.4
p1,1719767510.6940,2.134,-47.9,-57.9
p1,1719767510.7281,2.127,-45.0,-57.3
p1,1719767510.8014,2.109,-46.8,-56.5
p1,1719767515.9718,2.114,-46.9,-55.8
p1,1719767515.9938,2.164,-47.6,-57.9
p1,1719767516.0279,2.164,-46.3,-55.9
p1,1719767516.1012,2.134,-45.6,-57.7
# 2.2 21.973 24.414 43.945 25.6982002258301
p1,1719767570.2390,4.215,-46.1,-57.9
p1,1719767570.2610,4.247,-45.8,-56.0
p1,1719767570.2854,4.252,-47.5,-56.2
p1,1719767570.3293,4.208,-45.1,-57.8
p1,1719767595.9372,4.212,-45.1,-55.3
p1,1719767595.9592,4.245,-47.2,-57.4
p1,1719767595.9836,4.275,-45.1,-55.2
p1,1719767596.0275,4.296,-47.1,-56.5
# 24 26.86 24.41 83.01 8.09980010986328
p1,1719767629.8060,0.048,-45.9,-56.5
p1,1719767629.8329,0.047,-46.2,-56.0
p1,1719767629.8573,0.031,-47.5,-57.5
p1,1719767629.9403,0.025,-46.7,-55.3
p1,1719767637.9058,0.046,-46.8,-56.7
p1,1719767637.9327,0.082,-46.6,-55.1
p1,1719767637.9571,0.038,-46.4,-55.2
p1,1719767638.0401,0.032,-46.5,-57.8

two-tags.csv