Saddle points of a 2D matrix

the problem I'm working on is to find the saddle points of a matrix and now I'm trying this ...

• nested loop to check every element
• check if the element is the smallest in its column and the biggest in its row
• if it is,print it into the matrix'indices'
• if there was none,print empty matrix....and the code [row,col]=size(matrix); for I=1:row for j=1:col if matrix (I,j)==max(matrix, I)&&matrix (I,j)==min(matrix, j) indices=[i j;]: else indices=[ ] end end endsome help with the syntax please,thanks!!

Answer 1

[Jon]

Here is a simple approach. Note I define a saddle point as one that is either the largest in its column and smallest in its row or the smallest in its column and largest in its row. Maybe you only want to look for the second kind in which case you can modify the approach accordingly.

Also this code is quite inefficient. You could further optimize it by finding and saving the column maximums, column minimums, row maximums and row minimums before entering the loop.

You could also probably vectorize this further and not use a loop at all, but I think you wanted to see how the basic syntax would look.

% make a matrix to try algorithm on
% there are saddle points at 2,2 and 4,4
A = [10 12 7 3 12;
    3 10 6 2 8;
    12 24 17 6 10;
    15 21 10 8 12;
    1 18 22 4 15];
disp A

% get dimensions of the matrix
[numRows,numCols] = size(A);

% preallocate array to hold indices for saddle points, there can be at most two
indices = zeros(2,2);
% loop through rows and columns of matrix
numSaddle = 0; % counter

for iRow = 1:numRows
    for jCol = 1:numCols
        % check if it is the biggest element in its row and smallest
        % element in its column
        brsc = A(iRow,jCol) == max(A(iRow,:)) && A(iRow,jCol) == min(A(:,jCol));
        
        
        
        % check if is the smallest element in its row and biggest
        % element in its column
        srbc = A(iRow,jCol) == min(A(iRow,:)) && A(iRow,jCol)== max(A(:,jCol));
        
        if brsc || srbc
            numSaddle = numSaddle + 1;
            indices(numSaddle,:) = [iRow,jCol];
        end
        
    end
end
% delete off the unused entries in the indices array
indices = indices(1:numSaddle,:);

% display the result
disp(indices)

% display saddle points
for k = 1:numSaddle
    disp(A(indices(k,1),indices(k,2)))
end

[Marco Nashaat]

Thanks for your work but I can use some help with the code provided ...sorry for any trouble!!

function indices=saddle(M)
    indices=[];
    [row,col]=size(M);
    for I=1:row
        for j=1:col
            if M(I,j)==max(M(I,1:col))&&M(I,j)==min(M(1:row,j))
                indices=[I j,];
            end
        end
    end
end

apparently indices returns only the last saddle point how can I fix this to return every single one,thanks!!

[Jon]

First, I think that there will only be one element that satisfies your criteria. I think you need to use the vice verse part (largest in its column and the smallest in its row) to get two saddle points.

Once you have modified your logic for that

So that you keep adding the new solutions to the list, replace the line

indices=[I j,];

with

indices = [indices;[I,j]]; % concatenate indices

For performance it is better to preallocate a matrix with the maximum size rather than having it grow in the loop, but the above approach will work.

You may have some other problems too. I think you should replace your

 M(I,1:col)

with

M(I,:)

and

M( 1:row,j)

with

M(:,j)

so that you get the max and mins over the all of the columns and rows resp rather than just up to you current row and column

Finally for consistency if you use a capital I for the rows you should use a capital J for the columns. It is also good to indent your code where it loops. Try selecting your whole code and the ctrl-I will do a smart indent.

[Marco Nashaat]

Thanks a lot It works perfectly

[Rishi Diwan]

function indices=saddle(M)
    indices=[]; c=1;
    [row,col]=size(M);
    for I=1:row
        for j=1:col
            if M(I,j)== max(M(I,1:col)) && M(I,j)==min(M(1:row,j))
                indices(c,1)=I;
                indices(c,2)=j;
                c=c+1;
            end
        end
    end
end

[Shaon Talukdar]

Great!!! It Worked.

[Faraz Ahmad]

@Rishi Diwan.Thanks a lot

[Kushagra Mehrotra]

Thanks Rishi !

Answer 2

[Sahil]

    function indices = saddle(M)

saddle_m =  zeros(size(M));

row_maxima = max(M, [], 2);
col_minima = min(M, [], 1);

indices = [];
for i = 1:size(M, 1)
    for j = 1:size(M, 2)
        if M(i, j) == row_maxima(i) && M(i, j) == col_minima(j)
            saddle_m(i, j) = 1;
            indices = [i, j; indices];
        end
    end
end
end

[Nihal Dwivedi]

thanks this worked perfectly

[Jessamyn Johnson]

Could you explain to me what the function of the saddle_m is?

Answer 3

[fred ssemwogerere]

Hello, i think something like this should do nicely:

