Finding islands of zeros in a sequence

Question

Imagine you have a very long sequence. What is the most efficient way of finding the intervals where the sequence is all zeros (or more precisely the sequence drops to near-zero values abs(X)):



For simplicity, lets assume the following sequence:

sig = [1 1 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0];


I'm trying to get the following information:

startIndex   EndIndex    Duration
3            6           4
12           12          1
14           16          3
25           26          2
30           30          1


then using this information, we find the intervals with duration >= to some specified value (say 3), and returning the indices of the values in all these intervals combined:

indices = [3 4 5 6 14 15 16];


That last part is related to a previous question:


  MATLAB: vectorized array creation
  from a list of start/end indices


This is what I have so far:

sig = [1 1 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0];
len = length(sig);
thresh = 3;

%# align the signal with itself successively shifted by one
%# v will thus contain 1 in the starting locations of the zero interval
v = true(1,len-thresh+1);
for i=1:thresh
    v = v & ( sig(i:len-thresh+i) == 0 );
end

%# extend the 1's till the end of the intervals
for i=1:thresh-1
    v(find(v)+1) = true;
end

%# get the final indices
v = find(v);


I'm looking to vectorize/optimize the code, but I'm open to other solutions.
I have to stress that space and time efficiencies are very important, since I'm processing a large number of long bio-signals.

Finding islands of zeros in a sequence

6 Answers