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

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

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

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

Answer 3

приведенный выше ответ по genovice можно изменить, чтобы найти индексы ненулевых элементов в векторе как:

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

Answer 4

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 5

Как показал gnovice, мы проведем пороговый тест, чтобы сделать "почти ноль" действительно нулевым:

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

Затем найдите регионы, в которых кумулятивная сумма не увеличивается:

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

Запоминание Отличный метод gnovice для заполнения диапазонов индексов

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 всегда идет * на 1017 * мест позже (более длинные серии имеют пробеги в islands)

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

Test

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

Я думаю, что наиболее MATLAB / «векторизованный» способ сделать это - вычислить свертку вашего сигнала с фильтром, подобным [-1 1]. Вы должны посмотреть на документацию функции conv. Затем на выходе conv используйте find для получения соответствующих индексов.