3

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
    ],

]
RaduS
  • 2,465
  • 9
  • 44
  • 65
  • 2
    `xg,yg=np.where(m==2)` give you green points coordinates. A bit more time for the rest ;) – B. M. Nov 12 '17 at 21:52
  • how big in `np_matrix` and how much memory do you have? – Daniel F Nov 13 '17 at 07:31
  • np_matrix can get up to 10000x10000 i have 32gb ram – RaduS Nov 13 '17 at 07:33
  • Ok, so no hough transforms. Are all `1` values necessarily part of a rectangle? – Daniel F Nov 13 '17 at 07:39
  • nope, the matrix shape must remain the same – RaduS Nov 13 '17 at 07:41
  • Well, all rectangles borders are marked with 1 in the input matrix. With the exception for the borders of the matrix, where sometimes the border of the rectangle is not visible. See the above image. In that case the border of the matrix becomes the border of the rectangle as well. – RaduS Nov 13 '17 at 07:45
  • 1
    I post an alternative answer, with minimal impact I think. – B. M. Nov 15 '17 at 12:19

2 Answers2

1

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]]]))
Daniel F
  • 13,620
  • 2
  • 29
  • 55
  • Waow, thank you @DanielF This is perfect :) I know that the reverse indexing was a bit strange and i thank you that you implemented it in the function :) – RaduS Nov 13 '17 at 08:58
  • 1
    I assume that's you serial voting me. Don't bother, those upvotes will get deleted. Just one is enough for me :) – Daniel F Nov 13 '17 at 09:07
1

Another method, which makes the four directions symetric : 

rm = m[::-1].T                            # (j,-i) to (x,y)
green = np.where(rm==2)                   # the costly operation
centers = np.vstack(green).T

rm[green] = 0
res = []

for x,y in centers:
    for s in (-1,1):                      # rear/front
        for t in range(2) :               # vertical/horizontal             
            v = *_,save = rm[x,y::s]            
            v[-1] = 1                     # sentinel
            res.append(y + s*v.argmax())  # find the first 1
            v[-1] = save 
            x,y,rm = y,x,rm.T             # turn 

rm[green] = 2  

coordinates = np.array(res).reshape(-1,4) 
corners = coordinates.take([[1,2],[3,2],[1,0],[3,0]],axis=1)

This avoids to deal with the included/excluded behavior of Python slices, and manages borders with a sentinel system.

print(centers);print(corners)

[[ 0  0]
 [ 7 12]
 [16 27]
 [29 21]
 [34  7]]
-----------
[[[ 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]]]
B. M.
  • 18,243
  • 2
  • 35
  • 54
  • Thank you B. M. for the answer i will test for performance on bigger matrices – RaduS Nov 15 '17 at 19:24
  • I don't think any difference / @ Daniel F solution, since `green = np.where(rm==2) ` is `O(n²)` . but if you find a other way to track the centers, I am confident about the match ;) – B. M. Nov 15 '17 at 19:37