Python outline for binary 2D matrix

Question

I want to calculate the convex hull around a shape in an NxM binary matrix. The convex hull algorithm expects a list of coordinates, so I accept numpy.argwhere (im) to have all the coordinates of the point of the shape. However, most of these points do not contribute to the convex hull (they lie inside the shape). Since the computation time of the convex hull is at least proportional to the number of points that it receives as input, I came up with the idea of ​​filtering out a lot of useless points in advance and transmitting only those that span the outline. The idea is quite simple: for each row in the NxM binary matrix, I take only the minimum and maximum indices. For example:

im = np.array([[1,1,1,0], [1,0,1,1], [1,1,0,1], [0,0,0,0], [0,1,1,1]], dtype=np.bool) outline = somefunc(im) 

Then the outline should be read (in tuples or as a 5x2 numpy array, I don't mind):

 [(0,0),(0,2),(1,0),(1,3),(2,0),(2,3),(4,1),(4,3)] 

Any convex hull that is dense around this shape (im) should be a subset of these points (contour). In other words, if "somefunc ()" is effective at filtering inside points, it saves time for calculating a convex hull.

I have code that performs the above trick, but I hope someone has a smarter (quick search), since I need to run it many times. The code I have is:

 # I have a 2D binary field. random for the purpose of demonstration. import numpy as np im = np.random.random((320,360)) > 0.9 # This is my algorithm so far. Notice that coords is sorted. coords = np.argwhere(im) left = np.roll(coords[:,0], 1, axis=0) != coords[:,0] outline = np.vstack([coords[left], coords[left[1:]], coords[-1]]) 

Another idea I used was to use Python reduce (), so I would only need to run the list of coords once. But it’s hard for me to find a good reduction function.

Any help would be greatly appreciated!

change

At the same time, I found a faster way to go from im directly to outline . At least with large images, this happens much faster. In the apparent absence of an external solution, I consider this a solution to this issue.

However, if someone knows an even faster method, please say :)

Answer 1

In the absence of an acceptable answer, I am posting my best working code as a solution.

 def outline(im): ''' Input binary 2D (NxM) image. Ouput array (2xK) of K (y,x) coordinates where 0 <= K <= 2*M. ''' topbottom = np.empty((1,2*im.shape[1]), dtype=np.uint16) topbottom[0,0:im.shape[1]] = np.argmax(im, axis=0) topbottom[0,im.shape[1]:] = (im.shape[0]-1)-np.argmax(np.flipud(im), axis=0) mask = np.tile(np.any(im, axis=0), (2,)) xvalues = np.tile(np.arange(im.shape[1]), (1,2)) return np.vstack([topbottom,xvalues])[:,mask].T 

Answer 2

This assignment seems to do the same as your last two steps:

 outline = np.array(dict(reversed(coords)).items() + dict(coords).items()) 

I don’t know if it works faster.

Answer 3

For a more general solution, you can use some edge detection method to find only the boundary points. I believe (Google ..) that NumPy has a built-in sobel filter that will do this.