Identifying Largest Submatrices in a 0/1 Matrix?

[pablrodr]

In the following 0/1 matrix I'm trying to identify every largest submatrices formed by 1's as shown in the picture.
Submatrices can have just one row only if they have more than 3 columns.
Submatrices can have just one column only if they have more than 3 rows.
Submatrices should have less than maxcol columns and maxrow rows and more than mincol and minrow. In the picture mincol=minrow=2. maxrow=maxcolumn=6.
I've been searching for this problem, looks like an already solved problem but couldn't find it elsewhere.

 

[Mark44]

In the following 0/1 matrix I'm trying to identify every largest submatrices formed by 1's as shown in the picture.
Submatrices can have just one row only if they have more than 3 columns.
Submatrices can have just one column only if they have more than 3 rows.
Submatrices should have less than maxcol columns and maxrow rows and more than mincol and minrow. In the picture mincol=minrow=2. maxrow=maxcolumn=6.

From your picture, a submatrix should have at least minrow rows and at least mincol columns. This is different from what you said, which would imply that a two-dimensional submatrix would have to be 3 X 3 or larger.

Also, it should be possible for a submatrix to have at most minrow rows and at most mincol columns for a matrix all of whose entries are 1's.

I've been searching for this problem, looks like an already solved problem but couldn't find it elsewhere.

Presumably this is a problem that you want to automate; otherwise you could visually inspect the matrix and pick out the submatrices.

Finding the one-dimensional submatrices shouldn't be too hard, but finding the two-dimensional submatrices will be harder, I believe. For the the horizontal 1D submatrices, for each row, scan across it until you reach a 1. From this cell, continue scanning for 1's. If you encounter three or more in that row, you have a submatrix. You'll need to remember where the submatrix started, and how many 1 cells there were in it.

For the vertical 1D submatrices, for each column do essentially the same as described above, but scan downward. Again, if you hit a submatrix, you need to keep track of its starting cell and how many cells are in it.

Finding the 2D submatrices is harder. I have several ideas, but none of them are fully thought out.

I mentioned earlier about the need for keeping track of the starting cells and lengths of the 1D submatrices. One possibility would be to create a tracking matrix of the same size as the one you're working with, but whose cells contain a pair of numbers. Here are some examples of a cell entry in this tracking matrix (T) that I envision:
T(1, 2) = (3, 0)
The cell at row 1, column 2 is the start of a horizontal submatrix of length 3.

T(2, 1) = (0, 3)
The cell at row 2, column 1 is the start of a vertical submatrix of length 3.

T(2, 1) = (3, 4)
The cell at row 2, column 1 is the start of a horizontal submatrix of length 3 and a vertical submatrix of length 4.

All other entries in the tracking matrix would be (0, 0).