To find submatrix having max. sum

The function takes matrix(A) as input and computes the sum of elements each of its submatrices, and finds the maximum sum. The submatrix is of the form contiguous set of elements of the original matrix. If there are more than one with maximum sum the function can pick any one of them. The function form is function [row, col, numrows, numcols, summa]= maxsubsum (A); where row and col specify the indexes of the top left corner of the submatrix with maximum sum , numrows and numcols are its dimensions and summa is the of the elements.

[Azzi Abdelmalek]

Can you illustrate with an example?

[Muhammad Usman Saleem]

@Azzi , this is an example as input argument

function [row,col,numrows,numcols,summa] = maxsubsum(A)

Answer 1

[Image Analyst]

This is trivial, at least for window with odd numbers of elements. Only slightly less trivial for even window widths. Just use conv2(). But you have to specify the size of the submatrix, in two for loops because you need to find it's size. Obviously, for an all positive matrix, the submatrix with the biggest sum would simply be the same as the entire image with the sum being the sum of all the matrix elements. If the matrix has positive and negative values, and you have to try every submatrix from a 1 by 1 to a rows-by-cols, and do that for every element in the matrix, then it gets time consuming and very complicated - basically use conv2 for every possible submatrix size which could be hundreds depending on the size of the matrix.

[rows, columns] = size(A);
overallMaxSum = -inf;
for smColumns = 1 : columns
    for smRows = 1 : rows
        sumMatrix = conv2(inputMatrix, ones(smRows, smColumns), 'same');
        % Find max value
        maxValue = max(sumMatrix);
        if maxValue > overallMaxSum 
            numrows = smRows;
            numcols = smColumns;
            % Now find location of that max value.
            % Window will be centered about that max, so now
            % find the starting and stopping rows and columns
            % for the submatrix centered at that location
            % by subtracing half the window width.
        end
    end
end

I'm going to leave the last few lines to you since it seems to be homework.

[Muhammad Usman Saleem]

@Image thanks for your contributions.. to me % Now find location of that max value = maxValue(sumRow,sumCol)?? I do not get from your that comments

              % Window will be centered about that max, so now
              % find the starting and stopping rows and columns
              % for the submatrix centered at that location
              % by subtracing half the window width.
After reading these comments , i am getting more confuse.. Easily hints required please..Thanks in advance

[Image Analyst]

Muhammad, there are only 3 lines of code left for you to do. And the last two are essentially the same. If I do them for you then you will have done nothing on your homework at all. I'll start them for you but you've go to finish the last few characters so at least you've originated a few characters of your homework and it's not all my work.

[row, col] = find(
row = row - floor(...... % Back up a half window width to the top left corner.
col =

Once you have it solved, then maybe you can mark it as "Accepted" - thanks in advance.

[Muhammad Usman Saleem]

@Image thank you very much for your assistance... I am now using that for two lines which you mentioned above

[row, col] = find(sumMatrix);
           row = row - floor(numrows);
           col = col - floor(numcols);

but according to remaining lines find the starting and stopping rows and columns

% find the starting and stopping rows and columns= * _*Is i have to any use the find?? but now in which i shall use find?*_ *
% for the submatrix centered at that location= * _* where i have to use loop here but for which?*_ *
% by subtracing half the window width.= * _*Totally getting confuse in this task?*_ *

[Muhammad Usman Saleem]

Dear @Image , To me i think these three lines give the summma of the sub matrix.?? To sum the element of a matrix i use often use that code

summa=0;
           for i=1:row
               for j=1:col
                   summa=summa+sumMatrix(i,j);
               end
           end

But problem is that it will be come next to for loop..repeating looking for more assistance....

[Image Analyst]

No, and no. Think - what is the half window width? Is it floor(numrows)? No, of course not.

And why are you doing that double for loop to get the sum of the matrix when I already gave you the sum in sumMatrix????

I think you're just trying to race through this without actually thinking it through.

[Muhammad Usman Saleem]

I am getting more confuse... I have no idea about the half of the window... It is my last question and then i will be free from matlab.. forever...

[Muhammad Usman Saleem]

@Image????

[Image Analyst]

Muhammad, it's not that hard. Let's say your window was 5 wide. Let's say your window was centered at column 55. Can't you just draw that out and figure out where the left and right edges would be??? Let me show you:

49 50 51 52 53 54 55 56 57 58 59   <- Your columns numbers
             X  X  X  X  X         <- Your 5 wide window.
            -2 -1  0  1  2         <- Position relative to center

So it looks like the left edge of the window is -2 to the left of the center. So find the row and column of the max value

[rowOfMax, colOfmax] = find(sumMatrix == maxValue);

But rowOfMax and colOfmax are the location of the center, so you need to subtract half the window width. But you can't take smRows/2 and smColumns/2 because you can't start at half pixels so you need to convert the 5/2 = 2.5 into 2. You do that with the floor() function. So the left edge is colOfMax - floor(cmColumns/2).

row = rowOfMax - floor(smRows/2);
col = colOfMax - floor(smColumns/2);

That pretty much explains it in excruciating detail . Stick those lines into my prior code and that pretty much completes your assignment. Please mark the Answer as Accepted. Thanks in advance.