Skip to content

Instantly share code, notes, and snippets.

@tve
Last active October 23, 2024 18:00
Show Gist options
  • Save tve/f7411b65276e5ce28983cc234bc38cf6 to your computer and use it in GitHub Desktop.
Save tve/f7411b65276e5ce28983cc234bc38cf6 to your computer and use it in GitHub Desktop.
Motus burst-finder for Sensorgnome

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
#! /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)
}
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
tagID tagProjectID mfgID dateBin dtRegistered type codeset manufacturer model lifespan nomFreq offsetFreq period periodSD pulseLen param1 param2 param3 sum 3-2
10695 1 1 2014-3 2014-07-22 12:21:49.103 ID Lotek4 Lotek NTQB-6-2 1391 166.38 0.3505 19.9942 0.001 2.5 21.9375 19.5625 24.4375 65.9375 4.875
10696 1 2 2014-3 2014-07-22 12:21:49.763 ID Lotek4 Lotek NTQB-6-2 1391 166.38 0.3738 19.9945 0.0009 2.5 22 24.5 44 90.5 19.5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment