python contour for binary 2D matrix

Question

Hi,

I want to calculate a convex hull around a shape in a binary NxM matrix. The convex hull algorithm expects a list of coordinates, so I take numpy.argwhere(im) to have all shape point coordinates. However, most of those points are not contributing to the convex hull (they lie on the inside of the shape). Because convex hull computation time is at least proportional to the number of points that it gets as input, I devised an idea to filter the plethora of useless points on beforehand and only pass those that span the outline. The idea is quite simple, that for each row in the binary NxM matrix I take only the minimal and maximal indices. So 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 outline should 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 tight around this shape (im), must a subset of these points (outline). In other words, if "somefunc()" is efficient in filtering the inside points then it saves time for the convex hull computation.

I have code that does the above trick, but I am hoping someone has a more clever (read faster) approach since I need to run it many 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 had was to use Python's reduce() so I'd need to run over the list of coords only once. But I have difficulty finding a good reducing function.

Any help would greatly be appreciated!

edit

In the meanwhile I have found a faster way to go from im directly to outline. At least with large images this is significantly faster. In the apparent absence of an external solution I am positing it as the solution to this question.

Still, if somebody knows an even faster method, please speak up :)

Answer 1

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

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

Don't know if it's any faster, however.

Answer 2

For more general solution, you could use somekind of edge detection method to find only the edge points. I believe (Google..) that NumPy has built-in sobel filter, which will do that.

Answer 3

In the absence of an acceptable answer I post my best working code as the 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