按顺序查找零个岛屿

Question

想象一下,你有一个很长的序列.查找序列全为零的间隔的最有效方法是什么(或者更确切地说,序列降至接近零的值abs(X)<eps):

为简单起见,我们假设以下顺序:

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];

我正在尝试获取以下信息:

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

然后使用这些信息,我们找到持续时间> =到某个指定值(例如3)的间隔,并返回所有这些间隔中的值的索引组合:

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

最后一部分与前一个问题有关:

MATLAB:从开始/结束索引列表创建矢量化数组

这是我到目前为止:

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);

我正在寻找矢量化/优化代码,但我对其他解决方案持开放态度.我必须强调空间和时间效率非常重要,因为我正在处理大量长生物信号.

Answer 1

这些是我用矢量化方式解决问题的步骤,从给定的向量开始sig:

• 首先,对向量进行阈值以获得tsig零和1 的向量(零,其中信号的绝对值下降到足够接近零,其他地方为0):

  tsig = (abs(sig) >= eps);  %# Using eps as the threshold
  

• 接下来,使用函数DIFF和FIND查找每个零字符串的起始索引,结束索引和持续时间:

  dsig = diff([1 tsig 1]);
  startIndex = find(dsig < 0);
  endIndex = find(dsig > 0)-1;
  duration = endIndex-startIndex+1;
  

• 然后,找到持续时间大于或等于某个值的零字符串(例如3,来自您的示例):

  stringIndex = (duration >= 3);
  startIndex = startIndex(stringIndex);
  endIndex = endIndex(stringIndex);
  

• 最后,使用我对链接问题的回答中的方法来生成最终的索引集:

  indices = zeros(1,max(endIndex)+1);
  indices(startIndex) = 1;
  indices(endIndex+1) = indices(endIndex+1)-1;
  indices = find(cumsum(indices));
  

Answer 2

您可以通过查找长度为零的字符串thresh(STRFIND函数非常快)来解决此问题作为字符串搜索任务

startIndex = strfind(sig, zeros(1,thresh));

请注意,较长的子字符串将在多个位置进行标记,但是一旦我们添加中间位置,从间隔开始startIndex到结束时最终将连接start+thresh-1.

indices = unique( bsxfun(@plus, startIndex', 0:thresh-1) )';

请注意,您始终可以通过链接问题中的@gnovice将最后一步与CUMSUM/FIND解决方案进行交换.