how to find all submatrices values are greater than threshold in a given matrix (without using numpy and Scipy)

Question

I'm working on microcontrollers, where it doesn't supports numpy or scipy. I want to extract all submatrices greater than given threshold value in matrix.

myMtarix = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 204, 0, 0, 0, 0, 0, 0, 60, 0, 0, 284, 0],
            [0, 100, 0, 74, 421, 157, 0, 0, 0, 0, 317, 364, 736, 245, 1470, 0],
            [0, 717, 0, 258, 879, 496, 0, 0, 0, 0, 0, 671, 766, 725, 1429, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

myMatrix = 6*16 matrix and i want to extract

subMatrix1 = [[100],
             [717]]

subMatrix2 = [[0, 204, 0],
             [74, 421, 157],
             [258, 879, 496]]

subMatrix3 = [[0, 60, 0, 0, 284],
              [317, 364, 736, 245, 1470],
              [0,671, 766, 725, 1429]]

and threshold = 10

I tried something like this

Here, collecting the values > threshold and their indexes

    threshold = 10
    pressureIndexes = []
    pressurePoints = []
    reqValue = []
    reqIndex = []
    
    reqValue = [myMatrix[i][j] for i in range(numRows) for j in range(numCols) if(myMatrix[i][j] > threshold)]
    reqIndex = [[i,j] for i in range(numRows) for j in range(numCols) if(myMatrix[i][j] > threshold)]
 

from here, I'm try to extract the the exact boundaries of submatrices

    Xend = Xstart = reqIndex[0][0]
    Yend = Ystart = reqIndex[0][1]
    dummy = []  
    for i in range(1,len(reqIndex)):
        PXstart = Xstart
        PXend  = Xend
        PYstart = Ystart
        PYend  = Yend
        Xstart = min(Xstart,reqIndex[i][0])
        Xend = max(Xend,reqIndex[i][0])
        Ystart = min(PYstart,reqIndex[i][1])
        Yend = max(PYend,reqIndex[i][1])
        if(abs(PXend-Xend) > 2 or abs(PYend-Yend) > 2):
            dummy.append([[PXstart,PXend],[PYstart,PYend]])
            Xend = Xstart = reqIndex[i][0]
            Yend = Ystart = reqIndex[i][1]
    dummy.append([[Xstart,Xend],[Ystart,Yend]])
    print()
    
    for i in dummy:
        print(i)
    print('---------------------------------------------------------')
    sleep(1)

OUTPUT :

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 204, 0, 0, 0, 0, 0, 0, 60, 0, 0, 284, 0]
[0, 100, 0, 74, 421, 157, 0, 0, 0, 0, 317, 364, 736, 245, 1470, 0]
[0, 717, 0, 258, 879, 496, 0, 0, 0, 0, 0, 671, 766, 725, 1429, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        
                
[[1, 1], [4, 4]]  # [[rowStarting,rowEnding],[colStarting,colEnding]] for value 204
[[1, 1], [11, 11]]
[[1, 3], [1, 14]]

Answer 1

Here is a way to do it, it will returns a list of sub-matrices with no 0 line or column:

mm       = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 204, 0, 0, 0, 0, 0, 0, 60, 0, 0, 284, 0],
            [0, 100, 0, 74, 421, 157, 0, 0, 0, 0, 317, 364, 736, 245, 1470, 0],
            [0, 717, 0, 258, 879, 496, 0, 0, 0, 0, 0, 671, 766, 725, 1429, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]




## values below threshold are set to 0
def threshold(m, th=10):
    for l in range(len(m)):
        for c in range(len(m[l])):
            v=m[l][c]
            if v < th:
                v = 0
            m[l][c] = v
    return m


## helper functions to handle matrixes

## work with a colum values
def column(m, c):
    return list(map(lambda x: x[c], m))


## cut and drop left of matrix
def cutleftofcolumn(m, c):
    return list(map(lambda x: x[c+1:], m))


## cut and drop right of matrix
def cutrightofcolumn(m, c):
    return list(map(lambda x: x[:c], m))


## remove 0 borders of the matrix
def removeBorders(m: list) -> list:
    test = True
    while test:
        test = False
        #if sum(m[0])==0:
        if all(map(lambda x: x==0, m[0])):
            m = m[1:]
            test = True
        #if sum(m[-1])==0:
        if all(map(lambda x: x==0, m[-1])):
            m = m[:-1]
            test = True
        #if sum(column(m, 0))==0:
        if all(map(lambda x: x==0, column(m, 0))):
            m=cutleftofcolumn(m, 0)
            test = True
        #if sum(column(m, -1))==0:
        if all(map(lambda x: x==0, column(m, -1))):
            m=cutrightofcolumn(m, -1)
            test = True
    return m


## split on a 0 column and returns 2 matrices
def splitv(m, c):
    a=cutleftofcolumn(m, c)
    b=cutrightofcolumn(m, c)
    return [a, b]


## split on a 0 line and returns 2 matrices
def splith(m, l):
    return [m[0:l], m[l+1:]]



mm = threshold(mm, 10)

listMatrices = [mm]


test = True
while (test):
    test=False
    index = 0
    while (len (listMatrices)>index):

        ## get first matrix of the list
        m = listMatrices.pop(0)

        ## removes 0 borders of the matrix
        m = removeBorders(m)
    
        lll=[]    
        ## try to find an horizontal split on 0 line
        if lll==[]:
            for l in range(len(m)):
                #if sum(m[l])==0:
                if all(map(lambda x: x==0, m[l])):
                    lll = lll + splith(m, l)
                    test = True
                    break
    
        ## try to find a vertical split on 0 column
        if lll==[]:
            for c in range(len(m[0])):
                cc = column(m, c)
                #if sum(cc)==0:
                if all(map(lambda x: x==0, cc)):
                    lll = lll + splitv(m, c)
                    #print("Csum=0", c)
                    test = True
                    break
            
        if lll==[]:
            listMatrices.append(m)
        else:
            for l in lll:
                listMatrices.append(l)
        index+=1


print(listMatrices)

Output is:

[[[0, 60, 0, 0, 284], [317, 364, 736, 245, 1470], [0, 671, 766, 725, 1429]],
 [[0, 204, 0], [74, 421, 157], [258, 879, 496]],
 [[100], [717]]]