changeset 0:1df4a6fb0d22

added flst files moved over from "smoothie"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matlab/flstDecode.m	Fri Oct 31 10:52:27 2014 +0800
@@ -0,0 +1,13 @@
+function vpath = flstDecode(d)
+
+nFrame = min([d.memory, d.updateCount]);
+psi = d.psi(:,(d.memory-nFrame+1):d.memory);
+vpath = zeros(1, nFrame);
+
+% initialise backward step
+[~, vpath(end)] = max(d.oldDelta);
+
+% rest of backward step
+for iFrame = (nFrame-1):-1:1
+    vpath(iFrame) = psi(vpath(iFrame+1), iFrame+1);
+end
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matlab/flstMakeData.m	Fri Oct 31 10:52:27 2014 +0800
@@ -0,0 +1,24 @@
+function d = flstMakeData(mdl, memory)
+
+% makeFLSTData just returns a struct that contains all the necessary data 
+% for a Fixed Lag Sparse Transition Viterbi decoder.
+
+init = mdl.init;
+transFrom = mdl.transFrom;
+transTo = mdl.transTo;
+transProb = mdl.transProb;
+
+d = struct();
+d.init = init(:);
+d.from = transFrom;
+d.to = transTo;
+d.prob = transProb;
+d.memory = memory;
+d.nState = length(init);
+d.nTrans = length(transFrom);
+d.delta = ones(d.nState, 1) / d.nState;
+d.oldDelta = ones(d.nState, 1) / d.nState;
+d.psi = zeros(d.nState, memory);
+d.scale = ones(1, memory);
+d.updateCount = 0;
+d.path = [];

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matlab/flstUpdateModel.m	Fri Oct 31 10:52:27 2014 +0800
@@ -0,0 +1,7 @@
+function d = flstUpdateModel(d, mdl)
+
+d.from = mdl.transFrom;
+d.to   = mdl.transTo;
+d.prob = mdl.transProb;
+d.init = mdl.init;
+d.nTrans = length(mdl.transFrom);
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matlab/flstUpdateTransition.m	Fri Oct 31 10:52:27 2014 +0800
@@ -0,0 +1,10 @@
+function d = flstUpdateTransition(d, transMat, thresh)
+
+if nargin < 3
+    thresh = eps;
+end
+
+[d.from, d.to] = find(transMat > thresh);
+temp = find(transMat(:) > thresh);
+d.prob = transMat(temp);
+d.nTrans = length(d.prob);
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matlab/flstViterbiUpdate.m	Fri Oct 31 10:52:27 2014 +0800
@@ -0,0 +1,62 @@
+function d = flstViterbiUpdate(obsLik, d, isFinal)
+
+if nargin < 3
+    isFinal = 0;
+end
+
+% d.psi(:,1:(d.memory-1)) = d.psi(:,2:d.memory);
+d.psi = circshift(d.psi, -1, 2);
+% d.scale(1:(d.memory-1)) = d.scale(2:d.memory);
+d.scale = circshift(d.scale, -1, 2);
+
+if d.updateCount == 0
+     % initialise first frame
+    d.oldDelta = d.init .* obsLik;
+    deltaSum = sum(d.oldDelta);
+    d.oldDelta = d.oldDelta / deltaSum;
+    d.scale(d.memory) = 1.0/deltaSum;
+else
+    tempPsi = ones(d.nState, 1);
+
+    % calculate best previous state for every current state
+    % this would be the "sparse" loop in C++
+
+%     for jState = 1:d.nState
+%         temp = d.oldDelta(d.from) .* d.prob';
+%         [d.delta(jState), tempPsi(jState)] = max(temp(d.to==jState));
+%     end
+
+    for iTrans = 1:d.nTrans
+        transProb = d.prob(iTrans);
+        fromState = d.from(iTrans);
+        toState = d.to(iTrans);
+        currentValue = d.oldDelta(fromState) * transProb;
+        if (currentValue > d.delta(toState))
+            d.delta(toState) = currentValue; % will be multiplied by the right obs later!
+            tempPsi(toState) = fromState;
+        end
+    end
+    d.delta = d.delta .* obsLik;
+    deltaSum = sum(d.delta);
+
+    if deltaSum > 0
+        d.oldDelta = d.delta / deltaSum; % normalise (scale)
+        d.scale(d.memory) = 1.0/deltaSum;
+        d.delta = zeros(size(d.delta));
+    else
+        warning('Viterbi has been fed some zero probabilities (update %d),\nat least they become zero in combination with the model.', d.updateCount);
+        d.oldDelta = ones(d.nState,1)/d.nState;
+        d.scale(d.memory) = 1.0;
+        d.delta = zeros(size(d.delta));
+    end
+    d.psi(:,d.memory) = tempPsi;
+end
+d.updateCount = d.updateCount + 1;
+
+if isFinal
+    temp = flstDecode(d);
+    d.path = [d.path, temp];
+elseif d.updateCount > (d.memory-1)
+    temp = flstDecode(d);
+    d.path = [d.path, temp(1)];
+end

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matlab/hmm_dummy.m	Fri Oct 31 10:52:27 2014 +0800
@@ -0,0 +1,8 @@
+function mdl = hmm_dummy()
+
+% hmm_dummy returns a hidden Markov model for use in test_flst.m
+
+mdl.transFrom = [1,1,2];
+mdl.transTo   = [1,2,2];
+mdl.transProb = [0.6, 0.4, 1];
+mdl.init = [1,0];
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/matlab/test_flst.m	Fri Oct 31 10:52:27 2014 +0800
@@ -0,0 +1,42 @@
+% TEST_FLST tests the fixed lag sparse transition Viterbi implementation
+
+addpath('misc')
+addpath('smoothiecore')
+addpath('flst')
+
+%% setup model
+
+mdl = hmm_dummy();
+memory = 3;
+d = flstMakeData(mdl, memory);
+
+%% now make up some probabilites
+
+obsLik = [...
+    [0.5, 0.5];
+    [0.8, 0.2];
+    [0.4, 0.6];
+    [0.8, 0.2];
+    [0.8, 0.2];
+    [0.2, 0.8];
+    [0.3, 0.7];
+    [0.9, 0.1]]';
+
+nFrame = size(obsLik,2);
+
+
+for iFrame = 1:nFrame-1
+    d = flstViterbiUpdate(obsLik(:,iFrame), d);
+end
+d = flstViterbiUpdate(obsLik(:,iFrame), d, 1);
+e = d;
+d = flstMakeData(mdl, memory);
+disp(e)
+
+%% test
+
+if all((e.path-[1 1 1 1 1 2 2 2])==0)
+    fprintf(1, 'Test ok.\n');
+else
+    warning('Test has detected an error.')
+end
\ No newline at end of file