在序列中找到零的島嶼

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: vectorized array creation from a list of start/end indices

這是我到目前爲止有：

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和那些（其中零信號的絕對值降到足夠接近零，那些在別處）：

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

• 接下來，找到起始指數之S，使用函數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); 
  

• 最後，使用the method from my answer to the linked question來生成最終的索引集：

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

Answer 2

我認爲最簡單的MATLAB /「矢量化」方法是通過計算信號與濾波器[-1 1]的卷積。你應該看看函數conv的文檔。然後在conv的輸出中使用find來獲得相關索引。

Answer 3

function indice=sigvec(sig,thresh) 
    %extend sig head and tail to avoid 0 head and 0 tail 

    exsig=[1,sig,1]; 
    %convolution sig with extend sig 
    cvexsig=conv(exsig,ones(1,thresh)); 
    tempsig=double(cvexsig==0); 

    indice=find(conv(tempsig,ones(1,thresh)))-thresh; 

Answer 4

就可以解決這個作爲一個字符串搜索任務，通過查找長度thresh的零的字符串（STRFIND功能是非常快的）

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

需要注意的是更長的子字符串將會被標記在多個位置，但最終會加入一次我們添加之間的位置從間隔開始startIndex到結尾start+thresh-1。

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

請注意，您可以隨時更換爲可從linked question通過@gnovice的CUMSUM /找到解決這最後一步。

Answer 5

由於gnovice表明，我們會做一個閾值測試，以使「接近零」真零點：

logcl = abs(sig(:)) >= zero_tolerance; 

然後找出其中的區域中累積不增加：

cs = cumsum(logcl); 
islands = cs(1+thresh:end) == cs(1:end-thresh); 

記住gnovice's great method for filling in ranges of indexes

v = zeros(1,max(endInd)+1); %# An array of zeroes 
v(startInd) = 1;    %# Place 1 at the starts of the intervals 
v(endInd+1) = v(endInd+1)-1; %# Add -1 one index after the ends of the intervals 
indices = find(cumsum(v)); %# Perform a cumulative sum and find the nonzero entries 

我們注意到，我們的islands載體已經在startInd位置的，和我們的目的endInd總是thresh點後（長的滑雪道是那些在islands運行）

endcap = zeros(thresh,1); 
indices = find(cumsum([islands ; endcap] - [endcap ; islands])) 

測試

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]; 
logcl = abs(sig(:)) >= .1; 
cs = cumsum(logcl); 
islands = cs(1+thresh:end) == cs(1:end-thresh); 
endcap = zeros(thresh,1); 
indices = find(cumsum([islands ; endcap] - [endcap ; islands])) 

indices = 

    2 
    3 
    4 
    5 
    13 
    14 
    15 

Answer 6

這在numpy的（還回答here）

def nonzero_intervals(vec): 
    ''' 
    Find islands of non-zeros in the vector vec 
    ''' 
    if len(vec)==0: 
     return [] 
    elif not isinstance(vec, np.ndarray): 
     vec = np.array(vec) 

    edges, = np.nonzero(np.diff((vec==0)*1)) 
    edge_vec = [edges+1] 
    if vec[0] != 0: 
     edge_vec.insert(0, [0]) 
    if vec[-1] != 0: 
     edge_vec.append([len(vec)]) 
    edges = np.concatenate(edge_vec) 
    return zip(edges[::2], edges[1::2]) 

例如：

a=[1, 2, 0, 0, 0, 3, 4, 0] 
intervals = nonzero_intervals(a) 
assert intervals == [(0, 2), (5, 7)] 

Answer 7

通過genovice上面的回答可被修飾以發現的非零元素的索引中的載體爲：

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