Valley/Ridge tracing in N-D data

This is both a question about whether an appropriate Matlab method/toolbox exist, or if the mathematically inclined folks on here have any good references to help:

The basic issue is to trace the peak (or valley) of some N-dimensional array of scalar values. This would preferably include regularization or some other cost function so as to reduce the effects of noise and force some smoothness on the resulting curve.

The mental model here is a topographic map, where I would like to find the peak of a ridgeline. However, let us say the map also has a considerable amount of "noise" in the form of rock-piles and big mounds of dirt scattered across the ridge. Let us also say that the ridge might have side-ridges (spurs) that sprout from the main ridge. I need a method to estimate the position of the main ridge so that (a) the path is smooth and (b) it maximizes some measure such as the total height along the path so as to avoid getting dragged off to local maxima (like spur ridges).

I can think of a few ways to try to tackle this: the obvious being find max and use gradient to walk to next point, but this is going to be sensitive to noise, and like to run off on local maxima (side spurs) at the first opportunity. The hope is to find a tried and true method that I can implement rapidly in Matlab. Especially in higher N-Dimensions.

Thanks, Dan

Answer 1

[Michael Judge]

Hi Daniel,

I was looking for a similar function and stumbled upon the tfridge function. It is working nicely for me, although I cannot find much information on how it works.

Cheers, Michael

[Michael Judge]

Now that I'm checkin in on this again, I realize that you were looking for N-dimensional ridge tracing, so tfridge probably won't help much.

Answer 2

[Steffen B. Petersen]

Hi Dan

I have a simple code for 'Ridge walking' in 2D gray scale images. Maybe this could be extended to ND although it may not be trivial to define the threshold. Another challenge is that it may 'explode' because of the higher dimensionality, ie the number of ridges to map may be infinite. The code is below - it is called from a gui, but you can probably figure out how to adapt it to your setting.

function axes1_PlasmidButtonDownFcn(hObject, eventdata, handles)

mydata=struct('area',{},'max',{},'mean',{},'median',{},'integral',{}); handles=guidata(hObject); handles.commandcount=handles.commandcount+1; handles.commandlist(handles.commandcount).name='Axes1 SpotButtonDownFcn'; fprintf(1,'\n\nAxes1_SpotButtonDownFcn Called'); myim=handles.image(handles.imnum).data;

[sx sy sz]=size(myim); if sz==3 myim=rgb2gray(myim); end

I2=im2bw(myim,0.25); %This is hardwired to 0.25 -- has to change

boundaries=bwboundaries(I2,'holes'); [bx by]=size(boundaries); k=0; sxmin=100; for i=1:bx b=boundaries{i}; [sx sy]=size(b); if sx>sxmin k=k+1; pboundaries{k}=boundaries{i}; end end bdetails=boundaries_details(boundaries,myim); size(bdetails) handles.boundaries=boundaries; handles.bwimage=I2; immin=min(min(myim)); immax=max(max(myim)); axes(handles.axes1); h1=imshow(double(myim),[immin immax]); mybutton=get(gcf,'SelectionType'); update_flag=0; if strcmp(mybutton,'normal')==1 fprintf(1,'\nLEFT BUTTON PRESSED\n'); update_flag=1; end if strcmp(mybutton,'alt')==1 fprintf(1,'\nRIGHT BUTTON PRESSED\n'); axpos=get(gca,'position'); fig2=figure('visible','on','position',axpos); newax = copyobj(handles.axes1,fig2); colormap(handles.colormap); update_flag=0; end if update_flag==1 if handles.count>1 lastx=handles.lastx; lasty=handles.lasty; end fprintf(1,'\nAxes1_SpotButtondownFcn called');

    hold on;
    px=plot(1:sx,1,'b');    
    py=plot(1,1:sy,'r');       
end
drawnow;

mm=get(gca,'currentpoint'); myx=mm(1,1); myy=mm(1,2); [sx,sy]=size(boundaries);

save bdetails bdetails save pboundaries pboundaries

[px,py]=size(pboundaries); for i=1:2:py b=pboundaries{i}; plot(b(:,2),b(:,1),'g','linewidth',2); c=pboundaries{i+1}; plot(c(:,2),c(:,1),'b','linewidth',2); drawnow; % Now find the curve running on the ridge between the outer and inner % boundary [bx,by]=size(b); [cx,cy]=size(c); for j=1:bx for k=1:cx bdist(k)=sqrt((c(k,1)-b(j,1))^2+(c(k,2)-b(j,2))^2); end [bdmin bloc]=min(bdist); xr=b(j,1)+(c(bloc,1)-b(j,1))/2; yr=b(j,2)+(c(bloc,2)-b(j,2))/2; ridge(j,1)=xr; ridge(j,2)=yr; end plot(ridge(:,2),ridge(:,1),'r','linewidth',2);

    %Now extract the image intensity values from the original image and
    %plot them in axes2
    [rx ry]=size(ridge);
    hz=1;
    for i=1:rx
        xc=int16(ridge(i,1));
        yc=int16(ridge(i,2));
        myval=mean(mean(myim(xc-hz:xc+hz,yc-hz:yc+hz)));
        myvector(i)=myval;
    end

end axes(handles.axes2); cla; plot(1:rx,myvector,'b'); set(gca,'Ydir','normal'); title('Plasmid Ridge Walk');

axes(handles.axes3); cla;

mylen=length(myvector); myrange=floor(mylen/2); Y = xcorr(myvector,myrange,'unbiased');

title('Autocorrelation of Plasmid Ridge Walk') xlabel('pixel dist');

axes(handles.axes4); cla; title(''); axes(handles.axes5); cla; title('');

guidata(handles.figure1, handles);

Answer 3

[Constantino Carlos Reyes-Aldasoro]

Hello

Not sure if you still need this, but I have implemented a ridge tracing using Lindeberg's Scale Space algorithms. The code and a description is available here:

https://uk.mathworks.com/matlabcentral/fileexchange/67933-scale-space-vessel-tracing-implementation-of-lindeberg-s-algorithms?s_tid=srchtitle

https://github.com/reyesaldasoro/Scale-Space-Vessel-Tracing