% To check which element is the smallest in its column, and biggest in its row, for a given matrix say, 
% "b", you can first pre-allocate a matrix of zeros where the valid saddle points will be input.
indices=zeros(size(b)); % pre-alocating "indices" based on size of assumed matrix "b"
% Next determine the minimum values of each column of the matrix, "b"
b_colmin=min(b);
% Determine the maximum values for each row of "b" by first taking the transpose of "b"
b_rowmax=max(b'); 
% Check for membership of "b_colmin" in "b_rowmax"."lm" is a vector of lowest indices in "b_rowmax"  for each value of "b_colmin" in "b_rowmax"  
[~,lm]=ismember(b_colmin,b_rowmax);
% find the column indices of non-zero indices ("nzCol") in "lm", and the corresponding vector on non-zero values ("nzVec"). The vector "nzVec" in actual sense will be a vector of row indices for the saddle points.
[~,nzCol,nzVec]=find(lm);
% Input saddle points into marix "indices" based on indices
indices(nzVec,nzCol)=b(nzVec,nzCol);

[Marco Nashaat]

Thanks but I guess there might be a bug....when asking for membership let's say the maximum value of a row was actually equal to minimum of Irrelative column then "indices" will return the index of a wrong element!! correct me if I was wrong,thanks

[fred ssemwogerere]

"indices" returns the values that are maximum in a row, but minimum in their column, at their indexed positions in an assumed matrix "b". However, if the aim is to only get the indices of the saddle points, then all you need will be: "nzVec" and "nzCol". You can write this into an array as [nzVec,nzCol].

Answer 4

[darova]

One way to use surfnorm

clc,clear

% generate some data
[X,Y] = meshgrid( linspace(-1,1,20) );
Z = X.^2-Y.^2;

[nx,ny,nz] = surfnorm(X,Y,Z);       % normal vectors
[az,el,rho] = cart2sph(nx,ny,nz);   % find azimuth and elevation
[~,ix] = max(el(:));                % find maximum elevation
mesh(X,Y,Z)
hold on
scatter3(X(ix),Y(ix),Z(ix),50,'r','filled')      % saddle point
quiver3(X,Y,Z,nx,ny,nz,'b')          % show normal vectors
hold off

axis equal

Answer 5

[Ajijul Mridol]

function indices=saddle(M)
[row,col]=size(M);
k=1;
for i=1:row
    for j=1:col
        %check if it is the biggest element in row and smallest in that column
        if (M(i,j)==max(M(i,:)) | M(i,j)==M(i,:)) & (M(i,j)==min(M(:,j)) | M(i,j)==M(:,j))
            indices(k,1)=i; 
            indices(k,2)=j;
            k=k+1;
        end
    end
end
if k==1
    indices=[]; %return an empty matrix if there is not saddle point
    return
end
end

Answer 6

[Sharnam Singhwal]

function indices=saddle(M)
[row,col]=size(M);
count=0;
indices=[];
for i= 1:row
    for j= 1:col
        if M(i,j)==max(M(i,:)) && M(i,j)==min(M(:,j))
            indices=[indices;i j];
        end
    end 
end 

end

Answer 7

[shubham nayak]

function indices=saddle(z)
[a,b]=size(z);c=1;
indices=[];
for i = 1:a
    for j = 1:b
        maxrow(i,j)=max(z(i,1:b));
        if(maxrow(i,j)<=min(z(1:a,j)))
            indices(c,1)=i;
            indices(c,2)=j; 
            c=c+1;
        end
    end
end
end

Answer 8

[Soumyadip Sikdar]

function [number,indices]=saddle_point(M)
s=size(M);
n=0;
indices=[];
number={};
for i=1:s(1)
    for j=1:s(2)
        l=M(i,j)>=M(i,:);
        x=M(i,j)<=M(:,j);
        if l==ones(1,s(2))& x==ones(s(1),1)
            n=n+1;
            number{n,1}=[i,j];
        else
            continue
        end
    end
end
indices=cell2mat(number);

This might help you out

Answer 9

[muhammad akl]

% this is my answer
function indices=saddle(M)
[r,c]=size(M);
indices=[];
for i=1:r
    for j=1:c
        if M(i,j) >= max(M(i,:)) && M(i,j) <= min(M(:,j))
            indices=[indices; i,j];
        end
    end
end       

[DGM]

Care to explain how your answer is different from this answer?

https://www.mathworks.com/matlabcentral/answers/504828-saddle-points-of-a-2d-matrix#answer_485798

... because it's not consequentially different. The only changes are a trivial change of variable name, some extra spaces scattered about, and an inconsequential change of comparison operators.

When you're adding an answer to a thread full of other answers, it's important to make sure you're adding something new to the conversation. It's entirely appropriate to challenge existing answers or improve upon them, but if you're repeating what's already been presented, or if it's unclear how your answer is worth considering, there's no value added to what the reader sees.

Answer 10

[Walter Roberson]

M = imread('cameraman.tif');

SM = [0 0 0; 1 1 1; 0 0 0];
maxmask1 = imregionalmax(M, SM);
minmask1 = imregionalmin(M, SM);
maxmask2 = imregionalmax(M, SM.');
minmask2 = imregionalmin(M, SM.');

loc_is_saddle = (maxmask1 & minmask2) | (minmask1 & maxmask2);

imshow(M); title('original');

imshow(loc_is_saddle); title('saddle points')