Поиск островов нулей в последовательности

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 нулей и Ones (нули, где абсолютное значение сигнала падает достаточно близко к нулю, те, в другом месте):

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

• Далее найти начальный Indice 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))'; 

Обратите внимание, что вы всегда можете поменять этот последний шаг с решением CUMSUM/FIND по @gnovice из linked question.

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;