Get coordinates of squares in numpy matrix

Given the following numpy matrix

import numpy as np
np_matrix = np.array([[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,0,0,0]
                    ,[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,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,0,0,0,0,0,0,0,0,0,0,1,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,0,0,0,0,0,0,0,0,0,0,1,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,0,0,0,0,0,0,0,0,0,0,1,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,0,0,0,2,0,0,0,0,0,0,1,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,0,0,0,0,0,0,0,0,0,0,1,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,0,0,0,0,0,0,0,0,0,0,1,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,1,1,1,1,1,1,1,1,1,1,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,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,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,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,0,0,0,2,0,0,1,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,0,0,0,0,0,0,1,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,0,0,0,0,0,0,1,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,0,0,0,0,0,0,1,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,0,0,0,0,0,0,1,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,0,0,0,0,0,0,1,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,1,1,1,1,1,1,0,0,0]
                    ,[0,0,0,1,1,1,1,1,1,1,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,0,0,0,0,0,1,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,1]
                    ,[0,0,0,1,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0]
                    ,[0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0]
                    ,[0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0]
                    ,[0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0]
                    ,[0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0]
                    ,[0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,0]
                    ,[1,1,1,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,0,0]
                    ,[0,0,1,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,0,0]
                    ,[0,0,1,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,0,0]
                    ,[0,0,1,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,0,0]
                    ,[0,0,1,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,0,0]
                    ,[0,0,1,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,0,0]
                    ,[2,0,1,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,0,0]])

print(np_matrix)
print(np_matrix.shape)

which can be represented as an image.

enter image description here

Here are a few assumptions about the input matrix:

  • The matrix shape can vary. It is not a fixed size.
  • The number of squares varies from matrix to matrix. But there is always at least one square in the matrix.
  • For each green dot there is a square around it and squares have a single dot inside them. The dot inside the square is marked with number 2
  • Squares are sequential on the X axis and square's borders never overlap the borders of other squares. Squares borders are marked with number 1
  • The white space is marked with number 0

I have two questions. In the most efficient way how can i get an array with the coordinates of all the green dots? And how can i get an array with all the corners for the squares around a green dot?

enter image description here

Here is the result i am looking after for this example:

green_dots_coordinates = [
    [0,0],  # dot 1 with coordinates x1, y1 inside square 1
    [7,12], # dot 2 with coordinates x2, y2 inside square 2
    [16,27],# dot 3 with coordinates x3, y3 inside square 3
    [29,21],# dot 4 with coordinates x4, y4 inside square 4
    [34,7], # dot 5 with coordinates x5, y5 inside square 5
]



sqaures_corners_coordinates = [
    #square nr 1
    [
        [0,6], # x1, y1
        [2,6], # x2, y2
        [0,0], # x3, y3
        [2,0], # x4, y4
    ],

    #square nr 2
    [
        [3,14], # x1, y1
        [9,14], # x2, y2
        [3,7], # x3, y3
        [9,7], # x4, y4
    ],

    #square nr 3
    [
        [12,31], # x1, y1
        [23,31], # x2, y2
        [12,24], # x3, y3
        [23,24], # x4, y4
    ],

    #square nr 4
    [
        [25,22], # x1, y1
        [32,22], # x2, y2
        [25,15], # x3, y3
        [32,15], # x4, y4
    ]

    ,#square nr 5
    [
        [33,13], # x1, y1
        [35,13], # x2, y2
        [33,0], # x3, y3
        [35,0], # x4, y4
    ],

]

1 answer

  • answered 2017-11-13 08:39 Daniel F

    Your output format is frankly pretty bizarre and requires reversing the order of indices a lot, (and makes the output fairly useless for indexing the original array) but this works:

    def find_boxes(np_matrix):
        np_mat = np_matrix[::-1, :]  # reversed in expected output
        def find_extent(arr, val):
            xn = arr.size
            x0 = np.flatnonzero(arr == 1)
            xi = np.searchsorted(x0, val, side = 'right')
            if xi == x0.size:
                x1 = x0[xi-1]
                x2 = xn - 1
            elif xi == 0:
                x1 = 0
                x2 = x0[xi]
            else:
                x1 = x0[xi-1]
                x2 = x0[xi]
            return np.array([x1, x2])
    
        green = np.where(np_mat == 2)
        green = tuple(g[np.argsort(green[-1])] for g in green)
        coords = np.empty((green[0].size, 2, 4))
    
        for i, (x, y) in enumerate(zip(*green)):
            coords[i, 0] =   np.tile(find_extent(np_mat[x, :], y),       2)
            coords[i, 1] = np.repeat(find_extent(np_mat[:, y], x)[::-1], 2)  # reversed again
        return np.stack(green)[::-1].T, coords.swapaxes(1,2).astype(int)
        # reversed again and transposed
    

    Testing:

    find_boxes(np_matrix)
    Out: 
    (array([[ 0,  0],
            [ 7, 12],
            [16, 27],
            [29, 21],
            [34,  7]], dtype=int32), 
     array([[[ 0,  6],
             [ 2,  6],
             [ 0,  0],
             [ 2,  0]],
    
            [[ 3, 14],
             [ 9, 14],
             [ 3,  7],
             [ 9,  7]],
    
            [[12, 31],
             [23, 31],
             [12, 24],
             [23, 24]],
    
            [[25, 22],
             [32, 22],
             [25, 15],
             [32, 15]],
    
            [[33, 13],
             [35, 13],
             [33,  0],
             [35,  0]]]))