2
\$\begingroup\$

The following MATLAB code takes in multiple peak coordinates and heights and eliminates lesser peaks that are within a certain distance threshold of the highest peak of the vicinity. Is there a better way to implement this code? Does a more efficient algorithm exist?

Code

function [ the_peaks,idx_list ] = max_peaks( peak_list, vicinity_threshold )
%MAX_PEAKS(peak_list, vicinity_threshold) returns the highest peaks within
%the vicinity specified by the vicinity_threshold.
%
%   peak_list is an array with rows defined by [x,y, amplitude]
%
%   vicinity_threshold is the distance within which all lesser peaks are
%   killed.
[sorted_peaks,orig_idx]=sortrows(peak_list,3,'desc');
the_peaks=zeros(size(sorted_peaks));     % Preallocate
idx_list=zeros(length(sorted_peaks),1);
peak_idx=1;
while(~isempty(sorted_peaks))
    the_peaks(peak_idx,:)=sorted_peaks(1,:);     %The greatest peak.
    idx_list(peak_idx)=orig_idx(1);
    peak_idx=peak_idx+1;
    D=pdist2(sorted_peaks(1:end,1:2),sorted_peaks(1,1:2));     %Distance to other peaks
    np=D<vicinity_threshold;     % Peaks in the vicinity
    sorted_peaks(np,:)=[];     % Kill peaks in the vicinity
    orig_idx(np)=[];
end
idx_list(~any(the_peaks,2),:)=[];     % clear preallocated extras
the_peaks(~any(the_peaks,2),:)=[];
end

example

test_peaks=[1,1,0.5; 5,5,0.9; 5,1,0.6; 300,300,0.2; 303,303,0.7; 1,100,0.9; 1,104,0.95; 1,250,.7; 1,200,.75];
mP=max_peaks(test_peaks,10)
scatter (test_peaks(:,1),test_peaks(:,2),'o');
hold on
scatter (mP(:,1),mP(:,2),'*');
\$\endgroup\$
  • \$\begingroup\$ This depends on the number of peaks in your list. For short lists this code is probably acceptably fast. For very long lists it will be terribly slow. Look into R trees. That's a data structure where you store points, and you can cheaply find all points within a bounding box. You define a bounding box around one peak, and immediately find all peaks within that box, which is I think the same way you define distance here. If you need to prune based on Euclidean distance, you have a short list of close points to check. \$\endgroup\$ – Cris Luengo Dec 8 '17 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.