Encontrar islas de ceros en una secuencia


Imagina que tienes una secuencia muy larga. ¿Cuál es la forma más eficiente de encontrar los intervalos donde la secuencia es todos los ceros (o más precisamente la secuencia cae a valores cercanos a cero abs(X)<eps):

Para simplificar, supongamos la siguiente secuencia:

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

Estoy tratando de obtener la siguiente información:

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

Luego, usando esta información, encontramos los intervalos con duración >= a algún valor especificado (digamos 3), y devolviendo los índices de los valores en todos estos intervalos combinados:

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

Esa última parte está relacionada con una pregunta anterior:

MATLAB: creación de matrices vectorizadas de una lista de índices de inicio/fin

Esto es lo que tengo hasta ahora:

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

Estoy buscando vectorizar/optimizar el código, pero estoy abierto a otras soluciones. Tengo que enfatizar que las eficiencias de espacio y tiempo son muy importantes, ya que estoy procesando un gran número de bio-señales largas.

Author: Community, 2010-07-18

7 answers

Estos son los pasos que tomaría para resolver su problema de una manera vectorizada, comenzando con un vector dado sig:

  • Primero, umbral del vector para obtener un vector tsig de ceros y unos (ceros donde el valor absoluto de la señal cae lo suficientemente cerca de cero, unos en otros lugares):

    tsig = (abs(sig) >= eps);  %# Using eps as the threshold
    
  • A continuación, encuentre los índices iniciales, los índices finales y la duración de cada cadena de ceros utilizando las funciones DIFF y BUSCAR :

    dsig = diff([1 tsig 1]);
    startIndex = find(dsig < 0);
    endIndex = find(dsig > 0)-1;
    duration = endIndex-startIndex+1;
    
  • Luego, encuentra las cadenas de ceros con una duración mayor o igual a algún valor (como 3, de tu ejemplo):

    stringIndex = (duration >= 3);
    startIndex = startIndex(stringIndex);
    endIndex = endIndex(stringIndex);
    
  • Finalmente, use el método de mi respuesta a la pregunta vinculada para generar su conjunto final de índices:

    indices = zeros(1,max(endIndex)+1);
    indices(startIndex) = 1;
    indices(endIndex+1) = indices(endIndex+1)-1;
    indices = find(cumsum(indices));
    
 33
Author: gnovice,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 10:31:34

Puede resolver esto como una tarea de búsqueda de cadenas, encontrando cadenas de ceros de longitud thresh (la función STRFIND es muy rápida)

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

Tenga en cuenta que las subcadenas más largas se marcarán en múltiples ubicaciones, pero eventualmente se unirán una vez que agreguemos ubicaciones intermedias desde intervalos que comienzan en startIndex para terminar en start+thresh-1.

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

Tenga en cuenta que siempre puede intercambiar este último paso con la solución CUMSUM/FIND de @gnovice desde la pregunta vinculada .

 10
Author: Amro,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 11:47:11
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;
 1
Author: emailhy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-07-18 02:39:15

La respuesta anterior de genovice se puede modificar para encontrar los índices de elementos distintos de cero en un vector como:

    tsig = (abs(sig) >= eps);
    dsig = diff([0 tsig 0]);
    startIndex = find(dsig > 0);
    endIndex = find(dsig < 0)-1;
    duration = endIndex-startIndex+1;
 1
Author: pankaj singh,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-11-28 08:56:39

Como gnovice mostró, vamos a hacer una prueba de umbral para hacer" cerca de cero " realmente cero:

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

Luego encuentra regiones donde la suma acumulada no está aumentando:

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

Recordando el gran método de gnovice para rellenar rangos de índices

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

Observamos que nuestro vector islands ya tiene unos en las ubicaciones startInd, y para nuestros propósitos endInd siempre viene thresh puntos más tarde (las carreras más largas tienen carreras de unos en islands)

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

Prueba

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
 0
Author: Ben Voigt,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 11:47:11

Creo que la forma más"vectorizada" de MATLAB es computando una convolución de su señal con un filtro como [-1 1]. Usted debe mirar la documentación de la función conv. Luego, en la salida de conv use find para obtener los índices relevantes.

 -1
Author: carlosdc,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-07-18 02:13:58

Aquí está en numpy (también respondido aquí)

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

Ej:

a=[1, 2, 0, 0, 0, 3, 4, 0]
intervals = nonzero_intervals(a)
assert intervals == [(0, 2), (5, 7)]
 -1
Author: Peter,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:02:22