Active Contour Model

quick post about something I did last year for a project that never went anywhere.

the Active Contour Model (ACM) is an old fashioned way of vectorizing the contour of an object. it works very well when an object is isolated on a flat color but the principle can also be used “live” to determine where the “border” between different shapes is. In Photoshop, this would correspond to the “magic wand” and the “quick selection tool” respectively.

ACM uses morphological snakes, the principle of snakes is fairly simple to understand, the animations, from this Python implementation’s repo clearly explain the idea. the snake is basically a polyline that can expand or shrink as needed. below the snake is used to enclose a starfish shape.

the snake is like an elastic, first it’s stretched around the starfish and gradually tightens. there’s a major difference between a snake and an elesatic, the snake can go “inside” the creases when an elastic would remain “outside” (thus describing the convex hull of the starfish ).

and in this example, the snake behaves more like expanding foam, progressively filling the space around its starting point until it reaches a boundary.

if the two behaviours seem different, they are actually the same ; the snake is driven by gradient descent, which is a fancy way of saying that the points of the snake are always “rolling downhill”.

so, this gradient is the first thing we’ll have to compute,  we’ll need the distance of each pixel to the object we want to capture.

to find this object, I threshold the luminance of each pixel against an arbitrary value, this gives a binary (black & white) image.

so this glorious rooster:

gives this binary image after threshold

then I found & ported a Java example that computes the gradient flows. I don’t quite understand everything that happens there but it samples the neighbourhood of each pixel with a sparse convolution matrix twice, forward and backwards. during the forward pass, it gives an average score to each pixel and during the backwards pass, it sums them up to get the final result.

our binary image will turn into this Worley-ish voronoi-ish series of gradients:

along which the snakes’ points will be free to roll. also note that the black areas contain the morphological skeleton of the image which can be extremely useful :)

with 2, 2D dimensional Flow martices flowX & flowY, we move the points around by doing something like:

an interesting property of the snake is it’s ability to shrink / expand. this is one of the properties of differential growth, it’s a very rich mechanic. the snake is made of edges and stores a min/max length for an edge. each time we update the snake, it can either :

1. destroy an edge if it is too short
2. do nothing if the edge is not too short and not too long
3. subdivide an edge if it is too long

or in code:

simple enough right?
and this kind of logic is used in many procedurally generated pieces like this for instance:

it’s important to note that the snake should stop when all the points have reached a local minima (the bottom of a valley) but that it doesn’t always happen so I’ve set a max number of iterations instead. Once the process is over, the callback method recieves a series of points that describe the enclosing shape, this polygon can be used to mask or clip the image, or just as a vector shape.

I’ll leave you with a bunch of samples, click on the pictures below to get started.

here’s a ZIP of the code with the sample images, they come from https://www.walldevil.com/

enjoy :)