Tìm các đảo số 0 theo thứ tự

Question

Hãy tưởng tượng bạn có một chuỗi rất dài. cách hiệu quả nhất của việc tìm kiếm các khoảng là gì nơi dãy là tất cả các số không (hay chính xác hơn chuỗi giảm xuống giá trị gần như zero abs(X)<eps):

Để đơn giản, cho phép giả định trình tự sau đây:

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

tôi đang cố gắng để có được các thông tin sau:

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

sau đó sử dụng thông tin này, chúng tôi tìm thấy những khoảng thời gian với thời gian> = một số giá trị nào đó (chẳng hạn 3), và trả lại chỉ số của các giá trị trong tất cả những khoảng thời gian kết hợp:

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

Đó phần cuối cùng liên quan đến một câu hỏi trước:

MATLAB: vectorized array creation from a list of start/end indices

Đây là những gì tôi có cho đến nay:

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

Tôi đang tìm cách để vector hóa/tối ưu hóa mã, nhưng tôi đang mở để soluti khác . Tôi phải nhấn mạnh rằng không gian và thời gian hiệu quả là rất quan trọng, vì tôi đang xử lý một số lượng lớn các tín hiệu sinh học dài.

Answer 1

Đây là những bước tôi sẽ làm để giải quyết vấn đề của bạn một cách vectorized, bắt đầu với một vector cho sig:

• Thứ nhất, ngưỡng vector để có được một vector tsig các zeros và những người (zero trong đó giá trị tuyệt đối của tín hiệu giảm đủ gần bằng không, những người ở nơi khác):

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

• Tiếp theo, tìm ra indice bắt đầu s, kết thúc chỉ số, và thời gian của mỗi chuỗi zero sử dụng các chức năng DIFF và FIND:

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

• Sau đó, tìm chuỗi zero với một khoảng thời gian lớn hơn hoặc tương đương với một số giá trị (ví dụ như 3, từ Ví dụ của bạn):

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

• cuối cùng, sử dụng the method from my answer to the linked question để tạo ra tập cuối cùng lại chỉ số:

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

Answer 2

Tôi nghĩ rằng hầu hết MATLAB/"vectorized" cách làm điều đó là bằng cách tính toán một sự biến đổi tín hiệu của bạn với một bộ lọc như [-1 1]. Bạn nên xem tài liệu của hàm conv. Sau đó, trên đầu ra của sử dụng conv tìm thấy để có được các chỉ số có liên quan.

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

Bạn có thể giải quyết việc này như là một nhiệm vụ tìm kiếm chuỗi, bằng cách tìm chuỗi số không có độ dài thresh (chức năng STRFIND rất nhanh)

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

Lưu ý rằng chuỗi con dài hơn sẽ được đánh dấu ở nhiều địa điểm nhưng cuối cùng sẽ được đã tham gia khi chúng tôi thêm vào giữa các vị trí từ các khoảng thời gian bắt đầu tại startIndex để kết thúc tại start+thresh-1.

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

Lưu ý rằng bạn luôn có thể trao đổi bước cuối cùng này bằng giải pháp CUMSUM/FIND của @gnovice từ linked question.

Answer 5

Như gnovice cho thấy, chúng tôi sẽ làm một bài kiểm tra ngưỡng để làm cho "gần bằng không" thực sự không:

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

Sau đó tìm vùng có tổng tích lũy không tăng:

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

Ghi nhớ 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 

Chúng tôi lưu ý rằng vector islands của chúng tôi đã có những người trong startInd địa điểm, và cho các mục đích của chúng tôi endInd luôn luôn đi kèm thresh điểm sau (chạy dài đã chạy của những người thân trong islands)

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

thử nghiệm

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

Dưới đây là trong NumPy (cũng đã trả lời 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]) 

Ví dụ:

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

Answer 7

câu trả lời ở trên bởi genovice có thể được sửa đổi để tìm ra chỉ số của các yếu tố khác không trong một vector như:

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